Module refinery.lib.scripts.js.analysis.intrinsics

What a JavaScript program writes on the intrinsics, computed once per SemanticModel. build_intrinsic_writes() scans the program for every global name it binds, assigns, writes a property on, installs a descriptor on, or hands to code this analysis cannot read, and for the property keys it writes on the names whose keys are watched; IntrinsicWrites holds the answer and asks the prototype-chain questions of it.

The scan reads only the semantic model, so it sits beside it rather than above any layer that orders or summarizes code: the EffectModel and the DominanceModel both read the one answer ModelCache builds, and neither has to reach into the other for it. The registry of intrinsics the scan watches lives here for the same reason.

"""
What a JavaScript program writes on the intrinsics, computed once per
`refinery.lib.scripts.js.analysis.model.SemanticModel`. `build_intrinsic_writes` scans the program
for every global name it binds, assigns, writes a property on, installs a descriptor on, or hands to
code this analysis cannot read, and for the property keys it writes on the names whose keys are
watched; `IntrinsicWrites` holds the answer and asks the prototype-chain questions of it.

The scan reads only the semantic model, so it sits beside it rather than above any layer that orders
or summarizes code: the `refinery.lib.scripts.js.analysis.effects.EffectModel` and the
`refinery.lib.scripts.js.analysis.dominance.DominanceModel` both read the one answer
`refinery.lib.scripts.js.analysis.cache.ModelCache` builds, and neither has to reach into the other
for it. The registry of intrinsics the scan watches lives here for the same reason.
"""
from __future__ import annotations

import enum

from typing import Iterator, NamedTuple, Sequence

from refinery.lib.scripts import Node
from refinery.lib.scripts.analysis.components import strongly_connected_components
from refinery.lib.scripts.js.analysis.model import (
    _TESTED_FORMS,
    FUNCTION_NODES,
    Binding,
    Role,
    SemanticModel,
    _governing_target,
    enclosing_function,
    is_invocation_target,
    is_member_write_target,
    reference_role,
)
from refinery.lib.scripts.js.builtins import (
    BUILTIN_MEMBER_NAMES,
    PROTOTYPE_CHAIN_PROPERTIES,
    RECEIVER_WRITING_METHODS,
)
from refinery.lib.scripts.js.keys import accessor_installs, key_is, key_may_be, key_text
from refinery.lib.scripts.js.model import (
    ACCESSOR_INSTALL_METHODS,
    LOGICAL_ASSIGNMENT_OPERATORS,
    JsArrowFunctionExpression,
    JsAssignmentExpression,
    JsBinaryExpression,
    JsCallExpression,
    JsConditionalExpression,
    JsExpressionStatement,
    JsForInStatement,
    JsForOfStatement,
    JsFunctionDeclaration,
    JsFunctionExpression,
    JsIdentifier,
    JsLogicalExpression,
    JsMemberExpression,
    JsNewExpression,
    JsParenthesizedExpression,
    JsProperty,
    JsReturnStatement,
    JsSequenceExpression,
    JsSpreadElement,
    JsTaggedTemplateExpression,
    JsTemplateLiteral,
    JsUnaryExpression,
    JsUpdateExpression,
    JsVariableDeclarator,
    strip_parens,
)

PURE_INTRINSIC_METHODS = frozenset({
    'String.fromCharCode',
    'Array.isArray',
    'Math.abs',
    'Math.ceil',
    'Math.floor',
    'Math.round',
    'Math.trunc',
    'Math.sign',
    'Math.max',
    'Math.min',
    'Math.pow',
    'Math.sqrt',
    'Math.cbrt',
    'Math.log',
    'Math.log2',
    'Math.log10',
    'Math.exp',
    'Number.isNaN',
    'Number.isFinite',
    'Number.isInteger',
    'Number.isSafeInteger',
    'Number.parseInt',
    'Number.parseFloat',
})

PURE_GLOBAL_FUNCTIONS = frozenset({
    'parseInt',
    'parseFloat',
    'isNaN',
    'isFinite',
})

SPECIES_KEYS = PROTOTYPE_CHAIN_PROPERTIES
"""
The two property names that decide what an allocating `Array.prototype` method returns.
ArraySpeciesCreate reads `constructor[Symbol.species]` off the receiver, and `__proto__` replaces
the prototype that `constructor` lookup walks, so writing either can make the "newly created" array
be a shared object — or make the call throw, by leaving a primitive where a constructor is expected.
"""

_SURFACE_KEYS = SPECIES_KEYS | frozenset({'prototype'})
"""
The property names whose value shares the mutable surface of the intrinsic it was read from, so
handing that value to unanalysable code is as dangerous as handing over the intrinsic itself.
`SPECIES_KEYS` reach the prototype chain and `prototype` is the chain. Every other key yields
something whose properties nobody consults when the intrinsic is used: patching a property of the
number `Math.PI` or of the function `Math.floor` cannot change what `Math.floor(1.7)` returns, while
patching one of `Array.prototype` decides what `[1, 2].join()` means.
"""

PURE_INTRINSIC_ROOTS = (
    frozenset(name.split('.', 1)[0] for name in PURE_INTRINSIC_METHODS) | PURE_GLOBAL_FUNCTIONS
)


class _GlobalObject:
    """
    Sentinel denoting the global object as the value an expression evaluates to, distinct from a
    named intrinsic root and from an unresolved value.
    """


GLOBAL_OBJECT = _GlobalObject()

_DENOTED_ROOT_DEPTH_LIMIT = 16

_CALLEE_DEPTH_LIMIT = 4
"""
How far `_callee_is_write_free` follows an intrinsic through nested calls before refusing. A chain
longer than this is not proven safe, merely unproven, so exhausting the limit records the write.
Four was enough for every shape measured; the limit exists because the recursion is over call
*edges*, which a mutually-recursive pair makes unbounded.
"""

_VALUE_FORWARDING_NODES = (
    JsParenthesizedExpression,
    JsLogicalExpression,
    JsConditionalExpression,
    JsSequenceExpression,
    JsSpreadElement,
)
"""
The forms that hand an operand's value onward unchanged, so an intrinsic inside one escapes wherever
the form itself does. These are the outward counterpart of the arms `_denoted_roots` looks *into*,
and the pairing is not incidental: a fold that collapses `Math || 0` to `Math` must not change this
analysis's answer, which the pinning contract in `refinery.lib.scripts.js.analysis.cache.ModelCache`
requires.
"""

PROTOTYPE_OWNERS: dict[str, str] = {
    'str': 'String',
    'list': 'Array',
    'JsBuffer': 'Buffer',
    'dict': 'Object',
    'bool': 'Boolean',
    'int': 'Number',
    'float': 'Number',
    'JsFunctionDeclaration': 'Function',
    'JsFunctionExpression': 'Function',
    'JsArrowFunctionExpression': 'Function',
    'RegExpObject': 'RegExp',
}
"""
The intrinsic whose prototype supplies the methods of each interpreter value type, keyed by type
name so this module needs no import from the interpreter that depends on it. A method call on a
literal receiver names no global at the call site, so trusting it means asking whether *this*
prototype is intact: `String.prototype.toUpperCase = f` is a write to `String`, and it changes what
`'ab'.toUpperCase()` means even though the expression mentions no identifier at all.

Every type in the interpreter's value domain is named here directly, including
`refinery.lib.scripts.js.values.JsBuffer`, whose methods come from `Buffer.prototype`
rather than the `Array.prototype` its `list` base would suggest. A function value is represented as
its own AST node, so the two function node names appear here as value types rather than as syntax;
both inherit from `Function.prototype`. Lookup is exact rather than a walk up the Python MRO, which
would silently answer `Array` for any future `list` subclass instead of refusing. A type with no
entry is never trusted through this route.
"""

INHERITED_CHAIN_ROOTS = frozenset({'Object'})
"""
The prototypes every value inherits from beyond the one that owns its own methods.
`Object.prototype` roots every chain, so a getter installed there is reached by a plain read on an
array literal and on `Math` alike — which is why reading a property is a strictly stronger
requirement than calling a method.
"""

KEYED_WRITE_ROOTS = (
    PURE_INTRINSIC_ROOTS
    | INHERITED_CHAIN_ROOTS
    | frozenset(PROTOTYPE_OWNERS.values())
)
"""
The global names whose written property keys `IntrinsicWrites.key_written` bounds. A name outside
this set is one the scan records no key for, so answering `False` about it would read an absence of
evidence as evidence of absence; that predicate answers `True` for every key of such a name instead.

The set is the union of the names this module already watches for a reason: the intrinsics whose
methods are trusted, the roots a plain property read walks through, and the owners of the prototypes
that supply each value type's members. A caller asking about a name outside it is asking a question
this scan was not built to answer, and is told so.
"""

ESCAPE_RECORDED_ROOTS = PURE_INTRINSIC_ROOTS | frozenset({'RegExp', 'Date', 'Iterator'})
"""
The global names an escape records as written by name, not only by key: the names a fold trusts
to run code. A fold runs the methods of the pure roots, a fold that decides what a regular
expression answers trusts `RegExp`, so `p(RegExp)` for a `p` that replaces `RegExp.prototype.test`
must withdraw that trust, a fold that decides a comparison of the clock trusts `Date`, which
`Reflect.set(Date, 'now', f)` must withdraw, and a fold that converts an array iterator trusts the
prototype `Iterator` holds, which every such iterator inherits.

`Object` and `Function` are left out on purpose. Real samples hand `Object` to a call this scan
cannot resolve, and recording that escape refuses every fold that trusts `Object.prototype` in
them; the precise answer follows the escaped value to its writes, which this scan does not do.
"""

ESCAPE_WATCHED_ROOTS = KEYED_WRITE_ROOTS | ESCAPE_RECORDED_ROOTS
"""
The global names whose escape the scan looks for: every name it records keys for, and every name
`ESCAPE_RECORDED_ROOTS` records by name.
"""

_KEY_RECORDED_ROOTS = ESCAPE_WATCHED_ROOTS - ESCAPE_RECORDED_ROOTS
"""
The watched names whose escape the scan records by key alone: `IntrinsicWrites.key_written`
answers every key of one handed off, or of one read as a property (`g.Object`) and handed off or
written through, while `IntrinsicWrites.names` still lists it as unwritten.
"""

_WRITING_METHODS = RECEIVER_WRITING_METHODS | ACCESSOR_INSTALL_METHODS
"""
The methods that write the object they are read off: the methods of the built-in prototypes that
store into their receiver, and the accessor installers.
"""

_PROTOTYPE_READERS = frozenset({'getPrototypeOf'})

_PROTOTYPE_KEY = frozenset({'prototype'})

_CONSTRUCTOR_KEY = frozenset({'constructor'})


