Skip to content

armgit / rea

Public Imported from GitHub
0

Reverse engineer anything with agents, from app behavior down to native binaries.

14.5 KB
Raw Blame
import * as t from "@babel/types";
import type {
  JavaScriptSemanticAnalysisState,
  JavaScriptSemanticBindingState,
} from "./javascriptSemanticState.js";
import {
  semanticPropertyPathKeyMatches,
  type JavaScriptSemanticPropertyPath,
} from "./javascriptSemanticPropertyPaths.js";
import { unwrapJavaScriptExpression } from "./javascriptAstValues.js";
import {
  semanticObjectPropertyReferences,
  semanticArrayPropertyReferences,
  type JavaScriptSemanticObjectReference,
} from "./javascriptSemanticObjectReferences.js";
import { SEMANTIC_ALIAS_SELECTION_LIMIT } from "./javascriptSemanticResourceLimits.js";
import {
  semanticBindingAtRead,
  semanticDefiniteEffectPrecedesReference,
  semanticEffectTiming,
  semanticTopLevelEffectFollowsCapture,
} from "./javascriptSemanticMutationInitializers.js";
import {
  semanticCopiedReferencePath,
  semanticReferenceIterationUnknown,
  semanticReferenceSourcesInactive,
} from "./javascriptSemanticReferenceSources.js";
import { semanticStoredSourceSelection } from "./javascriptSemanticIterationSources.js";
import {
  semanticAliasSelectionChoices,
  type SemanticAliasSelectionPath,
} from "./javascriptSemanticAliasSelections.js";

export interface SemanticCapturedSelection {
  readonly at: t.Node;
  readonly depth: number;
  /** Object spread/rest reads only an own enumerable slot at this depth. */
  readonly ownEnumerable?: true;
}

/** The next origin crossed owns a repeated copy boundary at the same depth. */
export const semanticNormalizeCapturedSelections = (
  selections: readonly SemanticCapturedSelection[] | undefined,
  pathLength?: number,
): readonly SemanticCapturedSelection[] | undefined => {
  const byDepth = new Map<number, SemanticCapturedSelection>();
  for (const capture of selections ?? [])
    if (
      capture.depth > 0 &&
      (pathLength === undefined || capture.depth <= pathLength)
    )
      byDepth.set(capture.depth, capture);
  const normalized = [...byDepth.values()].sort(
    (left, right) => left.depth - right.depth,
  );
  return normalized.length ? normalized : undefined;
};

/** Keep capture boundaries aligned as a selected prefix is added or consumed. */
export const semanticShiftCapturedSelections = (
  selections: readonly SemanticCapturedSelection[] | undefined,
  delta: number,
): readonly SemanticCapturedSelection[] | undefined => {
  const shifted = selections?.flatMap((selection) =>
    selection.depth + delta > 0
      ? [{ ...selection, depth: selection.depth + delta }]
      : [],
  );
  return semanticNormalizeCapturedSelections(shifted);
};

/** Record an object/array property selected when a shallow copy was made. */
export const semanticCapturedSelectionsAfterPropertyRead = (
  selections: readonly SemanticCapturedSelection[] | undefined,
  source: Pick<
    JavaScriptSemanticObjectReference,
    "path" | "capturedSelectionAt" | "ownEnumerable"
  >,
): readonly SemanticCapturedSelection[] => [
  ...(semanticShiftCapturedSelections(selections, source.path.length - 1) ??
    []),
  ...(source.capturedSelectionAt === undefined
    ? []
    : [
        {
          at: source.capturedSelectionAt,
          depth: source.path.length,
          ...(source.ownEnumerable ? { ownEnumerable: true as const } : {}),
        },
      ]),
];

interface ProjectedSource {
  readonly node: t.Node;
  readonly path: SemanticAliasSelectionPath;
  readonly capturedSelections?: readonly SemanticCapturedSelection[];
}

/** A fresh parent does not prove a descendant receiver is a fresh allocation. */
const hasFreshProjectedReceiver = (
  root: t.Node,
  path: JavaScriptSemanticPropertyPath,
  state: JavaScriptSemanticAnalysisState,
): boolean => {
  const pending = [{ node: root, path }];
  const examined = new WeakMap<t.Node, Set<string>>();
  let selections = 0;
  while (pending.length > 0) {
    const current = pending.pop()!;
    const node = unwrapJavaScriptExpression(current.node).node;
    const key = JSON.stringify(current.path);
    const paths = examined.get(node) ?? new Set<string>();
    if (paths.has(key)) return false;
    paths.add(key);
    examined.set(node, paths);
    if (++selections > SEMANTIC_ALIAS_SELECTION_LIMIT) {
      state.valueResourceLimits.add("alias-selections");
      return false;
    }
    if (current.path.length === 0) {
      if (
        !t.isObjectExpression(node) &&
        !t.isArrayExpression(node) &&
        !t.isFunction(node) &&
        !t.isClassExpression(node)
      )
        return false;
      continue;
    }
    const [selected, ...remaining] = current.path;
    const sources = t.isObjectExpression(node)
      ? semanticObjectPropertyReferences(node, [selected!], state)
      : t.isArrayExpression(node)
        ? semanticArrayPropertyReferences(node, [selected!])
        : [];
    if (sources.length === 0) return false;
    if (
      selections + pending.length + sources.length >
      SEMANTIC_ALIAS_SELECTION_LIMIT
    ) {
      state.valueResourceLimits.add("alias-selections");
      return false;
    }
    pending.push(
      ...sources.map((source) => ({
        node: source.node,
        path: [...source.path, ...remaining],
      })),
    );
  }
  return true;
};

/** Select retained assignment and copy sources at one projected member read. */
export const semanticProjectedSourcesAtRead = (
  ...arguments_: Parameters<typeof semanticProjectedSourceFactsAtRead>
): readonly ProjectedSource[] | undefined =>
  semanticProjectedSourceFactsAtRead(...arguments_)?.sources;

/** Retain the selected receiver's possible owners after its current value becomes opaque. */
export const semanticProjectedSourceEligibilityAtRead = (
  binding: JavaScriptSemanticBindingState,
  reference: t.Node,
  path: SemanticAliasSelectionPath,
  state: JavaScriptSemanticAnalysisState,
  memberReadAt: t.Node = reference,
  capturedSelections: readonly SemanticCapturedSelection[] = [],
): readonly ProjectedSource[] | undefined =>
  projectedSourceFactsAtRead(
    binding,
    reference,
    path,
    state,
    false,
    memberReadAt,
    capturedSelections,
    true,
  )?.sources;

/** Keep imported origins subject to the same selected writes as other values. */
export const semanticProjectedSourceFactsAtRead = (
  ...arguments_: Parameters<typeof projectedSourceFactsAtRead>
): ReturnType<typeof projectedSourceFactsAtRead> =>
  projectedSourceFactsAtRead(...arguments_);

const projectedSourceFactsAtRead = (
  binding: JavaScriptSemanticBindingState,
  reference: t.Node,
  path: SemanticAliasSelectionPath,
  state: JavaScriptSemanticAnalysisState,
  includeUnknown: boolean,
  memberReadAt: t.Node = reference,
  capturedSelections: readonly SemanticCapturedSelection[] = [],
  retainEligibility = false,
):
  | {
      readonly sources: readonly ProjectedSource[];
      readonly retainsOrigin: boolean;
    }
  | undefined => {
  const read = semanticBindingAtRead(binding, reference, state.parentsByNode);
  const captured = [
    ...read.binding.initializers,
    ...read.binding.referenceInitializers,
  ];
  const normalizedCaptures = semanticNormalizeCapturedSelections(
    capturedSelections,
    path.length,
  );
  const captureForDepth = (depth: number): t.Node | undefined =>
    normalizedCaptures?.find((capture) => capture.depth >= depth)?.at;
  const selectedAt = (depth: number): t.Node =>
    captureForDepth(depth) ?? memberReadAt;
  const samePrefix = (
    prefix: JavaScriptSemanticBindingState["memberWrites"][number],
    effect: JavaScriptSemanticBindingState["memberWrites"][number],
  ): boolean =>
    prefix.path.length < effect.path.length &&
    prefix.path.every(
      (key, index) =>
        key !== null &&
        typeof key !== "object" &&
        effect.path[index] !== null &&
        typeof effect.path[index] !== "object" &&
        String(key) === String(effect.path[index]),
    );
  const targetsReplacedPrefix = (
    effect: JavaScriptSemanticBindingState["memberWrites"][number],
  ): boolean =>
    capturedSelections.length > 0 &&
    binding.memberWrites.some((replacement) => {
      const capture = captureForDepth(replacement.path.length);
      const receiverAt = effect.receiverAt ?? effect.node;
      return (
        capture !== undefined &&
        receiverAt !== undefined &&
        replacement.receiverIdentity === "definite" &&
        t.isAssignmentExpression(replacement.node, { operator: "=" }) &&
        samePrefix(replacement, effect) &&
        semanticTopLevelEffectFollowsCapture(
          capture,
          replacement.node,
          state.parentsByNode,
        ) &&
        semanticDefiniteEffectPrecedesReference(
          replacement.node,
          receiverAt,
          state.parentsByNode,
        ) &&
        hasFreshProjectedReceiver(
          replacement.node.right,
          effect.path.slice(replacement.path.length, -1),
          state,
        )
      );
    });
  const matches = (
    effect: JavaScriptSemanticBindingState["memberWrites"][number],
  ) =>
    (effect.receiverInitializers === undefined ||
      effect.receiverInitializers.length === 0 ||
      captured.length === 0 ||
      effect.receiverInitializers.some((receiver) =>
        captured.some(
          (source) =>
            source.node === receiver.node &&
            JSON.stringify(source.projection) ===
              JSON.stringify(receiver.projection),
        ),
      )) &&
    path.length > 0 &&
    effect.path.length <= path.length &&
    effect.path.every((key, index) => {
      const selected = path[index];
      return (
        selected !== undefined &&
        semanticAliasSelectionChoices(selected).some(
          (choice) =>
            choice === null ||
            typeof choice === "object" ||
            semanticPropertyPathKeyMatches(key, String(choice)),
        )
      );
    }) &&
    semanticEffectTiming(selectedAt(effect.path.length), effect.node, state) !==
      "after" &&
    !targetsReplacedPrefix(effect);
  const writes = binding.memberWrites.filter(matches);
  let replacement:
    | JavaScriptSemanticBindingState["memberWrites"][number]
    | undefined;
  for (const effect of writes) {
    if (
      effect.receiverIdentity === "definite" &&
      t.isAssignmentExpression(effect.node, { operator: "=" }) &&
      effect.path.every(
        (key, index) =>
          key !== null &&
          typeof key !== "object" &&
          path[index] !== null &&
          typeof path[index] !== "object" &&
          String(key) === String(path[index]),
      ) &&
      semanticDefiniteEffectPrecedesReference(
        effect.node,
        selectedAt(effect.path.length),
        state.parentsByNode,
      ) &&
      (replacement === undefined ||
        semanticDefiniteEffectPrecedesReference(
          replacement.node!,
          effect.node,
          state.parentsByNode,
        ) ||
        (replacement.node === effect.node &&
          (replacement.assignedSources?.[0]?.target?.start ?? -1) <
            (effect.assignedSources?.[0]?.target?.start ?? -1)))
    )
      replacement = effect;
  }
  const superseded = (
    effect: JavaScriptSemanticBindingState["memberWrites"][number],
  ) =>
    replacement !== undefined &&
    effect.node !== undefined &&
    effect !== replacement &&
    (semanticEffectTiming(replacement.node!, effect.node, state) === "before" ||
      (effect.node === replacement.node &&
        (effect.assignedSources?.[0]?.target?.start ?? -1) <
          (replacement.assignedSources?.[0]?.target?.start ?? -1)));
  if (
    includeUnknown &&
    binding.escapedPaths.some(
      (effect) => matches(effect) && !superseded(effect),
    )
  )
    return undefined;
  const sources: ProjectedSource[] = [];
  for (const effect of writes) {
    if (!retainEligibility && superseded(effect)) continue;
    if (
      !t.isAssignmentExpression(effect.node) ||
      !["=", "||=", "&&=", "??="].includes(effect.node.operator)
    ) {
      if (includeUnknown) return undefined;
      continue;
    }
    if (effect.assignedSources === undefined) {
      if (includeUnknown) return undefined;
      continue;
    }
    const remaining = path.slice(effect.path.length);
    for (const source of effect.assignedSources) {
      if (semanticReferenceIterationUnknown(source, state)) return undefined;
      if (semanticReferenceSourcesInactive(source, state)) continue;
      const [key, ...suffix] = remaining;
      for (const choice of key === undefined
        ? [undefined]
        : semanticAliasSelectionChoices(key)) {
        const selection = semanticStoredSourceSelection(
          source,
          choice === undefined ? [] : [choice],
        );
        if (selection !== null)
          sources.push({
            node: source.node,
            path: [...selection.projection, ...suffix],
            ...(selection.capturedSelectionDepth === undefined
              ? {}
              : {
                  capturedSelections: [
                    {
                      at: source.node,
                      depth: selection.capturedSelectionDepth,
                      ...(selection.ownEnumerable
                        ? { ownEnumerable: true as const }
                        : {}),
                    },
                  ],
                }),
          });
      }
    }
  }
  if (!retainEligibility && replacement !== undefined)
    return { sources, retainsOrigin: false };
  for (const initializer of read.binding.initializers) {
    if (semanticReferenceIterationUnknown(initializer, state)) return undefined;
    if (semanticReferenceSourcesInactive(initializer, state)) continue;
    sources.push({
      node: initializer.node,
      path: [...initializer.projection, ...path],
    });
  }
  for (const initializer of read.binding.referenceInitializers) {
    if (semanticReferenceIterationUnknown(initializer, state)) return undefined;
    if (semanticReferenceSourcesInactive(initializer, state)) continue;
    const [key, ...suffix] = path;
    for (const choice of key === undefined
      ? [undefined]
      : semanticAliasSelectionChoices(key)) {
      const projection = semanticCopiedReferencePath(
        initializer,
        choice === undefined ? [] : [choice],
        "identity",
      );
      if (projection !== null)
        sources.push({
          node: initializer.node,
          path: [...projection, ...suffix],
          capturedSelections:
            initializer.copyProjectionOffset === undefined
              ? []
              : [
                  {
                    at: initializer.node,
                    depth: projection.length + suffix.length - path.length + 1,
                    ...(initializer.copyKind === "object-rest"
                      ? { ownEnumerable: true as const }
                      : {}),
                  },
                ],
        });
    }
  }
  return { sources, retainsOrigin: true };
};