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