class _BuiltinReach:
    """
    Which values of a program may be a built-in object the scan cannot attribute a write through to
    the root owning it, and whether a write, a call writing its receiver, or a hand-off reaches one:
    the question behind `IntrinsicWrites.followable`.

    The scan attributes a write to the name at the foot of the chain it goes through and follows
    that name through the bindings holding it (`_IntrinsicAliases`). A built-in object reached
    without spelling its owner escapes both: `''.constructor.prototype.x = 1` writes
    `String.prototype` through no name, and so does `var p = [].__proto__; p.x = 1`. A value is
    *unattributed* where it may be such an object:

    - a member read whose key is unknown, or one a built-in type's chain supplies
      (`refinery.lib.scripts.js.builtins.BUILTIN_MEMBER_NAMES`): each may hand out a prototype or a
      function the language installed;
    - `prototype` read off an unattributed value;
    - a call of a method whose key may be `getPrototypeOf` (`refinery.lib.scripts.js.keys.key_may_be`);
    - a name of a binding that a declarator or an assignment stores an unattributed value into, or
      that a destructuring takes under a key the first arm counts;
    - an operand handed on unchanged by a logical operator, a conditional, a sequence or a plain
      assignment, where the operand is unattributed.

    A fold leaves the set of unattributed values as it was or smaller: a key it collapses to a
    string the first arm does not count takes a value out, and a forwarding form it removes is one
    the search looked through.
    """

    def __init__(self, model: SemanticModel, aliases: _IntrinsicAliases):
        self.model = model
        self.aliases = aliases
        self._answers: dict[Node | Binding, bool] = {}

    def unattributed(self, node: Node) -> bool:
        """
        Whether *node* may evaluate to an unattributed value. The values and bindings *node* may
        take its value from are searched with a stack rather than by recursion, so a chain of names
        of any length costs no depth. Every one searched without finding an unattributed value is
        remembered as having none, and every one on the way from *node* to one found is remembered
        as having one, so the many reads of one name cost one search between them.
        """
        known = self._answers.get(node)
        if known is not None:
            return known
        leaf, sources = self._sources(node)
        if leaf or not sources:
            self._answers[node] = leaf
            return leaf
        searched: list[Node | Binding] = [node]
        seen: set[Node | Binding] = {node}
        reached_from: dict[Node | Binding, Node | Binding] = {}
        pending: list[tuple[Node | Binding, Node | Binding]] = [(source, node) for source in sources]
        found: Node | Binding | None = None
        while pending:
            item, origin = pending.pop()
            if item in seen:
                continue
            seen.add(item)
            reached_from[item] = origin
            known = self._answers.get(item)
            if known is False:
                continue
            if known is True:
                found = item
                break
            searched.append(item)
            leaf, sources = self._sources(item)
            if leaf:
                found = item
                break
            pending.extend((source, item) for source in sources)
        if found is None:
            for item in searched:
                self._answers[item] = False
            return False
        cursor = found
        while cursor is not node:
            self._answers[cursor] = True
            cursor = reached_from[cursor]
        self._answers[node] = True
        return True

    def _sources(self, item: Node | Binding) -> tuple[bool, list[Node | Binding]]:
        """
        Whether *item* is unattributed by itself, and otherwise the values and bindings it may take
        its value from.
        """
        if isinstance(item, Binding):
            return self._binding_sources(item)
        node = strip_parens(item)
        if isinstance(node, JsIdentifier):
            binding = self.model.resolve(node)
            return False, [] if binding is None else [binding]
        if isinstance(node, JsMemberExpression):
            if key_may_be(node, BUILTIN_MEMBER_NAMES):
                return True, []
            if key_may_be(node, _PROTOTYPE_KEY) and node.object is not None:
                return False, [node.object]
            return False, []
        if isinstance(node, JsCallExpression):
            callee = strip_parens(node.callee)
            reads_a_prototype = isinstance(callee, JsMemberExpression) and key_may_be(callee, _PROTOTYPE_READERS)
            return reads_a_prototype, []
        sources: Sequence[Node | None] = ()
        if isinstance(node, JsLogicalExpression):
            sources = [node.left, node.right]
        elif isinstance(node, JsConditionalExpression):
            sources = [node.consequent, node.alternate]
        elif isinstance(node, JsSequenceExpression):
            sources = node.expressions[-1:]
        elif isinstance(node, JsAssignmentExpression):
            if node.operator == '=':
                sources = [node.right]
            elif node.operator in LOGICAL_ASSIGNMENT_OPERATORS:
                sources = [node.left, node.right]
        return False, [source for source in sources if source is not None]

    def _binding_sources(self, binding: Binding) -> tuple[bool, list[Node | Binding]]:
        """
        Whether *binding* takes an unattributed value from a destructuring by itself
        (`_destructured_under_a_builtin_key`), and otherwise the values its declarators and the
        assignments to it store. A declaration and an assignment destructure alike.
        """
        sources: list[Node | Binding] = []
        for declaration in binding.declarations:
            parent = declaration.parent
            if isinstance(parent, JsVariableDeclarator) and parent.id is declaration:
                if parent.init is not None:
                    sources.append(parent.init)
            elif _destructured_under_a_builtin_key(declaration):
                return True, []
        for reference in (*binding.writes, *binding.indefinite_writes):
            parent = reference.parent
            if isinstance(parent, JsAssignmentExpression) and parent.left is reference:
                if parent.right is not None:
                    sources.append(parent.right)
            elif _destructured_under_a_builtin_key(reference):
                return True, []
        return False, sources

    def trips_at(self, node: Node) -> bool:
        """
        Whether *node* writes a built-in object in a way the scan does not follow: it writes through
        an unattributed value, calls a method that may write its receiver
        (`refinery.lib.scripts.js.builtins.RECEIVER_WRITING_METHODS`, or a key not known) on a
        value that may be a built-in object, or is an unattributed value and hands it off. The scan
        reads no call as a write, so `Array.prototype.push(5)`, which stores an element every array
        then inherits, counts here although it names its owner. A name an assignment stores into
        hands no value anywhere; what a logical assignment evaluates to, which may be the name's old
        value, is asked of the assignment.
        """
        for member in _written_members(_write_target(node)):
            if member.object is not None and self.unattributed(member.object):
                return True
        if isinstance(node, JsCallExpression):
            callee = strip_parens(node.callee)
            if isinstance(callee, JsMemberExpression) and callee.object is not None:
                if key_may_be(callee, RECEIVER_WRITING_METHODS) and self._may_be_a_builtin(callee.object):
                    return True
        if isinstance(node, JsIdentifier) and reference_role(node) is not Role.READ:
            return False
        return self.unattributed(node) and self._handed_off(node)

    def _may_be_a_builtin(self, node: Node) -> bool:
        """
        Whether *node* may evaluate to a built-in object: an unattributed value, or a value rooted
        at a name the scan watches (`ESCAPE_WATCHED_ROOTS`), as `Array.prototype` is rooted at
        `Array`.
        """
        if self.unattributed(node):
            return True
        return any(
            self.aliases.names_denoted_by(root) & ESCAPE_WATCHED_ROOTS
            for root in _denoted_roots(node)
        )

    def _handed_off(self, node: Node) -> bool:
        """
        Whether the unattributed value at *node*, carried outward through the forms that hand it on,
        reaches a position `_hands_over` reads as handing it over, or is stored into anything but a
        name, whose binding the search follows instead. A read off it hands over nothing: what the
        read yields is a value of its own, which this asks about where it stands.
        """
        cursor = node
        while True:
            parent = cursor.parent
            if parent is None or isinstance(parent, JsExpressionStatement):
                return False
            if isinstance(parent, JsMemberExpression) and parent.object is cursor:
                return False
            if isinstance(parent, JsConditionalExpression) and parent.test is cursor:
                return False
            if not isinstance(parent, _VALUE_FORWARDING_NODES):
                break
            cursor = parent
        target = _rebinding_target(cursor)
        if target is not None:
            return not isinstance(strip_parens(target), JsIdentifier)
        return _hands_over(self.model, self.aliases, cursor, 0)


def _destructured_under_a_builtin_key(target: Node) -> bool:
    """
    Whether the destructuring that stores into *target* reads, on its way there, a key a built-in
    type's chain may supply (`refinery.lib.scripts.js.builtins.BUILTIN_MEMBER_NAMES`) or a key not
    known. Each of `({constructor: S} = '')`, `var {constructor: S = 0} = ''` and
    `var {constructor: {prototype: P}} = ''` stores a built-in object without spelling its owner.
    The way from *target* to the pattern is the climb
    `refinery.lib.scripts.js.analysis.model.is_member_write_target` takes, through defaults and
    nested patterns, so every property it passes is one the destructuring reads.
    """
    _, outermost = _governing_target(target)
    cursor = target
    while cursor is not outermost and cursor.parent is not None:
        cursor = cursor.parent
        if isinstance(cursor, JsProperty) and key_may_be(cursor, BUILTIN_MEMBER_NAMES):
            return True
    return False


def _constructs_through_an_unread_key(model: SemanticModel, node: Node) -> bool:
    """
    Whether, under the model that suspects code it cannot read, *node* calls or constructs through a
    `constructor` read or a key not known. The reflection check counts no such read that is invoked
    in place (`test_unfixed_defects.TestCodeRunThroughAConstructorReadInPlaceIsAReflectionSurface`),
    so a string of code `[].constructor.constructor(s)()` runs is one nothing else accounts for.
    """
    if model.trust_eval or not isinstance(node, (JsCallExpression, JsNewExpression)):
        return False
    callee = strip_parens(node.callee)
    return isinstance(callee, JsMemberExpression) and key_may_be(callee, _CONSTRUCTOR_KEY)


class IntrinsicWrites(NamedTuple):
    """
    What one scan of a program says about the globals it writes: *names*, the set a caller asks
    about a whole name with, and *keys*, the properties each of the watched names was written at —
    or `None` for a name whose written keys this scan cannot bound. *aliases* is the relation the
    scan resolved write targets through, kept for `follows_only_through_bindings`. *followable*
    says whether the scan follows every write the program makes on a built-in object: none reaches
    one through a value read without spelling its owner (`_BuiltinReach`), no watched name is
    handed off, nor read as a property and handed off or written through, where the scan records
    the escape by key alone (`_KEY_RECORDED_ROOTS`), and, under the model that suspects code it
    cannot read, no call runs through a key the reflection check leaves uncounted
    (`_constructs_through_an_unread_key`). A fold that reads a built-in's chain or converts an
    object without spelling its owner asks it on top of the questions about *names*.

    The two are produced together because they are read off the same nodes and must not disagree:
    a name recorded in one for a reason the other cannot express is a name one caller refuses and
    the other clears. Where a write cannot be pinned to a key, *keys* records the name unbounded
    rather than omitting it, so `keys` never reports less about a name than `names` does.
    """
    names: frozenset[str]
    keys: dict[str, frozenset[str] | None]
    aliases: _IntrinsicAliases
    followable: bool

    def key_written(self, name: str, key: str) -> bool:
        """
        Whether the program writes the property *key* on a chain rooted at the global *name*:
        `Object.prototype.constructor = C`, `delete Object.getPrototypeOf`, or a descriptor
        installed for that key. A name whose written keys cannot be bounded answers `True` for
        every key, and so does a name outside `KEYED_WRITE_ROOTS`, which the scan records nothing
        about at all. See `refinery.lib.scripts.js.analysis.effects.EffectModel.global_key_written`
        for why the question is asked of a name rather than of a receiver.
        """
        if name not in KEYED_WRITE_ROOTS:
            return True
        keys = self.keys.get(name, frozenset())
        return keys is None or key in keys

    def follows_only_through_bindings(self, value: Node) -> bool:
        """
        Whether a write through what *value* evaluates to is one this scan or the semantic model it
        read records where the value is spelled or a binding holds it, and never through a property
        holding it. The scan follows a value through the bindings that hold it and trusts `Object`,
        `Function`, `Boolean` and `Buffer` when they escape (`ESCAPE_RECORDED_ROOTS`), and the
        semantic model finds a write to a global through a name holding the global object, not
        through a property holding it. Stored in a property, `scope.P = Object.prototype` lets
        `scope.P.p = 1` write `Object.prototype` unrecorded; stored in a binding,
        `var P = Object.prototype` makes `P.p = 1` a recorded write.

        A value may carry what any of its `denoting_leaves` evaluates to, and one of them qualifies
        where the scan's aliases resolve it to a root the scan watches, where it may be the global
        object, or where the model was not built over it and so cannot say. The foot of a member
        chain is no value the chain evaluates to: it qualifies through the root it names, as
        `Object` does for `Object.prototype`, and never as the global object, since what
        `window.document` evaluates to is a property of that object.
        """
        model = self.aliases.model
        for leaf in denoting_leaves(value):
            if not model.knows(leaf):
                return True
            if isinstance(leaf, JsIdentifier) and self.aliases.names_denoted_by(leaf) & ESCAPE_WATCHED_ROOTS:
                return True
            if not _is_member_object(leaf) and model.may_be_the_global_object(leaf):
                return True
        return False

    def records_a_read(self, node: Node, names: frozenset[str]) -> bool:
        """
        Whether the scan records the watched *names* read at *node*: what *node* evaluates to is
        written through or escapes (`_records_a_watched_read`), the test the scan applies to a
        property read naming one of them.
        """
        return _records_a_watched_read(self.aliases.model, self.aliases, node, names)

    def denotes_a_watched_root(self, binding: Binding) -> bool:
        """
        Whether a value *binding* may hold denotes a root the scan watches, so that a write through
        a name resolving to the binding is one the scan attributes to that root.
        """
        return bool(self.aliases.names_of(binding) & ESCAPE_WATCHED_ROOTS)

    def roots_unwritten(self, owner: str, roots: frozenset[str]) -> bool:
        """
        Whether the program writes neither *owner* nor any prototype in *roots*. A property read
        resolves against the whole prototype chain rather than one prototype, so each name the chain
        passes through has to answer the same question
        `refinery.lib.scripts.js.analysis.effects.EffectModel.trusted_prototype` asks of the owner
        alone.
        """
        return all(name not in self.names for name in (owner, *roots))

    def chain_roots_unwritten(self, value_type: type) -> bool:
        """
        Whether the program writes no prototype a plain property read on a value of *value_type*
        consults, so such a read can run no accessor the program installed there. See
        `refinery.lib.scripts.js.analysis.effects.EffectModel.chain_roots_unwritten` for what the
        answer leaves out and who may ask it.
        """
        owner = PROTOTYPE_OWNERS.get(value_type.__name__)
        if owner is None:
            return False
        return self.roots_unwritten(owner, INHERITED_CHAIN_ROOTS)

    def records_more_than(self, other: IntrinsicWrites) -> bool:
        """
        Whether this scan records a written name, a key written on a name, or a name whose written
        keys it cannot bound, that the scan *other* does not record.
        """
        if self.names - other.names:
            return True
        for name, keys in self.keys.items():
            known = other.keys.get(name, frozenset())
            if known is None:
                continue
            if keys is None or keys - known:
                return True
        return False


class SpeculationState(enum.Enum):
    """
    Where a `WriteSpeculation` stands.
    """
    ASSUMING = 'assuming'
    DISCHARGED = 'discharged'
    REFUTED = 'refuted'


class SpeculationRefuted(Exception):
    """
    Raised by `WriteSpeculation.observe` at a build of the scan that records more than the build
    before it, and at every build after that one.
    """


class WriteSpeculation:
    """
    The record of a run that assumes every write on a built-in object the scan does not follow
    (`IntrinsicWrites.followable`) writes nothing. While it assumes, `observe` presents each build
    of the scan as following every write and compares it with the build before it: one that
    records more (`IntrinsicWrites.records_more_than`) refutes the assumption. A build that follows
    every write and records no more discharges it, and every later build is presented as it is.

    A run that ends discharged may keep its result. Each fold it made before the discharge read the
    record of some build and assumed nothing outside that record is written. No build records more
    than the one before, so the record of the discharging build, R, is part of every earlier one.
    Take an execution and the first write outside the record a fold relied on, if one happens: up to
    that moment every fold's premise held, so the discharged tree behaves alike up to it and makes
    the same write. That tree has no write the scan does not follow, so the write is in R, and so in
    every earlier record: no fold relied on its absence. So no such write happens. Code a splice
    brings in after the discharge is read by the scan as it is, as in any run.
    """

    def __init__(self):
        self.state = SpeculationState.ASSUMING
        self._record: IntrinsicWrites | None = None

    @property
    def assuming(self) -> bool:
        return self.state is SpeculationState.ASSUMING

    @property
    def discharged(self) -> bool:
        return self.state is SpeculationState.DISCHARGED

    def observe(self, writes: IntrinsicWrites) -> IntrinsicWrites:
        """
        The build *writes* of the scan as the run reads it: presented as following every write
        while the assumption holds, and as it is once the assumption is discharged. Raises
        `SpeculationRefuted` where *writes* records more than the build before it, and at every
        build once that has happened.
        """
        if self.state is SpeculationState.DISCHARGED:
            return writes
        if self.state is SpeculationState.REFUTED or (
            self._record is not None and writes.records_more_than(self._record)
        ):
            self.state = SpeculationState.REFUTED
            raise SpeculationRefuted
        self._record = writes
        if writes.followable:
            self.state = SpeculationState.DISCHARGED
            return writes
        return writes._replace(followable=True)


