Re-organize sources
[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 "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 }
This page took 0.042165 seconds and 4 git commands to generate.