middleware/file: fix delegations (#376)

Fix the delegation handling in the *file* and *dnssec* middleware.
Refactor tests a bit and show that they are failling.

Add a Tree printer, cleanups and tests.
Fix wildcard test - should get no answer from empty-non-terminal

5 files changed, 88 insertions, 89 deletions

diff --git a/middleware/file/tree/elem.go b/middleware/file/tree/elem.go
index 234e2c848..6317cc912 100644
--- a/middleware/file/tree/elem.go
+++ b/middleware/file/tree/elem.go
@@ -52,13 +52,10 @@ func (e *Elem) Name() string {
 	return ""
 }
 
-// IsWildcard returns true if this name starts with a wildcard label (*.)
-func (e *Elem) IsWildcard() bool {
-	n := e.Name()
-	if len(n) < 2 {
-		return false
-	}
-	return n[0] == '*' && n[1] == '.'
+// Empty returns true is e does not contain any RRs, i.e. is an
+// empty-non-terminal.
+func (e *Elem) Empty() bool {
+	return len(e.m) == 0
 }
 
 // Insert inserts rr into e. If rr is equal to existing rrs this is a noop.
diff --git a/middleware/file/tree/less.go b/middleware/file/tree/less.go
index 595dc9213..3b8340088 100644
--- a/middleware/file/tree/less.go
+++ b/middleware/file/tree/less.go
@@ -11,7 +11,7 @@ import (
 // The function orders names in DNSSEC canonical order: RFC 4034s section-6.1
 //
 // See http://bert-hubert.blogspot.co.uk/2015/10/how-to-do-fast-canonical-ordering-of.html
-// for a blog article on this implementation.
+// for a blog article on this implementation, although here we still go label by label.
 //
 // The values of a and b are *not* lowercased before the comparison!
 func less(a, b string) int {
@@ -24,6 +24,7 @@ func less(a, b string) int {
 		if oka && okb {
 			return 0
 		}
+
 		// sadly this []byte will allocate... TODO(miek): check if this is needed
 		// for a name, otherwise compare the strings.
 		ab := []byte(a[ai:aj])
diff --git a/middleware/file/tree/less_test.go b/middleware/file/tree/less_test.go
index 419b75c55..ed021b66f 100644
--- a/middleware/file/tree/less_test.go
+++ b/middleware/file/tree/less_test.go
@@ -65,7 +65,7 @@ Tests:
 		sort.Sort(set(test.in))
 		for i := 0; i < len(test.in); i++ {
 			if test.in[i] != test.out[i] {
-				t.Errorf("test %d: expected %s, got %s\n", j, test.out[i], test.in[i])
+				t.Errorf("Test %d: expected %s, got %s\n", j, test.out[i], test.in[i])
 				n := ""
 				for k, in := range test.in {
 					if k+1 == len(test.in) {
diff --git a/middleware/file/tree/print.go b/middleware/file/tree/print.go
new file mode 100644
index 000000000..f098e56c7
--- /dev/null
+++ b/middleware/file/tree/print.go
@@ -0,0 +1,58 @@
+package tree
+
+import "fmt"
+
+// Print prints a Tree. Main use is to aid in debugging.
+func (t *Tree) Print() {
+	if t.Root == nil {
+		fmt.Println("<nil>")
+	}
+	t.Root.print()
+}
+
+func (n *Node) print() {
+	q := NewQueue()
+	q.Push(n)
+
+	nodesInCurrentLevel := 1
+	nodesInNextLevel := 0
+
+	for !q.Empty() {
+		do := q.Pop()
+		nodesInCurrentLevel--
+
+		if do != nil {
+			fmt.Print(do.Elem.Name(), " ")
+			q.Push(do.Left)
+			q.Push(do.Right)
+			nodesInNextLevel += 2
+		}
+		if nodesInCurrentLevel == 0 {
+			fmt.Println()
+		}
+		nodesInCurrentLevel = nodesInNextLevel
+		nodesInNextLevel = 0
+	}
+	fmt.Println()
+}
+
+type queue []*Node
+
+func NewQueue() queue {
+	q := queue([]*Node{})
+	return q
+}
+
+func (q *queue) Push(n *Node) {
+	*q = append(*q, n)
+}
+
+func (q *queue) Pop() *Node {
+	n := (*q)[0]
+	*q = (*q)[1:]
+	return n
+}
+
+func (q *queue) Empty() bool {
+	return len(*q) == 0
+}
diff --git a/middleware/file/tree/tree.go b/middleware/file/tree/tree.go
index 668c19734..ed33c09a4 100644
--- a/middleware/file/tree/tree.go
+++ b/middleware/file/tree/tree.go
@@ -13,9 +13,6 @@
 // Heavily modified by Miek Gieben for use in DNS zones.
 package tree
 
-// TODO(miek): locking? lockfree would be nice. Will probably go for fine grained locking on the name level.
-// TODO(miek): fix docs
-
 import "github.com/miekg/dns"
 
 const (
@@ -23,17 +20,6 @@ const (
 	bu23
 )
 
-// Result is a result of a Search.
-type Result int
-
-// Various constants that indicated the type a resource returned.
-const (
-	Found Result = iota
-	NameError
-	EmptyNonTerminal
-	Delegation
-)
-
 // Operation mode of the LLRB tree.
 const mode = bu23
 
@@ -151,77 +137,32 @@ func (t *Tree) Len() int {
 	return t.Count
 }
 
-// Search returns the first match of qname/qtype in the Tree.
-func (t *Tree) Search(qname string, qtype uint16) (*Elem, Result) {
-	if t.Root == nil {
-		return nil, NameError
-	}
-	n, res := t.Root.search(qname, qtype, false)
-	if n == nil {
-		return nil, res
-	}
-	return n.Elem, res
-}
-
-// SearchGlue returns the first match of qname/(A/AAAA) in the Tree.
-func (t *Tree) SearchGlue(qname string) (*Elem, Result) {
-	// TODO(miek): shouldn't need this, because when we *find* the delegation, we
-	// know for sure that any glue is under it. Should change the return values
-	// to return the node, so we can resume from those.
+// Search returns the first match of qname in the Tree.
+func (t *Tree) Search(qname string) (*Elem, bool) {
 	if t.Root == nil {
-		return nil, NameError
+		return nil, false
 	}
-	n, res := t.Root.search(qname, dns.TypeA, true)
+	n, res := t.Root.search(qname)
 	if n == nil {
 		return nil, res
 	}
 	return n.Elem, res
 }
 
-// search searches the tree for qname and type. If glue is true the search *does* not
-// stop when hitting NS records, but descends in search of glue. The qtype for this
-// kind of search can only be AAAA or A.
-func (n *Node) search(qname string, qtype uint16, glue bool) (*Node, Result) {
-	old := n
-
-	var wild *Node
-
+// search searches the tree for qname and type.
+func (n *Node) search(qname string) (*Node, bool) {
 	for n != nil {
-
-		// Is this a wildcard that applies to us
-		if n.Elem.IsWildcard() {
-			if dns.IsSubDomain(n.Elem.Name()[2:], qname) {
-				wild = n
-			}
-		}
-
 		switch c := Less(n.Elem, qname); {
 		case c == 0:
-			return n, Found
+			return n, true
 		case c < 0:
-			old = n
 			n = n.Left
 		default:
-			if !glue && n.Elem.Types(dns.TypeNS) != nil {
-				return n, Delegation
-
-			}
-			old = n
 			n = n.Right
 		}
 	}
 
-	// If we have seen a wildcard "on-the-way-to-here", we should return this wildcard
-	// instead. This is to be able to have a more specific RR defined *under* the wildcard.
-	if wild != nil {
-		return wild, Found
-	}
-
-	if dns.CountLabel(qname) < dns.CountLabel(old.Elem.Name()) {
-		return n, EmptyNonTerminal
-	}
-
-	return n, NameError
+	return n, false
 }
 
 // Insert inserts rr into the Tree at the first match found
@@ -233,6 +174,7 @@ func (t *Tree) Insert(rr dns.RR) {
 	t.Root.Color = black
 }
 
+// insert inserts rr in to the tree.
 func (n *Node) insert(rr dns.RR) (root *Node, d int) {
 	if n == nil {
 		return &Node{Elem: newElem(rr)}, 1
@@ -339,21 +281,21 @@ func (t *Tree) Delete(rr dns.RR) {
 		return
 	}
 
-	el, _ := t.Search(rr.Header().Name, rr.Header().Rrtype)
+	el, _ := t.Search(rr.Header().Name)
 	if el == nil {
-		t.DeleteNode(rr)
+		t.deleteNode(rr)
 		return
 	}
 	// Delete from this element.
 	empty := el.Delete(rr)
 	if empty {
-		t.DeleteNode(rr)
+		t.deleteNode(rr)
 		return
 	}
 }
 
 // DeleteNode deletes the node that matches rr according to Less().
-func (t *Tree) DeleteNode(rr dns.RR) {
+func (t *Tree) deleteNode(rr dns.RR) {
 	if t.Root == nil {
 		return
 	}
@@ -427,15 +369,16 @@ func (n *Node) max() *Node {
 }
 
 // Prev returns the greatest value equal to or less than the qname according to Less().
-func (t *Tree) Prev(qname string) *Elem {
+func (t *Tree) Prev(qname string) (*Elem, bool) {
 	if t.Root == nil {
-		return nil
+		return nil, false
 	}
+
 	n := t.Root.floor(qname)
 	if n == nil {
-		return nil
+		return nil, false
 	}
-	return n.Elem
+	return n.Elem, true
 }
 
 func (n *Node) floor(qname string) *Node {
@@ -445,7 +388,7 @@ func (n *Node) floor(qname string) *Node {
 	switch c := Less(n.Elem, qname); {
 	case c == 0:
 		return n
-	case c < 0:
+	case c <= 0:
 		return n.Left.floor(qname)
 	default:
 		if r := n.Right.floor(qname); r != nil {
@@ -456,15 +399,15 @@ func (n *Node) floor(qname string) *Node {
 }
 
 // Next returns the smallest value equal to or greater than the qname according to Less().
-func (t *Tree) Next(qname string) *Elem {
+func (t *Tree) Next(qname string) (*Elem, bool) {
 	if t.Root == nil {
-		return nil
+		return nil, false
 	}
 	n := t.Root.ceil(qname)
 	if n == nil {
-		return nil
+		return nil, false
 	}
-	return n.Elem
+	return n.Elem, true
 }
 
 func (n *Node) ceil(qname string) *Node {