regexp.go

// Copyright 2011 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package index

import (
	"regexp/syntax"
	"sort"
	"strconv"
	"strings"
	"unicode"
)

// A Query is a matching machine, like a regular expression,
// that matches some text and not other text.  When we compute a
// Query from a regexp, the Query is a conservative version of the
// regexp: it matches everything the regexp would match, and probably
// quite a bit more.  We can then filter target files by whether they match
// the Query (using a trigram index) before running the comparatively
// more expensive regexp machinery.
type Query struct {
	Op      QueryOp
	Trigram []string
	Sub     []*Query
}

type QueryOp int

const (
	QAll  QueryOp = iota // Everything matches
	QNone                // Nothing matches
	QAnd                 // All in Sub and Trigram must match
	QOr                  // At least one in Sub or Trigram must match
)

var allQuery = &Query{Op: QAll}
var noneQuery = &Query{Op: QNone}

// and returns the query q AND r, possibly reusing q's and r's storage.
func (q *Query) and(r *Query) *Query {
	return q.andOr(r, QAnd)
}

// or returns the query q OR r, possibly reusing q's and r's storage.
func (q *Query) or(r *Query) *Query {
	return q.andOr(r, QOr)
}

// andOr returns the query q AND r or q OR r, possibly reusing q's and r's storage.
// It works hard to avoid creating unnecessarily complicated structures.
func (q *Query) andOr(r *Query, op QueryOp) (out *Query) {
	opstr := "&"
	if op == QOr {
		opstr = "|"
	}
	//println("andOr", q.String(), opstr, r.String())
	//defer func() { println("  ->", out.String()) }()
	_ = opstr

	if len(q.Trigram) == 0 && len(q.Sub) == 1 {
		q = q.Sub[0]
	}
	if len(r.Trigram) == 0 && len(r.Sub) == 1 {
		r = r.Sub[0]
	}

	// Boolean simplification.
	// If q ⇒ r, q AND r ≡ q.
	// If q ⇒ r, q OR r ≡ r.
	if q.implies(r) {
		//println(q.String(), "implies", r.String())
		if op == QAnd {
			return q
		}
		return r
	}
	if r.implies(q) {
		//println(r.String(), "implies", q.String())
		if op == QAnd {
			return r
		}
		return q
	}

	// Both q and r are QAnd or QOr.
	// If they match or can be made to match, merge.
	qAtom := len(q.Trigram) == 1 && len(q.Sub) == 0
	rAtom := len(r.Trigram) == 1 && len(r.Sub) == 0
	if q.Op == op && (r.Op == op || rAtom) {
		q.Trigram = stringSet.union(q.Trigram, r.Trigram, false)
		q.Sub = append(q.Sub, r.Sub...)
		return q
	}
	if r.Op == op && qAtom {
		r.Trigram = stringSet.union(r.Trigram, q.Trigram, false)
		return r
	}
	if qAtom && rAtom {
		q.Op = op
		q.Trigram = append(q.Trigram, r.Trigram...)
		return q
	}

	// If one matches the op, add the other to it.
	if q.Op == op {
		q.Sub = append(q.Sub, r)
		return q
	}
	if r.Op == op {
		r.Sub = append(r.Sub, q)
		return r
	}

	// We are creating an AND of ORs or an OR of ANDs.
	// Factor out common trigrams, if any.
	common := stringSet{}
	i, j := 0, 0
	wi, wj := 0, 0
	for i < len(q.Trigram) && j < len(r.Trigram) {
		qt, rt := q.Trigram[i], r.Trigram[j]
		if qt < rt {
			q.Trigram[wi] = qt
			wi++
			i++
		} else if qt > rt {
			r.Trigram[wj] = rt
			wj++
			j++
		} else {
			common = append(common, qt)
			i++
			j++
		}
	}
	for ; i < len(q.Trigram); i++ {
		q.Trigram[wi] = q.Trigram[i]
		wi++
	}
	for ; j < len(r.Trigram); j++ {
		r.Trigram[wj] = r.Trigram[j]
		wj++
	}
	q.Trigram = q.Trigram[:wi]
	r.Trigram = r.Trigram[:wj]
	if len(common) > 0 {
		// If there were common trigrams, rewrite
		//
		//	(abc|def|ghi|jkl) AND (abc|def|mno|prs) =>
		//		(abc|def) OR ((ghi|jkl) AND (mno|prs))
		//
		//	(abc&def&ghi&jkl) OR (abc&def&mno&prs) =>
		//		(abc&def) AND ((ghi&jkl) OR (mno&prs))
		//
		// Build up the right one of
		//	(ghi|jkl) AND (mno|prs)
		//	(ghi&jkl) OR (mno&prs)
		// Call andOr recursively in case q and r can now be simplified
		// (we removed some trigrams).
		s := q.andOr(r, op)

		// Add in factored trigrams.
		otherOp := QAnd + QOr - op
		t := &Query{Op: otherOp, Trigram: common}
		return t.andOr(s, t.Op)
	}

	// Otherwise just create the op.
	return &Query{Op: op, Sub: []*Query{q, r}}
}

