From 93d6096c8714f3c7c9450df89e812021a212b978 Mon Sep 17 00:00:00 2001
From: "Ondrej Zajicek (work)" <santiago@crfreenet.org>
Date: Thu, 3 Mar 2022 03:38:12 +0100
Subject: Filter: Implement type checks for function calls

Keep list of function parameters in f_line and use it to verify
types of arguments for function calls. Only static type checks
are implemented.
---
 filter/f-inst.h | 6 ++++++
 1 file changed, 6 insertions(+)

(limited to 'filter/f-inst.h')

diff --git a/filter/f-inst.h b/filter/f-inst.h
index df45f88e..12df40f6 100644
--- a/filter/f-inst.h
+++ b/filter/f-inst.h
@@ -35,12 +35,18 @@ const char *f_instruction_name_(enum f_instruction_code fi);
 static inline const char *f_instruction_name(enum f_instruction_code fi)
 { return f_instruction_name_(fi) + 3; }
 
+struct f_arg {
+  struct symbol *arg;
+  struct f_arg *next;
+};
+
 /* Filter structures for execution */
 /* Line of instructions to be unconditionally executed one after another */
 struct f_line {
   uint len;				/* Line length */
   u8 args;				/* Function: Args required */
   u8 vars;
+  struct f_arg *arg_list;
   struct f_line_item items[0];		/* The items themselves */
 };
 
-- 
cgit v1.2.3


From 26bc4f9904b014c9949489e8ae28366da473e85d Mon Sep 17 00:00:00 2001
From: "Ondrej Zajicek (work)" <santiago@crfreenet.org>
Date: Sun, 6 Mar 2022 02:18:01 +0100
Subject: Filter: Implement direct recursion

Direct recursion almost worked, just crashed on function signature check.
Split function parsing such that function signature is saved before
function body is processed. Recursive calls are marked so they can be
avoided during f_same() and similar code walking.

Also, include tower of hanoi solver as a test case.
---
 filter/config.Y  | 23 ++++++++++++---------
 filter/decl.m4   |  2 ++
 filter/f-inst.c  |  9 ++++++--
 filter/f-inst.h  |  2 +-
 filter/test.conf | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 86 insertions(+), 13 deletions(-)

(limited to 'filter/f-inst.h')

diff --git a/filter/config.Y b/filter/config.Y
index a4e82c7d..82a072ab 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -460,25 +460,28 @@ function_body:
 
 conf: function_def ;
 function_def:
-   FUNCTION symbol { DBG( "Beginning of function %s\n", $2->name );
+   FUNCTION symbol {
+     DBG( "Beginning of function %s\n", $2->name );
      $2 = cf_define_symbol($2, SYM_FUNCTION, function, NULL);
      cf_push_scope($2);
-   }  function_args function_body
-   {
-     $5->arg_list = NULL;
-     $5->args = 0;
+   } function_args {
+     /* Make dummy f_line for storing function prototype */
+     struct f_line *dummy = cfg_allocz(sizeof(struct f_line));
+     $2->function = dummy;
 
      /* Revert the args */
      while ($4) {
        struct f_arg *tmp = $4;
        $4 = $4->next;
 
-       tmp->next = $5->arg_list;
-       $5->arg_list = tmp;
-       $5->args++;
+       tmp->next = dummy->arg_list;
+       dummy->arg_list = tmp;
+       dummy->args++;
      }
-
-     $2->function = $5;
+   } function_body {
+     $6->args = $2->function->args;
+     $6->arg_list = $2->function->arg_list;
+     $2->function = $6;
      cf_pop_scope();
    }
  ;
diff --git a/filter/decl.m4 b/filter/decl.m4
index a2a8c88a..3d118e34 100644
--- a/filter/decl.m4
+++ b/filter/decl.m4
@@ -376,6 +376,7 @@ case INST_NAME(): {
 #undef whati
 #undef item
   dest->items[pos].fi_code = what->fi_code;
+  dest->items[pos].flags = what->flags;
   dest->items[pos].lineno = what->lineno;
   break;
 }
@@ -647,6 +648,7 @@ FID_WR_PUT(4)m4_dnl
 struct f_inst {
   struct f_inst *next;			/* Next instruction */
   enum f_instruction_code fi_code;	/* Instruction code */
+  enum f_instruction_flags flags;	/* Flags, instruction-specific */
   enum f_type type;			/* Type of returned value, if known */
   int size;				/* How many instructions are underneath */
   int lineno;				/* Line number */
diff --git a/filter/f-inst.c b/filter/f-inst.c
index 500732c6..e75b5e01 100644
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -1165,11 +1165,16 @@
     whati->fvar = tmp;
     what->size += tmp->size;
 
+    /* Mark recursive calls, they have dummy f_line */
+    if (!sym->function->len)
+      what->flags |= FIF_RECURSIVE;
+
     FID_SAME_BODY()
-      if (!(f1->sym->flags & SYM_FLAG_SAME))
-	return 0;
+    if (!(f1->sym->flags & SYM_FLAG_SAME) && !(f1_->flags & FIF_RECURSIVE))
+      return 0;
 
     FID_ITERATE_BODY()
+    if (!(what->flags & FIF_RECURSIVE))
       BUFFER_PUSH(fit->lines) = whati->sym->function;
 
     FID_INTERPRET_BODY()
diff --git a/filter/f-inst.h b/filter/f-inst.h
index 12df40f6..58563c79 100644
--- a/filter/f-inst.h
+++ b/filter/f-inst.h
@@ -22,7 +22,7 @@
 
 /* Flags for instructions */
 enum f_instruction_flags {
-  FIF_PRINTED = 1,		/* FI_PRINT_AND_DIE: message put in buffer */
+  FIF_RECURSIVE = 1,		/* FI_CALL: function is directly recursive */
 } PACKED;
 
 /* Include generated filter instruction declarations */
diff --git a/filter/test.conf b/filter/test.conf
index 401a999b..e8b6a663 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -1290,7 +1290,60 @@ function fifteen()
 	return 15;
 }
 
+function factorial(int x)
+{
+	if x = 0 then return 0;
+	if x = 1 then return 1;
+	else return x * factorial(x - 1);
+}
+
+function fibonacci(int x)
+{
+	if x = 0 then return 0;
+	if x = 1 then return 1;
+	else return fibonacci(x - 1) + fibonacci(x - 2);
+}
+
+function hanoi_init(int a; int b)
+{
+	if b = 0
+	then return +empty+;
+	else return prepend(hanoi_init(a + 1, b - 1), a);
+}
+
+function hanoi_solve(int n; bgppath h_src; bgppath h_dst; bgppath h_aux; bool x; bool y)
+bgppath tmp1;
+bgppath tmp2;
+int v;
+{
+	# x -> return src or dst
+	# y -> print state
+
+	if n = 0 then { if x then return h_src; else return h_dst; }
+
+	tmp1 = hanoi_solve(n - 1, h_src, h_aux, h_dst, true, y);
+	tmp2 = hanoi_solve(n - 1, h_src, h_aux, h_dst, false, false);
+	h_src = tmp1;
+	h_aux = tmp2;
+
+	v = h_src.first;
+	# bt_assert(h_dst = +empty+ || v < h_dst.first);
+	h_src = delete(h_src, v);
+	h_dst = prepend(h_dst, v);
+
+	if y then
+		print "move: ", v, " src: ", h_src, " dst:", h_dst, " aux:", h_aux;
+
+	tmp1 = hanoi_solve(n - 1, h_aux, h_dst, h_src, true, y);
+	tmp2 = hanoi_solve(n - 1, h_aux, h_dst, h_src, false, false);
+	h_aux = tmp1;
+	h_dst = tmp2;
+
+	if x then return h_src; else return h_dst;
+}
+
 function t_call_function()
+bgppath h_src;
 {
 	bt_assert(fifteen() = 15);
 
@@ -1302,6 +1355,16 @@ function t_call_function()
 	bt_assert(callme(4, 4) = 16);
 	bt_assert(callme(7, 2) = 14);
 	bt_assert(callmeagain(1, 2, 3) = 6);
+
+	bt_assert(factorial(5) = 120);
+	bt_assert(factorial(10) = 3628800);
+
+	bt_assert(fibonacci(10) = 55);
+	bt_assert(fibonacci(20) = 6765);
+
+	h_src = hanoi_init(1, 6);
+	bt_assert(format(h_src) = "(path 1 2 3 4 5 6)");
+	bt_assert(hanoi_solve(6, h_src, +empty+, +empty+, false, false) = h_src);
 }
 
 bt_test_suite(t_call_function, "Testing calling functions");
-- 
cgit v1.2.3


From a2527ee53d9d8fe7a1c29b56f8450b9ef1f9c7bc Mon Sep 17 00:00:00 2001
From: "Ondrej Zajicek (work)" <santiago@crfreenet.org>
Date: Wed, 9 Mar 2022 02:32:29 +0100
Subject: Filter: Improve handling of stack frames in filter bytecode

When f_line is done, we have to pop the stack frame. The old code just
removed nominal number of args/vars. Change it to use stored ventry value
modified by number of returned values. This allows to allocate variables
on a stack frame during execution of f_lines instead of just at start.

But we need to know the number of returned values for a f_line. It is 1
for term, 0 for cmd. Store that to f_line during linearization.
---
 conf/confbase.Y       |  4 ++--
 filter/config.Y       | 14 +++++++-------
 filter/decl.m4        |  6 ++++--
 filter/f-inst.c       |  8 ++++----
 filter/f-inst.h       |  7 ++++---
 filter/f-util.c       |  2 +-
 filter/filter.c       |  3 +--
 nest/config.Y         |  4 ++--
 proto/static/config.Y |  2 +-
 9 files changed, 26 insertions(+), 24 deletions(-)

(limited to 'filter/f-inst.h')

diff --git a/conf/confbase.Y b/conf/confbase.Y
index 18ca8489..1d5738ff 100644
--- a/conf/confbase.Y
+++ b/conf/confbase.Y
@@ -153,14 +153,14 @@ conf: definition ;
 definition:
    DEFINE symbol '=' term ';' {
      struct f_val *val = cfg_allocz(sizeof(struct f_val));
-     if (f_eval(f_linearize($4), cfg_mem, val) > F_RETURN) cf_error("Runtime error");
+     if (f_eval(f_linearize($4, 1), cfg_mem, val) > F_RETURN) cf_error("Runtime error");
      cf_define_symbol($2, SYM_CONSTANT | val->type, val, val);
    }
  ;
 
 expr:
    NUM
- | '(' term ')' { $$ = f_eval_int(f_linearize($2)); }
+ | '(' term ')' { $$ = f_eval_int(f_linearize($2, 1)); }
  | CF_SYM_KNOWN {
      if ($1->class != (SYM_CONSTANT | T_INT)) cf_error("Number constant expected");
      $$ = SYM_VAL($1).i; }
diff --git a/filter/config.Y b/filter/config.Y
index a3acf245..b67ca925 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -329,7 +329,7 @@ filter_def:
 
 conf: filter_eval ;
 filter_eval:
-   EVAL term { f_eval_int(f_linearize($2)); }
+   EVAL term { f_eval_int(f_linearize($2, 1)); }
  ;
 
 conf: custom_attr ;
@@ -453,7 +453,7 @@ where_filter:
 
 function_body:
    function_vars '{' cmds '}' {
-     $$ = f_linearize($3);
+     $$ = f_linearize($3, 0);
      $$->vars = $1;
    }
  ;
@@ -537,7 +537,7 @@ set_atom:
  | VPN_RD { $$.type = T_RD; $$.val.ec = $1; }
  | ENUM   { $$.type = pair_a($1); $$.val.i = pair_b($1); }
  | '(' term ')' {
-     if (f_eval(f_linearize($2), cfg_mem, &($$)) > F_RETURN) cf_error("Runtime error");
+     if (f_eval(f_linearize($2, 1), cfg_mem, &($$)) > F_RETURN) cf_error("Runtime error");
      if (!f_valid_set_type($$.type)) cf_error("Set-incompatible type");
    }
  | CF_SYM_KNOWN {
@@ -549,13 +549,13 @@ set_atom:
 
 switch_atom:
    NUM   { $$.type = T_INT; $$.val.i = $1; }
- | '(' term ')' { $$.type = T_INT; $$.val.i = f_eval_int(f_linearize($2)); }
+ | '(' term ')' { $$.type = T_INT; $$.val.i = f_eval_int(f_linearize($2, 1)); }
  | fipa  { $$ = $1; }
  | ENUM  { $$.type = pair_a($1); $$.val.i = pair_b($1); }
  ;
 
 cnum:
-   term { $$ = f_eval_int(f_linearize($1)); }
+   term { $$ = f_eval_int(f_linearize($1, 1)); }
 
 pair_item:
    '(' cnum ',' cnum ')'		{ $$ = f_new_pair_item($2, $2, $4, $4); }
@@ -642,7 +642,7 @@ switch_body: /* EMPTY */ { $$ = NULL; }
  | switch_body switch_items ':' cmds  {
      /* Fill data fields */
      struct f_tree *t;
-     struct f_line *line = f_linearize($4);
+     struct f_line *line = f_linearize($4, 0);
      for (t = $2; t; t = t->left)
        t->data = line;
      $$ = f_merge_items($1, $2);
@@ -651,7 +651,7 @@ switch_body: /* EMPTY */ { $$ = NULL; }
      struct f_tree *t = f_new_tree();
      t->from.type = t->to.type = T_VOID;
      t->right = t;
-     t->data = f_linearize($3);
+     t->data = f_linearize($3, 0);
      $$ = f_merge_items($1, t);
  }
  ;
diff --git a/filter/decl.m4 b/filter/decl.m4
index 3d118e34..4c56cd9c 100644
--- a/filter/decl.m4
+++ b/filter/decl.m4
@@ -216,7 +216,7 @@ whati->f$1 = f$1;
 FID_DUMP_BODY()m4_dnl
 f_dump_line(item->fl$1, indent + 1);
 FID_LINEARIZE_BODY()m4_dnl
-item->fl$1 = f_linearize(whati->f$1);
+item->fl$1 = f_linearize(whati->f$1, $2);
 FID_SAME_BODY()m4_dnl
 if (!f_same(f1->fl$1, f2->fl$1)) return 0;
 FID_ITERATE_BODY()m4_dnl
@@ -568,7 +568,7 @@ FID_WR_PUT(8)
 }
 
 struct f_line *
-f_linearize_concat(const struct f_inst * const inst[], uint count)
+f_linearize_concat(const struct f_inst * const inst[], uint count, uint results)
 {
   uint len = 0;
   for (uint i=0; i<count; i++)
@@ -580,6 +580,8 @@ f_linearize_concat(const struct f_inst * const inst[], uint count)
   for (uint i=0; i<count; i++)
     out->len = linearize(out, inst[i], out->len);
 
+    out->results = results;
+
 #ifdef LOCAL_DEBUG
   f_dump_line(out, 0);
 #endif
diff --git a/filter/f-inst.c b/filter/f-inst.c
index e75b5e01..5b8310c3 100644
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -64,7 +64,7 @@
  *	m4_dnl	  ARG_ANY(num);				argument with no type check accessible by v1, v2, v3
  *	m4_dnl	  ARG_TYPE(num, type);			just declare the type of argument
  *	m4_dnl	  VARARG;				variable-length argument list; accessible by vv(i) and whati->varcount
- *	m4_dnl	  LINE(num, unused);			this argument has to be converted to its own f_line
+ *	m4_dnl	  LINE(num, out);			this argument has to be converted to its own f_line
  *	m4_dnl	  SYMBOL;				symbol handed from config
  *	m4_dnl	  STATIC_ATTR;				static attribute definition
  *	m4_dnl	  DYNAMIC_ATTR;				dynamic attribute definition
@@ -298,7 +298,7 @@
     RESULT_TYPE(T_BOOL);
 
     if (v1.val.i)
-      LINE(2,0);
+      LINE(2,1);
     else
       RESULT_VAL(v1);
   }
@@ -308,7 +308,7 @@
     RESULT_TYPE(T_BOOL);
 
     if (!v1.val.i)
-      LINE(2,0);
+      LINE(2,1);
     else
       RESULT_VAL(v1);
   }
