1 (** Tests for the line-level diff algorithm and hunk generation. *) 2 3 let test_line_diff () = 4 let open Ogit.Resolvers.Diff in 5 match of_contents "first\nold\nlast\n" "first\nnew\nlast\n" with 6 | [ ctx1; del; add; ctx2 ] -> 7 Alcotest.(check string) "ctx1 text" "first" ctx1.text; 8 Alcotest.(check string) "del text" "old" del.text; 9 Alcotest.(check string) "add text" "new" add.text; 10 Alcotest.(check string) "ctx2 text" "last" ctx2.text 11 | lines -> Alcotest.failf "expected 4 lines, got %d" (List.length lines) 12 13 let test_empty_vs_empty () = 14 let open Ogit.Resolvers.Diff in 15 let lines = of_contents "" "" in 16 Alcotest.(check int) "no lines" 0 (List.length lines); 17 let hunks = hunks lines in 18 Alcotest.(check int) "no hunks" 0 (List.length hunks) 19 20 let test_identical_content () = 21 let open Ogit.Resolvers.Diff in 22 let content = "line1\nline2\nline3\n" in 23 let lines = of_contents content content in 24 List.iter 25 (fun line -> Alcotest.(check bool) "all context" true (line.kind = Context)) 26 lines; 27 let hunks = hunks lines in 28 Alcotest.(check int) "no hunks for identical" 0 (List.length hunks) 29 30 let test_entirely_new_file () = 31 let open Ogit.Resolvers.Diff in 32 let lines = of_contents "" "new1\nnew2\n" in 33 Alcotest.(check int) "2 additions" 2 (List.length lines); 34 List.iter 35 (fun line -> 36 Alcotest.(check bool) "all additions" true (line.kind = Addition)) 37 lines 38 39 let test_entirely_deleted_file () = 40 let open Ogit.Resolvers.Diff in 41 let lines = of_contents "old1\nold2\n" "" in 42 Alcotest.(check int) "2 deletions" 2 (List.length lines); 43 List.iter 44 (fun line -> 45 Alcotest.(check bool) "all deletions" true (line.kind = Deletion)) 46 lines 47 48 let test_trailing_newline_handling () = 49 let open Ogit.Resolvers.Diff in 50 let with_newline = of_contents "a\n" "a\n" in 51 let without_newline = of_contents "a" "a" in 52 Alcotest.(check int) "with newline: 1 line" 1 (List.length with_newline); 53 Alcotest.(check int) "without newline: 1 line" 1 (List.length without_newline); 54 Alcotest.(check string) "text matches" "a" (List.hd with_newline).text; 55 Alcotest.(check string) "text matches" "a" (List.hd without_newline).text 56 57 let test_no_trailing_newline_diff () = 58 let open Ogit.Resolvers.Diff in 59 let lines = of_contents "a\nb" "a\nc" in 60 Alcotest.(check int) "3 lines" 3 (List.length lines); 61 let kinds = List.map (fun l -> l.kind) lines in 62 Alcotest.(check bool) 63 "context+del+add" true 64 (kinds = [ Context; Deletion; Addition ]) 65 66 let test_hunks () = 67 let open Ogit.Resolvers.Diff in 68 let old_content = List.init 12 (fun i -> string_of_int (i + 1)) in 69 let new_content = 70 List.mapi (fun i l -> if i = 5 then "changed" else l) old_content 71 in 72 match 73 hunks 74 (of_contents 75 (String.concat "\n" old_content) 76 (String.concat "\n" new_content)) 77 with 78 | [ hunk ] -> 79 Alcotest.(check int) "old_start" 3 hunk.old_start; 80 Alcotest.(check int) "old_count" 7 hunk.old_count; 81 Alcotest.(check int) "new_start" 3 hunk.new_start; 82 Alcotest.(check int) "new_count" 7 hunk.new_count 83 | hunks -> Alcotest.failf "expected 1 hunk, got %d" (List.length hunks) 84 85 let test_multiple_hunks () = 86 let open Ogit.Resolvers.Diff in 87 let old_content = List.init 20 (fun i -> string_of_int (i + 1)) in 88 let new_content = 89 List.mapi (fun i l -> if i = 2 || i = 17 then "changed" else l) old_content 90 in 91 let result = 92 hunks 93 (of_contents 94 (String.concat "\n" old_content) 95 (String.concat "\n" new_content)) 96 in 97 Alcotest.(check int) "2 hunks" 2 (List.length result) 98 99 let test_large_file_fallback () = 100 let open Ogit.Resolvers.Diff in 101 (* Every line differs after trimming: 2000 edits exceed the 1024-difference 102 cap, so the diff degrades to wholesale replacement. *) 103 let old_content = String.concat "\n" (List.init 2001 string_of_int) in 104 let new_content = 105 String.concat "\n" (List.init 2001 (fun i -> string_of_int (i + 3000))) 106 in 107 let lines = of_contents old_content new_content in 108 let has_deletions = List.exists (fun l -> l.kind = Deletion) lines in 109 let has_additions = List.exists (fun l -> l.kind = Addition) lines in 110 Alcotest.(check bool) "has deletions" true has_deletions; 111 Alcotest.(check bool) "has additions" true has_additions; 112 (* No context lines in fallback mode *) 113 let has_context = List.exists (fun l -> l.kind = Context) lines in 114 Alcotest.(check bool) "no context in fallback" false has_context 115 116 (* Cost tracks the number of differences, not file size: two edits in a 117 3000-line file must produce an exact diff, which the old 118 quadratic-matrix implementation could not afford at this size. *) 119 let test_small_change_in_large_file () = 120 let open Ogit.Resolvers.Diff in 121 let numbered = List.init 3000 (fun i -> "line " ^ string_of_int (i + 1)) in 122 let changed = 123 List.mapi 124 (fun i line -> if i = 100 || i = 2900 then line ^ " changed" else line) 125 numbered 126 in 127 let lines = 128 of_contents 129 (String.concat "\n" numbered ^ "\n") 130 (String.concat "\n" changed ^ "\n") 131 in 132 let count kind = 133 List.length (List.filter (fun l -> l.kind = kind) lines) 134 in 135 Alcotest.(check int) "two deletions" 2 (count Deletion); 136 Alcotest.(check int) "two additions" 2 (count Addition); 137 Alcotest.(check int) "rest is context" 2998 (count Context); 138 (match List.rev lines with 139 | last :: _ -> 140 Alcotest.(check (option int)) "last old number" (Some 3000) 141 last.old_number; 142 Alcotest.(check (option int)) "last new number" (Some 3000) 143 last.new_number 144 | [] -> Alcotest.fail "no lines") 145 146 (* Whatever script the search picks, replaying it must reproduce both inputs: 147 the old file is the context and deleted lines in order, the new file the 148 context and added lines. *) 149 let test_reconstruction () = 150 let open Ogit.Resolvers.Diff in 151 let reconstruct_old lines = 152 List.filter_map 153 (fun l -> 154 match l.kind with Context | Deletion -> Some l.text | Addition -> None) 155 lines 156 in 157 let reconstruct_new lines = 158 List.filter_map 159 (fun l -> 160 match l.kind with Context | Addition -> Some l.text | Deletion -> None) 161 lines 162 in 163 let check name old_lines new_lines = 164 let content lines = 165 match lines with [] -> "" | _ -> String.concat "\n" lines ^ "\n" 166 in 167 let diff = of_contents (content old_lines) (content new_lines) in 168 Alcotest.(check (list string)) 169 (name ^ ": old reconstructed") 170 old_lines (reconstruct_old diff); 171 Alcotest.(check (list string)) 172 (name ^ ": new reconstructed") 173 new_lines (reconstruct_new diff) 174 in 175 check "replace middle" [ "a"; "b"; "c" ] [ "a"; "x"; "c" ]; 176 check "empty old" [] [ "a"; "b" ]; 177 check "empty new" [ "a"; "b" ] []; 178 check "moved block" [ "a"; "b"; "c"; "d" ] [ "c"; "d"; "a"; "b" ]; 179 check "interleaved" 180 [ "1"; "2"; "3"; "4"; "5"; "6" ] 181 [ "1"; "x"; "3"; "y"; "5"; "z" ]; 182 check "repeated lines" [ "a"; "a"; "b"; "a" ] [ "a"; "b"; "a"; "a" ]; 183 (* Past the difference cap the coarse fallback must still reconstruct. *) 184 check "beyond the cap" 185 (List.init 600 (fun i -> "old " ^ string_of_int i)) 186 (List.init 700 (fun i -> "new " ^ string_of_int i)) 187 188 let suite = 189 ( "diff", 190 [ 191 Alcotest.test_case "basic line diff" `Quick test_line_diff; 192 Alcotest.test_case "empty vs empty" `Quick test_empty_vs_empty; 193 Alcotest.test_case "identical content" `Quick test_identical_content; 194 Alcotest.test_case "entirely new file" `Quick test_entirely_new_file; 195 Alcotest.test_case "entirely deleted file" `Quick 196 test_entirely_deleted_file; 197 Alcotest.test_case "trailing newline" `Quick 198 test_trailing_newline_handling; 199 Alcotest.test_case "no trailing newline diff" `Quick 200 test_no_trailing_newline_diff; 201 Alcotest.test_case "single hunk" `Quick test_hunks; 202 Alcotest.test_case "multiple hunks" `Quick test_multiple_hunks; 203 Alcotest.test_case "large file fallback" `Quick test_large_file_fallback; 204 Alcotest.test_case "small change in large file" `Quick 205 test_small_change_in_large_file; 206 Alcotest.test_case "reconstruction" `Quick test_reconstruction; 207 ] ) 208