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