dymokomi/luce-browser-foundation
Source of release 0.6.1
#==============================================================================================
#
# trie - Trie<ValueType, MetadataT, ValueTraits>: a tree keyed by sequences of values
#
# DESCRIPTION:
# Port of AK/Trie.h (lines 1-309). Detail::Trie (Trie2) holds a node's value, optional
# metadata and children (a HashMap from value to child, ValueTraits being the map's key
# traits); AK::Trie embeds it. The CRTP base type is dropped: the members answer
# Trie2 pointers, and a Trie is its Trie2. The donor's iterator ranges `(It& it, It
# const& end)` are a span of values with an index into it (`it` passed by pointer where
# the donor advances the caller's iterator). A missing-metadata provider is a
# Function0[M?] (ensure_child) or a Function2[Trie2*, usize, M?] (insert: the node and
# the index `it`); for_each_node_in_tree_order's callback is a
# Function1[const Trie2*, IterationDecision]. The try_clone() overloads (values that
# are cloned, not copied) do not apply: luce-base values copy.
#
#==============================================================================================
# ensure_child's default provider: `[] { return OptionalNone {}; }`.
func trie_no_metadata[M](context: void*?) -> M?:
_ = context
return none
# insert's per-level provider: `[&] { return invoke_provide_missing_metadata(*last_root_node, it); }`.
# A static method of the captures: the function type `func(void*?) -> M?` does not mention V and
# VT, and a generic function value takes its type arguments from that type only.
struct TrieProvideMetadata[V, M, VT: Traits[V]]:
var provide: Function2[Trie2[V, M, VT]*, usize, M?]
var node: Trie2[V, M, VT]*
var it: usize
static func call(context: void*?) -> M?:
let captures = (const TrieProvideMetadata[V, M, VT]*)(context else trap("Trie: no captures"))
return function2_call(&captures.provide, captures.node, captures.it)
# for_each_node_in_tree_order's traversal state: whether the node's own visit happened, and
# where the walk over its children is.
struct TrieState[V, M, VT: Traits[V]]:
var did_generate_root: bool
var it: HashTableIterator[HashMapEntry[V, Trie2[V, M, VT]*]]
var end: HashTableIterator[HashMapEntry[V, Trie2[V, M, VT]*]]
# mark: Detail::Trie ============================================================================
## Ported from AK/Trie.h:36 AK::Detail::Trie::Trie(ValueType, Optional<MetadataType>).
pub func trie2_construct[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*, value: V, metadata: M?):
this.m_value = value
this.m_metadata = trie2_metadata_cell(metadata)
# The storage of an Optional<MetadataType>: none, or a managed cell holding the metadata.
func trie2_metadata_cell[M](metadata: M?) -> M*?:
let value = metadata else return none
let cell = new M[1] --- else trap("out of memory")
cell[0] = value
return cell.data
## Ported from AK/Trie.h:43 AK::Detail::Trie::traverse_until_last_accessible_node(It&, It const&):
## follows values[*it...] down the children as far as they exist, advancing *it.
pub func trie2_traverse_until_last_accessible_node[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*, it: usize*, values: const V[]) -> Trie2[V, M, VT]*:
var node = this
while *it < values.length:
let next_it = hash_map_find_k(&node.m_children, values[*it])
let bucket = next_it.m_bucket else return node
node = bucket.storage.value
*it += 1
return node
## Ported from AK/Trie.h:56 AK::Detail::Trie::traverse_until_last_accessible_node const.
pub func trie2_traverse_until_last_accessible_node_const[V, M, VT: Traits[V]](this: const Trie2[V, M, VT]*, it: usize*, values: const V[]) -> const Trie2[V, M, VT]*:
return trie2_traverse_until_last_accessible_node((Trie2[V, M, VT]*)this, it, values)
## Ported from AK/Trie.h:59 AK::Detail::Trie::traverse_until_last_accessible_node(It const&, It const&).
pub func trie2_traverse_until_last_accessible_node_2[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*, begin: usize, values: const V[]) -> Trie2[V, M, VT]*:
var it = begin
return trie2_traverse_until_last_accessible_node(this, &it, values)
## Ported from AK/Trie.h:66 AK::Detail::Trie::traverse_until_last_accessible_node(It const&, It const&) const.
pub func trie2_traverse_until_last_accessible_node_const_2[V, M, VT: Traits[V]](this: const Trie2[V, M, VT]*, begin: usize, values: const V[]) -> const Trie2[V, M, VT]*:
var it = begin
return trie2_traverse_until_last_accessible_node((Trie2[V, M, VT]*)this, &it, values)
## Ported from AK/Trie.h:72 AK::Detail::Trie::has_metadata.
pub func trie2_has_metadata[V, M, VT: Traits[V]](this: const Trie2[V, M, VT]*) -> bool:
return this.m_metadata != none
## Ported from AK/Trie.h:74 AK::Detail::Trie::metadata.
pub func trie2_metadata[V, M, VT: Traits[V]](this: const Trie2[V, M, VT]*) -> M?:
let cell = this.m_metadata else return none
return *cell
## Ported from AK/Trie.h:79 AK::Detail::Trie::set_metadata.
pub func trie2_set_metadata[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*, metadata: M):
this.m_metadata = trie2_metadata_cell[M](metadata)
## Ported from AK/Trie.h:84 AK::Detail::Trie::metadata_value const.
pub func trie2_metadata_value_const[V, M, VT: Traits[V]](this: const Trie2[V, M, VT]*) -> M:
let cell = this.m_metadata else trap("VERIFY: Trie node without metadata")
return *cell
## Ported from AK/Trie.h:89 AK::Detail::Trie::metadata_value.
pub func trie2_metadata_value[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*) -> M*:
return this.m_metadata else trap("VERIFY: Trie node without metadata")
## Ported from AK/Trie.h:95 AK::Detail::Trie::value const.
pub func trie2_value_const[V, M, VT: Traits[V]](this: const Trie2[V, M, VT]*) -> V:
return this.m_value
## Ported from AK/Trie.h:96 AK::Detail::Trie::value.
pub func trie2_value[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*) -> V*:
return &this.m_value
## Ported from AK/Trie.h:99 AK::Detail::Trie::ensure_child: the child for `value`, made with the
## metadata `metadata_if_missing` answers when there is none.
pub func trie2_ensure_child[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*, value: V, metadata_if_missing: Function0[M?]) -> Trie2[V, M, VT]*!:
let it = hash_map_find_k(&this.m_children, value)
if let bucket = it.m_bucket:
return bucket.storage.value
let missing_metadata = function0_call(&metadata_if_missing)
let node = new Trie2[V, M, VT](m_value = value, m_metadata = trie2_metadata_cell(missing_metadata), m_children = HashMap[V, Trie2[V, M, VT]*, VT]()) catch:
return try ak_error_throw(ak_error_from_errno(enomem))
_ = try hash_map_try_set(&this.m_children, value, node)
return node
# ensure_child with the donor's default provider (no metadata).
func trie2_ensure_child_default[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*, value: V) -> Trie2[V, M, VT]*!:
let none_provider: func(void*?) -> M? = trie_no_metadata
return try trie2_ensure_child(this, value, Function0[M?](call = none_provider, context = none))
## Ported from AK/Trie.h:125 AK::Detail::Trie::insert(It&, It const&, MetadataType,
## ProvideMetadataFunction): inserts values[*it...] below the deepest existing node, the nodes it
## creates on the way getting `provide_missing_metadata(node, it)`, and sets the last node's
## metadata.
pub func trie2_insert_t_metadata_t_t_provide_metadata_function[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*, it: usize*, values: const V[], metadata: M, provide_missing_metadata: Function2[Trie2[V, M, VT]*, usize, M?]) -> Trie2[V, M, VT]*!:
var last_root_node = trie2_traverse_until_last_accessible_node(this, it, values)
let provide: func(void*?) -> M? = TrieProvideMetadata[V, M, VT].call
while *it != values.length:
var captures = TrieProvideMetadata[V, M, VT](provide = provide_missing_metadata, node = last_root_node, it = *it)
last_root_node = try trie2_ensure_child(last_root_node, values[*it], Function0[M?](call = provide, context = &captures))
*it += 1
trie2_set_metadata(last_root_node, metadata)
return last_root_node
## Ported from AK/Trie.h:147 AK::Detail::Trie::insert(It&, It const&) (no metadata).
pub func trie2_insert[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*, it: usize*, values: const V[]) -> Trie2[V, M, VT]*!:
var last_root_node = trie2_traverse_until_last_accessible_node(this, it, values)
while *it != values.length:
last_root_node = try trie2_ensure_child_default(last_root_node, values[*it])
*it += 1
return last_root_node
## Ported from AK/Trie.h:161 AK::Detail::Trie::insert(It const&, It const&, MetadataType,
## ProvideMetadataFunction).
pub func trie2_insert_t_metadata_t_t_provide_metadata_function_2[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*, begin: usize, values: const V[], metadata: M, provide_missing_metadata: Function2[Trie2[V, M, VT]*, usize, M?]) -> Trie2[V, M, VT]*!:
var it = begin
return try trie2_insert_t_metadata_t_t_provide_metadata_function(this, &it, values, metadata, provide_missing_metadata)
## Ported from AK/Trie.h:170 AK::Detail::Trie::insert(It const&, It const&) (no metadata).
pub func trie2_insert_2[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*, begin: usize, values: const V[]) -> Trie2[V, M, VT]*!:
var it = begin
return try trie2_insert(this, &it, values)
## Ported from AK/Trie.h:177 AK::Detail::Trie::children.
pub func trie2_children[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*) -> HashMap[V, Trie2[V, M, VT]*, VT]*:
return &this.m_children
## Ported from AK/Trie.h:178 AK::Detail::Trie::children const.
pub func trie2_children_const[V, M, VT: Traits[V]](this: const Trie2[V, M, VT]*) -> const HashMap[V, Trie2[V, M, VT]*, VT]*:
return &this.m_children
## Ported from AK/Trie.h:181 AK::Detail::Trie::for_each_node_in_tree_order: visits this node and
## then each subtree in the children map's order, until the callback answers Break.
pub func trie2_for_each_node_in_tree_order[V, M, VT: Traits[V]](this: const Trie2[V, M, VT]*, callback: Function1[const Trie2[V, M, VT]*, IterationDecision]) -> !:
var state: Vector[TrieState[V, M, VT]]
try vector_try_append_t(&state, TrieState[V, M, VT](did_generate_root = false, it = hash_map_begin_const(&this.m_children), end = hash_map_end_const(&this.m_children)))
var current_node: const Trie2[V, M, VT]*? = this
while let node = current_node:
if function1_call(&callback, node) == IterationDecision.break_:
break
try trie2_skip_to_next_iterator(&state, ¤t_node)
## Ported from AK/Trie.h:213 AK::Detail::Trie::is_empty.
pub func trie2_is_empty[V, M, VT: Traits[V]](this: const Trie2[V, M, VT]*) -> bool:
return hash_map_is_empty(&this.m_children)
## Ported from AK/Trie.h:214 AK::Detail::Trie::clear.
pub func trie2_clear[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*):
hash_map_clear(&this.m_children)
## Ported from AK/Trie.h:216 AK::Detail::Trie::deep_copy.
pub func trie2_deep_copy[V, M, VT: Traits[V]](this: Trie2[V, M, VT]*) -> Trie2[V, M, VT]!:
var root = Trie2[V, M, VT](m_value = this.m_value, m_metadata = trie2_metadata_cell(try trie2_copy_metadata[V, M, VT](trie2_metadata(this))), m_children = HashMap[V, Trie2[V, M, VT]*, VT]())
for it in hash_map_begin(&this.m_children):
let copy = try trie2_deep_copy(it.value)
let cell = new Trie2[V, M, VT][1] --- catch:
return try ak_error_throw(ak_error_from_errno(enomem))
cell[0] = copy
let child = cell.data
_ = try hash_map_try_set(&root.m_children, it.key, child)
return root
## Ported from AK/Trie.h:234 AK::Detail::Trie::copy_metadata.
pub func trie2_copy_metadata[V, M, VT: Traits[V]](metadata: M?) -> M?!:
let value = metadata else return none
return value
## Ported from AK/Trie.h:245 AK::Detail::Trie::skip_to_next_iterator.
pub func trie2_skip_to_next_iterator[V, M, VT: Traits[V]](state: Vector[TrieState[V, M, VT]]*, current_node: (const Trie2[V, M, VT]*?)*) -> !:
let current_state = vector_last(state)
if current_state.did_generate_root:
hash_table_iterator_inc(¤t_state.it)
else:
current_state.did_generate_root = true
if hash_table_iterator_eq(¤t_state.it, current_state.end):
return try trie2_pop_and_get_next_iterator(state, current_node)
let child = hash_table_iterator_deref(¤t_state.it).value
*current_node = child
try vector_try_append_t(state, TrieState[V, M, VT](did_generate_root = false, it = hash_map_begin_const(&child.m_children), end = hash_map_end_const(&child.m_children)))
## Ported from AK/Trie.h:262 AK::Detail::Trie::pop_and_get_next_iterator.
pub func trie2_pop_and_get_next_iterator[V, M, VT: Traits[V]](state: Vector[TrieState[V, M, VT]]*, current_node: (const Trie2[V, M, VT]*?)*) -> !:
_ = vector_take_last(state)
if vector_is_empty(state):
*current_node = none
return
return try trie2_skip_to_next_iterator(state, current_node)
# mark: AK::Trie ================================================================================
## Ported from AK/Trie.h:293 AK::Trie::Trie(ValueType, MetadataType).
pub func trie_construct_opaque[V, M, VT: Traits[V]](this: Trie[V, M, VT]*, value: V, metadata: M):
trie2_construct(&this.base, value, metadata)
## Ported from AK/Trie.h:299 AK::Trie::Trie(ValueType).
pub func trie_construct[V, M, VT: Traits[V]](this: Trie[V, M, VT]*, value: V):
trie2_construct[V, M, VT](&this.base, value, none)