src/normalize.c

   1 /*
   2  *  Normalize C declaration specifier lists.
   3  *  Copyright © 2011, 2021 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 compare_specs(const struct cdecl_declspec *a,
  62                          const struct cdecl_declspec *b)
  63 {
  64         return order_spec(a) - order_spec(b);
  65 }
  66
  67 /*
  68  * Merge two sorted specifier lists.  Each list must have at least one element.
  69  */
  70 static struct cdecl_declspec *
  71 merge_specs(struct cdecl_declspec *l1, size_t n1,
  72             struct cdecl_declspec *l2, size_t n2)
  73 {
  74         struct cdecl_declspec *top = l1, **p = &top;
  75
  76         assert(n1 > 0 && n2 > 0);
  77
  78         for (size_t i = 0, j = 0; i < n1 && j < n2;) {
  79                 int ord = compare_specs(l1, l2);
  80                 struct cdecl_declspec *tmp;
  81
  82                 if (ord <= 0) {
  83                         p = &l1->next;
  84                         l1 = l1->next;
  85                         i++;
  86                 } else if (ord > 0) {
  87                         tmp = l2->next;
  88                         l2->next = l1;
  89                         *p = l2;
  90                         p = &l2->next;
  91                         l2 = tmp;
  92
  93                         j++;
  94                 }
  95
  96                 if (!l1)
  97                         *p = l2;
  98         }
  99
 100         return top;
 101 }
 102
 103
 104 /*
 105  * A simple merge sort.  Set n to the number of elements in the list, or 0
 106  * to have the sort function count them.
 107  */
 108 static struct cdecl_declspec *sort_specs(struct cdecl_declspec *l1, size_t n)
 109 {
 110         struct cdecl_declspec *l2, *c;
 111         size_t i;
 112
 113         /* Find the midpoint of the list. */
 114         if (n > 1) {
 115                 for (i = 0, l2 = l1; i < (n+1)/2; i++)
 116                         l2 = l2->next;
 117         } else if (n == 0) {
 118                 for (i = 0, c = l2 = l1; c; i++, c = c->next) {
 119                         if (i % 2 == 0)
 120                                 l2 = l2->next;
 121                 }
 122
 123                 n = i;
 124         }
 125
 126         assert(n != 0);
 127         if (n == 1) {
 128                 l1->next = NULL;
 129                 return l1;
 130         }
 131
 132         /* l1 always has the longer "half". */
 133         l1 = sort_specs(l1, (n+1)/2);
 134         l2 = sort_specs(l2, n/2);
 135
 136         return merge_specs(l1, (n+1)/2, l2, n/2);
 137 }
 138
 139 /*
 140  * C allows declaration specifiers to appear in any order, and allows arbitrary
 141  * repetition of some kinds of specifiers.  Normalize the specifier lists by
 142  * sorting the specifiers and removing repeated function specifiers and type
 143  * qualifiers.
 144  */
 145 struct cdecl_declspec *cdecl__normalize_specs(struct cdecl_declspec *specs)
 146 {
 147         struct cdecl_declspec *c, *l;
 148
 149         if (!specs)
 150                 return NULL;
 151
 152         specs = sort_specs(specs, 0);
 153
 154         for (c = specs, l = NULL; c; l = c, c = c->next) {
 155                 switch (cdecl_spec_kind(c)) {
 156                 case CDECL_SPEC_QUAL:
 157                 case CDECL_SPEC_FUNC:
 158                         if (l && l->type == c->type) {
 159                                 l->next = c->next;
 160                                 free(c);
 161                                 c = l;
 162                         }
 163                 }
 164         }
 165
 166         return specs;
 167 }