
<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>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</div><div>when serializing lists (they are now serialized in a single pass).</div><div><br></div><div>Additionally I've added a *precise-list-storage* special variable which, when bound to true, will ensure that all lists stored</div><div>will have all shared substructure correctly serialized and deserialized. The only downside of this approach is that it will</div><div>blow the stack on large lists.</div><div><br></div><div>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.</div><div><br></div><div>All the tests still pass, but please drop me a line if anything breaks.</div><div><br></div><div>Cheers,</div><div> Sean.</div><div><br></div><br><div><div>On 16 Feb 2009, at 21:30, Gustavo wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"> (sorry, I didn't want to send the e-mail yet). <br><br><div class="gmail_quote">2009/2/16 Gustavo <span dir="ltr"><<a href="mailto:gugamilare@gmail.com">gugamilare@gmail.com</a>></span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> Hello,<br><br>CL-Store can handle storing normal circular lists, but it can't store correctly the circularity on lists like this particular list:<br><br><span style="font-family: courier new,monospace;">'(0 . #1=(1 2 3 . #1#))</span><br> <br>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.<br><br><span style="font-family: courier new,monospace;">cl-user> (setf *print-circle* t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">t</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">cl-user> (cl-store:store '(0 . #1=(1 2 3 . #1#)) "test")</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(0 . #1=(1 2 3 . #1#))</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">cl-user> (cl-store:restore "test")</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">#1=(0 1 2 . #1#)</span><br><br>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:<br> <br><font face="courier new,monospace">'(0 1 [...] </font>1000000 . #1=(1000001 . #1#))<br><br>It would take something in the order of factorial(10^6) ~ 10^12 steps to execute this.<br><br>I attached a patch which implements this idea, plus a regression test for this case. Initially I wrote the test binding a list to <span style="font-family: courier new,monospace;">'(0 . #1=(1 2 3 . #1#))</span>, but in case of failure it would hang, it printed the form as if *print-circle* = nil even if *print-circle*=t.<br> <br>The regression test fails for the current version (I tested it) but passes successfully when the patch is applied.<br><br>Actually, there is still a bug in this sense, </blockquote><div> </div><div>well, if you call it a bug. It can also be a choice of design.<br> <br>In test circ.16, the following list<br><br><span style="font-family: courier new,monospace;">'#1=(1 #2=(#1#) . #2#)</span><br><br>is not exactly like this list<br><br><span style="font-family: courier new,monospace;">'#1=(1 (#1#) #1#)</span><br> <br><span style="font-family: courier new,monospace;">cl-user> (defvar mylist '#1=(1 (#1#) #1#))</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">mylist</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">cl-user> mylist</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">#1=(1 (#1#) #1#)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">cl-user> (defvar mylist2 '#1=(1 #2=(#1#) . #2#))</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">mylist2</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">cl-user> mylist2</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">#1=(1 #2=(#1#) . #2#)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">cl-user> (eq (cadr mylist) (cddr mylist))</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">nil</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">cl-user> (eq (cadr mylist2) (cddr mylist2))</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">t</span><br><br>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.<br> 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 <span style="font-family: courier new,monospace;">(cadr mylist)</span> and <span style="font-family: courier new,monospace;">(cddr mylist)</span> are eq.<br> <br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br><font color="#888888"><br>Gustavo.<br> </font></blockquote></div><br> _______________________________________________<br>cl-store-devel mailing list<br><a href="mailto:cl-store-devel@common-lisp.net">cl-store-devel@common-lisp.net</a><br><a href="http://common-lisp.net/cgi-bin/mailman/listinfo/cl-store-devel">http://common-lisp.net/cgi-bin/mailman/listinfo/cl-store-devel</a><br></blockquote></div><br></body></html>