Module refinery.lib.scripts.js.analysis.dominance

Dominance over the per-function control-flow graphs of the SemanticModel. One node dominates another when every path from the function's entry to the second passes through the first — so the first is guaranteed to have executed by the time the second runs. This is the flow-sensitive replacement for the constant inliner's statement-position heuristics: because an inlining candidate is single-assignment, "does the constant hold its value at this use?" is exactly "does the definition dominate the use?".

This is a fourth layer of the analysis substrate, built on the control-flow graphs in refinery.lib.scripts.js.analysis.cfg and keyed to AST node identity. Like those graphs it is per-function — a nested function is a separate graph — and conservative by construction: the exceptional edges the graph adds (a throw reaching a handler) are kept in the dominator computation, so a definition is reported as dominating a use only when it runs before that use on every path, including the ones that leave a try by throwing. A use a definition does not dominate, or one in a different function's graph, is answered conservatively as not-dominated.

The public surface — DominatorModel.dominates(), DominatorModel.strictly_dominates(), DominatorModel.cfg_node_of(), DominanceModel.runs_before_function(), build_dominance() — is keyed to AST nodes: an arbitrary node is located to the control-flow node of the statement (or loop head) that evaluates it, the granularity at which the graph reasons. strictly_dominates is the non-reflexive dominates, refusing a same-statement pair a caller must order. The ordering the queries below are built from is that of statements: dominance orders entering a statement, and a run reaching a handler because the statement threw has entered it without completing it, so a point such a run reaches is ordered after the statement only when the statement cannot throw at all. runs_before_function lifts that ordering across calls: it answers whether a definition runs before every invocation of a function, which a single graph cannot, by ordering the definition against the points the function is referenced and recursing up the call graph. runs_before and runs_before_all expose that same ordering against a single reference, or every reference in a set — the query a transform needs to confirm a value is established before every use that could observe it.

A statement may complete without evaluating every part of it: a store below && is skipped on the runs that complete x && (c = 5) without it. So every ordering query here answers whether the node it is asked about has run, completes_before included, and holds only where the statement evaluates the node on every run on which it completes. The exceptions are cannot_precede, which asks whether anything can run before a node on a run on which the node runs, and for which the statement is enough, and the dominance queries dominates, strictly_dominates and completes_before_node, which order the statements alone.

"""
Dominance over the per-function control-flow graphs of the
`refinery.lib.scripts.js.analysis.model.SemanticModel`. One node *dominates* another when every path
from the function's entry to the second passes through the first — so the first is guaranteed to have
executed by the time the second runs. This is the flow-sensitive replacement for the constant
inliner's statement-position heuristics: because an inlining candidate is single-assignment, "does the
constant hold its value at this use?" is exactly "does the definition dominate the use?".

This is a fourth layer of the analysis substrate, built on the control-flow graphs in
`refinery.lib.scripts.js.analysis.cfg` and keyed to AST node identity. Like those graphs it is
per-function — a nested function is a separate graph — and conservative by construction: the
exceptional edges the graph adds (a throw reaching a handler) are kept in the dominator computation, so
a definition is reported as dominating a use only when it runs before that use on *every* path,
including the ones that leave a `try` by throwing. A use a definition does not dominate, or one in a
different function's graph, is answered conservatively as not-dominated.

The public surface — `DominanceModel.dominates`, `DominanceModel.strictly_dominates`,
`DominanceModel.cfg_node_of`, `DominanceModel.runs_before_function`, `build_dominance` — is keyed to AST
nodes: an arbitrary node is located to the control-flow node of the statement (or loop head) that
evaluates it, the granularity at which the graph reasons. `strictly_dominates` is the non-reflexive
`dominates`, refusing a same-statement pair a caller must order. The ordering the queries below
are built from is that of statements: dominance orders *entering* a statement, and a run reaching
a handler because the statement threw has entered it without completing it, so a point such a run
reaches is ordered after the statement only when the statement cannot throw at all.
`runs_before_function` lifts that ordering across calls: it answers whether a definition runs
before every invocation of a function, which a single graph cannot, by ordering the definition
against the points the function is referenced and recursing up the call graph. `runs_before` and
`runs_before_all` expose that same ordering against a single reference, or every reference in a
set — the query a transform needs to confirm a value is established before every use that could
observe it.

A statement may complete without evaluating every part of it: a store below `&&` is skipped on the
runs that complete `x && (c = 5)` without it. So every ordering query here answers whether the
node it is asked about has run, `completes_before` included, and holds only where the statement
evaluates the node on every run on which it completes. The exceptions are `cannot_precede`, which
asks whether anything can run before a node on a run on which the node runs, and for which the
statement is enough, and the dominance queries `dominates`, `strictly_dominates` and
`completes_before_node`, which order the statements alone.
"""
from __future__ import annotations

from dataclasses import dataclass
from typing import Iterable, Iterator, Sequence

from refinery.lib.scripts import Node
from refinery.lib.scripts.analysis.cfg import Projection
from refinery.lib.scripts.analysis.dominance import DominatorModel
from refinery.lib.scripts.js.analysis.cfg import (
    CfgNode,
    ControlFlowGraph,
    ControlFlowModel,
    build_control_flow_model,
    evaluated_part,
)
from refinery.lib.scripts.js.analysis.evaluation import (
    enclosing_run,
    evaluated_whenever_completed,
)
from refinery.lib.scripts.js.analysis.intrinsics import (
    SPECIES_KEYS,
    IntrinsicWrites,
    build_intrinsic_writes,
)
from refinery.lib.scripts.js.analysis.model import (
    Binding,
    SemanticModel,
    enclosing_operator,
    is_invocation_target,
    is_member_write_target,
    is_simple_assignment_target,
)
from refinery.lib.scripts.js.keys import key_may_be, key_text
from refinery.lib.scripts.js.model import (
    FUNCTION_NODES,
    JsArrowFunctionExpression,
    JsAssignmentExpression,
    JsCallExpression,
    JsExportDefaultDeclaration,
    JsFunctionExpression,
    JsIdentifier,
    JsMemberExpression,
    JsNewExpression,
    JsObjectExpression,
    JsParenthesizedExpression,
    is_async_function,
    is_generator_function,
    object_member_access_runs_accessor,
    strip_parens,
    value_is_discarded,
)


@dataclass(eq=False)
class _HandOver:
    """
    The moment one local object reaches code that can call a function installed on it without
    reading the key the function is stored at. A method call on the object runs its callee with
    the object as `this`; where an accessor may run on the object's prototype chain, any access
    runs one with the object as `this`. The functions installed on the object share this node of
    the ordering graph, whose *points* are those accesses, so the accesses are listed and ordered
    once for all of them (`DominanceModel._member_reference_points`). The other points of such a
    function name it and belong to it alone: the *reads* of its key, the reads at a key that is
    not statically known (*unnamed*), the reflective *surfaces* that can name the object, and the
    end of the script where an importer reaches the object (*exported*).
    """
    points: list[Node]
    reads: dict[str, list[Node]]
    unnamed: list[Node]
    surfaces: list[Node]
    exported: bool


_PROTO = frozenset({'__proto__'})


def _may_name_the_prototype(access: JsMemberExpression) -> bool:
    """
    Whether *access* may read or write the prototype of the object it accesses, or the constructor
    whose `prototype` that is: its key is one of
    `refinery.lib.scripts.js.analysis.intrinsics.SPECIES_KEYS`, or not statically known.
    """
    return key_may_be(access, SPECIES_KEYS)


def _may_hand_out_the_prototype(access: JsMemberExpression) -> bool:
    """
    Whether *access* may hand out the prototype of the object it reads for code to install an
    accessor on (`_may_name_the_prototype`). A write into the key only swaps the prototype of this
    one object, and a call only runs what the key holds, so neither hands the prototype out; any
    other use of the value, a member access or install through it included, may.
    """
    return (
        _may_name_the_prototype(access)
        and not is_invocation_target(access)
        and not is_member_write_target(access)
    )


