# Packbestanden

Packbestanden zijn het mechanisme van git voor efficiënte opslag en overdracht. In plaats van elk object als een afzonderlijk, met zlib gecomprimeerd bestand op te slaan, combineren packbestanden veel objecten in één bestand, eventueel met deltacompressie. Bijna elke gekloonde repository gebruikt packbestanden.

## Structuur van packbestanden

Een packbestand (`.git/objects/pack/pack-{hash}.pack`) bevat:

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

### Codering van objecttypen

Elke vermelding begint met een geheel getal met variabele lengte, waarin het type en de grootte door elkaar zijn gecodeerd:

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

Typewaarden:
| Waarde | Type |
|-------|------|
| 1 | Commit |
| 2 | Tree |
| 3 | Blob |
| 4 | Tag |
| 6 | OFS_DELTA (deltaverwijzing op basis van offset) |
| 7 | REF_DELTA (deltaverwijzing op basis van hash) |

## Packbestanden lezen

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

De klasse `PackFile`:
1. Valideert de koptekst en het versienummer van `PACK`
2. Vindt de offset via het bestand `.idx` en parseert de varint voor type en grootte van de vermelding
3. Decomprimeert de gegevens die met zlib zijn gecomprimeerd
4. Voor basisobjecten: retourneert de inhoud rechtstreeks
5. Voor delta-objecten: haalt het basisobject op (en volgt daarbij de keten) en past de delta toe; opgeloste objecten worden gecachet

## Packindexbestanden

Bij elk bestand van `.pack` hoort een bestand van `.idx` voor snelle zoekacties. Zonder de index moet het hele packbestand worden doorzocht om een object te vinden.

### Indeling van de v2-index

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

De fan-outtabel maakt binair zoeken naar O(log n) mogelijk: de vermeldingen van 256 geven aan hoeveel hashes met elke mogelijke eerste byte beginnen.

### Indeling van de v1-index

Oudere indeling zonder CRC32-controlesommen. Pitmaster ondersteunt beide: `PackIndex::open()` leest een bestand van v1 als de magische waarde v2 ontbreekt, zodat dezelfde code voor beide werkt.

## Delta's verwerken

Objecten met deltacompressie bevatten instructies om de inhoud uit een basisobject te reconstrueren, in plaats van de volledige inhoud op te slaan. Dit zorgt voor aanzienlijke compressie bij vergelijkbare objecten (e.g., opeenvolgende versies van hetzelfde bestand).

### Deltatypen

**OFS_DELTA** (type 6): het basisobject wordt aangeduid met een negatieve offset binnen hetzelfde packbestand. Dit komt vaker voor omdat de hash van het basisobject niet bekend hoeft te zijn.

**REF_DELTA** (type 7): het basisobject wordt aangeduid met zijn hash. In git kan het basisobject buiten het packbestand staan (thin packs). Pitmaster zoekt alleen binnen hetzelfde packbestand naar REF_DELTA-basisobjecten. Thin packs worden daarom niet ondersteund ([#16](https://github.com/inline0/pitmaster/issues/16)).

### Delta-instructies

Delta-inhoud is een reeks kopieer- en invoeginstructies:

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

Kopieerinstructies: de 7 bits X geven aan welke bytes voor offset en grootte aanwezig zijn. De offset is maximaal 4 bytes en de grootte maximaal 3 bytes. Als de grootte nul is, betekent dit 0x10000 (65536) bytes.

Invoeginstructies: de 7 L-bits geven de lengte van de letterlijke gegevens aan (1-127 bytes). L=0 is gereserveerd en ongeldig.

### DeltaApplier

```php
use Pitmaster\Pack\DeltaApplier;

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

De `DeltaApplier`:
1. Leest de verwachte grootte van het basisobject en de resultaatgrootte uit de delta-koptekst (gecodeerd met LEB128)
2. Doorloopt de instructies:
   - Kopiëren: haalt de offset en grootte op en kopieert bytes uit de inhoud van het basisobject
   - Invoegen: haalt de lengte op en kopieert de letterlijke bytes uit de deltagegevens
3. Controleert of de resultaatgrootte overeenkomt met de verwachte grootte

### Deltaketens

Het basisobject van een deltacompressie kan zelf ook deltacompressie gebruiken. `PackFile::read()` en `readAtOffset()` volgen de keten:

1. Lees de vermelding. Als het een basistype is (commit, tree, blob, tag), retourneer deze.
2. Bij OFS_DELTA: bereken de base-offset (huidige offset min de gecodeerde negatieve offset), lees de basisvermelding en herhaal.
3. Bij REF_DELTA: zoek het basisobject op hash op in de index van hetzelfde packbestand en herhaal.
4. Pas de delta-instructies toe op het opgeloste basisobject.
5. Beperk de keten met `PITMASTER_MAX_DELTA_CHAIN` (standaard 50) om eindeloze ketens te voorkomen.

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

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

## PackWriter

Pitmaster kan packbestanden schrijven voor netwerkbewerkingen (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
```

De `PackWriter`:
1. Verzamelt objecten voor het packbestand
2. Serialiseert elk object met een varint-koptekst voor type en grootte
3. Comprimeert de inhoud met zlib
4. Schrijft de PACK-koptekst, vermeldingen en de trailer SHA-1

Momenteel worden alleen basisobjecten geschreven (geen deltacompressie). Deltacompressie is een optimalisatie die later kan worden toegevoegd; laat `git gc` de objecten opnieuw inpakken voor efficiëntere opslag.

## PackEnumerator

Doorloop alle objecten in een packbestand, in indexvolgorde:

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

Elk item is een opgelost `GitObject`.

## MultiPackIndex

Voor repositories met veel packbestanden biedt de multi-pack-index (MIDX) één zoekactie voor alle packbestanden.

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

Het MIDX-bestand (`.git/objects/pack/multi-pack-index`) bevat:
- Een fan-outtabel (zoals in packindex v2)
- Object-ID's, gesorteerd over alle packbestanden
- Bestandsnamen van packbestanden en de packtoewijzing per object
- Offsets in de afzonderlijke packbestanden

`MultiPackIndex::open($path)` parseert een MIDX-bestand en biedt `findObject($hex)` en `packNames()`. Zoekacties naar objecten in de repository gebruiken deze niet: de objectdatabase leest altijd de afzonderlijke bestanden van `.idx`.

## CommitGraph

Het commit-graph-bestand versnelt het doorlopen van de commitgeschiedenis en het berekenen van de mergebasis.

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

Het staat in `.git/objects/info/commit-graph` en bevat:
- Commit-OID's in gesorteerde volgorde
- Informatie over ouders (geïndexeerd, zodat objecten niet hoeven te worden gelezen)
- Generatienummers (voor snellere bereikbaarheidscontroles)
- Tijdstempels van commits

Als dit bestand aanwezig is, leest de berekening van de mergebasis achter `Repository::merge()`, `mergeBase()`, `isBranchMerged()` en de controle op fast-forward bij push de ouderkoppelingen uit de commit-graph in plaats van afzonderlijke commitobjecten te lezen. `CommitWalker` (log) gebruikt dit bestand niet.

## Gehele getallen met variabele lengte

Packbestanden gebruiken meerdere coderingen voor gehele getallen met variabele lengte:

### Varint van Git (kopteksten voor type en grootte)

Codering waarbij de MSB aangeeft dat er meer bytes volgen:

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

Gebruikt in delta-instructiekoppen voor de basisgrootte en resultaatgrootte:

```php
use Pitmaster\Encoding\Leb128;

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

### BinaryReader

Laag-niveau byte stream met positietracking:

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