class UnfollowedWriteRefusals:
    """
    The record one deobfuscation run keeps of whether a question was answered no because the scan
    does not follow every write on a built-in object (`IntrinsicWrites.followable`), on any tree of
    the run. Only such an answer can refuse a fold, so a run whose last tree is not followed runs
    again under a `WriteSpeculation` only where one was given.
    """

    def __init__(self):
        self.refused = False

    def note(self) -> None:
        """
        Record that a question was answered no because the scan does not follow every write.
        """
        self.refused = True


def build_intrinsic_writes(model: SemanticModel) -> IntrinsicWrites:
    """
    The set of global names the program does anything with beyond reading them, and the property
    keys it writes on each of the names whose keys are watched.

    A name belongs to the first for binding it in any scope, assigning to it, writing or updating or
    deleting a property anywhere along a chain rooted at it (`Object.prototype.x = 1`,
    `Math.PI++`), installing a descriptor on it with `Object.defineProperty`, or handing it to
    code whose writes this analysis cannot enumerate.

    This is the per-name counterpart of
    `refinery.lib.scripts.js.analysis.effects._intrinsics_pristine`, which answers the same question
    for a fixed root set but collapses it to one program-wide flag. Keeping the answer per name is
    what lets a program that patches `Object.prototype` still have its `Math.floor` calls folded;
    the flag cannot express that, because one disturbed root disables every other one.

    Bindings cover every *assignment* form too, so no separate scan of write-role identifiers is
    needed: a bare `Math = 1` introduces an implicit-global binding for `Math`, as do the
    destructuring and `for`-target forms. Only property writes, deletes, and descriptor installs —
    which leave the name itself a plain read — need the explicit branches below.

    A write target names the intrinsic it patches only when the program spells it out.
    `var m = Math; m.floor = f` patches `Math` while mentioning it nowhere in the assignment, so the
    chain root is resolved through the values its binding may hold rather than taken as the name it
    is spelled with.

    A write need not be *anywhere* in the program for a name to belong here. Handing an intrinsic to
    code whose writes this analysis cannot enumerate — `patch(Math)` for a `patch` it cannot resolve
    — leaves the name looking untouched while its properties are replaced, so an intrinsic that
    escapes is recorded as written. `_value_escapes` decides which uses hand the value over.

    The keyed answer is the same scan read for the property a write names rather than only for the
    name it is rooted at, and it exists because the per-name question is too coarse for a caller
    that cares which property was replaced — a file patching `Object.prototype.z` has written
    `Object`, and refusing everything about `Object` on that basis refuses the very files the
    question is asked about.

    Only the *final* key of a chain is recorded, which is the one a write replaces:
    `Object.prototype.z = 9` replaces `z` and leaves `prototype` and `constructor` alone, so
    recording the keys it passes through would report a file as having patched the mechanism a
    caller is asking about when it did nothing of the kind. Every other route by which a name's
    properties can change — a binding that shadows it, a value that escapes, a computed key, a
    descriptor read from a value this analysis cannot read — bounds no key at all and is recorded
    as unbounded.
    """
    names: set[str] = set()
    keys: dict[str, set[str] | None] = {}

    def record_keys(found: frozenset[str], key: str | None) -> None:
        for name in found & KEYED_WRITE_ROOTS:
            if key is None:
                keys[name] = None
                continue
            known = keys.setdefault(name, set())
            if known is not None:
                known.add(key)

    def record(found: frozenset[str], key: str | None) -> None:
        names.update(found)
        record_keys(found, key)

    pending = [model.root_scope]
    while pending:
        scope = pending.pop()
        record(frozenset(scope.bindings), None)
        pending.extend(scope.children)
    aliases = _IntrinsicAliases(model)
    reach = _BuiltinReach(model, aliases)
    followable = True

    def record_escape(watched: frozenset[str]) -> None:
        nonlocal followable
        record_keys(watched, None)
        names.update(watched & ESCAPE_RECORDED_ROOTS)
        if watched & _KEY_RECORDED_ROOTS:
            followable = False

    for node in model.root.walk():
        if followable and (reach.trips_at(node) or _constructs_through_an_unread_key(model, node)):
            followable = False
        if isinstance(node, JsIdentifier):
            if not _names_a_member_property(node) and reference_role(node) is Role.READ:
                watched = aliases.names_denoted_by(node) & ESCAPE_WATCHED_ROOTS
                if watched and _value_escapes(model, aliases, node, watched):
                    record_escape(watched)
            continue
        if isinstance(node, JsMemberExpression):
            if not key_may_be(node, ESCAPE_WATCHED_ROOTS):
                continue
            key = key_text(node)
            watched = ESCAPE_WATCHED_ROOTS if key is None else frozenset({key})
            if (
                _records_a_watched_read(model, aliases, node, watched)
                and key_is(node, ESCAPE_WATCHED_ROOTS, model.assumed_keys)
            ):
                record_escape(watched)
            continue
        if isinstance(node, JsCallExpression):
            for install in accessor_installs(node):
                for base in _denoted_roots(install.target):
                    record(aliases.names_denoted_by(base), install.key)
                if install.key is not None and model.may_be_the_global_object(install.target):
                    record(frozenset({install.key}), None)
            continue
        for member in _written_members(_write_target(node)):
            for base in _member_chain_roots(member):
                record(aliases.names_denoted_by(base), key_text(member))
            written_global = model.may_name_a_global(member)
            if written_global is not None:
                record(frozenset({written_global}), None)
    return IntrinsicWrites(
        frozenset(names),
        {name: None if written is None else frozenset(written) for name, written in keys.items()},
        aliases,
        followable,
    )


def _records_a_watched_read(
    model: SemanticModel,
    aliases: _IntrinsicAliases,
    node: Node,
    names: frozenset[str],
) -> bool:
    """
    Whether what *node* evaluates to, which may be one of the watched *names*, is written through
    (`_written_through`) or escapes (`_value_escapes`).
    """
    return _written_through(node) or _value_escapes(model, aliases, node, names)


def _written_members(target: Node | None) -> Iterator[JsMemberExpression]:
    """
    Every member access a write to *target* may store through. A plain member target is that one
    access; a pattern holds one per position it assigns into, which `[Object.prototype.z] = [9]` and
    `({k: Object.prototype.z} = o)` both write a property through while naming no member target at
    the top. A pattern is read by walking it, so a member standing in a computed key inside one is
    yielded too — which over-reports a write and is the direction this whole scan fails in.
    """
    cursor = strip_parens(target)
    if isinstance(cursor, JsMemberExpression):
        yield cursor
    elif cursor is not None and not isinstance(cursor, JsIdentifier):
        for node in cursor.walk():
            if isinstance(node, JsMemberExpression):
                yield node


def _value_escapes(
    model: SemanticModel,
    aliases: _IntrinsicAliases,
    node: Node,
    names: frozenset[str],
    depth: int = 0,
) -> bool:
    """
    Whether the value read at *node* — which may denote the intrinsics *names* — reaches code that
    could write a property on it without this analysis seeing the write. A property read names its
    value at the member access, so a caller asks about `g.String` there, not at the name `String`.

    The question is deliberately inverted. Tracking where an intrinsic *flows to* would need a
    binder from each argument to its parameter, and that binder reaches none of the routes an
    obfuscator actually uses: a callback that receives the value, a function that returns it,
    `arguments`, spread, rest, or a method on an object literal. Asking instead whether the value
    leaves a position whose effect is *known* covers all of them at once, and fails in the safe
    direction by construction — an unrecognized position counts as an escape, which costs an
    unfolded call rather than a wrong value.

    The positions that hand nothing over, and so must stay free or every fold collapses:

    - a member base, when the key cannot yield the intrinsic's own mutable surface
      (`Math.floor(1.7)`)
    - a callee of a call or of `new`, which consumes it (`parseInt(x)`, `new RegExp(p)`)
    - an operator operand, which reads a value without capturing the object (`typeof Math`), except
      the left of `instanceof`, which is handed to the right operand's `Symbol.hasInstance` method
    - a hole of an untagged template; a tagged template hands its holes to the tag as arguments
    - the test of a branch or a loop, which converts it to a boolean and calls nothing on an object
      (`if (String.prototype)`)
    - a rebinding whose target the alias analysis still resolves to the same names (`var m = Math`)
    - a return of a function whose every call the text shows, where the value at none of those
      calls escapes and none is written through (`_returned_value_escapes`)

    That last arm is what makes one predicate serve both this scan and the parameter-escape question
    inside `_callee_is_write_free`, rather than two walks differing by a flag. A rebinding is safe
    precisely when a later write through the new name is still attributed back, which is a question
    `_IntrinsicAliases` already answers: `var m = Math` is spared because `m` denotes `Math`, while
    `save = o` inside a callee is not, because a parameter denotes nothing and the attribution chain
    dies there. The *names* being non-empty is therefore load-bearing — an empty set is a subset of
    everything, and would spare the very case the arm exists to catch.
    """
    value = _forwarded_value(node)
    if value is None:
        return False
    target = _rebinding_target(value)
    if target is not None:
        return not (names and names <= _names_bound_to(model, aliases, target))
    parent = value.parent
    if (
        isinstance(parent, JsReturnStatement)
        or isinstance(parent, JsArrowFunctionExpression) and parent.body is value
    ):
        return _returned_value_escapes(model, aliases, value, names, depth)
    return _hands_over(model, aliases, value, depth)


def _rebinding_target(value: Node) -> Node | None:
    """
    The target *value* is stored into, where it is the initializer of a declarator or the right
    side of an assignment, or `None` where it stands anywhere else.
    """
    parent = value.parent
    if isinstance(parent, JsVariableDeclarator) and parent.init is value:
        return parent.id
    if isinstance(parent, JsAssignmentExpression) and parent.right is value:
        return parent.left
    return None


def _hands_over(model: SemanticModel, aliases: _IntrinsicAliases, value: Node, depth: int) -> bool:
    """
    Whether the position *value* stands in hands its value to code that could write a property on
    it unseen: every position but those `_value_escapes` lists as handing nothing over, where a
    rebinding (`_rebinding_target`) and a return count as handing it over. Whether either of those
    spares the value depends on the names it may denote, which only `_value_escapes` knows.
    """
    parent = value.parent
    if isinstance(parent, _TESTED_FORMS) and parent.test is value:
        return False
    if isinstance(parent, JsNewExpression) and parent.callee is value:
        return False
    if isinstance(parent, JsCallExpression):
        if parent.callee is value:
            return False
        callee = unambiguous_callee(model, parent)
        return not _callee_is_write_free(model, aliases, callee, depth + 1)
    if isinstance(parent, JsBinaryExpression) and parent.operator == 'instanceof':
        return parent.left is value
    if isinstance(parent, JsTemplateLiteral):
        return isinstance(parent.parent, JsTaggedTemplateExpression)
    if isinstance(parent, (JsUnaryExpression, JsBinaryExpression)):
        return False
    return True


def _returned_value_escapes(
    model: SemanticModel,
    aliases: _IntrinsicAliases,
    value: Node,
    names: frozenset[str],
    depth: int,
) -> bool:
    """
    Whether *value*, returned by the function enclosing it, escapes where that function returns it:
    every call and construction of the function is shown (`SemanticModel.shown_calls`), the value
    escapes at none of them, and none is the foot of a member chain written through or installed on
    (`_written_through`), a write the scan attributes to the name at the foot of a chain and so
    never to a call. A generator or an async function hands its value to an object, which escapes.
    """
    function = enclosing_function(value)
    if not isinstance(function, FUNCTION_NODES) or depth > _CALLEE_DEPTH_LIMIT or function.is_async:
        return True
    if isinstance(function, (JsFunctionDeclaration, JsFunctionExpression)) and function.generator:
        return True
    calls = model.shown_calls(function)
    if calls is None:
        return True
    return any(
        _written_through(call) or _value_escapes(model, aliases, call, names, depth + 1)
        for call in calls
    )


def _written_through(value: Node) -> bool:
    """
    Whether a member chain whose foot is *value*, looking through the forms that forward it, is
    written or deleted somewhere along it, or invokes on what it holds an accessor install or a
    method that writes its receiver (`_invokes_a_write`).
    """
    cursor = value
    while (parent := cursor.parent) is not None:
        if isinstance(parent, JsMemberExpression):
            if parent.object is not cursor:
                return False
            if is_member_write_target(parent) or _invokes_a_write(parent):
                return True
        elif not isinstance(parent, _VALUE_FORWARDING_NODES):
            return False
        cursor = parent
    return False


def _invokes_a_write(member: JsMemberExpression) -> bool:
    """
    Whether *member* is invoked under a key that may be an accessor installer
    (`refinery.lib.scripts.js.model.ACCESSOR_INSTALL_METHODS`) or a method that writes the object
    it is read off (`refinery.lib.scripts.js.builtins.RECEIVER_WRITING_METHODS`):
    `globalThis.Array.prototype.push(5)` stores an element every array then inherits.
    """
    return is_invocation_target(member) and key_may_be(member, _WRITING_METHODS)


def _names_a_member_property(node: JsIdentifier) -> bool:
    """
    Whether *node* is the name a dotted member access reads, whose value is the access itself.
    """
    parent = node.parent
    if not isinstance(parent, JsMemberExpression):
        return False
    return parent.property is node and not parent.computed


def _write_target(node: Node) -> Node | None:
    """
    The target the write at *node* stores through: the left of an assignment, the operand of an
    update or a `delete`, or the head of a `for`-`in` or `for`-`of`; `None` where *node* writes
    nothing.
    """
    if isinstance(node, JsAssignmentExpression):
        return node.left
    if isinstance(node, JsUpdateExpression):
        return node.argument
    if isinstance(node, JsUnaryExpression) and node.operator == 'delete':
        return node.operand
    if isinstance(node, (JsForInStatement, JsForOfStatement)):
        return node.left
    return None