class DominanceModel(DominatorModel):
    """
    Dominator relations for the per-function control-flow graphs of one script, built over a
    `refinery.lib.scripts.js.analysis.model.SemanticModel`. Ask whether one AST node is guaranteed to
    execute before another with `dominates`. Build through `build_dominance`.

    The ordering across calls reads three facts about what lies outside the text: *intrinsic_writes*
    says whether the program writes the prototype chain a plain object reads through, and the
    semantic model what the file is and which of its bindings code outside it may reach
    (`refinery.lib.scripts.js.analysis.model.SemanticModel.callable_from_outside`).
    """

    def __init__(
        self,
        model: SemanticModel,
        control_flow: ControlFlowModel | None = None,
        *,
        intrinsic_writes: IntrinsicWrites | None = None,
    ):
        flow = control_flow if control_flow is not None else build_control_flow_model(model.root)
        super().__init__(flow)
        self.model = model
        if intrinsic_writes is None:
            intrinsic_writes = build_intrinsic_writes(model)
        self.intrinsic_writes = intrinsic_writes
        self._reference_points_cache: dict[Node, list[Node | _HandOver] | None] = {}
        self._invocation_orders: dict[Node, dict[Node | _HandOver, bool]] = {}
        self._entered_from: dict[Node, dict[Node, bool]] = {}
        self._hand_overs: dict[Binding, _HandOver | None] = {}
        self._runs_with_its_node_cache: dict[Node, bool] = {}
        self._lifts_cache: dict[Node, list[tuple[Node, Node]]] = {}

    def completes_before(self, definition: Node, point: Node) -> bool:
        """
        Whether *definition* has run on every run that reaches *point*, both in one graph: the
        statement evaluating it evaluates it whenever it completes (`_runs_with_its_node`), and has
        completed (`_statement_completes_before`).
        """
        return (
            self._runs_with_its_node(definition)
            and self._statement_completes_before(definition, point)
        )

    def _statement_completes_before(self, definition: Node, point: Node) -> bool:
        """
        Whether the statement evaluating *definition* has completed on every run that reaches the
        statement evaluating *point*, both in one graph. Dominance alone orders entering the first
        statement: in `try { r = window; } catch (e) {} use(r);` the statement `r = window`
        dominates `use(r)`, yet the handler runs exactly when reading `window` threw and `r` was
        never written. So a point
        `refinery.lib.scripts.analysis.cfg.ControlFlowGraph.reached_after_a_throw` places after a
        throw out of the statement is ordered after it only when
        `refinery.lib.scripts.js.analysis.model.SemanticModel.statement_cannot_throw` holds for the
        statement. Not reflexive: a point sharing the node is refused, since the graph orders the
        parts of one node no further; a declarator is a node of its own
        (`refinery.lib.scripts.js.analysis.cfg.evaluated_part`), the operands of an expression are
        not. The script root as *point* stands for the end of the script
        (`_completes_before_the_end`).
        """
        if point is self.model.root:
            return self._completes_before_the_end(definition)
        located = self.locate_pair(definition, point)
        return located is not None and self.completes_before_node(*located)

    def _completes_before_the_end(self, definition: Node) -> bool:
        """
        Whether the statement evaluating *definition* has completed on every run that finishes the
        script, the point where an importer outside every import cycle calls what a module
        exports: `_completes_before_exit` of the script's graph. A run that ends in a throw finishes
        nothing, since no importer runs after a module whose body threw.
        """
        return self._completes_before_exit(self.model.root, definition)

    def _completes_before_exit(self, activation: Node, definition: Node) -> bool:
        """
        Whether the statement evaluating *definition* has completed on every run of *activation*
        that ends without a throw: every predecessor a completed run enters the exit of its graph
        from is that statement, or one it `completes_before_node`. A predecessor joined to the exit
        both plainly and by an error edge, as an empty `finally` is, is one such run.
        """
        graph = self._flow.graph_of(activation)
        located = self.locate(definition)
        if graph is None or located is None or located[0] is not graph:
            return False
        node = located[1]
        return all(
            source is node or self.completes_before_node(graph, node, source)
            for source in graph.exit.predecessors
            if graph.completes_into(source, graph.exit)
        )

    def completes_before_node(self, graph: ControlFlowGraph, a: CfgNode, b: CfgNode) -> bool:
        """
        The counterpart of `_statement_completes_before` for a caller that has already located the
        two nodes in *graph*. Whether *a* can throw is asked of what its node evaluates
        (`refinery.lib.scripts.js.analysis.cfg.evaluated_part`).
        """
        if a is b or not self.dominates_node(graph, a, b, Projection.MAY):
            return False
        thrown = graph.reached_after_a_throw(a)
        if id(b) not in thrown:
            return True
        return a.element is not None and self.model.statement_cannot_throw(
            evaluated_part(graph, a.element)
        )

    def runs_before_function(self, definition: Node, function: Node) -> bool:
        """
        Whether *definition* is guaranteed to have executed before any invocation of *function* — so
        a value established at *definition* holds throughout every call of *function*, and may be
        inlined into its body. The reasoning rests on one fact: a function cannot be invoked before
        a reference to it has been evaluated. Its reference points are its own creation, for an
        anonymous function expression, or the uses of its name, for a named binding; no invocation
        can precede the earliest of them. So *definition* runs before every invocation exactly when
        it runs before every reference point — and that, per point, is `completes_before` when the
        point lies in *definition*'s own function, or the same question applied to the function the
        point lies in, recursing up the call graph. Where *definition* stands in a function the
        program calls where it writes it, a point outside that function is ordered by the call
        instead, once every return of the function follows *definition* (`_lifts`). The ordering is
        *strict*: a reference sharing the definition's node — an earlier operand of a sequence
        evaluated before it — is not accepted, since dominance is reflexive and orders the parts
        of one node no further; a declarator before it is a node of its own and is ordered. A
        reference's function is its nearest enclosing function (its `_activation_of`), so a use in
        a function's parameter defaults is attributed to that function's invocation, not to the
        statement that declares it. Functions that reach each other's invocations — a recursive
        function, mutually recursive ones — are answered together
        (`_solve_invocation_orders`). This is the interprocedural counterpart of `dominates`, and
        the sound replacement for ordering a cross-function inline by statement position.

        Conservatively `False` when a reference point cannot be ordered or enumerated: the named
        binding is reassigned or redeclared (its references no longer pin one function), code
        outside the file can call the function, or a reference lies in a function that itself runs
        too late or escapes, and when the statement evaluating *definition* may complete without
        evaluating it (`_runs_with_its_node`). A function neither referenced nor within reflection's
        reach is vacuously safe.
        """
        return self._runs_with_its_node(definition) and self._ordered(definition, function)

    def runs_before_every_invocation(self, definition: Node, function: Node) -> bool:
        """
        Whether *definition* is guaranteed to run before every invocation of *function*, and
        *function* is entered from the activation that runs *definition*, or from one a call it
        lifts to runs in (`_entered`, `_lifts`) — `runs_before_function` with the vacuity
        refused. A reader nothing in the file obtains, or one only code nothing obtains calls,
        answers the ordering question over no invocation at all and passes vacuously; a value
        established against no invocation is established for no read, so such a reader does not
        qualify. An object handed to code does not enter the
        methods stored on it. An anonymous function expression created in that activation is
        entered by its own creation, the one point no invocation can precede.
        """
        if not self.runs_before_function(definition, function):
            return False
        return any(self._entered(owner, function) for _, owner in self._lifts(definition))

    def runs_before(self, definition: Node, reference: Node) -> bool:
        """
        Whether *definition* is guaranteed to have executed before *reference* is evaluated — the
        single-reference form of the ordering `runs_before_function` applies per reference point.
        When *reference* shares *definition*'s activation this is `completes_before` (a reference
        sharing *definition*'s node is not accepted, since dominance is reflexive and orders the
        parts of one node no further); when *reference* lies inside a function that cannot be
        invoked until after *definition*, it is the interprocedural runs-before-function query,
        recursing up the call graph. Conservatively `False` whenever the
        ordering cannot be established — a reference in an activation that may run before
        *definition*, a reference point that cannot be enumerated, or a statement that may complete
        without evaluating *definition* (`_runs_with_its_node`) — so a caller may treat `True` as
        a guarantee.
        """
        return (
            self._runs_with_its_node(definition)
            and self._runs_after(definition, reference)
        )

    def runs_before_all(self, definition: Node, references: Iterable[Node]) -> bool:
        """
        Whether *definition* is guaranteed to run before every reference in *references* — `runs_before`
        for each, vacuously `True` for an empty iterable.
        """
        if not self._runs_with_its_node(definition):
            return False
        return all(self._runs_after(definition, reference) for reference in references)

    def cannot_precede(self, reference: Node, anchor: Node) -> bool:
        """
        Whether *reference* cannot run before *anchor* on any run on which *anchor* runs: the
        statement evaluating *anchor* has completed before *reference* runs, as `runs_before` asks
        without asking whether that statement evaluates *anchor* at all. A run that skips *anchor*
        has nothing for *reference* to precede, so a fold made at *anchor* holds wherever it is
        evaluated as long as no such *reference* comes first. An *anchor* in a part that runs at a
        time of its own, as the initializer of a field does each time an instance is constructed,
        is located in the graph of that run and ordered there.
        """
        located = self.locate(anchor)
        if located is None or located[1].element is None:
            return False
        return self._runs_after(anchor, reference)

    def callee_established_before(self, call: JsCallExpression | JsNewExpression) -> bool:
        """
        Whether the name *call* reads its callee through holds its `singular_value` before *call*
        runs (`binding_established_before`). A function declared in a block has two names, each in
        place from a point of its own, which is why the name is the one the call reads and not the
        one the function declares. `False` for a callee that is no name.
        """
        callee = strip_parens(call.callee)
        if not isinstance(callee, JsIdentifier):
            return False
        return self.binding_established_before(self.model.resolve(callee), call)

    def binding_established_before(self, binding: Binding | None, reference: Node) -> bool:
        """
        Whether *binding*'s `singular_value` is in place before *reference* runs: every node in its
        `SemanticModel.binding_establishment_sites` executes first. A hoisted function declaration has no
        sites and qualifies unconditionally; a `var`/`let`/`const` initializer, a class declaration, or a
        lone assignment (`f = function(){}`, the form namespace flattening leaves) qualifies only where
        each establishing node runs before *reference*. `False` when the binding holds no single orderable
        value, so its presence cannot be ordered — the query a consumer needs before trusting a value that
        would otherwise be read out of its temporal dead zone or before its establishing write.
        A site the statement or loop head holding it evaluates on some runs only orders nothing
        (`runs_before`): `x && (T = [])` completes without writing `T`.
        """
        sites = self.model.binding_establishment_sites(binding)
        if sites is None:
            return False
        return all(self.runs_before(site, reference) for site in sites)

    def _runs_with_its_node(self, site: Node) -> bool:
        """
        Whether *site* has run whenever the control-flow node evaluating it has completed. A graph
        has a node for a statement, a loop head and a declarator and none for the parts of an
        expression, so an ordering against that node answers for *site* only where the node
        evaluates it on every run
        (`refinery.lib.scripts.js.analysis.evaluation.evaluated_whenever_completed`). Memoized by
        identity, since every ordering query of one definition asks it again for each reference.
        """
        cached = self._runs_with_its_node_cache.get(site)
        if cached is None:
            located = self.locate(site)
            element = None if located is None else located[1].element
            cached = element is not None and evaluated_whenever_completed(site, element)
            self._runs_with_its_node_cache[site] = cached
        return cached

    def past_dead_zone(self, binding: Binding, reference: Node) -> bool:
        """
        Whether *reference* is guaranteed to run past *binding*'s temporal dead zone: every
        declaration of this `let`/`const`/`class` binding executes first, so a read at *reference*
        cannot raise a `ReferenceError`. Distinct from `binding_established_before`, which orders
        the singular value's establishing write: a dead zone ends at the DECLARATION, not at the
        first value assignment, so a `let` declared before *reference* but reassigned afterward is
        past its dead zone here while `binding_established_before` — reasoning about the value —
        answers `False`. `False` when the binding carries no declaration to order, so the dead
        zone's end cannot be proven.
        """
        return bool(binding.declarations) and all(
            self.runs_before(site, reference) for site in binding.declarations
        )

    def _ordered(self, definition: Node, function: Node) -> bool:
        """
        Whether *definition* runs before every invocation of *function*. Answers are kept per
        definition and every one kept is final, so each query of the same definition shares the
        functions an earlier one solved.
        """
        orders = self._invocation_orders.setdefault(definition, {})
        ordered = orders.get(function)
        if ordered is None:
            self._solve_invocation_orders(definition, function, orders)
            ordered = orders[function]
        return ordered

    def _solve_invocation_orders(
        self,
        definition: Node,
        function: Node,
        orders: dict[Node | _HandOver, bool],
    ):
        """
        Solve `_ordered` for *function* and for every function a reference point of it lies in,
        one strongly connected component of that graph at a time: Tarjan's algorithm, kept on an
        explicit stack so a long chain of calls cannot exhaust the interpreter's. A point that is a
        `_HandOver` is a node of the graph in its own right, shared by every function installed on
        one object. The members of one component reach each other's invocations and get one
        answer: they are ordered when every point outside the component is, one in an activation
        that runs the definition or a call returning only once it has (`_site_in`) by
        `_statement_completes_before` of that site, one in another function or hand-over by that
        node's answer. A function expression such an activation creates only after the site has
        completed is ordered without its points (`_created_after`).

        This is sound because the earliest invocation of any function in a component follows a
        reference to it that nothing in the component can have evaluated yet, so that reference is
        one of the points outside it. A node stops at the first point it cannot order: that point
        lies outside every component the node belongs to, so it leaves each of them unordered
        however the other points stand. Every other component is stored only once every component
        it reaches is, which is what makes each stored answer final.
        """
        index: dict[Node | _HandOver, int] = {}
        lowlink: dict[Node | _HandOver, int] = {}
        ordered: dict[Node | _HandOver, bool] = {}
        stack: list[Node | _HandOver] = []
        frames: list[tuple[Node | _HandOver, Iterator[Node | _HandOver]]] = []

        def open_frame(opened: Node | _HandOver):
            index[opened] = lowlink[opened] = len(index)
            stack.append(opened)
            if self._created_after(definition, opened):
                points = ()
            else:
                points = self._reference_points(opened)
            ordered[opened] = points is not None
            frames.append((opened, iter(points or ())))

        open_frame(function)
        while frames:
            current, points = frames[-1]
            for point in points:
                if not ordered[current]:
                    break
                if isinstance(point, _HandOver):
                    activation: Node | _HandOver = point
                else:
                    activation = self._activation_of(point)
                    if (site := self._site_in(definition, activation)) is not None:
                        if not self._statement_completes_before(site, point):
                            ordered[current] = False
                        continue
                    if activation is self.model.root:
                        ordered[current] = False
                        continue
                if (known := orders.get(activation)) is not None:
                    if not known:
                        ordered[current] = False
                elif activation not in index:
                    open_frame(activation)
                    break
                else:
                    lowlink[current] = min(lowlink[current], index[activation])
            if frames[-1][0] is not current:
                continue
            frames.pop()
            if lowlink[current] == index[current]:
                members: list[Node | _HandOver] = []
                while not members or members[-1] is not current:
                    members.append(stack.pop())
                answer = all(ordered[member] for member in members)
                for member in members:
                    orders[member] = answer
            if frames:
                parent = frames[-1][0]
                if current in orders:
                    ordered[parent] = ordered[parent] and orders[current]
                else:
                    lowlink[parent] = min(lowlink[parent], lowlink[current])

    def _created_after(self, definition: Node, activation: Node | _HandOver) -> bool:
        """
        Whether *activation* is a function expression created, in an activation `_site_in` places
        *definition* in, only once that site has completed. No copy of the function exists before
        that, so none is invoked before it, whatever its reference points are: a method call that
        hands its object over before the method is stored there cannot call the method yet. A
        function declaration exists from the start of its activation and never qualifies.
        """
        if not isinstance(activation, (JsFunctionExpression, JsArrowFunctionExpression)):
            return False
        site = self._site_in(definition, self._activation_of(activation))
        return site is not None and self._statement_completes_before(site, activation)

    def _entered(self, owner: Node, function: Node) -> bool:
        """
        Whether a reference point of *function* that names it lies in *owner*, or in a function
        entered from *owner* the same way: a read of its name or of the key it is stored at, a
        reflective surface that can name it, the end of the script where an importer calls it, or
        its own creation for a function bound to nothing. The accesses of a `_HandOver` hand an
        object on and never enter a function, so a method no code in the file obtains stays
        unentered however often its object is handed over. Answers are kept per activation, since
        the question does not depend on the definition.
        """
        known = self._entered_from.setdefault(owner, {})
        answer = known.get(function)
        if answer is not None:
            return answer
        seen: set[Node] = {function}
        pending: list[Node] = [function]
        while pending:
            current = pending.pop()
            for point in self._reference_points(current) or ():
                if isinstance(point, _HandOver):
                    continue
                activation = self._activation_of(point)
                if activation is owner or known.get(activation) is True:
                    known[function] = True
                    return True
                if (
                    activation is not self.model.root
                    and activation not in seen
                    and known.get(activation) is None
                ):
                    seen.add(activation)
                    pending.append(activation)
        for node in seen:
            known[node] = False
        return False

    def _reference_points(self, activation: Node | _HandOver) -> Sequence[Node | _HandOver] | None:
        """
        The points no invocation of *activation* can precede, or `None` when they cannot be
        enumerated. A `_HandOver` holds its own points. For a function pinned to its names
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.function_names`) these are the
        value-reads of those names — a read must be evaluated before the value it denotes can be
        called — together with the opaque reflective surface sites that could invoke it by name
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.reflection_surface_sites`): a direct
        `eval`, `Function`, a string timer, or a dynamic global access cannot invoke the function
        before the surface that grants the capability has run, so each surface is itself a point no
        invocation precedes, ranked exactly like a read. The enumeration is `None` when the name is
        redeclared, reassigned to another value so a read no longer pins this one function
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.binding_pinned_to`), or resolved
        inside a dynamic scope a `with` body governs, whose
        `refinery.lib.scripts.js.analysis.model.Binding.dynamic_refs` entry is unorderable; this
        mirrors the escape verdict
        `refinery.lib.scripts.js.analysis.effects.EffectModel.function_escapes` draws from the same
        fact. A surface lexically inside the function is dropped: it cannot trigger the function's
        first invocation, only a re-entrant one, so it never bounds the ordering. A function
        installed as a property of a non-escaping local object (`_member_reference_points`) is
        enumerated instead by the points that name it and the object's `_HandOver`; this is
        consulted first, so a namespace method ordered by its call sites is not mistaken for an
        anonymous closure ordered by its creation.

        A function is ordered by its creation alone, the one point no invocation can precede, when
        it is bound to no name and matches neither pattern, and when the value of the assignment
        installing it flows on (`_installed_value_escapes`). So is the initializer of a field: it
        runs at the constructions of its class, none of which precedes the class statement creating
        it, and one that statement makes itself, in a static block, shares its node. A function
        code outside the file can call while the file runs
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.callable_from_outside`) has no
        enumeration at all. One an importer outside every import cycle can call has the end of the
        script as one more point, the script root standing for it (`_statement_completes_before`),
        since such an importer calls in only once the module has finished, and so has one code
        loading a library calls by name
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.reached_from_outside`).

        Memoized by identity: the enumeration is a pure function of *activation* and the model,
        both fixed for the model's lifetime — the whole DominanceModel is rebuilt when the tree
        version advances — so every `runs_before*` caller shares one result per function instead of
        recomputing it per reference and per query.
        """
        if isinstance(activation, _HandOver):
            return activation.points
        cache = self._reference_points_cache
        if activation not in cache:
            cache[activation] = self._compute_reference_points(activation)
        return cache[activation]

    def _compute_reference_points(self, function: Node) -> list[Node | _HandOver] | None:
        if not isinstance(function, FUNCTION_NODES):
            return [function]
        names = self.model.function_names(function)
        if self.model.callable_from_outside(function):
            return None
        if self._installed_value_escapes(function):
            return [function]
        if names is None and isinstance(function.parent, JsExportDefaultDeclaration):
            return [self.model.root]
        member_points = self._member_reference_points(function)
        if member_points is not None:
            return member_points
        if names is None:
            return [function]
        points: list[Node | _HandOver] = []
        for name in names.bindings:
            if (
                name.dynamic_refs
                or len(name.declarations) != 1
                or not self.model.binding_pinned_to(name, function)
            ):
                return None
            points.extend(names.reads_of(name))
            points.extend(
                site
                for site in self.model.reflection_surface_sites(name)
                if not site.is_descendant_of(function)
            )
            if name.exported or self.model.reached_from_outside(name):
                points.append(self.model.root)
        return points

    @staticmethod
    def _installed_value_escapes(function: Node) -> bool:
        """
        Whether *function* is the right side of an assignment whose own value the program goes on
        to use: chained into another name or key (`h = NS.g = function(){}`), called on the spot,
        or passed on as an argument. That value reaches code through no read of the name or of the
        key the assignment installs into, so neither enumeration lists it.
        """
        parent = function.parent
        return (
            isinstance(parent, JsAssignmentExpression)
            and parent.right is function
            and not value_is_discarded(parent)
        )

    def _member_reference_points(self, function: Node) -> list[Node | _HandOver] | None:
        """
        The points no invocation of *function* can precede when it is installed as a property of a
        non-escaping local object, or `None` where that pattern does not hold. *function* is the
        value of a `BASE.key = function` statement whose `BASE` resolves to a binding with a
        `_HandOver`, one holding a single object literal that never escapes as a bare value
        (`_hand_over`). The callable can then be obtained in two ways only: by reading `BASE.key`,
        or by code the object is handed to, which reads the key itself. The points are the
        hand-over, the reads of `key` and of keys that are not statically known, the reflective
        surfaces that could name the binding, and the end of the script for an object an importer
        reaches. A write of `key` never obtains the value and is not a point. An install at the key
        `__proto__` makes *function* the object's prototype rather than a property of it, so every
        inherited read reaches it, and the pattern does not hold.
        """
        parent = function.parent
        if not (
            isinstance(parent, JsAssignmentExpression)
            and parent.operator == '='
            and parent.right is function
        ):
            return None
        target = strip_parens(parent.left)
        if not isinstance(target, JsMemberExpression) or not isinstance(target.object, JsIdentifier):
            return None
        key = key_text(target)
        if key is None or key_may_be(target, _PROTO):
            return None
        binding = self.model.resolve(target.object)
        if binding is None:
            return None
        hand_over = self._hand_over(binding)
        if hand_over is None:
            return None
        points: list[Node | _HandOver] = [hand_over]
        points.extend(hand_over.reads.get(key, ()))
        points.extend(hand_over.unnamed)
        points.extend(site for site in hand_over.surfaces if not site.is_descendant_of(function))
        if hand_over.exported:
            points.append(self.model.root)
        return points

    def _hand_over(self, binding: Binding) -> _HandOver | None:
        """
        The `_HandOver` of the object *binding* holds, computed once per binding, or `None` where
        its accesses cannot all be enumerated: the binding holds no single object literal
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.singular_value`), one of its reads is
        not the object of a member access, a `with` could rename it (a
        `refinery.lib.scripts.js.analysis.model.Binding.dynamic_refs` entry), an importer can reach
        it before the module has finished
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.importer_may_run_first`), or a host
        can reach it by name
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.named_by_the_host`).

        An access hands the object to code when it is a method call in any form, whose callee
        receives the object as `this`, and when it reads or writes the object's prototype
        (`_may_name_the_prototype`), after which the object may inherit accessors from another
        prototype. Every access does, the establishing writes included, when an accessor may run on
        the object's prototype chain and receive the object as `this`, or at its own key the very
        function being stored there. That is so when the literal declares an accessor or a prototype
        (`refinery.lib.scripts.js.model.object_member_access_runs_accessor`); when the program
        writes the prototype chain of a plain object
        (`refinery.lib.scripts.js.analysis.intrinsics.IntrinsicWrites.chain_roots_unwritten`); when
        it holds code this analysis cannot read, which may install one anywhere
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.has_reflection_surface`), the term
        `refinery.lib.scripts.js.analysis.effects.EffectModel.read_chain_intact` asks of a plain
        read as well; and when an access of the object may hand out its prototype
        (`_may_hand_out_the_prototype`). An accessor installed through what that access yields lands
        on a prototype every later object of the same kind inherits, the objects later runs of the
        same code create included, so a point at the access alone would not order those.

        An accessor can receive the object at no other moment, since the object never escapes as
        a bare value. Nothing can call a function through the object before the access that hands
        the object over has run, so such an access is a point rather than a reason to refuse, for
        the reason a reflective surface is one.
        """
        if binding in self._hand_overs:
            return self._hand_overs[binding]
        hand_over = self._compute_hand_over(binding)
        self._hand_overs[binding] = hand_over
        return hand_over

    def _compute_hand_over(self, binding: Binding) -> _HandOver | None:
        literal = self.model.singular_value(binding)
        if not isinstance(literal, JsObjectExpression):
            return None
        if (
            binding.dynamic_refs
            or self.model.importer_may_run_first(binding)
            or self.model.named_by_the_host(binding)
        ):
            return None
        accesses: list[JsMemberExpression] = []
        for read in binding.reads:
            node = read
            access = node.parent
            while isinstance(access, JsParenthesizedExpression):
                node, access = access, access.parent
            if not isinstance(access, JsMemberExpression) or access.object is not node:
                return None
            accesses.append(access)
        every_access_runs_code = (
            object_member_access_runs_accessor(literal)
            or not self.intrinsic_writes.chain_roots_unwritten(dict)
            or self.model.has_reflection_surface()
            or any(_may_hand_out_the_prototype(access) for access in accesses)
        )
        points: list[Node] = []
        reads: dict[str, list[Node]] = {}
        unnamed: list[Node] = []
        for access in accesses:
            if (
                every_access_runs_code
                or is_invocation_target(access)
                or _may_name_the_prototype(access)
            ):
                points.append(access)
            if is_simple_assignment_target(access):
                continue
            if (key := key_text(access)) is None:
                unnamed.append(access)
            else:
                reads.setdefault(key, []).append(access)
        return _HandOver(
            points,
            reads,
            unnamed,
            self.model.reflection_surface_sites(binding),
            binding.exported,
        )

    def _runs_after(self, definition: Node, point: Node) -> bool:
        owner = self._activation_of(point)
        if (site := self._site_in(definition, owner)) is not None:
            return self._statement_completes_before(site, point)
        if owner is not self.model.root:
            return self._ordered(definition, owner)
        return False

    def _site_in(self, definition: Node, activation: Node | _HandOver) -> Node | None:
        """
        The node of *activation* whose completion orders *definition*: *definition* itself where
        *activation* runs it, and otherwise the call that runs a function *definition* stands in,
        climbing outward through such calls (`_lifts`). `None` where *activation* is not on that
        climb.
        """
        for site, owner in self._lifts(definition):
            if owner is activation:
                return site
        return None

    def _lifts(self, definition: Node) -> list[tuple[Node, Node]]:
        """
        *definition* with its activation, followed by every call it lifts to: where a function
        expression the program calls where it writes it holds the site so far, and every run of the
        function that returns rather than throws has evaluated the site
        (`_completes_before_exit`), the call has returned only after the site ran, so the call,
        in its own activation, orders the site for every point there. A generator or an `async`
        function returns before its body has run, and holds no such site; the statement evaluating
        the call must evaluate it whenever it completes (`_runs_with_its_node`). Memoized.
        """
        if (lifts := self._lifts_cache.get(definition)) is not None:
            return lifts
        site = definition
        owner = self._activation_of(definition)
        lifts = [(site, owner)]
        while (
            isinstance(owner, (JsFunctionExpression, JsArrowFunctionExpression))
            and not is_generator_function(owner)
            and not is_async_function(owner)
            and isinstance(call := enclosing_operator(owner), JsCallExpression)
            and strip_parens(call.callee) is owner
            and self._completes_before_exit(owner, site)
            and self._runs_with_its_node(call)
        ):
            site = call
            owner = self._activation_of(call)
            lifts.append((site, owner))
        self._lifts_cache[definition] = lifts
        return lifts

    def _activation_of(self, element: Node) -> Node:
        """
        The run owner whose invocation evaluates *element*
        (`refinery.lib.scripts.js.analysis.evaluation.enclosing_run`), or the script root when no
        run owner does. This is the unit `runs_before_function` reasons about: a reference in a
        function's body *or its parameter defaults* runs when that function is invoked, and one in
        the initializer of a field when an instance is constructed, so each attributes to its run,
        never to the statement that merely declares it in the enclosing graph.
        """
        run = enclosing_run(element)
        return run if run is not None else self.model.root


