// It takes a RegexTree and computes the set of chars that can start it.
541284
func getFirstCharsPrefix(tree *RegexTree) *Prefix {
	s := regexFcd{
		fcStack:  make([]regexFc, 32),
		intStack: make([]int, 32),
	}
	fc := s.regexFCFromRegexTree(tree)

	if fc == nil || fc.nullable || fc.cc.IsEmpty() {
		return nil
	}
	fcSet := fc.getFirstChars()
	return &Prefix{PrefixSet: fcSet, CaseInsensitive: fc.caseInsensitive}
}
1332790
func LiteralPrefix(s *syntax.Regexp) string {
	// traverse the left-most branch in the parse tree as long as the
	// node represents a concatenation
	for s != nil && s.Op == syntax.OpConcat {
		if len(s.Sub) < 1 {
			return ""
		}

		s = s.Sub[0]
	}

	if s.Op == syntax.OpLiteral {
		return string(s.Rune)
	}

	return "" // no literal prefix
}
756525
func (tree *tree) split(pattern string) (out []*node) {
	base := pattern
	for {
		if pattern == "" {
			break
		}
		c := pattern[0]

		var endinglabel byte

		end := strings.IndexAny(pattern, tree.Separators())
		if end < 0 {
			end = len(pattern)
			endinglabel = pattern[end-1]
		} else {
			endinglabel = pattern[end]
		}

		var child *node
		switch c {
		case tree.ParamChar():
			var l byte
			idx := strings.Index(base, pattern[:end])
			if idx > 0 {
				l = base[idx-1]
			}

			endinglabel = 0
			if len(pattern) > end {
				endinglabel = pattern[end]
			}

			child = &node{
				pattern:     pattern[:end],
				nodeType:    param,
				pname:       pattern[1:end],
				endinglabel: endinglabel,
				label:       l,
			}

			// Check if this param contains a regex definition
			parenthesisIdx := strings.Index(pattern[:end], "(")
			if parenthesisIdx > 0 { // Regex param
				startp, endp := nextParenthesis(pattern)
				child.re = regexp.MustCompile(pattern[startp+1 : endp])

				// Update child
				end = endp + 1
				child.pname = pattern[1:startp]
				child.pattern = pattern[:end]
				child.endinglabel = pattern[end-1]
			}

			out = append(out, child)
		case tree.WildcardChar():
			pname := pattern[1:]
			if pname == "" {
				pname = "*"
			}
			child = &node{
				pattern:  pattern,
				nodeType: wildcard,
				pname:    pname,
			}

			out = append(out, child)
			pattern = ""
			continue
		default:
			charIdx := stringsIndexAnyNotEscaped(pattern, tree.AllChars())
			if charIdx < 0 {
				charIdx = len(pattern)
			}

			count := strings.Count(pattern[:charIdx], `\`)
			charIdx -= count
			pattern = strings.Replace(pattern, `\`, "", count)

			end = charIdx

			cp := pattern[:end]
			endinglabel = cp[len(cp)-1]
			pattern = pattern[end:]

			child = &node{
				pattern:     cp,
				nodeType:    static,
				label:       c,
				endinglabel: endinglabel,
			}

			out = append(out, child)
			continue
		}
		pattern = pattern[end:]
	}

	return
}
921641
func MustCompile(str string, opt RegexOptions) *Regexp {
	regexp, error := Compile(str, opt)
	if error != nil {
		panic(`regexp2: Compile(` + quote(str) + `): ` + error.Error())
	}
	return regexp
}
1211717
func regexpQuery(text string, content, file bool) (Q, error) {
	var expr Q

	r, err := syntax.Parse(text, syntax.ClassNL|syntax.PerlX|syntax.UnicodeGroups)
	if err != nil {
		return nil, err
	}

	if r.Op == syntax.OpLiteral {
		expr = &Substring{
			Pattern:  string(r.Rune),
			FileName: file,
			Content:  content,
		}
	} else {
		expr = &Regexp{
			Regexp:   r,
			FileName: file,
			Content:  content,
		}
	}

	return expr, nil
}
735041
func Regexpf(t TestingT, rx interface{}, str interface{}, msg string, args ...interface{}) bool {
	if h, ok := t.(tHelper); ok {
		h.Helper()
	}
	return Regexp(t, rx, str, append([]interface{}{msg}, args...)...)
}
921256
func (t *Tree) startParse(lex *lexer) {
	t.Root = nil
	t.lex = lex
}
1074968
func (re *Regexp) FindRunesMatchStartingAt(r []rune, startAt int) (*Match, error) {
	return re.run(false, startAt, r)
}
330508
func GetRegex(pattern string) (*regexp.Regexp, error) {
	pattern = strings.Replace(pattern, ".", "\\.", -1) // Escape all '.' in the pattern
	pattern = strings.Replace(pattern, "(", "\\(", -1) // Escape all '(' in the pattern
	pattern = strings.Replace(pattern, ")", "\\)", -1) // Escape all ')' in the pattern
	pattern = strings.Replace(pattern, "*", ".*", -1)  // Replace a '*' with '.*' that matches zero or more characters
	pattern = strings.Replace(pattern, "{", "(", -1)   // Change a '{' to '('
	pattern = strings.Replace(pattern, ",", "|", -1)   // Change a ',' to '|'
	pattern = strings.Replace(pattern, "}", ")", -1)   // Change a '}' to ')'
	pattern = strings.Replace(pattern, "?", ".", -1)   // Change a '?' to '.'
	pattern = "^" + pattern + "$"
	return regexp.Compile(pattern)
}
718410
func isRegex(v interface{}) bool {
	s, ok := v.(string)
	if !ok {
		return false
	}
	_, err := regexp.Compile(s)
	return err == nil
}
343495
func Compile(expr string) (*Regexp, error) {
	re, err := syntax.Parse(expr, syntax.Perl)
	if err != nil {
		return nil, err
	}
	sre := re.Simplify()
	prog, err := syntax.Compile(sre)
	if err != nil {
		return nil, err
	}
	if err := toByteProg(prog); err != nil {
		return nil, err
	}
	r := &Regexp{
		Syntax: re,
		expr:   expr,
	}
	if err := r.m.init(prog); err != nil {
		return nil, err
	}
	return r, nil
}
692250
func IsMatches(str, pattern string) bool {
	match, _ := regexp.MatchString(pattern, str)
	return match
}
761581
func SliceMatchesRegex(input string, expressions []string) (bool, error) {
	for _, expression := range expressions {
		if !strings.HasPrefix(expression, "^") || !strings.HasSuffix(expression, "$") {
			// replace glob-style wildcards with regexp wildcards
			// for plain strings, and quote all characters that could
			// be interpreted in regular expression
			expression = "^" + GlobToRegexp(expression) + "$"
		}

		expr, err := regexp.Compile(expression)
		if err != nil {
			return false, trace.BadParameter(err.Error())
		}

		// Since the expression is always surrounded by ^ and $ this is an exact
		// match for either a a plain string (for example ^hello$) or for a regexp
		// (for example ^hel*o$).
		if expr.MatchString(input) {
			return true, nil
		}
	}

	return false, nil
}
1332130
func Parse(input string) (*Tree, error) {
	t := NewTree(bytes.NewReader([]byte(input)))
	return t, t.Parse()
}
1209039
func Grep(re, lines string) (string, error) {
	match := ""
	regex, regexErr := regexp.Compile(re)
	if regexErr != nil {
		return "", regexErr
	}

	for _, line := range strings.Split(lines, "\n") {
		if regex.MatchString(line) {
			match = match + "\n" + line
		}
	}
	return match, nil
}
242136
func init() {
	RegisterCharset(&Charset{
		Name:    "GBK",
		Aliases: []string{"GB2312"}, // GBK is a superset of GB2312.
		NewDecoder: func() Decoder {
			return decodeGBKRune
		},
		NewEncoder: func() Encoder {
			return encodeGBKRune
		},
	})
}
900792
func (p *parser) startGroup(openGroup *regexNode) {
	p.group = openGroup
	p.alternation = newRegexNode(ntAlternate, p.options)
	p.concatenation = newRegexNode(ntConcatenate, p.options)
}