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