So sánh hai tệp tin

“Diffs” là ngôn ngữ chung của sự thay đổi. Chúng là những câu chuyện nhỏ gọn cho bạn biết cái gì đã di chuyển giữa hai phiên bản của một thứ—mã nguồn, văn xuôi, một tập dữ liệu—mà không buộc bạn phải đọc lại mọi thứ. Đằng sau vài biểu tượng đó (+, -, @@) là một chồng sâu các thuật toán, phương pháp phỏng đoán và định dạng cân bằng giữa tính tối ưu, tốc độ và sự hiểu biết của con người. Bài viết này là một chuyến tham quan thực tế, từ thuật toán đến quy trình làm việc của diffs: cách chúng được tính toán, cách chúng được định dạng, cách các công cụ hợp nhất sử dụng chúng và cách điều chỉnh chúng để có những bài đánh giá tốt hơn. Trên đường đi, chúng ta sẽ củng cố các tuyên bố trong các nguồn chính và tài liệu chính thức—bởi vì những chi tiết nhỏ (như liệu khoảng trắng có được tính hay không) thực sự quan trọng.

Một “diff” thực sự là gì

Về mặt hình thức, một diff mô tả một kịch bản chỉnh sửa ngắn nhất (SES) để biến đổi một chuỗi “cũ” thành một chuỗi “mới” bằng cách sử dụng các phép chèn và xóa (và đôi khi là các phép thay thế, có thể được mô hình hóa dưới dạng xóa+chèn). Trong thực tế, hầu hết các diff dành cho lập trình viên đềuhướng theo dòng và sau đó được tinh chỉnh tùy chọn thành các từ hoặc ký tự để dễ đọc. Các đầu ra kinh điển là các định dạng ngữ cảnh và thống nhất ; cái sau—cái bạn thường thấy trong đánh giá mã—nén đầu ra bằng một tiêu đề ngắn gọn và các “hunks”, mỗi cái hiển thị một vùng lân cận của ngữ cảnh xung quanh các thay đổi. Định dạng thống nhất được chọn thông qua -u/--unified và là tiêu chuẩn trên thực tế để vá lỗi; patch thường được hưởng lợi từ các dòng ngữ cảnh để áp dụng các thay đổi một cách mạnh mẽ.

Sách hướng dẫn GNU diff liệt kê các công tắc bạn tìm đến khi muốn ít tiếng ồn và nhiều tín hiệu hơn—bỏ qua khoảng trắng, mở rộng các tab để căn chỉnh hoặc yêu cầu một kịch bản chỉnh sửa “tối thiểu” ngay cả khi nó chậm hơn (tham khảo tùy chọn). Các tùy chọn này không thay đổi ý nghĩa của việc hai tệp khác nhau; chúng thay đổi cách thuật toán tìm kiếm các kịch bản nhỏ hơn một cách tích cực và cách kết quả đượctrình bày cho con người.

Từ LCS đến Myers: cách tính toán diffs

Hầu hết các diff văn bản được xây dựng trên sự trừu tượng của Dãy con chung dài nhất (LCS) . Lập trình động cổ điển giải quyết LCS trong thời gian và không gian O(mn), nhưng điều đó quá chậm và tốn bộ nhớ cho các tệp lớn. Thuật toán của Hirschberg đã chỉ ra cách tính toán các căn chỉnh tối ưu trong không gian tuyến tính (vẫn thời gian O(mn)) bằng cách sử dụng chia để trị, một kỹ thuật tiết kiệm không gian cơ bản đã ảnh hưởng đến các triển khai diff thực tế.

Để có tốc độ và chất lượng, bước đột phá là thuật toán của Eugene W. Myers năm 1986, tìm thấy một SES trong thời gian O(ND) (N ≈ tổng số dòng, D ≈ khoảng cách chỉnh sửa) và không gian gần như tuyến tính. Myers mô hình hóa các chỉnh sửa trong một “đồ thị chỉnh sửa” và tiến dọc theo các biên giới vươn xa nhất, mang lại kết quả vừa nhanh vừa gần với mức tối thiểu trong cài đặt diff dòng. Đó là lý do tại sao “Myers” vẫn là mặc định trong nhiều công cụ.

