block.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include "block.h"
   4 #include "hash.h"
   5 #include "name.h"
   6 #include "strutils.h"
   7 #include "utils.h"
   8
   9 struct ref {
  10         char *name;
  11         int flags;
  12 };
  13
  14 struct ref *ref_init(char *name, int flags)
  15 {
  16         struct ref *result = xmalloc(sizeof(struct ref));
  17         result->name = name;
  18         result->flags = flags;
  19         return result;
  20 }
  21
  22 struct block *block_init(struct node *node)
  23 {
  24         struct block *block = xmalloc(sizeof(struct block));
  25         memset(block, 0, sizeof(*block));
  26         block->node = node;
  27         return block;
  28 }
  29
  30 static void free_hashed(void *name, void *data)
  31 {
  32         free(name);
  33 }
  34
  35 void block_free(struct block *block)
  36 {
  37         struct block_list *cur = block->_children;
  38         while (cur) {
  39                 struct block_list *next = cur->next;
  40                 block_free(cur->block);
  41                 free(cur);
  42                 cur = next;
  43         }
  44         if (block->_names) {
  45                 hash_walk(block->_names, free_hashed, NULL);
  46                 hash_release(block->_names);
  47         }
  48         free(block);
  49 }
  50
  51 static int find_blocks(struct node *node, void *data)
  52 {
  53         struct block *block = data;
  54         if (node == block->node)
  55                 return 1;
  56         if (node->type == AST_BLOCK || node->type == AST_FUNCTION) {
  57                 struct block_list *newchild = xmalloc(sizeof(struct block_list));
  58                 newchild->block = block_init(node);
  59                 newchild->block->parent = block;
  60                 newchild->next = block->_children;
  61                 block->_children = newchild;
  62                 return 0;
  63         }
  64         return 1;
  65 }
  66
  67 static void init_children(struct block *block)
  68 {
  69         struct block_list *cur = NULL;
  70         struct block_list *newhead = NULL;
  71         node_walk(block->node, find_blocks, block);
  72         /* reversing children order */
  73         cur = block->_children;
  74         while (cur) {
  75                 struct block_list *next = cur->next;
  76                 cur->next = newhead;
  77                 newhead = cur;
  78                 cur = next;
  79         }
  80         block->_children = newhead;
  81         block->walked = 1;
  82 }
  83
  84 struct block_list *block_children(struct block *block)
  85 {
  86         if (!block->walked)
  87                 init_children(block);
  88         return block->_children;
  89 }
  90
  91 static void block_walk(struct block *block,
  92                 int (*see)(struct block *, void *),
  93                 void *data)
  94 {
  95         if (see(block, data)) {
  96                 struct block_list *cur;
  97                 cur = block_children(block);
  98                 while (cur) {
  99                         block_walk(cur->block, see, data);
 100                         cur = cur->next;
 101                 }
 102         }
 103 }
 104
 105 struct block_search {
 106         long offset;
 107         struct block *result;
 108 };
 109
 110 static int search_offset(struct block *block, void *data)
 111 {
 112         struct block_search *search = data;
 113         long offset = search->offset;
 114         if (block->node->start <= offset && offset < block->node->end) {
 115                 search->result = block;
 116                 return 1;
 117         }
 118         return 0;
 119 }
 120
 121 struct block *block_find(struct block *block, long offset)
 122 {
 123         struct block_search result;
 124         result.offset = offset;
 125         result.result = NULL;
 126         block_walk(block, search_offset, &result);
 127         return result.result;
 128 }
 129
 130 static void handle_enum(struct block *block, struct node *node)
 131 {
 132         int i;
 133         /* ENUM -> ENUMLIST */
 134         struct node *list = node->children[node->count - 1];
 135         if (list->type != AST_ENUMLIST)
 136                 return;
 137         if (node->children[0]->type == AST_IDENTIFIER)
 138                 hash_put(block_names(block),
 139                          name_init(node->children[0], NAME_ENUM));
 140         for (i = 0; i < list->count; i++) {
 141                 /* ENUMLIST -> ENUMVAL -> IDENTIFIER */
 142                 struct node *child = list->children[i]->children[0];
 143                 hash_put(block_names(block),
 144                          name_init(child, 0));
 145         }
 146 }
 147
 148 static void handle_struct(struct block *block, struct node *node)
 149 {
 150         if (node->count < 3)
 151                 return;
 152         if (node->children[1]->type == AST_IDENTIFIER) {
 153                 int flags = node->children[0]->type == AST_STRUCTKW ?
 154                         NAME_STRUCT : NAME_UNION;
 155                 hash_put(block_names(block),
 156                          name_init(node->children[1], flags));
 157         }
 158 }
 159
 160 struct declinfo {
 161         struct block *block;
 162         int flags;
 163         unsigned isstatic : 1;
 164         unsigned isextern : 1;
 165 };
 166
 167 static int analyze_declspec(struct node *node, void *data)
 168 {
 169         struct declinfo *declinfo = data;
 170         switch (node->type) {
 171         case AST_ENUM:
 172                 handle_enum(declinfo->block, node);
 173                 return 0;
 174         case AST_STRUCT:
 175                 handle_struct(declinfo->block, node);
 176                 return 0;
 177         case AST_STATICKW:
 178                 declinfo->isstatic = 1;
 179                 return 0;
 180         case AST_EXTERNKW:
 181                 declinfo->isextern = 1;
 182                 return 0;
 183         default:
 184                 return 1;
 185         }
 186 }
 187
 188 static int declinfo_flags(struct declinfo *declinfo)
 189 {
 190         int flags = 0;
 191         if (declinfo->isstatic)
 192                 flags |= NAME_STATIC;
 193         if (declinfo->isextern)
 194                 flags |= NAME_EXTERN;
 195         return flags | declinfo->flags;
 196 }
 197
 198 static void handle_function(struct block *block, struct node *node)
 199 {
 200         struct node *name;
 201         struct declinfo declinfo;
 202         memset(&declinfo, 0, sizeof(declinfo));
 203         node_walk(node->children[0], analyze_declspec, &declinfo);
 204         name = declarator_name(node->children[1]);
 205         if (name) {
 206                 int flags = declinfo_flags(&declinfo) | NAME_FUNCTION;
 207                 hash_put(block_names(block), name_init(name, flags));
 208         }
 209 }
 210
 211 static void add_declarator_name(struct declinfo *declinfo, struct node *decl)
 212 {
 213         struct node *name;
 214         struct block *block = declinfo->block;
 215         struct node *dirdecl = decl->children[decl->count - 1];
 216         /* nothing to do for function declarations */
 217         switch (*(enum decltype *) dirdecl->data) {
 218         case DECL_PARENS:
 219         case DECL_PARENS_TYPE:
 220         case DECL_PARENS_ID:
 221                 return;
 222         default:
 223                 break;
 224         }
 225         name = declarator_name(decl);
 226         if (name)
 227                 hash_put(block_names(block),
 228                          name_init(name, declinfo_flags(declinfo)));
 229 }
 230
 231 static int search_declarators(struct node *node, void *data)
 232 {
 233         struct declinfo *declinfo = data;
 234         if (node->type == AST_INIT) {
 235                 add_declarator_name(declinfo, node->children[0]);
 236                 return 0;
 237         }
 238         /* should ignore "extern int var" but not "extern int var = 1" */
 239         if (!declinfo->isextern && node->type == AST_DECL) {
 240                 add_declarator_name(declinfo, node);
 241                 return 0;
 242         }
 243         return 1;
 244 }
 245
 246 static void handle_declaration(struct block *block,
 247                                struct node *node,
 248                                int flags)
 249 {
 250         struct declinfo declinfo;
 251         memset(&declinfo, 0, sizeof(declinfo));
 252         declinfo.block = block;
 253         declinfo.flags = flags;
 254         node_walk(node->children[0], analyze_declspec, &declinfo);
 255         if (node->count > 1)
 256                 node_walk(node->children[1], search_declarators, &declinfo);
 257 }
 258
 259 static void handle_parameters(struct block *block, struct node *node)
 260 {
 261         int i;
 262         for (i = 0; i < node->count; i++) {
 263                 struct node *param = node->children[i];
 264                 if (param->count > 1) {
 265                         struct node *name = declarator_name(
 266                                 param->children[param->count - 1]);
 267                         if (name)
 268                                 hash_put(block_names(block),
 269                                          name_init(name, 0));
 270                 }
 271         }
 272 }
 273
 274 static void handle_label(struct block *block, struct node *node)
 275 {
 276         struct node *id = node->children[0];
 277         hash_put(block_names(block), name_init(id, NAME_LABEL));
 278 }
 279
 280 static int find_names(struct node *node, void *data)
 281 {
 282         struct block *block = data;
 283         switch (node->type) {
 284         case AST_FUNCTION:
 285                 handle_function(block, node);
 286                 break;
 287         case AST_DECLSTMT:
 288                 handle_declaration(block, node, 0);
 289                 break;
 290         case AST_LABELED:
 291                 handle_label(block, node);
 292                 return 1;
 293         case AST_BLOCKLIST:
 294         case AST_DECLLIST:
 295                 return 1;
 296         default:
 297                 break;
 298         }
 299         return block->node == node;
 300 }
 301
 302 static long name_hash(void *name)
 303 {
 304         return str_hash(((struct name *) name)->name);
 305 }
 306
 307 static long ref_hash(void *name)
 308 {
 309         return str_hash(((struct name *) name)->name);
 310 }
 311
 312 static int name_cmp(void *data, void *key)
 313 {
 314         struct name *name = data;
 315         struct ref *ref = key;
 316         if (!strcmp(name->name, ref->name))
 317                 return !modifiers_match(name, ref->flags);
 318         return 1;
 319 }
 320
 321 static void init_names(struct block *block)
 322 {
 323         block->_names = hash_init(name_hash, ref_hash, name_cmp, 4);
 324         if (block->node->type == AST_FUNCTION) {
 325                 /* FUNCTION -> DECL -> DECL2 -> PARAMLIST */
 326                 struct node *node = block->node;
 327                 struct node *decl = node->children[node->count - 2];
 328                 struct node *decl2 = decl->children[decl->count - 1];
 329                 if (decl2->count > 1) {
 330                         struct node *params = decl2->children[decl2->count - 1];
 331                         handle_parameters(block, params);
 332                 }
 333                 if (node->count >= 4) {
 334                         int i;
 335                         struct node *decllist = node->children[node->count - 2];
 336                         for (i = 0; i < decllist->count; i++)
 337                                 handle_declaration(block,
 338                                                    decllist->children[i],
 339                                                    NAME_PARAM);
 340                 }
 341         } else {
 342                 node_walk(block->node, find_names, block);
 343         }
 344 }
 345
 346 struct hash *block_names(struct block *block)
 347 {
 348         if (!block->_names)
 349                 init_names(block);
 350         return block->_names;
 351 }
 352
 353 struct ref *name_on(struct node *node)
 354 {
 355         if (node->type != AST_IDENTIFIER && node->type != AST_TYPENAME)
 356                 return NULL;
 357         return ref_init(node->data, guess_name_flags(node));
 358 }
 359
 360 struct block *block_defining(struct block *block, struct node *node)
 361 {
 362         struct ref *ref = name_on(node);
 363         while (block && !hash_get(block_names(block), ref))
 364                 block = block->parent;
 365         free(ref);
 366         return block;
 367 }
 368
 369 struct name *block_lookup(struct block *block, struct node *node)
 370 {
 371         struct ref *ref = name_on(node);
 372         struct name *result = NULL;
 373         if (!ref || ref->flags & (NAME_FIELD | NAME_PARAMDECL))
 374                 return NULL;
 375         while (block) {
 376                 struct name *cur = hash_get(block_names(block), ref);
 377                 if (cur) {
 378                         result = cur;
 379                         break;
 380                 }
 381                 block = block->parent;
 382         }
 383         free(ref);
 384         return result;
 385 }
 386
 387 struct {
 388         char *name;
 389         int flag;
 390 } tags[] = {{"struct ", NAME_STRUCT},
 391             {"enum ", NAME_ENUM},
 392             {"union ", NAME_UNION},
 393             {"label ", NAME_LABEL}};
 394
 395 static struct ref *token_name(char *token)
 396 {
 397         int flags = 0;
 398         int i;
 399         for (i = 0; i < LENGTH(tags); i++) {
 400                 if (startswith(token, tags[i].name)) {
 401                         token += strlen(tags[i].name);
 402                         flags |= tags[i].flag;
 403                         break;
 404                 }
 405         }
 406         return ref_init(token, flags);
 407 }
 408
 409 static struct block *block_byname(struct block *block, char *name)
 410 {
 411         struct block_list *blist = block_children(block);
 412         while (blist) {
 413                 struct node *node = blist->block->node;
 414                 struct node *declname = declarator_name(node->children[1]);
 415                 if (node->type == AST_FUNCTION &&
 416                     !strcmp(name, declname->data))
 417                         return blist->block;
 418                 blist = blist->next;
 419         }
 420         return NULL;
 421 }
 422
 423 struct name *block_find_hier(struct block *block, char *location)
 424 {
 425         char token[128];
 426         char *newlocation = readtoken(token, location, ":");
 427         struct block_list *blist = NULL;
 428         if (*newlocation) {
 429                 struct block *newblock = block_byname(block, token);
 430                 if (newblock)
 431                         return block_find_hier(newblock, newlocation);
 432         } else {
 433                 struct ref *key = token_name(token);
 434                 struct name *name = hash_get(block_names(block), key);
 435                 free(key);
 436                 if (name)
 437                         return name;
 438         }
 439         blist = block_children(block);
 440         while (blist) {
 441                 struct name *name = block_find_hier(blist->block, location);
 442                 if (name)
 443                         return name;
 444                 blist = blist->next;
 445         }
 446         return NULL;
 447 }