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