| 1 | <?php |
| 2 | /************************************************************* |
| 3 | # 076 License |
| 4 | |
| 5 | Copyright (c) テクニカル諏訪子 |
| 6 | |
| 7 | Permission is hereby granted to any person obtaining a copy of the software |
| 8 | Little Beast (the "Software") to use, modify, merge, copy, publish, distribute, |
| 9 | sublicense, and/or sell copies of the Software, subject to the following conditions: |
| 10 | |
| 11 | 1. **Origin Attribution**: |
| 12 | - You must not misrepresent the origin of the Software; you must not claim |
| 13 | you created the original Software. |
| 14 | - If the Software is used in a product, you must either: |
| 15 | a. Provide clear attribution in the product's documentation, user interface, |
| 16 | or other visible areas, **OR** |
| 17 | b. Pay the original developers a fee they specify in writing. |
| 18 | 2. **Usage Restriction**: |
| 19 | - The Software, or any derivative works, dependencies, or libraries |
| 20 | incorporating it, must not be used for censorship or to suppress freedom of |
| 21 | speech, expression, or creativity. Prohibited uses include, but are not |
| 22 | limited to: |
| 23 | - Censorship of so-called "hate speech", visuals, non-mainstream opinions, |
| 24 | ideas, or objective reality. |
| 25 | - Tools or systems designed to restrict access to information or |
| 26 | artistic works. |
| 27 | 3. **Notice Preservation**: |
| 28 | - This license and the above copyright notice must remain intact in all copies |
| 29 | of the source code. |
| 30 | |
| 31 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, |
| 32 | INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A |
| 33 | PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
| 34 | HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF |
| 35 | CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE |
| 36 | OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 37 | */ |
| 38 | namespace Std\Lib\Git; |
| 39 | |
| 40 | /** |
| 41 | * コミットの履歴を辿る（log、到達可能なオブジェクト、共通の祖先） |
| 42 | */ |
| 43 | final class Walk { |
| 44 | /** @var array ID => [親の配列, コミット時刻] */ |
| 45 | private array $info = []; |
| 46 | /** @var array クライアントのshallowのコミット（親を辿らない） */ |
| 47 | private array $grafts = []; |
| 48 | |
| 49 | public function __construct(private Repository $repo) {} |
| 50 | |
| 51 | /** shallowのコミット（そこで履歴が終わるとする） */ |
| 52 | public function setGrafts(array $ids): void { |
| 53 | $this->grafts = array_fill_keys($ids, true); |
| 54 | } |
| 55 | |
| 56 | /** コミットの親と時刻（キャッシュ） */ |
| 57 | private function node(string $id): array { |
| 58 | if (!isset($this->info[$id])) { |
| 59 | $c = $this->repo->commit($id); |
| 60 | $this->info[$id] = [isset($this->grafts[$id]) ? [] : $c->parents, $c->committer?->time ?? 0]; |
| 61 | } |
| 62 | return $this->info[$id]; |
| 63 | } |
| 64 | |
| 65 | /** |
| 66 | * 履歴（新しい順、git logと同じ） |
| 67 | * |
| 68 | * @param array $from リビジョン |
| 69 | * @param array $opt path、limit、skip、not、firstParent |
| 70 | */ |
| 71 | public function log(array $from, array $opt = []): \Generator { |
| 72 | $path = trim((string)($opt['path'] ?? ''), '/'); |
| 73 | $limit = isset($opt['limit']) ? (int)$opt['limit'] : PHP_INT_MAX; |
| 74 | $skip = (int)($opt['skip'] ?? 0); |
| 75 | $firstParent = !empty($opt['firstParent']); |
| 76 | $hide = []; |
| 77 | if (!empty($opt['not'])) { |
| 78 | $nots = []; |
| 79 | foreach ((array)$opt['not'] as $r) { |
| 80 | $id = $this->repo->resolve($r); |
| 81 | $id = $id === null ? null : $this->repo->peel($id, 'commit'); |
| 82 | if ($id !== null) $nots[] = $id; |
| 83 | } |
| 84 | if (!empty($nots)) $hide = array_fill_keys($this->ancestors($nots), true); |
| 85 | } |
| 86 | $queue = new \SplPriorityQueue(); |
| 87 | $seq = PHP_INT_MAX; |
| 88 | $seen = []; |
| 89 | foreach ($from as $r) { |
| 90 | $id = $this->repo->resolve($r); |
| 91 | $id = $id === null ? null : $this->repo->peel($id, 'commit'); |
| 92 | if ($id === null) throw new GitException("リビジョンが有りません：{$r}"); |
| 93 | if (isset($seen[$id]) || isset($hide[$id])) continue; |
| 94 | $seen[$id] = true; |
| 95 | $queue->insert($id, [$this->node($id)[1], $seq--]); |
| 96 | } |
| 97 | $n = 0; |
| 98 | while (!$queue->isEmpty() && $limit > 0) { |
| 99 | $id = $queue->extract(); |
| 100 | $c = $this->repo->commit($id); |
| 101 | $parents = $firstParent ? array_slice($c->parents, 0, 1) : $c->parents; |
| 102 | $show = true; |
| 103 | if ($path !== '') { |
| 104 | // パスが親と同じなら表示しない（同じ親だけを辿る） |
| 105 | $mine = $this->repo->entry($c->tree, $path)[2] ?? null; |
| 106 | $same = null; |
| 107 | foreach ($parents as $p) { |
| 108 | if ($this->repo->objects->exists($p) && ($this->repo->entry($p, $path)[2] ?? null) === $mine) { |
| 109 | $same = $p; |
| 110 | break; |
| 111 | } |
| 112 | } |
| 113 | if ($same !== null) { |
| 114 | $show = false; |
| 115 | $parents = [$same]; |
| 116 | } else if (empty($parents) && $mine === null) { |
| 117 | $show = false; |
| 118 | } |
| 119 | } |
| 120 | foreach ($parents as $p) { |
| 121 | if (isset($seen[$p]) || isset($hide[$p]) || !$this->repo->objects->exists($p)) continue; |
| 122 | $seen[$p] = true; |
| 123 | $queue->insert($p, [$this->node($p)[1], $seq--]); |
| 124 | } |
| 125 | if (!$show) continue; |
| 126 | if ($n++ < $skip) continue; |
| 127 | $limit--; |
| 128 | yield $c; |
| 129 | } |
| 130 | } |
| 131 | |
| 132 | /** 全部の祖先（自分を含む） */ |
| 133 | public function ancestors(array $ids): array { |
| 134 | $seen = []; |
| 135 | $stack = $ids; |
| 136 | while (!empty($stack)) { |
| 137 | $id = array_pop($stack); |
| 138 | if (isset($seen[$id]) || !$this->repo->objects->exists($id)) continue; |
| 139 | $seen[$id] = true; |
| 140 | foreach ($this->node($id)[0] as $p) if (!isset($seen[$p])) $stack[] = $p; |
| 141 | } |
| 142 | return array_keys($seen); |
| 143 | } |
| 144 | |
| 145 | /** aがbの祖先か（同じも含む） */ |
| 146 | public function isAncestor(string $a, string $b): bool { |
| 147 | if ($a === $b) return true; |
| 148 | $target = $this->node($a)[1]; |
| 149 | $seen = []; |
| 150 | $stack = [$b]; |
| 151 | while (!empty($stack)) { |
| 152 | $id = array_pop($stack); |
| 153 | if ($id === $a) return true; |
| 154 | if (isset($seen[$id]) || !$this->repo->objects->exists($id)) continue; |
| 155 | $seen[$id] = true; |
| 156 | [$parents, $time] = $this->node($id); |
| 157 | // 時刻が十分古ければ辿らない（1日のずれを許す） |
| 158 | if ($time < $target - 86400) continue; |
| 159 | foreach ($parents as $p) $stack[] = $p; |
| 160 | } |
| 161 | return false; |
| 162 | } |
| 163 | |
| 164 | /** 共通の祖先（一番新しい物、無ければnull） */ |
| 165 | public function mergeBase(string $a, string $b): ?string { |
| 166 | $anc = array_fill_keys($this->ancestors([$a]), true); |
| 167 | $best = null; |
| 168 | foreach ($this->ancestors([$b]) as $id) { |
| 169 | if (!isset($anc[$id])) continue; |
| 170 | if ($best === null || $this->isAncestor($best, $id)) $best = $id; |
| 171 | } |
| 172 | return $best; |
| 173 | } |
| 174 | |
| 175 | /** |
| 176 | * wantsから到達出来て、havesから到達出来ないコミット |
| 177 | * |
| 178 | * @return array [コミットの配列（新しい順）, 境界のコミット（havesから到達出来る親）] |
| 179 | */ |
| 180 | public function commitsBetween(array $wants, array $haves): array { |
| 181 | $flag = []; |
| 182 | $queue = new \SplPriorityQueue(); |
| 183 | $seq = PHP_INT_MAX; |
| 184 | $interesting = 0; |
| 185 | foreach ($haves as $id) { |
| 186 | if (isset($flag[$id]) || !$this->repo->objects->exists($id)) continue; |
| 187 | $flag[$id] = 'u'; |
| 188 | $queue->insert($id, [$this->node($id)[1], $seq--]); |
| 189 | } |
| 190 | foreach ($wants as $id) { |
| 191 | if (isset($flag[$id])) continue; |
| 192 | $flag[$id] = 'i'; |
| 193 | $interesting++; |
| 194 | $queue->insert($id, [$this->node($id)[1], $seq--]); |
| 195 | } |
| 196 | $order = []; |
| 197 | $slop = 5; |
| 198 | while (!$queue->isEmpty()) { |
| 199 | if ($interesting === 0 && --$slop < 0) break; |
| 200 | $id = $queue->extract(); |
| 201 | $f = $flag[$id]; |
| 202 | if ($f === 'i') { |
| 203 | $interesting--; |
| 204 | $order[] = $id; |
| 205 | } |
| 206 | foreach ($this->node($id)[0] as $p) { |
| 207 | if (!isset($flag[$p])) { |
| 208 | if (!$this->repo->objects->exists($p)) continue; |
| 209 | $flag[$p] = $f; |
| 210 | if ($f === 'i') $interesting++; |
| 211 | $queue->insert($p, [$this->node($p)[1], $seq--]); |
| 212 | } else if ($f === 'u' && $flag[$p] === 'i') { |
| 213 | // 既に見たコミットも除く（時刻がずれている場合） |
| 214 | $this->markUninteresting($p, $flag, $interesting); |
| 215 | } |
| 216 | } |
| 217 | } |
| 218 | $commits = array_values(array_filter($order, fn($id) => $flag[$id] === 'i')); |
| 219 | $boundary = []; |
| 220 | foreach ($commits as $id) foreach ($this->node($id)[0] as $p) if (($flag[$p] ?? null) === 'u') $boundary[$p] = true; |
| 221 | return [$commits, array_keys($boundary)]; |
| 222 | } |
| 223 | |
| 224 | private function markUninteresting(string $id, array &$flag, int &$interesting): void { |
| 225 | $stack = [$id]; |
| 226 | while (!empty($stack)) { |
| 227 | $c = array_pop($stack); |
| 228 | if (($flag[$c] ?? null) !== 'i') continue; |
| 229 | $flag[$c] = 'u'; |
| 230 | $interesting--; |
| 231 | if (isset($this->info[$c])) foreach ($this->info[$c][0] as $p) $stack[] = $p; |
| 232 | } |
| 233 | if ($interesting < 0) $interesting = 0; |
| 234 | } |
| 235 | |
| 236 | /** |
| 237 | * 送るオブジェクト（wantsから到達出来て、havesから到達出来ない物） |
| 238 | * |
| 239 | * @param array $wants 欲しいID（コミット、タグ等） |
| 240 | * @param array $haves 相手が持っているコミット |
| 241 | * @param array|null $commits 送るコミット（深さの制限等で決めた場合） |
| 242 | * @return array ID => 種類（コミット、ツリー・ブロブ、タグの順） |
| 243 | */ |
| 244 | public function objects(array $wants, array $haves, ?array $commits = null, ?array $boundary = null): array { |
| 245 | $tags = []; |
| 246 | $wantCommits = []; |
| 247 | $extra = []; |
| 248 | foreach ($wants as $id) { |
| 249 | $info = $this->repo->objects->info($id); |
| 250 | if ($info === null) throw new GitException("オブジェクトが有りません：{$id}"); |
| 251 | while ($info[0] === 'tag') { |
| 252 | $tags[$id] = 'tag'; |
| 253 | $id = $this->repo->tag($id)->object; |
| 254 | $info = $this->repo->objects->info($id); |
| 255 | if ($info === null) throw new GitException("オブジェクトが有りません：{$id}"); |
| 256 | } |
| 257 | if ($info[0] === 'commit') $wantCommits[] = $id; |
| 258 | else $extra[$id] = $info[0]; |
| 259 | } |
| 260 | if ($commits === null) [$commits, $boundary] = $this->commitsBetween($wantCommits, $haves); |
| 261 | // 境界のコミットのツリーは相手が持っている |
| 262 | $have = []; |
| 263 | foreach ($boundary ?? [] as $b) $this->markTree($this->repo->commit($b)->tree, $have); |
| 264 | $out = []; |
| 265 | foreach ($commits as $id) $out[$id] = 'commit'; |
| 266 | foreach ($commits as $id) $this->addTree($this->repo->commit($id)->tree, $have, $out); |
| 267 | foreach ($extra as $id => $type) { |
| 268 | if ($type === 'tree') $this->addTree($id, $have, $out); |
| 269 | else if (!isset($have[$id])) $out[$id] = $type; |
| 270 | } |
| 271 | return $out + $tags; |
| 272 | } |
| 273 | |
| 274 | private function markTree(string $tree, array &$have): void { |
| 275 | if (isset($have[$tree])) return; |
| 276 | $have[$tree] = true; |
| 277 | foreach ($this->repo->tree($tree)->entries as [$mode, , $id]) { |
| 278 | if ($mode === Tree::DIR) $this->markTree($id, $have); |
| 279 | else if ($mode !== Tree::SUBMODULE) $have[$id] = true; |
| 280 | } |
| 281 | } |
| 282 | |
| 283 | private function addTree(string $tree, array &$have, array &$out): void { |
| 284 | if (isset($have[$tree]) || isset($out[$tree])) return; |
| 285 | $out[$tree] = 'tree'; |
| 286 | foreach ($this->repo->tree($tree)->entries as [$mode, , $id]) { |
| 287 | if ($mode === Tree::DIR) $this->addTree($id, $have, $out); |
| 288 | else if ($mode !== Tree::SUBMODULE && !isset($have[$id])) $out[$id] = 'blob'; |
| 289 | } |
| 290 | } |
| 291 | |
| 292 | /** |
| 293 | * 深さを制限したコミット（git clone --depth） |
| 294 | * |
| 295 | * @return array [コミットの配列, 新しいshallowのコミット] |
| 296 | */ |
| 297 | public function deepen(array $wants, int $depth): array { |
| 298 | $level = []; |
| 299 | $queue = []; |
| 300 | foreach ($wants as $id) { |
| 301 | $level[$id] = 1; |
| 302 | $queue[] = $id; |
| 303 | } |
| 304 | $shallow = []; |
| 305 | for ($i = 0; $i < count($queue); $i++) { |
| 306 | $id = $queue[$i]; |
| 307 | $parents = $this->node($id)[0]; |
| 308 | if ($level[$id] >= $depth) { |
| 309 | if (!empty($parents)) $shallow[$id] = true; |
| 310 | continue; |
| 311 | } |
| 312 | foreach ($parents as $p) { |
| 313 | if (isset($level[$p]) || !$this->repo->objects->exists($p)) continue; |
| 314 | $level[$p] = $level[$id] + 1; |
| 315 | $queue[] = $p; |
| 316 | } |
| 317 | } |
| 318 | return [$queue, array_keys($shallow)]; |
| 319 | } |
| 320 | } |