def build_dominance(
    model: SemanticModel,
    control_flow: ControlFlowModel | None = None,
    *,
    intrinsic_writes: IntrinsicWrites | None = None,
) -> DominanceModel:
    """
    Build the `DominanceModel` for a script's `refinery.lib.scripts.js.analysis.model.SemanticModel`,
    reusing *control_flow* and *intrinsic_writes* when the caller has them to share, or building
    fresh ones when they are `None`.
    """
    return DominanceModel(model, control_flow, intrinsic_writes=intrinsic_writes)

Functions

def build_dominance(model, control_flow=None, *, intrinsic_writes=None)

Build the DominanceModel for a script's SemanticModel, reusing control_flow and intrinsic_writes when the caller has them to share, or building fresh ones when they are None.

Expand source code Browse git

def build_dominance(
    model: SemanticModel,
    control_flow: ControlFlowModel | None = None,
    *,
    intrinsic_writes: IntrinsicWrites | None = None,
) -> DominanceModel:
    """
    Build the `DominanceModel` for a script's `refinery.lib.scripts.js.analysis.model.SemanticModel`,
    reusing *control_flow* and *intrinsic_writes* when the caller has them to share, or building
    fresh ones when they are `None`.
    """
    return DominanceModel(model, control_flow, intrinsic_writes=intrinsic_writes)

