Skip to content

armgit / macro

Public Imported from GitHub
0

Macro is a unified workspace for teams: email, chat, docs, tasks, agents, calls, and CRM — @-linked together with shared AI memory.

18.8 KB
Raw Blame
//! Collaborative editing: a design shared as CRDT maps of node states.
//!
//! Every peer opens the stored `.fig` and then applies the shared entries,
//! which hold only what changed since the collaboration began:
//!
//! | container | key | value |
//! | --- | --- | --- |
//! | `figMeta` | `format`, `baseBlobs` | entry layout version; blobs every peer's file starts with |
//! | `figMeta` | `base`, `file:<fingerprint>` | the stored files the entries apply to (written by the web app's `core/collab-entries.ts`) |
//! | `figNodes` | node id (`12:34`) | the node's whole state ([`codec::NodeState`], base64) |
//! | `figBlobs` | content key | geometry or glyph blob (base64) |
//! | `figImages` | SHA-1 | image file (base64) |
//!
//! A node entry is the node's absolute state after an edit (properties,
//! parent and position, removed or not), so applying it is idempotent and
//! independent of the order entries arrive in: concurrent edits to
//! different nodes merge, and edits to one node resolve last-writer-wins.
//! Saving the merged file and opening it again, then applying the same
//! entries, gives the same document, so the stored file can be replaced at
//! any time.
//!
//! [`Collab`] tracks what this peer changed ([`Collab::record`], reported by
//! [`Collab::changes`]) and applies other peers' entries
//! ([`Collab::apply`]). Each peer creates nodes in its own guid session, so
//! new ids never collide. Undo stays local: an undo is an ordinary change
//! of the nodes it restores.

pub mod codec;
pub mod position;

use crate::document::{Document, Node, NodeIdx};
use crate::edit::flags;
use crate::model::Guid;
use codec::{BlobRef, DecodeError, NodeState, Reader, Writer, base64, blob_key, unbase64};
use serde::{Deserialize, Serialize};
use std::collections::{BTreeSet, HashMap, HashSet};
use std::hash::{Hash, Hasher};
use std::sync::Arc;

/// Version of the entry layout, stored in `figMeta.format`.
pub const FORMAT_VERSION: u32 = 1;

/// Images larger than this are not shared live; peers see them once the
/// merged file is saved and opened again.
pub const MAX_SHARED_IMAGE_BYTES: usize = 8 * 1024 * 1024;

/// Names of the maps that hold a collaborative design.
pub mod container {
    /// Format metadata.
    pub const META: &str = "figMeta";
    /// Node id → node state.
    pub const NODES: &str = "figNodes";
    /// Content key → blob.
    pub const BLOBS: &str = "figBlobs";
    /// SHA-1 → image file.
    pub const IMAGES: &str = "figImages";
    /// Every container.
    pub const ALL: [&str; 4] = [META, NODES, BLOBS, IMAGES];
}

/// Keys of the `figMeta` map.
pub mod meta {
    /// The entry layout version.
    pub const FORMAT: &str = "format";
    /// How many blobs the file had when the collaboration began. Blobs
    /// below it are the same in every later save, so entries refer to them
    /// by index.
    pub const BASE_BLOBS: &str = "baseBlobs";
}

/// One entry written (`value`) or deleted (`None`).
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct EntryChange {
    /// The map.
    pub container: String,
    /// The key within it.
    pub key: String,
    /// The new value; absent or null deletes the entry.
    #[serde(default)]
    pub value: Option<String>,
}

impl EntryChange {
    fn set(container: &str, key: impl Into<String>, value: String) -> Self {
        Self {
            container: container.to_owned(),
            key: key.into(),
            value: Some(value),
        }
    }
}

/// What applying other peers' changes did.
#[derive(Debug, Default)]
pub struct Remote {
    /// Nodes that changed, and parents whose children changed.
    pub touched: Vec<NodeIdx>,
    /// Images that arrived (renderers forget that they were missing).
    pub images: Vec<String>,
}

