types/types.c

   1 /*
   2  * declarations.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 <limits.h>
  23 #include <glib.h>
  24 #include <errno.h>
  25
  26 static
  27 GQuark prefix_quark(const char *prefix, GQuark quark)
  28 {
  29         GQuark nq;
  30         GString *str;
  31
  32         str = g_string_new(prefix);
  33         g_string_append(str, g_quark_to_string(quark));
  34         nq = g_quark_from_string(g_string_free(str, FALSE));
  35         return nq;
  36 }
  37
  38 static
  39 struct declaration *
  40         lookup_declaration_scope(GQuark declaration_name,
  41                 struct declaration_scope *scope)
  42 {
  43         return g_hash_table_lookup(scope->typedef_declarations,
  44                                    (gconstpointer) (unsigned long) declaration_name);
  45 }
  46
  47 struct declaration *lookup_declaration(GQuark declaration_name,
  48                 struct declaration_scope *scope)
  49 {
  50         struct declaration *declaration;
  51
  52         while (scope) {
  53                 declaration = lookup_declaration_scope(declaration_name,
  54                                                        scope);
  55                 if (declaration)
  56                         return declaration;
  57                 scope = scope->parent_scope;
  58         }
  59         return NULL;
  60 }
  61
  62 int register_declaration(GQuark name, struct declaration *declaration,
  63                 struct declaration_scope *scope)
  64 {
  65         if (!name)
  66                 return -EPERM;
  67
  68         /* Only lookup in local scope */
  69         if (lookup_declaration_scope(name, scope))
  70                 return -EEXIST;
  71
  72         g_hash_table_insert(scope->typedef_declarations,
  73                             (gpointer) (unsigned long) name,
  74                             declaration);
  75         declaration_ref(declaration);
  76         return 0;
  77 }
  78
  79 static
  80 struct definition *
  81         lookup_field_definition_scope(GQuark field_name,
  82                 struct definition_scope *scope)
  83 {
  84         return g_hash_table_lookup(scope->definitions,
  85                                    (gconstpointer) (unsigned long) field_name);
  86 }
  87
  88 /*
  89  * Returns the index at which the paths differ.
  90  * If the value returned equals len, it means the paths are identical
  91  * from index 0 to len-1.
  92  */
  93 static int compare_paths(GArray *a, GArray *b, int len)
  94 {
  95         int i;
  96
  97         assert(len <= a->len);
  98         assert(len <= b->len);
  99
 100         for (i = 0; i < len; i++) {
 101                 GQuark qa, qb;
 102
 103                 qa = g_array_index(a, GQuark, i);
 104                 qb = g_array_index(b, GQuark, i);
 105                 if (qa != qb)
 106                         return i;
 107         }
 108         return i;
 109 }
 110
 111 static int is_path_child_of(GArray *path, GArray *maybe_parent)
 112 {
 113         if (path->len <= maybe_parent->len)
 114                 return 0;
 115         if (compare_paths(path, maybe_parent, maybe_parent->len)
 116                         == maybe_parent->len)
 117                 return 1;
 118         else
 119                 return 0;
 120 }
 121
 122 static struct definition_scope *
 123         get_definition_scope(struct definition *definition)
 124 {
 125         switch (definition->declaration->id) {
 126         case CTF_TYPE_STRUCT:
 127         {
 128                 struct definition_struct *def =
 129                         container_of(definition, struct definition_struct, p);
 130                 return def->scope;
 131         }
 132         case CTF_TYPE_VARIANT:
 133         {
 134                 struct definition_variant *def =
 135                         container_of(definition, struct definition_variant, p);
 136                 return def->scope;
 137         }
 138         case CTF_TYPE_ARRAY:
 139         {
 140                 struct definition_array *def =
 141                         container_of(definition, struct definition_array, p);
 142                 return def->scope;
 143         }
 144         case CTF_TYPE_SEQUENCE:
 145         {
 146                 struct definition_sequence *def =
 147                         container_of(definition, struct definition_sequence, p);
 148                 return def->scope;
 149         }
 150
 151         case CTF_TYPE_INTEGER:
 152         case CTF_TYPE_FLOAT:
 153         case CTF_TYPE_ENUM:
 154         case CTF_TYPE_STRING:
 155         case CTF_TYPE_UNKNOWN:
 156         default:
 157                 return NULL;
 158         }
 159 }
 160
 161 /*
 162  * OK, here is the fun. We want to lookup a field that is:
 163  * - either in the same dynamic scope:
 164  *   - either in the current scope, but prior to the current field.
 165  *   - or in a parent scope (or parent of parent ...) still in a field
 166  *     prior to the current field position within the parents.
 167  * - or in a different dynamic scope:
 168  *   - either in a upper dynamic scope (walk down a targeted scope from
 169  *     the dynamic scope root)
 170  *   - or in a lower dynamic scope (failure)
 171  * The dynamic scope roots are linked together, so we can access the
 172  * parent dynamic scope from the child dynamic scope by walking up to
 173  * the parent.
 174  * If we cannot find such a field that is prior to our current path, we
 175  * return NULL.
 176  *
 177  * cur_path: the path leading to the variant definition.
 178  * lookup_path: the path leading to the enum we want to look for.
 179  * scope: the definition scope containing the variant definition.
 180  */
 181 struct definition *
 182         lookup_definition(GArray *cur_path,
 183                           GArray *lookup_path,
 184                           struct definition_scope *scope)
 185 {
 186         struct definition *definition, *lookup_definition;
 187         GQuark last;
 188         int index;
 189
 190         while (scope) {
 191                 /* going up in the hierarchy. Check where we come from. */
 192                 assert(is_path_child_of(cur_path, scope->scope_path));
 193                 assert(cur_path->len - scope->scope_path->len == 1);
 194                 last = g_array_index(cur_path, GQuark, cur_path->len - 1);
 195                 definition = lookup_field_definition_scope(last, scope);
 196                 assert(definition);
 197                 index = definition->index;
 198 lookup:
 199                 if (is_path_child_of(lookup_path, scope->scope_path)) {
 200                         /* Means we can lookup the field in this scope */
 201                         last = g_array_index(lookup_path, GQuark,
 202                                              scope->scope_path->len);
 203                         lookup_definition = lookup_field_definition_scope(last, scope);
 204                         if (!lookup_definition || ((index != -1) && lookup_definition->index >= index))
 205                                 return NULL;
 206                         /* Found it! And it is prior to the current field. */
 207                         if (lookup_path->len - scope->scope_path->len == 1) {
 208                                 /* Direct child */
 209                                 return lookup_definition;
 210                         } else {
 211                                 scope = get_definition_scope(lookup_definition);
 212                                 /* Check if the definition has a sub-scope */
 213                                 if (!scope)
 214                                         return NULL;
 215                                 /*
 216                                  * Don't compare index anymore, because we are
 217                                  * going within a scope that has been validated
 218                                  * to be entirely prior to the current scope.
 219                                  */
 220                                 cur_path = NULL;
 221                                 index = -1;
 222                                 goto lookup;
 223                         }
 224                 } else {
 225                         assert(index != -1);
 226                         /* lookup_path is within an upper scope */
 227                         cur_path = scope->scope_path;
 228                         scope = scope->parent_scope;
 229                 }
 230         }
 231         return NULL;
 232 }
 233
 234 int register_field_definition(GQuark field_name, struct definition *definition,
 235                 struct definition_scope *scope)
 236 {
 237         if (!field_name)
 238                 return -EPERM;
 239
 240         /* Only lookup in local scope */
 241         if (lookup_field_definition_scope(field_name, scope))
 242                 return -EEXIST;
 243
 244         g_hash_table_insert(scope->definitions,
 245                             (gpointer) (unsigned long) field_name,
 246                             definition);
 247         definition_ref(definition);
 248         return 0;
 249 }
 250
 251 void declaration_ref(struct declaration *declaration)
 252 {
 253         declaration->ref++;
 254 }
 255
 256 void declaration_unref(struct declaration *declaration)
 257 {
 258         if (!--declaration->ref)
 259                 declaration->declaration_free(declaration);
 260 }
 261
 262 void definition_ref(struct definition *definition)
 263 {
 264         definition->ref++;
 265 }
 266
 267 void definition_unref(struct definition *definition)
 268 {
 269         if (!--definition->ref)
 270                 definition->declaration->definition_free(definition);
 271 }
 272
 273 struct declaration_scope *
 274         new_declaration_scope(struct declaration_scope *parent_scope)
 275 {
 276         struct declaration_scope *scope = g_new(struct declaration_scope, 1);
 277
 278         scope->typedef_declarations = g_hash_table_new_full(g_direct_hash,
 279                                         g_direct_equal, NULL,
 280                                         (GDestroyNotify) definition_unref);
 281         scope->struct_declarations = g_hash_table_new_full(g_direct_hash,
 282                                         g_direct_equal, NULL,
 283                                         (GDestroyNotify) declaration_unref);
 284         scope->variant_declarations = g_hash_table_new_full(g_direct_hash,
 285                                         g_direct_equal, NULL,
 286                                         (GDestroyNotify) declaration_unref);
 287         scope->enum_declarations = g_hash_table_new_full(g_direct_hash,
 288                                         g_direct_equal, NULL,
 289                                         (GDestroyNotify) declaration_unref);
 290         scope->parent_scope = parent_scope;
 291         return scope;
 292 }
 293
 294 void free_declaration_scope(struct declaration_scope *scope)
 295 {
 296         g_hash_table_destroy(scope->enum_declarations);
 297         g_hash_table_destroy(scope->variant_declarations);
 298         g_hash_table_destroy(scope->struct_declarations);
 299         g_hash_table_destroy(scope->typedef_declarations);
 300         g_free(scope);
 301 }
 302
 303 static
 304 struct declaration_struct *lookup_struct_declaration_scope(GQuark struct_name,
 305                                              struct declaration_scope *scope)
 306 {
 307         return g_hash_table_lookup(scope->struct_declarations,
 308                                    (gconstpointer) (unsigned long) struct_name);
 309 }
 310
 311 struct declaration_struct *lookup_struct_declaration(GQuark struct_name,
 312                                        struct declaration_scope *scope)
 313 {
 314         struct declaration_struct *declaration;
 315
 316         while (scope) {
 317                 declaration = lookup_struct_declaration_scope(struct_name, scope);
 318                 if (declaration)
 319                         return declaration;
 320                 scope = scope->parent_scope;
 321         }
 322         return NULL;
 323 }
 324
 325 int register_struct_declaration(GQuark struct_name,
 326         struct declaration_struct *struct_declaration,
 327         struct declaration_scope *scope)
 328 {
 329         GQuark prefix_name;
 330         int ret;
 331
 332         if (!struct_name)
 333                 return -EPERM;
 334
 335         /* Only lookup in local scope */
 336         if (lookup_struct_declaration_scope(struct_name, scope))
 337                 return -EEXIST;
 338
 339         g_hash_table_insert(scope->struct_declarations,
 340                             (gpointer) (unsigned long) struct_name,
 341                             struct_declaration);
 342         declaration_ref(&struct_declaration->p);
 343
 344         /* Also add in typedef/typealias scopes */
 345         prefix_name = prefix_quark("struct ", struct_name);
 346         ret = register_declaration(prefix_name, &struct_declaration->p, scope);
 347         assert(!ret);
 348         return 0;
 349 }
 350
 351 static
 352 struct declaration_untagged_variant *
 353         lookup_variant_declaration_scope(GQuark variant_name,
 354                 struct declaration_scope *scope)
 355 {
 356         return g_hash_table_lookup(scope->variant_declarations,
 357                                    (gconstpointer) (unsigned long) variant_name);
 358 }
 359
 360 struct declaration_untagged_variant *
 361         lookup_variant_declaration(GQuark variant_name,
 362                 struct declaration_scope *scope)
 363 {
 364         struct declaration_untagged_variant *declaration;
 365
 366         while (scope) {
 367                 declaration = lookup_variant_declaration_scope(variant_name, scope);
 368                 if (declaration)
 369                         return declaration;
 370                 scope = scope->parent_scope;
 371         }
 372         return NULL;
 373 }
 374
 375 int register_variant_declaration(GQuark variant_name,
 376                 struct declaration_untagged_variant *untagged_variant_declaration,
 377                 struct declaration_scope *scope)
 378 {
 379         GQuark prefix_name;
 380         int ret;
 381
 382         if (!variant_name)
 383                 return -EPERM;
 384
 385         /* Only lookup in local scope */
 386         if (lookup_variant_declaration_scope(variant_name, scope))
 387                 return -EEXIST;
 388
 389         g_hash_table_insert(scope->variant_declarations,
 390                             (gpointer) (unsigned long) variant_name,
 391                             untagged_variant_declaration);
 392         declaration_ref(&untagged_variant_declaration->p);
 393
 394         /* Also add in typedef/typealias scopes */
 395         prefix_name = prefix_quark("variant ", variant_name);
 396         ret = register_declaration(prefix_name,
 397                         &untagged_variant_declaration->p, scope);
 398         assert(!ret);
 399         return 0;
 400 }
 401
 402 static
 403 struct declaration_enum *
 404         lookup_enum_declaration_scope(GQuark enum_name,
 405                 struct declaration_scope *scope)
 406 {
 407         return g_hash_table_lookup(scope->enum_declarations,
 408                                    (gconstpointer) (unsigned long) enum_name);
 409 }
 410
 411 struct declaration_enum *
 412         lookup_enum_declaration(GQuark enum_name,
 413                 struct declaration_scope *scope)
 414 {
 415         struct declaration_enum *declaration;
 416
 417         while (scope) {
 418                 declaration = lookup_enum_declaration_scope(enum_name, scope);
 419                 if (declaration)
 420                         return declaration;
 421                 scope = scope->parent_scope;
 422         }
 423         return NULL;
 424 }
 425
 426 int register_enum_declaration(GQuark enum_name,
 427                 struct declaration_enum *enum_declaration,
 428                 struct declaration_scope *scope)
 429 {
 430         GQuark prefix_name;
 431         int ret;
 432
 433         if (!enum_name)
 434                 return -EPERM;
 435
 436         /* Only lookup in local scope */
 437         if (lookup_enum_declaration_scope(enum_name, scope))
 438                 return -EEXIST;
 439
 440         g_hash_table_insert(scope->enum_declarations,
 441                             (gpointer) (unsigned long) enum_name,
 442                             enum_declaration);
 443         declaration_ref(&enum_declaration->p);
 444
 445         /* Also add in typedef/typealias scopes */
 446         prefix_name = prefix_quark("enum ", enum_name);
 447         ret = register_declaration(prefix_name, &enum_declaration->p, scope);
 448         assert(!ret);
 449         return 0;
 450 }
 451
 452 static struct definition_scope *
 453         _new_definition_scope(struct definition_scope *parent_scope,
 454                               int scope_path_len)
 455 {
 456         struct definition_scope *scope = g_new(struct definition_scope, 1);
 457
 458         scope->definitions = g_hash_table_new_full(g_direct_hash,
 459                                         g_direct_equal, NULL,
 460                                         (GDestroyNotify) definition_unref);
 461         scope->parent_scope = parent_scope;
 462         scope->scope_path = g_array_sized_new(FALSE, TRUE, sizeof(GQuark),
 463                                               scope_path_len);
 464         g_array_set_size(scope->scope_path, scope_path_len);
 465         return scope;
 466 }
 467
 468 struct definition_scope *
 469         new_definition_scope(struct definition_scope *parent_scope,
 470                              GQuark field_name)
 471 {
 472         struct definition_scope *scope;
 473         int scope_path_len = 1;
 474
 475         if (parent_scope)
 476                 scope_path_len += parent_scope->scope_path->len;
 477         scope = _new_definition_scope(parent_scope, scope_path_len);
 478         if (parent_scope)
 479                 memcpy(scope->scope_path, parent_scope->scope_path,
 480                        sizeof(GQuark) * (scope_path_len - 1));
 481         g_array_index(scope->scope_path, GQuark, scope_path_len - 1) =
 482                 field_name;
 483         return scope;
 484 }
 485
 486 /*
 487  * in: path (dot separated), out: q (GArray of GQuark)
 488  */
 489 void append_scope_path(const char *path, GArray *q)
 490 {
 491         const char *ptrbegin, *ptrend = path;
 492         GQuark quark;
 493
 494         for (;;) {
 495                 char *str;
 496                 size_t len;
 497
 498                 ptrbegin = ptrend;
 499                 ptrend = strchr(ptrbegin, '.');
 500                 if (!ptrend)
 501                         break;
 502                 len = ptrend - ptrbegin;
 503                 /* Don't accept two consecutive dots */
 504                 assert(len != 0);
 505                 str = g_new(char, len + 1);     /* include \0 */
 506                 memcpy(str, ptrbegin, len);
 507                 str[len] = '\0';
 508                 quark = g_quark_from_string(str);
 509                 g_array_append_val(q, quark);
 510                 g_free(str);
 511                 ptrend++;       /* skip current dot */
 512         }
 513         /* last. Check for trailing dot (and discard). */
 514         if (ptrbegin[0] != '\0') {
 515                 quark = g_quark_from_string(ptrbegin);
 516                 g_array_append_val(q, quark);
 517         }
 518 }
 519
 520 void set_dynamic_definition_scope(struct definition *definition,
 521                                   struct definition_scope *scope,
 522                                   const char *root_name)
 523 {
 524         g_array_set_size(scope->scope_path, 0);
 525         append_scope_path(root_name, scope->scope_path);
 526         /*
 527          * Use INT_MAX order to ensure that all fields of the parent
 528          * scope are seen as being prior to this scope.
 529          */
 530         definition->index = INT_MAX;
 531 }
 532
 533 void free_definition_scope(struct definition_scope *scope)
 534 {
 535         g_array_free(scope->scope_path, TRUE);
 536         g_hash_table_destroy(scope->definitions);
 537         g_free(scope);
 538 }