snapshot serialization/deserialization improperly handles non-linear cons cell structures
I use queues, as defined in the PAIP book. When saving/restoring snapshot of a prevalence system containing such a queue, the queue is restored incorrectly.
The queues are implemented as lists, but in addition to a reference to the list, queue stores a reference to the last cons of that list.
As queue needs pair of references - the list and its last cons - the queue uses another cons cell: CAR refers to the last element, and CDR refers to the queue content - the list.
For example, after executing this:
(let ((q (make-queue))) (enqueue 1 q) (enqueue 2 q) q)
the variable Q stores the cons structure illustrated on the CAM00125.jpg attached to this issue.
But cl-prevalence serialized doesn't understand that the last cons cell is referenced twice. Instead, each time it encounters the last cell, the cell is treated as new instance. Therefore, when deserialized, the last cell is duplicated. See the red illustration on CAM00126.jpg attach.
Since then queue operations don't work anymore of course, as the queue structure is not correct.
The queues code may be found here: http://norvig.com/paip/auxfns.lisp search for the section beginning with ;;;; Queues
To summarize, cl-prevalence serializer is prepared to handle circular lists, but not prepared for non-circular, but non-linear cons structures. Such structures are considered to be just proper lists.
As a quick workaround for this issue, I redefine function s-serialization::sequence-type-and-length in the file src/serialization/serialization.lisp like this:
(defun sequence-type-and-length (sequence) (if (listp sequence) (values :circular-list nil) ;; (handler-case ;; (let ((length (list-length sequence))) ;; (if length ;; (values :proper-list length) ;; (values :circular-list nil))) ;; (type-error () ;; (values :dotted-list nil))) (values :proper-sequence (length sequence))))
In result cl-prevalence serializer handles each cons cell separately, accounting for possible multiple references.