def _forwarded_value(node: Node) -> Node | None:
    """
    The outermost expression still carrying *node*'s value, or `None` when no enclosing form can
    hand that value on. The walk looks through the forms that forward a value unchanged —
    parentheses, the operands of `||`/`&&`/`??`, the branches of a conditional, the last expression
    of a sequence, and a spread — and through a member access only when its key reaches the
    intrinsic's own surface, since `p(Array.prototype)` hands over an object whose properties decide
    what `[1, 2].join()` means while `p(Math.PI)` hands over a number nobody consults.

    Strictly outward through `parent`, so unlike `_denoted_roots` — which recurses *into* an
    expression and needs `_DENOTED_ROOT_DEPTH_LIMIT` — this terminates on the finite path to the
    root without a limit.
    """
    cursor: Node = node
    while True:
        parent = cursor.parent
        if parent is None:
            return None
        if isinstance(parent, JsMemberExpression) and parent.object is cursor:
            if not _reaches_intrinsic_surface(parent):
                return None
            cursor = parent
            continue
        if isinstance(parent, JsConditionalExpression) and parent.test is cursor:
            return cursor
        if isinstance(parent, _VALUE_FORWARDING_NODES):
            cursor = parent
            continue
        return cursor


def _reaches_intrinsic_surface(member: JsMemberExpression) -> bool:
    """
    Whether reading *member*'s key off an intrinsic can yield an object sharing that intrinsic's
    mutable surface. A key not known may be any of them, so it counts: a missed reach is a name
    that keeps its trust while the program patches it.
    """
    return key_may_be(member, _SURFACE_KEYS)


def _names_bound_to(
    model: SemanticModel, aliases: _IntrinsicAliases, target: Node | None
) -> frozenset[str]:
    """
    The intrinsic names a value stored into *target* may still be found under, so a rebinding that
    keeps the value reachable by name is not an escape. A destructuring or member target yields
    nothing, since neither leaves a name this analysis resolves writes through.

    Both binding lookups are needed. A declarator id is not a *reference*, so `resolve` finds
    nothing for it and only `refinery.lib.scripts.js.analysis.model.SemanticModel.binding_of`
    answers; an assignment target is a reference and only `resolve` does.
    """
    if not isinstance(target, JsIdentifier):
        return frozenset()
    binding = model.binding_of(target) or model.resolve(target)
    if binding is None:
        return frozenset({target.name})
    return aliases.names_of(binding)


def _callee_is_write_free(
    model: SemanticModel,
    aliases: _IntrinsicAliases,
    func: JsFunctionDeclaration | JsFunctionExpression | JsArrowFunctionExpression | None,
    depth: int,
) -> bool:
    """
    Whether a call to *func* provably writes no property reachable from one of its parameters, and
    lets no parameter escape further. This is what keeps the escape rule from refusing every call:
    `log(Math)` for a `log` that only reads `o.PI` hands the intrinsic to code whose writes are
    fully enumerable, so `Math` keeps its trust.

    Fails closed on every way the enumeration could be incomplete — an unresolvable callee, a rest
    or destructured parameter whose contents no name tracks, a reachable `arguments` object, or
    recursion past `_CALLEE_DEPTH_LIMIT`. Each of those means a parameter's value could be written
    through somewhere this scan does not look. The writes are read off the targets as
    `build_intrinsic_writes` reads them (`_written_members`): a pattern, `[p.now] = [f]`, and the
    head of a `for`-`in` or `for`-`of` store through a member as a plain assignment does.

    The parameter-escape question routes back through `_value_escapes` rather than scanning for
    identifiers, so a callee that merely *reads* through its parameter (`return o.PI`) stays
    write-free while one that passes it on (`g(o)`) does not. That reuse also answers the return
    case: a parameter returned goes wherever each call of the callee puts its value, and one a call
    may receive another way escapes, as do `return [o]` and `return { m: o }`.

    The answer depends on *func* and *depth* alone, so one scan decides it once for each pair
    (`_IntrinsicAliases.write_free`): a function that returns its parameter is asked about at each
    of its calls, and deciding it walks every one of them (`_returned_value_escapes`).
    """
    if func is None or depth > _CALLEE_DEPTH_LIMIT:
        return False
    key = func, depth
    known = aliases.write_free.get(key)
    if known is None:
        known = aliases.write_free[key] = _parameters_stay_unwritten(model, aliases, func, depth)
    return known


def _parameters_stay_unwritten(
    model: SemanticModel,
    aliases: _IntrinsicAliases,
    func: JsFunctionDeclaration | JsFunctionExpression | JsArrowFunctionExpression,
    depth: int,
) -> bool:
    """
    The answer `_callee_is_write_free` gives for *func* at *depth*, decided anew.
    """
    scope = model.parameter_scope(func)
    if scope is None:
        return False
    if not isinstance(func, JsArrowFunctionExpression):
        binding = scope.bindings.get('arguments')
        if binding is not None and (model.references(binding) or model.reflection_can_reach(binding)):
            return False
    names = [param.name for param in func.params if isinstance(param, JsIdentifier)]
    if len(names) != len(func.params):
        return False
    params = frozenset(names)
    if not params:
        return True
    body = getattr(func, 'body', None)
    if body is None:
        return False
    for node in body.walk():
        if any(
            base.name in params
            for member in _written_members(_write_target(node))
            for base in _member_chain_roots(member)
        ):
            return False
        if isinstance(node, JsIdentifier) and node.name in params:
            if not _names_a_member_property(node) and reference_role(node) is Role.READ:
                names = aliases.names_denoted_by(node)
                if _value_escapes(model, aliases, node, names, depth):
                    return False
    return True


def unambiguous_callee(
    model: SemanticModel, call: JsCallExpression
) -> JsFunctionDeclaration | JsFunctionExpression | JsArrowFunctionExpression | None:
    """
    The function *call* certainly invokes for a consumer that cannot order the call against a
    reassignment of the callee's name, or `None`. The module-scope form of
    `refinery.lib.scripts.js.analysis.effects.EffectModel.unambiguous_callee`, which delegates here:
    the answer needs only the model, so `build_intrinsic_writes`, which runs before any effect model
    exists, can still ask it.
    """
    callee = call.callee
    if isinstance(callee, (JsFunctionExpression, JsArrowFunctionExpression)):
        return callee
    if not isinstance(callee, JsIdentifier):
        return None
    return unambiguous_function(model, model.resolve(callee))


def unambiguous_function(
    model: SemanticModel, binding: Binding | None
) -> JsFunctionDeclaration | JsFunctionExpression | JsArrowFunctionExpression | None:
    """
    The module-scope form of
    `refinery.lib.scripts.js.analysis.effects.EffectModel.unambiguous_function`, which delegates
    here. See that method for which bindings qualify.
    """
    value = model.singular_value(binding)
    return value if isinstance(value, FUNCTION_NODES) else None


class _IntrinsicAliases:
    """
    Resolves the identifier at the root of a write target to every name it may denote, so that a
    property write reaching an intrinsic through a local is attributed to the intrinsic rather than
    to the local. `var m = Math; m.floor = f` must record `Math`, or the write stays invisible to
    every consumer of `IntrinsicWrites.names` and `Math.floor(1.7)` goes on folding to the built-in.

    A *may* analysis on purpose: every value a binding can hold contributes, so one branch assigning
    an intrinsic is enough to poison the name. The direction is forced — missing an alias yields a
    wrong value, while an extra name yields an unfolded call — and it matches how the
    accessor-install targets are already over-approximated, `Object.defineProperty(0 || Math, …)`
    among them.

    The backward step is `_denoted_roots`, the same value-preserving walk the install-target scan
    uses, reused rather than reimplemented for two reasons. It already looks through exactly the
    forms a fold collapses (`||`, `&&`, `??`, conditional, sequence-last, assignment-RHS, parens),
    which is what keeps this answer stable while passes run — the pinning contract in
    `refinery.lib.scripts.js.analysis.cache.ModelCache` requires that this set never *grow* across a
    pass. And it stops at a call, so `var s = String.fromCharCode(x)` does not alias `String`: the
    local holds the *result*. Its member-chain arm over-approximates in the one remaining direction
    — `var n = Array.length` reports `Array` — which is sound and costs nothing.
    """

    def __init__(self, model: SemanticModel):
        self.model = model
        self._answers: dict[Binding, frozenset[str]] = {}
        self._sources: dict[Binding, tuple[frozenset[str], tuple[Binding, ...]]] = {}
        self.write_free: dict[tuple[Node, int], bool] = {}
        """
        What `_callee_is_write_free` decided of each callee at each depth, during the scan that
        built this relation and threads it through every question it asks.
        """

    def names_denoted_by(self, node: JsIdentifier) -> frozenset[str]:
        """
        Every intrinsic-root name *node* may denote, including its own when it names one directly. A
        name that resolves to no binding is a free global and denotes itself.
        """
        if node.name in PURE_INTRINSIC_ROOTS:
            return frozenset({node.name})
        binding = self.model.resolve(node)
        if binding is None:
            return frozenset({node.name})
        return self.names_of(binding)

    def names_of(self, binding: Binding) -> frozenset[str]:
        """
        Every name a value of *binding* may denote. The binding-level entry point, for a caller
        holding a binding rather than a reference to it — resolving a *write* target, whose
        declaration id is not a reference at all.

        A name holding another name denotes everything that one does, through chains of any length
        and through cycles (`a = b; b = a`). The bindings not yet answered that *binding* reaches
        are split into strongly connected components: the members of one reach the same bindings and
        share one answer, and each component comes after every component it reaches, whose answers
        it takes over. A binding that holds no name still unanswered is a component of its own and
        is answered without the search, which is how most bindings are asked about.
        """
        answer = self._answers.get(binding)
        if answer is not None:
            return answer
        if not self._unanswered_sources(binding):
            self._answer([binding])
        else:
            for component in strongly_connected_components((binding,), self._unanswered_sources):
                self._answer(component)
        return self._answers[binding]

    def _answer(self, component: list[Binding]):
        """
        Give every member of *component* the one answer they share: the names each of them denotes
        directly, and the answer of every binding outside the component that one of them holds.
        """
        members = set(component)
        found: set[str] = set()
        for member in component:
            names, sources = self._sources_of(member)
            found.update(names)
            for source in sources:
                if source not in members:
                    found.update(self._answers[source])
        answer = frozenset(found)
        for member in component:
            self._answers[member] = answer

    def _unanswered_sources(self, binding: Binding) -> list[Binding]:
        return [source for source in self._sources_of(binding)[1] if source not in self._answers]

    def _sources_of(self, binding: Binding) -> tuple[frozenset[str], tuple[Binding, ...]]:
        """
        The names a value of *binding* denotes directly, and the bindings of the names it holds,
        memoized per binding. A root spelled as a pure intrinsic denotes it even where a local of
        that name exists, and a root that resolves to no binding is a free global denoting itself.
        """
        known = self._sources.get(binding)
        if known is None:
            names: set[str] = set()
            sources: list[Binding] = []
            for root in _binding_value_roots(binding):
                if root.name in PURE_INTRINSIC_ROOTS:
                    names.add(root.name)
                    continue
                source = self.model.resolve(root)
                if source is None:
                    names.add(root.name)
                else:
                    sources.append(source)
            known = self._sources[binding] = frozenset(names), tuple(sources)
        return known


def _binding_value_roots(binding: Binding) -> Iterator[JsIdentifier]:
    """
    Every name a value of *binding* may denote, over its declarations' initializers and the right
    side of every plain assignment to it. Both are needed: a binding declared empty and assigned
    later (`var m; m = Math`) holds the intrinsic just as one initialized with it does.

    A write the model cannot pin to a value
    (`refinery.lib.scripts.js.analysis.model.Binding.indefinite_writes`) contributes as well. This
    is a *may* analysis, and `arguments[k] = Math` stores the intrinsic under a parameter's name
    whether or not the text says which parameter or whether the call supplied it; leaving it out is
    exactly the missed alias the caller's docstring names as a wrong answer.

    The may-side sibling of `refinery.lib.scripts.js.analysis.model.SemanticModel.binding_values`,
    deliberately wider than its readable channels: a compound assignment's right side contributes
    here where the must-query refuses the whole binding, because `_value_escapes`'s rebinding arm
    spares a target only while the names it may denote are still attributed back, and narrowing this
    walk would turn those rebindings into escapes. A channel neither walk reads — an intrinsic
    stored through a pattern, a parameter fed at a call site — is covered at its source instead: the
    intrinsic *read* that fed it escapes, which withdraws the key trust there.
    """
    for declaration in binding.declarations:
        parent = getattr(declaration, 'parent', None)
        initializer = getattr(parent, 'init', None)
        if initializer is not None:
            yield from _denoted_roots(initializer)
    for reference in (*binding.writes, *binding.indefinite_writes):
        parent = getattr(reference, 'parent', None)
        if isinstance(parent, JsAssignmentExpression) and parent.left is reference:
            yield from _denoted_roots(parent.right)


def denoting_leaves(node: Node | None, depth: int = 0) -> Iterator[Node]:
    """
    Every node whose value *node* may evaluate to, looking through the value-preserving forms a
    constant fold collapses: parentheses, the operands of `||`/`&&`/`??` and the branches of a
    conditional (either side may be the value), the last expression of a sequence, and the right
    side of an assignment. A member access yields the foot of its chain, `Object` for
    `Object.prototype.x`, which is what a write through the access is attributed to.

    Resolving only the syntactic form would make an answer read off these leaves change as folds
    fire — `Math || 0` names nothing until it collapses to `Math` — which is precisely what a
    consumer holding the answer across a pass cannot tolerate.
    """
    if depth > _DENOTED_ROOT_DEPTH_LIMIT:
        return
    cursor = strip_parens(node)
    if cursor is None:
        return
    if isinstance(cursor, JsMemberExpression):
        foot = _member_chain_foot(cursor)
        if foot is not None:
            yield foot
    elif isinstance(cursor, JsLogicalExpression):
        yield from denoting_leaves(cursor.left, depth + 1)
        yield from denoting_leaves(cursor.right, depth + 1)
    elif isinstance(cursor, JsConditionalExpression):
        yield from denoting_leaves(cursor.consequent, depth + 1)
        yield from denoting_leaves(cursor.alternate, depth + 1)
    elif isinstance(cursor, JsSequenceExpression):
        if cursor.expressions:
            yield from denoting_leaves(cursor.expressions[-1], depth + 1)
    elif isinstance(cursor, JsAssignmentExpression):
        yield from denoting_leaves(cursor.right, depth + 1)
    else:
        yield cursor


