[egit-dev] How a jgit merge could work - examine StrategySimpleTwoWayInC

["Halstrick, Christian" <christian.halstrick@xxxxxxx>]

Hi,

I am working on adding diff & merge functionality to jgit. Today I had long
debugging sessions through existing parts of these functionalities in class
StrategySimpleTwoWayInCore. I thought that this work is valuable for other
developers so I wrote some kind of pseudo code which should illustrate the
basic idea. Be careful: I left out a lot of stuff and at lot of references
are not explained ... but it may serve as a starting point to discuss where
and how the merge could be added.

It would be great to get some comments of the jgit-experts (Hi Shawn, Robin)
whether I got the idea of the merge. Should I continue posting strange pseudo
code explaining jgit internals or is there no interest?

# this merge will merge two(?) commits. It will already do all the work
# unless we have conflicts in the file content - here the content diff/merge
# is missing. E.g. if a file was only touched in one of the commits it will
# be there in the merge result. Files untouched in both commits are of course 
# also in the merge result
StrategySimpleTwoWayInCore InCoreMerger {
...
Treewalk walk;
...
merge(AnyObjectID[] tips)
	RevObject[] sourceObjects = walk.parseEntry(t) foreach t in tips
	RevCommit[] sourcecommits = walk.parseEntry(o) foreach o in sourceObjects 
	RevCommit[] sourceTrees = walk.parseTree(o) foreach o in sourceObjects
	return mergeImpl()

mergeImpl()
	# get a special TreeWalk which ensures that can detect file/folder
	# conflicts. E.g. commit A has added file d/alpha and commit B has
	# added folder d/alpha/
	tw = new NameConflictTreeWalk()
	tw.add(mergeBase(0,1), sourceTrees)
	hasConflict = false
	builder = cache.builder()
	foreach t in tw
		if t.OURS.mode == t.THEIRS.mode && t.equal(OURS, THEIRS)
			# ours & theirs are the same -> choose one
			builder.add(OURS, Stage0)
			continue
		elseif t.BASE.mode == t.OURS.mode && t.equal(BASE, OURS)
			# ours was not changed -> take theirs
			builder.add(THEIRS, Stage0)
		elseif t.BASE.mode == t.THEIRS.mode && t.equal(BASE, THEIRS)
			# theirs was not changed -> take ours
			builder.add(OURS, Stage0)
		elseif t.isSubtree()
			# at least for one of the trees we are processing a
			# folder. If for any other tree we are processing a 
			# file then this is a file/directory conflict
			if nontree(BASE)
				hasConflict = true
				builder.add(BASE, Stage1)
			if nontree(OURS)
				hasConflict = true
				builder.add(OURS, Stage2)
			if nontree(THEIRS)
				hasConflict = true
				builder.add(THEIRS, Stage3)
			tw.entersubtree()	# prepares tw to return childrens
						# in the next iteration
		else
			# here a file-content-based merge algorithm could start
			builder.add( (BASE, Stage1), (OURS, Stage2), (THEIRS, Stage3) )
	if (hasConflict)
		return false
	else
		cache.writeTree()
		return true

mergeBase()
	walk.setRevFilter(MERGE_BASE)
	walk.markStart(sourceCommits[0],sourceCommits[1])
	base = walk.next()
	if (walk.next()!=null) throw "Multiple merge bases ..."
	return base
}