Merge "websocket: avoid panic from invalid websocket requests"
diff --git a/lib/glob/glob.go b/lib/glob/glob.go
index 6f0ac86..d7fa168 100644
--- a/lib/glob/glob.go
+++ b/lib/glob/glob.go
@@ -22,24 +22,174 @@
package glob
import (
- "path/filepath"
+ "path"
"strings"
)
-// Glob represents a slash separated path glob expression.
+// Glob represents a slash separated path glob pattern.
type Glob struct {
- elems []string
+ elems []*Element
recursive bool
restricted bool
}
-func parseElem(pattern string) error {
- if len(pattern) == 0 {
- return filepath.ErrBadPattern
+// Parse returns a new Glob.
+func Parse(pattern string) (*Glob, error) {
+ if len(pattern) > 0 && pattern[0] == '/' {
+ return nil, path.ErrBadPattern
+ }
+
+ g := &Glob{}
+ if pattern == "" {
+ return g, nil
+ }
+
+ elems := strings.Split(pattern, "/")
+ if last := len(elems) - 1; last >= 0 {
+ if elems[last] == "..." {
+ elems = elems[:last]
+ g.recursive = true
+ } else if elems[last] == "***" {
+ elems = elems[:last]
+ g.recursive = true
+ g.restricted = true
+ }
+ }
+ g.elems = make([]*Element, len(elems))
+ for i, elem := range elems {
+ g.elems[i] = &Element{pattern: elem}
+ if err := g.elems[i].validate(); err != nil {
+ return nil, err
+ }
+ }
+
+ return g, nil
+}
+
+// Len returns the number of path elements represented by the glob expression.
+func (g *Glob) Len() int {
+ return len(g.elems)
+}
+
+// Empty returns true if the pattern cannot match anything.
+func (g *Glob) Empty() bool {
+ return !g.recursive && len(g.elems) == 0
+}
+
+// Recursive returns true if the pattern is recursive.
+func (g *Glob) Recursive() bool {
+ return g.recursive
+}
+
+// Restricted returns true if recursion is restricted (up to the caller to
+// know what that means).
+func (g *Glob) Restricted() bool {
+ return g.restricted
+}
+
+// Tail returns the suffix of g starting at the second element.
+func (g *Glob) Tail() *Glob {
+ if len(g.elems) <= 1 {
+ return &Glob{elems: nil, recursive: g.recursive, restricted: g.restricted}
+ }
+ return &Glob{elems: g.elems[1:], recursive: g.recursive, restricted: g.restricted}
+}
+
+// Head returns an Element for the first element of the glob pattern.
+func (g *Glob) Head() *Element {
+ if len(g.elems) == 0 {
+ if g.recursive {
+ return &Element{alwaysMatch: true}
+ }
+ return &Element{neverMatch: true}
+ }
+ return g.elems[0]
+}
+
+// SplitFixedElements returns the part of the glob pattern that contains only
+// fixed elements, and the glob that follows it.
+func (g *Glob) SplitFixedElements() ([]string, *Glob) {
+ var prefix []string
+ tail := g
+ for _, elem := range g.elems {
+ if pfx, fixed := elem.FixedPrefix(); fixed {
+ prefix = append(prefix, pfx)
+ tail = tail.Tail()
+ } else {
+ break
+ }
+ }
+ return prefix, tail
+}
+
+// String returns the string representation of the glob pattern.
+func (g *Glob) String() string {
+ elems := make([]string, len(g.elems))
+ for i, e := range g.elems {
+ elems[i] = e.pattern
+ }
+ if g.recursive {
+ if g.restricted {
+ elems = append(elems, "***")
+ } else {
+ elems = append(elems, "...")
+ }
+ }
+ return path.Join(elems...)
+}
+
+// Element represents a single element of a glob pattern.
+type Element struct {
+ pattern string
+ alwaysMatch bool
+ neverMatch bool
+}
+
+// Match returns true iff this pattern element matches the given segment.
+func (m *Element) Match(segment string) bool {
+ if m.neverMatch {
+ return false
+ }
+ if m.alwaysMatch {
+ return true
+ }
+ matches, err := path.Match(m.pattern, segment)
+ return err == nil && matches
+}
+
+// FixedPrefix returns the unescaped fixed part of the pattern, and whether the
+// prefix is the whole pattern. The fixed part does not contain any wildcards.
+func (m *Element) FixedPrefix() (string, bool) {
+ if m.neverMatch {
+ return "", true
+ }
+ if m.alwaysMatch {
+ return "", false
+ }
+ unescaped := ""
+ escape := false
+ for _, c := range m.pattern {
+ if escape {
+ escape = false
+ unescaped += string(c)
+ } else if strings.ContainsRune("*?[", c) {
+ return unescaped, false
+ } else if c == '\\' {
+ escape = true
+ } else {
+ unescaped += string(c)
+ }
+ }
+ return unescaped, true
+}
+
+func (m *Element) validate() error {
+ if len(m.pattern) == 0 {
+ return path.ErrBadPattern
}
escape := false
inrange := false
- for _, c := range pattern {
+ for _, c := range m.pattern {
if escape {
escape = false
continue
@@ -55,68 +205,22 @@
}
// If we are in the middle of an escape or character range, the expression is incomplete.
if escape || inrange {
- return filepath.ErrBadPattern
+ return path.ErrBadPattern
}
return nil
}
-// Parse returns a new Glob.
-func Parse(pattern string) (*Glob, error) {
- if len(pattern) > 0 && pattern[0] == '/' {
- return nil, filepath.ErrBadPattern
- }
-
- g := &Glob{}
- if pattern != "" {
- g.elems = strings.Split(pattern, "/")
- }
- if last := len(g.elems) - 1; last >= 0 {
- if g.elems[last] == "..." {
- g.elems = g.elems[:last]
- g.recursive = true
- } else if g.elems[last] == "***" {
- g.elems = g.elems[:last]
- g.recursive = true
- g.restricted = true
- }
- }
-
- // The only error we can get from the filepath library is badpattern.
- // A future implementation would most likely recognize that here, so for now
- // I'll just check every part to make sure it's error free.
- // Note: Match never returns an error when matching against an empty string.
- for _, elem := range g.elems {
- if err := parseElem(elem); err != nil {
- return nil, err
- }
- }
-
- return g, nil
-}
-
-// Len returns the number of path elements represented by the glob expression.
-func (g *Glob) Len() int {
- return len(g.elems)
-}
+// DEPRECATED CODE
// Finished returns true if the pattern cannot match anything.
+// This method is DEPRECATED.
func (g *Glob) Finished() bool {
- return !g.recursive && len(g.elems) == 0
-}
-
-// Recursive returns true if the pattern is recursive.
-func (g *Glob) Recursive() bool {
- return g.recursive
-}
-
-// Restricted returns true if recursion is restricted (up to the caller to
-// know what that means).
-func (g *Glob) Restricted() bool {
- return g.restricted
+ return g.Empty()
}
// Split returns the suffix of g starting at the path element corresponding to
// start.
+// This method is DEPRECATED.
func (g *Glob) Split(start int) *Glob {
if start >= len(g.elems) {
return &Glob{elems: nil, recursive: g.recursive, restricted: g.restricted}
@@ -129,22 +233,13 @@
// matched, a boolean indicating whether the match was successful;
// exact, a boolean indicating whether segment matched a fixed string pattern;
// remainder, a Glob representing the unmatched remainder of g.
+// This method is DEPRECATED.
func (g *Glob) MatchInitialSegment(segment string) (matched bool, exact bool, remainder *Glob) {
- if len(g.elems) == 0 {
- if !g.recursive {
- return false, false, nil
- }
- // The segment matches "...". This is not an exact match.
- return true, false, g
- }
-
- if matches, err := filepath.Match(g.elems[0], segment); err != nil {
- return false, false, nil
- } else if matches {
- _, fixed := isFixed(g.elems[0])
- return true, fixed, g.Split(1)
- }
- return false, false, nil
+ m := g.Head()
+ matched = m.Match(segment)
+ _, exact = m.FixedPrefix()
+ remainder = g.Tail()
+ return
}
// PartialMatch tries matching elems against part of a glob pattern.
@@ -158,6 +253,7 @@
//
// Note that if the glob is recursive elems can have more elements then
// the glob pattern and still get a true result.
+// This method is DEPRECATED.
func (g *Glob) PartialMatch(start int, elems []string) (matched bool, exact bool, remainder *Glob) {
g = g.Split(start)
allExact := true
@@ -172,57 +268,9 @@
return true, allExact, g
}
-// isFixed returns the unescaped string and true if 's' is a pattern specifying
-// a fixed string. Otherwise it returns the original string and false.
-func isFixed(s string) (string, bool) {
- // No special characters.
- if !strings.ContainsAny(s, "*?[") {
- return s, true
- }
- // Special characters and no backslash.
- if !strings.ContainsAny(s, "\\") {
- return "", false
- }
- unescaped := ""
- escape := false
- for _, c := range s {
- if escape {
- escape = false
- unescaped += string(c)
- } else if strings.ContainsRune("*?[", c) {
- // S contains an unescaped special character.
- return s, false
- } else if c == '\\' {
- escape = true
- } else {
- unescaped += string(c)
- }
- }
- return unescaped, true
-}
-
+// SplitFixedPrefix returns the part of the glob pattern that contains only
+// fixed elements, and the glob that follows it.
+// This method is DEPRECATED.
func (g *Glob) SplitFixedPrefix() ([]string, *Glob) {
- var prefix []string
- start := 0
- for _, elem := range g.elems {
- if u, q := isFixed(elem); q {
- prefix = append(prefix, u)
- start++
- } else {
- break
- }
- }
- return prefix, g.Split(start)
-}
-
-func (g *Glob) String() string {
- e := g.elems
- if g.recursive {
- if g.restricted {
- e = append(e, "***")
- } else {
- e = append(e, "...")
- }
- }
- return filepath.Join(e...)
+ return g.SplitFixedElements()
}
diff --git a/lib/glob/glob_test.go b/lib/glob/glob_test.go
index 2b8aea3..e75be4f 100644
--- a/lib/glob/glob_test.go
+++ b/lib/glob/glob_test.go
@@ -20,7 +20,7 @@
return true
}
-func TestStripFixedPrefix(t *testing.T) {
+func TestStripFixedElements(t *testing.T) {
tests := []struct {
pattern string
fixed []string
@@ -37,8 +37,107 @@
if err != nil {
t.Fatalf("parsing %q: %q", test.pattern, err.Error())
}
- if f, ng := g.SplitFixedPrefix(); !same(f, test.fixed) || test.rest != ng.String() {
- t.Fatalf("SplitFixedPrefix(%q) got %q,%q, expected %q,%q", test.pattern, f, ng.String(), test.fixed, test.rest)
+ if f, ng := g.SplitFixedElements(); !same(f, test.fixed) || test.rest != ng.String() {
+ t.Fatalf("SplitFixedElements(%q) got %q,%q, expected %q,%q", test.pattern, f, ng.String(), test.fixed, test.rest)
+ }
+ }
+}
+
+func TestMatch(t *testing.T) {
+ tests := []struct {
+ pattern string
+ name string
+ matched bool
+ }{
+ {"...", "", true},
+ {"***", "", true},
+ {"...", "a", true},
+ {"***", "a", true},
+ {"a", "", false},
+ {"a", "a", true},
+ {"a", "b", false},
+ {"a*", "a", true},
+ {"a*", "b", false},
+ {"a*b", "ab", true},
+ {"a*b", "afoob", true},
+ {"a\\*", "a", false},
+ {"a\\*", "a*", true},
+ {"\\\\", "\\", true},
+ {"?", "?", true},
+ {"?", "a", true},
+ {"?", "", false},
+ {"*?", "", false},
+ {"*?", "a", true},
+ {"*?", "ab", true},
+ {"*?", "abv", true},
+ {"[abc]", "a", true},
+ {"[abc]", "b", true},
+ {"[abc]", "c", true},
+ {"[abc]", "d", false},
+ {"[a-c]", "a", true},
+ {"[a-c]", "b", true},
+ {"[a-c]", "c", true},
+ {"[a-c]", "d", false},
+ {"\\[abc]", "a", false},
+ {"\\[abc]", "[abc]", true},
+ {"a/*", "a", true},
+ {"a/*", "b", false},
+ {"a/...", "a", true},
+ {"a/...", "b", false},
+ }
+ for i, test := range tests {
+ g, err := Parse(test.pattern)
+ if err != nil {
+ t.Errorf("unexpected parsing error for %q (#%d): %v", test.pattern, i, err)
+ continue
+ }
+ if matched := g.Head().Match(test.name); matched != test.matched {
+ t.Errorf("unexpected result for %q.Match(%q) (#%d). Got %v, expected %v", test.pattern, test.name, i, matched, test.matched)
+ }
+ }
+}
+
+func TestFixedPrefix(t *testing.T) {
+ tests := []struct {
+ pattern string
+ prefix string
+ full bool
+ }{
+ {"", "", true},
+ {"...", "", false},
+ {"***", "", false},
+ {"...", "", false},
+ {"***", "", false},
+ {"a", "a", true},
+ {"*a", "", false},
+ {"a*", "a", false},
+ {"a*b", "a", false},
+ {"a\\*", "a*", true},
+ {"\\\\", "\\", true},
+ {"?", "", false},
+ {"\\?", "?", true},
+ {"*?", "", false},
+ {"[abc]", "", false},
+ {"\\[abc]", "[abc]", true},
+ {"\\[abc]*", "[abc]", false},
+ }
+ for i, test := range tests {
+ g, err := Parse(test.pattern)
+ if err != nil {
+ t.Errorf("unexpected parsing error for %q (#%d): %v", test.pattern, i, err)
+ continue
+ }
+ if prefix, full := g.Head().FixedPrefix(); prefix != test.prefix || full != test.full {
+ t.Errorf("unexpected result for %q.FixedPrefix() (#%d). Got (%q,%v), expected (%q,%v)", test.pattern, i, prefix, full, test.prefix, test.full)
+ }
+ }
+}
+
+func TestBadPattern(t *testing.T) {
+ tests := []string{"[", "[foo", "[^foo", "\\", "a\\", "abc[foo", "a//b"}
+ for _, test := range tests {
+ if _, err := Parse(test); err == nil {
+ t.Errorf("Unexpected success for %q", test)
}
}
}
@@ -107,12 +206,3 @@
}
}
}
-
-func TestBadPattern(t *testing.T) {
- tests := []string{"[", "[foo", "[^foo", "\\", "a\\", "abc[foo", "a//b"}
- for _, test := range tests {
- if _, err := Parse(test); err == nil {
- t.Errorf("Unexpected success for %q", test)
- }
- }
-}
diff --git a/lib/stats/glob.go b/lib/stats/glob.go
index bcb2997..c846f79 100644
--- a/lib/stats/glob.go
+++ b/lib/stats/glob.go
@@ -51,11 +51,12 @@
*result = append(*result, KeyValue{prefix, v})
}
}
- if g.Finished() {
+ if g.Empty() {
return
}
+ matcher, left := g.Head(), g.Tail()
for name, child := range n.children {
- if ok, _, left := g.MatchInitialSegment(name); ok {
+ if matcher.Match(name) {
globStepLocked(path.Join(prefix, name), left, child, updatedSince, includeValues, result)
}
}
diff --git a/runtime/internal/naming/namespace/glob.go b/runtime/internal/naming/namespace/glob.go
index 6e334a2..2e33bf8 100644
--- a/runtime/internal/naming/namespace/glob.go
+++ b/runtime/internal/naming/namespace/glob.go
@@ -196,7 +196,10 @@
}
// Get the pattern elements below the current path.
- suffix := pattern.Split(depth(t.me.Name))
+ suffix := pattern
+ for i := depth(t.me.Name) - 1; i >= 0; i-- {
+ suffix = suffix.Tail()
+ }
// If we've satisfied the request and this isn't the root,
// reply to the caller.
@@ -210,7 +213,7 @@
// remote server) and the server is not another MT, then we needn't send the
// query on since we know the server will not supply a new address for the
// current name.
- if suffix.Finished() {
+ if suffix.Empty() {
if !t.me.ServesMountTable {
continue
}
diff --git a/runtime/internal/rpc/reserved.go b/runtime/internal/rpc/reserved.go
index 5662edc..31eb4e8 100644
--- a/runtime/internal/rpc/reserved.go
+++ b/runtime/internal/rpc/reserved.go
@@ -320,12 +320,13 @@
if state.glob.Len() == 0 {
depth++
}
+ matcher, left := state.glob.Head(), state.glob.Tail()
for child := range children {
if len(child) == 0 || strings.Contains(child, "/") {
ctx.Errorf("rpc Glob: %q.GlobChildren__() sent an invalid child name: %q", suffix, child)
continue
}
- if ok, _, left := state.glob.MatchInitialSegment(child); ok {
+ if matcher.Match(child) {
next := naming.Join(state.name, child)
queue = append(queue, gState{next, left, depth})
}
diff --git a/runtime/internal/rpc/test/glob_test.go b/runtime/internal/rpc/test/glob_test.go
index 3d00d7b..9bc312f 100644
--- a/runtime/internal/rpc/test/glob_test.go
+++ b/runtime/internal/rpc/test/glob_test.go
@@ -305,11 +305,12 @@
if g.Len() == 0 {
ch <- naming.GlobReplyEntry{naming.MountEntry{Name: name}}
}
- if g.Finished() {
+ if g.Empty() {
return
}
+ matcher, left := g.Head(), g.Tail()
for leaf, child := range n.children {
- if ok, _, left := g.MatchInitialSegment(leaf); ok {
+ if matcher.Match(leaf) {
o.globLoop(ch, naming.Join(name, leaf), left, child)
}
}
diff --git a/services/debug/debug/impl.go b/services/debug/debug/impl.go
index a35a70b..d2e1fcb 100644
--- a/services/debug/debug/impl.go
+++ b/services/debug/debug/impl.go
@@ -401,7 +401,7 @@
return
}
var prefixElems []string
- prefixElems, g = g.SplitFixedPrefix()
+ prefixElems, g = g.SplitFixedElements()
name := naming.Join(prefixElems...)
if len(root) != 0 {
name = naming.JoinAddressName(root, name)
diff --git a/services/mounttable/mounttablelib/mounttable.go b/services/mounttable/mounttablelib/mounttable.go
index 7dbb898..555431f 100644
--- a/services/mounttable/mounttablelib/mounttable.go
+++ b/services/mounttable/mounttablelib/mounttable.go
@@ -678,7 +678,7 @@
return
}
- if !pattern.Finished() {
+ if !pattern.Empty() {
// We can only list children to whom we have some access AND either
// - we have Read or Admin access to the directory or
// - we have Resolve or Create access to the directory and the
@@ -687,7 +687,7 @@
if err := n.satisfies(mt, ctx, call, traverseTags); err != nil {
goto out
}
- fixed, _ := pattern.SplitFixedPrefix()
+ fixed, _ := pattern.SplitFixedElements()
if len(fixed) == 0 {
goto out
}
@@ -702,9 +702,10 @@
n.parent.Unlock()
// Recurse through the children.
+ matcher, suffix := pattern.Head(), pattern.Tail()
for k, c := range children {
// At this point, n lock is held.
- if ok, _, suffix := pattern.MatchInitialSegment(k); ok {
+ if matcher.Match(k) {
c.Lock()
// If child allows any access show it. Otherwise, skip.
if err := c.satisfies(mt, ctx, call, allTags); err != nil {
diff --git a/services/mounttable/mounttablelib/neighborhood.go b/services/mounttable/mounttablelib/neighborhood.go
index 8939dcd..afdd11e 100644
--- a/services/mounttable/mounttablelib/neighborhood.go
+++ b/services/mounttable/mounttablelib/neighborhood.go
@@ -282,11 +282,11 @@
ch := make(chan naming.GlobReply)
go func() {
defer close(ch)
+ matcher := g.Head()
for k, n := range nh.neighbors() {
- if ok, _, _ := g.MatchInitialSegment(k); !ok {
- continue
+ if matcher.Match(k) {
+ ch <- naming.GlobReplyEntry{naming.MountEntry{Name: k, Servers: n, ServesMountTable: true}}
}
- ch <- naming.GlobReplyEntry{naming.MountEntry{Name: k, Servers: n, ServesMountTable: true}}
}
}()
return ch, nil