def _denoted_roots(node: Node | None) -> Iterator[JsIdentifier]:
    """
    Every name *node* may denote: the identifiers among its `denoting_leaves`.
    """
    for leaf in denoting_leaves(node):
        if isinstance(leaf, JsIdentifier):
            yield leaf


def _member_chain_foot(node: JsMemberExpression) -> Node | None:
    """
    The node at the foot of the member-access chain *node*, looking through parentheses.
    """
    cursor: Node | None = node
    while isinstance(cursor, JsMemberExpression):
        cursor = strip_parens(cursor.object)
    return cursor


def _is_member_object(node: Node) -> bool:
    """
    Whether *node* is the object a member access reads its property off, looking through
    parentheses.
    """
    cursor = node
    while isinstance(parent := cursor.parent, JsParenthesizedExpression):
        cursor = parent
    return isinstance(parent, JsMemberExpression) and parent.object is cursor


def _member_chain_roots(node: Node | None) -> Iterator[JsIdentifier]:
    """
    The names the foot of a member-access chain may evaluate to (`_denoted_roots`), none where
    *node* is no member access. `Math.prototype.x` roots at `Math`, so a write anywhere along the
    chain is attributed to the name that owns it; testing only the immediate `.object` would miss
    every nested write. A foot written `(0, Math)`, `(Math || m)` or `c ? Math : Date` roots at
    every name it may be, as an escape through those forms is attributed
    (`_VALUE_FORWARDING_NODES`).
    """
    cursor = strip_parens(node)
    if isinstance(cursor, JsMemberExpression):
        yield from _denoted_roots(_member_chain_foot(cursor))

Global variables

var SPECIES_KEYS

The two property names that decide what an allocating Array.prototype method returns. ArraySpeciesCreate reads constructor[Symbol.species] off the receiver, and __proto__ replaces the prototype that constructor lookup walks, so writing either can make the "newly created" array be a shared object — or make the call throw, by leaving a primitive where a constructor is expected.

var PROTOTYPE_OWNERS

The intrinsic whose prototype supplies the methods of each interpreter value type, keyed by type name so this module needs no import from the interpreter that depends on it. A method call on a literal receiver names no global at the call site, so trusting it means asking whether this prototype is intact: String.prototype.toUpperCase = f is a write to String, and it changes what 'ab'.toUpperCase() means even though the expression mentions no identifier at all.

Every type in the interpreter's value domain is named here directly, including JsBuffer, whose methods come from Buffer.prototype rather than the Array.prototype its list base would suggest. A function value is represented as its own AST node, so the two function node names appear here as value types rather than as syntax; both inherit from Function.prototype. Lookup is exact rather than a walk up the Python MRO, which would silently answer Array for any future list subclass instead of refusing. A type with no entry is never trusted through this route.

var INHERITED_CHAIN_ROOTS

The prototypes every value inherits from beyond the one that owns its own methods. Object.prototype roots every chain, so a getter installed there is reached by a plain read on an array literal and on Math alike — which is why reading a property is a strictly stronger requirement than calling a method.

var KEYED_WRITE_ROOTS

The global names whose written property keys IntrinsicWrites.key_written() bounds. A name outside this set is one the scan records no key for, so answering False about it would read an absence of evidence as evidence of absence; that predicate answers True for every key of such a name instead.

The set is the union of the names this module already watches for a reason: the intrinsics whose methods are trusted, the roots a plain property read walks through, and the owners of the prototypes that supply each value type's members. A caller asking about a name outside it is asking a question this scan was not built to answer, and is told so.

var ESCAPE_RECORDED_ROOTS

The global names an escape records as written by name, not only by key: the names a fold trusts to run code. A fold runs the methods of the pure roots, a fold that decides what a regular expression answers trusts RegExp, so p(RegExp) for a p that replaces RegExp.prototype.test must withdraw that trust, a fold that decides a comparison of the clock trusts Date, which Reflect.set(Date, 'now', f) must withdraw, and a fold that converts an array iterator trusts the prototype Iterator holds, which every such iterator inherits.

Object and Function are left out on purpose. Real samples hand Object to a call this scan cannot resolve, and recording that escape refuses every fold that trusts Object.prototype in them; the precise answer follows the escaped value to its writes, which this scan does not do.

var ESCAPE_WATCHED_ROOTS

The global names whose escape the scan looks for: every name it records keys for, and every name ESCAPE_RECORDED_ROOTS records by name.

Functions

def build_intrinsic_writes(model)

The set of global names the program does anything with beyond reading them, and the property keys it writes on each of the names whose keys are watched.

A name belongs to the first for binding it in any scope, assigning to it, writing or updating or deleting a property anywhere along a chain rooted at it (Object.prototype.x = 1, Math.PI++), installing a descriptor on it with Object.defineProperty, or handing it to code whose writes this analysis cannot enumerate.

This is the per-name counterpart of refinery.lib.scripts.js.analysis.effects._intrinsics_pristine, which answers the same question for a fixed root set but collapses it to one program-wide flag. Keeping the answer per name is what lets a program that patches Object.prototype still have its Math.floor calls folded; the flag cannot express that, because one disturbed root disables every other one.

Bindings cover every assignment form too, so no separate scan of write-role identifiers is needed: a bare Math = 1 introduces an implicit-global binding for Math, as do the destructuring and for-target forms. Only property writes, deletes, and descriptor installs — which leave the name itself a plain read — need the explicit branches below.

A write target names the intrinsic it patches only when the program spells it out. var m = Math; m.floor = f patches Math while mentioning it nowhere in the assignment, so the chain root is resolved through the values its binding may hold rather than taken as the name it is spelled with.

A write need not be anywhere in the program for a name to belong here. Handing an intrinsic to code whose writes this analysis cannot enumerate — patch(Math) for a patch it cannot resolve — leaves the name looking untouched while its properties are replaced, so an intrinsic that escapes is recorded as written. _value_escapes decides which uses hand the value over.

The keyed answer is the same scan read for the property a write names rather than only for the name it is rooted at, and it exists because the per-name question is too coarse for a caller that cares which property was replaced — a file patching Object.prototype.z has written Object, and refusing everything about Object on that basis refuses the very files the question is asked about.

Only the final key of a chain is recorded, which is the one a write replaces: Object.prototype.z = 9 replaces z and leaves prototype and constructor alone, so recording the keys it passes through would report a file as having patched the mechanism a caller is asking about when it did nothing of the kind. Every other route by which a name's properties can change — a binding that shadows it, a value that escapes, a computed key, a descriptor read from a value this analysis cannot read — bounds no key at all and is recorded as unbounded.

Expand source code Browse git

def build_intrinsic_writes(model: SemanticModel) -> IntrinsicWrites:
    """
    The set of global names the program does anything with beyond reading them, and the property
    keys it writes on each of the names whose keys are watched.

    A name belongs to the first for binding it in any scope, assigning to it, writing or updating or
    deleting a property anywhere along a chain rooted at it (`Object.prototype.x = 1`,
    `Math.PI++`), installing a descriptor on it with `Object.defineProperty`, or handing it to
    code whose writes this analysis cannot enumerate.

    This is the per-name counterpart of
    `refinery.lib.scripts.js.analysis.effects._intrinsics_pristine`, which answers the same question
    for a fixed root set but collapses it to one program-wide flag. Keeping the answer per name is
    what lets a program that patches `Object.prototype` still have its `Math.floor` calls folded;
    the flag cannot express that, because one disturbed root disables every other one.

    Bindings cover every *assignment* form too, so no separate scan of write-role identifiers is
    needed: a bare `Math = 1` introduces an implicit-global binding for `Math`, as do the
    destructuring and `for`-target forms. Only property writes, deletes, and descriptor installs —
    which leave the name itself a plain read — need the explicit branches below.

    A write target names the intrinsic it patches only when the program spells it out.
    `var m = Math; m.floor = f` patches `Math` while mentioning it nowhere in the assignment, so the
    chain root is resolved through the values its binding may hold rather than taken as the name it
    is spelled with.

    A write need not be *anywhere* in the program for a name to belong here. Handing an intrinsic to
    code whose writes this analysis cannot enumerate — `patch(Math)` for a `patch` it cannot resolve
    — leaves the name looking untouched while its properties are replaced, so an intrinsic that
    escapes is recorded as written. `_value_escapes` decides which uses hand the value over.

    The keyed answer is the same scan read for the property a write names rather than only for the
    name it is rooted at, and it exists because the per-name question is too coarse for a caller
    that cares which property was replaced — a file patching `Object.prototype.z` has written
    `Object`, and refusing everything about `Object` on that basis refuses the very files the
    question is asked about.

    Only the *final* key of a chain is recorded, which is the one a write replaces:
    `Object.prototype.z = 9` replaces `z` and leaves `prototype` and `constructor` alone, so
    recording the keys it passes through would report a file as having patched the mechanism a
    caller is asking about when it did nothing of the kind. Every other route by which a name's
    properties can change — a binding that shadows it, a value that escapes, a computed key, a
    descriptor read from a value this analysis cannot read — bounds no key at all and is recorded
    as unbounded.
    """
    names: set[str] = set()
    keys: dict[str, set[str] | None] = {}

    def record_keys(found: frozenset[str], key: str | None) -> None:
        for name in found & KEYED_WRITE_ROOTS:
            if key is None:
                keys[name] = None
                continue
            known = keys.setdefault(name, set())
            if known is not None:
                known.add(key)

    def record(found: frozenset[str], key: str | None) -> None:
        names.update(found)
        record_keys(found, key)

    pending = [model.root_scope]
    while pending:
        scope = pending.pop()
        record(frozenset(scope.bindings), None)
        pending.extend(scope.children)
    aliases = _IntrinsicAliases(model)
    reach = _BuiltinReach(model, aliases)
    followable = True

    def record_escape(watched: frozenset[str]) -> None:
        nonlocal followable
        record_keys(watched, None)
        names.update(watched & ESCAPE_RECORDED_ROOTS)
        if watched & _KEY_RECORDED_ROOTS:
            followable = False

    for node in model.root.walk():
        if followable and (reach.trips_at(node) or _constructs_through_an_unread_key(model, node)):
            followable = False
        if isinstance(node, JsIdentifier):
            if not _names_a_member_property(node) and reference_role(node) is Role.READ:
                watched = aliases.names_denoted_by(node) & ESCAPE_WATCHED_ROOTS
                if watched and _value_escapes(model, aliases, node, watched):
                    record_escape(watched)
            continue
        if isinstance(node, JsMemberExpression):
            if not key_may_be(node, ESCAPE_WATCHED_ROOTS):
                continue
            key = key_text(node)
            watched = ESCAPE_WATCHED_ROOTS if key is None else frozenset({key})
            if (
                _records_a_watched_read(model, aliases, node, watched)
                and key_is(node, ESCAPE_WATCHED_ROOTS, model.assumed_keys)
            ):
                record_escape(watched)
            continue
        if isinstance(node, JsCallExpression):
            for install in accessor_installs(node):
                for base in _denoted_roots(install.target):
                    record(aliases.names_denoted_by(base), install.key)
                if install.key is not None and model.may_be_the_global_object(install.target):
                    record(frozenset({install.key}), None)
            continue
        for member in _written_members(_write_target(node)):
            for base in _member_chain_roots(member):
                record(aliases.names_denoted_by(base), key_text(member))
            written_global = model.may_name_a_global(member)
            if written_global is not None:
                record(frozenset({written_global}), None)
    return IntrinsicWrites(
        frozenset(names),
        {name: None if written is None else frozenset(written) for name, written in keys.items()},
        aliases,
        followable,
    )

def unambiguous_callee(model, call)

The function call certainly invokes for a consumer that cannot order the call against a reassignment of the callee's name, or None. The module-scope form of EffectModel.unambiguous_callee(), which delegates here: the answer needs only the model, so build_intrinsic_writes(), which runs before any effect model exists, can still ask it.

Expand source code Browse git

def unambiguous_callee(
    model: SemanticModel, call: JsCallExpression
) -> JsFunctionDeclaration | JsFunctionExpression | JsArrowFunctionExpression | None:
    """
    The function *call* certainly invokes for a consumer that cannot order the call against a
    reassignment of the callee's name, or `None`. The module-scope form of
    `refinery.lib.scripts.js.analysis.effects.EffectModel.unambiguous_callee`, which delegates here:
    the answer needs only the model, so `build_intrinsic_writes`, which runs before any effect model
    exists, can still ask it.
    """
    callee = call.callee
    if isinstance(callee, (JsFunctionExpression, JsArrowFunctionExpression)):
        return callee
    if not isinstance(callee, JsIdentifier):
        return None
    return unambiguous_function(model, model.resolve(callee))

def unambiguous_function(model, binding)

The module-scope form of EffectModel.unambiguous_function(), which delegates here. See that method for which bindings qualify.

Expand source code Browse git

def unambiguous_function(
    model: SemanticModel, binding: Binding | None
) -> JsFunctionDeclaration | JsFunctionExpression | JsArrowFunctionExpression | None:
    """
    The module-scope form of
    `refinery.lib.scripts.js.analysis.effects.EffectModel.unambiguous_function`, which delegates
    here. See that method for which bindings qualify.
    """
    value = model.singular_value(binding)
    return value if isinstance(value, FUNCTION_NODES) else None

def denoting_leaves(node, depth=0)

Every node whose value node may evaluate to, looking through the value-preserving forms a constant fold collapses: parentheses, the operands of ||/&&/?? and the branches of a conditional (either side may be the value), the last expression of a sequence, and the right side of an assignment. A member access yields the foot of its chain, Object for Object.prototype.x, which is what a write through the access is attributed to.

Resolving only the syntactic form would make an answer read off these leaves change as folds fire — Math || 0 names nothing until it collapses to Math — which is precisely what a consumer holding the answer across a pass cannot tolerate.

Expand source code Browse git

