tagmanager/tm_symbol.c

   1 /*
   2 *
   3 *   Copyright (c) 2001-2002, Biswapesh Chattopadhyay
   4 *
   5 *   This source code is released for free distribution under the terms of the
   6 *   GNU General Public License.
   7 *
   8 */
   9
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12 #include <string.h>
  13 #include "tm_symbol.h"
  14 #include "tm_workspace.h"
  15
  16 static GMemChunk *sym_mem_chunk = NULL;
  17
  18 #define SYM_NEW(T) {\
  19         if (!sym_mem_chunk) \
  20                 sym_mem_chunk = g_mem_chunk_new("TMSymbol MemChunk", sizeof(TMSymbol), 1024 \
  21                   , G_ALLOC_AND_FREE); \
  22         (T) = g_chunk_new0(TMSymbol, sym_mem_chunk);}
  23
  24 #define SYM_FREE(T) g_mem_chunk_free(sym_mem_chunk, (T))
  25
  26 void tm_symbol_print(TMSymbol *sym, guint level)
  27 {
  28         guint i;
  29
  30         g_return_if_fail (sym != NULL);
  31         for (i=0; i < level; ++i)
  32                 fputc('\t', stderr);
  33         fprintf(stderr, "%s\n", (sym->tag)?sym->tag->name:"Root");
  34         if (sym->info.children)
  35         {
  36                 if (sym->tag)
  37                 {
  38                         if (tm_tag_function_t == sym->tag->type ||
  39                             tm_tag_prototype_t == sym->tag->type)
  40                         {
  41                                 tm_tag_print(sym->info.equiv, stderr);
  42                         }
  43                 }
  44                 else
  45                 {
  46                         for (i=0; i < sym->info.children->len; ++i)
  47                                 tm_symbol_print(TM_SYMBOL(sym->info.children->pdata[i])
  48                                   , level + 1);
  49                 }
  50         }
  51 }
  52
  53 #define SYM_ORDER(T) (((tm_tag_class_t == (T)->type) || (tm_tag_struct_t ==\
  54         (T)->type))?1:(((tm_tag_enum_t == (T)->type) || (tm_tag_interface_t ==\
  55         (T)->type))?2:3))
  56
  57 /* Comparison function for sorting symbols alphabetically */
  58 int tm_symbol_compare(const void *p1, const void *p2)
  59 {
  60         TMSymbol *s1, *s2;
  61
  62         if (!p1 && !p2)
  63                 return 0;
  64         else if (!p2)
  65                 return 1;
  66         else if (!p1)
  67                 return -1;
  68         s1 = *(TMSymbol **) p1;
  69         s2 = *(TMSymbol **) p2;
  70         if (!s1 && !s2)
  71                 return 0;
  72         else if (!s2)
  73                 return 1;
  74         else if (!s1)
  75                 return -1;
  76         if (!s1->tag && !s2->tag)
  77                 return 0;
  78         else if (!s2->tag)
  79                 return 1;
  80         else if (!s1->tag)
  81                 return -1;
  82         return strcmp(s1->tag->name, s2->tag->name);
  83 }
  84
  85 /*
  86  * Compares function argument lists.
  87  * FIXME: Compare based on types, not an exact string match.
  88  */
  89 int tm_arglist_compare(const TMTag* t1, const TMTag* t2)
  90 {
  91         return strcmp(NVL(t1->atts.entry.arglist, "()"),
  92                         NVL(t2->atts.entry.arglist, "()"));
  93 }
  94
  95 /* Need this custom compare function to generate a symbol tree
  96 in a simgle pass from tag list */
  97 int tm_symbol_tag_compare(const TMTag **t1, const TMTag **t2)
  98 {
  99         gint s1, s2;
 100
 101         if ((!t1 && !t2) || (!*t1 && !*t2))
 102                 return 0;
 103         else if (!t1 || !*t1)
 104                 return -1;
 105         else if (!t2 || !*t2)
 106                 return 1;
 107         if ((tm_tag_file_t == (*t1)->type) && (tm_tag_file_t == (*t2)->type))
 108                 return 0;
 109         else if (tm_tag_file_t == (*t1)->type)
 110                 return -1;
 111         else if (tm_tag_file_t == (*t2)->type)
 112                 return 1;
 113
 114         /* Compare on depth of scope - less depth gets higher priortity */
 115         s1 = tm_tag_scope_depth(*t1);
 116         s2 = tm_tag_scope_depth(*t2);
 117         if (s1 != s2)
 118                 return (s1 - s2);
 119
 120         /* Compare of tag type using a symbol ordering routine */
 121         s1 = SYM_ORDER(*t1);
 122         s2 = SYM_ORDER(*t2);
 123         if (s1 != s2)
 124                 return (s1 - s2);
 125
 126         /* Compare names alphabetically */
 127         s1 = strcmp((*t1)->name, (*t2)->name);
 128         if (s1 != 0)
 129                 return (s1);
 130
 131         /* Compare scope alphabetically */
 132         s1 = strcmp(NVL((*t1)->atts.entry.scope, ""),
 133           NVL((*t2)->atts.entry.scope, ""));
 134         if (s1 != 0)
 135                 return s1;
 136
 137         /* If none of them are function/prototype, they are effectively equal */
 138         if ((tm_tag_function_t != (*t1)->type) &&
 139             (tm_tag_prototype_t != (*t1)->type)&&
 140             (tm_tag_function_t != (*t2)->type) &&
 141             (tm_tag_prototype_t != (*t2)->type))
 142                 return 0;
 143
 144         /* Whichever is not a function/prototype goes first */
 145         if ((tm_tag_function_t != (*t1)->type) &&
 146             (tm_tag_prototype_t != (*t1)->type))
 147                 return -1;
 148         if ((tm_tag_function_t != (*t2)->type) &&
 149             (tm_tag_prototype_t != (*t2)->type))
 150                 return 1;
 151
 152         /* Compare the argument list */
 153         s1 = tm_arglist_compare(*t1, *t2);
 154         if (s1 != 0)
 155                 return s1;
 156
 157         /* Functions go before prototypes */
 158         if ((tm_tag_function_t == (*t1)->type) &&
 159             (tm_tag_function_t != (*t2)->type))
 160                 return -1;
 161         if ((tm_tag_function_t != (*t1)->type) &&
 162             (tm_tag_function_t == (*t2)->type))
 163                 return 1;
 164
 165         /* Give up */
 166         return 0;
 167 }
 168
 169 static void
 170 check_children_symbols(TMSymbol *sym, const char *name, gint level)
 171 {
 172   if (level > 5) {
 173     g_warning ("Infinite recursion detected (symbol name = %s) !!", name);
 174     return;
 175   }
 176   if(sym && name)
 177   {
 178     GPtrArray *scope_tags;
 179     TMTag *tag;
 180     TMSymbol *sym1 = sym->parent;
 181
 182     while(sym1 && (tag = sym1->tag) && tag->name)
 183     {
 184       if(0 == strcmp(tag->name, name))
 185       {
 186         return;
 187       }
 188       sym1 = sym1->parent;
 189     }
 190
 191     scope_tags = tm_tags_extract (tm_workspace_find_scope_members (NULL, name, FALSE, FALSE), tm_tag_max_t);
 192     if(scope_tags && scope_tags->len > 0)
 193     {
 194       unsigned int j;
 195       sym1 = NULL;
 196
 197       tm_tags_custom_sort (scope_tags,
 198                            (TMTagCompareFunc) tm_symbol_tag_compare,
 199                            FALSE);
 200       sym->info.children = g_ptr_array_sized_new(scope_tags->len);
 201       for (j=0; j < scope_tags->len; ++j)
 202       {
 203         tag = TM_TAG(scope_tags->pdata[j]);
 204         if (tm_tag_prototype_t == tag->type)
 205         {
 206                 /* Since the tags are sorted, we can now expect to find
 207                  * identical definitions/declarations in the previous element.
 208                  * Functions will come before their prototypes.
 209                  */
 210                 if (sym1 && (tm_tag_function_t == sym1->tag->type) &&
 211                   (!sym1->info.equiv) &&
 212                   (0 == strcmp(NVL(tag->atts.entry.scope, ""),
 213                                NVL(sym1->tag->atts.entry.scope, ""))) &&
 214                   (0 == strcmp(tag->name, sym1->tag->name)) &&
 215                   (0 == tm_arglist_compare(tag, sym1->tag)))
 216                 {
 217                         sym1->info.equiv = tag;
 218                         continue;
 219                 }
 220         }
 221         if (strcmp(tag->name, sym->tag->name) == 0)
 222         {
 223             continue; /* Avoid recursive definition */
 224         }
 225         SYM_NEW(sym1);
 226         sym1->tag = tag;
 227         sym1->parent = sym;
 228         g_ptr_array_add(sym->info.children, sym1);
 229       }
 230
 231       for (j=0; j < sym->info.children->len; ++j)
 232       {
 233         sym1 = TM_SYMBOL(sym->info.children->pdata[j]);
 234         if ((tm_tag_member_t & sym1->tag->type) == tm_tag_member_t &&
 235             sym1->tag->atts.entry.pointerOrder == 0)
 236           check_children_symbols(sym1, sym1->tag->atts.entry.type_ref[1],
 237                                  level + 1);
 238       }
 239     }
 240     if (scope_tags)
 241       g_ptr_array_free (scope_tags, TRUE);
 242   }
 243   return;
 244 }
 245
 246 static int
 247 tm_symbol_get_root_index (TMSymbol * sym)
 248 {
 249         int idx;
 250         char access;
 251
 252         access = sym->tag->atts.entry.access;
 253         switch (sym->tag->type)
 254         {
 255         case tm_tag_class_t:
 256                 idx = 0;
 257                 break;
 258         case tm_tag_struct_t:
 259                 idx = 1;
 260                 break;
 261         case tm_tag_union_t:
 262                 idx = 2;
 263                 break;
 264         case tm_tag_function_t:
 265                 switch (access)
 266                 {
 267                 case TAG_ACCESS_PRIVATE:
 268                 case TAG_ACCESS_PROTECTED:
 269                 case TAG_ACCESS_PUBLIC:
 270                         idx = 8;
 271                         break;
 272                 default:
 273                         idx = 3;
 274                         break;
 275                 }
 276                 break;
 277         case tm_tag_prototype_t:
 278                 if ((sym->info.equiv) && (TAG_ACCESS_UNKNOWN == access))
 279                         access = sym->info.equiv->atts.entry.access;
 280                 switch (access)
 281                 {
 282                 case TAG_ACCESS_PRIVATE:
 283                 case TAG_ACCESS_PROTECTED:
 284                 case TAG_ACCESS_PUBLIC:
 285                         idx = 8;
 286                         break;
 287                 default:
 288                         idx = 3;
 289                         break;
 290                 }
 291                 break;
 292         case tm_tag_member_t:
 293                 switch (access)
 294                 {
 295                 case TAG_ACCESS_PRIVATE:
 296                 case TAG_ACCESS_PROTECTED:
 297                 case TAG_ACCESS_PUBLIC:
 298                         idx = 8;
 299                         break;
 300                 default:
 301                         idx = 4;
 302                         break;
 303                 }
 304                 break;
 305         case tm_tag_variable_t:
 306         case tm_tag_externvar_t:
 307                 idx = 4;
 308                 break;
 309         case tm_tag_macro_t:
 310         case tm_tag_macro_with_arg_t:
 311                 idx = 5;
 312                 break;
 313         case tm_tag_typedef_t:
 314                 idx = 6;
 315                 break;
 316         case tm_tag_enumerator_t:
 317                 idx = 7;
 318                 break;
 319         default:
 320                 idx = 8;
 321                 break;
 322         }
 323         return idx;
 324 }
 325
 326 TMSymbol *tm_symbol_tree_new(GPtrArray *tags_array)
 327 {
 328         GPtrArray *tags;
 329         TMSymbol *grand_root = NULL;
 330         static int subroot_types[] = {
 331                 tm_tag_class_t, tm_tag_struct_t, tm_tag_union_t,
 332                 tm_tag_prototype_t, tm_tag_variable_t, tm_tag_macro_t,
 333                 tm_tag_typedef_t, tm_tag_enumerator_t, tm_tag_other_t,
 334                 tm_tag_undef_t
 335         };
 336         static TMTag subroot_tags[sizeof(subroot_types)] = {
 337                 {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}
 338         };
 339         static char* subroot_labels[sizeof(subroot_types)] = {
 340                 "Classes", "Structs", "Unions", "Functions", "Variables",
 341                 "Macros", "Typedefs", "Enumerators", "Others", NULL
 342         };
 343         TMSymbol *subroot[sizeof(subroot_types)] = {NULL, NULL, NULL,
 344                 NULL, NULL, NULL, NULL, NULL, NULL, NULL};
 345
 346 #ifdef TM_DEBUG
 347         g_message("Building symbol tree..");
 348 #endif
 349
 350         if ((!tags_array) || (tags_array->len <= 0))
 351                 return NULL;
 352
 353 #ifdef TM_DEBUG
 354         fprintf(stderr, "Dumping all tags..\n");
 355         tm_tags_array_print(tags_array, stderr);
 356 #endif
 357
 358         tags = tm_tags_extract(tags_array, tm_tag_max_t);
 359 #ifdef TM_DEBUG
 360         fprintf(stderr, "Dumping unordered tags..\n");
 361         tm_tags_array_print(tags, stderr);
 362 #endif
 363
 364         if (tags && (tags->len > 0))
 365         {
 366                 guint i;
 367
 368                 TMTag *tag;
 369                 TMSymbol *sym = NULL;
 370
 371                 /* Creating top-level symbols */
 372                 SYM_NEW(grand_root);
 373                 if (!grand_root->info.children)
 374                         grand_root->info.children = g_ptr_array_new();
 375
 376                 for (i = 0; subroot_types[i] != tm_tag_undef_t; i++)
 377                 {
 378                         SYM_NEW(sym);
 379                         subroot_tags[i].name = subroot_labels[i];
 380                         subroot_tags[i].type = subroot_types[i];
 381                         sym->tag = &subroot_tags[i];
 382                         sym->parent = grand_root;
 383                         g_ptr_array_add(grand_root->info.children, sym);
 384                         subroot[i] = sym;
 385                 }
 386
 387                 tm_tags_custom_sort(tags, (TMTagCompareFunc) tm_symbol_tag_compare
 388                   , FALSE);
 389
 390 #ifdef TM_DEBUG
 391                 fprintf(stderr, "Dumping ordered tags..");
 392                 tm_tags_array_print(tags, stderr);
 393                 fprintf(stderr, "Rebuilding symbol table..\n");
 394 #endif
 395                 sym = NULL;
 396                 for (i=0; i < tags->len; ++i)
 397                 {
 398                         tag = TM_TAG(tags->pdata[i]);
 399
 400                         if (tm_tag_prototype_t == tag->type)
 401                         {
 402                                 /* Since the tags are sorted, we can now expect to find
 403                                  * identical definitions/declarations in the previous element.
 404                                  * Functions will come before their prototypes.
 405                                  */
 406                                 if (sym && (tm_tag_function_t == sym->tag->type) &&
 407                                   (!sym->info.equiv) &&
 408                                   (0 == strcmp(NVL(tag->atts.entry.scope, ""),
 409                                                NVL(sym->tag->atts.entry.scope, ""))) &&
 410                                   (0 == strcmp(tag->name, sym->tag->name)) &&
 411                                   (0 == tm_arglist_compare(tag, sym->tag)))
 412                                 {
 413                                         sym->info.equiv = tag;
 414                                         continue;
 415                                 }
 416                         }
 417
 418                         if(tag->atts.entry.scope)
 419                         {
 420                                 if ((tm_tag_class_t | tm_tag_enum_t |
 421                                      tm_tag_struct_t | tm_tag_union_t) & tag->type)
 422                                 {
 423                                         /* this is Hack an shold be fixed by adding this info in tag struct */
 424                                         if(NULL != strstr(tag->name, "_fake_"))
 425                                         {
 426                                                 continue;
 427                                         }
 428                                 }
 429                                 else
 430                                 {
 431                                         continue;
 432                                 }
 433                         }
 434                         else
 435                         {
 436                                 if(!(tag->type & tm_tag_enum_t)
 437                                    && NULL != strstr(tag->name, "_fake_"))
 438                                 {
 439                                         /* This is Hack an should be fixed by adding this info in tag struct */
 440                                         continue;
 441                                 }
 442                         }
 443                         SYM_NEW(sym);
 444                         sym->tag = tag;
 445                         sym->parent = subroot[tm_symbol_get_root_index (sym)];
 446                         if (!sym->parent->info.children)
 447                                 sym->parent->info.children = g_ptr_array_new();
 448                         g_ptr_array_add(sym->parent->info.children, sym);
 449
 450                         if ((tm_tag_undef_t | tm_tag_function_t | tm_tag_prototype_t |
 451                                  tm_tag_macro_t | tm_tag_macro_with_arg_t | tm_tag_file_t)
 452                                 & tag->type)
 453                                 continue;
 454
 455                         check_children_symbols(sym, tag->name, 0);
 456                 }
 457 #ifdef TM_DEBUG
 458                 fprintf(stderr, "Done.Dumping symbol tree..");
 459                 tm_symbol_print(grand_root, 0);
 460 #endif
 461         }
 462         if (tags)
 463                 g_ptr_array_free(tags, TRUE);
 464
 465         return grand_root;
 466 }
 467
 468 static void tm_symbol_free(TMSymbol *sym)
 469 {
 470         if (!sym)
 471                 return;
 472         if (sym->info.children)
 473         {
 474                 guint i;
 475                 for (i=0; i < sym->info.children->len; ++i)
 476                         tm_symbol_free(TM_SYMBOL(sym->info.children->pdata[i]));
 477                 g_ptr_array_free(sym->info.children, TRUE);
 478                 sym->info.children = NULL;
 479         }
 480         SYM_FREE(sym);
 481 }
 482
 483 void tm_symbol_tree_free(gpointer root)
 484 {
 485         if (root)
 486                 tm_symbol_free(TM_SYMBOL(root));
 487 }
 488
 489 TMSymbol *tm_symbol_tree_update(TMSymbol *root, GPtrArray *tags)
 490 {
 491         if (root)
 492                 tm_symbol_free(root);
 493         if ((tags) && (tags->len > 0))
 494                 return tm_symbol_tree_new(tags);
 495         else
 496                 return NULL;
 497 }