@@ -536,7 +536,7 @@
     if (v1.val.i)
       LINE(2,0);
     else
-      LINE(3,1);
+      LINE(3,0);
   }
 
   INST(FI_PRINT, 0, 0) {
diff --git a/filter/f-inst.h b/filter/f-inst.h
index 58563c79..e35f71c6 100644
--- a/filter/f-inst.h
+++ b/filter/f-inst.h
@@ -46,14 +46,15 @@ struct f_line {
   uint len;				/* Line length */
   u8 args;				/* Function: Args required */
   u8 vars;
+  u8 results;				/* Results left on stack: cmd -> 0, term -> 1 */
   struct f_arg *arg_list;
   struct f_line_item items[0];		/* The items themselves */
 };
 
 /* Convert the f_inst infix tree to the f_line structures */
-struct f_line *f_linearize_concat(const struct f_inst * const inst[], uint count);
-static inline struct f_line *f_linearize(const struct f_inst *root)
-{ return f_linearize_concat(&root, 1); }
+struct f_line *f_linearize_concat(const struct f_inst * const inst[], uint count, uint results);
+static inline struct f_line *f_linearize(const struct f_inst *root, uint results)
+{ return f_linearize_concat(&root, 1, results); }
 
 void f_dump_line(const struct f_line *, uint indent);
 
diff --git a/filter/f-util.c b/filter/f-util.c
index 410999a6..fdb314b5 100644
--- a/filter/f-util.c
+++ b/filter/f-util.c
@@ -37,7 +37,7 @@ struct filter *f_new_where(struct f_inst *where)
 				   f_new_inst(FI_DIE, F_REJECT));
 
   struct filter *f = cfg_allocz(sizeof(struct filter));
