[ruby-dev:7280] Re: [BUG] regex.c

まつもと ゆきひろです

In message "[ruby-dev:7273] [BUG] regex.c"
    on 99/07/02, GOTO Kentaro <[e-mail]> writes:

|息抜きに Ruby しようと思ったら、バグに当たってしまいました。
|
|% ruby -ve '(" "*4680).scan(/((?!\\).*)+/)'
|ruby 1.3.4-990625 [i386-freebsd2.2.6]
|/tmp/rbn23789:1: [BUG] Segmentation fault
|Abort
|%

うーん、ばかでっかい文字列にemptyになりえるパターンのloopを
適用しちゃうとスタックが溢れちゃうってことらしいです。という
ことで、実行時に例外を出すことにしました。

# Perlみたいに一切を禁止しちゃうか...

パッチです。

ついでにゆうべウクライナからのメールのアドバイスを元に高速化
したコードも付けときます。正規表現マッチが10%くらい速いよう
な気がします。C_ALLOCAなマシンだと劇的に変わるかも。

--- regex.h	1999/06/09 09:21:31	1.1.1.3.2.10
+++ regex.h	1999/07/02 05:39:22
@@ -34,4 +34,5 @@
 # define re_search ruby_re_search
 # define re_set_casetable ruby_re_set_casetable
+# define register_info_type ruby_register_info_type
 #endif
 
@@ -91,4 +92,15 @@
 #define mbclen(c)   (re_mbctab[(unsigned char)(c)]+1)
 
+/* Structure used in re_match() */
+
+typedef union
+{
+  unsigned char *word;
+  struct {
+    unsigned is_active : 1;
+    unsigned matched_something : 1;
+  } bits;
+} register_info_type;
+
 /* This data structure is used to represent a compiled pattern.  */
 
@@ -117,4 +129,13 @@
 			   but at end of range or before a character
 			   listed in the fastmap.  */
+
+    /* stack & working area for re_match() */
+    unsigned char **regstart;
+    unsigned char **regend;
+    unsigned char **old_regstart;
+    unsigned char **old_regend;
+    register_info_type *reg_info;
+    unsigned char **best_regstart;
+    unsigned char **best_regend;
   };
 
--- regex.c	1999/06/25 09:02:46	1.1.1.3.2.26
+++ regex.c	1999/07/02 05:39:22
@@ -109,5 +109,5 @@
 #define FREE_AND_RETURN_VOID(stackb)	return
 #define FREE_AND_RETURN(stackb,val)	return(val)
-#define DOUBLE_STACK(stackx,stackb,len,type) \
+#define DOUBLE_STACK(stackx,stackb,len,type)				\
         (stackx = (type*)alloca(2 * len * sizeof(type)),		\
 	/* Only copy what is in use.  */				\
@@ -118,14 +118,5 @@
 
 #define FREE_VAR(var) if (var) free(var); var = NULL
-#define FREE_VARIABLES()						\
-  do {									\
-    FREE_VAR(regstart);							\
-    FREE_VAR(regend);							\
-    FREE_VAR(old_regstart)						\
-    FREE_VAR(old_regend);						\
-    FREE_VAR(best_regstart);						\
-    FREE_VAR(best_regend);						\
-    FREE_VAR(reg_info);							\
-  } while (0)
+#define FREE_VARIABLES()
 
 #define FREE_AND_RETURN_VOID(stackb)   free(stackb);return
@@ -2279,4 +2270,11 @@
   }
 
+  bufp->regstart = TMALLOC(regnum, unsigned char*);
+  bufp->regend = TMALLOC(regnum, unsigned char*);
+  bufp->old_regstart = TMALLOC(regnum, unsigned char*);
+  bufp->old_regend = TMALLOC(regnum, unsigned char*);
+  bufp->reg_info = TMALLOC(regnum, register_info_type);
+  bufp->best_regstart = TMALLOC(regnum, unsigned char*);
+  bufp->best_regend = TMALLOC(regnum, unsigned char*);
   FREE_AND_RETURN(stackb, 0);
 
@@ -2304,4 +2302,12 @@
   free(bufp->fastmap);
   if (bufp->must_skip) free(bufp->must_skip);
