jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2022, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#pragma once
8
9#include <AK/Assertions.h>
10#include <AK/TypeCasts.h>
11#include <LibJS/Heap/Cell.h>
12#include <LibJS/Heap/GCPtr.h>
13#include <LibWeb/Forward.h>
14
15namespace Web {
16
17template<typename T>
18class TreeNode {
19public:
20 T* parent() { return m_parent; }
21 T const* parent() const { return m_parent; }
22
23 bool has_children() const { return m_first_child; }
24 T* next_sibling() { return m_next_sibling; }
25 T* previous_sibling() { return m_previous_sibling; }
26 T* first_child() { return m_first_child; }
27 T* last_child() { return m_last_child; }
28 T const* next_sibling() const { return m_next_sibling; }
29 T const* previous_sibling() const { return m_previous_sibling; }
30 T const* first_child() const { return m_first_child; }
31 T const* last_child() const { return m_last_child; }
32
33 size_t child_count() const
34 {
35 size_t count = 0;
36 for (auto* child = first_child(); child; child = child->next_sibling())
37 ++count;
38 return count;
39 }
40
41 T* child_at_index(int index)
42 {
43 int count = 0;
44 for (auto* child = first_child(); child; child = child->next_sibling()) {
45 if (count == index)
46 return child;
47 ++count;
48 }
49 return nullptr;
50 }
51
52 T const* child_at_index(int index) const
53 {
54 return const_cast<TreeNode*>(this)->child_at_index(index);
55 }
56
57 // https://dom.spec.whatwg.org/#concept-tree-index
58 size_t index() const
59 {
60 // The index of an object is its number of preceding siblings, or 0 if it has none.
61 size_t index = 0;
62 for (auto* node = previous_sibling(); node; node = node->previous_sibling())
63 ++index;
64 return index;
65 }
66
67 Optional<size_t> index_of_child(T const& search_child)
68 {
69 VERIFY(search_child.parent() == this);
70 size_t index = 0;
71 auto* child = first_child();
72 VERIFY(child);
73
74 do {
75 if (child == &search_child)
76 return index;
77 index++;
78 } while (child && (child = child->next_sibling()));
79 return {};
80 }
81
82 template<typename ChildType>
83 Optional<size_t> index_of_child(T const& search_child)
84 {
85 VERIFY(search_child.parent() == this);
86 size_t index = 0;
87 auto* child = first_child();
88 VERIFY(child);
89
90 do {
91 if (!is<ChildType>(child))
92 continue;
93 if (child == &search_child)
94 return index;
95 index++;
96 } while (child && (child = child->next_sibling()));
97 return {};
98 }
99
100 bool is_ancestor_of(TreeNode const&) const;
101 bool is_inclusive_ancestor_of(TreeNode const&) const;
102 bool is_descendant_of(TreeNode const&) const;
103 bool is_inclusive_descendant_of(TreeNode const&) const;
104
105 bool is_following(TreeNode const&) const;
106
107 void append_child(JS::NonnullGCPtr<T> node);
108 void prepend_child(JS::NonnullGCPtr<T> node);
109 void insert_before(JS::NonnullGCPtr<T> node, JS::GCPtr<T> child);
110 void remove_child(JS::NonnullGCPtr<T> node);
111
112 bool is_child_allowed(T const&) const { return true; }
113
114 T* next_in_pre_order()
115 {
116 if (first_child())
117 return first_child();
118 T* node;
119 if (!(node = next_sibling())) {
120 node = parent();
121 while (node && !node->next_sibling())
122 node = node->parent();
123 if (node)
124 node = node->next_sibling();
125 }
126 return node;
127 }
128
129 T* next_in_pre_order(T const* stay_within)
130 {
131 if (first_child())
132 return first_child();
133
134 T* node = static_cast<T*>(this);
135 T* next = nullptr;
136 while (!(next = node->next_sibling())) {
137 node = node->parent();
138 if (!node || node == stay_within)
139 return nullptr;
140 }
141 return next;
142 }
143
144 T const* next_in_pre_order() const
145 {
146 return const_cast<TreeNode*>(this)->next_in_pre_order();
147 }
148
149 T const* next_in_pre_order(T const* stay_within) const
150 {
151 return const_cast<TreeNode*>(this)->next_in_pre_order(stay_within);
152 }
153
154 T* previous_in_pre_order()
155 {
156 if (auto* node = previous_sibling()) {
157 while (node->last_child())
158 node = node->last_child();
159
160 return node;
161 }
162
163 return parent();
164 }
165
166 T const* previous_in_pre_order() const
167 {
168 return const_cast<TreeNode*>(this)->previous_in_pre_order();
169 }
170
171 bool is_before(T const& other) const
172 {
173 if (this == &other)
174 return false;
175 for (auto* node = this; node; node = node->next_in_pre_order()) {
176 if (node == &other)
177 return true;
178 }
179 return false;
180 }
181
182 // https://dom.spec.whatwg.org/#concept-tree-preceding (Object A is 'typename U' and Object B is 'this')
183 template<typename U>
184 bool has_preceding_node_of_type_in_tree_order() const
185 {
186 for (auto* node = previous_in_pre_order(); node; node = node->previous_in_pre_order()) {
187 if (is<U>(node))
188 return true;
189 }
190 return false;
191 }
192
193 // https://dom.spec.whatwg.org/#concept-tree-following (Object A is 'typename U' and Object B is 'this')
194 template<typename U>
195 bool has_following_node_of_type_in_tree_order() const
196 {
197 for (auto* node = next_in_pre_order(); node; node = node->next_in_pre_order()) {
198 if (is<U>(node))
199 return true;
200 }
201 return false;
202 }
203
204 template<typename Callback>
205 IterationDecision for_each_in_inclusive_subtree(Callback callback) const
206 {
207 if (callback(static_cast<T const&>(*this)) == IterationDecision::Break)
208 return IterationDecision::Break;
209 for (auto* child = first_child(); child; child = child->next_sibling()) {
210 if (child->for_each_in_inclusive_subtree(callback) == IterationDecision::Break)
211 return IterationDecision::Break;
212 }
213 return IterationDecision::Continue;
214 }
215
216 template<typename Callback>
217 IterationDecision for_each_in_inclusive_subtree(Callback callback)
218 {
219 if (callback(static_cast<T&>(*this)) == IterationDecision::Break)
220 return IterationDecision::Break;
221 for (auto* child = first_child(); child; child = child->next_sibling()) {
222 if (child->for_each_in_inclusive_subtree(callback) == IterationDecision::Break)
223 return IterationDecision::Break;
224 }
225 return IterationDecision::Continue;
226 }
227
228 template<typename U, typename Callback>
229 IterationDecision for_each_in_inclusive_subtree_of_type(Callback callback)
230 {
231 if (is<U>(static_cast<T const&>(*this))) {
232 if (callback(static_cast<U&>(*this)) == IterationDecision::Break)
233 return IterationDecision::Break;
234 }
235 for (auto* child = first_child(); child; child = child->next_sibling()) {
236 if (child->template for_each_in_inclusive_subtree_of_type<U>(callback) == IterationDecision::Break)
237 return IterationDecision::Break;
238 }
239 return IterationDecision::Continue;
240 }
241
242 template<typename U, typename Callback>
243 IterationDecision for_each_in_inclusive_subtree_of_type(Callback callback) const
244 {
245 if (is<U>(static_cast<T const&>(*this))) {
246 if (callback(static_cast<U const&>(*this)) == IterationDecision::Break)
247 return IterationDecision::Break;
248 }
249 for (auto* child = first_child(); child; child = child->next_sibling()) {
250 if (child->template for_each_in_inclusive_subtree_of_type<U>(callback) == IterationDecision::Break)
251 return IterationDecision::Break;
252 }
253 return IterationDecision::Continue;
254 }
255
256 template<typename Callback>
257 IterationDecision for_each_in_subtree(Callback callback) const
258 {
259 for (auto* child = first_child(); child; child = child->next_sibling()) {
260 if (child->for_each_in_inclusive_subtree(callback) == IterationDecision::Break)
261 return IterationDecision::Break;
262 }
263 return IterationDecision::Continue;
264 }
265
266 template<typename Callback>
267 IterationDecision for_each_in_subtree(Callback callback)
268 {
269 for (auto* child = first_child(); child; child = child->next_sibling()) {
270 if (child->for_each_in_inclusive_subtree(callback) == IterationDecision::Break)
271 return IterationDecision::Break;
272 }
273 return IterationDecision::Continue;
274 }
275
276 template<typename U, typename Callback>
277 IterationDecision for_each_in_subtree_of_type(Callback callback)
278 {
279 for (auto* child = first_child(); child; child = child->next_sibling()) {
280 if (child->template for_each_in_inclusive_subtree_of_type<U>(callback) == IterationDecision::Break)
281 return IterationDecision::Break;
282 }
283 return IterationDecision::Continue;
284 }
285
286 template<typename U, typename Callback>
287 IterationDecision for_each_in_subtree_of_type(Callback callback) const
288 {
289 for (auto* child = first_child(); child; child = child->next_sibling()) {
290 if (child->template for_each_in_inclusive_subtree_of_type<U>(callback) == IterationDecision::Break)
291 return IterationDecision::Break;
292 }
293 return IterationDecision::Continue;
294 }
295
296 template<typename Callback>
297 void for_each_child(Callback callback) const
298 {
299 return const_cast<TreeNode*>(this)->template for_each_child(move(callback));
300 }
301
302 template<typename Callback>
303 void for_each_child(Callback callback)
304 {
305 for (auto* node = first_child(); node; node = node->next_sibling())
306 callback(*node);
307 }
308
309 template<typename U, typename Callback>
310 void for_each_child_of_type(Callback callback)
311 {
312 for (auto* node = first_child(); node; node = node->next_sibling()) {
313 if (is<U>(node))
314 callback(verify_cast<U>(*node));
315 }
316 }
317
318 template<typename U, typename Callback>
319 void for_each_child_of_type(Callback callback) const
320 {
321 return const_cast<TreeNode*>(this)->template for_each_child_of_type<U>(move(callback));
322 }
323
324 template<typename U>
325 U const* next_sibling_of_type() const
326 {
327 return const_cast<TreeNode*>(this)->template next_sibling_of_type<U>();
328 }
329
330 template<typename U>
331 inline U* next_sibling_of_type()
332 {
333 for (auto* sibling = next_sibling(); sibling; sibling = sibling->next_sibling()) {
334 if (is<U>(*sibling))
335 return &verify_cast<U>(*sibling);
336 }
337 return nullptr;
338 }
339
340 template<typename U>
341 U const* previous_sibling_of_type() const
342 {
343 return const_cast<TreeNode*>(this)->template previous_sibling_of_type<U>();
344 }
345
346 template<typename U>
347 U* previous_sibling_of_type()
348 {
349 for (auto* sibling = previous_sibling(); sibling; sibling = sibling->previous_sibling()) {
350 if (is<U>(*sibling))
351 return &verify_cast<U>(*sibling);
352 }
353 return nullptr;
354 }
355
356 template<typename U>
357 U const* first_child_of_type() const
358 {
359 return const_cast<TreeNode*>(this)->template first_child_of_type<U>();
360 }
361
362 template<typename U>
363 U const* last_child_of_type() const
364 {
365 return const_cast<TreeNode*>(this)->template last_child_of_type<U>();
366 }
367
368 template<typename U>
369 U* first_child_of_type()
370 {
371 for (auto* child = first_child(); child; child = child->next_sibling()) {
372 if (is<U>(*child))
373 return &verify_cast<U>(*child);
374 }
375 return nullptr;
376 }
377
378 template<typename U>
379 U* last_child_of_type()
380 {
381 for (auto* child = last_child(); child; child = child->previous_sibling()) {
382 if (is<U>(*child))
383 return &verify_cast<U>(*child);
384 }
385 return nullptr;
386 }
387
388 template<typename U>
389 bool has_child_of_type() const
390 {
391 return first_child_of_type<U>() != nullptr;
392 }
393
394 template<typename U>
395 U const* first_ancestor_of_type() const
396 {
397 return const_cast<TreeNode*>(this)->template first_ancestor_of_type<U>();
398 }
399
400 template<typename U>
401 U* first_ancestor_of_type()
402 {
403 for (auto* ancestor = parent(); ancestor; ancestor = ancestor->parent()) {
404 if (is<U>(*ancestor))
405 return &verify_cast<U>(*ancestor);
406 }
407 return nullptr;
408 }
409
410 bool is_parent_of(T const& other) const
411 {
412 for (auto* child = first_child(); child; child = child->next_sibling()) {
413 if (&other == child)
414 return true;
415 }
416 return false;
417 }
418
419 ~TreeNode() = default;
420
421protected:
422 TreeNode() = default;
423
424 void visit_edges(JS::Cell::Visitor& visitor)
425 {
426 visitor.visit(m_parent);
427 visitor.visit(m_first_child);
428 visitor.visit(m_last_child);
429 visitor.visit(m_next_sibling);
430 visitor.visit(m_previous_sibling);
431 }
432
433private:
434 T* m_parent { nullptr };
435 T* m_first_child { nullptr };
436 T* m_last_child { nullptr };
437 T* m_next_sibling { nullptr };
438 T* m_previous_sibling { nullptr };
439};
440
441template<typename T>
442inline void TreeNode<T>::remove_child(JS::NonnullGCPtr<T> node)
443{
444 VERIFY(node->m_parent == this);
445
446 if (m_first_child == node)
447 m_first_child = node->m_next_sibling;
448
449 if (m_last_child == node)
450 m_last_child = node->m_previous_sibling;
451
452 if (node->m_next_sibling)
453 node->m_next_sibling->m_previous_sibling = node->m_previous_sibling;
454
455 if (node->m_previous_sibling)
456 node->m_previous_sibling->m_next_sibling = node->m_next_sibling;
457
458 node->m_next_sibling = nullptr;
459 node->m_previous_sibling = nullptr;
460 node->m_parent = nullptr;
461}
462
463template<typename T>
464inline void TreeNode<T>::append_child(JS::NonnullGCPtr<T> node)
465{
466 VERIFY(!node->m_parent);
467
468 if (!static_cast<T*>(this)->is_child_allowed(*node))
469 return;
470
471 if (m_last_child)
472 m_last_child->m_next_sibling = node.ptr();
473 node->m_previous_sibling = m_last_child;
474 node->m_parent = static_cast<T*>(this);
475 m_last_child = node.ptr();
476 if (!m_first_child)
477 m_first_child = m_last_child;
478}
479
480template<typename T>
481inline void TreeNode<T>::insert_before(JS::NonnullGCPtr<T> node, JS::GCPtr<T> child)
482{
483 if (!child)
484 return append_child(move(node));
485
486 VERIFY(!node->m_parent);
487 VERIFY(child->parent() == this);
488
489 node->m_previous_sibling = child->m_previous_sibling;
490 node->m_next_sibling = child;
491
492 if (child->m_previous_sibling)
493 child->m_previous_sibling->m_next_sibling = node;
494
495 if (m_first_child == child)
496 m_first_child = node;
497
498 child->m_previous_sibling = node;
499
500 node->m_parent = static_cast<T*>(this);
501}
502
503template<typename T>
504inline void TreeNode<T>::prepend_child(JS::NonnullGCPtr<T> node)
505{
506 VERIFY(!node->m_parent);
507
508 if (!static_cast<T*>(this)->is_child_allowed(*node))
509 return;
510
511 if (m_first_child)
512 m_first_child->m_previous_sibling = node.ptr();
513 node->m_next_sibling = m_first_child;
514 node->m_parent = static_cast<T*>(this);
515 m_first_child = node.ptr();
516 if (!m_last_child)
517 m_last_child = m_first_child;
518 node->inserted_into(static_cast<T&>(*this));
519
520 static_cast<T*>(this)->children_changed();
521}
522
523template<typename T>
524inline bool TreeNode<T>::is_ancestor_of(TreeNode<T> const& other) const
525{
526 for (auto* ancestor = other.parent(); ancestor; ancestor = ancestor->parent()) {
527 if (ancestor == this)
528 return true;
529 }
530 return false;
531}
532
533template<typename T>
534inline bool TreeNode<T>::is_inclusive_ancestor_of(TreeNode<T> const& other) const
535{
536 return &other == this || is_ancestor_of(other);
537}
538
539template<typename T>
540inline bool TreeNode<T>::is_descendant_of(TreeNode<T> const& other) const
541{
542 return other.is_ancestor_of(*this);
543}
544
545template<typename T>
546inline bool TreeNode<T>::is_inclusive_descendant_of(TreeNode<T> const& other) const
547{
548 return other.is_inclusive_ancestor_of(*this);
549}
550
551// https://dom.spec.whatwg.org/#concept-tree-following
552template<typename T>
553inline bool TreeNode<T>::is_following(TreeNode<T> const& other) const
554{
555 // An object A is following an object B if A and B are in the same tree and A comes after B in tree order.
556 for (auto* node = previous_in_pre_order(); node; node = node->previous_in_pre_order()) {
557 if (node == &other)
558 return true;
559 }
560
561 return false;
562}
563
564}