chadtmiller.com/pds.js

Switch repository

Loading…

/**
 * Assembling the push that merges a pull request.
 *
 * Merging is the authority's own act on the authority's own repository, so
 * this runs on that server under that account's session. It takes two object
 * stores, the canonical copy's and the copy holding the work, and answers with
 * a bundle to append and the ref to move. It writes nothing: the caller owns
 * the blobs and the record.
 *
 * The two stores are on different servers and neither holds the other's
 * objects, but a commit id is the same id everywhere, so the intersection of
 * two walks is the merge base. Where the base is main's own tip the result
 * tree is the branch's own. Where main has moved, the result is the
 * three-way merge of the two against the base, and a conflict refuses the
 * merge and names the paths.
 *
 * Workers-clean: no node imports.
 */

import { buildMergeCommit, mergeable, mergeTrailers } from './merge-commit.js';
import { mergeTrees } from './merge3.js';
import { parseCommit, parseTree } from './objects.js';
import { buildBundleIndex, encodePackIndex } from './pack-index.js';
import { writeBundle, writePack } from './pack-write.js';

/**
 * How far back main is read to place a branch against it. A branch taken
 * further back than this reads as unrelated, which is the honest answer from
 * a bounded walk rather than a guess.
 */
const MAIN_DEPTH = 1000;

/** How many commits of a branch are read before it counts as unrelated. */
const BRANCH_DEPTH = 500;

/**
 * What a bundle chain presents to a walk over it.
 * @typedef {Object} ObjectStore
 * @property {(sha: string) => {type: string, size: number}|null} meta
 * @property {(sha: string) => Promise<{type: string, data: Uint8Array}|null>} get
 */

/**
 * The commits one tip reaches, newest first, to a bounded depth.
 * @param {ObjectStore} store
 * @param {string} tip
 * @param {number} depth
 * @returns {Promise<string[]>}
 */
async function history(store, tip, depth) {
  /** @type {string[]} */
  const walked = [];
  const seen = new Set();
  let at = tip;
  while (at && walked.length < depth && !seen.has(at)) {
    seen.add(at);
    walked.push(at);
    const object = await store.get(at);
    if (object?.type !== 'commit') break;
    at = parseCommit(object.data).parents[0];
  }
  return walked;
}

/**
 * Every object a tree holds that the canonical copy lacks, the tree itself
 * included.
 *
 * A subtree whose id the canonical copy already has is skipped whole. Two
 * copies of one repository share almost every tree, so this is what keeps the
 * cost of a merge on the size of the change rather than the repository.
 * @param {Pick<ObjectStore, 'get'>} source
 * @param {ObjectStore} main
 * @param {string} root - a tree id
 * @param {Map<string, {type: string, data: Uint8Array}>} into
 */
async function collectTree(source, main, root, into) {
  if (main.meta(root) || into.has(root)) return;
  const tree = await source.get(root);
  if (!tree || tree.type !== 'tree') return;
  into.set(root, tree);
  for (const entry of parseTree(tree.data)) {
    // A submodule names a commit in another repository, which this one has
    // never held and is not merging now.
    if (entry.type === 'submodule') continue;
    if (main.meta(entry.sha) || into.has(entry.sha)) continue;
    if (entry.type === 'dir') {
      await collectTree(source, main, entry.sha, into);
      continue;
    }
    const blob = await source.get(entry.sha);
    if (blob) into.set(entry.sha, blob);
  }
}

/**
 * @typedef {Object} Merge
 * @property {string} sha - the commit that carries the work onto main
 * @property {string} ref - the canonical ref it moves
 * @property {Uint8Array} bundle
 * @property {Uint8Array} index - the pack index for that bundle
 * @property {string[]} heads - what the bundle carries, for the record entry
 * @property {number} objects - how many objects it adds
 */

/**
 * Build the push that merges one pull request.
 *
 * @param {Object} ctx
 * @param {ObjectStore} ctx.main - the canonical copy's objects
 * @param {ObjectStore} ctx.source - the objects of the copy holding the work
 * @param {string} ctx.mainTip
 * @param {string} ctx.branchTip
 * @param {string} ctx.canonicalRef - full ref name main lives under
 * @param {'merge'|'squash'} ctx.mode
 * @param {{did: string, repo: string, ref: string}} ctx.from - the copy and
 *   branch the work came from, for the trailers
 * @param {{name: string, email: string}} ctx.by - who is merging it
 * @param {number} ctx.at - epoch milliseconds
 * @param {string} ctx.subject
 * @param {string} [ctx.body]
 * @returns {Promise<Merge>}
 */
