Module refinery.lib.scripts.js.analysis.cfg

JavaScript's contribution to the shared control-flow substrate: which node types are which control-flow shape, and where the parts of each are stored.

Everything structural — the graph, the frontier threading, the jump-target and handler stacks, and the shapes themselves — lives in refinery.lib.scripts.analysis.cfg. What remains here is _Builder.statement, the recognition of Js* node types, and the accessors that pull a construct apart. Two of the shape parameters are answered from JavaScript semantics rather than from syntax: switch falls through from one case to the next, and an unlabelled break may leave a switch as well as a loop.

"""
JavaScript's contribution to the shared control-flow substrate: which node types are which
control-flow shape, and where the parts of each are stored.

Everything structural — the graph, the frontier threading, the jump-target and handler stacks, and
the shapes themselves — lives in `refinery.lib.scripts.analysis.cfg`. What remains here is
`_Builder.statement`, the recognition of `Js*` node types, and the accessors that pull a construct
apart. Two of the shape parameters are answered from JavaScript semantics rather than from syntax:
`switch` falls through from one case to the next, and an unlabelled `break` may leave a `switch` as
well as a loop.
"""
from __future__ import annotations

from typing import Sequence

from refinery.lib.scripts import Node
from refinery.lib.scripts.analysis.cfg import (
    ArmFlow,
    CfgBuilder,
    CfgNode,
    ControlFlowGraph,
    ControlFlowModel,
    ElementLocator,
)
from refinery.lib.scripts.analysis.cfg import build_control_flow as _build_control_flow
from refinery.lib.scripts.js.analysis.model import FUNCTION_NODES
from refinery.lib.scripts.js.model import (
    JsBlockStatement,
    JsBreakStatement,
    JsContinueStatement,
    JsDoWhileStatement,
    JsForInStatement,
    JsForOfStatement,
    JsForStatement,
    JsIfStatement,
    JsLabeledStatement,
    JsReturnStatement,
    JsScript,
    JsSwitchStatement,
    JsThrowStatement,
    JsTryStatement,
    JsWhileStatement,
    JsWithStatement,
)

__all__ = [
    'CfgNode',
    'ControlFlowGraph',
    'ControlFlowModel',
    'ElementLocator',
    'build_cfg',
    'build_control_flow',
    'build_control_flow_model',
]

_LOOP_NODES = (
    JsWhileStatement,
    JsDoWhileStatement,
    JsForStatement,
    JsForInStatement,
    JsForOfStatement,
)


def _label_name(statement: Node) -> str | None:
    label = getattr(statement, 'label', None)
    return label.name if label is not None else None


