Blame


1 85ab4559 2020-09-22 stsp /* Generic infrastructure to implement various diff algorithms. */
2 85ab4559 2020-09-22 stsp /*
3 85ab4559 2020-09-22 stsp * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
4 85ab4559 2020-09-22 stsp *
5 85ab4559 2020-09-22 stsp * Permission to use, copy, modify, and distribute this software for any
6 85ab4559 2020-09-22 stsp * purpose with or without fee is hereby granted, provided that the above
7 85ab4559 2020-09-22 stsp * copyright notice and this permission notice appear in all copies.
8 85ab4559 2020-09-22 stsp *
9 85ab4559 2020-09-22 stsp * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 85ab4559 2020-09-22 stsp * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 85ab4559 2020-09-22 stsp * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 85ab4559 2020-09-22 stsp * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 85ab4559 2020-09-22 stsp * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 85ab4559 2020-09-22 stsp * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 85ab4559 2020-09-22 stsp * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 85ab4559 2020-09-22 stsp */
17 85ab4559 2020-09-22 stsp
18 85ab4559 2020-09-22 stsp #ifndef MAX
19 85ab4559 2020-09-22 stsp #define MAX(A,B) ((A)>(B)?(A):(B))
20 85ab4559 2020-09-22 stsp #endif
21 85ab4559 2020-09-22 stsp #ifndef MIN
22 85ab4559 2020-09-22 stsp #define MIN(A,B) ((A)<(B)?(A):(B))
23 85ab4559 2020-09-22 stsp #endif
24 85ab4559 2020-09-22 stsp
25 85ab4559 2020-09-22 stsp static inline bool
26 85ab4559 2020-09-22 stsp diff_range_empty(const struct diff_range *r)
27 85ab4559 2020-09-22 stsp {
28 85ab4559 2020-09-22 stsp return r->start == r->end;
29 85ab4559 2020-09-22 stsp }
30 85ab4559 2020-09-22 stsp
31 85ab4559 2020-09-22 stsp static inline bool
32 85ab4559 2020-09-22 stsp diff_ranges_touch(const struct diff_range *a, const struct diff_range *b)
33 85ab4559 2020-09-22 stsp {
34 85ab4559 2020-09-22 stsp return (a->end >= b->start) && (a->start <= b->end);
35 85ab4559 2020-09-22 stsp }
36 85ab4559 2020-09-22 stsp
37 85ab4559 2020-09-22 stsp static inline void
38 85ab4559 2020-09-22 stsp diff_ranges_merge(struct diff_range *a, const struct diff_range *b)
39 85ab4559 2020-09-22 stsp {
40 85ab4559 2020-09-22 stsp *a = (struct diff_range){
41 85ab4559 2020-09-22 stsp .start = MIN(a->start, b->start),
42 85ab4559 2020-09-22 stsp .end = MAX(a->end, b->end),
43 85ab4559 2020-09-22 stsp };
44 85ab4559 2020-09-22 stsp }
45 85ab4559 2020-09-22 stsp
46 85ab4559 2020-09-22 stsp static inline int
47 85ab4559 2020-09-22 stsp diff_range_len(const struct diff_range *r)
48 85ab4559 2020-09-22 stsp {
49 85ab4559 2020-09-22 stsp if (!r)
50 85ab4559 2020-09-22 stsp return 0;
51 85ab4559 2020-09-22 stsp return r->end - r->start;
52 85ab4559 2020-09-22 stsp }
53 85ab4559 2020-09-22 stsp
54 85ab4559 2020-09-22 stsp /* List of all possible return codes of a diff invocation. */
55 85ab4559 2020-09-22 stsp #define DIFF_RC_USE_DIFF_ALGO_FALLBACK -1
56 85ab4559 2020-09-22 stsp #define DIFF_RC_OK 0
57 85ab4559 2020-09-22 stsp /* Any positive return values are errno values from sys/errno.h */
58 85ab4559 2020-09-22 stsp
59 85ab4559 2020-09-22 stsp /* Indicate whether two given diff atoms match. */
60 85ab4559 2020-09-22 stsp int
61 85ab4559 2020-09-22 stsp diff_atom_same(bool *same,
62 85ab4559 2020-09-22 stsp const struct diff_atom *left,
63 85ab4559 2020-09-22 stsp const struct diff_atom *right);
64 85ab4559 2020-09-22 stsp
65 85ab4559 2020-09-22 stsp /* A diff chunk represents a set of atoms on the left and/or a set of atoms on
66 85ab4559 2020-09-22 stsp * the right.
67 85ab4559 2020-09-22 stsp *
68 85ab4559 2020-09-22 stsp * If solved == false:
69 85ab4559 2020-09-22 stsp * The diff algorithm has divided the source file, and this is a chunk that the
70 85ab4559 2020-09-22 stsp * inner_algo should run on next.
71 85ab4559 2020-09-22 stsp * The lines on the left should be diffed against the lines on the right.
72 85ab4559 2020-09-22 stsp * (If there are no left lines or no right lines, it implies solved == true,
73 85ab4559 2020-09-22 stsp * because there is nothing to diff.)
74 85ab4559 2020-09-22 stsp *
75 85ab4559 2020-09-22 stsp * If solved == true:
76 85ab4559 2020-09-22 stsp * If there are only left atoms, it is a chunk removing atoms from the left ("a
77 85ab4559 2020-09-22 stsp * minus chunk").
78 85ab4559 2020-09-22 stsp * If there are only right atoms, it is a chunk adding atoms from the right ("a
79 85ab4559 2020-09-22 stsp * plus chunk").
80 85ab4559 2020-09-22 stsp * If there are both left and right lines, it is a chunk of equal content on
81 85ab4559 2020-09-22 stsp * both sides, and left_count == right_count:
82 85ab4559 2020-09-22 stsp *
83 85ab4559 2020-09-22 stsp * - foo }
84 85ab4559 2020-09-22 stsp * - bar }-- diff_chunk{ left_start = &left.atoms.head[0], left_count = 3,
85 85ab4559 2020-09-22 stsp * - baz } right_start = NULL, right_count = 0 }
86 85ab4559 2020-09-22 stsp * moo }
87 85ab4559 2020-09-22 stsp * goo }-- diff_chunk{ left_start = &left.atoms.head[3], left_count = 3,
88 85ab4559 2020-09-22 stsp * zoo } right_start = &right.atoms.head[0], right_count = 3 }
89 85ab4559 2020-09-22 stsp * +loo }
90 85ab4559 2020-09-22 stsp * +roo }-- diff_chunk{ left_start = NULL, left_count = 0,
91 85ab4559 2020-09-22 stsp * +too } right_start = &right.atoms.head[3], right_count = 3 }
92 85ab4559 2020-09-22 stsp *
93 85ab4559 2020-09-22 stsp */
94 85ab4559 2020-09-22 stsp struct diff_chunk {
95 85ab4559 2020-09-22 stsp bool solved;
96 85ab4559 2020-09-22 stsp struct diff_atom *left_start;
97 85ab4559 2020-09-22 stsp unsigned int left_count;
98 85ab4559 2020-09-22 stsp struct diff_atom *right_start;
99 85ab4559 2020-09-22 stsp unsigned int right_count;
100 85ab4559 2020-09-22 stsp };
101 85ab4559 2020-09-22 stsp
102 85ab4559 2020-09-22 stsp #define DIFF_RESULT_ALLOC_BLOCKSIZE 128
103 85ab4559 2020-09-22 stsp
104 85ab4559 2020-09-22 stsp enum diff_chunk_type {
105 85ab4559 2020-09-22 stsp CHUNK_EMPTY,
106 85ab4559 2020-09-22 stsp CHUNK_PLUS,
107 85ab4559 2020-09-22 stsp CHUNK_MINUS,
108 85ab4559 2020-09-22 stsp CHUNK_SAME,
109 85ab4559 2020-09-22 stsp CHUNK_ERROR,
110 85ab4559 2020-09-22 stsp };
111 85ab4559 2020-09-22 stsp
112 85ab4559 2020-09-22 stsp static inline enum diff_chunk_type
113 85ab4559 2020-09-22 stsp diff_chunk_type(const struct diff_chunk *chunk)
114 85ab4559 2020-09-22 stsp {
115 85ab4559 2020-09-22 stsp if (!chunk->left_count && !chunk->right_count)
116 85ab4559 2020-09-22 stsp return CHUNK_EMPTY;
117 85ab4559 2020-09-22 stsp if (!chunk->solved)
118 85ab4559 2020-09-22 stsp return CHUNK_ERROR;
119 85ab4559 2020-09-22 stsp if (!chunk->right_count)
120 85ab4559 2020-09-22 stsp return CHUNK_MINUS;
121 85ab4559 2020-09-22 stsp if (!chunk->left_count)
122 85ab4559 2020-09-22 stsp return CHUNK_PLUS;
123 85ab4559 2020-09-22 stsp if (chunk->left_count != chunk->right_count)
124 85ab4559 2020-09-22 stsp return CHUNK_ERROR;
125 85ab4559 2020-09-22 stsp return CHUNK_SAME;
126 85ab4559 2020-09-22 stsp }
127 85ab4559 2020-09-22 stsp
128 2f26640c 2020-10-17 stsp struct diff_chunk_context;
129 2f26640c 2020-10-17 stsp
130 2f26640c 2020-10-17 stsp bool
131 2f26640c 2020-10-17 stsp diff_chunk_context_empty(const struct diff_chunk_context *cc);
132 2f26640c 2020-10-17 stsp
133 2f26640c 2020-10-17 stsp bool
134 2f26640c 2020-10-17 stsp diff_chunk_contexts_touch(const struct diff_chunk_context *cc,
135 2f26640c 2020-10-17 stsp const struct diff_chunk_context *other);
136 2f26640c 2020-10-17 stsp
137 2f26640c 2020-10-17 stsp void
138 2f26640c 2020-10-17 stsp diff_chunk_contexts_merge(struct diff_chunk_context *cc,
139 2f26640c 2020-10-17 stsp const struct diff_chunk_context *other);
140 2f26640c 2020-10-17 stsp
141 85ab4559 2020-09-22 stsp struct diff_state {
142 85ab4559 2020-09-22 stsp /* The final result passed to the original diff caller. */
143 85ab4559 2020-09-22 stsp struct diff_result *result;
144 85ab4559 2020-09-22 stsp
145 85ab4559 2020-09-22 stsp /* The root diff_data is in result->left,right, these are (possibly)
146 85ab4559 2020-09-22 stsp * subsections of the root data. */
147 85ab4559 2020-09-22 stsp struct diff_data left;
148 85ab4559 2020-09-22 stsp struct diff_data right;
149 85ab4559 2020-09-22 stsp
150 85ab4559 2020-09-22 stsp unsigned int recursion_depth_left;
151 85ab4559 2020-09-22 stsp
152 85ab4559 2020-09-22 stsp /* Remaining chunks from one diff algorithm pass, if any solved == false
153 85ab4559 2020-09-22 stsp * chunks came up. */
154 85ab4559 2020-09-22 stsp diff_chunk_arraylist_t temp_result;
155 8be88dfa 2020-10-21 stsp
156 8be88dfa 2020-10-21 stsp /* State buffer used by Myers algorithm. */
157 8be88dfa 2020-10-21 stsp int *kd_buf;
158 8be88dfa 2020-10-21 stsp size_t kd_buf_size; /* in units of sizeof(int), not bytes */
159 85ab4559 2020-09-22 stsp };
160 85ab4559 2020-09-22 stsp
161 85ab4559 2020-09-22 stsp struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved,
162 85ab4559 2020-09-22 stsp struct diff_atom *left_start,
163 85ab4559 2020-09-22 stsp unsigned int left_count,
164 85ab4559 2020-09-22 stsp struct diff_atom *right_start,
165 85ab4559 2020-09-22 stsp unsigned int right_count);
166 2c20a3ed 2020-09-22 stsp
167 2c20a3ed 2020-09-22 stsp struct diff_output_info;
168 2c20a3ed 2020-09-22 stsp
169 2c20a3ed 2020-09-22 stsp int diff_output_lines(struct diff_output_info *output_info, FILE *dest,
170 2c20a3ed 2020-09-22 stsp const char *prefix, struct diff_atom *start_atom,
171 2c20a3ed 2020-09-22 stsp unsigned int count);
172 2c20a3ed 2020-09-22 stsp
173 7021523c 2020-10-16 stsp int diff_output_trailing_newline_msg(struct diff_output_info *outinfo,
174 7021523c 2020-10-16 stsp FILE *dest,
175 7021523c 2020-10-16 stsp const struct diff_chunk *c);
176 b3fd1fa2 2020-12-10 stsp #define DIFF_FUNCTION_CONTEXT_SIZE 55
177 b3fd1fa2 2020-12-10 stsp int diff_output_match_function_prototype(char *prototype, size_t prototype_size,
178 b3fd1fa2 2020-12-10 stsp int *last_prototype_idx,
179 13e2caa3 2020-10-17 stsp const struct diff_result *result,
180 13e2caa3 2020-10-17 stsp const struct diff_chunk_context *cc);
181 7021523c 2020-10-16 stsp
182 2c20a3ed 2020-09-22 stsp struct diff_output_info *diff_output_info_alloc(void);
183 87c31341 2020-10-11 neels
184 87c31341 2020-10-11 neels void
185 87c31341 2020-10-11 neels diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
186 87c31341 2020-10-11 neels struct diff_atom *from_atom, unsigned int atoms_count);