نزدیک‌ترین commit کافی نیست؛ چند پایهٔ ادغام در گرافِ Git با پایتون

پیش از ادغامِ دو تغییر، باید معلوم باشد کدام پیشینه را مشترک می‌دانیم. در یک تاریخچهٔ شاخه‌دار، نزدیک‌ترین گره برحسبِ شمارِ یال‌ها الزاماً پایهٔ درستِ ادغام نیست؛ حتی ممکن است پاسخِ درست بیش از یک گره داشته باشد. این درس، مسئله را روی گراف‌های کوچک و تألیفی با پایتون بازسازی می‌کند. نام‌های R و X فقط برچسب‌اند؛ هیچ مخزن، شاخه، فایلِ پروژه یا فرمانِ Git ساخته، خوانده یا تغییر داده نمی‌شود.

۱. گرافِ والدها چه چیزی را نگه می‌دارد؟

ورودی، نگاشتِ هر برچسب به تاپلِ والدهای آن است. اگر والدِ X برابر R باشد، با دنبال‌کردنِ والدها از X به R می‌رسیم. در قراردادِ ما هر نوک، خودش نیز در مجموعهٔ اجدادش قرار می‌گیرد؛ سپس هر والد و والدهایِ آن اضافه می‌شوند. این رابطه دربارهٔ دسترس‌پذیری در پیشینه است، نه ترتیبِ حروف، تاریخِ ثبت، مدتِ کار یا فاصلهٔ زمانیِ دو تغییر.

مرزِ آموزشیِ تابع، dict دقیق با یک تا هشت گره است. برچسب، رشتهٔ دقیقِ ASCII با یک تا هشت نویسه است؛ با حرفِ بزرگ آغاز می‌شود و ادامه می‌تواند حرفِ بزرگ، رقم یا زیرخط باشد. هر تاپلِ والد حداکثر هفت عضو دارد و مجموعِ مدخل‌ها از شانزده بیشتر نمی‌شود. والدِ تکراری، نامِ اعلام‌نشده و هر چرخه رد می‌شوند. این حدود، قواعدِ نمونهٔ ما هستند؛ قالبِ شناسه یا ظرفیتِ واقعیِ Git را تعریف نمی‌کنند.

دو نوک باید از ابتدا در همان نگاشت حضور داشته باشند. پیش از پاسخ، کلِ ساختار بررسی می‌شود؛ وجودِ چرخه در یک شاخهٔ نامرتبط نیز خطای ورودی است. بنابراین کاربر نمی‌تواند با انتخابِ دو گرهِ ظاهراً سالم، قسمتِ معیوبِ همان ورودی را پنهان کند. گرافِ پذیرفته‌شده هم اطلاعاتی دربارهٔ محتوای فایل‌ها، نامِ شاخه‌ها، ارجاع‌های دوردست یا تاریخچهٔ حذف‌شده ندارد.

در آزمایشِ ادغامِ سه‌طرفهٔ فایل، متنِ پایه از ابتدا داده شده بود و Git واقعاً سه فایلِ ساختگی را ترکیب می‌کرد. اینجا هنوز متنی برای ترکیب نداریم؛ فقط پایه‌های ممکن را از رابطهٔ والدها استخراج می‌کنیم. انتخابِ پایه و معتبر بودنِ محتوای نتیجه، دو بررسیِ جدا با ورودی و شاهدِ متفاوت‌اند.

۲. جدِ مشترکِ بهتر، کم‌فاصله‌تر نیست

ابتدا اجدادِ دو نوک را اشتراک می‌گیریم. طبقِ تعریفِ رسمیِ merge-base، یک جدِ مشترک از جدِ مشترکِ دیگر بهتر است اگر دومی جدِ اولی باشد. پس گرهی را حذف می‌کنیم که یک جدِ مشترکِ دیگر، پایین‌تر از آن در رابطهٔ فرزندی باشد. «بهتر» در این تعریف، رتبهٔ کیفیت یا کوتاهیِ مسیر نیست؛ رابطهٔ مشخصِ دسترس‌پذیری است.