class _Builder(CfgBuilder):
    """
    The JavaScript dispatch over `refinery.lib.scripts.analysis.cfg.CfgBuilder`.
    """

    def body_statements(self, owner: Node) -> list[Node]:
        if isinstance(owner, JsScript):
            return list(owner.body)
        body = getattr(owner, 'body', None)
        if isinstance(body, JsBlockStatement):
            return list(body.body)
        if isinstance(body, Node):
            return [body]
        return []

    def statement(self, statement: Node, frontier: list[CfgNode]) -> list[CfgNode]:
        if isinstance(statement, JsBlockStatement):
            return self.sequence(statement.body, frontier)
        if isinstance(statement, JsIfStatement):
            arms: list[Node | None] = [statement.consequent]
            if statement.alternate is not None:
                arms.append(statement.alternate)
            return self.branch_on(
                statement, arms, frontier, exhaustive=statement.alternate is not None)
        if isinstance(statement, JsWhileStatement):
            return self.loop_head_tested(statement, statement.body, frontier)
        if isinstance(statement, JsDoWhileStatement):
            return self.loop_tail_tested(statement, statement.body, frontier)
        if isinstance(statement, JsForStatement):
            return self.loop_counted(
                statement.init, statement.test, statement.update, statement.body, frontier)
        if isinstance(statement, (JsForInStatement, JsForOfStatement)):
            return self.loop_head_tested(statement, getattr(statement, 'body', None), frontier)
        if isinstance(statement, JsSwitchStatement):
            return self._switch(statement, frontier)
        if isinstance(statement, JsTryStatement):
            handler = statement.handler
            finalizer = statement.finalizer
            return self.guarded(
                statement.block,
                [(handler, handler.body)] if handler is not None else (),
                finalizer,
                list(finalizer.body) if finalizer is not None else (),
                frontier,
            )
        if isinstance(statement, JsLabeledStatement):
            return self.labelled(
                _label_name(statement),
                statement.body,
                frontier,
                binds_to_body=isinstance(statement.body, (*_LOOP_NODES, JsSwitchStatement)),
            )
        if isinstance(statement, JsReturnStatement):
            return self.terminate(statement, frontier, exceptional=False)
        if isinstance(statement, JsThrowStatement):
            return self.terminate(statement, frontier, exceptional=True)
        if isinstance(statement, JsBreakStatement):
            return self.jump_out(statement, _label_name(statement), frontier)
        if isinstance(statement, JsContinueStatement):
            return self.jump_back(statement, _label_name(statement), frontier)
        if isinstance(statement, JsWithStatement):
            node = self.node(statement)
            self.link(frontier, node)
            return self.statement(statement.body, [node]) if statement.body else [node]
        return self.opaque(statement, frontier)

    def _switch(self, statement: JsSwitchStatement, frontier: list[CfgNode]) -> list[CfgNode]:
        arms: list[Sequence[Node]] = [list(case.body) for case in statement.cases]
        exhaustive = any(case.test is None for case in statement.cases)
        return self.dispatch(
            statement, arms, frontier, arm_flow=ArmFlow.SEQUENTIAL, exhaustive=exhaustive)


def build_cfg(owner: Node) -> ControlFlowGraph:
    """
    Build the control-flow graph of *owner*, a `refinery.lib.scripts.js.model.JsScript` or a
    function node, over its own body without descending into nested function bodies.
    """
    return _Builder(owner).build()


def build_control_flow(root: JsScript) -> dict[int, ControlFlowGraph]:
    """
    Build one control-flow graph per function and for the script itself, keyed by the owner node's
    identity.
    """
    return _build_control_flow(root, _Builder, FUNCTION_NODES)


def build_control_flow_model(root: JsScript) -> ControlFlowModel:
    """
    Build the `refinery.lib.scripts.analysis.cfg.ControlFlowModel` for a script root — the shared
    control-flow layer the `DominanceModel` and `LivenessModel` consume.
    """
    return ControlFlowModel(build_control_flow(root))

Functions

def build_cfg(owner)

Build the control-flow graph of owner, a JsScript or a function node, over its own body without descending into nested function bodies.

Expand source code Browse git

def build_cfg(owner: Node) -> ControlFlowGraph:
    """
    Build the control-flow graph of *owner*, a `refinery.lib.scripts.js.model.JsScript` or a
    function node, over its own body without descending into nested function bodies.
    """
    return _Builder(owner).build()

def build_control_flow(root)

Build one control-flow graph per function and for the script itself, keyed by the owner node's identity.

Expand source code Browse git

def build_control_flow(root: JsScript) -> dict[int, ControlFlowGraph]:
    """
    Build one control-flow graph per function and for the script itself, keyed by the owner node's
    identity.
    """
    return _build_control_flow(root, _Builder, FUNCTION_NODES)

def build_control_flow_model(root)

Build the ControlFlowModel for a script root — the shared control-flow layer the DominanceModel and LivenessModel consume.

Expand source code Browse git

def build_control_flow_model(root: JsScript) -> ControlFlowModel:
    """
    Build the `refinery.lib.scripts.analysis.cfg.ControlFlowModel` for a script root — the shared
    control-flow layer the `DominanceModel` and `LivenessModel` consume.
    """
    return ControlFlowModel(build_control_flow(root))

Classes

