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