Filter: Add literal for empty set

Add literal for empty set [], which works both for tree-based sets
and prefix sets by using existing constant promotion mechanism.

Minor changes by committer.

6 files changed, 90 insertions, 5 deletions

diff --git a/filter/config.Y b/filter/config.Y
index a4b4d3d3..a4e82c7d 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -674,6 +674,7 @@ bgp_path:
 bgp_path_tail:
    NUM bgp_path_tail		{ $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .asn = $1, .kind = PM_ASN, }, }); $$->next = $2;  }
  | NUM DDOT NUM bgp_path_tail	{ $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .from = $1, .to = $3, .kind = PM_ASN_RANGE }, }); $$->next = $4; }
+ | '[' ']' bgp_path_tail { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .set = NULL, .kind = PM_ASN_SET }, }); $$->next = $3; }
  | '[' set_items ']' bgp_path_tail {
    if ($2->from.type != T_INT) cf_error("Only integer sets allowed in path mask");
    $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .set = build_tree($2), .kind = PM_ASN_SET }, }); $$->next = $4;
@@ -693,6 +694,7 @@ constant:
  | fipa	  { $$ = f_new_inst(FI_CONSTANT, $1); }
  | VPN_RD { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_RD, .val.ec = $1, }); }
  | net_   { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_NET, .val.net = $1, }); }
+ | '[' ']' { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_SET, .val.t = NULL, }); }
  | '[' set_items ']' {
      DBG( "We've got a set here..." );
      $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_SET, .val.t = build_tree($2), });
diff --git a/filter/data.c b/filter/data.c
index 56c1fb17..276738a9 100644
--- a/filter/data.c
+++ b/filter/data.c
@@ -79,6 +79,8 @@ f_type_element_type(enum f_type t)
   };
 }
 
+const struct f_trie f_const_empty_trie = { .ipv4 = -1, };
+
 const struct f_val f_const_empty_path = {
   .type = T_PATH,
   .val.ad = &null_adata,
@@ -91,6 +93,9 @@ const struct f_val f_const_empty_path = {
 }, f_const_empty_lclist = {
   .type = T_LCLIST,
   .val.ad = &null_adata,
+}, f_const_empty_prefix_set = {
+  .type = T_PREFIX_SET,
+  .val.ti = &f_const_empty_trie,
 };
 
 static struct adata *
@@ -301,6 +306,12 @@ val_same(const struct f_val *v1, const struct f_val *v2)
 int
 clist_set_type(const struct f_tree *set, struct f_val *v)
 {
+  if (!set)
+  {
+    v->type = T_VOID;
+    return 1;
+  }
+
   switch (set->from.type)
   {
   case T_PAIR:
@@ -537,6 +548,9 @@ val_in_range(const struct f_val *v1, const struct f_val *v2)
   if (v2->type != T_SET)
     return F_CMP_ERROR;
 
+  if (!v2->val.t)
+    return 0;
+
   /* With integrated Quad<->IP implicit conversion */
   if ((v1->type == v2->val.t->from.type) ||
       ((v1->type == T_QUAD) && val_is_ip4(&(v2->val.t->from)) && val_is_ip4(&(v2->val.t->to))))
diff --git a/filter/data.h b/filter/data.h
index 8cba8c0e..221e4229 100644
--- a/filter/data.h
+++ b/filter/data.h
@@ -279,11 +279,11 @@ int val_in_range(const struct f_val *v1, const struct f_val *v2);
 
 int clist_set_type(const struct f_tree *set, struct f_val *v);
 static inline int eclist_set_type(const struct f_tree *set)
-{ return set->from.type == T_EC; }
+{ return !set || set->from.type == T_EC; }
 static inline int lclist_set_type(const struct f_tree *set)
-{ return set->from.type == T_LC; }
+{ return !set || set->from.type == T_LC; }
 static inline int path_set_type(const struct f_tree *set)
-{ return set->from.type == T_INT; }
+{ return !set || set->from.type == T_INT; }
 
 const struct adata *clist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
 const struct adata *eclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
@@ -299,7 +299,7 @@ undef_value(struct f_val v)
     (v.val.ad == &null_adata);
 }
 
-extern const struct f_val f_const_empty_path, f_const_empty_clist, f_const_empty_eclist, f_const_empty_lclist;
+extern const struct f_val f_const_empty_path, f_const_empty_clist, f_const_empty_eclist, f_const_empty_lclist, f_const_empty_prefix_set;
 
 enum filter_return f_eval(const struct f_line *expr, struct linpool *tmp_pool, struct f_val *pres);
 
diff --git a/filter/decl.m4 b/filter/decl.m4
index 4f7ca3ad..fc26e193 100644
--- a/filter/decl.m4
+++ b/filter/decl.m4
@@ -501,6 +501,11 @@ f_const_promotion(struct f_inst *arg, enum f_type want)
     return 1;
   }
 
+  else if ((c->type == T_SET) && (!c->val.t) && (want == T_PREFIX_SET)) {
+    *c = f_const_empty_prefix_set;
+    return 1;
+  }
+
   return 0;
 }
 