class CfgNode (element, successors=<factory>, predecessors=<factory>)

One vertex of a control-flow graph. element is the AST node it stands for — a statement, or a loop-head expression whose reads and writes occur at this point — or None for the synthetic entry and exit. successors lists the nodes control may pass to next.

eq=False is load bearing. Every map in every layer above is keyed by id(node), and two structurally equal statements are two distinct points in the program.

repr=False is too. A generated repr expands successors and predecessors, and the guard against recursion only covers the node currently being formatted, so a graph re-expands at every join: a chain of five hundred nodes — a script of five hundred statements — exhausts the interpreter's stack, and a handful of branches produces megabytes. A debugger, a failing assertion, or pytest --showlocals would print one.

Expand source code Browse git

@dataclass(eq=False, repr=False)
class CfgNode:
    """
    One vertex of a control-flow graph. `element` is the AST node it stands for — a statement, or a
    loop-head expression whose reads and writes occur at this point — or `None` for the synthetic
    entry and exit. `successors` lists the nodes control may pass to next.

    `eq=False` is load bearing. Every map in every layer above is keyed by `id(node)`, and two
    structurally equal statements are two distinct points in the program.

    `repr=False` is too. A generated repr expands `successors` and `predecessors`, and the guard
    against recursion only covers the node currently being formatted, so a graph re-expands at every
    join: a chain of five hundred nodes — a script of five hundred statements — exhausts the
    interpreter's stack, and a handful of branches produces megabytes. A debugger, a failing
    assertion, or `pytest --showlocals` would print one.
    """
    element: Node | None
    successors: list[CfgNode] = field(default_factory=list)
    predecessors: list[CfgNode] = field(default_factory=list)

Instance variables

var element

The type of the None singleton.

var successors

The type of the None singleton.

var predecessors

The type of the None singleton.

class ControlFlowGraph (owner)

The control-flow graph of one function or script body. entry and exit are synthetic; every other node wraps an AST element reachable through node_of.

Expand source code Browse git

class ControlFlowGraph:
    """
    The control-flow graph of one function or script body. `entry` and `exit` are synthetic; every
    other node wraps an AST element reachable through `node_of`.
    """

    def __init__(self, owner: Node):
        self.owner = owner
        self.entry = CfgNode(None)
        self.exit = CfgNode(None)
        self.nodes: list[CfgNode] = [self.entry, self.exit]
        self._node_of: dict[int, CfgNode] = {}
        self.exceptional_edges: set[tuple[int, int]] = set()

    def node_of(self, element: Node) -> CfgNode | None:
        """
        The graph node standing for *element*, or `None` if *element* is not part of this body, or is
        a node the graph does not represent on its own such as a plain expression inside a statement.
        """
        return self._node_of.get(id(element))

    def is_exceptional(self, source: CfgNode, target: CfgNode) -> bool:
        """
        Whether the edge from *source* to *target* is taken only when *source* throws rather than
        completing normally. A definition *source* makes is not guaranteed to have happened along
        such an edge, so a flow-sensitive analysis must not treat it as a kill there.
        """
        return (id(source), id(target)) in self.exceptional_edges

Methods

def node_of(self, element)

The graph node standing for element, or None if element is not part of this body, or is a node the graph does not represent on its own such as a plain expression inside a statement.

Expand source code Browse git

def node_of(self, element: Node) -> CfgNode | None:
    """
    The graph node standing for *element*, or `None` if *element* is not part of this body, or is
    a node the graph does not represent on its own such as a plain expression inside a statement.
    """
    return self._node_of.get(id(element))

def is_exceptional(self, source, target)

Whether the edge from source to target is taken only when source throws rather than completing normally. A definition source makes is not guaranteed to have happened along such an edge, so a flow-sensitive analysis must not treat it as a kill there.

Expand source code Browse git

