types/types.c

   1 /*
   2  * types.c
   3  *
   4  * BabelTrace - Converter
   5  *
   6  * Types registry.
   7  *
   8  * Copyright 2010, 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   9  *
  10  * Permission is hereby granted, free of charge, to any person obtaining a copy
  11  * of this software and associated documentation files (the "Software"), to deal
  12  * in the Software without restriction, including without limitation the rights
  13  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  14  * copies of the Software, and to permit persons to whom the Software is
  15  * furnished to do so, subject to the following conditions:
  16  *
  17  * The above copyright notice and this permission notice shall be included in
  18  * all copies or substantial portions of the Software.
  19  */
  20
  21 #include <babeltrace/format.h>
  22 #include <babeltrace/babeltrace.h>
  23 #include <limits.h>
  24 #include <glib.h>
  25 #include <errno.h>
  26
  27 static
  28 GQuark prefix_quark(const char *prefix, GQuark quark)
  29 {
  30         GQuark nq;
  31         GString *str;
  32
  33         str = g_string_new(prefix);
  34         g_string_append(str, g_quark_to_string(quark));
  35         nq = g_quark_from_string(g_string_free(str, FALSE));
  36         return nq;
  37 }
  38
  39 static
  40 struct declaration *
  41         lookup_declaration_scope(GQuark declaration_name,
  42                 struct declaration_scope *scope)
  43 {
  44         return g_hash_table_lookup(scope->typedef_declarations,
  45                                    (gconstpointer) (unsigned long) declaration_name);
  46 }
  47
  48 struct declaration *lookup_declaration(GQuark declaration_name,
  49                 struct declaration_scope *scope)
  50 {
  51         struct declaration *declaration;
  52
  53         while (scope) {
  54                 declaration = lookup_declaration_scope(declaration_name,
  55                                                        scope);
  56                 if (declaration)
  57                         return declaration;
  58                 scope = scope->parent_scope;
  59         }
  60         return NULL;
  61 }
  62
  63 int register_declaration(GQuark name, struct declaration *declaration,
  64                 struct declaration_scope *scope)
  65 {
  66         if (!name)
  67                 return -EPERM;
  68
  69         /* Only lookup in local scope */
  70         if (lookup_declaration_scope(name, scope))
  71                 return -EEXIST;
  72
  73         g_hash_table_insert(scope->typedef_declarations,
  74                             (gpointer) (unsigned long) name,
  75                             declaration);
  76         declaration_ref(declaration);
  77         return 0;
  78 }
  79
  80 static
  81 struct definition *
  82         lookup_field_definition_scope(GQuark field_name,
  83                 struct definition_scope *scope)
  84 {
  85         return g_hash_table_lookup(scope->definitions,
  86                                    (gconstpointer) (unsigned long) field_name);
  87 }
  88
  89 /*
  90  * Returns the index at which the paths differ.
  91  * If the value returned equals len, it means the paths are identical
  92  * from index 0 to len-1.
  93  */
  94 static int compare_paths(GArray *a, GArray *b, int len)
  95 {
  96         int i;
  97
  98         assert(len <= a->len);
  99         assert(len <= b->len);
 100
 101         for (i = 0; i < len; i++) {
 102                 GQuark qa, qb;
 103
 104                 qa = g_array_index(a, GQuark, i);
 105                 qb = g_array_index(b, GQuark, i);
 106                 if (qa != qb)
 107                         return i;
 108         }
 109         return i;
 110 }
 111
 112 static int is_path_child_of(GArray *path, GArray *maybe_parent)
 113 {
 114         int i, ret;
 115
 116         if (babeltrace_debug) {
 117                 int need_dot = 0;
 118
 119                 printf_debug("Is path \"");
 120                 for (i = 0; i < path->len; need_dot = 1, i++)
 121                         printf("%s%s", need_dot ? "." : "",
 122                                 g_quark_to_string(g_array_index(path, GQuark, i)));
 123                 need_dot = 0;
 124                 printf("\" child of \"");
 125                 for (i = 0; i < maybe_parent->len; need_dot = 1, i++)
 126                         printf("%s%s", need_dot ? "." : "",
 127                                 g_quark_to_string(g_array_index(maybe_parent, GQuark, i)));
 128                 printf("\" ? ");
 129         }
 130
 131         if (path->len <= maybe_parent->len) {
 132                 ret = 0;
 133                 goto end;
 134         }
 135         if (compare_paths(path, maybe_parent, maybe_parent->len)
 136                         == maybe_parent->len)
 137                 ret = 1;
 138         else
 139                 ret = 0;
 140 end:
 141         if (babeltrace_debug)
 142                 printf("%s\n", ret ? "Yes" : "No");
 143         return ret;
 144 }
 145
 146 static struct definition_scope *
 147         get_definition_scope(struct definition *definition)
 148 {
 149         switch (definition->declaration->id) {
 150         case CTF_TYPE_STRUCT:
 151         {
 152                 struct definition_struct *def =
 153                         container_of(definition, struct definition_struct, p);
 154                 return def->scope;
 155         }
 156         case CTF_TYPE_VARIANT:
 157         {
 158                 struct definition_variant *def =
 159                         container_of(definition, struct definition_variant, p);
 160                 return def->scope;
 161         }
 162         case CTF_TYPE_ARRAY:
 163         {
 164                 struct definition_array *def =
 165                         container_of(definition, struct definition_array, p);
 166                 return def->scope;
 167         }
 168         case CTF_TYPE_SEQUENCE:
 169         {
 170                 struct definition_sequence *def =
 171                         container_of(definition, struct definition_sequence, p);
 172                 return def->scope;
 173         }
 174
 175         case CTF_TYPE_INTEGER:
 176         case CTF_TYPE_FLOAT:
 177         case CTF_TYPE_ENUM:
 178         case CTF_TYPE_STRING:
 179         case CTF_TYPE_UNKNOWN:
 180         default:
 181                 return NULL;
 182         }
 183 }
 184
 185 /*
 186  * OK, here is the fun. We want to lookup a field that is:
 187  * - either in the same dynamic scope:
 188  *   - either in the current scope, but prior to the current field.
 189  *   - or in a parent scope (or parent of parent ...) still in a field
 190  *     prior to the current field position within the parents.
 191  * - or in a different dynamic scope:
 192  *   - either in a upper dynamic scope (walk down a targeted scope from
 193  *     the dynamic scope root)
 194  *   - or in a lower dynamic scope (failure)
 195  * The dynamic scope roots are linked together, so we can access the
 196  * parent dynamic scope from the child dynamic scope by walking up to
 197  * the parent.
 198  * If we cannot find such a field that is prior to our current path, we
 199  * return NULL.
 200  *
 201  * cur_path: the path leading to the variant definition.
 202  * lookup_path: the path leading to the enum we want to look for.
 203  * scope: the definition scope containing the variant definition.
 204  */
 205 struct definition *
 206         lookup_definition(GArray *cur_path,
 207                           GArray *lookup_path,
 208                           struct definition_scope *scope)
 209 {
 210         struct definition *definition, *lookup_definition;
 211         GQuark last;
 212         int index;
 213
 214         /* Going up in the hierarchy. Check where we come from. */
 215         assert(is_path_child_of(cur_path, scope->scope_path));
 216         assert(cur_path->len - scope->scope_path->len == 1);
 217
 218         /*
 219          * First, check if the target name is size one, present in
 220          * our parent path, located prior to us.
 221          */
 222         if (lookup_path->len == 1) {
 223                 last = g_array_index(lookup_path, GQuark, 0);
 224                 lookup_definition = lookup_field_definition_scope(last, scope);
 225                 last = g_array_index(cur_path, GQuark, cur_path->len - 1);
 226                 definition = lookup_field_definition_scope(last, scope);
 227                 assert(definition);
 228                 if (lookup_definition && lookup_definition->index < definition->index)
 229                         return lookup_definition;
 230                 else
 231                         return NULL;
 232         }
 233
 234         while (scope) {
 235                 if (is_path_child_of(cur_path, scope->scope_path) &&
 236                     cur_path->len - scope->scope_path->len == 1) {
 237                         last = g_array_index(cur_path, GQuark, cur_path->len - 1);
 238                         definition = lookup_field_definition_scope(last, scope);
 239                         assert(definition);
 240                         index = definition->index;
 241                 } else {
 242                         /*
 243                          * Getting to a dynamic scope parent. We are
 244                          * guaranteed that the parent is entirely
 245                          * located before the child.
 246                          */
 247                         index = -1;
 248                 }
 249 lookup:
 250                 if (is_path_child_of(lookup_path, scope->scope_path)) {
 251                         /* Means we can lookup the field in this scope */
 252                         last = g_array_index(lookup_path, GQuark,
 253                                              scope->scope_path->len);
 254                         lookup_definition = lookup_field_definition_scope(last, scope);
 255                         if (!lookup_definition || ((index != -1) && lookup_definition->index >= index))
 256                                 return NULL;
 257                         /* Found it! And it is prior to the current field. */
 258                         if (lookup_path->len - scope->scope_path->len == 1) {
 259                                 /* Direct child */
 260                                 return lookup_definition;
 261                         } else {
 262                                 scope = get_definition_scope(lookup_definition);
 263                                 /* Check if the definition has a sub-scope */
 264                                 if (!scope)
 265                                         return NULL;
 266                                 /*
 267                                  * Don't compare index anymore, because we are
 268                                  * going within a scope that has been validated
 269                                  * to be entirely prior to the current scope.
 270                                  */
 271                                 cur_path = NULL;
 272                                 index = -1;
 273                                 goto lookup;
 274                         }
 275                 } else {
 276                         /* lookup_path is within an upper scope */
 277                         cur_path = scope->scope_path;
 278                         scope = scope->parent_scope;
 279                 }
 280         }
 281         return NULL;
 282 }
 283
 284 int register_field_definition(GQuark field_name, struct definition *definition,
 285                 struct definition_scope *scope)
 286 {
 287         if (!scope || !field_name)
 288                 return -EPERM;
 289
 290         /* Only lookup in local scope */
 291         if (lookup_field_definition_scope(field_name, scope))
 292                 return -EEXIST;
 293
 294         g_hash_table_insert(scope->definitions,
 295                             (gpointer) (unsigned long) field_name,
 296                             definition);
 297         /* Don't keep reference on definition */
 298         return 0;
 299 }
 300
 301 void declaration_ref(struct declaration *declaration)
 302 {
 303         declaration->ref++;
 304 }
 305
 306 void declaration_unref(struct declaration *declaration)
 307 {
 308         if (!declaration)
 309                 return;
 310         if (!--declaration->ref)
 311                 declaration->declaration_free(declaration);
 312 }
 313
 314 void definition_ref(struct definition *definition)
 315 {
 316         definition->ref++;
 317 }
 318
 319 void definition_unref(struct definition *definition)
 320 {
 321         if (!definition)
 322                 return;
 323         if (!--definition->ref)
 324                 definition->declaration->definition_free(definition);
 325 }
 326
 327 struct declaration_scope *
 328         new_declaration_scope(struct declaration_scope *parent_scope)
 329 {
 330         struct declaration_scope *scope = g_new(struct declaration_scope, 1);
 331
 332         scope->typedef_declarations = g_hash_table_new_full(g_direct_hash,
 333                                         g_direct_equal, NULL,
 334                                         (GDestroyNotify) definition_unref);
 335         scope->struct_declarations = g_hash_table_new_full(g_direct_hash,
 336                                         g_direct_equal, NULL,
 337                                         (GDestroyNotify) declaration_unref);
 338         scope->variant_declarations = g_hash_table_new_full(g_direct_hash,
 339                                         g_direct_equal, NULL,
 340                                         (GDestroyNotify) declaration_unref);
 341         scope->enum_declarations = g_hash_table_new_full(g_direct_hash,
 342                                         g_direct_equal, NULL,
 343                                         (GDestroyNotify) declaration_unref);
 344         scope->parent_scope = parent_scope;
 345         return scope;
 346 }
 347
 348 void free_declaration_scope(struct declaration_scope *scope)
 349 {
 350         g_hash_table_destroy(scope->enum_declarations);
 351         g_hash_table_destroy(scope->variant_declarations);
 352         g_hash_table_destroy(scope->struct_declarations);
 353         g_hash_table_destroy(scope->typedef_declarations);
 354         g_free(scope);
 355 }
 356
 357 static
 358 struct declaration_struct *lookup_struct_declaration_scope(GQuark struct_name,
 359                                              struct declaration_scope *scope)
 360 {
 361         return g_hash_table_lookup(scope->struct_declarations,
 362                                    (gconstpointer) (unsigned long) struct_name);
 363 }
 364
 365 struct declaration_struct *lookup_struct_declaration(GQuark struct_name,
 366                                        struct declaration_scope *scope)
 367 {
 368         struct declaration_struct *declaration;
 369
 370         while (scope) {
 371                 declaration = lookup_struct_declaration_scope(struct_name, scope);
 372                 if (declaration)
 373                         return declaration;
 374                 scope = scope->parent_scope;
 375         }
 376         return NULL;
 377 }
 378
 379 int register_struct_declaration(GQuark struct_name,
 380         struct declaration_struct *struct_declaration,
 381         struct declaration_scope *scope)
 382 {
 383         GQuark prefix_name;
 384         int ret;
 385
 386         if (!struct_name)
 387                 return -EPERM;
 388
 389         /* Only lookup in local scope */
 390         if (lookup_struct_declaration_scope(struct_name, scope))
 391                 return -EEXIST;
 392
 393         g_hash_table_insert(scope->struct_declarations,
 394                             (gpointer) (unsigned long) struct_name,
 395                             struct_declaration);
 396         declaration_ref(&struct_declaration->p);
 397
 398         /* Also add in typedef/typealias scopes */
 399         prefix_name = prefix_quark("struct ", struct_name);
 400         ret = register_declaration(prefix_name, &struct_declaration->p, scope);
 401         assert(!ret);
 402         return 0;
 403 }
 404
 405 static
 406 struct declaration_untagged_variant *
 407         lookup_variant_declaration_scope(GQuark variant_name,
 408                 struct declaration_scope *scope)
 409 {
 410         return g_hash_table_lookup(scope->variant_declarations,
 411                                    (gconstpointer) (unsigned long) variant_name);
 412 }
 413
 414 struct declaration_untagged_variant *
 415         lookup_variant_declaration(GQuark variant_name,
 416                 struct declaration_scope *scope)
 417 {
 418         struct declaration_untagged_variant *declaration;
 419
 420         while (scope) {
 421                 declaration = lookup_variant_declaration_scope(variant_name, scope);
 422                 if (declaration)
 423                         return declaration;
 424                 scope = scope->parent_scope;
 425         }
 426         return NULL;
 427 }
 428
 429 int register_variant_declaration(GQuark variant_name,
 430                 struct declaration_untagged_variant *untagged_variant_declaration,
 431                 struct declaration_scope *scope)
 432 {
 433         GQuark prefix_name;
 434         int ret;
 435
 436         if (!variant_name)
 437                 return -EPERM;
 438
 439         /* Only lookup in local scope */
 440         if (lookup_variant_declaration_scope(variant_name, scope))
 441                 return -EEXIST;
 442
 443         g_hash_table_insert(scope->variant_declarations,
 444                             (gpointer) (unsigned long) variant_name,
 445                             untagged_variant_declaration);
 446         declaration_ref(&untagged_variant_declaration->p);
 447
 448         /* Also add in typedef/typealias scopes */
 449         prefix_name = prefix_quark("variant ", variant_name);
 450         ret = register_declaration(prefix_name,
 451                         &untagged_variant_declaration->p, scope);
 452         assert(!ret);
 453         return 0;
 454 }
 455
 456 static
 457 struct declaration_enum *
 458         lookup_enum_declaration_scope(GQuark enum_name,
 459                 struct declaration_scope *scope)
 460 {
 461         return g_hash_table_lookup(scope->enum_declarations,
 462                                    (gconstpointer) (unsigned long) enum_name);
 463 }
 464
 465 struct declaration_enum *
 466         lookup_enum_declaration(GQuark enum_name,
 467                 struct declaration_scope *scope)
 468 {
 469         struct declaration_enum *declaration;
 470
 471         while (scope) {
 472                 declaration = lookup_enum_declaration_scope(enum_name, scope);
 473                 if (declaration)
 474                         return declaration;
 475                 scope = scope->parent_scope;
 476         }
 477         return NULL;
 478 }
 479
 480 int register_enum_declaration(GQuark enum_name,
 481                 struct declaration_enum *enum_declaration,
 482                 struct declaration_scope *scope)
 483 {
 484         GQuark prefix_name;
 485         int ret;
 486
 487         if (!enum_name)
 488                 return -EPERM;
 489
 490         /* Only lookup in local scope */
 491         if (lookup_enum_declaration_scope(enum_name, scope))
 492                 return -EEXIST;
 493
 494         g_hash_table_insert(scope->enum_declarations,
 495                             (gpointer) (unsigned long) enum_name,
 496                             enum_declaration);
 497         declaration_ref(&enum_declaration->p);
 498
 499         /* Also add in typedef/typealias scopes */
 500         prefix_name = prefix_quark("enum ", enum_name);
 501         ret = register_declaration(prefix_name, &enum_declaration->p, scope);
 502         assert(!ret);
 503         return 0;
 504 }
 505
 506 static struct definition_scope *
 507         _new_definition_scope(struct definition_scope *parent_scope,
 508                               int scope_path_len)
 509 {
 510         struct definition_scope *scope = g_new(struct definition_scope, 1);
 511
 512         scope->definitions = g_hash_table_new(g_direct_hash,
 513                                         g_direct_equal);
 514         scope->parent_scope = parent_scope;
 515         scope->scope_path = g_array_sized_new(FALSE, TRUE, sizeof(GQuark),
 516                                               scope_path_len);
 517         g_array_set_size(scope->scope_path, scope_path_len);
 518         return scope;
 519 }
 520
 521 GQuark new_definition_path(struct definition_scope *parent_scope,
 522                            GQuark field_name, const char *root_name)
 523 {
 524         GQuark path;
 525         GString *str;
 526         gchar *c_str;
 527         int i;
 528         int need_dot = 0;
 529
 530         str = g_string_new("");
 531         if (root_name) {
 532                 g_string_append(str, root_name);
 533                 need_dot = 1;
 534         } else if (parent_scope) {
 535                 for (i = 0; i < parent_scope->scope_path->len; i++) {
 536                         GQuark q = g_array_index(parent_scope->scope_path,
 537                                                  GQuark, i);
 538                         if (!q)
 539                                 continue;
 540                         if (need_dot)
 541                                 g_string_append(str, ".");
 542                         g_string_append(str, g_quark_to_string(q));
 543                         need_dot = 1;
 544                 }
 545         }
 546         if (field_name) {
 547                 if (need_dot)
 548                         g_string_append(str, ".");
 549                 g_string_append(str, g_quark_to_string(field_name));
 550         }
 551         c_str = g_string_free(str, FALSE);
 552         if (c_str[0] == '\0')
 553                 return 0;
 554         path = g_quark_from_string(c_str);
 555         printf_debug("new definition path: %s\n", c_str);
 556         g_free(c_str);
 557         return path;
 558 }
 559
 560 struct definition_scope *
 561         new_definition_scope(struct definition_scope *parent_scope,
 562                              GQuark field_name, const char *root_name)
 563 {
 564         struct definition_scope *scope;
 565
 566         if (root_name) {
 567                 scope = _new_definition_scope(parent_scope, 0);
 568                 append_scope_path(root_name, scope->scope_path);
 569         } else {
 570                 int scope_path_len = 1;
 571
 572                 assert(parent_scope);
 573                 scope_path_len += parent_scope->scope_path->len;
 574                 scope = _new_definition_scope(parent_scope, scope_path_len);
 575                 memcpy(scope->scope_path->data, parent_scope->scope_path->data,
 576                        sizeof(GQuark) * (scope_path_len - 1));
 577                 g_array_index(scope->scope_path, GQuark, scope_path_len - 1) =
 578                         field_name;
 579         }
 580         if (babeltrace_debug) {
 581                 int i, need_dot = 0;
 582
 583                 printf_debug("new definition scope: ");
 584                 for (i = 0; i < scope->scope_path->len; need_dot = 1, i++)
 585                         printf("%s%s", need_dot ? "." : "",
 586                                 g_quark_to_string(g_array_index(scope->scope_path, GQuark, i)));
 587                 printf("\n");
 588         }
 589         return scope;
 590 }
 591
 592 /*
 593  * in: path (dot separated), out: q (GArray of GQuark)
 594  */
 595 void append_scope_path(const char *path, GArray *q)
 596 {
 597         const char *ptrbegin, *ptrend = path;
 598         GQuark quark;
 599
 600         for (;;) {
 601                 char *str;
 602                 size_t len;
 603
 604                 ptrbegin = ptrend;
 605                 ptrend = strchr(ptrbegin, '.');
 606                 if (!ptrend)
 607                         break;
 608                 len = ptrend - ptrbegin;
 609                 /* Don't accept two consecutive dots */
 610                 assert(len != 0);
 611                 str = g_new(char, len + 1);     /* include \0 */
 612                 memcpy(str, ptrbegin, len);
 613                 str[len] = '\0';
 614                 quark = g_quark_from_string(str);
 615                 g_array_append_val(q, quark);
 616                 g_free(str);
 617                 ptrend++;       /* skip current dot */
 618         }
 619         /* last. Check for trailing dot (and discard). */
 620         if (ptrbegin[0] != '\0') {
 621                 quark = g_quark_from_string(ptrbegin);
 622                 g_array_append_val(q, quark);
 623         }
 624 }
 625
 626 void free_definition_scope(struct definition_scope *scope)
 627 {
 628         g_array_free(scope->scope_path, TRUE);
 629         g_hash_table_destroy(scope->definitions);
 630         g_free(scope);
 631 }