<?php
/*************************************************************
# 076 License

Copyright (c) テクニカル諏訪子

Permission is hereby granted to any person obtaining a copy of the software
Little Beast (the "Software") to use, modify, merge, copy, publish, distribute,
sublicense, and/or sell copies of the Software, subject to the following conditions:

    1. **Origin Attribution**:
       - You must not misrepresent the origin of the Software; you must not claim
         you created the original Software.
       - If the Software is used in a product, you must either:
         a. Provide clear attribution in the product's documentation, user interface,
            or other visible areas, **OR**
         b. Pay the original developers a fee they specify in writing.
    2. **Usage Restriction**:
       - The Software, or any derivative works, dependencies, or libraries
         incorporating it, must not be used for censorship or to suppress freedom of
         speech, expression, or creativity. Prohibited uses include, but are not
         limited to:
         - Censorship of so-called "hate speech", visuals, non-mainstream opinions,
           ideas, or objective reality.
         - Tools or systems designed to restrict access to information or
           artistic works.
    3. **Notice Preservation**:
       - This license and the above copyright notice must remain intact in all copies
         of the source code.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
namespace Std\Lib\Git;

/**
 * 差分（ツリーの変更、行の差分、git diffの形式）
 */
final class Diff {
  /** これより大きいファイルは行の差分を出さない */
  public const MAX_BYTES = 2097152;
  /** 編集距離の上限（超えたら全部の置き換えとする） */
  private const MAX_D = 3000;

  /**
   * 2つのツリーの違い
   *
   * @param string|null $a  元のツリー（nullなら空）
   * @param string|null $b  新しいツリー（nullなら空）
   * @param bool $renames  同じ内容の削除と追加を名前の変更（R）にする
   * @return array  ['status' => A・D・M・T・R, 'old' => [mode, path, id]|null, 'new' => [mode, path, id]|null]（パスの順）
   */
  public static function trees(Repository $repo, ?string $a, ?string $b, bool $renames = true): array {
    $out = [];
    self::walk($repo, $a, $b, '', $out);
    if ($renames) {
      $added = [];
      foreach ($out as $i => $c) if ($c['status'] === 'A') $added[$c['new'][2]][] = $i;
      foreach ($out as $i => $c) {
        if ($c['status'] !== 'D' || empty($added[$c['old'][2]])) continue;
        $j = array_shift($added[$c['old'][2]]);
        $out[$j] = ['status' => 'R', 'old' => $c['old'], 'new' => $out[$j]['new']];
        unset($out[$i]);
      }
    }
    $out = array_values($out);
    usort($out, fn($x, $y) => strcmp(($x['new'] ?? $x['old'])[1], ($y['new'] ?? $y['old'])[1]));
    return $out;
  }

  private static function walk(Repository $repo, ?string $a, ?string $b, string $prefix, array &$out): void {
    if ($a === $b) return;
    $ea = [];
    $eb = [];
    foreach ($a !== null ? $repo->tree($a)->entries : [] as $e) $ea[$e[1]] = $e;
    foreach ($b !== null ? $repo->tree($b)->entries : [] as $e) $eb[$e[1]] = $e;
    $names = array_unique(array_merge(array_keys($ea), array_keys($eb)));
    sort($names, SORT_STRING);
    foreach ($names as $name) {
      $x = $ea[$name] ?? null;
      $y = $eb[$name] ?? null;
      $path = $prefix.$name;
      $xd = $x !== null && $x[0] === Tree::DIR;
      $yd = $y !== null && $y[0] === Tree::DIR;
      if ($xd || $yd) {
        self::walk($repo, $xd ? $x[2] : null, $yd ? $y[2] : null, $path.'/', $out);
        if ($x !== null && !$xd) $out[] = ['status' => 'D', 'old' => [$x[0], $path, $x[2]], 'new' => null];
        if ($y !== null && !$yd) $out[] = ['status' => 'A', 'old' => null, 'new' => [$y[0], $path, $y[2]]];
        continue;
      }
      if ($x === null) $out[] = ['status' => 'A', 'old' => null, 'new' => [$y[0], $path, $y[2]]];
      else if ($y === null) $out[] = ['status' => 'D', 'old' => [$x[0], $path, $x[2]], 'new' => null];
      else if ($x[2] !== $y[2] || $x[0] !== $y[0]) {
        $type = fn($m) => $m === Tree::LINK ? 'l' : ($m === Tree::SUBMODULE ? 's' : 'f');
        $out[] = ['status' => $type($x[0]) === $type($y[0]) ? 'M' : 'T', 'old' => [$x[0], $path, $x[2]], 'new' => [$y[0], $path, $y[2]]];
      }
    }
  }

