-rw-r--r-- | ui-ssdiff.c | 141 |
1 files changed, 118 insertions, 23 deletions
diff --git a/ui-ssdiff.c b/ui-ssdiff.c index 5673642..408e620 100644 --- a/ui-ssdiff.c +++ b/ui-ssdiff.c | |||
@@ -10,16 +10,62 @@ struct deferred_lines { | |||
10 | int line_no; | 10 | int line_no; |
11 | char *line; | 11 | char *line; |
12 | struct deferred_lines *next; | 12 | struct deferred_lines *next; |
13 | }; | 13 | }; |
14 | 14 | ||
15 | static struct deferred_lines *deferred_old, *deferred_old_last; | 15 | static struct deferred_lines *deferred_old, *deferred_old_last; |
16 | static struct deferred_lines *deferred_new, *deferred_new_last; | 16 | 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) |
19 | { | 65 | { |
20 | char *buf1, *buf2; | 66 | char *buf1, *buf2; |
21 | int len; | 67 | int len; |
22 | 68 | ||
23 | buf1 = strchr(line, type); | 69 | buf1 = strchr(line, type); |
24 | if (buf1 == NULL) | 70 | if (buf1 == NULL) |
25 | return 0; | 71 | return 0; |
@@ -68,16 +114,27 @@ static char *replace_tabs(char *line) | |||
68 | strncat(result, spaces, 8 - (strlen(result) % 8)); | 114 | strncat(result, spaces, 8 - (strlen(result) % 8)); |
69 | strncat(result, prev_buf, cur_buf - prev_buf); | 115 | strncat(result, prev_buf, cur_buf - prev_buf); |
70 | } | 116 | } |
71 | prev_buf = cur_buf + 1; | 117 | prev_buf = cur_buf + 1; |
72 | } | 118 | } |
73 | return result; | 119 | return result; |
74 | } | 120 | } |
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) |
77 | { | 134 | { |
78 | struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines)); | 135 | struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines)); |
79 | item->line = xstrdup(line); | 136 | item->line = xstrdup(line); |
80 | item->line_no = line_no; | 137 | item->line_no = line_no; |
81 | item->next = NULL; | 138 | item->next = NULL; |
82 | if (deferred_old) { | 139 | if (deferred_old) { |
83 | deferred_old_last->next = item; | 140 | deferred_old_last->next = item; |
@@ -96,99 +153,141 @@ static void deferred_new_add(char *line, int line_no) | |||
96 | if (deferred_new) { | 153 | if (deferred_new) { |
97 | deferred_new_last->next = item; | 154 | deferred_new_last->next = item; |
98 | deferred_new_last = item; | 155 | deferred_new_last = item; |
99 | } else { | 156 | } else { |
100 | deferred_new = deferred_new_last = item; | 157 | deferred_new = deferred_new_last = item; |
101 | } | 158 | } |
102 | } | 159 | } |
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) | ||
106 | { | 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) | ||
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>"); |
108 | if (old_line_no > 0) | 201 | if (old_line_no > 0) |
109 | htmlf("<td class='lineno'>%d</td><td class='%s'>", | 202 | htmlf("<td class='lineno'>%d</td><td class='%s'>", |
110 | old_line_no, class); | 203 | old_line_no, class); |
111 | else if (old_line) | 204 | else if (old_line) |
112 | htmlf("<td class='lineno'></td><td class='%s'>", class); | 205 | htmlf("<td class='lineno'></td><td class='%s'>", class); |
113 | else | 206 | else |
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) |
210 | print_part_with_lcs("del", old_line, lcs); | ||
211 | else | ||
118 | html_txt(old_line); | 212 | html_txt(old_line); |
119 | free(old_line); | ||
120 | } | 213 | } |
121 | 214 | ||
122 | html("</td>"); | 215 | html("</td>"); |
123 | |||
124 | if (new_line_no > 0) | 216 | if (new_line_no > 0) |
125 | htmlf("<td class='lineno'>%d</td><td class='%s'>", | 217 | htmlf("<td class='lineno'>%d</td><td class='%s'>", |
126 | new_line_no, class); | 218 | new_line_no, class); |
127 | else if (new_line) | 219 | else if (new_line) |
128 | htmlf("<td class='lineno'></td><td class='%s'>", class); | 220 | htmlf("<td class='lineno'></td><td class='%s'>", class); |
129 | else | 221 | else |
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) |
225 | print_part_with_lcs("add", new_line, lcs); | ||
226 | else | ||
134 | html_txt(new_line); | 227 | html_txt(new_line); |
135 | free(new_line); | ||
136 | } | 228 | } |
137 | 229 | ||
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 | } |
140 | 238 | ||
141 | static void print_deferred_old_lines() | 239 | static void print_deferred_old_lines() |
142 | { | 240 | { |
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; |
146 | while (iter_old) { | 243 | while (iter_old) { |
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; |
150 | free(iter_old); | 247 | free(iter_old); |
151 | iter_old = tmp; | 248 | iter_old = tmp; |
152 | } | 249 | } |
153 | } | 250 | } |
154 | 251 | ||
155 | static void print_deferred_new_lines() | 252 | static void print_deferred_new_lines() |
156 | { | 253 | { |
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; |
164 | free(iter_new); | 260 | free(iter_new); |
165 | iter_new = tmp; | 261 | iter_new = tmp; |
166 | } | 262 | } |
167 | } | 263 | } |
168 | 264 | ||
169 | static void print_deferred_changed_lines() | 265 | static void print_deferred_changed_lines() |
170 | { | 266 | { |
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 | ||
173 | iter_old = deferred_old; | 272 | iter_old = deferred_old; |
174 | iter_new = deferred_new; | 273 | iter_new = deferred_new; |
175 | while (iter_old || iter_new) { | 274 | while (iter_old || iter_new) { |
176 | if (iter_old && iter_new) | 275 | if (iter_old && iter_new) |
177 | print_ssdiff_line("changed", iter_old->line_no, | 276 | print_ssdiff_line("changed", iter_old->line_no, |
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) { |
188 | tmp = iter_old->next; | 287 | tmp = iter_old->next; |
189 | free(iter_old); | 288 | free(iter_old); |
190 | iter_old = tmp; | 289 | iter_old = tmp; |
191 | } | 290 | } |
192 | 291 | ||
193 | if (iter_new) { | 292 | if (iter_new) { |
194 | tmp = iter_new->next; | 293 | tmp = iter_new->next; |
@@ -197,47 +296,43 @@ static void print_deferred_changed_lines() | |||
197 | } | 296 | } |
198 | } | 297 | } |
199 | } | 298 | } |
200 | 299 | ||
201 | void cgit_ssdiff_print_deferred_lines() | 300 | void cgit_ssdiff_print_deferred_lines() |
202 | { | 301 | { |
203 | if (!deferred_old && !deferred_new) | 302 | if (!deferred_old && !deferred_new) |
204 | return; | 303 | return; |
205 | |||
206 | if (deferred_old && !deferred_new) | 304 | if (deferred_old && !deferred_new) |
207 | print_deferred_old_lines(); | 305 | print_deferred_old_lines(); |
208 | else if (!deferred_old && deferred_new) | 306 | else if (!deferred_old && deferred_new) |
209 | print_deferred_new_lines(); | 307 | print_deferred_new_lines(); |
210 | else | 308 | else |
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; |
214 | deferred_new = deferred_new_last = NULL; | 311 | deferred_new = deferred_new_last = NULL; |
215 | } | 312 | } |
216 | 313 | ||
217 | /* | 314 | /* |
218 | * print a single line returned from xdiff | 315 | * print a single line returned from xdiff |
219 | */ | 316 | */ |
220 | void cgit_ssdiff_line_cb(char *line, int len) | 317 | void cgit_ssdiff_line_cb(char *line, int len) |
221 | { | 318 | { |
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] == '@') { |
227 | current_old_line = line_from_hunk(line, '-'); | 322 | current_old_line = line_from_hunk(line, '-'); |
228 | current_new_line = line_from_hunk(line, '+'); | 323 | current_new_line = line_from_hunk(line, '+'); |
229 | } | 324 | } |
230 | 325 | ||
231 | if (line[0] == ' ') { | 326 | if (line[0] == ' ') { |
232 | if (deferred_old || deferred_new) | 327 | if (deferred_old || deferred_new) |
233 | cgit_ssdiff_print_deferred_lines(); | 328 | cgit_ssdiff_print_deferred_lines(); |
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; |
237 | current_new_line += 1; | 332 | current_new_line += 1; |
238 | } else if (line[0] == '+') { | 333 | } else if (line[0] == '+') { |
239 | deferred_new_add(line, current_new_line); | 334 | deferred_new_add(line, current_new_line); |
240 | current_new_line += 1; | 335 | current_new_line += 1; |
241 | } else if (line[0] == '-') { | 336 | } else if (line[0] == '-') { |
242 | deferred_old_add(line, current_old_line); | 337 | deferred_old_add(line, current_old_line); |
243 | current_old_line += 1; | 338 | current_old_line += 1; |