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