dymokomi/luce-browser-engine
Source of release 0.6.1
0.6.1 / src / web / tree_node_1.lucb
#==============================================================================================
#
# tree_node_1 - TreeNode<T>: the parent/child/sibling links of the DOM, layout, paintable and
# pseudo-element trees, their mutation and pre-order
#
# DESCRIPTION:
# Port of Libraries/LibWeb/TreeNode.h (lines 1-219 and 479-639, the out-of-line
# members); tree_node_2 has the traversals. TreeNode<T> is a CRTP mixin: in C++
# its members reach the derived T with static_cast<T*>(this). Here the TreeNode[T] is a
# field of T, and every function takes the T itself, constrained by HasTreeNode[T], the
# interface through which a T hands out its embedded links (DESIGN.md §2.5). A
# `TreeNode const&` parameter is the `const T*` it was bound to.
#
# Templates parameterized by a class U (`first_child_of_type<U>`, `for_each_child_of_type
# <U>`, ...) take U's ClassInfo instead and answer the matching T; the caller downcasts
# (DESIGN.md §2.4). C++ lambdas passed as `Callback` become a pointer to a struct that
# implements TraversalCallback[T] or IterationCallback[T], whose `call` is the lambda's
# body (DESIGN.md §2.7 case 2). The const overloads keep their names and forward to the
# mutable ones, as the C++ const_casts do.
#
# Copyright (c) 2018-2022, Andreas Kling <andreas@ladybird.org>
# SPDX-License-Identifier: BSD-2-Clause
#
#==============================================================================================
# mark: Interfaces ==============================================================================
## A class that embeds a TreeNode[T] (the C++ `class T : public TreeNode<T>`): hands out its links.
pub interface HasTreeNode[T]:
func tree() -> TreeNode[T]*
## The hooks TreeNode<T>::prepend_child calls on T: Layout::Node's `inserted_into(Node&)` and
## `children_changed()`. Only Layout::Node instantiates prepend_child.
pub interface TreeNodePrependHooks[T]:
func inserted_into(parent: T*)
func children_changed()
## A C++ traversal callback `[&](T& node) -> TraversalDecision`.
pub interface TraversalCallback[T]:
func call(node: T*) -> TraversalDecision
## A C++ iteration callback `[&](T& node) -> IterationDecision`.
pub interface IterationCallback[T]:
func call(node: T*) -> ak.IterationDecision
## `is<U>(node)` for a U given by its ClassInfo: the class-id range test (DESIGN.md §2.4).
pub func tree_node_is_of_class[T: gc.IsCell](node: const T*, class_info: const ak.ClassInfo*) -> bool:
let id = node.cell().class_id
return id >= class_info.first_id and id <= class_info.last_id
# mark: Conformances ============================================================================
extend DomNode:
func tree() -> TreeNode[DomNode]*: return (TreeNode[DomNode]*)&self.tree_node
extend LayoutNode:
func tree() -> TreeNode[LayoutNode]*: return (TreeNode[LayoutNode]*)&self.tree_node
func inserted_into(parent: LayoutNode*): layout_node_inserted_into((LayoutNode*)&self, parent)
func children_changed(): layout_node_children_changed((LayoutNode*)&self)
extend PaintPaintable:
func tree() -> TreeNode[PaintPaintable]*: return (TreeNode[PaintPaintable]*)&self.tree_node
extend DomPseudoElementTreeNode:
func tree() -> TreeNode[DomPseudoElementTreeNode]*:
return (TreeNode[DomPseudoElementTreeNode]*)&self.tree_node
# mark: traverse_preorder =======================================================================
## Ported from Libraries/LibWeb/TreeNode.h:19 Web::traverse_preorder.
pub func traverse_preorder[T: HasTreeNode[T], C: TraversalCallback[T]](root: T*?, callback: C*) -> TraversalDecision:
var current = root
while let node = current:
let decision = callback.call(node)
if decision == TraversalDecision.break_:
return TraversalDecision.break_
if decision != TraversalDecision.skip_children_and_continue and node.tree().m_first_child != none:
current = node.tree().m_first_child
continue
if root == node:
break
if node.tree().m_next_sibling != none:
current = node.tree().m_next_sibling
continue
var at = node
while root != at and at.tree().m_next_sibling == none:
at = at.tree().m_parent else trap("traverse_preorder: left the tree")
if root == at:
break
current = at.tree().m_next_sibling
return TraversalDecision.continue_
# mark: Links ===================================================================================
## Ported from Libraries/LibWeb/TreeNode.h:52 Web::TreeNode::parent.
pub func tree_node_parent[T: HasTreeNode[T]](this: T*) -> T*?:
return this.tree().m_parent
## Ported from Libraries/LibWeb/TreeNode.h:53 Web::TreeNode::parent.
pub func tree_node_parent_const[T: HasTreeNode[T]](this: const T*) -> const T*?:
return this.tree().m_parent
## Ported from Libraries/LibWeb/TreeNode.h:55 Web::TreeNode::has_children.
pub func tree_node_has_children[T: HasTreeNode[T]](this: const T*) -> bool:
return this.tree().m_first_child != none
## Ported from Libraries/LibWeb/TreeNode.h:56 Web::TreeNode::next_sibling.
pub func tree_node_next_sibling[T: HasTreeNode[T]](this: T*) -> T*?:
return this.tree().m_next_sibling
## Ported from Libraries/LibWeb/TreeNode.h:57 Web::TreeNode::previous_sibling.
pub func tree_node_previous_sibling[T: HasTreeNode[T]](this: T*) -> T*?:
return this.tree().m_previous_sibling
## Ported from Libraries/LibWeb/TreeNode.h:58 Web::TreeNode::first_child.
pub func tree_node_first_child[T: HasTreeNode[T]](this: T*) -> T*?:
return this.tree().m_first_child
## Ported from Libraries/LibWeb/TreeNode.h:59 Web::TreeNode::last_child.
pub func tree_node_last_child[T: HasTreeNode[T]](this: T*) -> T*?:
return this.tree().m_last_child
## Ported from Libraries/LibWeb/TreeNode.h:60 Web::TreeNode::next_sibling.
pub func tree_node_next_sibling_const[T: HasTreeNode[T]](this: const T*) -> const T*?:
return this.tree().m_next_sibling
## Ported from Libraries/LibWeb/TreeNode.h:61 Web::TreeNode::previous_sibling.
pub func tree_node_previous_sibling_const[T: HasTreeNode[T]](this: const T*) -> const T*?:
return this.tree().m_previous_sibling
## Ported from Libraries/LibWeb/TreeNode.h:62 Web::TreeNode::first_child.
pub func tree_node_first_child_const[T: HasTreeNode[T]](this: const T*) -> const T*?:
return this.tree().m_first_child
## Ported from Libraries/LibWeb/TreeNode.h:63 Web::TreeNode::last_child.
pub func tree_node_last_child_const[T: HasTreeNode[T]](this: const T*) -> const T*?:
return this.tree().m_last_child
## Ported from Libraries/LibWeb/TreeNode.h:66 Web::TreeNode::index.
# https://dom.spec.whatwg.org/#concept-tree-index
pub func tree_node_index[T: HasTreeNode[T]](this: const T*) -> usize:
# The index of an object is its number of preceding siblings, or 0 if it has none.
var index: usize = 0
var node = this.tree().m_previous_sibling
while let sibling = node:
index += 1
node = sibling.tree().m_previous_sibling
return index
## Ported from Libraries/LibWeb/TreeNode.h:76 Web::TreeNode::root.
# https://dom.spec.whatwg.org/#concept-tree-root
pub func tree_node_root[T: HasTreeNode[T]](this: T*) -> T*:
# The root of an object is itself, if its parent is null, or else it is the root of its parent.
# The root of a tree is any object participating in that tree whose parent is null.
var root = this
while let parent = root.tree().m_parent:
root = parent
return root
## Ported from Libraries/LibWeb/TreeNode.h:85 Web::TreeNode::root.
pub func tree_node_root_const[T: HasTreeNode[T]](this: const T*) -> const T*:
return tree_node_root((T*)this)
# mark: Ancestry and order ======================================================================
## Ported from Libraries/LibWeb/TreeNode.h:98 Web::TreeNode::has_preceding_node_of_type_in_tree_order.
# https://dom.spec.whatwg.org/#concept-tree-preceding (Object A is 'typename U' and Object B is 'this')
pub func tree_node_has_preceding_node_of_type_in_tree_order[T: HasTreeNode[T] & gc.IsCell](this: const T*, class_info: const ak.ClassInfo*) -> bool:
var node = tree_node_previous_in_pre_order_const(this)
while let at = node:
if tree_node_is_of_class(at, class_info):
return true
node = tree_node_previous_in_pre_order_const(at)
return false
## Ported from Libraries/LibWeb/TreeNode.h:109 Web::TreeNode::has_following_node_of_type_in_tree_order.
# https://dom.spec.whatwg.org/#concept-tree-following (Object A is 'typename U' and Object B is 'this')
pub func tree_node_has_following_node_of_type_in_tree_order[T: HasTreeNode[T] & gc.IsCell](this: const T*, class_info: const ak.ClassInfo*) -> bool:
var node = tree_node_next_in_pre_order_const(this)
while let at = node:
if tree_node_is_of_class(at, class_info):
return true
node = tree_node_next_in_pre_order_const(at)
return false
## Ported from Libraries/LibWeb/TreeNode.h:118 Web::TreeNode::is_parent_of.
pub func tree_node_is_parent_of[T: HasTreeNode[T]](this: const T*, other: const T*) -> bool:
var child = this.tree().m_first_child
while let at = child:
if other == at:
return true
child = at.tree().m_next_sibling
return false
## Ported from Libraries/LibWeb/TreeNode.h:579 Web::TreeNode::is_ancestor_of.
pub func tree_node_is_ancestor_of[T: HasTreeNode[T]](this: const T*, other: const T*) -> bool:
var ancestor = other.tree().m_parent
while let at = ancestor:
if at == this:
return true
ancestor = at.tree().m_parent
return false
## Ported from Libraries/LibWeb/TreeNode.h:589 Web::TreeNode::is_inclusive_ancestor_of.
pub func tree_node_is_inclusive_ancestor_of[T: HasTreeNode[T]](this: const T*, other: const T*) -> bool:
return other == this or tree_node_is_ancestor_of(this, other)
## Ported from Libraries/LibWeb/TreeNode.h:596 Web::TreeNode::contains.
# https://dom.spec.whatwg.org/#dom-node-contains
pub func tree_node_contains[T: HasTreeNode[T]](this: const T*, other: const T*?) -> bool:
# The contains(other) method steps are to return true if other is an inclusive descendant of this; otherwise false (including when other is null).
if let node = other:
return tree_node_is_inclusive_descendant_of(node, this)
return false
## Ported from Libraries/LibWeb/TreeNode.h:603 Web::TreeNode::is_descendant_of.
pub func tree_node_is_descendant_of[T: HasTreeNode[T]](this: const T*, other: const T*) -> bool:
return tree_node_is_ancestor_of(other, this)
## Ported from Libraries/LibWeb/TreeNode.h:609 Web::TreeNode::is_inclusive_descendant_of.
pub func tree_node_is_inclusive_descendant_of[T: HasTreeNode[T]](this: const T*, other: const T*) -> bool:
return tree_node_is_inclusive_ancestor_of(other, this)
## Ported from Libraries/LibWeb/TreeNode.h:616 Web::TreeNode::is_following.
# https://dom.spec.whatwg.org/#concept-tree-following
pub func tree_node_is_following[T: HasTreeNode[T]](this: const T*, other: const T*) -> bool:
# 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.
var node = tree_node_previous_in_pre_order_const(this)
while let at = node:
if at == other:
return true
node = tree_node_previous_in_pre_order_const(at)
return false
## Ported from Libraries/LibWeb/TreeNode.h:628 Web::TreeNode::is_before.
pub func tree_node_is_before[T: HasTreeNode[T]](this: const T*, other: const T*) -> bool:
if this == other:
return false
var node: const T*? = this
while let at = node:
if at == other:
return true
node = tree_node_next_in_pre_order_const(at)
return false
# mark: Mutation ================================================================================
## Ported from Libraries/LibWeb/TreeNode.h:503 Web::TreeNode::append_child.
pub func tree_node_append_child[T: HasTreeNode[T]](this: T*, node: T*):
assert(node.tree().m_parent == none)
if let last = this.tree().m_last_child:
last.tree().m_next_sibling = node
node.tree().m_previous_sibling = this.tree().m_last_child
node.tree().m_parent = this
this.tree().m_last_child = node
if this.tree().m_first_child == none:
this.tree().m_first_child = this.tree().m_last_child
## Ported from Libraries/LibWeb/TreeNode.h:562 Web::TreeNode::prepend_child.
pub func tree_node_prepend_child[T: HasTreeNode[T] & TreeNodePrependHooks[T]](this: T*, node: T*):
assert(node.tree().m_parent == none)
if let first = this.tree().m_first_child:
first.tree().m_previous_sibling = node
node.tree().m_next_sibling = this.tree().m_first_child
node.tree().m_parent = this
this.tree().m_first_child = node
if this.tree().m_last_child == none:
this.tree().m_last_child = this.tree().m_first_child
node.inserted_into(this)
this.children_changed()
## Ported from Libraries/LibWeb/TreeNode.h:539 Web::TreeNode::insert_before.
pub func tree_node_insert_before[T: HasTreeNode[T]](this: T*, node: T*, child: T*?):
let before = child else return tree_node_append_child(this, node)
assert(node.tree().m_parent == none)
assert(before.tree().m_parent == this)
node.tree().m_previous_sibling = before.tree().m_previous_sibling
node.tree().m_next_sibling = before
if let previous = before.tree().m_previous_sibling:
previous.tree().m_next_sibling = node
if this.tree().m_first_child == before:
this.tree().m_first_child = node
before.tree().m_previous_sibling = node
node.tree().m_parent = this
## Ported from Libraries/LibWeb/TreeNode.h:481 Web::TreeNode::remove_child.
pub func tree_node_remove_child[T: HasTreeNode[T]](this: T*, node: T*):
assert(node.tree().m_parent == this)
if this.tree().m_first_child == node:
this.tree().m_first_child = node.tree().m_next_sibling
if this.tree().m_last_child == node:
this.tree().m_last_child = node.tree().m_previous_sibling
if let next = node.tree().m_next_sibling:
next.tree().m_previous_sibling = node.tree().m_previous_sibling
if let previous = node.tree().m_previous_sibling:
previous.tree().m_next_sibling = node.tree().m_next_sibling
node.tree().m_next_sibling = none
node.tree().m_previous_sibling = none
node.tree().m_parent = none
## Ported from Libraries/LibWeb/TreeNode.h:517 Web::TreeNode::replace_child.
pub func tree_node_replace_child[T: HasTreeNode[T]](this: T*, new_child: T*, old_child: T*):
assert(old_child != new_child)
assert(old_child.tree().m_parent == this)
assert(new_child.tree().m_parent == none)
if this.tree().m_first_child == old_child:
this.tree().m_first_child = new_child
if this.tree().m_last_child == old_child:
this.tree().m_last_child = new_child
new_child.tree().m_next_sibling = old_child.tree().m_next_sibling
if let next = new_child.tree().m_next_sibling:
next.tree().m_previous_sibling = new_child
new_child.tree().m_previous_sibling = old_child.tree().m_previous_sibling
if let previous = new_child.tree().m_previous_sibling:
previous.tree().m_next_sibling = new_child
new_child.tree().m_parent = old_child.tree().m_parent
old_child.tree().m_next_sibling = none
old_child.tree().m_previous_sibling = none
old_child.tree().m_parent = none
## Ported from Libraries/LibWeb/TreeNode.h:133 Web::TreeNode::remove.
pub func tree_node_remove[T: HasTreeNode[T]](this: T*):
let parent = this.tree().m_parent else trap("VERIFY: TreeNode::remove without a parent")
tree_node_remove_child(parent, this)
# mark: Children and pre-order ==================================================================
## Ported from Libraries/LibWeb/TreeNode.h:139 Web::TreeNode::child_count.
pub func tree_node_child_count[T: HasTreeNode[T]](this: const T*) -> usize:
var count: usize = 0
var child = this.tree().m_first_child
while let at = child:
count += 1
child = at.tree().m_next_sibling
return count
## Ported from Libraries/LibWeb/TreeNode.h:147 Web::TreeNode::child_at_index.
pub func tree_node_child_at_index[T: HasTreeNode[T]](this: T*, index: usize) -> T*?:
var count: usize = 0
var child = this.tree().m_first_child
while let at = child:
if count == index:
return at
count += 1
child = at.tree().m_next_sibling
return none
## Ported from Libraries/LibWeb/TreeNode.h:158 Web::TreeNode::child_at_index.
pub func tree_node_child_at_index_const[T: HasTreeNode[T]](this: const T*, index: usize) -> const T*?:
return tree_node_child_at_index((T*)this, index)
## Ported from Libraries/LibWeb/TreeNode.h:163 Web::TreeNode::next_in_pre_order.
pub func tree_node_next_in_pre_order[T: HasTreeNode[T]](this: T*) -> T*?:
if let first = this.tree().m_first_child:
return first
var node = this.tree().m_next_sibling
if node == none:
node = this.tree().m_parent
while let at = node:
if at.tree().m_next_sibling != none:
break
node = at.tree().m_parent
if let at = node:
node = at.tree().m_next_sibling
return node
## Ported from Libraries/LibWeb/TreeNode.h:178 Web::TreeNode::next_in_pre_order.
pub func tree_node_next_in_pre_order_t[T: HasTreeNode[T]](this: T*, stay_within: const T*?) -> T*?:
if let first = this.tree().m_first_child:
return first
var node: T*? = this
while let at = node:
if stay_within == at:
return none
if let next = at.tree().m_next_sibling:
return next
node = at.tree().m_parent
return none
## Ported from Libraries/LibWeb/TreeNode.h:194 Web::TreeNode::next_in_pre_order.
pub func tree_node_next_in_pre_order_const[T: HasTreeNode[T]](this: const T*) -> const T*?:
return tree_node_next_in_pre_order((T*)this)
## Ported from Libraries/LibWeb/TreeNode.h:199 Web::TreeNode::next_in_pre_order.
pub func tree_node_next_in_pre_order_t_const[T: HasTreeNode[T]](this: const T*, stay_within: const T*?) -> const T*?:
return tree_node_next_in_pre_order_t((T*)this, stay_within)
## Ported from Libraries/LibWeb/TreeNode.h:204 Web::TreeNode::previous_in_pre_order.
pub func tree_node_previous_in_pre_order[T: HasTreeNode[T]](this: T*) -> T*?:
if let previous = this.tree().m_previous_sibling:
var node = previous
while let last = node.tree().m_last_child:
node = last
return node
return this.tree().m_parent
## Ported from Libraries/LibWeb/TreeNode.h:216 Web::TreeNode::previous_in_pre_order.
pub func tree_node_previous_in_pre_order_const[T: HasTreeNode[T]](this: const T*) -> const T*?:
return tree_node_previous_in_pre_order((T*)this)