diff options
Diffstat (limited to 'subversion/libsvn_diff/diff4.c')
| -rw-r--r-- | subversion/libsvn_diff/diff4.c | 314 |
1 files changed, 314 insertions, 0 deletions
diff --git a/subversion/libsvn_diff/diff4.c b/subversion/libsvn_diff/diff4.c new file mode 100644 index 0000000..9f3cb8c --- /dev/null +++ b/subversion/libsvn_diff/diff4.c @@ -0,0 +1,314 @@ +/* + * diff.c : routines for doing diffs + * + * ==================================================================== + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + * ==================================================================== + */ + + +#include <apr.h> +#include <apr_pools.h> +#include <apr_general.h> + +#include "svn_pools.h" +#include "svn_error.h" +#include "svn_diff.h" +#include "svn_types.h" + +#include "diff.h" + +/* + * Variance adjustment rules: + * + * See notes/variance-adjusted-patching.html + * + * ###: Expand this comment to contain the full set of adjustment + * ###: rules instead of pointing to a webpage. + */ + +/* + * In the text below consider the following: + * + * O = Original + * M = Modified + * L = Latest + * A = Ancestor + * X:Y = diff between X and Y + * X:Y:Z = 3-way diff between X, Y and Z + * P = O:L, possibly adjusted + * + * diff4 -- Variance adjusted diff algorithm + * + * 1. Create a diff O:L and call that P. + * + * 2. Morph P into a 3-way diff by performing the following + * transformation: O:L -> O:O:L. + * + * 3. Create a diff A:O. + * + * 4. Using A:O... + * + * #. Using M:A... + * + * #. Resolve conflicts... + * + + 1. Out-range added line: decrement the line numbers in every hunk in P + that comes after the addition. This undoes the effect of the add, since + the add never happened in D. + + 2. Out-range deleted line: increment the line numbers in every hunk in P + that comes after the deletion. This undoes the effect of the deletion, + since the deletion never happened in D. + + 3. Out-range edited line: do nothing. Out-range edits are irrelevant to P. + + 4. Added line in context range in P: remove the corresponding line from + the context, optionally replacing it with new context based on that + region in M, and adjust line numbers and mappings appropriately. + + 5. Added line in affected text range in P: this is a dependency problem + -- part of the change T:18-T:19 depends on changes introduced to T after + B branched. There are several possible behaviors, depending on what the + user wants. One is to generate an informative error, stating that + T:18-T:19 depends on some other change (T:N-T:M, where N>=8, M<=18, + and M-N == 1); the exact revisions can be discovered automatically using + the same process as "cvs annotate", though it may take some time to do + so. Another option is to include the change in P, as an insertion of the + "after" version of the text, and adjust line numbers and mappings + accordingly. (And if all this isn't sounding a lot like a directory + merge algorithm, try drinking more of the Kool-Aid.) A third option is + to include it as an insertion, but with metadata (such as CVS-style + conflict markers) indicating that the line attempting to be patched + does not exist in B. + + 6. Deleted line that is in-range in P: request another universe -- this + situation can't happen in ours. + + 7. In-range edited line: reverse that edit in the "before" version of the + corresponding line in the appropriate hunk in P, to obtain the version of + the line that will be found in B when P is applied. +*/ + + +static void +adjust_diff(svn_diff_t *diff, svn_diff_t *adjust) +{ + svn_diff_t *hunk; + apr_off_t range_start; + apr_off_t range_end; + apr_off_t adjustment; + + for (; adjust; adjust = adjust->next) + { + range_start = adjust->modified_start; + range_end = range_start + adjust->modified_length; + adjustment = adjust->original_length - adjust->modified_length; + + /* No change in line count, so no modifications. [3, 7] */ + if (adjustment == 0) + continue; + + for (hunk = diff; hunk; hunk = hunk->next) + { + /* Changes are in the range before this hunk. Adjust the start + * of the hunk. [1, 2] + */ + if (hunk->modified_start >= range_end) + { + hunk->modified_start += adjustment; + continue; + } + + /* Changes are in the range beyond this hunk. No adjustments + * needed. [1, 2] + */ + if (hunk->modified_start + hunk->modified_length <= range_start) + continue; + + /* From here on changes are in the range of this hunk. */ + + /* This is a context hunk. Adjust the length. [4] + */ + if (hunk->type == svn_diff__type_diff_modified) + { + hunk->modified_length += adjustment; + continue; + } + + /* Mark as conflicted. This happens in the reverse case when a line + * is added in range and in the forward case when a line is deleted + * in range. [5 (reverse), 6 (forward)] + */ + if (adjustment < 0) + hunk->type = svn_diff__type_conflict; + + /* Adjust the length of this hunk (reverse the change). [5, 6] */ + hunk->modified_length -= adjustment; + } + } +} + +svn_error_t * +svn_diff_diff4_2(svn_diff_t **diff, + void *diff_baton, + const svn_diff_fns2_t *vtable, + apr_pool_t *pool) +{ + svn_diff__tree_t *tree; + svn_diff__position_t *position_list[4]; + svn_diff__token_index_t num_tokens; + svn_diff__token_index_t *token_counts[4]; + svn_diff_datasource_e datasource[] = {svn_diff_datasource_original, + svn_diff_datasource_modified, + svn_diff_datasource_latest, + svn_diff_datasource_ancestor}; + svn_diff__lcs_t *lcs_ol; + svn_diff__lcs_t *lcs_adjust; + svn_diff_t *diff_ol; + svn_diff_t *diff_adjust; + svn_diff_t *hunk; + apr_pool_t *subpool; + apr_pool_t *subpool2; + apr_pool_t *subpool3; + apr_off_t prefix_lines = 0; + apr_off_t suffix_lines = 0; + + *diff = NULL; + + subpool = svn_pool_create(pool); + subpool2 = svn_pool_create(subpool); + subpool3 = svn_pool_create(subpool2); + + svn_diff__tree_create(&tree, subpool3); + + SVN_ERR(vtable->datasources_open(diff_baton, &prefix_lines, &suffix_lines, + datasource, 4)); + + SVN_ERR(svn_diff__get_tokens(&position_list[0], + tree, + diff_baton, vtable, + svn_diff_datasource_original, + prefix_lines, + subpool2)); + + SVN_ERR(svn_diff__get_tokens(&position_list[1], + tree, + diff_baton, vtable, + svn_diff_datasource_modified, + prefix_lines, + subpool)); + + SVN_ERR(svn_diff__get_tokens(&position_list[2], + tree, + diff_baton, vtable, + svn_diff_datasource_latest, + prefix_lines, + subpool)); + + SVN_ERR(svn_diff__get_tokens(&position_list[3], + tree, + diff_baton, vtable, + svn_diff_datasource_ancestor, + prefix_lines, + subpool2)); + + num_tokens = svn_diff__get_node_count(tree); + + /* Get rid of the tokens, we don't need them to calc the diff */ + if (vtable->token_discard_all != NULL) + vtable->token_discard_all(diff_baton); + + /* We don't need the nodes in the tree either anymore, nor the tree itself */ + svn_pool_clear(subpool3); + + token_counts[0] = svn_diff__get_token_counts(position_list[0], num_tokens, + subpool); + token_counts[1] = svn_diff__get_token_counts(position_list[1], num_tokens, + subpool); + token_counts[2] = svn_diff__get_token_counts(position_list[2], num_tokens, + subpool); + token_counts[3] = svn_diff__get_token_counts(position_list[3], num_tokens, + subpool); + + /* Get the lcs for original - latest */ + lcs_ol = svn_diff__lcs(position_list[0], position_list[2], + token_counts[0], token_counts[2], + num_tokens, prefix_lines, + suffix_lines, subpool3); + diff_ol = svn_diff__diff(lcs_ol, 1, 1, TRUE, pool); + + svn_pool_clear(subpool3); + + for (hunk = diff_ol; hunk; hunk = hunk->next) + { + hunk->latest_start = hunk->modified_start; + hunk->latest_length = hunk->modified_length; + hunk->modified_start = hunk->original_start; + hunk->modified_length = hunk->original_length; + + if (hunk->type == svn_diff__type_diff_modified) + hunk->type = svn_diff__type_diff_latest; + else + hunk->type = svn_diff__type_diff_modified; + } + + /* Get the lcs for common ancestor - original + * Do reverse adjustements + */ + lcs_adjust = svn_diff__lcs(position_list[3], position_list[2], + token_counts[3], token_counts[2], + num_tokens, prefix_lines, + suffix_lines, subpool3); + diff_adjust = svn_diff__diff(lcs_adjust, 1, 1, FALSE, subpool3); + adjust_diff(diff_ol, diff_adjust); + + svn_pool_clear(subpool3); + + /* Get the lcs for modified - common ancestor + * Do forward adjustments + */ + lcs_adjust = svn_diff__lcs(position_list[1], position_list[3], + token_counts[1], token_counts[3], + num_tokens, prefix_lines, + suffix_lines, subpool3); + diff_adjust = svn_diff__diff(lcs_adjust, 1, 1, FALSE, subpool3); + adjust_diff(diff_ol, diff_adjust); + + /* Get rid of the position lists for original and ancestor, and delete + * our scratchpool. + */ + svn_pool_destroy(subpool2); + + /* Now we try and resolve the conflicts we encountered */ + for (hunk = diff_ol; hunk; hunk = hunk->next) + { + if (hunk->type == svn_diff__type_conflict) + { + svn_diff__resolve_conflict(hunk, &position_list[1], + &position_list[2], num_tokens, pool); + } + } + + svn_pool_destroy(subpool); + + *diff = diff_ol; + + return SVN_NO_ERROR; +} |
