Design advice on a merge abstraction

[sageserpent-open]

Hi all,

A request for some design advice. Get yourself a brew, it’s a long one…

Background:

I have an abstraction to represent merges (in the sense of merging file content, eg. Git merge) that looks like this…

trait MergeResult[Element]:
  def transformElementsEnMasse[TransformedElement](
                                                    transform: IndexedSeq[Element] => IndexedSeq[TransformedElement]
                                                  )(using equality: Eq[TransformedElement]): MergeResult[TransformedElement]

  /** Yields content in a form suitable for being potentially nested within
   * either side of a larger [[MergedWithConflicts]]. This is necessary because
   * Git doesn't model nested conflicts, where one side of a conflict can
   * contain a smaller conflict. <p>This occurs because splicing can generate
   * such nested conflicts housed within a larger conflict between move
   * destination anchors on one side (with the splice) and some other
   * conflicting content on the opposite side to the anchors.
   *
   * @return
   * The elements as single [[IndexedSeq]].
   * @see
   * https://github.com/sageserpent-open/kineticMerge/issues/160
   */
  def flattenContent: IndexedSeq[Element]

The merge result abstraction generalises an indexed sequence of elements to be either a resolved merge or a conflicted merge, which at the moment is either a single indexed sequence for a fully resolved merge, or two indexed sequences for the left and right halves of a conflicted merge.

Note that no attempt is made to localise fine-grained conflicts - it’s all or nothing over the entire file content, so you get a ‘left-side’ and a ‘right-side’, these correspond to Git stage entries in a conflicted merge.

So far, so good - that all works very nicely.

It gets a bit more complicated in that the various transforms applied end up falling into four categories:

1. A filtration, so the sequence element type doesn’t change, but elements can be dropped.
2. A map-accumulate, in this case the sequence element type doesn’t change, but elements can be added or dropped or transmogrified - all in the context of previously processed elements.
3. A left-fold, but as it turns out, this is really another map-accumulate in disguise.
4. A flat-map of sorts, where the inner-type yielded by the operation being flat-mapped is an indexed sequence that should be concatenated into the resulting sequence. The element types change too.
5. A map; the element types change.

Note that all these transforms are expressed wrt to the indexed sequence abstraction, not MergeResult.

There is also a rather hokey flattening operation on MergeResult that converts one to a simple indexed sequence (regardless of whether resolved or conflicted), and the less said about that the better, only it is unavoidable. Shrug.

What I want to do:

A. Finesse MergeResult so that it can model localised conflicts - so whereas for a fully resolved merge one would have an implied indexed sequence of elements, one with conflicts could be thought of as being a dag of elements with (hopefully) mostly long straight runs representing partially resolved output and the odd competing runs of elements representing local conflicts (or one run competing against a direct shortcut between elements - this models a deletion versus edit conflict).

B. Make those five kinds of transform into a first-class part of the API for MergeResult. This isn’t just to scratch an itch, the point is that with finer grained conflicts, there is no longer a single sequence of elements to pass to the transform - the operations apply in a more localised form, tracking the straight sections and competing sides of the local conflicts separately. This also has to take context into account for the map-accumulate / left-fold situations.

C. Finesse the flattening, so that instead of unconditionally flattening a MergeResult into an indexed sequence, there is an operation of MergeResult[MergeResult[Element]] => MergeResult[Element] that will inline a localised conflict directly into an enclosing non-conflicted straight run, and will inline a straight run into the relevant side of an enclosing conflict. Where one conflict is nested within one side of another, then the same kind of hokey outcome as with the current flattening takes place, and that’s OK.

Where I’ve got to:

It’s fairly straightforward to cutover MergeResult to internally represent the localised conflicts using a dag approach, and the operations to build one up pretty much write themselves. So that’s item A done.

I’m less certain about item B. My current thoughts are to hoist those four operations into the API of MergeResult, being a bit cavalier about the difference between a MergeResult on one hand as being a collection-like / monad-like thing and IndexedSeq on the other also being collection-like / monad-like.

So:

