[test-suite] Use forward-parsing when searching for numbers.

[Meinersbur]

Summary

Avoid trying to backtrack from a character change to the beginning of a floating point comparison in order to parse it. This a unnecessarily error-prone and has other problems such as those fixed in D36768. This patch replaces this by search for the beginning of any number, then always scanning forward to find the end of the number like a parser does.

This patch in particular fixes a problem when comparing the program output of 628.pop2 from to the reference output from SPEC2017. The relevant excepts from the outputs are:

65.000 (program output)
65.0 5 (reference output)

The first character difference is between 0 (program output) and (whitespace from reference). For the program output, the backtrack solution rewinds to 65.000. With the reference output, it has already advanced to 5 (due to the -i ignore whitespace flag; SPEC reference outputs have normalized whitespace). This case is explicitly handled without the -i flag, but backtracking through whitespace would make the algorithm even more complicated and there are other problems such as that it backs-up through any number of exponent characters (e, E, d, D).

Also fixes potential stack overflow when parsing numbers larger than 200 characters and allows identical values with different formatting (0 and 0.0) even with no absolute/relative tolerances defined.

[naromero77]

Ran the entire test suite with GCC 10.2.0. For the record, there was one failure:

********************
Failing Tests (1):
    test-suite :: MultiSource/Benchmarks/Trimaran/enc-pc1/enc-pc1.test
  Expected Passes    : 254
  Unexpected Failures: 1

But after investigation, there was not related to this patch. The results from GCC are incorrect.

[naromero77]

Confirming that all tests are passing with clang/clang++.

[naromero77]

LGTM

[Meinersbur]

• Fix copy&paste File1End

[Meinersbur]

• Special handling of 0.0 tolerances like original

tools/fpcmp.c

 /*===-- fpcmp.c - LLVM Floating point comparison tool ---------------------===*\
 |*                                                                            *|
 |* Part of the LLVM Project, under the Apache License v2.0 with LLVM          *|
 |* Exceptions.                                                                *|
 |* See https://llvm.org/LICENSE.txt for license information.                  *|
 |* SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception                    *|
 |*                                                                            *|
 \*===----------------------------------------------------------------------===*/
 
 /* Note that this file is essentially a bastardized C version of
  * FileUtilities.cpp from LLVM. */
 
 #include <ctype.h>
 #include <math.h>
+#include <stddef.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 const char *g_program;
 
 /* *** */
 
static bool isExponentChar(char C) {
   case 'D':  // Strange exponential notation.
   case 'd':  // Strange exponential notation.
   case 'e':
   case 'E': return true;
   default: return false;
   }
 }
 
