crates/oxy-core/src/state.rs at 5b1114a04905 · andymccall/oxygen

# 5b1114a04905 oxygen / crates / oxy-core / src / state.rs

14.4 KiB · Rust · last changed Import the Oxygen specification and the first Rust implementation (root change) 1 month ago source blame history raw

//! A state: a dependency-closed set of changes, applied to a tree graph and
//! per-node file graphs (spec §8.3), with materialization (spec §9.5, §11).

use crate::graph::{AtomKey, DepOracle, FileGraph, Materialized, Vertex};
use crate::hash::{ChangeHash, ObjectRef};
use crate::ids::NodeId;
use crate::objects::{AtomRef, Change, Edit, Mode, NodeKind, TreeOp};
use crate::tree::{TreeGraph, TreeView};
use std::cell::RefCell;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::rc::Rc;

#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum StateError {
    #[error("change {1} depends on {0}, which is not in the state")]
    MissingDep(ChangeHash, ChangeHash),
}

/// One `Replace` edit: `(change, old blob, new blob)`.
type ReplaceRecord = (ChangeHash, Option<ObjectRef>, Option<ObjectRef>);

#[derive(Default)]
pub struct State {
    changes: HashMap<ChangeHash, Change>,
    tree: TreeGraph,
    files: HashMap<NodeId, FileGraph>,
    replaces: HashMap<NodeId, Vec<ReplaceRecord>>,
    closure: RefCell<HashMap<ChangeHash, Rc<HashSet<ChangeHash>>>>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum FileContent {
    Text { bytes: Vec<u8>, materialized: Materialized },
    /// Live blobs; more than one is a replace conflict (spec §9.3).
    Opaque { blobs: Vec<ObjectRef> },
    Dir,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct FileState {
    pub node: NodeId,
    pub kind: NodeKind,
    pub mode: Mode,
    pub content: FileContent,
}

impl FileState {
    pub fn is_conflicted(&self) -> bool {
        match &self.content {
            FileContent::Text { materialized, .. } => materialized.is_conflicted(),
            FileContent::Opaque { blobs } => blobs.len() > 1,
            FileContent::Dir => false,
        }
    }
}

/// The whole tree of a state, materialized.
#[derive(Clone, Debug, Default)]
pub struct Snapshot {
    pub tree: TreeView,
    pub files: BTreeMap<String, FileState>,
}

impl Snapshot {
    pub fn is_conflicted(&self) -> bool {
        self.tree.is_conflicted() || self.files.values().any(|f| f.is_conflicted())
    }
}

fn vertex(r: AtomRef) -> Vertex {
    match r {
        AtomRef::Start => Vertex::Start,
        AtomRef::End => Vertex::End,
        AtomRef::Atom { change, index } => Vertex::Atom((change, index)),
    }
}

/// Replace self references in a tree op with the concrete change hash.
pub fn resolve_tree_op(op: &TreeOp, me: ChangeHash) -> TreeOp {
    match op {
        TreeOp::RemoveNode { node, placement } => TreeOp::RemoveNode { node: *node, placement: placement.resolve(me) },
        TreeOp::Move { node, old, parent, name } => {
            TreeOp::Move { node: *node, old: old.resolve(me), parent: *parent, name: name.clone() }
        }
        TreeOp::SetMode { node, old, mode } => TreeOp::SetMode { node: *node, old: old.resolve(me), mode: *mode },
        add @ TreeOp::AddNode { .. } => add.clone(),
    }
}

impl State {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn len(&self) -> usize {
        self.changes.len()
    }
    pub fn is_empty(&self) -> bool {
        self.changes.is_empty()
    }
    pub fn contains(&self, h: &ChangeHash) -> bool {
        self.changes.contains_key(h)
    }
    pub fn get(&self, h: &ChangeHash) -> Option<&Change> {
        self.changes.get(h)
    }
    pub fn changes(&self) -> impl Iterator<Item = (&ChangeHash, &Change)> {
        self.changes.iter()
    }
    pub fn tree(&self) -> &TreeGraph {
        &self.tree
    }
    pub fn file(&self, node: &NodeId) -> Option<&FileGraph> {
        self.files.get(node)
    }

    /// Add a change whose dependencies are already present.
    pub fn add(&mut self, change: Change) -> Result<ChangeHash, StateError> {
        let h = change.hash();
        if self.changes.contains_key(&h) {
            return Ok(h);
        }
        for d in &change.deps {
            if !self.changes.contains_key(d) {
                return Err(StateError::MissingDep(*d, h));
            }
        }
        Ok(self.add_unchecked(change))
    }

    /// Add a change in any order; call `validate` once all are in.
    pub fn add_unchecked(&mut self, change: Change) -> ChangeHash {
        let h = change.hash();
        if self.changes.contains_key(&h) {
            return h;
        }
        self.apply(h, &change);
        self.changes.insert(h, change);
        self.closure.borrow_mut().clear();
        h
    }

    pub fn validate(&self) -> Result<(), StateError> {
        for (h, c) in &self.changes {
            for d in &c.deps {
                if !self.changes.contains_key(d) {
                    return Err(StateError::MissingDep(*d, *h));
                }
            }
        }
        Ok(())
    }

    fn apply(&mut self, h: ChangeHash, c: &Change) {
        for (i, op) in c.tree_ops.iter().enumerate() {
            self.tree.apply(h, i as u32, &resolve_tree_op(op, h));
        }
        let mut counters: HashMap<NodeId, u32> = HashMap::new();
        for e in &c.edits {
            match e {
                Edit::Insert { node, after, before, lines } => {
                    let idx = counters.entry(*node).or_default();
                    let first = *idx;
                    *idx += lines.len() as u32;
                    self.files.entry(*node).or_default().insert(h, first, vertex(after.resolve(h)), vertex(before.resolve(h)), lines);
                }
                Edit::Delete { node, atoms } => {
                    let g = self.files.entry(*node).or_default();
                    for r in atoms {
                        g.delete(h, &r.resolve(h));
                    }
                }
                Edit::Replace { node, old, new } => {
                    self.replaces.entry(*node).or_default().push((h, *old, *new));
                }
            }
        }
    }

    /// Transitive dependencies of `h`, excluding `h` itself.
    pub fn closure(&self, h: &ChangeHash) -> Rc<HashSet<ChangeHash>> {
        if let Some(c) = self.closure.borrow().get(h) {
            return c.clone();
        }
        let mut out = HashSet::new();
        let mut stack: Vec<ChangeHash> = self.changes.get(h).map(|c| c.deps.clone()).unwrap_or_default();
        while let Some(d) = stack.pop() {
            if out.insert(d) {
                if let Some(c) = self.changes.get(&d) {
                    stack.extend(c.deps.iter().copied());
                }
            }
        }
        let rc = Rc::new(out);
        self.closure.borrow_mut().insert(*h, rc.clone());
        rc
    }

    /// Changes that no other change depends on directly, sorted.
    pub fn heads(&self) -> Vec<ChangeHash> {
        let depended: HashSet<&ChangeHash> = self.changes.values().flat_map(|c| c.deps.iter()).collect();
        let mut heads: Vec<ChangeHash> = self.changes.keys().filter(|h| !depended.contains(h)).copied().collect();
        heads.sort();
        heads
    }

    /// Maximal elements among `hashes` (those not in the closure of another).
    pub fn maximal(&self, hashes: &[ChangeHash]) -> Vec<ChangeHash> {
        let set: BTreeSet<ChangeHash> = hashes.iter().copied().collect();
        set.iter().filter(|h| !set.iter().any(|o| o != *h && self.closure(o).contains(h))).copied().collect()
    }

    pub fn materialize_file(&self, node: &NodeId) -> Materialized {
        self.files.get(node).map(|g| g.materialize(self)).unwrap_or_default()
    }

    /// Live lines of a text node in materialized order.
    pub fn live_lines(&self, node: &NodeId) -> Vec<(AtomKey, Vec<u8>)> {
        let Some(g) = self.files.get(node) else { return vec![] };
        let m = g.materialize(self);
        m.live_atoms().into_iter().map(|a| (a, g.content(&a).unwrap_or_default().to_vec())).collect()
    }

    /// Live blobs of an opaque node: every `new` that no later `Replace` retired.
    pub fn live_blobs(&self, node: &NodeId) -> Vec<ObjectRef> {
        let Some(rs) = self.replaces.get(node) else { return vec![] };
        let olds: HashSet<ObjectRef> = rs.iter().filter_map(|(_, o, _)| *o).collect();
        let mut live: Vec<ObjectRef> = rs.iter().filter_map(|(_, _, n)| *n).filter(|n| !olds.contains(n)).collect();
        live.sort();
        live.dedup();
        live
    }

    /// Short label for conflict markers: `changeid-prefix "message"`.
    pub fn label(&self, h: &ChangeHash) -> String {
        match self.changes.get(h) {
            Some(c) => format!("{} \"{}\"", c.change_id.short(8), c.message.lines().next().unwrap_or("")),
            None => format!("#{}", h.short(12)),
        }
    }

    pub fn render_file(&self, node: &NodeId) -> (Vec<u8>, Materialized) {
        let Some(g) = self.files.get(node) else { return (Vec::new(), Materialized::default()) };
        let m = g.materialize(self);
        let bytes = g.render(&m, &|h| self.label(h));
        (bytes, m)
    }

    pub fn materialize(&self) -> Snapshot {
        let tree = self.tree.view();
        let mut files = BTreeMap::new();
        for (path, e) in &tree.entries {
            let content = match e.kind {
                NodeKind::Dir => FileContent::Dir,
                NodeKind::Symlink => FileContent::Opaque { blobs: self.live_blobs(&e.node) },
                NodeKind::File if e.mode.opaque => FileContent::Opaque { blobs: self.live_blobs(&e.node) },
                NodeKind::File => {
                    let (bytes, materialized) = self.render_file(&e.node);
                    FileContent::Text { bytes, materialized }
                }
            };
            files.insert(path.clone(), FileState { node: e.node, kind: e.kind, mode: e.mode, content });
        }
        Snapshot { tree, files }
    }
}

impl DepOracle for State {
    fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
        a == b || self.closure(a).contains(b)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::ids::ChangeId;
    use crate::objects::{AtomRange, ChangeKind, Hlc, OpRef};

    fn change(deps: Vec<ChangeHash>, tree_ops: Vec<TreeOp>, edits: Vec<Edit>) -> Change {
        let mut c = Change {
            change_id: ChangeId::random(),
            deps,
            author: ObjectRef::ZERO,
            hlc: Hlc { wall_ms: 1, logical: 0 },
            message: "m".into(),
            tree_ops,
            edits,
            kind: ChangeKind::Normal,
        };
        c.normalize();
        c
    }

    #[test]
    fn build_edit_and_materialize() {
        let mut st = State::new();
        let f = NodeId::random();
        let c1 = change(
            vec![],
            vec![TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "a.txt".into() }],
            vec![Edit::Insert { node: f, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"one\n".to_vec(), b"two\n".to_vec()] }],
        );
        let h1 = st.add(c1).unwrap();
        // Depends on h1: append a line and delete "one".
        let c2 = change(
            vec![h1],
            vec![],
            vec![
                Edit::Delete { node: f, atoms: vec![AtomRange { change: h1, from: 0, to: 1 }] },
                Edit::Insert { node: f, after: AtomRef::Atom { change: h1, index: 1 }, before: AtomRef::End, lines: vec![b"three\n".to_vec()] },
            ],
        );
        let h2 = st.add(c2).unwrap();
        assert_eq!(st.heads(), vec![h2]);
        assert!(st.depends_on(&h2, &h1));
        assert!(!st.depends_on(&h1, &h2));
        let snap = st.materialize();
        assert!(!snap.is_conflicted());
        let a = &snap.files["a.txt"];
        assert!(matches!(&a.content, FileContent::Text { bytes, .. } if bytes == b"two\nthree\n"));
        assert_eq!(st.live_lines(&f).len(), 2);
    }