def denoting_leaves(node: Node | None, depth: int = 0) -> Iterator[Node]:
    """
    Every node whose value *node* may evaluate to, looking through the value-preserving forms a
    constant fold collapses: parentheses, the operands of `||`/`&&`/`??` and the branches of a
    conditional (either side may be the value), the last expression of a sequence, and the right
    side of an assignment. A member access yields the foot of its chain, `Object` for
    `Object.prototype.x`, which is what a write through the access is attributed to.

    Resolving only the syntactic form would make an answer read off these leaves change as folds
    fire — `Math || 0` names nothing until it collapses to `Math` — which is precisely what a
    consumer holding the answer across a pass cannot tolerate.
    """
    if depth > _DENOTED_ROOT_DEPTH_LIMIT:
        return
    cursor = strip_parens(node)
    if cursor is None:
        return
    if isinstance(cursor, JsMemberExpression):
        foot = _member_chain_foot(cursor)
        if foot is not None:
            yield foot
    elif isinstance(cursor, JsLogicalExpression):
        yield from denoting_leaves(cursor.left, depth + 1)
        yield from denoting_leaves(cursor.right, depth + 1)
    elif isinstance(cursor, JsConditionalExpression):
        yield from denoting_leaves(cursor.consequent, depth + 1)
        yield from denoting_leaves(cursor.alternate, depth + 1)
    elif isinstance(cursor, JsSequenceExpression):
        if cursor.expressions:
            yield from denoting_leaves(cursor.expressions[-1], depth + 1)
    elif isinstance(cursor, JsAssignmentExpression):
        yield from denoting_leaves(cursor.right, depth + 1)
    else:
        yield cursor

Classes

class IntrinsicWrites (names, keys, aliases, followable)

What one scan of a program says about the globals it writes: names, the set a caller asks about a whole name with, and keys, the properties each of the watched names was written at — or None for a name whose written keys this scan cannot bound. aliases is the relation the scan resolved write targets through, kept for follows_only_through_bindings. followable says whether the scan follows every write the program makes on a built-in object: none reaches one through a value read without spelling its owner (_BuiltinReach), no watched name is handed off, nor read as a property and handed off or written through, where the scan records the escape by key alone (_KEY_RECORDED_ROOTS), and, under the model that suspects code it cannot read, no call runs through a key the reflection check leaves uncounted (_constructs_through_an_unread_key). A fold that reads a built-in's chain or converts an object without spelling its owner asks it on top of the questions about names.

The two are produced together because they are read off the same nodes and must not disagree: a name recorded in one for a reason the other cannot express is a name one caller refuses and the other clears. Where a write cannot be pinned to a key, keys records the name unbounded rather than omitting it, so keys never reports less about a name than names does.

Expand source code Browse git

class IntrinsicWrites(NamedTuple):
    """
    What one scan of a program says about the globals it writes: *names*, the set a caller asks
    about a whole name with, and *keys*, the properties each of the watched names was written at —
    or `None` for a name whose written keys this scan cannot bound. *aliases* is the relation the
    scan resolved write targets through, kept for `follows_only_through_bindings`. *followable*
    says whether the scan follows every write the program makes on a built-in object: none reaches
    one through a value read without spelling its owner (`_BuiltinReach`), no watched name is
    handed off, nor read as a property and handed off or written through, where the scan records
    the escape by key alone (`_KEY_RECORDED_ROOTS`), and, under the model that suspects code it
    cannot read, no call runs through a key the reflection check leaves uncounted
    (`_constructs_through_an_unread_key`). A fold that reads a built-in's chain or converts an
    object without spelling its owner asks it on top of the questions about *names*.

    The two are produced together because they are read off the same nodes and must not disagree:
    a name recorded in one for a reason the other cannot express is a name one caller refuses and
    the other clears. Where a write cannot be pinned to a key, *keys* records the name unbounded
    rather than omitting it, so `keys` never reports less about a name than `names` does.
    """
    names: frozenset[str]
    keys: dict[str, frozenset[str] | None]
    aliases: _IntrinsicAliases
    followable: bool

    def key_written(self, name: str, key: str) -> bool:
        """
        Whether the program writes the property *key* on a chain rooted at the global *name*:
        `Object.prototype.constructor = C`, `delete Object.getPrototypeOf`, or a descriptor
        installed for that key. A name whose written keys cannot be bounded answers `True` for
        every key, and so does a name outside `KEYED_WRITE_ROOTS`, which the scan records nothing
        about at all. See `refinery.lib.scripts.js.analysis.effects.EffectModel.global_key_written`
        for why the question is asked of a name rather than of a receiver.
        """
        if name not in KEYED_WRITE_ROOTS:
            return True
        keys = self.keys.get(name, frozenset())
        return keys is None or key in keys

    def follows_only_through_bindings(self, value: Node) -> bool:
        """
        Whether a write through what *value* evaluates to is one this scan or the semantic model it
        read records where the value is spelled or a binding holds it, and never through a property
        holding it. The scan follows a value through the bindings that hold it and trusts `Object`,
        `Function`, `Boolean` and `Buffer` when they escape (`ESCAPE_RECORDED_ROOTS`), and the
        semantic model finds a write to a global through a name holding the global object, not
        through a property holding it. Stored in a property, `scope.P = Object.prototype` lets
        `scope.P.p = 1` write `Object.prototype` unrecorded; stored in a binding,
        `var P = Object.prototype` makes `P.p = 1` a recorded write.

        A value may carry what any of its `denoting_leaves` evaluates to, and one of them qualifies
        where the scan's aliases resolve it to a root the scan watches, where it may be the global
        object, or where the model was not built over it and so cannot say. The foot of a member
        chain is no value the chain evaluates to: it qualifies through the root it names, as
        `Object` does for `Object.prototype`, and never as the global object, since what
        `window.document` evaluates to is a property of that object.
        """
        model = self.aliases.model
        for leaf in denoting_leaves(value):
            if not model.knows(leaf):
                return True
            if isinstance(leaf, JsIdentifier) and self.aliases.names_denoted_by(leaf) & ESCAPE_WATCHED_ROOTS:
                return True
            if not _is_member_object(leaf) and model.may_be_the_global_object(leaf):
                return True
        return False

    def records_a_read(self, node: Node, names: frozenset[str]) -> bool:
        """
        Whether the scan records the watched *names* read at *node*: what *node* evaluates to is
        written through or escapes (`_records_a_watched_read`), the test the scan applies to a
        property read naming one of them.
        """
        return _records_a_watched_read(self.aliases.model, self.aliases, node, names)

    def denotes_a_watched_root(self, binding: Binding) -> bool:
        """
        Whether a value *binding* may hold denotes a root the scan watches, so that a write through
        a name resolving to the binding is one the scan attributes to that root.
        """
        return bool(self.aliases.names_of(binding) & ESCAPE_WATCHED_ROOTS)

    def roots_unwritten(self, owner: str, roots: frozenset[str]) -> bool:
        """
        Whether the program writes neither *owner* nor any prototype in *roots*. A property read
        resolves against the whole prototype chain rather than one prototype, so each name the chain
        passes through has to answer the same question
        `refinery.lib.scripts.js.analysis.effects.EffectModel.trusted_prototype` asks of the owner
        alone.
        """
        return all(name not in self.names for name in (owner, *roots))

    def chain_roots_unwritten(self, value_type: type) -> bool:
        """
        Whether the program writes no prototype a plain property read on a value of *value_type*
        consults, so such a read can run no accessor the program installed there. See
        `refinery.lib.scripts.js.analysis.effects.EffectModel.chain_roots_unwritten` for what the
        answer leaves out and who may ask it.
        """
        owner = PROTOTYPE_OWNERS.get(value_type.__name__)
        if owner is None:
            return False
        return self.roots_unwritten(owner, INHERITED_CHAIN_ROOTS)

    def records_more_than(self, other: IntrinsicWrites) -> bool:
        """
        Whether this scan records a written name, a key written on a name, or a name whose written
        keys it cannot bound, that the scan *other* does not record.
        """
        if self.names - other.names:
            return True
        for name, keys in self.keys.items():
            known = other.keys.get(name, frozenset())
            if known is None:
                continue
            if keys is None or keys - known:
                return True
        return False

Ancestors

• builtins.tuple

Instance variables

var names

Alias for field number 0

Expand source code Browse git

class IntrinsicWrites(NamedTuple):
    """
    What one scan of a program says about the globals it writes: *names*, the set a caller asks
    about a whole name with, and *keys*, the properties each of the watched names was written at —
    or `None` for a name whose written keys this scan cannot bound. *aliases* is the relation the
    scan resolved write targets through, kept for `follows_only_through_bindings`. *followable*
    says whether the scan follows every write the program makes on a built-in object: none reaches
    one through a value read without spelling its owner (`_BuiltinReach`), no watched name is
    handed off, nor read as a property and handed off or written through, where the scan records
    the escape by key alone (`_KEY_RECORDED_ROOTS`), and, under the model that suspects code it
    cannot read, no call runs through a key the reflection check leaves uncounted
    (`_constructs_through_an_unread_key`). A fold that reads a built-in's chain or converts an
    object without spelling its owner asks it on top of the questions about *names*.

    The two are produced together because they are read off the same nodes and must not disagree:
    a name recorded in one for a reason the other cannot express is a name one caller refuses and
    the other clears. Where a write cannot be pinned to a key, *keys* records the name unbounded
    rather than omitting it, so `keys` never reports less about a name than `names` does.
    """
    names: frozenset[str]
    keys: dict[str, frozenset[str] | None]
    aliases: _IntrinsicAliases
    followable: bool

    def key_written(self, name: str, key: str) -> bool:
        """
        Whether the program writes the property *key* on a chain rooted at the global *name*:
        `Object.prototype.constructor = C`, `delete Object.getPrototypeOf`, or a descriptor
        installed for that key. A name whose written keys cannot be bounded answers `True` for
        every key, and so does a name outside `KEYED_WRITE_ROOTS`, which the scan records nothing
        about at all. See `refinery.lib.scripts.js.analysis.effects.EffectModel.global_key_written`
        for why the question is asked of a name rather than of a receiver.
        """
        if name not in KEYED_WRITE_ROOTS:
            return True
        keys = self.keys.get(name, frozenset())
        return keys is None or key in keys

    def follows_only_through_bindings(self, value: Node) -> bool:
        """
        Whether a write through what *value* evaluates to is one this scan or the semantic model it
        read records where the value is spelled or a binding holds it, and never through a property
        holding it. The scan follows a value through the bindings that hold it and trusts `Object`,
        `Function`, `Boolean` and `Buffer` when they escape (`ESCAPE_RECORDED_ROOTS`), and the
        semantic model finds a write to a global through a name holding the global object, not
        through a property holding it. Stored in a property, `scope.P = Object.prototype` lets
        `scope.P.p = 1` write `Object.prototype` unrecorded; stored in a binding,
        `var P = Object.prototype` makes `P.p = 1` a recorded write.

        A value may carry what any of its `denoting_leaves` evaluates to, and one of them qualifies
        where the scan's aliases resolve it to a root the scan watches, where it may be the global
        object, or where the model was not built over it and so cannot say. The foot of a member
        chain is no value the chain evaluates to: it qualifies through the root it names, as
        `Object` does for `Object.prototype`, and never as the global object, since what
        `window.document` evaluates to is a property of that object.
        """
        model = self.aliases.model
        for leaf in denoting_leaves(value):
            if not model.knows(leaf):
                return True
            if isinstance(leaf, JsIdentifier) and self.aliases.names_denoted_by(leaf) & ESCAPE_WATCHED_ROOTS:
                return True
            if not _is_member_object(leaf) and model.may_be_the_global_object(leaf):
                return True
        return False

    def records_a_read(self, node: Node, names: frozenset[str]) -> bool:
        """
        Whether the scan records the watched *names* read at *node*: what *node* evaluates to is
        written through or escapes (`_records_a_watched_read`), the test the scan applies to a
        property read naming one of them.
        """
        return _records_a_watched_read(self.aliases.model, self.aliases, node, names)

    def denotes_a_watched_root(self, binding: Binding) -> bool:
        """
        Whether a value *binding* may hold denotes a root the scan watches, so that a write through
        a name resolving to the binding is one the scan attributes to that root.
        """
        return bool(self.aliases.names_of(binding) & ESCAPE_WATCHED_ROOTS)

    def roots_unwritten(self, owner: str, roots: frozenset[str]) -> bool:
        """
        Whether the program writes neither *owner* nor any prototype in *roots*. A property read
        resolves against the whole prototype chain rather than one prototype, so each name the chain
        passes through has to answer the same question
        `refinery.lib.scripts.js.analysis.effects.EffectModel.trusted_prototype` asks of the owner
        alone.
        """
        return all(name not in self.names for name in (owner, *roots))

    def chain_roots_unwritten(self, value_type: type) -> bool:
        """
        Whether the program writes no prototype a plain property read on a value of *value_type*
        consults, so such a read can run no accessor the program installed there. See
        `refinery.lib.scripts.js.analysis.effects.EffectModel.chain_roots_unwritten` for what the
        answer leaves out and who may ask it.
        """
        owner = PROTOTYPE_OWNERS.get(value_type.__name__)
        if owner is None:
            return False
        return self.roots_unwritten(owner, INHERITED_CHAIN_ROOTS)

    def records_more_than(self, other: IntrinsicWrites) -> bool:
        """
        Whether this scan records a written name, a key written on a name, or a name whose written
        keys it cannot bound, that the scan *other* does not record.
        """
        if self.names - other.names:
            return True
        for name, keys in self.keys.items():
            known = other.keys.get(name, frozenset())
            if known is None:
                continue
            if keys is None or keys - known:
                return True
        return False

var keys

Alias for field number 1

Expand source code Browse git