شاهدِ دستیِ ما هفت گره دارد. R والدِ X و X والدِ U و V است؛ W نیز والدش V است. نوکِ A دو والد U و R دارد و نوکِ B دو والد W و R. از هر نوک با یک یال مستقیم به R می‌رسیم، اما رسیدن از A به X دو یال و از B به X سه یال می‌خواهد. جمعِ کوتاه‌ترین فاصله‌ها برای R برابر دو و برای X برابر پنج است.

بااین‌حال اشتراکِ اجداد فقط R و X است و پاسخِ درست X خواهد بود، چون R جدِ X است. قاعدهٔ انتخابِ کمترین جمعِ فاصله، در همین مثال R را برمی‌گزیند و اشتباه می‌کند. یال‌های مستقیم به R، گذشتهٔ موجود از مسیر X را پاک نمی‌کنند. این شاهد از داده‌های خودمان ساخته شده و نیازی به ساعت، اجرای مخزن یا فرضِ مرتب‌بودنِ تاریخِ commitها ندارد.

اگر دو اتصالِ مستقیمِ A به R و B به R را برداریم، مجموعهٔ اجداد و پاسخِ پایه عوض نمی‌شوند؛ فقط فاصلهٔ کوتاه‌ترین مسیر تا R بیشتر می‌شود. این تغییرِ کنترل‌شده، علتِ شکستِ معیارِ فاصله را روشن می‌کند. نتیجه، مجوزِ حذفِ دلخواهِ یال در مخزن نیست؛ می‌گوییم در همین دو گرافِ تألیفی، رابطهٔ دسترس‌پذیریِ لازم برای پاسخ یکسان مانده است.

۳. دو پایهٔ ناسنجیدنی و مرزِ انتخابِ یکی

اکنون R ریشه است و X و Y هر دو والدشان R است. هر دو نوکِ A و B، به X و Y والد دارند. اجدادِ مشترک R و X و Y هستند؛ R کنار می‌رود، ولی نه X جدِ Y است و نه Y جدِ X. بنابراین هر دو باقی می‌مانند. مجموعهٔ پاسخ، نسبت به رابطهٔ نیاکان ناسنجیدنی است؛ وجودِ یک ریشهٔ مشترک، پاسخِ یکتا را تضمین نمی‌کند.

مرجعِ رسمی، امکانِ چند پایه در پیشینهٔ دارای ادغام‌های متقاطع و گزینهٔ --all را توضیح می‌دهد. اگر آن گزینه نباشد، انتخابِ یک پایهٔ مشخص در حالتِ چندپایه معین نشده است. تابعِ ما همهٔ پایه‌ها را برمی‌گرداند و فقط برای نمایش، برچسب‌ها را مرتب می‌کند. کوچک‌ترین برچسب را برنده نمی‌کند و ادعا ندارد ترتیبِ خروجیِ یک فرمانِ اجراشدهٔ Git را بازسازی کرده است.

پاسخِ خالی نیز معنی دارد: دو ریشهٔ جدا، جدِ مشترک ندارند و تابع تاپلِ تهی می‌دهد. اگر یک نوک جدِ دیگری باشد، همان نوک تنها پایهٔ بهتر است؛ برای پرسشِ یک نوک با خودش نیز همان برچسب باقی می‌ماند. این‌ها قراردادهای رابطه‌ایِ رابطِ حاضرند؛ کدِ خروجِ فرایند، سیاستِ ادغامِ تاریخچه‌های نامرتبط یا ساختنِ پایهٔ مجازی را شبیه‌سازی نمی‌کنیم.

