Luce packages
LuceLuce BaseLuciaOS

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)