← Back to branch summary

~kosova/+junk/tuxfamily-twiki

« back to all changes in this revision

Viewing changes to foswiki/lib/Foswiki/Merge.pm

  • Committer: James Michael DuPont
  • Date: 2009-07-18 19:58:49 UTC
  • Revision ID: jamesmikedupont@gmail.com-20090718195849-vgbmaht2ys791uo2
added foswiki

Show diffs side-by-side

added added

removed removed

Lines of Context:
foswiki/lib/Foswiki/Merge.pm
 
1
# See bottom of file for license and copyright information
 
2
 
 
3
=begin TML
 
4
 
 
5
---+ package Foswiki::Merge
 
6
 
 
7
Support for merging strings
 
8
 
 
9
=cut
 
10
 
 
11
package Foswiki::Merge;
 
12
 
 
13
use strict;
 
14
use Assert;
 
15
 
 
16
require CGI;
 
17
 
 
18
=begin TML
 
19
 
 
20
---++ StaticMethod merge2( $arev, $a, $brev, $b, $sep, $session, $info )
 
21
 
 
22
   * =$arev= - rev for $a (string)
 
23
   * =$a= - first ('original') string
 
24
   * =$brev= - rev for $b (string)
 
25
   * =$b= - second ('new') string
 
26
   * =$sep= = separator, string RE e.g. '.*?\n' for lines
 
27
   * =$session= - Foswiki object
 
28
   * =$info= - data block passed to plugins merge handler. Conventionally this will identify the source of the text being merged (the source form field, or undef for the body text)
 
29
 
 
30
Perform a merge of two versions of the same text, using
 
31
HTML tags to mark conflicts.
 
32
 
 
33
The granularity of the merge depends on the setting of $sep.
 
34
For example, if it is ="\\n"=, a line-by-line merge will be done.
 
35
 
 
36
Where conflicts exist, they are marked using HTML <del> and
 
37
<ins> tags. <del> marks content from $a while <ins>
 
38
marks content from $b.
 
39
 
 
40
Non-conflicting content (insertions from either set) are not
 
41
marked.
 
42
 
 
43
The plugins =mergeHandler= is called for each merge.
 
44
 
 
45
Call it like this:
 
46
<verbatim>
 
47
$newText = Foswiki::Merge::merge2(
 
48
   $oldrev, $old, $newrev, $new, '.*?\n', $session, $info );
 
49
</verbatim>
 
50
 
 
51
=cut
 
52
 
 
53
sub merge2 {
 
54
    my ( $va, $ia, $vb, $ib, $sep, $session, $info ) = @_;
 
55
 
 
56
    my @a = split( /($sep)/, $ia );
 
57
    my @b = split( /($sep)/, $ib );
 
58
 
 
59
    ASSERT( $session && $session->isa('Foswiki') ) if DEBUG;
 
60
 
 
61
    my @out;
 
62
    require Algorithm::Diff;
 
63
    Algorithm::Diff::traverse_balanced(
 
64
        \@a,
 
65
        \@b,
 
66
        {
 
67
            MATCH     => \&_acceptA,
 
68
            DISCARD_A => \&_acceptA,
 
69
            DISCARD_B => \&_acceptB,
 
70
            CHANGE    => \&_change
 
71
        },
 
72
        undef,
 
73
        \@out,
 
74
        \@a,
 
75
        \@b,
 
76
        $session, $info
 
77
    );
 
78
    return join( '', @out );
 
79
}
 
80
 
 
81
sub _acceptA {
 
82
    my ( $a, $b, $out, $ai, $bi, $session, $info ) = @_;
 
83
 
 
84
    ASSERT( $session->isa('Foswiki') ) if DEBUG;
 
85
 
 
86
    #print STDERR "From A: '$ai->[$a]'\n";
 
87
    # accept text from the old version without asking for resolution
 
88
    my $merged =
 
89
      $session->{plugins}
 
90
      ->dispatch( 'mergeHandler', ' ', $ai->[$a], undef, $info );
 
91
    if ( defined $merged ) {
 
92
        push( @$out, $merged );
 
93
    }
 
94
    else {
 
95
        push( @$out, $ai->[$a] );
 
96
    }
 
97
}
 
