doublestar.go

package doublestar

import (
	"fmt"
	"os"
	"path"
	"path/filepath"
	"strings"
	"unicode/utf8"
)

// ErrBadPattern indicates a pattern was malformed.
var ErrBadPattern = path.ErrBadPattern

// Split a path on the given separator, respecting escaping.
func splitPathOnSeparator(path string, separator rune) (ret []string) {
	idx := 0
	if separator == '\\' {
		// if the separator is '\\', then we can just split...
		ret = strings.Split(path, string(separator))
		idx = len(ret)
	} else {
		// otherwise, we need to be careful of situations where the separator was escaped
		cnt := strings.Count(path, string(separator))
		if cnt == 0 {
			return []string{path}
		}

		ret = make([]string, cnt+1)
		pathlen := len(path)
		separatorLen := utf8.RuneLen(separator)
		emptyEnd := false
		for start := 0; start < pathlen; {
			end := indexRuneWithEscaping(path[start:], separator)
			if end == -1 {
				emptyEnd = false
				end = pathlen
			} else {
				emptyEnd = true
				end += start
			}
			ret[idx] = path[start:end]
			start = end + separatorLen
			idx++
		}

		// If the last rune is a path separator, we need to append an empty string to
		// represent the last, empty path component. By default, the strings from
		// make([]string, ...) will be empty, so we just need to icrement the count
		if emptyEnd {
			idx++
		}
	}

	return ret[:idx]
}

// Find the first index of a rune in a string,
// ignoring any times the rune is escaped using "\".
func indexRuneWithEscaping(s string, r rune) int {
	end := strings.IndexRune(s, r)
	if end == -1 {
		return -1
	}
	if end > 0 && s[end-1] == '\\' {
		start := end + utf8.RuneLen(r)
		end = indexRuneWithEscaping(s[start:], r)
		if end != -1 {
			end += start
		}
	}
	return end
}

// Find the last index of a rune in a string,
// ignoring any times the rune is escaped using "\".
func lastIndexRuneWithEscaping(s string, r rune) int {
	end := strings.LastIndex(s, string(r))
	if end == -1 {
		return -1
	}
	if end > 0 && s[end-1] == '\\' {
		end = lastIndexRuneWithEscaping(s[:end-1], r)
	}
	return end
}

// Find the index of the first instance of one of the unicode characters in
// chars, ignoring any times those characters are escaped using "\".
func indexAnyWithEscaping(s, chars string) int {
	end := strings.IndexAny(s, chars)
	if end == -1 {
		return -1
	}
	if end > 0 && s[end-1] == '\\' {
		_, adj := utf8.DecodeRuneInString(s[end:])
		start := end + adj
		end = indexAnyWithEscaping(s[start:], chars)
		if end != -1 {
			end += start
		}
	}
	return end
}

// Split a set of alternatives such as {alt1,alt2,...} and returns the index of
// the rune after the closing curly brace. Respects nested alternatives and
// escaped runes.
func splitAlternatives(s string) (ret []string, idx int) {
	ret = make([]string, 0, 2)
	idx = 0
	slen := len(s)
	braceCnt := 1
	esc := false
	start := 0
	for braceCnt > 0 {
		if idx >= slen {
			return nil, -1
		}

		sRune, adj := utf8.DecodeRuneInString(s[idx:])
		if esc {
			esc = false
		} else if sRune == '\\' {
			esc = true
		} else if sRune == '{' {
			braceCnt++
		} else if sRune == '}' {
			braceCnt--
		} else if sRune == ',' && braceCnt == 1 {
			ret = append(ret, s[start:idx])
			start = idx + adj
		}

		idx += adj
	}
	ret = append(ret, s[start:idx-1])
	return
}

// Returns true if the pattern is "zero length", meaning
// it could match zero or more characters.
func isZeroLengthPattern(pattern string) (ret bool, err error) {
	// * can match zero
	if pattern == "" || pattern == "*" || pattern == "**" {
		return true, nil
	}

	// an alternative with zero length can match zero, for example {,x} - the
	// first alternative has zero length
	r, adj := utf8.DecodeRuneInString(pattern)
	if r == '{' {
		options, endOptions := splitAlternatives(pattern[adj:])
		if endOptions == -1 {
			return false, ErrBadPattern
		}
		if ret, err = isZeroLengthPattern(pattern[adj+endOptions:]); !ret || err != nil {
			return
		}
		for _, o := range options {
			if ret, err = isZeroLengthPattern(o); ret || err != nil {
				return
			}
		}
	}

	return false, nil
}

