<?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;
    }
}
