/*
* Normalize C declaration specifier lists.
- * Copyright © 2011, 2021 Nick Bowler
+ * Copyright © 2011, 2021, 2023 Nick Bowler
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
#include "cdecl-internal.h"
/*
- * Totally order the declaration specifier types by defining an injection into
- * the natural numbers.
+ * Partially order the declaration specifiers by assigning each specifier
+ * type an appropriate integer value. These values need not be unique for
+ * specifiers that never appear together.
+ *
+ * This implementation relies implicitly on the specific enumeration values.
+ * These values are expected to be stable as they are exposed library API.
*/
-static unsigned order_spec(struct cdecl_declspec *spec)
+static int order_spec(const struct cdecl_declspec *spec)
{
- switch (spec->type) {
-# include "ordspecs.h"
- default:
- assert(0);
+ unsigned kind = cdecl_spec_kind(spec);
+ unsigned ret = spec->type;
+
+ /* General sequence: storage, function, qualifier, type */
+ switch (kind) {
+ case CDECL_SPEC_QUAL:
+ ret |= CDECL_SPEC_FUNC;
+ break;
+ case CDECL_SPEC_TYPE:
+ /* Manually reorder some elements that are in the wrong place */
+ switch (ret) {
+ case CDECL_TYPE_INT:
+ ret += 2; /* OK because "float int" is invalid. */
+ break;
+ case CDECL_TYPE_SIGNED:
+ case CDECL_TYPE_UNSIGNED:
+ ret = CDECL_TYPE_VOID;
+ break;
+ }
+ ret |= CDECL_SPEC_FUNC|CDECL_SPEC_QUAL;
}
+
+ return ret;
}
-static int compare_specs(struct cdecl_declspec *a, struct cdecl_declspec *b)
+static int
+compare_specs(const struct cdecl_declspec *a, const struct cdecl_declspec *b)
{
return order_spec(a) - order_spec(b);
}
-/*
- * Merge two sorted specifier lists. Each list must have at least one element.
- */
+/* Merge two sorted specifier lists, and return the head of the sorted list. */
static struct cdecl_declspec *
-merge_specs(struct cdecl_declspec *l1, size_t n1,
- struct cdecl_declspec *l2, size_t n2)
+merge_specs(struct cdecl_declspec *l1, struct cdecl_declspec *l2)
{
- struct cdecl_declspec *top = l1, **p = ⊤
-
- assert(n1 > 0 && n2 > 0);
+ struct cdecl_declspec *head = NULL, **x = &head;
- for (size_t i = 0, j = 0; i < n1 && j < n2;) {
- int ord = compare_specs(l1, l2);
- struct cdecl_declspec *tmp;
-
- if (ord <= 0) {
- p = &l1->next;
+ while (l1 && l2) {
+ if (compare_specs(l1, l2) > 0) {
+ *x = l2;
+ l2 = l2->next;
+ } else {
+ *x = l1;
l1 = l1->next;
- i++;
- } else if (ord > 0) {
- tmp = l2->next;
- l2->next = l1;
- *p = l2;
- p = &l2->next;
- l2 = tmp;
-
- j++;
}
-
- if (!l1)
- *p = l2;
+ x = &(*x)->next;
}
- return top;
+ *x = l1 ? l1 : l2;
+ return head;
}
-
-/*
- * A simple merge sort. Set n to the number of elements in the list, or 0
- * to have the sort function count them.
- */
-static struct cdecl_declspec *sort_specs(struct cdecl_declspec *l1, size_t n)
+/* Merge sort a specifier list, where n is the number of items in the list. */
+static struct cdecl_declspec *
+sort_specs(struct cdecl_declspec *l1, size_t n)
{
- struct cdecl_declspec *l2, *c;
- size_t i;
+ struct cdecl_declspec *l2 = l1, **x = &l1;
+ size_t i, n1;
- /* Find the midpoint of the list. */
- if (n > 1) {
- for (i = 0, l2 = l1; i < (n+1)/2; i++)
- l2 = l2->next;
- } else if (n == 0) {
- for (i = 0, c = l2 = l1; c; i++, c = c->next) {
- if (i % 2 == 0)
- l2 = l2->next;
- }
-
- n = i;
- }
-
- assert(n != 0);
- if (n == 1) {
- l1->next = NULL;
+ if (n < 2)
return l1;
- }
- /* l1 always has the longer "half". */
- l1 = sort_specs(l1, (n+1)/2);
- l2 = sort_specs(l2, n/2);
+ n1 = n/2;
+ for (i = 0; i < n1; i++) {
+ x = &l2->next;
+ l2 = *x;
+ }
+ *x = NULL;
- return merge_specs(l1, (n+1)/2, l2, n/2);
+ l1 = sort_specs(l1, n1);
+ l2 = sort_specs(l2, (n+1)/2);
+ return merge_specs(l1, l2);
}
+/*
+ * Mask to clear the type/storage specifier bits on one side of the comparison
+ * to ensure that only function specifiers and qualifiers comapare equal below.
+ */
+#define SPEC_DUP_MASK (~(CDECL_SPEC_TYPE|CDECL_SPEC_STOR|0u))
+
/*
* C allows declaration specifiers to appear in any order, and allows arbitrary
* repetition of some kinds of specifiers. Normalize the specifier lists by
struct cdecl_declspec *cdecl__normalize_specs(struct cdecl_declspec *specs)
{
struct cdecl_declspec *c, *l;
+ size_t count = 0;
+
+ for (c = specs; c; c = c->next)
+ count++;
- if (!specs)
+ if (!(l = specs = sort_specs(specs, count)))
return NULL;
- specs = sort_specs(specs, 0);
-
- for (c = specs, l = NULL; c; l = c, c = c->next) {
- switch (cdecl_spec_kind(c)) {
- case CDECL_SPEC_QUAL:
- case CDECL_SPEC_FUNC:
- if (l && l->type == c->type) {
- l->next = c->next;
- free(c);
- c = l;
- }
+ while ((c = l->next)) {
+ if ((l->type & SPEC_DUP_MASK) == c->type) {
+ l->next = c->next;
+ free(c);
+ } else {
+ l = c;
}
}
projects / cdecl99.git / blobdiff