Porównaj dwa pliki

„Diffy” to lingua franca zmian. To zwięzłe narracje, które mówią ci, co się zmieniło między dwiema wersjami czegoś — kodu źródłowego, prozy, zbioru danych — bez zmuszania cię do ponownego czytania wszystkiego. Za tymi kilkoma symbolami (+, -, @@) kryje się głęboki stos algorytmów, heurystyk i formatów, które równoważą optymalność, szybkość i ludzkie zrozumienie. Ten artykuł to praktyczna, od algorytmów do przepływów pracy, wycieczka po diffach: jak są obliczane, jak są formatowane, jak używają ich narzędzia do scalania i jak je dostrajać, aby uzyskać lepsze recenzje. Po drodze będziemy opierać twierdzenia na źródłach pierwotnych i oficjalnych dokumentach — ponieważ drobne szczegóły (takie jak to, czy białe znaki się liczą) naprawdę mają znaczenie.

Czym właściwie jest „diff”

Formalnie diff opisuje najkrótszy skrypt edycyjny (SES) do przekształcenia „starej” sekwencji w „nową” za pomocą wstawień i usunięć (a czasami podstawień, które można modelować jako usuń+wstaw). W praktyce większość diffów skierowanych do programistów jestzorientowana na linie, a następnie opcjonalnie dopracowywana do słów lub znaków w celu czytelności. Kanonicznymi wynikami są formaty kontekstowy i zunifikowany ; ten drugi — to, co zwykle widzisz w recenzji kodu — kompresuje dane wyjściowe za pomocą zwięzłego nagłówka i „fragmentów”, z których każdy pokazuje sąsiedztwo kontekstu wokół zmian. Format zunifikowany jest wybierany za pomocą -u/--unified i jest de facto standardem do łatania; patch generalnie korzysta z linii kontekstowych , aby solidnie zastosować zmiany.

Podręcznik GNU diff kataloguje przełączniki, po które sięgasz, gdy chcesz mniej szumu i więcej sygnału — ignorowanie pustych znaków, rozwijanie tabulatorów w celu wyrównania lub proszenie o „minimalny” skrypt edycyjny, nawet jeśli jest wolniejszy (odniesienie do opcji). Te opcje не zmieniają tego, co oznacza, że dwa pliki się różnią; zmieniają jak agresywnie algorytm szuka mniejszych skryptów i jak wynik jestprezentowany ludziom.

Od LCS do Myersa: jak obliczane są diffy

Większość diffów tekstowych opiera się na abstrakcji najdłuższego wspólnego podciągu (LCS) . Klasyczne programowanie dynamiczne rozwiązuje LCS w czasie i przestrzeni O(mn), ale jest to zbyt wolne i pamięciożerne dla dużych plików. Algorytm Hirschberga pokazał, jak obliczać optymalne dopasowania w przestrzeni liniowej (wciąż czas O(mn)) przy użyciu metody „dziel i zwyciężaj”, fundamentalnej techniki oszczędzania miejsca, która wpłynęła na praktyczne implementacje diff.

Dla szybkości i jakości przełomem był algorytm Eugene'a W. Myersa z 1986 roku, który znajduje SES w czasie O(ND) (N ≈ całkowita liczba linii, D ≈ odległość edycyjna) i niemal liniowej przestrzeni. Myers modeluje edycje w „grafie edycji” i postępuje wzdłużnajdalszych granic, dając wyniki, które są zarówno szybkie, jak i bliskie minimalnym w ustawieniu diffów liniowych. Dlatego „Myers” pozostaje domyślnym w wielu narzędziach.

Istnieje również rodzina Hunt–Szymanski , która przyspiesza LCS, gdy niewiele pozycji pasuje (poprzez wstępne indeksowanie dopasowań i ściganie rosnących podciągów), i jest historycznie powiązana z wczesnymi wariantami diff. Te algorytmy naświetlają kompromisy: w danych wejściowych z rzadkimi dopasowaniami mogą działać subkwadratowo. Aby zapoznać się z przeglądem praktyka łączącym teorię i implementację, zobacz notatki Neila Frasera.

Gdy „optymalny” nie jest czytelny: strategie cierpliwości i histogramu

