[PATCH 5/5] argp: Avoid undefined behaviour when invoking qsort().
Adhemerval Zanella
adhemerval.zanella@linaro.org
Tue Feb 2 14:45:05 GMT 2021
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;
> }
> -
> +
> /* 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. */
>
More information about the Libc-alpha
mailing list