suwako / LittleBeast

master
ブランチ master
LittleBeast / src / Std / Lib / Git / Pack.php
11.4 KB、297行 生 Blame 履歴
1<?php
2/*************************************************************
3# 076 License
4
5Copyright (c) テクニカル諏訪子
6
7Permission is hereby granted to any person obtaining a copy of the software
8Little Beast (the "Software") to use, modify, merge, copy, publish, distribute,
9sublicense, 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
31THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
32INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
33PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
34HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
35CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
36OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 */
38namespace Std\Lib\Git;
39
40/**
41 * パックファイル（objects/pack/pack-*.pack）とインデックス（.idx v2、v1）
42 *
43 * オブジェクトの種類：1 commit、2 tree、3 blob、4 tag、6 OFS_DELTA、7 REF_DELTA。
44 */
45final class Pack {
46 public const COMMIT = 1;
47 public const TREE = 2;
48 public const BLOB = 3;
49 public const TAG = 4;
50 public const OFS_DELTA = 6;
51 public const REF_DELTA = 7;
52 public const TYPES = [1 => 'commit', 2 => 'tree', 3 => 'blob', 4 => 'tag'];
53
54 /** @var resource|null */
55 private $fh = null;
56 private string $idx = '';
57 private int $version = 2;
58 private int $count = 0;
59 private int $namesAt = 0;
60 private int $crcAt = 0;
61 private int $offsetsAt = 0;
62 private int $largeAt = 0;
63 private ?string $rev = null;
64 public readonly int $size;
65
66 /**
67 * @param string $path .packのパス
68 * @param int $hashLen 20（SHA-1）又は32（SHA-256）
69 * @param bool $withIndex .idxを読む（受け取り中のパックはfalse）
70 */
71 public function __construct(public readonly string $path, private int $hashLen, bool $withIndex = true) {
72 $fh = @fopen($path, 'rb');
73 if ($fh === false) throw new GitException("パックを開けません：{$path}");
74 $this->fh = $fh;
75 $this->size = (int)fstat($fh)['size'];
76 $head = (string)fread($fh, 12);
77 if (strlen($head) < 12 || substr($head, 0, 4) !== 'PACK' || !in_array(unpack('N', $head, 4)[1], [2, 3], true)) throw new GitException("パックではありません：{$path}");
78 if ($withIndex) $this->loadIndex(substr($path, 0, -5).'.idx');
79 }
80
81 public function __destruct() {
82 if ($this->fh) fclose($this->fh);
83 }
84
85 private function loadIndex(string $file): void {
86 $idx = @file_get_contents($file);
87 if ($idx === false) throw new GitException("インデックスを読めません：{$file}");
88 $this->idx = $idx;
89 $h = $this->hashLen;
90 if (substr($idx, 0, 4) === "\xfftOc") {
91 $this->version = unpack('N', $idx, 4)[1];
92 if ($this->version !== 2) throw new GitException("未対応のインデックスのバージョン：{$this->version}");
93 $this->count = unpack('N', $idx, 8 + 255 * 4)[1];
94 $this->namesAt = 8 + 256 * 4;
95 $this->crcAt = $this->namesAt + $this->count * $h;
96 $this->offsetsAt = $this->crcAt + $this->count * 4;
97 $this->largeAt = $this->offsetsAt + $this->count * 4;
98 } else {
99 // v1：fanout、[オフセット(4) 名前]の配列
100 $this->version = 1;
101 $this->count = unpack('N', $idx, 255 * 4)[1];
102 $this->namesAt = 256 * 4;
103 }
104 if (strlen($idx) < $this->namesAt + $this->count * $h) throw new GitException("壊れたインデックス：{$file}");
105 }
106
107 public function count(): int {
108 return $this->count;
109 }
110
111 /** n番目（名前の順）のID（バイナリ） */
112 public function idAt(int $n): string {
113 return $this->version === 2 ? substr($this->idx, $this->namesAt + $n * $this->hashLen, $this->hashLen)
114 : substr($this->idx, $this->namesAt + $n * ($this->hashLen + 4) + 4, $this->hashLen);
115 }
116
117 /** n番目のオフセット */
118 public function offsetAt(int $n): int {
119 if ($this->version === 1) return unpack('N', $this->idx, $this->namesAt + $n * ($this->hashLen + 4))[1];
120 $o = unpack('N', $this->idx, $this->offsetsAt + $n * 4)[1];
121 if ($o & 0x80000000) $o = unpack('J', $this->idx, $this->largeAt + ($o & 0x7fffffff) * 8)[1];
122 return $o;
123 }
124
125 public function crcAt(int $n): ?int {
126 return $this->version === 2 ? unpack('N', $this->idx, $this->crcAt + $n * 4)[1] : null;
127 }
128
129 /**
130 * IDの位置（名前の順の番号）
131 *
132 * @param string $id バイナリのID
133 */
134 public function position(string $id): ?int {
135 $first = ord($id[0]);
136 $fan = $this->version === 2 ? 8 : 0;
137 $lo = $first === 0 ? 0 : unpack('N', $this->idx, $fan + ($first - 1) * 4)[1];
138 $hi = unpack('N', $this->idx, $fan + $first * 4)[1] - 1;
139 while ($lo <= $hi) {
140 $mid = ($lo + $hi) >> 1;
141 $c = strcmp($this->idAt($mid), $id);
142 if ($c === 0) return $mid;
143 if ($c < 0) $lo = $mid + 1;
144 else $hi = $mid - 1;
145 }
146 return null;
147 }
148
149 /** IDのオフセット（無ければnull） */
150 public function find(string $id): ?int {
151 $n = $this->position($id);
152 return $n === null ? null : $this->offsetAt($n);
153 }
154
155 /**
156 * 始まりが一致するID（短いIDの解決用）
157 *
158 * @param string $prefix 16進数（偶数でなくても良い）
159 * @return string[] 16進数（最大2件）
160 */
161 public function findPrefix(string $prefix): array {
162 $out = [];
163 $first = hexdec(substr($prefix . '0', 0, 2));
164 $fan = $this->version === 2 ? 8 : 0;
165 $lo = $first === 0 ? 0 : unpack('N', $this->idx, $fan + ($first - 1) * 4)[1];
166 $hi = unpack('N', $this->idx, $fan + (strlen($prefix) >= 2 ? $first : min(255, $first + 15)) * 4)[1];
167 for ($n = $lo; $n < $hi && count($out) < 2; $n++) {
168 $hex = bin2hex($this->idAt($n));
169 if (str_starts_with($hex, $prefix)) $out[] = $hex;
170 }
171 return $out;
172 }
173
174 /** 全部のID（16進数） */
175 public function ids(): \Generator {
176 for ($n = 0; $n < $this->count; $n++) yield bin2hex($this->idAt($n));
177 }
178
179 /**
180 * エントリーのヘッダー
181 *
182 * @return array [種類, 大きさ, データの位置, 元のオフセット（OFS）, 元のID（REF、バイナリ）]
183 */
184 public function header(int $offset): array {
185 fseek($this->fh, $offset);
186 $buf = (string)fread($this->fh, 32 + $this->hashLen);
187 $p = 0;
188 $b = ord($buf[$p++]);
189 $type = ($b >> 4) & 7;
190 $size = $b & 15;
191 $shift = 4;
192 while ($b & 0x80) {
193 $b = ord($buf[$p++]);
194 $size |= ($b & 0x7f) << $shift;
195 $shift += 7;
196 }
197 $baseOffset = null;
198 $baseId = null;
199 if ($type === self::OFS_DELTA) {
200 $b = ord($buf[$p++]);
201 $n = $b & 0x7f;
202 while ($b & 0x80) {
203 $b = ord($buf[$p++]);
204 $n = (($n + 1) << 7) | ($b & 0x7f);
205 }
206 $baseOffset = $offset - $n;
207 if ($baseOffset < 12 || $baseOffset >= $offset) throw new GitException("壊れたパック（OFS_DELTA）：{$this->path}");
208 } else if ($type === self::REF_DELTA) {
209 $baseId = substr($buf, $p, $this->hashLen);
210 $p += $this->hashLen;
211 } else if (!isset(self::TYPES[$type])) {
212 throw new GitException("壊れたパック（種類{$type}、{$offset}）：{$this->path}");
213 }
214 return [$type, $size, $offset + $p, $baseOffset, $baseId];
215 }
216
217 /**
218 * zlibのデータを展開する
219 *
220 * @param int $pos データの位置
221 * @param int $size 展開後の大きさ（分かっていれば読む量の目安）
222 * @param int|null $consumed 圧縮されたデータの長さ
223 */
224 public function inflate(int $pos, int $size, ?int &$consumed = null): string {
225 fseek($this->fh, $pos);
226 $ctx = inflate_init(ZLIB_ENCODING_DEFLATE);
227 $out = '';
228 $chunk = min(max(256, $size + 64), 1048576);
229 while (true) {
230 $in = fread($this->fh, $chunk);
231 if ($in === false || $in === '') throw new GitException("壊れたパック（途中で終わる）：{$this->path}");
232 $res = @inflate_add($ctx, $in, ZLIB_SYNC_FLUSH);
233 if ($res === false) throw new GitException("壊れたパック（zlib）：{$this->path}");
234 $out .= $res;
235 if (inflate_get_status($ctx) === ZLIB_STREAM_END) break;
236 $chunk = 65536;
237 }
238 $consumed = inflate_get_read_len($ctx);
239 if (strlen($out) !== $size) throw new GitException("壊れたパック（大きさ）：{$this->path}");
240 return $out;
241 }
242
243 /** 位置のオフセットに対する次のエントリーの始まり（.revか、無ければ作る） */
244 public function entryEnd(int $offset): int {
245 $this->loadRev();
246 // オフセットの順のn番目
247 $lo = 0;
248 $hi = $this->count - 1;
249 while ($lo <= $hi) {
250 $mid = ($lo + $hi) >> 1;
251 $o = $this->offsetAt(unpack('N', $this->rev, $mid * 4)[1]);
252 if ($o === $offset) return $mid + 1 < $this->count ? $this->offsetAt(unpack('N', $this->rev, ($mid + 1) * 4)[1]) : $this->size - $this->hashLen;
253 if ($o < $offset) $lo = $mid + 1;
254 else $hi = $mid - 1;
255 }
256 throw new GitException("パックにエントリーが有りません（{$offset}）：{$this->path}");
257 }
258
259 /** オフセットのID（バイナリ） */
260 public function idAtOffset(int $offset): ?string {
261 $this->loadRev();
262 $lo = 0;
263 $hi = $this->count - 1;
264 while ($lo <= $hi) {
265 $mid = ($lo + $hi) >> 1;
266 $n = unpack('N', $this->rev, $mid * 4)[1];
267 $o = $this->offsetAt($n);
268 if ($o === $offset) return $this->idAt($n);
269 if ($o < $offset) $lo = $mid + 1;
270 else $hi = $mid - 1;
271 }
272 return null;
273 }
274
275 /** 逆インデックス（オフセットの順の名前の番号）。.revが有れば使う */
276 private function loadRev(): void {
277 if ($this->rev !== null) return;
278 $file = substr($this->path, 0, -5).'.rev';
279 $r = is_file($file) ? (string)file_get_contents($file) : '';
280 if (strlen($r) >= 12 + $this->count * 4 && substr($r, 0, 4) === 'RIDX' && unpack('N', $r, 4)[1] === 1) {
281 $this->rev = substr($r, 12, $this->count * 4);
282 return;
283 }
284 $offs = [];
285 for ($n = 0; $n < $this->count; $n++) $offs[$n] = $this->offsetAt($n);
286 asort($offs);
287 $this->rev = pack('N*', ...array_keys($offs));
288 }
289
290 /** パックの中身の生のバイト列（ヘッダーと圧縮されたデータ） */
291 public function raw(int $start, int $end): string {
292 fseek($this->fh, $start);
293 $s = (string)fread($this->fh, $end - $start);
294 if (strlen($s) !== $end - $start) throw new GitException("パックを読めません：{$this->path}");
295 return $s;
296 }
297}