Page MenuHomePhorge
Differential D25031 Diff 83 externals/diff_match_patch/diff_match_patch.php

Changeset View

Standalone View

View Options

externals/diff_match_patch/diff_match_patch.php

Context not available.
// Trim off common suffix (speedup) // Trim off common suffix (speedup)
$commonlength = $this->diff_commonSuffix($text1, $text2); $commonlength = $this->diff_commonSuffix($text1, $text2);
$commonsuffix = mb_substr($text1, mb_strlen($text1) - $commonlength); $commonsuffix = mb_substr($text1, mbstrlen($text1) - $commonlength);
$text1 = mb_substr($text1, 0, mb_strlen($text1) - $commonlength); $text1 = mb_substr($text1, 0, mbstrlen($text1) - $commonlength);
$text2 = mb_substr($text2, 0, mb_strlen($text2) - $commonlength); $text2 = mb_substr($text2, 0, mbstrlen($text2) - $commonlength);
// Compute the diff on the middle block // Compute the diff on the middle block
$diffs = $this->diff_compute($text1, $text2, $checklines); $diffs = $this->diff_compute($text1, $text2, $checklines);
Context not available.
return array ( array ( DIFF_DELETE, $text1 ) ); return array ( array ( DIFF_DELETE, $text1 ) );
} }
$longtext = mb_strlen($text1) > mb_strlen($text2) ? $text1 : $text2; $longtext = mbstrlen($text1) > mbstrlen($text2) ? $text1 : $text2;
$shorttext = mb_strlen($text1) > mb_strlen($text2) ? $text2 : $text1; $shorttext = mbstrlen($text1) > mbstrlen($text2) ? $text2 : $text1;
$i = mb_strpos($longtext, $shorttext); $i = mb_strpos($longtext, $shorttext);
if ($i !== false) { if ($i !== false) {
// Shorter text is inside the longer text (speedup) // Shorter text is inside the longer text (speedup)
$diffs = array ( $diffs = array (
array ( DIFF_INSERT, mb_substr($longtext, 0, $i) ), array ( DIFF_INSERT, mb_substr($longtext, 0, $i) ),
array ( DIFF_EQUAL, $shorttext ), array ( DIFF_EQUAL, $shorttext ),
array ( DIFF_INSERT, mb_substr($longtext, $i +mb_strlen($shorttext)) ) array ( DIFF_INSERT, mb_substr($longtext, $i +mbstrlen($shorttext)) )
); );
// Swap insertions for deletions if diff is reversed. // Swap insertions for deletions if diff is reversed.
if (mb_strlen($text1) > mb_strlen($text2)) { if (mbstrlen($text1) > mbstrlen($text2)) {
$diffs[0][0] = $diffs[2][0] = DIFF_DELETE; $diffs[0][0] = $diffs[2][0] = DIFF_DELETE;
} }
return $diffs; return $diffs;
Context not available.
} }
// Perform a real diff. // Perform a real diff.
if ($checklines && (mb_strlen($text1) < 100 || mb_strlen($text2) < 100)) { if ($checklines && (mbstrlen($text1) < 100 || mbstrlen($text2) < 100)) {
// Too trivial for the overhead. // Too trivial for the overhead.
$checklines = false; $checklines = false;
} }
Context not available.
$lineEnd = -1; $lineEnd = -1;
// Keeping our own length variable is faster than looking it up. // Keeping our own length variable is faster than looking it up.
$lineArrayLength = count($lineArray); $lineArrayLength = count($lineArray);
while ($lineEnd < mb_strlen($text) - 1) { while ($lineEnd < mbstrlen($text) - 1) {
$lineEnd = mb_strpos($text, "\n", $lineStart); $lineEnd = mb_strpos($text, "\n", $lineStart);
if ($lineEnd === false) { if ($lineEnd === false) {
$lineEnd = mb_strlen($text) - 1; $lineEnd = mbstrlen($text) - 1;
} }
$line = mb_substr($text, $lineStart, $lineEnd +1 -$lineStart); $line = mb_substr($text, $lineStart, $lineEnd +1 -$lineStart);
$lineStart = $lineEnd +1; $lineStart = $lineEnd +1;
Context not available.
for ($x = 0; $x < count($diffs); $x++) { for ($x = 0; $x < count($diffs); $x++) {
$chars = $diffs[$x][1]; $chars = $diffs[$x][1];
$text = array (); $text = array ();
for ($y = 0; $y < mb_strlen($chars); $y++) { for ($y = 0; $y < mbstrlen($chars); $y++) {
$text[$y] = $lineArray[charCodeAt($chars, $y)]; $text[$y] = $lineArray[charCodeAt($chars, $y)];
} }
$diffs[$x][1] = implode('',$text); $diffs[$x][1] = implode('',$text);
Context not available.
$ms_end = microtime(true) + $this->Diff_Timeout; $ms_end = microtime(true) + $this->Diff_Timeout;
// Cache the text lengths to prevent multiple calls. // Cache the text lengths to prevent multiple calls.
$text1_length = mb_strlen($text1); $text1_length = mbstrlen($text1);
$text2_length = mb_strlen($text2); $text2_length = mbstrlen($text2);
$max_d = $text1_length + $text2_length -1; $max_d = $text1_length + $text2_length -1;
$doubleEnd = $this->Diff_DualThreshold * 2 < $max_d; $doubleEnd = $this->Diff_DualThreshold * 2 < $max_d;
$v_map1 = array(); $v_map1 = array();
Context not available.
*/ */
function diff_path1($v_map, $text1, $text2) { function diff_path1($v_map, $text1, $text2) {
$path = array (); $path = array ();
$x = mb_strlen($text1); $x = mbstrlen($text1);
$y = mb_strlen($text2); $y = mbstrlen($text2);
/** @type {number?} */ /** @type {number?} */
$last_op = null; $last_op = null;
for ($d = count($v_map) - 2; $d >= 0; $d--) { for ($d = count($v_map) - 2; $d >= 0; $d--) {
Context not available.
function diff_path2($v_map, $text1, $text2) { function diff_path2($v_map, $text1, $text2) {
$path = array (); $path = array ();
$pathLength = 0; $pathLength = 0;
$x = mb_strlen($text1); $x = mbstrlen($text1);
$y = mb_strlen($text2); $y = mbstrlen($text2);
/** @type {number?} */ /** @type {number?} */
$last_op = null; $last_op = null;
for ($d = count($v_map) - 2; $d >= 0; $d--) { for ($d = count($v_map) - 2; $d >= 0; $d--) {
Context not available.
if (isset ($v_map[$d][($x -1) . ',' . $y])) { if (isset ($v_map[$d][($x -1) . ',' . $y])) {
$x--; $x--;
if ($last_op === DIFF_DELETE) { if ($last_op === DIFF_DELETE) {
$path[$pathLength -1][1] .= $text1[mb_strlen($text1) - $x -1]; $path[$pathLength -1][1] .= $text1[mbstrlen($text1) - $x -1];
} else { } else {
$path[$pathLength++] = array ( $path[$pathLength++] = array (
DIFF_DELETE, DIFF_DELETE,
$text1[mb_strlen($text1) - $x -1] $text1[mbstrlen($text1) - $x -1]
); );
} }
$last_op = DIFF_DELETE; $last_op = DIFF_DELETE;
Context not available.
elseif (isset ($v_map[$d][$x . ',' . ($y -1)])) { elseif (isset ($v_map[$d][$x . ',' . ($y -1)])) {
$y--; $y--;
if ($last_op === DIFF_INSERT) { if ($last_op === DIFF_INSERT) {
$path[$pathLength -1][1] .= $text2[mb_strlen($text2) - $y -1]; $path[$pathLength -1][1] .= $text2[mbstrlen($text2) - $y -1];
} else { } else {
$path[$pathLength++] = array ( $path[$pathLength++] = array (
DIFF_INSERT, DIFF_INSERT,
$text2[mb_strlen($text2) - $y -1] $text2[mbstrlen($text2) - $y -1]
); );
} }
$last_op = DIFF_INSERT; $last_op = DIFF_INSERT;
Context not available.
// throw new Error('No diagonal. Can\'t happen. (diff_path2)'); // throw new Error('No diagonal. Can\'t happen. (diff_path2)');
//} //}
if ($last_op === DIFF_EQUAL) { if ($last_op === DIFF_EQUAL) {
$path[$pathLength -1][1] .= $text1[mb_strlen($text1) - $x -1]; $path[$pathLength -1][1] .= $text1[mbstrlen($text1) - $x -1];
} else { } else {
$path[$pathLength++] = array ( $path[$pathLength++] = array (
DIFF_EQUAL, DIFF_EQUAL,
$text1[mb_strlen($text1) - $x -1] $text1[mbstrlen($text1) - $x -1]
); );
} }
$last_op = DIFF_EQUAL; $last_op = DIFF_EQUAL;
Context not available.
* text2 and the common middle. Or null if there was no match. * text2 and the common middle. Or null if there was no match.
*/ */
function diff_halfMatch($text1, $text2) { function diff_halfMatch($text1, $text2) {
$longtext = mb_strlen($text1) > mb_strlen($text2) ? $text1 : $text2; $longtext = mbstrlen($text1) > mbstrlen($text2) ? $text1 : $text2;
$shorttext = mb_strlen($text1) > mb_strlen($text2) ? $text2 : $text1; $shorttext = mbstrlen($text1) > mbstrlen($text2) ? $text2 : $text1;
if (mb_strlen($longtext) < 10 || mb_strlen($shorttext) < 1) { if (mbstrlen($longtext) < 10 || mbstrlen($shorttext) < 1) {
return null; // Pointless. return null; // Pointless.
} }
// First check if the second quarter is the seed for a half-match. // First check if the second quarter is the seed for a half-match.
$hm1 = $this->diff_halfMatchI($longtext, $shorttext, ceil(mb_strlen($longtext) / 4)); $hm1 = $this->diff_halfMatchI($longtext, $shorttext, ceil(mbstrlen($longtext) / 4));
// Check again based on the third quarter. // Check again based on the third quarter.
$hm2 = $this->diff_halfMatchI($longtext, $shorttext, ceil(mb_strlen($longtext) / 2)); $hm2 = $this->diff_halfMatchI($longtext, $shorttext, ceil(mbstrlen($longtext) / 2));
if (!$hm1 && !$hm2) { if (!$hm1 && !$hm2) {
return null; return null;
Context not available.
$hm = $hm2; $hm = $hm2;
} else { } else {
// Both matched. Select the longest. // Both matched. Select the longest.
$hm = mb_strlen($hm1[4]) > mb_strlen($hm2[4]) ? $hm1 : $hm2; $hm = mbstrlen($hm1[4]) > mbstrlen($hm2[4]) ? $hm1 : $hm2;
} }
// A half-match was found, sort out the return data. // A half-match was found, sort out the return data.
if (mb_strlen($text1) > mb_strlen($text2)) { if (mbstrlen($text1) > mbstrlen($text2)) {
$text1_a = $hm[0]; $text1_a = $hm[0];
$text1_b = $hm[1]; $text1_b = $hm[1];
$text2_a = $hm[2]; $text2_a = $hm[2];
Context not available.
*/ */
function diff_halfMatchI($longtext, $shorttext, $i) { function diff_halfMatchI($longtext, $shorttext, $i) {
// Start with a 1/4 length mb_substring at position i as a seed. // Start with a 1/4 length mb_substring at position i as a seed.
$seed = mb_substr($longtext, $i, floor(mb_strlen($longtext) / 4)); $seed = mb_substr($longtext, $i, floor(mbstrlen($longtext) / 4));
$j = -1; $j = -1;
$best_common = ''; $best_common = '';
Context not available.
while ( ($j = mb_strpos($shorttext, $seed, $j + 1)) !== false ) { while ( ($j = mb_strpos($shorttext, $seed, $j + 1)) !== false ) {
$prefixLength = $this->diff_commonPrefix(mb_substr($longtext, $i), mb_substr($shorttext, $j)); $prefixLength = $this->diff_commonPrefix(mb_substr($longtext, $i), mb_substr($shorttext, $j));
$suffixLength = $this->diff_commonSuffix(mb_substr($longtext, 0, $i), mb_substr($shorttext, 0, $j)); $suffixLength = $this->diff_commonSuffix(mb_substr($longtext, 0, $i), mb_substr($shorttext, 0, $j));
if (mb_strlen($best_common) < $suffixLength + $prefixLength) { if (mbstrlen($best_common) < $suffixLength + $prefixLength) {
$best_common = mb_substr($shorttext, $j - $suffixLength, $suffixLength) . mb_substr($shorttext, $j, $prefixLength); $best_common = mb_substr($shorttext, $j - $suffixLength, $suffixLength) . mb_substr($shorttext, $j, $prefixLength);
$best_longtext_a = mb_substr($longtext, 0, $i - $suffixLength); $best_longtext_a = mb_substr($longtext, 0, $i - $suffixLength);
$best_longtext_b = mb_substr($longtext, $i + $prefixLength); $best_longtext_b = mb_substr($longtext, $i + $prefixLength);
Context not available.
$best_shorttext_b = mb_substr($shorttext, $j + $prefixLength); $best_shorttext_b = mb_substr($shorttext, $j + $prefixLength);
} }
} }
if (mb_strlen($best_common) >= mb_strlen($longtext) / 2) { if (mbstrlen($best_common) >= mbstrlen($longtext) / 2) {
return array ( return array (
$best_longtext_a, $best_longtext_a,
$best_longtext_b, $best_longtext_b,
Context not available.
$length_changes2 = 0; $length_changes2 = 0;
$lastequality = $diffs[$pointer][1]; $lastequality = $diffs[$pointer][1];
} else { // an insertion or deletion } else { // an insertion or deletion
$length_changes2 += mb_strlen($diffs[$pointer][1]); $length_changes2 += mbstrlen($diffs[$pointer][1]);
if ($lastequality !== null && (mb_strlen($lastequality) <= $length_changes1) && (mb_strlen($lastequality) <= $length_changes2)) { if ($lastequality !== null && (mbstrlen($lastequality) <= $length_changes1) && (mbstrlen($lastequality) <= $length_changes2)) {
// Duplicate record // Duplicate record
$zzz_diffs = array_splice($diffs, $equalities[$equalitiesLength -1], 0, array(array ( $zzz_diffs = array_splice($diffs, $equalities[$equalitiesLength -1], 0, array(array (
DIFF_DELETE, DIFF_DELETE,
Context not available.
// First, shift the edit as far left as possible. // First, shift the edit as far left as possible.
$commonOffset = $this->diff_commonSuffix($equality1, $edit); $commonOffset = $this->diff_commonSuffix($equality1, $edit);
if ($commonOffset !== '') { if ($commonOffset !== '') {
$commonString = mb_substr($edit, mb_strlen($edit) - $commonOffset); $commonString = mb_substr($edit, mbstrlen($edit) - $commonOffset);
$equality1 = mb_substr($equality1, 0, mb_strlen($equality1) - $commonOffset); $equality1 = mb_substr($equality1, 0, mbstrlen($equality1) - $commonOffset);
$edit = $commonString . mb_substr($edit, 0, mb_strlen($edit) - $commonOffset); $edit = $commonString . mb_substr($edit, 0, mbstrlen($edit) - $commonOffset);
$equality2 = $commonString . $equality2; $equality2 = $commonString . $equality2;
} }
Context not available.
// rather than force total conformity. // rather than force total conformity.
$score = 0; $score = 0;
// One point for non-alphanumeric. // One point for non-alphanumeric.
if (preg_match($punctuation, $one[mb_strlen($one) - 1]) || preg_match($punctuation, $two[0])) { if (@preg_match($punctuation, $one[mbstrlen($one) - 1]) || @preg_match($punctuation, $two[0])) {
$score++; $score++;
// Two points for whitespace. // Two points for whitespace.
if (preg_match($whitespace, $one[mb_strlen($one) - 1] ) || preg_match($whitespace, $two[0])) { if (@preg_match($whitespace, $one[mbstrlen($one) - 1] ) || @preg_match($whitespace, $two[0])) {
$score++; $score++;
// Three points for line breaks. // Three points for line breaks.
if (preg_match($linebreak, $one[mb_strlen($one) - 1]) || preg_match($linebreak, $two[0])) { if (@preg_match($linebreak, $one[mbstrlen($one) - 1]) || @preg_match($linebreak, $two[0])) {
$score++; $score++;
// Four points for blank lines. // Four points for blank lines.
if (preg_match($blanklineEnd, $one) || preg_match($blanklineStart, $two)) { if (@preg_match($blanklineEnd, $one) || @preg_match($blanklineStart, $two)) {
$score++; $score++;
} }
} }
Context not available.
$post_del = false; $post_del = false;
while ($pointer < count($diffs)) { while ($pointer < count($diffs)) {
if ($diffs[$pointer][0] == DIFF_EQUAL) { // equality found if ($diffs[$pointer][0] == DIFF_EQUAL) { // equality found
if (mb_strlen($diffs[$pointer][1]) < $this->Diff_EditCost && ($post_ins || $post_del)) { if (mbstrlen($diffs[$pointer][1]) < $this->Diff_EditCost && ($post_ins || $post_del)) {
// Candidate found. // Candidate found.
$equalities[$equalitiesLength++] = $pointer; $equalities[$equalitiesLength++] = $pointer;
$pre_ins = $post_ins; $pre_ins = $post_ins;
Context not available.
* <ins>A</del>X<ins>C</ins><del>D</del> * <ins>A</del>X<ins>C</ins><del>D</del>
* <ins>A</ins><del>B</del>X<del>C</del> * <ins>A</ins><del>B</del>X<del>C</del>
*/ */
if ($lastequality && (($pre_ins && $pre_del && $post_ins && $post_del) || ((mb_strlen($lastequality) < $this->Diff_EditCost / 2) && ($pre_ins + $pre_del + $post_ins + $post_del) == 3))) { if ($lastequality && (($pre_ins && $pre_del && $post_ins && $post_del) || ((mbstrlen($lastequality) < $this->Diff_EditCost / 2) && ($pre_ins + $pre_del + $post_ins + $post_del) == 3))) {
// Duplicate record // Duplicate record
$zzz_diffs = array_splice($diffs, $equalities[$equalitiesLength -1], 0, array(array ( $zzz_diffs = array_splice($diffs, $equalities[$equalitiesLength -1], 0, array(array (
DIFF_DELETE, DIFF_DELETE,
Context not available.
// Factor out any common suffixies. // Factor out any common suffixies.
$commonlength = $this->diff_commonSuffix($text_insert, $text_delete); $commonlength = $this->diff_commonSuffix($text_insert, $text_delete);
if ($commonlength !== 0) { if ($commonlength !== 0) {
$diffs[$pointer][1] = mb_substr($text_insert, mb_strlen($text_insert) - $commonlength) . $diffs[$pointer][1]; $diffs[$pointer][1] = mb_substr($text_insert, mbstrlen($text_insert) - $commonlength) . $diffs[$pointer][1];
$text_insert = mb_substr($text_insert, 0, mb_strlen($text_insert) - $commonlength); $text_insert = mb_substr($text_insert, 0, mbstrlen($text_insert) - $commonlength);
$text_delete = mb_substr($text_delete, 0, mb_strlen($text_delete) - $commonlength); $text_delete = mb_substr($text_delete, 0, mbstrlen($text_delete) - $commonlength);
} }
} }
// Delete the offending records and add the merged ones. // Delete the offending records and add the merged ones.
Context not available.
while ($pointer < count($diffs) - 1) { while ($pointer < count($diffs) - 1) {
if ($diffs[$pointer-1][0] == DIFF_EQUAL && $diffs[$pointer+1][0] == DIFF_EQUAL) { if ($diffs[$pointer-1][0] == DIFF_EQUAL && $diffs[$pointer+1][0] == DIFF_EQUAL) {
// This is a single edit surrounded by equalities. // This is a single edit surrounded by equalities.
if ( mb_substr($diffs[$pointer][1], mb_strlen($diffs[$pointer][1]) - mb_strlen($diffs[$pointer -1][1])) == $diffs[$pointer -1][1]) { if ( mb_substr($diffs[$pointer][1], mbstrlen($diffs[$pointer][1]) - mbstrlen($diffs[$pointer -1][1])) == $diffs[$pointer -1][1]) {
// Shift the edit over the previous equality. // Shift the edit over the previous equality.
$diffs[$pointer][1] = $diffs[$pointer -1][1] . mb_substr($diffs[$pointer][1], 0, mb_strlen($diffs[$pointer][1]) - mb_strlen($diffs[$pointer -1][1])); $diffs[$pointer][1] = $diffs[$pointer -1][1] . mb_substr($diffs[$pointer][1], 0, mbstrlen($diffs[$pointer][1]) - mbstrlen($diffs[$pointer -1][1]));
$diffs[$pointer +1][1] = $diffs[$pointer -1][1] . $diffs[$pointer +1][1]; $diffs[$pointer +1][1] = $diffs[$pointer -1][1] . $diffs[$pointer +1][1];
array_splice($diffs, $pointer -1, 1); array_splice($diffs, $pointer -1, 1);
$changes = true; $changes = true;
} elseif (mb_substr($diffs[$pointer][1], 0, mb_strlen($diffs[$pointer +1][1])) == $diffs[$pointer +1][1]) { } elseif (mb_substr($diffs[$pointer][1], 0, mbstrlen($diffs[$pointer +1][1])) == $diffs[$pointer +1][1]) {
// Shift the edit over the next equality. // Shift the edit over the next equality.
$diffs[$pointer -1][1] .= $diffs[$pointer +1][1]; $diffs[$pointer -1][1] .= $diffs[$pointer +1][1];
$diffs[$pointer][1] = mb_substr($diffs[$pointer][1], mb_strlen($diffs[$pointer +1][1])) . $diffs[$pointer +1][1]; $diffs[$pointer][1] = mb_substr($diffs[$pointer][1], mbstrlen($diffs[$pointer +1][1])) . $diffs[$pointer +1][1];
array_splice($diffs, $pointer +1, 1); array_splice($diffs, $pointer +1, 1);
$changes = true; $changes = true;
} }
Context not available.
$last_chars2 = 0; $last_chars2 = 0;
for ($x = 0; $x < count($diffs); $x++) { for ($x = 0; $x < count($diffs); $x++) {
if ($diffs[$x][0] !== DIFF_INSERT) { // Equality or deletion. if ($diffs[$x][0] !== DIFF_INSERT) { // Equality or deletion.
$chars1 += mb_strlen($diffs[$x][1]); $chars1 += mbstrlen($diffs[$x][1]);
} }
if ($diffs[$x][0] !== DIFF_DELETE) { // Equality or insertion. if ($diffs[$x][0] !== DIFF_DELETE) { // Equality or insertion.
$chars2 += mb_strlen($diffs[$x][1]); $chars2 += mbstrlen($diffs[$x][1]);
} }
if ($chars1 > $loc) { // Overshot the location. if ($chars1 > $loc) { // Overshot the location.
break; break;
Context not available.
break; break;
} }
if ($op !== DIFF_DELETE) { if ($op !== DIFF_DELETE) {
$i += mb_strlen($data); $i += mbstrlen($data);
} }
} }
return implode('',$html); return implode('',$html);
Context not available.
$data = $diffs[$x][1]; $data = $diffs[$x][1];
switch ($op) { switch ($op) {
case DIFF_INSERT : case DIFF_INSERT :
$insertions += mb_strlen($data); $insertions += mbstrlen($data);
break; break;
case DIFF_DELETE : case DIFF_DELETE :
$deletions += mb_strlen($data); $deletions += mbstrlen($data);
break; break;
case DIFF_EQUAL : case DIFF_EQUAL :
// A deletion and an insertion is one substitution. // A deletion and an insertion is one substitution.
Context not available.
$text[$x] = '+' .encodeURI($diffs[$x][1]); $text[$x] = '+' .encodeURI($diffs[$x][1]);
break; break;
case DIFF_DELETE : case DIFF_DELETE :
$text[$x] = '-' .mb_strlen($diffs[$x][1]); $text[$x] = '-' .mbstrlen($diffs[$x][1]);
break; break;
case DIFF_EQUAL : case DIFF_EQUAL :
$text[$x] = '=' .mb_strlen($diffs[$x][1]); $text[$x] = '=' .mbstrlen($diffs[$x][1]);
break; break;
} }
} }
Context not available.
} }
} }
} }
if ($pointer != mb_strlen($text1)) { if ($pointer != mbstrlen($text1)) {
// throw new Exception('Delta length (' . $pointer . ') does not equal source text length (' . mb_strlen($text1) . ').'); // throw new Exception('Delta length (' . $pointer . ') does not equal source text length (' . mbstrlen($text1) . ').');
echo_Exception('Delta length (' . $pointer . ') does not equal source text length (' . mb_strlen($text1) . ').'); echo_Exception('Delta length (' . $pointer . ') does not equal source text length (' . mbstrlen($text1) . ').');
} }
return $diffs; return $diffs;
} }
Context not available.
* @return {number} Best match index or -1. * @return {number} Best match index or -1.
*/ */
function match_main($text, $pattern, $loc) { function match_main($text, $pattern, $loc) {
$loc = max(0, min($loc, mb_strlen($text))); $loc = max(0, min($loc, mbstrlen($text)));
if ($text == $pattern) { if ($text == $pattern) {
// Shortcut (potentially not guaranteed by the algorithm) // Shortcut (potentially not guaranteed by the algorithm)
return 0; return 0;
} }
elseif (!mb_strlen($text)) { elseif (!mbstrlen($text)) {
// Nothing to match. // Nothing to match.
return -1; return -1;
} }
elseif (mb_substr($text, $loc, mb_strlen($pattern)) == $pattern) { elseif (mb_substr($text, $loc, mbstrlen($pattern)) == $pattern) {
// Perfect match at the perfect spot! (Includes case of null pattern) // Perfect match at the perfect spot! (Includes case of null pattern)
return $loc; return $loc;
} else { } else {
Context not available.
* @private * @private
*/ */
function match_bitap($text, $pattern, $loc) { function match_bitap($text, $pattern, $loc) {
if (mb_strlen($pattern) > Match_MaxBits) { if (mbstrlen($pattern) > Match_MaxBits) {
echo_Exception('Pattern too long for this browser.'); echo_Exception('Pattern too long for this browser.');
} }
Context not available.
} }
// What about in the other direction? (speedup) // What about in the other direction? (speedup)
$best_loc = mb_strrpos( $text, $pattern, min($loc + mb_strlen($pattern), mb_strlen($text)) ); $best_loc = mb_strrpos( $text, $pattern, min($loc + mbstrlen($pattern), mbstrlen($text)) );
if ($best_loc !== false) { if ($best_loc !== false) {
$score_threshold = min($this->match_bitapScore(0, $best_loc, $pattern, $loc), $score_threshold); $score_threshold = min($this->match_bitapScore(0, $best_loc, $pattern, $loc), $score_threshold);
} }
// Initialise the bit arrays. // Initialise the bit arrays.
$matchmask = 1 << (mb_strlen($pattern) - 1); $matchmask = 1 << (mbstrlen($pattern) - 1);
$best_loc = -1; $best_loc = -1;
$bin_min = null; $bin_min = null;
$bin_mid = null; $bin_mid = null;
$bin_max = mb_strlen($pattern) + mb_strlen($text); $bin_max = mbstrlen($pattern) + mbstrlen($text);
$last_rd = null; $last_rd = null;
for ($d = 0; $d < mb_strlen($pattern); $d++) { for ($d = 0; $d < mbstrlen($pattern); $d++) {
// Scan for the best match; each iteration allows for one more error. // Scan for the best match; each iteration allows for one more error.
// Run a binary search to determine how far from 'loc' we can stray at this // Run a binary search to determine how far from 'loc' we can stray at this
// error level. // error level.
Context not available.
// Use the result from this iteration as the maximum for the next. // Use the result from this iteration as the maximum for the next.
$bin_max = $bin_mid; $bin_max = $bin_mid;
$start = max(1, $loc - $bin_mid +1); $start = max(1, $loc - $bin_mid +1);
$finish = min($loc + $bin_mid, mb_strlen($text)) + mb_strlen($pattern); $finish = min($loc + $bin_mid, mbstrlen($text)) + mbstrlen($pattern);
$rd = Array ( $rd = Array (
$finish +2 $finish +2
Context not available.
* @private * @private
*/ */
function match_bitapScore($e, $x, $pattern, $loc) { function match_bitapScore($e, $x, $pattern, $loc) {
$accuracy = $e / mb_strlen($pattern); $accuracy = $e / mbstrlen($pattern);
$proximity = abs($loc - $x); $proximity = abs($loc - $x);
if (!$this->Match_Distance) { if (!$this->Match_Distance) {
// Dodge divide by zero error. // Dodge divide by zero error.
Context not available.
*/ */
function match_alphabet($pattern) { function match_alphabet($pattern) {
$s = array (); $s = array ();
for ($i = 0; $i < mb_strlen($pattern); $i++) { for ($i = 0; $i < mbstrlen($pattern); $i++) {
$s[ $pattern[$i] ] = 0; $s[ $pattern[$i] ] = 0;
} }
for ($i = 0; $i < mb_strlen($pattern); $i++) { for ($i = 0; $i < mbstrlen($pattern); $i++) {
$s[ $pattern[$i] ] |= 1 << (mb_strlen($pattern) - $i - 1); $s[ $pattern[$i] ] |= 1 << (mbstrlen($pattern) - $i - 1);
} }
return $s; return $s;
} }
Context not available.
$padding = 0; $padding = 0;
$i = 0; $i = 0;
while ( while (
( mb_strlen($pattern) === 0 // Javascript's indexOf/lastIndexOd return 0/strlen respectively if pattern = '' ( mbstrlen($pattern) === 0 // Javascript's indexOf/lastIndexOd return 0/strlen respectively if pattern = ''
|| mb_strpos($text, $pattern) !== mb_strrpos($text, $pattern) || mb_strpos($text, $pattern) !== mb_strrpos($text, $pattern)
) )
&& $pattern !== $previousPattern // avoid infinte loop && $pattern !== $previousPattern // avoid infinte loop
&& mb_strlen($pattern) < Match_MaxBits - $this->Patch_Margin - $this->Patch_Margin ) { && mbstrlen($pattern) < Match_MaxBits - $this->Patch_Margin - $this->Patch_Margin ) {
$padding += $this->Patch_Margin; $padding += $this->Patch_Margin;
$previousPattern = $pattern; $previousPattern = $pattern;
$pattern = mb_substr($text, max($patch->start2 - $padding,0), ($patch->start2 + $patch->length1 + $padding) - max($patch->start2 - $padding,0) ); $pattern = mb_substr($text, max($patch->start2 - $padding,0), ($patch->start2 + $patch->length1 + $padding) - max($patch->start2 - $padding,0) );
Context not available.
} }
// Roll back the start points. // Roll back the start points.
$patch->start1 -= mb_strlen($prefix); $patch->start1 -= mbstrlen($prefix);
$patch->start2 -= mb_strlen($prefix); $patch->start2 -= mbstrlen($prefix);
// Extend the lengths. // Extend the lengths.
$patch->length1 += mb_strlen($prefix) + mb_strlen($suffix); $patch->length1 += mbstrlen($prefix) + mbstrlen($suffix);
$patch->length2 += mb_strlen($prefix) + mb_strlen($suffix); $patch->length2 += mbstrlen($prefix) + mbstrlen($suffix);
} }
/** /**
Context not available.
switch ($diff_type) { switch ($diff_type) {
case DIFF_INSERT : case DIFF_INSERT :
$patch->diffs[$patchDiffLength++] = $diffs[$x]; $patch->diffs[$patchDiffLength++] = $diffs[$x];
$patch->length2 += mb_strlen($diff_text); $patch->length2 += mbstrlen($diff_text);
$postpatch_text = mb_substr($postpatch_text, 0, $char_count2) . $diff_text . mb_substr($postpatch_text,$char_count2); $postpatch_text = mb_substr($postpatch_text, 0, $char_count2) . $diff_text . mb_substr($postpatch_text,$char_count2);
break; break;
case DIFF_DELETE : case DIFF_DELETE :
$patch->length1 += mb_strlen($diff_text); $patch->length1 += mbstrlen($diff_text);
$patch->diffs[$patchDiffLength++] = $diffs[$x]; $patch->diffs[$patchDiffLength++] = $diffs[$x];
$postpatch_text = mb_substr($postpatch_text, 0, $char_count2) . mb_substr($postpatch_text, $char_count2 + mb_strlen($diff_text) ); $postpatch_text = mb_substr($postpatch_text, 0, $char_count2) . mb_substr($postpatch_text, $char_count2 + mbstrlen($diff_text) );
break; break;
case DIFF_EQUAL : case DIFF_EQUAL :
if ( mb_strlen($diff_text) <= 2 * $this->Patch_Margin && $patchDiffLength && count($diffs) != $x + 1) { if ( mbstrlen($diff_text) <= 2 * $this->Patch_Margin && $patchDiffLength && count($diffs) != $x + 1) {
// Small equality inside a patch. // Small equality inside a patch.
$patch->diffs[$patchDiffLength++] = $diffs[$x]; $patch->diffs[$patchDiffLength++] = $diffs[$x];
$patch->length1 += mb_strlen($diff_text); $patch->length1 += mbstrlen($diff_text);
$patch->length2 += mb_strlen($diff_text); $patch->length2 += mbstrlen($diff_text);
} elseif ( mb_strlen($diff_text) >= 2 * $this->Patch_Margin ) { } elseif ( mbstrlen($diff_text) >= 2 * $this->Patch_Margin ) {
// Time for a new patch. // Time for a new patch.
if ($patchDiffLength) { if ($patchDiffLength) {
$this->patch_addContext($patch, $prepatch_text); $this->patch_addContext($patch, $prepatch_text);
Context not available.
// Update the current character count. // Update the current character count.
if ($diff_type !== DIFF_INSERT) { if ($diff_type !== DIFF_INSERT) {
$char_count1 += mb_strlen($diff_text); $char_count1 += mbstrlen($diff_text);
} }
if ($diff_type !== DIFF_DELETE) { if ($diff_type !== DIFF_DELETE) {
$char_count2 += mb_strlen($diff_text); $char_count2 += mbstrlen($diff_text);
} }
} }
// Pick up the leftover patch if not empty. // Pick up the leftover patch if not empty.
Context not available.
$text1 = $this->diff_text1($patches[$x]->diffs); $text1 = $this->diff_text1($patches[$x]->diffs);
$start_loc = null; $start_loc = null;
$end_loc = -1; $end_loc = -1;
if (mb_strlen($text1) > Match_MaxBits) { if (mbstrlen($text1) > Match_MaxBits) {
// patch_splitMax will only provide an oversized pattern in the case of // patch_splitMax will only provide an oversized pattern in the case of
// a monster delete. // a monster delete.
$start_loc = $this->match_main($text, mb_substr($text1, 0, Match_MaxBits ), $expected_loc); $start_loc = $this->match_main($text, mb_substr($text1, 0, Match_MaxBits ), $expected_loc);
if ($start_loc != -1) { if ($start_loc != -1) {
$end_loc = $this->match_main($text, mb_substr($text1,mb_strlen($text1) - Match_MaxBits), $expected_loc + mb_strlen($text1) - Match_MaxBits); $end_loc = $this->match_main($text, mb_substr($text1,mbstrlen($text1) - Match_MaxBits), $expected_loc + mbstrlen($text1) - Match_MaxBits);
if ($end_loc == -1 || $start_loc >= $end_loc) { if ($end_loc == -1 || $start_loc >= $end_loc) {
// Can't find valid trailing context. Drop this patch. // Can't find valid trailing context. Drop this patch.
$start_loc = -1; $start_loc = -1;
Context not available.
$delta = $start_loc - $expected_loc; $delta = $start_loc - $expected_loc;
$text2 = null; $text2 = null;
if ($end_loc == -1) { if ($end_loc == -1) {
$text2 = mb_substr($text, $start_loc, mb_strlen($text1) ); $text2 = mb_substr($text, $start_loc, mbstrlen($text1) );
} else { } else {
$text2 = mb_substr($text, $start_loc, $end_loc + Match_MaxBits - $start_loc); $text2 = mb_substr($text, $start_loc, $end_loc + Match_MaxBits - $start_loc);
} }
if ($text1 == $text2) { if ($text1 == $text2) {
// Perfect match, just shove the replacement text in. // Perfect match, just shove the replacement text in.
$text = mb_substr($text, 0, $start_loc) . $this->diff_text2($patches[$x]->diffs) . mb_substr($text,$start_loc + mb_strlen($text1) ); $text = mb_substr($text, 0, $start_loc) . $this->diff_text2($patches[$x]->diffs) . mb_substr($text,$start_loc + mbstrlen($text1) );
} else { } else {
// Imperfect match. Run a diff to get a framework of equivalent // Imperfect match. Run a diff to get a framework of equivalent
// indices. // indices.
$diffs = $this->diff_main($text1, $text2, false); $diffs = $this->diff_main($text1, $text2, false);
if ( mb_strlen($text1) > Match_MaxBits && $this->diff_levenshtein($diffs) / mb_strlen($text1) > $this->Patch_DeleteThreshold) { if ( mbstrlen($text1) > Match_MaxBits && $this->diff_levenshtein($diffs) / mbstrlen($text1) > $this->Patch_DeleteThreshold) {
// The end points match, but the content is unacceptably bad. // The end points match, but the content is unacceptably bad.
$results[$x] = false; $results[$x] = false;
} else { } else {
Context not available.
if ($mod[0] === DIFF_INSERT) { // Insertion if ($mod[0] === DIFF_INSERT) { // Insertion
$text = mb_substr($text, 0, $start_loc + $index2) . $mod[1] . mb_substr($text, $start_loc + $index2); $text = mb_substr($text, 0, $start_loc + $index2) . $mod[1] . mb_substr($text, $start_loc + $index2);
} elseif ($mod[0] === DIFF_DELETE) { // Deletion } elseif ($mod[0] === DIFF_DELETE) { // Deletion
$text = mb_substr($text, 0, $start_loc + $index2) . mb_substr($text,$start_loc + $this->diff_xIndex($diffs, $index1 + mb_strlen($mod[1]) )); $text = mb_substr($text, 0, $start_loc + $index2) . mb_substr($text,$start_loc + $this->diff_xIndex($diffs, $index1 + mbstrlen($mod[1]) ));
} }
if ($mod[0] !== DIFF_DELETE) { if ($mod[0] !== DIFF_DELETE) {
$index1 += mb_strlen($mod[1]); $index1 += mbstrlen($mod[1]);
} }
} }
} }
Context not available.
} }
} }
// Strip the padding off. // Strip the padding off.
$text = mb_substr($text, mb_strlen($nullPadding), mb_strlen($text) - 2*mb_strlen($nullPadding) ); $text = mb_substr($text, mbstrlen($nullPadding), mbstrlen($text) - 2*mbstrlen($nullPadding) );
return array($text, $results); return array($text, $results);
} }
Context not available.
$patch->start2 -= $paddingLength; // Should be 0. $patch->start2 -= $paddingLength; // Should be 0.
$patch->length1 += $paddingLength; $patch->length1 += $paddingLength;
$patch->length2 += $paddingLength; $patch->length2 += $paddingLength;
} elseif ($paddingLength > mb_strlen($diffs[0][1]) ) { } elseif ($paddingLength > mbstrlen($diffs[0][1]) ) {
// Grow first equality. // Grow first equality.
$extraLength = $paddingLength - mb_strlen($diffs[0][1]); $extraLength = $paddingLength - mbstrlen($diffs[0][1]);
$diffs[0][1] = mb_substr( $nullPadding , mb_strlen($diffs[0][1]) ) . $diffs[0][1]; $diffs[0][1] = mb_substr( $nullPadding , mbstrlen($diffs[0][1]) ) . $diffs[0][1];
$patch->start1 -= $extraLength; $patch->start1 -= $extraLength;
$patch->start2 -= $extraLength; $patch->start2 -= $extraLength;
$patch->length1 += $extraLength; $patch->length1 += $extraLength;
Context not available.
array_push($diffs, array(DIFF_EQUAL, $nullPadding) ); array_push($diffs, array(DIFF_EQUAL, $nullPadding) );
$patch->length1 += $paddingLength; $patch->length1 += $paddingLength;
$patch->length2 += $paddingLength; $patch->length2 += $paddingLength;
} elseif ($paddingLength > mb_strlen( $diffs[count($diffs)-1][1] ) ) { } elseif ($paddingLength > mbstrlen( $diffs[count($diffs)-1][1] ) ) {
// Grow last equality. // Grow last equality.
$extraLength = $paddingLength - mb_strlen( $diffs[count($diffs)-1][1] ); $extraLength = $paddingLength - mbstrlen( $diffs[count($diffs)-1][1] );
$diffs[ count($diffs)-1][1] .= mb_substr($nullPadding,0,$extraLength); $diffs[ count($diffs)-1][1] .= mb_substr($nullPadding,0,$extraLength);
$patch->length1 += $extraLength; $patch->length1 += $extraLength;
$patch->length2 += $extraLength; $patch->length2 += $extraLength;
Context not available.
// Create one of several smaller patches. // Create one of several smaller patches.
$patch = new patch_obj(); $patch = new patch_obj();
$empty = true; $empty = true;
$patch->start1 = $start1 - mb_strlen($precontext); $patch->start1 = $start1 - mbstrlen($precontext);
$patch->start2 = $start2 - mb_strlen($precontext); $patch->start2 = $start2 - mbstrlen($precontext);
if ($precontext !== '') { if ($precontext !== '') {
$patch->length1 = $patch->length2 = mb_strlen($precontext); $patch->length1 = $patch->length2 = mbstrlen($precontext);
array_push($patch->diffs, array(DIFF_EQUAL, $precontext) ); array_push($patch->diffs, array(DIFF_EQUAL, $precontext) );
} }
while ( count($bigpatch->diffs) !== 0 && $patch->length1 < $patch_size - $this->Patch_Margin) { while ( count($bigpatch->diffs) !== 0 && $patch->length1 < $patch_size - $this->Patch_Margin) {
Context not available.
$diff_text = $bigpatch->diffs[0][1]; $diff_text = $bigpatch->diffs[0][1];
if ($diff_type === DIFF_INSERT) { if ($diff_type === DIFF_INSERT) {
// Insertions are harmless. // Insertions are harmless.
$patch->length2 += mb_strlen($diff_text); $patch->length2 += mbstrlen($diff_text);
$start2 += mb_strlen($diff_text); $start2 += mbstrlen($diff_text);
array_push($patch->diffs, array_shift($bigpatch->diffs) ); array_push($patch->diffs, array_shift($bigpatch->diffs) );
$empty = false; $empty = false;
} else } else
if ($diff_type === DIFF_DELETE && count($patch->diffs) == 1 && $patch->diffs[0][0] == DIFF_EQUAL && (mb_strlen($diff_text) > 2 * $patch_size) ) { if ($diff_type === DIFF_DELETE && count($patch->diffs) == 1 && $patch->diffs[0][0] == DIFF_EQUAL && (mbstrlen($diff_text) > 2 * $patch_size) ) {
// This is a large deletion. Let it pass in one chunk. // This is a large deletion. Let it pass in one chunk.
$patch->length1 += mb_strlen($diff_text); $patch->length1 += mbstrlen($diff_text);
$start1 += mb_strlen($diff_text); $start1 += mbstrlen($diff_text);
$empty = false; $empty = false;
array_push( $patch->diffs, array($diff_type, $diff_text) ); array_push( $patch->diffs, array($diff_type, $diff_text) );
array_shift($bigpatch->diffs); array_shift($bigpatch->diffs);
} else { } else {
// Deletion or equality. Only take as much as we can stomach. // Deletion or equality. Only take as much as we can stomach.
$diff_text = mb_substr($diff_text, 0, $patch_size - $patch->length1 - $this->Patch_Margin); $diff_text = mb_substr($diff_text, 0, $patch_size - $patch->length1 - $this->Patch_Margin);
$patch->length1 += mb_strlen($diff_text); $patch->length1 += mbstrlen($diff_text);
$start1 += mb_strlen($diff_text); $start1 += mbstrlen($diff_text);
if ($diff_type === DIFF_EQUAL) { if ($diff_type === DIFF_EQUAL) {
$patch->length2 += mb_strlen($diff_text); $patch->length2 += mbstrlen($diff_text);
$start2 += mb_strlen($diff_text); $start2 += mbstrlen($diff_text);
} else { } else {
$empty = false; $empty = false;
} }
Context not available.
if ($diff_text == $bigpatch->diffs[0][1]) { if ($diff_text == $bigpatch->diffs[0][1]) {
array_shift($bigpatch->diffs); array_shift($bigpatch->diffs);
} else { } else {
$bigpatch->diffs[0][1] = mb_substr( $bigpatch->diffs[0][1],mb_strlen($diff_text) ); $bigpatch->diffs[0][1] = mb_substr( $bigpatch->diffs[0][1],mbstrlen($diff_text) );
} }
} }
} }
// Compute the head context for the next patch. // Compute the head context for the next patch.
$precontext = $this->diff_text2($patch->diffs); $precontext = $this->diff_text2($patch->diffs);
$precontext = mb_substr($precontext, mb_strlen($precontext)-$this->Patch_Margin); $precontext = mb_substr($precontext, mbstrlen($precontext)-$this->Patch_Margin);
// Append the end context for this patch. // Append the end context for this patch.
$postcontext = mb_substr( $this->diff_text1($bigpatch->diffs), 0, $this->Patch_Margin ); $postcontext = mb_substr( $this->diff_text1($bigpatch->diffs), 0, $this->Patch_Margin );
if ($postcontext !== '') { if ($postcontext !== '') {
$patch->length1 += mb_strlen($postcontext); $patch->length1 += mbstrlen($postcontext);
$patch->length2 += mb_strlen($postcontext); $patch->length2 += mbstrlen($postcontext);
if ( count($patch->diffs) !== 0 && $patch->diffs[ count($patch->diffs) - 1][0] === DIFF_EQUAL) { if ( count($patch->diffs) !== 0 && $patch->diffs[ count($patch->diffs) - 1][0] === DIFF_EQUAL) {
$patch->diffs[ count($patch->diffs) - 1][1] .= $postcontext; $patch->diffs[ count($patch->diffs) - 1][1] .= $postcontext;
} else { } else {
Context not available.
if ($textline === '') { if ($textline === '') {
return $patches; return $patches;
} }
$text = explode("\n",$textline); $text = @explode("\n",$textline);
foreach($text as $i=>$t){ if($t===''){ unset($text[$i]); } } foreach($text as $i=>$t){ if($t===''){ unset($text[$i]); } }
$textPointer = 0; $textPointer = 0;
while ($textPointer < count($text) ) { while ($textPointer < count($text) ) {
$m = null; $m = null;
preg_match('/^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/',$text[$textPointer],$m); @preg_match('/^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/',$text[$textPointer],$m);
if (!$m) { if (!$m) {
echo_Exception('Invalid patch string: ' . $text[$textPointer]); echo_Exception('Invalid patch string: ' . $text[$textPointer]);
} }
Context not available.
} }
function mb_ord($v) { function mb_ord($v) {
$k = mb_convert_encoding($v, 'UCS-2LE', 'UTF-8'); $k = mb_convert_encoding($v, 'UCS-2LE', 'UTF-8');
$k1 = ord(substr($k, 0, 1)); $k1 = ord(@substr($k, 0, 1));
$k2 = ord(substr($k, 1, 1)); $k2 = ord(@substr($k, 1, 1));
return $k2 * 256 + $k1; return $k2 * 256 + $k1;
} }
function mb_chr($num){ function mb_chr($num){
Context not available.
Content licensed under Creative Commons Attribution-ShareAlike 4.0 (CC-BY-SA) unless otherwise noted; code licensed under Apache 2.0 or other open source licenses. · CC BY-SA 4.0 · Apache 2.0