Backtracking with collections

I was trying to use the #states method to record the state of a
collection. It wasn't working properly for various reasons, but in the
process, I found that the register: and restoreFrom: mechanism doesn't
work for collections if become: was used to change the collection size
between the register: and the restoreFrom:.

This happens naturally in OrderedCollections (this is the way they grow
- at least in VW).

Try these examples:

| array |
array := #(1 2 3 4 5) copy.
array restoreFrom: #(4 5 6) copy.
array

--->  #(4 5 6 nil nil)


| array |
array := #(1 2 3) copy.
array restoreFrom: #(4 5 6 7 8) copy.
array


--> Index out of bounds exception

Michael Lucas-Smith tried it in Squeak and the first example produced  
#(4 5 6 4 5) and the second one produced: #(4 5 6).

To do this properly, you'd first have to create a new collection of the
proper size, use a become: to change the original collection back, then
restore it to the proper values using the existing restore mechanism.

Am I out to lunch on this one or does this change need to be made?

David Buck


_______________________________________________
seaside mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/seaside

Backtracking used to be an area with many bugs in versions prior to
Seaside 2.7. I believe that most of these bugs have been fixed in
Seaside 2.7 for Squeak. I added tests for all of these regressions and
special implementations of #snapshotCopy and #restoreFromSnapshot:
that were necessary in Squeak. Since these fixtures are mostly related
to implementation details of the Squeak collection hierarchy other
platforms probably need other tests to reliably detect backtracking
problems (and we would like to integrate those into the core tests).
Thats why Seaside 2.8 moves #snapshotCopy and #restoreFromSnapshot: to
platform specific code (I just did some more cleanup right now).

This is not how the backtracking API works, #copy is not part of it.
Have a look at WABacktrackingTest:

        original := Array with: 1 with: 2 with: 3.
        snapshot1 := original snapshotCopy.

        original at: 1 put: #a.
        snapshot2 := original snapshotCopy.

        original at: 2 put: #b.
        snapshot3 := original snapshotCopy.

        original restoreFromSnapshot: snapshot1.
        self assert: original = #( 1 2 3 ).

        original restoreFromSnapshot: snapshot2.
        self assert: original = #( a 2 3 ).

        original restoreFromSnapshot: snapshot3.
        self assert: original = #( a b 3 )

>  Michael Lucas-Smith tried it in Squeak and the first example produced
>  #(4 5 6 4 5) and the second one produced: #(4 5 6).

Arrays are considered to be immutable in size in Squeak.

>  To do this properly, you'd first have to create a new collection of the
>  proper size, use a become: to change the original collection back, then
>  restore it to the proper values using the existing restore mechanism.
>
>  Am I out to lunch on this one or does this change need to be made?

You need to implement #snapshotCopy and #restoreFromSnapshot: in
OrderedCollection according to your internal implementation. I guess
#snapshotCopy  just returns a shallow copy (the default), while
#restoreFromSnapshot: can do a #become: of a copy of the snapshot to
the one you want to restore. Or something like that.

Lukas

--
Lukas Renggli
http://www.lukas-renggli.ch
_______________________________________________
seaside mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/seaside

Lukas Renggli wrote:

 | array |
 array := #(1 2 3 4 5) copy.
 array restoreFrom: #(4 5 6) copy.
 array

 --->  #(4 5 6 nil nil)


 | array |
 array := #(1 2 3) copy.
 array restoreFrom: #(4 5 6 7 8) copy.
 array


 --> Index out of bounds exception
    

This is not how the backtracking API works, #copy is not part of it.
Have a look at WABacktrackingTest:
  

Just a note:  The "copy" above was just a VisualWorks work-around to get around immutable literal objects.  I could have said "beMutable" or I could have created the arrays using with:with:with: etc.  For the purpose of this problem, you can ignore the copy.

 Michael Lucas-Smith tried it in Squeak and the first example produced
 #(4 5 6 4 5) and the second one produced: #(4 5 6).
    

Arrays are considered to be immutable in size in Squeak.
  

And I think Arrays should be considered immutable in size.  This mechanism isn't designed for arbitrary become: calls and shouldn't need to worry about that.  My main concern was actually OrderedCollection.  In VW, OrderedCollection contains named and indexed instance variables and grows using become:.  Maybe not the best implementation, but that's what's there.  This mechanism would have trouble with that unless you make a special case for OrderedCollection.

 To do this properly, you'd first have to create a new collection of the
 proper size, use a become: to change the original collection back, then
 restore it to the proper values using the existing restore mechanism.

 Am I out to lunch on this one or does this change need to be made?
    

You need to implement #snapshotCopy and #restoreFromSnapshot: in
OrderedCollection according to your internal implementation. I guess
#snapshotCopy  just returns a shallow copy (the default), while
#restoreFromSnapshot: can do a #become: of a copy of the snapshot to
the one you want to restore. Or something like that.

Lukas

This sounds reasonable.  The snapshotCopy method should be fine as is.  It's the restoreFromSnapshot: that would need to be implemented in OrderedCollection.

Thanks
David Buck


_______________________________________________
seaside mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/seaside