// Copyright 2020 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 fs

import (
	
)

// A GlobFS is a file system with a Glob method.
type GlobFS interface {
	FS

	// Glob returns the names of all files matching pattern,
	// providing an implementation of the top-level
	// Glob function.
	Glob(pattern string) ([]string, error)
}

// 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 [path.Match]. The pattern may describe hierarchical names such as
// usr/*/bin/ed.
//
// Glob ignores file system errors such as I/O errors reading directories.
// The only possible returned error is [path.ErrBadPattern], reporting that
// the pattern is malformed.
//
// If fs implements [GlobFS], Glob calls fs.Glob.
// Otherwise, Glob uses [ReadDir] to traverse the directory tree
// and look for matches for the pattern.
func ( FS,  string) ( []string,  error) {
	return globWithLimit(, , 0)
}

func globWithLimit( FS,  string,  int) ( []string,  error) {
	// This limit is added to prevent stack exhaustion issues. See
	// CVE-2022-30630.
	const  = 10000
	if  >  {
		return nil, path.ErrBadPattern
	}
	if ,  := .(GlobFS);  {
		return .Glob()
	}

	// Check pattern is well-formed.
	if ,  := path.Match(, "");  != nil {
		return nil, 
	}
	if !hasMeta() {
		if _,  = Stat(, );  != nil {
			return nil, nil
		}
		return []string{}, nil
	}

	,  := path.Split()
	 = cleanGlobPath()

	if !hasMeta() {
		return glob(, , , nil)
	}

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

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

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

// glob searches for files matching pattern in the directory dir
// and appends them to matches, returning the updated slice.
// If the directory cannot be opened, glob returns the existing matches.
// New matches are added in lexicographical order.
func glob( FS, ,  string,  []string) ( []string,  error) {
	 = 
	,  := ReadDir(, )
	if  != nil {
		return // ignore I/O error
	}

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

// hasMeta reports whether path contains any of the magic characters
// recognized by path.Match.
func hasMeta( string) bool {
	for  := 0;  < len(); ++ {
		switch [] {
		case '*', '?', '[', '\\':
			return true
		}
	}
	return false
}