1 /* Generic infrastructure to implement various diff algorithms. */
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 #ifndef MAX
19 #define MAX(A,B) ((A)>(B)?(A):(B))
20 #endif
21 #ifndef MIN
22 #define MIN(A,B) ((A)<(B)?(A):(B))
23 #endif
24 
25 static inline bool
26 diff_range_empty(const struct diff_range *r)
27 {
28 	return r->start == r->end;
29 }
30 
31 static inline bool
32 diff_ranges_touch(const struct diff_range *a, const struct diff_range *b)
33 {
34 	return (a->end >= b->start) && (a->start <= b->end);
35 }
36 
37 static inline void
38 diff_ranges_merge(struct diff_range *a, const struct diff_range *b)
39 {
40 	*a = (struct diff_range){
41 		.start = MIN(a->start, b->start),
42 		.end = MAX(a->end, b->end),
43 	};
44 }
45 
46 static inline int
47 diff_range_len(const struct diff_range *r)
48 {
49 	if (!r)
50 		return 0;
51 	return r->end - r->start;
52 }
53 
54 /* List of all possible return codes of a diff invocation. */
55 #define DIFF_RC_USE_DIFF_ALGO_FALLBACK	-1
56 #define DIFF_RC_OK			0
57 /* Any positive return values are errno values from sys/errno.h */
58 
59 struct diff_data;
60 
61 struct diff_atom {
62 	struct diff_data *d; /* back pointer to associated diff data */
63 
64 	off_t pos;		/* if not memory-mapped */
65 	const uint8_t *at;	/* if memory-mapped */
66 	off_t len;
67 
68 	/* This hash is just a very cheap speed up for finding *mismatching*
69 	 * atoms. When hashes match, we still need to compare entire atoms to
70 	 * find out whether they are indeed identical or not. */
71 	unsigned int hash;
72 
73 	/* State for the Patience Diff algorithm */
74 	/* TODO: keep a separate array for the patience state */
75 	struct {
76 		bool unique_here;
77 		bool unique_in_both;
78 		struct diff_atom *pos_in_other;
79 		struct diff_atom *prev_stack;
80 		struct diff_range identical_lines;
81 	} patience;
82 };
83 
84 int
85 diff_atom_cmp(int *cmp,
86 	      const struct diff_atom *left,
87 	      const struct diff_atom *right);
88 
89 /* Indicate whether two given diff atoms match. */
90 int
91 diff_atom_same(bool *same,
92 	       const struct diff_atom *left,
93 	       const struct diff_atom *right);
94 
95 /* The atom's index in the entire file. For atoms divided by lines of text, this
96  * yields the line number (starting with 0). Also works for diff_data that
97  * reference only a subsection of a file, always reflecting the global position
98  * in the file (and not the relative position within the subsection). */
99 #define diff_atom_root_idx(DIFF_DATA, ATOM) \
100 	((ATOM) && ((ATOM) >= (DIFF_DATA)->root->atoms.head) \
101 	 ? (unsigned int)((ATOM) - ((DIFF_DATA)->root->atoms.head)) \
102 	 : (DIFF_DATA)->root->atoms.len)
103 
104 /* The atom's index within DIFF_DATA. For atoms divided by lines of text, this
105  * yields the line number (starting with 0). */
106 #define diff_atom_idx(DIFF_DATA, ATOM) \
107 	((ATOM) && ((ATOM) >= (DIFF_DATA)->atoms.head) \
108 	 ? (unsigned int)((ATOM) - ((DIFF_DATA)->atoms.head)) \
109 	 : (DIFF_DATA)->atoms.len)
110 
111 #define foreach_diff_atom(ATOM, FIRST_ATOM, COUNT) \
112 	for ((ATOM) = (FIRST_ATOM); \
113 	     (ATOM) \
114 	     && ((ATOM) >= (FIRST_ATOM)) \
115 	     && ((ATOM) - (FIRST_ATOM) < (COUNT)); \
116 	     (ATOM)++)
117 
118 #define diff_data_foreach_atom(ATOM, DIFF_DATA) \
119 	foreach_diff_atom(ATOM, (DIFF_DATA)->atoms.head, (DIFF_DATA)->atoms.len)
120 
121 #define diff_data_foreach_atom_from(FROM, ATOM, DIFF_DATA) \
122 	for ((ATOM) = (FROM); \
123 	     (ATOM) \
124 	     && ((ATOM) >= (DIFF_DATA)->atoms.head) \
125 	     && ((ATOM) - (DIFF_DATA)->atoms.head < (DIFF_DATA)->atoms.len); \
126 	     (ATOM)++)
127 
128 /* A diff chunk represents a set of atoms on the left and/or a set of atoms on
129  * the right.
130  *
131  * If solved == false:
132  * The diff algorithm has divided the source file, and this is a chunk that the
133  * inner_algo should run on next.
134  * The lines on the left should be diffed against the lines on the right.
135  * (If there are no left lines or no right lines, it implies solved == true,
136  * because there is nothing to diff.)
137  *
138  * If solved == true:
139  * If there are only left atoms, it is a chunk removing atoms from the left ("a
140  * minus chunk").
141  * If there are only right atoms, it is a chunk adding atoms from the right ("a
142  * plus chunk").
143  * If there are both left and right lines, it is a chunk of equal content on
144  * both sides, and left_count == right_count:
145  *
146  * - foo  }
147  * - bar  }-- diff_chunk{ left_start = &left.atoms.head[0], left_count = 3,
148  * - baz  }               right_start = NULL, right_count = 0 }
149  *   moo    }
150  *   goo    }-- diff_chunk{ left_start = &left.atoms.head[3], left_count = 3,
151  *   zoo    }              right_start = &right.atoms.head[0], right_count = 3 }
152  *  +loo      }
153  *  +roo      }-- diff_chunk{ left_start = NULL, left_count = 0,
154  *  +too      }            right_start = &right.atoms.head[3], right_count = 3 }
155  *
156  */
157 struct diff_chunk {
158 	bool solved;
159 	struct diff_atom *left_start;
160 	unsigned int left_count;
161 	struct diff_atom *right_start;
162 	unsigned int right_count;
163 };
164 
165 #define DIFF_RESULT_ALLOC_BLOCKSIZE 128
166 
167 enum diff_chunk_type {
168 	CHUNK_EMPTY,
169 	CHUNK_PLUS,
170 	CHUNK_MINUS,
171 	CHUNK_SAME,
172 	CHUNK_ERROR,
173 };
174 
175 static inline enum diff_chunk_type
176 diff_chunk_type(const struct diff_chunk *chunk)
177 {
178 	if (!chunk->left_count && !chunk->right_count)
179 		return CHUNK_EMPTY;
180 	if (!chunk->solved)
181 		return CHUNK_ERROR;
182 	if (!chunk->right_count)
183 		return CHUNK_MINUS;
184 	if (!chunk->left_count)
185 		return CHUNK_PLUS;
186 	if (chunk->left_count != chunk->right_count)
187 		return CHUNK_ERROR;
188 	return CHUNK_SAME;
189 }
190 
191 struct diff_state {
192 	/* The final result passed to the original diff caller. */
193 	struct diff_result *result;
194 
195 	/* The root diff_data is in result->left,right, these are (possibly)
196 	 * subsections of the root data. */
197 	struct diff_data left;
198 	struct diff_data right;
199 
200 	unsigned int recursion_depth_left;
201 
202 	/* Remaining chunks from one diff algorithm pass, if any solved == false
203 	 * chunks came up. */
204 	diff_chunk_arraylist_t temp_result;
205 };
206 
207 struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved,
208 					struct diff_atom *left_start,
209 					unsigned int left_count,
210 					struct diff_atom *right_start,
211 					unsigned int right_count);
212 
213 struct diff_output_info;
214 
215 int diff_output_lines(struct diff_output_info *output_info, FILE *dest,
216 		       const char *prefix, struct diff_atom *start_atom,
217 		       unsigned int count);
218 
219 struct diff_output_info *diff_output_info_alloc(void);