filter/config.Y

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