~ knotless Search/
↑↓ move↵ open⇧↵ all results

chadtmiller.com/knotless
Switch repository
Loading…

git that lives in your Atmosphere account

knotless.dev
1 collaborator

knotless 0.13.0 Latest 2 packages, 1 image

1
10

A stack queued lands in turn

Merged chadtmiller.com asked to merge into main from chadtmiller.com/knotless:stack/queue
.changeset/stacked-pulls-queue.mdnew+7−0
View file
@@ -0,0 +1,7 @@
---
default: minor
---
# A stack queued lands in turn
Queue each pull of a stack and each waits for the one below it, then moves to what that one landed on and lands in turn. `knotless queue` lists one waiting as `stacked`. Leaving the queue takes those waiting on the pull with it.
crates/knotless/src/cli.rs+3−0
View file
@@ -2269,6 +2269,9 @@ async fn command(
format!("{} at {}", b.state, abbrev(&b.commit)),
),
(Some(p), None) => (p.position.to_string(), w.waits_for()),
(None, _) if w.stage == crate::queue::stage::STACKED => {
("-".to_string(), "stacked".to_string())
}
(None, _) => ("-".to_string(), "ejected".to_string()),
};
writeln!(out, "{at}\t{base}\t{state}\t{}\t{}", i.uri, i.title)?;
crates/knotless/src/forge.rs+9−0
View file
@@ -125,6 +125,10 @@ pub struct Item {
/// pull's head: where this one's own changes start ([`since_of`]).
#[serde(default, skip_serializing_if = "Option::is_none")]
pub since: Option<String>,
/// Whether its head branch is in the repository it targets, the
/// target's own: a branch another pull there can be based on.
#[serde(default, skip_serializing_if = "std::ops::Not::not")]
pub own_head: bool,
/// That pull: the one it was moved off, as it landed.
#[serde(default, skip_serializing_if = "Option::is_none")]
pub below: Option<String>,
@@ -433,6 +437,10 @@ pub fn assemble(repo: &RepoRecord, owner: &str, entries: &[Entry]) -> Vec<Item>
let reviewers = pull.iter().flat_map(|p| &p.reviewers);
let reviewers = reviewers.map(|r| r.did.clone()).collect();
let reverts = pull.as_ref().and_then(|p| p.reverts.clone());
let own_head = pull.as_ref().is_some_and(|p| {
let by = parse_uri(&p.head.repo.uri).is_ok_and(|(did, ..)| did == owner);
by && p.head.repo.key == p.repo.key
});
items.push(Item {
uri: e.uri.clone(),
author: e.author.clone(),
@@ -444,6 +452,7 @@ pub fn assemble(repo: &RepoRecord, owner: &str, entries: &[Entry]) -> Vec<Item>
merged: None,
merged_from: None,
since: None,
own_head,
below: None,
merged_batch: None,
closed_by: None,
crates/knotless/src/queue.rs+127−12
View file
@@ -38,14 +38,39 @@ use serde_json::Value;
use std::collections::BTreeMap;
use std::time::Duration;
/// The open pull `item` is built on while the queue holds that one, queued
/// or ejected to be fixed: `item` waits for it out of line. As that one
/// lands, `item` moves to what it landed on ([`forge::moved_on`]), and is
/// in that branch's line.
pub fn below<'a>(items: &'a [Item], item: &Item) -> Option<&'a Item> {
let base = item.base.as_deref()?;
let held = |q: &Queued| q.state == QUEUED || q.state == EJECTED;
items.iter().find(|i| {
let named = i.own_head && i.head.as_ref().is_some_and(|h| h.branch == base);
named && i.state == "open" && i.uri != item.uri && i.queue.as_ref().is_some_and(held)
})
}
/// The branch `item` lands on once those it waits for have landed.
pub fn lands_on(items: &[Item], item: &Item) -> String {
let mut at = item;
let mut seen = vec![item.uri.as_str()];
while let Some(lower) = below(items, at).filter(|l| !seen.contains(&l.uri.as_str())) {
seen.push(&lower.uri);
at = lower;
}
at.base.clone().unwrap_or_default()
}
/// The queued pulls among `items`, in the order they were queued: the open
/// pulls whose latest queue record is `queued`. One its author made a
/// draft again after it was queued waits out of line, and is back in its
/// place once marked ready.
/// place once marked ready; so too one built on a pull the queue holds
/// ([`below`]).
pub fn queued(items: &[Item]) -> Vec<&Item> {
let in_line = |i: &&Item| {
let queued = i.queue.as_ref().is_some_and(|q| q.state == QUEUED);
i.state == "open" && queued && !i.draft
i.state == "open" && queued && !i.draft && below(items, i).is_none()
};
let mut line: Vec<&Item> = items.iter().filter(in_line).collect();
line.sort_by_key(|i| i.queue.as_ref().map(|q| q.at.clone()));
@@ -160,11 +185,31 @@ pub async fn enqueue(ctx: &Ctx, url: &RepoUrl, pull: &str) -> Result<Place> {
entries.push(Entry { uri, author, value });
}
let items = forge::assemble(&t.record, t.remote.did(), &entries);
let mut at = place(&items, pull).expect("a pull just queued is in the queue");
let mut at = place(&items, pull).unwrap_or_else(|| behind(&items, pull));
at.ejected_before = before;
Ok(at)
}
/// The place of a pull waiting for the pull below it, or of one just
/// queued that the queue reads as out of line: at the back of the branch
/// it lands on.
fn behind(items: &[Item], pull: &str) -> Place {
let item = items.iter().find(|i| i.uri == pull);
let base = item.map(|i| lands_on(items, i)).unwrap_or_default();
let ahead = queued(items);
let of = ahead
.iter()
.filter(|i| i.base.as_ref() == Some(&base))
.count()
+ 1;
Place {
base,
position: of,
of,
ejected_before: None,
}
}
/// Why the queue last ejected `item`, when it did so at `head`.
fn ejected_at(item: &Item, head: &str) -> Option<String> {
let last = item.queue.as_ref()?;
@@ -265,15 +310,34 @@ pub async fn leave(ctx: &Ctx, url: &RepoUrl, pull: &str) -> Result<()> {
let pull = t.named(pull);
let pull = pull.as_str();
maintainer(ctx, &t).await?;
let (_, item) = open_pull(ctx, &t, pull).await?;
let (entries, item) = open_pull(ctx, &t, pull).await?;
if item.queue.as_ref().is_none_or(|q| q.state != QUEUED) {
bail!("{pull} is not in the merge queue");
}
t.write(ctx, nsid::QUEUE, record(&t, pull, LEFT, None))
.await?;
let items = forge::assemble(&t.record, t.remote.did(), &entries);
// Highest first: one left waiting for nothing would land on the branch
// of the one below it.
for gone in leaving(&items, pull).iter().rev() {
t.write(ctx, nsid::QUEUE, record(&t, gone, LEFT, None))
.await?;
}
Ok(())
}
/// `pull`, then those queued that wait for it, lowest first.
fn leaving(items: &[Item], pull: &str) -> Vec<String> {
let mut going = vec![pull.to_string()];
let waits = |i: &Item, going: &[String]| {
let queued = i.queue.as_ref().is_some_and(|q| q.state == QUEUED);
let on = below(items, i).is_some_and(|b| going.contains(&b.uri));
queued && on && !going.contains(&i.uri)
};
while let Some(next) = items.iter().find(|i| waits(i, &going)) {
going.push(next.uri.clone());
}
going
}
/// Turns a pull away from the merge queue, at its head `head`, saying why,
/// as the runner landing it does.
pub async fn eject(ctx: &Ctx, t: &Target, pull: &str, ejected: Ejected<'_>) -> Result<()> {
@@ -441,6 +505,8 @@ pub mod stage {
pub const CHECKING: &str = "checking";
/// In a batch that passed, landing.
pub const LANDING: &str = "landing";
/// Out of line, waiting for the pull below it to land ([`super::below`]).
pub const STACKED: &str = "stacked";
}
impl Waiting {
@@ -480,6 +546,9 @@ impl Waiting {
},
};
}
if self.stage == stage::STACKED {
return "Waits for the pull below it to land".to_string();
}
if let Some(p) = &self.place {
let place = format!("Queued, {} of {}", ordinal(p.position), p.of);
return match self.stage.as_str() {
@@ -679,18 +748,21 @@ pub fn waiting(items: &[Item], checks: &[Check], record: &RepoRecord, owner: &st
}
})
.collect();
let ejected = items
.iter()
.filter(|i| i.state == "open" && i.queue.as_ref().is_some_and(|q| q.state == EJECTED));
waiting.extend(ejected.map(|i| Waiting {
let out_of_line = |i: &Item, stage: &str| Waiting {
item: i.clone(),
place: None,
batch: None,
preflight: Vec::new(),
stage: String::new(),
stage: stage.to_string(),
preflights: Vec::new(),
ahead: None,
}));
};
let open = || items.iter().filter(|i| i.state == "open");
let state = |i: &Item, state: &str| i.queue.as_ref().is_some_and(|q| q.state == state);
let stacked = open().filter(|i| state(i, QUEUED) && !i.draft && below(items, i).is_some());
waiting.extend(stacked.map(|i| out_of_line(i, stage::STACKED)));
let ejected = open().filter(|i| state(i, EJECTED));
waiting.extend(ejected.map(|i| out_of_line(i, "")));
waiting
}
@@ -1147,6 +1219,49 @@ mod tests {
assert_eq!(said, want);
}
#[test]
fn a_pull_waits_for_the_one_below_it() {
let on = |mut i: Item, branch: &str, base: &str, own: bool| {
let repo = json!({"uri": "at://did:o/dev.knotless.repo/r", "key": "k"});
i.head = serde_json::from_value(json!({"repo": repo, "branch": branch})).unwrap();
i.base = Some(base.to_string());
i.own_head = own;
i
};
let low = on(item("low", "open", queued_at("1")), "low", "main", true);
let mid = on(item("mid", "open", queued_at("2")), "mid", "low", true);
let top = on(item("top", "open", queued_at("3")), "top", "mid", true);
let items = [low.clone(), mid.clone(), top.clone()];
let line: Vec<&str> = queued(&items).iter().map(|i| i.title.as_str()).collect();
assert_eq!(line, ["low"]);
assert_eq!(lands_on(&items, &top), "main");
assert_eq!(behind(&items, &top.uri).position, 2);
let all = waiting(&items, &[], &RepoRecord::default(), "did:o");
let said: Vec<String> = all.iter().map(Waiting::said).collect();
let stacked = "Waits for the pull below it to land";
assert_eq!(said[1], stacked);
assert_eq!(said[2], stacked);
// Those above leave with it.
let going = leaving(&items, &low.uri);
assert_eq!(going, [low.uri.clone(), mid.uri.clone(), top.uri.clone()]);
assert_eq!(leaving(&items, &top.uri), std::slice::from_ref(&top.uri));
// One whose branch is a fork's has nothing above it wait.
let away = [on(low.clone(), "low", "main", false), mid.clone()];
assert_eq!(queued(&away).len(), 2);
// Nor does one left, or landed; so the base is that of the pull.
let mut left = low.clone();
left.queue.as_mut().unwrap().state = LEFT.to_string();
let items = [left, mid.clone()];
assert_eq!(queued(&items)[0].title, "mid");
// Those that wait for each other end, rather than go round.
let round = [
on(item("a", "open", queued_at("1")), "a", "b", true),
on(item("b", "open", queued_at("2")), "b", "a", true),
];
assert!(queued(&round).is_empty());
assert_eq!(lands_on(&round, &round[0]), "a");
}
#[test]
fn a_draft_waits_out_of_line() {
let mut draft = item("b", "open", queued_at("1"));
crates/knotless-run/tests/run.rs+48−0
View file
@@ -3831,6 +3831,54 @@ fn a_merge_queue_lands_in_batches() {
q.shows(&into, "merge queue: queued");
}
/// Pulls queued in a stack land in turn: each waits for the one below it,
/// moves to main as that lands, and its squash holds only its own changes.
/// Those above leave with one that leaves.
#[test]
fn a_stack_lands_in_turn() {
let rt = tokio::runtime::Runtime::new().unwrap();
let q = Line::new(&rt);
let url = q.url.clone();
let l = q.lander(&rt, "state.json", |_| {});
l.step(&rt);
let low = q.pull("low", "low", "low\n");
let on = |branch: &str, file: &str, base: &str| {
q.owner
.git(&q.work, &["checkout", "-q", "-b", branch, base]);
q.owner.commit_file(&q.work, file, "above\n");
q.owner.git(&q.work, &["push", "-q", "origin", branch]);
q.ok(&["pull", "create", &url, base, &url, branch, branch])
};
let mid = on("mid", "mid", "low");
q.queue(&[&low, &mid]);
let line = q.ok(&["queue", "list", &url]);
assert!(
line.contains(&format!("-\tlow\tstacked\t{mid}\t")),
"{line}"
);
assert!(
line.contains("Waits for the pull below it to land"),
"{line}"
);
for _ in 0..40 {
l.pass(&rt);
if q.ok(&["pull", "show", &url, &mid]).starts_with("merged") {
break;
}
}
q.shows(&mid, "merged pull");
assert_eq!(q.log(2), ["mid", "low"]);
q.owner.git(&q.work, &["cat-file", "-e", "origin/main:mid"]);
let under = q.pull("under", "under", "under\n");
let over = on("over", "over", "under");
q.queue(&[&under, &over]);
q.ok(&["queue", "leave", &url, &under]);
wait_until(|| q.ok(&["queue", "list", &url]).contains("empty"));
l.pass(&rt);
assert_eq!(q.log(1), ["mid"]);
}
/// A runner the repository names that may not push lands its queue
/// through the appview's gateway, which takes a batch from it only once the
/// owner has delegated writes there: until then, each batch it would land
crates/knotless-serve/src/web/queue.rs+14−10
View file
@@ -244,21 +244,25 @@ pub(super) async fn get_queue(
for w in &waiting {
let pull = item_view(&app, &record, &w.item).await;
let q = w.item.queue.clone().expect("a pull waiting was queued");
let Some(place) = &w.place else {
ejected.push(EjectedPull {
pull,
ejected_at: q.created_at,
reason: q.reason,
checks: failed_checks(&shown, &runs, &w.item),
});
continue;
let base = match &w.place {
Some(place) => place.base.clone(),
None if w.stage == queue::stage::STACKED => queue::lands_on(&items, &w.item),
None => {
ejected.push(EjectedPull {
pull,
ejected_at: q.created_at,
reason: q.reason,
checks: failed_checks(&shown, &runs, &w.item),
});
continue;
}
};
// Pulls into different branches interleave in the order they were
// queued, so each joins its branch's line wherever that is.
let at = branches.iter().position(|b| b.branch == place.base);
let at = branches.iter().position(|b| b.branch == base);
let at = at.unwrap_or_else(|| {
branches.push(QueueBranch {
branch: place.base.clone(),
branch: base.clone(),
pulls: Vec::new(),
batches: Vec::new(),
});
docs/design/collaboration.md+1−0
View file
@@ -827,6 +827,7 @@ pull whose branch it targets, or the pull it was moved off, which the moving
record names in `pull`, and up the same way. Where several pulls target one
branch, the oldest is the one followed. A retarget by hand takes a pull out.
The pull's page shows the chain, and its files page the pulls either side.
Queued, a stack [lands in turn](merge-queue.md#stacks), lowest first.
## Forks
docs/design/merge-queue.md+17−0
View file
@@ -581,3 +581,20 @@ its table.
The runner prunes batch checks it no longer needs, so each run keeps what
it read in `target/queue-stats/`, and later runs count it too. To see what
a change did, run it before and after, and compare the days either side.
## Stacks
A pull queued while the pull whose branch it targets is queued, or ejected to
be fixed, waits out of line, and `knotless queue` lists it as `stacked`. When
the pull below lands and its branch goes, the pull above moves to what it
landed on and joins that branch's line. So a stack lands in turn, lowest
first, each with its own batch. A pull ejected keeps those above waiting until
it is fixed and queued again. Leaving the queue takes those waiting on it too,
highest first, so none is left to land on the branch below.
A stack is not batched as one: batches stay what a branch's line makes of the
pulls in it, and each layer is checked on the branch as the last one left it.
A pull queued whose base is another pull's branch, with that pull not in the
queue, lands on that branch, as a part of a feature branch does. If the branch
below stays, as a protected one does, the pull above lands on it once the
pull below has gone.
docs/reference/cli.md+1−1
View file
@@ -443,7 +443,7 @@ for its method, made out to the DID in the appview's
| `pull merge` | the commit the branch is now at, then `deleted <branch>` and a `closed <issue>` line per issue it closed; queued instead, `<base> takes pulls through the merge queue: queued, <n> of <of>`, then where to follow it |
| `pull merge --queue` | `queued into <base>: <n> of <of>`; queued again at the head the queue last ejected, a line saying so and why; then where to follow it, and to read an ejection's logs before queueing again |
| `pull merge --check` | `<state>`, `<method>` and `checks <checks>`, and `reviews <passed or blocked>` when its branch asks for reviews, tab-separated, then a `missing <what>` line for each thing its reviews lack (`reviews 1 of 2`, `owners of web/: @alice or @bob`, `changes asked by @carol`, `a review of its head from @bot`; owners who are the pull's author alone add `, its author alone, whose own approval never counts, so web/ needs another owner in CODEOWNERS`), an `uncounted <why>` line for each approval that does not count (`@dan's approval does not count: only the owner's and collaborators' approvals count`), a `warning <what>` line for each CODEOWNERS line skipped, a `conflict <path>` line per file that conflicts, `deletes <branch>` for the branch it would delete, `may <what>`, `queue only` when its branch takes pulls only through the merge queue, and last why it cannot merge, in the words `pull merge` would refuse with, and that the caller may not merge it when it may not |
| `queue list` | a line per pull: `<position>`, `<base>`, `<state>`, `<uri>`, `<title>`, tab-separated, where the state is `queued`, `pre-flight <workflows>` while the [pre-flights](workflows.md#the-merge-queue) it waits for run, comma-separated, `failed <workflows>` once the newest run of one failed and none runs, as the runner has yet to eject it or run it again, or `<checking or landing> at <commit>`; an ejected pull has `-` and `ejected`, and a line after it with the reason; `the merge queue is empty` if it is |
| `queue list` | a line per pull: `<position>`, `<base>`, `<state>`, `<uri>`, `<title>`, tab-separated, where the state is `queued`, `pre-flight <workflows>` while the [pre-flights](workflows.md#the-merge-queue) it waits for run, comma-separated, `failed <workflows>` once the newest run of one failed and none runs, as the runner has yet to eject it or run it again, or `<checking or landing> at <commit>`; an ejected pull has `-` and `ejected`, and a line after it with the reason; one [waiting for the pull below it](../design/merge-queue.md#stacks) has `-` and `stacked`; `the merge queue is empty` if it is |
| `queue list --json` | each pull waiting, with its `place` and `batch`, or the `preflight` workflows it waits for |
| `queue leave` | `left the merge queue` |
| `pull edit`, `comment delete`, `pull close`, `pull reopen`, `pull retarget` | `edited`, `deleted`, `closed`, `open`, `retargeted` |
lexicons/dev/knotless/defs.json+1−1
View file
@@ -613,7 +613,7 @@
"reason": { "type": "string", "description": "Why it was ejected, as the runner said." },
"createdAt": { "type": "string", "format": "datetime", "description": "When it was queued or ejected." },
"said": { "type": "string", "description": "Where it stands, in words: `Queued, 3rd of 5, running its checks`, `In a batch of 4 being checked`, `Landing`, or why it was ejected." },
"stage": { "type": "string", "knownValues": ["queued", "preflight", "again", "ready", "review", "checking", "landing"], "description": "While queued, where it stands, as `dev.knotless.getQueue#queuedView` says." },
"stage": { "type": "string", "knownValues": ["queued", "preflight", "again", "ready", "review", "checking", "landing", "stacked"], "description": "While queued, where it stands, as `dev.knotless.getQueue#queuedView` says." },
"typical": { "type": "ref", "ref": "#queueTypicalView", "description": "While queued, how long its merge queue typically takes." },
"batchStartedAt": { "type": "string", "format": "datetime", "description": "While its batch is being checked or landing, when that started." },
"aheadStartedAt": { "type": "string", "format": "datetime", "description": "Queued in no batch, when the newest batch being checked ahead of it started." },
lexicons/dev/knotless/getQueue.json+1−1
View file
web/src/lib/organisms/MergeBox.svelte+10−2
View file