sdk/go/arvados/fs_base.go

   1 // Copyright (C) The Arvados Authors. All rights reserved.
   2 //
   3 // SPDX-License-Identifier: Apache-2.0
   4
   5 package arvados
   6
   7 import (
   8         "errors"
   9         "fmt"
  10         "io"
  11         "io/fs"
  12         "log"
  13         "net/http"
  14         "os"
  15         "path"
  16         "strings"
  17         "sync"
  18         "time"
  19 )
  20
  21 var (
  22         ErrReadOnlyFile      = errors.New("read-only file")
  23         ErrNegativeOffset    = errors.New("cannot seek to negative offset")
  24         ErrFileExists        = errors.New("file exists")
  25         ErrInvalidOperation  = errors.New("invalid operation")
  26         ErrInvalidArgument   = errors.New("invalid argument")
  27         ErrDirectoryNotEmpty = errors.New("directory not empty")
  28         ErrWriteOnlyMode     = errors.New("file is O_WRONLY")
  29         ErrSyncNotSupported  = errors.New("O_SYNC flag is not supported")
  30         ErrIsDirectory       = errors.New("cannot rename file to overwrite existing directory")
  31         ErrNotADirectory     = errors.New("not a directory")
  32         ErrPermission        = os.ErrPermission
  33         DebugLocksPanicMode  = false
  34 )
  35
  36 type syncer interface {
  37         Sync() error
  38 }
  39
  40 func debugPanicIfNotLocked(l sync.Locker, writing bool) {
  41         if !DebugLocksPanicMode {
  42                 return
  43         }
  44         race := false
  45         if rl, ok := l.(interface {
  46                 RLock()
  47                 RUnlock()
  48         }); ok && writing {
  49                 go func() {
  50                         // Fail if we can grab the read lock during an
  51                         // operation that purportedly has write lock.
  52                         rl.RLock()
  53                         race = true
  54                         rl.RUnlock()
  55                 }()
  56         } else {
  57                 go func() {
  58                         l.Lock()
  59                         race = true
  60                         l.Unlock()
  61                 }()
  62         }
  63         time.Sleep(100)
  64         if race {
  65                 panic("bug: caller-must-have-lock func called, but nobody has lock")
  66         }
  67 }
  68
  69 // A File is an *os.File-like interface for reading and writing files
  70 // in a FileSystem.
  71 type File interface {
  72         io.Reader
  73         io.Writer
  74         io.Closer
  75         io.Seeker
  76         Size() int64
  77         Readdir(int) ([]os.FileInfo, error)
  78         Stat() (os.FileInfo, error)
  79         Truncate(int64) error
  80         Sync() error
  81         // Create a snapshot of a file or directory tree, which can
  82         // then be spliced onto a different path or a different
  83         // collection.
  84         Snapshot() (*Subtree, error)
  85         // Replace this file or directory with the given snapshot.
  86         // The target must be inside a collection: Splice returns an
  87         // error if the File is a virtual file or directory like
  88         // by_id, a project directory, .arvados#collection,
  89         // etc. Splice can replace directories with regular files and
  90         // vice versa, except it cannot replace the root directory of
  91         // a collection with a regular file.
  92         Splice(snapshot *Subtree) error
  93 }
  94
  95 // A Subtree is a detached part of a filesystem tree that can be
  96 // spliced into a filesystem via (File)Splice().
  97 type Subtree struct {
  98         inode inode
  99 }
 100
 101 // A FileSystem is an http.Filesystem plus Stat() and support for
 102 // opening writable files. All methods are safe to call from multiple
 103 // goroutines.
 104 type FileSystem interface {
 105         http.FileSystem
 106         fsBackend
 107
 108         rootnode() inode
 109
 110         // filesystem-wide lock: used by Rename() to prevent deadlock
 111         // while locking multiple inodes.
 112         locker() sync.Locker
 113
 114         // throttle for limiting concurrent background writers
 115         throttle() *throttle
 116
 117         // create a new node with nil parent.
 118         newNode(name string, perm os.FileMode, modTime time.Time) (node inode, err error)
 119
 120         // analogous to os.Stat()
 121         Stat(name string) (os.FileInfo, error)
 122
 123         // analogous to os.Create(): create/truncate a file and open it O_RDWR.
 124         Create(name string) (File, error)
 125
 126         // Like os.OpenFile(): create or open a file or directory.
 127         //
 128         // If flag&os.O_EXCL==0, it opens an existing file or
 129         // directory if one exists. If flag&os.O_CREATE!=0, it creates
 130         // a new empty file or directory if one does not already
 131         // exist.
 132         //
 133         // When creating a new item, perm&os.ModeDir determines
 134         // whether it is a file or a directory.
 135         //
 136         // A file can be opened multiple times and used concurrently
 137         // from multiple goroutines. However, each File object should
 138         // be used by only one goroutine at a time.
 139         OpenFile(name string, flag int, perm os.FileMode) (File, error)
 140
 141         Mkdir(name string, perm os.FileMode) error
 142         Remove(name string) error
 143         RemoveAll(name string) error
 144         Rename(oldname, newname string) error
 145
 146         // Write buffered data from memory to storage, returning when
 147         // all updates have been saved to persistent storage.
 148         Sync() error
 149
 150         // Write buffered data from memory to storage, but don't wait
 151         // for all writes to finish before returning. If shortBlocks
 152         // is true, flush everything; otherwise, if there's less than
 153         // a full block of buffered data at the end of a stream, leave
 154         // it buffered in memory in case more data can be appended. If
 155         // path is "", flush all dirs/streams; otherwise, flush only
 156         // the specified dir/stream.
 157         Flush(path string, shortBlocks bool) error
 158
 159         // Estimate current memory usage.
 160         MemorySize() int64
 161 }
 162
 163 type fsFS struct {
 164         FileSystem
 165 }
 166
 167 // FS returns an fs.FS interface to the given FileSystem, to enable
 168 // the use of fs.WalkDir, etc.
 169 func FS(fs FileSystem) fs.FS { return fsFS{fs} }
 170 func (fs fsFS) Open(path string) (fs.File, error) {
 171         f, err := fs.FileSystem.Open(path)
 172         return f, err
 173 }
 174
 175 type inode interface {
 176         SetParent(parent inode, name string)
 177         Parent() inode
 178         FS() FileSystem
 179         Read([]byte, filenodePtr) (int, filenodePtr, error)
 180         Write([]byte, filenodePtr) (int, filenodePtr, error)
 181         Truncate(int64) error
 182         IsDir() bool
 183         Readdir() ([]os.FileInfo, error)
 184         Size() int64
 185         FileInfo() os.FileInfo
 186         // Create a snapshot of this node and its descendants.
 187         Snapshot() (inode, error)
 188         // Replace this node with a copy of the provided snapshot.
 189         // Caller may provide the same snapshot to multiple Splice
 190         // calls, but must not modify the snapshot concurrently.
 191         Splice(inode) error
 192
 193         // Child() performs lookups and updates of named child nodes.
 194         //
 195         // (The term "child" here is used strictly. This means name is
 196         // not "." or "..", and name does not contain "/".)
 197         //
 198         // If replace is non-nil, Child calls replace(x) where x is
 199         // the current child inode with the given name. If possible,
 200         // the child inode is replaced with the one returned by
 201         // replace().
 202         //
 203         // If replace(x) returns an inode (besides x or nil) that is
 204         // subsequently returned by Child(), then Child()'s caller
 205         // must ensure the new child's name and parent are set/updated
 206         // to Child()'s name argument and its receiver respectively.
 207         // This is not necessarily done before replace(x) returns, but
 208         // it must be done before Child()'s caller releases the
 209         // parent's lock.
 210         //
 211         // Nil represents "no child". replace(nil) signifies that no
 212         // child with this name exists yet. If replace() returns nil,
 213         // the existing child should be deleted if possible.
 214         //
 215         // An implementation of Child() is permitted to ignore
 216         // replace() or its return value. For example, a regular file
 217         // inode does not have children, so Child() always returns
 218         // nil.
 219         //
 220         // Child() returns the child, if any, with the given name: if
 221         // a child was added or changed, the new child is returned.
 222         //
 223         // Caller must have lock (or rlock if replace is nil).
 224         Child(name string, replace func(inode) (inode, error)) (inode, error)
 225
 226         sync.Locker
 227         RLock()
 228         RUnlock()
 229         MemorySize() int64
 230 }
 231
 232 type fileinfo struct {
 233         name    string
 234         mode    os.FileMode
 235         size    int64
 236         modTime time.Time
 237 }
 238
 239 // Name implements os.FileInfo.
 240 func (fi fileinfo) Name() string {
 241         return fi.name
 242 }
 243
 244 // ModTime implements os.FileInfo.
 245 func (fi fileinfo) ModTime() time.Time {
 246         return fi.modTime
 247 }
 248
 249 // Mode implements os.FileInfo.
 250 func (fi fileinfo) Mode() os.FileMode {
 251         return fi.mode
 252 }
 253
 254 // IsDir implements os.FileInfo.
 255 func (fi fileinfo) IsDir() bool {
 256         return fi.mode&os.ModeDir != 0
 257 }
 258
 259 // Size implements os.FileInfo.
 260 func (fi fileinfo) Size() int64 {
 261         return fi.size
 262 }
 263
 264 // Sys implements os.FileInfo.
 265 func (fi fileinfo) Sys() interface{} {
 266         return nil
 267 }
 268
 269 type nullnode struct{}
 270
 271 func (*nullnode) Mkdir(string, os.FileMode) error {
 272         return ErrInvalidOperation
 273 }
 274
 275 func (*nullnode) Read([]byte, filenodePtr) (int, filenodePtr, error) {
 276         return 0, filenodePtr{}, ErrInvalidOperation
 277 }
 278
 279 func (*nullnode) Write([]byte, filenodePtr) (int, filenodePtr, error) {
 280         return 0, filenodePtr{}, ErrInvalidOperation
 281 }
 282
 283 func (*nullnode) Truncate(int64) error {
 284         return ErrInvalidOperation
 285 }
 286
 287 func (*nullnode) FileInfo() os.FileInfo {
 288         return fileinfo{}
 289 }
 290
 291 func (*nullnode) IsDir() bool {
 292         return false
 293 }
 294
 295 func (*nullnode) Readdir() ([]os.FileInfo, error) {
 296         return nil, ErrInvalidOperation
 297 }
 298
 299 func (*nullnode) Child(name string, replace func(inode) (inode, error)) (inode, error) {
 300         return nil, ErrNotADirectory
 301 }
 302
 303 func (*nullnode) MemorySize() int64 {
 304         // Types that embed nullnode should report their own size, but
 305         // if they don't, we at least report a non-zero size to ensure
 306         // a large tree doesn't get reported as 0 bytes.
 307         return 64
 308 }
 309
 310 func (*nullnode) Snapshot() (inode, error) {
 311         return nil, ErrInvalidOperation
 312 }
 313
 314 func (*nullnode) Splice(inode) error {
 315         return ErrInvalidOperation
 316 }
 317
 318 type treenode struct {
 319         fs       FileSystem
 320         parent   inode
 321         inodes   map[string]inode
 322         fileinfo fileinfo
 323         sync.RWMutex
 324         nullnode
 325 }
 326
 327 func (n *treenode) FS() FileSystem {
 328         return n.fs
 329 }
 330
 331 func (n *treenode) SetParent(p inode, name string) {
 332         n.Lock()
 333         defer n.Unlock()
 334         n.parent = p
 335         n.fileinfo.name = name
 336 }
 337
 338 func (n *treenode) Parent() inode {
 339         n.RLock()
 340         defer n.RUnlock()
 341         return n.parent
 342 }
 343
 344 func (n *treenode) IsDir() bool {
 345         return true
 346 }
 347
 348 func (n *treenode) Child(name string, replace func(inode) (inode, error)) (child inode, err error) {
 349         debugPanicIfNotLocked(n, false)
 350         child = n.inodes[name]
 351         if name == "" || name == "." || name == ".." {
 352                 err = ErrInvalidArgument
 353                 return
 354         }
 355         if replace == nil {
 356                 return
 357         }
 358         newchild, err := replace(child)
 359         if err != nil {
 360                 return
 361         }
 362         if newchild == nil {
 363                 debugPanicIfNotLocked(n, true)
 364                 delete(n.inodes, name)
 365         } else if newchild != child {
 366                 debugPanicIfNotLocked(n, true)
 367                 n.inodes[name] = newchild
 368                 n.fileinfo.modTime = time.Now()
 369                 child = newchild
 370         }
 371         return
 372 }
 373
 374 func (n *treenode) Size() int64 {
 375         return n.FileInfo().Size()
 376 }
 377
 378 func (n *treenode) FileInfo() os.FileInfo {
 379         n.Lock()
 380         defer n.Unlock()
 381         n.fileinfo.size = int64(len(n.inodes))
 382         return n.fileinfo
 383 }
 384
 385 func (n *treenode) Readdir() (fi []os.FileInfo, err error) {
 386         n.RLock()
 387         defer n.RUnlock()
 388         fi = make([]os.FileInfo, 0, len(n.inodes))
 389         for _, inode := range n.inodes {
 390                 fi = append(fi, inode.FileInfo())
 391         }
 392         return
 393 }
 394
 395 func (n *treenode) Sync() error {
 396         n.RLock()
 397         defer n.RUnlock()
 398         for _, inode := range n.inodes {
 399                 syncer, ok := inode.(syncer)
 400                 if !ok {
 401                         return ErrInvalidOperation
 402                 }
 403                 err := syncer.Sync()
 404                 if err != nil {
 405                         return err
 406                 }
 407         }
 408         return nil
 409 }
 410
 411 func (n *treenode) MemorySize() (size int64) {
 412         n.RLock()
 413         defer n.RUnlock()
 414         debugPanicIfNotLocked(n, false)
 415         for _, inode := range n.inodes {
 416                 size += inode.MemorySize()
 417         }
 418         return
 419 }
 420
 421 type fileSystem struct {
 422         root inode
 423         fsBackend
 424         mutex sync.Mutex
 425         thr   *throttle
 426 }
 427
 428 func (fs *fileSystem) rootnode() inode {
 429         return fs.root
 430 }
 431
 432 func (fs *fileSystem) throttle() *throttle {
 433         return fs.thr
 434 }
 435
 436 func (fs *fileSystem) locker() sync.Locker {
 437         return &fs.mutex
 438 }
 439
 440 // OpenFile is analogous to os.OpenFile().
 441 func (fs *fileSystem) OpenFile(name string, flag int, perm os.FileMode) (File, error) {
 442         return fs.openFile(name, flag, perm)
 443 }
 444
 445 func (fs *fileSystem) openFile(name string, flag int, perm os.FileMode) (*filehandle, error) {
 446         if flag&os.O_SYNC != 0 {
 447                 return nil, ErrSyncNotSupported
 448         }
 449         dirname, name := path.Split(name)
 450         parent, err := rlookup(fs.root, dirname)
 451         if err != nil {
 452                 return nil, err
 453         }
 454         var readable, writable bool
 455         switch flag & (os.O_RDWR | os.O_RDONLY | os.O_WRONLY) {
 456         case os.O_RDWR:
 457                 readable = true
 458                 writable = true
 459         case os.O_RDONLY:
 460                 readable = true
 461         case os.O_WRONLY:
 462                 writable = true
 463         default:
 464                 return nil, fmt.Errorf("invalid flags 0x%x", flag)
 465         }
 466         if parent.IsDir() {
 467                 // A directory can be opened via "foo/", "foo/.", or
 468                 // "foo/..".
 469                 switch name {
 470                 case ".", "":
 471                         return &filehandle{inode: parent, readable: readable, writable: writable}, nil
 472                 case "..":
 473                         return &filehandle{inode: parent.Parent(), readable: readable, writable: writable}, nil
 474                 }
 475         }
 476         createMode := flag&os.O_CREATE != 0
 477         // We always need to take Lock() here, not just RLock(). Even
 478         // if we know we won't be creating a file, parent might be a
 479         // lookupnode, which sometimes populates its inodes map during
 480         // a Child() call.
 481         parent.Lock()
 482         defer parent.Unlock()
 483         n, err := parent.Child(name, nil)
 484         if err != nil {
 485                 return nil, err
 486         } else if n == nil {
 487                 if !createMode {
 488                         return nil, os.ErrNotExist
 489                 }
 490                 n, err = parent.Child(name, func(inode) (repl inode, err error) {
 491                         repl, err = parent.FS().newNode(name, perm|0755, time.Now())
 492                         if err != nil {
 493                                 return
 494                         }
 495                         repl.SetParent(parent, name)
 496                         return
 497                 })
 498                 if err != nil {
 499                         return nil, err
 500                 } else if n == nil {
 501                         // Parent rejected new child, but returned no error
 502                         return nil, ErrInvalidArgument
 503                 }
 504         } else if flag&os.O_EXCL != 0 {
 505                 return nil, ErrFileExists
 506         } else if flag&os.O_TRUNC != 0 {
 507                 if !writable {
 508                         return nil, fmt.Errorf("invalid flag O_TRUNC in read-only mode")
 509                 } else if n.IsDir() {
 510                         return nil, fmt.Errorf("invalid flag O_TRUNC when opening directory")
 511                 } else if err := n.Truncate(0); err != nil {
 512                         return nil, err
 513                 }
 514         }
 515         return &filehandle{
 516                 inode:    n,
 517                 append:   flag&os.O_APPEND != 0,
 518                 readable: readable,
 519                 writable: writable,
 520         }, nil
 521 }
 522
 523 func (fs *fileSystem) Open(name string) (http.File, error) {
 524         return fs.OpenFile(name, os.O_RDONLY, 0)
 525 }
 526
 527 func (fs *fileSystem) Create(name string) (File, error) {
 528         return fs.OpenFile(name, os.O_CREATE|os.O_RDWR|os.O_TRUNC, 0)
 529 }
 530
 531 func (fs *fileSystem) Mkdir(name string, perm os.FileMode) error {
 532         dirname, name := path.Split(name)
 533         n, err := rlookup(fs.root, dirname)
 534         if err != nil {
 535                 return err
 536         }
 537         n.Lock()
 538         defer n.Unlock()
 539         if child, err := n.Child(name, nil); err != nil {
 540                 return err
 541         } else if child != nil {
 542                 return os.ErrExist
 543         }
 544
 545         _, err = n.Child(name, func(inode) (repl inode, err error) {
 546                 repl, err = n.FS().newNode(name, perm|os.ModeDir, time.Now())
 547                 if err != nil {
 548                         return
 549                 }
 550                 repl.SetParent(n, name)
 551                 return
 552         })
 553         return err
 554 }
 555
 556 func (fs *fileSystem) Stat(name string) (os.FileInfo, error) {
 557         node, err := rlookup(fs.root, name)
 558         if err != nil {
 559                 return nil, err
 560         }
 561         return node.FileInfo(), nil
 562 }
 563
 564 func (fs *fileSystem) Rename(oldname, newname string) error {
 565         olddir, oldname := path.Split(oldname)
 566         if oldname == "" || oldname == "." || oldname == ".." {
 567                 return ErrInvalidArgument
 568         }
 569         olddirf, err := fs.openFile(olddir+".", os.O_RDONLY, 0)
 570         if err != nil {
 571                 return fmt.Errorf("%q: %s", olddir, err)
 572         }
 573         defer olddirf.Close()
 574
 575         newdir, newname := path.Split(newname)
 576         if newname == "." || newname == ".." {
 577                 return ErrInvalidArgument
 578         } else if newname == "" {
 579                 // Rename("a/b", "c/") means Rename("a/b", "c/b")
 580                 newname = oldname
 581         }
 582         newdirf, err := fs.openFile(newdir+".", os.O_RDONLY, 0)
 583         if err != nil {
 584                 return fmt.Errorf("%q: %s", newdir, err)
 585         }
 586         defer newdirf.Close()
 587
 588         // TODO: If the nearest common ancestor ("nca") of olddirf and
 589         // newdirf is on a different filesystem than fs, we should
 590         // call nca.FS().Rename() instead of proceeding. Until then
 591         // it's awkward for filesystems to implement their own Rename
 592         // methods effectively: the only one that runs is the one on
 593         // the root FileSystem exposed to the caller (webdav, fuse,
 594         // etc).
 595
 596         // When acquiring locks on multiple inodes, avoid deadlock by
 597         // locking the entire containing filesystem first.
 598         cfs := olddirf.inode.FS()
 599         cfs.locker().Lock()
 600         defer cfs.locker().Unlock()
 601
 602         if cfs != newdirf.inode.FS() {
 603                 // Moving inodes across filesystems is not (yet)
 604                 // supported. Locking inodes from different
 605                 // filesystems could deadlock, so we must error out
 606                 // now.
 607                 return ErrInvalidOperation
 608         }
 609
 610         // To ensure we can test reliably whether we're about to move
 611         // a directory into itself, lock all potential common
 612         // ancestors of olddir and newdir.
 613         needLock := []sync.Locker{}
 614         for _, node := range []inode{olddirf.inode, newdirf.inode} {
 615                 needLock = append(needLock, node)
 616                 for node.Parent() != node && node.Parent().FS() == node.FS() {
 617                         node = node.Parent()
 618                         needLock = append(needLock, node)
 619                 }
 620         }
 621         locked := map[sync.Locker]bool{}
 622         for i := len(needLock) - 1; i >= 0; i-- {
 623                 if n := needLock[i]; !locked[n] {
 624                         n.Lock()
 625                         defer n.Unlock()
 626                         locked[n] = true
 627                 }
 628         }
 629
 630         _, err = olddirf.inode.Child(oldname, func(oldinode inode) (inode, error) {
 631                 if oldinode == nil {
 632                         return oldinode, os.ErrNotExist
 633                 }
 634                 if locked[oldinode] {
 635                         // oldinode cannot become a descendant of itself.
 636                         return oldinode, ErrInvalidArgument
 637                 }
 638                 if oldinode.FS() != cfs && newdirf.inode != olddirf.inode {
 639                         // moving a mount point to a different parent
 640                         // is not (yet) supported.
 641                         return oldinode, ErrInvalidArgument
 642                 }
 643                 accepted, err := newdirf.inode.Child(newname, func(existing inode) (inode, error) {
 644                         if existing != nil && existing.IsDir() {
 645                                 return existing, ErrIsDirectory
 646                         }
 647                         return oldinode, nil
 648                 })
 649                 if err != nil {
 650                         // Leave oldinode in olddir.
 651                         return oldinode, err
 652                 }
 653                 accepted.SetParent(newdirf.inode, newname)
 654                 return nil, nil
 655         })
 656         return err
 657 }
 658
 659 func (fs *fileSystem) Remove(name string) error {
 660         return fs.remove(strings.TrimRight(name, "/"), false)
 661 }
 662
 663 func (fs *fileSystem) RemoveAll(name string) error {
 664         err := fs.remove(strings.TrimRight(name, "/"), true)
 665         if os.IsNotExist(err) {
 666                 // "If the path does not exist, RemoveAll returns
 667                 // nil." (see "os" pkg)
 668                 err = nil
 669         }
 670         return err
 671 }
 672
 673 func (fs *fileSystem) remove(name string, recursive bool) error {
 674         dirname, name := path.Split(name)
 675         if name == "" || name == "." || name == ".." {
 676                 return ErrInvalidArgument
 677         }
 678         dir, err := rlookup(fs.root, dirname)
 679         if err != nil {
 680                 return err
 681         }
 682         dir.Lock()
 683         defer dir.Unlock()
 684         _, err = dir.Child(name, func(node inode) (inode, error) {
 685                 if node == nil {
 686                         return nil, os.ErrNotExist
 687                 }
 688                 if !recursive && node.IsDir() && node.Size() > 0 {
 689                         return node, ErrDirectoryNotEmpty
 690                 }
 691                 return nil, nil
 692         })
 693         return err
 694 }
 695
 696 func (fs *fileSystem) Sync() error {
 697         if syncer, ok := fs.root.(syncer); ok {
 698                 return syncer.Sync()
 699         }
 700         return ErrInvalidOperation
 701 }
 702
 703 func (fs *fileSystem) Flush(string, bool) error {
 704         log.Printf("TODO: flush fileSystem")
 705         return ErrInvalidOperation
 706 }
 707
 708 func (fs *fileSystem) MemorySize() int64 {
 709         return fs.root.MemorySize()
 710 }
 711
 712 // rlookup (recursive lookup) returns the inode for the file/directory
 713 // with the given name (which may contain "/" separators). If no such
 714 // file/directory exists, the returned node is nil.
 715 func rlookup(start inode, path string) (node inode, err error) {
 716         node = start
 717         for _, name := range strings.Split(path, "/") {
 718                 if node.IsDir() {
 719                         if name == "." || name == "" {
 720                                 continue
 721                         }
 722                         if name == ".." {
 723                                 node = node.Parent()
 724                                 continue
 725                         }
 726                 }
 727                 node, err = func() (inode, error) {
 728                         node.Lock()
 729                         defer node.Unlock()
 730                         return node.Child(name, nil)
 731                 }()
 732                 if node == nil || err != nil {
 733                         break
 734                 }
 735         }
 736         if node == nil && err == nil {
 737                 err = os.ErrNotExist
 738         }
 739         return
 740 }
 741
 742 func permittedName(name string) bool {
 743         return name != "" && name != "." && name != ".." && !strings.Contains(name, "/")
 744 }
 745
 746 // Snapshot returns a Subtree that's a copy of the given path. It
 747 // returns an error if the path is not inside a collection.
 748 func Snapshot(fs FileSystem, path string) (*Subtree, error) {
 749         f, err := fs.OpenFile(path, os.O_RDONLY, 0)
 750         if err != nil {
 751                 return nil, err
 752         }
 753         defer f.Close()
 754         return f.Snapshot()
 755 }
 756
 757 // Splice inserts newsubtree at the indicated target path.
 758 //
 759 // Splice returns an error if target is not inside a collection.
 760 //
 761 // Splice returns an error if target is the root of a collection and
 762 // newsubtree is a snapshot of a file.
 763 func Splice(fs FileSystem, target string, newsubtree *Subtree) error {
 764         f, err := fs.OpenFile(target, os.O_WRONLY, 0)
 765         if os.IsNotExist(err) {
 766                 f, err = fs.OpenFile(target, os.O_CREATE|os.O_WRONLY, 0700)
 767         }
 768         if err != nil {
 769                 return fmt.Errorf("open %s: %w", target, err)
 770         }
 771         defer f.Close()
 772         return f.Splice(newsubtree)
 773 }