1 85ab4559 2020-09-22 stsp /* Generic infrastructure to implement various diff algorithms. */
3 85ab4559 2020-09-22 stsp * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
5 85ab4559 2020-09-22 stsp * Permission to use, copy, modify, and distribute this software for any
6 85ab4559 2020-09-22 stsp * purpose with or without fee is hereby granted, provided that the above
7 85ab4559 2020-09-22 stsp * copyright notice and this permission notice appear in all copies.
9 85ab4559 2020-09-22 stsp * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 85ab4559 2020-09-22 stsp * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 85ab4559 2020-09-22 stsp * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 85ab4559 2020-09-22 stsp * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 85ab4559 2020-09-22 stsp * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 85ab4559 2020-09-22 stsp * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 85ab4559 2020-09-22 stsp * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 85ab4559 2020-09-22 stsp #define MAX(A,B) ((A)>(B)?(A):(B))
22 85ab4559 2020-09-22 stsp #define MIN(A,B) ((A)<(B)?(A):(B))
25 85ab4559 2020-09-22 stsp static inline bool
26 85ab4559 2020-09-22 stsp diff_range_empty(const struct diff_range *r)
28 85ab4559 2020-09-22 stsp return r->start == r->end;
31 85ab4559 2020-09-22 stsp static inline bool
32 85ab4559 2020-09-22 stsp diff_ranges_touch(const struct diff_range *a, const struct diff_range *b)
34 85ab4559 2020-09-22 stsp return (a->end >= b->start) && (a->start <= b->end);
37 85ab4559 2020-09-22 stsp static inline void
38 85ab4559 2020-09-22 stsp diff_ranges_merge(struct diff_range *a, const struct diff_range *b)
40 85ab4559 2020-09-22 stsp *a = (struct diff_range){
41 85ab4559 2020-09-22 stsp .start = MIN(a->start, b->start),
42 85ab4559 2020-09-22 stsp .end = MAX(a->end, b->end),
46 85ab4559 2020-09-22 stsp static inline int
47 85ab4559 2020-09-22 stsp diff_range_len(const struct diff_range *r)
51 85ab4559 2020-09-22 stsp return r->end - r->start;
54 85ab4559 2020-09-22 stsp /* List of all possible return codes of a diff invocation. */
55 85ab4559 2020-09-22 stsp #define DIFF_RC_USE_DIFF_ALGO_FALLBACK -1
56 85ab4559 2020-09-22 stsp #define DIFF_RC_OK 0
57 85ab4559 2020-09-22 stsp /* Any positive return values are errno values from sys/errno.h */
59 85ab4559 2020-09-22 stsp struct diff_data;
61 85ab4559 2020-09-22 stsp struct diff_atom {
62 85ab4559 2020-09-22 stsp struct diff_data *d; /* back pointer to associated diff data */
64 85ab4559 2020-09-22 stsp off_t pos; /* if not memory-mapped */
65 85ab4559 2020-09-22 stsp const uint8_t *at; /* if memory-mapped */
68 85ab4559 2020-09-22 stsp /* This hash is just a very cheap speed up for finding *mismatching*
69 85ab4559 2020-09-22 stsp * atoms. When hashes match, we still need to compare entire atoms to
70 85ab4559 2020-09-22 stsp * find out whether they are indeed identical or not. */
71 85ab4559 2020-09-22 stsp unsigned int hash;
73 85ab4559 2020-09-22 stsp /* State for the Patience Diff algorithm */
74 85ab4559 2020-09-22 stsp /* TODO: keep a separate array for the patience state */
76 85ab4559 2020-09-22 stsp bool unique_here;
77 85ab4559 2020-09-22 stsp bool unique_in_both;
78 85ab4559 2020-09-22 stsp struct diff_atom *pos_in_other;
79 85ab4559 2020-09-22 stsp struct diff_atom *prev_stack;
80 85ab4559 2020-09-22 stsp struct diff_range identical_lines;
85 85ab4559 2020-09-22 stsp diff_atom_cmp(int *cmp,
86 85ab4559 2020-09-22 stsp const struct diff_atom *left,
87 85ab4559 2020-09-22 stsp const struct diff_atom *right);
89 85ab4559 2020-09-22 stsp /* Indicate whether two given diff atoms match. */
91 85ab4559 2020-09-22 stsp diff_atom_same(bool *same,
92 85ab4559 2020-09-22 stsp const struct diff_atom *left,
93 85ab4559 2020-09-22 stsp const struct diff_atom *right);
95 85ab4559 2020-09-22 stsp /* The atom's index in the entire file. For atoms divided by lines of text, this
96 85ab4559 2020-09-22 stsp * yields the line number (starting with 0). Also works for diff_data that
97 85ab4559 2020-09-22 stsp * reference only a subsection of a file, always reflecting the global position
98 85ab4559 2020-09-22 stsp * in the file (and not the relative position within the subsection). */
99 85ab4559 2020-09-22 stsp #define diff_atom_root_idx(DIFF_DATA, ATOM) \
100 85ab4559 2020-09-22 stsp ((ATOM) && ((ATOM) >= (DIFF_DATA)->root->atoms.head) \
101 85ab4559 2020-09-22 stsp ? (unsigned int)((ATOM) - ((DIFF_DATA)->root->atoms.head)) \
102 85ab4559 2020-09-22 stsp : (DIFF_DATA)->root->atoms.len)
104 85ab4559 2020-09-22 stsp /* The atom's index within DIFF_DATA. For atoms divided by lines of text, this
105 85ab4559 2020-09-22 stsp * yields the line number (starting with 0). */
106 85ab4559 2020-09-22 stsp #define diff_atom_idx(DIFF_DATA, ATOM) \
107 85ab4559 2020-09-22 stsp ((ATOM) && ((ATOM) >= (DIFF_DATA)->atoms.head) \
108 85ab4559 2020-09-22 stsp ? (unsigned int)((ATOM) - ((DIFF_DATA)->atoms.head)) \
109 85ab4559 2020-09-22 stsp : (DIFF_DATA)->atoms.len)
111 85ab4559 2020-09-22 stsp #define foreach_diff_atom(ATOM, FIRST_ATOM, COUNT) \
112 85ab4559 2020-09-22 stsp for ((ATOM) = (FIRST_ATOM); \
114 85ab4559 2020-09-22 stsp && ((ATOM) >= (FIRST_ATOM)) \
115 85ab4559 2020-09-22 stsp && ((ATOM) - (FIRST_ATOM) < (COUNT)); \
118 85ab4559 2020-09-22 stsp #define diff_data_foreach_atom(ATOM, DIFF_DATA) \
119 85ab4559 2020-09-22 stsp foreach_diff_atom(ATOM, (DIFF_DATA)->atoms.head, (DIFF_DATA)->atoms.len)
121 85ab4559 2020-09-22 stsp #define diff_data_foreach_atom_from(FROM, ATOM, DIFF_DATA) \
122 85ab4559 2020-09-22 stsp for ((ATOM) = (FROM); \
124 85ab4559 2020-09-22 stsp && ((ATOM) >= (DIFF_DATA)->atoms.head) \
125 85ab4559 2020-09-22 stsp && ((ATOM) - (DIFF_DATA)->atoms.head < (DIFF_DATA)->atoms.len); \
128 85ab4559 2020-09-22 stsp /* A diff chunk represents a set of atoms on the left and/or a set of atoms on
129 85ab4559 2020-09-22 stsp * the right.
131 85ab4559 2020-09-22 stsp * If solved == false:
132 85ab4559 2020-09-22 stsp * The diff algorithm has divided the source file, and this is a chunk that the
133 85ab4559 2020-09-22 stsp * inner_algo should run on next.
134 85ab4559 2020-09-22 stsp * The lines on the left should be diffed against the lines on the right.
135 85ab4559 2020-09-22 stsp * (If there are no left lines or no right lines, it implies solved == true,
136 85ab4559 2020-09-22 stsp * because there is nothing to diff.)
138 85ab4559 2020-09-22 stsp * If solved == true:
139 85ab4559 2020-09-22 stsp * If there are only left atoms, it is a chunk removing atoms from the left ("a
140 85ab4559 2020-09-22 stsp * minus chunk").
141 85ab4559 2020-09-22 stsp * If there are only right atoms, it is a chunk adding atoms from the right ("a
142 85ab4559 2020-09-22 stsp * plus chunk").
143 85ab4559 2020-09-22 stsp * If there are both left and right lines, it is a chunk of equal content on
144 85ab4559 2020-09-22 stsp * both sides, and left_count == right_count:
147 85ab4559 2020-09-22 stsp * - bar }-- diff_chunk{ left_start = &left.atoms.head[0], left_count = 3,
148 85ab4559 2020-09-22 stsp * - baz } right_start = NULL, right_count = 0 }
150 85ab4559 2020-09-22 stsp * goo }-- diff_chunk{ left_start = &left.atoms.head[3], left_count = 3,
151 85ab4559 2020-09-22 stsp * zoo } right_start = &right.atoms.head[0], right_count = 3 }
153 85ab4559 2020-09-22 stsp * +roo }-- diff_chunk{ left_start = NULL, left_count = 0,
154 85ab4559 2020-09-22 stsp * +too } right_start = &right.atoms.head[3], right_count = 3 }
157 85ab4559 2020-09-22 stsp struct diff_chunk {
158 85ab4559 2020-09-22 stsp bool solved;
159 85ab4559 2020-09-22 stsp struct diff_atom *left_start;
160 85ab4559 2020-09-22 stsp unsigned int left_count;
161 85ab4559 2020-09-22 stsp struct diff_atom *right_start;
162 85ab4559 2020-09-22 stsp unsigned int right_count;
165 85ab4559 2020-09-22 stsp #define DIFF_RESULT_ALLOC_BLOCKSIZE 128
167 85ab4559 2020-09-22 stsp enum diff_chunk_type {
168 85ab4559 2020-09-22 stsp CHUNK_EMPTY,
169 85ab4559 2020-09-22 stsp CHUNK_PLUS,
170 85ab4559 2020-09-22 stsp CHUNK_MINUS,
171 85ab4559 2020-09-22 stsp CHUNK_SAME,
172 85ab4559 2020-09-22 stsp CHUNK_ERROR,
175 85ab4559 2020-09-22 stsp static inline enum diff_chunk_type
176 85ab4559 2020-09-22 stsp diff_chunk_type(const struct diff_chunk *chunk)
178 85ab4559 2020-09-22 stsp if (!chunk->left_count && !chunk->right_count)
179 85ab4559 2020-09-22 stsp return CHUNK_EMPTY;
180 85ab4559 2020-09-22 stsp if (!chunk->solved)
181 85ab4559 2020-09-22 stsp return CHUNK_ERROR;
182 85ab4559 2020-09-22 stsp if (!chunk->right_count)
183 85ab4559 2020-09-22 stsp return CHUNK_MINUS;
184 85ab4559 2020-09-22 stsp if (!chunk->left_count)
185 85ab4559 2020-09-22 stsp return CHUNK_PLUS;
186 85ab4559 2020-09-22 stsp if (chunk->left_count != chunk->right_count)
187 85ab4559 2020-09-22 stsp return CHUNK_ERROR;
188 85ab4559 2020-09-22 stsp return CHUNK_SAME;
191 85ab4559 2020-09-22 stsp struct diff_state {
192 85ab4559 2020-09-22 stsp /* The final result passed to the original diff caller. */
193 85ab4559 2020-09-22 stsp struct diff_result *result;
195 85ab4559 2020-09-22 stsp /* The root diff_data is in result->left,right, these are (possibly)
196 85ab4559 2020-09-22 stsp * subsections of the root data. */
197 85ab4559 2020-09-22 stsp struct diff_data left;
198 85ab4559 2020-09-22 stsp struct diff_data right;
200 85ab4559 2020-09-22 stsp unsigned int recursion_depth_left;
202 85ab4559 2020-09-22 stsp /* Remaining chunks from one diff algorithm pass, if any solved == false
203 85ab4559 2020-09-22 stsp * chunks came up. */
204 85ab4559 2020-09-22 stsp diff_chunk_arraylist_t temp_result;
207 85ab4559 2020-09-22 stsp struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved,
208 85ab4559 2020-09-22 stsp struct diff_atom *left_start,
209 85ab4559 2020-09-22 stsp unsigned int left_count,
210 85ab4559 2020-09-22 stsp struct diff_atom *right_start,
211 85ab4559 2020-09-22 stsp unsigned int right_count);
213 2c20a3ed 2020-09-22 stsp struct diff_output_info;
215 2c20a3ed 2020-09-22 stsp int diff_output_lines(struct diff_output_info *output_info, FILE *dest,
216 2c20a3ed 2020-09-22 stsp const char *prefix, struct diff_atom *start_atom,
217 2c20a3ed 2020-09-22 stsp unsigned int count);
219 2c20a3ed 2020-09-22 stsp struct diff_output_info *diff_output_info_alloc(void);
