Re: Initial Travis testing results look great. One failed self test on OS X 10.10

[Bruno Haible]

Jeffrey Walton wrote in
<https://lists.gnu.org/archive/html/bug-gnulib/2020-03/msg00085.html>:
> FAIL: test-argp-2.sh
> ====================
> 
> *** argp.61477  2020-03-28 20:12:34.000000000 -0400
> --- -   2020-03-28 20:12:34.583510000 -0400
> ***************
> *** 1,4 ****
> ! Usage: test-argp [-tvCSOlp?V] [-f FILE] [-r FILE] [-o[ARG]] [--test]
> !             [--file=FILE] [--input=FILE] [--read=FILE] [--verbose] 
> [--cantiga]
> !             [--sonet] [--option] [--optional[=ARG]] [--many] [--one] [--two]
> !             [--limerick] [--poem] [--help] [--usage] [--version] ARGS...
> --- 1,4 ----
> ! Usage: test-argp [-tCSvOpl?V] [-f FILE] [-r FILE] [-o[ARG]] [--test]
> !             [--cantiga] [--sonet] [--file=FILE] [--input=FILE] [--read=FILE]
> !             [--verbose] [--option] [--optional[=ARG]] [--poem] [--limerick]
> !             [--many] [--one] [--two] [--help] [--usage] [--version] ARGS...
> *** argp.61477  2020-03-28 20:12:34.000000000 -0400
> --- -   2020-03-28 20:12:34.626794000 -0400
> ***************
> *** 1,4 ****
> ! Usage: test-argp [-tvCSOlp?V] [-f FILE] [-r FILE] [-o[ARG]] [--test]
> ! [--file=FILE] [--input=FILE] [--read=FILE] [--verbose] [--cantiga] [--sonet]
> ! [--option] [--optional[=ARG]] [--many] [--one] [--two] [--limerick] [--poem]
>   [--help] [--usage] [--version] ARGS...
> --- 1,4 ----
> ! Usage: test-argp [-tCSvOpl?V] [-f FILE] [-r FILE] [-o[ARG]] [--test]
> ! [--cantiga] [--sonet] [--file=FILE] [--input=FILE] [--read=FILE] [--verbose]
> ! [--option] [--optional[=ARG]] [--poem] [--limerick] [--many] [--one] [--two]
>   [--help] [--usage] [--version] ARGS...
> *** argp.61477  2020-03-28 20:12:34.000000000 -0400
> --- -   2020-03-28 20:12:34.657116000 -0400
> ***************
> *** 5,17 ****
>     -t, --test
> 
>    Option Group 1
> -   -f, -r, --file=FILE, --input=FILE, --read=FILE
> -                              Option with a mandatory argument
> -   -v, --verbose              Simple option without arguments
> 
>    Option Group 1.1
>     -C, --cantiga              create a cantiga
>     -S, --sonet                create a sonet
> 
>    Option Group 2
>     -O, --option               An option
> --- 5,17 ----
>     -t, --test
> 
>    Option Group 1
> 
>    Option Group 1.1
>     -C, --cantiga              create a cantiga
>     -S, --sonet                create a sonet
> +   -f, -r, --file=FILE, --input=FILE, --read=FILE
> +                              Option with a mandatory argument
> +   -v, --verbose              Simple option without arguments
> 
>    Option Group 2
>     -O, --option               An option
> ***************
> *** 19,32 ****
>     -o, --optional[=ARG]       Option with an optional argument. ARG is one of
>                                the following:
> 
>     many                       many units
>     one                        one unit
>     two                        two units
> 
> -  Option Group 2.1
> -   -l, --limerick             create a limerick
> -   -p, --poem                 create a poem
> -
>     -?, --help                 give this help list
>         --usage                give a short usage message
>     -V, --version              print program version
> --- 19,32 ----
>     -o, --optional[=ARG]       Option with an optional argument. ARG is one of
>                                the following:
> 
> +  Option Group 2.1
> +   -p, --poem                 create a poem
> +   -l, --limerick             create a limerick
> +
>     many                       many units
>     one                        one unit
>     two                        two units
> 
>     -?, --help                 give this help list
>         --usage                give a short usage message
>     -V, --version              print program version
> FAIL test-argp-2.sh (exit status: 1)

As I observe this failure also on FreeBSD, and it makes the '--help' output
produce really nonsensical output, I decided to dig deeper.

In 2009, we had a case where the suspicion that qsort() is used in an invalid
manner, but that was not the cause of the bug, back then:
<https://lists.gnu.org/archive/html/bug-gnulib/2009-09/msg00287.html>.

But now it is. Recall the requirements that a comparison function passed to
qsort() must fulfil:
<https://pubs.opengroup.org/onlinepubs/9699919799/functions/qsort.html>

  "When the same objects (consisting of width bytes, irrespective of their
   current positions in the array) are passed more than once to the comparison
   function, the results shall be consistent with one another. That is, they
   shall define a total ordering on the array."

