xemacs-beta: src/regex.c comparison

comparison src/regex.c @ 185:3d6bfa290dbd r20-3b19

Import from CVS: tag r20-3b19

author	cvs
date	Mon, 13 Aug 2007 09:55:28 +0200
parents	e121b013d1f0
children	850242ba4a81

comparison

equal deleted inserted replaced

-:bcd2674570bf
+:3d6bfa290dbd
 static int done = 0;
 if (done)
 return;
-bzero (re_syntax_table, sizeof re_syntax_table);
+memset (re_syntax_table, 0, sizeof (re_syntax_table));
 for (c = 'a'; c <= 'z'; c++)
 re_syntax_table[c] = Sword;
 for (c = 'A'; c <= 'Z'; c++)
 one.  We need to make sure there are no crashes, which would occur
 otherwise due to out-of-bounds array references. */
 #define ISASCII(c) (((unsigned EMACS_INT) (c)) < 0x100 && ISASCII_1 (c))
 #else
 #define ISASCII(c) ISASCII_1 (c)
-#endif
+#endif /* MULE */
 #ifdef isblank
 #define ISBLANK(c) (ISASCII (c) && isblank (c))
 #else
 #define ISBLANK(c) ((c) == ' ' || (c) == '\t')
 /* 97/2/17 jhod: The following two were merged back in from the Mule
 2.3 code to enable some language specific processing */
 ,categoryspec,     /* Matches entries in the character category tables */
 notcategoryspec    /* The opposite of the above */
-#endif
+#endif /* MULE */
 } re_opcode_t;
 /* Common operations on the compiled pattern.  */
 static reg_errcode_t compile_extended_range (CONST char **p_ptr,
 					     CONST char *pend,
 					     char *translate,
 					     reg_syntax_t syntax,
 					     Lisp_Object rtab);
