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