rea/src/application/native/NativeValueTrace.test.ts

import { describe, expect, it } from "vitest";
import { traceNativeValues } from "./NativeValueTrace.js";
import {
  createAnalysisExecution,
  type AnalysisOperationPort,
} from "../AnalysisProvider.js";
import { ghidraFunctionDossier } from "../../domain/ghidraValues.fixture.js";
import { functionDossierSchema } from "../../domain/hopperValues.js";
import { jsonValueSchema } from "../../domain/jsonValue.js";
import { nativeValueTraceSchema } from "../../domain/native/nativeValueTrace.js";
import { AnalysisCancelledError } from "../../domain/analysisErrorCore.js";
import { ok, err } from "../../domain/result.js";

const subject = {
  path: "/fixture",
  sha256: "a".repeat(64),
  format: "mach-o" as const,
  architecture: "arm64" as const,
};
const provider = { id: "fixture", name: "Fixture", version: "1" };
const scalar = {
  kind: "constant",
  size_bytes: 4,
  location: null,
  constant_hex: "3",
};
const node = (id: string, address: string, opcode: string) => ({
  id,
  address,
  sequence: 0,
  opcode,
  is_dead: true,
  block_membership: "member",
  inputs: [scalar, scalar],
  output: scalar,
});
const analysis: AnalysisOperationPort = {
  execute: async (operation, parameters) => {
    if (operation === "resolve_native_call_targets")
      return ok(
        createAnalysisExecution(
          {
            call_site: "0x1000",
            procedure: "0x1000",
            status: "direct",
            mechanism: "direct",
            targets: [
              {
                address: "0x2000",
                procedure: "0x2000",
                status: "direct",
                basis: "provider-reference",
                references: [],
              },
            ],
            limitations: [],
          },
          provider,
          { subject },
        ),
      );
    const callee = parameters.procedure === "0x2000";
    return ok(
      createAnalysisExecution(
        jsonValueSchema.parse({
          ...functionDossierSchema.parse(ghidraFunctionDossier()),
          procedure: {
            address: callee ? "0x2000" : "0x1000",
            name: callee ? "callee" : "caller",
            classification: null,
            body: {
              available: false,
              reason:
                "The provider did not report complete function body ranges.",
            },
            signature: null,
            locals: [],
          },
          native_value_flow: {
            available: true,
            provenance: "ghidra-high-pcode",
            operations: callee
              ? [node("return", "0x2000", "RETURN")]
              : [node("call", "0x1000", "CALL")],
            def_use: [],
            effects: [],
            parameters: callee
              ? [{ ordinal: 0, name: "value", data_type: "/int" }]
              : [],
            parameter_uses: callee
              ? [{ ordinal: 0, use: "return", input_index: 1 }]
              : [],
            truncated: false,
            omitted_operations_lower_bound: 0,
            known_omitted_inputs: 0,
            known_omitted_edges: 0,
            limitations: [],
          },
        }),
        provider,
        { subject },
      ),
    );
  },
};
describe("native value parameter-use node membership", () => {
  it("retains only parameter uses whose parameter nodes fit the node budget", async () => {
    const operationCount = 3_000;
    const parameterUseCount = 12_000;
    const base = functionDossierSchema.parse(ghidraFunctionDossier());
    const procedureAddress = base.procedure.address;
    const largeFlow = {
      available: true as const,
      provenance: "ghidra-high-pcode" as const,
      operations: Array.from({ length: operationCount }, (_, index) => ({
        ...node(`operation-${String(index)}`, procedureAddress, "MULTIEQUAL"),
        inputs: [scalar, scalar, scalar, scalar],
      })),
      def_use: [],
      effects: [],
      parameters: [{ ordinal: 0, name: "value", data_type: "/int" }],
      parameter_uses: Array.from({ length: parameterUseCount }, (_, index) => ({
        ordinal: 0,
        use: `operation-${String(index % operationCount)}`,
        input_index: Math.floor(index / operationCount),
      })),
      truncated: false,
      omitted_operations_lower_bound: 0,
      known_omitted_inputs: 0,
      known_omitted_edges: 0,
      limitations: [],
    };
    const largeDossier = {
      ...base,
      native_value_flow: largeFlow,
    };
    const largeAnalysis: AnalysisOperationPort = {
      execute: async () =>
        ok(createAnalysisExecution(largeDossier, provider, { subject })),
    };

    const includedParameter = await traceNativeValues(largeAnalysis, {
      procedure: procedureAddress,
      max_nodes: 20_000,
      max_edges: 40_000,
      offset: operationCount,
      limit: 1,
    });
    if (!includedParameter.ok) throw includedParameter.error;
    const includedResult = nativeValueTraceSchema.parse(
      includedParameter.value,
    );
    expect(includedResult).toMatchObject({
      total_nodes: operationCount + 1,
      total_edges: parameterUseCount,
      nodes: [
        expect.objectContaining({
          id: `${procedureAddress}/parameter:0`,
          kind: "parameter",
        }),
      ],
      truncated: true,
    });
    expect(includedResult.edges).toHaveLength(parameterUseCount);

    const omittedParameter = await traceNativeValues(largeAnalysis, {
      procedure: procedureAddress,
      max_nodes: operationCount,
      max_edges: 40_000,
      offset: operationCount - 1,
      limit: 1,
    });
    if (!omittedParameter.ok) throw omittedParameter.error;
    const omittedResult = nativeValueTraceSchema.parse(omittedParameter.value);
    expect(omittedResult).toMatchObject({
      total_nodes: operationCount,
      total_edges: 0,
      nodes: [expect.objectContaining({ kind: "operation" })],
      edges: [],
      truncated: true,
    });
  });

  it("preserves operation IDs that collide with generated parameter IDs", async () => {
    const base = functionDossierSchema.parse(ghidraFunctionDossier());
    const address = base.procedure.address;
    const execution = createAnalysisExecution(
      {
        ...base,
        native_value_flow: {
          available: true,
          provenance: "ghidra-high-pcode",
          operations: [
            node("parameter:0", address, "COPY"),
            node("use", address, "COPY"),
          ],
          def_use: [],
          effects: [],
          parameters: [{ ordinal: 0, name: "value", data_type: "/int" }],
          parameter_uses: [{ ordinal: 0, use: "use", input_index: 1 }],
          truncated: false,
          omitted_operations_lower_bound: 0,
          known_omitted_inputs: 0,
          known_omitted_edges: 0,
          limitations: [],
        },
      },
      provider,
      { subject },
    );
    const result = await traceNativeValues(
      { execute: async () => ok(execution) },
      { procedure: address, max_nodes: 2 },
    );

    if (!result.ok) throw result.error;
    const parsedResult = nativeValueTraceSchema.parse(result.value);
    expect(parsedResult).toMatchObject({
      total_nodes: 2,
      total_edges: 1,
      edges: [
        {
          source: `${address}/parameter:0`,
          target: `${address}/use`,
          kind: "parameter-use",
        },
      ],
    });
  });
});

