lib/diff3.php

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