From b8cc390e7ed724a9ad605453227d1e4686f3a11b Mon Sep 17 00:00:00 2001 From: Ondrej Zajicek Date: Fri, 6 May 2011 22:00:54 +0200 Subject: Fixes several problems in filter syntax. - Fixes several conflicts in the grammar. - Fixes a bug in (a..b, c) pair patterns. - Makes pair patterns orthogonal. - Allows term expressions in pair patterns without additional ( ). - Allows several comma separated values in switch cases. --- filter/config.Y | 214 ++++++++++++++++++++++++++++++++++---------------------- 1 file changed, 129 insertions(+), 85 deletions(-) (limited to 'filter/config.Y') diff --git a/filter/config.Y b/filter/config.Y index ebe6f49..e635f60 100644 --- a/filter/config.Y +++ b/filter/config.Y @@ -12,32 +12,67 @@ CF_HDR CF_DEFINES -#define P(a,b) ((a<<8) | b) +#define P(a,b) ((a << 8) | b) -static int make_pair(int i1, int i2) +static inline u32 pair(u32 a, u32 b) { return (a << 16) | b; } +static inline u32 pair_a(u32 p) { return p >> 16; } +static inline u32 pair_b(u32 p) { return p & 0xFFFF; } + + +/* + * Sets and their items are during parsing handled as lists, linked + * through left ptr. The first item in a list also contains a pointer + * to the last item in a list (right ptr). For convenience, even items + * are handled as one-item lists. Lists are merged by f_merge_items(). + */ + +static inline struct f_tree * +f_new_item(struct f_val from, struct f_val to) { - unsigned u1 = i1; - unsigned u2 = i2; + struct f_tree *t = f_new_tree(); + t->right = t; + t->from = from; + t->to = to; + return t; +} - if ((u1 > 0xFFFF) || (u2 > 0xFFFF)) - cf_error( "Can't operate with value out of bounds in pair constructor"); +static inline struct f_tree * +f_merge_items(struct f_tree *a, struct f_tree *b) +{ + if (!a) return b; + a->right->left = b; + a->right = b->right; + b->right = NULL; + return a; +} - return (u1 << 16) | u2; +static inline struct f_tree * +f_new_pair_item(int fa, int ta, int fb, int tb) +{ + struct f_tree *t = f_new_tree(); + t->right = t; + t->from.type = t->to.type = T_PAIR; + t->from.val.i = pair(fa, fb); + t->to.val.i = pair(ta, tb); + return t; } -struct f_tree *f_generate_rev_wcard(int from, int to, int expr) +static inline struct f_tree * +f_new_pair_set(int fa, int ta, int fb, int tb) { - struct f_tree *ret = NULL, *last = NULL; + struct f_tree *lst = NULL; + int i; - while (from <= to) { - ret = f_new_tree(); - ret->from.type = ret->to.type = T_PAIR; - ret->from.val.i = ret->to.val.i = make_pair(from, expr); - ret->left = last; + if ((fa == ta) || ((fb == 0) && (tb == 0xFFFF))) + return f_new_pair_item(fa, ta, fb, tb); + + if ((ta < fa) || (tb < fb)) + cf_error( "From value cannot be higher that To value in pair sets"); - from++; last = ret; - } - return ret; + for (i = fa; i <= ta; i++) + lst = f_merge_items(lst, f_new_pair_item(i, i, fb, tb)); + + return lst; } CF_DECLS @@ -60,10 +95,11 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN, %type term block cmds cmds_int cmd function_body constant print_one print_list var_list var_listn dynamic_attr static_attr function_call symbol dpair bgp_path_expr %type filter filter_body where_filter -%type type break_command -%type set_item set_items switch_body +%type type break_command pair_expr +%type pair_atom +%type pair_item set_item switch_item set_items switch_items switch_body %type fprefix_set -%type set_atom fprefix fprefix_s fipa +%type set_atom switch_atom fprefix fprefix_s fipa %type decls declsn one_decl function_params %type bgp_path bgp_path_tail1 bgp_path_tail2 @@ -243,66 +279,71 @@ fipa: IPA %prec PREFIX_DUMMY { $$.type = T_IP; $$.val.px.ip = $1; } ; + + +/* + * Set constants. They are also used in switch cases. We use separate + * nonterminals for switch (set_atom/switch_atom, set_item/switch_item ...) + * to elude a collision between symbol (in expr) in set_atom and symbol + * as a function call in switch case cmds. + */ + set_atom: - expr { $$.type = T_INT; $$.val.i = $1; } /* 'SYM' included in 'expr' creates 3 reduce/shift conflicts */ + expr { $$.type = T_INT; $$.val.i = $1; } | RTRID { $$.type = T_QUAD; $$.val.i = $1; } | fipa { $$ = $1; } - | ENUM { $$.type = $1 >> 16; $$.val.i = $1 & 0xffff; } - ; + | ENUM { $$.type = pair_a($1); $$.val.i = pair_b($1); } + ; -set_item: - '(' expr ',' expr ')' { - $$ = f_new_tree(); - $$->from.type = $$->to.type = T_PAIR; - $$->from.val.i = make_pair($2, $4); - $$->to.val.i = make_pair($2, $4); - } - | '(' expr ',' expr '.' '.' expr ')' { - $$ = f_new_tree(); - $$->from.type = $$->to.type = T_PAIR; - $$->from.val.i = make_pair($2, $4); - $$->to.val.i = make_pair($2, $7); - } - | '(' expr ',' expr ')' '.' '.' '(' expr ',' expr ')' { - $$ = f_new_tree(); - $$->from.type = $$->to.type = T_PAIR; - $$->from.val.i = make_pair($2, $4); - $$->to.val.i = make_pair($9, $11); - } - | '(' '*' ',' '*' ')' { /* This is probably useless :-) */ - $$ = f_new_tree(); - $$->from.type = $$->to.type = T_PAIR; - $$->from.val.i = 0; - $$->to.val.i = 0xffffffff; - } - | '(' expr ',' '*' ')' { - $$ = f_new_tree(); - $$->from.type = $$->to.type = T_PAIR; - $$->from.val.i = make_pair($2, 0); - $$->to.val.i = make_pair($2, 0xffff); - } - | '(' '*' ',' expr ')' { - $$ = f_generate_rev_wcard(0, 0xffff, $4); - } - /* This causes 3 reduce/reduce conflicts - | '(' expr '.' '.' expr ',' expr ')' { - cf_error("Not implemented yet"); - }*/ - | set_atom { - $$ = f_new_tree(); - $$->from = $1; - $$->to = $1; +switch_atom: + NUM { $$.type = T_INT; $$.val.i = $1; } + | '(' term ')' { $$.type = T_INT; $$.val.i = f_eval_int($2); } + | RTRID { $$.type = T_QUAD; $$.val.i = $1; } + | fipa { $$ = $1; } + | ENUM { $$.type = pair_a($1); $$.val.i = pair_b($1); } + ; + +pair_expr: + term { $$ = f_eval_int($1); check_u16($$); } + +pair_atom: + pair_expr { $$ = pair($1, $1); } + | pair_expr DDOT pair_expr { $$ = pair($1, $3); } + | '*' { $$ = 0xFFFF; } + ; + +pair_item: + '(' pair_atom ',' pair_atom ')' { + $$ = f_new_pair_set(pair_a($2), pair_b($2), pair_a($4), pair_b($4)); } - | set_atom '.' '.' set_atom { - $$ = f_new_tree(); - $$->from = $1; - $$->to = $4; + | '(' pair_atom ',' pair_atom ')' DDOT '(' pair_expr ',' pair_expr ')' { + /* Hack: $2 and $4 should be pair_expr, but that would cause shift/reduce conflict */ + if ((pair_a($2) != pair_b($2)) || (pair_a($4) != pair_b($4))) + cf_error("syntax error"); + $$ = f_new_pair_item(pair_b($2), pair_b($4), $8, $10); } ; +set_item: + pair_item + | set_atom { $$ = f_new_item($1, $1); } + | set_atom DDOT set_atom { $$ = f_new_item($1, $3); } + ; + +switch_item: + pair_item + | switch_atom { $$ = f_new_item($1, $1); } + | switch_atom DDOT switch_atom { $$ = f_new_item($1, $3); } + ; + set_items: - set_item { $$ = $1; } - | set_items ',' set_item { $$ = $3; $$->left = $1; } + set_item + | set_items ',' set_item { $$ = f_merge_items($1, $3); } + ; + +switch_items: + switch_item + | switch_items ',' switch_item { $$ = f_merge_items($1, $3); } ; fprefix_s: @@ -328,18 +369,20 @@ fprefix_set: ; switch_body: /* EMPTY */ { $$ = NULL; } - | switch_body set_item ':' cmds { - $$ = $2; - $$->data = $4; - $$->left = $1; - } - | switch_body ELSECOL cmds { - $$ = f_new_tree(); - $$->from.type = T_VOID; - $$->to.type = T_VOID; - $$->data = $3; - $$->left = $1; - } + | switch_body switch_items ':' cmds { + /* Fill data fields */ + struct f_tree *t; + for (t = $2; t; t = t->left) + t->data = $4; + $$ = f_merge_items($1, $2); + } + | switch_body ELSECOL cmds { + struct f_tree *t = f_new_tree(); + t->from.type = t->to.type = T_VOID; + t->right = t; + t->data = $3; + $$ = f_merge_items($1, t); + } ; /* CONST '(' expr ')' { $$ = f_new_inst(); $$->code = 'c'; $$->aux = T_INT; $$->a2.i = $3; } */ @@ -374,7 +417,8 @@ dpair: { if (($2->aux != T_INT) || ($4->aux != T_INT)) cf_error( "Can't operate with value of non-integer type in pair constructor" ); - $$ = f_new_inst(); $$->code = 'c'; $$->aux = T_PAIR; $$->a2.i = make_pair($2->a2.i, $4->a2.i); + check_u16($2->a2.i); check_u16($4->a2.i); + $$ = f_new_inst(); $$->code = 'c'; $$->aux = T_PAIR; $$->a2.i = pair($2->a2.i, $4->a2.i); } else { $$ = f_new_inst(); $$->code = P('m', 'p'); $$->a1.p = $2; $$->a2.p = $4; } @@ -399,7 +443,7 @@ constant: /* * Maybe there are no dynamic attributes defined by protocols. * For such cases, we force the dynamic_attr list to contain - * at least an invalid token, so it's syntantically correct. + * at least an invalid token, so it is syntantically correct. */ CF_ADDTO(dynamic_attr, INVALID_TOKEN { $$ = NULL; }) -- cgit v1.2.3