1 /* Generic infrastructure to implement various diff algorithms. */
3 * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
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.
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.
19 #define MAX(A,B) ((A)>(B)?(A):(B))
22 #define MIN(A,B) ((A)<(B)?(A):(B))
26 diff_range_empty(const struct diff_range
*r
)
28 return r
->start
== r
->end
;
32 diff_ranges_touch(const struct diff_range
*a
, const struct diff_range
*b
)
34 return (a
->end
>= b
->start
) && (a
->start
<= b
->end
);
38 diff_ranges_merge(struct diff_range
*a
, const struct diff_range
*b
)
40 *a
= (struct diff_range
){
41 .start
= MIN(a
->start
, b
->start
),
42 .end
= MAX(a
->end
, b
->end
),
47 diff_range_len(const struct diff_range
*r
)
51 return r
->end
- r
->start
;
54 /* List of all possible return codes of a diff invocation. */
55 #define DIFF_RC_USE_DIFF_ALGO_FALLBACK -1
57 /* Any positive return values are errno values from sys/errno.h */
59 /* Indicate whether two given diff atoms match. */
61 diff_atom_same(bool *same
,
62 const struct diff_atom
*left
,
63 const struct diff_atom
*right
);
65 /* A diff chunk represents a set of atoms on the left and/or a set of atoms on
69 * The diff algorithm has divided the source file, and this is a chunk that the
70 * inner_algo should run on next.
71 * The lines on the left should be diffed against the lines on the right.
72 * (If there are no left lines or no right lines, it implies solved == true,
73 * because there is nothing to diff.)
76 * If there are only left atoms, it is a chunk removing atoms from the left ("a
78 * If there are only right atoms, it is a chunk adding atoms from the right ("a
80 * If there are both left and right lines, it is a chunk of equal content on
81 * both sides, and left_count == right_count:
84 * - bar }-- diff_chunk{ left_start = &left.atoms.head[0], left_count = 3,
85 * - baz } right_start = NULL, right_count = 0 }
87 * goo }-- diff_chunk{ left_start = &left.atoms.head[3], left_count = 3,
88 * zoo } right_start = &right.atoms.head[0], right_count = 3 }
90 * +roo }-- diff_chunk{ left_start = NULL, left_count = 0,
91 * +too } right_start = &right.atoms.head[3], right_count = 3 }
96 struct diff_atom
*left_start
;
97 unsigned int left_count
;
98 struct diff_atom
*right_start
;
99 unsigned int right_count
;
102 #define DIFF_RESULT_ALLOC_BLOCKSIZE 128
104 enum diff_chunk_type
{
112 static inline enum diff_chunk_type
113 diff_chunk_type(const struct diff_chunk
*chunk
)
115 if (!chunk
->left_count
&& !chunk
->right_count
)
119 if (!chunk
->right_count
)
121 if (!chunk
->left_count
)
123 if (chunk
->left_count
!= chunk
->right_count
)
128 struct diff_chunk_context
;
131 diff_chunk_context_empty(const struct diff_chunk_context
*cc
);
134 diff_chunk_contexts_touch(const struct diff_chunk_context
*cc
,
135 const struct diff_chunk_context
*other
);
138 diff_chunk_contexts_merge(struct diff_chunk_context
*cc
,
139 const struct diff_chunk_context
*other
);
142 /* The final result passed to the original diff caller. */
143 struct diff_result
*result
;
145 /* The root diff_data is in result->left,right, these are (possibly)
146 * subsections of the root data. */
147 struct diff_data left
;
148 struct diff_data right
;
150 unsigned int recursion_depth_left
;
152 /* Remaining chunks from one diff algorithm pass, if any solved == false
154 diff_chunk_arraylist_t temp_result
;
156 /* State buffer used by Myers algorithm. */
158 size_t kd_buf_size
; /* in units of sizeof(int), not bytes */
161 struct diff_chunk
*diff_state_add_chunk(struct diff_state
*state
, bool solved
,
162 struct diff_atom
*left_start
,
163 unsigned int left_count
,
164 struct diff_atom
*right_start
,
165 unsigned int right_count
);
167 struct diff_output_info
;
169 int diff_output_lines(struct diff_output_info
*output_info
, FILE *dest
,
170 const char *prefix
, struct diff_atom
*start_atom
,
173 int diff_output_trailing_newline_msg(struct diff_output_info
*outinfo
,
175 const struct diff_chunk
*c
);
176 #define DIFF_FUNCTION_CONTEXT_SIZE 55
177 int diff_output_match_function_prototype(char *prototype
, size_t prototype_size
,
178 int *last_prototype_idx
,
179 const struct diff_result
*result
,
180 const struct diff_chunk_context
*cc
);
182 struct diff_output_info
*diff_output_info_alloc(void);
185 diff_data_init_subsection(struct diff_data
*d
, struct diff_data
*parent
,
186 struct diff_atom
*from_atom
, unsigned int atoms_count
);