2 * diff.c : routines for doing diffs
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
13 * http://www.apache.org/licenses/LICENSE-2.0
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
21 * ====================================================================
26 #include <apr_pools.h>
27 #include <apr_general.h>
29 #include "svn_pools.h"
30 #include "svn_error.h"
32 #include "svn_types.h"
37 * Variance adjustment rules:
39 * See notes/variance-adjusted-patching.html
41 * ###: Expand this comment to contain the full set of adjustment
42 * ###: rules instead of pointing to a webpage.
46 * In the text below consider the following:
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
56 * diff4 -- Variance adjusted diff algorithm
58 * 1. Create a diff O:L and call that P.
60 * 2. Morph P into a 3-way diff by performing the following
61 * transformation: O:L -> O:O:L.
63 * 3. Create a diff A:O.
69 * #. Resolve conflicts...
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.
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.
80 3. Out-range edited line: do nothing. Out-range edits are irrelevant to P.
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.
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
101 6. Deleted line that is in-range in P: request another universe -- this
102 situation can't happen in ours.
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.
111 adjust_diff(svn_diff_t *diff, svn_diff_t *adjust)
114 apr_off_t range_start;
116 apr_off_t adjustment;
118 for (; adjust; adjust = adjust->next)
120 range_start = adjust->modified_start;
121 range_end = range_start + adjust->modified_length;
122 adjustment = adjust->original_length - adjust->modified_length;
124 /* No change in line count, so no modifications. [3, 7] */
128 for (hunk = diff; hunk; hunk = hunk->next)
130 /* Changes are in the range before this hunk. Adjust the start
131 * of the hunk. [1, 2]
133 if (hunk->modified_start >= range_end)
135 hunk->modified_start += adjustment;
139 /* Changes are in the range beyond this hunk. No adjustments
142 if (hunk->modified_start + hunk->modified_length <= range_start)
145 /* From here on changes are in the range of this hunk. */
147 /* This is a context hunk. Adjust the length. [4]
149 if (hunk->type == svn_diff__type_diff_modified)
151 hunk->modified_length += adjustment;
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)]
160 hunk->type = svn_diff__type_conflict;
162 /* Adjust the length of this hunk (reverse the change). [5, 6] */
163 hunk->modified_length -= adjustment;
169 svn_diff_diff4_2(svn_diff_t **diff,
171 const svn_diff_fns2_t *vtable,
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;
185 svn_diff_t *diff_adjust;
188 apr_pool_t *subpool2;
189 apr_pool_t *subpool3;
190 apr_off_t prefix_lines = 0;
191 apr_off_t suffix_lines = 0;
195 subpool = svn_pool_create(pool);
196 subpool2 = svn_pool_create(subpool);
197 subpool3 = svn_pool_create(subpool2);
199 svn_diff__tree_create(&tree, subpool3);
201 SVN_ERR(vtable->datasources_open(diff_baton, &prefix_lines, &suffix_lines,
204 SVN_ERR(svn_diff__get_tokens(&position_list[0],
207 svn_diff_datasource_original,
211 SVN_ERR(svn_diff__get_tokens(&position_list[1],
214 svn_diff_datasource_modified,
218 SVN_ERR(svn_diff__get_tokens(&position_list[2],
221 svn_diff_datasource_latest,
225 SVN_ERR(svn_diff__get_tokens(&position_list[3],
228 svn_diff_datasource_ancestor,
232 num_tokens = svn_diff__get_node_count(tree);
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);
238 /* We don't need the nodes in the tree either anymore, nor the tree itself */
239 svn_pool_clear(subpool3);
241 token_counts[0] = svn_diff__get_token_counts(position_list[0], num_tokens,
243 token_counts[1] = svn_diff__get_token_counts(position_list[1], num_tokens,
245 token_counts[2] = svn_diff__get_token_counts(position_list[2], num_tokens,
247 token_counts[3] = svn_diff__get_token_counts(position_list[3], num_tokens,
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);
257 svn_pool_clear(subpool3);
259 for (hunk = diff_ol; hunk; hunk = hunk->next)
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;
266 if (hunk->type == svn_diff__type_diff_modified)
267 hunk->type = svn_diff__type_diff_latest;
269 hunk->type = svn_diff__type_diff_modified;
272 /* Get the lcs for common ancestor - original
273 * Do reverse adjustments
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);
282 svn_pool_clear(subpool3);
284 /* Get the lcs for modified - common ancestor
285 * Do forward adjustments
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);
294 /* Get rid of the position lists for original and ancestor, and delete
297 svn_pool_destroy(subpool2);
299 /* Now we try and resolve the conflicts we encountered */
300 for (hunk = diff_ol; hunk; hunk = hunk->next)
302 if (hunk->type == svn_diff__type_conflict)
304 svn_diff__resolve_conflict(hunk, &position_list[1],
305 &position_list[2], num_tokens, pool);
309 svn_pool_destroy(subpool);