diff4.c revision 251881
1251881Speter/* 2251881Speter * diff.c : routines for doing diffs 3251881Speter * 4251881Speter * ==================================================================== 5251881Speter * Licensed to the Apache Software Foundation (ASF) under one 6251881Speter * or more contributor license agreements. See the NOTICE file 7251881Speter * distributed with this work for additional information 8251881Speter * regarding copyright ownership. The ASF licenses this file 9251881Speter * to you under the Apache License, Version 2.0 (the 10251881Speter * "License"); you may not use this file except in compliance 11251881Speter * with the License. You may obtain a copy of the License at 12251881Speter * 13251881Speter * http://www.apache.org/licenses/LICENSE-2.0 14251881Speter * 15251881Speter * Unless required by applicable law or agreed to in writing, 16251881Speter * software distributed under the License is distributed on an 17251881Speter * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 18251881Speter * KIND, either express or implied. See the License for the 19251881Speter * specific language governing permissions and limitations 20251881Speter * under the License. 21251881Speter * ==================================================================== 22251881Speter */ 23251881Speter 24251881Speter 25251881Speter#include <apr.h> 26251881Speter#include <apr_pools.h> 27251881Speter#include <apr_general.h> 28251881Speter 29251881Speter#include "svn_pools.h" 30251881Speter#include "svn_error.h" 31251881Speter#include "svn_diff.h" 32251881Speter#include "svn_types.h" 33251881Speter 34251881Speter#include "diff.h" 35251881Speter 36251881Speter/* 37251881Speter * Variance adjustment rules: 38251881Speter * 39251881Speter * See notes/variance-adjusted-patching.html 40251881Speter * 41251881Speter * ###: Expand this comment to contain the full set of adjustment 42251881Speter * ###: rules instead of pointing to a webpage. 43251881Speter */ 44251881Speter 45251881Speter/* 46251881Speter * In the text below consider the following: 47251881Speter * 48251881Speter * O = Original 49251881Speter * M = Modified 50251881Speter * L = Latest 51251881Speter * A = Ancestor 52251881Speter * X:Y = diff between X and Y 53251881Speter * X:Y:Z = 3-way diff between X, Y and Z 54251881Speter * P = O:L, possibly adjusted 55251881Speter * 56251881Speter * diff4 -- Variance adjusted diff algorithm 57251881Speter * 58251881Speter * 1. Create a diff O:L and call that P. 59251881Speter * 60251881Speter * 2. Morph P into a 3-way diff by performing the following 61251881Speter * transformation: O:L -> O:O:L. 62251881Speter * 63251881Speter * 3. Create a diff A:O. 64251881Speter * 65251881Speter * 4. Using A:O... 66251881Speter * 67251881Speter * #. Using M:A... 68251881Speter * 69251881Speter * #. Resolve conflicts... 70251881Speter * 71251881Speter 72251881Speter 1. Out-range added line: decrement the line numbers in every hunk in P 73251881Speter that comes after the addition. This undoes the effect of the add, since 74251881Speter the add never happened in D. 75251881Speter 76251881Speter 2. Out-range deleted line: increment the line numbers in every hunk in P 77251881Speter that comes after the deletion. This undoes the effect of the deletion, 78251881Speter since the deletion never happened in D. 79251881Speter 80251881Speter 3. Out-range edited line: do nothing. Out-range edits are irrelevant to P. 81251881Speter 82251881Speter 4. Added line in context range in P: remove the corresponding line from 83251881Speter the context, optionally replacing it with new context based on that 84251881Speter region in M, and adjust line numbers and mappings appropriately. 85251881Speter 86251881Speter 5. Added line in affected text range in P: this is a dependency problem 87251881Speter -- part of the change T:18-T:19 depends on changes introduced to T after 88251881Speter B branched. There are several possible behaviors, depending on what the 89251881Speter user wants. One is to generate an informative error, stating that 90251881Speter T:18-T:19 depends on some other change (T:N-T:M, where N>=8, M<=18, 91251881Speter and M-N == 1); the exact revisions can be discovered automatically using 92251881Speter the same process as "cvs annotate", though it may take some time to do 93251881Speter so. Another option is to include the change in P, as an insertion of the 94251881Speter "after" version of the text, and adjust line numbers and mappings 95251881Speter accordingly. (And if all this isn't sounding a lot like a directory 96251881Speter merge algorithm, try drinking more of the Kool-Aid.) A third option is 97251881Speter to include it as an insertion, but with metadata (such as CVS-style 98251881Speter conflict markers) indicating that the line attempting to be patched 99251881Speter does not exist in B. 100251881Speter 101251881Speter 6. Deleted line that is in-range in P: request another universe -- this 102251881Speter situation can't happen in ours. 103251881Speter 104251881Speter 7. In-range edited line: reverse that edit in the "before" version of the 105251881Speter corresponding line in the appropriate hunk in P, to obtain the version of 106251881Speter the line that will be found in B when P is applied. 107251881Speter*/ 108251881Speter 109251881Speter 110251881Speterstatic void 111251881Speteradjust_diff(svn_diff_t *diff, svn_diff_t *adjust) 112251881Speter{ 113251881Speter svn_diff_t *hunk; 114251881Speter apr_off_t range_start; 115251881Speter apr_off_t range_end; 116251881Speter apr_off_t adjustment; 117251881Speter 118251881Speter for (; adjust; adjust = adjust->next) 119251881Speter { 120251881Speter range_start = adjust->modified_start; 121251881Speter range_end = range_start + adjust->modified_length; 122251881Speter adjustment = adjust->original_length - adjust->modified_length; 123251881Speter 124251881Speter /* No change in line count, so no modifications. [3, 7] */ 125251881Speter if (adjustment == 0) 126251881Speter continue; 127251881Speter 128251881Speter for (hunk = diff; hunk; hunk = hunk->next) 129251881Speter { 130251881Speter /* Changes are in the range before this hunk. Adjust the start 131251881Speter * of the hunk. [1, 2] 132251881Speter */ 133251881Speter if (hunk->modified_start >= range_end) 134251881Speter { 135251881Speter hunk->modified_start += adjustment; 136251881Speter continue; 137251881Speter } 138251881Speter 139251881Speter /* Changes are in the range beyond this hunk. No adjustments 140251881Speter * needed. [1, 2] 141251881Speter */ 142251881Speter if (hunk->modified_start + hunk->modified_length <= range_start) 143251881Speter continue; 144251881Speter 145251881Speter /* From here on changes are in the range of this hunk. */ 146251881Speter 147251881Speter /* This is a context hunk. Adjust the length. [4] 148251881Speter */ 149251881Speter if (hunk->type == svn_diff__type_diff_modified) 150251881Speter { 151251881Speter hunk->modified_length += adjustment; 152251881Speter continue; 153251881Speter } 154251881Speter 155251881Speter /* Mark as conflicted. This happens in the reverse case when a line 156251881Speter * is added in range and in the forward case when a line is deleted 157251881Speter * in range. [5 (reverse), 6 (forward)] 158251881Speter */ 159251881Speter if (adjustment < 0) 160251881Speter hunk->type = svn_diff__type_conflict; 161251881Speter 162251881Speter /* Adjust the length of this hunk (reverse the change). [5, 6] */ 163251881Speter hunk->modified_length -= adjustment; 164251881Speter } 165251881Speter } 166251881Speter} 167251881Speter 168251881Spetersvn_error_t * 169251881Spetersvn_diff_diff4_2(svn_diff_t **diff, 170251881Speter void *diff_baton, 171251881Speter const svn_diff_fns2_t *vtable, 172251881Speter apr_pool_t *pool) 173251881Speter{ 174251881Speter svn_diff__tree_t *tree; 175251881Speter svn_diff__position_t *position_list[4]; 176251881Speter svn_diff__token_index_t num_tokens; 177251881Speter svn_diff__token_index_t *token_counts[4]; 178251881Speter svn_diff_datasource_e datasource[] = {svn_diff_datasource_original, 179251881Speter svn_diff_datasource_modified, 180251881Speter svn_diff_datasource_latest, 181251881Speter svn_diff_datasource_ancestor}; 182251881Speter svn_diff__lcs_t *lcs_ol; 183251881Speter svn_diff__lcs_t *lcs_adjust; 184251881Speter svn_diff_t *diff_ol; 185251881Speter svn_diff_t *diff_adjust; 186251881Speter svn_diff_t *hunk; 187251881Speter apr_pool_t *subpool; 188251881Speter apr_pool_t *subpool2; 189251881Speter apr_pool_t *subpool3; 190251881Speter apr_off_t prefix_lines = 0; 191251881Speter apr_off_t suffix_lines = 0; 192251881Speter 193251881Speter *diff = NULL; 194251881Speter 195251881Speter subpool = svn_pool_create(pool); 196251881Speter subpool2 = svn_pool_create(subpool); 197251881Speter subpool3 = svn_pool_create(subpool2); 198251881Speter 199251881Speter svn_diff__tree_create(&tree, subpool3); 200251881Speter 201251881Speter SVN_ERR(vtable->datasources_open(diff_baton, &prefix_lines, &suffix_lines, 202251881Speter datasource, 4)); 203251881Speter 204251881Speter SVN_ERR(svn_diff__get_tokens(&position_list[0], 205251881Speter tree, 206251881Speter diff_baton, vtable, 207251881Speter svn_diff_datasource_original, 208251881Speter prefix_lines, 209251881Speter subpool2)); 210251881Speter 211251881Speter SVN_ERR(svn_diff__get_tokens(&position_list[1], 212251881Speter tree, 213251881Speter diff_baton, vtable, 214251881Speter svn_diff_datasource_modified, 215251881Speter prefix_lines, 216251881Speter subpool)); 217251881Speter 218251881Speter SVN_ERR(svn_diff__get_tokens(&position_list[2], 219251881Speter tree, 220251881Speter diff_baton, vtable, 221251881Speter svn_diff_datasource_latest, 222251881Speter prefix_lines, 223251881Speter subpool)); 224251881Speter 225251881Speter SVN_ERR(svn_diff__get_tokens(&position_list[3], 226251881Speter tree, 227251881Speter diff_baton, vtable, 228251881Speter svn_diff_datasource_ancestor, 229251881Speter prefix_lines, 230251881Speter subpool2)); 231251881Speter 232251881Speter num_tokens = svn_diff__get_node_count(tree); 233251881Speter 234251881Speter /* Get rid of the tokens, we don't need them to calc the diff */ 235251881Speter if (vtable->token_discard_all != NULL) 236251881Speter vtable->token_discard_all(diff_baton); 237251881Speter 238251881Speter /* We don't need the nodes in the tree either anymore, nor the tree itself */ 239251881Speter svn_pool_clear(subpool3); 240251881Speter 241251881Speter token_counts[0] = svn_diff__get_token_counts(position_list[0], num_tokens, 242251881Speter subpool); 243251881Speter token_counts[1] = svn_diff__get_token_counts(position_list[1], num_tokens, 244251881Speter subpool); 245251881Speter token_counts[2] = svn_diff__get_token_counts(position_list[2], num_tokens, 246251881Speter subpool); 247251881Speter token_counts[3] = svn_diff__get_token_counts(position_list[3], num_tokens, 248251881Speter subpool); 249251881Speter 250251881Speter /* Get the lcs for original - latest */ 251251881Speter lcs_ol = svn_diff__lcs(position_list[0], position_list[2], 252251881Speter token_counts[0], token_counts[2], 253251881Speter num_tokens, prefix_lines, 254251881Speter suffix_lines, subpool3); 255251881Speter diff_ol = svn_diff__diff(lcs_ol, 1, 1, TRUE, pool); 256251881Speter 257251881Speter svn_pool_clear(subpool3); 258251881Speter 259251881Speter for (hunk = diff_ol; hunk; hunk = hunk->next) 260251881Speter { 261251881Speter hunk->latest_start = hunk->modified_start; 262251881Speter hunk->latest_length = hunk->modified_length; 263251881Speter hunk->modified_start = hunk->original_start; 264251881Speter hunk->modified_length = hunk->original_length; 265251881Speter 266251881Speter if (hunk->type == svn_diff__type_diff_modified) 267251881Speter hunk->type = svn_diff__type_diff_latest; 268251881Speter else 269251881Speter hunk->type = svn_diff__type_diff_modified; 270251881Speter } 271251881Speter 272251881Speter /* Get the lcs for common ancestor - original 273251881Speter * Do reverse adjustements 274251881Speter */ 275251881Speter lcs_adjust = svn_diff__lcs(position_list[3], position_list[2], 276251881Speter token_counts[3], token_counts[2], 277251881Speter num_tokens, prefix_lines, 278251881Speter suffix_lines, subpool3); 279251881Speter diff_adjust = svn_diff__diff(lcs_adjust, 1, 1, FALSE, subpool3); 280251881Speter adjust_diff(diff_ol, diff_adjust); 281251881Speter 282251881Speter svn_pool_clear(subpool3); 283251881Speter 284251881Speter /* Get the lcs for modified - common ancestor 285251881Speter * Do forward adjustments 286251881Speter */ 287251881Speter lcs_adjust = svn_diff__lcs(position_list[1], position_list[3], 288251881Speter token_counts[1], token_counts[3], 289251881Speter num_tokens, prefix_lines, 290251881Speter suffix_lines, subpool3); 291251881Speter diff_adjust = svn_diff__diff(lcs_adjust, 1, 1, FALSE, subpool3); 292251881Speter adjust_diff(diff_ol, diff_adjust); 293251881Speter 294251881Speter /* Get rid of the position lists for original and ancestor, and delete 295251881Speter * our scratchpool. 296251881Speter */ 297251881Speter svn_pool_destroy(subpool2); 298251881Speter 299251881Speter /* Now we try and resolve the conflicts we encountered */ 300251881Speter for (hunk = diff_ol; hunk; hunk = hunk->next) 301251881Speter { 302251881Speter if (hunk->type == svn_diff__type_conflict) 303251881Speter { 304251881Speter svn_diff__resolve_conflict(hunk, &position_list[1], 305251881Speter &position_list[2], num_tokens, pool); 306251881Speter } 307251881Speter } 308251881Speter 309251881Speter svn_pool_destroy(subpool); 310251881Speter 311251881Speter *diff = diff_ol; 312251881Speter 313251881Speter return SVN_NO_ERROR; 314251881Speter} 315