Module refinery.lib.scripts.analysis.dominance

Dominance over the per-body control-flow graphs of one script, in the graph-theoretic sense only.

One node dominates another when every path from the body's entry to the second passes through the first, so the first is guaranteed to have executed by the time the second runs. That is a statement about a graph and nothing else, which is why the whole of it lives here: a language contributes the graph, and the relation over it is the same relation for every language.

The queries are keyed to AST nodes rather than to graph nodes, because that is what every caller holds. An element the graph does not represent on its own — an expression inside a statement — resolves to the node of the statement that evaluates it, which is the granularity the graph reasons at. Two elements in different bodies' graphs are not ordered here at all: whether one body runs before another is a question about calls, and a language answers it with the layer it builds on this one.

Exceptional edges take part in the computation like any other edge. A definition is therefore reported as dominating a use only when it runs first on every path, including the ones that leave a guarded block by throwing, which is the conservative direction and the one a caller may rely on.

A node no path from the entry reaches is dominated by nothing and dominates nothing, itself included. Dominance quantifies over the paths from the entry, and an unreachable node lies on none of them, so every answer about one is vacuous. Reporting it as dominating itself would let a region the program cannot enter order code that it can, and — worse — a reachable join one of whose predecessors is unreachable would inherit that predecessor's answer and lose the dominators it really has. Obfuscated scripts are full of the tail after a return or a throw, so this is the ordinary case rather than the exotic one.

Dominance orders, it does not certify. That a definition dominates a use says the statement holding it ran, not that the store it performs completed: a statement may throw part-way through, and refinery.lib.scripts.analysis.liveness states the same asymmetry as the reason its transfer function is not the textbook one. A caller reading dominance as evidence a value was established needs the extra refusal, which refinery.lib.scripts.analysis.reaching makes.

"""
Dominance over the per-body control-flow graphs of one script, in the graph-theoretic sense only.

One node *dominates* another when every path from the body's entry to the second passes through the
first, so the first is guaranteed to have executed by the time the second runs. That is a statement
about a graph and nothing else, which is why the whole of it lives here: a language contributes the
graph, and the relation over it is the same relation for every language.

The queries are keyed to AST nodes rather than to graph nodes, because that is what every caller
holds. An element the graph does not represent on its own — an expression inside a statement —
resolves to the node of the statement that evaluates it, which is the granularity the graph reasons
at. Two elements in different bodies' graphs are not ordered here at all: whether one body runs
before another is a question about calls, and a language answers it with the layer it builds on this
one.

Exceptional edges take part in the computation like any other edge. A definition is therefore
reported as dominating a use only when it runs first on *every* path, including the ones that leave a
guarded block by throwing, which is the conservative direction and the one a caller may rely on.

**A node no path from the entry reaches is dominated by nothing and dominates nothing**, itself
included. Dominance quantifies over the paths from the entry, and an unreachable node lies on none of
them, so every answer about one is vacuous. Reporting it as dominating itself would let a region the
program cannot enter order code that it can, and — worse — a *reachable* join one of whose
predecessors is unreachable would inherit that predecessor's answer and lose the dominators it really
has. Obfuscated scripts are full of the tail after a `return` or a `throw`, so this is the ordinary
case rather than the exotic one.

**Dominance orders, it does not certify.** That a definition dominates a use says the statement
holding it ran, not that the store it performs completed: a statement may throw part-way through, and
`refinery.lib.scripts.analysis.liveness` states the same asymmetry as the reason its transfer function
is not the textbook one. A caller reading dominance as evidence a value was established needs the
extra refusal, which `refinery.lib.scripts.analysis.reaching` makes.
"""
from __future__ import annotations

from typing import AbstractSet as Set
from typing import Iterator

from refinery.lib.scripts import Node
from refinery.lib.scripts.analysis.cfg import (
    CfgNode,
    ControlFlowGraph,
    ControlFlowModel,
    Projection,
    flood,
)


def _immediate_dominators(
    graph: ControlFlowGraph, projection: Projection,
) -> tuple[dict[int, int], list[CfgNode]]:
    """
    The immediate dominator of every node the entry reaches under *projection*, keyed by node
    identity, with the entry seeded as its own — the conventional answer, and what marks it as the
    root for `_dominance_intervals` — and the reached nodes themselves, in the depth-first preorder
    the computation numbers them in. A node no walk from the entry reaches is in neither, which is
    what the module docstring requires.

    Lengauer and Tarjan's algorithm with path compression: number the nodes in depth-first preorder,
    find each node's semidominator by evaluating its predecessors over a forest that grows in
    reverse preorder, and settle the immediate dominator from the semidominators in one forward
    pass. Its cost depends on the edges, not on the order a walk happens to meet the nodes in, which
    is what an iterative intersection cannot promise: a resuming `trap` adds a hub with an edge to
    every statement of its block, a walk meets that hub late, and the intersection then climbs from
    every later predecessor back to the top of the script — the square of the block.
    """
    number: dict[int, int] = {id(graph.entry): 0}
    vertex: list[CfgNode] = [graph.entry]
    parent: list[int] = [0]
    stack: list[tuple[CfgNode, Iterator[CfgNode]]] = [
        (graph.entry, iter(projection.successors(graph.entry)))
    ]
    while stack:
        node, successors = stack[-1]
        for successor in successors:
            if id(successor) in number:
                continue
            number[id(successor)] = len(vertex)
            parent.append(number[id(node)])
            vertex.append(successor)
            stack.append((successor, iter(projection.successors(successor))))
            break
        else:
            stack.pop()
    count = len(vertex)
    semi = list(range(count))
    label = list(range(count))
    ancestor = [-1] * count
    idom = [0] * count
    bucket: list[list[int]] = [[] for _ in range(count)]

    def evaluate(v: int) -> int:
        if ancestor[v] < 0:
            return v
        chain: list[int] = []
        x = v
        while ancestor[ancestor[x]] >= 0:
            chain.append(x)
            x = ancestor[x]
        for x in reversed(chain):
            above = ancestor[x]
            if semi[label[above]] < semi[label[x]]:
                label[x] = label[above]
            ancestor[x] = ancestor[above]
        return label[v]

    for w in range(count - 1, 0, -1):
        for predecessor in projection.predecessors(vertex[w]):
            v = number.get(id(predecessor))
            if v is None:
                continue
            u = evaluate(v)
            if semi[u] < semi[w]:
                semi[w] = semi[u]
        bucket[semi[w]].append(w)
        p = parent[w]
        ancestor[w] = p
        for v in bucket[p]:
            u = evaluate(v)
            idom[v] = u if semi[u] < semi[v] else p
        bucket[p].clear()
    for w in range(1, count):
        if idom[w] != semi[w]:
            idom[w] = idom[idom[w]]
    return {id(vertex[w]): id(vertex[idom[w]]) for w in range(count)}, vertex


