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