const nativeFlowDossier = (
  base: ReturnType<typeof functionDossierSchema.parse>,
  facts: {
    address: string;
    name: string;
    operations: ReturnType<typeof node>[];
    parameters: { ordinal: number; name: string; data_type: string }[];
  },
) => {
  const { address, name, operations, parameters } = facts;
  return jsonValueSchema.parse({
    ...base,
    procedure: {
      address,
      name,
      classification: null,
      body: {
        available: false,
        reason: "The provider did not report complete function body ranges.",
      },
      signature: null,
      locals: [],
    },
    native_value_flow: {
      available: true,
      provenance: "ghidra-high-pcode",
      operations,
      def_use: [],
      effects: [],
      parameters,
      parameter_uses: [],
      truncated: false,
      omitted_operations_lower_bound: 0,
      known_omitted_inputs: 0,
      known_omitted_edges: 0,
      limitations: [],
    },
  });
};

const callBindingAnalysis = (
  callerAddress: string,
  calleeAddress: string,
  caller: ReturnType<typeof jsonValueSchema.parse>,
  callee: ReturnType<typeof jsonValueSchema.parse>,
): AnalysisOperationPort => ({
  execute: async (operation, parameters) => {
    if (operation === "resolve_native_call_targets")
      return ok(
        createAnalysisExecution(
          {
            call_site: String(parameters.address),
            procedure: calleeAddress,
            status: "direct",
            mechanism: "direct",
            targets: [
              {
                address: calleeAddress,
                procedure: calleeAddress,
                status: "direct",
                basis: "provider-reference",
                references: [],
              },
            ],
            limitations: [],
          },
          provider,
          { subject },
        ),
      );
    if (operation !== "analyze_function")
      throw new Error(`Unexpected native trace operation: ${operation}`);
    if (
      parameters.procedure !== callerAddress &&
      parameters.procedure !== calleeAddress
    )
      throw new Error(`Unexpected procedure: ${String(parameters.procedure)}`);
    return ok(
      createAnalysisExecution(
        parameters.procedure === callerAddress ? caller : callee,
        provider,
        { subject },
      ),
    );
  },
});

