Fast and simple PHP diff method

nerd, prog
The "diff" is done in the diff() function (only 25 LoC - although some might call this "too compact"); the rest is for presentation purpose (plain-text or HTML, side-by-side = horizontal, or diff lines above eachother = vertical):

<?php



namespace Rsi;



class Diff{



  const TYPE_EQUAL = 'e'; //!< A and B are equal.

  const TYPE_DIFF = 'x'; //!< A and B differ.

  const TYPE_SPACE = 's'; //!< A and B differ only in leading and trailing white-space.

  const TYPE_DIFF_A = 'a'; //!< A is not present in B.

  const TYPE_DIFF_B = 'b'; //!< B is not present in A.



  const HTML_MODE_VERTICAL = 'vertical'; //!< Show A above B in HTML view (when different).

  const HTML_MODE_HORIZONTAL = 'horizontal'; //!< Show A left and B right in HTML view.



  public $defaultHead = ['A','B']; //!< Default header for the HTML table.

  public $extra = 2; //!< Extra, unchanged lines to show around changes.

  public $extraAllThreshold = 2; //!< Show all code when there is max this number of lines to be hidden.

  public $styleFile = __DIR__ . '/diff.css'; //!< Stylsheet filename.

  public $htmlMode = self::HTML_MODE_VERTICAL; //!< See HTML_MODE_* constants.

  public $whiteSpaceThreshold = 0.2; //!< Only show "white-space only" changes if they are more then this part of the (maximum)

    // number of lines in the block.

  public $lineDiffMaxLines = 2; //!< Only show detailed diff info if the difference in line count is equal or below this amount.

  public $lineDiffThreshold = 0.6; //!< Only show detailed diff info if more than this part of the block stayed the same.

  public $skipTemplate = '* lines'; //!< Template for skipped lines (asterisk is replaced with number of lines).



  protected $_a = []; //!< Lines for side A.

  protected $_b = []; //!< Lines for side B.

  protected $_diff = []; //!< Diff results (array of blocks with keys: t = type, sa = start of block in A, ca = line count for

    // block in A, sb = start of block in B, cb = line count for block in B).



  /**

   * Create diff.

   * @param string $a  Text for A.

   * @param string $b  Text for B.

   * @param bool  Set to true if A and B are both local filenames. Besides loading the files, this will also set the default

   *   head to the filenames, combined with the modification date (and time, when changed within 24 hours of eachother).

   */

  public function __construct($a,$b,$files = false){

    if($files){

      $ta = filemtime($a);

      $tb = filemtime($b);

      $format = 'Y-m-d' . (($diff = abs($ta - $tb)) < 86400 ? ' H:i' . ($diff < 60 ? ':s' : null) : null);

      $this->defaultHead = [$a . ' @ ' . date($format,$ta),$b . ' @ ' . date($format,$tb)];

      $a = file_get_contents($a);

      $b = file_get_contents($b);

    }

    $this->_diff = $this->diff($this->_a = $this->lines($a),$this->_b = $this->lines($b));

  }



  protected function lines($str){

    return $str === null ? [] : explode("\n",$str);

  }

  /**

   * Calculate the difference between two blocks.

   * @param array $a  Lines of block A.

   * @param array $b  Lines of block B.

   * @param int $oa  Offset of block A in relation to the comlete file.

   * @param int $ob  Offset of block B in relation to the comlete file.

   * @return array  Array with a record per comparison block ('t' = block type - see TYPE_* constants, 'sa' = start of block in

   *   A, 'ca' = number of lines in A, 'sb' = start of block in B, 'cb' = number of lines in B).

   */