// implies reports whether q implies r.
// It is okay for it to return false negatives.
func (q *Query) implies(r *Query) bool {
	if q.Op == QNone || r.Op == QAll {
		// False implies everything.
		// Everything implies True.
		return true
	}
	if q.Op == QAll || r.Op == QNone {
		// True implies nothing.
		// Nothing implies False.
		return false
	}

	if q.Op == QAnd || (q.Op == QOr && len(q.Trigram) == 1 && len(q.Sub) == 0) {
		return trigramsImply(q.Trigram, r)
	}

	if q.Op == QOr && r.Op == QOr &&
		len(q.Trigram) > 0 && len(q.Sub) == 0 &&
		stringSet.isSubsetOf(q.Trigram, r.Trigram) {
		return true
	}
	return false
}

func trigramsImply(t []string, q *Query) bool {
	switch q.Op {
	case QOr:
		for _, qq := range q.Sub {
			if trigramsImply(t, qq) {
				return true
			}
		}
		for i := range t {
			if stringSet.isSubsetOf(t[i:i+1], q.Trigram) {
				return true
			}
		}
		return false
	case QAnd:
		for _, qq := range q.Sub {
			if !trigramsImply(t, qq) {
				return false
			}
		}
		if !stringSet.isSubsetOf(q.Trigram, t) {
			return false
		}
		return true
	}
	return false
}

// maybeRewrite rewrites q to use op if it is possible to do so
// without changing the meaning.  It also simplifies if the node
// is an empty OR or AND.
func (q *Query) maybeRewrite(op QueryOp) {
	if q.Op != QAnd && q.Op != QOr {
		return
	}

	// AND/OR doing real work?  Can't rewrite.
	n := len(q.Sub) + len(q.Trigram)
	if n > 1 {
		return
	}

	// Nothing left in the AND/OR?
	if n == 0 {
		if q.Op == QAnd {
			q.Op = QAll
		} else {
			q.Op = QNone
		}
		return
	}

	// Just a sub-node: throw away wrapper.
	if len(q.Sub) == 1 {
		*q = *q.Sub[0]
	}

	// Just a trigram: can use either op.
	q.Op = op
}

// andTrigrams returns q AND the OR of the AND of the trigrams present in each string.
func (q *Query) andTrigrams(t stringSet) *Query {
	if t.minLen() < 3 {
		// If there is a short string, we can't guarantee
		// that any trigrams must be present, so use ALL.
		// q AND ALL = q.
		return q
	}

	//println("andtrigrams", strings.Join(t, ","))
	or := noneQuery
	for _, tt := range t {
		var trig stringSet
		for i := 0; i+3 <= len(tt); i++ {
			trig.add(tt[i : i+3])
		}
		trig.clean(false)
		//println(tt, "trig", strings.Join(trig, ","))
		or = or.or(&Query{Op: QAnd, Trigram: trig})
	}
	q = q.and(or)
	return q
}

