1// Copyright 2015 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package testing
6
7import (
8	"fmt"
9	"os"
10	"strconv"
11	"strings"
12	"sync"
13)
14
15// matcher sanitizes, uniques, and filters names of subtests and subbenchmarks.
16type matcher struct {
17	filter    filterMatch
18	matchFunc func(pat, str string) (bool, error)
19
20	mu sync.Mutex
21
22	// subNames is used to deduplicate subtest names.
23	// Each key is the subtest name joined to the deduplicated name of the parent test.
24	// Each value is the count of the number of occurrences of the given subtest name
25	// already seen.
26	subNames map[string]int32
27}
28
29type filterMatch interface {
30	// matches checks the name against the receiver's pattern strings using the
31	// given match function.
32	matches(name []string, matchString func(pat, str string) (bool, error)) (ok, partial bool)
33
34	// verify checks that the receiver's pattern strings are valid filters by
35	// calling the given match function.
36	verify(name string, matchString func(pat, str string) (bool, error)) error
37}
38
39// simpleMatch matches a test name if all of the pattern strings match in
40// sequence.
41type simpleMatch []string
42
43// alternationMatch matches a test name if one of the alternations match.
44type alternationMatch []filterMatch
45
46// TODO: fix test_main to avoid race and improve caching, also allowing to
47// eliminate this Mutex.
48var matchMutex sync.Mutex
49
50func newMatcher(matchString func(pat, str string) (bool, error), patterns, name string) *matcher {
51	var impl filterMatch
52	if patterns != "" {
53		impl = splitRegexp(patterns)
54		if err := impl.verify(name, matchString); err != nil {
55			fmt.Fprintf(os.Stderr, "testing: invalid regexp for %s\n", err)
56			os.Exit(1)
57		}
58	}
59	return &matcher{
60		filter:    impl,
61		matchFunc: matchString,
62		subNames:  map[string]int32{},
63	}
64}
65
66func (m *matcher) fullName(c *common, subname string) (name string, ok, partial bool) {
67	name = subname
68
69	m.mu.Lock()
70	defer m.mu.Unlock()
71
72	if c != nil && c.level > 0 {
73		name = m.unique(c.name, rewrite(subname))
74	}
75
76	matchMutex.Lock()
77	defer matchMutex.Unlock()
78
79	if m.filter == nil {
80		return name, true, false
81	}
82
83	// We check the full array of paths each time to allow for the case that
84	// a pattern contains a '/'.
85	elem := strings.Split(name, "/")
86	ok, partial = m.filter.matches(elem, m.matchFunc)
87	return name, ok, partial
88}
89
90// clearSubNames clears the matcher's internal state, potentially freeing
91// memory. After this is called, T.Name may return the same strings as it did
92// for earlier subtests.
93func (m *matcher) clearSubNames() {
94	m.mu.Lock()
95	defer m.mu.Unlock()
96	for key := range m.subNames {
97		delete(m.subNames, key)
98	}
99}
100
101func (m simpleMatch) matches(name []string, matchString func(pat, str string) (bool, error)) (ok, partial bool) {
102	for i, s := range name {
103		if i >= len(m) {
104			break
105		}
106		if ok, _ := matchString(m[i], s); !ok {
107			return false, false
108		}
109	}
110	return true, len(name) < len(m)
111}
112
113func (m simpleMatch) verify(name string, matchString func(pat, str string) (bool, error)) error {
114	for i, s := range m {
115		m[i] = rewrite(s)
116	}
117	// Verify filters before doing any processing.
118	for i, s := range m {
119		if _, err := matchString(s, "non-empty"); err != nil {
120			return fmt.Errorf("element %d of %s (%q): %s", i, name, s, err)
121		}
122	}
123	return nil
124}
125
126func (m alternationMatch) matches(name []string, matchString func(pat, str string) (bool, error)) (ok, partial bool) {
127	for _, m := range m {
128		if ok, partial = m.matches(name, matchString); ok {
129			return ok, partial
130		}
131	}
132	return false, false
133}
134
135func (m alternationMatch) verify(name string, matchString func(pat, str string) (bool, error)) error {
136	for i, m := range m {
137		if err := m.verify(name, matchString); err != nil {
138			return fmt.Errorf("alternation %d of %s", i, err)
139		}
140	}
141	return nil
142}
143
144func splitRegexp(s string) filterMatch {
145	a := make(simpleMatch, 0, strings.Count(s, "/"))
146	b := make(alternationMatch, 0, strings.Count(s, "|"))
147	cs := 0
148	cp := 0
149	for i := 0; i < len(s); {
150		switch s[i] {
151		case '[':
152			cs++
153		case ']':
154			if cs--; cs < 0 { // An unmatched ']' is legal.
155				cs = 0
156			}
157		case '(':
158			if cs == 0 {
159				cp++
160			}
161		case ')':
162			if cs == 0 {
163				cp--
164			}
165		case '\\':
166			i++
167		case '/':
168			if cs == 0 && cp == 0 {
169				a = append(a, s[:i])
170				s = s[i+1:]
171				i = 0
172				continue
173			}
174		case '|':
175			if cs == 0 && cp == 0 {
176				a = append(a, s[:i])
177				s = s[i+1:]
178				i = 0
179				b = append(b, a)
180				a = make(simpleMatch, 0, len(a))
181				continue
182			}
183		}
184		i++
185	}
186
187	a = append(a, s)
188	if len(b) == 0 {
189		return a
190	}
191	return append(b, a)
192}
193
194// unique creates a unique name for the given parent and subname by affixing it
195// with one or more counts, if necessary.
196func (m *matcher) unique(parent, subname string) string {
197	base := parent + "/" + subname
198
199	for {
200		n := m.subNames[base]
201		if n < 0 {
202			panic("subtest count overflow")
203		}
204		m.subNames[base] = n + 1
205
206		if n == 0 && subname != "" {
207			prefix, nn := parseSubtestNumber(base)
208			if len(prefix) < len(base) && nn < m.subNames[prefix] {
209				// This test is explicitly named like "parent/subname#NN",
210				// and #NN was already used for the NNth occurrence of "parent/subname".
211				// Loop to add a disambiguating suffix.
212				continue
213			}
214			return base
215		}
216
217		name := fmt.Sprintf("%s#%02d", base, n)
218		if m.subNames[name] != 0 {
219			// This is the nth occurrence of base, but the name "parent/subname#NN"
220			// collides with the first occurrence of a subtest *explicitly* named
221			// "parent/subname#NN". Try the next number.
222			continue
223		}
224
225		return name
226	}
227}
228
229// parseSubtestNumber splits a subtest name into a "#%02d"-formatted int32
230// suffix (if present), and a prefix preceding that suffix (always).
231func parseSubtestNumber(s string) (prefix string, nn int32) {
232	i := strings.LastIndex(s, "#")
233	if i < 0 {
234		return s, 0
235	}
236
237	prefix, suffix := s[:i], s[i+1:]
238	if len(suffix) < 2 || (len(suffix) > 2 && suffix[0] == '0') {
239		// Even if suffix is numeric, it is not a possible output of a "%02" format
240		// string: it has either too few digits or too many leading zeroes.
241		return s, 0
242	}
243	if suffix == "00" {
244		if !strings.HasSuffix(prefix, "/") {
245			// We only use "#00" as a suffix for subtests named with the empty
246			// string — it isn't a valid suffix if the subtest name is non-empty.
247			return s, 0
248		}
249	}
250
251	n, err := strconv.ParseInt(suffix, 10, 32)
252	if err != nil || n < 0 {
253		return s, 0
254	}
255	return prefix, int32(n)
256}
257
258// rewrite rewrites a subname to having only printable characters and no white
259// space.
260func rewrite(s string) string {
261	b := []byte{}
262	for _, r := range s {
263		switch {
264		case isSpace(r):
265			b = append(b, '_')
266		case !strconv.IsPrint(r):
267			s := strconv.QuoteRune(r)
268			b = append(b, s[1:len(s)-1]...)
269		default:
270			b = append(b, string(r)...)
271		}
272	}
273	return string(b)
274}
275
276func isSpace(r rune) bool {
277	if r < 0x2000 {
278		switch r {
279		// Note: not the same as Unicode Z class.
280		case '\t', '\n', '\v', '\f', '\r', ' ', 0x85, 0xA0, 0x1680:
281			return true
282		}
283	} else {
284		if r <= 0x200a {
285			return true
286		}
287		switch r {
288		case 0x2028, 0x2029, 0x202f, 0x205f, 0x3000:
289			return true
290		}
291	}
292	return false
293}
294