1 /*
2 * diff.c : routines for doing diffs
3 *
4 * ====================================================================
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * with the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
20 * under the License.
21 * ====================================================================
22 */
23
24
25 #include <apr.h>
26 #include <apr_pools.h>
27 #include <apr_general.h>
28
29 #include "svn_pools.h"
30 #include "svn_error.h"
31 #include "svn_diff.h"
32 #include "svn_types.h"
33
34 #include "diff.h"
35
36 /*
37 * Variance adjustment rules:
38 *
39 * See notes/variance-adjusted-patching.html
40 *
41 * ###: Expand this comment to contain the full set of adjustment
42 * ###: rules instead of pointing to a webpage.
43 */
44
45 /*
46 * In the text below consider the following:
47 *
48 * O = Original
49 * M = Modified
50 * L = Latest
51 * A = Ancestor
52 * X:Y = diff between X and Y
53 * X:Y:Z = 3-way diff between X, Y and Z
54 * P = O:L, possibly adjusted
55 *
56 * diff4 -- Variance adjusted diff algorithm
57 *
58 * 1. Create a diff O:L and call that P.
59 *
60 * 2. Morph P into a 3-way diff by performing the following
61 * transformation: O:L -> O:O:L.
62 *
63 * 3. Create a diff A:O.
64 *
65 * 4. Using A:O...
66 *
67 * #. Using M:A...
68 *
69 * #. Resolve conflicts...
70 *
71
72 1. Out-range added line: decrement the line numbers in every hunk in P
73 that comes after the addition. This undoes the effect of the add, since
74 the add never happened in D.
75
76 2. Out-range deleted line: increment the line numbers in every hunk in P
77 that comes after the deletion. This undoes the effect of the deletion,
78 since the deletion never happened in D.
79
80 3. Out-range edited line: do nothing. Out-range edits are irrelevant to P.
81
82 4. Added line in context range in P: remove the corresponding line from
83 the context, optionally replacing it with new context based on that
84 region in M, and adjust line numbers and mappings appropriately.
85
86 5. Added line in affected text range in P: this is a dependency problem
87 -- part of the change T:18-T:19 depends on changes introduced to T after
88 B branched. There are several possible behaviors, depending on what the
89 user wants. One is to generate an informative error, stating that
90 T:18-T:19 depends on some other change (T:N-T:M, where N>=8, M<=18,
91 and M-N == 1); the exact revisions can be discovered automatically using
92 the same process as "cvs annotate", though it may take some time to do
93 so. Another option is to include the change in P, as an insertion of the
94 "after" version of the text, and adjust line numbers and mappings
95 accordingly. (And if all this isn't sounding a lot like a directory
96 merge algorithm, try drinking more of the Kool-Aid.) A third option is
97 to include it as an insertion, but with metadata (such as CVS-style
98 conflict markers) indicating that the line attempting to be patched
99 does not exist in B.
100
101 6. Deleted line that is in-range in P: request another universe -- this
102 situation can't happen in ours.
103
104 7. In-range edited line: reverse that edit in the "before" version of the
105 corresponding line in the appropriate hunk in P, to obtain the version of
106 the line that will be found in B when P is applied.
107 */
108
109
110 static void
adjust_diff(svn_diff_t * diff,svn_diff_t * adjust)111 adjust_diff(svn_diff_t *diff, svn_diff_t *adjust)
112 {
113 svn_diff_t *hunk;
114 apr_off_t range_start;
115 apr_off_t range_end;
116 apr_off_t adjustment;
117
118 for (; adjust; adjust = adjust->next)
119 {
120 range_start = adjust->modified_start;
121 range_end = range_start + adjust->modified_length;
122 adjustment = adjust->original_length - adjust->modified_length;
123
124 /* No change in line count, so no modifications. [3, 7] */
125 if (adjustment == 0)
126 continue;
127
128 for (hunk = diff; hunk; hunk = hunk->next)
129 {
130 /* Changes are in the range before this hunk. Adjust the start
131 * of the hunk. [1, 2]
132 */
133 if (hunk->modified_start >= range_end)
134 {
135 hunk->modified_start += adjustment;
136 continue;
137 }
138
139 /* Changes are in the range beyond this hunk. No adjustments
140 * needed. [1, 2]
141 */
142 if (hunk->modified_start + hunk->modified_length <= range_start)
143 continue;
144
145 /* From here on changes are in the range of this hunk. */
146
147 /* This is a context hunk. Adjust the length. [4]
148 */
149 if (hunk->type == svn_diff__type_diff_modified)
150 {
151 hunk->modified_length += adjustment;
152 continue;
153 }
154
155 /* Mark as conflicted. This happens in the reverse case when a line
156 * is added in range and in the forward case when a line is deleted
157 * in range. [5 (reverse), 6 (forward)]
158 */
159 if (adjustment < 0)
160 hunk->type = svn_diff__type_conflict;
161
162 /* Adjust the length of this hunk (reverse the change). [5, 6] */
163 hunk->modified_length -= adjustment;
164 }
165 }
166 }
167
168 svn_error_t *
svn_diff_diff4_2(svn_diff_t ** diff,void * diff_baton,const svn_diff_fns2_t * vtable,apr_pool_t * pool)169 svn_diff_diff4_2(svn_diff_t **diff,
170 void *diff_baton,
171 const svn_diff_fns2_t *vtable,
172 apr_pool_t *pool)
173 {
174 svn_diff__tree_t *tree;
175 svn_diff__position_t *position_list[4];
176 svn_diff__token_index_t num_tokens;
177 svn_diff__token_index_t *token_counts[4];
178 svn_diff_datasource_e datasource[] = {svn_diff_datasource_original,
179 svn_diff_datasource_modified,
180 svn_diff_datasource_latest,
181 svn_diff_datasource_ancestor};
182 svn_diff__lcs_t *lcs_ol;
183 svn_diff__lcs_t *lcs_adjust;
184 svn_diff_t *diff_ol;
185 svn_diff_t *diff_adjust;
186 svn_diff_t *hunk;
187 apr_pool_t *subpool;
188 apr_pool_t *subpool2;
189 apr_pool_t *subpool3;
190 apr_off_t prefix_lines = 0;
191 apr_off_t suffix_lines = 0;
192
193 *diff = NULL;
194
195 subpool = svn_pool_create(pool);
196 subpool2 = svn_pool_create(subpool);
197 subpool3 = svn_pool_create(subpool2);
198
199 svn_diff__tree_create(&tree, subpool3);
200
201 SVN_ERR(vtable->datasources_open(diff_baton, &prefix_lines, &suffix_lines,
202 datasource, 4));
203
204 SVN_ERR(svn_diff__get_tokens(&position_list[0],
205 tree,
206 diff_baton, vtable,
207 svn_diff_datasource_original,
208 prefix_lines,
209 subpool2));
210
211 SVN_ERR(svn_diff__get_tokens(&position_list[1],
212 tree,
213 diff_baton, vtable,
214 svn_diff_datasource_modified,
215 prefix_lines,
216 subpool));
217
218 SVN_ERR(svn_diff__get_tokens(&position_list[2],
219 tree,
220 diff_baton, vtable,
221 svn_diff_datasource_latest,
222 prefix_lines,
223 subpool));
224
225 SVN_ERR(svn_diff__get_tokens(&position_list[3],
226 tree,
227 diff_baton, vtable,
228 svn_diff_datasource_ancestor,
229 prefix_lines,
230 subpool2));
231
232 num_tokens = svn_diff__get_node_count(tree);
233
234 /* Get rid of the tokens, we don't need them to calc the diff */
235 if (vtable->token_discard_all != NULL)
236 vtable->token_discard_all(diff_baton);
237
238 /* We don't need the nodes in the tree either anymore, nor the tree itself */
239 svn_pool_clear(subpool3);
240
241 token_counts[0] = svn_diff__get_token_counts(position_list[0], num_tokens,
242 subpool);
243 token_counts[1] = svn_diff__get_token_counts(position_list[1], num_tokens,
244 subpool);
245 token_counts[2] = svn_diff__get_token_counts(position_list[2], num_tokens,
246 subpool);
247 token_counts[3] = svn_diff__get_token_counts(position_list[3], num_tokens,
248 subpool);
249
250 /* Get the lcs for original - latest */
251 lcs_ol = svn_diff__lcs(position_list[0], position_list[2],
252 token_counts[0], token_counts[2],
253 num_tokens, prefix_lines,
254 suffix_lines, subpool3);
255 diff_ol = svn_diff__diff(lcs_ol, 1, 1, TRUE, pool);
256
257 svn_pool_clear(subpool3);
258
259 for (hunk = diff_ol; hunk; hunk = hunk->next)
260 {
261 hunk->latest_start = hunk->modified_start;
262 hunk->latest_length = hunk->modified_length;
263 hunk->modified_start = hunk->original_start;
264 hunk->modified_length = hunk->original_length;
265
266 if (hunk->type == svn_diff__type_diff_modified)
267 hunk->type = svn_diff__type_diff_latest;
268 else
269 hunk->type = svn_diff__type_diff_modified;
270 }
271
272 /* Get the lcs for common ancestor - original
273 * Do reverse adjustments
274 */
275 lcs_adjust = svn_diff__lcs(position_list[3], position_list[2],
276 token_counts[3], token_counts[2],
277 num_tokens, prefix_lines,
278 suffix_lines, subpool3);
279 diff_adjust = svn_diff__diff(lcs_adjust, 1, 1, FALSE, subpool3);
280 adjust_diff(diff_ol, diff_adjust);
281
282 svn_pool_clear(subpool3);
283
284 /* Get the lcs for modified - common ancestor
285 * Do forward adjustments
286 */
287 lcs_adjust = svn_diff__lcs(position_list[1], position_list[3],
288 token_counts[1], token_counts[3],
289 num_tokens, prefix_lines,
290 suffix_lines, subpool3);
291 diff_adjust = svn_diff__diff(lcs_adjust, 1, 1, FALSE, subpool3);
292 adjust_diff(diff_ol, diff_adjust);
293
294 /* Get rid of the position lists for original and ancestor, and delete
295 * our scratchpool.
296 */
297 svn_pool_destroy(subpool2);
298
299 /* Now we try and resolve the conflicts we encountered */
300 for (hunk = diff_ol; hunk; hunk = hunk->next)
301 {
302 if (hunk->type == svn_diff__type_conflict)
303 {
304 svn_diff__resolve_conflict(hunk, &position_list[1],
305 &position_list[2], num_tokens, pool);
306 }
307 }
308
309 svn_pool_destroy(subpool);
310
311 *diff = diff_ol;
312
313 return SVN_NO_ERROR;
314 }
315