// Match returns true if name matches the shell file name pattern.
// The pattern syntax is:
//
//  pattern:
//    { term }
//  term:
//    '*'         matches any sequence of non-path-separators
//    '**'        matches any sequence of characters, including
//                path separators.
//    '?'         matches any single non-path-separator character
//    '[' [ '^' ] { character-range } ']'
//          character class (must be non-empty)
//    '{' { term } [ ',' { term } ... ] '}'
//    c           matches character c (c != '*', '?', '\\', '[')
//    '\\' c      matches character c
//
//  character-range:
//    c           matches character c (c != '\\', '-', ']')
//    '\\' c      matches character c
//    lo '-' hi   matches character c for lo <= c <= hi
//
// Match requires pattern to match all of name, not just a substring.
// The path-separator defaults to the '/' character. The only possible
// returned error is ErrBadPattern, when pattern is malformed.
//
// Note: this is meant as a drop-in replacement for path.Match() which
// always uses '/' as the path separator. If you want to support systems
// which use a different path separator (such as Windows), what you want
// is the PathMatch() function below.
//
func Match(pattern, name string) (bool, error) {
	return matchWithSeparator(pattern, name, '/')
}

// PathMatch is like Match except that it uses your system's path separator.
// For most systems, this will be '/'. However, for Windows, it would be '\\'.
// Note that for systems where the path separator is '\\', escaping is
// disabled.
//
// Note: this is meant as a drop-in replacement for filepath.Match().
//
func PathMatch(pattern, name string) (bool, error) {
	pattern = filepath.ToSlash(pattern)
	return matchWithSeparator(pattern, name, os.PathSeparator)
}

// Match returns true if name matches the shell file name pattern.
// The pattern syntax is:
//
//  pattern:
//    { term }
//  term:
//    '*'         matches any sequence of non-path-separators
//              '**'        matches any sequence of characters, including
//                          path separators.
//    '?'         matches any single non-path-separator character
//    '[' [ '^' ] { character-range } ']'
//          character class (must be non-empty)
//    '{' { term } [ ',' { term } ... ] '}'
//    c           matches character c (c != '*', '?', '\\', '[')
//    '\\' c      matches character c
//
//  character-range:
//    c           matches character c (c != '\\', '-', ']')
//    '\\' c      matches character c, unless separator is '\\'
//    lo '-' hi   matches character c for lo <= c <= hi
//
// Match requires pattern to match all of name, not just a substring.
// The only possible returned error is ErrBadPattern, when pattern
// is malformed.
//
func matchWithSeparator(pattern, name string, separator rune) (bool, error) {
	nameComponents := splitPathOnSeparator(name, separator)
	return doMatching(pattern, nameComponents)
}

func doMatching(pattern string, nameComponents []string) (matched bool, err error) {
	// check for some base-cases
	patternLen, nameLen := len(pattern), len(nameComponents)
	if patternLen == 0 && nameLen == 0 {
		return true, nil
	}
	if patternLen == 0 || nameLen == 0 {
		return false, nil
	}

	slashIdx := indexRuneWithEscaping(pattern, '/')
	lastComponent := slashIdx == -1
	if lastComponent {
		slashIdx = len(pattern)
	}
	if pattern[:slashIdx] == "**" {
		// if our last pattern component is a doublestar, we're done -
		// doublestar will match any remaining name components, if any.
		if lastComponent {
			return true, nil
		}

		// otherwise, try matching remaining components
		for nameIdx := 0; nameIdx < nameLen; nameIdx++ {
			if m, _ := doMatching(pattern[slashIdx+1:], nameComponents[nameIdx:]); m {
				return true, nil
			}
		}
		return false, nil
	}

	var matches []string
	matches, err = matchComponent(pattern, nameComponents[0])
	if matches == nil || err != nil {
		return
	}
	if len(matches) == 0 && nameLen == 1 {
		return true, nil
	}

	if nameLen > 1 {
		for _, alt := range matches {
			matched, err = doMatching(alt, nameComponents[1:])
			if matched || err != nil {
				return
			}
		}
	}

	return false, nil
}

