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