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