/*
 *  Normalize C declaration specifier lists.
 *  Copyright © 2011 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 "normalize.h"

/*
 * Totally order the declaration specifier types by defining an injection into
 * the natural numbers.
 */
static unsigned order_spec(struct cdecl_declspec *spec)
{
	switch (spec->type) {
#	include "ordspecs.h"
	default:
		assert(0);
	}
}

static int compare_specs(struct cdecl_declspec *a, struct cdecl_declspec *b)
{
	return order_spec(a) - order_spec(b);
}

/*
 * Merge two sorted specifier lists.  Each list must have at least one element.
 */
static struct cdecl_declspec *
merge_specs(struct cdecl_declspec *l1, size_t n1,
            struct cdecl_declspec *l2, size_t n2)
{
	struct cdecl_declspec *top = l1, **p = &top;

	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;
			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;
	}

	return top;
}
        

/*
 * 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)
{
	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;
		}

		n = i;
	}

	assert(n != 0);
	if (n == 1) {
		l1->next = NULL;
		return l1;
	}

	/* l1 always has the longer "half". */
	l1 = sort_specs(l1, (n+1)/2);
	l2 = sort_specs(l2, n/2);

	return merge_specs(l1, (n+1)/2, l2, n/2);
}

/*
 * 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;

	if (!specs)
		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;
			}
		}
	}

	return specs;
}