  /** バイナリか（最初の8000バイトにNULが有る） */
  public static function isBinary(string $s): bool {
    return str_contains(substr($s, 0, 8000), "\0");
  }

  /** 行に分ける（改行は含まない） */
  public static function split(string $s): array {
    if ($s === '') return [];
    $lines = explode("\n", $s);
    if (end($lines) === '') array_pop($lines);
    return $lines;
  }

  /**
   * 行の対応（Myersのアルゴリズム）
   *
   * @return array  [元の行の番号, 新しい行の番号]の配列（同じ行、0から）
   */
  public static function match(array $a, array $b): array {
    $n = count($a);
    $m = count($b);
    // 前と後ろの同じ部分
    $pre = 0;
    while ($pre < $n && $pre < $m && $a[$pre] === $b[$pre]) $pre++;
    $suf = 0;
    while ($suf < $n - $pre && $suf < $m - $pre && $a[$n - 1 - $suf] === $b[$m - 1 - $suf]) $suf++;
    $pairs = [];
    for ($i = 0; $i < $pre; $i++) $pairs[] = [$i, $i];
    $A = array_slice($a, $pre, $n - $pre - $suf);
    $B = array_slice($b, $pre, $m - $pre - $suf);
    foreach (self::myers($A, $B) as [$i, $j]) $pairs[] = [$i + $pre, $j + $pre];
    for ($k = $suf; $k > 0; $k--) $pairs[] = [$n - $k, $m - $k];
    return $pairs;
  }

  private static function myers(array $a, array $b): array {
    if ($a === [] || $b === []) return [];
    // 相手に無い行は必ず変更なので除く（xdiffと同じ）。行は番号にする
    $ids = [];
    $inB = [];
    foreach ($b as $l) $inB[$l] = true;
    $inA = [];
    foreach ($a as $l) $inA[$l] = true;
    $A = [];
    $mapA = [];
    foreach ($a as $i => $l) if (isset($inB[$l])) {
      $A[] = $ids[$l] ??= count($ids);
      $mapA[] = $i;
    }
    $B = [];
    $mapB = [];
    foreach ($b as $j => $l) if (isset($inA[$l])) {
      $B[] = $ids[$l] ??= count($ids);
      $mapB[] = $j;
    }
    $n = count($A);
    $m = count($B);
    if ($n === 0 || $m === 0) return [];
    // 各ステップのVは詰めた文字列で持つ（メモリを節約）
    $v = [1 => 0];
    $trace = [];
    $found = false;
    $limit = min($n + $m, self::MAX_D);
    for ($d = 0; $d <= $limit; $d++) {
      $trace[] = pack('N*', ...array_map(fn($k) => ($v[$k] ?? 0) + 1, range(-$d - 1, $d + 1)));
      for ($k = -$d; $k <= $d; $k += 2) {
        if ($k === -$d || ($k !== $d && ($v[$k - 1] ?? -1) < ($v[$k + 1] ?? -1))) $x = $v[$k + 1] ?? 0;
        else $x = ($v[$k - 1] ?? 0) + 1;
        $y = $x - $k;
        while ($x < $n && $y < $m && $A[$x] === $B[$y]) {
          $x++;
          $y++;
        }
        $v[$k] = $x;
        if ($x >= $n && $y >= $m) {
          $found = true;
          break 2;
        }
      }
    }
    if (!$found) return [];
    $get = function(int $d, int $k) use (&$trace): int {
      // k = -d-1 … d+1（0は「無い」）
      $i = $k + $d + 1;
      if ($i < 0 || $i > 2 * $d + 2) return -1;
      return unpack('N', $trace[$d], $i * 4)[1] - 1;
    };
    $pairs = [];
    $x = $n;
    $y = $m;
    for ($d = count($trace) - 1; $d >= 0; $d--) {
      $k = $x - $y;
      $down = $k === -$d || ($k !== $d && $get($d, $k - 1) < $get($d, $k + 1));
      $pk = $down ? $k + 1 : $k - 1;
      $px = max(0, $get($d, $pk));
      $py = $px - $pk;
      while ($x > $px && $y > $py) {
        $x--;
        $y--;
        $pairs[] = [$mapA[$x], $mapB[$y]];
      }
      if ($d > 0) {
        $x = $px;
        $y = $py;
      }
    }
    return array_reverse($pairs);
  }

  /**
   * 行の差分のハンク
   *
   * @return array  ['oldStart', 'oldLines', 'newStart', 'newLines', 'lines' => [[' '|'-'|'+', 行]]]（番号は1から）
   */
  public static function hunks(array $a, array $b, int $context = 3): array {
    // 編集の列（' '、'-'、'+'）
    $ops = [];
    $i = 0;
    $j = 0;
    foreach (array_merge(self::match($a, $b), [[count($a), count($b)]]) as [$x, $y]) {
      while ($i < $x) $ops[] = ['-', $i++, null];
      while ($j < $y) $ops[] = ['+', null, $j++];
      if ($x < count($a)) $ops[] = [' ', $i++, $j++];
    }
    $hunks = [];
    $n = count($ops);
    $k = 0;
    while ($k < $n) {
      while ($k < $n && $ops[$k][0] === ' ') $k++;
      if ($k >= $n) break;
      $start = max(0, $k - $context);
      // 変更の間の同じ行が2*context以下なら同じハンク
      $end = $k;
      while (true) {
        while ($end < $n && $ops[$end][0] !== ' ') $end++;
        $same = $end;
        while ($same < $n && $ops[$same][0] === ' ') $same++;
        if ($same < $n && $same - $end <= 2 * $context) {
          $end = $same;
          continue;
        }
        $end = min($n, $end + $context);
        break;
      }
      $h = ['oldStart' => 0, 'oldLines' => 0, 'newStart' => 0, 'newLines' => 0, 'lines' => []];
      $oldStart = null;
      $newStart = null;
      for ($p = $start; $p < $end; $p++) {
        [$op, $x, $y] = $ops[$p];
        if ($x !== null) {
          $oldStart ??= $x;
          $h['oldLines']++;
        }
        if ($y !== null) {
          $newStart ??= $y;
          $h['newLines']++;
        }
        $h['lines'][] = [$op, $op === '+' ? $b[$y] : $a[$x]];
      }
      // 行が無い側の番号はgitと同じ（直前の行）
      $h['oldStart'] = $oldStart !== null ? $oldStart + 1 : self::before($ops, $start, 1);
      $h['newStart'] = $newStart !== null ? $newStart + 1 : self::before($ops, $start, 2);
      $hunks[] = $h;
      $k = $end;
    }
    return $hunks;
  }

  private static function before(array $ops, int $pos, int $side): int {
    for ($p = $pos - 1; $p >= 0; $p--) if ($ops[$p][$side] !== null) return $ops[$p][$side] + 1;
    return 0;
  }

  /**
   * git diffの形式
   *
   * @param string|null $a  元のコミット・ツリー（nullなら空）
   * @param string|null $b  新しいコミット・ツリー
   */
  public static function unified(Repository $repo, ?string $a, ?string $b, int $context = 3, bool $quotePath = true): string {
    $q = fn(string $prefix, string $path) => self::quote($prefix.$path, $quotePath);
    $ta = $a === null ? null : $repo->treeOf($a);
    $tb = $b === null ? null : $repo->treeOf($b);
    $out = '';
    $short = fn(?string $id) => substr($id ?? $repo->zeroId(), 0, 7);
    foreach (self::trees($repo, $ta, $tb) as $c) {
      [$om, $op, $oid] = $c['old'] ?? [null, null, null];
      [$nm, $np, $nid] = $c['new'] ?? [null, null, null];
      $pa = $op ?? $np;
      $pb = $np ?? $op;
      $out .= 'diff --git '.$q('a/', $pa).' '.$q('b/', $pb)."\n";
      if ($c['status'] === 'A') $out .= "new file mode {$nm}\n";
      if ($c['status'] === 'D') $out .= "deleted file mode {$om}\n";
      if ($c['status'] === 'T' || ($c['status'] === 'M' && $om !== $nm)) $out .= "old mode {$om}\nnew mode {$nm}\n";
      if ($c['status'] === 'R') $out .= "similarity index 100%\nrename from ".self::quote($op, $quotePath)."\nrename to ".self::quote($np, $quotePath)."\n";
      if ($c['status'] === 'R' || $oid === $nid) continue;
      $out .= 'index '.$short($oid).'..'.$short($nid).($c['status'] === 'M' && $om === $nm ? " {$nm}" : '')."\n";
      $old = $oid !== null && $om !== Tree::SUBMODULE ? $repo->blob($oid) : ($om === Tree::SUBMODULE ? "Subproject commit {$oid}\n" : '');
      $new = $nid !== null && $nm !== Tree::SUBMODULE ? $repo->blob($nid) : ($nm === Tree::SUBMODULE ? "Subproject commit {$nid}\n" : '');
      if (self::isBinary($old) || self::isBinary($new)) {
        $out .= 'Binary files '.($oid !== null ? $q('a/', $pa) : '/dev/null').' and '.($nid !== null ? $q('b/', $pb) : '/dev/null')." differ\n";
        continue;
      }
      $out .= '--- '.($oid !== null ? $q('a/', $pa) : '/dev/null')."\n".'+++ '.($nid !== null ? $q('b/', $pb) : '/dev/null')."\n";
      $out .= self::format($old, $new, $context);
    }
    return $out;
  }

