<?php
/**
* SeekQuarry/Yioop --
* Open Source Pure PHP Search Engine, Crawler, and Indexer
*
* Copyright (C) 2009 - 2026 Chris Pollett chris@pollett.org
*
* LICENSE:
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*
* END LICENSE
*
* @author Chris Pollett chris@pollett.org
* @license https://www.gnu.org/licenses/ GPL3
* @link https://www.seekquarry.com/
* @copyright 2009 - 2026
* @filesource
*/
namespace seekquarry\yioop\library;
/**
* Reads objects that Git has collected into packfiles, the compact form
* objects take after a repository is repacked. A packfile is a single file
* of compressed objects paired with an index file that says where each
* object lives inside it. This class finds an object by name through the
* index, reads it out of the packfile, and where the object was stored as a
* difference against another object (a "delta") rebuilds the whole object
* from that chain of differences.
*
* It is the companion to GitRepository: that class reads loose objects and
* refs, and hands off to this class when an object is not present as a loose
* file. Like GitRepository it only ever reads, never writes or executes the
* repository, and it works against open file handles rather than loading a
* whole packfile into memory, so a large repository does not become a large
* memory cost. Every step is bounded: objects decompress under a fixed size
* limit, delta chains are followed only to a fixed depth, and offsets read
* from the files are checked before they are used, so a corrupt or hostile
* pack cannot exhaust memory or loop forever.
*
* @author Chris Pollett
*/
class GitPackReader
{
/**
* Absolute path to the bare repository directory
* @var string
*/
public $repo_path;
/**
* The GitRepository this reader belongs to, used to fetch the base of a
* delta that refers to its base by object name rather than by position
* @var object
*/
public $repository;
/**
* Open packfile handles keyed by packfile path, so a packfile is opened
* once and reused across many object reads
* @var array
*/
private $pack_handles = [];
/**
* Parsed index summaries keyed by index path, each holding the data
* needed to look an object name up quickly
* @var array
*/
private $index_info = [];
/**
* Object type numbers as they appear in a packfile header
*/
const TYPE_COMMIT = 1;
const TYPE_TREE = 2;
const TYPE_BLOB = 3;
const TYPE_TAG = 4;
const TYPE_OFS_DELTA = 6;
const TYPE_REF_DELTA = 7;
/**
* Map from packfile type number to the object kind name
*/
const TYPE_NAMES = [self::TYPE_COMMIT => "commit",
self::TYPE_TREE => "tree", self::TYPE_BLOB => "blob",
self::TYPE_TAG => "tag"];
/**
* Bytes occupied by the index header and its 256-entry fanout table,
* after which the sorted object names begin
*/
const FANOUT_END = 8 + 256 * 4;
/**
* Deepest chain of deltas this reader will follow before giving up,
* a guard against a circular or pathologically deep chain
*/
const MAX_DELTA_DEPTH = 1000;
/**
* Number of compressed bytes read from a packfile per decompression step
*/
const INFLATE_CHUNK = 65536;
/**
* Sets up a packfile reader for the given bare repository.
*
* @param string $repo_path path to the bare repository directory
* @param object $repository the GitRepository that owns this reader,
* used to resolve a delta base given only its object name
*/
public function __construct($repo_path, $repository)
{
$this->repo_path = rtrim($repo_path, "/");
$this->repository = $repository;
}
/**
* Reads a single object out of whichever packfile contains it, given its
* object name, and returns its kind and raw contents. Returns null when
* the object is in none of the repository's packfiles.
*
* @param string $sha hex object name to read
* @return array|null ["type" => kind name, "body" => raw bytes], or null
* if no packfile holds the object
*/
public function readObject($sha)
{
$raw_sha = @hex2bin($sha);
if ($raw_sha === false || strlen($raw_sha) != 20) {
throw new \Exception("git_bad_object_name");
}
foreach ($this->packPairs() as $pair) {
$offset = $this->findOffset($pair["index"], $raw_sha);
if ($offset !== null) {
return $this->readAtOffset($pair["pack"], $offset, 0);
}
}
return null;
}
/**
* Lists the packfiles in the repository as index and packfile path
* pairs. Only packfiles that have a matching index are returned, since
* an object cannot be located without its index.
*
* @return array list of ["index" => idx path, "pack" => pack path]
*/
private function packPairs()
{
$pairs = [];
$pack_dir = $this->repo_path . "/objects/pack";
if (!is_dir($pack_dir)) {
return $pairs;
}
foreach (glob($pack_dir . "/pack-*.idx") as $index_path) {
$pack_path = substr($index_path, 0, -4) . ".pack";
if (is_file($pack_path)) {
$pairs[] = ["index" => $index_path, "pack" => $pack_path];
}
}
return $pairs;
}
/**
* Finds the position of an object inside a packfile by looking its name
* up in the packfile's index, or returns null if the index does not list
* it. The index stores object names in sorted order with a small lookup
* table on the first name byte, so the search goes straight to a narrow
* range and then bisects it.
*
* @param string $index_path path to the packfile index
* @param string $raw_sha 20 byte object name to look up
* @return int|null byte position of the object in the packfile, or null
*/
private function findOffset($index_path, $raw_sha)
{
$info = $this->indexInfo($index_path);
$first_byte = ord($raw_sha[0]);
$low = ($first_byte == 0) ? 0 : $info["fanout"][$first_byte - 1];
$high = $info["fanout"][$first_byte];
$names = $info["contents"];
$names_start = self::FANOUT_END;
while ($low < $high) {
$mid = intdiv($low + $high, 2);
$name = substr($names, $names_start + $mid * 20, 20);
if ($name === $raw_sha) {
return $this->offsetAt($info, $mid);
}
if ($name < $raw_sha) {
$low = $mid + 1;
} else {
$high = $mid;
}
}
return null;
}
/**
* Reads the stored byte position of the object at a given rank within a
* packfile index. Positions too large for the main four-byte table are
* held in a separate eight-byte table, which this follows when needed.
*
* @param array $info parsed index summary
* @param int $rank position of the object within the sorted names
* @return int byte position of the object in the packfile
*/
private function offsetAt($info, $rank)
{
$small = unpack("N", substr($info["contents"],
$info["offsets_start"] + $rank * 4, 4))[1];
if (($small & 0x80000000) == 0) {
return $small;
}
$large_rank = $small & 0x7fffffff;
return unpack("J", substr($info["contents"],
$info["large_start"] + $large_rank * 8, 8))[1];
}
/**
* Loads and remembers the parts of a packfile index needed for lookups:
* the fanout table, the whole index contents, the object count, and
* where the names, positions, and large-position tables begin. The index
* is far smaller than its packfile, so it is read in full once and kept.
*
* @param string $index_path path to the packfile index
* @return array parsed index summary
*/
private function indexInfo($index_path)
{
if (isset($this->index_info[$index_path])) {
return $this->index_info[$index_path];
}
$contents = (string)file_get_contents($index_path);
if (substr($contents, 0, 8) !== "\377tOc\0\0\0\2") {
throw new \Exception("git_unsupported_index");
}
$fanout = array_values(unpack("N256",
substr($contents, 8, 256 * 4)));
$count = $fanout[255];
$names_start = self::FANOUT_END;
$offsets_start = $names_start + $count * 20 + $count * 4;
$large_start = $offsets_start + $count * 4;
$info = ["contents" => $contents, "fanout" => $fanout,
"count" => $count, "offsets_start" => $offsets_start,
"large_start" => $large_start];
$this->index_info[$index_path] = $info;
return $info;
}
/**
* Reads the object stored at a given position in a packfile and returns
* its kind and raw contents, rebuilding it from its base when it was
* stored as a delta. The depth count rises with each base followed so a
* chain of deltas cannot be followed without limit.
*
* @param string $pack_path path to the packfile
* @param int $offset byte position of the object in the packfile
* @param int $depth how many delta bases have been followed so far
* @return array ["type" => kind name, "body" => raw bytes]
*/
private function readAtOffset($pack_path, $offset, $depth)
{
if ($depth > self::MAX_DELTA_DEPTH) {
throw new \Exception("git_delta_too_deep");
}
$handle = $this->packHandle($pack_path);
if ($offset < 0 || fseek($handle, $offset) != 0) {
throw new \Exception("git_bad_pack_offset");
}
$first = ord($this->readByte($handle));
$type = ($first >> 4) & 0x07;
$size = $first & 0x0f;
$shift = 4;
while ($first & 0x80) {
$first = ord($this->readByte($handle));
$size |= ($first & 0x7f) << $shift;
$shift += 7;
if ($size > GitRepository::MAX_OBJECT_SIZE) {
throw new \Exception("git_object_too_large");
}
}
if ($type == self::TYPE_OFS_DELTA) {
$base_offset = $offset - $this->readBaseDistance($handle);
$delta = $this->inflateExactly($handle, $size);
$base = $this->readAtOffset($pack_path, $base_offset, $depth + 1);
return ["type" => $base["type"],
"body" => $this->applyDelta($base["body"], $delta)];
}
if ($type == self::TYPE_REF_DELTA) {
$base_sha = bin2hex($this->readBytes($handle, 20));
$delta = $this->inflateExactly($handle, $size);
$base = $this->repository->readObject($base_sha);
if ($base === null) {
throw new \Exception("git_delta_base_missing");
}
return ["type" => $base["type"],
"body" => $this->applyDelta($base["body"], $delta)];
}
if (!isset(self::TYPE_NAMES[$type])) {
throw new \Exception("git_unknown_object_type");
}
return ["type" => self::TYPE_NAMES[$type],
"body" => $this->inflateExactly($handle, $size)];
}
/**
* Reads the distance back to a delta's base for a delta that names its
* base by position. The distance is stored in a compact form spread over
* one or more bytes, which this reassembles.
*
* @param resource $handle open packfile handle positioned at the distance
* @return int how far back from the delta the base object sits
*/
private function readBaseDistance($handle)
{
$byte = ord($this->readByte($handle));
$distance = $byte & 0x7f;
while ($byte & 0x80) {
$byte = ord($this->readByte($handle));
$distance = (($distance + 1) << 7) | ($byte & 0x7f);
}
return $distance;
}
/**
* Rebuilds a full object from a base object and a delta, the list of
* copy-from-base and insert-new instructions Git uses to record one
* object as a change to another. The rebuilt size is checked against the
* size the delta declares and against the overall object size limit.
*
* @param string $base contents of the base object
* @param string $delta the delta instruction stream
* @return string the rebuilt object contents
*/
private function applyDelta($base, $delta)
{
$pos = 0;
$total = strlen($delta);
$this->readDeltaSize($delta, $pos, $total);
$target_size = $this->readDeltaSize($delta, $pos, $total);
if ($target_size > GitRepository::MAX_OBJECT_SIZE) {
throw new \Exception("git_object_too_large");
}
$out = "";
while ($pos < $total) {
$op = ord($delta[$pos]);
$pos++;
if ($op & 0x80) {
$out .= $this->copyFromBase($base, $delta, $pos, $total, $op);
} else if ($op != 0) {
if ($pos + $op > $total) {
throw new \Exception("git_delta_corrupt");
}
$out .= substr($delta, $pos, $op);
$pos += $op;
} else {
throw new \Exception("git_delta_corrupt");
}
if (strlen($out) > GitRepository::MAX_OBJECT_SIZE) {
throw new \Exception("git_object_too_large");
}
}
if (strlen($out) !== $target_size) {
throw new \Exception("git_delta_corrupt");
}
return $out;
}
/**
* Carries out one copy instruction from a delta, copying a run of bytes
* from the base object. The instruction's leading byte says which of the
* following bytes give the start position and length of the run.
*
* @param string $base contents of the base object
* @param string $delta the delta instruction stream
* @param int &$pos read position in the delta, advanced past this
* instruction's operand bytes
* @param int $total length of the delta stream
* @param int $op the copy instruction's leading byte
* @return string the bytes copied from the base
*/
private function copyFromBase($base, $delta, &$pos, $total, $op)
{
$copy_offset = 0;
$copy_size = 0;
$offset_bits = [0x01 => 0, 0x02 => 8, 0x04 => 16, 0x08 => 24];
foreach ($offset_bits as $flag => $shift) {
if ($op & $flag) {
if ($pos >= $total) {
throw new \Exception("git_delta_corrupt");
}
$copy_offset |= ord($delta[$pos]) << $shift;
$pos++;
}
}
$size_bits = [0x10 => 0, 0x20 => 8, 0x40 => 16];
foreach ($size_bits as $flag => $shift) {
if ($op & $flag) {
if ($pos >= $total) {
throw new \Exception("git_delta_corrupt");
}
$copy_size |= ord($delta[$pos]) << $shift;
$pos++;
}
}
if ($copy_size == 0) {
$copy_size = 0x10000;
}
if ($copy_offset + $copy_size > strlen($base)) {
throw new \Exception("git_delta_corrupt");
}
return substr($base, $copy_offset, $copy_size);
}
/**
* Reads one of the two sizes recorded at the start of a delta (the size
* of the base and the size of the result), each held as a little-endian
* variable-length number.
*
* @param string $delta the delta instruction stream
* @param int &$pos read position in the delta, advanced past the number
* @param int $total length of the delta stream
* @return int the size that was read
*/
private function readDeltaSize($delta, &$pos, $total)
{
$result = 0;
$shift = 0;
do {
if ($pos >= $total) {
throw new \Exception("git_delta_corrupt");
}
$byte = ord($delta[$pos]);
$pos++;
$result |= ($byte & 0x7f) << $shift;
$shift += 7;
} while ($byte & 0x80);
return $result;
}
/**
* Decompresses exactly the given number of bytes of object data from the
* current position in a packfile, stopping with an error if it would run
* past the object size limit or cannot produce the expected amount.
*
* @param resource $handle open packfile handle at the compressed data
* @param int $size number of bytes the object decompresses to
* @return string the decompressed object data
*/
private function inflateExactly($handle, $size)
{
if ($size > GitRepository::MAX_OBJECT_SIZE) {
throw new \Exception("git_object_too_large");
}
$context = inflate_init(ZLIB_ENCODING_DEFLATE);
if ($context === false) {
throw new \Exception("git_object_inflate_failed");
}
$out = "";
while (strlen($out) < $size) {
$chunk = fread($handle, self::INFLATE_CHUNK);
if ($chunk === false || $chunk === "") {
break;
}
$piece = inflate_add($context, $chunk);
if ($piece === false) {
throw new \Exception("git_object_inflate_failed");
}
$out .= $piece;
if (strlen($out) > GitRepository::MAX_OBJECT_SIZE) {
throw new \Exception("git_object_too_large");
}
}
if (strlen($out) !== $size) {
throw new \Exception("git_object_corrupt");
}
return $out;
}
/**
* Returns the open handle for a packfile, opening it on first use and
* reusing it afterwards.
*
* @param string $pack_path path to the packfile
* @return resource the open file handle
*/
private function packHandle($pack_path)
{
if (empty($this->pack_handles[$pack_path])) {
$handle = fopen($pack_path, "r");
if ($handle === false) {
throw new \Exception("git_pack_open_failed");
}
$this->pack_handles[$pack_path] = $handle;
}
return $this->pack_handles[$pack_path];
}
/**
* Reads a single byte from a packfile handle, treating an unexpected end
* of file as a corrupt packfile.
*
* @param resource $handle open packfile handle
* @return string the one byte that was read
*/
private function readByte($handle)
{
return $this->readBytes($handle, 1);
}
/**
* Reads an exact number of bytes from a packfile handle, treating a short
* read as a corrupt packfile.
*
* @param resource $handle open packfile handle
* @param int $count number of bytes to read
* @return string the bytes that were read
*/
private function readBytes($handle, $count)
{
$data = fread($handle, $count);
if ($data === false || strlen($data) != $count) {
throw new \Exception("git_pack_truncated");
}
return $data;
}
}
(c) 2026 Seekquarry - Open Source Search Engine Software