// Glob returns the names of all files matching pattern or nil
// if there is no matching file. The syntax of pattern is the same
// as in Match. The pattern may describe hierarchical names such as
// /usr/*/bin/ed (assuming the Separator is '/').
//
// Glob ignores file system errors such as I/O errors reading directories.
// The only possible returned error is ErrBadPattern, when pattern
// is malformed.
//
// Your system path separator is automatically used. This means on
// systems where the separator is '\\' (Windows), escaping will be
// disabled.
//
// Note: this is meant as a drop-in replacement for filepath.Glob().
//
func Glob(pattern string) (matches []string, err error) {
	if len(pattern) == 0 {
		return nil, nil
	}

	// If the pattern is relative or absolute and we're on a non-Windows machine,
	// volumeName will be an empty string. If it is absolute and we're on a
	// Windows machine, volumeName will be a drive letter ("C:") for filesystem
	// paths or \\<server>\<share> for UNC paths.
	isAbs := filepath.IsAbs(pattern)
	volumeName := filepath.VolumeName(pattern)
	isWindowsUNC := strings.HasPrefix(volumeName, `\\`)
	if isWindowsUNC || isAbs {
		startIdx := len(volumeName) + 1
		return doGlob(fmt.Sprintf("%s%s", volumeName, string(os.PathSeparator)), filepath.ToSlash(pattern[startIdx:]), matches)
	}

	// otherwise, it's a relative pattern
	return doGlob(".", filepath.ToSlash(pattern), matches)
}

// Perform a glob
func doGlob(basedir, pattern string, matches []string) (m []string, e error) {
	m = matches
	e = nil

	// if the pattern starts with any path components that aren't globbed (ie,
	// `path/to/glob*`), we can skip over the un-globbed components (`path/to` in
	// our example).
	globIdx := indexAnyWithEscaping(pattern, "*?[{\\")
	if globIdx > 0 {
		globIdx = lastIndexRuneWithEscaping(pattern[:globIdx], '/')
	} else if globIdx == -1 {
		globIdx = lastIndexRuneWithEscaping(pattern, '/')
	}
	if globIdx > 0 {
		basedir = filepath.Join(basedir, pattern[:globIdx])
		pattern = pattern[globIdx+1:]
	}

	// Lstat will return an error if the file/directory doesn't exist
	fi, err := os.Lstat(basedir)
	if err != nil {
		return
	}

	// if the pattern is empty, we've found a match
	if len(pattern) == 0 {
		m = append(m, basedir)
		return
	}

	// otherwise, we need to check each item in the directory...
	// first, if basedir is a symlink, follow it...
	if (fi.Mode() & os.ModeSymlink) != 0 {
		fi, err = os.Stat(basedir)
		if err != nil {
			return
		}
	}

	// confirm it's a directory...
	if !fi.IsDir() {
		return
	}

	// read directory
	dir, err := os.Open(basedir)
	if err != nil {
		return
	}
	defer dir.Close()

	files, _ := dir.Readdir(-1)
	slashIdx := indexRuneWithEscaping(pattern, '/')
	lastComponent := slashIdx == -1
	if lastComponent {
		slashIdx = len(pattern)
	}
	if pattern[:slashIdx] == "**" {
		// if the current component is a doublestar, we'll try depth-first
		for _, file := range files {
			// if symlink, we may want to follow
			if (file.Mode() & os.ModeSymlink) != 0 {
				file, err = os.Stat(filepath.Join(basedir, file.Name()))
				if err != nil {
					continue
				}
			}

			if file.IsDir() {
				// recurse into directories
				if lastComponent {
					m = append(m, filepath.Join(basedir, file.Name()))
				}
				m, e = doGlob(filepath.Join(basedir, file.Name()), pattern, m)
			} else if lastComponent {
				// if the pattern's last component is a doublestar, we match filenames, too
				m = append(m, filepath.Join(basedir, file.Name()))
			}
		}
		if lastComponent {
			return // we're done
		}

		pattern = pattern[slashIdx+1:]
	}

	// check items in current directory and recurse
	var match []string
	for _, file := range files {
		match, e = matchComponent(pattern, file.Name())
		if e != nil {
			return
		}
		if match != nil {
			if len(match) == 0 {
				m = append(m, filepath.Join(basedir, file.Name()))
			} else {
				for _, alt := range match {
					m, e = doGlob(filepath.Join(basedir, file.Name()), alt, m)
				}
			}
		}
	}
	return
}