در شرحِ فنیِ جاریِ Git دربارهٔ paint_down_to_common، رنگ‌گذاری، شمارهٔ نسل و شرط‌های توقفِ الگوریتمِ واقعی توضیح داده شده‌اند. برنامهٔ کوچکِ ما آن الگوریتمِ بهینه‌شده را پیاده نمی‌کند؛ همهٔ رابطه‌های لازم را در دامنهٔ محدود خودش می‌سازد. از درستیِ این مدل، سرعت، هزینهٔ حافظه یا رفتارِ Git در مخزنِ بزرگ نتیجه نمی‌گیریم.

۴. کدِ کامل؛ مرجعِ مستقلِ مسیرهایِ کامل

فایلِ زیر فقط کتابخانهٔ استاندارد لازم دارد. تابعِ اصلی، گره‌های دارای والدهایِ آماده را پیدا می‌کند و مجموعهٔ اجدادِ هر گره را از والدهایش می‌سازد. اگر هنوز گره باقی باشد ولی هیچ گرهی آماده نشود، چرخه داریم. این محاسبه، گراف را اجرا نمی‌کند. در درسِ تحویلِ ready و اعلامِ done، موضوع عمرِ کارها بود؛ اینجا همین ترتیبِ والدها فقط ابزارِ ساختنِ یک رابطهٔ ثابت است.

"""All best common ancestors in a supplied small DAG; no Git or repository I/O.

Own exact profile: dict1..8 ASCII commit labels, tuple0..7 distinct parents,
all parents declared, at most16 entries. Labels are not object IDs or dates.
"""
from itertools import product
import json
import platform
import re
import sys


def checked_graph(graph):
    if type(graph) is not dict or not 1 <= len(graph) <= 8:
        raise ValueError('exact_dict_one_to_eight_commits')
    valid = lambda value: type(value) is str and re.fullmatch(r'[A-Z][A-Z0-9_]{0,7}', value) is not None
    if any(not valid(node) for node in graph):
        raise ValueError('exact_ASCII_commit_labels_one_to_eight_characters')
    entries = 0
    for parents in graph.values():
        if type(parents) is not tuple or len(parents) > 7:
            raise ValueError('exact_parent_tuple_at_most_seven')
        if any(not valid(parent) or parent not in graph for parent in parents):
            raise ValueError('all_parent_names_must_be_explicitly_declared')
        if len(set(parents)) != len(parents):
            raise ValueError('duplicate_parent_entry')
        entries += len(parents)
    if entries > 16:
        raise ValueError('at_most_sixteen_parent_entries')
    return {node: tuple(sorted(graph[node])) for node in sorted(graph)}


def ancestry_closure(graph):
    """Trusted checked structure: parent-before-child sets; rejects any cycle."""
    remaining = set(graph)
    ancestors = {}
    while remaining:
        ready = sorted(node for node in remaining if all(p in ancestors for p in graph[node]))
        if not ready:
            raise ValueError('supplied_graph_has_a_cycle')
        for node in ready:
            reached = {node}
            for parent in graph[node]:
                reached.update(ancestors[parent])
            ancestors[node] = reached
            remaining.remove(node)
    return ancestors


def best_common_bases(graph, left, right):
    supplied = checked_graph(graph)
    ancestors = ancestry_closure(supplied)
    if type(left) is not str or type(right) is not str or left not in supplied or right not in supplied:
        raise ValueError('both_exact_string_tips_must_be_declared')
    common = ancestors[left] & ancestors[right]
    best = tuple(sorted(candidate for candidate in common if not any(
        candidate != other and candidate in ancestors[other] for other in common)))
    return {'left': left, 'right': right,
            'left_ancestors_including_self': tuple(sorted(ancestors[left])),
            'right_ancestors_including_self': tuple(sorted(ancestors[right])),
            'common': tuple(sorted(common)), 'best': best,
            'redundant_common': tuple(sorted(common - set(best))),
            'units': 'commit labels and parent relations; no seconds or timestamps'}


def explicit_parent_paths(graph, start):
    """All finite parent-walk tuples on trusted acyclic fixtures, including self.

    Independent reference: no checker, closure map, production query or distance.
    """
    paths = []
    def walk(node, path):
        extended = path + (node,)
        paths.append(extended)
        for parent in graph[node]:
            walk(parent, extended)
    walk(start, ())
    return tuple(paths)


