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 enum diff_chunk_type {
100 	CHUNK_EMPTY,
101 	CHUNK_PLUS,
102 	CHUNK_MINUS,
103 	CHUNK_SAME,
104 	CHUNK_ERROR,
105 };
106 
107 static inline enum diff_chunk_type
108 diff_chunk_type(const struct diff_chunk *chunk)
109 {
110 	if (!chunk->left_count && !chunk->right_count)
111 		return CHUNK_EMPTY;
112 	if (!chunk->solved)
113 		return CHUNK_ERROR;
114 	if (!chunk->right_count)
115 		return CHUNK_MINUS;
116 	if (!chunk->left_count)
117 		return CHUNK_PLUS;
118 	if (chunk->left_count != chunk->right_count)
119 		return CHUNK_ERROR;
120 	return CHUNK_SAME;
121 }
122 
123 struct diff_chunk_context;
124 
125 bool
126 diff_chunk_context_empty(const struct diff_chunk_context *cc);
127 
128 bool
129 diff_chunk_contexts_touch(const struct diff_chunk_context *cc,
130 			  const struct diff_chunk_context *other);
131 
132 void
133 diff_chunk_contexts_merge(struct diff_chunk_context *cc,
134 			  const struct diff_chunk_context *other);
135 
136 struct diff_state {
137 	/* The final result passed to the original diff caller. */
138 	struct diff_result *result;
139 
140 	/* The root diff_data is in result->left,right, these are (possibly)
141 	 * subsections of the root data. */
142 	struct diff_data left;
143 	struct diff_data right;
144 
145 	unsigned int recursion_depth_left;
146 
147 	/* Remaining chunks from one diff algorithm pass, if any solved == false
148 	 * chunks came up. */
149 	diff_chunk_arraylist_t temp_result;
150 
151  	/* State buffer used by Myers algorithm. */
152 	int *kd_buf;
153 	size_t kd_buf_size; /* in units of sizeof(int), not bytes */
154 };
155 
156 struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved,
157 					struct diff_atom *left_start,
158 					unsigned int left_count,
159 					struct diff_atom *right_start,
160 					unsigned int right_count);
161 
162 struct diff_output_info;
163 
164 int diff_output_lines(struct diff_output_info *output_info, FILE *dest,
165 		       const char *prefix, struct diff_atom *start_atom,
166 		       unsigned int count);
167 
168 int diff_output_trailing_newline_msg(struct diff_output_info *outinfo,
169 				     FILE *dest,
170 				     const struct diff_chunk *c);
171 #define DIFF_FUNCTION_CONTEXT_SIZE	55
172 int diff_output_match_function_prototype(char *prototype, size_t prototype_size,
173 					 int *last_prototype_idx,
174 					 const struct diff_result *result,
175 					 const struct diff_chunk_context *cc,
176 					 unsigned int ncontext);
177 
178 struct diff_output_info *diff_output_info_alloc(void);
179 
180 void
181 diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
182 			  struct diff_atom *from_atom, unsigned int atoms_count);