func (q *Query) String() string {
	if q == nil {
		return "?"
	}
	if q.Op == QNone {
		return "-"
	}
	if q.Op == QAll {
		return "+"
	}

	if len(q.Sub) == 0 && len(q.Trigram) == 1 {
		return strconv.Quote(q.Trigram[0])
	}

	var (
		s     string
		sjoin string
		end   string
		tjoin string
	)
	if q.Op == QAnd {
		sjoin = " "
		tjoin = " "
	} else {
		s = "("
		sjoin = ")|("
		end = ")"
		tjoin = "|"
	}
	for i, t := range q.Trigram {
		if i > 0 {
			s += tjoin
		}
		s += strconv.Quote(t)
	}
	if len(q.Sub) > 0 {
		if len(q.Trigram) > 0 {
			s += sjoin
		}
		s += q.Sub[0].String()
		for i := 1; i < len(q.Sub); i++ {
			s += sjoin + q.Sub[i].String()
		}
	}
	s += end
	return s
}

// RegexpQuery returns a Query for the given regexp.
func RegexpQuery(re *syntax.Regexp) *Query {
	info := analyze(re)
	info.simplify(true)
	info.addExact()
	return info.match
}

// A regexpInfo summarizes the results of analyzing a regexp.
type regexpInfo struct {
	// canEmpty records whether the regexp matches the empty string
	canEmpty bool

	// exact is the exact set of strings matching the regexp.
	exact stringSet

	// if exact is nil, prefix is the set of possible match prefixes,
	// and suffix is the set of possible match suffixes.
	prefix stringSet // otherwise: the exact set of matching prefixes ...
	suffix stringSet // ... and suffixes

	// match records a query that must be satisfied by any
	// match for the regexp, in addition to the information
	// recorded above.
	match *Query
}

const (
	// Exact sets are limited to maxExact strings.
	// If they get too big, simplify will rewrite the regexpInfo
	// to use prefix and suffix instead.  It's not worthwhile for
	// this to be bigger than maxSet.
	// Because we allow the maximum length of an exact string
	// to grow to 5 below (see simplify), it helps to avoid ridiculous
	// alternations if maxExact is sized so that 3 case-insensitive letters
	// triggers a flush.
	maxExact = 7

	// Prefix and suffix sets are limited to maxSet strings.
	// If they get too big, simplify will replace groups of strings
	// sharing a common leading prefix (or trailing suffix) with
	// that common prefix (or suffix).  It is useful for maxSet
	// to be at least 2³ = 8 so that we can exactly
	// represent a case-insensitive abc by the set
	// {abc, abC, aBc, aBC, Abc, AbC, ABc, ABC}.
	maxSet = 20
)

// anyMatch returns the regexpInfo describing a regexp that
// matches any string.
func anyMatch() regexpInfo {
	return regexpInfo{
		canEmpty: true,
		prefix:   []string{""},
		suffix:   []string{""},
		match:    allQuery,
	}
}

// anyChar returns the regexpInfo describing a regexp that
// matches any single character.
func anyChar() regexpInfo {
	return regexpInfo{
		prefix: []string{""},
		suffix: []string{""},
		match:  allQuery,
	}
}

// noMatch returns the regexpInfo describing a regexp that
// matches no strings at all.
func noMatch() regexpInfo {
	return regexpInfo{
		match: noneQuery,
	}
}

// emptyString returns the regexpInfo describing a regexp that
// matches only the empty string.
func emptyString() regexpInfo {
	return regexpInfo{
		canEmpty: true,
		exact:    []string{""},
		match:    allQuery,
	}
}

