[PATCH 0/5] argp: Fix several cases of undefined behaviour

[PATCH 0/5] argp: Fix several cases of undefined behaviour

[Bruno Haible]

Here is a proposed patch series to merge changes in the argp-help.c file,
done in Gnulib, back to glibc.

The argp-help.c file is what determines the output of the --help option of
a program that uses the 'argp' facility
 <https://www.gnu.org/software/libc/manual/html_node/Argp.html>.

The purpose of these patches is to fix three different kinds of what ISO C
calls "undefined behaviour", and thus achieve the --help output on
different operating systems. Without the patches, the --help output was
different (and nonsensical) on macOS and FreeBSD.

I am not an expert in the argp facility, but I am pretty confident about
the changes as
  - they are limited to a single file, without affecting the other parts
    of the 'argp' facility,
  - I spent several days reading and understanding this file and the
    associated documentation,
  - the glibc tests of the 'argp' facility pass, without requiring changes.

Patch 1/5 is by Paul Eggert
 <https://lists.gnu.org/archive/html/bug-gnulib/2017-05/msg00176.html>
It fixes an alert from GCC's -fcheck-pointer-bounds instrumentation.

Patch 2/5 was originally by Eric Blake
 <https://lists.gnu.org/archive/html/bug-gnulib/2009-09/msg00287.html>.
It fixes an undefined behaviour: The code used the _tolower function
on arbitrary ASCII letters. But this function is documented, e.g. in
 <https://linux.die.net/man/3/_tolower>, to take only uppercase letter
as arguments.
Inside glibc it might not be undefined behaviour if glibc's _tolower
functions has more guarantees. But tolower() is not that much slower.
This part of glibc is not performance-critical: Producing the --help
output occurs at most once per program run, and there are rarely more
than 1000 command-line options for which the help output needs to be
produced.

Patch 3/5 fixes undefined behaviour caused by calling the functions
isspace(), isalpha(), isalnum(), isdigit() on values of type 'char',
not 'unsigned char'. See e.g. POSIX
 <https://pubs.opengroup.org/onlinepubs/9699919799/functions/isalnum_l.html>
This matters only on platforms for which 'char' is signed (e.g. not
on powerpc), and only for options that contain non-ASCII characters.
Admittedly, this is rare nowadays that ISO-8859-1 is no longer in wide
use. But it costs nothing to fix this: Fetching a byte from memory
and zero-extending it takes as many CPU instructions as fetching a byte
from memory and sign-extending it.

Patch 4/5 are cosmetic / readability changes that I felt most helpful
when understanding this code.
  - Add sectioning comments. Reading a 2000-lines file without
    structure is like reading a 200-pages novel with no chapter titles.
    The file has page breaks, but they don't carry any information,
    and some editors don't display page breaks.
  - Write NULL to designate a null pointer. It does help readability
    to write 0 for integers and NULL for pointers.
  - Fix wrong comments.
  - Move two functions so that they appear in proximity of related code,
    instead of interrupting the sequence of functions that deal with
    something completely different.

Patch 5/5 fixes undefined behaviour caused by calling the function
qsort() with a sort predicate that is not a total order. POSIX
 <https://pubs.opengroup.org/onlinepubs/9699919799/functions/qsort.html>
says:
  "When the same objects ... 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 some debugging before the qsort() call and printed out
the results of this comparison function
  1) as a matrix,
  2) as a list of violations of the total order rule.

For example, the output on the gnulib test suite example was:

hol_sort: entries = {
  [0] = [] [Main options]
  [1] = [test] []
  [2] = [] [Option Group 1]
  [3] = [verbose] [Simple option without arguments]
  [4] = [file] [Option with a mandatory argument]
  [5] = [hidden] [Hidden option]
  [6] = [] [Option Group 1.1]
  [7] = [cantiga] [create a cantiga]
  [8] = [sonet] [create a sonet]
  [9] = [] [Option Group 2]
  [10] = [option] [An option]
  [11] = [optional] [Option with an optional argument. ARG is one of the following:]
  [12] = [one] [one unit]
  [13] = [two] [two units]
  [14] = [many] [many units]
  [15] = [] [Option Group 2.1]
  [16] = [poem] [create a poem]
  [17] = [limerick] [create a limerick]
  [18] = [help] [give this help list]
  [19] = [usage] [give a short usage message]
  [20] = [program-name] [set the program name]
  [21] = [HANG] [hang for SECS seconds (default 3600)]
  [22] = [version] [print program version]
}
hol_sort: comparisons =
   . - - - - - - - - - - - - - - - - - - - - - -
   + . - - - - - - - - - - - - - - - - - - - - -
   + + . - - . . . . - - - - - - - - - - - - - -
   + + + . + + . . . - - - - - - - - - - - - - -
   + + + - . + . . . - - - - - - - - - - - - - -
   + + . - - . . . . - - - - - - - - - - - - - -
   + + . . . . . - - - - - - - - - - - - - - - -
   + + . . . . + . - - - - - - - - - - - - - - -
   + + . . . . + + . - - - - - - - - - - - - - -
   + + + + + + + + + . - - - - - . . . - - - - -
   + + + + + + + + + + . - - - - . . . - - - - -
   + + + + + + + + + + + . - - - . . . - - - - -
   + + + + + + + + + + + + . - + . . . - - - - -
   + + + + + + + + + + + + + . + . . . - - - - -
   + + + + + + + + + + + + - - . . . . - - - - -
   + + + + + + + + + . . . . . . . - - - - - - -
   + + + + + + + + + . . . . . . + . + - - - - -
   + + + + + + + + + . . . . . . + - . - - - - -
   + + + + + + + + + + + + + + + + + + . - + + -
   + + + + + + + + + + + + + + + + + + + . + + -
   + + + + + + + + + + + + + + + + + + - - . . -
   + + + + + + + + + + + + + + + + + + - - . . -
   + + + + + + + + + + + + + + + + + + + + + + .