trait MergeResult[Element]:
  def mapAccumulate[State, Transformed](seed: State)(
      operation: (State, Element) => (State, Transformed)
  ): (State, MergeResult[Transformed])

  def map[Transformed](
      transform: Element => Transformed
  ): MergeResult[Transformed]

  def flatMap[Transformed](innerTransform: Element => IndexedSeq[Transformed]): MergeResult[Transformed]

Note that the flat-map’s inner transform yields an indexed sequence - so this is rather like flat-mapping over a collection to yield optional inner results in the standard library; a mixed flat-map.

Now for item C. The only place where this is required is after doing one of the map-accumulates, not when doing the mixed flat-mapping. Of course, if I admitted that one of the two map-accumulates actually end up building a MergeResult[MergeResult[Element]], then perhaps this could be expressed more directly in the API. A kind of flatMapAccumulate?

Curious to know your thoughts…

[Ichoran]

I think the core algorithmic challenge here is to go from a well-defined sequence to a birooted directed acyclic graph. Because if you have stuff in common, then a conflict, then more stuff in common, the only real constraint is that you start at the beginning (one root) and end at the end (the other root).

What I don’t see in your solution-thus-far is anything that really grapples with this aspect of the nature of it. Some of it is simplified if you handle only two-way rather than n-way merges, but it’s worth solving the general problem conceptually before deciding the simplification is enough. Maybe you don’t need to grapple with it? But it seems like a good idea to do so to me.

map is trivial. Just recreate the structure with different content at each node.

filter is still a sensible operation from graph to graph; however, you can’t just filter the pieces and call it a day because you might filter a bifurcation into a linear path if you filter out everything on one side.

fold in the ordinary sense doesn’t work because there are an arbitrary number of different paths that could be taken–so which one are you folding? You can fold any linear segment, but not the structure as a whole unless you limit yourself to two-way merge so that you have either one or two paths at any time, each of which is delimited. Then fold could be structured to produce two outputs.

The flatMap of sorts seems like a generalization of filter where in addition to removing elements, you can change or add them also (but dependent only on the current element). The logic is actually identical–you can’t create branches with this, and they might disappear.

The mapAccumulate seems like a generalization of fold and flatMap in that you carry along a state which you have to duplicate across all branches, but you don’t have to worry about returning the howevermany results because it will only preserve structure if you merge the states when a bifurcation resolves into a single path again. Otherwise you will have to unfold your birooted DAG into a tree. (Your type signature doesn’t include this.)

So actually everything is a mapAccumulate. foldMap is a mapAccumulate with Unit state and trivial merge. fold if it works at all is a mapAccumulate with the identity transform and which returns the state instead of the (unchanged) structure. filter is a foldMap where the only options are to keep an element or drop it. map is a foldMap where the only thing to do is change the element.

Linearization is yet again another mapAccumulate where now you have to allow one new feature: when you merge, you are allowed to prepend zero or more items on the basis of the merged states. Then the state simply accumulates the elements; and when merging, you take the two traced states and do whatever you do to linearize and prepend them to the following content.

So it seems like everything you are thinking about involves implementing one method:

class Dag[E <: Element]():
  def transmogrify[S, EE <: Element](
    zero: S,
    op: (S, E) => (S, Seq[EE]),
    fuse: (S, S) => (S, Seq[EE])
  ): (S, Dag[EE]) = ???

This isn’t a very efficient way to do a fold, of course, so you might not want to write it this way. But unless I’m mistaken about what you’re after, it sounds like your design boils down to writing this one function.

(Note: if fuse is not commutative, you might have to write fuse: Seq[S] => (S, Seq[EE]) to handle a n-way merge all in one go.)

Anyway, not sure if this is helpful because I’m not sure I understand your constraints and goals well enough; but that’s my perspective on the problem.

[sageserpent-open]

@Ichoran That’s a nice considered reply, thanks.

I’ll think over this, but a couple of replies in-line in case you’re interested further, but no pressure…

@Ichoran

Because if you have stuff in common, then a conflict, then more stuff in common, the only real constraint is that you start at the beginning (one root) and end at the end (the other root).

