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
18 #include "filter-ast.h"
19 #include "filter-parser.h"
20 #include "filter-ir.h"
22 #include <common/compat/errno.h>
23 #include <common/macros.h>
24 #include <common/string-utils/string-utils.h>
27 struct ir_op
*generate_ir_recursive(struct filter_parser_ctx
*ctx
,
28 struct filter_node
*node
, enum ir_side side
);
31 struct ir_op
*make_op_root(struct ir_op
*child
, enum ir_side side
)
35 op
= calloc(sizeof(struct ir_op
), 1);
38 switch (child
->data_type
) {
41 fprintf(stderr
, "[error] Unknown root child data type\n");
45 fprintf(stderr
, "[error] String cannot be root data type\n");
49 case IR_DATA_FIELD_REF
:
50 case IR_DATA_GET_CONTEXT_REF
:
51 case IR_DATA_EXPRESSION
:
57 op
->data_type
= child
->data_type
;
58 op
->signedness
= child
->signedness
;
59 op
->u
.root
.child
= child
;
64 enum ir_load_string_type
get_literal_string_type(const char *string
)
68 if (strutils_is_star_glob_pattern(string
)) {
69 if (strutils_is_star_at_the_end_only_glob_pattern(string
)) {
70 return IR_LOAD_STRING_TYPE_GLOB_STAR_END
;
73 return IR_LOAD_STRING_TYPE_GLOB_STAR
;
76 return IR_LOAD_STRING_TYPE_PLAIN
;
80 struct ir_op
*make_op_load_string(const char *string
, enum ir_side side
)
84 op
= calloc(sizeof(struct ir_op
), 1);
88 op
->data_type
= IR_DATA_STRING
;
89 op
->signedness
= IR_SIGN_UNKNOWN
;
91 op
->u
.load
.u
.string
.type
= get_literal_string_type(string
);
92 op
->u
.load
.u
.string
.value
= strdup(string
);
93 if (!op
->u
.load
.u
.string
.value
) {
101 struct ir_op
*make_op_load_numeric(int64_t v
, enum ir_side side
)
105 op
= calloc(sizeof(struct ir_op
), 1);
109 op
->data_type
= IR_DATA_NUMERIC
;
110 /* TODO: for now, all numeric values are signed */
111 op
->signedness
= IR_SIGNED
;
113 op
->u
.load
.u
.num
= v
;
118 struct ir_op
*make_op_load_float(double v
, enum ir_side side
)
122 op
= calloc(sizeof(struct ir_op
), 1);
126 op
->data_type
= IR_DATA_FLOAT
;
127 op
->signedness
= IR_SIGN_UNKNOWN
;
129 op
->u
.load
.u
.flt
= v
;
134 void free_load_expression(struct ir_load_expression
*load_expression
)
136 struct ir_load_expression_op
*exp_op
;
138 if (!load_expression
)
140 exp_op
= load_expression
->child
;
142 struct ir_load_expression_op
*prev_exp_op
;
146 switch (exp_op
->type
) {
147 case IR_LOAD_EXPRESSION_GET_CONTEXT_ROOT
:
148 case IR_LOAD_EXPRESSION_GET_APP_CONTEXT_ROOT
:
149 case IR_LOAD_EXPRESSION_GET_PAYLOAD_ROOT
:
150 case IR_LOAD_EXPRESSION_GET_INDEX
:
151 case IR_LOAD_EXPRESSION_LOAD_FIELD
:
153 case IR_LOAD_EXPRESSION_GET_SYMBOL
:
154 free(exp_op
->u
.symbol
);
157 prev_exp_op
= exp_op
;
158 exp_op
= exp_op
->next
;
161 free(load_expression
);
165 * Returns the first node of the chain, after initializing the next
169 struct filter_node
*load_expression_get_forward_chain(struct filter_node
*node
)
171 struct filter_node
*prev_node
;
174 assert(node
->type
== NODE_EXPRESSION
);
176 node
= node
->u
.expression
.prev
;
180 node
->u
.expression
.next
= prev_node
;
186 struct ir_load_expression
*create_load_expression(struct filter_node
*node
)
188 struct ir_load_expression
*load_exp
;
189 struct ir_load_expression_op
*load_exp_op
, *prev_op
;
192 /* Get forward chain. */
193 node
= load_expression_get_forward_chain(node
);
196 load_exp
= calloc(sizeof(struct ir_load_expression
), 1);
201 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
204 load_exp
->child
= load_exp_op
;
205 str
= node
->u
.expression
.u
.string
;
206 if (!strcmp(str
, "$ctx")) {
207 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_CONTEXT_ROOT
;
208 node
= node
->u
.expression
.next
;
210 fprintf(stderr
, "[error] Expecting identifier after \'%s\'\n", str
);
213 str
= node
->u
.expression
.u
.string
;
214 } else if (!strcmp(str
, "$app")) {
215 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_APP_CONTEXT_ROOT
;
216 node
= node
->u
.expression
.next
;
218 fprintf(stderr
, "[error] Expecting identifier after \'%s\'\n", str
);
221 str
= node
->u
.expression
.u
.string
;
222 } else if (str
[0] == '$') {
223 fprintf(stderr
, "[error] Unexpected identifier \'%s\'\n", str
);
226 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_PAYLOAD_ROOT
;
230 struct filter_node
*bracket_node
;
232 prev_op
= load_exp_op
;
233 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
236 prev_op
->next
= load_exp_op
;
237 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_SYMBOL
;
238 load_exp_op
->u
.symbol
= strdup(str
);
239 if (!load_exp_op
->u
.symbol
)
242 /* Explore brackets from current node. */
243 for (bracket_node
= node
->u
.expression
.next_bracket
;
244 bracket_node
!= NULL
;
245 bracket_node
= bracket_node
->u
.expression
.next_bracket
) {
246 prev_op
= load_exp_op
;
247 if (bracket_node
->type
!= NODE_EXPRESSION
||
248 bracket_node
->u
.expression
.type
!= AST_EXP_CONSTANT
) {
249 fprintf(stderr
, "[error] Expecting constant index in array expression\n");
252 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
255 prev_op
->next
= load_exp_op
;
256 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_INDEX
;
257 load_exp_op
->u
.index
= bracket_node
->u
.expression
.u
.constant
;
259 /* Go to next chain element. */
260 node
= node
->u
.expression
.next
;
263 str
= node
->u
.expression
.u
.string
;
265 /* Add final load field */
266 prev_op
= load_exp_op
;
267 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
270 prev_op
->next
= load_exp_op
;
271 load_exp_op
->type
= IR_LOAD_EXPRESSION_LOAD_FIELD
;
275 free_load_expression(load_exp
);
280 struct ir_op
*make_op_load_expression(struct filter_node
*node
,
285 op
= calloc(sizeof(struct ir_op
), 1);
289 op
->data_type
= IR_DATA_EXPRESSION
;
290 op
->signedness
= IR_SIGN_DYN
;
292 op
->u
.load
.u
.expression
= create_load_expression(node
);
293 if (!op
->u
.load
.u
.expression
) {
299 free_load_expression(op
->u
.load
.u
.expression
);
305 struct ir_op
*make_op_unary(enum unary_op_type unary_op_type
,
306 const char *op_str
, enum ir_op_signedness signedness
,
307 struct ir_op
*child
, enum ir_side side
)
309 struct ir_op
*op
= NULL
;
311 if (child
->data_type
== IR_DATA_STRING
) {
312 fprintf(stderr
, "[error] unary operation '%s' not allowed on string literal\n", op_str
);
316 op
= calloc(sizeof(struct ir_op
), 1);
319 op
->op
= IR_OP_UNARY
;
320 op
->data_type
= child
->data_type
;
321 op
->signedness
= signedness
;
323 op
->u
.unary
.type
= unary_op_type
;
324 op
->u
.unary
.child
= child
;
333 * unary + is pretty much useless.
336 struct ir_op
*make_op_unary_plus(struct ir_op
*child
, enum ir_side side
)
338 return make_op_unary(AST_UNARY_PLUS
, "+", child
->signedness
,
343 struct ir_op
*make_op_unary_minus(struct ir_op
*child
, enum ir_side side
)
345 return make_op_unary(AST_UNARY_MINUS
, "-", child
->signedness
,
350 struct ir_op
*make_op_unary_not(struct ir_op
*child
, enum ir_side side
)
352 return make_op_unary(AST_UNARY_NOT
, "!", child
->signedness
,
357 struct ir_op
*make_op_unary_bit_not(struct ir_op
*child
, enum ir_side side
)
359 return make_op_unary(AST_UNARY_BIT_NOT
, "~", child
->signedness
,
364 struct ir_op
*make_op_binary_compare(enum op_type bin_op_type
,
365 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
368 struct ir_op
*op
= NULL
;
370 if (left
->data_type
== IR_DATA_UNKNOWN
371 || right
->data_type
== IR_DATA_UNKNOWN
) {
372 fprintf(stderr
, "[error] binary operation '%s' has unknown operand type\n", op_str
);
376 if ((left
->data_type
== IR_DATA_STRING
377 && (right
->data_type
== IR_DATA_NUMERIC
|| right
->data_type
== IR_DATA_FLOAT
))
378 || ((left
->data_type
== IR_DATA_NUMERIC
|| left
->data_type
== IR_DATA_FLOAT
) &&
379 right
->data_type
== IR_DATA_STRING
)) {
380 fprintf(stderr
, "[error] binary operation '%s' operand type mismatch\n", op_str
);
384 op
= calloc(sizeof(struct ir_op
), 1);
387 op
->op
= IR_OP_BINARY
;
388 op
->u
.binary
.type
= bin_op_type
;
389 op
->u
.binary
.left
= left
;
390 op
->u
.binary
.right
= right
;
392 /* we return a boolean, represented as signed numeric */
393 op
->data_type
= IR_DATA_NUMERIC
;
394 op
->signedness
= IR_SIGNED
;
405 struct ir_op
*make_op_binary_eq(struct ir_op
*left
, struct ir_op
*right
,
408 return make_op_binary_compare(AST_OP_EQ
, "==", left
, right
, side
);
412 struct ir_op
*make_op_binary_ne(struct ir_op
*left
, struct ir_op
*right
,
415 return make_op_binary_compare(AST_OP_NE
, "!=", left
, right
, side
);
419 struct ir_op
*make_op_binary_gt(struct ir_op
*left
, struct ir_op
*right
,
422 return make_op_binary_compare(AST_OP_GT
, ">", left
, right
, side
);
426 struct ir_op
*make_op_binary_lt(struct ir_op
*left
, struct ir_op
*right
,
429 return make_op_binary_compare(AST_OP_LT
, "<", left
, right
, side
);
433 struct ir_op
*make_op_binary_ge(struct ir_op
*left
, struct ir_op
*right
,
436 return make_op_binary_compare(AST_OP_GE
, ">=", left
, right
, side
);
440 struct ir_op
*make_op_binary_le(struct ir_op
*left
, struct ir_op
*right
,
443 return make_op_binary_compare(AST_OP_LE
, "<=", left
, right
, side
);
447 struct ir_op
*make_op_binary_logical(enum op_type bin_op_type
,
448 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
451 struct ir_op
*op
= NULL
;
453 if (left
->data_type
== IR_DATA_UNKNOWN
454 || right
->data_type
== IR_DATA_UNKNOWN
) {
455 fprintf(stderr
, "[error] binary operation '%s' has unknown operand type\n", op_str
);
459 if (left
->data_type
== IR_DATA_STRING
460 || right
->data_type
== IR_DATA_STRING
) {
461 fprintf(stderr
, "[error] logical binary operation '%s' cannot have string operand\n", op_str
);
465 op
= calloc(sizeof(struct ir_op
), 1);
468 op
->op
= IR_OP_LOGICAL
;
469 op
->u
.binary
.type
= bin_op_type
;
470 op
->u
.binary
.left
= left
;
471 op
->u
.binary
.right
= right
;
473 /* we return a boolean, represented as signed numeric */
474 op
->data_type
= IR_DATA_NUMERIC
;
475 op
->signedness
= IR_SIGNED
;
486 struct ir_op
*make_op_binary_bitwise(enum op_type bin_op_type
,
487 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
490 struct ir_op
*op
= NULL
;
492 if (left
->data_type
== IR_DATA_UNKNOWN
493 || right
->data_type
== IR_DATA_UNKNOWN
) {
494 fprintf(stderr
, "[error] bitwise binary operation '%s' has unknown operand type\n", op_str
);
498 if (left
->data_type
== IR_DATA_STRING
499 || right
->data_type
== IR_DATA_STRING
) {
500 fprintf(stderr
, "[error] bitwise binary operation '%s' cannot have string operand\n", op_str
);
503 if (left
->data_type
== IR_DATA_FLOAT
504 || right
->data_type
== IR_DATA_FLOAT
) {
505 fprintf(stderr
, "[error] bitwise binary operation '%s' cannot have floating point operand\n", op_str
);
509 op
= calloc(sizeof(struct ir_op
), 1);
512 op
->op
= IR_OP_BINARY
;
513 op
->u
.binary
.type
= bin_op_type
;
514 op
->u
.binary
.left
= left
;
515 op
->u
.binary
.right
= right
;
517 /* we return a signed numeric */
518 op
->data_type
= IR_DATA_NUMERIC
;
519 op
->signedness
= IR_SIGNED
;
530 struct ir_op
*make_op_binary_logical_and(struct ir_op
*left
, struct ir_op
*right
,
533 return make_op_binary_logical(AST_OP_AND
, "&&", left
, right
, side
);
537 struct ir_op
*make_op_binary_logical_or(struct ir_op
*left
, struct ir_op
*right
,
540 return make_op_binary_logical(AST_OP_OR
, "||", left
, right
, side
);
544 struct ir_op
*make_op_binary_bitwise_rshift(struct ir_op
*left
, struct ir_op
*right
,
547 return make_op_binary_bitwise(AST_OP_BIT_RSHIFT
, ">>", left
, right
, side
);
551 struct ir_op
*make_op_binary_bitwise_lshift(struct ir_op
*left
, struct ir_op
*right
,
554 return make_op_binary_bitwise(AST_OP_BIT_LSHIFT
, "<<", left
, right
, side
);
558 struct ir_op
*make_op_binary_bitwise_and(struct ir_op
*left
, struct ir_op
*right
,
561 return make_op_binary_bitwise(AST_OP_BIT_AND
, "&", left
, right
, side
);
565 struct ir_op
*make_op_binary_bitwise_or(struct ir_op
*left
, struct ir_op
*right
,
568 return make_op_binary_bitwise(AST_OP_BIT_OR
, "|", left
, right
, side
);
572 struct ir_op
*make_op_binary_bitwise_xor(struct ir_op
*left
, struct ir_op
*right
,
575 return make_op_binary_bitwise(AST_OP_BIT_XOR
, "^", left
, right
, side
);
579 void filter_free_ir_recursive(struct ir_op
*op
)
586 fprintf(stderr
, "[error] Unknown op type in %s\n",
590 filter_free_ir_recursive(op
->u
.root
.child
);
593 switch (op
->data_type
) {
595 free(op
->u
.load
.u
.string
.value
);
597 case IR_DATA_FIELD_REF
: /* fall-through */
598 case IR_DATA_GET_CONTEXT_REF
:
599 free(op
->u
.load
.u
.ref
);
601 case IR_DATA_EXPRESSION
:
602 free_load_expression(op
->u
.load
.u
.expression
);
608 filter_free_ir_recursive(op
->u
.unary
.child
);
611 filter_free_ir_recursive(op
->u
.binary
.left
);
612 filter_free_ir_recursive(op
->u
.binary
.right
);
615 filter_free_ir_recursive(op
->u
.logical
.left
);
616 filter_free_ir_recursive(op
->u
.logical
.right
);
623 struct ir_op
*make_expression(struct filter_parser_ctx
*ctx
,
624 struct filter_node
*node
, enum ir_side side
)
626 switch (node
->u
.expression
.type
) {
627 case AST_EXP_UNKNOWN
:
629 fprintf(stderr
, "[error] %s: unknown expression type\n", __func__
);
633 return make_op_load_string(node
->u
.expression
.u
.string
, side
);
634 case AST_EXP_CONSTANT
:
635 return make_op_load_numeric(node
->u
.expression
.u
.constant
,
637 case AST_EXP_FLOAT_CONSTANT
:
638 return make_op_load_float(node
->u
.expression
.u
.float_constant
,
640 case AST_EXP_IDENTIFIER
:
641 case AST_EXP_GLOBAL_IDENTIFIER
:
642 return make_op_load_expression(node
, side
);
644 return generate_ir_recursive(ctx
, node
->u
.expression
.u
.child
,
650 struct ir_op
*make_op(struct filter_parser_ctx
*ctx
,
651 struct filter_node
*node
, enum ir_side side
)
653 struct ir_op
*op
= NULL
, *lchild
, *rchild
;
654 const char *op_str
= "?";
656 switch (node
->u
.op
.type
) {
659 fprintf(stderr
, "[error] %s: unknown binary op type\n", __func__
);
663 * The following binary operators other than comparators and
664 * logical and/or are not supported yet.
668 goto error_not_supported
;
671 goto error_not_supported
;
674 goto error_not_supported
;
677 goto error_not_supported
;
680 goto error_not_supported
;
682 case AST_OP_BIT_RSHIFT
:
683 case AST_OP_BIT_LSHIFT
:
687 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
690 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_RIGHT
);
692 filter_free_ir_recursive(lchild
);
703 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
706 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_RIGHT
);
708 filter_free_ir_recursive(lchild
);
716 * Both children considered as left, since we need to
719 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
722 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_LEFT
);
724 filter_free_ir_recursive(lchild
);
730 switch (node
->u
.op
.type
) {
732 op
= make_op_binary_logical_and(lchild
, rchild
, side
);
735 op
= make_op_binary_logical_or(lchild
, rchild
, side
);
738 op
= make_op_binary_eq(lchild
, rchild
, side
);
741 op
= make_op_binary_ne(lchild
, rchild
, side
);
744 op
= make_op_binary_gt(lchild
, rchild
, side
);
747 op
= make_op_binary_lt(lchild
, rchild
, side
);
750 op
= make_op_binary_ge(lchild
, rchild
, side
);
753 op
= make_op_binary_le(lchild
, rchild
, side
);
755 case AST_OP_BIT_RSHIFT
:
756 op
= make_op_binary_bitwise_rshift(lchild
, rchild
, side
);
758 case AST_OP_BIT_LSHIFT
:
759 op
= make_op_binary_bitwise_lshift(lchild
, rchild
, side
);
762 op
= make_op_binary_bitwise_and(lchild
, rchild
, side
);
765 op
= make_op_binary_bitwise_or(lchild
, rchild
, side
);
768 op
= make_op_binary_bitwise_xor(lchild
, rchild
, side
);
775 filter_free_ir_recursive(rchild
);
776 filter_free_ir_recursive(lchild
);
781 fprintf(stderr
, "[error] %s: binary operation '%s' not supported\n",
787 struct ir_op
*make_unary_op(struct filter_parser_ctx
*ctx
,
788 struct filter_node
*node
, enum ir_side side
)
790 switch (node
->u
.unary_op
.type
) {
791 case AST_UNARY_UNKNOWN
:
793 fprintf(stderr
, "[error] %s: unknown unary op type\n", __func__
);
798 struct ir_op
*op
, *child
;
800 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
804 op
= make_op_unary_plus(child
, side
);
806 filter_free_ir_recursive(child
);
811 case AST_UNARY_MINUS
:
813 struct ir_op
*op
, *child
;
815 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
819 op
= make_op_unary_minus(child
, side
);
821 filter_free_ir_recursive(child
);
828 struct ir_op
*op
, *child
;
830 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
834 op
= make_op_unary_not(child
, side
);
836 filter_free_ir_recursive(child
);
841 case AST_UNARY_BIT_NOT
:
843 struct ir_op
*op
, *child
;
845 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
849 op
= make_op_unary_bit_not(child
, side
);
851 filter_free_ir_recursive(child
);
862 struct ir_op
*generate_ir_recursive(struct filter_parser_ctx
*ctx
,
863 struct filter_node
*node
, enum ir_side side
)
865 switch (node
->type
) {
868 fprintf(stderr
, "[error] %s: unknown node type\n", __func__
);
873 struct ir_op
*op
, *child
;
875 child
= generate_ir_recursive(ctx
, node
->u
.root
.child
,
879 op
= make_op_root(child
, side
);
881 filter_free_ir_recursive(child
);
886 case NODE_EXPRESSION
:
887 return make_expression(ctx
, node
, side
);
889 return make_op(ctx
, node
, side
);
891 return make_unary_op(ctx
, node
, side
);
897 void filter_ir_free(struct filter_parser_ctx
*ctx
)
899 filter_free_ir_recursive(ctx
->ir_root
);
904 int filter_visitor_ir_generate(struct filter_parser_ctx
*ctx
)
908 op
= generate_ir_recursive(ctx
, &ctx
->ast
->root
, IR_LEFT
);