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  * Totally order the declaration specifier types by defining an injection into
  28  * the natural numbers.
  29  */
  30 static unsigned order_spec(struct cdecl_declspec *spec)
  31 {
  32         switch (spec->type) {
  33 #       include "ordspecs.h"
  34         default:
  35                 assert(0);
  36         }
  37 }
  38
  39 static int compare_specs(struct cdecl_declspec *a, struct cdecl_declspec *b)
  40 {
  41         return order_spec(a) - order_spec(b);
  42 }
  43
  44 /*
  45  * Merge two sorted specifier lists.  Each list must have at least one element.
  46  */
  47 static struct cdecl_declspec *
  48 merge_specs(struct cdecl_declspec *l1, size_t n1,
  49             struct cdecl_declspec *l2, size_t n2)
  50 {
  51         struct cdecl_declspec *top = l1, **p = &top;
  52
  53         assert(n1 > 0 && n2 > 0);
  54
  55         for (size_t i = 0, j = 0; i < n1 && j < n2;) {
  56                 int ord = compare_specs(l1, l2);
  57                 struct cdecl_declspec *tmp;
  58
  59                 if (ord <= 0) {
  60                         p = &l1->next;
  61                         l1 = l1->next;
  62                         i++;
  63                 } else if (ord > 0) {
  64                         tmp = l2->next;
  65                         l2->next = l1;
  66                         *p = l2;
  67                         p = &l2->next;
  68                         l2 = tmp;
  69
  70                         j++;
  71                 }
  72
  73                 if (!l1)
  74                         *p = l2;
  75         }
  76
  77         return top;
  78 }
  79
  80
  81 /*
  82  * A simple merge sort.  Set n to the number of elements in the list, or 0
  83  * to have the sort function count them.
  84  */
  85 static struct cdecl_declspec *sort_specs(struct cdecl_declspec *l1, size_t n)
  86 {
  87         struct cdecl_declspec *l2, *c;
  88         size_t i;
  89
  90         /* Find the midpoint of the list. */
  91         if (n > 1) {
  92                 for (i = 0, l2 = l1; i < (n+1)/2; i++)
  93                         l2 = l2->next;
  94         } else if (n == 0) {
  95                 for (i = 0, c = l2 = l1; c; i++, c = c->next) {
  96                         if (i % 2 == 0)
  97                                 l2 = l2->next;
  98                 }
  99
 100                 n = i;
 101         }
 102
 103         assert(n != 0);
 104         if (n == 1) {
 105                 l1->next = NULL;
 106                 return l1;
 107         }
 108
 109         /* l1 always has the longer "half". */
 110         l1 = sort_specs(l1, (n+1)/2);
 111         l2 = sort_specs(l2, n/2);
 112
 113         return merge_specs(l1, (n+1)/2, l2, n/2);
 114 }
 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
 126         if (!specs)
 127                 return NULL;
 128
 129         specs = sort_specs(specs, 0);
 130
 131         for (c = specs, l = NULL; c; l = c, c = c->next) {
 132                 switch (cdecl_spec_kind(c)) {
 133                 case CDECL_SPEC_QUAL:
 134                 case CDECL_SPEC_FUNC:
 135                         if (l && l->type == c->type) {
 136                                 l->next = c->next;
 137                                 free(c);
 138                                 c = l;
 139                         }
 140                 }
 141         }
 142
 143         return specs;
 144 }