R devel - Jun 2006 - Request for Comments: Fix for Bug 8141 (stack overflow)

Hi,

I have a proposed fix for Bug 8141 that passes make check-all on my  
machine and that will actually NOT overflow the C stack even for the  
larger problems than the test case given in 8141.

The basic idea is to not use recursion to walk the list elements and  
instead use a loop building up a new list from the substitution that  
is then returned.

The test case is as follows:

cat test.r

dfn <- rep(list(rep(0,2)),300000)
test <- as.data.frame.list(dfn)


A simple test compares the results with the old implementation in  
R-2.3.1 with my new one


cat testit.sh

# the old implementation
date
R --slave --silent --no-save < test.r
date

# the new one
cd /data/R/src/build/bin
date
./R --slave --silent --no-save < /home/kbhend/test.r
date


Running testit.sh shows that the old case segfaults from the C stack  
overflow while the new case happily proceeds until the end.

Tue Jun 13 17:24:23 EDT 2006
Error: segfault from C stack overflow
Execution halted
Tue Jun 13 17:24:26 EDT 2006
Tue Jun 13 17:24:26 EDT 2006
Tue Jun 13 17:26:22 EDT 2006


My proposed replacement routine for substituteList in coerce.c is  
given by:

/* Work through a list doing substitute on the */
/* elements taking particular care to handle ... */


SEXP attribute_hidden substituteList(SEXP el, SEXP rho)
{
     SEXP h, p, n = R_NilValue;
     p = R_NilValue;
     while (el != R_NilValue) {
	if (CAR(el) == R_DotsSymbol) {
	    if (rho == R_NilValue)
		h = R_UnboundValue;	/* so there is no substitution below */
	    else
		h = findVarInFrame3(rho, CAR(el), TRUE);
	    if (h == R_UnboundValue) {
                 h = lcons(R_DotsSymbol, R_NilValue);
                 if (n == R_NilValue) {
		     PROTECT(n = h);
                 }
                 else {
		     SETCDR(p,h);
		}
                 p = h;
	    } else if (h == R_NilValue  || h == R_MissingArg) {
		/* do not update  the new list pointer n  since we are skipping  
this element */
	    } else if (TYPEOF(h) == DOTSXP) {
	        h = substituteList(h, R_NilValue);
                 if (n == R_NilValue) {
		     PROTECT(n = h);
                 }
                 else {
		     SETCDR(p,h);
		}
                 p = h;
	    } else {
		error(_("... used in an incorrect context"));
                 h = R_NilValue;
                 if (n == R_NilValue)
                      n = h;
                 else {
		     SETCDR(p,h);
		}
                 p = h;
	    }
	}
	else {
	    h = substitute(CAR(el), rho);
	    if (isLanguage(el))
		h = LCONS(h, R_NilValue);
	    else
		h = CONS(h, R_NilValue);
	    SET_TAG(h, TAG(el));
             if (n == R_NilValue) {
	        PROTECT(n=h);
             }
             else {
	        SETCDR(p,h);
	    }
             p = h;
	}
         el = CDR(el);
     }
     if (n != R_NilValue) {
        UNPROTECT(1);
     }
     return n;
}


As I said, with this code in place R passes make check-all with  
flying colors and handles the bug 8141 test case well.


Would someone in the know, please review this piece of code and  
compare it to the original substituteList in coerce.c and let me know  
what you think.  If anyone has access to a large testcase that uses  
substituteList, I would love for them to test this code and report  
any problems.


Hope this helps,

Kevin