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 <diff/arraylist.h>
25 #include <diff/diff_main.h>
26 #include <diff/diff_output.h>
27 
28 #include "diff_debug.h"
29 #include "diff_internal.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 void
38 diff_chunk_context_get(struct diff_chunk_context *cc, const struct diff_result *r,
39 		  int chunk_idx, int context_lines)
40 {
41 	const struct diff_chunk *c = &r->chunks.head[chunk_idx];
42 	int left_start = diff_atom_root_idx(&r->left, c->left_start);
43 	int left_end = MIN(r->left.atoms.len,
44 			   left_start + c->left_count + context_lines);
45 	int right_start = diff_atom_root_idx(&r->right, c->right_start);
46 	int right_end = MIN(r->right.atoms.len,
47 			    right_start + c->right_count + context_lines);
48 
49 	left_start = MAX(0, left_start - context_lines);
50 	right_start = MAX(0, right_start - context_lines);
51 
52 	*cc = (struct diff_chunk_context){
53 		.chunk = {
54 			.start = chunk_idx,
55 			.end = chunk_idx + 1,
56 		},
57 		.left = {
58 			.start = left_start,
59 			.end = left_end,
60 		},
61 		.right = {
62 			.start = right_start,
63 			.end = right_end,
64 		},
65 	};
66 }
67 
68 static bool
69 chunk_contexts_touch(const struct diff_chunk_context *cc,
70 		     const struct diff_chunk_context *other)
71 {
72 	return diff_ranges_touch(&cc->chunk, &other->chunk)
73 		|| diff_ranges_touch(&cc->left, &other->left)
74 		|| diff_ranges_touch(&cc->right, &other->right);
75 }
76 
77 static void
78 chunk_contexts_merge(struct diff_chunk_context *cc,
79 		     const struct diff_chunk_context *other)
80 {
81 	diff_ranges_merge(&cc->chunk, &other->chunk);
82 	diff_ranges_merge(&cc->left, &other->left);
83 	diff_ranges_merge(&cc->right, &other->right);
84 }
85 
86 struct diff_output_unidiff_state {
87 	bool header_printed;
88 };
89 
90 struct diff_output_unidiff_state *
91 diff_output_unidiff_state_alloc(void)
92 {
93 	struct diff_output_unidiff_state *state;
94 
95 	state = calloc(1, sizeof(struct diff_output_unidiff_state));
96 	if (state != NULL)
97 		diff_output_unidiff_state_reset(state);
98 	return state;
99 }
100 
101 void
102 diff_output_unidiff_state_reset(struct diff_output_unidiff_state *state)
103 {
104 	state->header_printed = false;
105 }
106 
107 void
108 diff_output_unidiff_state_free(struct diff_output_unidiff_state *state)
109 {
110 	free(state);
111 }
112 
113 static int
114 output_unidiff_chunk(struct diff_output_info *outinfo, FILE *dest,
115 		     struct diff_output_unidiff_state *state,
116 		     const struct diff_input_info *info,
117 		     const struct diff_result *result,
118 		     const struct diff_chunk_context *cc)
119 {
120 	int rc;
121 	off_t outoff = 0, *offp;
122 
123 	if (diff_range_empty(&cc->left) && diff_range_empty(&cc->right))
124 		return DIFF_RC_OK;
125 
126 	if (outinfo && outinfo->line_offsets.len > 0) {
127 		unsigned int idx = outinfo->line_offsets.len - 1;
128 		outoff = outinfo->line_offsets.head[idx];
129 	}
130 
131 	if (!(state->header_printed)) {
132 		rc = fprintf(dest, "--- %s\n", info->left_path ? : "a");
133 		if (rc < 0)
134 			return errno;
135 		if (outinfo) {
136 			ARRAYLIST_ADD(offp, outinfo->line_offsets);
137 			if (offp == NULL)
138 				return ENOMEM;
139 			outoff += rc;
140 			*offp = outoff;
141 
142 		}
143 		rc = fprintf(dest, "+++ %s\n", info->right_path ? : "b");
144 		if (rc < 0)
145 			return errno;
146 		if (outinfo) {
147 			ARRAYLIST_ADD(offp, outinfo->line_offsets);
148 			if (offp == NULL)
149 				return ENOMEM;
150 			outoff += rc;
151 			*offp = outoff;
152 
153 		}
154 		state->header_printed = true;
155 	}
156 
157 	rc = fprintf(dest, "@@ -%d,%d +%d,%d @@\n",
158 		cc->left.start + 1, cc->left.end - cc->left.start,
159 		cc->right.start + 1, cc->right.end - cc->right.start);
160 	if (rc < 0)
161 		return errno;
162 	if (outinfo) {
163 		ARRAYLIST_ADD(offp, outinfo->line_offsets);
164 		if (offp == NULL)
165 			return ENOMEM;
166 		outoff += rc;
167 		*offp = outoff;
168 
169 	}
170 
171 	/* Got the absolute line numbers where to start printing, and the index
172 	 * of the interesting (non-context) chunk.
173 	 * To print context lines above the interesting chunk, nipping on the
174 	 * previous chunk index may be necessary.
175 	 * It is guaranteed to be only context lines where left == right, so it
176 	 * suffices to look on the left. */
177 	const struct diff_chunk *first_chunk;
178 	int chunk_start_line;
179 	first_chunk = &result->chunks.head[cc->chunk.start];
180 	chunk_start_line = diff_atom_root_idx(&result->left,
181 					      first_chunk->left_start);
182 	if (cc->left.start < chunk_start_line) {
183 		rc = diff_output_lines(outinfo, dest, " ",
184 				  &result->left.atoms.head[cc->left.start],
185 				  chunk_start_line - cc->left.start);
186 		if (rc)
187 			return rc;
188 	}
189 
190 	/* Now write out all the joined chunks and contexts between them */
191 	int c_idx;
192 	for (c_idx = cc->chunk.start; c_idx < cc->chunk.end; c_idx++) {
193 		const struct diff_chunk *c = &result->chunks.head[c_idx];
194 
195 		if (c->left_count && c->right_count)
196 			rc = diff_output_lines(outinfo, dest,
197 					  c->solved ? " " : "?",
198 					  c->left_start, c->left_count);
199 		else if (c->left_count && !c->right_count)
200 			rc = diff_output_lines(outinfo, dest,
201 					  c->solved ? "-" : "?",
202 					  c->left_start, c->left_count);
203 		else if (c->right_count && !c->left_count)
204 			rc = diff_output_lines(outinfo, dest,
205 					  c->solved ? "+" : "?",
206 					  c->right_start, c->right_count);
207 		if (rc)
208 			return rc;
209 	}
210 
211 	/* Trailing context? */
212 	const struct diff_chunk *last_chunk;
213 	int chunk_end_line;
214 	last_chunk = &result->chunks.head[cc->chunk.end - 1];
215 	chunk_end_line = diff_atom_root_idx(&result->left,
216 					    last_chunk->left_start
217 					    + last_chunk->left_count);
218 	if (cc->left.end > chunk_end_line) {
219 		rc = diff_output_lines(outinfo, dest, " ",
220 				  &result->left.atoms.head[chunk_end_line],
221 				  cc->left.end - chunk_end_line);
222 		if (rc)
223 			return rc;
224 	}
225 
226 	return DIFF_RC_OK;
227 }
228 
229 int
230 diff_output_unidiff_chunk(struct diff_output_info **output_info, FILE *dest,
231 			  struct diff_output_unidiff_state *state,
232 			  const struct diff_input_info *info,
233 			  const struct diff_result *result,
234 			  const struct diff_chunk_context *cc)
235 {
236 	struct diff_output_info *outinfo = NULL;
237 
238 	if (output_info) {
239 		*output_info = diff_output_info_alloc();
240 		if (*output_info == NULL)
241 			return ENOMEM;
242 		outinfo = *output_info;
243 	}
244 
245 	return output_unidiff_chunk(outinfo, dest, state, info,
246 	    result, cc);
247 }
248 
249 int
250 diff_output_unidiff(struct diff_output_info **output_info,
251 		    FILE *dest, const struct diff_input_info *info,
252 		    const struct diff_result *result,
253 		    unsigned int context_lines)
254 {
255 	struct diff_output_unidiff_state *state;
256 	struct diff_chunk_context cc = {};
257 	struct diff_output_info *outinfo = NULL;
258 	int i;
259 
260 	if (!result)
261 		return EINVAL;
262 	if (result->rc != DIFF_RC_OK)
263 		return result->rc;
264 
265 	if (output_info) {
266 		*output_info = diff_output_info_alloc();
267 		if (*output_info == NULL)
268 			return ENOMEM;
269 		outinfo = *output_info;
270 	}
271 
272 	state = diff_output_unidiff_state_alloc();
273 	if (state == NULL) {
274 		if (output_info) {
275 			diff_output_info_free(*output_info);
276 			*output_info = NULL;
277 		}
278 		return ENOMEM;
279 	}
280 
281 
282 	for (i = 0; i < result->chunks.len; i++) {
283 		struct diff_chunk *c = &result->chunks.head[i];
284 		enum diff_chunk_type t = diff_chunk_type(c);
285 		struct diff_chunk_context next;
286 
287 		if (t != CHUNK_MINUS && t != CHUNK_PLUS)
288 			continue;
289 
290 		if (chunk_context_empty(&cc)) {
291 			/* These are the first lines being printed.
292 			 * Note down the start point, any number of subsequent
293 			 * chunks may be joined up to this unidiff chunk by
294 			 * context lines or by being directly adjacent. */
295 			diff_chunk_context_get(&cc, result, i, context_lines);
296 			debug("new chunk to be printed:"
297 			      " chunk %d-%d left %d-%d right %d-%d\n",
298 			      cc.chunk.start, cc.chunk.end,
299 			      cc.left.start, cc.left.end,
300 			      cc.right.start, cc.right.end);
301 			continue;
302 		}
303 
304 		/* There already is a previous chunk noted down for being
305 		 * printed. Does it join up with this one? */
306 		diff_chunk_context_get(&next, result, i, context_lines);
307 		debug("new chunk to be printed:"
308 		      " chunk %d-%d left %d-%d right %d-%d\n",
309 		      next.chunk.start, next.chunk.end,
310 		      next.left.start, next.left.end,
311 		      next.right.start, next.right.end);
312 
313 		if (chunk_contexts_touch(&cc, &next)) {
314 			/* This next context touches or overlaps the previous
315 			 * one, join. */
316 			chunk_contexts_merge(&cc, &next);
317 			debug("new chunk to be printed touches previous chunk,"
318 			      " now: left %d-%d right %d-%d\n",
319 			      cc.left.start, cc.left.end,
320 			      cc.right.start, cc.right.end);
321 			continue;
322 		}
323 
324 		/* No touching, so the previous context is complete with a gap
325 		 * between it and this next one. Print the previous one and
326 		 * start fresh here. */
327 		debug("new chunk to be printed does not touch previous chunk;"
328 		      " print left %d-%d right %d-%d\n",
329 		      cc.left.start, cc.left.end, cc.right.start, cc.right.end);
330 		output_unidiff_chunk(outinfo, dest, state, info, result, &cc);
331 		cc = next;
332 		debug("new unprinted chunk is left %d-%d right %d-%d\n",
333 		      cc.left.start, cc.left.end, cc.right.start, cc.right.end);
334 	}
335 
336 	if (!chunk_context_empty(&cc))
337 		output_unidiff_chunk(outinfo, dest, state, info, result, &cc);
338 	diff_output_unidiff_state_free(state);
339 	return DIFF_RC_OK;
340 }