Algoritmi di diff testuale: come funzionano Git, le patch e gli strumenti di diff

Ogni strumento di code review, ogni output di git diff, ogni file di patch che hai mai letto risale a un piccolo numero di algoritmi inventati tra il 1976 e il 2009. Sapere quale usa il tuo strumento — e quale assunzione fa — è la differenza tra leggere un diff in 30 secondi e fissarne uno confuso per dieci minuti chiedendoti se il refactoring ha davvero preservato il comportamento.

Cos’è davvero un diff

Un diff è uno script di modifica: una sequenza minimale di inserimenti e cancellazioni che trasforma il file A nel file B. Per due file di lunghezza totale N con D differenze, esistono molti script possibili. Un algoritmo di diff ne sceglie uno secondo un criterio di ottimizzazione — di solito il più piccolo D, ma non sempre.

Ne seguono due corollari. Primo, la stessa modifica al file può produrre legitimamente diff dall’aspetto diverso da strumenti diversi; sono tutti corretti nel senso che applicandoli si ricostruisce il file B. Secondo, “diff leggibile” è un vincolo più debole di “diff minimo,” e i due spesso non concordano. Puoi confrontare due file tu stesso con il nostro strumento di diff testualee vedere l’output unificato fianco a fianco.

Diff Myers — il default ovunque

Il paper di Eugene Myers del 1986 An O(ND) Difference Algorithm and Its Variations ha definito l’algoritmo che GNU diff, Git, Mercurial, SVN e la maggior parte degli editor usano ancora di default. Inquadra il problema del diff come trovare il percorso più breve attraverso un grafo di modifica: ogni passo diagonale è una riga corrispondente, ogni passo orizzontale cancella una riga da A, ogni passo verticale inserisce una riga da B. Il percorso più breve corrisponde allo script di modifica minimo.

La complessità temporale è O(N × D) dove N è la lunghezza totale del file e Dè il numero di differenze. Per i file sorgente tipici con piccole modifiche l’algoritmo è essenzialmente lineare; per file riscritti dall’inizio alla fine degrada, ed è per questo che Git limita l’analisi con i default di diff.algorithm e diff.renameLimit.

La debolezza di Myers è che minimizza la dimensione del diff senza alcun senso della struttura. Dopo aver spostato un blocco di codice, Myers spesso abbina la parentesi graffa chiusa di una funzione con quella chiusa di una funzione diversa perché produce meno righe modificate in totale. Il risultato è tecnicamente minimo e umanamente sconcertante.

Diff Patience — progettato per la leggibilità

Bram Cohen (l’autore di BitTorrent) ha introdotto il diff Patience nel 2007 specificamente per correggere il problema di leggibilità dei refactoring di Myers. L’algoritmo:

1. Trova tutte le righe che appaiono esattamente una volta in entrambi i file. Queste sono le righe ancora univoche.
2. Calcola la sottosequenza comune più lunga delle ancore univoche (usando l’algoritmo patience-sort — da qui il nome).
3. Fa il diff ricorsivo di ogni regione tra ancore consecutive usando la stessa procedura, tornando a Myers quando non rimangono ancore univoche.

Il risultato allinea il diff attorno alle righe che un essere umano riconoscerebbe come “la stessa cosa” — firme di funzioni, commenti unici, dichiarazioni di classe. Patience è più lento di Myers nel caso peggiore ma produce output molto più leggibile per le tipiche modifiche al codice. Abilitalo in Git con git diff --patience o globalmente con git config diff.algorithm patience.

Diff Histogram — Patience, raffinato

Il diff Histogram è stato introdotto da JGit (l’implementazione Java di Git) e successivamente portato in Git upstream. Migliora Patience essendo più intelligente nella scelta delle righe ancora: invece di richiedere l’unicità, sceglie le righe rare con il minor numero di occorrenze in entrambi i file. Le righe comuni (parentesi graffe chiuse, righe vuote) vengono deprioritizzate; le righe rare (nomi di funzioni, stringhe distintive) diventano ancore.

Histogram è il default consigliato per la maggior parte dei repository oggi. Produce output simile a Patience per i casi tipici e notevolmente migliore per i file con molte righe ripetute (come file di dati, fixture e configurazioni con molto rientro). Abilitalo globalmente con git config --global diff.algorithm histogram.

Leggere un hunk di diff unificato

Il diff unificato (-u) è il formato di scambio de facto. Un hunk si presenta così:

@@ -42,7 +42,9 @@ class UserController {
   const user = await User.findById(id);
   if (!user) {
-    return res.status(404).end();
+    logger.warn({ id }, "user not found");
+    return res.status(404).json({ error: "not found" });
   }
   return res.json(user);
 }

La riga @@è l’intestazione dell’hunk. Dice: il vecchio file inizia alla riga 42 e si estende per 7 righe; il nuovo file inizia alla riga 42 e si estende per 9 righe. Il testo dopo il secondo @@è un’intestazione di sezione — per il codice è di solito la funzione o la classe che racchiude, scelta da Git da un’euristica per linguaggio.

Le righe senza prefisso sono contesto invariato. Le righe che iniziano con - esistono solo nel vecchio file; le righe che iniziano con + esistono solo nel nuovo file. Il contesto predefinito è tre righe per lato; -U10lo allarga, utile quando l’effetto della modifica dipende da un’istruzione appena fuori vista.

Spazi e terminazioni di riga

La singola fonte più grande di diff confusi è lo spazio. I problemi più comuni:

• Spazi finali. Un editor che rimuove gli spazi finali al salvataggio segnalerà ogni riga toccata. Configura core.whitespace e git diff --ignore-space-at-eol per mantenere il diff concentrato sulle modifiche reali.
• Rientro misto.Passare da tab a spazi (o viceversa) è un diff dell’intero file anche se nessuna logica è cambiata. Usa git diff -w per ignorare tutte le differenze di spazio quando si rivedono tali modifiche.
• Terminazioni di riga. Le differenze CRLF vs LF fanno sembrare modificata ogni riga. Configura .gitattributes con * text=auto per normalizzare al commit.
• Newline finale. I file senza un newline finale mostrano \ No newline at end of file nel diff. Alcuni strumenti aggiungono silenziosamente il newline al salvataggio, producendo diff di una riga che sembrano rumore.

File binari

Gli algoritmi di diff operano sulle righe. I file senza interruzioni di riga naturali — immagini, eseguibili, PDF — producono output inutile quando confrontati testualmente. Git rileva il contenuto binario cercando byte null nei primi 8 KB; quando trovati, il diff si riduce a Binary files a/x and b/x differ.

Per il contenuto binario che dovrebbe essere confrontabile (DOCX, XLSX, file di design), .gitattributes può registrare un filtro textconv personalizzato che converte il file in una rappresentazione testuale prima del confronto. diff=word, diff=exif e simili built-in vengono forniti con Git.

Merge a tre vie e perché si verificano i conflitti

Quando fai il merge del branch B nel branch A, Git guarda tre versioni: l’antenato comune C, la versione A e la versione B. Il merge procede riga per riga:

• Riga invariata da C ad A ma modificata in B → prendi B.
• Riga modificata in A ma invariata in B → prendi A.
• Riga modificata identicamente in entrambi → prendi uno qualsiasi; nessun conflitto.
• Riga modificata diversamente in A e B → conflitto.

I conflitti vengono segnalati nel file di lavoro con marcatori <<<<<<<, ======= e >>>>>>> che mostrano entrambe le versioni. La versione antenata può essere inclusa anche con merge.conflictStyle diff3, il che rende la risoluzione molto più facile perché puoi vedere da dove è partita ciascuna parte.

Scegliere un algoritmo in pratica

Per il lavoro quotidiano, Histogram è il miglior default e quello che la maggior parte dei team dovrebbe configurare globalmente. Patience produce risultati molto simili ed è utile per file molto grandi dove l’utilizzo di memoria di Histogram diventa notevole. Myers è la scelta giusta per le pipeline da macchina a macchina che consumano diff in modo programmatico, perché il suo output è il minimo canonico.

Gli strumenti di code review (GitHub, GitLab, Gerrit) usano tutti Myers di default per ragioni storiche; le loro UI non espongono sempre la scelta dell’algoritmo. Quando un diff di review sembra disallineato, scarica la patch e riesegui localmente con git diff --histogram — il risultato è spesso molto più facile da leggere.

La conclusione onesta

Imposta il tuo algoritmo Git globale su Histogram e non pensarci più per la maggior parte dei repository. Quando un diff ti confonde dopo un refactoring, riesegui con un algoritmo diverso prima di assumere che la modifica sia sbagliata. Normalizza gli spazi e le terminazioni di riga a livello di repository così i revisori passano il tempo sulla logica, non sulla formattazione. E ricorda che il diff è una presentazione, non la verità — la verità sono i due file, e un diff è solo uno dei tanti modi validi per descrivere il percorso tra loro.