rust-lang/glob — pull request #18 by blaenk (2014-12-29 00:19:23+00:00)
Title: enables recursive patterns when globbing

The current globbing algorithm splits the glob pattern based on the path
separator, which makes recursive wildcards `**` essentially act like `*`
as they're only matching on a single path component.

This commit enables recursive wildcards when globbing by following a
pretty simple algorithm. I tried to make the implementation as simple as
possible within the current globbing mechanism.

1. if the current pattern is recursive (contains a `**`) and it's not
the last pattern:
1. find the next non-recursive pattern, essentially collapsing
consecutive recursive patterns. This is already done when
parsing the `Pattern`, but it has to be done again for the
current globbing algorithm since the `Pattern` is
constructed from a single path component, thereby losing
out on the context of consecutive recursive wildcards.
2. if there are no other non-recursive patterns, then
accept this and all remaining recursive paths
3. else if the next non-recursive pattern matches, accept
this and proceed to the pattern after the next non-recursive
pattern
4. else: accept this on the basis of the current recursive
wildcard and remain on this pattern
2. else if it's recursive and it's the last pattern:
accept this and all remaining recursive patterns
3. else: continue matching as was done before this commit

This algorithm necessitates an `is_recursive` field (and accompanying
accessor method) on `Pattern` to cheaply determine if a `Pattern`
contains an `AnyRecursiveSequence` token. This field is turned on
when an `AnyRecursiveSequence` token is parsed, and serves to avoid
the performance penalty of having to traverse the entire vector of
tokens to determine if such a token exists.

This field isn't crucial though, and we could search the vector if
we would rather not add this field.

This commit places the restriction that a recursive wildstar should
form a _single_ path component, i.e. `a/**/b` would be valid but not
`a**/b` or `a/**b`. This restriction is also present in Python and
serves to simplify the matching semantics. Such invalid sequences
are treated literally in this implementation. For comparison,
Python throws an exception and Ruby seems to treat it as a single
wildcard.

Test coverage of recursive wildcards was also improved significantly.