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