stack-breadcrumb.yml

# SPDX-License-Identifier: MIT
# Adapted from the taskless/taskless stack-breadcrumb workflow and brought into
# this repository under its MIT license, with permission.
name: Stack Breadcrumb

# Self-contained stacked-PR breadcrumb. All logic lives in a zero-dependency
# module (.github/scripts/stack-breadcrumb.cjs) that each job loads via
# actions/github-script — no pnpm/tsx/package install, no build step.
#
# Two stages keep reconciliation serialized per stack root:
#   STAGE 1 (dispatch)  — on PR shape-change events, resolve the affected
#                         root(s) and fire a `repository_dispatch`.
#   STAGE 2 (reconcile) — on that dispatch (or a manual `workflow_dispatch`),
#                         render and propagate the breadcrumb, serialized per
#                         root, AND "true" the stack: re-run any stale
#                         `stack`-prefixed check that a shape change left failing
#                         on a PR that is no longer the tip.
#
# Two CARRY jobs run on a member's MERGE, embedding the merged PR's body into a
# surviving PR as a keyed `<!-- PR:N -->` region below the tree:
#   CARRY-FORWARD  (merge into a NON-default base, tip→root) — an atomic collapse
#                  accumulates the merged CHILD into its parent ("Contains #N").
#   CARRY-BACKWARD (merge into the DEFAULT branch, root→tip) — an incremental
#                  land absorbs the merged PARENT into the redirected root (the
#                  child GitHub retargets onto the default branch), headed
#                  "Built on top of #N".
# Either way the PR that finally reaches the default branch holds the full stack
# legacy; a merge with no surviving stack neighbour is a clean no-op.
#
# Stage 1 fires the dispatch with the built-in GITHUB_TOKEN: although that token
# normally suppresses recursive workflow runs, `repository_dispatch` is a
# documented exception, so stage 2 fires. NOTE: `repository_dispatch` always runs
# from the DEFAULT BRANCH's copy of this file, so the live breadcrumb (driven by
# PR events → dispatch → reconcile) activates only once this is merged to `main`.
# `workflow_dispatch` instead runs from the branch you select in the "Run
# workflow" menu, so it can be used to test the reconcile stage before merge.

on:
  pull_request:
    # Tree SHAPE only — no `synchronize` (a head push never changes membership).
    types: [opened, reopened, edited, closed]
  repository_dispatch:
    types: [stack-reconcile]
  workflow_dispatch:
    inputs:
      root:
        description: "Root PR number to reconcile (leave empty to reconcile all open stacks)"
        required: false
        default: ""

# Permissions are least-privilege per job: stage 1 only POSTs a dispatch; only
# stage 2 writes PR bodies.
permissions: {}