class IntrinsicWrites(NamedTuple):
    """
    What one scan of a program says about the globals it writes: *names*, the set a caller asks
    about a whole name with, and *keys*, the properties each of the watched names was written at —
    or `None` for a name whose written keys this scan cannot bound. *aliases* is the relation the
    scan resolved write targets through, kept for `follows_only_through_bindings`. *followable*
    says whether the scan follows every write the program makes on a built-in object: none reaches
    one through a value read without spelling its owner (`_BuiltinReach`), no watched name is
    handed off, nor read as a property and handed off or written through, where the scan records
    the escape by key alone (`_KEY_RECORDED_ROOTS`), and, under the model that suspects code it
    cannot read, no call runs through a key the reflection check leaves uncounted
    (`_constructs_through_an_unread_key`). A fold that reads a built-in's chain or converts an
    object without spelling its owner asks it on top of the questions about *names*.

    The two are produced together because they are read off the same nodes and must not disagree:
    a name recorded in one for a reason the other cannot express is a name one caller refuses and
    the other clears. Where a write cannot be pinned to a key, *keys* records the name unbounded
    rather than omitting it, so `keys` never reports less about a name than `names` does.
    """
    names: frozenset[str]
    keys: dict[str, frozenset[str] | None]
    aliases: _IntrinsicAliases
    followable: bool

    def key_written(self, name: str, key: str) -> bool:
        """
        Whether the program writes the property *key* on a chain rooted at the global *name*:
        `Object.prototype.constructor = C`, `delete Object.getPrototypeOf`, or a descriptor
        installed for that key. A name whose written keys cannot be bounded answers `True` for
        every key, and so does a name outside `KEYED_WRITE_ROOTS`, which the scan records nothing
        about at all. See `refinery.lib.scripts.js.analysis.effects.EffectModel.global_key_written`
        for why the question is asked of a name rather than of a receiver.
        """
        if name not in KEYED_WRITE_ROOTS:
            return True
        keys = self.keys.get(name, frozenset())
        return keys is None or key in keys

    def follows_only_through_bindings(self, value: Node) -> bool:
        """
        Whether a write through what *value* evaluates to is one this scan or the semantic model it
        read records where the value is spelled or a binding holds it, and never through a property
        holding it. The scan follows a value through the bindings that hold it and trusts `Object`,
        `Function`, `Boolean` and `Buffer` when they escape (`ESCAPE_RECORDED_ROOTS`), and the
        semantic model finds a write to a global through a name holding the global object, not
        through a property holding it. Stored in a property, `scope.P = Object.prototype` lets
        `scope.P.p = 1` write `Object.prototype` unrecorded; stored in a binding,
        `var P = Object.prototype` makes `P.p = 1` a recorded write.

        A value may carry what any of its `denoting_leaves` evaluates to, and one of them qualifies
        where the scan's aliases resolve it to a root the scan watches, where it may be the global
        object, or where the model was not built over it and so cannot say. The foot of a member
        chain is no value the chain evaluates to: it qualifies through the root it names, as
        `Object` does for `Object.prototype`, and never as the global object, since what
        `window.document` evaluates to is a property of that object.
        """
        model = self.aliases.model
        for leaf in denoting_leaves(value):
            if not model.knows(leaf):
                return True
            if isinstance(leaf, JsIdentifier) and self.aliases.names_denoted_by(leaf) & ESCAPE_WATCHED_ROOTS:
                return True
            if not _is_member_object(leaf) and model.may_be_the_global_object(leaf):
                return True
        return False

    def records_a_read(self, node: Node, names: frozenset[str]) -> bool:
        """
        Whether the scan records the watched *names* read at *node*: what *node* evaluates to is
        written through or escapes (`_records_a_watched_read`), the test the scan applies to a
        property read naming one of them.
        """
        return _records_a_watched_read(self.aliases.model, self.aliases, node, names)

    def denotes_a_watched_root(self, binding: Binding) -> bool:
        """
        Whether a value *binding* may hold denotes a root the scan watches, so that a write through
        a name resolving to the binding is one the scan attributes to that root.
        """
        return bool(self.aliases.names_of(binding) & ESCAPE_WATCHED_ROOTS)

    def roots_unwritten(self, owner: str, roots: frozenset[str]) -> bool:
        """
        Whether the program writes neither *owner* nor any prototype in *roots*. A property read
        resolves against the whole prototype chain rather than one prototype, so each name the chain
        passes through has to answer the same question
        `refinery.lib.scripts.js.analysis.effects.EffectModel.trusted_prototype` asks of the owner
        alone.
        """
        return all(name not in self.names for name in (owner, *roots))

    def chain_roots_unwritten(self, value_type: type) -> bool:
        """
        Whether the program writes no prototype a plain property read on a value of *value_type*
        consults, so such a read can run no accessor the program installed there. See
        `refinery.lib.scripts.js.analysis.effects.EffectModel.chain_roots_unwritten` for what the
        answer leaves out and who may ask it.
        """
        owner = PROTOTYPE_OWNERS.get(value_type.__name__)
        if owner is None:
            return False
        return self.roots_unwritten(owner, INHERITED_CHAIN_ROOTS)

    def records_more_than(self, other: IntrinsicWrites) -> bool:
        """
        Whether this scan records a written name, a key written on a name, or a name whose written
        keys it cannot bound, that the scan *other* does not record.
        """
        if self.names - other.names:
            return True
        for name, keys in self.keys.items():
            known = other.keys.get(name, frozenset())
            if known is None:
                continue
            if keys is None or keys - known:
                return True
        return False

var aliases

Alias for field number 2

Expand source code Browse git

class IntrinsicWrites(NamedTuple):
    """
    What one scan of a program says about the globals it writes: *names*, the set a caller asks
    about a whole name with, and *keys*, the properties each of the watched names was written at —
    or `None` for a name whose written keys this scan cannot bound. *aliases* is the relation the
    scan resolved write targets through, kept for `follows_only_through_bindings`. *followable*
    says whether the scan follows every write the program makes on a built-in object: none reaches
    one through a value read without spelling its owner (`_BuiltinReach`), no watched name is
    handed off, nor read as a property and handed off or written through, where the scan records
    the escape by key alone (`_KEY_RECORDED_ROOTS`), and, under the model that suspects code it
    cannot read, no call runs through a key the reflection check leaves uncounted
    (`_constructs_through_an_unread_key`). A fold that reads a built-in's chain or converts an
    object without spelling its owner asks it on top of the questions about *names*.

    The two are produced together because they are read off the same nodes and must not disagree:
    a name recorded in one for a reason the other cannot express is a name one caller refuses and
    the other clears. Where a write cannot be pinned to a key, *keys* records the name unbounded
    rather than omitting it, so `keys` never reports less about a name than `names` does.
    """
    names: frozenset[str]
    keys: dict[str, frozenset[str] | None]
    aliases: _IntrinsicAliases
    followable: bool

    def key_written(self, name: str, key: str) -> bool:
        """
        Whether the program writes the property *key* on a chain rooted at the global *name*:
        `Object.prototype.constructor = C`, `delete Object.getPrototypeOf`, or a descriptor
        installed for that key. A name whose written keys cannot be bounded answers `True` for
        every key, and so does a name outside `KEYED_WRITE_ROOTS`, which the scan records nothing
        about at all. See `refinery.lib.scripts.js.analysis.effects.EffectModel.global_key_written`
        for why the question is asked of a name rather than of a receiver.
        """
        if name not in KEYED_WRITE_ROOTS:
            return True
        keys = self.keys.get(name, frozenset())
        return keys is None or key in keys

    def follows_only_through_bindings(self, value: Node) -> bool:
        """
        Whether a write through what *value* evaluates to is one this scan or the semantic model it
        read records where the value is spelled or a binding holds it, and never through a property
        holding it. The scan follows a value through the bindings that hold it and trusts `Object`,
        `Function`, `Boolean` and `Buffer` when they escape (`ESCAPE_RECORDED_ROOTS`), and the
        semantic model finds a write to a global through a name holding the global object, not
        through a property holding it. Stored in a property, `scope.P = Object.prototype` lets
        `scope.P.p = 1` write `Object.prototype` unrecorded; stored in a binding,
        `var P = Object.prototype` makes `P.p = 1` a recorded write.

        A value may carry what any of its `denoting_leaves` evaluates to, and one of them qualifies
        where the scan's aliases resolve it to a root the scan watches, where it may be the global
        object, or where the model was not built over it and so cannot say. The foot of a member
        chain is no value the chain evaluates to: it qualifies through the root it names, as
        `Object` does for `Object.prototype`, and never as the global object, since what
        `window.document` evaluates to is a property of that object.
        """
        model = self.aliases.model
        for leaf in denoting_leaves(value):
            if not model.knows(leaf):
                return True
            if isinstance(leaf, JsIdentifier) and self.aliases.names_denoted_by(leaf) & ESCAPE_WATCHED_ROOTS:
                return True
            if not _is_member_object(leaf) and model.may_be_the_global_object(leaf):
                return True
        return False

    def records_a_read(self, node: Node, names: frozenset[str]) -> bool:
        """
        Whether the scan records the watched *names* read at *node*: what *node* evaluates to is
        written through or escapes (`_records_a_watched_read`), the test the scan applies to a
        property read naming one of them.
        """
        return _records_a_watched_read(self.aliases.model, self.aliases, node, names)

    def denotes_a_watched_root(self, binding: Binding) -> bool:
        """
        Whether a value *binding* may hold denotes a root the scan watches, so that a write through
        a name resolving to the binding is one the scan attributes to that root.
        """
        return bool(self.aliases.names_of(binding) & ESCAPE_WATCHED_ROOTS)

    def roots_unwritten(self, owner: str, roots: frozenset[str]) -> bool:
        """
        Whether the program writes neither *owner* nor any prototype in *roots*. A property read
        resolves against the whole prototype chain rather than one prototype, so each name the chain
        passes through has to answer the same question
        `refinery.lib.scripts.js.analysis.effects.EffectModel.trusted_prototype` asks of the owner
        alone.
        """
        return all(name not in self.names for name in (owner, *roots))

    def chain_roots_unwritten(self, value_type: type) -> bool:
        """
        Whether the program writes no prototype a plain property read on a value of *value_type*
        consults, so such a read can run no accessor the program installed there. See
        `refinery.lib.scripts.js.analysis.effects.EffectModel.chain_roots_unwritten` for what the
        answer leaves out and who may ask it.
        """
        owner = PROTOTYPE_OWNERS.get(value_type.__name__)
        if owner is None:
            return False
        return self.roots_unwritten(owner, INHERITED_CHAIN_ROOTS)

    def records_more_than(self, other: IntrinsicWrites) -> bool:
        """
        Whether this scan records a written name, a key written on a name, or a name whose written
        keys it cannot bound, that the scan *other* does not record.
        """
        if self.names - other.names:
            return True
        for name, keys in self.keys.items():
            known = other.keys.get(name, frozenset())
            if known is None:
                continue
            if keys is None or keys - known:
                return True
        return False

var followable

Alias for field number 3

Expand source code Browse git

class IntrinsicWrites(NamedTuple):
    """
    What one scan of a program says about the globals it writes: *names*, the set a caller asks
    about a whole name with, and *keys*, the properties each of the watched names was written at —
    or `None` for a name whose written keys this scan cannot bound. *aliases* is the relation the
    scan resolved write targets through, kept for `follows_only_through_bindings`. *followable*
    says whether the scan follows every write the program makes on a built-in object: none reaches
    one through a value read without spelling its owner (`_BuiltinReach`), no watched name is
    handed off, nor read as a property and handed off or written through, where the scan records
    the escape by key alone (`_KEY_RECORDED_ROOTS`), and, under the model that suspects code it
    cannot read, no call runs through a key the reflection check leaves uncounted
    (`_constructs_through_an_unread_key`). A fold that reads a built-in's chain or converts an
    object without spelling its owner asks it on top of the questions about *names*.

    The two are produced together because they are read off the same nodes and must not disagree:
    a name recorded in one for a reason the other cannot express is a name one caller refuses and
    the other clears. Where a write cannot be pinned to a key, *keys* records the name unbounded
    rather than omitting it, so `keys` never reports less about a name than `names` does.
    """
    names: frozenset[str]
    keys: dict[str, frozenset[str] | None]
    aliases: _IntrinsicAliases
    followable: bool

    def key_written(self, name: str, key: str) -> bool:
        """
        Whether the program writes the property *key* on a chain rooted at the global *name*:
        `Object.prototype.constructor = C`, `delete Object.getPrototypeOf`, or a descriptor
        installed for that key. A name whose written keys cannot be bounded answers `True` for
        every key, and so does a name outside `KEYED_WRITE_ROOTS`, which the scan records nothing
        about at all. See `refinery.lib.scripts.js.analysis.effects.EffectModel.global_key_written`
        for why the question is asked of a name rather than of a receiver.
        """
        if name not in KEYED_WRITE_ROOTS:
            return True
        keys = self.keys.get(name, frozenset())
        return keys is None or key in keys

    def follows_only_through_bindings(self, value: Node) -> bool:
        """
        Whether a write through what *value* evaluates to is one this scan or the semantic model it
        read records where the value is spelled or a binding holds it, and never through a property
        holding it. The scan follows a value through the bindings that hold it and trusts `Object`,
        `Function`, `Boolean` and `Buffer` when they escape (`ESCAPE_RECORDED_ROOTS`), and the
        semantic model finds a write to a global through a name holding the global object, not
        through a property holding it. Stored in a property, `scope.P = Object.prototype` lets
        `scope.P.p = 1` write `Object.prototype` unrecorded; stored in a binding,
        `var P = Object.prototype` makes `P.p = 1` a recorded write.

        A value may carry what any of its `denoting_leaves` evaluates to, and one of them qualifies
        where the scan's aliases resolve it to a root the scan watches, where it may be the global
        object, or where the model was not built over it and so cannot say. The foot of a member
        chain is no value the chain evaluates to: it qualifies through the root it names, as
        `Object` does for `Object.prototype`, and never as the global object, since what
        `window.document` evaluates to is a property of that object.
        """
        model = self.aliases.model
        for leaf in denoting_leaves(value):
            if not model.knows(leaf):
                return True
            if isinstance(leaf, JsIdentifier) and self.aliases.names_denoted_by(leaf) & ESCAPE_WATCHED_ROOTS:
                return True
            if not _is_member_object(leaf) and model.may_be_the_global_object(leaf):
                return True
        return False

    def records_a_read(self, node: Node, names: frozenset[str]) -> bool:
        """
        Whether the scan records the watched *names* read at *node*: what *node* evaluates to is
        written through or escapes (`_records_a_watched_read`), the test the scan applies to a
        property read naming one of them.
        """
        return _records_a_watched_read(self.aliases.model, self.aliases, node, names)

    def denotes_a_watched_root(self, binding: Binding) -> bool:
        """
        Whether a value *binding* may hold denotes a root the scan watches, so that a write through
        a name resolving to the binding is one the scan attributes to that root.
        """
        return bool(self.aliases.names_of(binding) & ESCAPE_WATCHED_ROOTS)

    def roots_unwritten(self, owner: str, roots: frozenset[str]) -> bool:
        """
        Whether the program writes neither *owner* nor any prototype in *roots*. A property read
        resolves against the whole prototype chain rather than one prototype, so each name the chain
        passes through has to answer the same question
        `refinery.lib.scripts.js.analysis.effects.EffectModel.trusted_prototype` asks of the owner
        alone.
        """
        return all(name not in self.names for name in (owner, *roots))

    def chain_roots_unwritten(self, value_type: type) -> bool:
        """
        Whether the program writes no prototype a plain property read on a value of *value_type*
        consults, so such a read can run no accessor the program installed there. See
        `refinery.lib.scripts.js.analysis.effects.EffectModel.chain_roots_unwritten` for what the
        answer leaves out and who may ask it.
        """
        owner = PROTOTYPE_OWNERS.get(value_type.__name__)
        if owner is None:
            return False
        return self.roots_unwritten(owner, INHERITED_CHAIN_ROOTS)

    def records_more_than(self, other: IntrinsicWrites) -> bool:
        """
        Whether this scan records a written name, a key written on a name, or a name whose written
        keys it cannot bound, that the scan *other* does not record.
        """
        if self.names - other.names:
            return True
        for name, keys in self.keys.items():
            known = other.keys.get(name, frozenset())
            if known is None:
                continue
            if keys is None or keys - known:
                return True
        return False