hol_sort: transitivity violated for [2] [3] [6]
hol_sort: transitivity violated for [2] [3] [7]
...

"transitivity violated for [2] [3] [6]" means that
  compare([2], [3]) < 0
  compare([3], [6]) = 0
  compare([2], [6]) = 0
and similarly for the other violations.

More details in
 <https://lists.gnu.org/archive/html/bug-gnulib/2020-12/msg00088.html>.

So, I rewrote the comparison function 'hol_entry_cmp' in such a way that
  - it reflects the original programmer's intent (as best as can
    understand from the previous code and its comments),
  - it is a total order (this is guaranteed by defining it a lexicographic
    comparison function, based on several more elementary total orderings),
  - it passes the Gnulib test suite.
It then also passes the glibc test suite without further adjustments.


Bruno Haible (4):
  argp: Don't rely on undefined behaviour of _tolower().
  argp: Don't pass invalid arguments to isspace, isalnum, isalpha,
    isdigit.
  argp: Improve comments.
  argp: Avoid undefined behaviour when invoking qsort().

Paul Eggert (1):
  argp: fix pointer-subtraction bug

 argp/argp-help.c | 379 ++++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 246 insertions(+), 133 deletions(-)

-- 
2.7.4

[PATCH 1/5] argp: fix pointer-subtraction bug

[Bruno Haible]

From: Paul Eggert <eggert@cs.ucla.edu>

* argp/argp-help.c (hol_append): Don’t subtract pointers to
different arrays, as this can run afoul of -fcheck-pointer-bounds.
See the thread containing Bruno Haible’s report in:
http://lists.gnu.org/archive/html/bug-gnulib/2017-05/msg00171.html
---
 argp/argp-help.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/argp/argp-help.c b/argp/argp-help.c
index 15c5fd2..f417e12 100644
--- a/argp/argp-help.c
+++ b/argp/argp-help.c
@@ -867,7 +867,8 @@ hol_append (struct hol *hol, struct hol *more)
 
 	  /* Fix up the short options pointers from HOL.  */
 	  for (e = entries, left = hol->num_entries; left > 0; e++, left--)
-	    e->short_options += (short_options - hol->short_options);
+	    e->short_options
+	      = short_options + (e->short_options - hol->short_options);
 
 	  /* Now add the short options from MORE, fixing up its entries
 	     too.  */
-- 
2.7.4

[PATCH 2/5] argp: Don't rely on undefined behaviour of _tolower().

[Bruno Haible]

Patch by Eric Blake
<https://lists.gnu.org/archive/html/bug-gnulib/2009-09/msg00287.html>.

* argp/argp-help.c (hol_entry_cmp): Don't use _tolower on values that are
not upper-case.  Pass correct range to tolower.
---
 argp/argp-help.c | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