98
 
 
99
sub _acceptB {
 
100
    my ( $a, $b, $out, $ai, $bi, $session, $info ) = @_;
 
101
 
 
102
    ASSERT( $session->isa('Foswiki') ) if DEBUG;
 
103
 
 
104
    #print STDERR "From B: '$bi->[$b]'\n";
 
105
    my $merged =
 
106
      $session->{plugins}
 
107
      ->dispatch( 'mergeHandler', ' ', $bi->[$b], undef, $info );
 
108
    if ( defined $merged ) {
 
109
        push( @$out, $merged );
 
110
    }
 
111
    else {
 
112
        push( @$out, $bi->[$b] );
 
113
    }
 
114
}
 
115
 
 
116
sub _change {
 
117
    my ( $a, $b, $out, $ai, $bi, $session, $info ) = @_;
 
118
    my $merged;
 
119
    ASSERT( $session->isa('Foswiki') ) if DEBUG;
 
120
 
 
121
    # Diff isn't terribly smart sometimes; it will generate changes
 
122
    # with a or b empty, which I would have thought should have
 
123
    # been accepts.
 
124
    if ( $ai->[$a] =~ /\S/ ) {
 
125
 
 
126
        # there is some non-white text to delete
 
127
        if ( $bi->[$b] =~ /\S/ ) {
 
128
 
 
129
            # this insert is replacing something with something
 
130
            $merged =
 
131
              $session->{plugins}
 
132
              ->dispatch( 'mergeHandler', 'c', $ai->[$a], $bi->[$b], $info );
 
133
            if ( defined $merged ) {
 
134
                push( @$out, $merged );
 
135
            }
 
136
            else {
 
137
                push( @$out, CGI::del( $ai->[$a] ) );
 
138
                push( @$out, CGI::ins( $bi->[$b] ) );
 
139
            }
 
140
        }
 
141
        else {
 
142
            $merged =
 
143
              $session->{plugins}
 
144
              ->dispatch( 'mergeHandler', '-', $ai->[$a], $bi->[$b], $info );
 
145
            if ( defined $merged ) {
 
146
                push( @$out, $merged );
 
147
            }
 
148
            else {
 
149
                push( @$out, CGI::del( $ai->[$a] ) );
 
150
            }
 
151
        }
 
152
    }
 
153
    elsif ( $bi->[$b] =~ /\S/ ) {
 
154
 
 
155
        # inserting new
 
156
        $merged =
 
157
          $session->{plugins}
 
158
          ->dispatch( 'mergeHandler', '+', $ai->[$a], $bi->[$b], $info );
 
159
 
 
160
        #print STDERR "From B: '$bi->[$b]'\n";
 
161
        if ( defined $merged ) {
 
162
            push( @$out, $merged );
 
163
        }
 
164
        else {
 
165
            push( @$out, $bi->[$b] );
 
166
        }
 
167
    }
 
168
    else {
 
169
 
 
170
        # otherwise this insert is not replacing anything
 
171
        #print STDERR "From B: '$bi->[$b]'\n";
 
172
        $merged =
 
173
          $session->{plugins}
 
174
          ->dispatch( 'mergeHandler', ' ', $ai->[$a], $bi->[$b], $info );
 
175
        if ( defined $merged ) {
 
176
            push( @$out, $merged );
 
177
        }
 
178
        else {
 
179
            push( @$out, $bi->[$b] );
 
180
        }
 
181
    }
 
182
}
 
183
 
 
184
=begin TML
 
185
 
 
186
---++ StaticMethod simpleMerge( $a, $b, $sep ) -> \@arr
 
