oino_session/manager/
tree.rs

1//! Tree view of a session, built and dropped without recursion so very deep
2//! linear sessions cannot overflow the stack.
3
4use std::collections::HashMap;
5
6use serde::{Serialize, Serializer};
7
8use crate::entry::{EntryId, IsoTimestamp, SessionEntry};
9
10/// One node of [`super::SessionManager::tree`].
11#[derive(Clone, Debug, PartialEq)]
12pub struct SessionTreeNode {
13    /// The entry.
14    pub entry: SessionEntry,
15    /// Children sorted by entry timestamp (stable).
16    pub children: Vec<SessionTreeNode>,
17    /// Current label of this entry.
18    pub label: Option<String>,
19    /// When the label was set.
20    pub label_timestamp: Option<IsoTimestamp>,
21}
22
23impl Drop for SessionTreeNode {
24    fn drop(&mut self) {
25        let mut stack = std::mem::take(&mut self.children);
26        while let Some(mut node) = stack.pop() {
27            stack.append(&mut node.children);
28        }
29    }
30}
31
32impl Serialize for SessionTreeNode {
33    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
34        use serde::ser::SerializeMap;
35        let mut map = serializer.serialize_map(None)?;
36        map.serialize_entry("entry", &self.entry)?;
37        map.serialize_entry("children", &self.children)?;
38        if let Some(label) = &self.label {
39            map.serialize_entry("label", label)?;
40        }
41        if let Some(timestamp) = &self.label_timestamp {
42            map.serialize_entry("labelTimestamp", timestamp)?;
43        }
44        map.end()
45    }
46}
47
48pub(super) fn build(
49    entries: &[SessionEntry],
50    labels: &HashMap<EntryId, (String, IsoTimestamp)>,
51) -> Vec<SessionTreeNode> {
52    let position: HashMap<&EntryId, usize> = entries
53        .iter()
54        .enumerate()
55        .map(|(i, e)| (&e.id, i))
56        .collect();
57    let mut children: Vec<Vec<usize>> = vec![Vec::new(); entries.len()];
58    let mut roots = Vec::new();
59    for (index, entry) in entries.iter().enumerate() {
60        match entry
61            .parent_id
62            .as_ref()
63            .filter(|parent| **parent != entry.id)
64            .and_then(|parent| position.get(parent))
65        {
66            Some(&parent) if parent != index => children[parent].push(index),
67            _ => roots.push(index),
68        }
69    }
70    let millis: Vec<i64> = entries
71        .iter()
72        .map(|e| e.timestamp.to_ms().unwrap_or(0))
73        .collect();
74    for list in &mut children {
75        list.sort_by_key(|&index| millis[index]);
76    }
77    // Post-order without recursion, then assemble bottom-up.
78    let mut order = Vec::with_capacity(entries.len());
79    let mut stack: Vec<usize> = roots.clone();
80    let mut visited = vec![false; entries.len()];
81    while let Some(index) = stack.pop() {
82        if std::mem::replace(&mut visited[index], true) {
83            continue;
84        }
85        order.push(index);
86        stack.extend(children[index].iter().copied());
87    }
88    let mut built: Vec<Option<SessionTreeNode>> = (0..entries.len()).map(|_| None).collect();
89    for &index in order.iter().rev() {
90        let entry = &entries[index];
91        let kids = children[index]
92            .iter()
93            .filter_map(|&child| built[child].take())
94            .collect();
95        let label = labels.get(&entry.id);
96        built[index] = Some(SessionTreeNode {
97            entry: entry.clone(),
98            children: kids,
99            label: label.map(|(text, _)| text.clone()),
100            label_timestamp: label.map(|(_, ts)| ts.clone()),
101        });
102    }
103    roots
104        .into_iter()
105        .filter_map(|index| built[index].take())
106        .collect()
107}
oino_session/manager/tree.rs

oino_session/manager/
tree.rs
