Unit Testing for BIRD

 - Unit Testing Framework (BirdTest)
 - Integration of BirdTest into the BIRD build system
 - Tests for several BIRD modules

 Based on squashed Pavel Tvrdik's int-test branch, updated for
 current int-new branch.

12 files changed, 1694 insertions, 385 deletions

diff --git a/filter/Makefile b/filter/Makefile
index f27befdf..6bada8ca 100644
--- a/filter/Makefile
+++ b/filter/Makefile
@@ -2,3 +2,7 @@ src := filter.c f-util.c tree.c trie.c
 obj := $(src-o-files)
 $(all-daemon)
 $(cf-local)
+
+tests_src := tree_test.c filter_test.c trie_test.c
+tests_targets := $(tests_targets) $(tests-target-files)
+tests_objs := $(tests_objs) $(src-o-files)
diff --git a/filter/config.Y b/filter/config.Y
index 8af444a3..b5ae850a 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -323,7 +323,71 @@ f_generate_lc(struct f_inst *t1, struct f_inst *t2, struct f_inst *t3)
   return rv;
 }
 
+/*
+ * Remove all new lines and doubled whitespaces
+ * and convert all tabulators to spaces
+ * and return a copy of string
+ */
+char *
+assert_copy_expr(const char *start, size_t len)
+{
+  /* XXX: Allocates maybe a little more memory than we really finally need */
+  char *str = cfg_alloc(len + 1);
+
+  char *dst = str;
+  const char *src = start - 1;
+  const char *end = start + len;
+  while (++src < end)
+  {
+    if (*src == '\n')
+      continue;
+
+    /* Skip doubled whitespaces */
+    if (src != start)
+    {
+      const char *prev = src - 1;
+      if ((*src == ' ' || *src == '\t') && (*prev == ' ' || *prev == '\t'))
+	continue;
+    }
+
+    if (*src == '\t')
+      *dst = ' ';
+    else
+      *dst = *src;
+
+    dst++;
+  }
+  *dst = '\0';
+
+  return str;
+}
+
+/*
+ * assert_done - create f_instruction of bt_assert
+ * @expr: expression in bt_assert()
+ * @start: pointer to first char of test expression
+ * @end: pointer to the last char of test expression
+ */
+static struct f_inst *
+assert_done(struct f_inst *expr, const char *start, const char *end)
+{
+  struct f_inst *i;
+  i = f_new_inst();
+  i->code = P('a','s');
+  i->a1.p = expr;
+
+  if (end >= start)
+  {
+    i->a2.p = assert_copy_expr(start, end - start + 1);
+  }
+  else
+  {
+    /* this is a break of lexer buffer */
+    i->a2.p = "???";
+  }
 
+  return i;
+}
 
 CF_DECLS
 
@@ -341,12 +405,13 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN,
 	ADD, DELETE, CONTAINS, RESET,
 	PREPEND, FIRST, LAST, LAST_NONAGGREGATED, MATCH,
 	EMPTY,
-	FILTER, WHERE, EVAL)
+	FILTER, WHERE, EVAL,
+	BT_ASSERT, BT_TEST_SUITE)
 
 %nonassoc THEN
 %nonassoc ELSE
 
-%type <x> term block cmds cmds_int cmd function_body constant constructor print_one print_list var_list var_listn dynamic_attr static_attr function_call symbol bgp_path_expr
+%type <x> term block cmds cmds_int cmd function_body constant constructor print_one print_list var_list var_listn dynamic_attr static_attr function_call symbol bgp_path_expr bt_assert
 %type <f> filter filter_body where_filter
 %type <i> type break_command ec_kind
 %type <i32> cnum
@@ -356,6 +421,7 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN,
 %type <px> fprefix
 %type <s> decls declsn one_decl function_params
 %type <h> bgp_path bgp_path_tail1 bgp_path_tail2
+%type <t> get_cf_position
 
 CF_GRAMMAR
 
@@ -375,6 +441,21 @@ filter_eval:
    EVAL term { f_eval_int($2); }
  ;
 
+CF_ADDTO(conf, bt_test_suite)
+bt_test_suite:
+ BT_TEST_SUITE '(' SYM ',' text ')' {
+  if (!($3->class & SYM_FUNCTION))
+    cf_error("Function expected");
+
+  struct f_bt_test_suite *t = cfg_alloc(sizeof(struct f_bt_test_suite));
+  t->fn = $3->def;
+  t->fn_name = $3->name;
+  t->dsc = $5;
+
+  add_tail(&new_config->tests, &t->n);
+ }
+ ;
+
 type:
    INT { $$ = T_INT; }
  | BOOL { $$ = T_BOOL; }
@@ -835,6 +916,8 @@ term:
  | ROA_CHECK '(' rtable ')' { $$ = f_generate_roa_check($3, NULL, NULL); }
  | ROA_CHECK '(' rtable ',' term ',' term ')' { $$ = f_generate_roa_check($3, $5, $7); }
 
+ | bt_assert { $$ = $1; }
+
 /* | term '.' LEN { $$->code = P('P','l'); } */
 
 /* function_call is inlined here */
@@ -966,6 +1049,7 @@ cmd:
       $$->a1.p = $2;
       $$->a2.p = build_tree( $4 );
    }
+ | bt_assert ';' { $$ = $1; }
 
 
  | rtadot dynamic_attr '.' EMPTY ';' { $$ = f_generate_empty($2); }
@@ -975,4 +1059,14 @@ cmd:
  | rtadot dynamic_attr '.' FILTER '(' term ')' ';'    { $$ = f_generate_complex( P('C','a'), 'f', $2, $6 ); }
  ;
 
+ bt_assert:
+   BT_ASSERT '(' get_cf_position term get_cf_position ')' { $$ = assert_done($4, $3 + 1, $5 - 1); }
+ ;
+
+get_cf_position:
+{
+  $$ = cf_text;
+};
+
+
 CF_END
diff --git a/filter/filter.c b/filter/filter.c
index 09b89401..3df602a3 100644
--- a/filter/filter.c
+++ b/filter/filter.c
@@ -52,6 +52,8 @@
 
 #define CMP_ERROR 999
 
+void (*bt_assert_hook)(int result, struct f_inst *assert);
+
 static struct adata *
 adata_empty(struct linpool *pool, int l)
 {
@@ -563,8 +565,8 @@ f_rta_cow(void)
 
 static struct tbf rl_runtime_err = TBF_DEFAULT_LOG_LIMITS;
 
-#define runtime(x) do { \
-    log_rl(&rl_runtime_err, L_ERR "filters, line %d: %s", what->lineno, x); \
+#define runtime(fmt, ...) do { \
+    log_rl(&rl_runtime_err, L_ERR "filters, line %d: " fmt, what->lineno, ##__VA_ARGS__); \
     res.type = T_RETURN; \
     res.val.i = F_ERROR; \
     return res; \
@@ -1475,6 +1477,17 @@ interpret(struct f_inst *what)
 
     break;
 
+  case P('a', 's'):	/* Birdtest Assert */
+    ONEARG;
+
+    if (v1.type != T_BOOL)
+      runtime("Should be boolean value");
+
+    res.type = v1.type;
+    res.val = v1.val;
+
+    CALL(bt_assert_hook, res.val.i, what);
+    break;
 
   default:
     bug( "Unknown instruction %d (%c)", what->code, what->code & 0xff);
diff --git a/filter/filter.h b/filter/filter.h
index fc11b91e..a4808731 100644
--- a/filter/filter.h
+++ b/filter/filter.h
@@ -16,16 +16,16 @@
 
 struct f_inst {		/* Instruction */
   struct f_inst *next;	/* Structure is 16 bytes, anyway */
-  u16 code;
-  u16 aux;
+  u16 code;		/* Instruction code, see the interpret() function and P() macro */
+  u16 aux;		/* Extension to instruction code, T_*, EA_*, EAF_*  */
   union {
     int i;
     void *p;
-  } a1;
+  } a1;			/* The first argument */
   union {
     int i;
     void *p;
-  } a2;
+  } a2;			/* The second argument */
   int lineno;
 };
 
