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  */
17 
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>
25 
26 #include <arraylist.h>
27 #include <diff_main.h>
28 #include <diff_output.h>
29 
30 #include "diff_internal.h"
31 #include "diff_debug.h"
32 
33 bool
34 diff_chunk_context_empty(const struct diff_chunk_context *cc)
35 {
36 	return diff_range_empty(&cc->chunk);
37 }
38 
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 }
46 
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 }
55 
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 }
63 
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 }
72 
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 }
78 
79 int
80 diff_chunk_get_left_count(struct diff_chunk *c)
81 {
82 	return c->left_count;
83 }
84 
85 int
86 diff_chunk_get_right_count(struct diff_chunk *c)
87 {
88 	return c->right_count;
89 }
90 
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);
100 
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 	};
115 }
116 
117 bool
118 diff_chunk_contexts_touch(const struct diff_chunk_context *cc,
119 			  const struct diff_chunk_context *other)
120 {
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);
124 }
125 
126 void
127 diff_chunk_contexts_merge(struct diff_chunk_context *cc,
128 			  const struct diff_chunk_context *other)
129 {
130 	diff_ranges_merge(&cc->chunk, &other->chunk);
131 	diff_ranges_merge(&cc->left, &other->left);
132 	diff_ranges_merge(&cc->right, &other->right);
133 }
134 
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)
141 {
142 	int i;
143 	int seen_minus = 0, seen_plus = 0;
144 
145 	if (nchunks_used)
146 		*nchunks_used = 0;
147 
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;
152 
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;
164 
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;
173 		}
174 
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);
178 
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;
188 	}
189 }
190 
191 struct diff_output_unidiff_state {
192 	bool header_printed;
193 	char prototype[DIFF_FUNCTION_CONTEXT_SIZE];
194 	int last_prototype_idx;
195 };
196 
197 struct diff_output_unidiff_state *
198 diff_output_unidiff_state_alloc(void)
199 {
200 	struct diff_output_unidiff_state *state;
201 
202 	state = calloc(1, sizeof(struct diff_output_unidiff_state));
203 	if (state != NULL)
204 		diff_output_unidiff_state_reset(state);
205 	return state;
206 }
207 
208 void
209 diff_output_unidiff_state_reset(struct diff_output_unidiff_state *state)
210 {
211 	state->header_printed = false;
212 	memset(state->prototype, 0, sizeof(state->prototype));
213 	state->last_prototype_idx = 0;
214 }
215 
216 void
217 diff_output_unidiff_state_free(struct diff_output_unidiff_state *state)
218 {
219 	free(state);
220 }
221 
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)
229 {
230 	int rc, left_start, left_len, right_start, right_len;
231 	off_t outoff = 0, *offp;
232 
233 	if (diff_range_empty(&cc->left) && diff_range_empty(&cc->right))
234 		return DIFF_RC_OK;
235 
236 	if (outinfo && outinfo->line_offsets.len > 0) {
237 		unsigned int idx = outinfo->line_offsets.len - 1;
238 		outoff = outinfo->line_offsets.head[idx];
239 	}
240 
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;
252 
253 		}
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;
264 
265 		}
266 		state->header_printed = true;
267 	}
268 
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;
276 
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;
284 
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;
291 	}
292 
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 : "");
313 	}
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;
322 
323 	}
324 
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;
342 	}
343 
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];
348 
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;
363 
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;
368 		}
369 	}
370 
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;
384 	}
385 
386 	return DIFF_RC_OK;
387 }
388 
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)
395 {
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);
400 
401 	if (output_info) {
402 		*output_info = diff_output_info_alloc();
403 		if (*output_info == NULL)
404 			return ENOMEM;
405 		outinfo = *output_info;
406 	}
407 
408 	return output_unidiff_chunk(outinfo, dest, state, info,
409 	    result, false, show_function_prototypes, cc);
410 }
411 
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)
417 {
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 	int i;
429 
430 	if (!result)
431 		return EINVAL;
432 	if (result->rc != DIFF_RC_OK)
433 		return result->rc;
434 
435 	if (output_info) {
436 		*output_info = diff_output_info_alloc();
437 		if (*output_info == NULL)
438 			return ENOMEM;
439 		outinfo = *output_info;
440 	}
441 
442 	if (have_binary && !force_text) {
443 		for (i = 0; i < result->chunks.len; i++) {
444 			struct diff_chunk *c = &result->chunks.head[i];
445 			enum diff_chunk_type t = diff_chunk_type(c);
446 
447 			if (t != CHUNK_MINUS && t != CHUNK_PLUS)
448 				continue;
449 
450 			fprintf(dest, "Binary files %s and %s differ\n",
451 			    diff_output_get_label_left(info),
452 			    diff_output_get_label_right(info));
453 			break;
454 		}
455 
456 		return DIFF_RC_OK;
457 	}
458 
459 	state = diff_output_unidiff_state_alloc();
460 	if (state == NULL) {
461 		if (output_info) {
462 			diff_output_info_free(*output_info);
463 			*output_info = NULL;
464 		}
465 		return ENOMEM;
466 	}
467 
468 #if DEBUG
469 	unsigned int check_left_pos, check_right_pos;
470 	check_left_pos = 0;
471 	check_right_pos = 0;
472 	for (i = 0; i < result->chunks.len; i++) {
473 		struct diff_chunk *c = &result->chunks.head[i];
474 		enum diff_chunk_type t = diff_chunk_type(c);
475 
476 		debug("[%d] %s lines L%d R%d @L %d @R %d\n",
477 		      i, (t == CHUNK_MINUS ? "minus" :
478 			  (t == CHUNK_PLUS ? "plus" :
479 			   (t == CHUNK_SAME ? "same" : "?"))),
480 		      c->left_count,
481 		      c->right_count,
482 		      c->left_start ? diff_atom_root_idx(result->left, c->left_start) : -1,
483 		      c->right_start ? diff_atom_root_idx(result->right, c->right_start) : -1);
484 		assert(check_left_pos == diff_atom_root_idx(result->left, c->left_start));
485 		assert(check_right_pos == diff_atom_root_idx(result->right, c->right_start));
486 		check_left_pos += c->left_count;
487 		check_right_pos += c->right_count;
488 
489 	}
490 	assert(check_left_pos == result->left->atoms.len);
491 	assert(check_right_pos == result->right->atoms.len);
492 #endif
493 
494 	for (i = 0; i < result->chunks.len; i++) {
495 		struct diff_chunk *c = &result->chunks.head[i];
496 		enum diff_chunk_type t = diff_chunk_type(c);
497 		struct diff_chunk_context next;
498 
499 		if (t != CHUNK_MINUS && t != CHUNK_PLUS)
500 			continue;
501 
502 		if (diff_chunk_context_empty(&cc)) {
503 			/* These are the first lines being printed.
504 			 * Note down the start point, any number of subsequent
505 			 * chunks may be joined up to this unidiff chunk by
506 			 * context lines or by being directly adjacent. */
507 			diff_chunk_context_get(&cc, result, i, context_lines);
508 			debug("new chunk to be printed:"
509 			      " chunk %d-%d left %d-%d right %d-%d\n",
510 			      cc.chunk.start, cc.chunk.end,
511 			      cc.left.start, cc.left.end,
512 			      cc.right.start, cc.right.end);
513 			continue;
514 		}
515 
516 		/* There already is a previous chunk noted down for being
517 		 * printed. Does it join up with this one? */
518 		diff_chunk_context_get(&next, result, i, context_lines);
519 		debug("new chunk to be printed:"
520 		      " chunk %d-%d left %d-%d right %d-%d\n",
521 		      next.chunk.start, next.chunk.end,
522 		      next.left.start, next.left.end,
523 		      next.right.start, next.right.end);
524 
525 		if (diff_chunk_contexts_touch(&cc, &next)) {
526 			/* This next context touches or overlaps the previous
527 			 * one, join. */
528 			diff_chunk_contexts_merge(&cc, &next);
529 			debug("new chunk to be printed touches previous chunk,"
530 			      " now: left %d-%d right %d-%d\n",
531 			      cc.left.start, cc.left.end,
532 			      cc.right.start, cc.right.end);
533 			continue;
534 		}
535 
536 		/* No touching, so the previous context is complete with a gap
537 		 * between it and this next one. Print the previous one and
538 		 * start fresh here. */
539 		debug("new chunk to be printed does not touch previous chunk;"
540 		      " print left %d-%d right %d-%d\n",
541 		      cc.left.start, cc.left.end, cc.right.start, cc.right.end);
542 		output_unidiff_chunk(outinfo, dest, state, info, result,
543 		    true, show_function_prototypes, &cc);
544 		cc = next;
545 		debug("new unprinted chunk is left %d-%d right %d-%d\n",
546 		      cc.left.start, cc.left.end, cc.right.start, cc.right.end);
547 	}
548 
549 	if (!diff_chunk_context_empty(&cc))
550 		output_unidiff_chunk(outinfo, dest, state, info, result,
551 		    true, show_function_prototypes, &cc);
552 	diff_output_unidiff_state_free(state);
553 	return DIFF_RC_OK;
554 }