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