# File Pack

File pack adalah mekanisme git untuk penyimpanan dan transfer yang efisien. Alih-alih menyimpan setiap objek sebagai file terkompresi zlib terpisah, file pack menggabungkan banyak objek ke dalam satu file dengan kompresi delta opsional. Hampir semua repositori hasil kloning menggunakan file pack.

## Struktur file pack

File pack (`.git/objects/pack/pack-{hash}.pack`) berisi:

```
Header:   PACK (4 bytes) + version (4 bytes, big-endian) + count (4 bytes, big-endian)
Entries:  [type+size varint] [delta-base] [zlib-compressed data] ...
Trailer:  checksum of the pack (20 bytes SHA-1, 32 bytes SHA-256)
```

### Pengodean jenis objek

Setiap entri diawali bilangan bulat dengan panjang bervariasi, dengan jenis dan ukuran diselingkan:

```
First byte: 1TTTSSSS
  TTT  = object type (1-4 for base objects, 6 for OFS_DELTA, 7 for REF_DELTA)
  SSSS = first 4 bits of uncompressed size
  MSB  = 1 means more size bytes follow
```

Nilai jenis:
| Nilai | Jenis |
|-------|------|
| 1 | Commit |
| 2 | Tree |
| 3 | Blob |
| 4 | Tag |
| 6 | OFS_DELTA (delta berbasis offset) |
| 7 | REF_DELTA (delta berbasis hash) |

## Membaca file pack

```php
use Pitmaster\Pack\PackFile;

$pack = PackFile::open(
    '/path/to/.git/objects/pack/pack-abc123.pack',
    '/path/to/.git/objects/pack/pack-abc123.idx',
);

$pack->has($hex);               // Is the object in this pack?
$object = $pack->read($hex);    // Resolved GitObject, or null
$object = $pack->readAtOffset($offset);
$hashes = $pack->allHashes();
```

Kelas `PackFile`:
1. Memvalidasi header `PACK` dan nomor versi
2. Menemukan offset melalui file `.idx` dan mengurai varint jenis/ukuran entri
3. Mendekompresi data yang dikompresi dengan zlib
4. Untuk objek dasar: mengembalikan konten secara langsung
5. Untuk objek delta: meresolusikan basisnya (mengikuti rantai) dan menerapkan delta, lalu menyimpan objek hasil resolusi dalam cache

## File indeks pack

Setiap file `.pack` memiliki file `.idx` pasangan untuk pencarian cepat. Tanpa indeks, objek harus ditemukan dengan memindai seluruh pack.

### Format indeks v2

```
Magic:    FF 74 4F 63 (identifies v2)
Version:  00 00 00 02
Fanout:   256 x 4-byte big-endian counts (cumulative)
Names:    N x 20-byte SHA-1 hashes, sorted (32 bytes for SHA-256)
CRC32s:   N x 4-byte CRC32 checksums
Offsets:  N x 4-byte pack offsets (MSB=1 means large offset table)
Large:    M x 8-byte offsets (for packs > 2GB)
Checksums: pack checksum + index checksum (20 bytes each for SHA-1)
```

```php
use Pitmaster\Pack\PackIndex;

$index = PackIndex::open('/path/to/pack-abc123.idx');

// Look up an object
$offset = $index->findOffset($hex);  // Pack file offset, or null

// List all objects in the pack
$hashes = $index->allHashes();
$count = $index->objectCount();
```

Tabel fanout memungkinkan pencarian biner O(log n): entri 256 menunjukkan jumlah hash yang dimulai dengan setiap kemungkinan byte pertama.

### Format indeks v1

Format lama tanpa checksum CRC32. Pitmaster mendukung keduanya: `PackIndex::open()` membaca file v1 jika magic v2 tidak ada, sehingga kode yang sama berfungsi untuk keduanya.

## Resolusi delta

Objek berdelta menyimpan instruksi untuk merekonstruksi konten dari objek basis, alih-alih menyimpan konten lengkap. Cara ini menghasilkan kompresi signifikan untuk objek yang serupa (e.g., versi berurutan dari file yang sama).

### Jenis delta

**OFS_DELTA** (jenis 6): objek basis diidentifikasi dengan offset negatif dalam file pack yang sama. Lebih umum karena tidak perlu mengetahui hash objek basis.