diff --git a/filter/f-inst.c b/filter/f-inst.c
index 5d42c40a..d321f06d 100644
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -401,7 +401,7 @@
 	  break;
 
 	case T_SET:
-	  if (vv(i).val.t->from.type != T_INT)
+	  if (!path_set_type(vv(i).val.t))
 	    runtime("Only integer sets allowed in path mask");
 
 	  pm->item[i] = (struct f_path_mask_item) {
diff --git a/filter/test.conf b/filter/test.conf
index 484628e5..50c58b3a 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -130,12 +130,18 @@ define is3 = [5, 17, 2, 11, 8, 15, 3, 19];
 function t_int_set()
 int set is;
 {
+	is = [];
+	bt_assert(is = []);
+	bt_assert(0 !~ is);
+
 	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 ]);
 	bt_assert(999 !~ [ 666, 333 ]);
+	bt_assert(1 !~ []);
+	bt_assert(1 !~ is);
 
 	is = [ 2, 3, 4, 7..11 ];
 	bt_assert(10 ~ is);
@@ -170,6 +176,7 @@ int set is;
 	bt_assert([1,4..10,20] = [1,4..10,20]);
 
 	bt_assert(format([ 1, 2, 1, 1, 1, 3, 4, 1, 1, 1, 5 ]) = "[1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5]");
+	bt_assert(format([]) = "[]");
 }
 
 bt_test_suite(t_int_set, "Testing sets of integers");
@@ -237,6 +244,9 @@ pair pp;
 pair set ps;
 {
 	pp = (1, 2);
+	ps = [];
+	bt_assert(pp !~ ps);
+
 	ps = [(1,(one+one)), (3,4)..(4,8), (5,*), (6,3..6)];
 	bt_assert(format(ps) = "[(1,2), (3,4)..(4,8), (5,0)..(5,65535), (6,3)..(6,6)]");
 	bt_assert(pp ~ ps);
@@ -253,6 +263,7 @@ pair set ps;
 	bt_assert((6,6+one) !~ ps);
 	bt_assert(((one+6),2) !~ ps);
 	bt_assert((1,1) !~ ps);
+	bt_assert(pp !~ []);
 
 	ps = [(20..150, 200..300), (50100..50200, 1000..50000), (*, 5+5)];
 	bt_assert((100,200) ~ ps);
@@ -304,6 +315,7 @@ quad qq;
 	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]);
+	bt_assert(qq !~ []);
 }
 
 bt_test_suite(t_quad_set, "Testing sets of quads");
@@ -384,6 +396,7 @@ ip set ips;
 
 	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_assert(1.2.3.4 !~ []);
 }
 
 bt_test_suite(t_ip_set, "Testing sets of ip address");
@@ -473,13 +486,34 @@ function test_pxset(prefix set 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(net10 !~ []);
 
 	bt_assert([ 10.0.0.0/8{ 15 , 17 } ] = [ 10.0.0.0/8{ 15 , 17 } ]);
 }
 
+function test_empty_pxset(prefix set pxs)
+int set s0;
+prefix set s1;
+{
+	s0 = [];
+	s1 = [];
+	bt_assert(pxs != s0);
+	bt_assert(pxs  = s1);
+	#bt_assert(pxs  = []);
+}
+
 function t_prefix_set()
 prefix set pxs;
 {
+	pxs = [];
+	bt_assert(format(pxs) = "[]");
+	#bt_assert(pxs = []);
+	bt_assert(1.2.0.0/16 !~ []);
+	bt_assert(1.2.0.0/16 !~ pxs);
+
+	test_empty_pxset([]);
+	test_empty_pxset(pxs);
+
 	pxs = [ 1.2.0.0/16, 1.4.0.0/16+, 44.66.88.64/30{24,28}, 12.34.56.0/24{8,16} ];
 	bt_assert(format(pxs) = "[1.2.0.0/16{0.1.0.0}, 1.4.0.0/16{0.1.255.255}, 12.34.0.0/16{1.255.0.0}, 44.66.88.64/28{0.0.1.240}]");
 
@@ -564,6 +598,12 @@ bt_test_suite(t_prefix6, "Testing prefix IPv6");
 function t_prefix6_set()
 prefix set pxs;
 {
+	pxs = [];
+	bt_assert(format(pxs) = "[]");
+	#bt_assert(pxs = []);
+	bt_assert(12::34/128 !~ []);
+	bt_assert(12::34/128 !~ pxs);
+
 	bt_assert(1180::/16 ~ [ 1100::/8{15, 17} ]);
 	bt_assert(12::34 = 12::34);
 	bt_assert(12::34 ~ [ 12::33..12::35 ]);
@@ -681,6 +721,7 @@ int set set12;
 	bt_assert(3 ~ p2);
 	bt_assert(p2 ~ [2, 10..20]);
 	bt_assert(p2 ~ [4, 10..20]);
+	bt_assert(p2 !~ []);
 
 	p2 = prepend(p2, 5);
 	bt_assert(p2 !~ pm1);
@@ -691,6 +732,8 @@ int set set12;
 	bt_assert(p2 ~ [= 5 [2, 4, 6] 3 [1..2] 1 =]);
 	bt_assert(p2 ~ [= 5 set35 3 set12 set12 =]);
 	bt_assert(p2 ~ mkpath(5, 4));
+	bt_assert(p2 ~ [= * [3] * =]);
+	bt_assert(p2 !~ [= * [] * =]);
 
 	bt_assert(p2.len = 5);
 	bt_assert(p2.first = 5);
@@ -699,6 +742,10 @@ int set set12;
 	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));
