glob.go

package gitconfig

import "strings"

// The patterns of includeIf "gitdir:" and "onbranch:" are matched as paths:
// '*' and '?' do not match '/', "**/" at the start of a segment matches any
// number of directories, "**" ending the pattern after a '/' (or alone)
// matches anything, a segment of more stars ("***") is "**", "[...]" is a class of characters ("[!...]" or "[^...]"
// negated, "a-z" a range, "[:digit:]" a named class) and '\' quotes the
// next character. A pattern with an unterminated class, or an unknown class
// name, matches nothing, as in git.
//
// The pattern is compiled into tokens and matched by simulating every
// possible position in the pattern at once, so that the time is linear in
// the length of the name for a given pattern: patterns come from
// configuration files someone else may have written.

type globKind uint8

const (
	globLit   globKind = iota // one given character
	globAny                   // '?': any character but '/'
	globClass                 // "[...]": a character of the class, never '/'
	globStar                  // '*': any run of characters without '/'
	globDirs                  // "**/": nothing, or anything ending with '/'
	globAll                   // final "**": anything
)

type globToken struct {
	kind   globKind
	c      byte      // globLit
	ranges [][2]byte // globClass: inclusive ranges
	negate bool      // globClass
}

// compileGlob compiles p, or returns false if it is malformed.
func compileGlob(p string) ([]globToken, bool) {
	var toks []globToken
	// A "[:" starts a named class only if a ":]" follows somewhere.
	lastColon := strings.LastIndex(p, ":]")
	segStart := true
	for i := 0; i < len(p); {
		c := p[i]
		switch {
		case c == '*' && segStart && starSegment(p[i:]) > 1:
			// As in git, a segment of three or more stars is "**" too.
			i += starSegment(p[i:])
			if i == len(p) {
				toks = append(toks, globToken{kind: globAll})
				continue
			}
			if len(toks) == 0 || toks[len(toks)-1].kind != globDirs {
				// "**/**/" is "**/".
				toks = append(toks, globToken{kind: globDirs})
			}
			// Past the '/': still at the start of a segment.
			i++
			continue
		case c == '*':
			for i < len(p) && p[i] == '*' {
				i++
			}
			toks = append(toks, globToken{kind: globStar})
		case c == '?':
			toks = append(toks, globToken{kind: globAny})
			i++
		case c == '[':
			tok, end, ok := compileClass(p, i, lastColon)
			if !ok {
				// Failing at once keeps the work linear: no other '['
				// rescans the rest of the pattern.
				return nil, false
			}
			toks = append(toks, tok)
			i = end
		case c == '\\' && i+1 < len(p):
			toks = append(toks, globToken{kind: globLit, c: p[i+1]})
			i += 2
		default:
			toks = append(toks, globToken{kind: globLit, c: c})
			i++
		}
		// "**" is special only at the start of a segment: at the start of the
		// pattern or after a '/'.
		segStart = toks[len(toks)-1].kind == globLit && toks[len(toks)-1].c == '/'
	}
	return toks, true
}

// starSegment returns the number of stars p starts with, if they make up a
// whole segment (the end of p or a '/' follows), 0 otherwise.
func starSegment(p string) int {
	n := 0
	for n < len(p) && p[n] == '*' {
		n++
	}
	if n < len(p) && p[n] != '/' {
		return 0
	}
	return n
}

// compileClass compiles the class starting at p[start], and returns the
// index past its end, or false if it is not terminated or names an unknown
// class. lastColon is the index of the last ":]" in p.
func compileClass(p string, start, lastColon int) (globToken, int, bool) {
	tok := globToken{kind: globClass}
	i := start + 1
	if i < len(p) && (p[i] == '!' || p[i] == '^') {
		tok.negate = true
		i++
	}
	first := true // a ']' first in the class is a literal ']'
	for i < len(p) {
		c := p[i]
		if c == ']' && !first {
			return tok, i + 1, true
		}
		first = false
		if c == '[' && i+1 < len(p) && p[i+1] == ':' && i+2 <= lastColon {
			// Found, as some ":]" starts at or after i+2. A known name
			// ends within a few bytes, and an unknown one fails.
			n := strings.Index(p[i+2:], ":]")
			ranges, ok := namedClasses[p[i+2:i+2+n]]
			if !ok {
				return globToken{}, 0, false
			}
			tok.ranges = append(tok.ranges, ranges...)
			i += 2 + n + 2
			continue
		}
		if c == '\\' && i+1 < len(p) {
			i++
			c = p[i]
		}
		// A range "a-z"; a '-' before the closing ']' is a literal '-'.
		lo, hi := c, c
		if i+2 < len(p) && p[i+1] == '-' && p[i+2] != ']' {
			hi = p[i+2]
			if hi == '\\' && i+3 < len(p) {
				hi = p[i+3]
				i++
			}
			i += 2
		}
		tok.ranges = append(tok.ranges, [2]byte{lo, hi})
		i++
	}
	return globToken{}, 0, false
}