def path_reference(graph, left, right):
    left_paths = explicit_parent_paths(graph, left)
    right_paths = explicit_parent_paths(graph, right)
    common = {path[-1] for path in left_paths} & {path[-1] for path in right_paths}
    covered_by_later_common = set()
    for origin in common:
        for path in explicit_parent_paths(graph, origin):
            if len(path) > 1:
                covered_by_later_common.add(path[-1])
    return tuple(sorted(common - covered_by_later_common))


def shortest_parent_distances(graph, start):
    """Separate WRONG-HEURISTIC witness helper, never the merge-base rule."""
    distance = {start: 0}
    queue = [start]
    while queue:
        node = queue.pop(0)
        for parent in graph[node]:
            if parent not in distance:
                distance[parent] = distance[node] + 1
                queue.append(parent)
    return distance


def rejected(graph, left='A', right='A'):
    try:
        best_common_bases(graph, left, right)
    except ValueError:
        return True
    return False


def run_example():
    shortcut = {'R': (), 'X': ('R',), 'U': ('X',), 'A': ('U', 'R'),
                'V': ('X',), 'W': ('V',), 'B': ('W', 'R')}
    shortcut_result = best_common_bases(shortcut, 'A', 'B')
    da = shortest_parent_distances(shortcut, 'A')
    db = shortest_parent_distances(shortcut, 'B')
    sums = {node: da[node] + db[node] for node in shortcut_result['common']}
    wrong_choice = min(sums, key=lambda node: (sums[node], node))
    cross = {'R': (), 'X': ('R',), 'Y': ('R',), 'A': ('X', 'Y'), 'B': ('Y', 'X')}
    cross_result = best_common_bases(cross, 'A', 'B')
    checks = {
        'manual_shortcut_nearest_sum_is_R_but_best_common_is_X':
            shortcut_result['common'] == ('R', 'X') and shortcut_result['best'] == ('X',)
            and sums == {'R': 2, 'X': 5} and wrong_choice == 'R',
        'manual_two_incomparable_bases_are_both_returned':
            cross_result['common'] == ('R', 'X', 'Y') and cross_result['best'] == ('X', 'Y')
            and cross_result['redundant_common'] == ('R',),
        'ancestor_tip_itself_is_unique_best_base':
            best_common_bases(cross, 'X', 'A')['best'] == ('X',),
        'same_tip_uses_reflexive_ancestry_and_is_only_best':
            best_common_bases(cross, 'A', 'A')['best'] == ('A',)
            and 'A' in best_common_bases(cross, 'A', 'A')['common'],
        'disconnected_histories_have_no_invented_base':
            best_common_bases({'A': (), 'B': ()}, 'A', 'B')['common'] == ()
            and best_common_bases({'A': (), 'B': ()}, 'A', 'B')['best'] == (),
        'ordinary_split_has_only_common_root':
            best_common_bases({'R': (), 'A': ('R',), 'B': ('R',)}, 'A', 'B')['best'] == ('R',),
    }
    reverse = best_common_bases(shortcut, 'B', 'A')
    checks['swapping_tips_preserves_common_and_best_not_side_names'] = (
        reverse['left'] == 'B' and reverse['right'] == 'A'
        and reverse['common'] == shortcut_result['common'] and reverse['best'] == shortcut_result['best'])
    without_shortcuts = dict(shortcut, A=('U',), B=('W',))
    checks['redundant_ancestral_edges_change_distances_not_ancestry_answer'] = (
        best_common_bases(without_shortcuts, 'A', 'B') == shortcut_result
        and shortest_parent_distances(without_shortcuts, 'A')['R'] == 3
        and shortest_parent_distances(without_shortcuts, 'B')['R'] == 4)
    triple = {'R': (), 'X': ('R',), 'Y': ('R',), 'Z': ('R',),
              'A': ('X', 'Y', 'Z'), 'B': ('Z', 'Y', 'X')}
    tri = best_common_bases(triple, 'A', 'B')
    certificate = tri['best'] == ('X', 'Y', 'Z')
    for candidate in tri['best']:
        for other in tri['best']:
            if candidate != other:
                certificate = certificate and not any(path[-1] == candidate for path in explicit_parent_paths(triple, other))
    certificate = certificate and all(any(path[-1] == ancestor for base in tri['best']
        for path in explicit_parent_paths(triple, base)) for ancestor in tri['common'])
    checks['returned_antichain_covers_every_common_ancestor_in_manual_triple'] = certificate

    labels = tuple('ABCDE')
    possible = tuple((child, parent) for child in labels for parent in labels if parent < child)
    profiles = queries = 0
    oracle_ok = True
    for flags in product((False, True), repeat=len(possible)):
        graph = {node: tuple(parent for (child, parent), present in zip(possible, flags)
                             if child == node and present) for node in labels}
        for left in labels:
            for right in labels:
                actual = best_common_bases(graph, left, right)
                oracle_ok = oracle_ok and actual['best'] == path_reference(graph, left, right)
                queries += 1
        profiles += 1
    checks['independent_explicit_paths_1024_DAGs_25600_queries_ONE_family'] = (
        oracle_ok and profiles == 1024 and queries == 25600)

    class DictChild(dict):
        pass
    class TupleChild(tuple):
        pass
    class StrChild(str):
        pass
    invalid = [([], 'A', 'A'), ({}, 'A', 'A'), (DictChild(A=()), 'A', 'A'),
        ({True: ()}, 'A', 'A'), ({'bad': ()}, 'bad', 'bad'), ({'A12345678': ()}, 'A', 'A'),
        ({StrChild('A'): ()}, 'A', 'A'), ({'A': []}, 'A', 'A'),
        ({'A': TupleChild(())}, 'A', 'A'), ({'A': iter(())}, 'A', 'A'),
        ({'A': ('MISSING',)}, 'A', 'A'), ({'A': (True,)}, 'A', 'A'),
        ({'A': (StrChild('A'),)}, 'A', 'A'), ({'A': ('B', 'B'), 'B': ()}, 'A', 'B'),
        ({'A': ('A',)}, 'A', 'A'), ({'A': ('B',), 'B': ('A',)}, 'A', 'B'),
        ({'A': ('B',), 'B': ('A',), 'C': ()}, 'C', 'C'),
        ({'A': ()}, 'MISSING', 'A'), ({'A': ()}, True, 'A'),
        ({'A': ()}, StrChild('A'), 'A'), ({'A': ()}, 'A', None),
        ({'N' + str(i): () for i in range(9)}, 'N0', 'N1')]
    max16 = {'A': (), 'B': ('A',), 'C': ('A', 'B'), 'D': ('A', 'B', 'C'),
             'E': ('A', 'B', 'C', 'D'), 'F': ('B', 'C', 'D', 'E'), 'G': ('F',), 'H': ('G',)}
    over17 = dict(max16, F=('A', 'B', 'C', 'D', 'E'))
    invalid.append((over17, 'H', 'E'))
    rejected_count = sum(rejected(graph, left, right) for graph, left, right in invalid)
    checks['full_exact_schema_unknowns_cycles_caps_and_query_types_ONE_invalid_family'] = rejected_count == len(invalid)
    star7 = {node: () for node in 'ABCDEFG'}
    star7['H'] = tuple('ABCDEFG')
    checks['closed_resource_endpoints_eight_nodes_sixteen_edges_seven_parents_name8'] = (
        sum(map(len, max16.values())) == 16 and best_common_bases(max16, 'H', 'E')['best'] == ('E',)
        and best_common_bases(star7, 'H', 'A')['best'] == ('A',)
        and best_common_bases({'R1234567': ()}, 'R1234567', 'R1234567')['best'] == ('R1234567',))
    mutable = {'A': (), 'B': ('A',)}
    before = tuple(mutable.items())
    held = best_common_bases(mutable, 'B', 'A')
    returned_fresh = best_common_bases(mutable, 'B', 'A')
    returned_fresh['best'] = ('UNRELATED',)
    not_mutated = tuple(mutable.items()) == before
    mutable['B'] = ()
    checks['inputs_unmutated_fresh_results_and_old_snapshot_survives_caller_edit'] = (
        not_mutated and held['best'] == ('A',) and returned_fresh['best'] == ('UNRELATED',)
        and best_common_bases(mutable, 'B', 'A')['best'] == ())
    extension = dict(cross, A2=('A',))
    reordered = {node: tuple(reversed(parents)) for node, parents in reversed(tuple(extension.items()))}
    checks['new_single_parent_tip_and_declaration_order_preserve_existing_bases'] = (
        best_common_bases(extension, 'A2', 'B')['best'] == cross_result['best']
        and best_common_bases(extension, 'A2', 'B') == best_common_bases(reordered, 'A2', 'B'))
    assert len(checks) == 14 and all(type(value) is bool and value for value in checks.values()), checks
    return {'python': platform.python_version(), 'implementation': platform.python_implementation(),
        'dependencies': 'Python standard library only', 'scope': 'Supplied finite commit-parent DAG; no Git/repository/ref/reflog/content merge/clock/network or performance experiment.',
        'shortcut_fixture': {'parents': shortcut, 'query': ('A', 'B'), 'answer': shortcut_result,
                             'shortest_parent_distance_sum': sums, 'wrong_nearest_sum_choice': wrong_choice},
        'incomparable_fixture': {'parents': cross, 'query': ('A', 'B'), 'answer': cross_result},
        'manual_three_base_certificate': tri,
        'independent_explicit_path_family_ONE_group': {'profiles': profiles, 'ordered_tip_queries': queries},
        'invalid_cases_inside_ONE_group': len(invalid),
        'own_limits': {'commits': [1, 8], 'parents_per_commit': [0, 7], 'total_parent_entries': 16,
                       'labels': 'exact ASCII [A-Z][A-Z0-9_]{0,7}; all declared; no duplicates/cycles',
                       'output_order': 'sorted label display only; not unspecified Git default single-base choice'},
        'Git_invocations': 0, 'new_repository_or_branch_operations': 0, 'checks': checks}


