emacs: src/regex.c comparison

comparison src/regex.c @ 28380:5478842aea4c

(analyse_first): New function obtained by ripping out most of re_compile_fastmap and generalizing it a little bit so that it can also just return whether a given (sub)pattern can match the empty string or not. (regex_compile): Use `analyse_first' to decide whether the loop-check needs to be done or not for *, +, *? and +? (the loop check is costly for non-greedy repetition). (re_compile_fastmap): Delegate the actual work to `analyse_first'.

author	Stefan Monnier <monnier@iro.umontreal.ca>
date	Wed, 29 Mar 2000 04:01:25 +0000
parents	bc86be15099e
children	975fe3d8922e

comparison

equal deleted inserted replaced

-:b3a689c74cde
+:5478842aea4c
 along with this program; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
 USA.	 */
 /* TODO:
-- use analyze_first to optimize non-empty loops
 - clean up multibyte issues
 - structure the opcode space into opcode+flag.
-- merge with glic's regex.[ch]
+- merge with glibc's regex.[ch]
+*/
-That's it for now    -sm */
 /* AIX requires this to be the first thing in the file. */
 #if defined (_AIX) && !defined (REGEX_MALLOC)
 #pragma alloca
 #endif
 					  reg_syntax_t syntax));
 static boolean at_endline_loc_p _RE_ARGS((const unsigned char *p,
 					  const unsigned char *pend,
 					  reg_syntax_t syntax));
 static unsigned char *skip_one_char _RE_ARGS((unsigned char *p));
