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     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     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     function merged()
  55     {
  56         return $this->orig;
  57     }
  58
  59     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     function _init()
  77     {
  78         $this->orig = $this->final1 = $this->final2 = array();
  79     }
  80
  81     function _append(&$array, $lines)
  82     {
  83         array_splice($array, sizeof($array), 0, $lines);
  84     }
  85
  86     function input($lines)
  87     {
  88         if ($lines)
  89             $this->_append($this->orig, $lines);
  90     }
  91
  92     function out1($lines)
  93     {
  94         if ($lines)
  95             $this->_append($this->final1, $lines);
  96     }
  97
  98     function out2($lines)
  99     {
 100         if ($lines)
 101             $this->_append($this->final2, $lines);
 102     }
 103
 104     function is_empty()
 105     {
 106         return !$this->orig && !$this->final1 && !$this->final2;
 107     }
 108
 109     function finish()
 110     {
 111         if ($this->is_empty())
 112             return false;
 113         else {
 114             $block = new _Diff3_Block($this->orig, $this->final1, $this->final2);
 115             $this->_init();
 116             return $block;
 117         }
 118     }
 119 }
 120
 121 class Diff3
 122 {
 123     function __construct($orig, $final1, $final2)
 124     {
 125         $eng = new _DiffEngine;
 126         $this->ConflictingBlocks = 0; //Conflict counter
 127         $this->blocks = $this->__diff3($eng->diff($orig, $final1),
 128             $eng->diff($orig, $final2));
 129     }
 130
 131     function __diff3($edits1, $edits2)
 132     {
 133         $blocks = array();
 134         $bb = new _Diff3_BlockBuilder;
 135
 136         $e1 = current($edits1);
 137         $e2 = current($edits2);
 138         while ($e1 || $e2) {
 139 //          echo "====\n";
 140 //          print_r($e1);
 141 //          print_r($e2);
 142 //          echo "====\n";
 143
 144             if ($e1 && $e2 && $e1->type == 'copy' && $e2->type == 'copy') {
 145                 // We have copy blocks from both diffs.  This is the (only)
 146                 // time we want to emit a diff3 copy block.
 147                 // Flush current diff3 diff block, if any
 148                 if ($block = $bb->finish())
 149                     $blocks[] = $block;
 150
 151                 $ncopy = min($e1->norig(), $e2->norig());
 152                 assert($ncopy > 0);
 153                 $blocks[] = new _Diff3_CopyBlock(array_slice($e1->orig, 0, $ncopy));
 154
 155                 if ($e1->norig() > $ncopy) {
 156                     array_splice($e1->orig, 0, $ncopy);
 157                     array_splice($e1->final, 0, $ncopy);
 158                 } else
 159                     $e1 = next($edits1);
 160
 161                 if ($e2->norig() > $ncopy) {
 162                     array_splice($e2->orig, 0, $ncopy);
 163                     array_splice($e2->final, 0, $ncopy);
 164                 } else
 165                     $e2 = next($edits2);
 166             } else {
 167                 if ($e1 && $e2) {
 168                     if ($e1->orig && $e2->orig) {
 169                         $norig = min($e1->norig(), $e2->norig());
 170                         $orig = array_splice($e1->orig, 0, $norig);
 171                         array_splice($e2->orig, 0, $norig);
 172                         $bb->input($orig);
 173                     }
 174
 175                     if ($e1->type == 'copy')
 176                         $bb->out1(array_splice($e1->final, 0, $norig));
 177
 178                     if ($e2->type == 'copy')
 179                         $bb->out2(array_splice($e2->final, 0, $norig));
 180                 }
 181                 if ($e1 && !$e1->orig) {
 182                     $bb->out1($e1->final);
 183                     $e1 = next($edits1);
 184                 }
 185                 if ($e2 && !$e2->orig) {
 186                     $bb->out2($e2->final);
 187                     $e2 = next($edits2);
 188                 }
 189             }
 190         }
 191
 192         if ($block = $bb->finish())
 193             $blocks[] = $block;
 194
 195         return $blocks;
 196     }
 197
 198     function merged_output($label1 = false, $label2 = false)
 199     {
 200         $lines = array();
 201         foreach ($this->blocks as $block) {
 202             if ($block->is_conflict()) {
 203                 // FIXME: this should probably be moved somewhere else...
 204                 $lines = array_merge($lines,
 205                     array("<<<<<<<" . ($label1 ? " $label1" : '')),
 206                     $block->final1,
 207                     array("======="),
 208                     $block->final2,
 209                     array(">>>>>>>" . ($label2 ? " $label2" : '')));
 210                 $this->ConflictingBlocks++;
 211             } else {
 212                 $lines = array_merge($lines, $block->merged());
 213             }
 214         }
 215         return $lines;
 216     }
 217 }
 218
 219 // Local Variables:
 220 // mode: php
 221 // tab-width: 8
 222 // c-basic-offset: 4
 223 // c-hanging-comment-ender-p: nil
 224 // indent-tabs-mode: nil
 225 // End: