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

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