In case it's not obvious, I'm gearing into the merge problem. I decided to bite this off before releasing because it's the right way to implement the equivalent of 'cvs update'.
As previously mentioned, the merge operates on triples of the form (working entity, common ancestor, entity to be merged). The merge itself is straightforward; Josh has done a wonderful job describing his merge strategy and I plan to just liberate it. The challenge seems to lie in computing the triples in the face of renames.
You might think that if the working and merge entities have the same workspace name, we can reasonably assume that they are the right things to merge, but consider what happens when:
workspace:
modify entity A
merge path
rename A to B
rename X to A
Note that merge.A and workspace.A have no common ancestor.
The saving grace is that ancestors, if they exist, are always unique. In the case above, X and A simply won't have a common ancestor at all, and with enough work we can figure this out.
We can fully expand the ancestor tree of everything and do an exhaustive pairwise comparison, but there surely has to be a better way. At the moment, the best strategy I can think of goes as follows:
for depth D in 1 to infinity
for all entities in workspace, in merge path
expand ancestry list to depth D
for each entity in workspace
for each entities in merge path
check for common ancestor
if found, remove triple from unresolved pool
Iterate until done or until no more ancestor matches are found (orphans).
Does anyone see a better algorithm? Is there some additional way to bound the expansion so that we don't have to completely expand the entities that might (but won't) match those that have no predecessor?
shap