/*
* Normalize C declaration specifier lists.
* Copyright © 2011, 2021 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 .
*/
#include
#include
#include
#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. 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 = ⊤
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;
}