Files
figcraft/crates/collab/src/history.rs
BFlatandClaude Opus 5.5 94ff3d4df6 M9: collaboration: per-user undo, rejections, reconnect (#105)
* M9: collaboration: per-user undo, rejections, reconnect

Step 3 of docs/collab-protocol.md, the parts that don't need the transport:

- Per-user undo and redo (figcraft_collab::Client::{undo, redo}): each undoable batch is a step
  (values before/after by target, nodes created/deleted). Others' batches ordered after the step
  take its targets for good; creates invert to deletes (not when others built inside), deletes
  re-create the subtree. An undo or redo waits for every earlier batch and is remade from the
  confirmed state when it goes out; derived data follows as a follow-up batch.
- Rejections: refused batches leave the history (with an undo waiting on them) and queue a
  Notice; the engine shows it through Session::message (the UI's toast).
- Offline queue and reconnect: Hello.resume {session, client_id, seq}; the server keeps a
  bounded log and answers with the missed batches or a snapshot, plus what it did with the
  client's batches (processed {last_batch, refused}); queued batches then go out.
  Server::state / restore persist the session (client-id counter, log, session id).
- Presence carries editing_text {node, caret, selection}.
- Engine: documents in a live session (LiveDoc, Session::collab_*): commands, gestures and
  groups sync as one step each; edit.undo / edit.redo route to the per-user history; remote
  edits show under a gesture in progress. Outside a session snapshot undo is unchanged.
- Sim: dropped connections, undo/redo, and a checker that no undo reverts a change by someone
  else its author had seen. New tests in undo_tests, reconnect_tests, collab_live_tests,
  collab_undo_tests.
- CLAUDE.md / AGENTS.md: collab in the L2 layer list.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

* M9: collaboration wording in the progress docs after per-user undo and reconnect

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

* M9: protocol doc: what the engine's live-session tests cover

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

---------

Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
2026-10-11 03:19:24 +07:00

429 lines
17 KiB
Rust

//! Per-user undo and redo in a live session. Every undoable batch of this client becomes a
//! [`Step`]: the values it wrote and the values they replaced, by [`Target`], plus the nodes it
//! created or deleted. Undoing a step writes the replaced values back, but only where nobody else
//! wrote after the step (the server ordered someone else's batch after it); redo goes the other
//! way. Batches from others never become steps.
use std::collections::{BTreeMap, BTreeSet};
use figcraft_doc::NodeId;
use crate::Error;
use crate::change::{Change, DocProp, Entry, Family, Json, Prop, Target};
use crate::replica::{Mode, Replica, create_change};
/// Index of the state before a step in its two-sided records.
pub(crate) const BACK: usize = 0;
/// Index of the state after a step.
pub(crate) const FWD: usize = 1;
/// What a batch of this client is for.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum BatchKind {
/// An edit (one command or gesture).
Edit,
/// Undoing an edit.
Undo,
/// Redoing an undone edit.
Redo,
/// Derived data brought up to date after other batches (never in the undo history).
FollowUp,
}
/// Something to tell the user (a short toast).
#[derive(Clone, Debug, PartialEq)]
pub enum Notice {
/// The server refused one of this client's batches: what it changed is rolled back and it
/// leaves the undo history.
Rejected { batch_id: u64, kind: BatchKind, reason: String },
/// The session restarted while this client was away: its unconfirmed batches are gone.
Lost { batches: usize },
}
impl Notice {
/// The text to show.
pub fn message(&self) -> String {
match self {
Notice::Rejected { kind: BatchKind::Undo, reason, .. } => format!("Couldn't undo: {reason}"),
Notice::Rejected { kind: BatchKind::Redo, reason, .. } => format!("Couldn't redo: {reason}"),
Notice::Rejected { reason, .. } => format!("Your change couldn't be applied: {reason}"),
Notice::Lost { batches } => {
format!("The live session restarted: {batches} unsent change{} couldn't be kept", if *batches == 1 { "" } else { "s" })
}
}
}
}
/// The two sides of a value: before and after the step.
type Sides<T> = [T; 2];
/// What a batch wrote, by target.
type Writes = BTreeMap<Target, Sides<Option<Json>>>;
/// Nodes that exist on one side only: the change creating them as they are there.
type Nodes = BTreeMap<NodeId, Sides<Option<Change>>>;
/// One entry of the undo history.
#[derive(Clone, Debug)]
pub(crate) struct Step {
/// Unique within the client (batches name their step by it).
pub id: u64,
pub label: String,
/// The batch that last applied this step: the edit, or its latest undo or redo (which may
/// still wait to be sent).
pub batch: u64,
/// The server confirmed the step's last batch that was sent, and nothing of it is in flight:
/// batches from others ordered after it conflict with it.
pub confirmed: bool,
/// That confirmed batch went towards the after side (the edit or a redo; false: an undo).
pub settled_forward: bool,
/// While an undo or redo of the step is in flight: what it writes, and what others wrote
/// meanwhile (ordered before it, unless the connection drops and it is made again).
in_flight: Option<(BTreeSet<Target>, Touches)>,
writes: Writes,
nodes: Nodes,
/// Targets others wrote after this step: it never writes them again.
taken: BTreeSet<Target>,
/// Nodes others created again after this step (by their undo): it never deletes them.
taken_nodes: BTreeSet<NodeId>,
}
/// What `changes` (a batch that turned `pre` into `post`) wrote, oriented `[pre, post]`; with
/// `same`, also the targets it wrote that kept their value.
fn capture(pre: &Replica, post: &Replica, changes: &[Change], same: bool) -> Result<(Writes, Nodes), Error> {
let (a, b) = (pre.document(), post.document());
let mut writes = Writes::new();
let mut nodes = Nodes::new();
for c in changes {
match c {
Change::Create { id, .. } => {
if let Some(n) = b.node(*id)
&& !a.contains(*id)
{
nodes.insert(*id, [None, Some(create_change(n, post.key(*id))?)]);
}
}
Change::Delete { id } => {
for d in a.subtree(*id) {
if let Some(n) = a.node(d)
&& !b.contains(d)
{
nodes.insert(d, [Some(create_change(n, pre.key(d))?), None]);
}
}
}
other => {
let Some(t) = Target::of(other) else { continue };
if writes.contains_key(&t) {
continue;
}
let (x, y) = (pre.value(&t)?, post.value(&t)?);
// A node created or deleted by the batch is recorded whole above.
let missing = matches!(t, Target::Node(..)) && (x.is_none() || y.is_none());
if !missing && (same || x != y) {
writes.insert(t, [x, y]);
}
}
}
}
Ok((writes, nodes))
}
impl Step {
/// The step for batch `batch` that turned `pre` into `post` with `changes`.
pub fn new(id: u64, label: &str, batch: u64, pre: &Replica, post: &Replica, changes: &[Change]) -> Result<Step, Error> {
let (writes, nodes) = capture(pre, post, changes, false)?;
Ok(Step {
id,
label: label.to_string(),
batch,
confirmed: false,
settled_forward: true,
writes,
nodes,
taken: BTreeSet::new(),
taken_nodes: BTreeSet::new(),
in_flight: None,
})
}
/// A batch of the step (its edit, an undo or a redo: `kind`) was applied again, now on top of
/// `pre` (giving `post`): what it replaced is now taken from `pre` (others' batches were
/// ordered before it, or an earlier batch of this client was refused) and what it wrote from
/// `post`. The edit's nodes become those it now creates and deletes (a layer someone put
/// inside a layer it deletes comes back with an undo); an undo or redo only updates the nodes
/// of the step (what it takes with it beyond them was someone else's).
pub fn refresh(&mut self, pre: &Replica, post: &Replica, changes: &[Change], kind: BatchKind) -> Result<(), Error> {
let (writes, nodes) = capture(pre, post, changes, true)?;
let (p, q) = if kind == BatchKind::Undo { (FWD, BACK) } else { (BACK, FWD) };
for (t, [x, y]) in writes {
if !self.taken.contains(&t)
&& let Some(s) = self.writes.get_mut(&t)
{
s[p] = x;
s[q] = y;
}
}
let oriented = nodes.into_iter().map(|(id, [x, y])| {
let mut s = [None, None];
s[p] = x;
s[q] = y;
(id, s)
});
if kind == BatchKind::Edit {
self.nodes = oriented.collect();
} else {
for (id, s) in oriented {
if let Some(e) = self.nodes.get_mut(&id) {
*e = s;
}
}
}
Ok(())
}
/// An undo or redo of the step (`changes`) goes out: until the server confirms it, others'
/// batches are ordered before it.
pub fn send(&mut self, changes: &[Change]) {
self.confirmed = false;
self.in_flight = Some((changes.iter().filter_map(Target::of).collect(), Touches::default()));
}
/// The server confirmed the step's batch of `kind`.
pub fn settle(&mut self, kind: BatchKind) {
self.confirmed = true;
self.in_flight = None;
self.settled_forward = kind != BatchKind::Undo;
}
/// Its undo or redo in flight was lost with the connection: it will be made again, so what
/// others wrote meanwhile came after the step's last confirmed batch.
pub fn lost(&mut self) {
self.confirmed = true;
if let Some((_, seen)) = self.in_flight.take() {
self.taint(&seen, &BTreeSet::new());
}
}
/// Someone else's batch (`touches`) was ordered after the step's last batch, or before its
/// batch in flight: the targets it writes are theirs from now on, except those the batch in
/// flight writes again after them.
pub fn others_wrote(&mut self, touches: &Touches) {
if self.confirmed {
self.taint(touches, &BTreeSet::new());
} else if let Some((mine, seen)) = self.in_flight.take() {
self.taint(touches, &mine);
let mut seen = seen;
seen.absorb(touches);
self.in_flight = Some((mine, seen));
}
}
/// Leave the targets `touches` writes (but those in `except`) alone from now on.
fn taint(&mut self, touches: &Touches, except: &BTreeSet<Target>) {
for t in self.writes.keys() {
if touches.hits(t) && !except.contains(t) {
self.taken.insert(t.clone());
}
}
for id in self.nodes.keys() {
if touches.nodes.contains(id) {
self.taken_nodes.insert(*id);
}
}
}
/// The batches since this step are unknown (a reconnect brought a snapshot): every target
/// whose value in `state` isn't the one the step's confirmed batch wrote was changed by others.
pub fn verify(&mut self, state: &Replica) -> Result<(), Error> {
let side = if self.settled_forward { FWD } else { BACK };
for (t, v) in &self.writes {
if !self.taken.contains(t) && state.value(t)? != v[side] {
self.taken.insert(t.clone());
}
}
Ok(())
}
/// The batch that takes `view` to this step's `side` (BACK: undo, FWD: redo): nodes of that
/// side created again (parents first), the values of that side written back, then nodes of
/// the other side deleted. Leaves out targets others wrote since, nodes that no longer fit
/// (a parent gone) and created nodes others have put layers into. Every change of the result
/// applies (validated in order).
pub fn toward(&self, side: usize, view: &Replica) -> Result<Vec<Change>, Error> {
let other = 1 - side;
let mut work = view.clone();
let mut out = Vec::new();
let doc = view.document();
// Nodes to bring back, shallowest first (a parent before its children).
let back: BTreeMap<NodeId, &Change> = self
.nodes
.iter()
.filter(|(id, s)| s[other].is_none() && !self.taken_nodes.contains(*id) && !doc.contains(**id))
.filter_map(|(id, s)| s[side].as_ref().map(|c| (*id, c)))
.collect();
let depth = |mut id: NodeId| {
let mut d = 0usize;
while let Some(Change::Create { parent: Some(p), .. }) = back.get(&id).copied() {
d += 1;
id = *p;
if d > back.len() {
break;
}
}
d
};
let mut todo: Vec<(usize, Change)> = back.iter().map(|(id, c)| (depth(*id), (*c).clone())).collect();
todo.sort_by_key(|(d, _)| *d);
let mut todo: Vec<Change> = todo.into_iter().map(|(_, c)| c).collect();
for (t, v) in &self.writes {
let moved_away = matches!(t, Target::Node(id, Prop::Position) if self.taken.contains(&Target::Node(*id, Prop::Parent)));
if self.taken.contains(t) || moved_away {
continue;
}
let now = work.value(t)?;
if matches!(t, Target::Node(..)) && now.is_none() {
continue;
}
let want = v[side].as_ref();
if now.as_ref() == want {
continue;
}
todo.extend(t.write(want));
}
apply_all(&mut work, &mut out, todo);
// Nodes to remove: those that exist only on the other side, when nothing else is inside.
let gone: BTreeSet<NodeId> = self
.nodes
.iter()
.filter(|(id, s)| s[side].is_none() && s[other].is_some() && !self.taken_nodes.contains(*id))
.map(|(id, _)| *id)
.collect();
let wdoc = work.document();
let mut stack: Vec<NodeId> =
gone.iter().copied().filter(|id| wdoc.node(*id).is_some_and(|n| n.parent.is_none_or(|p| !gone.contains(&p)))).collect();
let mut deletes = Vec::new();
while let Some(id) = stack.pop() {
if wdoc.subtree(id).iter().all(|d| gone.contains(d)) {
deletes.push(Change::Delete { id });
} else if let Some(n) = wdoc.node(id) {
stack.extend(n.children.iter().copied().filter(|c| gone.contains(c)));
}
}
apply_all(&mut work, &mut out, deletes);
// Changes that apply one by one can still fail the batch's checks together (rare): keep
// only those that pass them in order.
if view.clone().apply(&out, Mode::Strict).is_err() {
let mut w = view.clone();
out.retain(|c| {
let mut t = w.clone();
let ok = t.apply(std::slice::from_ref(c), Mode::Strict).is_ok();
if ok {
w = t;
}
ok
});
}
Ok(out)
}
}
/// Apply `todo` to `work` change by change, keeping in `out` those that apply; changes that don't
/// are retried while others still go in (a move back can depend on another move back).
fn apply_all(work: &mut Replica, out: &mut Vec<Change>, mut todo: Vec<Change>) {
loop {
let before = todo.len();
let mut left = Vec::new();
for c in todo {
match work.apply(std::slice::from_ref(&c), Mode::Lenient) {
Ok(a) if a.skipped == 0 => out.push(c),
_ => left.push(c),
}
}
if left.is_empty() || left.len() == before {
return;
}
todo = left;
}
}
/// What a batch from someone else wrote, for marking the steps it conflicts with.
#[derive(Clone, Debug, Default)]
pub(crate) struct Touches {
props: BTreeSet<(NodeId, Prop)>,
/// Nodes created (or created again): all their properties are written.
nodes: BTreeSet<NodeId>,
docs: BTreeSet<DocProp>,
entries: BTreeSet<Entry>,
/// Lists written whole.
whole: BTreeSet<Family>,
/// Lists written in any way (whole, order or an entry).
lists: BTreeSet<Family>,
}
impl Touches {
/// Add what `other` writes.
pub fn absorb(&mut self, other: &Touches) {
self.props.extend(other.props.iter().copied());
self.nodes.extend(other.nodes.iter().copied());
self.docs.extend(other.docs.iter().copied());
self.entries.extend(other.entries.iter().cloned());
self.whole.extend(other.whole.iter().copied());
self.lists.extend(other.lists.iter().copied());
}
pub fn of(changes: &[Change]) -> Touches {
let mut t = Touches::default();
for c in changes {
match c {
Change::Create { id, .. } => {
t.nodes.insert(*id);
}
Change::Set { id, prop, .. } => {
t.props.insert((*id, *prop));
}
Change::Delete { .. } => {}
Change::SetDoc { prop, .. } => {
t.docs.insert(*prop);
match prop.list() {
Some(Ok(l)) => {
t.whole.insert(l);
t.lists.insert(l);
}
Some(Err(l)) => {
t.lists.insert(l);
}
None => {}
}
}
Change::Put { entry, .. } | Change::Remove { entry } => {
t.entries.insert(entry.clone());
if let Some(l) = entry.list() {
t.lists.insert(l);
}
}
}
}
t
}
/// Whether these writes change `target`.
pub fn hits(&self, target: &Target) -> bool {
match target {
Target::Node(id, p) => self.props.contains(&(*id, *p)) || self.nodes.contains(id),
Target::Doc(p) => {
self.docs.contains(p)
|| match p.list() {
Some(Ok(l)) => self.lists.contains(&l),
Some(Err(l)) => self.whole.contains(&l),
None => false,
}
}
Target::Entry(e) => self.entries.contains(e) || e.list().is_some_and(|l| self.whole.contains(&l)),
}
}
/// Whether these writes create node `id`.
pub fn creates(&self, id: NodeId) -> bool {
self.nodes.contains(&id)
}
}