Index: externals/diff_match_patch/diff_match_patch.php =================================================================== --- /dev/null +++ externals/diff_match_patch/diff_match_patch.php @@ -0,0 +1,2117 @@ +>} Array of diff tuples. + */ + function diff_main($text1, $text2, $checklines = true) { + // Check for equality (speedup) + if ($text1 === $text2) { + return array ( array ( DIFF_EQUAL, $text1) ); + } + + // Trim off common prefix (speedup) + $commonlength = $this->diff_commonPrefix($text1, $text2); + $commonprefix = mb_substr($text1, 0, $commonlength); + $text1 = mb_substr($text1, $commonlength); + $text2 = mb_substr($text2, $commonlength); + + // Trim off common suffix (speedup) + $commonlength = $this->diff_commonSuffix($text1, $text2); + $commonsuffix = mb_substr($text1, mb_strlen($text1) - $commonlength); + $text1 = mb_substr($text1, 0, mb_strlen($text1) - $commonlength); + $text2 = mb_substr($text2, 0, mb_strlen($text2) - $commonlength); + + // Compute the diff on the middle block + $diffs = $this->diff_compute($text1, $text2, $checklines); + + // Restore the prefix and suffix + if ($commonprefix !== '') { + array_unshift($diffs, array ( DIFF_EQUAL, $commonprefix )); + } + if ($commonsuffix !== '') { + array_push($diffs, array ( DIFF_EQUAL, $commonsuffix )); + } + $this->diff_cleanupMerge($diffs); + return $diffs; + } + + /** + * Find the differences between two texts. Assumes that the texts do not + * have any common prefix or suffix. + * @param {string} text1 Old string to be diffed. + * @param {string} text2 New string to be diffed. + * @param {boolean} checklines Speedup flag. If false, then don't run a + * line-level diff first to identify the changed areas. + * If true, then run a faster, slightly less optimal diff + * @return {Array.>} Array of diff tuples. + * @private + */ + function diff_compute($text1, $text2, $checklines) { + + if ($text1 === '') { + // Just add some text (speedup) + return array ( array ( DIFF_INSERT, $text2 ) ); + } + + if ($text2 === '') { + // Just delete some text (speedup) + return array ( array ( DIFF_DELETE, $text1 ) ); + } + + $longtext = mb_strlen($text1) > mb_strlen($text2) ? $text1 : $text2; + $shorttext = mb_strlen($text1) > mb_strlen($text2) ? $text2 : $text1; + $i = mb_strpos($longtext, $shorttext); + if ($i !== false) { + // Shorter text is inside the longer text (speedup) + $diffs = array ( + array ( DIFF_INSERT, mb_substr($longtext, 0, $i) ), + array ( DIFF_EQUAL, $shorttext ), + array ( DIFF_INSERT, mb_substr($longtext, $i +mb_strlen($shorttext)) ) + ); + + // Swap insertions for deletions if diff is reversed. + if (mb_strlen($text1) > mb_strlen($text2)) { + $diffs[0][0] = $diffs[2][0] = DIFF_DELETE; + } + return $diffs; + } + $longtext = $shorttext = null; // Garbage collect + + // Check to see if the problem can be split in two. + $hm = $this->diff_halfMatch($text1, $text2); + if ($hm) { + // A half-match was found, sort out the return data. + $text1_a = $hm[0]; + $text1_b = $hm[1]; + $text2_a = $hm[2]; + $text2_b = $hm[3]; + $mid_common = $hm[4]; + // Send both pairs off for separate processing. + $diffs_a = $this->diff_main($text1_a, $text2_a, $checklines); + $diffs_b = $this->diff_main($text1_b, $text2_b, $checklines); + // Merge the results. + return array_merge($diffs_a, array ( + array ( + DIFF_EQUAL, + $mid_common + ) + ), $diffs_b); + } + + // Perform a real diff. + if ($checklines && (mb_strlen($text1) < 100 || mb_strlen($text2) < 100)) { + // Too trivial for the overhead. + $checklines = false; + } + $linearray = null; + if ($checklines) { + // Scan the text on a line-by-line basis first. + $a = $this->diff_linesToChars($text1, $text2); + $text1 = $a[0]; + $text2 = $a[1]; + $linearray = $a[2]; + } + $diffs = $this->diff_map($text1, $text2); + if (!$diffs) { + // No acceptable result. + $diffs = array ( + array ( + DIFF_DELETE, + $text1 + ), + array ( + DIFF_INSERT, + $text2 + ) + ); + } + if ($checklines) { + // Convert the diff back to original text. + $this->diff_charsToLines($diffs, $linearray); + // Eliminate freak matches (e.g. blank lines) + $this->diff_cleanupSemantic($diffs); + + // Rediff any replacement blocks, this time character-by-character. + // Add a dummy entry at the end. + array_push($diffs, array ( + DIFF_EQUAL, + '' + )); + $pointer = 0; + $count_delete = 0; + $count_insert = 0; + $text_delete = ''; + $text_insert = ''; + while ($pointer < count($diffs)) { + switch ($diffs[$pointer][0]) { + case DIFF_INSERT : + $count_insert++; + $text_insert .= $diffs[$pointer][1]; + break; + case DIFF_DELETE : + $count_delete++; + $text_delete .= $diffs[$pointer][1]; + break; + case DIFF_EQUAL : + // Upon reaching an equality, check for prior redundancies. + if ($count_delete >= 1 && $count_insert >= 1) { + // Delete the offending records and add the merged ones. + $a = $this->diff_main($text_delete, $text_insert, false); + array_splice($diffs, $pointer - $count_delete - $count_insert, $count_delete + $count_insert); + + $pointer = $pointer - $count_delete - $count_insert; + for ($j = count($a) - 1; $j >= 0; $j--) { + array_splice($diffs, $pointer, 0, array($a[$j])); + } + $pointer = $pointer +count($a); + } + $count_insert = 0; + $count_delete = 0; + $text_delete = ''; + $text_insert = ''; + break; + } + $pointer++; + } + array_pop($diffs); // Remove the dummy entry at the end. + } + return $diffs; + } + + /** + * Split two texts into an array of strings. Reduce the texts to a string of + * hashes where each Unicode character represents one line. + * @param {string} text1 First string. + * @param {string} text2 Second string. + * @return {Array.>} Three element Array, containing the + * encoded text1, the encoded text2 and the array of unique strings. The + * zeroth element of the array of unique strings is intentionally blank. + * @private + */ + function diff_linesToChars($text1, $text2) { + $lineArray = array(); // e.g. lineArray[4] == 'Hello\n' + $lineHash = array(); // e.g. lineHash['Hello\n'] == 4 + + // '\x00' is a valid character, but various debuggers don't like it. + // So we'll insert a junk entry to avoid generating a null character. + $lineArray[0] = ''; + + $chars1 = $this->diff_linesToCharsMunge($text1, $lineArray, $lineHash); + $chars2 = $this->diff_linesToCharsMunge($text2, $lineArray, $lineHash); + return array ( + $chars1, + $chars2, + $lineArray + ); + } + + /** + * Split a text into an array of strings. Reduce the texts to a string of + * hashes where each Unicode character represents one line. + * Modifies linearray and linehash through being a closure. + * @param {string} text String to encode + * @return {string} Encoded string + * @private + */ + function diff_linesToCharsMunge($text, &$lineArray, &$lineHash) { + $chars = ''; + // Walk the text, pulling out a mb_substring for each line. + // text.split('\n') would would temporarily double our memory footprint. + // Modifying text would create many large strings to garbage collect. + $lineStart = 0; + $lineEnd = -1; + // Keeping our own length variable is faster than looking it up. + $lineArrayLength = count($lineArray); + while ($lineEnd < mb_strlen($text) - 1) { + $lineEnd = mb_strpos($text, "\n", $lineStart); + if ($lineEnd === false) { + $lineEnd = mb_strlen($text) - 1; + } + $line = mb_substr($text, $lineStart, $lineEnd +1 -$lineStart); + $lineStart = $lineEnd +1; + + if ( isset($lineHash[$line]) ) { + $chars .= mb_chr($lineHash[$line]); + } else { + $chars .= mb_chr($lineArrayLength); + $lineHash[$line] = $lineArrayLength; + $lineArray[$lineArrayLength++] = $line; + } + } + return $chars; + } + /** + * Rehydrate the text in a diff from a string of line hashes to real lines of + * text. + * @param {Array.>} diffs Array of diff tuples. + * @param {Array.} lineArray Array of unique strings. + * @private + */ + function diff_charsToLines(&$diffs, $lineArray) { + for ($x = 0; $x < count($diffs); $x++) { + $chars = $diffs[$x][1]; + $text = array (); + for ($y = 0; $y < mb_strlen($chars); $y++) { + $text[$y] = $lineArray[charCodeAt($chars, $y)]; + } + $diffs[$x][1] = implode('',$text); + } + } + + /** + * Explore the intersection points between the two texts. + * @param {string} text1 Old string to be diffed. + * @param {string} text2 New string to be diffed. + * @return {Array.>?} Array of diff tuples or null if no + * diff available. + * @private + */ + function diff_map($text1, $text2) { + // Don't run for too long. + $ms_end = microtime(true) + $this->Diff_Timeout; + + // Cache the text lengths to prevent multiple calls. + $text1_length = mb_strlen($text1); + $text2_length = mb_strlen($text2); + $max_d = $text1_length + $text2_length -1; + $doubleEnd = $this->Diff_DualThreshold * 2 < $max_d; + $v_map1 = array(); + $v_map2 = array(); + $v1 = array(); + $v2 = array(); + $v1[1] = 0; + $v2[1] = 0; + $x = null; + $y = null; + $footstep = null; // Used to track overlapping paths. + $footsteps = array(); + $done = false; + // Safari 1.x doesn't have hasOwnProperty + //? $hasOwnProperty = !!(footsteps.hasOwnProperty); + // If the total number of characters is odd, then the front path will collide + // with the reverse path. + $front = ($text1_length + $text2_length) % 2; + for ($d = 0; $d < $max_d; $d++) { + // Bail out if timeout reached. + if ($this->Diff_Timeout > 0 && microtime(true) > $ms_end) { + return null; // zzz + } + + // Walk the front path one step. + $v_map1[$d] = array (); + for ($k = -$d; $k <= $d; $k += 2) { + if ($k == -$d || $k != $d && $v1[$k -1] < $v1[$k +1]) { + $x = $v1[$k +1]; + } else { + $x = $v1[$k -1] + 1; + } + $y = $x - $k; + if ($doubleEnd) { + $footstep = $x . ',' . $y; + if ($front && isset ($footsteps[$footstep])) { + $done = true; + } + if (!$front) { + $footsteps[$footstep] = $d; + } + } + while (!$done && ($x < $text1_length) && ($y < $text2_length) && (mb_substr($text1, $x, 1) == mb_substr($text2, $y, 1)) ) { + $x++; + $y++; + if ($doubleEnd) { + $footstep = $x . ',' . $y; + if ($front && isset ($footsteps[$footstep])) { + $done = true; + } + if (!$front) { + $footsteps[$footstep] = $d; + } + } + } + $v1[$k] = $x; + $v_map1[$d][$x . ',' . $y] = true; + if ($x == $text1_length && $y == $text2_length) { + // Reached the end in single-path mode. + return $this->diff_path1($v_map1, $text1, $text2); + } + elseif ($done) { + // Front path ran over reverse path. + + $v_map2 = array_slice($v_map2, 0, $footsteps[$footstep] + 1); + $a = $this->diff_path1($v_map1, mb_substr($text1, 0, $x), mb_substr($text2, 0, $y)); + + return array_merge($a, $this->diff_path2($v_map2, mb_substr($text1, $x), mb_substr($text2, $y))); + } + } + + if ($doubleEnd) { + // Walk the reverse path one step. + $v_map2[$d] = array(); + for ($k = -$d; $k <= $d; $k += 2) { + if ($k == -$d || $k != $d && $v2[$k -1] < $v2[$k +1]) { + $x = $v2[$k +1]; + } else { + $x = $v2[$k -1] + 1; + } + $y = $x - $k; + $footstep = ($text1_length - $x) . ',' . ($text2_length - $y); + if (!$front && isset ($footsteps[$footstep])) { + $done = true; + } + if ($front) { + $footsteps[$footstep] = $d; + } + while (!$done && $x < $text1_length && $y < $text2_length && mb_substr($text1, $text1_length - $x -1, 1) == mb_substr($text2, $text2_length - $y -1, 1) ) { + $x++; + $y++; + $footstep = ($text1_length - $x) . ',' . ($text2_length - $y); + if (!$front && isset ($footsteps[$footstep])) { + $done = true; + } + if ($front) { + $footsteps[$footstep] = $d; + } + } + $v2[$k] = $x; + $v_map2[$d][$x . ',' . $y] = true; + if ($done) { + // Reverse path ran over front path. + $v_map1 = array_slice($v_map1, 0, $footsteps[$footstep] + 1); + $a = $this->diff_path1($v_map1, mb_substr($text1, 0, $text1_length - $x), mb_substr($text2, 0, $text2_length - $y)); + return array_merge($a, $this->diff_path2($v_map2, mb_substr($text1, $text1_length - $x), mb_substr($text2, $text2_length - $y))); + } + } + } + } + // Number of diffs equals number of characters, no commonality at all. + return null; + } + + /** + * Work from the middle back to the start to determine the path. + * @param {Array.} v_map Array of paths.ers + * @param {string} text1 Old string fragment to be diffed. + * @param {string} text2 New string fragment to be diffed. + * @return {Array.>} Array of diff tuples. + * @private + */ + function diff_path1($v_map, $text1, $text2) { + $path = array (); + $x = mb_strlen($text1); + $y = mb_strlen($text2); + /** @type {number?} */ + $last_op = null; + for ($d = count($v_map) - 2; $d >= 0; $d--) { + while (1) { + if (isset ($v_map[$d][($x -1) . ',' . $y])) { + $x--; + if ($last_op === DIFF_DELETE) { + $path[0][1] = mb_substr($text1, $x, 1) . $path[0][1]; + } else { + array_unshift($path, array ( + DIFF_DELETE, + mb_substr($text1, $x, 1) + )); + } + $last_op = DIFF_DELETE; + break; + } elseif (isset ($v_map[$d][$x . ',' . ($y -1)])) { + $y--; + if ($last_op === DIFF_INSERT) { + $path[0][1] = mb_substr($text2, $y, 1) . $path[0][1]; + } else { + array_unshift($path, array ( + DIFF_INSERT, + mb_substr($text2, $y, 1) + )); + } + $last_op = DIFF_INSERT; + break; + } else { + $x--; + $y--; + //if (text1.charAt(x) != text2.charAt(y)) { + // throw new Error('No diagonal. Can\'t happen. (diff_path1)'); + //} + if ($last_op === DIFF_EQUAL) { + $path[0][1] = mb_substr($text1, $x, 1) . $path[0][1]; + } else { + array_unshift($path, array ( + DIFF_EQUAL, + mb_substr($text1, $x, 1) + )); + } + $last_op = DIFF_EQUAL; + } + } + } + return $path; + } + + /** + * Work from the middle back to the end to determine the path. + * @param {Array.} v_map Array of paths. + * @param {string} text1 Old string fragment to be diffed. + * @param {string} text2 New string fragment to be diffed. + * @return {Array.>} Array of diff tuples. + * @private + */ + function diff_path2($v_map, $text1, $text2) { + $path = array (); + $pathLength = 0; + $x = mb_strlen($text1); + $y = mb_strlen($text2); + /** @type {number?} */ + $last_op = null; + for ($d = count($v_map) - 2; $d >= 0; $d--) { + while (1) { + if (isset ($v_map[$d][($x -1) . ',' . $y])) { + $x--; + if ($last_op === DIFF_DELETE) { + $path[$pathLength -1][1] .= $text1[mb_strlen($text1) - $x -1]; + } else { + $path[$pathLength++] = array ( + DIFF_DELETE, + $text1[mb_strlen($text1) - $x -1] + ); + } + $last_op = DIFF_DELETE; + break; + } + elseif (isset ($v_map[$d][$x . ',' . ($y -1)])) { + $y--; + if ($last_op === DIFF_INSERT) { + $path[$pathLength -1][1] .= $text2[mb_strlen($text2) - $y -1]; + } else { + $path[$pathLength++] = array ( + DIFF_INSERT, + $text2[mb_strlen($text2) - $y -1] + ); + } + $last_op = DIFF_INSERT; + break; + } else { + $x--; + $y--; + //if (text1.charAt(text1.length - x - 1) != + // text2.charAt(text2.length - y - 1)) { + // throw new Error('No diagonal. Can\'t happen. (diff_path2)'); + //} + if ($last_op === DIFF_EQUAL) { + $path[$pathLength -1][1] .= $text1[mb_strlen($text1) - $x -1]; + } else { + $path[$pathLength++] = array ( + DIFF_EQUAL, + $text1[mb_strlen($text1) - $x -1] + ); + } + $last_op = DIFF_EQUAL; + } + } + } + return $path; + } + + /** + * Determine the common prefix of two strings + * @param {string} text1 First string. + * @param {string} text2 Second string. + * @return {number} The number of characters common to the start of each + * string. + */ + function diff_commonPrefix($text1, $text2) { + for ($i = 0; 1; $i++) { + $t1 = mb_substr($text1, $i, 1); + $t2 = mb_substr($text2, $i, 1); + if($t1==='' || $t2==='' || $t1 !== $t2 ){ + return $i; + } + } + } + + /** + * Determine the common suffix of two strings + * @param {string} text1 First string. + * @param {string} text2 Second string. + * @return {number} The number of characters common to the end of each string. + */ + function diff_commonSuffix($text1, $text2) { + return $this->diff_commonPrefix( strrev($text1), strrev($text2) ); + } + + /** + * Do the two texts share a mb_substring which is at least half the length of the + * longer text? + * @param {string} text1 First string. + * @param {string} text2 Second string. + * @return {Array.?} Five element Array, containing the prefix of + * text1, the suffix of text1, the prefix of text2, the suffix of + * text2 and the common middle. Or null if there was no match. + */ + function diff_halfMatch($text1, $text2) { + $longtext = mb_strlen($text1) > mb_strlen($text2) ? $text1 : $text2; + $shorttext = mb_strlen($text1) > mb_strlen($text2) ? $text2 : $text1; + if (mb_strlen($longtext) < 10 || mb_strlen($shorttext) < 1) { + return null; // Pointless. + } + + // First check if the second quarter is the seed for a half-match. + $hm1 = $this->diff_halfMatchI($longtext, $shorttext, ceil(mb_strlen($longtext) / 4)); + // Check again based on the third quarter. + $hm2 = $this->diff_halfMatchI($longtext, $shorttext, ceil(mb_strlen($longtext) / 2)); + + if (!$hm1 && !$hm2) { + return null; + } elseif (!$hm2) { + $hm = $hm1; + } elseif (!$hm1) { + $hm = $hm2; + } else { + // Both matched. Select the longest. + $hm = mb_strlen($hm1[4]) > mb_strlen($hm2[4]) ? $hm1 : $hm2; + } + + // A half-match was found, sort out the return data. + if (mb_strlen($text1) > mb_strlen($text2)) { + $text1_a = $hm[0]; + $text1_b = $hm[1]; + $text2_a = $hm[2]; + $text2_b = $hm[3]; + } else { + $text2_a = $hm[0]; + $text2_b = $hm[1]; + $text1_a = $hm[2]; + $text1_b = $hm[3]; + } + $mid_common = $hm[4]; + return array( $text1_a, $text1_b, $text2_a, $text2_b, $mid_common ); + } + + /** + * Does a mb_substring of shorttext exist within longtext such that the mb_substring + * is at least half the length of longtext? + * Closure, but does not reference any external variables. + * @param {string} longtext Longer string. + * @param {string} shorttext Shorter string. + * @param {number} i Start index of quarter length mb_substring within longtext + * @return {Array.?} Five element Array, containing the prefix of + * longtext, the suffix of longtext, the prefix of shorttext, the suffix + * of shorttext and the common middle. Or null if there was no match. + * @private + */ + function diff_halfMatchI($longtext, $shorttext, $i) { + // Start with a 1/4 length mb_substring at position i as a seed. + $seed = mb_substr($longtext, $i, floor(mb_strlen($longtext) / 4)); + + $j = -1; + $best_common = ''; + $best_longtext_a = null; + $best_longtext_b = null; + $best_shorttext_a = null; + $best_shorttext_b = null; + while ( ($j = mb_strpos($shorttext, $seed, $j + 1)) !== false ) { + $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)); + if (mb_strlen($best_common) < $suffixLength + $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_b = mb_substr($longtext, $i + $prefixLength); + $best_shorttext_a = mb_substr($shorttext, 0, $j - $suffixLength); + $best_shorttext_b = mb_substr($shorttext, $j + $prefixLength); + } + } + if (mb_strlen($best_common) >= mb_strlen($longtext) / 2) { + return array ( + $best_longtext_a, + $best_longtext_b, + $best_shorttext_a, + $best_shorttext_b, + $best_common + ); + } else { + return null; + } + } + + /** + * Reduce the number of edits by eliminating semantically trivial equalities. + * @param {Array.>} diffs Array of diff tuples. + */ + function diff_cleanupSemantic(&$diffs) { + $changes = false; + $equalities = array (); // Stack of indices where equalities are found. + $equalitiesLength = 0; // Keeping our own length var is faster in JS. + $lastequality = null; // Always equal to equalities[equalitiesLength-1][1] + $pointer = 0; // Index of current position. + // Number of characters that changed prior to the equality. + $length_changes1 = 0; + // Number of characters that changed after the equality. + $length_changes2 = 0; + while ($pointer < count($diffs)) { + if ($diffs[$pointer][0] == DIFF_EQUAL) { // equality found + $equalities[$equalitiesLength++] = $pointer; + $length_changes1 = $length_changes2; + $length_changes2 = 0; + $lastequality = $diffs[$pointer][1]; + } else { // an insertion or deletion + $length_changes2 += mb_strlen($diffs[$pointer][1]); + if ($lastequality !== null && (mb_strlen($lastequality) <= $length_changes1) && (mb_strlen($lastequality) <= $length_changes2)) { + // Duplicate record + $zzz_diffs = array_splice($diffs, $equalities[$equalitiesLength -1], 0, array(array ( + DIFF_DELETE, + $lastequality + ))); + // Change second copy to insert. + $diffs[$equalities[$equalitiesLength -1] + 1][0] = DIFF_INSERT; + // Throw away the equality we just deleted. + $equalitiesLength--; + // Throw away the previous equality (it needs to be reevaluated). + $equalitiesLength--; + $pointer = $equalitiesLength > 0 ? $equalities[$equalitiesLength -1] : -1; + $length_changes1 = 0; // Reset the counters. + $length_changes2 = 0; + $lastequality = null; + $changes = true; + } + } + $pointer++; + } + if ($changes) { + $this->diff_cleanupMerge($diffs); + } + $this->diff_cleanupSemanticLossless($diffs); + } + + /** + * Look for single edits surrounded on both sides by equalities + * which can be shifted sideways to align the edit to a word boundary. + * e.g: The cat came. -> The cat came. + * @param {Array.>} diffs Array of diff tuples. + */ + function diff_cleanupSemanticLossless(&$diffs) { + + $pointer = 1; + // Intentionally ignore the first and last element (don't need checking). + while ($pointer < count($diffs) - 1) { + if ($diffs[$pointer -1][0] == DIFF_EQUAL && $diffs[$pointer +1][0] == DIFF_EQUAL) { + // This is a single edit surrounded by equalities. + $equality1 = $diffs[$pointer -1][1]; + $edit = $diffs[$pointer][1]; + $equality2 = $diffs[$pointer +1][1]; + + // First, shift the edit as far left as possible. + $commonOffset = $this->diff_commonSuffix($equality1, $edit); + if ($commonOffset !== '') { + $commonString = mb_substr($edit, mb_strlen($edit) - $commonOffset); + $equality1 = mb_substr($equality1, 0, mb_strlen($equality1) - $commonOffset); + $edit = $commonString . mb_substr($edit, 0, mb_strlen($edit) - $commonOffset); + $equality2 = $commonString . $equality2; + } + + // Second, step character by character right, looking for the best fit. + $bestEquality1 = $equality1; + $bestEdit = $edit; + $bestEquality2 = $equality2; + $bestScore = $this->diff_cleanupSemanticScore($equality1, $edit) + $this->diff_cleanupSemanticScore($edit, $equality2); + while (isset($equality2[0]) && $edit[0] === $equality2[0]) { + $equality1 .= $edit[0]; + $edit = mb_substr($edit, 1) . $equality2[0]; + $equality2 = mb_substr($equality2, 1); + $score = $this->diff_cleanupSemanticScore($equality1, $edit) + $this->diff_cleanupSemanticScore($edit, $equality2); + // The >= encourages trailing rather than leading whitespace on edits. + if ($score >= $bestScore) { + $bestScore = $score; + $bestEquality1 = $equality1; + $bestEdit = $edit; + $bestEquality2 = $equality2; + } + } + + if ($diffs[$pointer -1][1] != $bestEquality1) { + // We have an improvement, save it back to the diff. + if ($bestEquality1) { + $diffs[$pointer -1][1] = $bestEquality1; + } else { + $zzz_diffs = array_splice($diffs, $pointer -1, 1); + $pointer--; + } + $diffs[$pointer][1] = $bestEdit; + if ($bestEquality2) { + $diffs[$pointer +1][1] = $bestEquality2; + } else { + $zzz_diffs = array_splice($diffs, $pointer +1, 1); + $pointer--; + } + } + } + $pointer++; + } + } + + /** + * Given two strings, compute a score representing whether the internal + * boundary falls on logical boundaries. + * Scores range from 5 (best) to 0 (worst). + * Closure, makes reference to regex patterns defined above. + * @param {string} one First string + * @param {string} two Second string + * @return {number} The score. + */ + function diff_cleanupSemanticScore($one, $two) { + // Define some regex patterns for matching boundaries. + $punctuation = '/[^a-zA-Z0-9]/'; + $whitespace = '/\s/'; + $linebreak = '/[\r\n]/'; + $blanklineEnd = '/\n\r?\n$/'; + $blanklineStart = '/^\r?\n\r?\n/'; + + if (!$one || !$two) { + // Edges are the best. + return 5; + } + + // Each port of this function behaves slightly differently due to + // subtle differences in each language's definition of things like + // 'whitespace'. Since this function's purpose is largely cosmetic, + // the choice has been made to use each language's native features + // rather than force total conformity. + $score = 0; + // One point for non-alphanumeric. + if (preg_match($punctuation, $one[mb_strlen($one) - 1]) || preg_match($punctuation, $two[0])) { + $score++; + // Two points for whitespace. + if (preg_match($whitespace, $one[mb_strlen($one) - 1] ) || preg_match($whitespace, $two[0])) { + $score++; + // Three points for line breaks. + if (preg_match($linebreak, $one[mb_strlen($one) - 1]) || preg_match($linebreak, $two[0])) { + $score++; + // Four points for blank lines. + if (preg_match($blanklineEnd, $one) || preg_match($blanklineStart, $two)) { + $score++; + } + } + } + } + return $score; + } + + /** + * Reduce the number of edits by eliminating operationally trivial equalities. + * @param {Array.>} diffs Array of diff tuples. + */ + function diff_cleanupEfficiency(&$diffs) { + $changes = false; + $equalities = array (); // Stack of indices where equalities are found. + $equalitiesLength = 0; // Keeping our own length var is faster in JS. + $lastequality = ''; // Always equal to equalities[equalitiesLength-1][1] + $pointer = 0; // Index of current position. + // Is there an insertion operation before the last equality. + $pre_ins = false; + // Is there a deletion operation before the last equality. + $pre_del = false; + // Is there an insertion operation after the last equality. + $post_ins = false; + // Is there a deletion operation after the last equality. + $post_del = false; + while ($pointer < count($diffs)) { + if ($diffs[$pointer][0] == DIFF_EQUAL) { // equality found + if (mb_strlen($diffs[$pointer][1]) < $this->Diff_EditCost && ($post_ins || $post_del)) { + // Candidate found. + $equalities[$equalitiesLength++] = $pointer; + $pre_ins = $post_ins; + $pre_del = $post_del; + $lastequality = $diffs[$pointer][1]; + } else { + // Not a candidate, and can never become one. + $equalitiesLength = 0; + $lastequality = ''; + } + $post_ins = $post_del = false; + } else { // an insertion or deletion + if ($diffs[$pointer][0] == DIFF_DELETE) { + $post_del = true; + } else { + $post_ins = true; + } + /* + * Five types to be split: + * ABXYCD + * AXCD + * ABXC + * AXCD + * ABXC + */ + 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))) { + // Duplicate record + $zzz_diffs = array_splice($diffs, $equalities[$equalitiesLength -1], 0, array(array ( + DIFF_DELETE, + $lastequality + ))); + // Change second copy to insert. + $diffs[$equalities[$equalitiesLength -1] + 1][0] = DIFF_INSERT; + $equalitiesLength--; // Throw away the equality we just deleted; + $lastequality = ''; + if ($pre_ins && $pre_del) { + // No changes made which could affect previous entry, keep going. + $post_ins = $post_del = true; + $equalitiesLength = 0; + } else { + $equalitiesLength--; // Throw away the previous equality; + $pointer = $equalitiesLength > 0 ? $equalities[$equalitiesLength -1] : -1; + $post_ins = $post_del = false; + } + $changes = true; + } + } + $pointer++; + } + + if ($changes) { + $this->diff_cleanupMerge($diffs); + } + } + + /** + * Reorder and merge like edit sections. Merge equalities. + * Any edit section can move as long as it doesn't cross an equality. + * @param {Array.>} diffs Array of diff tuples. + */ + function diff_cleanupMerge(&$diffs) { + array_push($diffs, array ( DIFF_EQUAL, '' )); // Add a dummy entry at the end. + $pointer = 0; + $count_delete = 0; + $count_insert = 0; + $text_delete = ''; + $text_insert = ''; + $commonlength = null; + while ($pointer < count($diffs)) { + switch ($diffs[$pointer][0]) { + case DIFF_INSERT : + $count_insert++; + $text_insert .= $diffs[$pointer][1]; + $pointer++; + break; + case DIFF_DELETE : + $count_delete++; + $text_delete .= $diffs[$pointer][1]; + $pointer++; + break; + case DIFF_EQUAL : + // Upon reaching an equality, check for prior redundancies. + if ($count_delete !== 0 || $count_insert !== 0) { + if ($count_delete !== 0 && $count_insert !== 0) { + // Factor out any common prefixies. + $commonlength = $this->diff_commonPrefix($text_insert, $text_delete); + if ($commonlength !== 0) { + if (($pointer - $count_delete - $count_insert) > 0 && $diffs[$pointer - $count_delete - $count_insert -1][0] == DIFF_EQUAL) { + $diffs[$pointer - $count_delete - $count_insert -1][1] .= mb_substr($text_insert, 0, $commonlength); + } else { + array_splice($diffs, 0, 0, array(array ( + DIFF_EQUAL, + mb_substr($text_insert, 0, $commonlength) + ))); + $pointer++; + } + $text_insert = mb_substr($text_insert, $commonlength); + $text_delete = mb_substr($text_delete, $commonlength); + } + // Factor out any common suffixies. + $commonlength = $this->diff_commonSuffix($text_insert, $text_delete); + if ($commonlength !== 0) { + $diffs[$pointer][1] = mb_substr($text_insert, mb_strlen($text_insert) - $commonlength) . $diffs[$pointer][1]; + $text_insert = mb_substr($text_insert, 0, mb_strlen($text_insert) - $commonlength); + $text_delete = mb_substr($text_delete, 0, mb_strlen($text_delete) - $commonlength); + } + } + // Delete the offending records and add the merged ones. + if ($count_delete === 0) { + array_splice($diffs, $pointer-$count_delete-$count_insert, $count_delete+$count_insert, array(array( + DIFF_INSERT, + $text_insert + ))); + } elseif ($count_insert === 0) { + array_splice($diffs, $pointer-$count_delete-$count_insert, $count_delete+$count_insert, array(array( + DIFF_DELETE, + $text_delete + ))); + } else { + array_splice($diffs, $pointer-$count_delete-$count_insert, $count_delete+$count_insert, array(array( + DIFF_DELETE, + $text_delete + ), array ( + DIFF_INSERT, + $text_insert + ))); + } + $pointer = $pointer - $count_delete - $count_insert + ($count_delete ? 1 : 0) + ($count_insert ? 1 : 0) + 1; + } elseif ($pointer !== 0 && $diffs[$pointer -1][0] == DIFF_EQUAL) { + // Merge this equality with the previous one. + $diffs[$pointer -1][1] .= $diffs[$pointer][1]; + array_splice($diffs, $pointer, 1); + } else { + $pointer++; + } + $count_insert = 0; + $count_delete = 0; + $text_delete = ''; + $text_insert = ''; + break; + } + } + if ($diffs[count($diffs) - 1][1] === '') { + array_pop($diffs); // Remove the dummy entry at the end. + } + + // Second pass: look for single edits surrounded on both sides by equalities + // which can be shifted sideways to eliminate an equality. + // e.g: ABAC -> ABAC + $changes = false; + $pointer = 1; + // Intentionally ignore the first and last element (don't need checking). + while ($pointer < count($diffs) - 1) { + if ($diffs[$pointer-1][0] == DIFF_EQUAL && $diffs[$pointer+1][0] == DIFF_EQUAL) { + // 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]) { + // 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][1] = $diffs[$pointer -1][1] . $diffs[$pointer +1][1]; + array_splice($diffs, $pointer -1, 1); + $changes = true; + } elseif (mb_substr($diffs[$pointer][1], 0, mb_strlen($diffs[$pointer +1][1])) == $diffs[$pointer +1][1]) { + // Shift the edit over the next equality. + $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]; + array_splice($diffs, $pointer +1, 1); + $changes = true; + } + } + $pointer++; + } + // If shifts were made, the diff needs reordering and another shift sweep. + if ($changes) { + $this->diff_cleanupMerge($diffs); + } + } + + /** + * loc is a location in text1, compute and return the equivalent location in + * text2. + * e.g. 'The cat' vs 'The big cat', 1->1, 5->8 + * @param {Array.>} diffs Array of diff tuples. + * @param {number} loc Location within text1. + * @return {number} Location within text2. + */ + function diff_xIndex($diffs, $loc) { + $chars1 = 0; + $chars2 = 0; + $last_chars1 = 0; + $last_chars2 = 0; + for ($x = 0; $x < count($diffs); $x++) { + if ($diffs[$x][0] !== DIFF_INSERT) { // Equality or deletion. + $chars1 += mb_strlen($diffs[$x][1]); + } + if ($diffs[$x][0] !== DIFF_DELETE) { // Equality or insertion. + $chars2 += mb_strlen($diffs[$x][1]); + } + if ($chars1 > $loc) { // Overshot the location. + break; + } + $last_chars1 = $chars1; + $last_chars2 = $chars2; + } + // Was the location was deleted? + if (count($diffs) != $x && $diffs[$x][0] === DIFF_DELETE) { + return $last_chars2; + } + // Add the remaining character length. + return $last_chars2 + ($loc - $last_chars1); + } + + /** + * Convert a diff array into a pretty HTML report. + * @param {Array.>} diffs Array of diff tuples. + * @return {string} HTML representation. + */ + function diff_prettyHtml($diffs) { + $html = array (); + $i = 0; + for ($x = 0; $x < count($diffs); $x++) { + $op = $diffs[$x][0]; // Operation (insert, delete, equal) + $data = $diffs[$x][1]; // Text of change. + $text = preg_replace(array ( + '/&/', + '//', + "/\n/" + ), array ( + '&', + '<', + '>', + '¶
' + ), $data); + + switch ($op) { + case DIFF_INSERT : + $html[$x] = '' . $text . ''; + break; + case DIFF_DELETE : + $html[$x] = '' . $text . ''; + break; + case DIFF_EQUAL : + $html[$x] = '' . $text . ''; + break; + } + if ($op !== DIFF_DELETE) { + $i += mb_strlen($data); + } + } + return implode('',$html); + } + + /** + * Compute and return the source text (all equalities and deletions). + * @param {Array.>} diffs Array of diff tuples. + * @return {string} Source text. + */ + function diff_text1($diffs) { + $text = array (); + for ($x = 0; $x < count($diffs); $x++) { + if ($diffs[$x][0] !== DIFF_INSERT) { + $text[$x] = $diffs[$x][1]; + } + } + return implode('',$text); + } + + /** + * Compute and return the destination text (all equalities and insertions). + * @param {Array.>} diffs Array of diff tuples. + * @return {string} Destination text. + */ + function diff_text2($diffs) { + $text = array (); + for ($x = 0; $x < count($diffs); $x++) { + if ($diffs[$x][0] !== DIFF_DELETE) { + $text[$x] = $diffs[$x][1]; + } + } + return implode('',$text); + } + + /** + * Compute the Levenshtein distance; the number of inserted, deleted or + * substituted characters. + * @param {Array.>} diffs Array of diff tuples. + * @return {number} Number of changes. + */ + function diff_levenshtein($diffs) { + $levenshtein = 0; + $insertions = 0; + $deletions = 0; + for ($x = 0; $x < count($diffs); $x++) { + $op = $diffs[$x][0]; + $data = $diffs[$x][1]; + switch ($op) { + case DIFF_INSERT : + $insertions += mb_strlen($data); + break; + case DIFF_DELETE : + $deletions += mb_strlen($data); + break; + case DIFF_EQUAL : + // A deletion and an insertion is one substitution. + $levenshtein += max($insertions, $deletions); + $insertions = 0; + $deletions = 0; + break; + } + } + $levenshtein += max($insertions, $deletions); + return $levenshtein; + } + + /** + * Crush the diff into an encoded string which describes the operations + * required to transform text1 into text2. + * E.g. =3\t-2\t+ing -> Keep 3 chars, delete 2 chars, insert 'ing'. + * Operations are tab-separated. Inserted text is escaped using %xx notation. + * @param {Array.>} diffs Array of diff tuples. + * @return {string} Delta text. + */ + function diff_toDelta($diffs) { + $text = array (); + for ($x = 0; $x < count($diffs); $x++) { + switch ($diffs[$x][0]) { + case DIFF_INSERT : + $text[$x] = '+' .encodeURI($diffs[$x][1]); + break; + case DIFF_DELETE : + $text[$x] = '-' .mb_strlen($diffs[$x][1]); + break; + case DIFF_EQUAL : + $text[$x] = '=' .mb_strlen($diffs[$x][1]); + break; + } + } + return str_replace('%20', ' ', implode("\t", $text)); + } + + /** + * Given the original text1, and an encoded string which describes the + * operations required to transform text1 into text2, compute the full diff. + * @param {string} text1 Source string for the diff. + * @param {string} delta Delta text. + * @return {Array.>} Array of diff tuples. + * @throws {Error} If invalid input. + */ + function diff_fromDelta($text1, $delta) { + $diffs = array (); + $diffsLength = 0; // Keeping our own length var is faster in JS. + $pointer = 0; // Cursor in text1 + $tokens = preg_split("/\t/", $delta); + + for ($x = 0; $x < count($tokens); $x++) { + // Each token begins with a one character parameter which specifies the + // operation of this token (delete, insert, equality). + $param = mb_substr($tokens[$x], 1); + switch ($tokens[$x][0]) { + case '+' : + try { + $diffs[$diffsLength++] = array ( + DIFF_INSERT, + decodeURI($param) + ); + } catch (Exception $ex) { + echo_Exception('Illegal escape in diff_fromDelta: ' . $param); + // Malformed URI sequence. + } + break; + case '-' : + // Fall through. + case '=' : + $n = (int) $param; + if ($n < 0) { + echo_Exception('Invalid number in diff_fromDelta: ' . $param); + } + $text = mb_substr($text1, $pointer, $n); + $pointer += $n; + if ($tokens[$x][0] == '=') { + $diffs[$diffsLength++] = array ( + DIFF_EQUAL, + $text + ); + } else { + $diffs[$diffsLength++] = array ( + DIFF_DELETE, + $text + ); + } + break; + default : + // Blank tokens are ok (from a trailing \t). + // Anything else is an error. + if ($tokens[$x]) { + echo_Exception('Invalid diff operation in diff_fromDelta: ' . $tokens[$x]); + } + } + } + if ($pointer != mb_strlen($text1)) { +// throw new Exception('Delta length (' . $pointer . ') does not equal source text length (' . mb_strlen($text1) . ').'); + echo_Exception('Delta length (' . $pointer . ') does not equal source text length (' . mb_strlen($text1) . ').'); + } + return $diffs; + } + + // MATCH FUNCTIONS + + /** + * Locate the best instance of 'pattern' in 'text' near 'loc'. + * @param {string} text The text to search. + * @param {string} pattern The pattern to search for. + * @param {number} loc The location to search around. + * @return {number} Best match index or -1. + */ + function match_main($text, $pattern, $loc) { + $loc = max(0, min($loc, mb_strlen($text))); + if ($text == $pattern) { + // Shortcut (potentially not guaranteed by the algorithm) + return 0; + } + elseif (!mb_strlen($text)) { + // Nothing to match. + return -1; + } + elseif (mb_substr($text, $loc, mb_strlen($pattern)) == $pattern) { + // Perfect match at the perfect spot! (Includes case of null pattern) + return $loc; + } else { + // Do a fuzzy compare. + return $this->match_bitap($text, $pattern, $loc); + } + } + + /** + * Locate the best instance of 'pattern' in 'text' near 'loc' using the + * Bitap algorithm. + * @param {string} text The text to search. + * @param {string} pattern The pattern to search for. + * @param {number} loc The location to search around. + * @return {number} Best match index or -1. + * @private + */ + function match_bitap($text, $pattern, $loc) { + if (mb_strlen($pattern) > Match_MaxBits) { + echo_Exception('Pattern too long for this browser.'); + } + + // Initialise the alphabet. + $s = $this->match_alphabet($pattern); + + // Highest score beyond which we give up. + $score_threshold = $this->Match_Threshold; + + // Is there a nearby exact match? (speedup) + $best_loc = mb_strpos($text, $pattern, $loc); + if ($best_loc !== false) { + $score_threshold = min($this->match_bitapScore(0, $best_loc, $pattern, $loc), $score_threshold); + } + + // What about in the other direction? (speedup) + $best_loc = mb_strrpos( $text, $pattern, min($loc + mb_strlen($pattern), mb_strlen($text)) ); + if ($best_loc !== false) { + $score_threshold = min($this->match_bitapScore(0, $best_loc, $pattern, $loc), $score_threshold); + } + + // Initialise the bit arrays. + $matchmask = 1 << (mb_strlen($pattern) - 1); + $best_loc = -1; + + $bin_min = null; + $bin_mid = null; + $bin_max = mb_strlen($pattern) + mb_strlen($text); + $last_rd = null; + for ($d = 0; $d < mb_strlen($pattern); $d++) { + // 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 + // error level. + $bin_min = 0; + $bin_mid = $bin_max; + while ($bin_min < $bin_mid) { + if ($this->match_bitapScore($d, $loc + $bin_mid, $pattern, $loc) <= $score_threshold) { + $bin_min = $bin_mid; + } else { + $bin_max = $bin_mid; + } + $bin_mid = floor(($bin_max - $bin_min) / 2 + $bin_min); + } + // Use the result from this iteration as the maximum for the next. + $bin_max = $bin_mid; + $start = max(1, $loc - $bin_mid +1); + $finish = min($loc + $bin_mid, mb_strlen($text)) + mb_strlen($pattern); + + $rd = Array ( + $finish +2 + ); + $rd[$finish +1] = (1 << $d) - 1; + for ($j = $finish; $j >= $start; $j--) { + // The alphabet (s) is a sparse hash, so the following line generates + // warnings. +@ $charMatch = $s[ $text[$j -1] ]; + if ($d === 0) { // First pass: exact match. + $rd[$j] = (($rd[$j +1] << 1) | 1) & $charMatch; + } else { // Subsequent passes: fuzzy match. + $rd[$j] = (($rd[$j +1] << 1) | 1) & $charMatch | ((($last_rd[$j +1] | $last_rd[$j]) << 1) | 1) | $last_rd[$j +1]; + } + if ($rd[$j] & $matchmask) { + $score = $this->match_bitapScore($d, $j -1, $pattern, $loc); + // This match will almost certainly be better than any existing match. + // But check anyway. + if ($score <= $score_threshold) { + // Told you so. + $score_threshold = $score; + $best_loc = $j -1; + if ($best_loc > $loc) { + // When passing loc, don't exceed our current distance from loc. + $start = max(1, 2 * $loc - $best_loc); + } else { + // Already passed loc, downhill from here on in. + break; + } + } + } + } + // No hope for a (better) match at greater error levels. + if ($this->match_bitapScore($d +1, $loc, $pattern, $loc) > $score_threshold) { + break; + } + $last_rd = $rd; + } + return (int)$best_loc; + } + + /** + * Compute and return the score for a match with e errors and x location. + * Accesses loc and pattern through being a closure. + * @param {number} e Number of errors in match. + * @param {number} x Location of match. + * @return {number} Overall score for match (0.0 = good, 1.0 = bad). + * @private + */ + function match_bitapScore($e, $x, $pattern, $loc) { + $accuracy = $e / mb_strlen($pattern); + $proximity = abs($loc - $x); + if (!$this->Match_Distance) { + // Dodge divide by zero error. + return $proximity ? 1.0 : $accuracy; + } + return $accuracy + ($proximity / $this->Match_Distance); + } + + /** + * Initialise the alphabet for the Bitap algorithm. + * @param {string} pattern The text to encode. + * @return {Object} Hash of character locations. + * @private + */ + function match_alphabet($pattern) { + $s = array (); + for ($i = 0; $i < mb_strlen($pattern); $i++) { + $s[ $pattern[$i] ] = 0; + } + for ($i = 0; $i < mb_strlen($pattern); $i++) { + $s[ $pattern[$i] ] |= 1 << (mb_strlen($pattern) - $i - 1); + } + return $s; + } + + // PATCH FUNCTIONS + + /** + * Increase the context until it is unique, + * but don't let the pattern expand beyond Match_MaxBits. + * @param {patch_obj} patch The patch to grow. + * @param {string} text Source text. + * @private + */ + function patch_addContext($patch, $text) { + $pattern = mb_substr($text, $patch->start2, $patch->length1 ); + $previousPattern = null; + $padding = 0; + $i = 0; + while ( + ( mb_strlen($pattern) === 0 // Javascript's indexOf/lastIndexOd return 0/strlen respectively if pattern = '' + || mb_strpos($text, $pattern) !== mb_strrpos($text, $pattern) + ) + && $pattern !== $previousPattern // avoid infinte loop + && mb_strlen($pattern) < Match_MaxBits - $this->Patch_Margin - $this->Patch_Margin ) { + $padding += $this->Patch_Margin; + $previousPattern = $pattern; + $pattern = mb_substr($text, max($patch->start2 - $padding,0), ($patch->start2 + $patch->length1 + $padding) - max($patch->start2 - $padding,0) ); + } + // Add one chunk for good luck. + $padding += $this->Patch_Margin; + // Add the prefix. + $prefix = mb_substr($text, max($patch->start2 - $padding,0), $patch->start2 - max($patch->start2 - $padding,0) ); + if ($prefix!=='') { + array_unshift($patch->diffs, array ( + DIFF_EQUAL, + $prefix + )); + } + // Add the suffix. + $suffix = mb_substr($text, $patch->start2 + $patch->length1, ($patch->start2 + $patch->length1 + $padding) - ($patch->start2 + $patch->length1) ); + if ($suffix!=='') { + array_push($patch->diffs, array ( + DIFF_EQUAL, + $suffix + )); + } + + // Roll back the start points. + $patch->start1 -= mb_strlen($prefix); + $patch->start2 -= mb_strlen($prefix); + // Extend the lengths. + $patch->length1 += mb_strlen($prefix) + mb_strlen($suffix); + $patch->length2 += mb_strlen($prefix) + mb_strlen($suffix); + } + + /** + * Compute a list of patches to turn text1 into text2. + * Use diffs if provided, otherwise compute it ourselves. + * There are four ways to call this function, depending on what data is + * available to the caller: + * Method 1: + * a = text1, b = text2 + * Method 2: + * a = diffs + * Method 3 (optimal): + * a = text1, b = diffs + * Method 4 (deprecated, use method 3): + * a = text1, b = text2, c = diffs + * + * @param {string|Array.>} a text1 (methods 1,3,4) or + * Array of diff tuples for text1 to text2 (method 2). + * @param {string|Array.>} opt_b text2 (methods 1,4) or + * Array of diff tuples for text1 to text2 (method 3) or undefined (method 2). + * @param {string|Array.>} opt_c Array of diff tuples for + * text1 to text2 (method 4) or undefined (methods 1,2,3). + * @return {Array.} Array of patch objects. + */ + function patch_make($a, $opt_b = null, $opt_c = null ) { + if (is_string($a) && is_string($opt_b) && $opt_c === null ) { + // Method 1: text1, text2 + // Compute diffs from text1 and text2. + $text1 = $a; + $diffs = $this->diff_main($text1, $opt_b, true); + if ( count($diffs) > 2) { + $this->diff_cleanupSemantic($diffs); + $this->diff_cleanupEfficiency($diffs); + } + } elseif ( is_array($a) && $opt_b === null && $opt_c === null) { + // Method 2: diffs + // Compute text1 from diffs. + $diffs = $a; + $text1 = $this->diff_text1($diffs); + } elseif ( is_string($a) && is_array($opt_b) && $opt_c === null) { + // Method 3: text1, diffs + $text1 = $a; + $diffs = $opt_b; + } elseif ( is_string($a) && is_string($opt_b) && is_array($opt_c) ) { + // Method 4: text1, text2, diffs + // text2 is not used. + $text1 = $a; + $diffs = $opt_c; + } else { + echo_Exception('Unknown call format to patch_make.'); + } + + if ( count($diffs) === 0) { + return array(); // Get rid of the null case. + } + $patches = array(); + $patch = new patch_obj(); + $patchDiffLength = 0; // Keeping our own length var is faster in JS. + $char_count1 = 0; // Number of characters into the text1 string. + $char_count2 = 0; // Number of characters into the text2 string. + // Start with text1 (prepatch_text) and apply the diffs until we arrive at + // text2 (postpatch_text). We recreate the patches one by one to determine + // context info. + $prepatch_text = $text1; + $postpatch_text = $text1; + for ($x = 0; $x < count($diffs); $x++) { + $diff_type = $diffs[$x][0]; + $diff_text = $diffs[$x][1]; + + if (!$patchDiffLength && $diff_type !== DIFF_EQUAL) { + // A new patch starts here. + $patch->start1 = $char_count1; + $patch->start2 = $char_count2; + } + + switch ($diff_type) { + case DIFF_INSERT : + $patch->diffs[$patchDiffLength++] = $diffs[$x]; + $patch->length2 += mb_strlen($diff_text); + $postpatch_text = mb_substr($postpatch_text, 0, $char_count2) . $diff_text . mb_substr($postpatch_text,$char_count2); + break; + case DIFF_DELETE : + $patch->length1 += mb_strlen($diff_text); + $patch->diffs[$patchDiffLength++] = $diffs[$x]; + $postpatch_text = mb_substr($postpatch_text, 0, $char_count2) . mb_substr($postpatch_text, $char_count2 + mb_strlen($diff_text) ); + break; + case DIFF_EQUAL : + if ( mb_strlen($diff_text) <= 2 * $this->Patch_Margin && $patchDiffLength && count($diffs) != $x + 1) { + // Small equality inside a patch. + $patch->diffs[$patchDiffLength++] = $diffs[$x]; + $patch->length1 += mb_strlen($diff_text); + $patch->length2 += mb_strlen($diff_text); + } elseif ( mb_strlen($diff_text) >= 2 * $this->Patch_Margin ) { + // Time for a new patch. + if ($patchDiffLength) { + $this->patch_addContext($patch, $prepatch_text); + array_push($patches,$patch); + $patch = new patch_obj(); + $patchDiffLength = 0; + // Unlike Unidiff, our patch lists have a rolling context. + // http://code.google.com/p/google-diff-match-patch/wiki/Unidiff + // Update prepatch text & pos to reflect the application of the + // just completed patch. + $prepatch_text = $postpatch_text; + $char_count1 = $char_count2; + } + } + break; + } + + // Update the current character count. + if ($diff_type !== DIFF_INSERT) { + $char_count1 += mb_strlen($diff_text); + } + if ($diff_type !== DIFF_DELETE) { + $char_count2 += mb_strlen($diff_text); + } + } + // Pick up the leftover patch if not empty. + if ($patchDiffLength) { + $this->patch_addContext($patch, $prepatch_text); + array_push($patches, $patch); + } + + return $patches; + } + + /** + * Given an array of patches, return another array that is identical. + * @param {Array.} patches Array of patch objects. + * @return {Array.} Array of patch objects. + */ + function patch_deepCopy($patches) { + // Making deep copies is hard in JavaScript. + $patchesCopy = array(); + for ($x = 0; $x < count($patches); $x++) { + $patch = $patches[$x]; + $patchCopy = new patch_obj(); + for ($y = 0; $y < count($patch->diffs); $y++) { + $patchCopy->diffs[$y] = $patch->diffs[$y]; // ?? . slice(); + } + $patchCopy->start1 = $patch->start1; + $patchCopy->start2 = $patch->start2; + $patchCopy->length1 = $patch->length1; + $patchCopy->length2 = $patch->length2; + $patchesCopy[$x] = $patchCopy; + } + return $patchesCopy; + } + + /** + * Merge a set of patches onto the text. Return a patched text, as well + * as a list of true/false values indicating which patches were applied. + * @param {Array.} patches Array of patch objects. + * @param {string} text Old text. + * @return {Array.>} Two element Array, containing the + * new text and an array of boolean values. + */ + function patch_apply($patches, $text) { + if ( count($patches) == 0) { + return array($text,array()); + } + + // Deep copy the patches so that no changes are made to originals. + $patches = $this->patch_deepCopy($patches); + + $nullPadding = $this->patch_addPadding($patches); + $text = $nullPadding . $text . $nullPadding; + + $this->patch_splitMax($patches); + // delta keeps track of the offset between the expected and actual location + // of the previous patch. If there are patches expected at positions 10 and + // 20, but the first patch was found at 12, delta is 2 and the second patch + // has an effective expected position of 22. + $delta = 0; + $results = array(); + for ($x = 0; $x < count($patches) ; $x++) { + $expected_loc = $patches[$x]->start2 + $delta; + $text1 = $this->diff_text1($patches[$x]->diffs); + $start_loc = null; + $end_loc = -1; + if (mb_strlen($text1) > Match_MaxBits) { + // patch_splitMax will only provide an oversized pattern in the case of + // a monster delete. + $start_loc = $this->match_main($text, mb_substr($text1, 0, Match_MaxBits ), $expected_loc); + 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); + if ($end_loc == -1 || $start_loc >= $end_loc) { + // Can't find valid trailing context. Drop this patch. + $start_loc = -1; + } + } + } else { + $start_loc = $this->match_main($text, $text1, $expected_loc); + } + if ($start_loc == -1) { + // No match found. :( + $results[$x] = false; + // Subtract the delta for this failed patch from subsequent patches. + $delta -= $patches[$x]->length2 - $patches[$x]->length1; + } else { + // Found a match. :) + $results[$x] = true; + $delta = $start_loc - $expected_loc; + $text2 = null; + if ($end_loc == -1) { + $text2 = mb_substr($text, $start_loc, mb_strlen($text1) ); + } else { + $text2 = mb_substr($text, $start_loc, $end_loc + Match_MaxBits - $start_loc); + } + if ($text1 == $text2) { + // 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) ); + } else { + // Imperfect match. Run a diff to get a framework of equivalent + // indices. + $diffs = $this->diff_main($text1, $text2, false); + if ( mb_strlen($text1) > Match_MaxBits && $this->diff_levenshtein($diffs) / mb_strlen($text1) > $this->Patch_DeleteThreshold) { + // The end points match, but the content is unacceptably bad. + $results[$x] = false; + } else { + $this->diff_cleanupSemanticLossless($diffs); + $index1 = 0; + $index2 = NULL; + for ($y = 0; $y < count($patches[$x]->diffs); $y++) { + $mod = $patches[$x]->diffs[$y]; + if ($mod[0] !== DIFF_EQUAL) { + $index2 = $this->diff_xIndex($diffs, $index1); + } + if ($mod[0] === DIFF_INSERT) { // Insertion + $text = mb_substr($text, 0, $start_loc + $index2) . $mod[1] . mb_substr($text, $start_loc + $index2); + } 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]) )); + } + if ($mod[0] !== DIFF_DELETE) { + $index1 += mb_strlen($mod[1]); + } + } + } + } + } + } + // Strip the padding off. + $text = mb_substr($text, mb_strlen($nullPadding), mb_strlen($text) - 2*mb_strlen($nullPadding) ); + return array($text, $results); + } + + /** + * Add some padding on text start and end so that edges can match something. + * Intended to be called only from within patch_apply. + * @param {Array.} patches Array of patch objects. + * @return {string} The padding string added to each side. + */ + function patch_addPadding(&$patches){ + $paddingLength = $this->Patch_Margin; + $nullPadding = ''; + for ($x = 1; $x <= $paddingLength; $x++) { + $nullPadding .= mb_chr($x); + } + + // Bump all the patches forward. + for ($x = 0; $x < count($patches); $x++) { + $patches[$x]->start1 += $paddingLength; + $patches[$x]->start2 += $paddingLength; + } + + // Add some padding on start of first diff. + $patch = &$patches[0]; + $diffs = &$patch->diffs; + if (count($diffs) == 0 || $diffs[0][0] != DIFF_EQUAL) { + // Add nullPadding equality. + array_unshift($diffs, array(DIFF_EQUAL, $nullPadding)); + $patch->start1 -= $paddingLength; // Should be 0. + $patch->start2 -= $paddingLength; // Should be 0. + $patch->length1 += $paddingLength; + $patch->length2 += $paddingLength; + } elseif ($paddingLength > mb_strlen($diffs[0][1]) ) { + // Grow first equality. + $extraLength = $paddingLength - mb_strlen($diffs[0][1]); + $diffs[0][1] = mb_substr( $nullPadding , mb_strlen($diffs[0][1]) ) . $diffs[0][1]; + $patch->start1 -= $extraLength; + $patch->start2 -= $extraLength; + $patch->length1 += $extraLength; + $patch->length2 += $extraLength; + } + + // Add some padding on end of last diff. + $patch = &$patches[count($patches) - 1]; + $diffs = &$patch->diffs; + if ( count($diffs) == 0 || $diffs[ count($diffs) - 1][0] != DIFF_EQUAL) { + // Add nullPadding equality. + array_push($diffs, array(DIFF_EQUAL, $nullPadding) ); + $patch->length1 += $paddingLength; + $patch->length2 += $paddingLength; + } elseif ($paddingLength > mb_strlen( $diffs[count($diffs)-1][1] ) ) { + // Grow last equality. + $extraLength = $paddingLength - mb_strlen( $diffs[count($diffs)-1][1] ); + $diffs[ count($diffs)-1][1] .= mb_substr($nullPadding,0,$extraLength); + $patch->length1 += $extraLength; + $patch->length2 += $extraLength; + } + + return $nullPadding; + } + + /** + * Look through the patches and break up any which are longer than the maximum + * limit of the match algorithm. + * @param {Array.} patches Array of patch objects. + */ + function patch_splitMax(&$patches) { + for ($x = 0; $x < count($patches); $x++) { + if ( $patches[$x]->length1 > Match_MaxBits) { + $bigpatch = $patches[$x]; + // Remove the big old patch. + array_splice($patches,$x--,1); + $patch_size = Match_MaxBits; + $start1 = $bigpatch->start1; + $start2 = $bigpatch->start2; + $precontext = ''; + while ( count($bigpatch->diffs) !== 0) { + // Create one of several smaller patches. + $patch = new patch_obj(); + $empty = true; + $patch->start1 = $start1 - mb_strlen($precontext); + $patch->start2 = $start2 - mb_strlen($precontext); + if ($precontext !== '') { + $patch->length1 = $patch->length2 = mb_strlen($precontext); + array_push($patch->diffs, array(DIFF_EQUAL, $precontext) ); + } + while ( count($bigpatch->diffs) !== 0 && $patch->length1 < $patch_size - $this->Patch_Margin) { + $diff_type = $bigpatch->diffs[0][0]; + $diff_text = $bigpatch->diffs[0][1]; + if ($diff_type === DIFF_INSERT) { + // Insertions are harmless. + $patch->length2 += mb_strlen($diff_text); + $start2 += mb_strlen($diff_text); + array_push($patch->diffs, array_shift($bigpatch->diffs) ); + $empty = false; + } else + if ($diff_type === DIFF_DELETE && count($patch->diffs) == 1 && $patch->diffs[0][0] == DIFF_EQUAL && (mb_strlen($diff_text) > 2 * $patch_size) ) { + // This is a large deletion. Let it pass in one chunk. + $patch->length1 += mb_strlen($diff_text); + $start1 += mb_strlen($diff_text); + $empty = false; + array_push( $patch->diffs, array($diff_type, $diff_text) ); + array_shift($bigpatch->diffs); + } else { + // 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); + $patch->length1 += mb_strlen($diff_text); + $start1 += mb_strlen($diff_text); + if ($diff_type === DIFF_EQUAL) { + $patch->length2 += mb_strlen($diff_text); + $start2 += mb_strlen($diff_text); + } else { + $empty = false; + } + array_push($patch->diffs, array($diff_type, $diff_text) ); + if ($diff_text == $bigpatch->diffs[0][1]) { + array_shift($bigpatch->diffs); + } else { + $bigpatch->diffs[0][1] = mb_substr( $bigpatch->diffs[0][1],mb_strlen($diff_text) ); + } + } + } + // Compute the head context for the next patch. + $precontext = $this->diff_text2($patch->diffs); + $precontext = mb_substr($precontext, mb_strlen($precontext)-$this->Patch_Margin); + // Append the end context for this patch. + $postcontext = mb_substr( $this->diff_text1($bigpatch->diffs), 0, $this->Patch_Margin ); + if ($postcontext !== '') { + $patch->length1 += mb_strlen($postcontext); + $patch->length2 += mb_strlen($postcontext); + if ( count($patch->diffs) !== 0 && $patch->diffs[ count($patch->diffs) - 1][0] === DIFF_EQUAL) { + $patch->diffs[ count($patch->diffs) - 1][1] .= $postcontext; + } else { + array_push($patch->diffs, array(DIFF_EQUAL, $postcontext)); + } + } + if (!$empty) { + array_splice($patches, ++$x, 0, array($patch)); + } + } + } + } + } + + /** + * Take a list of patches and return a textual representation. + * @param {Array.} patches Array of patch objects. + * @return {string} Text representation of patches. + */ + function patch_toText($patches) { + $text = array(); + for ($x = 0; $x < count($patches) ; $x++) { + $text[$x] = $patches[$x]; + } + return implode('',$text); + } + + /** + * Parse a textual representation of patches and return a list of patch objects. + * @param {string} textline Text representation of patches. + * @return {Array.} Array of patch objects. + * @throws {Error} If invalid input. + */ + function patch_fromText($textline) { + $patches = array(); + if ($textline === '') { + return $patches; + } + $text = explode("\n",$textline); + foreach($text as $i=>$t){ if($t===''){ unset($text[$i]); } } + $textPointer = 0; + while ($textPointer < count($text) ) { + $m = null; + preg_match('/^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/',$text[$textPointer],$m); + if (!$m) { + echo_Exception('Invalid patch string: ' . $text[$textPointer]); + } + $patch = new patch_obj(); + array_push($patches, $patch); + @$patch->start1 = (int)$m[1]; + if (@$m[2] === '') { + $patch->start1--; + $patch->length1 = 1; + } elseif ( @$m[2] == '0') { + $patch->length1 = 0; + } else { + $patch->start1--; + @$patch->length1 = (int)$m[2]; + } + + @$patch->start2 = (int)$m[3]; + if (@$m[4] === '') { + $patch->start2--; + $patch->length2 = 1; + } elseif ( @$m[4] == '0') { + $patch->length2 = 0; + } else { + $patch->start2--; + @$patch->length2 = (int)$m[4]; + } + $textPointer++; + + while ($textPointer < count($text) ) { + $sign = $text[$textPointer][0]; + try { + $line = decodeURI( mb_substr($text[$textPointer],1) ); + } catch (Exception $ex) { + // Malformed URI sequence. + throw new Exception('Illegal escape in patch_fromText: ' . $line); + } + if ($sign == '-') { + // Deletion. + array_push( $patch->diffs, array(DIFF_DELETE, $line) ); + } elseif ($sign == '+') { + // Insertion. + array_push($patch->diffs, array(DIFF_INSERT, $line) ); + } elseif ($sign == ' ') { + // Minor equality. + array_push($patch->diffs, array(DIFF_EQUAL, $line) ); + } elseif ($sign == '@') { + // Start of next patch. + break; + } elseif ($sign === '') { + // Blank line? Whatever. + } else { + // WTF? + echo_Exception('Invalid patch mode "' . $sign . '" in: ' . $line); + } + $textPointer++; + } + } + return $patches; + } +} + +/** + * Class representing one patch operation. + * @constructor + */ +class patch_obj { + /** @type {Array.>} */ + public $diffs = array(); + /** @type {number?} */ + public $start1 = null; + /** @type {number?} */ + public $start2 = null; + /** @type {number} */ + public $length1 = 0; + /** @type {number} */ + public $length2 = 0; + + /** + * Emmulate GNU diff's format. + * Header: @@ -382,8 +481,9 @@ + * Indicies are printed as 1-based, not 0-based. + * @return {string} The GNU diff string. + */ + function toString() { + if ($this->length1 === 0) { + $coords1 = $this->start1 . ',0'; + } elseif ($this->length1 == 1) { + $coords1 = $this->start1 + 1; + } else { + $coords1 = ($this->start1 + 1) . ',' . $this->length1; + } + if ($this->length2 === 0) { + $coords2 = $this->start2 . ',0'; + } elseif ($this->length2 == 1) { + $coords2 = $this->start2 + 1; + } else { + $coords2 = ($this->start2 + 1) . ',' . $this->length2; + } + $text = array ( '@@ -' . $coords1 . ' +' . $coords2 . " @@\n" ); + + // Escape the body of the patch with %xx notation. + for ($x = 0; $x < count($this->diffs); $x++) { + switch ($this->diffs[$x][0]) { + case DIFF_INSERT : + $op = '+'; + break; + case DIFF_DELETE : + $op = '-'; + break; + case DIFF_EQUAL : + $op = ' '; + break; + } + $text[$x +1] = $op . encodeURI($this->diffs[$x][1]) . "\n"; + } + return str_replace('%20', ' ', implode('',$text)); + } + function __toString(){ + return $this->toString(); + } +} + +define('DIFF_DELETE', -1); +define('DIFF_INSERT', 1); +define('DIFF_EQUAL', 0); + +define('Match_MaxBits', PHP_INT_SIZE * 8); + + +function charCodeAt($str, $pos) { + return mb_ord(mb_substr($str, $pos, 1)); +} +function mb_ord($v) { + $k = mb_convert_encoding($v, 'UCS-2LE', 'UTF-8'); + $k1 = ord(substr($k, 0, 1)); + $k2 = ord(substr($k, 1, 1)); + return $k2 * 256 + $k1; +} +function mb_chr($num){ + return mb_convert_encoding('&#'.intval($num).';', 'UTF-8', 'HTML-ENTITIES'); +} + +/** + * as in javascript encodeURI() following the MDN description + * + * @link https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/encodeURI + * @param $url + * @return string + */ +function encodeURI($url) { + return strtr(rawurlencode($url), array ( + '%3B' => ';', '%2C' => ',', '%2F' => '/', '%3F' => '?', '%3A' => ':', '%40' => '@', '%26' => '&', '%3D' => '=', + '%2B' => '+', '%24' => '$', '%21' => '!', '%2A' => '*', '%27' => '\'', '%28' => '(', '%29' => ')', '%23' => '#', + )); +} + +function decodeURI($encoded) { + static $dontDecode; + if (!$dontDecode) { + $table = array ( + '%3B' => ';', '%2C' => ',', '%2F' => '/', '%3F' => '?', '%3A' => ':', '%40' => '@', '%26' => '&', '%3D' => '=', + '%2B' => '+', '%24' => '$', '%21' => '!', '%2A' => '*', '%27' => '\'', '%28' => '(', '%29' => ')', '%23' => '#', + ); + $dontDecode = array(); + foreach ($table as $k => $v) { + $dontDecode[$k] = encodeURI($k); + } + } + return rawurldecode(strtr($encoded, $dontDecode)); +} + +function echo_Exception($str){ + global $lastException; + $lastException = $str; + echo $str; +} +//mb_internal_encoding("UTF-8"); + +?> \ No newline at end of file Index: resources/sql/patches/20131206.phragment.sql =================================================================== --- /dev/null +++ resources/sql/patches/20131206.phragment.sql @@ -0,0 +1,24 @@ +CREATE TABLE {$NAMESPACE}_phragment.phragment_fragment ( + id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY, + phid VARCHAR(64) NOT NULL COLLATE utf8_bin, + path VARCHAR(2048) NOT NULL COLLATE utf8_bin, + depth INT UNSIGNED NOT NULL, + ownerPHID VARCHAR(64) NOT NULL COLLATE utf8_bin, + latestVersionPHID VARCHAR(64) NOT NULL COLLATE utf8_bin, + viewPolicy VARCHAR(64) NOT NULL COLLATE utf8_bin, + editPolicy VARCHAR(64) NOT NULL COLLATE utf8_bin, + dateCreated INT UNSIGNED NOT NULL, + dateModified INT UNSIGNED NOT NULL, + UNIQUE KEY `key_phid` (phid) +) ENGINE=InnoDB, COLLATE utf8_general_ci; + +CREATE TABLE {$NAMESPACE}_phragment.phragment_fragmentversion ( + id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY, + phid VARCHAR(64) NOT NULL COLLATE utf8_bin, + sequence INT UNSIGNED NOT NULL, + fragmentPHID VARCHAR(64) NOT NULL COLLATE utf8_bin, + filePHID VARCHAR(64) NULL COLLATE utf8_bin, + dateCreated INT UNSIGNED NOT NULL, + dateModified INT UNSIGNED NOT NULL, + UNIQUE KEY `key_version` (sequence, fragmentPHID, filePHID) +) ENGINE=InnoDB, COLLATE utf8_general_ci; Index: src/__phutil_library_map__.php =================================================================== --- src/__phutil_library_map__.php +++ src/__phutil_library_map__.php @@ -1053,6 +1053,7 @@ 'PhabricatorApplicationPhlux' => 'applications/phlux/application/PhabricatorApplicationPhlux.php', 'PhabricatorApplicationPholio' => 'applications/pholio/application/PhabricatorApplicationPholio.php', 'PhabricatorApplicationPhortune' => 'applications/phortune/application/PhabricatorApplicationPhortune.php', + 'PhabricatorApplicationPhragment' => 'applications/phragment/application/PhabricatorApplicationPhragment.php', 'PhabricatorApplicationPhrequent' => 'applications/phrequent/application/PhabricatorApplicationPhrequent.php', 'PhabricatorApplicationPhriction' => 'applications/phriction/application/PhabricatorApplicationPhriction.php', 'PhabricatorApplicationPolicy' => 'applications/policy/application/PhabricatorApplicationPolicy.php', @@ -2173,6 +2174,17 @@ 'PhortuneTestExtraPaymentProvider' => 'applications/phortune/provider/__tests__/PhortuneTestExtraPaymentProvider.php', 'PhortuneTestPaymentProvider' => 'applications/phortune/provider/PhortuneTestPaymentProvider.php', 'PhortuneWePayPaymentProvider' => 'applications/phortune/provider/PhortuneWePayPaymentProvider.php', + 'PhragmentBrowseController' => 'applications/phragment/controller/PhragmentBrowseController.php', + 'PhragmentController' => 'applications/phragment/controller/PhragmentController.php', + 'PhragmentCreateController' => 'applications/phragment/controller/PhragmentCreateController.php', + 'PhragmentDAO' => 'applications/phragment/storage/PhragmentDAO.php', + 'PhragmentFragment' => 'applications/phragment/storage/PhragmentFragment.php', + 'PhragmentFragmentQuery' => 'applications/phragment/query/PhragmentFragmentQuery.php', + 'PhragmentFragmentVersion' => 'applications/phragment/storage/PhragmentFragmentVersion.php', + 'PhragmentFragmentVersionQuery' => 'applications/phragment/query/PhragmentFragmentVersionQuery.php', + 'PhragmentPHIDTypeFragment' => 'applications/phragment/phid/PhragmentPHIDTypeFragment.php', + 'PhragmentPHIDTypeFragmentVersion' => 'applications/phragment/phid/PhragmentPHIDTypeFragmentVersion.php', + 'PhragmentPatchUtil' => 'applications/phragment/util/PhragmentPatchUtil.php', 'PhrequentController' => 'applications/phrequent/controller/PhrequentController.php', 'PhrequentDAO' => 'applications/phrequent/storage/PhrequentDAO.php', 'PhrequentListController' => 'applications/phrequent/controller/PhrequentListController.php', @@ -3488,6 +3500,7 @@ 'PhabricatorApplicationPhlux' => 'PhabricatorApplication', 'PhabricatorApplicationPholio' => 'PhabricatorApplication', 'PhabricatorApplicationPhortune' => 'PhabricatorApplication', + 'PhabricatorApplicationPhragment' => 'PhabricatorApplication', 'PhabricatorApplicationPhrequent' => 'PhabricatorApplication', 'PhabricatorApplicationPhriction' => 'PhabricatorApplication', 'PhabricatorApplicationPolicy' => 'PhabricatorApplication', @@ -4749,6 +4762,25 @@ 'PhortuneTestExtraPaymentProvider' => 'PhortunePaymentProvider', 'PhortuneTestPaymentProvider' => 'PhortunePaymentProvider', 'PhortuneWePayPaymentProvider' => 'PhortunePaymentProvider', + 'PhragmentBrowseController' => 'PhragmentController', + 'PhragmentController' => 'PhabricatorController', + 'PhragmentCreateController' => 'PhragmentController', + 'PhragmentDAO' => 'PhabricatorLiskDAO', + 'PhragmentFragment' => + array( + 0 => 'PhragmentDAO', + 1 => 'PhabricatorPolicyInterface', + ), + 'PhragmentFragmentQuery' => 'PhabricatorCursorPagedPolicyAwareQuery', + 'PhragmentFragmentVersion' => + array( + 0 => 'PhragmentDAO', + 1 => 'PhabricatorPolicyInterface', + ), + 'PhragmentFragmentVersionQuery' => 'PhabricatorCursorPagedPolicyAwareQuery', + 'PhragmentPHIDTypeFragment' => 'PhabricatorPHIDType', + 'PhragmentPHIDTypeFragmentVersion' => 'PhabricatorPHIDType', + 'PhragmentPatchUtil' => 'Phobject', 'PhrequentController' => 'PhabricatorController', 'PhrequentDAO' => 'PhabricatorLiskDAO', 'PhrequentListController' => Index: src/applications/phragment/application/PhabricatorApplicationPhragment.php =================================================================== --- /dev/null +++ src/applications/phragment/application/PhabricatorApplicationPhragment.php @@ -0,0 +1,44 @@ + array( + '' => 'PhragmentBrowseController', + 'browse/(?P.*)' => 'PhragmentBrowseController', + 'create/(?P.*)' => 'PhragmentCreateController', + ), + ); + } + +} + Index: src/applications/phragment/controller/PhragmentBrowseController.php =================================================================== --- /dev/null +++ src/applications/phragment/controller/PhragmentBrowseController.php @@ -0,0 +1,105 @@ +dblob = idx($data, "dblob", ""); + } + + public function processRequest() { + $request = $this->getRequest(); + $viewer = $request->getUser(); + + $parents = $this->loadParentFragments($this->dblob); + if ($parents === null) { + return new Aphront404Response(); + } + $current = idx($parents, count($parents) - 1, null); + + $path = ''; + if ($current !== null) { + $path = $current->getPath(); + } + + $crumbs = $this->buildApplicationCrumbsWithPath($parents); + $crumbs->addAction( + id(new PHUIListItemView()) + ->setName(pht('Create Fragment')) + ->setHref($this->getApplicationURI('/create/'.$path)) + ->setIcon('create')); + + $current_box = $this->createCurrentFragmentView($current); + + $list = id(new PHUIObjectItemListView()) + ->setUser($viewer); + + $fragments = null; + if ($current === null) { + // Find all root fragments. + $fragments = id(new PhragmentFragmentQuery()) + ->setViewer($this->getRequest()->getUser()) + ->needLatestVersion(true) + ->withDepths(array(1)) + ->execute(); + } else { + // Find all child fragments. + $fragments = id(new PhragmentFragmentQuery()) + ->setViewer($this->getRequest()->getUser()) + ->needLatestVersion(true) + ->withLeadingPath($current->getPath().'/') + ->withDepths(array($current->getDepth() + 1)) + ->execute(); + } + + foreach ($fragments as $fragment) { + $item = id(new PHUIObjectItemView()); + $item->setHeader($fragment->getName()); + $item->setHref($this->getApplicationURI('/browse/'.$fragment->getPath())); + $item->addAttribute('Last Updated '.phabricator_datetime( + $fragment->getLatestVersion()->getDateCreated(), + $viewer)); + $item->addAttribute( + 'Latest Version '.$fragment->getLatestVersion()->getSequence()); + $list->addItem($item); + } + + return $this->buildApplicationPage( + array( + $crumbs, + $current_box, + $list), + array( + 'title' => pht('Browse Phragments'), + 'device' => true)); + } + + private function createCurrentFragmentView($fragment) { + if ($fragment === null) { + return null; + } + + $viewer = $this->getRequest()->getUser(); + + $header = id(new PHUIHeaderView()) + ->setHeader($fragment->getName()) + ->setPolicyObject($fragment) + ->setUser($viewer); + $properties = new PHUIPropertyListView(); + + $phids = array(); + $phids[] = $fragment->getLatestVersionPHID(); + + $this->loadHandles($phids); + + $properties->addProperty( + pht('Latest Version'), + $this->renderHandlesForPHIDs(array($fragment->getLatestVersionPHID()))); + + return id(new PHUIObjectBoxView()) + ->setHeader($header) + ->addPropertyList($properties); + } + +} Index: src/applications/phragment/controller/PhragmentController.php =================================================================== --- /dev/null +++ src/applications/phragment/controller/PhragmentController.php @@ -0,0 +1,56 @@ +setViewer($this->getRequest()->getUser()) + ->withPaths($combinations) + ->execute(); + foreach ($combinations as $combination) { + $found = false; + foreach ($results as $fragment) { + if ($fragment->getPath() === $combination) { + $fragments[] = $fragment; + $found = true; + break; + } + } + if (!$found) { + return null; + } + } + return $fragments; + } + + protected function buildApplicationCrumbsWithPath(array $fragments) { + $crumbs = $this->buildApplicationCrumbs(); + $crumbs->addCrumb( + id(new PhabricatorCrumbView()) + ->setName('/') + ->setHref('/phragment/')); + foreach ($fragments as $parent) { + $crumbs->addCrumb( + id(new PhabricatorCrumbView()) + ->setName($parent->getName()) + ->setHref('/phragment/browse/'.$parent->getPath())); + } + return $crumbs; + } + +} Index: src/applications/phragment/controller/PhragmentCreateController.php =================================================================== --- /dev/null +++ src/applications/phragment/controller/PhragmentCreateController.php @@ -0,0 +1,142 @@ +dblob = idx($data, "dblob", ""); + } + + public function processRequest() { + $request = $this->getRequest(); + $viewer = $request->getUser(); + + $parent = null; + $parents = $this->loadParentFragments($this->dblob); + if ($parents === null) { + return new Aphront404Response(); + } + if (count($parents) !== 0) { + $parent = idx($parents, count($parents) - 1, null); + } + + $parent_path = ''; + if ($parent !== null) { + $parent_path = $parent->getPath(); + } + $parent_path = trim($parent_path, '/'); + + $fragment = id(new PhragmentFragment()); + + $error_view = null; + + if ($request->isFormPost()) { + $errors = array(); + + $v_name = $request->getStr('name'); + $v_fileid = $request->getInt('fileID'); + $v_viewpolicy = $request->getStr('viewPolicy'); + $v_editpolicy = $request->getStr('editPolicy'); + + if (strpos($v_name, '/') !== false) { + $errors[] = pht('The fragment name can not contain \'/\'.'); + } + + $file = id(new PhabricatorFile())->load($v_fileid); + if ($file === null) { + $errors[] = pht('The specified file doesn\'t exist.'); + } + + if (!count($errors)) { + $depth = 1; + if ($parent !== null) { + $depth = $parent->getDepth() + 1; + } + + $version = id(new PhragmentFragmentVersion()); + $version->setSequence(0); + $version->setFragmentPHID(''); // Can't set this yet... + $version->setFilePHID($file->getPHID()); + $version->save(); + + $fragment->setPath(trim($parent_path.'/'.$v_name, '/')); + $fragment->setDepth($depth); + $fragment->setOwnerPHID($viewer->getPHID()); + $fragment->setLatestVersionPHID($version->getPHID()); + $fragment->setViewPolicy($v_viewpolicy); + $fragment->setEditPolicy($v_editpolicy); + $fragment->save(); + + $version->setFragmentPHID($fragment->getPHID()); + $version->save(); + + return id(new AphrontRedirectResponse()) + ->setURI('/phragment/browse/'.trim($parent_path.'/'.$v_name, '/')); + } else { + $error_view = id(new AphrontErrorView()) + ->setErrors($errors) + ->setTitle(pht('Errors while creating fragment')); + } + } + + $policies = id(new PhabricatorPolicyQuery()) + ->setViewer($viewer) + ->setObject($fragment) + ->execute(); + + $form = id(new AphrontFormView()) + ->setUser($viewer) + ->appendChild( + id(new AphrontFormTextControl()) + ->setLabel(pht('Parent Path')) + ->setDisabled(true) + ->setValue('/'.trim($parent_path.'/', '/'))) + ->appendChild( + id(new AphrontFormTextControl()) + ->setLabel(pht('Name')) + ->setName('name')) + ->appendChild( + id(new AphrontFormTextControl()) + ->setLabel(pht('File ID')) + ->setName('fileID')) + ->appendChild( + id(new AphrontFormPolicyControl()) + ->setUser($viewer) + ->setName('viewPolicy') + ->setPolicyObject($fragment) + ->setPolicies($policies) + ->setCapability(PhabricatorPolicyCapability::CAN_VIEW)) + ->appendChild( + id(new AphrontFormPolicyControl()) + ->setUser($viewer) + ->setName('editPolicy') + ->setPolicyObject($fragment) + ->setPolicies($policies) + ->setCapability(PhabricatorPolicyCapability::CAN_EDIT)) + ->appendChild( + id(new AphrontFormSubmitControl()) + ->setValue(pht('Create Fragment')) + ->addCancelButton( + $this->getApplicationURI('browse/'.$parent_path))); + + $crumbs = $this->buildApplicationCrumbsWithPath($parents); + $crumbs->addCrumb( + id(new PhabricatorCrumbView()) + ->setName(pht('Create Fragment'))); + + $box = id(new PHUIObjectBoxView()) + ->setHeaderText('Create Fragment') + ->setValidationException(null) + ->setForm($form); + + return $this->buildApplicationPage( + array( + $crumbs, + $box), + array( + 'title' => pht('Create Phragment'), + 'device' => true)); + } + +} Index: src/applications/phragment/phid/PhragmentPHIDTypeFragment.php =================================================================== --- /dev/null +++ src/applications/phragment/phid/PhragmentPHIDTypeFragment.php @@ -0,0 +1,46 @@ +withPHIDs($phids); + } + + public function loadHandles( + PhabricatorHandleQuery $query, + array $handles, + array $objects) { + + $viewer = $query->getViewer(); + foreach ($handles as $phid => $handle) { + $fragment = $objects[$phid]; + + $handle->setName($fragment->getID()); + $handle->setURI($fragment->getURI()); + } + } + + public function canLoadNamedObject($name) { + return false; + } + +} Index: src/applications/phragment/phid/PhragmentPHIDTypeFragmentVersion.php =================================================================== --- /dev/null +++ src/applications/phragment/phid/PhragmentPHIDTypeFragmentVersion.php @@ -0,0 +1,46 @@ +withPHIDs($phids); + } + + public function loadHandles( + PhabricatorHandleQuery $query, + array $handles, + array $objects) { + + $viewer = $query->getViewer(); + foreach ($handles as $phid => $handle) { + $version = $objects[$phid]; + + $handle->setName($version->getSequence()); + $handle->setURI($version->getURI()); + } + } + + public function canLoadNamedObject($name) { + return false; + } + +} Index: src/applications/phragment/query/PhragmentFragmentQuery.php =================================================================== --- /dev/null +++ src/applications/phragment/query/PhragmentFragmentQuery.php @@ -0,0 +1,131 @@ +ids = $ids; + return $this; + } + + public function withPHIDs(array $phids) { + $this->phids = $phids; + return $this; + } + + public function withPaths(array $paths) { + $this->paths = $paths; + return $this; + } + + public function withLeadingPath($path) { + $this->leadingPath = $path; + return $this; + } + + public function withDepths($depths) { + $this->depths = $depths; + return $this; + } + + public function needLatestVersion($need_latest_version) { + $this->needsLatestVersion = $need_latest_version; + return $this; + } + + public function loadPage() { + $table = new PhragmentFragment(); + $conn_r = $table->establishConnection('r'); + + $data = queryfx_all( + $conn_r, + 'SELECT * FROM %T %Q %Q %Q', + $table->getTableName(), + $this->buildWhereClause($conn_r), + $this->buildOrderClause($conn_r), + $this->buildLimitClause($conn_r)); + + return $table->loadAllFromArray($data); + } + + protected function buildWhereClause($conn_r) { + $where = array(); + + if ($this->ids) { + $where[] = qsprintf( + $conn_r, + 'id IN (%Ld)', + $this->ids); + } + + if ($this->phids) { + $where[] = qsprintf( + $conn_r, + 'phid IN (%Ls)', + $this->phids); + } + + if ($this->paths) { + $where[] = qsprintf( + $conn_r, + 'path IN (%Ls)', + $this->paths); + } + + if ($this->leadingPath) { + $where[] = qsprintf( + $conn_r, + 'path LIKE %>', + $this->leadingPath); + } + + if ($this->depths) { + $where[] = qsprintf( + $conn_r, + 'depth IN (%Ld)', + $this->depths); + } + + $where[] = $this->buildPagingClause($conn_r); + + return $this->formatWhereClause($where); + } + + protected function didFilterPage(array $page) { + if ($this->needsLatestVersion) { + $versions = array(); + + $version_phids = array_filter(mpull($page, 'getLatestVersionPHID')); + if ($version_phids) { + $versions = id(new PhabricatorObjectQuery()) + ->setViewer($this->getViewer()) + ->withPHIDs($version_phids) + ->setParentQuery($this) + ->execute(); + $versions = mpull($versions, null, 'getPHID'); + } + + foreach ($page as $key => $fragment) { + $version_phid = $fragment->getLatestVersionPHID(); + if (empty($versions[$version_phid])) { + unset($page[$key]); + continue; + } + $fragment->attachLatestVersion($versions[$version_phid]); + } + } + + return $page; + } + + public function getQueryApplicationClass() { + return 'PhabricatorApplicationPhragment'; + } +} Index: src/applications/phragment/query/PhragmentFragmentVersionQuery.php =================================================================== --- /dev/null +++ src/applications/phragment/query/PhragmentFragmentVersionQuery.php @@ -0,0 +1,97 @@ +ids = $ids; + return $this; + } + + public function withPHIDs(array $phids) { + $this->phids = $phids; + return $this; + } + + public function withFragmentPHIDs(array $fragment_phids) { + $this->fragmentPHIDs = $fragment_phids; + return $this; + } + + public function loadPage() { + $table = new PhragmentFragmentVersion(); + $conn_r = $table->establishConnection('r'); + + $data = queryfx_all( + $conn_r, + 'SELECT * FROM %T %Q %Q %Q', + $table->getTableName(), + $this->buildWhereClause($conn_r), + $this->buildOrderClause($conn_r), + $this->buildLimitClause($conn_r)); + + return $table->loadAllFromArray($data); + } + + protected function buildWhereClause($conn_r) { + $where = array(); + + if ($this->ids) { + $where[] = qsprintf( + $conn_r, + 'id IN (%Ld)', + $this->ids); + } + + if ($this->phids) { + $where[] = qsprintf( + $conn_r, + 'phid IN (%Ls)', + $this->phids); + } + + if ($this->fragmentPHIDs) { + $where[] = qsprintf( + $conn_r, + 'fragmentPHID IN (%Ls)', + $this->fragmentPHIDs); + } + + $where[] = $this->buildPagingClause($conn_r); + + return $this->formatWhereClause($where); + } + + protected function willFilterPage(array $page) { + $fragments = array(); + + $fragment_phids = array_filter(mpull($page, 'getFragmentPHID')); + if ($fragment_phids) { + $fragments = id(new PhabricatorObjectQuery()) + ->setViewer($this->getViewer()) + ->withPHIDs($fragment_phids) + ->setParentQuery($this) + ->execute(); + $fragments = mpull($fragments, null, 'getPHID'); + } + + foreach ($page as $key => $version) { + $fragment_phid = $version->getFragmentPHID(); + if (empty($fragments[$fragment_phid])) { + unset($page[$key]); + continue; + } + $version->attachFragment($fragments[$fragment_phid]); + } + + return $page; + } + + public function getQueryApplicationClass() { + return 'PhabricatorApplicationPhragment'; + } +} Index: src/applications/phragment/storage/PhragmentDAO.php =================================================================== --- /dev/null +++ src/applications/phragment/storage/PhragmentDAO.php @@ -0,0 +1,9 @@ + true, + ) + parent::getConfiguration(); + } + + public function generatePHID() { + return PhabricatorPHID::generateNewPHID( + PhragmentPHIDTypeFragment::TYPECONST); + } + + public function getURI() { + return '/phragment/fragment/'.$this->getID().'/'; + } + + public function getName() { + $components = explode('/', $this->path); + return $components[count($components) - 1]; + } + + public function getFile() { + return $this->assertAttached($this->file); + } + + public function attachFile(PhabricatorFile $file) { + return $this->file = $file; + } + + public function getLatestVersion() { + return $this->assertAttached($this->latestVersion); + } + + public function attachLatestVersion(PhragmentFragmentVersion $version) { + return $this->latestVersion = $version; + } + + public function getCapabilities() { + return array( + PhabricatorPolicyCapability::CAN_VIEW, + PhabricatorPolicyCapability::CAN_EDIT, + ); + } + + public function getPolicy($capability) { + switch ($capability) { + case PhabricatorPolicyCapability::CAN_VIEW: + return $this->getViewPolicy(); + case PhabricatorPolicyCapability::CAN_EDIT: + return $this->getEditPolicy(); + } + } + + public function hasAutomaticCapability($capability, PhabricatorUser $viewer) { + return $viewer->getPHID() == $this->ownerPHID; + } + + public function describeAutomaticCapability($capability) { + switch ($capability) { + case PhabricatorPolicyCapability::CAN_VIEW: + return pht('Owners of a fragment can always view it.'); + case PhabricatorPolicyCapability::CAN_EDIT: + return pht('Owners of a fragment can always edit it.'); + } + return null; + } + +} Index: src/applications/phragment/storage/PhragmentFragmentVersion.php =================================================================== --- /dev/null +++ src/applications/phragment/storage/PhragmentFragmentVersion.php @@ -0,0 +1,62 @@ + true, + ) + parent::getConfiguration(); + } + + public function generatePHID() { + return PhabricatorPHID::generateNewPHID( + PhragmentPHIDTypeFragmentVersion::TYPECONST); + } + + public function getURI() { + return '/phragment/patch/'.$this->getID().'/'; + } + + public function getFragment() { + return $this->assertAttached($this->fragment); + } + + public function attachFragment(PhragmentFragment $fragment) { + return $this->fragment = $fragment; + } + + public function getFile() { + return $this->assertAttached($this->file); + } + + public function attachFile(PhabricatorFile $file) { + return $this->file = $file; + } + + public function getCapabilities() { + return array( + PhabricatorPolicyCapability::CAN_VIEW + ); + } + + public function getPolicy($capability) { + return $this->getFragment()->getPolicy($capability); + } + + public function hasAutomaticCapability($capability, PhabricatorUser $viewer) { + return $this->getFragment()->hasAutomaticCapability($capability, $viewer); + } + + public function describeAutomaticCapability($capability) { + return $this->getFragment()->describeAutomaticCapability($capability); + } + +} Index: src/applications/phragment/util/PhragmentPatchUtil.php =================================================================== --- /dev/null +++ src/applications/phragment/util/PhragmentPatchUtil.php @@ -0,0 +1,53 @@ +getContentHash(); + } + if ($new !== null) { + $new_hash = $new->getContentHash(); + } + + $old_content = ""; + $new_content = ""; + + if ($old_hash === $new_hash) { + return null; + } + + if ($old_hash !== self::EMPTY_HASH) { + $old_content = $old->loadFileData(); + } else { + $old_content = ""; + } + + if ($new_hash !== self::EMPTY_HASH) { + $new_content = $new->loadFileData(); + } else { + $new_content = ""; + } + + $dmp = new diff_match_patch(); + $dmp_patches = $dmp->patch_make($old_content, $new_content); + return $dmp->patch_toText($dmp_patches); + } + +} Index: src/infrastructure/storage/patch/PhabricatorBuiltinPatchList.php =================================================================== --- src/infrastructure/storage/patch/PhabricatorBuiltinPatchList.php +++ src/infrastructure/storage/patch/PhabricatorBuiltinPatchList.php @@ -216,6 +216,10 @@ 'type' => 'db', 'name' => 'passphrase', ), + 'db.phragment' => array( + 'type' => 'db', + 'name' => 'phragment', + ), '0000.legacy.sql' => array( 'type' => 'sql', 'name' => $this->getPatchPath('0000.legacy.sql'), @@ -1812,6 +1816,10 @@ 'type' => 'php', 'name' => $this->getPatchPath('20131205.buildstepordermig.php'), ), + '20131206.phragment.sql' => array( + 'type' => 'sql', + 'name' => $this->getPatchPath('20131206.phragment.sql'), + ), ); } }