Source file src/path/filepath/path.go

     1  // Copyright 2009 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package filepath implements utility routines for manipulating filename paths
     6  // in a way compatible with the target operating system-defined file paths.
     7  //
     8  // The filepath package uses either forward slashes or backslashes,
     9  // depending on the operating system. To process paths such as URLs
    10  // that always use forward slashes regardless of the operating
    11  // system, see the [path] package.
    12  package filepath
    13  
    14  import (
    15  	"errors"
    16  	"io/fs"
    17  	"os"
    18  	"sort"
    19  	"strings"
    20  )
    21  
    22  // A lazybuf is a lazily constructed path buffer.
    23  // It supports append, reading previously appended bytes,
    24  // and retrieving the final string. It does not allocate a buffer
    25  // to hold the output until that output diverges from s.
    26  type lazybuf struct {
    27  	path       string
    28  	buf        []byte
    29  	w          int
    30  	volAndPath string
    31  	volLen     int
    32  }
    33  
    34  func (b *lazybuf) index(i int) byte {
    35  	if b.buf != nil {
    36  		return b.buf[i]
    37  	}
    38  	return b.path[i]
    39  }
    40  
    41  func (b *lazybuf) append(c byte) {
    42  	if b.buf == nil {
    43  		if b.w < len(b.path) && b.path[b.w] == c {
    44  			b.w++
    45  			return
    46  		}
    47  		b.buf = make([]byte, len(b.path))
    48  		copy(b.buf, b.path[:b.w])
    49  	}
    50  	b.buf[b.w] = c
    51  	b.w++
    52  }
    53  
    54  func (b *lazybuf) prepend(prefix ...byte) {
    55  	b.buf = append(prefix, b.buf...)
    56  	b.w += len(prefix)
    57  }
    58  
    59  func (b *lazybuf) string() string {
    60  	if b.buf == nil {
    61  		return b.volAndPath[:b.volLen+b.w]
    62  	}
    63  	return b.volAndPath[:b.volLen] + string(b.buf[:b.w])
    64  }
    65  
    66  const (
    67  	Separator     = os.PathSeparator
    68  	ListSeparator = os.PathListSeparator
    69  )
    70  
    71  // Clean returns the shortest path name equivalent to path
    72  // by purely lexical processing. It applies the following rules
    73  // iteratively until no further processing can be done:
    74  //
    75  //  1. Replace multiple Separator elements with a single one.
    76  //  2. Eliminate each . path name element (the current directory).
    77  //  3. Eliminate each inner .. path name element (the parent directory)
    78  //     along with the non-.. element that precedes it.
    79  //  4. Eliminate .. elements that begin a rooted path:
    80  //     that is, replace "/.." by "/" at the beginning of a path,
    81  //     assuming Separator is '/'.
    82  //
    83  // The returned path ends in a slash only if it represents a root directory,
    84  // such as "/" on Unix or `C:\` on Windows.
    85  //
    86  // Finally, any occurrences of slash are replaced by Separator.
    87  //
    88  // If the result of this process is an empty string, Clean
    89  // returns the string ".".
    90  //
    91  // On Windows, Clean does not modify the volume name other than to replace
    92  // occurrences of "/" with `\`.
    93  // For example, Clean("//host/share/../x") returns `\\host\share\x`.
    94  //
    95  // See also Rob Pike, “Lexical File Names in Plan 9 or
    96  // Getting Dot-Dot Right,”
    97  // https://9p.io/sys/doc/lexnames.html
    98  func Clean(path string) string {
    99  	originalPath := path
   100  	volLen := volumeNameLen(path)
   101  	path = path[volLen:]
   102  	if path == "" {
   103  		if volLen > 1 && os.IsPathSeparator(originalPath[0]) && os.IsPathSeparator(originalPath[1]) {
   104  			// should be UNC
   105  			return FromSlash(originalPath)
   106  		}
   107  		return originalPath + "."
   108  	}
   109  	rooted := os.IsPathSeparator(path[0])
   110  
   111  	// Invariants:
   112  	//	reading from path; r is index of next byte to process.
   113  	//	writing to buf; w is index of next byte to write.
   114  	//	dotdot is index in buf where .. must stop, either because
   115  	//		it is the leading slash or it is a leading ../../.. prefix.
   116  	n := len(path)
   117  	out := lazybuf{path: path, volAndPath: originalPath, volLen: volLen}
   118  	r, dotdot := 0, 0
   119  	if rooted {
   120  		out.append(Separator)
   121  		r, dotdot = 1, 1
   122  	}
   123  
   124  	for r < n {
   125  		switch {
   126  		case os.IsPathSeparator(path[r]):
   127  			// empty path element
   128  			r++
   129  		case path[r] == '.' && (r+1 == n || os.IsPathSeparator(path[r+1])):
   130  			// . element
   131  			r++
   132  		case path[r] == '.' && path[r+1] == '.' && (r+2 == n || os.IsPathSeparator(path[r+2])):
   133  			// .. element: remove to last separator
   134  			r += 2
   135  			switch {
   136  			case out.w > dotdot:
   137  				// can backtrack
   138  				out.w--
   139  				for out.w > dotdot && !os.IsPathSeparator(out.index(out.w)) {
   140  					out.w--
   141  				}
   142  			case !rooted:
   143  				// cannot backtrack, but not rooted, so append .. element.
   144  				if out.w > 0 {
   145  					out.append(Separator)
   146  				}
   147  				out.append('.')
   148  				out.append('.')
   149  				dotdot = out.w
   150  			}
   151  		default:
   152  			// real path element.
   153  			// add slash if needed
   154  			if rooted && out.w != 1 || !rooted && out.w != 0 {
   155  				out.append(Separator)
   156  			}
   157  			// copy element
   158  			for ; r < n && !os.IsPathSeparator(path[r]); r++ {
   159  				out.append(path[r])
   160  			}
   161  		}
   162  	}
   163  
   164  	// Turn empty string into "."
   165  	if out.w == 0 {
   166  		out.append('.')
   167  	}
   168  
   169  	postClean(&out) // avoid creating absolute paths on Windows
   170  	return FromSlash(out.string())
   171  }
   172  
   173  // IsLocal reports whether path, using lexical analysis only, has all of these properties:
   174  //
   175  //   - is within the subtree rooted at the directory in which path is evaluated
   176  //   - is not an absolute path
   177  //   - is not empty
   178  //   - on Windows, is not a reserved name such as "NUL"
   179  //
   180  // If IsLocal(path) returns true, then
   181  // Join(base, path) will always produce a path contained within base and
   182  // Clean(path) will always produce an unrooted path with no ".." path elements.
   183  //
   184  // IsLocal is a purely lexical operation.
   185  // In particular, it does not account for the effect of any symbolic links
   186  // that may exist in the filesystem.
   187  func IsLocal(path string) bool {
   188  	return isLocal(path)
   189  }
   190  
   191  func unixIsLocal(path string) bool {
   192  	if IsAbs(path) || path == "" {
   193  		return false
   194  	}
   195  	hasDots := false
   196  	for p := path; p != ""; {
   197  		var part string
   198  		part, p, _ = strings.Cut(p, "/")
   199  		if part == "." || part == ".." {
   200  			hasDots = true
   201  			break
   202  		}
   203  	}
   204  	if hasDots {
   205  		path = Clean(path)
   206  	}
   207  	if path == ".." || strings.HasPrefix(path, "../") {
   208  		return false
   209  	}
   210  	return true
   211  }
   212  
   213  // ToSlash returns the result of replacing each separator character
   214  // in path with a slash ('/') character. Multiple separators are
   215  // replaced by multiple slashes.
   216  func ToSlash(path string) string {
   217  	if Separator == '/' {
   218  		return path
   219  	}
   220  	return strings.ReplaceAll(path, string(Separator), "/")
   221  }
   222  
   223  // FromSlash returns the result of replacing each slash ('/') character
   224  // in path with a separator character. Multiple slashes are replaced
   225  // by multiple separators.
   226  func FromSlash(path string) string {
   227  	if Separator == '/' {
   228  		return path
   229  	}
   230  	return strings.ReplaceAll(path, "/", string(Separator))
   231  }
   232  
   233  // SplitList splits a list of paths joined by the OS-specific ListSeparator,
   234  // usually found in PATH or GOPATH environment variables.
   235  // Unlike strings.Split, SplitList returns an empty slice when passed an empty
   236  // string.
   237  func SplitList(path string) []string {
   238  	return splitList(path)
   239  }
   240  
   241  // Split splits path immediately following the final Separator,
   242  // separating it into a directory and file name component.
   243  // If there is no Separator in path, Split returns an empty dir
   244  // and file set to path.
   245  // The returned values have the property that path = dir+file.
   246  func Split(path string) (dir, file string) {
   247  	vol := VolumeName(path)
   248  	i := len(path) - 1
   249  	for i >= len(vol) && !os.IsPathSeparator(path[i]) {
   250  		i--
   251  	}
   252  	return path[:i+1], path[i+1:]
   253  }
   254  
   255  // Join joins any number of path elements into a single path,
   256  // separating them with an OS specific Separator. Empty elements
   257  // are ignored. The result is Cleaned. However, if the argument
   258  // list is empty or all its elements are empty, Join returns
   259  // an empty string.
   260  // On Windows, the result will only be a UNC path if the first
   261  // non-empty element is a UNC path.
   262  func Join(elem ...string) string {
   263  	return join(elem)
   264  }
   265  
   266  // Ext returns the file name extension used by path.
   267  // The extension is the suffix beginning at the final dot
   268  // in the final element of path; it is empty if there is
   269  // no dot.
   270  func Ext(path string) string {
   271  	for i := len(path) - 1; i >= 0 && !os.IsPathSeparator(path[i]); i-- {
   272  		if path[i] == '.' {
   273  			return path[i:]
   274  		}
   275  	}
   276  	return ""
   277  }
   278  
   279  // EvalSymlinks returns the path name after the evaluation of any symbolic
   280  // links.
   281  // If path is relative the result will be relative to the current directory,
   282  // unless one of the components is an absolute symbolic link.
   283  // EvalSymlinks calls Clean on the result.
   284  func EvalSymlinks(path string) (string, error) {
   285  	return evalSymlinks(path)
   286  }
   287  
   288  // Abs returns an absolute representation of path.
   289  // If the path is not absolute it will be joined with the current
   290  // working directory to turn it into an absolute path. The absolute
   291  // path name for a given file is not guaranteed to be unique.
   292  // Abs calls Clean on the result.
   293  func Abs(path string) (string, error) {
   294  	return abs(path)
   295  }
   296  
   297  func unixAbs(path string) (string, error) {
   298  	if IsAbs(path) {
   299  		return Clean(path), nil
   300  	}
   301  	wd, err := os.Getwd()
   302  	if err != nil {
   303  		return "", err
   304  	}
   305  	return Join(wd, path), nil
   306  }
   307  
   308  // Rel returns a relative path that is lexically equivalent to targpath when
   309  // joined to basepath with an intervening separator. That is,
   310  // Join(basepath, Rel(basepath, targpath)) is equivalent to targpath itself.
   311  // On success, the returned path will always be relative to basepath,
   312  // even if basepath and targpath share no elements.
   313  // An error is returned if targpath can't be made relative to basepath or if
   314  // knowing the current working directory would be necessary to compute it.
   315  // Rel calls Clean on the result.
   316  func Rel(basepath, targpath string) (string, error) {
   317  	baseVol := VolumeName(basepath)
   318  	targVol := VolumeName(targpath)
   319  	base := Clean(basepath)
   320  	targ := Clean(targpath)
   321  	if sameWord(targ, base) {
   322  		return ".", nil
   323  	}
   324  	base = base[len(baseVol):]
   325  	targ = targ[len(targVol):]
   326  	if base == "." {
   327  		base = ""
   328  	} else if base == "" && volumeNameLen(baseVol) > 2 /* isUNC */ {
   329  		// Treat any targetpath matching `\\host\share` basepath as absolute path.
   330  		base = string(Separator)
   331  	}
   332  
   333  	// Can't use IsAbs - `\a` and `a` are both relative in Windows.
   334  	baseSlashed := len(base) > 0 && base[0] == Separator
   335  	targSlashed := len(targ) > 0 && targ[0] == Separator
   336  	if baseSlashed != targSlashed || !sameWord(baseVol, targVol) {
   337  		return "", errors.New("Rel: can't make " + targpath + " relative to " + basepath)
   338  	}
   339  	// Position base[b0:bi] and targ[t0:ti] at the first differing elements.
   340  	bl := len(base)
   341  	tl := len(targ)
   342  	var b0, bi, t0, ti int
   343  	for {
   344  		for bi < bl && base[bi] != Separator {
   345  			bi++
   346  		}
   347  		for ti < tl && targ[ti] != Separator {
   348  			ti++
   349  		}
   350  		if !sameWord(targ[t0:ti], base[b0:bi]) {
   351  			break
   352  		}
   353  		if bi < bl {
   354  			bi++
   355  		}
   356  		if ti < tl {
   357  			ti++
   358  		}
   359  		b0 = bi
   360  		t0 = ti
   361  	}
   362  	if base[b0:bi] == ".." {
   363  		return "", errors.New("Rel: can't make " + targpath + " relative to " + basepath)
   364  	}
   365  	if b0 != bl {
   366  		// Base elements left. Must go up before going down.
   367  		seps := strings.Count(base[b0:bl], string(Separator))
   368  		size := 2 + seps*3
   369  		if tl != t0 {
   370  			size += 1 + tl - t0
   371  		}
   372  		buf := make([]byte, size)
   373  		n := copy(buf, "..")
   374  		for i := 0; i < seps; i++ {
   375  			buf[n] = Separator
   376  			copy(buf[n+1:], "..")
   377  			n += 3
   378  		}
   379  		if t0 != tl {
   380  			buf[n] = Separator
   381  			copy(buf[n+1:], targ[t0:])
   382  		}
   383  		return string(buf), nil
   384  	}
   385  	return targ[t0:], nil
   386  }
   387  
   388  // SkipDir is used as a return value from WalkFuncs to indicate that
   389  // the directory named in the call is to be skipped. It is not returned
   390  // as an error by any function.
   391  var SkipDir error = fs.SkipDir
   392  
   393  // SkipAll is used as a return value from WalkFuncs to indicate that
   394  // all remaining files and directories are to be skipped. It is not returned
   395  // as an error by any function.
   396  var SkipAll error = fs.SkipAll
   397  
   398  // WalkFunc is the type of the function called by Walk to visit each
   399  // file or directory.
   400  //
   401  // The path argument contains the argument to Walk as a prefix.
   402  // That is, if Walk is called with root argument "dir" and finds a file
   403  // named "a" in that directory, the walk function will be called with
   404  // argument "dir/a".
   405  //
   406  // The directory and file are joined with Join, which may clean the
   407  // directory name: if Walk is called with the root argument "x/../dir"
   408  // and finds a file named "a" in that directory, the walk function will
   409  // be called with argument "dir/a", not "x/../dir/a".
   410  //
   411  // The info argument is the fs.FileInfo for the named path.
   412  //
   413  // The error result returned by the function controls how Walk continues.
   414  // If the function returns the special value SkipDir, Walk skips the
   415  // current directory (path if info.IsDir() is true, otherwise path's
   416  // parent directory). If the function returns the special value SkipAll,
   417  // Walk skips all remaining files and directories. Otherwise, if the function
   418  // returns a non-nil error, Walk stops entirely and returns that error.
   419  //
   420  // The err argument reports an error related to path, signaling that Walk
   421  // will not walk into that directory. The function can decide how to
   422  // handle that error; as described earlier, returning the error will
   423  // cause Walk to stop walking the entire tree.
   424  //
   425  // Walk calls the function with a non-nil err argument in two cases.
   426  //
   427  // First, if an os.Lstat on the root directory or any directory or file
   428  // in the tree fails, Walk calls the function with path set to that
   429  // directory or file's path, info set to nil, and err set to the error
   430  // from os.Lstat.
   431  //
   432  // Second, if a directory's Readdirnames method fails, Walk calls the
   433  // function with path set to the directory's path, info, set to an
   434  // fs.FileInfo describing the directory, and err set to the error from
   435  // Readdirnames.
   436  type WalkFunc func(path string, info fs.FileInfo, err error) error
   437  
   438  var lstat = os.Lstat // for testing
   439  
   440  // walkDir recursively descends path, calling walkDirFn.
   441  func walkDir(path string, d fs.DirEntry, walkDirFn fs.WalkDirFunc) error {
   442  	if err := walkDirFn(path, d, nil); err != nil || !d.IsDir() {
   443  		if err == SkipDir && d.IsDir() {
   444  			// Successfully skipped directory.
   445  			err = nil
   446  		}
   447  		return err
   448  	}
   449  
   450  	dirs, err := readDir(path)
   451  	if err != nil {
   452  		// Second call, to report ReadDir error.
   453  		err = walkDirFn(path, d, err)
   454  		if err != nil {
   455  			if err == SkipDir && d.IsDir() {
   456  				err = nil
   457  			}
   458  			return err
   459  		}
   460  	}
   461  
   462  	for _, d1 := range dirs {
   463  		path1 := Join(path, d1.Name())
   464  		if err := walkDir(path1, d1, walkDirFn); err != nil {
   465  			if err == SkipDir {
   466  				break
   467  			}
   468  			return err
   469  		}
   470  	}
   471  	return nil
   472  }
   473  
   474  // walk recursively descends path, calling walkFn.
   475  func walk(path string, info fs.FileInfo, walkFn WalkFunc) error {
   476  	if !info.IsDir() {
   477  		return walkFn(path, info, nil)
   478  	}
   479  
   480  	names, err := readDirNames(path)
   481  	err1 := walkFn(path, info, err)
   482  	// If err != nil, walk can't walk into this directory.
   483  	// err1 != nil means walkFn want walk to skip this directory or stop walking.
   484  	// Therefore, if one of err and err1 isn't nil, walk will return.
   485  	if err != nil || err1 != nil {
   486  		// The caller's behavior is controlled by the return value, which is decided
   487  		// by walkFn. walkFn may ignore err and return nil.
   488  		// If walkFn returns SkipDir or SkipAll, it will be handled by the caller.
   489  		// So walk should return whatever walkFn returns.
   490  		return err1
   491  	}
   492  
   493  	for _, name := range names {
   494  		filename := Join(path, name)
   495  		fileInfo, err := lstat(filename)
   496  		if err != nil {
   497  			if err := walkFn(filename, fileInfo, err); err != nil && err != SkipDir {
   498  				return err
   499  			}
   500  		} else {
   501  			err = walk(filename, fileInfo, walkFn)
   502  			if err != nil {
   503  				if !fileInfo.IsDir() || err != SkipDir {
   504  					return err
   505  				}
   506  			}
   507  		}
   508  	}
   509  	return nil
   510  }
   511  
   512  // WalkDir walks the file tree rooted at root, calling fn for each file or
   513  // directory in the tree, including root.
   514  //
   515  // All errors that arise visiting files and directories are filtered by fn:
   516  // see the fs.WalkDirFunc documentation for details.
   517  //
   518  // The files are walked in lexical order, which makes the output deterministic
   519  // but requires WalkDir to read an entire directory into memory before proceeding
   520  // to walk that directory.
   521  //
   522  // WalkDir does not follow symbolic links.
   523  //
   524  // WalkDir calls fn with paths that use the separator character appropriate
   525  // for the operating system. This is unlike [io/fs.WalkDir], which always
   526  // uses slash separated paths.
   527  func WalkDir(root string, fn fs.WalkDirFunc) error {
   528  	info, err := os.Lstat(root)
   529  	if err != nil {
   530  		err = fn(root, nil, err)
   531  	} else {
   532  		err = walkDir(root, &statDirEntry{info}, fn)
   533  	}
   534  	if err == SkipDir || err == SkipAll {
   535  		return nil
   536  	}
   537  	return err
   538  }
   539  
   540  type statDirEntry struct {
   541  	info fs.FileInfo
   542  }
   543  
   544  func (d *statDirEntry) Name() string               { return d.info.Name() }
   545  func (d *statDirEntry) IsDir() bool                { return d.info.IsDir() }
   546  func (d *statDirEntry) Type() fs.FileMode          { return d.info.Mode().Type() }
   547  func (d *statDirEntry) Info() (fs.FileInfo, error) { return d.info, nil }
   548  
   549  func (d *statDirEntry) String() string {
   550  	return fs.FormatDirEntry(d)
   551  }
   552  
   553  // Walk walks the file tree rooted at root, calling fn for each file or
   554  // directory in the tree, including root.
   555  //
   556  // All errors that arise visiting files and directories are filtered by fn:
   557  // see the WalkFunc documentation for details.
   558  //
   559  // The files are walked in lexical order, which makes the output deterministic
   560  // but requires Walk to read an entire directory into memory before proceeding
   561  // to walk that directory.
   562  //
   563  // Walk does not follow symbolic links.
   564  //
   565  // Walk is less efficient than WalkDir, introduced in Go 1.16,
   566  // which avoids calling os.Lstat on every visited file or directory.
   567  func Walk(root string, fn WalkFunc) error {
   568  	info, err := os.Lstat(root)
   569  	if err != nil {
   570  		err = fn(root, nil, err)
   571  	} else {
   572  		err = walk(root, info, fn)
   573  	}
   574  	if err == SkipDir || err == SkipAll {
   575  		return nil
   576  	}
   577  	return err
   578  }
   579  
   580  // readDir reads the directory named by dirname and returns
   581  // a sorted list of directory entries.
   582  func readDir(dirname string) ([]fs.DirEntry, error) {
   583  	f, err := os.Open(dirname)
   584  	if err != nil {
   585  		return nil, err
   586  	}
   587  	dirs, err := f.ReadDir(-1)
   588  	f.Close()
   589  	if err != nil {
   590  		return nil, err
   591  	}
   592  	sort.Slice(dirs, func(i, j int) bool { return dirs[i].Name() < dirs[j].Name() })
   593  	return dirs, nil
   594  }
   595  
   596  // readDirNames reads the directory named by dirname and returns
   597  // a sorted list of directory entry names.
   598  func readDirNames(dirname string) ([]string, error) {
   599  	f, err := os.Open(dirname)
   600  	if err != nil {
   601  		return nil, err
   602  	}
   603  	names, err := f.Readdirnames(-1)
   604  	f.Close()
   605  	if err != nil {
   606  		return nil, err
   607  	}
   608  	sort.Strings(names)
   609  	return names, nil
   610  }
   611  
   612  // Base returns the last element of path.
   613  // Trailing path separators are removed before extracting the last element.
   614  // If the path is empty, Base returns ".".
   615  // If the path consists entirely of separators, Base returns a single separator.
   616  func Base(path string) string {
   617  	if path == "" {
   618  		return "."
   619  	}
   620  	// Strip trailing slashes.
   621  	for len(path) > 0 && os.IsPathSeparator(path[len(path)-1]) {
   622  		path = path[0 : len(path)-1]
   623  	}
   624  	// Throw away volume name
   625  	path = path[len(VolumeName(path)):]
   626  	// Find the last element
   627  	i := len(path) - 1
   628  	for i >= 0 && !os.IsPathSeparator(path[i]) {
   629  		i--
   630  	}
   631  	if i >= 0 {
   632  		path = path[i+1:]
   633  	}
   634  	// If empty now, it had only slashes.
   635  	if path == "" {
   636  		return string(Separator)
   637  	}
   638  	return path
   639  }
   640  
   641  // Dir returns all but the last element of path, typically the path's directory.
   642  // After dropping the final element, Dir calls Clean on the path and trailing
   643  // slashes are removed.
   644  // If the path is empty, Dir returns ".".
   645  // If the path consists entirely of separators, Dir returns a single separator.
   646  // The returned path does not end in a separator unless it is the root directory.
   647  func Dir(path string) string {
   648  	vol := VolumeName(path)
   649  	i := len(path) - 1
   650  	for i >= len(vol) && !os.IsPathSeparator(path[i]) {
   651  		i--
   652  	}
   653  	dir := Clean(path[len(vol) : i+1])
   654  	if dir == "." && len(vol) > 2 {
   655  		// must be UNC
   656  		return vol
   657  	}
   658  	return vol + dir
   659  }
   660  
   661  // VolumeName returns leading volume name.
   662  // Given "C:\foo\bar" it returns "C:" on Windows.
   663  // Given "\\host\share\foo" it returns "\\host\share".
   664  // On other platforms it returns "".
   665  func VolumeName(path string) string {
   666  	return FromSlash(path[:volumeNameLen(path)])
   667  }
   668  

View as plain text