3 files changed, 143 insertions, 6 deletions
diff --git a/middleware/file/tree/elem.go b/middleware/file/tree/elem.go
index 6785a6849..785d64660 100644
--- a/middleware/file/tree/elem.go
+++ b/middleware/file/tree/elem.go
@@ -1,9 +1,6 @@
 package tree
 
-import (
-	"github.com/miekg/coredns/middleware"
-	"github.com/miekg/dns"
-)
+import "github.com/miekg/dns"
 
 type Elem struct {
 	m map[uint16][]dns.RR
@@ -91,8 +88,8 @@ func (e *Elem) Delete(rr dns.RR) (empty bool) {
 	return
 }
 
-// Less is a tree helper function that calls middleware.Less.
-func Less(a *Elem, name string) int { return middleware.Less(name, a.Name()) }
+// Less is a tree helper function that calls less.
+func Less(a *Elem, name string) int { return less(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 {
diff --git a/middleware/file/tree/less.go b/middleware/file/tree/less.go
new file mode 100644
index 000000000..32d87b683
--- /dev/null
+++ b/middleware/file/tree/less.go
@@ -0,0 +1,59 @@
+package tree
+
+import (
+	"bytes"
+
+	"github.com/miekg/dns"
+)
+
+// less returns <0 when a is less than b, 0 when they are equal and
+// >0 when a is larger than b.
+// 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.
+//
+// The values of a and b are *not* lowercased before the comparison!
+func less(a, b string) int {
+	i := 1
+	aj := len(a)
+	bj := len(b)
+	for {
+		ai, oka := dns.PrevLabel(a, i)
+		bi, okb := dns.PrevLabel(b, i)
+		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])
+		bb := []byte(b[bi:bj])
+		doDDD(ab)
+		doDDD(bb)
+
+		res := bytes.Compare(ab, bb)
+		if res != 0 {
+			return res
+		}
+
+		i++
+		aj, bj = ai, bi
+	}
+	return 0
+}
+
+func doDDD(b []byte) {
+	lb := len(b)
+	for i := 0; i < lb; i++ {
+		if i+3 < lb && b[i] == '\\' && isDigit(b[i+1]) && isDigit(b[i+2]) && isDigit(b[i+3]) {
+			b[i] = dddToByte(b[i:])
+			for j := i + 1; j < lb-3; j++ {
+				b[j] = b[j+3]
+			}
+			lb -= 3
+		}
+	}
+}
+
+func isDigit(b byte) bool     { return b >= '0' && b <= '9' }
+func dddToByte(s []byte) byte { return (s[1]-'0')*100 + (s[2]-'0')*10 + (s[3] - '0') }
diff --git a/middleware/file/tree/less_test.go b/middleware/file/tree/less_test.go
new file mode 100644
index 000000000..419b75c55
--- /dev/null
+++ b/middleware/file/tree/less_test.go
@@ -0,0 +1,81 @@
+package tree
+
+import (
+	"sort"
+	"strings"
+	"testing"
+)
+
+type set []string
+
+func (p set) Len() int           { return len(p) }
+func (p set) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
+func (p set) Less(i, j int) bool { d := less(p[i], p[j]); return d <= 0 }
+
+func TestLess(t *testing.T) {
+	tests := []struct {
+		in  []string
+		out []string
+	}{
+		{
+			[]string{"aaa.powerdns.de", "bbb.powerdns.net.", "xxx.powerdns.com."},
+			[]string{"xxx.powerdns.com.", "aaa.powerdns.de", "bbb.powerdns.net."},
+		},
+		{
+			[]string{"aaa.POWERDNS.de", "bbb.PoweRdnS.net.", "xxx.powerdns.com."},
+			[]string{"xxx.powerdns.com.", "aaa.POWERDNS.de", "bbb.PoweRdnS.net."},
+		},
+		{
+			[]string{"aaa.aaaa.aa.", "aa.aaa.a.", "bbb.bbbb.bb."},
+			[]string{"aa.aaa.a.", "aaa.aaaa.aa.", "bbb.bbbb.bb."},
+		},
+		{
+			[]string{"aaaaa.", "aaa.", "bbb."},
+			[]string{"aaa.", "aaaaa.", "bbb."},
+		},
+		{
+			[]string{"a.a.a.a.", "a.a.", "a.a.a."},
+			[]string{"a.a.", "a.a.a.", "a.a.a.a."},
+		},
+		{
+			[]string{"example.", "z.example.", "a.example."},
+			[]string{"example.", "a.example.", "z.example."},
+		},
+		{
+			[]string{"a.example.", "Z.a.example.", "z.example.", "yljkjljk.a.example.", "\\001.z.example.", "example.", "*.z.example.", "\\200.z.example.", "zABC.a.EXAMPLE."},
+			[]string{"example.", "a.example.", "yljkjljk.a.example.", "Z.a.example.", "zABC.a.EXAMPLE.", "z.example.", "\\001.z.example.", "*.z.example.", "\\200.z.example."},
+		},
+		{
+			// RFC3034 example.
+			[]string{"a.example.", "Z.a.example.", "z.example.", "yljkjljk.a.example.", "example.", "*.z.example.", "zABC.a.EXAMPLE."},
+			[]string{"example.", "a.example.", "yljkjljk.a.example.", "Z.a.example.", "zABC.a.EXAMPLE.", "z.example.", "*.z.example."},
+		},
+	}
+
+Tests:
+	for j, test := range tests {
+		// Need to lowercase these example as the Less function does lowercase for us anymore.
+		for i, b := range test.in {
+			test.in[i] = strings.ToLower(b)
+		}
+		for i, b := range test.out {
+			test.out[i] = strings.ToLower(b)
+		}
+
+		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])
+				n := ""
+				for k, in := range test.in {
+					if k+1 == len(test.in) {
+						n = "\n"
+					}
+					t.Logf("%s <-> %s\n%s", in, test.out[k], n)
+				}
+				continue Tests
+			}
+
+		}
+	}
+}