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 <diff/diff_output.h>
19 
20 #include "debug.h"
21 
22 enum chunk_type {
23 	CHUNK_EMPTY,
24 	CHUNK_PLUS,
25 	CHUNK_MINUS,
26 	CHUNK_SAME,
27 	CHUNK_WEIRD,
28 };
29 
30 static inline enum chunk_type
31 chunk_type(const struct diff_chunk *chunk)
32 {
33 	if (!chunk->left_count && !chunk->right_count)
34 		return CHUNK_EMPTY;
35 	if (!chunk->solved)
36 		return CHUNK_WEIRD;
37 	if (!chunk->right_count)
38 		return CHUNK_MINUS;
39 	if (!chunk->left_count)
40 		return CHUNK_PLUS;
41 	if (chunk->left_count != chunk->right_count)
42 		return CHUNK_WEIRD;
43 	return CHUNK_SAME;
44 }
45 
46 struct chunk_context {
47 	struct diff_range chunk;
48 	struct diff_range left, right;
49 };
50 
51 static bool
52 chunk_context_empty(const struct chunk_context *cc)
53 {
54 	return diff_range_empty(&cc->chunk);
55 }
56 
57 static void
58 chunk_context_get(struct chunk_context *cc, const struct diff_result *r,
59 		  int chunk_idx, int context_lines)
60 {
61 	const struct diff_chunk *c = &r->chunks.head[chunk_idx];
62 	int left_start = diff_atom_root_idx(&r->left, c->left_start);
63 	int left_end = MIN(r->left.atoms.len,
64 			   left_start + c->left_count + context_lines);
65 	int right_start = diff_atom_root_idx(&r->right, c->right_start);
66 	int right_end = MIN(r->right.atoms.len,
67 			    right_start + c->right_count + context_lines);
68 
69 	left_start = MAX(0, left_start - context_lines);
70 	right_start = MAX(0, right_start - context_lines);
71 
72 	*cc = (struct chunk_context){
73 		.chunk = {
74 			.start = chunk_idx,
75 			.end = chunk_idx + 1,
76 		},
77 		.left = {
78 			.start = left_start,
79 			.end = left_end,
80 		},
81 		.right = {
82 			.start = right_start,
83 			.end = right_end,
84 		},
85 	};
86 }
87 
88 static bool
89 chunk_contexts_touch(const struct chunk_context *cc,
90 		     const struct chunk_context *other)
91 {
92 	return diff_ranges_touch(&cc->chunk, &other->chunk)
93 		|| diff_ranges_touch(&cc->left, &other->left)
94 		|| diff_ranges_touch(&cc->right, &other->right);
95 }
96 
97 static void
98 chunk_contexts_merge(struct chunk_context *cc,
99 		     const struct chunk_context *other)
100 {
101 	diff_ranges_merge(&cc->chunk, &other->chunk);
102 	diff_ranges_merge(&cc->left, &other->left);
103 	diff_ranges_merge(&cc->right, &other->right);
104 }
105 
106 static void
107 diff_output_unidiff_chunk(FILE *dest, bool *header_printed,
108 			  const struct diff_input_info *info,
109 			  const struct diff_result *result,
110 			  const struct chunk_context *cc)
111 {
112 	if (diff_range_empty(&cc->left) && diff_range_empty(&cc->right))
113 		return;
114 
115 	if (!(*header_printed)) {
116 		fprintf(dest, "--- %s\n+++ %s\n",
117 			info->left_path ? : "a",
118 			info->right_path ? : "b");
119 		*header_printed = true;
120 	}
121 
122 	fprintf(dest, "@@ -%d,%d +%d,%d @@\n",
123 		cc->left.start + 1, cc->left.end - cc->left.start,
124 		cc->right.start + 1, cc->right.end - cc->right.start);
125 
126 	/* Got the absolute line numbers where to start printing, and the index
127 	 * of the interesting (non-context) chunk.
128 	 * To print context lines above the interesting chunk, nipping on the
129 	 * previous chunk index may be necessary.
130 	 * It is guaranteed to be only context lines where left == right, so it
131 	 * suffices to look on the left. */
132 	const struct diff_chunk *first_chunk;
133 	int chunk_start_line;
134 	first_chunk = &result->chunks.head[cc->chunk.start];
135 	chunk_start_line = diff_atom_root_idx(&result->left,
136 					      first_chunk->left_start);
137 	if (cc->left.start < chunk_start_line)
138 		diff_output_lines(dest, " ",
139 				  &result->left.atoms.head[cc->left.start],
140 				  chunk_start_line - cc->left.start);
141 
142 	/* Now write out all the joined chunks and contexts between them */
143 	int c_idx;
144 	for (c_idx = cc->chunk.start; c_idx < cc->chunk.end; c_idx++) {
145 		const struct diff_chunk *c = &result->chunks.head[c_idx];
146 
147 		if (c->left_count && c->right_count)
148 			diff_output_lines(dest,
149 					  c->solved ? " " : "?",
150 					  c->left_start, c->left_count);
151 		else if (c->left_count && !c->right_count)
152 			diff_output_lines(dest,
153 					  c->solved ? "-" : "?",
154 					  c->left_start, c->left_count);
155 		else if (c->right_count && !c->left_count)
156 			diff_output_lines(dest,
157 					  c->solved ? "+" : "?",
158 					  c->right_start, c->right_count);
159 	}
160 
161 	/* Trailing context? */
162 	const struct diff_chunk *last_chunk;
163 	int chunk_end_line;
164 	last_chunk = &result->chunks.head[cc->chunk.end - 1];
165 	chunk_end_line = diff_atom_root_idx(&result->left,
166 					    last_chunk->left_start
167 					    + last_chunk->left_count);
168 	if (cc->left.end > chunk_end_line)
169 		diff_output_lines(dest, " ",
170 				  &result->left.atoms.head[chunk_end_line],
171 				  cc->left.end - chunk_end_line);
172 }
173 
174 enum diff_rc
175 diff_output_unidiff(FILE *dest, const struct diff_input_info *info,
176 		    const struct diff_result *result,
177 		    unsigned int context_lines)
178 {
179 	if (!result)
180 		return DIFF_RC_EINVAL;
181 	if (result->rc != DIFF_RC_OK)
182 		return result->rc;
183 
184 	struct chunk_context cc = {};
185 	bool header_printed = false;
186 
187 	int i;
188 	for (i = 0; i < result->chunks.len; i++) {
189 		struct diff_chunk *c = &result->chunks.head[i];
190 		enum chunk_type t = chunk_type(c);
191 		struct chunk_context next;
192 
193 		if (t != CHUNK_MINUS && t != CHUNK_PLUS)
194 			continue;
195 
196 		if (chunk_context_empty(&cc)) {
197 			/* These are the first lines being printed.
198 			 * Note down the start point, any number of subsequent
199 			 * chunks may be joined up to this unidiff chunk by
200 			 * context lines or by being directly adjacent. */
201 			chunk_context_get(&cc, result, i, context_lines);
202 			debug("new chunk to be printed:"
203 			      " chunk %d-%d left %d-%d right %d-%d\n",
204 			      cc.chunk.start, cc.chunk.end,
205 			      cc.left.start, cc.left.end,
206 			      cc.right.start, cc.right.end);
207 			continue;
208 		}
209 
210 		/* There already is a previous chunk noted down for being
211 		 * printed. Does it join up with this one? */
212 		chunk_context_get(&next, result, i, context_lines);
213 		debug("new chunk to be printed:"
214 		      " chunk %d-%d left %d-%d right %d-%d\n",
215 		      next.chunk.start, next.chunk.end,
216 		      next.left.start, next.left.end,
217 		      next.right.start, next.right.end);
218 
219 		if (chunk_contexts_touch(&cc, &next)) {
220 			/* This next context touches or overlaps the previous
221 			 * one, join. */
222 			chunk_contexts_merge(&cc, &next);
223 			debug("new chunk to be printed touches previous chunk,"
224 			      " now: left %d-%d right %d-%d\n",
225 			      cc.left.start, cc.left.end,
226 			      cc.right.start, cc.right.end);
227 			continue;
228 		}
229 
230 		/* No touching, so the previous context is complete with a gap
231 		 * between it and this next one. Print the previous one and
232 		 * start fresh here. */
233 		debug("new chunk to be printed does not touch previous chunk;"
234 		      " print left %d-%d right %d-%d\n",
235 		      cc.left.start, cc.left.end, cc.right.start, cc.right.end);
236 		diff_output_unidiff_chunk(dest, &header_printed, info, result,
237 					  &cc);
238 		cc = next;
239 		debug("new unprinted chunk is left %d-%d right %d-%d\n",
240 		      cc.left.start, cc.left.end, cc.right.start, cc.right.end);
241 	}
242 
243 	if (!chunk_context_empty(&cc))
244 		diff_output_unidiff_chunk(dest, &header_printed, info, result,
245 					  &cc);
246 	return DIFF_RC_OK;
247 }