COPY-TREE fails with stack overflow on long lists

[Robert Dodier]

COPY-TREE fails with a stack overflow when its argument is a long list. (I didn't try to find out what is the minimum length to trigger the error.)

COPY-LIST succeeds on a list of the same length.

Thank you for your attention to this. I searched the bug database but didn't find a similar report. I don't see anything about COPY-TREE in the change logs.

------------------------- bug --------------------------
* (defvar x nil)

X
* (dotimes (i 65536) (push 1 x))

NIL
* (copy-tree x)
INFO: Control stack guard page unprotected
Control stack guard page temporarily disabled: proceed with caution

debugger invoked on a SB-KERNEL::CONTROL-STACK-EXHAUSTED in thread #<THREAD
                                                                     "initial thread" RUNNING
                                                                     {AA8F9A9}>:
  Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.

PROCEED WITH CAUTION.

Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
  0: [ABORT] Exit debugger, returning to top level.

(SB-KERNEL::CONTROL-STACK-EXHAUSTED-ERROR)
0]

------------------------- info --------------------------
$ sbcl --version
SBCL 1.0.49

* *features*

(:ANSI-CL :COMMON-LISP :SBCL :SB-DOC :SB-TEST :SB-LDB :SB-PACKAGE-LOCKS
 :SB-UNICODE :SB-EVAL :SB-SOURCE-LOCATIONS :IEEE-FLOATING-POINT :X86 :UNIX :ELF
 :LINUX :SB-THREAD :LARGEFILE :GENCGC :STACK-GROWS-DOWNWARD-NOT-UPWARD
 :C-STACK-IS-CONTROL-STACK :COMPARE-AND-SWAP-VOPS :UNWIND-TO-FRAME-AND-CALL-VOP
 :RAW-INSTANCE-INIT-VOPS :STACK-ALLOCATABLE-CLOSURES :STACK-ALLOCATABLE-VECTORS
 :STACK-ALLOCATABLE-LISTS :STACK-ALLOCATABLE-FIXED-OBJECTS :ALIEN-CALLBACKS
 :CYCLE-COUNTER :INLINE-CONSTANTS :MEMORY-BARRIER-VOPS :LINKAGE-TABLE
 :OS-PROVIDES-DLOPEN :OS-PROVIDES-DLADDR :OS-PROVIDES-PUTWC
 :OS-PROVIDES-SUSECONDS-T :OS-PROVIDES-GETPROTOBY-R :OS-PROVIDES-POLL)

$ uname -a
Linux robert-laptop 2.6.24-16-generic #1 SMP Thu Apr 10 13:23:42 UTC 2008 i686 GNU/Linux

[Stas Boukarev (stassats)]

commit 4b25bb8e20bf3c1419a11b7d4cfefa23e4f3279b
Author: Stas Boukarev <email address hidden>
Date: Mon May 14 05:12:45 2012 +0400

    Optimize copy-tree.

    copy-tree used to always call itself, even on linear lists, which
    caused stack exhaustion on long lists. Make it copy linear lists
    linearly, and recur only when necessary. This also makes it somewhat
    faster.

[Nikodemus Siivola (nikodemus)]

in SBCL 1.0.57