Classes

class DominanceModel (model, control_flow=None, *, intrinsic_writes=None)

Dominator relations for the per-function control-flow graphs of one script, built over a SemanticModel. Ask whether one AST node is guaranteed to execute before another with dominates. Build through build_dominance().

The ordering across calls reads three facts about what lies outside the text: intrinsic_writes says whether the program writes the prototype chain a plain object reads through, and the semantic model what the file is and which of its bindings code outside it may reach (SemanticModel.callable_from_outside()).

Expand source code Browse git

class DominanceModel(DominatorModel):
    """
    Dominator relations for the per-function control-flow graphs of one script, built over a
    `refinery.lib.scripts.js.analysis.model.SemanticModel`. Ask whether one AST node is guaranteed to
    execute before another with `dominates`. Build through `build_dominance`.

    The ordering across calls reads three facts about what lies outside the text: *intrinsic_writes*
    says whether the program writes the prototype chain a plain object reads through, and the
    semantic model what the file is and which of its bindings code outside it may reach
    (`refinery.lib.scripts.js.analysis.model.SemanticModel.callable_from_outside`).
    """

    def __init__(
        self,
        model: SemanticModel,
        control_flow: ControlFlowModel | None = None,
        *,
        intrinsic_writes: IntrinsicWrites | None = None,
    ):
        flow = control_flow if control_flow is not None else build_control_flow_model(model.root)
        super().__init__(flow)
        self.model = model
        if intrinsic_writes is None:
            intrinsic_writes = build_intrinsic_writes(model)
        self.intrinsic_writes = intrinsic_writes
        self._reference_points_cache: dict[Node, list[Node | _HandOver] | None] = {}
        self._invocation_orders: dict[Node, dict[Node | _HandOver, bool]] = {}
        self._entered_from: dict[Node, dict[Node, bool]] = {}
        self._hand_overs: dict[Binding, _HandOver | None] = {}
        self._runs_with_its_node_cache: dict[Node, bool] = {}
        self._lifts_cache: dict[Node, list[tuple[Node, Node]]] = {}

    def completes_before(self, definition: Node, point: Node) -> bool:
        """
        Whether *definition* has run on every run that reaches *point*, both in one graph: the
        statement evaluating it evaluates it whenever it completes (`_runs_with_its_node`), and has
        completed (`_statement_completes_before`).
        """
        return (
            self._runs_with_its_node(definition)
            and self._statement_completes_before(definition, point)
        )

    def _statement_completes_before(self, definition: Node, point: Node) -> bool:
        """
        Whether the statement evaluating *definition* has completed on every run that reaches the
        statement evaluating *point*, both in one graph. Dominance alone orders entering the first
        statement: in `try { r = window; } catch (e) {} use(r);` the statement `r = window`
        dominates `use(r)`, yet the handler runs exactly when reading `window` threw and `r` was
        never written. So a point
        `refinery.lib.scripts.analysis.cfg.ControlFlowGraph.reached_after_a_throw` places after a
        throw out of the statement is ordered after it only when
        `refinery.lib.scripts.js.analysis.model.SemanticModel.statement_cannot_throw` holds for the
        statement. Not reflexive: a point sharing the node is refused, since the graph orders the
        parts of one node no further; a declarator is a node of its own
        (`refinery.lib.scripts.js.analysis.cfg.evaluated_part`), the operands of an expression are
        not. The script root as *point* stands for the end of the script
        (`_completes_before_the_end`).
        """
        if point is self.model.root:
            return self._completes_before_the_end(definition)
        located = self.locate_pair(definition, point)
        return located is not None and self.completes_before_node(*located)

    def _completes_before_the_end(self, definition: Node) -> bool:
        """
        Whether the statement evaluating *definition* has completed on every run that finishes the
        script, the point where an importer outside every import cycle calls what a module
        exports: `_completes_before_exit` of the script's graph. A run that ends in a throw finishes
        nothing, since no importer runs after a module whose body threw.
        """
        return self._completes_before_exit(self.model.root, definition)

    def _completes_before_exit(self, activation: Node, definition: Node) -> bool:
        """
        Whether the statement evaluating *definition* has completed on every run of *activation*
        that ends without a throw: every predecessor a completed run enters the exit of its graph
        from is that statement, or one it `completes_before_node`. A predecessor joined to the exit
        both plainly and by an error edge, as an empty `finally` is, is one such run.
        """
        graph = self._flow.graph_of(activation)
        located = self.locate(definition)
        if graph is None or located is None or located[0] is not graph:
            return False
        node = located[1]
        return all(
            source is node or self.completes_before_node(graph, node, source)
            for source in graph.exit.predecessors
            if graph.completes_into(source, graph.exit)
        )

    def completes_before_node(self, graph: ControlFlowGraph, a: CfgNode, b: CfgNode) -> bool:
        """
        The counterpart of `_statement_completes_before` for a caller that has already located the
        two nodes in *graph*. Whether *a* can throw is asked of what its node evaluates
        (`refinery.lib.scripts.js.analysis.cfg.evaluated_part`).
        """
        if a is b or not self.dominates_node(graph, a, b, Projection.MAY):
            return False
        thrown = graph.reached_after_a_throw(a)
        if id(b) not in thrown:
            return True
        return a.element is not None and self.model.statement_cannot_throw(
            evaluated_part(graph, a.element)
        )

    def runs_before_function(self, definition: Node, function: Node) -> bool:
        """
        Whether *definition* is guaranteed to have executed before any invocation of *function* — so
        a value established at *definition* holds throughout every call of *function*, and may be
        inlined into its body. The reasoning rests on one fact: a function cannot be invoked before
        a reference to it has been evaluated. Its reference points are its own creation, for an
        anonymous function expression, or the uses of its name, for a named binding; no invocation
        can precede the earliest of them. So *definition* runs before every invocation exactly when
        it runs before every reference point — and that, per point, is `completes_before` when the
        point lies in *definition*'s own function, or the same question applied to the function the
        point lies in, recursing up the call graph. Where *definition* stands in a function the
        program calls where it writes it, a point outside that function is ordered by the call
        instead, once every return of the function follows *definition* (`_lifts`). The ordering is
        *strict*: a reference sharing the definition's node — an earlier operand of a sequence
        evaluated before it — is not accepted, since dominance is reflexive and orders the parts
        of one node no further; a declarator before it is a node of its own and is ordered. A
        reference's function is its nearest enclosing function (its `_activation_of`), so a use in
        a function's parameter defaults is attributed to that function's invocation, not to the
        statement that declares it. Functions that reach each other's invocations — a recursive
        function, mutually recursive ones — are answered together
        (`_solve_invocation_orders`). This is the interprocedural counterpart of `dominates`, and
        the sound replacement for ordering a cross-function inline by statement position.

        Conservatively `False` when a reference point cannot be ordered or enumerated: the named
        binding is reassigned or redeclared (its references no longer pin one function), code
        outside the file can call the function, or a reference lies in a function that itself runs
        too late or escapes, and when the statement evaluating *definition* may complete without
        evaluating it (`_runs_with_its_node`). A function neither referenced nor within reflection's
        reach is vacuously safe.
        """
        return self._runs_with_its_node(definition) and self._ordered(definition, function)

    def runs_before_every_invocation(self, definition: Node, function: Node) -> bool:
        """
        Whether *definition* is guaranteed to run before every invocation of *function*, and
        *function* is entered from the activation that runs *definition*, or from one a call it
        lifts to runs in (`_entered`, `_lifts`) — `runs_before_function` with the vacuity
        refused. A reader nothing in the file obtains, or one only code nothing obtains calls,
        answers the ordering question over no invocation at all and passes vacuously; a value
        established against no invocation is established for no read, so such a reader does not
        qualify. An object handed to code does not enter the
        methods stored on it. An anonymous function expression created in that activation is
        entered by its own creation, the one point no invocation can precede.
        """
        if not self.runs_before_function(definition, function):
            return False
        return any(self._entered(owner, function) for _, owner in self._lifts(definition))

    def runs_before(self, definition: Node, reference: Node) -> bool:
        """
        Whether *definition* is guaranteed to have executed before *reference* is evaluated — the
        single-reference form of the ordering `runs_before_function` applies per reference point.
        When *reference* shares *definition*'s activation this is `completes_before` (a reference
        sharing *definition*'s node is not accepted, since dominance is reflexive and orders the
        parts of one node no further); when *reference* lies inside a function that cannot be
        invoked until after *definition*, it is the interprocedural runs-before-function query,
        recursing up the call graph. Conservatively `False` whenever the
        ordering cannot be established — a reference in an activation that may run before
        *definition*, a reference point that cannot be enumerated, or a statement that may complete
        without evaluating *definition* (`_runs_with_its_node`) — so a caller may treat `True` as
        a guarantee.
        """
        return (
            self._runs_with_its_node(definition)
            and self._runs_after(definition, reference)
        )

    def runs_before_all(self, definition: Node, references: Iterable[Node]) -> bool:
        """
        Whether *definition* is guaranteed to run before every reference in *references* — `runs_before`
        for each, vacuously `True` for an empty iterable.
        """
        if not self._runs_with_its_node(definition):
            return False
        return all(self._runs_after(definition, reference) for reference in references)

    def cannot_precede(self, reference: Node, anchor: Node) -> bool:
        """
        Whether *reference* cannot run before *anchor* on any run on which *anchor* runs: the
        statement evaluating *anchor* has completed before *reference* runs, as `runs_before` asks
        without asking whether that statement evaluates *anchor* at all. A run that skips *anchor*
        has nothing for *reference* to precede, so a fold made at *anchor* holds wherever it is
        evaluated as long as no such *reference* comes first. An *anchor* in a part that runs at a
        time of its own, as the initializer of a field does each time an instance is constructed,
        is located in the graph of that run and ordered there.
        """
        located = self.locate(anchor)
        if located is None or located[1].element is None:
            return False
        return self._runs_after(anchor, reference)

    def callee_established_before(self, call: JsCallExpression | JsNewExpression) -> bool:
        """
        Whether the name *call* reads its callee through holds its `singular_value` before *call*
        runs (`binding_established_before`). A function declared in a block has two names, each in
        place from a point of its own, which is why the name is the one the call reads and not the
        one the function declares. `False` for a callee that is no name.
        """
        callee = strip_parens(call.callee)
        if not isinstance(callee, JsIdentifier):
            return False
        return self.binding_established_before(self.model.resolve(callee), call)

    def binding_established_before(self, binding: Binding | None, reference: Node) -> bool:
        """
        Whether *binding*'s `singular_value` is in place before *reference* runs: every node in its
        `SemanticModel.binding_establishment_sites` executes first. A hoisted function declaration has no
        sites and qualifies unconditionally; a `var`/`let`/`const` initializer, a class declaration, or a
        lone assignment (`f = function(){}`, the form namespace flattening leaves) qualifies only where
        each establishing node runs before *reference*. `False` when the binding holds no single orderable
        value, so its presence cannot be ordered — the query a consumer needs before trusting a value that
        would otherwise be read out of its temporal dead zone or before its establishing write.
        A site the statement or loop head holding it evaluates on some runs only orders nothing
        (`runs_before`): `x && (T = [])` completes without writing `T`.
        """
        sites = self.model.binding_establishment_sites(binding)
        if sites is None:
            return False
        return all(self.runs_before(site, reference) for site in sites)

    def _runs_with_its_node(self, site: Node) -> bool:
        """
        Whether *site* has run whenever the control-flow node evaluating it has completed. A graph
        has a node for a statement, a loop head and a declarator and none for the parts of an
        expression, so an ordering against that node answers for *site* only where the node
        evaluates it on every run
        (`refinery.lib.scripts.js.analysis.evaluation.evaluated_whenever_completed`). Memoized by
        identity, since every ordering query of one definition asks it again for each reference.
        """
        cached = self._runs_with_its_node_cache.get(site)
        if cached is None:
            located = self.locate(site)
            element = None if located is None else located[1].element
            cached = element is not None and evaluated_whenever_completed(site, element)
            self._runs_with_its_node_cache[site] = cached
        return cached

    def past_dead_zone(self, binding: Binding, reference: Node) -> bool:
        """
        Whether *reference* is guaranteed to run past *binding*'s temporal dead zone: every
        declaration of this `let`/`const`/`class` binding executes first, so a read at *reference*
        cannot raise a `ReferenceError`. Distinct from `binding_established_before`, which orders
        the singular value's establishing write: a dead zone ends at the DECLARATION, not at the
        first value assignment, so a `let` declared before *reference* but reassigned afterward is
        past its dead zone here while `binding_established_before` — reasoning about the value —
        answers `False`. `False` when the binding carries no declaration to order, so the dead
        zone's end cannot be proven.
        """
        return bool(binding.declarations) and all(
            self.runs_before(site, reference) for site in binding.declarations
        )

    def _ordered(self, definition: Node, function: Node) -> bool:
        """
        Whether *definition* runs before every invocation of *function*. Answers are kept per
        definition and every one kept is final, so each query of the same definition shares the
        functions an earlier one solved.
        """
        orders = self._invocation_orders.setdefault(definition, {})
        ordered = orders.get(function)
        if ordered is None:
            self._solve_invocation_orders(definition, function, orders)
            ordered = orders[function]
        return ordered

    def _solve_invocation_orders(
        self,
        definition: Node,
        function: Node,
        orders: dict[Node | _HandOver, bool],
    ):
        """
        Solve `_ordered` for *function* and for every function a reference point of it lies in,
        one strongly connected component of that graph at a time: Tarjan's algorithm, kept on an
        explicit stack so a long chain of calls cannot exhaust the interpreter's. A point that is a
        `_HandOver` is a node of the graph in its own right, shared by every function installed on
        one object. The members of one component reach each other's invocations and get one
        answer: they are ordered when every point outside the component is, one in an activation
        that runs the definition or a call returning only once it has (`_site_in`) by
        `_statement_completes_before` of that site, one in another function or hand-over by that
        node's answer. A function expression such an activation creates only after the site has
        completed is ordered without its points (`_created_after`).

        This is sound because the earliest invocation of any function in a component follows a
        reference to it that nothing in the component can have evaluated yet, so that reference is
        one of the points outside it. A node stops at the first point it cannot order: that point
        lies outside every component the node belongs to, so it leaves each of them unordered
        however the other points stand. Every other component is stored only once every component
        it reaches is, which is what makes each stored answer final.
        """
        index: dict[Node | _HandOver, int] = {}
        lowlink: dict[Node | _HandOver, int] = {}
        ordered: dict[Node | _HandOver, bool] = {}
        stack: list[Node | _HandOver] = []
        frames: list[tuple[Node | _HandOver, Iterator[Node | _HandOver]]] = []

        def open_frame(opened: Node | _HandOver):
            index[opened] = lowlink[opened] = len(index)
            stack.append(opened)
            if self._created_after(definition, opened):
                points = ()
            else:
                points = self._reference_points(opened)
            ordered[opened] = points is not None
            frames.append((opened, iter(points or ())))

        open_frame(function)
        while frames:
            current, points = frames[-1]
            for point in points:
                if not ordered[current]:
                    break
                if isinstance(point, _HandOver):
                    activation: Node | _HandOver = point
                else:
                    activation = self._activation_of(point)
                    if (site := self._site_in(definition, activation)) is not None:
                        if not self._statement_completes_before(site, point):
                            ordered[current] = False
                        continue
                    if activation is self.model.root:
                        ordered[current] = False
                        continue
                if (known := orders.get(activation)) is not None:
                    if not known:
                        ordered[current] = False
                elif activation not in index:
                    open_frame(activation)
                    break
                else:
                    lowlink[current] = min(lowlink[current], index[activation])
            if frames[-1][0] is not current:
                continue
            frames.pop()
            if lowlink[current] == index[current]:
                members: list[Node | _HandOver] = []
                while not members or members[-1] is not current:
                    members.append(stack.pop())
                answer = all(ordered[member] for member in members)
                for member in members:
                    orders[member] = answer
            if frames:
                parent = frames[-1][0]
                if current in orders:
                    ordered[parent] = ordered[parent] and orders[current]
                else:
                    lowlink[parent] = min(lowlink[parent], lowlink[current])

    def _created_after(self, definition: Node, activation: Node | _HandOver) -> bool:
        """
        Whether *activation* is a function expression created, in an activation `_site_in` places
        *definition* in, only once that site has completed. No copy of the function exists before
        that, so none is invoked before it, whatever its reference points are: a method call that
        hands its object over before the method is stored there cannot call the method yet. A
        function declaration exists from the start of its activation and never qualifies.
        """
        if not isinstance(activation, (JsFunctionExpression, JsArrowFunctionExpression)):
            return False
        site = self._site_in(definition, self._activation_of(activation))
        return site is not None and self._statement_completes_before(site, activation)

    def _entered(self, owner: Node, function: Node) -> bool:
        """
        Whether a reference point of *function* that names it lies in *owner*, or in a function
        entered from *owner* the same way: a read of its name or of the key it is stored at, a
        reflective surface that can name it, the end of the script where an importer calls it, or
        its own creation for a function bound to nothing. The accesses of a `_HandOver` hand an
        object on and never enter a function, so a method no code in the file obtains stays
        unentered however often its object is handed over. Answers are kept per activation, since
        the question does not depend on the definition.
        """
        known = self._entered_from.setdefault(owner, {})
        answer = known.get(function)
        if answer is not None:
            return answer
        seen: set[Node] = {function}
        pending: list[Node] = [function]
        while pending:
            current = pending.pop()
            for point in self._reference_points(current) or ():
                if isinstance(point, _HandOver):
                    continue
                activation = self._activation_of(point)
                if activation is owner or known.get(activation) is True:
                    known[function] = True
                    return True
                if (
                    activation is not self.model.root
                    and activation not in seen
                    and known.get(activation) is None
                ):
                    seen.add(activation)
                    pending.append(activation)
        for node in seen:
            known[node] = False
        return False

    def _reference_points(self, activation: Node | _HandOver) -> Sequence[Node | _HandOver] | None:
        """
        The points no invocation of *activation* can precede, or `None` when they cannot be
        enumerated. A `_HandOver` holds its own points. For a function pinned to its names
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.function_names`) these are the
        value-reads of those names — a read must be evaluated before the value it denotes can be
        called — together with the opaque reflective surface sites that could invoke it by name
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.reflection_surface_sites`): a direct
        `eval`, `Function`, a string timer, or a dynamic global access cannot invoke the function
        before the surface that grants the capability has run, so each surface is itself a point no
        invocation precedes, ranked exactly like a read. The enumeration is `None` when the name is
        redeclared, reassigned to another value so a read no longer pins this one function
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.binding_pinned_to`), or resolved
        inside a dynamic scope a `with` body governs, whose
        `refinery.lib.scripts.js.analysis.model.Binding.dynamic_refs` entry is unorderable; this
        mirrors the escape verdict
        `refinery.lib.scripts.js.analysis.effects.EffectModel.function_escapes` draws from the same
        fact. A surface lexically inside the function is dropped: it cannot trigger the function's
        first invocation, only a re-entrant one, so it never bounds the ordering. A function
        installed as a property of a non-escaping local object (`_member_reference_points`) is
        enumerated instead by the points that name it and the object's `_HandOver`; this is
        consulted first, so a namespace method ordered by its call sites is not mistaken for an
        anonymous closure ordered by its creation.

        A function is ordered by its creation alone, the one point no invocation can precede, when
        it is bound to no name and matches neither pattern, and when the value of the assignment
        installing it flows on (`_installed_value_escapes`). So is the initializer of a field: it
        runs at the constructions of its class, none of which precedes the class statement creating
        it, and one that statement makes itself, in a static block, shares its node. A function
        code outside the file can call while the file runs
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.callable_from_outside`) has no
        enumeration at all. One an importer outside every import cycle can call has the end of the
        script as one more point, the script root standing for it (`_statement_completes_before`),
        since such an importer calls in only once the module has finished, and so has one code
        loading a library calls by name
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.reached_from_outside`).

        Memoized by identity: the enumeration is a pure function of *activation* and the model,
        both fixed for the model's lifetime — the whole DominanceModel is rebuilt when the tree
        version advances — so every `runs_before*` caller shares one result per function instead of
        recomputing it per reference and per query.
        """
        if isinstance(activation, _HandOver):
            return activation.points
        cache = self._reference_points_cache
        if activation not in cache:
            cache[activation] = self._compute_reference_points(activation)
        return cache[activation]

    def _compute_reference_points(self, function: Node) -> list[Node | _HandOver] | None:
        if not isinstance(function, FUNCTION_NODES):
            return [function]
        names = self.model.function_names(function)
        if self.model.callable_from_outside(function):
            return None
        if self._installed_value_escapes(function):
            return [function]
        if names is None and isinstance(function.parent, JsExportDefaultDeclaration):
            return [self.model.root]
        member_points = self._member_reference_points(function)
        if member_points is not None:
            return member_points
        if names is None:
            return [function]
        points: list[Node | _HandOver] = []
        for name in names.bindings:
            if (
                name.dynamic_refs
                or len(name.declarations) != 1
                or not self.model.binding_pinned_to(name, function)
            ):
                return None
            points.extend(names.reads_of(name))
            points.extend(
                site
                for site in self.model.reflection_surface_sites(name)
                if not site.is_descendant_of(function)
            )
            if name.exported or self.model.reached_from_outside(name):
                points.append(self.model.root)
        return points

    @staticmethod
    def _installed_value_escapes(function: Node) -> bool:
        """
        Whether *function* is the right side of an assignment whose own value the program goes on
        to use: chained into another name or key (`h = NS.g = function(){}`), called on the spot,
        or passed on as an argument. That value reaches code through no read of the name or of the
        key the assignment installs into, so neither enumeration lists it.
        """
        parent = function.parent
        return (
            isinstance(parent, JsAssignmentExpression)
            and parent.right is function
            and not value_is_discarded(parent)
        )

    def _member_reference_points(self, function: Node) -> list[Node | _HandOver] | None:
        """
        The points no invocation of *function* can precede when it is installed as a property of a
        non-escaping local object, or `None` where that pattern does not hold. *function* is the
        value of a `BASE.key = function` statement whose `BASE` resolves to a binding with a
        `_HandOver`, one holding a single object literal that never escapes as a bare value
        (`_hand_over`). The callable can then be obtained in two ways only: by reading `BASE.key`,
        or by code the object is handed to, which reads the key itself. The points are the
        hand-over, the reads of `key` and of keys that are not statically known, the reflective
        surfaces that could name the binding, and the end of the script for an object an importer
        reaches. A write of `key` never obtains the value and is not a point. An install at the key
        `__proto__` makes *function* the object's prototype rather than a property of it, so every
        inherited read reaches it, and the pattern does not hold.
        """
        parent = function.parent
        if not (
            isinstance(parent, JsAssignmentExpression)
            and parent.operator == '='
            and parent.right is function
        ):
            return None
        target = strip_parens(parent.left)
        if not isinstance(target, JsMemberExpression) or not isinstance(target.object, JsIdentifier):
            return None
        key = key_text(target)
        if key is None or key_may_be(target, _PROTO):
            return None
        binding = self.model.resolve(target.object)
        if binding is None:
            return None
        hand_over = self._hand_over(binding)
        if hand_over is None:
            return None
        points: list[Node | _HandOver] = [hand_over]
        points.extend(hand_over.reads.get(key, ()))
        points.extend(hand_over.unnamed)
        points.extend(site for site in hand_over.surfaces if not site.is_descendant_of(function))
        if hand_over.exported:
            points.append(self.model.root)
        return points

    def _hand_over(self, binding: Binding) -> _HandOver | None:
        """
        The `_HandOver` of the object *binding* holds, computed once per binding, or `None` where
        its accesses cannot all be enumerated: the binding holds no single object literal
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.singular_value`), one of its reads is
        not the object of a member access, a `with` could rename it (a
        `refinery.lib.scripts.js.analysis.model.Binding.dynamic_refs` entry), an importer can reach
        it before the module has finished
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.importer_may_run_first`), or a host
        can reach it by name
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.named_by_the_host`).

        An access hands the object to code when it is a method call in any form, whose callee
        receives the object as `this`, and when it reads or writes the object's prototype
        (`_may_name_the_prototype`), after which the object may inherit accessors from another
        prototype. Every access does, the establishing writes included, when an accessor may run on
        the object's prototype chain and receive the object as `this`, or at its own key the very
        function being stored there. That is so when the literal declares an accessor or a prototype
        (`refinery.lib.scripts.js.model.object_member_access_runs_accessor`); when the program
        writes the prototype chain of a plain object
        (`refinery.lib.scripts.js.analysis.intrinsics.IntrinsicWrites.chain_roots_unwritten`); when
        it holds code this analysis cannot read, which may install one anywhere
        (`refinery.lib.scripts.js.analysis.model.SemanticModel.has_reflection_surface`), the term
        `refinery.lib.scripts.js.analysis.effects.EffectModel.read_chain_intact` asks of a plain
        read as well; and when an access of the object may hand out its prototype
        (`_may_hand_out_the_prototype`). An accessor installed through what that access yields lands
        on a prototype every later object of the same kind inherits, the objects later runs of the
        same code create included, so a point at the access alone would not order those.

        An accessor can receive the object at no other moment, since the object never escapes as
        a bare value. Nothing can call a function through the object before the access that hands
        the object over has run, so such an access is a point rather than a reason to refuse, for
        the reason a reflective surface is one.
        """
        if binding in self._hand_overs:
            return self._hand_overs[binding]
        hand_over = self._compute_hand_over(binding)
        self._hand_overs[binding] = hand_over
        return hand_over

    def _compute_hand_over(self, binding: Binding) -> _HandOver | None:
        literal = self.model.singular_value(binding)
        if not isinstance(literal, JsObjectExpression):
            return None
        if (
            binding.dynamic_refs
            or self.model.importer_may_run_first(binding)
            or self.model.named_by_the_host(binding)
        ):
            return None
        accesses: list[JsMemberExpression] = []
        for read in binding.reads:
            node = read
            access = node.parent
            while isinstance(access, JsParenthesizedExpression):
                node, access = access, access.parent
            if not isinstance(access, JsMemberExpression) or access.object is not node:
                return None
            accesses.append(access)
        every_access_runs_code = (
            object_member_access_runs_accessor(literal)
            or not self.intrinsic_writes.chain_roots_unwritten(dict)
            or self.model.has_reflection_surface()
            or any(_may_hand_out_the_prototype(access) for access in accesses)
        )
        points: list[Node] = []
        reads: dict[str, list[Node]] = {}
        unnamed: list[Node] = []
        for access in accesses:
            if (
                every_access_runs_code
                or is_invocation_target(access)
                or _may_name_the_prototype(access)
            ):
                points.append(access)
            if is_simple_assignment_target(access):
                continue
            if (key := key_text(access)) is None:
                unnamed.append(access)
            else:
                reads.setdefault(key, []).append(access)
        return _HandOver(
            points,
            reads,
            unnamed,
            self.model.reflection_surface_sites(binding),
            binding.exported,
        )

    def _runs_after(self, definition: Node, point: Node) -> bool:
        owner = self._activation_of(point)
        if (site := self._site_in(definition, owner)) is not None:
            return self._statement_completes_before(site, point)
        if owner is not self.model.root:
            return self._ordered(definition, owner)
        return False

    def _site_in(self, definition: Node, activation: Node | _HandOver) -> Node | None:
        """
        The node of *activation* whose completion orders *definition*: *definition* itself where
        *activation* runs it, and otherwise the call that runs a function *definition* stands in,
        climbing outward through such calls (`_lifts`). `None` where *activation* is not on that
        climb.
        """
        for site, owner in self._lifts(definition):
            if owner is activation:
                return site
        return None

    def _lifts(self, definition: Node) -> list[tuple[Node, Node]]:
        """
        *definition* with its activation, followed by every call it lifts to: where a function
        expression the program calls where it writes it holds the site so far, and every run of the
        function that returns rather than throws has evaluated the site
        (`_completes_before_exit`), the call has returned only after the site ran, so the call,
        in its own activation, orders the site for every point there. A generator or an `async`
        function returns before its body has run, and holds no such site; the statement evaluating
        the call must evaluate it whenever it completes (`_runs_with_its_node`). Memoized.
        """
        if (lifts := self._lifts_cache.get(definition)) is not None:
            return lifts
        site = definition
        owner = self._activation_of(definition)
        lifts = [(site, owner)]
        while (
            isinstance(owner, (JsFunctionExpression, JsArrowFunctionExpression))
            and not is_generator_function(owner)
            and not is_async_function(owner)
            and isinstance(call := enclosing_operator(owner), JsCallExpression)
            and strip_parens(call.callee) is owner
            and self._completes_before_exit(owner, site)
            and self._runs_with_its_node(call)
        ):
            site = call
            owner = self._activation_of(call)
            lifts.append((site, owner))
        self._lifts_cache[definition] = lifts
        return lifts

    def _activation_of(self, element: Node) -> Node:
        """
        The run owner whose invocation evaluates *element*
        (`refinery.lib.scripts.js.analysis.evaluation.enclosing_run`), or the script root when no
        run owner does. This is the unit `runs_before_function` reasons about: a reference in a
        function's body *or its parameter defaults* runs when that function is invoked, and one in
        the initializer of a field when an instance is constructed, so each attributes to its run,
        never to the statement that merely declares it in the enclosing graph.
        """
        run = enclosing_run(element)
        return run if run is not None else self.model.root

