1 /* Generic infrastructure to implement various diff algorithms. */
3 * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
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.
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.
19 #define MAX(A,B) ((A)>(B)?(A):(B))
22 #define MIN(A,B) ((A)<(B)?(A):(B))
26 diff_range_empty(const struct diff_range *r)
28 return r->start == r->end;
32 diff_ranges_touch(const struct diff_range *a, const struct diff_range *b)
34 return (a->end >= b->start) && (a->start <= b->end);
38 diff_ranges_merge(struct diff_range *a, const struct diff_range *b)
40 *a = (struct diff_range){
41 .start = MIN(a->start, b->start),
42 .end = MAX(a->end, b->end),
47 diff_range_len(const struct diff_range *r)
51 return r->end - r->start;
54 /* List of all possible return codes of a diff invocation. */
55 #define DIFF_RC_USE_DIFF_ALGO_FALLBACK -1
57 /* Any positive return values are errno values from sys/errno.h */
62 struct diff_data *root; /* back pointer to root diff data */
64 off_t pos; /* if not memory-mapped */
65 const uint8_t *at; /* if memory-mapped */
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. */
73 /* State for the Patience Diff algorithm */
74 /* TODO: keep a separate array for the patience state */
77 struct diff_atom *pos_in_other;
78 struct diff_atom *prev_stack;
79 struct diff_range identical_lines;
84 diff_atom_cmp(int *cmp,
85 const struct diff_atom *left,
86 const struct diff_atom *right);
88 /* Indicate whether two given diff atoms match. */
90 diff_atom_same(bool *same,
91 const struct diff_atom *left,
92 const struct diff_atom *right);
94 /* The atom's index in the entire file. For atoms divided by lines of text, this
95 * yields the line number (starting with 0). Also works for diff_data that
96 * reference only a subsection of a file, always reflecting the global position
97 * in the file (and not the relative position within the subsection). */
98 #define diff_atom_root_idx(DIFF_DATA, ATOM) \
99 ((ATOM) && ((ATOM) >= (DIFF_DATA)->root->atoms.head) \
100 ? (unsigned int)((ATOM) - ((DIFF_DATA)->root->atoms.head)) \
101 : (DIFF_DATA)->root->atoms.len)
103 /* The atom's index within DIFF_DATA. For atoms divided by lines of text, this
104 * yields the line number (starting with 0). */
105 #define diff_atom_idx(DIFF_DATA, ATOM) \
106 ((ATOM) && ((ATOM) >= (DIFF_DATA)->atoms.head) \
107 ? (unsigned int)((ATOM) - ((DIFF_DATA)->atoms.head)) \
108 : (DIFF_DATA)->atoms.len)
110 #define foreach_diff_atom(ATOM, FIRST_ATOM, COUNT) \
111 for ((ATOM) = (FIRST_ATOM); \
113 && ((ATOM) >= (FIRST_ATOM)) \
114 && ((ATOM) - (FIRST_ATOM) < (COUNT)); \
117 #define diff_data_foreach_atom(ATOM, DIFF_DATA) \
118 foreach_diff_atom(ATOM, (DIFF_DATA)->atoms.head, (DIFF_DATA)->atoms.len)
120 #define diff_data_foreach_atom_from(FROM, ATOM, DIFF_DATA) \
121 for ((ATOM) = (FROM); \
123 && ((ATOM) >= (DIFF_DATA)->atoms.head) \
124 && ((ATOM) - (DIFF_DATA)->atoms.head < (DIFF_DATA)->atoms.len); \
127 /* A diff chunk represents a set of atoms on the left and/or a set of atoms on
130 * If solved == false:
131 * The diff algorithm has divided the source file, and this is a chunk that the
132 * inner_algo should run on next.
133 * The lines on the left should be diffed against the lines on the right.
134 * (If there are no left lines or no right lines, it implies solved == true,
135 * because there is nothing to diff.)
138 * If there are only left atoms, it is a chunk removing atoms from the left ("a
140 * If there are only right atoms, it is a chunk adding atoms from the right ("a
142 * If there are both left and right lines, it is a chunk of equal content on
143 * both sides, and left_count == right_count:
146 * - bar }-- diff_chunk{ left_start = &left.atoms.head[0], left_count = 3,
147 * - baz } right_start = NULL, right_count = 0 }
149 * goo }-- diff_chunk{ left_start = &left.atoms.head[3], left_count = 3,
150 * zoo } right_start = &right.atoms.head[0], right_count = 3 }
152 * +roo }-- diff_chunk{ left_start = NULL, left_count = 0,
153 * +too } right_start = &right.atoms.head[3], right_count = 3 }
158 struct diff_atom *left_start;
159 unsigned int left_count;
160 struct diff_atom *right_start;
161 unsigned int right_count;
164 #define DIFF_RESULT_ALLOC_BLOCKSIZE 128
166 enum diff_chunk_type {
174 static inline enum diff_chunk_type
175 diff_chunk_type(const struct diff_chunk *chunk)
177 if (!chunk->left_count && !chunk->right_count)
181 if (!chunk->right_count)
183 if (!chunk->left_count)
185 if (chunk->left_count != chunk->right_count)
191 /* The final result passed to the original diff caller. */
192 struct diff_result *result;
194 /* The root diff_data is in result->left,right, these are (possibly)
195 * subsections of the root data. */
196 struct diff_data left;
197 struct diff_data right;
199 unsigned int recursion_depth_left;
201 /* Remaining chunks from one diff algorithm pass, if any solved == false
203 diff_chunk_arraylist_t temp_result;
206 struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved,
207 struct diff_atom *left_start,
208 unsigned int left_count,
209 struct diff_atom *right_start,
210 unsigned int right_count);
212 struct diff_output_info;
214 int diff_output_lines(struct diff_output_info *output_info, FILE *dest,
215 const char *prefix, struct diff_atom *start_atom,
218 struct diff_output_info *diff_output_info_alloc(void);
221 diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
222 struct diff_atom *from_atom, unsigned int atoms_count);