Add support for diff3 conflict style about spork

[slarse]

@wetneb There is unfortunately no simple way to just tack on the base part of the conflict after the merge has completed. The merge algorithm works by removing so-called inconsistencies in the raw merge (which is just the set union of all three ASTs), and iteratively removes anything from the base revision that is inconsistent with either the left or right revision. So, by definition, when the merge has completed and conflicts have been resolved, the base part of any conflict is already gone.

For a brief definition of the merge algorithm, you can refer to section 2.2 of the whitepaper (a preprint is freely available on arxiv). For a significantly more in-depth explanation with worked examples, you may refer to Chapter 4 of my master's thesis (note: it's quite a long read).

I never had time to get around to even experimenting with outputting the base revision due to being short on time, but off the top of my head I can imagine two potential ways of resolving the base part of a conflict. Do note that these are ideas born from thinking through code I wrote 4 years ago, so I can't guarantee either will work in practice.

• When removing inconsistencies, keep track of which base revision PCS triples are removed by what left/right revision triples.
• When outputting conflicts, use the base/left or base/right mappings to find the corresponding part of the base revision.

It feels a bit weird: intuitively the parser should not need to know about how we want to display conflicts.

This is the canonical way to use Spoon: set the environment first (which includes the pretty printer), and then parse, analyze/transform and pretty print with that environment. Setting of the printer requires modifications to the environment, and doing that at any time after parsing would be a bit unexpected. There also was never a reason to leave this configurable before, so there's that as well. Feel free to put up a PR with improvements.

[monperrus]

Great idea, would you do a pull request?

[wetneb]

It's not actually clear to me if the algorithm used to generate the conflicts allows for generating a "base" part alongside the "left" and "right" ones.

This seems to be the place where the "left" and "right" parts are currently extracted:

spork/src/main/kotlin/se/kth/spork/spoon/pcsinterpreter/SporkTreeBuilder.kt

Lines 213 to 226 in e440feb

	private fun traverseConflict(
	nextPcs: Pcs<SpoonNode>,
	conflicting: Pcs<SpoonNode>,
	children: Map<SpoonNode, Pcs<SpoonNode>>,
	tree: SporkTree,
	): SpoonNode {
	remainingInconsistencies.remove(nextPcs)
	remainingInconsistencies.remove(conflicting)
	listOf(Revision.LEFT, Revision.RIGHT).forEach(tree::addRevision)
	val leftPcs = if (nextPcs.revision === Revision.LEFT) nextPcs else conflicting
	val rightPcs = if (leftPcs === nextPcs) conflicting else nextPcs
	val leftNodes = extractConflictList(leftPcs, children)
	val rightNodes = extractConflictList(rightPcs, children)
	val resolved = tryResolveConflict(leftNodes, rightNodes)

Not being familiar with the PCS structure, it's not clear to me if there is a simple way to also generate the "base" part in this context. I don't even know if it actually makes sense - it's unclear to me to what extent the base revision is relied on, so it can well be that there are cases where only the left and right revisions are compared, without the ability to trace elements back to the base revision?

@monperrus are you clear on this?