def _dominance_intervals(
    idom: dict[int, int], graph: ControlFlowGraph, order: list[CfgNode],
) -> tuple[dict[int, int], dict[int, int]]:
    """
    Entry and exit stamps from a depth-first walk of the immediate-dominator tree, keyed by node
    identity. A node's descendants in that tree are exactly the nodes it dominates, and a depth-first
    walk visits a subtree contiguously, so *dominates* becomes the test that one stamp lies inside
    another's half-open interval.

    Iterative, because the tree of a straight-line body is a chain as long as the body.
    """
    root = id(graph.entry)
    children: dict[int, list[int]] = {id(node): [] for node in order}
    for node in order:
        key = id(node)
        if key != root:
            children[idom[key]].append(key)
    entered: dict[int, int] = {root: 0}
    left: dict[int, int] = {}
    clock = 1
    stack: list[tuple[int, Iterator[int]]] = [(root, iter(children[root]))]
    while stack:
        key, remaining = stack[-1]
        for child in remaining:
            entered[child] = clock
            clock += 1
            stack.append((child, iter(children[child])))
            break
        else:
            left[key] = clock
            stack.pop()
    return entered, left


class DominanceTree:
    """
    The dominator relation of one control-flow graph, held as the *immediate*-dominator tree with a
    depth-first numbering over it.

    A node's dominators are the path from it to the root of that tree, so the tree carries the whole
    relation in space linear in the body where a set per node is quadratic in it: one straight-line
    body of five thousand statements costs twelve million set entries as sets and five thousand
    parent links as a tree. The numbering then answers `dominates` with two comparisons rather than a
    set lookup, which matters because the callers above ask it hundreds of thousands of times per
    script.

    Only the nodes the entry reaches are in the tree. That is not an optimisation but the relation:
    see the module docstring on why an unreachable node dominates nothing.
    """

    def __init__(self, graph: ControlFlowGraph, projection: Projection):
        self.idom, order = _immediate_dominators(graph, projection)
        self._entered, self._left = _dominance_intervals(self.idom, graph, order)

    @property
    def reached(self) -> Set[int]:
        """
        The ids of the nodes the entry reaches under the projection this tree was built with, which
        is exactly the set the tree holds: a node the entry does not reach is not in it at all.

        Read rather than flooded again. A caller asking which statements of a body can run is asking
        the question the tree already had to answer to exist, and a flood per body per pass over a
        script whose bodies share one graph is the same walk repeated.
        """
        return self._entered.keys()

    def dominates(self, a: CfgNode, b: CfgNode) -> bool:
        """
        Whether *a* dominates *b*. Reflexive for a reachable node; `False` whenever either node is
        unreachable, the two being one unreachable node included.
        """
        opened = self._entered.get(id(a))
        if opened is None:
            return False
        reached = self._entered.get(id(b))
        return reached is not None and opened <= reached < self._left[id(a)]


