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.
19 fe621944 2020-11-10 stsp #define MAX(A,B) ((A)>(B)?(A):(B))
22 fe621944 2020-11-10 stsp #define MIN(A,B) ((A)<(B)?(A):(B))
25 fe621944 2020-11-10 stsp static inline bool
26 fe621944 2020-11-10 stsp diff_range_empty(const struct diff_range *r)
28 fe621944 2020-11-10 stsp return r->start == r->end;
31 fe621944 2020-11-10 stsp static inline bool
32 fe621944 2020-11-10 stsp diff_ranges_touch(const struct diff_range *a, const struct diff_range *b)
34 fe621944 2020-11-10 stsp return (a->end >= b->start) && (a->start <= b->end);
37 fe621944 2020-11-10 stsp static inline void
38 fe621944 2020-11-10 stsp diff_ranges_merge(struct diff_range *a, const struct diff_range *b)
40 fe621944 2020-11-10 stsp *a = (struct diff_range){
41 fe621944 2020-11-10 stsp .start = MIN(a->start, b->start),
42 fe621944 2020-11-10 stsp .end = MAX(a->end, b->end),
46 fe621944 2020-11-10 stsp static inline int
47 fe621944 2020-11-10 stsp diff_range_len(const struct diff_range *r)
51 fe621944 2020-11-10 stsp return r->end - r->start;
54 fe621944 2020-11-10 stsp /* Indicate whether two given diff atoms match. */
56 fe621944 2020-11-10 stsp diff_atom_same(bool *same,
57 fe621944 2020-11-10 stsp const struct diff_atom *left,
58 fe621944 2020-11-10 stsp const struct diff_atom *right);
60 fe621944 2020-11-10 stsp /* A diff chunk represents a set of atoms on the left and/or a set of atoms on
61 fe621944 2020-11-10 stsp * the right.
63 fe621944 2020-11-10 stsp * If solved == false:
64 fe621944 2020-11-10 stsp * The diff algorithm has divided the source file, and this is a chunk that the
65 fe621944 2020-11-10 stsp * inner_algo should run on next.
66 fe621944 2020-11-10 stsp * The lines on the left should be diffed against the lines on the right.
67 fe621944 2020-11-10 stsp * (If there are no left lines or no right lines, it implies solved == true,
68 fe621944 2020-11-10 stsp * because there is nothing to diff.)
70 fe621944 2020-11-10 stsp * If solved == true:
71 fe621944 2020-11-10 stsp * If there are only left atoms, it is a chunk removing atoms from the left ("a
72 fe621944 2020-11-10 stsp * minus chunk").
73 fe621944 2020-11-10 stsp * If there are only right atoms, it is a chunk adding atoms from the right ("a
74 fe621944 2020-11-10 stsp * plus chunk").
75 fe621944 2020-11-10 stsp * If there are both left and right lines, it is a chunk of equal content on
76 fe621944 2020-11-10 stsp * both sides, and left_count == right_count:
79 fe621944 2020-11-10 stsp * - bar }-- diff_chunk{ left_start = &left.atoms.head[0], left_count = 3,
80 fe621944 2020-11-10 stsp * - baz } right_start = NULL, right_count = 0 }
82 fe621944 2020-11-10 stsp * goo }-- diff_chunk{ left_start = &left.atoms.head[3], left_count = 3,
83 fe621944 2020-11-10 stsp * zoo } right_start = &right.atoms.head[0], right_count = 3 }
85 fe621944 2020-11-10 stsp * +roo }-- diff_chunk{ left_start = NULL, left_count = 0,
86 fe621944 2020-11-10 stsp * +too } right_start = &right.atoms.head[3], right_count = 3 }
89 fe621944 2020-11-10 stsp struct diff_chunk {
90 fe621944 2020-11-10 stsp bool solved;
91 fe621944 2020-11-10 stsp struct diff_atom *left_start;
92 fe621944 2020-11-10 stsp unsigned int left_count;
93 fe621944 2020-11-10 stsp struct diff_atom *right_start;
94 fe621944 2020-11-10 stsp unsigned int right_count;
97 fe621944 2020-11-10 stsp #define DIFF_RESULT_ALLOC_BLOCKSIZE 128
99 fe621944 2020-11-10 stsp enum diff_chunk_type {
100 fe621944 2020-11-10 stsp CHUNK_EMPTY,
101 fe621944 2020-11-10 stsp CHUNK_PLUS,
102 fe621944 2020-11-10 stsp CHUNK_MINUS,
103 fe621944 2020-11-10 stsp CHUNK_SAME,
104 fe621944 2020-11-10 stsp CHUNK_ERROR,
107 fe621944 2020-11-10 stsp static inline enum diff_chunk_type
108 fe621944 2020-11-10 stsp diff_chunk_type(const struct diff_chunk *chunk)
110 fe621944 2020-11-10 stsp if (!chunk->left_count && !chunk->right_count)
111 fe621944 2020-11-10 stsp return CHUNK_EMPTY;
112 fe621944 2020-11-10 stsp if (!chunk->solved)
113 fe621944 2020-11-10 stsp return CHUNK_ERROR;
114 fe621944 2020-11-10 stsp if (!chunk->right_count)
115 fe621944 2020-11-10 stsp return CHUNK_MINUS;
116 fe621944 2020-11-10 stsp if (!chunk->left_count)
117 fe621944 2020-11-10 stsp return CHUNK_PLUS;
118 fe621944 2020-11-10 stsp if (chunk->left_count != chunk->right_count)
119 fe621944 2020-11-10 stsp return CHUNK_ERROR;
120 fe621944 2020-11-10 stsp return CHUNK_SAME;
123 fe621944 2020-11-10 stsp struct diff_chunk_context;
126 fe621944 2020-11-10 stsp diff_chunk_context_empty(const struct diff_chunk_context *cc);
129 fe621944 2020-11-10 stsp diff_chunk_contexts_touch(const struct diff_chunk_context *cc,
130 fe621944 2020-11-10 stsp const struct diff_chunk_context *other);
133 fe621944 2020-11-10 stsp diff_chunk_contexts_merge(struct diff_chunk_context *cc,
134 fe621944 2020-11-10 stsp const struct diff_chunk_context *other);
136 fe621944 2020-11-10 stsp struct diff_state {
137 fe621944 2020-11-10 stsp /* The final result passed to the original diff caller. */
138 fe621944 2020-11-10 stsp struct diff_result *result;
140 fe621944 2020-11-10 stsp /* The root diff_data is in result->left,right, these are (possibly)
141 fe621944 2020-11-10 stsp * subsections of the root data. */
142 fe621944 2020-11-10 stsp struct diff_data left;
143 fe621944 2020-11-10 stsp struct diff_data right;
145 fe621944 2020-11-10 stsp unsigned int recursion_depth_left;
147 fe621944 2020-11-10 stsp /* Remaining chunks from one diff algorithm pass, if any solved == false
148 fe621944 2020-11-10 stsp * chunks came up. */
149 fe621944 2020-11-10 stsp diff_chunk_arraylist_t temp_result;
151 fe621944 2020-11-10 stsp /* State buffer used by Myers algorithm. */
152 fe621944 2020-11-10 stsp int *kd_buf;
153 fe621944 2020-11-10 stsp size_t kd_buf_size; /* in units of sizeof(int), not bytes */
156 fe621944 2020-11-10 stsp struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved,
157 fe621944 2020-11-10 stsp struct diff_atom *left_start,
158 fe621944 2020-11-10 stsp unsigned int left_count,
159 fe621944 2020-11-10 stsp struct diff_atom *right_start,
160 fe621944 2020-11-10 stsp unsigned int right_count);
162 fe621944 2020-11-10 stsp struct diff_output_info;
164 fe621944 2020-11-10 stsp int diff_output_lines(struct diff_output_info *output_info, FILE *dest,
165 fe621944 2020-11-10 stsp const char *prefix, struct diff_atom *start_atom,
166 fe621944 2020-11-10 stsp unsigned int count);
168 fe621944 2020-11-10 stsp int diff_output_trailing_newline_msg(struct diff_output_info *outinfo,
169 fe621944 2020-11-10 stsp FILE *dest,
170 fe621944 2020-11-10 stsp const struct diff_chunk *c);
171 f3b2b552 2020-12-10 stsp #define DIFF_FUNCTION_CONTEXT_SIZE 55
172 f3b2b552 2020-12-10 stsp int diff_output_match_function_prototype(char *prototype, size_t prototype_size,
173 f3b2b552 2020-12-10 stsp int *last_prototype_idx,
174 fe621944 2020-11-10 stsp const struct diff_result *result,
175 579042a9 2022-09-23 stsp const struct diff_chunk_context *cc,
176 579042a9 2022-09-23 stsp unsigned int ncontext);
178 fe621944 2020-11-10 stsp struct diff_output_info *diff_output_info_alloc(void);
181 fe621944 2020-11-10 stsp diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
182 fe621944 2020-11-10 stsp struct diff_atom *from_atom, unsigned int atoms_count);
