| 0,0 → 1,364 |
|---|
| <?php |
| // WebSVN - Subversion repository viewing via the web using PHP |
| // Copyright (C) 2004-2006 Tim Armes |
| // |
| // This program is free software; you can redistribute it and/or modify |
| // it under the terms of the GNU General Public License as published by |
| // the Free Software Foundation; either version 2 of the License, or |
| // (at your option) any later version. |
| // |
| // This program is distributed in the hope that it will be useful, |
| // but WITHOUT ANY WARRANTY; without even the implied warranty of |
| // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| // GNU General Public License for more details. |
| // |
| // You should have received a copy of the GNU General Public License |
| // along with this program; if not, write to the Free Software |
| // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| // |
| // -- |
| // |
| // diff_util.php |
| // |
| // help diff_inc.php to make sensible changes from added and deleted diff lines |
| // These lines are automatically paired and also inline diff is performed to show |
| // insertions/deletions on one line. diff_inc.php must have all Horde_Text_Diff |
| // requirements met (include_once statements). |
| |
| // Interface for diffing function |
| class LineDiffInterface { |
| // similarity 1 means that strings are very close to each other |
| // 0 means totally different |
| function lineSimilarity($text1, $text2) { |
| assert(false); |
| } |
| |
| // return array($left, $right) annotated with <ins> and <del> |
| function inlineDiff($text1, $highlighted1, $text2, $highlighted2, $highlighted) { |
| assert(false); |
| } |
| } |
| |
| // Default line diffing function |
| class LineDiff extends LineDiffInterface { |
| |
| private bool $ignoreWhitespace; |
| |
| function __construct($ignoreWhitespace) { |
| $this->ignoreWhitespace = $ignoreWhitespace; |
| } |
| |
| // {{{ levenshtein2 |
| // levenshtein edit distance, on small strings use php function |
| // on large strings approximate distance using words |
| // computed by dynamic programming |
| function levenshtein2($str1, $str2) { |
| if (strlen($str1) < 255 && strlen($str2) < 255) { |
| return levenshtein($str1, $str2); |
| } |
| |
| $l1 = explode(' ', $str1); |
| $l2 = explode(' ', $str2); |
| |
| $n = count($l1); |
| $m = count($l2); |
| $d = array_fill(0, $n + 1, array_fill(0, $m + 1, 0)); |
| |
| for ($i = 1; $i < $n + 1; $i++) { |
| $d[$i][0] = $i; |
| } |
| for ($j = 1; $j < $m + 1; $j++) { |
| $d[0][$j] = $j; |
| } |
| |
| for ($i = 1; $i < $n + 1; $i++) { |
| for ($j = 1; $j < $m + 1; $j++) { |
| $c = ($l1[$i - 1] == $l2[$j - 1]) ? 0 : strlen($l1[$i - 1]) + strlen($l2[$j - 1]); |
| $d[$i][$j] = min($d[$i - 1][$j] + 1, $d[$i][$j - 1] + 1, $d[$i - 1][$j - 1] + $c); |
| } |
| } |
| |
| return $d[$n][$m]; |
| } |
| // }}} |
| |
| // {{{ lineSimilarity |
| function lineSimilarity($text1, $text2) { |
| $distance = $this->levenshtein2($text1, $text2); |
| return max(0.0, 1.0 - $distance / (strlen($text1) + strlen($text2) + 4)); |
| } |
| // }}} |
| |
| // {{{ tokenize whole line into words |
| // note that separators are returned as tokens of length 1 |
| // and if $ignoreWhitespace is true, consecutive whitespaces are returned as one token |
| function tokenize($string, $highlighted, $ignoreWhitespace) { |
| $html = array('<' => '>', '&' => ';'); |
| $whitespaces = array("\t","\n","\r",' '); |
| $separators = array('.','-','+','*','/','<','>','?','(',')','&','/','{','}','[',']',':',';'); |
| $data = array(); |
| $segment = ''; |
| $segmentIsWhitespace = true; |
| $count = strlen($string); |
| for ($i = 0; $i < $count; $i++) { |
| $c = $string[$i]; |
| if ($highlighted && array_key_exists($c, $html)) { |
| if ($segment != '') { |
| $data[] = $segment; |
| } |
| // consider html tags and entities as a single token |
| $endchar = $html[$c]; |
| $segment = $c; |
| do { |
| $i++; |
| $c = $string[$i]; |
| $segment .= $c; |
| } while ($c != $endchar && $i < $count - 1); |
| $data[] = $segment; |
| $segment = ''; |
| $segmentIsWhitespace = false; |
| } else if (in_array($c, $separators) || (!$ignoreWhitespace && in_array($c, $whitespaces))) { |
| // if it is separator or whitespace and we do not consider consecutive whitespaces |
| if ($segment != '') { |
| $data[] = $segment; |
| } |
| $data[] = $c; |
| $segment = ''; |
| $segmentIsWhitespace = true; |
| } else if (in_array($c, $whitespaces)) { |
| // if it is whitespace and we consider consecutive whitespaces as one token |
| if (!$segmentIsWhitespace) { |
| $data[] = $segment; |
| $segment = ''; |
| $segmentIsWhitespace = true; |
| } |
| $segment .= $c; |
| } else { |
| // no separator or whitespace |
| if ($segmentIsWhitespace && $segment != '') { |
| $data[] = $segment; |
| $segment = ''; |
| } |
| $segment .= $c; |
| $segmentIsWhitespace = false; |
| } |
| } |
| if ($segment != '') { |
| $data[] = $segment; |
| } |
| return $data; |
| } |
| // }}} |
| |
| // {{{ lineDiff |
| function inlineDiff($text1, $highlighted1, $text2, $highlighted2, $highlighted) { |
| $whitespaces = array(' ', "\t", "\n", "\r"); |
| |
| $do_diff = true; |
| |
| if ($text1 == '' || $text2 == '') { |
| $do_diff = false; |
| } |
| |
| if ($this->ignoreWhitespace && (str_replace($whitespaces, array(), $text1) == str_replace($whitespaces, array(), $text2))) { |
| $do_diff = false; |
| } |
| |
| // Exit gracefully if loading of Horde_Text_Diff failed |
| if (!class_exists('Horde_Text_Diff') || !class_exists('Horde_Text_Diff_Mapped')) { |
| $do_diff = false; |
| } |
| |
| // Return highlighted lines without doing inline diff |
| if (!$do_diff) { |
| return array($highlighted1, $highlighted2); |
| } |
| |
| $tokens1 = $this->tokenize($highlighted1, $highlighted, $this->ignoreWhitespace); |
| $tokens2 = $this->tokenize($highlighted2, $highlighted, $this->ignoreWhitespace); |
| |
| if (!$this->ignoreWhitespace) { |
| $diff = new Horde_Text_Diff('Native', array($tokens1, $tokens2)); |
| } else { |
| // we need to create mapped parts for MappedDiff |
| $mapped1 = array(); |
| foreach ($tokens1 as $token) { |
| $mapped1[] = str_replace($whitespaces, array(), $token); |
| } |
| $mapped2 = array(); |
| foreach ($tokens2 as $token) { |
| $mapped2[] = str_replace($whitespaces, array(), $token); |
| } |
| $diff = new Horde_Text_Diff_Mapped('Native', array($tokens1, $tokens2, $mapped1, $mapped2)); |
| } |
| |
| // now, get the diff and annotate text |
| $edits = $diff->getDiff(); |
| |
| $line1 = ''; |
| $line2 = ''; |
| foreach ($edits as $edit) { |
| if ($edit instanceof Horde_Text_Diff_Op_Copy) { |
| $line1 .= implode('', $edit->orig); |
| $line2 .= implode('', $edit->final); |
| } else if ($edit instanceof Horde_Text_Diff_Op_Delete) { |
| $line1 .= '<del>'.implode('', $edit->orig).'</del>'; |
| } else if ($edit instanceof Horde_Text_Diff_Op_Add) { |
| $line2 .= '<ins>'.implode('', $edit->final).'</ins>'; |
| } else if ($edit instanceof Horde_Text_Diff_Op_Change) { |
| $line1 .= '<del>'.implode('', $edit->orig).'</del>'; |
| $line2 .= '<ins>'.implode('', $edit->final).'</ins>'; |
| } else { |
| assert(false); |
| } |
| } |
| return array($line1, $line2); |
| } |
| // }}} |
| } |
| |
| // Class for computing sensibly added/deleted block of lines. |
| class SensibleLineChanges { |
| var $_added = array(); |
| var $_deleted = array(); |
| var $_lineDiff = null; |
| |
| function __construct($lineDiff) { |
| $this->_lineDiff = $lineDiff; |
| } |
| |
| function addDeletedLine($text, $highlighted_text, $lineno) { |
| $this->_deleted[] = array($text, $highlighted_text, $lineno); |
| } |
| |
| function addAddedLine($text, $highlighted_text, $lineno) { |
| $this->_added[] = array($text, $highlighted_text, $lineno); |
| } |
| |
| // this function computes simple match - first min(deleted,added) lines are marked as changed |
| // it is intended to be run instead of _computeBestMatching if the diff is too big |
| function _computeFastMatching($n, $m) { |
| $result = array(); |
| $q = 0; |
| while ($q < $n && $q < $m) { |
| $result[] = array($this->_deleted[$q], $this->_added[$q]); |
| $q++; |
| } |
| while ($q < $n) { |
| $result[] = array($this->_deleted[$q], null); |
| $q++; |
| } |
| while ($q < $m) { |
| $result[] = array(null, $this->_added[$q]); |
| $q++; |
| } |
| return $result; |
| } |
| |
| // {{{ _computeBestMatching |
| // dynamically compute best matching |
| // note that this is O(n*m) * O(line similarity) |
| function _computeBestMatching() { |
| $n = count($this->_deleted); |
| $m = count($this->_added); |
| |
| // if the computation will be slow, just run fast algorithm |
| if ($n * $m > 10000) { |
| return $this->_computeFastMatching($n, $m); |
| } |
| |
| // dyn[$i][$j] holds best sum of similarities we can obtain if we match |
| // first $i deleted lines and first $j added lines |
| $dyn = array_fill(0, $n + 1, array_fill(0, $m + 1, 0.0)); |
| // backlinks, so we can reconstruct best layout easily |
| $back = array_fill(0, $n + 1, array_fill(0, $m + 1, -1)); |
| |
| // if there is no similarity, prefer adding/deleting lines |
| $value_del = 0.1; |
| $value_add = 0.1; |
| |
| // initialize arrays |
| for ($i = 1; $i <= $n; $i++) { |
| $back[$i][0] = 0; |
| $dyn[$i][0] = $value_del * $i; |
| } |
| for ($j = 1; $j <= $m; $j++) { |
| $back[0][$j] = 1; |
| $dyn[0][$j] = $value_add * $j; |
| } |
| |
| // main dynamic programming |
| for ($i = 1; $i <= $n; $i++) { |
| for ($j = 1; $j <= $m; $j++) { |
| $best = - 1.0; |
| $b = -1; |
| if ($dyn[$i - 1][$j] + $value_del >= $best) { |
| $b = 0; |
| $best = $dyn[$i - 1][$j] + $value_del; |
| } |
| if ($dyn[$i][$j - 1] + $value_add >= $best) { |
| $b = 1; |
| $best = $dyn[$i][$j - 1] + $value_add; |
| } |
| $sim = $this->_lineDiff->lineSimilarity($this->_deleted[$i - 1][0], $this->_added[$j - 1][0]); |
| if ($dyn[$i - 1][$j - 1] + $sim >= $best) { |
| $b = 2; |
| $best = $dyn[$i - 1][$j - 1] + $sim; |
| } |
| $back[$i][$j] = $b; |
| $dyn[$i][$j] = $best; |
| } |
| } |
| |
| // compute layout for best result |
| $i = $n; |
| $j = $m; |
| $result = array(); |
| |
| while ($i + $j >= 1) { |
| switch($back[$i][$j]) { |
| case 2: array_push($result, array($this->_deleted[$i - 1], $this->_added[$j - 1])); |
| $i--; |
| $j--; |
| break; |
| case 1: array_push($result, array(null, $this->_added[$j - 1])); |
| $j--; |
| break; |
| case 0: array_push($result, array($this->_deleted[$i - 1], null)); |
| $i--; |
| break; |
| default: |
| assert(false); |
| } |
| } |
| return array_reverse($result); |
| } |
| // }}} |
| |
| // {{{ addChangesToListing |
| // add computed changes to the listing |
| function addChangesToListing(&$listingHelper, $highlighted) { |
| $matching = $this->_computeBestMatching(); |
| foreach ($matching as $change) { |
| if ($change[1] == null) { |
| // deleted -- preserve original highlighted text |
| $listingHelper->addDeletedLine($change[0][1], $change[0][2]); |
| } else if ($change[0] == null) { |
| // added -- preserve original highlighted text |
| $listingHelper->addAddedLine($change[1][1], $change[1][2]); |
| } else { |
| // this is fully changed line, make inline diff |
| $diff = $this->_lineDiff->inlineDiff($change[0][0], $change[0][1], $change[1][0], $change[1][1], $highlighted); |
| $listingHelper->addChangedLine($diff[0], $change[0][2], $diff[1], $change[1][2]); |
| } |
| } |
| $this->clear(); |
| } |
| // }}} |
| |
| function clear() { |
| $this->_added = array(); |
| $this->_deleted = array(); |
| } |
| } |
| |