-rw-r--r-- | ui-ssdiff.c | 145 |
1 files changed, 120 insertions, 25 deletions
diff --git a/ui-ssdiff.c b/ui-ssdiff.c index 5673642..408e620 100644 --- a/ui-ssdiff.c +++ b/ui-ssdiff.c | |||
@@ -17,2 +17,48 @@ static struct deferred_lines *deferred_new, *deferred_new_last; | |||
17 | 17 | ||
18 | static char *longest_common_subsequence(char *A, char *B) | ||
19 | { | ||
20 | int i, j, ri; | ||
21 | int m = strlen(A); | ||
22 | int n = strlen(B); | ||
23 | int L[m + 1][n + 1]; | ||
24 | int tmp1, tmp2; | ||
25 | int lcs_length; | ||
26 | char *result; | ||
27 | |||
28 | for (i = m; i >= 0; i--) { | ||
29 | for (j = n; j >= 0; j--) { | ||
30 | if (A[i] == '\0' || B[j] == '\0') { | ||
31 | L[i][j] = 0; | ||
32 | } else if (A[i] == B[j]) { | ||
33 | L[i][j] = 1 + L[i + 1][j + 1]; | ||
34 | } else { | ||
35 | tmp1 = L[i + 1][j]; | ||
36 | tmp2 = L[i][j + 1]; | ||
37 | L[i][j] = (tmp1 > tmp2 ? tmp1 : tmp2); | ||
38 | } | ||
39 | } | ||
40 | } | ||
41 | |||
42 | lcs_length = L[0][0]; | ||
43 | result = xmalloc(lcs_length + 2); | ||
44 | memset(result, 0, sizeof(*result) * (lcs_length + 2)); | ||
45 | |||
46 | ri = 0; | ||
47 | i = 0; | ||
48 | j = 0; | ||
49 | while (i < m && j < n) { | ||
50 | if (A[i] == B[j]) { | ||
51 | result[ri] = A[i]; | ||
52 | ri += 1; | ||
53 | i += 1; | ||
54 | j += 1; | ||
55 | } else if (L[i + 1][j] >= L[i][j + 1]) { | ||
56 | i += 1; | ||
57 | } else { | ||
58 | j += 1; | ||
59 | } | ||
60 | } | ||
61 | return result; | ||
62 | } | ||
63 | |||
18 | static int line_from_hunk(char *line, char type) | 64 | static int line_from_hunk(char *line, char type) |
@@ -75,2 +121,13 @@ static char *replace_tabs(char *line) | |||
75 | 121 | ||
122 | static int calc_deferred_lines(struct deferred_lines *start) | ||
123 | { | ||
124 | struct deferred_lines *item = start; | ||
125 | int result = 0; | ||
126 | while (item) { | ||
127 | result += 1; | ||
128 | item = item->next; | ||
129 | } | ||
130 | return result; | ||
131 | } | ||
132 | |||
76 | static void deferred_old_add(char *line, int line_no) | 133 | static void deferred_old_add(char *line, int line_no) |
@@ -103,5 +160,41 @@ static void deferred_new_add(char *line, int line_no) | |||
103 | 160 | ||
104 | static void print_ssdiff_line(char *class, int old_line_no, char *old_line, | 161 | static void print_part_with_lcs(char *class, char *line, char *lcs) |
105 | int new_line_no, char *new_line) | 162 | { |
163 | int line_len = strlen(line); | ||
164 | int i, j; | ||
165 | char c[2] = " "; | ||
166 | int same = 1; | ||
167 | |||
168 | j = 0; | ||
169 | for (i = 0; i < line_len; i++) { | ||
170 | c[0] = line[i]; | ||
171 | if (same) { | ||
172 | if (line[i] == lcs[j]) | ||
173 | j += 1; | ||
174 | else { | ||
175 | same = 0; | ||
176 | htmlf("<span class='%s'>", class); | ||
177 | } | ||
178 | } else if (line[i] == lcs[j]) { | ||
179 | same = 1; | ||
180 | htmlf("</span>"); | ||
181 | j += 1; | ||
182 | } | ||
183 | html_txt(c); | ||
184 | } | ||
185 | } | ||
186 | |||
187 | static void print_ssdiff_line(char *class, | ||
188 | int old_line_no, | ||
189 | char *old_line, | ||
190 | int new_line_no, | ||
191 | char *new_line, int individual_chars) | ||
106 | { | 192 | { |
193 | char *lcs = NULL; | ||
194 | if (old_line) | ||
195 | old_line = replace_tabs(old_line + 1); | ||
196 | if (new_line) | ||
197 | new_line = replace_tabs(new_line + 1); | ||
198 | if (individual_chars && old_line && new_line) | ||
199 | lcs = longest_common_subsequence(old_line, new_line); | ||
107 | html("<tr>"); | 200 | html("<tr>"); |
@@ -114,7 +207,7 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line, | |||
114 | htmlf("<td class='lineno'></td><td class='%s_dark'>", class); | 207 | htmlf("<td class='lineno'></td><td class='%s_dark'>", class); |
115 | |||
116 | if (old_line) { | 208 | if (old_line) { |
117 | old_line = replace_tabs(old_line + 1); | 209 | if (lcs) |
118 | html_txt(old_line); | 210 | print_part_with_lcs("del", old_line, lcs); |
119 | free(old_line); | 211 | else |
212 | html_txt(old_line); | ||
120 | } | 213 | } |
@@ -122,3 +215,2 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line, | |||
122 | html("</td>"); | 215 | html("</td>"); |
123 | |||
124 | if (new_line_no > 0) | 216 | if (new_line_no > 0) |
@@ -130,7 +222,7 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line, | |||
130 | htmlf("<td class='lineno'></td><td class='%s_dark'>", class); | 222 | htmlf("<td class='lineno'></td><td class='%s_dark'>", class); |
131 | |||
132 | if (new_line) { | 223 | if (new_line) { |
133 | new_line = replace_tabs(new_line + 1); | 224 | if (lcs) |
134 | html_txt(new_line); | 225 | print_part_with_lcs("add", new_line, lcs); |
135 | free(new_line); | 226 | else |
227 | html_txt(new_line); | ||
136 | } | 228 | } |
@@ -138,2 +230,8 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line, | |||
138 | html("</td></tr>"); | 230 | html("</td></tr>"); |
231 | if (lcs) | ||
232 | free(lcs); | ||
233 | if (new_line) | ||
234 | free(new_line); | ||
235 | if (old_line) | ||
236 | free(old_line); | ||
139 | } | 237 | } |
@@ -143,3 +241,2 @@ static void print_deferred_old_lines() | |||
143 | struct deferred_lines *iter_old, *tmp; | 241 | struct deferred_lines *iter_old, *tmp; |
144 | |||
145 | iter_old = deferred_old; | 242 | iter_old = deferred_old; |
@@ -147,3 +244,3 @@ static void print_deferred_old_lines() | |||
147 | print_ssdiff_line("del", iter_old->line_no, | 244 | print_ssdiff_line("del", iter_old->line_no, |
148 | iter_old->line, -1, NULL); | 245 | iter_old->line, -1, NULL, 0); |
149 | tmp = iter_old->next; | 246 | tmp = iter_old->next; |
@@ -157,7 +254,6 @@ static void print_deferred_new_lines() | |||
157 | struct deferred_lines *iter_new, *tmp; | 254 | struct deferred_lines *iter_new, *tmp; |
158 | |||
159 | iter_new = deferred_new; | 255 | iter_new = deferred_new; |
160 | while (iter_new) { | 256 | while (iter_new) { |
161 | print_ssdiff_line("add", -1, NULL, iter_new->line_no, | 257 | print_ssdiff_line("add", -1, NULL, |
162 | iter_new->line); | 258 | iter_new->line_no, iter_new->line, 0); |
163 | tmp = iter_new->next; | 259 | tmp = iter_new->next; |
@@ -171,2 +267,5 @@ static void print_deferred_changed_lines() | |||
171 | struct deferred_lines *iter_old, *iter_new, *tmp; | 267 | struct deferred_lines *iter_old, *iter_new, *tmp; |
268 | int n_old_lines = calc_deferred_lines(deferred_old); | ||
269 | int n_new_lines = calc_deferred_lines(deferred_new); | ||
270 | int individual_chars = (n_old_lines == n_new_lines ? 1 : 0); | ||
172 | 271 | ||
@@ -178,10 +277,10 @@ static void print_deferred_changed_lines() | |||
178 | iter_old->line, | 277 | iter_old->line, |
179 | iter_new->line_no, iter_new->line); | 278 | iter_new->line_no, iter_new->line, |
279 | individual_chars); | ||
180 | else if (iter_old) | 280 | else if (iter_old) |
181 | print_ssdiff_line("changed", iter_old->line_no, | 281 | print_ssdiff_line("changed", iter_old->line_no, |
182 | iter_old->line, -1, NULL); | 282 | iter_old->line, -1, NULL, 0); |
183 | else if (iter_new) | 283 | else if (iter_new) |
184 | print_ssdiff_line("changed", -1, NULL, | 284 | print_ssdiff_line("changed", -1, NULL, |
185 | iter_new->line_no, iter_new->line); | 285 | iter_new->line_no, iter_new->line, 0); |
186 | |||
187 | if (iter_old) { | 286 | if (iter_old) { |
@@ -204,3 +303,2 @@ void cgit_ssdiff_print_deferred_lines() | |||
204 | return; | 303 | return; |
205 | |||
206 | if (deferred_old && !deferred_new) | 304 | if (deferred_old && !deferred_new) |
@@ -211,3 +309,2 @@ void cgit_ssdiff_print_deferred_lines() | |||
211 | print_deferred_changed_lines(); | 309 | print_deferred_changed_lines(); |
212 | |||
213 | deferred_old = deferred_old_last = NULL; | 310 | deferred_old = deferred_old_last = NULL; |
@@ -222,5 +319,3 @@ void cgit_ssdiff_line_cb(char *line, int len) | |||
222 | char c = line[len - 1]; | 319 | char c = line[len - 1]; |
223 | |||
224 | line[len - 1] = '\0'; | 320 | line[len - 1] = '\0'; |
225 | |||
226 | if (line[0] == '@') { | 321 | if (line[0] == '@') { |
@@ -234,3 +329,3 @@ void cgit_ssdiff_line_cb(char *line, int len) | |||
234 | print_ssdiff_line("ctx", current_old_line, line, | 329 | print_ssdiff_line("ctx", current_old_line, line, |
235 | current_new_line, line); | 330 | current_new_line, line, 0); |
236 | current_old_line += 1; | 331 | current_old_line += 1; |