script/dom/node/
comparator.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5use std::cmp::Ordering;
6
7use bitflags::bitflags;
8use js::context::NoGC;
9use script_bindings::dom::UnrootedDom;
10
11use crate::dom::Node;
12use crate::dom::traversal::NoGcTraversal;
13
14#[derive(Clone, Copy)]
15pub(crate) struct DomPositionContainment(u8);
16
17bitflags! {
18    impl DomPositionContainment: u8 {
19        const AContainsB = 1 << 0;
20        const BContainsA = 1 << 1;
21    }
22}
23
24pub(crate) fn compare_dom_positions<Traversal: NoGcTraversal>(
25    no_gc: &NoGC,
26    container_a: &Node,
27    offset_a: u32,
28    container_b: &Node,
29    offset_b: u32,
30) -> (Option<Ordering>, DomPositionContainment) {
31    if container_a == container_b {
32        return (
33            Some(offset_a.cmp(&offset_b)),
34            DomPositionContainment::empty(),
35        );
36    }
37
38    if let Some(child_of_a) = find_child_in_ancestors::<Traversal>(no_gc, container_b, container_a)
39    {
40        let ordering =
41            match compare_offset_and_node_in_same_parent::<Traversal>(no_gc, offset_a, &child_of_a)
42            {
43                Ordering::Equal => Ordering::Less,
44                ordering => ordering,
45            };
46        return (Some(ordering), DomPositionContainment::AContainsB);
47    }
48
49    if let Some(child_of_b) = find_child_in_ancestors::<Traversal>(no_gc, container_a, container_b)
50    {
51        let ordering =
52            match compare_offset_and_node_in_same_parent::<Traversal>(no_gc, offset_b, &child_of_b)
53            {
54                Ordering::Equal => Ordering::Greater,
55                ordering => ordering.reverse(),
56            };
57        return (Some(ordering), DomPositionContainment::BContainsA);
58    }
59
60    let Some((least_common_ancestor_child_of_a, least_common_ancestor_child_of_b)) =
61        least_common_ancestor_children::<Traversal>(no_gc, container_a, container_b)
62    else {
63        return (None, DomPositionContainment::empty());
64    };
65
66    let ordering = compare_nodes_in_same_parent::<Traversal>(
67        no_gc,
68        &least_common_ancestor_child_of_a,
69        &least_common_ancestor_child_of_b,
70    );
71    (Some(ordering), DomPositionContainment::empty())
72}
73
74/// If `possible_ancestor` is an ancestor of `possible_descendant` return the
75/// child of `possible_ancestor` that is an ancestor of `possible_descendant` or
76/// is `possible_descendant` itself.
77fn find_child_in_ancestors<'a, Traversal: NoGcTraversal>(
78    no_gc: &'a NoGC,
79    possible_descendant: &Node,
80    possible_ancestor: &Node,
81) -> Option<UnrootedDom<'a, Node>> {
82    let mut child = UnrootedDom::from_ref(possible_descendant, no_gc);
83    let mut maybe_ancestor = Traversal::parent(no_gc, possible_descendant);
84    while let Some(ancestor) = maybe_ancestor {
85        if **ancestor == *possible_ancestor {
86            return Some(child);
87        }
88
89        maybe_ancestor = Traversal::parent(no_gc, &ancestor);
90        child = ancestor;
91    }
92    None
93}
94
95/// Compare an offset in a parent node with a child node in that same parent node.
96fn compare_offset_and_node_in_same_parent<Traversal: NoGcTraversal>(
97    no_gc: &NoGC,
98    offset_a: u32,
99    node_b: &Node,
100) -> Ordering {
101    let parent = Traversal::parent(no_gc, node_b).expect("Node should always have a parent");
102    for (current_offset, child) in Traversal::children(no_gc, &parent).enumerate() {
103        if current_offset == offset_a as usize && **child == *node_b {
104            return Ordering::Equal;
105        }
106        if current_offset == offset_a as usize {
107            return Ordering::Less;
108        }
109        if **child == *node_b {
110            return Ordering::Greater;
111        }
112    }
113    unreachable!("A node should always be a child of its parent.");
114}
115
116/// Compare two nodes that are both children of the same parent node.
117fn compare_nodes_in_same_parent<Traversal: NoGcTraversal>(
118    no_gc: &NoGC,
119    node_a: &Node,
120    node_b: &Node,
121) -> Ordering {
122    if node_a == node_b {
123        return Ordering::Equal;
124    }
125
126    let parent = Traversal::parent(no_gc, node_a).expect("Node should always have a parent");
127    for child in Traversal::children(no_gc, &parent) {
128        if **child == *node_a {
129            return Ordering::Less;
130        }
131        if **child == *node_b {
132            return Ordering::Greater;
133        }
134    }
135    unreachable!("A node should always be a child of its parent.");
136}
137
138/// When `node_a` and `node_b` share a least common ancestor, this function returns a
139/// tuple containing the child of the least common ancestor that is an inclusive ancestor
140/// of `node_a` and the child of the least common ancestor that is an inclusive ancestor
141/// of `node_b`. If `node_a` and `node_b` do not have a least common ancestor, this
142/// returns `None`.
143///
144/// Note: This function assumes that the least common inclusive ancestor is neither of the
145/// nodes passed as arguments.
146fn least_common_ancestor_children<'a, Traversal: NoGcTraversal>(
147    no_gc: &'a NoGC,
148    node_a: &Node,
149    node_b: &Node,
150) -> Option<(UnrootedDom<'a, Node>, UnrootedDom<'a, Node>)> {
151    let mut depth_a = 0;
152    let mut inclusive_ancestor = Some(UnrootedDom::from_ref(node_a, no_gc));
153    while let Some(ancestor) = inclusive_ancestor {
154        debug_assert!(**ancestor != *node_b);
155        inclusive_ancestor = Traversal::parent(no_gc, &ancestor);
156        depth_a += 1;
157    }
158
159    let mut depth_b = 0;
160    let mut inclusive_ancestor = Some(UnrootedDom::from_ref(node_b, no_gc));
161    while let Some(ancestor) = inclusive_ancestor {
162        debug_assert!(**ancestor != *node_a);
163        inclusive_ancestor = Traversal::parent(no_gc, &ancestor);
164        depth_b += 1;
165    }
166
167    let mut inclusive_ancestor_of_a = Some(UnrootedDom::from_ref(node_a, no_gc));
168    let mut inclusive_ancestor_of_b = Some(UnrootedDom::from_ref(node_b, no_gc));
169
170    while depth_a > depth_b {
171        let ancestor = inclusive_ancestor_of_a.expect("Guaranteed by depth");
172        inclusive_ancestor_of_a = Traversal::parent(no_gc, &ancestor);
173        depth_a -= 1;
174    }
175
176    while depth_b > depth_a {
177        let ancestor = inclusive_ancestor_of_b.expect("Guaranteed by depth");
178        inclusive_ancestor_of_b = Traversal::parent(no_gc, &ancestor);
179        depth_b -= 1;
180    }
181
182    let mut candidate_child_a = inclusive_ancestor_of_a.expect("Should always have a candidate");
183    let mut candidate_child_b = inclusive_ancestor_of_b.expect("Should always have a candidate");
184    let mut inclusive_ancestor_of_a = Traversal::parent(no_gc, &candidate_child_a);
185    let mut inclusive_ancestor_of_b = Traversal::parent(no_gc, &candidate_child_b);
186
187    while let Some(ancestor_of_a) = inclusive_ancestor_of_a &&
188        let Some(ancestor_of_b) = inclusive_ancestor_of_b
189    {
190        if ancestor_of_a == ancestor_of_b {
191            return Some((candidate_child_a, candidate_child_b));
192        }
193
194        inclusive_ancestor_of_a = Traversal::parent(no_gc, &ancestor_of_a);
195        inclusive_ancestor_of_b = Traversal::parent(no_gc, &ancestor_of_b);
196        candidate_child_a = ancestor_of_a;
197        candidate_child_b = ancestor_of_b;
198    }
199
200    None
201}
script/dom/node/comparator.rs

script/dom/node/
comparator.rs
