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>

4 files changed, 153 insertions, 2 deletions

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));