On Mon, 28 Jan 2013 19:46:13 +0100, Richard Hipp <[email protected]> wrote:
On Mon, Jan 28, 2013 at 1:40 PM, Joerg Sonnenberger
<[email protected]
wrote:
You don't understand me. Anchoring helps, if you can use it to avoid
initial wild cards or limit the length of backtracking. It doesn't help
to avoid the exponential edge cases with .*foo patterns though.
I think another point is that the Lua regexp does not do anchoring (or at
least I didn't see it - did I miss something?)
you mean in the pattern syntax? then
see, e.g., here: http://www.lua.org/pil/20.2.html and search for "anchor":
lua uses the same syntax as standard regexp for this, e.g.
"^.*foo" means "search for anything at beginning of line followed by foo"
FWIW, the regexp.c code already present in Fossil does not need anchoring
to avoid exponential blowup, since it uses an NFA. However, it does use
anchoring as a performance optimization, to avoid running the NFA over
every byte of input text. The NFA is linear in the size of input, but
the
constant of proportionality is large relative to memcmp() so we like to
use
memcmp()-based anchoring to avoid having the NFA look at every single
byte
of input.
--
Using Opera's revolutionary email client: http://www.opera.com/mail/
_______________________________________________
fossil-users mailing list
[email protected]
http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
