2 * diff.c : routines for doing diffs
4 * ====================================================================
5 * Copyright (c) 2000-2004 CollabNet. All rights reserved.
7 * This software is licensed as described in the file COPYING, which
8 * you should have received as part of this distribution. The terms
9 * are also available at http://subversion.tigris.org/license-1.html.
10 * If newer versions of this license are posted there, you may use a
11 * newer version instead, at your option.
13 * This software consists of voluntary contributions made by many
14 * individuals. For exact contribution history, see the revision
15 * history and logs, available at http://subversion.tigris.org/.
16 * ====================================================================
21 #include <apr_pools.h>
22 #include <apr_general.h>
24 #include "svn_pools.h"
25 #include "svn_error.h"
27 #include "svn_types.h"
32 * Variance adjustment rules:
34 * http://subversion.tigris.org/variance-adjusted-patching.html
36 * ###: Expand this comment to contain the full set of adjustment
37 * ###: rules instead of pointing to a webpage.
41 * In the text below consider the following:
47 * X:Y = diff between X and Y
48 * X:Y:Z = 3-way diff between X, Y and Z
49 * P = O:L, possibly adjusted
51 * diff4 -- Variance adjusted diff algorithm
53 * 1. Create a diff O:L and call that P.
55 * 2. Morph P into a 3-way diff by performing the following
56 * transformation: O:L -> O:O:L.
58 * 3. Create a diff A:O.
64 * #. Resolve conflicts...
67 1. Out-range added line: decrement the line numbers in every hunk in P
68 that comes after the addition. This undoes the effect of the add, since
69 the add never happened in D.
71 2. Out-range deleted line: increment the line numbers in every hunk in P
72 that comes after the deletion. This undoes the effect of the deletion,
73 since the deletion never happened in D.
75 3. Out-range edited line: do nothing. Out-range edits are irrelevant to P.
77 4. Added line in context range in P: remove the corresponding line from
78 the context, optionally replacing it with new context based on that
79 region in M, and adjust line numbers and mappings appropriately.
81 5. Added line in affected text range in P: this is a dependency problem
82 -- part of the change T:18-T:19 depends on changes introduced to T after
83 B branched. There are several possible behaviors, depending on what the
84 user wants. One is to generate an informative error, stating that
85 T:18-T:19 depends on some other change (T:N-T:M, where N>=8, M<=18,
86 and M-N == 1); the exact revisions can be discovered automatically using
87 the same process as "cvs annotate", though it may take some time to do
88 so. Another option is to include the change in P, as an insertion of the
89 "after" version of the text, and adjust line numbers and mappings
90 accordingly. (And if all this isn't sounding a lot like a directory
91 merge algorithm, try drinking more of the Kool-Aid.) A third option is
92 to include it as an insertion, but with metadata (such as CVS-style
93 conflict markers) indicating that the line attempting to be patched
96 6. Deleted line that is in-range in P: request another universe -- this
97 situation can't happen in ours.
99 7. In-range edited line: reverse that edit in the "before" version of the
100 corresponding line in the appropriate hunk in P, to obtain the version of
101 the line that will be found in B when P is applied.
106 adjust_diff(svn_diff_t
*diff
, svn_diff_t
*adjust
)
109 apr_off_t range_start
;
111 apr_off_t adjustment
;
113 for (; adjust
; adjust
= adjust
->next
)
115 range_start
= adjust
->modified_start
;
116 range_end
= range_start
+ adjust
->modified_length
;
117 adjustment
= adjust
->original_length
- adjust
->modified_length
;
119 /* No change in line count, so no modifications. [3, 7] */
123 for (hunk
= diff
; hunk
; hunk
= hunk
->next
)
125 /* Changes are in the range before this hunk. Adjust the start
126 * of the hunk. [1, 2]
128 if (hunk
->modified_start
>= range_end
)
130 hunk
->modified_start
+= adjustment
;
134 /* Changes are in the range beyond this hunk. No adjustments
137 if (hunk
->modified_start
+ hunk
->modified_length
<= range_start
)
140 /* From here on changes are in the range of this hunk. */
142 /* This is a context hunk. Adjust the length. [4]
144 if (hunk
->type
== svn_diff__type_diff_modified
)
146 hunk
->modified_length
+= adjustment
;
150 /* Mark as conflicted. This happens in the reverse case when a line
151 * is added in range and in the forward case when a line is deleted
152 * in range. [5 (reverse), 6 (forward)]
155 hunk
->type
= svn_diff__type_conflict
;
157 /* Adjust the length of this hunk (reverse the change). [5, 6] */
158 hunk
->modified_length
-= adjustment
;
164 svn_diff_diff4(svn_diff_t
**diff
,
166 const svn_diff_fns_t
*vtable
,
169 svn_diff__tree_t
*tree
;
170 svn_diff__position_t
*position_list
[4];
171 svn_diff__lcs_t
*lcs_ol
;
172 svn_diff__lcs_t
*lcs_adjust
;
174 svn_diff_t
*diff_adjust
;
177 apr_pool_t
*subpool2
;
178 apr_pool_t
*subpool3
;
182 subpool
= svn_pool_create(pool
);
183 subpool2
= svn_pool_create(subpool
);
184 subpool3
= svn_pool_create(subpool2
);
186 svn_diff__tree_create(&tree
, subpool3
);
188 SVN_ERR(svn_diff__get_tokens(&position_list
[0],
191 svn_diff_datasource_original
,
194 SVN_ERR(svn_diff__get_tokens(&position_list
[1],
197 svn_diff_datasource_modified
,
200 SVN_ERR(svn_diff__get_tokens(&position_list
[2],
203 svn_diff_datasource_latest
,
206 SVN_ERR(svn_diff__get_tokens(&position_list
[3],
209 svn_diff_datasource_ancestor
,
212 /* Get rid of the tokens, we don't need them to calc the diff */
213 if (vtable
->token_discard_all
!= NULL
)
214 vtable
->token_discard_all(diff_baton
);
216 /* We don't need the nodes in the tree either anymore, nor the tree itself */
217 svn_pool_clear(subpool3
);
219 /* Get the lcs for original - latest */
220 lcs_ol
= svn_diff__lcs(position_list
[0], position_list
[2], subpool3
);
221 diff_ol
= svn_diff__diff(lcs_ol
, 1, 1, TRUE
, pool
);
223 svn_pool_clear(subpool3
);
225 for (hunk
= diff_ol
; hunk
; hunk
= hunk
->next
)
227 hunk
->latest_start
= hunk
->modified_start
;
228 hunk
->latest_length
= hunk
->modified_length
;
229 hunk
->modified_start
= hunk
->original_start
;
230 hunk
->modified_length
= hunk
->original_length
;
232 if (hunk
->type
== svn_diff__type_diff_modified
)
233 hunk
->type
= svn_diff__type_diff_latest
;
235 hunk
->type
= svn_diff__type_diff_modified
;
238 /* Get the lcs for common ancestor - original
239 * Do reverse adjustements
241 lcs_adjust
= svn_diff__lcs(position_list
[3], position_list
[2], subpool3
);
242 diff_adjust
= svn_diff__diff(lcs_adjust
, 1, 1, FALSE
, subpool3
);
243 adjust_diff(diff_ol
, diff_adjust
);
245 svn_pool_clear(subpool3
);
247 /* Get the lcs for modified - common ancestor
248 * Do forward adjustments
250 lcs_adjust
= svn_diff__lcs(position_list
[1], position_list
[3], subpool3
);
251 diff_adjust
= svn_diff__diff(lcs_adjust
, 1, 1, FALSE
, subpool3
);
252 adjust_diff(diff_ol
, diff_adjust
);
254 /* Get rid of the position lists for original and ancestor, and delete
257 svn_pool_destroy(subpool2
);
259 /* Now we try and resolve the conflicts we encountered */
260 for (hunk
= diff_ol
; hunk
; hunk
= hunk
->next
)
262 if (hunk
->type
== svn_diff__type_conflict
)
264 svn_diff__resolve_conflict(hunk
, &position_list
[1],
265 &position_list
[2], pool
);
269 svn_pool_destroy(subpool
);