X-Git-Url: https://git.draconx.ca/gitweb/cdecl99.git/blobdiff_plain/31ac11cc668bb8ecc1317fd2e8bd79b7925bceeb..032fe50c0297846a8d03eda505c9726f60a46501:/src/normalize.c

diff --git a/src/normalize.c b/src/normalize.c
index 704d575..8cd0020 100644
--- a/src/normalize.c
+++ b/src/normalize.c
@@ -1,6 +1,6 @@
 /*
  *  Normalize C declaration specifier lists.
- *  Copyright © 2011 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
@@ -15,101 +15,96 @@
  *  You should have received a copy of the GNU General Public License
  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
+
 #include <config.h>
 #include <stdlib.h>
 #include <assert.h>
 
 #include "cdecl.h"
-#include "normalize.h"
+#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 = &top;
+	struct cdecl_declspec *head = NULL, **x = &head;
 
-	assert(n1 > 0 && n2 > 0);
-
-	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;
-
-	/* 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;
-		}
+	struct cdecl_declspec *l2 = l1, **x = &l1;
+	size_t i, n1;
 
-		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);
 }
 
 /*
@@ -121,21 +116,20 @@ static struct cdecl_declspec *sort_specs(struct cdecl_declspec *l1, size_t n)
 struct cdecl_declspec *cdecl__normalize_specs(struct cdecl_declspec *specs)
 {
 	struct cdecl_declspec *c, *l;
+	size_t count = 0;
 
-	if (!specs)
-		return NULL;
-
-	specs = sort_specs(specs, 0);
+	for (c = specs; c; c = c->next)
+		count++;
+	specs = sort_specs(specs, count);
 
 	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;
-			}
+		if (!(c->type & (CDECL_SPEC_QUAL|CDECL_SPEC_FUNC)))
+			continue;
+
+		if (l && l->type == c->type) {
+			l->next = c->next;
+			free(c);
+			c = l;
 		}
 	}