Regexp matching errors

Regexp matching errors

[Stefan Monnier]

The handling of the fastmap optimization in regep.c had some bugs w.r.t
eight-bit-* chars in multibyte buffers/strings when case-fold is not in use:

   src/emacs --batch -Q --eval \
             '(let ((case-fold-search nil))
                (message "%s" (list (string-match "\xa1\\|a" "éf\x81g")
                                    (string-match "\x81\\|a" "éf\x81g")
                                    (string-match "[\xa1]" "éf\x81g")
                                    (string-match "[\x81]" "éf\x81g"))))'

returned

   (2 nil 2 nil)

I've installed the patch below to hopefully fix them.
I believe this patch to be prefectly safe, but you never know, so if you
notice anything fishy about regexp-matching, please tell me.


        Stefan



2006-09-22  Stefan Monnier  <monnier@iro.umontreal.ca>

	* regex.c (analyse_first): For eight-bit-control chars, mark both the
	char's value and its leading byte in the fastmap.
	(re_search_2): When fast-scanning without translation, be careful to
	check that we only match the leading byte of a multibyte char.

	* charset.h (PREV_CHAR_BOUNDARY): Make it work from within a char's
	byte sequence.
	(AT_CHAR_BOUNDARY): New macro.

Index: src/charset.h
===================================================================
RCS file: /sources/emacs/emacs/src/charset.h,v
retrieving revision 1.83
diff -u -r1.83 charset.h
--- src/charset.h	29 May 2006 06:19:09 -0000	1.83
+++ src/charset.h	22 Sep 2006 17:29:43 -0000
@@ -658,22 +658,34 @@
   } while (0)
 
 
-/* If P is after LIMIT, advance P to the previous character boundary.
-   It assumes that P is already at a character boundary of the sane
-   mulitbyte form whose beginning address is LIMIT.  */
+/* If P is after LIMIT, advance P to the previous character boundary.  */
 
 #define PREV_CHAR_BOUNDARY(p, limit)					\
   do {									\
     if ((p) > (limit))							\
       {									\
 	const unsigned char *p0 = (p);					\
+	const unsigned char *p_limit = max (limit, p0 - MAX_MULTIBYTE_LENGTH);\
 	do {								\
 	  p0--;								\
-	} while (p0 >= limit && ! CHAR_HEAD_P (*p0));			\
-	(p) = (BYTES_BY_CHAR_HEAD (*p0) == (p) - p0) ? p0 : (p) - 1;	\
+	} while (p0 >= p_limit && ! CHAR_HEAD_P (*p0));			\
+	/* If BBCH(*p0) > p-p0, it means we were not on a boundary.  */	\
+	(p) = (BYTES_BY_CHAR_HEAD (*p0) >= (p) - p0) ? p0 : (p) - 1;	\
       }									\
   } while (0)
 
+#define AT_CHAR_BOUNDARY_P(result, p, limit)	\
+  do {						\
+    if (CHAR_HEAD_P (*(p)) || (p) <= limit)	\
+      /* Optimization for the common case. */	\
+      (result) = 1;				\
+    else					\
+      {						\
+	const unsigned char *p_aux = (p)+1;	\
+	PREV_CHAR_BOUNDARY (p_aux, limit);	\
+	(result) = (p_aux == (p));		\
+      }						\
+} while (0)
 
 #ifdef emacs
 
Index: src/regex.c
===================================================================
RCS file: /sources/emacs/emacs/src/regex.c,v
retrieving revision 1.212
diff -u -r1.212 regex.c
--- src/regex.c	16 Sep 2006 15:28:47 -0000	1.212
+++ src/regex.c	22 Sep 2006 17:29:43 -0000
@@ -3877,11 +3877,13 @@
 	  if (fastmap)
 	    {
 	      int c = RE_STRING_CHAR (p + 1, pend - p);
-
+	      /* When fast-scanning, the fastmap can be indexed either with
+		 a char (smaller than 256) or with the first byte of
+		 a char's byte sequence.  So we have to conservatively add
+		 both to the table.  */
 	      if (SINGLE_BYTE_CHAR_P (c))
 		fastmap[c] = 1;
-	      else
-		fastmap[p[1]] = 1;
+	      fastmap[p[1]] = 1;
 	    }
 	  break;
 
@@ -3899,6 +3901,10 @@
 	     So any that are not listed in the charset
 	     are possible matches, even in multibyte buffers.  */
 	  if (!fastmap) break;
+	  /* We don't need to mark LEADING_CODE_8_BIT_CONTROL specially
+	     because it will automatically be set when needed by virtue of
+	     being larger than the highest char of its charset (0xbf) but
+	     smaller than (1<<BYTEWIDTH).  */
 	  for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH;
 	       j < (1 << BYTEWIDTH); j++)
 	    fastmap[j] = 1;
@@ -3909,7 +3915,13 @@
 	  for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH - 1, p++;
 	       j >= 0; j--)
 	    if (!!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))) ^ not)
-	      fastmap[j] = 1;
+	      {
+		fastmap[j] = 1;
+#ifdef emacs
+		if (j >= 0x80 && j < 0xa0)
+		  fastmap[LEADING_CODE_8_BIT_CONTROL] = 1;
+#endif
+	      }
 
 	  if ((not && multibyte)
 	      /* Any character set can possibly contain a character
@@ -4352,11 +4364,33 @@
 		    }
 		}
 	      else
-		while (range > lim && !fastmap[*d])
+		do
 		  {
-		    d++;
-		    range--;
-		  }
+		    re_char *d_start = d;
+		    while (range > lim && !fastmap[*d])
+		      {
+			d++;
+			range--;
+		      }
+#ifdef emacs
+		    if (multibyte && range > lim)
+		      {
+			/* Check that we are at the beginning of a char.  */
+			int at_boundary;
+			AT_CHAR_BOUNDARY_P (at_boundary, d, d_start);
+			if (at_boundary)
+			  break;
+			else
+			  { /* We have matched an internal byte of a char
+			       rather than the leading byte, so it's a false
+			       positive: we should keep scanning.  */
+			    d++; range--;
+			  }
+		      }
+		    else
+#endif
+		      break;
+		  } while (1);
 
 	      startpos += irange - range;
 	    }