Blob


1 /* Produce a unidiff output from a diff_result. */
2 /*
3 * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
18 #include <errno.h>
19 #include <stdbool.h>
20 #include <stdint.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <assert.h>
26 #include <arraylist.h>
27 #include <diff_main.h>
28 #include <diff_output.h>
30 #include "diff_internal.h"
31 #include "diff_debug.h"
33 bool
34 diff_chunk_context_empty(const struct diff_chunk_context *cc)
35 {
36 return diff_range_empty(&cc->chunk);
37 }
39 int
40 diff_chunk_get_left_start(const struct diff_chunk *c,
41 const struct diff_result *r, int context_lines)
42 {
43 int left_start = diff_atom_root_idx(r->left, c->left_start);
44 return MAX(0, left_start - context_lines);
45 }
47 int
48 diff_chunk_get_left_end(const struct diff_chunk *c,
49 const struct diff_result *r, int context_lines)
50 {
51 int left_start = diff_chunk_get_left_start(c, r, 0);
52 return MIN(r->left->atoms.len,
53 left_start + c->left_count + context_lines);
54 }
56 int
57 diff_chunk_get_right_start(const struct diff_chunk *c,
58 const struct diff_result *r, int context_lines)
59 {
60 int right_start = diff_atom_root_idx(r->right, c->right_start);
61 return MAX(0, right_start - context_lines);
62 }
64 int
65 diff_chunk_get_right_end(const struct diff_chunk *c,
66 const struct diff_result *r, int context_lines)
67 {
68 int right_start = diff_chunk_get_right_start(c, r, 0);
69 return MIN(r->right->atoms.len,
70 right_start + c->right_count + context_lines);
71 }
73 struct diff_chunk *
74 diff_chunk_get(const struct diff_result *r, int chunk_idx)
75 {
76 return &r->chunks.head[chunk_idx];
77 }
79 int
80 diff_chunk_get_left_count(struct diff_chunk *c)
81 {
82 return c->left_count;
83 }
85 int
86 diff_chunk_get_right_count(struct diff_chunk *c)
87 {
88 return c->right_count;
89 }
91 void
92 diff_chunk_context_get(struct diff_chunk_context *cc, const struct diff_result *r,
93 int chunk_idx, int context_lines)
94 {
95 const struct diff_chunk *c = &r->chunks.head[chunk_idx];
96 int left_start = diff_chunk_get_left_start(c, r, context_lines);
97 int left_end = diff_chunk_get_left_end(c, r, context_lines);
98 int right_start = diff_chunk_get_right_start(c, r, context_lines);
99 int right_end = diff_chunk_get_right_end(c, r, context_lines);
101 *cc = (struct diff_chunk_context){
102 .chunk = {
103 .start = chunk_idx,
104 .end = chunk_idx + 1,
105 },
106 .left = {
107 .start = left_start,
108 .end = left_end,
109 },
110 .right = {
111 .start = right_start,
112 .end = right_end,
113 },
114 };
117 bool
118 diff_chunk_contexts_touch(const struct diff_chunk_context *cc,
119 const struct diff_chunk_context *other)
121 return diff_ranges_touch(&cc->chunk, &other->chunk)
122 || diff_ranges_touch(&cc->left, &other->left)
123 || diff_ranges_touch(&cc->right, &other->right);
126 void
127 diff_chunk_contexts_merge(struct diff_chunk_context *cc,
128 const struct diff_chunk_context *other)
130 diff_ranges_merge(&cc->chunk, &other->chunk);
131 diff_ranges_merge(&cc->left, &other->left);
132 diff_ranges_merge(&cc->right, &other->right);
135 void
136 diff_chunk_context_load_change(struct diff_chunk_context *cc,
137 int *nchunks_used,
138 struct diff_result *result,
139 int start_chunk_idx,
140 int context_lines)
142 int i;
143 int seen_minus = 0, seen_plus = 0;
145 if (nchunks_used)
146 *nchunks_used = 0;
148 for (i = start_chunk_idx; i < result->chunks.len; i++) {
149 struct diff_chunk *chunk = &result->chunks.head[i];
150 enum diff_chunk_type t = diff_chunk_type(chunk);
151 struct diff_chunk_context next;
153 if (t != CHUNK_MINUS && t != CHUNK_PLUS) {
154 if (nchunks_used)
155 (*nchunks_used)++;
156 if (seen_minus || seen_plus)
157 break;
158 else
159 continue;
160 } else if (t == CHUNK_MINUS)
161 seen_minus = 1;
162 else if (t == CHUNK_PLUS)
163 seen_plus = 1;
165 if (diff_chunk_context_empty(cc)) {
166 /* Note down the start point, any number of subsequent
167 * chunks may be joined up to this chunk by being
168 * directly adjacent. */
169 diff_chunk_context_get(cc, result, i, context_lines);
170 if (nchunks_used)
171 (*nchunks_used)++;
172 continue;
175 /* There already is a previous chunk noted down for being
176 * printed. Does it join up with this one? */
177 diff_chunk_context_get(&next, result, i, context_lines);
179 if (diff_chunk_contexts_touch(cc, &next)) {
180 /* This next context touches or overlaps the previous
181 * one, join. */
182 diff_chunk_contexts_merge(cc, &next);
183 if (nchunks_used)
184 (*nchunks_used)++;
185 continue;
186 } else
187 break;
191 struct diff_output_unidiff_state {
192 bool header_printed;
193 char prototype[DIFF_FUNCTION_CONTEXT_SIZE];
194 int last_prototype_idx;
195 };
197 struct diff_output_unidiff_state *
198 diff_output_unidiff_state_alloc(void)
200 struct diff_output_unidiff_state *state;
202 state = calloc(1, sizeof(struct diff_output_unidiff_state));
203 if (state != NULL)
204 diff_output_unidiff_state_reset(state);
205 return state;
208 void
209 diff_output_unidiff_state_reset(struct diff_output_unidiff_state *state)
211 state->header_printed = false;
212 memset(state->prototype, 0, sizeof(state->prototype));
213 state->last_prototype_idx = 0;
216 void
217 diff_output_unidiff_state_free(struct diff_output_unidiff_state *state)
219 free(state);
222 static int
223 output_unidiff_chunk(struct diff_output_info *outinfo, FILE *dest,
224 struct diff_output_unidiff_state *state,
225 const struct diff_input_info *info,
226 const struct diff_result *result,
227 bool print_header, bool show_function_prototypes,
228 const struct diff_chunk_context *cc)
230 int rc, left_start, left_len, right_start, right_len;
231 off_t outoff = 0, *offp;
233 if (diff_range_empty(&cc->left) && diff_range_empty(&cc->right))
234 return DIFF_RC_OK;
236 if (outinfo && outinfo->line_offsets.len > 0) {
237 unsigned int idx = outinfo->line_offsets.len - 1;
238 outoff = outinfo->line_offsets.head[idx];
241 if (print_header && !(state->header_printed)) {
242 rc = fprintf(dest, "--- %s\n",
243 diff_output_get_label_left(info));
244 if (rc < 0)
245 return errno;
246 if (outinfo) {
247 ARRAYLIST_ADD(offp, outinfo->line_offsets);
248 if (offp == NULL)
249 return ENOMEM;
250 outoff += rc;
251 *offp = outoff;
254 rc = fprintf(dest, "+++ %s\n",
255 diff_output_get_label_right(info));
256 if (rc < 0)
257 return errno;
258 if (outinfo) {
259 ARRAYLIST_ADD(offp, outinfo->line_offsets);
260 if (offp == NULL)
261 return ENOMEM;
262 outoff += rc;
263 *offp = outoff;
266 state->header_printed = true;
269 left_len = cc->left.end - cc->left.start;
270 if (result->left->atoms.len == 0)
271 left_start = 0;
272 else if (left_len == 0 && cc->left.start > 0)
273 left_start = cc->left.start;
274 else
275 left_start = cc->left.start + 1;
277 right_len = cc->right.end - cc->right.start;
278 if (result->right->atoms.len == 0)
279 right_start = 0;
280 else if (right_len == 0 && cc->right.start > 0)
281 right_start = cc->right.start;
282 else
283 right_start = cc->right.start + 1;
285 if (show_function_prototypes) {
286 rc = diff_output_match_function_prototype(state->prototype,
287 sizeof(state->prototype), &state->last_prototype_idx,
288 result, cc);
289 if (rc)
290 return rc;
293 if (left_len == 1 && right_len == 1) {
294 rc = fprintf(dest, "@@ -%d +%d @@%s%s\n",
295 left_start, right_start,
296 state->prototype[0] ? " " : "",
297 state->prototype[0] ? state->prototype : "");
298 } else if (left_len == 1 && right_len != 1) {
299 rc = fprintf(dest, "@@ -%d +%d,%d @@%s%s\n",
300 left_start, right_start, right_len,
301 state->prototype[0] ? " " : "",
302 state->prototype[0] ? state->prototype : "");
303 } else if (left_len != 1 && right_len == 1) {
304 rc = fprintf(dest, "@@ -%d,%d +%d @@%s%s\n",
305 left_start, left_len, right_start,
306 state->prototype[0] ? " " : "",
307 state->prototype[0] ? state->prototype : "");
308 } else {
309 rc = fprintf(dest, "@@ -%d,%d +%d,%d @@%s%s\n",
310 left_start, left_len, right_start, right_len,
311 state->prototype[0] ? " " : "",
312 state->prototype[0] ? state->prototype : "");
314 if (rc < 0)
315 return errno;
316 if (outinfo) {
317 ARRAYLIST_ADD(offp, outinfo->line_offsets);
318 if (offp == NULL)
319 return ENOMEM;
320 outoff += rc;
321 *offp = outoff;
325 /* Got the absolute line numbers where to start printing, and the index
326 * of the interesting (non-context) chunk.
327 * To print context lines above the interesting chunk, nipping on the
328 * previous chunk index may be necessary.
329 * It is guaranteed to be only context lines where left == right, so it
330 * suffices to look on the left. */
331 const struct diff_chunk *first_chunk;
332 int chunk_start_line;
333 first_chunk = &result->chunks.head[cc->chunk.start];
334 chunk_start_line = diff_atom_root_idx(result->left,
335 first_chunk->left_start);
336 if (cc->left.start < chunk_start_line) {
337 rc = diff_output_lines(outinfo, dest, " ",
338 &result->left->atoms.head[cc->left.start],
339 chunk_start_line - cc->left.start);
340 if (rc)
341 return rc;
344 /* Now write out all the joined chunks and contexts between them */
345 int c_idx;
346 for (c_idx = cc->chunk.start; c_idx < cc->chunk.end; c_idx++) {
347 const struct diff_chunk *c = &result->chunks.head[c_idx];
349 if (c->left_count && c->right_count)
350 rc = diff_output_lines(outinfo, dest,
351 c->solved ? " " : "?",
352 c->left_start, c->left_count);
353 else if (c->left_count && !c->right_count)
354 rc = diff_output_lines(outinfo, dest,
355 c->solved ? "-" : "?",
356 c->left_start, c->left_count);
357 else if (c->right_count && !c->left_count)
358 rc = diff_output_lines(outinfo, dest,
359 c->solved ? "+" : "?",
360 c->right_start, c->right_count);
361 if (rc)
362 return rc;
364 if (cc->chunk.end == result->chunks.len) {
365 rc = diff_output_trailing_newline_msg(outinfo, dest, c);
366 if (rc != DIFF_RC_OK)
367 return rc;
371 /* Trailing context? */
372 const struct diff_chunk *last_chunk;
373 int chunk_end_line;
374 last_chunk = &result->chunks.head[cc->chunk.end - 1];
375 chunk_end_line = diff_atom_root_idx(result->left,
376 last_chunk->left_start
377 + last_chunk->left_count);
378 if (cc->left.end > chunk_end_line) {
379 rc = diff_output_lines(outinfo, dest, " ",
380 &result->left->atoms.head[chunk_end_line],
381 cc->left.end - chunk_end_line);
382 if (rc)
383 return rc;
386 return DIFF_RC_OK;
389 int
390 diff_output_unidiff_chunk(struct diff_output_info **output_info, FILE *dest,
391 struct diff_output_unidiff_state *state,
392 const struct diff_input_info *info,
393 const struct diff_result *result,
394 const struct diff_chunk_context *cc)
396 struct diff_output_info *outinfo = NULL;
397 int flags = (result->left->root->diff_flags |
398 result->right->root->diff_flags);
399 bool show_function_prototypes = (flags & DIFF_FLAG_SHOW_PROTOTYPES);
401 if (output_info) {
402 *output_info = diff_output_info_alloc();
403 if (*output_info == NULL)
404 return ENOMEM;
405 outinfo = *output_info;
408 return output_unidiff_chunk(outinfo, dest, state, info,
409 result, false, show_function_prototypes, cc);
412 int
413 diff_output_unidiff(struct diff_output_info **output_info,
414 FILE *dest, const struct diff_input_info *info,
415 const struct diff_result *result,
416 unsigned int context_lines)
418 struct diff_output_unidiff_state *state;
419 struct diff_chunk_context cc = {};
420 struct diff_output_info *outinfo = NULL;
421 int atomizer_flags = (result->left->atomizer_flags|
422 result->right->atomizer_flags);
423 int flags = (result->left->root->diff_flags |
424 result->right->root->diff_flags);
425 bool show_function_prototypes = (flags & DIFF_FLAG_SHOW_PROTOTYPES);
426 bool force_text = (flags & DIFF_FLAG_FORCE_TEXT_DATA);
427 bool have_binary = (atomizer_flags & DIFF_ATOMIZER_FOUND_BINARY_DATA);
428 off_t outoff = 0, *offp;
429 int rc, i;
431 if (!result)
432 return EINVAL;
433 if (result->rc != DIFF_RC_OK)
434 return result->rc;
436 if (output_info) {
437 *output_info = diff_output_info_alloc();
438 if (*output_info == NULL)
439 return ENOMEM;
440 outinfo = *output_info;
443 if (have_binary && !force_text) {
444 for (i = 0; i < result->chunks.len; i++) {
445 struct diff_chunk *c = &result->chunks.head[i];
446 enum diff_chunk_type t = diff_chunk_type(c);
448 if (t != CHUNK_MINUS && t != CHUNK_PLUS)
449 continue;
451 if (outinfo && outinfo->line_offsets.len > 0) {
452 unsigned int idx =
453 outinfo->line_offsets.len - 1;
454 outoff = outinfo->line_offsets.head[idx];
457 rc = fprintf(dest, "Binary files %s and %s differ\n",
458 diff_output_get_label_left(info),
459 diff_output_get_label_right(info));
460 if (outinfo) {
461 ARRAYLIST_ADD(offp, outinfo->line_offsets);
462 if (offp == NULL)
463 return ENOMEM;
464 outoff += rc;
465 *offp = outoff;
468 break;
471 return DIFF_RC_OK;
474 state = diff_output_unidiff_state_alloc();
475 if (state == NULL) {
476 if (output_info) {
477 diff_output_info_free(*output_info);
478 *output_info = NULL;
480 return ENOMEM;
483 #if DEBUG
484 unsigned int check_left_pos, check_right_pos;
485 check_left_pos = 0;
486 check_right_pos = 0;
487 for (i = 0; i < result->chunks.len; i++) {
488 struct diff_chunk *c = &result->chunks.head[i];
489 enum diff_chunk_type t = diff_chunk_type(c);
491 debug("[%d] %s lines L%d R%d @L %d @R %d\n",
492 i, (t == CHUNK_MINUS ? "minus" :
493 (t == CHUNK_PLUS ? "plus" :
494 (t == CHUNK_SAME ? "same" : "?"))),
495 c->left_count,
496 c->right_count,
497 c->left_start ? diff_atom_root_idx(result->left, c->left_start) : -1,
498 c->right_start ? diff_atom_root_idx(result->right, c->right_start) : -1);
499 assert(check_left_pos == diff_atom_root_idx(result->left, c->left_start));
500 assert(check_right_pos == diff_atom_root_idx(result->right, c->right_start));
501 check_left_pos += c->left_count;
502 check_right_pos += c->right_count;
505 assert(check_left_pos == result->left->atoms.len);
506 assert(check_right_pos == result->right->atoms.len);
507 #endif
509 for (i = 0; i < result->chunks.len; i++) {
510 struct diff_chunk *c = &result->chunks.head[i];
511 enum diff_chunk_type t = diff_chunk_type(c);
512 struct diff_chunk_context next;
514 if (t != CHUNK_MINUS && t != CHUNK_PLUS)
515 continue;
517 if (diff_chunk_context_empty(&cc)) {
518 /* These are the first lines being printed.
519 * Note down the start point, any number of subsequent
520 * chunks may be joined up to this unidiff chunk by
521 * context lines or by being directly adjacent. */
522 diff_chunk_context_get(&cc, result, i, context_lines);
523 debug("new chunk to be printed:"
524 " chunk %d-%d left %d-%d right %d-%d\n",
525 cc.chunk.start, cc.chunk.end,
526 cc.left.start, cc.left.end,
527 cc.right.start, cc.right.end);
528 continue;
531 /* There already is a previous chunk noted down for being
532 * printed. Does it join up with this one? */
533 diff_chunk_context_get(&next, result, i, context_lines);
534 debug("new chunk to be printed:"
535 " chunk %d-%d left %d-%d right %d-%d\n",
536 next.chunk.start, next.chunk.end,
537 next.left.start, next.left.end,
538 next.right.start, next.right.end);
540 if (diff_chunk_contexts_touch(&cc, &next)) {
541 /* This next context touches or overlaps the previous
542 * one, join. */
543 diff_chunk_contexts_merge(&cc, &next);
544 debug("new chunk to be printed touches previous chunk,"
545 " now: left %d-%d right %d-%d\n",
546 cc.left.start, cc.left.end,
547 cc.right.start, cc.right.end);
548 continue;
551 /* No touching, so the previous context is complete with a gap
552 * between it and this next one. Print the previous one and
553 * start fresh here. */
554 debug("new chunk to be printed does not touch previous chunk;"
555 " print left %d-%d right %d-%d\n",
556 cc.left.start, cc.left.end, cc.right.start, cc.right.end);
557 output_unidiff_chunk(outinfo, dest, state, info, result,
558 true, show_function_prototypes, &cc);
559 cc = next;
560 debug("new unprinted chunk is left %d-%d right %d-%d\n",
561 cc.left.start, cc.left.end, cc.right.start, cc.right.end);
564 if (!diff_chunk_context_empty(&cc))
565 output_unidiff_chunk(outinfo, dest, state, info, result,
566 true, show_function_prototypes, &cc);
567 diff_output_unidiff_state_free(state);
568 return DIFF_RC_OK;