> Good point, but it is an ambiguity that is easily resolved simply by saying
> glob patterns have to implement greedy matching when variables are used.
I implemented a mostly-linear time glob algorithm by implementing
minimal matching left-to-right. I am opposed to any semantic that would
result in pattern matching being fairly expensive (specifically, any
algorithm that results in * being recursive is bad).
I'm fairly sure that the greediness or non-greediness of the match doesn't
have to affect the efficiency of the operation. I've written both greedy
and non-greedy pattern matchers, and I believe all of them exhibit the
same sort of mostly-linear never-exponential behavior you describe.
(The trick I used in the greedy case, FWIW, is to scan the remainder of the
pattern and back off the initial match so it doesn't cover material needed to
satisfy the rest of the pattern.)
If I had done minimal-matching right-to-left, would the result have been
greedy? (This would resolve my objection.)
I don't think so. I think you have to tweak your approach.
Let me know if this doesn't make sense; I'm not an expert on this.
The reason I prefer a greedy match is that it seems to be what most people have
come to expect. Capturing globs and regexps tend to be greedy by default.
Ned