diff options
Diffstat (limited to 'include')
| -rw-r--r-- | include/arraylist.h | 121 | ||||
| -rw-r--r-- | include/diff_main.h | 264 | ||||
| -rw-r--r-- | include/diff_output.h | 112 |
3 files changed, 497 insertions, 0 deletions
diff --git a/include/arraylist.h b/include/arraylist.h new file mode 100644 index 000000000000..453b71cedd7f --- /dev/null +++ b/include/arraylist.h @@ -0,0 +1,121 @@ +/* Auto-reallocating array for arbitrary member types. */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* Usage: + * + * ARRAYLIST(any_type_t) list; + * // OR + * typedef ARRAYLIST(any_type_t) any_type_list_t; + * any_type_list_t list; + * + * // pass the number of (at first unused) members to add on each realloc: + * ARRAYLIST_INIT(list, 128); + * any_type_t *x; + * while (bar) { + * // This enlarges the allocated array as needed; + * // list.head may change due to realloc: + * ARRAYLIST_ADD(x, list); + * if (!x) + * return ENOMEM; + * *x = random_foo_value; + * } + * for (i = 0; i < list.len; i++) + * printf("%s", foo_to_str(list.head[i])); + * ARRAYLIST_FREE(list); + */ +#define ARRAYLIST(MEMBER_TYPE) \ + struct { \ + MEMBER_TYPE *head; \ + MEMBER_TYPE *p; \ + unsigned int len; \ + unsigned int allocated; \ + unsigned int alloc_blocksize; \ + } + +#define ARRAYLIST_INIT(ARRAY_LIST, ALLOC_BLOCKSIZE) do { \ + (ARRAY_LIST).head = NULL; \ + (ARRAY_LIST).len = 0; \ + (ARRAY_LIST).allocated = 0; \ + (ARRAY_LIST).alloc_blocksize = ALLOC_BLOCKSIZE; \ + } while(0) + +#define ARRAYLIST_ADD(NEW_ITEM_P, ARRAY_LIST) do { \ + if ((ARRAY_LIST).len && !(ARRAY_LIST).allocated) { \ + NEW_ITEM_P = NULL; \ + break; \ + } \ + if ((ARRAY_LIST).head == NULL \ + || (ARRAY_LIST).allocated < (ARRAY_LIST).len + 1) { \ + (ARRAY_LIST).p = recallocarray((ARRAY_LIST).head, \ + (ARRAY_LIST).len, \ + (ARRAY_LIST).allocated + \ + ((ARRAY_LIST).allocated ? \ + (ARRAY_LIST).allocated / 2 : \ + (ARRAY_LIST).alloc_blocksize ? \ + (ARRAY_LIST).alloc_blocksize : 8), \ + sizeof(*(ARRAY_LIST).head)); \ + if ((ARRAY_LIST).p == NULL) { \ + NEW_ITEM_P = NULL; \ + break; \ + } \ + (ARRAY_LIST).allocated += \ + (ARRAY_LIST).allocated ? \ + (ARRAY_LIST).allocated / 2 : \ + (ARRAY_LIST).alloc_blocksize ? \ + (ARRAY_LIST).alloc_blocksize : 8, \ + (ARRAY_LIST).head = (ARRAY_LIST).p; \ + (ARRAY_LIST).p = NULL; \ + }; \ + if ((ARRAY_LIST).head == NULL \ + || (ARRAY_LIST).allocated < (ARRAY_LIST).len + 1) { \ + NEW_ITEM_P = NULL; \ + break; \ + } \ + (NEW_ITEM_P) = &(ARRAY_LIST).head[(ARRAY_LIST).len]; \ + (ARRAY_LIST).len++; \ + } while (0) + +#define ARRAYLIST_INSERT(NEW_ITEM_P, ARRAY_LIST, AT_IDX) do { \ + int _at_idx = (AT_IDX); \ + ARRAYLIST_ADD(NEW_ITEM_P, ARRAY_LIST); \ + if ((NEW_ITEM_P) \ + && _at_idx >= 0 \ + && _at_idx < (ARRAY_LIST).len) { \ + memmove(&(ARRAY_LIST).head[_at_idx + 1], \ + &(ARRAY_LIST).head[_at_idx], \ + ((ARRAY_LIST).len - 1 - _at_idx) \ + * sizeof(*(ARRAY_LIST).head)); \ + (NEW_ITEM_P) = &(ARRAY_LIST).head[_at_idx]; \ + }; \ + } while (0) + +#define ARRAYLIST_CLEAR(ARRAY_LIST) \ + (ARRAY_LIST).len = 0 + +#define ARRAYLIST_FREE(ARRAY_LIST) \ + do { \ + if ((ARRAY_LIST).head && (ARRAY_LIST).allocated) \ + free((ARRAY_LIST).head); \ + ARRAYLIST_INIT(ARRAY_LIST, (ARRAY_LIST).alloc_blocksize); \ + } while(0) + +#define ARRAYLIST_FOREACH(ITEM_P, ARRAY_LIST) \ + for ((ITEM_P) = (ARRAY_LIST).head; \ + (ITEM_P) - (ARRAY_LIST).head < (ARRAY_LIST).len; \ + (ITEM_P)++) + +#define ARRAYLIST_IDX(ITEM_P, ARRAY_LIST) ((ITEM_P) - (ARRAY_LIST).head) diff --git a/include/diff_main.h b/include/diff_main.h new file mode 100644 index 000000000000..04a6c6e748c9 --- /dev/null +++ b/include/diff_main.h @@ -0,0 +1,264 @@ +/* Generic infrastructure to implement various diff algorithms. */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +struct diff_range { + int start; + int end; +}; + +/* List of all possible return codes of a diff invocation. */ +#define DIFF_RC_USE_DIFF_ALGO_FALLBACK -1 +#define DIFF_RC_OK 0 +/* Any positive return values are errno values from sys/errno.h */ + +struct diff_atom { + struct diff_data *root; /* back pointer to root diff data */ + + off_t pos; /* set whether memory-mapped or not */ + const uint8_t *at; /* only set if memory-mapped */ + off_t len; + + /* This hash is just a very cheap speed up for finding *mismatching* + * atoms. When hashes match, we still need to compare entire atoms to + * find out whether they are indeed identical or not. + * Calculated over all atom bytes with diff_atom_hash_update(). */ + unsigned int hash; +}; + +/* Mix another atom_byte into the provided hash value and return the result. + * The hash value passed in for the first byte of the atom must be zero. */ +unsigned int +diff_atom_hash_update(unsigned int hash, unsigned char atom_byte); + +/* Compare two atoms for equality. Return 0 on success, or errno on failure. + * Set cmp to -1, 0, or 1, just like strcmp(). */ +int +diff_atom_cmp(int *cmp, + const struct diff_atom *left, + const struct diff_atom *right); + + +/* The atom's index in the entire file. For atoms divided by lines of text, this + * yields the line number (starting with 0). Also works for diff_data that + * reference only a subsection of a file, always reflecting the global position + * in the file (and not the relative position within the subsection). */ +#define diff_atom_root_idx(DIFF_DATA, ATOM) \ + ((ATOM) && ((ATOM) >= (DIFF_DATA)->root->atoms.head) \ + ? (unsigned int)((ATOM) - ((DIFF_DATA)->root->atoms.head)) \ + : (DIFF_DATA)->root->atoms.len) + +/* The atom's index within DIFF_DATA. For atoms divided by lines of text, this + * yields the line number (starting with 0). */ +#define diff_atom_idx(DIFF_DATA, ATOM) \ + ((ATOM) && ((ATOM) >= (DIFF_DATA)->atoms.head) \ + ? (unsigned int)((ATOM) - ((DIFF_DATA)->atoms.head)) \ + : (DIFF_DATA)->atoms.len) + +#define foreach_diff_atom(ATOM, FIRST_ATOM, COUNT) \ + for ((ATOM) = (FIRST_ATOM); \ + (ATOM) \ + && ((ATOM) >= (FIRST_ATOM)) \ + && ((ATOM) - (FIRST_ATOM) < (COUNT)); \ + (ATOM)++) + +#define diff_data_foreach_atom(ATOM, DIFF_DATA) \ + foreach_diff_atom(ATOM, (DIFF_DATA)->atoms.head, (DIFF_DATA)->atoms.len) + +#define diff_data_foreach_atom_from(FROM, ATOM, DIFF_DATA) \ + for ((ATOM) = (FROM); \ + (ATOM) \ + && ((ATOM) >= (DIFF_DATA)->atoms.head) \ + && ((ATOM) - (DIFF_DATA)->atoms.head < (DIFF_DATA)->atoms.len); \ + (ATOM)++) + +#define diff_data_foreach_atom_backwards_from(FROM, ATOM, DIFF_DATA) \ + for ((ATOM) = (FROM); \ + (ATOM) \ + && ((ATOM) >= (DIFF_DATA)->atoms.head) \ + && ((ATOM) - (DIFF_DATA)->atoms.head >= 0); \ + (ATOM)--) + +/* For each file, there is a "root" struct diff_data referencing the entire + * file, which the atoms are parsed from. In recursion of diff algorithm, there + * may be "child" struct diff_data only referencing a subsection of the file, + * re-using the atoms parsing. For "root" structs, atoms_allocated will be + * nonzero, indicating that the array of atoms is owned by that struct. For + * "child" structs, atoms_allocated == 0, to indicate that the struct is + * referencing a subset of atoms. */ +struct diff_data { + FILE *f; /* if root diff_data and not memory-mapped */ + off_t pos; /* if not memory-mapped */ + const uint8_t *data; /* if memory-mapped */ + off_t len; + + int atomizer_flags; + ARRAYLIST(struct diff_atom) atoms; + struct diff_data *root; + struct diff_data *current; + void *algo_data; + + int diff_flags; + + int err; +}; + +/* Flags set by file atomizer. */ +#define DIFF_ATOMIZER_FOUND_BINARY_DATA 0x00000001 + +/* Flags set by caller of diff_main(). */ +#define DIFF_FLAG_IGNORE_WHITESPACE 0x00000001 +#define DIFF_FLAG_SHOW_PROTOTYPES 0x00000002 +#define DIFF_FLAG_FORCE_TEXT_DATA 0x00000004 + +void diff_data_free(struct diff_data *diff_data); + +struct diff_chunk; +typedef ARRAYLIST(struct diff_chunk) diff_chunk_arraylist_t; + +struct diff_result { + int rc; + + /* + * Pointers to diff data passed in via diff_main. + * Do not free these diff_data before freeing the diff_result struct. + */ + struct diff_data *left; + struct diff_data *right; + + diff_chunk_arraylist_t chunks; +}; + +enum diff_chunk_type { + CHUNK_EMPTY, + CHUNK_PLUS, + CHUNK_MINUS, + CHUNK_SAME, + CHUNK_ERROR, +}; + +enum diff_chunk_type diff_chunk_type(const struct diff_chunk *c); + +struct diff_state; + +/* Signature of a utility function to divide a file into diff atoms. + * An example is diff_atomize_text_by_line() in diff_atomize_text.c. + * + * func_data: context pointer (free to be used by implementation). + * d: struct diff_data with d->data and d->len already set up, and + * d->atoms to be created and d->atomizer_flags to be set up. + */ +typedef int (*diff_atomize_func_t)(void *func_data, struct diff_data *d); + +extern int diff_atomize_text_by_line(void *func_data, struct diff_data *d); + +struct diff_algo_config; +typedef int (*diff_algo_impl_t)( + const struct diff_algo_config *algo_config, struct diff_state *state); + +/* Form a result with all left-side removed and all right-side added, i.e. no + * actual diff algorithm involved. */ +int diff_algo_none(const struct diff_algo_config *algo_config, + struct diff_state *state); + +/* Myers Diff tracing from the start all the way through to the end, requiring + * quadratic amounts of memory. This can fail if the required space surpasses + * algo_config->permitted_state_size. */ +extern int diff_algo_myers(const struct diff_algo_config *algo_config, + struct diff_state *state); + +/* Myers "Divide et Impera": tracing forwards from the start and backwards from + * the end to find a midpoint that divides the problem into smaller chunks. + * Requires only linear amounts of memory. */ +extern int diff_algo_myers_divide( + const struct diff_algo_config *algo_config, struct diff_state *state); + +/* Patience Diff algorithm, which divides a larger diff into smaller chunks. For + * very specific scenarios, it may lead to a complete diff result by itself, but + * needs a fallback algo to solve chunks that don't have common-unique atoms. */ +extern int diff_algo_patience( + const struct diff_algo_config *algo_config, struct diff_state *state); + +/* Diff algorithms to use, possibly nested. For example: + * + * struct diff_algo_config myers, patience, myers_divide; + * + * myers = (struct diff_algo_config){ + * .impl = diff_algo_myers, + * .permitted_state_size = 32 * 1024 * 1024, + * // When too large, do diff_algo_patience: + * .fallback_algo = &patience, + * }; + * + * const struct diff_algo_config patience = (struct diff_algo_config){ + * .impl = diff_algo_patience, + * // After subdivision, do Patience again: + * .inner_algo = &patience, + * // If subdivision failed, do Myers Divide et Impera: + * .fallback_algo = &myers_then_myers_divide, + * }; + * + * const struct diff_algo_config myers_divide = (struct diff_algo_config){ + * .impl = diff_algo_myers_divide, + * // When division succeeded, start from the top: + * .inner_algo = &myers_then_myers_divide, + * // (fallback_algo = NULL implies diff_algo_none). + * }; + * struct diff_config config = { + * .algo = &myers, + * ... + * }; + * diff_main(&config, ...); + */ +struct diff_algo_config { + diff_algo_impl_t impl; + + /* Fail this algo if it would use more than this amount of memory, and + * instead use fallback_algo (diff_algo_myers). permitted_state_size == + * 0 means no limitation. */ + size_t permitted_state_size; + + /* For algorithms that divide into smaller chunks, use this algorithm to + * solve the divided chunks. */ + const struct diff_algo_config *inner_algo; + + /* If the algorithm fails (e.g. diff_algo_myers_if_small needs too large + * state, or diff_algo_patience can't find any common-unique atoms), + * then use this algorithm instead. */ + const struct diff_algo_config *fallback_algo; +}; + +struct diff_config { + diff_atomize_func_t atomize_func; + void *atomize_func_data; + + const struct diff_algo_config *algo; + + /* How deep to step into subdivisions of a source file, a paranoia / + * safety measure to guard against infinite loops through diff + * algorithms. When the maximum recursion is reached, employ + * diff_algo_none (i.e. remove all left atoms and add all right atoms). + */ + unsigned int max_recursion_depth; +}; + +int diff_atomize_file(struct diff_data *d, const struct diff_config *config, + FILE *f, const uint8_t *data, off_t len, int diff_flags); +struct diff_result *diff_main(const struct diff_config *config, + struct diff_data *left, + struct diff_data *right); +void diff_result_free(struct diff_result *result); +int diff_result_contains_printable_chunks(struct diff_result *result); diff --git a/include/diff_output.h b/include/diff_output.h new file mode 100644 index 000000000000..d2568c5a2b50 --- /dev/null +++ b/include/diff_output.h @@ -0,0 +1,112 @@ +/* Diff output generators and invocation shims. */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +struct diff_input_info { + const char *left_path; + const char *right_path; + + /* Set by caller of diff_output_* functions. */ + int flags; +#define DIFF_INPUT_LEFT_NONEXISTENT 0x00000001 +#define DIFF_INPUT_RIGHT_NONEXISTENT 0x00000002 +}; + +struct diff_output_info { + /* + * Byte offset to each line in the generated output file. + * The total number of lines in the file is line_offsets.len - 1. + * The last offset in this array corresponds to end-of-file. + */ + ARRAYLIST(off_t) line_offsets; + /* + * Type (i.e., context, minus, plus) of each line generated by the diff. + * nb. 0x00 to 0x3b reserved for client-defined line types. + */ + ARRAYLIST(uint8_t) line_types; +#define DIFF_LINE_HUNK 0x3c +#define DIFF_LINE_MINUS 0x3d +#define DIFF_LINE_PLUS 0x3e +#define DIFF_LINE_CONTEXT 0x3f +#define DIFF_LINE_NONE 0x40 /* binary or no EOF newline msg, etc. */ +}; + +void diff_output_info_free(struct diff_output_info *output_info); + +struct diff_chunk_context { + struct diff_range chunk; + struct diff_range left, right; +}; + +int diff_output_plain(struct diff_output_info **output_info, FILE *dest, + const struct diff_input_info *info, + const struct diff_result *result, + int hunk_headers_only); +int diff_output_unidiff(struct diff_output_info **output_info, + FILE *dest, const struct diff_input_info *info, + const struct diff_result *result, + unsigned int context_lines); +int diff_output_edscript(struct diff_output_info **output_info, + FILE *dest, const struct diff_input_info *info, + const struct diff_result *result); +int diff_chunk_get_left_start(const struct diff_chunk *c, + const struct diff_result *r, + int context_lines); +int diff_chunk_get_left_end(const struct diff_chunk *c, + const struct diff_result *r, + int context_lines); +int diff_chunk_get_right_start(const struct diff_chunk *c, + const struct diff_result *r, + int context_lines); +int diff_chunk_get_right_end(const struct diff_chunk *c, + const struct diff_result *r, + int context_lines); +off_t diff_chunk_get_left_start_pos(const struct diff_chunk *c); +off_t diff_chunk_get_right_start_pos(const struct diff_chunk *c); +struct diff_chunk *diff_chunk_get(const struct diff_result *r, int chunk_idx); +int diff_chunk_get_left_count(struct diff_chunk *c); +int diff_chunk_get_right_count(struct diff_chunk *c); +void diff_chunk_context_get(struct diff_chunk_context *cc, + const struct diff_result *r, + int chunk_idx, int context_lines); +void diff_chunk_context_load_change(struct diff_chunk_context *cc, + int *nchunks_used, + struct diff_result *result, + int start_chunk_idx, + int context_lines); + +struct diff_output_unidiff_state; +struct diff_output_unidiff_state *diff_output_unidiff_state_alloc(void); +void diff_output_unidiff_state_reset(struct diff_output_unidiff_state *state); +void diff_output_unidiff_state_free(struct diff_output_unidiff_state *state); +int diff_output_unidiff_chunk(struct diff_output_info **output_info, FILE *dest, + struct diff_output_unidiff_state *state, + const struct diff_input_info *info, + const struct diff_result *result, + const struct diff_chunk_context *cc); +int diff_output_chunk_left_version(struct diff_output_info **output_info, + FILE *dest, + const struct diff_input_info *info, + const struct diff_result *result, + const struct diff_chunk_context *cc); +int diff_output_chunk_right_version(struct diff_output_info **output_info, + FILE *dest, + const struct diff_input_info *info, + const struct diff_result *result, + const struct diff_chunk_context *cc); + +const char *diff_output_get_label_left(const struct diff_input_info *info); +const char *diff_output_get_label_right(const struct diff_input_info *info); |