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

[Sean Ross]

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



Hi Gustavo,
  Thanks for the report. Yeah, the current storing of lists is pretty  
suboptimal and was changed from storing car + cdr to the current form.
   It's definitely doing the 'wrong thing' at the moment and will also  
fail for shared sublists.

   I'll try and take a look at it this week.

Cheers,
  Sean.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/cl-store-devel/attachments/20090216/6dd10ab1/attachment.html>