Fix closest encloser

4 files changed, 58 insertions, 17 deletions

diff --git a/middleware/canonical.go b/middleware/canonical.go
index b8953f655..9dacba78c 100644
--- a/middleware/canonical.go
+++ b/middleware/canonical.go
@@ -8,10 +8,10 @@ import (
 
 // Less returns <0 when a is less than b, 0 when they are equal and
 // >0 when a is larger than b.
-// The function order names in DNSSEC canonical order.
+// 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 how we do this. And https://tools.ietf.org/html/rfc4034#section-6.1 .
+// for a blog article on this implementation:
 func Less(a, b string) int {
 	i := 1
 	aj := len(a)
diff --git a/middleware/file/closest.go b/middleware/file/closest.go
index daee27314..8f9d9a8ba 100644
--- a/middleware/file/closest.go
+++ b/middleware/file/closest.go
@@ -4,13 +4,19 @@ import "github.com/miekg/dns"
 
 // ClosestEncloser returns the closest encloser for rr.
 func (z *Zone) ClosestEncloser(rr dns.RR) string {
-	elem := z.Tree.Prev(rr)
-	if elem == nil {
-		// SOA?
-		return ""
-	}
-	for _, r := range elem.All() {
-		return r.Header().Name
+	// tree/tree.go does not store a parent *Node pointer, so we can't
+	// just follow up the tree. TODO(miek): fix.
+
+	offset, end := dns.NextLabel(rr.Header().Name, 0)
+	for !end {
+		elem := z.Tree.Get(rr)
+		if elem != nil {
+			return elem.Name()
+		}
+		rr.Header().Name = rr.Header().Name[offset:]
+
+		offset, end = dns.NextLabel(rr.Header().Name, offset)
 	}
-	return ""
+
+	return z.SOA.Header().Name
 }
diff --git a/middleware/file/closest_test.go b/middleware/file/closest_test.go
index 643e4943f..db0b718b2 100644
--- a/middleware/file/closest_test.go
+++ b/middleware/file/closest_test.go
@@ -17,9 +17,12 @@ func TestClosestEncloser(t *testing.T) {
 		in, out string
 	}{
 		{"miek.nl.", "miek.nl."},
+		{"www.miek.nl.", "www.miek.nl."},
+
 		{"blaat.miek.nl.", "miek.nl."},
-		{"blaat.blaat.miek.nl.", "miek.nl."},
-		{"blaat.a.miek.nl.", "archive.miek.nl."},
+		{"blaat.www.miek.nl.", "www.miek.nl."},
+		{"www.blaat.miek.nl.", "miek.nl."},
+		{"blaat.a.miek.nl.", "a.miek.nl."},
 	}
 
 	mk, _ := dns.TypeToRR[dns.TypeA]
diff --git a/middleware/file/tree/tree.go b/middleware/file/tree/tree.go
index 05dfdfa7d..ca616ad67 100644
--- a/middleware/file/tree/tree.go
+++ b/middleware/file/tree/tree.go
@@ -13,7 +13,7 @@
 // Heavily modified by Miek Gieben for use in DNS zones.
 package tree
 
-// TODO(miek): locking? lockfree
+// TODO(miek): locking? lockfree would be nice. Will probably go for fine grained locking on the name level.
 // TODO(miek): fix docs
 
 import (
@@ -64,6 +64,14 @@ func (e *Elem) All() []dns.RR {
 	return list
 }
 
+// Return the domain name for this element.
+func (e *Elem) Name() string {
+	for _, rrs := range e.m {
+		return rrs[0].Header().Name
+	}
+	return ""
+}
+
 // Insert inserts rr into e. If rr is equal to existing rrs this is a noop.
 func (e *Elem) Insert(rr dns.RR) {
 	t := rr.Header().Rrtype
@@ -112,10 +120,7 @@ func (e *Elem) Delete(rr dns.RR) (empty bool) {
 }
 
 func Less(a *Elem, rr dns.RR) int {
-	for _, ar := range a.m { // Get first element in a
-		return middleware.Less(ar[0].Header().Name, rr.Header().Name)
-	}
-	return 0
+	return middleware.Less(rr.Header().Name, a.Name())
 }
 
 // Assuming the same type and name this will check if the rdata is equal as well.
@@ -539,6 +544,33 @@ func (n *Node) ceil(rr dns.RR) *Node {
 	return n
 }
 
+// Do performs fn on all values stored in the tree. A boolean is returned indicating whether the
+// Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort
+// relationships, future tree operation behaviors are undefined.
+func (t *Tree) Do(fn func(e *Elem) bool) bool {
+	if t.Root == nil {
+		return false
+	}
+	return t.Root.do(fn)
+}
+
+func (n *Node) do(fn func(e *Elem) bool) (done bool) {
+	if n.Left != nil {
+		done = n.Left.do(fn)
+		if done {
+			return
+		}
+	}
+	done = fn(n.Elem)
+	if done {
+		return
+	}
+	if n.Right != nil {
+		done = n.Right.do(fn)
+	}
+	return
+}
+
 /*
 Copyright ©2012 The bíogo Authors. All rights reserved.