    #[test]
    fn missing_dependency_is_rejected() {
        let mut st = State::new();
        let c = change(vec![ObjectRef([1; 32])], vec![], vec![]);
        assert!(matches!(st.add(c), Err(StateError::MissingDep(..))));
    }

    #[test]
    fn self_references_and_multi_insert_indexing() {
        let mut st = State::new();
        let f = NodeId::random();
        let me = OpRef { change: ObjectRef::ZERO, index: 0 };
        let c1 = change(
            vec![],
            vec![
                TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "x".into() },
                TreeOp::SetMode { node: f, old: me, mode: Mode { exec: true, opaque: false } },
            ],
            vec![
                Edit::Insert { node: f, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"a\n".to_vec(), b"c\n".to_vec()] },
                // Insert between the two lines just inserted, using self references.
                Edit::Insert {
                    node: f,
                    after: AtomRef::Atom { change: ObjectRef::ZERO, index: 0 },
                    before: AtomRef::Atom { change: ObjectRef::ZERO, index: 1 },
                    lines: vec![b"b\n".to_vec()],
                },
            ],
        );
        st.add(c1).unwrap();
        let snap = st.materialize();
        let x = &snap.files["x"];
        assert_eq!(x.mode, Mode { exec: true, opaque: false });
        assert!(matches!(&x.content, FileContent::Text { bytes, .. } if bytes == b"a\nb\nc\n"));
    }

    #[test]
    fn opaque_replace_and_conflict() {
        let mut st = State::new();
        let f = NodeId::random();
        let b1 = ObjectRef([1; 32]);
        let b2 = ObjectRef([2; 32]);
        let b3 = ObjectRef([3; 32]);
        let h1 = st.add(change(
            vec![],
            vec![TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::OPAQUE, parent: NodeId::ROOT, name: "img".into() }],
            vec![Edit::Replace { node: f, old: None, new: Some(b1) }],
        ))
        .unwrap();
        assert_eq!(st.live_blobs(&f), vec![b1]);
        st.add(change(vec![h1], vec![], vec![Edit::Replace { node: f, old: Some(b1), new: Some(b2) }])).unwrap();
        st.add(change(vec![h1], vec![], vec![Edit::Replace { node: f, old: Some(b1), new: Some(b3) }])).unwrap();
        let snap = st.materialize();
        assert!(snap.is_conflicted());
        assert!(matches!(&snap.files["img"].content, FileContent::Opaque { blobs } if blobs == &vec![b2, b3]));
    }

    #[test]
    fn maximal_elements() {
        let mut st = State::new();
        let h1 = st.add(change(vec![], vec![], vec![])).unwrap();
        let h2 = st.add(change(vec![h1], vec![], vec![])).unwrap();
        let h3 = st.add(change(vec![], vec![], vec![])).unwrap();
        let mut m = st.maximal(&[h1, h2, h3]);
        m.sort();
        let mut want = vec![h2, h3];
        want.sort();
        assert_eq!(m, want);
        assert_eq!(st.heads(), want);
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

ff0af1ee unknown 1 month ago	1	//! A state: a dependency-closed set of changes, applied to a tree graph and
	2	//! per-node file graphs (spec §8.3), with materialization (spec §9.5, §11).
	3
	4	use crate::graph::{AtomKey, DepOracle, FileGraph, Materialized, Vertex};
	5	use crate::hash::{ChangeHash, ObjectRef};
	6	use crate::ids::NodeId;
	7	use crate::objects::{AtomRef, Change, Edit, Mode, NodeKind, TreeOp};
	8	use crate::tree::{TreeGraph, TreeView};
	9	use std::cell::RefCell;
	10	use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
	11	use std::rc::Rc;
	12
	13	#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
	14	pub enum StateError {
	15	#[error("change {1} depends on {0}, which is not in the state")]
	16	MissingDep(ChangeHash, ChangeHash),
	17	}
	18
55e5a16a unknown 1 month ago ↶	19	/// One `Replace` edit: `(change, old blob, new blob)`.
	20	type ReplaceRecord = (ChangeHash, Option<ObjectRef>, Option<ObjectRef>);
	21
ff0af1ee unknown 1 month ago	22	#[derive(Default)]
	23	pub struct State {
	24	changes: HashMap<ChangeHash, Change>,
	25	tree: TreeGraph,
	26	files: HashMap<NodeId, FileGraph>,
55e5a16a unknown 1 month ago ↶	27	replaces: HashMap<NodeId, Vec<ReplaceRecord>>,
ff0af1ee unknown 1 month ago	28	closure: RefCell<HashMap<ChangeHash, Rc<HashSet<ChangeHash>>>>,
	29	}
	30
	31	#[derive(Clone, Debug, PartialEq, Eq)]
	32	pub enum FileContent {
	33	Text { bytes: Vec<u8>, materialized: Materialized },
	34	/// Live blobs; more than one is a replace conflict (spec §9.3).
	35	Opaque { blobs: Vec<ObjectRef> },
	36	Dir,
	37	}
	38
	39	#[derive(Clone, Debug, PartialEq, Eq)]
	40	pub struct FileState {
	41	pub node: NodeId,
	42	pub kind: NodeKind,
	43	pub mode: Mode,
	44	pub content: FileContent,
	45	}
	46
	47	impl FileState {
	48	pub fn is_conflicted(&self) -> bool {
	49	match &self.content {
	50	FileContent::Text { materialized, .. } => materialized.is_conflicted(),
	51	FileContent::Opaque { blobs } => blobs.len() > 1,
	52	FileContent::Dir => false,
	53	}
	54	}
	55	}
	56
	57	/// The whole tree of a state, materialized.
	58	#[derive(Clone, Debug, Default)]
	59	pub struct Snapshot {
	60	pub tree: TreeView,
	61	pub files: BTreeMap<String, FileState>,
	62	}
	63
	64	impl Snapshot {
	65	pub fn is_conflicted(&self) -> bool {
	66	self.tree.is_conflicted() \|\| self.files.values().any(\|f\| f.is_conflicted())
	67	}
	68	}
	69
	70	fn vertex(r: AtomRef) -> Vertex {
	71	match r {
	72	AtomRef::Start => Vertex::Start,
	73	AtomRef::End => Vertex::End,
	74	AtomRef::Atom { change, index } => Vertex::Atom((change, index)),
	75	}
	76	}
	77
	78	/// Replace self references in a tree op with the concrete change hash.
	79	pub fn resolve_tree_op(op: &TreeOp, me: ChangeHash) -> TreeOp {
	80	match op {
	81	TreeOp::RemoveNode { node, placement } => TreeOp::RemoveNode { node: *node, placement: placement.resolve(me) },
	82	TreeOp::Move { node, old, parent, name } => {
	83	TreeOp::Move { node: node, old: old.resolve(me), parent: parent, name: name.clone() }
	84	}
	85	TreeOp::SetMode { node, old, mode } => TreeOp::SetMode { node: node, old: old.resolve(me), mode: mode },
	86	add @ TreeOp::AddNode { .. } => add.clone(),
	87	}
	88	}
	89
	90	impl State {
	91	pub fn new() -> Self {
92	Self::default()
93	}
94
95	pub fn len(&self) -> usize {
96	self.changes.len()
97	}
98	pub fn is_empty(&self) -> bool {
99	self.changes.is_empty()
100	}
101	pub fn contains(&self, h: &ChangeHash) -> bool {
102	self.changes.contains_key(h)
103	}
104	pub fn get(&self, h: &ChangeHash) -> Option<&Change> {
105	self.changes.get(h)
106	}
107	pub fn changes(&self) -> impl Iterator<Item = (&ChangeHash, &Change)> {
108	self.changes.iter()
109	}
110	pub fn tree(&self) -> &TreeGraph {
111	&self.tree
112	}
113	pub fn file(&self, node: &NodeId) -> Option<&FileGraph> {
114	self.files.get(node)
115	}
116
117	/// Add a change whose dependencies are already present.
118	pub fn add(&mut self, change: Change) -> Result<ChangeHash, StateError> {
119	let h = change.hash();
120	if self.changes.contains_key(&h) {
121	return Ok(h);
122	}
123	for d in &change.deps {
124	if !self.changes.contains_key(d) {
125	return Err(StateError::MissingDep(*d, h));
126	}
127	}
128	Ok(self.add_unchecked(change))
129	}
130
131	/// Add a change in any order; call `validate` once all are in.
132	pub fn add_unchecked(&mut self, change: Change) -> ChangeHash {
133	let h = change.hash();
134	if self.changes.contains_key(&h) {
135	return h;
136	}
137	self.apply(h, &change);
138	self.changes.insert(h, change);
139	self.closure.borrow_mut().clear();
140	h
141	}
142
143	pub fn validate(&self) -> Result<(), StateError> {
144	for (h, c) in &self.changes {
145	for d in &c.deps {
146	if !self.changes.contains_key(d) {
147	return Err(StateError::MissingDep(d, h));
148	}
149	}
150	}
151	Ok(())
152	}
153
154	fn apply(&mut self, h: ChangeHash, c: &Change) {
155	for (i, op) in c.tree_ops.iter().enumerate() {
156	self.tree.apply(h, i as u32, &resolve_tree_op(op, h));
157	}
158	let mut counters: HashMap<NodeId, u32> = HashMap::new();
159	for e in &c.edits {
160	match e {
161	Edit::Insert { node, after, before, lines } => {
162	let idx = counters.entry(*node).or_default();
163	let first = *idx;
164	*idx += lines.len() as u32;
165	self.files.entry(*node).or_default().insert(h, first, vertex(after.resolve(h)), vertex(before.resolve(h)), lines);
166	}
167	Edit::Delete { node, atoms } => {
168	let g = self.files.entry(*node).or_default();
169	for r in atoms {
170	g.delete(h, &r.resolve(h));
171	}
172	}
173	Edit::Replace { node, old, new } => {
174	self.replaces.entry(node).or_default().push((h, old, *new));
175	}
176	}
177	}
178	}
179
180	/// Transitive dependencies of `h`, excluding `h` itself.
181	pub fn closure(&self, h: &ChangeHash) -> Rc<HashSet<ChangeHash>> {
182	if let Some(c) = self.closure.borrow().get(h) {
183	return c.clone();
184	}
185	let mut out = HashSet::new();
186	let mut stack: Vec<ChangeHash> = self.changes.get(h).map(\|c\| c.deps.clone()).unwrap_or_default();
187	while let Some(d) = stack.pop() {
188	if out.insert(d) {
189	if let Some(c) = self.changes.get(&d) {
190	stack.extend(c.deps.iter().copied());
191	}
192	}
193	}
194	let rc = Rc::new(out);
195	self.closure.borrow_mut().insert(*h, rc.clone());
196	rc
197	}
198
199	/// Changes that no other change depends on directly, sorted.
200	pub fn heads(&self) -> Vec<ChangeHash> {
201	let depended: HashSet<&ChangeHash> = self.changes.values().flat_map(\|c\| c.deps.iter()).collect();
202	let mut heads: Vec<ChangeHash> = self.changes.keys().filter(\|h\| !depended.contains(h)).copied().collect();
203	heads.sort();
204	heads
205	}
206
207	/// Maximal elements among `hashes` (those not in the closure of another).
208	pub fn maximal(&self, hashes: &[ChangeHash]) -> Vec<ChangeHash> {
209	let set: BTreeSet<ChangeHash> = hashes.iter().copied().collect();
210	set.iter().filter(\|h\| !set.iter().any(\|o\| o != *h && self.closure(o).contains(h))).copied().collect()
211	}
212
213	pub fn materialize_file(&self, node: &NodeId) -> Materialized {
214	self.files.get(node).map(\|g\| g.materialize(self)).unwrap_or_default()
215	}
216
217	/// Live lines of a text node in materialized order.
218	pub fn live_lines(&self, node: &NodeId) -> Vec<(AtomKey, Vec<u8>)> {
219	let Some(g) = self.files.get(node) else { return vec![] };
220	let m = g.materialize(self);
221	m.live_atoms().into_iter().map(\|a\| (a, g.content(&a).unwrap_or_default().to_vec())).collect()
222	}
223
224	/// Live blobs of an opaque node: every `new` that no later `Replace` retired.
225	pub fn live_blobs(&self, node: &NodeId) -> Vec<ObjectRef> {
226	let Some(rs) = self.replaces.get(node) else { return vec![] };
227	let olds: HashSet<ObjectRef> = rs.iter().filter_map(\|(_, o, _)\| *o).collect();
228	let mut live: Vec<ObjectRef> = rs.iter().filter_map(\|(_, _, n)\| *n).filter(\|n\| !olds.contains(n)).collect();
229	live.sort();
230	live.dedup();
231	live
232	}
233
234	/// Short label for conflict markers: `changeid-prefix "message"`.
235	pub fn label(&self, h: &ChangeHash) -> String {
236	match self.changes.get(h) {
237	Some(c) => format!("{} \"{}\"", c.change_id.short(8), c.message.lines().next().unwrap_or("")),
238	None => format!("#{}", h.short(12)),
239	}
240	}
241
242	pub fn render_file(&self, node: &NodeId) -> (Vec<u8>, Materialized) {
243	let Some(g) = self.files.get(node) else { return (Vec::new(), Materialized::default()) };
244	let m = g.materialize(self);
245	let bytes = g.render(&m, &\|h\| self.label(h));
246	(bytes, m)
247	}
248
249	pub fn materialize(&self) -> Snapshot {
250	let tree = self.tree.view();
251	let mut files = BTreeMap::new();
252	for (path, e) in &tree.entries {
253	let content = match e.kind {
254	NodeKind::Dir => FileContent::Dir,
255	NodeKind::Symlink => FileContent::Opaque { blobs: self.live_blobs(&e.node) },
256	NodeKind::File if e.mode.opaque => FileContent::Opaque { blobs: self.live_blobs(&e.node) },
257	NodeKind::File => {
258	let (bytes, materialized) = self.render_file(&e.node);
259	FileContent::Text { bytes, materialized }
260	}
261	};
262	files.insert(path.clone(), FileState { node: e.node, kind: e.kind, mode: e.mode, content });
263	}
264	Snapshot { tree, files }
265	}
266	}
267
268	impl DepOracle for State {
269	fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
270	a == b \|\| self.closure(a).contains(b)
271	}
272	}
273
274	#[cfg(test)]
275	mod tests {
276	use super::*;
277	use crate::ids::ChangeId;
278	use crate::objects::{AtomRange, ChangeKind, Hlc, OpRef};
279
280	fn change(deps: Vec<ChangeHash>, tree_ops: Vec<TreeOp>, edits: Vec<Edit>) -> Change {
281	let mut c = Change {
282	change_id: ChangeId::random(),
283	deps,
284	author: ObjectRef::ZERO,
285	hlc: Hlc { wall_ms: 1, logical: 0 },
286	message: "m".into(),
287	tree_ops,
288	edits,
289	kind: ChangeKind::Normal,
290	};
291	c.normalize();
292	c
293	}
294
295	#[test]
296	fn build_edit_and_materialize() {
297	let mut st = State::new();
298	let f = NodeId::random();
299	let c1 = change(
300	vec![],
301	vec![TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "a.txt".into() }],
302	vec![Edit::Insert { node: f, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"one\n".to_vec(), b"two\n".to_vec()] }],
303	);
304	let h1 = st.add(c1).unwrap();
305	// Depends on h1: append a line and delete "one".
306	let c2 = change(
307	vec![h1],
308	vec![],
309	vec![
310	Edit::Delete { node: f, atoms: vec![AtomRange { change: h1, from: 0, to: 1 }] },
311	Edit::Insert { node: f, after: AtomRef::Atom { change: h1, index: 1 }, before: AtomRef::End, lines: vec![b"three\n".to_vec()] },
312	],
313	);
314	let h2 = st.add(c2).unwrap();
315	assert_eq!(st.heads(), vec![h2]);
316	assert!(st.depends_on(&h2, &h1));
317	assert!(!st.depends_on(&h1, &h2));
318	let snap = st.materialize();
319	assert!(!snap.is_conflicted());
320	let a = &snap.files["a.txt"];
321	assert!(matches!(&a.content, FileContent::Text { bytes, .. } if bytes == b"two\nthree\n"));
322	assert_eq!(st.live_lines(&f).len(), 2);
323	}
324
325	#[test]
326	fn missing_dependency_is_rejected() {
327	let mut st = State::new();
328	let c = change(vec![ObjectRef([1; 32])], vec![], vec![]);
329	assert!(matches!(st.add(c), Err(StateError::MissingDep(..))));
330	}
331
332	#[test]
333	fn self_references_and_multi_insert_indexing() {
334	let mut st = State::new();
335	let f = NodeId::random();
336	let me = OpRef { change: ObjectRef::ZERO, index: 0 };
337	let c1 = change(
338	vec![],
339	vec![
340	TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "x".into() },
341	TreeOp::SetMode { node: f, old: me, mode: Mode { exec: true, opaque: false } },
342	],
343	vec![
344	Edit::Insert { node: f, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"a\n".to_vec(), b"c\n".to_vec()] },
345	// Insert between the two lines just inserted, using self references.
346	Edit::Insert {
347	node: f,
348	after: AtomRef::Atom { change: ObjectRef::ZERO, index: 0 },
349	before: AtomRef::Atom { change: ObjectRef::ZERO, index: 1 },
350	lines: vec![b"b\n".to_vec()],
351	},
352	],
353	);
354	st.add(c1).unwrap();
355	let snap = st.materialize();
356	let x = &snap.files["x"];
357	assert_eq!(x.mode, Mode { exec: true, opaque: false });
358	assert!(matches!(&x.content, FileContent::Text { bytes, .. } if bytes == b"a\nb\nc\n"));
359	}
360
361	#[test]
362	fn opaque_replace_and_conflict() {
363	let mut st = State::new();
364	let f = NodeId::random();
365	let b1 = ObjectRef([1; 32]);
366	let b2 = ObjectRef([2; 32]);
367	let b3 = ObjectRef([3; 32]);
368	let h1 = st.add(change(
369	vec![],
370	vec![TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::OPAQUE, parent: NodeId::ROOT, name: "img".into() }],
371	vec![Edit::Replace { node: f, old: None, new: Some(b1) }],
372	))
373	.unwrap();
374	assert_eq!(st.live_blobs(&f), vec![b1]);
375	st.add(change(vec![h1], vec![], vec![Edit::Replace { node: f, old: Some(b1), new: Some(b2) }])).unwrap();
376	st.add(change(vec![h1], vec![], vec![Edit::Replace { node: f, old: Some(b1), new: Some(b3) }])).unwrap();
377	let snap = st.materialize();
378	assert!(snap.is_conflicted());
379	assert!(matches!(&snap.files["img"].content, FileContent::Opaque { blobs } if blobs == &vec![b2, b3]));
380	}
381
382	#[test]
383	fn maximal_elements() {
384	let mut st = State::new();
385	let h1 = st.add(change(vec![], vec![], vec![])).unwrap();
386	let h2 = st.add(change(vec![h1], vec![], vec![])).unwrap();
387	let h3 = st.add(change(vec![], vec![], vec![])).unwrap();
388	let mut m = st.maximal(&[h1, h2, h3]);
389	m.sort();
390	let mut want = vec![h2, h3];
391	want.sort();
392	assert_eq!(m, want);
393	assert_eq!(st.heads(), want);
394	}
395	}

Keyboard