fs.go

// Copyright 2017 Keybase Inc. All rights reserved.
// Use of this source code is governed by a BSD
// license that can be found in the LICENSE file.

package libfs

import (
	"bytes"
	"context"
	"crypto/rand"
	"encoding/base64"
	"fmt"
	"net/http"
	"os"
	"path"
	"strings"
	"sync"
	"time"

	"github.com/keybase/client/go/kbfs/data"
	"github.com/keybase/client/go/kbfs/idutil"
	"github.com/keybase/client/go/kbfs/libkbfs"
	"github.com/keybase/client/go/kbfs/tlfhandle"
	"github.com/keybase/client/go/logger"
	"github.com/keybase/client/go/protocol/keybase1"
	"github.com/pkg/errors"
	billy "gopkg.in/src-d/go-billy.v4"
)

// FSEventType is FS event type.
type FSEventType int

const (
	_ FSEventType = iota
	// FSEventLock indicates Lock method has been called.
	FSEventLock
	// FSEventUnlock indicates Unlock method has been called.
	FSEventUnlock
)

// FSEvent is the type for events sent into the events channel passed into
// NewFS.
type FSEvent struct {
	EventType FSEventType
	File      *File
	Done      <-chan struct{}
}

type fsInner struct {
	config   libkbfs.Config
	root     libkbfs.Node
	rootInfo data.EntryInfo
	h        *tlfhandle.Handle
	subdir   string
	uniqID   string
	log      logger.Logger
	deferLog logger.Logger
	priority keybase1.MDPriority
	empty    bool
	// lockNamespace is the prefix used by any *File generated by this *FS when
	// they need to generate a lockID. By default, we use a canonical unix path
	// of the root of this FS as lock namespace. But one can call
	// SetLockNamespace to set it explicitly, which can be any bytes. When
	// Chroot is called, a slash ('/') followed by the changed subpath are
	// appended to the existing lockNamespace to form the new one. Note that
	// this is a naive append without and path clean.
	lockNamespace []byte

	eventsLock sync.RWMutex // nolint
	events     map[chan<- FSEvent]bool
}

// FS is a wrapper around a KBFS subdirectory that implements the
// billy.Filesystem interface.  It uses forward-slash separated paths.
// It may return errors wrapped with the `github.com/pkg/errors`
// package.
type FS struct {
	// Yes, storing ctx in a struct is a mortal sin, but the
	// billy.Filesystem interface doesn't give us a way to accept ctxs
	// any other way.
	ctx context.Context
	*fsInner
}

var _ billy.Filesystem = (*FS)(nil)

const (
	maxSymlinkLevels = 40 // same as Linux
)

func followSymlink(parentPath, link string) (newPath string, err error) {
	if path.IsAbs(link) {
		return "", errors.Errorf("Can't follow absolute link: %s", link)
	}

	newPath = path.Clean(path.Join(parentPath, link))
	if strings.HasPrefix(newPath, "..") {
		return "", errors.Errorf(
			"Cannot follow symlink out of chroot: %s", newPath)
	}

	return newPath, nil
}

func pathForLogging(
	ctx context.Context, config libkbfs.Config, root libkbfs.Node,
	filename string) string {
	if root == nil || root.Obfuscator() == nil {
		return filename
	}

	if filename == "." {
		return ""
	}

	parts := strings.Split(filename, "/")
	if len(parts) == 0 {
		return ""
	}
	n := root
	ret := ""
	for i := 0; i < len(parts)-1; i++ {
		p := parts[i]
		childName := n.ChildName(p)
		ret = path.Join(ret, childName.String())
		nextNode, _, err := config.KBFSOps().Lookup(ctx, n, childName)
		// If filename is a path that includes a symlink, we can get a nil node
		// here. So just move on if nextNode == nil. In the very rare case of
		// an entry that gets a duplicated obfuscated name within a directory,
		// this could give the wrong answer. But it's not worth it at this time
		// to follow the symlnk for logging.
		if err != nil || nextNode == nil {
			// Just keep using the parent node to obfuscate.
			continue
		}
		n = nextNode
	}
	ret = path.Join(ret, n.ChildName(parts[len(parts)-1]).String())
	return ret
}

// ErrNotADirectory is returned when a non-final path element exists but is not
// a directory.
type ErrNotADirectory struct {
	Name string
}

func (e ErrNotADirectory) Error() string {
	return fmt.Sprintf("%s is not a directory", e.Name)
}

type accessType int

const (
	readwrite accessType = iota
	// readwriteNoCreate creates a read-write file system, but doesn't
	// create the TLF if it doesn't already exists.  Instead, it
	// creates an empty file system.
	readwriteNoCreate
	readonly
)

func newFS(ctx context.Context, config libkbfs.Config,
	tlfHandle *tlfhandle.Handle, branch data.BranchName, subdir string,
	uniqID string, priority keybase1.MDPriority, unwrap bool,
	atype accessType) (*FS, error) {
	rootNodeGetter := config.KBFSOps().GetOrCreateRootNode
	if branch != data.MasterBranch || atype != readwrite {
		rootNodeGetter = config.KBFSOps().GetRootNode
	}

	rootNode, ei, err := rootNodeGetter(ctx, tlfHandle, branch)
	if err != nil {
		return nil, err
	}
	log := config.MakeLogger("")
	if rootNode == nil {
		if len(subdir) > 0 {
			return nil, errors.New("Subdir doesn't exist in empty TLF")
		}
		log.CDebugf(ctx,
			"Returning empty FS for empty TLF=%s", tlfHandle.GetCanonicalName())
		return &FS{
			ctx: ctx,
			fsInner: &fsInner{
				config:   config,
				empty:    true,
				h:        tlfHandle,
				uniqID:   uniqID,
				log:      log,
				deferLog: log.CloneWithAddedDepth(1),
			},
		}, nil
	}

	if unwrap {
		rootNode = rootNode.Unwrap()
	}
	if subdir != "" {
		subdir = path.Clean(subdir)
	}

	if atype == readonly {
		rootNode = libkbfs.ReadonlyNode{Node: rootNode}
	}
	n := rootNode

	// Look up the subdir's root.
	var parts []string
	if len(subdir) > 0 {
		parts = strings.Split(subdir, "/")
	}
	// Loop while we follow symlinks.
outer:
	for {
		for i, p := range parts {
			n, ei, err = config.KBFSOps().Lookup(ctx, n, n.ChildName(p))
			if err != nil {
				return nil, err
			}
			switch ei.Type {
			case data.Dir:
				continue
			case data.Sym:
				parentParts := parts[:i]
				newPath, err := followSymlink(
					path.Join(parentParts...), ei.SymPath)
				if err != nil {
					return nil, err
				}
				newParts := strings.Split(newPath, "/")
				newParts = append(newParts, parts[i+1:]...)
				// Fix subdir so we'll get the correct default lock namespace.
				oldSubdir := subdir
				subdir = path.Join(newParts...)
				config.MakeLogger("").CDebugf(ctx, "Expanding symlink: %s->%s",
					pathForLogging(ctx, config, rootNode, oldSubdir),
					pathForLogging(ctx, config, rootNode, subdir))
				parts = newParts
				n = rootNode
				continue outer
			default:
				return nil, ErrNotADirectory{Name: path.Join(parts[:i+1]...)}
			}
		}
		// Successfully looked up all directories.
		break
	}

	log.CDebugf(ctx, "Made new FS for TLF=%s, subdir=%s",
		tlfHandle.GetCanonicalName(),
		pathForLogging(ctx, config, rootNode, subdir))

	// Use the canonical unix path for default locking namespace, as this needs
	// to be the same across all platforms.
	unixFullPath := path.Join("/keybase", tlfHandle.Type().String(), subdir)

	return &FS{
		ctx: ctx,
		fsInner: &fsInner{
			config:        config,
			root:          n,
			rootInfo:      ei,
			h:             tlfHandle,
			subdir:        subdir,
			uniqID:        uniqID,
			log:           log,
			deferLog:      log.CloneWithAddedDepth(1),
			lockNamespace: []byte(unixFullPath),
			priority:      priority,
			events:        make(map[chan<- FSEvent]bool),
		},
	}, nil
}

// NewUnwrappedFS returns a new FS instance, chroot'd to the given TLF
// and subdir within that TLF, but all the nodes are unwrapped.
// `subdir` must exist, and point to a directory, before this function
// is called.  `uniqID` needs to uniquely identify this instance among
// all users of this TLF globally; for example, a device ID combined
// with a local tempfile name is recommended.
func NewUnwrappedFS(ctx context.Context, config libkbfs.Config,
	tlfHandle *tlfhandle.Handle, branch data.BranchName, subdir string,
	uniqID string, priority keybase1.MDPriority) (*FS, error) {
	return newFS(
		ctx, config, tlfHandle, branch, subdir, uniqID, priority, true,
		readwrite)
}

// NewReadonlyFS returns a new FS instance, chroot'd to the given TLF
// and subdir within that TLF, but all the nodes are read-only.
// `subdir` must exist, and point to a directory, before this function
// is called.  `uniqID` needs to uniquely identify this instance among
// all users of this TLF globally; for example, a device ID combined
// with a local tempfile name is recommended.
//
// Note that this should only be used for subdirectories that will
// never be accessed in read-write mode by this process, because the
// nodes created via this FS might stay read-only in the libkbfs
// NodeCache for a while.
func NewReadonlyFS(ctx context.Context, config libkbfs.Config,
	tlfHandle *tlfhandle.Handle, branch data.BranchName, subdir string,
	uniqID string, priority keybase1.MDPriority) (*FS, error) {
	return newFS(
		ctx, config, tlfHandle, branch, subdir, uniqID, priority, false,
		readonly)
}

// NewFSIfExists returns a new FS instance, chroot'd to the given TLF
// and subdir within that TLF, but only if the TLF already exists.
// `subdir` must exist, and point to a directory, before this function
// is called.  `uniqID` needs to uniquely identify this instance among
// all users of this TLF globally; for example, a device ID combined
// with a local tempfile name is recommended.
//
// If the TLF hasn't been initialized yet, this will return an FS that
// is always empty.  `IsEmpty()` will tell if you this is happening.
// If there's a need to re-check the TLF, a new FS must be
// constructed.
func NewFSIfExists(ctx context.Context, config libkbfs.Config,
	tlfHandle *tlfhandle.Handle, branch data.BranchName, subdir string,
	uniqID string, priority keybase1.MDPriority) (*FS, error) {
	return newFS(
		ctx, config, tlfHandle, branch, subdir, uniqID, priority, false,
		readwriteNoCreate)
}

// NewFS returns a new FS instance, chroot'd to the given TLF and
// subdir within that TLF.  `subdir` must exist, and point to a
// directory, before this function is called.  `uniqID` needs to
// uniquely identify this instance among all users of this TLF
// globally; for example, a device ID combined with a local tempfile
// name is recommended.
func NewFS(ctx context.Context, config libkbfs.Config,
	tlfHandle *tlfhandle.Handle, branch data.BranchName, subdir string,
	uniqID string, priority keybase1.MDPriority) (*FS, error) {
	return newFS(
		ctx, config, tlfHandle, branch, subdir, uniqID, priority, false,
		readwrite)
}

// PathForLogging returns the obfuscated path for the given filename.
func (fs *FS) PathForLogging(filename string) string {
	return pathForLogging(fs.ctx, fs.config, fs.root, filename)
}

// lookupOrCreateEntryNoFollow looks up the entry for a file in a
// given parent node.  If the entry is a symlink, it will return a nil
// Node and a nil error.  If the entry doesn't exist and O_CREATE is
// set in `flag`, it will create the entry as a file.
func (fs *FS) lookupOrCreateEntryNoFollow(
	dir libkbfs.Node, filename data.PathPartString, flag int,
	perm os.FileMode) (libkbfs.Node, data.EntryInfo, error) {
	n, ei, err := fs.config.KBFSOps().Lookup(fs.ctx, dir, filename)
	switch errors.Cause(err).(type) {
	case idutil.NoSuchNameError:
		// The file doesn't exist yet; create if requested
		if flag&os.O_CREATE == 0 {
			return nil, data.EntryInfo{}, err
		}
		fs.log.CDebugf(
			fs.ctx, "Creating %s since it doesn't exist yet", filename)
		excl := libkbfs.NoExcl
		if flag&os.O_EXCL != 0 {
			excl = libkbfs.WithExcl
		}
		isExec := (perm & 0100) != 0
		n, ei, err = fs.config.KBFSOps().CreateFile(
			fs.ctx, dir, filename, isExec, excl)
		switch errors.Cause(err).(type) {
		case data.NameExistsError:
			// Someone made it already; recurse to try the lookup again.
			fs.log.CDebugf(
				fs.ctx, "Attempting lookup again after failed create")
			return fs.lookupOrCreateEntryNoFollow(dir, filename, flag, perm)
		case nil:
			return n, ei, nil
		default:
			return nil, data.EntryInfo{}, err
		}
	case nil:
		// If we were supposed to have exclusively-created this file,
		// we must fail.
		if flag&os.O_CREATE != 0 && flag&os.O_EXCL != 0 {
			return nil, data.EntryInfo{}, errors.Wrap(os.ErrExist,
				"Exclusive create failed because the file exists")
		}

		if ei.Type == data.Sym {
			// The caller must retry if desired.
			return nil, ei, nil
		}

		return n, ei, nil
	default:
		return nil, data.EntryInfo{}, err
	}
}

// lookupParentWithDepth looks up the parent node of the given
// filename.  It follows symlinks in the path, but doesn't resolve the
// final base name.  If `exitEarly` is true, it returns on the first
// not-found error and `base` will contain the subpath of filename not
// yet found.
func (fs *FS) lookupParentWithDepth(
	filename string, exitEarly bool, depth int) (
	parent libkbfs.Node, parentDir, base string, err error) {
	parts := strings.Split(filename, "/")
	n := fs.root
	// Iterate through each of the parent directories of the file, but
	// not the file itself.
	for i := 0; i < len(parts)-1; i++ {
		p := parts[i]
		nextNode, ei, err := fs.config.KBFSOps().Lookup(
			fs.ctx, n, n.ChildName(p))
		switch errors.Cause(err).(type) {
		case idutil.NoSuchNameError:
			if exitEarly {
				parentDir = path.Join(parts[:i]...)
				base = path.Join(parts[i:]...)
				return n, parentDir, base, nil
			}
			return nil, "", "", err
		case nil:
			n = nextNode
		default:
			return nil, "", "", err
		}

		switch ei.Type {
		case data.Sym:
			if depth == maxSymlinkLevels {
				return nil, "", "", errors.New("Too many levels of symlinks")
			}
			parentDir = path.Join(parts[:i]...)
			newPath, err := followSymlink(parentDir, ei.SymPath)
			if err != nil {
				return nil, "", "", err
			}
			newPathPlusRemainder := append([]string{newPath}, parts[i+1:]...)
			return fs.lookupParentWithDepth(
				path.Join(newPathPlusRemainder...), exitEarly, depth+1)
		case data.Dir:
			continue
		default:
			return nil, "", "", ErrNotADirectory{Name: path.Join(parts[:i+1]...)}
		}
	}

	parentDir = path.Join(parts[:len(parts)-1]...)
	base = parts[len(parts)-1]
	return n, parentDir, base, nil
}

func (fs *FS) lookupParent(filename string) (
	parent libkbfs.Node, parentDir, base string, err error) {
	return fs.lookupParentWithDepth(filename, false, 0)
}

// lookupOrCreateEntry looks up the entry for a filename, following
// symlinks in the path (including if the final entry is a symlink).
// If the entry doesn't exist an O_CREATE is set in `flag`, it will
// create the entry as a file.
func (fs *FS) lookupOrCreateEntry(
	filename string, flag int, perm os.FileMode) (
	n libkbfs.Node, ei data.EntryInfo, err error) {
	// Shortcut the case where there's nothing to look up.
	if filename == "" || filename == "/" || filename == "." {
		return fs.root, fs.rootInfo, nil
	}
	filename = strings.TrimPrefix(filename, "/")

	for i := 0; i < maxSymlinkLevels; i++ {
		var parentDir, fName string
		n, parentDir, fName, err = fs.lookupParent(filename)
		if err != nil {
			return nil, data.EntryInfo{}, err
		}

		n, ei, err := fs.lookupOrCreateEntryNoFollow(
			n, n.ChildName(fName), flag, perm)
		if err != nil {
			return nil, data.EntryInfo{}, err
		}

		if ei.Type != data.Sym {
			return n, ei, nil
		}
		fs.log.CDebugf(fs.ctx, "Following symlink=%s from dir=%s",
			fs.PathForLogging(ei.SymPath), fs.PathForLogging(parentDir))
		filename, err = followSymlink(parentDir, ei.SymPath)
		if err != nil {
			return nil, data.EntryInfo{}, err
		}
	}
	return nil, data.EntryInfo{}, errors.New("Too many levels of symlinks")
}

func translateErr(err error) error {
	switch errors.Cause(err).(type) {
	case idutil.NoSuchNameError, ErrNotADirectory:
		return os.ErrNotExist
	case libkbfs.TlfAccessError, tlfhandle.ReadAccessError:
		return os.ErrPermission
	case libkbfs.NotDirError, libkbfs.NotFileError:
		return os.ErrInvalid
	case data.NameExistsError:
		return os.ErrExist
	default:
		return err
	}
}

func (fs *FS) mkdirAll(filename string, perm os.FileMode) (err error) {
	defer func() {
		err = translateErr(err)
	}()

	if filename == "/" || filename == "" || filename == "." {
		return nil
	}

	n, _, leftover, err := fs.lookupParentWithDepth(filename, true, 0)
	if err != nil {
		return err
	}

	parts := strings.Split(leftover, "/")
	// Make all necessary dirs.
	for _, p := range parts {
		child, _, err := fs.config.KBFSOps().CreateDir(
			fs.ctx, n, n.ChildName(p))
		switch errors.Cause(err).(type) {
		case data.NameExistsError:
			// The child directory already exists.
		case tlfhandle.WriteAccessError, libkbfs.WriteToReadonlyNodeError:
			// If the child already exists, this doesn't matter.
			var lookupErr error
			child, _, lookupErr = fs.config.KBFSOps().Lookup(
				fs.ctx, n, n.ChildName(p))
			if lookupErr != nil {
				return err
			}
		case nil:
		default:
			return err
		}
		n = child
	}

	return nil
}

func (fs *FS) ensureParentDir(filename string) error {
	err := fs.mkdirAll(path.Dir(filename), 0755)
	if err != nil && !os.IsExist(err) {
		switch errors.Cause(err).(type) {
		case tlfhandle.WriteAccessError, libkbfs.WriteToReadonlyNodeError:
			// We're not allowed to create any of the parent
			// directories automatically, so give back a proper
			// isNotExist error.
			fs.log.CDebugf(fs.ctx, "ensureParentDir: "+
				"can't mkdir all due to permission error %+v", err)
			return os.ErrNotExist
		default:
			return err
		}
	}
	return nil
}

type onFsEmpty bool

const (
	onFsEmptyErrNotExist     onFsEmpty = true
	onFsEmptyErrNotSupported onFsEmpty = false
)

// chooseErrorIfEmpty checks if fs is empty, and returns an error if it is.
// Based on onFsEmpty, it returns either os.ErrNotExist or a custom error. This
// is useful for operations like Stat and allows caller to treat lookups in an
// empty FS as not exist, as they should.
func (fs *FS) chooseErrorIfEmpty(onFsEmpty onFsEmpty) error {
	if fs.empty && onFsEmpty == onFsEmptyErrNotExist {
		return os.ErrNotExist
	} else if fs.empty {
		return errors.New("Not supported for an empty TLF")
	}
	return nil
}

// OpenFile implements the billy.Filesystem interface for FS.
func (fs *FS) OpenFile(filename string, flag int, perm os.FileMode) (
	f billy.File, err error) {
	fs.log.CDebugf(
		fs.ctx, "OpenFile %s, flag=%d, perm=%o",
		fs.PathForLogging(filename), flag, perm)
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "OpenFile done: %+v", err)
		err = translateErr(err)
	}()

	if err := fs.chooseErrorIfEmpty(flag&os.O_CREATE == 0); err != nil {
		return nil, err
	}

	err = fs.ensureParentDir(filename)
	if err != nil {
		return nil, err
	}

	n, ei, err := fs.lookupOrCreateEntry(filename, flag, perm)
	if err != nil {
		return nil, err
	}

	// Make sure this is a file.
	if !ei.Type.IsFile() {
		return nil, errors.Errorf("%s is not a file", filename)
	}

	if flag&os.O_TRUNC != 0 {
		err := fs.config.KBFSOps().Truncate(fs.ctx, n, 0)
		if err != nil {
			return nil, err
		}
	}

	offset := int64(0)
	if flag&os.O_APPEND != 0 {
		if ei.Size >= uint64(1<<63) {
			return nil, errors.New("offset too large")
		}
		offset = int64(ei.Size)
	}

	return &File{
		fs:       fs,
		filename: filename,
		node:     n,
		readOnly: flag == os.O_RDONLY,
		offset:   offset,
	}, nil
}

// Create implements the billy.Filesystem interface for FS.
func (fs *FS) Create(filename string) (billy.File, error) {
	return fs.OpenFile(filename, os.O_CREATE, 0600)
}

// Open implements the billy.Filesystem interface for FS.
func (fs *FS) Open(filename string) (billy.File, error) {
	return fs.OpenFile(filename, os.O_RDONLY, 0600)
}

func (fs *FS) makeFileInfo(
	ei data.EntryInfo, node libkbfs.Node, name string) os.FileInfo {
	if IsFastModeEnabled(fs.ctx) {
		return &FileInfoFast{
			name: name,
			ei:   ei,
		}
	}
	return &FileInfo{
		fs:   fs,
		ei:   ei,
		node: node,
		name: name,
	}
}

// Stat implements the billy.Filesystem interface for FS.
func (fs *FS) Stat(filename string) (fi os.FileInfo, err error) {
	fs.log.CDebugf(fs.ctx, "Stat %s", fs.PathForLogging(filename))
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "Stat done: %+v", err)
		err = translateErr(err)
	}()

	if fs.empty && (filename == "" || filename == ".") {
		// We can't just uncondionally use FileInfoFast here as that'd result
		// in WritePerm unset for non-existent TLFs.
		return fs.makeFileInfo(data.EntryInfo{
			Type: data.Dir,
		}, nil, filename), nil
	} else if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotExist); err != nil {
		return nil, err
	}

	n, ei, err := fs.lookupOrCreateEntry(filename, os.O_RDONLY, 0)
	if err != nil {
		return nil, err
	}

	return fs.makeFileInfo(ei, n, n.GetBasename().Plaintext()), nil
}

// Rename implements the billy.Filesystem interface for FS.
func (fs *FS) Rename(oldpath, newpath string) (err error) {
	fs.log.CDebugf(fs.ctx, "Rename %s -> %s",
		fs.PathForLogging(oldpath), fs.PathForLogging(newpath))
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "Rename done: %+v", err)
		err = translateErr(err)
	}()

	if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotSupported); err != nil {
		return err
	}

	err = fs.mkdirAll(path.Dir(newpath), 0755)
	if err != nil && !os.IsExist(err) {
		return err
	}

	oldParent, _, oldBase, err := fs.lookupParent(oldpath)
	if err != nil {
		return err
	}

	newParent, _, newBase, err := fs.lookupParent(newpath)
	if err != nil {
		return err
	}

	return fs.config.KBFSOps().Rename(
		fs.ctx, oldParent, oldParent.ChildName(oldBase), newParent,
		newParent.ChildName(newBase))
}

// Remove implements the billy.Filesystem interface for FS.
func (fs *FS) Remove(filename string) (err error) {
	fs.log.CDebugf(fs.ctx, "Remove %s", fs.PathForLogging(filename))
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "Remove done: %+v", err)
		err = translateErr(err)
	}()

	if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotSupported); err != nil {
		return err
	}

	parent, _, base, err := fs.lookupParent(filename)
	if err != nil {
		return err
	}

	basePart := parent.ChildName(base)
	_, ei, err := fs.config.KBFSOps().Lookup(fs.ctx, parent, basePart)
	if err != nil {
		return err
	}

	if ei.Type == data.Dir {
		return fs.config.KBFSOps().RemoveDir(fs.ctx, parent, basePart)
	}
	return fs.config.KBFSOps().RemoveEntry(fs.ctx, parent, basePart)
}

// Join implements the billy.Filesystem interface for FS.
func (fs *FS) Join(elem ...string) string {
	return path.Clean(path.Join(elem...))
}

// TempFile implements the billy.Filesystem interface for FS.
func (fs *FS) TempFile(dir, prefix string) (billy.File, error) {
	if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotSupported); err != nil {
		return nil, err
	}

	// We'd have to turn off journaling to support TempFile perfectly,
	// but the given uniq ID and a random number should be good
	// enough.  Especially since most users will end up renaming the
	// temp file before journal flushing even happens.
	b := make([]byte, 8)
	_, err := rand.Read(b)
	if err != nil {
		return nil, err
	}
	suffix := fs.uniqID + "-" + base64.URLEncoding.EncodeToString(b)
	return fs.OpenFile(path.Join(dir, prefix+suffix),
		os.O_CREATE|os.O_EXCL, 0600)
}

func (fs *FS) readDir(n libkbfs.Node) (fis []os.FileInfo, err error) {
	children, err := fs.config.KBFSOps().GetDirChildren(fs.ctx, n)
	if err != nil {
		return nil, err
	}

	fis = make([]os.FileInfo, 0, len(children))
	for name, ei := range children {
		var child libkbfs.Node
		if !IsFastModeEnabled(fs.ctx) { // node is not used in FileInfoFast
			child, _, err = fs.config.KBFSOps().Lookup(fs.ctx, n, name)
			if err != nil {
				return nil, err
			}
		}

		fis = append(fis, fs.makeFileInfo(ei, child, name.Plaintext()))
	}
	return fis, nil
}

// ReadDir implements the billy.Filesystem interface for FS.
func (fs *FS) ReadDir(p string) (fis []os.FileInfo, err error) {
	fs.log.CDebugf(fs.ctx, "ReadDir %s", fs.PathForLogging(p))
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "ReadDir done: %+v", err)
		err = translateErr(err)
	}()

	if fs.empty && (p == "" || p == "." || p == "/") {
		return nil, nil
	} else if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotExist); err != nil {
		return nil, err
	}

	n, _, err := fs.lookupOrCreateEntry(p, os.O_RDONLY, 0)
	if err != nil {
		return nil, err
	}
	return fs.readDir(n)
}

// MkdirAll implements the billy.Filesystem interface for FS.
func (fs *FS) MkdirAll(filename string, perm os.FileMode) (err error) {
	fs.log.CDebugf(fs.ctx, "MkdirAll %s", fs.PathForLogging(filename))
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "MkdirAll done: %+v", err)
	}()

	if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotSupported); err != nil {
		return err
	}

	return fs.mkdirAll(filename, perm)
}

// Lstat implements the billy.Filesystem interface for FS.
func (fs *FS) Lstat(filename string) (fi os.FileInfo, err error) {
	fs.log.CDebugf(fs.ctx, "Lstat %s", fs.PathForLogging(filename))
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "Lstat done: %+v", err)
		err = translateErr(err)
	}()

	if fs.empty && (filename == "" || filename == ".") {
		// We can't just uncondionally use FileInfoFast here as that'd result
		// in WritePerm unset for non-existent TLFs.
		return fs.makeFileInfo(data.EntryInfo{
			Type: data.Dir,
		}, nil, filename), nil
	} else if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotExist); err != nil {
		return nil, err
	}

	n, _, base, err := fs.lookupParent(filename)
	if err != nil {
		return nil, err
	}

	if base == "" {
		ei, err := fs.config.KBFSOps().Stat(fs.ctx, n)
		if err != nil {
			return nil, err
		}
		return fs.makeFileInfo(ei, n, ""), nil
	}

	n, ei, err := fs.config.KBFSOps().Lookup(fs.ctx, n, n.ChildName(base))
	if err != nil {
		return nil, err
	}

	return fs.makeFileInfo(ei, n, base), nil
}

// Symlink implements the billy.Filesystem interface for FS.
func (fs *FS) Symlink(target, link string) (err error) {
	fs.log.CDebugf(fs.ctx, "Symlink target=%s link=%s",
		fs.PathForLogging(target), fs.root.ChildName(link))
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "Symlink done: %+v", err)
		err = translateErr(err)
	}()

	if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotSupported); err != nil {
		return err
	}

	err = fs.ensureParentDir(link)
	if err != nil {
		return err
	}

	n, _, base, err := fs.lookupParent(link)
	if err != nil {
		return err
	}

	_, err = fs.config.KBFSOps().CreateLink(
		fs.ctx, n, n.ChildName(base), n.ChildName(target))
	return err
}

// Readlink implements the billy.Filesystem interface for FS.
func (fs *FS) Readlink(link string) (target string, err error) {
	fs.log.CDebugf(fs.ctx, "Readlink %s", fs.PathForLogging(link))
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "Readlink done: %+v", err)
		err = translateErr(err)
	}()

	if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotExist); err != nil {
		return "", err
	}

	n, _, base, err := fs.lookupParent(link)
	if err != nil {
		return "", err
	}

	_, ei, err := fs.config.KBFSOps().Lookup(fs.ctx, n, n.ChildName(base))
	if err != nil {
		return "", err
	}

	if ei.Type != data.Sym {
		return "", errors.Errorf("%s is not a symlink", link)
	}
	return ei.SymPath, nil
}

// Chmod implements the billy.Filesystem interface for FS.
func (fs *FS) Chmod(name string, mode os.FileMode) (err error) {
	fs.log.CDebugf(fs.ctx, "Chmod %s %s", fs.PathForLogging(name), mode)
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "Chmod done: %+v", err)
		err = translateErr(err)
	}()

	if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotSupported); err != nil {
		return err
	}

	n, _, err := fs.lookupOrCreateEntry(name, os.O_RDONLY, 0)
	if err != nil {
		return err
	}

	isExec := (mode & 0100) != 0
	return fs.config.KBFSOps().SetEx(fs.ctx, n, isExec)
}

// Lchown implements the billy.Filesystem interface for FS.
func (fs *FS) Lchown(name string, uid, gid int) error {
	// KBFS doesn't support ownership changes.
	fs.log.CDebugf(fs.ctx, "Ignoring Lchown %s %d %d",
		fs.PathForLogging(name), uid, gid)
	return nil
}

// Chown implements the billy.Filesystem interface for FS.
func (fs *FS) Chown(name string, uid, gid int) error {
	// KBFS doesn't support ownership changes.
	fs.log.CDebugf(fs.ctx, "Ignoring Chown %s %d %d",
		fs.PathForLogging(name), uid, gid)
	return nil
}

// Chtimes implements the billy.Filesystem interface for FS.
func (fs *FS) Chtimes(name string, atime time.Time, mtime time.Time) (
	err error) {
	fs.log.CDebugf(fs.ctx, "Chtimes %s mtime=%s; ignoring atime=%s",
		fs.PathForLogging(name), mtime, atime)
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "Chtimes done: %+v", err)
		err = translateErr(err)
	}()

	if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotSupported); err != nil {
		return err
	}

	n, _, err := fs.lookupOrCreateEntry(name, os.O_RDONLY, 0)
	if err != nil {
		return err
	}

	return fs.config.KBFSOps().SetMtime(fs.ctx, n, &mtime)
}

// ChrootAsLibFS returns a *FS whose root is p.
func (fs *FS) ChrootAsLibFS(p string) (newFS *FS, err error) {
	fs.log.CDebugf(fs.ctx, "Chroot %s", fs.PathForLogging(p))
	defer func() {
		fs.deferLog.CDebugf(fs.ctx, "Chroot done: %+v", err)
		err = translateErr(err)
	}()

	if p == "" || p == "." {
		return fs, nil
	}

	if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotExist); err != nil {
		return nil, err
	}

	// lookupOrCreateEntry doesn't handle "..", so we don't have to
	// worry about someone trying to break out of the jail since this
	// lookup will fail.
	n, ei, err := fs.lookupOrCreateEntry(p, os.O_RDONLY, 0)
	if err != nil {
		return nil, err
	}

	return &FS{
		ctx: fs.ctx,
		fsInner: &fsInner{
			config:   fs.config,
			root:     n,
			rootInfo: ei,
			h:        fs.h,
			subdir:   path.Clean(path.Join(fs.subdir, p)),
			uniqID:   fs.uniqID,
			log:      fs.log,
			deferLog: fs.deferLog,

			// Original lock namespace plus '/' plus the subdir.
			lockNamespace: bytes.Join(
				[][]byte{fs.lockNamespace, []byte(p)}, []byte{'/'}),
			priority: fs.priority,
			events:   make(map[chan<- FSEvent]bool),
		},
	}, nil
}

// Chroot implements the billy.Filesystem interface for FS.
func (fs *FS) Chroot(p string) (newFS billy.Filesystem, err error) {
	return fs.ChrootAsLibFS(p)
}

// Root implements the billy.Filesystem interface for FS.
func (fs *FS) Root() string {
	return path.Join(fs.h.GetCanonicalPath(), fs.subdir)
}

// SyncAll syncs any outstanding buffered writes to the KBFS journal.
func (fs *FS) SyncAll() error {
	if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotSupported); err != nil {
		return err
	}
	return fs.config.KBFSOps().SyncAll(fs.ctx, fs.root.GetFolderBranch())
}

// Config returns the underlying Config object of this FS.
func (fs *FS) Config() libkbfs.Config {
	return fs.config
}

// SetLockNamespace sets the namespace used in locking.
func (fs *FS) SetLockNamespace(lockNamespace []byte) {
	fs.lockNamespace = make([]byte, len(lockNamespace))
	copy(fs.lockNamespace, lockNamespace)
}

// GetLockNamespace returns the namespace used in locking.
func (fs *FS) GetLockNamespace() (lockNamespace []byte) {
	return fs.lockNamespace
}

// SubscribeToEvents causes *File objects constructed from this *FS to send
// events to the channel at beginning of Lock and Unlock. The send is done
// blockingly so caller needs to drain the channel properly or make it buffered
// with enough size.
func (fs *FS) SubscribeToEvents(ch chan<- FSEvent) {
	fs.eventsLock.Lock()
	defer fs.eventsLock.Unlock()
	fs.events[ch] = true
}

// UnsubscribeToEvents stops *File objects constructed from this *FS from
// sending events to ch. It also closes ch.
func (fs *FS) UnsubscribeToEvents(ch chan<- FSEvent) {
	fs.eventsLock.Lock()
	defer fs.eventsLock.Unlock()
	delete(fs.events, ch)
	close(ch)
}

func (fs *FS) sendEvents(e FSEvent) {
	fs.eventsLock.RLock()
	defer fs.eventsLock.RUnlock()
	for ch := range fs.events {
		ch <- e
	}
}

// WithContext returns a *FS based on fs, with its ctx replaced with ctx.
func (fs *FS) WithContext(ctx context.Context) *FS {
	return &FS{
		ctx:     ctx,
		fsInner: fs.fsInner,
	}
}

// ToHTTPFileSystem calls fs.WithCtx with ctx to create a *FS with the new ctx,
// and returns a wrapper around it that satisfies the http.FileSystem
// interface.
func (fs *FS) ToHTTPFileSystem(ctx context.Context) http.FileSystem {
	return httpFileSystem{fs: fs.WithContext(ctx)}
}

// RootNode returns the Node of the root directory of this FS.
func (fs *FS) RootNode() libkbfs.Node {
	return fs.root
}

// Handle returns the TLF handle corresponding to this FS.
func (fs *FS) Handle() *tlfhandle.Handle {
	return fs.h
}

type folderHandleChangeObserver func()

func (folderHandleChangeObserver) LocalChange(
	context.Context, libkbfs.Node, libkbfs.WriteRange) {
}
func (folderHandleChangeObserver) BatchChanges(
	context.Context, []libkbfs.NodeChange, []libkbfs.NodeID) {
}
func (o folderHandleChangeObserver) TlfHandleChange(
	context.Context, *tlfhandle.Handle) {
	o()
}

// SubscribeToObsolete returns a channel that will be closed when this *FS
// reaches obsolescence, meaning if user of this object caches it for long term
// use, it should invalide this entry and create a new one using NewFS.
func (fs *FS) SubscribeToObsolete() (<-chan struct{}, error) {
	if err := fs.chooseErrorIfEmpty(onFsEmptyErrNotSupported); err != nil {
		return nil, err
	}

	c := make(chan struct{})
	var once sync.Once
	onHandleChange := folderHandleChangeObserver(
		func() { once.Do(func() { close(c) }) })
	if err := fs.config.Notifier().RegisterForChanges(
		[]data.FolderBranch{fs.root.GetFolderBranch()},
		onHandleChange); err != nil {
		return nil, err
	}
	return c, nil
}

// IsEmpty returns true if this is a faked-out empty TLF.
func (fs *FS) IsEmpty() bool {
	return fs.empty
}