Ancestors

• DominatorModel

Methods

def completes_before(self, definition, point)

Whether definition has run on every run that reaches point, both in one graph: the statement evaluating it evaluates it whenever it completes (_runs_with_its_node), and has completed (_statement_completes_before).

Expand source code Browse git

def completes_before(self, definition: Node, point: Node) -> bool:
    """
    Whether *definition* has run on every run that reaches *point*, both in one graph: the
    statement evaluating it evaluates it whenever it completes (`_runs_with_its_node`), and has
    completed (`_statement_completes_before`).
    """
    return (
        self._runs_with_its_node(definition)
        and self._statement_completes_before(definition, point)
    )

def completes_before_node(self, graph, a, b)

The counterpart of _statement_completes_before for a caller that has already located the two nodes in graph. Whether a can throw is asked of what its node evaluates (evaluated_part()).

Expand source code Browse git

def completes_before_node(self, graph: ControlFlowGraph, a: CfgNode, b: CfgNode) -> bool:
    """
    The counterpart of `_statement_completes_before` for a caller that has already located the
    two nodes in *graph*. Whether *a* can throw is asked of what its node evaluates
    (`refinery.lib.scripts.js.analysis.cfg.evaluated_part`).
    """
    if a is b or not self.dominates_node(graph, a, b, Projection.MAY):
        return False
    thrown = graph.reached_after_a_throw(a)
    if id(b) not in thrown:
        return True
    return a.element is not None and self.model.statement_cannot_throw(
        evaluated_part(graph, a.element)
    )