187
 
 
188
Perform a merge of two versions of the same text, returning
 
189
an array of strings representing the blocks in the merged context
 
190
where each string starts with one of "+", "-" or " " depending on
 
191
whether it is an insertion, a deletion, or just text. Insertions
 
192
and deletions alway happen in pairs, as text taken in from either
 
193
version that does not replace text in the other version will simply
 
194
be accepted.
 
195
 
 
196
The granularity of the merge depends on the setting of $sep.
 
197
For example, if it is ="\\n"=, a line-by-line merge will be done.
 
198
$sep characters are retained in the outout.
 
199
 
 
200
=cut
 
201
 
 
202
sub simpleMerge {
 
203
    my ( $ia, $ib, $sep ) = @_;
 
204
 
 
205
    my @a = split( /($sep)/, $ia );
 
206
    my @b = split( /($sep)/, $ib );
 
207
 
 
208
    my $out = [];
 
209
    require Algorithm::Diff;
 
210
    Algorithm::Diff::traverse_balanced(
 
211
        \@a,
 
212
        \@b,
 
213
        {
 
214
            MATCH     => \&_sAcceptA,
 
215
            DISCARD_A => \&_sAcceptA,
 
216
            DISCARD_B => \&_sAcceptB,
 
217
            CHANGE    => \&_sChange
 
218
        },
 
219
        undef, $out,
 
220
        \@a,
 
221
        \@b
 
222
    );
 
223
    return $out;
 
224
}
 
225
 
 
226
sub _sAcceptA {
 
227
    my ( $a, $b, $out, $ai, $bi ) = @_;
 
228
 
 
229
    push( @$out, ' ' . $ai->[$a] );
 
230
}
 
231
 
 
232
sub _sAcceptB {
 
233
    my ( $a, $b, $out, $ai, $bi ) = @_;
 
234
 
 
235
    push( @$out, ' ' . $bi->[$b] );
 
236
}
 
237
 
 
238
sub _sChange {
 
239
    my ( $a, $b, $out, $ai, $bi ) = @_;
 
240
    my $simpleInsert = 0;
 
241
 
 
242
    if ( $ai->[$a] =~ /\S/ ) {
 
243
 
 
244
        # there is some non-white text to delete
 
245
        push( @$out, '-' . $ai->[$a] );
 
246
    }
 
247
    else {
 
248
 
 
249
        # otherwise this insert is not replacing anything
 
250
        $simpleInsert = 1;
 
251
    }
 
252
 
 
253
    if ( !$simpleInsert && $bi->[$b] =~ /\S/ ) {
 
254
 
 
255
        # this insert is replacing something with something
 
256
        push( @$out, '+' . $bi->[$b] );
 
257
    }
 
258
    else {
 
259
 
 
260
        # otherwise it is replacing nothing, or is whitespace or null
 
261
        push( @$out, ' ' . $bi->[$b] );
 
262
    }
 
263
}
 
264
 
 
265
sub _equal {
 
266
    my ( $a, $b ) = @_;
 
267
    return 1 if ( !defined($a) && !defined($b) );
 
268
    return 0 if ( !defined($a) || !defined($b) );
 
269
    return $a eq $b;
 
270
}
 
271
 
 
272
=begin TML
 
273
 
 
274
---++ StaticMethod merge3( $arev, $a, $brev, $b, $crev, $c, $sep,
 
275
                          $session, $info )
 
276
 
 
277
   * =$arev= - rev for common ancestor (id e.g. ver no)
 
278
   * =$a= - common ancestor
 
279
   * =$brev= - rev no for first derivative string (id)
 
280
   * =$b= - first derivative string
 
281
   * =$crev= - rev no for second derivative string (id)
 
282
   * =$c= - second derivative string
 
283
   * =$sep= = separator, string RE e.g. '.*?\n' for lines
 
284
   * =$session= - Foswiki object
 