def is_exceptional(self, source: CfgNode, target: CfgNode) -> bool:
    """
    Whether the edge from *source* to *target* is taken only when *source* throws rather than
    completing normally. A definition *source* makes is not guaranteed to have happened along
    such an edge, so a flow-sensitive analysis must not treat it as a kill there.
    """
    return (id(source), id(target)) in self.exceptional_edges

class ControlFlowModel (graphs)

The per-body control-flow graphs of one script, paired with the ElementLocator that maps any AST node to the graph node evaluating it. Built once over the script root — the graphs are purely syntactic and need no semantic model — and shared by every solver layered on it, which would otherwise each rebuild the whole set.

Expand source code Browse git

class ControlFlowModel:
    """
    The per-body control-flow graphs of one script, paired with the `ElementLocator` that maps any
    AST node to the graph node evaluating it. Built once over the script root — the graphs are purely
    syntactic and need no semantic model — and shared by every solver layered on it, which would
    otherwise each rebuild the whole set.
    """

    def __init__(self, graphs: dict[int, ControlFlowGraph]):
        self.graphs = graphs
        self._locator = ElementLocator(graphs)

    def graph_of(self, owner: Node) -> ControlFlowGraph | None:
        """
        The control-flow graph owned by *owner* — a function node or the script root — or `None` when
        it owns none.
        """
        return self.graphs.get(id(owner))

    def node_of(self, element: Node) -> CfgNode | None:
        """
        The control-flow node standing for *element*, or `None` when the graphs do not represent it
        directly. Delegates to the shared `ElementLocator`.
        """
        return self._locator.node_of(element)

    def locate(self, element: Node) -> tuple[ControlFlowGraph, CfgNode] | None:
        """
        The graph and node that evaluate *element*, climbing out of any enclosing expression, or
        `None` when it has no enclosing graph node. Delegates to the shared `ElementLocator`.
        """
        return self._locator.locate(element)

Methods

def graph_of(self, owner)

The control-flow graph owned by owner — a function node or the script root — or None when it owns none.

Expand source code Browse git

def graph_of(self, owner: Node) -> ControlFlowGraph | None:
    """
    The control-flow graph owned by *owner* — a function node or the script root — or `None` when
    it owns none.
    """
    return self.graphs.get(id(owner))

def node_of(self, element)

The control-flow node standing for element, or None when the graphs do not represent it directly. Delegates to the shared ElementLocator.

Expand source code Browse git

def node_of(self, element: Node) -> CfgNode | None:
    """
    The control-flow node standing for *element*, or `None` when the graphs do not represent it
    directly. Delegates to the shared `ElementLocator`.
    """
    return self._locator.node_of(element)

def locate(self, element)

The graph and node that evaluate element, climbing out of any enclosing expression, or None when it has no enclosing graph node. Delegates to the shared ElementLocator.

Expand source code Browse git

def locate(self, element: Node) -> tuple[ControlFlowGraph, CfgNode] | None:
    """
    The graph and node that evaluate *element*, climbing out of any enclosing expression, or
    `None` when it has no enclosing graph node. Delegates to the shared `ElementLocator`.
    """
    return self._locator.locate(element)

class ElementLocator (graphs)

Locates an AST node among the per-body control-flow graphs of one script. Built once from the graph set, it maps an element to the graph and node that evaluate it — directly for an element a graph node stands for (node_of), or by climbing to the enclosing statement for one nested inside an expression (locate). Every flow-sensitive layer built on the graphs shares it, so the AST-to-graph mapping and its parent-climb live in one place.

Expand source code Browse git

