// MatchSubtree returns true when there is a subtree representing extensions
// to key, that is if there are any keys in the tree which have key as prefix.
193969
func (trie *Trie) MatchSubtree(key Prefix) (matched bool) {
	_, _, matched, _ = trie.findSubtree(key)
	return
}
224752
func (t *Trie) PrefixMatch(key string) []interface{} {
	node, _ := t.findNode(key)
	if node != nil {
		return t.Walk(node)
	}
	return []interface{}{}
}
1126287
func (s Selector) MatchAll(n *html.Node) []*html.Node {
	return s.matchAllInto(n, nil)
}
202960
func (this *Context) Find(re interface{}) *Context {
    r := getRegexp(re)
    matches := r.FindSubmatch(this.Bytes())
    names := make(map[string]int)

    for k, v := range r.SubexpNames() {
        if v != "" {
            names[v] = k
        }
    }

    result := &Context {
        Parent: this,
        List: matches,
        Names: names,
    }

    return result
}
130199
func MatchAny(path string, patterns []string) (bool, error) {
	for _, pattern := range patterns {
		match, err := doublestar.Match(pattern, filepath.ToSlash(path))
		if err != nil {
			return false, err
		} else if match {
			return true, nil
		}
	}
	return false, nil
}
1098129
func (t *Trie) Match(addr [16]byte) (bool, error) {
	current := t.root
	next := t.root
	for i := 0; i < 127; i++ {
		maskPosition := i % 8
		currentByte := i / 8

		left := (addr[currentByte] & singleBitMask[maskPosition]) == 0

		if left {
			next = current.children[0]
		} else {
			next = current.children[1]
		}

		if next == nil {
			return false, nil
		}

		if next.match {
			return true, nil
		}

		current = next
	}

	return false, nil
}
17139
func (node *TrieNode) Match(data []byte) *TrieNode {
	dataLen := len(data)
	suffixLen := len(node.suffix)
	if dataLen < suffixLen {
		return nil // ### return, cannot be fully matched ###
	}

	for i := 0; i < suffixLen; i++ {
		if data[i] != node.suffix[i] {
			return nil // ### return, no match ###
		}
	}

	if dataLen == suffixLen {
		if node.PathLen > 0 {
			return node // ### return, full match ###
		}
		return nil // ### return, invalid match ###
	}

	data = data[suffixLen:]
	numChildren := len(node.children)
	for i := 0; i < numChildren; i++ {
		matchedNode := node.children[i].Match(data)
		if matchedNode != nil {
			return matchedNode // ### return, match found ###
		}
	}

	return nil // ### return, no valid path ###
}
715964
func (t *docMatchTree) matches(cp *contentProvider, cost int, known map[matchTree]bool) (bool, bool) {
	return len(t.current) > 0, true
}
322523
func (pn *pathNode) match(segments []string, wildcardValues []string) (leaf *pathLeaf, wildcardMap map[string]string) {
	// Handle leaf nodes:
	if len(segments) == 0 {
		for _, leaf := range pn.leaves {
			if leaf.match(wildcardValues) {
				return leaf, makeWildcardMap(leaf, wildcardValues)
			}
		}
		return nil, nil
	}

	var seg string
	seg, segments = segments[0], segments[1:]

	subPn, ok := pn.edges[seg]
	if ok {
		leaf, wildcardMap = subPn.match(segments, wildcardValues)
	}

	if leaf == nil && pn.wildcard != nil {
		leaf, wildcardMap = pn.wildcard.match(segments, append(wildcardValues, seg))
	}

	if leaf == nil && pn.matchesFullPath {
		for _, leaf := range pn.leaves {
			if leaf.matchesFullPath && leaf.match(wildcardValues) {
				if len(wildcardValues) > 0 {
					wcVals := []string{wildcardValues[len(wildcardValues)-1], seg}
					for _, s := range segments {
						wcVals = append(wcVals, s)
					}
					wildcardValues[len(wildcardValues)-1] = strings.Join(wcVals, "/")
				}
				return leaf, makeWildcardMap(leaf, wildcardValues)
			}
		}
		return nil, nil
	}

	return leaf, wildcardMap
}
801163
func (trie *Trie) Match(prefix Prefix) (matchedExactly bool) {
	return trie.Get(prefix) != nil
}
67785
func treeCanMatchPattern(pattern string) func(name string) bool {
	wildCard := false
	if i := strings.Index(pattern, "..."); i >= 0 {
		wildCard = true
		pattern = pattern[:i]
	}
	return func(name string) bool {
		return len(name) <= len(pattern) && hasPathPrefix(pattern, name) ||
			wildCard && strings.HasPrefix(name, pattern)
	}
}
1266199
func (t *Trie) MatchPrefix(view []byte) string {
	for t != nil {
		if len(t.label) != 0 {
			return t.label
		}

		if len(view) == 0 {
			break
		}

		t = t.children[view[0]]
		view = view[1:]
	}

	return ""
}
97707
func buildAndCompareTreesFromFuzz(data []byte, proofIndex uint64) (cachedTree *Tree, numLeaves uint64) {
	hash := sha256.New()
	tree := New(hash)
	cachedTree = New(hash)
	if proofIndex != math.MaxUint64 {
		if err := cachedTree.SetIndex(proofIndex); err != nil {
			panic(err)
		}
	}

	for _, b := range data {
		b = b % 6 // should be in range [0;5]

		// if b == 0 we add the data as a leaf.
		if b == 0 {
			data := hash.Sum([]byte{byte(numLeaves)})
			tree.Push(data)
			cachedTree.Push(data)
			numLeaves++
			continue
		}
		// else we create a cached subTree of height b-1
		height := int(b - 1) // should be in range [0:4]
		subTree := New(hash)
		for i := uint64(0); i < 1<<uint64(height); i++ {
			data := hash.Sum([]byte{byte(numLeaves)})
			tree.Push(data)
			subTree.Push(data)
			numLeaves++
		}
		if err := cachedTree.PushSubTree(height, subTree.Root()); err != nil {
			return
		}
	}
	if !bytes.Equal(tree.Root(), cachedTree.Root()) {
		panic("tree roots don't match")
	}
	return
}
92644
func (s *Sublist) Match(subject string) []interface{} {
	s.RLock()
	rc, ok := s.cache[subject]
	s.RUnlock()
	if ok {
		return rc
	}

	tsa := [32]string{}
	tokens := tsa[:0]
	start := 0
	for i := 0; i < len(subject); i++ {
		if subject[i] == btsep {
			tokens = append(tokens, subject[start:i])
			start = i + 1
		}
	}
	tokens = append(tokens, subject[start:])
	result := make([]interface{}, 0, 4)

	s.Lock()
	matchLevel(s.root, tokens, &result)

	// Add to our cache
	s.cache[subject] = result
	// Bound the number of entries to sublistMaxCache
	if len(s.cache) > slCacheMax {
		for k := range s.cache {
			delete(s.cache, k)
			break
		}
	}
	s.Unlock()

	return result
}
1255689
func (r *Router) matchingPrefixInternal(ctx context.Context, path string) string {
	ns, err := namespace.FromContext(ctx)
	if err != nil {
		return ""
	}
	path = ns.Path + path

	var existing string
	fn := func(existingPath string, v interface{}) bool {
		if strings.HasPrefix(existingPath, path) {
			existing = existingPath
			return true
		}
		return false
	}
	r.root.WalkPrefix(path, fn)
	return existing
}
1008294
func (m *matcher) match(line string) *Template {
	tmpl := m.root.search(line)
	if tmpl != nil {
		return tmpl
	}
	return m.defaultTemplate
}
657988
func (s *sqlStrConcat) Match(n ast.Node, c *gosec.Context) (*gosec.Issue, error) {
	if node, ok := n.(*ast.BinaryExpr); ok {
		if start, ok := node.X.(*ast.BasicLit); ok {
			if str, e := gosec.GetString(start); e == nil {
				if !s.MatchPatterns(str) {
					return nil, nil
				}
				if _, ok := node.Y.(*ast.BasicLit); ok {
					return nil, nil // string cat OK
				}
				if second, ok := node.Y.(*ast.Ident); ok && s.checkObject(second, c) {
					return nil, nil
				}
				return gosec.NewIssue(c, n, s.ID(), s.What, s.Severity, s.Confidence), nil
			}
		}
	}
	return nil, nil
}