{"abstract":"History reachable only through a merge's second parent is ignored and the base is too old or missing.","category":"Text diff and three-way merge","checks":10,"contract":"Given a commit graph (commit -> parent list) and two commits, ancestors include the commit itself and all commits reachable through any parent. The merge bases are the common ancestors that are not ancestors of another common ancestor. Return them sorted.","evaluation_group":"w2-text-diff-merge-merge-base-selection","failed_approach":"Following all parents only at the starting commit still drops second parents deeper in history.","family":"w2-text-diff-merge-merge-base-selection-all-parents","id":"FA-75621","implementations":{"attempt":{"sha256":"d3df6bd10c94562e04c1b657df6a5e03b24cd96a8c4829e793be502231a5f911","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(parents, x, y):\n    def anc(c):\n        seen = set()\n        stack = [c]\n        while stack:\n            k = stack.pop()\n            if k in seen:\n                continue\n            seen.add(k)\n            stack.extend(parents.get(k, []) if k == c else parents.get(k, [])[:1])\n        return seen\n    common = anc(x) & anc(y)\n    best = [c for c in common if not any(c != d and c in anc(d) for d in common)]\n    return sorted(best)\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    1: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c3', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c1', 'c2'], ['c1'])],\n    2: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c4', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c1', 'c3'], ['c1'])],\n    3: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c5', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c1', 'c4'], ['c1'])],\n    4: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c6', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c1', 'c5'], ['c1'])],\n    5: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c7', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c1', 'c6'], ['c1'])],\n}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"3e4031f095c60d04588c0fed866a9068c02846b330b84696d07117ea3f7d7fbe","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(parents, x, y):\n    def anc(c):\n        seen = set()\n        stack = [c]\n        while stack:\n            k = stack.pop()\n            if k in seen:\n                continue\n            seen.add(k)\n            stack.extend(parents.get(k, [])[:1])\n        return seen\n    common = anc(x) & anc(y)\n    best = [c for c in common if not any(c != d and c in anc(d) for d in common)]\n    return sorted(best)\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    1: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c3', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c1', 'c2'], ['c1'])],\n    2: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c4', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c1', 'c3'], ['c1'])],\n    3: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c5', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c1', 'c4'], ['c1'])],\n    4: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c6', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c1', 'c5'], ['c1'])],\n    5: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c7', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c1', 'c6'], ['c1'])],\n}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"e02aef2250ef4ee9767bcf2b96f3e4a1adb36390d46fec1e5197f568f906194e","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(parents, x, y):\n    def anc(c):\n        seen = set()\n        stack = [c]\n        while stack:\n            k = stack.pop()\n            if k in seen:\n                continue\n            seen.add(k)\n            stack.extend(parents.get(k, []))\n        return seen\n    common = anc(x) & anc(y)\n    best = [c for c in common if not any(c != d and c in anc(d) for d in common)]\n    return sorted(best)\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    1: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c3', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c1', 'c2'], ['c1'])],\n    2: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c4', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c1', 'c3'], ['c1'])],\n    3: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c5', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c1', 'c4'], ['c1'])],\n    4: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c6', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c1', 'c5'], ['c1'])],\n    5: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c7', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c1', 'c6'], ['c1'])],\n}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"A deterministic, bounded teaching model of one diff, patch or merge rule with stipulated conventions; it is not a production diff or version-control implementation and makes no claim of conformance to any specific tool. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-text-diff-merge-merge-base-selection-all-parents","generated_at":"2026-09-29T14:49:08.382193+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"A three-way merge is only as good as its base; criss-cross histories legitimately have several best common ancestors.","repair":"Follow every parent of every commit.","root_cause":"The ancestor walk extends the stack with the first parent only.","sha256":"687b8283091b4ad821bc731ced11b82a3111c59ff80df09e309bf8d455b3ca1d","title":"Merge base selection: traversal follows only first parents · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":72.546,"exit_code":1,"observations":[{"actual":["B"],"check":"simple fork","expected":["B"],"passed":true},{"actual":["D"],"check":"merge commit sees both parents","expected":["D"],"passed":true},{"actual":["B"],"check":"fast-forward: one side is an ancestor","expected":["B"],"passed":true},{"actual":["D"],"check":"same commit","expected":["D"],"passed":true},{"actual":["X1","Y1"],"check":"criss-cross has two merge bases","expected":["X1","Y1"],"passed":true},{"actual":["c1"],"check":"long chain against a side branch","expected":["c1"],"passed":true},{"actual":["a"],"check":"second parent carries the only common ancestor","expected":["a"],"passed":true},{"actual":[],"check":"unrelated histories","expected":[],"passed":true},{"actual":[],"check":"second parent deeper in history","expected":["a"],"passed":false},{"actual":["c1"],"check":"first commit is the ancestor","expected":["c1"],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"simple fork\", \"actual\": [\"B\"], \"expected\": [\"B\"], \"passed\": true}, {\"check\": \"merge commit sees both parents\", \"actual\": [\"D\"], \"expected\": [\"D\"], \"passed\": true}, {\"check\": \"fast-forward: one side is an ancestor\", \"actual\": [\"B\"], \"expected\": [\"B\"], \"passed\": true}, {\"check\": \"same commit\", \"actual\": [\"D\"], \"expected\": [\"D\"], \"passed\": true}, {\"check\": \"criss-cross has two merge bases\", \"actual\": [\"X1\", \"Y1\"], \"expected\": [\"X1\", \"Y1\"], \"passed\": true}, {\"check\": \"long chain against a side branch\", \"actual\": [\"c1\"], \"expected\": [\"c1\"], \"passed\": true}, {\"check\": \"second parent carries the only common ancestor\", \"actual\": [\"a\"], \"expected\": [\"a\"], \"passed\": true}, {\"check\": \"unrelated histories\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"second parent deeper in history\", \"actual\": [], \"expected\": [\"a\"], \"passed\": false}, {\"check\": \"first commit is the ancestor\", \"actual\": [\"c1\"], \"expected\": [\"c1\"], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":49.697,"exit_code":1,"observations":[{"actual":["B"],"check":"simple fork","expected":["B"],"passed":true},{"actual":["B"],"check":"merge commit sees both parents","expected":["D"],"passed":false},{"actual":["B"],"check":"fast-forward: one side is an ancestor","expected":["B"],"passed":true},{"actual":["D"],"check":"same commit","expected":["D"],"passed":true},{"actual":["R"],"check":"criss-cross has two merge bases","expected":["X1","Y1"],"passed":false},{"actual":["c1"],"check":"long chain against a side branch","expected":["c1"],"passed":true},{"actual":[],"check":"second parent carries the only common ancestor","expected":["a"],"passed":false},{"actual":[],"check":"unrelated histories","expected":[],"passed":true},{"actual":[],"check":"second parent deeper in history","expected":["a"],"passed":false},{"actual":["c1"],"check":"first commit is the ancestor","expected":["c1"],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"simple fork\", \"actual\": [\"B\"], \"expected\": [\"B\"], \"passed\": true}, {\"check\": \"merge commit sees both parents\", \"actual\": [\"B\"], \"expected\": [\"D\"], \"passed\": false}, {\"check\": \"fast-forward: one side is an ancestor\", \"actual\": [\"B\"], \"expected\": [\"B\"], \"passed\": true}, {\"check\": \"same commit\", \"actual\": [\"D\"], \"expected\": [\"D\"], \"passed\": true}, {\"check\": \"criss-cross has two merge bases\", \"actual\": [\"R\"], \"expected\": [\"X1\", \"Y1\"], \"passed\": false}, {\"check\": \"long chain against a side branch\", \"actual\": [\"c1\"], \"expected\": [\"c1\"], \"passed\": true}, {\"check\": \"second parent carries the only common ancestor\", \"actual\": [], \"expected\": [\"a\"], \"passed\": false}, {\"check\": \"unrelated histories\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"second parent deeper in history\", \"actual\": [], \"expected\": [\"a\"], \"passed\": false}, {\"check\": \"first commit is the ancestor\", \"actual\": [\"c1\"], \"expected\": [\"c1\"], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":43.791,"exit_code":0,"observations":[{"actual":["B"],"check":"simple fork","expected":["B"],"passed":true},{"actual":["D"],"check":"merge commit sees both parents","expected":["D"],"passed":true},{"actual":["B"],"check":"fast-forward: one side is an ancestor","expected":["B"],"passed":true},{"actual":["D"],"check":"same commit","expected":["D"],"passed":true},{"actual":["X1","Y1"],"check":"criss-cross has two merge bases","expected":["X1","Y1"],"passed":true},{"actual":["c1"],"check":"long chain against a side branch","expected":["c1"],"passed":true},{"actual":["a"],"check":"second parent carries the only common ancestor","expected":["a"],"passed":true},{"actual":[],"check":"unrelated histories","expected":[],"passed":true},{"actual":["a"],"check":"second parent deeper in history","expected":["a"],"passed":true},{"actual":["c1"],"check":"first commit is the ancestor","expected":["c1"],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"simple fork\", \"actual\": [\"B\"], \"expected\": [\"B\"], \"passed\": true}, {\"check\": \"merge commit sees both parents\", \"actual\": [\"D\"], \"expected\": [\"D\"], \"passed\": true}, {\"check\": \"fast-forward: one side is an ancestor\", \"actual\": [\"B\"], \"expected\": [\"B\"], \"passed\": true}, {\"check\": \"same commit\", \"actual\": [\"D\"], \"expected\": [\"D\"], \"passed\": true}, {\"check\": \"criss-cross has two merge bases\", \"actual\": [\"X1\", \"Y1\"], \"expected\": [\"X1\", \"Y1\"], \"passed\": true}, {\"check\": \"long chain against a side branch\", \"actual\": [\"c1\"], \"expected\": [\"c1\"], \"passed\": true}, {\"check\": \"second parent carries the only common ancestor\", \"actual\": [\"a\"], \"expected\": [\"a\"], \"passed\": true}, {\"check\": \"unrelated histories\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"second parent deeper in history\", \"actual\": [\"a\"], \"expected\": [\"a\"], \"passed\": true}, {\"check\": \"first commit is the ancestor\", \"actual\": [\"c1\"], \"expected\": [\"c1\"], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}