When I search backward in w3m by using the '?' command, the program
freezes with high CPU usage for a bit of time if the found text is near
the end of a very long line.

How to reproduce the issue:

    printf 'first line\nsecond line is %*s a long line\nthird line\n' 10000 '' > test.txt
    w3m test.txt

Run those commands and then go to the third line and search backward for
the word "line".  Now the program will freeze for a second.  If you
increase the number 10000, the freezing time will increase with the
square of that number.

The reason that this happens when searching backward but not forward is
that in the function `backwardSearch` in search.c there is this loop:

    while (regexMatch(...) == 1)

but in `forwardSearch` it's just an if statement:

    if (regexMatch(...) == 1)

That means that when searching backward, we do one regexMatch for each
character on the line and since the regexMatch itself already searches
through the characters, that's pretty wasteful and that's what gives us
the squared times.

It should be possible to change this so that an if statement is used in
`backwardSearch` just like in `forwardSearch`.  Maybe there could be two
versions of `regexMatch` where one of them searches backwards or just
returns the last match instead of the first one so that we don't have to
call it in a loop.

[Resending my mail from 2023-04-11 as it does not appear in the Debian
BTS. With help from #debian-admin I learned the my local part (mail@) in
my From: was the problem. My mails went to /dev/null or somewhere. :-(
Apologies for any inconveniences.]



Hi Robert,

Thanks for the detailed bug report!

[Snip repro steps]

This does not work as we are searching backwards and need the last
match, not the first.

This would be the ideal solution, of course - but also not a trivial
one. As a workaround we can change the function to not proceed char by
char, but to skip past the end of the last match. This will of course
not help if nearly the whole line matches.

See my patch below (I also refactored backwardSearch to remove a lot of
duplicated code).


We need to search the whole line up to the position we are at to find
the first match from the end. If we have a match we know its end and can
skip past it. This makes searching very long strings way more efficient.

While there, refactor the whole function.
---
 search.c |  104 ++++++++++++++++++++++++++-------------------------------------
 1 file changed, 44 insertions(+), 60 deletions(-)
--- a/search.c
+++ b/search.c
@@ -220,7 +220,7 @@ backwardSearch(Buffer *buf, char *str)
 	while (l->bpos && l->prev)
 	    l = l->prev;
     }
-    begin = l;
+
     if (pos > 0) {
 	pos--;
 #ifdef USE_M17N
@@ -228,80 +228,64 @@ backwardSearch(Buffer *buf, char *str)
 	    pos--;
 #endif
 	p = &l->lineBuf[pos];
-	found = NULL;
-	found_last = NULL;
+    }
+    else {
+	if (!(l = l->prev)) {
+	    if (!WrapSearch)
+		return SR_NOTFOUND;
+	    l = buf->lastLine;
+	}
+	p = &l->lineBuf[l->size];
+    }
+
+    begin = l;
+    found = NULL;
+    found_last = NULL;
+
+    while (1) {
 	q = l->lineBuf;
+	/*
+	 * Search as long as we have matches on the current line.
+	 * We are searching the line from begin to end. As we are searching
+	 * backwards we want the last match on the line.
+	 */
 	while (regexMatch(q, &l->lineBuf[l->size] - q, q == l->lineBuf) == 1) {
 	    matchedPosition(&first, &last);
 	    if (first <= p) {
 		found = first;
 		found_last = last;
 	    }
-	    if (q - l->lineBuf >= l->size)
-		break;
-	    q++;
+	    q = last;
 #ifdef USE_M17N
 	    while (q - l->lineBuf < l->size
 		   && l->propBuf[q - l->lineBuf] & PC_WCHAR2)
 		q++;
 #endif
-	    if (q > p)
+	    if (q >= p)
 		break;
 	}
-	if (found) {
-	    pos = found - l->lineBuf;
-	    while (pos >= l->len && l->next && l->next->bpos) {
-		pos -= l->len;
-		l = l->next;
-	    }
-	    buf->pos = pos;
-	    if (l != buf->currentLine)
-		gotoLine(buf, l->linenumber);
-	    arrangeCursor(buf);
-	    set_mark(l, pos, pos + found_last - found);
-	    return SR_FOUND;
+
+	if (found)
+	    break;
+
+	if (!(l = l->prev)) {
+	    if (!WrapSearch)
+		return SR_NOTFOUND;
+	    l = buf->lastLine;
 	}
+	if (l == begin)	/* no match */
+	    return SR_NOTFOUND;;
     }
-    for (l = l->prev;; l = l->prev) {
-	if (l == NULL) {
-	    if (WrapSearch) {
-		l = buf->lastLine;
-		wrapped = TRUE;
-	    }
-	    else {
-		break;
-	    }
-	}
-	found = NULL;
-	found_last = NULL;
-	q = l->lineBuf;
-	while (regexMatch(q, &l->lineBuf[l->size] - q, q == l->lineBuf) == 1) {
-	    matchedPosition(&first, &last);
-	    found = first;
-	    found_last = last;
-	    if (q - l->lineBuf >= l->size)
-		break;
-	    q++;
-#ifdef USE_M17N
-	    while (q - l->lineBuf < l->size
-		   && l->propBuf[q - l->lineBuf] & PC_WCHAR2)
-		q++;
-#endif
-	}
-	if (found) {
-	    pos = found - l->lineBuf;
-	    while (pos >= l->len && l->next && l->next->bpos) {
-		pos -= l->len;
-		l = l->next;
-	    }
-	    buf->pos = pos;
-	    gotoLine(buf, l->linenumber);
-	    arrangeCursor(buf);
-	    set_mark(l, pos, pos + found_last - found);
-	    return SR_FOUND | (wrapped ? SR_WRAPPED : 0);
-	}
-	if (wrapped && l == begin)	/* no match */
-	    break;
+
+    pos = found - l->lineBuf;
+    while (pos >= l->len && l->next && l->next->bpos) {
+	pos -= l->len;
+	l = l->next;
     }
-    return SR_NOTFOUND;
+    buf->pos = pos;
+    if (l != buf->currentLine)
+	gotoLine(buf, l->linenumber);
+    arrangeCursor(buf);
+    set_mark(l, pos, pos + found_last - found);
+    return SR_FOUND | (wrapped ? SR_WRAPPED : 0);
 }