lib/ctf-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/ctf-ir/field-types-internal.h>
  29 #include <babeltrace/ctf-ir/field-path-internal.h>
  30 #include <babeltrace/ctf-ir/field-path.h>
  31 #include <babeltrace/ctf-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_type_recursive(struct bt_field_type *ft,
  39                 struct bt_field_type *tgt_ft, struct bt_field_path *field_path)
  40 {
  41         bool found = false;
  42
  43         if (tgt_ft == ft) {
  44                 found = true;
  45                 goto end;
  46         }
  47
  48         switch (ft->id) {
  49         case BT_FIELD_TYPE_ID_STRUCTURE:
  50         case BT_FIELD_TYPE_ID_VARIANT:
  51         {
  52                 struct bt_field_type_named_field_types_container *container_ft =
  53                         (void *) ft;
  54                 uint64_t i;
  55
  56                 for (i = 0; i < container_ft->named_fts->len; i++) {
  57                         struct bt_named_field_type *named_ft =
  58                                 BT_FIELD_TYPE_NAMED_FT_AT_INDEX(
  59                                         container_ft, i);
  60
  61                         g_array_append_val(field_path->indexes, i);
  62                         found = find_field_type_recursive(named_ft->ft,
  63                                 tgt_ft, 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_TYPE_ID_STATIC_ARRAY:
  75         case BT_FIELD_TYPE_ID_DYNAMIC_ARRAY:
  76         {
  77                 struct bt_field_type_array *array_ft = (void *) ft;
  78
  79                 found = find_field_type_recursive(array_ft->element_ft,
  80                         tgt_ft, field_path);
  81                 break;
  82         }
  83         default:
  84                 break;
  85         }
  86
  87 end:
  88         return found;
  89 }
  90
  91 static
  92 int find_field_type(struct bt_field_type *root_ft,
  93                 enum bt_scope root_scope, struct bt_field_type *tgt_ft,
  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_ft) {
 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_type_recursive(root_ft, tgt_ft, field_path)) {
 111                 /* Not found here */
 112                 BT_PUT(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_type_in_ctx(struct bt_field_type *ft,
 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_type(ctx->packet_header, BT_SCOPE_PACKET_HEADER,
 128                 ft, &field_path);
 129         if (ret || field_path) {
 130                 goto end;
 131         }
 132
 133         ret = find_field_type(ctx->packet_context, BT_SCOPE_PACKET_CONTEXT,
 134                 ft, &field_path);
 135         if (ret || field_path) {
 136                 goto end;
 137         }
 138
 139         ret = find_field_type(ctx->event_header, BT_SCOPE_EVENT_HEADER,
 140                 ft, &field_path);
 141         if (ret || field_path) {
 142                 goto end;
 143         }
 144
 145         ret = find_field_type(ctx->event_common_context,
 146                 BT_SCOPE_EVENT_COMMON_CONTEXT, ft, &field_path);
 147         if (ret || field_path) {
 148                 goto end;
 149         }
 150
 151         ret = find_field_type(ctx->event_specific_context,
 152                 BT_SCOPE_EVENT_SPECIFIC_CONTEXT, ft, &field_path);
 153         if (ret || field_path) {
 154                 goto end;
 155         }
 156
 157         ret = find_field_type(ctx->event_payload, BT_SCOPE_EVENT_PAYLOAD,
 158                 ft, &field_path);
 159         if (ret || field_path) {
 160                 goto end;
 161         }
 162
 163 end:
 164         return field_path;
 165 }
 166
 167 BT_ASSERT_PRE_FUNC
 168 static inline
 169 bool target_is_before_source(struct bt_field_path *src_field_path,
 170                 struct bt_field_path *tgt_field_path)
 171 {
 172         bool is_valid = true;
 173         uint64_t src_i = 0, tgt_i = 0;
 174
 175         if (tgt_field_path->root < src_field_path->root) {
 176                 goto end;
 177         }
 178
 179         if (tgt_field_path->root > src_field_path->root) {
 180                 is_valid = false;
 181                 goto end;
 182         }
 183
 184         BT_ASSERT(tgt_field_path->root == src_field_path->root);
 185
 186         while (src_i < src_field_path->indexes->len &&
 187                         tgt_i < tgt_field_path->indexes->len) {
 188                 uint64_t src_index = bt_field_path_get_index_by_index_inline(
 189                         src_field_path, src_i);
 190                 uint64_t tgt_index = bt_field_path_get_index_by_index_inline(
 191                         tgt_field_path, tgt_i);
 192
 193                 if (tgt_index > src_index) {
 194                         is_valid = false;
 195                         goto end;
 196                 }
 197
 198                 src_i++;
 199                 tgt_i++;
 200         }
 201
 202 end:
 203         return is_valid;
 204 }
 205
 206 BT_ASSERT_PRE_FUNC
 207 static inline
 208 struct bt_field_type *borrow_root_field_type(
 209                 struct bt_resolve_field_path_context *ctx, enum bt_scope scope)
 210 {
 211         switch (scope) {
 212         case BT_SCOPE_PACKET_HEADER:
 213                 return ctx->packet_header;
 214         case BT_SCOPE_PACKET_CONTEXT:
 215                 return ctx->packet_context;
 216         case BT_SCOPE_EVENT_HEADER:
 217                 return ctx->event_header;
 218         case BT_SCOPE_EVENT_COMMON_CONTEXT:
 219                 return ctx->event_common_context;
 220         case BT_SCOPE_EVENT_SPECIFIC_CONTEXT:
 221                 return ctx->event_specific_context;
 222         case BT_SCOPE_EVENT_PAYLOAD:
 223                 return ctx->event_payload;
 224         default:
 225                 abort();
 226         }
 227
 228         return NULL;
 229 }
 230
 231 BT_ASSERT_PRE_FUNC
 232 static inline
 233 struct bt_field_type *borrow_child_field_type(struct bt_field_type *parent_ft,
 234                 uint64_t index, bool *advance)
 235 {
 236         struct bt_field_type *child_ft = NULL;
 237
 238         switch (parent_ft->id) {
 239         case BT_FIELD_TYPE_ID_STRUCTURE:
 240         case BT_FIELD_TYPE_ID_VARIANT:
 241         {
 242                 struct bt_named_field_type *named_ft =
 243                         BT_FIELD_TYPE_NAMED_FT_AT_INDEX(parent_ft, index);
 244
 245                 child_ft = named_ft->ft;
 246                 *advance = true;
 247                 break;
 248         }
 249         case BT_FIELD_TYPE_ID_STATIC_ARRAY:
 250         case BT_FIELD_TYPE_ID_DYNAMIC_ARRAY:
 251         {
 252                 struct bt_field_type_array *array_ft = (void *) parent_ft;
 253
 254                 child_ft = array_ft->element_ft;
 255                 *advance = false;
 256                 break;
 257         }
 258         default:
 259                 break;
 260         }
 261
 262         return child_ft;
 263 }
 264
 265 BT_ASSERT_PRE_FUNC
 266 static inline
 267 bool target_field_path_in_different_scope_has_struct_ft_only(
 268                 struct bt_field_path *src_field_path,
 269                 struct bt_field_path *tgt_field_path,
 270                 struct bt_resolve_field_path_context *ctx)
 271 {
 272         bool is_valid = true;
 273         uint64_t i = 0;
 274         struct bt_field_type *ft;
 275
 276         if (src_field_path->root == tgt_field_path->root) {
 277                 goto end;
 278         }
 279
 280         ft = borrow_root_field_type(ctx, tgt_field_path->root);
 281
 282         while (i < tgt_field_path->indexes->len) {
 283                 uint64_t index = bt_field_path_get_index_by_index_inline(
 284                         tgt_field_path, i);
 285                 bool advance;
 286
 287                 if (ft->id == BT_FIELD_TYPE_ID_STATIC_ARRAY ||
 288                                 ft->id == BT_FIELD_TYPE_ID_DYNAMIC_ARRAY ||
 289                                 ft->id == BT_FIELD_TYPE_ID_VARIANT) {
 290                         is_valid = false;
 291                         goto end;
 292                 }
 293
 294                 ft = borrow_child_field_type(ft, index, &advance);
 295
 296                 if (advance) {
 297                         i++;
 298                 }
 299         }
 300
 301 end:
 302         return is_valid;
 303 }
 304
 305 BT_ASSERT_PRE_FUNC
 306 static inline
 307 bool lca_is_structure_field_type(struct bt_field_path *src_field_path,
 308                 struct bt_field_path *tgt_field_path,
 309                 struct bt_resolve_field_path_context *ctx)
 310 {
 311         bool is_valid = true;
 312         struct bt_field_type *src_ft;
 313         struct bt_field_type *tgt_ft;
 314         struct bt_field_type *prev_ft = NULL;
 315         uint64_t src_i = 0, tgt_i = 0;
 316
 317         if (src_field_path->root != tgt_field_path->root) {
 318                 goto end;
 319         }
 320
 321         src_ft = borrow_root_field_type(ctx, src_field_path->root);
 322         tgt_ft = borrow_root_field_type(ctx, tgt_field_path->root);
 323         BT_ASSERT(src_ft);
 324         BT_ASSERT(tgt_ft);
 325
 326         while (src_i < src_field_path->indexes->len &&
 327                         tgt_i < tgt_field_path->indexes->len) {
 328                 bool advance;
 329                 uint64_t src_index = bt_field_path_get_index_by_index_inline(
 330                         src_field_path, src_i);
 331                 uint64_t tgt_index = bt_field_path_get_index_by_index_inline(
 332                         tgt_field_path, tgt_i);
 333
 334                 if (src_ft != tgt_ft) {
 335                         if (!prev_ft) {
 336                                 /*
 337                                  * This is correct: the LCA is the root
 338                                  * scope field type, which must be a
 339                                  * structure field type.
 340                                  */
 341                                 break;
 342                         }
 343
 344                         if (prev_ft->id != BT_FIELD_TYPE_ID_STRUCTURE) {
 345                                 is_valid = false;
 346                         }
 347
 348                         break;
 349                 }
 350
 351                 prev_ft = src_ft;
 352                 src_ft = borrow_child_field_type(src_ft, src_index, &advance);
 353
 354                 if (advance) {
 355                         src_i++;
 356                 }
 357
 358                 tgt_ft = borrow_child_field_type(tgt_ft, tgt_index, &advance);
 359
 360                 if (advance) {
 361                         tgt_i++;
 362                 }
 363         }
 364
 365 end:
 366         return is_valid;
 367 }
 368
 369 BT_ASSERT_PRE_FUNC
 370 static inline
 371 bool lca_to_target_has_struct_ft_only(struct bt_field_path *src_field_path,
 372                 struct bt_field_path *tgt_field_path,
 373                 struct bt_resolve_field_path_context *ctx)
 374 {
 375         bool is_valid = true;
 376         struct bt_field_type *src_ft;
 377         struct bt_field_type *tgt_ft;
 378         uint64_t src_i = 0, tgt_i = 0;
 379
 380         if (src_field_path->root != tgt_field_path->root) {
 381                 goto end;
 382         }
 383
 384         src_ft = borrow_root_field_type(ctx, src_field_path->root);
 385         tgt_ft = borrow_root_field_type(ctx, tgt_field_path->root);
 386         BT_ASSERT(src_ft);
 387         BT_ASSERT(tgt_ft);
 388         BT_ASSERT(src_ft == tgt_ft);
 389
 390         /* Find LCA */
 391         while (src_i < src_field_path->indexes->len &&
 392                         tgt_i < tgt_field_path->indexes->len) {
 393                 bool advance;
 394                 uint64_t src_index = bt_field_path_get_index_by_index_inline(
 395                         src_field_path, src_i);
 396                 uint64_t tgt_index = bt_field_path_get_index_by_index_inline(
 397                         tgt_field_path, tgt_i);
 398
 399                 if (src_i != tgt_i) {
 400                         /* Next FT is different: LCA is `tgt_ft` */
 401                         break;
 402                 }
 403
 404                 src_ft = borrow_child_field_type(src_ft, src_index, &advance);
 405
 406                 if (advance) {
 407                         src_i++;
 408                 }
 409
 410                 tgt_ft = borrow_child_field_type(tgt_ft, tgt_index, &advance);
 411
 412                 if (advance) {
 413                         tgt_i++;
 414                 }
 415         }
 416
 417         /* Only structure field types to the target */
 418         while (tgt_i < tgt_field_path->indexes->len) {
 419                 bool advance;
 420                 uint64_t tgt_index = bt_field_path_get_index_by_index_inline(
 421                         tgt_field_path, tgt_i);
 422
 423                 if (tgt_ft->id == BT_FIELD_TYPE_ID_STATIC_ARRAY ||
 424                                 tgt_ft->id == BT_FIELD_TYPE_ID_DYNAMIC_ARRAY ||
 425                                 tgt_ft->id == BT_FIELD_TYPE_ID_VARIANT) {
 426                         is_valid = false;
 427                         goto end;
 428                 }
 429
 430                 tgt_ft = borrow_child_field_type(tgt_ft, tgt_index, &advance);
 431
 432                 if (advance) {
 433                         tgt_i++;
 434                 }
 435         }
 436
 437 end:
 438         return is_valid;
 439 }
 440
 441 BT_ASSERT_PRE_FUNC
 442 static inline
 443 bool field_path_is_valid(struct bt_field_type *src_ft,
 444                 struct bt_field_type *tgt_ft,
 445                 struct bt_resolve_field_path_context *ctx)
 446 {
 447         bool is_valid = true;
 448         struct bt_field_path *src_field_path = find_field_type_in_ctx(
 449                 src_ft, ctx);
 450         struct bt_field_path *tgt_field_path = find_field_type_in_ctx(
 451                 tgt_ft, ctx);
 452
 453         if (!src_field_path) {
 454                 BT_ASSERT_PRE_MSG("Cannot find requesting field type in "
 455                         "resolving context: %!+F", src_ft);
 456                 is_valid = false;
 457                 goto end;
 458         }
 459
 460         if (!tgt_field_path) {
 461                 BT_ASSERT_PRE_MSG("Cannot find target field type in "
 462                         "resolving context: %!+F", tgt_ft);
 463                 is_valid = false;
 464                 goto end;
 465         }
 466
 467         /* Target must be before source */
 468         if (!target_is_before_source(src_field_path, tgt_field_path)) {
 469                 BT_ASSERT_PRE_MSG("Target field type is located after "
 470                         "requesting field type: %![req-ft-]+F, %![tgt-ft-]+F",
 471                         src_ft, tgt_ft);
 472                 is_valid = false;
 473                 goto end;
 474         }
 475
 476         /*
 477          * If target is in a different scope than source, there are no
 478          * array or variant field types on the way to the target.
 479          */
 480         if (!target_field_path_in_different_scope_has_struct_ft_only(
 481                         src_field_path, tgt_field_path, ctx)) {
 482                 BT_ASSERT_PRE_MSG("Target field type is located in a "
 483                         "different scope than requesting field type, "
 484                         "but within an array or a variant field type: "
 485                         "%![req-ft-]+F, %![tgt-ft-]+F",
 486                         src_ft, tgt_ft);
 487                 is_valid = false;
 488                 goto end;
 489         }
 490
 491         /* Same scope: LCA must be a structure field type */
 492         if (!lca_is_structure_field_type(src_field_path, tgt_field_path, ctx)) {
 493                 BT_ASSERT_PRE_MSG("Lowest common ancestor of target and "
 494                         "requesting field types is not a structure field type: "
 495                         "%![req-ft-]+F, %![tgt-ft-]+F",
 496                         src_ft, tgt_ft);
 497                 is_valid = false;
 498                 goto end;
 499         }
 500
 501         /* Same scope: path from LCA to target has no array/variant FTs */
 502         if (!lca_to_target_has_struct_ft_only(src_field_path, tgt_field_path,
 503                         ctx)) {
 504                 BT_ASSERT_PRE_MSG("Path from lowest common ancestor of target "
 505                         "and requesting field types to target field type "
 506                         "contains an array or a variant field type: "
 507                         "%![req-ft-]+F, %![tgt-ft-]+F", src_ft, tgt_ft);
 508                 is_valid = false;
 509                 goto end;
 510         }
 511
 512 end:
 513         bt_put(src_field_path);
 514         bt_put(tgt_field_path);
 515         return is_valid;
 516 }
 517
 518 static
 519 struct bt_field_path *resolve_field_path(struct bt_field_type *src_ft,
 520                 struct bt_field_type *tgt_ft,
 521                 struct bt_resolve_field_path_context *ctx)
 522 {
 523         BT_ASSERT_PRE(field_path_is_valid(src_ft, tgt_ft, ctx),
 524                 "Invalid target field type: %![req-ft-]+F, %![tgt-ft-]+F",
 525                 src_ft, tgt_ft);
 526         return find_field_type_in_ctx(tgt_ft, ctx);
 527 }
 528
 529 BT_HIDDEN
 530 int bt_resolve_field_paths(struct bt_field_type *ft,
 531                 struct bt_resolve_field_path_context *ctx)
 532 {
 533         int ret = 0;
 534
 535         BT_ASSERT(ft);
 536
 537         /* Resolving part for dynamic array and variant field types */
 538         switch (ft->id) {
 539         case BT_FIELD_TYPE_ID_DYNAMIC_ARRAY:
 540         {
 541                 struct bt_field_type_dynamic_array *dyn_array_ft = (void *) ft;
 542
 543                 if (dyn_array_ft->length_ft) {
 544                         BT_ASSERT(!dyn_array_ft->length_field_path);
 545                         dyn_array_ft->length_field_path = resolve_field_path(
 546                                 ft, dyn_array_ft->length_ft, ctx);
 547                         if (!dyn_array_ft->length_field_path) {
 548                                 ret = -1;
 549                                 goto end;
 550                         }
 551                 }
 552
 553                 break;
 554         }
 555         case BT_FIELD_TYPE_ID_VARIANT:
 556         {
 557                 struct bt_field_type_variant *var_ft = (void *) ft;
 558
 559                 if (var_ft->selector_ft) {
 560                         BT_ASSERT(!var_ft->selector_field_path);
 561                         var_ft->selector_field_path =
 562                                 resolve_field_path(ft,
 563                                         var_ft->selector_ft, ctx);
 564                         if (!var_ft->selector_field_path) {
 565                                 ret = -1;
 566                                 goto end;
 567                         }
 568                 }
 569         }
 570         default:
 571                 break;
 572         }
 573
 574         /* Recursive part */
 575         switch (ft->id) {
 576         case BT_FIELD_TYPE_ID_STRUCTURE:
 577         case BT_FIELD_TYPE_ID_VARIANT:
 578         {
 579                 struct bt_field_type_named_field_types_container *container_ft =
 580                         (void *) ft;
 581                 uint64_t i;
 582
 583                 for (i = 0; i < container_ft->named_fts->len; i++) {
 584                         struct bt_named_field_type *named_ft =
 585                                 BT_FIELD_TYPE_NAMED_FT_AT_INDEX(
 586                                         container_ft, i);
 587
 588                         ret = bt_resolve_field_paths(named_ft->ft, ctx);
 589                         if (ret) {
 590                                 goto end;
 591                         }
 592                 }
 593
 594                 break;
 595         }
 596         case BT_FIELD_TYPE_ID_STATIC_ARRAY:
 597         case BT_FIELD_TYPE_ID_DYNAMIC_ARRAY:
 598         {
 599                 struct bt_field_type_array *array_ft = (void *) ft;
 600
 601                 ret = bt_resolve_field_paths(array_ft->element_ft, ctx);
 602                 break;
 603         }
 604         default:
 605                 break;
 606         }
 607
 608 end:
 609         return ret;
 610 }