class DominatorModel:
    """
    Dominator relations for the per-body control-flow graphs of one script. A graph's dominance tree
    is computed once, on the first ordering question asked about that graph, and kept for as long as
    this model lives.

    Computing them all on construction instead would charge every caller for the whole script when
    most callers ask about one body, and the model is rebuilt from scratch whenever the tree version
    advances. This is the same laziness `refinery.lib.scripts.analysis.cycles.CycleModel` has, for the
    same reason.
    """

    def __init__(self, flow: ControlFlowModel):
        self._flow = flow
        self._trees: dict[tuple[int, Projection], DominanceTree] = {}
        self._reached: dict[tuple[int, Projection], frozenset[int]] = {}

    def locate(self, element: Node) -> tuple[ControlFlowGraph, CfgNode] | None:
        """
        The control-flow graph and node that evaluate *element*, climbing out of any expression it is
        nested in, or `None` when it has no enclosing graph node. The graph identifies the body whose
        invocation runs *element*, which a caller needs to keep a query within one graph.
        """
        return self._flow.locate(element)

    def graph_of(self, owner: Node) -> ControlFlowGraph | None:
        """
        The control-flow graph of the body of *owner*, a function node or the script root, or `None`
        when it has none.
        """
        return self._flow.graph_of(owner)

    def cfg_node_of(self, element: Node) -> CfgNode | None:
        """
        The control-flow node of the statement or loop head that evaluates *element*, or `None` when
        *element* has no enclosing graph node.
        """
        located = self._flow.locate(element)
        return located[1] if located is not None else None

    def locate_pair(self, a: Node, b: Node) -> tuple[ControlFlowGraph, CfgNode, CfgNode] | None:
        """
        The graph and the two control-flow nodes that evaluate *a* and *b* when both lie in the same
        body's graph, or `None` when either is unlocatable or the two lie in different graphs, where
        intraprocedural dominance does not apply.
        """
        located_a = self._flow.locate(a)
        located_b = self._flow.locate(b)
        if located_a is None or located_b is None:
            return None
        graph_a, node_a = located_a
        graph_b, node_b = located_b
        if graph_a is not graph_b:
            return None
        return graph_a, node_a, node_b

    def dominates(self, a: Node, b: Node) -> bool:
        """
        Whether the statement evaluating *a* is guaranteed to have executed by the time the statement
        evaluating *b* runs. Reflexive — *a* and *b* in the same statement share one control-flow
        node, so a node dominates itself. `False` when either element is unlocatable, when the two
        lie in different graphs, or when the statement holding either cannot be reached at all.

        The `Projection.MAY` reading, which is the one an ordering question wants: it accepts *a*
        only where it runs first on *every* path the graph draws, and a path the forward projection
        declines to draw is a path the run can still take. A caller that means the forward reading —
        one flooding rather than ordering — asks `dominates_node` and names it.
        """
        located = self.locate_pair(a, b)
        return located is not None and self.dominates_node(*located, Projection.MAY)

    def strictly_dominates(self, a: Node, b: Node) -> bool:
        """
        Like `dominates`, but not reflexive: `False` when *a* and *b* share one control-flow node.

        A caller that must reject a same-statement occurrence needs this. Two occurrences inside one
        statement may be evaluated in either order as far as this granularity can tell, so the
        reflexive answer would accept a reference that is in fact evaluated first.
        """
        located = self.locate_pair(a, b)
        if located is None or located[1] is located[2]:
            return False
        return self.dominates_node(*located, Projection.MAY)

    def dominates_node(
        self, graph: ControlFlowGraph, a: CfgNode, b: CfgNode, projection: Projection,
    ) -> bool:
        """
        Whether control-flow node *a* dominates *b* within *graph*, which must be the graph both
        belong to, under *projection*. Reflexive. The node-level counterpart of `dominates`, for a
        caller that has already located the two.

        *graph* is asked for rather than looked up because it is the key the dominance tree is
        memoized under, and because a caller holding two nodes has already had to establish that they
        share a body for the question to mean anything.

        *projection* is asked for and has no default, because the two readings disagree exactly where
        this is hardest to check: under `Projection.MAY` a statement guarded by a resuming `trap`
        dominates nothing below it, since the hub draws a run arriving from every later statement,
        and under `Projection.FORWARD` it dominates what follows it. Both answers are right about
        different questions, and a caller that did not choose got whichever this happened to be
        written with.

        The entry dominates exactly the nodes it reaches, which `reached_from_entry` answers without
        the tree: a graph asked nothing but questions from its entry never needs one built.
        """
        if a is graph.entry:
            return id(b) in self.reached_from_entry(graph, projection)
        return self.tree_of(graph, projection).dominates(a, b)

    def tree_of(self, graph: ControlFlowGraph, projection: Projection) -> DominanceTree:
        """
        The dominance tree of *graph* under *projection*, computed on first use and kept thereafter.

        A graph that `carries_resumption` reports nothing of has one tree and not two: the projections
        draw the same edges over it, so both keys answer from the `Projection.MAY` entry. That is
        nearly every script, and it is what keeps a second consumer asking the forward reading from
        doubling the dominance work of the whole run.

        A flood `reached_from_entry` kept for the same key before the tree existed is dropped once
        the tree is built, since the tree holds the same set and is what is read from then on.
        """
        key = self._key(graph, projection)
        found = self._trees.get(key)
        if found is None:
            found = self._trees[key] = DominanceTree(graph, key[1])
            self._reached.pop(key, None)
        return found

    @staticmethod
    def _key(graph: ControlFlowGraph, projection: Projection) -> tuple[int, Projection]:
        """
        The key the answers about *graph* under *projection* are memoized under: its
        `refinery.lib.scripts.analysis.cfg.ControlFlowGraph.reading`, since a graph that
        `carries_resumption` reports nothing of draws the same edges under both projections.
        """
        return id(graph), graph.reading(projection)

    def reached_from_entry(self, graph: ControlFlowGraph, projection: Projection) -> Set[int]:
        """
        The ids of the nodes of *graph* the body's entry reaches under *projection*, memoized per
        graph. A caller deciding which statements of a body can run asks this rather than
        `reachable` from the entry: a script's bodies share one graph per function, and a pass
        asking per body pays one flood per body for an answer that does not vary within a graph.

        Where the dominance tree of the graph exists, it holds that set already. Otherwise one
        flood answers it, which costs a fraction of building the tree: a pass asking this of every
        body of a script would otherwise build a tree for every one of them.
        """
        key = self._key(graph, projection)
        if (tree := self._trees.get(key)) is not None:
            return tree.reached
        if (reached := self._reached.get(key)) is None:
            reached = frozenset(flood([graph.entry], forward=True, projection=key[1]))
            self._reached[key] = reached
        return reached

    def never_runs(self, statement: Node) -> bool:
        """
        Whether no path from the entry of its body reaches any part of *statement*, which is what a
        pass deleting the statements that cannot run asks. A compound statement runs when its first
        executable node is reached, so a `do` loop whose tail-tested condition is unreachable still
        runs its body: the statement never runs only when every control-flow node standing for a
        part of it in the graph of its body is unreachable. A node of a body nested in it belongs to
        the graph of that body and says nothing about whether the statement around it runs, so it
        is not counted, and a statement no node of that graph stands for a part of is not proven
        never to run. In a graph whose every node is reached, nothing is.
        """
        if (graph := self._graph_around(statement)) is None:
            return False
        reachable = self.reached_from_entry(graph, Projection.MAY)
        if len(reachable) == len(graph.nodes):
            return False
        saw_node = False
        for element in statement.walk():
            if (node := graph.node_of(element)) is None:
                continue
            saw_node = True
            if id(node) in reachable:
                return False
        return saw_node

    def completes(self, statement: Node) -> bool:
        """
        Whether control may run off the end of *statement*: some node from which normal control
        falls through past it is reached from the entry of its body
        (`refinery.lib.scripts.analysis.cfg.ControlFlowGraph.completion_of`). A statement the graph
        was not built as a member of a sequence of may.
        """
        if (graph := self._graph_around(statement)) is None:
            return True
        if (completion := graph.completion_of(statement)) is None:
            return True
        reachable = self.reached_from_entry(graph, Projection.MAY)
        return any(id(node) in reachable for node in completion)

    def _graph_around(self, statement: Node) -> ControlFlowGraph | None:
        """
        The graph of the body *statement* stands in: that of its nearest ancestor a graph is drawn
        for.
        """
        cursor = statement.parent
        while cursor is not None:
            if (graph := self._flow.graph_of(cursor)) is not None:
                return graph
            cursor = cursor.parent
        return None

    def reachable(
        self, start: CfgNode, *, forward: bool, projection: Projection,
    ) -> set[int]:
        """
        The ids of the control-flow nodes reachable from *start* under *projection* — over successor
        edges when *forward*, over predecessor edges otherwise — including *start* itself. Exceptional
        edges are followed like any other, since they live in the same successor and predecessor
        lists.

        The two directions are kept separate rather than offered as one path-between query because a
        caller intersecting them memoizes each side independently: one definition is asked against
        many uses, and the forward set from the definition is the same every time.
        """
        return flood([start], forward=forward, projection=projection)

