<?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\version_control;
/**
* 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 = [];
/**
* Versions recently rebuilt as the base of a delta, oldest first, keyed
* by packfile path and position for a delta that gives its base by
* position and by object name for one that names it. Git stores
* successive versions of a folder or file as differences in chains up
* to fifty steps deep, and walking a history reads each version in
* turn; rebuilt from the start each time, a chain is unpacked again for
* every step along it, and a clone of a long history spent most of its
* time doing that. Kept here, the next version down the chain is one
* difference away.
* @var array
*/
private $base_cache = [];
/**
* Total bytes of the bodies held in base_cache
* @var int
*/
private $base_cache_bytes = 0;
/**
* $entry_ends holds, for each packfile path, where each entry in it
* ends and which object starts at each position, as entryEnds works
* them out from the packfile's index
* @var array
*/
private $entry_ends = [];
/**
* CHECKSUM_LENGTH the length of the SHA-1 checksum, the 20-byte hash
* of everything before it, that closes a packfile
*/
const CHECKSUM_LENGTH = 20;
/**
* 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.
* Each step of a chain holds its own difference while the version it
* was built against is read below it, so the memory a read needs
* grows with the chain. Git itself writes chains no deeper than this,
* and a thousand steps of a large file was enough to exhaust two
* gigabytes while serving one pull.
*/
const MAX_DELTA_DEPTH = 50;
/**
* Number of compressed bytes read from a packfile per decompression step
*/
const INFLATE_CHUNK = 65536;
/**
* Most bytes of rebuilt bases kept in base_cache; the oldest are let go
* first once this is passed
*/
const BASE_CACHE_BYTES = 16000000;
/**
* Fewest compressed bytes read in one step. Most folders and changes
* between versions are a few hundred bytes, so a read sized to the
* object rather than to INFLATE_CHUNK saves copying tens of kilobytes
* that are not used.
*/
const SMALLEST_READ = 512;
/**
* 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;
}
/**
* storedEntry gives an object's entry in a packfile exactly as it is
* stored there, still compressed, so GitUploadPack can copy it into a
* clone's pack without decompressing, rebuilding and compressing it
* again, which took most of a clone's time. A delta, an object stored
* as its differences from another, comes back with the name of the
* object it is built on, whether the packfile gives that object by
* name or by its position in the file. The entry ends where the next
* entry in the file starts, or where the packfile's closing checksum
* starts.
*
* @param string $sha hex object name to look up
* @return array|null ["kind" => the packfile type number, 1 to 4 for
* an object stored whole, 6 or 7 for a delta, "size" => the
* object's or the delta's size once decompressed, "base" => hex
* name of a delta's base or "", "data" => the compressed bytes],
* or null when no packfile holds the object
*/
public function storedEntry($sha)
{
$raw_sha = @hex2bin($sha);
if ($raw_sha === false || strlen($raw_sha) != 20) {
return null;
}
foreach ($this->packPairs() as $pair) {
$offset = $this->findOffset($pair["index"], $raw_sha);
if ($offset === null) {
continue;
}
$ends = $this->entryEnds($pair);
$handle = $this->packHandle($pair["pack"]);
if (fseek($handle, $offset) != 0) {
return null;
}
$first = ord($this->readByte($handle));
$kind = ($first >> 4) & 0x07;
$size = $first & 0x0f;
$shift = 4;
while ($first & 0x80) {
$first = ord($this->readByte($handle));
$size |= ($first & 0x7f) << $shift;
$shift += 7;
}
$base = "";
if ($kind == self::TYPE_OFS_DELTA) {
$base_offset = $offset - $this->readBaseDistance($handle);
$base = $ends["names"][$base_offset] ?? "";
if ($base === "") {
return null;
}
} else if ($kind == self::TYPE_REF_DELTA) {
$base = bin2hex($this->readBytes($handle, 20));
}
$data_start = ftell($handle);
$data_end = $ends["ends"][$offset] ?? 0;
if ($data_end <= $data_start) {
return null;
}
$data = $this->readBytes($handle, $data_end - $data_start);
return ["kind" => $kind, "size" => $size, "base" => $base,
"data" => $data];
}
return null;
}
/**
* entryEnds works out, once per packfile, where each entry ends and
* which object starts at each position, from the packfile's index.
* Sorting the positions the index lists puts each entry next to the one
* after it, whose start is the first's end; the last entry ends where
* the packfile's 20-byte closing checksum begins. storedEntry uses the
* ends to copy an entry and the names to name a delta's base.
*
* @param array $pair ["index" => idx path, "pack" => pack path]
* @return array ["ends" => position => end position, "names" =>
* position => hex object name]
*/
private function entryEnds($pair)
{
if (isset($this->entry_ends[$pair["pack"]])) {
return $this->entry_ends[$pair["pack"]];
}
$info = $this->indexInfo($pair["index"]);
$names = [];
for ($rank = 0; $rank < $info["count"]; $rank++) {
$names[$this->offsetAt($info, $rank)] = bin2hex(substr(
$info["contents"], self::FANOUT_END + $rank * 20, 20));
}
ksort($names);
$positions = array_keys($names);
$ends = [];
$last = count($positions) - 1;
foreach ($positions as $index => $position) {
$ends[$position] = ($index < $last) ? $positions[$index + 1] :
filesize($pair["pack"]) - self::CHECKSUM_LENGTH;
}
$this->entry_ends[$pair["pack"]] = ["ends" => $ends,
"names" => $names];
return $this->entry_ends[$pair["pack"]];
}
/**
* 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;
}
/**
* Says whether a position in a packfile looks like the start of an
* object at all. A size beyond what any object may be has two very
* different causes: an object that really is that big, or a read
* standing somewhere that is not an object. The kind recorded in the
* first byte tells them apart, since only seven kinds exist and two of
* those are never written, and a position past the end of the file
* settles it outright.
*
* @param string $pack_path path to the packfile
* @param int $offset byte position being read
* @return string what was found there, in words
*/
private function describeOffset($pack_path, $offset)
{
$size = filesize($pack_path);
if ($size === false) {
return "packsize=unknown";
}
if ($offset >= $size) {
return "packsize=" . $size . " verdict=past-the-end";
}
$handle = $this->packHandle($pack_path);
$held = ftell($handle);
if (fseek($handle, $offset) != 0) {
return "packsize=" . $size . " verdict=unreachable";
}
$first = ord($this->readByte($handle));
fseek($handle, $held);
$kind = ($first >> 4) & 0x07;
$known = [1 => "commit", 2 => "tree", 3 => "blob", 4 => "tag",
6 => "delta-by-position", 7 => "delta-by-name"];
if (!isset($known[$kind])) {
return "packsize=" . $size . " kind=" . $kind .
" verdict=not-an-object-header";
}
return "packsize=" . $size . " kind=" . $known[$kind] .
" verdict=looks-like-an-object";
}
/**
* 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) {
/* The size is read from the packfile itself, so a size
beyond what any object may be means the read is not
standing where an object begins. Saying where it was
standing turns a bare complaint into something a
person can follow. */
throw new \Exception("git_object_too_large size=" . $size .
" offset=" . $offset . " pack=" . basename($pack_path) .
" " . $this->describeOffset($pack_path, $offset));
}
}
if ($type == self::TYPE_OFS_DELTA) {
/* The version below is read before this step's difference is
unpacked, so a chain holds one difference at a time rather
than one for every step still waiting. */
$base_offset = $offset - $this->readBaseDistance($handle);
$delta_at = ftell($handle);
$base_key = $pack_path . ":" . $base_offset;
$base = $this->base_cache[$base_key] ?? null;
if ($base === null) {
$base = $this->readAtOffset($pack_path, $base_offset,
$depth + 1);
$this->keepBase($base_key, $base);
}
if (fseek($handle, $delta_at) != 0) {
throw new \Exception("git_bad_pack_offset");
}
$delta = $this->inflateExactly($handle, $size);
$rebuilt = GitDelta::apply($base["body"], $delta);
$delta = null;
return ["type" => $base["type"], "body" => $rebuilt];
}
if ($type == self::TYPE_REF_DELTA) {
$base_sha = bin2hex($this->readBytes($handle, 20));
$delta = $this->inflateExactly($handle, $size);
$base = $this->base_cache[$base_sha] ?? null;
if ($base === null) {
$base = $this->repository->readObject($base_sha);
if ($base === null) {
throw new \Exception("git_delta_base_missing");
}
$this->keepBase($base_sha, $base);
}
return ["type" => $base["type"],
"body" => GitDelta::apply($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)];
}
/**
* Remembers a version just rebuilt as the base of a delta, letting go
* of the oldest ones kept once BASE_CACHE_BYTES would be passed. A
* version larger than that is not kept at all.
*
* @param string $key packfile path and position of the version, or
* its object name
* @param array $base ["type" => kind name, "body" => raw bytes]
*/
private function keepBase($key, $base)
{
$length = strlen($base["body"]);
if ($length > self::BASE_CACHE_BYTES) {
return;
}
while ($this->base_cache_bytes + $length > self::BASE_CACHE_BYTES &&
!empty($this->base_cache)) {
$oldest = array_key_first($this->base_cache);
$this->base_cache_bytes -=
strlen($this->base_cache[$oldest]["body"]);
unset($this->base_cache[$oldest]);
}
$this->base_cache[$key] = $base;
$this->base_cache_bytes += $length;
}
/**
* 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;
}
/**
* 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 = "";
$step = min(self::INFLATE_CHUNK,
max(self::SMALLEST_READ, $size + 64));
while (strlen($out) < $size) {
$chunk = fread($handle, $step);
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;
}
}
- Yioop Repo - Seekquarry