-#endif
+#endif /* MULE */
 static boolean group_match_null_string_p (unsigned char **p,
 					  unsigned char *end,
 					  register_info_type *reg_info);
 static boolean alt_match_null_string_p (unsigned char *p, unsigned char *end,
 					register_info_type *reg_info);
 else if (!(syntax & RE_CONTEXT_INDEP_OPS))
 goto normal_char;
 }
 {
-/* Are we optimizing this jump?  */
+	    /* true means zero/many matches are allowed. */
-boolean keep_string_p = false;
+	    boolean zero_times_ok = c != '+';
+boolean many_times_ok = c != '?';
-/* 1 means zero (many) matches is allowed.  */
-char zero_times_ok = 0, many_times_ok = 0;
+/* true means match shortest string possible. */
+boolean minimal = false;
 /* If there is a sequence of repetition chars, collapse it
 down to just one (the right one).  We can't combine
 interval operators with these because of, e.g., `a{2}*',
-which should only match an even number of `a's.  */
+which should only match an even number of `a's.	*/
+while (p != pend)
-for (;;)
 {
-zero_times_ok |= c != '+';
-many_times_ok |= c != '?';
-if (p == pend)
-break;
 PATFETCH (c);
-if (c == '*'
+if (c == '*' || (!(syntax & RE_BK_PLUS_QM)
-|| (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
+&& (c == '+' || c == '?')))
 ;
-else if (syntax & RE_BK_PLUS_QM  &&  c == '\\')
+else if (syntax & RE_BK_PLUS_QM && c == '\\')
 {
 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
 PATFETCH (c1);
 if (!(c1 == '+' || c1 == '?'))
 PATUNFETCH;
 break;
 }
 /* If we get here, we found another repeat character.  */
-}
+if (!(syntax & RE_NO_MINIMAL_MATCHING))
+{
+/* `*?' and `+?' and `??' are okay (and mean match
+minimally), but other sequences (such as `*??' and
+`+++') are rejected (reserved for future use). */
+if (minimal || c != '?')
+FREE_STACK_RETURN (REG_BADRPT);
+minimal = true;
+}
+else
+{
+zero_times_ok |= c != '+';
+many_times_ok |= c != '?';
+}
+}
 /* Star, etc. applied to an empty pattern is equivalent
 to an empty pattern.  */
 if (!laststart)
 break;
-/* Now we know whether or not zero matches is allowed
+	    /* Now we know whether zero matches is allowed
-and also whether or not two or more matches is allowed.  */
+	       and whether two or more matches is allowed
-if (many_times_ok)
+and whether we want minimal or maximal matching. */
-{ /* More than one repetition is allowed, so put in at the
+if (minimal)
-end a backward relative jump from `b' to before the next
+{
-jump we're going to put in below (which jumps from
+if (!many_times_ok)
-laststart to after this jump).
+{
+/* "a??" becomes:
-But if we are at the `*' in the exact sequence `.*\n',
+0: /on_failure_jump to 6
-insert an unconditional jump backwards to the .,
+3: /jump to 9
-instead of the beginning of the loop.  This way we only
+6: /exactn/1/A
-push a failure point once, instead of every time
+9: end of pattern.
-through the loop.  */
+*/
-assert (p - 1 > pattern);
+GET_BUFFER_SPACE (6);
+INSERT_JUMP (jump, laststart, b + 3);
-/* Allocate the space for the jump.  */
+b += 3;
-GET_BUFFER_SPACE (3);
+INSERT_JUMP (on_failure_jump, laststart, laststart + 6);
+b += 3;
-/* We know we are not at the first character of the pattern,
+}
-because laststart was nonzero.  And we've already
+else if (zero_times_ok)
-incremented `p', by the way, to be the character after
+{
-the `*'.  Do we have to do something analogous here
+/* "a*?" becomes:
-for null bytes, because of RE_DOT_NOT_NULL?  */
+0: /jump to 6
-if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
+3: /exactn/1/A
-		    && zero_times_ok
+6: /on_failure_jump to 3
-&& p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
+9: end of pattern.
-&& !(syntax & RE_DOT_NEWLINE))
+*/
-{ /* We have .*\n.  */
+GET_BUFFER_SPACE (6);
-STORE_JUMP (jump, b, laststart);
+INSERT_JUMP (jump, laststart, b + 3);
-keep_string_p = true;
+b += 3;
+STORE_JUMP (on_failure_jump, b, laststart + 3);
+b += 3;
 }
 else
-/* Anything else.  */
+{
-STORE_JUMP (maybe_pop_jump, b, laststart - 3);
+/* "a+?" becomes:
+0: /exactn/1/A
-/* We've added more stuff to the buffer.  */
+3: /on_failure_jump to 0
+6: end of pattern.
+*/
+GET_BUFFER_SPACE (3);
+STORE_JUMP (on_failure_jump, b, laststart);
+b += 3;
+}
+}
+else
+{
+/* Are we optimizing this jump?  */
+boolean keep_string_p = false;
+if (many_times_ok)
+{ /* More than one repetition is allowed, so put in at the
+end a backward relative jump from `b' to before the next
+jump we're going to put in below (which jumps from
+laststart to after this jump).
+But if we are at the `*' in the exact sequence `.*\n',
+insert an unconditional jump backwards to the .,
+instead of the beginning of the loop.  This way we only
+push a failure point once, instead of every time
+through the loop.  */
+assert (p - 1 > pattern);
+/* Allocate the space for the jump.  */
+GET_BUFFER_SPACE (3);
+/* We know we are not at the first character of the
+pattern, because laststart was nonzero.  And we've
+already incremented `p', by the way, to be the
+character after the `*'.  Do we have to do something
+analogous here for null bytes, because of
+RE_DOT_NOT_NULL? */
+if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
+&& zero_times_ok
+&& p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
+&& !(syntax & RE_DOT_NEWLINE))
+{ /* We have .*\n.  */
+STORE_JUMP (jump, b, laststart);
+keep_string_p = true;
+}
+else
+/* Anything else.  */
+STORE_JUMP (maybe_pop_jump, b, laststart - 3);
+/* We've added more stuff to the buffer.  */
+b += 3;
+}
+/* On failure, jump from laststart to b + 3, which will be the
+end of the buffer after this jump is inserted.  */
+GET_BUFFER_SPACE (3);
+INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
+					   : on_failure_jump,
+laststart, b + 3);
 b += 3;
+if (!zero_times_ok)
+{
+/* At least one repetition is required, so insert a
+`dummy_failure_jump' before the initial
+`on_failure_jump' instruction of the loop. This
+effects a skip over that instruction the first time
+we hit that loop.  */
+GET_BUFFER_SPACE (3);
+INSERT_JUMP (dummy_failure_jump, laststart, laststart + 6);
+b += 3;
+}
 }
-/* On failure, jump from laststart to b + 3, which will be the
-end of the buffer after this jump is inserted.  */
-GET_BUFFER_SPACE (3);
-INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
-: on_failure_jump,
-laststart, b + 3);
 pending_exact = 0;
