From: Nobuyoshi Nakada <nobu@...>
Date: 2006-09-24T16:54:53+09:00
Subject: Re: Array shift bug

Hi,

At Sun, 24 Sep 2006 11:52:27 +0900,
Devin Mullins wrote in [ruby-talk:216068]:
> 
> Bob Hutchison wrote:
> > A short article describing a problem in the implementation of array  
> > shift in Ruby 1.8.4 with a simple one-line fix in the C code is here:
> That's half a fix. If you're using shift and push to manage a queue, you 
> still have an ever-growing buffer.*

Does this patch fix it?


Index: array.c
===================================================================
RCS file: /cvs/ruby/src/ruby/array.c,v
retrieving revision 1.195
diff -p -U 2 -r1.195 array.c
--- array.c	16 Sep 2006 02:24:58 -0000	1.195
+++ array.c	24 Sep 2006 07:53:48 -0000
@@ -43,4 +43,11 @@ memfill(register VALUE *mem, register lo
 #define ARY_NOEMBED FL_USER3
 #define ARY_SHARED_P(a) FL_TEST(a, ELTS_SHARED)
+#define ARY_SHARED_ARY(a) RARRAY(a)->as.heap.aux.shared
+#define ARY_SHARED_LIMIT(a) (\
+	(RARRAY(a)->as.heap.ptr -			\
+	 RARRAY(ARY_SHARED_ARY(a))->as.heap.ptr >	\
+	 ARY_DEFAULT_SIZE) &&				\
+	(RARRAY(a)->as.heap.len <			\
+	 RARRAY(ARY_SHARED_ARY(a))->as.heap.len / 2))
 
 #define ARY_SET_NOEMBED(ary) do {\
@@ -229,5 +236,5 @@ ary_make_shared(VALUE ary)
     if (ARY_EMBED_P(ary)) abort();
     if (ARY_SHARED_P(ary)) {
-	return RARRAY(ary)->as.heap.aux.shared;
+	return ARY_SHARED_ARY(ary);
     }
     else {
@@ -239,5 +246,5 @@ ary_make_shared(VALUE ary)
 	shared->as.heap.ptr = RARRAY(ary)->as.heap.ptr;
 	shared->as.heap.aux.capa = RARRAY(ary)->as.heap.aux.capa;
-	RARRAY(ary)->as.heap.aux.shared = (VALUE)shared;
+	ARY_SHARED_ARY(ary) = (VALUE)shared;
 	FL_SET(ary, ELTS_SHARED);
 	OBJ_FREEZE(shared);
@@ -452,5 +459,5 @@ ary_shared_array(VALUE klass, VALUE ary)
     RARRAY(val)->as.heap.ptr = RARRAY(ary)->as.heap.ptr;
     RARRAY(val)->as.heap.len = RARRAY(ary)->as.heap.len;
-    RARRAY(val)->as.heap.aux.shared = RARRAY(ary)->as.heap.aux.shared;
+    ARY_SHARED_ARY(val) = ARY_SHARED_ARY(ary);
     FL_SET(val, ELTS_SHARED);
     return val;
@@ -533,5 +540,5 @@ rb_ary_pop(VALUE ary)
     rb_ary_modify_check(ary);
     if (RARRAY_LEN(ary) == 0) return Qnil;
-    if (!FL_TEST(ary, ELTS_SHARED) &&
+    if (!ARY_SHARED_P(ary, ELTS_SHARED) &&
 	    RARRAY_LEN(ary) * 3 < ARY_CAPA(ary) &&
 	    ARY_CAPA(ary) > ARY_DEFAULT_SIZE) {
@@ -587,4 +594,7 @@ rb_ary_shift(VALUE ary)
 	RARRAY(ary)->as.heap.ptr++;	/* shift ptr */
 	RARRAY(ary)->as.heap.len--;
+	if (ARY_SHARED_LIMIT(ary)) {
+	    rb_ary_modify(ary);
+	}
     }
 
@@ -620,7 +630,4 @@ rb_ary_shift_m(int argc, VALUE *argv, VA
 
     rb_ary_modify_check(ary);
-    if (ARY_EMBED_P(ary)) {
-	
-    }
 
     result = ary_shared_first(argc, argv, ary, Qfalse);
@@ -629,4 +636,7 @@ rb_ary_shift_m(int argc, VALUE *argv, VA
 	RARRAY(ary)->as.heap.ptr += n;
 	RARRAY(ary)->as.heap.len -= n;
+	if (ARY_SHARED_LIMIT(ary)) {
+	    rb_ary_modify(ary);
+	}
     }
     else {
@@ -734,5 +744,5 @@ rb_ary_subseq(VALUE ary, long beg, long 
 	RARRAY(ary2)->as.heap.ptr = ptr + beg;
 	RARRAY(ary2)->as.heap.len = len;
-	RARRAY(ary2)->as.heap.aux.shared = shared;
+	ARY_SHARED_ARY(ary2) = shared;
 	FL_SET(ary2, ELTS_SHARED);
 	return ary2;
@@ -2093,5 +2103,5 @@ rb_ary_replace(VALUE copy, VALUE orig)
     RARRAY(copy)->as.heap.ptr = RARRAY(shared)->as.heap.ptr;
     RARRAY(copy)->as.heap.len = RARRAY(shared)->as.heap.len;
-    RARRAY(copy)->as.heap.aux.shared = shared;
+    ARY_SHARED_ARY(copy) = shared;
     FL_SET(copy, ELTS_SHARED);
 


-- 
Nobu Nakada