  /**
   * パスの引用（gitのcore.quotePath。制御文字・「"」・「\」と、$nonAsciiならASCII以外を8進数に）
   */
  public static function quote(string $path, bool $nonAscii = true): string {
    if (!preg_match($nonAscii ? '/[\x00-\x1f"\\\\\x7f-\xff]/' : '/[\x00-\x1f"\\\\\x7f]/', $path)) return $path;
    $out = '"';
    $map = ["\x07" => '\a', "\x08" => '\b', "\t" => '\t', "\n" => '\n', "\x0b" => '\v', "\x0c" => '\f', "\r" => '\r', '"' => '\"', '\\' => '\\\\'];
    for ($i = 0, $n = strlen($path); $i < $n; $i++) {
      $c = $path[$i];
      $o = ord($c);
      if (isset($map[$c])) $out .= $map[$c];
      else if ($o < 0x20 || $o === 0x7f || ($nonAscii && $o >= 0x80)) $out .= sprintf('\\%03o', $o);
      else $out .= $c;
    }
    return $out.'"';
  }

  /** 2つの文字列の差分（「@@」から） */
  public static function format(string $old, string $new, int $context = 3): string {
    $a = self::split($old);
    $b = self::split($new);
    $noNlA = $old !== '' && !str_ends_with($old, "\n");
    $noNlB = $new !== '' && !str_ends_with($new, "\n");
    // 最後の行の改行の有無が違えば別の行
    if ($noNlA && $noNlB === false && $a !== []) $a[count($a) - 1] .= "\0";
    if ($noNlB && $noNlA === false && $b !== []) $b[count($b) - 1] .= "\0";
    $out = '';
    foreach (self::hunks($a, $b, $context) as $h) {
      $range = fn($s, $l) => $l === 1 ? "{$s}" : "{$s},{$l}";
      // 関数の名前（gitの既定：英字・「_」・「$」で始まる前の行）
      $func = '';
      for ($p = $h['oldStart'] - 2; $p >= 0; $p--) {
        if (preg_match('/^[A-Za-z_$]/', $a[$p])) {
          $func = ' '.rtrim(substr(rtrim($a[$p], "\0"), 0, 80));
          break;
        }
      }
      $out .= '@@ -'.$range($h['oldStart'], $h['oldLines']).' +'.$range($h['newStart'], $h['newLines'])." @@{$func}\n";
      $ia = 0;
      $ib = 0;
      foreach ($h['lines'] as [$op, $line]) {
        $out .= $op.rtrim($line, "\0")."\n";
        $lastA = $op !== '+' && $h['oldStart'] - 1 + $ia++ === count($a) - 1;
        $lastB = $op !== '-' && $h['newStart'] - 1 + $ib++ === count($b) - 1;
        if (($op === '-' && $lastA && $noNlA) || ($op === '+' && $lastB && $noNlB) || ($op === ' ' && (($lastA && $noNlA) || ($lastB && $noNlB)))) {
          $out .= "\\ No newline at end of file\n";
        }
      }
    }
    return $out;
  }
}