/*
 *  Normalize C declaration specifier lists.
 *  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
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  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 "cdecl-internal.h"

/*
 * 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 int order_spec(const struct cdecl_declspec *spec)
{
	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(const struct cdecl_declspec *a, const struct cdecl_declspec *b)
{
	return order_spec(a) - order_spec(b);
}

/* Merge two sorted specifier lists, and return the head of the sorted list. */
static struct cdecl_declspec *
merge_specs(struct cdecl_declspec *l1, struct cdecl_declspec *l2)
{
	struct cdecl_declspec *head = NULL, **x = &head;

	while (l1 && l2) {
		if (compare_specs(l1, l2) > 0) {
			*x = l2;
			l2 = l2->next;
		} else {
			*x = l1;
			l1 = l1->next;
		}
		x = &(*x)->next;
	}

	*x = l1 ? l1 : l2;
	return head;
}

/* 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 = l1, **x = &l1;
	size_t i, n1;

	if (n < 2)
		return l1;

	n1 = n/2;
	for (i = 0; i < n1; i++) {
		x = &l2->next;
		l2 = *x;
	}
	*x = NULL;

	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
 * sorting the specifiers and removing repeated function specifiers and type
 * qualifiers.
 */
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 (!(l = specs = sort_specs(specs, count)))
		return NULL;

	while ((c = l->next)) {
		if ((l->type & SPEC_DUP_MASK) == c->type) {
			l->next = c->next;
			free(c);
		} else {
			l = c;
		}
	}

	return specs;
}