// analyze returns the regexpInfo for the regexp re.
func analyze(re *syntax.Regexp) (ret regexpInfo) {
	//println("analyze", re.String())
	//defer func() { println("->", ret.String()) }()
	var info regexpInfo
	switch re.Op {
	case syntax.OpNoMatch:
		return noMatch()

	case syntax.OpEmptyMatch,
		syntax.OpBeginLine, syntax.OpEndLine,
		syntax.OpBeginText, syntax.OpEndText,
		syntax.OpWordBoundary, syntax.OpNoWordBoundary:
		return emptyString()

	case syntax.OpLiteral:
		if re.Flags&syntax.FoldCase != 0 {
			switch len(re.Rune) {
			case 0:
				return emptyString()
			case 1:
				// Single-letter case-folded string:
				// rewrite into char class and analyze.
				re1 := &syntax.Regexp{
					Op: syntax.OpCharClass,
				}
				re1.Rune = re1.Rune0[:0]
				r0 := re.Rune[0]
				re1.Rune = append(re1.Rune, r0, r0)
				for r1 := unicode.SimpleFold(r0); r1 != r0; r1 = unicode.SimpleFold(r1) {
					re1.Rune = append(re1.Rune, r1, r1)
				}
				info = analyze(re1)
				return info
			}
			// Multi-letter case-folded string:
			// treat as concatenation of single-letter case-folded strings.
			re1 := &syntax.Regexp{
				Op:    syntax.OpLiteral,
				Flags: syntax.FoldCase,
			}
			info = emptyString()
			for i := range re.Rune {
				re1.Rune = re.Rune[i : i+1]
				info = concat(info, analyze(re1))
			}
			return info
		}
		info.exact = stringSet{string(re.Rune)}
		info.match = allQuery

	case syntax.OpAnyCharNotNL, syntax.OpAnyChar:
		return anyChar()

	case syntax.OpCapture:
		return analyze(re.Sub[0])

	case syntax.OpConcat:
		return fold(concat, re.Sub, emptyString())

	case syntax.OpAlternate:
		return fold(alternate, re.Sub, noMatch())

	case syntax.OpQuest:
		return alternate(analyze(re.Sub[0]), emptyString())

	case syntax.OpStar:
		// We don't know anything, so assume the worst.
		return anyMatch()

	case syntax.OpRepeat:
		if re.Min == 0 {
			// Like OpStar
			return anyMatch()
		}
		fallthrough
	case syntax.OpPlus:
		// x+
		// Since there has to be at least one x, the prefixes and suffixes
		// stay the same.  If x was exact, it isn't anymore.
		info = analyze(re.Sub[0])
		if info.exact.have() {
			info.prefix = info.exact
			info.suffix = info.exact.copy()
			info.exact = nil
		}

	case syntax.OpCharClass:
		info.match = allQuery

		// Special case.
		if len(re.Rune) == 0 {
			return noMatch()
		}

		// Special case.
		if len(re.Rune) == 1 {
			info.exact = stringSet{string(re.Rune[0])}
			break
		}

		n := 0
		for i := 0; i < len(re.Rune); i += 2 {
			n += int(re.Rune[i+1] - re.Rune[i])
		}
		// If the class is too large, it's okay to overestimate.
		if n > 100 {
			return anyChar()
		}

		info.exact = []string{}
		for i := 0; i < len(re.Rune); i += 2 {
			lo, hi := re.Rune[i], re.Rune[i+1]
			for rr := lo; rr <= hi; rr++ {
				info.exact.add(string(rr))
			}
		}
	}

	info.simplify(false)
	return info
}

// fold is the usual higher-order function.
func fold(f func(x, y regexpInfo) regexpInfo, sub []*syntax.Regexp, zero regexpInfo) regexpInfo {
	if len(sub) == 0 {
		return zero
	}
	if len(sub) == 1 {
		return analyze(sub[0])
	}
	info := f(analyze(sub[0]), analyze(sub[1]))
	for i := 2; i < len(sub); i++ {
		info = f(info, analyze(sub[i]))
	}
	return info
}

// concat returns the regexp info for xy given x and y.
func concat(x, y regexpInfo) (out regexpInfo) {
	//println("concat", x.String(), "...", y.String())
	//defer func() { println("->", out.String()) }()
	var xy regexpInfo
	xy.match = x.match.and(y.match)
	if x.exact.have() && y.exact.have() {
		xy.exact = x.exact.cross(y.exact, false)
	} else {
		if x.exact.have() {
			xy.prefix = x.exact.cross(y.prefix, false)
		} else {
			xy.prefix = x.prefix
			if x.canEmpty {
				xy.prefix = xy.prefix.union(y.prefix, false)
			}
		}
		if y.exact.have() {
			xy.suffix = x.suffix.cross(y.exact, true)
		} else {
			xy.suffix = y.suffix
			if y.canEmpty {
				xy.suffix = xy.suffix.union(x.suffix, true)
			}
		}
	}

	// If all the possible strings in the cross product of x.suffix
	// and y.prefix are long enough, then the trigram for one
	// of them must be present and would not necessarily be
	// accounted for in xy.prefix or xy.suffix yet.  Cut things off
	// at maxSet just to keep the sets manageable.
	if !x.exact.have() && !y.exact.have() &&
		x.suffix.size() <= maxSet && y.prefix.size() <= maxSet &&
		x.suffix.minLen()+y.prefix.minLen() >= 3 {
		xy.match = xy.match.andTrigrams(x.suffix.cross(y.prefix, false))
	}

	xy.simplify(false)
	return xy
}

