diff options
Diffstat (limited to 'pkg/fspath')
| -rw-r--r-- | pkg/fspath/BUILD | 26 | ||||
| -rw-r--r-- | pkg/fspath/builder.go | 112 | ||||
| -rw-r--r-- | pkg/fspath/builder_test.go | 58 | ||||
| -rw-r--r-- | pkg/fspath/fspath.go | 187 | ||||
| -rw-r--r-- | pkg/fspath/fspath_test.go | 134 |
5 files changed, 517 insertions, 0 deletions
diff --git a/pkg/fspath/BUILD b/pkg/fspath/BUILD new file mode 100644 index 000000000..67dd1e225 --- /dev/null +++ b/pkg/fspath/BUILD @@ -0,0 +1,26 @@ +load("//tools:defs.bzl", "go_library", "go_test") + +package(default_visibility = ["//visibility:public"]) + +licenses(["notice"]) + +go_library( + name = "fspath", + srcs = [ + "builder.go", + "fspath.go", + ], + deps = [ + "//pkg/gohacks", + ], +) + +go_test( + name = "fspath_test", + size = "small", + srcs = [ + "builder_test.go", + "fspath_test.go", + ], + library = ":fspath", +) diff --git a/pkg/fspath/builder.go b/pkg/fspath/builder.go new file mode 100644 index 000000000..6318d3874 --- /dev/null +++ b/pkg/fspath/builder.go @@ -0,0 +1,112 @@ +// Copyright 2019 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package fspath + +import ( + "fmt" + + "gvisor.dev/gvisor/pkg/gohacks" +) + +// Builder is similar to strings.Builder, but is used to produce pathnames +// given path components in reverse order (from leaf to root). This is useful +// in the common case where a filesystem is represented by a tree of named +// nodes, and the path to a given node must be produced by walking upward from +// that node to a given root. +type Builder struct { + buf []byte + start int + needSep bool +} + +// Reset resets the Builder to be empty. +func (b *Builder) Reset() { + b.start = len(b.buf) + b.needSep = false +} + +// Len returns the number of accumulated bytes. +func (b *Builder) Len() int { + return len(b.buf) - b.start +} + +func (b *Builder) needToGrow(n int) bool { + return b.start < n +} + +func (b *Builder) grow(n int) { + newLen := b.Len() + n + var newCap int + if len(b.buf) == 0 { + newCap = 64 // arbitrary + } else { + newCap = 2 * len(b.buf) + } + for newCap < newLen { + newCap *= 2 + if newCap == 0 { + panic(fmt.Sprintf("required length (%d) causes buffer size to overflow", newLen)) + } + } + newBuf := make([]byte, newCap) + copy(newBuf[newCap-b.Len():], b.buf[b.start:]) + b.start += newCap - len(b.buf) + b.buf = newBuf +} + +// PrependComponent prepends the given path component to b's buffer. A path +// separator is automatically inserted if appropriate. +func (b *Builder) PrependComponent(pc string) { + if b.needSep { + b.PrependByte('/') + } + b.PrependString(pc) + b.needSep = true +} + +// PrependString prepends the given string to b's buffer. +func (b *Builder) PrependString(str string) { + if b.needToGrow(len(str)) { + b.grow(len(str)) + } + b.start -= len(str) + copy(b.buf[b.start:], str) +} + +// PrependByte prepends the given byte to b's buffer. +func (b *Builder) PrependByte(c byte) { + if b.needToGrow(1) { + b.grow(1) + } + b.start-- + b.buf[b.start] = c +} + +// AppendString appends the given string to b's buffer. +func (b *Builder) AppendString(str string) { + if b.needToGrow(len(str)) { + b.grow(len(str)) + } + oldStart := b.start + b.start -= len(str) + copy(b.buf[b.start:], b.buf[oldStart:]) + copy(b.buf[len(b.buf)-len(str):], str) +} + +// String returns the accumulated string. No other methods should be called +// after String. +func (b *Builder) String() string { + return gohacks.StringFromImmutableBytes(b.buf[b.start:]) +} diff --git a/pkg/fspath/builder_test.go b/pkg/fspath/builder_test.go new file mode 100644 index 000000000..22f890273 --- /dev/null +++ b/pkg/fspath/builder_test.go @@ -0,0 +1,58 @@ +// Copyright 2019 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package fspath + +import ( + "testing" +) + +func TestBuilder(t *testing.T) { + type testCase struct { + pcs []string // path components in reverse order + after string + want string + } + tests := []testCase{ + { + // Empty case. + }, + { + pcs: []string{"foo"}, + want: "foo", + }, + { + pcs: []string{"foo", "bar", "baz"}, + want: "baz/bar/foo", + }, + { + pcs: []string{"foo", "bar"}, + after: " (deleted)", + want: "bar/foo (deleted)", + }, + } + + for _, test := range tests { + t.Run(test.want, func(t *testing.T) { + var b Builder + for _, pc := range test.pcs { + b.PrependComponent(pc) + } + b.AppendString(test.after) + if got := b.String(); got != test.want { + t.Errorf("got %q, wanted %q", got, test.want) + } + }) + } +} diff --git a/pkg/fspath/fspath.go b/pkg/fspath/fspath.go new file mode 100644 index 000000000..4c983d5fd --- /dev/null +++ b/pkg/fspath/fspath.go @@ -0,0 +1,187 @@ +// Copyright 2019 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// Package fspath provides efficient tools for working with file paths in +// Linux-compatible filesystem implementations. +package fspath + +import ( + "strings" +) + +const pathSep = '/' + +// Parse parses a pathname as described by path_resolution(7), except that +// empty pathnames will be parsed successfully to a Path for which +// Path.Absolute == Path.Dir == Path.HasComponents() == false. (This is +// necessary to support AT_EMPTY_PATH.) +func Parse(pathname string) Path { + if len(pathname) == 0 { + return Path{} + } + // Skip leading path separators. + i := 0 + for pathname[i] == pathSep { + i++ + if i == len(pathname) { + // pathname consists entirely of path separators. + return Path{ + Absolute: true, + Dir: true, + } + } + } + // Skip trailing path separators. This is required by Iterator.Next. This + // loop is guaranteed to terminate with j >= 0 because otherwise the + // pathname would consist entirely of path separators, so we would have + // returned above. + j := len(pathname) - 1 + for pathname[j] == pathSep { + j-- + } + // Find the end of the first path component. + firstEnd := i + 1 + for firstEnd != len(pathname) && pathname[firstEnd] != pathSep { + firstEnd++ + } + return Path{ + Begin: Iterator{ + partialPathname: pathname[i : j+1], + end: firstEnd - i, + }, + Absolute: i != 0, + Dir: j != len(pathname)-1, + } +} + +// Path contains the information contained in a pathname string. +// +// Path is copyable by value. The zero value for Path is equivalent to +// fspath.Parse(""), i.e. the empty path. +type Path struct { + // Begin is an iterator to the first path component in the relative part of + // the path. + // + // Path doesn't store information about path components after the first + // since this would require allocation. + Begin Iterator + + // If true, the path is absolute, such that lookup should begin at the + // filesystem root. If false, the path is relative, such that where lookup + // begins is unspecified. + Absolute bool + + // If true, the pathname contains trailing path separators, so the last + // path component must exist and resolve to a directory. + Dir bool +} + +// String returns a pathname string equivalent to p. Note that the returned +// string is not necessarily equal to the string p was parsed from; in +// particular, redundant path separators will not be present. +func (p Path) String() string { + var b strings.Builder + if p.Absolute { + b.WriteByte(pathSep) + } + sep := false + for pit := p.Begin; pit.Ok(); pit = pit.Next() { + if sep { + b.WriteByte(pathSep) + } + b.WriteString(pit.String()) + sep = true + } + // Don't return "//" for Parse("/"). + if p.Dir && p.Begin.Ok() { + b.WriteByte(pathSep) + } + return b.String() +} + +// HasComponents returns true if p contains a non-zero number of path +// components. +func (p Path) HasComponents() bool { + return p.Begin.Ok() +} + +// An Iterator represents either a path component in a Path or a terminal +// iterator indicating that the end of the path has been reached. +// +// Iterator is immutable and copyable by value. The zero value of Iterator is +// valid, and represents a terminal iterator. +type Iterator struct { + // partialPathname is a substring of the original pathname beginning at the + // start of the represented path component and ending immediately after the + // end of the last path component in the pathname. If partialPathname is + // empty, the PathnameIterator is terminal. + // + // See TestParseIteratorPartialPathnames in fspath_test.go for a worked + // example. + partialPathname string + + // end is the offset into partialPathname of the first byte after the end + // of the represented path component. + end int +} + +// Ok returns true if it is not terminal. +func (it Iterator) Ok() bool { + return len(it.partialPathname) != 0 +} + +// String returns the path component represented by it. +// +// Preconditions: it.Ok(). +func (it Iterator) String() string { + return it.partialPathname[:it.end] +} + +// Next returns an iterator to the path component after it. If it is the last +// component in the path, Next returns a terminal iterator. +// +// Preconditions: it.Ok(). +func (it Iterator) Next() Iterator { + if it.end == len(it.partialPathname) { + // End of the path. + return Iterator{} + } + // Skip path separators. Since Parse trims trailing path separators, if we + // aren't at the end of the path, there is definitely another path + // component. + i := it.end + 1 + for { + if it.partialPathname[i] != pathSep { + break + } + i++ + } + nextPartialPathname := it.partialPathname[i:] + // Find the end of this path component. + nextEnd := 1 + for nextEnd < len(nextPartialPathname) && nextPartialPathname[nextEnd] != pathSep { + nextEnd++ + } + return Iterator{ + partialPathname: nextPartialPathname, + end: nextEnd, + } +} + +// NextOk is equivalent to it.Next().Ok(), but is faster. +// +// Preconditions: it.Ok(). +func (it Iterator) NextOk() bool { + return it.end != len(it.partialPathname) +} diff --git a/pkg/fspath/fspath_test.go b/pkg/fspath/fspath_test.go new file mode 100644 index 000000000..d5e9a549a --- /dev/null +++ b/pkg/fspath/fspath_test.go @@ -0,0 +1,134 @@ +// Copyright 2019 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package fspath + +import ( + "reflect" + "strings" + "testing" +) + +func TestParseIteratorPartialPathnames(t *testing.T) { + path := Parse("/foo//bar///baz////") + // Parse strips leading slashes, and records their presence as + // Path.Absolute. + if !path.Absolute { + t.Errorf("Path.Absolute: got false, wanted true") + } + // Parse strips trailing slashes, and records their presence as Path.Dir. + if !path.Dir { + t.Errorf("Path.Dir: got false, wanted true") + } + // The first Iterator.partialPathname is the input pathname, with leading + // and trailing slashes stripped. + it := path.Begin + if want := "foo//bar///baz"; it.partialPathname != want { + t.Errorf("first Iterator.partialPathname: got %q, wanted %q", it.partialPathname, want) + } + // Successive Iterator.partialPathnames remove the leading path component + // and following slashes, until we run out of path components and get a + // terminal Iterator. + it = it.Next() + if want := "bar///baz"; it.partialPathname != want { + t.Errorf("second Iterator.partialPathname: got %q, wanted %q", it.partialPathname, want) + } + it = it.Next() + if want := "baz"; it.partialPathname != want { + t.Errorf("third Iterator.partialPathname: got %q, wanted %q", it.partialPathname, want) + } + it = it.Next() + if want := ""; it.partialPathname != want { + t.Errorf("fourth Iterator.partialPathname: got %q, wanted %q", it.partialPathname, want) + } + if it.Ok() { + t.Errorf("fourth Iterator.Ok(): got true, wanted false") + } +} + +func TestParse(t *testing.T) { + type testCase struct { + pathname string + relpath []string + abs bool + dir bool + } + tests := []testCase{ + { + pathname: "", + relpath: []string{}, + abs: false, + dir: false, + }, + { + pathname: "/", + relpath: []string{}, + abs: true, + dir: true, + }, + { + pathname: "//", + relpath: []string{}, + abs: true, + dir: true, + }, + } + for _, sep := range []string{"/", "//"} { + for _, abs := range []bool{false, true} { + for _, dir := range []bool{false, true} { + for _, pcs := range [][]string{ + // single path component + {"foo"}, + // multiple path components, including non-UTF-8 + {".", "foo", "..", "\xe6", "bar"}, + } { + prefix := "" + if abs { + prefix = sep + } + suffix := "" + if dir { + suffix = sep + } + tests = append(tests, testCase{ + pathname: prefix + strings.Join(pcs, sep) + suffix, + relpath: pcs, + abs: abs, + dir: dir, + }) + } + } + } + } + + for _, test := range tests { + t.Run(test.pathname, func(t *testing.T) { + p := Parse(test.pathname) + t.Logf("pathname %q => path %q", test.pathname, p) + if p.Absolute != test.abs { + t.Errorf("path absoluteness: got %v, wanted %v", p.Absolute, test.abs) + } + if p.Dir != test.dir { + t.Errorf("path must resolve to a directory: got %v, wanted %v", p.Dir, test.dir) + } + pcs := []string{} + for pit := p.Begin; pit.Ok(); pit = pit.Next() { + pcs = append(pcs, pit.String()) + } + if !reflect.DeepEqual(pcs, test.relpath) { + t.Errorf("relative path: got %v, wanted %v", pcs, test.relpath) + } + }) + } +} |