On Jul 15, 2004, at 8:22 AM, goran.krampe at bluefish.se wrote:

Hi Göran,

I've snipped out the bulk of your original post, as my response is very 
simple: please don't stop working on SqueakMap. Squat is an interesting 
experiment, has lots of potential, is very cool, etc. SqueakMap is an 
essential part of the infrastructure that the community depends on 
today. A large part of the progress we've made in the last couple of 
years is directly attributable to SqueakMap. Please don't abandon it 
just because Squat may eventually offer similar functionality.

> In fact - the coolest thing would be if someone could build me a 
> mechanism which can take an instance A (of SMSqueakMap) and an 
> instance B and then compare them and figure out the differences. If I 
> had that - then a user could do local modifications to the map - say 
> add a new release of a package - and then "commit" them to the server. 
> It would first compute the differences made by comparing the current 
> modified map with the latest snapshot on disk - and send the 
> differences over the wire to the master server. The master would then 
> either say "No conflicts, committed" or "Conflicts detected - they are 
> these" and the user would have an opportunity to undo selected 
> conflicting changes and try to commit again.
>
> So... I want a smart Smalltalk diff/patch but for *objects* and not 
> Strings. Anyone up to the task? Magma should in essence already have 
> this capability somewhere in there I think. :)

Well, I've been working on something a bit like this for Monticello. 
The thing is, a general diff/patch algorithm for arbitrary graphs of 
objects is really, really hard. (Or I'm completely missing something. 
If I am let me know - I'd love to be wrong about this.) OODBs have a 
bit of an advantage because (a) all objects have unique ids and (b), 
you only have to keep track of which objects are dirty, not how to 
replicate the changes.

The shortcut I'm taking for Monticello is to insist that the objects 
form a tree, rather than a directed graph. That makes it just "very 
hard," rather than "next-to-impossible." (Diffing unordered trees has 
been shown to be NP-complete.) Another wrinkle I'm adding is that I 
want to make the patches comprehensible to human-beings, and not merely 
capable of transforming one tree into another.

Right now, the algorithm is only partially implemented. It passes a 
bunch of unit tests, but it can't actually compare two trees and 
produce a patch yet. The good news is that it's well separated from 
Monticello. When it's done it should be possible to apply it to other 
domains without too much work. Naturally I'll put it on SqueakMap when 
it's actually useful.
As always, bleeding-edge versions are available from my public 
repository. (The package is called "DiffEng" for Difference Engine.)

http://monticello.wiresong.ca/ob

Because of the restriction to object trees rather than arbitrary DGs, 
it might or might not be useful for SqueakMap (someday).

Cheers,

Colin