tagmanager/src/tm_tag.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 <stdlib.h>
  11 #include <string.h>
  12 #include <glib-object.h>
  13
  14 #include "general.h"
  15 #include "entry.h"
  16 #include "parse.h"
  17 #include "read.h"
  18 #define LIBCTAGS_DEFINED
  19 #include "tm_tag.h"
  20
  21
  22 #define TAG_NEW(T)      ((T) = g_slice_new0(TMTag))
  23 #define TAG_FREE(T)     g_slice_free(TMTag, (T))
  24
  25
  26 #ifdef DEBUG_TAG_REFS
  27
  28 static GHashTable *alive_tags = NULL;
  29
  30 static void foreach_tags_log(gpointer key, gpointer value, gpointer data)
  31 {
  32         gsize *ref_count = data;
  33         const TMTag *tag = value;
  34
  35         *ref_count += (gsize) tag->refcount;
  36         g_debug("Leaked TMTag (%d refs): %s", tag->refcount, tag->name);
  37 }
  38
  39 static void log_refs_at_exit(void)
  40 {
  41         gsize ref_count = 0;
  42
  43         g_hash_table_foreach(alive_tags, foreach_tags_log, &ref_count);
  44         g_debug("TMTag references left at exit: %lu", ref_count);
  45 }
  46
  47 static TMTag *log_tag_new(void)
  48 {
  49         TMTag *tag;
  50
  51         if (! alive_tags)
  52         {
  53                 alive_tags = g_hash_table_new(g_direct_hash, g_direct_equal);
  54                 atexit(log_refs_at_exit);
  55         }
  56         TAG_NEW(tag);
  57         g_hash_table_insert(alive_tags, tag, tag);
  58
  59         return tag;
  60 }
  61
  62 static void log_tag_free(TMTag *tag)
  63 {
  64         g_return_if_fail(alive_tags != NULL);
  65
  66         if (! g_hash_table_remove(alive_tags, tag)) {
  67                 g_critical("Freeing invalid TMTag pointer %p", (void *) tag);
  68         } else {
  69                 TAG_FREE(tag);
  70         }
  71 }
  72
  73 #undef TAG_NEW
  74 #undef TAG_FREE
  75 #define TAG_NEW(T)      ((T) = log_tag_new())
  76 #define TAG_FREE(T)     log_tag_free(T)
  77
  78 #endif /* DEBUG_TAG_REFS */
  79
  80
  81 /* Note: To preserve binary compatibility, it is very important
  82         that you only *append* to this list ! */
  83 enum
  84 {
  85         TA_NAME = 200,
  86         TA_LINE,
  87         TA_LOCAL,
  88         TA_POS, /* Obsolete */
  89         TA_TYPE,
  90         TA_ARGLIST,
  91         TA_SCOPE,
  92         TA_VARTYPE,
  93         TA_INHERITS,
  94         TA_TIME,
  95         TA_ACCESS,
  96         TA_IMPL,
  97         TA_LANG,
  98         TA_INACTIVE, /* Obsolete */
  99         TA_POINTER
 100 };
 101
 102 static guint *s_sort_attrs = NULL;
 103 static gboolean s_partial = FALSE;
 104
 105 static const char *s_tag_type_names[] = {
 106         "class", /* classes */
 107         "enum", /* enumeration names */
 108         "enumerator", /* enumerators (values inside an enumeration) */
 109         "externvar", /* external variable declarations */
 110         "field", /* fields */
 111         "function", /*  function definitions */
 112         "interface", /* interfaces */
 113         "macro", /* macro definitions */
 114         "member", /* class, struct, and union members */
 115         "method", /* methods */
 116         "namespace", /* namespaces */
 117         "package", /* packages */
 118         "prototype", /* function prototypes */
 119         "struct", /* structure names */
 120         "typedef", /* typedefs */
 121         "union", /* union names */
 122         "variable", /* variable definitions */
 123         "other" /* Other tag type (non C/C++/Java) */
 124 };
 125
 126 static int s_tag_types[] = {
 127         tm_tag_class_t,
 128         tm_tag_enum_t,
 129         tm_tag_enumerator_t,
 130         tm_tag_externvar_t,
 131         tm_tag_field_t,
 132         tm_tag_function_t,
 133         tm_tag_interface_t,
 134         tm_tag_macro_t,
 135         tm_tag_member_t,
 136         tm_tag_method_t,
 137         tm_tag_namespace_t,
 138         tm_tag_package_t,
 139         tm_tag_prototype_t,
 140         tm_tag_struct_t,
 141         tm_tag_typedef_t,
 142         tm_tag_union_t,
 143         tm_tag_variable_t,
 144         tm_tag_other_t
 145 };
 146
 147 /* Gets the GType for a TMTag */
 148 GType tm_tag_get_type(void)
 149 {
 150         static GType gtype = 0;
 151         if (G_UNLIKELY (gtype == 0))
 152         {
 153                 gtype = g_boxed_type_register_static("TMTag", (GBoxedCopyFunc)tm_tag_ref,
 154                                                                                          (GBoxedFreeFunc)tm_tag_unref);
 155         }
 156         return gtype;
 157 }
 158
 159 static int get_tag_type(const char *tag_name)
 160 {
 161         unsigned int i;
 162         int cmp;
 163         g_return_val_if_fail(tag_name, 0);
 164         for (i=0; i < sizeof(s_tag_type_names)/sizeof(char *); ++i)
 165         {
 166                 cmp = strcmp(tag_name, s_tag_type_names[i]);
 167                 if (0 == cmp)
 168                         return s_tag_types[i];
 169                 else if (cmp < 0)
 170                         break;
 171         }
 172         /* other is not checked above as it is last, not sorted alphabetically */
 173         if (strcmp(tag_name, "other") == 0)
 174                 return tm_tag_other_t;
 175 #ifdef TM_DEBUG
 176         fprintf(stderr, "Unknown tag type %s\n", tag_name);
 177 #endif
 178         return tm_tag_undef_t;
 179 }
 180
 181 static char get_tag_impl(const char *impl)
 182 {
 183         if ((0 == strcmp("virtual", impl))
 184          || (0 == strcmp("pure virtual", impl)))
 185                 return TAG_IMPL_VIRTUAL;
 186
 187 #ifdef TM_DEBUG
 188                 g_warning("Unknown implementation %s", impl);
 189 #endif
 190         return TAG_IMPL_UNKNOWN;
 191 }
 192
 193 static char get_tag_access(const char *access)
 194 {
 195         if (0 == strcmp("public", access))
 196                 return TAG_ACCESS_PUBLIC;
 197         else if (0 == strcmp("protected", access))
 198                 return TAG_ACCESS_PROTECTED;
 199         else if (0 == strcmp("private", access))
 200                 return TAG_ACCESS_PRIVATE;
 201         else if (0 == strcmp("friend", access))
 202                 return TAG_ACCESS_FRIEND;
 203         else if (0 == strcmp("default", access))
 204                 return TAG_ACCESS_DEFAULT;
 205
 206 #ifdef TM_DEBUG
 207         g_warning("Unknown access type %s", access);
 208 #endif
 209         return TAG_ACCESS_UNKNOWN;
 210 }
 211
 212 /*
 213  Initializes a TMTag structure with information from a tagEntryInfo struct
 214  used by the ctags parsers. Note that the TMTag structure must be malloc()ed
 215  before calling this function. This function is called by tm_tag_new() - you
 216  should not need to call this directly.
 217  @param tag The TMTag structure to initialize
 218  @param file Pointer to a TMSourceFile struct (it is assigned to the file member)
 219  @param tag_entry Tag information gathered by the ctags parser
 220  @return TRUE on success, FALSE on failure
 221 */
 222 static gboolean tm_tag_init(TMTag *tag, TMSourceFile *file, const tagEntryInfo *tag_entry)
 223 {
 224         tag->refcount = 1;
 225         if (NULL == tag_entry)
 226         {
 227                 return FALSE;
 228         }
 229         else
 230         {
 231                 /* This is a normal tag entry */
 232                 if (NULL == tag_entry->name)
 233                         return FALSE;
 234                 tag->name = g_strdup(tag_entry->name);
 235                 tag->type = get_tag_type(tag_entry->kindName);
 236                 tag->local = tag_entry->isFileScope;
 237                 tag->pointerOrder = 0;  /* backward compatibility (use var_type instead) */
 238                 tag->line = tag_entry->lineNumber;
 239                 if (NULL != tag_entry->extensionFields.arglist)
 240                         tag->arglist = g_strdup(tag_entry->extensionFields.arglist);
 241                 if ((NULL != tag_entry->extensionFields.scope[1]) &&
 242                         (isalpha(tag_entry->extensionFields.scope[1][0]) ||
 243                          tag_entry->extensionFields.scope[1][0] == '_' ||
 244                          tag_entry->extensionFields.scope[1][0] == '$'))
 245                         tag->scope = g_strdup(tag_entry->extensionFields.scope[1]);
 246                 if (tag_entry->extensionFields.inheritance != NULL)
 247                         tag->inheritance = g_strdup(tag_entry->extensionFields.inheritance);
 248                 if (tag_entry->extensionFields.varType != NULL)
 249                         tag->var_type = g_strdup(tag_entry->extensionFields.varType);
 250                 if (tag_entry->extensionFields.access != NULL)
 251                         tag->access = get_tag_access(tag_entry->extensionFields.access);
 252                 if (tag_entry->extensionFields.implementation != NULL)
 253                         tag->impl = get_tag_impl(tag_entry->extensionFields.implementation);
 254                 if ((tm_tag_macro_t == tag->type) && (NULL != tag->arglist))
 255                         tag->type = tm_tag_macro_with_arg_t;
 256                 tag->file = file;
 257                 tag->lang = file->lang;
 258                 return TRUE;
 259         }
 260 }
 261
 262 /*
 263  Creates a new tag structure from a tagEntryInfo pointer and a TMSOurceFile pointer
 264  and returns a pointer to it.
 265  @param file - Pointer to the TMSourceFile structure containing the tag
 266  @param tag_entry Contains tag information generated by ctags
 267  @return the new TMTag structure. This should be free()-ed using tm_tag_free()
 268 */
 269 TMTag *tm_tag_new(TMSourceFile *file, const tagEntryInfo *tag_entry)
 270 {
 271         TMTag *tag;
 272
 273         TAG_NEW(tag);
 274         if (FALSE == tm_tag_init(tag, file, tag_entry))
 275         {
 276                 TAG_FREE(tag);
 277                 return NULL;
 278         }
 279         return tag;
 280 }
 281
 282 /*
 283  Initializes an already malloc()ed TMTag structure by reading a tag entry
 284  line from a file. The structure should be allocated beforehand.
 285  @param tag The TMTag structure to populate
 286  @param file The TMSourceFile struct (assigned to the file member)
 287  @param fp FILE pointer from where the tag line is read
 288  @return TRUE on success, FALSE on FAILURE
 289 */
 290 static gboolean tm_tag_init_from_file(TMTag *tag, TMSourceFile *file, FILE *fp)
 291 {
 292         guchar buf[BUFSIZ];
 293         guchar *start, *end;
 294         gboolean status;
 295         guchar changed_char = TA_NAME;
 296
 297         tag->refcount = 1;
 298         if ((NULL == fgets((gchar*)buf, BUFSIZ, fp)) || ('\0' == *buf))
 299                 return FALSE;
 300         for (start = end = buf, status = TRUE; (TRUE == status); start = end, ++ end)
 301         {
 302                 while ((*end < TA_NAME) && (*end != '\0') && (*end != '\n'))
 303                         ++ end;
 304                 if (('\0' == *end) || ('\n' == *end))
 305                         status = FALSE;
 306                 changed_char = *end;
 307                 *end = '\0';
 308                 if (NULL == tag->name)
 309                 {
 310                         if (!isprint(*start))
 311                                 return FALSE;
 312                         else
 313                                 tag->name = g_strdup((gchar*)start);
 314                 }
 315                 else
 316                 {
 317                         switch (*start)
 318                         {
 319                                 case TA_LINE:
 320                                         tag->line = atol((gchar*)start + 1);
 321                                         break;
 322                                 case TA_LOCAL:
 323                                         tag->local = atoi((gchar*)start + 1);
 324                                         break;
 325                                 case TA_TYPE:
 326                                         tag->type = (TMTagType) atoi((gchar*)start + 1);
 327                                         break;
 328                                 case TA_ARGLIST:
 329                                         tag->arglist = g_strdup((gchar*)start + 1);
 330                                         break;
 331                                 case TA_SCOPE:
 332                                         tag->scope = g_strdup((gchar*)start + 1);
 333                                         break;
 334                                 case TA_POINTER:
 335                                         tag->pointerOrder = atoi((gchar*)start + 1);
 336                                         break;
 337                                 case TA_VARTYPE:
 338                                         tag->var_type = g_strdup((gchar*)start + 1);
 339                                         break;
 340                                 case TA_INHERITS:
 341                                         tag->inheritance = g_strdup((gchar*)start + 1);
 342                                         break;
 343                                 case TA_TIME:  /* Obsolete */
 344                                         break;
 345                                 case TA_LANG:  /* Obsolete */
 346                                         break;
 347                                 case TA_INACTIVE:  /* Obsolete */
 348                                         break;
 349                                 case TA_ACCESS:
 350                                         tag->access = *(start + 1);
 351                                         break;
 352                                 case TA_IMPL:
 353                                         tag->impl = *(start + 1);
 354                                         break;
 355                                 default:
 356 #ifdef GEANY_DEBUG
 357                                         g_warning("Unknown attribute %s", start + 1);
 358 #endif
 359                                         break;
 360                         }
 361                 }
 362                 *end = changed_char;
 363         }
 364         if (NULL == tag->name)
 365                 return FALSE;
 366         tag->file = file;
 367         return TRUE;
 368 }
 369
 370 /* alternative parser for Pascal and LaTeX global tags files with the following format
 371  * tagname|return value|arglist|description\n */
 372 static gboolean tm_tag_init_from_file_alt(TMTag *tag, TMSourceFile *file, FILE *fp)
 373 {
 374         guchar buf[BUFSIZ];
 375         guchar *start, *end;
 376         gboolean status;
 377         /*guchar changed_char = TA_NAME;*/
 378
 379         tag->refcount = 1;
 380         if ((NULL == fgets((gchar*)buf, BUFSIZ, fp)) || ('\0' == *buf))
 381                 return FALSE;
 382         {
 383                 gchar **fields;
 384                 guint field_len;
 385                 for (start = end = buf, status = TRUE; (TRUE == status); start = end, ++ end)
 386                 {
 387                         while ((*end < TA_NAME) && (*end != '\0') && (*end != '\n'))
 388                                 ++ end;
 389                         if (('\0' == *end) || ('\n' == *end))
 390                                 status = FALSE;
 391                         /*changed_char = *end;*/
 392                         *end = '\0';
 393                         if (NULL == tag->name && !isprint(*start))
 394                                         return FALSE;
 395
 396                         fields = g_strsplit((gchar*)start, "|", -1);
 397                         field_len = g_strv_length(fields);
 398
 399                         if (field_len >= 1) tag->name = g_strdup(fields[0]);
 400                         else tag->name = NULL;
 401                         if (field_len >= 2 && fields[1] != NULL) tag->var_type = g_strdup(fields[1]);
 402                         if (field_len >= 3 && fields[2] != NULL) tag->arglist = g_strdup(fields[2]);
 403                         tag->type = tm_tag_prototype_t;
 404                         g_strfreev(fields);
 405                 }
 406         }
 407
 408         if (NULL == tag->name)
 409                 return FALSE;
 410         tag->file = file;
 411         return TRUE;
 412 }
 413
 414 /*
 415  Same as tm_tag_init_from_file(), but parsing CTags tag file format
 416  (http://ctags.sourceforge.net/FORMAT)
 417 */
 418 static gboolean tm_tag_init_from_file_ctags(TMTag *tag, TMSourceFile *file, FILE *fp)
 419 {
 420         gchar buf[BUFSIZ];
 421         gchar *p, *tab;
 422
 423         tag->refcount = 1;
 424         tag->type = tm_tag_function_t; /* default type is function if no kind is specified */
 425         do
 426         {
 427                 if ((NULL == fgets(buf, BUFSIZ, fp)) || ('\0' == *buf))
 428                         return FALSE;
 429         }
 430         while (strncmp(buf, "!_TAG_", 6) == 0); /* skip !_TAG_ lines */
 431
 432         p = buf;
 433
 434         /* tag name */
 435         if (! (tab = strchr(p, '\t')) || p == tab)
 436                 return FALSE;
 437         tag->name = g_strndup(p, (gsize)(tab - p));
 438         p = tab + 1;
 439
 440         /* tagfile, unused */
 441         if (! (tab = strchr(p, '\t')))
 442         {
 443                 g_free(tag->name);
 444                 tag->name = NULL;
 445                 return FALSE;
 446         }
 447         p = tab + 1;
 448         /* Ex command, unused */
 449         if (*p == '/' || *p == '?')
 450         {
 451                 gchar c = *p;
 452                 for (++p; *p && *p != c; p++)
 453                 {
 454                         if (*p == '\\' && p[1])
 455                                 p++;
 456                 }
 457         }
 458         else /* assume a line */
 459                 tag->line = atol(p);
 460         tab = strstr(p, ";\"");
 461         /* read extension fields */
 462         if (tab)
 463         {
 464                 p = tab + 2;
 465                 while (*p && *p != '\n' && *p != '\r')
 466                 {
 467                         gchar *end;
 468                         const gchar *key, *value = NULL;
 469
 470                         /* skip leading tabulations */
 471                         while (*p && *p == '\t') p++;
 472                         /* find the separator (:) and end (\t) */
 473                         key = end = p;
 474                         while (*end && *end != '\t' && *end != '\n' && *end != '\r')
 475                         {
 476                                 if (*end == ':' && ! value)
 477                                 {
 478                                         *end = 0; /* terminate the key */
 479                                         value = end + 1;
 480                                 }
 481                                 end++;
 482                         }
 483                         /* move p paste the so we won't stop parsing by setting *end=0 below */
 484                         p = *end ? end + 1 : end;
 485                         *end = 0; /* terminate the value (or key if no value) */
 486
 487                         if (! value || 0 == strcmp(key, "kind")) /* tag kind */
 488                         {
 489                                 const gchar *kind = value ? value : key;
 490
 491                                 if (kind[0] && kind[1])
 492                                         tag->type = get_tag_type(kind);
 493                                 else
 494                                 {
 495                                         switch (*kind)
 496                                         {
 497                                                 case 'c': tag->type = tm_tag_class_t; break;
 498                                                 case 'd': tag->type = tm_tag_macro_t; break;
 499                                                 case 'e': tag->type = tm_tag_enumerator_t; break;
 500                                                 case 'F': tag->type = tm_tag_other_t; break;  /* Obsolete */
 501                                                 case 'f': tag->type = tm_tag_function_t; break;
 502                                                 case 'g': tag->type = tm_tag_enum_t; break;
 503                                                 case 'I': tag->type = tm_tag_class_t; break;
 504                                                 case 'i': tag->type = tm_tag_interface_t; break;
 505                                                 case 'l': tag->type = tm_tag_variable_t; break;
 506                                                 case 'M': tag->type = tm_tag_macro_t; break;
 507                                                 case 'm': tag->type = tm_tag_member_t; break;
 508                                                 case 'n': tag->type = tm_tag_namespace_t; break;
 509                                                 case 'P': tag->type = tm_tag_package_t; break;
 510                                                 case 'p': tag->type = tm_tag_prototype_t; break;
 511                                                 case 's': tag->type = tm_tag_struct_t; break;
 512                                                 case 't': tag->type = tm_tag_typedef_t; break;
 513                                                 case 'u': tag->type = tm_tag_union_t; break;
 514                                                 case 'v': tag->type = tm_tag_variable_t; break;
 515                                                 case 'x': tag->type = tm_tag_externvar_t; break;
 516                                                 default:
 517 #ifdef TM_DEBUG
 518                                                         g_warning("Unknown tag kind %c", *kind);
 519 #endif
 520                                                         tag->type = tm_tag_other_t; break;
 521                                         }
 522                                 }
 523                         }
 524                         else if (0 == strcmp(key, "inherits")) /* comma-separated list of classes this class inherits from */
 525                         {
 526                                 g_free(tag->inheritance);
 527                                 tag->inheritance = g_strdup(value);
 528                         }
 529                         else if (0 == strcmp(key, "implementation")) /* implementation limit */
 530                                 tag->impl = get_tag_impl(value);
 531                         else if (0 == strcmp(key, "line")) /* line */
 532                                 tag->line = atol(value);
 533                         else if (0 == strcmp(key, "access")) /* access */
 534                                 tag->access = get_tag_access(value);
 535                         else if (0 == strcmp(key, "class") ||
 536                                          0 == strcmp(key, "enum") ||
 537                                          0 == strcmp(key, "function") ||
 538                                          0 == strcmp(key, "struct") ||
 539                                          0 == strcmp(key, "union")) /* Name of the class/enum/function/struct/union in which this tag is a member */
 540                         {
 541                                 g_free(tag->scope);
 542                                 tag->scope = g_strdup(value);
 543                         }
 544                         else if (0 == strcmp(key, "file")) /* static (local) tag */
 545                                 tag->local = TRUE;
 546                         else if (0 == strcmp(key, "signature")) /* arglist */
 547                         {
 548                                 g_free(tag->arglist);
 549                                 tag->arglist = g_strdup(value);
 550                         }
 551                 }
 552         }
 553
 554         tag->file = file;
 555         return TRUE;
 556 }
 557
 558 /*
 559  Same as tm_tag_new() except that the tag attributes are read from file.
 560  @param mode langType to use for the tag.
 561 */
 562 TMTag *tm_tag_new_from_file(TMSourceFile *file, FILE *fp, gint mode, TMFileFormat format)
 563 {
 564         TMTag *tag;
 565         gboolean result = FALSE;
 566
 567         TAG_NEW(tag);
 568
 569         switch (format)
 570         {
 571                 case TM_FILE_FORMAT_TAGMANAGER:
 572                         result = tm_tag_init_from_file(tag, file, fp);
 573                         break;
 574                 case TM_FILE_FORMAT_PIPE:
 575                         result = tm_tag_init_from_file_alt(tag, file, fp);
 576                         break;
 577                 case TM_FILE_FORMAT_CTAGS:
 578                         result = tm_tag_init_from_file_ctags(tag, file, fp);
 579                         break;
 580         }
 581
 582         if (! result)
 583         {
 584                 TAG_FREE(tag);
 585                 return NULL;
 586         }
 587         tag->lang = mode;
 588         return tag;
 589 }
 590
 591 /*
 592  Writes tag information to the given FILE *.
 593  @param tag The tag information to write.
 594  @param file FILE pointer to which the tag information is written.
 595  @param attrs Attributes to be written (bitmask).
 596  @return TRUE on success, FALSE on failure.
 597 */
 598 gboolean tm_tag_write(TMTag *tag, FILE *fp, guint attrs)
 599 {
 600         fprintf(fp, "%s", tag->name);
 601         if (attrs & tm_tag_attr_type_t)
 602                 fprintf(fp, "%c%d", TA_TYPE, tag->type);
 603         if ((attrs & tm_tag_attr_arglist_t) && (NULL != tag->arglist))
 604                 fprintf(fp, "%c%s", TA_ARGLIST, tag->arglist);
 605         if (attrs & tm_tag_attr_line_t)
 606                 fprintf(fp, "%c%ld", TA_LINE, tag->line);
 607         if (attrs & tm_tag_attr_local_t)
 608                 fprintf(fp, "%c%d", TA_LOCAL, tag->local);
 609         if ((attrs & tm_tag_attr_scope_t) && (NULL != tag->scope))
 610                 fprintf(fp, "%c%s", TA_SCOPE, tag->scope);
 611         if ((attrs & tm_tag_attr_inheritance_t) && (NULL != tag->inheritance))
 612                 fprintf(fp, "%c%s", TA_INHERITS, tag->inheritance);
 613         if (attrs & tm_tag_attr_pointer_t)
 614                 fprintf(fp, "%c%d", TA_POINTER, tag->pointerOrder);
 615         if ((attrs & tm_tag_attr_vartype_t) && (NULL != tag->var_type))
 616                 fprintf(fp, "%c%s", TA_VARTYPE, tag->var_type);
 617         if ((attrs & tm_tag_attr_access_t) && (TAG_ACCESS_UNKNOWN != tag->access))
 618                 fprintf(fp, "%c%c", TA_ACCESS, tag->access);
 619         if ((attrs & tm_tag_attr_impl_t) && (TAG_IMPL_UNKNOWN != tag->impl))
 620                 fprintf(fp, "%c%c", TA_IMPL, tag->impl);
 621
 622         if (fprintf(fp, "\n"))
 623                 return TRUE;
 624         else
 625                 return FALSE;
 626 }
 627
 628 /*
 629  Destroys a TMTag structure, i.e. frees all elements except the tag itself.
 630  @param tag The TMTag structure to destroy
 631  @see tm_tag_free()
 632 */
 633 static void tm_tag_destroy(TMTag *tag)
 634 {
 635         g_free(tag->name);
 636         g_free(tag->arglist);
 637         g_free(tag->scope);
 638         g_free(tag->inheritance);
 639         g_free(tag->var_type);
 640 }
 641
 642
 643 /*
 644  Drops a reference from a TMTag. If the reference count reaches 0, this function
 645  destroys all data in the tag and frees the tag structure as well.
 646  @param tag Pointer to a TMTag structure
 647 */
 648 void tm_tag_unref(TMTag *tag)
 649 {
 650         /* be NULL-proof because tm_tag_free() was NULL-proof and we indent to be a
 651          * drop-in replacment of it */
 652         if (NULL != tag && g_atomic_int_dec_and_test(&tag->refcount))
 653         {
 654                 tm_tag_destroy(tag);
 655                 TAG_FREE(tag);
 656         }
 657 }
 658
 659 /*
 660  Adds a reference to a TMTag.
 661  @param tag Pointer to a TMTag structure
 662  @return the passed-in TMTag
 663 */
 664 TMTag *tm_tag_ref(TMTag *tag)
 665 {
 666         g_atomic_int_inc(&tag->refcount);
 667         return tag;
 668 }
 669
 670 /*
 671  Inbuilt tag comparison function. Do not call directly since it needs some
 672  static variables to be set. Always use tm_tags_sort() and tm_tags_dedup()
 673  instead.
 674 */
 675 static int tm_tag_compare(const void *ptr1, const void *ptr2)
 676 {
 677         unsigned int *sort_attr;
 678         int returnval = 0;
 679         TMTag *t1 = *((TMTag **) ptr1);
 680         TMTag *t2 = *((TMTag **) ptr2);
 681
 682         if ((NULL == t1) || (NULL == t2))
 683         {
 684                 g_warning("Found NULL tag");
 685                 return t2 - t1;
 686         }
 687         if (NULL == s_sort_attrs)
 688         {
 689                 if (s_partial)
 690                         return strncmp(FALLBACK(t1->name, ""), FALLBACK(t2->name, ""), strlen(FALLBACK(t1->name, "")));
 691                 else
 692                         return strcmp(FALLBACK(t1->name, ""), FALLBACK(t2->name, ""));
 693         }
 694
 695         for (sort_attr = s_sort_attrs; *sort_attr != tm_tag_attr_none_t; ++ sort_attr)
 696         {
 697                 switch (*sort_attr)
 698                 {
 699                         case tm_tag_attr_name_t:
 700                                 if (s_partial)
 701                                         returnval = strncmp(FALLBACK(t1->name, ""), FALLBACK(t2->name, ""), strlen(FALLBACK(t1->name, "")));
 702                                 else
 703                                         returnval = strcmp(FALLBACK(t1->name, ""), FALLBACK(t2->name, ""));
 704                                 if (0 != returnval)
 705                                         return returnval;
 706                                 break;
 707                         case tm_tag_attr_type_t:
 708                                 if (0 != (returnval = (t1->type - t2->type)))
 709                                         return returnval;
 710                                 break;
 711                         case tm_tag_attr_file_t:
 712                                 if (0 != (returnval = (t1->file - t2->file)))
 713                                         return returnval;
 714                                 break;
 715                         case tm_tag_attr_scope_t:
 716                                 if (0 != (returnval = strcmp(FALLBACK(t1->scope, ""), FALLBACK(t2->scope, ""))))
 717                                         return returnval;
 718                                 break;
 719                         case tm_tag_attr_arglist_t:
 720                                 if (0 != (returnval = strcmp(FALLBACK(t1->arglist, ""), FALLBACK(t2->arglist, ""))))
 721                                 {
 722                                         int line_diff = (t1->line - t2->line);
 723
 724                                         return line_diff ? line_diff : returnval;
 725                                 }
 726                                 break;
 727                         case tm_tag_attr_vartype_t:
 728                                 if (0 != (returnval = strcmp(FALLBACK(t1->var_type, ""), FALLBACK(t2->var_type, ""))))
 729                                         return returnval;
 730                                 break;
 731                         case tm_tag_attr_line_t:
 732                                 if (0 != (returnval = (t1->line - t2->line)))
 733                                         return returnval;
 734                                 break;
 735                 }
 736         }
 737         return returnval;
 738 }
 739
 740 /*
 741  Removes NULL tag entries from an array of tags. Called after tm_tags_dedup() since
 742  this function substitutes duplicate entries with NULL
 743  @param tags_array Array of tags to dedup
 744  @return TRUE on success, FALSE on failure
 745 */
 746 gboolean tm_tags_prune(GPtrArray *tags_array)
 747 {
 748         guint i, count;
 749         for (i=0, count = 0; i < tags_array->len; ++i)
 750         {
 751                 if (NULL != tags_array->pdata[i])
 752                         tags_array->pdata[count++] = tags_array->pdata[i];
 753         }
 754         tags_array->len = count;
 755         return TRUE;
 756 }
 757
 758 /*
 759  Deduplicates an array on tags using the inbuilt comparison function based on
 760  the attributes specified. Called by tm_tags_sort() when dedup is TRUE.
 761  @param tags_array Array of tags to dedup.
 762  @param sort_attributes Attributes the array is sorted on. They will be deduped
 763  on the same criteria.
 764  @return TRUE on success, FALSE on failure
 765 */
 766 gboolean tm_tags_dedup(GPtrArray *tags_array, TMTagAttrType *sort_attributes)
 767 {
 768         guint i;
 769
 770         if ((!tags_array) || (!tags_array->len))
 771                 return TRUE;
 772         s_sort_attrs = sort_attributes;
 773         s_partial = FALSE;
 774         for (i = 1; i < tags_array->len; ++i)
 775         {
 776                 if (0 == tm_tag_compare(&(tags_array->pdata[i - 1]), &(tags_array->pdata[i])))
 777                 {
 778                         tags_array->pdata[i-1] = NULL;
 779                 }
 780         }
 781         tm_tags_prune(tags_array);
 782         return TRUE;
 783 }
 784
 785 /*
 786  Sort an array of tags on the specified attribuites using the inbuilt comparison
 787  function.
 788  @param tags_array The array of tags to be sorted
 789  @param sort_attributes Attributes to be sorted on (int array terminated by 0)
 790  @param dedup Whether to deduplicate the sorted array
 791  @return TRUE on success, FALSE on failure
 792 */
 793 gboolean tm_tags_sort(GPtrArray *tags_array, TMTagAttrType *sort_attributes, gboolean dedup)
 794 {
 795         if ((!tags_array) || (!tags_array->len))
 796                 return TRUE;
 797         s_sort_attrs = sort_attributes;
 798         s_partial = FALSE;
 799         qsort(tags_array->pdata, tags_array->len, sizeof(gpointer), tm_tag_compare);
 800         s_sort_attrs = NULL;
 801         if (dedup)
 802                 tm_tags_dedup(tags_array, sort_attributes);
 803         return TRUE;
 804 }
 805
 806 GPtrArray *tm_tags_remove_file_tags(TMSourceFile *source_file, GPtrArray *tags_array)
 807 {
 808         guint i;
 809         for (i = 0; i < tags_array->len; i++)
 810         {
 811                 TMTag *tag = tags_array->pdata[i];
 812
 813                 if (tag != NULL && tag->file == source_file)
 814                         tags_array->pdata[i] = NULL;
 815         }
 816         tm_tags_prune(tags_array);
 817 }
 818
 819 /* Optimized merge sort for merging sorted values from one array to another
 820  * where one of the arrays is much smaller than the other.
 821  * The merge complexity depends mostly on the size of the small array
 822  * and is almost independent of the size of the big array.
 823  * In addition, get rid of the duplicates (if both big_array and small_array are duplicate-free). */
 824 static GPtrArray *merge(GPtrArray *big_array, GPtrArray *small_array) {
 825         guint i1 = 0;  /* index to big_array */
 826         guint i2 = 0;  /* index to small_array */
 827         guint initial_step;
 828         guint step;
 829         GPtrArray *res_array = g_ptr_array_sized_new(big_array->len + small_array->len);
 830 #ifdef TM_DEBUG
 831         guint cmpnum = 0;
 832 #endif
 833
 834         /* swap the arrays if len(small) > len(big) */
 835         if (small_array->len > big_array->len)
 836         {
 837                 GPtrArray *tmp = small_array;
 838                 small_array = big_array;
 839                 big_array = tmp;
 840         }
 841
 842         /* on average, we are merging a value from small_array every
 843          * len(big_array) / len(small_array) values - good approximation for fast jump
 844          * step size */
 845         initial_step = (small_array->len > 0) ? big_array->len / small_array->len : 1;
 846         initial_step = initial_step > 4 ? initial_step : 1;
 847         step = initial_step;
 848
 849         while (i1 < big_array->len && i2 < small_array->len)
 850         {
 851                 gint cmpval;
 852                 gpointer val1 = big_array->pdata[i1];
 853                 gpointer val2 = small_array->pdata[i2];
 854
 855                 if (step > 4)  /* fast path start */
 856                 {
 857                         guint j1 = (i1 + step < big_array->len) ? i1 + step : big_array->len - 1;
 858
 859                         val1 = big_array->pdata[j1];
 860 #ifdef TM_DEBUG
 861                         cmpnum++;
 862 #endif
 863                         /* if the value in big_array after making the big step is still smaller
 864                          * than the value in small_array, we can copy all the values inbetween
 865                          * into the result without making expensive string comparisons */
 866                         if (tm_tag_compare(&val1, &val2) < 0)
 867                         {
 868                                 while (i1 <= j1)
 869                                 {
 870                                         val1 = big_array->pdata[i1];
 871                                         g_ptr_array_add(res_array, val1);
 872                                         i1++;
 873                                 }
 874                                 continue;
 875                         }
 876                         else
 877                         {
 878                                 /* lower the step and try again */
 879                                 step /= 2;
 880                                 continue;
 881                         }
 882                 }  /* fast path end */
 883
 884 #ifdef TM_DEBUG
 885                 cmpnum++;
 886 #endif
 887                 cmpval = tm_tag_compare(&val1, &val2);
 888                 if (cmpval < 0)
 889                 {
 890                         g_ptr_array_add(res_array, val1);
 891                         i1++;
 892                 }
 893                 else
 894                 {
 895                         g_ptr_array_add(res_array, val2);
 896                         i2++;
 897                         /* value from small_array gets merged - reset the step size */
 898                         step = initial_step;
 899                         if (cmpval == 0)
 900                                 i1++;  /* remove the duplicate, keep just the newly merged value */
 901                 }
 902         }
 903
 904         /* end of one of the arrays reached - copy the rest from the other array */
 905         while (i1 < big_array->len)
 906                 g_ptr_array_add(res_array, big_array->pdata[i1++]);
 907         while (i2 < small_array->len)
 908                 g_ptr_array_add(res_array, small_array->pdata[i2++]);
 909
 910 #ifdef TM_DEBUG
 911         printf("cmpnums: %u\n", cmpnum);
 912         printf("total tags: %u\n", big_array->len);
 913         printf("merged tags: %u\n\n", small_array->len);
 914 #endif
 915
 916         return res_array;
 917 }
 918
 919 GPtrArray *tm_tags_merge(GPtrArray *big_array, GPtrArray *small_array, TMTagAttrType *sort_attributes)
 920 {
 921         GPtrArray *res_array;
 922
 923         s_sort_attrs = sort_attributes;
 924         s_partial = FALSE;
 925         res_array = merge(big_array, small_array);
 926         s_sort_attrs = NULL;
 927         return res_array;
 928 }
 929
 930 /*
 931  This function will extract the tags of the specified types from an array of tags.
 932  The returned value is a GPtrArray which should be free-d with a call to
 933  g_ptr_array_free(array, TRUE). However, do not free the tags themselves since they
 934  are not duplicated.
 935  @param tags_array The original array of tags
 936  @param tag_types - The tag types to extract. Can be a bitmask. For example, passing
 937  (tm_tag_typedef_t | tm_tag_struct_t) will extract all typedefs and structures from
 938  the original array.
 939  @return an array of tags (NULL on failure)
 940 */
 941 GPtrArray *tm_tags_extract(GPtrArray *tags_array, guint tag_types)
 942 {
 943         GPtrArray *new_tags;
 944         guint i;
 945         if (NULL == tags_array)
 946                 return NULL;
 947         new_tags = g_ptr_array_new();
 948         for (i=0; i < tags_array->len; ++i)
 949         {
 950                 if (NULL != tags_array->pdata[i])
 951                 {
 952                         if (tag_types & (((TMTag *) tags_array->pdata[i])->type))
 953                                 g_ptr_array_add(new_tags, tags_array->pdata[i]);
 954                 }
 955         }
 956         return new_tags;
 957 }
 958
 959 /*
 960  Completely frees an array of tags.
 961  @param tags_array Array of tags to be freed.
 962  @param free_array Whether the GptrArray is to be freed as well.
 963 */
 964 void tm_tags_array_free(GPtrArray *tags_array, gboolean free_all)
 965 {
 966         if (tags_array)
 967         {
 968                 guint i;
 969                 for (i = 0; i < tags_array->len; ++i)
 970                         tm_tag_unref(tags_array->pdata[i]);
 971                 if (free_all)
 972                         g_ptr_array_free(tags_array, TRUE);
 973                 else
 974                         g_ptr_array_set_size(tags_array, 0);
 975         }
 976 }
 977
 978 static TMTag **tags_search(const GPtrArray *tags_array, TMTag *tag, gboolean partial,
 979                 gboolean tags_array_sorted)
 980 {
 981         if (tags_array_sorted)
 982         {       /* fast binary search on sorted tags array */
 983                 return (TMTag **) bsearch(&tag, tags_array->pdata, tags_array->len
 984                   , sizeof(gpointer), tm_tag_compare);
 985         }
 986         else
 987         {       /* the slow way: linear search (to make it a bit faster, search reverse assuming
 988                  * that the tag to search was added recently) */
 989                 int i;
 990                 TMTag **t;
 991                 for (i = tags_array->len - 1; i >= 0; i--)
 992                 {
 993                         t = (TMTag **) &tags_array->pdata[i];
 994                         if (0 == tm_tag_compare(&tag, t))
 995                                 return t;
 996                 }
 997         }
 998         return NULL;
 999 }