def runs_before_function(self, definition, function)

Whether definition is guaranteed to have executed before any invocation of function — so a value established at definition holds throughout every call of function, and may be inlined into its body. The reasoning rests on one fact: a function cannot be invoked before a reference to it has been evaluated. Its reference points are its own creation, for an anonymous function expression, or the uses of its name, for a named binding; no invocation can precede the earliest of them. So definition runs before every invocation exactly when it runs before every reference point — and that, per point, is completes_before when the point lies in definition's own function, or the same question applied to the function the point lies in, recursing up the call graph. Where definition stands in a function the program calls where it writes it, a point outside that function is ordered by the call instead, once every return of the function follows definition (_lifts). The ordering is strict: a reference sharing the definition's node — an earlier operand of a sequence evaluated before it — is not accepted, since dominance is reflexive and orders the parts of one node no further; a declarator before it is a node of its own and is ordered. A reference's function is its nearest enclosing function (its _activation_of), so a use in a function's parameter defaults is attributed to that function's invocation, not to the statement that declares it. Functions that reach each other's invocations — a recursive function, mutually recursive ones — are answered together (_solve_invocation_orders). This is the interprocedural counterpart of dominates, and the sound replacement for ordering a cross-function inline by statement position.

Conservatively False when a reference point cannot be ordered or enumerated: the named binding is reassigned or redeclared (its references no longer pin one function), code outside the file can call the function, or a reference lies in a function that itself runs too late or escapes, and when the statement evaluating definition may complete without evaluating it (_runs_with_its_node). A function neither referenced nor within reflection's reach is vacuously safe.