// Attempt to match a single path component with a pattern. Note that the
// pattern may include multiple components but that the "name" is just a single
// path component. The return value is a slice of patterns that should be
// checked against subsequent path components or nil, indicating that the
// pattern does not match this path. It is assumed that pattern components are
// separated by '/'
func matchComponent(pattern, name string) ([]string, error) {
	// check for matches one rune at a time
	patternLen, nameLen := len(pattern), len(name)
	patIdx, nameIdx := 0, 0
	for patIdx < patternLen && nameIdx < nameLen {
		patRune, patAdj := utf8.DecodeRuneInString(pattern[patIdx:])
		nameRune, nameAdj := utf8.DecodeRuneInString(name[nameIdx:])
		if patRune == '/' {
			patIdx++
			break
		} else if patRune == '\\' {
			// handle escaped runes, only if separator isn't '\\'
			patIdx += patAdj
			patRune, patAdj = utf8.DecodeRuneInString(pattern[patIdx:])
			if patRune == utf8.RuneError {
				return nil, ErrBadPattern
			} else if patRune == nameRune {
				patIdx += patAdj
				nameIdx += nameAdj
			} else {
				return nil, nil
			}
		} else if patRune == '*' {
			// handle stars - a star at the end of the pattern or before a separator
			// will always match the rest of the path component
			if patIdx += patAdj; patIdx >= patternLen {
				return []string{}, nil
			}
			if patRune, patAdj = utf8.DecodeRuneInString(pattern[patIdx:]); patRune == '/' {
				return []string{pattern[patIdx+patAdj:]}, nil
			}

			// check if we can make any matches
			for ; nameIdx < nameLen; nameIdx += nameAdj {
				if m, e := matchComponent(pattern[patIdx:], name[nameIdx:]); m != nil || e != nil {
					return m, e
				}
			}
			return nil, nil
		} else if patRune == '[' {
			// handle character sets
			patIdx += patAdj
			endClass := indexRuneWithEscaping(pattern[patIdx:], ']')
			if endClass == -1 {
				return nil, ErrBadPattern
			}
			endClass += patIdx
			classRunes := []rune(pattern[patIdx:endClass])
			classRunesLen := len(classRunes)
			if classRunesLen > 0 {
				classIdx := 0
				matchClass := false
				if classRunes[0] == '^' {
					classIdx++
				}
				for classIdx < classRunesLen {
					low := classRunes[classIdx]
					if low == '-' {
						return nil, ErrBadPattern
					}
					classIdx++
					if low == '\\' {
						if classIdx < classRunesLen {
							low = classRunes[classIdx]
							classIdx++
						} else {
							return nil, ErrBadPattern
						}
					}
					high := low
					if classIdx < classRunesLen && classRunes[classIdx] == '-' {
						// we have a range of runes
						if classIdx++; classIdx >= classRunesLen {
							return nil, ErrBadPattern
						}
						high = classRunes[classIdx]
						if high == '-' {
							return nil, ErrBadPattern
						}
						classIdx++
						if high == '\\' {
							if classIdx < classRunesLen {
								high = classRunes[classIdx]
								classIdx++
							} else {
								return nil, ErrBadPattern
							}
						}
					}
					if low <= nameRune && nameRune <= high {
						matchClass = true
					}
				}
				if matchClass == (classRunes[0] == '^') {
					return nil, nil
				}
			} else {
				return nil, ErrBadPattern
			}
			patIdx = endClass + 1
			nameIdx += nameAdj
		} else if patRune == '{' {
			// handle alternatives such as {alt1,alt2,...}
			patIdx += patAdj
			options, endOptions := splitAlternatives(pattern[patIdx:])
			if endOptions == -1 {
				return nil, ErrBadPattern
			}
			patIdx += endOptions

			results := make([][]string, 0, len(options))
			totalResults := 0
			for _, o := range options {
				m, e := matchComponent(o+pattern[patIdx:], name[nameIdx:])
				if e != nil {
					return nil, e
				}
				if m != nil {
					results = append(results, m)
					totalResults += len(m)
				}
			}
			if len(results) > 0 {
				lst := make([]string, 0, totalResults)
				for _, m := range results {
					lst = append(lst, m...)
				}
				return lst, nil
			}

			return nil, nil
		} else if patRune == '?' || patRune == nameRune {
			// handle single-rune wildcard
			patIdx += patAdj
			nameIdx += nameAdj
		} else {
			return nil, nil
		}
	}
	if nameIdx >= nameLen {
		if patIdx >= patternLen {
			return []string{}, nil
		}

		pattern = pattern[patIdx:]
		slashIdx := indexRuneWithEscaping(pattern, '/')
		testPattern := pattern
		if slashIdx >= 0 {
			testPattern = pattern[:slashIdx]
		}

		zeroLength, err := isZeroLengthPattern(testPattern)
		if err != nil {
			return nil, err
		}
		if zeroLength {
			if slashIdx == -1 {
				return []string{}, nil
			} else {
				return []string{pattern[slashIdx+1:]}, nil
			}
		}
	}
	return nil, nil
}