**REF_DELTA** (jenis 7): objek basis diidentifikasi dengan hash-nya. Di git, basis dapat berada di luar pack (thin pack). Pitmaster hanya mencari basis REF_DELTA di dalam pack yang sama, sehingga thin pack tidak didukung ([#16](https://github.com/inline0/pitmaster/issues/16)).

### Instruksi delta

Konten delta berupa rangkaian instruksi salin dan sisipkan:

```
Copy:   1XXXXXXX [offset bytes] [size bytes]   (copy from base)
Insert: 0LLLLLLL <L bytes of literal data>       (insert new data)
```

Instruksi salin: 7 bit X menunjukkan byte offset dan ukuran yang tersedia. Offset berukuran hingga 4 byte, ukuran hingga 3 byte. Jika ukurannya nol, artinya 0x10000 (65536) byte.

Instruksi sisipkan: 7 bit L menunjukkan panjang data literal (1-127 byte). L=0 dicadangkan/tidak valid.

### DeltaApplier

```php
use Pitmaster\Pack\DeltaApplier;

$result = DeltaApplier::apply($baseContent, $deltaInstructions);
```

`DeltaApplier`:
1. Membaca ukuran basis dan ukuran hasil yang diharapkan dari header delta (dikodekan sebagai LEB128)
2. Menelusuri instruksi:
   - Salin: mengambil offset dan ukuran, lalu menyalin byte dari konten basis
   - Sisipkan: mengambil panjang, lalu menyalin byte literal dari data delta
3. Memverifikasi bahwa ukuran hasil cocok dengan ukuran yang diharapkan

### Rantai delta

Basis suatu objek berdelta dapat berupa objek berdelta itu sendiri. `PackFile::read()` dan `readAtOffset()` mengikuti rantainya:

1. Baca entri. Jika jenisnya adalah jenis dasar (commit, tree, blob, tag), kembalikan entri tersebut.
2. Jika OFS_DELTA: hitung offset basis (offset saat ini dikurangi offset negatif yang dikodekan), baca entri basis, lalu lakukan rekursi.
3. Jika REF_DELTA: cari basis berdasarkan hash dalam indeks pack yang sama, lalu lakukan rekursi.
4. Terapkan instruksi delta pada basis yang sudah diresolusikan.
5. Terapkan batas `PITMASTER_MAX_DELTA_CHAIN` (default 50) untuk mencegah rantai berjalan tanpa kendali.

```php
// Configure max chain depth (integer)
define('PITMASTER_MAX_DELTA_CHAIN', 50);

// Read the effective limit
$max = \Pitmaster\Pack\DeltaResolver::maxChainDepth();
```

## PackWriter

Pitmaster dapat menulis file pack untuk operasi jaringan (push).

```php
use Pitmaster\Pack\PackWriter;
use Pitmaster\Pack\PackIndexer;

$packData = PackWriter::encode($objects);           // GitObject[] to pack bytes
$paths = PackWriter::write($packDir, $objects);     // ['packPath' => ..., 'idxPath' => ..., 'hash' => ...]

$idxPath = PackIndexer::writeIndex($packPath);      // Build the .idx for a received pack
```

`PackWriter`:
1. Mengumpulkan objek yang akan disertakan dalam pack
2. Menserialisasikan setiap objek dengan header varint jenis/ukuran
3. Mengompresi konten dengan zlib
4. Menulis header PACK, entri, dan trailer SHA-1

Saat ini hanya menulis objek dasar (tanpa kompresi delta). Kompresi delta adalah optimasi yang dapat ditambahkan nanti; biarkan `git gc` mengemas ulang demi efisiensi penyimpanan.

## PackEnumerator

Ulangi semua objek dalam pack, sesuai urutan indeks:

```php
use Pitmaster\Pack\PackEnumerator;

$enumerator = new PackEnumerator($packFile); // a PackFile opened with its .idx

foreach ($enumerator->enumerate() as $object) {
    echo "{$object->type->value} {$object->id->hex} {$object->size()}\n";
}
```

Setiap item adalah `GitObject` yang sudah diresolusikan.

## MultiPackIndex

Untuk repositori dengan banyak file pack, multi-pack-index (MIDX) menyediakan satu pencarian untuk semua pack.

```php
use Pitmaster\Pack\MultiPackIndex;
```

File MIDX (`.git/objects/pack/multi-pack-index`) berisi:
- Tabel fanout (seperti v2 indeks pack)
- ID objek yang diurutkan di seluruh pack
- Nama file pack dan penetapan pack untuk setiap objek
- Offset ke dalam setiap file pack

`MultiPackIndex::open($path)` mengurai file MIDX dan menyediakan `findObject($hex)` dan `packNames()`. Pencarian objek di repositori tidak menggunakannya: basis data objek selalu membaca file `.idx` satu per satu.

## CommitGraph

File commit-graph mempercepat penelusuran riwayat commit dan penghitungan merge base.

```php
use Pitmaster\Pack\CommitGraph;
```

Terletak di `.git/objects/info/commit-graph`, file ini berisi:
- OID commit dalam urutan terurut
- Informasi parent (diindeks, tidak memerlukan pembacaan objek)
- Nomor generasi (untuk mempercepat kueri keterjangkauan)
- Timestamp commit

Jika tersedia, penghitungan merge base di balik `Repository::merge()`, `mergeBase()`, `isBranchMerged()`, dan pemeriksaan fast-forward push membaca tautan parent dari commit-graph alih-alih membaca objek commit satu per satu. `CommitWalker` (log) tidak menggunakannya.

## Bilangan bulat dengan panjang bervariasi

File pack menggunakan beberapa pengodean bilangan bulat dengan panjang bervariasi:

### Varint Git (header jenis/ukuran)

Pengodean lanjutkan-pada-MSB, dengan bit paling signifikan menandakan masih ada byte berikutnya:

```php
use Pitmaster\Encoding\VarInt;

$size = VarInt::decodePackSize($reader, $initialBits);  // continues the size from the first header byte
$offset = VarInt::decodeOfsOffset($reader);             // OFS_DELTA base distance
$header = VarInt::encodePackSize($type, $size);
```

### LEB128 (header delta)

Digunakan dalam header instruksi delta untuk ukuran dasar dan ukuran hasil:

```php
use Pitmaster\Encoding\Leb128;

$value = Leb128::decodeUnsigned($reader);   // a BinaryReader
$bytes = Leb128::encodeUnsigned($value);
```

### BinaryReader

Aliran byte tingkat rendah dengan pelacakan posisi:

```php
use Pitmaster\Encoding\BinaryReader;

$reader = new BinaryReader($data);
$byte = $reader->readByte();
$int = $reader->readUint32();   // big-endian
$bytes = $reader->read(20);
$hash = $reader->readHash(20);
$reader->position();  // Current offset
$reader->seek(0);
```