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