Actually, not quite - you could start and / or end with a conflict, or even just have one big conflict - so the dag degenerates into a two chain forest.

There is a constraint though in that both resolved straight runs and conflicts are coalesced as far as possible, so there is a strict alternation between resolved parts and conflicted parts, thinking of these as ‘boxes’ around parts of the implied dag.

@Ichoran

Some of it is simplified if you handle only two-way rather than n-way merges, but it’s worth solving the general problem conceptually before deciding the simplification is enough. Maybe you don’t need to grapple with it?

I made a scope decision very early on with Kinetic Merge not to do octopus merging, so only two lines of development ever get merged wrt a common base commit. (Furthermore, only one best common base commit is supported for now. I can count on the fingers of one hand the number of times I’ve encountered multiple ambiguous best common base commits due to criss-cross merging etc in the last 15 years or so of Git, and previously whenever using Clearcase.)

If folks want to merge in multiple branches, then the expectation is to merge them one-by-one.

So the conflicts only ever have two sides, so to speak - left and right.

@Ichoran

filter is still a sensible operation from graph to graph; however, you can’t just filter the pieces and call it a day because you might filter a bifurcation into a linear path if you filter out everything on one side.

That is an excellent insight. It’s more subtle than this in practice, because there are several kinds of conflict to consider: left-edit versus right-edit, left-deletion versus right-edit, left-edit versus right-deletion and left-insertion versus right-insertion.

Kinetic Merge is more stringent than core Git in that it considers a deletion versus edit conflict to be important, whereas core Git simply goes with the edit. So if an edit versus edit conflict is whittled down to a deletion versus edit conflict, it still stays as a conflict. On the other hand, if a conflict with an edit is whittled down on both sides, it should vanish. Insertion conflicts can also be whittled down to resolved insertions from just one side, or vanish completely.

There is a final twist when a transformation makes both sides of a conflict equivalent, in which case this becomes resolved. I’ve never seen this in the wild, but it is currently supported.

@Ichoran

The mapAccumulate seems like a generalization of fold and flatMap in that you carry along a state which you have to duplicate across all branches, but you don’t have to worry about returning the howevermany results because it will only preserve structure if you merge the states when a bifurcation resolves into a single path again. Otherwise you will have to unfold your birooted DAG into a tree. (Your type signature doesn’t include this.)

Ah, not quite: something that carries over from the original implementation design is the notion of there being a left side and a right side to the merge result. So even though there are localised conflicts and thus an implied dag, there are only two paths that accumulation etc have to follow. Perhaps thinking of this as a dag under the hood is too suggestive - I think in terms of the dag being partitioned into boxes.

Really, what I’m after is a way of doing parallel left and right traverses (loosely in the sense of Cats traverse / foldable) along those two paths, but keeping a sense of what box the traversal is in so that the box structure is preserved, subject to the whittling down from above.

As the two paths are parallel, there is no need to fuse state on exit from a conflicted box.

Sorry, should have made that clearer in the first place, but this conversation is helping me clear my thinking, so good.

Thinking about this, I’m leaning towards a mixed ‘flat-map-accumulate’ where each ‘output’ of the map-accumulate is concatenated into the result, which has to be another MergeResult - so a more opinionated type signature than the standard map-accumulate, in that it acknowledges the underlying indexed sequences that need to be concatenated on the fly.

@Ichoran

Anyway, not sure if this is helpful because I’m not sure I understand your constraints and goals well enough; but that’s my perspective on the problem.

It’s been very useful, thanks for taking the time to plunge into somebody else’s design swamp.

[sageserpent-open]

Hmm, carrying on with the theme of boxes of indexed sequences, I’m realising that there are two levels of flat-mapping and map-accumulating / folding that I’m trying to conflate into one thing, namely the overall MergeResult.

I had thought about this before, but shield away from having to write two-level folds and flat-maps because of the boilerplate of joining up the two levels in client code. I want it all to happen on the inside of the MergeResult abstraction.