// alternate returns the regexpInfo for x|y given x and y.
func alternate(x, y regexpInfo) (out regexpInfo) {
	//println("alternate", x.String(), "...", y.String())
	//defer func() { println("->", out.String()) }()
	var xy regexpInfo
	if x.exact.have() && y.exact.have() {
		xy.exact = x.exact.union(y.exact, false)
	} else if x.exact.have() {
		xy.prefix = x.exact.union(y.prefix, false)
		xy.suffix = x.exact.union(y.suffix, true)
		x.addExact()
	} else if y.exact.have() {
		xy.prefix = x.prefix.union(y.exact, false)
		xy.suffix = x.suffix.union(y.exact.copy(), true)
		y.addExact()
	} else {
		xy.prefix = x.prefix.union(y.prefix, false)
		xy.suffix = x.suffix.union(y.suffix, true)
	}
	xy.canEmpty = x.canEmpty || y.canEmpty
	xy.match = x.match.or(y.match)

	xy.simplify(false)
	return xy
}

// addExact adds to the match query the trigrams for matching info.exact.
func (info *regexpInfo) addExact() {
	if info.exact.have() {
		info.match = info.match.andTrigrams(info.exact)
	}
}

// simplify simplifies the regexpInfo when the exact set gets too large.
func (info *regexpInfo) simplify(force bool) {
	//println("  simplify", info.String(), " force=", force)
	//defer func() { println("  ->", info.String()) }()
	// If there are now too many exact strings,
	// loop over them, adding trigrams and moving
	// the relevant pieces into prefix and suffix.
	info.exact.clean(false)
	if len(info.exact) > maxExact || (info.exact.minLen() >= 3 && force) || info.exact.minLen() >= 4 {
		info.addExact()
		for _, s := range info.exact {
			n := len(s)
			if n < 3 {
				info.prefix.add(s)
				info.suffix.add(s)
			} else {
				info.prefix.add(s[:2])
				info.suffix.add(s[n-2:])
			}
		}
		info.exact = nil
	}

	if !info.exact.have() {
		info.simplifySet(&info.prefix)
		info.simplifySet(&info.suffix)
	}
}

// simplifySet reduces the size of the given set (either prefix or suffix).
// There is no need to pass around enormous prefix or suffix sets, since
// they will only be used to create trigrams.  As they get too big, simplifySet
// moves the information they contain into the match query, which is
// more efficient to pass around.
func (info *regexpInfo) simplifySet(s *stringSet) {
	t := *s
	t.clean(s == &info.suffix)

	// Add the OR of the current prefix/suffix set to the query.
	info.match = info.match.andTrigrams(t)

	for n := 3; n == 3 || t.size() > maxSet; n-- {
		// Replace set by strings of length n-1.
		w := 0
		for _, str := range t {
			if len(str) >= n {
				if s == &info.prefix {
					str = str[:n-1]
				} else {
					str = str[len(str)-n+1:]
				}
			}
			if w == 0 || t[w-1] != str {
				t[w] = str
				w++
			}
		}
		t = t[:w]
		t.clean(s == &info.suffix)
	}

	// Now make sure that the prefix/suffix sets aren't redundant.
	// For example, if we know "ab" is a possible prefix, then it
	// doesn't help at all to know that  "abc" is also a possible
	// prefix, so delete "abc".
	w := 0
	f := strings.HasPrefix
	if s == &info.suffix {
		f = strings.HasSuffix
	}
	for _, str := range t {
		if w == 0 || !f(str, t[w-1]) {
			t[w] = str
			w++
		}
	}
	t = t[:w]

	*s = t
}

