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