describe("native value call-binding fan-out", () => {
  it("preserves binding order and edge-budget behavior for repeated callees", async () => {
    const callCount = 128;
    const callerAddress = "0x1000";
    const calleeAddress = "0x2000";
    const base = functionDossierSchema.parse(ghidraFunctionDossier());
    const caller = nativeFlowDossier(base, {
      address: callerAddress,
      name: "caller",
      operations: Array.from({ length: callCount }, (_, index) => ({
        ...node(
          `call-${index}`,
          `0x${(0x1000 + index * 4).toString(16)}`,
          "CALL",
        ),
        sequence: index,
        inputs: [scalar, scalar],
      })),
      parameters: [],
    });
    const callee = nativeFlowDossier(base, {
      address: calleeAddress,
      name: "callee",
      operations: [node("return", calleeAddress, "RETURN")],
      parameters: [{ ordinal: 0, name: "value", data_type: "/int" }],
    });
    const fanoutAnalysis = callBindingAnalysis(
      callerAddress,
      calleeAddress,
      caller,
      callee,
    );
    const expectedEdges = [
      ...Array.from({ length: callCount }, (_, index) => ({
        source: `${callerAddress}/call-${index}`,
        target: calleeAddress,
        input_index: null,
        kind: "call",
      })),
      ...Array.from({ length: callCount }, (_, index) => [
        {
          source: `${callerAddress}/call-${index}`,
          target: `${calleeAddress}/parameter:0`,
          input_index: 1,
          kind: "argument-binding",
        },
        {
          source: `${calleeAddress}/return`,
          target: `${callerAddress}/call-${index}`,
          input_index: 1,
          kind: "return-binding",
        },
      ]).flat(),
    ];
    const request = {
      procedure: callerAddress,
      max_functions: 2,
      max_call_sites: callCount,
      max_nodes: callCount + 2,
      max_edges: callCount * 3,
      limit: callCount + 2,
    };

    const complete = await traceNativeValues(fanoutAnalysis, request);
    if (!complete.ok) throw complete.error;
    const completeResult = nativeValueTraceSchema.parse(complete.value);
    const edgeShape = (edges: typeof completeResult.edges) =>
      edges.map(({ source, target, input_index, kind }) => ({
        source,
        target,
        input_index,
        kind,
      }));
    expect(completeResult).toMatchObject({
      total_nodes: callCount + 2,
      total_edges: callCount * 3,
      truncated: false,
      unknowns: [],
    });
    expect(edgeShape(completeResult.edges)).toEqual(expectedEdges);

    const capped = await traceNativeValues(fanoutAnalysis, {
      ...request,
      max_edges: callCount * 3 - 1,
    });
    if (!capped.ok) throw capped.error;
    const cappedResult = nativeValueTraceSchema.parse(capped.value);
    expect(cappedResult).toMatchObject({
      total_nodes: callCount + 2,
      total_edges: callCount * 3 - 1,
      truncated: true,
    });
    expect(edgeShape(cappedResult.edges)).toEqual(
      expectedEdges.slice(0, callCount * 3 - 1),
    );

    const nodeCapped = await traceNativeValues(fanoutAnalysis, {
      ...request,
      max_nodes: callCount + 1,
    });
    if (!nodeCapped.ok) throw nodeCapped.error;
    const nodeCappedResult = nativeValueTraceSchema.parse(nodeCapped.value);
    expect(nodeCappedResult).toMatchObject({
      total_nodes: callCount + 1,
      total_edges: callCount * 2,
      truncated: true,
      unknowns: Array.from({ length: callCount }, () => ({
        procedure: callerAddress,
        address: null,
        reason: `Parameter bindings for ${calleeAddress} are unavailable or omitted`,
      })),
    });
    expect(edgeShape(nodeCappedResult.edges)).toEqual(
      expectedEdges.filter(({ kind }) => kind !== "argument-binding"),
    );
  });
});

