Metin Diff Algoritmaları: Git, Yamalar ve Diff Araçları Nasıl Çalışır

Her kod inceleme aracı, her git diffçıktısı, okuduğunuz her yama dosyası, 1976 ile 2009 arasında icat edilen az sayıda algoritmaya dayanır. Aracınızın hangisini kullandığını — ve hangi varsayımı yaptığını — bilmek, bir diff’i 30 saniyede okumak ile yeniden düzenlemenin davranışı gerçekten koruyup korumadığını sorgulayarak on dakika bakmak arasındaki farktır.

Diff gerçekte nedir

Diff, A dosyasını B dosyasına dönüştüren minimal bir ekleme ve silme dizisi olan bir düzenleme betiğidir. Bir diff algoritması, bazı optimizasyon kriterlerine göre bir tane seçer — genellikle en küçükD, ama her zaman değil.

Metin diff aracımızla iki dosyayı kendiniz karşılaştırabilir ve birleşik çıktıyı yan yana görebilirsiniz.

Myers diff — her yerde varsayılan

Eugene Myers'ın 1986 tarihli An O(ND) Difference Algorithm and Its Variations makalesi, GNU diff, Git, Mercurial, SVN ve çoğu düzenleyicinin hâlâ varsayılan olarak kullandığı algoritmayı tanımladı. Diff sorununu bir düzenleme grafiğinde en kısa yolu bulmak olarak çerçeveler.

Myers’ın zayıflığı, diff boyutunu herhangi bir yapı algısı olmaksızın en aza indirmesidir. Bir kod bloğu taşındıktan sonra Myers, daha az toplam değişen satır ürettiği için bir fonksiyonun kapanış parantezini farklı bir fonksiyonununkiyle sıklıkla eşleştirir. Sonuç teknik olarak minimaldir ve insan açısından şaşırtıcıdır.

Patience diff — okunabilirlik için tasarlandı

Bram Cohen (BitTorrent’ın yazarı) Patience diff’i 2007’de özellikle Myers’ın yeniden düzenleme okunabilirliği sorununu gidermek için tanıttı. Algoritma:

1. Her iki dosyada tam olarak bir kez görünen tüm satırları bulun. Bunlar benzersiz çapa satırlarıdır.
2. Benzersiz çapaların en uzun ortak alt dizisini hesaplayın.
3. Ardışık çapalar arasındaki her bölgeyi aynı prosedürü kullanarak özyinelemeli olarak diff’leyin.

Git’te git diff --patience ile veya git config diff.algorithm patience ile genel olarak etkinleştirin.

Histogram diff — Patience’ın geliştirilmiş hali

Histogram diff JGit tarafından tanıtıldı ve daha sonra üst git’e taşındı. Benzersizlik yerine her iki dosyadaki en düşük oluşum sayısına sahip nadir satırları seçerek Patience’ı iyileştirir. Ortak satırlar (kapanış parantezleri, boş satırlar) düşük önceliklidir; nadir satırlar (fonksiyon adları, ayırt edici dizeler) çapa haline gelir.

Histogram, bugün çoğu depo için önerilen varsayılandır. git config --global diff.algorithm histogram ile genel olarak etkinleştirin.

Birleşik diff hunk’ını okumak

Birleşik diff (-u) fiili değişim formatıdır. Bir hunk şöyle görünür:

@@ -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);
 }

@@ satırı hunk başlığıdır. Eski dosyanın 42. satırdan başladığını ve 7 satır kapladığını; yeni dosyanın 42. satırdan başladığını ve 9 satır kapladığını söyler. Önek olmayan satırlar değişmemiş bağlamdır. -ile başlayan satırlar yalnızca eski dosyada mevcuttur; + ile başlayan satırlar yalnızca yeni dosyada.

Üç yönlü birleştirme ve çakışmaların neden oluştuğu

B dalını A dalına birleştirdiğinizde Git üç versiyona bakar: ortak ata C, A versiyonu ve B versiyonu. Birleştirme satır satır ilerler:

• C’den A’ya değişmemiş ancak B’de değiştirilmiş → B’yi al.
• A’da değiştirilmiş ancak B’de değişmemiş → A’yı al.
• Her ikisinde de aynı şekilde değiştirilmiş → herhangi birini al; çakışma yok.
• A ve B’de farklı şekilde değiştirilmiş → çakışma.

Pratikte algoritma seçimi

Günlük çalışmada Histogram en iyi varsayılandır ve çoğu ekibin genel olarak yapılandırması gereken algoritmadır. Patience benzer sonuçlar üretir ve Histogram’ın bellek kullanımının belirgin hale geldiği çok büyük dosyalar için faydalı kalır. Myers, diff’leri programatik olarak tüketen makine-arası hatlar için doğru tercihtir çünkü çıktısı kanonik minimumdur.

Dürüst özet

Global Git algoritmanızı Histogram’a geçirin ve çoğu depo için bir daha düşünmeyin. Bir yeniden düzenleme sonrası diff sizi şaşırtırsa, değişikliğin yanlış olduğunu varsaymadan önce farklı bir algoritmayla yeniden görselleştirin. Boşlukları ve satır sonlarını depo düzeyinde normalleştirin. Ve diff’in bir sunum olduğunu, gerçek olmadığını unutmayın — gerçek iki dosyadır; diff ise aralarındaki yolu tanımlamanın pek çok geçerli yolundan biridir.