Re: (info-stnd) search.c:regexp_search() finishes too early

[Gavin Smith]

On Thu, Jan 9, 2014 at 9:53 PM, Sergey Poznyakoff <address@hidden> wrote:
> Hi Gavin,
>
> Thanks a lot for the report and the testcase.  I have fixed the bug
> in the repository.  For your convenience, the patch is attached.
> Please let me know if it works for you.
>
> Regards,
> Sergey
>
I am having some problems using this on long files or files with a lot
of matches. I am trying to find cross-references or menu items in
files. I have a split Texinfo manual installed and whenever I open the
subfile including the indices it takes several minutes to do so,
because its indices have thousands of entries. These lines were added:

+  if (previous_content != binding->buffer ||
+      previous_start != start ||
+      previous_end != end)

>From what I can tell, anytime anything changes in the binding
argument, all the work done by the last call to regexp_search() is
thrown away. This includes the common case of keeping binding->buffer
and binding->end constant and continually increasing binding->start.
If as I suspect it is calculating all the matches every time, instead
of just the first one, looping through all the matches is quadratic in
the number of matches (i.e., for n matches, it would calculate n +
(n-1) + (n-2) + ... + 2 + 1 matches).