/// One peer's view of the shared maps.
pub struct Collab {
    session: u32,
    base_blobs: u32,
    /// Shared key of each blob added during the collaboration.
    blob_keys: HashMap<u32, Arc<str>>,
    /// Blobs in the shared map (written or received) → document index.
    blobs_by_key: HashMap<Arc<str>, u32>,
    /// Images every peer has: in the file, written, or received.
    images_shared: HashSet<String>,
    /// Hash of each node's entry as last written or applied.
    synced: HashMap<Guid, u64>,
    /// Nodes changed here since the last [`Collab::changes`].
    dirty: BTreeSet<NodeIdx>,
    /// Edit flags of every field changed during the collaboration, by any
    /// peer: saving rewrites them whichever version of the file a peer
    /// opened.
    flags: HashMap<Guid, u64>,
    /// Entries waiting for blobs that have not arrived.
    pending: HashMap<Guid, String>,
    /// Nodes whose parent has not arrived.
    unlinked: HashSet<Guid>,
}

fn value_hash(value: &str) -> u64 {
    let mut h = std::hash::DefaultHasher::new();
    value.hash(&mut h);
    h.finish()
}

impl Collab {
    /// Starts collaborating on an opened document. New nodes get ids in
    /// `session` (unique per peer). `base_blobs` is `figMeta.baseBlobs`
    /// when the shared maps have it; otherwise this peer's count is used
    /// and returned as a change to write.
    pub fn new(
        doc: &mut Document,
        session: u32,
        base_blobs: Option<u32>,
    ) -> (Collab, Vec<EntryChange>) {
        let local = doc
            .nodes
            .iter()
            .filter_map(|n| n.props.guid)
            .filter(|g| g.session == session)
            .map(|g| g.local)
            .max()
            .unwrap_or(0);
        doc.next_guid = Guid {
            session,
            local: local + 1,
        };
        let original = doc.original_blobs as u32;
        let mut changes = Vec::new();
        let base_blobs = match base_blobs {
            Some(n) => n.min(original),
            None => {
                changes.push(EntryChange::set(
                    container::META,
                    meta::BASE_BLOBS,
                    original.to_string(),
                ));
                original
            }
        };
        let collab = Collab {
            session,
            base_blobs,
            blob_keys: HashMap::new(),
            blobs_by_key: HashMap::new(),
            images_shared: doc.images.keys().cloned().collect(),
            synced: HashMap::new(),
            dirty: BTreeSet::new(),
            flags: HashMap::new(),
            pending: HashMap::new(),
            unlinked: HashSet::new(),
        };
        (collab, changes)
    }

    /// The guid session this peer creates nodes in.
    pub fn session(&self) -> u32 {
        self.session
    }

    /// Notes nodes a local step (an edit, undo, or redo) changed, so the
    /// next [`Collab::changes`] reports them. After undo and redo
    /// (`relink`), parents' children are derived again from the nodes'
    /// parent links, as the snapshots they restore predate other peers'
    /// changes; parents that changed are added to `touched`.
    pub fn record(&mut self, doc: &mut Document, touched: &mut Vec<NodeIdx>, relink: bool) {
        for &i in touched.iter() {
            let node = &mut doc.nodes[i as usize];
            let Some(g) = node.props.guid else { continue };
            let f = self.flags.entry(g).or_default();
            *f |= node.edits & !flags::CREATED;
            node.edits |= *f;
            self.dirty.insert(i);
        }
        if relink {
            let mut parents: HashSet<NodeIdx> = touched.iter().copied().collect();
            parents.extend(touched.iter().filter_map(|&i| doc.node(i).parent));
            for p in relink_children(doc, &parents, &HashMap::new()) {
                if !touched.contains(&p) {
                    touched.push(p);
                }
            }
            doc.refresh_pages();
        }
    }