  protected function diff($a,$b,$oa = 0,$ob = 0){

    //prefixes: o = offset, c = count, s = start, i = index

    $ca = count($a);

    $cb = count($b);

    $sa = $sb = $count = 0;

    $cache = [];

    for($ia = 0; $ia < $ca - $count; $ia++)

      foreach(($cache[$a[$ia]] ?? ($cache[$a[$ia]] = array_keys($b,$a[$ia],true))) as $ib) if($ib < $cb - $count){

        for($c = 1; $c < $count; $c++) if($a[$ia + $c] !== $b[$ib + $c]) continue 2;

        while(($ia + $c < $ca) && ($ib + $c < $cb) && ($a[$ia + $c] === $b[$ib + $c])) $c++;

        $count = $c;

        $sa = $ia;

        $sb = $ib;

      }

    return $count

      ? array_merge(

          $this->diff(array_slice($a,0,$sa),array_slice($b,0,$sb),$oa,$ob),

          [['t' => self::TYPE_EQUAL,'sa' => $oa + $sa,'ca' => $count,'sb' => $ob + $sb,'cb' => $count]],

          $this->diff(array_slice($a,$sa + $count),array_slice($b,$sb + $count),$oa + $sa + $count,$ob + $sb + $count)

        )

      : ($a || $b ? [[

          't' => ($a && $b) ? self::TYPE_DIFF : ($a ? self::TYPE_DIFF_A : self::TYPE_DIFF_B),

          'sa' => $oa,'ca' => $ca,

          'sb' => $ob,'cb' => $cb

        ]] : []);

  }

  /**

   * Count the number of blocks of a certain type.

   * @param string $type  Diff type (see DIFF_* constants). Set to null to count all "not equal" blocks.

   * @return int

   */

  public function count($type = null){

    $count = 0;

    foreach($this->_diff as $block) if($type === null ? $block['t'] != self::TYPE_EQUAL : $block['t'] == $type) $count++;

    return $count;

  }

  /**

   * Maximum line number.

   * @param bool $chars  Return the number of characters for the largest line number.

   * @return int  Largest line number (or characters).

   */

  public function maxLine($chars = false){

    $lines = max(count($this->_a),count($this->_b));

    return $chars ? ceil(log($lines,10)) : $lines;

  }



  protected function textLine($type,$sa,$ca,$sb,$cb){

    //prefixes: s = start, c = count

    $text = null;

    switch($type){

      case self::TYPE_EQUAL:

        for($i = 0; $i < $ca; $i++) $text .= " " . $this->_a[$sa + $i] . "\n";

        break;

      default:

        for($i = 0; $i < $ca; $i++) $text .= "-" . $this->_a[$sa + $i] . "\n";

        for($i = 0; $i < $cb; $i++) $text .= "+" . $this->_b[$sb + $i] . "\n";

    }

    return $text;

  }

  /**

   * Classic, textual diff output (A above B).

   * @param mixed $head  Header for the text (string). Set to true for a default head, or provide an array with the A and B

   *   description.

   * @return string

   */

  public function asText($head = null){

    //prefixes: c = count, p = prefix, q = suffix (unchanged lines before and after the diff)

    if($head === true) $head = $this->defaultHead;

    if(is_array($head)) $head = "+++ " . array_shift($head) . "\n--- " . array_shift($head);

    $text = $head ? "$head\n" : null;

    $index = 0;

    $count = count($this->_diff);

    while($index < $count) if($this->_diff[$i = $index]['t'] != self::TYPE_EQUAL){

      $blocks = [];

      while(($i < $count) && (

        ($this->_diff[$i]['t'] != self::TYPE_EQUAL) ||

        ($this->_diff[$i]['ca'] <= $this->extra * 2 + $this->extraAllThreshold) //relativly small equal block

      )) $blocks[] = $this->_diff[$i++];

      $pa = min($this->extra,$sa = $blocks[0]['sa']);

      $qa = min($this->extra,count($this->_a) - ($sa + ($ca = array_sum(array_column($blocks,'ca')))));

      $pb = min($this->extra,$sb = $blocks[0]['sb']);

      $qb = min($this->extra,count($this->_b) - ($sb + ($cb = array_sum(array_column($blocks,'cb')))));

      $text .=

        "@@ -" . ($sa - $pa + 1) . "," . ($ca + $pa + $qa) . " +" .  ($sb - $pb + 1) . "," . ($cb + $pb + $qb) . " @@\n" .

        $this->textLine($this->_diff[$index - 1]['t'] ?? self::TYPE_EQUAL,$sa - $pa,$pa,$sb - $pb,$pb);

      foreach($blocks as $block) if(extract($block)) $text .= $this->textLine($t,$sa,$ca,$sb,$cb);

      $text .= $this->textLine($this->_diff[$i]['t'] ?? self::TYPE_EQUAL,$sa + $ca,$qa,$sb + $cb,$qb);

      $index = $i;

    }

    else $index++;

    return $text;

  }

  /**

   * Style block for the HTML diff.

   * @return string

   */

  public function htmlStyle(){

    return "<style>" . str_replace('var(--diff-max-line)',$this->maxLine(true),file_get_contents($this->styleFile)) . "</style>";

  }



  protected function htmlLineBlock($type,$chars,$start,$count){

    if(!$count) return null;

    $prefix = $type == self::TYPE_EQUAL ? null : "<span class='text-$type'>";

    $suffix = $type == self::TYPE_EQUAL ? null : "</span>";

    return $prefix . str_replace("\n","$suffix\n$prefix",htmlentities(implode(array_slice($chars,$start,$count)))) . $suffix;

  }



  protected function htmlLineSpace($chars){

    $html = null;

    foreach($chars as $char){

      $type = 'other';

      switch($char){

        case ' ': $type = 'space'; break;

        case "\t": $type = 'tab'; break;

        case "\r": $type = 'cr'; break;

      }

      $html .= "<span class='space type-$type'>$char</span>";

    }

    return $html;

  }



  protected function htmlLine($index,$type,$sa,$ca,$sb,$cb){

    //prefixes: h = HTML for code, s = start, c = count, y = char array, p = prefix chars, q = suffix chars

    $ha = $hb = null;

    $a = array_slice($this->_a,$sa,$ca);

    $b = array_slice($this->_b,$sb,$cb);

    switch($type){

      case self::TYPE_DIFF:

        if(abs($ca - $cb) <= $this->lineDiffMaxLines){

          $diff = $this->diff($ya = str_split(implode("\n",$a)),$yb = str_split(implode("\n",$b)));

          $same = 0;

          foreach($diff as $block) if($block['t'] == self::TYPE_EQUAL) $same += $block['ca'];

          if($same / max(count($ya),count($yb)) >= $this->lineDiffThreshold) foreach($diff as $block){ //show char diff

            $ha .= $this->htmlLineBlock($block['t'],$ya,$block['sa'],$block['ca']);

            $hb .= $this->htmlLineBlock($block['t'],$yb,$block['sb'],$block['cb']);

          }

        }

        break;

      case self::TYPE_SPACE:

        for($i = 0; $i < $ca; $i++){

          $common = trim($a[$i]);

          list($pa,$qa) = array_map('str_split',explode($common,$a[$i],2));

          list($pb,$qb) = array_map('str_split',explode($common,$b[$i],2));

          while($pa && $pb && (end($pa) == end($pb)) && array_pop($pa)) $common = array_pop($pb) . $common;

          while($qa && $qb && ($qa[0] == $qb[0]) && array_shift($qa)) $common .= array_shift($qb);

          $ha .= ($i ? "\n" : null) . $this->htmlLineSpace($pa) . htmlentities($common) . $this->htmlLineSpace($qa);

          $hb .= ($i ? "\n" : null) . $this->htmlLineSpace($pb) . htmlentities($common) . $this->htmlLineSpace($qb);

        }

        break;

    }

    //prefixes: l = line number column, c = code column

    $tr = "<tr class='block-$index type-$type'>";

    $la = "<td class='line'>" . ($ca ? implode("\n",range($sa + 1,$sa + $ca)) : null) . "</td>";

    $ca = "<td class='code side-a'>" . ($ha ?: htmlentities(implode("\n",$a))) . "\n</td>";

    $lb = "<td class='line'>" . ($cb ? implode("\n",range($sb + 1,$sb + $cb)) : null) . "</td>";

    $cb = "<td class='code side-b'>" . ($hb ?: htmlentities(implode("\n",$b))) . "\n</td>";

    $td = "<td class='line'></td>";

    switch($this->htmlMode){

      case self::HTML_MODE_VERTICAL: return $type == self::TYPE_EQUAL

        ? "$tr$la$lb$ca</tr>"

        : ($a ? "$tr$la$td$ca</tr>" : null) . ($b ? "$tr$td$lb$cb</tr>" : null);

      default: return "$tr$la$ca$lb$cb</tr>";

    }

  }

