Skip to content

armgit / rea

Public Imported from GitHub
0

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

18.8 KB
Raw Blame
import { absenceClaimable, canonicalJson } from "../comparisonSemantics.js";
import { digestCanonicalValue } from "../canonicalDigest.js";
import { compareUnicodeCodePoints } from "../unicodeCodePointOrder.js";
import type { Evidence } from "../evidence.js";
import type {
  ApplicationEdge,
  ApplicationNode,
} from "./javascriptApplicationGraphSchemas.js";
import type { JavaScriptApplicationGraph } from "./javascriptApplicationGraph.js";
import type { ApplicationVersionComparisonItem } from "./javascriptApplicationVersionComparisonSchemas.js";
import type {
  ApplicationVersionMatchingProjection,
  ApplicationVersionNodePair,
} from "./javascriptApplicationVersionKeys.js";

/** All classified entities and their complete ambiguity candidate sets. */
export interface ApplicationVersionItemProjection {
  readonly items: ApplicationVersionComparisonItem[];
}

interface ItemContext {
  readonly leftGraph: JavaScriptApplicationGraph;
  readonly rightGraph: JavaScriptApplicationGraph;
  readonly leftEvidenceId: string;
  readonly rightEvidenceId: string;
  readonly leftNativeEvidenceByDigest: ReadonlyMap<string, readonly string[]>;
  readonly rightNativeEvidenceByDigest: ReadonlyMap<string, readonly string[]>;
  readonly pairByLeft: ReadonlyMap<string, string>;
  readonly pairByRight: ReadonlyMap<string, string>;
  readonly leftRelationships: RelationshipIndex;
  readonly rightRelationships: RelationshipIndex;
}

type ItemContextInput = Omit<
  ItemContext,
  | "leftNativeEvidenceByDigest"
  | "rightNativeEvidenceByDigest"
  | "pairByLeft"
  | "pairByRight"
  | "leftRelationships"
  | "rightRelationships"
> & {
  readonly leftNativeEvidence: readonly Evidence[];
  readonly rightNativeEvidence: readonly Evidence[];
};

interface IndexedRelationship {
  readonly direction: "in" | "out";
  readonly relation: ApplicationEdge["relation"];
  readonly neighborId: string;
}

interface RelationshipIndex {
  readonly nodeById: ReadonlyMap<string, ApplicationNode>;
  readonly adjacency: ReadonlyMap<string, readonly IndexedRelationship[]>;
}

type OneSidedNode =
  | {
      readonly left: ApplicationNode;
      readonly right?: never;
      readonly candidateRightNodeIds: readonly string[];
      readonly candidateLeftNodeIds?: never;
    }
  | {
      readonly left?: never;
      readonly right: ApplicationNode;
      readonly candidateRightNodeIds?: never;
      readonly candidateLeftNodeIds: readonly string[];
    };

type ComparisonItemSemantic<
  Item extends ApplicationVersionComparisonItem =
    ApplicationVersionComparisonItem,
> = Item extends ApplicationVersionComparisonItem
  ? Omit<Item, "item_id">
  : never;

