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

/**
 * Serves a Git repository to a cloning client over the "smart" side of
 * Git's HTTP protocol, in pure PHP with no git program involved. The dumb
 * side of that protocol just hands back the repository's stored files, so a
 * client has to download the whole history; the smart side lets the client
 * ask for only what it wants, which is what makes a shallow clone (git's
 * --depth option) possible. This class produces the two smart replies: the
 * advertisement a client reads first to learn the repository's branches and
 * what the server can do, and the response to the follow-up request in which
 * the client says which commits it wants and how much history to include.
 *
 * It reads objects through a GitRepository, which already knows how to pull
 * commits, trees, and blobs out of both loose files and packfiles (undoing
 * Git's delta compression on the way). This class adds only the protocol on
 * top: framing bytes into Git's length-prefixed "pkt-line" records, reading
 * the client's request, walking history from the wanted commits down to the
 * requested depth, and writing the chosen objects into a fresh packfile.
 * Objects are written into that pack whole rather than as deltas, which is
 * always valid and keeps the writer simple. Like the rest of the Git library
 * it only ever reads the repository.
 *
 * The framing follows Git's pack protocol: a pkt-line is a four-hex-digit
 * length (counting the four digits) then that many bytes, and the special
 * length "0000" is a flush marker that separates sections.
 *
 * @author Chris Pollett
 */
class GitUploadPack
{
    /**
     * The repository being served, used to read refs and objects
     * @var object
     */
    private $repository;
    /**
     * Object names the client already holds, gathered from the commits it
     * says it has and everything those record. Anything in here is left out
     * of the packfile, since sending a file the client already has is what
     * turns a small update into a copy of the whole working tree.
     * @var array
     */
    private $held_objects = [];
    /**
     * For each object being packed, the kind of thing it is and, for a
     * folder or file, the name it goes by. Successive versions of one file
     * are nearly alike, so packing them next to each other is what lets each
     * be sent as its small difference from the one before.
     * @var array
     */
    private $object_groups = [];
    /**
     * For each folder and file the client already holds, the object name of
     * the version it has, kept under the name that thing goes by. A new
     * version can then be sent as its difference from the client's own copy
     * instead of whole, which is what the thin-pack capability allows.
     * @var array
     */
    private $held_by_name = [];
    /**
     * Length in bytes of the hex count that begins every pkt-line
     * @var int
     */
    const PKT_LENGTH_DIGITS = 4;
    /**
     * The flush marker, a pkt-line whose length field is all zeros, which
     * separates one section of the protocol from the next
     * @var string
     */
    const FLUSH_PKT = "0000";
    /**
     * Largest byte count a single pkt-line can carry, including its own
     * four-digit length, fixed by the pack protocol
     * @var int
     */
    const MAX_PKT_LENGTH = 65520;
    /**
     * Number of hex characters in an object name
     * @var int
     */
    const SHA_HEX_LENGTH = 40;
    /**
     * Pack object type code for a commit, used in a packed object's header
     * @var int
     */
    const OBJECT_TYPE_COMMIT = 1;
    /**
     * Pack object type code for a tree
     * @var int
     */
    const OBJECT_TYPE_TREE = 2;
    /**
     * Pack object type code for a blob
     * @var int
     */
    const OBJECT_TYPE_BLOB = 3;
    /**
     * Pack object type code for an annotated tag
     * @var int
     */
    const OBJECT_TYPE_TAG = 4;
    /**
     * Map from Git's object type words to the numeric type codes a packfile
     * uses in each object's header
     * @var array
     */
    const TYPE_CODES = ["commit" => self::OBJECT_TYPE_COMMIT,
        "tree" => self::OBJECT_TYPE_TREE, "blob" => self::OBJECT_TYPE_BLOB,
        "tag" => self::OBJECT_TYPE_TAG];
    /**
     * Bits of the object size that fit in the first byte of a packed
     * object's header, the low four bits after the three type bits
     * @var int
     */
    const FIRST_SIZE_BITS = 4;
    /**
     * Bits of the object size carried by each continuation byte of a packed
     * object's header, the low seven bits
     * @var int
     */
    const CONTINUATION_SIZE_BITS = 7;
    /**
     * The high bit of a header byte, set to say another size byte follows
     * @var int
     */
    const CONTINUATION_FLAG = 0x80;
    /**
     * A cap on how many objects one response may pack, so a request cannot
     * make the server walk an unbounded amount of history at once
     * @var int
     */
    const MAX_PACK_OBJECTS = 250000;
    /**
     * Most commits of the client's own history to walk back through while
     * working out where the two sides' histories meet. The walk reads
     * commits and nothing else, which costs a fraction of a millisecond
     * each, so this is generous enough for a repository of any age while
     * still refusing an unbounded amount of work.
     * @var int
     */
    const MAX_HELD_HISTORY = 100000;
    /**
     * Pack type code for an object written as its difference from another
     * object that the packfile names outright
     * @var int
     */
    const TYPE_REF_DELTA = 7;
    /**
     * Most objects in a row that may be written as a difference from the one
     * before. Rebuilding the last of such a run means rebuilding all of
     * them, so the run is broken every so often by an object written in
     * full, keeping that work bounded for the client.
     * @var int
     */
    const MAX_DELTA_CHAIN = 10;
    /**
     * Largest object, in bytes, that is sent as a difference from another.
     * Working out a difference compares two whole objects and holds both
     * along with the answer, so on objects of a hundred megabytes and more
     * it costs minutes and gigabytes for a saving that a large file, being
     * mostly incompressible, rarely gives. Anything larger than this is
     * sent whole (16 megabytes).
     */
    const MAX_DELTA_BODY = 16777216;
    /**
     * The service name a cloning (read-only) client asks for
     * @var string
     */
    const UPLOAD_PACK_SERVICE = "git-upload-pack";
    /**
     * The name a client uses to say it will accept a pack whose differences
     * may be built against content the client already holds rather than
     * against content sent alongside. Such a pack is smaller, and the client
     * completes it from its own store on arrival.
     * @var string
     */
    const THIN_PACK_CAPABILITY = "thin-pack";
    /**
     * The capabilities the server tells the client it supports. "shallow"
     * is the one that allows a depth-limited clone; "no-progress" says the
     * server will not send human-readable progress lines;
     * "multi_ack_detailed" lets a round of negotiation name each commit the
     * two sides are found to hold in common and say when the server is ready
     * to send, which is what lets a client with a long history settle
     * quickly instead of giving up and asking for all of it; "thin-pack"
     * lets a file's new version be sent as its difference from the version
     * the client already has, rather than whole. Side-band multiplexing is
     * deliberately not offered, so the packfile comes back as plain bytes
     * after the acknowledgment rather than chopped into band-tagged records.
     * @var string
     */
    const CAPABILITIES =
        "shallow no-progress multi_ack_detailed thin-pack";

