# Soubory pack

Soubory pack jsou mechanismem git pro efektivní ukládání a přenos. Místo ukládání každého objektu jako samostatného souboru komprimovaného pomocí zlib kombinují mnoho objektů do jednoho souboru s volitelnou kompresí delt. Soubory pack používá téměř každé naklonované úložiště.

## Struktura souboru pack

Soubor pack (`.git/objects/pack/pack-{hash}.pack`) obsahuje:

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

### Kódování typu objektu

Každá položka začíná celočíselnou hodnotou proměnné délky, v níž jsou typ a velikost proloženy:

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

Hodnoty typu:
| Hodnota | Typ |
|-------|------|
| 1 | Commit |
| 2 | Tree |
| 3 | Blob |
| 4 | Tag |
| 6 | OFS_DELTA (delta založená na offsetu) |
| 7 | REF_DELTA (delta založená na hashi) |

## Čtení souborů 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();
```

Třída `PackFile`:
1. Ověří hlavičku `PACK` a číslo verze
2. Vyhledá offset v souboru `.idx` a načte varint typu a velikosti položky
3. Dekomprimuje data komprimovaná pomocí zlib
4. U základních objektů vrátí obsah přímo
5. U deltových objektů najde základ (postupuje řetězcem delt), použije deltu a objekty po vyřešení ukládá do mezipaměti

## Soubory indexu pack

Ke každému souboru `.pack` patří soubor `.idx` pro rychlé vyhledávání. Bez indexu je nutné při hledání objektu prohledat celý soubor pack.

### Formát indexu 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();
```

Tabulka rozptylu umožňuje binární vyhledávání O(log n): položky 256 udávají, kolik hashů začíná každým možným prvním bajtem.

### Formát indexu v1

Starší formát bez kontrolních součtů CRC32. Pitmaster podporuje oba formáty: `PackIndex::open()` načte soubor v1, pokud chybí magická hodnota v2, takže stejný kód funguje pro oba.

## Řešení delt

Objekty uložené pomocí delty obsahují pokyny k obnovení obsahu ze základního objektu místo celého obsahu. Tím se dosahuje výrazné komprese u podobných objektů (e.g např. po sobě jdoucích verzí stejného souboru).

### Typy delt

**OFS_DELTA** (typ 6): základní objekt je určen záporným offsetem v rámci stejného souboru pack. Tento typ je běžnější, protože nevyžaduje znalost hashe základního objektu.

**REF_DELTA** (typ 7): základní objekt je určen svým hashem. V gitu může být základ mimo soubor pack (tenké soubory pack). Pitmaster hledá základy REF_DELTA pouze v rámci stejného souboru pack, takže tenké soubory pack nejsou podporovány ([#16](https://github.com/inline0/pitmaster/issues/16)).

### Pokyny delty

Obsah delty tvoří posloupnost pokynů ke kopírování a vkládání:

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

Pokyny ke kopírování: 7 bitů X určuje, které bajty offsetu a velikosti jsou přítomné. Offset může mít až 4 bajty, velikost až 3 bajty. Pokud je velikost nula, znamená to 65536 bajtů.

Pokyny k vložení: 7 bitů L udává délku doslovných dat (1–127 bajtů). L=0 je vyhrazená/neplatná hodnota.

### DeltaApplier

```php
use Pitmaster\Pack\DeltaApplier;

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

`DeltaApplier`:
1. Načte očekávanou velikost základu a výslednou velikost z hlavičky delty (kódování LEB128)
2. Prochází pokyny:
   - Kopírování: načte offset a velikost a zkopíruje bajty z obsahu základu
   - Vložení: načte délku a zkopíruje doslovné bajty z dat delty
3. Ověří, že výsledná velikost odpovídá očekávané velikosti

### Řetězce delt

Základ objektu uloženého pomocí delty může být sám uložen pomocí delty. `PackFile::read()` a `readAtOffset()` postupují řetězcem:

1. Načte položku. Pokud jde o základní typ (commit, tree, blob, tag), vrátí ji.
2. U OFS_DELTA vypočítá offset základu (aktuální offset minus zakódovaný záporný offset), načte základní položku a rekurzivně pokračuje.
3. U REF_DELTA vyhledá základ podle hashe v indexu stejného souboru pack a rekurzivně pokračuje.
4. Použije pokyny delty na vyřešený základ.
5. Vynutí limit `PITMASTER_MAX_DELTA_CHAIN` (výchozí hodnota 50), aby zabránil nekonečně dlouhým řetězcům.

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

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

## PackWriter

Pitmaster může zapisovat soubory pack pro síťové operace (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. Shromáždí objekty, které mají být zahrnuty do souboru pack
2. Serializuje každý objekt s hlavičkou varint typu a velikosti
3. Komprimuje obsah pomocí zlib
4. Zapíše hlavičku PACK, položky a závěrečný SHA-1

V současnosti zapisuje pouze základní objekty (bez komprese delt). Komprese delt je optimalizace, kterou lze přidat později; přenechte přebalení kvůli efektivnějšímu ukládání nástroji `git gc`.

## PackEnumerator

Procházet všechny objekty v souboru pack v pořadí podle indexu:

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

Každá položka je vyřešený objekt `GitObject`.

## MultiPackIndex

U úložišť s mnoha soubory pack poskytuje multi-pack-index (MIDX) jednotné vyhledávání napříč všemi soubory pack.

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

Soubor MIDX (`.git/objects/pack/multi-pack-index`) obsahuje:
- Tabulku rozptylu (jako index pack v2)
- ID objektů seřazená napříč všemi soubory pack
- Názvy souborů pack a přiřazení jednotlivých objektů k souborům pack
- Offsety v jednotlivých souborech pack

`MultiPackIndex::open($path)` analyzuje soubor MIDX a poskytuje `findObject($hex)` a `packNames()`. Vyhledávání objektů v úložišti jej nepoužívá: databáze objektů vždy čte jednotlivé soubory `.idx`.

## CommitGraph

Soubor commit-graph urychluje procházení historie commitů a výpočet základů sloučení.

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

Nachází se v `.git/objects/info/commit-graph` a obsahuje:
- OID commitů v seřazeném pořadí
- Informace o rodičích (indexované, bez nutnosti číst objekty)
- Generační čísla (pro rychlejší dotazy na dosažitelnost)
- Časová razítka commitů

Pokud je k dispozici, výpočet základního sloučení pro `Repository::merge()`, `mergeBase()`, `isBranchMerged()` a kontrola rychlého posunu při odesílání čtou odkazy na rodiče z grafu commitů namísto jednotlivých objektů commitů. `CommitWalker` (log) tuto možnost nepoužívá.

## Celá čísla proměnné délky

Soubory pack používají několik kódování celých čísel proměnné délky:

### Git varint (hlavičky typu a velikosti)

Kódování MSB-continue, kde nejvýznamnější bit označuje, že následují další bajty:

```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 (hlavičky rozdílů)

Používá se v hlavičkách instrukcí rozdílu pro velikost základu a výsledku:

```php
use Pitmaster\Encoding\Leb128;

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

### BinaryReader

Nízkourovňový proud bajtů se sledováním pozice:

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