libgo/go/path/filepath/path.go - gofrontend - Git at Google

 // Copyright 2009 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 implements utility routines for manipulating filename paths
 // in a way compatible with the target operating system-defined file paths.
 //
 // The filepath package uses either forward slashes or backslashes,
 // depending on the operating system. To process paths such as URLs
 // that always use forward slashes regardless of the operating
 // system, see the path package.
 package filepath

 import (
 	"errors"
 	"os"
 	"sort"
 	"strings"
 )

 // A lazybuf is a lazily constructed path buffer.
 // It supports append, reading previously appended bytes,
 // and retrieving the final string. It does not allocate a buffer
 // to hold the output until that output diverges from s.
 type lazybuf struct {
 	path       string
 	buf        []byte
 	w          int
 	volAndPath string
 	volLen     int
 }

 func (b *lazybuf) index(i int) byte {
 	if b.buf != nil {
 		return b.buf[i]
 	}
 	return b.path[i]
 }

 func (b *lazybuf) append(c byte) {
 	if b.buf == nil {
 		if b.w < len(b.path) && b.path[b.w] == c {
 			b.w++
 			return
 		}
 		b.buf = make([]byte, len(b.path))
 		copy(b.buf, b.path[:b.w])
 	}
 	b.buf[b.w] = c
 	b.w++
 }

 func (b *lazybuf) string() string {
 	if b.buf == nil {
 		return b.volAndPath[:b.volLen+b.w]
 	}
 	return b.volAndPath[:b.volLen] + string(b.buf[:b.w])
 }

 const (
 	Separator     = os.PathSeparator
 	ListSeparator = os.PathListSeparator
 )

 // Clean returns the shortest path name equivalent to path
 // by purely lexical processing. It applies the following rules
 // iteratively until no further processing can be done:
 //
 //	1. Replace multiple Separator elements with a single one.
 //	2. Eliminate each . path name element (the current directory).
 //	3. Eliminate each inner .. path name element (the parent directory)
 //	   along with the non-.. element that precedes it.
 //	4. Eliminate .. elements that begin a rooted path:
 //	   that is, replace "/.." by "/" at the beginning of a path,
 //	   assuming Separator is '/'.
 //
 // The returned path ends in a slash only if it represents a root directory,
 // such as "/" on Unix or `C:\` on Windows.
 //
 // Finally, any occurrences of slash are replaced by Separator.
 //
 // If the result of this process is an empty string, Clean
 // returns the string ".".
 //
 // See also Rob Pike, ``Lexical File Names in Plan 9 or
 // Getting Dot-Dot Right,''
 // https://9p.io/sys/doc/lexnames.html
 func Clean(path string) string {
 	originalPath := path
 	volLen := volumeNameLen(path)
 	path = path[volLen:]
 	if path == "" {
 		if volLen > 1 && originalPath[1] != ':' {
 			// should be UNC
 			return FromSlash(originalPath)
 		}
 		return originalPath + "."
 	}
 	rooted := os.IsPathSeparator(path[0])

 	// Invariants:
 	//	reading from path; r is index of next byte to process.
 	//	writing to buf; w is index of next byte to write.
 	//	dotdot is index in buf where .. must stop, either because
 	//		it is the leading slash or it is a leading ../../.. prefix.
 	n := len(path)
 	out := lazybuf{path: path, volAndPath: originalPath, volLen: volLen}
 	r, dotdot := 0, 0
 	if rooted {
 		out.append(Separator)
 		r, dotdot = 1, 1
 	}

 	for r < n {
 		switch {
 		case os.IsPathSeparator(path[r]):
 			// empty path element
 			r++
 		case path[r] == '.' && (r+1 == n || os.IsPathSeparator(path[r+1])):
 			// . element
 			r++
 		case path[r] == '.' && path[r+1] == '.' && (r+2 == n || os.IsPathSeparator(path[r+2])):
 			// .. element: remove to last separator
 			r += 2
 			switch {
 			case out.w > dotdot:
 				// can backtrack
 				out.w--
 				for out.w > dotdot && !os.IsPathSeparator(out.index(out.w)) {
 					out.w--
 				}
 			case !rooted:
 				// cannot backtrack, but not rooted, so append .. element.
 				if out.w > 0 {
 					out.append(Separator)
 				}
 				out.append('.')
 				out.append('.')
 				dotdot = out.w
 			}
 		default:
 			// real path element.
 			// add slash if needed
 			if rooted && out.w != 1 || !rooted && out.w != 0 {
 				out.append(Separator)
 			}
 			// copy element
 			for ; r < n && !os.IsPathSeparator(path[r]); r++ {
 				out.append(path[r])
 			}
 		}
 	}

 	// Turn empty string into "."
 	if out.w == 0 {
 		out.append('.')
 	}

 	return FromSlash(out.string())
 }

 // ToSlash returns the result of replacing each separator character
 // in path with a slash ('/') character. Multiple separators are
 // replaced by multiple slashes.
 func ToSlash(path string) string {
 	if Separator == '/' {
 		return path
 	}
 	return strings.ReplaceAll(path, string(Separator), "/")
 }

 // FromSlash returns the result of replacing each slash ('/') character
 // in path with a separator character. Multiple slashes are replaced
 // by multiple separators.
 func FromSlash(path string) string {
 	if Separator == '/' {
 		return path
 	}
 	return strings.ReplaceAll(path, "/", string(Separator))
 }

 // SplitList splits a list of paths joined by the OS-specific ListSeparator,
 // usually found in PATH or GOPATH environment variables.
 // Unlike strings.Split, SplitList returns an empty slice when passed an empty
 // string.
 func SplitList(path string) []string {
 	return splitList(path)
 }

 // Split splits path immediately following the final Separator,
 // separating it into a directory and file name component.
 // If there is no Separator in path, Split returns an empty dir
 // and file set to path.
 // The returned values have the property that path = dir+file.
 func Split(path string) (dir, file string) {
 	vol := VolumeName(path)
 	i := len(path) - 1
 	for i >= len(vol) && !os.IsPathSeparator(path[i]) {
 		i--
 	}
 	return path[:i+1], path[i+1:]
 }

 // Join joins any number of path elements into a single path,
 // separating them with an OS specific Separator. Empty elements
 // are ignored. The result is Cleaned. However, if the argument
 // list is empty or all its elements are empty, Join returns
 // an empty string.
 // On Windows, the result will only be a UNC path if the first
 // non-empty element is a UNC path.
 func Join(elem ...string) string {
 	return join(elem)
 }

 // Ext returns the file name extension used by path.
 // The extension is the suffix beginning at the final dot
 // in the final element of path; it is empty if there is
 // no dot.
 func Ext(path string) string {
 	for i := len(path) - 1; i >= 0 && !os.IsPathSeparator(path[i]); i-- {
 		if path[i] == '.' {
 			return path[i:]
 		}
 	}
 	return ""
 }

 // EvalSymlinks returns the path name after the evaluation of any symbolic
 // links.
 // If path is relative the result will be relative to the current directory,
 // unless one of the components is an absolute symbolic link.
 // EvalSymlinks calls Clean on the result.
 func EvalSymlinks(path string) (string, error) {
 	return evalSymlinks(path)
 }

 // Abs returns an absolute representation of path.
 // If the path is not absolute it will be joined with the current
 // working directory to turn it into an absolute path. The absolute
 // path name for a given file is not guaranteed to be unique.
 // Abs calls Clean on the result.
 func Abs(path string) (string, error) {
 	return abs(path)
 }

 func unixAbs(path string) (string, error) {
 	if IsAbs(path) {
 		return Clean(path), nil
 	}
 	wd, err := os.Getwd()
 	if err != nil {
 		return "", err
 	}
 	return Join(wd, path), nil
 }

 // Rel returns a relative path that is lexically equivalent to targpath when
 // joined to basepath with an intervening separator. That is,
 // Join(basepath, Rel(basepath, targpath)) is equivalent to targpath itself.
 // On success, the returned path will always be relative to basepath,
 // even if basepath and targpath share no elements.
 // An error is returned if targpath can't be made relative to basepath or if
 // knowing the current working directory would be necessary to compute it.
 // Rel calls Clean on the result.
 func Rel(basepath, targpath string) (string, error) {
 	baseVol := VolumeName(basepath)
 	targVol := VolumeName(targpath)
 	base := Clean(basepath)
 	targ := Clean(targpath)
 	if sameWord(targ, base) {
 		return ".", nil
 	}
 	base = base[len(baseVol):]
 	targ = targ[len(targVol):]
 	if base == "." {
 		base = ""
 	}
 	// Can't use IsAbs - `\a` and `a` are both relative in Windows.
 	baseSlashed := len(base) > 0 && base[0] == Separator
 	targSlashed := len(targ) > 0 && targ[0] == Separator
 	if baseSlashed != targSlashed || !sameWord(baseVol, targVol) {
 		return "", errors.New("Rel: can't make " + targpath + " relative to " + basepath)
 	}
 	// Position base[b0:bi] and targ[t0:ti] at the first differing elements.
 	bl := len(base)
 	tl := len(targ)
 	var b0, bi, t0, ti int
 	for {
 		for bi < bl && base[bi] != Separator {
 			bi++
 		}
 		for ti < tl && targ[ti] != Separator {
 			ti++
 		}
 		if !sameWord(targ[t0:ti], base[b0:bi]) {
 			break
 		}
 		if bi < bl {
 			bi++
 		}
 		if ti < tl {
 			ti++
 		}
 		b0 = bi
 		t0 = ti
 	}
 	if base[b0:bi] == ".." {
 		return "", errors.New("Rel: can't make " + targpath + " relative to " + basepath)
 	}
 	if b0 != bl {
 		// Base elements left. Must go up before going down.
 		seps := strings.Count(base[b0:bl], string(Separator))
 		size := 2 + seps*3
 		if tl != t0 {
 			size += 1 + tl - t0
 		}
 		buf := make([]byte, size)
 		n := copy(buf, "..")
 		for i := 0; i < seps; i++ {
 			buf[n] = Separator
 			copy(buf[n+1:], "..")
 			n += 3
 		}
 		if t0 != tl {
 			buf[n] = Separator
 			copy(buf[n+1:], targ[t0:])
 		}
 		return string(buf), nil
 	}
 	return targ[t0:], nil
 }

 // SkipDir is used as a return value from WalkFuncs to indicate that
 // the directory named in the call is to be skipped. It is not returned
 // as an error by any function.
 var SkipDir = errors.New("skip this directory")

 // WalkFunc is the type of the function called for each file or directory
 // visited by Walk. The path argument contains the argument to Walk as a
 // prefix; that is, if Walk is called with "dir", which is a directory
 // containing the file "a", the walk function will be called with argument
 // "dir/a". The info argument is the os.FileInfo for the named path.
 //
 // If there was a problem walking to the file or directory named by path, the
 // incoming error will describe the problem and the function can decide how
 // to handle that error (and Walk will not descend into that directory). In the
 // case of an error, the info argument will be nil. If an error is returned,
 // processing stops. The sole exception is when the function returns the special
 // value SkipDir. If the function returns SkipDir when invoked on a directory,
 // Walk skips the directory's contents entirely. If the function returns SkipDir
 // when invoked on a non-directory file, Walk skips the remaining files in the
 // containing directory.
 type WalkFunc func(path string, info os.FileInfo, err error) error

 var lstat = os.Lstat // for testing

 // walk recursively descends path, calling walkFn.
 func walk(path string, info os.FileInfo, walkFn WalkFunc) error {
 	if !info.IsDir() {
 		return walkFn(path, info, nil)
 	}

 	names, err := readDirNames(path)
 	err1 := walkFn(path, info, err)
 	// If err != nil, walk can't walk into this directory.
 	// err1 != nil means walkFn want walk to skip this directory or stop walking.
 	// Therefore, if one of err and err1 isn't nil, walk will return.
 	if err != nil || err1 != nil {
 		// The caller's behavior is controlled by the return value, which is decided
 		// by walkFn. walkFn may ignore err and return nil.
 		// If walkFn returns SkipDir, it will be handled by the caller.
 		// So walk should return whatever walkFn returns.
 		return err1
 	}

 	for _, name := range names {
 		filename := Join(path, name)
 		fileInfo, err := lstat(filename)
 		if err != nil {
 			if err := walkFn(filename, fileInfo, err); err != nil && err != SkipDir {
 				return err
 			}
 		} else {
 			err = walk(filename, fileInfo, walkFn)
 			if err != nil {
 				if !fileInfo.IsDir() || err != SkipDir {
 					return err
 				}
 			}
 		}
 	}
 	return nil
 }

 // Walk walks the file tree rooted at root, calling walkFn for each file or
 // directory in the tree, including root. All errors that arise visiting files
 // and directories are filtered by walkFn. The files are walked in lexical
 // order, which makes the output deterministic but means that for very
 // large directories Walk can be inefficient.
 // Walk does not follow symbolic links.
 func Walk(root string, walkFn WalkFunc) error {
 	info, err := os.Lstat(root)
 	if err != nil {
 		err = walkFn(root, nil, err)
 	} else {
 		err = walk(root, info, walkFn)
 	}
 	if err == SkipDir {
 		return nil
 	}
 	return err
 }

 // readDirNames reads the directory named by dirname and returns
 // a sorted list of directory entries.
 func readDirNames(dirname string) ([]string, error) {
 	f, err := os.Open(dirname)
 	if err != nil {
 		return nil, err
 	}
 	names, err := f.Readdirnames(-1)
 	f.Close()
 	if err != nil {
 		return nil, err
 	}
 	sort.Strings(names)
 	return names, nil
 }

 // Base returns the last element of path.
 // Trailing path separators are removed before extracting the last element.
 // If the path is empty, Base returns ".".
 // If the path consists entirely of separators, Base returns a single separator.
 func Base(path string) string {
 	if path == "" {
 		return "."
 	}
 	// Strip trailing slashes.
 	for len(path) > 0 && os.IsPathSeparator(path[len(path)-1]) {
 		path = path[0 : len(path)-1]
 	}
 	// Throw away volume name
 	path = path[len(VolumeName(path)):]
 	// Find the last element
 	i := len(path) - 1
 	for i >= 0 && !os.IsPathSeparator(path[i]) {
 		i--
 	}
 	if i >= 0 {
 		path = path[i+1:]
 	}
 	// If empty now, it had only slashes.
 	if path == "" {
 		return string(Separator)
 	}
 	return path
 }

 // Dir returns all but the last element of path, typically the path's directory.
 // After dropping the final element, Dir calls Clean on the path and trailing
 // slashes are removed.
 // If the path is empty, Dir returns ".".
 // If the path consists entirely of separators, Dir returns a single separator.
 // The returned path does not end in a separator unless it is the root directory.
 func Dir(path string) string {
 	vol := VolumeName(path)
 	i := len(path) - 1
 	for i >= len(vol) && !os.IsPathSeparator(path[i]) {
 		i--
 	}
 	dir := Clean(path[len(vol) : i+1])
 	if dir == "." && len(vol) > 2 {
 		// must be UNC
 		return vol
 	}
 	return vol + dir
 }

 // VolumeName returns leading volume name.
 // Given "C:\foo\bar" it returns "C:" on Windows.
 // Given "\\host\share\foo" it returns "\\host\share".
 // On other platforms it returns "".
 func VolumeName(path string) string {
 	return path[:volumeNameLen(path)]
 }
	// Copyright 2009 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 implements utility routines for manipulating filename paths
	// in a way compatible with the target operating system-defined file paths.
	//
	// The filepath package uses either forward slashes or backslashes,
	// depending on the operating system. To process paths such as URLs
	// that always use forward slashes regardless of the operating
	// system, see the path package.
	package filepath

	import (
	"errors"
	"os"
	"sort"
	"strings"
	)

	// A lazybuf is a lazily constructed path buffer.
	// It supports append, reading previously appended bytes,
	// and retrieving the final string. It does not allocate a buffer
	// to hold the output until that output diverges from s.
	type lazybuf struct {
	path string
	buf []byte
	w int
	volAndPath string
	volLen int
	}

	func (b *lazybuf) index(i int) byte {
	if b.buf != nil {
	return b.buf[i]
	}
	return b.path[i]
	}

	func (b *lazybuf) append(c byte) {
	if b.buf == nil {
	if b.w < len(b.path) && b.path[b.w] == c {
	b.w++
	return
	}
	b.buf = make([]byte, len(b.path))
	copy(b.buf, b.path[:b.w])
	}
	b.buf[b.w] = c
	b.w++
	}

	func (b *lazybuf) string() string {
	if b.buf == nil {
	return b.volAndPath[:b.volLen+b.w]
	}
	return b.volAndPath[:b.volLen] + string(b.buf[:b.w])
	}

	const (
	Separator = os.PathSeparator
	ListSeparator = os.PathListSeparator
	)

	// Clean returns the shortest path name equivalent to path
	// by purely lexical processing. It applies the following rules
	// iteratively until no further processing can be done:
	//
	// 1. Replace multiple Separator elements with a single one.
	// 2. Eliminate each . path name element (the current directory).
	// 3. Eliminate each inner .. path name element (the parent directory)
	// along with the non-.. element that precedes it.
	// 4. Eliminate .. elements that begin a rooted path:
	// that is, replace "/.." by "/" at the beginning of a path,
	// assuming Separator is '/'.
	//
	// The returned path ends in a slash only if it represents a root directory,
	// such as "/" on Unix or `C:\` on Windows.
	//
	// Finally, any occurrences of slash are replaced by Separator.
	//
	// If the result of this process is an empty string, Clean
	// returns the string ".".
	//
	// See also Rob Pike, ``Lexical File Names in Plan 9 or
	// Getting Dot-Dot Right,''
	// https://9p.io/sys/doc/lexnames.html
	func Clean(path string) string {
	originalPath := path
	volLen := volumeNameLen(path)
	path = path[volLen:]
	if path == "" {
	if volLen > 1 && originalPath[1] != ':' {
	// should be UNC
	return FromSlash(originalPath)
	}
	return originalPath + "."
	}
	rooted := os.IsPathSeparator(path[0])

	// Invariants:
	// reading from path; r is index of next byte to process.
	// writing to buf; w is index of next byte to write.
	// dotdot is index in buf where .. must stop, either because
	// it is the leading slash or it is a leading ../../.. prefix.
	n := len(path)
	out := lazybuf{path: path, volAndPath: originalPath, volLen: volLen}
	r, dotdot := 0, 0
	if rooted {
	out.append(Separator)
	r, dotdot = 1, 1
	}

	for r < n {
	switch {
	case os.IsPathSeparator(path[r]):
	// empty path element
	r++
	case path[r] == '.' && (r+1 == n \|\| os.IsPathSeparator(path[r+1])):
	// . element
	r++
	case path[r] == '.' && path[r+1] == '.' && (r+2 == n \|\| os.IsPathSeparator(path[r+2])):
	// .. element: remove to last separator
	r += 2
	switch {
	case out.w > dotdot:
	// can backtrack
	out.w--
	for out.w > dotdot && !os.IsPathSeparator(out.index(out.w)) {
	out.w--
	}
	case !rooted:
	// cannot backtrack, but not rooted, so append .. element.
	if out.w > 0 {
	out.append(Separator)
	}
	out.append('.')
	out.append('.')
	dotdot = out.w
	}
	default:
	// real path element.
	// add slash if needed
	if rooted && out.w != 1 \|\| !rooted && out.w != 0 {
	out.append(Separator)
	}
	// copy element
	for ; r < n && !os.IsPathSeparator(path[r]); r++ {
	out.append(path[r])
	}
	}
	}

	// Turn empty string into "."
	if out.w == 0 {
	out.append('.')
	}

	return FromSlash(out.string())
	}

	// ToSlash returns the result of replacing each separator character
	// in path with a slash ('/') character. Multiple separators are
	// replaced by multiple slashes.
	func ToSlash(path string) string {
	if Separator == '/' {
	return path
	}
	return strings.ReplaceAll(path, string(Separator), "/")
	}

	// FromSlash returns the result of replacing each slash ('/') character
	// in path with a separator character. Multiple slashes are replaced
	// by multiple separators.
	func FromSlash(path string) string {
	if Separator == '/' {
	return path
	}
	return strings.ReplaceAll(path, "/", string(Separator))
	}

	// SplitList splits a list of paths joined by the OS-specific ListSeparator,
	// usually found in PATH or GOPATH environment variables.
	// Unlike strings.Split, SplitList returns an empty slice when passed an empty
	// string.
	func SplitList(path string) []string {
	return splitList(path)
	}

	// Split splits path immediately following the final Separator,
	// separating it into a directory and file name component.
	// If there is no Separator in path, Split returns an empty dir
	// and file set to path.
	// The returned values have the property that path = dir+file.
	func Split(path string) (dir, file string) {
	vol := VolumeName(path)
	i := len(path) - 1
	for i >= len(vol) && !os.IsPathSeparator(path[i]) {
	i--
	}
	return path[:i+1], path[i+1:]
	}

	// Join joins any number of path elements into a single path,
	// separating them with an OS specific Separator. Empty elements
	// are ignored. The result is Cleaned. However, if the argument
	// list is empty or all its elements are empty, Join returns
	// an empty string.
	// On Windows, the result will only be a UNC path if the first
	// non-empty element is a UNC path.
	func Join(elem ...string) string {
	return join(elem)
	}

	// Ext returns the file name extension used by path.
	// The extension is the suffix beginning at the final dot
	// in the final element of path; it is empty if there is
	// no dot.
	func Ext(path string) string {
	for i := len(path) - 1; i >= 0 && !os.IsPathSeparator(path[i]); i-- {
	if path[i] == '.' {
	return path[i:]
	}
	}
	return ""
	}

	// EvalSymlinks returns the path name after the evaluation of any symbolic
	// links.
	// If path is relative the result will be relative to the current directory,
	// unless one of the components is an absolute symbolic link.
	// EvalSymlinks calls Clean on the result.
	func EvalSymlinks(path string) (string, error) {
	return evalSymlinks(path)
	}

	// Abs returns an absolute representation of path.
	// If the path is not absolute it will be joined with the current
	// working directory to turn it into an absolute path. The absolute
	// path name for a given file is not guaranteed to be unique.
	// Abs calls Clean on the result.
	func Abs(path string) (string, error) {
	return abs(path)
	}

	func unixAbs(path string) (string, error) {
	if IsAbs(path) {
	return Clean(path), nil
	}
	wd, err := os.Getwd()
	if err != nil {
	return "", err
	}
	return Join(wd, path), nil
	}

	// Rel returns a relative path that is lexically equivalent to targpath when
	// joined to basepath with an intervening separator. That is,
	// Join(basepath, Rel(basepath, targpath)) is equivalent to targpath itself.
	// On success, the returned path will always be relative to basepath,
	// even if basepath and targpath share no elements.
	// An error is returned if targpath can't be made relative to basepath or if
	// knowing the current working directory would be necessary to compute it.
	// Rel calls Clean on the result.
	func Rel(basepath, targpath string) (string, error) {
	baseVol := VolumeName(basepath)
	targVol := VolumeName(targpath)
	base := Clean(basepath)
	targ := Clean(targpath)
	if sameWord(targ, base) {
	return ".", nil
	}
	base = base[len(baseVol):]
	targ = targ[len(targVol):]
	if base == "." {
	base = ""
	}
	// Can't use IsAbs - `\a` and `a` are both relative in Windows.
	baseSlashed := len(base) > 0 && base[0] == Separator
	targSlashed := len(targ) > 0 && targ[0] == Separator
	if baseSlashed != targSlashed \|\| !sameWord(baseVol, targVol) {
	return "", errors.New("Rel: can't make " + targpath + " relative to " + basepath)
	}
	// Position base[b0:bi] and targ[t0:ti] at the first differing elements.
	bl := len(base)
	tl := len(targ)
	var b0, bi, t0, ti int
	for {
	for bi < bl && base[bi] != Separator {
	bi++
	}
	for ti < tl && targ[ti] != Separator {
	ti++
	}
	if !sameWord(targ[t0:ti], base[b0:bi]) {
	break
	}
	if bi < bl {
	bi++
	}
	if ti < tl {
	ti++
	}
	b0 = bi
	t0 = ti
	}
	if base[b0:bi] == ".." {
	return "", errors.New("Rel: can't make " + targpath + " relative to " + basepath)
	}
	if b0 != bl {
	// Base elements left. Must go up before going down.
	seps := strings.Count(base[b0:bl], string(Separator))
	size := 2 + seps*3
	if tl != t0 {
	size += 1 + tl - t0
	}
	buf := make([]byte, size)
	n := copy(buf, "..")
	for i := 0; i < seps; i++ {
	buf[n] = Separator
	copy(buf[n+1:], "..")
	n += 3
	}
	if t0 != tl {
	buf[n] = Separator
	copy(buf[n+1:], targ[t0:])
	}
	return string(buf), nil
	}
	return targ[t0:], nil
	}

	// SkipDir is used as a return value from WalkFuncs to indicate that
	// the directory named in the call is to be skipped. It is not returned
	// as an error by any function.
	var SkipDir = errors.New("skip this directory")

	// WalkFunc is the type of the function called for each file or directory
	// visited by Walk. The path argument contains the argument to Walk as a
	// prefix; that is, if Walk is called with "dir", which is a directory
	// containing the file "a", the walk function will be called with argument
	// "dir/a". The info argument is the os.FileInfo for the named path.
	//
	// If there was a problem walking to the file or directory named by path, the
	// incoming error will describe the problem and the function can decide how
	// to handle that error (and Walk will not descend into that directory). In the
	// case of an error, the info argument will be nil. If an error is returned,
	// processing stops. The sole exception is when the function returns the special
	// value SkipDir. If the function returns SkipDir when invoked on a directory,
	// Walk skips the directory's contents entirely. If the function returns SkipDir
	// when invoked on a non-directory file, Walk skips the remaining files in the
	// containing directory.
	type WalkFunc func(path string, info os.FileInfo, err error) error

	var lstat = os.Lstat // for testing

	// walk recursively descends path, calling walkFn.
	func walk(path string, info os.FileInfo, walkFn WalkFunc) error {
	if !info.IsDir() {
	return walkFn(path, info, nil)
	}

	names, err := readDirNames(path)
	err1 := walkFn(path, info, err)
	// If err != nil, walk can't walk into this directory.
	// err1 != nil means walkFn want walk to skip this directory or stop walking.
	// Therefore, if one of err and err1 isn't nil, walk will return.
	if err != nil \|\| err1 != nil {
	// The caller's behavior is controlled by the return value, which is decided
	// by walkFn. walkFn may ignore err and return nil.
	// If walkFn returns SkipDir, it will be handled by the caller.
	// So walk should return whatever walkFn returns.
	return err1
	}

	for _, name := range names {
	filename := Join(path, name)
	fileInfo, err := lstat(filename)
	if err != nil {
	if err := walkFn(filename, fileInfo, err); err != nil && err != SkipDir {
	return err
	}
	} else {
	err = walk(filename, fileInfo, walkFn)
	if err != nil {
	if !fileInfo.IsDir() \|\| err != SkipDir {
	return err
	}
	}
	}
	}
	return nil
	}

	// Walk walks the file tree rooted at root, calling walkFn for each file or
	// directory in the tree, including root. All errors that arise visiting files
	// and directories are filtered by walkFn. The files are walked in lexical
	// order, which makes the output deterministic but means that for very
	// large directories Walk can be inefficient.
	// Walk does not follow symbolic links.
	func Walk(root string, walkFn WalkFunc) error {
	info, err := os.Lstat(root)
	if err != nil {
	err = walkFn(root, nil, err)
	} else {
	err = walk(root, info, walkFn)
	}
	if err == SkipDir {
	return nil
	}
	return err
	}

	// readDirNames reads the directory named by dirname and returns
	// a sorted list of directory entries.
	func readDirNames(dirname string) ([]string, error) {
	f, err := os.Open(dirname)
	if err != nil {
	return nil, err
	}
	names, err := f.Readdirnames(-1)
	f.Close()
	if err != nil {
	return nil, err
	}
	sort.Strings(names)
	return names, nil
	}

	// Base returns the last element of path.
	// Trailing path separators are removed before extracting the last element.
	// If the path is empty, Base returns ".".
	// If the path consists entirely of separators, Base returns a single separator.
	func Base(path string) string {
	if path == "" {
	return "."
	}
	// Strip trailing slashes.
	for len(path) > 0 && os.IsPathSeparator(path[len(path)-1]) {
	path = path[0 : len(path)-1]
	}
	// Throw away volume name
	path = path[len(VolumeName(path)):]
	// Find the last element
	i := len(path) - 1
	for i >= 0 && !os.IsPathSeparator(path[i]) {
	i--
	}
	if i >= 0 {
	path = path[i+1:]
	}
	// If empty now, it had only slashes.
	if path == "" {
	return string(Separator)
	}
	return path
	}

	// Dir returns all but the last element of path, typically the path's directory.
	// After dropping the final element, Dir calls Clean on the path and trailing
	// slashes are removed.
	// If the path is empty, Dir returns ".".
	// If the path consists entirely of separators, Dir returns a single separator.
	// The returned path does not end in a separator unless it is the root directory.
	func Dir(path string) string {
	vol := VolumeName(path)
	i := len(path) - 1
	for i >= len(vol) && !os.IsPathSeparator(path[i]) {
	i--
	}
	dir := Clean(path[len(vol) : i+1])
	if dir == "." && len(vol) > 2 {
	// must be UNC
	return vol
	}
	return vol + dir
	}

	// VolumeName returns leading volume name.
	// Given "C:\foo\bar" it returns "C:" on Windows.
	// Given "\\host\share\foo" it returns "\\host\share".
	// On other platforms it returns "".
	func VolumeName(path string) string {
	return path[:volumeNameLen(path)]
	}