jobs:
  dispatch:
    name: Resolve root and dispatch reconcile
    # Skip fork PRs (read-only token) and the bot's own body edits. The built-in
    # GITHUB_TOKEN already won't retrigger workflows, but the actor guard makes
    # the no-loop guarantee explicit for any non-token edit too.
    if: >-
      github.event_name == 'pull_request'
      && github.event.pull_request.head.repo.full_name == github.repository
      && github.event.sender.login != 'github-actions[bot]'
    runs-on: ubuntu-latest
    permissions:
      contents: write # required to POST repository_dispatch
      pull-requests: read # walk the tree
    concurrency:
      group: stack-breadcrumb-dispatch-${{ github.event.pull_request.number }}
      cancel-in-progress: true
    steps:
      # Check out the DEFAULT branch's copy of the script, not the PR head: this
      # privileged job (contents: write) must run trusted, reviewed logic, never
      # PR-supplied code.
      - uses: actions/checkout@v4
        with:
          ref: ${{ github.event.repository.default_branch }}

      - uses: actions/github-script@v7
        with:
          script: |
            const scriptPath = `${process.env.GITHUB_WORKSPACE}/.github/scripts/stack-breadcrumb.cjs`;
            let stack;
            try {
              stack = require(scriptPath);
            } catch (error) {
              // Bootstrap: before this workflow is on the default branch the
              // script isn't there yet. Skip rather than fail.
              if (error.code === "MODULE_NOT_FOUND") {
                core.info("stack-breadcrumb script not on the default branch yet; skipping until merged.");
                return;
              }
              throw error;
            }
            const { owner, repo } = context.repo;

            const defaultBranch = (await github.rest.repos.get({ owner, repo })).data.default_branch;
            const rawPulls = await github.paginate(github.rest.pulls.list, {
              owner, repo, state: "open", per_page: 100,
            });
            // Same-repo PRs only: the tree keys parents by branch name, so a fork
            // PR sharing a branch name would corrupt root resolution.
            const pullRequests = rawPulls
              .filter((pr) => pr.head.repo?.full_name === `${owner}/${repo}`)
              .map((pr) => ({
                number: pr.number,
                title: pr.title,
                headRefName: pr.head.ref,
                baseRefName: pr.base.ref,
                body: pr.body ?? "",
              }));

            const trigger = {
              number: context.payload.pull_request.number,
              baseRefName: context.payload.pull_request.base.ref,
            };
            const roots = stack.resolveAffectedRoots(trigger, pullRequests, defaultBranch);
            if (roots.length === 0) {
              core.info(`PR #${trigger.number} affects no open stack; nothing to dispatch`);
              return;
            }
            for (const root of roots) {
              await github.rest.repos.createDispatchEvent({
                owner, repo, event_type: "stack-reconcile", client_payload: { root },
              });
              core.info(`dispatched reconcile for root #${root}`);
            }

  carry-forward:
    name: Carry a merged PR's body into its parent
    # On a stack member's MERGE, embed its body into its parent PR as a keyed
    # `<!-- PR:N -->` region below the tree, so an atomic collapse (tip→root)
    # accumulates the full legacy on the PR that finally lands on the default
    # branch. Incremental delivery (each PR merges straight to the default
    # branch) has no open parent PR to carry into → a clean no-op.
    if: >-
      github.event_name == 'pull_request'
      && github.event.action == 'closed'
      && github.event.pull_request.merged == true
      && github.event.pull_request.base.ref != github.event.repository.default_branch
      && github.event.pull_request.head.repo.full_name == github.repository
      && github.event.sender.login != 'github-actions[bot]'
    runs-on: ubuntu-latest
    permissions:
      contents: read # actions/checkout needs this (top-level permissions: {} grants no defaults)
      pull-requests: write # edit the parent PR body
    concurrency:
      # Serialize per PARENT branch (the body we write); convergent upserts make
      # this safe, and we must not cancel a carry mid-write.
      group: stack-carry-forward-${{ github.event.pull_request.base.ref }}
      cancel-in-progress: false
    steps:
      # Trusted script from the default branch — never PR-supplied code.
      - uses: actions/checkout@v4
        with:
          ref: ${{ github.event.repository.default_branch }}

      - uses: actions/github-script@v7
        with:
          script: |
            const scriptPath = `${process.env.GITHUB_WORKSPACE}/.github/scripts/stack-breadcrumb.cjs`;
            let stack;
            try {
              stack = require(scriptPath);
            } catch (error) {
              if (error.code === "MODULE_NOT_FOUND") {
                core.info("stack-breadcrumb script not on the default branch yet; skipping until merged.");
                return;
              }
              throw error;
            }
            const { owner, repo } = context.repo;
            const merged = context.payload.pull_request;

            // The parent is the open PR whose head branch is this PR's base.
            const rawPulls = await github.paginate(github.rest.pulls.list, {
              owner, repo, state: "open", per_page: 100,
            });
            const parent = rawPulls.find(
              (pr) =>
                pr.head.repo?.full_name === `${owner}/${repo}` &&
                pr.head.ref === merged.base.ref
            );
            if (!parent) {
              core.info(`#${merged.number} merged into "${merged.base.ref}", which has no open parent PR — nothing to carry (incremental land).`);
              return;
            }

            // Fetch fresh bodies — the event payload can lag a last-moment edit.
            const [{ data: mergedFresh }, { data: parentFresh }] = await Promise.all([
              github.rest.pulls.get({ owner, repo, pull_number: merged.number }),
              github.rest.pulls.get({ owner, repo, pull_number: parent.number }),
            ]);

            const newBody = stack.carryForward(
              parentFresh.body ?? "",
              merged.number,
              mergedFresh.body ?? ""
            );
            if (newBody === (parentFresh.body ?? "")) {
              core.info(`#${merged.number} already carried into #${parent.number}; nothing to do.`);
              return;
            }
            await github.rest.pulls.update({ owner, repo, pull_number: parent.number, body: newBody });
            core.info(`carried #${merged.number} into parent #${parent.number}`);

  carry-backward:
    name: Absorb a merged parent into the redirected root
    # On a member's merge INTO THE DEFAULT BRANCH (an incremental forward land),
    # embed the merged PR's body into the open child that was built on it — the
    # PR GitHub retargets onto the default branch to become the new root — as a
    # keyed `<!-- PR:N -->` region headed "Built on top of #N". A merge to the
    # default branch with no such child (a standalone PR, or the genuine last
    # slice) has nothing to absorb into → a clean no-op.
    if: >-
      github.event_name == 'pull_request'
      && github.event.action == 'closed'
      && github.event.pull_request.merged == true
      && github.event.pull_request.base.ref == github.event.repository.default_branch
      && github.event.pull_request.head.repo.full_name == github.repository
      && github.event.sender.login != 'github-actions[bot]'
    runs-on: ubuntu-latest
    permissions:
      contents: read # actions/checkout needs this (top-level permissions: {} grants no defaults)
      pull-requests: write # edit the redirected-root PR body
    concurrency:
      # Serialize retries of THIS merge event; convergent upserts make it safe,
      # and we must not cancel an absorb mid-write.
      group: stack-carry-backward-${{ github.event.pull_request.number }}
      cancel-in-progress: false
    steps:
      # Trusted script from the default branch — never PR-supplied code.
      - uses: actions/checkout@v4
        with:
          ref: ${{ github.event.repository.default_branch }}

      - uses: actions/github-script@v7
        with:
          script: |
            const scriptPath = `${process.env.GITHUB_WORKSPACE}/.github/scripts/stack-breadcrumb.cjs`;
            let stack;
            try {
              stack = require(scriptPath);
            } catch (error) {
              if (error.code === "MODULE_NOT_FOUND") {
                core.info("stack-breadcrumb script not on the default branch yet; skipping until merged.");
                return;
              }
              throw error;
            }
            const { owner, repo } = context.repo;
            const merged = context.payload.pull_request;
            const defaultBranch = context.payload.repository.default_branch;

            // The redirected root is the open child built on the merged PR. Find
            // it two ways, because merging the root may have deleted its head
            // branch and made GitHub retarget the child onto the default branch:
            //   1. base still points at the merged root's head branch (branch
            //      not deleted, or the retarget hasn't landed yet);
            //   2. otherwise the child's breadcrumb marker records the merged PR
            //      as its parent, and its base is now the default branch.
            // A branching stack can have several such children (each becomes an
            // independent root); absorb the parent into every one.
            const rawPulls = await github.paginate(github.rest.pulls.list, {
              owner, repo, state: "open", per_page: 100,
            });
            const sameRepo = rawPulls.filter(
              (pr) => pr.head.repo?.full_name === `${owner}/${repo}`
            );
            const children = sameRepo.filter((pr) => {
              if (pr.base.ref === merged.head.ref) return true;
              if (pr.base.ref !== defaultBranch) return false;
              const marker = stack.parseStackComment(pr.body ?? "");
              return marker !== undefined && marker.parents.get(pr.number) === merged.number;
            });
            if (children.length === 0) {
              core.info(`#${merged.number} merged into "${merged.base.ref}" with no open child built on it — nothing to absorb (standalone or last slice).`);
              return;
            }

            // Fetch the merged body fresh — the event payload can lag a
            // last-moment edit.
            const { data: mergedFresh } = await github.rest.pulls.get({
              owner, repo, pull_number: merged.number,
            });

            for (const child of children) {
              const { data: childFresh } = await github.rest.pulls.get({
                owner, repo, pull_number: child.number,
              });
              const newBody = stack.carryBackward(
                childFresh.body ?? "",
                merged.number,
                mergedFresh.body ?? ""
              );
              if (newBody === (childFresh.body ?? "")) {
                core.info(`#${merged.number} already absorbed into #${child.number}; nothing to do.`);
                continue;
              }
              await github.rest.pulls.update({ owner, repo, pull_number: child.number, body: newBody });
              core.info(`absorbed #${merged.number} into redirected root #${child.number}`);
            }

  reconcile:
    name: Reconcile breadcrumb across the stack
    if: github.event_name == 'repository_dispatch' || github.event_name == 'workflow_dispatch'
    runs-on: ubuntu-latest
    permissions:
      contents: read # checkout
      pull-requests: write # edit PR bodies
      actions: write # re-run stale stack-dependent checks ("trueing" the stack)
    # One reconcile per root at a time. A burst for one root collapses to the
    # latest run; convergent writes make cancellation safe.
    concurrency:
      group: stack-reconcile-${{ github.event.client_payload.root || github.event.inputs.root || 'all' }}
      cancel-in-progress: true
    steps:
      - uses: actions/checkout@v4

      - uses: actions/github-script@v7
        with:
          script: |
            const stack = require(`${process.env.GITHUB_WORKSPACE}/.github/scripts/stack-breadcrumb.cjs`);
            const { owner, repo } = context.repo;

            const defaultBranch = (await github.rest.repos.get({ owner, repo })).data.default_branch;
            const rawPulls = await github.paginate(github.rest.pulls.list, {
              owner, repo, state: "open", per_page: 100,
            });
            // Same-repo PRs only: a fork PR sharing a branch name would corrupt
            // branch-name-keyed tree derivation.
            const pullRequests = rawPulls
              .filter((pr) => pr.head.repo?.full_name === `${owner}/${repo}`)
              .map((pr) => ({
                number: pr.number,
                title: pr.title,
                headRefName: pr.head.ref,
                baseRefName: pr.base.ref,
                body: pr.body ?? "",
                state: "open",
                headSha: pr.head.sha,
              }));

            // Preserve construction history: pull in stack members recorded in
            // existing breadcrumb markers that are no longer open (merged/closed),
            // so the tree keeps listing them and the last open PR captures the
            // whole stack. Their bodies are frozen (reconcile never rewrites a
            // non-open member); they're fetched only for tree structure/rendering.
            // Root resolution below still uses the open-PR list only.
            const openNumbers = new Set(pullRequests.map((pr) => pr.number));
            const historicalNumbers = new Set();
            for (const pr of pullRequests) {
              const marker = stack.parseStackComment(pr.body);
              if (!marker) continue;
              for (const member of marker.members) {
                // Guard against a malformed marker (non-positive / non-integer)
                // and skip members that are already open.
                if (Number.isInteger(member) && member > 0 && !openNumbers.has(member)) {
                  historicalNumbers.add(member);
                }
              }
            }
            // PR bodies are user-editable, so a crafted/malformed marker could
            // list many members; cap the historical fetch defensively (with a log).
            const MAX_HISTORICAL_MEMBERS = 50;
            let historicalList = [...historicalNumbers].toSorted((a, b) => a - b);
            if (historicalList.length > MAX_HISTORICAL_MEMBERS) {
              core.info(`stack-breadcrumb: marker lists ${historicalList.length} historical members; capping at ${MAX_HISTORICAL_MEMBERS}`);
              historicalList = historicalList.slice(0, MAX_HISTORICAL_MEMBERS);
            }
            // Fetch in parallel (bounded by the cap above); keep same-repo PRs.
            const fetched = (
              await Promise.all(
                historicalList.map(async (number) => {
                  try {
                    const { data: pr } = await github.rest.pulls.get({ owner, repo, pull_number: number });
                    if (pr.head.repo?.full_name !== `${owner}/${repo}`) return undefined;
                    return {
                      number: pr.number,
                      title: pr.title,
                      headRefName: pr.head.ref,
                      baseRefName: pr.base.ref,
                      body: pr.body ?? "",
                      state: pr.state, // "closed" (merged or closed) — freezes rewrites
                    };
                  } catch (error) {
                    core.info(`stack-breadcrumb: could not fetch historical PR #${number}: ${String(error)}`);
                    return undefined;
                  }
                })
              )
            ).filter((pr) => pr !== undefined);
            // The tree is keyed by headRefName, so admit a historical PR only if
            // its head ref is not already claimed — by an open PR OR an earlier
            // historical one. A reused branch name would otherwise corrupt tree
            // derivation.
            const claimedHeadRefs = new Set(pullRequests.map((pr) => pr.headRefName));
            const historical = [];
            for (const pr of fetched) {
              if (claimedHeadRefs.has(pr.headRefName)) {
                core.info(`stack-breadcrumb: skipping historical PR #${pr.number}; head ref "${pr.headRefName}" already claimed by another PR`);
                continue;
              }
              claimedHeadRefs.add(pr.headRefName);
              historical.push(pr);
            }
            const allPullRequests = [...pullRequests, ...historical];

            const writeBody = async (number, body) => {
              await github.rest.pulls.update({ owner, repo, pull_number: number, body });
            };

            // Root values can arrive as strings (dispatch payloads) or typos
            // (manual input); coerce to a positive integer.
            const parseRoot = (value) => {
              const parsed = Number(value);
              return Number.isInteger(parsed) && parsed > 0 ? parsed : undefined;
            };

            // repository_dispatch always carries client_payload.root (stage 1 sets
            // it); workflow_dispatch carries inputs.root (empty → reconcile all).
            let roots;
            if (context.eventName === "repository_dispatch") {
              const root = parseRoot(context.payload.client_payload?.root);
              if (root === undefined) {
                core.setFailed(`repository_dispatch requires a positive integer client_payload.root; got ${JSON.stringify(context.payload.client_payload?.root)}`);
                return;
              }
              // The root came from stage 1 but the stack may have shifted since.
              const actualRoot = stack.findRoot(root, pullRequests, defaultBranch);
              if (actualRoot === undefined) {
                // Documented race: the root merged/closed between dispatch and
                // reconcile. Safe, explicit no-op — a later event re-resolves.
                core.info(`root #${root} is no longer an open PR; nothing to reconcile.`);
                return;
              }
              // Normalize to the current true root in case membership changed.
              roots = [actualRoot];
            } else {
              const rawInput = context.payload.inputs?.root;
              if (rawInput) {
                const root = parseRoot(rawInput);
                if (root === undefined) {
                  core.setFailed(`workflow_dispatch input "root" must be a positive integer PR number; got "${rawInput}"`);
                  return;
                }
                // Manual input: fail loudly if it isn't an open PR or isn't the
                // actual stack root, rather than reconciling the wrong subtree.
                const actualRoot = stack.findRoot(root, pullRequests, defaultBranch);
                if (actualRoot === undefined) {
                  core.setFailed(`workflow_dispatch input #${root} is not an open PR.`);
                  return;
                }
                if (actualRoot !== root) {
                  core.setFailed(`workflow_dispatch input #${root} is not a stack root; its root is #${actualRoot}. Re-run with #${actualRoot}, or leave the input empty to reconcile all stacks.`);
                  return;
                }
                roots = [root];
              } else {
                roots = stack.findAllRoots(pullRequests, defaultBranch);
              }
            }

            // reconcile() continues past an individual failed write (safe
            // failure) and records it; surface any such failures as a job
            // failure so an inconsistent breadcrumb doesn't pass silently.
            const failures = [];
            for (const root of roots) {
              const result = await stack.reconcile(root, { pullRequests: allPullRequests, writeBody });
              core.info(`reconciled root #${root}: ${JSON.stringify(result)}`);
              failures.push(...result.failed);
            }

            // "Trueing" the stack: a stack shape change can leave a PR's
            // stack-position-dependent checks (e.g. the OpenSpec archive gate)
            // failing on a PR that is no longer the tip. GitHub won't re-run a
            // PR's checks when a *different* PR changes, so do it here — re-run
            // any workflow run on an affected (open) PR that has a FAILED
            // `stack`-prefixed job. Failing tests and green/skipped stack checks
            // are left alone.
            const rechecked = new Set();
            for (const root of roots) {
              const tree = stack.buildTree(root, allPullRequests);
              for (const number of tree.members) {
                if (rechecked.has(number)) continue;
                rechecked.add(number);
                const pr = allPullRequests.find((p) => p.number === number);
                if (!pr || pr.state !== "open" || !pr.headSha) continue;
                const runs = await github.paginate(github.rest.actions.listWorkflowRunsForRepo, {
                  owner, repo, head_sha: pr.headSha, per_page: 100,
                });
                const seenWorkflows = new Set();
                for (const run of runs) {
                  // Consider only the latest run per workflow for this head SHA.
                  if (seenWorkflows.has(run.workflow_id)) continue;
                  seenWorkflows.add(run.workflow_id);
                  // A still-running latest run will report fresh on its own; a
                  // run that did not fail overall cannot contain a failed job, so
                  // skip the job fetch for it entirely.
                  if (run.status !== "completed" || run.conclusion !== "failure") continue;
                  const jobs = await github.paginate(github.rest.actions.listJobsForWorkflowRun, {
                    owner, repo, run_id: run.id, per_page: 100,
                  });
                  if (!stack.hasFailedStackJob(jobs)) continue;
                  try {
                    await github.rest.actions.reRunWorkflow({ owner, repo, run_id: run.id });
                    core.info(`recheck: re-ran "${run.name}" (run ${run.id}) on PR #${number}`);
                  } catch (error) {
                    core.info(`recheck: could not re-run run ${run.id} on PR #${number}: ${String(error)}`);
                  }
                }
              }
            }

            if (failures.length > 0) {
              core.setFailed(`Failed to update ${failures.length} PR body/bodies: ${failures.map((n) => `#${n}`).join(", ")}. See logs above.`);
            }