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