-b += 3;
+}
-if (!zero_times_ok)
-{
-/* At least one repetition is required, so insert a
-`dummy_failure_jump' before the initial
-`on_failure_jump' instruction of the loop. This
-effects a skip over that instruction the first time
-we hit that loop.  */
-GET_BUFFER_SPACE (3);
-INSERT_JUMP (dummy_failure_jump, laststart, laststart + 6);
-b += 3;
-}
-}
 	  break;
 	case '.':
 laststart = b;
 case '(':
 if (syntax & RE_NO_BK_PARENS)
 goto normal_backslash;
 handle_open:
-bufp->re_nsub++;
+{
-regnum++;
+regnum_t r;
-if (COMPILE_STACK_FULL)
+if (!(syntax & RE_NO_SHY_GROUPS)
-{
+&& p != pend
-RETALLOC (compile_stack.stack, compile_stack.size << 1,
+&& TRANSLATE(*p) == TRANSLATE('?'))
-compile_stack_elt_t);
+{
-if (compile_stack.stack == NULL) return REG_ESPACE;
+p++;
+PATFETCH(c);
-compile_stack.size <<= 1;
+switch (c)
-}
+{
+case ':': /* shy groups */
-/* These are the values to restore when we hit end of this
+r = MAX_REGNUM + 1;
-group.  They are all relative offsets, so that if the
+break;
-whole pattern moves because of realloc, they will still
-be valid.  */
+/* All others are reserved for future constructs. */
-COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
+default:
-COMPILE_STACK_TOP.fixup_alt_jump
+FREE_STACK_RETURN (REG_BADPAT);
-= fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
+}
-COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
+}
-COMPILE_STACK_TOP.regnum = regnum;
+else
+{
-/* We will eventually replace the 0 with the number of
+bufp->re_nsub++;
-groups inner to this one.  But do not push a
+r = ++regnum;
-start_memory for groups beyond the last one we can
+}
-represent in the compiled pattern.  */
-if (regnum <= MAX_REGNUM)
+if (COMPILE_STACK_FULL)
 {
-COMPILE_STACK_TOP.inner_group_offset = b - bufp->buffer + 2;
+RETALLOC (compile_stack.stack, compile_stack.size << 1,
-BUF_PUSH_3 (start_memory, regnum, 0);
+compile_stack_elt_t);
-}
+if (compile_stack.stack == NULL) return REG_ESPACE;
-compile_stack.avail++;
+compile_stack.size <<= 1;
+}
-fixup_alt_jump = 0;
-laststart = 0;
+/* These are the values to restore when we hit end of this
-begalt = b;
+group.  They are all relative offsets, so that if the
-	      /* If we've reached MAX_REGNUM groups, then this open
+whole pattern moves because of realloc, they will still
-		 won't actually generate any code, so we'll have to
+be valid.  */
-		 clear pending_exact explicitly.  */
+COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
-	      pending_exact = 0;
+COMPILE_STACK_TOP.fixup_alt_jump
+= fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
+COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
+COMPILE_STACK_TOP.regnum = r;
+/* We will eventually replace the 0 with the number of
+groups inner to this one.  But do not push a
+start_memory for groups beyond the last one we can
+represent in the compiled pattern.  */
+if (r <= MAX_REGNUM)
+{
+COMPILE_STACK_TOP.inner_group_offset
+= b - bufp->buffer + 2;
+BUF_PUSH_3 (start_memory, r, 0);
+}
+compile_stack.avail++;
+fixup_alt_jump = 0;
+laststart = 0;
+begalt = b;
+/* If we've reached MAX_REGNUM groups, then this open
+won't actually generate any code, so we'll have to
+clear pending_exact explicitly.  */
+pending_exact = 0;
+}
 break;
 case ')':
 if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
 	  for (j = *p * BYTEWIDTH; j < 0x80; j++)
 fastmap[j] = 1;
 	  /* And all extended characters must be allowed, too. */
 	  for (j = 0x80; j < 0xA0; j++)
 	    fastmap[j] = 1;
-#else
+#else /* ! MULE */
 	  for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
 fastmap[j] = 1;
-#endif
+#endif /* ! MULE */
 	  for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
 	    if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
 fastmap[j] = 1;
 break;
 #ifdef DEBUG
 /* Counts the total number of registers pushed.  */
 unsigned num_regs_pushed = 0;
 #endif
+/* 1 if this match ends in the same string (string1 or string2)
+as the best previous match.  */
+boolean same_str_p;
+/* 1 if this match is the best seen so far.  */
+boolean best_match_p;
 DEBUG_PRINT1 ("\n\nEntering re_match_2.\n");
 INIT_FAIL_STACK ();
 #ifdef MATCH_MAY_ALLOCATE
 there are groups, we include space for register 0 (the whole
 pattern), even though we never use it, since it simplifies the
 array indexing.  We should fix this.  */
 if (bufp->re_nsub)
 {
-regstart = REGEX_TALLOC (num_regs, CONST char *);
+regstart       = REGEX_TALLOC (num_regs, CONST char *);
-regend = REGEX_TALLOC (num_regs, CONST char *);
+regend         = REGEX_TALLOC (num_regs, CONST char *);
-old_regstart = REGEX_TALLOC (num_regs, CONST char *);
+old_regstart   = REGEX_TALLOC (num_regs, CONST char *);
-old_regend = REGEX_TALLOC (num_regs, CONST char *);
+old_regend     = REGEX_TALLOC (num_regs, CONST char *);
-best_regstart = REGEX_TALLOC (num_regs, CONST char *);
+best_regstart  = REGEX_TALLOC (num_regs, CONST char *);
-best_regend = REGEX_TALLOC (num_regs, CONST char *);
+best_regend    = REGEX_TALLOC (num_regs, CONST char *);
-reg_info = REGEX_TALLOC (num_regs, register_info_type);
+reg_info       = REGEX_TALLOC (num_regs, register_info_type);
-reg_dummy = REGEX_TALLOC (num_regs, CONST char *);
+reg_dummy      = REGEX_TALLOC (num_regs, CONST char *);
 reg_info_dummy = REGEX_TALLOC (num_regs, register_info_type);
 if (!(regstart && regend && old_regstart && old_regend && reg_info
 && best_regstart && best_regend && reg_dummy && reg_info_dummy))
 {
 	  /* If we haven't matched the entire string, and we want the
 longest match, try backtracking.  */
 if (d != end_match_2)
 	    {
-	      /* 1 if this match ends in the same string (string1 or string2)
+	      same_str_p = (FIRST_STRING_P (match_end)
-		 as the best previous match.  */
+			    == MATCHING_IN_FIRST_STRING);
-	      boolean same_str_p = (FIRST_STRING_P (match_end)
-				    == MATCHING_IN_FIRST_STRING);
-	      /* 1 if this match is the best seen so far.  */
-	      boolean best_match_p;
 	      /* AIX compiler got confused when this was combined
 		 with the previous declaration.  */
 	      if (same_str_p)
 		best_match_p = d > match_end;
 	    SET_REGS_MATCHED ();
 	    INC_CHARPTR (d);
 	    break;
 	  }
-#endif
+#endif /* MULE */
 /* The beginning of a group is represented by start_memory.
 The arguments are the register number in the next byte, and the
 number of groups inner to this one in the next.  The text
 DEBUG_PRINT1 ("EXECUTING on_failure_keep_string_jump");
 EXTRACT_NUMBER_AND_INCR (mcnt, p);
 DEBUG_PRINT3 (" %d (to 0x%p):\n", mcnt, p + mcnt);
-PUSH_FAILURE_POINT (p + mcnt, (void *) 0, -2);
+PUSH_FAILURE_POINT (p + mcnt, (char *) 0, -2);
 break;
 	/* Uses of on_failure_jump:
 something meaningless for pop_failure_jump to pop.  */
 case dummy_failure_jump:
 DEBUG_PRINT1 ("EXECUTING dummy_failure_jump.\n");
 /* It doesn't matter what we push for the string here.  What
 the code at `fail' tests is the value for the pattern.  */
-PUSH_FAILURE_POINT ((void *) 0, (void *) 0, -2);
+PUSH_FAILURE_POINT ((unsigned char *) 0, (char *) 0, -2);
 goto unconditional_jump;
 /* At the end of an alternative, we need to push a dummy failure
 point in case we are followed by a `pop_failure_jump', because
 requires that we match the `ab' alternative.  */
 case push_dummy_failure:
 DEBUG_PRINT1 ("EXECUTING push_dummy_failure.\n");
 /* See comments just above at `dummy_failure_jump' about the
 two zeroes.  */
-PUSH_FAILURE_POINT ((void *) 0, (void *) 0, -2);
+PUSH_FAILURE_POINT ((unsigned char *) 0, (char *) 0, -2);
 break;
 /* Have to succeed matching what follows at least n times.
 After that, handle like `on_failure_jump'.  */
 case succeed_n:

Mercurial > hg > xemacs-beta

comparison src/regex.c @ 185:3d6bfa290dbd r20-3b19