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