func (info regexpInfo) String() string {
	s := ""
	if info.canEmpty {
		s += "canempty "
	}
	if info.exact.have() {
		s += "exact:" + strings.Join(info.exact, ",")
	} else {
		s += "prefix:" + strings.Join(info.prefix, ",")
		s += " suffix:" + strings.Join(info.suffix, ",")
	}
	s += " match: " + info.match.String()
	return s
}

// A stringSet is a set of strings.
// The nil stringSet indicates not having a set.
// The non-nil but empty stringSet is the empty set.
type stringSet []string

// have reports whether we have a stringSet.
func (s stringSet) have() bool {
	return s != nil
}

// contains reports whether s contains str.
func (s stringSet) contains(str string) bool {
	for _, ss := range s {
		if ss == str {
			return true
		}
	}
	return false
}

type byPrefix []string

func (x *byPrefix) Len() int           { return len(*x) }
func (x *byPrefix) Swap(i, j int)      { (*x)[i], (*x)[j] = (*x)[j], (*x)[i] }
func (x *byPrefix) Less(i, j int) bool { return (*x)[i] < (*x)[j] }

type bySuffix []string

func (x *bySuffix) Len() int      { return len(*x) }
func (x *bySuffix) Swap(i, j int) { (*x)[i], (*x)[j] = (*x)[j], (*x)[i] }
func (x *bySuffix) Less(i, j int) bool {
	s := (*x)[i]
	t := (*x)[j]
	for i := 1; i <= len(s) && i <= len(t); i++ {
		si := s[len(s)-i]
		ti := t[len(t)-i]
		if si < ti {
			return true
		}
		if si > ti {
			return false
		}
	}
	return len(s) < len(t)
}

// add adds str to the set.
func (s *stringSet) add(str string) {
	*s = append(*s, str)
}

// clean removes duplicates from the stringSet.
func (s *stringSet) clean(isSuffix bool) {
	t := *s
	if isSuffix {
		sort.Sort((*bySuffix)(s))
	} else {
		sort.Sort((*byPrefix)(s))
	}
	w := 0
	for _, str := range t {
		if w == 0 || t[w-1] != str {
			t[w] = str
			w++
		}
	}
	*s = t[:w]
}

// size returns the number of strings in s.
func (s stringSet) size() int {
	return len(s)
}

// minLen returns the length of the shortest string in s.
func (s stringSet) minLen() int {
	if len(s) == 0 {
		return 0
	}
	m := len(s[0])
	for _, str := range s {
		if m > len(str) {
			m = len(str)
		}
	}
	return m
}

// maxLen returns the length of the longest string in s.
func (s stringSet) maxLen() int {
	if len(s) == 0 {
		return 0
	}
	m := len(s[0])
	for _, str := range s {
		if m < len(str) {
			m = len(str)
		}
	}
	return m
}

// union returns the union of s and t, reusing s's storage.
func (s stringSet) union(t stringSet, isSuffix bool) stringSet {
	s = append(s, t...)
	s.clean(isSuffix)
	return s
}

// cross returns the cross product of s and t.
func (s stringSet) cross(t stringSet, isSuffix bool) stringSet {
	p := stringSet{}
	for _, ss := range s {
		for _, tt := range t {
			p.add(ss + tt)
		}
	}
	p.clean(isSuffix)
	return p
}

// clear empties the set but preserves the storage.
func (s *stringSet) clear() {
	*s = (*s)[:0]
}

// copy returns a copy of the set that does not share storage with the original.
func (s stringSet) copy() stringSet {
	return append(stringSet{}, s...)
}

// isSubsetOf returns true if all strings in s are also in t.
// It assumes both sets are sorted.
func (s stringSet) isSubsetOf(t stringSet) bool {
	j := 0
	for _, ss := range s {
		for j < len(t) && t[j] < ss {
			j++
		}
		if j >= len(t) || t[j] != ss {
			return false
		}
	}
	return true
}