-  f->root = f_linearize(cond);
+  f->root = f_linearize(cond, 0);
   return f;
 }
 
diff --git a/filter/filter.c b/filter/filter.c
index e505d570..20a380dc 100644
--- a/filter/filter.c
+++ b/filter/filter.c
@@ -215,8 +215,7 @@ interpret(struct filter_state *fs, const struct f_line *line, struct f_val *val)
     }
 
     /* End of current line. Drop local variables before exiting. */
-    fstk->vcnt -= curline.line->vars;
-    fstk->vcnt -= curline.line->args;
+    fstk->vcnt = curline.ventry + curline.line->results;
     fstk->ecnt--;
   }
 
diff --git a/nest/config.Y b/nest/config.Y
index 17999422..ac599c09 100644
--- a/nest/config.Y
+++ b/nest/config.Y
@@ -165,7 +165,7 @@ rtrid:
 
 idval:
    NUM { $$ = $1; }
- | '(' term ')' { $$ = f_eval_int(f_linearize($2)); }
+ | '(' term ')' { $$ = f_eval_int(f_linearize($2, 1)); }
  | IP4 { $$ = ip4_to_u32($1); }
  | CF_SYM_KNOWN {
      if ($1->class == (SYM_CONSTANT | T_INT) || $1->class == (SYM_CONSTANT | T_QUAD))
@@ -860,7 +860,7 @@ CF_CLI(DUMP FILTER ALL,,, [[Dump all filters in linearized form]])
 { filters_dump_all(); cli_msg(0, ""); } ;
 
 CF_CLI(EVAL, term, <expr>, [[Evaluate an expression]])
-{ cmd_eval(f_linearize($2)); } ;
+{ cmd_eval(f_linearize($2, 1)); } ;
 
 CF_CLI_HELP(ECHO, ..., [[Control echoing of log messages]])
 CF_CLI(ECHO, echo_mask echo_size, (all | off | { debug|trace|info|remote|warning|error|auth [, ...] }) [<buffer-size>], [[Control echoing of log messages]]) {
diff --git a/proto/static/config.Y b/proto/static/config.Y
index 41e10dbf..9d26ee82 100644
--- a/proto/static/config.Y
+++ b/proto/static/config.Y
@@ -40,7 +40,7 @@ static_route_finish(void)
   if (net_type_match(this_srt->net, NB_DEST) == !this_srt->dest)
     cf_error("Unexpected or missing nexthop/type");
 
-  this_srt->cmds = f_linearize(this_srt_cmds);
+  this_srt->cmds = f_linearize(this_srt_cmds, 0);
 }
 
 CF_DECLS
-- 
cgit v1.2.3