// 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 path

import (
	
	
	
)

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

// Match reports whether name matches the shell pattern.
// The pattern syntax is:
//
//	pattern:
//		{ term }
//	term:
//		'*'         matches any sequence of non-/ characters
//		'?'         matches any single non-/ 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.
//
func (,  string) ( bool,  error) {
:
	for len() > 0 {
		var  bool
		var  string
		, ,  = scanChunk()
		if  &&  == "" {
			// Trailing * matches rest of string unless it has a /.
			return bytealg.IndexByteString(, '/') < 0, 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() && [] != '/'; ++ {
				, ,  := 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, 
				}
			}
		}
		// Before returning false with no error,
		// check that the remainder of the pattern is syntactically valid.
		for len() > 0 {
			_, ,  = scanChunk()
			if , ,  := matchChunk(, "");  != 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 '\\':
			// 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] == '/' {
					 = true
				}
				,  := utf8.DecodeRuneInString()
				 = [:]
			}
			 = [1:]

		case '\\':
			 = [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] == '\\' {
		 = [1:]
		if len() == 0 {
			 = ErrBadPattern
			return
		}
	}
	,  := utf8.DecodeRuneInString()
	if  == utf8.RuneError &&  == 1 {
		 = ErrBadPattern
	}
	 = [:]
	if len() == 0 {
		 = ErrBadPattern
	}
	return
}