Classes

class DominanceTree (graph, projection)

The dominator relation of one control-flow graph, held as the immediate-dominator tree with a depth-first numbering over it.

A node's dominators are the path from it to the root of that tree, so the tree carries the whole relation in space linear in the body where a set per node is quadratic in it: one straight-line body of five thousand statements costs twelve million set entries as sets and five thousand parent links as a tree. The numbering then answers dominates with two comparisons rather than a set lookup, which matters because the callers above ask it hundreds of thousands of times per script.

Only the nodes the entry reaches are in the tree. That is not an optimisation but the relation: see the module docstring on why an unreachable node dominates nothing.

Expand source code Browse git

class DominanceTree:
    """
    The dominator relation of one control-flow graph, held as the *immediate*-dominator tree with a
    depth-first numbering over it.

    A node's dominators are the path from it to the root of that tree, so the tree carries the whole
    relation in space linear in the body where a set per node is quadratic in it: one straight-line
    body of five thousand statements costs twelve million set entries as sets and five thousand
    parent links as a tree. The numbering then answers `dominates` with two comparisons rather than a
    set lookup, which matters because the callers above ask it hundreds of thousands of times per
    script.

    Only the nodes the entry reaches are in the tree. That is not an optimisation but the relation:
    see the module docstring on why an unreachable node dominates nothing.
    """

    def __init__(self, graph: ControlFlowGraph, projection: Projection):
        self.idom, order = _immediate_dominators(graph, projection)
        self._entered, self._left = _dominance_intervals(self.idom, graph, order)

    @property
    def reached(self) -> Set[int]:
        """
        The ids of the nodes the entry reaches under the projection this tree was built with, which
        is exactly the set the tree holds: a node the entry does not reach is not in it at all.

        Read rather than flooded again. A caller asking which statements of a body can run is asking
        the question the tree already had to answer to exist, and a flood per body per pass over a
        script whose bodies share one graph is the same walk repeated.
        """
        return self._entered.keys()

    def dominates(self, a: CfgNode, b: CfgNode) -> bool:
        """
        Whether *a* dominates *b*. Reflexive for a reachable node; `False` whenever either node is
        unreachable, the two being one unreachable node included.
        """
        opened = self._entered.get(id(a))
        if opened is None:
            return False
        reached = self._entered.get(id(b))
        return reached is not None and opened <= reached < self._left[id(a)]

Instance variables

var reached

The ids of the nodes the entry reaches under the projection this tree was built with, which is exactly the set the tree holds: a node the entry does not reach is not in it at all.

Read rather than flooded again. A caller asking which statements of a body can run is asking the question the tree already had to answer to exist, and a flood per body per pass over a script whose bodies share one graph is the same walk repeated.

Expand source code Browse git

@property
def reached(self) -> Set[int]:
    """
    The ids of the nodes the entry reaches under the projection this tree was built with, which
    is exactly the set the tree holds: a node the entry does not reach is not in it at all.

    Read rather than flooded again. A caller asking which statements of a body can run is asking
    the question the tree already had to answer to exist, and a flood per body per pass over a
    script whose bodies share one graph is the same walk repeated.
    """
    return self._entered.keys()

Methods

def dominates(self, a, b)

Whether a dominates b. Reflexive for a reachable node; False whenever either node is unreachable, the two being one unreachable node included.

Expand source code Browse git

