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 <assert.h>
24 
25 #include <arraylist.h>
26 #include <diff_main.h>
27 #include <diff_output.h>
28 
29 #include "diff_internal.h"
30 #include "diff_debug.h"
31 
32 bool
33 diff_chunk_context_empty(const struct diff_chunk_context *cc)
34 {
35 	return diff_range_empty(&cc->chunk);
36 }
37 
38 int
39 diff_chunk_get_left_start(const struct diff_chunk *c,
40     const struct diff_result *r, int context_lines)
41 {
42 	int left_start = diff_atom_root_idx(r->left, c->left_start);
43 	return MAX(0, left_start - context_lines);
44 }
45 
46 int
47 diff_chunk_get_left_end(const struct diff_chunk *c,
48     const struct diff_result *r, int context_lines)
49 {
50 	int left_start = diff_chunk_get_left_start(c, r, 0);
51 	return MIN(r->left->atoms.len,
52 	    left_start + c->left_count + context_lines);
53 }
54 
55 int
56 diff_chunk_get_right_start(const struct diff_chunk *c,
57     const struct diff_result *r, int context_lines)
58 {
59 	int right_start = diff_atom_root_idx(r->right, c->right_start);
60 	return MAX(0, right_start - context_lines);
61 }
62 
63 int
64 diff_chunk_get_right_end(const struct diff_chunk *c,
65     const struct diff_result *r, int context_lines)
66 {
67 	int right_start = diff_chunk_get_right_start(c, r, 0);
68 	return MIN(r->right->atoms.len,
69 	    right_start + c->right_count + context_lines);
70 }
71 
72 struct diff_chunk *
73 diff_chunk_get(const struct diff_result *r, int chunk_idx)
74 {
75 	return &r->chunks.head[chunk_idx];
76 }
77 
78 int
79 diff_chunk_get_left_count(struct diff_chunk *c)
80 {
81 	return c->left_count;
82 }
83 
84 int
85 diff_chunk_get_right_count(struct diff_chunk *c)
86 {
87 	return c->right_count;
88 }
89 
90 void
91 diff_chunk_context_get(struct diff_chunk_context *cc, const struct diff_result *r,
92 		  int chunk_idx, int context_lines)
93 {
94 	const struct diff_chunk *c = &r->chunks.head[chunk_idx];
95 	int left_start = diff_chunk_get_left_start(c, r, context_lines);
96 	int left_end = diff_chunk_get_left_end(c, r, context_lines);
97 	int right_start = diff_chunk_get_right_start(c, r, context_lines);
98 	int right_end = diff_chunk_get_right_end(c, r,  context_lines);
99 
100 	*cc = (struct diff_chunk_context){
101 		.chunk = {
102 			.start = chunk_idx,
103 			.end = chunk_idx + 1,
104 		},
105 		.left = {
106 			.start = left_start,
107 			.end = left_end,
108 		},
109 		.right = {
110 			.start = right_start,
111 			.end = right_end,
112 		},
113 	};
114 }
115 
116 bool
117 diff_chunk_contexts_touch(const struct diff_chunk_context *cc,
118 			  const struct diff_chunk_context *other)
119 {
120 	return diff_ranges_touch(&cc->chunk, &other->chunk)
121 		|| diff_ranges_touch(&cc->left, &other->left)
122 		|| diff_ranges_touch(&cc->right, &other->right);
123 }
124 
125 void
126 diff_chunk_contexts_merge(struct diff_chunk_context *cc,
127 			  const struct diff_chunk_context *other)
128 {
129 	diff_ranges_merge(&cc->chunk, &other->chunk);
130 	diff_ranges_merge(&cc->left, &other->left);
131 	diff_ranges_merge(&cc->right, &other->right);
132 }
133 
134 void
135 diff_chunk_context_load_change(struct diff_chunk_context *cc,
136 			       int *nchunks_used,
137 			       struct diff_result *result,
138 			       int start_chunk_idx,
139 			       int context_lines)
140 {
141 	int i;
142 	int seen_minus = 0, seen_plus = 0;
143 
144 	if (nchunks_used)
145 		*nchunks_used = 0;
146 
147 	for (i = start_chunk_idx; i < result->chunks.len; i++) {
148 		struct diff_chunk *chunk = &result->chunks.head[i];
149 		enum diff_chunk_type t = diff_chunk_type(chunk);
150 		struct diff_chunk_context next;
151 
152 		if (t != CHUNK_MINUS && t != CHUNK_PLUS) {
153 			if (nchunks_used)
154 				(*nchunks_used)++;
155 			if (seen_minus || seen_plus)
156 				break;
157 			else
158 				continue;
159 		} else if (t == CHUNK_MINUS)
160 			seen_minus = 1;
161 		else if (t == CHUNK_PLUS)
162 			seen_plus = 1;
163 
164 		if (diff_chunk_context_empty(cc)) {
165 			/* Note down the start point, any number of subsequent
166 			 * chunks may be joined up to this chunk by being
167 			 * directly adjacent. */
168 			diff_chunk_context_get(cc, result, i, context_lines);
169 			if (nchunks_used)
170 				(*nchunks_used)++;
171 			continue;
172 		}
173 
174 		/* There already is a previous chunk noted down for being
175 		 * printed. Does it join up with this one? */
176 		diff_chunk_context_get(&next, result, i, context_lines);
177 
178 		if (diff_chunk_contexts_touch(cc, &next)) {
179 			/* This next context touches or overlaps the previous
180 			 * one, join. */
181 			diff_chunk_contexts_merge(cc, &next);
182 			if (nchunks_used)
183 				(*nchunks_used)++;
184 			continue;
185 		} else
186 			break;
187 	}
188 }
189 
190 struct diff_output_unidiff_state {
191 	bool header_printed;
192 };
193 
194 struct diff_output_unidiff_state *
195 diff_output_unidiff_state_alloc(void)
196 {
197 	struct diff_output_unidiff_state *state;
198 
199 	state = calloc(1, sizeof(struct diff_output_unidiff_state));
200 	if (state != NULL)
201 		diff_output_unidiff_state_reset(state);
202 	return state;
203 }
204 
205 void
206 diff_output_unidiff_state_reset(struct diff_output_unidiff_state *state)
207 {
208 	state->header_printed = false;
209 }
210 
211 void
212 diff_output_unidiff_state_free(struct diff_output_unidiff_state *state)
213 {
214 	free(state);
215 }
216 
217 static int
218 output_unidiff_chunk(struct diff_output_info *outinfo, FILE *dest,
219 		     struct diff_output_unidiff_state *state,
220 		     const struct diff_input_info *info,
221 		     const struct diff_result *result,
222 		     bool print_header, bool show_function_prototypes,
223 		     const struct diff_chunk_context *cc)
224 {
225 	int rc, left_start, left_len, right_start, right_len;
226 	off_t outoff = 0, *offp;
227 	char *prototype = NULL;
228 
229 	if (diff_range_empty(&cc->left) && diff_range_empty(&cc->right))
230 		return DIFF_RC_OK;
231 
232 	if (outinfo && outinfo->line_offsets.len > 0) {
233 		unsigned int idx = outinfo->line_offsets.len - 1;
234 		outoff = outinfo->line_offsets.head[idx];
235 	}
236 
237 	if (print_header && !(state->header_printed)) {
238 		rc = fprintf(dest, "--- %s\n", info->left_path ? : "a");
239 		if (rc < 0)
240 			return errno;
241 		if (outinfo) {
242 			ARRAYLIST_ADD(offp, outinfo->line_offsets);
243 			if (offp == NULL)
244 				return ENOMEM;
245 			outoff += rc;
246 			*offp = outoff;
247 
248 		}
249 		rc = fprintf(dest, "+++ %s\n", info->right_path ? : "b");
250 		if (rc < 0)
251 			return errno;
252 		if (outinfo) {
253 			ARRAYLIST_ADD(offp, outinfo->line_offsets);
254 			if (offp == NULL)
255 				return ENOMEM;
256 			outoff += rc;
257 			*offp = outoff;
258 
259 		}
260 		state->header_printed = true;
261 	}
262 
263 	left_len = cc->left.end - cc->left.start;
264 	if (result->left->atoms.len == 0)
265 		left_start = 0;
266 	else if (left_len == 0 && cc->left.start > 0)
267 		left_start = cc->left.start;
268 	else
269 		left_start = cc->left.start + 1;
270 
271 	right_len = cc->right.end - cc->right.start;
272 	if (result->right->atoms.len == 0)
273 		right_start = 0;
274 	else if (right_len == 0 && cc->right.start > 0)
275 		right_start = cc->right.start;
276 	else
277 		right_start = cc->right.start + 1;
278 
279 	if (show_function_prototypes) {
280 		rc = diff_output_match_function_prototype(&prototype,
281 		    result, cc);
282 		if (rc)
283 			return rc;
284 	}
285 
286 	if (left_len == 1 && right_len == 1) {
287 		rc = fprintf(dest, "@@ -%d +%d @@%s%s\n",
288 			left_start, right_start,
289 			prototype ? " " : "",
290 			prototype ? : "");
291 	} else if (left_len == 1 && right_len != 1) {
292 		rc = fprintf(dest, "@@ -%d +%d,%d @@%s%s\n",
293 			left_start, right_start, right_len,
294 			prototype ? " " : "",
295 			prototype ? : "");
296 	} else if (left_len != 1 && right_len == 1) {
297 		rc = fprintf(dest, "@@ -%d,%d +%d @@%s%s\n",
298 			left_start, left_len, right_start,
299 			prototype ? " " : "",
300 			prototype ? : "");
301 	} else {
302 		rc = fprintf(dest, "@@ -%d,%d +%d,%d @@%s%s\n",
303 			left_start, left_len, right_start, right_len,
304 			prototype ? " " : "",
305 			prototype ? : "");
306 	}
307 	free(prototype);
308 	if (rc < 0)
309 		return errno;
310 	if (outinfo) {
311 		ARRAYLIST_ADD(offp, outinfo->line_offsets);
312 		if (offp == NULL)
313 			return ENOMEM;
314 		outoff += rc;
315 		*offp = outoff;
316 
317 	}
318 
319 	/* Got the absolute line numbers where to start printing, and the index
320 	 * of the interesting (non-context) chunk.
321 	 * To print context lines above the interesting chunk, nipping on the
322 	 * previous chunk index may be necessary.
323 	 * It is guaranteed to be only context lines where left == right, so it
324 	 * suffices to look on the left. */
325 	const struct diff_chunk *first_chunk;
326 	int chunk_start_line;
327 	first_chunk = &result->chunks.head[cc->chunk.start];
328 	chunk_start_line = diff_atom_root_idx(result->left,
329 					      first_chunk->left_start);
330 	if (cc->left.start < chunk_start_line) {
331 		rc = diff_output_lines(outinfo, dest, " ",
332 				  &result->left->atoms.head[cc->left.start],
333 				  chunk_start_line - cc->left.start);
334 		if (rc)
335 			return rc;
336 	}
337 
338 	/* Now write out all the joined chunks and contexts between them */
339 	int c_idx;
340 	for (c_idx = cc->chunk.start; c_idx < cc->chunk.end; c_idx++) {
341 		const struct diff_chunk *c = &result->chunks.head[c_idx];
342 
343 		if (c->left_count && c->right_count)
344 			rc = diff_output_lines(outinfo, dest,
345 					  c->solved ? " " : "?",
346 					  c->left_start, c->left_count);
347 		else if (c->left_count && !c->right_count)
348 			rc = diff_output_lines(outinfo, dest,
349 					  c->solved ? "-" : "?",
350 					  c->left_start, c->left_count);
351 		else if (c->right_count && !c->left_count)
352 			rc = diff_output_lines(outinfo, dest,
353 					  c->solved ? "+" : "?",
354 					  c->right_start, c->right_count);
355 		if (rc)
356 			return rc;
357 
358 		if (cc->chunk.end == result->chunks.len) {
359 			rc = diff_output_trailing_newline_msg(outinfo, dest, c);
360 			if (rc != DIFF_RC_OK)
361 				return rc;
362 		}
363 	}
364 
365 	/* Trailing context? */
366 	const struct diff_chunk *last_chunk;
367 	int chunk_end_line;
368 	last_chunk = &result->chunks.head[cc->chunk.end - 1];
369 	chunk_end_line = diff_atom_root_idx(result->left,
370 					    last_chunk->left_start
371 					    + last_chunk->left_count);
372 	if (cc->left.end > chunk_end_line) {
373 		rc = diff_output_lines(outinfo, dest, " ",
374 				  &result->left->atoms.head[chunk_end_line],
375 				  cc->left.end - chunk_end_line);
376 		if (rc)
377 			return rc;
378 	}
379 
380 	return DIFF_RC_OK;
381 }
382 
383 int
384 diff_output_unidiff_chunk(struct diff_output_info **output_info, FILE *dest,
385 			  struct diff_output_unidiff_state *state,
386 			  const struct diff_input_info *info,
387 			  const struct diff_result *result,
388 			  const struct diff_chunk_context *cc)
389 {
390 	struct diff_output_info *outinfo = NULL;
391 	int flags = (result->left->root->diff_flags |
392 	    result->right->root->diff_flags);
393 	bool show_function_prototypes = (flags & DIFF_FLAG_SHOW_PROTOTYPES);
394 
395 	if (output_info) {
396 		*output_info = diff_output_info_alloc();
397 		if (*output_info == NULL)
398 			return ENOMEM;
399 		outinfo = *output_info;
400 	}
401 
402 	return output_unidiff_chunk(outinfo, dest, state, info,
403 	    result, false, show_function_prototypes, cc);
404 }
405 
406 int
407 diff_output_unidiff(struct diff_output_info **output_info,
408 		    FILE *dest, const struct diff_input_info *info,
409 		    const struct diff_result *result,
410 		    unsigned int context_lines)
411 {
412 	struct diff_output_unidiff_state *state;
413 	struct diff_chunk_context cc = {};
414 	struct diff_output_info *outinfo = NULL;
415 	int flags = (result->left->root->diff_flags |
416 	    result->right->root->diff_flags);
417 	bool show_function_prototypes = (flags & DIFF_FLAG_SHOW_PROTOTYPES);
418 	int i;
419 
420 	if (!result)
421 		return EINVAL;
422 	if (result->rc != DIFF_RC_OK)
423 		return result->rc;
424 
425 	if (output_info) {
426 		*output_info = diff_output_info_alloc();
427 		if (*output_info == NULL)
428 			return ENOMEM;
429 		outinfo = *output_info;
430 	}
431 
432 	state = diff_output_unidiff_state_alloc();
433 	if (state == NULL) {
434 		if (output_info) {
435 			diff_output_info_free(*output_info);
436 			*output_info = NULL;
437 		}
438 		return ENOMEM;
439 	}
440 
441 #if DEBUG
442 	unsigned int check_left_pos, check_right_pos;
443 	check_left_pos = 0;
444 	check_right_pos = 0;
445 	for (i = 0; i < result->chunks.len; i++) {
446 		struct diff_chunk *c = &result->chunks.head[i];
447 		enum diff_chunk_type t = diff_chunk_type(c);
448 
449 		debug("[%d] %s lines L%d R%d @L %d @R %d\n",
450 		      i, (t == CHUNK_MINUS ? "minus" :
451 			  (t == CHUNK_PLUS ? "plus" :
452 			   (t == CHUNK_SAME ? "same" : "?"))),
453 		      c->left_count,
454 		      c->right_count,
455 		      c->left_start ? diff_atom_root_idx(result->left, c->left_start) : -1,
456 		      c->right_start ? diff_atom_root_idx(result->right, c->right_start) : -1);
457 		assert(check_left_pos == diff_atom_root_idx(result->left, c->left_start));
458 		assert(check_right_pos == diff_atom_root_idx(result->right, c->right_start));
459 		check_left_pos += c->left_count;
460 		check_right_pos += c->right_count;
461 
462 	}
463 	assert(check_left_pos == result->left->atoms.len);
464 	assert(check_right_pos == result->right->atoms.len);
465 #endif
466 
467 	for (i = 0; i < result->chunks.len; i++) {
468 		struct diff_chunk *c = &result->chunks.head[i];
469 		enum diff_chunk_type t = diff_chunk_type(c);
470 		struct diff_chunk_context next;
471 
472 		if (t != CHUNK_MINUS && t != CHUNK_PLUS)
473 			continue;
474 
475 		if (diff_chunk_context_empty(&cc)) {
476 			/* These are the first lines being printed.
477 			 * Note down the start point, any number of subsequent
478 			 * chunks may be joined up to this unidiff chunk by
479 			 * context lines or by being directly adjacent. */
480 			diff_chunk_context_get(&cc, result, i, context_lines);
481 			debug("new chunk to be printed:"
482 			      " chunk %d-%d left %d-%d right %d-%d\n",
483 			      cc.chunk.start, cc.chunk.end,
484 			      cc.left.start, cc.left.end,
485 			      cc.right.start, cc.right.end);
486 			continue;
487 		}
488 
489 		/* There already is a previous chunk noted down for being
490 		 * printed. Does it join up with this one? */
491 		diff_chunk_context_get(&next, result, i, context_lines);
492 		debug("new chunk to be printed:"
493 		      " chunk %d-%d left %d-%d right %d-%d\n",
494 		      next.chunk.start, next.chunk.end,
495 		      next.left.start, next.left.end,
496 		      next.right.start, next.right.end);
497 
498 		if (diff_chunk_contexts_touch(&cc, &next)) {
499 			/* This next context touches or overlaps the previous
500 			 * one, join. */
501 			diff_chunk_contexts_merge(&cc, &next);
502 			debug("new chunk to be printed touches previous chunk,"
503 			      " now: left %d-%d right %d-%d\n",
504 			      cc.left.start, cc.left.end,
505 			      cc.right.start, cc.right.end);
506 			continue;
507 		}
508 
509 		/* No touching, so the previous context is complete with a gap
510 		 * between it and this next one. Print the previous one and
511 		 * start fresh here. */
512 		debug("new chunk to be printed does not touch previous chunk;"
513 		      " print left %d-%d right %d-%d\n",
514 		      cc.left.start, cc.left.end, cc.right.start, cc.right.end);
515 		output_unidiff_chunk(outinfo, dest, state, info, result,
516 		    true, show_function_prototypes, &cc);
517 		cc = next;
518 		debug("new unprinted chunk is left %d-%d right %d-%d\n",
519 		      cc.left.start, cc.left.end, cc.right.start, cc.right.end);
520 	}
521 
522 	if (!diff_chunk_context_empty(&cc))
523 		output_unidiff_chunk(outinfo, dest, state, info, result,
524 		    true, show_function_prototypes, &cc);
525 	diff_output_unidiff_state_free(state);
526 	return DIFF_RC_OK;
527 }