/** Classify matched, unmatched, and ambiguous nodes without inventing absence. */
export const classifyJavaScriptApplicationVersions = (
  matching: ApplicationVersionMatchingProjection,
  context: ItemContextInput,
): ApplicationVersionItemProjection => {
  const pairByLeft = new Map(
    matching.pairs.map(({ left, right }) => [
      left.node_id,
      `pair:${left.node_id}:${right.node_id}`,
    ]),
  );
  const pairByRight = new Map(
    matching.pairs.map(({ left, right }) => [
      right.node_id,
      `pair:${left.node_id}:${right.node_id}`,
    ]),
  );
  const fullContext: ItemContext = {
    leftGraph: context.leftGraph,
    rightGraph: context.rightGraph,
    leftEvidenceId: context.leftEvidenceId,
    rightEvidenceId: context.rightEvidenceId,
    leftNativeEvidenceByDigest: indexNativeEvidence(context.leftNativeEvidence),
    rightNativeEvidenceByDigest: indexNativeEvidence(
      context.rightNativeEvidence,
    ),
    pairByLeft,
    pairByRight,
    leftRelationships: indexRelationships(context.leftGraph),
    rightRelationships: indexRelationships(context.rightGraph),
  };
  const leftItems = matching.unmatchedLeft.map((node) => {
    const candidates = matching.candidatesForLeft.get(node.node_id) ?? [];
    return unmatchedItem(
      {
        left: node,
        candidateRightNodeIds: candidates,
      },
      fullContext,
    );
  });
  const rightItems = matching.unmatchedRight.map((node) => {
    const candidates = matching.candidatesForRight.get(node.node_id) ?? [];
    return unmatchedItem(
      {
        right: node,
        candidateLeftNodeIds: candidates,
      },
      fullContext,
    );
  });
  return {
    items: [
      ...matching.pairs.map((pair) => matchedItem(pair, fullContext)),
      ...leftItems,
      ...rightItems,
    ].sort((left, right) =>
      compareUnicodeCodePoints(left.item_id, right.item_id),
    ),
  };
};

const matchedItem = (
  pair: ApplicationVersionNodePair,
  context: ItemContext,
): ApplicationVersionComparisonItem => {
  const relationships = compareRelationships(pair, context);
  const dimensions = changedDimensions(pair, relationships);
  const complete = graphsComplete(context);
  const ownEvidenceUncertain =
    ownPresenceUncertain(pair.left) || ownPresenceUncertain(pair.right);
  const observedChange =
    !ownEvidenceUncertain &&
    (dimensions.includes("content") || dimensions.includes("properties"));
  // Coordinates remain comparison evidence; relocation alone is not a
  // content, property, or relationship change.
  const completeChange =
    !ownEvidenceUncertain &&
    complete &&
    dimensions.some((dimension) => dimension !== "location");
  const status: ApplicationVersionComparisonItem["status"] =
    ownEvidenceUncertain
      ? "unknown"
      : observedChange || completeChange
        ? "changed"
        : complete && !relationships.unresolved
          ? "unchanged"
          : "unknown";
  const finalDimensions = ownEvidenceUncertain
    ? []
    : status === "unknown" && !complete
      ? [...dimensions, "coverage" as const]
      : dimensions;
  const semantic: ComparisonItemSemantic = {
    status,
    node_kind: pair.left.kind,
    left_node_id: pair.left.node_id,
    right_node_id: pair.right.node_id,
    match: matchedMatch(pair),
    dimensions: finalDimensions,
    evidence_links: itemEvidenceLinks(pair.left, pair.right, context),
    limitations: [
      ...new Set([
        ...ownAvailabilityLimitations(pair.left),
        ...ownAvailabilityLimitations(pair.right),
      ]),
      ...matchLimitations(pair),
      ...(status === "unknown" && !complete
        ? [
            "Incomplete graph coverage prevents a complete node-level conclusion.",
          ]
        : []),
      ...(relationships.unresolved
        ? [
            "Relationship target identity remains unresolved; equal node kinds do not establish cross-version alignment.",
          ]
        : []),
    ],
  };
  return itemWithId(semantic);
};

const unmatchedItem = (
  member: OneSidedNode,
  context: ItemContext,
): ApplicationVersionComparisonItem =>
  member.left === undefined
    ? rightOnlyItem(member.right, member.candidateLeftNodeIds, context)
    : leftOnlyItem(member.left, member.candidateRightNodeIds, context);

