# Pack-файли

Pack-файли — механізм git для ефективного зберігання та передавання даних. Замість зберігання кожного об'єкта в окремому стисненому файлі zlib, pack-файли об'єднують багато об'єктів в один файл із необов'язковим дельта-стисненням. Майже всі клоновані репозиторії використовують pack-файли.

## Структура pack-файлу

Pack-файл (`.git/objects/pack/pack-{hash}.pack`) містить:

```
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)
```

### Кодування типу об'єкта

Кожен запис починається цілим числом змінної довжини, у якому чергуються тип і розмір:

```
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
```

Значення типів:
| Значення | Тип |
|-------|------|
| 1 | Commit |
| 2 | Tree |
| 3 | Blob |
| 4 | Tag |
| 6 | OFS_DELTA (дельта за зміщенням) |
| 7 | REF_DELTA (дельта за хешем) |

## Читання 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();
```

Клас `PackFile`:
1. Перевіряє заголовок `PACK` і номер версії
2. Знаходить зміщення через файл `.idx` і розбирає varint типу/розміру запису
3. Розпаковує стиснені дані zlib
4. Для базових об'єктів повертає вміст без змін
5. Для дельта-об'єктів розв'язує посилання на базовий об'єкт (проходячи ланцюжки) і застосовує дельту, кешуючи розв'язані об'єкти

## Файли індексу pack

Кожен файл `.pack` має відповідний файл `.idx` для швидкого пошуку. Без індексу для знаходження об'єкта потрібно сканувати весь pack.

### Формат індексу 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();
```

Таблиця розгалужень дає змогу виконувати двійковий пошук O(log n): записи 256 вказують, скільки хешів починаються з кожного можливого першого байта.

### Формат індексу v1

Старіший формат без контрольних сум CRC32. Pitmaster підтримує обидва формати: `PackIndex::open()` читає файл v1, якщо відсутній магічний номер v2, тож той самий код працює з обома.

## Розв'язання дельт

Дельта-об'єкти зберігають інструкції для відновлення вмісту з базового об'єкта замість повного вмісту. Це забезпечує значне стиснення схожих об'єктів (e.g., послідовних версій того самого файлу).

### Типи дельт

**OFS_DELTA** (тип 6): базовий об'єкт визначається від'ємним зміщенням у тому самому pack-файлі. Такий тип поширеніший, бо не потребує знання хешу базового об'єкта.

**REF_DELTA** (тип 7): базовий об'єкт визначається за його хешем. У git базовий об'єкт може зберігатися поза pack-файлом (тонкі pack-файли). Pitmaster шукає REF_DELTA базові об'єкти лише в тому самому pack-файлі, тому тонкі pack-файли не підтримуються ([#16](https://github.com/inline0/pitmaster/issues/16)).

### Інструкції дельти

Вміст дельти — це послідовність інструкцій копіювання та вставлення:

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

Вказівки копіювання: 7 бітів X позначають, які байти зміщення та розміру присутні. Зміщення займає до 4 байтів, розмір — до 3 байтів. Якщо розмір дорівнює нулю, це означає 65536 байтів (0x10000).

Вказівки вставлення: 7 бітів L задають довжину літеральних даних (1-127 байтів). L=0 зарезервовано й недійсне.

### DeltaApplier

```php
use Pitmaster\Pack\DeltaApplier;

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

`DeltaApplier`:
1. Читає очікувані розмір базового об'єкта та розмір результату із заголовка дельти (у кодуванні LEB128)
2. Перебирає інструкції:
   - Копіювання: отримує зміщення й розмір та копіює байти з базового вмісту
   - Вставлення: отримує довжину й копіює літеральні байти з даних дельти
3. Перевіряє, чи відповідає розмір результату очікуваному

### Ланцюжки дельт

Базовий об'єкт дельта-об'єкта сам може бути дельта-об'єктом. `PackFile::read()` і `readAtOffset()` проходять цей ланцюжок:

1. Читає запис. Якщо це базовий тип (commit, tree, blob, tag), повертає його.
2. Якщо OFS_DELTA: обчислює зміщення базового об'єкта (поточне зміщення мінус закодоване від'ємне зміщення), читає базовий запис і переходить до нього рекурсивно.
3. Якщо REF_DELTA: шукає базовий об'єкт за хешем в індексі того самого pack-файлу й переходить до нього рекурсивно.
4. Застосовує інструкції дельти до розв'язаного базового об'єкта.
5. Обмежує `PITMASTER_MAX_DELTA_CHAIN` (за замовчуванням 50), щоб запобігти надмірно довгим ланцюжкам.

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

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

## PackWriter

Pitmaster може записувати pack-файли для мережевих операцій (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. Збирає об'єкти для включення в pack-файл
2. Серіалізує кожен об'єкт із заголовком varint типу/розміру
3. Стискає вміст за допомогою zlib
4. Записує заголовок PACK, записи та завершальний хеш SHA-1

Наразі записуються лише базові об'єкти (без дельта-стиснення). Дельта-стиснення можна додати пізніше як оптимізацію; для ефективнішого зберігання дозвольте `git gc` перепакувати об'єкти.

## PackEnumerator

Перебрати всі об'єкти в pack-файлі в порядку індексу:

```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";
}
```

Кожен елемент — це розв'язаний об'єкт `GitObject`.

## MultiPackIndex

Для репозиторіїв із багатьма pack-файлами multi-pack-index (MIDX) забезпечує єдиний пошук в усіх pack-файлах.

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

Файл MIDX (`.git/objects/pack/multi-pack-index`) містить:
- Таблицю розгалужень (як в індексі pack v2)
- ID об'єктів, відсортовані для всіх pack-файлів
- Назви pack-файлів і призначення кожного об'єкта відповідному pack-файлу
- Зміщення в окремих pack-файлах

`MultiPackIndex::open($path)` розбирає файл MIDX і надає `findObject($hex)` та `packNames()`. Пошук об'єктів у репозиторії ним не користується: база об'єктів завжди читає окремі файли `.idx`.

## CommitGraph

Файл commit-graph прискорює обхід історії комітів і обчислення бази злиття.

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

Розташований у `.git/objects/info/commit-graph`, він містить:
- OID комітів у відсортованому порядку
- Інформацію про батьків (індексовану, без потреби читати об'єкти)
- Номери генерації (для швидших запитів щодо досяжності)
- Часові позначки комітів

Коли цей файл наявний, обчислення бази злиття для `Repository::merge()`, `mergeBase()`, `isBranchMerged()` і перевірки перемотування вперед під час push читає посилання на батьків із commit-graph, а не окремі об'єкти комітів. `CommitWalker` (log) його не використовує.

## Цілі числа змінної довжини

У pack-файлах використовуються різні кодування цілих чисел змінної довжини:

### Varint Git (заголовки типу/розміру)

Кодування з продовженням у старшому біті: старший біт указує, що за ним ідуть додаткові байти:

```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 (заголовки дельт)

Використовується в заголовках інструкцій delta для базового розміру та розміру результату:

```php
use Pitmaster\Encoding\Leb128;

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

### BinaryReader

Низькорівневий потік байтів із відстеженням позиції:

```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);
```