loro_internal/state/
container_tree.rs

1//! Structured state traversal. Container identity comes from CRDT edges, never value shape.
2//! A sink constructs the target representation without a whole-document intermediate tree.
3use super::{deleted_root_container_value_is_cleared, visible_container_value_is_empty, DocState};
4use crate::{container::idx::ContainerIdx, ContainerType, LoroValue};
5use loro_common::{ContainerID, LoroError, LoroResult};
6use std::sync::atomic::Ordering;
7#[derive(Debug)]
8pub enum Event<'a> {
9    Object(usize),
10    Array(usize),
11    End,
12    Key(&'a str),
13    String(&'a str),
14    Number(f64),
15    Bool(bool),
16    Null,
17    Binary(&'a [u8]),
18}
19pub trait Sink {
20    fn emit(&mut self, e: Event<'_>) -> LoroResult<()>;
21    fn container(&mut self, id: &ContainerID) -> LoroResult<()>;
22    fn container_end(&mut self) -> LoroResult<()> {
23        self.emit(Event::End)
24    }
25    fn value_start(&mut self) -> LoroResult<()>;
26    fn value_end(&mut self) -> LoroResult<()>;
27}
28impl DocState {
29    pub fn read_container_tree<S: Sink>(
30        &mut self,
31        s: &mut S,
32        cid: Option<&ContainerID>,
33        rich: bool,
34        selected_roots: Option<&[String]>,
35    ) -> LoroResult<()> {
36        if let Some(id) = cid {
37            let idx = self.arena.register_container(id);
38            return self.read_container_node(s, idx, rich, None, None, 0);
39        }
40        let roots = self.preferred_root_containers();
41        let mut visible = Vec::new();
42        let selected: Option<std::collections::HashSet<&str>> =
43            selected_roots.map(|names| names.iter().map(String::as_str).collect());
44        for idx in roots {
45            if let Some(names) = &selected {
46                let name = self
47                    .root_container_name(idx)
48                    .ok_or_else(|| err("Missing root name"))?;
49                if !names.contains(name.as_str()) {
50                    continue;
51                }
52            }
53            if matches!(idx.get_type(), ContainerType::Unknown(_)) {
54                return Err(err("Unsupported container type"));
55            }
56            let id = self
57                .arena
58                .idx_to_id(idx)
59                .ok_or_else(|| err("Missing container ID"))?;
60            let hidden = self
61                .config
62                .hide_empty_root_containers
63                .load(Ordering::Relaxed);
64            let deleted = self.config.deleted_root_containers.lock().contains(&id);
65            let v = if hidden || deleted {
66                self.store
67                    .try_get_value_ephemeral(idx)?
68                    .or_else(|| Some(idx.get_type().default_value()))
69            } else {
70                None
71            };
72            if v.as_ref().is_some_and(|v| {
73                (hidden && visible_container_value_is_empty(idx.get_type(), v))
74                    || (deleted && deleted_root_container_value_is_cleared(idx.get_type(), v))
75            }) {
76                continue;
77            }
78            visible.push((
79                self.root_container_name(idx)
80                    .ok_or_else(|| err("Missing root name"))?,
81                idx,
82                v,
83            ));
84        }
85        s.emit(Event::Object(visible.len()))?;
86        for (key, idx, value) in visible {
87            s.emit(Event::Key(&key))?;
88            self.read_container_node(s, idx, rich, None, value, 0)?;
89        }
90        s.emit(Event::End)
91    }
92    /// Read a list window and its coordinates under the same state lock.
93    pub fn read_container_tree_slice<S: Sink>(
94        &mut self,
95        sink: &mut S,
96        cid: &ContainerID,
97        rich: bool,
98        start: usize,
99        end: usize,
100    ) -> LoroResult<(usize, usize)> {
101        let idx = self.arena.register_container(cid);
102        let kind = idx.get_type();
103        if !matches!(kind, ContainerType::List | ContainerType::MovableList) {
104            return Err(err("Expected list container"));
105        }
106        let value = self
107            .store
108            .try_get_value_ephemeral(idx)?
109            .unwrap_or_else(|| kind.default_value());
110        let total = value
111            .as_list()
112            .ok_or_else(|| err("Expected list value"))?
113            .len();
114        let start = start.min(total);
115        self.read_container_node(sink, idx, rich, Some((start, end)), Some(value), 0)?;
116        Ok((start, total))
117    }
118    fn read_container_node<S: Sink>(
119        &mut self,
120        s: &mut S,
121        idx: ContainerIdx,
122        rich: bool,
123        range: Option<(usize, usize)>,
124        value: Option<LoroValue>,
125        depth: usize,
126    ) -> LoroResult<()> {
127        check_depth(depth)?;
128        let id = self
129            .arena
130            .idx_to_id(idx)
131            .ok_or_else(|| err("Missing container ID"))?;
132        let kind = idx.get_type();
133        if matches!(kind, ContainerType::Unknown(_)) {
134            return Err(err("Unsupported container type"));
135        }
136        let v = if rich && kind == ContainerType::Text {
137            self.store
138                .get_or_create_mut(idx)
139                .as_richtext_state_mut()
140                .ok_or_else(|| err("Missing text state"))?
141                .get_richtext_value()
142        } else {
143            match value {
144                Some(value) => value,
145                None => self
146                    .store
147                    .try_get_value_ephemeral(idx)?
148                    .unwrap_or_else(|| kind.default_value()),
149            }
150        };
151        s.container(&id)?;
152
153        match (&v, kind) {
154            (LoroValue::Map(m), ContainerType::Map) => {
155                s.emit(Event::Object(m.len()))?;
156                for (k, v) in m.iter() {
157                    s.emit(Event::Key(k))?;
158                    let merge = loro_common::parse_mergeable_marker(&id, k, v)
159                        .map(|t| ContainerID::new_mergeable(&id, k, t));
160                    if let Some(c) = merge {
161                        let i = self.arena.register_container(&c);
162                        self.read_container_node(s, i, rich, None, None, depth + 1)?;
163                    } else {
164                        self.read_container_edge(s, v, rich, depth + 1)?;
165                    }
166                }
167                s.emit(Event::End)?;
168            }
169            (LoroValue::List(l), ContainerType::List | ContainerType::MovableList) => {
170                let (start, end) = range.unwrap_or((0, l.len()));
171                let start = start.min(l.len());
172                let end = end.min(l.len()).max(start);
173                s.emit(Event::Array(end - start))?;
174                for v in &l[start..end] {
175                    self.read_container_edge(s, v, rich, depth + 1)?;
176                }
177                s.emit(Event::End)?;
178            }
179            (_, ContainerType::Tree) => self.read_tree_nodes(s, &v, rich, depth + 1)?,
180            _ => raw(s, &v, depth + 1)?,
181        };
182        s.container_end()
183    }
184    fn read_container_edge<S: Sink>(
185        &mut self,
186        s: &mut S,
187        v: &LoroValue,
188        rich: bool,
189        depth: usize,
190    ) -> LoroResult<()> {
191        if let LoroValue::Container(cid) = v {
192            let idx = self.arena.register_container(cid);
193            return self.read_container_node(s, idx, rich, None, None, depth);
194        }
195        s.value_start()?;
196        raw(s, v, depth + 1)?;
197        s.value_end()
198    }
199    fn read_tree_nodes<S: Sink>(
200        &mut self,
201        s: &mut S,
202        v: &LoroValue,
203        rich: bool,
204        depth: usize,
205    ) -> LoroResult<()> {
206        check_depth(depth)?;
207        match v {
208            LoroValue::List(l) => {
209                s.emit(Event::Array(l.len()))?;
210                for node in l.iter() {
211                    let m = node.as_map().ok_or_else(|| err("Invalid tree node"))?;
212                    s.emit(Event::Object(m.len()))?;
213                    for (k, v) in m.iter() {
214                        s.emit(Event::Key(k))?;
215                        if k == "meta" {
216                            self.read_container_edge(s, v, rich, depth + 1)?;
217                        } else if k == "children" {
218                            self.read_tree_nodes(s, v, rich, depth + 1)?;
219                        } else {
220                            raw(s, v, depth + 1)?;
221                        }
222                    }
223                    s.emit(Event::End)?;
224                }
225                s.emit(Event::End)
226            }
227            _ => Err(err("Invalid tree value")),
228        }
229    }
230}
231pub fn err(s: &str) -> LoroError {
232    LoroError::JsError(s.to_string().into_boxed_str())
233}
234fn raw<S: Sink>(s: &mut S, v: &LoroValue, depth: usize) -> LoroResult<()> {
235    check_depth(depth)?;
236    match v {
237        LoroValue::Null => s.emit(Event::Null),
238        LoroValue::Bool(b) => s.emit(Event::Bool(*b)),
239        // Match the existing JavaScript value conversion, including i64 -> number.
240        LoroValue::I64(n) => s.emit(Event::Number(*n as f64)),
241        LoroValue::Double(n) => s.emit(Event::Number(*n)),
242        LoroValue::Binary(v) => s.emit(Event::Binary(v)),
243        LoroValue::Container(id) => s.emit(Event::String(&id.to_string())),
244        LoroValue::String(v) => s.emit(Event::String(v)),
245        LoroValue::List(l) => {
246            s.emit(Event::Array(l.len()))?;
247            for v in l.iter() {
248                raw(s, v, depth + 1)?;
249            }
250            s.emit(Event::End)
251        }
252        LoroValue::Map(m) => {
253            s.emit(Event::Object(m.len()))?;
254            for (k, v) in m.iter() {
255                s.emit(Event::Key(k))?;
256                raw(s, v, depth + 1)?;
257            }
258            s.emit(Event::End)
259        }
260    }
261}
262
263fn check_depth(depth: usize) -> LoroResult<()> {
264    if depth > 256 {
265        Err(err("toContainerTree nesting exceeds 256 levels"))
266    } else {
267        Ok(())
268    }
269}
loro_internal/state/container_tree.rs

loro_internal/state/
container_tree.rs