def dominates(self, a: CfgNode, b: CfgNode) -> bool:
    """
    Whether *a* dominates *b*. Reflexive for a reachable node; `False` whenever either node is
    unreachable, the two being one unreachable node included.
    """
    opened = self._entered.get(id(a))
    if opened is None:
        return False
    reached = self._entered.get(id(b))
    return reached is not None and opened <= reached < self._left[id(a)]

class DominatorModel (flow)

Dominator relations for the per-body control-flow graphs of one script. A graph's dominance tree is computed once, on the first ordering question asked about that graph, and kept for as long as this model lives.

Computing them all on construction instead would charge every caller for the whole script when most callers ask about one body, and the model is rebuilt from scratch whenever the tree version advances. This is the same laziness CycleModel has, for the same reason.

Expand source code Browse git

class DominatorModel:
    """
    Dominator relations for the per-body control-flow graphs of one script. A graph's dominance tree
    is computed once, on the first ordering question asked about that graph, and kept for as long as
    this model lives.

    Computing them all on construction instead would charge every caller for the whole script when
    most callers ask about one body, and the model is rebuilt from scratch whenever the tree version
    advances. This is the same laziness `refinery.lib.scripts.analysis.cycles.CycleModel` has, for the
    same reason.
    """

    def __init__(self, flow: ControlFlowModel):
        self._flow = flow
        self._trees: dict[tuple[int, Projection], DominanceTree] = {}
        self._reached: dict[tuple[int, Projection], frozenset[int]] = {}

    def locate(self, element: Node) -> tuple[ControlFlowGraph, CfgNode] | None:
        """
        The control-flow graph and node that evaluate *element*, climbing out of any expression it is
        nested in, or `None` when it has no enclosing graph node. The graph identifies the body whose
        invocation runs *element*, which a caller needs to keep a query within one graph.
        """
        return self._flow.locate(element)

    def graph_of(self, owner: Node) -> ControlFlowGraph | None:
        """
        The control-flow graph of the body of *owner*, a function node or the script root, or `None`
        when it has none.
        """
        return self._flow.graph_of(owner)

    def cfg_node_of(self, element: Node) -> CfgNode | None:
        """
        The control-flow node of the statement or loop head that evaluates *element*, or `None` when
        *element* has no enclosing graph node.
        """
        located = self._flow.locate(element)
        return located[1] if located is not None else None

    def locate_pair(self, a: Node, b: Node) -> tuple[ControlFlowGraph, CfgNode, CfgNode] | None:
        """
        The graph and the two control-flow nodes that evaluate *a* and *b* when both lie in the same
        body's graph, or `None` when either is unlocatable or the two lie in different graphs, where
        intraprocedural dominance does not apply.
        """
        located_a = self._flow.locate(a)
        located_b = self._flow.locate(b)
        if located_a is None or located_b is None:
            return None
        graph_a, node_a = located_a
        graph_b, node_b = located_b
        if graph_a is not graph_b:
            return None
        return graph_a, node_a, node_b

    def dominates(self, a: Node, b: Node) -> bool:
        """
        Whether the statement evaluating *a* is guaranteed to have executed by the time the statement
        evaluating *b* runs. Reflexive — *a* and *b* in the same statement share one control-flow
        node, so a node dominates itself. `False` when either element is unlocatable, when the two
        lie in different graphs, or when the statement holding either cannot be reached at all.

        The `Projection.MAY` reading, which is the one an ordering question wants: it accepts *a*
        only where it runs first on *every* path the graph draws, and a path the forward projection
        declines to draw is a path the run can still take. A caller that means the forward reading —
        one flooding rather than ordering — asks `dominates_node` and names it.
        """
        located = self.locate_pair(a, b)
        return located is not None and self.dominates_node(*located, Projection.MAY)

    def strictly_dominates(self, a: Node, b: Node) -> bool:
        """
        Like `dominates`, but not reflexive: `False` when *a* and *b* share one control-flow node.

        A caller that must reject a same-statement occurrence needs this. Two occurrences inside one
        statement may be evaluated in either order as far as this granularity can tell, so the
        reflexive answer would accept a reference that is in fact evaluated first.
        """
        located = self.locate_pair(a, b)
        if located is None or located[1] is located[2]:
            return False
        return self.dominates_node(*located, Projection.MAY)

    def dominates_node(
        self, graph: ControlFlowGraph, a: CfgNode, b: CfgNode, projection: Projection,
    ) -> bool:
        """
        Whether control-flow node *a* dominates *b* within *graph*, which must be the graph both
        belong to, under *projection*. Reflexive. The node-level counterpart of `dominates`, for a
        caller that has already located the two.

        *graph* is asked for rather than looked up because it is the key the dominance tree is
        memoized under, and because a caller holding two nodes has already had to establish that they
        share a body for the question to mean anything.

        *projection* is asked for and has no default, because the two readings disagree exactly where
        this is hardest to check: under `Projection.MAY` a statement guarded by a resuming `trap`
        dominates nothing below it, since the hub draws a run arriving from every later statement,
        and under `Projection.FORWARD` it dominates what follows it. Both answers are right about
        different questions, and a caller that did not choose got whichever this happened to be
        written with.

        The entry dominates exactly the nodes it reaches, which `reached_from_entry` answers without
        the tree: a graph asked nothing but questions from its entry never needs one built.
        """
        if a is graph.entry:
            return id(b) in self.reached_from_entry(graph, projection)
        return self.tree_of(graph, projection).dominates(a, b)

    def tree_of(self, graph: ControlFlowGraph, projection: Projection) -> DominanceTree:
        """
        The dominance tree of *graph* under *projection*, computed on first use and kept thereafter.

        A graph that `carries_resumption` reports nothing of has one tree and not two: the projections
        draw the same edges over it, so both keys answer from the `Projection.MAY` entry. That is
        nearly every script, and it is what keeps a second consumer asking the forward reading from
        doubling the dominance work of the whole run.

        A flood `reached_from_entry` kept for the same key before the tree existed is dropped once
        the tree is built, since the tree holds the same set and is what is read from then on.
        """
        key = self._key(graph, projection)
        found = self._trees.get(key)
        if found is None:
            found = self._trees[key] = DominanceTree(graph, key[1])
            self._reached.pop(key, None)
        return found

    @staticmethod
    def _key(graph: ControlFlowGraph, projection: Projection) -> tuple[int, Projection]:
        """
        The key the answers about *graph* under *projection* are memoized under: its
        `refinery.lib.scripts.analysis.cfg.ControlFlowGraph.reading`, since a graph that
        `carries_resumption` reports nothing of draws the same edges under both projections.
        """
        return id(graph), graph.reading(projection)

    def reached_from_entry(self, graph: ControlFlowGraph, projection: Projection) -> Set[int]:
        """
        The ids of the nodes of *graph* the body's entry reaches under *projection*, memoized per
        graph. A caller deciding which statements of a body can run asks this rather than
        `reachable` from the entry: a script's bodies share one graph per function, and a pass
        asking per body pays one flood per body for an answer that does not vary within a graph.

        Where the dominance tree of the graph exists, it holds that set already. Otherwise one
        flood answers it, which costs a fraction of building the tree: a pass asking this of every
        body of a script would otherwise build a tree for every one of them.
        """
        key = self._key(graph, projection)
        if (tree := self._trees.get(key)) is not None:
            return tree.reached
        if (reached := self._reached.get(key)) is None:
            reached = frozenset(flood([graph.entry], forward=True, projection=key[1]))
            self._reached[key] = reached
        return reached

    def never_runs(self, statement: Node) -> bool:
        """
        Whether no path from the entry of its body reaches any part of *statement*, which is what a
        pass deleting the statements that cannot run asks. A compound statement runs when its first
        executable node is reached, so a `do` loop whose tail-tested condition is unreachable still
        runs its body: the statement never runs only when every control-flow node standing for a
        part of it in the graph of its body is unreachable. A node of a body nested in it belongs to
        the graph of that body and says nothing about whether the statement around it runs, so it
        is not counted, and a statement no node of that graph stands for a part of is not proven
        never to run. In a graph whose every node is reached, nothing is.
        """
        if (graph := self._graph_around(statement)) is None:
            return False
        reachable = self.reached_from_entry(graph, Projection.MAY)
        if len(reachable) == len(graph.nodes):
            return False
        saw_node = False
        for element in statement.walk():
            if (node := graph.node_of(element)) is None:
                continue
            saw_node = True
            if id(node) in reachable:
                return False
        return saw_node

    def completes(self, statement: Node) -> bool:
        """
        Whether control may run off the end of *statement*: some node from which normal control
        falls through past it is reached from the entry of its body
        (`refinery.lib.scripts.analysis.cfg.ControlFlowGraph.completion_of`). A statement the graph
        was not built as a member of a sequence of may.
        """
        if (graph := self._graph_around(statement)) is None:
            return True
        if (completion := graph.completion_of(statement)) is None:
            return True
        reachable = self.reached_from_entry(graph, Projection.MAY)
        return any(id(node) in reachable for node in completion)

    def _graph_around(self, statement: Node) -> ControlFlowGraph | None:
        """
        The graph of the body *statement* stands in: that of its nearest ancestor a graph is drawn
        for.
        """
        cursor = statement.parent
        while cursor is not None:
            if (graph := self._flow.graph_of(cursor)) is not None:
                return graph
            cursor = cursor.parent
        return None

    def reachable(
        self, start: CfgNode, *, forward: bool, projection: Projection,
    ) -> set[int]:
        """
        The ids of the control-flow nodes reachable from *start* under *projection* — over successor
        edges when *forward*, over predecessor edges otherwise — including *start* itself. Exceptional
        edges are followed like any other, since they live in the same successor and predecessor
        lists.

        The two directions are kept separate rather than offered as one path-between query because a
        caller intersecting them memoizes each side independently: one definition is asked against
        many uses, and the forward set from the definition is the same every time.
        """
        return flood([start], forward=forward, projection=projection)

