Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-engine

Source of release 0.6.0

0.6.0 / src / web / tests_tree_node.lucb

#==============================================================================================
#
#   tests_tree_node - TreeNode<T>: links, mutation, pre-order and the typed traversals
#
#   DESCRIPTION:
#       The donor has no unit test for TreeNode.h (its behaviour is covered by the DOM and
#       layout tests); these pin the C++ results on a small tree of test cells:
#
#           root
#           ├── a          (class "even")
#           │   ├── a1
#           │   └── a2     (class "even")
#           ├── b
#           └── c          (class "even")
#               └── c1
#
#==============================================================================================

# mark: The test cell ===========================================================================

## A cell class with a TreeNode, as DOM::Node and Layout::Node are.
struct TestTreeItem: gc.IsCell, HasTreeNode[TestTreeItem], TreeNodePrependHooks[TestTreeItem]:
    var cell_base: gc.Cell
    var tree_node: TreeNode[TestTreeItem]
    var name: u8
    var inserted_into_count: i32
    var children_changed_count: i32

    func cell() -> gc.Cell*: return (gc.Cell*)&self

    func tree() -> TreeNode[TestTreeItem]*: return (TreeNode[TestTreeItem]*)&self.tree_node

    func inserted_into(parent: TestTreeItem*):
        let this = (TestTreeItem*)&self
        assert(this.tree().m_parent == parent)
        this.inserted_into_count += 1

    func children_changed():
        let this = (TestTreeItem*)&self
        this.children_changed_count += 1

## The class of the test cells: ids 1 (odd) to 2 (even); "even" is the subclass with id 2.
let test_tree_item_class: ak.ClassInfo = ak.ClassInfo(name = "TestTreeItem", first_id = 1, last_id = 2, size = memory.size_of(TestTreeItem), vtable = (const void*)&test_tree_item_vtable)
let test_tree_item_even_class: ak.ClassInfo = ak.ClassInfo(name = "TestTreeItemEven", first_id = 2, last_id = 2, size = memory.size_of(TestTreeItem), vtable = (const void*)&test_tree_item_vtable)
let test_tree_item_vtable: gc.CellVTable = gc.CellVTable(class_info = &test_tree_item_class)

func test_tree_item(name: u8, even: bool) -> TestTreeItem*:
    let item = new TestTreeItem(cell_base = gc.Cell(vtable = &test_tree_item_vtable, class_id = 2 if even else 1), name = name) else trap("out of memory")
    return item

## The test tree of the header, its nodes in tree order.
struct TestTree:
    var root: TestTreeItem*
    var a: TestTreeItem*
    var a1: TestTreeItem*
    var a2: TestTreeItem*
    var b: TestTreeItem*
    var c: TestTreeItem*
    var c1: TestTreeItem*

func test_tree() -> TestTree:
    let tree = TestTree(root = test_tree_item('R', false), a = test_tree_item('a', true), a1 = test_tree_item('1', false),
                        a2 = test_tree_item('2', true), b = test_tree_item('b', false), c = test_tree_item('c', true),
                        c1 = test_tree_item('3', false))
    tree_node_append_child(tree.root, tree.a)
    tree_node_append_child(tree.root, tree.b)
    tree_node_append_child(tree.root, tree.c)
    tree_node_append_child(tree.a, tree.a1)
    tree_node_append_child(tree.a, tree.a2)
    tree_node_append_child(tree.c, tree.c1)
    return tree

## The names of the children of `parent`, first to last.
func test_tree_children(parent: TestTreeItem*, out: u8[]) -> usize:
    var count: usize = 0
    var child = tree_node_first_child(parent)
    while let at = child:
        out[count] = at.name
        count += 1
        child = tree_node_next_sibling(at)
    return count

## A traversal callback that records the names it visits, skipping the children of `skip` and
## stopping at `stop`.
struct TestTreeRecorder: TraversalCallback[TestTreeItem]:
    var names: u8[16]
    var count: usize
    var skip: u8
    var stop: u8

    func call(node: TestTreeItem*) -> TraversalDecision:
        self.names[self.count] = node.name
        self.count += 1
        if node.name == self.stop: return TraversalDecision.break_
        if node.name == self.skip: return TraversalDecision.skip_children_and_continue
        return TraversalDecision.continue_

    func recorded() -> str:
        return (str)self.names[0..<self.count]

## An iteration callback that records names and breaks at `stop`.
struct TestTreeIterationRecorder: IterationCallback[TestTreeItem]:
    var names: u8[16]
    var count: usize
    var stop: u8

    func call(node: TestTreeItem*) -> ak.IterationDecision:
        self.names[self.count] = node.name
        self.count += 1
        if node.name == self.stop: return ak.IterationDecision.break_
        return ak.IterationDecision.continue_

    func recorded() -> str:
        return (str)self.names[0..<self.count]

