DOLIST's detection of constant list arg can exhaust memory on circular lists

[Douglas Katzman]

DOLIST uses LIST-MEMBERS so that it can insert into its expansion (THE (member <items>) loopvar).
But only a very specific case of circularity is detected. The general case is not:

 * (sb-impl::list-members '(one two three . #1=(foo bar . #1#)))
  =>
Heap exhausted during garbage collection: 32 bytes available, 48 requested.
 Gen StaPg UbSta LaSta LUbSt Boxed Unboxed LB LUB !move Alloc Waste Trig WP GCs Mem-age
   0: 0 0 0 0 0 0 0 0 0 0 0 10737418 0 0 0.0000
   1: 28980 0 0 0 13125 0 0 0 0 429658320 421680 268565578 0 1 1.4002
   2: 32767 0 0 0 18324 3 0 0 16 600034640 504496 2000000 11571 0 0.6321
   3: 0 0 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
   4: 0 0 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
   5: 0 0 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
   6: 0 0 0 0 1154 162 0 0 0 43122688 0 2000000 1123 0 0.0000
   Total bytes allocated = 1072815648
   Dynamic-space-size bytes = 1073741824
GC control variables:
   *GC-INHIBIT* = true
   *GC-PENDING* = in progress
fatal error encountered in SBCL pid 3135:
Heap exhausted, game over.

But this minimal example employs a circular list whose first three elements are not part of the cycle.
EVAL is used only to hide the const-ness from the compiler, proving that the code is otherwise fine.
The output varies randomly of course.

(let ((n 0))
   (flet ((test-it (arg &aux (x (random 100)))
              (format t "Iteration ~D : ~S ~S~%" (incf n) arg x)
              (< x 3)))
     (dolist (item (eval ''(one two three . #1=(foo bar . #1#))))
       (cond ((test-it item) (return 'yup))
                  ((eql n 12) (return 'bah))))))
=>
Iteration 1 : ONE 66
Iteration 2 : TWO 80
Iteration 3 : THREE 64
Iteration 4 : FOO 68
Iteration 5 : BAR 1
YUP

Maybe if LIST-WITH-LENGTH-P is false of the constant list we should not try so hard to insert a member type?

[Paul Khuong (pvk)]

Fixed in

commit 678a5d0cd5bfccf621e11147507471c3f511595c
Author: Paul Khuong <email address hidden>
Date: Thu Jan 3 10:31:09 2013 -0500

    Do not traverse long constant lists when expanding DOLIST

    * Only gather type information on the list contents' if it's short
      (at most 20 elements); otherwise, do not derive type information.

    * Thanks to Douglas Katzman for the bug report (lp#1095488).