Subclasses

• DominanceModel

Methods

def locate(self, element)

The control-flow graph and node that evaluate element, climbing out of any expression it is nested in, or None when it has no enclosing graph node. The graph identifies the body whose invocation runs element, which a caller needs to keep a query within one graph.

Expand source code Browse git

def locate(self, element: Node) -> tuple[ControlFlowGraph, CfgNode] | None:
    """
    The control-flow graph and node that evaluate *element*, climbing out of any expression it is
    nested in, or `None` when it has no enclosing graph node. The graph identifies the body whose
    invocation runs *element*, which a caller needs to keep a query within one graph.
    """
    return self._flow.locate(element)

def graph_of(self, owner)

The control-flow graph of the body of owner, a function node or the script root, or None when it has none.

Expand source code Browse git

def graph_of(self, owner: Node) -> ControlFlowGraph | None:
    """
    The control-flow graph of the body of *owner*, a function node or the script root, or `None`
    when it has none.
    """
    return self._flow.graph_of(owner)

def cfg_node_of(self, element)

The control-flow node of the statement or loop head that evaluates element, or None when element has no enclosing graph node.

Expand source code Browse git

def cfg_node_of(self, element: Node) -> CfgNode | None:
    """
    The control-flow node of the statement or loop head that evaluates *element*, or `None` when
    *element* has no enclosing graph node.
    """
    located = self._flow.locate(element)
    return located[1] if located is not None else None

