Something went wrong. Try again.
@recaptime-dev's working patches + fork for Phorge, a community fork of Phabricator. (Upstream dev and stable branches are at upstream/main and upstream/stable respectively.) hq.recaptime.dev/wiki/Phorge
phorge phabricator
Something went wrong. Try again.
7.5 kB · 294 lines
PHP
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295<?php
final class PhutilProseDifferenceEngine extends Phobject {
public function getDiff($u, $v) { return $this->buildDiff($u, $v, 0); }
private function buildDiff($u, $v, $level) { $u_parts = $this->splitCorpus($u, $level); $v_parts = $this->splitCorpus($v, $level);
if ($level === 0) { $diff = $this->newHashDiff($u_parts, $v_parts); $too_large = false; } else { list($diff, $too_large) = $this->newEditDistanceMatrixDiff( $u_parts, $v_parts, $level); }
$diff->reorderParts();
// If we just built a character-level diff, we're all done and do not // need to go any deeper. if ($level == 3) { return $diff; }
$blocks = array(); $block = null; foreach ($diff->getParts() as $part) { $type = $part['type']; $text = $part['text']; switch ($type) { case '=': if ($block) { $blocks[] = $block; $block = null; } $blocks[] = array( 'type' => $type, 'text' => $text, ); break; case '-': if (!$block) { $block = array( 'type' => '!', 'old' => '', 'new' => '', ); } $block['old'] .= $text; break; case '+': if (!$block) { $block = array( 'type' => '!', 'old' => '', 'new' => '', ); } $block['new'] .= $text; break; } }
if ($block) { $blocks[] = $block; }
$result = new PhutilProseDiff(); foreach ($blocks as $block) { $type = $block['type']; if ($type == '=') { $result->addPart('=', $block['text']); } else { $old = $block['old']; $new = $block['new']; if (!strlen($old) && !strlen($new)) { // Nothing to do. } else if (!strlen($old)) { $result->addPart('+', $new); } else if (!strlen($new)) { $result->addPart('-', $old); } else { if ($too_large) { // If this text was too big to diff, don't try to subdivide it. $result->addPart('-', $old); $result->addPart('+', $new); } else { $subdiff = $this->buildDiff( $old, $new, $level + 1);
foreach ($subdiff->getParts() as $part) { $result->addPart($part['type'], $part['text']); } } } } }
$result->reorderParts();
return $result; }
private function splitCorpus($corpus, $level) { switch ($level) { case 0: // Level 0: Split into paragraphs. $expr = '/([\n]+)/'; break; case 1: // Level 1: Split into sentences. $expr = '/([\n,!;?\.]+)/'; break; case 2: // Level 2: Split into words. $expr = '/(\s+)/'; break; case 3: // Level 3: Split into characters. return phutil_utf8v_combined($corpus); }
$pieces = preg_split($expr, $corpus, -1, PREG_SPLIT_DELIM_CAPTURE); return $this->stitchPieces($pieces, $level); }
private function stitchPieces(array $pieces, $level) { $results = array(); $count = count($pieces); for ($ii = 0; $ii < $count; $ii += 2) { $result = $pieces[$ii]; if ($ii + 1 < $count) { $result .= $pieces[$ii + 1]; }
if ($level < 2) { $trimmed_pieces = $this->trimApart($result); foreach ($trimmed_pieces as $trimmed_piece) { $results[] = $trimmed_piece; } } else { $results[] = $result; } }
// If the input ended with a delimiter, we can get an empty final piece. // Just discard it. if (last($results) == '') { array_pop($results); }
return $results; }
private function newEditDistanceMatrixDiff( array $u_parts, array $v_parts, $level) {
$matrix = id(new PhutilEditDistanceMatrix()) ->setMaximumLength(128) ->setSequences($u_parts, $v_parts) ->setComputeString(true);
// For word-level and character-level changes, smooth the output string // to reduce the choppiness of the diff. if ($level > 1) { $matrix->setApplySmoothing(PhutilEditDistanceMatrix::SMOOTHING_FULL); }
$u_pos = 0; $v_pos = 0;
$edits = $matrix->getEditString(); $edits_length = strlen($edits);
$diff = new PhutilProseDiff(); for ($ii = 0; $ii < $edits_length; $ii++) { $c = $edits[$ii]; if ($c == 's') { $diff->addPart('=', $u_parts[$u_pos]); $u_pos++; $v_pos++; } else if ($c == 'd') { $diff->addPart('-', $u_parts[$u_pos]); $u_pos++; } else if ($c == 'i') { $diff->addPart('+', $v_parts[$v_pos]); $v_pos++; } else if ($c == 'x') { $diff->addPart('-', $u_parts[$u_pos]); $diff->addPart('+', $v_parts[$v_pos]); $u_pos++; $v_pos++; } else { throw new Exception( pht( 'Unexpected character ("%s") in edit string.', $c)); } }
return array($diff, $matrix->didReachMaximumLength()); }
private function newHashDiff(array $u_parts, array $v_parts) {
$u_ref = new PhabricatorDocumentRef(); $v_ref = new PhabricatorDocumentRef();
$u_blocks = $this->newDocumentEngineBlocks($u_parts); $v_blocks = $this->newDocumentEngineBlocks($v_parts);
$rows = id(new PhabricatorDocumentEngineBlocks()) ->addBlockList($u_ref, $u_blocks) ->addBlockList($v_ref, $v_blocks) ->newTwoUpLayout();
$diff = new PhutilProseDiff(); foreach ($rows as $row) { list($u_block, $v_block) = $row;
if ($u_block && $v_block) { if ($u_block->getDifferenceType() === '-') { $diff->addPart('-', $u_block->getContent()); $diff->addPart('+', $v_block->getContent()); } else { $diff->addPart('=', $u_block->getContent()); } } else if ($u_block) { $diff->addPart('-', $u_block->getContent()); } else { $diff->addPart('+', $v_block->getContent()); } }
return $diff; }
private function newDocumentEngineBlocks(array $parts) { $blocks = array();
foreach ($parts as $part) { $hash = PhabricatorHash::digestForIndex($part);
$blocks[] = id(new PhabricatorDocumentEngineBlock()) ->setContent($part) ->setDifferenceHash($hash); }
return $blocks; }
public static function trimApart($input) { // Split pieces into separate text and whitespace sections: make one // piece out of all the whitespace at the beginning, one piece out of // all the actual text in the middle, and one piece out of all the // whitespace at the end.
$parts = array();
$length = strlen($input);
$corpus = ltrim($input); $l_length = strlen($corpus); if ($l_length !== $length) { $parts[] = substr($input, 0, $length - $l_length); }
$corpus = rtrim($corpus); $lr_length = strlen($corpus);
if ($lr_length) { $parts[] = $corpus; }
if ($lr_length !== $l_length) { // NOTE: This will be a negative value; we're slicing from the end of // the input string. $parts[] = substr($input, $lr_length - $l_length); }
return $parts; }
}