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

/**
 * コミットの履歴を辿る（log、到達可能なオブジェクト、共通の祖先）
 */
final class Walk {
  /** @var array ID => [親の配列, コミット時刻] */
  private array $info = [];
  /** @var array クライアントのshallowのコミット（親を辿らない） */
  private array $grafts = [];

  public function __construct(private Repository $repo) {}

  /** shallowのコミット（そこで履歴が終わるとする） */
  public function setGrafts(array $ids): void {
    $this->grafts = array_fill_keys($ids, true);
  }

  /** コミットの親と時刻（キャッシュ） */
  private function node(string $id): array {
    if (!isset($this->info[$id])) {
      $c = $this->repo->commit($id);
      $this->info[$id] = [isset($this->grafts[$id]) ? [] : $c->parents, $c->committer?->time ?? 0];
    }
    return $this->info[$id];
  }

  /**
   * 履歴（新しい順、git logと同じ）
   *
   * @param array $from  リビジョン
   * @param array $opt  path、limit、skip、not、firstParent
   */
  public function log(array $from, array $opt = []): \Generator {
    $path = trim((string)($opt['path'] ?? ''), '/');
    $limit = isset($opt['limit']) ? (int)$opt['limit'] : PHP_INT_MAX;
    $skip = (int)($opt['skip'] ?? 0);
    $firstParent = !empty($opt['firstParent']);
    $hide = [];
    if (!empty($opt['not'])) {
      $nots = [];
      foreach ((array)$opt['not'] as $r) {
        $id = $this->repo->resolve($r);
        $id = $id === null ? null : $this->repo->peel($id, 'commit');
        if ($id !== null) $nots[] = $id;
      }
      if (!empty($nots)) $hide = array_fill_keys($this->ancestors($nots), true);
    }
    $queue = new \SplPriorityQueue();
    $seq = PHP_INT_MAX;
    $seen = [];
    foreach ($from as $r) {
      $id = $this->repo->resolve($r);
      $id = $id === null ? null : $this->repo->peel($id, 'commit');
      if ($id === null) throw new GitException("リビジョンが有りません：{$r}");
      if (isset($seen[$id]) || isset($hide[$id])) continue;
      $seen[$id] = true;
      $queue->insert($id, [$this->node($id)[1], $seq--]);
    }
    $n = 0;
    while (!$queue->isEmpty() && $limit > 0) {
      $id = $queue->extract();
      $c = $this->repo->commit($id);
      $parents = $firstParent ? array_slice($c->parents, 0, 1) : $c->parents;
      $show = true;
      if ($path !== '') {
        // パスが親と同じなら表示しない（同じ親だけを辿る）
        $mine = $this->repo->entry($c->tree, $path)[2] ?? null;
        $same = null;
        foreach ($parents as $p) {
          if ($this->repo->objects->exists($p) && ($this->repo->entry($p, $path)[2] ?? null) === $mine) {
            $same = $p;
            break;
          }
        }
        if ($same !== null) {
          $show = false;
          $parents = [$same];
        } else if (empty($parents) && $mine === null) {
          $show = false;
        }
      }
      foreach ($parents as $p) {
        if (isset($seen[$p]) || isset($hide[$p]) || !$this->repo->objects->exists($p)) continue;
        $seen[$p] = true;
        $queue->insert($p, [$this->node($p)[1], $seq--]);
      }
      if (!$show) continue;
      if ($n++ < $skip) continue;
      $limit--;
      yield $c;
    }
  }

  /** 全部の祖先（自分を含む） */
  public function ancestors(array $ids): array {
    $seen = [];
    $stack = $ids;
    while (!empty($stack)) {
      $id = array_pop($stack);
      if (isset($seen[$id]) || !$this->repo->objects->exists($id)) continue;
      $seen[$id] = true;
      foreach ($this->node($id)[0] as $p) if (!isset($seen[$p])) $stack[] = $p;
    }
    return array_keys($seen);
  }

  /** aがbの祖先か（同じも含む） */
  public function isAncestor(string $a, string $b): bool {
    if ($a === $b) return true;
    $target = $this->node($a)[1];
    $seen = [];
    $stack = [$b];
    while (!empty($stack)) {
      $id = array_pop($stack);
      if ($id === $a) return true;
      if (isset($seen[$id]) || !$this->repo->objects->exists($id)) continue;
      $seen[$id] = true;
      [$parents, $time] = $this->node($id);
      // 時刻が十分古ければ辿らない（1日のずれを許す）
      if ($time < $target - 86400) continue;
      foreach ($parents as $p) $stack[] = $p;
    }
    return false;
  }

  /** 共通の祖先（一番新しい物、無ければnull） */
  public function mergeBase(string $a, string $b): ?string {
    $anc = array_fill_keys($this->ancestors([$a]), true);
    $best = null;
    foreach ($this->ancestors([$b]) as $id) {
      if (!isset($anc[$id])) continue;
      if ($best === null || $this->isAncestor($best, $id)) $best = $id;
    }
    return $best;
  }

