2 * filter-visitor-generate-ir.c
4 * LTTng filter generate intermediate representation
6 * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 * This library is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU Lesser General Public License, version 2.1 only,
10 * as published by the Free Software Foundation.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with this library; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29 #include "filter-ast.h"
30 #include "filter-parser.h"
31 #include "filter-ir.h"
33 #include <common/macros.h>
34 #include <common/string-utils/string-utils.h>
37 struct ir_op
*generate_ir_recursive(struct filter_parser_ctx
*ctx
,
38 struct filter_node
*node
, enum ir_side side
);
41 struct ir_op
*make_op_root(struct ir_op
*child
, enum ir_side side
)
45 op
= calloc(sizeof(struct ir_op
), 1);
48 switch (child
->data_type
) {
51 fprintf(stderr
, "[error] Unknown root child data type\n");
55 fprintf(stderr
, "[error] String cannot be root data type\n");
59 case IR_DATA_FIELD_REF
:
60 case IR_DATA_GET_CONTEXT_REF
:
61 case IR_DATA_EXPRESSION
:
67 op
->data_type
= child
->data_type
;
68 op
->signedness
= child
->signedness
;
69 op
->u
.root
.child
= child
;
74 enum ir_load_string_type
get_literal_string_type(const char *string
)
78 if (strutils_is_star_glob_pattern(string
)) {
79 if (strutils_is_star_at_the_end_only_glob_pattern(string
)) {
80 return IR_LOAD_STRING_TYPE_GLOB_STAR_END
;
83 return IR_LOAD_STRING_TYPE_GLOB_STAR
;
86 return IR_LOAD_STRING_TYPE_PLAIN
;
90 struct ir_op
*make_op_load_string(char *string
, enum ir_side side
)
94 op
= calloc(sizeof(struct ir_op
), 1);
98 op
->data_type
= IR_DATA_STRING
;
99 op
->signedness
= IR_SIGN_UNKNOWN
;
101 op
->u
.load
.u
.string
.type
= get_literal_string_type(string
);
102 op
->u
.load
.u
.string
.value
= strdup(string
);
103 if (!op
->u
.load
.u
.string
.value
) {
111 struct ir_op
*make_op_load_numeric(int64_t v
, enum ir_side side
)
115 op
= calloc(sizeof(struct ir_op
), 1);
119 op
->data_type
= IR_DATA_NUMERIC
;
120 /* TODO: for now, all numeric values are signed */
121 op
->signedness
= IR_SIGNED
;
123 op
->u
.load
.u
.num
= v
;
128 struct ir_op
*make_op_load_float(double v
, enum ir_side side
)
132 op
= calloc(sizeof(struct ir_op
), 1);
136 op
->data_type
= IR_DATA_FLOAT
;
137 op
->signedness
= IR_SIGN_UNKNOWN
;
139 op
->u
.load
.u
.flt
= v
;
144 void free_load_expression(struct ir_load_expression
*load_expression
)
146 struct ir_load_expression_op
*exp_op
;
148 if (!load_expression
)
150 exp_op
= load_expression
->child
;
152 struct ir_load_expression_op
*prev_exp_op
;
156 switch (exp_op
->type
) {
157 case IR_LOAD_EXPRESSION_GET_CONTEXT_ROOT
:
158 case IR_LOAD_EXPRESSION_GET_APP_CONTEXT_ROOT
:
159 case IR_LOAD_EXPRESSION_GET_PAYLOAD_ROOT
:
160 case IR_LOAD_EXPRESSION_GET_INDEX
:
161 case IR_LOAD_EXPRESSION_LOAD_FIELD
:
163 case IR_LOAD_EXPRESSION_GET_SYMBOL
:
164 free(exp_op
->u
.symbol
);
167 prev_exp_op
= exp_op
;
168 exp_op
= exp_op
->next
;
171 free(load_expression
);
175 * Returns the first node of the chain, after initializing the next
179 struct filter_node
*load_expression_get_forward_chain(struct filter_node
*node
)
181 struct filter_node
*prev_node
;
184 assert(node
->type
== NODE_EXPRESSION
);
186 node
= node
->u
.expression
.prev
;
190 node
->u
.expression
.next
= prev_node
;
196 struct ir_load_expression
*create_load_expression(struct filter_node
*node
)
198 struct ir_load_expression
*load_exp
;
199 struct ir_load_expression_op
*load_exp_op
, *prev_op
;
202 /* Get forward chain. */
203 node
= load_expression_get_forward_chain(node
);
206 load_exp
= calloc(sizeof(struct ir_load_expression
), 1);
211 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
214 load_exp
->child
= load_exp_op
;
215 str
= node
->u
.expression
.u
.string
;
216 if (!strcmp(str
, "$ctx")) {
217 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_CONTEXT_ROOT
;
218 node
= node
->u
.expression
.next
;
220 fprintf(stderr
, "[error] Expecting identifier after \'%s\'\n", str
);
223 str
= node
->u
.expression
.u
.string
;
224 } else if (!strcmp(str
, "$app")) {
225 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_APP_CONTEXT_ROOT
;
226 node
= node
->u
.expression
.next
;
228 fprintf(stderr
, "[error] Expecting identifier after \'%s\'\n", str
);
231 str
= node
->u
.expression
.u
.string
;
232 } else if (str
[0] == '$') {
233 fprintf(stderr
, "[error] Unexpected identifier \'%s\'\n", str
);
236 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_PAYLOAD_ROOT
;
240 struct filter_node
*bracket_node
;
242 prev_op
= load_exp_op
;
243 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
246 prev_op
->next
= load_exp_op
;
247 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_SYMBOL
;
248 load_exp_op
->u
.symbol
= strdup(str
);
249 if (!load_exp_op
->u
.symbol
)
252 /* Explore brackets from current node. */
253 for (bracket_node
= node
->u
.expression
.next_bracket
;
254 bracket_node
!= NULL
;
255 bracket_node
= bracket_node
->u
.expression
.next_bracket
) {
256 prev_op
= load_exp_op
;
257 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
260 prev_op
->next
= load_exp_op
;
261 load_exp_op
->type
= IR_LOAD_EXPRESSION_GET_INDEX
;
262 load_exp_op
->u
.index
= bracket_node
->u
.expression
.u
.constant
;
264 /* Go to next chain element. */
265 node
= node
->u
.expression
.next
;
268 str
= node
->u
.expression
.u
.string
;
270 /* Add final load field */
271 prev_op
= load_exp_op
;
272 load_exp_op
= calloc(sizeof(struct ir_load_expression_op
), 1);
275 prev_op
->next
= load_exp_op
;
276 load_exp_op
->type
= IR_LOAD_EXPRESSION_LOAD_FIELD
;
280 free_load_expression(load_exp
);
285 struct ir_op
*make_op_load_expression(struct filter_node
*node
,
290 op
= calloc(sizeof(struct ir_op
), 1);
294 op
->data_type
= IR_DATA_EXPRESSION
;
295 op
->signedness
= IR_SIGN_DYN
;
297 op
->u
.load
.u
.expression
= create_load_expression(node
);
298 if (!op
->u
.load
.u
.expression
) {
304 free_load_expression(op
->u
.load
.u
.expression
);
310 struct ir_op
*make_op_unary(enum unary_op_type unary_op_type
,
311 const char *op_str
, enum ir_op_signedness signedness
,
312 struct ir_op
*child
, enum ir_side side
)
314 struct ir_op
*op
= NULL
;
316 if (child
->data_type
== IR_DATA_STRING
) {
317 fprintf(stderr
, "[error] unary operation '%s' not allowed on string literal\n", op_str
);
321 op
= calloc(sizeof(struct ir_op
), 1);
324 op
->op
= IR_OP_UNARY
;
325 op
->data_type
= child
->data_type
;
326 op
->signedness
= signedness
;
328 op
->u
.unary
.type
= unary_op_type
;
329 op
->u
.unary
.child
= child
;
338 * unary + is pretty much useless.
341 struct ir_op
*make_op_unary_plus(struct ir_op
*child
, enum ir_side side
)
343 return make_op_unary(AST_UNARY_PLUS
, "+", child
->signedness
,
348 struct ir_op
*make_op_unary_minus(struct ir_op
*child
, enum ir_side side
)
350 return make_op_unary(AST_UNARY_MINUS
, "-", child
->signedness
,
355 struct ir_op
*make_op_unary_not(struct ir_op
*child
, enum ir_side side
)
357 return make_op_unary(AST_UNARY_NOT
, "!", child
->signedness
,
362 struct ir_op
*make_op_unary_bit_not(struct ir_op
*child
, enum ir_side side
)
364 return make_op_unary(AST_UNARY_BIT_NOT
, "~", child
->signedness
,
369 struct ir_op
*make_op_binary_compare(enum op_type bin_op_type
,
370 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
373 struct ir_op
*op
= NULL
;
375 if (left
->data_type
== IR_DATA_UNKNOWN
376 || right
->data_type
== IR_DATA_UNKNOWN
) {
377 fprintf(stderr
, "[error] binary operation '%s' has unknown operand type\n", op_str
);
381 if ((left
->data_type
== IR_DATA_STRING
382 && (right
->data_type
== IR_DATA_NUMERIC
|| right
->data_type
== IR_DATA_FLOAT
))
383 || ((left
->data_type
== IR_DATA_NUMERIC
|| left
->data_type
== IR_DATA_FLOAT
) &&
384 right
->data_type
== IR_DATA_STRING
)) {
385 fprintf(stderr
, "[error] binary operation '%s' operand type mismatch\n", op_str
);
389 op
= calloc(sizeof(struct ir_op
), 1);
392 op
->op
= IR_OP_BINARY
;
393 op
->u
.binary
.type
= bin_op_type
;
394 op
->u
.binary
.left
= left
;
395 op
->u
.binary
.right
= right
;
397 /* we return a boolean, represented as signed numeric */
398 op
->data_type
= IR_DATA_NUMERIC
;
399 op
->signedness
= IR_SIGNED
;
410 struct ir_op
*make_op_binary_eq(struct ir_op
*left
, struct ir_op
*right
,
413 return make_op_binary_compare(AST_OP_EQ
, "==", left
, right
, side
);
417 struct ir_op
*make_op_binary_ne(struct ir_op
*left
, struct ir_op
*right
,
420 return make_op_binary_compare(AST_OP_NE
, "!=", left
, right
, side
);
424 struct ir_op
*make_op_binary_gt(struct ir_op
*left
, struct ir_op
*right
,
427 return make_op_binary_compare(AST_OP_GT
, ">", left
, right
, side
);
431 struct ir_op
*make_op_binary_lt(struct ir_op
*left
, struct ir_op
*right
,
434 return make_op_binary_compare(AST_OP_LT
, "<", left
, right
, side
);
438 struct ir_op
*make_op_binary_ge(struct ir_op
*left
, struct ir_op
*right
,
441 return make_op_binary_compare(AST_OP_GE
, ">=", left
, right
, side
);
445 struct ir_op
*make_op_binary_le(struct ir_op
*left
, struct ir_op
*right
,
448 return make_op_binary_compare(AST_OP_LE
, "<=", left
, right
, side
);
452 struct ir_op
*make_op_binary_logical(enum op_type bin_op_type
,
453 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
456 struct ir_op
*op
= NULL
;
458 if (left
->data_type
== IR_DATA_UNKNOWN
459 || right
->data_type
== IR_DATA_UNKNOWN
) {
460 fprintf(stderr
, "[error] binary operation '%s' has unknown operand type\n", op_str
);
464 if (left
->data_type
== IR_DATA_STRING
465 || right
->data_type
== IR_DATA_STRING
) {
466 fprintf(stderr
, "[error] logical binary operation '%s' cannot have string operand\n", op_str
);
470 op
= calloc(sizeof(struct ir_op
), 1);
473 op
->op
= IR_OP_LOGICAL
;
474 op
->u
.binary
.type
= bin_op_type
;
475 op
->u
.binary
.left
= left
;
476 op
->u
.binary
.right
= right
;
478 /* we return a boolean, represented as signed numeric */
479 op
->data_type
= IR_DATA_NUMERIC
;
480 op
->signedness
= IR_SIGNED
;
491 struct ir_op
*make_op_binary_bitwise(enum op_type bin_op_type
,
492 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
495 struct ir_op
*op
= NULL
;
497 if (left
->data_type
== IR_DATA_UNKNOWN
498 || right
->data_type
== IR_DATA_UNKNOWN
) {
499 fprintf(stderr
, "[error] bitwise binary operation '%s' has unknown operand type\n", op_str
);
503 if (left
->data_type
== IR_DATA_STRING
504 || right
->data_type
== IR_DATA_STRING
) {
505 fprintf(stderr
, "[error] bitwise binary operation '%s' cannot have string operand\n", op_str
);
508 if (left
->data_type
== IR_DATA_FLOAT
509 || right
->data_type
== IR_DATA_FLOAT
) {
510 fprintf(stderr
, "[error] bitwise binary operation '%s' cannot have floating point operand\n", op_str
);
514 op
= calloc(sizeof(struct ir_op
), 1);
517 op
->op
= IR_OP_BINARY
;
518 op
->u
.binary
.type
= bin_op_type
;
519 op
->u
.binary
.left
= left
;
520 op
->u
.binary
.right
= right
;
522 /* we return a signed numeric */
523 op
->data_type
= IR_DATA_NUMERIC
;
524 op
->signedness
= IR_SIGNED
;
535 struct ir_op
*make_op_binary_logical_and(struct ir_op
*left
, struct ir_op
*right
,
538 return make_op_binary_logical(AST_OP_AND
, "&&", left
, right
, side
);
542 struct ir_op
*make_op_binary_logical_or(struct ir_op
*left
, struct ir_op
*right
,
545 return make_op_binary_logical(AST_OP_OR
, "||", left
, right
, side
);
549 struct ir_op
*make_op_binary_bitwise_rshift(struct ir_op
*left
, struct ir_op
*right
,
552 return make_op_binary_bitwise(AST_OP_BIT_RSHIFT
, ">>", left
, right
, side
);
556 struct ir_op
*make_op_binary_bitwise_lshift(struct ir_op
*left
, struct ir_op
*right
,
559 return make_op_binary_bitwise(AST_OP_BIT_LSHIFT
, "<<", left
, right
, side
);
563 struct ir_op
*make_op_binary_bitwise_and(struct ir_op
*left
, struct ir_op
*right
,
566 return make_op_binary_bitwise(AST_OP_BIT_AND
, "&", left
, right
, side
);
570 struct ir_op
*make_op_binary_bitwise_or(struct ir_op
*left
, struct ir_op
*right
,
573 return make_op_binary_bitwise(AST_OP_BIT_OR
, "|", left
, right
, side
);
577 struct ir_op
*make_op_binary_bitwise_xor(struct ir_op
*left
, struct ir_op
*right
,
580 return make_op_binary_bitwise(AST_OP_BIT_XOR
, "^", left
, right
, side
);
584 void filter_free_ir_recursive(struct ir_op
*op
)
591 fprintf(stderr
, "[error] Unknown op type in %s\n",
595 filter_free_ir_recursive(op
->u
.root
.child
);
598 switch (op
->data_type
) {
600 free(op
->u
.load
.u
.string
.value
);
602 case IR_DATA_FIELD_REF
: /* fall-through */
603 case IR_DATA_GET_CONTEXT_REF
:
604 free(op
->u
.load
.u
.ref
);
606 case IR_DATA_EXPRESSION
:
607 free_load_expression(op
->u
.load
.u
.expression
);
613 filter_free_ir_recursive(op
->u
.unary
.child
);
616 filter_free_ir_recursive(op
->u
.binary
.left
);
617 filter_free_ir_recursive(op
->u
.binary
.right
);
620 filter_free_ir_recursive(op
->u
.logical
.left
);
621 filter_free_ir_recursive(op
->u
.logical
.right
);
628 struct ir_op
*make_expression(struct filter_parser_ctx
*ctx
,
629 struct filter_node
*node
, enum ir_side side
)
631 switch (node
->u
.expression
.type
) {
632 case AST_EXP_UNKNOWN
:
634 fprintf(stderr
, "[error] %s: unknown expression type\n", __func__
);
638 return make_op_load_string(node
->u
.expression
.u
.string
, side
);
639 case AST_EXP_CONSTANT
:
640 return make_op_load_numeric(node
->u
.expression
.u
.constant
,
642 case AST_EXP_FLOAT_CONSTANT
:
643 return make_op_load_float(node
->u
.expression
.u
.float_constant
,
645 case AST_EXP_IDENTIFIER
:
646 case AST_EXP_GLOBAL_IDENTIFIER
:
647 return make_op_load_expression(node
, side
);
649 return generate_ir_recursive(ctx
, node
->u
.expression
.u
.child
,
655 struct ir_op
*make_op(struct filter_parser_ctx
*ctx
,
656 struct filter_node
*node
, enum ir_side side
)
658 struct ir_op
*op
= NULL
, *lchild
, *rchild
;
659 const char *op_str
= "?";
661 switch (node
->u
.op
.type
) {
664 fprintf(stderr
, "[error] %s: unknown binary op type\n", __func__
);
668 * The following binary operators other than comparators and
669 * logical and/or are not supported yet.
673 goto error_not_supported
;
676 goto error_not_supported
;
679 goto error_not_supported
;
682 goto error_not_supported
;
685 goto error_not_supported
;
687 case AST_OP_BIT_RSHIFT
:
688 case AST_OP_BIT_LSHIFT
:
692 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
695 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_RIGHT
);
697 filter_free_ir_recursive(lchild
);
708 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
711 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_RIGHT
);
713 filter_free_ir_recursive(lchild
);
721 * Both children considered as left, since we need to
724 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
727 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_LEFT
);
729 filter_free_ir_recursive(lchild
);
735 switch (node
->u
.op
.type
) {
737 op
= make_op_binary_logical_and(lchild
, rchild
, side
);
740 op
= make_op_binary_logical_or(lchild
, rchild
, side
);
743 op
= make_op_binary_eq(lchild
, rchild
, side
);
746 op
= make_op_binary_ne(lchild
, rchild
, side
);
749 op
= make_op_binary_gt(lchild
, rchild
, side
);
752 op
= make_op_binary_lt(lchild
, rchild
, side
);
755 op
= make_op_binary_ge(lchild
, rchild
, side
);
758 op
= make_op_binary_le(lchild
, rchild
, side
);
760 case AST_OP_BIT_RSHIFT
:
761 op
= make_op_binary_bitwise_rshift(lchild
, rchild
, side
);
763 case AST_OP_BIT_LSHIFT
:
764 op
= make_op_binary_bitwise_lshift(lchild
, rchild
, side
);
767 op
= make_op_binary_bitwise_and(lchild
, rchild
, side
);
770 op
= make_op_binary_bitwise_or(lchild
, rchild
, side
);
773 op
= make_op_binary_bitwise_xor(lchild
, rchild
, side
);
780 filter_free_ir_recursive(rchild
);
781 filter_free_ir_recursive(lchild
);
786 fprintf(stderr
, "[error] %s: binary operation '%s' not supported\n",
792 struct ir_op
*make_unary_op(struct filter_parser_ctx
*ctx
,
793 struct filter_node
*node
, enum ir_side side
)
795 switch (node
->u
.unary_op
.type
) {
796 case AST_UNARY_UNKNOWN
:
798 fprintf(stderr
, "[error] %s: unknown unary op type\n", __func__
);
803 struct ir_op
*op
, *child
;
805 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
809 op
= make_op_unary_plus(child
, side
);
811 filter_free_ir_recursive(child
);
816 case AST_UNARY_MINUS
:
818 struct ir_op
*op
, *child
;
820 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
824 op
= make_op_unary_minus(child
, side
);
826 filter_free_ir_recursive(child
);
833 struct ir_op
*op
, *child
;
835 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
839 op
= make_op_unary_not(child
, side
);
841 filter_free_ir_recursive(child
);
846 case AST_UNARY_BIT_NOT
:
848 struct ir_op
*op
, *child
;
850 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
854 op
= make_op_unary_bit_not(child
, side
);
856 filter_free_ir_recursive(child
);
867 struct ir_op
*generate_ir_recursive(struct filter_parser_ctx
*ctx
,
868 struct filter_node
*node
, enum ir_side side
)
870 switch (node
->type
) {
873 fprintf(stderr
, "[error] %s: unknown node type\n", __func__
);
878 struct ir_op
*op
, *child
;
880 child
= generate_ir_recursive(ctx
, node
->u
.root
.child
,
884 op
= make_op_root(child
, side
);
886 filter_free_ir_recursive(child
);
891 case NODE_EXPRESSION
:
892 return make_expression(ctx
, node
, side
);
894 return make_op(ctx
, node
, side
);
896 return make_unary_op(ctx
, node
, side
);
902 void filter_ir_free(struct filter_parser_ctx
*ctx
)
904 filter_free_ir_recursive(ctx
->ir_root
);
909 int filter_visitor_ir_generate(struct filter_parser_ctx
*ctx
)
913 op
= generate_ir_recursive(ctx
, &ctx
->ast
->root
, IR_LEFT
);