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