1package dns
2
3// Dedup removes identical RRs from rrs. It preserves the original ordering.
4// The lowest TTL of any duplicates is used in the remaining one. Dedup modifies
5// rrs.
6// m is used to store the RRs temporary. If it is nil a new map will be allocated.
7func Dedup(rrs []RR, m map[string]RR) []RR {
8	if m == nil {
9		m = make(map[string]RR)
10	}
11	// Save the keys, so we don't have to call normalizedString twice.
12	keys := make([]*string, 0, len(rrs))
13
14	for _, r := range rrs {
15		key := normalizedString(r)
16		keys = append(keys, &key)
17		if _, ok := m[key]; ok {
18			// Shortest TTL wins.
19			if m[key].Header().Ttl > r.Header().Ttl {
20				m[key].Header().Ttl = r.Header().Ttl
21			}
22			continue
23		}
24
25		m[key] = r
26	}
27	// If the length of the result map equals the amount of RRs we got,
28	// it means they were all different. We can then just return the original rrset.
29	if len(m) == len(rrs) {
30		return rrs
31	}
32
33	j := 0
34	for i, r := range rrs {
35		// If keys[i] lives in the map, we should copy and remove it.
36		if _, ok := m[*keys[i]]; ok {
37			delete(m, *keys[i])
38			rrs[j] = r
39			j++
40		}
41
42		if len(m) == 0 {
43			break
44		}
45	}
46
47	return rrs[:j]
48}
49
50// normalizedString returns a normalized string from r. The TTL
51// is removed and the domain name is lowercased. We go from this:
52// DomainName<TAB>TTL<TAB>CLASS<TAB>TYPE<TAB>RDATA to:
53// lowercasename<TAB>CLASS<TAB>TYPE...
54func normalizedString(r RR) string {
55	// A string Go DNS makes has: domainname<TAB>TTL<TAB>...
56	b := []byte(r.String())
57
58	// find the first non-escaped tab, then another, so we capture where the TTL lives.
59	esc := false
60	ttlStart, ttlEnd := 0, 0
61	for i := 0; i < len(b) && ttlEnd == 0; i++ {
62		switch {
63		case b[i] == '\\':
64			esc = !esc
65		case b[i] == '\t' && !esc:
66			if ttlStart == 0 {
67				ttlStart = i
68				continue
69			}
70			if ttlEnd == 0 {
71				ttlEnd = i
72			}
73		case b[i] >= 'A' && b[i] <= 'Z' && !esc:
74			b[i] += 32
75		default:
76			esc = false
77		}
78	}
79
80	// remove TTL.
81	copy(b[ttlStart:], b[ttlEnd:])
82	cut := ttlEnd - ttlStart
83	return string(b[:len(b)-cut])
84}
85