const leftOnlyItem = (
  node: ApplicationNode,
  candidateNodeIds: readonly string[],
  context: ItemContext,
): ApplicationVersionComparisonItem => {
  const [firstCandidate, ...remainingCandidates] = candidateNodeIds;
  const common = {
    node_kind: node.kind,
    evidence_links: itemEvidenceLinks(node, undefined, context),
  };
  if (firstCandidate !== undefined)
    return itemWithId({
      ...common,
      status: "unknown",
      left_node_id: node.node_id,
      right_node_id: null,
      match: {
        status: "ambiguous",
        basis: "none",
        confidence: "unknown",
        candidate_left_node_ids: [],
        candidate_right_node_ids: [firstCandidate, ...remainingCandidates],
      },
      dimensions: ["availability"],
      limitations: [
        ...ownAvailabilityLimitations(node),
        AMBIGUOUS_MATCH_LIMITATION,
      ],
    });
  if (ownPresenceUncertain(node))
    return itemWithId({
      ...common,
      status: "unknown",
      left_node_id: node.node_id,
      right_node_id: null,
      match: unmatchedMatch(),
      dimensions: ["availability"],
      limitations: ownAvailabilityLimitations(node),
    });
  const absenceObserved = absenceClaimable(context.rightGraph.coverage);
  return itemWithId({
    ...common,
    status: absenceObserved ? "removed" : "unknown",
    left_node_id: node.node_id,
    right_node_id: null,
    match: unmatchedMatch(),
    dimensions: absenceObserved
      ? ["availability"]
      : ["availability", "coverage"],
    limitations: [
      ...ownAvailabilityLimitations(node),
      ...(absenceObserved ? [] : [INCOMPLETE_GRAPH_LIMITATION]),
    ],
  });
};

const rightOnlyItem = (
  node: ApplicationNode,
  candidateNodeIds: readonly string[],
  context: ItemContext,
): ApplicationVersionComparisonItem => {
  const [firstCandidate, ...remainingCandidates] = candidateNodeIds;
  const common = {
    node_kind: node.kind,
    evidence_links: itemEvidenceLinks(undefined, node, context),
  };
  if (firstCandidate !== undefined)
    return itemWithId({
      ...common,
      status: "unknown",
      left_node_id: null,
      right_node_id: node.node_id,
      match: {
        status: "ambiguous",
        basis: "none",
        confidence: "unknown",
        candidate_left_node_ids: [firstCandidate, ...remainingCandidates],
        candidate_right_node_ids: [],
      },
      dimensions: ["availability"],
      limitations: [
        ...ownAvailabilityLimitations(node),
        AMBIGUOUS_MATCH_LIMITATION,
      ],
    });
  if (ownPresenceUncertain(node))
    return itemWithId({
      ...common,
      status: "unknown",
      left_node_id: null,
      right_node_id: node.node_id,
      match: unmatchedMatch(),
      dimensions: ["availability"],
      limitations: ownAvailabilityLimitations(node),
    });
  const absenceObserved = absenceClaimable(context.leftGraph.coverage);
  return itemWithId({
    ...common,
    status: absenceObserved ? "added" : "unknown",
    left_node_id: null,
    right_node_id: node.node_id,
    match: unmatchedMatch(),
    dimensions: absenceObserved
      ? ["availability"]
      : ["availability", "coverage"],
    limitations: [
      ...ownAvailabilityLimitations(node),
      ...(absenceObserved ? [] : [INCOMPLETE_GRAPH_LIMITATION]),
    ],
  });
};

const matchedMatch = (
  pair: ApplicationVersionNodePair,
): Extract<
  ApplicationVersionComparisonItem["match"],
  { readonly status: "matched" }
> => {
  const candidates: {
    readonly candidate_left_node_ids: [];
    readonly candidate_right_node_ids: [];
  } = {
    candidate_left_node_ids: [],
    candidate_right_node_ids: [],
  };
  switch (pair.basis) {
    case "exact-node-identity":
    case "exact-content-digest":
    case "exact-module-source-digest":
      return {
        status: "matched",
        basis: pair.basis,
        confidence: "exact",
        ...candidates,
      };
    case "source-map-identity":
      return {
        status: "matched",
        basis: pair.basis,
        confidence: "high",
        ...candidates,
      };
    case "structural-fingerprint":
    case "semantic-key":
      return {
        status: "matched",
        basis: pair.basis,
        confidence: "medium",
        ...candidates,
      };
  }
};

const unmatchedMatch = (): Extract<
  ApplicationVersionComparisonItem["match"],
  { readonly status: "unmatched" }
