y_octo/doc/
history.rs

1use std::{collections::VecDeque, sync::Arc};
2
3use serde::{Deserialize, Serialize};
4
5use super::{store::StoreRef, *};
6use crate::sync::RwLock;
7
8enum ParentNode {
9    Root(String),
10    Node(Somr<Item>),
11    Unknown,
12}
13
14#[derive(Clone, Default)]
15pub struct HistoryOptions {
16    pub client: Option<u64>,
17    /// Only available when client is set
18    pub skip: Option<usize>,
19    /// Only available when client is set
20    pub limit: Option<usize>,
21}
22
23#[derive(Debug, Clone, Default)]
24pub struct StoreHistory {
25    store: StoreRef,
26    parents: Arc<RwLock<HashMap<Id, Somr<Item>>>>,
27}
28
29impl StoreHistory {
30    pub(crate) fn new(store: &StoreRef) -> Self {
31        Self {
32            store: store.clone(),
33            ..Default::default()
34        }
35    }
36
37    pub fn resolve(&self) {
38        let store = self.store.read().unwrap();
39        self.resolve_with_store(&store);
40    }
41
42    pub(crate) fn resolve_with_store(&self, store: &DocStore) {
43        let mut parents = self.parents.write().unwrap();
44
45        for node in store.items.values().flat_map(|items| items.iter()) {
46            let node = node.as_item();
47            if let Some(item) = node.get() {
48                parents
49                    .entry(item.id)
50                    .and_modify(|e| {
51                        if *e != node {
52                            *e = node.clone();
53                        }
54                    })
55                    .or_insert(node.clone());
56            }
57        }
58    }
59
60    pub fn parse_update(&self, update: &Update) -> Vec<History> {
61        let store_items = SortedNodes::new(update.structs.iter().collect::<Vec<_>>())
62            .filter_map(|n| n.as_item().get().cloned())
63            .collect::<Vec<_>>();
64
65        // make items as reference
66        let mut store_items = store_items.iter().collect::<Vec<_>>();
67        store_items.sort_by(|a, b| a.id.clock.cmp(&b.id.clock));
68
69        self.parse_items(store_items)
70    }
71
72    pub fn parse_delete_sets(
73        &self,
74        old_sets: &ClientMap<OrderRange>,
75        new_sets: &ClientMap<OrderRange>,
76    ) -> Vec<History> {
77        let store = self.store.read().unwrap();
78        let deleted_items = new_sets
79            .iter()
80            .filter_map(|(id, new_range)| {
81                // diff range if old range exists, or use new range
82                let range = old_sets
83                    .get(id)
84                    .map(|r| r.diff_range(new_range).into())
85                    .unwrap_or(new_range.clone());
86                (!range.is_empty()).then_some((id, range))
87            })
88            .filter_map(|(client, range)| {
89                // check items contains in deleted range
90                store.items.get(client).map(move |items| {
91                    items
92                        .iter()
93                        .filter(move |i| range.contains(i.clock()))
94                        .filter_map(|i| i.as_item().get().cloned())
95                })
96            })
97            .flatten()
98            .collect();
99
100        self.parse_deleted_items(deleted_items)
101    }
102
103    pub fn parse_store(&self, options: HistoryOptions) -> Vec<History> {
104        let store_items = {
105            let client = options
106                .client
107                .as_ref()
108                .and_then(|client| client.ne(&0).then_some(client));
109            let store = self.store.read().unwrap();
110            let mut sort_iter: Box<dyn Iterator<Item = Item>> = Box::new(
111                SortedNodes::new(if let Some(client) = client {
112                    store.items.get(client).map(|i| vec![(client, i)]).unwrap_or_default()
113                } else {
114                    store.items.iter().collect::<Vec<_>>()
115                })
116                .filter_map(|n| n.as_item().get().cloned()),
117            );
118            if client.is_some() {
119                // skip and limit only available when client is set
120                if let Some(skip) = options.skip {
121                    sort_iter = Box::new(sort_iter.skip(skip));
122                }
123                if let Some(limit) = options.limit {
124                    sort_iter = Box::new(sort_iter.take(limit));
125                }
126            }
127
128            sort_iter.collect::<Vec<_>>()
129        };
130
131        // make items as reference
132        let mut store_items = store_items.iter().collect::<Vec<_>>();
133        store_items.sort_by(|a, b| a.id.clock.cmp(&b.id.clock));
134
135        self.parse_items(store_items)
136    }
137
138    fn parse_items(&self, store_items: Vec<&Item>) -> Vec<History> {
139        let parents = self.parents.read().unwrap();
140        let mut histories = vec![];
141
142        for item in store_items {
143            if item.deleted() {
144                continue;
145            }
146
147            histories.push(History {
148                id: item.id.to_string(),
149                parent: Self::parse_path(item, &parents),
150                content: Value::from(&item.content).to_string(),
151                action: HistoryAction::Update,
152            })
153        }
154
155        histories
156    }
157
158    fn parse_deleted_items(&self, deleted_items: Vec<Item>) -> Vec<History> {
159        let parents = self.parents.read().unwrap();
160        let mut histories = vec![];
161
162        for item in deleted_items {
163            histories.push(History {
164                id: item.id.to_string(),
165                parent: Self::parse_path(&item, &parents),
166                content: Value::from(&item.content).to_string(),
167                action: HistoryAction::Delete,
168            })
169        }
170
171        histories
172    }
173
174    fn parse_path(item: &Item, parents: &HashMap<Id, Somr<Item>>) -> Vec<String> {
175        let mut path = Vec::new();
176        let mut cur = item.clone();
177
178        while let Some(node) = cur.find_node_with_parent_info() {
179            path.push(Self::get_node_name(&node));
180
181            match Self::get_parent(parents, &node.parent) {
182                ParentNode::Root(name) => {
183                    path.push(name);
184                    break;
185                }
186                ParentNode::Node(parent) => {
187                    if let Some(parent) = parent.get() {
188                        cur = parent.clone();
189                    } else {
190                        break;
191                    }
192                }
193                ParentNode::Unknown => {
194                    break;
195                }
196            }
197        }
198
199        path.reverse();
200        path
201    }
202
203    fn get_node_name(item: &Item) -> String {
204        if let Some(name) = item.parent_sub.clone() {
205            name.to_string()
206        } else {
207            let mut curr = item.clone();
208            let mut idx = 0;
209
210            while let Some(item) = curr.left.get() {
211                curr = item.clone();
212                idx += 1;
213            }
214
215            idx.to_string()
216        }
217    }
218
219    fn get_parent(parents: &HashMap<Id, Somr<Item>>, parent: &Option<Parent>) -> ParentNode {
220        match parent {
221            None => ParentNode::Unknown,
222            Some(Parent::Type(ptr)) => ptr
223                .ty()
224                .and_then(|ty| {
225                    ty.item
226                        .get()
227                        .and_then(|i| parents.get(&i.id).map(|p| ParentNode::Node(p.clone())))
228                        .or(ty.root_name.clone().map(ParentNode::Root))
229                })
230                .unwrap_or(ParentNode::Unknown),
231            Some(Parent::String(name)) => ParentNode::Root(name.to_string()),
232            Some(Parent::Id(id)) => parents
233                .get(id)
234                .map(|p| ParentNode::Node(p.clone()))
235                .unwrap_or(ParentNode::Unknown),
236        }
237    }
238}
239
240#[derive(Debug, Serialize, Deserialize, PartialEq)]
241pub enum HistoryAction {
242    Insert,
243    Update,
244    Delete,
245}
246
247#[derive(Debug, Serialize, Deserialize, PartialEq)]
248pub struct History {
249    pub id: String,
250    pub parent: Vec<String>,
251    pub content: String,
252    pub action: HistoryAction,
253}
254
255pub(crate) struct SortedNodes<'a> {
256    nodes: Vec<(&'a Client, &'a VecDeque<Node>)>,
257    current: Option<VecDeque<Node>>,
258}
259
260impl<'a> SortedNodes<'a> {
261    pub fn new(mut nodes: Vec<(&'a Client, &'a VecDeque<Node>)>) -> Self {
262        nodes.sort_by(|a, b| b.0.cmp(a.0));
263        let current = nodes.pop().map(|(_, v)| v.clone());
264        Self { nodes, current }
265    }
266}
267
268impl Iterator for SortedNodes<'_> {
269    type Item = Node;
270
271    fn next(&mut self) -> Option<Self::Item> {
272        if let Some(current) = self.current.as_mut()
273            && let Some(node) = current.pop_back()
274        {
275            return Some(node);
276        }
277
278        if let Some((_, nodes)) = self.nodes.pop() {
279            self.current = Some(nodes.clone());
280            self.next()
281        } else {
282            None
283        }
284    }
285}
286
287#[cfg(test)]
288mod test {
289    use super::*;
290
291    #[test]
292    fn parse_history_client_test() {
293        loom_model!({
294            let doc = Doc::default();
295            let mut map = doc.get_or_create_map("map").unwrap();
296            let mut sub_map = doc.create_map().unwrap();
297            map.insert("sub_map".to_string(), sub_map.clone()).unwrap();
298            sub_map.insert("key".to_string(), "value").unwrap();
299
300            assert_eq!(doc.clients()[0], doc.client());
301        });
302    }
303
304    #[test]
305    fn parse_history_test() {
306        loom_model!({
307            let doc = Doc::default();
308            let mut map = doc.get_or_create_map("map").unwrap();
309            let mut sub_map = doc.create_map().unwrap();
310            map.insert("sub_map".to_string(), sub_map.clone()).unwrap();
311            sub_map.insert("key".to_string(), "value").unwrap();
312
313            let history = StoreHistory::new(&doc.store);
314
315            let update = doc.encode_update().unwrap();
316
317            assert_eq!(history.parse_store(Default::default()), history.parse_update(&update,));
318        });
319    }
320}
y_octo/doc/history.rs

y_octo/doc/
history.rs
