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