Comparing object graphs (was: The future of SM...)
Colin Putney
cputney at wiresong.ca
Tue Jul 20 23:26:46 UTC 2004
Göran wrote:
> 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. :)
I replied:
> 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..
Chris concurred:
> An interesting, very tough problem.. Too tough for me.
And finally, Stephan Rudlof wrote:
> Some way to go is to look for XML diff algorithms. They compare XML
> files.
>
> A Smalltalk class hierarchy can be exported as XML:
> - classes
> - name
> - superclass name
> - inst var names
> - method names
> - method bytecode hashes (!)
> - optional: method source (not so important than the previous point)
> ...
> After that these XML exports could be diffed.
>
> Of course the diff problem is hard and the patch problem is harder than
> that: there are more than one ways to convert one XML graph into
> another...
> But the benefit is to get an idea of
> - how far two different Smalltalk systems are away from each other,
> - *where* they differ,
> - and - last but not least - how much the porting effort of some
> software could be ... (!)
Hi Stephane,
This is more or less the approach I have taken for Monticello. XML has
spurred research into tree-diffing algorithms, since straight text
diffs only sort-of-work for XML. The various algorithms I've run across
all make different trade-offs; the one I've selected aims for simple,
and can be adapted to the "ugly" trees that Smalltalk source-code
forms, but is quite complex and (possibly) slow on really large trees.
On the other hand, this is a simplified version of the general problem
that Göran and Chris were talking about - the ability to diff and patch
any graph of objects, not just source code (which, luckily, can be
restricted to a tree without many problems.)
Colin
More information about the Squeak-dev
mailing list
|