develooper Front page | perl.perl5.porters | Postings from May 2000

[PATCH 5.6.0] buglet in REx optimizer

From:
Ilya Zakharevich
Date:
May 8, 2000 15:18
Subject:
[PATCH 5.6.0] buglet in REx optimizer
Message ID:
20000508181835.A15444@monk.mps.ohio-state.edu
The REx optimizer contained an enourmous pessimization (which in very
rare cases could make things very slow).  The patch adds a little bit
of comments, and fixes this (on the first edited line).

It also

  a) hides (but not removes!) the REx segfault bug discussed pn p5p
     right now;

  b) In yet-more rare cases (like one discussed in the bug reports
     above) the search still can be quadratic (though with much better
     constant than before).

Enjoy,
Ilya

--- ./regexec.c.sent2	Mon May  8 17:23:26 2000
+++ ./regexec.c	Mon May  8 18:08:17 2000
@@ -599,9 +599,10 @@ Perl_re_intuit_start(pTHX_ regexp *prog,
 	  find_anchor:
 	    while (t < strend - prog->minlen) {
 		if (*t == '\n') {
-		    if (t < s - prog->check_offset_min) {
+		    if (t < check_at - prog->check_offset_min) {
 			if (prog->anchored_substr) {
-			    /* We definitely contradict the found anchored
+			    /* Since we moved from the found position,
+			       we definitely contradict the found anchored
 			       substr.  Due to the above check we do not
 			       contradict "check" substr.
 			       Thus we can arrive here only if check substr
@@ -612,12 +613,17 @@ Perl_re_intuit_start(pTHX_ regexp *prog,
 				PL_colors[0],PL_colors[1], (long)(strpos - i_strpos), (long)(strpos - i_strpos + prog->anchored_offset)));
 			    goto do_other_anchored;
 			}
+			/* We don't contradict the found floating substring. */
+			/* XXXX Why not check for STCLASS? */
 			s = t + 1;
 			DEBUG_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld...\n",
 			    PL_colors[0],PL_colors[1], (long)(s - i_strpos)));
 			goto set_useful;
 		    }
-		    DEBUG_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m, restarting lookup for other hints at offset %ld...\n",
+		    /* Position contradicts check-string */
+		    /* XXXX probably better to look for check-string
+		       than for "\n", so one should lower the limit for t? */
+		    DEBUG_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m, restarting lookup for check-string at offset %ld...\n",
 			PL_colors[0],PL_colors[1], (long)(t + 1 - i_strpos)));
 		    strpos = s = t + 1;
 		    goto restart;



nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About