From patchwork Thu Jan 7 01:06:20 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bruno Haible X-Patchwork-Id: 1423107 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=libc-alpha-bounces@sourceware.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=clisp.org Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=clisp.org header.i=@clisp.org header.a=rsa-sha256 header.s=strato-dkim-0002 header.b=DtZB+d90; dkim-atps=neutral Received: from sourceware.org (unknown [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4DB7PW4SbWz9sRR for ; Thu, 7 Jan 2021 12:07:27 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 08C953844072; Thu, 7 Jan 2021 01:07:16 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mo4-p01-ob.smtp.rzone.de (mo4-p01-ob.smtp.rzone.de [81.169.146.165]) by sourceware.org (Postfix) with ESMTPS id 85A513870857 for ; Thu, 7 Jan 2021 01:07:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 85A513870857 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=clisp.org Authentication-Results: sourceware.org; spf=none smtp.mailfrom=bruno@clisp.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; t=1609981631; s=strato-dkim-0002; d=clisp.org; h=References:In-Reply-To:Message-Id:Date:Subject:Cc:To:From:From: Subject:Sender; bh=MMFfIK6iRRJyl4rFu6mgUAXW+O+L83hk48S5/BiD6CY=; b=DtZB+d90IgOK7F6VrvdIW0Jv1nRJSSjv3I91kf0WCIW4HNtjcVIn2X44TGmRyGlgJP ADcAzVHQGda0KWegWk2YviE/1KRcKWj1/9OYSo/oakocyBiATvTDI4wB6BAJErvuOB1q 4HSKvxu7eBzkkGQNyHiKC5H++InzloPBBPTHRn2ZSPHRZEwcF9NcPmBo/BQCoQ5aI+Zl e/VYahZ4BJf0kULrWVT2D+OFJEF4e2t/cPtjxN8OuOHrqVH9siS53rlDx6CkKv842EQg fMBxI0R4zLVVyzrgytW0uYgooOM4q2bmhGlwToe+5jkw9P+8IZqQQ+65KnuPsyroO/uS 6kZA== X-RZG-AUTH: ":Ln4Re0+Ic/6oZXR1YgKryK8brlshOcZlIWs+iCP5vnk6shH+AHjwLuWOHqf3yZdW" X-RZG-CLASS-ID: mo00 Received: from omega.bruno.haible.de by smtp.strato.de (RZmta 47.12.1 DYNA|AUTH) with ESMTPSA id u0aa20x0717331v (using TLSv1.2 with cipher ECDHE-RSA-AES128-SHA256 (curve X9_62_prime256v1 with 256 ECDH bits, eq. 3072 bits RSA)) (Client did not present a certificate); Thu, 7 Jan 2021 02:07:03 +0100 (CET) From: Bruno Haible To: libc-alpha@sourceware.org, Paul Eggert Subject: [PATCH 5/5] argp: Avoid undefined behaviour when invoking qsort(). Date: Thu, 7 Jan 2021 02:06:20 +0100 Message-Id: <1609981580-17229-6-git-send-email-bruno@clisp.org> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1609981580-17229-1-git-send-email-bruno@clisp.org> References: <1609981580-17229-1-git-send-email-bruno@clisp.org> X-Spam-Status: No, score=-12.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_PASS, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Bruno Haible Errors-To: libc-alpha-bounces@sourceware.org Sender: "Libc-alpha" This fixes a Gnulib test-argp-2.sh test failure on macOS and FreeBSD. Reported by Jeffrey Walton in . * 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. Reviewed-by: Adhemerval Zanella --- 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. */