手動實現 git 的 git diff 功能

這是 git diff 后的效果，感覺挺簡單的，不就是比較新舊版本，新增了就用 "+" 顯示新加一行，刪除了就用 "-" 顯示刪除一行，修改了一行就用 "-"、"+" 顯示將舊版本中的該行干掉了并且新版本中增加了一行，即使用 "刪除" + "新增" 操作代替 "修改" 操作，然后就用

然后我們寫的測試代碼如下：

import com.goldwind.ipark.common.util.MyStringUitls;
import org.apache.commons.text.similarity.LevenshteinDistance;import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;public class MyDiffTest {public static void main(String[] args) {List<String> lines_old = loadTxtFile2List("C:\\E\\javaCode\\git\\outer_project\\guodiantou\\gdtipark-user-servie\\src\\main\\java\\com\\goldwind\\ipark\\base\\test\\DemoClass1.java" );List<String> lines_new = loadTxtFile2List("C:\\E\\javaCode\\git\\outer_project\\guodiantou\\gdtipark-user-servie\\src\\main\\java\\com\\goldwind\\ipark\\base\\test\\DemoClass2.java");// lines1的起始行和 lines2 的起始行做映射// 掃描舊版本中的每一行int size = lines_old.size();for( int i=0;i<size;i++ ){// 從新版本中找該行String line_old = lines_old.get(i);String line_new = lines_new.get(i);// 如果發現版本中中該行的數據變了，那么提示刪除了舊的行，添加了新的行if( line_new.equals( line_old ) ){System.out.println( line_old );}else {System.out.println( "- " + line_old );System.out.println( "+ " + line_new );}}// xxxx        xxxx1          -xxxx// yyyy        yyyy           +xxxx1// xxxxxx      xxxxxx         xxxxxx// zzzz        zzzz           zzzz}private static List<String> loadTxtFile2List(String filePath) {BufferedReader reader = null;List<String> lines = new ArrayList<>();try {reader = new BufferedReader(new FileReader(filePath));String line = reader.readLine();while (line != null) {// System.out.println(line);lines.add( line );line = reader.readLine();}return lines;} catch (Exception e) {e.printStackTrace();return null;} finally {if (reader != null) {try {reader.close();} catch (Exception e) {e.printStackTrace();}}}}
}

其中用到的2個新舊版本的文本如下：

DemoClass1.java：

import com.goldwind.ipark.common.exception.BusinessLogicException;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.text.similarity.LevenshteinDistance;@Slf4j
public class DemoClass1 {private static final LevenshteinDistance LEVENSHTEIN_DISTANCE = LevenshteinDistance.getDefaultInstance();public static String null2emptyWithTrim( String str ){if( str == null ){str = "";}str = str.trim();return str;}public static String requiredStringParamCheck(String param, String paramRemark) {param = null2emptyWithTrim( param );if( param.length() == 0 ){String msg = "操作失敗，請求參數 \"" + paramRemark + "\" 為空";log.error( msg );throw new BusinessLogicException( msg );}return param;}public static double calculateSimilarity( String str1,String str2 ){int distance = LEVENSHTEIN_DISTANCE.apply(str1, str2);double similarity = 1 - (double) distance / Math.max(str1.length(), str2.length());System.out.println("相似度：" + similarity);return similarity;}
}

DemoClass2.java：

import com.goldwind.ipark.common.exception.BusinessLogicException;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.text.similarity.LevenshteinDistance;@Slf4j
public class DemoClass2 {private static final LevenshteinDistance LEVENSHTEIN_DISTANCE = LevenshteinDistance.getDefaultInstance();private static final LevenshteinDistance LEVENSHTEIN_DISTANCE1 = LevenshteinDistance.getDefaultInstance();private static final LevenshteinDistance LEVENSHTEIN_DISTANCE2 = LevenshteinDistance.getDefaultInstance();public static String null2emptyWithTrim( String str ){if( str == null ){str = "";}str = str.trim();return str;}public static String requiredStringParamCheck(String param, String paramRemark) {param = null2emptyWithTrim( param );if( param.length() == 0 ){String msg = "操作失敗，請求參數 \"" + paramRemark + "\" 為空";log.error( msg );throw new BusinessLogicException( msg );}return param;}public static double calculateSimilarity( String str1,String str2 ){int distance = LEVENSHTEIN_DISTANCE.apply(str1, str2);double similarity = 1 - (double) distance / Math.max(str1.length(), str2.length());System.out.println("相似度：" + similarity);return similarity;}
}

DemoClass2.java 相較于 DemoClass1.java 的區別是 "public class" 后面的類名不同，"private static final LevenshteinDistance LEVENSHTEIN_DISTANC..." 多復制了2行并改了名稱，然后運行后顯示差別如下：

import com.goldwind.ipark.common.exception.BusinessLogicException;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.text.similarity.LevenshteinDistance;@Slf4j
- public class DemoClass1 {
+ public class DemoClass2 {private static final LevenshteinDistance LEVENSHTEIN_DISTANCE = LevenshteinDistance.getDefaultInstance();
- 
+     private static final LevenshteinDistance LEVENSHTEIN_DISTANCE1 = LevenshteinDistance.getDefaultInstance();
-     public static String null2emptyWithTrim( String str ){
+     private static final LevenshteinDistance LEVENSHTEIN_DISTANCE2 = LevenshteinDistance.getDefaultInstance();
-         if( str == null ){
+ 
-             str = "";
+     public static String null2emptyWithTrim( String str ){
-         }
+         if( str == null ){
-         str = str.trim();
+             str = "";
-         return str;
+         }
-     }
+         str = str.trim();
- 
+         return str;
-     public static String requiredStringParamCheck(String param, String paramRemark) {
+     }
-         param = null2emptyWithTrim( param );
+ 
-         if( param.length() == 0 ){
+     public static String requiredStringParamCheck(String param, String paramRemark) {
-             String msg = "操作失敗，請求參數 \"" + paramRemark + "\" 為空";
+         param = null2emptyWithTrim( param );
-             log.error( msg );
+         if( param.length() == 0 ){
-             throw new BusinessLogicException( msg );
+             String msg = "操作失敗，請求參數 \"" + paramRemark + "\" 為空";
-         }
+             log.error( msg );
-         return param;
+             throw new BusinessLogicException( msg );
-     }
+         }
- 
+         return param;
-     public static double calculateSimilarity( String str1,String str2 ){
+     }
-         int distance = LEVENSHTEIN_DISTANCE.apply(str1, str2);
+ 
-         double similarity = 1 - (double) distance / Math.max(str1.length(), str2.length());
+     public static double calculateSimilarity( String str1,String str2 ){
-         System.out.println("相似度：" + similarity);
+         int distance = LEVENSHTEIN_DISTANCE.apply(str1, str2);
-         return similarity;
+         double similarity = 1 - (double) distance / Math.max(str1.length(), str2.length());
-     }
+         System.out.println("相似度：" + similarity);
- }
+         return similarity;

為啥？？？

如上兩張圖片，舊版本的第10行和新版本的第10行對應，從直觀上看新版本的第11、12行是在舊版本的第10行和第11行之間插進去的，但是程序并不這么認為，它會認為將舊版本的第11行的空白行修改為了新版本的 “private static final LevenshteinDistance LEVENSHTEIN_DISTANCE1 = LevenshteinDistance.getDefaultInstance();” 為什么我們人眼會這么直觀的感覺到新版本的第11、12行時插進去的，因為我們比較了新舊版本的第7、8、9、10行都差不多，舊版本的11~27行和新版本的 13~29行都差不多，所以自然而然的認為新版本的11、12行是直接插進去的，那么現在我們就來算法實現吧！（ ps：前文中的 “差不多” 是差幾多？是完全equals 還是很像？”其實這里可以設置一個閾值，使用求字符串的相似度算法求出相似度，網上有現成的類庫求相似度，自己也可以使用動態規劃寫一個簡單的字符串相似度算法?）

感覺恰當的算法的執行過程應該是這樣的：

新舊版本各維持一個行號游標：index_old、index_new，最開始這兩個游標相同，越往后可能不同，但是他們表示的行的內容應該是應該相似的，因為新版本的修改會導致內容越來越 “錯位”。假設我們從上面2張圖片的第7行開始描：

? ? ? ? 1. 最開始?index_old =?index_new = 7，算法檢測到新舊版本的第7行的內容相同( 后面我們就盡量用偽代碼表示，就不說這么多啰里啰嗦的話了?)，即 lines_old[?7] = lines_new[?7]。

? ? ? ? 2.?index_old++，index_new++，都變為8，算法檢測到 lines_old[ 8 ] != lines_new[?index_new ]，并且他們的相似度很高，所以算法判斷新版本的第8行相較于舊版本的第8行是做了修改操作。

? ? ? ? 3.?index_old++，index_new++，都變為9，算法檢測到 lines_old[ 9?] = lines_new[ 9 ]。

? ? ? ? 4.?index_old++，index_new++，都變為10，算法檢測到 lines_old[ 10?] = lines_new[ 10?]。

? ? ? ? 5.??index_old++，index_new++，都變為11，算法檢測到 lines_old[ 11?] !=??lines_new[ 11?]，并且這兩行的文本內容及不相似，所以判斷新版本是在舊版本的第11行插入了一行 “private static final LevenshteinDistance LEVENSHTEIN_DISTANCE1 =LevenshteinDistance.getDefaultInstance();”，所以此時舊版本的第11行就和新版本的第11行對應不上了，而是和新版本的第12行做對應。

? ? ? ? 6.??index_old 不變，index_new++，index_old 還是11，index_new 變為 12，即舊版本的第11行要和新版本的第12行做對應，就像找老婆一樣，舊7和新7結為了夫妻，舊8和新8結為了夫妻( 雖然有一點點的裂痕，但不打緊?)，新9和新9結為了夫妻，...，所以舊11也要在新版本中找到一個新x作為自己的伴侶，本來已經找到了一個新11，但是發現新11和自己三觀差別很大，根本合不來，所以pass掉，繼續找，現在發現了下一個相親對象新12，發現lines_old[ 11 ] 和 lines_new[ 12 ] 相似度還是差別很大，所以算法判斷新版本又插入了一個新行 “private static final LevenshteinDistance LEVENSHTEIN_DISTANCE2 = LevenshteinDistance.getDefaultInstance();”。

? ? ? ? 7.?index_old 不變，index_new++，index_old 還是11，index_new 變為 13，因為?lines_old[ 11 ] =?lines_new[ 13?],所以舊11 很幸運的找到了自己的伴侶新13,。

? ? ? ? 8.??index_old++，index_new++，index_old變為12，index_new變為14，因為?lines_old[ 12?] =?lines_new[ 14?],所以此步未檢測到變化。

? ? ? ? ...

改進后的測試代碼如下：