filevercmp: fix several unexpected results

Problems reported by Michael Debertol in <https://bugs.gnu.org/49239>.
While looking into this, I spotted some more areas where the
code and documentation did not agree, or where the documentation
was unclear.  The biggest change needed by coreutils is a new
function filenvercmp that can compare byte strings containing NUL.
* lib/filevercmp.c: Do not include sys/types.h, stdlib.h, string.h.
Include idx.h, verify.h.
(match_suffix): Remove, replacing all uses with calls to ...
(file_prefixlen): ... this new function.  Simplify it by
avoiding the need for a confusing READ_ALPHA state variable.
Change its API to something more useful, with a *LEN arg.
it with a new *LEN arg.
(file_prefixlen, verrevcmp):
Prefer idx_t to size_t where either will do.
(order): Change args to S, POS, LEN instead of just S[POS].
This lets us handle NUL bytes correctly.  Callers changed.
Verify that ints are sufficiently wide for its API.
(verrevcmp): Don't assume that S1[S1_LEN] is a non-digit,
and likewise for S2[S2_LEN].  The byte might not be accessible
if filenvercmp is being called.
(filevercmp): Reimplement by calling filenvercmp.
(filenvercmp): New function, rewritten without the assumption
that the inputs are null-terminated.
Remove "easy comparison to see if strings are identical", as the
use of it later (a) was undocumented, and (b) caused sort -V to be
unstable.  When both strings start with ".", do not skip past
the "."s before looking for suffixes, as this disagreed
with the documentation.
* lib/filevercmp.h: Fix comments, which had many mistakes.
(filenvercmp): New decl.
* modules/filevercmp (Depends-on): Add idx, verify.  Remove string.
* tests/test-filevercmp.c: Include string.h.
(examples): Reorder examples ".0" and ".9" that matched the code
but not the documentation.  The code has been fixed to match the
documentation.  Add some examples involving \1 so that they
can be tried with both \1 and \0.  Add some other examples
taken from the bug report.
(equals): New set of test cases.
(sign, test_filevercmp): New functions.
(main): Remove test case where the fixed filevercmp disagrees with
strverscmp.  Use test_filevercmp instead of filevercmp, so that
we also test filenvercmp.  Test the newly-introduced EQUALS cases.

1 files changed, 90 insertions, 4 deletions

diff --git a/tests/test-filevercmp.c b/tests/test-filevercmp.c
index 79ad4aed8f..b2a7e90f3f 100644
--- a/tests/test-filevercmp.c
+++ b/tests/test-filevercmp.c
@@ -19,6 +19,7 @@
 #include "filevercmp.h"
 
 #include <stddef.h>
+#include <string.h>
 
 #include "macros.h"
 
@@ -28,8 +29,6 @@ static const char *const examples[] =
   "",
   ".",
   "..",
-  ".0",
-  ".9",
   ".A",
   ".Z",
   ".a~",
@@ -40,7 +39,14 @@ static const char *const examples[] =
   ".zz~",
   ".zz",
   ".zz.~1~",
+  ".0",
+  ".9",
   ".zz.0",
+  ".\1",
+  ".\1.txt",
+  ".\1x",
+  ".\1x\1",
+  ".\1.0",
   "0",
   "9",
   "A",
@@ -51,6 +57,10 @@ static const char *const examples[] =
   "a.b",
   "a.bc~",
   "a.bc",
+  "a+",
+  "a.",
+  "a..a",
+  "a.+",
   "b~",
   "b",
   "gcc-c++-10.fc9.tar.gz",
@@ -80,10 +90,79 @@ static const char *const examples[] =
   "zz",
   "zz.~1~",
   "zz.0",
+  "zz.0.txt",
+  "\1",
+  "\1.txt",
+  "\1x",
+  "\1x\1",
+  "\1.0",
+  "#\1.b#",
   "#.b#",
   NULL
 };
 
+/* Sets of examples that should all sort equally.  Each set is
+   terminated by NULL.  */
+static char const *const equals[] =
+  {
+    "a",
+    "a0",
+    "a0000",
+    NULL,
+    "a\1c-27.txt",
+    "a\1c-027.txt",
+    "a\1c-00000000000000000000000000000000000000000000000000000027.txt",
+    NULL,
+    ".a\1c-27.txt",
+    ".a\1c-027.txt",
+    ".a\1c-00000000000000000000000000000000000000000000000000000027.txt",
+    NULL,
+    "a\1c-",
+    "a\1c-0",
+    "a\1c-00",
+    NULL,
+    ".a\1c-",
+    ".a\1c-0",
+    ".a\1c-00",
+    NULL,
+    "a\1c-0.txt",
+    "a\1c-00.txt",
+    NULL,
+    ".a\1c-1\1.txt",
+    ".a\1c-001\1.txt",
+    NULL,
+  };
+
+static int
+sign (int i)
+{
+  return i < 0 ? -1 : 0 < i;
+}
+
+/* Return filevercmp (A, B), checking that a similar result is gotten
+   after replacing all '\1's with '\0's and calling filenvercmp with
+   the embedded '\0's.  */
+static int
+test_filevercmp (char const *a, char const *b)
+{
+  int result = filevercmp (a, b);
+
+  char buffer[1000];
+
+  ptrdiff_t alen = strlen (a), blen = strlen (b);
+  ASSERT (alen + blen <= sizeof buffer);
+  memcpy (buffer, a, alen);
+  memcpy (buffer + alen, b, blen);
+  for (ptrdiff_t i = 0; i < alen + blen; i++)
+    if (buffer[i] == '\1')
+      buffer[i] = '\0';
+
+  int nresult = filenvercmp (buffer, alen, buffer + alen, blen);
+  ASSERT (sign (nresult) == sign (result));
+
+  return result;
+}
+
 int
 main (void)
 {
@@ -94,7 +173,6 @@ main (void)
   ASSERT (filevercmp ("a", "a") == 0);
   ASSERT (filevercmp ("a", "b") < 0);
   ASSERT (filevercmp ("b", "a") > 0);
-  ASSERT (filevercmp ("a0", "a") > 0);
   ASSERT (filevercmp ("00", "01") < 0);
   ASSERT (filevercmp ("01", "010") < 0);
   ASSERT (filevercmp ("9", "10") < 0);
@@ -106,7 +184,7 @@ main (void)
       const char *const *j;
       for (j = examples; *j; j++)
         {
-          int result = filevercmp (*i, *j);
+          int result = test_filevercmp (*i, *j);
           if (result < 0)
             ASSERT (i < j);
           else if (0 < result)
@@ -116,5 +194,13 @@ main (void)
         }
     }
 
+  for (i = equals; i < equals + sizeof equals / sizeof *equals; i++)
+    for (; *i; i++)
+      for (char const *const *j = i; *j; j++)
+        {
+          ASSERT (test_filevercmp (*i, *j) == 0);
+          ASSERT (test_filevercmp (*j, *i) == 0);
+        }
+
   return 0;
 }