class ElementLocator:
    """
    Locates an AST node among the per-body control-flow graphs of one script. Built once from the
    graph set, it maps an element to the graph and node that evaluate it — directly for an element a
    graph node stands for (`node_of`), or by climbing to the enclosing statement for one nested
    inside an expression (`locate`). Every flow-sensitive layer built on the graphs shares it, so the
    AST-to-graph mapping and its parent-climb live in one place.
    """

    def __init__(self, graphs: dict[int, ControlFlowGraph]):
        self._element_graph: dict[int, ControlFlowGraph] = {}
        self._owners = {id(graph.owner) for graph in graphs.values()}
        for graph in graphs.values():
            for node in graph.nodes:
                if node.element is not None:
                    self._element_graph[id(node.element)] = graph

    def node_of(self, element: Node) -> CfgNode | None:
        """
        The control-flow node standing for *element* in whichever graph owns it, or `None` when
        *element* is not itself a node the graphs represent.
        """
        graph = self._element_graph.get(id(element))
        return graph.node_of(element) if graph is not None else None

    def locate(self, element: Node) -> tuple[ControlFlowGraph, CfgNode] | None:
        """
        The graph and node that evaluate *element*, climbing out of any expression it is nested in to
        the enclosing statement or loop head, or `None` when it has no enclosing graph node.

        The climb stops at the body *element* is written in rather than continuing into the body
        around it. Something inside a body that no node of that body's graph stands for — the default
        of a parameter, an attribute on the body itself — is evaluated when that body is invoked, and
        the enclosing body's statement that mentions it is not that point. Answering with that
        statement orders the element against code the invocation may never run beside, which is the
        false claim the per-body split exists to avoid; `None` says the graphs do not place it, and a
        caller reads that as unknown.

        The body *element* is itself is not its own boundary: a block is a value written at a point
        in the body around it, so locating one climbs out to the statement that mentions it.
        """
        cursor: Node | None = element
        while cursor is not None:
            graph = self._element_graph.get(id(cursor))
            if graph is not None:
                node = graph.node_of(cursor)
                if node is not None:
                    return graph, node
            if cursor is not element and id(cursor) in self._owners:
                return None
            cursor = cursor.parent
        return None

Methods

def node_of(self, element)

The control-flow node standing for element in whichever graph owns it, or None when element is not itself a node the graphs represent.

Expand source code Browse git

def node_of(self, element: Node) -> CfgNode | None:
    """
    The control-flow node standing for *element* in whichever graph owns it, or `None` when
    *element* is not itself a node the graphs represent.
    """
    graph = self._element_graph.get(id(element))
    return graph.node_of(element) if graph is not None else None

def locate(self, element)

The graph and node that evaluate element, climbing out of any expression it is nested in to the enclosing statement or loop head, or None when it has no enclosing graph node.

The climb stops at the body element is written in rather than continuing into the body around it. Something inside a body that no node of that body's graph stands for — the default of a parameter, an attribute on the body itself — is evaluated when that body is invoked, and the enclosing body's statement that mentions it is not that point. Answering with that statement orders the element against code the invocation may never run beside, which is the false claim the per-body split exists to avoid; None says the graphs do not place it, and a caller reads that as unknown.

The body element is itself is not its own boundary: a block is a value written at a point in the body around it, so locating one climbs out to the statement that mentions it.

Expand source code Browse git

def locate(self, element: Node) -> tuple[ControlFlowGraph, CfgNode] | None:
    """
    The graph and node that evaluate *element*, climbing out of any expression it is nested in to
    the enclosing statement or loop head, or `None` when it has no enclosing graph node.

    The climb stops at the body *element* is written in rather than continuing into the body
    around it. Something inside a body that no node of that body's graph stands for — the default
    of a parameter, an attribute on the body itself — is evaluated when that body is invoked, and
    the enclosing body's statement that mentions it is not that point. Answering with that
    statement orders the element against code the invocation may never run beside, which is the
    false claim the per-body split exists to avoid; `None` says the graphs do not place it, and a
    caller reads that as unknown.

    The body *element* is itself is not its own boundary: a block is a value written at a point
    in the body around it, so locating one climbs out to the statement that mentions it.
    """
    cursor: Node | None = element
    while cursor is not None:
        graph = self._element_graph.get(id(cursor))
        if graph is not None:
            node = graph.node_of(cursor)
            if node is not None:
                return graph, node
        if cursor is not element and id(cursor) in self._owners:
            return None
        cursor = cursor.parent
    return None