Ngoài ra còn có họ Hunt–Szymanski , giúp tăng tốc LCS khi có ít vị trí khớp (bằng cách lập chỉ mục trước các kết quả khớp và theo đuổi các dãy con tăng dần), và có liên quan lịch sử đến các biến thể diff ban đầu. Các thuật toán này làm sáng tỏ các sự đánh đổi: trong các đầu vào có các kết quả khớp thưa thớt, chúng có thể chạy dưới dạng bậc hai. Để có cái nhìn tổng quan của người thực hành kết nối lý thuyết và triển khai, hãy xem ghi chú của Neil Fraser.

Khi “tối ưu” không dễ đọc: chiến lược kiên nhẫn và biểu đồ

Myers nhắm đến các kịch bản chỉnh sửa tối thiểu, nhưng “tối thiểu” ≠ “dễ đọc nhất”. Các khối lớn được sắp xếp lại hoặc sao chép có thể đánh lừa một thuật toán SES thuần túy thành các căn chỉnh khó xử. Hãy tham gia patience diff, được cho là của Bram Cohen: nó neo vào các dòng độc đáo, tần suất thấp để ổn định các căn chỉnh, thường tạo ra các diff mà con người thấy sạch sẽ hơn—đặc biệt là trong mã có các hàm đã di chuyển hoặc các khối được tổ chức lại. Nhiều công cụ hiển thị điều này thông qua một tùy chọn “kiên nhẫn” (ví dụ:diff.algorithm).

Histogram diff mở rộng sự kiên nhẫn bằng một biểu đồ tần suất để xử lý tốt hơn các yếu tố xuất hiện ít trong khi vẫn nhanh (được phổ biến trong JGit). Nếu bạn đã từng thấy --histogram tạo ra các hunks rõ ràng hơn cho các tệp nhiễu, đó là do thiết kế. Trên Git hiện đại, bạn có thể chọn thuật toán trên toàn cầu hoặc cho mỗi lần gọi:git config diff.algorithm myers|patience|histogram hoặc git diff --patience.

Sự rõ ràng ở cấp độ từ, kiểm soát khoảng trắng và tô sáng mã đã di chuyển

Diffs dòng rất ngắn gọn nhưng có thể che khuất các chỉnh sửa nhỏ. Diffs cấp độ từ (--word-diff) tô màu các thay đổi trong dòng mà không làm tràn ngập bài đánh giá bằng các phép chèn/xóa toàn bộ dòng—tuyệt vời cho văn xuôi, các chuỗi dài hoặc các dòng đơn.

Khoảng trắng có thể làm tràn ngập diffs sau khi định dạng lại. Cả Git và GNU diff đều cho phép bạn bỏ qua các thay đổi về khoảng trắng ở các mức độ khác nhau và các tùy chọn khoảng trắng của GNU diff (-b, -w, -B) giúp ích khi một trình định dạng chạy; bạn sẽ thấy các chỉnh sửa logic thay vì nhiễu căn chỉnh.

Khi mã di chuyển toàn bộ, Git có thể tô sáng các khối đã di chuyển bằng --color-moved, tách biệt trực quan “đã di chuyển” khỏi “đã sửa đổi”, giúp người đánh giá kiểm tra xem một lần di chuyển có che giấu các chỉnh sửa không mong muốn hay không. Duy trì nó thông qua diff.colorMoved.

Diffs phục vụ cho việc hợp nhất: hai chiều so với ba chiều và diff3

Một diff hai chiều so sánh chính xác hai phiên bản; nó không thể cho biết liệu cả hai bên đã chỉnh sửa cùng một dòng cơ sở hay không, vì vậy nó thường gây ra quá nhiều xung đột. Hợp nhất ba chiều (được sử dụng bởi các VCS hiện đại) tính toán các diff từ một tổ tiên chungđến mỗi bên và sau đó dung hòa hai bộ thay đổi. Điều này làm giảm đáng kể các xung đột giả và cung cấp ngữ cảnh tốt hơn. Lõi thuật toán cổ điển ở đây là diff3, hợp nhất các thay đổi từ “O” (cơ sở) thành “A” và “B” và đánh dấu các xung đột khi cần thiết.