# mark: Tests ===================================================================================

test "TreeNode: append_child links parents and siblings":
    let tree = test_tree()
    var names: u8[8]
    let count = test_tree_children(tree.root, names)
    assert((str)names[0..<count] == "abc")
    assert(tree_node_parent(tree.a1) == tree.a)
    assert(tree_node_first_child(tree.root) == tree.a)
    assert(tree_node_last_child(tree.root) == tree.c)
    assert(tree_node_previous_sibling(tree.c) == tree.b)
    assert(tree_node_previous_sibling(tree.a) == none)
    assert(tree_node_next_sibling(tree.c) == none)
    assert(tree_node_has_children(tree.a))
    assert(not tree_node_has_children(tree.b))
    assert(tree_node_child_count(tree.root) == 3)
    assert(tree_node_child_count(tree.b) == 0)
    assert(tree_node_index(tree.root) == 0)
    assert(tree_node_index(tree.c) == 2)
    assert(tree_node_child_at_index(tree.root, 1) == tree.b)
    assert(tree_node_child_at_index(tree.root, 3) == none)
    assert(tree_node_root(tree.c1) == tree.root)
    assert(tree_node_root_const(tree.root) == tree.root)

test "TreeNode: ancestry, contains and tree order":
    let tree = test_tree()
    assert(tree_node_is_ancestor_of(tree.root, tree.a2))
    assert(not tree_node_is_ancestor_of(tree.a2, tree.a2))
    assert(tree_node_is_inclusive_ancestor_of(tree.a2, tree.a2))
    assert(not tree_node_is_ancestor_of(tree.a, tree.c1))
    assert(tree_node_is_descendant_of(tree.c1, tree.c))
    assert(tree_node_is_inclusive_descendant_of(tree.c, tree.c))
    assert(tree_node_contains(tree.root, tree.c1))
    assert(not tree_node_contains(tree.b, tree.c1))
    assert(not tree_node_contains(tree.b, none))
    assert(tree_node_is_parent_of(tree.a, tree.a2))
    assert(not tree_node_is_parent_of(tree.root, tree.a2))
    # is_following: this comes after other in tree order.
    assert(tree_node_is_following(tree.c1, tree.a2))
    assert(not tree_node_is_following(tree.a2, tree.c1))
    assert(not tree_node_is_following(tree.b, tree.b))
    # is_before: this comes before other.
    assert(tree_node_is_before(tree.a1, tree.b))
    assert(not tree_node_is_before(tree.b, tree.a1))
    assert(not tree_node_is_before(tree.b, tree.b))

test "TreeNode: next_in_pre_order and previous_in_pre_order":
    let tree = test_tree()
    var names: u8[8]
    var count: usize = 0
    var node: TestTreeItem*? = tree.root
    while let at = node:
        names[count] = at.name
        count += 1
        node = tree_node_next_in_pre_order(at)
    assert((str)names[0..<count] == "Ra12bc3")

    count = 0
    node = tree.c1
    while let at = node:
        names[count] = at.name
        count += 1
        node = tree_node_previous_in_pre_order(at)
    assert((str)names[0..<count] == "3cb21aR")

    # stay_within ends the walk at the last node of the subtree.
    assert(tree_node_next_in_pre_order_t(tree.a, tree.a) == tree.a1)
    assert(tree_node_next_in_pre_order_t(tree.a2, tree.a) == none)
    assert(tree_node_next_in_pre_order_t(tree.a2, tree.root) == tree.b)
    assert(tree_node_next_in_pre_order_t_const(tree.c1, none) == none)

test "TreeNode: insert_before, prepend_child, remove_child, replace_child":
    let tree = test_tree()
    var names: u8[8]
    let d = test_tree_item('d', false)
    tree_node_insert_before(tree.root, d, tree.b)
    var count = test_tree_children(tree.root, names)
    assert((str)names[0..<count] == "adbc")
    assert(tree_node_parent(d) == tree.root)

    let e = test_tree_item('e', false)
    tree_node_insert_before(tree.root, e, none)
    count = test_tree_children(tree.root, names)
    assert((str)names[0..<count] == "adbce")

    let f = test_tree_item('f', false)
    tree_node_prepend_child(tree.root, f)
    count = test_tree_children(tree.root, names)
    assert((str)names[0..<count] == "fadbce")
    assert(f.inserted_into_count == 1)
    assert(tree.root.children_changed_count == 1)

    tree_node_remove_child(tree.root, d)
    tree_node_remove(e)
    count = test_tree_children(tree.root, names)
    assert((str)names[0..<count] == "fabc")
    assert(tree_node_parent(d) == none and tree_node_next_sibling(d) == none)
    assert(tree_node_last_child(tree.root) == tree.c)

    tree_node_replace_child(tree.root, d, tree.b)
    count = test_tree_children(tree.root, names)
    assert((str)names[0..<count] == "fadc")
    assert(tree_node_parent(tree.b) == none)
    tree_node_replace_child(tree.root, e, f)
    count = test_tree_children(tree.root, names)
    assert((str)names[0..<count] == "eadc")
    assert(tree_node_first_child(tree.root) == e)

