/*
* 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 .
*/
#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, 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;
}