if __name__ == '__main__':
    sys.stdout.buffer.write((json.dumps(run_example(), ensure_ascii=True, indent=2, allow_nan=False) + '\n').encode('utf-8'))

مرجعِ مستقل، تمامِ مسیرهای متناهیِ دنبال‌کردنِ والدها را به شکلِ تاپل‌های کامل می‌سازد. انتهای مسیرها، اجدادِ هر نوک را مشخص می‌کند. سپس هر گرهِ مشترکی که در انتهای یک مسیرِ غیرتک‌عضوی از جدِ مشترکِ دیگری دیده شود کنار می‌رود. این مرجع نه اعتبارسنج، نه جدولِ بستار و نه تابعِ انتخابِ اصلی را فراخوانی می‌کند؛ مسیرهایِ صریح، نمایشِ محاسباتیِ جداگانه‌ای دارند.

خانوادهٔ محدود، همهٔ ۱۰۲۴ گرافِ پنج‌گرهی با یال‌های رو‌به‌عقب در ترتیبِ ثابتِ برچسب‌ها و همهٔ ۲۵ جفتِ مرتبِ نوک‌ها را می‌سازد. این ۲۵۶۰۰ پرسش فقط یک گروهِ بررسی است. چهارده گروهِ نام‌دار، شاهدهای دستی، چرخه و ورودیِ نامعتبر، تقارنِ دو نوک، مرزهای اندازه، ترتیبِ اعلان‌ها و استقلالِ خروجی‌ها را نیز می‌سنجند. این شمارش، اثباتِ همهٔ گراف‌های ممکن یا اجرایِ مقایسه‌ایِ Git نیست.

