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