285
   * =$info= - data block passed to plugins merge handler. Conventionally this will identify the source of the text being merged (the source form field, or undef for the body text)
 
286
 
 
287
Perform a merge of two versions (b and c) of the same text, using
 
288
HTML &lt;div> tags to mark conflicts. a is the common ancestor.
 
289
 
 
290
The granularity of the merge depends on the setting of $sep.
 
291
For example, if it is =".*?\\n"=, a line-by-line merge will be done.
 
292
 
 
293
Where conflicts exist, they are labeled using the provided revision
 
294
numbers.
 
295
 
 
296
The plugins =mergeHandler= is called for each merge.
 
297
 
 
298
Here's a little picture of a 3-way merge:
 
299
 
 
300
      a   <- ancestor
 
301
     / \
 
302
    b   c <- revisions
 
303
     \ /
 
304
      d   <- merged result, returned.
 
305
 
 
306
call it like this:
 
307
<verbatim>
 
308
    my ( $ancestorMeta, $ancestorText ) =
 
309
        $store->readTopic( undef, $webName, $topic, $originalrev );
 
310
    $newText = Foswiki::Merge::merge3(
 
311
        $ancestorText, $prevText, $newText,
 
312
        $originalrev, $rev, "new",
 
313
        '.*?\n' );
 
314
</verbatim>
 
315
 
 
316
=cut
 
317
 
 
318
sub merge3 {
 
319
    my ( $arev, $ia, $brev, $ib, $crev, $ic, $sep, $session, $info ) = @_;
 
320
 
 
321
    $sep = "\r?\n" if ( !defined($sep) );
 
322
 
 
323
    my @a = split( /(.+?$sep)/, $ia );
 
324
    my @b = split( /(.+?$sep)/, $ib );
 
325
    my @c = split( /(.+?$sep)/, $ic );
 
326
    require Algorithm::Diff;
 
327
    my @bdiffs = Algorithm::Diff::sdiff( \@a, \@b );
 
328
    my @cdiffs = Algorithm::Diff::sdiff( \@a, \@c );
 
329
 
 
330
    my $ai   = 0;                 # index into a
 
331
    my $bdi  = 0;                 # index into bdiffs
 
332
    my $cdi  = 0;                 # index into bdiffs
 
333
    my $na   = scalar(@a);
 
334
    my $nbd  = scalar(@bdiffs);
 
335
    my $ncd  = scalar(@cdiffs);
 
336
    my $done = 0;
 
337
    my ( @achunk, @bchunk, @cchunk );
 
338
    my @diffs;                    # (a, b, c)
 
339
 
 
340
    # diffs are of the form [ [ modifier, b_elem, c_elem ] ... ]
 
341
    # where modifiers is one of:
 
342
    #   '+': element (b or c) added
 
343
    #   '-': element (from a) removed
 
344
    #   'u': element unmodified
 
345
    #   'c': element changed (a to b/c)
 
346
 
 
347
    # first, collate the diffs.
 
348
 
 
349
    while ( !$done ) {
 
350
        my $bop = ( $bdi < $nbd ) ? $bdiffs[$bdi][0] : 'x';
 
351
        if ( $bop eq '+' ) {
 
352
            push @bchunk, $bdiffs[ $bdi++ ][2];
 
353
            next;
 
354
        }
 
355
        my $cop = ( $cdi < $ncd ) ? $cdiffs[$cdi][0] : 'x';
 
356
        if ( $cop eq '+' ) {
 
357
            push @cchunk, $cdiffs[ $cdi++ ][2];
 
358
            next;
 
359
        }
 
360
        while ( scalar(@bchunk) || scalar(@cchunk) ) {
 
361
            push @diffs, [ shift @achunk, shift @bchunk, shift @cchunk ];
 
362
        }
 
363
        if ( scalar(@achunk) ) {
 
364
            @achunk = ();
 
365
        }
 
366
        last if ( $bop eq 'x' || $cop eq 'x' );
 
367
 
 
368
        # now that we've dealt with '+' and 'x', the only remaining
 
369
        # operations are '-', 'u', and 'c', which all consume an
 
370
        # element of a, so we should increment them together.
 
371
        my $aline = $bdiffs[$bdi][1];
 
372
        my $bline = $bdiffs[$bdi][2];
 
373
        my $cline = $cdiffs[$cdi][2];
 
374
        push @diffs, [ $aline, $bline, $cline ];
 
375
        $bdi++;
 
376
        $cdi++;
 
377
    }
 
378
 
 
379
    # at this point, both lists should be consumed, unless theres a bug in
 
380
    # Algorithm::Diff. We'll consume whatevers left if necessary though.
 
381
 
 
382
    while ( $bdi < $nbd ) {
 
383
        push @diffs, [ $bdiffs[$bdi][1], undef, $bdiffs[$bdi][2] ];
 
384
        $bdi++;
 
385
    }
 
386
    while ( $cdi < $ncd ) {
 
387
        push @diffs, [ $cdiffs[$cdi][1], undef, $cdiffs[$cdi][2] ];
 
388
        $cdi++;
 
389
    }
 
390
 
 
391
    my ( @aconf, @bconf, @cconf, @merged );
 
392
    my $conflict = 0;
 
393
    my @out;
 
394
    my ( $aline, $bline, $cline );
 
395
 
 
396
    for my $diff (@diffs) {
 
397
        ( $aline, $bline, $cline ) = @$diff;
 
398
        my $ab = _equal( $aline, $bline );
 
399
        my $ac = _equal( $aline, $cline );
 
400
        my $bc = _equal( $bline, $cline );
 
401
        my $dline = undef;
 
402
 
 
403
        if ($bc) {
 
404
 
 
405
            # same change (or no change) in b and c
 
406
            $dline = $bline;
 
407
        }
 
408
        elsif ($ab) {
 
409
 
 
410
            # line did not change in b
 
411
            $dline = $cline;
 
412
        }
 
413
        elsif ($ac) {
 
414
 
 
415
            # line did not change in c
 
416
            $dline = $bline;
 
417
        }
 
418
        else {
 
419
 
 
420
            # line changed in both b and c
 
421
            $conflict = 1;
 
422
        }
 
423
 
 
424
        if ($conflict) {
 
425
 
 
426
            # store up conflicting lines until we get a non-conflicting
 
427
            push @aconf, $aline;
 
428
            push @bconf, $bline;
 
429
            push @cconf, $cline;
 
430
        }
 
431
 
 
432
        if ( defined($dline) ) {
 
433
 
 
434
            # we have a non-conflicting line
 
435
            if ($conflict) {
 
436
 
 
437
                # flush any pending conflict if there is enough
 
438
                # context (at least 3 lines)
 
439
                push( @merged, $dline );
 
440
                if ( @merged > 3 ) {
 
441
                    for my $i ( 0 .. $#merged ) {
 
442
                        pop @aconf;
 
443
                        pop @bconf;
 
444
                        pop @cconf;
 
445
                    }
 
446
                    _handleConflict(
 
447
                        \@out, \@aconf, \@bconf, \@cconf,  $arev,
 
448
                        $brev, $crev,   $sep,    $session, $info
 
449
                    );
 
450
                    $conflict = 0;
 
451
                    push @out, @merged;
 
452
                    @merged = ();
 
453
                }
 
454
            }
 
455
            else {
 
456
 
 
457
                # the line is non-conflicting
 
458
                my $merged =
 
459
                  $session->{plugins}
 
460
                  ->dispatch( 'mergeHandler', ' ', $dline, $dline, $info );
 
461
                if ( defined $merged ) {
 
462
                    push( @out, $merged );
 
463
                }
 
464
                else {
 
465
                    push( @out, $dline );
 
466
                }
 
467
            }
 
468
        }
 
469
        elsif (@merged) {
 
470
            @merged = ();
 
471
        }
 
472
    }
 
473
 
 
474
    if ($conflict) {
 
475
        for my $i ( 0 .. $#merged ) {
 
476
            pop @aconf;
 
477
            pop @bconf;
 
478
            pop @cconf;
 
479
        }
 
480
 
 
481
        _handleConflict(
 
482
            \@out, \@aconf, \@bconf, \@cconf,  $arev,
 
483
            $brev, $crev,   $sep,    $session, $info
 
484
        );
 
485
    }
 
486
    push @out, @merged;
 
487
    @merged = ();
 
488
 
 
489
    #foreach ( @out ) { print STDERR (defined($_) ? $_ : "undefined") . "\n"; }
 
490
 
 
491
    return join( '', @out );
 
492
}
 
