dolt_merge_base is non-deterministic on multi-LCA criss-cross merges

[timsehn]

Summary

dolt_merge_base(C, D) returns different results on repeated invocations of the same scenario when C and D have multiple maximal common ancestors (the classic criss-cross merge case). Across 10 runs of the setup below, the function returned commit a1 6 times and commit b1 4 times — both are valid maximal LCAs, but dolt_merge_base arguably shouldn't be unstable.

Tested against dolt version 1.88.0 (latest at time of writing).

Repro

Initialize a fresh repo and run:

CREATE TABLE t(id INTEGER PRIMARY KEY, v INT);
INSERT INTO t VALUES (1, 10);
CALL dolt_add('-A');
CALL dolt_commit('-m', 'base', '--date', '2020-01-01T00:00:00');
CALL dolt_branch('A');
CALL dolt_branch('B');
CALL dolt_checkout('A');
INSERT INTO t VALUES (2, 20);
CALL dolt_add('-A');
CALL dolt_commit('-m', 'a1', '--date', '2030-01-01T00:00:00');
CALL dolt_checkout('B');
INSERT INTO t VALUES (3, 30);
CALL dolt_add('-A');
CALL dolt_commit('-m', 'b1', '--date', '2020-06-01T00:00:00');
CALL dolt_branch('C', 'A');
CALL dolt_branch('D', 'B');
CALL dolt_checkout('C');
CALL dolt_merge('B');
CALL dolt_checkout('D');
CALL dolt_merge('A');

Then:

SELECT message FROM dolt_log WHERE commit_hash = dolt_merge_base('C', 'D');

Repeat the SELECT 10 times in fresh dolt sql -c invocations (or in a loop in one session). Observed (in our 10-run sample):

• a1 — 6 times
• b1 — 4 times

Topology

       base (2020-01-01)
       /  \
      A    B
      |    |
     a1    b1
 (2030-01)  (2020-06)
      |\\  //|
      | \\/  |
      |   X  |
      |  /\\ |
      | /  \\|
      C     D
   merge(B) merge(A)

Maximal common ancestors of C and D are {a1, b1} — neither is an ancestor of the other, and base is an ancestor of both. A correct merge_base implementation should pick one of {a1, b1} deterministically (e.g., timestamp-ordered, hash-ordered, or topological).

Expected

dolt_merge_base(C, D) returns the same value on every call for a given pair of commits.

Observed

Result varies across runs — appears to depend on traversal order which is not seeded deterministically.

Discovery context

Surfaced while writing parity oracle tests in doltlite#847 (doltlite implements dolt_merge_base with a deterministic timestamp-then-hash tiebreaker and was failing the Dolt-parity assertion because Dolt's answer wasn't stable). The doltlite oracle now uses an "any maximal LCA is acceptable" helper for these criss-cross cases as a workaround, but the underlying determinism gap in Dolt remains.

Suggested fix direction

After finding the set of maximal common ancestors, apply a deterministic tiebreaker. Options:

• Commit timestamp (max first), then commit-hash lex order as the second tier — what doltlite uses.
• Pure commit-hash lex order — simpler, but loses the "prefer most recent" property.
• Topological order over the commit graph — most "git-like" but more expensive.