def locate_pair(self, a, b)

The graph and the two control-flow nodes that evaluate a and b when both lie in the same body's graph, or None when either is unlocatable or the two lie in different graphs, where intraprocedural dominance does not apply.

Expand source code Browse git

def locate_pair(self, a: Node, b: Node) -> tuple[ControlFlowGraph, CfgNode, CfgNode] | None:
    """
    The graph and the two control-flow nodes that evaluate *a* and *b* when both lie in the same
    body's graph, or `None` when either is unlocatable or the two lie in different graphs, where
    intraprocedural dominance does not apply.
    """
    located_a = self._flow.locate(a)
    located_b = self._flow.locate(b)
    if located_a is None or located_b is None:
        return None
    graph_a, node_a = located_a
    graph_b, node_b = located_b
    if graph_a is not graph_b:
        return None
    return graph_a, node_a, node_b

def dominates(self, a, b)

Whether the statement evaluating a is guaranteed to have executed by the time the statement evaluating b runs. Reflexive — a and b in the same statement share one control-flow node, so a node dominates itself. False when either element is unlocatable, when the two lie in different graphs, or when the statement holding either cannot be reached at all.

The Projection.MAY reading, which is the one an ordering question wants: it accepts a only where it runs first on every path the graph draws, and a path the forward projection declines to draw is a path the run can still take. A caller that means the forward reading — one flooding rather than ordering — asks dominates_node and names it.

Expand source code Browse git

def dominates(self, a: Node, b: Node) -> bool:
    """
    Whether the statement evaluating *a* is guaranteed to have executed by the time the statement
    evaluating *b* runs. Reflexive — *a* and *b* in the same statement share one control-flow
    node, so a node dominates itself. `False` when either element is unlocatable, when the two
    lie in different graphs, or when the statement holding either cannot be reached at all.

    The `Projection.MAY` reading, which is the one an ordering question wants: it accepts *a*
    only where it runs first on *every* path the graph draws, and a path the forward projection
    declines to draw is a path the run can still take. A caller that means the forward reading —
    one flooding rather than ordering — asks `dominates_node` and names it.
    """
    located = self.locate_pair(a, b)
    return located is not None and self.dominates_node(*located, Projection.MAY)

def strictly_dominates(self, a, b)

Like dominates, but not reflexive: False when a and b share one control-flow node.

A caller that must reject a same-statement occurrence needs this. Two occurrences inside one statement may be evaluated in either order as far as this granularity can tell, so the reflexive answer would accept a reference that is in fact evaluated first.

Expand source code Browse git

def strictly_dominates(self, a: Node, b: Node) -> bool:
    """
    Like `dominates`, but not reflexive: `False` when *a* and *b* share one control-flow node.

    A caller that must reject a same-statement occurrence needs this. Two occurrences inside one
    statement may be evaluated in either order as far as this granularity can tell, so the
    reflexive answer would accept a reference that is in fact evaluated first.
    """
    located = self.locate_pair(a, b)
    if located is None or located[1] is located[2]:
        return False
    return self.dominates_node(*located, Projection.MAY)

def dominates_node(self, graph, a, b, projection)

Whether control-flow node a dominates b within graph, which must be the graph both belong to, under projection. Reflexive. The node-level counterpart of dominates, for a caller that has already located the two.

graph is asked for rather than looked up because it is the key the dominance tree is memoized under, and because a caller holding two nodes has already had to establish that they share a body for the question to mean anything.

projection is asked for and has no default, because the two readings disagree exactly where this is hardest to check: under Projection.MAY a statement guarded by a resuming trap dominates nothing below it, since the hub draws a run arriving from every later statement, and under Projection.FORWARD it dominates what follows it. Both answers are right about different questions, and a caller that did not choose got whichever this happened to be written with.

The entry dominates exactly the nodes it reaches, which reached_from_entry answers without the tree: a graph asked nothing but questions from its entry never needs one built.

Expand source code Browse git

def dominates_node(
    self, graph: ControlFlowGraph, a: CfgNode, b: CfgNode, projection: Projection,
) -> bool:
    """
    Whether control-flow node *a* dominates *b* within *graph*, which must be the graph both
    belong to, under *projection*. Reflexive. The node-level counterpart of `dominates`, for a
    caller that has already located the two.

    *graph* is asked for rather than looked up because it is the key the dominance tree is
    memoized under, and because a caller holding two nodes has already had to establish that they
    share a body for the question to mean anything.

    *projection* is asked for and has no default, because the two readings disagree exactly where
    this is hardest to check: under `Projection.MAY` a statement guarded by a resuming `trap`
    dominates nothing below it, since the hub draws a run arriving from every later statement,
    and under `Projection.FORWARD` it dominates what follows it. Both answers are right about
    different questions, and a caller that did not choose got whichever this happened to be
    written with.

    The entry dominates exactly the nodes it reaches, which `reached_from_entry` answers without
    the tree: a graph asked nothing but questions from its entry never needs one built.
    """
    if a is graph.entry:
        return id(b) in self.reached_from_entry(graph, projection)
    return self.tree_of(graph, projection).dominates(a, b)

def tree_of(self, graph, projection)

The dominance tree of graph under projection, computed on first use and kept thereafter.

A graph that carries_resumption reports nothing of has one tree and not two: the projections draw the same edges over it, so both keys answer from the Projection.MAY entry. That is nearly every script, and it is what keeps a second consumer asking the forward reading from doubling the dominance work of the whole run.

A flood reached_from_entry kept for the same key before the tree existed is dropped once the tree is built, since the tree holds the same set and is what is read from then on.

