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