From 6d8bc3c6cbffdf42f60080779b9f6d6da0e6d1a3 Mon Sep 17 00:00:00 2001
From: bert hubert <bert.hubert@netherlabs.nl>
Date: Tue, 16 Jun 2015 13:14:32 +0200
Subject: [PATCH] implement a canonical ordering mode for DNSName plus add
 testcases for it. Preliminary slow but correct implementation.

---
 pdns/dnsname.cc         |  8 ++++++++
 pdns/dnsname.hh         | 14 ++++++++++++--
 pdns/test-dnsname_cc.cc | 35 +++++++++++++++++++++++++++++++++++
 3 files changed, 55 insertions(+), 2 deletions(-)

diff --git a/pdns/dnsname.cc b/pdns/dnsname.cc
index a3d2778e9..85f5c277f 100644
--- a/pdns/dnsname.cc
+++ b/pdns/dnsname.cc
@@ -1,6 +1,7 @@
 #include "dnsname.hh"
 #include <boost/format.hpp>
 #include <string>
+
 #include "dnswriter.hh"
 
 /* raw storage
@@ -143,6 +144,13 @@ vector<string> DNSName::getRawLabels() const
   return ret;
 }
 
+
+bool DNSName::canonCompare(const DNSName& rhs) const
+{
+  auto ours=getRawLabels(), rhsLabels = rhs.getRawLabels();
+  return std::lexicographical_compare(ours.rbegin(), ours.rend(), rhsLabels.rbegin(), rhsLabels.rend(), CIStringCompare());
+}
+
 bool DNSName::chopOff() 
 {
   if(d_storage.empty())
diff --git a/pdns/dnsname.hh b/pdns/dnsname.hh
index de5623502..542c85fa3 100644
--- a/pdns/dnsname.hh
+++ b/pdns/dnsname.hh
@@ -47,15 +47,17 @@ public:
     return *this;
   }
 
-  bool operator<(const DNSName& rhs)  const
+  bool operator<(const DNSName& rhs)  const // this delivers _some_ kind of ordering, but not one useful in a DNS context. Really fast though.
   {
     return std::lexicographical_compare(d_storage.rbegin(), d_storage.rend(), 
 				 rhs.d_storage.rbegin(), rhs.d_storage.rend(),
 				 [](const char& a, const char& b) {
 					  return tolower(a) < tolower(b); 
-				 });
+					}); // note that this is case insensitive, including on the label lengths
   }
 
+  bool canonCompare(const DNSName& rhs) const;
+  
 private:
   //  typedef __gnu_cxx::__sso_string string_t;
   typedef std::string string_t;
@@ -67,6 +69,14 @@ private:
   static std::string unescapeLabel(const std::string& orig);
 };
 
+struct CanonDNSNameCompare: public std::binary_function<DNSName, DNSName, bool>
+{
+  bool operator()(const DNSName&a, const DNSName& b) const
+  {
+    return a.canonCompare(b);
+  }
+};
+
 inline DNSName operator+(const DNSName& lhs, const DNSName& rhs)
 {
   DNSName ret=lhs;
diff --git a/pdns/test-dnsname_cc.cc b/pdns/test-dnsname_cc.cc
index a457a9e12..1c5806631 100644
--- a/pdns/test-dnsname_cc.cc
+++ b/pdns/test-dnsname_cc.cc
@@ -267,8 +267,42 @@ BOOST_AUTO_TEST_CASE(test_suffixmatch) {
 
   smn.add(DNSName()); // block the root
   BOOST_CHECK(smn.check(DNSName("a.root-servers.net.")));
+}
+
+
+BOOST_AUTO_TEST_CASE(test_concat) {
+  DNSName first("www."), second("powerdns.com.");
+  BOOST_CHECK_EQUAL((first+second).toString(), "www.powerdns.com.");
+}
+
+BOOST_AUTO_TEST_CASE(test_compare_naive) {
+  BOOST_CHECK(DNSName("abc.com.") < DNSName("zdf.com."));
+  BOOST_CHECK(DNSName("Abc.com.") < DNSName("zdf.com."));
+  BOOST_CHECK(DNSName("Abc.com.") < DNSName("Zdf.com."));
+  BOOST_CHECK(DNSName("abc.com.") < DNSName("Zdf.com."));
+}
+
+BOOST_AUTO_TEST_CASE(test_compare_canonical) {
+  DNSName lower("bert.com."), higher("alpha.nl.");
+  BOOST_CHECK(lower.canonCompare(higher));
+
 
+  vector<DNSName> vec({"bert.com.", "alpha.nl.", "articles.xxx.",
+	"Aleph1.powerdns.com.", "ZOMG.powerdns.com.", "aaa.XXX.", "yyy.XXX.", 
+	"test.powerdns.com."});
+  sort(vec.begin(), vec.end(), CanonDNSNameCompare());
+  //  for(const auto& v : vec)
+  //  cerr<<'"'<<v.toString()<<'"'<<endl;
 
+  vector<DNSName> right({"bert.com.",  "Aleph1.powerdns.com.",
+	"test.powerdns.com.",
+	"ZOMG.powerdns.com.",
+	"alpha.nl.",
+	"aaa.XXX.",
+	"articles.xxx.",
+	"yyy.XXX."});
+
+  BOOST_CHECK(vec==right);
 }
 
 
@@ -366,6 +400,7 @@ BOOST_AUTO_TEST_CASE(test_name_length_too_long) { // 256 char name
   }
 }
 
+
 BOOST_AUTO_TEST_CASE(test_invalid_label_length) { // Invalid label length in qname
 
   string name("\x02""ns\x07""example\x04""com\x00", 16);
-- 
2.50.0