Expand source code Browse git

def runs_before_function(self, definition: Node, function: Node) -> bool:
    """
    Whether *definition* is guaranteed to have executed before any invocation of *function* — so
    a value established at *definition* holds throughout every call of *function*, and may be
    inlined into its body. The reasoning rests on one fact: a function cannot be invoked before
    a reference to it has been evaluated. Its reference points are its own creation, for an
    anonymous function expression, or the uses of its name, for a named binding; no invocation
    can precede the earliest of them. So *definition* runs before every invocation exactly when
    it runs before every reference point — and that, per point, is `completes_before` when the
    point lies in *definition*'s own function, or the same question applied to the function the
    point lies in, recursing up the call graph. Where *definition* stands in a function the
    program calls where it writes it, a point outside that function is ordered by the call
    instead, once every return of the function follows *definition* (`_lifts`). The ordering is
    *strict*: a reference sharing the definition's node — an earlier operand of a sequence
    evaluated before it — is not accepted, since dominance is reflexive and orders the parts
    of one node no further; a declarator before it is a node of its own and is ordered. A
    reference's function is its nearest enclosing function (its `_activation_of`), so a use in
    a function's parameter defaults is attributed to that function's invocation, not to the
    statement that declares it. Functions that reach each other's invocations — a recursive
    function, mutually recursive ones — are answered together
    (`_solve_invocation_orders`). This is the interprocedural counterpart of `dominates`, and
    the sound replacement for ordering a cross-function inline by statement position.

    Conservatively `False` when a reference point cannot be ordered or enumerated: the named
    binding is reassigned or redeclared (its references no longer pin one function), code
    outside the file can call the function, or a reference lies in a function that itself runs
    too late or escapes, and when the statement evaluating *definition* may complete without
    evaluating it (`_runs_with_its_node`). A function neither referenced nor within reflection's
    reach is vacuously safe.
    """
    return self._runs_with_its_node(definition) and self._ordered(definition, function)

