2 * filter-visitor-generate-ir.c
4 * LTTng filter generate intermediate representation
6 * Copyright 2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 * SPDX-License-Identifier: LGPL-2.1-only
17 #include "filter-ast.h"
18 #include "filter-parser.h"
19 #include "filter-ir.h"
21 #include <common/compat/errno.h>
22 #include <common/macros.h>
23 #include <common/string-utils/string-utils.h>
26 struct ir_op
*generate_ir_recursive(struct filter_parser_ctx
*ctx
,
27 struct filter_node
*node
, enum ir_side side
);
30 struct ir_op
*make_op_root(struct ir_op
*child
, enum ir_side side
)
34 op
= calloc(sizeof(struct ir_op
), 1);
37 switch (child
->data_type
) {
40 fprintf(stderr
, "[error] Unknown root child data type\n");
44 fprintf(stderr
, "[error] String cannot be root data type\n");
48 case IR_DATA_FIELD_REF
:
49 case IR_DATA_GET_CONTEXT_REF
:
50 case IR_DATA_EXPRESSION
:
56 op
->data_type
= child
->data_type
;
57 op
->signedness
= child
->signedness
;
58 op
->u
.root
.child
= child
;
63 enum ir_load_string_type
get_literal_string_type(const char *string
)
67 if (strutils_is_star_glob_pattern(string
)) {
68 if (strutils_is_star_at_the_end_only_glob_pattern(string
)) {
69 return IR_LOAD_STRING_TYPE_GLOB_STAR_END
;
72 return IR_LOAD_STRING_TYPE_GLOB_STAR
;
75 return IR_LOAD_STRING_TYPE_PLAIN
;
79 struct ir_op
*make_op_load_string(const char *string
, enum ir_side side
)
83 op
= calloc(sizeof(struct ir_op
), 1);
87 op
->data_type
= IR_DATA_STRING
;
88 op
->signedness
= IR_SIGN_UNKNOWN
;
90 op
->u
.load
.u
.string
.type
= get_literal_string_type(string
);
91 op
->u
.load
.u
.string
.value
= strdup(string
);
92 if (!op
->u
.load
.u
.string
.value
) {
100 struct ir_op
*make_op_load_numeric(int64_t v
, enum ir_side side
)
104 op
= calloc(sizeof(struct ir_op
), 1);
108 op
->data_type
= IR_DATA_NUMERIC
;
109 /* TODO: for now, all numeric values are signed */
110 op
->signedness
= IR_SIGNED
;
112 op
->u
.load
.u
.num
= v
;
117 struct ir_op
*make_op_load_float(double v
, enum ir_side side
)
121 op
= calloc(sizeof(struct ir_op
), 1);
125 op
->data_type
= IR_DATA_FLOAT
;
126 op
->signedness
= IR_SIGN_UNKNOWN
;
128 op
->u
.load
.u
.flt
= v
;
133 void free_load_expression(struct ir_load_expression
*load_expression
)
135 struct ir_load_expression_op
*exp_op
;
137 if (!load_expression
)
139 exp_op
= load_expression
->child
;
141 struct ir_load_expression_op
*prev_exp_op
;
145 switch (exp_op
->type
) {
146 case IR_LOAD_EXPRESSION_GET_CONTEXT_ROOT
:
147 case IR_LOAD_EXPRESSION_GET_APP_CONTEXT_ROOT
:
148 case IR_LOAD_EXPRESSION_GET_PAYLOAD_ROOT
:
149 case IR_LOAD_EXPRESSION_GET_INDEX
:
150 case IR_LOAD_EXPRESSION_LOAD_FIELD
:
152 case IR_LOAD_EXPRESSION_GET_SYMBOL
:
153 free(exp_op
->u
.symbol
);
156 prev_exp_op
= exp_op
;
157 exp_op
= exp_op
->next
;
160 free(load_expression
);
164 * Returns the first node of the chain, after initializing the next
168 struct filter_node
*load_expression_get_forward_chain(struct filter_node
*node
)
170 struct filter_node
*prev_node
;
173 LTTNG_ASSERT(node
->type
== NODE_EXPRESSION
);
175 node
= node
->u
.expression
.prev
;
179 node
->u
.expression
.next
= prev_node
;
185 struct ir_load_expression
*create_load_expression(struct filter_node
*node
)
187 struct ir_load_expression
*load_exp
;
188 struct ir_load_expression_op
*load_exp_op
, *prev_op
;
191 /* Get forward chain. */
192 node
= load_expression_get_forward_chain(node
);
195 load_exp
= calloc(sizeof(struct ir_load_expression
), 1);
200 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
203 load_exp
->child
= load_exp_op
;
204 str
= node
->u
.expression
.u
.string
;
205 if (!strcmp(str
, "$ctx")) {
206 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_CONTEXT_ROOT
;
207 node
= node
->u
.expression
.next
;
209 fprintf(stderr
, "[error] Expecting identifier after \'%s\'\n", str
);
212 str
= node
->u
.expression
.u
.string
;
213 } else if (!strcmp(str
, "$app")) {
214 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_APP_CONTEXT_ROOT
;
215 node
= node
->u
.expression
.next
;
217 fprintf(stderr
, "[error] Expecting identifier after \'%s\'\n", str
);
220 str
= node
->u
.expression
.u
.string
;
221 } else if (str
[0] == '$') {
222 fprintf(stderr
, "[error] Unexpected identifier \'%s\'\n", str
);
225 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_PAYLOAD_ROOT
;
229 struct filter_node
*bracket_node
;
231 prev_op
= load_exp_op
;
232 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
235 prev_op
->next
= load_exp_op
;
236 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_SYMBOL
;
237 load_exp_op
->u
.symbol
= strdup(str
);
238 if (!load_exp_op
->u
.symbol
)
241 /* Explore brackets from current node. */
242 for (bracket_node
= node
->u
.expression
.next_bracket
;
243 bracket_node
!= NULL
;
244 bracket_node
= bracket_node
->u
.expression
.next_bracket
) {
245 prev_op
= load_exp_op
;
246 if (bracket_node
->type
!= NODE_EXPRESSION
||
247 bracket_node
->u
.expression
.type
!= AST_EXP_CONSTANT
) {
248 fprintf(stderr
, "[error] Expecting constant index in array expression\n");
251 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
254 prev_op
->next
= load_exp_op
;
255 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_INDEX
;
256 load_exp_op
->u
.index
= bracket_node
->u
.expression
.u
.constant
;
258 /* Go to next chain element. */
259 node
= node
->u
.expression
.next
;
262 str
= node
->u
.expression
.u
.string
;
264 /* Add final load field */
265 prev_op
= load_exp_op
;
266 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
269 prev_op
->next
= load_exp_op
;
270 load_exp_op
->type
= IR_LOAD_EXPRESSION_LOAD_FIELD
;
274 free_load_expression(load_exp
);
279 struct ir_op
*make_op_load_expression(struct filter_node
*node
,
284 op
= calloc(sizeof(struct ir_op
), 1);
288 op
->data_type
= IR_DATA_EXPRESSION
;
289 op
->signedness
= IR_SIGN_DYN
;
291 op
->u
.load
.u
.expression
= create_load_expression(node
);
292 if (!op
->u
.load
.u
.expression
) {
298 free_load_expression(op
->u
.load
.u
.expression
);
304 struct ir_op
*make_op_unary(enum unary_op_type unary_op_type
,
305 const char *op_str
, enum ir_op_signedness signedness
,
306 struct ir_op
*child
, enum ir_side side
)
308 struct ir_op
*op
= NULL
;
310 if (child
->data_type
== IR_DATA_STRING
) {
311 fprintf(stderr
, "[error] unary operation '%s' not allowed on string literal\n", op_str
);
315 op
= calloc(sizeof(struct ir_op
), 1);
318 op
->op
= IR_OP_UNARY
;
319 op
->data_type
= child
->data_type
;
320 op
->signedness
= signedness
;
322 op
->u
.unary
.type
= unary_op_type
;
323 op
->u
.unary
.child
= child
;
332 * unary + is pretty much useless.
335 struct ir_op
*make_op_unary_plus(struct ir_op
*child
, enum ir_side side
)
337 return make_op_unary(AST_UNARY_PLUS
, "+", child
->signedness
,
342 struct ir_op
*make_op_unary_minus(struct ir_op
*child
, enum ir_side side
)
344 return make_op_unary(AST_UNARY_MINUS
, "-", child
->signedness
,
349 struct ir_op
*make_op_unary_not(struct ir_op
*child
, enum ir_side side
)
351 return make_op_unary(AST_UNARY_NOT
, "!", child
->signedness
,
356 struct ir_op
*make_op_unary_bit_not(struct ir_op
*child
, enum ir_side side
)
358 return make_op_unary(AST_UNARY_BIT_NOT
, "~", child
->signedness
,
363 struct ir_op
*make_op_binary_compare(enum op_type bin_op_type
,
364 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
367 struct ir_op
*op
= NULL
;
369 if (left
->data_type
== IR_DATA_UNKNOWN
370 || right
->data_type
== IR_DATA_UNKNOWN
) {
371 fprintf(stderr
, "[error] binary operation '%s' has unknown operand type\n", op_str
);
375 if ((left
->data_type
== IR_DATA_STRING
376 && (right
->data_type
== IR_DATA_NUMERIC
|| right
->data_type
== IR_DATA_FLOAT
))
377 || ((left
->data_type
== IR_DATA_NUMERIC
|| left
->data_type
== IR_DATA_FLOAT
) &&
378 right
->data_type
== IR_DATA_STRING
)) {
379 fprintf(stderr
, "[error] binary operation '%s' operand type mismatch\n", op_str
);
383 op
= calloc(sizeof(struct ir_op
), 1);
386 op
->op
= IR_OP_BINARY
;
387 op
->u
.binary
.type
= bin_op_type
;
388 op
->u
.binary
.left
= left
;
389 op
->u
.binary
.right
= right
;
391 /* we return a boolean, represented as signed numeric */
392 op
->data_type
= IR_DATA_NUMERIC
;
393 op
->signedness
= IR_SIGNED
;
404 struct ir_op
*make_op_binary_eq(struct ir_op
*left
, struct ir_op
*right
,
407 return make_op_binary_compare(AST_OP_EQ
, "==", left
, right
, side
);
411 struct ir_op
*make_op_binary_ne(struct ir_op
*left
, struct ir_op
*right
,
414 return make_op_binary_compare(AST_OP_NE
, "!=", left
, right
, side
);
418 struct ir_op
*make_op_binary_gt(struct ir_op
*left
, struct ir_op
*right
,
421 return make_op_binary_compare(AST_OP_GT
, ">", left
, right
, side
);
425 struct ir_op
*make_op_binary_lt(struct ir_op
*left
, struct ir_op
*right
,
428 return make_op_binary_compare(AST_OP_LT
, "<", left
, right
, side
);
432 struct ir_op
*make_op_binary_ge(struct ir_op
*left
, struct ir_op
*right
,
435 return make_op_binary_compare(AST_OP_GE
, ">=", left
, right
, side
);
439 struct ir_op
*make_op_binary_le(struct ir_op
*left
, struct ir_op
*right
,
442 return make_op_binary_compare(AST_OP_LE
, "<=", left
, right
, side
);
446 struct ir_op
*make_op_binary_logical(enum op_type bin_op_type
,
447 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
450 struct ir_op
*op
= NULL
;
452 if (left
->data_type
== IR_DATA_UNKNOWN
453 || right
->data_type
== IR_DATA_UNKNOWN
) {
454 fprintf(stderr
, "[error] binary operation '%s' has unknown operand type\n", op_str
);
458 if (left
->data_type
== IR_DATA_STRING
459 || right
->data_type
== IR_DATA_STRING
) {
460 fprintf(stderr
, "[error] logical binary operation '%s' cannot have string operand\n", op_str
);
464 op
= calloc(sizeof(struct ir_op
), 1);
467 op
->op
= IR_OP_LOGICAL
;
468 op
->u
.binary
.type
= bin_op_type
;
469 op
->u
.binary
.left
= left
;
470 op
->u
.binary
.right
= right
;
472 /* we return a boolean, represented as signed numeric */
473 op
->data_type
= IR_DATA_NUMERIC
;
474 op
->signedness
= IR_SIGNED
;
485 struct ir_op
*make_op_binary_bitwise(enum op_type bin_op_type
,
486 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
489 struct ir_op
*op
= NULL
;
491 if (left
->data_type
== IR_DATA_UNKNOWN
492 || right
->data_type
== IR_DATA_UNKNOWN
) {
493 fprintf(stderr
, "[error] bitwise binary operation '%s' has unknown operand type\n", op_str
);
497 if (left
->data_type
== IR_DATA_STRING
498 || right
->data_type
== IR_DATA_STRING
) {
499 fprintf(stderr
, "[error] bitwise binary operation '%s' cannot have string operand\n", op_str
);
502 if (left
->data_type
== IR_DATA_FLOAT
503 || right
->data_type
== IR_DATA_FLOAT
) {
504 fprintf(stderr
, "[error] bitwise binary operation '%s' cannot have floating point operand\n", op_str
);
508 op
= calloc(sizeof(struct ir_op
), 1);
511 op
->op
= IR_OP_BINARY
;
512 op
->u
.binary
.type
= bin_op_type
;
513 op
->u
.binary
.left
= left
;
514 op
->u
.binary
.right
= right
;
516 /* we return a signed numeric */
517 op
->data_type
= IR_DATA_NUMERIC
;
518 op
->signedness
= IR_SIGNED
;
529 struct ir_op
*make_op_binary_logical_and(struct ir_op
*left
, struct ir_op
*right
,
532 return make_op_binary_logical(AST_OP_AND
, "&&", left
, right
, side
);
536 struct ir_op
*make_op_binary_logical_or(struct ir_op
*left
, struct ir_op
*right
,
539 return make_op_binary_logical(AST_OP_OR
, "||", left
, right
, side
);
543 struct ir_op
*make_op_binary_bitwise_rshift(struct ir_op
*left
, struct ir_op
*right
,
546 return make_op_binary_bitwise(AST_OP_BIT_RSHIFT
, ">>", left
, right
, side
);
550 struct ir_op
*make_op_binary_bitwise_lshift(struct ir_op
*left
, struct ir_op
*right
,
553 return make_op_binary_bitwise(AST_OP_BIT_LSHIFT
, "<<", left
, right
, side
);
557 struct ir_op
*make_op_binary_bitwise_and(struct ir_op
*left
, struct ir_op
*right
,
560 return make_op_binary_bitwise(AST_OP_BIT_AND
, "&", left
, right
, side
);
564 struct ir_op
*make_op_binary_bitwise_or(struct ir_op
*left
, struct ir_op
*right
,
567 return make_op_binary_bitwise(AST_OP_BIT_OR
, "|", left
, right
, side
);
571 struct ir_op
*make_op_binary_bitwise_xor(struct ir_op
*left
, struct ir_op
*right
,
574 return make_op_binary_bitwise(AST_OP_BIT_XOR
, "^", left
, right
, side
);
578 void filter_free_ir_recursive(struct ir_op
*op
)
585 fprintf(stderr
, "[error] Unknown op type in %s\n",
589 filter_free_ir_recursive(op
->u
.root
.child
);
592 switch (op
->data_type
) {
594 free(op
->u
.load
.u
.string
.value
);
596 case IR_DATA_FIELD_REF
: /* fall-through */
597 case IR_DATA_GET_CONTEXT_REF
:
598 free(op
->u
.load
.u
.ref
);
600 case IR_DATA_EXPRESSION
:
601 free_load_expression(op
->u
.load
.u
.expression
);
607 filter_free_ir_recursive(op
->u
.unary
.child
);
610 filter_free_ir_recursive(op
->u
.binary
.left
);
611 filter_free_ir_recursive(op
->u
.binary
.right
);
614 filter_free_ir_recursive(op
->u
.logical
.left
);
615 filter_free_ir_recursive(op
->u
.logical
.right
);
622 struct ir_op
*make_expression(struct filter_parser_ctx
*ctx
,
623 struct filter_node
*node
, enum ir_side side
)
625 switch (node
->u
.expression
.type
) {
626 case AST_EXP_UNKNOWN
:
628 fprintf(stderr
, "[error] %s: unknown expression type\n", __func__
);
632 return make_op_load_string(node
->u
.expression
.u
.string
, side
);
633 case AST_EXP_CONSTANT
:
634 return make_op_load_numeric(node
->u
.expression
.u
.constant
,
636 case AST_EXP_FLOAT_CONSTANT
:
637 return make_op_load_float(node
->u
.expression
.u
.float_constant
,
639 case AST_EXP_IDENTIFIER
:
640 case AST_EXP_GLOBAL_IDENTIFIER
:
641 return make_op_load_expression(node
, side
);
643 return generate_ir_recursive(ctx
, node
->u
.expression
.u
.child
,
649 struct ir_op
*make_op(struct filter_parser_ctx
*ctx
,
650 struct filter_node
*node
, enum ir_side side
)
652 struct ir_op
*op
= NULL
, *lchild
, *rchild
;
653 const char *op_str
= "?";
655 switch (node
->u
.op
.type
) {
658 fprintf(stderr
, "[error] %s: unknown binary op type\n", __func__
);
662 * The following binary operators other than comparators and
663 * logical and/or are not supported yet.
667 goto error_not_supported
;
670 goto error_not_supported
;
673 goto error_not_supported
;
676 goto error_not_supported
;
679 goto error_not_supported
;
681 case AST_OP_BIT_RSHIFT
:
682 case AST_OP_BIT_LSHIFT
:
686 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
689 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_RIGHT
);
691 filter_free_ir_recursive(lchild
);
702 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
705 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_RIGHT
);
707 filter_free_ir_recursive(lchild
);
715 * Both children considered as left, since we need to
718 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
721 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_LEFT
);
723 filter_free_ir_recursive(lchild
);
729 switch (node
->u
.op
.type
) {
731 op
= make_op_binary_logical_and(lchild
, rchild
, side
);
734 op
= make_op_binary_logical_or(lchild
, rchild
, side
);
737 op
= make_op_binary_eq(lchild
, rchild
, side
);
740 op
= make_op_binary_ne(lchild
, rchild
, side
);
743 op
= make_op_binary_gt(lchild
, rchild
, side
);
746 op
= make_op_binary_lt(lchild
, rchild
, side
);
749 op
= make_op_binary_ge(lchild
, rchild
, side
);
752 op
= make_op_binary_le(lchild
, rchild
, side
);
754 case AST_OP_BIT_RSHIFT
:
755 op
= make_op_binary_bitwise_rshift(lchild
, rchild
, side
);
757 case AST_OP_BIT_LSHIFT
:
758 op
= make_op_binary_bitwise_lshift(lchild
, rchild
, side
);
761 op
= make_op_binary_bitwise_and(lchild
, rchild
, side
);
764 op
= make_op_binary_bitwise_or(lchild
, rchild
, side
);
767 op
= make_op_binary_bitwise_xor(lchild
, rchild
, side
);
774 filter_free_ir_recursive(rchild
);
775 filter_free_ir_recursive(lchild
);
780 fprintf(stderr
, "[error] %s: binary operation '%s' not supported\n",
786 struct ir_op
*make_unary_op(struct filter_parser_ctx
*ctx
,
787 struct filter_node
*node
, enum ir_side side
)
789 switch (node
->u
.unary_op
.type
) {
790 case AST_UNARY_UNKNOWN
:
792 fprintf(stderr
, "[error] %s: unknown unary op type\n", __func__
);
797 struct ir_op
*op
, *child
;
799 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
803 op
= make_op_unary_plus(child
, side
);
805 filter_free_ir_recursive(child
);
810 case AST_UNARY_MINUS
:
812 struct ir_op
*op
, *child
;
814 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
818 op
= make_op_unary_minus(child
, side
);
820 filter_free_ir_recursive(child
);
827 struct ir_op
*op
, *child
;
829 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
833 op
= make_op_unary_not(child
, side
);
835 filter_free_ir_recursive(child
);
840 case AST_UNARY_BIT_NOT
:
842 struct ir_op
*op
, *child
;
844 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
848 op
= make_op_unary_bit_not(child
, side
);
850 filter_free_ir_recursive(child
);
861 struct ir_op
*generate_ir_recursive(struct filter_parser_ctx
*ctx
,
862 struct filter_node
*node
, enum ir_side side
)
864 switch (node
->type
) {
867 fprintf(stderr
, "[error] %s: unknown node type\n", __func__
);
872 struct ir_op
*op
, *child
;
874 child
= generate_ir_recursive(ctx
, node
->u
.root
.child
,
878 op
= make_op_root(child
, side
);
880 filter_free_ir_recursive(child
);
885 case NODE_EXPRESSION
:
886 return make_expression(ctx
, node
, side
);
888 return make_op(ctx
, node
, side
);
890 return make_unary_op(ctx
, node
, side
);
895 void filter_ir_free(struct filter_parser_ctx
*ctx
)
897 filter_free_ir_recursive(ctx
->ir_root
);
901 int filter_visitor_ir_generate(struct filter_parser_ctx
*ctx
)
905 op
= generate_ir_recursive(ctx
, &ctx
->ast
->root
, IR_LEFT
);