diff --git a/argp/argp-help.c b/argp/argp-help.c
index f417e12..5844d5b 100644
--- a/argp/argp-help.c
+++ b/argp/argp-help.c
@@ -780,13 +780,11 @@ hol_entry_cmp (const struct hol_entry *entry1,
 	   first, but as they're not displayed, it doesn't matter where
 	   they are.  */
 	{
-	  char first1 = short1 ? short1 : long1 ? *long1 : 0;
-	  char first2 = short2 ? short2 : long2 ? *long2 : 0;
-#ifdef _tolower
-	  int lower_cmp = _tolower (first1) - _tolower (first2);
-#else
+	  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);
-#endif
 	  /* 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;
-- 
2.7.4

[PATCH 3/5] argp: Don't pass invalid arguments to isspace, isalnum, isalpha, isdigit.

[Bruno Haible]

* lib/argp-help.c (SKIPWS): Cast character to 'unsigned char' before passing it
to isspace().
(fill_in_uparams): Likewise for isalpha(), isalnum(), isdigit().
(canon_doc_option): Likewise for isspace(), isalnum().
---
 argp/argp-help.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

diff --git a/argp/argp-help.c b/argp/argp-help.c
index 5844d5b..d686a23 100644
--- a/argp/argp-help.c
+++ b/argp/argp-help.c
@@ -166,7 +166,7 @@ fill_in_uparams (const struct argp_state *state)
 {
   const char *var = getenv ("ARGP_HELP_FMT");
 
-#define SKIPWS(p) do { while (isspace (*p)) p++; } while (0);
+#define SKIPWS(p) do { while (isspace ((unsigned char) *p)) p++; } while (0);
 
   if (var)
     /* Parse var. */
@@ -174,14 +174,14 @@ fill_in_uparams (const struct argp_state *state)
       {
 	SKIPWS (var);
 
-	if (isalpha (*var))
+	if (isalpha ((unsigned char) *var))
 	  {
 	    size_t var_len;
 	    const struct uparam_name *un;
 	    int unspec = 0, val = 0;
 	    const char *arg = var;
 
-	    while (isalnum (*arg) || *arg == '-' || *arg == '_')
+	    while (isalnum ((unsigned char) *arg) || *arg == '-' || *arg == '_')
 	      arg++;
 	    var_len = arg - var;
 
@@ -206,10 +206,10 @@ fill_in_uparams (const struct argp_state *state)
 		else
 		  val = 1;
 	      }
-	    else if (isdigit (*arg))
+	    else if (isdigit ((unsigned char) *arg))
 	      {
 		val = atoi (arg);
-		while (isdigit (*arg))
+		while (isdigit ((unsigned char) *arg))
 		  arg++;
 		SKIPWS (arg);
 	      }
@@ -713,12 +713,12 @@ canon_doc_option (const char **name)
 {
   int non_opt;
   /* Skip initial whitespace.  */
-  while (isspace (**name))
+  while (isspace ((unsigned char) **name))
     (*name)++;
   /* Decide whether this looks like an option (leading `-') or not.  */
   non_opt = (**name != '-');
   /* Skip until part of name used for sorting.  */
-  while (**name && !isalnum (**name))
+  while (**name && !isalnum ((unsigned char) **name))
     (*name)++;
   return non_opt;
 }
-- 
2.7.4

[PATCH 4/5] argp: Improve comments.

[Bruno Haible]

* argp/argp-help.c: Add sectioning comments. Write NULL to designate a
null pointer.
(struct hol_entry): Fix comment regarding sort order of group.
(hol_entry_short_iterate, hol_entry_long_iterate): Add comment.
(until_short, canon_doc_option, hol_entry_qcmp): Improve comment.
(hol_cluster_is_child, argp_hol): Move functions.
---
 argp/argp-help.c | 108 +++++++++++++++++++++++++++++++++----------------------
 1 file changed, 65 insertions(+), 43 deletions(-)

diff --git a/argp/argp-help.c b/argp/argp-help.c
index d686a23..637abca 100644
--- a/argp/argp-help.c
+++ b/argp/argp-help.c
@@ -87,6 +87,8 @@ char *strerror (int errnum);
 # define SIZE_MAX ((size_t) -1)
 #endif
 \f
+/* ========================================================================== */
+
 /* User-selectable (using an environment variable) formatting parameters.
 
    These may be specified in an environment variable called `ARGP_HELP_FMT',
@@ -253,6 +255,8 @@ fill_in_uparams (const struct argp_state *state)
       }
 }
 \f
+/* ========================================================================== */
+
 /* Returns true if OPT hasn't been marked invisible.  Visibility only affects
    whether OPT is displayed or used in sorting, not option shadowing.  */
 #define ovisible(opt) (! ((opt)->flags & OPTION_HIDDEN))
@@ -345,6 +349,9 @@ find_char (char ch, char *beg, char *end)
   return 0;
 }
 \f
+/* -------------------------------------------------------------------------- */
+/* Data structure: HOL = Help Option List                                     */
+
 struct hol_cluster;		/* fwd decl */
 
 struct hol_entry
@@ -363,11 +370,11 @@ struct hol_entry
   char *short_options;
 
   /* Entries are sorted by their group first, in the order:
-       1, 2, ..., n, 0, -m, ..., -2, -1
+       0, 1, 2, ..., n, -m, ..., -2, -1
      and then alphabetically within each group.  The default is 0.  */
   int group;
 
-  /* The cluster of options this entry belongs to, or 0 if none.  */
+  /* The cluster of options this entry belongs to, or NULL if none.  */
   struct hol_cluster *cluster;
 
   /* The argp from which this option came.  */
@@ -389,7 +396,7 @@ struct hol_cluster
      same depth (clusters always follow options in the same group).  */
   int group;
 
-  /* The cluster to which this cluster belongs, or 0 if it's at the base
+  /* The cluster to which this cluster belongs, or NULL if it's at the base
      level.  */
   struct hol_cluster *parent;
 
@@ -422,7 +429,7 @@ struct hol
 };
 \f
 /* Create a struct hol from the options in ARGP.  CLUSTER is the
-   hol_cluster in which these entries occur, or 0, if at the root.  */
+   hol_cluster in which these entries occur, or NULL if at the root.  */
 static struct hol *
 make_hol (const struct argp *argp, struct hol_cluster *cluster)
 {
@@ -540,6 +547,9 @@ hol_free (struct hol *hol)
   free (hol);
 }
 \f
+/* Iterate across the short_options of the given ENTRY.  Call FUNC for each.
+   Stop when such a call returns a non-zero value, and return this value.
+   If all FUNC invocations returned 0, return 0.  */
 static int
 hol_entry_short_iterate (const struct hol_entry *entry,
 			 int (*func)(const struct argp_option *opt,
@@ -565,6 +575,9 @@ hol_entry_short_iterate (const struct hol_entry *entry,
   return val;
 }
 
+/* Iterate across the long options of the given ENTRY.  Call FUNC for each.
+   Stop when such a call returns a non-zero value, and return this value.
+   If all FUNC invocations returned 0, return 0.  */
 static inline int
 __attribute__ ((always_inline))
 hol_entry_long_iterate (const struct hol_entry *entry,
@@ -589,7 +602,7 @@ hol_entry_long_iterate (const struct hol_entry *entry,
   return val;
 }
 \f
-/* Iterator that returns true for the first short option.  */
+/* A filter that returns true for the first short option of a given ENTRY.  */
 static inline int
 until_short (const struct argp_option *opt, const struct argp_option *real,
 	     const char *domain, void *cookie)
@@ -605,7 +618,7 @@ hol_entry_first_short (const struct hol_entry *entry)
 				  entry->argp->argp_domain, 0);
 }
 
-/* Returns the first valid long option in ENTRY, or 0 if there is none.  */
+/* Returns the first valid long option in ENTRY, or NULL if there is none.  */
 static const char *
 hol_entry_first_long (const struct hol_entry *entry)
 {
@@ -617,7 +630,7 @@ hol_entry_first_long (const struct hol_entry *entry)
   return 0;
 }
 
-/* Returns the entry in HOL with the long option name NAME, or 0 if there is
+/* Returns the entry in HOL with the long option name NAME, or NULL if there is
    none.  */
 static struct hol_entry *
 hol_find_entry (struct hol *hol, const char *name)
@@ -652,6 +665,9 @@ hol_set_group (struct hol *hol, const char *name, int group)
     entry->group = group;
 }
 \f