Myers dąży do minimalnych skryptów edycyjnych, ale „minimalny” ≠ „najbardziej czytelny”. Duże bloki przestawione lub zduplikowane mogą oszukać czysty algorytm SES w niezręczne dopasowania. Wprowadź patience diff, przypisywany Bramowi Cohenowi: zakotwicza się na unikalnych, rzadko występujących liniach, aby ustabilizować dopasowania, często tworząc diffy, które ludzie uważają za czystsze — zwłaszcza w kodzie z przeniesionymi funkcjami lub przeorganizowanymi blokami. Wiele narzędzi udostępnia to za pomocą opcji „cierpliwość” (np.diff.algorithm).

Histogram diff rozszerza cierpliwość o histogram częstotliwości, aby lepiej radzić sobie z elementami o niskiej częstotliwości występowania, pozostając szybkim (spopularyzowany w JGit). Jeśli kiedykolwiek stwierdziłeś, że --histogram tworzy wyraźniejsze fragmenty dla zaszumionych plików, to jest to celowe. W nowoczesnym Git możesz wybrać algorytm globalnie lub dla każdego wywołania:git config diff.algorithm myers|patience|histogram lub git diff --patience.

Przejrzystość na poziomie słów, kontrola białych znaków i podświetlanie przeniesionego kodu

Diffy liniowe są zwięzłe, ale mogą ukrywać drobne edycje. Diffy na poziomie słów (--word-diff) kolorują zmiany wewnątrz linii bez zalewania recenzji całymi wstawieniami/usunięciami linii — świetne do prozy, długich ciągów znaków lub jednolinijkowców.

Białe znaki mogą zalać diffy po przeformatowaniu. Zarówno Git, jak i GNU diff pozwalają ignorować zmiany spacji w różnym stopniu, a opcje białych znaków GNU diff (-b, -w, -B) pomagają, gdy działa formater; zobaczysz edycje logiczne zamiast szumu wyrównania.

Gdy kod jest przenoszony w całości, Git może podświetlić przeniesione bloki za pomocą --color-moved, wizualnie oddzielając „przeniesione” od „zmodyfikowanych”, co pomaga recenzentom sprawdzić, czy przeniesienie nie ukryło niezamierzonych edycji. Utrwal to za pomocą diff.colorMoved.

Diffy w służbie scalania: dwukierunkowe vs. trójkierunkowe i diff3

Diff dwukierunkowy porównuje dokładnie dwie wersje; nie może stwierdzić, czy obie strony edytowały tę samą linię bazową, więc często powoduje nadmierne konflikty. Scalanie trójkierunkowe (używane przez nowoczesne VCS) oblicza diffy z wspólnego przodkado każdej strony, a następnie uzgadnia dwa zestawy zmian. To dramatycznie redukuje fałszywe konflikty i zapewnia lepszy kontekst. Klasycznym rdzeniem algorytmicznym jest tutaj diff3, który scala zmiany z „O” (bazy) do „A” i „B” i w razie potrzeby oznacza konflikty.

Prace akademickie i przemysłowe wciąż formalizują i ulepszają poprawność scalania; na przykład zweryfikowane scalania trójkierunkowe proponują semantyczne pojęcia wolności od konfliktów. W codziennym Gicie nowoczesna strategia scalania ort opiera się na diffowaniu i wykrywaniu zmian nazw, aby tworzyć scalenia z mniejszą liczbą niespodzianek. Dla użytkowników kluczowe wskazówki to: pokazywanie linii bazowych w konfliktach za pomocą merge.conflictStyle=diff3i częste integrowanie, aby diffy pozostały małe.

Wykrywanie zmian nazw i jego progi

Tradycyjne diffy nie mogą „widzieć” zmian nazw, ponieważ adresowanie treści traktuje pliki jak bloby; widzą tylko usunięcie i dodanie. Heurystyki wykrywania zmian nazw przerzucają most nad tą przepaścią, porównując podobieństwo między dodanymi/usuniętymi parami. W Git włącz lub dostosuj za pomocą -M/--find-renames[=<n>] (domyślnie ~50% podobieństwa). Zmniejsz ją dla bardziej zaszumionych przeniesień. Możesz ograniczyć porównania kandydatów za pomocą diff.renameLimit (i merge.renameLimit podczas scalania). Aby śledzić historię przez zmiany nazw, użyj git log --follow -- <path>. Nowszy Git wykonuje również wykrywanie zmian nazw katalogów , aby propagować przeniesienia folderów podczas scalania.

