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")