// namedClasses are the ranges of the named classes, in ASCII.
var namedClasses = map[string][][2]byte{
	"alnum":  {{'0', '9'}, {'A', 'Z'}, {'a', 'z'}},
	"alpha":  {{'A', 'Z'}, {'a', 'z'}},
	"blank":  {{' ', ' '}, {'\t', '\t'}},
	"cntrl":  {{0, 31}, {127, 127}},
	"digit":  {{'0', '9'}},
	"graph":  {{'!', '~'}},
	"lower":  {{'a', 'z'}},
	"print":  {{' ', '~'}},
	"punct":  {{'!', '/'}, {':', '@'}, {'[', '`'}, {'{', '~'}},
	"space":  {{'\t', '\r'}, {' ', ' '}},
	"upper":  {{'A', 'Z'}},
	"xdigit": {{'0', '9'}, {'A', 'F'}, {'a', 'f'}},
}

func (t globToken) inClass(c byte, fold bool) bool {
	for _, r := range t.ranges {
		if r[0] <= c && c <= r[1] || fold && r[0] <= swapCase(c) && swapCase(c) <= r[1] {
			return !t.negate
		}
	}
	return t.negate
}

func swapCase(c byte) byte {
	if isAlpha(c) {
		return c ^ 0x20
	}
	return c
}

func sameByte(a, b byte, fold bool) bool {
	return a == b || fold && swapCase(a) == b
}

// globMatch reports whether name matches pattern. With fold, the case of
// ASCII letters is ignored.
func globMatch(pattern, name string, fold bool) bool {
	toks, ok := compileGlob(pattern)
	if !ok {
		return false
	}
	n := int32(len(toks))
	// A state is a position in the pattern, 2*s for token s, or 2*s+1 for
	// the inside of the directories matched by the globDirs token s. Only
	// the states reached are visited.
	cur := newStateSet(2*n + 2)
	next := newStateSet(2*n + 2)

	// enter adds the state of token s and those reachable without a
	// character: past a '*', "**/" or final "**".
	enter := func(set *stateSet, s int32) {
		for set.add(2*s) && s < n {
			if k := toks[s].kind; k != globStar && k != globDirs && k != globAll {
				break
			}
			s++
		}
	}

	enter(cur, 0)
	for i := 0; i < len(name); i++ {
		c := name[i]
		next.reset()
		for _, id := range cur.list {
			s := id / 2
			if id%2 == 1 {
				// Inside "**/": anything, and a '/' may end it.
				next.add(id)
				if c == '/' {
					enter(next, s+1)
				}
				continue
			}
			if s == n {
				continue
			}
			switch t := toks[s]; t.kind {
			case globLit:
				if sameByte(c, t.c, fold) {
					enter(next, s+1)
				}
			case globAny:
				if c != '/' {
					enter(next, s+1)
				}
			case globClass:
				if c != '/' && t.inClass(c, fold) {
					enter(next, s+1)
				}
			case globStar:
				if c != '/' {
					enter(next, s)
				}
			case globDirs:
				next.add(id + 1)
				if c == '/' {
					enter(next, s+1)
				}
			case globAll:
				enter(next, s)
			}
		}
		if len(next.list) == 0 {
			// No position left: the rest of name cannot match.
			return false
		}
		cur, next = next, cur
	}
	// Matched if the whole pattern is consumed.
	return cur.has(2 * n)
}

// stateSet is a set of states, listed in the order they were added. reset
// empties it in constant time by moving to a new generation instead of
// clearing mark.
type stateSet struct {
	list []int32
	mark []uint32 // mark[id] == gen if id is in the set
	gen  uint32
}

func newStateSet(size int32) *stateSet {
	return &stateSet{mark: make([]uint32, size), gen: 1}
}

func (ss *stateSet) reset() {
	ss.list = ss.list[:0]
	ss.gen++
}

// add adds id and reports whether it was absent.
func (ss *stateSet) add(id int32) bool {
	if ss.mark[id] == ss.gen {
		return false
	}
	ss.mark[id] = ss.gen
	ss.list = append(ss.list, id)
	return true
}

func (ss *stateSet) has(id int32) bool {
	return ss.mark[id] == ss.gen
}