src/normalize.c

   1 /*
   2  *  Normalize C declaration specifier lists.
   3  *  Copyright © 2011, 2021, 2023 Nick Bowler
   4  *
   5  *  This program is free software: you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation, either version 3 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #include <config.h>
  20 #include <stdlib.h>
  21 #include <assert.h>
  22
  23 #include "cdecl.h"
  24 #include "cdecl-internal.h"
  25
  26 /*
  27  * Partially order the declaration specifiers by assigning each specifier
  28  * type an appropriate integer value.  These values need not be unique for
  29  * specifiers that never appear together.
  30  *
  31  * This implementation relies implicitly on the specific enumeration values.
  32  * These values are expected to be stable as they are exposed library API.
  33  */
  34 static int order_spec(const struct cdecl_declspec *spec)
  35 {
  36         unsigned kind = cdecl_spec_kind(spec);
  37         unsigned ret = spec->type;
  38
  39         /* General sequence: storage, function, qualifier, type */
  40         switch (kind) {
  41         case CDECL_SPEC_QUAL:
  42                 ret |= CDECL_SPEC_FUNC;
  43                 break;
  44         case CDECL_SPEC_TYPE:
  45                 /* Manually reorder some elements that are in the wrong place */
  46                 switch (ret) {
  47                 case CDECL_TYPE_INT:
  48                         ret += 2; /* OK because "float int" is invalid. */
  49                         break;
  50                 case CDECL_TYPE_SIGNED:
  51                 case CDECL_TYPE_UNSIGNED:
  52                         ret = CDECL_TYPE_VOID;
  53                         break;
  54                 }
  55                 ret |= CDECL_SPEC_FUNC|CDECL_SPEC_QUAL;
  56         }
  57
  58         return ret;
  59 }
  60
  61 static int
  62 compare_specs(const struct cdecl_declspec *a, const struct cdecl_declspec *b)
  63 {
  64         return order_spec(a) - order_spec(b);
  65 }
  66
  67 /* Merge two sorted specifier lists, and return the head of the sorted list. */
  68 static struct cdecl_declspec *
  69 merge_specs(struct cdecl_declspec *l1, struct cdecl_declspec *l2)
  70 {
  71         struct cdecl_declspec *head = NULL, **x = &head;
  72
  73         while (l1 && l2) {
  74                 if (compare_specs(l1, l2) > 0) {
  75                         *x = l2;
  76                         l2 = l2->next;
  77                 } else {
  78                         *x = l1;
  79                         l1 = l1->next;
  80                 }
  81                 x = &(*x)->next;
  82         }
  83
  84         *x = l1 ? l1 : l2;
  85         return head;
  86 }
  87
  88 /* Merge sort a specifier list, where n is the number of items in the list. */
  89 static struct cdecl_declspec *
  90 sort_specs(struct cdecl_declspec *l1, size_t n)
  91 {
  92         struct cdecl_declspec *l2 = l1, **x = &l1;
  93         size_t i, n1;
  94
  95         if (n < 2)
  96                 return l1;
  97
  98         n1 = n/2;
  99         for (i = 0; i < n1; i++) {
 100                 x = &l2->next;
 101                 l2 = *x;
 102         }
 103         *x = NULL;
 104
 105         l1 = sort_specs(l1, n1);
 106         l2 = sort_specs(l2, (n+1)/2);
 107         return merge_specs(l1, l2);
 108 }
 109
 110 /*
 111  * Mask to clear the type/storage specifier bits on one side of the comparison
 112  * to ensure that only function specifiers and qualifiers comapare equal below.
 113  */
 114 #define SPEC_DUP_MASK (~(CDECL_SPEC_TYPE|CDECL_SPEC_STOR|0u))
 115
 116 /*
 117  * C allows declaration specifiers to appear in any order, and allows arbitrary
 118  * repetition of some kinds of specifiers.  Normalize the specifier lists by
 119  * sorting the specifiers and removing repeated function specifiers and type
 120  * qualifiers.
 121  */
 122 struct cdecl_declspec *cdecl__normalize_specs(struct cdecl_declspec *specs)
 123 {
 124         struct cdecl_declspec *c, *l;
 125         size_t count = 0;
 126
 127         for (c = specs; c; c = c->next)
 128                 count++;
 129
 130         if (!(l = specs = sort_specs(specs, count)))
 131                 return NULL;
 132
 133         while ((c = l->next)) {
 134                 if ((l->type & SPEC_DUP_MASK) == c->type) {
 135                         l->next = c->next;
 136                         free(c);
 137                 } else {
 138                         l = c;
 139                 }
 140         }
 141
 142         return specs;
 143 }