empty non-terminal support

When looking for a name in tree, return wether we got to a longer one -

if so we had an ent. Add tests + dnssec tests and refactor the tests as

well a bit.

13 files changed, 423 insertions, 267 deletions

diff --git a/middleware/file/closest.go b/middleware/file/closest.go
index 895b1a524..df74cad50 100644
--- a/middleware/file/closest.go
+++ b/middleware/file/closest.go
@@ -6,10 +6,9 @@ import "github.com/miekg/dns"
 func (z *Zone) ClosestEncloser(rr dns.RR) string {
 	// 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)
+		elem, _ := z.Tree.Get(rr)
 		if elem != nil {
 			return elem.Name()
 		}
diff --git a/middleware/file/dnssec_test.go b/middleware/file/dnssec_test.go
index 44f8b0f66..c225a5612 100644
--- a/middleware/file/dnssec_test.go
+++ b/middleware/file/dnssec_test.go
@@ -121,36 +121,19 @@ func TestLookupDNSSEC(t *testing.T) {
 		sort.Sort(coretest.RRSet(resp.Ns))
 		sort.Sort(coretest.RRSet(resp.Extra))
 
-		if resp.Rcode != tc.Rcode {
-			t.Errorf("rcode is %q, expected %q", dns.RcodeToString[resp.Rcode], dns.RcodeToString[tc.Rcode])
+		if !coretest.Header(t, tc, resp) {
 			t.Logf("%v\n", resp)
 			continue
 		}
 
-		if len(resp.Answer) != len(tc.Answer) {
-			t.Errorf("answer for %q contained %d results, %d expected", tc.Qname, len(resp.Answer), len(tc.Answer))
-			t.Logf("%v\n", resp)
-			continue
-		}
-		if len(resp.Ns) != len(tc.Ns) {
-			t.Errorf("authority for %q contained %d results, %d expected", tc.Qname, len(resp.Ns), len(tc.Ns))
-			t.Logf("%v\n", resp)
-			continue
-		}
-		if len(resp.Extra) != len(tc.Extra) {
-			t.Errorf("additional for %q contained %d results, %d expected", tc.Qname, len(resp.Extra), len(tc.Extra))
-			t.Logf("%v\n", resp)
-			continue
-		}
-
-		if !coretest.CheckSection(t, tc, coretest.Answer, resp.Answer) {
+		if !coretest.Section(t, tc, coretest.Answer, resp.Answer) {
 			t.Logf("%v\n", resp)
 		}
-		if !coretest.CheckSection(t, tc, coretest.Ns, resp.Ns) {
+		if !coretest.Section(t, tc, coretest.Ns, resp.Ns) {
 			t.Logf("%v\n", resp)
 
 		}
-		if !coretest.CheckSection(t, tc, coretest.Extra, resp.Extra) {
+		if !coretest.Section(t, tc, coretest.Extra, resp.Extra) {
 			t.Logf("%v\n", resp)
 		}
 	}
diff --git a/middleware/file/ent_test.go b/middleware/file/ent_test.go
new file mode 100644
index 000000000..38f68e8e1
--- /dev/null
+++ b/middleware/file/ent_test.go
@@ -0,0 +1,176 @@
+package file
+
+import (
+	"sort"
+	"strings"
+	"testing"
+
+	"github.com/miekg/coredns/middleware"
+	coretest "github.com/miekg/coredns/middleware/testing"
+
+	"github.com/miekg/dns"
+	"golang.org/x/net/context"
+)
+
+var entTestCases = []coretest.Case{
+	{
+		Qname: "b.c.miek.nl.", Qtype: dns.TypeA,
+		Ns: []dns.RR{
+			coretest.SOA("miek.nl.	1800	IN	SOA	linode.atoom.net. miek.miek.nl. 1282630057 14400 3600 604800 14400"),
+		},
+	},
+	{
+		Qname: "b.c.miek.nl.", Qtype: dns.TypeA, Do: true,
+		Ns: []dns.RR{
+			coretest.NSEC("a.miek.nl.	14400	IN	NSEC	a.b.c.miek.nl. A RRSIG NSEC"),
+			coretest.RRSIG("a.miek.nl.	14400	IN	RRSIG	NSEC 8 3 14400 20160502144311 20160402144311 12051 miek.nl. d5XZEy6SUpq98ZKUlzqhAfkLI9pQPc="),
+			coretest.RRSIG("miek.nl.	1800	IN	RRSIG	SOA 8 2 1800 20160502144311 20160402144311 12051 miek.nl. KegoBxA3Tbrhlc4cEdkRiteIkOfsq"),
+			coretest.SOA("miek.nl.	1800	IN	SOA	linode.atoom.net. miek.miek.nl. 1282630057 14400 3600 604800 14400"),
+		},
+	},
+}
+
+func TestLookupENT(t *testing.T) {
+	zone, err := Parse(strings.NewReader(dbMiekENTNL), testzone, "stdin")
+	if err != nil {
+		t.Fatalf("expect no error when reading zone, got %q", err)
+	}
+
+	fm := File{Next: coretest.ErrorHandler(), Zones: Zones{Z: map[string]*Zone{testzone: zone}, Names: []string{testzone}}}
+	ctx := context.TODO()
+
+	for _, tc := range entTestCases {
+		m := tc.Msg()
+
+		rec := middleware.NewResponseRecorder(&middleware.TestResponseWriter{})
+		_, err := fm.ServeDNS(ctx, rec, m)
+		if err != nil {
+			t.Errorf("expected no error, got %v\n", err)
+			return
+		}
+		resp := rec.Msg()
+
+		sort.Sort(coretest.RRSet(resp.Answer))
+		sort.Sort(coretest.RRSet(resp.Ns))
+		sort.Sort(coretest.RRSet(resp.Extra))
+
+		if !coretest.Header(t, tc, resp) {
+			t.Logf("%v\n", resp)
+			continue
+		}
+
+		if !coretest.Section(t, tc, coretest.Answer, resp.Answer) {
+			t.Logf("%v\n", resp)
+		}
+		if !coretest.Section(t, tc, coretest.Ns, resp.Ns) {
+			t.Logf("%v\n", resp)
+
+		}
+		if !coretest.Section(t, tc, coretest.Extra, resp.Extra) {
+			t.Logf("%v\n", resp)
+		}
+	}
+}
+
+const dbMiekENTNL = `; File written on Sat Apr  2 16:43:11 2016
+; dnssec_signzone version 9.10.3-P4-Ubuntu
+miek.nl.		1800	IN SOA	linode.atoom.net. miek.miek.nl. (
+					1282630057 ; serial
+					14400      ; refresh (4 hours)
+					3600       ; retry (1 hour)
+					604800     ; expire (1 week)
+					14400      ; minimum (4 hours)
+					)
+			1800	RRSIG	SOA 8 2 1800 (
+					20160502144311 20160402144311 12051 miek.nl.
+					KegoBxA3Tbrhlc4cEdkRiteIkOfsqD4oCLLM
+					ISJ5bChWy00LGHUlAnHVu5Ti96hUjVNmGSxa
+					xtGSuAAMFCr52W8pAB8LBIlu9B6QZUPHMccr
+					SuzxAX3ioawk2uTjm+k8AGPT4RoQdXemGLAp
+					zJTASolTVmeMTh5J0sZTZJrtvZ0= )
+			1800	NS	linode.atoom.net.
+			1800	RRSIG	NS 8 2 1800 (
+					20160502144311 20160402144311 12051 miek.nl.
+					m0cOHL6Rre/0jZPXe+0IUjs/8AFASRCvDbSx
+					ZQsRDSlZgS6RoMP3OC77cnrKDVlfZ2Vhq3Ce
+					nYPoGe0/atB92XXsilmstx4HTSU64gsV9iLN
+					Xkzk36617t7zGOl/qumqfaUXeA9tihItzEim
+					6SGnufVZI4o8xeyaVCNDDuN0bvY= )
+			14400	NSEC	a.miek.nl. NS SOA RRSIG NSEC DNSKEY
+			14400	RRSIG	NSEC 8 2 14400 (
+					20160502144311 20160402144311 12051 miek.nl.
+					BCWVgwxWrs4tBjS9QXKkftCUbiLi40NyH1yA
+					nbFy1wCKQ2jDH00810+ia4b66QrjlAKgxE9z
+					9U7MKSMV86sNkyAtlCi+2OnjtWF6sxPdJO7k
+					CHeg46XBjrQuiJRY8CneQX56+IEPdufLeqPR
+					l+ocBQ2UkGhXmQdWp3CFDn2/eqU= )
+			1800	DNSKEY	256 3 8 (
+					AwEAAcNEU67LJI5GEgF9QLNqLO1SMq1EdoQ6
+					E9f85ha0k0ewQGCblyW2836GiVsm6k8Kr5EC
+					IoMJ6fZWf3CQSQ9ycWfTyOHfmI3eQ/1Covhb
+					2y4bAmL/07PhrL7ozWBW3wBfM335Ft9xjtXH
+					Py7ztCbV9qZ4TVDTW/Iyg0PiwgoXVesz
+					) ; ZSK; alg = RSASHA256; key id = 12051
+			1800	DNSKEY	257 3 8 (
+					AwEAAcWdjBl4W4wh/hPxMDcBytmNCvEngIgB
+					9Ut3C2+QI0oVz78/WK9KPoQF7B74JQ/mjO4f
+					vIncBmPp6mFNxs9/WQX0IXf7oKviEVOXLjct
+					R4D1KQLX0wprvtUIsQFIGdXaO6suTT5eDbSd
+					6tTwu5xIkGkDmQhhH8OQydoEuCwV245ZwF/8
+					AIsqBYDNQtQ6zhd6jDC+uZJXg/9LuPOxFHbi
+					MTjp6j3CCW0kHbfM/YHZErWWtjPj3U3Z7knQ
+					SIm5PO5FRKBEYDdr5UxWJ/1/20SrzI3iztvP
+					wHDsA2rdHm/4YRzq7CvG4N0t9ac/T0a0Sxba
+					/BUX2UVPWaIVBdTRBtgHi0s=
+					) ; KSK; alg = RSASHA256; key id = 33694
+			1800	RRSIG	DNSKEY 8 2 1800 (
+					20160502144311 20160402144311 12051 miek.nl.
+					YNpi1jRDQKpnsQEjIjxqy+kJGaYnV16e8Iug
+					40c82y4pee7kIojFUllSKP44qiJpCArxF557
+					tfjfwBd6c4hkqCScGPZXJ06LMyG4u//rhVMh
+					4hyKcxzQFKxmrFlj3oQGksCI8lxGX6RxiZuR
+					qv2ol2lUWrqetpAL+Zzwt71884E= )
+			1800	RRSIG	DNSKEY 8 2 1800 (
+					20160502144311 20160402144311 33694 miek.nl.
+					jKpLDEeyadgM0wDgzEk6sBBdWr2/aCrkAOU/
+					w6dYIafN98f21oIYQfscV1gc7CTsA0vwzzUu
+					x0QgwxoNLMvSxxjOiW/2MzF8eozczImeCWbl
+					ad/pVCYH6Jn5UBrZ5RCWMVcs2RP5KDXWeXKs
+					jEN/0EmQg5qNd4zqtlPIQinA9I1HquJAnS56
+					pFvYyGIbZmGEbhR18sXVBeTWYr+zOMHn2quX
+					0kkrx2udz+sPg7i4yRsLdhw138gPRy1qvbaC
+					8ELs1xo1mC9pTlDOhz24Q3iXpVAU1lXLYOh9
+					nUP1/4UvZEYXHBUQk/XPRciojniWjAF825x3
+					QoSivMHblBwRdAKJSg== )
+a.miek.nl.		1800	IN A	127.0.0.1
+			1800	RRSIG	A 8 3 1800 (
+					20160502144311 20160402144311 12051 miek.nl.
+					lUOYdSxScjyYz+Ebc+nb6iTNgCohqj7K+Dat
+					97KE7haV2nP3LxdYuDCJYZpeyhsXDLHd4bFI
+					bInYPwJiC6DUCxPCuCWy0KYlZOWW8KCLX3Ia
+					BOPQbvIwLsJhnX+/tyMD9mXortoqATO79/6p
+					nNxvFeM8pFDwaih17fXMuFR/BsI= )
+			14400	NSEC	a.b.c.miek.nl. A RRSIG NSEC
+			14400	RRSIG	NSEC 8 3 14400 (
+					20160502144311 20160402144311 12051 miek.nl.
+					d5XZEy6SUp+TPRJQED+0R65zf2Yeo/1dlEA2
+					jYYvkXGSHXke4sg9nH8U3nr1rLcuqA1DsQgH
+					uMIjdENvXuZ+WCSwvIbhC+JEI6AyQ6Gfaf/D
+					I3mfu60C730IRByTrKM5C2rt11lwRQlbdaUY
+					h23/nn/q98ZKUlzqhAfkLI9pQPc= )
+a.b.c.miek.nl.		1800	IN A	127.0.0.1
+			1800	RRSIG	A 8 5 1800 (
+					20160502144311 20160402144311 12051 miek.nl.
+					FwgU5+fFD4hEebco3gvKQt3PXfY+dcOJr8dl
+					Ky4WLsONIdhP+4e9oprPisSLxImErY21BcrW
+					xzu1IZrYDsS8XBVV44lBx5WXEKvAOrUcut/S
+					OWhFZW7ncdIQCp32ZBIatiLRJEqXUjx+guHs
+					noFLiHix35wJWsRKwjGLIhH1fbs= )
+			14400	NSEC	miek.nl. A RRSIG NSEC
+			14400	RRSIG	NSEC 8 5 14400 (
+					20160502144311 20160402144311 12051 miek.nl.
+					lXgOqm9/jRRYvaG5jC1CDvTtGYxMroTzf4t4
+					jeYGb60+qI0q9sHQKfAJvoQ5o8o1qfR7OuiF
+					f544ipYT9eTcJRyGAOoJ37yMie7ZIoVJ91tB
+					r8YdzZ9Q6x3v1cbwTaQiacwhPZhGYOw63qIs
+					q5IQErIPos2sNk+y9D8BEce2DO4= )`
diff --git a/middleware/file/file_test.go b/middleware/file/file_test.go
index 00f667d57..87314db43 100644
--- a/middleware/file/file_test.go
+++ b/middleware/file/file_test.go
@@ -1,5 +1,16 @@
 package file
 
+import (
+	"strings"
+	"testing"
+)
+
+func BenchmarkParseInsert(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		Parse(strings.NewReader(dbMiekENTNL), testzone, "stdin")
+	}
+}
+
 /*
 var testDir = filepath.Join(os.TempDir(), "caddy_testdir")
 var ErrCustom = errors.New("Custom Error")
diff --git a/middleware/file/lookup.go b/middleware/file/lookup.go
index aaf29834d..bc048c66a 100644
--- a/middleware/file/lookup.go
+++ b/middleware/file/lookup.go
@@ -16,7 +16,7 @@ const (
 	ServerFailure
 )
 
-// Lookup looks up qname and qtype in the zone, when do is true DNSSEC are included as well.
+// Lookup looks up qname and qtype in the zone. When do is true DNSSEC records are included.
 // Three sets of records are returned, one for the answer, one for authority  and one for the additional section.
 func (z *Zone) Lookup(qname string, qtype uint16, do bool) ([]dns.RR, []dns.RR, []dns.RR, Result) {
 	var rr dns.RR
@@ -34,11 +34,12 @@ func (z *Zone) Lookup(qname string, qtype uint16, do bool) ([]dns.RR, []dns.RR,
 	rr.Header().Rrtype = qtype
 	rr.Header().Name = qname
 
-	elem := z.Tree.Get(rr)
+	elem, res := z.Tree.Get(rr)
 	if elem == nil {
-		if elem == nil {
-			return z.nameError(rr, do)
+		if res == tree.EmptyNonTerminal {
+			return z.emptyNonTerminal(rr, do)
 		}
+		return z.nameError(rr, do)
 	}
 
 	rrs := elem.Types(dns.TypeCNAME)
@@ -66,6 +67,14 @@ func (z *Zone) noData(elem *tree.Elem, do bool) ([]dns.RR, []dns.RR, []dns.RR, R
 	return nil, append(soa, nsec...), nil, Success
 }
 
+func (z *Zone) emptyNonTerminal(rr dns.RR, do bool) ([]dns.RR, []dns.RR, []dns.RR, Result) {
+	soa, _, _, _ := z.lookupSOA(do)
+
+	elem := z.Tree.Prev(rr)
+	nsec := z.lookupNSEC(elem, do)
+	return nil, append(soa, nsec...), nil, Success
+}
+
 func (z *Zone) nameError(rr dns.RR, do bool) ([]dns.RR, []dns.RR, []dns.RR, Result) {
 	// Is there a wildcard?
 	rr1 := dns.Copy(rr)
@@ -73,7 +82,7 @@ func (z *Zone) nameError(rr dns.RR, do bool) ([]dns.RR, []dns.RR, []dns.RR, Resu
 	rr1.Header().Rrtype = rr.Header().Rrtype
 	ce := z.ClosestEncloser(rr1)
 	rr1.Header().Name = "*." + ce
-	elem := z.Tree.Get(rr1)
+	elem, _ := z.Tree.Get(rr1) // use result here?
 
 	if elem != nil {
 		ret := elem.Types(rr1.Header().Rrtype) // there can only be one of these (or zero)
@@ -127,7 +136,7 @@ func (z *Zone) lookupNSEC(elem *tree.Elem, do bool) []dns.RR {
 }
 
 func (z *Zone) lookupCNAME(rrs []dns.RR, rr dns.RR, do bool) ([]dns.RR, []dns.RR, []dns.RR, Result) {
-	elem := z.Tree.Get(rr)
+	elem, _ := z.Tree.Get(rr)
 	if elem == nil {
 		return rrs, nil, nil, Success
 	}
diff --git a/middleware/file/lookup_test.go b/middleware/file/lookup_test.go
index 6f9f59251..df65d0150 100644
--- a/middleware/file/lookup_test.go
+++ b/middleware/file/lookup_test.go
@@ -89,36 +89,19 @@ func TestLookup(t *testing.T) {
 		sort.Sort(coretest.RRSet(resp.Ns))
 		sort.Sort(coretest.RRSet(resp.Extra))
 
-		if resp.Rcode != tc.Rcode {
-			t.Errorf("rcode is %q, expected %q", dns.RcodeToString[resp.Rcode], dns.RcodeToString[tc.Rcode])
+		if !coretest.Header(t, tc, resp) {
 			t.Logf("%v\n", resp)
 			continue
 		}
 
-		if len(resp.Answer) != len(tc.Answer) {
-			t.Errorf("answer for %q contained %d results, %d expected", tc.Qname, len(resp.Answer), len(tc.Answer))
-			t.Logf("%v\n", resp)
-			continue
-		}
-		if len(resp.Ns) != len(tc.Ns) {
-			t.Errorf("authority for %q contained %d results, %d expected", tc.Qname, len(resp.Ns), len(tc.Ns))
-			t.Logf("%v\n", resp)
-			continue
-		}
-		if len(resp.Extra) != len(tc.Extra) {
-			t.Errorf("additional for %q contained %d results, %d expected", tc.Qname, len(resp.Extra), len(tc.Extra))
-			t.Logf("%v\n", resp)
-			continue
-		}
-
-		if !coretest.CheckSection(t, tc, coretest.Answer, resp.Answer) {
+		if !coretest.Section(t, tc, coretest.Answer, resp.Answer) {
 			t.Logf("%v\n", resp)
 		}
-		if !coretest.CheckSection(t, tc, coretest.Ns, resp.Ns) {
+		if !coretest.Section(t, tc, coretest.Ns, resp.Ns) {
 			t.Logf("%v\n", resp)
 
 		}
-		if !coretest.CheckSection(t, tc, coretest.Extra, resp.Extra) {
+		if !coretest.Section(t, tc, coretest.Extra, resp.Extra) {
 			t.Logf("%v\n", resp)
 		}
 	}
diff --git a/middleware/file/tree/all.go b/middleware/file/tree/all.go
index f621e3465..fd806365f 100644
--- a/middleware/file/tree/all.go
+++ b/middleware/file/tree/all.go
@@ -19,3 +19,30 @@ func (n *Node) all(found []*Elem) []*Elem {
 	}
 	return found
 }
+
+// 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
+}
diff --git a/middleware/file/tree/elem.go b/middleware/file/tree/elem.go
new file mode 100644
index 000000000..4008e8380
--- /dev/null
+++ b/middleware/file/tree/elem.go
@@ -0,0 +1,121 @@
+package tree
+
+import (
+	"github.com/miekg/coredns/middleware"
+	"github.com/miekg/dns"
+)
+
+type Elem struct {
+	m map[uint16][]dns.RR
+}
+
+// newElem returns a new elem.
+func newElem(rr dns.RR) *Elem {
+	e := Elem{m: make(map[uint16][]dns.RR)}
+	e.m[rr.Header().Rrtype] = []dns.RR{rr}
+	return &e
+}
+
+// Types returns the RRs with type qtype from e.
+func (e *Elem) Types(qtype uint16) []dns.RR {
+	if rrs, ok := e.m[qtype]; ok {
+		return rrs
+	}
+	// nodata
+	return nil
+}
+
+// All returns all RRs from e, regardless of type.
+func (e *Elem) All() []dns.RR {
+	list := []dns.RR{}
+	for _, rrs := range e.m {
+		list = append(list, rrs...)
+	}
+	return list
+}
+
+// Name returns the name for this node.
+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
+	if e.m == nil {
+		e.m = make(map[uint16][]dns.RR)
+		e.m[t] = []dns.RR{rr}
+		return
+	}
+	rrs, ok := e.m[t]
+	if !ok {
+		e.m[t] = []dns.RR{rr}
+		return
+	}
+	for _, er := range rrs {
+		if equalRdata(er, rr) {
+			return
+		}
+	}
+
+	rrs = append(rrs, rr)
+	e.m[t] = rrs
+}
+
+// Delete removes rr from e. When e is empty after the removal the returned bool is true.
+func (e *Elem) Delete(rr dns.RR) (empty bool) {
+	if e.m == nil {
+		return true
+	}
+
+	t := rr.Header().Rrtype
+	rrs, ok := e.m[t]
+	if !ok {
+		return
+	}
+
+	for i, er := range rrs {
+		if equalRdata(er, rr) {
+			rrs = removeFromSlice(rrs, i)
+			e.m[t] = rrs
+			empty = len(rrs) == 0
+			if empty {
+				delete(e.m, t)
+			}
+			return
+		}
+	}
+	return
+}
+
+func Less(a *Elem, rr dns.RR) int {
+	return middleware.Less(rr.Header().Name, a.Name())
+}
+
+// Assuming the same type and name this will check if the rdata is equal as well.
+func equalRdata(a, b dns.RR) bool {
+	switch x := a.(type) {
+	// TODO(miek): more types, i.e. all types. + tests for this.
+	case *dns.A:
+		return x.A.Equal(b.(*dns.A).A)
+	case *dns.AAAA:
+		return x.AAAA.Equal(b.(*dns.AAAA).AAAA)
+	case *dns.MX:
+		if x.Mx == b.(*dns.MX).Mx && x.Preference == b.(*dns.MX).Preference {
+			return true
+		}
+	}
+	return false
+}
+
+// removeFromSlice removes index i from the slice.
+func removeFromSlice(rrs []dns.RR, i int) []dns.RR {
+	if i >= len(rrs) {
+		return rrs
+	}
+	rrs = append(rrs[:i], rrs[i+1:]...)
+	return rrs
+}
diff --git a/middleware/file/tree/tree.go b/middleware/file/tree/tree.go
index ca616ad67..d0ecfcd94 100644
--- a/middleware/file/tree/tree.go
+++ b/middleware/file/tree/tree.go
@@ -16,16 +16,22 @@ 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/coredns/middleware"
-	"github.com/miekg/dns"
-)
+import "github.com/miekg/dns"
 
 const (
 	TD234 = iota
 	BU23
 )
 
+// Result is a result of a Get lookup.
+type Result int
+
+const (
+	Found Result = iota
+	NameError
+	EmptyNonTerminal
+)
+
 // Operation mode of the LLRB tree.
 const Mode = BU23
 
@@ -35,119 +41,6 @@ func init() {
 	}
 }
 
-type Elem struct {
-	m map[uint16][]dns.RR
-}
-
-// newElem returns a new elem
-func newElem(rr dns.RR) *Elem {
-	e := Elem{m: make(map[uint16][]dns.RR)}
-	e.m[rr.Header().Rrtype] = []dns.RR{rr}
-	return &e
-}
-
-// Types returns the RRs with type qtype from e.
-func (e *Elem) Types(qtype uint16) []dns.RR {
-	if rrs, ok := e.m[qtype]; ok {
-		// TODO(miek): length should never be zero here.
-		return rrs
-	}
-	return nil
-}
-
-// All returns all RRs from e, regardless of type.
-func (e *Elem) All() []dns.RR {
-	list := []dns.RR{}
-	for _, rrs := range e.m {
-		list = append(list, rrs...)
-	}
-	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
-	if e.m == nil {
-		e.m = make(map[uint16][]dns.RR)
-		e.m[t] = []dns.RR{rr}
-		return
-	}
-	rrs, ok := e.m[t]
-	if !ok {
-		e.m[t] = []dns.RR{rr}
-		return
-	}
-	for _, er := range rrs {
-		if equalRdata(er, rr) {
-			return
-		}
-	}
-
-	rrs = append(rrs, rr)
-	e.m[t] = rrs
-}
-
-// Delete removes rr from e. When e is empty after the removal the returned bool is true.
-func (e *Elem) Delete(rr dns.RR) (empty bool) {
-	t := rr.Header().Rrtype
-	if e.m == nil {
-		return
-	}
-	rrs, ok := e.m[t]
-	if !ok {
-		return
-	}
-	for i, er := range rrs {
-		if equalRdata(er, rr) {
-			rrs = removeFromSlice(rrs, i)
-			e.m[t] = rrs
-			empty = len(rrs) == 0
-			if empty {
-				delete(e.m, t)
-			}
-			return
-		}
-	}
-	return
-}
-
-func Less(a *Elem, rr dns.RR) int {
-	return middleware.Less(rr.Header().Name, a.Name())
-}
-
-// Assuming the same type and name this will check if the rdata is equal as well.
-func equalRdata(a, b dns.RR) bool {
-	switch x := a.(type) {
-	// TODO(miek): more types, i.e. all types.
-	case *dns.A:
-		return x.A.Equal(b.(*dns.A).A)
-	case *dns.AAAA:
-		return x.AAAA.Equal(b.(*dns.AAAA).AAAA)
-	case *dns.MX:
-		if x.Mx == b.(*dns.MX).Mx && x.Preference == b.(*dns.MX).Preference {
-			return true
-		}
-	}
-	return false
-}
-
-// removeFromSlice removes index i from the slice.
-func removeFromSlice(rrs []dns.RR, i int) []dns.RR {
-	if i >= len(rrs) {
-		return rrs
-	}
-	rrs = append(rrs[:i], rrs[i+1:]...)
-	return rrs
-}
-
 // A Color represents the color of a Node.
 type Color bool
 
@@ -257,30 +150,36 @@ func (t *Tree) Len() int {
 }
 
 // Get returns the first match of rr in the Tree.
-func (t *Tree) Get(rr dns.RR) *Elem {
+func (t *Tree) Get(rr dns.RR) (*Elem, Result) {
 	if t.Root == nil {
-		return nil
+		return nil, NameError
 	}
-	n := t.Root.search(rr)
+	n, res := t.Root.search(rr)
 	if n == nil {
-		return nil
+		return nil, res
 	}
-	return n.Elem
+	return n.Elem, res
 }
 
-func (n *Node) search(rr dns.RR) *Node {
+func (n *Node) search(rr dns.RR) (*Node, Result) {
+	old := n
 	for n != nil {
 		switch c := Less(n.Elem, rr); {
 		case c == 0:
-			return n
+			return n, Found
 		case c < 0:
+			old = n
 			n = n.Left
 		default:
+			old = n
 			n = n.Right
 		}
 	}
+	if dns.CountLabel(rr.Header().Name) < dns.CountLabel(old.Elem.Name()) {
+		return n, EmptyNonTerminal
+	}
 
-	return n
+	return n, NameError
 }
 
 // Insert inserts rr into the Tree at the first match found
@@ -397,13 +296,13 @@ func (t *Tree) Delete(rr dns.RR) {
 	if t.Root == nil {
 		return
 	}
-	// If there is an element, remove the rr from it
-	el := t.Get(rr)
+
+	el, _ := t.Get(rr)
 	if el == nil {
 		t.DeleteNode(rr)
 		return
 	}
-	// delete from this element
+	// Delete from this element.
 	empty := el.Delete(rr)
 	if empty {
 		t.DeleteNode(rr)
@@ -454,7 +353,6 @@ func (n *Node) delete(rr dns.RR) (root *Node, d int) {
 	}
 
 	root = n.fixUp()
-
 	return
 }
 
@@ -544,33 +442,6 @@ 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.
 
diff --git a/middleware/file/wildcard_test.go b/middleware/file/wildcard_test.go
index 1dab78226..1b502acff 100644
--- a/middleware/file/wildcard_test.go
+++ b/middleware/file/wildcard_test.go
@@ -45,7 +45,7 @@ var wildcardTestCases = []coretest.Case{
 }
 
 func TestLookupWildcard(t *testing.T) {
-	zone, err := Parse(strings.NewReader(dbDnssexNl_signed), testzone1, "stdin")
+	zone, err := Parse(strings.NewReader(dbDnssexNL_signed), testzone1, "stdin")
 	if err != nil {
 		t.Fatalf("expect no error when reading zone, got %q", err)
 	}
@@ -68,41 +68,24 @@ func TestLookupWildcard(t *testing.T) {
 		sort.Sort(coretest.RRSet(resp.Ns))
 		sort.Sort(coretest.RRSet(resp.Extra))
 
-		if resp.Rcode != tc.Rcode {
-			t.Errorf("rcode is %q, expected %q", dns.RcodeToString[resp.Rcode], dns.RcodeToString[tc.Rcode])
+		if !coretest.Header(t, tc, resp) {
 			t.Logf("%v\n", resp)
 			continue
 		}
 
-		if len(resp.Answer) != len(tc.Answer) {
-			t.Errorf("answer for %q contained %d results, %d expected", tc.Qname, len(resp.Answer), len(tc.Answer))
-			t.Logf("%v\n", resp)
-			continue
-		}
-		if len(resp.Ns) != len(tc.Ns) {
-			t.Errorf("authority for %q contained %d results, %d expected", tc.Qname, len(resp.Ns), len(tc.Ns))
-			t.Logf("%v\n", resp)
-			continue
-		}
-		if len(resp.Extra) != len(tc.Extra) {
-			t.Errorf("additional for %q contained %d results, %d expected", tc.Qname, len(resp.Extra), len(tc.Extra))
-			t.Logf("%v\n", resp)
-			continue
-		}
-
-		if !coretest.CheckSection(t, tc, coretest.Answer, resp.Answer) {
+		if !coretest.Section(t, tc, coretest.Answer, resp.Answer) {
 			t.Logf("%v\n", resp)
 		}
-		if !coretest.CheckSection(t, tc, coretest.Ns, resp.Ns) {
+		if !coretest.Section(t, tc, coretest.Ns, resp.Ns) {
 			t.Logf("%v\n", resp)
 		}
-		if !coretest.CheckSection(t, tc, coretest.Extra, resp.Extra) {
+		if !coretest.Section(t, tc, coretest.Extra, resp.Extra) {
 			t.Logf("%v\n", resp)
 		}
 	}
 }
 
-const dbDnssexNl_signed = `
+const dbDnssexNL_signed = `
 ; File written on Tue Mar 29 21:02:24 2016
 ; dnssec_signzone version 9.10.3-P4-Ubuntu
 dnssex.nl.		1800	IN SOA	linode.atoom.net. miek.miek.nl. (
diff --git a/middleware/file/zone.go b/middleware/file/zone.go
index bac420669..1547a23b4 100644
--- a/middleware/file/zone.go
+++ b/middleware/file/zone.go
@@ -10,7 +10,7 @@ import (
 type Transfer struct {
 	Out bool
 	In  bool
-	// more later
+	// more later?
 }
 
 type Zone struct {
@@ -22,17 +22,16 @@ type Zone struct {
 	Transfer *Transfer
 }
 
+// NewZone returns a new zone.
 func NewZone(name string) *Zone {
 	return &Zone{name: dns.Fqdn(name), Tree: &tree.Tree{}, Transfer: &Transfer{}}
 }
 
-func (z *Zone) Insert(r dns.RR) {
-	z.Tree.Insert(r)
-}
+// Insert inserts r into z.
+func (z *Zone) Insert(r dns.RR) { z.Tree.Insert(r) }
 
-func (z *Zone) Delete(r dns.RR) {
-	z.Tree.Delete(r)
-}
+// Delete deletes r from z.
+func (z *Zone) Delete(r dns.RR) { z.Tree.Delete(r) }
 
 // It the transfer request allowed.
 func (z *Zone) TransferAllowed(state middleware.State) bool {
diff --git a/middleware/file/zone_test.go b/middleware/file/zone_test.go
index 4e3997c46..5421d1dd3 100644
--- a/middleware/file/zone_test.go
+++ b/middleware/file/zone_test.go
@@ -1,30 +1,3 @@
 package file
 
-import (
-	"testing"
-
-	"github.com/miekg/dns"
-)
-
-func TestZoneInsert(t *testing.T) {
-	z := NewZone("miek.nl")
-	rr, _ := dns.NewRR("miek.nl. IN A 127.0.0.1")
-	z.Insert(rr)
-
-	t.Logf("%+v\n", z)
-
-	elem := z.Get(rr)
-	t.Logf("%+v\n", elem)
-	if elem != nil {
-		t.Logf("%+v\n", elem.Types(dns.TypeA))
-	}
-	z.Delete(rr)
-
-	t.Logf("%+v\n", z)
-
-	elem = z.Get(rr)
-	t.Logf("%+v\n", elem)
-	if elem != nil {
-		t.Logf("%+v\n", elem.Types(dns.TypeA))
-	}
-}
+// TODO tests here.
diff --git a/middleware/testing/helpers.go b/middleware/testing/helpers.go
index dc0fa4c38..36654d7ab 100644
--- a/middleware/testing/helpers.go
+++ b/middleware/testing/helpers.go
@@ -9,10 +9,10 @@ import (
 	"golang.org/x/net/context"
 )
 
-type Section int
+type Sect int
 
 const (
-	Answer Section = iota
+	Answer Sect = iota
 	Ns
 	Extra
 )
@@ -59,7 +59,28 @@ func MX(rr string) *dns.MX       { r, _ := dns.NewRR(rr); return r.(*dns.MX) }
 func RRSIG(rr string) *dns.RRSIG { r, _ := dns.NewRR(rr); return r.(*dns.RRSIG) }
 func NSEC(rr string) *dns.NSEC   { r, _ := dns.NewRR(rr); return r.(*dns.NSEC) }
 
-func CheckSection(t *testing.T, tc Case, sect Section, rr []dns.RR) bool {
+func Header(t *testing.T, tc Case, resp *dns.Msg) bool {
+	if resp.Rcode != tc.Rcode {
+		t.Errorf("rcode is %q, expected %q", dns.RcodeToString[resp.Rcode], dns.RcodeToString[tc.Rcode])
+		return false
+	}
+
+	if len(resp.Answer) != len(tc.Answer) {
+		t.Errorf("answer for %q contained %d results, %d expected", tc.Qname, len(resp.Answer), len(tc.Answer))
+		return false
+	}
+	if len(resp.Ns) != len(tc.Ns) {
+		t.Errorf("authority for %q contained %d results, %d expected", tc.Qname, len(resp.Ns), len(tc.Ns))
+		return false
+	}
+	if len(resp.Extra) != len(tc.Extra) {
+		t.Errorf("additional for %q contained %d results, %d expected", tc.Qname, len(resp.Extra), len(tc.Extra))
+		return false
+	}
+	return true
+}
+
+func Section(t *testing.T, tc Case, sect Sect, rr []dns.RR) bool {
 	section := []dns.RR{}
 	switch sect {
 	case 0: