Adding upstream version 1.16.10.upstream/1.16.10upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

14 files changed, 1231 insertions, 0 deletions

diff --git a/src/io/fs/fs.go b/src/io/fs/fs.go
new file mode 100644
index 0000000..3d2e2ee
--- /dev/null
+++ b/src/io/fs/fs.go
@@ -0,0 +1,257 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package fs defines basic interfaces to a file system.
+// A file system can be provided by the host operating system
+// but also by other packages.
+package fs
+
+import (
+	"internal/oserror"
+	"time"
+	"unicode/utf8"
+)
+
+// An FS provides access to a hierarchical file system.
+//
+// The FS interface is the minimum implementation required of the file system.
+// A file system may implement additional interfaces,
+// such as ReadFileFS, to provide additional or optimized functionality.
+type FS interface {
+	// Open opens the named file.
+	//
+	// When Open returns an error, it should be of type *PathError
+	// with the Op field set to "open", the Path field set to name,
+	// and the Err field describing the problem.
+	//
+	// Open should reject attempts to open names that do not satisfy
+	// ValidPath(name), returning a *PathError with Err set to
+	// ErrInvalid or ErrNotExist.
+	Open(name string) (File, error)
+}
+
+// ValidPath reports whether the given path name
+// is valid for use in a call to Open.
+//
+// Path names passed to open are UTF-8-encoded,
+// unrooted, slash-separated sequences of path elements, like “x/y/z”.
+// Path names must not contain an element that is “.” or “..” or the empty string,
+// except for the special case that the root directory is named “.”.
+// Paths must not start or end with a slash: “/x” and “x/” are invalid.
+//
+// Note that paths are slash-separated on all systems, even Windows.
+// Paths containing other characters such as backslash and colon
+// are accepted as valid, but those characters must never be
+// interpreted by an FS implementation as path element separators.
+func ValidPath(name string) bool {
+	if !utf8.ValidString(name) {
+		return false
+	}
+
+	if name == "." {
+		// special case
+		return true
+	}
+
+	// Iterate over elements in name, checking each.
+	for {
+		i := 0
+		for i < len(name) && name[i] != '/' {
+			i++
+		}
+		elem := name[:i]
+		if elem == "" || elem == "." || elem == ".." {
+			return false
+		}
+		if i == len(name) {
+			return true // reached clean ending
+		}
+		name = name[i+1:]
+	}
+}
+
+// A File provides access to a single file.
+// The File interface is the minimum implementation required of the file.
+// A file may implement additional interfaces, such as
+// ReadDirFile, ReaderAt, or Seeker, to provide additional or optimized functionality.
+type File interface {
+	Stat() (FileInfo, error)
+	Read([]byte) (int, error)
+	Close() error
+}
+
+// A DirEntry is an entry read from a directory
+// (using the ReadDir function or a ReadDirFile's ReadDir method).
+type DirEntry interface {
+	// Name returns the name of the file (or subdirectory) described by the entry.
+	// This name is only the final element of the path (the base name), not the entire path.
+	// For example, Name would return "hello.go" not "/home/gopher/hello.go".
+	Name() string
+
+	// IsDir reports whether the entry describes a directory.
+	IsDir() bool
+
+	// Type returns the type bits for the entry.
+	// The type bits are a subset of the usual FileMode bits, those returned by the FileMode.Type method.
+	Type() FileMode
+
+	// Info returns the FileInfo for the file or subdirectory described by the entry.
+	// The returned FileInfo may be from the time of the original directory read
+	// or from the time of the call to Info. If the file has been removed or renamed
+	// since the directory read, Info may return an error satisfying errors.Is(err, ErrNotExist).
+	// If the entry denotes a symbolic link, Info reports the information about the link itself,
+	// not the link's target.
+	Info() (FileInfo, error)
+}
+
+// A ReadDirFile is a directory file whose entries can be read with the ReadDir method.
+// Every directory file should implement this interface.
+// (It is permissible for any file to implement this interface,
+// but if so ReadDir should return an error for non-directories.)
+type ReadDirFile interface {
+	File
+
+	// ReadDir reads the contents of the directory and returns
+	// a slice of up to n DirEntry values in directory order.
+	// Subsequent calls on the same file will yield further DirEntry values.
+	//
+	// If n > 0, ReadDir returns at most n DirEntry structures.
+	// In this case, if ReadDir returns an empty slice, it will return
+	// a non-nil error explaining why.
+	// At the end of a directory, the error is io.EOF.
+	//
+	// If n <= 0, ReadDir returns all the DirEntry values from the directory
+	// in a single slice. In this case, if ReadDir succeeds (reads all the way
+	// to the end of the directory), it returns the slice and a nil error.
+	// If it encounters an error before the end of the directory,
+	// ReadDir returns the DirEntry list read until that point and a non-nil error.
+	ReadDir(n int) ([]DirEntry, error)
+}
+
+// Generic file system errors.
+// Errors returned by file systems can be tested against these errors
+// using errors.Is.
+var (
+	ErrInvalid    = errInvalid()    // "invalid argument"
+	ErrPermission = errPermission() // "permission denied"
+	ErrExist      = errExist()      // "file already exists"
+	ErrNotExist   = errNotExist()   // "file does not exist"
+	ErrClosed     = errClosed()     // "file already closed"
+)
+
+func errInvalid() error    { return oserror.ErrInvalid }
+func errPermission() error { return oserror.ErrPermission }
+func errExist() error      { return oserror.ErrExist }
+func errNotExist() error   { return oserror.ErrNotExist }
+func errClosed() error     { return oserror.ErrClosed }
+
+// A FileInfo describes a file and is returned by Stat.
+type FileInfo interface {
+	Name() string       // base name of the file
+	Size() int64        // length in bytes for regular files; system-dependent for others
+	Mode() FileMode     // file mode bits
+	ModTime() time.Time // modification time
+	IsDir() bool        // abbreviation for Mode().IsDir()
+	Sys() interface{}   // underlying data source (can return nil)
+}
+
+// A FileMode represents a file's mode and permission bits.
+// The bits have the same definition on all systems, so that
+// information about files can be moved from one system
+// to another portably. Not all bits apply to all systems.
+// The only required bit is ModeDir for directories.
+type FileMode uint32
+
+// The defined file mode bits are the most significant bits of the FileMode.
+// The nine least-significant bits are the standard Unix rwxrwxrwx permissions.
+// The values of these bits should be considered part of the public API and
+// may be used in wire protocols or disk representations: they must not be
+// changed, although new bits might be added.
+const (
+	// The single letters are the abbreviations
+	// used by the String method's formatting.
+	ModeDir        FileMode = 1 << (32 - 1 - iota) // d: is a directory
+	ModeAppend                                     // a: append-only
+	ModeExclusive                                  // l: exclusive use
+	ModeTemporary                                  // T: temporary file; Plan 9 only
+	ModeSymlink                                    // L: symbolic link
+	ModeDevice                                     // D: device file
+	ModeNamedPipe                                  // p: named pipe (FIFO)
+	ModeSocket                                     // S: Unix domain socket
+	ModeSetuid                                     // u: setuid
+	ModeSetgid                                     // g: setgid
+	ModeCharDevice                                 // c: Unix character device, when ModeDevice is set
+	ModeSticky                                     // t: sticky
+	ModeIrregular                                  // ?: non-regular file; nothing else is known about this file
+
+	// Mask for the type bits. For regular files, none will be set.
+	ModeType = ModeDir | ModeSymlink | ModeNamedPipe | ModeSocket | ModeDevice | ModeCharDevice | ModeIrregular
+
+	ModePerm FileMode = 0777 // Unix permission bits
+)
+
+func (m FileMode) String() string {
+	const str = "dalTLDpSugct?"
+	var buf [32]byte // Mode is uint32.
+	w := 0
+	for i, c := range str {
+		if m&(1<<uint(32-1-i)) != 0 {
+			buf[w] = byte(c)
+			w++
+		}
+	}
+	if w == 0 {
+		buf[w] = '-'
+		w++
+	}
+	const rwx = "rwxrwxrwx"
+	for i, c := range rwx {
+		if m&(1<<uint(9-1-i)) != 0 {
+			buf[w] = byte(c)
+		} else {
+			buf[w] = '-'
+		}
+		w++
+	}
+	return string(buf[:w])
+}
+
+// IsDir reports whether m describes a directory.
+// That is, it tests for the ModeDir bit being set in m.
+func (m FileMode) IsDir() bool {
+	return m&ModeDir != 0
+}
+
+// IsRegular reports whether m describes a regular file.
+// That is, it tests that no mode type bits are set.
+func (m FileMode) IsRegular() bool {
+	return m&ModeType == 0
+}
+
+// Perm returns the Unix permission bits in m (m & ModePerm).
+func (m FileMode) Perm() FileMode {
+	return m & ModePerm
+}
+
+// Type returns type bits in m (m & ModeType).
+func (m FileMode) Type() FileMode {
+	return m & ModeType
+}
+
+// PathError records an error and the operation and file path that caused it.
+type PathError struct {
+	Op   string
+	Path string
+	Err  error
+}
+
+func (e *PathError) Error() string { return e.Op + " " + e.Path + ": " + e.Err.Error() }
+
+func (e *PathError) Unwrap() error { return e.Err }
+
+// Timeout reports whether this error represents a timeout.
+func (e *PathError) Timeout() bool {
+	t, ok := e.Err.(interface{ Timeout() bool })
+	return ok && t.Timeout()
+}
diff --git a/src/io/fs/fs_test.go b/src/io/fs/fs_test.go
new file mode 100644
index 0000000..aae1a76
--- /dev/null
+++ b/src/io/fs/fs_test.go
@@ -0,0 +1,49 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs_test
+
+import (
+	. "io/fs"
+	"testing"
+)
+
+var isValidPathTests = []struct {
+	name string
+	ok   bool
+}{
+	{".", true},
+	{"x", true},
+	{"x/y", true},
+
+	{"", false},
+	{"..", false},
+	{"/", false},
+	{"x/", false},
+	{"/x", false},
+	{"x/y/", false},
+	{"/x/y", false},
+	{"./", false},
+	{"./x", false},
+	{"x/.", false},
+	{"x/./y", false},
+	{"../", false},
+	{"../x", false},
+	{"x/..", false},
+	{"x/../y", false},
+	{"x//y", false},
+	{`x\`, true},
+	{`x\y`, true},
+	{`x:y`, true},
+	{`\x`, true},
+}
+
+func TestValidPath(t *testing.T) {
+	for _, tt := range isValidPathTests {
+		ok := ValidPath(tt.name)
+		if ok != tt.ok {
+			t.Errorf("ValidPath(%q) = %v, want %v", tt.name, ok, tt.ok)
+		}
+	}
+}
diff --git a/src/io/fs/glob.go b/src/io/fs/glob.go
new file mode 100644
index 0000000..45d9cb6
--- /dev/null
+++ b/src/io/fs/glob.go
@@ -0,0 +1,119 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs
+
+import (
+	"path"
+)
+
+// A GlobFS is a file system with a Glob method.
+type GlobFS interface {
+	FS
+
+	// Glob returns the names of all files matching pattern,
+	// providing an implementation of the top-level
+	// Glob function.
+	Glob(pattern string) ([]string, error)
+}
+
+// Glob returns the names of all files matching pattern or nil
+// if there is no matching file. The syntax of patterns is the same
+// as in path.Match. The pattern may describe hierarchical names such as
+// usr/*/bin/ed.
+//
+// Glob ignores file system errors such as I/O errors reading directories.
+// The only possible returned error is path.ErrBadPattern, reporting that
+// the pattern is malformed.
+//
+// If fs implements GlobFS, Glob calls fs.Glob.
+// Otherwise, Glob uses ReadDir to traverse the directory tree
+// and look for matches for the pattern.
+func Glob(fsys FS, pattern string) (matches []string, err error) {
+	if fsys, ok := fsys.(GlobFS); ok {
+		return fsys.Glob(pattern)
+	}
+
+	// Check pattern is well-formed.
+	if _, err := path.Match(pattern, ""); err != nil {
+		return nil, err
+	}
+	if !hasMeta(pattern) {
+		if _, err = Stat(fsys, pattern); err != nil {
+			return nil, nil
+		}
+		return []string{pattern}, nil
+	}
+
+	dir, file := path.Split(pattern)
+	dir = cleanGlobPath(dir)
+
+	if !hasMeta(dir) {
+		return glob(fsys, dir, file, nil)
+	}
+
+	// Prevent infinite recursion. See issue 15879.
+	if dir == pattern {
+		return nil, path.ErrBadPattern
+	}
+
+	var m []string
+	m, err = Glob(fsys, dir)
+	if err != nil {
+		return
+	}
+	for _, d := range m {
+		matches, err = glob(fsys, d, file, matches)
+		if err != nil {
+			return
+		}
+	}
+	return
+}
+
+// cleanGlobPath prepares path for glob matching.
+func cleanGlobPath(path string) string {
+	switch path {
+	case "":
+		return "."
+	default:
+		return path[0 : len(path)-1] // chop off trailing separator
+	}
+}
+
+// glob searches for files matching pattern in the directory dir
+// and appends them to matches, returning the updated slice.
+// If the directory cannot be opened, glob returns the existing matches.
+// New matches are added in lexicographical order.
+func glob(fs FS, dir, pattern string, matches []string) (m []string, e error) {
+	m = matches
+	infos, err := ReadDir(fs, dir)
+	if err != nil {
+		return // ignore I/O error
+	}
+
+	for _, info := range infos {
+		n := info.Name()
+		matched, err := path.Match(pattern, n)
+		if err != nil {
+			return m, err
+		}
+		if matched {
+			m = append(m, path.Join(dir, n))
+		}
+	}
+	return
+}
+
+// hasMeta reports whether path contains any of the magic characters
+// recognized by path.Match.
+func hasMeta(path string) bool {
+	for i := 0; i < len(path); i++ {
+		switch path[i] {
+		case '*', '?', '[', '\\':
+			return true
+		}
+	}
+	return false
+}
diff --git a/src/io/fs/glob_test.go b/src/io/fs/glob_test.go
new file mode 100644
index 0000000..f19bebe
--- /dev/null
+++ b/src/io/fs/glob_test.go
@@ -0,0 +1,87 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs_test
+
+import (
+	. "io/fs"
+	"os"
+	"path"
+	"testing"
+)
+
+var globTests = []struct {
+	fs              FS
+	pattern, result string
+}{
+	{os.DirFS("."), "glob.go", "glob.go"},
+	{os.DirFS("."), "gl?b.go", "glob.go"},
+	{os.DirFS("."), `gl\ob.go`, "glob.go"},
+	{os.DirFS("."), "*", "glob.go"},
+	{os.DirFS(".."), "*/glob.go", "fs/glob.go"},
+}
+
+func TestGlob(t *testing.T) {
+	for _, tt := range globTests {
+		matches, err := Glob(tt.fs, tt.pattern)
+		if err != nil {
+			t.Errorf("Glob error for %q: %s", tt.pattern, err)
+			continue
+		}
+		if !contains(matches, tt.result) {
+			t.Errorf("Glob(%#q) = %#v want %v", tt.pattern, matches, tt.result)
+		}
+	}
+	for _, pattern := range []string{"no_match", "../*/no_match", `\*`} {
+		matches, err := Glob(os.DirFS("."), pattern)
+		if err != nil {
+			t.Errorf("Glob error for %q: %s", pattern, err)
+			continue
+		}
+		if len(matches) != 0 {
+			t.Errorf("Glob(%#q) = %#v want []", pattern, matches)
+		}
+	}
+}
+
+func TestGlobError(t *testing.T) {
+	bad := []string{`[]`, `nonexist/[]`}
+	for _, pattern := range bad {
+		_, err := Glob(os.DirFS("."), pattern)
+		if err != path.ErrBadPattern {
+			t.Errorf("Glob(fs, %#q) returned err=%v, want path.ErrBadPattern", pattern, err)
+		}
+	}
+}
+
+// contains reports whether vector contains the string s.
+func contains(vector []string, s string) bool {
+	for _, elem := range vector {
+		if elem == s {
+			return true
+		}
+	}
+	return false
+}
+
+type globOnly struct{ GlobFS }
+
+func (globOnly) Open(name string) (File, error) { return nil, ErrNotExist }
+
+func TestGlobMethod(t *testing.T) {
+	check := func(desc string, names []string, err error) {
+		t.Helper()
+		if err != nil || len(names) != 1 || names[0] != "hello.txt" {
+			t.Errorf("Glob(%s) = %v, %v, want %v, nil", desc, names, err, []string{"hello.txt"})
+		}
+	}
+
+	// Test that ReadDir uses the method when present.
+	names, err := Glob(globOnly{testFsys}, "*.txt")
+	check("readDirOnly", names, err)
+
+	// Test that ReadDir uses Open when the method is not present.
+	names, err = Glob(openOnly{testFsys}, "*.txt")
+	check("openOnly", names, err)
+}
diff --git a/src/io/fs/readdir.go b/src/io/fs/readdir.go
new file mode 100644
index 0000000..3a5aa6d
--- /dev/null
+++ b/src/io/fs/readdir.go
@@ -0,0 +1,47 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs
+
+import (
+	"errors"
+	"sort"
+)
+
+// ReadDirFS is the interface implemented by a file system
+// that provides an optimized implementation of ReadDir.
+type ReadDirFS interface {
+	FS
+
+	// ReadDir reads the named directory
+	// and returns a list of directory entries sorted by filename.
+	ReadDir(name string) ([]DirEntry, error)
+}
+
+// ReadDir reads the named directory
+// and returns a list of directory entries sorted by filename.
+//
+// If fs implements ReadDirFS, ReadDir calls fs.ReadDir.
+// Otherwise ReadDir calls fs.Open and uses ReadDir and Close
+// on the returned file.
+func ReadDir(fsys FS, name string) ([]DirEntry, error) {
+	if fsys, ok := fsys.(ReadDirFS); ok {
+		return fsys.ReadDir(name)
+	}
+
+	file, err := fsys.Open(name)
+	if err != nil {
+		return nil, err
+	}
+	defer file.Close()
+
+	dir, ok := file.(ReadDirFile)
+	if !ok {
+		return nil, &PathError{Op: "readdir", Path: name, Err: errors.New("not implemented")}
+	}
+
+	list, err := dir.ReadDir(-1)
+	sort.Slice(list, func(i, j int) bool { return list[i].Name() < list[j].Name() })
+	return list, err
+}
diff --git a/src/io/fs/readdir_test.go b/src/io/fs/readdir_test.go
new file mode 100644
index 0000000..405bfa6
--- /dev/null
+++ b/src/io/fs/readdir_test.go
@@ -0,0 +1,43 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs_test
+
+import (
+	. "io/fs"
+	"testing"
+)
+
+type readDirOnly struct{ ReadDirFS }
+
+func (readDirOnly) Open(name string) (File, error) { return nil, ErrNotExist }
+
+func TestReadDir(t *testing.T) {
+	check := func(desc string, dirs []DirEntry, err error) {
+		t.Helper()
+		if err != nil || len(dirs) != 2 || dirs[0].Name() != "hello.txt" || dirs[1].Name() != "sub" {
+			var names []string
+			for _, d := range dirs {
+				names = append(names, d.Name())
+			}
+			t.Errorf("ReadDir(%s) = %v, %v, want %v, nil", desc, names, err, []string{"hello.txt", "sub"})
+		}
+	}
+
+	// Test that ReadDir uses the method when present.
+	dirs, err := ReadDir(readDirOnly{testFsys}, ".")
+	check("readDirOnly", dirs, err)
+
+	// Test that ReadDir uses Open when the method is not present.
+	dirs, err = ReadDir(openOnly{testFsys}, ".")
+	check("openOnly", dirs, err)
+
+	// Test that ReadDir on Sub of . works (sub_test checks non-trivial subs).
+	sub, err := Sub(testFsys, ".")
+	if err != nil {
+		t.Fatal(err)
+	}
+	dirs, err = ReadDir(sub, ".")
+	check("sub(.)", dirs, err)
+}
diff --git a/src/io/fs/readfile.go b/src/io/fs/readfile.go
new file mode 100644
index 0000000..7ee9ead
--- /dev/null
+++ b/src/io/fs/readfile.go
@@ -0,0 +1,63 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs
+
+import "io"
+
+// ReadFileFS is the interface implemented by a file system
+// that provides an optimized implementation of ReadFile.
+type ReadFileFS interface {
+	FS
+
+	// ReadFile reads the named file and returns its contents.
+	// A successful call returns a nil error, not io.EOF.
+	// (Because ReadFile reads the whole file, the expected EOF
+	// from the final Read is not treated as an error to be reported.)
+	ReadFile(name string) ([]byte, error)
+}
+
+// ReadFile reads the named file from the file system fs and returns its contents.
+// A successful call returns a nil error, not io.EOF.
+// (Because ReadFile reads the whole file, the expected EOF
+// from the final Read is not treated as an error to be reported.)
+//
+// If fs implements ReadFileFS, ReadFile calls fs.ReadFile.
+// Otherwise ReadFile calls fs.Open and uses Read and Close
+// on the returned file.
+func ReadFile(fsys FS, name string) ([]byte, error) {
+	if fsys, ok := fsys.(ReadFileFS); ok {
+		return fsys.ReadFile(name)
+	}
+
+	file, err := fsys.Open(name)
+	if err != nil {
+		return nil, err
+	}
+	defer file.Close()
+
+	var size int
+	if info, err := file.Stat(); err == nil {
+		size64 := info.Size()
+		if int64(int(size64)) == size64 {
+			size = int(size64)
+		}
+	}
+
+	data := make([]byte, 0, size+1)
+	for {
+		if len(data) >= cap(data) {
+			d := append(data[:cap(data)], 0)
+			data = d[:len(data)]
+		}
+		n, err := file.Read(data[len(data):cap(data)])
+		data = data[:len(data)+n]
+		if err != nil {
+			if err == io.EOF {
+				err = nil
+			}
+			return data, err
+		}
+	}
+}
diff --git a/src/io/fs/readfile_test.go b/src/io/fs/readfile_test.go
new file mode 100644
index 0000000..07219c1
--- /dev/null
+++ b/src/io/fs/readfile_test.go
@@ -0,0 +1,59 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs_test
+
+import (
+	. "io/fs"
+	"testing"
+	"testing/fstest"
+	"time"
+)
+
+var testFsys = fstest.MapFS{
+	"hello.txt": {
+		Data:    []byte("hello, world"),
+		Mode:    0456,
+		ModTime: time.Now(),
+		Sys:     &sysValue,
+	},
+	"sub/goodbye.txt": {
+		Data:    []byte("goodbye, world"),
+		Mode:    0456,
+		ModTime: time.Now(),
+		Sys:     &sysValue,
+	},
+}
+
+var sysValue int
+
+type readFileOnly struct{ ReadFileFS }
+
+func (readFileOnly) Open(name string) (File, error) { return nil, ErrNotExist }
+
+type openOnly struct{ FS }
+
+func TestReadFile(t *testing.T) {
+	// Test that ReadFile uses the method when present.
+	data, err := ReadFile(readFileOnly{testFsys}, "hello.txt")
+	if string(data) != "hello, world" || err != nil {
+		t.Fatalf(`ReadFile(readFileOnly, "hello.txt") = %q, %v, want %q, nil`, data, err, "hello, world")
+	}
+
+	// Test that ReadFile uses Open when the method is not present.
+	data, err = ReadFile(openOnly{testFsys}, "hello.txt")
+	if string(data) != "hello, world" || err != nil {
+		t.Fatalf(`ReadFile(openOnly, "hello.txt") = %q, %v, want %q, nil`, data, err, "hello, world")
+	}
+
+	// Test that ReadFile on Sub of . works (sub_test checks non-trivial subs).
+	sub, err := Sub(testFsys, ".")
+	if err != nil {
+		t.Fatal(err)
+	}
+	data, err = ReadFile(sub, "hello.txt")
+	if string(data) != "hello, world" || err != nil {
+		t.Fatalf(`ReadFile(sub(.), "hello.txt") = %q, %v, want %q, nil`, data, err, "hello, world")
+	}
+}
diff --git a/src/io/fs/stat.go b/src/io/fs/stat.go
new file mode 100644
index 0000000..735a6e3
--- /dev/null
+++ b/src/io/fs/stat.go
@@ -0,0 +1,31 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs
+
+// A StatFS is a file system with a Stat method.
+type StatFS interface {
+	FS
+
+	// Stat returns a FileInfo describing the file.
+	// If there is an error, it should be of type *PathError.
+	Stat(name string) (FileInfo, error)
+}
+
+// Stat returns a FileInfo describing the named file from the file system.
+//
+// If fs implements StatFS, Stat calls fs.Stat.
+// Otherwise, Stat opens the file to stat it.
+func Stat(fsys FS, name string) (FileInfo, error) {
+	if fsys, ok := fsys.(StatFS); ok {
+		return fsys.Stat(name)
+	}
+
+	file, err := fsys.Open(name)
+	if err != nil {
+		return nil, err
+	}
+	defer file.Close()
+	return file.Stat()
+}
diff --git a/src/io/fs/stat_test.go b/src/io/fs/stat_test.go
new file mode 100644
index 0000000..e312b6f
--- /dev/null
+++ b/src/io/fs/stat_test.go
@@ -0,0 +1,36 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs_test
+
+import (
+	"fmt"
+	. "io/fs"
+	"testing"
+)
+
+type statOnly struct{ StatFS }
+
+func (statOnly) Open(name string) (File, error) { return nil, ErrNotExist }
+
+func TestStat(t *testing.T) {
+	check := func(desc string, info FileInfo, err error) {
+		t.Helper()
+		if err != nil || info == nil || info.Mode() != 0456 {
+			infoStr := "<nil>"
+			if info != nil {
+				infoStr = fmt.Sprintf("FileInfo(Mode: %#o)", info.Mode())
+			}
+			t.Fatalf("Stat(%s) = %v, %v, want Mode:0456, nil", desc, infoStr, err)
+		}
+	}
+
+	// Test that Stat uses the method when present.
+	info, err := Stat(statOnly{testFsys}, "hello.txt")
+	check("statOnly", info, err)
+
+	// Test that Stat uses Open when the method is not present.
+	info, err = Stat(openOnly{testFsys}, "hello.txt")
+	check("openOnly", info, err)
+}
diff --git a/src/io/fs/sub.go b/src/io/fs/sub.go
new file mode 100644
index 0000000..64cdffe
--- /dev/null
+++ b/src/io/fs/sub.go
@@ -0,0 +1,127 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs
+
+import (
+	"errors"
+	"path"
+)
+
+// A SubFS is a file system with a Sub method.
+type SubFS interface {
+	FS
+
+	// Sub returns an FS corresponding to the subtree rooted at dir.
+	Sub(dir string) (FS, error)
+}
+
+// Sub returns an FS corresponding to the subtree rooted at fsys's dir.
+//
+// If fs implements SubFS, Sub calls returns fsys.Sub(dir).
+// Otherwise, if dir is ".", Sub returns fsys unchanged.
+// Otherwise, Sub returns a new FS implementation sub that,
+// in effect, implements sub.Open(dir) as fsys.Open(path.Join(dir, name)).
+// The implementation also translates calls to ReadDir, ReadFile, and Glob appropriately.
+//
+// Note that Sub(os.DirFS("/"), "prefix") is equivalent to os.DirFS("/prefix")
+// and that neither of them guarantees to avoid operating system
+// accesses outside "/prefix", because the implementation of os.DirFS
+// does not check for symbolic links inside "/prefix" that point to
+// other directories. That is, os.DirFS is not a general substitute for a
+// chroot-style security mechanism, and Sub does not change that fact.
+func Sub(fsys FS, dir string) (FS, error) {
+	if !ValidPath(dir) {
+		return nil, &PathError{Op: "sub", Path: dir, Err: errors.New("invalid name")}
+	}
+	if dir == "." {
+		return fsys, nil
+	}
+	if fsys, ok := fsys.(SubFS); ok {
+		return fsys.Sub(dir)
+	}
+	return &subFS{fsys, dir}, nil
+}
+
+type subFS struct {
+	fsys FS
+	dir  string
+}
+
+// fullName maps name to the fully-qualified name dir/name.
+func (f *subFS) fullName(op string, name string) (string, error) {
+	if !ValidPath(name) {
+		return "", &PathError{Op: op, Path: name, Err: errors.New("invalid name")}
+	}
+	return path.Join(f.dir, name), nil
+}
+
+// shorten maps name, which should start with f.dir, back to the suffix after f.dir.
+func (f *subFS) shorten(name string) (rel string, ok bool) {
+	if name == f.dir {
+		return ".", true
+	}
+	if len(name) >= len(f.dir)+2 && name[len(f.dir)] == '/' && name[:len(f.dir)] == f.dir {
+		return name[len(f.dir)+1:], true
+	}
+	return "", false
+}
+
+// fixErr shortens any reported names in PathErrors by stripping dir.
+func (f *subFS) fixErr(err error) error {
+	if e, ok := err.(*PathError); ok {
+		if short, ok := f.shorten(e.Path); ok {
+			e.Path = short
+		}
+	}
+	return err
+}
+
+func (f *subFS) Open(name string) (File, error) {
+	full, err := f.fullName("open", name)
+	if err != nil {
+		return nil, err
+	}
+	file, err := f.fsys.Open(full)
+	return file, f.fixErr(err)
+}
+
+func (f *subFS) ReadDir(name string) ([]DirEntry, error) {
+	full, err := f.fullName("read", name)
+	if err != nil {
+		return nil, err
+	}
+	dir, err := ReadDir(f.fsys, full)
+	return dir, f.fixErr(err)
+}
+
+func (f *subFS) ReadFile(name string) ([]byte, error) {
+	full, err := f.fullName("read", name)
+	if err != nil {
+		return nil, err
+	}
+	data, err := ReadFile(f.fsys, full)
+	return data, f.fixErr(err)
+}
+
+func (f *subFS) Glob(pattern string) ([]string, error) {
+	// Check pattern is well-formed.
+	if _, err := path.Match(pattern, ""); err != nil {
+		return nil, err
+	}
+	if pattern == "." {
+		return []string{"."}, nil
+	}
+
+	full := f.dir + "/" + pattern
+	list, err := Glob(f.fsys, full)
+	for i, name := range list {
+		name, ok := f.shorten(name)
+		if !ok {
+			return nil, errors.New("invalid result from inner fsys Glob: " + name + " not in " + f.dir) // can't use fmt in this package
+		}
+		list[i] = name
+	}
+	return list, f.fixErr(err)
+}
diff --git a/src/io/fs/sub_test.go b/src/io/fs/sub_test.go
new file mode 100644
index 0000000..451b0ef
--- /dev/null
+++ b/src/io/fs/sub_test.go
@@ -0,0 +1,57 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs_test
+
+import (
+	. "io/fs"
+	"testing"
+)
+
+type subOnly struct{ SubFS }
+
+func (subOnly) Open(name string) (File, error) { return nil, ErrNotExist }
+
+func TestSub(t *testing.T) {
+	check := func(desc string, sub FS, err error) {
+		t.Helper()
+		if err != nil {
+			t.Errorf("Sub(sub): %v", err)
+			return
+		}
+		data, err := ReadFile(sub, "goodbye.txt")
+		if string(data) != "goodbye, world" || err != nil {
+			t.Errorf(`ReadFile(%s, "goodbye.txt" = %q, %v, want %q, nil`, desc, string(data), err, "goodbye, world")
+		}
+
+		dirs, err := ReadDir(sub, ".")
+		if err != nil || len(dirs) != 1 || dirs[0].Name() != "goodbye.txt" {
+			var names []string
+			for _, d := range dirs {
+				names = append(names, d.Name())
+			}
+			t.Errorf(`ReadDir(%s, ".") = %v, %v, want %v, nil`, desc, names, err, []string{"goodbye.txt"})
+		}
+	}
+
+	// Test that Sub uses the method when present.
+	sub, err := Sub(subOnly{testFsys}, "sub")
+	check("subOnly", sub, err)
+
+	// Test that Sub uses Open when the method is not present.
+	sub, err = Sub(openOnly{testFsys}, "sub")
+	check("openOnly", sub, err)
+
+	_, err = sub.Open("nonexist")
+	if err == nil {
+		t.Fatal("Open(nonexist): succeeded")
+	}
+	pe, ok := err.(*PathError)
+	if !ok {
+		t.Fatalf("Open(nonexist): error is %T, want *PathError", err)
+	}
+	if pe.Path != "nonexist" {
+		t.Fatalf("Open(nonexist): err.Path = %q, want %q", pe.Path, "nonexist")
+	}
+}
diff --git a/src/io/fs/walk.go b/src/io/fs/walk.go
new file mode 100644
index 0000000..534876b
--- /dev/null
+++ b/src/io/fs/walk.go
@@ -0,0 +1,127 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs
+
+import (
+	"errors"
+	"path"
+)
+
+// SkipDir is used as a return value from WalkDirFuncs to indicate that
+// the directory named in the call is to be skipped. It is not returned
+// as an error by any function.
+var SkipDir = errors.New("skip this directory")
+
+// WalkDirFunc is the type of the function called by WalkDir to visit
+// each file or directory.
+//
+// The path argument contains the argument to WalkDir as a prefix.
+// That is, if WalkDir is called with root argument "dir" and finds a file
+// named "a" in that directory, the walk function will be called with
+// argument "dir/a".
+//
+// The d argument is the fs.DirEntry for the named path.
+//
+// The error result returned by the function controls how WalkDir
+// continues. If the function returns the special value SkipDir, WalkDir
+// skips the current directory (path if d.IsDir() is true, otherwise
+// path's parent directory). Otherwise, if the function returns a non-nil
+// error, WalkDir stops entirely and returns that error.
+//
+// The err argument reports an error related to path, signaling that
+// WalkDir will not walk into that directory. The function can decide how
+// to handle that error; as described earlier, returning the error will
+// cause WalkDir to stop walking the entire tree.
+//
+// WalkDir calls the function with a non-nil err argument in two cases.
+//
+// First, if the initial fs.Stat on the root directory fails, WalkDir
+// calls the function with path set to root, d set to nil, and err set to
+// the error from fs.Stat.
+//
+// Second, if a directory's ReadDir method fails, WalkDir calls the
+// function with path set to the directory's path, d set to an
+// fs.DirEntry describing the directory, and err set to the error from
+// ReadDir. In this second case, the function is called twice with the
+// path of the directory: the first call is before the directory read is
+// attempted and has err set to nil, giving the function a chance to
+// return SkipDir and avoid the ReadDir entirely. The second call is
+// after a failed ReadDir and reports the error from ReadDir.
+// (If ReadDir succeeds, there is no second call.)
+//
+// The differences between WalkDirFunc compared to filepath.WalkFunc are:
+//
+//   - The second argument has type fs.DirEntry instead of fs.FileInfo.
+//   - The function is called before reading a directory, to allow SkipDir
+//     to bypass the directory read entirely.
+//   - If a directory read fails, the function is called a second time
+//     for that directory to report the error.
+//
+type WalkDirFunc func(path string, d DirEntry, err error) error
+
+// walkDir recursively descends path, calling walkDirFn.
+func walkDir(fsys FS, name string, d DirEntry, walkDirFn WalkDirFunc) error {
+	if err := walkDirFn(name, d, nil); err != nil || !d.IsDir() {
+		if err == SkipDir && d.IsDir() {
+			// Successfully skipped directory.
+			err = nil
+		}
+		return err
+	}
+
+	dirs, err := ReadDir(fsys, name)
+	if err != nil {
+		// Second call, to report ReadDir error.
+		err = walkDirFn(name, d, err)
+		if err != nil {
+			return err
+		}
+	}
+
+	for _, d1 := range dirs {
+		name1 := path.Join(name, d1.Name())
+		if err := walkDir(fsys, name1, d1, walkDirFn); err != nil {
+			if err == SkipDir {
+				break
+			}
+			return err
+		}
+	}
+	return nil
+}
+
+// WalkDir walks the file tree rooted at root, calling fn for each file or
+// directory in the tree, including root.
+//
+// All errors that arise visiting files and directories are filtered by fn:
+// see the fs.WalkDirFunc documentation for details.
+//
+// The files are walked in lexical order, which makes the output deterministic
+// but requires WalkDir to read an entire directory into memory before proceeding
+// to walk that directory.
+//
+// WalkDir does not follow symbolic links found in directories,
+// but if root itself is a symbolic link, its target will be walked.
+func WalkDir(fsys FS, root string, fn WalkDirFunc) error {
+	info, err := Stat(fsys, root)
+	if err != nil {
+		err = fn(root, nil, err)
+	} else {
+		err = walkDir(fsys, root, &statDirEntry{info}, fn)
+	}
+	if err == SkipDir {
+		return nil
+	}
+	return err
+}
+
+type statDirEntry struct {
+	info FileInfo
+}
+
+func (d *statDirEntry) Name() string            { return d.info.Name() }
+func (d *statDirEntry) IsDir() bool             { return d.info.IsDir() }
+func (d *statDirEntry) Type() FileMode          { return d.info.Mode().Type() }
+func (d *statDirEntry) Info() (FileInfo, error) { return d.info, nil }
diff --git a/src/io/fs/walk_test.go b/src/io/fs/walk_test.go
new file mode 100644
index 0000000..ebc4e50
--- /dev/null
+++ b/src/io/fs/walk_test.go
@@ -0,0 +1,129 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fs_test
+
+import (
+	. "io/fs"
+	"io/ioutil"
+	"os"
+	pathpkg "path"
+	"testing"
+	"testing/fstest"
+)
+
+type Node struct {
+	name    string
+	entries []*Node // nil if the entry is a file
+	mark    int
+}
+
+var tree = &Node{
+	"testdata",
+	[]*Node{
+		{"a", nil, 0},
+		{"b", []*Node{}, 0},
+		{"c", nil, 0},
+		{
+			"d",
+			[]*Node{
+				{"x", nil, 0},
+				{"y", []*Node{}, 0},
+				{
+					"z",
+					[]*Node{
+						{"u", nil, 0},
+						{"v", nil, 0},
+					},
+					0,
+				},
+			},
+			0,
+		},
+	},
+	0,
+}
+
+func walkTree(n *Node, path string, f func(path string, n *Node)) {
+	f(path, n)
+	for _, e := range n.entries {
+		walkTree(e, pathpkg.Join(path, e.name), f)
+	}
+}
+
+func makeTree(t *testing.T) FS {
+	fsys := fstest.MapFS{}
+	walkTree(tree, tree.name, func(path string, n *Node) {
+		if n.entries == nil {
+			fsys[path] = &fstest.MapFile{}
+		} else {
+			fsys[path] = &fstest.MapFile{Mode: ModeDir}
+		}
+	})
+	return fsys
+}
+
+func markTree(n *Node) { walkTree(n, "", func(path string, n *Node) { n.mark++ }) }
+
+func checkMarks(t *testing.T, report bool) {
+	walkTree(tree, tree.name, func(path string, n *Node) {
+		if n.mark != 1 && report {
+			t.Errorf("node %s mark = %d; expected 1", path, n.mark)
+		}
+		n.mark = 0
+	})
+}
+
+// Assumes that each node name is unique. Good enough for a test.
+// If clear is true, any incoming error is cleared before return. The errors
+// are always accumulated, though.
+func mark(entry DirEntry, err error, errors *[]error, clear bool) error {
+	name := entry.Name()
+	walkTree(tree, tree.name, func(path string, n *Node) {
+		if n.name == name {
+			n.mark++
+		}
+	})
+	if err != nil {
+		*errors = append(*errors, err)
+		if clear {
+			return nil
+		}
+		return err
+	}
+	return nil
+}
+
+func TestWalkDir(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", "TestWalk")
+	if err != nil {
+		t.Fatal("creating temp dir:", err)
+	}
+	defer os.RemoveAll(tmpDir)
+
+	origDir, err := os.Getwd()
+	if err != nil {
+		t.Fatal("finding working dir:", err)
+	}
+	if err = os.Chdir(tmpDir); err != nil {
+		t.Fatal("entering temp dir:", err)
+	}
+	defer os.Chdir(origDir)
+
+	fsys := makeTree(t)
+	errors := make([]error, 0, 10)
+	clear := true
+	markFn := func(path string, entry DirEntry, err error) error {
+		return mark(entry, err, &errors, clear)
+	}
+	// Expect no errors.
+	err = WalkDir(fsys, ".", markFn)
+	if err != nil {
+		t.Fatalf("no error expected, found: %s", err)
+	}
+	if len(errors) != 0 {
+		t.Fatalf("unexpected errors: %s", errors)
+	}
+	checkMarks(t, true)
+}