[cl-store-devel] Bug in some circular lists storage

[Gustavo]

Hello,

CL-Store can handle storing normal circular lists, but it can't store
correctly the circularity on lists like this particular list:

'(0 . #1=(1 2 3 . #1#))

The problem is that the circularity is inside the list. Not that I am
actually using this kind of list, I just ran into this bug for curiosity.

cl-user> (setf *print-circle* t)
t
cl-user> (cl-store:store '(0 . #1=(1 2 3 . #1#)) "test")
(0 . #1=(1 2 3 . #1#))
cl-user> (cl-store:restore "test")
#1=(0 1 2 . #1#)

The problem is that safe-length returns 3 as the length for the given list.
A possible solution is to make safe-length test if the circularity found
references the list itself. If it does, than return the value it already
returned. If not, it returns (values 1 (cdr list)). This makes cl-store to
store only a single cons and repeat the same process to the cdr of the list.
This simple change should make cl-store backward compatible and will fix
this issue, although it is not optimal to, for instance, this list:

'(0 1 [...] 1000000 . #1=(1000001 . #1#))

It would take something in the order of factorial(10^6) ~ 10^12 steps to
execute this.

I attached a patch which implements this idea, plus a regression test for
this case. Initially I wrote the test binding a list to '(0 . #1=(1 2 3 .
#1#)), but in case of failure it would hang, it printed the form as if
*print-circle* = nil even if *print-circle*=t.

The regression test fails for the current version (I tested it) but passes
successfully when the patch is applied.

Actually, there is still a bug in this sense,

Gustavo.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/cl-store-devel/attachments/20090216/6aa813ae/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch
Type: application/octet-stream
Size: 1279 bytes
Desc: not available
URL: <https://mailman.common-lisp.net/pipermail/cl-store-devel/attachments/20090216/6aa813ae/attachment.obj>