www.aleph1.co.uk Git - yaffs-website/blob - vendor/caxy/php-htmldiff/lib/Caxy/HtmlDiff/ListDiffLines.php

   1 <?php
   2
   3 namespace Caxy\HtmlDiff;
   4
   5 use Caxy\HtmlDiff\Strategy\ListItemMatchStrategy;
   6 use Sunra\PhpSimple\HtmlDomParser;
   7
   8 class ListDiffLines extends AbstractDiff
   9 {
  10     const CLASS_LIST_ITEM_ADDED = 'normal new';
  11     const CLASS_LIST_ITEM_DELETED = 'removed';
  12     const CLASS_LIST_ITEM_CHANGED = 'replacement';
  13     const CLASS_LIST_ITEM_NONE = 'normal';
  14
  15     protected static $listTypes = array('ul', 'ol', 'dl');
  16
  17     /**
  18      * List of tags that should be included when retrieving
  19      * text from a single list item that will be used in
  20      * matching logic (and only in matching logic).
  21      *
  22      * @see getRelevantNodeText()
  23      *
  24      * @var array
  25      */
  26     protected static $listContentTags = array(
  27         'h1','h2','h3','h4','h5','pre','div','br','hr','code',
  28         'input','form','img','span','a','i','b','strong','em',
  29         'font','big','del','tt','sub','sup','strike',
  30     );
  31
  32     /**
  33      * @var LcsService
  34      */
  35     protected $lcsService;
  36
  37     /**
  38      * @param string              $oldText
  39      * @param string              $newText
  40      * @param HtmlDiffConfig|null $config
  41      *
  42      * @return ListDiffLines
  43      */
  44     public static function create($oldText, $newText, HtmlDiffConfig $config = null)
  45     {
  46         $diff = new self($oldText, $newText);
  47
  48         if (null !== $config) {
  49             $diff->setConfig($config);
  50         }
  51
  52         return $diff;
  53     }
  54
  55     /**
  56      * {@inheritDoc}
  57      */
  58     public function build()
  59     {
  60         $this->prepare();
  61
  62         if ($this->hasDiffCache() && $this->getDiffCache()->contains($this->oldText, $this->newText)) {
  63             $this->content = $this->getDiffCache()->fetch($this->oldText, $this->newText);
  64
  65             return $this->content;
  66         }
  67
  68         $matchStrategy = new ListItemMatchStrategy($this->config->getMatchThreshold());
  69         $this->lcsService = new LcsService($matchStrategy);
  70
  71         return $this->listByLines($this->oldText, $this->newText);
  72     }
  73
  74     /**
  75      * @param string $old
  76      * @param string $new
  77      *
  78      * @return string
  79      */
  80     protected function listByLines($old, $new)
  81     {
  82         /* @var $newDom \simple_html_dom */
  83         $newDom = HtmlDomParser::str_get_html($new);
  84         /* @var $oldDom \simple_html_dom */
  85         $oldDom = HtmlDomParser::str_get_html($old);
  86
  87         $newListNode = $this->findListNode($newDom);
  88         $oldListNode = $this->findListNode($oldDom);
  89
  90         $operations = $this->getListItemOperations($oldListNode, $newListNode);
  91
  92         return $this->processOperations($operations, $oldListNode, $newListNode);
  93     }
  94
  95     /**
  96      * @param \simple_html_dom|\simple_html_dom_node $dom
  97      *
  98      * @return \simple_html_dom_node[]|\simple_html_dom_node|null
  99      */
 100     protected function findListNode($dom)
 101     {
 102         return $dom->find(implode(', ', static::$listTypes), 0);
 103     }
 104
 105     /**
 106      * @param \simple_html_dom_node $oldListNode
 107      * @param \simple_html_dom_node $newListNode
 108      *
 109      * @return array|Operation[]
 110      */
 111     protected function getListItemOperations($oldListNode, $newListNode)
 112     {
 113         // Prepare arrays of list item content to use in LCS algorithm
 114         $oldListText = $this->getListTextArray($oldListNode);
 115         $newListText = $this->getListTextArray($newListNode);
 116
 117         $lcsMatches = $this->lcsService->longestCommonSubsequence($oldListText, $newListText);
 118
 119         $oldLength = count($oldListText);
 120         $newLength = count($newListText);
 121
 122         $operations = array();
 123         $currentLineInOld = 0;
 124         $currentLineInNew = 0;
 125         $lcsMatches[$oldLength + 1] = $newLength + 1;
 126         foreach ($lcsMatches as $matchInOld => $matchInNew) {
 127             // No matching line in new list
 128             if ($matchInNew === 0) {
 129                 continue;
 130             }
 131
 132             $nextLineInOld = $currentLineInOld + 1;
 133             $nextLineInNew = $currentLineInNew + 1;
 134
 135             if ($matchInNew > $nextLineInNew && $matchInOld > $nextLineInOld) {
 136                 // Change
 137                 $operations[] = new Operation(
 138                     Operation::CHANGED,
 139                     $nextLineInOld,
 140                     $matchInOld - 1,
 141                     $nextLineInNew,
 142                     $matchInNew - 1
 143                 );
 144             } elseif ($matchInNew > $nextLineInNew && $matchInOld === $nextLineInOld) {
 145                 // Add items before this
 146                 $operations[] = new Operation(
 147                     Operation::ADDED,
 148                     $currentLineInOld,
 149                     $currentLineInOld,
 150                     $nextLineInNew,
 151                     $matchInNew - 1
 152                 );
 153             } elseif ($matchInNew === $nextLineInNew && $matchInOld > $nextLineInOld) {
 154                 // Delete items before this
 155                 $operations[] = new Operation(
 156                     Operation::DELETED,
 157                     $nextLineInOld,
 158                     $matchInOld - 1,
 159                     $currentLineInNew,
 160                     $currentLineInNew
 161                 );
 162             }
 163
 164             $currentLineInNew = $matchInNew;
 165             $currentLineInOld = $matchInOld;
 166         }
 167
 168         return $operations;
 169     }
 170
 171     /**
 172      * @param \simple_html_dom_node $listNode
 173      *
 174      * @return array
 175      */
 176     protected function getListTextArray($listNode)
 177     {
 178         $output = array();
 179         foreach ($listNode->children() as $listItem) {
 180             $output[] = $this->getRelevantNodeText($listItem);
 181         }
 182
 183         return $output;
 184     }
 185
 186     /**
 187      * @param \simple_html_dom_node $node
 188      *
 189      * @return string
 190      */
 191     protected function getRelevantNodeText($node)
 192     {
 193         if (!$node->hasChildNodes()) {
 194             return $node->innertext();
 195         }
 196
 197         $output = '';
 198         foreach ($node->nodes as $child) {
 199             /* @var $child \simple_html_dom_node */
 200             if (!$child->hasChildNodes()) {
 201                 $output .= $child->outertext();
 202             } elseif (in_array($child->nodeName(), static::$listContentTags, true)) {
 203                 $output .= sprintf('<%1$s>%2$s</%1$s>', $child->nodeName(), $this->getRelevantNodeText($child));
 204             }
 205         }
 206
 207         return $output;
 208     }
 209
 210     /**
 211      * @param \simple_html_dom_node $li
 212      *
 213      * @return string
 214      */
 215     protected function deleteListItem($li)
 216     {
 217         $this->addClassToNode($li, self::CLASS_LIST_ITEM_DELETED);
 218         $li->innertext = sprintf('<del>%s</del>', $li->innertext);
 219
 220         return $li->outertext;
 221     }
 222
 223     /**
 224      * @param \simple_html_dom_node $li
 225      * @param bool                  $replacement
 226      *
 227      * @return string
 228      */
 229     protected function addListItem($li, $replacement = false)
 230     {
 231         $this->addClassToNode($li, $replacement ? self::CLASS_LIST_ITEM_CHANGED : self::CLASS_LIST_ITEM_ADDED);
 232         $li->innertext = sprintf('<ins>%s</ins>', $li->innertext);
 233
 234         return $li->outertext;
 235     }
 236
 237     /**
 238      * @param Operation[]|array     $operations
 239      * @param \simple_html_dom_node $oldListNode
 240      * @param \simple_html_dom_node $newListNode
 241      *
 242      * @return string
 243      */
 244     protected function processOperations($operations, $oldListNode, $newListNode)
 245     {
 246         $output = '';
 247
 248         $indexInOld = 0;
 249         $indexInNew = 0;
 250         $lastOperation = null;
 251
 252         foreach ($operations as $operation) {
 253             $replaced = false;
 254             while ($operation->startInOld > ($operation->action === Operation::ADDED ? $indexInOld : $indexInOld + 1)) {
 255                 $li = $oldListNode->children($indexInOld);
 256                 $matchingLi = null;
 257                 if ($operation->startInNew > ($operation->action === Operation::DELETED ? $indexInNew
 258                         : $indexInNew + 1)
 259                 ) {
 260                     $matchingLi = $newListNode->children($indexInNew);
 261                 }
 262                 if (null !== $matchingLi) {
 263                     $htmlDiff = HtmlDiff::create($li->innertext, $matchingLi->innertext, $this->config);
 264                     $li->innertext = $htmlDiff->build();
 265                     $indexInNew++;
 266                 }
 267                 $class = self::CLASS_LIST_ITEM_NONE;
 268
 269                 if ($lastOperation === Operation::DELETED && !$replaced) {
 270                     $class = self::CLASS_LIST_ITEM_CHANGED;
 271                     $replaced = true;
 272                 }
 273                 $li->setAttribute('class', trim($li->getAttribute('class').' '.$class));
 274
 275                 $output .= $li->outertext;
 276                 $indexInOld++;
 277             }
 278
 279             switch ($operation->action) {
 280                 case Operation::ADDED:
 281                     for ($i = $operation->startInNew; $i <= $operation->endInNew; $i++) {
 282                         $output .= $this->addListItem($newListNode->children($i - 1));
 283                     }
 284                     $indexInNew = $operation->endInNew;
 285                     break;
 286
 287                 case Operation::DELETED:
 288                     for ($i = $operation->startInOld; $i <= $operation->endInOld; $i++) {
 289                         $output .= $this->deleteListItem($oldListNode->children($i - 1));
 290                     }
 291                     $indexInOld = $operation->endInOld;
 292                     break;
 293
 294                 case Operation::CHANGED:
 295                     $changeDelta = 0;
 296                     for ($i = $operation->startInOld; $i <= $operation->endInOld; $i++) {
 297                         $output .= $this->deleteListItem($oldListNode->children($i - 1));
 298                         $changeDelta--;
 299                     }
 300                     for ($i = $operation->startInNew; $i <= $operation->endInNew; $i++) {
 301                         $output .= $this->addListItem($newListNode->children($i - 1), $changeDelta < 0);
 302                         $changeDelta++;
 303                     }
 304                     $indexInOld = $operation->endInOld;
 305                     $indexInNew = $operation->endInNew;
 306                     break;
 307             }
 308
 309             $lastOperation = $operation->action;
 310         }
 311
 312         $oldCount = count($oldListNode->children());
 313         $newCount = count($newListNode->children());
 314         while ($indexInOld < $oldCount) {
 315             $li = $oldListNode->children($indexInOld);
 316             $matchingLi = null;
 317             if ($indexInNew < $newCount) {
 318                 $matchingLi = $newListNode->children($indexInNew);
 319             }
 320             if (null !== $matchingLi) {
 321                 $htmlDiff = HtmlDiff::create($li->innertext(), $matchingLi->innertext(), $this->config);
 322                 $li->innertext = $htmlDiff->build();
 323                 $indexInNew++;
 324             }
 325             $class = self::CLASS_LIST_ITEM_NONE;
 326
 327             if ($lastOperation === Operation::DELETED) {
 328                 $class = self::CLASS_LIST_ITEM_CHANGED;
 329             }
 330             $li->setAttribute('class', trim($li->getAttribute('class').' '.$class));
 331
 332             $output .= $li->outertext;
 333             $indexInOld++;
 334         }
 335
 336         $newListNode->innertext = $output;
 337         $newListNode->setAttribute('class', trim($newListNode->getAttribute('class').' diff-list'));
 338
 339         return $newListNode->outertext;
 340     }
 341
 342     /**
 343      * @param \simple_html_dom_node $node
 344      * @param string                $class
 345      */
 346     protected function addClassToNode($node, $class)
 347     {
 348         $node->setAttribute('class', trim(sprintf('%s %s', $node->getAttribute('class'), $class)));
 349     }
 350 }