xref: /web-bugs/src/Horde/Text/Diff/ThreeWay.php (revision e3c4b0ac) 
1<?php
2/**
3 * A class for computing three way merges.
4 *
5 * Copyright 2007-2017 Horde LLC (http://www.horde.org/)
6 *
7 * See the enclosed file COPYING for license information (LGPL). If you did
8 * not receive this file, see http://www.horde.org/licenses/lgpl21.
9 *
10 * @package Text_Diff
11 * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
12 */
13class Horde_Text_Diff_ThreeWay
14{
15    /**
16     * Array of changes.
17     *
18     * @var array
19     */
20    protected $_edits;
21
22    /**
23     * Conflict counter.
24     *
25     * @var integer
26     */
27    protected $_conflictingBlocks = 0;
28
29    /**
30     * Computes diff between 3 sequences of strings.
31     *
32     * @param array $orig    The original lines to use.
33     * @param array $final1  The first version to compare to.
34     * @param array $final2  The second version to compare to.
35     */
36    public function __construct($orig, $final1, $final2)
37    {
38        if (extension_loaded('xdiff')) {
39            $engine = new Horde_Text_Diff_Engine_Xdiff();
40        } else {
41            $engine = new Horde_Text_Diff_Engine_Native();
42        }
43
44        $this->_edits = $this->_diff3($engine->diff($orig, $final1),
45                                      $engine->diff($orig, $final2));
46    }
47
48    /**
49     */
50    public function mergedOutput($label1 = false, $label2 = false)
51    {
52        $lines = array();
53        foreach ($this->_edits as $edit) {
54            if ($edit->isConflict()) {
55                /* FIXME: this should probably be moved somewhere else. */
56                $lines = array_merge($lines,
57                                     array('<<<<<<<' . ($label1 ? ' ' . $label1 : '')),
58                                     $edit->final1,
59                                     array("======="),
60                                     $edit->final2,
61                                     array('>>>>>>>' . ($label2 ? ' ' . $label2 : '')));
62                $this->_conflictingBlocks++;
63            } else {
64                $lines = array_merge($lines, $edit->merged());
65            }
66        }
67
68        return $lines;
69    }
70
71    /**
72     */
73    protected function _diff3($edits1, $edits2)
74    {
75        $edits = array();
76        $bb = new Horde_Text_Diff_ThreeWay_BlockBuilder();
77
78        $e1 = current($edits1);
79        $e2 = current($edits2);
80        while ($e1 || $e2) {
81            if ($e1 && $e2 &&
82                $e1 instanceof Horde_Text_Diff_Op_Copy &&
83                $e2 instanceof Horde_Text_Diff_Op_Copy) {
84                /* We have copy blocks from both diffs. This is the (only)
85                 * time we want to emit a diff3 copy block.  Flush current
86                 * diff3 diff block, if any. */
87                if ($edit = $bb->finish()) {
88                    $edits[] = $edit;
89                }
90
91                $ncopy = min($e1->norig(), $e2->norig());
92                assert($ncopy > 0);
93                $edits[] = new Horde_Text_Diff_ThreeWay_Op_Copy(array_slice($e1->orig, 0, $ncopy));
94
95                if ($e1->norig() > $ncopy) {
96                    array_splice($e1->orig, 0, $ncopy);
97                    array_splice($e1->final, 0, $ncopy);
98                } else {
99                    $e1 = next($edits1);
100                }
101
102                if ($e2->norig() > $ncopy) {
103                    array_splice($e2->orig, 0, $ncopy);
104                    array_splice($e2->final, 0, $ncopy);
105                } else {
106                    $e2 = next($edits2);
107                }
108            } else {
109                if ($e1 && $e2) {
110                    if ($e1->orig && $e2->orig) {
111                        $norig = min($e1->norig(), $e2->norig());
112                        $orig = array_splice($e1->orig, 0, $norig);
113                        array_splice($e2->orig, 0, $norig);
114                        $bb->input($orig);
115                    }
116
117                    if ($e1 instanceof Horde_Text_Diff_Op_Copy) {
118                        $bb->out1(array_splice($e1->final, 0, $norig));
119                    }
120
121                    if ($e2 instanceof Horde_Text_Diff_Op_Copy) {
122                        $bb->out2(array_splice($e2->final, 0, $norig));
123                    }
124                }
125
126                if ($e1 && ! $e1->orig) {
127                    $bb->out1($e1->final);
128                    $e1 = next($edits1);
129                }
130                if ($e2 && ! $e2->orig) {
131                    $bb->out2($e2->final);
132                    $e2 = next($edits2);
133                }
134            }
135        }
136
137        if ($edit = $bb->finish()) {
138            $edits[] = $edit;
139        }
140
141        return $edits;
142    }
143}
144