// Copyright 2010 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 filepath

import (
	
	
	
	
	
	
)

// ErrBadPattern indicates a pattern was malformed.
var ErrBadPattern = errors.New("syntax error in pattern")

// Match reports whether name matches the shell file name pattern.
// The pattern syntax is:
//
//	pattern:
//		{ term }
//	term:
//		'*'         matches any sequence of non-Separator characters
//		'?'         matches any single non-Separator character
//		'[' [ '^' ] { character-range } ']'
//		            character class (must be non-empty)
//		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 only possible returned error is ErrBadPattern, when pattern
// is malformed.
//
// On Windows, escaping is disabled. Instead, '\\' is treated as
// path separator.
//
func (,  string) ( bool,  error) {
:
	for len() > 0 {
		var  bool
		var  string
		, ,  = scanChunk()
		if  &&  == "" {
			// Trailing * matches rest of string unless it has a /.
			return !strings.Contains(, string(Separator)), nil
		}
		// Look for match at current position.
		, ,  := matchChunk(, )
		// if we're the last chunk, make sure we've exhausted the name
		// otherwise we'll give a false result even if we could still match
		// using the star
		if  && (len() == 0 || len() > 0) {
			 = 
			continue
		}
		if  != nil {
			return false, 
		}
		if  {
			// Look for match skipping i+1 bytes.
			// Cannot skip /.
			for  := 0;  < len() && [] != Separator; ++ {
				, ,  := matchChunk(, [+1:])
				if  {
					// if we're the last chunk, make sure we exhausted the name
					if len() == 0 && len() > 0 {
						continue
					}
					 = 
					continue 
				}
				if  != nil {
					return false, 
				}
			}
		}
		return false, nil
	}
	return len() == 0, nil
}

// scanChunk gets the next segment of pattern, which is a non-star string
// possibly preceded by a star.
func scanChunk( string) ( bool, ,  string) {
	for len() > 0 && [0] == '*' {
		 = [1:]
		 = true
	}
	 := false
	var  int
:
	for  = 0;  < len(); ++ {
		switch [] {
		case '\\':
			if runtime.GOOS != "windows" {
				// error check handled in matchChunk: bad pattern.
				if +1 < len() {
					++
				}
			}
		case '[':
			 = true
		case ']':
			 = false
		case '*':
			if ! {
				break 
			}
		}
	}
	return , [0:], [:]
}

// matchChunk checks whether chunk matches the beginning of s.
// If so, it returns the remainder of s (after the match).
// Chunk is all single-character operators: literals, char classes, and ?.
func matchChunk(,  string) ( string,  bool,  error) {
	// failed records whether the match has failed.
	// After the match fails, the loop continues on processing chunk,
	// checking that the pattern is well-formed but no longer reading s.
	 := false
	for len() > 0 {
		if ! && len() == 0 {
			 = true
		}
		switch [0] {
		case '[':
			// character class
			var  rune
			if ! {
				var  int
				,  = utf8.DecodeRuneInString()
				 = [:]
			}
			 = [1:]
			// possibly negated
			 := false
			if len() > 0 && [0] == '^' {
				 = true
				 = [1:]
			}
			// parse all ranges
			 := false
			 := 0
			for {
				if len() > 0 && [0] == ']' &&  > 0 {
					 = [1:]
					break
				}
				var ,  rune
				if , ,  = getEsc();  != nil {
					return "", false, 
				}
				 = 
				if [0] == '-' {
					if , ,  = getEsc([1:]);  != nil {
						return "", false, 
					}
				}
				if  <=  &&  <=  {
					 = true
				}
				++
			}
			if  ==  {
				 = true
			}

		case '?':
			if ! {
				if [0] == Separator {
					 = true
				}
				,  := utf8.DecodeRuneInString()
				 = [:]
			}
			 = [1:]

		case '\\':
			if runtime.GOOS != "windows" {
				 = [1:]
				if len() == 0 {
					return "", false, ErrBadPattern
				}
			}
			fallthrough

		default:
			if ! {
				if [0] != [0] {
					 = true
				}
				 = [1:]
			}
			 = [1:]
		}
	}
	if  {
		return "", false, nil
	}
	return , true, nil
}

// getEsc gets a possibly-escaped character from chunk, for a character class.
func getEsc( string) ( rune,  string,  error) {
	if len() == 0 || [0] == '-' || [0] == ']' {
		 = ErrBadPattern
		return
	}
	if [0] == '\\' && runtime.GOOS != "windows" {
		 = [1:]
		if len() == 0 {
			 = ErrBadPattern
			return
		}
	}
	,  := utf8.DecodeRuneInString()
	if  == utf8.RuneError &&  == 1 {
		 = ErrBadPattern
	}
	 = [:]
	if len() == 0 {
		 = ErrBadPattern
	}
	return
}

// Glob returns the names of all files matching pattern or nil
// if there is no matching file. The syntax of patterns 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.
func ( string) ( []string,  error) {
	// Check pattern is well-formed.
	if ,  := Match(, "");  != nil {
		return nil, 
	}
	if !hasMeta() {
		if _,  = os.Lstat();  != nil {
			return nil, nil
		}
		return []string{}, nil
	}

	,  := Split()
	 := 0
	if runtime.GOOS == "windows" {
		,  = cleanGlobPathWindows()
	} else {
		 = cleanGlobPath()
	}

	if !hasMeta([:]) {
		return glob(, , nil)
	}

	// Prevent infinite recursion. See issue 15879.
	if  ==  {
		return nil, ErrBadPattern
	}

	var  []string
	,  = ()
	if  != nil {
		return
	}
	for ,  := range  {
		,  = glob(, , )
		if  != nil {
			return
		}
	}
	return
}

// cleanGlobPath prepares path for glob matching.
func cleanGlobPath( string) string {
	switch  {
	case "":
		return "."
	case string(Separator):
		// do nothing to the path
		return 
	default:
		return [0 : len()-1] // chop off trailing separator
	}
}

// cleanGlobPathWindows is windows version of cleanGlobPath.
func cleanGlobPathWindows( string) ( int,  string) {
	 := volumeNameLen()
	switch {
	case  == "":
		return 0, "."
	case +1 == len() && os.IsPathSeparator([len()-1]): // /, \, C:\ and C:/
		// do nothing to the path
		return  + 1, 
	case  == len() && len() == 2: // C:
		return ,  + "." // convert C: into C:.
	default:
		if  >= len() {
			 = len() - 1
		}
		return , [0 : len()-1] // chop off trailing separator
	}
}

// glob searches for files matching pattern in the directory dir
// and appends them to matches. If the directory cannot be
// opened, it returns the existing matches. New matches are
// added in lexicographical order.
func glob(,  string,  []string) ( []string,  error) {
	 = 
	,  := os.Stat()
	if  != nil {
		return // ignore I/O error
	}
	if !.IsDir() {
		return // ignore I/O error
	}
	,  := os.Open()
	if  != nil {
		return // ignore I/O error
	}
	defer .Close()

	,  := .Readdirnames(-1)
	sort.Strings()

	for ,  := range  {
		,  := Match(, )
		if  != nil {
			return , 
		}
		if  {
			 = append(, Join(, ))
		}
	}
	return
}

// hasMeta reports whether path contains any of the magic characters
// recognized by Match.
func hasMeta( string) bool {
	 := `*?[`
	if runtime.GOOS != "windows" {
		 = `*?[\`
	}
	return strings.ContainsAny(, )
}