    /// The entry changes that bring the shared maps up to date with this
    /// peer's edits since the last call.
    pub fn changes(&mut self, doc: &Document) -> Vec<EntryChange> {
        let mut nodes = Vec::new();
        let mut extra = Vec::new();
        let dirty = std::mem::take(&mut self.dirty);
        let Collab {
            base_blobs,
            blob_keys,
            blobs_by_key,
            images_shared,
            synced,
            flags: all_flags,
            ..
        } = self;
        for i in dirty {
            let node = doc.node(i);
            let Some(g) = node.props.guid else { continue };
            let known = synced.contains_key(&g);
            let created = node.edits & flags::CREATED != 0;
            // Never shared and back to how the file has it (or gone).
            if !known && (node.edits == 0 || created && node.removed) {
                continue;
            }
            let state = NodeState {
                props: node.props.clone(),
                removed: node.removed,
                listed: node
                    .parent
                    .is_some_and(|p| doc.node(p).children.contains(&i)),
                edits: node.edits | all_flags.get(&g).copied().unwrap_or(0),
                source: node.source,
            };
            let mut new_blobs: Vec<(Arc<str>, u32)> = Vec::new();
            let mut blob = |b: u32| -> BlobRef {
                if b < *base_blobs {
                    return BlobRef::Base(b);
                }
                let key = blob_keys
                    .entry(b)
                    .or_insert_with(|| blob_key(doc.blobs.bytes(b).unwrap_or_default()).into())
                    .clone();
                if !blobs_by_key.contains_key(&key) && !new_blobs.iter().any(|(k, _)| *k == key) {
                    new_blobs.push((key.clone(), b));
                }
                BlobRef::Shared(key)
            };
            let value = base64(&Writer::new(&mut blob).node(&state));
            let h = value_hash(&value);
            if synced.get(&g) == Some(&h) {
                continue;
            }
            synced.insert(g, h);
            for (key, b) in new_blobs {
                let bytes = doc.blobs.bytes(b).unwrap_or_default();
                extra.push(EntryChange::set(container::BLOBS, &*key, base64(bytes)));
                blobs_by_key.insert(key, b);
            }
            let mut hashes = Vec::new();
            codec::image_hashes(&node.props, &mut hashes);
            for hash in hashes {
                if !images_shared.insert(hash.to_string()) {
                    continue;
                }
                if let Some(bytes) = doc.images.get(&*hash)
                    && bytes.len() <= MAX_SHARED_IMAGE_BYTES
                {
                    extra.push(EntryChange::set(
                        container::IMAGES,
                        hash.to_string(),
                        base64(bytes),
                    ));
                }
            }
            nodes.push(EntryChange::set(container::NODES, g.to_string(), value));
        }
        extra.extend(nodes);
        extra
    }

    /// Applies entry changes made by other peers. Entries referencing blobs
    /// that have not arrived wait for them; nodes whose parent has not
    /// arrived stay detached until it does.
    pub fn apply(&mut self, doc: &mut Document, changes: &[EntryChange]) -> Remote {
        let mut remote = Remote::default();
        for c in changes {
            let Some(value) = &c.value else { continue };
            match c.container.as_str() {
                container::IMAGES => {
                    let hash = c.key.to_ascii_lowercase();
                    if !doc.images.contains_key(&hash)
                        && let Some(bytes) = unbase64(value)
                        && doc.add_image(&hash, bytes).is_some()
                    {
                        remote.images.push(hash.clone());
                    }
                    self.images_shared.insert(hash);
                }
                container::BLOBS => {
                    let key: Arc<str> = c.key.as_str().into();
                    if !self.blobs_by_key.contains_key(&key)
                        && let Some(bytes) = unbase64(value)
                    {
                        let at = doc.blobs.push(&bytes);
                        self.blobs_by_key.insert(key.clone(), at);
                        self.blob_keys.insert(at, key);
                    }
                }
                _ => {}
            }
        }

        // The latest value per node: waiting entries first, then these.
        let mut entries: Vec<(Guid, String)> = self.pending.drain().collect();
        for c in changes {
            if c.container != container::NODES {
                continue;
            }
            let (Some(g), Some(value)) = (Guid::parse(&c.key), &c.value) else {
                continue;
            };
            entries.retain(|(e, _)| *e != g);
            entries.push((g, value.clone()));
        }

        let mut states = Vec::new();
        {
            let original = doc.original_blobs as u32;
            let blobs_by_key = &self.blobs_by_key;
            let resolve = |r: &BlobRef| match r {
                BlobRef::Base(i) => (*i < original).then_some(*i),
                BlobRef::Shared(key) => blobs_by_key.get(key).copied(),
            };
            for (g, value) in entries {
                let h = value_hash(&value);
                if self.synced.get(&g) == Some(&h) {
                    continue;
                }
                let Some(bytes) = unbase64(&value) else {
                    continue;
                };
                match Reader::new(&bytes, &resolve).node() {
                    Ok(state) if state.props.guid == Some(g) => states.push((g, h, state)),
                    Err(DecodeError::Missing(_)) => {
                        self.pending.insert(g, value);
                    }
                    // Damaged, or written by a newer layout.
                    Ok(_) | Err(DecodeError::Invalid) => {}
                }
            }
        }

        let mut affected: HashSet<NodeIdx> = HashSet::new();
        let mut placed = Vec::new();
        let mut listed = HashMap::new();
        for (g, h, state) in states {
            let existing = doc.find(g);
            let i = match existing {
                Some(i) => i,
                None => {
                    let i = doc.nodes.len() as NodeIdx;
                    doc.nodes.push(Node {
                        props: Default::default(),
                        parent: None,
                        children: Vec::new(),
                        edits: flags::CREATED,
                        removed: true,
                        source: None,
                    });
                    doc.by_guid.insert(g, i);
                    i
                }
            };
            // Only nodes that changed place need their parents' children
            // derived again (most remote edits change properties alone).
            let old = doc.node(i);
            let moved = existing.is_none()
                || old.removed != state.removed
                || old.props.parent != state.props.parent
                || old.props.position != state.props.position
                || old
                    .parent
                    .is_some_and(|p| doc.node(p).children.contains(&i))
                    != state.listed;
            let f = self.flags.entry(g).or_default();
            *f |= state.edits & !flags::CREATED;
            let node = &mut doc.nodes[i as usize];
            // Whether the node is new to this peer's file decides how saving
            // writes it, whichever file the sender opened.
            let created = node.edits & flags::CREATED;
            if moved && let Some(p) = node.parent {
                affected.insert(p);
            }
            node.props = state.props;
            node.removed = state.removed;
            node.edits = ((node.edits | *f) & !flags::CREATED) | created;
            if created != 0 {
                node.source = state.source;
            }
            if let Some(key) = node.props.override_key {
                doc.by_override_key.insert(key, g);
            }
            self.synced.insert(g, h);
            if moved {
                listed.insert(i, state.listed);
                placed.push(i);
            }
            remote.touched.push(i);
        }
        // Earlier nodes whose parent may have arrived now.
        for g in self.unlinked.clone() {
            if let Some(i) = doc.find(g)
                && !placed.contains(&i)
            {
                placed.push(i);
            }
        }
        for i in placed {
            let parent_guid = doc.props(i).parent;
            let parent = parent_guid.and_then(|g| doc.find(g)).filter(|&p| p != i);
            if let Some(g) = doc.props(i).guid {
                if parent_guid.is_some() && parent.is_none() {
                    self.unlinked.insert(g);
                } else {
                    self.unlinked.remove(&g);
                }
            }
            doc.nodes[i as usize].parent = parent;
            if let Some(p) = parent {
                affected.insert(p);
            }
        }
        for p in relink_children(doc, &affected, &listed) {
            if !remote.touched.contains(&p) {
                remote.touched.push(p);
            }
        }
        doc.refresh_pages();
        remote
    }
}

