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