src/TortoiseMerge/libsvn_diff/diff3.c

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