113341Sjkh/* Generic infrastructure to implement various diff algorithms. */ 213341Sjkh/* 375328Sobrien * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> 475328Sobrien * 575328Sobrien * Permission to use, copy, modify, and distribute this software for any 613341Sjkh * purpose with or without fee is hereby granted, provided that the above 713341Sjkh * copyright notice and this permission notice appear in all copies. 813341Sjkh * 913341Sjkh * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 1039556Sjkh * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 1113341Sjkh * 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. 16 */ 17 18#ifndef MAX 19#define MAX(A,B) ((A)>(B)?(A):(B)) 20#endif 21#ifndef MIN 22#define MIN(A,B) ((A)<(B)?(A):(B)) 23#endif 24 25static inline bool 26diff_range_empty(const struct diff_range *r) 27{ 28 return r->start == r->end; 29} 30 31static inline bool 32diff_ranges_touch(const struct diff_range *a, const struct diff_range *b) 33{ 34 return (a->end >= b->start) && (a->start <= b->end); 35} 36 37static inline void 38diff_ranges_merge(struct diff_range *a, const struct diff_range *b) 39{ 40 *a = (struct diff_range){ 41 .start = MIN(a->start, b->start), 42 .end = MAX(a->end, b->end), 43 }; 44} 45 46static inline int 47diff_range_len(const struct diff_range *r) 48{ 49 if (!r) 50 return 0; 51 return r->end - r->start; 52} 53 54/* Indicate whether two given diff atoms match. */ 55int 56diff_atom_same(bool *same, 57 const struct diff_atom *left, 58 const struct diff_atom *right); 59 60/* A diff chunk represents a set of atoms on the left and/or a set of atoms on 61 * the right. 62 * 63 * If solved == false: 64 * The diff algorithm has divided the source file, and this is a chunk that the 65 * inner_algo should run on next. 66 * The lines on the left should be diffed against the lines on the right. 67 * (If there are no left lines or no right lines, it implies solved == true, 68 * because there is nothing to diff.) 69 * 70 * If solved == true: 71 * If there are only left atoms, it is a chunk removing atoms from the left ("a 72 * minus chunk"). 73 * If there are only right atoms, it is a chunk adding atoms from the right ("a 74 * plus chunk"). 75 * If there are both left and right lines, it is a chunk of equal content on 76 * both sides, and left_count == right_count: 77 * 78 * - foo } 79 * - bar }-- diff_chunk{ left_start = &left.atoms.head[0], left_count = 3, 80 * - baz } right_start = NULL, right_count = 0 } 81 * moo } 82 * goo }-- diff_chunk{ left_start = &left.atoms.head[3], left_count = 3, 83 * zoo } right_start = &right.atoms.head[0], right_count = 3 } 84 * +loo } 85 * +roo }-- diff_chunk{ left_start = NULL, left_count = 0, 86 * +too } right_start = &right.atoms.head[3], right_count = 3 } 87 * 88 */ 89struct diff_chunk { 90 bool solved; 91 struct diff_atom *left_start; 92 unsigned int left_count; 93 struct diff_atom *right_start; 94 unsigned int right_count; 95}; 96 97#define DIFF_RESULT_ALLOC_BLOCKSIZE 128 98 99struct diff_chunk_context; 100 101bool 102diff_chunk_context_empty(const struct diff_chunk_context *cc); 103 104bool 105diff_chunk_contexts_touch(const struct diff_chunk_context *cc, 106 const struct diff_chunk_context *other); 107 108void 109diff_chunk_contexts_merge(struct diff_chunk_context *cc, 110 const struct diff_chunk_context *other); 111 112struct diff_state { 113 /* The final result passed to the original diff caller. */ 114 struct diff_result *result; 115 116 /* The root diff_data is in result->left,right, these are (possibly) 117 * subsections of the root data. */ 118 struct diff_data left; 119 struct diff_data right; 120 121 unsigned int recursion_depth_left; 122 123 /* Remaining chunks from one diff algorithm pass, if any solved == false 124 * chunks came up. */ 125 diff_chunk_arraylist_t temp_result; 126 127 /* State buffer used by Myers algorithm. */ 128 int *kd_buf; 129 size_t kd_buf_size; /* in units of sizeof(int), not bytes */ 130}; 131 132struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved, 133 struct diff_atom *left_start, 134 unsigned int left_count, 135 struct diff_atom *right_start, 136 unsigned int right_count); 137 138struct diff_output_info; 139 140int diff_output_lines(struct diff_output_info *output_info, FILE *dest, 141 const char *prefix, struct diff_atom *start_atom, 142 unsigned int count); 143 144int diff_output_trailing_newline_msg(struct diff_output_info *outinfo, 145 FILE *dest, 146 const struct diff_chunk *c); 147#define DIFF_FUNCTION_CONTEXT_SIZE 55 148int diff_output_match_function_prototype(char *prototype, size_t prototype_size, 149 int *last_prototype_idx, 150 const struct diff_result *result, 151 int chunk_start_line); 152 153struct diff_output_info *diff_output_info_alloc(void); 154 155void 156diff_data_init_subsection(struct diff_data *d, struct diff_data *parent, 157 struct diff_atom *from_atom, unsigned int atoms_count); 158