Filter: Implement for loops

For loops allow to iterate over elements in compound data like BGP paths
or community lists. The syntax is:

  for [ <type> ] <variable> in <expr> do <command-body>

8 files changed, 254 insertions, 8 deletions

diff --git a/doc/bird.sgml b/doc/bird.sgml
index f933128c..89b1541c 100644
--- a/doc/bird.sgml
+++ b/doc/bird.sgml
@@ -1683,7 +1683,8 @@ prefix and an ASN as arguments.
 <sect>Control structures
 <label id="control-structures">
 
-<p>Filters support two control structures: conditions and case switches.
+<p>Filters support several control structures: conditions, for loops and case
+switches.
 
 <p>Syntax of a condition is: <cf>if <M>boolean expression</M> then <m/commandT/;
 else <m/commandF/;</cf> and you can use <cf>{ <m/command1/; <m/command2/;
@@ -1691,6 +1692,14 @@ else <m/commandF/;</cf> and you can use <cf>{ <m/command1/; <m/command2/;
 omitted. If the <cf><m>boolean expression</m></cf> is true, <m/commandT/ is
 executed, otherwise <m/commandF/ is executed.
 
+<p>For loops allow to iterate over elements in compound data like BGP paths or
+community lists. The syntax is: <cf>for [ <m/type/ ] <m/variable/ in <m/expr/
+do <m/command/;</cf> and you can also use compound command like in conditions.
+The expression is evaluated to a compound data, then for each element from such
+data the command is executed with the item assigned to the variable. A variable
+may be an existing one (when just name is used) or a locally defined (when type
+and name is used). In both cases, it must have the same type as elements.
+
 <p>The <cf>case</cf> is similar to case from Pascal. Syntax is <cf>case
 <m/expr/ { else: | <m/num_or_prefix [ .. num_or_prefix]/: <m/statement/ ; [
 ... ] }</cf>. The expression after <cf>case</cf> can be of any type which can be
@@ -1703,16 +1712,21 @@ neither of the <cf/:/ clauses, the statements after <cf/else:/ are executed.
 <p>Here is example that uses <cf/if/ and <cf/case/ structures:
 
 <code>
+if 1234 = i then printn "."; else {
+	print "not 1234";
+	print "You need {} around multiple commands";
+}
+
+for int asn in bgp_path do {
+	printn "ASN: ", asn;
+	if asn < 65536 then print " (2B)"; else print " (4B)";
+}
+
 case arg1 {
 	2: print "two"; print "I can do more commands without {}";
 	3 .. 5: print "three to five";
 	else: print "something else";
 }
-
-if 1234 = i then printn "."; else {
-  print "not 1234";
-  print "You need {} around multiple commands";
-}
 </code>
 
 
diff --git a/filter/config.Y b/filter/config.Y
index f8f47862..c7c82068 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -296,7 +296,7 @@ assert_assign(struct f_lval *lval, struct f_inst *expr, const char *start, const
 
   checker = f_new_inst(FI_EQ, expr, getter);
   setter->next = checker;
-  
+
   return assert_done(setter, start, end);
 }
 
@@ -307,6 +307,7 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN,
 	INT, BOOL, IP, TYPE, PREFIX, RD, PAIR, QUAD, EC, LC,
 	SET, STRING, BGPMASK, BGPPATH, CLIST, ECLIST, LCLIST,
 	IF, THEN, ELSE, CASE,
+	FOR, IN, DO,
 	TRUE, FALSE, RT, RO, UNKNOWN, GENERIC,
 	FROM, GW, NET, MASK, PROTO, SOURCE, SCOPE, DEST, IFNAME, IFINDEX, WEIGHT, GW_MPLS,
 	PREFERENCE,
@@ -342,6 +343,7 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN,
 %type <v> set_atom switch_atom fipa
 %type <px> fprefix
 %type <t> get_cf_position
+%type <s> for_var
 
 CF_GRAMMAR
 
@@ -899,6 +901,11 @@ var:
      $$ = f_new_inst(FI_VAR_INIT, $3, sym);
    }
 
+for_var:
+   type symbol { $$ = cf_define_symbol($2, SYM_VARIABLE | $1, offset, f_new_var(sym_->scope)); }
+ | CF_SYM_KNOWN { $$ = $1; cf_assert_symbol($1, SYM_VARIABLE); }
+ ;
+
 cmd:
    '{' cmds_scoped '}' {
      $$ = $2;
@@ -909,6 +916,18 @@ cmd:
  | IF term THEN cmd ELSE cmd {
      $$ = f_new_inst(FI_CONDITION, $2, $4, $6);
    }
+ | FOR {
+     /* Reserve space for walk data on stack */
+     cf_push_scope(NULL);
+     conf_this_scope->slots += 2;
+   } for_var IN
+   /* Parse term in the parent scope */
+   { conf_this_scope->active = 0; } term { conf_this_scope->active = 1; }
+   DO cmd {
+     cf_pop_scope();
+     $$ = f_new_inst(FI_FOR_INIT, $6, $3);
+     $$->next = f_new_inst(FI_FOR_NEXT, $3, $9);
+   }
  | CF_SYM_KNOWN '=' term ';' {
      switch ($1->class) {
        case SYM_VARIABLE_RANGE:
diff --git a/filter/data.c b/filter/data.c
index 2bb5920c..87c438fc 100644
--- a/filter/data.c
+++ b/filter/data.c
@@ -72,6 +72,7 @@ enum f_type
 f_type_element_type(enum f_type t)
 {
   switch(t) {
+    case T_PATH:   return T_INT;
     case T_CLIST:  return T_PAIR;
     case T_ECLIST: return T_EC;
     case T_LCLIST: return T_LC;
diff --git a/filter/f-inst.c b/filter/f-inst.c
index dc243b4e..30db96f2 100644
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -87,6 +87,11 @@
  *	m4_dnl	  RESULT_VOID;				return undef
  *	m4_dnl	}
  *
+ *	Note that runtime arguments m4_dnl (ARG*, VARARG) must be defined before
+ *	parse-time arguments m4_dnl (LINE, SYMBOL, ...). During linearization,
+ *	first ones move position in f_line by linearizing arguments first, while
+ *	second ones store data to the current position.
+ *
  *	Also note that the { ... } blocks are not respected by M4 at all.
  *	If you get weird unmatched-brace-pair errors, check what it generated and why.
  *	What is really considered as one instruction is not the { ... } block
@@ -543,6 +548,94 @@
     RESULT_VAL(val);
   }
 
+  INST(FI_FOR_INIT, 1, 0) {
+    NEVER_CONSTANT;
+    ARG_ANY(1);
+    SYMBOL;
+
+    FID_NEW_BODY()
+    ASSERT((sym->class & ~0xff) == SYM_VARIABLE);
+
+    /* Static type check */
+    if (f1->type)
+    {
+      enum f_type t_var = (sym->class & 0xff);
+      enum f_type t_arg = f_type_element_type(f1->type);
+      if (!t_arg)
+        cf_error("Value of expression in FOR must be iterable, got %s",
+		 f_type_name(f1->type));
+      if (t_var != t_arg)
+	cf_error("Loop variable '%s' in FOR must be %s, is %s",
+		 sym->name, f_type_name(t_arg), f_type_name(t_var));
+    }
+
+    FID_INTERPRET_BODY()
+
+    /* Dynamic type check */
+    if ((sym->class & 0xff) != f_type_element_type(v1.type))
+      runtime("Mismatched argument and variable type");
+
+    /* Setup the index */
+    v2 = (struct f_val) { .type = T_INT, .val.i = 0 };
+
+    /* Keep v1 and v2 on the stack */
+    fstk->vcnt += 2;
+  }
+
+  INST(FI_FOR_NEXT, 2, 0) {
+    NEVER_CONSTANT;
+    SYMBOL;
+
+    /* Type checks are done in FI_FOR_INIT */
+
+    /* Loop variable */
+    struct f_val *var = &fstk->vstk[curline.vbase + sym->offset];
+    int step = 0;
+
+    switch(v1.type)
+    {
+    case T_PATH:
+      var->type = T_INT;
+      step = as_path_walk(v1.val.ad, &v2.val.i, &var->val.i);
+      break;
+
+    case T_CLIST:
+      var->type = T_PAIR;
+      step = int_set_walk(v1.val.ad, &v2.val.i, &var->val.i);
+      break;
+
+    case T_ECLIST:
+      var->type = T_EC;
+      step = ec_set_walk(v1.val.ad, &v2.val.i, &var->val.ec);
+      break;
+
+    case T_LCLIST:
+      var->type = T_LC;
+      step = lc_set_walk(v1.val.ad, &v2.val.i, &var->val.lc);
+      break;
+
+    default:
+      runtime( "Clist or lclist expected" );
+    }
+
+    if (step)
+    {
+      /* Keep v1 and v2 on the stack */
+      fstk->vcnt += 2;
+
+      /* Repeat this instruction */
+      curline.pos--;
+
+      /* Execute the loop body */
+      LINE(1, 0);
+
+      /* Space for loop variable, may be unused */
+      fstk->vcnt += 1;
+    }
+    else
+      var->type = T_VOID;
+  }
+
   INST(FI_CONDITION, 1, 0) {
     ARG(1, T_BOOL);
     if (v1.val.i)
diff --git a/filter/test.conf b/filter/test.conf
index 436031a3..bc5f898e 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -758,6 +758,15 @@ int set set12;
 	bt_assert(delete(p2, [4..5]) = prepend(prepend(prepend(prepend(+empty+, 3), 3), 2), 1));
 
 	bt_assert(format([= 1 2+ 3 =]) = "[= 1 2 + 3 =]");
+
+	# iteration over path
+	int x = 0;
+	int y = 0;
+	for int i in p2 do {
+	    x = x + i;
+	    y = y + x;
+	}
+	bt_assert(x = 18 && y = 50);
 }
 
 bt_test_suite(t_path, "Testing paths");
@@ -884,6 +893,12 @@ clist r;
 	bt_assert(format(r) = "(clist (2,1) (1,3) (2,2) (3,1) (2,3))");
 	bt_assert(r.min = (1,3));
 	bt_assert(r.max = (3,1));
+
+	# iteration over clist
+	int x = 0;
+	for pair c in r do
+	    x = x + c.asn * c.asn * c.data;
+	bt_assert(x = 36);
 }
 
 bt_test_suite(t_clist, "Testing lists of communities");
@@ -999,6 +1014,13 @@ eclist r;
 	bt_assert(format(r) = "(eclist (rt, 2, 1) (rt, 1, 3) (rt, 2, 2) (rt, 3, 1) (rt, 2, 3))");
 	bt_assert(r.min = (rt, 1, 3));
 	bt_assert(r.max = (rt, 3, 1));
+
+	# iteration over eclist
+	int x = 0;
+	for ec c in r do
+	  if c > (rt, 2, 0) && c < (rt, 3, 0) then
+	    x = x + 1;
+	bt_assert(x = 3);
 }
 
 bt_test_suite(t_eclist, "Testing lists of extended communities");
@@ -1117,6 +1139,19 @@ lclist r;
 	bt_assert(format(r) = "(lclist (2, 3, 3) (1, 2, 3) (2, 3, 1) (3, 1, 2) (2, 1, 3))");
 	bt_assert(r.min = (1, 2, 3));
 	bt_assert(r.max = (3, 1, 2));
+
+	# iteration over lclist
+	int x = 0;
+	int y = 0;
+	lc mx = (0, 0, 0);
+	for lc c in r do {
+	    int asn2 = c.asn * c.asn;
+	    x = x + asn2 * c.data1;
+	    y = y + asn2 * c.data2;
+	    if c > mx then mx = c;
+	}
+	bt_assert(x = 39 && y = 49);
+	bt_assert(mx = r.max);
 }
 
 bt_test_suite(t_lclist, "Testing lists of large communities");
@@ -1580,13 +1615,16 @@ filter vpn_filter
 	bt_assert(net.type != NET_IP6);
 	bt_assert(net.rd = 0:1:2);
 
+	bool b = false;
 	case (net.type) {
 	  NET_IP4: print "IPV4";
 	  NET_IP6: print "IPV6";
+	  else: b = true;
 	}
+	bt_assert(b);
 
 	bt_check_assign(from, 10.20.30.40);
-	bt_check_assign(gw, 55.55.55.44);
+	# bt_check_assign(gw, 55.55.55.44);
 
 	bgp_community.add((3,5));
 	bgp_ext_community.add((ro, 135, 999));
diff --git a/nest/a-path.c b/nest/a-path.c
index d5b01635..6bb18285 100644
--- a/nest/a-path.c
+++ b/nest/a-path.c
@@ -669,6 +669,35 @@ as_path_filter(struct linpool *pool, const struct adata *path, const struct f_va
   return res;
 }
 
+int
+as_path_walk(const struct adata *path, uint *pos, uint *val)
+{
+  if (!path)
+    return 0;
+
+  const u8 *p = path->data;
+  const u8 *q = p + path->length;
+  uint n, x = *pos;
+
+  while (p < q)
+  {
+    n = p[1];
+    p += 2;
+
+    if (x < n)
+    {
+      *val = get_as(p + x * BS);
+      *pos += 1;
+      return 1;
+    }
+
+    p += n * BS;
+    x -= n;
+  }
+
+  return 0;
+}
+
 
 struct pm_pos
 {
diff --git a/nest/a-set.c b/nest/a-set.c
index 71fbac94..40ed573c 100644
--- a/nest/a-set.c
+++ b/nest/a-set.c
@@ -693,3 +693,51 @@ lc_set_max(const struct adata *list, lcomm *val)
   *val = (lcomm) { res[0], res[1], res[2] };
   return 1;
 }
+
+int
+int_set_walk(const struct adata *list, uint *pos, uint *val)
+{
+  if (!list)
+    return 0;
+
+  if (*pos >= (uint) int_set_get_size(list))
+    return 0;
+
+  u32 *res = int_set_get_data(list) + *pos;
+  *val = *res;
+  *pos += 1;
+
+  return 1;
+}
+
+int
+ec_set_walk(const struct adata *list, uint *pos, u64 *val)
+{
+  if (!list)
+    return 0;
+
+  if (*pos >= (uint) int_set_get_size(list))
+    return 0;
+
+  u32 *res = int_set_get_data(list) + *pos;
+  *val = ec_generic(res[0], res[1]);
+  *pos += 2;
+
+  return 1;
+}
+
+int
+lc_set_walk(const struct adata *list, uint *pos, lcomm *val)
+{
+  if (!list)
+    return 0;
+
+  if (*pos >= (uint) int_set_get_size(list))
+    return 0;
+
+  u32 *res = int_set_get_data(list) + *pos;
+  *val = (lcomm) { res[0], res[1], res[2] };
+  *pos += 3;
+
+  return 1;
+}
diff --git a/nest/attrs.h b/nest/attrs.h
index 22e2ff4a..9412439b 100644
--- a/nest/attrs.h
+++ b/nest/attrs.h
@@ -51,6 +51,7 @@ u32 as_path_get_last_nonaggregated(const struct adata *path);
 int as_path_contains(const struct adata *path, u32 as, int min);
 int as_path_match_set(const struct adata *path, const struct f_tree *set);
 const struct adata *as_path_filter(struct linpool *pool, const struct adata *path, const struct f_val *set, int pos);
+int as_path_walk(const struct adata *path, uint *pos, uint *val);
 
 static inline struct adata *as_path_prepend(struct linpool *pool, const struct adata *path, u32 as)
 { return as_path_prepend2(pool, path, AS_PATH_SEQUENCE, as); }
@@ -225,6 +226,9 @@ int lc_set_min(const struct adata *list, lcomm *val);
 int int_set_max(const struct adata *list, u32 *val);
 int ec_set_max(const struct adata *list, u64 *val);
 int lc_set_max(const struct adata *list, lcomm *val);
+int int_set_walk(const struct adata *list, uint *pos, u32 *val);
+int ec_set_walk(const struct adata *list, uint *pos, u64 *val);
+int lc_set_walk(const struct adata *list, uint *pos, lcomm *val);
 
 void ec_set_sort_x(struct adata *set); /* Sort in place */