Re: Possible problem with looking-back function

[Stefan Monnier <monnier@iro.umontreal.ca>]

>>> Shouldn't it return 1?

Not according to the docstring:

   If GREEDY is non-nil, extend the match backwards as far as
   possible, stopping when a single additional previous character
   cannot be part of a match for REGEXP.  When the match is
   extended, its starting position is allowed to occur before
   LIMIT.

>> The algorithm searches backward until it finds a position from which there
>> is a match that extends to point.  Doing more would be quadratic

Actually our regexp matcher (i.e. "looking-at") is already much worse
than quadratic in worst-case complexity.

> AFAIK exists a bug, resp. missing implementation in re-search-backward.

Ignoring back-references, our regexps are pretty much within the
"regular language" domain, so in theory matching and searching can be
performed in linear time.  But our regexp engine uses a backtracking
implementation, so it's not even close to linear.  And the "backward"
matcher is not implemented, so we "simulate" it with a forward matcher,
which is why looking-back is slow and doesn't behave like we want.


        Stefan