Filter: Recursive filter iteration code

Add macros for recursive filter iteration that allows to examine
all instructions reachable from a filter.

5 files changed, 106 insertions, 0 deletions

diff --git a/filter/data.h b/filter/data.h
index a0ec3819..61cdb43e 100644
--- a/filter/data.h
+++ b/filter/data.h
@@ -175,6 +175,7 @@ struct f_tree *build_tree(struct f_tree *);
 const struct f_tree *find_tree(const struct f_tree *t, const struct f_val *val);
 int same_tree(const struct f_tree *t0, const struct f_tree *t2);
 void tree_format(const struct f_tree *t, buffer *buf);
+void tree_walk(const struct f_tree *t, void (*hook)(const struct f_tree *, void *), void *data);
 
 struct f_trie *f_new_trie(linpool *lp, uint data_size);
 void *trie_add_prefix(struct f_trie *t, const net_addr *n, uint l, uint h);
diff --git a/filter/decl.m4 b/filter/decl.m4
index 14b9329c..5242c04c 100644
--- a/filter/decl.m4
+++ b/filter/decl.m4
@@ -40,6 +40,7 @@ m4_divert(-1)m4_dnl
 #	106	comparator body
 #	107	struct f_line_item content
 #	108	interpreter body
+#	109	iterator body
 #
 #	Here are macros to allow you to _divert to the right directions.
 m4_define(FID_STRUCT_IN, `m4_divert(101)')
@@ -50,6 +51,7 @@ m4_define(FID_LINEARIZE_BODY, `m4_divert(105)')
 m4_define(FID_SAME_BODY, `m4_divert(106)')
 m4_define(FID_LINE_IN, `m4_divert(107)')
 m4_define(FID_INTERPRET_BODY, `m4_divert(108)')
+m4_define(FID_ITERATE_BODY, `m4_divert(109)')
 
 #	Sometimes you want slightly different code versions in different
 #	outputs.
@@ -211,6 +213,8 @@ FID_LINEARIZE_BODY()m4_dnl
 item->fl$1 = f_linearize(whati->f$1);
 FID_SAME_BODY()m4_dnl
 if (!f_same(f1->fl$1, f2->fl$1)) return 0;
+FID_ITERATE_BODY()m4_dnl
+if (whati->fl$1) BUFFER_PUSH(fit->lines) = whati->fl$1;
 FID_INTERPRET_EXEC()m4_dnl
 do { if (whati->fl$1) {
   LINEX_(whati->fl$1);
@@ -265,6 +269,7 @@ m4_define(ACCESS_RTE, `FID_HIC(,[[do { if (!fs->rte) runtime("No route to access
 #	7	dump line item callers
 #	8	linearize
 #	9	same (filter comparator)
+#	10	iterate
 #	1	union in struct f_inst
 #	3	constructors + interpreter
 #
@@ -285,6 +290,7 @@ m4_define(FID_DUMP, `FID_ZONE(6, Dump line)')
 m4_define(FID_DUMP_CALLER, `FID_ZONE(7, Dump line caller)')
 m4_define(FID_LINEARIZE, `FID_ZONE(8, Linearize)')
 m4_define(FID_SAME, `FID_ZONE(9, Comparison)')
+m4_define(FID_ITERATE, `FID_ZONE(10, Iteration)')
 
 #	This macro does all the code wrapping. See inline comments.
 m4_define(INST_FLUSH, `m4_ifdef([[INST_NAME]], [[
@@ -372,6 +378,13 @@ m4_undivert(106)m4_dnl
 #undef f2
 break;
 
+FID_ITERATE()m4_dnl			The iterator
+case INST_NAME():
+#define whati (&(what->i_]]INST_NAME()[[))
+m4_undivert(109)m4_dnl
+#undef whati
+break;
+
 m4_divert(-1)FID_FLUSH(101,200)m4_dnl  And finally this flushes all the unused diversions
 ]])')
 
@@ -582,6 +595,27 @@ FID_WR_PUT(9)
   return 1;
 }
 
+
+/* Part of FI_SWITCH filter iterator */
+static void
+f_add_tree_lines(const struct f_tree *t, void *fit_)
+{
+  struct filter_iterator * fit = fit_;
+
+  if (t->data)
+    BUFFER_PUSH(fit->lines) = t->data;
+}
+
+/* Filter line iterator */
+void
+f_add_lines(const struct f_line_item *what, struct filter_iterator *fit)
+{
+  switch(what->fi_code) {
+FID_WR_PUT(10)
+  }
+}
+
+
 #if defined(__GNUC__) && __GNUC__ >= 6
 #pragma GCC diagnostic pop
 #endif
diff --git a/filter/f-inst.c b/filter/f-inst.c
index b6bc81f7..5cae31ba 100644
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -172,6 +172,22 @@
  *	m4_dnl	use macros f1 and f2.
  *	m4_dnl	For writing directly here, use FID_SAME_BODY.
  *
+ *	m4_dnl		f_add_lines(...)
+ *	m4_dnl		{
+ *	m4_dnl		  switch (what_->fi_code) {
+ *	m4_dnl		    case FI_EXAMPLE:
+ *	m4_dnl	(109)	      [[ put it here ]]
+ *	m4_dnl		      break;
+ *	m4_dnl		  }
+ *	m4_dnl		}
+ *	m4_dnl	This code adds new filter lines reachable from the instruction
+ *	m4_dnl	to the filter iterator line buffer. This is for instructions
+ *	m4_dnl  that changes conrol flow, like FI_CONDITION or FI_CALL, most
+ *	m4_dnl  instructions do not need to update it. It is used in generic
+ *	m4_dnl  filter iteration code (FILTER_ITERATE*). For accessing your
+ *	m4_dnl  custom instruction data, use macros f1 and f2. For writing
+ *	m4_dnl	directly here, use FID_ITERATE_BODY.
+ *
  *	m4_dnl		interpret(...)
  *	m4_dnl		{
  *	m4_dnl		  switch (what->fi_code) {
@@ -948,6 +964,10 @@
     FID_SAME_BODY()
       if (!(f1->sym->flags & SYM_FLAG_SAME))
 	return 0;
+
+    FID_ITERATE_BODY()
+      BUFFER_PUSH(fit->lines) = whati->sym->function;
+
     FID_INTERPRET_BODY()
 
     /* Push the body on stack */
@@ -977,6 +997,10 @@
 
     FID_MEMBER(struct f_tree *, tree, [[!same_tree(f1->tree, f2->tree)]], "tree %p", item->tree);
 
+    FID_ITERATE_BODY()
+      tree_walk(whati->tree, f_add_tree_lines, fit);
+
+    FID_INTERPRET_BODY()
     const struct f_tree *t = find_tree(tree, &v1);
     if (!t) {
       v1.type = T_VOID;
diff --git a/filter/f-inst.h b/filter/f-inst.h
index bfa163fc..df45f88e 100644
--- a/filter/f-inst.h
+++ b/filter/f-inst.h
@@ -17,6 +17,7 @@
 #include "conf/conf.h"
 #include "filter/filter.h"
 #include "filter/data.h"
+#include "lib/buffer.h"
 #include "lib/flowspec.h"
 
 /* Flags for instructions */
@@ -50,6 +51,41 @@ static inline struct f_line *f_linearize(const struct f_inst *root)
 
 void f_dump_line(const struct f_line *, uint indent);
 
+
+/* Recursive iteration over filter instructions */
+
+struct filter_iterator {
+  BUFFER_(const struct f_line *) lines;
+};
+
+void f_add_lines(const struct f_line_item *what, struct filter_iterator *fit);
+
+#define FILTER_ITERATE_INIT(fit, filter, pool)			\
+  ({								\
+    BUFFER_INIT((fit)->lines, (pool), 32);			\
+    BUFFER_PUSH((fit)->lines) = (filter)->root;			\
+  })
+
+#define FILTER_ITERATE(fit, fi) ({				\
+  const struct f_line *fl_;					\
+  while (!BUFFER_EMPTY((fit)->lines))				\
+  {								\
+    BUFFER_POP((fit)->lines);					\
+    fl_ = (fit)->lines.data[(fit)->lines.used];			\
+    for (uint i_ = 0; i_ < fl_->len; i_++)			\
+    {								\
+      const struct f_line_item *fi = &fl_->items[i_];		\
+      f_add_lines(fi, (fit));
+
+#define FILTER_ITERATE_END } } })
+
+#define FILTER_ITERATE_CLEANUP(fit)				\
+  ({								\
+    mb_free((fit)->lines.data);					\
+    memset((fit), 0, sizeof(struct filter_iterator));		\
+  })
+
+
 struct filter *f_new_where(struct f_inst *);
 static inline struct f_dynamic_attr f_new_dynamic_attr(u8 type, enum f_type f_type, uint code) /* Type as core knows it, type as filters know it, and code of dynamic attribute */
 { return (struct f_dynamic_attr) { .type = type, .f_type = f_type, .ea_code = code }; }   /* f_type currently unused; will be handy for static type checking */
diff --git a/filter/tree.c b/filter/tree.c
index 2bbc84bb..5da86b9d 100644
--- a/filter/tree.c
+++ b/filter/tree.c
@@ -170,3 +170,14 @@ tree_format(const struct f_tree *t, buffer *buf)
 
   buffer_puts(buf, "]");
 }
+
+void
+tree_walk(const struct f_tree *t, void (*hook)(const struct f_tree *, void *), void *data)
+{
+  if (!t)
+    return;
+
+  tree_walk(t->left, hook, data);
+  hook(t, data);
+  tree_walk(t->right, hook, data);
+}