ui/src/plugins/com.android.HeapDumpExplorer/queries.ts

// Copyright (C) 2026 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

import type {Engine} from '../../trace_processor/engine';
import {
  BLOB_NULL,
  LONG,
  LONG_NULL,
  NUM,
  NUM_NULL,
  STR,
  STR_NULL,
  type QueryResult,
} from '../../trace_processor/query_result';
import type {
  OverviewData,
  OomeData,
  HeapInfo,
  InstanceRow,
  InstanceDetail,
  PathEntry,
  PrimOrRef,
  BitmapListRow,
  StringListRow,
  DuplicateBitmapGroup,
  DuplicateStringGroup,
  DuplicateArrayGroup,
  Field,
  ArrayElem,
  HeapDump,
} from './types';
import {fmtHex} from './format';
import {shortClassName, SQL_PREAMBLE} from './components';
import {Time} from '../../base/time';
import {mergedClassNamesSql} from '../dev.perfetto.HeapProfile/merged_class_sql';

/**
 * Reinterpret a SQL int64 as an unsigned 64-bit native pointer.
 *
 * SQLite has no unsigned integer type, so a pointer with bit 63 set arrives as
 * a negative bigint. Normalize every pointer as it enters the plugin so they
 * are consistently unsigned when compared, used as Map keys or displayed.
 */
function toNativePtr(v: bigint): bigint {
  return BigInt.asUintN(64, v);
}

export async function loadDumpsList(
  engine: Engine,
): Promise<readonly HeapDump[]> {
  const res = await engine.query(`
    SELECT
      g.upid AS upid,
      g.ts AS ts,
      coalesce(p.cmdline, p.name) AS pname,
      p.pid AS pid
    FROM heap_graph g
    JOIN process p USING (upid)
    ORDER BY g.ts ASC
  `);
  const result: HeapDump[] = [];
  for (
    const it = res.iter({
      upid: NUM,
      ts: LONG,
      pname: STR_NULL,
      pid: NUM_NULL,
    });
    it.valid();
    it.next()
  ) {
    result.push({
      upid: it.upid,
      ts: Time.fromRaw(it.ts),
      processName: it.pname,
      pid: it.pid,
    });
  }
  return result;
}

export function dumpFilterSql(dump: HeapDump, alias: string = 'o'): string {
  return (
    `${alias}.upid = ${dump.upid} ` +
    `AND ${alias}.graph_sample_ts = ${dump.ts}`
  );
}

async function requireDominatorTree(engine: Engine): Promise<void> {
  await engine.query(SQL_PREAMBLE);
}

function className(name: string | null, deobfuscated: string | null): string {
  return deobfuscated ?? name ?? '???';
}

function makeDisplay(cls: string, id: number): string {
  return `${shortClassName(cls)} ${fmtHex(id)}`;
}