-static bool isNumberChar(char C) {
+static bool isDigitChar(char C) {
   switch (C) {
   case '0': case '1': case '2': case '3': case '4':
   case '5': case '6': case '7': case '8': case '9':
-  case '.': return true;
-  default: return isSignedChar(C) || isExponentChar(C);
+    return true;
+  default:
+    return false;
   }
 }
 
-static const char *BackupNumber(const char *Pos, const char *FirstChar,
-                                const char *End) {
-  // If already at the very beginning, we cannot go back further.
-  // It ensures that the access Pos[-1] is valid.
-  // This also handles the case where the file is empty (FirstChar == End).
-  if (Pos == FirstChar)
-    return Pos;
-
-  // If we didn't stop in the middle of a number, don't backup.
-  if (!(Pos == End || isNumberChar(*Pos)) && !isNumberChar(Pos[-1]))
-    return Pos;
-
-  // If we're one past the number, the two numbers can have different number
-  // of digits. Even if we're wrong, and we get the previous number, the
-  // comparison should have failed anyway.
-  if (Pos == End || !isNumberChar(*Pos))
-    Pos--;
-
-  // Otherwise, return to the start of the number.
-  bool HasPeriod = false;
-  while (Pos > FirstChar && isNumberChar(Pos[-1])) {
-    // Backup over at most one period.
-    if (Pos[-1] == '.') {
-      if (HasPeriod)
-        break;
-      HasPeriod = true;
-    }
+static bool isPossibleStartOfNumber(char C) {
+  return isDigitChar(C) || isSignedChar(C) || C == '.';
 
-    --Pos;
-    if (Pos > FirstChar && isSignedChar(Pos[0]) && !isExponentChar(Pos[-1]))
-      break;
+static const char *AdvanceNumber(const char *StartPos, const char *End) {
+  const char *Pos = StartPos;
+  const char *EndOfNumber = NULL;
+
+  // Sign character (optional)
+  if (Pos < End && isSignedChar(*Pos))
+    ++Pos;
+
+  // Pre-decimal digits (optional)
+  while (Pos < End && isDigitChar(*Pos)) {
+    ++Pos;
+    EndOfNumber = Pos;
   }
-  return Pos;
+
+  // Decimal separator
+  if (Pos < End && *Pos == '.') {
+    ++Pos;
+
+    // Post-decimal digits (require at least one when period present)
+    bool HasPostDecimalDigit = false;
+    while (Pos < End && isDigitChar(*Pos)) {
+      HasPostDecimalDigit = true;
+
+      ++Pos;
+      EndOfNumber = Pos;
+    }
+    if (!HasPostDecimalDigit)
+      return EndOfNumber;
   }
 
-/// EndOfNumber - Return the first character that is not part of the specified
-/// number.  This assumes that the buffer is null terminated, so it won't fall
-/// off the end.
-static const char *EndOfNumber(const char *Pos) {
-  while (isNumberChar(*Pos))
+  // Require a valid number before the exponent.
+  // (e.g. don't recognize '+e1' as a number)
+  if (!EndOfNumber)
+    return EndOfNumber;
+
+  // Exponent separator
+  if (Pos < End && isExponentChar(*Pos)) {
+    ++Pos;
+
+    // Exponent sign (optional)
+    if (Pos < End && isSignedChar(*Pos))
+      ++Pos;
+
+    // Exponent digits (require at least one when 'e' present)
+    while (Pos < End && isDigitChar(*Pos)) {
       ++Pos;
-  return Pos;
+      EndOfNumber = Pos;
+    }
+  }
+
+  return EndOfNumber;
 }
 
 static bool skip_whitespace(const char **FP, const char *FEnd) {
   bool skipped_some = false;
   while (*FP < FEnd && isspace((unsigned char)**FP)) {
     skipped_some = true;
     ++*FP;
   }
   return skipped_some;
 }
 
 /// CompareNumbers - compare two numbers, returning true if they are different.
-static bool CompareNumbers(const char **F1PP, const char **F2PP,
-                           const char *F1End, const char *F2End,
-                           double AbsTolerance, double RelTolerance) {
-  const char *F1P = *F1PP;
-  const char *F2P = *F2PP;
+static bool CompareNumbers(const char *F1P, const char *F2P, const char *F1End,
+                           const char *F2End, double AbsTolerance,
+                           double RelTolerance) {
   const char *F1NumEnd, *F2NumEnd;
+  const ptrdiff_t F1Len = F1End - F1P;
+  const ptrdiff_t F2Len = F2End - F2P;
   double V1 = 0.0, V2 = 0.0;
 
-  // If one of the positions is at a space and the other isn't, chomp up 'til
-  // the end of the space.
-  skip_whitespace(&F1P, F1End);
-  skip_whitespace(&F2P, F2End);
-
-  if (F1P == F1End || F2P == F2End) {
-    fprintf(stderr, ("%s: FP Comparison failed, reached end of file\n"),
-            g_program);
-    return true;
-  }
+  // Fast character-by-character comparison of the numbers.
+  if (F1Len == F2Len && memcmp(F1P, F2P, F1Len) == 0)
+    return false;
 
-  // If we stop on numbers, compare their difference.
-  if (!isNumberChar(*F1P) || !isNumberChar(*F2P)) {
-    // The diff failed.
-    F1NumEnd = F1P;
-    F2NumEnd = F2P;
-  } else {
-    // Note that some ugliness is built into this to permit support for numbers
-    // that use "D" or "d" as their exponential marker, e.g. "1.234D45".  This
-    // occurs in 200.sixtrack in spec2k.
-    V1 = strtod(F1P, (char**)(&F1NumEnd));
-    V2 = strtod(F2P, (char**)(&F2NumEnd));
+  V1 = strtod(F1P, (char **)(&F1NumEnd));
+  V2 = strtod(F2P, (char **)(&F2NumEnd));
 
-    if (*F1NumEnd == 'D' || *F1NumEnd == 'd') {
-      // Copy string into tmp buffer to replace the 'D' with an 'e'.
-      char StrTmp[200];
-      memcpy(StrTmp, F1P, EndOfNumber(F1NumEnd)+1 - F1P);
-      // Strange exponential notation!
-      StrTmp[(unsigned)(F1NumEnd-F1P)] = 'e';
+    char *StrTmp = malloc(F1Len + 1);
+    memcpy(StrTmp, F1P, F1Len + 1);
+
+    StrTmp[(unsigned)(F1NumEnd - F1P)] = 'e';
 
-      V1 = strtod(&StrTmp[0], (char**)(&F1NumEnd));
-      F1NumEnd = F1P + (F1NumEnd-&StrTmp[0]);
-    }
+    V1 = strtod(&StrTmp[0], (char **)(&F1NumEnd));
+    F1NumEnd = F1P + (F1NumEnd - &StrTmp[0]);
+
+    free(StrTmp);
 
-    if (*F2NumEnd == 'D' || *F2NumEnd == 'd') {
-      // Copy string into tmp buffer to replace the 'D' with an 'e'.
-      char StrTmp[200];
-      memcpy(StrTmp, F2P, EndOfNumber(F2NumEnd)+1 - F2P);
-      // Strange exponential notation!
-      StrTmp[(unsigned)(F2NumEnd-F2P)] = 'e';
+    char *StrTmp = malloc(F2Len + 1);
+    memcpy(StrTmp, F2P, F2Len + 1);
+
+    StrTmp[(unsigned)(F2NumEnd - F2P)] = 'e';
 
-      V2 = strtod(&StrTmp[0], (char**)(&F2NumEnd));
-      F2NumEnd = F2P + (F2NumEnd-&StrTmp[0]);
-    }
+    V2 = strtod(&StrTmp[0], (char **)(&F2NumEnd));
+    F2NumEnd = F2P + (F2NumEnd - &StrTmp[0]);
+
+    free(StrTmp);
   }
 
   if (F1NumEnd == F1P || F2NumEnd == F2P) {
     fprintf(stderr, ("%s: FP Comparison failed, not a numeric difference "
                      "between '%c' and '%c'\n"), g_program, F1P[0], F2P[0]);
     return true;
   }
 
+  // Quick check for identical values
+  if (V1 == V2)
+    return false;
+
   // Check to see if these are inside the absolute tolerance
-  if (AbsTolerance < fabs(V1-V2)) {
+  if (AbsTolerance == 0.0 || AbsTolerance < fabs(V1 - V2)) {
     // Nope, check the relative tolerance...
     double Diff;
     if (V2)
       Diff = fabs(V1/V2 - 1.0);
     else if (V1)
       Diff = fabs(V2/V1 - 1.0);
     else
       Diff = 0;  // Both zero.
-    if (Diff > RelTolerance) {
+    if (RelTolerance == 0.0 || Diff > RelTolerance) {
       fprintf(stderr, ("%s: Compared: %e and %e\n"
                        "abs. diff = %e rel.diff = %e\n"
                        "Out of tolerance: rel/abs: %e/%e\n"),
               g_program, V1, V2, fabs(V1-V2), Diff, RelTolerance, AbsTolerance);
       return true;
     }
   }
 
-  // Otherwise, advance our read pointers to the end of the numbers.
-  *F1PP = F1NumEnd;  *F2PP = F2NumEnd;
   return false;
 }
 
 /* *** */
 
 char *load_file(const char *path, long *size_out) {
   FILE *fp;
   long size;
int diff_files_with_tolerance(const char *path_a, const char *path_b,
   long A_size, B_size;
   char *data_a = load_file(path_a, &A_size);
   char *data_b = load_file(path_b, &B_size);
 
   /* Fast path equivalent buffers. */
   if (A_size == B_size && memcmp(data_a, data_b, A_size) == 0)
     return 0;
 
-  /* Otherwise, if our tolerances are 0 then we are done. */
-  if (relative_tolerance == 0.0 && absolute_tolerance == 0.0 &&
-      !ignore_whitespace) {
-    fprintf(stderr, "%s: files differ without tolerance allowance\n",
-            g_program);
-    return 1;
-  }
-
   /* *** */
 
   // Okay, now that we opened the files, scan them for the first difference.
   const char *File1Start = data_a;
   const char *File2Start = data_b;
   const char *File1End = data_a + A_size;
   const char *File2End = data_b + B_size;
   const char *F1P = File1Start;
   const char *F2P = File2Start;
 
   while (1) {
+    // Reached the end of at least one file?
+    if (F1P >= File1End || F2P >= File2End) {
+      // Skip any whitespace at the end of the file.
+      if (ignore_whitespace) {
+        skip_whitespace(&F1P, File1End);
+        skip_whitespace(&F2P, File2End);
+      }
+      break;
+    }
+
     // Scan for the end of file or next difference.
-    while (F1P < File1End && F2P < File2End) {
-      if (*F1P == *F2P) {
-        ++F1P, ++F2P;
-        continue;
-      }
+    if (*F1P == *F2P && !isPossibleStartOfNumber(*F1P)) {
 
-      // With whitespace ignored, skip whitespace chars (if any) and recheck for
-      // the next difference.
-      if (ignore_whitespace) {
-        if (skip_whitespace(&F1P, File1End) | skip_whitespace(&F2P, File2End))
-          continue;
-      }
+    // the next difference. Otherwise, only ignore whitespace before numbers.
+    const char *F1NumStart = F1P;
+    const char *F2NumStart = F2P;
+    } else {
+      skip_whitespace(&F1NumStart, File1End);
+      skip_whitespace(&F2NumStart, File2End);
 
-      break;
-    }
+    const char *F1NumEnd = AdvanceNumber(F1NumStart, File1End);
+    const char *F2NumEnd = AdvanceNumber(F2NumStart, File2End);
 
-    if (F1P >= File1End || F2P >= File2End) break;
+    // If one side is a number, but not the other, we found a difference.
+    if (!F1NumEnd || !F2NumEnd) {
+      // If there is no number starting at the current position, it might be a
+      // non-numeric difference.
+      if (*F1P != *F2P)
+        break;
 
-    // BackupNumber will also backup when at the first char after a number. This
-    // is to catch when one of the number has more trailing floating-point zeros
-    // than the other. However, when this is the case in both buffers, we'd
-    // repeat the most recent number forever.
-    // Therefore, we fast-stop if both buffers have no number at the current
-    // position.
-    if (!isNumberChar(*F1P) && !isNumberChar(*F2P)) {
-      fprintf(stderr, "%s: FP Comparison failed, not a numeric difference "
-                      "between '%c' and '%c'\n",
-              g_program, F1P[0], F2P[0]);
-      return 1;
+      // Otherwise, try over with the next pair to eventually find the
+      // difference or a matching number. Consider:
+      //
+      //     +1.0
+      //     ++1.0
+      //
+      // Starting with the first + characters, the first will be recognized as a
+      // number, but not the second. Only when comparing the second characters
+      // both will be recognized as numbers.
+      ++F1P, ++F2P;
+      continue;
     }
 
-    // Okay, we must have found a difference.  Backup to the start of the
-    // current number each stream is at so that we can compare from the
-    // beginning.
-    F1P = BackupNumber(F1P, File1Start, File1End);
-    F2P = BackupNumber(F2P, File2Start, File2End);
-
     // Now that we are at the start of the numbers, compare them, exiting if
     // they don't match.
-    if (CompareNumbers(&F1P, &F2P, File1End, File2End,
+    if (CompareNumbers(F1NumStart, F2NumStart, F1NumEnd, F2NumEnd,
                        absolute_tolerance, relative_tolerance))
       return 1;
-  }
 
-  // Skip any whitespace at the end of the file.
-  if (ignore_whitespace) {
-    skip_whitespace(&F1P, File1End);
-    skip_whitespace(&F2P, File2End);
+    // Numbers compare equal, continue after the numbers.
+    F1P = F1NumEnd;
+    F2P = F2NumEnd;
   }
 
   // Okay, we reached the end of file.  If both files are at the end, we
   // succeeded.
   bool F1AtEnd = F1P >= File1End;
   bool F2AtEnd = F2P >= File2End;
-  if (!F1AtEnd || !F2AtEnd) {
-    // Else, we might have run off the end due to a number: backup and retry.
-    F1P = BackupNumber(F1P, File1Start, File1End);
-    F2P = BackupNumber(F2P, File2Start, File2End);
-
-    // Now that we are at the start of the numbers, compare them, exiting if
-    // they don't match.
-    if (CompareNumbers(&F1P, &F2P, File1End, File2End,
-                       absolute_tolerance, relative_tolerance))
-      return 1;
-
-    // There might be more whitespace after the number.
-    if (ignore_whitespace) {
-      skip_whitespace(&F1P, File1End);
-      skip_whitespace(&F2P, File2End);
-    }
-
-    // If we found the end, we succeeded.
-    if (F1P < File1End || F2P < File2End)
-      return 1;
+  if (!F1AtEnd && !F2AtEnd) {
+    fprintf(stderr,
+            "%s: FP Comparison failed, not a numeric difference between '%c' "
+            "and '%c'\n",
+            g_program, F1P[0], F2P[0]);
+  if (!F1AtEnd || !F2AtEnd) {
+    fprintf(stderr,
+            "%s: FP Comparison failed, unexpected end of one of the files\n",
+            g_program);
   }
 
   return 0;
 }
 
 void usage() {
   fprintf(stderr, "usage: %s [-a VALUE] [-r VALUE] [-i] <path-A> <path-B>\n\n",
           g_program);