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

   1 <?php
   2
   3 namespace Caxy\HtmlDiff;
   4
   5 use Caxy\HtmlDiff\Table\TableDiff;
   6
   7 /**
   8  * Class HtmlDiff.
   9  */
  10 class HtmlDiff extends AbstractDiff
  11 {
  12     /**
  13      * @var array
  14      */
  15     protected $wordIndices;
  16     /**
  17      * @var array
  18      */
  19     protected $oldTables;
  20     /**
  21      * @var array
  22      */
  23     protected $newTables;
  24     /**
  25      * @var array
  26      */
  27     protected $newIsolatedDiffTags;
  28     /**
  29      * @var array
  30      */
  31     protected $oldIsolatedDiffTags;
  32
  33     /**
  34      * @param string              $oldText
  35      * @param string              $newText
  36      * @param HtmlDiffConfig|null $config
  37      *
  38      * @return self
  39      */
  40     public static function create($oldText, $newText, HtmlDiffConfig $config = null)
  41     {
  42         $diff = new self($oldText, $newText);
  43
  44         if (null !== $config) {
  45             $diff->setConfig($config);
  46         }
  47
  48         return $diff;
  49     }
  50
  51     /**
  52      * @param $bool
  53      *
  54      * @return $this
  55      *
  56      * @deprecated since 0.1.0
  57      */
  58     public function setUseTableDiffing($bool)
  59     {
  60         $this->config->setUseTableDiffing($bool);
  61
  62         return $this;
  63     }
  64
  65     /**
  66      * @param bool $boolean
  67      *
  68      * @return HtmlDiff
  69      *
  70      * @deprecated since 0.1.0
  71      */
  72     public function setInsertSpaceInReplace($boolean)
  73     {
  74         $this->config->setInsertSpaceInReplace($boolean);
  75
  76         return $this;
  77     }
  78
  79     /**
  80      * @return bool
  81      *
  82      * @deprecated since 0.1.0
  83      */
  84     public function getInsertSpaceInReplace()
  85     {
  86         return $this->config->isInsertSpaceInReplace();
  87     }
  88
  89     /**
  90      * @return string
  91      */
  92     public function build()
  93     {
  94         $this->prepare();
  95
  96         if ($this->hasDiffCache() && $this->getDiffCache()->contains($this->oldText, $this->newText)) {
  97             $this->content = $this->getDiffCache()->fetch($this->oldText, $this->newText);
  98
  99             return $this->content;
 100         }
 101
 102         // Pre-processing Optimizations
 103
 104         // 1. Equality
 105         if ($this->oldText == $this->newText) {
 106             return $this->newText;
 107         }
 108
 109         $this->splitInputsToWords();
 110         $this->replaceIsolatedDiffTags();
 111         $this->indexNewWords();
 112
 113         $operations = $this->operations();
 114
 115         foreach ($operations as $item) {
 116             $this->performOperation($item);
 117         }
 118
 119         if ($this->hasDiffCache()) {
 120             $this->getDiffCache()->save($this->oldText, $this->newText, $this->content);
 121         }
 122
 123         return $this->content;
 124     }
 125
 126     protected function indexNewWords()
 127     {
 128         $this->wordIndices = array();
 129         foreach ($this->newWords as $i => $word) {
 130             if ($this->isTag($word)) {
 131                 $word = $this->stripTagAttributes($word);
 132             }
 133             if (isset($this->wordIndices[ $word ])) {
 134                 $this->wordIndices[ $word ][] = $i;
 135             } else {
 136                 $this->wordIndices[ $word ] = array($i);
 137             }
 138         }
 139     }
 140
 141     protected function replaceIsolatedDiffTags()
 142     {
 143         $this->oldIsolatedDiffTags = $this->createIsolatedDiffTagPlaceholders($this->oldWords);
 144         $this->newIsolatedDiffTags = $this->createIsolatedDiffTagPlaceholders($this->newWords);
 145     }
 146
 147     /**
 148      * @param array $words
 149      *
 150      * @return array
 151      */
 152     protected function createIsolatedDiffTagPlaceholders(&$words)
 153     {
 154         $openIsolatedDiffTags = 0;
 155         $isolatedDiffTagIndices = array();
 156         $isolatedDiffTagStart = 0;
 157         $currentIsolatedDiffTag = null;
 158         foreach ($words as $index => $word) {
 159             $openIsolatedDiffTag = $this->isOpeningIsolatedDiffTag($word, $currentIsolatedDiffTag);
 160             if ($openIsolatedDiffTag) {
 161                 if ($this->isSelfClosingTag($word) || mb_stripos($word, '<img') !== false) {
 162                     if ($openIsolatedDiffTags === 0) {
 163                         $isolatedDiffTagIndices[] = array(
 164                             'start' => $index,
 165                             'length' => 1,
 166                             'tagType' => $openIsolatedDiffTag,
 167                         );
 168                         $currentIsolatedDiffTag = null;
 169                     }
 170                 } else {
 171                     if ($openIsolatedDiffTags === 0) {
 172                         $isolatedDiffTagStart = $index;
 173                     }
 174                     ++$openIsolatedDiffTags;
 175                     $currentIsolatedDiffTag = $openIsolatedDiffTag;
 176                 }
 177             } elseif ($openIsolatedDiffTags > 0 && $this->isClosingIsolatedDiffTag($word, $currentIsolatedDiffTag)) {
 178                 --$openIsolatedDiffTags;
 179                 if ($openIsolatedDiffTags == 0) {
 180                     $isolatedDiffTagIndices[] = array('start' => $isolatedDiffTagStart, 'length' => $index - $isolatedDiffTagStart + 1, 'tagType' => $currentIsolatedDiffTag);
 181                     $currentIsolatedDiffTag = null;
 182                 }
 183             }
 184         }
 185         $isolatedDiffTagScript = array();
 186         $offset = 0;
 187         foreach ($isolatedDiffTagIndices as $isolatedDiffTagIndex) {
 188             $start = $isolatedDiffTagIndex['start'] - $offset;
 189             $placeholderString = $this->config->getIsolatedDiffTagPlaceholder($isolatedDiffTagIndex['tagType']);
 190             $isolatedDiffTagScript[$start] = array_splice($words, $start, $isolatedDiffTagIndex['length'], $placeholderString);
 191             $offset += $isolatedDiffTagIndex['length'] - 1;
 192         }
 193
 194         return $isolatedDiffTagScript;
 195     }
 196
 197     /**
 198      * @param string      $item
 199      * @param null|string $currentIsolatedDiffTag
 200      *
 201      * @return false|string
 202      */
 203     protected function isOpeningIsolatedDiffTag($item, $currentIsolatedDiffTag = null)
 204     {
 205         $tagsToMatch = $currentIsolatedDiffTag !== null
 206             ? array($currentIsolatedDiffTag => $this->config->getIsolatedDiffTagPlaceholder($currentIsolatedDiffTag))
 207             : $this->config->getIsolatedDiffTags();
 208         $pattern = '#<%s(\s+[^>]*)?>#iUu';
 209         foreach ($tagsToMatch as $key => $value) {
 210             if (preg_match(sprintf($pattern, $key), $item)) {
 211                 return $key;
 212             }
 213         }
 214
 215         return false;
 216     }
 217
 218     protected function isSelfClosingTag($text)
 219     {
 220         return (bool) preg_match('/<[^>]+\/\s*>/u', $text);
 221     }
 222
 223     /**
 224      * @param string      $item
 225      * @param null|string $currentIsolatedDiffTag
 226      *
 227      * @return false|string
 228      */
 229     protected function isClosingIsolatedDiffTag($item, $currentIsolatedDiffTag = null)
 230     {
 231         $tagsToMatch = $currentIsolatedDiffTag !== null
 232             ? array($currentIsolatedDiffTag => $this->config->getIsolatedDiffTagPlaceholder($currentIsolatedDiffTag))
 233             : $this->config->getIsolatedDiffTags();
 234         $pattern = '#</%s(\s+[^>]*)?>#iUu';
 235         foreach ($tagsToMatch as $key => $value) {
 236             if (preg_match(sprintf($pattern, $key), $item)) {
 237                 return $key;
 238             }
 239         }
 240
 241         return false;
 242     }
 243
 244     /**
 245      * @param Operation $operation
 246      */
 247     protected function performOperation($operation)
 248     {
 249         switch ($operation->action) {
 250             case 'equal' :
 251             $this->processEqualOperation($operation);
 252             break;
 253             case 'delete' :
 254             $this->processDeleteOperation($operation, 'diffdel');
 255             break;
 256             case 'insert' :
 257             $this->processInsertOperation($operation, 'diffins');
 258             break;
 259             case 'replace':
 260             $this->processReplaceOperation($operation);
 261             break;
 262             default:
 263             break;
 264         }
 265     }
 266
 267     /**
 268      * @param Operation $operation
 269      */
 270     protected function processReplaceOperation($operation)
 271     {
 272         $this->processDeleteOperation($operation, 'diffmod');
 273         $this->processInsertOperation($operation, 'diffmod');
 274     }
 275
 276     /**
 277      * @param Operation $operation
 278      * @param string    $cssClass
 279      */
 280     protected function processInsertOperation($operation, $cssClass)
 281     {
 282         $text = array();
 283         foreach ($this->newWords as $pos => $s) {
 284             if ($pos >= $operation->startInNew && $pos < $operation->endInNew) {
 285                 if ($this->config->isIsolatedDiffTagPlaceholder($s) && isset($this->newIsolatedDiffTags[$pos])) {
 286                     foreach ($this->newIsolatedDiffTags[$pos] as $word) {
 287                         $text[] = $word;
 288                     }
 289                 } else {
 290                     $text[] = $s;
 291                 }
 292             }
 293         }
 294         $this->insertTag('ins', $cssClass, $text);
 295     }
 296
 297     /**
 298      * @param Operation $operation
 299      * @param string    $cssClass
 300      */
 301     protected function processDeleteOperation($operation, $cssClass)
 302     {
 303         $text = array();
 304         foreach ($this->oldWords as $pos => $s) {
 305             if ($pos >= $operation->startInOld && $pos < $operation->endInOld) {
 306                 if ($this->config->isIsolatedDiffTagPlaceholder($s) && isset($this->oldIsolatedDiffTags[$pos])) {
 307                     foreach ($this->oldIsolatedDiffTags[$pos] as $word) {
 308                         $text[] = $word;
 309                     }
 310                 } else {
 311                     $text[] = $s;
 312                 }
 313             }
 314         }
 315         $this->insertTag('del', $cssClass, $text);
 316     }
 317
 318     /**
 319      * @param Operation $operation
 320      * @param int       $pos
 321      * @param string    $placeholder
 322      * @param bool      $stripWrappingTags
 323      *
 324      * @return string
 325      */
 326     protected function diffIsolatedPlaceholder($operation, $pos, $placeholder, $stripWrappingTags = true)
 327     {
 328         $oldText = implode('', $this->findIsolatedDiffTagsInOld($operation, $pos));
 329         $newText = implode('', $this->newIsolatedDiffTags[$pos]);
 330
 331         if ($this->isListPlaceholder($placeholder)) {
 332             return $this->diffList($oldText, $newText);
 333         } elseif ($this->config->isUseTableDiffing() && $this->isTablePlaceholder($placeholder)) {
 334             return $this->diffTables($oldText, $newText);
 335         } elseif ($this->isLinkPlaceholder($placeholder)) {
 336             return $this->diffElementsByAttribute($oldText, $newText, 'href', 'a');
 337         } elseif ($this->isImagePlaceholder($placeholder)) {
 338             return $this->diffElementsByAttribute($oldText, $newText, 'src', 'img');
 339         }
 340
 341         return $this->diffElements($oldText, $newText, $stripWrappingTags);
 342     }
 343
 344     /**
 345      * @param string $oldText
 346      * @param string $newText
 347      * @param bool   $stripWrappingTags
 348      *
 349      * @return string
 350      */
 351     protected function diffElements($oldText, $newText, $stripWrappingTags = true)
 352     {
 353         $wrapStart = '';
 354         $wrapEnd = '';
 355
 356         if ($stripWrappingTags) {
 357             $pattern = '/(^<[^>]+>)|(<\/[^>]+>$)/iu';
 358             $matches = array();
 359
 360             if (preg_match_all($pattern, $newText, $matches)) {
 361                 $wrapStart = isset($matches[0][0]) ? $matches[0][0] : '';
 362                 $wrapEnd = isset($matches[0][1]) ? $matches[0][1] : '';
 363             }
 364             $oldText = preg_replace($pattern, '', $oldText);
 365             $newText = preg_replace($pattern, '', $newText);
 366         }
 367
 368         $diff = self::create($oldText, $newText, $this->config);
 369
 370         return $wrapStart.$diff->build().$wrapEnd;
 371     }
 372
 373     /**
 374      * @param string $oldText
 375      * @param string $newText
 376      *
 377      * @return string
 378      */
 379     protected function diffList($oldText, $newText)
 380     {
 381         $diff = ListDiffLines::create($oldText, $newText, $this->config);
 382
 383         return $diff->build();
 384     }
 385
 386     /**
 387      * @param string $oldText
 388      * @param string $newText
 389      *
 390      * @return string
 391      */
 392     protected function diffTables($oldText, $newText)
 393     {
 394         $diff = TableDiff::create($oldText, $newText, $this->config);
 395
 396         return $diff->build();
 397     }
 398
 399     protected function diffElementsByAttribute($oldText, $newText, $attribute, $element)
 400     {
 401         $oldAttribute = $this->getAttributeFromTag($oldText, $attribute);
 402         $newAttribute = $this->getAttributeFromTag($newText, $attribute);
 403
 404         if ($oldAttribute !== $newAttribute) {
 405             $diffClass = sprintf('diffmod diff%s diff%s', $element, $attribute);
 406
 407             return sprintf(
 408                 '%s%s',
 409                 $this->wrapText($oldText, 'del', $diffClass),
 410                 $this->wrapText($newText, 'ins', $diffClass)
 411             );
 412         }
 413
 414         return $this->diffElements($oldText, $newText);
 415     }
 416
 417     /**
 418      * @param Operation $operation
 419      */
 420     protected function processEqualOperation($operation)
 421     {
 422         $result = array();
 423         foreach ($this->newWords as $pos => $s) {
 424             if ($pos >= $operation->startInNew && $pos < $operation->endInNew) {
 425                 if ($this->config->isIsolatedDiffTagPlaceholder($s) && isset($this->newIsolatedDiffTags[$pos])) {
 426                     $result[] = $this->diffIsolatedPlaceholder($operation, $pos, $s);
 427                 } else {
 428                     $result[] = $s;
 429                 }
 430             }
 431         }
 432         $this->content .= implode('', $result);
 433     }
 434
 435     /**
 436      * @param string $text
 437      * @param string $attribute
 438      *
 439      * @return null|string
 440      */
 441     protected function getAttributeFromTag($text, $attribute)
 442     {
 443         $matches = array();
 444         if (preg_match(sprintf('/<[^>]*\b%s\s*=\s*([\'"])(.*)\1[^>]*>/iu', $attribute), $text, $matches)) {
 445             return htmlspecialchars_decode($matches[2]);
 446         }
 447
 448         return;
 449     }
 450
 451     /**
 452      * @param string $text
 453      *
 454      * @return bool
 455      */
 456     protected function isListPlaceholder($text)
 457     {
 458         return $this->isPlaceholderType($text, array('ol', 'dl', 'ul'));
 459     }
 460
 461     /**
 462      * @param string $text
 463      *
 464      * @return bool
 465      */
 466     public function isLinkPlaceholder($text)
 467     {
 468         return $this->isPlaceholderType($text, 'a');
 469     }
 470
 471     /**
 472      * @param string $text
 473      *
 474      * @return bool
 475      */
 476     public function isImagePlaceholder($text)
 477     {
 478         return $this->isPlaceholderType($text, 'img');
 479     }
 480
 481     /**
 482      * @param string       $text
 483      * @param array|string $types
 484      * @param bool         $strict
 485      *
 486      * @return bool
 487      */
 488     protected function isPlaceholderType($text, $types, $strict = true)
 489     {
 490         if (!is_array($types)) {
 491             $types = array($types);
 492         }
 493
 494         $criteria = array();
 495         foreach ($types as $type) {
 496             if ($this->config->isIsolatedDiffTag($type)) {
 497                 $criteria[] = $this->config->getIsolatedDiffTagPlaceholder($type);
 498             } else {
 499                 $criteria[] = $type;
 500             }
 501         }
 502
 503         return in_array($text, $criteria, $strict);
 504     }
 505
 506     /**
 507      * @param string $text
 508      *
 509      * @return bool
 510      */
 511     protected function isTablePlaceholder($text)
 512     {
 513         return $this->isPlaceholderType($text, 'table');
 514     }
 515
 516     /**
 517      * @param Operation $operation
 518      * @param int       $posInNew
 519      *
 520      * @return array
 521      */
 522     protected function findIsolatedDiffTagsInOld($operation, $posInNew)
 523     {
 524         $offset = $posInNew - $operation->startInNew;
 525
 526         return $this->oldIsolatedDiffTags[$operation->startInOld + $offset];
 527     }
 528
 529     /**
 530      * @param string $tag
 531      * @param string $cssClass
 532      * @param array  $words
 533      */
 534     protected function insertTag($tag, $cssClass, &$words)
 535     {
 536         while (true) {
 537             if (count($words) == 0) {
 538                 break;
 539             }
 540
 541             $nonTags = $this->extractConsecutiveWords($words, 'noTag');
 542
 543             $specialCaseTagInjection = '';
 544             $specialCaseTagInjectionIsBefore = false;
 545
 546             if (count($nonTags) != 0) {
 547                 $text = $this->wrapText(implode('', $nonTags), $tag, $cssClass);
 548                 $this->content .= $text;
 549             } else {
 550                 $firstOrDefault = false;
 551                 foreach ($this->config->getSpecialCaseOpeningTags() as $x) {
 552                     if (preg_match($x, $words[ 0 ])) {
 553                         $firstOrDefault = $x;
 554                         break;
 555                     }
 556                 }
 557                 if ($firstOrDefault) {
 558                     $specialCaseTagInjection = '<ins class="mod">';
 559                     if ($tag == 'del') {
 560                         unset($words[ 0 ]);
 561                     }
 562                 } elseif (array_search($words[ 0 ], $this->config->getSpecialCaseClosingTags()) !== false) {
 563                     $specialCaseTagInjection = '</ins>';
 564                     $specialCaseTagInjectionIsBefore = true;
 565                     if ($tag == 'del') {
 566                         unset($words[ 0 ]);
 567                     }
 568                 }
 569             }
 570             if (count($words) == 0 && mb_strlen($specialCaseTagInjection) == 0) {
 571                 break;
 572             }
 573             if ($specialCaseTagInjectionIsBefore) {
 574                 $this->content .= $specialCaseTagInjection.implode('', $this->extractConsecutiveWords($words, 'tag'));
 575             } else {
 576                 $workTag = $this->extractConsecutiveWords($words, 'tag');
 577                 if (isset($workTag[ 0 ]) && $this->isOpeningTag($workTag[ 0 ]) && !$this->isClosingTag($workTag[ 0 ])) {
 578                     if (mb_strpos($workTag[ 0 ], 'class=')) {
 579                         $workTag[ 0 ] = str_replace('class="', 'class="diffmod ', $workTag[ 0 ]);
 580                         $workTag[ 0 ] = str_replace("class='", 'class="diffmod ', $workTag[ 0 ]);
 581                     } else {
 582                         $workTag[ 0 ] = str_replace('>', ' class="diffmod">', $workTag[ 0 ]);
 583                     }
 584                 }
 585
 586                 $appendContent = implode('', $workTag).$specialCaseTagInjection;
 587                 if (isset($workTag[0]) && false !== mb_stripos($workTag[0], '<img')) {
 588                     $appendContent = $this->wrapText($appendContent, $tag, $cssClass);
 589                 }
 590                 $this->content .= $appendContent;
 591             }
 592         }
 593     }
 594
 595     /**
 596      * @param string $word
 597      * @param string $condition
 598      *
 599      * @return bool
 600      */
 601     protected function checkCondition($word, $condition)
 602     {
 603         return $condition == 'tag' ? $this->isTag($word) : !$this->isTag($word);
 604     }
 605
 606     /**
 607      * @param string $text
 608      * @param string $tagName
 609      * @param string $cssClass
 610      *
 611      * @return string
 612      */
 613     protected function wrapText($text, $tagName, $cssClass)
 614     {
 615         return sprintf('<%1$s class="%2$s">%3$s</%1$s>', $tagName, $cssClass, $text);
 616     }
 617
 618     /**
 619      * @param array  $words
 620      * @param string $condition
 621      *
 622      * @return array
 623      */
 624     protected function extractConsecutiveWords(&$words, $condition)
 625     {
 626         $indexOfFirstTag = null;
 627         $words = array_values($words);
 628         foreach ($words as $i => $word) {
 629             if (!$this->checkCondition($word, $condition)) {
 630                 $indexOfFirstTag = $i;
 631                 break;
 632             }
 633         }
 634         if ($indexOfFirstTag !== null) {
 635             $items = array();
 636             foreach ($words as $pos => $s) {
 637                 if ($pos >= 0 && $pos < $indexOfFirstTag) {
 638                     $items[] = $s;
 639                 }
 640             }
 641             if ($indexOfFirstTag > 0) {
 642                 array_splice($words, 0, $indexOfFirstTag);
 643             }
 644
 645             return $items;
 646         } else {
 647             $items = array();
 648             foreach ($words as $pos => $s) {
 649                 if ($pos >= 0 && $pos <= count($words)) {
 650                     $items[] = $s;
 651                 }
 652             }
 653             array_splice($words, 0, count($words));
 654
 655             return $items;
 656         }
 657     }
 658
 659     /**
 660      * @param string $item
 661      *
 662      * @return bool
 663      */
 664     protected function isTag($item)
 665     {
 666         return $this->isOpeningTag($item) || $this->isClosingTag($item);
 667     }
 668
 669     /**
 670      * @param string $item
 671      *
 672      * @return bool
 673      */
 674     protected function isOpeningTag($item)
 675     {
 676         return preg_match('#<[^>]+>\\s*#iUu', $item);
 677     }
 678
 679     /**
 680      * @param string $item
 681      *
 682      * @return bool
 683      */
 684     protected function isClosingTag($item)
 685     {
 686         return preg_match('#</[^>]+>\\s*#iUu', $item);
 687     }
 688
 689     /**
 690      * @return Operation[]
 691      */
 692     protected function operations()
 693     {
 694         $positionInOld = 0;
 695         $positionInNew = 0;
 696         $operations = array();
 697
 698         $matches   = $this->matchingBlocks();
 699         $matches[] = new Match(count($this->oldWords), count($this->newWords), 0);
 700
 701         foreach ($matches as $i => $match) {
 702             $matchStartsAtCurrentPositionInOld = ($positionInOld === $match->startInOld);
 703             $matchStartsAtCurrentPositionInNew = ($positionInNew === $match->startInNew);
 704
 705             if ($matchStartsAtCurrentPositionInOld === false && $matchStartsAtCurrentPositionInNew === false) {
 706                 $action = 'replace';
 707             } elseif ($matchStartsAtCurrentPositionInOld === true && $matchStartsAtCurrentPositionInNew === false) {
 708                 $action = 'insert';
 709             } elseif ($matchStartsAtCurrentPositionInOld === false && $matchStartsAtCurrentPositionInNew === true) {
 710                 $action = 'delete';
 711             } else { // This occurs if the first few words are the same in both versions
 712                 $action = 'none';
 713             }
 714
 715             if ($action !== 'none') {
 716                 $operations[] = new Operation($action, $positionInOld, $match->startInOld, $positionInNew, $match->startInNew);
 717             }
 718
 719             if (count($match) !== 0) {
 720                 $operations[] = new Operation('equal', $match->startInOld, $match->endInOld(), $match->startInNew, $match->endInNew());
 721             }
 722
 723             $positionInOld = $match->endInOld();
 724             $positionInNew = $match->endInNew();
 725         }
 726
 727         return $operations;
 728     }
 729
 730     /**
 731      * @return Match[]
 732      */
 733     protected function matchingBlocks()
 734     {
 735         $matchingBlocks = array();
 736         $this->findMatchingBlocks(0, count($this->oldWords), 0, count($this->newWords), $matchingBlocks);
 737
 738         return $matchingBlocks;
 739     }
 740
 741     /**
 742      * @param int   $startInOld
 743      * @param int   $endInOld
 744      * @param int   $startInNew
 745      * @param int   $endInNew
 746      * @param array $matchingBlocks
 747      */
 748     protected function findMatchingBlocks($startInOld, $endInOld, $startInNew, $endInNew, &$matchingBlocks)
 749     {
 750         $match = $this->findMatch($startInOld, $endInOld, $startInNew, $endInNew);
 751
 752         if ($match !== null) {
 753             if ($startInOld < $match->startInOld && $startInNew < $match->startInNew) {
 754                 $this->findMatchingBlocks($startInOld, $match->startInOld, $startInNew, $match->startInNew, $matchingBlocks);
 755             }
 756
 757             $matchingBlocks[] = $match;
 758
 759             if ($match->endInOld() < $endInOld && $match->endInNew() < $endInNew) {
 760                 $this->findMatchingBlocks($match->endInOld(), $endInOld, $match->endInNew(), $endInNew, $matchingBlocks);
 761             }
 762         }
 763     }
 764
 765     /**
 766      * @param string $word
 767      *
 768      * @return string
 769      */
 770     protected function stripTagAttributes($word)
 771     {
 772         $space = mb_strpos($word, ' ', 1);
 773
 774         if ($space) {
 775             return '<' . mb_substr($word, 1, $space) . '>';
 776         }
 777
 778         return trim($word, '<>');
 779     }
 780
 781     /**
 782      * @param int $startInOld
 783      * @param int $endInOld
 784      * @param int $startInNew
 785      * @param int $endInNew
 786      *
 787      * @return Match|null
 788      */
 789     protected function findMatch($startInOld, $endInOld, $startInNew, $endInNew)
 790     {
 791         $bestMatchInOld = $startInOld;
 792         $bestMatchInNew = $startInNew;
 793         $bestMatchSize = 0;
 794         $matchLengthAt = array();
 795
 796         for ($indexInOld = $startInOld; $indexInOld < $endInOld; ++$indexInOld) {
 797             $newMatchLengthAt = array();
 798             $index = $this->oldWords[ $indexInOld ];
 799             if ($this->isTag($index)) {
 800                 $index = $this->stripTagAttributes($index);
 801             }
 802             if (!isset($this->wordIndices[ $index ])) {
 803                 $matchLengthAt = $newMatchLengthAt;
 804                 continue;
 805             }
 806             foreach ($this->wordIndices[ $index ] as $indexInNew) {
 807                 if ($indexInNew < $startInNew) {
 808                     continue;
 809                 }
 810                 if ($indexInNew >= $endInNew) {
 811                     break;
 812                 }
 813
 814                 $newMatchLength = (isset($matchLengthAt[ $indexInNew - 1 ]) ? $matchLengthAt[ $indexInNew - 1 ] : 0) + 1;
 815                 $newMatchLengthAt[ $indexInNew ] = $newMatchLength;
 816
 817                 if ($newMatchLength > $bestMatchSize ||
 818                     (
 819                         $this->isGroupDiffs() &&
 820                         $bestMatchSize > 0 &&
 821                         $this->isOnlyWhitespace($this->array_slice_cached($this->oldWords, $bestMatchInOld, $bestMatchSize))
 822                     )
 823                 ) {
 824                     $bestMatchInOld = $indexInOld - $newMatchLength + 1;
 825                     $bestMatchInNew = $indexInNew - $newMatchLength + 1;
 826                     $bestMatchSize = $newMatchLength;
 827                 }
 828             }
 829             $matchLengthAt = $newMatchLengthAt;
 830         }
 831
 832         // Skip match if none found or match consists only of whitespace
 833         if ($bestMatchSize != 0 &&
 834             (
 835                 !$this->isGroupDiffs() ||
 836                 !$this->isOnlyWhitespace($this->array_slice_cached($this->oldWords, $bestMatchInOld, $bestMatchSize))
 837             )
 838         ) {
 839             return new Match($bestMatchInOld, $bestMatchInNew, $bestMatchSize);
 840         }
 841
 842         return null;
 843     }
 844
 845     /**
 846      * @param string $str
 847      *
 848      * @return bool
 849      */
 850     protected function isOnlyWhitespace($str)
 851     {
 852         //  Slightly faster then using preg_match
 853         return $str !== '' && (mb_strlen(trim($str)) === 0);
 854     }
 855
 856     /**
 857      * Special array_slice function that caches its last request.
 858      *
 859      * The diff algorithm seems to request the same information many times in a row.
 860      * by returning the previous answer the algorithm preforms way faster.
 861      *
 862      * The result is a string instead of an array, this way we safe on the amount of
 863      * memory intensive implode() calls.
 864      *
 865      * @param array         &$array
 866      * @param integer       $offset
 867      * @param integer|null  $length
 868      *
 869      * @return string
 870      */
 871     protected function array_slice_cached(&$array, $offset, $length = null)
 872     {
 873         static $lastOffset = null;
 874         static $lastLength = null;
 875         static $cache      = null;
 876
 877         // PHP has no support for by-reference comparing.
 878         // to prevent false positive hits, reset the cache when the oldWords or newWords is changed.
 879         if ($this->resetCache === true) {
 880             $cache = null;
 881
 882             $this->resetCache = false;
 883         }
 884
 885         if (
 886             $cache !== null &&
 887             $lastLength === $length &&
 888             $lastOffset === $offset
 889         ) { // Hit
 890             return $cache;
 891         } // Miss
 892
 893         $lastOffset = $offset;
 894         $lastLength = $length;
 895
 896         $cache = implode('', array_slice($array, $offset, $length));
 897
 898         return $cache;
 899     }
 900 }