Remapping | Is ** greedy or lazy?

[sloretz]

The remapping design doc does not state whether ** is greedy or lazy. This can change the outcome of some remap rules.

Example:

• rule /**/foo/**:=/\1/\2
• name /foo/bar/foo/bar

If ** is greedy the output name is /foo/bar.

If ** is lazy the output name is /bar/foo/bar

Arguments for Greedy

Name matching with wild cards is similar to regular expression matching. In perl syntax the quantifiers *, +, ? are greedy by default. Since so many regular expression libraries have been based off this syntax, a user might expect ** to be greedy too.

Arguments for lazy

A lazy operator can reduce the amount of backtracking an implementation has to do while matching. If given rule /**/foo/bar/baz:=... and name /foo/bar/baz a greedy ** would backtrack after every token, while a lazy ** would result in no backtracking at all.

Proposal

** should be greedy by default. In most cases remapping will only happen at startup, so the performance does not matter.

If the performance of backtracking becomes an issue then the syntax could be amended to allow changing the greediness. Perl does this with ? where * is greedy while *? is lazy. Ex: ** could be greedy while **? is lazy.