lib/glob: Clean up the glob library
Refactored the glob library to expose a new Element object that can
be used to match one path segment at a time.
Deprecated MatchInitialSegment() in favor of Head() and Tail().
Deprecated PartialMatch().
Deprecated Finished() in favor of Empty().
Deprecated Split() in favor of Tail().
Deprecated SplitFixedPrefix() in favor of SplitFixedElements().
Partly addresses: v.io/i/532
Change-Id: Ia94c958fb8415fc36a123887626c5d377806170f
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)
- }
- }
-}
