[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Possible problem with looking-back function
From: |
Stefan Monnier |
Subject: |
Re: Possible problem with looking-back function |
Date: |
Thu, 19 Aug 2010 10:01:53 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) |
>>> 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