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

View as plain text