azul_core/
diff.rs

1use std::{
2    fmt,
3    collections::BTreeSet,
4};
5use crate::{
6    id_tree::{NodeId, NodeDataContainer},
7    dom::{CompactDom, NodeData},
8};
9
10#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
11pub struct DomRange {
12    pub start: NodeId,
13    pub end: NodeId,
14}
15
16impl DomRange {
17
18    pub fn new(start: NodeId, end: NodeId) -> Self {
19        Self { start, end }
20    }
21
22    pub fn single_node(node_id: NodeId) -> Self {
23        Self {
24            start: node_id,
25            end: node_id,
26        }
27    }
28}
29
30impl fmt::Debug for DomRange {
31    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
32        write!(f, "{}..{}", self.start, self.end)
33    }
34}
35
36impl fmt::Display for DomRange {
37    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
38        write!(f, "{}..{}", self.start, self.end)
39    }
40}
41
42#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
43pub enum DomChange {
44    /// Node is present on the new DOM, but not on the old one = add node
45    Added(DomRange),
46    /// Node is present on the old DOM, but not on the new one = remove node
47    Removed(DomRange),
48}
49
50impl fmt::Display for DomChange {
51    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
52        use self::DomChange::*;
53        match self {
54            Added(c) => write!(f, "+ {}", c),
55            Removed(c) => write!(f, "- {}", c),
56        }
57    }
58}
59
60#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
61pub struct DomDiff {
62    /// What the actual changes nodes (not trees / subtrees) were in this diff, in order of appearance
63    pub changed_nodes: Vec<DomChange>,
64}
65
66impl DomDiff {
67    pub fn new(old: &CompactDom, new: &CompactDom) -> Self {
68
69        // TODO: Check if old root = new root, if not, change entire tree
70
71        let mut changes = BTreeSet::new();
72        let mut visited_nodes = NodeDataContainer::new(vec![false; new.len()]);
73
74        visited_nodes[NodeId::ZERO] = true;
75
76        let has_root_changed = node_has_changed(
77            &old.arena.node_data[NodeId::ZERO],
78            &new.arena.node_data[NodeId::ZERO]
79        );
80
81        if has_root_changed == NODE_CHANGED_NOTHING {
82
83            diff_tree_inner(NodeId::ZERO, old, new, &mut changes, &mut visited_nodes);
84            add_visited_nodes(visited_nodes, &mut changes);
85
86            Self {
87                changed_nodes: optimize_changeset(changes)
88            }
89
90        } else {
91
92            // Root changed = everything changed
93            changes.insert(DomChange::Removed(DomRange {
94                start: NodeId::ZERO,
95                end: NodeId::new(old.len() - 1)
96            }));
97
98            changes.insert(DomChange::Added(DomRange {
99                start: NodeId::ZERO,
100                end: NodeId::new(new.len() - 1)
101            }));
102
103            Self {
104                changed_nodes: optimize_changeset(changes)
105            }
106        }
107    }
108
109    /// Formats the diff into a git-like `+ Node1 / - Node3` form
110    pub fn format_nicely(&self, old: &CompactDom, new: &CompactDom) -> String {
111        use self::DomChange::*;
112        self.changed_nodes.iter().map(|change| {
113            match change {
114                Added(c) => format!("+\t{}", new.arena.node_data[c.start]),
115                Removed(c) => format!("-\t{}", old.arena.node_data[c.start]),
116            }
117        }).collect::<Vec<String>>().join("\r\n")
118    }
119}
120
121impl fmt::Display for DomDiff {
122    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
123        for c in self.changed_nodes.iter() {
124            write!(f, "{}", c)?;
125        }
126        Ok(())
127    }
128}
129
130impl DomRange {
131
132    /// Is `other` a subtree of `self`? - Assumes that the DOM was
133    /// constructed in a linear order, i.e. the child being within
134    /// the parents start / end bounds
135    pub fn contains(&self, other: &Self) -> bool {
136        other.start.index() >= self.start.index() &&
137        other.end.index() <= self.end.index()
138    }
139
140    /// Compares two DOM ranges *without* looking at the DOM hashes (not equivalent to `==`)
141    pub fn equals_range(&self, other: &Self) -> bool {
142        other.start == self.start &&
143        other.end == self.end
144    }
145}
146
147const NODE_CHANGED_NOTHING: u8  = 0x01;
148const NODE_CHANGED_TYPE: u8     = 0x02;
149const NODE_CHANGED_CLASSES: u8  = 0x04;
150const NODE_CHANGED_IDS: u8      = 0x08;
151
152// In order to test two DOM nodes for "equality", you'd need to
153// test if the node type, the classes and the ids are the same.
154// The rest of the attributes can be ignored, since they are not
155// used by the CSS engine.
156//
157// NOTE: The callbacks / etc. need to be changed!
158#[inline]
159fn node_has_changed(old: &NodeData, new: &NodeData) -> u8 {
160    let mut result = NODE_CHANGED_NOTHING;
161
162    if old.get_node_type() != new.get_node_type() {
163        result &= NODE_CHANGED_TYPE;
164    }
165
166    if old.get_classes() != new.get_classes() {
167        result &= NODE_CHANGED_CLASSES;
168    }
169
170    if old.get_ids() != new.get_ids() {
171        result &= NODE_CHANGED_IDS;
172    }
173
174    result
175}
176
177fn diff_tree_inner(
178    old_root_id: NodeId,
179    old: &CompactDom,
180    new: &CompactDom,
181    changes: &mut BTreeSet<DomChange>,
182    visited_nodes: &mut NodeDataContainer<bool>,
183) {
184    let mut node_shift = 0_isize;
185
186    for old_node_id in old_root_id.children(&old.arena.node_hierarchy) {
187
188        // Node ID that corresponds to the same node in the new node tree
189        let new_node_id = NodeId::new((old_node_id.index() as isize + node_shift) as usize);
190
191        let old_node_last_child = NodeId::new(match old.arena.node_hierarchy[old_node_id].next_sibling {
192            Some(s) => s.index(),
193            None => old.arena.node_hierarchy.len() - 1,
194        });
195
196        match new.arena.node_data.get(new_node_id) {
197            None => {
198                // Couldn't find the new node in the new tree, old tree has more children than new
199                changes.insert(DomChange::Removed(DomRange {
200                    start: old_node_id,
201                    end: old_node_last_child,
202                }));
203            },
204            Some(new_node_data) => {
205
206                visited_nodes[new_node_id] = true;
207
208                let old_node_data = &old.arena.node_data[old_node_id];
209                let compare_nodes = node_has_changed(old_node_data, new_node_data);
210
211                if compare_nodes == NODE_CHANGED_NOTHING {
212                    diff_tree_inner(old_node_id, old, new, changes, visited_nodes);
213                } else {
214
215                    let new_node_subtree_len = new.arena.node_hierarchy.subtree_len(new_node_id);
216
217                    let next_node_id = match new.arena.node_hierarchy[new_node_id].next_sibling {
218                        Some(s) => s.index(),
219                        None => new.arena.node_hierarchy.len() - 1,
220                    };
221
222                    // remove entire old subtree, including the node itself
223                    changes.insert(DomChange::Removed(DomRange {
224                        start: old_node_id,
225                        end: old_node_last_child,
226                    }));
227
228                    // add entire new subtree, including the node itself
229                    changes.insert(DomChange::Added(DomRange {
230                        start: new_node_id,
231                        end: NodeId::new(next_node_id),
232                    }));
233
234                    node_shift += new_node_subtree_len as isize;
235
236                    for n in new_node_id.index()..next_node_id {
237                        visited_nodes[NodeId::new(n)] = true;
238                    }
239                }
240            }
241        }
242    }
243}
244
245fn add_visited_nodes(
246    visited_nodes: NodeDataContainer<bool>,
247    changes: &mut BTreeSet<DomChange>,
248) {
249    changes.extend(
250        visited_nodes
251        .linear_iter()
252        .filter_map(|node_id| if visited_nodes[node_id] { None } else { Some(node_id) })
253        .map(|node_id| DomChange::Added(DomRange::single_node(node_id)))
254    );
255}
256
257fn optimize_changeset(changes: BTreeSet<DomChange>) -> Vec<DomChange> {
258    // TODO: optimize changeset into larger chunks!
259    changes.into_iter().collect()
260}
azul_core/diff.rs

azul_core/
diff.rs
