<?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;

/**
 * 3方向のマージ（行とツリー）
 *
 * 行：共通の祖先からの両方の変更を合わせる（diff3）。重なるか隣り合う変更が違えばコンフリクト（gitと同じ）。
 * ツリー：片方だけの変更はそのまま、両方が変えたファイルは行でマージする。
 * 削除と変更、ファイルとディレクトリ、バイナリ、シンボリックリンク等の両方の変更はコンフリクト。
 */
final class Merge {
  /**
   * 行のマージ（行は改行を含む）
   *
   * @return array  lines（コンフリクトはマーカー付き）、conflicts（コンフリクトの数）
   */
  public static function lines(array $base, array $ours, array $theirs, string $ourName = 'ours', string $theirName = 'theirs'): array {
    $changes = [];
    foreach (self::changes($base, $ours) as $c) $changes[] = $c + [4 => 'o'];
    foreach (self::changes($base, $theirs) as $c) $changes[] = $c + [4 => 't'];
    usort($changes, fn($a, $b) => [$a[0], $a[1]] <=> [$b[0], $b[1]]);
    $out = [];
    $conflicts = 0;
    $pos = 0;
    $n = count($changes);
    for ($i = 0; $i < $n;) {
      // 重なる・隣り合う変更をまとめる
      $group = [$changes[$i]];
      $start = $changes[$i][0];
      $end = $changes[$i][1];
      for ($i++; $i < $n && $changes[$i][0] <= $end; $i++) {
        $group[] = $changes[$i];
        $end = max($end, $changes[$i][1]);
      }
      for ($k = $pos; $k < $start; $k++) $out[] = $base[$k];
      $o = array_values(array_filter($group, fn($c) => $c[4] === 'o'));
      $t = array_values(array_filter($group, fn($c) => $c[4] === 't'));
      if (empty($t)) {
        array_push($out, ...self::region($o, $start, $end, $ours));
      } else if (empty($o)) {
        array_push($out, ...self::region($t, $start, $end, $theirs));
      } else {
        $a = self::region($o, $start, $end, $ours);
        $b = self::region($t, $start, $end, $theirs);
        if ($a === $b) {
          array_push($out, ...$a);
        } else {
          $conflicts++;
          $eol = fn(array $l) => $l !== [] && !str_ends_with((string)end($l), "\n") ? ["\n"] : [];
          array_push($out, "<<<<<<< {$ourName}\n", ...$a, ...$eol($a));
          array_push($out, "=======\n", ...$b, ...$eol($b));
          $out[] = ">>>>>>> {$theirName}\n";
        }
      }
      $pos = $end;
    }
    for ($k = $pos; $k < count($base); $k++) $out[] = $base[$k];
    return ['lines' => $out, 'conflicts' => $conflicts];
  }

  /** 文字列を行に分ける（改行を含む） */
  public static function split(string $s): array {
    return $s === '' ? [] : preg_split('/(?<=\n)/', $s, -1, PREG_SPLIT_NO_EMPTY);
  }

  /**
   * ファイルの内容のマージ
   *
   * @return string|null  コンフリクトやバイナリならnull
   */
  public static function text(string $base, string $ours, string $theirs): ?string {
    if ($ours === $theirs) return $ours;
    if ($base === $ours) return $theirs;
    if ($base === $theirs) return $ours;
    if (Diff::isBinary($base) || Diff::isBinary($ours) || Diff::isBinary($theirs)) return null;
    if (strlen($base) + strlen($ours) + strlen($theirs) > 3 * Diff::MAX_BYTES) return null;
    $r = self::lines(self::split($base), self::split($ours), self::split($theirs));
    return $r['conflicts'] === 0 ? implode('', $r['lines']) : null;
  }

  /**
   * ツリーのマージ
   *
   * @param string|null $base  共通の祖先のツリー（無ければnull）
   * @return array  tree（新しいツリーのID、コンフリクトが有ればnull）、conflicts（パスの配列）
   */
  public static function trees(Repository $repo, ?string $base, string $ours, string $theirs): array {
    $conflicts = [];
    $tree = self::mergeTree($repo, $base, $ours, $theirs, '', $conflicts);
    return ['tree' => empty($conflicts) ? ($tree ?? $repo->writeTree([])) : null, 'conflicts' => $conflicts];
  }

