Re: git subtree bugs (mishandled merges, recursion depth)

Colin Stagner writes ("Re: git subtree bugs (mishandled merges, recursion depth)"):

Hi.  (For future reference, that patch series is
  [PATCH v2 0/3] contrib/subtree: reduce recursion during split
in the other thread.)

I have some thoughts about this.

I didn't find a formal description of git-subtree's data model, or how git subtree split works, precisely. So I'm going to make some suppositions.

I observe that git-subtree split doesn't record any metadata in the split versions of the commits (for example, the downstream project commitid they were split from).

Repeated splits ought ideally not to constantly generate additional material. So the algorithm ought to be deterministic. An easy way to do that is to make splitting a pure function from downstream commits to subtree commits.

If one can run git subtree split on every commit in the downstream that has a git subtree merge as an ancestor, then one might think that means the split must produce as many commits as there are in the downtream.

But we can map multiple downstream commits to the same subtree commit. Consider the cases, for some downstream commit D.

 0. D is a single parent commit that *does* change the subtree.
    This becomes a new commit with parent split(D~).

 1. D is a single parent commit that doesn't change the subtree:
    We reuse the parent's split: split(D) = split(D~)

 2. D is a multi-parent commit.  Determine \forall{i} split(D^i).
    Discard all split(D^i) which are ancestors of any split(D^j).
    If any remaining split(D^i) is not subtree-treesame D,
    or there is more than one remaining split(D^i),
    construct a new commit with those remaining split(D^i) as parents.
    Otherwise all remaining split(D^i) are the same,
    and they are treesame to D, so discard: split(D) = split(D^i).

 3. D is a subtree merge commit.  split(D^1) is explicitly stated
    in the git-subtree metadata.  Calculate split(D^0) as above.
    Then calculate split(D) according to point 2.

In fact, 0 and 1 are special cases of 2.

Do you think it would be worth me prototyping this? I think at least for my case it would produce considerably fewer commits, but until I try it that's just guesswork.

Ian.