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 /*
  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_VAR_SET, expr, lval->sym);
 402       getter = f_new_inst(FI_VAR_GET, 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   setter->next = 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, BT_TEST_SAME, FORMAT)
 445
 446 %nonassoc THEN
 447 %nonassoc ELSE
 448
 449 %type <xp> cmds_int
 450 %type <x> term block cmd cmds constant constructor print_one print_list var_list function_call symbol_value bgp_path_expr bgp_path bgp_path_tail
 451 %type <fda> dynamic_attr
 452 %type <fsa> static_attr
 453 %type <f> filter where_filter
 454 %type <fl> filter_body function_body
 455 %type <flv> lvalue
 456 %type <i> type function_params declsn decls
 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, filter, NULL); cf_push_scope( $2 ); }
 471      filter_body {
 472      struct filter *f = cfg_alloc(sizeof(struct filter));
 473      *f = (struct filter) { .sym = $2, .root = $4 };
 474      $2->filter = f;
 475
 476      cf_pop_scope();
 477    }
 478  ;
 479
 480 conf: filter_eval ;
 481 filter_eval:
 482    EVAL term { f_eval_int(f_linearize($2)); }
 483  ;
 484
 485 conf: custom_attr ;
 486 custom_attr: ATTRIBUTE type CF_SYM_VOID ';' {
 487   cf_define_symbol($3, SYM_ATTRIBUTE, attribute, ca_lookup(new_config->pool, $3->name, $2)->fda);
 488 };
 489
 490 conf: bt_test_suite ;
 491 bt_test_suite:
 492  BT_TEST_SUITE '(' CF_SYM_KNOWN ',' text ')' {
 493   cf_assert_symbol($3, SYM_FUNCTION);
 494   struct f_bt_test_suite *t = cfg_allocz(sizeof(struct f_bt_test_suite));
 495   t->fn = $3->function;
 496   t->fn_name = $3->name;
 497   t->dsc = $5;
 498
 499   add_tail(&new_config->tests, &t->n);
 500  }
 501  ;
 502
 503 conf: bt_test_same ;
 504 bt_test_same:
 505  BT_TEST_SAME '(' CF_SYM_KNOWN ',' CF_SYM_KNOWN ',' NUM ')' {
 506   cf_assert_symbol($3, SYM_FUNCTION);
 507   cf_assert_symbol($5, SYM_FUNCTION);
 508   struct f_bt_test_suite *t = cfg_allocz(sizeof(struct f_bt_test_suite));
 509   t->fn = $3->function;
 510   t->cmp = $5->function;
 511   t->result = $7;
 512   t->fn_name = $3->name;
 513   t->dsc = $5->name;
 514   add_tail(&new_config->tests, &t->n);
 515  }
 516  ;
 517
 518 type:
 519    INT { $$ = T_INT; }
 520  | BOOL { $$ = T_BOOL; }
 521  | IP { $$ = T_IP; }
 522  | RD { $$ = T_RD; }
 523  | PREFIX { $$ = T_NET; }
 524  | PAIR { $$ = T_PAIR; }
 525  | QUAD { $$ = T_QUAD; }
 526  | EC { $$ = T_EC; }
 527  | LC { $$ = T_LC; }
 528  | STRING { $$ = T_STRING; }
 529  | BGPMASK { $$ = T_PATH_MASK; }
 530  | BGPPATH { $$ = T_PATH; }
 531  | CLIST { $$ = T_CLIST; }
 532  | ECLIST { $$ = T_ECLIST; }
 533  | LCLIST { $$ = T_LCLIST; }
 534  | type SET {
 535         switch ($1) {
 536           case T_INT:
 537           case T_PAIR:
 538           case T_QUAD:
 539           case T_EC:
 540           case T_LC:
 541           case T_RD:
 542           case T_IP:
 543                $$ = T_SET;
 544                break;
 545
 546           case T_NET:
 547                $$ = T_PREFIX_SET;
 548             break;
 549
 550           default:
 551                 cf_error( "You can't create sets of this type." );
 552         }
 553    }
 554  ;
 555
 556 /* Declarations with ';' at the end */
 557 decls:
 558    /* EMPTY */ { $$ = 0; }
 559  | declsn ';' { $$ = $1; }
 560  ;
 561
 562 /* Declarations that have no ';' at the end. */
 563 declsn:
 564    type CF_SYM_VOID {
 565      cf_define_symbol($2, SYM_VARIABLE | $1, offset, $2->scope->slots++);
 566      $$ = $2->scope->slots;
 567    }
 568  | declsn ';' type CF_SYM_VOID {
 569      if ($4->scope->slots >= 0xff) cf_error("Too many declarations, at most 255 allowed");
 570      cf_define_symbol($4, SYM_VARIABLE | $3, offset, $4->scope->slots++);
 571      $$ = $4->scope->slots;
 572    }
 573  ;
 574
 575 filter_body: function_body ;
 576
 577 filter:
 578    CF_SYM_KNOWN {
 579      cf_assert_symbol($1, SYM_FILTER);
 580      $$ = $1->filter;
 581    }
 582  | filter_body {
 583      struct filter *f = cfg_alloc(sizeof(struct filter));
 584      *f = (struct filter) { .root = $1 };
 585      $$ = f;
 586    }
 587  ;
 588
 589 where_filter:
 590    WHERE term {
 591      /* Construct 'IF term THEN { ACCEPT; } ELSE { REJECT; }' */
 592      $$ = f_new_where($2);
 593    }
 594  ;
 595
 596 function_params:
 597    '(' declsn ')' { $$ = $2; }
 598  | '(' ')' { $$ = 0; }
 599  ;
 600
 601 function_body:
 602    decls '{' cmds '}' {
 603      $$ = f_linearize($3);
 604      $$->vars = $1;
 605    }
 606  ;
 607
 608 conf: function_def ;
 609 function_def:
 610    FUNCTION CF_SYM_VOID { DBG( "Beginning of function %s\n", $2->name );
 611      $2 = cf_define_symbol($2, SYM_FUNCTION, function, NULL);
 612      cf_push_scope($2);
 613    } function_params function_body {
 614      $5->vars -= $4;
 615      $5->args = $4;
 616      $2->function = $5;
 617      cf_pop_scope();
 618    }
 619  ;
 620
 621 /* Programs */
 622
 623 cmds: /* EMPTY */ { $$ = NULL; }
 624  | cmds_int { $$ = $1[0]; }
 625  ;
 626
 627 cmds_int: cmd { $$[0] = $$[1] = $1; }
 628  | cmds_int cmd { $$[1] = $2; $1[1]->next = $2; $$[0] = $1[0]; }
 629  ;
 630
 631 block:
 632    cmd {
 633      $$=$1;
 634    }
 635  | '{' cmds '}' {
 636      $$=$2;
 637    }
 638  ;
 639
 640 /*
 641  * Complex types, their bison value is struct f_val
 642  */
 643 fipa:
 644    IP4 %prec PREFIX_DUMMY { $$.type = T_IP; $$.val.ip = ipa_from_ip4($1); }
 645  | IP6 %prec PREFIX_DUMMY { $$.type = T_IP; $$.val.ip = ipa_from_ip6($1); }
 646  ;
 647
 648
 649
 650 /*
 651  * Set constants. They are also used in switch cases. We use separate
 652  * nonterminals for switch (set_atom/switch_atom, set_item/switch_item ...)
 653  * to elude a collision between symbol (in expr) in set_atom and symbol
 654  * as a function call in switch case cmds.
 655  */
 656
 657 set_atom:
 658    NUM    { $$.type = T_INT; $$.val.i = $1; }
 659  | fipa   { $$ = $1; }
 660  | VPN_RD { $$.type = T_RD; $$.val.ec = $1; }
 661  | ENUM   { $$.type = pair_a($1); $$.val.i = pair_b($1); }
 662  | '(' term ')' {
 663      if (f_eval(f_linearize($2), cfg_mem, &($$)) > F_RETURN) cf_error("Runtime error");
 664      if (!f_valid_set_type($$.type)) cf_error("Set-incompatible type");
 665    }
 666  | CF_SYM_KNOWN {
 667      cf_assert_symbol($1, SYM_CONSTANT);
 668      if (!f_valid_set_type(SYM_TYPE($1))) cf_error("%s: set-incompatible type", $1->name);
 669      $$ = *$1->val;
 670    }
 671  ;
 672
 673 switch_atom:
 674    NUM   { $$.type = T_INT; $$.val.i = $1; }
 675  | '(' term ')' { $$.type = T_INT; $$.val.i = f_eval_int(f_linearize($2)); }
 676  | fipa  { $$ = $1; }
 677  | ENUM  { $$.type = pair_a($1); $$.val.i = pair_b($1); }
 678  ;
 679
 680 cnum:
 681    term { $$ = f_eval_int(f_linearize($1)); }
 682
 683 pair_item:
 684    '(' cnum ',' cnum ')'                { $$ = f_new_pair_item($2, $2, $4, $4); }
 685  | '(' cnum ',' cnum DDOT cnum ')'      { $$ = f_new_pair_item($2, $2, $4, $6); }
 686  | '(' cnum ',' '*' ')'                 { $$ = f_new_pair_item($2, $2, 0, CC_ALL); }
 687  | '(' cnum DDOT cnum ',' cnum ')'      { $$ = f_new_pair_set($2, $4, $6, $6); }
 688  | '(' cnum DDOT cnum ',' cnum DDOT cnum ')' { $$ = f_new_pair_set($2, $4, $6, $8); }
 689  | '(' cnum DDOT cnum ',' '*' ')'       { $$ = f_new_pair_item($2, $4, 0, CC_ALL); }
 690  | '(' '*' ',' cnum ')'                 { $$ = f_new_pair_set(0, CC_ALL, $4, $4); }
 691  | '(' '*' ',' cnum DDOT cnum ')'       { $$ = f_new_pair_set(0, CC_ALL, $4, $6); }
 692  | '(' '*' ',' '*' ')'                  { $$ = f_new_pair_item(0, CC_ALL, 0, CC_ALL); }
 693  | '(' cnum ',' cnum ')' DDOT '(' cnum ',' cnum ')'
 694    { $$ = f_new_pair_item($2, $8, $4, $10); }
 695  ;
 696
 697 ec_kind:
 698    RT { $$ = EC_RT; }
 699  | RO { $$ = EC_RO; }
 700  | UNKNOWN NUM { $$ = $2; }
 701  | GENERIC { $$ = EC_GENERIC; }
 702  ;
 703
 704 ec_item:
 705    '(' ec_kind ',' cnum ',' cnum ')'            { $$ = f_new_ec_item($2, 0, $4, $6, $6); }
 706  | '(' ec_kind ',' cnum ',' cnum DDOT cnum ')'  { $$ = f_new_ec_item($2, 0, $4, $6, $8); }
 707  | '(' ec_kind ',' cnum ',' '*' ')'             { $$ = f_new_ec_item($2, 0, $4, 0, EC_ALL); }
 708  ;
 709
 710 lc_item:
 711    '(' cnum ',' cnum ',' cnum ')'           { $$ = f_new_lc_item($2, $2, $4, $4, $6, $6); }
 712  | '(' cnum ',' cnum ',' cnum DDOT cnum ')' { $$ = f_new_lc_item($2, $2, $4, $4, $6, $8); }
 713  | '(' cnum ',' cnum ',' '*' ')'            { $$ = f_new_lc_item($2, $2, $4, $4, 0, LC_ALL); }
 714  | '(' cnum ',' cnum DDOT cnum ',' '*' ')'  { $$ = f_new_lc_item($2, $2, $4, $6, 0, LC_ALL); }
 715  | '(' cnum ',' '*' ',' '*' ')'             { $$ = f_new_lc_item($2, $2, 0, LC_ALL, 0, LC_ALL); }
 716  | '(' cnum DDOT cnum ',' '*' ',' '*' ')'   { $$ = f_new_lc_item($2, $4, 0, LC_ALL, 0, LC_ALL); }
 717  | '(' '*' ',' '*' ',' '*' ')'              { $$ = f_new_lc_item(0, LC_ALL, 0, LC_ALL, 0, LC_ALL); }
 718  | '(' cnum ',' cnum ',' cnum ')' DDOT '(' cnum ',' cnum ',' cnum ')'
 719    { $$ = f_new_lc_item($2, $10, $4, $12, $6, $14); }
 720 ;
 721
 722 set_item:
 723    pair_item
 724  | ec_item
 725  | lc_item
 726  | set_atom { $$ = f_new_item($1, $1); }
 727  | set_atom DDOT set_atom { $$ = f_new_item($1, $3); }
 728  ;
 729
 730 switch_item:
 731    pair_item
 732  | ec_item
 733  | lc_item
 734  | switch_atom { $$ = f_new_item($1, $1); }
 735  | switch_atom DDOT switch_atom { $$ = f_new_item($1, $3); }
 736  ;
 737
 738 set_items:
 739    set_item
 740  | set_items ',' set_item { $$ = f_merge_items($1, $3); }
 741  ;
 742
 743 switch_items:
 744    switch_item
 745  | switch_items ',' switch_item { $$ = f_merge_items($1, $3); }
 746  ;
 747
 748 fprefix:
 749    net_ip_      { $$.net = $1; $$.lo = $1.pxlen; $$.hi = $1.pxlen; }
 750  | net_ip_ '+'  { $$.net = $1; $$.lo = $1.pxlen; $$.hi = net_max_prefix_length[$1.type]; }
 751  | net_ip_ '-'  { $$.net = $1; $$.lo = 0; $$.hi = $1.pxlen; }
 752  | net_ip_ '{' NUM ',' NUM '}' {
 753      $$.net = $1; $$.lo = $3; $$.hi = $5;
 754      if (($3 > $5) || ($5 > net_max_prefix_length[$1.type]))
 755        cf_error("Invalid prefix pattern range: {%u, %u}", $3, $5);
 756    }
 757  ;
 758
 759 fprefix_set:
 760    fprefix { $$ = f_new_trie(cfg_mem, sizeof(struct f_trie_node)); trie_add_prefix($$, &($1.net), $1.lo, $1.hi); }
 761  | fprefix_set ',' fprefix { $$ = $1; trie_add_prefix($$, &($3.net), $3.lo, $3.hi); }
 762  ;
 763
 764 switch_body: /* EMPTY */ { $$ = NULL; }
 765  | switch_body switch_items ':' cmds  {
 766      /* Fill data fields */
 767      struct f_tree *t;
 768      struct f_line *line = f_linearize($4);
 769      for (t = $2; t; t = t->left)
 770        t->data = line;
 771      $$ = f_merge_items($1, $2);
 772    }
 773  | switch_body ELSECOL cmds {
 774      struct f_tree *t = f_new_tree();
 775      t->from.type = t->to.type = T_VOID;
 776      t->right = t;
 777      t->data = f_linearize($3);
 778      $$ = f_merge_items($1, t);
 779  }
 780  ;
 781
 782 bgp_path_expr:
 783    symbol_value { $$ = $1; }
 784  | '(' term ')' { $$ = $2; }
 785  ;
 786
 787 bgp_path:
 788    PO  bgp_path_tail PC  { $$ = $2; }
 789  ;
 790
 791 bgp_path_tail:
 792    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;  }
 793  | 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; }
 794  | '*' bgp_path_tail            { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .kind = PM_ASTERISK }, }); $$->next = $2; }
 795  | '?' bgp_path_tail            { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .kind = PM_QUESTION }, }); $$->next = $2; }
 796  | bgp_path_expr bgp_path_tail  { $$ = $1; $$->next = $2; }
 797  |                              { $$ = NULL; }
 798  ;
 799
 800 constant:
 801    NUM    { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_INT, .val.i = $1, }); }
 802  | TRUE   { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_BOOL, .val.i = 1, }); }
 803  | FALSE  { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_BOOL, .val.i = 0, }); }
 804  | TEXT   { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_STRING, .val.s = $1, }); }
 805  | fipa   { $$ = f_new_inst(FI_CONSTANT, $1); }
 806  | VPN_RD { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_RD, .val.ec = $1, }); }
 807  | net_   { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_NET, .val.net = $1, }); }
 808  | '[' set_items ']' {
 809      DBG( "We've got a set here..." );
 810      $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_SET, .val.t = build_tree($2), });
 811      DBG( "ook\n" );
 812  }
 813  | '[' fprefix_set ']' { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PREFIX_SET, .val.ti = $2, }); }
 814  | ENUM   { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = $1 >> 16, .val.i = $1 & 0xffff, }); }
 815  ;
 816
 817 constructor:
 818    '(' term ',' term ')' { $$ = f_new_inst(FI_PAIR_CONSTRUCT, $2, $4); }
 819  | '(' ec_kind ',' term ',' term ')' { $$ = f_new_inst(FI_EC_CONSTRUCT, $4, $6, $2); }
 820  | '(' term ',' term ',' term ')' { $$ = f_new_inst(FI_LC_CONSTRUCT, $2, $4, $6); }
 821  | bgp_path { $$ = f_new_inst(FI_PATHMASK_CONSTRUCT, $1, 0); }
 822  ;
 823
 824
 825 /* This generates the function_call variable list backwards. */
 826 var_list: /* EMPTY */ { $$ = NULL; }
 827  | term { $$ = $1; }
 828  | var_list ',' term { $$ = $3; $$->next = $1; }
 829
 830 function_call:
 831    CF_SYM_KNOWN '(' var_list ')' {
 832      if ($1->class != SYM_FUNCTION)
 833        cf_error("You can't call something which is not a function. Really.");
 834
 835      struct f_inst *fc = f_new_inst(FI_CALL, $1);
 836      uint args = 0;
 837      while ($3) {
 838        args++;
 839        struct f_inst *tmp = $3->next;
 840        $3->next = fc;
 841
 842        fc = $3;
 843        $3 = tmp;
 844      }
 845
 846      if (args != $1->function->args)
 847        cf_error("Function call '%s' got %u arguments, need %u arguments.",
 848            $1->name, args, $1->function->args);
 849
 850      $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_VOID });
 851      $$->next = fc;
 852    }
 853  ;
 854
 855 symbol_value: CF_SYM_KNOWN
 856   {
 857     switch ($1->class) {
 858       case SYM_CONSTANT_RANGE:
 859         $$ = f_new_inst(FI_CONSTANT, *($1->val));
 860         break;
 861       case SYM_VARIABLE_RANGE:
 862         $$ = f_new_inst(FI_VAR_GET, $1);
 863         break;
 864       case SYM_ATTRIBUTE:
 865         $$ = f_new_inst(FI_EA_GET, *$1->attribute);
 866         break;
 867       default:
 868         cf_error("Can't get value of symbol %s", $1->name);
 869     }
 870   }
 871  ;
 872
 873 static_attr:
 874    FROM    { $$ = f_new_static_attr(T_IP,         SA_FROM,      0); }
 875  | GW      { $$ = f_new_static_attr(T_IP,         SA_GW,        0); }
 876  | NET     { $$ = f_new_static_attr(T_NET,        SA_NET,       1); }
 877  | PROTO   { $$ = f_new_static_attr(T_STRING,     SA_PROTO,     1); }
 878  | SOURCE  { $$ = f_new_static_attr(T_ENUM_RTS,   SA_SOURCE,    1); }
 879  | SCOPE   { $$ = f_new_static_attr(T_ENUM_SCOPE, SA_SCOPE,     0); }
 880  | DEST    { $$ = f_new_static_attr(T_ENUM_RTD,   SA_DEST,      0); }
 881  | IFNAME  { $$ = f_new_static_attr(T_STRING,     SA_IFNAME,    0); }
 882  | IFINDEX { $$ = f_new_static_attr(T_INT,        SA_IFINDEX,   1); }
 883  ;
 884
 885 term:
 886    '(' term ')'         { $$ = $2; }
 887  | term '+' term        { $$ = f_new_inst(FI_ADD, $1, $3); }
 888  | term '-' term        { $$ = f_new_inst(FI_SUBTRACT, $1, $3); }
 889  | term '*' term        { $$ = f_new_inst(FI_MULTIPLY, $1, $3); }
 890  | term '/' term        { $$ = f_new_inst(FI_DIVIDE, $1, $3); }
 891  | term AND term        { $$ = f_new_inst(FI_AND, $1, $3); }
 892  | term OR  term        { $$ = f_new_inst(FI_OR, $1, $3); }
 893  | term '=' term        { $$ = f_new_inst(FI_EQ, $1, $3); }
 894  | term NEQ term        { $$ = f_new_inst(FI_NEQ, $1, $3); }
 895  | term '<' term        { $$ = f_new_inst(FI_LT, $1, $3); }
 896  | term LEQ term        { $$ = f_new_inst(FI_LTE, $1, $3); }
 897  | term '>' term        { $$ = f_new_inst(FI_LT, $3, $1); }
 898  | term GEQ term        { $$ = f_new_inst(FI_LTE, $3, $1); }
 899  | term '~' term        { $$ = f_new_inst(FI_MATCH, $1, $3); }
 900  | term NMA term        { $$ = f_new_inst(FI_NOT_MATCH, $1, $3); }
 901  | '!' term             { $$ = f_new_inst(FI_NOT, $2); }
 902  | DEFINED '(' term ')' { $$ = f_new_inst(FI_DEFINED, $3); }
 903
 904  | symbol_value   { $$ = $1; }
 905  | constant { $$ = $1; }
 906  | constructor { $$ = $1; }
 907
 908  | PREFERENCE { $$ = f_new_inst(FI_PREF_GET); }
 909
 910  | static_attr { $$ = f_new_inst(FI_RTA_GET, $1); }
 911
 912  | dynamic_attr { $$ = f_new_inst(FI_EA_GET, $1); }
 913
 914  | term '.' IS_V4 { $$ = f_new_inst(FI_IS_V4, $1); }
 915  | term '.' TYPE { $$ = f_new_inst(FI_TYPE, $1); }
 916  | term '.' IP { $$ = f_new_inst(FI_IP, $1); }
 917  | term '.' RD { $$ = f_new_inst(FI_ROUTE_DISTINGUISHER, $1); }
 918  | term '.' LEN { $$ = f_new_inst(FI_LENGTH, $1); }
 919  | term '.' MAXLEN { $$ = f_new_inst(FI_ROA_MAXLEN, $1); }
 920  | term '.' ASN { $$ = f_new_inst(FI_ROA_ASN, $1); }
 921  | term '.' SRC { $$ = f_new_inst(FI_SADR_SRC, $1); }
 922  | term '.' MASK '(' term ')' { $$ = f_new_inst(FI_IP_MASK, $1, $5); }
 923  | term '.' FIRST { $$ = f_new_inst(FI_AS_PATH_FIRST, $1); }
 924  | term '.' LAST  { $$ = f_new_inst(FI_AS_PATH_LAST, $1); }
 925  | term '.' LAST_NONAGGREGATED  { $$ = f_new_inst(FI_AS_PATH_LAST_NAG, $1); }
 926
 927 /* Communities */
 928 /* This causes one shift/reduce conflict
 929  | dynamic_attr '.' ADD '(' term ')' { }
 930  | dynamic_attr '.' DELETE '(' term ')' { }
 931  | dynamic_attr '.' CONTAINS '(' term ')' { }
 932  | dynamic_attr '.' RESET{ }
 933 */
 934
 935  | '+' EMPTY '+' { $$ = f_new_inst(FI_CONSTANT, f_const_empty_path); }
 936  | '-' EMPTY '-' { $$ = f_new_inst(FI_CONSTANT, f_const_empty_clist); }
 937  | '-' '-' EMPTY '-' '-' { $$ = f_new_inst(FI_CONSTANT, f_const_empty_eclist); }
 938  | '-' '-' '-' EMPTY '-' '-' '-' { $$ = f_new_inst(FI_CONSTANT, f_const_empty_lclist); }
 939  | PREPEND '(' term ',' term ')' { $$ = f_new_inst(FI_PATH_PREPEND, $3, $5); }
 940  | ADD '(' term ',' term ')' { $$ = f_new_inst(FI_CLIST_ADD, $3, $5); }
 941  | DELETE '(' term ',' term ')' { $$ = f_new_inst(FI_CLIST_DEL, $3, $5); }
 942  | FILTER '(' term ',' term ')' { $$ = f_new_inst(FI_CLIST_FILTER, $3, $5); }
 943
 944  | ROA_CHECK '(' rtable ')' { $$ = f_new_inst(FI_ROA_CHECK_IMPLICIT, $3); }
 945  | ROA_CHECK '(' rtable ',' term ',' term ')' { $$ = f_new_inst(FI_ROA_CHECK_EXPLICIT, $5, $7, $3); }
 946
 947  | FORMAT '(' term ')' {  $$ = f_new_inst(FI_FORMAT, $3); }
 948
 949 /* | term '.' LEN { $$->code = P('P','l'); } */
 950
 951  | function_call
 952  ;
 953
 954 break_command:
 955    QUITBIRD { $$ = F_QUITBIRD; }
 956  | ACCEPT { $$ = F_ACCEPT; }
 957  | REJECT { $$ = F_REJECT; }
 958  | ERROR { $$ = F_ERROR; }
 959  | PRINT { $$ = F_NOP; }
 960  | PRINTN { $$ = F_NONL; }
 961  ;
 962
 963 print_one:
 964    term { $$ = f_new_inst(FI_PRINT, $1); }
 965  ;
 966
 967 print_list: /* EMPTY */ { $$ = NULL; }
 968  | print_one { $$ = $1; }
 969  | print_one ',' print_list {
 970      if ($1) {
 971        $1->next = $3;
 972        $$ = $1;
 973      } else $$ = $3;
 974    }
 975  ;
 976
 977 cmd:
 978    IF term THEN block {
 979      $$ = f_new_inst(FI_CONDITION, $2, $4, NULL);
 980    }
 981  | IF term THEN block ELSE block {
 982      $$ = f_new_inst(FI_CONDITION, $2, $4, $6);
 983    }
 984  | CF_SYM_KNOWN '=' term ';' {
 985      switch ($1->class) {
 986        case SYM_VARIABLE_RANGE:
 987          $$ = f_new_inst(FI_VAR_SET, $3, $1);
 988          break;
 989        case SYM_ATTRIBUTE:
 990          $$ = f_new_inst(FI_EA_SET, $3, *$1->attribute);
 991          break;
 992        default:
 993          cf_error("Can't assign to symbol %s", $1->name);
 994      }
 995    }
 996  | RETURN term ';' {
 997      DBG( "Ook, we'll return the value\n" );
 998      $$ = f_new_inst(FI_RETURN, $2);
 999    }
