146 lines
3.9 KiB
Go
146 lines
3.9 KiB
Go
// Package blacklist implements the domain lookup structure used by blacklists
|
|
// and allowlists, plus the parsers for bulk imports.
|
|
//
|
|
// The matcher is built for lists with hundreds of thousands of entries. It
|
|
// stores one map entry per configured domain and answers "is this name, or any
|
|
// parent of it, listed?" by walking the name's suffixes, which is bounded by
|
|
// the label count rather than by the size of the list. Subdomain coverage
|
|
// therefore costs nothing extra: blocking example.com automatically covers
|
|
// a.b.example.com without storing a single additional row.
|
|
package blacklist
|
|
|
|
import (
|
|
"strings"
|
|
)
|
|
|
|
// Match flags stored per domain. A single map keeps the memory footprint of a
|
|
// large list to one entry per domain rather than one per match mode.
|
|
const (
|
|
flagExact uint8 = 1 << 0 // matches the domain itself only
|
|
flagSuffix uint8 = 1 << 1 // matches the domain and every subdomain
|
|
)
|
|
|
|
// Set is an immutable compiled domain list.
|
|
type Set struct {
|
|
ID int64
|
|
Name string
|
|
Kind string
|
|
domains map[string]uint8
|
|
}
|
|
|
|
// Builder accumulates domains before freezing them into a Set.
|
|
type Builder struct {
|
|
id int64
|
|
name string
|
|
kind string
|
|
domains map[string]uint8
|
|
}
|
|
|
|
// NewBuilder starts building a list. sizeHint pre-sizes the map, which matters
|
|
// when loading a list with hundreds of thousands of domains.
|
|
func NewBuilder(id int64, name, kind string, sizeHint int) *Builder {
|
|
if sizeHint < 8 {
|
|
sizeHint = 8
|
|
}
|
|
return &Builder{id: id, name: name, kind: kind, domains: make(map[string]uint8, sizeHint)}
|
|
}
|
|
|
|
// Add records one domain. The domain must already be normalised: lowercase,
|
|
// no trailing dot. A leading "*." is understood as a subdomain wildcard.
|
|
func (b *Builder) Add(domain string, matchSubdomains bool) {
|
|
domain = strings.TrimSuffix(strings.ToLower(strings.TrimSpace(domain)), ".")
|
|
if domain == "" {
|
|
return
|
|
}
|
|
if strings.HasPrefix(domain, "*.") {
|
|
domain = domain[2:]
|
|
matchSubdomains = true
|
|
if domain == "" {
|
|
return
|
|
}
|
|
}
|
|
if matchSubdomains {
|
|
b.domains[domain] |= flagSuffix | flagExact
|
|
} else {
|
|
b.domains[domain] |= flagExact
|
|
}
|
|
}
|
|
|
|
// Len reports how many distinct domains have been added.
|
|
func (b *Builder) Len() int { return len(b.domains) }
|
|
|
|
// Build freezes the builder into a Set.
|
|
func (b *Builder) Build() *Set {
|
|
return &Set{ID: b.id, Name: b.name, Kind: b.kind, domains: b.domains}
|
|
}
|
|
|
|
// Len reports the number of domains in the set.
|
|
func (s *Set) Len() int {
|
|
if s == nil {
|
|
return 0
|
|
}
|
|
return len(s.domains)
|
|
}
|
|
|
|
// Match reports whether name is covered by this list, returning the listed
|
|
// domain that matched.
|
|
//
|
|
// name may be given with or without a trailing dot and in any case.
|
|
func (s *Set) Match(name string) (string, bool) {
|
|
if s == nil || len(s.domains) == 0 {
|
|
return "", false
|
|
}
|
|
n := normaliseQuery(name)
|
|
if n == "" {
|
|
return "", false
|
|
}
|
|
|
|
// Exact match on the full name.
|
|
if f, ok := s.domains[n]; ok && f&flagExact != 0 {
|
|
return n, true
|
|
}
|
|
|
|
// Walk up the parents; each one only matches if it was added as a
|
|
// subdomain-covering entry.
|
|
rest := n
|
|
for {
|
|
i := strings.IndexByte(rest, '.')
|
|
if i < 0 {
|
|
return "", false
|
|
}
|
|
rest = rest[i+1:]
|
|
if rest == "" {
|
|
return "", false
|
|
}
|
|
if f, ok := s.domains[rest]; ok && f&flagSuffix != 0 {
|
|
return rest, true
|
|
}
|
|
}
|
|
}
|
|
|
|
// Contains reports whether the exact domain is present in the list, ignoring
|
|
// subdomain coverage. It backs the "is this already in the list?" check.
|
|
func (s *Set) Contains(domain string) bool {
|
|
if s == nil {
|
|
return false
|
|
}
|
|
_, ok := s.domains[normaliseQuery(domain)]
|
|
return ok
|
|
}
|
|
|
|
// normaliseQuery lowercases a query name and removes the trailing dot.
|
|
func normaliseQuery(name string) string {
|
|
n := strings.TrimSpace(name)
|
|
if n == "" {
|
|
return ""
|
|
}
|
|
n = strings.TrimSuffix(n, ".")
|
|
// Fast path: most query names are already lowercase.
|
|
for i := 0; i < len(n); i++ {
|
|
if c := n[i]; c >= 'A' && c <= 'Z' {
|
|
return strings.ToLower(n)
|
|
}
|
|
}
|
|
return n
|
|
}
|