<?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 the contents of a bare Git repository directly from the files on
 * disk, without running the git program. It can list the branches in a
 * repository and read the commits, folder listings (trees), and file
 * contents (blobs) those branches point at.
 *
 * The repository's stored history is treated as read-only data: nothing in
 * this class ever changes a commit, tree, blob, or ref, and nothing is ever
 * executed from the repository, so a repository pushed by an untrusted user
 * cannot run code on the server. The one thing this class does write is the
 * empty skeleton of a brand new bare repository, which is just folders and a
 * couple of small text files; it never touches the contents of a repository
 * that already exists. Each object is decompressed under a fixed size limit
 * so that a corrupt or deliberately crafted object cannot use up all the
 * server's memory.
 *
 * This class reads loose objects (the form a freshly pushed object takes,
 * one compressed file per object) and both loose and packed refs. Objects
 * that have been collected into packfiles are read by a separate companion
 * class, GitPackReader; when an object is not present as a loose file,
 * readObject hands off to that reader, so callers see one combined view of
 * the repository's objects.
 *
 * @author Chris Pollett
 */
class GitRepository
{
    /**
     * Absolute path to the bare repository directory (the folder that
     * directly contains HEAD, the objects folder, and the refs folder)
     * @var string
     */
    public $repo_path;
    /**
     * Reader for objects stored in packfiles, created the first time an
     * object is not found as a loose file
     * @var object
     */
    private $pack_reader;
    /**
     * One megabyte expressed in bytes, used to state the object size limit
     * in readable units
     */
    const ONE_MEGABYTE = 1048576;
    /**
     * Largest number of bytes a single object is allowed to decompress to.
     * Reading stops and an error is thrown past this point so that a
     * corrupt or hostile object cannot exhaust memory (64 megabytes).
     */
    const MAX_OBJECT_SIZE = 64 * self::ONE_MEGABYTE;
    /**
     * Number of compressed input bytes fed to the decompressor per step.
     * Feeding the input in steps lets the size limit be checked as output
     * is produced rather than only after the whole object is expanded.
     */
    const INFLATE_CHUNK = 65536;
    /**
     * Number of hex characters in a full object name (a 20 byte SHA-1
     * written as hexadecimal)
     */
    const SHA_HEX_LENGTH = 40;
    /**
     * Number of bytes in a full object name in its raw form (a SHA-1 is
     * 20 bytes), the form used inside tree records
     */
    const SHA_RAW_LENGTH = 20;
    /**
     * Largest number of commits the statistics walk will follow before it
     * stops, so a very long history cannot make the walk run for a long time
     */
    const STATISTICS_COMMIT_CAP = 20000;
    /**
     * Largest number of tree entries the statistics file-type walk will
     * visit before it stops, so a repository with a great many files cannot
     * make the walk run for a long time
     */
    const STATISTICS_FILE_CAP = 50000;
    /**
     * Deepest chain of one annotated tag pointing at another that peeling
     * will follow before giving up, a guard against a cycle
     */
    const MAX_TAG_DEPTH = 100;
    /**
     * Branch name a freshly created repository's HEAD points at when no
     * other name is supplied
     */
    const DEFAULT_BRANCH = "main";
    /**
     * Permission bits used for the folders of a freshly created repository.
     * Yioop creates web-writable files and folders so the web server can
     * read and write them whoever owns them, which is what later lets an
     * authorised push write objects and refs into the repository.
     */
    const DIRECTORY_PERMISSIONS = 0777;
    /**
     * Number of bytes in one block of a tar archive. A tar file is a series
     * of these fixed-size blocks: one holds each file's header, and each
     * file's contents are padded up to a whole number of them.
     */
    const TAR_BLOCK = 512;
    /**
     * Longest file path, in characters, that fits in a tar header's main
     * name field. A longer path is split, with the leading folders moved
     * into the header's separate prefix field.
     */
    const TAR_NAME_LENGTH = 100;
    /**
     * Largest total size, in bytes, of the files a downloadable archive may
     * hold before the build is refused. This keeps a request to zip up a
     * very large repository from exhausting the server's memory; someone
     * wanting the whole of such a repository can clone it instead (256
     * megabytes).
     */
    const MAX_ARCHIVE_SIZE = 256 * self::ONE_MEGABYTE;
    /**
     * Sets up a reader for the bare repository stored at the given path.
     *
     * @param string $repo_path path to the bare repository directory
     */
    public function __construct($repo_path)
    {
        $this->repo_path = rtrim($repo_path, "/");
    }
    /**
     * Creates the empty skeleton of a bare repository at this path if one is
     * not already there: the HEAD pointer, the configuration file that marks
     * the folder as a bare repository, and the folders Git keeps its objects
     * and refs in. This is the pure-PHP equivalent of "git init --bare"; it
     * only writes folders and small text files and runs nothing, so no part
     * of Git executes on the server, and a repository that already exists is
     * left exactly as it was.
     *
     * @param string $default_branch name the new repository's HEAD should
     *     point at before its first commit arrives
     * @return bool true if a new repository was created, false if one was
     *     already present
     */
    public function initBare($default_branch = self::DEFAULT_BRANCH)
    {
        if ($this->hasExistingGitContent()) {
            return false;
        }
        $folders = ["objects", "objects/info", "objects/pack", "refs",
            "refs/heads", "refs/tags"];
        foreach ($folders as $folder) {
            $full = $this->repo_path . "/" . $folder;
            if (!is_dir($full)) {
                mkdir($full, self::DIRECTORY_PERMISSIONS, true);
            }
        }
        $head_file = $this->repo_path . "/HEAD";
        if (!file_exists($head_file)) {
            file_put_contents($head_file,
                "ref: refs/heads/" . $default_branch . "\n");
        }
        $config_file = $this->repo_path . "/config";
        if (!file_exists($config_file)) {
            file_put_contents($config_file,
                "[core]\n\trepositoryformatversion = 0\n" .
                "\tfilemode = true\n\tbare = true\n");
        }
        return true;
    }
    /**
     * Decides whether a piece of data a client is trying to push is allowed
     * under the configured size caps. A cap of zero means that cap is off.
     * The blob cap bounds any single object written; the push cap bounds a
     * whole pack file; the repository cap bounds how large the repository is
     * allowed to grow once this data is added. This is kept as plain
     * arithmetic with no side effects so it can be checked on its own.
     *
     * @param int $content_length bytes about to be written
     * @param int $repo_size bytes the repository already holds
     * @param bool $is_pack whether the data being written is a pack file
     * @param int $blob_cap largest a single object may be, 0 for no cap
     * @param int $push_cap largest a single pack may be, 0 for no cap
     * @param int $repo_cap largest the repository may grow to, 0 for no cap
     * @return bool whether the write stays within every cap that is on
     */
    public static function withinPushLimits($content_length, $repo_size,
        $is_pack, $blob_cap, $push_cap, $repo_cap)
    {
        if ($blob_cap > 0 && $content_length > $blob_cap) {
            return false;
        }
        if ($is_pack && $push_cap > 0 && $content_length > $push_cap) {
            return false;
        }
        if ($repo_cap > 0 && $repo_size + $content_length > $repo_cap) {
            return false;
        }
        return true;
    }
    /**
     * Reports whether the target folder already holds a Git repository in
     * any form: the bare layout this class creates, a partial version of it,
     * or an ordinary checkout with a .git folder. initBare checks this so
     * that pointing a git page at a path that is already a repository, for
     * example through a page path setting, never overwrites or damages it.
     *
     * @return bool true if the folder already contains Git repository data
     */
    private function hasExistingGitContent()
    {
        return is_file($this->repo_path . "/HEAD") ||
            is_dir($this->repo_path . "/objects") ||
            is_dir($this->repo_path . "/refs") ||
            is_dir($this->repo_path . "/.git") ||
            is_file($this->repo_path . "/config");
    }
    /**
     * Reports whether the path given to this reader actually looks like a
     * bare repository, that is whether it has the HEAD file and objects
     * folder a repository needs.
     *
     * @return bool true if the path has the expected repository contents
     */
    public function isRepository()
    {
        return is_file($this->repo_path . "/HEAD") &&
            is_dir($this->repo_path . "/objects");
    }
    /**
     * Classifies the folder this reader was pointed at as one of three
     * states, so a caller can decide whether a git request should be served
     * from, started in, or refused at the folder. The states are: an
     * existing bare repository ("repository"); a folder holding no content
     * beyond directory entries and dot files such as a macOS .DS_Store, in
     * which a repository could be started ("empty"); or a folder already
     * holding other content that is not a repository ("occupied").
     *
     * @return string one of "repository", "empty", or "occupied"
     */
    public function folderState()
    {
        if ($this->isRepository()) {
            return "repository";
        }
        $entries = @scandir($this->repo_path);
        if ($entries !== false) {
            foreach ($entries as $entry) {
                if ($entry[0] !== ".") {
                    return "occupied";
                }
            }
        }
        return "empty";
    }
    /**
     * Returns the name of the branch the repository's HEAD currently points
     * at, for example "master". Returns the empty string when HEAD points
     * straight at a commit rather than at a branch.
     *
     * @return string the current branch name, or "" if HEAD is detached
     */
    public function headBranch()
    {
        $head_text = trim((string)@file_get_contents(
            $this->repo_path . "/HEAD"));
        if (str_starts_with($head_text, "ref: refs/heads/")) {
            return substr($head_text, strlen("ref: refs/heads/"));
        }
        return "";
    }
    /**
     * Returns the branches in the repository as a list mapping each branch
     * name to the object name of the commit it points at. Both branches
     * stored as their own files and branches collected into the packed-refs
     * file are included, with a branch's own file taking precedence.
     *
     * @return array branch name => commit object name (hex SHA-1)
     */
    public function branches()
    {
        $branches = [];
        $packed = $this->repo_path . "/packed-refs";
        if (is_file($packed)) {
            $lines = explode("\n", (string)@file_get_contents($packed));
            foreach ($lines as $line) {
                $line = trim($line);
                if ($line == "" || $line[0] == "#" || $line[0] == "^") {
                    continue;
                }
                $parts = explode(" ", $line, 2);
                if (count($parts) == 2 &&
                    str_starts_with($parts[1], "refs/heads/")) {
                    $name = substr($parts[1], strlen("refs/heads/"));
                    $branches[$name] = $parts[0];
                }
            }
        }
        $heads_dir = $this->repo_path . "/refs/heads";
        if (is_dir($heads_dir)) {
            $this->collectLooseRefs($heads_dir, "", $branches);
        }
        ksort($branches);
        return $branches;
    }
    /**
     * Returns every ref in the repository, branches and tags alike, as a
     * list mapping the full ref name (such as "refs/heads/master" or
     * "refs/tags/v1") to the object name it points at. Refs stored as their
     * own files and refs collected into the packed-refs file are both
     * included, with a ref's own file taking precedence. The dumb-transport
     * info/refs listing that lets a client clone is built from this.
     *
     * @return array full ref name => object name (hex SHA-1)
     */
    public function allRefs()
    {
        $refs = [];
        $packed = $this->repo_path . "/packed-refs";
        if (is_file($packed)) {
            $lines = explode("\n", (string)@file_get_contents($packed));
            foreach ($lines as $line) {
                $line = trim($line);
                if ($line == "" || $line[0] == "#" || $line[0] == "^") {
                    continue;
                }
                $parts = explode(" ", $line, 2);
                if (count($parts) == 2 &&
                    str_starts_with($parts[1], "refs/") &&
                    $this->isObjectName($parts[0])) {
                    $refs[$parts[1]] = $parts[0];
                }
            }
        }
        $refs_dir = $this->repo_path . "/refs";
        if (is_dir($refs_dir)) {
            $this->collectLooseRefs($refs_dir, "refs/", $refs);
        }
        ksort($refs);
        return $refs;
    }
    /**
     * If the object named is an annotated tag, follows it to the object it
     * finally points at, stepping through a chain if one tag points at
     * another, and returns that object's name. Returns the empty string
     * when the object is not a tag, which lets a caller tell an annotated
     * tag apart from a branch or a lightweight tag. The dumb-transport
     * info/refs listing uses this to add the peeled line Git writes for an
     * annotated tag.
     *
     * @param string $sha object name to peel
     * @return string object name the tag resolves to, or "" if not a tag
     */
    public function peeledTarget($sha)
    {
        $depth = 0;
        $object = $this->readObject($sha);
        while ($object !== null && $object["type"] == "tag" &&
            $depth < self::MAX_TAG_DEPTH) {
            $target = $this->tagTarget($object["body"]);
            if ($target == "") {
                return "";
            }
            $sha = $target;
            $object = $this->readObject($sha);
            $depth++;
        }
        return ($depth > 0) ? $sha : "";
    }
    /**
     * Reads the object name an annotated tag points at out of the tag's
     * contents, which record it on a line beginning with the word "object".
     *
     * @param string $body the tag object's contents
     * @return string the object name the tag points at, or "" if none found
     */
    private function tagTarget($body)
    {
        foreach (explode("\n", $body) as $line) {
            if (str_starts_with($line, "object ")) {
                return trim(substr($line, strlen("object ")));
            }
            if ($line == "") {
                break;
            }
        }
        return "";
    }
    /**
     * Walks a folder of ref files on disk, adding each ref it finds to the
     * running list. Ref files may sit inside sub folders (a branch named
     * "feature/login", or a ref under refs/tags, is stored that way), so
     * this calls itself for each sub folder.
     *
     * @param string $dir folder being scanned for ref files
     * @param string $prefix ref-name prefix carried in from parent folders,
     *     for example "feature/" or "refs/"
     * @param array &$branches running list of ref name => object name that
     *     this method adds to
     */
    private function collectLooseRefs($dir, $prefix, &$branches)
    {
        foreach (scandir($dir) as $name) {
            if ($name == "." || $name == "..") {
                continue;
            }
            $full = $dir . "/" . $name;
            if (is_dir($full)) {
                $this->collectLooseRefs($full, $prefix . $name . "/",
                    $branches);
            } else {
                $sha = trim((string)@file_get_contents($full));
                /* A ref file can instead hold the name of another ref, as
                   refs/remotes/origin/HEAD does when it records which
                   branch that remote's HEAD follows. Such a file names a
                   ref rather than an object, and the listing of refs that
                   a client is given carries only refs naming an object, so
                   it is passed over. Taking its contents for an object
                   name would break the listing outright, since nothing can
                   be read under that name. */
                if ($this->isObjectName($sha)) {
                    $branches[$prefix . $name] = $sha;
                }
            }
        }
    }
    /**
     * Whether a piece of text is the name of an object, that is the hex
     * SHA-1 Git identifies an object by. Somewhere a ref is expected this
     * tells a ref naming an object apart from one naming another ref.
     *
     * @param string $sha text to check
     * @return bool whether the text names an object
     */
    private function isObjectName($sha)
    {
        return strlen($sha) == self::SHA_HEX_LENGTH && ctype_xdigit($sha);
    }
    /**
     * Reads a single object out of the repository given its object name and
     * returns its kind and raw contents. The object name is the hex SHA-1
     * that Git uses to identify the object. Loose objects are read directly;
     * for an object with no loose file the packfile reader is consulted.
     *
     * @param string $sha hex object name to read
     * @return array|null ["type" => "commit"|"tree"|"blob"|"tag",
     *     "body" => raw bytes], or null if the object is in neither a loose
     *     file nor a packfile
     */
    public function readObject($sha)
    {
        if (strlen($sha) != self::SHA_HEX_LENGTH ||
            !ctype_xdigit($sha)) {
            throw new \Exception("git_bad_object_name");
        }
        $path = $this->repo_path . "/objects/" . substr($sha, 0, 2) . "/" .
            substr($sha, 2);
        if (!is_file($path)) {
            return $this->packReader()->readObject($sha);
        }
        $inflated = $this->inflateObjectFile($path);
        $null_at = strpos($inflated, "\0");
        if ($null_at === false) {
            throw new \Exception("git_object_corrupt");
        }
        $header = substr($inflated, 0, $null_at);
        $body = substr($inflated, $null_at + 1);
        $header_parts = explode(" ", $header, 2);
        if (count($header_parts) != 2 ||
            (string)strlen($body) !== $header_parts[1]) {
            throw new \Exception("git_object_corrupt");
        }
        if (sha1($header . "\0" . $body) !== $sha) {
            throw new \Exception("git_object_corrupt");
        }
        return ["type" => $header_parts[0], "body" => $body];
    }
    /**
     * Decompresses one loose object file into memory, stopping with an
     * error if it would expand past the object size limit. The compressed
     * bytes are fed to the decompressor in steps so the limit is enforced
     * while the object is still being expanded rather than only afterwards.
     *
     * @param string $path path to the compressed loose object file
     * @return string the decompressed object, header and all
     */
    private function inflateObjectFile($path)
    {
        $compressed = (string)file_get_contents($path);
        $context = inflate_init(ZLIB_ENCODING_DEFLATE);
        if ($context === false) {
            throw new \Exception("git_object_inflate_failed");
        }
        $inflated = "";
        $total = strlen($compressed);
        for ($pos = 0; $pos < $total; $pos += self::INFLATE_CHUNK) {
            $piece = inflate_add($context,
                substr($compressed, $pos, self::INFLATE_CHUNK));
            if ($piece === false) {
                throw new \Exception("git_object_inflate_failed");
            }
            $inflated .= $piece;
            if (strlen($inflated) > self::MAX_OBJECT_SIZE) {
                throw new \Exception("git_object_too_large");
            }
        }
        return $inflated;
    }
    /**
     * Reads a commit and returns its parts: the folder listing it captures,
     * the commits that came before it, who wrote it and when, and the
     * commit message.
     *
     * @param string $sha object name of the commit to read
     * @return array ["tree" => object name of the commit's tree,
     *     "parents" => list of parent commit object names,
     *     "author" => author line, "committer" => committer line,
     *     "message" => commit message text]
     */
    public function commit($sha)
    {
        $object = $this->readObject($sha);
        if ($object === null || $object["type"] != "commit") {
            throw new \Exception("git_not_a_commit");
        }
        $commit = ["tree" => "", "parents" => [], "author" => "",
            "committer" => "", "message" => ""];
        $split_at = strpos($object["body"], "\n\n");
        $headers = ($split_at === false) ? $object["body"] :
            substr($object["body"], 0, $split_at);
        $commit["message"] = ($split_at === false) ? "" :
            substr($object["body"], $split_at + 2);
        foreach (explode("\n", $headers) as $line) {
            $field = explode(" ", $line, 2);
            if (count($field) != 2) {
                continue;
            }
            if ($field[0] == "tree") {
                $commit["tree"] = $field[1];
            } else if ($field[0] == "parent") {
                $commit["parents"][] = $field[1];
            } else if ($field[0] == "author") {
                $commit["author"] = $field[1];
            } else if ($field[0] == "committer") {
                $commit["committer"] = $field[1];
            }
        }
        return $commit;
    }
    /**
     * Works out which files a commit changed by comparing its tree to the
     * tree of its first parent. A file whose object name differs between
     * the two, or that is present on only one side, is reported, along
     * with whether the commit added, removed, or modified it. This is what
     * lets the read view show a commit's changes the way a typical Git
     * hosting page does. A first commit, having no parent, reports every
     * file as added.
     *
     * @param string $commit_sha object name of the commit to examine
     * @return array list of changes, each ["path" => the file's path from
     *      the repository root, "status" => "added", "removed", or
     *      "modified", "old_sha" => the file's object name in the parent
     *      or "" if absent, "new_sha" => its object name in the commit or
     *      "" if absent]
     */
    public function treeDiff($commit_sha)
    {
        $commit = $this->commit($commit_sha);
        $old_tree = "";
        if (!empty($commit["parents"])) {
            $parent = $this->commit($commit["parents"][0]);
            $old_tree = $parent["tree"];
        }
        $changes = [];
        $this->collectTreeChanges($old_tree, $commit["tree"], "",
            $changes);
        return $changes;
    }
    /**
     * Compares two trees folder by folder, recording every file that
     * differs between them into a running list. Sub folders present on
     * either side are compared by calling this again, so a whole added or
     * removed folder is reported as its individual files. Called by
     * treeDiff to build a commit's list of changed files.
     *
     * @param string $old_tree object name of the earlier tree, or "" when
     *      that folder is absent on the earlier side
     * @param string $new_tree object name of the later tree, or "" when
     *      that folder is absent on the later side
     * @param string $prefix path carried in from parent folders that each
     *      entry's name is joined onto
     * @param array &$changes running list this adds change records to
     */
    private function collectTreeChanges($old_tree, $new_tree, $prefix,
        &$changes)
    {
        $old_entries = ($old_tree === "") ? [] : $this->treeMap($old_tree);
        $new_entries = ($new_tree === "") ? [] : $this->treeMap($new_tree);
        $names = array_keys($old_entries + $new_entries);
        sort($names);
        foreach ($names as $name) {
            $old = $old_entries[$name] ?? null;
            $new = $new_entries[$name] ?? null;
            $old_dir = ($old !== null && $old["is_dir"]);
            $new_dir = ($new !== null && $new["is_dir"]);
            $joined = ($prefix === "") ? $name : $prefix . "/" . $name;
            if ($old_dir || $new_dir) {
                $this->collectTreeChanges(($old_dir) ? $old["sha"] : "",
                    ($new_dir) ? $new["sha"] : "", $joined, $changes);
                continue;
            }
            $old_sha = ($old !== null) ? $old["sha"] : "";
            $new_sha = ($new !== null) ? $new["sha"] : "";
            if ($old_sha === $new_sha) {
                continue;
            }
            if ($old_sha === "") {
                $status = "added";
            } else if ($new_sha === "") {
                $status = "removed";
            } else {
                $status = "modified";
            }
            $changes[] = ["path" => $joined, "status" => $status,
                "old_sha" => $old_sha, "new_sha" => $new_sha];
        }
    }
    /**
     * Reads a tree and returns its entries keyed by name, so two trees can
     * be lined up entry against entry when comparing them.
     *
     * @param string $tree_sha object name of the tree to read
     * @return array map from each entry name to its ["mode", "name",
     *      "sha", "is_dir"] record
     */
    private function treeMap($tree_sha)
    {
        $map = [];
        foreach ($this->tree($tree_sha) as $entry) {
            $map[$entry["name"]] = $entry;
        }
        return $map;
    }
    /**
     * Works out, for each named entry in one folder of the repository, the
     * most recent commit that changed that entry. This is what lets the
     * file browser show, next to every file and sub folder, the summary of
     * the commit that last touched it and how long ago that was, the way a
     * typical Git hosting page does. The answer is cached per folder, keyed
     * to the commit it was worked out against, so the history is only walked
     * again once that commit (the branch tip) has moved on.
     *
     * @param string $start_sha object name of the commit to start from,
     *      usually the tip of the branch being viewed
     * @param array $path folder to look in, as a list of the folder names
     *      leading to it from the repository root (empty for the root)
     * @param array $names the entry names in that folder to date
     * @return array map from entry name to ["summary" => first line of the
     *      commit message, "author" => name of who made that commit,
     *      "time" => commit time as a Unix timestamp]
     */
    public function lastCommitForEntries($start_sha, $path, $names)
    {
        $cache_file = $this->repo_path . "/info/yioop-lastcommit-" .
            sha1(implode("/", $path));
        if (is_file($cache_file)) {
            $cached = json_decode(file_get_contents($cache_file), true);
            if (is_array($cached) &&
                ($cached["sha"] ?? "") === $start_sha) {
                $found = [];
                foreach ($names as $name) {
                    if (isset($cached["entries"][$name])) {
                        $found[$name] = $cached["entries"][$name];
                    }
                }
                return $found;
            }
        }
        $found = $this->walkLastCommitForEntries($start_sha, $path, $names);
        $info_dir = $this->repo_path . "/info";
        if (is_dir($info_dir) || @mkdir($info_dir, 0777, true)) {
            @file_put_contents($cache_file,
                json_encode(["sha" => $start_sha, "entries" => $found]));
        }
        return $found;
    }
    /**
     * Walks the history to find, for each named entry in one folder, the
     * most recent commit that changed it, filling in the caching done by
     * lastCommitForEntries.
     *
     * The history is walked newest first following only each commit's first
     * parent, comparing the folder's listing at a commit against the same
     * folder in that parent: any entry whose object name differs (or that is
     * newly present) was changed by that commit. Walking stops once every
     * asked-for entry has been dated, or once the history runs out, so even
     * a file untouched for a long time still gets the commit that last
     * changed it rather than being left blank.
     *
     * @param string $start_sha object name of the commit to start from,
     *      usually the tip of the branch being viewed
     * @param array $path folder to look in, as a list of the folder names
     *      leading to it from the repository root (empty for the root)
     * @param array $names the entry names in that folder to date
     * @return array map from entry name to ["summary" => first line of the
     *      commit message, "author" => name of who made that commit,
     *      "time" => commit time as a Unix timestamp]
     */
    private function walkLastCommitForEntries($start_sha, $path, $names)
    {
        $found = [];
        $remaining = array_flip($names);
        $commit = $this->commit($start_sha);
        $current_tree = $this->treeAtPath($commit["tree"], $path);
        while (!empty($remaining)) {
            $parent_sha = $commit["parents"][0] ?? "";
            $parent_tree = [];
            $parent_commit = null;
            if ($parent_sha !== "") {
                $parent_commit = $this->commit($parent_sha);
                $parent_tree =
                    $this->treeAtPath($parent_commit["tree"], $path);
            }
            foreach ($current_tree as $name => $entry_sha) {
                if (isset($remaining[$name]) &&
                    ($parent_tree[$name] ?? "") !== $entry_sha) {
                    $break_at = strpos($commit["message"], "\n");
                    $summary = ($break_at === false) ? $commit["message"] :
                        substr($commit["message"], 0, $break_at);
                    $found[$name] = ["summary" => trim($summary),
                        "author" => $this->authorName($commit["author"]),
                        "time" => $this->commitTime($commit["committer"])];
                    unset($remaining[$name]);
                }
            }
            if ($parent_sha === "") {
                break;
            }
            $commit = $parent_commit;
            $current_tree = $parent_tree;
        }
        return $found;
    }
    /**
     * Follows a folder path down from a commit's top level tree and returns
     * a simple map of the names in the folder it arrives at to the object
     * names of their contents. An empty map is returned when the path does
     * not exist at that point in history, which is how a newly created
     * folder is recognised as new.
     *
     * @param string $tree_sha object name of the commit's top level tree
     * @param array $path the folder names leading to the folder of interest
     * @return array map from entry name to its object name
     */
    private function treeAtPath($tree_sha, $path)
    {
        $sha = $tree_sha;
        foreach ($path as $component) {
            $step_sha = "";
            foreach ($this->tree($sha) as $entry) {
                if ($entry["name"] === $component && $entry["is_dir"]) {
                    $step_sha = $entry["sha"];
                    break;
                }
            }
            if ($step_sha === "") {
                return [];
            }
            $sha = $step_sha;
        }
        $listing = [];
        foreach ($this->tree($sha) as $entry) {
            $listing[$entry["name"]] = $entry["sha"];
        }
        return $listing;
    }
    /**
     * Reads the time a commit was recorded out of its committer line, which
     * ends with a Unix timestamp and a timezone. Returns zero when no time
     * can be read.
     *
     * @param string $committer_line the committer line from a commit
     * @return int the commit time as a Unix timestamp, or zero
     */
    private function commitTime($committer_line)
    {
        if (preg_match('/(\d+)\s+[+-]\d{4}\s*$/', $committer_line,
            $matches)) {
            return (int)$matches[1];
        }
        return 0;
    }
    /**
     * Reads the display name out of a commit's author line, which Git keeps
     * in the form "Name <email> timestamp zone"; the name on its own is what
     * the file listing shows for who last changed a file.
     *
     * @param string $author_line the author line from a commit
     * @return string the author's name, or the whole line if it does not
     *      parse
     */
    private function authorName($author_line)
    {
        if (preg_match("/^(.*) <[^>]*> \d+ [+-]\d{4}\s*$/", $author_line,
            $match)) {
            return $match[1];
        }
        return $author_line;
    }
    /**
     * Reads a tree, which is Git's record of one folder, and returns the
     * entries it lists. Each entry is a file or sub folder together with
     * its permission bits and the object name of its contents.
     *
     * @param string $sha object name of the tree to read
     * @return array list of ["mode" => permission string,
     *     "name" => entry name, "sha" => object name of the entry,
     *     "is_dir" => whether the entry is a sub folder]
     */
    public function tree($sha)
    {
        $object = $this->readObject($sha);
        if ($object === null || $object["type"] != "tree") {
            throw new \Exception("git_not_a_tree");
        }
        $body = $object["body"];
        $entries = [];
        $pos = 0;
        $total = strlen($body);
        while ($pos < $total) {
            $space_at = strpos($body, " ", $pos);
            $null_at = ($space_at === false) ? false :
                strpos($body, "\0", $space_at);
            if ($space_at === false || $null_at === false ||
                $null_at + 1 + self::SHA_RAW_LENGTH > $total) {
                throw new \Exception("git_tree_corrupt");
            }
            $mode = substr($body, $pos, $space_at - $pos);
            $name = substr($body, $space_at + 1, $null_at - $space_at - 1);
            $raw_sha = substr($body, $null_at + 1, self::SHA_RAW_LENGTH);
            $entries[] = ["mode" => $mode, "name" => $name,
                "sha" => bin2hex($raw_sha), "is_dir" => ($mode == "40000")];
            $pos = $null_at + 1 + self::SHA_RAW_LENGTH;
        }
        return $entries;
    }
    /**
     * Reads a blob, which is Git's record of one file's contents, and
     * returns those raw bytes.
     *
     * @param string $sha object name of the blob to read
     * @return string the file contents stored in the blob
     */
    public function blob($sha)
    {
        $object = $this->readObject($sha);
        if ($object === null || $object["type"] != "blob") {
            throw new \Exception("git_not_a_blob");
        }
        return $object["body"];
    }
    /**
     * Reads a run of commits from the history so a read view can show a
     * scrollable commit list a page at a time. Starting from the given
     * commit and following each commit's first parent, the first $offset
     * commits are skipped and the next $limit are returned newest first,
     * which is what lets the caller ask for "the next twenty" as a reader
     * scrolls.
     *
     * @param string $start_sha object name of the commit to start from
     * @param int $offset number of commits to skip before collecting
     * @param int $limit most commits to return, or zero or less for
     *      every commit from the offset to the start of history
     * @return array list of commits, each ["sha" => object name,
     *      "author" => author's name, "time" => commit time as a Unix
     *      timestamp, "subject" => first line of the commit message]
     */
    public function commitList($start_sha, $offset, $limit)
    {
        $commits = [];
        $sha = $start_sha;
        $seen = 0;
        while ($sha !== "" && ($limit <= 0 || $seen < $offset + $limit)) {
            try {
                $commit = $this->commit($sha);
            } catch (\Exception $error) {
                break;
            }
            if ($seen >= $offset) {
                $name = $commit["author"];
                $time = 0;
                if (preg_match("/^(.*) <[^>]*> (\d+) [+-]\d{4}\s*$/",
                    $commit["author"], $match)) {
                    $name = $match[1];
                    $time = (int)$match[2];
                }
                $commits[] = ["sha" => $sha, "author" => $name,
                    "time" => $time,
                    "subject" => $this->firstLine($commit["message"])];
            }
            $seen++;
            $sha = $commit["parents"][0] ?? "";
        }
        return $commits;
    }
    /**
     * Lists the repository's tags newest first so a read view can offer them
     * for browsing and download. Each tag is followed to the commit it marks
     * (an annotated tag through its tag object, a lightweight tag directly),
     * and that commit's time and message summary are read so the list can be
     * shown much like the commit list.
     *
     * @return array list of tags, each ["name" => tag name,
     *      "sha" => object name of the commit it marks, "time" => that
     *      commit's time as a Unix timestamp, "subject" => first line of
     *      that commit's message]
     */
    public function tags()
    {
        $tags = [];
        foreach ($this->allRefs() as $ref => $sha) {
            if (!str_starts_with($ref, "refs/tags/")) {
                continue;
            }
            $commit_sha = $this->peeledTarget($sha);
            if ($commit_sha === "") {
                $commit_sha = $sha;
            }
            try {
                $commit = $this->commit($commit_sha);
            } catch (\Exception $error) {
                continue;
            }
            $time = 0;
            if (preg_match("/ (\d+) [+-]\d{4}\s*$/", $commit["committer"],
                $match)) {
                $time = (int)$match[1];
            }
            $tags[] = ["name" => substr($ref, strlen("refs/tags/")),
                "sha" => $commit_sha, "time" => $time,
                "subject" => $this->firstLine($commit["message"])];
        }
        usort($tags, function ($first, $second) {
            return $second["time"] <=> $first["time"];
        });
        return $tags;
    }
    /**
     * Returns the first line of a commit or tag message, used as the short
     * summary shown in a list.
     *
     * @param string $message the full message
     * @return string its first line, with surrounding blank space removed
     */
    private function firstLine($message)
    {
        $message = trim($message);
        $newline_at = strpos($message, "\n");
        return ($newline_at === false) ? $message :
            substr($message, 0, $newline_at);
    }
    /**
     * Gathers a few simple counts that describe a repository: how many
     * commits it holds, how many each author made, how many were made in
     * each month, and how many files of each type sit in the newest commit.
     * The commit history is followed along first parents, and the newest
     * commit's files are counted by the ending of their name. Both walks
     * stop after a generous cap so an unusually large repository cannot make
     * this run for a long time.
     *
     * @param string $start_sha object name of the commit to start from,
     *      normally the tip of the shown branch
     * @return array counts with keys "commits" (total), "authors" (name to
     *      count), "months" (year and month text to count), "files" (total
     *      files in the newest commit), and "extensions" (file ending to
     *      count)
     */
    public function statistics($start_sha)
    {
        $authors = [];
        $months = [];
        $commit_count = 0;
        $sha = $start_sha;
        $tree_sha = "";
        while ($sha !== "" && $commit_count < self::STATISTICS_COMMIT_CAP) {
            try {
                $commit = $this->commit($sha);
            } catch (\Exception $error) {
                break;
            }
            if ($tree_sha === "") {
                $tree_sha = $commit["tree"];
            }
            $name = $commit["author"];
            $time = 0;
            if (preg_match("/^(.*) <[^>]*> (\d+) [+-]\d{4}\s*$/",
                $commit["author"], $match)) {
                $name = $match[1];
                $time = (int)$match[2];
            }
            $authors[$name] = ($authors[$name] ?? 0) + 1;
            if ($time > 0) {
                $month = gmdate("Y-m", $time);
                $months[$month] = ($months[$month] ?? 0) + 1;
            }
            $commit_count++;
            $sha = $commit["parents"][0] ?? "";
        }
        $extensions = [];
        $file_count = 0;
        $budget = self::STATISTICS_FILE_CAP;
        if ($tree_sha !== "") {
            $this->collectFileTypes($tree_sha, $extensions, $file_count,
                $budget);
        }
        return ["commits" => $commit_count, "authors" => $authors,
            "months" => $months, "files" => $file_count,
            "extensions" => $extensions];
    }
    /**
     * Walks a tree and everything beneath it, counting how many files there
     * are and how many end in each file ending. A shared budget limits the
     * total work so a repository with a huge number of files cannot make
     * this run for a long time.
     *
     * @param string $tree_sha object name of the tree to walk
     * @param array &$extensions file ending to count, added to in place; a
     *      file with no ending is counted under an empty text key
     * @param int &$file_count running total of files, added to in place
     * @param int &$budget remaining number of entries that may be visited,
     *      lowered in place as the walk proceeds
     */
    private function collectFileTypes($tree_sha, &$extensions, &$file_count,
        &$budget)
    {
        if ($budget <= 0) {
            return;
        }
        try {
            $entries = $this->tree($tree_sha);
        } catch (\Exception $error) {
            return;
        }
        foreach ($entries as $entry) {
            if ($budget <= 0) {
                return;
            }
            $budget--;
            if (!empty($entry["is_dir"])) {
                $this->collectFileTypes($entry["sha"], $extensions,
                    $file_count, $budget);
                continue;
            }
            $file_count++;
            $dot_at = strrpos($entry["name"], ".");
            $ending = ($dot_at === false || $dot_at === 0) ? "" :
                strtolower(substr($entry["name"], $dot_at + 1));
            $extensions[$ending] = ($extensions[$ending] ?? 0) + 1;
        }
    }
    /**
     * Builds a downloadable archive of everything in one commit and writes
     * it to the given file. This is the pure-PHP stand-in for "git archive":
     * the commit's whole file tree is walked and each file written into a
     * zip or a gzip-compressed tar, under a top folder so the archive
     * unpacks tidily. The archive is written straight to a file rather than
     * built up in memory, and its total size is capped, so zipping even a
     * large repository stays within the server's means.
     *
     * @param string $commit_sha object name of the commit to archive
     * @param string $format either "zip" or "targz"
     * @param string $out_path file to write the finished archive to
     * @param string $prefix top folder name to place every file under,
     *      ending in a slash, for example "myproject/"
     */
    public function writeArchive($commit_sha, $format, $out_path, $prefix)
    {
        $commit = $this->commit($commit_sha);
        $files = [];
        $this->collectTreeFiles($commit["tree"], $prefix, $files);
        if ($format === "zip") {
            $this->writeZipArchive($files, $out_path);
        } else {
            $this->writeTarGzArchive($files, $out_path);
        }
    }
    /**
     * Builds an archive of just one folder of a snapshot rather than the
     * whole repository, used when a reader downloads the sub folder they
     * are looking at. Works the same way as writeArchive but starts from
     * the given folder's tree instead of the commit's top tree.
     *
     * @param string $tree_sha object name of the folder's tree to archive
     * @param string $format either "zip" or "targz"
     * @param string $out_path file to write the archive to
     * @param string $prefix folder name placed in front of every path
     *      written into the archive
     */
    public function writeArchiveFromTree($tree_sha, $format, $out_path,
        $prefix)
    {
        $files = [];
        $this->collectTreeFiles($tree_sha, $prefix, $files);
        if ($format === "zip") {
            $this->writeZipArchive($files, $out_path);
        } else {
            $this->writeTarGzArchive($files, $out_path);
        }
    }
    /**
     * Gathers every file in a tree, folders and all, into a flat list of
     * paths and object names ready to be written into an archive. Sub
     * folders are followed by calling this again; submodule links, which
     * hold no file content here, are left out.
     *
     * @param string $tree_sha object name of the tree to walk
     * @param string $prefix path carried in from parent folders, ending in
     *      a slash, that each entry's name is joined onto
     * @param array &$files running list this adds ["path", "sha", "mode"]
     *      records to
     */
    private function collectTreeFiles($tree_sha, $prefix, &$files)
    {
        foreach ($this->tree($tree_sha) as $entry) {
            $path = $prefix . $entry["name"];
            if ($entry["is_dir"]) {
                $this->collectTreeFiles($entry["sha"], $path . "/", $files);
            } else if ($entry["mode"] !== "160000") {
                $files[] = ["path" => $path, "sha" => $entry["sha"],
                    "mode" => $entry["mode"]];
            }
        }
    }
    /**
     * Writes the given files into a gzip-compressed tar archive, one file at
     * a time straight into the compressed output stream so only a single
     * file is ever held in memory. The build is refused once the files seen
     * so far pass the archive size cap.
     *
     * @param array $files list of ["path", "sha", "mode"] records to write
     * @param string $out_path file to write the archive to
     */
    private function writeTarGzArchive($files, $out_path)
    {
        $stream = gzopen($out_path, "wb");
        if ($stream === false) {
            throw new \Exception("git_archive_open_failed");
        }
        $total = 0;
        foreach ($files as $file) {
            $blob = $this->blob($file["sha"]);
            $total += strlen($blob);
            if ($total > self::MAX_ARCHIVE_SIZE) {
                gzclose($stream);
                @unlink($out_path);
                throw new \Exception("git_archive_too_large");
            }
            gzwrite($stream, $this->tarHeader($file["path"],
                strlen($blob), $file["mode"]));
            gzwrite($stream, $blob);
            $remainder = strlen($blob) % self::TAR_BLOCK;
            if ($remainder !== 0) {
                gzwrite($stream,
                    str_repeat("\0", self::TAR_BLOCK - $remainder));
            }
        }
        gzwrite($stream, str_repeat("\0", self::TAR_BLOCK * 2));
        gzclose($stream);
    }
    /**
     * Writes the given files into a zip archive. The build is refused once
     * the files seen so far pass the archive size cap.
     *
     * @param array $files list of ["path", "sha", "mode"] records to write
     * @param string $out_path file to write the archive to
     */
    private function writeZipArchive($files, $out_path)
    {
        if (!class_exists("\\ZipArchive")) {
            throw new \Exception("git_archive_zip_unsupported");
        }
        $zip = new \ZipArchive();
        if ($zip->open($out_path,
            \ZipArchive::CREATE | \ZipArchive::OVERWRITE) !== true) {
            throw new \Exception("git_archive_open_failed");
        }
        $total = 0;
        foreach ($files as $file) {
            $blob = $this->blob($file["sha"]);
            $total += strlen($blob);
            if ($total > self::MAX_ARCHIVE_SIZE) {
                $zip->close();
                @unlink($out_path);
                throw new \Exception("git_archive_too_large");
            }
            $zip->addFromString($file["path"], $blob);
        }
        $zip->close();
    }
    /**
     * Builds the 512-byte tar header block that introduces one file in a tar
     * archive, in the widely understood ustar format. A path too long for
     * the header's name field is split, with its leading folders moved into
     * the separate prefix field. The header carries a checksum of its own
     * bytes, which this computes as the format requires.
     *
     * @param string $path the file's path within the archive
     * @param int $size the file's size in bytes
     * @param string $mode the file's git mode, used only to mark a file
     *      executable or not
     * @return string the 512-byte header block
     */
    private function tarHeader($path, $size, $mode)
    {
        $name = $path;
        $prefix = "";
        if (strlen($name) > self::TAR_NAME_LENGTH) {
            $split_at = strrpos(
                substr($name, 0, self::TAR_NAME_LENGTH + 1), "/");
            if ($split_at !== false && $split_at > 0) {
                $prefix = substr($name, 0, $split_at);
                $name = substr($name, $split_at + 1);
            } else {
                $name = substr($name, -self::TAR_NAME_LENGTH);
            }
        }
        $file_mode = ($mode === "100755") ? "0000755" : "0000644";
        $header = pack("a100a8a8a8a12a12", $name, $file_mode, "0000000",
            "0000000", sprintf("%011o", $size), sprintf("%011o", time()));
        $header .= "        ";
        $header .= pack("a1a100a6a2a32a32a8a8a155", "0", "", "ustar", "00",
            "", "", "", "", $prefix);
        $header = str_pad($header, self::TAR_BLOCK, "\0");
        $checksum = 0;
        for ($index = 0; $index < self::TAR_BLOCK; $index++) {
            $checksum += ord($header[$index]);
        }
        $checksum_field = sprintf("%06o", $checksum) . "\0 ";
        return substr_replace($header, $checksum_field, 148, 8);
    }
    /**
     * Returns the packfile reader for this repository, creating it the first
     * time an object is not found as a loose file. Keeping one reader lets it
     * hold packfiles open across many reads.
     *
     * @return object the packfile reader
     */
    private function packReader()
    {
        if ($this->pack_reader === null) {
            $this->pack_reader = new GitPackReader($this->repo_path, $this);
        }
        return $this->pack_reader;
    }
}
