match.go

     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  
     5  package testing
     6  
     7  import (
     8  	"fmt"
     9  	"os"
    10  	"strconv"
    11  	"strings"
    12  	"sync"
    13  )
    14  
    15  // matcher sanitizes, uniques, and filters names of subtests and subbenchmarks.
    16  type 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  
    29  type 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.
    41  type simpleMatch []string
    42  
    43  // alternationMatch matches a test name if one of the alternations match.
    44  type alternationMatch []filterMatch
    45  
    46  // TODO: fix test_main to avoid race and improve caching, also allowing to
    47  // eliminate this Mutex.
    48  var matchMutex sync.Mutex
    49  
    50  func 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  
    66  func (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.
    93  func (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  
   101  func (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  
   113  func (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  
   126  func (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  
   135  func (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  
   144  func 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.
   196  func (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).
   231  func 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.
   260  func 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  
   276  func 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
View as plain text