1000  | dynamic_attr '=' term ';' {
1001      $$ = f_new_inst(FI_EA_SET, $3, $1);
1002    }
1003  | static_attr '=' term ';' {
1004      if ($1.readonly)
1005        cf_error( "This static attribute is read-only.");
1006      $$ = f_new_inst(FI_RTA_SET, $3, $1);
1007    }
1008  | PREFERENCE '=' term ';' {
1009      $$ = f_new_inst(FI_PREF_SET, $3);
1010    }
1011  | UNSET '(' dynamic_attr ')' ';' {
1012      $$ = f_new_inst(FI_EA_UNSET, $3);
1013    }
1014  | break_command print_list ';' { $$ = f_new_inst(FI_PRINT_AND_DIE, $2, $1); }
1015  | function_call ';' { $$ = f_new_inst(FI_DROP_RESULT, $1); }
1016  | CASE term '{' switch_body '}' {
1017       $$ = f_new_inst(FI_SWITCH, $2, build_tree($4));
1018    }
1019
1020  | dynamic_attr '.' EMPTY ';' { $$ = f_generate_empty($1); }
1021  | dynamic_attr '.' PREPEND '(' term ')' ';'   { $$ = f_generate_complex( FI_PATH_PREPEND, $1, $5 ); }
1022  | dynamic_attr '.' ADD '(' term ')' ';'       { $$ = f_generate_complex( FI_CLIST_ADD, $1, $5 ); }
1023  | dynamic_attr '.' DELETE '(' term ')' ';'    { $$ = f_generate_complex( FI_CLIST_DEL, $1, $5 ); }
1024  | dynamic_attr '.' FILTER '(' term ')' ';'    { $$ = f_generate_complex( FI_CLIST_FILTER, $1, $5 ); }
1025  | BT_ASSERT '(' get_cf_position term get_cf_position ')' ';' { $$ = assert_done($4, $3 + 1, $5 - 1); }
1026  | BT_CHECK_ASSIGN '(' get_cf_position lvalue get_cf_position ',' term ')' ';' { $$ = assert_assign(&$4, $7, $3 + 1, $5 - 1); }
1027  ;
1028
1029 get_cf_position:
1030 {
1031   $$ = cf_text;
1032 };
1033
1034 lvalue:
1035    CF_SYM_KNOWN { cf_assert_symbol($1, SYM_VARIABLE); $$ = (struct f_lval) { .type = F_LVAL_VARIABLE, .sym = $1 }; }
1036  | PREFERENCE { $$ = (struct f_lval) { .type = F_LVAL_PREFERENCE }; }
1037  | static_attr { $$ = (struct f_lval) { .type = F_LVAL_SA, .sa = $1 }; }
1038  | dynamic_attr { $$ = (struct f_lval) { .type = F_LVAL_EA, .da = $1 }; };
1039
1040 CF_END