← Back to branch summary

~svn/ubuntu/raring/subversion/ppa

« back to all changes in this revision

Viewing changes to subversion/libsvn_diff/diff3.c

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-12-05 01:26:14 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051205012614-qom4xfypgtsqc2xq
Tags: 1.2.3dfsg1-3ubuntu1
Merge with the final Debian release of 1.2.3dfsg1-3, bringing in
fixes to the clean target, better documentation of the libdb4.3
upgrade and build fixes to work with swig1.3_1.3.27.

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
}