  /**
   * コミットを他のコミットの上に当てる（cherry-pick）
   *
   * @return string|null  新しいツリー、コンフリクトならnull
   */
  public static function pick(Repository $repo, string $commit, string $onto): ?string {
    $c = $repo->commit($commit);
    $parent = $c->parents[0] ?? null;
    $r = self::trees($repo, $parent !== null ? $repo->commit($parent)->tree : null, $repo->commit($onto)->tree, $c->tree);
    return $r['tree'];
  }

  //////// 内部

  /** 変更（[元の始め, 元の終わり, 新しい始め, 新しい終わり]、終わりは含まない） */
  private static function changes(array $a, array $b): array {
    $out = [];
    $pi = 0;
    $pj = 0;
    foreach (array_merge(Diff::match($a, $b), [[count($a), count($b)]]) as [$i, $j]) {
      if ($i > $pi || $j > $pj) $out[] = [$pi, $i, $pj, $j];
      $pi = $i + 1;
      $pj = $j + 1;
    }
    return $out;
  }

  /** 元の[start, end)に当たる片方の行 */
  private static function region(array $changes, int $start, int $end, array $lines): array {
    $first = $changes[0];
    $last = end($changes);
    $from = $first[2] - ($first[0] - $start);
    $to = $last[3] + ($end - $last[1]);
    return array_slice($lines, $from, $to - $from);
  }

  /** @return string|null  空ならnull */
  private static function mergeTree(Repository $repo, ?string $base, ?string $ours, ?string $theirs, string $prefix, array &$conflicts): ?string {
    if ($ours === $theirs) return $ours;
    if ($base === $ours) return $theirs;
    if ($base === $theirs) return $ours;
    $entries = fn(?string $t) => $t === null ? [] : array_column($repo->tree($t)->entries, null, 1);
    $b = $entries($base);
    $o = $entries($ours);
    $t = $entries($theirs);
    $out = [];
    foreach (array_unique(array_merge(array_keys($b), array_keys($o), array_keys($t))) as $name) {
      $name = (string)$name;
      $be = $b[$name] ?? null;
      $oe = $o[$name] ?? null;
      $te = $t[$name] ?? null;
      $path = $prefix.$name;
      if ($oe === $te) $e = $oe;
      else if ($be === $oe) $e = $te;
      else if ($be === $te) $e = $oe;
      else $e = self::mergeEntry($repo, $be, $oe, $te, $path, $conflicts);
      if ($e !== null) $out[] = $e;
    }
    return empty($out) ? null : $repo->writeTree($out);
  }

  /** 両方が変えたエントリー（[mode, name, id]又はnull） */
  private static function mergeEntry(Repository $repo, ?array $be, ?array $oe, ?array $te, string $path, array &$conflicts): ?array {
    $isDir = fn(?array $e) => $e !== null && $e[0] === Tree::DIR;
    $isFile = fn(?array $e) => $e !== null && ($e[0] === Tree::FILE || $e[0] === Tree::EXEC);
    // 両方ディレクトリ
    if ($isDir($oe) && $isDir($te)) {
      $id = self::mergeTree($repo, $isDir($be) ? $be[2] : null, $oe[2], $te[2], $path.'/', $conflicts);
      return $id === null ? null : [Tree::DIR, $oe[1], $id];
    }
    // 両方普通のファイル（追加・追加も）
    if ($isFile($oe) && $isFile($te) && ($be === null || $isFile($be))) {
      $text = self::text($be !== null ? $repo->blob($be[2]) : '', $repo->blob($oe[2]), $repo->blob($te[2]));
      if ($text === null) {
        $conflicts[] = $path;
        return $oe;
      }
      // 実行権限は変えた方
      $mode = $be !== null && $oe[0] === $be[0] ? $te[0] : $oe[0];
      if ($be === null && $oe[0] !== $te[0]) {
        $conflicts[] = $path;
        return $oe;
      }
      return [$mode, $oe[1], $repo->writeBlob($text)];
    }
    // 削除と変更、種類の違い等
    $conflicts[] = $path;
    return $oe ?? $te;
  }
}