publicsuffix: hold icann-ness until wildcards fully match
Consider the "uberspace.de" domain. The relevant rules in the Public
Suffix List are "*.uberspace.de" (in the PRVIATE DOMAIN section) and
"de" (in the ICANN DOMAIN section).
The PublicSuffix function returns a string and a bool. Both before and
after this commit, the string returned is "de", which is correct
according to a literal interpretation of the formal algorithm. But the
bool returned, icann-ness, is false before and true after. The correct
answer is true, since the matching rule, "de", is in the ICANN DOMAIN
section of the PSL.
Before this commit, the two-stage match for "*.uberspace" set the icann
bit when matching the back part, "uberspace", before checking that the
front part, the "*" wildcard, also matched.
A couple more examples, for the "bd" and "ck" domains. The relevant
rules are "*.bd" and "*.ck", with no non-wildcard "bd" or "ck" rule.
Before this commit, the PublicSuffix function would return (icann ==
true), when the correct result is (icann == false), the same as for
"nosuchtld".
Benchmarks get worse, but correctness trumps performance. Future commits
may be able to recover some of the loss. In any case, in absolute terms,
15µs is still pretty fast.
name old time/op new time/op delta
PublicSuffix-56 11.0µs ± 0% 14.8µs ± 2% +34.57% (p=0.000 n=9+10)
Change-Id: I85ca6ab57a31308af5a29c46313197897eab5ab6
Reviewed-on: https://go-review.googlesource.com/c/154977
Reviewed-by: Nigel Tao <nigeltao@golang.org>
diff --git a/publicsuffix/gen.go b/publicsuffix/gen.go
index f85a3c3..372ffbb 100644
--- a/publicsuffix/gen.go
+++ b/publicsuffix/gen.go
@@ -100,6 +100,7 @@
labelsList = []string{}
labelsMap = map[string]bool{}
rules = []string{}
+ numICANNRules = 0
// validSuffixRE is used to check that the entries in the public suffix
// list are in canonical form (after Punycode encoding). Specifically,
@@ -167,11 +168,14 @@
}
s = strings.TrimSpace(s)
if strings.Contains(s, "BEGIN ICANN DOMAINS") {
+ if len(rules) != 0 {
+ return fmt.Errorf(`expected no rules before "BEGIN ICANN DOMAINS"`)
+ }
icann = true
continue
}
if strings.Contains(s, "END ICANN DOMAINS") {
- icann = false
+ icann, numICANNRules = false, len(rules)
continue
}
if s == "" || strings.HasPrefix(s, "//") {
@@ -287,7 +291,7 @@
func printTest(w io.Writer, n *node) error {
fmt.Fprintf(w, "// generated by go run gen.go; DO NOT EDIT\n\n")
- fmt.Fprintf(w, "package publicsuffix\n\nvar rules = [...]string{\n")
+ fmt.Fprintf(w, "package publicsuffix\n\nconst numICANNRules = %d\n\nvar rules = [...]string{\n", numICANNRules)
for _, rule := range rules {
fmt.Fprintf(w, "%q,\n", rule)
}
diff --git a/publicsuffix/list.go b/publicsuffix/list.go
index be9a9b7..8405ac1 100644
--- a/publicsuffix/list.go
+++ b/publicsuffix/list.go
@@ -84,11 +84,12 @@
// https://wiki.mozilla.org/Public_Suffix_List/Use_Cases
func PublicSuffix(domain string) (publicSuffix string, icann bool) {
lo, hi := uint32(0), uint32(numTLD)
- s, suffix, wildcard := domain, len(domain), false
+ s, suffix, icannNode, wildcard := domain, len(domain), false, false
loop:
for {
dot := strings.LastIndex(s, ".")
if wildcard {
+ icann = icannNode
suffix = 1 + dot
}
if lo == hi {
@@ -100,7 +101,7 @@
}
u := nodes[f] >> (nodesBitsTextOffset + nodesBitsTextLength)
- icann = u&(1<<nodesBitsICANN-1) != 0
+ icannNode = u&(1<<nodesBitsICANN-1) != 0
u >>= nodesBitsICANN
u = children[u&(1<<nodesBitsChildren-1)]
lo = u & (1<<childrenBitsLo - 1)
@@ -116,6 +117,9 @@
}
u >>= childrenBitsNodeType
wildcard = u&(1<<childrenBitsWildcard-1) != 0
+ if !wildcard {
+ icann = icannNode
+ }
if dot == -1 {
break
diff --git a/publicsuffix/list_test.go b/publicsuffix/list_test.go
index 42d79cc..98f8442 100644
--- a/publicsuffix/list_test.go
+++ b/publicsuffix/list_test.go
@@ -79,10 +79,12 @@
}
var publicSuffixTestCases = []struct {
- domain, want string
+ domain string
+ wantPS string
+ wantICANN bool
}{
// Empty string.
- {"", ""},
+ {"", "", false},
// The .ao rules are:
// ao
@@ -92,11 +94,11 @@
// co.ao
// pb.ao
// it.ao
- {"ao", "ao"},
- {"www.ao", "ao"},
- {"pb.ao", "pb.ao"},
- {"www.pb.ao", "pb.ao"},
- {"www.xxx.yyy.zzz.pb.ao", "pb.ao"},
+ {"ao", "ao", true},
+ {"www.ao", "ao", true},
+ {"pb.ao", "pb.ao", true},
+ {"www.pb.ao", "pb.ao", true},
+ {"www.xxx.yyy.zzz.pb.ao", "pb.ao", true},
// The .ar rules are:
// ar
@@ -109,19 +111,19 @@
// net.ar
// org.ar
// tur.ar
- // blogspot.com.ar
- {"ar", "ar"},
- {"www.ar", "ar"},
- {"nic.ar", "ar"},
- {"www.nic.ar", "ar"},
- {"com.ar", "com.ar"},
- {"www.com.ar", "com.ar"},
- {"blogspot.com.ar", "blogspot.com.ar"},
- {"www.blogspot.com.ar", "blogspot.com.ar"},
- {"www.xxx.yyy.zzz.blogspot.com.ar", "blogspot.com.ar"},
- {"logspot.com.ar", "com.ar"},
- {"zlogspot.com.ar", "com.ar"},
- {"zblogspot.com.ar", "com.ar"},
+ // blogspot.com.ar (in the PRIVATE DOMAIN section).
+ {"ar", "ar", true},
+ {"www.ar", "ar", true},
+ {"nic.ar", "ar", true},
+ {"www.nic.ar", "ar", true},
+ {"com.ar", "com.ar", true},
+ {"www.com.ar", "com.ar", true},
+ {"blogspot.com.ar", "blogspot.com.ar", false}, // PRIVATE DOMAIN.
+ {"www.blogspot.com.ar", "blogspot.com.ar", false}, // PRIVATE DOMAIN.
+ {"www.xxx.yyy.zzz.blogspot.com.ar", "blogspot.com.ar", false}, // PRIVATE DOMAIN.
+ {"logspot.com.ar", "com.ar", true},
+ {"zlogspot.com.ar", "com.ar", true},
+ {"zblogspot.com.ar", "com.ar", true},
// The .arpa rules are:
// arpa
@@ -131,11 +133,11 @@
// iris.arpa
// uri.arpa
// urn.arpa
- {"arpa", "arpa"},
- {"www.arpa", "arpa"},
- {"urn.arpa", "urn.arpa"},
- {"www.urn.arpa", "urn.arpa"},
- {"www.xxx.yyy.zzz.urn.arpa", "urn.arpa"},
+ {"arpa", "arpa", true},
+ {"www.arpa", "arpa", true},
+ {"urn.arpa", "urn.arpa", true},
+ {"www.urn.arpa", "urn.arpa", true},
+ {"www.xxx.yyy.zzz.urn.arpa", "urn.arpa", true},
// The relevant {kobe,kyoto}.jp rules are:
// jp
@@ -143,18 +145,18 @@
// !city.kobe.jp
// kyoto.jp
// ide.kyoto.jp
- {"jp", "jp"},
- {"kobe.jp", "jp"},
- {"c.kobe.jp", "c.kobe.jp"},
- {"b.c.kobe.jp", "c.kobe.jp"},
- {"a.b.c.kobe.jp", "c.kobe.jp"},
- {"city.kobe.jp", "kobe.jp"},
- {"www.city.kobe.jp", "kobe.jp"},
- {"kyoto.jp", "kyoto.jp"},
- {"test.kyoto.jp", "kyoto.jp"},
- {"ide.kyoto.jp", "ide.kyoto.jp"},
- {"b.ide.kyoto.jp", "ide.kyoto.jp"},
- {"a.b.ide.kyoto.jp", "ide.kyoto.jp"},
+ {"jp", "jp", true},
+ {"kobe.jp", "jp", true},
+ {"c.kobe.jp", "c.kobe.jp", true},
+ {"b.c.kobe.jp", "c.kobe.jp", true},
+ {"a.b.c.kobe.jp", "c.kobe.jp", true},
+ {"city.kobe.jp", "kobe.jp", true},
+ {"www.city.kobe.jp", "kobe.jp", true},
+ {"kyoto.jp", "kyoto.jp", true},
+ {"test.kyoto.jp", "kyoto.jp", true},
+ {"ide.kyoto.jp", "ide.kyoto.jp", true},
+ {"b.ide.kyoto.jp", "ide.kyoto.jp", true},
+ {"a.b.ide.kyoto.jp", "ide.kyoto.jp", true},
// The .tw rules are:
// tw
@@ -172,17 +174,17 @@
// 組織.tw (xn--uc0atv.tw)
// 商業.tw (xn--czrw28b.tw)
// blogspot.tw
- {"tw", "tw"},
- {"aaa.tw", "tw"},
- {"www.aaa.tw", "tw"},
- {"xn--czrw28b.aaa.tw", "tw"},
- {"edu.tw", "edu.tw"},
- {"www.edu.tw", "edu.tw"},
- {"xn--czrw28b.edu.tw", "edu.tw"},
- {"xn--czrw28b.tw", "xn--czrw28b.tw"},
- {"www.xn--czrw28b.tw", "xn--czrw28b.tw"},
- {"xn--uc0atv.xn--czrw28b.tw", "xn--czrw28b.tw"},
- {"xn--kpry57d.tw", "tw"},
+ {"tw", "tw", true},
+ {"aaa.tw", "tw", true},
+ {"www.aaa.tw", "tw", true},
+ {"xn--czrw28b.aaa.tw", "tw", true},
+ {"edu.tw", "edu.tw", true},
+ {"www.edu.tw", "edu.tw", true},
+ {"xn--czrw28b.edu.tw", "edu.tw", true},
+ {"xn--czrw28b.tw", "xn--czrw28b.tw", true},
+ {"www.xn--czrw28b.tw", "xn--czrw28b.tw", true},
+ {"xn--uc0atv.xn--czrw28b.tw", "xn--czrw28b.tw", true},
+ {"xn--kpry57d.tw", "tw", true},
// The .uk rules are:
// uk
@@ -197,37 +199,91 @@
// plc.uk
// police.uk
// *.sch.uk
- // blogspot.co.uk
- {"uk", "uk"},
- {"aaa.uk", "uk"},
- {"www.aaa.uk", "uk"},
- {"mod.uk", "uk"},
- {"www.mod.uk", "uk"},
- {"sch.uk", "uk"},
- {"mod.sch.uk", "mod.sch.uk"},
- {"www.sch.uk", "www.sch.uk"},
- {"blogspot.co.uk", "blogspot.co.uk"},
- {"blogspot.nic.uk", "uk"},
- {"blogspot.sch.uk", "blogspot.sch.uk"},
+ // blogspot.co.uk (in the PRIVATE DOMAIN section).
+ {"uk", "uk", true},
+ {"aaa.uk", "uk", true},
+ {"www.aaa.uk", "uk", true},
+ {"mod.uk", "uk", true},
+ {"www.mod.uk", "uk", true},
+ {"sch.uk", "uk", true},
+ {"mod.sch.uk", "mod.sch.uk", true},
+ {"www.sch.uk", "www.sch.uk", true},
+ {"co.uk", "co.uk", true},
+ {"www.co.uk", "co.uk", true},
+ {"blogspot.co.uk", "blogspot.co.uk", false}, // PRIVATE DOMAIN.
+ {"blogspot.nic.uk", "uk", true},
+ {"blogspot.sch.uk", "blogspot.sch.uk", true},
// The .рф rules are
// рф (xn--p1ai)
- {"xn--p1ai", "xn--p1ai"},
- {"aaa.xn--p1ai", "xn--p1ai"},
- {"www.xxx.yyy.xn--p1ai", "xn--p1ai"},
+ {"xn--p1ai", "xn--p1ai", true},
+ {"aaa.xn--p1ai", "xn--p1ai", true},
+ {"www.xxx.yyy.xn--p1ai", "xn--p1ai", true},
// The .bd rules are:
// *.bd
- {"bd", "bd"},
- {"www.bd", "www.bd"},
- {"zzz.bd", "zzz.bd"},
- {"www.zzz.bd", "zzz.bd"},
- {"www.xxx.yyy.zzz.bd", "zzz.bd"},
+ {"bd", "bd", false}, // The catch-all "*" rule is not in the ICANN DOMAIN section. See footnote (†).
+ {"www.bd", "www.bd", true},
+ {"xxx.www.bd", "www.bd", true},
+ {"zzz.bd", "zzz.bd", true},
+ {"www.zzz.bd", "zzz.bd", true},
+ {"www.xxx.yyy.zzz.bd", "zzz.bd", true},
+
+ // The .ck rules are:
+ // *.ck
+ // !www.ck
+ {"ck", "ck", false}, // The catch-all "*" rule is not in the ICANN DOMAIN section. See footnote (†).
+ {"www.ck", "ck", true},
+ {"xxx.www.ck", "ck", true},
+ {"zzz.ck", "zzz.ck", true},
+ {"www.zzz.ck", "zzz.ck", true},
+ {"www.xxx.yyy.zzz.ck", "zzz.ck", true},
+
+ // The .myjino.ru rules (in the PRIVATE DOMAIN section) are:
+ // myjino.ru
+ // *.hosting.myjino.ru
+ // *.landing.myjino.ru
+ // *.spectrum.myjino.ru
+ // *.vps.myjino.ru
+ {"myjino.ru", "myjino.ru", false},
+ {"aaa.myjino.ru", "myjino.ru", false},
+ {"bbb.ccc.myjino.ru", "myjino.ru", false},
+ {"hosting.ddd.myjino.ru", "myjino.ru", false},
+ {"landing.myjino.ru", "myjino.ru", false},
+ {"www.landing.myjino.ru", "www.landing.myjino.ru", false},
+ {"spectrum.vps.myjino.ru", "spectrum.vps.myjino.ru", false},
+
+ // The .uberspace.de rules (in the PRIVATE DOMAIN section) are:
+ // *.uberspace.de
+ {"uberspace.de", "de", true}, // "de" is in the ICANN DOMAIN section. See footnote (†).
+ {"aaa.uberspace.de", "aaa.uberspace.de", false},
+ {"bbb.ccc.uberspace.de", "ccc.uberspace.de", false},
// There are no .nosuchtld rules.
- {"nosuchtld", "nosuchtld"},
- {"foo.nosuchtld", "nosuchtld"},
- {"bar.foo.nosuchtld", "nosuchtld"},
+ {"nosuchtld", "nosuchtld", false},
+ {"foo.nosuchtld", "nosuchtld", false},
+ {"bar.foo.nosuchtld", "nosuchtld", false},
+
+ // (†) There is some disagreement on how wildcards behave: what should the
+ // public suffix of "platform.sh" be when both "*.platform.sh" and "sh" is
+ // in the PSL, but "platform.sh" is not? Two possible answers are
+ // "platform.sh" and "sh", there are valid arguments for either behavior,
+ // and different browsers have implemented different behaviors.
+ //
+ // This implementation, Go's golang.org/x/net/publicsuffix, returns "sh",
+ // the same as a literal interpretation of the "Formal Algorithm" section
+ // of https://publicsuffix.org/list/
+ //
+ // Together, the TestPublicSuffix and TestSlowPublicSuffix tests check that
+ // the Go implementation (func PublicSuffix in list.go) and the literal
+ // interpretation (func slowPublicSuffix in list_test.go) produce the same
+ // (golden) results on every test case in this publicSuffixTestCases slice,
+ // including some "platform.sh" style cases.
+ //
+ // More discussion of "the platform.sh problem" is at:
+ // - https://github.com/publicsuffix/list/issues/694
+ // - https://bugzilla.mozilla.org/show_bug.cgi?id=1124625#c6
+ // - https://wiki.mozilla.org/Public_Suffix_List/platform.sh_Problem
}
func BenchmarkPublicSuffix(b *testing.B) {
@@ -240,22 +296,44 @@
func TestPublicSuffix(t *testing.T) {
for _, tc := range publicSuffixTestCases {
- got := List.PublicSuffix(tc.domain)
- if got != tc.want {
- t.Errorf("%q: got %q, want %q", tc.domain, got, tc.want)
+ gotPS, gotICANN := PublicSuffix(tc.domain)
+ if gotPS != tc.wantPS || gotICANN != tc.wantICANN {
+ t.Errorf("%q: got (%q, %t), want (%q, %t)", tc.domain, gotPS, gotICANN, tc.wantPS, tc.wantICANN)
}
}
}
func TestSlowPublicSuffix(t *testing.T) {
for _, tc := range publicSuffixTestCases {
- got := slowPublicSuffix(tc.domain)
- if got != tc.want {
- t.Errorf("%q: got %q, want %q", tc.domain, got, tc.want)
+ gotPS, gotICANN := slowPublicSuffix(tc.domain)
+ if gotPS != tc.wantPS || gotICANN != tc.wantICANN {
+ t.Errorf("%q: got (%q, %t), want (%q, %t)", tc.domain, gotPS, gotICANN, tc.wantPS, tc.wantICANN)
}
}
}
+func TestNumICANNRules(t *testing.T) {
+ if numICANNRules <= 0 {
+ t.Fatal("no ICANN rules")
+ }
+ if numICANNRules >= len(rules) {
+ t.Fatal("no Private rules")
+ }
+ // Check the last ICANN and first Private rules. If the underlying public
+ // suffix list changes, we may need to update these hard-coded checks.
+ if got, want := rules[numICANNRules-1], "zuerich"; got != want {
+ t.Errorf("last ICANN rule: got %q, wawnt %q", got, want)
+ }
+ if got, want := rules[numICANNRules], "cc.ua"; got != want {
+ t.Errorf("first Private rule: got %q, wawnt %q", got, want)
+ }
+}
+
+type slowPublicSuffixRule struct {
+ ruleParts []string
+ icann bool
+}
+
// slowPublicSuffix implements the canonical (but O(number of rules)) public
// suffix algorithm described at http://publicsuffix.org/list/.
//
@@ -269,7 +347,7 @@
//
// This function returns the public suffix, not the registrable domain, and so
// it stops after step 6.
-func slowPublicSuffix(domain string) string {
+func slowPublicSuffix(domain string) (string, bool) {
match := func(rulePart, domainPart string) bool {
switch rulePart[0] {
case '*':
@@ -281,10 +359,10 @@
}
domainParts := strings.Split(domain, ".")
- var matchingRules [][]string
+ var matchingRules []slowPublicSuffixRule
loop:
- for _, rule := range rules {
+ for i, rule := range rules {
ruleParts := strings.Split(rule, ".")
if len(domainParts) < len(ruleParts) {
continue
@@ -296,36 +374,43 @@
continue loop
}
}
- matchingRules = append(matchingRules, ruleParts)
+ matchingRules = append(matchingRules, slowPublicSuffixRule{
+ ruleParts: ruleParts,
+ icann: i < numICANNRules,
+ })
}
if len(matchingRules) == 0 {
- matchingRules = append(matchingRules, []string{"*"})
+ matchingRules = append(matchingRules, slowPublicSuffixRule{
+ ruleParts: []string{"*"},
+ icann: false,
+ })
} else {
sort.Sort(byPriority(matchingRules))
}
+
prevailing := matchingRules[0]
- if prevailing[0][0] == '!' {
- prevailing = prevailing[1:]
+ if prevailing.ruleParts[0][0] == '!' {
+ prevailing.ruleParts = prevailing.ruleParts[1:]
}
- if prevailing[0][0] == '*' {
- replaced := domainParts[len(domainParts)-len(prevailing)]
- prevailing = append([]string{replaced}, prevailing[1:]...)
+ if prevailing.ruleParts[0][0] == '*' {
+ replaced := domainParts[len(domainParts)-len(prevailing.ruleParts)]
+ prevailing.ruleParts = append([]string{replaced}, prevailing.ruleParts[1:]...)
}
- return strings.Join(prevailing, ".")
+ return strings.Join(prevailing.ruleParts, "."), prevailing.icann
}
-type byPriority [][]string
+type byPriority []slowPublicSuffixRule
func (b byPriority) Len() int { return len(b) }
func (b byPriority) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
func (b byPriority) Less(i, j int) bool {
- if b[i][0][0] == '!' {
+ if b[i].ruleParts[0][0] == '!' {
return true
}
- if b[j][0][0] == '!' {
+ if b[j].ruleParts[0][0] == '!' {
return false
}
- return len(b[i]) > len(b[j])
+ return len(b[i].ruleParts) > len(b[j].ruleParts)
}
// eTLDPlusOneTestCases come from
diff --git a/publicsuffix/table_test.go b/publicsuffix/table_test.go
index d2c4ea9..97ca2c9 100644
--- a/publicsuffix/table_test.go
+++ b/publicsuffix/table_test.go
@@ -2,6 +2,8 @@
package publicsuffix
+const numICANNRules = 7334
+
var rules = [...]string{
"ac",
"com.ac",