Expand source code Browse git

def tree_of(self, graph: ControlFlowGraph, projection: Projection) -> DominanceTree:
    """
    The dominance tree of *graph* under *projection*, computed on first use and kept thereafter.

    A graph that `carries_resumption` reports nothing of has one tree and not two: the projections
    draw the same edges over it, so both keys answer from the `Projection.MAY` entry. That is
    nearly every script, and it is what keeps a second consumer asking the forward reading from
    doubling the dominance work of the whole run.

    A flood `reached_from_entry` kept for the same key before the tree existed is dropped once
    the tree is built, since the tree holds the same set and is what is read from then on.
    """
    key = self._key(graph, projection)
    found = self._trees.get(key)
    if found is None:
        found = self._trees[key] = DominanceTree(graph, key[1])
        self._reached.pop(key, None)
    return found

def reached_from_entry(self, graph, projection)

The ids of the nodes of graph the body's entry reaches under projection, memoized per graph. A caller deciding which statements of a body can run asks this rather than reachable from the entry: a script's bodies share one graph per function, and a pass asking per body pays one flood per body for an answer that does not vary within a graph.

Where the dominance tree of the graph exists, it holds that set already. Otherwise one flood answers it, which costs a fraction of building the tree: a pass asking this of every body of a script would otherwise build a tree for every one of them.

Expand source code Browse git

def reached_from_entry(self, graph: ControlFlowGraph, projection: Projection) -> Set[int]:
    """
    The ids of the nodes of *graph* the body's entry reaches under *projection*, memoized per
    graph. A caller deciding which statements of a body can run asks this rather than
    `reachable` from the entry: a script's bodies share one graph per function, and a pass
    asking per body pays one flood per body for an answer that does not vary within a graph.

    Where the dominance tree of the graph exists, it holds that set already. Otherwise one
    flood answers it, which costs a fraction of building the tree: a pass asking this of every
    body of a script would otherwise build a tree for every one of them.
    """
    key = self._key(graph, projection)
    if (tree := self._trees.get(key)) is not None:
        return tree.reached
    if (reached := self._reached.get(key)) is None:
        reached = frozenset(flood([graph.entry], forward=True, projection=key[1]))
        self._reached[key] = reached
    return reached

def never_runs(self, statement)

Whether no path from the entry of its body reaches any part of statement, which is what a pass deleting the statements that cannot run asks. A compound statement runs when its first executable node is reached, so a do loop whose tail-tested condition is unreachable still runs its body: the statement never runs only when every control-flow node standing for a part of it in the graph of its body is unreachable. A node of a body nested in it belongs to the graph of that body and says nothing about whether the statement around it runs, so it is not counted, and a statement no node of that graph stands for a part of is not proven never to run. In a graph whose every node is reached, nothing is.

Expand source code Browse git

def never_runs(self, statement: Node) -> bool:
    """
    Whether no path from the entry of its body reaches any part of *statement*, which is what a
    pass deleting the statements that cannot run asks. A compound statement runs when its first
    executable node is reached, so a `do` loop whose tail-tested condition is unreachable still
    runs its body: the statement never runs only when every control-flow node standing for a
    part of it in the graph of its body is unreachable. A node of a body nested in it belongs to
    the graph of that body and says nothing about whether the statement around it runs, so it
    is not counted, and a statement no node of that graph stands for a part of is not proven
    never to run. In a graph whose every node is reached, nothing is.
    """
    if (graph := self._graph_around(statement)) is None:
        return False
    reachable = self.reached_from_entry(graph, Projection.MAY)
    if len(reachable) == len(graph.nodes):
        return False
    saw_node = False
    for element in statement.walk():
        if (node := graph.node_of(element)) is None:
            continue
        saw_node = True
        if id(node) in reachable:
            return False
    return saw_node

def completes(self, statement)

Whether control may run off the end of statement: some node from which normal control falls through past it is reached from the entry of its body (ControlFlowGraph.completion_of()). A statement the graph was not built as a member of a sequence of may.

Expand source code Browse git

def completes(self, statement: Node) -> bool:
    """
    Whether control may run off the end of *statement*: some node from which normal control
    falls through past it is reached from the entry of its body
    (`refinery.lib.scripts.analysis.cfg.ControlFlowGraph.completion_of`). A statement the graph
    was not built as a member of a sequence of may.
    """
    if (graph := self._graph_around(statement)) is None:
        return True
    if (completion := graph.completion_of(statement)) is None:
        return True
    reachable = self.reached_from_entry(graph, Projection.MAY)
    return any(id(node) in reachable for node in completion)

def reachable(self, start, *, forward, projection)

The ids of the control-flow nodes reachable from start under projection — over successor edges when forward, over predecessor edges otherwise — including start itself. Exceptional edges are followed like any other, since they live in the same successor and predecessor lists.

The two directions are kept separate rather than offered as one path-between query because a caller intersecting them memoizes each side independently: one definition is asked against many uses, and the forward set from the definition is the same every time.

Expand source code Browse git

def reachable(
    self, start: CfgNode, *, forward: bool, projection: Projection,
) -> set[int]:
    """
    The ids of the control-flow nodes reachable from *start* under *projection* — over successor
    edges when *forward*, over predecessor edges otherwise — including *start* itself. Exceptional
    edges are followed like any other, since they live in the same successor and predecessor
    lists.

    The two directions are kept separate rather than offered as one path-between query because a
    caller intersecting them memoizes each side independently: one definition is asked against
    many uses, and the forward set from the definition is the same every time.
    """
    return flood([start], forward=forward, projection=projection)