filter/config.Y

   1 /*
   2  *      BIRD - filters
   3  *
   4  *      Copyright 1998--2000 Pavel Machek
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  *
   8         FIXME: priority of ! should be lower
   9  */
  10
  11 CF_HDR
  12
  13 #include "filter/f-inst.h"
  14 #include "filter/data.h"
  15
  16 CF_DEFINES
  17
  18 static inline u32 pair(u32 a, u32 b) { return (a << 16) | b; }
  19 static inline u32 pair_a(u32 p) { return p >> 16; }
  20 static inline u32 pair_b(u32 p) { return p & 0xFFFF; }
  21
  22 static struct symbol *this_function;
  23
  24 static struct f_method_scope {
  25   struct f_inst *object;
  26   struct sym_scope *main;
  27   struct sym_scope scope;
  28 } f_method_scope_stack[32];
  29 static int f_method_scope_pos = -1;
  30
  31 #define FM  (f_method_scope_stack[f_method_scope_pos])
  32
  33 static inline void f_method_call_start(struct f_inst *object)
  34 {
  35   if (object->type == T_VOID)
  36     cf_error("Can't infer type to properly call a method, please assign the value to a variable");
  37   if (++f_method_scope_pos >= (int) ARRAY_SIZE(f_method_scope_stack))
  38     cf_error("Too many nested method calls");
  39
  40   struct sym_scope *scope = f_type_method_scope(object->type);
  41   if (!scope)
  42     cf_error("No methods defined for type %s", f_type_name(object->type));
  43
  44   FM = (struct f_method_scope) {
  45     .object = object,
  46     .main = new_config->current_scope,
  47     .scope = {
  48       .next = NULL,
  49       .hash = scope->hash,
  50       .active = 1,
  51       .block = 1,
  52       .readonly = 1,
  53     },
  54   };
  55   new_config->current_scope = &FM.scope;
  56 }
  57
  58 static inline void f_method_call_args(void)
  59 {
  60   ASSERT_DIE(FM.scope.active);
  61   FM.scope.active = 0;
  62
  63   new_config->current_scope = FM.main;
  64 }
  65
  66 static inline void f_method_call_end(void)
  67 {
  68   ASSERT_DIE(f_method_scope_pos >= 0);
  69   if (FM.scope.active) {
  70     ASSERT_DIE(&FM.scope == new_config->current_scope);
  71     new_config->current_scope = FM.main;
  72
  73     FM.scope.active = 0;
  74   }
  75
  76   f_method_scope_pos--;
  77 }
  78
  79 static int
  80 f_new_var(struct sym_scope *s)
  81 {
  82   /*
  83    * - A variable is an offset on vstack from vbase.
  84    * - Vbase is set on filter start / function call.
  85    * - Scopes contain (non-frame) block scopes inside filter/function scope
  86    * - Each scope knows number of vars in that scope
  87    * - Offset is therefore a sum of 'slots' up to filter/function scope
  88    * - New variables are added on top of vstk, so intermediate values cannot
  89    *   be there during FI_VAR_INIT. I.e. no 'var' inside 'term'.
  90    * - Also, each f_line must always have its scope, otherwise a variable may
  91    *   be defined but not initialized if relevant f_line is not executed.
  92    */
  93
  94   int offset = s->slots++;
  95
  96   while (s->block)
  97   {
  98     s = s->next;
  99     ASSERT(s);
 100     offset += s->slots;
 101   }
 102
 103   if (offset >= 0xff)
 104     cf_error("Too many variables, at most 255 allowed");
 105
 106   return offset;
 107 }
 108
 109 /*
 110  * Sets and their items are during parsing handled as lists, linked
 111  * through left ptr. The first item in a list also contains a pointer
 112  * to the last item in a list (right ptr). For convenience, even items
 113  * are handled as one-item lists. Lists are merged by f_merge_items().
 114  */
 115 static int
 116 f_valid_set_type(int type)
 117 {
 118   switch (type)
 119   {
 120   case T_INT:
 121   case T_PAIR:
 122   case T_QUAD:
 123   case T_ENUM:
 124   case T_IP:
 125   case T_EC:
 126   case T_LC:
 127   case T_RD:
 128     return 1;
 129
 130   default:
 131     return 0;
 132   }
 133 }
 134
 135 static inline struct f_tree *
 136 f_new_item(struct f_val from, struct f_val to)
 137 {
 138   struct f_tree *t = f_new_tree();
 139   t->right = t;
 140   t->from = from;
 141   t->to = to;
 142   return t;
 143 }
 144
 145 static inline struct f_tree *
 146 f_merge_items(struct f_tree *a, struct f_tree *b)
 147 {
 148   if (!a) return b;
 149   a->right->left = b;
 150   a->right = b->right;
 151   b->right = NULL;
 152   return a;
 153 }
 154
 155 static inline struct f_tree *
 156 f_new_pair_item(int fa, int ta, int fb, int tb)
 157 {
 158   check_u16(fa);
 159   check_u16(ta);
 160   check_u16(fb);
 161   check_u16(tb);
 162
 163   if ((ta < fa) || (tb < fb))
 164     cf_error( "From value cannot be higher that To value in pair sets");
 165
 166   struct f_tree *t = f_new_tree();
 167   t->right = t;
 168   t->from.type = t->to.type = T_PAIR;
 169   t->from.val.i = pair(fa, fb);
 170   t->to.val.i = pair(ta, tb);
 171   return t;
 172 }
 173
 174 static inline struct f_tree *
 175 f_new_pair_set(int fa, int ta, int fb, int tb)
 176 {
 177   check_u16(fa);
 178   check_u16(ta);
 179   check_u16(fb);
 180   check_u16(tb);
 181
 182   if ((ta < fa) || (tb < fb))
 183     cf_error( "From value cannot be higher that To value in pair sets");
 184
 185   struct f_tree *lst = NULL;
 186   int i;
 187
 188   for (i = fa; i <= ta; i++)
 189     lst = f_merge_items(lst, f_new_pair_item(i, i, fb, tb));
 190
 191   return lst;
 192 }
 193
 194 #define CC_ALL 0xFFFF
 195 #define EC_ALL 0xFFFFFFFF
 196 #define LC_ALL 0xFFFFFFFF
 197
 198 static struct f_tree *
 199 f_new_ec_item(u32 kind, u32 ipv4_used, u32 key, u32 vf, u32 vt)
 200 {
 201   u64 fm, to;
 202
 203   if ((kind != EC_GENERIC) && (ipv4_used || (key >= 0x10000))) {
 204     check_u16(vf);
 205     if (vt == EC_ALL)
 206       vt = 0xFFFF;
 207     else
 208       check_u16(vt);
 209   }
 210
 211   if (kind == EC_GENERIC) {
 212     fm = ec_generic(key, vf);
 213     to = ec_generic(key, vt);
 214   }
 215   else if (ipv4_used) {
 216     fm = ec_ip4(kind, key, vf);
 217     to = ec_ip4(kind, key, vt);
 218   }
 219   else if (key < 0x10000) {
 220     fm = ec_as2(kind, key, vf);
 221     to = ec_as2(kind, key, vt);
 222   }
 223   else {
 224     fm = ec_as4(kind, key, vf);
 225     to = ec_as4(kind, key, vt);
 226   }
 227
 228   struct f_tree *t = f_new_tree();
 229   t->right = t;
 230   t->from.type = t->to.type = T_EC;
 231   t->from.val.ec = fm;
 232   t->to.val.ec = to;
 233   return t;
 234 }
 235
 236 static struct f_tree *
 237 f_new_lc_item(u32 f1, u32 t1, u32 f2, u32 t2, u32 f3, u32 t3)
 238 {
 239   struct f_tree *t = f_new_tree();
 240   t->right = t;
 241   t->from.type = t->to.type = T_LC;
 242   t->from.val.lc = (lcomm) {f1, f2, f3};
 243   t->to.val.lc = (lcomm) {t1, t2, t3};
 244   return t;
 245 }
 246
 247 static inline struct f_inst *
 248 f_const_empty(enum f_type t)
 249 {
 250   switch (t) {
 251     case T_PATH:
 252     case T_CLIST:
 253     case T_ECLIST:
 254     case T_LCLIST:
 255       return f_new_inst(FI_CONSTANT, (struct f_val) {
 256         .type = t,
 257         .val.ad = &null_adata,
 258       });
 259     default:
 260       return f_new_inst(FI_CONSTANT, (struct f_val) {});
 261   }
 262 }
 263
 264 /*
 265  * Remove all new lines and doubled whitespaces
 266  * and convert all tabulators to spaces
 267  * and return a copy of string
 268  */
 269 char *
 270 assert_copy_expr(const char *start, size_t len)
 271 {
 272   /* XXX: Allocates maybe a little more memory than we really finally need */
 273   char *str = cfg_alloc(len + 1);
 274
 275   char *dst = str;
 276   const char *src = start - 1;
 277   const char *end = start + len;
 278   while (++src < end)
 279   {
 280     if (*src == '\n')
 281       continue;
 282
 283     /* Skip doubled whitespaces */
 284     if (src != start)
 285     {
 286       const char *prev = src - 1;
 287       if ((*src == ' ' || *src == '\t') && (*prev == ' ' || *prev == '\t'))
 288         continue;
 289     }
 290
 291     if (*src == '\t')
 292       *dst = ' ';
 293     else
 294       *dst = *src;
 295
 296     dst++;
 297   }
 298   *dst = '\0';
 299
 300   return str;
 301 }
 302
 303 /*
 304  * assert_done - create f_instruction of bt_assert
 305  * @expr: expression in bt_assert()
 306  * @start: pointer to first char of test expression
 307  * @end: pointer to the last char of test expression
 308  */
 309 static struct f_inst *
 310 assert_done(struct f_inst *expr, const char *start, const char *end)
 311 {
 312   return f_new_inst(FI_ASSERT, expr,
 313     (end >= start) ?
 314       assert_copy_expr(start, end - start + 1)
 315     : "???");
 316 }
 317
 318 static struct f_inst *
 319 f_lval_getter(struct f_lval *lval)
 320 {
 321   switch (lval->type) {
 322     case F_LVAL_VARIABLE:       return f_new_inst(FI_VAR_GET, lval->sym);
 323     case F_LVAL_SA:             return f_new_inst(FI_RTA_GET, lval->sa);
 324     case F_LVAL_EA:             return f_new_inst(FI_EA_GET, lval->da);
 325     default:                    bug("Unknown lval type");
 326   }
 327 }
 328
 329 static struct f_inst *
 330 f_lval_setter(struct f_lval *lval, struct f_inst *expr)
 331 {
 332   switch (lval->type) {
 333     case F_LVAL_VARIABLE:       return f_new_inst(FI_VAR_SET, expr, lval->sym);
 334     case F_LVAL_SA:             return f_new_inst(FI_RTA_SET, expr, lval->sa);
 335     case F_LVAL_EA:             return f_new_inst(FI_EA_SET, expr, lval->da);
 336     default:                    bug("Unknown lval type");
 337   }
 338 }
 339
 340 static struct f_inst *
 341 assert_assign(struct f_lval *lval, struct f_inst *expr, const char *start, const char *end)
 342 {
 343   struct f_inst *setter = f_lval_setter(lval, expr),
 344                 *getter = f_lval_getter(lval);
 345
 346   struct f_inst *checker = f_new_inst(FI_EQ, expr, getter);
 347   setter->next = checker;
 348
 349   return assert_done(setter, start, end);
 350 }
 351
 352 CF_DECLS
 353
 354 CF_KEYWORDS_EXCLUSIVE(IN)
 355 CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN,
 356         ACCEPT, REJECT, ERROR,
 357         INT, BOOL, IP, PREFIX, RD, PAIR, QUAD, EC, LC,
 358         SET, STRING, BYTESTRING, BGPMASK, BGPPATH, CLIST, ECLIST, LCLIST,
 359         IF, THEN, ELSE, CASE,
 360         FOR, DO,
 361         TRUE, FALSE, RT, RO, UNKNOWN, GENERIC,
 362         FROM, GW, NET, PROTO, SOURCE, SCOPE, DEST, IFNAME, IFINDEX, WEIGHT, GW_MPLS, ONLINK,
 363         PREFERENCE,
 364         ROA_CHECK,
 365         DEFINED,
 366         ADD, DELETE, RESET,
 367         PREPEND,
 368         EMPTY,
 369         FILTER, WHERE, EVAL, ATTRIBUTE,
 370         FROM_HEX,
 371         BT_ASSERT, BT_TEST_SUITE, BT_CHECK_ASSIGN, BT_TEST_SAME, FORMAT)
 372
 373 %nonassoc THEN
 374 %nonassoc ELSE
 375
 376 %type <xp> cmds_int cmd_prep
 377 %type <x> term term_bs cmd cmd_var cmds cmds_scoped constant constructor var var_list var_list_r function_call symbol_value bgp_path_expr bgp_path bgp_path_tail term_dot_method method_name_cont
 378 %type <fda> dynamic_attr
 379 %type <fsa> static_attr
 380 %type <f> filter where_filter
 381 %type <fl> filter_body function_body
 382 %type <flv> lvalue
 383 %type <i> type function_vars function_type
 384 %type <fa> function_argsn function_args
 385 %type <ecs> ec_kind
 386 %type <fret> break_command
 387 %type <i32> cnum
 388 %type <e> pair_item ec_item lc_item set_item switch_item set_items switch_items switch_body
 389 %type <trie> fprefix_set
 390 %type <v> set_atom switch_atom fipa
 391 %type <px> fprefix
 392 %type <t> get_cf_position
 393 %type <s> for_var
 394
 395 CF_GRAMMAR
 396
 397 conf: filter_def ;
 398 filter_def:
 399    FILTER symbol {
 400      $2 = cf_define_symbol(new_config, $2, SYM_FILTER, filter, NULL);
 401      cf_push_scope( new_config, $2 );
 402      this_function = NULL;
 403    } filter_body {
 404      struct filter *f = cfg_alloc(sizeof(struct filter));
 405      *f = (struct filter) { .sym = $2, .root = $4 };
 406      $2->filter = f;
 407
 408      cf_pop_scope(new_config);
 409    }
 410  ;
 411
 412 conf: filter_eval ;
 413 filter_eval:
 414    EVAL term { cf_eval_int($2); }
 415  ;
 416
 417 conf: custom_attr ;
 418 custom_attr: ATTRIBUTE type symbol ';' {
 419   cf_define_symbol(new_config, $3, SYM_ATTRIBUTE, attribute, ca_lookup(new_config->pool, $3->name, $2)->fda);
 420 };
 421
 422 conf: bt_test_suite ;
 423 bt_test_suite:
 424  BT_TEST_SUITE '(' symbol_known ',' text ')' {
 425   cf_assert_symbol($3, SYM_FUNCTION);
 426   struct f_bt_test_suite *t = cfg_allocz(sizeof(struct f_bt_test_suite));
 427   t->fn = $3->function;
 428   t->fn_name = $3->name;
 429   t->dsc = $5;
 430
 431   add_tail(&new_config->tests, &t->n);
 432  }
 433  ;
 434
 435 conf: bt_test_same ;
 436 bt_test_same:
 437  BT_TEST_SAME '(' symbol_known ',' symbol_known ',' NUM ')' {
 438   cf_assert_symbol($3, SYM_FUNCTION);
 439   cf_assert_symbol($5, SYM_FUNCTION);
 440   struct f_bt_test_suite *t = cfg_allocz(sizeof(struct f_bt_test_suite));
 441   t->fn = $3->function;
 442   t->cmp = $5->function;
 443   t->result = $7;
 444   t->fn_name = $3->name;
 445   t->dsc = $5->name;
 446   add_tail(&new_config->tests, &t->n);
 447  }
 448  ;
 449
 450 type:
 451    INT { $$ = T_INT; }
 452  | BOOL { $$ = T_BOOL; }
 453  | IP { $$ = T_IP; }
 454  | RD { $$ = T_RD; }
 455  | PREFIX { $$ = T_NET; }
 456  | PAIR { $$ = T_PAIR; }
 457  | QUAD { $$ = T_QUAD; }
 458  | EC { $$ = T_EC; }
 459  | LC { $$ = T_LC; }
 460  | STRING { $$ = T_STRING; }
 461  | BYTESTRING { $$ = T_BYTESTRING; }
 462  | BGPMASK { $$ = T_PATH_MASK; }
 463  | BGPPATH { $$ = T_PATH; }
 464  | CLIST { $$ = T_CLIST; }
 465  | ECLIST { $$ = T_ECLIST; }
 466  | LCLIST { $$ = T_LCLIST; }
 467  | type SET {
 468         switch ($1) {
 469           case T_INT:
 470           case T_PAIR:
 471           case T_QUAD:
 472           case T_EC:
 473           case T_LC:
 474           case T_RD:
 475           case T_IP:
 476                $$ = T_SET;
 477                break;
 478
 479           case T_NET:
 480                $$ = T_PREFIX_SET;
 481             break;
 482
 483           default:
 484                 cf_error( "You can't create sets of this type." );
 485         }
 486    }
 487  ;
 488
 489 function_argsn:
 490    /* EMPTY */ { $$ = NULL; }
 491  | function_argsn type symbol ';' {
 492      if ($3->scope->slots >= 0xfe) cf_error("Too many declarations, at most 255 allowed");
 493      $$ = cfg_alloc(sizeof(struct f_arg));
 494      $$->arg = cf_define_symbol(new_config, $3, SYM_VARIABLE | $2, offset, sym_->scope->slots++);
 495      $$->next = $1;
 496    }
 497  ;
 498
 499 function_args:
 500    '(' ')' { $$ = NULL; }
 501  | '(' function_argsn type symbol ')' {
 502      $$ = cfg_alloc(sizeof(struct f_arg));
 503      $$->arg = cf_define_symbol(new_config, $4, SYM_VARIABLE | $3, offset, sym_->scope->slots++);
 504      $$->next = $2;
 505    }
 506  ;
 507
 508 function_vars:
 509    /* EMPTY */ { $$ = 0; }
 510  | function_vars type symbol ';' {
 511      cf_define_symbol(new_config, $3, SYM_VARIABLE | $2, offset, f_new_var(sym_->scope));
 512      $$ = $1 + 1;
 513    }
 514  ;
 515
 516 function_type:
 517    /* EMPTY */ { $$ = T_VOID; }
 518  | IMP type { $$ = $2; }
 519  ;
 520
 521 filter_body: function_body ;
 522
 523 filter:
 524    symbol_known {
 525      cf_assert_symbol($1, SYM_FILTER);
 526      $$ = $1->filter;
 527    }
 528  | {
 529      cf_push_scope(new_config, NULL);
 530      this_function = NULL;
 531    } filter_body {
 532      struct filter *f = cfg_alloc(sizeof(struct filter));
 533      *f = (struct filter) { .root = $2 };
 534      $$ = f;
 535
 536      cf_pop_scope(new_config);
 537    }
 538  ;
 539
 540 where_filter:
 541    WHERE term {
 542      /* Construct 'IF term THEN { ACCEPT; } ELSE { REJECT; }' */
 543      $$ = f_new_where($2);
 544    }
 545  ;
 546
 547 function_body:
 548    function_vars '{' cmds '}' {
 549      $$ = f_linearize($3, 0);
 550      $$->vars = $1;
 551    }
 552  ;
 553
 554 conf: function_def ;
 555
 556 function_def:
 557    FUNCTION symbol {
 558      DBG( "Beginning of function %s\n", $2->name );
 559      this_function = cf_define_symbol(new_config, $2, SYM_FUNCTION, function, NULL);
 560      cf_push_scope(new_config, this_function);
 561    } function_args function_type {
 562      /* Make dummy f_line for storing function prototype */
 563      struct f_line *dummy = cfg_allocz(sizeof(struct f_line));
 564      this_function->function = dummy;
 565
 566      dummy->return_type = $5;
 567
 568      /* Revert the args */
 569      while ($4) {
 570        struct f_arg *tmp = $4;
 571        $4 = $4->next;
 572
 573        tmp->next = dummy->arg_list;
 574        dummy->arg_list = tmp;
 575        dummy->args++;
 576      }
 577    } function_body {
 578      $7->args = this_function->function->args;
 579      $7->arg_list = this_function->function->arg_list;
 580      $7->return_type = this_function->function->return_type;
 581      $2->function = $7;
 582      cf_pop_scope(new_config);
 583    }
 584  ;
 585
 586 /* Programs */
 587
 588 cmds: /* EMPTY */ { $$ = NULL; }
 589  | cmds_int { $$ = $1.begin; }
 590  ;
 591
 592 cmds_scoped: { cf_push_soft_scope(new_config); } cmds { cf_pop_soft_scope(new_config); $$ = $2; } ;
 593
 594 cmd_var: var | cmd ;
 595
 596 cmd_prep: cmd_var {
 597   $$.begin = $$.end = $1;
 598   if ($1)
 599     while ($$.end->next)
 600       $$.end = $$.end->next;
 601 }
 602  ;
 603
 604 cmds_int: cmd_prep
 605  | cmds_int cmd_prep {
 606   if (!$1.begin)
 607     $$ = $2;
 608   else if (!$2.begin)
 609     $$ = $1;
 610   else {
 611     $$.begin = $1.begin;
 612     $$.end = $2.end;
 613     $1.end->next = $2.begin;
 614   }
 615  }
 616  ;
 617
 618 /*
 619  * Complex types, their bison value is struct f_val
 620  */
 621 fipa:
 622    IP4 %prec PREFIX_DUMMY { $$.type = T_IP; $$.val.ip = ipa_from_ip4($1); }
 623  | IP6 %prec PREFIX_DUMMY { $$.type = T_IP; $$.val.ip = ipa_from_ip6($1); }
 624  ;
 625
 626
 627
 628 /*
 629  * Set constants. They are also used in switch cases. We use separate
 630  * nonterminals for switch (set_atom/switch_atom, set_item/switch_item ...)
 631  * to elude a collision between symbol (in expr) in set_atom and symbol
 632  * as a function call in switch case cmds.
 633  */
 634
 635 set_atom:
 636    NUM    { $$.type = T_INT; $$.val.i = $1; }
 637  | fipa   { $$ = $1; }
 638  | VPN_RD { $$.type = T_RD; $$.val.ec = $1; }
 639  | ENUM   { $$.type = pair_a($1); $$.val.i = pair_b($1); }
 640  | '(' term ')' {
 641      $$ = cf_eval($2, T_VOID);
 642      if (!f_valid_set_type($$.type)) cf_error("Set-incompatible type");
 643    }
 644  | symbol_known {
 645      cf_assert_symbol($1, SYM_CONSTANT);
 646      if (!f_valid_set_type(SYM_TYPE($1))) cf_error("%s: set-incompatible type", $1->name);
 647      $$ = *$1->val;
 648    }
 649  ;
 650
 651 switch_atom:
 652    NUM   { $$.type = T_INT; $$.val.i = $1; }
 653  | '(' term ')' { $$ = cf_eval($2, T_INT); }
 654  | fipa  { $$ = $1; }
 655  | ENUM  { $$.type = pair_a($1); $$.val.i = pair_b($1); }
 656  ;
 657
 658 cnum:
 659    term { $$ = cf_eval_int($1); }
 660
 661 pair_item:
 662    '(' cnum ',' cnum ')'                { $$ = f_new_pair_item($2, $2, $4, $4); }
 663  | '(' cnum ',' cnum DDOT cnum ')'      { $$ = f_new_pair_item($2, $2, $4, $6); }
 664  | '(' cnum ',' '*' ')'                 { $$ = f_new_pair_item($2, $2, 0, CC_ALL); }
 665  | '(' cnum DDOT cnum ',' cnum ')'      { $$ = f_new_pair_set($2, $4, $6, $6); }
 666  | '(' cnum DDOT cnum ',' cnum DDOT cnum ')' { $$ = f_new_pair_set($2, $4, $6, $8); }
 667  | '(' cnum DDOT cnum ',' '*' ')'       { $$ = f_new_pair_item($2, $4, 0, CC_ALL); }
 668  | '(' '*' ',' cnum ')'                 { $$ = f_new_pair_set(0, CC_ALL, $4, $4); }
 669  | '(' '*' ',' cnum DDOT cnum ')'       { $$ = f_new_pair_set(0, CC_ALL, $4, $6); }
 670  | '(' '*' ',' '*' ')'                  { $$ = f_new_pair_item(0, CC_ALL, 0, CC_ALL); }
 671  | '(' cnum ',' cnum ')' DDOT '(' cnum ',' cnum ')'
 672    { $$ = f_new_pair_item($2, $8, $4, $10); }
 673  ;
 674
 675 ec_kind:
 676    RT { $$ = EC_RT; }
 677  | RO { $$ = EC_RO; }
 678  | UNKNOWN NUM { $$ = $2; }
 679  | GENERIC { $$ = EC_GENERIC; }
 680  ;
 681
 682 ec_item:
 683    '(' ec_kind ',' cnum ',' cnum ')'            { $$ = f_new_ec_item($2, 0, $4, $6, $6); }
 684  | '(' ec_kind ',' cnum ',' cnum DDOT cnum ')'  { $$ = f_new_ec_item($2, 0, $4, $6, $8); }
 685  | '(' ec_kind ',' cnum ',' '*' ')'             { $$ = f_new_ec_item($2, 0, $4, 0, EC_ALL); }
 686  ;
 687
 688 lc_item:
 689    '(' cnum ',' cnum ',' cnum ')'           { $$ = f_new_lc_item($2, $2, $4, $4, $6, $6); }
 690  | '(' cnum ',' cnum ',' cnum DDOT cnum ')' { $$ = f_new_lc_item($2, $2, $4, $4, $6, $8); }
 691  | '(' cnum ',' cnum ',' '*' ')'            { $$ = f_new_lc_item($2, $2, $4, $4, 0, LC_ALL); }
 692  | '(' cnum ',' cnum DDOT cnum ',' '*' ')'  { $$ = f_new_lc_item($2, $2, $4, $6, 0, LC_ALL); }
 693  | '(' cnum ',' '*' ',' '*' ')'             { $$ = f_new_lc_item($2, $2, 0, LC_ALL, 0, LC_ALL); }
 694  | '(' cnum DDOT cnum ',' '*' ',' '*' ')'   { $$ = f_new_lc_item($2, $4, 0, LC_ALL, 0, LC_ALL); }
 695  | '(' '*' ',' '*' ',' '*' ')'              { $$ = f_new_lc_item(0, LC_ALL, 0, LC_ALL, 0, LC_ALL); }
 696  | '(' cnum ',' cnum ',' cnum ')' DDOT '(' cnum ',' cnum ',' cnum ')'
 697    { $$ = f_new_lc_item($2, $10, $4, $12, $6, $14); }
 698 ;
 699
 700 set_item:
 701    pair_item
 702  | ec_item
 703  | lc_item
 704  | set_atom { $$ = f_new_item($1, $1); }
 705  | set_atom DDOT set_atom { $$ = f_new_item($1, $3); }
 706  ;
 707
 708 switch_item:
 709    pair_item
 710  | ec_item
 711  | lc_item
 712  | switch_atom { $$ = f_new_item($1, $1); }
 713  | switch_atom DDOT switch_atom { $$ = f_new_item($1, $3); }
 714  ;
 715
 716 set_items:
 717    set_item
 718  | set_items ',' set_item { $$ = f_merge_items($1, $3); }
 719  ;
 720
 721 switch_items:
 722    switch_item
 723  | switch_items ',' switch_item { $$ = f_merge_items($1, $3); }
 724  ;
 725
 726 fprefix:
 727    net_ip_      { $$.net = $1; $$.lo = $1.pxlen; $$.hi = $1.pxlen; }
 728  | net_ip_ '+'  { $$.net = $1; $$.lo = $1.pxlen; $$.hi = net_max_prefix_length[$1.type]; }
 729  | net_ip_ '-'  { $$.net = $1; $$.lo = 0; $$.hi = $1.pxlen; }
 730  | net_ip_ '{' NUM ',' NUM '}' {
 731      $$.net = $1; $$.lo = $3; $$.hi = $5;
 732      if (($3 > $5) || ($5 > net_max_prefix_length[$1.type]))
 733        cf_error("Invalid prefix pattern range: {%u, %u}", $3, $5);
 734    }
 735  ;
 736
 737 fprefix_set:
 738    fprefix { $$ = f_new_trie(cfg_mem, 0); trie_add_prefix($$, &($1.net), $1.lo, $1.hi); }
 739  | fprefix_set ',' fprefix { $$ = $1; if (!trie_add_prefix($$, &($3.net), $3.lo, $3.hi)) cf_error("Mixed IPv4/IPv6 prefixes in prefix set"); }
 740  ;
 741
 742 switch_body: /* EMPTY */ { $$ = NULL; }
 743  | switch_body switch_items ':' cmds_scoped  {
 744      /* Fill data fields */
 745      struct f_tree *t;
 746      for (t = $2; t; t = t->left)
 747        t->data = $4;
 748      $$ = f_merge_items($1, $2);
 749    }
 750  | switch_body ELSECOL cmds_scoped {
 751      struct f_tree *t = f_new_tree();
 752      t->from.type = t->to.type = T_VOID;
 753      t->right = t;
 754      t->data = $3;
 755      $$ = f_merge_items($1, t);
 756  }
 757  ;
 758
 759 bgp_path_expr:
 760    symbol_value { $$ = $1; }
 761  | '(' term ')' { $$ = $2; }
 762  ;
 763
 764 bgp_path:
 765    PO  bgp_path_tail PC  { $$ = $2; }
 766  ;
 767
 768 bgp_path_tail:
 769    NUM bgp_path_tail            { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .asn = $1, .kind = PM_ASN, }, }); $$->next = $2;  }
 770  | NUM DDOT NUM bgp_path_tail   { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .from = $1, .to = $3, .kind = PM_ASN_RANGE }, }); $$->next = $4; }
 771  | '[' ']' bgp_path_tail { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .set = NULL, .kind = PM_ASN_SET }, }); $$->next = $3; }
 772  | '[' set_items ']' bgp_path_tail {
 773    if ($2->from.type != T_INT) cf_error("Only integer sets allowed in path mask");
 774    $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .set = build_tree($2), .kind = PM_ASN_SET }, }); $$->next = $4;
 775  }
 776  | '*' bgp_path_tail            { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .kind = PM_ASTERISK }, }); $$->next = $2; }
 777  | '?' bgp_path_tail            { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .kind = PM_QUESTION }, }); $$->next = $2; }
 778  | '+' bgp_path_tail            { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .kind = PM_LOOP }, }); $$->next = $2; }
 779  | bgp_path_expr bgp_path_tail  { $$ = $1; $$->next = $2; }
 780  |                              { $$ = NULL; }
 781  ;
 782
 783 constant:
 784    NUM      { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_INT, .val.i = $1, }); }
 785  | TRUE     { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_BOOL, .val.i = 1, }); }
 786  | FALSE    { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_BOOL, .val.i = 0, }); }
 787  | TEXT     { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_STRING, .val.s = $1, }); }
 788  | BYTETEXT { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_BYTESTRING, .val.bs = $1, }); }
 789  | fipa     { $$ = f_new_inst(FI_CONSTANT, $1); }
 790  | VPN_RD   { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_RD, .val.ec = $1, }); }
 791  | net_     { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_NET, .val.net = $1, }); }
 792  | '[' ']' { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_SET, .val.t = NULL, }); }
 793  | '[' set_items ']' {
 794      DBG( "We've got a set here..." );
 795      $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_SET, .val.t = build_tree($2), });
 796      DBG( "ook\n" );
 797  }
 798  | '[' fprefix_set ']' { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PREFIX_SET, .val.ti = $2, }); }
 799  | ENUM   { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = $1 >> 16, .val.i = $1 & 0xffff, }); }
 800  ;
 801
 802 constructor:
 803    '(' term ',' term ')' { $$ = f_new_inst(FI_PAIR_CONSTRUCT, $2, $4); }
 804  | '(' ec_kind ',' term ',' term ')' { $$ = f_new_inst(FI_EC_CONSTRUCT, $4, $6, $2); }
 805  | '(' term ',' term ',' term ')' { $$ = f_new_inst(FI_LC_CONSTRUCT, $2, $4, $6); }
 806  | bgp_path { $$ = f_new_inst(FI_PATHMASK_CONSTRUCT, $1); }
 807  ;
 808
 809
 810 /* This generates the function_call variable list backwards */
 811 var_list_r:
 812    /* EMPTY */ { $$ = NULL; }
 813  | term { $$ = $1; }
 814  | var_list_r ',' term { $$ = $3; $$->next = $1; }
 815  ;
 816
 817 var_list: var_list_r
 818    {
 819      $$ = NULL;
 820
 821      /* Revert the var_list_r */
 822      while ($1) {
 823        struct f_inst *tmp = $1;
 824        $1 = $1->next;
 825
 826        tmp->next = $$;
 827        $$ = tmp;
 828      }
 829    }
 830  ;
 831
 832 function_call:
 833    symbol_known '(' var_list ')'
 834    {
 835      if ($1->class != SYM_FUNCTION)
 836        cf_error("You can't call something which is not a function. Really.");
 837
 838      $$ = f_new_inst(FI_CALL, $3, $1);
 839    }
 840  ;
 841
 842 symbol_value: symbol_known
 843   {
 844     switch ($1->class) {
 845       case SYM_CONSTANT_RANGE:
 846         $$ = f_new_inst(FI_CONSTANT, *($1->val));
 847         break;
 848       case SYM_VARIABLE_RANGE:
 849         $$ = f_new_inst(FI_VAR_GET, $1);
 850         break;
 851       case SYM_ATTRIBUTE:
 852         $$ = f_new_inst(FI_EA_GET, *$1->attribute);
 853         break;
 854       default:
 855         cf_error("Can't get value of symbol %s", $1->name);
 856     }
 857   }
 858  ;
 859
 860 static_attr:
 861    FROM    { $$ = f_new_static_attr(T_IP,         SA_FROM,      0); }
 862  | GW      { $$ = f_new_static_attr(T_IP,         SA_GW,        0); }
 863  | NET     { $$ = f_new_static_attr(T_NET,        SA_NET,       1); }
 864  | PROTO   { $$ = f_new_static_attr(T_STRING,     SA_PROTO,     1); }
 865  | SOURCE  { $$ = f_new_static_attr(T_ENUM_RTS,   SA_SOURCE,    1); }
 866  | SCOPE   { $$ = f_new_static_attr(T_ENUM_SCOPE, SA_SCOPE,     0); }
 867  | DEST    { $$ = f_new_static_attr(T_ENUM_RTD,   SA_DEST,      0); }
 868  | IFNAME  { $$ = f_new_static_attr(T_STRING,     SA_IFNAME,    0); }
 869  | IFINDEX { $$ = f_new_static_attr(T_INT,        SA_IFINDEX,   1); }
 870  | WEIGHT  { $$ = f_new_static_attr(T_INT,        SA_WEIGHT,    0); }
 871  | PREFERENCE { $$ = f_new_static_attr(T_INT,     SA_PREF,      0); }
 872  | GW_MPLS { $$ = f_new_static_attr(T_INT,        SA_GW_MPLS,   0); }
 873  | ONLINK  { $$ = f_new_static_attr(T_BOOL,       SA_ONLINK,    0); }
 874  ;
 875
 876 term_dot_method: term '.' { f_method_call_start($1); } method_name_cont { f_method_call_end(); $$ = $4; };
 877 method_name_cont:
 878    CF_SYM_METHOD_BARE {
 879      $$ = f_dispatch_method($1, FM.object, NULL, 1);
 880    }
 881  | CF_SYM_METHOD_ARGS {
 882      f_method_call_args();
 883    } '(' var_list ')' {
 884      $$ = f_dispatch_method($1, FM.object, $4, 1);
 885    }
 886  ;
 887
 888 term:
 889    '(' term ')'         { $$ = $2; }
 890  | term '+' term        { $$ = f_new_inst(FI_ADD, $1, $3); }
 891  | term '-' term        { $$ = f_new_inst(FI_SUBTRACT, $1, $3); }
 892  | term '*' term        { $$ = f_new_inst(FI_MULTIPLY, $1, $3); }
 893  | term '/' term        { $$ = f_new_inst(FI_DIVIDE, $1, $3); }
 894  | term AND term        { $$ = f_new_inst(FI_AND, $1, $3); }
 895  | term OR  term        { $$ = f_new_inst(FI_OR, $1, $3); }
 896  | term '=' term        { $$ = f_new_inst(FI_EQ, $1, $3); }
 897  | term NEQ term        { $$ = f_new_inst(FI_NEQ, $1, $3); }
 898  | term '<' term        { $$ = f_new_inst(FI_LT, $1, $3); }
 899  | term LEQ term        { $$ = f_new_inst(FI_LTE, $1, $3); }
 900  | term '>' term        { $$ = f_new_inst(FI_LT, $3, $1); }
 901  | term GEQ term        { $$ = f_new_inst(FI_LTE, $3, $1); }
 902  | term '~' term        { $$ = f_new_inst(FI_MATCH, $1, $3); }
 903  | term NMA term        { $$ = f_new_inst(FI_NOT_MATCH, $1, $3); }
 904  | '!' term             { $$ = f_new_inst(FI_NOT, $2); }
 905  | DEFINED '(' term ')' { $$ = f_new_inst(FI_DEFINED, $3); }
 906
 907  | symbol_value   { $$ = $1; }
 908  | constant { $$ = $1; }
 909  | constructor { $$ = $1; }
 910
 911  | static_attr { $$ = f_new_inst(FI_RTA_GET, $1); }
 912
 913  | dynamic_attr { $$ = f_new_inst(FI_EA_GET, $1); }
 914
 915  | term_dot_method
 916
 917  | '+' EMPTY '+' { $$ = f_const_empty(T_PATH); }
 918  | '-' EMPTY '-' { $$ = f_const_empty(T_CLIST); }
 919  | '-' '-' EMPTY '-' '-' { $$ = f_const_empty(T_ECLIST); }
 920  | '-' '-' '-' EMPTY '-' '-' '-' { $$ = f_const_empty(T_LCLIST); }
 921  | PREPEND '(' term ',' term ')' { $$ = f_dispatch_method_x("prepend", $3->type, $3, $5); }
 922  | ADD '(' term ',' term ')' { $$ = f_dispatch_method_x("add", $3->type, $3, $5); }
 923  | DELETE '(' term ',' term ')' { $$ = f_dispatch_method_x("delete", $3->type, $3, $5); }
 924  | FILTER '(' term ',' term ')' { $$ = f_dispatch_method_x("filter", $3->type, $3, $5); }
 925
 926  | ROA_CHECK '(' rtable ')' { $$ = f_new_inst(FI_ROA_CHECK_IMPLICIT, $3); }
 927  | ROA_CHECK '(' rtable ',' term ',' term ')' { $$ = f_new_inst(FI_ROA_CHECK_EXPLICIT, $5, $7, $3); }
 928
 929  | FORMAT '(' term ')' {  $$ = f_new_inst(FI_FORMAT, $3); }
 930
 931  | term_bs
 932  | function_call
 933  ;
 934
 935 term_bs:
 936    FROM_HEX '(' term ')' { $$ = f_new_inst(FI_FROM_HEX, $3); }
 937  ;
 938
 939 break_command:
 940    ACCEPT { $$ = F_ACCEPT; }
 941  | REJECT { $$ = F_REJECT; }
 942  | ERROR { $$ = F_ERROR; }
 943  ;
 944
 945 var:
 946    type symbol '=' term ';' {
 947      struct symbol *sym = cf_define_symbol(new_config, $2, SYM_VARIABLE | $1, offset, f_new_var(sym_->scope));
 948      $$ = f_new_inst(FI_VAR_INIT, $4, sym);
 949    }
 950  | type symbol ';' {
 951      struct symbol *sym = cf_define_symbol(new_config, $2, SYM_VARIABLE | $1, offset, f_new_var(sym_->scope));
 952      $$ = f_new_inst(FI_VAR_INIT0, sym);
 953    }
 954  ;
 955
 956 for_var:
 957    type symbol { $$ = cf_define_symbol(new_config, $2, SYM_VARIABLE | $1, offset, f_new_var(sym_->scope)); }
 958  | CF_SYM_KNOWN { $$ = $1; cf_assert_symbol($1, SYM_VARIABLE); }
 959  ;
 960
 961 cmd:
 962    '{' cmds_scoped '}' {
 963      $$ = $2;
 964    }
 965  | IF term THEN cmd {
 966      $$ = f_new_inst(FI_CONDITION, $2, $4, NULL);
 967    }
 968  | IF term THEN cmd ELSE cmd {
 969      $$ = f_new_inst(FI_CONDITION, $2, $4, $6);
 970    }
 971  | FOR {
 972      /* Reserve space for walk data on stack */
 973      cf_push_block_scope(new_config);
 974      new_config->current_scope->slots += 2;
 975    } for_var IN
 976    /* Parse term in the parent scope */
 977    { new_config->current_scope->active = 0; } term { new_config->current_scope->active = 1; }
 978    DO cmd {
 979      cf_pop_block_scope(new_config);
 980      $$ = f_for_cycle($3, $6, $9);
 981    }
 982  | symbol_known '=' term ';' {
 983      switch ($1->class) {
 984        case SYM_VARIABLE_RANGE:
 985          $$ = f_new_inst(FI_VAR_SET, $3, $1);
 986          break;
 987        case SYM_ATTRIBUTE:
 988          $$ = f_new_inst(FI_EA_SET, $3, *$1->attribute);
 989          break;
 990        default:
 991          cf_error("Can't assign to symbol %s", $1->name);
 992      }
 993    }
 994  | RETURN term ';' {
 995      DBG( "Ook, we'll return the value\n" );
 996      if (!this_function)
 997        cf_error("Can't return from a non-function, use accept or reject instead.");
 998      if (this_function->function->return_type == T_VOID)
 999      {
1000        if ($2->type != T_VOID)
1001          cf_warn("Inferring function %s return type from its return value: %s", this_function->name, f_type_name($2->type));
1002        ((struct f_line *) this_function->function)->return_type = $2->type;
1003      }
1004      else if (this_function->function->return_type != $2->type)
1005        cf_error("Can't return type %s from function %s, expected %s",
1006                 f_type_name($2->type), this_function->name, f_type_name(this_function->function->return_type));
1007
1008      $$ = f_new_inst(FI_RETURN, $2);
1009    }
1010  | dynamic_attr '=' term ';' {
1011      $$ = f_new_inst(FI_EA_SET, $3, $1);
1012    }
1013  | static_attr '=' term ';' {
1014      if ($1.readonly)
1015        cf_error( "This static attribute is read-only.");
1016      $$ = f_new_inst(FI_RTA_SET, $3, $1);
1017    }
1018  | UNSET '(' dynamic_attr ')' ';' {
1019      $$ = f_new_inst(FI_EA_UNSET, $3);
1020    }
1021  | break_command var_list_r ';' {
1022     $$ = f_print($2, !!$2, $1);
1023    }
1024  | PRINT var_list_r ';' {
1025     $$ = f_print($2, 1, F_NOP);
1026    }
1027  | PRINTN var_list_r ';' {
1028     $$ = f_print($2, 0, F_NOP);
1029    }
1030  | function_call ';' { $$ = f_new_inst(FI_DROP_RESULT, $1); }
1031  | CASE term '{' switch_body '}' {
1032       $$ = f_new_inst(FI_SWITCH, $2, $4);
1033    }
1034  | lvalue '.' {
1035      f_method_call_start(f_lval_getter(&$1));
1036    } method_name_cont ';' {
1037      f_method_call_end();
1038      $$ = f_lval_setter(&$1, $4);
1039    }
1040  | BT_ASSERT '(' get_cf_position term get_cf_position ')' ';' { $$ = assert_done($4, $3 + 1, $5 - 1); }
1041  | BT_CHECK_ASSIGN '(' get_cf_position lvalue get_cf_position ',' term ')' ';' { $$ = assert_assign(&$4, $7, $3 + 1, $5 - 1); }
1042  ;
1043
1044 get_cf_position:
1045 {
1046   $$ = cf_text;
1047 };
1048
1049 lvalue:
1050    CF_SYM_KNOWN {
1051      switch ($1->class)
1052      {
1053        case SYM_VARIABLE_RANGE:
1054          $$ = (struct f_lval) { .type = F_LVAL_VARIABLE, .sym = $1 };
1055          break;
1056        case SYM_ATTRIBUTE:
1057          $$ = (struct f_lval) { .type = F_LVAL_EA, .da = *($1->attribute) };
1058          break;
1059        default:
1060          cf_error("Variable name or custom attribute name required");
1061      }
1062    }
1063  | static_attr { $$ = (struct f_lval) { .type = F_LVAL_SA, .sa = $1 }; }
1064  | dynamic_attr { $$ = (struct f_lval) { .type = F_LVAL_EA, .da = $1 }; };
1065
1066 CF_END