test "TreeNode: traversals skip children and break":
    let tree = test_tree()
    var all = TestTreeRecorder()
    assert(tree_node_for_each_in_inclusive_subtree(tree.root, &all) == TraversalDecision.continue_)
    assert(all.recorded() == "Ra12bc3")

    var skipping = TestTreeRecorder(skip = 'a')
    assert(tree_node_for_each_in_inclusive_subtree(tree.root, &skipping) == TraversalDecision.continue_)
    assert(skipping.recorded() == "Rabc3")

    var stopping = TestTreeRecorder(stop = 'b')
    assert(tree_node_for_each_in_inclusive_subtree(tree.root, &stopping) == TraversalDecision.break_)
    assert(stopping.recorded() == "Ra12b")

    var subtree = TestTreeRecorder()
    assert(tree_node_for_each_in_subtree(tree.root, &subtree) == TraversalDecision.continue_)
    assert(subtree.recorded() == "a12bc3")

    # A traversal of a subtree stays in it.
    var inner = TestTreeRecorder()
    _ = tree_node_for_each_in_inclusive_subtree_const(tree.a, &inner)
    assert(inner.recorded() == "a12")

    var evens = TestTreeRecorder()
    _ = tree_node_for_each_in_subtree_of_type(tree.root, &test_tree_item_even_class, &evens)
    assert(evens.recorded() == "a2c")

    var inclusive_evens = TestTreeRecorder(stop = '2')
    assert(tree_node_for_each_in_inclusive_subtree_of_type(tree.a, &test_tree_item_even_class, &inclusive_evens) == TraversalDecision.break_)
    assert(inclusive_evens.recorded() == "a2")

test "TreeNode: children, siblings and ancestors of a type":
    let tree = test_tree()
    assert(tree_node_first_child_of_type(tree.root, &test_tree_item_even_class) == tree.a)
    assert(tree_node_last_child_of_type(tree.root, &test_tree_item_even_class) == tree.c)
    assert(tree_node_first_child_of_type(tree.c, &test_tree_item_even_class) == none)
    assert(tree_node_has_child_of_type(tree.a, &test_tree_item_even_class))
    assert(not tree_node_has_child_of_type(tree.c, &test_tree_item_even_class))
    assert(tree_node_next_sibling_of_type(tree.a, &test_tree_item_even_class) == tree.c)
    assert(tree_node_previous_sibling_of_type(tree.c, &test_tree_item_even_class) == tree.a)
    assert(tree_node_previous_sibling_of_type(tree.a, &test_tree_item_even_class) == none)
    assert(tree_node_first_ancestor_of_type(tree.c1, &test_tree_item_even_class) == tree.c)
    assert(tree_node_first_ancestor_of_type(tree.c, &test_tree_item_even_class) == none)
    assert(tree_node_has_preceding_node_of_type_in_tree_order(tree.b, &test_tree_item_even_class))
    assert(not tree_node_has_preceding_node_of_type_in_tree_order(tree.a, &test_tree_item_even_class))
    assert(tree_node_has_following_node_of_type_in_tree_order(tree.b, &test_tree_item_even_class))
    assert(not tree_node_has_following_node_of_type_in_tree_order(tree.c, &test_tree_item_even_class))

    var children = TestTreeIterationRecorder()
    tree_node_for_each_child(tree.root, &children)
    assert(children.recorded() == "abc")
    var first_two = TestTreeIterationRecorder(stop = 'b')
    tree_node_for_each_child_const(tree.root, &first_two)
    assert(first_two.recorded() == "ab")
    var even_children = TestTreeIterationRecorder()
    tree_node_for_each_child_of_type(tree.root, &test_tree_item_even_class, &even_children)
    assert(even_children.recorded() == "ac")

    var ancestors = TestTreeIterationRecorder()
    tree_node_for_each_ancestor(tree.a2, &ancestors)
    assert(ancestors.recorded() == "aR")
    var inclusive_ancestors = TestTreeIterationRecorder(stop = 'a')
    tree_node_for_each_inclusive_ancestor(tree.a2, &inclusive_ancestors)
    assert(inclusive_ancestors.recorded() == "2a")
    var even_ancestors = TestTreeIterationRecorder()
    tree_node_for_each_inclusive_ancestor_of_type(tree.a2, &test_tree_item_even_class, &even_ancestors)
    assert(even_ancestors.recorded() == "2a")