1 1dfba055 2020-10-07 stsp /* Generic infrastructure to implement various diff algorithms. */
  2 1dfba055 2020-10-07 stsp /*
  3 1dfba055 2020-10-07 stsp  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
  4 1dfba055 2020-10-07 stsp  *
  5 1dfba055 2020-10-07 stsp  * Permission to use, copy, modify, and distribute this software for any
  6 1dfba055 2020-10-07 stsp  * purpose with or without fee is hereby granted, provided that the above
  7 1dfba055 2020-10-07 stsp  * copyright notice and this permission notice appear in all copies.
  8 1dfba055 2020-10-07 stsp  *
  9 1dfba055 2020-10-07 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 10 1dfba055 2020-10-07 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 11 1dfba055 2020-10-07 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 12 1dfba055 2020-10-07 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 13 1dfba055 2020-10-07 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 14 1dfba055 2020-10-07 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 15 1dfba055 2020-10-07 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 16 1dfba055 2020-10-07 stsp  */
 17 1dfba055 2020-10-07 stsp 
 18 1dfba055 2020-10-07 stsp struct diff_range {
 19 1dfba055 2020-10-07 stsp 	int start;
 20 1dfba055 2020-10-07 stsp 	int end;
 21 1dfba055 2020-10-07 stsp };
 22 1dfba055 2020-10-07 stsp 
 23 1dfba055 2020-10-07 stsp /* List of all possible return codes of a diff invocation. */
 24 1dfba055 2020-10-07 stsp #define DIFF_RC_USE_DIFF_ALGO_FALLBACK	-1
 25 1dfba055 2020-10-07 stsp #define DIFF_RC_OK			0
 26 1dfba055 2020-10-07 stsp /* Any positive return values are errno values from sys/errno.h */
 27 1dfba055 2020-10-07 stsp 
 28 1dfba055 2020-10-07 stsp struct diff_atom;
 29 1dfba055 2020-10-07 stsp 
 30 1dfba055 2020-10-07 stsp /* For each file, there is a "root" struct diff_data referencing the entire
 31 1dfba055 2020-10-07 stsp  * file, which the atoms are parsed from. In recursion of diff algorithm, there
 32 1dfba055 2020-10-07 stsp  * may be "child" struct diff_data only referencing a subsection of the file,
 33 1dfba055 2020-10-07 stsp  * re-using the atoms parsing. For "root" structs, atoms_allocated will be
 34 1dfba055 2020-10-07 stsp  * nonzero, indicating that the array of atoms is owned by that struct. For
 35 1dfba055 2020-10-07 stsp  * "child" structs, atoms_allocated == 0, to indicate that the struct is
 36 1dfba055 2020-10-07 stsp  * referencing a subset of atoms. */
 37 1dfba055 2020-10-07 stsp struct diff_data {
 38 1dfba055 2020-10-07 stsp 	FILE *f;		/* if root diff_data and not memory-mapped */
 39 1dfba055 2020-10-07 stsp 	off_t pos;		/* if not memory-mapped */
 40 1dfba055 2020-10-07 stsp 	const uint8_t *data;	/* if memory-mapped */
 41 1dfba055 2020-10-07 stsp 	off_t len;
 42 1dfba055 2020-10-07 stsp 
 43 1dfba055 2020-10-07 stsp 	ARRAYLIST(struct diff_atom) atoms;
 44 1dfba055 2020-10-07 stsp 	struct diff_data *root;
 45 6c8c5d3f 2020-10-12 neels 	struct diff_data *current;
 46 6c8c5d3f 2020-10-12 neels 	void *algo_data;
 47 1dfba055 2020-10-07 stsp 
 48 1dfba055 2020-10-07 stsp 	int diff_flags;
 49 60b6e08b 2020-10-12 neels 
 50 60b6e08b 2020-10-12 neels 	int err;
 51 1dfba055 2020-10-07 stsp };
 52 1dfba055 2020-10-07 stsp 
 53 1dfba055 2020-10-07 stsp #define DIFF_FLAG_IGNORE_WHITESPACE	0x00000001
 54 1dfba055 2020-10-07 stsp 
 55 1dfba055 2020-10-07 stsp void diff_data_free(struct diff_data *diff_data);
 56 1dfba055 2020-10-07 stsp 
 57 1dfba055 2020-10-07 stsp struct diff_chunk;
 58 1dfba055 2020-10-07 stsp typedef ARRAYLIST(struct diff_chunk) diff_chunk_arraylist_t;
 59 1dfba055 2020-10-07 stsp 
 60 1dfba055 2020-10-07 stsp struct diff_result {
 61 1dfba055 2020-10-07 stsp 	int rc;
 62 1dfba055 2020-10-07 stsp 	struct diff_data left;
 63 1dfba055 2020-10-07 stsp 	struct diff_data right;
 64 1dfba055 2020-10-07 stsp 	diff_chunk_arraylist_t chunks;
 65 1dfba055 2020-10-07 stsp };
 66 1dfba055 2020-10-07 stsp 
 67 1dfba055 2020-10-07 stsp struct diff_state;
 68 1dfba055 2020-10-07 stsp 
 69 1dfba055 2020-10-07 stsp /* Signature of a utility function to divide both source files into diff atoms.
 70 1dfba055 2020-10-07 stsp  * It is possible that a (future) algorithm requires both source files to decide
 71 1dfba055 2020-10-07 stsp  * on atom split points, hence this gets both left and right to atomize at the
 72 1dfba055 2020-10-07 stsp  * same time.
 73 1dfba055 2020-10-07 stsp  * An example is diff_atomize_text_by_line() in diff_atomize_text.c.
 74 1dfba055 2020-10-07 stsp  *
 75 1dfba055 2020-10-07 stsp  * func_data: context pointer (free to be used by implementation).
 76 1dfba055 2020-10-07 stsp  * left: struct diff_data with left->data and left->len already set up, and
 77 1dfba055 2020-10-07 stsp  * left->atoms to be created.
 78 1dfba055 2020-10-07 stsp  * right: struct diff_data with right->data and right->len already set up, and
 79 1dfba055 2020-10-07 stsp  * right->atoms to be created.
 80 1dfba055 2020-10-07 stsp  */
 81 1dfba055 2020-10-07 stsp typedef int (*diff_atomize_func_t)(void *func_data,
 82 1dfba055 2020-10-07 stsp 					    struct diff_data *left,
 83 1dfba055 2020-10-07 stsp 					    struct diff_data *right);
 84 1dfba055 2020-10-07 stsp 
 85 1dfba055 2020-10-07 stsp extern int diff_atomize_text_by_line(void *func_data,
 86 1dfba055 2020-10-07 stsp 					      struct diff_data *left,
 87 1dfba055 2020-10-07 stsp 					      struct diff_data *right);
 88 1dfba055 2020-10-07 stsp 
 89 1dfba055 2020-10-07 stsp struct diff_algo_config;
 90 1dfba055 2020-10-07 stsp typedef int (*diff_algo_impl_t)(
 91 1dfba055 2020-10-07 stsp 	const struct diff_algo_config *algo_config, struct diff_state *state);
 92 1dfba055 2020-10-07 stsp 
 93 1dfba055 2020-10-07 stsp /* Form a result with all left-side removed and all right-side added, i.e. no
 94 1dfba055 2020-10-07 stsp  * actual diff algorithm involved. */
 95 1dfba055 2020-10-07 stsp int diff_algo_none(const struct diff_algo_config *algo_config,
 96 0c70b22b 2020-10-11 neels 	struct diff_state *state);
 97 1dfba055 2020-10-07 stsp 
 98 1dfba055 2020-10-07 stsp /* Myers Diff tracing from the start all the way through to the end, requiring
 99 1dfba055 2020-10-07 stsp  * quadratic amounts of memory. This can fail if the required space surpasses
100 1dfba055 2020-10-07 stsp  * algo_config->permitted_state_size. */
101 1dfba055 2020-10-07 stsp extern int diff_algo_myers(const struct diff_algo_config *algo_config,
102 0c70b22b 2020-10-11 neels 	struct diff_state *state);
103 1dfba055 2020-10-07 stsp 
104 1dfba055 2020-10-07 stsp /* Myers "Divide et Impera": tracing forwards from the start and backwards from
105 1dfba055 2020-10-07 stsp  * the end to find a midpoint that divides the problem into smaller chunks.
106 1dfba055 2020-10-07 stsp  * Requires only linear amounts of memory. */
107 1dfba055 2020-10-07 stsp extern int diff_algo_myers_divide(
108 1dfba055 2020-10-07 stsp 	const struct diff_algo_config *algo_config, struct diff_state *state);
109 1dfba055 2020-10-07 stsp 
110 1dfba055 2020-10-07 stsp /* Patience Diff algorithm, which divides a larger diff into smaller chunks. For
111 1dfba055 2020-10-07 stsp  * very specific scenarios, it may lead to a complete diff result by itself, but
112 1dfba055 2020-10-07 stsp  * needs a fallback algo to solve chunks that don't have common-unique atoms. */
113 1dfba055 2020-10-07 stsp extern int diff_algo_patience(
114 1dfba055 2020-10-07 stsp 	const struct diff_algo_config *algo_config, struct diff_state *state);
115 1dfba055 2020-10-07 stsp 
116 1dfba055 2020-10-07 stsp /* Diff algorithms to use, possibly nested. For example:
117 1dfba055 2020-10-07 stsp  *
118 1dfba055 2020-10-07 stsp  * struct diff_algo_config myers, patience, myers_divide;
119 1dfba055 2020-10-07 stsp  *
120 1dfba055 2020-10-07 stsp  * myers = (struct diff_algo_config){
121 1dfba055 2020-10-07 stsp  *         .impl = diff_algo_myers,
122 1dfba055 2020-10-07 stsp  *         .permitted_state_size = 32 * 1024 * 1024,
123 1dfba055 2020-10-07 stsp  *         // When too large, do diff_algo_patience:
124 1dfba055 2020-10-07 stsp  *         .fallback_algo = &patience,
125 1dfba055 2020-10-07 stsp  * };
126 1dfba055 2020-10-07 stsp  *
127 1dfba055 2020-10-07 stsp  * const struct diff_algo_config patience = (struct diff_algo_config){
128 1dfba055 2020-10-07 stsp  * 	.impl = diff_algo_patience,
129 1dfba055 2020-10-07 stsp  * 	// After subdivision, do Patience again:
130 1dfba055 2020-10-07 stsp  * 	.inner_algo = &patience,
131 1dfba055 2020-10-07 stsp  * 	// If subdivision failed, do Myers Divide et Impera:
132 1dfba055 2020-10-07 stsp  * 	.fallback_algo = &myers_then_myers_divide,
133 1dfba055 2020-10-07 stsp  * };
134 1dfba055 2020-10-07 stsp  * 
135 1dfba055 2020-10-07 stsp  * const struct diff_algo_config myers_divide = (struct diff_algo_config){
136 1dfba055 2020-10-07 stsp  * 	.impl = diff_algo_myers_divide,
137 1dfba055 2020-10-07 stsp  * 	// When division succeeded, start from the top:
138 1dfba055 2020-10-07 stsp  * 	.inner_algo = &myers_then_myers_divide,
139 1dfba055 2020-10-07 stsp  * 	// (fallback_algo = NULL implies diff_algo_none).
140 1dfba055 2020-10-07 stsp  * };
141 1dfba055 2020-10-07 stsp  * struct diff_config config = {
142 1dfba055 2020-10-07 stsp  *         .algo = &myers,
143 1dfba055 2020-10-07 stsp  *         ...
144 1dfba055 2020-10-07 stsp  * };
145 1dfba055 2020-10-07 stsp  * diff_main(&config, ...);
146 1dfba055 2020-10-07 stsp  */
147 1dfba055 2020-10-07 stsp struct diff_algo_config {
148 1dfba055 2020-10-07 stsp 	diff_algo_impl_t impl;
149 1dfba055 2020-10-07 stsp 
150 1dfba055 2020-10-07 stsp 	/* Fail this algo if it would use more than this amount of memory, and
151 1dfba055 2020-10-07 stsp 	 * instead use fallback_algo (diff_algo_myers). permitted_state_size ==
152 1dfba055 2020-10-07 stsp 	 * 0 means no limitation. */
153 1dfba055 2020-10-07 stsp 	size_t permitted_state_size;
154 1dfba055 2020-10-07 stsp 
155 1dfba055 2020-10-07 stsp 	/* For algorithms that divide into smaller chunks, use this algorithm to
156 1dfba055 2020-10-07 stsp 	 * solve the divided chunks. */
157 1dfba055 2020-10-07 stsp 	const struct diff_algo_config *inner_algo;
158 1dfba055 2020-10-07 stsp 
159 1dfba055 2020-10-07 stsp 	/* If the algorithm fails (e.g. diff_algo_myers_if_small needs too large
160 1dfba055 2020-10-07 stsp 	 * state, or diff_algo_patience can't find any common-unique atoms),
161 1dfba055 2020-10-07 stsp 	 * then use this algorithm instead. */
162 1dfba055 2020-10-07 stsp 	const struct diff_algo_config *fallback_algo;
163 1dfba055 2020-10-07 stsp };
164 1dfba055 2020-10-07 stsp 
165 1dfba055 2020-10-07 stsp struct diff_config {
166 1dfba055 2020-10-07 stsp 	diff_atomize_func_t atomize_func;
167 1dfba055 2020-10-07 stsp 	void *atomize_func_data;
168 1dfba055 2020-10-07 stsp 
169 1dfba055 2020-10-07 stsp 	const struct diff_algo_config *algo;
170 1dfba055 2020-10-07 stsp 
171 1dfba055 2020-10-07 stsp 	/* How deep to step into subdivisions of a source file, a paranoia /
172 1dfba055 2020-10-07 stsp 	 * safety measure to guard against infinite loops through diff
173 1dfba055 2020-10-07 stsp 	 * algorithms. When the maximum recursion is reached, employ
174 1dfba055 2020-10-07 stsp 	 * diff_algo_none (i.e. remove all left atoms and add all right atoms).
175 1dfba055 2020-10-07 stsp 	 */
176 1dfba055 2020-10-07 stsp 	unsigned int max_recursion_depth;
177 1dfba055 2020-10-07 stsp };
178 1dfba055 2020-10-07 stsp 
179 1dfba055 2020-10-07 stsp struct diff_result *diff_main(const struct diff_config *config,
180 1dfba055 2020-10-07 stsp 			      FILE *left_f, const uint8_t *left_data,
181 1dfba055 2020-10-07 stsp 			      off_t left_len,
182 1dfba055 2020-10-07 stsp 			      FILE *right_f, const uint8_t *right_data,
183 1dfba055 2020-10-07 stsp 			      off_t right_len, int diff_flags);
184 1dfba055 2020-10-07 stsp void diff_result_free(struct diff_result *result);