function sqlEsc(s: string): string {
  return s.replace(/'/g, "''");
}

const KIND_TO_REACHABILITY: Record<string, string> = {
  KIND_WEAK_REFERENCE: 'weak',
  KIND_SOFT_REFERENCE: 'soft',
  KIND_PHANTOM_REFERENCE: 'phantom',
  KIND_FINALIZER_REFERENCE: 'finalizer',
};

function rowFromIter(it: {
  id: number;
  cls: string;
  deob: string | null;
  self_size: number;
  native_size: number;
  heap_type: string | null;
  root_type: string | null;
  dominated_size: number | null;
  dominated_native: number | null;
  dominated_obj_count: number | null;
  value_string: string | null;
  class_kind?: string;
}): InstanceRow {
  const cls = className(it.cls, it.deob);
  const retainedJava = it.dominated_size ?? it.self_size;
  const retainedNative = it.dominated_native ?? it.native_size;
  const heap = it.heap_type ?? 'default';
  const reachabilityName =
    (it.class_kind && KIND_TO_REACHABILITY[it.class_kind]) ?? 'strong';
  return {
    id: it.id,
    display: makeDisplay(cls, it.id),
    className: cls,
    isRoot: it.root_type !== null,
    rootTypeNames: it.root_type !== null ? [it.root_type] : null,
    reachabilityName,
    heap,
    shallowJava: it.self_size,
    shallowNative: it.native_size,
    retainedTotal: retainedJava + retainedNative,
    retainedCount: it.dominated_obj_count ?? 1,
    reachableSize: null,
    reachableNative: null,
    reachableCount: null,
    retainedByHeap: [{heap, java: retainedJava, native_: retainedNative}],
    str: it.value_string,
    referent: null,
  };
}

const INSTANCE_COLS = `
  o.id, c.name AS cls, c.deobfuscated_name AS deob,
  o.self_size, o.native_size, o.heap_type, o.root_type,
  d.dominated_size_bytes AS dominated_size,
  d.dominated_native_size_bytes AS dominated_native,
  d.dominated_obj_count,
  od.value_string, c.kind AS class_kind`;

const INSTANCE_ITER_SPEC = {
  id: NUM,
  cls: STR,
  deob: STR_NULL,
  self_size: NUM,
  native_size: NUM,
  heap_type: STR_NULL,
  root_type: STR_NULL,
  dominated_size: NUM_NULL,
  dominated_native: NUM_NULL,
  dominated_obj_count: NUM_NULL,
  value_string: STR_NULL,
  class_kind: STR,
};

function collectRows(res: QueryResult): InstanceRow[] {
  const rows: InstanceRow[] = [];
  for (const it = res.iter(INSTANCE_ITER_SPEC); it.valid(); it.next()) {
    rows.push(rowFromIter(it));
  }
  return rows;
}

/**
 * Batch-fetch content hashes for bitmap pixel buffers via DumpData.
 * Uses the pre-computed array_data_hash column from the trace processor,
 * avoiding expensive byte-level hashing in TypeScript.
 */
async function batchBitmapBufferHashes(
  engine: Engine,
  activeDump: HeapDump,
  bitmaps: Array<{objectId: number; nativePtr: bigint}>,
): Promise<Map<number, string>> {
  const result = new Map<number, string>();
  const dumpData = await loadBitmapDumpData(engine, activeDump);
  if (!dumpData) return result;

  // Build bufferObjId → [bitmapObjectId, ...] mapping.
  const bufToBitmaps = new Map<number, number[]>();
  for (const b of bitmaps) {
    const bufId = dumpData.bufferMap.get(b.nativePtr);
    if (bufId === undefined) continue;
    const existing = bufToBitmaps.get(bufId);
    if (existing) {
      existing.push(b.objectId);
    } else {
      bufToBitmaps.set(bufId, [b.objectId]);
    }
  }
  if (bufToBitmaps.size === 0) return result;

  const ids = [...bufToBitmaps.keys()].join(',');
  const bufRes = await engine.query(`
    SELECT o.id AS buf_id, od.array_data_hash AS hash
    FROM heap_graph_object o
    JOIN heap_graph_object_data od ON o.object_data_id = od.id
    WHERE o.id IN (${ids})
      AND od.array_data_hash IS NOT NULL
  `);
  for (
    const it = bufRes.iter({buf_id: NUM, hash: LONG_NULL});
    it.valid();
    it.next()
  ) {
    if (it.hash === null) continue;
    const hashStr = it.hash.toString();
    const bmpIds = bufToBitmaps.get(it.buf_id);
    if (bmpIds) {
      for (const id of bmpIds) {
        result.set(id, hashStr);
      }
    }
  }
  return result;
}

// Whether the trace has HPROF field values (heap_graph_primitive).
export async function hasFieldValues(engine: Engine): Promise<boolean> {
  const res = await engine.query(`SELECT 1 FROM heap_graph_primitive LIMIT 1`);
  return res.iter({}).valid();
}

// Names (deobfuscated where possible) of the classes in `dump` that may
// include other classes merged in by app optimization (e.g. R8 class
// merging). Empty unless the trace includes a deobfuscation mapping.
export async function getPotentiallyMergedClasses(
  engine: Engine,
  dump: HeapDump,
): Promise<ReadonlySet<string>> {
  const res = await engine.query(mergedClassNamesSql(dump.upid, dump.ts));
  const names = new Set<string>();
  for (const it = res.iter({name: STR}); it.valid(); it.next()) {
    names.add(it.name);
  }
  return names;
}

export async function getOverview(
  engine: Engine,
  activeDump: HeapDump,
  hasPrimitives: boolean,
): Promise<OverviewData> {
  const dumpFilter = dumpFilterSql(activeDump, 'o');
  const oomeInfo = await getOome(engine, activeDump);
  const countRes = await engine.query(`
    SELECT
      sum(iif(o.reachable, 1, 0)) AS reachable,
      sum(iif(NOT o.reachable, 1, 0)) AS unreachable,
      count(DISTINCT o.type_id) AS classes
    FROM heap_graph_object o
    WHERE ${dumpFilter}
  `);
  const countIt = countRes.iter({
    reachable: NUM,
    unreachable: NUM,
    classes: NUM,
  });
  const reachableInstanceCount = countIt.reachable;
  const unreachableInstanceCount = countIt.unreachable;
  const classCount = countIt.classes;

  // Process stats at the dump instant. Null when the trace carries no such stats.
  const statsRes = await engine.query(`
    INCLUDE PERFETTO MODULE android.oom_adjuster;
    INCLUDE PERFETTO MODULE android.memory.heap_graph.heap_graph_stats;
    SELECT
      CAST(oom_score_adj AS INT) AS score,
      android_oom_adj_score_to_bucket_name(CAST(oom_score_adj AS INT)) AS bucket,
      anon_rss_and_swap_size AS anonRssAndSwapSize,
      dmabuf_rss_size AS dmabufRssSize,
      process_uptime AS processUptime
    FROM android_heap_graph_stats
    WHERE upid = ${activeDump.upid}
      AND graph_sample_ts = ${activeDump.ts}
    LIMIT 1
  `);
  const statsIt = statsRes.iter({
    score: NUM_NULL,
    bucket: STR_NULL,
    anonRssAndSwapSize: LONG_NULL,
    dmabufRssSize: LONG_NULL,
    processUptime: LONG_NULL,
  });
  let oomScore: number | null = null;
  let oomBucket: string | null = null;
  let anonRssAndSwapSize: bigint | null = null;
  let dmabufRssSize: bigint | null = null;
  let processUptime: bigint | null = null;
  if (statsIt.valid()) {
    oomScore = statsIt.score;
    oomBucket = statsIt.bucket;
    anonRssAndSwapSize = statsIt.anonRssAndSwapSize;
    dmabufRssSize = statsIt.dmabufRssSize;
    processUptime = statsIt.processUptime;
  }

  const heapRes = await engine.query(`
    SELECT
      ifnull(o.heap_type, 'default') AS heap,
      SUM(o.self_size) AS java,
      SUM(o.native_size) AS native_
    FROM heap_graph_object o
    WHERE o.reachable != 0 AND ${dumpFilter}
    GROUP BY heap
    ORDER BY heap
  `);
  const heaps: HeapInfo[] = [];
  for (
    const it = heapRes.iter({heap: STR, java: NUM, native_: NUM});
    it.valid();
    it.next()
  ) {
    heaps.push({name: it.heap, java: it.java, native_: it.native_});
  }

  // Duplicate bitmaps grouped by pixel content hash. Each bitmap's compressed
  // DumpData buffer is hashed to detect true content duplicates rather than
  // just matching on dimensions. Skipped for proto heap graphs (no HPROF data).
  const dupRes = hasPrimitives
    ? await engine.query(`
    SELECT
      o.id,
      MAX(CASE WHEN f.field_name GLOB '*mWidth' THEN f.int_value END) AS w,
      MAX(CASE WHEN f.field_name GLOB '*mHeight' THEN f.int_value END) AS h,
      MAX(CASE WHEN f.field_name GLOB '*mNativePtr' THEN f.long_value END)
        AS native_ptr,
      o.self_size + o.native_size AS total_bytes
    FROM heap_graph_object o
    JOIN heap_graph_class c ON o.type_id = c.id
    LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
    LEFT JOIN heap_graph_primitive f ON f.field_set_id = od.field_set_id
    WHERE o.reachable != 0
      AND ${dumpFilter}
      AND (c.name = 'android.graphics.Bitmap'
        OR c.deobfuscated_name = 'android.graphics.Bitmap')
    GROUP BY o.id
    HAVING w IS NOT NULL AND h IS NOT NULL
  `)
    : null;

  // Collect bitmap info and compute content hashes.
  const bitmapInfos: Array<{
    id: number;
    w: number;
    h: number;
    totalBytes: number;
    nativePtr: bigint | null;
  }> = [];
  if (dupRes !== null) {
    for (
      const it = dupRes.iter({
        id: NUM,
        w: NUM,
        h: NUM,
        native_ptr: LONG_NULL,
        total_bytes: NUM,
      });
      it.valid();
      it.next()
    ) {
      bitmapInfos.push({
        id: it.id,
        w: it.w,
        h: it.h,
        totalBytes: it.total_bytes,
        nativePtr: it.native_ptr === null ? null : toNativePtr(it.native_ptr),
      });
    }
  }

  const hashInputs = bitmapInfos
    .filter((b) => b.nativePtr !== null)
    .map((b) => ({objectId: b.id, nativePtr: b.nativePtr!}));
  const hashes =
    hashInputs.length > 0
      ? await batchBitmapBufferHashes(engine, activeDump, hashInputs)
      : new Map<number, string>();

  const hashGroups = new Map<
    string,
    {w: number; h: number; cnt: number; total: number; min: number}
  >();
  for (const b of bitmapInfos) {
    const hash = hashes.get(b.id);
    if (!hash) continue;
    const existing = hashGroups.get(hash);
    if (existing) {
      existing.cnt++;
      existing.total += b.totalBytes;
      existing.min = Math.min(existing.min, b.totalBytes);
    } else {
      hashGroups.set(hash, {
        w: b.w,
        h: b.h,
        cnt: 1,
        total: b.totalBytes,
        min: b.totalBytes,
      });
    }
  }
  const duplicateBitmaps: DuplicateBitmapGroup[] = [];
  for (const [key, g] of hashGroups) {
    if (g.cnt < 2) continue;
    duplicateBitmaps.push({
      groupKey: key,
      width: g.w,
      height: g.h,
      count: g.cnt,
      totalBytes: g.total,
      wastedBytes: g.total - g.min,
    });
  }
  duplicateBitmaps.sort((a, b) => b.wastedBytes - a.wastedBytes);

  // Duplicate strings grouped by value. Only available for HPROF dumps
  // which populate heap_graph_object_data.value_string.
  const duplicateStrings: DuplicateStringGroup[] = [];
  if (hasPrimitives) {
    const strRes = await engine.query(`
      SELECT
        od.value_string AS value,
        COUNT(*) AS cnt,
        SUM(o.self_size) AS total_bytes,
        MIN(o.self_size) AS min_bytes
      FROM heap_graph_object o
      JOIN heap_graph_class c ON o.type_id = c.id
      LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
      WHERE o.reachable != 0
        AND ${dumpFilter}
        AND od.value_string IS NOT NULL
        AND (c.name = 'java.lang.String'
          OR c.deobfuscated_name = 'java.lang.String')
      GROUP BY od.value_string
      HAVING cnt > 1
      ORDER BY total_bytes - min_bytes DESC
    `);
    for (
      const it = strRes.iter({
        value: STR,
        cnt: NUM,
        total_bytes: NUM,
        min_bytes: NUM,
      });
      it.valid();
      it.next()
    ) {
      duplicateStrings.push({
        value: it.value,
        count: it.cnt,
        totalBytes: it.total_bytes,
        wastedBytes: it.total_bytes - it.min_bytes,
      });
    }
  }

  const duplicateArrays: DuplicateArrayGroup[] = [];
  const dupArrRes = await engine.query(`
    SELECT
      ifnull(c.deobfuscated_name, c.name) AS cls,
      CAST(od.array_data_hash AS TEXT) AS hash,
      COUNT(*) AS cnt,
      SUM(o.self_size + o.native_size) AS total_bytes,
      MIN(o.self_size + o.native_size) AS min_bytes
    FROM heap_graph_object o
    JOIN heap_graph_class c ON o.type_id = c.id
    LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
    WHERE o.reachable != 0
      AND ${dumpFilter}
      AND od.array_data_hash IS NOT NULL
    GROUP BY o.type_id, od.array_data_hash
    HAVING cnt > 1
    ORDER BY total_bytes - min_bytes DESC
  `);
  for (
    const it = dupArrRes.iter({
      cls: STR,
      hash: STR,
      cnt: NUM,
      total_bytes: NUM,
      min_bytes: NUM,
    });
    it.valid();
    it.next()
  ) {
    duplicateArrays.push({
      className: it.cls,
      arrayHash: it.hash,
      count: it.cnt,
      totalBytes: it.total_bytes,
      wastedBytes: it.total_bytes - it.min_bytes,
    });
  }

  return {
    reachableInstanceCount,
    unreachableInstanceCount,
    classCount,
    heaps,
    duplicateBitmaps:
      duplicateBitmaps.length > 0 ? duplicateBitmaps : undefined,
    duplicateStrings:
      duplicateStrings.length > 0 ? duplicateStrings : undefined,
    duplicateArrays: duplicateArrays.length > 0 ? duplicateArrays : undefined,
    oomScore,
    oomBucket,
    anonRssAndSwapSize,
    dmabufRssSize,
    processUptime,
    oome: oomeInfo?.details,
  };
}

export async function getOome(
  engine: Engine,
  activeDump: HeapDump,
): Promise<OomeData | undefined> {
  const oomeRes = await engine.query(`
    INCLUDE PERFETTO MODULE android.memory.heap_graph.oome;
    SELECT
      g.upid AS upid,
      g.ts AS ts,
      o.allocation_size_bytes AS allocationSizeBytes,
      o.free_bytes_until_oom AS freeBytesUntilOom,
      o.error_msg AS errorMsg
    FROM heap_graph g
    LEFT JOIN android_heap_graph_java_oome_details o ON o.heap_graph_id = g.id
    WHERE g.upid = ${activeDump.upid} AND g.dump_reason = 'OOME'
    LIMIT 1
  `);
  if (oomeRes.numRows() > 0) {
    const row = oomeRes.firstRow({
      upid: NUM,
      ts: LONG,
      allocationSizeBytes: LONG_NULL,
      freeBytesUntilOom: LONG_NULL,
      errorMsg: STR_NULL,
    });
    return {
      upid: row.upid,
      ts: Time.fromRaw(row.ts),
      details: {
        allocationSizeBytes: row.allocationSizeBytes ?? undefined,
        freeBytesUntilOom: row.freeBytesUntilOom ?? undefined,
        errorMsg: row.errorMsg ?? undefined,
      },
    };
  }
  return undefined;
}

/** Fetch primitive and reference field values for an object. */
async function fetchFieldValues(
  engine: Engine,
  activeDump: HeapDump,
  refSetId: number | null,
  fieldSetId: number | null,
): Promise<Field[]> {
  const fields: Field[] = [];

  if (fieldSetId !== null) {
    const fRes = await engine.query(`
      SELECT field_name, field_type,
        bool_value, byte_value, char_value, short_value,
        int_value, long_value, float_value, double_value
      FROM heap_graph_primitive
      WHERE field_set_id = ${fieldSetId}
      ORDER BY field_name
    `);
    for (
      const fit = fRes.iter({
        field_name: STR,
        field_type: STR,
        bool_value: NUM_NULL,
        byte_value: NUM_NULL,
        char_value: NUM_NULL,
        short_value: NUM_NULL,
        int_value: NUM_NULL,
        long_value: LONG_NULL,
        float_value: NUM_NULL,
        double_value: NUM_NULL,
      });
      fit.valid();
      fit.next()
    ) {
      fields.push({
        name: fit.field_name,
        typeName: fit.field_type,
        value: primFieldValue(fit),
      });
    }
  }

  if (refSetId !== null) {
    // heap_graph_class is not dump-scoped; restrict and dedup by name to
    // avoid cross-dump row multiplication when deobfuscating field_type_name.
    const rRes = await engine.query(`
      WITH class_in_dump AS (
        SELECT c.name, MIN(c.deobfuscated_name) AS deobfuscated_name
        FROM heap_graph_class c
        JOIN heap_graph_object o ON o.type_id = c.id
        WHERE ${dumpFilterSql(activeDump, 'o')}
        GROUP BY c.name
      )
      SELECT
        ifnull(r.deobfuscated_field_name, r.field_name) AS fname,
        ifnull(ct.deobfuscated_name, r.field_type_name) AS ftype,
        r.owned_id,
        c2.name AS ref_cls,
        c2.deobfuscated_name AS ref_deob,
        od2.value_string AS ref_str,
        o2.self_size AS ref_self_size,
        o2.native_size AS ref_native_size,
        d2.dominated_size_bytes AS ref_dominated_size,
        d2.dominated_native_size_bytes AS ref_dominated_native
      FROM heap_graph_reference r
      LEFT JOIN class_in_dump ct ON r.field_type_name = ct.name
      LEFT JOIN heap_graph_object o2 ON r.owned_id = o2.id
      LEFT JOIN heap_graph_class c2 ON o2.type_id = c2.id
      LEFT JOIN heap_graph_object_data od2 ON o2.object_data_id = od2.id
      LEFT JOIN heap_graph_dominator_tree d2 ON d2.id = o2.id
      WHERE r.reference_set_id = ${refSetId}
      ORDER BY fname
    `);
    for (
      const rit = rRes.iter({
        fname: STR,
        ftype: STR_NULL,
        owned_id: NUM_NULL,
        ref_cls: STR_NULL,
        ref_deob: STR_NULL,
        ref_str: STR_NULL,
        ref_self_size: NUM_NULL,
        ref_native_size: NUM_NULL,
        ref_dominated_size: NUM_NULL,
        ref_dominated_native: NUM_NULL,
      });
      rit.valid();
      rit.next()
    ) {
      if (rit.owned_id === null || rit.owned_id === 0) {
        fields.push({
          name: rit.fname,
          typeName: rit.ftype ?? '',
          value: {kind: 'prim', v: 'null'},
        });
      } else {
        const refCls = className(rit.ref_cls, rit.ref_deob);
        fields.push({
          name: rit.fname,
          typeName: rit.ftype ?? '',
          value: {
            kind: 'ref',
            id: rit.owned_id,
            display: makeDisplay(refCls, rit.owned_id),
            str: rit.ref_str,
            shallowJava: rit.ref_self_size ?? 0,
            shallowNative: rit.ref_native_size ?? 0,
            retainedJava: rit.ref_dominated_size ?? rit.ref_self_size ?? 0,
            retainedNative:
              rit.ref_dominated_native ?? rit.ref_native_size ?? 0,
          },
        });
      }
    }
  }

  return fields;
}

/** Fetch dominator-tree path from GC root to the given object. */
export async function fetchDominatorPath(
  engine: Engine,
  id: number,
): Promise<InstanceDetail['dominatorPath']> {
  return (await fetchDominatorPaths(engine, [id])).get(id) ?? null;
}

/** Fetch shortest reference path from a GC root to the given object. */
export async function fetchShortestPathFromRoot(
  engine: Engine,
  id: number,
): Promise<InstanceDetail['shortestPath']> {
  return (await fetchShortestPaths(engine, [id])).get(id) ?? null;
}

/** Batch-fetch shortest reference paths for multiple objects. */
export async function fetchShortestPaths(
  engine: Engine,
  ids: readonly number[],
): Promise<Map<number, readonly PathEntry[]>> {
  const result = new Map<number, readonly PathEntry[]>();
  if (ids.length === 0) return result;

  await requireDominatorTree(engine);

  // Walk UP the BFS tree (id→parent_id) from each target.
  const seeds = ids
    .map((id) => `SELECT ${id} AS root_node_id, 1 AS root_target_weight`)
    .join(' UNION ALL ');
  const dfsRes = await engine.query(`
    INCLUDE PERFETTO MODULE graphs.search;
    SELECT root_node_id, node_id
    FROM graph_reachable_weight_bounded_dfs!(
      (
        SELECT id AS source_node_id, parent_id AS dest_node_id,
          0 AS edge_weight
        FROM _heap_graph_object_min_depth_tree
        WHERE parent_id IS NOT NULL
      ),
      (${seeds}),
      1
    )
  `);

  const allNodeIds = new Set<number>();
  for (const it = dfsRes.iter({node_id: NUM}); it.valid(); it.next()) {
    allNodeIds.add(it.node_id);
  }
  if (allNodeIds.size === 0) return result;

  // Fetch parent_id links to reconstruct ordered chains.
  const parentRes = await engine.query(`
    SELECT id, parent_id
    FROM _heap_graph_object_min_depth_tree
    WHERE id IN (${Array.from(allNodeIds).join(',')})
  `);
  const parentMap = new Map<number, number | null>();
  for (
    const it = parentRes.iter({id: NUM, parent_id: NUM_NULL});
    it.valid();
    it.next()
  ) {
    parentMap.set(it.id, it.parent_id ?? null);
  }

  // Reconstruct ordered chains: walk parent_id from each target up, reverse.
  const pathChains = new Map<number, number[]>();
  for (const id of ids) {
    const chain: number[] = [];
    let cur: number | null = id;
    while (cur !== null && parentMap.has(cur)) {
      chain.push(cur);
      cur = parentMap.get(cur) ?? null;
    }
    if (chain.length === 0) continue;
    chain.reverse();
    pathChains.set(id, chain);
  }
  if (pathChains.size === 0) return result;

  // Batch-fetch node metadata.
  const nodeRes = await engine.query(`
    SELECT
      o.id, c.name AS cls, c.deobfuscated_name AS deob,
      o.self_size, o.native_size, o.heap_type, o.root_type,
      dt.dominated_size_bytes AS dominated_size,
      dt.dominated_native_size_bytes AS dominated_native,
      dt.dominated_obj_count,
      od.value_string, c.kind AS class_kind
    FROM heap_graph_object o
    JOIN heap_graph_class c ON o.type_id = c.id
    LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
    LEFT JOIN heap_graph_dominator_tree dt ON dt.id = o.id
    WHERE o.id IN (${Array.from(allNodeIds).join(',')})
  `);
  const nodeMap = new Map<number, InstanceRow>();
  for (
    const it = nodeRes.iter({
      id: NUM,
      cls: STR,
      deob: STR_NULL,
      self_size: NUM,
      native_size: NUM,
      heap_type: STR_NULL,
      root_type: STR_NULL,
      dominated_size: NUM_NULL,
      dominated_native: NUM_NULL,
      dominated_obj_count: NUM_NULL,
      value_string: STR_NULL,
      class_kind: STR,
    });
    it.valid();
    it.next()
  ) {
    nodeMap.set(it.id, rowFromIter(it));
  }

  // Batch-resolve field names for all parent→child edges.
  const edgePairs: string[] = [];
  for (const chain of pathChains.values()) {
    for (let i = 0; i < chain.length - 1; i++) {
      edgePairs.push(`SELECT ${chain[i]} AS pid, ${chain[i + 1]} AS cid`);
    }
  }
  const fieldMap = new Map<string, string>();
  if (edgePairs.length > 0) {
    const fRes = await engine.query(`
      SELECT e.pid, e.cid,
        ifnull(r.deobfuscated_field_name, r.field_name) AS fname
      FROM (${edgePairs.join(' UNION ALL ')}) e
      JOIN heap_graph_object o ON o.id = e.pid
      JOIN heap_graph_reference r
        ON r.reference_set_id = o.reference_set_id AND r.owned_id = e.cid
    `);
    for (
      const it = fRes.iter({pid: NUM, cid: NUM, fname: STR});
      it.valid();
      it.next()
    ) {
      fieldMap.set(`${it.pid}:${it.cid}`, '.' + it.fname);
    }
  }

  for (const [targetId, chain] of pathChains) {
    const path: PathEntry[] = [];
    for (let i = 0; i < chain.length; i++) {
      const row = nodeMap.get(chain[i]);
      if (!row) continue;
      const field =
        i < chain.length - 1
          ? (fieldMap.get(`${chain[i]}:${chain[i + 1]}`) ?? '')
          : '';
      path.push({row, field, isDominator: false});
    }
    if (path.length > 0) result.set(targetId, path);
  }
  return result;
}

/** Batch-fetch dominator-tree paths for multiple objects. */
export async function fetchDominatorPaths(
  engine: Engine,
  ids: readonly number[],
): Promise<Map<number, readonly PathEntry[]>> {
  const result = new Map<number, readonly PathEntry[]>();
  if (ids.length === 0) return result;

  await requireDominatorTree(engine);

  // Reversed edges (id→idom_id) so DFS walks UP towards the root.
  const seeds = ids
    .map((id) => `SELECT ${id} AS root_node_id, 1 AS root_target_weight`)
    .join(' UNION ALL ');
  const dfsRes = await engine.query(`
    INCLUDE PERFETTO MODULE graphs.search;
    SELECT root_node_id, node_id
    FROM graph_reachable_weight_bounded_dfs!(
      (
        SELECT id AS source_node_id, idom_id AS dest_node_id,
          0 AS edge_weight
        FROM heap_graph_dominator_tree
        WHERE idom_id IS NOT NULL
      ),
      (${seeds}),
      1
    )
  `);

  const allNodeIds = new Set<number>();
  for (const it = dfsRes.iter({node_id: NUM}); it.valid(); it.next()) {
    allNodeIds.add(it.node_id);
  }
  if (allNodeIds.size === 0) return result;

  const idomRes = await engine.query(`
    SELECT id, idom_id
    FROM heap_graph_dominator_tree
    WHERE id IN (${Array.from(allNodeIds).join(',')})
  `);
  const idomMap = new Map<number, number | null>();
  for (
    const it = idomRes.iter({id: NUM, idom_id: NUM_NULL});
    it.valid();
    it.next()
  ) {
    idomMap.set(it.id, it.idom_id ?? null);
  }

  // Reconstruct ordered chains: walk idom_id from each ID up, then reverse.
  const pathChains = new Map<number, number[]>();
  for (const id of ids) {
    const chain: number[] = [];
    let cur: number | null = id;
    while (cur !== null && idomMap.has(cur)) {
      chain.push(cur);
      cur = idomMap.get(cur) ?? null;
    }
    if (chain.length === 0) continue;
    chain.reverse();
    pathChains.set(id, chain);
  }
  if (pathChains.size === 0) return result;

  const nodeRes = await engine.query(`
    SELECT
      o.id, c.name AS cls, c.deobfuscated_name AS deob,
      o.self_size, o.native_size, o.heap_type, o.root_type,
      dt.dominated_size_bytes AS dominated_size,
      dt.dominated_native_size_bytes AS dominated_native,
      dt.dominated_obj_count,
      od.value_string, c.kind AS class_kind
    FROM heap_graph_object o
    JOIN heap_graph_class c ON o.type_id = c.id
    LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
    LEFT JOIN heap_graph_dominator_tree dt ON dt.id = o.id
    WHERE o.id IN (${Array.from(allNodeIds).join(',')})
  `);
  const nodeMap = new Map<number, InstanceRow>();
  for (
    const it = nodeRes.iter({
      id: NUM,
      cls: STR,
      deob: STR_NULL,
      self_size: NUM,
      native_size: NUM,
      heap_type: STR_NULL,
      root_type: STR_NULL,
      dominated_size: NUM_NULL,
      dominated_native: NUM_NULL,
      dominated_obj_count: NUM_NULL,
      value_string: STR_NULL,
      class_kind: STR,
    });
    it.valid();
    it.next()
  ) {
    nodeMap.set(it.id, rowFromIter(it));
  }

  const edgePairs: string[] = [];
  for (const chain of pathChains.values()) {
    for (let i = 0; i < chain.length - 1; i++) {
      edgePairs.push(`SELECT ${chain[i]} AS pid, ${chain[i + 1]} AS cid`);
    }
  }
  const fieldMap = new Map<string, string>();
  if (edgePairs.length > 0) {
    const fRes = await engine.query(`
      SELECT e.pid, e.cid,
        ifnull(r.deobfuscated_field_name, r.field_name) AS fname
      FROM (${edgePairs.join(' UNION ALL ')}) e
      JOIN heap_graph_object o ON o.id = e.pid
      JOIN heap_graph_reference r
        ON r.reference_set_id = o.reference_set_id AND r.owned_id = e.cid
    `);
    for (
      const it = fRes.iter({pid: NUM, cid: NUM, fname: STR});
      it.valid();
      it.next()
    ) {
      fieldMap.set(`${it.pid}:${it.cid}`, '.' + it.fname);
    }
  }

  for (const [targetId, chain] of pathChains) {
    const path: PathEntry[] = [];
    for (let i = 0; i < chain.length; i++) {
      const row = nodeMap.get(chain[i]);
      if (!row) continue;
      const field =
        i < chain.length - 1
          ? (fieldMap.get(`${chain[i]}:${chain[i + 1]}`) ?? '')
          : '';
      path.push({row, field, isDominator: true});
    }
    if (path.length > 0) result.set(targetId, path);
  }
  return result;
}

export async function getInstance(
  engine: Engine,
  activeDump: HeapDump,
  id: number,
): Promise<InstanceDetail | undefined> {
  await requireDominatorTree(engine);
  const objRes = await engine.query(`
    SELECT
      o.id,
      o.type_id,
      c.name AS cls,
      c.deobfuscated_name AS deob,
      c.kind AS class_kind,
      o.self_size,
      o.native_size,
      o.heap_type,
      o.root_type,
      od.value_string,
      o.reference_set_id,
      od.field_set_id,
      od.array_element_type,
      od.array_data_id,
      d.dominated_size_bytes AS dominated_size,
      d.dominated_native_size_bytes AS dominated_native,
      d.dominated_obj_count
    FROM heap_graph_object o
    JOIN heap_graph_class c ON o.type_id = c.id
    LEFT JOIN heap_graph_dominator_tree d ON d.id = o.id
    LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
    WHERE o.id = ${id}
  `);

  const oit = objRes.iter({
    id: NUM,
    type_id: NUM,
    cls: STR,
    deob: STR_NULL,
    class_kind: STR,
    self_size: NUM,
    native_size: NUM,
    heap_type: STR_NULL,
    root_type: STR_NULL,
    value_string: STR_NULL,
    reference_set_id: NUM_NULL,
    field_set_id: NUM_NULL,
    array_element_type: STR_NULL,
    array_data_id: NUM_NULL,
    dominated_size: NUM_NULL,
    dominated_native: NUM_NULL,
    dominated_obj_count: NUM_NULL,
  });
  if (!oit.valid()) return undefined;

  const fullClassName = className(oit.cls, oit.deob);
  const classKind = oit.class_kind;
  const typeId = oit.type_id;
  const refSetId = oit.reference_set_id;
  const fieldSetId = oit.field_set_id;
  const arrayDataId = oit.array_data_id;
  const arrayElementType = oit.array_element_type;

  // Class objects in the C++ parser are named "java.lang.Class<ClassName>".
  const isClassObj = fullClassName.startsWith('java.lang.Class<');
  const isArrayInstance = fullClassName.endsWith('[]');

  const reachabilityName = KIND_TO_REACHABILITY[classKind] ?? 'strong';

  const baseRow = rowFromIter({...oit, class_kind: classKind});

  // Detect referent for Reference subclasses.
  let referent: InstanceRow | null = null;
  if (reachabilityName !== 'strong' && refSetId !== null) {
    const refResult = await engine.query(`
      SELECT
        r.owned_id,
        c2.name AS ref_cls, c2.deobfuscated_name AS ref_deob,
        od2.value_string AS ref_str
      FROM heap_graph_reference r
      LEFT JOIN heap_graph_object o2 ON r.owned_id = o2.id
      LEFT JOIN heap_graph_class c2 ON o2.type_id = c2.id
      LEFT JOIN heap_graph_object_data od2 ON o2.object_data_id = od2.id
      WHERE r.reference_set_id = ${refSetId}
        AND (r.field_name GLOB '*referent'
          OR r.deobfuscated_field_name GLOB '*referent')

    `);
    const rit = refResult.iter({
      owned_id: NUM_NULL,
      ref_cls: STR_NULL,
      ref_deob: STR_NULL,
      ref_str: STR_NULL,
    });
    if (rit.valid() && rit.owned_id !== null && rit.owned_id !== 0) {
      const refCls = className(rit.ref_cls, rit.ref_deob);
      referent = {
        id: rit.owned_id,
        display: makeDisplay(refCls, rit.owned_id),
        className: refCls,
        isRoot: false,
        rootTypeNames: null,
        reachabilityName: 'strong',
        heap: baseRow.heap,
        shallowJava: 0,
        shallowNative: 0,
        retainedTotal: 0,
        retainedCount: 1,
        reachableCount: null,
        reachableSize: null,
        reachableNative: null,
        retainedByHeap: [],
        str: rit.ref_str,
        referent: null,
      };
    }
  }

  const row: InstanceRow = {...baseRow, reachabilityName, referent};

  // Look up the java.lang.Class<X> object for this class.
  let classObjRow: InstanceRow | null = null;
  {
    const classObjName = sqlEsc(`java.lang.Class<${oit.cls}>`);
    const cRes = await engine.query(`
      SELECT ${INSTANCE_COLS}
      FROM heap_graph_object o
      JOIN heap_graph_class c ON o.type_id = c.id
      LEFT JOIN heap_graph_dominator_tree d ON d.id = o.id
      LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
      WHERE ${dumpFilterSql(activeDump, 'o')}
        AND (c.name = '${classObjName}'
          OR c.deobfuscated_name = '${classObjName}')
    `);
    const rows = collectRows(cRes);
    if (rows.length > 0) classObjRow = rows[0];
  }

  const instanceFields =
    !isArrayInstance && !isClassObj
      ? await fetchFieldValues(engine, activeDump, refSetId, fieldSetId)
      : [];

  let arrayLength = 0;
  let elemTypeName: string | null = null;
  const arrayElems: ArrayElem[] = [];
  if (isArrayInstance) {
    elemTypeName = fullClassName.slice(0, -2); // "int[]" → "int"
    if (arrayDataId !== null && arrayElementType !== null) {
      // Primitive array: decode via JSON SQL function.
      const jsonRes = await engine.query(`
        SELECT __intrinsic_heap_graph_array_json(${arrayDataId}) AS data
      `);
      const jit = jsonRes.iter({data: STR_NULL});
      if (jit.valid() && jit.data !== null) {
        const values = JSON.parse(jit.data) as Array<number | string | boolean>;
        for (let i = 0; i < values.length; i++) {
          arrayElems.push({
            idx: i,
            value: {
              kind: 'prim',
              v: formatPrimValue(arrayElementType, values[i]),
            },
          });
        }
        arrayLength = values.length;
      }
    } else if (refSetId !== null) {
      // Object array elements (String[], Object[], etc.)
      // For HPROF, field_name is "[0]", "[1]", etc.
      // For perfetto heap graph, field_name may be empty or a plain name.
      // We use the row order as fallback index.
      const oaRes = await engine.query(`
        SELECT
          r.field_name AS fname,
          r.owned_id,
          c2.name AS ref_cls,
          c2.deobfuscated_name AS ref_deob,
          od2.value_string AS ref_str,
          o2.self_size AS ref_shallow,
          o2.native_size AS ref_native,
          ifnull(d2.dominated_size_bytes, o2.self_size) AS ref_retained,
          ifnull(d2.dominated_native_size_bytes, o2.native_size)
            AS ref_retained_native
        FROM heap_graph_reference r
        LEFT JOIN heap_graph_object o2 ON r.owned_id = o2.id
        LEFT JOIN heap_graph_object_data od2 ON o2.object_data_id = od2.id
        LEFT JOIN heap_graph_class c2 ON o2.type_id = c2.id
        LEFT JOIN heap_graph_dominator_tree d2 ON d2.id = o2.id
        WHERE r.reference_set_id = ${refSetId}
        ORDER BY r.id
      `);
      let seqIdx = 0;
      for (
        const oait = oaRes.iter({
          fname: STR,
          owned_id: NUM_NULL,
          ref_cls: STR_NULL,
          ref_deob: STR_NULL,
          ref_str: STR_NULL,
          ref_shallow: NUM_NULL,
          ref_native: NUM_NULL,
          ref_retained: NUM_NULL,
          ref_retained_native: NUM_NULL,
        });
        oait.valid();
        oait.next()
      ) {
        const raw = oait.fname;
        let idx: number;
        if (raw.startsWith('[') && raw.endsWith(']')) {
          idx = parseInt(raw.slice(1, raw.length - 1), 10);
        } else {
          const parsed = parseInt(raw, 10);
          idx = Number.isNaN(parsed) ? seqIdx : parsed;
        }
        seqIdx++;
        let value: PrimOrRef;
        if (oait.owned_id === null || oait.owned_id === 0) {
          value = {kind: 'prim', v: 'null'};
        } else {
          const refCls = className(oait.ref_cls, oait.ref_deob);
          value = {
            kind: 'ref',
            id: oait.owned_id,
            display: makeDisplay(refCls, oait.owned_id),
            str: oait.ref_str,
            shallowJava: oait.ref_shallow ?? 0,
            shallowNative: oait.ref_native ?? 0,
            retainedJava: oait.ref_retained ?? 0,
            retainedNative: oait.ref_retained_native ?? 0,
          };
        }
        arrayElems.push({idx, value});
        arrayLength = Math.max(arrayLength, idx + 1);
      }
    }
  }

  const revRes = await engine.query(`
    SELECT ${INSTANCE_COLS}
    FROM heap_graph_reference r
    JOIN heap_graph_object o ON r.owner_id = o.id
    JOIN heap_graph_class c ON o.type_id = c.id
    LEFT JOIN heap_graph_dominator_tree d ON d.id = o.id
    LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
    WHERE r.owned_id = ${id}
    ORDER BY (ifnull(d.dominated_size_bytes, 0)
      + ifnull(d.dominated_native_size_bytes, 0)) DESC
  `);
  const reverseRefs = collectRows(revRes);

  const domRes = await engine.query(`
    SELECT ${INSTANCE_COLS}
    FROM heap_graph_dominator_tree d
    JOIN heap_graph_object o ON d.id = o.id
    JOIN heap_graph_class c ON o.type_id = c.id
    LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
    WHERE d.idom_id = ${id}
    ORDER BY (d.dominated_size_bytes + d.dominated_native_size_bytes) DESC
  `);
  const dominated = collectRows(domRes);

  const dominatorPath = await fetchDominatorPath(engine, id);
  const shortestPath = await fetchShortestPathFromRoot(engine, id);

  const staticFields = isClassObj
    ? await fetchFieldValues(engine, activeDump, refSetId, fieldSetId)
    : [];

  let bitmap: InstanceDetail['bitmap'] = null;
  if (fullClassName === 'android.graphics.Bitmap') {
    bitmap = await extractBitmapPixels(engine, activeDump, fieldSetId);
  }
  if (bitmap === null) {
    const deobName = className(oit.cls, oit.deob);
    if (deobName === 'android.graphics.Bitmap') {
      bitmap = await extractBitmapPixels(engine, activeDump, fieldSetId);
    }
  }

  const classHierarchy = await getClassHierarchy(engine, typeId);

  return {
    row,
    isClassObj,
    isArrayInstance,
    isClassInstance: !isClassObj && !isArrayInstance,
    classObjRow,
    instanceSize: row.shallowJava,
    classHierarchy,
    staticFields,
    instanceFields,
    elemTypeName,
    arrayLength,
    arrayElems,
    bitmap,
    reverseRefs,
    dominated,
    dominatorPath,
    shortestPath,
  };
}

/**
 * Superclass chain of `startClassId`, ordered starting-class first. The DFS
 * over `id → superclass_id` is a linear chain under single inheritance, so
 * we walk it by following each row's `parent_node_id` (the DFS predecessor,
 * i.e. the subclass that discovered this ancestor).
 */
export async function getClassHierarchy(
  engine: Engine,
  startClassId: number,
): Promise<readonly string[]> {
  const res = await engine.query(`
    INCLUDE PERFETTO MODULE graphs.search;

    SELECT
      dfs.node_id AS class_id,
      dfs.parent_node_id AS child_class_id,
      coalesce(c.deobfuscated_name, c.name) AS name
    FROM graph_reachable_dfs!(
      (SELECT id AS source_node_id, superclass_id AS dest_node_id
       FROM heap_graph_class WHERE superclass_id IS NOT NULL),
      (SELECT ${startClassId} AS node_id)
    ) AS dfs
    JOIN heap_graph_class c ON c.id = dfs.node_id
  `);

  type Row = {classId: number; childClassId: number | null; className: string};
  const rows: Row[] = [];
  for (
    const it = res.iter({
      class_id: NUM,
      child_class_id: NUM_NULL,
      name: STR,
    });
    it.valid();
    it.next()
  ) {
    rows.push({
      classId: it.class_id,
      childClassId: it.child_class_id,
      className: it.name,
    });
  }

  const byChildId = new Map<number, Row>();
  let start: Row | undefined;
  for (const r of rows) {
    if (r.classId === startClassId) start = r;
    else if (r.childClassId !== null) byChildId.set(r.childClassId, r);
  }

  const chain: string[] = [];
  for (let cur = start; cur !== undefined; cur = byChildId.get(cur.classId)) {
    chain.push(cur.className);
  }
  return chain;
}

/**
 * `rootName`'s transitive subclasses that have objects in `activeDump`. The graph
 * is walked over all of heap_graph_class so it passes through abstract classes
 * (which have no objects); the object join then scopes the result to the dump.
 */
export async function getSubclassNames(
  engine: Engine,
  activeDump: HeapDump,
  rootName: string,
): Promise<readonly string[]> {
  const res = await engine.query(`
    INCLUDE PERFETTO MODULE graphs.search;
    SELECT DISTINCT coalesce(c.deobfuscated_name, c.name) AS name
    FROM graph_reachable_dfs!(
      (SELECT superclass_id AS source_node_id, id AS dest_node_id
       FROM heap_graph_class WHERE superclass_id IS NOT NULL),
      (SELECT id AS node_id FROM heap_graph_class
       WHERE coalesce(deobfuscated_name, name) = '${sqlEsc(rootName)}'
       LIMIT 1)
    ) AS dfs
    JOIN heap_graph_class c ON c.id = dfs.node_id
    JOIN heap_graph_object o ON o.type_id = c.id
    WHERE ${dumpFilterSql(activeDump, 'o')}
  `);
  const names: string[] = [];
  for (const it = res.iter({name: STR}); it.valid(); it.next()) {
    names.push(it.name);
  }
  return names;
}

export async function getRawArrayBlob(
  engine: Engine,
  objectId: number,
): Promise<Uint8Array<ArrayBuffer> | null> {
  const res = await engine.query(`
    SELECT __intrinsic_heap_graph_array(od.array_data_id) AS data
    FROM heap_graph_object o
    JOIN heap_graph_object_data od ON o.object_data_id = od.id
    WHERE o.id = ${objectId} AND od.array_data_id IS NOT NULL
  `);
  const it = res.iter({data: BLOB_NULL});
  if (it.valid() && it.data !== null) return it.data;
  return null;
}

/** Format a single JSON-decoded primitive value for display. */
function formatPrimValue(type: string, v: number | string | boolean): string {
  if (type === 'boolean') return Number(v) !== 0 ? 'true' : 'false';
  if (type === 'char') {
    const c = v as number;
    return c >= 32 && c < 127 ? `'${String.fromCharCode(c)}'` : String(c);
  }
  return String(v);
}

//
// Modern Android (API 26+) stores bitmap pixel data via a static field
// `android.graphics.Bitmap.dumpData` pointing to a `Bitmap$DumpData` instance.
// DumpData contains: format (int: 0=JPEG, 1=PNG, 2-4=WEBP), natives (long[])
// mapping native pointers, and buffers (Object[] of byte[]) with compressed
// image data. Each Bitmap instance has mNativePtr (long) used to index into
// the natives/buffers arrays.

interface BitmapDumpData {
  format: number; // 0=JPEG, 1=PNG, 2-4=WEBP
  // Map from native pointer (as bigint) to buffer object ID.
  bufferMap: Map<bigint, number>;
}

const bitmapDumpDataByDump = new WeakMap<
  HeapDump,
  Promise<BitmapDumpData | null>
>();

function loadBitmapDumpData(
  engine: Engine,
  activeDump: HeapDump,
): Promise<BitmapDumpData | null> {
  const cached = bitmapDumpDataByDump.get(activeDump);
  if (cached !== undefined) return cached;
  const promise = computeBitmapDumpData(engine, activeDump);
  bitmapDumpDataByDump.set(activeDump, promise);
  return promise;
}

async function computeBitmapDumpData(
  engine: Engine,
  activeDump: HeapDump,
): Promise<BitmapDumpData | null> {
  const classObjRes = await engine.query(`
    SELECT o.reference_set_id
    FROM heap_graph_object o
    JOIN heap_graph_class c ON o.type_id = c.id
    WHERE ${dumpFilterSql(activeDump, 'o')}
      AND (c.name LIKE '%Class<android.graphics.Bitmap>'
        OR c.deobfuscated_name LIKE '%Class<android.graphics.Bitmap>')
  `);
  const classIt = classObjRes.iter({reference_set_id: NUM_NULL});
  if (!classIt.valid() || classIt.reference_set_id === null) return null;

  // Step 2: Follow dumpData reference from the class object.
  const ddRes = await engine.query(`
    SELECT r.owned_id AS dump_data_id
    FROM heap_graph_reference r
    WHERE r.reference_set_id = ${classIt.reference_set_id}
      AND r.field_name GLOB '*dumpData'

  `);
  const ddIt = ddRes.iter({dump_data_id: NUM_NULL});
  if (!ddIt.valid() || ddIt.dump_data_id === null) return null;
  const dumpDataId = ddIt.dump_data_id;

  // Step 3: Read format from DumpData's fields.
  const fmtRes = await engine.query(`
    SELECT int_value FROM heap_graph_primitive
    WHERE field_set_id = (
      SELECT od.field_set_id FROM heap_graph_object o
      JOIN heap_graph_object_data od ON o.object_data_id = od.id
      WHERE o.id = ${dumpDataId}
    )
      AND field_name GLOB '*format'

  `);
  const fmtIt = fmtRes.iter({int_value: NUM_NULL});
  const format = fmtIt.valid() ? (fmtIt.int_value ?? 1) : 1;

  // Step 4: Get DumpData's references — natives (long[]) and buffers (Object[]).
  const refsRes = await engine.query(`
    SELECT r.field_name, r.owned_id
    FROM heap_graph_reference r
    WHERE r.reference_set_id = (SELECT reference_set_id FROM heap_graph_object WHERE id = ${dumpDataId})
      AND (r.field_name GLOB '*natives' OR r.field_name GLOB '*buffers')
  `);
  let nativesObjId: number | null = null;
  let buffersObjId: number | null = null;
  for (
    const it = refsRes.iter({field_name: STR, owned_id: NUM});
    it.valid();
    it.next()
  ) {
    if (it.field_name.endsWith('natives')) nativesObjId = it.owned_id;
    if (it.field_name.endsWith('buffers')) buffersObjId = it.owned_id;
  }
  if (nativesObjId === null || buffersObjId === null) return null;

  // Step 5: Decode natives long[] via JSON.
  const nativesRes = await engine.query(`
    SELECT __intrinsic_heap_graph_array_json(od.array_data_id) AS data
    FROM heap_graph_object o
    JOIN heap_graph_object_data od ON o.object_data_id = od.id
    WHERE o.id = ${nativesObjId}
  `);
  const nativesIt = nativesRes.iter({data: STR_NULL});
  if (!nativesIt.valid() || nativesIt.data === null) return null;
  // Native pointers need BigInt for 64-bit precision in Map lookups.
  const nativesPtrs = (JSON.parse(nativesIt.data) as string[]).map((s) =>
    toNativePtr(BigInt(s)),
  );

  // Step 6: Get buffers Object[] references — array index → byte[] object ID.
  const bufsRes = await engine.query(`
    SELECT r.field_name, r.owned_id
    FROM heap_graph_reference r
    WHERE r.reference_set_id = (SELECT reference_set_id FROM heap_graph_object WHERE id = ${buffersObjId})
    ORDER BY CAST(SUBSTR(r.field_name, 2) AS INTEGER)
  `);
  const bufferObjIds: number[] = [];
  for (
    const it = bufsRes.iter({field_name: STR, owned_id: NUM});
    it.valid();
    it.next()
  ) {
    // field_name is "[0]", "[1]", etc.
    const idx = parseInt(it.field_name.slice(1, -1), 10);
    bufferObjIds[idx] = it.owned_id;
  }

  // Step 7: Build nativePtr → buffer object ID map.
  const bufferMap = new Map<bigint, number>();
  const count = Math.min(nativesPtrs.length, bufferObjIds.length);
  for (let i = 0; i < count; i++) {
    if (bufferObjIds[i] !== undefined && bufferObjIds[i] !== 0) {
      bufferMap.set(nativesPtrs[i], bufferObjIds[i]);
    }
  }

  return {format, bufferMap};
}

const DUMP_DATA_FORMAT_NAMES: Record<number, string> = {
  0: 'jpeg',
  1: 'png',
  2: 'webp',
  3: 'webp',
  4: 'webp',
};

async function extractBitmapPixels(
  engine: Engine,
  activeDump: HeapDump,
  fieldSetId: number | null,
): Promise<InstanceDetail['bitmap']> {
  if (fieldSetId === null) return null;

  const dimRes = await engine.query(`
    SELECT field_name, int_value, long_value
    FROM heap_graph_primitive
    WHERE field_set_id = ${fieldSetId}
      AND (field_name GLOB '*mWidth' OR field_name GLOB '*mHeight'
        OR field_name GLOB '*mNativePtr')
  `);
  let width = 0;
  let height = 0;
  let nativePtr = 0n;
  for (
    const it = dimRes.iter({
      field_name: STR,
      int_value: NUM_NULL,
      long_value: LONG_NULL,
    });
    it.valid();
    it.next()
  ) {
    if (it.field_name.endsWith('mWidth')) width = it.int_value ?? 0;
    if (it.field_name.endsWith('mHeight')) height = it.int_value ?? 0;
    if (it.field_name.endsWith('mNativePtr')) {
      nativePtr = toNativePtr(it.long_value ?? 0n);
    }
  }
  if (width <= 0 || height <= 0 || nativePtr === 0n) return null;

  const dumpData = await loadBitmapDumpData(engine, activeDump);
  if (dumpData === null) return null;

  const bufferObjId = dumpData.bufferMap.get(nativePtr);
  if (bufferObjId === undefined) return null;

  const bufRes = await engine.query(`
    SELECT __intrinsic_heap_graph_array(od.array_data_id) AS data
    FROM heap_graph_object o
    JOIN heap_graph_object_data od ON o.object_data_id = od.id
    WHERE o.id = ${bufferObjId}
  `);
  const bufIt = bufRes.iter({data: BLOB_NULL});
  if (!bufIt.valid() || bufIt.data === null) return null;

  const format = DUMP_DATA_FORMAT_NAMES[dumpData.format] ?? 'png';
  return {width, height, format, data: bufIt.data};
}

export async function getBitmapPixels(
  engine: Engine,
  activeDump: HeapDump,
  objectId: number,
): Promise<InstanceDetail['bitmap']> {
  const res = await engine.query(`
    SELECT od.field_set_id
    FROM heap_graph_object o
    JOIN heap_graph_object_data od ON o.object_data_id = od.id
    WHERE o.id = ${objectId}
`);
  const row = res.maybeFirstRow({field_set_id: NUM_NULL});
  return extractBitmapPixels(engine, activeDump, row?.field_set_id ?? null);
}

export async function search(
  engine: Engine,
  activeDump: HeapDump,
  query: string,
): Promise<readonly InstanceRow[]> {
  await requireDominatorTree(engine);
  if (query.startsWith('0x') || query.startsWith('0X')) {
    const numId = parseInt(query, 16);
    if (!isNaN(numId)) {
      const res = await engine.query(`
        SELECT ${INSTANCE_COLS}
        FROM heap_graph_object o
        JOIN heap_graph_class c ON o.type_id = c.id
        LEFT JOIN heap_graph_dominator_tree d ON d.id = o.id
        LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
        WHERE o.id = ${numId}
      `);
      return collectRows(res);
    }
  }

  const escaped = query.replace(/[%_\\]/g, '\\$&').replace(/'/g, "''");
  const res = await engine.query(`
    SELECT ${INSTANCE_COLS}
    FROM heap_graph_object o
    JOIN heap_graph_class c ON o.type_id = c.id
    LEFT JOIN heap_graph_dominator_tree d ON d.id = o.id
    LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
    WHERE o.reachable != 0
      AND ${dumpFilterSql(activeDump, 'o')}
      AND (c.name LIKE '%${escaped}%' ESCAPE '\\'
        OR c.deobfuscated_name LIKE '%${escaped}%' ESCAPE '\\')
    ORDER BY (ifnull(d.dominated_size_bytes, 0)
      + ifnull(d.dominated_native_size_bytes, 0)) DESC
  `);
  return collectRows(res);
}

export async function getStringList(
  engine: Engine,
  activeDump: HeapDump,
): Promise<readonly StringListRow[]> {
  await requireDominatorTree(engine);
  const res = await engine.query(`
    SELECT
      o.id,
      od.value_string AS value,
      o.self_size,
      o.native_size,
      o.heap_type,
      c.name AS cls,
      c.deobfuscated_name AS deob,
      d.dominated_size_bytes AS dominated_size,
      d.dominated_native_size_bytes AS dominated_native
    FROM heap_graph_object o
    JOIN heap_graph_class c ON o.type_id = c.id
    LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
    LEFT JOIN heap_graph_dominator_tree d ON d.id = o.id
    WHERE o.reachable != 0
      AND ${dumpFilterSql(activeDump, 'o')}
      AND od.value_string IS NOT NULL
      AND (c.name = 'java.lang.String'
        OR c.deobfuscated_name = 'java.lang.String')
    ORDER BY (ifnull(d.dominated_size_bytes, 0)
      + ifnull(d.dominated_native_size_bytes, 0)) DESC
  `);

  const rows: StringListRow[] = [];
  for (
    const it = res.iter({
      id: NUM,
      value: STR,
      self_size: NUM,
      native_size: NUM,
      heap_type: STR_NULL,
      cls: STR,
      deob: STR_NULL,
      dominated_size: NUM_NULL,
      dominated_native: NUM_NULL,
    });
    it.valid();
    it.next()
  ) {
    const fullCls = className(it.cls, it.deob);
    rows.push({
      id: it.id,
      value: it.value,
      length: it.value.length,
      retainedSize: it.dominated_size ?? it.self_size,
      reachableSize: null,
      reachableNativeSize: null,
      reachableCount: null,
      shallowSize: it.self_size,
      nativeSize: it.native_size,
      heap: it.heap_type ?? 'default',
      className: fullCls,
      display: makeDisplay(fullCls, it.id),
    });
  }
  return rows;
}

export async function getBitmapList(
  engine: Engine,
  activeDump: HeapDump,
): Promise<readonly BitmapListRow[]> {
  await requireDominatorTree(engine);
  const dumpData = await loadBitmapDumpData(engine, activeDump);

  await engine.query(
    `INCLUDE PERFETTO MODULE android.memory.heap_graph.bitmap;`,
  );
  const res = await engine.query(`
    SELECT
      o.id,
      c.name AS cls,
      c.deobfuscated_name AS deob,
      o.self_size,
      o.native_size,
      o.heap_type,
      o.root_type,
      d.dominated_size_bytes AS dominated_size,
      d.dominated_native_size_bytes AS dominated_native,
      d.dominated_obj_count,
      od.value_string,
      c.kind AS class_kind,
      cast_int!(b.width) AS width,
      cast_int!(b.height) AS height,
      cast_int!(b.density) AS density,
      MAX(CASE WHEN f.field_name GLOB '*mNativePtr' THEN f.long_value END) AS native_ptr,
      b.bitmap_id,
      b.bitmap_storage_type,
      b.source_id,
      cast_int!(b.source_pid) AS source_pid,
      b.source_storage_type,
      b.source_process_name
    FROM heap_graph_object o
    JOIN heap_graph_class c ON o.type_id = c.id
    LEFT JOIN heap_graph_object_data od ON o.object_data_id = od.id
    LEFT JOIN heap_graph_dominator_tree d ON d.id = o.id
    LEFT JOIN heap_graph_primitive f ON f.field_set_id = od.field_set_id
    LEFT JOIN heap_graph_bitmaps b ON b.object_id = o.id
    WHERE o.reachable != 0
      AND ${dumpFilterSql(activeDump, 'o')}
      AND (c.name = 'android.graphics.Bitmap'
        OR c.deobfuscated_name = 'android.graphics.Bitmap')
    GROUP BY o.id
    ORDER BY (ifnull(d.dominated_size_bytes, 0)
      + ifnull(d.dominated_native_size_bytes, 0)) DESC
  `);

  // Collect rows and native pointers for hash lookup.
  const rawRows: Array<{
    row: InstanceRow;
    w: number;
    h: number;
    hasPixelData: boolean;
    density: number;
    nativePtr: bigint | null;
    bitmapId: bigint | null;
    storageType: string | null;
    sourceId: bigint | null;
    sourcePid: number | null;
    sourceStorageType: string | null;
    sourceProcessName: string | null;
  }> = [];
  const hashInputs: Array<{objectId: number; nativePtr: bigint}> = [];
  for (
    const it = res.iter({
      id: NUM,
      cls: STR,
      deob: STR_NULL,
      self_size: NUM,
      native_size: NUM,
      heap_type: STR_NULL,
      root_type: STR_NULL,
      dominated_size: NUM_NULL,
      dominated_native: NUM_NULL,
      dominated_obj_count: NUM_NULL,
      value_string: STR_NULL,
      class_kind: STR,
      width: NUM_NULL,
      height: NUM_NULL,
      density: NUM_NULL,
      native_ptr: LONG_NULL,
      bitmap_id: LONG_NULL,
      bitmap_storage_type: STR_NULL,
      source_id: LONG_NULL,
      source_pid: NUM_NULL,
      source_storage_type: STR_NULL,
      source_process_name: STR_NULL,
    });
    it.valid();
    it.next()
  ) {
    const w = it.width ?? 0;
    const h = it.height ?? 0;
    const nativePtr =
      it.native_ptr === null ? null : toNativePtr(it.native_ptr);
    let hasPixelData = false;
    if (dumpData !== null && nativePtr !== null && w > 0 && h > 0) {
      hasPixelData = dumpData.bufferMap.has(nativePtr);
      if (hasPixelData) {
        hashInputs.push({objectId: it.id, nativePtr});
      }
    }
    rawRows.push({
      row: rowFromIter(it),
      w,
      h,
      hasPixelData,
      density: it.density ?? 0,
      nativePtr,
      bitmapId: it.bitmap_id,
      storageType: it.bitmap_storage_type,
      sourceId: it.source_id,
      sourcePid: it.source_pid,
      sourceStorageType: it.source_storage_type,
      sourceProcessName: it.source_process_name,
    });
  }

  // Look up pre-computed content hashes for bitmaps with pixel data.
  const hashes =
    hashInputs.length > 0
      ? await batchBitmapBufferHashes(engine, activeDump, hashInputs)
      : new Map<number, string>();

  const rows: BitmapListRow[] = rawRows.map((r) => ({
    row: r.row,
    width: r.w,
    height: r.h,
    pixelCount: r.w * r.h,
    hasPixelData: r.hasPixelData,
    density: r.density,
    bufferHash: hashes.get(r.row.id) ?? null,
    storageType: r.storageType,
    bitmapId: r.bitmapId,
    sourceId: r.sourceId,
    sourcePid: r.sourcePid,
    sourceStorageType: r.sourceStorageType,
    sourceProcessName: r.sourceProcessName,
  }));
  return rows;
}

function primFieldValue(it: {
  field_type: string;
  bool_value: number | null;
  byte_value: number | null;
  char_value: number | null;
  short_value: number | null;
  int_value: number | null;
  long_value: bigint | null;
  float_value: number | null;
  double_value: number | null;
}): PrimOrRef {
  switch (it.field_type) {
    case 'boolean':
      return {
        kind: 'prim',
        v: it.bool_value !== null && it.bool_value !== 0 ? 'true' : 'false',
      };
    case 'byte':
      return {kind: 'prim', v: String(it.byte_value ?? 0)};
    case 'char': {
      const code = it.char_value ?? 0;
      const ch =
        code >= 32 && code < 127
          ? `'${String.fromCharCode(code)}'`
          : String(code);
      return {kind: 'prim', v: ch};
    }
    case 'short':
      return {kind: 'prim', v: String(it.short_value ?? 0)};
    case 'int':
      return {kind: 'prim', v: String(it.int_value ?? 0)};
    case 'long':
      return {kind: 'prim', v: String(it.long_value ?? 0)};
    case 'float':
      return {kind: 'prim', v: String(it.float_value ?? 0)};
    case 'double':
      return {kind: 'prim', v: String(it.double_value ?? 0)};
    default:
      return {kind: 'prim', v: '???'};
  }
}

//
// The _heap_graph_object_tree_aggregation table computes cumulative reachable
// sizes via a BFS tree.  The table materialisation is expensive on first access,
// so we load it asynchronously and fill in reachable columns after the initial
// render.

/** Fetch reachable (cumulative) sizes for a set of object IDs. */
async function getReachableSizes(
  engine: Engine,
  ids: readonly number[],
): Promise<Map<number, {size: number; native: number; count: number}>> {
  await engine.query(
    `INCLUDE PERFETTO MODULE android.memory.heap_graph.object_tree`,
  );
  if (ids.length === 0) return new Map();
  const res = await engine.query(`
    SELECT id,
      cumulative_size AS size,
      cumulative_native_size AS native_size,
      cumulative_count AS count
    FROM _heap_graph_object_tree_aggregation
    WHERE id IN (${ids.join(',')})
  `);
  const map = new Map<number, {size: number; native: number; count: number}>();
  for (
    const it = res.iter({id: NUM, size: NUM, native_size: NUM, count: NUM});
    it.valid();
    it.next()
  ) {
    map.set(it.id, {size: it.size, native: it.native_size, count: it.count});
  }
  return map;
}

/**
 * Enrich InstanceRow[] with reachable sizes.  Call after initial data load;
 * the caller should trigger a re-render when the returned promise resolves.
 */
export async function enrichWithReachable(
  engine: Engine,
  rows: readonly InstanceRow[],
): Promise<void> {
  const unenriched = rows.filter((r) => r.reachableSize === null);
  if (unenriched.length === 0) return;
  const ids = unenriched.map((r) => r.id);
  const map = await getReachableSizes(engine, ids);
  for (const row of unenriched) {
    const s = map.get(row.id);
    row.reachableSize = s?.size ?? 0;
    row.reachableNative = s?.native ?? 0;
    row.reachableCount = s?.count ?? 0;
  }
}

/**
 * Enrich PrimOrRef fields with reachable sizes (for ref-kind fields only).
 */
export async function enrichFieldsWithReachable(
  engine: Engine,
  fields: readonly Field[],
): Promise<void> {
  const ids: number[] = [];
  for (const f of fields) {
    if (f.value.kind === 'ref' && f.value.reachableJava === undefined) {
      ids.push(f.value.id);
    }
  }
  if (ids.length === 0) return;
  const map = await getReachableSizes(engine, ids);
  for (const f of fields) {
    if (f.value.kind === 'ref' && f.value.reachableJava === undefined) {
      const s = map.get(f.value.id);
      f.value.reachableJava = s?.size ?? 0;
      f.value.reachableNative = s?.native ?? 0;
      f.value.reachableCount = s?.count ?? 0;
    }
  }
}

/**
 * Enrich array elements with reachable sizes (for ref-kind values only).
 */
export async function enrichArrayElemsWithReachable(
  engine: Engine,
  elems: readonly ArrayElem[],
): Promise<void> {
  const ids: number[] = [];
  for (const e of elems) {
    if (e.value.kind === 'ref' && e.value.reachableJava === undefined) {
      ids.push(e.value.id);
    }
  }
  if (ids.length === 0) return;
  const map = await getReachableSizes(engine, ids);
  for (const e of elems) {
    if (e.value.kind === 'ref' && e.value.reachableJava === undefined) {
      const s = map.get(e.value.id);
      e.value.reachableJava = s?.size ?? 0;
      e.value.reachableNative = s?.native ?? 0;
      e.value.reachableCount = s?.count ?? 0;
    }
  }
}