Methods

def key_written(self, name, key)

Whether the program writes the property key on a chain rooted at the global name: Object.prototype.constructor = C, delete Object.getPrototypeOf, or a descriptor installed for that key. A name whose written keys cannot be bounded answers True for every key, and so does a name outside KEYED_WRITE_ROOTS, which the scan records nothing about at all. See EffectModel.global_key_written() for why the question is asked of a name rather than of a receiver.

Expand source code Browse git

def key_written(self, name: str, key: str) -> bool:
    """
    Whether the program writes the property *key* on a chain rooted at the global *name*:
    `Object.prototype.constructor = C`, `delete Object.getPrototypeOf`, or a descriptor
    installed for that key. A name whose written keys cannot be bounded answers `True` for
    every key, and so does a name outside `KEYED_WRITE_ROOTS`, which the scan records nothing
    about at all. See `refinery.lib.scripts.js.analysis.effects.EffectModel.global_key_written`
    for why the question is asked of a name rather than of a receiver.
    """
    if name not in KEYED_WRITE_ROOTS:
        return True
    keys = self.keys.get(name, frozenset())
    return keys is None or key in keys

def follows_only_through_bindings(self, value)

Whether a write through what value evaluates to is one this scan or the semantic model it read records where the value is spelled or a binding holds it, and never through a property holding it. The scan follows a value through the bindings that hold it and trusts Object, Function, Boolean and Buffer when they escape (ESCAPE_RECORDED_ROOTS), and the semantic model finds a write to a global through a name holding the global object, not through a property holding it. Stored in a property, scope.P = Object.prototype lets scope.P.p = 1 write Object.prototype unrecorded; stored in a binding, var P = Object.prototype makes P.p = 1 a recorded write.

A value may carry what any of its denoting_leaves() evaluates to, and one of them qualifies where the scan's aliases resolve it to a root the scan watches, where it may be the global object, or where the model was not built over it and so cannot say. The foot of a member chain is no value the chain evaluates to: it qualifies through the root it names, as Object does for Object.prototype, and never as the global object, since what window.document evaluates to is a property of that object.

Expand source code Browse git

def follows_only_through_bindings(self, value: Node) -> bool:
    """
    Whether a write through what *value* evaluates to is one this scan or the semantic model it
    read records where the value is spelled or a binding holds it, and never through a property
    holding it. The scan follows a value through the bindings that hold it and trusts `Object`,
    `Function`, `Boolean` and `Buffer` when they escape (`ESCAPE_RECORDED_ROOTS`), and the
    semantic model finds a write to a global through a name holding the global object, not
    through a property holding it. Stored in a property, `scope.P = Object.prototype` lets
    `scope.P.p = 1` write `Object.prototype` unrecorded; stored in a binding,
    `var P = Object.prototype` makes `P.p = 1` a recorded write.

    A value may carry what any of its `denoting_leaves` evaluates to, and one of them qualifies
    where the scan's aliases resolve it to a root the scan watches, where it may be the global
    object, or where the model was not built over it and so cannot say. The foot of a member
    chain is no value the chain evaluates to: it qualifies through the root it names, as
    `Object` does for `Object.prototype`, and never as the global object, since what
    `window.document` evaluates to is a property of that object.
    """
    model = self.aliases.model
    for leaf in denoting_leaves(value):
        if not model.knows(leaf):
            return True
        if isinstance(leaf, JsIdentifier) and self.aliases.names_denoted_by(leaf) & ESCAPE_WATCHED_ROOTS:
            return True
        if not _is_member_object(leaf) and model.may_be_the_global_object(leaf):
            return True
    return False

def records_a_read(self, node, names)

Whether the scan records the watched names read at node: what node evaluates to is written through or escapes (_records_a_watched_read), the test the scan applies to a property read naming one of them.

Expand source code Browse git

def records_a_read(self, node: Node, names: frozenset[str]) -> bool:
    """
    Whether the scan records the watched *names* read at *node*: what *node* evaluates to is
    written through or escapes (`_records_a_watched_read`), the test the scan applies to a
    property read naming one of them.
    """
    return _records_a_watched_read(self.aliases.model, self.aliases, node, names)

def denotes_a_watched_root(self, binding)

Whether a value binding may hold denotes a root the scan watches, so that a write through a name resolving to the binding is one the scan attributes to that root.

Expand source code Browse git

def denotes_a_watched_root(self, binding: Binding) -> bool:
    """
    Whether a value *binding* may hold denotes a root the scan watches, so that a write through
    a name resolving to the binding is one the scan attributes to that root.
    """
    return bool(self.aliases.names_of(binding) & ESCAPE_WATCHED_ROOTS)

def roots_unwritten(self, owner, roots)

Whether the program writes neither owner nor any prototype in roots. A property read resolves against the whole prototype chain rather than one prototype, so each name the chain passes through has to answer the same question EffectModel.trusted_prototype() asks of the owner alone.

Expand source code Browse git

def roots_unwritten(self, owner: str, roots: frozenset[str]) -> bool:
    """
    Whether the program writes neither *owner* nor any prototype in *roots*. A property read
    resolves against the whole prototype chain rather than one prototype, so each name the chain
    passes through has to answer the same question
    `refinery.lib.scripts.js.analysis.effects.EffectModel.trusted_prototype` asks of the owner
    alone.
    """
    return all(name not in self.names for name in (owner, *roots))

def chain_roots_unwritten(self, value_type)

Whether the program writes no prototype a plain property read on a value of value_type consults, so such a read can run no accessor the program installed there. See EffectModel.chain_roots_unwritten() for what the answer leaves out and who may ask it.

Expand source code Browse git

def chain_roots_unwritten(self, value_type: type) -> bool:
    """
    Whether the program writes no prototype a plain property read on a value of *value_type*
    consults, so such a read can run no accessor the program installed there. See
    `refinery.lib.scripts.js.analysis.effects.EffectModel.chain_roots_unwritten` for what the
    answer leaves out and who may ask it.
    """
    owner = PROTOTYPE_OWNERS.get(value_type.__name__)
    if owner is None:
        return False
    return self.roots_unwritten(owner, INHERITED_CHAIN_ROOTS)

def records_more_than(self, other)

Whether this scan records a written name, a key written on a name, or a name whose written keys it cannot bound, that the scan other does not record.

Expand source code Browse git

def records_more_than(self, other: IntrinsicWrites) -> bool:
    """
    Whether this scan records a written name, a key written on a name, or a name whose written
    keys it cannot bound, that the scan *other* does not record.
    """
    if self.names - other.names:
        return True
    for name, keys in self.keys.items():
        known = other.keys.get(name, frozenset())
        if known is None:
            continue
        if keys is None or keys - known:
            return True
    return False

class SpeculationState (*args, **kwds)

Where a WriteSpeculation stands.

Expand source code Browse git

class SpeculationState(enum.Enum):
    """
    Where a `WriteSpeculation` stands.
    """
    ASSUMING = 'assuming'
    DISCHARGED = 'discharged'
    REFUTED = 'refuted'

Ancestors

• enum.Enum

Class variables

var ASSUMING

The type of the None singleton.

var DISCHARGED

The type of the None singleton.

var REFUTED

The type of the None singleton.

class SpeculationRefuted (*args, **kwargs)

Raised by WriteSpeculation.observe() at a build of the scan that records more than the build before it, and at every build after that one.

Expand source code Browse git

class SpeculationRefuted(Exception):
    """
    Raised by `WriteSpeculation.observe` at a build of the scan that records more than the build
    before it, and at every build after that one.
    """

Ancestors

• builtins.Exception
• builtins.BaseException

class WriteSpeculation

The record of a run that assumes every write on a built-in object the scan does not follow (IntrinsicWrites.followable) writes nothing. While it assumes, observe presents each build of the scan as following every write and compares it with the build before it: one that records more (IntrinsicWrites.records_more_than()) refutes the assumption. A build that follows every write and records no more discharges it, and every later build is presented as it is.

A run that ends discharged may keep its result. Each fold it made before the discharge read the record of some build and assumed nothing outside that record is written. No build records more than the one before, so the record of the discharging build, R, is part of every earlier one. Take an execution and the first write outside the record a fold relied on, if one happens: up to that moment every fold's premise held, so the discharged tree behaves alike up to it and makes the same write. That tree has no write the scan does not follow, so the write is in R, and so in every earlier record: no fold relied on its absence. So no such write happens. Code a splice brings in after the discharge is read by the scan as it is, as in any run.

Expand source code Browse git

class WriteSpeculation:
    """
    The record of a run that assumes every write on a built-in object the scan does not follow
    (`IntrinsicWrites.followable`) writes nothing. While it assumes, `observe` presents each build
    of the scan as following every write and compares it with the build before it: one that
    records more (`IntrinsicWrites.records_more_than`) refutes the assumption. A build that follows
    every write and records no more discharges it, and every later build is presented as it is.

    A run that ends discharged may keep its result. Each fold it made before the discharge read the
    record of some build and assumed nothing outside that record is written. No build records more
    than the one before, so the record of the discharging build, R, is part of every earlier one.
    Take an execution and the first write outside the record a fold relied on, if one happens: up to
    that moment every fold's premise held, so the discharged tree behaves alike up to it and makes
    the same write. That tree has no write the scan does not follow, so the write is in R, and so in
    every earlier record: no fold relied on its absence. So no such write happens. Code a splice
    brings in after the discharge is read by the scan as it is, as in any run.
    """

    def __init__(self):
        self.state = SpeculationState.ASSUMING
        self._record: IntrinsicWrites | None = None

    @property
    def assuming(self) -> bool:
        return self.state is SpeculationState.ASSUMING

    @property
    def discharged(self) -> bool:
        return self.state is SpeculationState.DISCHARGED

    def observe(self, writes: IntrinsicWrites) -> IntrinsicWrites:
        """
        The build *writes* of the scan as the run reads it: presented as following every write
        while the assumption holds, and as it is once the assumption is discharged. Raises
        `SpeculationRefuted` where *writes* records more than the build before it, and at every
        build once that has happened.
        """
        if self.state is SpeculationState.DISCHARGED:
            return writes
        if self.state is SpeculationState.REFUTED or (
            self._record is not None and writes.records_more_than(self._record)
        ):
            self.state = SpeculationState.REFUTED
            raise SpeculationRefuted
        self._record = writes
        if writes.followable:
            self.state = SpeculationState.DISCHARGED
            return writes
        return writes._replace(followable=True)

Instance variables

var assuming

Expand source code Browse git

@property
def assuming(self) -> bool:
    return self.state is SpeculationState.ASSUMING

var discharged

Expand source code Browse git

@property
def discharged(self) -> bool:
    return self.state is SpeculationState.DISCHARGED

Methods

def observe(self, writes)

The build writes of the scan as the run reads it: presented as following every write while the assumption holds, and as it is once the assumption is discharged. Raises SpeculationRefuted where writes records more than the build before it, and at every build once that has happened.

Expand source code Browse git

def observe(self, writes: IntrinsicWrites) -> IntrinsicWrites:
    """
    The build *writes* of the scan as the run reads it: presented as following every write
    while the assumption holds, and as it is once the assumption is discharged. Raises
    `SpeculationRefuted` where *writes* records more than the build before it, and at every
    build once that has happened.
    """
    if self.state is SpeculationState.DISCHARGED:
        return writes
    if self.state is SpeculationState.REFUTED or (
        self._record is not None and writes.records_more_than(self._record)
    ):
        self.state = SpeculationState.REFUTED
        raise SpeculationRefuted
    self._record = writes
    if writes.followable:
        self.state = SpeculationState.DISCHARGED
        return writes
    return writes._replace(followable=True)

class UnfollowedWriteRefusals

The record one deobfuscation run keeps of whether a question was answered no because the scan does not follow every write on a built-in object (IntrinsicWrites.followable), on any tree of the run. Only such an answer can refuse a fold, so a run whose last tree is not followed runs again under a WriteSpeculation only where one was given.

Expand source code Browse git

class UnfollowedWriteRefusals:
    """
    The record one deobfuscation run keeps of whether a question was answered no because the scan
    does not follow every write on a built-in object (`IntrinsicWrites.followable`), on any tree of
    the run. Only such an answer can refuse a fold, so a run whose last tree is not followed runs
    again under a `WriteSpeculation` only where one was given.
    """

    def __init__(self):
        self.refused = False

    def note(self) -> None:
        """
        Record that a question was answered no because the scan does not follow every write.
        """
        self.refused = True

Methods

def note(self)

Record that a question was answered no because the scan does not follow every write.

Expand source code Browse git

def note(self) -> None:
    """
    Record that a question was answered no because the scan does not follow every write.
    """
    self.refused = True