I added debugging code to print the contents of the argument array passed to
qsort(), as well as a matrix of all the cmp(entry[i], entry[j]) results, and
a verification of the "total ordering" property, and found:

  * The argument arrary is the same on glibc and on macOS,
  * The matrix of cmp(entry[i], entry[j]) results is the same on glibc and
    on macOS,
  * The verification of the "total ordering" property prints many failures.

This means that qsort() has undefined behaviour, the way it is invoked.

And it is not surprising that different qsort implementations (in glibc
vs. macOS/FreeBSD) produce different results.

This patch fixes the test failure by rewriting the comparison function in
a way that it is a total ordering. Recall that the easiest way to guarantee
a total ordering is to use lexicographic ordering
<https://en.wikipedia.org/wiki/Lexicographic_order>. All functions defined as

int foo_cmp (const foo *foo1, const foo *foo2)
{
  int cmp = prop1_compare (prop1 (foo1), prop1 (foo2));
  if (cmp != 0)
    return cmp;

  cmp = prop2_compare (prop2 (foo1), prop2 (foo2));
  if (cmp != 0)
    return cmp;

  ...

  cmp = propN_compare (propN (foo1), propN (foo2));
  if (cmp != 0)
    return cmp;

  return 0;
}

(with prop1_compare, ..., propN_compare being total order functions) are
total orderings.

I will soon submit a glibc bug to get this fixed in glibc as well.


2020-12-08  Bruno Haible  <bruno@clisp.org>

        argp: Avoid undefined behaviour when invoking qsort().
        This fixes a test-argp-2.sh test failure on macOS and FreeBSD.
        Reported by Jeffrey Walton <noloader@gmail.com> in
        <https://lists.gnu.org/archive/html/bug-gnulib/2020-03/msg00085.html>.
        * lib/argp-help.c (group_cmp): Remove third argument.
        (hol_sibling_cluster_cmp, hol_cousin_cluster_cmp): New functions, based
        upon hol_cluster_cmp.
        (hol_cluster_cmp): Use hol_cousin_cluster_cmp.
        (hol_entry_cmp): Rewritten to implement a total order.

diff --git a/lib/argp-help.c b/lib/argp-help.c
index 29d0f03..1cb0b84 100644
--- a/lib/argp-help.c
+++ b/lib/argp-help.c
@@ -672,37 +672,93 @@ hol_set_group (struct hol *hol, const char *name, int 
group)
     entry->group = group;
 }
 
-/* Order by group:  0, 1, 2, ..., n, -m, ..., -2, -1.
-   EQ is what to return if GROUP1 and GROUP2 are the same.  */
+/* -------------------------------------------------------------------------- 
*/
+/* Sorting the entries in a HOL.                                              
*/
+
+/* Order by group:  0, 1, 2, ..., n, -m, ..., -2, -1.  */
 static int
-group_cmp (int group1, int group2, int eq)
+group_cmp (int group1, int group2)
 {
-  if (group1 == group2)
-    return eq;
-  else if ((group1 < 0 && group2 < 0) || (group1 >= 0 && group2 >= 0))
+  if ((group1 < 0 && group2 < 0) || (group1 >= 0 && group2 >= 0))
     return group1 - group2;
   else
+    /* Return > 0 if group1 < 0 <= group2.
+       Return < 0 if group2 < 0 <= group1.  */
     return group2 - group1;
 }
 
