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