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