From: Gavin Kistner <gavin@...>
Date: 2005-08-22T02:24:21+09:00
Subject: Diffing/Merging Hierarchical Trees

Imagine an XML file (with no Text nodes) where every node has a  
unique id.

Imagine a user modifies a copy of this file. Modifications include  
adding some new nodes (deep in the hierarchy), modifying properties  
on a couple other nodes, and deleting some other nodes.

Imagine that the original XML file changes. I want to re-apply the  
work that user did, using the modified tree. I want to get a set of  
commands from a diff between the user's work and the original, and  
then apply those commands to the changed original.

This is more than a 3-way text merge primarily because nodes can be  
re-ordered or moved to a new point in the hierarchy, but the presence  
of the unique identifier on each node makes it possible to absolutely  
know that this is not a new node.

...

Anyone know of any projects that do this sort of thing? Algorithms?  
White papers? Web pages?