Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-html

Source of release 0.5.1

0.5.1 / tools / gen_entities / dafsa.lucb

#==============================================================================================
#
#   dafsa - the DAFSA of the named character references and its numbering
#
#   DESCRIPTION:
#       Port of the Node and DafsaBuilder classes and the node-data functions of
#       generate_libweb_html_named_character_references.py. From the Python script's header:
#
#       First, a deterministic acyclic finite state automaton (DAFSA) is constructed from the
#       set of named character references. The nodes in the DAFSA are populated with a
#       "number" field that represents the count of all possible valid words from that node.
#       This "number" field allows for minimal perfect hashing, where each word in the set
#       corresponds to a unique index. The unique index of a word in the set is calculated
#       during traversal/search of the DAFSA:
#       - For any non-matching node that is iterated when searching a list of children, add
#         their number to the unique index
#       - For nodes that match the current character, if the node is a valid end-of-word, add
#         1 to the unique index
#
#       The 'first layer' of nodes is extracted into a lookup table and the 'second layer' is
#       searched with a 52-bit mask per first character (see emit.lucb); after the second
#       layer, the "number" of each child is cumulative over its previous siblings and each
#       node stores the length of its list of children.
#
#       The Python dicts keyed by node identity become fields of the node: `child_index` is
#       `child_indexes[id(node)]`, and the minimized-node dict is an open-addressing table.
#
#==============================================================================================

# mark: Nodes ===================================================================================

## A DAFSA node: a child per ASCII character.
struct Node:
    var children: (Node*?)[128]
    var is_terminal: bool
    var number: usize
    ## child_indexes[id(node)], when the node has an entry.
    var child_index: usize?

func node_num_direct_children(node: const Node*) -> usize:
    var count: usize = 0
    for child in node.children:
        if child != none:
            count += 1
    return count

func is_ascii_alpha(c_: usize) -> bool:
    return (0x41 <= c_ and c_ <= 0x5A) or (0x61 <= c_ and c_ <= 0x7A)

func ascii_alphabetic_to_index(c_: usize) -> usize:
    assert(is_ascii_alpha(c_))
    return (c_ - 0x41) if c_ <= 0x5A else (c_ - 0x61 + 26)

func node_get_ascii_alphabetic_bit_mask(node: const Node*) -> u64:
    var mask: u64 = 0
    for (i, child) in node.children.indexed():
        if child == none:
            continue
        mask = mask | ((u64)1 << ascii_alphabetic_to_index(i))
    return mask

func calc_numbers(node: Node*):
    node.number = 1 if node.is_terminal else 0
    for child in node.children:
        if let c_ = child:
            calc_numbers(c_)
            node.number += c_.number

# node_key(n): equality matches the C++ NodeTraits: identity of each child slot + terminal flag.
func node_keys_equal(a: const Node*, b: const Node*) -> bool:
    if a.is_terminal != b.is_terminal:
        return false
    for i: usize in 0..<128:
        if a.children[i] != b.children[i]:
            return false
    return true

func node_key_hash(node: const Node*) -> u64:
    var h: u64 = 0xcbf29ce484222325 if node.is_terminal else 0x84222325cbf29ce4
    for child in node.children:
        var word: u64 = 0
        if let c_ = child:
            word = (u64)(usize)c_
        h = (h ^ word) *% 0x100000001b3
    return h

# mark: DafsaBuilder ============================================================================

## (parent, character_index, child) of the words still being minimized.
struct UncheckedNode:
    var parent: Node*
    var character_index: usize
    var child: Node*

let minimized_table_size: usize = 16384

## The DAFSA under construction.
struct DafsaBuilder:
    var root: Node*
    ## minimized_nodes: node_key -> Node, open addressing by node_key_hash.
    var minimized_nodes: (Node*?)[]
    var unchecked_nodes: UncheckedNode[]
    var unchecked_count: usize
    var previous_word: str

func dafsa_builder_create() -> DafsaBuilder!:
    return DafsaBuilder(root = try new Node, minimized_nodes = try new (Node*?)[minimized_table_size],
                        unchecked_nodes = try new UncheckedNode[64] ---, unchecked_count = 0, previous_word = "")

func dafsa_builder_insert(this: DafsaBuilder*, s: str) -> !:
    if not (s > this.previous_word):
        error(invalid_entities, "insertion order: the names of Entities.json are not sorted")

    var common_prefix_len: usize = 0
    let minimum = s.length if s.length < this.previous_word.length else this.previous_word.length
    for i in 0..<minimum:
        if s.bytes[i] != this.previous_word.bytes[i]:
            break
        common_prefix_len += 1

    dafsa_builder_minimize(this, common_prefix_len)

    var node = this.root
    if this.unchecked_count > 0:
        node = this.unchecked_nodes[this.unchecked_count - 1].child

    for ch in s.bytes[common_prefix_len..]:
        let c_ = (usize)ch
        assert(node.children[c_] == none)
        let child = try new Node
        node.children[c_] = child
        if this.unchecked_count == this.unchecked_nodes.length:
            error(invalid_entities, "a name is too long")
        this.unchecked_nodes[this.unchecked_count] = UncheckedNode(parent = node, character_index = c_, child = child)
        this.unchecked_count += 1
        node = child
    node.is_terminal = true

    this.previous_word = s