Diffy binarne i delta: rsync, VCDIFF/xdelta, bsdiff

Tekst to не jedyna rzecz, która się zmienia. W przypadku plików binarnych zazwyczaj chcesz kodowania delta — emituj instrukcje kopiowania/dodawania, aby zrekonstruować cel z źródła. Algorytm rsync zapoczątkował wydajne różnicowanie zdalne przy użyciu kroczących sum kontrolnych do wyrównywania bloków w sieci, minimalizując przepustowość.

IETF znormalizowało ogólny format delta, VCDIFF (RFC 3284), opisujący kod bajtowy ADD, COPY i RUN, z implementacjami takimi jak xdelta3 używającymi go do łatania binarnego. W przypadku kompaktowych łatek na plikach wykonywalnych, bsdiff często tworzy bardzo małe delty za pomocą tablic sufiksowych i kompresji; wybierz go, gdy rozmiar łatki dominuje, a generowanie może odbywać się offline.

Diffy tekstowe poza kodem źródłowym: dopasowywanie rozmyte i łatanie

Gdy potrzebujesz solidnego łatania w obliczu współbieżnych edycji lub nieco niedopasowanych kontekstów — pomyśl o edytorach lub systemach współpracy — rozważ diff-match-patch. Łączy on różnicowanie w stylu Myersa z Bitap dopasowywaniem rozmytym, aby znaleźć bliskie dopasowania i zastosować łatki „na miarę możliwości”, plus przyspieszenia przed diffem i czyszczenie po diffie, które zamieniają odrobinę minimalizmu na ładniejszy ludzki wynik. Jak łączyć diff i łatkę rozmytą w ciągłych pętlach synchronizacji, zobacz w Synchronizacji RóżnicowejFrasera.

Diffy danych strukturalnych: tabele i drzewa

Diffy liniowe na CSV/TSV są kruche, ponieważ zmiana jednej komórki może wyglądać jak edycja całej linii. Narzędzia diff świadome tabel (daff) traktują dane jako wiersze/kolumny, emitując łatki, które celują w określone komórki i renderując wizualizacje, które uwidaczniają dodania, usunięcia i modyfikacje (zobacz winietę R). Do szybkich sprawdzeń specjalistyczne różnice CSV mogą podświetlać zmiany komórka po komórce i zmiany typów; nie są one algorytmicznie egzotyczne, ale zwiększają sygnał recenzji, porównując strukturę, na której faktycznie ci zależy.

Praktyczne dostrajanie Git diff: lista kontrolna recenzenta

• Wybierz odpowiedni algorytm: zacznij od Myersa (domyślnie), spróbuj --patience , jeśli zmiany kolejności lub zaszumione bloki mylą wynik, lub --histogram dla szybkich, czytelnych diffów na powtarzalnym tekście. Ustaw domyślny za pomocą git config diff.algorithm ….
• Zmniejsz szum: w przypadku edycji tylko stylistycznych użyj flag białych znaków (-b, -w, --ignore-blank-lines), aby skupić się na istotnych zmianach. Poza Gitem zobacz kontrolki białych znaków GNU diff.
• Zobacz wewnątrz linii: --word-diff pomaga w przypadku długich linii i prozy.
• Sprawdź przeniesiony kod: --color-moved (lub diff.colorMoved) oddziela „przeniesione” od „zmodyfikowanych”.
• Obsługuj zmiany nazw: podczas recenzowania refaktoryzacji dodaj -M lub dostosuj próg podobieństwa (-M90%, -M30%), aby wychwycić zmiany nazw; pamiętaj, że domyślnie jest to około 50%. W przypadku głębokich drzew ustaw diff.renameLimit.
• Śledź historię przez zmiany nazw: git log --follow -- <path>.

Jak scalania faktycznie zużywają diffy (i co robić, gdy tego nie robią)

Scalanie oblicza dwa diffy (BASE→OURS, BASE→THEIRS) i próbuje zastosować oba do BASE. Strategie takie jak ort organizują to na dużą skalę, uwzględniając wykrywanie zmian nazw (w tym przeniesienia na skalę katalogu) i heurystyki w celu zminimalizowania konfliktów. Gdy występują konflikty, --conflict=diff3 wzbogaca znaczniki o kontekst bazowy, który jest nieoceniony do zrozumienia intencji. Rozdział Pro Git o Zaawansowanym Scalaniu przedstawia wzorce rozwiązywania, a dokumentacja Gita wymienia pokrętła takie jak -X ours i -X theirs. Aby zaoszczędzić czas na powtarzających się konfliktach, włącz rerere , aby nagrywać i odtwarzać swoje rozwiązania.