@@ -55,7 +55,7 @@ struct f_prefix {
 };
 
 struct f_val {
-  int type;
+  int type;		/* T_*  */
   union {
     uint i;
     u64 ec;
@@ -205,4 +205,15 @@ struct f_trie
 
 #define FF_FORCE_TMPATTR 1		/* Force all attributes to be temporary */
 
+/* Bird Tests */
+struct f_bt_test_suite {
+  node n;			/* Node in config->tests */
+  struct f_inst *fn;		/* Root of function */
+  const char *fn_name;		/* Name of test */
+  const char *dsc;		/* Description */
+};
+
+/* Hook for call bt_assert() function in configuration */
+extern void (*bt_assert_hook)(int result, struct f_inst *assert);
+
 #endif
diff --git a/filter/filter_test.c b/filter/filter_test.c
new file mode 100644
index 00000000..693b1fe0
--- /dev/null
+++ b/filter/filter_test.c
@@ -0,0 +1,87 @@
+/*
+ *	Filters: Tests
+ *
+ *	(c) 2015 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
+
+#include <string.h>
+#include <stdlib.h>
+
+#include "test/birdtest.h"
+#include "test/bt-utils.h"
+
+#include "filter/filter.h"
+#include "conf/conf.h"
+
+#define BT_CONFIG_FILE "filter/test.conf"
+
+
+static struct config *
+parse_config_file(const void *filename_void)
+{
+  bt_bird_init();
+
+  size_t fn_size = strlen((const char *) filename_void) + 1;
+  char *filename = alloca(fn_size);
+  strncpy(filename, filename_void, fn_size);
+
+  struct config *c = bt_config_file_parse(filename);
+  bt_bird_cleanup();
+
+  return c;
+}
+
+static int
+run_function(const void *parsed_fn_def)
+{
+  /* XXX: const -> non-const */
+  struct f_inst *f = (struct f_inst *) parsed_fn_def;
+
+  linpool *tmp = lp_new(&root_pool, 4096);
+  struct f_val res = f_eval(f, tmp);
+  rfree(tmp);
+
+  if (res.type == T_RETURN && res.val.i >= F_REJECT)
+    return BT_FAILURE;
+
+  return BT_SUCCESS;
+}
+
+static void
+bt_assert_filter(int result, struct f_inst *assert)
+{
+  int bt_suit_case_result = BT_SUCCESS;
+  if (!result)
+  {
+    bt_result = BT_FAILURE;
+    bt_suite_result = BT_FAILURE;
+    bt_suit_case_result = BT_FAILURE;
+  }
+
+  bt_log_suite_case_result(bt_suit_case_result, "Assertion at line %d (%s)", assert->lineno, (char *) assert->a2.p);
+}
+
+int
+main(int argc, char *argv[])
+{
+  bt_init(argc, argv);
+
+  struct config *c = parse_config_file(BT_CONFIG_FILE);
+
+  if (c)
+  {
+    bt_assert_hook = bt_assert_filter;
+
+    struct f_bt_test_suite *t;
+    WALK_LIST(t, c->tests)
+      bt_test_suite_base(run_function, t->fn_name, t->fn, BT_FORKING, BT_TIMEOUT, "%s", t->dsc);
+  }
+
+  return bt_exit_value();
+}
diff --git a/filter/test.conf b/filter/test.conf
index e65b3ebb..de3a3113 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -1,24 +1,24 @@
-
 /*
- *	This is an example configuration file.
+ *	This is unit testing configuration file for testing filters
+ *
  *	FIXME: add all examples from docs here.
  */
 
-# Yet another comment
-
 router id 62.168.0.1;
 
-define xyzzy = (120+10);
-define '1a-a1' = (20+10);
-define one = 1;
-define ten = 10;
+/* We have to setup any protocol */
+protocol static { ipv4; }
+
 
-define p23 = (2, 3);
-define ip1222 = 1.2.2.2;
 
-define net10 = 10.0.0.0/8;
-define netdoc = 2001:db8::/32;
 
+/*
+ * 	Common definitions and functions
+ * 	--------------------------------
+ */
+
+define one = 1;
+define ten = 10;
 
 function onef(int a)
 {
@@ -26,108 +26,78 @@ function onef(int a)
 }
 
 
-function 'mkpair-a'(int a)
-{
-	return (1, a);
-}
 
-function mktrip(int a)
-{
-	return (a, 2*a, 3*a);
-}
 
-function mkpath(int a; int b)
-{
-	return [= a b 3 2 1 =];
-}
+/*
+ * 	Testing empty lists/paths
+ * 	-------------------------
+ */
 
-function callme(int arg1; int arg2)
-int local1;
-int local2;
-int i;
+function t_empty()
 {
-	printn "Function callme called arguments ", arg1, " and ", arg2, ": " ;
-	i = arg2;
+	bt_assert(+empty+ = +empty+);
+	bt_assert(+empty+ != -empty-);
+	bt_assert(+empty+ != --empty--);
 
-	case arg1 {
-	11, 1, 111: printn "jedna, "; printn "jedna";
-	(one+onef(2)): printn "dva, "; printn "jeste jednou dva";
-	(2+one) .. 5: if arg2 < 3 then printn "tri az pet";
-	else: printn "neco jineho";
-	}
-	print;
-}
+	bt_assert(-empty- = -empty-);
+	bt_assert(-empty- != --empty--);
 
-function fifteen()
-{
-	print "fifteen called";
-	return 15;
+	bt_assert(--empty-- = --empty--);
 }
 
+bt_test_suite(t_empty, "Testing +empty+, -empty-, --empty--");
+
+
+
+
 /*
-roa table rl
-{
-	roa 10.110.0.0/16 max 16 as 1000;
-	roa 10.120.0.0/16 max 24 as 1000;
-	roa 10.130.0.0/16 max 24 as 2000;
-	roa 10.130.128.0/18 max 24 as 3000;
-}
+ * 	Testing Paths
+ * 	-------------
+ */
 
-function test_roa()
+function mkpath(int a; int b)
 {
-	# cannot be tested in __startup(), sorry
-	print "Testing ROA";
-	print "Should be true: ", roa_check(rl, 10.10.0.0/16, 1000) = ROA_UNKNOWN,
-	      " ", roa_check(rl, 10.0.0.0/8, 1000) = ROA_UNKNOWN,
-	      " ", roa_check(rl, 10.110.0.0/16, 1000) = ROA_VALID,
-	      " ", roa_check(rl, 10.110.0.0/16, 2000) = ROA_INVALID,
-	      " ", roa_check(rl, 10.110.32.0/20, 1000) = ROA_INVALID,
-	      " ", roa_check(rl, 10.120.32.0/20, 1000) = ROA_VALID;
-	print "Should be true: ", roa_check(rl, 10.120.32.0/20, 2000) = ROA_INVALID,
-	      " ", roa_check(rl, 10.120.32.32/28, 1000) = ROA_INVALID,
-	      " ", roa_check(rl, 10.130.130.0/24, 1000) = ROA_INVALID,
-	      " ", roa_check(rl, 10.130.130.0/24, 2000) = ROA_VALID,
-	      " ", roa_check(rl, 10.130.30.0/24, 3000) = ROA_INVALID,
-	      " ", roa_check(rl, 10.130.130.0/24, 3000) = ROA_VALID;
+	return [= a b 3 2 1 =];
 }
-*/
 
-function path_test()
+function t_path()
 bgpmask pm1;
 bgpmask pm2;
 bgppath p2;
-clist l;
-clist l2;
-eclist el;
-eclist el2;
-lclist ll;
-lclist ll2;
 {
-	print "Entering path test...";
 	pm1 =  / 4 3 2 1 /;
-	pm2 = [= 3..6 3 2 1..2 =];
-	print "Testing path masks: ", pm1, " ", pm2;
+	pm2 = [= 4 3 2 1 =];
+
 	p2 = prepend( + empty +, 1 );
 	p2 = prepend( p2, 2 );
 	p2 = prepend( p2, 3 );
 	p2 = prepend( p2, 4 );
-	print "Testing path: (4 3 2 1) = ", p2;
-	print "Should be true: ", p2 ~ pm1, " ", p2 ~ pm2, " ", 3 ~ p2, " ", p2 ~ [2, 10..20], " ", p2 ~ [4, 10..20];
-	print "4 = ", p2.len;
-	p2 = prepend( p2, 5 );
-	print "Testing path: (5 4 3 2 1) = ", p2;
-	print "Should be false: ", p2 ~ pm1, " ", p2 ~ pm2, " ", 10 ~ p2, " ", p2 ~ [8, ten..(2*ten)], " ", p2 ~ [= 1..4 4 3 2 1 =], " ",  p2 ~ [= 5 4 4..100 2 1 =];
-	print "Should be true: ", p2 ~  / ? 4 3 2 1 /,  " ", p2, " ",  / ? 4 3 2 1 /;
-	print "Should be true: ", p2 ~ [= * 4 3 * 1 =], " ", p2, " ", [= * 4 3 * 1 =];
-	print "Should be true: ", p2 ~ [= 5..6 4..10 1..3 1..3 1..65536 =];
-	print "Should be true: ", p2 ~ [= (3+2) (2*2) 3 2 1 =], " ", p2 ~ mkpath(5, 4);
-	print "Should be true: ", p2.len = 5, " ", p2.first = 5, " ", p2.last = 1;
-	print "Should be true: ", pm1 = [= 4 3 2 1 =], " ", pm1 != [= 4 3 1 2 =], " ",
-				pm2 = [= 3..6 3 2 1..2 =], " ", pm2 != [= 3..6 3 2 1..3 =], " ",
-				[= 1 2 (1+2) =] = [= 1 2 (1+2) =], " ", [= 1 2 (1+2) =] != [= 1 2 (2+1) =];
-	print "5 = ", p2.len;
-	print "Delete 3:   ", delete(p2, 3);
-	print "Filter 1-3: ", filter(p2, [1..3]);
+
+	print "Testing paths: ", p2;
+	bt_assert(p2.len = 4);
+	bt_assert(p2 ~ pm1);
+	bt_assert(p2 ~ pm2);
+	bt_assert(3 ~ p2);
+	bt_assert(p2 ~ [2, 10..20]);
+	bt_assert(p2 ~ [4, 10..20]);
+
+	p2 = prepend(p2, 5);
+	bt_assert(p2 !~ pm1);
+	bt_assert(p2 !~ pm2);
+	bt_assert(10 !~ p2);
+	bt_assert(p2 !~ [8, ten..(2*ten)]);
+	bt_assert(p2 ~  / ? 4 3 2 1 /);
+	bt_assert(p2 ~ [= * 4 3 * 1 =]);
+	bt_assert(p2 ~ [= (3+2) (2*2) 3 2 1 =]);
+	bt_assert(p2 ~ mkpath(5, 4));
+
+	bt_assert(p2.len = 5);
+	bt_assert(p2.first = 5);
+	bt_assert(p2.last = 1);
+
+	bt_assert(p2.len = 5);
+	bt_assert(delete(p2, 3) = prepend(prepend(prepend(prepend(+empty+, 1), 2), 4), 5));
+	bt_assert(filter(p2, [1..3]) = prepend(prepend(prepend(+empty+, 1), 2), 3));
 
 	pm1 = [= 1 2 * 3 4 5 =];
 	p2 = prepend( + empty +, 5 );
@@ -136,63 +106,134 @@ lclist ll2;
 	p2 = prepend( p2, 3 );
 	p2 = prepend( p2, 2 );
 	p2 = prepend( p2, 1 );
-	print "Should be true: ", p2 ~ pm1, " ", p2, " ", pm1;
-	print "Delete 3:   ", delete(p2, 3);
-	print "Delete 4-5: ", delete(p2, [4..5]);
+
+	bt_assert(p2 ~ pm1);
+	bt_assert(delete(p2, 3) = prepend(prepend(prepend(prepend(+empty+, 5), 4), 2), 1));
+	bt_assert(delete(p2, [4..5]) = prepend(prepend(prepend(prepend(+empty+, 3), 3), 2), 1));
+}
+
+bt_test_suite(t_path, "Testing paths");
+
+
+
+
+/*
+ * 	Testing Community List
+ *	----------------------
+ */
+
+define p23 = (2, 3);
+
+function t_community_list()
+clist l;
+clist l2;
+{
+	/* XXX: add((x,y)) works as prepend */
 
 	l = - empty -;
-	print "Should be false in this special case: ", l ~ [(*,*)];
+	bt_assert(l !~ [(*,*)]);
+	bt_assert((l ~ [(*,*)]) != (l !~ [(*,*)]));
+
 	l = add( l, (one,2) );
-	print "Should be always true: ", l ~ [(*,*)];
+	bt_assert(l ~ [(*,*)]);
 	l = add( l, (2,one+2) );
 	print "Community list (1,2) (2,3) ", l;
-	print "Should be true: ", (2,3) ~ l, " ", l ~ [(1,*)], " ", l ~ [p23]," ", l ~ [(2,2..3)], " ", l ~ [(1,1..2)], " ", l ~ [(1,1)..(1,2)];
-	l = add( l, (2,5) );
-	l = add( l, (5,one) );
-	l = add( l, (6,one) );
-	l = add( l, (one,one) );
-	l = delete( l, [(5,1),(6,one),(one,1)] );
-	l = delete( l, [(5,one),(6,one)] );
-	l = filter( l, [(1,*)] );
-	print "Community list (1,2) ", l;
-	print "Should be false: ", (2,3) ~ l, " ", l ~ [(2,*)], " ", l ~ [(one,3..6)];
-	print "Should be always true: ", l ~ [(*,*)];
-	l = add( l, (3,one) );
-	l = add( l, (one+one+one,one+one) );
-	l = add( l, (3,3) );
-	l = add( l, (3,4) );
-	l = add( l, (3,5) );
-	l2 = filter( l, [(3,*)] );
-	l = delete( l, [(3,2..4)] );
-	print "Community list (1,2) (3,1) (3,5) ", l, " len: ", l.len;
-	l = add( l, (3,2) );
-	l = add( l, (4,5) );
-	print "Community list (1,2) (3,1) (3,5) (3,2) (4,5) ", l, " len: ", l.len;
-	print "Should be true: ", l ~ [(*,2)], " ", l ~ [(*,5)], " ", l ~ [(*, one)];
-	print "Should be false: ", l ~ [(*,3)], " ", l ~ [(*,(one+6))], " ", l ~ [(*, (one+one+one))];
-	l = delete( l, [(*,(one+onef(3)))] );
-	l = delete( l, [(*,(4+one))] );
-	print "Community list (3,1) ", l;
-	l = delete( l, [(*,(onef(5)))] );
-	print "Community list empty ", l;
-	l2 = add( l2, (3,6) );
-	l = filter( l2, [(3,1..4)] );
-	l2 = filter( l2, [(3,3..6)] );
+
+	bt_assert((2,3) ~ l);
+	bt_assert(l ~ [(1,*)]);
+	bt_assert(l ~ [p23]);
+	bt_assert(l ~ [(2,2..3)]);
+	bt_assert(l ~ [(1,1..2)]);
+	bt_assert(l ~ [(1,1)..(1,2)]);
+
+	l = add(l, (2,5));
+	l = add(l, (5,one));
+	l = add(l, (6,one));
+	l = add(l, (one,one));
+	l = delete(l, [(5,1),(6,one),(one,1)]);
+	l = delete(l, [(5,one),(6,one)]);
+	l = filter(l, [(1,*)]);
+	bt_assert(l = add(-empty-, (1,2)));
+
+	bt_assert((2,3) !~ l);
+	bt_assert(l !~ [(2,*)]);
+	bt_assert(l !~ [(one,3..6)]);
+	bt_assert(l ~ [(*,*)]);
+
+	l = add(l, (3,one));
+	l = add(l, (one+one+one,one+one));
+	l = add(l, (3,3));
+	l = add(l, (3,4));
+	l = add(l, (3,5));
+	l2 = filter(l, [(3,*)]);
+	l = delete(l, [(3,2..4)]);
+	bt_assert(l = add(add(add(-empty-, (1,2)), (3,1)), (3,5)));
+	bt_assert(l.len = 3);
+
+	l = add(l, (3,2));
+	l = add(l, (4,5));
+	bt_assert(l = add(add(add(add(add(-empty-, (1,2)), (3,1)), (3,5)), (3,2)), (4,5)));
+
+	bt_assert(l.len = 5);
+	bt_assert(l ~ [(*,2)]);
+	bt_assert(l ~ [(*,5)]);
+	bt_assert(l ~ [(*, one)]);
+	bt_assert(l !~ [(*,3)]);
+	bt_assert(l !~ [(*,(one+6))]);
+	bt_assert(l !~ [(*, (one+one+one))]);
+
+	l = delete(l, [(*,(one+onef(3)))]);
+	l = delete(l, [(*,(4+one))]);
+	bt_assert(l = add(-empty-, (3,1)));
+
+	l = delete(l, [(*,(onef(5)))]);
+	bt_assert(l = -empty-);
+
+	l2 = add(l2, (3,6));
+	l = filter(l2, [(3,1..4)]);
+	l2 = filter(l2, [(3,3..6)]);
+
 	print "clist A (1..4): ", l;
+	bt_assert(l = add(add(add(add(-empty-, (3,1)), (3,2)), (3,3)), (3,4)));
+
 	print "clist B (3..6): ", l2;
-	print "clist A union B: ", add( l2, l );
+	bt_assert(l2 = add(add(add(add(-empty-, (3,3)), (3,4)), (3,5)), (3,6)));
+
+	print "clist A union B: ", add( l, l2 );
+	bt_assert(add(l, l2) = add(add(add(add(add(add(-empty-, (3,1)), (3,2)), (3,3)), (3,4)), (3,5)), (3,6)));
+
 	print "clist A isect B: ", filter( l, l2 );
+	bt_assert(filter(l, l2) = add(add(-empty-, (3,3)), (3,4)));
+
 	print "clist A \ B: ", delete( l, l2 );
+	bt_assert(delete(l, l2) = add(add(-empty-, (3,1)), (3,2)));
+}
+
+bt_test_suite(t_community_list, "Testing communities and lists");
+
+
+
+
+/*
+ * 	Testing Extended Community List
+ * 	-------------------------------
+ */
 
+function t_extended_community_list()
+eclist el;
+eclist el2;
+{
 	el = -- empty --;
 	el = add(el, (rt, 10, 20));
 	el = add(el, (ro, 10.20.30.40, 100));
 	el = add(el, (ro, 11.21.31.41.mask(16), 200));
+
 	print "EC list (rt, 10, 20) (ro, 10.20.30.40, 100) (ro, 11.21.0.0, 200):";
 	print el;
-	print "EC len: ", el.len;
+	bt_assert(el.len = 3);
 	el = delete(el, (rt, 10, 20));
 	el = delete(el, (rt, 10, 30));
+	bt_assert(el = add(add(--empty--, (ro, 10.20.30.40, 100)), (ro, 11.21.0.0, 200)));
 	el = add(el, (unknown 2, ten, 1));
 	el = add(el, (unknown 5, ten, 1));
 	el = add(el, (rt, ten, one+one));
@@ -201,268 +242,688 @@ lclist ll2;
 	el = add(el, (rt, 10, 5));
 	el = add(el, (generic, 0x2000a, 3*ten));
 	el = delete(el, [(rt, 10, 2..ten)]);
-	print "EC list (ro, 10.20.30.40, 100) (ro, 11.21.0.0, 200) (rt, 10, 1) (unknown 0x5, 10, 1) (rt, 10, 30):";
-	print el;
+	bt_assert(el = add(add(add(add(add(--empty--, (ro, 10.20.30.40, 100)), (ro, 11.21.0.0, 200)), (rt, 10, 1)), (unknown 5, 10, 1)), (rt, 10, 30)));
+
 	el = filter(el, [(rt, 10, *)]);
-	print "EC list (rt, 10, 1) (rt, 10, 30): ", el;
-	print "Testing EC list, true: ", (rt, 10, 1) ~ el, " ", el ~ [(rt, 10, ten..40)];
-	print "Testing EC list, false: ", (rt, 10, 20) ~ el, " ", (ro, 10.20.30.40, 100) ~ el, " ", el ~ [(rt, 10, 35..40)], " ", el ~ [(ro, 10, *)];
+	bt_assert(el = add(add(--empty--, (rt, 10, 1)), (rt, 10, 30)));
+	bt_assert((rt, 10, 1) ~ el);
+	bt_assert(el ~ [(rt, 10, ten..40)]);
+	bt_assert((rt, 10, 20) !~ el);
+	bt_assert((ro, 10.20.30.40, 100) !~ el);
+	bt_assert(el !~ [(rt, 10, 35..40)]);
+	bt_assert(el !~ [(ro, 10, *)]);
+
 	el = add(el, (rt, 10, 40));
 	el2 = filter(el, [(rt, 10, 20..40)] );
 	el2 = add(el2, (rt, 10, 50));
+
 	print "eclist A (1,30,40): ", el;
+	bt_assert(el = add(add(add(--empty--, (rt, 10, 1)), (rt, 10, 30)), (rt, 10, 40)));
+
 	print "eclist B (30,40,50): ", el2;
-	print "eclist A union B: ", add( el2, el );
-	print "eclist A isect B: ", filter( el, el2 );
-	print "eclist A \ B: ", delete( el, el2 );
-
-	ll = --- empty ---;
-	ll = add(ll, (ten, 20, 30));
-	ll = add(ll, (1000, 2000, 3000));
-	ll = add(ll, mktrip(100000));
-	print "LC list (10, 20, 30) (1000, 2000, 3000) (100000, 200000, 300000):";
-	print ll;
-	print "LC len: ", el.len;
-	print "Should be true: ", mktrip(1000) ~ ll, " ", ll ~ [(5,10,15), (10,20,30)], " ", ll ~ [(10,15..25,*)], " ", ll ~ [(ten, *, *)];
-	print "Should be false: ", mktrip(100) ~ ll, " ", ll ~ [(5,10,15), (10,21,30)], " ", ll ~ [(10,21..25,*)], " ", ll ~ [(11, *, *)];
-	print "LC filtered: ", filter(ll, [(5..15, *, *), (100000, 500..500000, *)]);
-
-	ll = --- empty ---;
-	ll = add(ll, (10, 10, 10));
-	ll = add(ll, (20, 20, 20));
-	ll = add(ll, (30, 30, 30));
-
-	ll2 = --- empty ---;
-	ll2 = add(ll2, (20, 20, 20));
-	ll2 = add(ll2, (30, 30, 30));
-	ll2 = add(ll2, (40, 40, 40));
-
-	print "lclist A (10,20,30): ", ll;
-	print "lclist B (20,30,40): ", ll2;
-	print "lclist A union B: ", add(ll, ll2);
-	print "lclist A isect B: ", filter(ll, ll2);
-	print "lclist A \ B: ", delete(ll, ll2);
-
-#	test_roa();
-}
-
-function bla()
-{
-	print "fifteen called";
-	return 15;
+	bt_assert(el2 = add(add(add(--empty--, (rt, 10, 30)), (rt, 10, 40)), (rt, 10, 50)));
+
+	print "eclist A union B: ", add(el2, el);
+	bt_assert(add(el2, el) =  add(add(add(add(--empty--, (rt, 10, 30)), (rt, 10, 40)), (rt, 10, 50)), (rt, 10, 1)));
+
+	print "eclist A isect B: ", filter(el, el2);
+	bt_assert(filter(el, el2) = add(add(--empty--, (rt, 10, 30)), (rt, 10, 40)));
+
+	print "eclist A \ B: ", delete(el, el2);
+	bt_assert(delete(el, el2) = add(--empty--, (rt, 10, 1)));
 }
 
-define four=4;
-define onetwo=1.2.3.4;
+bt_test_suite(t_extended_community_list, "Testing extended communities and lists");
 
-function __test1()
+
+
+
+/*
+ * 	Testing defined() function
+ * 	--------------------------
+ */
+
+function test_undef(int a)
+int b;
 {
-	if source ~ [ RTS_BGP, RTS_STATIC ] then {
-#		ospf_metric1 = 65535;
-#		ospf_metric2 = 1000;
-		ospf_tag = 0x12345678;
-		accept;
+	if a = 3 then {
+		b = 4;
+		bt_assert(defined(b));
+	}
+	else {
+		bt_assert(!defined(b));
 	}
-	reject;
 }
 
-function __test2()
+function t_define()
+int i;
 {
-	if source ~ [ RTS_BGP, RTS_STATIC ] then {
-#		ospf_metric1 = 65535;
-#		ospf_metric2 = 1000;
-		ospf_tag = 0x12345678;
-		accept;
-	}
-	reject;
+	test_undef(2);
+	test_undef(3);
+	test_undef(2);
+
+	bt_assert(defined(1));
+	bt_assert(defined(1.2.3.4));
 }
 
+bt_test_suite(t_define, "Testing defined() function");
 
-function test_pxset(prefix set pxs)
+
+
+
+/*
+ * 	Testing quads
+ * 	-------------
+ */
+
+function t_quad()
+quad qq;
 {
-	print pxs;
-	print "  must be true:  ",	net10  ~ pxs, ",", 10.0.0.0/10  ~ pxs, ",", 10.0.0.0/12 ~ pxs, ",",
-					20.0.0.0/24 ~ pxs, ",", 20.0.40.0/24 ~ pxs, ",", 20.0.0.0/26 ~ pxs, ",",
-					20.0.100.0/26 ~ pxs, ",", 20.0.0.0/28 ~ pxs, ",", 20.0.255.0/28 ~ pxs;
-	print "  must be false: ",	10.0.0.0/7 ~ pxs,  ",", 10.0.0.0/13 ~ pxs, ",", 10.0.0.0/16 ~ pxs, ",",
-					20.0.0.0/16 ~ pxs, ",", 20.0.0.0/23 ~ pxs, ",", 20.0.0.0/29 ~ pxs, ",",
-					11.0.0.0/10 ~ pxs, ",", 20.1.0.0/26 ~ pxs;
+	qq = 1.2.3.4;
+	print "Testinq quad: 1.2.3.4 = ", qq;
+	bt_assert(qq = 1.2.3.4);
+	bt_assert(qq != 4.3.2.1);
 }
 
-function test_undef(int a)
-int b;
+bt_test_suite(t_quad, "Testing quads");
+
+
+
+
+/*
+ * 	Testing sets of quads
+ * 	---------------------
+ */
+
+function t_quad_set()
+quad qq;
 {
-	if a = 3
-	then b = 4;
-	print "Defined: ", a, " ", b, " ", defined(b);
+	qq = 1.2.3.4;
+	bt_assert(qq ~ [1.2.3.4, 5.6.7.8]);
+	bt_assert(qq !~ [1.2.1.1, 1.2.3.5]);
 }
 
-define is1 = [ one, (2+1), (6-one), 8, 11, 15, 17, 19];
-define is2 = [(17+2), 17, 15, 11, 8, 5, 3, 2];
-define is3 = [5, 17, 2, 11, 8, 15, 3, 19];
+bt_test_suite(t_quad_set, "Testing sets of quads");
 
-define pxs2 = [ 10.0.0.0/16{8,12}, 20.0.0.0/16{24,28} ];
+
+
+
+/*
+ * 	Testing Extended Communities
+ * 	----------------------------
+ */
+
+function t_ec()
+ec cc;
+{
+	cc = (rt, 12345, 200000);
+	print "Testing EC: ", cc;
+
+	bt_assert(cc = (rt, 12345, 200000));
+	bt_assert(cc < (rt, 12345, 200010));
+	bt_assert(cc != (rt, 12346, 200000));
+	bt_assert(cc != (ro, 12345, 200000));
+	bt_assert(!(cc > (rt, 12345, 200010)));
+
+	print "Testing EC: (ro, 100000, 20000) = ", (ro, 100000, 20000);
+}
+
+bt_test_suite(t_ec, "Testing Extended Communities");
+
+
+
+
+/*
+ * 	Testing sets of Extended Communities
+ * 	------------------------------------
+ */
 
 define ecs2 = [(rt, ten, (one+onef(0))*10), (ro, 100000, 100..200), (rt, 12345, *)];
 
+function t_ec_set()
+ec set ecs;
+{
+	ecs = [(rt, ten, (one+onef(0))*10), (ro, 100000, 100..200), (rt, 12345, *)];
+	print "EC set (rt, 10, 20) (ro, 100000, 100..200), (rt, 12345, *):";
+	print ecs;
+	print ecs2;
+
+	bt_assert((rt, 10, 20) ~ ecs);
+	bt_assert((ro, 100000, 100) ~ ecs);
+	bt_assert((ro, 100000, 128) ~ ecs);
+	bt_assert((ro, 100000, 200) ~ ecs);
+	bt_assert((rt, 12345, 0) ~ ecs);
+	bt_assert((rt, 12345, 200000) ~ ecs);
+	bt_assert((rt, 12345, 4000000) ~ ecs);
+	bt_assert((ro, 10, 20) !~ ecs);
+	bt_assert((rt, 10, 21) !~ ecs);
+	bt_assert((ro, 100000, 99) !~ ecs);
+	bt_assert((ro, 12345, 10) !~ ecs);
+	bt_assert((rt, 12346, 0) !~ ecs);
+	bt_assert((ro, 0.1.134.160, 150) !~ ecs);
+}
+
+bt_test_suite(t_ec_set, "Testing sets of Extended Communities");
+
+
+
+
+/*
+ *	Testing integers
+ *	----------------
+ */
+
+define four = 4;
+define xyzzy = (120+10);
+define '1a-a1' = (xyzzy-100);
 
-function __startup() 
+function t_int()
 int i;
-bool b;
-prefix px;
-ip p;
-pair pp;
-quad qq;
-ec cc;
+{
+	bt_assert(xyzzy = 130);
+	bt_assert('1a-a1' = 30);
+
+	i = four;
+	i = 12*100 + 60/2 + i;
+	i = (i + 0);
+	bt_assert(i = 1234);
+
+	if (i = 4) then
+		bt_assert(false);
+	else
+		bt_assert(true);
+
+	if !(i = 3) then
+		bt_assert(true);
+	else
+		bt_assert(false);
+
+	if 1234 = i then
+		bt_assert(true);
+	else
+		bt_assert(false);
+
+	if 1 <= 1 then
+		bt_assert(true);
+	else
+		bt_assert(false);
+
+	if 1234 < 1234 then
+		bt_assert(false);
+	else
+		bt_assert(true);
+
+	i = 4200000000;
+	bt_assert(i = 4200000000);
+	bt_assert(i > 4100000000);
+	bt_assert(!(i > 4250000000));
+
+	bt_assert(1 = 1);
+	bt_assert(!(1 != 1));
+
+	bt_assert(1 != 2);
+	bt_assert(1 <= 2);
+
+	bt_assert(1 != "a");
+	bt_assert(1 != (0,1));
+}
+
+bt_test_suite(t_int, "Testing integers");
+
+
+
+
+/*
+ * 	Testing sets of integers
+ * 	------------------------
+ */
+
+define is1 = [ one, (2+1), (6-one), 8, 11, 15, 17, 19];
+define is2 = [(17+2), 17, 15, 11, 8, 5, 3, 2];
+define is3 = [5, 17, 2, 11, 8, 15, 3, 19];
+
+function t_int_set()
 int set is;
-pair set ps;
-ec set ecs;
-ip set ips;
-prefix set pxs;
-string st;
 {
-	print "1a-a1 = 30: ", '1a-a1'; 
-	print "Testing filter language:";
-	i = four; 
-	i = 12*100 + 60/2 + i; 
-	i = ( i + 0 );
-	print "  arithmetics: 1234 = ", i;
-	printn "  if statements ";
-	print "what happens here?";
-	printn ".";
-	if (i = 4) then { print "*** FAIL: if 0"; quitbird; } else printn ".";
-#	if !(i = 3) then { print "*** FAIL: if 0"; quitbird; } else printn ".";
-	if 1234 = i then printn "."; else { print "*** FAIL: if 1 else"; }
-#	if 1 <= 1 then printn "."; else { print "*** FAIL: test 3"; }
-	if 1234 < 1234 then { print "*** FAIL: test 4"; quitbird; } else print "ok";
+	bt_assert(1 ~ [1,2,3]);
+	bt_assert(5 ~ [1..20]);
+	bt_assert(2 ~ [ 1, 2, 3 ]);
+	bt_assert(5 ~ [ 4 .. 7 ]);
+	bt_assert(1 !~ [ 2, 3, 4 ]);
+
 	is = [ 2, 3, 4, 7..11 ];
+	bt_assert(10 ~ is);
+	bt_assert(5 !~ is);
+
+	bt_assert(1 ~ is1);
+	bt_assert(3 ~ is1);
+	bt_assert(5 ~ is1);
+	bt_assert((one+2) ~ is1);
+	bt_assert(2 ~ is2);
+	bt_assert(2 ~ is3);
+	bt_assert(4 !~ is1);
+	bt_assert(4 !~ is2);
+	bt_assert(4 !~ is3);
+	bt_assert(10 !~ is1);
+	bt_assert(10 !~ is2);
+	bt_assert(10 !~ is3);
+	bt_assert(15 ~ is1);
+	bt_assert(15 ~ is2);
+	bt_assert(15 ~ is3);
+	bt_assert(18 !~ is1);
+	bt_assert(18 !~ is2);
+	bt_assert(18 !~ is3);
+	bt_assert(19 ~ is1);
+	bt_assert(19 ~ is2);
+	bt_assert(19 ~ is3);
+	bt_assert(20 !~ is1);
+	bt_assert(20 !~ is2);
+	bt_assert(20 !~ is3);
+
+	bt_assert([1,2] != [1,3]);
+	bt_assert([1,4..10,20] = [1,4..10,20]);
 
-	print "must be true:  ", 1 = 1, " ", 1 != (0,1), " ", 1 != "a", " ", +empty+ = +empty+, " ", -empty- = -empty-, " ", --empty-- = --empty-- ,
-			" ", [1,4..10,20] = [1,4..10,20] , " ", [ 10.0.0.0/8{ 15 , 17 } ] = [ 10.0.0.0/8{ 15 , 17 } ];
-	print "must be false: ", 1 != 1, " ", 1 = (0,1), " ", 1 = "a", " ", +empty+ = -empty-, " ", -empty- = --empty--, " ", --empty-- = +empty+ ,
-			" ", [1,2] = [1,3], " ", [ 10.0.0.0/8{ 15 , 17 } ] = [ 11.0.0.0/8{ 15 , 17 } ];
+	print "What will this do? ", [ 1, 2, 1, 1, 1, 3, 4, 1, 1, 1, 5 ];
+}
 
-	print "  must be true: ", 1.2.0.0/16 ~ [ 1.0.0.0/8{ 15 , 17 } ];
-	print "  data types; must be true: ", 1.2.3.4 = 1.2.3.4, ",", 1 ~ [1,2,3], ",", 5 ~ [1..20], ",", 10 ~ is, ",", 2 ~ [ 1, 2, 3 ], ",", 5 ~ [ 4 .. 7 ], ",", 1.2.3.4 ~ [ 1.2.3.3..1.2.3.5 ], ",", 1.2.3.4 ~ 1.0.0.0/8, ",", 1.0.0.0/8 ~ 1.0.0.0/8, ",", 1.0.0.0/8 ~ [ 1.0.0.0/8+ ];
-	print "  must be true: ", true && true, ",", true || false, ",", ! false && ! false && true, ",", 1 < 2 && 1 != 3, ",", true && true && ! false, ",", true || 1+"a", ",", !(false && 1+"a");
+bt_test_suite(t_int_set, "Testing sets of integers");
 
-	print "  must be true: ", defined(1), ",", defined(1.2.3.4), ",", 1 != 2, ",", 1 <= 2;
-	print "  data types: must be false: ", 1 ~ [ 2, 3, 4 ], ",", 5 ~ is, ",", 1.2.3.4 ~ [ 1.2.3.3, 1.2.3.5 ], ",", (1,2) > (2,2), ",", (1,1) > (1,1), ",", 1.0.0.0/9 ~ [ 1.0.0.0/8- ], ",", 1.2.0.0/17 ~ [ 1.0.0.0/8{ 15 , 16 } ], ",", true && false;
 
 
-	print "  must be true:  ", 1 ~ is1, "  ", 3 ~ is1, "  ", 5 ~ is1;
-	print "  must be true:  ", (one+2) ~ is1, "  ", 2 ~ is2, "  ", 2 ~ is3;
-	print "  must be false: ", 4 ~ is1, " ", 4 ~ is2, " ", 4 ~ is3;
-	print "  must be false: ", 10 ~ is1, " ", 10 ~ is2, " ", 10 ~ is3;
-	print "  must be true:  ", 15 ~ is1, "  ", 15 ~ is2, "  ", 15 ~ is3;
-	print "  must be false: ", 18 ~ is1, " ", 18 ~ is2, " ", 18 ~ is3;
-	print "  must be true:  ", 19 ~ is1, "  ", 19 ~ is2, "  ", 19 ~ is3;
-	print "  must be false: ", 20 ~ is1, " ", 20 ~ is2, " ", 20 ~ is3;
 
-	px = 1.2.0.0/18;
-	print "Testing prefixes: 1.2.0.0/18 = ", px;
-	print "  must be true:  ",	192.168.0.0/16 ~ 192.168.0.0/16, " ", 192.168.0.0/17 ~ 192.168.0.0/16, " ", 192.168.254.0/24 ~ 192.168.0.0/16, " ", netdoc ~ 2001::/16;
-	print "  must be false: ",	192.168.0.0/15 ~ 192.168.0.0/16, " ", 192.160.0.0/17 ~ 192.168.0.0/16, " ", px ~ netdoc;
+/*
+ * 	Testing ip address
+ * 	------------------
+ */
+
+define onetwo = 1.2.3.4;
 
+function t_ip()
+ip p;
+{
 	p = 127.1.2.3;
-	print "Testing mask : 127.0.0.0 = ", p.mask(8);
+	bt_assert(p.mask(8) = 127.0.0.0);
+	bt_assert(1.2.3.4 = 1.2.3.4);
+	bt_assert(1.2.3.4 = onetwo);
+	print "1.2.3.4 = ", onetwo;
+}
+
+bt_test_suite(t_ip, "Testing ip address");
+
+
+
+
+/*
+ * 	Testing sets of ip address
+ * 	--------------------------
+ */
+
+function t_ip_set()
+{
+	bt_assert(1.2.3.4 !~ [ 1.2.3.3, 1.2.3.5 ]);
+	bt_assert(1.2.3.4 ~ [ 1.2.3.3..1.2.3.5 ]);
+}
+
+bt_test_suite(t_ip_set, "Testing sets of ip address");
+
+
 
+
+/*
+ *	Testing enums
+ *	-------------
+ */
+
+function t_enum()
+{
+	print "Testing enums: ", RTS_DUMMY, " ", RTS_STATIC;
+	bt_assert(RTS_STATIC ~ [RTS_STATIC, RTS_DEVICE]);
+	bt_assert(RTS_BGP !~ [RTS_STATIC, RTS_DEVICE]);
+}
+
+bt_test_suite(t_enum, "Testing enums");
+
+
+
+
+/*
+ * 	Testing pairs
+ * 	-------------
+ */
+
+function 'mkpair-a'(int a)
+{
+	return (1, a);
+}
+
+function t_pair()
+pair pp;
+{
 	pp = (1, 2);
-	print "Testing pairs: (1,2) = ", (1,2), " = ", pp, " = ", (1,1+1), " = ", 'mkpair-a'(2);
-	print "  must be true:  ", (1,2) = (1,1+1);
-	print "Testing enums: ", RTS_DUMMY, " ", RTS_STATIC, " ",
-		", true: ", RTS_STATIC ~ [RTS_STATIC, RTS_DEVICE],
-		", false: ", RTS_BGP ~ [RTS_STATIC, RTS_DEVICE];
+	bt_assert((1,2) = pp);
+	bt_assert((1,1+1) = pp);
+	bt_assert('mkpair-a'(2) = pp);
+	bt_assert((1,2) = (1,1+1));
+	bt_assert(((1,2) < (2,2)));
+	bt_assert(!((1,1) > (1,1)));
+}
+
+bt_test_suite(t_pair, "Testing pairs");
+
+
 
+
+/*
+ * 	Testing sets of pairs
+ * 	---------------------
+ */
+
+function t_pair_set()
+pair pp;
+pair set ps;
+{
+	pp = (1, 2);
 	ps = [(1,(one+one)), (3,4)..(4,8), (5,*), (6,3..6)];
 	print "Pair set: ", ps;
-	print "Testing pair set, true:  ", pp ~ ps,  "  ", (3,5) ~ ps, "  ", (4,1) ~ ps, "  ", (5,4) ~ ps, "  ", (5,65535) ~ ps, "  ", (6,4) ~ ps, "  ", (3, 10000) ~ ps;
-	print "Testing pair set, false: ", (3,3) ~ ps, " ", (4,9) ~ ps, " ", (4,65535) ~ ps, " ", (6,2) ~ ps, " ", (6,6+one) ~ ps, " ", ((one+6),2) ~ ps, " ", (1,1) ~ ps;
+	bt_assert(pp ~ ps);
+	bt_assert((3,5) ~ ps);
+	bt_assert((4,1) ~ ps);
+	bt_assert((5,4) ~ ps);
+	bt_assert((5,65535) ~ ps);
+	bt_assert((6,4) ~ ps);
+	bt_assert((3, 10000) ~ ps);
+	bt_assert((3,3) !~ ps);
+	bt_assert((4,9) !~ ps);
+	bt_assert((4,65535) !~ ps);
+	bt_assert((6,2) !~ ps);
+	bt_assert((6,6+one) !~ ps);
+	bt_assert(((one+6),2) !~ ps);
+	bt_assert((1,1) !~ ps);
 
 	ps = [(20..150, 200..300), (50100..50200, 1000..50000), (*, 5+5)];
-	print "Pair set: .. too long ..";
-	print "Testing pair set, true:  ", (100,200) ~ ps,  "  ", (150,300) ~ ps, "  ", (50180,1200) ~ ps, "  ", (50110,49000) ~ ps, "  ", (0,10) ~ ps, "  ", (64000,10) ~ ps;
-	print "Testing pair set, false: ", (20,199) ~ ps, " ", (151,250) ~ ps, " ", (50050,2000) ~ ps, " ", (50150,50050) ~ ps, " ", (10,9) ~ ps, " ", (65535,11) ~ ps ;
+	print "Pair set: ", ps;
+	bt_assert((100,200) ~ ps);
+	bt_assert((150,300) ~ ps);
+	bt_assert((50180,1200) ~ ps);
+	bt_assert((50110,49000) ~ ps);
+	bt_assert((0,10) ~ ps);
+	bt_assert((64000,10) ~ ps);
+	bt_assert((20,199) !~ ps);
+	bt_assert((151,250) !~ ps);
+	bt_assert((50050,2000) !~ ps);
+	bt_assert((50150,50050) !~ ps);
+	bt_assert((10,9) !~ ps);
+	bt_assert((65535,11) !~ ps);
+}
 
-	qq = 1.2.3.4;
-	print "Testinq quad: 1.2.3.4 = ", qq,
-		", true: ", qq = 1.2.3.4, " ", qq ~ [1.2.3.4, 5.6.7.8],
-		", false: ", qq = 4.3.2.1, " ", qq ~ [1.2.1.1, 1.2.3.5];
+bt_test_suite(t_pair_set, "Testing sets of pairs");
 
-	cc = (rt, 12345, 200000);
-	print "Testing EC: (rt, 12345, 200000) = ", cc;
-	print "Testing EC: (ro, 100000, 20000) = ", (ro, 100000, 20000);
-	print "Testing EC: (rt, 10.20.30.40, 20000) = ", (rt, 10.20.30.40, 20000);
-	print "  true: ", cc = (rt, 12345, 200000), " ", cc < (rt, 12345, 200010),
-		", false: ", cc = (rt, 12346, 200000), " ", cc = (ro, 12345, 200000), " ",  cc > (rt, 12345, 200010);
 
-	ecs = [(rt, ten, (one+onef(0))*10), (ro, 100000, 100..200), (rt, 12345, *)];
-	print "EC set: ", ecs;
-	print "EC set: ", ecs2;
-	print "Testing EC set, true:  ",  (rt, 10, 20) ~ ecs, "  ", (ro, 100000, 100) ~ ecs, "  ", (ro, 100000, 200) ~ ecs,
-		"  ", (rt, 12345, 0) ~ ecs, "  ", cc ~ ecs,  "  ", (rt, 12345, 4000000) ~ ecs;
-	print "Testing EC set, false: ", (ro, 10, 20) ~ ecs, " ", (rt, 10, 21) ~ ecs, " ", (ro, 100000, 99) ~ ecs,
-		" ", (ro, 12345, 10) ~ ecs, " ", (rt, 12346, 0) ~ ecs, " ", (ro, 0.1.134.160, 150) ~ ecs;
 
+
+/*
+ * 	Testing string matching
+ * 	-----------------------
+ */
+
+function t_string()
+string st;
+{
 	st = "Hello";
-	print "Testing string: ", st, " true: ", st ~ "Hell*", " false: ", st ~ "ell*";
-	
+	print "Testing string: ", st;
+	bt_assert(st ~ "Hell*");
+	bt_assert(st ~ "?ello");
+	bt_assert(st ~ "Hello");
+	bt_assert(st ~ "Hell?");
+	bt_assert(st !~ "ell*");
+}
+
+bt_test_suite(t_string, "Testing string matching");
+
+
+
+
+/*
+ * 	Testing boolean expressions
+ * 	---------------------------
+ */
+
+function t_bool()
+bool b;
+{
 	b = true;
-	print "Testing bool: ", b, ", ", !b;
+	bt_assert(b);
+	bt_assert(!!b);
+
+	if ( b = true ) then
+		bt_assert(b);
+	else
+		bt_assert(false);
+
+	bt_assert(true && true);
+	bt_assert(true || false);
+	bt_assert(! false && ! false && true);
+	bt_assert(1 < 2 && 1 != 3);
+	bt_assert(true && true && ! false);
+	bt_assert(true || 1+"a");
+	bt_assert(!(false && 1+"a"));
+	bt_assert(!(true && false));
+}
 
-	if ( b = true ) then print "Testing bool comparison b = true: ", b;
-	else { print "*** FAIL: TRUE test failed" ; quitbird; }
-	
-	ips = [ 1.1.1.0 .. 1.1.1.255, ip1222];
-	print "Testing IP sets: ";
-	print ips;
-	print "  must be true:  ",	1.1.1.0 ~ ips, ",", 1.1.1.100 ~ ips, ",", 1.2.2.2 ~ ips;
-	print "  must be false: ",	1.1.0.255 ~ ips, ",", 1.1.2.0  ~ ips, ",", 1.2.2.3 ~ ips, ",", 192.168.1.1 ~ ips;
+bt_test_suite(t_bool, "Testing boolean expressions");
 
-	pxs = [ 1.2.0.0/16, 1.4.0.0/16+];
-	print "Testing prefix sets: ";
+
+
+
+/*
+ * 	Testing prefixes
+ * 	----------------
+ */
+
+define netdoc = 2001:db8::/32;
+
+function t_prefix()
+prefix px;
+{
+	px = 1.2.0.0/18;
+	print "Testing prefixes: 1.2.0.0/18 = ", px;
+	bt_assert(192.168.0.0/16 ~ 192.168.0.0/16);
+	bt_assert(192.168.0.0/17 ~ 192.168.0.0/16);
+	bt_assert(192.168.254.0/24 ~ 192.168.0.0/16);
+	bt_assert(netdoc ~ 2001::/16);
+	bt_assert(192.168.0.0/15 !~ 192.168.0.0/16);
+	bt_assert(192.160.0.0/17 !~ 192.168.0.0/16);
+	bt_assert(px !~ netdoc);
+
+	bt_assert(1.2.3.4 ~ 1.0.0.0/8);
+	bt_assert(1.0.0.0/8 ~ 1.0.0.0/8);
+}
+
+bt_test_suite(t_prefix, "Testing prefixes");
+
+
+
+
+/*
+ *	Testing prefix sets
+ *	-------------------
+ */
+
+define net10 = 10.0.0.0/8;
+define pxs2 = [ 10.0.0.0/16{8,12}, 20.0.0.0/16{24,28} ];
+
+function test_pxset(prefix set pxs)
+{
 	print pxs;
-	print "  must be true:  ",	1.2.0.0/16 ~ pxs, ",", 1.4.0.0/16 ~ pxs, ",", 1.4.0.0/18 ~ pxs, ",", 1.4.0.0/32 ~ pxs;
-	print "  must be false: ",	1.1.0.0/16 ~ pxs, ",", 1.3.0.0/16 ~ pxs, ",", 1.2.0.0/15 ~ pxs, ",", 1.2.0.0/17 ~ pxs, ",",
-					1.2.0.0/32 ~ pxs, ",", 1.4.0.0/15 ~ pxs;
+
+	bt_assert(net10  ~ pxs);
+	bt_assert(10.0.0.0/10  ~ pxs);
+	bt_assert(10.0.0.0/12 ~ pxs);
+	bt_assert(20.0.0.0/24 ~ pxs);
+	bt_assert(20.0.40.0/24 ~ pxs);
+	bt_assert(20.0.0.0/26 ~ pxs);
+	bt_assert(20.0.100.0/26 ~ pxs);
+	bt_assert(20.0.0.0/28 ~ pxs);
+	bt_assert(20.0.255.0/28 ~ pxs);
+
+	bt_assert(10.0.0.0/7 !~ pxs);
+	bt_assert(10.0.0.0/13 !~ pxs);
+	bt_assert(10.0.0.0/16 !~ pxs);
+	bt_assert(20.0.0.0/16 !~ pxs);
+	bt_assert(20.0.0.0/23 !~ pxs);
+	bt_assert(20.0.0.0/29 !~ pxs);
+	bt_assert(11.0.0.0/10 !~ pxs);
+	bt_assert(20.1.0.0/26 !~ pxs);
+
+	bt_assert(1.0.0.0/8 ~ [ 1.0.0.0/8+ ]);
+	bt_assert(1.0.0.0/9 !~ [ 1.0.0.0/8- ]);
+	bt_assert(1.2.0.0/17 !~ [ 1.0.0.0/8{ 15 , 16 } ]);
+
+	bt_assert([ 10.0.0.0/8{ 15 , 17 } ] = [ 10.0.0.0/8{ 15 , 17 } ]);
+}
+
+function t_prefix_sets()
+prefix set pxs;
+{
+	pxs = [ 1.2.0.0/16, 1.4.0.0/16+];
+	print "Testing prefix sets: ", pxs;
+	bt_assert(1.2.0.0/16 ~ pxs);
+	bt_assert(1.4.0.0/16 ~ pxs);
+	bt_assert(1.4.0.0/18 ~ pxs);
+	bt_assert(1.4.0.0/32 ~ pxs);
+	bt_assert(1.1.0.0/16 !~ pxs);
+	bt_assert(1.3.0.0/16 !~ pxs);
+	bt_assert(1.2.0.0/15 !~ pxs);
+	bt_assert(1.2.0.0/17 !~ pxs);
+	bt_assert(1.2.0.0/32 !~ pxs);
+	bt_assert(1.4.0.0/15 !~ pxs);
 
 	test_pxset(pxs2);
 	test_pxset([ 10.0.0.0/16{8,12}, 20.0.0.0/16{24,28} ]);
-	print "What will this do? ", [ 1, 2, 1, 1, 1, 3, 4, 1, 1, 1, 5 ];
 
-	print "Testing functions...";
-	callme ( 1, 2 );
-	callme ( 2, 2 );
-	callme ( 2, 2 );
-	callme ( 3, 2 );
-	callme ( 4, 4 );
-	callme ( 7, 2 );
+	bt_assert(1.2.0.0/16 ~ [ 1.0.0.0/8{ 15 , 17 } ]);
+	bt_assert([ 10.0.0.0/8{ 15 , 17 } ] != [ 11.0.0.0/8{ 15 , 17 } ]);
+}
 
-	i = fifteen();
-	print "Testing function calls: 15 = ", i;
+bt_test_suite(t_prefix_sets, "Testing prefix sets");
 
-	path_test();
 
-	print "1.2.3.4 = ", onetwo;
 
-	i = 4200000000;
-	print "4200000000 = ", i, "    true: ", i = 4200000000, " ", i > 4100000000, "   false: ", i > 4250000000;
 
-	test_undef(2);
-	test_undef(3);
-	test_undef(2);
+/*
+ * 	Testing IP sets
+ * 	---------------
+ */
 
-	print "Testing include";
-	include "test.conf.inc";
+define ip1222 = 1.2.2.2;
 
-	print "done";
-	quitbird;
-#	print "*** FAIL: this is unreachable"; 
+function t_ip_sets()
+ip set ips;
+{
+	ips = [ 1.1.1.0 .. 1.1.1.255, ip1222];
+	print "Testing IP sets: ", ips;
+	bt_assert(1.1.1.0 ~ ips);
+	bt_assert(1.1.1.100 ~ ips);
+	bt_assert(1.2.2.2 ~ ips);
+	bt_assert(1.1.0.255 !~ ips);
+	bt_assert(1.1.2.0  !~ ips);
+	bt_assert(1.2.2.3 !~ ips);
+	bt_assert(192.168.1.1 !~ ips);
 }
 
-filter testf 
-int j; 
-{ 
+bt_test_suite(t_ip_sets, "Testing IP sets");
+
+
+
+
+/*
+ *	 Testing calling functions
+ *	 -------------------------
+ */
+
+function callme(int arg1; int arg2)
+int i;
+{
+	case arg1 {
+	1, 42: return 42;
+	else: return arg1 * arg2;
+	}
+
+	return 0;
+}
+
+function fifteen()
+{
+	return 15;
+}
+
+function t_call_function()
+{
+	bt_assert(fifteen() = 15);
+
+	bt_assert(callme(1, 2) = 42);
+	bt_assert(callme(42, 2) = 42);
+
+	bt_assert(callme(2, 2) = 4);
+	bt_assert(callme(3, 2) = 6);
+	bt_assert(callme(4, 4) = 16);
+	bt_assert(callme(7, 2) = 14);
+}
+
+bt_test_suite(t_call_function, "Testing calling functions");
+
+
+
+
+/*
+ * 	Test including another config file
+ * 	----------------------------------
+ */
+
+function t_include()
+int i;
+{
+  print "Testing include";
+  i = 1;
+  include "test.conf.inc";
+  bt_assert(i = 42);
+}
+
+bt_test_suite(t_include, "Test including another config file");
+
+
+
+
+/*
+ *	Unused functions -- testing only parsing
+ *	----------------------------------------
+ */
+
+function __test1()
+{
+	if source ~ [ RTS_BGP, RTS_STATIC ] then {
+#		ospf_metric1 = 65535;
+#		ospf_metric2 = 1000;
+		ospf_tag = 0x12345678;
+		accept;
+	}
+	reject;
+}
+
+function __test2()
+{
+	if source ~ [ RTS_BGP, RTS_STATIC ] then {
+#		ospf_metric1 = 65535;
+#		ospf_metric2 = 1000;
+		ospf_tag = 0x12345678;
+		accept;
+	}
+	reject;
+}
+
+filter testf
+int j;
+{
 	print "Heya, filtering route to ", net.ip, " prefixlen ", net.len, " source ", source;
 	print "This route was from ", from;
 	j = 7;
@@ -472,8 +933,34 @@ int j;
 	}
 	rip_metric = 14;
 	unset(rip_metric);
-		
+
 	accept "ok I take that";
 }
 
-eval __startup();
+/*
+roa table rl
+{
+	roa 10.110.0.0/16 max 16 as 1000;
+	roa 10.120.0.0/16 max 24 as 1000;
+	roa 10.130.0.0/16 max 24 as 2000;
+	roa 10.130.128.0/18 max 24 as 3000;
+}
+
+function test_roa()
+{
+	# cannot be tested in __startup(), sorry
+	print "Testing ROA";
+	print "Should be true: ", roa_check(rl, 10.10.0.0/16, 1000) = ROA_UNKNOWN,
+	      " ", roa_check(rl, 10.0.0.0/8, 1000) = ROA_UNKNOWN,
+	      " ", roa_check(rl, 10.110.0.0/16, 1000) = ROA_VALID,
+	      " ", roa_check(rl, 10.110.0.0/16, 2000) = ROA_INVALID,
+	      " ", roa_check(rl, 10.110.32.0/20, 1000) = ROA_INVALID,
+	      " ", roa_check(rl, 10.120.32.0/20, 1000) = ROA_VALID;
+	print "Should be true: ", roa_check(rl, 10.120.32.0/20, 2000) = ROA_INVALID,
+	      " ", roa_check(rl, 10.120.32.32/28, 1000) = ROA_INVALID,
+	      " ", roa_check(rl, 10.130.130.0/24, 1000) = ROA_INVALID,
+	      " ", roa_check(rl, 10.130.130.0/24, 2000) = ROA_VALID,
+	      " ", roa_check(rl, 10.130.30.0/24, 3000) = ROA_INVALID,
+	      " ", roa_check(rl, 10.130.130.0/24, 3000) = ROA_VALID;
+}
+*/
\ No newline at end of file
diff --git a/filter/test.conf.inc b/filter/test.conf.inc
index 109a49c5..7707ae38 100644
--- a/filter/test.conf.inc
+++ b/filter/test.conf.inc
@@ -2,4 +2,5 @@
 print "Entering include";
 print "Should be 2:  ", 1+1;
 print "Leaving include";
+i = 42;
 
diff --git a/filter/test.conf2 b/filter/test.conf2
index 60bdd965..2a5d896b 100644
--- a/filter/test.conf2
+++ b/filter/test.conf2
@@ -18,6 +18,7 @@ protocol direct {
 
 protocol kernel {
 	disabled;
+	ipv4;			# Must be specified at least one channel
 #	learn;			# Learn all routes from the kernel
 #	scan time 10;		# Scan kernel tables every 10 seconds
 }
@@ -25,51 +26,58 @@ protocol kernel {
 protocol static {
 #	disabled;
 
-	import filter { print "ahoj"; 
-	print source;
-	if source = RTS_STATIC then {
-		print "It is from static";
-	}
-	print from;
-	from = 1.2.3.4;
-	print from;
-	print scope;
-	scope = SCOPE_HOST;
-	print scope;
-	if !(scope ~ [ SCOPE_HOST, SCOPE_SITE ]) then {
-		print "Failed in test";
-		quitbird;
-	}
-		
-	preference = 15;
-	print preference;
-	preference = 29;
-	print preference;
-	rip_metric = 1;
-	print rip_metric;
-	rip_metric = rip_metric + 5;
-	print rip_metric;
-	bgp_community = - empty - ; 
-	print "nazdar";
-	bgp_community = add(bgp_community, (1,2));
-	print "cau";
-	bgp_community = add(bgp_community, (2,3));
-	bgp_community.add((4,5));
-	print "community = ", bgp_community;
-	bgp_community.delete((2,3));
-	print "community = ", bgp_community;
-	bgp_community.empty;
-	print "community = ", bgp_community;
-	print "done";
-	};
+	ipv4 {
+		export all;
+
+		import filter {
+			print "ahoj";
+			print source;
+			if source = RTS_STATIC then {
+				print "It is from static";
+			}
+			print from;
+			from = 1.2.3.4;
+			print from;
+			print scope;
+			scope = SCOPE_HOST;
+			print scope;
+			if !(scope ~ [ SCOPE_HOST, SCOPE_SITE ]) then {
+				print "Failed in test";
+				quitbird;
+			}
 
+			preference = 15;
+			print preference;
+			preference = 29;
+			print preference;
+			rip_metric = 1;
+			print rip_metric;
+			rip_metric = rip_metric + 5;
+			print rip_metric;
+
+#
+# TODO: uncomment this part after finishing BGP integration version
+#
+#			bgp_community = -empty-;
+#			print "hi";
+#			bgp_community = add(bgp_community, (1,2));
+#			print "hello";
+#			bgp_community = add(bgp_community, (2,3));
+#			bgp_community.add((4,5));
+#			print "community = ", bgp_community;
+#			bgp_community.delete((2,3));
+#			print "community = ", bgp_community;
+#			bgp_community.empty;
+#			print "community = ", bgp_community;
+#			print "done";
+		};
+	};
 	route 0.0.0.0/0 via 195.113.31.113;
 	route 62.168.0.0/25 reject;
 	route 1.2.3.4/32 via 195.113.31.124;
-#	route 10.0.0.0/8 reject;
-#	route 10.1.1.0:255.255.255.0 via 62.168.0.3;
-#	route 10.1.2.0:255.255.255.0 via 62.168.0.3;
-#	route 10.1.3.0:255.255.255.0 via 62.168.0.4;
-#	route 10.2.0.0/24 via "arc0";
-	export all;
+	route 10.0.0.0/8 reject;
+	route 10.1.1.0:255.255.255.0 via 62.168.0.3;
+	route 10.1.2.0:255.255.255.0 via 62.168.0.3;
+	route 10.1.3.0:255.255.255.0 via 62.168.0.4;
+	route 10.2.0.0/24 via "arc0";
 }
diff --git a/filter/test6.conf b/filter/test6.conf
index f25ffc47..fb82cf6b 100644
--- a/filter/test6.conf
+++ b/filter/test6.conf
@@ -9,6 +9,8 @@ router id 62.168.0.1;
 
 define xyzzy = (120+10);
 
+protocol device {}
+
 function callme(int arg1; int arg2)
 int local1;
 int local2;
@@ -30,7 +32,7 @@ function fifteen()
 	return 15;
 }
 
-function paths()
+function _paths()
 bgpmask pm1;
 bgpmask pm2;
 bgppath p2;
@@ -97,7 +99,7 @@ ip p;
 pair pp;
 int set is;
 prefix set pxs;
-string s;
+string str;
 { 
 	print "Testing filter language:";
 	i = four; 
@@ -129,8 +131,8 @@ string s;
 	print "Testing pairs: (1,2) = ", (1,2), " = ", pp;
 	print "Testing enums: ", RTS_DUMMY, " ", RTS_STATIC;
 
-	s = "Hello";
-	print "Testing string: ", s, " true: ", s ~ "Hell*", " false: ", s ~ "ell*";
+	str = "Hello";
+	print "Testing string: ", str, " true: ", str ~ "Hell*", " false: ", str ~ "ell*";
 	
 	b = true;
 	print "Testing bool: ", b, ", ", !b;
@@ -156,11 +158,12 @@ string s;
 	i = fifteen();
 	print "Testing function calls: 15 = ", i;
 
-	paths();
+	_paths();
 
 	print "done";
-	quitbird;
-#	print "*** FAIL: this is unreachable"; 
+	return 0;
+	print "*** FAIL: this is unreachable";
+	quitbird;  # quit with err exit code 1
 }
 
 filter testf 
diff --git a/filter/test_bgp_filtering.conf b/filter/test_bgp_filtering.conf
new file mode 100644
index 00000000..573cad46
--- /dev/null
+++ b/filter/test_bgp_filtering.conf
@@ -0,0 +1,113 @@
+router id 62.168.0.1;
+
+function net_martian()
+{
+  return net ~ [ 169.254.0.0/16+, 172.16.0.0/12+, 192.168.0.0/16+, 10.0.0.0/8+, 
+    127.0.0.0/8+, 224.0.0.0/4+, 240.0.0.0/4+, 0.0.0.0/32-, 0.0.0.0/0{25,32}, 0.0.0.0/0{0,7} ];
+}
+
+function net_local()
+{
+  return net ~ [ 12.10.0.0/16+, 34.10.0.0/16+ ];
+}
+
+function rt_import(int asn; int set peer_asns; prefix set peer_nets)
+{
+  if ! (net ~ peer_nets) then return false;
+  if ! (bgp_path.last ~ peer_asns) then return false;
+  if bgp_path.first != asn then return false;
+  if bgp_path.len > 64 then return false;
+  if bgp_next_hop != from then return false;
+  return true;
+}
+
+function rt_import_all(int asn)
+{
+  if net_martian() || net_local() then return false;
+  if bgp_path.first != asn then return false;
+  if bgp_path.len > 64 then return false;
+  if bgp_next_hop != from then return false;
+  return true;
+}
+
+function rt_import_rs(int asn)
+{
+  if net_martian() || net_local() then return false;
+  if bgp_path.len > 64 then return false;
+  return true;
+}
+
+function rt_export()
+{
+  if proto = "static_bgp" then return true;
+  if source != RTS_BGP then return false;
+  if net_martian() then return false;
+  if bgp_path.len > 64 then return false;
+  # return bgp_next_hop ~ [ 100.1.1.1, 100.1.1.2, 200.1.1.1 ];
+  return bgp_path.first ~ [ 345, 346 ];
+}
+
+
+function rt_export_all()
+{
+  if proto = "static_bgp" then return true;
+  if source != RTS_BGP then return false;
+  if net_martian() then return false;
+  if bgp_path.len > 64 then return false;
+  return true;
+}
+
+filter bgp_in_uplink_123
+{
+  if ! rt_import_all(123) then reject;
+  accept;
+}
+
+filter bgp_out_uplink_123
+{
+  if ! rt_export() then reject;
+  accept;
+}
+
+
+filter bgp_in_peer_234
+{
+  if ! rt_import(234, [ 234, 1234, 2345, 3456 ],
+        [ 12.34.0.0/16, 23.34.0.0/16, 34.56.0.0/16 ])
+  then reject;
+  accept;
+}
+
+filter bgp_out_peer_234
+{
+  if ! rt_export() then reject;
+  accept;
+}
+
+filter bgp_in_rs
+{
+  if ! rt_import_rs(bgp_path.last) then reject;
+  accept;
+}
+
+filter bgp_out_rs
+{
+  if ! rt_export() then reject;
+  accept;
+}
+
+
+filter bgp_in_client_345
+{
+  if ! rt_import(345, [ 345 ], [ 34.5.0.0/16 ]) then reject;
+  accept;
+}
+
+filter bgp_out_client_345
+{
+  if ! rt_export_all() then reject;
+  accept;
+}
+
+
+
diff --git a/filter/tree_test.c b/filter/tree_test.c
new file mode 100644
index 00000000..abe955d0
--- /dev/null
+++ b/filter/tree_test.c
@@ -0,0 +1,304 @@
+/*
+ *	Filters: Utility Functions Tests
+ *
+ *	(c) 2015 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include "test/birdtest.h"
+#include "test/bt-utils.h"
+
+#include "filter/filter.h"
+#include "conf/conf.h"
+
+#define MAX_TREE_HEIGHT 13
+
+static void
+start_conf_env(void)
+{
+  bt_bird_init();
+
+  pool *p = rp_new(&root_pool, "helper_pool");
+  linpool *l = lp_new(p, 4080);
+  cfg_mem = l;
+}
+
+static struct f_tree *
+new_tree(uint id)
+{
+  struct f_tree *tree = f_new_tree();
+  tree->from.type  = tree->to.type  = T_INT;
+  tree->from.val.i = tree->to.val.i = id;
+
+  return tree;
+}
+
+/*
+ * Show subtree in infix notation
+ */
+static void
+show_subtree(struct f_tree *node)
+{
+  if (!node)
+    return;
+
+  show_subtree(node->left);
+
+  if (node->from.val.i == node->to.val.i)
+    bt_debug("%u ", node->from.val.i);
+  else
+    bt_debug("%u..%u ", node->from.val.i, node->to.val.i);
+
+  show_subtree(node->right);
+}
+
+static void
+show_tree2(struct f_tree *root_node, const char *tree_name)
+{
+  bt_debug("%s: \n", tree_name);
+  bt_debug("[ ");
+  show_subtree(root_node);
+  bt_debug("]\n\n");
+}
+
+#define show_tree(tree) show_tree2(tree, #tree);
+
+static uint
+get_nodes_count_full_bin_tree(uint height)
+{
+  return (bt_naive_pow(2, height+1) - 1);
+}
+
+static struct f_tree *
+get_balanced_full_subtree(uint height, uint idx)
+{
+  struct f_tree *node = new_tree(idx);
+  if (height > 0)
+  {
+    uint nodes_in_subtree = get_nodes_count_full_bin_tree(--height);
+    node->left  = get_balanced_full_subtree(height, idx - nodes_in_subtree/2 - 1);
+    node->right = get_balanced_full_subtree(height, idx + nodes_in_subtree/2 + 1);
+  }
+  return node;
+}
+
+static struct f_tree *
+get_balanced_full_tree(uint height)
+{
+  return get_balanced_full_subtree(height, get_nodes_count_full_bin_tree(height)/2);
+}
+
+static struct f_tree *
+get_degenerated_left_tree(uint nodes_count)
+{
+  struct f_tree *old = NULL;
+  struct f_tree *new = NULL;
+  uint i;
+
+  for (i = 0; i < nodes_count; i++)
+  {
+    old = new;
+    new = new_tree(nodes_count-1-i);
+    new->left = old;
+  }
+
+  return new;
+}
+
+static struct f_tree *
+get_random_degenerated_left_tree(uint nodes_count)
+{
+  struct f_tree *tree = get_degenerated_left_tree(nodes_count);
+
+  size_t avaible_indexes_size = nodes_count * sizeof(byte);
+  byte *avaible_indexes = malloc(avaible_indexes_size);
+  memset(avaible_indexes, 0, avaible_indexes_size);
+
+  struct f_tree *n;
+  for (n = tree; n; n = n->left)
+  {
+    uint selected_idx;
+    do
+    {
+      selected_idx = bt_random() % nodes_count;
+    } while(avaible_indexes[selected_idx] != 0);
+
+    avaible_indexes[selected_idx] = 1;
+    n->from.type  = n->to.type  = T_INT;
+    n->from.val.i = n->to.val.i = selected_idx;
+  }
+
+  free(avaible_indexes);
+  return tree;
+}
+
+static struct f_tree *
+get_balanced_tree_with_ranged_values(uint nodes_count)
+{
+  struct f_tree *tree = get_degenerated_left_tree(nodes_count);
+
+  uint idx = 0;
+  struct f_tree *n;
+  for (n = tree; n; n = n->left)
+  {
+    n->from.type = n->to.type = T_INT;
+    n->from.val.i = idx;
+    idx += (uint)bt_random() / nodes_count;	/* (... / nodes_count) preventing overflow an uint idx */
+    n->to.val.i = idx++;
+  }
+
+  return build_tree(tree);
+}
+
+
+static int
+t_balancing(void)
+{
+  start_conf_env();
+
+  uint height;
+  for (height = 1; height < MAX_TREE_HEIGHT; height++)
+  {
+    uint nodes_count = get_nodes_count_full_bin_tree(height);
+
+    struct f_tree *simple_degenerated_tree = get_degenerated_left_tree(nodes_count);
+    show_tree(simple_degenerated_tree);
+
+    struct f_tree *expected_balanced_tree = get_balanced_full_tree(height);
+    show_tree(expected_balanced_tree);
+
+    struct f_tree *balanced_tree_from_simple = build_tree(simple_degenerated_tree);
+    show_tree(balanced_tree_from_simple);
+
+    bt_assert(same_tree(balanced_tree_from_simple, expected_balanced_tree));
+  }
+
+  return BT_SUCCESS;
+}
+
+
+static int
+t_balancing_random(void)
+{
+  start_conf_env();
+
+  uint height;
+  for (height = 1; height < MAX_TREE_HEIGHT; height++)
+  {
+    uint nodes_count = get_nodes_count_full_bin_tree(height);
+
+    struct f_tree *expected_balanced_tree = get_balanced_full_tree(height);
+
+    uint i;
+    for(i = 0; i < 10; i++)
+    {
+      struct f_tree *random_degenerated_tree = get_random_degenerated_left_tree(nodes_count);
+      show_tree(random_degenerated_tree);
+
+      struct f_tree *balanced_tree_from_random = build_tree(random_degenerated_tree);
+
+      show_tree(expected_balanced_tree);
+      show_tree(balanced_tree_from_random);
+
+      bt_assert(same_tree(balanced_tree_from_random, expected_balanced_tree));
+    }
+  }
+
+  return BT_SUCCESS;
+}
+
+static int
+t_find(void)
+{
+  start_conf_env();
+
+  uint height;
+  for (height = 1; height < MAX_TREE_HEIGHT; height++)
+  {
+    uint nodes_count = get_nodes_count_full_bin_tree(height);
+
+    struct f_tree *tree = get_balanced_full_tree(height);
+    show_tree(tree);
+
+    struct f_val looking_up_value = {
+	.type = T_INT
+    };
+    for(looking_up_value.val.i = 0; looking_up_value.val.i < nodes_count; looking_up_value.val.i++)
+    {
+      struct f_tree *found_tree = find_tree(tree, looking_up_value);
+      bt_assert((val_compare(looking_up_value, found_tree->from) == 0) && (val_compare(looking_up_value, found_tree->to) == 0));
+    }
+  }
+
+  return BT_SUCCESS;
+}
+
+static uint
+get_max_value_in_unbalanced_tree(struct f_tree *node, uint max)
+{
+  if (!node)
+    return max;
+
+  if (node->to.val.i > max)
+    max = node->to.val.i;
+
+  uint max_left  = get_max_value_in_unbalanced_tree(node->left, max);
+  if (max_left > max)
+    max = max_left;
+
+  uint max_right = get_max_value_in_unbalanced_tree(node->right, max);
+  if (max_right > max)
+    max = max_right;
+
+  return max;
+}
+
+static int
+t_find_ranges(void)
+{
+  start_conf_env();
+
+  uint height;
+  for (height = 1; height < MAX_TREE_HEIGHT; height++)
+  {
+    uint nodes_count = get_nodes_count_full_bin_tree(height);
+
+    struct f_tree *tree = get_balanced_tree_with_ranged_values(nodes_count);
+    uint max_value = get_max_value_in_unbalanced_tree(tree, 0);
+
+    show_tree(tree);
+
+    bt_debug("max_value: %u \n", max_value);
+
+    struct f_val needle = {
+	.type = T_INT
+    };
+    uint *i = &needle.val.i;
+
+    for(*i = 0; *i <= max_value; *i += (uint)bt_random()/nodes_count)
+    {
+      struct f_tree *found_tree = find_tree(tree, needle);
+      bt_debug("searching: %u \n", *i);
+      bt_assert(
+	  (val_compare(needle, found_tree->from) == 0) || (val_compare(needle, found_tree->to) == 0) ||
+	 ((val_compare(needle, found_tree->from) == 1) && (val_compare(needle, found_tree->to) == -1))
+      );
+    }
+  }
+
+  return BT_SUCCESS;
+}
+
+int
+main(int argc, char *argv[])
+{
+  bt_init(argc, argv);
+
+  bt_test_suite(t_balancing, "Balancing strong unbalanced trees");
+  bt_test_suite(t_balancing_random, "Balancing random unbalanced trees");
+  bt_test_suite(t_find, "Finding values in trees");
+  bt_test_suite(t_find_ranges, "Finding values in trees with random ranged values");
+
+  return bt_exit_value();
+}
diff --git a/filter/trie_test.c b/filter/trie_test.c
new file mode 100644
index 00000000..c528c7d9
--- /dev/null
+++ b/filter/trie_test.c
@@ -0,0 +1,184 @@
+/*
+ *	Filters: Utility Functions Tests
+ *
+ *	(c) 2015 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include "test/birdtest.h"
+#include "test/bt-utils.h"
+
+#include "filter/filter.h"
+#include "conf/conf.h"
+
+#define TESTS_NUM		10
+#define PREFIXES_NUM 		10
+#define PREFIX_TESTS_NUM 	10000
+
+#define BIG_BUFFER_SIZE		10000
+
+/* Wrapping structure for storing f_prefixes structures in list */
+struct f_prefix_node {
+  node n;
+  struct f_prefix prefix;
+};
+
+static u32
+xrandom(u32 max)
+{
+  return (bt_random() % max);
+}
+
+static int
+is_prefix_included(list *prefixes, struct f_prefix *needle)
+{
+  struct f_prefix_node *n;
+  WALK_LIST(n, *prefixes)
+  {
+    ip6_addr cmask = ip6_mkmask(MIN(n->prefix.net.pxlen, needle->net.pxlen));
+
+    ip6_addr ip = net6_prefix(&n->prefix.net);
+    ip6_addr needle_ip = net6_prefix(&needle->net);
+
+    if ((ipa_compare(ipa_and(ip, cmask), ipa_and(needle_ip, cmask)) == 0) &&
+	(n->prefix.lo <= needle->net.pxlen) && (needle->net.pxlen <= n->prefix.hi))
+    {
+      bt_debug("FOUND\t" PRIip6 "/%d %d-%d\n", ARGip6(net6_prefix(&n->prefix.net)), n->prefix.net.pxlen, n->prefix.lo, n->prefix.hi);
+      return 1; /* OK */
+    }
+  }
+  return 0; /* FAIL */
+}
+
+static struct f_prefix
+get_random_ip6_prefix(void)
+{
+  struct f_prefix p;
+  u8 pxlen = xrandom(120)+8;
+  ip6_addr ip6 = ip6_build(bt_random(),bt_random(),bt_random(),bt_random());
+  net_addr_ip6 net6 = NET_ADDR_IP6(ip6, pxlen);
+
+  p.net = *((net_addr*) &net6);
+
+  if (bt_random() % 2)
+  {
+    p.lo = 0;
+    p.hi = p.net.pxlen;
+  }
+  else
+  {
+    p.lo = p.net.pxlen;
+    p.hi = net_max_prefix_length[p.net.type];
+  }
+
+  return p;
+}
+
+static void
+generate_random_ipv6_prefixes(list *prefixes)
+{
+  int i;
+  for (i = 0; i < PREFIXES_NUM; i++)
+  {
+    struct f_prefix f = get_random_ip6_prefix();
+
+    struct f_prefix_node *px = calloc(1, sizeof(struct f_prefix_node));
+    px->prefix = f;
+
+    bt_debug("ADD\t" PRIip6 "/%d %d-%d\n", ARGip6(net6_prefix(&px->prefix.net)), px->prefix.net.pxlen, px->prefix.lo, px->prefix.hi);
+    add_tail(prefixes, &px->n);
+  }
+}
+
+static int
+t_match_net(void)
+{
+  bt_bird_init();
+  bt_config_parse(BT_CONFIG_SIMPLE);
+
+  uint round;
+  for (round = 0; round < TESTS_NUM; round++)
+  {
+    list prefixes; /* of structs f_extended_prefix */
+    init_list(&prefixes);
+    struct f_trie *trie = f_new_trie(config->mem, sizeof(struct f_trie_node));
+
+    generate_random_ipv6_prefixes(&prefixes);
+    struct f_prefix_node *n;
+    WALK_LIST(n, prefixes)
+    {
+      trie_add_prefix(trie, &n->prefix.net, n->prefix.lo, n->prefix.hi);
+    }
+
+    int i;
+    for (i = 0; i < PREFIX_TESTS_NUM; i++)
+    {
+      struct f_prefix f = get_random_ip6_prefix();
+      bt_debug("TEST\t" PRIip6 "/%d\n", ARGip6(net6_prefix(&f.net)), f.net.pxlen);
+
+      int should_be = is_prefix_included(&prefixes, &f);
+      int is_there  = trie_match_net(trie, &f.net);
+      bt_assert_msg(should_be == is_there, "Prefix " PRIip6 "/%d %s", ARGip6(net6_prefix(&f.net)), f.net.pxlen, (should_be ? "should be found in trie" : "should not be found in trie"));
+    }
+
+    struct f_prefix_node *nxt;
+    WALK_LIST_DELSAFE(n, nxt, prefixes)
+    {
+      free(n);
+    }
+  }
+
+  return BT_SUCCESS;
+}
+
+static int
+t_trie_same(void)
+{
+  bt_bird_init();
+  bt_config_parse(BT_CONFIG_SIMPLE);
+
+  int round;
+  for (round = 0; round < TESTS_NUM*4; round++)
+  {
+    struct f_trie * trie1 = f_new_trie(config->mem, sizeof(struct f_trie_node));
+    struct f_trie * trie2 = f_new_trie(config->mem, sizeof(struct f_trie_node));
+
+    list prefixes; /* a list of f_extended_prefix structures */
+    init_list(&prefixes);
+    int i;
+    for (i = 0; i < 100; i++)
+      generate_random_ipv6_prefixes(&prefixes);
+
+    struct f_prefix_node *n;
+    WALK_LIST(n, prefixes)
+    {
+      trie_add_prefix(trie1, &n->prefix.net, n->prefix.lo, n->prefix.hi);
+    }
+    WALK_LIST_BACKWARDS(n, prefixes)
+    {
+      trie_add_prefix(trie2, &n->prefix.net, n->prefix.lo, n->prefix.hi);
+    }
+
+    bt_assert(trie_same(trie1, trie2));
+
+    struct f_prefix_node *nxt;
+    WALK_LIST_DELSAFE(n, nxt, prefixes)
+    {
+      free(n);
+    }
+  }
+
+  return BT_SUCCESS;
+}
+
+int
+main(int argc, char *argv[])
+{
+  bt_init(argc, argv);
+
+  bt_test_suite(t_match_net, "Testing random prefix matching");
+  bt_test_suite(t_trie_same, "A trie filled forward should be same with a trie filled backward.");
+
+  return bt_exit_value();
+}