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