{
  "python": "3.14.5",
  "implementation": "CPython",
  "dependencies": "Python standard library only",
  "scope": "Supplied finite commit-parent DAG; no Git/repository/ref/reflog/content merge/clock/network or performance experiment.",
  "shortcut_fixture": {
    "parents": {
      "R": [],
      "X": [
        "R"
      ],
      "U": [
        "X"
      ],
      "A": [
        "U",
        "R"
      ],
      "V": [
        "X"
      ],
      "W": [
        "V"
      ],
      "B": [
        "W",
        "R"
      ]
    },
    "query": [
      "A",
      "B"
    ],
    "answer": {
      "left": "A",
      "right": "B",
      "left_ancestors_including_self": [
        "A",
        "R",
        "U",
        "X"
      ],
      "right_ancestors_including_self": [
        "B",
        "R",
        "V",
        "W",
        "X"
      ],
      "common": [
        "R",
        "X"
      ],
      "best": [
        "X"
      ],
      "redundant_common": [
        "R"
      ],
      "units": "commit labels and parent relations; no seconds or timestamps"
    },
    "shortest_parent_distance_sum": {
      "R": 2,
      "X": 5
    },
    "wrong_nearest_sum_choice": "R"
  },
  "incomparable_fixture": {
    "parents": {
      "R": [],
      "X": [
        "R"
      ],
      "Y": [
        "R"
      ],
      "A": [
        "X",
        "Y"
      ],
      "B": [
        "Y",
        "X"
      ]
    },
    "query": [
      "A",
      "B"
    ],
    "answer": {
      "left": "A",
      "right": "B",
      "left_ancestors_including_self": [
        "A",
        "R",
        "X",
        "Y"
      ],
      "right_ancestors_including_self": [
        "B",
        "R",
        "X",
        "Y"
      ],
      "common": [
        "R",
        "X",
        "Y"
      ],
      "best": [
        "X",
        "Y"
      ],
      "redundant_common": [
        "R"
      ],
      "units": "commit labels and parent relations; no seconds or timestamps"
    }
  },
  "manual_three_base_certificate": {
    "left": "A",
    "right": "B",
    "left_ancestors_including_self": [
      "A",
      "R",
      "X",
      "Y",
      "Z"
    ],
    "right_ancestors_including_self": [
      "B",
      "R",
      "X",
      "Y",
      "Z"
    ],
    "common": [
      "R",
      "X",
      "Y",
      "Z"
    ],
    "best": [
      "X",
      "Y",
      "Z"
    ],
    "redundant_common": [
      "R"
    ],
    "units": "commit labels and parent relations; no seconds or timestamps"
  },
  "independent_explicit_path_family_ONE_group": {
    "profiles": 1024,
    "ordered_tip_queries": 25600
  },
  "invalid_cases_inside_ONE_group": 23,
  "own_limits": {
    "commits": [
      1,
      8
    ],
    "parents_per_commit": [
      0,
      7
    ],
    "total_parent_entries": 16,
    "labels": "exact ASCII [A-Z][A-Z0-9_]{0,7}; all declared; no duplicates/cycles",
    "output_order": "sorted label display only; not unspecified Git default single-base choice"
  },
  "Git_invocations": 0,
  "new_repository_or_branch_operations": 0,
  "checks": {
    "manual_shortcut_nearest_sum_is_R_but_best_common_is_X": true,
    "manual_two_incomparable_bases_are_both_returned": true,
    "ancestor_tip_itself_is_unique_best_base": true,
    "same_tip_uses_reflexive_ancestry_and_is_only_best": true,
    "disconnected_histories_have_no_invented_base": true,
    "ordinary_split_has_only_common_root": true,
    "swapping_tips_preserves_common_and_best_not_side_names": true,
    "redundant_ancestral_edges_change_distances_not_ancestry_answer": true,
    "returned_antichain_covers_every_common_ancestor_in_manual_triple": true,
    "independent_explicit_paths_1024_DAGs_25600_queries_ONE_family": true,
    "full_exact_schema_unknowns_cycles_caps_and_query_types_ONE_invalid_family": true,
    "closed_resource_endpoints_eight_nodes_sixteen_edges_seven_parents_name8": true,
    "inputs_unmutated_fresh_results_and_old_snapshot_survives_caller_edit": true,
    "new_single_parent_tip_and_declaration_order_preserve_existing_bases": true
  }
}

