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
diff_range_empty(const struct diff_range * r)26 diff_range_empty(const struct diff_range *r)
27 {
28 return r->start == r->end;
29 }
30
31 static inline bool
diff_ranges_touch(const struct diff_range * a,const struct diff_range * b)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
diff_ranges_merge(struct diff_range * a,const struct diff_range * b)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
diff_range_len(const struct diff_range * r)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 int chunk_start_line);
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