func dafsa_builder_minimize(this: DafsaBuilder*, down_to: usize):
    if this.unchecked_count == 0:
        return
    while this.unchecked_count > down_to:
        this.unchecked_count -= 1
        let unchecked = this.unchecked_nodes[this.unchecked_count]
        # existing = self.minimized_nodes.get(node_key(child))
        var slot = (usize)(node_key_hash(unchecked.child) % (u64)minimized_table_size)
        var existing: Node*? = none
        while let candidate = this.minimized_nodes[slot]:
            if node_keys_equal(candidate, unchecked.child):
                existing = candidate
                break
            slot = (slot + 1) % minimized_table_size
        if let node = existing:
            unchecked.parent.children[unchecked.character_index] = node
        else:
            this.minimized_nodes[slot] = unchecked.child

func dafsa_builder_calc_numbers(this: DafsaBuilder*):
    calc_numbers(this.root)

func dafsa_builder_get_unique_index(this: const DafsaBuilder*, s: str) -> usize?:
    var index: usize = 0
    var node = this.root
    for ch in s.bytes:
        let c_ = (usize)ch
        let next = node.children[c_] else return none
        for sibling_c: usize in 0..<128:
            if let sibling = node.children[sibling_c]:
                if sibling_c < c_:
                    index += sibling.number
        node = next
        if node.is_terminal:
            index += 1
    return index

# mark: Node data ===============================================================================

## One row of g_named_character_reference_nodes: (character, number, end_of_word,
## child_index, children_len).
struct NodeData:
    var character: usize
    var number: usize
    var end_of_word: bool
    var child_index: usize
    var children_len: usize

## The Python generator's `queue` list and the `node_data` list it fills.
struct NodeQueue:
    var nodes: Node*[]
    var length: usize
    var head: usize

func node_queue_append(queue: NodeQueue*, node: Node*) -> !:
    if queue.length == queue.nodes.length:
        error(invalid_entities, "the node queue is full")
    queue.nodes[queue.length] = node
    queue.length += 1

func queue_children(node: Node*, queue: NodeQueue*, first_available_index: usize) -> usize!:
    var current_available_index = first_available_index
    for child in node.children:
        let c_ = child else continue
        if c_.child_index == none:
            let child_num_children = node_num_direct_children(c_)
            if child_num_children > 0:
                c_.child_index = current_available_index
                current_available_index += child_num_children
            try node_queue_append(queue, c_)
    return current_available_index

func write_children_data(node: Node*, node_data: NodeData[], node_data_count: usize*, queue: NodeQueue*, first_available_index: usize) -> usize!:
    var current_available_index = first_available_index
    var unique_index_tally: usize = 0
    for (c_, child) in node.children.indexed():
        let child_node = child else continue
        let child_num_children = node_num_direct_children(child_node)

        if child_node.child_index == none:
            if child_num_children > 0:
                child_node.child_index = current_available_index
                current_available_index += child_num_children
            try node_queue_append(queue, child_node)

        if *node_data_count == node_data.length:
            error(invalid_entities, "too many DAFSA nodes")
        node_data[*node_data_count] = NodeData(character = c_, number = unique_index_tally, end_of_word = child_node.is_terminal,
                                               child_index = child_node.child_index else 0, children_len = child_num_children)
        *node_data_count += 1

        unique_index_tally += child_node.number
    return current_available_index

## The rows of g_named_character_reference_nodes after the unused node 0; the second layer's
## child indexes are left in the nodes.
func write_node_data(dafsa_builder: DafsaBuilder*) -> NodeData[]!:
    var queue = NodeQueue(nodes = try new Node*[1 << 16] ---, length = 0, head = 0)
    var node_data = try new NodeData[1 << 14] ---
    var node_data_count: usize = 0

    var first_available_index: usize = 1
    first_available_index = try queue_children(dafsa_builder.root, &queue, first_available_index)

    # child_indexes.clear(): the entries so far are the first layer's.
    for i in 0..<queue.length:
        queue.nodes[i].child_index = none
    first_available_index = 1
    let second_layer_length = queue.length
    for i in 0..<second_layer_length:
        _ = i
        let node = queue.nodes[queue.head]
        queue.head += 1
        first_available_index = try queue_children(node, &queue, first_available_index)

    while queue.head < queue.length:
        let node = queue.nodes[queue.head]
        queue.head += 1
        first_available_index = try write_children_data(node, node_data, &node_data_count, &queue, first_available_index)
    return node_data[..<node_data_count]