  /**

   * HTML diff with markup.

   * @param mixed $head  Table head (string; table row with 4 columns: line A, code A, line B, code B). Set to true for a

   *   default head, or provide an array with the column headers (2 = only for code columns, or 4 = all columns).

   * @return string  HTML table.

   */

  public function asHtml($head = null){

    if($head === true) $head = $this->defaultHead;

    if(is_array($head)){

      if(count($head = array_values($head)) < 4) $head = ['#',array_shift($head),'#',array_shift($head)];

      $la = "<th class='line'>{$head[0]}</th>";

      $ca = "<th class='code'>{$head[1]}</th>";

      $lb = "<th class='line'>{$head[2]}</th>";

      $cb = "<th class='code'>{$head[3]}</th>";

      $th = "<th class='line'>";

      switch($this->htmlMode){

        case self::HTML_MODE_VERTICAL: $head = "<tr>$la$th</th>$ca</tr><tr>$th$lb$cb</tr>"; break;

        default: $head = "<tr>$la$ca$lb$cb</tr>";

      }

    }

    $cols = [self::HTML_MODE_VERTICAL => 3][$this->htmlMode] ?? 4;

    $skip = "<tr class='skip'><td colspan='$cols'>{$this->skipTemplate}</td></tr>\n";

    $last = count($this->_diff) - 1;

    $body = null;

    foreach($this->_diff as $index => ['t' => $t,'sa' => $sa,'ca' => $ca,'sb' => $sb,'cb' => $cb]) switch($t){

      case self::TYPE_EQUAL:

        $body .= ($ca <= ($x = $this->extra) * 2 + $this->extraAllThreshold)

          ? $this->htmlLine($index,$t,$sa,$ca,$sb,$cb) //show complete equal block since it is relativly small

          : ($index ? $this->htmlLine($index,$t,$sa,$x,$sb,$x) : null) .

            str_replace('*', $ca - ($index ? $x : 0) - ($index < $last ? $x : 0), $skip) .

            ($index < $last ? $this->htmlLine($index,$t,$sa + $ca - $x,$x,$sb + $cb - $x,$x) : null);

        break;

      case self::TYPE_DIFF: //check for white-space-only diffs inside this block

        $count = 0;

        foreach(($diff = $this->diff(

          array_map('trim',array_slice($this->_a,$sa,$ca)),

          array_map('trim',array_slice($this->_b,$sb,$cb)),

          $sa,$sb

        )) as $block) if($block['t'] == self::TYPE_EQUAL) $count += $block['ca'];

        if($count / max($ca,$cb) > $this->whiteSpaceThreshold){ //show white-space blocks differently

          foreach($diff as $sub => ['t' => $t,'sa' => $sa,'ca' => $ca,'sb' => $sb,'cb' => $cb])

            $body .= $this->htmlLine($index . '-' . $sub,$t == self::TYPE_EQUAL ? self::TYPE_SPACE : $t,$sa,$ca,$sb,$cb);

          break;

        } //else

      default:

        $body .= $this->htmlLine($index,$t,$sa,$ca,$sb,$cb);

    }

    return "<table class='diff {$this->htmlMode}'><thead>$head</thead><tbody>$body</tbody></table>";

  }



  public function __toString(){

    return $this->asText() ?: '';

  }



}