describe("bounded native value dependency composition", () => {
  it("reports work truncation and stable pagination without traversing ambiguous calls", async () => {
    const bounded = await traceNativeValues(analysis, {
      procedure: "0x1000",
      max_functions: 1,
    });
    expect(bounded.ok).toBe(true);
    if (bounded.ok)
      expect(bounded.value).toMatchObject({
        truncated: true,
        decompilations: 1,
      });
    const page = await traceNativeValues(analysis, {
      procedure: "0x1000",
      limit: 1,
    });
    expect(page.ok).toBe(true);
    if (page.ok)
      expect(page.value).toMatchObject({ total_nodes: 3, next_offset: 1 });
    const ambiguous = await traceNativeValues(
      {
        execute: async (operation, parameters, options) => {
          if (operation !== "resolve_native_call_targets")
            return analysis.execute(operation, parameters, options);
          return ok(
            createAnalysisExecution(
              {
                call_site: "0x1000",
                procedure: "0x1000",
                status: "ambiguous",
                mechanism: "computed",
                targets: [
                  {
                    address: "0x2000",
                    procedure: "0x2000",
                    status: "candidate",
                    basis: "provider-reference",
                    references: [],
                  },
                ],
                limitations: [],
              },
              provider,
              { subject },
            ),
          );
        },
      },
      { procedure: "0x1000" },
    );
    expect(ambiguous.ok).toBe(true);
    if (ambiguous.ok)
      expect(ambiguous.value).toMatchObject({
        decompilations: 1,
        edges: [expect.objectContaining({ status: "candidate" })],
      });
  });
  it("propagates cancellation and rejects cross-target dependencies", async () => {
    const controller = new AbortController();
    controller.abort();
    expect(
      await traceNativeValues(
        analysis,
        { procedure: "0x1000" },
        controller.signal,
      ),
    ).toMatchObject({ ok: false, error: { _tag: "AnalysisCancelledError" } });
    const cancelled = await traceNativeValues(
      {
        execute: async () =>
          err(new AnalysisCancelledError("analyze_function")),
      },
      { procedure: "0x1000" },
    );
    expect(cancelled.ok).toBe(false);
    const mismatch = await traceNativeValues(
      {
        execute: async (operation, parameters, options) => {
          const value = await analysis.execute(operation, parameters, options);
          return value.ok && parameters.procedure === "0x2000"
            ? ok({
                ...value.value,
                subject: { ...subject, sha256: "b".repeat(64) },
              })
            : value;
        },
      },
      { procedure: "0x1000" },
    );
    expect(mismatch).toMatchObject({
      ok: false,
      error: { _tag: "AnalysisOutputError" },
    });
  });
});