How to Prove a Refactor Is Safe Without Unit Tests

You want to make a routine faster or tidier, but there are no unit tests for it, and writing a proper test suite first would take longer than the change. The routine is old, it is called from all over the place, and nobody can say for certain what it returns for every input.

You do not need to know. You already have a perfect description of the correct behaviour: the current code. Keep a copy of it, write the new version, and run both on the same inputs - a million of them if you like - comparing everything each one returns. Any difference is reported with the input that caused it. This is called differential testing, and for a single routine it takes about fifteen minutes to set up.

The Example

The routine splits a string at the first character that belongs to a set. It returns the part before that character, removes that part and the separator from the line, and returns the position found. The current version calls Pos once for every character from 1 to 255 that is in the set, so it scans the line up to 255 times:

for I := 1 to 255 do
begin
  C := Char(I);
  if C in AChs then
  begin
    J := Pos(C, ALine);
    if (J <> 0) and (J < APosn) then
      APosn := J;
  end;
end;

The replacement walks the line once and stops at the first match:

for J := 1 to Length(ALine) do
  if (ALine[J] <> #0) and (Ord(ALine[J]) <= 255) and (AnsiChar(ALine[J]) in AChs) then
  begin
    APosn := J;
    Break;
  end;

It looks equivalent. The two extra conditions are there because of details of the old loop: it starts at 1, so it never finds #0, and it only ever looks for characters up to 255. Getting either one wrong would change results for a few unusual inputs - exactly the kind of mistake that reading the code does not catch.

The Comparison Program

A console program with both versions in it. The old one is pasted in unchanged; the new one is the candidate. {$IFDEF BROKEN} removes the #0 check, so the same program can show what a failure looks like.

program Compare_Split;

// Runs the old and new versions of a routine side by side on generated
// input and reports every case where they disagree.

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  System.Diagnostics;

type
  TCharSet = set of AnsiChar;

{ The routine as it is now - copied unchanged }
function Old_Split(var ALine: string; const AChs: TCharSet; var APosn: Integer): string;
var
  I, J: Integer;
  C: Char;
begin
  APosn := Length(ALine) + 1;
  for I := 1 to 255 do
  begin
    C := Char(I);
    if C in AChs then
    begin
      J := Pos(C, ALine);
      if (J <> 0) and (J < APosn) then
        APosn := J;
    end;
  end;
  if APosn > Length(ALine) then
  begin
    Result := ALine;
    ALine := '';
  end
  else
  begin
    Result := Copy(ALine, 1, APosn - 1);
    Delete(ALine, 1, APosn);
  end;
end;

{ The proposed replacement - one pass over the line }
function New_Split(var ALine: string; const AChs: TCharSet; var APosn: Integer): string;
var
  J: Integer;
begin
  APosn := Length(ALine) + 1;
  for J := 1 to Length(ALine) do
    if {$IFDEF BROKEN} {$ELSE} (ALine[J] <> #0) and {$ENDIF}
       (Ord(ALine[J]) <= 255) and (AnsiChar(ALine[J]) in AChs) then
    begin
      APosn := J;
      Break;
    end;
  if APosn > Length(ALine) then
  begin
    Result := ALine;
    ALine := '';
  end
  else
  begin
    Result := Copy(ALine, 1, APosn - 1);
    Delete(ALine, 1, APosn);
  end;
end;

const
  // Characters chosen to hit the edges: separators, #0, the top of the byte
  // range, and characters above 255 whose low byte is a separator (#$012C is
  // ',' + $0100, #$0141 is 'A' + $0100)
  Pool: array [0..15] of Char =
    ('a', 'b', ',', ';', ' ', '=', #9, #0, #$7F, #$0080, #$00FF,
     #$0100, #$012C, #$0141, #$203B, #$FF0C);

function RandomLine: string;
var
  I: Integer;
begin
  SetLength(Result, Random(12));
  for I := 1 to Length(Result) do
    Result[I] := Pool[Random(Length(Pool))];
end;

function RandomSet: TCharSet;
var
  I: Integer;
begin
  Result := [];
  for I := 0 to Random(5) do
    case Random(5) of
      0: Include(Result, AnsiChar(','));
      1: Include(Result, AnsiChar(';'));
      2: Include(Result, AnsiChar(#0));
      3: Include(Result, AnsiChar('A'));
    else
      Include(Result, AnsiChar(Random(256)));
    end;
end;

function Show(const S: string): string;
var
  I: Integer;
begin
  Result := '';
  for I := 1 to Length(S) do
    if (S[I] >= ' ') and (S[I] <= '~') then
      Result := Result + S[I]
    else
      Result := Result + '#$' + IntToHex(Ord(S[I]), 4);
  Result := '''' + Result + '''';
end;

function ShowSet(const ASet: TCharSet): string;
var
  C: AnsiChar;
begin
  Result := '';
  for C := Low(AnsiChar) to High(AnsiChar) do
    if C in ASet then
      Result := Result + ' #' + IntToStr(Ord(C));
  Result := '[' + Trim(Result) + ']';
end;

const
  Cases = 1000000;
  MaxReported = 5;

var
  K, Run, LDifferences: Integer;
  LSet: TCharSet;
  LInput, LOldLine, LNewLine, LOldResult, LNewResult: string;
  LOldPosn, LNewPosn: Integer;
  LWatch: TStopwatch;
  LOldMs, LNewMs: Int64;
begin
  RandSeed := 20261021;   // fixed, so a failure can be repeated
  LDifferences := 0;
  for K := 1 to Cases do
  begin
    LInput := RandomLine;
    LSet := RandomSet;

    LOldLine := LInput;
    LNewLine := LInput;
    LOldResult := Old_Split(LOldLine, LSet, LOldPosn);
    LNewResult := New_Split(LNewLine, LSet, LNewPosn);

    // Compare everything the routine returns, including var parameters
    if (LOldResult <> LNewResult) or (LOldLine <> LNewLine) or (LOldPosn <> LNewPosn) then
    begin
      Inc(LDifferences);
      if LDifferences <= MaxReported then
        WriteLn(Format('Case %d: line %s set %s'#13#10 +
                       '  old: result %s rest %s posn %d'#13#10 +
                       '  new: result %s rest %s posn %d',
                       [K, Show(LInput), ShowSet(LSet),
                        Show(LOldResult), Show(LOldLine), LOldPosn,
                        Show(LNewResult), Show(LNewLine), LNewPosn]));
    end;
  end;
  WriteLn(Format('%d cases, %d differences', [Cases, LDifferences]));

  // Timing on a longer line, after the results are known to match.
  // Best of five runs, to take out noise from the rest of the machine.
  LInput := StringOfChar('a', 200) + ',';
  LSet := [',', ';'];
  LOldMs := High(Int64);
  LNewMs := High(Int64);
  for Run := 1 to 5 do
  begin
    LWatch := TStopwatch.StartNew;
    for K := 1 to 1000000 do
    begin
      LOldLine := LInput;
      Old_Split(LOldLine, LSet, LOldPosn);
    end;
    if LWatch.ElapsedMilliseconds < LOldMs then
      LOldMs := LWatch.ElapsedMilliseconds;

    LWatch := TStopwatch.StartNew;
    for K := 1 to 1000000 do
    begin
      LNewLine := LInput;
      New_Split(LNewLine, LSet, LNewPosn);
    end;
    if LWatch.ElapsedMilliseconds < LNewMs then
      LNewMs := LWatch.ElapsedMilliseconds;
  end;
  WriteLn(Format('1,000,000 splits of a 201 character line, best of 5: old %d ms, new %d ms', [LOldMs, LNewMs]));

  ExitCode := LDifferences;
end.

Choosing the Inputs

Random input finds nothing if it never reaches the cases where the two versions could differ. The generator above is random, but from a small pool chosen on purpose:

the separators the routine is normally used with - comma, semicolon, space, equals and tab;
#0, because the old loop starts at 1;
#$007F, #$0080 and #$00FF, the edges of the byte range;
characters above 255 whose low byte is a separator or a letter, such as #$012C (low byte is a comma) and #$0141 (low byte is 'A'), to catch any code that cuts characters down to one byte;
lines from 0 to 11 characters, so empty lines, single characters and a separator at either end all occur many times.

Sets are built the same way: the usual separators, #0, 'A' and some random bytes. With such a small pool, a million cases cover every short combination many times over.

Write character codes with four hex digits. While writing this program, the pool first contained #$80, and the output showed it as #$20AC, the euro sign: Delphi treats a two-digit character code from #$80 to #$FF as a byte in the source code page and converts it. #$0080 is taken literally.

The Results

The candidate as written:

1000000 cases, 0 differences
1,000,000 splits of a 201 character line, best of 5: old 664 ms, new 466 ms

Built with -DBROKEN, the version without the #0 check:

Case 1: line '#$0000#$FF0C#$007Fa#$203Bba' set [#0 #59]
  old: result '#$0000#$FF0C#$007Fa#$203Bba' rest '' posn 8
  new: result '' rest '#$FF0C#$007Fa#$203Bba' posn 1
...
1000000 cases, 111723 differences

Each report gives the input and both outputs, which is usually enough to see the cause straight away - here, the new version found #0 at position 1 and the old one never looks for it. Because RandSeed is fixed, the same cases come up on every run, so a fix can be checked against exactly the inputs that failed.

Making It Reliable

Compare every output. Here that is the result, the changed var parameter and the position. A refactor that returns the right result but leaves the line different is still a bug.
Give both versions identical input. Copy anything passed by reference before each call, as the program does with LOldLine and LNewLine.
Paste the old version, do not reconstruct it. The point is to compare against what the code does now, bugs included.
Make the input space small and dense. A pool of 16 characters and short lines covers far more combinations than random text of any length.
Test exhaustively when you can. A routine that takes one character can be checked against all 65,536 values of Char in a few milliseconds - no sampling at all.
Fix the seed. A failure you cannot repeat is very hard to fix.
Time it only after the results match. Then the speed-up is real. Take the best of several runs; single runs of this program varied by up to 50% from one to the next.

What It Does Not Do

It proves the new code behaves like the old code on the inputs you generated. It does not prove the old code was right, and it says nothing about inputs your generator never produces. When the old behaviour is wrong and you mean to change it, keep the comparison and add an exception for that one case, so every other difference is still reported.

Keep the program after the change goes in. With the old version renamed and kept as a reference, it is a regression test for the next person who touches the routine.

PBS Delphi - Comparing Old and New Code Side by Side

Back to Articles for Developers
Back to Articles on Delphi
Delphi Warnings W1050, W1057 and W1058 Explained
Interposer Classes in Delphi

If you found this useful, then please consider making a donation.

Please donate if helpful