<?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;
/**
* GitUploadPack serves a Git repository to a client that clones or fetches
* it 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.
* GitUploadPack produces the two smart replies. The first is the
* advertisement a client reads to learn the repository's branches and what
* the server can do. The second answers the request in which the client
* says which commits it wants, which it has, and how much history to take.
*
* GitUploadPack reads objects through a GitRepository, which pulls commits,
* trees (folders) and blobs (file contents) out of both loose files and
* packfiles. A packfile is the one file git keeps or sends a set of
* objects in, each compressed, some stored as their differences from
* another object. GitUploadPack adds the protocol on top. It frames bytes
* into Git's length-prefixed pkt-line records, reads the client's request,
* walks history from the wanted commits, and writes the chosen objects into
* a fresh packfile. An object is written as its difference from another
* where that is smaller, and an entry already stored in the repository's
* packfile is copied as stored. 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
{
/**
* $repository is the GitRepository being served, which GitUploadPack
* reads branches, tags and objects through
* @var object
*/
private $repository;
/**
* $held_objects holds, as keys, the object names the client already
* has, gathered from the commits it says it has and the folders and
* files those record. Anything in here is left out of the packfile (the
* one file the reply's objects travel in), since sending a file the
* client already has turns a small update into a copy of the whole
* working tree.
* @var array
*/
private $held_objects = [];
/**
* $object_groups gives, 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 lets each be sent as its small difference from the one before.
* @var array
*/
private $object_groups = [];
/**
* $held_by_name gives, 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 the thin-pack
* capability (the client's word that it will finish such a pack from
* its own copies) allows.
* @var array
*/
private $held_by_name = [];
/**
* PKT_LENGTH_DIGITS is how many hexadecimal (base sixteen) digits begin
* every pkt-line (one record of git's protocol) and give its length
* @var int
*/
const PKT_LENGTH_DIGITS = 4;
/**
* FLUSH_PKT is the flush marker, a pkt-line (one record of git's
* protocol) whose length field is all zeros, which separates one
* section of the protocol from the next
* @var string
*/
const FLUSH_PKT = "0000";
/**
* MAX_PKT_LENGTH is the largest number of bytes one pkt-line (one
* record of git's protocol) can carry, including its own four-digit
* length, as the pack protocol fixes it
* @var int
*/
const MAX_PKT_LENGTH = 65520;
/**
* SHA_HEX_LENGTH is how many hexadecimal (base sixteen) characters an
* object name
* has; git names an object by the SHA-1 checksum (a 20-byte summary)
* of its contents
* @var int
*/
const SHA_HEX_LENGTH = 40;
/**
* OBJECT_TYPE_COMMIT is the number a packfile (the one file a set of
* git objects travels in) puts in an object's header to say it is a
* commit
* @var int
*/
const OBJECT_TYPE_COMMIT = 1;
/**
* OBJECT_TYPE_TREE is the number a packfile (the one file a set of git
* objects travels in) puts in an object's header to say it is a tree,
* which is git's word for a folder
* @var int
*/
const OBJECT_TYPE_TREE = 2;
/**
* OBJECT_TYPE_BLOB is the number a packfile (the one file a set of git
* objects travels in) puts in an object's header to say it is a blob,
* which is git's word for a file's contents
* @var int
*/
const OBJECT_TYPE_BLOB = 3;
/**
* OBJECT_TYPE_TAG is the number a packfile (the one file a set of git
* objects travels in) puts in an object's header to say it is an
* annotated tag, a named label on a commit with a message of its own
* @var int
*/
const OBJECT_TYPE_TAG = 4;
/**
* TYPE_CODES maps git's words for the kinds of object to the numbers
* a packfile (the one file a set of git objects travels in) puts 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];
/**
* FIRST_SIZE_BITS is how many bits of an object's size fit in the
* first byte of its header in a packfile (the one file a set of git
* objects travels in): the low four, after the three that give its
* kind
* @var int
*/
const FIRST_SIZE_BITS = 4;
/**
* CONTINUATION_SIZE_BITS is how many bits of an object's size each
* further byte of its header in a packfile (the one file a set of git
* objects travels in) carries: the low seven
* @var int
*/
const CONTINUATION_SIZE_BITS = 7;
/**
* CONTINUATION_FLAG is the high bit of a byte of an object's header in
* a packfile (the one file a set of git objects travels in), set to
* say that another byte of the size follows
* @var int
*/
const CONTINUATION_FLAG = 0x80;
/**
* MAX_PACK_OBJECTS is the most objects one reply may pack, so a request
* cannot make the server walk an unbounded amount of history at once
* @var int
*/
const MAX_PACK_OBJECTS = 250000;
/**
* MAX_HELD_HISTORY is the most commits of the client's own history
* markHeldHistory walks 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;
/**
* TYPE_REF_DELTA is the number a packfile (the one file a set of git
* objects travels in) puts in an object's header to say the object is
* written as its difference from another object, named outright
* @var int
*/
const TYPE_REF_DELTA = 7;
/**
* MAX_DELTA_CHAIN is the most objects in a row that packChunks writes
* 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 = 50;
/**
* MAX_DELTA_BODY is the largest object, in bytes, that packChunks sends
* as a difference from another (16 megabytes). 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 is sent whole.
* @var int
*/
const MAX_DELTA_BODY = 16777216;
/**
* UPLOAD_PACK_SERVICE is the service name a client that clones or
* fetches, and so only reads, asks for
* @var string
*/
const UPLOAD_PACK_SERVICE = "git-upload-pack";
/**
* THIN_PACK_CAPABILITY is the word 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";
/**
* CAPABILITIES lists what 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.
* "allow-tip-sha1-in-want" and "allow-reachable-sha1-in-want" let a
* client ask for an object by its name rather than by a branch or tag
* name, so someone who knows a commit name can fetch just that commit
* and its history; without them a client refuses to send the request at
* all and says the server does not allow an unadvertised object.
* "deepen-relative" lets a client with a shallow history ask for a
* number of commits more beyond where its history stops, which is what
* git fetch --deepen sends; without it git refuses with "Server does
* not support --deepen".
* 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 " .
"allow-tip-sha1-in-want allow-reachable-sha1-in-want " .
self::DEEPEN_RELATIVE;
/**
* DEEPEN_RELATIVE is the name of the capability a client adds to its
* first want line when the depth it asks for counts from its own
* shallow commits rather than from the commits it wants
* @var string
*/
const DEEPEN_RELATIVE = "deepen-relative";
/**
* __construct makes a GitUploadPack that serves one repository.
* GitComponent makes one for each clone or fetch request it answers.
*
* @param object $repository the GitRepository whose branches, tags and
* objects are to be served
*/
public function __construct($repository)
{
$this->repository = $repository;
}
/**
* pktLine wraps a piece of data as one pkt-line, the record git's
* protocol is made of: the length, counting the four length digits
* themselves, in four hexadecimal digits, followed by the data. Every
* line of a reply GitUploadPack builds, and of a request a test sends
* it, is framed this way.
*
* @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;
}
/**
* decodePktLines splits a run of pkt-lines, the length-prefixed records
* git's protocol is made of, into the pieces of data they carry.
* parseUploadRequest reads a client's request with it, and GitComponent
* reads a request's lines for its log. 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;
}
/**
* advertiseRefs builds the advertisement a client reads first, with an
* HTTP GET request, to learn about the repository. It names the
* service, then lists every ref (a branch or tag name) with the object
* it points at, attaching the server's capabilities to the first line.
* It points HEAD at the default branch so the client knows which branch
* to check out. An annotated tag also gets a peeled line, which gives
* the commit the tag finally refers to. GitComponent sends it as the
* body of the info/refs reply.
*
* @return string the advertisement as pkt-lines (git's length-prefixed
* records), 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;
}
/**
* parseUploadRequest turns the pkt-lines (git's length-prefixed
* records) a client posted into the lists and settings uploadPackChunks
* works from. The client lists the object names it wants and the
* object names it already has, so the server can leave their history
* out. A client with a shallow history names the commits that history
* stops at, and may say how deep a history to send. The last round
* ends with "done". Of the capabilities the client adds to its first
* want line, thin-pack and deepen-relative are read; the rest change
* nothing here.
*
* @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,
* "thin" => whether the client takes a thin pack,
* "shallow" => the commits the client's shallow history stops at,
* which it holds without their parents,
* "relative" => whether the depth counts from those shallow
* commits rather than from the wanted commits, as git fetch
* --deepen asks]
*/
public function parseUploadRequest($request_body)
{
$wants = [];
$haves = [];
$client_shallow = [];
$capabilities = [];
$depth = 0;
$done = false;
foreach (self::decodePktLines($request_body) as $line) {
if ($line === false || $line === "") {
continue;
}
$parts = explode(" ", $line);
$names_object = isset($parts[1]) &&
strlen($parts[1]) == self::SHA_HEX_LENGTH &&
ctype_xdigit($parts[1]);
if ($parts[0] == "want" && $names_object) {
$wants[$parts[1]] = true;
foreach (array_slice($parts, 2) as $capability) {
$capabilities[trim($capability)] = true;
}
} else if ($parts[0] == "have" && $names_object) {
$haves[$parts[1]] = true;
} else if ($parts[0] == "shallow" && $names_object) {
$client_shallow[$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]),
"shallow" => array_keys($client_shallow),
"relative" => isset($capabilities[self::DEEPEN_RELATIVE])];
}
/**
* uploadPackChunks is the generator GitComponent draws a clone's or
* fetch's whole reply from. It yields each piece of the reply as soon
* as that piece is made, rather than building the whole reply first.
*
* Yielding keeps a large clone from holding the server's memory:
* GitComponent::serveUploadPack writes each piece to a file, and the
* web server sends that file while the rest is made. The packfile (the
* one file the reply's objects travel in) is never held in memory, and
* the client starts receiving before it is finished.
*
* A request with a depth, or from a client with a shallow history,
* first gets the shallow lines, which say where the new history ends,
* and the unshallow lines, which say where the client's old history no
* longer ends.
*
* 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"], $request["shallow"], $request["relative"],
$request["done"]);
if ($request["depth"] > 0) {
foreach ($walk["shallow"] as $shallow_sha) {
yield self::pktLine("shallow " . $shallow_sha . "\n");
}
foreach ($walk["unshallow"] as $unshallow_sha) {
yield self::pktLine("unshallow " . $unshallow_sha . "\n");
}
yield self::FLUSH_PKT;
if (!$request["done"]) {
/* A round that offers held commits waits for its
acknowledgments after where the history ends; one that
offers none, as the first does, waits for nothing more. */
if (!empty($request["haves"])) {
yield from $this->negotiationRoundChunks($commons);
}
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"]);
}
/**
* negotiationRoundChunks gives the acknowledgment lines that close a
* round in which the client offered commits it holds and has not yet
* said it is done. uploadPackChunks sends them. 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");
}
/**
* commonCommits keeps, of the commits a client offers as held, those
* this repository has too; uploadPackChunks acknowledges them. 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;
}
/**
* walkWanted decides which objects go in the reply's pack, for
* uploadPackChunks. Starting at the wanted commits, it follows history
* back and takes each commit the client lacks together with the whole
* tree of folders and files that commit records. When a depth is given
* the walk keeps only that many commits deep along each parent line,
* and the commits at the cutoff are marked as shallow. A wanted object
* that is a tag is followed to the commit it names first.
*
* A client whose own history is shallow names the commits it stops at.
* Such a commit is held but its parents are not. Where the new history
* ends is worked out first by shallowCutoff, from the wanted commits
* or, for git fetch --deepen, from the client's shallow commits. The
* walk that gathers objects then goes on through commits the client
* holds, packing none of them, and stops at that new cutoff.
*
* @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
* does not pack these or their history
* @param array $client_shallow object names of the commits the
* client's shallow history stops at
* @param bool $relative whether $depth counts from the client's shallow
* commits rather than from the wanted commits
* @param bool $pack whether to gather the objects to pack; false for a
* round of a depth request that only asks where history ends
* @return array ["objects" => ordered list of object names to pack,
* "shallow" => object names of commits at the depth cutoff,
* "unshallow" => the client's shallow commits whose parents are
* now sent]
*/
private function walkWanted($wants, $depth, $haves = [],
$client_shallow = [], $relative = false, $pack = true)
{
$objects = [];
$held_commits = [];
$client_shallow = array_flip($client_shallow);
$this->held_objects = [];
$this->held_by_name = [];
$queue = [];
foreach ($wants as $want) {
$commit_sha = $this->resolveToCommit($want, $objects);
if ($commit_sha != "") {
$queue[] = $commit_sha;
}
}
$cutoff = ["shallow" => [], "unshallow" => []];
if ($depth > 0) {
$cutoff = $this->shallowCutoff($relative ?
array_keys($client_shallow) : $queue, $depth +
($relative ? 1 : 0), $client_shallow);
}
if (!$pack) {
return ["objects" => [], "shallow" => $cutoff["shallow"],
"unshallow" => $cutoff["unshallow"]];
}
foreach ($haves as $have_sha) {
$this->markHeldHistory($have_sha, $held_commits,
$client_shallow);
$this->collectHeld($have_sha);
}
$stop_at = array_flip($cutoff["shallow"]);
$visited = [];
while (!empty($queue)) {
$commit_sha = array_shift($queue);
if (isset($visited[$commit_sha])) {
continue;
}
$visited[$commit_sha] = true;
$held = isset($held_commits[$commit_sha]);
/* Without a depth the client holds all history under a commit
it holds. With one, a commit it holds may lie above its old
shallow commits, under which the new commits are. */
if ($held && $depth <= 0) {
continue;
}
$commit = $this->repository->commit($commit_sha);
if (!$held) {
$this->addObject($commit_sha, $objects);
$this->collectTree($commit["tree"], $objects, "");
}
/* Walking a history has no waiting in it, so the loop is
handed back after each commit. A full clone of a long
history spent seconds here before the first object was
packed, and without this the whole site waited with it. */
if (\Fiber::getCurrent() !== null) {
\Fiber::suspend();
}
if (isset($stop_at[$commit_sha])) {
continue;
}
foreach ($commit["parents"] as $parent_sha) {
$queue[] = $parent_sha;
}
}
return ["objects" => array_keys($objects),
"shallow" => $cutoff["shallow"],
"unshallow" => $cutoff["unshallow"]];
}
/**
* shallowCutoff works out where a depth-limited history ends: the
* commits that many levels down from the starting commits, counting a
* starting commit as level one, whose parents are not sent. walkWanted
* calls it with the wanted commits for git fetch --depth, and with the
* client's shallow commits and one level more for git fetch --deepen,
* so that the history goes that many commits past where the client's
* stops. Only commits are read, not their folders, since where history
* ends is all that is being worked out.
*
* @param array $starts object names of the commits to count from
* @param int $levels how many levels of commits the history keeps
* @param array $client_shallow the client's shallow commits, as keys
* @return array ["shallow" => commits at the cutoff that have parents,
* "unshallow" => the client's shallow commits the history now goes
* past, whose parents are sent]
*/
private function shallowCutoff($starts, $levels, $client_shallow)
{
$queue = [];
foreach ($starts as $start_sha) {
$queue[] = [$start_sha, 1];
}
$visited = [];
$shallow = [];
$expanded = [];
while (!empty($queue)) {
[$commit_sha, $level] = array_shift($queue);
if (isset($visited[$commit_sha]) ||
$this->repository->readObject($commit_sha) === null) {
continue;
}
$visited[$commit_sha] = true;
$parents = $this->repository->commit($commit_sha)["parents"];
if ($level >= $levels && !empty($parents)) {
$shallow[$commit_sha] = true;
continue;
}
$expanded[$commit_sha] = true;
foreach ($parents as $parent_sha) {
$queue[] = [$parent_sha, $level + 1];
}
}
return ["shallow" => array_keys($shallow),
"unshallow" => array_keys(array_intersect_key($client_shallow,
$expanded))];
}
/**
* resolveToCommit follows a wanted object name to the commit it stands
* for, so walkWanted can start its walk there. A commit is returned as
* itself. An annotated tag is unwrapped, and the tag object is added to
* the pack on the way, until a commit is reached. Anything that is not
* a commit or tag gives 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 (strlen($target) != self::SHA_HEX_LENGTH ||
!ctype_xdigit($target)) {
return "";
}
$sha = $target;
}
return "";
}
/**
* collectTree adds a tree (git's word for a folder) and everything
* under it to the set of objects to pack, for each commit walkWanted
* sends: the tree object itself, each blob (file contents) it lists,
* and, by walking into them, all its sub-folders. A tree already added,
* or one the client holds, 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);
}
}
}
/**
* addObject is how walkWanted and the methods it calls put an object
* into the set to pack, along with the group orderForPack later sorts
* it by. The set keeps the order names were added in, leaves out
* objects the client holds, and stops growing at MAX_PACK_OBJECTS.
*
* @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;
}
}
/**
* markHeldHistory fills the set of commits the client is known to
* have, starting from one commit it offered and going back through all
* that commit's ancestors. walkWanted's walk over what to send then
* 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.
*
* A client with a shallow history holds a shallow commit but not its
* parents, so the marking stops at each commit the client named as
* shallow. Marking past it took the parents a deepening fetch asks for
* as already held, and the fetch brought nothing.
*
* @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
* @param array $client_shallow the client's shallow commits, as keys,
* whose parents the client does not hold
*/
private function markHeldHistory($have_sha, &$seen_commits,
$client_shallow = [])
{
$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++;
if (\Fiber::getCurrent() !== null) {
\Fiber::suspend();
}
$object = $this->repository->readObject($sha);
if ($object === null || $object["type"] != "commit" ||
isset($client_shallow[$sha])) {
continue;
}
foreach ($this->repository->commit($sha)["parents"]
as $parent_sha) {
$queue[] = $parent_sha;
}
}
}
/**
* collectHeld gathers into $held_objects everything one commit the
* client says it has records: the commit, the folders it names, and the
* files in them. walkWanted calls it for each such commit, so nothing
* the client holds is packed. 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"], "");
}
/**
* collectHeldTree gathers into $held_objects 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. It also records each
* under the name it goes by in $held_by_name, so that a new version of
* a file can be sent as its difference from the client's copy.
* collectHeld calls it on a commit's top folder.
*
* @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"];
}
}
}
/**
* packChunks produces a packfile (the one file a set of git objects
* travels in) of the given objects a piece at a time, for the end of
* uploadPackChunks's reply. The packfile holds the "PACK" signature,
* the count of objects, then each object compressed, 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;
$sending = array_flip($ordered);
foreach ($ordered as $sha) {
/* An object already stored in a packfile is copied as it is
stored, still compressed, when the client will be able to
read it: whole, or as a delta on an object this pack also
sends, or, in a thin pack, on one the client holds. A delta
the packfile gives by position is sent by its base's name,
since positions in the new pack differ. */
$entry = $this->repository->storedEntry($sha);
if ($entry !== null && ($entry["base"] === "" ||
isset($sending[$entry["base"]]) ||
($thin && isset($this->held_objects[$entry["base"]])))) {
$piece = ($entry["base"] === "") ?
$this->packObjectHeader($entry["kind"],
$entry["size"]) . $entry["data"] :
$this->packObjectHeader(self::TYPE_REF_DELTA,
$entry["size"]) . hex2bin($entry["base"]) .
$entry["data"];
$entry = null;
hash_update($checksum, $piece);
yield $piece;
$previous = null;
$chain = 0;
if (\Fiber::getCurrent() !== null) {
\Fiber::suspend();
}
continue;
}
$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);
/* A delta's object takes the type of the object it is built
on, so tags and commits, which share the group "", are only
built on their own kind. */
if ($previous !== null && $previous["group"] === $group &&
$previous["type"] === $object["type"] &&
$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, "type" => $object["type"]];
/* 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);
}
/**
* heldVersion gives packChunks the client's own copy of a folder or
* file, looked up by the name it goes by, so a new version can be sent
* as its difference from that copy rather than whole. It is 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"]];
}
/**
* orderForPack puts the objects packChunks is to pack 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;
}
/**
* packObjectHeader builds the header of varying length that packChunks
* writes before each object it packs. The first byte holds the object's
* kind and the lowest four bits of its 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 number the pack uses for the object's kind,
* such as OBJECT_TYPE_COMMIT
* @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);
}
}
- Yioop Repo - Seekquarry