Think of doing a left-fold of a tree of sequences as an example of a two-level fold - it has to jump in and out of each tree node to fold along each sequence, but also fold the whole lot across the tree.

Flat-mapping is similar, you would have to concatenate the sequences on one hand, but also inline a tree into a larger one on the other.

I wonder if there’s a nice way of expressing this in Cats… ?

[sageserpent-open]

Epilogue: I tried to cutover the existing client code to use the tentative new API and realised that the left-fold and map-accumulate have a postprocessing step using the accumulated state after them - in one case the postprocessing invokes the same transform that it lives in tail-recursively. So trying to express a map-accumulate up in MergeResult leads to all kinds of problems, notably because both sides of the merge can lead to different states when there are conflicts, which leads to fun and games with postprocessing, especially with (tail) recursion.

What I settled on follows. I’ve left the implementations out for the sake of clarity:

case class MergeResult[Element: Eq] private (segments: Seq[Segment[Element]]):
  // Resolved and conflicting segments should be coalesced.
  require(segments.isEmpty || segments.zip(segments.tail).forall {
    case (Segment.Resolved(_), Segment.Conflicted(_, _)) => true
    case (Segment.Conflicted(_, _), Segment.Resolved(_)) => true
    case _                                               => false
  })

  def addResolved(element: Element): MergeResult[Element] = ???

  def addResolved(elements: Seq[Element]): MergeResult[Element] = ???

  def addConflicted(
      leftElements: Seq[Element],
      rightElements: Seq[Element]
  ): MergeResult[Element] = ???

  // TODO: remove this...
  def flattenContent: Seq[Element] = ???

  def map[Transformed: Eq](
      transform: Element => Transformed
  ): MergeResult[Transformed] = ???

  def innerFlatMap[Transformed: Eq](
      transform: Element => Seq[Transformed]
  ): MergeResult[Transformed] = ???

  def filterNot(predicate: Element => Boolean): MergeResult[Element] = filter(
    predicate.andThen(!_)
  )

  def filter(predicate: Element => Boolean): MergeResult[Element] = ???

  // The result has the same localised conflict structure as `this`,
  // subject to conflicts not being 'ironed-out' or introduced by the transform.
  def onEachSide[Transformed: Eq](
      transform: MergeResult.Side[Element] => MergeResult.Side[Transformed]
  ): MergeResult[Transformed] = ???

end MergeResult

object MergeResult:
  def empty[Element: Eq]: MergeResult[Element] = MergeResult(
    IndexedSeq.empty
  )

  case class Side[Element: Eq](
      elementsWithSegmentLabels: Seq[(Element, Int)]
  ):
    def innerFlatMapAccumulate[State, Transformed: Eq](initialState: State)(
        statefulTransform: (State, Element) => (State, Seq[Transformed])
    ): (State, Side[Transformed]) = ???

    // Used when post-processing what comes out of `innerFlatMapAccumulate`.
    def append(elements: Seq[Element]): Side[Element] = ???
  end Side

  enum Segment[Element: Eq]:
    this match
      case Resolved(elements)                      => require(elements.nonEmpty)
      case Conflicted(leftElements, rightElements) =>
        // NOTE: it's OK if just *one* side is empty.
        require(leftElements.nonEmpty || rightElements.nonEmpty)
        require(!leftElements.corresponds(rightElements)(Eq.eqv))
    end match

    case Resolved(elements: Seq[Element])(using eq: Eq[Element])
    // Don't bother representing different flavours of conflicts, namely left
    // edit / right edit, left deletion / right edit, left edit / right deletion
    // or left insertion / right insertion.
    // `MergeAlgebra`, and that is fine as it is for now.
    case Conflicted(
        // If this is empty, it represents a left-deletion.
        leftElements: Seq[Element],
        // If this is empty, it represents a right-deletion.
        rightElements: Seq[Element]
    )(using eq: Eq[Element])
  end Segment
end MergeResult

extension [Element](mergeResult: MergeResult[MergeResult[Element]])
  def flatten: MergeResult[Element] = ???
end extension