paren_repr.py

# I happened to be looking at some of Cranelift's code, and I noticed that their constant-time dominates()
# check was using a somewhat more ad-hoc version of a hidden gem from the data structures literature called the
# parenthesis representation for trees. As far as I know, this was invented by Jacobson in his 1989 paper
# Space-Efficient Static Trees and Graphs. I first learned about it from the slightly later paper by Munro and Raman
# called Succinct Representations of Balanced Parentheses and Static Trees. I figured I'd give it an extremely
# quick intro and then show how it leads to a (slightly better) version of Cranelift's algorithm.
#
# This parenthesis representation of trees is surprisingly versatile, but its most striking feature is that
# it lets us query the ancestor relationship between two nodes in a tree in constant time, with a few instructions.
# And the idea is extremely simple and intuitive if you just draw the right kind of picture.
#
# Imagine you walk a tree recursively and before recursing to your children you print an opening parenthesis and after
# recursing you print a closing parenthesis. Node X is then an ancestor of Y if the X parentheses enclose the Y parentheses.
#
#            A [0,9]
#           / \
#    [1,6] B   C [7,8]
#        /  \
# [2,3] D    E [4,5]
#
# ((()())())
# ABDDEEBCCA
#
# We don't actually print anything; that is just an aid to intuition. (In the original paper on succinct data structures,
# you do retain this kind of representation as a bit string and compute rank/select queries. And if you treat ( as +1 and ) as
# -1 then the prefix sum, which equals the (-rank minus the )-rank, will tell you the tree depth at each position.)
#
# For our simple case where we prefer query speed over space compactness, we will just increment a counter representing the
# parenthesis positions and label the nodes with that range. Then the ancestor check is a numerical range containment check:

def is_ancestor(range1, range2):
    return range1.start <= range2.start and range2.end <= range1.end

# If you look at Cranelift's code at https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/codegen/src/dominator_tree.rs#L487,
# you should be able to see that `pre` is like our `start` and `pre_max` is similar to our `end` but 1 less in value. Furthermore, it's
# computed as an actual max in a separate pass rather than just computing it on the way back up from the recursion. Their version is
# valid too; it collapses the end point of a parent and its last child (and its last child, etc), but the distinct `pre` still lets you
# distinguish a parent from its last child, etc. For the type of queries Munro and Raman do in their paper having distinct end points
# is necessary, but it doesn't help our ancestor queries. One way to conceptualize the difference is that the `pre_max` variant works
# with lower-inclusive, upper-exclusive intervals since the end point of one node's range equals the start point of the next node.
#
# They mention that one limitation of their approach is that they only order nodes (blocks), not elements (instructions) within nodes.
# Actually, you can easily support that by conservatively reserving a range to be occupied (initially or later) by elements.
# They're already doing something similar to that for their block rpo (reverse post-order) numbers in the main data structure, and it
# works just as well here. 

def walk(node, preorder_func, postorder_func):
    node.range.start = counter
    counter += 1

    # Reserve a range of values which can later be assigned to elements associated with the node.
    # These elements will then dominate later elements in this same node as well as descendant nodes
    # and any elements therein.
    counter += reservation

    # Assign an all-inclusive upper bound in case the callbacks try to query for ancestors.
    node.range.end = INT_MAX

    preorder_func(node)

    for child in node.children:
        walk(child, preorder_func, postorder_func)

    # We need to reserve space for the ending positions as well.
    counter += reservation

    node.range.end = counter
    counter += 1
    
    # If we remove these last two increments then `range.end` will correspond to Cranelift's `pre_max`.

    postorder_func(node)