-/* Compare clusters CL1 & CL2 by the order that they should appear in
+/* Compare clusters CL1 and CL2 by the order that they should appear in
+   output.  Assume CL1 and CL2 have the same parent.  */
+static int
+hol_sibling_cluster_cmp (const struct hol_cluster *cl1,
+                         const struct hol_cluster *cl2)
+{
+  /* Compare by group first.  */
+  int cmp = group_cmp (cl1->group, cl2->group);
+  if (cmp != 0)
+    return cmp;
+
+  /* Within a group, compare by index within the group.  */
+  return cl2->index - cl1->index;
+}
+
+/* Compare clusters CL1 and CL2 by the order that they should appear in
+   output.  Assume CL1 and CL2 are at the same depth.  */
+static int
+hol_cousin_cluster_cmp (const struct hol_cluster *cl1,
+                        const struct hol_cluster *cl2)
+{
+  if (cl1->parent == cl2->parent)
+    return hol_sibling_cluster_cmp (cl1, cl2);
+  else
+    {
+      /* Compare the parent clusters first.  */
+      int cmp = hol_cousin_cluster_cmp (cl1->parent, cl2->parent);
+      if (cmp != 0)
+        return cmp;
+
+      /* Next, compare by group.  */
+      cmp = group_cmp (cl1->group, cl2->group);
+      if (cmp != 0)
+        return cmp;
+
+      /* Next, within a group, compare by index within the group.  */
+      return cl2->index - cl1->index;
+    }
+}
+
+/* Compare clusters CL1 and CL2 by the order that they should appear in
    output.  */
 static int
 hol_cluster_cmp (const struct hol_cluster *cl1, const struct hol_cluster *cl2)
 {
   /* If one cluster is deeper than the other, use its ancestor at the same
-     level, so that finding the common ancestor is straightforward.  */
-  while (cl1->depth > cl2->depth)
-    cl1 = cl1->parent;
-  while (cl2->depth > cl1->depth)
-    cl2 = cl2->parent;
+     level.  Then, go by the rule that entries that are not in a sub-cluster
+     come before entries in a sub-cluster.  */
+  if (cl1->depth > cl2->depth)
+    {
+      do
+        cl1 = cl1->parent;
+      while (cl1->depth > cl2->depth);
+      int cmp = hol_cousin_cluster_cmp (cl1, cl2);
+      if (cmp != 0)
+        return cmp;
 
-  /* Now reduce both clusters to their ancestors at the point where both have
-     a common parent; these can be directly compared.  */
-  while (cl1->parent != cl2->parent)
-    cl1 = cl1->parent, cl2 = cl2->parent;
+      return 1;
+    }
+  else if (cl1->depth < cl2->depth)
+    {
+      do
+        cl2 = cl2->parent;
+      while (cl1->depth < cl2->depth);
+      int cmp = hol_cousin_cluster_cmp (cl1, cl2);
+      if (cmp != 0)
+        return cmp;
 
-  return group_cmp (cl1->group, cl2->group, cl2->index - cl1->index);
+      return -1;
+    }
+  else
+    return hol_cousin_cluster_cmp (cl1, cl2);
 }
 
 /* Return the ancestor of CL that's just below the root (i.e., has a parent
@@ -733,77 +789,116 @@ canon_doc_option (const char **name)
   return non_opt;
 }
 
-/* Order ENTRY1 & ENTRY2 by the order which they should appear in a help
-   listing.  */
+/* Order ENTRY1 and ENTRY2 by the order which they should appear in a help
+   listing.
+   This function implements a total order, that is:
+     - if cmp (entry1, entry2) < 0 and cmp (entry2, entry3) < 0,
+       then cmp (entry1, entry3) < 0.
+     - if cmp (entry1, entry2) < 0 and cmp (entry2, entry3) == 0,
+       then cmp (entry1, entry3) < 0.
+     - if cmp (entry1, entry2) == 0 and cmp (entry2, entry3) < 0,
+       then cmp (entry1, entry3) < 0.
+     - if cmp (entry1, entry2) == 0 and cmp (entry2, entry3) == 0,
+       then cmp (entry1, entry3) == 0.  */
 static int
 hol_entry_cmp (const struct hol_entry *entry1,
                const struct hol_entry *entry2)
 {
-  /* The group numbers by which the entries should be ordered; if either is
-     in a cluster, then this is just the group within the cluster.  */
-  int group1 = entry1->group, group2 = entry2->group;
-
-  if (entry1->cluster != entry2->cluster)
+  /* First, compare the group numbers.  For entries within a cluster, what
+     matters is the group number of the base cluster in which the entry
+     resides.  */
+  int group1 = (entry1->cluster
+                ? hol_cluster_base (entry1->cluster)->group
+                : entry1->group);
+  int group2 = (entry2->cluster
+                ? hol_cluster_base (entry2->cluster)->group
+                : entry2->group);
+  int cmp = group_cmp (group1, group2);
+  if (cmp != 0)
+    return cmp;
+
+  /* The group numbers are the same.  */
+
+  /* Entries that are not in a cluster come before entries in a cluster.  */
+  cmp = (entry1->cluster != NULL) - (entry2->cluster != NULL);
+  if (cmp != 0)
+    return cmp;
+
+  /* Compare the clusters.  */
+  if (entry1->cluster != NULL)
     {
-      /* The entries are not within the same cluster, so we can't compare them
-         directly, we have to use the appropriate clustering level too.  */
-      if (! entry1->cluster)
-        /* ENTRY1 is at the 'base level', not in a cluster, so we have to
-           compare it's group number with that of the base cluster in which
-           ENTRY2 resides.  Note that if they're in the same group, the
-           clustered option always comes last.  */
-        return group_cmp (group1, hol_cluster_base (entry2->cluster)->group, 
-1);
-      else if (! entry2->cluster)
-        /* Likewise, but ENTRY2's not in a cluster.  */
-        return group_cmp (hol_cluster_base (entry1->cluster)->group, group2, 
1);
-      else
-        /* Both entries are in clusters, we can just compare the clusters.  */
-        return hol_cluster_cmp (entry1->cluster, entry2->cluster);
+      cmp = hol_cluster_cmp (entry1->cluster, entry2->cluster);
+      if (cmp != 0)
+        return cmp;
     }
-  else if (group1 == group2)
-    /* The entries are both in the same cluster and group, so compare them
-       alphabetically.  */
+
+  /* For entries in the same cluster, compare also the group numbers
+     within the cluster.  */
+  cmp = group_cmp (entry1->group, entry2->group);
+  if (cmp != 0)
+    return cmp;
+
+  /* The entries are both in the same group and the same cluster.  */
+
+  /* 'documentation' options always follow normal options (or documentation
+     options that *look* like normal options).  */
+  const char *long1 = hol_entry_first_long (entry1);
+  const char *long2 = hol_entry_first_long (entry2);
+  int doc1 =
+    (odoc (entry1->opt) ? long1 != NULL && canon_doc_option (&long1) : 0);
+  int doc2 =
+    (odoc (entry2->opt) ? long2 != NULL && canon_doc_option (&long2) : 0);
+  cmp = doc1 - doc2;
+  if (cmp != 0)
+    return cmp;
+
+  /* Compare the entries alphabetically.  */
+
+  /* First, compare the first character of the options.
+     Put entries without *any* valid options (such as options with
+     OPTION_HIDDEN set) first.  But as they're not displayed, it doesn't
+     matter where they are.  */
+  int short1 = hol_entry_first_short (entry1);
+  int short2 = hol_entry_first_short (entry2);
+  unsigned char first1 = short1 ? short1 : long1 != NULL ? *long1 : 0;
+  unsigned char first2 = short2 ? short2 : long2 != NULL ? *long2 : 0;
+  /* Compare ignoring case.  */
+  /* Use tolower, not _tolower, since the latter has undefined behaviour
+     for characters that are not uppercase letters.  */
+  cmp = tolower (first1) - tolower (first2);
+  if (cmp != 0)
+    return cmp;
+  /* When the options start with the same letter (ignoring case), lower-case
+     comes first.  */
+  cmp = first2 - first1;
+  if (cmp != 0)
+    return cmp;
+
+  /* The first character of the options agree.  */
+
+  /* Put entries with a short option before entries without a short option.  */
+  cmp = (short1 != 0) - (short2 != 0);
+  if (cmp != 0)
+    return cmp;
+
+  /* Compare entries without a short option by comparing the long option.  */
+  if (short1 == 0)
     {
-      int short1 = hol_entry_first_short (entry1);
-      int short2 = hol_entry_first_short (entry2);
-      int doc1 = odoc (entry1->opt);
-      int doc2 = odoc (entry2->opt);
-      const char *long1 = hol_entry_first_long (entry1);
-      const char *long2 = hol_entry_first_long (entry2);
-
-      if (doc1)
-        doc1 = long1 != NULL && canon_doc_option (&long1);
-      if (doc2)
-        doc2 = long2 != NULL && canon_doc_option (&long2);
-
-      if (doc1 != doc2)
-        /* 'documentation' options always follow normal options (or
-           documentation options that *look* like normal options).  */
-        return doc1 - doc2;
-      else if (!short1 && !short2 && long1 && long2)
-        /* Only long options.  */
-        return __strcasecmp (long1, long2);
-      else
-        /* Compare short/short, long/short, short/long, using the first
-           character of long options.  Entries without *any* valid
-           options (such as options with OPTION_HIDDEN set) will be put
-           first, but as they're not displayed, it doesn't matter where
-           they are.  */
+      cmp = (long1 != NULL) - (long2 != NULL);
+      if (cmp != 0)
+        return cmp;
+
+      if (long1 != NULL)
         {
-          unsigned char first1 = short1 ? short1 : long1 ? *long1 : 0;
-          unsigned char first2 = short2 ? short2 : long2 ? *long2 : 0;
-          /* Use tolower, not _tolower, since the latter has undefined
-             behaviour for characters that are not uppercase letters.  */
-          int lower_cmp = tolower (first1) - tolower (first2);
-          /* Compare ignoring case, except when the options are both the
-             same letter, in which case lower-case always comes first.  */
-          return lower_cmp ? lower_cmp : first2 - first1;
+          cmp = __strcasecmp (long1, long2);
+          if (cmp != 0)
+            return cmp;
         }
     }
-  else
-    /* Within the same cluster, but not the same group, so just compare
-       groups.  */
-    return group_cmp (group1, group2, 0);
+
+  /* We're out of comparison criteria.  At this point, if ENTRY1 != ENTRY2,
+     the order of these entries will be unpredictable.  */
+  return 0;
 }
 
 /* Variant of hol_entry_cmp with correct signature for qsort.  */

argp-debug.diff
Description: Text Data

argp-glibc.out
Description: Text document

argp-macos.out
Description: Text document