> => ({
  status: "unmatched",
  basis: "none",
  confidence: "unknown",
  candidate_left_node_ids: [],
  candidate_right_node_ids: [],
});

const AMBIGUOUS_MATCH_LIMITATION =
  "Multiple nodes share the same permitted match key; no cross-version pair was selected.";
const INCOMPLETE_GRAPH_LIMITATION =
  "The opposite graph is incomplete, so an unmatched node cannot be classified as added or removed.";

const ownPresenceUncertain = (node: ApplicationNode): boolean =>
  node.observations.every(
    ({ evidence }) =>
      evidence.state === "unknown" || evidence.state === "unavailable",
  );

const ownAvailabilityLimitations = (node: ApplicationNode): string[] => {
  const limitations = new Set<string>();
  for (const { evidence } of node.observations)
    if (evidence.state === "unknown" || evidence.state === "unavailable")
      for (const limitation of evidence.limitations)
        limitations.add(limitation);
  return [...limitations].sort(compareUnicodeCodePoints);
};

const changedDimensions = (
  pair: ApplicationVersionNodePair,
  relationships: RelationshipComparison,
): ApplicationVersionComparisonItem["dimensions"] => {
  const dimensions: ApplicationVersionComparisonItem["dimensions"] = [];
  const leftContent = contentIdentity(pair.left);
  const rightContent = contentIdentity(pair.right);
  if (
    leftContent !== null &&
    rightContent !== null &&
    leftContent !== rightContent
  )
    dimensions.push("content");
  if (
    canonicalJson(locations(pair.left)) !== canonicalJson(locations(pair.right))
  )
    dimensions.push("location");
  if (
    canonicalJson(properties(pair.left)) !==
    canonicalJson(properties(pair.right))
  )
    dimensions.push("properties");
  if (relationships.different) dimensions.push("relationships");
  return dimensions;
};

const contentIdentity = (node: ApplicationNode): string | null => {
  if (node.identity.strategy === "content-digest")
    return `content:${node.identity.sha256}`;
  if (node.kind === "javascript-module")
    return stringProperty(node, "source_sha256");
  if (
    node.kind === "source-module" &&
    node.identity.strategy === "source-map-original"
  )
    return node.identity.source_sha256;
  return null;
};

const locations = (node: ApplicationNode) =>
  node.observations
    .map(({ evidence }) =>
      evidence.location.available ? evidence.location.value : evidence.location,
    )
    .sort((left, right) =>
      compareUnicodeCodePoints(canonicalJson(left), canonicalJson(right)),
    );

const properties = (node: ApplicationNode) =>
  node.observations
    .map(({ label, properties: values, source_map_reference }) => ({
      label,
      properties: values,
      source_map_reference,
    }))
    .sort((left, right) =>
      compareUnicodeCodePoints(canonicalJson(left), canonicalJson(right)),
    );

const indexRelationships = (
  graph: JavaScriptApplicationGraph,
): RelationshipIndex => {
  const adjacency = new Map<string, IndexedRelationship[]>();
  const add = (nodeId: string, relationship: IndexedRelationship): void => {
    const existing = adjacency.get(nodeId);
    if (existing === undefined) adjacency.set(nodeId, [relationship]);
    else existing.push(relationship);
  };
  for (const edge of graph.edges) {
    add(edge.source_node_id, {
      direction: "out",
      relation: edge.relation,
      neighborId: edge.target_node_id,
    });
    if (edge.target_node_id !== edge.source_node_id)
      add(edge.target_node_id, {
        direction: "in",
        relation: edge.relation,
        neighborId: edge.source_node_id,
      });
  }
  return {
    nodeById: new Map(graph.nodes.map((value) => [value.node_id, value])),
    adjacency,
  };
};

/** Positive topology differences and unresolved neighbor identity are independent facts. */
interface RelationshipComparison {
  readonly different: boolean;
  readonly unresolved: boolean;
}

