Module refinery.lib.scripts.ps1.analysis.callgraph

The call graph of one PowerShell script: which function definitions a command name denotes, which invocations reach that name, and whether the two together are the whole story.

Two questions are asked of it, and they fail in opposite directions, which is why one walk answers both. Reachability decides whether a definition may be deleted, so a call site the walk misses deletes live code. Output flow — Ps1OutputFlow — decides whether a bare value inside a body may be deleted, so a call site the walk misses deletes a payload. A walk that expanded only bodies already proven reachable would be sound for the first question and a deletion licence for the second, so the walk here expands every body a name can denote.

The graph is structure and nothing more. It says who can call what; what a call does with the value it produces is the effect layer's question, asked through here rather than answered here.

"""
The call graph of one PowerShell script: which function definitions a command name denotes, which
invocations reach that name, and whether the two together are the whole story.

Two questions are asked of it, and they fail in opposite directions, which is why one walk answers
both. *Reachability* decides whether a definition may be deleted, so a call site the walk misses
deletes live code. *Output flow* — `refinery.lib.scripts.ps1.analysis.effects.Ps1OutputFlow` —
decides whether a bare value inside a body may be deleted, so a call site the walk misses deletes a
payload. A walk that expanded only bodies already proven reachable would be sound for the first
question and a deletion licence for the second, so the walk here expands every body a name can
denote.

The graph is structure and nothing more. It says who can call what; what a call *does* with the
value it produces is the effect layer's question, asked through here rather than answered here.
"""
from __future__ import annotations

import re

from typing import TYPE_CHECKING, Callable, Mapping, NamedTuple, Sequence

if TYPE_CHECKING:
    from refinery.lib.scripts.analysis.dominance import DominatorModel

from refinery.lib.scripts import Node
from refinery.lib.scripts.ps1.analysis.world import (
    Ps1TypeWorld,
    command_definition_keyword_binding,
    runs_code_it_cannot_read,
)
from refinery.lib.scripts.ps1.ast import (
    assignment_target_variables,
    bound_argument_value,
    free_positional_values,
    get_command_name,
    get_member_name,
    get_param_block,
    has_wildcard,
    implicit_get_retry,
    is_execution_context_invoke,
    is_opaque_dispatch,
    is_scriptblock_invoke,
    may_create_a_scriptblock,
    member_may_be,
    normalize_command_name,
    resolve_command_name,
    string_value,
)
from refinery.lib.scripts.ps1.data import KNOWN_CMDLETS
from refinery.lib.scripts.ps1.model import (
    Ps1AccessKind,
    Ps1AssignmentExpression,
    Ps1CommandArgument,
    Ps1CommandInvocation,
    Ps1FunctionDefinition,
    Ps1HereString,
    Ps1InvokeMember,
    Ps1MemberAccess,
    Ps1MethodMember,
    Ps1ParenExpression,
    Ps1Pipeline,
    Ps1PipelineElement,
    Ps1ScopeModifier,
    Ps1Script,
    Ps1ScriptBlock,
    Ps1StringLiteral,
    Ps1Variable,
)
from refinery.lib.scripts.ps1.options import eval_is_trusted

#: The variable namespaces that name a command rather than a value. Kept in step with
#: `refinery.lib.scripts.ps1.analysis.world._IDENTITY_SCOPES`, which this module cannot reuse
#: because the world reports one verdict for the whole script and this one needs the single node.
_IDENTITY_SCOPES = frozenset({
    Ps1ScopeModifier.ALIAS,
    Ps1ScopeModifier.FUNCTION,
})

#: Commands that hand a name to code outside this file. A `.psm1` exporting a function has call
#: sites in whatever imported it, and no walk over this tree can see them. Read through
#: `refinery.lib.scripts.ps1.ast.resolve_command_name`, which is the deny-list reading of a name:
#: a hit here withholds every name-keyed removal, so a spelling that dodges the table is the
#: dangerous direction. That closes a module qualifier written after the call operator, quoted or
#: not — `& Microsoft.PowerShell.Core\Export-ModuleMember` arrives as one token either way. Written
#: as a bare command statement the lexer splits the name at the backslash and the table is dodged;
#: see `refinery.lib.scripts.ps1.ast.resolve_command_name` for why that hole is the lexer's.
_EXPORTING_COMMANDS = frozenset({
    'export-modulemember',
})

#: The .NET attribute type names that, on a function's `param` block, bind command aliases for the
#: function — `[Alias('q')]` and its `Attribute`-suffixed and namespace-qualified spellings. Matched
#: after the namespace is stripped, the way .NET resolves an attribute type name.
_COMMAND_ALIAS_ATTRIBUTES = frozenset({
    'alias',
    'aliasattribute',
})


def binds_command_identity(node: Node) -> bool:
    """
    Whether `node` writes the `function:` or `alias:` namespace, binding a command name to something
    the definition scan does not read as a definition and the call scan does not read as a call.
    Every name-keyed decision has to treat such a node as an unknown: it can bind the name about to
    be deleted, and it can be the only thing that reaches it.
    """
    if not isinstance(node, Ps1AssignmentExpression):
        return False
    return any(
        variable.scope in _IDENTITY_SCOPES
        for variable in assignment_target_variables(node.target)
    )


def _is_class_method(definition: Ps1FunctionDefinition) -> bool:
    """
    Whether a function definition is the body of a class method rather than a command. A method is
    reached through `$object.Method()` and never through its bare name, so it is neither a
    definition a call site can name nor a definition this graph can find the callers of.
    """
    return isinstance(definition.parent, Ps1MethodMember)


def _enclosing_function(node: Node) -> str | None:
    """
    The key of the **outermost** function definition whose body holds `node`, or `None` when `node`
    runs as part of the script itself.

    Outermost rather than innermost, because the only reader is `Ps1CallGraph.reachable_names` and a
    nested definition is never called by name. `function Outer { function Inner { Payload } }`
    credits the call to `Outer`: reading it as `Inner`'s leaves `Payload` reached by nothing, so it
    is deleted while `Inner` — which no pass removes, since only a top-level definition is
    removable — stands there calling a name the emitted script no longer defines. Attribution to the
    enclosing scope is what makes the two answers agree.

    A class method anywhere on the way out answers `None` and stops the walk, which is the
    conservative direction. A method body runs whenever something constructs or calls into the
    class, and this graph cannot see that happen; treating its calls as unconditional keeps every
    name they reach reachable, and `Ps1OutputFlow` separately refuses to ground a method body
    because no call site ever names it. Carrying on to the enclosing function instead would make
    those calls conditional on a name that reaches the *class*, which nothing here can prove.
    """
    found: str | None = None
    cursor = node.parent
    while cursor is not None:
        if isinstance(cursor, Ps1FunctionDefinition):
            if _is_class_method(cursor):
                return None
            found = normalize_command_name(cursor.name)
        cursor = cursor.parent
    return found


class Ps1CallSite(NamedTuple):
    """
    One invocation of a command name, paired with the key of the outermost function whose body holds
    it — see `_enclosing_function` — which is the edge's source, where the invocation is its target.
    """
    invocation: Ps1CommandInvocation
    caller: str | None


class Ps1CallGraph:
    """
    The verdict of `build_call_graph`. Definitions and call sites are keyed through
    `refinery.lib.scripts.ps1.ast.normalize_command_name`, so `function global:F` and a bare call to
    `F` meet on one key, and every definition sharing a key is kept: a redefinition shadows the
    earlier body only from the point it runs, which is order and scope information no walk over the
    tree carries.
    """

    def __init__(
        self,
        definitions: Mapping[str, Sequence[Ps1FunctionDefinition]],
        keyword_definitions: Mapping[str, Sequence[Ps1ScriptBlock]],
        call_sites: Mapping[str, Sequence[Ps1CallSite]],
        unattributed_sites: Sequence[Node],
        readable: bool,
        exports: bool,
        handed_out: frozenset[str] = frozenset(),
        hands_out_every: bool = False,
    ):
        self._definitions = dict(definitions)
        self._keyword_definitions = dict(keyword_definitions)
        self._call_sites = dict(call_sites)
        self._unattributed_sites = tuple(unattributed_sites)
        self._readable = readable
        self._exports = exports
        self._handed_out = handed_out
        self._hands_out_every = hands_out_every

    def hands_out(self, name: str) -> bool:
        """
        Whether the script may reach the body of the function *name* other than by calling it by
        name: it reads `$function:K`, writes a path into the `function:` drive, asks `Get-Command`
        for it, looks a command up through `$ExecutionContext` or `$PSCmdlet`, reads
        `$MyInvocation` inside it, or does any of these where the name cannot be read. A body handed
        out this way may run wherever something runs a block, so no list of call sites is the list of
        places it runs.
        """
        return self._hands_out_every or normalize_command_name(name) in self._handed_out

    def named_callers(self, body: Node) -> list[Node] | None:
        """
        The calls naming the function whose body *body* is, or `None` where those are not all the
        calls that may run it beside `unattributed_sites`: *body* is no function's, this graph
        cannot be read, the function is a class method or has no name, or the script hands it out.
        """
        parent = body.parent
        if (
            not self._readable
            or not isinstance(parent, Ps1FunctionDefinition)
            or _is_class_method(parent)
            or not parent.name
            or self.hands_out(parent.name)
        ):
            return None
        return [site.invocation for site in self.call_sites(parent.name)]

    def sites_running(self, block: Ps1ScriptBlock, attributed_only: bool = False) -> list[Node] | None:
        """
        The calls that may run *block*, or `None` where they cannot all be named. A function body is
        run by the calls naming the function (`named_callers`), and, unless *attributed_only*, by
        every call in `unattributed_sites`. A script block is run by the `&` or `.` that invokes it
        where it is written, and by the `ForEach-Object` or `Where-Object` it is handed to.
        """
        parent = block.parent
        if isinstance(parent, Ps1FunctionDefinition):
            named = self.named_callers(block)
            if named is None or attributed_only:
                return named
            return [*named, *self.unattributed_sites]
        invocation = parent.parent if isinstance(parent, Ps1CommandArgument) else parent
        if not isinstance(invocation, Ps1CommandInvocation):
            return None
        if invocation.name is block:
            return [invocation] if invocation.invocation_operator in ('&', '.') else None
        if resolve_command_name(invocation) in ('foreach-object', 'where-object'):
            return [invocation]
        return None

    @property
    def is_readable(self) -> bool:
        """
        Whether this tree is the whole story about what a command name denotes and who reaches it.
        Six independent things say it is not, and every one of them has to be asked, because none
        implies another:

        - the command table is open (`Ps1TypeWorld.command_table_closed` is false), so a dot-sourced
          file, an imported module, an `iex` or an aliasing cmdlet defines or imports a command the
          walk never read. A pure type-system mutation — a `class`, `Add-Type` — is *not* one of
          these: it opens the wider `closed_for_the_whole_run` but not the command table, since it
          binds no command name, so the graph stays readable beside it;
        - an invocation dispatches opaquely (`& $f`), so a name is reached without being written;
        - an assignment binds the `function:` or `alias:` namespace, which defines a command under a
          spelling the definition scan does not read — and leaves the world closed while doing it,
          since `${function:j} = { }` remaps nothing in the type system;
        - a function definition carries a function-level `[Alias]` attribute, the declarative form of
          the same binding: it names a second command for that function under a spelling the
          definition scan, keyed on the function's own name, does not read; see
          `_declares_a_command_alias`;
        - the script calls `Export-ModuleMember`, which hands a name to a caller outside the file;
        - a call written under a qualifier resolves onto a name this script defines; see
          `_collides_with_a_definition`.

        Every consumer reads this as fail-closed: an unreadable graph keeps more, never less.

        The first two rows are the ones
        `refinery.lib.scripts.ps1.options.Ps1DeobfuscationOptions.trust_eval` switches off, being
        the two that say a name is reached by code nobody can read; see `build_call_graph`.

        The `Export-ModuleMember` row catches the explicit export and not the general case. A
        `.psm1` with no export statement exports every function by default, and nothing in a file
        says it is a module — the assumption the bare-output default rests on, stated where a
        caller can see it in `refinery.units.scripting.dps1`.
        """
        return self._readable

    @property
    def exports_a_name(self) -> bool:
        """
        Whether this script hands a command name to code outside the file, which is one of the six
        things `is_readable` reads and the only one that says a *definition* has a reader elsewhere.

        The distinction is worth the separate name because the two questions have different answers
        for the same script. An `Invoke-Expression` opens the type world and could in principle call
        anything, and every pass here has long accepted that risk in exchange for resolving the
        trampolines obfuscators are built out of. An export is not a risk taken for anything: the
        script says in as many words that a caller it cannot see will call this name, so a pass that
        deletes the definition deletes a reachable entry point.
        """
        return self._exports

    def may_run_a_body(self, node: Node) -> bool:
        """
        Whether evaluating *node* itself may run a body of this script, or code the script does not
        spell, which an error handler around it then guards: a script block, which runs wherever
        something runs it; a call that runs or makes one; or a command that dispatches to a target
        the source does not spell, runs code nobody can read, or names a function or keyword body
        this script defines. Where this graph is not the whole story, a name no cmdlet answers to
        may name a body code nobody can read defined; a name a cmdlet answers to is read as that
        cmdlet, the risk every pass here takes in exchange for reading through an `iex` at all.
        """
        if isinstance(node, Ps1ScriptBlock):
            return True
        if isinstance(node, Ps1InvokeMember):
            return (
                is_scriptblock_invoke(node)
                or may_create_a_scriptblock(node)
                or is_execution_context_invoke(node)
            )
        if not isinstance(node, Ps1CommandInvocation):
            return False
        if is_opaque_dispatch(node) or runs_code_it_cannot_read(node):
            return True
        name = get_command_name(node)
        if name is None or self.definitions(name) or self.keyword_definitions(name):
            return True
        if self._readable:
            return False
        resolved = resolve_command_name(node)
        return resolved is None or resolved not in KNOWN_CMDLETS

    def definitions(self, name: str) -> Sequence[Ps1FunctionDefinition]:
        """
        Every function definition a call to `name` could reach, in source order.
        """
        return self._definitions.get(normalize_command_name(name), ())

    def keyword_definitions(self, name: str) -> Sequence[Ps1ScriptBlock]:
        """
        The scriptblock bodies a `workflow`/`configuration` statement binds to `name`, in source
        order. These define the same command name a `function` does but are not themselves a
        `refinery.lib.scripts.ps1.model.Ps1FunctionDefinition`, so a caller weighing whether a name
        is inert reads them beside `definitions`: the empty `function` a call names may be shadowed
        by a `workflow` whose body acts.
        """
        return self._keyword_definitions.get(normalize_command_name(name), ())

    def call_sites(self, name: str) -> Sequence[Ps1CallSite]:
        """
        Every invocation of `name` standing in this tree, in source order, wherever it sits. This
        is what separates the graph from the reachability query below, which reads only the edges it
        can reach from the script itself.
        """
        return self._call_sites.get(normalize_command_name(name), ())

    @property
    def unattributed_sites(self) -> Sequence[Node]:
        """
        Every node standing in this tree that runs code this analysis cannot read — a dispatch
        whose target the source does not spell (`& $f`), a string run as code (`iex $c`), a block
        made or run from one — in source order, under either reading of such code: it may call any
        function this script defines, and a later step may spell the very call it makes (`$f = 'f1';
        & $f`, `iex 'f1'`), so a reader asking where a body may run reads these beside the sites
        that name it.
        """
        return self._unattributed_sites

    @property
    def defined_names(self) -> Sequence[str]:
        """
        Every key this script defines a function under, in source order of the first definition.
        """
        return tuple(self._definitions)

    def reachable_names(self) -> frozenset[str]:
        """
        Every command name some path from the script itself can reach: the names called outside any
        function, then the names those functions call, to a fixpoint. A function whose key is absent
        is called from nowhere in this tree.

        An unreadable graph answers with every name it saw, defined or called, since a name reached
        from outside is reached by a path this cannot trace.
        """
        if not self._readable or self._hands_out_every:
            return frozenset(self._definitions) | frozenset(self._call_sites)
        calls_from: dict[str | None, set[str]] = {}
        calls_from[None] = set(self._handed_out)
        for name, sites in self._call_sites.items():
            for site in sites:
                calls_from.setdefault(site.caller, set()).add(name)
        reachable = set(calls_from.get(None, ()))
        frontier = [name for name in reachable if name in self._definitions]
        while frontier:
            for name in calls_from.get(frontier.pop(), ()):
                if name in reachable:
                    continue
                reachable.add(name)
                if name in self._definitions:
                    frontier.append(name)
        return frozenset(reachable)


class Ps1BodyCallers:
    """
    The calls that may run each script block of the tree *root*, as
    `refinery.lib.scripts.ps1.analysis.dispatch.Ps1CallSites` asks for them: read off the call
    graph *calls* hands over, which is asked for only once a question needs it.
    """

    def __init__(self, root: Node, calls: Callable[[], Ps1CallGraph]):
        self._root = root
        self._calls = calls

    def bodies(self) -> list[Node]:
        return [node for node in self._root.walk() if isinstance(node, Ps1ScriptBlock)]

    def sites_running(self, body: Node) -> list[Node] | None:
        if not isinstance(body, Ps1ScriptBlock):
            return None
        return self._calls().sites_running(body, attributed_only=True)

    def unattributed_sites(self) -> Sequence[Node]:
        return self._calls().unattributed_sites


def names_used_before_defined(
    graph: Ps1CallGraph,
    dominance: DominatorModel,
) -> frozenset[str]:
    """
    The keys with a call site that no definition of the name is guaranteed to have run before. Such
    a call names, at the point it stands, whatever bound the name earlier — nothing, at script
    scope, where Windows PowerShell 5.1 answers the bare word with a `CommandNotFoundException`.
    That error is non-terminating there, so the run carries on and a later call does reach the
    body, but the earlier call ran the error rather than the body — measured: `zzqfoo1; function
    zzqfoo1 { 'boom' }; zzqfoo1` writes an error record and then `boom`. A pass that folds that
    earlier call into the body invents the body's value for a statement that raised, and one that
    deletes it with the definition as an inert pair erases the error; which body the call reaches,
    and whether it reaches one at all, is order the fold does not carry, so every definition and
    call of a name reported here is left alone rather than resolved for the reachable calls alone.

    Only a call the definition shares a control-flow graph with is ordered. A call inside another
    function's body runs when that body is invoked, an ordering no per-body graph carries, and
    dominance across two graphs is always false; reading that as unreached would refuse every helper
    that calls another, so a cross-graph call is treated as reached — the direction that keeps a
    fold the pass already takes. **Strict** dominance, so a definition and a call sharing one node
    do not read as ordered: statement granularity cannot order a use and a definition written on one
    line, and the reflexive answer for that pair is the use-before-definition this refuses.
    """
    unreached: set[str] = set()
    for key in graph.defined_names:
        definitions = graph.definitions(key)
        for site in graph.call_sites(key):
            call = site.invocation
            colocated = [d for d in definitions if dominance.locate_pair(d, call) is not None]
            if colocated and not any(dominance.strictly_dominates(d, call) for d in colocated):
                unreached.add(key)
                break
    return frozenset(unreached)


def calls_after_a_definition(
    graph: Ps1CallGraph,
    dominance: DominatorModel,
) -> frozenset[int]:
    """
    The identities of the call sites a definition of the name they call certainly ran before: in
    the same body, or, for a call in a function body, before every statement outside any function
    body through which that body may first be entered. A helper defined at the top and called from
    functions the script calls later is one; a call from another function that runs before the
    definition is not. A body whose callers cannot all be listed (an unreadable graph, a function
    handed out as a value, a class method, a call nested in a block), or that a cycle of calls
    reaches, is entered from nowhere this can name. **Strict** dominance, for the reason
    `names_used_before_defined` gives.
    """
    entries = _BodyEntries(graph)
    found: set[int] = set()
    for key in graph.defined_names:
        definitions = graph.definitions(key)
        for site in graph.call_sites(key):
            call = site.invocation
            if any(_runs_before(definition, call, dominance, entries) for definition in definitions):
                found.add(id(call))
    return frozenset(found)


def _runs_before(
    definition: Ps1FunctionDefinition,
    call: Node,
    dominance: DominatorModel,
    entries: _BodyEntries,
) -> bool:
    if dominance.locate_pair(definition, call) is not None:
        return dominance.strictly_dominates(definition, call)
    body = _enclosing_block(call)
    if body is None:
        return False
    first = entries.of(body)
    return bool(first) and all(
        dominance.locate_pair(definition, entry) is not None
        and dominance.strictly_dominates(definition, entry)
        for entry in first
    )


def _enclosing_block(node: Node) -> Ps1ScriptBlock | None:
    cursor = node.parent
    while cursor is not None and not isinstance(cursor, Ps1ScriptBlock):
        cursor = cursor.parent
    return cursor


class _BodyEntries:
    """
    For a function body, the call sites outside every function body through which a run may first
    enter it, or `None` where a caller cannot be listed. Computed once per body without
    recursion; a body on a cycle of calls has no entry list this keeps, so neither has any body that
    a cycle reaches.
    """

    def __init__(self, graph: Ps1CallGraph):
        self._graph = graph
        self._memo: dict[int, frozenset[Node] | None] = {}

    def _sites(self, body: Ps1ScriptBlock) -> list[Node] | None:
        named = self._graph.named_callers(body)
        return None if named is None else [*named, *self._graph.unattributed_sites]

    def of(self, body: Ps1ScriptBlock) -> frozenset[Node] | None:
        memo = self._memo
        if id(body) in memo:
            return memo[id(body)]
        active: set[int] = set()
        stack: list[tuple[Ps1ScriptBlock, list[Node], set[Node] | None]] = []

        def push(block: Ps1ScriptBlock) -> bool:
            sites = self._sites(block)
            if sites is None:
                memo[id(block)] = None
                return False
            active.add(id(block))
            stack.append((block, list(sites), set()))
            return True

        if not push(body):
            return None
        while stack:
            block, pending, found = stack[-1]
            if found is not None and pending:
                site = pending.pop()
                holder = _enclosing_block(site)
                if holder is None:
                    found.add(site)
                    continue
                if id(holder) in memo:
                    inner = memo[id(holder)]
                    if inner is None:
                        stack[-1] = (block, pending, None)
                    else:
                        found.update(inner)
                    continue
                if id(holder) in active:
                    stack[-1] = (block, pending, None)
                    continue
                if not push(holder):
                    stack[-1] = (block, pending, None)
                continue
            stack.pop()
            active.discard(id(block))
            result = None if found is None else frozenset(found)
            memo[id(block)] = result
            if stack:
                outer, outer_pending, outer_found = stack[-1]
                if result is None:
                    stack[-1] = (outer, outer_pending, None)
                elif outer_found is not None:
                    outer_found.update(result)
        return memo.get(id(body))


def _collides_with_a_definition(
    resolved: Sequence[str],
    definitions: Mapping[str, Sequence[Ps1FunctionDefinition]],
) -> bool:
    """
    Whether some call keyed under a qualifier resolves onto a name this script defines.

    `& 'MyModule\\Qzmr'` keys as `mymodule\\qzmr` while `function Qzmr` keys as `qzmr`, so nothing
    matches, the definition reads as uncalled, and deleting it leaves a script calling a name it no
    longer defines. `resolved` holds every name a call may run that its written key does not spell,
    which is the deny-list reading `refinery.lib.scripts.ps1.ast.resolve_command_name` gives — so an
    alias is here too, and `iex $x` beside a `function Invoke-Expression` collides for the same
    reason, as does `item` beside a `function Get-Item`, which the implicit `Get-` retry reaches.

    **The two arrive under different conditions, because they sit at opposite ends of the
    precedence.** An alias is the highest tier and beats a script function, so `iex` reaches
    `Invoke-Expression` however the script spells its own definitions. The implicit `Get-` retry is
    the lowest, reached only once the function tier has missed, so `item` reaches `Get-Item` only in
    a script that defines no `item` of its own — and `build_call_graph` therefore withholds a retry
    name when the bare key is one this script defines. The set it withholds against is the one
    `defined_names` reports, which is what the command model's own function tier reads, so the two
    cannot disagree about which calls the retry is reached from.

    **The condition is the collision and not the qualifier.** A quoted executable path is the same
    shape: `& 'C:\\tools\\stage2.exe'` keys as the path and resolves to `stage2.exe`. Reading the
    backslash itself as the signal would make every script that invokes an executable by path
    unreadable, and `& 'C:\\Windows\\Temp\\payload.exe'` is one of the commonest shapes there is;
    that is not failing closed, it is switching the analysis off. Asked this way it costs nothing
    unless the stripped name is one this tree actually defines.

    **This has no PowerShell oracle and is a policy choice.** Real PowerShell errors on
    `& 'MyModule\\Qzmr'` when no such module is loaded — it does not reach the local definition — so
    the language does not say the definition must survive. What says so is the internal invariant
    that no removal leaves a dangling reference, plus a decision to fail closed in front of the
    lexer's qualified-name hole rather than behind it. `& 'global:Qzmr'` is a different case and is
    oracle-backed: the scope qualifier is stripped by the *key*, so the call and the definition
    already meet and nothing here fires.

    The call is not filed under the stripped key instead, which would be the other way to make the
    two meet. The same list feeds `refinery.lib.scripts.ps1.analysis.effects.Ps1OutputFlow`, where
    an extra call site *grounds* a function and licenses deleting what its body writes — so a guess
    that keeps a definition alive would buy that at the price of a payload.
    """
    return any(name in definitions for name in resolved)


def _declares_a_command_alias(definition: Ps1FunctionDefinition) -> bool:
    """
    Whether `definition` carries a function-level `[Alias(...)]` attribute, which binds each name it
    lists as a command name for the function the moment the definition runs — a second spelling the
    definition scan, keyed on the function's own name, never reads, and one the call scan reaches
    under a name no definition of it stands. It is the declarative form of a `Set-Alias`, so the
    graph reads it the way `binds_command_identity` reads the imperative `alias:` write: the tree is
    no longer the whole story about what a command name denotes.

    Only the attributes on the `param` block itself are read. An `[Alias]` on one of the parameters
    names a parameter of the function, not the command, and leaves the graph the whole story.
    """
    block = get_param_block(definition.body)
    if block is None:
        return False
    return any(
        attribute.name.rpartition('.')[2].lower() in _COMMAND_ALIAS_ATTRIBUTES
        for attribute in block.attributes
    )


def build_call_graph(
    root: Ps1Script,
    world: Ps1TypeWorld,
    options: object | None = None,
) -> Ps1CallGraph:
    """
    Walk the whole tree once, recording every function definition, every statically named invocation
    with the function that holds it, and every reason the result is not the whole story.

    The walk runs in source order so that a consumer removing what it finds removes from the front,
    and cannot short-circuit on the first unknown, because the definitions and call sites are still
    needed to decide what to keep.

    The collision row is decided after the walk rather than during it, because a definition may be
    written below the call that resolves onto it and a script is not read top to bottom.

    `refinery.lib.scripts.ps1.options.Ps1DeobfuscationOptions.trust_eval` clears exactly the two
    rows that say code nobody can read reaches a name — the open world, through the verdict this is
    handed, and the opaque dispatch, here. The other four stand under it: an export and a collision
    are written in the script, and so are an assignment into the `function:` namespace and a
    function-level `[Alias]` attribute, each a definition under a spelling the scan does not read
    rather than a call from outside it.
    """
    trusting = eval_is_trusted(options)
    definitions: dict[str, list[Ps1FunctionDefinition]] = {}
    keyword_definitions: dict[str, list[Ps1ScriptBlock]] = {}
    call_sites: dict[str, list[Ps1CallSite]] = {}
    unattributed_sites: list[Node] = []
    qualified: list[str] = []
    retried: dict[str, list[str]] = {}
    readable = world.command_table_closed
    exports = False
    handed_out: set[str] = set()
    hands_out_every = False
    for node in root.walk_in_order():
        if isinstance(node, (Ps1CommandInvocation, Ps1InvokeMember)) and runs_code_it_cannot_read(node):
            unattributed_sites.append(node)
        handing = _functions_handed_out(node)
        if handing is None:
            hands_out_every = True
        else:
            handed_out.update(handing)
        if isinstance(node, Ps1FunctionDefinition):
            if not _is_class_method(node):
                definitions.setdefault(normalize_command_name(node.name), []).append(node)
                if _declares_a_command_alias(node):
                    readable = False
        elif isinstance(node, Ps1CommandInvocation):
            binding = command_definition_keyword_binding(node)
            if binding is not None:
                keyword_name, keyword_body = binding
                keyword_definitions.setdefault(keyword_name, []).append(keyword_body)
            name = get_command_name(node)
            if name is None:
                if not trusting and is_opaque_dispatch(node):
                    readable = False
                continue
            key = normalize_command_name(name)
            resolved = resolve_command_name(node)
            if resolved in _EXPORTING_COMMANDS:
                readable = False
                exports = True
            if resolved is not None and resolved != key:
                qualified.append(resolved)
            retry = None if resolved is None else implicit_get_retry(resolved)
            if retry is not None:
                retried.setdefault(key, []).append(retry)
            call_sites.setdefault(key, []).append(Ps1CallSite(node, _enclosing_function(node)))
        elif binds_command_identity(node):
            readable = False
    for key, names in retried.items():
        if key not in definitions:
            qualified.extend(names)
    if _collides_with_a_definition(qualified, definitions):
        readable = False
    return Ps1CallGraph(
        definitions,
        keyword_definitions,
        call_sites,
        unattributed_sites,
        readable,
        exports,
        frozenset(handed_out),
        hands_out_every,
    )


_COMMAND_LOOKUPS = frozenset({
    'getcmdlet',
    'getcmdletbytypename',
    'getcmdlets',
    'getcommand',
    'getcommandname',
    'getcommands',
})


def _functions_handed_out(node: Node) -> tuple[str, ...] | None:
    """
    The keys of the functions *node* may hand out as a value rather than call, or `None` where it
    may hand out any of them: a `$function:K` occurrence; a string that names a path into
    the `function:` drive; `Get-Command`; a command lookup through `$ExecutionContext` or
    `$PSCmdlet`; `$MyInvocation` read inside a function body, which hands out that function. An item
    command whose path cannot be read is the residual the world model documents for the same
    commands: refusing on it would refuse every script that copies or deletes a file by variable.
    """
    if isinstance(node, Ps1Variable):
        if node.scope is Ps1ScopeModifier.FUNCTION:
            return (normalize_command_name(node.name),)
        if node.scope is Ps1ScopeModifier.NONE and node.name.lower() == 'myinvocation':
            cursor = node.parent
            while cursor is not None:
                if isinstance(cursor, Ps1FunctionDefinition):
                    return (normalize_command_name(cursor.name),)
                cursor = cursor.parent
        return ()
    if isinstance(node, (Ps1StringLiteral, Ps1HereString)):
        return _function_paths_in(node.value)
    if isinstance(node, Ps1CommandInvocation):
        if resolve_command_name(node) == 'get-command' and not _only_a_member_is_read(node):
            return _command_looked_up(node)
        return ()
    if isinstance(node, Ps1InvokeMember) and node.access is Ps1AccessKind.INSTANCE:
        if not member_may_be(node.member, _COMMAND_LOOKUPS):
            return ()
        receiver = node.object
        while isinstance(receiver, Ps1MemberAccess):
            receiver = receiver.object
        if isinstance(receiver, Ps1Variable) and receiver.name.lower() in ('executioncontext', 'pscmdlet'):
            return None
    return ()


def _command_looked_up(command: Ps1CommandInvocation) -> tuple[str, ...] | None:
    """
    The key of the function `Get-Command` *command* looks up by name, or `None` where it may list
    any of them: the name is the value bound to `-Name`, written as such or as the first argument
    no parameter takes. Every other selection, `-CommandType Function` and `-Verb` among them, and
    a splat, whose table this cannot see into, lists every function its filter passes.
    """
    for argument in command.arguments:
        if not isinstance(argument, Ps1CommandArgument):
            return None
        value = argument.value
        if isinstance(value, Ps1Variable) and value.splatted:
            return None
    written = bound_argument_value(command, 'name')
    if written is None:
        written = next(iter(free_positional_values(command, 'get-command')), None)
    text = None if written is None else string_value(written)
    if text is None or has_wildcard(text):
        return None
    return (normalize_command_name(text),)


def _only_a_member_is_read(command: Ps1CommandInvocation) -> bool:
    """
    Whether what *command* writes out is used only for one member other than the block it carries,
    where it stands, as `(Get-Command K).Name` uses it: nothing that runs the body leaves.
    """
    cursor: Node = command
    parent = cursor.parent
    if isinstance(parent, Ps1PipelineElement) and not parent.redirections:
        pipeline = parent.parent
        if not isinstance(pipeline, Ps1Pipeline) or len(pipeline.elements) != 1:
            return False
        cursor, parent = pipeline, pipeline.parent
    while isinstance(parent, Ps1ParenExpression):
        cursor, parent = parent, parent.parent
    if not isinstance(parent, Ps1MemberAccess) or parent.object is not cursor:
        return False
    name = get_member_name(parent.member)
    return name is not None and name.lower() != 'scriptblock'


def _function_paths_in(text: str) -> tuple[str, ...] | None:
    """
    The keys of the functions the paths into the `function:` drive in *text* name, or `None` where
    one of them names no single function.
    """
    lowered = text.lower()
    found: list[str] = []
    start = lowered.find('function:')
    while start >= 0:
        rest = lowered[start + len('function:'):].lstrip(':\\/')
        name = re.split(r'[\s\'"`;,|)}\]]', rest, maxsplit=1)[0]
        if not name or has_wildcard(name):
            return None
        found.append(normalize_command_name(name))
        start = lowered.find('function:', start + 1)
    return tuple(found)

Functions

def binds_command_identity(node)

Whether node writes the function: or alias: namespace, binding a command name to something the definition scan does not read as a definition and the call scan does not read as a call. Every name-keyed decision has to treat such a node as an unknown: it can bind the name about to be deleted, and it can be the only thing that reaches it.

Expand source code Browse git

def binds_command_identity(node: Node) -> bool:
    """
    Whether `node` writes the `function:` or `alias:` namespace, binding a command name to something
    the definition scan does not read as a definition and the call scan does not read as a call.
    Every name-keyed decision has to treat such a node as an unknown: it can bind the name about to
    be deleted, and it can be the only thing that reaches it.
    """
    if not isinstance(node, Ps1AssignmentExpression):
        return False
    return any(
        variable.scope in _IDENTITY_SCOPES
        for variable in assignment_target_variables(node.target)
    )

def names_used_before_defined(graph, dominance)

The keys with a call site that no definition of the name is guaranteed to have run before. Such a call names, at the point it stands, whatever bound the name earlier — nothing, at script scope, where Windows PowerShell 5.1 answers the bare word with a CommandNotFoundException. That error is non-terminating there, so the run carries on and a later call does reach the body, but the earlier call ran the error rather than the body — measured: zzqfoo1; function zzqfoo1 { 'boom' }; zzqfoo1<code> writes an error record and then </code>boom. A pass that folds that earlier call into the body invents the body's value for a statement that raised, and one that deletes it with the definition as an inert pair erases the error; which body the call reaches, and whether it reaches one at all, is order the fold does not carry, so every definition and call of a name reported here is left alone rather than resolved for the reachable calls alone.

Only a call the definition shares a control-flow graph with is ordered. A call inside another function's body runs when that body is invoked, an ordering no per-body graph carries, and dominance across two graphs is always false; reading that as unreached would refuse every helper that calls another, so a cross-graph call is treated as reached — the direction that keeps a fold the pass already takes. Strict dominance, so a definition and a call sharing one node do not read as ordered: statement granularity cannot order a use and a definition written on one line, and the reflexive answer for that pair is the use-before-definition this refuses.

Expand source code Browse git

def names_used_before_defined(
    graph: Ps1CallGraph,
    dominance: DominatorModel,
) -> frozenset[str]:
    """
    The keys with a call site that no definition of the name is guaranteed to have run before. Such
    a call names, at the point it stands, whatever bound the name earlier — nothing, at script
    scope, where Windows PowerShell 5.1 answers the bare word with a `CommandNotFoundException`.
    That error is non-terminating there, so the run carries on and a later call does reach the
    body, but the earlier call ran the error rather than the body — measured: `zzqfoo1; function
    zzqfoo1 { 'boom' }; zzqfoo1` writes an error record and then `boom`. A pass that folds that
    earlier call into the body invents the body's value for a statement that raised, and one that
    deletes it with the definition as an inert pair erases the error; which body the call reaches,
    and whether it reaches one at all, is order the fold does not carry, so every definition and
    call of a name reported here is left alone rather than resolved for the reachable calls alone.

    Only a call the definition shares a control-flow graph with is ordered. A call inside another
    function's body runs when that body is invoked, an ordering no per-body graph carries, and
    dominance across two graphs is always false; reading that as unreached would refuse every helper
    that calls another, so a cross-graph call is treated as reached — the direction that keeps a
    fold the pass already takes. **Strict** dominance, so a definition and a call sharing one node
    do not read as ordered: statement granularity cannot order a use and a definition written on one
    line, and the reflexive answer for that pair is the use-before-definition this refuses.
    """
    unreached: set[str] = set()
    for key in graph.defined_names:
        definitions = graph.definitions(key)
        for site in graph.call_sites(key):
            call = site.invocation
            colocated = [d for d in definitions if dominance.locate_pair(d, call) is not None]
            if colocated and not any(dominance.strictly_dominates(d, call) for d in colocated):
                unreached.add(key)
                break
    return frozenset(unreached)

def calls_after_a_definition(graph, dominance)

The identities of the call sites a definition of the name they call certainly ran before: in the same body, or, for a call in a function body, before every statement outside any function body through which that body may first be entered. A helper defined at the top and called from functions the script calls later is one; a call from another function that runs before the definition is not. A body whose callers cannot all be listed (an unreadable graph, a function handed out as a value, a class method, a call nested in a block), or that a cycle of calls reaches, is entered from nowhere this can name. Strict dominance, for the reason names_used_before_defined() gives.

Expand source code Browse git

def calls_after_a_definition(
    graph: Ps1CallGraph,
    dominance: DominatorModel,
) -> frozenset[int]:
    """
    The identities of the call sites a definition of the name they call certainly ran before: in
    the same body, or, for a call in a function body, before every statement outside any function
    body through which that body may first be entered. A helper defined at the top and called from
    functions the script calls later is one; a call from another function that runs before the
    definition is not. A body whose callers cannot all be listed (an unreadable graph, a function
    handed out as a value, a class method, a call nested in a block), or that a cycle of calls
    reaches, is entered from nowhere this can name. **Strict** dominance, for the reason
    `names_used_before_defined` gives.
    """
    entries = _BodyEntries(graph)
    found: set[int] = set()
    for key in graph.defined_names:
        definitions = graph.definitions(key)
        for site in graph.call_sites(key):
            call = site.invocation
            if any(_runs_before(definition, call, dominance, entries) for definition in definitions):
                found.add(id(call))
    return frozenset(found)

def build_call_graph(root, world, options=None)

Walk the whole tree once, recording every function definition, every statically named invocation with the function that holds it, and every reason the result is not the whole story.

The walk runs in source order so that a consumer removing what it finds removes from the front, and cannot short-circuit on the first unknown, because the definitions and call sites are still needed to decide what to keep.

The collision row is decided after the walk rather than during it, because a definition may be written below the call that resolves onto it and a script is not read top to bottom.

Ps1DeobfuscationOptions.trust_eval clears exactly the two rows that say code nobody can read reaches a name — the open world, through the verdict this is handed, and the opaque dispatch, here. The other four stand under it: an export and a collision are written in the script, and so are an assignment into the function: namespace and a function-level [Alias] attribute, each a definition under a spelling the scan does not read rather than a call from outside it.

Expand source code Browse git

def build_call_graph(
    root: Ps1Script,
    world: Ps1TypeWorld,
    options: object | None = None,
) -> Ps1CallGraph:
    """
    Walk the whole tree once, recording every function definition, every statically named invocation
    with the function that holds it, and every reason the result is not the whole story.

    The walk runs in source order so that a consumer removing what it finds removes from the front,
    and cannot short-circuit on the first unknown, because the definitions and call sites are still
    needed to decide what to keep.

    The collision row is decided after the walk rather than during it, because a definition may be
    written below the call that resolves onto it and a script is not read top to bottom.

    `refinery.lib.scripts.ps1.options.Ps1DeobfuscationOptions.trust_eval` clears exactly the two
    rows that say code nobody can read reaches a name — the open world, through the verdict this is
    handed, and the opaque dispatch, here. The other four stand under it: an export and a collision
    are written in the script, and so are an assignment into the `function:` namespace and a
    function-level `[Alias]` attribute, each a definition under a spelling the scan does not read
    rather than a call from outside it.
    """
    trusting = eval_is_trusted(options)
    definitions: dict[str, list[Ps1FunctionDefinition]] = {}
    keyword_definitions: dict[str, list[Ps1ScriptBlock]] = {}
    call_sites: dict[str, list[Ps1CallSite]] = {}
    unattributed_sites: list[Node] = []
    qualified: list[str] = []
    retried: dict[str, list[str]] = {}
    readable = world.command_table_closed
    exports = False
    handed_out: set[str] = set()
    hands_out_every = False
    for node in root.walk_in_order():
        if isinstance(node, (Ps1CommandInvocation, Ps1InvokeMember)) and runs_code_it_cannot_read(node):
            unattributed_sites.append(node)
        handing = _functions_handed_out(node)
        if handing is None:
            hands_out_every = True
        else:
            handed_out.update(handing)
        if isinstance(node, Ps1FunctionDefinition):
            if not _is_class_method(node):
                definitions.setdefault(normalize_command_name(node.name), []).append(node)
                if _declares_a_command_alias(node):
                    readable = False
        elif isinstance(node, Ps1CommandInvocation):
            binding = command_definition_keyword_binding(node)
            if binding is not None:
                keyword_name, keyword_body = binding
                keyword_definitions.setdefault(keyword_name, []).append(keyword_body)
            name = get_command_name(node)
            if name is None:
                if not trusting and is_opaque_dispatch(node):
                    readable = False
                continue
            key = normalize_command_name(name)
            resolved = resolve_command_name(node)
            if resolved in _EXPORTING_COMMANDS:
                readable = False
                exports = True
            if resolved is not None and resolved != key:
                qualified.append(resolved)
            retry = None if resolved is None else implicit_get_retry(resolved)
            if retry is not None:
                retried.setdefault(key, []).append(retry)
            call_sites.setdefault(key, []).append(Ps1CallSite(node, _enclosing_function(node)))
        elif binds_command_identity(node):
            readable = False
    for key, names in retried.items():
        if key not in definitions:
            qualified.extend(names)
    if _collides_with_a_definition(qualified, definitions):
        readable = False
    return Ps1CallGraph(
        definitions,
        keyword_definitions,
        call_sites,
        unattributed_sites,
        readable,
        exports,
        frozenset(handed_out),
        hands_out_every,
    )

Classes

class Ps1CallSite (invocation, caller)

One invocation of a command name, paired with the key of the outermost function whose body holds it — see _enclosing_function — which is the edge's source, where the invocation is its target.

Expand source code Browse git

class Ps1CallSite(NamedTuple):
    """
    One invocation of a command name, paired with the key of the outermost function whose body holds
    it — see `_enclosing_function` — which is the edge's source, where the invocation is its target.
    """
    invocation: Ps1CommandInvocation
    caller: str | None

Ancestors

• builtins.tuple

Instance variables

var invocation

Alias for field number 0

Expand source code Browse git

class Ps1CallSite(NamedTuple):
    """
    One invocation of a command name, paired with the key of the outermost function whose body holds
    it — see `_enclosing_function` — which is the edge's source, where the invocation is its target.
    """
    invocation: Ps1CommandInvocation
    caller: str | None

var caller

Alias for field number 1

Expand source code Browse git

class Ps1CallSite(NamedTuple):
    """
    One invocation of a command name, paired with the key of the outermost function whose body holds
    it — see `_enclosing_function` — which is the edge's source, where the invocation is its target.
    """
    invocation: Ps1CommandInvocation
    caller: str | None

class Ps1CallGraph (definitions, keyword_definitions, call_sites, unattributed_sites, readable, exports, handed_out=frozenset(), hands_out_every=False)

The verdict of build_call_graph(). Definitions and call sites are keyed through normalize_command_name(), so function global:F and a bare call to F meet on one key, and every definition sharing a key is kept: a redefinition shadows the earlier body only from the point it runs, which is order and scope information no walk over the tree carries.

Expand source code Browse git

class Ps1CallGraph:
    """
    The verdict of `build_call_graph`. Definitions and call sites are keyed through
    `refinery.lib.scripts.ps1.ast.normalize_command_name`, so `function global:F` and a bare call to
    `F` meet on one key, and every definition sharing a key is kept: a redefinition shadows the
    earlier body only from the point it runs, which is order and scope information no walk over the
    tree carries.
    """

    def __init__(
        self,
        definitions: Mapping[str, Sequence[Ps1FunctionDefinition]],
        keyword_definitions: Mapping[str, Sequence[Ps1ScriptBlock]],
        call_sites: Mapping[str, Sequence[Ps1CallSite]],
        unattributed_sites: Sequence[Node],
        readable: bool,
        exports: bool,
        handed_out: frozenset[str] = frozenset(),
        hands_out_every: bool = False,
    ):
        self._definitions = dict(definitions)
        self._keyword_definitions = dict(keyword_definitions)
        self._call_sites = dict(call_sites)
        self._unattributed_sites = tuple(unattributed_sites)
        self._readable = readable
        self._exports = exports
        self._handed_out = handed_out
        self._hands_out_every = hands_out_every

    def hands_out(self, name: str) -> bool:
        """
        Whether the script may reach the body of the function *name* other than by calling it by
        name: it reads `$function:K`, writes a path into the `function:` drive, asks `Get-Command`
        for it, looks a command up through `$ExecutionContext` or `$PSCmdlet`, reads
        `$MyInvocation` inside it, or does any of these where the name cannot be read. A body handed
        out this way may run wherever something runs a block, so no list of call sites is the list of
        places it runs.
        """
        return self._hands_out_every or normalize_command_name(name) in self._handed_out

    def named_callers(self, body: Node) -> list[Node] | None:
        """
        The calls naming the function whose body *body* is, or `None` where those are not all the
        calls that may run it beside `unattributed_sites`: *body* is no function's, this graph
        cannot be read, the function is a class method or has no name, or the script hands it out.
        """
        parent = body.parent
        if (
            not self._readable
            or not isinstance(parent, Ps1FunctionDefinition)
            or _is_class_method(parent)
            or not parent.name
            or self.hands_out(parent.name)
        ):
            return None
        return [site.invocation for site in self.call_sites(parent.name)]

    def sites_running(self, block: Ps1ScriptBlock, attributed_only: bool = False) -> list[Node] | None:
        """
        The calls that may run *block*, or `None` where they cannot all be named. A function body is
        run by the calls naming the function (`named_callers`), and, unless *attributed_only*, by
        every call in `unattributed_sites`. A script block is run by the `&` or `.` that invokes it
        where it is written, and by the `ForEach-Object` or `Where-Object` it is handed to.
        """
        parent = block.parent
        if isinstance(parent, Ps1FunctionDefinition):
            named = self.named_callers(block)
            if named is None or attributed_only:
                return named
            return [*named, *self.unattributed_sites]
        invocation = parent.parent if isinstance(parent, Ps1CommandArgument) else parent
        if not isinstance(invocation, Ps1CommandInvocation):
            return None
        if invocation.name is block:
            return [invocation] if invocation.invocation_operator in ('&', '.') else None
        if resolve_command_name(invocation) in ('foreach-object', 'where-object'):
            return [invocation]
        return None

    @property
    def is_readable(self) -> bool:
        """
        Whether this tree is the whole story about what a command name denotes and who reaches it.
        Six independent things say it is not, and every one of them has to be asked, because none
        implies another:

        - the command table is open (`Ps1TypeWorld.command_table_closed` is false), so a dot-sourced
          file, an imported module, an `iex` or an aliasing cmdlet defines or imports a command the
          walk never read. A pure type-system mutation — a `class`, `Add-Type` — is *not* one of
          these: it opens the wider `closed_for_the_whole_run` but not the command table, since it
          binds no command name, so the graph stays readable beside it;
        - an invocation dispatches opaquely (`& $f`), so a name is reached without being written;
        - an assignment binds the `function:` or `alias:` namespace, which defines a command under a
          spelling the definition scan does not read — and leaves the world closed while doing it,
          since `${function:j} = { }` remaps nothing in the type system;
        - a function definition carries a function-level `[Alias]` attribute, the declarative form of
          the same binding: it names a second command for that function under a spelling the
          definition scan, keyed on the function's own name, does not read; see
          `_declares_a_command_alias`;
        - the script calls `Export-ModuleMember`, which hands a name to a caller outside the file;
        - a call written under a qualifier resolves onto a name this script defines; see
          `_collides_with_a_definition`.

        Every consumer reads this as fail-closed: an unreadable graph keeps more, never less.

        The first two rows are the ones
        `refinery.lib.scripts.ps1.options.Ps1DeobfuscationOptions.trust_eval` switches off, being
        the two that say a name is reached by code nobody can read; see `build_call_graph`.

        The `Export-ModuleMember` row catches the explicit export and not the general case. A
        `.psm1` with no export statement exports every function by default, and nothing in a file
        says it is a module — the assumption the bare-output default rests on, stated where a
        caller can see it in `refinery.units.scripting.dps1`.
        """
        return self._readable

    @property
    def exports_a_name(self) -> bool:
        """
        Whether this script hands a command name to code outside the file, which is one of the six
        things `is_readable` reads and the only one that says a *definition* has a reader elsewhere.

        The distinction is worth the separate name because the two questions have different answers
        for the same script. An `Invoke-Expression` opens the type world and could in principle call
        anything, and every pass here has long accepted that risk in exchange for resolving the
        trampolines obfuscators are built out of. An export is not a risk taken for anything: the
        script says in as many words that a caller it cannot see will call this name, so a pass that
        deletes the definition deletes a reachable entry point.
        """
        return self._exports

    def may_run_a_body(self, node: Node) -> bool:
        """
        Whether evaluating *node* itself may run a body of this script, or code the script does not
        spell, which an error handler around it then guards: a script block, which runs wherever
        something runs it; a call that runs or makes one; or a command that dispatches to a target
        the source does not spell, runs code nobody can read, or names a function or keyword body
        this script defines. Where this graph is not the whole story, a name no cmdlet answers to
        may name a body code nobody can read defined; a name a cmdlet answers to is read as that
        cmdlet, the risk every pass here takes in exchange for reading through an `iex` at all.
        """
        if isinstance(node, Ps1ScriptBlock):
            return True
        if isinstance(node, Ps1InvokeMember):
            return (
                is_scriptblock_invoke(node)
                or may_create_a_scriptblock(node)
                or is_execution_context_invoke(node)
            )
        if not isinstance(node, Ps1CommandInvocation):
            return False
        if is_opaque_dispatch(node) or runs_code_it_cannot_read(node):
            return True
        name = get_command_name(node)
        if name is None or self.definitions(name) or self.keyword_definitions(name):
            return True
        if self._readable:
            return False
        resolved = resolve_command_name(node)
        return resolved is None or resolved not in KNOWN_CMDLETS

    def definitions(self, name: str) -> Sequence[Ps1FunctionDefinition]:
        """
        Every function definition a call to `name` could reach, in source order.
        """
        return self._definitions.get(normalize_command_name(name), ())

    def keyword_definitions(self, name: str) -> Sequence[Ps1ScriptBlock]:
        """
        The scriptblock bodies a `workflow`/`configuration` statement binds to `name`, in source
        order. These define the same command name a `function` does but are not themselves a
        `refinery.lib.scripts.ps1.model.Ps1FunctionDefinition`, so a caller weighing whether a name
        is inert reads them beside `definitions`: the empty `function` a call names may be shadowed
        by a `workflow` whose body acts.
        """
        return self._keyword_definitions.get(normalize_command_name(name), ())

    def call_sites(self, name: str) -> Sequence[Ps1CallSite]:
        """
        Every invocation of `name` standing in this tree, in source order, wherever it sits. This
        is what separates the graph from the reachability query below, which reads only the edges it
        can reach from the script itself.
        """
        return self._call_sites.get(normalize_command_name(name), ())

    @property
    def unattributed_sites(self) -> Sequence[Node]:
        """
        Every node standing in this tree that runs code this analysis cannot read — a dispatch
        whose target the source does not spell (`& $f`), a string run as code (`iex $c`), a block
        made or run from one — in source order, under either reading of such code: it may call any
        function this script defines, and a later step may spell the very call it makes (`$f = 'f1';
        & $f`, `iex 'f1'`), so a reader asking where a body may run reads these beside the sites
        that name it.
        """
        return self._unattributed_sites

    @property
    def defined_names(self) -> Sequence[str]:
        """
        Every key this script defines a function under, in source order of the first definition.
        """
        return tuple(self._definitions)

    def reachable_names(self) -> frozenset[str]:
        """
        Every command name some path from the script itself can reach: the names called outside any
        function, then the names those functions call, to a fixpoint. A function whose key is absent
        is called from nowhere in this tree.

        An unreadable graph answers with every name it saw, defined or called, since a name reached
        from outside is reached by a path this cannot trace.
        """
        if not self._readable or self._hands_out_every:
            return frozenset(self._definitions) | frozenset(self._call_sites)
        calls_from: dict[str | None, set[str]] = {}
        calls_from[None] = set(self._handed_out)
        for name, sites in self._call_sites.items():
            for site in sites:
                calls_from.setdefault(site.caller, set()).add(name)
        reachable = set(calls_from.get(None, ()))
        frontier = [name for name in reachable if name in self._definitions]
        while frontier:
            for name in calls_from.get(frontier.pop(), ()):
                if name in reachable:
                    continue
                reachable.add(name)
                if name in self._definitions:
                    frontier.append(name)
        return frozenset(reachable)

Instance variables

var is_readable

Whether this tree is the whole story about what a command name denotes and who reaches it. Six independent things say it is not, and every one of them has to be asked, because none implies another:

• the command table is open (Ps1TypeWorld.command_table_closed is false), so a dot-sourced file, an imported module, an iex or an aliasing cmdlet defines or imports a command the walk never read. A pure type-system mutation — a class, Add-Type — is not one of these: it opens the wider closed_for_the_whole_run but not the command table, since it binds no command name, so the graph stays readable beside it;
• an invocation dispatches opaquely (& $f), so a name is reached without being written;
• an assignment binds the function: or alias: namespace, which defines a command under a spelling the definition scan does not read — and leaves the world closed while doing it, since ${function:j} = { } remaps nothing in the type system;
• a function definition carries a function-level [Alias] attribute, the declarative form of the same binding: it names a second command for that function under a spelling the definition scan, keyed on the function's own name, does not read; see _declares_a_command_alias;
• the script calls Export-ModuleMember, which hands a name to a caller outside the file;
• a call written under a qualifier resolves onto a name this script defines; see _collides_with_a_definition.

Every consumer reads this as fail-closed: an unreadable graph keeps more, never less.

The first two rows are the ones Ps1DeobfuscationOptions.trust_eval switches off, being the two that say a name is reached by code nobody can read; see build_call_graph().

The Export-ModuleMember row catches the explicit export and not the general case. A .psm1 with no export statement exports every function by default, and nothing in a file says it is a module — the assumption the bare-output default rests on, stated where a caller can see it in refinery.units.scripting.dps1.

Expand source code Browse git

@property
def is_readable(self) -> bool:
    """
    Whether this tree is the whole story about what a command name denotes and who reaches it.
    Six independent things say it is not, and every one of them has to be asked, because none
    implies another:

    - the command table is open (`Ps1TypeWorld.command_table_closed` is false), so a dot-sourced
      file, an imported module, an `iex` or an aliasing cmdlet defines or imports a command the
      walk never read. A pure type-system mutation — a `class`, `Add-Type` — is *not* one of
      these: it opens the wider `closed_for_the_whole_run` but not the command table, since it
      binds no command name, so the graph stays readable beside it;
    - an invocation dispatches opaquely (`& $f`), so a name is reached without being written;
    - an assignment binds the `function:` or `alias:` namespace, which defines a command under a
      spelling the definition scan does not read — and leaves the world closed while doing it,
      since `${function:j} = { }` remaps nothing in the type system;
    - a function definition carries a function-level `[Alias]` attribute, the declarative form of
      the same binding: it names a second command for that function under a spelling the
      definition scan, keyed on the function's own name, does not read; see
      `_declares_a_command_alias`;
    - the script calls `Export-ModuleMember`, which hands a name to a caller outside the file;
    - a call written under a qualifier resolves onto a name this script defines; see
      `_collides_with_a_definition`.

    Every consumer reads this as fail-closed: an unreadable graph keeps more, never less.

    The first two rows are the ones
    `refinery.lib.scripts.ps1.options.Ps1DeobfuscationOptions.trust_eval` switches off, being
    the two that say a name is reached by code nobody can read; see `build_call_graph`.

    The `Export-ModuleMember` row catches the explicit export and not the general case. A
    `.psm1` with no export statement exports every function by default, and nothing in a file
    says it is a module — the assumption the bare-output default rests on, stated where a
    caller can see it in `refinery.units.scripting.dps1`.
    """
    return self._readable

var exports_a_name

Whether this script hands a command name to code outside the file, which is one of the six things is_readable reads and the only one that says a definition has a reader elsewhere.

The distinction is worth the separate name because the two questions have different answers for the same script. An Invoke-Expression opens the type world and could in principle call anything, and every pass here has long accepted that risk in exchange for resolving the trampolines obfuscators are built out of. An export is not a risk taken for anything: the script says in as many words that a caller it cannot see will call this name, so a pass that deletes the definition deletes a reachable entry point.

Expand source code Browse git

@property
def exports_a_name(self) -> bool:
    """
    Whether this script hands a command name to code outside the file, which is one of the six
    things `is_readable` reads and the only one that says a *definition* has a reader elsewhere.

    The distinction is worth the separate name because the two questions have different answers
    for the same script. An `Invoke-Expression` opens the type world and could in principle call
    anything, and every pass here has long accepted that risk in exchange for resolving the
    trampolines obfuscators are built out of. An export is not a risk taken for anything: the
    script says in as many words that a caller it cannot see will call this name, so a pass that
    deletes the definition deletes a reachable entry point.
    """
    return self._exports

var unattributed_sites

Every node standing in this tree that runs code this analysis cannot read — a dispatch whose target the source does not spell (& $f), a string run as code (iex $c), a block made or run from one — in source order, under either reading of such code: it may call any function this script defines, and a later step may spell the very call it makes ($f = 'f1'; & $f<code>, </code>iex 'f1'), so a reader asking where a body may run reads these beside the sites that name it.

Expand source code Browse git

@property
def unattributed_sites(self) -> Sequence[Node]:
    """
    Every node standing in this tree that runs code this analysis cannot read — a dispatch
    whose target the source does not spell (`& $f`), a string run as code (`iex $c`), a block
    made or run from one — in source order, under either reading of such code: it may call any
    function this script defines, and a later step may spell the very call it makes (`$f = 'f1';
    & $f`, `iex 'f1'`), so a reader asking where a body may run reads these beside the sites
    that name it.
    """
    return self._unattributed_sites

var defined_names

Every key this script defines a function under, in source order of the first definition.

Expand source code Browse git

@property
def defined_names(self) -> Sequence[str]:
    """
    Every key this script defines a function under, in source order of the first definition.
    """
    return tuple(self._definitions)

Methods

def hands_out(self, name)

Whether the script may reach the body of the function name other than by calling it by name: it reads $function:K, writes a path into the function: drive, asks Get-Command for it, looks a command up through $ExecutionContext or $PSCmdlet, reads $MyInvocation inside it, or does any of these where the name cannot be read. A body handed out this way may run wherever something runs a block, so no list of call sites is the list of places it runs.

Expand source code Browse git

def hands_out(self, name: str) -> bool:
    """
    Whether the script may reach the body of the function *name* other than by calling it by
    name: it reads `$function:K`, writes a path into the `function:` drive, asks `Get-Command`
    for it, looks a command up through `$ExecutionContext` or `$PSCmdlet`, reads
    `$MyInvocation` inside it, or does any of these where the name cannot be read. A body handed
    out this way may run wherever something runs a block, so no list of call sites is the list of
    places it runs.
    """
    return self._hands_out_every or normalize_command_name(name) in self._handed_out

def named_callers(self, body)

The calls naming the function whose body body is, or None where those are not all the calls that may run it beside unattributed_sites: body is no function's, this graph cannot be read, the function is a class method or has no name, or the script hands it out.

Expand source code Browse git

def named_callers(self, body: Node) -> list[Node] | None:
    """
    The calls naming the function whose body *body* is, or `None` where those are not all the
    calls that may run it beside `unattributed_sites`: *body* is no function's, this graph
    cannot be read, the function is a class method or has no name, or the script hands it out.
    """
    parent = body.parent
    if (
        not self._readable
        or not isinstance(parent, Ps1FunctionDefinition)
        or _is_class_method(parent)
        or not parent.name
        or self.hands_out(parent.name)
    ):
        return None
    return [site.invocation for site in self.call_sites(parent.name)]

def sites_running(self, block, attributed_only=False)

The calls that may run block, or None where they cannot all be named. A function body is run by the calls naming the function (named_callers), and, unless attributed_only, by every call in unattributed_sites. A script block is run by the & or . that invokes it where it is written, and by the ForEach-Object or Where-Object it is handed to.

Expand source code Browse git

def sites_running(self, block: Ps1ScriptBlock, attributed_only: bool = False) -> list[Node] | None:
    """
    The calls that may run *block*, or `None` where they cannot all be named. A function body is
    run by the calls naming the function (`named_callers`), and, unless *attributed_only*, by
    every call in `unattributed_sites`. A script block is run by the `&` or `.` that invokes it
    where it is written, and by the `ForEach-Object` or `Where-Object` it is handed to.
    """
    parent = block.parent
    if isinstance(parent, Ps1FunctionDefinition):
        named = self.named_callers(block)
        if named is None or attributed_only:
            return named
        return [*named, *self.unattributed_sites]
    invocation = parent.parent if isinstance(parent, Ps1CommandArgument) else parent
    if not isinstance(invocation, Ps1CommandInvocation):
        return None
    if invocation.name is block:
        return [invocation] if invocation.invocation_operator in ('&', '.') else None
    if resolve_command_name(invocation) in ('foreach-object', 'where-object'):
        return [invocation]
    return None

def may_run_a_body(self, node)

Whether evaluating node itself may run a body of this script, or code the script does not spell, which an error handler around it then guards: a script block, which runs wherever something runs it; a call that runs or makes one; or a command that dispatches to a target the source does not spell, runs code nobody can read, or names a function or keyword body this script defines. Where this graph is not the whole story, a name no cmdlet answers to may name a body code nobody can read defined; a name a cmdlet answers to is read as that cmdlet, the risk every pass here takes in exchange for reading through an iex at all.

Expand source code Browse git

def may_run_a_body(self, node: Node) -> bool:
    """
    Whether evaluating *node* itself may run a body of this script, or code the script does not
    spell, which an error handler around it then guards: a script block, which runs wherever
    something runs it; a call that runs or makes one; or a command that dispatches to a target
    the source does not spell, runs code nobody can read, or names a function or keyword body
    this script defines. Where this graph is not the whole story, a name no cmdlet answers to
    may name a body code nobody can read defined; a name a cmdlet answers to is read as that
    cmdlet, the risk every pass here takes in exchange for reading through an `iex` at all.
    """
    if isinstance(node, Ps1ScriptBlock):
        return True
    if isinstance(node, Ps1InvokeMember):
        return (
            is_scriptblock_invoke(node)
            or may_create_a_scriptblock(node)
            or is_execution_context_invoke(node)
        )
    if not isinstance(node, Ps1CommandInvocation):
        return False
    if is_opaque_dispatch(node) or runs_code_it_cannot_read(node):
        return True
    name = get_command_name(node)
    if name is None or self.definitions(name) or self.keyword_definitions(name):
        return True
    if self._readable:
        return False
    resolved = resolve_command_name(node)
    return resolved is None or resolved not in KNOWN_CMDLETS

def definitions(self, name)

Every function definition a call to name could reach, in source order.

Expand source code Browse git

def definitions(self, name: str) -> Sequence[Ps1FunctionDefinition]:
    """
    Every function definition a call to `name` could reach, in source order.
    """
    return self._definitions.get(normalize_command_name(name), ())

def keyword_definitions(self, name)

The scriptblock bodies a workflow/configuration statement binds to name, in source order. These define the same command name a function does but are not themselves a Ps1FunctionDefinition, so a caller weighing whether a name is inert reads them beside definitions: the empty function a call names may be shadowed by a workflow whose body acts.

Expand source code Browse git

def keyword_definitions(self, name: str) -> Sequence[Ps1ScriptBlock]:
    """
    The scriptblock bodies a `workflow`/`configuration` statement binds to `name`, in source
    order. These define the same command name a `function` does but are not themselves a
    `refinery.lib.scripts.ps1.model.Ps1FunctionDefinition`, so a caller weighing whether a name
    is inert reads them beside `definitions`: the empty `function` a call names may be shadowed
    by a `workflow` whose body acts.
    """
    return self._keyword_definitions.get(normalize_command_name(name), ())

def call_sites(self, name)

Every invocation of name standing in this tree, in source order, wherever it sits. This is what separates the graph from the reachability query below, which reads only the edges it can reach from the script itself.

Expand source code Browse git

def call_sites(self, name: str) -> Sequence[Ps1CallSite]:
    """
    Every invocation of `name` standing in this tree, in source order, wherever it sits. This
    is what separates the graph from the reachability query below, which reads only the edges it
    can reach from the script itself.
    """
    return self._call_sites.get(normalize_command_name(name), ())

def reachable_names(self)

Every command name some path from the script itself can reach: the names called outside any function, then the names those functions call, to a fixpoint. A function whose key is absent is called from nowhere in this tree.

An unreadable graph answers with every name it saw, defined or called, since a name reached from outside is reached by a path this cannot trace.

Expand source code Browse git

def reachable_names(self) -> frozenset[str]:
    """
    Every command name some path from the script itself can reach: the names called outside any
    function, then the names those functions call, to a fixpoint. A function whose key is absent
    is called from nowhere in this tree.

    An unreadable graph answers with every name it saw, defined or called, since a name reached
    from outside is reached by a path this cannot trace.
    """
    if not self._readable or self._hands_out_every:
        return frozenset(self._definitions) | frozenset(self._call_sites)
    calls_from: dict[str | None, set[str]] = {}
    calls_from[None] = set(self._handed_out)
    for name, sites in self._call_sites.items():
        for site in sites:
            calls_from.setdefault(site.caller, set()).add(name)
    reachable = set(calls_from.get(None, ()))
    frontier = [name for name in reachable if name in self._definitions]
    while frontier:
        for name in calls_from.get(frontier.pop(), ()):
            if name in reachable:
                continue
            reachable.add(name)
            if name in self._definitions:
                frontier.append(name)
    return frozenset(reachable)

class Ps1BodyCallers (root, calls)

The calls that may run each script block of the tree root, as Ps1CallSites asks for them: read off the call graph calls hands over, which is asked for only once a question needs it.

Expand source code Browse git

class Ps1BodyCallers:
    """
    The calls that may run each script block of the tree *root*, as
    `refinery.lib.scripts.ps1.analysis.dispatch.Ps1CallSites` asks for them: read off the call
    graph *calls* hands over, which is asked for only once a question needs it.
    """

    def __init__(self, root: Node, calls: Callable[[], Ps1CallGraph]):
        self._root = root
        self._calls = calls

    def bodies(self) -> list[Node]:
        return [node for node in self._root.walk() if isinstance(node, Ps1ScriptBlock)]

    def sites_running(self, body: Node) -> list[Node] | None:
        if not isinstance(body, Ps1ScriptBlock):
            return None
        return self._calls().sites_running(body, attributed_only=True)

    def unattributed_sites(self) -> Sequence[Node]:
        return self._calls().unattributed_sites

Methods

def bodies(self)

Expand source code Browse git

def bodies(self) -> list[Node]:
    return [node for node in self._root.walk() if isinstance(node, Ps1ScriptBlock)]

def sites_running(self, body)

Expand source code Browse git

def sites_running(self, body: Node) -> list[Node] | None:
    if not isinstance(body, Ps1ScriptBlock):
        return None
    return self._calls().sites_running(body, attributed_only=True)

def unattributed_sites(self)

Expand source code Browse git

def unattributed_sites(self) -> Sequence[Node]:
    return self._calls().unattributed_sites