Issue #2 new

snapshot serialization/deserialization improperly handles non-linear cons cell structures

avodonosov avataravodonosov created an issue

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.

Comments (0)

  1. Log in to comment
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.