const compareRelationships = (
  pair: ApplicationVersionNodePair,
  context: ItemContext,
): RelationshipComparison => {
  const left = relationshipFacts(pair.left, "left", context);
  const right = relationshipFacts(pair.right, "right", context);
  return {
    different:
      left.paired !== right.paired ||
      left.unpairedShape !== right.unpairedShape,
    unresolved: left.unresolved || right.unresolved,
  };
};

const relationshipFacts = (
  node: ApplicationNode,
  side: "left" | "right",
  context: ItemContext,
): {
  readonly paired: string;
  readonly unpairedShape: string;
  readonly unresolved: boolean;
} => {
  const { nodeById, adjacency } =
    side === "left" ? context.leftRelationships : context.rightRelationships;
  const paired = side === "left" ? context.pairByLeft : context.pairByRight;
  const matched: string[] = [];
  const unpaired: string[] = [];
  for (const { direction, relation, neighborId } of adjacency.get(
    node.node_id,
  ) ?? []) {
    const mapped = paired.get(neighborId);
    if (mapped !== undefined)
      matched.push(`${direction}\0${relation}\0${mapped}`);
    else
      unpaired.push(
        `${direction}\0${relation}\0${nodeById.get(neighborId)?.kind ?? "unknown"}`,
      );
  }
  return {
    paired: canonicalJson(matched.sort(compareUnicodeCodePoints)),
    unpairedShape: canonicalJson(unpaired.sort(compareUnicodeCodePoints)),
    unresolved: unpaired.length > 0,
  };
};

const itemEvidenceLinks = (
  left: ApplicationNode | undefined,
  right: ApplicationNode | undefined,
  context: ItemContext,
): string[] =>
  [
    ...new Set([
      context.leftEvidenceId,
      context.rightEvidenceId,
      ...nativeLinks(left, context.leftNativeEvidenceByDigest),
      ...nativeLinks(right, context.rightNativeEvidenceByDigest),
    ]),
  ].sort(compareUnicodeCodePoints);

const nativeLinks = (
  node: ApplicationNode | undefined,
  evidenceByDigest: ReadonlyMap<string, readonly string[]>,
): readonly string[] => {
  const identity = node === undefined ? null : contentIdentity(node);
  if (identity === null) return [];
  const digest = identity.replace(/^content:/u, "");
  return evidenceByDigest.get(digest) ?? [];
};

const indexNativeEvidence = (
  evidence: readonly Evidence[],
): ReadonlyMap<string, readonly string[]> => {
  const evidenceByDigest = new Map<string, string[]>();
  for (const { evidence_id: id, subject } of evidence) {
    const digest = subject?.digest.sha256;
    if (digest === undefined) continue;
    const ids = evidenceByDigest.get(digest);
    if (ids === undefined) evidenceByDigest.set(digest, [id]);
    else ids.push(id);
  }
  return evidenceByDigest;
};

const matchLimitations = (pair: ApplicationVersionNodePair): string[] => [
  ...(pair.basis === "structural-fingerprint"
    ? [
        "Structural fingerprint equality is rename-resistant inference; it is not byte identity or proof of semantic equivalence.",
      ]
    : []),
  ...(pair.basis === "source-map-identity"
    ? [
        "Source-map original names identify a candidate source lineage; changed or unavailable source content remains explicit.",
      ]
    : []),
  ...(pair.basis === "semantic-key"
    ? [
        "Semantic-key pairing is a deterministic inference and is never promoted to exact identity.",
      ]
    : []),
];

const itemWithId = <Semantic extends ComparisonItemSemantic>(
  semantic: Semantic,
): Semantic & { readonly item_id: string } => ({
  ...semantic,
  item_id: `javc_item_${digestCanonicalValue(semantic, "Application version item")}`,
});

const stringProperty = (node: ApplicationNode, key: string): string | null => {
  const values = [
    ...new Set(
      node.observations
        .map(({ properties: values }) => values[key])
        .filter((value): value is string => typeof value === "string"),
    ),
  ];
  return values.length === 1 ? (values[0] ?? null) : null;
};

const graphsComplete = (context: ItemContext): boolean =>
  absenceClaimable(context.leftGraph.coverage) &&
  absenceClaimable(context.rightGraph.coverage);