Công việc học thuật và công nghiệp tiếp tục chính thức hóa và cải thiện tính đúng đắn của việc hợp nhất; ví dụ, các hợp nhất ba chiều đã được xác minh đề xuất các khái niệm ngữ nghĩa về không có xung đột. Trong Git hàng ngày, chiến lược hợp nhất ort hiện đại được xây dựng dựa trên việc diff và phát hiện đổi tên để tạo ra các hợp nhất ít bất ngờ hơn. Đối với người dùng, các mẹo chính là: hiển thị các dòng cơ sở trong các xung đột bằng merge.conflictStyle=diff3, và tích hợp thường xuyên để các diff vẫn nhỏ.

Phát hiện đổi tên và các ngưỡng của nó

Diffs truyền thống không thể “nhìn thấy” việc đổi tên vì việc định địa chỉ nội dung coi các tệp là các blob; chúng chỉ thấy một lần xóa và một lần thêm. Các phương pháp phỏng đoán phát hiện đổi tên thu hẹp khoảng cách đó bằng cách so sánh sự tương đồng giữa các cặp đã thêm/xóa. Trong Git, hãy bật hoặc điều chỉnh thông qua -M/--find-renames[=<n>] (mặc định là ~50% sự tương đồng). Giảm nó xuống cho các lần di chuyển nhiễu hơn. Bạn có thể giới hạn các so sánh ứng cử viên bằng diff.renameLimit (và merge.renameLimit trong quá trình hợp nhất). Để theo dõi lịch sử qua các lần đổi tên, hãy sử dụng git log --follow -- <path>. Git gần đây cũng thực hiện phát hiện đổi tên thư mục để truyền bá các lần di chuyển thư mục trong quá trình hợp nhất.

Diffs nhị phân và delta: rsync, VCDIFF/xdelta, bsdiff

Văn bản không phải là thứ duy nhất thay đổi. Đối với các tệp nhị phân, bạn thường muốn mã hóa delta—phát hành các hướng dẫn sao chép/thêm để tái tạo một mục tiêu từ một nguồn. Thuật toán rsync đã đi tiên phong trong việc diff từ xa hiệu quả bằng cách sử dụng các tổng kiểm tra cuộn để căn chỉnh các khối trên một mạng, giảm thiểu băng thông.

IETF đã tiêu chuẩn hóa một định dạng delta chung, VCDIFF (RFC 3284), mô tả một bytecode của ADD, COPY, và RUN, với các triển khai như xdelta3 sử dụng nó để vá lỗi nhị phân. Đối với các bản vá nhỏ gọn trên các tệp thực thi, bsdiff thường tạo ra các delta rất nhỏ thông qua các mảng hậu tố và nén; hãy chọn nó khi kích thước bản vá chiếm ưu thế và việc tạo có thể diễn ra ngoại tuyến.

Diffs văn bản ngoài mã nguồn: khớp mờ và vá lỗi

Khi bạn cần vá lỗi mạnh mẽ khi đối mặt với các chỉnh sửa đồng thời hoặc các ngữ cảnh hơi lệch—hãy nghĩ đến các trình soạn thảo hoặc các hệ thống cộng tác—hãy xem xét diff-match-patch. Nó kết hợp việc diff kiểu Myers với Bitap khớp mờ để tìm các kết quả khớp gần đúng và áp dụng các bản vá “theo nỗ lực tốt nhất”, cộng với các tăng tốc trước diff và các dọn dẹp sau diff đổi một chút tính tối thiểu để có đầu ra con người đẹp hơn. Để biết cách kết hợp diff và bản vá mờ trong các vòng lặp đồng bộ hóa liên tục, hãy xem Đồng bộ hóa vi phâncủa Fraser.

