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

View as plain text