lib/ctf-ir/resolve.c

   1 /*
   2  * resolve.c
   3  *
   4  * Babeltrace - CTF IR: Type resolving internal
   5  *
   6  * Copyright 2015 Jérémie Galarneau <jeremie.galarneau@efficios.com>
   7  * Copyright 2016 Philippe Proulx <pproulx@efficios.com>
   8  *
   9  * Authors: Jérémie Galarneau <jeremie.galarneau@efficios.com>
  10  *          Philippe Proulx <pproulx@efficios.com>
  11  *
  12  * Permission is hereby granted, free of charge, to any person obtaining a copy
  13  * of this software and associated documentation files (the "Software"), to deal
  14  * in the Software without restriction, including without limitation the rights
  15  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  16  * copies of the Software, and to permit persons to whom the Software is
  17  * furnished to do so, subject to the following conditions:
  18  *
  19  * The above copyright notice and this permission notice shall be included in
  20  * all copies or substantial portions of the Software.
  21  *
  22  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  23  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  24  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  25  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  26  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  27  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  28  * SOFTWARE.
  29  */
  30
  31 #include <babeltrace/ctf-ir/event.h>
  32 #include <babeltrace/ctf-ir/stream-class.h>
  33 #include <babeltrace/ctf-ir/resolve-internal.h>
  34 #include <babeltrace/ctf-ir/field-types.h>
  35 #include <babeltrace/ctf-ir/field-path.h>
  36 #include <babeltrace/ctf-ir/field-path-internal.h>
  37 #include <babeltrace/ctf-ir/event-internal.h>
  38 #include <babeltrace/ref.h>
  39 #include <babeltrace/babeltrace-internal.h>
  40 #include <babeltrace/values.h>
  41 #include <limits.h>
  42 #include <glib.h>
  43
  44 #define _printf_error(fmt, args...) \
  45         printf_verbose("[resolving] " fmt, ## args)
  46
  47 typedef GPtrArray type_stack;
  48
  49 /*
  50  * A stack frame.
  51  *
  52  * `type` contains a compound field type (structure, variant, array,
  53  * or sequence) and `index` indicates the index of the field type in
  54  * the upper frame (-1 for array and sequence field types).
  55  *
  56  * `type` is owned by the stack frame.
  57  */
  58 struct type_stack_frame {
  59         struct bt_ctf_field_type *type;
  60         int index;
  61 };
  62
  63 /*
  64  * The current context of the resolving engine.
  65  *
  66  * `scopes` contain the 6 CTF scope field types (see CTF, sect. 7.3.2)
  67  * in the following order:
  68  *
  69  *   * Packet header
  70  *   * Packet context
  71  *   * Event header
  72  *   * Stream event context
  73  *   * Event context
  74  *   * Event payload
  75  */
  76 struct resolve_context {
  77         struct bt_value *environment;
  78         struct bt_ctf_field_type *scopes[6];
  79
  80         /* Root scope being visited */
  81         enum bt_ctf_scope root_scope;
  82         type_stack *type_stack;
  83         struct bt_ctf_field_type *cur_field_type;
  84 };
  85
  86 /* TSDL dynamic scope prefixes as defined in CTF Section 7.3.2 */
  87 static const char * const absolute_path_prefixes[] = {
  88         [BT_CTF_SCOPE_ENV]                      = "env.",
  89         [BT_CTF_SCOPE_TRACE_PACKET_HEADER]      = "trace.packet.header.",
  90         [BT_CTF_SCOPE_STREAM_PACKET_CONTEXT]    = "stream.packet.context.",
  91         [BT_CTF_SCOPE_STREAM_EVENT_HEADER]      = "stream.event.header.",
  92         [BT_CTF_SCOPE_STREAM_EVENT_CONTEXT]     = "stream.event.context.",
  93         [BT_CTF_SCOPE_EVENT_CONTEXT]            = "event.context.",
  94         [BT_CTF_SCOPE_EVENT_FIELDS]             = "event.fields.",
  95 };
  96
  97 /* Number of path tokens used for the absolute prefixes */
  98 static const int absolute_path_prefix_ptoken_counts[] = {
  99         [BT_CTF_SCOPE_ENV]                      = 1,
 100         [BT_CTF_SCOPE_TRACE_PACKET_HEADER]      = 3,
 101         [BT_CTF_SCOPE_STREAM_PACKET_CONTEXT]    = 3,
 102         [BT_CTF_SCOPE_STREAM_EVENT_HEADER]      = 3,
 103         [BT_CTF_SCOPE_STREAM_EVENT_CONTEXT]     = 3,
 104         [BT_CTF_SCOPE_EVENT_CONTEXT]            = 2,
 105         [BT_CTF_SCOPE_EVENT_FIELDS]             = 2,
 106 };
 107
 108 /*
 109  * Destroys a type stack frame.
 110  */
 111 static
 112 void type_stack_destroy_notify(gpointer data)
 113 {
 114         struct type_stack_frame *frame = data;
 115
 116         BT_PUT(frame->type);
 117         g_free(frame);
 118 }
 119
 120 /*
 121  * Creates a type stack.
 122  *
 123  * Return value is owned by the caller.
 124  */
 125 static
 126 type_stack *type_stack_create(void)
 127 {
 128         return g_ptr_array_new_with_free_func(type_stack_destroy_notify);
 129 }
 130
 131 /*
 132  * Destroys a type stack.
 133  */
 134 static
 135 void type_stack_destroy(type_stack *stack)
 136 {
 137         g_ptr_array_free(stack, TRUE);
 138 }
 139
 140 /*
 141  * Pushes a field type onto a type stack.
 142  *
 143  * `type` is owned by the caller (stack frame gets a new reference).
 144  */
 145 static
 146 int type_stack_push(type_stack *stack, struct bt_ctf_field_type *type)
 147 {
 148         int ret = 0;
 149         struct type_stack_frame *frame = NULL;
 150
 151         if (!stack || !type) {
 152                 ret = -1;
 153                 goto end;
 154         }
 155
 156         frame = g_new0(struct type_stack_frame, 1);
 157         if (!frame) {
 158                 ret = -1;
 159                 goto end;
 160         }
 161
 162         frame->type = bt_get(type);
 163         g_ptr_array_add(stack, frame);
 164
 165 end:
 166         return ret;
 167 }
 168
 169 /*
 170  * Checks whether or not `stack` is empty.
 171  */
 172 static
 173 bool type_stack_empty(type_stack *stack)
 174 {
 175         return stack->len == 0;
 176 }
 177
 178 /*
 179  * Returns the number of frames in `stack`.
 180  */
 181 static
 182 size_t type_stack_size(type_stack *stack)
 183 {
 184         return stack->len;
 185 }
 186
 187 /*
 188  * Returns the top frame of `stack`.
 189  *
 190  * Return value is owned by `stack`.
 191  */
 192 static
 193 struct type_stack_frame *type_stack_peek(type_stack *stack)
 194 {
 195         struct type_stack_frame *entry = NULL;
 196
 197         if (!stack || type_stack_empty(stack)) {
 198                 goto end;
 199         }
 200
 201         entry = g_ptr_array_index(stack, stack->len - 1);
 202 end:
 203         return entry;
 204 }
 205
 206 /*
 207  * Returns the frame at index `index` in `stack`.
 208  *
 209  * Return value is owned by `stack`.
 210  */
 211 static
 212 struct type_stack_frame *type_stack_at(type_stack *stack,
 213                 size_t index)
 214 {
 215         struct type_stack_frame *entry = NULL;
 216
 217         if (!stack || index >= stack->len) {
 218                 goto end;
 219         }
 220
 221         entry = g_ptr_array_index(stack, index);
 222
 223 end:
 224         return entry;
 225 }
 226
 227 /*
 228  * Removes the top frame of `stack`.
 229  */
 230 static
 231 void type_stack_pop(type_stack *stack)
 232 {
 233         if (!type_stack_empty(stack)) {
 234                 /*
 235                  * This will call the frame's destructor and free it, as
 236                  * well as put its contained field type.
 237                  */
 238                 g_ptr_array_set_size(stack, stack->len - 1);
 239         }
 240 }
 241
 242 /*
 243  * Returns the scope field type of `scope` in the context `ctx`.
 244  *
 245  * Return value is owned by `ctx` on success.
 246  */
 247 static
 248 struct bt_ctf_field_type *get_type_from_ctx(struct resolve_context *ctx,
 249                 enum bt_ctf_scope scope)
 250 {
 251         assert(scope >= BT_CTF_SCOPE_TRACE_PACKET_HEADER &&
 252                 scope <= BT_CTF_SCOPE_EVENT_FIELDS);
 253
 254         return ctx->scopes[scope - BT_CTF_SCOPE_TRACE_PACKET_HEADER];
 255 }
 256
 257 /*
 258  * Returns the CTF scope from a path string. May return
 259  * CTF_NODE_UNKNOWN if the path is found to be relative.
 260  */
 261 static
 262 enum bt_ctf_scope get_root_scope_from_absolute_pathstr(const char *pathstr)
 263 {
 264         enum bt_ctf_scope scope;
 265         enum bt_ctf_scope ret = BT_CTF_SCOPE_UNKNOWN;
 266         const size_t prefixes_count = sizeof(absolute_path_prefixes) /
 267                 sizeof(*absolute_path_prefixes);
 268
 269         for (scope = BT_CTF_SCOPE_ENV; scope < BT_CTF_SCOPE_ENV +
 270                         prefixes_count; scope++) {
 271                 /*
 272                  * Chech if path string starts with a known absolute
 273                  * path prefix.
 274                  *
 275                  * Refer to CTF 7.3.2 STATIC AND DYNAMIC SCOPES.
 276                  */
 277                 if (strncmp(pathstr, absolute_path_prefixes[scope],
 278                                 strlen(absolute_path_prefixes[scope]))) {
 279                         /* Prefix does not match: try the next one */
 280                         continue;
 281                 }
 282
 283                 /* Found it! */
 284                 ret = scope;
 285                 goto end;
 286         }
 287
 288 end:
 289         return ret;
 290 }
 291
 292 /*
 293  * Destroys a path token.
 294  */
 295 static
 296 void ptokens_destroy_func(gpointer ptoken, gpointer data)
 297 {
 298         g_string_free(ptoken, TRUE);
 299 }
 300
 301 /*
 302  * Destroys a path token list.
 303  */
 304 static
 305 void ptokens_destroy(GList *ptokens)
 306 {
 307         if (!ptokens) {
 308                 return;
 309         }
 310
 311         g_list_foreach(ptokens, ptokens_destroy_func, NULL);
 312         g_list_free(ptokens);
 313 }
 314
 315 /*
 316  * Returns the string contained in a path token.
 317  */
 318 static
 319 const char *ptoken_get_string(GList *ptoken)
 320 {
 321         GString *tokenstr = (GString *) ptoken->data;
 322
 323         return tokenstr->str;
 324 }
 325
 326 /*
 327  * Converts a path string to a path token list, that is, splits the
 328  * individual words of a path string into a list of individual
 329  * strings.
 330  *
 331  * Return value is owned by the caller on success.
 332  */
 333 static
 334 GList *pathstr_to_ptokens(const char *pathstr)
 335 {
 336         const char *at = pathstr;
 337         const char *last = at;
 338         GList *ptokens = NULL;
 339
 340         for (;;) {
 341                 if (*at == '.' || *at == '\0') {
 342                         GString *tokenstr;
 343
 344                         if (at == last) {
 345                                 /* Error: empty token */
 346                                 _printf_error("Empty token in path string at position %d\n",
 347                                         (int) (at - pathstr));
 348                                 goto error;
 349                         }
 350
 351                         tokenstr = g_string_new(NULL);
 352                         g_string_append_len(tokenstr, last, at - last);
 353                         ptokens = g_list_append(ptokens, tokenstr);
 354                         last = at + 1;
 355                 }
 356
 357                 if (*at == '\0') {
 358                         break;
 359                 }
 360
 361                 at++;
 362         }
 363
 364         return ptokens;
 365
 366 error:
 367         ptokens_destroy(ptokens);
 368         return NULL;
 369 }
 370
 371 /*
 372  * Converts a path token list to a field path object. The path token
 373  * list is relative from `type`. The index of the source looking for
 374  * its target within `type` is indicated by `src_index`. This can be
 375  * `INT_MAX` if the source is contained in `type`.
 376  *
 377  * `ptokens` is owned by the caller. `field_path` is an output parameter
 378  * owned by the caller that must be filled here. `type` is owned by the
 379  * caller.
 380  */
 381 static
 382 int ptokens_to_field_path(GList *ptokens, struct bt_ctf_field_path *field_path,
 383                 struct bt_ctf_field_type *type, int src_index)
 384 {
 385         int ret = 0;
 386         GList *cur_ptoken = ptokens;
 387         bool first_level_done = false;
 388
 389         /* Get our own reference */
 390         bt_get(type);
 391
 392         /* Locate target */
 393         while (cur_ptoken) {
 394                 int child_index;
 395                 struct bt_ctf_field_type *child_type;
 396                 const char *field_name = ptoken_get_string(cur_ptoken);
 397                 enum bt_ctf_type_id type_id =
 398                         bt_ctf_field_type_get_type_id(type);
 399
 400                 /* Find to which index corresponds the current path token */
 401                 if (type_id == CTF_TYPE_ARRAY || type_id == CTF_TYPE_SEQUENCE) {
 402                         child_index = -1;
 403                 } else {
 404                         child_index = bt_ctf_field_type_get_field_index(type,
 405                                 field_name);
 406                         if (child_index < 0) {
 407                                 /*
 408                                  * Error: field name does not exist or
 409                                  * wrong current type.
 410                                  */
 411                                 _printf_error("Cannot get index of field type named \"%s\"\n",
 412                                         field_name);
 413                                 ret = -1;
 414                                 goto end;
 415                         } else if (child_index > src_index &&
 416                                         !first_level_done) {
 417                                 _printf_error("Child type is located after source index (%d)\n",
 418                                         src_index);
 419                                 ret = -1;
 420                                 goto end;
 421                         }
 422
 423                         /* Next path token */
 424                         cur_ptoken = g_list_next(cur_ptoken);
 425                         first_level_done = true;
 426                 }
 427
 428                 /* Create new field path entry */
 429                 g_array_append_val(field_path->indexes, child_index);
 430
 431                 /* Get child field type */
 432                 child_type = bt_ctf_field_type_get_field_at_index(type,
 433                         child_index);
 434                 if (!child_type) {
 435                         _printf_error("Cannot get child type at index %d (field \"%s\")\n",
 436                                 child_index, field_name);
 437                         ret = -1;
 438                         goto end;
 439                 }
 440
 441                 /* Move child type to current type */
 442                 BT_MOVE(type, child_type);
 443         }
 444
 445 end:
 446         bt_put(type);
 447         return ret;
 448 }
 449
 450 /*
 451  * Converts a known absolute path token list to a field path object
 452  * within the resolving context `ctx`.
 453  *
 454  * `ptokens` is owned by the caller. `field_path` is an output parameter
 455  * owned by the caller that must be filled here.
 456  */
 457 static
 458 int absolute_ptokens_to_field_path(GList *ptokens,
 459                 struct bt_ctf_field_path *field_path,
 460                 struct resolve_context *ctx)
 461 {
 462         int ret = 0;
 463         GList *cur_ptoken;
 464         struct bt_ctf_field_type *type;
 465
 466         /* Skip absolute path tokens */
 467         cur_ptoken = g_list_nth(ptokens,
 468                 absolute_path_prefix_ptoken_counts[field_path->root]);
 469
 470         /* Start with root type */
 471         type = get_type_from_ctx(ctx, field_path->root);
 472         if (!type) {
 473                 /* Error: root type is not available */
 474                 _printf_error("Root type with scope type %d is not available\n",
 475                         field_path->root);
 476                 ret = -1;
 477                 goto end;
 478         }
 479
 480         /* Locate target */
 481         ret = ptokens_to_field_path(cur_ptoken, field_path, type, INT_MAX);
 482
 483 end:
 484         return ret;
 485 }
 486
 487 /*
 488  * Converts a known relative path token list to a field path object
 489  * within the resolving context `ctx`.
 490  *
 491  * `ptokens` is owned by the caller. `field_path` is an output parameter
 492  * owned by the caller that must be filled here.
 493  */
 494 static
 495 int relative_ptokens_to_field_path(GList *ptokens,
 496                 struct bt_ctf_field_path *field_path,
 497                 struct resolve_context *ctx)
 498 {
 499         int ret = 0;
 500         int parent_pos_in_stack;
 501         struct bt_ctf_field_path *tail_field_path = bt_ctf_field_path_create();
 502
 503         if (!tail_field_path) {
 504                 _printf_error("Cannot create field path\n");
 505                 ret = -1;
 506                 goto end;
 507         }
 508
 509         parent_pos_in_stack = type_stack_size(ctx->type_stack) - 1;
 510
 511         while (parent_pos_in_stack >= 0) {
 512                 struct bt_ctf_field_type *parent_type =
 513                         type_stack_at(ctx->type_stack,
 514                                 parent_pos_in_stack)->type;
 515                 int cur_index = type_stack_at(ctx->type_stack,
 516                         parent_pos_in_stack)->index;
 517
 518                 /* Locate target from current parent type */
 519                 ret = ptokens_to_field_path(ptokens, tail_field_path,
 520                         parent_type, cur_index);
 521                 if (ret) {
 522                         /* Not found... yet */
 523                         bt_ctf_field_path_clear(tail_field_path);
 524                 } else {
 525                         /* Found: stitch tail field path to head field path */
 526                         int i = 0;
 527                         int tail_field_path_len =
 528                                 tail_field_path->indexes->len;
 529
 530                         while (true) {
 531                                 struct bt_ctf_field_type *cur_type =
 532                                         type_stack_at(ctx->type_stack, i)->type;
 533                                 int index = type_stack_at(
 534                                         ctx->type_stack, i)->index;
 535
 536                                 if (cur_type == parent_type) {
 537                                         break;
 538                                 }
 539
 540                                 g_array_append_val(field_path->indexes,
 541                                         index);
 542                                 i++;
 543                         }
 544
 545                         for (i = 0; i < tail_field_path_len; i++) {
 546                                 int index = g_array_index(
 547                                         tail_field_path->indexes,
 548                                         int, i);
 549
 550                                 g_array_append_val(field_path->indexes,
 551                                         index);
 552                         }
 553                         break;
 554                 }
 555
 556                 parent_pos_in_stack--;
 557         }
 558
 559         if (parent_pos_in_stack < 0) {
 560                 /* Not found: look in previous scopes */
 561                 field_path->root--;
 562
 563                 while (field_path->root >= BT_CTF_SCOPE_TRACE_PACKET_HEADER) {
 564                         struct bt_ctf_field_type *root_type;
 565                         bt_ctf_field_path_clear(field_path);
 566
 567                         root_type = get_type_from_ctx(ctx, field_path->root);
 568                         if (!root_type) {
 569                                 field_path->root--;
 570                                 continue;
 571                         }
 572
 573                         /* Locate target in previous scope */
 574                         ret = ptokens_to_field_path(ptokens, field_path,
 575                                 root_type, INT_MAX);
 576                         if (ret) {
 577                                 /* Not found yet */
 578                                 field_path->root--;
 579                                 continue;
 580                         }
 581
 582                         /* Found */
 583                         break;
 584                 }
 585         }
 586
 587 end:
 588         BT_PUT(tail_field_path);
 589         return ret;
 590 }
 591
 592 /*
 593  * Converts a path string to a field path object within the resolving
 594  * context `ctx`.
 595  *
 596  * Return value is owned by the caller on success.
 597  */
 598 static
 599 struct bt_ctf_field_path *pathstr_to_field_path(const char *pathstr,
 600                 struct resolve_context *ctx)
 601 {
 602         int ret;
 603         enum bt_ctf_scope root_scope;
 604         GList *ptokens = NULL;
 605         struct bt_ctf_field_path *field_path = NULL;
 606
 607         /* Create field path */
 608         field_path = bt_ctf_field_path_create();
 609         if (!field_path) {
 610                 _printf_error("Cannot create field path\n");
 611                 ret = -1;
 612                 goto end;
 613         }
 614
 615         /* Convert path string to path tokens */
 616         ptokens = pathstr_to_ptokens(pathstr);
 617         if (!ptokens) {
 618                 _printf_error("Cannot convert path string \"%s\" to path tokens\n",
 619                         pathstr);
 620                 ret = -1;
 621                 goto end;
 622         }
 623
 624         /* Absolute or relative path? */
 625         root_scope = get_root_scope_from_absolute_pathstr(pathstr);
 626
 627         if (root_scope == BT_CTF_SCOPE_UNKNOWN) {
 628                 /* Relative path: start with current root scope */
 629                 field_path->root = ctx->root_scope;
 630                 ret = relative_ptokens_to_field_path(ptokens, field_path, ctx);
 631                 if (ret) {
 632                         _printf_error("Cannot get relative field path of path string \"%s\"\n",
 633                                 pathstr);
 634                         _printf_error("  Starting at root scope %d, finished at root scope %d\n",
 635                                 ctx->root_scope, field_path->root);
 636                         goto end;
 637                 }
 638         } else if (root_scope == BT_CTF_SCOPE_ENV) {
 639                 _printf_error("Sequence field types referring the trace environment are not supported as of this version\n");
 640                 ret = -1;
 641                 goto end;
 642         } else {
 643                 /* Absolute path: use found root scope */
 644                 field_path->root = root_scope;
 645                 ret = absolute_ptokens_to_field_path(ptokens, field_path, ctx);
 646                 if (ret) {
 647                         _printf_error("Cannot get absolute field path of path string \"%s\"\n",
 648                                 pathstr);
 649                         _printf_error("  Looking in root scope %d\n", root_scope);
 650                         goto end;
 651                 }
 652         }
 653
 654 end:
 655         if (ret) {
 656                 BT_PUT(field_path);
 657         }
 658
 659         ptokens_destroy(ptokens);
 660
 661         return field_path;
 662 }
 663
 664 /*
 665  * Retrieves a field type by following the field path `field_path` in
 666  * the resolving context `ctx`.
 667  *
 668  * Return value is owned by the caller on success.
 669  */
 670 static
 671 struct bt_ctf_field_type *field_path_to_field_type(
 672                 struct bt_ctf_field_path *field_path,
 673                 struct resolve_context *ctx)
 674 {
 675         int i;
 676         struct bt_ctf_field_type *type;
 677
 678         /* Start with root type */
 679         type = get_type_from_ctx(ctx, field_path->root);
 680         bt_get(type);
 681         if (!type) {
 682                 /* Error: root type is not available */
 683                 _printf_error("Root type with scope type %d is not available\n",
 684                         field_path->root);
 685                 goto error;
 686         }
 687
 688         /* Locate target */
 689         for (i = 0; i < field_path->indexes->len; i++) {
 690                 struct bt_ctf_field_type *child_type;
 691                 int child_index =
 692                         g_array_index(field_path->indexes, int, i);
 693
 694                 /* Get child field type */
 695                 child_type = bt_ctf_field_type_get_field_at_index(type,
 696                         child_index);
 697                 if (!child_type) {
 698                         _printf_error("Cannot get field type field at index %d\n",
 699                                 child_index);
 700                         goto error;
 701                 }
 702
 703                 /* Move child type to current type */
 704                 BT_MOVE(type, child_type);
 705         }
 706
 707         return type;
 708
 709 error:
 710         BT_PUT(type);
 711         return type;
 712 }
 713
 714 /*
 715  * Returns the equivalent field path object of the context type stack.
 716  *
 717  * Return value is owned by the caller on success.
 718  */
 719 static
 720 struct bt_ctf_field_path *get_ctx_stack_field_path(struct resolve_context *ctx)
 721 {
 722         int i;
 723         struct bt_ctf_field_path *field_path;
 724
 725         /* Create field path */
 726         field_path = bt_ctf_field_path_create();
 727         if (!field_path) {
 728                 _printf_error("Cannot create field path\n");
 729                 goto error;
 730         }
 731
 732         field_path->root = ctx->root_scope;
 733
 734         for (i = 0; i < type_stack_size(ctx->type_stack); i++) {
 735                 struct type_stack_frame *frame;
 736
 737                 frame = type_stack_at(ctx->type_stack, i);
 738                 g_array_append_val(field_path->indexes, frame->index);
 739         }
 740
 741         return field_path;
 742
 743 error:
 744         BT_PUT(field_path);
 745         return field_path;
 746 }
 747
 748 /*
 749  * Returns the lowest common ancestor of two field path objects
 750  * having the same root scope.
 751  *
 752  * `field_path1` and `field_path2` are owned by the caller.
 753  */
 754 int get_field_paths_lca_index(struct bt_ctf_field_path *field_path1,
 755                 struct bt_ctf_field_path *field_path2)
 756 {
 757         int lca_index = 0;
 758         int field_path1_len, field_path2_len;
 759
 760         /*
 761          * Start from both roots and find the first mismatch.
 762          */
 763         assert(field_path1->root == field_path2->root);
 764         field_path1_len = field_path1->indexes->len;
 765         field_path2_len = field_path2->indexes->len;
 766
 767         while (true) {
 768                 int target_index, ctx_index;
 769
 770                 if (lca_index == field_path2_len ||
 771                                 lca_index == field_path1_len) {
 772                         /*
 773                          * This means that both field paths never split.
 774                          * This is invalid because the target cannot be
 775                          * an ancestor of the source.
 776                          */
 777                         _printf_error("In source and target: one is an ancestor of the other\n");
 778                         lca_index = -1;
 779                         break;
 780                 }
 781
 782                 target_index = g_array_index(field_path1->indexes, int,
 783                         lca_index);
 784                 ctx_index = g_array_index(field_path2->indexes, int,
 785                         lca_index);
 786
 787                 if (target_index != ctx_index) {
 788                         /* LCA index is the previous */
 789                         break;
 790                 }
 791
 792                 lca_index++;
 793         }
 794
 795         return lca_index;
 796 }
 797
 798 /*
 799  * Validates a target field path.
 800  *
 801  * `target_field_path` and `target_type` are owned by the caller.
 802  */
 803 static
 804 int validate_target_field_path(struct bt_ctf_field_path *target_field_path,
 805                 struct bt_ctf_field_type *target_type,
 806                 struct resolve_context *ctx)
 807 {
 808         int ret = 0;
 809         struct bt_ctf_field_path *ctx_field_path;
 810         int target_field_path_len = target_field_path->indexes->len;
 811         int lca_index;
 812         int ctx_cur_field_type_id;
 813         int target_type_id;
 814
 815         /* Get context field path */
 816         ctx_field_path = get_ctx_stack_field_path(ctx);
 817         if (!ctx_field_path) {
 818                 _printf_error("Cannot get source field path\n");
 819                 ret = -1;
 820                 goto end;
 821         }
 822
 823         /*
 824          * Make sure the target is not a root.
 825          */
 826         if (target_field_path_len == 0) {
 827                 _printf_error("Target field path's length is 0 (targeting the root)\n");
 828                 ret = -1;
 829                 goto end;
 830         }
 831
 832         /*
 833          * Make sure the root of the target field path is not located
 834          * after the context field path's root.
 835          */
 836         if (target_field_path->root > ctx_field_path->root) {
 837                 _printf_error("Target is located after source\n");
 838                 ret = -1;
 839                 goto end;
 840         }
 841
 842         if (target_field_path->root == ctx_field_path->root) {
 843                 int target_index, ctx_index;
 844
 845                 /*
 846                  * Find the index of the lowest common ancestor of both field
 847                  * paths.
 848                  */
 849                 lca_index = get_field_paths_lca_index(target_field_path,
 850                         ctx_field_path);
 851                 if (lca_index < 0) {
 852                         _printf_error("Cannot get least common ancestor\n");
 853                         ret = -1;
 854                         goto end;
 855                 }
 856
 857                 /*
 858                  * Make sure the target field path is located before the
 859                  * context field path.
 860                  */
 861                 target_index = g_array_index(target_field_path->indexes,
 862                         int, lca_index);
 863                 ctx_index = g_array_index(ctx_field_path->indexes,
 864                         int, lca_index);
 865
 866                 if (target_index >= ctx_index) {
 867                         _printf_error("Target index (%d) is greater or equal to source index (%d) in LCA\n",
 868                                 target_index, ctx_index);
 869                         ret = -1;
 870                         goto end;
 871                 }
 872         }
 873
 874         /*
 875          * Make sure the target type has the right type and properties.
 876          */
 877         ctx_cur_field_type_id = bt_ctf_field_type_get_type_id(
 878                 ctx->cur_field_type);
 879         target_type_id = bt_ctf_field_type_get_type_id(target_type);
 880
 881         if (ctx_cur_field_type_id == CTF_TYPE_VARIANT) {
 882                 if (target_type_id != CTF_TYPE_ENUM) {
 883                         _printf_error("Variant type's tag field type is not an enumeration\n");
 884                         ret = -1;
 885                         goto end;
 886                 }
 887         } else if (ctx_cur_field_type_id == CTF_TYPE_SEQUENCE) {
 888                 if (target_type_id != CTF_TYPE_INTEGER ||
 889                                 bt_ctf_field_type_integer_get_signed(
 890                                         target_type)) {
 891                         _printf_error("Sequence type's length field type is not an unsigned integer\n");
 892                         ret = -1;
 893                         goto end;
 894                 }
 895         } else {
 896                 assert(false);
 897         }
 898
 899 end:
 900         BT_PUT(ctx_field_path);
 901         return ret;
 902 }
 903
 904 /*
 905  * Resolves a variant or sequence field type `type`.
 906  *
 907  * `type` is owned by the caller.
 908  */
 909 static
 910 int resolve_sequence_or_variant_type(struct bt_ctf_field_type *type,
 911                 struct resolve_context *ctx)
 912 {
 913         int ret = 0;
 914         const char *pathstr;
 915         int type_id = bt_ctf_field_type_get_type_id(type);
 916         struct bt_ctf_field_path *target_field_path = NULL;
 917         struct bt_ctf_field_type *target_type = NULL;
 918
 919         /* Get path string */
 920         switch (type_id) {
 921         case CTF_TYPE_SEQUENCE:
 922                 pathstr =
 923                         bt_ctf_field_type_sequence_get_length_field_name(type);
 924                 break;
 925         case CTF_TYPE_VARIANT:
 926                 pathstr =
 927                         bt_ctf_field_type_variant_get_tag_name(type);
 928                 break;
 929         default:
 930                 assert(false);
 931                 ret = -1;
 932                 goto end;
 933         }
 934
 935         /* Get target field path out of path string */
 936         target_field_path = pathstr_to_field_path(pathstr, ctx);
 937         if (!target_field_path) {
 938                 _printf_error("Cannot get target field path for path string \"%s\"\n",
 939                         pathstr);
 940                 ret = -1;
 941                 goto end;
 942         }
 943
 944         /* Get target field type */
 945         target_type = field_path_to_field_type(target_field_path, ctx);
 946         if (!target_type) {
 947                 _printf_error("Cannot get target field type for path string \"%s\"\n",
 948                         pathstr);
 949                 ret = -1;
 950                 goto end;
 951         }
 952
 953         ret = validate_target_field_path(target_field_path, target_type, ctx);
 954         if (ret) {
 955                 _printf_error("Invalid target field path for path string \"%s\"\n",
 956                         pathstr);
 957                 goto end;
 958         }
 959
 960         /* Set target field path and target field type */
 961         if (type_id == CTF_TYPE_SEQUENCE) {
 962                 ret = bt_ctf_field_type_sequence_set_length_field_path(
 963                         type, target_field_path);
 964                 if (ret) {
 965                         _printf_error("Cannot set sequence field type's length field path\n");
 966                         goto end;
 967                 }
 968         } else if (type_id == CTF_TYPE_VARIANT) {
 969                 ret = bt_ctf_field_type_variant_set_tag_field_path(
 970                         type, target_field_path);
 971                 if (ret) {
 972                         _printf_error("Cannot set variant field type's tag field path\n");
 973                         goto end;
 974                 }
 975
 976                 ret = bt_ctf_field_type_variant_set_tag_field_type(
 977                         type, target_type);
 978                 if (ret) {
 979                         _printf_error("Cannot set variant field type's tag field type\n");
 980                         goto end;
 981                 }
 982         } else {
 983                 assert(false);
 984         }
 985
 986 end:
 987         BT_PUT(target_field_path);
 988         BT_PUT(target_type);
 989         return ret;
 990 }
 991
 992 /*
 993  * Resolves a field type `type`.
 994  *
 995  * `type` is owned by the caller.
 996  */
 997 static
 998 int resolve_type(struct bt_ctf_field_type *type, struct resolve_context *ctx)
 999 {
1000         int ret = 0;
1001         int type_id;
1002
1003         if (!type) {
1004                 /* Type is not available; still valid */
1005                 goto end;
1006         }
1007
1008         type_id = bt_ctf_field_type_get_type_id(type);
1009         ctx->cur_field_type = type;
1010
1011         /* Resolve sequence/variant field type */
1012         switch (type_id) {
1013         case CTF_TYPE_SEQUENCE:
1014         case CTF_TYPE_VARIANT:
1015                 ret = resolve_sequence_or_variant_type(type, ctx);
1016                 if (ret) {
1017                         _printf_error("Cannot resolve sequence or variant field type's length/tag\n");
1018                         goto end;
1019                 }
1020                 break;
1021         default:
1022                 break;
1023         }
1024
1025         /* Recurse into compound types */
1026         switch (type_id) {
1027         case CTF_TYPE_STRUCT:
1028         case CTF_TYPE_VARIANT:
1029         case CTF_TYPE_SEQUENCE:
1030         case CTF_TYPE_ARRAY:
1031         {
1032                 int field_count, f_index;
1033
1034                 ret = type_stack_push(ctx->type_stack, type);
1035                 if (ret) {
1036                         _printf_error("Cannot push field type on type stack\n");
1037                         _printf_error("  Stack size: %zu\n",
1038                                 type_stack_size(ctx->type_stack));
1039                         goto end;
1040                 }
1041
1042                 field_count = bt_ctf_field_type_get_field_count(type);
1043                 if (field_count < 0) {
1044                         _printf_error("Cannot get field type field count\n");
1045                         ret = field_count;
1046                         goto end;
1047                 }
1048
1049                 for (f_index = 0; f_index < field_count; f_index++) {
1050                         struct bt_ctf_field_type *child_type =
1051                                 bt_ctf_field_type_get_field_at_index(type,
1052                                         f_index);
1053
1054                         if (!child_type) {
1055                                 _printf_error("Cannot get field type field at index %d/%d\n",
1056                                         f_index, field_count);
1057                                 ret = -1;
1058                                 goto end;
1059                         }
1060
1061                         if (type_id == CTF_TYPE_ARRAY ||
1062                                         type_id == CTF_TYPE_SEQUENCE) {
1063                                 type_stack_peek(ctx->type_stack)->index = -1;
1064                         } else {
1065                                 type_stack_peek(ctx->type_stack)->index =
1066                                         f_index;
1067                         }
1068
1069                         ret = resolve_type(child_type, ctx);
1070                         BT_PUT(child_type);
1071                         if (ret) {
1072                                 goto end;
1073                         }
1074                 }
1075
1076                 type_stack_pop(ctx->type_stack);
1077                 break;
1078         }
1079         default:
1080                 break;
1081         }
1082
1083 end:
1084         return ret;
1085 }
1086
1087 /*
1088  * Resolves the root field type corresponding to the scope `root_scope`.
1089  */
1090 static
1091 int resolve_root_type(enum bt_ctf_scope root_scope, struct resolve_context *ctx)
1092 {
1093         int ret;
1094
1095         assert(type_stack_size(ctx->type_stack) == 0);
1096         ctx->root_scope = root_scope;
1097         ret = resolve_type(get_type_from_ctx(ctx, root_scope), ctx);
1098         ctx->root_scope = BT_CTF_SCOPE_UNKNOWN;
1099
1100         return ret;
1101 }
1102
1103 BT_HIDDEN
1104 int bt_ctf_resolve_types(
1105                 struct bt_value *environment,
1106                 struct bt_ctf_field_type *packet_header_type,
1107                 struct bt_ctf_field_type *packet_context_type,
1108                 struct bt_ctf_field_type *event_header_type,
1109                 struct bt_ctf_field_type *stream_event_ctx_type,
1110                 struct bt_ctf_field_type *event_context_type,
1111                 struct bt_ctf_field_type *event_payload_type,
1112                 enum bt_ctf_resolve_flag flags)
1113 {
1114         int ret = 0;
1115         struct resolve_context ctx = {
1116                 .environment = environment,
1117                 .scopes = {
1118                         packet_header_type,
1119                         packet_context_type,
1120                         event_header_type,
1121                         stream_event_ctx_type,
1122                         event_context_type,
1123                         event_payload_type,
1124                 },
1125                 .root_scope = BT_CTF_SCOPE_UNKNOWN,
1126         };
1127
1128         /* Initialize type stack */
1129         ctx.type_stack = type_stack_create();
1130         if (!ctx.type_stack) {
1131                 printf_error("Cannot create type stack\n");
1132                 ret = -1;
1133                 goto end;
1134         }
1135
1136         /* Resolve packet header type */
1137         if (flags & BT_CTF_RESOLVE_FLAG_PACKET_HEADER) {
1138                 ret = resolve_root_type(BT_CTF_SCOPE_TRACE_PACKET_HEADER, &ctx);
1139                 if (ret) {
1140                         _printf_error("Cannot resolve trace packet header type\n");
1141                         goto end;
1142                 }
1143         }
1144
1145         /* Resolve packet context type */
1146         if (flags & BT_CTF_RESOLVE_FLAG_PACKET_CONTEXT) {
1147                 ret = resolve_root_type(BT_CTF_SCOPE_STREAM_PACKET_CONTEXT, &ctx);
1148                 if (ret) {
1149                         _printf_error("Cannot resolve stream packet context type\n");
1150                         goto end;
1151                 }
1152         }
1153
1154         /* Resolve event header type */
1155         if (flags & BT_CTF_RESOLVE_FLAG_EVENT_HEADER) {
1156                 ret = resolve_root_type(BT_CTF_SCOPE_STREAM_EVENT_HEADER, &ctx);
1157                 if (ret) {
1158                         _printf_error("Cannot resolve stream event header type\n");
1159                         goto end;
1160                 }
1161         }
1162
1163         /* Resolve stream event context type */
1164         if (flags & BT_CTF_RESOLVE_FLAG_STREAM_EVENT_CTX) {
1165                 ret = resolve_root_type(BT_CTF_SCOPE_STREAM_EVENT_CONTEXT, &ctx);
1166                 if (ret) {
1167                         _printf_error("Cannot resolve stream event context type\n");
1168                         goto end;
1169                 }
1170         }
1171
1172         /* Resolve event context type */
1173         if (flags & BT_CTF_RESOLVE_FLAG_EVENT_CONTEXT) {
1174                 ret = resolve_root_type(BT_CTF_SCOPE_EVENT_CONTEXT, &ctx);
1175                 if (ret) {
1176                         _printf_error("Cannot resolve event context type\n");
1177                         goto end;
1178                 }
1179         }
1180
1181         /* Resolve event payload type */
1182         if (flags & BT_CTF_RESOLVE_FLAG_EVENT_PAYLOAD) {
1183                 ret = resolve_root_type(BT_CTF_SCOPE_EVENT_FIELDS, &ctx);
1184                 if (ret) {
1185                         _printf_error("Cannot resolve event payload type\n");
1186                         goto end;
1187                 }
1188         }
1189
1190 end:
1191         type_stack_destroy(ctx.type_stack);
1192
1193         return ret;
1194 }