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