src/TortoiseMerge/libsvn_diff/diff3.c

   1 /*\r
   2  * diff3.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 #include "svn_error.h"\r
  24 #include "svn_version.h"\r
  25 #include "svn_io.h"\r
  26 \r
  27 #include "svn_pools.h"\r
  28 #include "svn_error.h"\r
  29 #include "svn_diff.h"\r
  30 #include "svn_types.h"\r
  31 \r
  32 #include "diff.h"\r
  33 \r
  34 \r
  35 void\r
  36 svn_diff__resolve_conflict(svn_diff_t *hunk,\r
  37                            svn_diff__position_t **position_list1,\r
  38                            svn_diff__position_t **position_list2,\r
  39                            apr_pool_t *pool)\r
  40 {\r
  41     apr_off_t modified_start = hunk->modified_start + 1;\r
  42     apr_off_t latest_start = hunk->latest_start + 1;\r
  43     apr_off_t common_length;\r
  44     apr_off_t modified_length = hunk->modified_length;\r
  45     apr_off_t latest_length = hunk->latest_length;\r
  46     svn_diff__position_t *start_position[2];\r
  47     svn_diff__position_t *position[2];\r
  48     svn_diff__lcs_t *lcs = NULL;\r
  49     svn_diff__lcs_t **lcs_ref = &lcs;\r
  50     svn_diff_t **diff_ref = &hunk->resolved_diff;\r
  51     apr_pool_t *subpool;\r
  52 \r
  53     /* First find the starting positions for the\r
  54      * comparison\r
  55      */\r
  56 \r
  57     start_position[0] = *position_list1;\r
  58     start_position[1] = *position_list2;\r
  59 \r
  60     while (start_position[0]->offset < modified_start)\r
  61       start_position[0] = start_position[0]->next;\r
  62 \r
  63     while (start_position[1]->offset < latest_start)\r
  64       start_position[1] = start_position[1]->next;\r
  65 \r
  66     position[0] = start_position[0];\r
  67     position[1] = start_position[1];\r
  68 \r
  69     common_length = modified_length < latest_length\r
  70                   ? modified_length : latest_length;\r
  71 \r
  72     while (common_length > 0\r
  73            && position[0]->node == position[1]->node)\r
  74       {\r
  75         position[0] = position[0]->next;\r
  76         position[1] = position[1]->next;\r
  77 \r
  78         common_length--;\r
  79       }\r
  80 \r
  81     if (common_length == 0\r
  82         && modified_length == latest_length)\r
  83       {\r
  84         hunk->type = svn_diff__type_diff_common;\r
  85         hunk->resolved_diff = NULL;\r
  86 \r
  87         *position_list1 = position[0];\r
  88         *position_list2 = position[1];\r
  89 \r
  90         return;\r
  91       }\r
  92 \r
  93     hunk->type = svn_diff__type_conflict;\r
  94 \r
  95     /* ### If we have a conflict we can try to find the\r
  96      * ### common parts in it by getting an lcs between\r
  97      * ### modified (start to start + length) and\r
  98      * ### latest (start to start + length).\r
  99      * ### We use this lcs to create a simple diff.  Only\r
 100      * ### where there is a diff between the two, we have\r
 101      * ### a conflict.\r
 102      * ### This raises a problem; several common diffs and\r
 103      * ### conflicts can occur within the same original\r
 104      * ### block.  This needs some thought.\r
 105      * ###\r
 106      * ### NB: We can use the node _pointers_ to identify\r
 107      * ###     different tokens\r
 108      */\r
 109 \r
 110     subpool = svn_pool_create(pool);\r
 111 \r
 112     /* Calculate how much of the two sequences was\r
 113      * actually the same.\r
 114      */\r
 115     common_length = (modified_length < latest_length\r
 116                     ? modified_length : latest_length)\r
 117                   - common_length;\r
 118 \r
 119     /* If there were matching symbols at the start of\r
 120      * both sequences, record that fact.\r
 121      */\r
 122     if (common_length > 0)\r
 123       {\r
 124         lcs = apr_palloc(subpool, sizeof(*lcs));\r
 125         lcs->next = NULL;\r
 126         lcs->position[0] = start_position[0];\r
 127         lcs->position[1] = start_position[1];\r
 128         lcs->length = common_length;\r
 129 \r
 130         lcs_ref = &lcs->next;\r
 131       }\r
 132 \r
 133     modified_length -= common_length;\r
 134     latest_length -= common_length;\r
 135 \r
 136     modified_start = start_position[0]->offset;\r
 137     latest_start = start_position[1]->offset;\r
 138 \r
 139     start_position[0] = position[0];\r
 140     start_position[1] = position[1];\r
 141 \r
 142     /* Create a new ring for svn_diff__lcs to grok.\r
 143      * We can safely do this given we don't need the\r
 144      * positions we processed anymore.\r
 145      */\r
 146     if (modified_length == 0)\r
 147       {\r
 148         *position_list1 = position[0];\r
 149         position[0] = NULL;\r
 150       }\r
 151     else\r
 152       {\r
 153         while (--modified_length)\r
 154           position[0] = position[0]->next;\r
 155 \r
 156         *position_list1 = position[0]->next;\r
 157         position[0]->next = start_position[0];\r
 158       }\r
 159 \r
 160     if (latest_length == 0)\r
 161       {\r
 162         *position_list2 = position[1];\r
 163         position[1] = NULL;\r
 164       }\r
 165     else\r
 166       {\r
 167         while (--latest_length)\r
 168           position[1] = position[1]->next;\r
 169 \r
 170         *position_list2 = position[1]->next;\r
 171         position[1]->next = start_position[1];\r
 172       }\r
 173 \r
 174     *lcs_ref = svn_diff__lcs(position[0], position[1],\r
 175                              subpool);\r
 176 \r
 177     /* Fix up the EOF lcs element in case one of\r
 178      * the two sequences was NULL.\r
 179      */\r
 180     if ((*lcs_ref)->position[0]->offset == 1)\r
 181       (*lcs_ref)->position[0] = *position_list1;\r
 182 \r
 183     if ((*lcs_ref)->position[1]->offset == 1)\r
 184       (*lcs_ref)->position[1] = *position_list2;\r
 185 \r
 186     /* Restore modified_length and latest_length */\r
 187     modified_length = hunk->modified_length;\r
 188     latest_length = hunk->latest_length;\r
 189 \r
 190     /* Produce the resolved diff */\r
 191     while (1)\r
 192       {\r
 193         if (modified_start < lcs->position[0]->offset\r
 194             || latest_start < lcs->position[1]->offset)\r
 195           {\r
 196             (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref));\r
 197 \r
 198             (*diff_ref)->type = svn_diff__type_conflict;\r
 199             (*diff_ref)->original_start = hunk->original_start;\r
 200             (*diff_ref)->original_length = hunk->original_length;\r
 201             (*diff_ref)->modified_start = modified_start - 1;\r
 202             (*diff_ref)->modified_length = lcs->position[0]->offset\r
 203                                            - modified_start;\r
 204             (*diff_ref)->latest_start = latest_start - 1;\r
 205             (*diff_ref)->latest_length = lcs->position[1]->offset\r
 206                                          - latest_start;\r
 207             (*diff_ref)->resolved_diff = NULL;\r
 208 \r
 209             diff_ref = &(*diff_ref)->next;\r
 210           }\r
 211 \r
 212         /* Detect the EOF */\r
 213         if (lcs->length == 0)\r
 214           break;\r
 215 \r
 216         modified_start = lcs->position[0]->offset;\r
 217         latest_start = lcs->position[1]->offset;\r
 218 \r
 219         (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref));\r
 220 \r
 221         (*diff_ref)->type = svn_diff__type_diff_common;\r
 222         (*diff_ref)->original_start = hunk->original_start;\r
 223         (*diff_ref)->original_length = hunk->original_length;\r
 224         (*diff_ref)->modified_start = modified_start - 1;\r
 225         (*diff_ref)->modified_length = lcs->length;\r
 226         (*diff_ref)->latest_start = latest_start - 1;\r
 227         (*diff_ref)->latest_length = lcs->length;\r
 228         (*diff_ref)->resolved_diff = NULL;\r
 229 \r
 230         diff_ref = &(*diff_ref)->next;\r
 231 \r
 232         modified_start += lcs->length;\r
 233         latest_start += lcs->length;\r
 234 \r
 235         lcs = lcs->next;\r
 236       }\r
 237 \r
 238     *diff_ref = NULL;\r
 239 \r
 240     svn_pool_destroy(subpool);\r
 241 }\r
 242 \r
 243 \r
 244 svn_error_t *\r
 245 svn_diff_diff3(svn_diff_t **diff,\r
 246                void *diff_baton,\r
 247                const svn_diff_fns_t *vtable,\r
 248                apr_pool_t *pool)\r
 249 {\r
 250   svn_diff__tree_t *tree;\r
 251   svn_diff__position_t *position_list[3];\r
 252   svn_diff__lcs_t *lcs_om;\r
 253   svn_diff__lcs_t *lcs_ol;\r
 254   apr_pool_t *subpool;\r
 255   apr_pool_t *treepool;\r
 256 \r
 257   *diff = NULL;\r
 258 \r
 259   subpool = svn_pool_create(pool);\r
 260   treepool = svn_pool_create(pool);\r
 261 \r
 262   svn_diff__tree_create(&tree, treepool);\r
 263 \r
 264   SVN_ERR(svn_diff__get_tokens(&position_list[0],\r
 265                                tree,\r
 266                                diff_baton, vtable,\r
 267                                svn_diff_datasource_original,\r
 268                                subpool));\r
 269 \r
 270   SVN_ERR(svn_diff__get_tokens(&position_list[1],\r
 271                                tree,\r
 272                                diff_baton, vtable,\r
 273                                svn_diff_datasource_modified,\r
 274                                subpool));\r
 275 \r
 276   SVN_ERR(svn_diff__get_tokens(&position_list[2],\r
 277                                tree,\r
 278                                diff_baton, vtable,\r
 279                                svn_diff_datasource_latest,\r
 280                                subpool));\r
 281 \r
 282   /* Get rid of the tokens, we don't need them to calc the diff */\r
 283   if (vtable->token_discard_all != NULL)\r
 284     vtable->token_discard_all(diff_baton);\r
 285 \r
 286   /* We don't need the nodes in the tree either anymore, nor the tree itself */\r
 287   svn_pool_destroy(treepool);\r
 288 \r
 289   /* Get the lcs for original-modified and original-latest */\r
 290   lcs_om = svn_diff__lcs(position_list[0], position_list[1],\r
 291                          subpool);\r
 292   lcs_ol = svn_diff__lcs(position_list[0], position_list[2],\r
 293                          subpool);\r
 294 \r
 295   /* Produce a merged diff */\r
 296   {\r
 297     svn_diff_t **diff_ref = diff;\r
 298 \r
 299     apr_off_t original_start = 1;\r
 300     apr_off_t modified_start = 1;\r
 301     apr_off_t latest_start = 1;\r
 302     apr_off_t original_sync;\r
 303     apr_off_t modified_sync;\r
 304     apr_off_t latest_sync;\r
 305     apr_off_t common_length;\r
 306     apr_off_t original_length;\r
 307     apr_off_t modified_length;\r
 308     apr_off_t latest_length;\r
 309     svn_boolean_t is_modified;\r
 310     svn_boolean_t is_latest;\r
 311     svn_diff__position_t sentinel_position[2];\r
 312 \r
 313     /* Point the position lists to the start of the list\r
 314      * so that common_diff/conflict detection actually is\r
 315      * able to work.\r
 316      */\r
 317     if (position_list[1])\r
 318       {\r
 319         sentinel_position[0].next = position_list[1]->next;\r
 320         sentinel_position[0].offset = position_list[1]->offset + 1;\r
 321         position_list[1]->next = &sentinel_position[0];\r
 322         position_list[1] = sentinel_position[0].next;\r
 323       }\r
 324     else\r
 325       {\r
 326         sentinel_position[0].offset = 1;\r
 327         sentinel_position[0].next = NULL;\r
 328         position_list[1] = &sentinel_position[0];\r
 329       }\r
 330 \r
 331     if (position_list[2])\r
 332       {\r
 333         sentinel_position[1].next = position_list[2]->next;\r
 334         sentinel_position[1].offset = position_list[2]->offset + 1;\r
 335         position_list[2]->next = &sentinel_position[1];\r
 336         position_list[2] = sentinel_position[1].next;\r
 337       }\r
 338     else\r
 339       {\r
 340         sentinel_position[1].offset = 1;\r
 341         sentinel_position[1].next = NULL;\r
 342         position_list[2] = &sentinel_position[1];\r
 343       }\r
 344 \r
 345     while (1)\r
 346       {\r
 347         /* Find the sync points */\r
 348         while (1)\r
 349           {\r
 350             if (lcs_om->position[0]->offset > lcs_ol->position[0]->offset)\r
 351               {\r
 352                 original_sync = lcs_om->position[0]->offset;\r
 353 \r
 354                 while (lcs_ol->position[0]->offset + lcs_ol->length\r
 355                        < original_sync)\r
 356                   lcs_ol = lcs_ol->next;\r
 357 \r
 358                 /* If the sync point is the EOF, and our current lcs segment\r
 359                  * doesn't reach as far as EOF, we need to skip this segment.\r
 360                  */\r
 361                 if (lcs_om->length == 0 && lcs_ol->length > 0\r
 362                     && lcs_ol->position[0]->offset + lcs_ol->length\r
 363                        == original_sync\r
 364                     && lcs_ol->position[1]->offset + lcs_ol->length\r
 365                        != lcs_ol->next->position[1]->offset)\r
 366                   lcs_ol = lcs_ol->next;\r
 367 \r
 368                 if (lcs_ol->position[0]->offset <= original_sync)\r
 369                     break;\r
 370               }\r
 371             else\r
 372               {\r
 373                 original_sync = lcs_ol->position[0]->offset;\r
 374 \r
 375                 while (lcs_om->position[0]->offset + lcs_om->length\r
 376                        < original_sync)\r
 377                   lcs_om = lcs_om->next;\r
 378 \r
 379                 /* If the sync point is the EOF, and our current lcs segment\r
 380                  * doesn't reach as far as EOF, we need to skip this segment.\r
 381                  */\r
 382                 if (lcs_ol->length == 0 && lcs_om->length > 0\r
 383                     && lcs_om->position[0]->offset + lcs_om->length\r
 384                        == original_sync\r
 385                     && lcs_om->position[1]->offset + lcs_om->length\r
 386                        != lcs_om->next->position[1]->offset)\r
 387                   lcs_om = lcs_om->next;\r
 388 \r
 389                 if (lcs_om->position[0]->offset <= original_sync)\r
 390                     break;\r
 391               }\r
 392           }\r
 393 \r
 394         modified_sync = lcs_om->position[1]->offset\r
 395                       + (original_sync - lcs_om->position[0]->offset);\r
 396         latest_sync = lcs_ol->position[1]->offset\r
 397                     + (original_sync - lcs_ol->position[0]->offset);\r
 398 \r
 399         /* Determine what is modified, if anything */\r
 400         is_modified = lcs_om->position[0]->offset - original_start > 0\r
 401                       || lcs_om->position[1]->offset - modified_start > 0;\r
 402 \r
 403         is_latest = lcs_ol->position[0]->offset - original_start > 0\r
 404                     || lcs_ol->position[1]->offset - latest_start > 0;\r
 405 \r
 406         if (is_modified || is_latest)\r
 407           {\r
 408             original_length = original_sync - original_start;\r
 409             modified_length = modified_sync - modified_start;\r
 410             latest_length = latest_sync - latest_start;\r
 411 \r
 412             (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref));\r
 413 \r
 414             (*diff_ref)->original_start = original_start - 1;\r
 415             (*diff_ref)->original_length = original_sync - original_start;\r
 416             (*diff_ref)->modified_start = modified_start - 1;\r
 417             (*diff_ref)->modified_length = modified_length;\r
 418             (*diff_ref)->latest_start = latest_start - 1;\r
 419             (*diff_ref)->latest_length = latest_length;\r
 420             (*diff_ref)->resolved_diff = NULL;\r
 421 \r
 422             if (is_modified && is_latest)\r
 423               {\r
 424                 svn_diff__resolve_conflict(*diff_ref,\r
 425                                            &position_list[1],\r
 426                                            &position_list[2],\r
 427                                            pool);\r
 428               }\r
 429             else if (is_modified)\r
 430               {\r
 431                 (*diff_ref)->type = svn_diff__type_diff_modified;\r
 432               }\r
 433             else\r
 434               {\r
 435                 (*diff_ref)->type = svn_diff__type_diff_latest;\r
 436               }\r
 437 \r
 438             diff_ref = &(*diff_ref)->next;\r
 439           }\r
 440 \r
 441         /* Detect EOF */\r
 442         if (lcs_om->length == 0 || lcs_ol->length == 0)\r
 443             break;\r
 444 \r
 445         modified_length = lcs_om->length\r
 446                           - (original_sync - lcs_om->position[0]->offset);\r
 447         latest_length = lcs_ol->length\r
 448                         - (original_sync - lcs_ol->position[0]->offset);\r
 449         common_length = modified_length < latest_length\r
 450                         ? modified_length : latest_length;\r
 451 \r
 452         (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref));\r
 453 \r
 454         (*diff_ref)->type = svn_diff__type_common;\r
 455         (*diff_ref)->original_start = original_sync - 1;\r
 456         (*diff_ref)->original_length = common_length;\r
 457         (*diff_ref)->modified_start = modified_sync - 1;\r
 458         (*diff_ref)->modified_length = common_length;\r
 459         (*diff_ref)->latest_start = latest_sync - 1;\r
 460         (*diff_ref)->latest_length = common_length;\r
 461         (*diff_ref)->resolved_diff = NULL;\r
 462 \r
 463         diff_ref = &(*diff_ref)->next;\r
 464 \r
 465         /* Set the new offsets */\r
 466         original_start = original_sync + common_length;\r
 467         modified_start = modified_sync + common_length;\r
 468         latest_start = latest_sync + common_length;\r
 469 \r
 470         /* Make it easier for diff_common/conflict detection\r
 471            by recording last lcs start positions\r
 472          */\r
 473         if (position_list[1]->offset < lcs_om->position[1]->offset)\r
 474           position_list[1] = lcs_om->position[1];\r
 475 \r
 476         if (position_list[2]->offset < lcs_ol->position[1]->offset)\r
 477           position_list[2] = lcs_ol->position[1];\r
 478 \r
 479         /* Make sure we are pointing to lcs entries beyond\r
 480          * the range we just processed\r
 481          */\r
 482         while (original_start >= lcs_om->position[0]->offset + lcs_om->length\r
 483                && lcs_om->length > 0)\r
 484           {\r
 485             lcs_om = lcs_om->next;\r
 486           }\r
 487 \r
 488         while (original_start >= lcs_ol->position[0]->offset + lcs_ol->length\r
 489                && lcs_ol->length > 0)\r
 490           {\r
 491             lcs_ol = lcs_ol->next;\r
 492           }\r
 493       }\r
 494 \r
 495     *diff_ref = NULL;\r
 496   }\r
 497 \r
 498   svn_pool_destroy(subpool);\r
 499 \r
 500   return SVN_NO_ERROR;\r
 501 }\r