1 /* Generic infrastructure to implement various diff algorithms. */ 2 /* 3 * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> 4 * 5 * Permission to use, copy, modify, and distribute this software for any 6 * purpose with or without fee is hereby granted, provided that the above 7 * copyright notice and this permission notice appear in all copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 * 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 25 static inline bool 26 diff_range_empty(const struct diff_range *r) 27 { 28 return r->start == r->end; 29 } 30 31 static inline bool 32 diff_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 37 static inline void 38 diff_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 46 static inline int 47 diff_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. */ 55 int 56 diff_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 */ 89 struct 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 99 struct diff_chunk_context; 100 101 bool 102 diff_chunk_context_empty(const struct diff_chunk_context *cc); 103 104 bool 105 diff_chunk_contexts_touch(const struct diff_chunk_context *cc, 106 const struct diff_chunk_context *other); 107 108 void 109 diff_chunk_contexts_merge(struct diff_chunk_context *cc, 110 const struct diff_chunk_context *other); 111 112 struct 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 132 struct 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 138 struct diff_output_info; 139 140 int 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 144 int 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 148 int diff_output_match_function_prototype(char *prototype, size_t prototype_size, 149 int *last_prototype_idx, 150 const struct diff_result *result, 151 const struct diff_chunk_context *cc); 152 153 struct diff_output_info *diff_output_info_alloc(void); 154 155 void 156 diff_data_init_subsection(struct diff_data *d, struct diff_data *parent, 157 struct diff_atom *from_atom, unsigned int atoms_count); 158