Poza plikami: scenariusze zdalne i przyrostowe

Jeśli synchronizujesz duże zasoby przez sieć, jesteś bliżej rsync świata niż lokalnego diff. Rsync oblicza kroczące sumy kontrolne, aby odkryć pasujące bloki zdalnie, a następnie przesyła tylko to, co konieczne. W przypadku spakowanych delt, VCDIFF/xdelta daje standardowy kod bajtowy i dojrzałe narzędzia; wybierz go, gdy kontrolujesz zarówno koder, jak i dekoder. A jeśli rozmiar łatki jest najważniejszy (np. oprogramowanie układowe over-the-air), bsdiff wymienia procesor/pamięć w czasie kompilacji na bardzo małe łatki.

Szybkie słowo o „rozmytym” i „przyjaznym”

Biblioteki takie jak diff-match-patch akceptują, że w prawdziwym świecie plik, który łatasz, mógł się zmienić. Łącząc solidny diff (często Myers) z dopasowywaniem rozmytym (Bitap) i konfigurowalnymi regułami czyszczenia, mogą znaleźć właściwe miejsce do zastosowania łatki i uczynić diff bardziej czytelnym — kluczowe dla edycji współpracy i synchronizacji.

„Stawki stołowe”, które powinieneś zinternalizować

1. Znaj swoje formaty. Zunifikowane diffy (-u/-U<n>) są kompaktowe i przyjazne dla łatek; to, czego oczekuje recenzja kodu i CI (odniesienie).
2. Znaj swoje algorytmy. Myers dla minimalnych edycji szybko (artykuł); cierpliwość/histogram dla czytelności przy zmianach kolejności lub zaszumionych blokach (cierpliwość, histogram); Hirschberg dla sztuczki z przestrzenią liniową (artykuł); Hunt–Szymanski dla przyspieszenia rzadkich dopasowań (artykuł).
3. Znaj swoje przełączniki. Kontrolki białych znaków, word-diff i color-moved są mnożnikami recenzji (dokumentacja git diff; opcje białych znaków GNU).
4. Znaj swoje scalania. Trójkierunkowe z diff3 -stylem jest mniej mylące; ort plus wykrywanie zmian nazw zmniejsza churn; rerere oszczędza czas.
5. Wybierz odpowiednie narzędzie do danych. Do CSV/tabel użyj daff; do plików binarnych użyj VCDIFF/xdelta lub bsdiff.

Dodatek: mała książka kucharska poleceń

Ponieważ pamięć mięśniowa ma znaczenie:

# Pokaż standardowy zunifikowany diff z dodatkowym kontekstem
  git diff -U5
  diff -u -U5 a b
  
  # Uzyskaj przejrzystość na poziomie słów dla długich linii lub prozy
  git diff --word-diff
  
  # Ignoruj szum białych znaków po przeformatowaniu
  git diff -b -w --ignore-blank-lines
  diff -b -w -B a b
  
  # Podświetl przeniesiony kod podczas recenzji
  git diff --color-moved
  git config --global diff.colorMoved default
  
  # Okiełznaj refaktoryzacje za pomocą wykrywania zmian nazw i śledź historię przez zmiany nazw
  git diff -M
  git log --follow -- <file>
  
  # Preferuj algorytm dla czytelności
  git diff --patience
  git diff --histogram
  git config --global diff.algorithm patience
  
  # Zobacz linie bazowe w znacznikach konfliktu
  git config --global merge.conflictStyle diff3

Myśl końcowa

Świetne diffy to mniej dowodzenie minimalności, a bardziej maksymalizacja zrozumienia recenzenta przy minimalnym koszcie poznawczym. Dlatego ekosystem wyewoluował wiele algorytmów (Myers, cierpliwość, histogram), wiele prezentacji (zunifikowany, word-diff, color-moved) i narzędzia świadome domeny (daff dla tabel, xdelta/bsdiff dla plików binarnych). Naucz się kompromisów, dostosuj pokrętła, a spędzisz więcej czasu na rozważaniuintencji i mniej czasu na ponownym składaniu kontekstu z czerwonych i zielonych linii.