برنامه نسخهٔ واقعیِ پایتون را در JSON می‌نویسد؛ محیطِ این آموزش CPython3.14.5 است. مستندِ merge-base آخرین تغییرِ خود را 2.43.0 و بی‌تغییر بودن تا 2.56.0 نشان می‌دهد؛ سندِ فنیِ دوم نسخهٔ 2.56.0 و تاریخِ ۲۸ سپتامبر ۲۰۲۶ دارد. دسترسیِ ما ۲۱ اکتبر است و جای تاریخِ انتشارِ اولیهٔ نامعلوم نمی‌نشیند. نه Git اجرا شده و نه عددِ کارایی از خبرِ انتشار به این آزمایش منتقل شده است.

۵. چهار پرسش برای انتخابِ پایه

پرسشِ اول: چرا در شاهدِ هفت‌گرهی، R با فاصلهٔ کمتر انتخاب نمی‌شود؟ پاسخ: چون R جدِ X است و X نیز جدِ هر دو نوک است؛ پس یک جدِ مشترکِ بهتر از R داریم. جمعِ فاصله‌های دو و پنج، در تعریفِ این رابطه نقشی ندارد. یالِ میان‌بُر، پیشینهٔ X را حذف نکرده است.

پرسشِ دوم: اگر پاسخ X و Y باشد، می‌توان فقط X را نگه داشت؟ پاسخ: برای قراردادِ «همهٔ پایه‌ها» خیر؛ هیچ‌کدام جدِ دیگری نیست. مرتب‌کردنِ نمایش، دلیلِ حذفِ Y نیست. اگر کاربرد به یک نتیجه احتیاج دارد، سیاستِ بعدی باید جدا تعریف و آزموده شود؛ تابعِ حاضر ادغامِ محتوای چند پایه را انجام نمی‌دهد.