+	bt_assert(delete(p2, []) = p2);
+	bt_assert(filter(p2, []) = +empty+);
+	bt_assert(delete(prepend(prepend(+empty+, 0), 1), []) = prepend(prepend(+empty+, 0), 1));
+	bt_assert(filter(prepend(prepend(+empty+, 0), 1), []) = +empty+);
 
 	p2 = prepend( + empty +, 5 );
 	p2 = prepend( p2, 4 );
@@ -759,6 +806,7 @@ clist r;
 	bt_assert(l ~ [(2,2..3)]);
 	bt_assert(l ~ [(1,1..2)]);
 	bt_assert(l ~ [(1,1)..(1,2)]);
+	bt_assert(l !~ []);
 
 	l = add(l, (2,5));
 	l = add(l, (5,one));
@@ -796,6 +844,9 @@ clist r;
 	bt_assert(l !~ [(*,(one+6))]);
 	bt_assert(l !~ [(*, (one+one+one))]);
 
+	bt_assert(delete(l, []) = l);
+	bt_assert(filter(l, []) = -empty-);
+
 	l = delete(l, [(*,(one+onef(3)))]);
 	l = delete(l, [(*,(4+one))]);
 	bt_assert(l = add(-empty-, (3,1)));
@@ -913,11 +964,15 @@ eclist r;
 	bt_assert((ro, 10.20.30.40, 100) !~ el);
 	bt_assert(el !~ [(rt, 10, 35..40)]);
 	bt_assert(el !~ [(ro, 10, *)]);
+	bt_assert(el !~ []);
 
 	el = add(el, (rt, 10, 40));
 	el2 = filter(el, [(rt, 10, 20..40)] );
 	el2 = add(el2, (rt, 10, 50));
 
+	bt_assert(delete(el, []) = el);
+	bt_assert(filter(el, []) = --empty--);
+
 	#  eclist A (1,30,40)
 	bt_assert(el = add(add(add(--empty--, (rt, 10, 1)), (rt, 10, 30)), (rt, 10, 40)));
 	bt_assert(format(el) = "(eclist (rt, 10, 1) (rt, 10, 30) (rt, 10, 40))");
@@ -1035,6 +1090,9 @@ lclist r;
 	ll2 = add(ll2, (30, 30, 30));
 	ll2 = add(ll2, (40, 40, 40));
 
+	bt_assert(delete(ll, []) = ll);
+	bt_assert(filter(ll, []) = ---empty---);
+
 	#  lclist A (10, 20, 30)
 	bt_assert(format(ll) = "(lclist (10, 10, 10) (20, 20, 20) (30, 30, 30))");
 
@@ -1094,6 +1152,7 @@ lc set lls;
 	bt_assert(ll !~ [(5,10,15), (10,21,30)]);
 	bt_assert(ll !~ [(10,21..25,*)]);
 	bt_assert(ll !~ [(11, *, *)]);
+	bt_assert(ll !~ []);
 
 	lls = [(10, 10, 10), (20, 20, 15..25), (30, 30, *), (40, 35..45, *), (50, *, *), (55..65, *, *)];
 	bt_assert(format(lls) = "[(10, 10, 10), (20, 20, 15)..(20, 20, 25), (30, 30, 0)..(30, 30, 4294967295), (40, 35, 0)..(40, 45, 4294967295), (50, 0, 0)..(50, 4294967295, 4294967295), (55, 0, 0)..(65, 4294967295, 4294967295)]");
@@ -1150,6 +1209,10 @@ bt_test_suite(t_rd, "Testing route distinguishers");
 function t_rd_set()
 rd set rds;
 {
+	rds = [];
+	bt_assert(rds = []);
+	bt_assert(10:20 !~ rds);
+
 	rds = [10:20, 100000:100..100000:200];
 	bt_assert(format(rds)  = "[10:20, 100000:100..100000:200]");
 
@@ -1160,6 +1223,7 @@ rd set rds;
 	bt_assert(100000:128 ~ rds);
 	bt_assert(100000:200 ~ rds);
 	bt_assert(100010:150 !~ rds);
+	bt_assert(100010:150 !~ []);
 }
 
 bt_test_suite(t_rd_set, "Testing sets of route distinguishers");