    /**
     * Makes an upload-pack server for one repository.
     *
     * @param object $repository the GitRepository whose refs and objects
     *      are to be served
     */
    public function __construct($repository)
    {
        $this->repository = $repository;
    }
    /**
     * Wraps a piece of data as one pkt-line: its length, counting the four
     * length digits themselves, in four hex digits, followed by the data.
     *
     * @param string $data the bytes to frame
     * @return string the framed pkt-line
     */
    public static function pktLine($data)
    {
        $length = strlen($data) + self::PKT_LENGTH_DIGITS;
        return sprintf("%04x", $length) . $data;
    }
    /**
     * Splits a run of pkt-lines into the pieces of data they carry. A flush
     * marker is reported as a boolean false entry so a reader can see where
     * one section ends, since the protocol uses flushes to separate the list
     * of wants from the list of the client's commits.
     *
     * @param string $stream the bytes to read, a sequence of pkt-lines
     * @return array in-order contents of each line, with false marking a
     *      flush; the trailing newline Git puts on a line is trimmed.
     *      Reading stops at the first thing that is not a line, so
     *      whatever follows the lines is left alone
     */
    public static function decodePktLines($stream)
    {
        $lines = [];
        $offset = 0;
        $total = strlen($stream);
        while ($offset + self::PKT_LENGTH_DIGITS <= $total) {
            $digits = substr($stream, $offset, self::PKT_LENGTH_DIGITS);
            /* A line begins with its length in hexadecimal. Anything else
               means the reading has walked past the lines into whatever
               follows them -- a pack, in a push -- and stopping is the
               only correct answer. Handing such bytes to a hexadecimal
               reading gives a number made up from whichever characters
               happened to be valid, which quietly puts the rest of the
               parse out of step. */
            if (!ctype_xdigit($digits)) {
                break;
            }
            $length = hexdec($digits);
            if ($length == 0) {
                $lines[] = false;
                $offset += self::PKT_LENGTH_DIGITS;
                continue;
            }
            if ($length < self::PKT_LENGTH_DIGITS ||
                $offset + $length > $total) {
                break;
            }
            $content = substr($stream, $offset + self::PKT_LENGTH_DIGITS,
                $length - self::PKT_LENGTH_DIGITS);
            $lines[] = rtrim($content, "\n");
            $offset += $length;
        }
        return $lines;
    }
    /**
     * Builds the advertisement a client reads first, over a GET, to discover
     * the repository. It names the service, then lists every ref with the
     * object it points at, attaching the server's capabilities to the first
     * line, and points HEAD at the default branch so the client knows which
     * branch to check out. Annotated tags also get a peeled line giving the
     * commit the tag ultimately refers to.
     *
     * @return string the advertisement as pkt-lines, ready to send as the
     *      body of the info/refs reply
     */
    public function advertiseRefs()
    {
        $output = self::pktLine("# service=" . self::UPLOAD_PACK_SERVICE .
            "\n") . self::FLUSH_PKT;
        $refs = $this->repository->allRefs();
        $head_branch = $this->repository->headBranch();
        $head_line = "";
        if ($head_branch != "" &&
            isset($refs["refs/heads/" . $head_branch])) {
            $head_line = $refs["refs/heads/" . $head_branch] . " HEAD";
        }
        $capabilities = self::CAPABILITIES;
        if ($head_line != "") {
            $capabilities .= " symref=HEAD:refs/heads/" . $head_branch;
        }
        $first = true;
        if ($head_line != "") {
            $output .= self::pktLine($head_line . "\0" . $capabilities .
                "\n");
            $first = false;
        }
        foreach ($refs as $name => $object_name) {
            $line = $object_name . " " . $name;
            if ($first) {
                $output .= self::pktLine($line . "\0" . $capabilities .
                    "\n");
                $first = false;
            } else {
                $output .= self::pktLine($line . "\n");
            }
            $peeled = $this->repository->peeledTarget($object_name);
            if ($peeled != "") {
                $output .= self::pktLine($peeled . " " . $name . "^{}\n");
            }
        }
        return $output . self::FLUSH_PKT;
    }
    /**
     * Reads the client's upload request out of the pkt-lines it posted. The
     * client lists the object names it wants, the object names it already has
     * (its current tips, so the server can leave their history out), may say
     * how deep a history to send, and ends with "done." Any capabilities the
     * client tacks onto its first want line are ignored here, since the
     * server only offers a fixed set.
     *
     * @param string $request_body the raw posted body
     * @return array ["wants" => list of wanted object names,
     *      "haves" => list of object names the client already has,
     *      "depth" => requested history depth, 0 meaning the whole history,
     *      "done" => whether the client said it is done negotiating]
     */
    public function parseUploadRequest($request_body)
    {
        $wants = [];
        $haves = [];
        $capabilities = [];
        $depth = 0;
        $done = false;
        foreach (self::decodePktLines($request_body) as $line) {
            if ($line === false || $line === "") {
                continue;
            }
            $parts = explode(" ", $line);
            if ($parts[0] == "want" && isset($parts[1]) &&
                $this->isObjectName($parts[1])) {
                $wants[$parts[1]] = true;
                foreach (array_slice($parts, 2) as $capability) {
                    $capabilities[trim($capability)] = true;
                }
            } else if ($parts[0] == "have" && isset($parts[1]) &&
                $this->isObjectName($parts[1])) {
                $haves[$parts[1]] = true;
            } else if ($parts[0] == "deepen" && isset($parts[1])) {
                $depth = max(0, intval($parts[1]));
            } else if ($parts[0] == "done") {
                $done = true;
            }
        }
        return ["wants" => array_keys($wants),
            "haves" => array_keys($haves), "depth" => $depth,
            "done" => $done,
            "thin" => isset($capabilities[self::THIN_PACK_CAPABILITY])];
    }
    /**
     * Produces the reply to a client's clone or fetch request a piece at a
     * time, yielding each as it is made rather than building the whole thing
     * first.
     *
     * Yielding is what keeps a large clone from taking the server down with
     * it: the caller hands this to the web server, which advances it only as
     * the client reads, so the packfile is neither held in memory nor built
     * in one long stretch that leaves every other connection unserved. It
     * also means the reply's length is not known when the headers go out, so
     * the body is sent without a stated length.
     *
     * A fetch happens in rounds. The client names what it wants and lists
     * commits it already has; while nothing it lists is recognized the reply
     * is a bare "NAK" and the client offers older commits next. As soon as
     * one is recognized the reply names it as held in common and says the
     * server is ready, which stops the client walking further back. Once the
     * client says it is done, the reply is a final acknowledgment followed
     * by the packfile of just the objects it is missing. Sending the pack
     * before that leaves the client reading pack bytes where it expects the
     * next pkt-line.
     *
     * @param string $request_body the client's posted upload request
     * @return \Generator yields the reply's bytes in order
     */
    public function uploadPackChunks($request_body)
    {
        $request = $this->parseUploadRequest($request_body);
        $commons = $this->commonCommits($request["haves"]);
        if (!$request["done"] && $request["depth"] <= 0) {
            yield from $this->negotiationRoundChunks($commons);
            return;
        }
        $walk = $this->walkWanted($request["wants"], $request["depth"],
            $request["haves"]);
        if ($request["depth"] > 0) {
            foreach ($walk["shallow"] as $shallow_sha) {
                yield self::pktLine("shallow " . $shallow_sha . "\n");
            }
            yield self::FLUSH_PKT;
            if (!$request["done"]) {
                return;
            }
        }
        if (empty($commons)) {
            yield self::pktLine("NAK\n");
        } else {
            yield self::pktLine("ACK " . $commons[0] . "\n");
        }
        yield from $this->packChunks($walk["objects"],
            $request["thin"]);
    }
    /**
     * Produces the answer to one round of a client's offers of commits it
     * already has. Naming each recognized commit as held in common, and then
     * saying the server is ready, is what lets the client stop offering ever
     * older commits and ask for its update; without it a client with a long
     * history gives up after a couple of hundred offers, concludes the two
     * sides share nothing, and asks for the whole history. The closing "NAK"
     * ends the round: a flush in its place is read as a missing
     * acknowledgment, and no closing line at all leaves the client waiting.
     *
     * @param array $commons object names from this round that the repository
     *      also holds, newest first
     * @return \Generator yields the round's pkt-lines in order
     */
    private function negotiationRoundChunks($commons)
    {
        foreach ($commons as $common) {
            yield self::pktLine("ACK " . $common . " common\n");
        }
        if (!empty($commons)) {
            yield self::pktLine("ACK " . $commons[0] . " ready\n");
        }
        yield self::pktLine("NAK\n");
    }
    /**
     * Picks out the commits a client says it already has that this
     * repository also holds. A client lists its commits newest first, so the
     * result keeps that order and its first entry is the newest commit the
     * two sides share.
     *
     * @param array $haves object names the client says it has
     * @return array the object names of those this repository also holds
     */
    private function commonCommits($haves)
    {
        $commons = [];
        foreach ($haves as $sha) {
            if ($this->repository->readObject($sha) !== null) {
                $commons[] = $sha;
            }
        }
        return $commons;
    }
    /**
     * Walks history from the wanted commits and gathers every object a
     * client needs to check them out: the commits themselves and, for each,
     * the whole tree of folders and files it records. When a depth is given
     * the walk keeps only that many commits deep along each parent line and
     * marks the commits at the cutoff as shallow. A wanted object that is a
     * tag is followed to the commit it names first.
     *
     * @param array $wants object names the client asked for
     * @param int $depth most commits to include along each history line, or
     *      0 for no limit
     * @param array $haves object names the client already has; the walk
     *      treats these as already visited so it stops at them and leaves
     *      their history out of the pack
     * @return array ["objects" => ordered list of object names to pack,
     *      "shallow" => object names of commits at the depth cutoff]
     */
    private function walkWanted($wants, $depth, $haves = [])
    {
        $objects = [];
        $shallow = [];
        $seen_commits = [];
        $this->held_objects = [];
        $this->held_by_name = [];
        foreach ($haves as $have_sha) {
            $this->markHeldHistory($have_sha, $seen_commits);
            $this->collectHeld($have_sha);
        }
        $queue = [];
        foreach ($wants as $want) {
            $commit_sha = $this->resolveToCommit($want, $objects);
            if ($commit_sha != "") {
                $queue[] = ["sha" => $commit_sha, "level" => 1];
            }
        }
        while (!empty($queue)) {
            $item = array_shift($queue);
            $commit_sha = $item["sha"];
            if (isset($seen_commits[$commit_sha])) {
                continue;
            }
            $seen_commits[$commit_sha] = true;
            $this->addObject($commit_sha, $objects);
            $commit = $this->repository->commit($commit_sha);
            $this->collectTree($commit["tree"], $objects, "");
            $at_cutoff = ($depth > 0 && $item["level"] >= $depth);
            if ($at_cutoff && !empty($commit["parents"])) {
                $shallow[$commit_sha] = true;
                continue;
            }
            foreach ($commit["parents"] as $parent_sha) {
                $queue[] = ["sha" => $parent_sha,
                    "level" => $item["level"] + 1];
            }
        }
        return ["objects" => array_keys($objects),
            "shallow" => array_keys($shallow)];
    }
    /**
     * Follows a wanted object name to the commit it stands for. A commit is
     * returned as itself; an annotated tag is unwrapped, adding the tag
     * object to the pack on the way, until a commit is reached. Anything
     * that is not a commit or tag yields the empty string.
     *
     * @param string $sha the wanted object name
     * @param array &$objects running set of objects to pack, added to when
     *      a tag is unwrapped
     * @return string the commit's object name, or "" if none is reached
     */
    private function resolveToCommit($sha, &$objects)
    {
        $steps = 0;
        while ($steps < self::MAX_PACK_OBJECTS) {
            $steps++;
            $object = $this->repository->readObject($sha);
            if ($object === null) {
                return "";
            }
            if ($object["type"] == "commit") {
                return $sha;
            }
            if ($object["type"] != "tag") {
                return "";
            }
            $this->addObject($sha, $objects);
            $target = "";
            foreach (explode("\n", $object["body"]) as $line) {
                if (strncmp($line, "object ", 7) === 0) {
                    $target = trim(substr($line, 7));
                    break;
                }
            }
            if (!$this->isObjectName($target)) {
                return "";
            }
            $sha = $target;
        }
        return "";
    }
    /**
     * Adds a tree and everything under it to the set of objects to pack: the
     * tree object itself, each blob it lists, and, by walking into them, all
     * sub-trees. A tree already added is skipped, so shared folders are
     * packed once.
     *
     * @param string $tree_sha object name of the tree to collect
     * @param array &$objects running set of objects to pack
     * @param string $name path this folder goes by, used to set successive
     *      versions of one file next to each other when packing
     */
    private function collectTree($tree_sha, &$objects,
        $name = "")
    {
        if (isset($objects[$tree_sha]) ||
            isset($this->held_objects[$tree_sha])) {
            return;
        }
        $this->addObject($tree_sha, $objects, "tree:" . $name);
        foreach ($this->repository->tree($tree_sha) as $entry) {
            $entry_name = $name . "/" . $entry["name"];
            if ($entry["is_dir"]) {
                $this->collectTree($entry["sha"], $objects, $entry_name);
            } else {
                $this->addObject($entry["sha"], $objects,
                    "blob:" . $entry_name);
            }
        }
    }
    /**
     * Records one object name in the set to pack, keeping insertion order and
     * refusing to grow past the object cap.
     *
     * @param string $sha object name to add
     * @param array &$objects running set of objects to pack
     * @param string $group what the object is and the name it goes by, used
     *      to set successive versions of one file next to each other
     */
    private function addObject($sha, &$objects, $group = "")
    {
        if (!isset($objects[$sha]) && !isset($this->held_objects[$sha]) &&
            count($objects) < self::MAX_PACK_OBJECTS) {
            $objects[$sha] = true;
            $this->object_groups[$sha] = $group;
        }
    }
    /**
     * Marks a commit the client says it has, and every commit before that
     * one, as already visited, so the walk over what to send stops where
     * the two sides' histories meet rather than running on to the first
     * commit ever made.
     *
     * Marking the named commit alone is what made one pull cost a whole
     * clone. The send walk stops when it reaches a visited commit, so a
     * commit the client names that does not happen to lie on the path being
     * walked stops nothing at all, and every commit in the repository is
     * gathered along with every folder and file any of them records. On a
     * repository with years of history that is minutes of work and hundreds
     * of megabytes, for a pull that should have sent a handful of objects.
     * Walking the client's history first costs one read of each commit and
     * nothing else, since where to stop is all that is being worked out.
     *
     * @param string $have_sha object name of a commit the client says it
     *      has
     * @param array &$seen_commits running set of commits the send walk
     *      treats as already visited
     */
    private function markHeldHistory($have_sha, &$seen_commits)
    {
        $queue = [$have_sha];
        $walked = 0;
        while (!empty($queue) && $walked < self::MAX_HELD_HISTORY) {
            $sha = array_shift($queue);
            if (isset($seen_commits[$sha])) {
                continue;
            }
            $seen_commits[$sha] = true;
            $walked++;
            $object = $this->repository->readObject($sha);
            if ($object === null || $object["type"] != "commit") {
                continue;
            }
            foreach ($this->repository->commit($sha)["parents"]
                as $parent_sha) {
                $queue[] = $parent_sha;
            }
        }
    }
    /**
     * Gathers everything one commit the client says it has records: the
     * commit, the folders it names, and the files in them. A folder already
     * gathered is skipped, so walking several of the client's commits costs
     * little more than walking one, neighboring commits sharing most of
     * their folders. A name the repository does not hold, or that is not a
     * commit, is passed over.
     *
     * @param string $commit_sha object name of a commit the client has
     */
    private function collectHeld($commit_sha)
    {
        $object = $this->repository->readObject($commit_sha);
        if ($object === null || $object["type"] != "commit") {
            return;
        }
        $this->held_objects[$commit_sha] = true;
        $commit = $this->repository->commit($commit_sha);
        $this->collectHeldTree($commit["tree"], "");
    }
    /**
     * Gathers a folder the client already has and everything under it: the
     * folder itself, each file it lists, and, by walking into them, all its
     * sub-folders.
     *
     * @param string $tree_sha object name of the folder to gather
     * @param string $name path this folder goes by, so the version of each
     *      thing the client holds can be found again by name
     */
    private function collectHeldTree($tree_sha, $name = "")
    {
        if (isset($this->held_objects[$tree_sha])) {
            return;
        }
        $this->held_objects[$tree_sha] = true;
        $this->held_by_name["tree:" . $name] = $tree_sha;
        foreach ($this->repository->tree($tree_sha) as $entry) {
            $entry_name = $name . "/" . $entry["name"];
            if ($entry["is_dir"]) {
                $this->collectHeldTree($entry["sha"], $entry_name);
            } else {
                $this->held_objects[$entry["sha"]] = true;
                $this->held_by_name["blob:" . $entry_name] = $entry["sha"];
            }
        }
    }
    /**
     * Produces a packfile of the given objects a piece at a time: the "PACK"
     * signature, the count of objects, then each object, and finally a
     * checksum of everything before it. The checksum is kept running as the
     * pieces go out, so the file never has to be assembled first in order to
     * be summed, and the caller can send each piece as it arrives.
     *
     * Objects are put in an order that sets successive versions of the same
     * file next to each other, and each is then written as its difference
     * from the one before it where that comes out smaller. Since two
     * versions of a file usually share nearly all their bytes, this is what
     * keeps a clone from carrying every version at full size. A run of such
     * differences is broken every so often by a version written in full, so
     * that rebuilding any one of them never means following a long chain.
     *
     * @param array $object_names object names to write
     * @param bool $thin whether the client will accept differences built
     *      against content it already holds and completes the pack itself
     * @return \Generator yields the packfile's bytes in order
     */
    private function packChunks($object_names, $thin = false)
    {
        $ordered = $this->orderForPack($object_names);
        $checksum = hash_init("sha1");
        $header = "PACK" . pack("N", 2) . pack("N", count($ordered));
        hash_update($checksum, $header);
        yield $header;
        $previous = null;
        $chain = 0;
        foreach ($ordered as $sha) {
            $object = $this->repository->readObject($sha);
            if ($object === null) {
                throw new \Exception("git_object_unreadable " . $sha);
            }
            $group = $this->object_groups[$sha] ?? "";
            $delta = null;
            $base_sha = "";
            $small_enough = (strlen($object["body"]) <=
                self::MAX_DELTA_BODY);
            if ($previous !== null && $previous["group"] === $group &&
                $chain < self::MAX_DELTA_CHAIN && $small_enough &&
                strlen($previous["body"]) <= self::MAX_DELTA_BODY) {
                $delta = GitDelta::create($previous["body"],
                    $object["body"]);
                $base_sha = $previous["sha"];
            }
            if ($delta === null && $thin && $small_enough) {
                $held = $this->heldVersion($group);
                if ($held !== null &&
                    strlen($held["body"]) <= self::MAX_DELTA_BODY) {
                    $delta = GitDelta::create($held["body"],
                        $object["body"]);
                    $base_sha = $held["sha"];
                }
            }
            if ($delta === null) {
                $chain = 0;
                $type_code = self::TYPE_CODES[$object["type"]] ?? 0;
                $piece = $this->packObjectHeader($type_code,
                    strlen($object["body"])) . gzcompress($object["body"]);
            } else {
                $chain++;
                $piece = $this->packObjectHeader(self::TYPE_REF_DELTA,
                    strlen($delta)) . hex2bin($base_sha) .
                    gzcompress($delta);
            }
            hash_update($checksum, $piece);
            yield $piece;
            $previous = ["sha" => $sha, "body" => $object["body"],
                "group" => $group];
            /* Building a pack walks the history and works out differences,
               a long stretch with no waiting in it, so the loop is handed
               back between objects. Without this one pull held the whole
               site for minutes. */
            if (\Fiber::getCurrent() !== null) {
                \Fiber::suspend();
            }
        }
        yield hash_final($checksum, true);
    }
    /**
     * Finds the version of a folder or file that the client already holds,
     * so a new version can be sent as its difference from that rather than
     * whole. Only used when the client has said it accepts such a pack, as
     * the content built against is not sent alongside.
     *
     * @param string $group what the object is and the name it goes by
     * @return array|null ["sha" => object name of the client's version,
     *      "body" => its content], or null if the client holds no version
     */
    private function heldVersion($group)
    {
        if (!isset($this->held_by_name[$group])) {
            return null;
        }
        $sha = $this->held_by_name[$group];
        $object = $this->repository->readObject($sha);
        if ($object === null) {
            return null;
        }
        return ["sha" => $sha, "body" => $object["body"]];
    }
    /**
     * Puts the objects to be packed in an order that sets successive
     * versions of the same file, or the same folder, next to each other.
     * Commits keep the order history was walked in and come first; folders
     * and files follow, gathered by the name they go by. Only neighbors are
     * compared when packing, so this ordering is what decides which
     * differences can be found.
     *
     * @param array $object_names object names to put in order
     * @return array the same object names, ordered for packing
     */
    private function orderForPack($object_names)
    {
        $commits = [];
        $by_group = [];
        foreach ($object_names as $sha) {
            $group = $this->object_groups[$sha] ?? "";
            if ($group === "") {
                $commits[] = $sha;
                continue;
            }
            if (!isset($by_group[$group])) {
                $by_group[$group] = [];
            }
            $by_group[$group][] = $sha;
        }
        ksort($by_group);
        $ordered = $commits;
        foreach ($by_group as $group_names) {
            foreach ($group_names as $sha) {
                $ordered[] = $sha;
            }
        }
        return $ordered;
    }
    /**
     * Builds the variable-length header that precedes a packed object. The
     * first byte holds the type and the lowest four bits of the size; each
     * further byte holds seven more bits of the size, low bits first, with
     * the high bit set on every byte but the last to say more follow.
     *
     * @param int $type_code the object's pack type code
     * @param int $size the object's uncompressed size in bytes
     * @return string the encoded header
     */
    private function packObjectHeader($type_code, $size)
    {
        $first = ($type_code << self::FIRST_SIZE_BITS) |
            ($size & ((1 << self::FIRST_SIZE_BITS) - 1));
        $size = $size >> self::FIRST_SIZE_BITS;
        $header = "";
        while ($size > 0) {
            $header .= chr($first | self::CONTINUATION_FLAG);
            $first = $size & ((1 << self::CONTINUATION_SIZE_BITS) - 1);
            $size = $size >> self::CONTINUATION_SIZE_BITS;
        }
        return $header . chr($first);
    }
    /**
     * Reports whether a string is a well-formed object name: forty
     * hexadecimal characters.
     *
     * @param string $sha the string to check
     * @return bool true if it is a valid object name
     */
    private function isObjectName($sha)
    {
        return is_string($sha) && strlen($sha) == self::SHA_HEX_LENGTH &&
            ctype_xdigit($sha);
    }
}
