1// Package fastwalk provides a faster version of [filepath.WalkDir] for file
2// system scanning tools.
3package fastwalk
4
5/*
6 * This code borrows heavily from golang.org/x/tools/internal/fastwalk
7 * and as such the Go license can be found in the go.LICENSE file and
8 * is reproduced below:
9 *
10 * Copyright (c) 2009 The Go Authors. All rights reserved.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions are
14 * met:
15 *
16 * * Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * * Redistributions in binary form must reproduce the above
19 * copyright notice, this list of conditions and the following disclaimer
20 * in the documentation and/or other materials provided with the
21 * distribution.
22 * * Neither the name of Google Inc. nor the names of its
23 * contributors may be used to endorse or promote products derived from
24 * this software without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
27 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
28 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
29 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
30 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
31 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
32 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
33 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
34 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
35 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
36 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 */
38
39import (
40 "errors"
41 "io/fs"
42 "os"
43 "path/filepath"
44 "runtime"
45 "sync"
46)
47
48// ErrTraverseLink is used as a return value from WalkDirFuncs to indicate that
49// the symlink named in the call may be traversed. This error is ignored if
50// the Follow [Config] option is true.
51var ErrTraverseLink = errors.New("fastwalk: traverse symlink, assuming target is a directory")
52
53// ErrSkipFiles is a used as a return value from WalkFuncs to indicate that the
54// callback should not be called for any other files in the current directory.
55// Child directories will still be traversed.
56var ErrSkipFiles = errors.New("fastwalk: skip remaining files in directory")
57
58// SkipDir is used as a return value from WalkDirFuncs to indicate that
59// the directory named in the call is to be skipped. It is not returned
60// as an error by any function.
61var SkipDir = fs.SkipDir
62
63// TODO(charlie): Look into implementing the fs.SkipAll behavior of
64// filepath.Walk and filepath.WalkDir. This may not be possible without taking
65// a performance hit.
66
67// DefaultNumWorkers returns the default number of worker goroutines to use in
68// [Walk] and is the value of [runtime.GOMAXPROCS](-1) clamped to a range
69// of 4 to 32 except on Darwin where it is either 4 (8 cores or less), 6
70// (10 cores or less), or 10 (more than 10 cores). This is because Walk / IO
71// performance on Darwin degrades with more concurrency.
72//
73// The optimal number for your workload may be lower or higher. The results
74// of BenchmarkFastWalkNumWorkers benchmark may be informative.
75func DefaultNumWorkers() int {
76 numCPU := runtime.GOMAXPROCS(-1)
77 if numCPU < 4 {
78 return 4
79 }
80 // Darwin IO performance on APFS can slow with increased parallelism.
81 // Depending on CPU, stat(2) performance is best around 4-10 workers
82 // and file IO is best around 4 workers. More workers only benefit CPU
83 // intensive tasks.
84 //
85 // NB(Charlie): As of macOS 15, the parallel performance of readdir_r(3)
86 // and stat(2) calls has improved and is now generally the number of
87 // performance cores (on ARM Macs).
88 //
89 // TODO: Consider using the value of sysctl("hw.perflevel0.physicalcpu").
90 // TODO: Find someone with a Mac Studio to test higher core counts.
91 if runtime.GOOS == "darwin" {
92 switch {
93 case numCPU <= 8:
94 return 4
95 case numCPU <= 10:
96 return 6
97 default: // numCPU > 10
98 return 10
99 }
100 }
101 if numCPU > 32 {
102 return 32
103 }
104 return numCPU
105}
106
107// DefaultToSlash returns true if this is a Go program compiled for Windows
108// running in an environment ([MSYS/MSYS2] or [Git for Windows]) that uses
109// forward slashes as the path separator instead of the native backslash.
110//
111// On non-Windows OSes this is a no-op and always returns false.
112//
113// To detect if we're running in [MSYS/MSYS2] we check if the "MSYSTEM"
114// environment variable exists.
115//
116// DefaultToSlash does not detect if this is a Windows executable running in [WSL].
117// Instead, users should (ideally) use programs compiled for Linux in WSL.
118//
119// See: [github.com/junegunn/fzf/issues/3859]
120//
121// NOTE: The reason that we do not check if we're running in WSL is that the
122// test was inconsistent since it depended on the working directory (it seems
123// that "/proc" cannot be accessed when programs are ran from a mounted Windows
124// directory) and what environment variables are shared between WSL and Win32
125// (this requires explicit [configuration]).
126//
127// [MSYS/MSYS2]: https://www.msys2.org/
128// [WSL]: https://learn.microsoft.com/en-us/windows/wsl/about
129// [Git for Windows]: https://gitforwindows.org/
130// [github.com/junegunn/fzf/issues/3859]: https://github.com/junegunn/fzf/issues/3859
131// [configuration]: https://devblogs.microsoft.com/commandline/share-environment-vars-between-wsl-and-windows/
132func DefaultToSlash() bool {
133 if runtime.GOOS != "windows" {
134 return false
135 }
136 // Previously this function attempted to determine if this is a Windows exe
137 // running in WSL. The check was:
138 //
139 // * File /proc/sys/fs/binfmt_misc/WSLInterop exist
140 // * Env var "WSL_DISTRO_NAME" exits
141 // * /proc/version contains "Microsoft" or "microsoft"
142 //
143 // Below are my notes explaining why that check was flaky:
144 //
145 // NOTE: This appears to fail when ran from WSL when the current working
146 // directory is a Windows directory that is mounted ("/mnt/c/...") since
147 // "/proc" is not accessible. It works if ran from a directory that is not
148 // mounted. Additionally, the "WSL_DISTRO_NAME" environment variable is not
149 // set when ran from WSL.
150 //
151 // I'm not sure what causes this, but it would be great to find a solution.
152 // My guess is that when ran from a Windows directory it uses the native
153 // Windows path syscalls (for example os.Getwd reports the canonical Windows
154 // path when a Go exe is ran from a mounted directory in WSL, but reports the
155 // WSL path when ran from outside a mounted Windows directory).
156 //
157 // That said, the real solution here is to use programs compiled for Linux
158 // when running in WSL.
159 _, ok := os.LookupEnv("MSYSTEM")
160 return ok
161}
162
163// SortMode determines the order that a directory's entries are visited by
164// [Walk]. Sorting applies only at the directory level and since we process
165// directories in parallel the order in which all files are visited is still
166// non-deterministic.
167//
168// Sorting is mostly useful for programs that print the output of Walk since
169// it makes it slightly more ordered compared to the default directory order.
170// Sorting may also help some programs that wish to change the order in which
171// a directory is processed by either processing all files first or enqueuing
172// all directories before processing files.
173//
174// All lexical sorting is case-sensitive.
175//
176// The overhead of sorting is minimal compared to the syscalls needed to
177// walk directories. The impact on performance due to changing the order
178// in which directory entries are processed will be dependent on the workload
179// and the structure of the file tree being visited (it might also have no
180// impact).
181type SortMode uint32
182
183const (
184 // Perform no sorting. Files will be visited in directory order.
185 // This is the default.
186 SortNone SortMode = iota
187
188 // Directory entries are sorted by name before being visited.
189 SortLexical
190
191 // Sort the directory entries so that regular files and non-directories
192 // (e.g. symbolic links) are visited before directories. Within each
193 // group (regular files, other files, directories) the entries are sorted
194 // by name.
195 //
196 // This is likely the mode that programs that print the output of Walk
197 // want to use. Since by processing all files before enqueuing
198 // sub-directories the output is slightly more grouped.
199 //
200 // Example order:
201 // - file: "a.txt"
202 // - file: "b.txt"
203 // - link: "a.link"
204 // - link: "b.link"
205 // - dir: "d1/"
206 // - dir: "d2/"
207 //
208 SortFilesFirst
209
210 // Sort the directory entries so that directories are visited first, then
211 // regular files are visited, and finally everything else is visited
212 // (e.g. symbolic links). Within each group (directories, regular files,
213 // other files) the entries are sorted by name.
214 //
215 // This mode is might be useful at preventing other walk goroutines from
216 // stalling due to lack of work since it immediately enqueues all of a
217 // directory's sub-directories for processing. The impact on performance
218 // will be dependent on the workload and the structure of the file tree
219 // being visited - it might also have no (or even a negative) impact on
220 // performance so testing/benchmarking is recommend.
221 //
222 // An example workload that might cause this is: processing one directory
223 // takes a long time, that directory has sub-directories we want to walk,
224 // while processing that directory all other Walk goroutines have finished
225 // processing their directories, those goroutines are now stalled waiting
226 // for more work (waiting on the one running goroutine to enqueue its
227 // sub-directories for processing).
228 //
229 // This might also be beneficial if processing files is expensive.
230 //
231 // Example order:
232 // - dir: "d1/"
233 // - dir: "d2/"
234 // - file: "a.txt"
235 // - file: "b.txt"
236 // - link: "a.link"
237 // - link: "b.link"
238 //
239 SortDirsFirst
240)
241
242var sortModeStrs = [...]string{
243 SortNone: "None",
244 SortLexical: "Lexical",
245 SortDirsFirst: "DirsFirst",
246 SortFilesFirst: "FilesFirst",
247}
248
249func (s SortMode) String() string {
250 if 0 <= int(s) && int(s) < len(sortModeStrs) {
251 return sortModeStrs[s]
252 }
253 return "SortMode(" + itoa(uint64(s)) + ")"
254}
255
256// DefaultConfig is the default [Config] used when none is supplied.
257var DefaultConfig = Config{
258 Follow: false,
259 ToSlash: DefaultToSlash(),
260 NumWorkers: DefaultNumWorkers(),
261 Sort: SortNone,
262 MaxDepth: 0,
263}
264
265// A Config controls the behavior of [Walk].
266type Config struct {
267 // TODO: do we want to pass a sentinel error to WalkFunc if
268 // a symlink loop is detected?
269
270 // Follow symbolic links ignoring directories that would lead
271 // to infinite loops; that is, entering a previously visited
272 // directory that is an ancestor of the last file encountered.
273 //
274 // The sentinel error ErrTraverseLink is ignored when Follow
275 // is true (this to prevent users from defeating the loop
276 // detection logic), but SkipDir and ErrSkipFiles are still
277 // respected.
278 Follow bool
279
280 // Join all paths using a forward slash "/" instead of the system
281 // default (the root path will be converted with filepath.ToSlash).
282 // This option exists for users on Windows Subsystem for Linux (WSL)
283 // that are running a Windows executable (like FZF) in WSL and need
284 // forward slashes for compatibility (since binary was compiled for
285 // Windows the path separator will be "\" which can cause issues in
286 // in a Unix shell).
287 //
288 // This option has no effect when the OS path separator is a
289 // forward slash "/".
290 //
291 // See FZF issue: https://github.com/junegunn/fzf/issues/3859
292 ToSlash bool
293
294 // Sort a directory's entries by SortMode before visiting them.
295 // The order that files are visited is deterministic only at the directory
296 // level, but not generally deterministic because we process directories
297 // in parallel. The performance impact of sorting entries is generally
298 // negligible compared to the syscalls required to read directories.
299 //
300 // This option mostly exists for programs that print the output of Walk
301 // (like FZF) since it provides some order and thus makes the output much
302 // nicer compared to the default directory order, which is basically random.
303 Sort SortMode
304
305 // Number of parallel workers to use. If NumWorkers if ≤ 0 then
306 // DefaultNumWorkers is used.
307 NumWorkers int
308
309 // MaxDepth limits the depth of directory traversal to MaxDepth levels
310 // beyond the root directory being walked. By default, there is no limit
311 // on the search depth and a value of zero or less disables this feature.
312 MaxDepth int
313}
314
315// Copy returns a copy of c. If c is nil an empty [Config] is returned.
316func (c *Config) Copy() *Config {
317 dupe := new(Config)
318 if c != nil {
319 *dupe = *c
320 }
321 return dupe
322}
323
324// A DirEntry extends the [fs.DirEntry] interface to add a Stat() method
325// that returns the result of calling [os.Stat] on the underlying file.
326// The results of Info() and Stat() are cached.
327//
328// The [fs.DirEntry] argument passed to the [fs.WalkDirFunc] by [Walk] is
329// always a DirEntry.
330type DirEntry interface {
331 fs.DirEntry
332
333 // Stat returns the fs.FileInfo for the file or subdirectory described
334 // by the entry. The returned FileInfo may be from the time of the
335 // original directory read or from the time of the call to os.Stat.
336 // If the entry denotes a symbolic link, Stat reports the information
337 // about the target itself, not the link.
338 Stat() (fs.FileInfo, error)
339
340 // Depth returns the depth at which this entry was generated relative to the
341 // root being walked.
342 Depth() int
343}
344
345// Walk is a faster implementation of [filepath.WalkDir] that walks the file
346// tree rooted at root in parallel, calling walkFn for each file or directory
347// in the tree, including root.
348//
349// All errors that arise visiting files and directories are filtered by walkFn
350// see the [fs.WalkDirFunc] documentation for details.
351// The [IgnorePermissionErrors] adapter is provided to handle to common case of
352// ignoring [fs.ErrPermission] errors.
353//
354// By default files are walked in directory order, which makes the output
355// non-deterministic. The Sort [Config] option can be used to control the order
356// in which directory entries are visited, but since we walk the file tree in
357// parallel the output is still non-deterministic (it's just slightly more
358// sorted).
359//
360// When a symbolic link is encountered, by default Walk will not follow it
361// unless walkFn returns [ErrTraverseLink] or the Follow [Config] setting is
362// true. See below for a more detailed explanation.
363//
364// Walk calls walkFn with paths that use the separator character appropriate
365// for the operating system unless the ToSlash [Config] setting is true which
366// will cause all paths to be joined with a forward slash.
367//
368// If walkFn returns the [SkipDir] sentinel error, the directory is skipped.
369// If walkFn returns the [ErrSkipFiles] sentinel error, the callback will not
370// be called for any other files in the current directory. Unlike,
371// [filepath.Walk] and [filepath.WalkDir] the [fs.SkipAll] sentinel error is
372// not respected.
373//
374// Unlike [filepath.WalkDir]:
375//
376// - Multiple goroutines stat the filesystem concurrently. The provided
377// walkFn must be safe for concurrent use.
378//
379// - The order that directories are visited is non-deterministic.
380//
381// - File stat calls must be done by the user and should be done via
382// the [DirEntry] argument to walkFn. The [DirEntry] caches the result
383// of both Info() and Stat(). The Stat() method is a fastwalk specific
384// extension and can be called by casting the [fs.DirEntry] to a
385// [fastwalk.DirEntry] or via the [StatDirEntry] helper. The [fs.DirEntry]
386// argument to walkFn will always be convertible to a [fastwalk.DirEntry].
387//
388// - The [fs.DirEntry] argument is always a [fastwalk.DirEntry], which has
389// a Stat() method that returns the result of calling [os.Stat] on the
390// file. The result of Stat() and Info() are cached. The [StatDirEntry]
391// helper can be used to call Stat() on the returned [fastwalk.DirEntry].
392//
393// - Additionally, the [fs.DirEntry] argument (which has type [fastwalk.DirEntry]),
394// has a Depth() method that returns the depth at which the entry was generated
395// relative to the root being walked. The [DirEntryDepth] helper function
396// can be used to call Depth() on the [fs.DirEntry] argument.
397//
398// - Walk can follow symlinks in two ways: the fist, and simplest, is to
399// set Follow [Config] option to true - this will cause Walk to follow
400// symlinks and detect/ignore any symlink loops; the second, is for walkFn
401// to return the sentinel [ErrTraverseLink] error.
402// When using [ErrTraverseLink] to follow symlinks it is walkFn's
403// responsibility to prevent Walk from going into symlink cycles.
404// By default Walk does not follow symbolic links.
405//
406// - When walking a directory, walkFn will be called for each non-directory
407// entry and directories will be enqueued and visited at a later time or
408// by another goroutine.
409//
410// - The [fs.SkipAll] sentinel error is not respected and not ignored. If the
411// WalkDirFunc returns SkipAll then Walk will exit with the error SkipAll.
412func Walk(conf *Config, root string, walkFn fs.WalkDirFunc) error {
413 fi, err := os.Stat(root)
414 if err != nil {
415 return err
416 }
417 if conf == nil {
418 dupe := DefaultConfig
419 conf = &dupe
420 }
421 if conf.ToSlash {
422 root = filepath.ToSlash(root)
423 }
424
425 // Make sure to wait for all workers to finish, otherwise
426 // walkFn could still be called after returning. This Wait call
427 // runs after close(e.donec) below.
428 var wg sync.WaitGroup
429 defer wg.Wait()
430
431 numWorkers := conf.NumWorkers
432 if numWorkers <= 0 {
433 numWorkers = DefaultNumWorkers()
434 }
435
436 w := &walker{
437 fn: walkFn,
438 // TODO: Increase the size of enqueuec so that we don't stall
439 // while processing a directory. Increasing the size of workc
440 // doesn't help as much (needs more testing).
441 enqueuec: make(chan walkItem, numWorkers), // buffered for performance
442 workc: make(chan walkItem, numWorkers), // buffered for performance
443 donec: make(chan struct{}),
444
445 // buffered for correctness & not leaking goroutines:
446 resc: make(chan error, numWorkers),
447
448 // TODO: we should just pass the Config
449 maxDepth: conf.MaxDepth,
450 follow: conf.Follow,
451 toSlash: conf.ToSlash,
452 sortMode: conf.Sort,
453 }
454 if w.follow {
455 w.ignoredDirs = append(w.ignoredDirs, fi)
456 }
457
458 defer close(w.donec)
459
460 for i := 0; i < numWorkers; i++ {
461 wg.Add(1)
462 go w.doWork(&wg)
463 }
464
465 root = cleanRootPath(root)
466 // NOTE: in BenchmarkFastWalk the size of todo averages around
467 // 170 and can be in the ~250 range at max.
468 todo := []walkItem{{dir: root, info: fileInfoToDirEntry(filepath.Dir(root), fi)}}
469 out := 0
470 for {
471 workc := w.workc
472 var workItem walkItem
473 if len(todo) == 0 {
474 workc = nil
475 } else {
476 workItem = todo[len(todo)-1]
477 }
478 select {
479 case workc <- workItem:
480 todo = todo[:len(todo)-1]
481 out++
482 case it := <-w.enqueuec:
483 // TODO: consider appending to todo directly and using a
484 // mutext this might help with contention around select
485 todo = append(todo, it)
486 case err := <-w.resc:
487 out--
488 if err != nil {
489 return err
490 }
491 if out == 0 && len(todo) == 0 {
492 // It's safe to quit here, as long as the buffered
493 // enqueue channel isn't also readable, which might
494 // happen if the worker sends both another unit of
495 // work and its result before the other select was
496 // scheduled and both w.resc and w.enqueuec were
497 // readable.
498 select {
499 case it := <-w.enqueuec:
500 todo = append(todo, it)
501 default:
502 return nil
503 }
504 }
505 }
506 }
507}
508
509// doWork reads directories as instructed (via workc) and runs the
510// user's callback function.
511func (w *walker) doWork(wg *sync.WaitGroup) {
512 defer wg.Done()
513 for {
514 select {
515 case <-w.donec:
516 return
517 case it := <-w.workc:
518 select {
519 case <-w.donec:
520 return
521 case w.resc <- w.walk(it.dir, it.info, !it.callbackDone):
522 }
523 }
524 }
525}
526
527type walker struct {
528 fn fs.WalkDirFunc
529
530 donec chan struct{} // closed on fastWalk's return
531 workc chan walkItem // to workers
532 enqueuec chan walkItem // from workers
533 resc chan error // from workers
534
535 ignoredDirs []fs.FileInfo
536 maxDepth int
537 follow bool
538 toSlash bool
539 sortMode SortMode
540}
541
542type walkItem struct {
543 dir string
544 info DirEntry
545 callbackDone bool // callback already called; don't do it again
546}
547
548func (w *walker) enqueue(it walkItem) {
549 select {
550 case w.enqueuec <- it:
551 case <-w.donec:
552 }
553}
554
555func (w *walker) shouldSkipDir(fi fs.FileInfo) bool {
556 for _, ignored := range w.ignoredDirs {
557 if os.SameFile(ignored, fi) {
558 return true
559 }
560 }
561 return false
562}
563
564func (w *walker) shouldTraverse(path string, de DirEntry) bool {
565 ts, err := de.Stat()
566 if err != nil {
567 return false
568 }
569 if !ts.IsDir() {
570 return false
571 }
572 if w.shouldSkipDir(ts) {
573 return false
574 }
575 for {
576 parent := filepath.Dir(path)
577 if parent == path {
578 return true
579 }
580 parentInfo, err := os.Stat(parent)
581 if err != nil {
582 return false
583 }
584 if os.SameFile(ts, parentInfo) {
585 return false
586 }
587 path = parent
588 }
589}
590
591func (w *walker) joinPaths(dir, base string) string {
592 // Handle the case where the root path argument to Walk is "/"
593 // without this the returned path is prefixed with "//".
594 if os.PathSeparator == '/' {
595 if len(dir) != 0 && dir[len(dir)-1] == '/' {
596 return dir + base
597 }
598 return dir + "/" + base
599 }
600 if len(dir) != 0 && os.IsPathSeparator(dir[len(dir)-1]) {
601 return dir + base
602 }
603 if w.toSlash {
604 return dir + "/" + base
605 }
606 return dir + string(os.PathSeparator) + base
607}
608
609func (w *walker) onDirEnt(dirName, baseName string, de DirEntry) error {
610 joined := w.joinPaths(dirName, baseName)
611 typ := de.Type()
612 if typ == os.ModeDir {
613 w.enqueue(walkItem{dir: joined, info: de})
614 return nil
615 }
616
617 err := w.fn(joined, de, nil)
618 if typ == os.ModeSymlink {
619 if err == ErrTraverseLink {
620 if !w.follow {
621 // Set callbackDone so we don't call it twice for both the
622 // symlink-as-symlink and the symlink-as-directory later:
623 w.enqueue(walkItem{dir: joined, info: de, callbackDone: true})
624 return nil
625 }
626 err = nil // Ignore ErrTraverseLink when Follow is true.
627 }
628 if err == filepath.SkipDir {
629 // Permit SkipDir on symlinks too.
630 return nil
631 }
632 if err == nil && w.follow && w.shouldTraverse(joined, de) {
633 // Traverse symlink
634 w.enqueue(walkItem{dir: joined, info: de, callbackDone: true})
635 }
636 }
637 return err
638}
639
640func (w *walker) walk(root string, info DirEntry, runUserCallback bool) error {
641 if runUserCallback {
642 err := w.fn(root, info, nil)
643 if err == filepath.SkipDir {
644 return nil
645 }
646 if err != nil {
647 return err
648 }
649 }
650
651 depth := info.Depth()
652 if w.maxDepth > 0 && depth >= w.maxDepth {
653 return nil
654 }
655 err := w.readDir(root, depth+1)
656 if err != nil {
657 // Second call, to report ReadDir error.
658 return w.fn(root, info, err)
659 }
660 return nil
661}
662
663// cleanRootPath returns the root path trimmed of extraneous trailing slashes.
664// This is a no-op on Windows.
665func cleanRootPath(root string) string {
666 if runtime.GOOS == "windows" || len(filepath.VolumeName(root)) != 0 {
667 // Windows paths or any path with a volume name (which AFAIK should
668 // only be Windows) are a bit too complicated to clean.
669 return root
670 }
671 if len(filepath.VolumeName(root)) != 0 {
672 return root
673 }
674 for i := len(root) - 1; i >= 0; i-- {
675 if !os.IsPathSeparator(root[i]) {
676 return root[:i+1]
677 }
678 }
679 if root != "" {
680 return root[0:1] // root is all path separators ("//")
681 }
682 return root
683}
684
685// Avoid the dependency on strconv since it pulls in a large number of other
686// dependencies which bloats the size of this package.
687func itoa(val uint64) string {
688 buf := make([]byte, 20)
689 i := len(buf) - 1
690 for val >= 10 {
691 buf[i] = byte(val%10 + '0')
692 i--
693 val /= 10
694 }
695 buf[i] = byte(val + '0')
696 return string(buf[i:])
697}