+/* -------------------------------------------------------------------------- */
+/* Sorting the entries in a HOL.                                              */
+
 /* Order by group:  0, 1, 2, ..., n, -m, ..., -2, -1.
    EQ is what to return if GROUP1 and GROUP2 are the same.  */
 static int
@@ -694,18 +710,8 @@ hol_cluster_base (struct hol_cluster *cl)
     cl = cl->parent;
   return cl;
 }
-
-/* Return true if CL1 is a child of CL2.  */
-static int
-hol_cluster_is_child (const struct hol_cluster *cl1,
-		      const struct hol_cluster *cl2)
-{
-  while (cl1 && cl1 != cl2)
-    cl1 = cl1->parent;
-  return cl1 == cl2;
-}
 \f
-/* Given the name of a OPTION_DOC option, modifies NAME to start at the tail
+/* Given the name of an OPTION_DOC option, modifies *NAME to start at the tail
    that should be used for comparisons, and returns true iff it should be
    treated as a non-option.  */
 static int
@@ -796,7 +802,7 @@ hol_entry_cmp (const struct hol_entry *entry1,
     return group_cmp (group1, group2, 0);
 }
 
-/* Version of hol_entry_cmp with correct signature for qsort.  */
+/* Variant of hol_entry_cmp with correct signature for qsort.  */
 static int
 hol_entry_qcmp (const void *entry1_v, const void *entry2_v)
 {
@@ -814,6 +820,9 @@ hol_sort (struct hol *hol)
 	   hol_entry_qcmp);
 }
 \f
+/* -------------------------------------------------------------------------- */
+/* Constructing the HOL.                                                      */
+
 /* Append MORE to HOL, destroying MORE in the process.  Options in HOL shadow
    any in MORE with the same name.  */
 static void
@@ -909,6 +918,32 @@ hol_append (struct hol *hol, struct hol *more)
   hol_free (more);
 }
 \f
+/* Make a HOL containing all levels of options in ARGP.  CLUSTER is the
+   cluster in which ARGP's entries should be clustered, or 0.  */
+static struct hol *
+argp_hol (const struct argp *argp, struct hol_cluster *cluster)
+{
+  const struct argp_child *child = argp->children;
+  struct hol *hol = make_hol (argp, cluster);
+  if (child)
+    while (child->argp)
+      {
+	struct hol_cluster *child_cluster =
+	  ((child->group || child->header)
+	   /* Put CHILD->argp within its own cluster.  */
+	   ? hol_add_cluster (hol, child->group, child->header,
+			      child - argp->children, cluster, argp)
+	   /* Just merge it into the parent's cluster.  */
+	   : cluster);
+	hol_append (hol, argp_hol (child->argp, child_cluster)) ;
+	child++;
+      }
+  return hol;
+}
+\f
+/* -------------------------------------------------------------------------- */
+/* Printing the HOL.                                                          */
+
 /* Inserts enough spaces to make sure STREAM is at column COL.  */
 static void
 indent_to (argp_fmtstream_t stream, unsigned col)
