src/lib/trace-ir/resolve-field-path.c

   1 /*
   2  * SPDX-License-Identifier: MIT
   3  *
   4  * Copyright 2018 Philippe Proulx <pproulx@efficios.com>
   5  */
   6
   7 #define BT_LOG_TAG "LIB/RESOLVE-FIELD-PATH"
   8 #include "lib/logging.h"
   9
  10 #include "lib/assert-pre.h"
  11 #include "common/assert.h"
  12 #include <babeltrace2/trace-ir/field-path.h>
  13 #include <limits.h>
  14 #include <stdbool.h>
  15 #include <stdint.h>
  16 #include <inttypes.h>
  17 #include <glib.h>
  18
  19 #include "field-class.h"
  20 #include "field-path.h"
  21 #include "resolve-field-path.h"
  22
  23 static
  24 bool find_field_class_recursive(struct bt_field_class *fc,
  25                 struct bt_field_class *tgt_fc, struct bt_field_path *field_path)
  26 {
  27         bool found = false;
  28
  29         if (tgt_fc == fc) {
  30                 found = true;
  31                 goto end;
  32         }
  33
  34         if (bt_field_class_type_is(fc->type, BT_FIELD_CLASS_TYPE_OPTION)) {
  35                 struct bt_field_class_option *opt_fc = (void *) fc;
  36                 struct bt_field_path_item item = {
  37                         .type = BT_FIELD_PATH_ITEM_TYPE_CURRENT_OPTION_CONTENT,
  38                         .index = UINT64_C(-1),
  39                 };
  40
  41                 bt_field_path_append_item(field_path, &item);
  42                 found = find_field_class_recursive(opt_fc->content_fc,
  43                         tgt_fc, field_path);
  44                 if (found) {
  45                         goto end;
  46                 }
  47
  48                 bt_field_path_remove_last_item(field_path);
  49         } else if (fc->type == BT_FIELD_CLASS_TYPE_STRUCTURE ||
  50                         bt_field_class_type_is(fc->type,
  51                                 BT_FIELD_CLASS_TYPE_VARIANT)) {
  52                 struct bt_field_class_named_field_class_container *container_fc =
  53                         (void *) fc;
  54                 uint64_t i;
  55
  56                 for (i = 0; i < container_fc->named_fcs->len; i++) {
  57                         struct bt_named_field_class *named_fc =
  58                                 container_fc->named_fcs->pdata[i];
  59                         struct bt_field_path_item item = {
  60                                 .type = BT_FIELD_PATH_ITEM_TYPE_INDEX,
  61                                 .index = i,
  62                         };
  63
  64                         bt_field_path_append_item(field_path, &item);
  65                         found = find_field_class_recursive(named_fc->fc,
  66                                 tgt_fc, field_path);
  67                         if (found) {
  68                                 goto end;
  69                         }
  70
  71                         bt_field_path_remove_last_item(field_path);
  72                 }
  73         } else if (bt_field_class_type_is(fc->type, BT_FIELD_CLASS_TYPE_ARRAY)) {
  74                 struct bt_field_class_array *array_fc = (void *) fc;
  75                 struct bt_field_path_item item = {
  76                         .type = BT_FIELD_PATH_ITEM_TYPE_CURRENT_ARRAY_ELEMENT,
  77                         .index = UINT64_C(-1),
  78                 };
  79
  80                 bt_field_path_append_item(field_path, &item);
  81                 found = find_field_class_recursive(array_fc->element_fc,
  82                         tgt_fc, field_path);
  83                 if (found) {
  84                         goto end;
  85                 }
  86
  87                 bt_field_path_remove_last_item(field_path);
  88         }
  89
  90 end:
  91         return found;
  92 }
  93
  94 static
  95 int find_field_class(struct bt_field_class *root_fc,
  96                 enum bt_field_path_scope root_scope, struct bt_field_class *tgt_fc,
  97                 struct bt_field_path **ret_field_path)
  98 {
  99         int ret = 0;
 100         struct bt_field_path *field_path = NULL;
 101
 102         if (!root_fc) {
 103                 goto end;
 104         }
 105
 106         field_path = bt_field_path_create();
 107         if (!field_path) {
 108                 ret = -1;
 109                 goto end;
 110         }
 111
 112         field_path->root = root_scope;
 113         if (!find_field_class_recursive(root_fc, tgt_fc, field_path)) {
 114                 /* Not found here */
 115                 BT_OBJECT_PUT_REF_AND_RESET(field_path);
 116         }
 117
 118 end:
 119         *ret_field_path = field_path;
 120         return ret;
 121 }
 122
 123 static
 124 struct bt_field_path *find_field_class_in_ctx(struct bt_field_class *fc,
 125                 struct bt_resolve_field_path_context *ctx)
 126 {
 127         struct bt_field_path *field_path = NULL;
 128         int ret;
 129
 130         ret = find_field_class(ctx->packet_context, BT_FIELD_PATH_SCOPE_PACKET_CONTEXT,
 131                 fc, &field_path);
 132         if (ret || field_path) {
 133                 goto end;
 134         }
 135
 136         ret = find_field_class(ctx->event_common_context,
 137                 BT_FIELD_PATH_SCOPE_EVENT_COMMON_CONTEXT, fc, &field_path);
 138         if (ret || field_path) {
 139                 goto end;
 140         }
 141
 142         ret = find_field_class(ctx->event_specific_context,
 143                 BT_FIELD_PATH_SCOPE_EVENT_SPECIFIC_CONTEXT, fc, &field_path);
 144         if (ret || field_path) {
 145                 goto end;
 146         }
 147
 148         ret = find_field_class(ctx->event_payload, BT_FIELD_PATH_SCOPE_EVENT_PAYLOAD,
 149                 fc, &field_path);
 150         if (ret || field_path) {
 151                 goto end;
 152         }
 153
 154 end:
 155         return field_path;
 156 }
 157
 158 BT_ASSERT_PRE_DEV_FUNC
 159 static inline
 160 bool target_is_before_source(struct bt_field_path *src_field_path,
 161                 struct bt_field_path *tgt_field_path)
 162 {
 163         bool is_valid = true;
 164         uint64_t src_i = 0, tgt_i = 0;
 165
 166         if (tgt_field_path->root < src_field_path->root) {
 167                 goto end;
 168         }
 169
 170         if (tgt_field_path->root > src_field_path->root) {
 171                 is_valid = false;
 172                 goto end;
 173         }
 174
 175         BT_ASSERT(tgt_field_path->root == src_field_path->root);
 176
 177         for (src_i = 0, tgt_i = 0; src_i < src_field_path->items->len &&
 178                         tgt_i < tgt_field_path->items->len; src_i++, tgt_i++) {
 179                 struct bt_field_path_item *src_fp_item =
 180                         bt_field_path_borrow_item_by_index_inline(
 181                                 src_field_path, src_i);
 182                 struct bt_field_path_item *tgt_fp_item =
 183                         bt_field_path_borrow_item_by_index_inline(
 184                                 tgt_field_path, tgt_i);
 185
 186                 if (src_fp_item->type == BT_FIELD_PATH_ITEM_TYPE_INDEX &&
 187                                 tgt_fp_item->type == BT_FIELD_PATH_ITEM_TYPE_INDEX) {
 188                         if (tgt_fp_item->index > src_fp_item->index) {
 189                                 is_valid = false;
 190                                 goto end;
 191                         }
 192                 }
 193
 194                 src_i++;
 195                 tgt_i++;
 196         }
 197
 198 end:
 199         return is_valid;
 200 }
 201
 202 BT_ASSERT_PRE_DEV_FUNC
 203 static inline
 204 struct bt_field_class *borrow_root_field_class(
 205                 struct bt_resolve_field_path_context *ctx, enum bt_field_path_scope scope)
 206 {
 207         switch (scope) {
 208         case BT_FIELD_PATH_SCOPE_PACKET_CONTEXT:
 209                 return ctx->packet_context;
 210         case BT_FIELD_PATH_SCOPE_EVENT_COMMON_CONTEXT:
 211                 return ctx->event_common_context;
 212         case BT_FIELD_PATH_SCOPE_EVENT_SPECIFIC_CONTEXT:
 213                 return ctx->event_specific_context;
 214         case BT_FIELD_PATH_SCOPE_EVENT_PAYLOAD:
 215                 return ctx->event_payload;
 216         default:
 217                 bt_common_abort();
 218         }
 219
 220         return NULL;
 221 }
 222
 223 BT_ASSERT_PRE_DEV_FUNC
 224 static inline
 225 struct bt_field_class *borrow_child_field_class(
 226                 struct bt_field_class *parent_fc,
 227                 struct bt_field_path_item *fp_item)
 228 {
 229         struct bt_field_class *child_fc = NULL;
 230
 231         if (bt_field_class_type_is(parent_fc->type,
 232                         BT_FIELD_CLASS_TYPE_OPTION)) {
 233                 struct bt_field_class_option *opt_fc = (void *) parent_fc;
 234
 235                 BT_ASSERT(fp_item->type ==
 236                         BT_FIELD_PATH_ITEM_TYPE_CURRENT_OPTION_CONTENT);
 237                 child_fc = opt_fc->content_fc;
 238         } else if (parent_fc->type == BT_FIELD_CLASS_TYPE_STRUCTURE ||
 239                         bt_field_class_type_is(parent_fc->type,
 240                                 BT_FIELD_CLASS_TYPE_VARIANT)) {
 241                 struct bt_field_class_named_field_class_container *container_fc =
 242                         (void *) parent_fc;
 243                 struct bt_named_field_class *named_fc;
 244
 245                 BT_ASSERT(fp_item->type == BT_FIELD_PATH_ITEM_TYPE_INDEX);
 246                 named_fc = container_fc->named_fcs->pdata[fp_item->index];
 247                 child_fc = named_fc->fc;
 248         } else if (bt_field_class_type_is(parent_fc->type,
 249                         BT_FIELD_CLASS_TYPE_ARRAY)) {
 250                 struct bt_field_class_array *array_fc = (void *) parent_fc;
 251
 252                 BT_ASSERT(fp_item->type ==
 253                         BT_FIELD_PATH_ITEM_TYPE_CURRENT_ARRAY_ELEMENT);
 254                 child_fc = array_fc->element_fc;
 255         }
 256
 257         return child_fc;
 258 }
 259
 260 BT_ASSERT_PRE_DEV_FUNC
 261 static inline
 262 bool target_field_path_in_different_scope_has_struct_fc_only(
 263                 struct bt_field_path *src_field_path,
 264                 struct bt_field_path *tgt_field_path,
 265                 struct bt_resolve_field_path_context *ctx)
 266 {
 267         bool is_valid = true;
 268         uint64_t i = 0;
 269         struct bt_field_class *fc;
 270
 271         if (src_field_path->root == tgt_field_path->root) {
 272                 goto end;
 273         }
 274
 275         fc = borrow_root_field_class(ctx, tgt_field_path->root);
 276
 277         for (i = 0; i < tgt_field_path->items->len; i++) {
 278                 struct bt_field_path_item *fp_item =
 279                         bt_field_path_borrow_item_by_index_inline(
 280                                 tgt_field_path, i);
 281
 282                 if (bt_field_class_type_is(fc->type,
 283                                 BT_FIELD_CLASS_TYPE_ARRAY) ||
 284                                 bt_field_class_type_is(fc->type,
 285                                         BT_FIELD_CLASS_TYPE_OPTION) ||
 286                                 bt_field_class_type_is(fc->type,
 287                                         BT_FIELD_CLASS_TYPE_VARIANT)) {
 288                         is_valid = false;
 289                         goto end;
 290                 }
 291
 292                 BT_ASSERT(fp_item->type == BT_FIELD_PATH_ITEM_TYPE_INDEX);
 293                 fc = borrow_child_field_class(fc, fp_item);
 294         }
 295
 296 end:
 297         return is_valid;
 298 }
 299
 300 BT_ASSERT_PRE_DEV_FUNC
 301 static inline
 302 bool lca_is_structure_field_class(struct bt_field_path *src_field_path,
 303                 struct bt_field_path *tgt_field_path,
 304                 struct bt_resolve_field_path_context *ctx)
 305 {
 306         bool is_valid = true;
 307         struct bt_field_class *src_fc;
 308         struct bt_field_class *tgt_fc;
 309         struct bt_field_class *prev_fc = NULL;
 310         uint64_t src_i = 0, tgt_i = 0;
 311
 312         if (src_field_path->root != tgt_field_path->root) {
 313                 goto end;
 314         }
 315
 316         src_fc = borrow_root_field_class(ctx, src_field_path->root);
 317         tgt_fc = borrow_root_field_class(ctx, tgt_field_path->root);
 318         BT_ASSERT(src_fc);
 319         BT_ASSERT(tgt_fc);
 320
 321         for (src_i = 0, tgt_i = 0; src_i < src_field_path->items->len &&
 322                         tgt_i < tgt_field_path->items->len; src_i++, tgt_i++) {
 323                 struct bt_field_path_item *src_fp_item =
 324                         bt_field_path_borrow_item_by_index_inline(
 325                                 src_field_path, src_i);
 326                 struct bt_field_path_item *tgt_fp_item =
 327                         bt_field_path_borrow_item_by_index_inline(
 328                                 tgt_field_path, tgt_i);
 329
 330                 if (src_fc != tgt_fc) {
 331                         if (!prev_fc) {
 332                                 /*
 333                                  * This is correct: the LCA is the root
 334                                  * scope field class, which must be a
 335                                  * structure field class.
 336                                  */
 337                                 break;
 338                         }
 339
 340                         if (prev_fc->type != BT_FIELD_CLASS_TYPE_STRUCTURE) {
 341                                 is_valid = false;
 342                         }
 343
 344                         break;
 345                 }
 346
 347                 prev_fc = src_fc;
 348                 src_fc = borrow_child_field_class(src_fc, src_fp_item);
 349                 tgt_fc = borrow_child_field_class(tgt_fc, tgt_fp_item);
 350         }
 351
 352 end:
 353         return is_valid;
 354 }
 355
 356 BT_ASSERT_PRE_DEV_FUNC
 357 static inline
 358 bool lca_to_target_has_struct_fc_only(struct bt_field_path *src_field_path,
 359                 struct bt_field_path *tgt_field_path,
 360                 struct bt_resolve_field_path_context *ctx)
 361 {
 362         bool is_valid = true;
 363         struct bt_field_class *src_fc;
 364         struct bt_field_class *tgt_fc;
 365         uint64_t src_i = 0, tgt_i = 0;
 366
 367         if (src_field_path->root != tgt_field_path->root) {
 368                 goto end;
 369         }
 370
 371         src_fc = borrow_root_field_class(ctx, src_field_path->root);
 372         tgt_fc = borrow_root_field_class(ctx, tgt_field_path->root);
 373         BT_ASSERT(src_fc);
 374         BT_ASSERT(tgt_fc);
 375         BT_ASSERT(src_fc == tgt_fc);
 376
 377         /* Find LCA */
 378         for (src_i = 0, tgt_i = 0; src_i < src_field_path->items->len &&
 379                         tgt_i < tgt_field_path->items->len; src_i++, tgt_i++) {
 380                 struct bt_field_path_item *src_fp_item =
 381                         bt_field_path_borrow_item_by_index_inline(
 382                                 src_field_path, src_i);
 383                 struct bt_field_path_item *tgt_fp_item =
 384                         bt_field_path_borrow_item_by_index_inline(
 385                                 tgt_field_path, tgt_i);
 386
 387                 if (src_i != tgt_i) {
 388                         /* Next field class is different: LCA is `tgt_fc` */
 389                         break;
 390                 }
 391
 392                 src_fc = borrow_child_field_class(src_fc, src_fp_item);
 393                 tgt_fc = borrow_child_field_class(tgt_fc, tgt_fp_item);
 394         }
 395
 396         /* Only structure field classes to the target */
 397         for (; tgt_i < tgt_field_path->items->len; tgt_i++) {
 398                 struct bt_field_path_item *tgt_fp_item =
 399                         bt_field_path_borrow_item_by_index_inline(
 400                                 tgt_field_path, tgt_i);
 401
 402                 if (bt_field_class_type_is(tgt_fc->type,
 403                                 BT_FIELD_CLASS_TYPE_ARRAY) ||
 404                                 bt_field_class_type_is(tgt_fc->type,
 405                                         BT_FIELD_CLASS_TYPE_OPTION) ||
 406                                 bt_field_class_type_is(tgt_fc->type,
 407                                         BT_FIELD_CLASS_TYPE_VARIANT)) {
 408                         is_valid = false;
 409                         goto end;
 410                 }
 411
 412                 tgt_fc = borrow_child_field_class(tgt_fc, tgt_fp_item);
 413         }
 414
 415 end:
 416         return is_valid;
 417 }
 418
 419 BT_ASSERT_PRE_DEV_FUNC
 420 static inline
 421 bool field_path_is_valid(struct bt_field_class *src_fc,
 422                 struct bt_field_class *tgt_fc,
 423                 struct bt_resolve_field_path_context *ctx)
 424 {
 425         bool is_valid = true;
 426         struct bt_field_path *src_field_path = find_field_class_in_ctx(
 427                 src_fc, ctx);
 428         struct bt_field_path *tgt_field_path = find_field_class_in_ctx(
 429                 tgt_fc, ctx);
 430
 431         if (!src_field_path) {
 432                 BT_ASSERT_PRE_DEV_MSG("Cannot find requesting field class in "
 433                         "resolving context: %!+F", src_fc);
 434                 is_valid = false;
 435                 goto end;
 436         }
 437
 438         if (!tgt_field_path) {
 439                 BT_ASSERT_PRE_DEV_MSG("Cannot find target field class in "
 440                         "resolving context: %!+F", tgt_fc);
 441                 is_valid = false;
 442                 goto end;
 443         }
 444
 445         /* Target must be before source */
 446         if (!target_is_before_source(src_field_path, tgt_field_path)) {
 447                 BT_ASSERT_PRE_DEV_MSG("Target field class is located after "
 448                         "requesting field class: %![req-fc-]+F, %![tgt-fc-]+F",
 449                         src_fc, tgt_fc);
 450                 is_valid = false;
 451                 goto end;
 452         }
 453
 454         /*
 455          * If target is in a different scope than source, there are no
 456          * array or variant field classes on the way to the target.
 457          */
 458         if (!target_field_path_in_different_scope_has_struct_fc_only(
 459                         src_field_path, tgt_field_path, ctx)) {
 460                 BT_ASSERT_PRE_DEV_MSG("Target field class is located in a "
 461                         "different scope than requesting field class, "
 462                         "but within an array or a variant field class: "
 463                         "%![req-fc-]+F, %![tgt-fc-]+F",
 464                         src_fc, tgt_fc);
 465                 is_valid = false;
 466                 goto end;
 467         }
 468
 469         /* Same scope: LCA must be a structure field class */
 470         if (!lca_is_structure_field_class(src_field_path, tgt_field_path, ctx)) {
 471                 BT_ASSERT_PRE_DEV_MSG("Lowest common ancestor of target and "
 472                         "requesting field classes is not a structure field class: "
 473                         "%![req-fc-]+F, %![tgt-fc-]+F",
 474                         src_fc, tgt_fc);
 475                 is_valid = false;
 476                 goto end;
 477         }
 478
 479         /* Same scope: path from LCA to target has no array/variant FTs */
 480         if (!lca_to_target_has_struct_fc_only(src_field_path, tgt_field_path,
 481                         ctx)) {
 482                 BT_ASSERT_PRE_DEV_MSG("Path from lowest common ancestor of target "
 483                         "and requesting field classes to target field class "
 484                         "contains an array or a variant field class: "
 485                         "%![req-fc-]+F, %![tgt-fc-]+F", src_fc, tgt_fc);
 486                 is_valid = false;
 487                 goto end;
 488         }
 489
 490 end:
 491         bt_object_put_ref(src_field_path);
 492         bt_object_put_ref(tgt_field_path);
 493         return is_valid;
 494 }
 495
 496 static
 497 struct bt_field_path *resolve_field_path(struct bt_field_class *src_fc,
 498                 struct bt_field_class *tgt_fc,
 499                 struct bt_resolve_field_path_context *ctx)
 500 {
 501         BT_ASSERT_PRE_DEV(field_path_is_valid(src_fc, tgt_fc, ctx),
 502                 "Invalid target field class: %![req-fc-]+F, %![tgt-fc-]+F",
 503                 src_fc, tgt_fc);
 504         return find_field_class_in_ctx(tgt_fc, ctx);
 505 }
 506
 507 BT_HIDDEN
 508 int bt_resolve_field_paths(struct bt_field_class *fc,
 509                 struct bt_resolve_field_path_context *ctx)
 510 {
 511         int ret = 0;
 512
 513         BT_ASSERT(fc);
 514
 515         /* Resolving part for dynamic array and variant field classes */
 516         if (bt_field_class_type_is(fc->type,
 517                         BT_FIELD_CLASS_TYPE_OPTION_WITH_SELECTOR_FIELD)) {
 518                 struct bt_field_class_option_with_selector_field *opt_fc = (void *) fc;
 519
 520                 BT_ASSERT(opt_fc->selector_fc);
 521                 BT_ASSERT(!opt_fc->selector_field_path);
 522                 opt_fc->selector_field_path = resolve_field_path(
 523                         fc, opt_fc->selector_fc, ctx);
 524                 if (!opt_fc->selector_field_path) {
 525                         ret = -1;
 526                         goto end;
 527                 }
 528         } else if (fc->type == BT_FIELD_CLASS_TYPE_DYNAMIC_ARRAY_WITH_LENGTH_FIELD) {
 529                 struct bt_field_class_array_dynamic *dyn_array_fc = (void *) fc;
 530
 531                 BT_ASSERT(dyn_array_fc->length_fc);
 532                 BT_ASSERT(!dyn_array_fc->length_field_path);
 533                 dyn_array_fc->length_field_path = resolve_field_path(
 534                         fc, dyn_array_fc->length_fc, ctx);
 535                 if (!dyn_array_fc->length_field_path) {
 536                         ret = -1;
 537                         goto end;
 538                 }
 539         } else if (bt_field_class_type_is(fc->type,
 540                         BT_FIELD_CLASS_TYPE_VARIANT_WITH_SELECTOR_FIELD)) {
 541                 struct bt_field_class_variant_with_selector_field *var_fc =
 542                         (void *) fc;
 543
 544                 if (var_fc->selector_fc) {
 545                         BT_ASSERT(!var_fc->selector_field_path);
 546                         var_fc->selector_field_path =
 547                                 resolve_field_path(fc,
 548                                         (void *) var_fc->selector_fc, ctx);
 549                         if (!var_fc->selector_field_path) {
 550                                 ret = -1;
 551                                 goto end;
 552                         }
 553                 }
 554         }
 555
 556         /* Recursive part */
 557         if (bt_field_class_type_is(fc->type, BT_FIELD_CLASS_TYPE_OPTION)) {
 558                 struct bt_field_class_option *opt_fc = (void *) fc;
 559
 560                 ret = bt_resolve_field_paths(opt_fc->content_fc, ctx);
 561         } else if (fc->type == BT_FIELD_CLASS_TYPE_STRUCTURE ||
 562                         bt_field_class_type_is(fc->type,
 563                                 BT_FIELD_CLASS_TYPE_VARIANT)) {
 564                 struct bt_field_class_named_field_class_container *container_fc =
 565                         (void *) fc;
 566                 uint64_t i;
 567
 568                 for (i = 0; i < container_fc->named_fcs->len; i++) {
 569                         struct bt_named_field_class *named_fc =
 570                                 container_fc->named_fcs->pdata[i];
 571
 572                         ret = bt_resolve_field_paths(named_fc->fc, ctx);
 573                         if (ret) {
 574                                 goto end;
 575                         }
 576                 }
 577         } else if (bt_field_class_type_is(fc->type,
 578                         BT_FIELD_CLASS_TYPE_ARRAY)) {
 579                 struct bt_field_class_array *array_fc = (void *) fc;
 580
 581                 ret = bt_resolve_field_paths(array_fc->element_fc, ctx);
 582         }
 583
 584 end:
 585         return ret;
 586 }