پرسشِ سوم: آیا پاسخِ تهی به معنیِ خرابیِ اعتبارسنج است؟ پاسخ: نه لزوماً؛ دو ریشهٔ مستقل، ورودیِ معتبر با اشتراکِ تهی‌اند. این وضعیت با نامِ والدِ اعلام‌نشده یا چرخه فرق دارد؛ آن دو خطای ورودی‌اند. رابط، جوابِ رابطه‌ایِ تهی را با خطای ساختار یا وضعیتِ خروجِ یک ابزارِ بیرونی یکی نمی‌گیرد.

پرسشِ چهارم: پس از یافتنِ پایه می‌توان ادغام را معتبر دانست؟ پاسخ: خیر؛ هنوز محتوای فایل‌ها، تعارض و شرط‌های عددیِ پروژه بررسی نشده‌اند. مدل فقط دربارهٔ گرافِ عرضه‌شده پاسخ می‌دهد. پیشینهٔ ناقص، اطلاعاتِ حذف‌شده یا ارجاعِ نادرست را خودکار کشف نمی‌کند و هیچ تغییری در شاخهٔ واقعی نمی‌دهد؛ اعتبارِ نتیجهٔ ادغام شاهدِ دیگری می‌خواهد.

منابع و مطالعهٔ بیشتر

• Git؛ تعریفِ merge-base، همهٔ پایه‌ها و حالتِ چندپایه
• Git2.56؛ تعریفِ جدِ مشترک و مرزِ الگوریتمِ paint_down_to_common

بررسی منابع: ۲۹ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.