La fusion trois-voies de Git repose sur une chaîne de traitements répartis entre plusieurs modules du code source. L'objectif est d'identifier un ancêtre commun, de mesurer les écarts entre deux branches et de réconcilier les modificatiosn au niveau fichier. Cette description se concentre sur les étapes essentielles et propose une relecture des structures clés sous un angle différent.

1. Recherche de l'ancêtre commun

Git parcourt le graphe orienté acyclique des commits pour trouver le point de divergence le plus récent entre deux branches. La fonction centrale exploite les parents de chaque commit et gère le cas des ancêtres multiples.

Fichier source : merge-base.c

struct commit *trouver_ancetre_commun(struct commit *branche_a,
                                      struct commit *branche_b)
{
    struct commit_list *candidates;
    struct commit *ancetre;

    /* Extraction des ancêtres communs potentiels */
    candidates = get_merge_bases(branche_a, branche_b);
    ancetre = pop_commit(&candidates);

    /* En cas de fusion octopus, on vide la liste pour la suite */
    while (candidates) {
        liberer_liste_commits(candidates);
        candidates = get_merge_bases(branche_a, branche_b);
    }

    return ancetre;
}

2. Calcul des différences

Une fois l'ancêtre identifié, Git compare son arbre avec ceux des deux révisions à fusionner. Deux séries de différences sont produites : l'une pour la branche locale, l'autre pour la branche distante.

Fichier source : diff.c

void calculer_diffs(const struct tree *base,
                    const struct tree *revis_a,
                    const struct tree *revis_b)
{
    struct diff_options options_diff;

    /* Écarts entre l'ancêtre et la première branche */
    comparer_arbres(base, revis_a, &options_diff);

    /* Écarts entre l'ancêtre et la seconde branche */
    comparer_arbres(base, revis_b, &options_diff);

    /* Normalisation et filtrage des résultats */
    normaliser_resultats_diff(&options_diff);
}

3. Logique de fusion trois-voies

Le cœur de l'algorithme traverse récursivement les arbres et détermine, pour chaque entrée, si elle peut être fusionnée automatiquement ou si elle doit être marquée comme conflit.

Fichier source : merge-recursive.c

int fusionner_arbres(const struct tree *base,
                     const struct tree *revis_a,
                     const struct tree *revis_b,
                     struct merge_options *opt)
{
    struct traverse_info contexte;
    int statut;

    memset(opt, 0, sizeof(*opt));
    opt->ours = revis_a;
    opt->theirs = revis_b;

    statut = parcourir_hierarchie(base, revis_a, revis_b,
                                 &contexte, opt);

    if (statut < 0) {
        error("Conflit de fusion détecté");
        return -1;
    }

    return 0;
}

Parcours récursif des entrées

int parcourir_hierarchie(const struct tree *base,
                         const struct tree *revis_a,
                         const struct tree *revis_b,
                         struct traverse_info *ctx,
                         struct merge_options *opt)
{
    /* Si les deux branches modifient la même entrée de manière incompatible */
    if (modifications_en_conflit(revis_a, revis_b)) {
        enregistrer_conflit(ctx, revis_a, revis_b);
        return -1;
    }

    /* Application de la fusion au niveau fichier */
    fusionner_fichier(ctx, base, revis_a, revis_b, opt);
    return 0;
}

Fusion au niveau fichier

void fusionner_fichier(struct traverse_info *ctx,
                       const struct tree *base,
                       const struct tree *revis_a,
                       const struct tree *revis_b,
                       struct merge_options *opt)
{
    struct contenu_fichier contenu;

    contenu.origine = lire_contenu(base);
    contenu.local   = lire_contenu(revis_a);
    contenu.distant = lire_contenu(revis_b);

    if (!appliquer_fusion_3voies(&contenu, opt)) {
        fprintf(stderr, "Conflit : résolution manuelle requise pour %s\n",
                ctx->path);
    }
}

4. Gestion des conflits

Lorsque les modifications ne peuvent pas être fusionnées automatiquement, Git insère des marqueurs dans le fichier pour matérialiser les zones litigieuses.

<<<<<<< M_BRANCHE
modification locale
=======
modification distante
>>>>>>> AUTRE_BRANCHE

Fichier source : merge-recursive.c

int appliquer_fusion_3voies(struct contenu_fichier *contenu,
                            struct merge_options *opt)
{
    struct diff_resultat resultat;

    resultat = diff_fichiers(contenu->origine,
                             contenu->local,
                             contenu->distant);

    if (resultat.conflit) {
        ecrire_marqueurs_conflit(contenu, opt);
        return -1;
    }

    ecrire_fichier_fusion(contenu, opt);
    return 0;
}

5. Création du commit de fusion

Quand tous les fichiers sont résolus, Git crée un commit possédant deux parents : le pointeur de la branche courante et celui de la branche fusionnée.

Fichier source : commit.c

int creer_commit_fusion(const char *message,
                        struct commit *tete,
                        struct commit *autre)
{
    struct commit_list *parents = NULL;

    commit_list_append(tete, &parents);
    commit_list_append(autre, &parents);

    return inserer_commit(message, parents);
}

Cartographie des responsabilités

• Recherche de l'ancêtre : merge-base.c
• Calcul des différences : diff.c
• Algorithme de fusion : merge-recursive.c
• Insertion des marqueurs de conflit : merge-recursive.c
• Création du commit : commit.c

Référence : code source disponible sur https://github.com/git/git.