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

[Gustavo]

 (sorry, I didn't want to send the e-mail yet).

2009/2/16 Gustavo <gugamilare at gmail.com>

> 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,


well, if you call it a bug. It can also be a choice of design.

In test circ.16, the following list

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

is not exactly like this list

'#1=(1 (#1#) #1#)

cl-user> (defvar mylist '#1=(1 (#1#) #1#))
mylist
cl-user> mylist
#1=(1 (#1#) #1#)
cl-user> (defvar mylist2 '#1=(1 #2=(#1#) . #2#))
mylist2
cl-user> mylist2
#1=(1 #2=(#1#) . #2#)
cl-user> (eq (cadr mylist) (cddr mylist))
nil
cl-user> (eq (cadr mylist2) (cddr mylist2))
t

And storing the former returns a list like the latter. But, yet, both lists
are "similar" - the circularity works the same way. The only fix for this
that I can think of is making storage for every cons cell store its car and
its cdr, but this would be very inconvenient.
I would leave it the way it is, I can hardly imagine a program which
actually uses a list like that one and that needs the fact that (cadr
mylist) and (cddr mylist) are eq.


>
> Gustavo.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/cl-store-devel/attachments/20090216/c7d7efb4/attachment.html>