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

[Sean Ross]

Right, I've pushed a change to the darcs repository and released a new  
version (0.8.9) of cl-store which fixes this issue and improves the  
general performance
when serializing lists (they are now serialized in a single pass).

Additionally I've added a *precise-list-storage* special variable  
which, when bound to true, will ensure that all lists stored
will have all shared substructure correctly serialized and  
deserialized. The only downside of this approach is that it will
blow the stack on large lists.

And, just for fun, I've added a small optimization for T and NIL which  
adds special serializers for them rather than storing them as symbols.

All the tests still pass, but please drop me a line if anything breaks.

Cheers,
  Sean.


On 16 Feb 2009, at 21:30, Gustavo wrote:

>  (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.
>
> _______________________________________________
> cl-store-devel mailing list
> cl-store-devel at common-lisp.net
> http://common-lisp.net/cgi-bin/mailman/listinfo/cl-store-devel

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