lib/diff3.php

   1 <?php
   2 // $Id$
   3 // diff3.php
   4 //
   5 // A class for computing three way diffs
   6 //
   7 // Copyright (C) 2001 Geoffrey T. Dairiki <dairiki@dairiki.org>
   8 // You may copy this code freely under the conditions of the GPL.
   9 //
  10
  11 require_once('lib/difflib.php');
  12
  13 class _Diff3_Block {
  14     var $type = 'diff3';
  15
  16     function _Diff3_Block ($orig = false, $final1 = false, $final2 = false) {
  17         $this->orig = $orig ? $orig : array();
  18         $this->final1 = $final1 ? $final1 : array();
  19         $this->final2 = $final2 ? $final2 : array();
  20     }
  21
  22     function merged () {
  23         if (!isset($this->_merged)) {
  24             if ($this->final1 === $this->final2)
  25                 $this->_merged = &$this->final1;
  26             elseif ($this->final1 === $this->orig)
  27                 $this->_merged = &$this->final2;
  28             elseif ($this->final2 === $this->orig)
  29                 $this->_merged = &$this->final1;
  30             else
  31                 $this->_merged = false;
  32         }
  33         return $this->_merged;
  34     }
  35
  36     function is_conflict () {
  37         return $this->merged() === false;
  38     }
  39 }
  40
  41
  42 class _Diff3_CopyBlock extends _Diff3_Block {
  43     var $type = 'copy';
  44
  45     function _Diff3_CopyBlock ($lines = false) {
  46         $this->orig = $lines ? $lines : array();
  47         $this->final1 = &$this->orig;
  48         $this->final2 = &$this->orig;
  49     }
  50
  51     function merged() {
  52         return $this->orig;
  53     }
  54
  55     function is_conflict () {
  56         return false;
  57     }
  58 }
  59
  60 class _Diff3_BlockBuilder {
  61     function _Diff3_BlockBuilder () {
  62         $this->_init();
  63     }
  64
  65     function _init() {
  66         $this->orig = $this->final1 = $this->final2 = array();
  67     }
  68
  69
  70     function _append (&$array, $lines) {
  71         array_splice($array, sizeof($array), 0, $lines);
  72     }
  73
  74     function input($lines) {
  75         if ($lines)
  76             $this->_append($this->orig, $lines);
  77     }
  78
  79     function out1($lines) {
  80         if ($lines)
  81             $this->_append($this->final1, $lines);
  82     }
  83
  84     function out2($lines) {
  85         if ($lines)
  86             $this->_append($this->final2, $lines);
  87     }
  88
  89     function is_empty() {
  90         return !$this->orig && !$this->final1 && !$this->final2;
  91     }
  92
  93     function finish() {
  94         if ($this->is_empty())
  95             return false;
  96         else {
  97             $block = new _Diff3_Block($this->orig, $this->final1, $this->final2);
  98             $this->_init();
  99             return $block;
 100         }
 101     }
 102 };
 103
 104
 105 class Diff3 {
 106     function Diff3 ($orig, $final1, $final2) {
 107         $eng = new _DiffEngine;
 108         $this->ConflictingBlocks = 0;  //Conflict counter
 109         $this->blocks = $this->__diff3($eng->diff($orig, $final1),
 110                                        $eng->diff($orig, $final2));
 111     }
 112
 113     function __diff3($edits1, $edits2) {
 114         $blocks = array();
 115         $bb = new _Diff3_BlockBuilder;
 116
 117         $e1 = current($edits1);
 118         $e2 = current($edits2);
 119         while ($e1 || $e2) {
 120 //          echo "====\n";
 121 //          print_r($e1);
 122 //          print_r($e2);
 123 //          echo "====\n";
 124
 125             if ($e1 && $e2 && $e1->type == 'copy' && $e2->type == 'copy') {
 126                 // We have copy blocks from both diffs.  This is the (only)
 127                 // time we want to emit a diff3 copy block.
 128                 // Flush current diff3 diff block, if any
 129                 if ($block = $bb->finish())
 130                     $blocks[] = $block;
 131
 132                 $ncopy = min($e1->norig(), $e2->norig());
 133                 assert($ncopy > 0);
 134                 $blocks[] = new _Diff3_CopyBlock(array_slice($e1->orig, 0, $ncopy));
 135
 136                 if ($e1->norig() > $ncopy) {
 137                     array_splice($e1->orig, 0, $ncopy);
 138                     array_splice($e1->final, 0, $ncopy);
 139                 }
 140                 else
 141                     $e1 = next($edits1);
 142
 143                 if ($e2->norig() > $ncopy) {
 144                     array_splice($e2->orig, 0, $ncopy);
 145                     array_splice($e2->final, 0, $ncopy);
 146                 }
 147                 else
 148                     $e2 = next($edits2);
 149             }
 150             else {
 151                 if ($e1 && $e2) {
 152                     if ($e1->orig && $e2->orig) {
 153                         $norig = min($e1->norig(), $e2->norig());
 154                         $orig = array_splice($e1->orig, 0, $norig);
 155                         array_splice($e2->orig, 0, $norig);
 156                         $bb->input($orig);
 157                     }
 158
 159                     if ($e1->type == 'copy')
 160                         $bb->out1(array_splice($e1->final, 0, $norig));
 161
 162                     if ($e2->type == 'copy')
 163                         $bb->out2(array_splice($e2->final, 0, $norig));
 164                 }
 165                 if ($e1 && ! $e1->orig) {
 166                     $bb->out1($e1->final);
 167                     $e1 = next($edits1);
 168                 }
 169                 if ($e2 && ! $e2->orig) {
 170                     $bb->out2($e2->final);
 171                     $e2 = next($edits2);
 172                 }
 173             }
 174         }
 175
 176         if ($block = $bb->finish())
 177             $blocks[] = $block;
 178
 179         return $blocks;
 180     }
 181
 182
 183     function merged_output($label1 = false, $label2 = false) {
 184         $lines = array();
 185         foreach ($this->blocks as $block) {
 186             if ($block->is_conflict()) {
 187                 // FIXME: this should probably be moved somewhere else...
 188                 $lines = array_merge($lines,
 189                                      array("<<<<<<<" . ($label1 ? " $label1" : '')),
 190                                      $block->final1,
 191                                      array("======="),
 192                                      $block->final2,
 193                                      array(">>>>>>>" . ($label2 ? " $label2" : '')));
 194                 $this->ConflictingBlocks++;
 195             }
 196             else {
 197                 $lines = array_merge($lines, $block->merged());
 198             }
 199         }
 200         return $lines;
 201     }
 202 }
 203
 204 // Local Variables:
 205 // mode: php
 206 // tab-width: 8
 207 // c-basic-offset: 4
 208 // c-hanging-comment-ender-p: nil
 209 // indent-tabs-mode: nil
 210 // End:
 211 ?>