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 static bool
32 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 static bool
98 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 static void
107 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 struct diff_output_unidiff_state {
116 	bool header_printed;
117 };
118 
119 struct diff_output_unidiff_state *
120 diff_output_unidiff_state_alloc(void)
121 {
122 	struct diff_output_unidiff_state *state;
123 
124 	state = calloc(1, sizeof(struct diff_output_unidiff_state));
125 	if (state != NULL)
126 		diff_output_unidiff_state_reset(state);
127 	return state;
128 }
129 
130 void
131 diff_output_unidiff_state_reset(struct diff_output_unidiff_state *state)
132 {
133 	state->header_printed = false;
134 }
135 
136 void
137 diff_output_unidiff_state_free(struct diff_output_unidiff_state *state)
138 {
139 	free(state);
140 }
141 
142 static int
143 output_unidiff_chunk(struct diff_output_info *outinfo, FILE *dest,
144 		     struct diff_output_unidiff_state *state,
145 		     const struct diff_input_info *info,
146 		     const struct diff_result *result,
147 		     const struct diff_chunk_context *cc)
148 {
149 	int rc;
150 	off_t outoff = 0, *offp;
151 
152 	if (diff_range_empty(&cc->left) && diff_range_empty(&cc->right))
153 		return DIFF_RC_OK;
154 
155 	if (outinfo && outinfo->line_offsets.len > 0) {
156 		unsigned int idx = outinfo->line_offsets.len - 1;
157 		outoff = outinfo->line_offsets.head[idx];
158 	}
159 
160 	if (!(state->header_printed)) {
161 		rc = fprintf(dest, "--- %s\n", info->left_path ? : "a");
162 		if (rc < 0)
163 			return errno;
164 		if (outinfo) {
165 			ARRAYLIST_ADD(offp, outinfo->line_offsets);
166 			if (offp == NULL)
167 				return ENOMEM;
168 			outoff += rc;
169 			*offp = outoff;
170 
171 		}
172 		rc = fprintf(dest, "+++ %s\n", info->right_path ? : "b");
173 		if (rc < 0)
174 			return errno;
175 		if (outinfo) {
176 			ARRAYLIST_ADD(offp, outinfo->line_offsets);
177 			if (offp == NULL)
178 				return ENOMEM;
179 			outoff += rc;
180 			*offp = outoff;
181 
182 		}
183 		state->header_printed = true;
184 	}
185 
186 	rc = fprintf(dest, "@@ -%d,%d +%d,%d @@\n",
187 		cc->left.start + 1, cc->left.end - cc->left.start,
188 		cc->right.start + 1, cc->right.end - cc->right.start);
189 	if (rc < 0)
190 		return errno;
191 	if (outinfo) {
192 		ARRAYLIST_ADD(offp, outinfo->line_offsets);
193 		if (offp == NULL)
194 			return ENOMEM;
195 		outoff += rc;
196 		*offp = outoff;
197 
198 	}
199 
200 	/* Got the absolute line numbers where to start printing, and the index
201 	 * of the interesting (non-context) chunk.
202 	 * To print context lines above the interesting chunk, nipping on the
203 	 * previous chunk index may be necessary.
204 	 * It is guaranteed to be only context lines where left == right, so it
205 	 * suffices to look on the left. */
206 	const struct diff_chunk *first_chunk;
207 	int chunk_start_line;
208 	first_chunk = &result->chunks.head[cc->chunk.start];
209 	chunk_start_line = diff_atom_root_idx(&result->left,
210 					      first_chunk->left_start);
211 	if (cc->left.start < chunk_start_line) {
212 		rc = diff_output_lines(outinfo, dest, " ",
213 				  &result->left.atoms.head[cc->left.start],
214 				  chunk_start_line - cc->left.start);
215 		if (rc)
216 			return rc;
217 	}
218 
219 	/* Now write out all the joined chunks and contexts between them */
220 	int c_idx;
221 	for (c_idx = cc->chunk.start; c_idx < cc->chunk.end; c_idx++) {
222 		const struct diff_chunk *c = &result->chunks.head[c_idx];
223 
224 		if (c->left_count && c->right_count)
225 			rc = diff_output_lines(outinfo, dest,
226 					  c->solved ? " " : "?",
227 					  c->left_start, c->left_count);
228 		else if (c->left_count && !c->right_count)
229 			rc = diff_output_lines(outinfo, dest,
230 					  c->solved ? "-" : "?",
231 					  c->left_start, c->left_count);
232 		else if (c->right_count && !c->left_count)
233 			rc = diff_output_lines(outinfo, dest,
234 					  c->solved ? "+" : "?",
235 					  c->right_start, c->right_count);
236 		if (rc)
237 			return rc;
238 	}
239 
240 	/* Trailing context? */
241 	const struct diff_chunk *last_chunk;
242 	int chunk_end_line;
243 	last_chunk = &result->chunks.head[cc->chunk.end - 1];
244 	chunk_end_line = diff_atom_root_idx(&result->left,
245 					    last_chunk->left_start
246 					    + last_chunk->left_count);
247 	if (cc->left.end > chunk_end_line) {
248 		rc = diff_output_lines(outinfo, dest, " ",
249 				  &result->left.atoms.head[chunk_end_line],
250 				  cc->left.end - chunk_end_line);
251 		if (rc)
252 			return rc;
253 	}
254 
255 	return DIFF_RC_OK;
256 }
257 
258 int
259 diff_output_unidiff_chunk(struct diff_output_info **output_info, FILE *dest,
260 			  struct diff_output_unidiff_state *state,
261 			  const struct diff_input_info *info,
262 			  const struct diff_result *result,
263 			  const struct diff_chunk_context *cc)
264 {
265 	struct diff_output_info *outinfo = NULL;
266 
267 	if (output_info) {
268 		*output_info = diff_output_info_alloc();
269 		if (*output_info == NULL)
270 			return ENOMEM;
271 		outinfo = *output_info;
272 	}
273 
274 	return output_unidiff_chunk(outinfo, dest, state, info,
275 	    result, cc);
276 }
277 
278 int
279 diff_output_unidiff(struct diff_output_info **output_info,
280 		    FILE *dest, const struct diff_input_info *info,
281 		    const struct diff_result *result,
282 		    unsigned int context_lines)
283 {
284 	struct diff_output_unidiff_state *state;
285 	struct diff_chunk_context cc = {};
286 	struct diff_output_info *outinfo = NULL;
287 	int i;
288 
289 	if (!result)
290 		return EINVAL;
291 	if (result->rc != DIFF_RC_OK)
292 		return result->rc;
293 
294 	if (output_info) {
295 		*output_info = diff_output_info_alloc();
296 		if (*output_info == NULL)
297 			return ENOMEM;
298 		outinfo = *output_info;
299 	}
300 
301 	state = diff_output_unidiff_state_alloc();
302 	if (state == NULL) {
303 		if (output_info) {
304 			diff_output_info_free(*output_info);
305 			*output_info = NULL;
306 		}
307 		return ENOMEM;
308 	}
309 
310 
311 	for (i = 0; i < result->chunks.len; i++) {
312 		struct diff_chunk *c = &result->chunks.head[i];
313 		enum diff_chunk_type t = diff_chunk_type(c);
314 		struct diff_chunk_context next;
315 
316 		if (t != CHUNK_MINUS && t != CHUNK_PLUS)
317 			continue;
318 
319 		if (chunk_context_empty(&cc)) {
320 			/* These are the first lines being printed.
321 			 * Note down the start point, any number of subsequent
322 			 * chunks may be joined up to this unidiff chunk by
323 			 * context lines or by being directly adjacent. */
324 			diff_chunk_context_get(&cc, result, i, context_lines);
325 			debug("new chunk to be printed:"
326 			      " chunk %d-%d left %d-%d right %d-%d\n",
327 			      cc.chunk.start, cc.chunk.end,
328 			      cc.left.start, cc.left.end,
329 			      cc.right.start, cc.right.end);
330 			continue;
331 		}
332 
333 		/* There already is a previous chunk noted down for being
334 		 * printed. Does it join up with this one? */
335 		diff_chunk_context_get(&next, result, i, context_lines);
336 		debug("new chunk to be printed:"
337 		      " chunk %d-%d left %d-%d right %d-%d\n",
338 		      next.chunk.start, next.chunk.end,
339 		      next.left.start, next.left.end,
340 		      next.right.start, next.right.end);
341 
342 		if (chunk_contexts_touch(&cc, &next)) {
343 			/* This next context touches or overlaps the previous
344 			 * one, join. */
345 			chunk_contexts_merge(&cc, &next);
346 			debug("new chunk to be printed touches previous chunk,"
347 			      " now: left %d-%d right %d-%d\n",
348 			      cc.left.start, cc.left.end,
349 			      cc.right.start, cc.right.end);
350 			continue;
351 		}
352 
353 		/* No touching, so the previous context is complete with a gap
354 		 * between it and this next one. Print the previous one and
355 		 * start fresh here. */
356 		debug("new chunk to be printed does not touch previous chunk;"
357 		      " print left %d-%d right %d-%d\n",
358 		      cc.left.start, cc.left.end, cc.right.start, cc.right.end);
359 		output_unidiff_chunk(outinfo, dest, state, info, result, &cc);
360 		cc = next;
361 		debug("new unprinted chunk is left %d-%d right %d-%d\n",
362 		      cc.left.start, cc.left.end, cc.right.start, cc.right.end);
363 	}
364 
365 	if (!chunk_context_empty(&cc))
366 		output_unidiff_chunk(outinfo, dest, state, info, result, &cc);
367 	diff_output_unidiff_state_free(state);
368 	return DIFF_RC_OK;
369 }