export async function buildMerge(ctx) {
  const { main, source, mainTip, branchTip, canonicalRef, mode, from } = ctx;

  // Asked before the walk, so a ref pointing at a tag or a tree is named for
  // what it is rather than reported as sharing no history with main.
  const tip = await source.get(branchTip);
  if (tip?.type !== 'commit') {
    throw new Error('That branch does not end in a commit.');
  }
  const branchTree = parseCommit(tip.data).tree;

  const inMain = new Set(await history(main, mainTip, MAIN_DEPTH));
  const branch = await history(source, branchTip, BRANCH_DEPTH);
  const base = branch.find((sha) => inMain.has(sha)) ?? null;

  const answer = mergeable({ base, sha: branchTip }, mainTip);
  if (!answer.can) throw new Error(answer.why);

  /** @type {Map<string, {type: string, data: Uint8Array}>} */
  const objects = new Map();

  // Main has moved: the result is what the two sides come to against the
  // base. The objects the merge makes are new to both copies and travel.
  let tree = branchTree;
  if (base !== mainTip) {
    const [baseCommit, mainCommit] = await Promise.all([
      main.get(/** @type {string} */ (base)),
      main.get(mainTip),
    ]);
    if (!baseCommit || !mainCommit) {
      throw new Error('Main could not be read for the merge.');
    }
    const merged = await mergeTrees(
      { get: async (sha) => (await main.get(sha)) ?? (await source.get(sha)) },
      parseCommit(baseCommit.data).tree,
      parseCommit(mainCommit.data).tree,
      branchTree,
      {
        labels: {
          ours: canonicalRef.replace(/^refs\/heads\//, ''),
          theirs: from.ref.replace(/^refs\/heads\//, ''),
        },
      },
    );
    if (merged.conflicts.length > 0) {
      throw new Error(
        `This branch conflicts with main in ${merged.conflicts.join(', ')}.`,
      );
    }
    for (const [sha, object] of merged.objects) {
      if (!main.meta(sha)) objects.set(sha, object);
    }
    tree = merged.sha;
  }
  // A walk over the result reads what the merge made before what the branch
  // holds, so a merged subtree opens and its unchanged children come from
  // the branch's copy.
  const made = {
    /** @param {string} sha */
    get: async (sha) => objects.get(sha) ?? (await source.get(sha)),
  };
  // A merge names the branch tip as a parent, so main's history has to reach
  // every commit of the branch, and a walk over that history opens each one's
  // own tree. The tip's tree alone is not enough: git reads every commit it
  // can reach, and a tree that is not there fails the whole fetch.
  //
  // A squash names only main, so the commits it squashed are unreachable and
  // stay where they are. Only the tree the result points at travels.
  if (mode === 'merge') {
    for (const sha of branch) {
      if (sha === base || main.meta(sha)) break;
      const commit = await source.get(sha);
      if (!commit) continue;
      objects.set(sha, commit);
      await collectTree(source, main, parseCommit(commit.data).tree, objects);
    }
  }
  await collectTree(made, main, tree, objects);

  const commit = buildMergeCommit({
    mode,
    tree,
    mainTip,
    branchTip,
    by: ctx.by,
    at: ctx.at,
    subject: ctx.subject,
    body: ctx.body,
    trailers: mergeTrailers(from),
  });

  const pack = writePack([...objects.values(), commit]);
  const bundle = writeBundle({
    refs: [{ sha: commit.sha, name: canonicalRef }],
    // What the reader must already hold. Main's tip covers the canonical
    // history; a merge also assumes nothing else, because every object the
    // branch adds is in the pack above.
    prerequisites: [mainTip],
    pack,
  });
  // No delta base to resolve: writePack stores every object whole, so nothing
  // in this pack refers outside it.
  const index = encodePackIndex(await buildBundleIndex(bundle));

  return {
    sha: commit.sha,
    ref: canonicalRef,
    bundle,
    index,
    heads: [commit.sha],
    objects: objects.size + 1,
  };
}