@@ -953,7 +988,7 @@ arg (const struct argp_option *real, const char *req_fmt, const char *opt_fmt,
 /* State used during the execution of hol_help.  */
 struct hol_help_state
 {
-  /* PREV_ENTRY should contain the previous entry printed, or 0.  */
+  /* PREV_ENTRY should contain the previous entry printed, or NULL.  */
   struct hol_entry *prev_entry;
 
   /* If an entry is in a different group from the previous one, and SEP_GROUPS
@@ -1031,6 +1066,16 @@ print_header (const char *str, const struct argp *argp,
     free ((char *) fstr);
 }
 
+/* Return true if CL1 is a child of CL2.  */
+static int
+hol_cluster_is_child (const struct hol_cluster *cl1,
+		      const struct hol_cluster *cl2)
+{
+  while (cl1 && cl1 != cl2)
+    cl1 = cl1->parent;
+  return cl1 == cl2;
+}
+
 /* Inserts a comma if this isn't the first item on the line, and then makes
    sure we're at least to column COL.  If this *is* the first item on a line,
    prints any pending whitespace/headers that should precede this line. Also
@@ -1344,29 +1389,6 @@ hol_usage (struct hol *hol, argp_fmtstream_t stream)
     }
 }
 \f
-/* Make a HOL containing all levels of options in ARGP.  CLUSTER is the
-   cluster in which ARGP's entries should be clustered, or 0.  */
-static struct hol *
-argp_hol (const struct argp *argp, struct hol_cluster *cluster)
-{
-  const struct argp_child *child = argp->children;
-  struct hol *hol = make_hol (argp, cluster);
-  if (child)
-    while (child->argp)
-      {
-	struct hol_cluster *child_cluster =
-	  ((child->group || child->header)
-	   /* Put CHILD->argp within its own cluster.  */
-	   ? hol_add_cluster (hol, child->group, child->header,
-			      child - argp->children, cluster, argp)
-	   /* Just merge it into the parent's cluster.  */
-	   : cluster);
-	hol_append (hol, argp_hol (child->argp, child_cluster)) ;
-	child++;
-      }
-  return hol;
-}
-\f
 /* Calculate how many different levels with alternative args strings exist in
    ARGP.  */
 static size_t
-- 
2.7.4

[PATCH 5/5] argp: Avoid undefined behaviour when invoking qsort().

[Bruno Haible]

This fixes a Gnulib 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>.

* argp/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.
---
 argp/argp-help.c | 254 +++++++++++++++++++++++++++++++++++++------------------
 1 file changed, 173 insertions(+), 81 deletions(-)

diff --git a/argp/argp-help.c b/argp/argp-help.c
index 637abca..02afba2 100644
--- a/argp/argp-help.c
+++ b/argp/argp-help.c
@@ -668,37 +668,90 @@ hol_set_group (struct hol *hol, const char *name, int group)
 /* -------------------------------------------------------------------------- */
 /* Sorting the entries in a HOL.                                              */
 
-/* Order by group:  0, 1, 2, ..., n, -m, ..., -2, -1.
-   EQ is what to return if GROUP1 and GROUP2 are the same.  */
+/* 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
@@ -710,7 +763,7 @@ hol_cluster_base (struct hol_cluster *cl)
     cl = cl->parent;
   return cl;
 }
-\f
+
 /* Given the name of an OPTION_DOC option, modifies *NAME to start at the tail
    that should be used for comparisons, and returns true iff it should be
    treated as a non-option.  */
@@ -721,7 +774,7 @@ canon_doc_option (const char **name)
   /* Skip initial whitespace.  */
   while (isspace ((unsigned char) **name))
     (*name)++;
-  /* Decide whether this looks like an option (leading `-') or not.  */
+  /* Decide whether this looks like an option (leading '-') or not.  */
   non_opt = (**name != '-');
   /* Skip until part of name used for sorting.  */
   while (**name && !isalnum ((unsigned char) **name))
@@ -729,77 +782,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.  */
-- 
2.7.4

[PATCH 1/5] argp: fix pointer-subtraction bug

[Bruno Haible]

[-- Attachment #1: Type: text/plain, Size: 98 bytes --]

This patch is attached. (git send-email did not send it because it is
authored by Paul, not me.)


[-- Attachment #2: 0001-argp-fix-pointer-subtraction-bug.patch --]
[-- Type: text/x-patch, Size: 1223 bytes --]

From 5a404daee6857506202b5a5eed331aba760b2308 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Thu, 7 Jan 2021 00:51:33 +0100
Subject: [PATCH 1/5] argp: fix pointer-subtraction bug
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* argp/argp-help.c (hol_append): Don’t subtract pointers to
different arrays, as this can run afoul of -fcheck-pointer-bounds.
See the thread containing Bruno Haible’s report in:
http://lists.gnu.org/archive/html/bug-gnulib/2017-05/msg00171.html
---
 argp/argp-help.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/argp/argp-help.c b/argp/argp-help.c
index 15c5fd2..f417e12 100644
--- a/argp/argp-help.c
+++ b/argp/argp-help.c
@@ -867,7 +867,8 @@ hol_append (struct hol *hol, struct hol *more)
 
 	  /* Fix up the short options pointers from HOL.  */
 	  for (e = entries, left = hol->num_entries; left > 0; e++, left--)
-	    e->short_options += (short_options - hol->short_options);
+	    e->short_options
+	      = short_options + (e->short_options - hol->short_options);
 
 	  /* Now add the short options from MORE, fixing up its entries
 	     too.  */
-- 
2.7.4

Re: [PATCH 1/5] argp: fix pointer-subtraction bug

[Adhemerval Zanella]

On 06/01/2021 22:06, Bruno Haible wrote:
> From: Paul Eggert <eggert@cs.ucla.edu>
> 
> * argp/argp-help.c (hol_append): Don’t subtract pointers to
> different arrays, as this can run afoul of -fcheck-pointer-bounds.
> See the thread containing Bruno Haible’s report in:
> http://lists.gnu.org/archive/html/bug-gnulib/2017-05/msg00171.html

LGTM, thanks.

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

> ---
>  argp/argp-help.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/argp/argp-help.c b/argp/argp-help.c
> index 15c5fd2..f417e12 100644
> --- a/argp/argp-help.c
> +++ b/argp/argp-help.c
> @@ -867,7 +867,8 @@ hol_append (struct hol *hol, struct hol *more)
>  
>  	  /* Fix up the short options pointers from HOL.  */
>  	  for (e = entries, left = hol->num_entries; left > 0; e++, left--)
> -	    e->short_options += (short_options - hol->short_options);
> +	    e->short_options
> +	      = short_options + (e->short_options - hol->short_options);
>  
>  	  /* Now add the short options from MORE, fixing up its entries
>  	     too.  */
> 

Re: [PATCH 2/5] argp: Don't rely on undefined behaviour of _tolower().

[Adhemerval Zanella]

On 06/01/2021 22:06, Bruno Haible wrote:
> Patch by Eric Blake
> <https://lists.gnu.org/archive/html/bug-gnulib/2009-09/msg00287.html>.
> 
> * argp/argp-help.c (hol_entry_cmp): Don't use _tolower on values that are
> not upper-case.  Pass correct range to tolower.

LGTM, thanks.

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

> ---
>  argp/argp-help.c | 10 ++++------
>  1 file changed, 4 insertions(+), 6 deletions(-)
> 
> diff --git a/argp/argp-help.c b/argp/argp-help.c
> index f417e12..5844d5b 100644
> --- a/argp/argp-help.c
> +++ b/argp/argp-help.c
> @@ -780,13 +780,11 @@ hol_entry_cmp (const struct hol_entry *entry1,
>  	   first, but as they're not displayed, it doesn't matter where
>  	   they are.  */
>  	{
> -	  char first1 = short1 ? short1 : long1 ? *long1 : 0;
> -	  char first2 = short2 ? short2 : long2 ? *long2 : 0;
> -#ifdef _tolower
> -	  int lower_cmp = _tolower (first1) - _tolower (first2);
> -#else
> +	  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);
> -#endif
>  	  /* 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;
> 

Re: [PATCH 3/5] argp: Don't pass invalid arguments to isspace, isalnum, isalpha, isdigit.

[Adhemerval Zanella]

On 06/01/2021 22:06, Bruno Haible wrote:
> * lib/argp-help.c (SKIPWS): Cast character to 'unsigned char' before passing it
> to isspace().
> (fill_in_uparams): Likewise for isalpha(), isalnum(), isdigit().
> (canon_doc_option): Likewise for isspace(), isalnum().

LGTM, thanks.

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

> ---
>  argp/argp-help.c | 14 +++++++-------
>  1 file changed, 7 insertions(+), 7 deletions(-)
> 
> diff --git a/argp/argp-help.c b/argp/argp-help.c
> index 5844d5b..d686a23 100644
> --- a/argp/argp-help.c
> +++ b/argp/argp-help.c
> @@ -166,7 +166,7 @@ fill_in_uparams (const struct argp_state *state)
>  {
>    const char *var = getenv ("ARGP_HELP_FMT");
>  
> -#define SKIPWS(p) do { while (isspace (*p)) p++; } while (0);
> +#define SKIPWS(p) do { while (isspace ((unsigned char) *p)) p++; } while (0);
>  
>    if (var)
>      /* Parse var. */
> @@ -174,14 +174,14 @@ fill_in_uparams (const struct argp_state *state)
>        {
>  	SKIPWS (var);
>  
> -	if (isalpha (*var))
> +	if (isalpha ((unsigned char) *var))
>  	  {
>  	    size_t var_len;
>  	    const struct uparam_name *un;
>  	    int unspec = 0, val = 0;
>  	    const char *arg = var;
>  
> -	    while (isalnum (*arg) || *arg == '-' || *arg == '_')
> +	    while (isalnum ((unsigned char) *arg) || *arg == '-' || *arg == '_')
>  	      arg++;
>  	    var_len = arg - var;
>  
> @@ -206,10 +206,10 @@ fill_in_uparams (const struct argp_state *state)
>  		else
>  		  val = 1;
>  	      }
> -	    else if (isdigit (*arg))
> +	    else if (isdigit ((unsigned char) *arg))
>  	      {
>  		val = atoi (arg);
> -		while (isdigit (*arg))
> +		while (isdigit ((unsigned char) *arg))
>  		  arg++;
>  		SKIPWS (arg);
>  	      }
> @@ -713,12 +713,12 @@ canon_doc_option (const char **name)
>  {
>    int non_opt;
>    /* Skip initial whitespace.  */
> -  while (isspace (**name))
> +  while (isspace ((unsigned char) **name))
>      (*name)++;
>    /* Decide whether this looks like an option (leading `-') or not.  */
>    non_opt = (**name != '-');
>    /* Skip until part of name used for sorting.  */
> -  while (**name && !isalnum (**name))
> +  while (**name && !isalnum ((unsigned char) **name))
>      (*name)++;
>    return non_opt;
>  }
> 

Re: [PATCH 4/5] argp: Improve comments.

[Adhemerval Zanella]

On 06/01/2021 22:06, Bruno Haible wrote:
> * argp/argp-help.c: Add sectioning comments. Write NULL to designate a
> null pointer.
> (struct hol_entry): Fix comment regarding sort order of group.
> (hol_entry_short_iterate, hol_entry_long_iterate): Add comment.
> (until_short, canon_doc_option, hol_entry_qcmp): Improve comment.
> (hol_cluster_is_child, argp_hol): Move functions.

LGTM, thanks.

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

> ---
>  argp/argp-help.c | 108 +++++++++++++++++++++++++++++++++----------------------
>  1 file changed, 65 insertions(+), 43 deletions(-)
> 
> diff --git a/argp/argp-help.c b/argp/argp-help.c
> index d686a23..637abca 100644
> --- a/argp/argp-help.c
> +++ b/argp/argp-help.c
> @@ -87,6 +87,8 @@ char *strerror (int errnum);
>  # define SIZE_MAX ((size_t) -1)
>  #endif
>  \f
> +/* ========================================================================== */
> +
>  /* User-selectable (using an environment variable) formatting parameters.
>  
>     These may be specified in an environment variable called `ARGP_HELP_FMT',
> @@ -253,6 +255,8 @@ fill_in_uparams (const struct argp_state *state)
>        }
>  }
>  \f
> +/* ========================================================================== */
> +
>  /* Returns true if OPT hasn't been marked invisible.  Visibility only affects
>     whether OPT is displayed or used in sorting, not option shadowing.  */
>  #define ovisible(opt) (! ((opt)->flags & OPTION_HIDDEN))
> @@ -345,6 +349,9 @@ find_char (char ch, char *beg, char *end)
>    return 0;
>  }
>  \f
> +/* -------------------------------------------------------------------------- */
> +/* Data structure: HOL = Help Option List                                     */
> +
>  struct hol_cluster;		/* fwd decl */
>  
>  struct hol_entry
> @@ -363,11 +370,11 @@ struct hol_entry
>    char *short_options;
>  
>    /* Entries are sorted by their group first, in the order:
> -       1, 2, ..., n, 0, -m, ..., -2, -1
> +       0, 1, 2, ..., n, -m, ..., -2, -1
>       and then alphabetically within each group.  The default is 0.  */
>    int group;
>  
> -  /* The cluster of options this entry belongs to, or 0 if none.  */
> +  /* The cluster of options this entry belongs to, or NULL if none.  */
>    struct hol_cluster *cluster;
>  
>    /* The argp from which this option came.  */
> @@ -389,7 +396,7 @@ struct hol_cluster
>       same depth (clusters always follow options in the same group).  */
>    int group;
>  
> -  /* The cluster to which this cluster belongs, or 0 if it's at the base
> +  /* The cluster to which this cluster belongs, or NULL if it's at the base
>       level.  */
>    struct hol_cluster *parent;
>  
> @@ -422,7 +429,7 @@ struct hol
>  };
>  \f
>  /* Create a struct hol from the options in ARGP.  CLUSTER is the
> -   hol_cluster in which these entries occur, or 0, if at the root.  */
> +   hol_cluster in which these entries occur, or NULL if at the root.  */
>  static struct hol *
>  make_hol (const struct argp *argp, struct hol_cluster *cluster)
>  {
> @@ -540,6 +547,9 @@ hol_free (struct hol *hol)
>    free (hol);
>  }
>  \f
> +/* Iterate across the short_options of the given ENTRY.  Call FUNC for each.
> +   Stop when such a call returns a non-zero value, and return this value.
> +   If all FUNC invocations returned 0, return 0.  */
>  static int
>  hol_entry_short_iterate (const struct hol_entry *entry,
>  			 int (*func)(const struct argp_option *opt,
> @@ -565,6 +575,9 @@ hol_entry_short_iterate (const struct hol_entry *entry,
>    return val;
>  }
>  
> +/* Iterate across the long options of the given ENTRY.  Call FUNC for each.
> +   Stop when such a call returns a non-zero value, and return this value.
> +   If all FUNC invocations returned 0, return 0.  */
>  static inline int
>  __attribute__ ((always_inline))
>  hol_entry_long_iterate (const struct hol_entry *entry,
> @@ -589,7 +602,7 @@ hol_entry_long_iterate (const struct hol_entry *entry,
>    return val;
>  }
>  \f
> -/* Iterator that returns true for the first short option.  */
> +/* A filter that returns true for the first short option of a given ENTRY.  */
>  static inline int
>  until_short (const struct argp_option *opt, const struct argp_option *real,
>  	     const char *domain, void *cookie)
> @@ -605,7 +618,7 @@ hol_entry_first_short (const struct hol_entry *entry)
>  				  entry->argp->argp_domain, 0);
>  }
>  
> -/* Returns the first valid long option in ENTRY, or 0 if there is none.  */
> +/* Returns the first valid long option in ENTRY, or NULL if there is none.  */
>  static const char *
>  hol_entry_first_long (const struct hol_entry *entry)
>  {
> @@ -617,7 +630,7 @@ hol_entry_first_long (const struct hol_entry *entry)
>    return 0;
>  }
>  
> -/* Returns the entry in HOL with the long option name NAME, or 0 if there is
> +/* Returns the entry in HOL with the long option name NAME, or NULL if there is
>     none.  */
>  static struct hol_entry *
>  hol_find_entry (struct hol *hol, const char *name)
> @@ -652,6 +665,9 @@ hol_set_group (struct hol *hol, const char *name, int group)
>      entry->group = group;
>  }
>  \f
> +/* -------------------------------------------------------------------------- */
> +/* Sorting the entries in a HOL.                                              */
> +
>  /* Order by group:  0, 1, 2, ..., n, -m, ..., -2, -1.
>     EQ is what to return if GROUP1 and GROUP2 are the same.  */
>  static int
> @@ -694,18 +710,8 @@ hol_cluster_base (struct hol_cluster *cl)
>      cl = cl->parent;
>    return cl;
>  }
> -
> -/* Return true if CL1 is a child of CL2.  */
> -static int
> -hol_cluster_is_child (const struct hol_cluster *cl1,
> -		      const struct hol_cluster *cl2)
> -{
> -  while (cl1 && cl1 != cl2)
> -    cl1 = cl1->parent;
> -  return cl1 == cl2;
> -}
>  \f
> -/* Given the name of a OPTION_DOC option, modifies NAME to start at the tail
> +/* Given the name of an OPTION_DOC option, modifies *NAME to start at the tail
>     that should be used for comparisons, and returns true iff it should be
>     treated as a non-option.  */
>  static int
> @@ -796,7 +802,7 @@ hol_entry_cmp (const struct hol_entry *entry1,
>      return group_cmp (group1, group2, 0);
>  }
>  
> -/* Version of hol_entry_cmp with correct signature for qsort.  */
> +/* Variant of hol_entry_cmp with correct signature for qsort.  */
>  static int
>  hol_entry_qcmp (const void *entry1_v, const void *entry2_v)
>  {
> @@ -814,6 +820,9 @@ hol_sort (struct hol *hol)
>  	   hol_entry_qcmp);
>  }
>  \f
> +/* -------------------------------------------------------------------------- */
> +/* Constructing the HOL.                                                      */
> +
>  /* Append MORE to HOL, destroying MORE in the process.  Options in HOL shadow
>     any in MORE with the same name.  */
>  static void
> @@ -909,6 +918,32 @@ hol_append (struct hol *hol, struct hol *more)
>    hol_free (more);
>  }
>  \f
> +/* Make a HOL containing all levels of options in ARGP.  CLUSTER is the
> +   cluster in which ARGP's entries should be clustered, or 0.  */
> +static struct hol *
> +argp_hol (const struct argp *argp, struct hol_cluster *cluster)
> +{
> +  const struct argp_child *child = argp->children;
> +  struct hol *hol = make_hol (argp, cluster);
> +  if (child)
> +    while (child->argp)
> +      {
> +	struct hol_cluster *child_cluster =
> +	  ((child->group || child->header)
> +	   /* Put CHILD->argp within its own cluster.  */
> +	   ? hol_add_cluster (hol, child->group, child->header,
> +			      child - argp->children, cluster, argp)
> +	   /* Just merge it into the parent's cluster.  */
> +	   : cluster);
> +	hol_append (hol, argp_hol (child->argp, child_cluster)) ;
> +	child++;
> +      }
> +  return hol;
> +}
> +\f
> +/* -------------------------------------------------------------------------- */
> +/* Printing the HOL.                                                          */
> +
>  /* Inserts enough spaces to make sure STREAM is at column COL.  */
>  static void
>  indent_to (argp_fmtstream_t stream, unsigned col)
> @@ -953,7 +988,7 @@ arg (const struct argp_option *real, const char *req_fmt, const char *opt_fmt,
>  /* State used during the execution of hol_help.  */
>  struct hol_help_state
>  {
> -  /* PREV_ENTRY should contain the previous entry printed, or 0.  */
> +  /* PREV_ENTRY should contain the previous entry printed, or NULL.  */
>    struct hol_entry *prev_entry;
>  
>    /* If an entry is in a different group from the previous one, and SEP_GROUPS
> @@ -1031,6 +1066,16 @@ print_header (const char *str, const struct argp *argp,
>      free ((char *) fstr);
>  }
>  
> +/* Return true if CL1 is a child of CL2.  */
> +static int
> +hol_cluster_is_child (const struct hol_cluster *cl1,
> +		      const struct hol_cluster *cl2)
> +{
> +  while (cl1 && cl1 != cl2)
> +    cl1 = cl1->parent;
> +  return cl1 == cl2;
> +}
> +
>  /* Inserts a comma if this isn't the first item on the line, and then makes
>     sure we're at least to column COL.  If this *is* the first item on a line,
>     prints any pending whitespace/headers that should precede this line. Also
> @@ -1344,29 +1389,6 @@ hol_usage (struct hol *hol, argp_fmtstream_t stream)
>      }
>  }
>  \f
> -/* Make a HOL containing all levels of options in ARGP.  CLUSTER is the
> -   cluster in which ARGP's entries should be clustered, or 0.  */
> -static struct hol *
> -argp_hol (const struct argp *argp, struct hol_cluster *cluster)
> -{
> -  const struct argp_child *child = argp->children;
> -  struct hol *hol = make_hol (argp, cluster);
> -  if (child)
> -    while (child->argp)
> -      {
> -	struct hol_cluster *child_cluster =
> -	  ((child->group || child->header)
> -	   /* Put CHILD->argp within its own cluster.  */
> -	   ? hol_add_cluster (hol, child->group, child->header,
> -			      child - argp->children, cluster, argp)
> -	   /* Just merge it into the parent's cluster.  */
> -	   : cluster);
> -	hol_append (hol, argp_hol (child->argp, child_cluster)) ;
> -	child++;
> -      }
> -  return hol;
> -}
> -\f
>  /* Calculate how many different levels with alternative args strings exist in
>     ARGP.  */
>  static size_t
> 

Re: [PATCH 5/5] argp: Avoid undefined behaviour when invoking qsort().

[Adhemerval Zanella]

On 06/01/2021 22:06, Bruno Haible wrote:
> This fixes a Gnulib 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>.
> 
> * argp/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.

LGTM, any chance to add a regression tests similar to the one that triggerd
the failure on macOS/FreeBSD?

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

> ---
>  argp/argp-help.c | 254 +++++++++++++++++++++++++++++++++++++------------------
>  1 file changed, 173 insertions(+), 81 deletions(-)
> 
> diff --git a/argp/argp-help.c b/argp/argp-help.c
> index 637abca..02afba2 100644
> --- a/argp/argp-help.c
> +++ b/argp/argp-help.c
> @@ -668,37 +668,90 @@ hol_set_group (struct hol *hol, const char *name, int group)
>  /* -------------------------------------------------------------------------- */
>  /* Sorting the entries in a HOL.                                              */
>  
> -/* Order by group:  0, 1, 2, ..., n, -m, ..., -2, -1.
> -   EQ is what to return if GROUP1 and GROUP2 are the same.  */
> +/* 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
> @@ -710,7 +763,7 @@ hol_cluster_base (struct hol_cluster *cl)
>      cl = cl->parent;
>    return cl;
>  }
> -\f
> +
>  /* Given the name of an OPTION_DOC option, modifies *NAME to start at the tail
>     that should be used for comparisons, and returns true iff it should be
>     treated as a non-option.  */
> @@ -721,7 +774,7 @@ canon_doc_option (const char **name)
>    /* Skip initial whitespace.  */
>    while (isspace ((unsigned char) **name))
>      (*name)++;
> -  /* Decide whether this looks like an option (leading `-') or not.  */
> +  /* Decide whether this looks like an option (leading '-') or not.  */
>    non_opt = (**name != '-');
>    /* Skip until part of name used for sorting.  */
>    while (**name && !isalnum ((unsigned char) **name))
> @@ -729,77 +782,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.  */
> 

Re: [PATCH 0/5] argp: Fix several cases of undefined behaviour

[Adhemerval Zanella]

On 06/01/2021 22:06, Bruno Haible wrote:
> Here is a proposed patch series to merge changes in the argp-help.c file,
> done in Gnulib, back to glibc.

Thanks for working on this, I have push it upstream. Do you plan to sync
back the rest of argp code? I noticed there is extra changes for argp-help,
but the rest is mainly code style, comments, and gnulib specific fixes.