def runs_before_every_invocation(self, definition, function)

Whether definition is guaranteed to run before every invocation of function, and function is entered from the activation that runs definition, or from one a call it lifts to runs in (_entered, _lifts) — runs_before_function with the vacuity refused. A reader nothing in the file obtains, or one only code nothing obtains calls, answers the ordering question over no invocation at all and passes vacuously; a value established against no invocation is established for no read, so such a reader does not qualify. An object handed to code does not enter the methods stored on it. An anonymous function expression created in that activation is entered by its own creation, the one point no invocation can precede.

Expand source code Browse git

def runs_before_every_invocation(self, definition: Node, function: Node) -> bool:
    """
    Whether *definition* is guaranteed to run before every invocation of *function*, and
    *function* is entered from the activation that runs *definition*, or from one a call it
    lifts to runs in (`_entered`, `_lifts`) — `runs_before_function` with the vacuity
    refused. A reader nothing in the file obtains, or one only code nothing obtains calls,
    answers the ordering question over no invocation at all and passes vacuously; a value
    established against no invocation is established for no read, so such a reader does not
    qualify. An object handed to code does not enter the
    methods stored on it. An anonymous function expression created in that activation is
    entered by its own creation, the one point no invocation can precede.
    """
    if not self.runs_before_function(definition, function):
        return False
    return any(self._entered(owner, function) for _, owner in self._lifts(definition))

def runs_before(self, definition, reference)

Whether definition is guaranteed to have executed before reference is evaluated — the single-reference form of the ordering runs_before_function applies per reference point. When reference shares definition's activation this is completes_before (a reference sharing definition's node is not accepted, since dominance is reflexive and orders the parts of one node no further); when reference lies inside a function that cannot be invoked until after definition, it is the interprocedural runs-before-function query, recursing up the call graph. Conservatively False whenever the ordering cannot be established — a reference in an activation that may run before definition, a reference point that cannot be enumerated, or a statement that may complete without evaluating definition (_runs_with_its_node) — so a caller may treat True as a guarantee.

Expand source code Browse git

def runs_before(self, definition: Node, reference: Node) -> bool:
    """
    Whether *definition* is guaranteed to have executed before *reference* is evaluated — the
    single-reference form of the ordering `runs_before_function` applies per reference point.
    When *reference* shares *definition*'s activation this is `completes_before` (a reference
    sharing *definition*'s node is not accepted, since dominance is reflexive and orders the
    parts of one node no further); when *reference* lies inside a function that cannot be
    invoked until after *definition*, it is the interprocedural runs-before-function query,
    recursing up the call graph. Conservatively `False` whenever the
    ordering cannot be established — a reference in an activation that may run before
    *definition*, a reference point that cannot be enumerated, or a statement that may complete
    without evaluating *definition* (`_runs_with_its_node`) — so a caller may treat `True` as
    a guarantee.
    """
    return (
        self._runs_with_its_node(definition)
        and self._runs_after(definition, reference)
    )

def runs_before_all(self, definition, references)

Whether definition is guaranteed to run before every reference in references — runs_before for each, vacuously True for an empty iterable.

Expand source code Browse git

def runs_before_all(self, definition: Node, references: Iterable[Node]) -> bool:
    """
    Whether *definition* is guaranteed to run before every reference in *references* — `runs_before`
    for each, vacuously `True` for an empty iterable.
    """
    if not self._runs_with_its_node(definition):
        return False
    return all(self._runs_after(definition, reference) for reference in references)

def cannot_precede(self, reference, anchor)

Whether reference cannot run before anchor on any run on which anchor runs: the statement evaluating anchor has completed before reference runs, as runs_before asks without asking whether that statement evaluates anchor at all. A run that skips anchor has nothing for reference to precede, so a fold made at anchor holds wherever it is evaluated as long as no such reference comes first. An anchor in a part that runs at a time of its own, as the initializer of a field does each time an instance is constructed, is located in the graph of that run and ordered there.

Expand source code Browse git

def cannot_precede(self, reference: Node, anchor: Node) -> bool:
    """
    Whether *reference* cannot run before *anchor* on any run on which *anchor* runs: the
    statement evaluating *anchor* has completed before *reference* runs, as `runs_before` asks
    without asking whether that statement evaluates *anchor* at all. A run that skips *anchor*
    has nothing for *reference* to precede, so a fold made at *anchor* holds wherever it is
    evaluated as long as no such *reference* comes first. An *anchor* in a part that runs at a
    time of its own, as the initializer of a field does each time an instance is constructed,
    is located in the graph of that run and ordered there.
    """
    located = self.locate(anchor)
    if located is None or located[1].element is None:
        return False
    return self._runs_after(anchor, reference)

def callee_established_before(self, call)

Whether the name call reads its callee through holds its singular_value before call runs (binding_established_before). A function declared in a block has two names, each in place from a point of its own, which is why the name is the one the call reads and not the one the function declares. False for a callee that is no name.

Expand source code Browse git

def callee_established_before(self, call: JsCallExpression | JsNewExpression) -> bool:
    """
    Whether the name *call* reads its callee through holds its `singular_value` before *call*
    runs (`binding_established_before`). A function declared in a block has two names, each in
    place from a point of its own, which is why the name is the one the call reads and not the
    one the function declares. `False` for a callee that is no name.
    """
    callee = strip_parens(call.callee)
    if not isinstance(callee, JsIdentifier):
        return False
    return self.binding_established_before(self.model.resolve(callee), call)

def binding_established_before(self, binding, reference)

Whether binding's singular_value is in place before reference runs: every node in its SemanticModel.binding_establishment_sites executes first. A hoisted function declaration has no sites and qualifies unconditionally; a var/let/const initializer, a class declaration, or a lone assignment (f = function(){}, the form namespace flattening leaves) qualifies only where each establishing node runs before reference. False when the binding holds no single orderable value, so its presence cannot be ordered — the query a consumer needs before trusting a value that would otherwise be read out of its temporal dead zone or before its establishing write. A site the statement or loop head holding it evaluates on some runs only orders nothing (runs_before): x && (T = []) completes without writing T.

Expand source code Browse git

def binding_established_before(self, binding: Binding | None, reference: Node) -> bool:
    """
    Whether *binding*'s `singular_value` is in place before *reference* runs: every node in its
    `SemanticModel.binding_establishment_sites` executes first. A hoisted function declaration has no
    sites and qualifies unconditionally; a `var`/`let`/`const` initializer, a class declaration, or a
    lone assignment (`f = function(){}`, the form namespace flattening leaves) qualifies only where
    each establishing node runs before *reference*. `False` when the binding holds no single orderable
    value, so its presence cannot be ordered — the query a consumer needs before trusting a value that
    would otherwise be read out of its temporal dead zone or before its establishing write.
    A site the statement or loop head holding it evaluates on some runs only orders nothing
    (`runs_before`): `x && (T = [])` completes without writing `T`.
    """
    sites = self.model.binding_establishment_sites(binding)
    if sites is None:
        return False
    return all(self.runs_before(site, reference) for site in sites)

def past_dead_zone(self, binding, reference)

Whether reference is guaranteed to run past binding's temporal dead zone: every declaration of this let/const/class binding executes first, so a read at reference cannot raise a ReferenceError. Distinct from binding_established_before, which orders the singular value's establishing write: a dead zone ends at the DECLARATION, not at the first value assignment, so a let declared before reference but reassigned afterward is past its dead zone here while binding_established_before — reasoning about the value — answers False. False when the binding carries no declaration to order, so the dead zone's end cannot be proven.

Expand source code Browse git

def past_dead_zone(self, binding: Binding, reference: Node) -> bool:
    """
    Whether *reference* is guaranteed to run past *binding*'s temporal dead zone: every
    declaration of this `let`/`const`/`class` binding executes first, so a read at *reference*
    cannot raise a `ReferenceError`. Distinct from `binding_established_before`, which orders
    the singular value's establishing write: a dead zone ends at the DECLARATION, not at the
    first value assignment, so a `let` declared before *reference* but reassigned afterward is
    past its dead zone here while `binding_established_before` — reasoning about the value —
    answers `False`. `False` when the binding carries no declaration to order, so the dead
    zone's end cannot be proven.
    """
    return bool(binding.declarations) and all(
        self.runs_before(site, reference) for site in binding.declarations
    )

Inherited members

• DominatorModel:
  • cfg_node_of
  • completes
  • dominates
  • dominates_node
  • graph_of
  • locate
  • locate_pair
  • never_runs
  • reachable
  • reached_from_entry
  • strictly_dominates
  • tree_of