Diffs dữ liệu có cấu trúc: bảng và cây

Diffs dòng trên CSV/TSV rất dễ vỡ vì một thay đổi một ô có thể trông giống như một chỉnh sửa toàn bộ dòng. Các công cụ diff nhận biết bảng (daff) coi dữ liệu là các hàng/cột, phát hành các bản vá nhắm vào các ô cụ thể và hiển thị các trực quan hóa làm cho các phép thêm, xóa và sửa đổi trở nên rõ ràng (xem R vignette). Để kiểm tra nhanh, các trình diff CSV chuyên dụng có thể tô sáng các thay đổi từng ô và các thay đổi loại; chúng không kỳ lạ về mặt thuật toán, nhưng chúng tăng tín hiệu đánh giá bằng cách so sánh cấu trúc mà bạn thực sự quan tâm.

Điều chỉnh Git diff thực tế: danh sách kiểm tra của người đánh giá

• Chọn thuật toán phù hợp: bắt đầu với Myers (mặc định), thử --patience nếu việc sắp xếp lại hoặc các khối nhiễu làm rối đầu ra, hoặc --histogram để có các diff nhanh, dễ đọc trên văn bản lặp đi lặp lại. Đặt mặc định bằng git config diff.algorithm ….
• Giảm nhiễu: đối với các chỉnh sửa chỉ về kiểu, hãy sử dụng các cờ khoảng trắng (-b, -w, --ignore-blank-lines) để tập trung vào các thay đổi thực chất. Ngoài Git, hãy xem các điều khiển khoảng trắng của GNU diff.
• Nhìn vào bên trong một dòng: --word-diff giúp ích cho các dòng dài và văn xuôi.
• Kiểm tra mã đã di chuyển: --color-moved (hoặc diff.colorMoved) tách “đã di chuyển” khỏi “đã sửa đổi”.
• Xử lý việc đổi tên: khi đánh giá các tái cấu trúc, hãy thêm -M hoặc điều chỉnh ngưỡng tương tự (-M90%, -M30%) để bắt các lần đổi tên; hãy nhớ rằng mặc định là khoảng 50%. Đối với các cây sâu, hãy đặt diff.renameLimit.
• Theo dõi lịch sử qua các lần đổi tên: git log --follow -- <path>.

Cách các hợp nhất thực sự tiêu thụ diffs (và phải làm gì khi chúng không làm vậy)

Một hợp nhất tính toán hai diff (BASE→OURS, BASE→THEIRS) và cố gắng áp dụng cả hai vào BASE. Các chiến lược như ort sắp xếp điều này ở quy mô lớn, kết hợp phát hiện đổi tên (bao gồm cả các di chuyển ở quy mô thư mục) và các phương pháp phỏng đoán để giảm thiểu xung đột. Khi xung đột xảy ra, --conflict=diff3 làm phong phú các điểm đánh dấu bằng ngữ cảnh cơ sở, điều này vô giá để hiểu ý định. Chương Pro Git về Hợp nhất nâng cao hướng dẫn qua các mẫu giải quyết, và tài liệu của Git liệt kê các nút như -X ours và -X theirs. Để tiết kiệm thời gian cho các xung đột lặp lại, hãy bật rerere để ghi lại và phát lại các giải pháp của bạn.

Ngoài các tệp: các kịch bản từ xa và tăng dần

Nếu bạn đang đồng bộ hóa các tài sản lớn qua mạng, bạn gần với rsync thế giới hơn là diff cục bộ. Rsync tính toán các tổng kiểm tra cuộn để khám phá các khối khớp từ xa, sau đó chỉ chuyển những gì cần thiết. Đối với các delta được đóng gói, VCDIFF/xdelta cung cấp cho bạn một bytecode tiêu chuẩn và các công cụ trưởng thành; hãy chọn nó khi bạn kiểm soát cả bộ mã hóa và bộ giải mã. Và nếu kích thước bản vá là tối quan trọng (ví dụ: phần mềm cơ sở qua mạng), bsdiff đổi CPU/bộ nhớ tại thời điểm xây dựng để lấy các bản vá rất nhỏ.

