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