src/normalize.c

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