  /**
   * wantsから到達出来て、havesから到達出来ないコミット
   *
   * @return array  [コミットの配列（新しい順）, 境界のコミット（havesから到達出来る親）]
   */
  public function commitsBetween(array $wants, array $haves): array {
    $flag = [];
    $queue = new \SplPriorityQueue();
    $seq = PHP_INT_MAX;
    $interesting = 0;
    foreach ($haves as $id) {
      if (isset($flag[$id]) || !$this->repo->objects->exists($id)) continue;
      $flag[$id] = 'u';
      $queue->insert($id, [$this->node($id)[1], $seq--]);
    }
    foreach ($wants as $id) {
      if (isset($flag[$id])) continue;
      $flag[$id] = 'i';
      $interesting++;
      $queue->insert($id, [$this->node($id)[1], $seq--]);
    }
    $order = [];
    $slop = 5;
    while (!$queue->isEmpty()) {
      if ($interesting === 0 && --$slop < 0) break;
      $id = $queue->extract();
      $f = $flag[$id];
      if ($f === 'i') {
        $interesting--;
        $order[] = $id;
      }
      foreach ($this->node($id)[0] as $p) {
        if (!isset($flag[$p])) {
          if (!$this->repo->objects->exists($p)) continue;
          $flag[$p] = $f;
          if ($f === 'i') $interesting++;
          $queue->insert($p, [$this->node($p)[1], $seq--]);
        } else if ($f === 'u' && $flag[$p] === 'i') {
          // 既に見たコミットも除く（時刻がずれている場合）
          $this->markUninteresting($p, $flag, $interesting);
        }
      }
    }
    $commits = array_values(array_filter($order, fn($id) => $flag[$id] === 'i'));
    $boundary = [];
    foreach ($commits as $id) foreach ($this->node($id)[0] as $p) if (($flag[$p] ?? null) === 'u') $boundary[$p] = true;
    return [$commits, array_keys($boundary)];
  }

  private function markUninteresting(string $id, array &$flag, int &$interesting): void {
    $stack = [$id];
    while (!empty($stack)) {
      $c = array_pop($stack);
      if (($flag[$c] ?? null) !== 'i') continue;
      $flag[$c] = 'u';
      $interesting--;
      if (isset($this->info[$c])) foreach ($this->info[$c][0] as $p) $stack[] = $p;
    }
    if ($interesting < 0) $interesting = 0;
  }

  /**
   * 送るオブジェクト（wantsから到達出来て、havesから到達出来ない物）
   *
   * @param array $wants  欲しいID（コミット、タグ等）
   * @param array $haves  相手が持っているコミット
   * @param array|null $commits  送るコミット（深さの制限等で決めた場合）
   * @return array  ID => 種類（コミット、ツリー・ブロブ、タグの順）
   */
  public function objects(array $wants, array $haves, ?array $commits = null, ?array $boundary = null): array {
    $tags = [];
    $wantCommits = [];
    $extra = [];
    foreach ($wants as $id) {
      $info = $this->repo->objects->info($id);
      if ($info === null) throw new GitException("オブジェクトが有りません：{$id}");
      while ($info[0] === 'tag') {
        $tags[$id] = 'tag';
        $id = $this->repo->tag($id)->object;
        $info = $this->repo->objects->info($id);
        if ($info === null) throw new GitException("オブジェクトが有りません：{$id}");
      }
      if ($info[0] === 'commit') $wantCommits[] = $id;
      else $extra[$id] = $info[0];
    }
    if ($commits === null) [$commits, $boundary] = $this->commitsBetween($wantCommits, $haves);
    // 境界のコミットのツリーは相手が持っている
    $have = [];
    foreach ($boundary ?? [] as $b) $this->markTree($this->repo->commit($b)->tree, $have);
    $out = [];
    foreach ($commits as $id) $out[$id] = 'commit';
    foreach ($commits as $id) $this->addTree($this->repo->commit($id)->tree, $have, $out);
    foreach ($extra as $id => $type) {
      if ($type === 'tree') $this->addTree($id, $have, $out);
      else if (!isset($have[$id])) $out[$id] = $type;
    }
    return $out + $tags;
  }

  private function markTree(string $tree, array &$have): void {
    if (isset($have[$tree])) return;
    $have[$tree] = true;
    foreach ($this->repo->tree($tree)->entries as [$mode, , $id]) {
      if ($mode === Tree::DIR) $this->markTree($id, $have);
      else if ($mode !== Tree::SUBMODULE) $have[$id] = true;
    }
  }

  private function addTree(string $tree, array &$have, array &$out): void {
    if (isset($have[$tree]) || isset($out[$tree])) return;
    $out[$tree] = 'tree';
    foreach ($this->repo->tree($tree)->entries as [$mode, , $id]) {
      if ($mode === Tree::DIR) $this->addTree($id, $have, $out);
      else if ($mode !== Tree::SUBMODULE && !isset($have[$id])) $out[$id] = 'blob';
    }
  }

  /**
   * 深さを制限したコミット（git clone --depth）
   *
   * @return array  [コミットの配列, 新しいshallowのコミット]
   */
  public function deepen(array $wants, int $depth): array {
    $level = [];
    $queue = [];
    foreach ($wants as $id) {
      $level[$id] = 1;
      $queue[] = $id;
    }
    $shallow = [];
    for ($i = 0; $i < count($queue); $i++) {
      $id = $queue[$i];
      $parents = $this->node($id)[0];
      if ($level[$id] >= $depth) {
        if (!empty($parents)) $shallow[$id] = true;
        continue;
      }
      foreach ($parents as $p) {
        if (isset($level[$p]) || !$this->repo->objects->exists($p)) continue;
        $level[$p] = $level[$id] + 1;
        $queue[] = $p;
      }
    }
    return [$queue, array_keys($shallow)];
  }
}