Fix 'leading zeros' caveat of StringRef::compare_numeric()

[snnw]

Summary

compare_numeric() now ignores leading zeros of any numbers embedded in StringRef. Previously, a longer number would always be considered larger than the shorter number. For example, "007" would be considered larger than "8". The behaviour is now more intuitive.

[chandlerc]

This adds lots of code and makes the code harder to read in order to handle this case.

Is there a specific problem you're addressing here? Can you work to make the code more readable rather than less readable if we need to support this use case?

Also, this ignores the common usage of a leading zero to indicate octal. I'm somewhat worried about StringRef having divergent behavior there.

[snnw]

Thanks for the review.

I'm not addressing a specific problem here; merely going off on the
comment mentioning that prefixed zeroes didn't work very well. I
gather that you'd argue against merging in this case, even if the code
were more readable. (I'd be happy to work on the readability, though.)

Regarding octal numbers: I believe behaviour is unchanged. Comparison
between two octal numbers (with or without leading zeroes) should work
as expected. Exactly which behaviour are you worried about?

[snnw]

Improved readability by using strtol(), which handles the conversion to numericals. It automatically handles prefixes of 0x for hexadecimal and 0 for octal.

Should be more readable than the original, as well. :)

[chandlerc]

This is a complex change to a routine with a strange and unclear interface and purpose.

In fact, this code is only called in one place that I can find outside of its unit tests: include/llvm/TableGen/Record.h. I'm not sure what that code is trying to do, but I don't think adding more complexity here to handle a corner case is the right path forward. I suspect that code should be rolling its own (hopefully *simpler* and more domain specific) logic and this method should just be deleted. But that doesn't really seem critically important either.

What I am confident in is that we shouldn't burn complexity and risk of bugs (or performance hits) on trying to make this function handle leading zeros particularly gracefully.

[craig.topper]

I believe it's current usage in TableGen I believe is to make record names come out in order like this.

XMM0
XMM1
XMM2
...
XMM9
XMM10

I'm not sure it matters to support octal or hex in a context where it's embedded in string with letters in it. It would definitely be weird for hex.

For the tablegen use case I think if someone were to put in extra zeros in their tablegen recrds they would only do so to put a consistent number of digits in all records with a common prefix string. So I don't think supporting leading zeros gracefully is necessary.

lib/Support/StringRef.cpp

 /// Check if this string ends with the given \p Suffix, ignoring case.
 bool StringRef::endswith_lower(StringRef Suffix) const {
   return Length >= Suffix.Length &&
       ascii_strncasecmp(end() - Suffix.Length, Suffix.Data, Suffix.Length) == 0;
 }
 
 /// compare_numeric - Compare strings, handle embedded numbers.
 int StringRef::compare_numeric(StringRef RHS) const {
-  for (size_t I = 0, E = std::min(Length, RHS.Length); I != E; ++I) {
+  size_t IL, IR;
+  for (IL = 0, IR = 0; IL != Length && IR != RHS.Length; ++IL, ++IR) {
     // Check for sequences of digits.
-    if (ascii_isdigit(Data[I]) && ascii_isdigit(RHS.Data[I])) {
-      // The longer sequence of numbers is considered larger.
-      // This doesn't really handle prefixed zeros well.
-      size_t J;
-      for (J = I + 1; J != E + 1; ++J) {
-        bool ld = J < Length && ascii_isdigit(Data[J]);
-        bool rd = J < RHS.Length && ascii_isdigit(RHS.Data[J]);
+    if (ascii_isdigit(Data[IL]) && ascii_isdigit(RHS.Data[IR])) {
+      // Skip any leading zeros.
+      while (Data[IL] == '0' && IL + 1 != Length && ascii_isdigit(Data[IL + 1]))
+        ++IL;
+      while (RHS.Data[IR] == '0' && IR + 1 != RHS.Length &&
+             ascii_isdigit(RHS.Data[IR + 1]))
+        ++IR;
+
+      size_t JL, JR;
+      for (JL = IL + 1, JR = IR + 1; JL != Length + 1 && JR != RHS.Length + 1;
+           ++JL, ++JR) {
+        bool ld = JL < Length && ascii_isdigit(Data[JL]);
+        bool rd = JR < RHS.Length && ascii_isdigit(RHS.Data[JR]);
         if (ld != rd)
           return rd ? -1 : 1;
         if (!rd)
           break;
       }
-      // The two number sequences have the same length (J-I), just memcmp them.
-      if (int Res = compareMemory(Data + I, RHS.Data + I, J - I))
+      // The two number sequences (excluding leading zeros) have the same
+      // length, just memcmp them.
+      if (int Res = compareMemory(Data + IL, RHS.Data + IR, JL - IL))
         return Res < 0 ? -1 : 1;
       // Identical number sequences, continue search after the numbers.
-      I = J - 1;
+      IL = JL - 1;
+      IR = JR - 1;
       continue;
     }
-    if (Data[I] != RHS.Data[I])
-      return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1;
+    if (Data[IL] != RHS.Data[IR])
+      return (unsigned char)Data[IL] < (unsigned char)RHS.Data[IR] ? -1 : 1;
   }
-  if (Length == RHS.Length)
+  if (Length - IL == RHS.Length - IR)
     return 0;
-  return Length < RHS.Length ? -1 : 1;
+  return Length - IL < RHS.Length - IR ? -1 : 1;
 }
 
 // Compute the edit distance between the two given strings.
 unsigned StringRef::edit_distance(llvm::StringRef Other,
                                   bool AllowReplacements,
                                   unsigned MaxEditDistance) const {
   return llvm::ComputeEditDistance(
       makeArrayRef(data(), size()),

unittests/ADT/StringRefTest.cpp

TEST(StringRefTest, StringOps) {
   EXPECT_EQ( 0, StringRef("aab").compare_numeric("aab"));
   EXPECT_EQ( 1, StringRef("aab").compare_numeric("aaa"));
   EXPECT_EQ(-1, StringRef("aab").compare_numeric("aabb"));
   EXPECT_EQ( 1, StringRef("aab").compare_numeric("aa"));
   EXPECT_EQ(-1, StringRef("1").compare_numeric("10"));
   EXPECT_EQ( 0, StringRef("10").compare_numeric("10"));
   EXPECT_EQ( 0, StringRef("10a").compare_numeric("10a"));
   EXPECT_EQ( 1, StringRef("2").compare_numeric("1"));
+  EXPECT_EQ(-1, StringRef("0a").compare_numeric("1"));
+  EXPECT_EQ( 1, StringRef("2").compare_numeric("01"));
+  EXPECT_EQ(-1, StringRef("2").compare_numeric("03"));
+  EXPECT_EQ( 0, StringRef("007 is 1337").compare_numeric("7 is 01337"));
   EXPECT_EQ( 0, StringRef("llvm_v1i64_ty").compare_numeric("llvm_v1i64_ty"));
   EXPECT_EQ( 1, StringRef("\xFF").compare_numeric("\1"));
   EXPECT_EQ( 1, StringRef("V16").compare_numeric("V1_q0"));
   EXPECT_EQ(-1, StringRef("V1_q0").compare_numeric("V16"));
   EXPECT_EQ(-1, StringRef("V8_q0").compare_numeric("V16"));
   EXPECT_EQ( 1, StringRef("V16").compare_numeric("V8_q0"));
   EXPECT_EQ(-1, StringRef("V1_q0").compare_numeric("V8_q0"));
   EXPECT_EQ( 1, StringRef("V8_q0").compare_numeric("V1_q0"));