1000
1001 /*
1002  Returns a pointer to the position of the first matching tag in a (sorted) tags array.
1003  The passed array of tags should be already sorted by name for optimal performance. If
1004  \c tags_array_sorted is set to FALSE, it may be unsorted but the lookup will be slower.
1005  @param tags_array Tag array (may be sorted on name)
1006  @param name Name of the tag to locate.
1007  @param partial If TRUE, matches the first part of the name instead of doing exact match.
1008  @param tags_array_sorted If TRUE, the passed \c tags_array is sorted by name so it can be
1009  searched with binary search. Otherwise it is searched linear which is obviously slower.
1010  @param tagCount Return location of the matched tags.
1011 */
1012 TMTag **tm_tags_find(const GPtrArray *tags_array, const char *name,
1013                 gboolean partial, gboolean tags_array_sorted, int * tagCount)
1014 {
1015         static TMTag *tag = NULL;
1016         TMTag **result;
1017         int tagMatches=0;
1018
1019         if ((!tags_array) || (!tags_array->len))
1020                 return NULL;
1021
1022         if (NULL == tag)
1023                 tag = g_new0(TMTag, 1);
1024         tag->name = (char *) name;
1025         s_sort_attrs = NULL;
1026         s_partial = partial;
1027
1028         result = tags_search(tags_array, tag, partial, tags_array_sorted);
1029         /* There can be matches on both sides of result */
1030         if (result)
1031         {
1032                 TMTag **last = (TMTag **) &tags_array->pdata[tags_array->len - 1];
1033                 TMTag **adv;
1034
1035                 /* First look for any matches after result */
1036                 adv = result;
1037                 adv++;
1038                 for (; adv <= last && *adv; ++ adv)
1039                 {
1040                         if (0 != tm_tag_compare(&tag, adv))
1041                                 break;
1042                         ++tagMatches;
1043                 }
1044                 /* Now look for matches from result and below */
1045                 for (; result >= (TMTag **) tags_array->pdata; -- result)
1046                 {
1047                         if (0 != tm_tag_compare(&tag, (TMTag **) result))
1048                                 break;
1049                         ++tagMatches;
1050                 }
1051                 *tagCount=tagMatches;
1052                 ++ result;      /* Correct address for the last successful match */
1053         }
1054         s_partial = FALSE;
1055         return (TMTag **) result;
1056 }
1057
1058 #ifdef TM_DEBUG /* various debugging functions */
1059
1060 /*
1061  Returns the type of tag as a string
1062  @param tag The tag whose type is required
1063 */
1064 const char *tm_tag_type_name(const TMTag *tag)
1065 {
1066         g_return_val_if_fail(tag, NULL);
1067         switch(tag->type)
1068         {
1069                 case tm_tag_class_t: return "class";
1070                 case tm_tag_enum_t: return "enum";
1071                 case tm_tag_enumerator_t: return "enumval";
1072                 case tm_tag_field_t: return "field";
1073                 case tm_tag_function_t: return "function";
1074                 case tm_tag_interface_t: return "interface";
1075                 case tm_tag_member_t: return "member";
1076                 case tm_tag_method_t: return "method";
1077                 case tm_tag_namespace_t: return "namespace";
1078                 case tm_tag_package_t: return "package";
1079                 case tm_tag_prototype_t: return "prototype";
1080                 case tm_tag_struct_t: return "struct";
1081                 case tm_tag_typedef_t: return "typedef";
1082                 case tm_tag_union_t: return "union";
1083                 case tm_tag_variable_t: return "variable";
1084                 case tm_tag_externvar_t: return "extern";
1085                 case tm_tag_macro_t: return "define";
1086                 case tm_tag_macro_with_arg_t: return "macro";
1087                 default: return NULL;
1088         }
1089         return NULL;
1090 }
1091
1092 /*
1093  Returns the TMTagType given the name of the type. Reverse of tm_tag_type_name.
1094  @param tag_name Name of the tag type
1095 */
1096 TMTagType tm_tag_name_type(const char* tag_name)
1097 {
1098         g_return_val_if_fail(tag_name, tm_tag_undef_t);
1099
1100         if (strcmp(tag_name, "class") == 0) return tm_tag_class_t;
1101         else if (strcmp(tag_name, "enum") == 0) return tm_tag_enum_t;
1102         else if (strcmp(tag_name, "enumval") == 0) return tm_tag_enumerator_t;
1103         else if (strcmp(tag_name, "field") == 0) return tm_tag_field_t;
1104         else if (strcmp(tag_name, "function") == 0) return tm_tag_function_t;
1105         else if (strcmp(tag_name, "interface") == 0) return tm_tag_interface_t;
1106         else if (strcmp(tag_name, "member") == 0) return tm_tag_member_t;
1107         else if (strcmp(tag_name, "method") == 0) return tm_tag_method_t;
1108         else if (strcmp(tag_name, "namespace") == 0) return tm_tag_namespace_t;
1109         else if (strcmp(tag_name, "package") == 0) return tm_tag_package_t;
1110         else if (strcmp(tag_name, "prototype") == 0) return tm_tag_prototype_t;
1111         else if (strcmp(tag_name, "struct") == 0) return tm_tag_struct_t;
1112         else if (strcmp(tag_name, "typedef") == 0) return tm_tag_typedef_t;
1113         else if (strcmp(tag_name, "union") == 0) return tm_tag_union_t;
1114         else if (strcmp(tag_name, "variable") == 0) return tm_tag_variable_t;
1115         else if (strcmp(tag_name, "extern") == 0) return tm_tag_externvar_t;
1116         else if (strcmp(tag_name, "define") == 0) return tm_tag_macro_t;
1117         else if (strcmp(tag_name, "macro") == 0) return tm_tag_macro_with_arg_t;
1118         else return tm_tag_undef_t;
1119 }
1120
1121 static const char *tm_tag_impl_name(TMTag *tag)
1122 {
1123         g_return_val_if_fail(tag, NULL);
1124         if (TAG_IMPL_VIRTUAL == tag->impl)
1125                 return "virtual";
1126         else
1127                 return NULL;
1128 }
1129
1130 static const char *tm_tag_access_name(TMTag *tag)
1131 {
1132         g_return_val_if_fail(tag, NULL);
1133         if (TAG_ACCESS_PUBLIC == tag->access)
1134                 return "public";
1135         else if (TAG_ACCESS_PROTECTED == tag->access)
1136                 return "protected";
1137         else if (TAG_ACCESS_PRIVATE == tag->access)
1138                 return "private";
1139         else
1140                 return NULL;
1141 }
1142
1143 /*
1144   Prints information about a tag to the given file pointer.
1145   @param tag The tag whose info is required.
1146   @param fp The file pointer of teh file to print the info to.
1147 */
1148 void tm_tag_print(TMTag *tag, FILE *fp)
1149 {
1150         const char *laccess, *impl, *type;
1151         if (!tag || !fp)
1152                 return;
1153         laccess = tm_tag_access_name(tag);
1154         impl = tm_tag_impl_name(tag);
1155         type = tm_tag_type_name(tag);
1156         if (laccess)
1157                 fprintf(fp, "%s ", laccess);
1158         if (impl)
1159                 fprintf(fp, "%s ", impl);
1160         if (type)
1161                 fprintf(fp, "%s ", type);
1162         if (tag->var_type)
1163                 fprintf(fp, "%s ", tag->var_type);
1164         if (tag->scope)
1165                 fprintf(fp, "%s::", tag->scope);
1166         fprintf(fp, "%s", tag->name);
1167         if (tag->arglist)
1168                 fprintf(fp, "%s", tag->arglist);
1169         if (tag->inheritance)
1170                 fprintf(fp, " : from %s", tag->inheritance);
1171         if ((tag->file) && (tag->line > 0))
1172                 fprintf(fp, "[%s:%ld]", tag->file->file_name
1173                   , tag->line);
1174         fprintf(fp, "\n");
1175 }
1176
1177 /*
1178   Prints info about all tags in the array to the given file pointer.
1179 */
1180 void tm_tags_array_print(GPtrArray *tags, FILE *fp)
1181 {
1182         guint i;
1183         TMTag *tag;
1184         if (!(tags && (tags->len > 0) && fp))
1185                 return;
1186         for (i = 0; i < tags->len; ++i)
1187         {
1188                 tag = TM_TAG(tags->pdata[i]);
1189                 tm_tag_print(tag, fp);
1190         }
1191 }
1192
1193 /*
1194   Returns the depth of tag scope (useful for finding tag hierarchy
1195 */
1196 gint tm_tag_scope_depth(const TMTag *t)
1197 {
1198         gint depth;
1199         char *s;
1200         if(!(t && t->scope))
1201                 return 0;
1202         for (s = t->scope, depth = 0; s; s = strstr(s, "::"))
1203         {
1204                 ++ depth;
1205                 ++ s;
1206         }
1207         return depth;
1208 }
1209
1210 #endif /* TM_DEBUG */