Một lời nhanh về “mờ” và “thân thiện”

Các thư viện như diff-match-patch chấp nhận rằng, trong thế giới thực, tệp bạn đang vá có thể đã bị trôi. Bằng cách kết hợp một diff vững chắc (thường là Myers) với khớp mờ (Bitap) và các quy tắc dọn dẹp có thể cấu hình, chúng có thể tìm đúng nơi để áp dụng một bản vá và làm cho diff dễ đọc hơn—quan trọng đối với việc chỉnh sửa cộng tác và đồng bộ hóa.

“Cược trên bàn” mà bạn nên nội tâm hóa

1. Biết các định dạng của bạn. Diffs thống nhất (-u/-U<n>) nhỏ gọn và thân thiện với bản vá; chúng là những gì mà đánh giá mã và CI mong đợi (tham khảo).
2. Biết các thuật toán của bạn. Myers cho các chỉnh sửa tối thiểu nhanh (bài báo); kiên nhẫn/biểu đồ để dễ đọc trên các sắp xếp lại hoặc các khối nhiễu (kiên nhẫn, biểu đồ); Hirschberg cho mẹo không gian tuyến tính (bài báo); Hunt–Szymanski để tăng tốc khớp thưa thớt (bài báo).
3. Biết các công tắc của bạn. Các điều khiển khoảng trắng, word-diff, và color-moved là các nhân tố đánh giá (tài liệu git diff; các tùy chọn khoảng trắng của GNU).
4. Biết các hợp nhất của bạn. Ba chiều với diff3 -kiểu ít gây nhầm lẫn hơn; ort cộng với phát hiện đổi tên làm giảm sự thay đổi; rerere tiết kiệm thời gian.
5. Chọn công cụ phù hợp cho dữ liệu. Đối với CSV/bảng, hãy sử dụng daff; đối với các tệp nhị phân, hãy sử dụng VCDIFF/xdelta hoặc bsdiff.

Phụ lục: sách dạy nấu ăn lệnh nhỏ

Bởi vì trí nhớ cơ bắp quan trọng:

# Hiển thị một diff thống nhất tiêu chuẩn với ngữ cảnh bổ sung
  git diff -U5
  diff -u -U5 a b
  
  # Nhận sự rõ ràng ở cấp độ từ cho các dòng dài hoặc văn xuôi
  git diff --word-diff
  
  # Bỏ qua nhiễu khoảng trắng sau khi định dạng lại
  git diff -b -w --ignore-blank-lines
  diff -b -w -B a b
  
  # Tô sáng mã đã di chuyển trong quá trình đánh giá
  git diff --color-moved
  git config --global diff.colorMoved default
  
  # Chế ngự các tái cấu trúc bằng phát hiện đổi tên và theo dõi lịch sử qua các lần đổi tên
  git diff -M
  git log --follow -- <file>
  
  # Ưu tiên thuật toán để dễ đọc
  git diff --patience
  git diff --histogram
  git config --global diff.algorithm patience
  
  # Xem các dòng cơ sở trong các điểm đánh dấu xung đột
  git config --global merge.conflictStyle diff3

Suy nghĩ kết luận

Các diff tuyệt vời ít liên quan đến việc chứng minh tính tối thiểu hơn là tối đa hóa sự hiểu biết của người đánh giá với chi phí nhận thức tối thiểu. Đó là lý do tại sao hệ sinh thái đã phát triển nhiều thuật toán (Myers, kiên nhẫn, biểu đồ), nhiều cách trình bày (thống nhất, word-diff, color-moved), và các công cụ nhận biết miền (daff cho bảng, xdelta/bsdiff cho các tệp nhị phân). Hãy tìm hiểu các sự đánh đổi, điều chỉnh các nút, và bạn sẽ dành nhiều thời gian hơn để suy luận về ý định và ít thời gian hơn để lắp ráp lại ngữ cảnh từ các dòng màu đỏ và xanh lá cây.