+static int analyse_first _RE_ARGS((unsigned char *p, unsigned char *pend,
+				   char *fastmap, const int multibyte));
 /* Fetch the next character in the uncompiled pattern---translating it
 if necessary.  Also cast from a signed character in the constant
 string passed to us by the user to an unsigned char that we can use
 as an array index (in, e.g., `translate').  */
 	      {
 		if (many_times_ok)
 		  {
 		    boolean simple = skip_one_char (laststart) == b;
 		    unsigned int startoffset = 0;
+		    re_opcode_t ofj =
+		      (simple || !analyse_first (laststart, b, NULL, 0)) ?
+		      on_failure_jump : on_failure_jump_loop;
 		    assert (skip_one_char (laststart) <= b);
 		    if (!zero_times_ok && simple)
 		      { /* Since simple * loops can be made faster by using
 		    	   on_failure_keep_string_jump, we turn simple P+
 		      }
 		    GET_BUFFER_SPACE (6);
 		    if (!zero_times_ok)
 		      /* A + loop.  */
-		      STORE_JUMP (on_failure_jump_loop, b, b + 6);
+		      STORE_JUMP (ofj, b, b + 6);
 		    else
 		      /* Simple * loops can use on_failure_keep_string_jump
 			 depending on what follows.  But since we don't know
 			 that yet, we leave the decision up to
 			 on_failure_jump_smart.  */
-		      INSERT_JUMP (simple ? on_failure_jump_smart
+		      INSERT_JUMP (simple ? on_failure_jump_smart : ofj,
-				   : on_failure_jump_loop,
 				   laststart + startoffset, b + 6);
 		    b += 3;
 		    STORE_JUMP (jump, b, laststart + startoffset);
 		    b += 3;
 		  }
 	      { /* I wish the greedy and non-greedy cases could be merged. */
 		GET_BUFFER_SPACE (7); /* We might use less.  */
 		if (many_times_ok)
 		  {
+		    boolean emptyp = analyse_first (laststart, b, NULL, 0);
 		    /* The non-greedy multiple match looks like a repeat..until:
 		       we only need a conditional jump at the end of the loop */
-		    BUF_PUSH (no_op);
+		    if (emptyp) BUF_PUSH (no_op);
-		    STORE_JUMP (on_failure_jump_nastyloop, b, laststart);
+		    STORE_JUMP (emptyp ? on_failure_jump_nastyloop
+				: on_failure_jump, b, laststart);
 		    b += 3;
 		    if (zero_times_ok)
 		      {
 			/* The repeat...until naturally matches one or more.
 			   To also match zero times, we need to first jump to
 return true;
 return false;
 }
-/* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
+/* analyse_first.
-BUFP.  A fastmap records which of the (1 << BYTEWIDTH) possible
+If fastmap is non-NULL, go through the pattern and fill fastmap
-characters can start a string that matches the pattern.  This fastmap
+with all the possible leading chars.  If fastmap is NULL, don't
-is used by re_search to skip quickly over impossible starting points.
+bother filling it up (obviously) and only return whether the
+pattern could potentially match the empty string.
-Character codes above (1 << BYTEWIDTH) are not represented in the
-fastmap, but the leading codes are represented.  Thus, the fastmap
+Return 1  if p..pend might match the empty string.
-indicates which character sets could start a match.
+Return 0  if p..pend matches at least one char.
+Return -1 if p..pend matches at least one char, but fastmap was not
-The caller must supply the address of a (1 << BYTEWIDTH)-byte data
+updated accurately.
-area as BUFP->fastmap.
+Return -2 if an error occurred.  */
-We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
+static int
-the pattern buffer.
+analyse_first (p, pend, fastmap, multibyte)
+unsigned char *p, *pend;
-Returns 0 if we succeed, -2 if an internal error.   */
+char *fastmap;
+const int multibyte;
-int
-re_compile_fastmap (bufp)
-struct re_pattern_buffer *bufp;
 {
 int j, k;
 boolean not;
 #ifdef MATCH_MAY_ALLOCATE
 fail_stack_type fail_stack;
 #endif
 #ifndef REGEX_MALLOC
 char *destination;
 #endif
-register char *fastmap = bufp->fastmap;
-unsigned char *pattern = bufp->buffer;
-unsigned long size = bufp->used;
-unsigned char *p = pattern;
-register unsigned char *pend = pattern + size;
-const boolean multibyte = bufp->multibyte;
 #if defined (REL_ALLOC) && defined (REGEX_MALLOC)
 /* This holds the pointer to the failure stack, when
 it is allocated relocatably.  */
 fail_stack_elt_t *failure_stack_ptr;
 #endif
 /* If all elements for base leading-codes in fastmap is set, this
 flag is set true.	*/
 boolean match_any_multibyte_characters = false;
-assert (fastmap != NULL && p != NULL);
+assert (p);
 INIT_FAIL_STACK ();
-bzero (fastmap, 1 << BYTEWIDTH);  /* Assume nothing's valid.	*/
-bufp->fastmap_accurate = 1;	    /* It will be when we're done.  */
-bufp->can_be_null = 0;
 /* The loop below works as follows:
 - It has a working-list kept in the PATTERN_STACK and which basically
 starts by only containing a pointer to the first operation.
 - If the opcode we're looking at is a match against some set of
 We guarantee termination by ignoring backward jumps (more or less),
 so that `p' is monotonically increasing.  More to the point, we
 never set `p' (or push) anything `<= p1'.  */
 /* If can_be_null is set, then the fastmap will not be used anyway.  */
-while (!bufp->can_be_null)
+while (1)
 {
 /* `p1' is used as a marker of how far back a `on_failure_jump'
 	 can go without being ignored.  It is normally equal to `p'
 	 (which prevents any backward `on_failure_jump') except right
 	 after a plain `jump', to allow patterns such as:
 	    3..9: <body>
 	    10: on_failure_jump 3
 	 as used for the *? operator.  */
 unsigned char *p1 = p;
-if (p >= pend || *p == succeed)
+if (p >= pend)
 	{
+	  if (path_can_be_null)
+	    return (RESET_FAIL_STACK (), 1);
 	  /* We have reached the (effective) end of pattern.  */
-	  if (!PATTERN_STACK_EMPTY ())
+	  if (PATTERN_STACK_EMPTY ())
-	    {
+	    return (RESET_FAIL_STACK (), 0);
-	      bufp->can_be_null |= path_can_be_null;
+	  p = (unsigned char*) POP_PATTERN_OP ();
-	      /* Reset for next path.  */
+	  path_can_be_null = true;
-	      path_can_be_null = true;
+	  continue;
-	      p = (unsigned char*) POP_PATTERN_OP ();
-	      continue;
-	    }
-	  else
-	    break;
 	}
 /* We should never be about to go beyond the end of the pattern.	*/
 assert (p < pend);
 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
 	{
+	case succeed:
+	  p = pend;
+	  continue;
 	case duplicate:
 	  /* If the first character has to match a backreference, that means
 	     that the group was empty (since it already matched).  Since this
 	     is the only case that interests us here, we can assume that the
 /* Following are the cases which match a character.  These end
 	 with `break'.	*/
 	case exactn:
-	  fastmap[p[1]] = 1;
+	  if (fastmap) fastmap[p[1]] = 1;
 	  break;
 	case anychar:
 	  /* We could put all the chars except for \n (and maybe \0)
 	     but we don't bother since it is generally not worth it.  */
-	  bufp->can_be_null = 1;
+	  if (!fastmap) break;
-	  continue;
+	  return (RESET_FAIL_STACK (), -1);
 	case charset_not:
 	  /* Chars beyond end of bitmap are possible matches.
 	     All the single-byte codes can occur in multibyte buffers.
 	      fastmap[j] = 1;
 	  break;
 #else  /* emacs */
 	  /* This match depends on text properties.  These end with
 	     aborting optimizations.  */
-	  bufp->can_be_null = 1;
+	  return (RESET_FAIL_STACK (), -1);
-	  continue;
 	case categoryspec:
 	case notcategoryspec:
 	  if (!fastmap) break;
 	  not = (re_opcode_t)p[-1] == notcategoryspec;
 	 does these things.  */
 path_can_be_null = false;
 p = pend;
 } /* while p */
-/* Set `can_be_null' for the last path (also the first path, if the
+return (RESET_FAIL_STACK (), 0);
-pattern is empty).	 */
+} /* analyse_first */
-bufp->can_be_null |= path_can_be_null;
-RESET_FAIL_STACK ();
+/* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
+BUFP.  A fastmap records which of the (1 << BYTEWIDTH) possible
+characters can start a string that matches the pattern.  This fastmap
+is used by re_search to skip quickly over impossible starting points.
+Character codes above (1 << BYTEWIDTH) are not represented in the
+fastmap, but the leading codes are represented.  Thus, the fastmap
+indicates which character sets could start a match.
+The caller must supply the address of a (1 << BYTEWIDTH)-byte data
+area as BUFP->fastmap.
+We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
+the pattern buffer.
+Returns 0 if we succeed, -2 if an internal error.   */
+int
+re_compile_fastmap (bufp)
+struct re_pattern_buffer *bufp;
+{
+char *fastmap = bufp->fastmap;
+int analysis;
+assert (fastmap && bufp->buffer);
+bzero (fastmap, 1 << BYTEWIDTH);  /* Assume nothing's valid.	*/
+bufp->fastmap_accurate = 1;	    /* It will be when we're done.  */
+analysis = analyse_first (bufp->buffer, bufp->buffer + bufp->used,
+			    fastmap, bufp->multibyte);
+if (analysis < -1)
+return analysis;
+bufp->can_be_null = (analysis != 0);
 return 0;
 } /* re_compile_fastmap */
 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
 ENDS.  Subsequent matches using PATTERN_BUFFER and REGS will use

Mercurial > emacs

comparison src/regex.c @ 28380:5478842aea4c