diff options
Diffstat (limited to 'subversion/libsvn_diff/diff3.c')
| -rw-r--r-- | subversion/libsvn_diff/diff3.c | 529 |
1 files changed, 529 insertions, 0 deletions
diff --git a/subversion/libsvn_diff/diff3.c b/subversion/libsvn_diff/diff3.c new file mode 100644 index 0000000..8b7c9b3 --- /dev/null +++ b/subversion/libsvn_diff/diff3.c @@ -0,0 +1,529 @@ +/* + * diff3.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" + + +void +svn_diff__resolve_conflict(svn_diff_t *hunk, + svn_diff__position_t **position_list1, + svn_diff__position_t **position_list2, + svn_diff__token_index_t num_tokens, + apr_pool_t *pool) +{ + apr_off_t modified_start = hunk->modified_start + 1; + apr_off_t latest_start = hunk->latest_start + 1; + apr_off_t common_length; + apr_off_t modified_length = hunk->modified_length; + apr_off_t latest_length = hunk->latest_length; + svn_diff__position_t *start_position[2]; + svn_diff__position_t *position[2]; + svn_diff__token_index_t *token_counts[2]; + svn_diff__lcs_t *lcs = NULL; + svn_diff__lcs_t **lcs_ref = &lcs; + svn_diff_t **diff_ref = &hunk->resolved_diff; + apr_pool_t *subpool; + + /* First find the starting positions for the + * comparison + */ + + start_position[0] = *position_list1; + start_position[1] = *position_list2; + + while (start_position[0]->offset < modified_start) + start_position[0] = start_position[0]->next; + + while (start_position[1]->offset < latest_start) + start_position[1] = start_position[1]->next; + + position[0] = start_position[0]; + position[1] = start_position[1]; + + common_length = modified_length < latest_length + ? modified_length : latest_length; + + while (common_length > 0 + && position[0]->token_index == position[1]->token_index) + { + position[0] = position[0]->next; + position[1] = position[1]->next; + + common_length--; + } + + if (common_length == 0 + && modified_length == latest_length) + { + hunk->type = svn_diff__type_diff_common; + hunk->resolved_diff = NULL; + + *position_list1 = position[0]; + *position_list2 = position[1]; + + return; + } + + hunk->type = svn_diff__type_conflict; + + /* ### If we have a conflict we can try to find the + * ### common parts in it by getting an lcs between + * ### modified (start to start + length) and + * ### latest (start to start + length). + * ### We use this lcs to create a simple diff. Only + * ### where there is a diff between the two, we have + * ### a conflict. + * ### This raises a problem; several common diffs and + * ### conflicts can occur within the same original + * ### block. This needs some thought. + * ### + * ### NB: We can use the node _pointers_ to identify + * ### different tokens + */ + + subpool = svn_pool_create(pool); + + /* Calculate how much of the two sequences was + * actually the same. + */ + common_length = (modified_length < latest_length + ? modified_length : latest_length) + - common_length; + + /* If there were matching symbols at the start of + * both sequences, record that fact. + */ + if (common_length > 0) + { + lcs = apr_palloc(subpool, sizeof(*lcs)); + lcs->next = NULL; + lcs->position[0] = start_position[0]; + lcs->position[1] = start_position[1]; + lcs->length = common_length; + + lcs_ref = &lcs->next; + } + + modified_length -= common_length; + latest_length -= common_length; + + modified_start = start_position[0]->offset; + latest_start = start_position[1]->offset; + + start_position[0] = position[0]; + start_position[1] = position[1]; + + /* Create a new ring for svn_diff__lcs to grok. + * We can safely do this given we don't need the + * positions we processed anymore. + */ + if (modified_length == 0) + { + *position_list1 = position[0]; + position[0] = NULL; + } + else + { + while (--modified_length) + position[0] = position[0]->next; + + *position_list1 = position[0]->next; + position[0]->next = start_position[0]; + } + + if (latest_length == 0) + { + *position_list2 = position[1]; + position[1] = NULL; + } + else + { + while (--latest_length) + position[1] = position[1]->next; + + *position_list2 = position[1]->next; + position[1]->next = start_position[1]; + } + + token_counts[0] = svn_diff__get_token_counts(position[0], num_tokens, + subpool); + token_counts[1] = svn_diff__get_token_counts(position[1], num_tokens, + subpool); + + *lcs_ref = svn_diff__lcs(position[0], position[1], token_counts[0], + token_counts[1], num_tokens, 0, 0, subpool); + + /* Fix up the EOF lcs element in case one of + * the two sequences was NULL. + */ + if ((*lcs_ref)->position[0]->offset == 1) + (*lcs_ref)->position[0] = *position_list1; + + if ((*lcs_ref)->position[1]->offset == 1) + (*lcs_ref)->position[1] = *position_list2; + + /* Produce the resolved diff */ + while (1) + { + if (modified_start < lcs->position[0]->offset + || latest_start < lcs->position[1]->offset) + { + (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref)); + + (*diff_ref)->type = svn_diff__type_conflict; + (*diff_ref)->original_start = hunk->original_start; + (*diff_ref)->original_length = hunk->original_length; + (*diff_ref)->modified_start = modified_start - 1; + (*diff_ref)->modified_length = lcs->position[0]->offset + - modified_start; + (*diff_ref)->latest_start = latest_start - 1; + (*diff_ref)->latest_length = lcs->position[1]->offset + - latest_start; + (*diff_ref)->resolved_diff = NULL; + + diff_ref = &(*diff_ref)->next; + } + + /* Detect the EOF */ + if (lcs->length == 0) + break; + + modified_start = lcs->position[0]->offset; + latest_start = lcs->position[1]->offset; + + (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref)); + + (*diff_ref)->type = svn_diff__type_diff_common; + (*diff_ref)->original_start = hunk->original_start; + (*diff_ref)->original_length = hunk->original_length; + (*diff_ref)->modified_start = modified_start - 1; + (*diff_ref)->modified_length = lcs->length; + (*diff_ref)->latest_start = latest_start - 1; + (*diff_ref)->latest_length = lcs->length; + (*diff_ref)->resolved_diff = NULL; + + diff_ref = &(*diff_ref)->next; + + modified_start += lcs->length; + latest_start += lcs->length; + + lcs = lcs->next; + } + + *diff_ref = NULL; + + svn_pool_destroy(subpool); +} + + +svn_error_t * +svn_diff_diff3_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[3]; + svn_diff__token_index_t num_tokens; + svn_diff__token_index_t *token_counts[3]; + svn_diff_datasource_e datasource[] = {svn_diff_datasource_original, + svn_diff_datasource_modified, + svn_diff_datasource_latest}; + svn_diff__lcs_t *lcs_om; + svn_diff__lcs_t *lcs_ol; + apr_pool_t *subpool; + apr_pool_t *treepool; + apr_off_t prefix_lines = 0; + apr_off_t suffix_lines = 0; + + *diff = NULL; + + subpool = svn_pool_create(pool); + treepool = svn_pool_create(pool); + + svn_diff__tree_create(&tree, treepool); + + SVN_ERR(vtable->datasources_open(diff_baton, &prefix_lines, &suffix_lines, + datasource, 3)); + + SVN_ERR(svn_diff__get_tokens(&position_list[0], + tree, + diff_baton, vtable, + svn_diff_datasource_original, + prefix_lines, + subpool)); + + 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)); + + 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_destroy(treepool); + + 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); + + /* Get the lcs for original-modified and original-latest */ + lcs_om = svn_diff__lcs(position_list[0], position_list[1], token_counts[0], + token_counts[1], num_tokens, prefix_lines, + suffix_lines, subpool); + lcs_ol = svn_diff__lcs(position_list[0], position_list[2], token_counts[0], + token_counts[2], num_tokens, prefix_lines, + suffix_lines, subpool); + + /* Produce a merged diff */ + { + svn_diff_t **diff_ref = diff; + + apr_off_t original_start = 1; + apr_off_t modified_start = 1; + apr_off_t latest_start = 1; + apr_off_t original_sync; + apr_off_t modified_sync; + apr_off_t latest_sync; + apr_off_t common_length; + apr_off_t modified_length; + apr_off_t latest_length; + svn_boolean_t is_modified; + svn_boolean_t is_latest; + svn_diff__position_t sentinel_position[2]; + + /* Point the position lists to the start of the list + * so that common_diff/conflict detection actually is + * able to work. + */ + if (position_list[1]) + { + sentinel_position[0].next = position_list[1]->next; + sentinel_position[0].offset = position_list[1]->offset + 1; + position_list[1]->next = &sentinel_position[0]; + position_list[1] = sentinel_position[0].next; + } + else + { + sentinel_position[0].offset = prefix_lines + 1; + sentinel_position[0].next = NULL; + position_list[1] = &sentinel_position[0]; + } + + if (position_list[2]) + { + sentinel_position[1].next = position_list[2]->next; + sentinel_position[1].offset = position_list[2]->offset + 1; + position_list[2]->next = &sentinel_position[1]; + position_list[2] = sentinel_position[1].next; + } + else + { + sentinel_position[1].offset = prefix_lines + 1; + sentinel_position[1].next = NULL; + position_list[2] = &sentinel_position[1]; + } + + while (1) + { + /* Find the sync points */ + while (1) + { + if (lcs_om->position[0]->offset > lcs_ol->position[0]->offset) + { + original_sync = lcs_om->position[0]->offset; + + while (lcs_ol->position[0]->offset + lcs_ol->length + < original_sync) + lcs_ol = lcs_ol->next; + + /* If the sync point is the EOF, and our current lcs segment + * doesn't reach as far as EOF, we need to skip this segment. + */ + if (lcs_om->length == 0 && lcs_ol->length > 0 + && lcs_ol->position[0]->offset + lcs_ol->length + == original_sync + && lcs_ol->position[1]->offset + lcs_ol->length + != lcs_ol->next->position[1]->offset) + lcs_ol = lcs_ol->next; + + if (lcs_ol->position[0]->offset <= original_sync) + break; + } + else + { + original_sync = lcs_ol->position[0]->offset; + + while (lcs_om->position[0]->offset + lcs_om->length + < original_sync) + lcs_om = lcs_om->next; + + /* If the sync point is the EOF, and our current lcs segment + * doesn't reach as far as EOF, we need to skip this segment. + */ + if (lcs_ol->length == 0 && lcs_om->length > 0 + && lcs_om->position[0]->offset + lcs_om->length + == original_sync + && lcs_om->position[1]->offset + lcs_om->length + != lcs_om->next->position[1]->offset) + lcs_om = lcs_om->next; + + if (lcs_om->position[0]->offset <= original_sync) + break; + } + } + + modified_sync = lcs_om->position[1]->offset + + (original_sync - lcs_om->position[0]->offset); + latest_sync = lcs_ol->position[1]->offset + + (original_sync - lcs_ol->position[0]->offset); + + /* Determine what is modified, if anything */ + is_modified = lcs_om->position[0]->offset - original_start > 0 + || lcs_om->position[1]->offset - modified_start > 0; + + is_latest = lcs_ol->position[0]->offset - original_start > 0 + || lcs_ol->position[1]->offset - latest_start > 0; + + if (is_modified || is_latest) + { + modified_length = modified_sync - modified_start; + latest_length = latest_sync - latest_start; + + (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref)); + + (*diff_ref)->original_start = original_start - 1; + (*diff_ref)->original_length = original_sync - original_start; + (*diff_ref)->modified_start = modified_start - 1; + (*diff_ref)->modified_length = modified_length; + (*diff_ref)->latest_start = latest_start - 1; + (*diff_ref)->latest_length = latest_length; + (*diff_ref)->resolved_diff = NULL; + + if (is_modified && is_latest) + { + svn_diff__resolve_conflict(*diff_ref, + &position_list[1], + &position_list[2], + num_tokens, + pool); + } + else if (is_modified) + { + (*diff_ref)->type = svn_diff__type_diff_modified; + } + else + { + (*diff_ref)->type = svn_diff__type_diff_latest; + } + + diff_ref = &(*diff_ref)->next; + } + + /* Detect EOF */ + if (lcs_om->length == 0 || lcs_ol->length == 0) + break; + + modified_length = lcs_om->length + - (original_sync - lcs_om->position[0]->offset); + latest_length = lcs_ol->length + - (original_sync - lcs_ol->position[0]->offset); + common_length = modified_length < latest_length + ? modified_length : latest_length; + + (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref)); + + (*diff_ref)->type = svn_diff__type_common; + (*diff_ref)->original_start = original_sync - 1; + (*diff_ref)->original_length = common_length; + (*diff_ref)->modified_start = modified_sync - 1; + (*diff_ref)->modified_length = common_length; + (*diff_ref)->latest_start = latest_sync - 1; + (*diff_ref)->latest_length = common_length; + (*diff_ref)->resolved_diff = NULL; + + diff_ref = &(*diff_ref)->next; + + /* Set the new offsets */ + original_start = original_sync + common_length; + modified_start = modified_sync + common_length; + latest_start = latest_sync + common_length; + + /* Make it easier for diff_common/conflict detection + by recording last lcs start positions + */ + if (position_list[1]->offset < lcs_om->position[1]->offset) + position_list[1] = lcs_om->position[1]; + + if (position_list[2]->offset < lcs_ol->position[1]->offset) + position_list[2] = lcs_ol->position[1]; + + /* Make sure we are pointing to lcs entries beyond + * the range we just processed + */ + while (original_start >= lcs_om->position[0]->offset + lcs_om->length + && lcs_om->length > 0) + { + lcs_om = lcs_om->next; + } + + while (original_start >= lcs_ol->position[0]->offset + lcs_ol->length + && lcs_ol->length > 0) + { + lcs_ol = lcs_ol->next; + } + } + + *diff_ref = NULL; + } + + svn_pool_destroy(subpool); + + return SVN_NO_ERROR; +} |
