src/TortoiseMerge/libsvn_diff/diff4.c

   1 /*\r
   2  * diff.c :  routines for doing diffs\r
   3  *\r
   4  * ====================================================================\r
   5  * Copyright (c) 2000-2004 CollabNet.  All rights reserved.\r
   6  *\r
   7  * This software is licensed as described in the file COPYING, which\r
   8  * you should have received as part of this distribution.  The terms\r
   9  * are also available at http://subversion.tigris.org/license-1.html.\r
  10  * If newer versions of this license are posted there, you may use a\r
  11  * newer version instead, at your option.\r
  12  *\r
  13  * This software consists of voluntary contributions made by many\r
  14  * individuals.  For exact contribution history, see the revision\r
  15  * history and logs, available at http://subversion.tigris.org/.\r
  16  * ====================================================================\r
  17  */\r
  18 \r
  19 \r
  20 #include <apr.h>\r
  21 //#include <apr_pools.h>\r
  22 #include <apr_general.h>\r
  23 \r
  24 #include "svn_pools.h"\r
  25 #include "svn_error.h"\r
  26 #include "svn_diff.h"\r
  27 #include "svn_types.h"\r
  28 \r
  29 #include "diff.h"\r
  30 \r
  31 /*\r
  32  * Variance adjustment rules:\r
  33  *\r
  34  * http://subversion.tigris.org/variance-adjusted-patching.html\r
  35  *\r
  36  * ###: Expand this comment to contain the full set of adjustment\r
  37  * ###: rules instead of pointing to a webpage.\r
  38  */\r
  39 \r
  40 /*\r
  41  * In the text below consider the following:\r
  42  *\r
  43  * O     = Original\r
  44  * M     = Modified\r
  45  * L     = Latest\r
  46  * A     = Ancestor\r
  47  * X:Y   = diff between X and Y\r
  48  * X:Y:Z = 3-way diff between X, Y and Z\r
  49  * P     = O:L, possibly adjusted\r
  50  *\r
  51  * diff4 -- Variance adjusted diff algorithm\r
  52  *\r
  53  * 1. Create a diff O:L and call that P.\r
  54  *\r
  55  * 2. Morph P into a 3-way diff by performing the following\r
  56  *    transformation: O:L -> O:O:L.\r
  57  *\r
  58  * 3. Create a diff A:O.\r
  59  *\r
  60  * 4. Using A:O...\r
  61  *\r
  62  * #. Using M:A...\r
  63  *\r
  64  * #. Resolve conflicts...\r
  65  *\r
  66 \r
  67    1. Out-range added line: decrement the line numbers in every hunk in P\r
  68       that comes after the addition. This undoes the effect of the add, since\r
  69       the add never happened in D.\r
  70 \r
  71    2. Out-range deleted line: increment the line numbers in every hunk in P\r
  72       that comes after the deletion. This undoes the effect of the deletion,\r
  73       since the deletion never happened in D.\r
  74 \r
  75    3. Out-range edited line: do nothing. Out-range edits are irrelevant to P.\r
  76 \r
  77    4. Added line in context range in P: remove the corresponding line from\r
  78       the context, optionally replacing it with new context based on that\r
  79       region in M, and adjust line numbers and mappings appropriately.\r
  80 \r
  81    5. Added line in affected text range in P: this is a dependency problem\r
  82       -- part of the change T:18-T:19 depends on changes introduced to T after\r
  83       B branched. There are several possible behaviors, depending on what the\r
  84       user wants. One is to generate an informative error, stating that\r
  85       T:18-T:19 depends on some other change (T:N-T:M, where N>=8, M<=18,\r
  86       and M-N == 1); the exact revisions can be discovered automatically using\r
  87       the same process as "cvs annotate", though it may take some time to do\r
  88       so. Another option is to include the change in P, as an insertion of the\r
  89       "after" version of the text, and adjust line numbers and mappings\r
  90       accordingly. (And if all this isn't sounding a lot like a directory\r
  91       merge algorithm, try drinking more of the Kool-Aid.) A third option is\r
  92       to include it as an insertion, but with metadata (such as CVS-style\r
  93       conflict markers) indicating that the line attempting to be patched\r
  94       does not exist in B.\r
  95 \r
  96    6. Deleted line that is in-range in P: request another universe -- this\r
  97       situation can't happen in ours.\r
  98 \r
  99    7. In-range edited line: reverse that edit in the "before" version of the\r
 100       corresponding line in the appropriate hunk in P, to obtain the version of\r
 101       the line that will be found in B when P is applied.\r
 102 */\r
 103 \r
 104 \r
 105 static void\r
 106 adjust_diff(svn_diff_t *diff, svn_diff_t *adjust)\r
 107 {\r
 108   svn_diff_t *hunk;\r
 109   apr_off_t range_start;\r
 110   apr_off_t range_end;\r
 111   apr_off_t adjustment;\r
 112 \r
 113   for (; adjust; adjust = adjust->next)\r
 114     {\r
 115       range_start = adjust->modified_start;\r
 116       range_end = range_start + adjust->modified_length;\r
 117       adjustment = adjust->original_length - adjust->modified_length;\r
 118 \r
 119       /* No change in line count, so no modifications. [3, 7] */\r
 120       if (adjustment == 0)\r
 121         continue;\r
 122 \r
 123       for (hunk = diff; hunk; hunk = hunk->next)\r
 124         {\r
 125           /* Changes are in the range before this hunk.  Adjust the start\r
 126            * of the hunk. [1, 2]\r
 127            */\r
 128           if (hunk->modified_start >= range_end)\r
 129             {\r
 130               hunk->modified_start += adjustment;\r
 131               continue;\r
 132             }\r
 133 \r
 134           /* Changes are in the range beyond this hunk.  No adjustments\r
 135            * needed. [1, 2]\r
 136            */\r
 137           if (hunk->modified_start + hunk->modified_length <= range_start)\r
 138             continue;\r
 139 \r
 140           /* From here on changes are in the range of this hunk. */\r
 141 \r
 142           /* This is a context hunk.  Adjust the length. [4]\r
 143            */\r
 144           if (hunk->type == svn_diff__type_diff_modified)\r
 145             {\r
 146               hunk->modified_length += adjustment;\r
 147               continue;\r
 148             }\r
 149 \r
 150           /* Mark as conflicted. This happens in the reverse case when a line\r
 151            * is added in range and in the forward case when a line is deleted\r
 152            * in range. [5 (reverse), 6 (forward)]\r
 153            */\r
 154           if (adjustment < 0)\r
 155               hunk->type = svn_diff__type_conflict;\r
 156 \r
 157           /* Adjust the length of this hunk (reverse the change). [5, 6] */\r
 158           hunk->modified_length -= adjustment;\r
 159         }\r
 160     }\r
 161 }\r
 162 \r
 163 svn_error_t *\r
 164 svn_diff_diff4(svn_diff_t **diff,\r
 165                void *diff_baton,\r
 166                const svn_diff_fns_t *vtable,\r
 167                apr_pool_t *pool)\r
 168 {\r
 169   svn_diff__tree_t *tree;\r
 170   svn_diff__position_t *position_list[4];\r
 171   svn_diff__lcs_t *lcs_ol;\r
 172   svn_diff__lcs_t *lcs_adjust;\r
 173   svn_diff_t *diff_ol;\r
 174   svn_diff_t *diff_adjust;\r
 175   svn_diff_t *hunk;\r
 176   apr_pool_t *subpool;\r
 177   apr_pool_t *subpool2;\r
 178   apr_pool_t *subpool3;\r
 179 \r
 180   *diff = NULL;\r
 181 \r
 182   subpool = svn_pool_create(pool);\r
 183   subpool2 = svn_pool_create(subpool);\r
 184   subpool3 = svn_pool_create(subpool2);\r
 185 \r
 186   svn_diff__tree_create(&tree, subpool3);\r
 187 \r
 188   SVN_ERR(svn_diff__get_tokens(&position_list[0],\r
 189                                tree,\r
 190                                diff_baton, vtable,\r
 191                                svn_diff_datasource_original,\r
 192                                subpool2));\r
 193 \r
 194   SVN_ERR(svn_diff__get_tokens(&position_list[1],\r
 195                                tree,\r
 196                                diff_baton, vtable,\r
 197                                svn_diff_datasource_modified,\r
 198                                subpool));\r
 199 \r
 200   SVN_ERR(svn_diff__get_tokens(&position_list[2],\r
 201                                tree,\r
 202                                diff_baton, vtable,\r
 203                                svn_diff_datasource_latest,\r
 204                                subpool));\r
 205 \r
 206   SVN_ERR(svn_diff__get_tokens(&position_list[3],\r
 207                                tree,\r
 208                                diff_baton, vtable,\r
 209                                svn_diff_datasource_ancestor,\r
 210                                subpool2));\r
 211 \r
 212   /* Get rid of the tokens, we don't need them to calc the diff */\r
 213   if (vtable->token_discard_all != NULL)\r
 214     vtable->token_discard_all(diff_baton);\r
 215 \r
 216   /* We don't need the nodes in the tree either anymore, nor the tree itself */\r
 217   svn_pool_clear(subpool3);\r
 218 \r
 219   /* Get the lcs for original - latest */\r
 220   lcs_ol = svn_diff__lcs(position_list[0], position_list[2], subpool3);\r
 221   diff_ol = svn_diff__diff(lcs_ol, 1, 1, TRUE, pool);\r
 222 \r
 223   svn_pool_clear(subpool3);\r
 224 \r
 225   for (hunk = diff_ol; hunk; hunk = hunk->next)\r
 226     {\r
 227       hunk->latest_start = hunk->modified_start;\r
 228       hunk->latest_length = hunk->modified_length;\r
 229       hunk->modified_start = hunk->original_start;\r
 230       hunk->modified_length = hunk->original_length;\r
 231 \r
 232       if (hunk->type == svn_diff__type_diff_modified)\r
 233           hunk->type = svn_diff__type_diff_latest;\r
 234       else\r
 235           hunk->type = svn_diff__type_diff_modified;\r
 236     }\r
 237 \r
 238   /* Get the lcs for common ancestor - original\r
 239    * Do reverse adjustements\r
 240    */\r
 241   lcs_adjust = svn_diff__lcs(position_list[3], position_list[2], subpool3);\r
 242   diff_adjust = svn_diff__diff(lcs_adjust, 1, 1, FALSE, subpool3);\r
 243   adjust_diff(diff_ol, diff_adjust);\r
 244 \r
 245   svn_pool_clear(subpool3);\r
 246 \r
 247   /* Get the lcs for modified - common ancestor\r
 248    * Do forward adjustments\r
 249    */\r
 250   lcs_adjust = svn_diff__lcs(position_list[1], position_list[3], subpool3);\r
 251   diff_adjust = svn_diff__diff(lcs_adjust, 1, 1, FALSE, subpool3);\r
 252   adjust_diff(diff_ol, diff_adjust);\r
 253 \r
 254   /* Get rid of the position lists for original and ancestor, and delete\r
 255    * our scratchpool.\r
 256    */\r
 257   svn_pool_destroy(subpool2);\r
 258 \r
 259   /* Now we try and resolve the conflicts we encountered */\r
 260   for (hunk = diff_ol; hunk; hunk = hunk->next)\r
 261     {\r
 262       if (hunk->type == svn_diff__type_conflict)\r
 263         {\r
 264           svn_diff__resolve_conflict(hunk, &position_list[1],\r
 265                                      &position_list[2], pool);\r
 266         }\r
 267     }\r
 268 \r
 269   svn_pool_destroy(subpool);\r
 270 \r
 271   *diff = diff_ol;\r
 272 \r
 273   return SVN_NO_ERROR;\r
 274 }\r