+
+  free(bufp->regstart);
+  free(bufp->regend);
+  free(bufp->old_regstart);
+  free(bufp->old_regend);
+  free(bufp->best_regstart);
+  free(bufp->best_regend);
+  free(bufp->reg_info);
   free(bufp);
 }
@@ -2585,5 +2591,5 @@
   unsigned is_a_succeed_n;
 
-  unsigned char **stackb = RE_TALLOC(NFAILURES, unsigned char*);
+  unsigned char **stackb = TMALLOC(NFAILURES, unsigned char*);
   unsigned char **stackp = stackb;
   unsigned char **stacke = stackb + NFAILURES;
@@ -2933,7 +2939,5 @@
 	if (startpos > 0)
 	  return -1;
-	else if (re_match(bufp, string, size, 0, regs) >= 0)
-	  return 0;
-	return -1;
+	return re_match(bufp, string, size, 0, regs);
       }
       break;
@@ -2963,5 +2967,5 @@
       pos = pend; pend = pbeg; pbeg = pos;
     }
-    if (pend > size) pend = size;
+    pend = size;
     if (bufp->options & RE_OPTIMIZE_NO_BM) {
       pos = slow_search(bufp->must+1, len,
@@ -3119,17 +3123,6 @@
 /* The following are used for re_match, defined below:  */
 
-/* Routine used by re_match.  */
+/* Accessing macros used in re_match: */
 
-/* Structure and accessing macros used in re_match:  */
-
-typedef union
-{
-  unsigned char *word;
-  struct {
-    unsigned is_active : 1;
-    unsigned matched_something : 1;
-  } bits;
-} register_info_type;
-
 #define IS_ACTIVE(R)  ((R).bits.is_active)
 #define MATCHED_SOMETHING(R)  ((R).bits.matched_something)
@@ -3324,6 +3317,6 @@
      keeps track of what the whole pattern matches.)  */
 
-  unsigned char **regstart = RE_TALLOC(num_regs, unsigned char*);
-  unsigned char **regend = RE_TALLOC(num_regs, unsigned char*);
+  unsigned char **regstart = bufp->regstart;
+  unsigned char **regend = bufp->regend;
 
   /* If a group that's operated upon by a repetition operator fails to
@@ -3332,6 +3325,6 @@
      are when we last see its open-group operator.  Similarly for a
      register's end.  */
-  unsigned char **old_regstart = RE_TALLOC(num_regs, unsigned char*);
-  unsigned char **old_regend = RE_TALLOC(num_regs, unsigned char*);
+  unsigned char **old_regstart = bufp->old_regstart;
+  unsigned char **old_regend = bufp->old_regend;
 
   /* The is_active field of reg_info helps us keep track of which (possibly
@@ -3342,5 +3335,5 @@
      loop their register is in.  */
 
-  register_info_type *reg_info = RE_TALLOC(num_regs, register_info_type);
+  register_info_type *reg_info = bufp->reg_info;
 
   /* The following record the register info as found in the above
@@ -3350,6 +3343,6 @@
 
   unsigned best_regs_set = 0;
-  unsigned char **best_regstart = RE_TALLOC(num_regs, unsigned char*);
-  unsigned char **best_regend = RE_TALLOC(num_regs, unsigned char*);
+  unsigned char **best_regstart = bufp->best_regstart;
+  unsigned char **best_regend = bufp->best_regend;
 
   if (regs) {
@@ -3541,6 +3534,11 @@
       case start_nowidth:
 	PUSH_FAILURE_POINT(0, d);
+	if (stackp - stackb > RE_DUP_MAX) {
+	   FREE_VARIABLES();
+	   FREE_AND_RETURN(stackb,(-2));
+	}
 	EXTRACT_NUMBER_AND_INCR(mcnt, p);
 	STORE_NUMBER(p+mcnt, stackp - stackb);
+	printf("%d\n", stackp - stackb);
 	continue;
 
@@ -4107,4 +4105,5 @@
     goto restore_best_regs;
 
+  FREE_VARIABLES();
   FREE_AND_RETURN(stackb,(-1)); 	/* Failure to match.  */
 }