493
 
 
494
my $conflictAttrs = { class => 'twikiConflict' };
 
495
 
 
496
# SMELL: internationalisation?
 
497
my $conflictB = CGI::b('CONFLICT');
 
498
 
 
499
sub _handleConflict {
 
500
    my (
 
501
        $out,  $aconf, $bconf, $cconf,   $arev,
 
502
        $brev, $crev,  $sep,   $session, $info
 
503
    ) = @_;
 
504
    my ( @a, @b, @c );
 
505
 
 
506
    @a = grep( $_, @$aconf );
 
507
    @b = grep( $_, @$bconf );
 
508
    @c = grep( $_, @$cconf );
 
509
    my $merged =
 
510
      $session->{plugins}
 
511
      ->dispatch( 'mergeHandler', 'c', join( '', @b ), join( '', @c ), $info );
 
512
    if ( defined $merged ) {
 
513
        push( @$out, $merged );
 
514
    }
 
515
    else {
 
516
        if (@a) {
 
517
            push( @$out,
 
518
                CGI::div( $conflictAttrs, "$conflictB original $arev:" )
 
519
                  . "\n" );
 
520
            push( @$out, @a );
 
521
        }
 
522
        if (@b) {
 
523
            push( @$out,
 
524
                CGI::div( $conflictAttrs,, "$conflictB version $brev:" )
 
525
                  . "\n" );
 
526
            push( @$out, @b );
 
527
        }
 
528
        if (@c) {
 
529
            push( @$out,
 
530
                CGI::div( $conflictAttrs,, "$conflictB version $crev:" )
 
531
                  . "\n" );
 
532
            push( @$out, @c );
 
533
        }
 
534
        push( @$out, CGI::div( $conflictAttrs,, "$conflictB end" ) . "\n" );
 
535
    }
 
536
}
 
537
 
 
538
1;
 
539
__DATA__
 
540
# Module of Foswiki - The Free and Open Source Wiki, http://foswiki.org/
 
541
#
 
542
# Copyright (C) 2008-2009 Foswiki Contributors. All Rights Reserved.
 
543
# Foswiki Contributors are listed in the AUTHORS file in the root
 
544
# of this distribution. NOTE: Please extend that file, not this notice.
 
545
#
 
546
# Additional copyrights apply to some or all of the code in this
 
547
# file as follows:
 
548
#
 
549
# Copyright (C) 2004-2007 TWiki Contributors. All Rights Reserved.
 
550
# TWiki Contributors are listed in the AUTHORS file in the root
 
551
# of this distribution. NOTE: Please extend that file, not this notice.
 
552
#
 
553
# This program is free software; you can redistribute it and/or
 
554
# modify it under the terms of the GNU General Public License
 
555
# as published by the Free Software Foundation; either version 2
 
556
# of the License, or (at your option) any later version. For
 
557
# more details read LICENSE in the root of this distribution.
 
558
#
 
559
# This program is distributed in the hope that it will be useful,
 
560
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
561
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 
562
#
 
563
# As per the GPL, removal of this notice is prohibited.