2 * Normalize C declaration specifier lists.
3 * Copyright © 2011, 2021 Nick Bowler
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
24 #include "cdecl-internal.h"
27 * Partially order the declaration specifiers by assigning each specifier
28 * type an appropriate integer value. These values need not be unique for
29 * specifiers that never appear together.
31 * This implementation relies implicitly on the specific enumeration values.
32 * These values are expected to be stable as they are exposed library API.
34 static int order_spec(const struct cdecl_declspec *spec)
36 unsigned kind = cdecl_spec_kind(spec);
37 unsigned ret = spec->type;
39 /* General sequence: storage, function, qualifier, type */
42 ret |= CDECL_SPEC_FUNC;
45 /* Manually reorder some elements that are in the wrong place */
48 ret += 2; /* OK because "float int" is invalid. */
50 case CDECL_TYPE_SIGNED:
51 case CDECL_TYPE_UNSIGNED:
52 ret = CDECL_TYPE_VOID;
55 ret |= CDECL_SPEC_FUNC|CDECL_SPEC_QUAL;
61 static int compare_specs(const struct cdecl_declspec *a,
62 const struct cdecl_declspec *b)
64 return order_spec(a) - order_spec(b);
68 * Merge two sorted specifier lists. Each list must have at least one element.
70 static struct cdecl_declspec *
71 merge_specs(struct cdecl_declspec *l1, size_t n1,
72 struct cdecl_declspec *l2, size_t n2)
74 struct cdecl_declspec *top = l1, **p = ⊤
76 assert(n1 > 0 && n2 > 0);
78 for (size_t i = 0, j = 0; i < n1 && j < n2;) {
79 int ord = compare_specs(l1, l2);
80 struct cdecl_declspec *tmp;
105 * A simple merge sort. Set n to the number of elements in the list, or 0
106 * to have the sort function count them.
108 static struct cdecl_declspec *sort_specs(struct cdecl_declspec *l1, size_t n)
110 struct cdecl_declspec *l2, *c;
113 /* Find the midpoint of the list. */
115 for (i = 0, l2 = l1; i < (n+1)/2; i++)
118 for (i = 0, c = l2 = l1; c; i++, c = c->next) {
132 /* l1 always has the longer "half". */
133 l1 = sort_specs(l1, (n+1)/2);
134 l2 = sort_specs(l2, n/2);
136 return merge_specs(l1, (n+1)/2, l2, n/2);
140 * C allows declaration specifiers to appear in any order, and allows arbitrary
141 * repetition of some kinds of specifiers. Normalize the specifier lists by
142 * sorting the specifiers and removing repeated function specifiers and type
145 struct cdecl_declspec *cdecl__normalize_specs(struct cdecl_declspec *specs)
147 struct cdecl_declspec *c, *l;
152 specs = sort_specs(specs, 0);
154 for (c = specs, l = NULL; c; l = c, c = c->next) {
155 switch (cdecl_spec_kind(c)) {
156 case CDECL_SPEC_QUAL:
157 case CDECL_SPEC_FUNC:
158 if (l && l->type == c->type) {