/// Derives the children of `parents` from the nodes' parent links, ordered
/// by position (then id) as files order them: live nodes, and removed ones
/// that are listed (as `listed` says for nodes that just arrived, as the
/// current children say for the rest). Returns the parents whose children
/// changed.
fn relink_children(
    doc: &mut Document,
    parents: &HashSet<NodeIdx>,
    listed: &HashMap<NodeIdx, bool>,
) -> Vec<NodeIdx> {
    if parents.is_empty() {
        return Vec::new();
    }
    let mut lists: HashMap<NodeIdx, Vec<NodeIdx>> =
        parents.iter().map(|&p| (p, Vec::new())).collect();
    let current: HashMap<NodeIdx, HashSet<NodeIdx>> = parents
        .iter()
        .map(|&p| (p, doc.node(p).children.iter().copied().collect()))
        .collect();
    for (i, n) in doc.nodes.iter().enumerate() {
        let i = i as NodeIdx;
        let Some(p) = n.parent else { continue };
        let Some(list) = lists.get_mut(&p) else {
            continue;
        };
        let keep = !n.removed
            || listed
                .get(&i)
                .copied()
                .unwrap_or_else(|| current[&p].contains(&i));
        if keep {
            list.push(i);
        }
    }
    let mut changed = Vec::new();
    for (p, mut list) in lists {
        list.sort_by(|&a, &b| {
            let pa = &doc.nodes[a as usize].props;
            let pb = &doc.nodes[b as usize].props;
            pa.position
                .as_deref()
                .unwrap_or("")
                .cmp(pb.position.as_deref().unwrap_or(""))
                .then_with(|| pa.guid.cmp(&pb.guid))
        });
        let node = &mut doc.nodes[p as usize];
        if node.children != list {
            node.children = list;
            changed.push(p);
        }
    }
    changed.sort_unstable();
    changed
}

#[cfg(test)]
mod test;