import { unzip, unzipChunkSegments } from '@gmod/bgzf-filehandle' import { SharedReadCache } from '@gmod/shared-read-cache' import { LocalFile, RemoteFile } from 'generic-filehandle2' import CSI from './csi.ts' import TBI from './tbi.ts' import { chunkBufferOffset, forEachLinePiece, optimizeChunks, sliceSegments, throwIfAborted, } from './util.ts' import type Chunk from './chunk.ts' import type IndexFile from './indexFile.ts' import type { Options } from './indexFile.ts' import type { BgzfWorkerPool, ChunkSegments } from '@gmod/bgzf-filehandle' import type { Budget } from '@gmod/shared-read-cache' import type { GenericFilehandle } from 'generic-filehandle2' const TAB = 9 const NEWLINE = 10 const CARRIAGE_RETURN = 13 const SEMICOLON = 59 const LESS_THAN = 60 const GREATER_THAN = 62 // Ceiling on how many chunk reads getLines keeps in flight ahead of the one it // is parsing. Six is the HTTP/1.1 per-host connection cap browsers enforce, so // going much above it buys nothing on the transport that matters. const MAX_READ_AHEAD_CHUNKS = 6 // SYNC: ~/src/gmod/bam-js/src/bamFile.ts DEFAULT_MAX_CACHE_BYTES // // We fetch compressed and cache decompressed, and an entry is a whole chunk, so // entry count says nothing about memory. How little is easy to underestimate: // a dense VCF (test/data/1kg.chr1.subset.vcf.gz — 213MB over 600kb of chr1) // has single index bins of 17MB compressed, 120MB decompressed. Panning it // under the old 80-entry cache peaked at 2GB RSS. // // That 120MB figure is also why this is no longer 100MB. A budget below one // query's working set does not cache less, it caches NOTHING: each entry is // evicted before the next pan can reuse it, so the hit rate is zero and the // decompress is paid again every time. On that same fixture, a six-window 50kb // pan measured 17 refills out of 17 — a total miss — at 100MB, against 0 at // 800MB, and 2596ms against 600ms. The working set plateaus at 497MB held, so // 1GB clears it with headroom and nothing above 800MB buys anything. // // Affordable as a ceiling only because of the idle timeout below: it is a peak // under panning, not a level a parked consumer holds. A small file is // unaffected either way, this being a ceiling and not an allocation. const DEFAULT_CHUNK_CACHE_BYTES = 1024 * 2 ** 20 // SYNC: ~/src/gmod/bam-js/src/bamFile.ts DEFAULT_CACHE_IDLE_TIMEOUT_MS // // Drop a chunk nothing has looked at for three minutes. The budget above is // only applied when a read settles, so it does nothing at all for a consumer // sitting still — and a genome browser holds one of these per track for as long // as the track is open. Timed from the last read, not the fetch, so panning // back and forth over one region never expires it. const DEFAULT_CHUNK_CACHE_IDLE_TIMEOUT_MS = 3 * 60 * 1000 type GetLinesCallback = ( line: string, fileOffset: number, start: number, end: number, ) => void interface GetLinesOpts { signal?: AbortSignal lineCallback: GetLinesCallback /** * Called as the chunks covering the query are fetched, with cumulative * downloaded bytes and the total bytes to fetch. One tick per chunk — the run * of BGZF blocks the index resolves a query to — including instant ticks for * chunks already cached. That is the natural unit here, since chunk byte * sizes are known up front from the index, which is what lets a caller render * a determinate progress bar rather than a spinner. */ onProgress?: (bytesDownloaded: number, totalBytes?: number) => void } // The decompressed chunk plus its block offsets, as @gmod/bgzf-filehandle // returns them: cpositions/dpositions are Float64Arrays, which is what the // wasm decompressor produces, and only indexed reads and `.length` are used // here. Taken from the package rather than restated so the two can't drift. type ReadChunk = ChunkSegments function resolveFilehandle( filehandle?: GenericFilehandle, path?: string, url?: string, ) { if (filehandle) { return filehandle } if (path) { return new LocalFile(path) } if (url) { return new RemoteFile(url) } throw new TypeError('must provide either filehandle, path, or url') } // An explicitly supplied index always wins over the `.tbi` / // `.tbi` names derived from the data file, whichever kind it is. function resolveIndex({ tbiFilehandle, csiFilehandle, tbiPath, csiPath, tbiUrl, csiUrl, path, url, }: { tbiFilehandle?: GenericFilehandle csiFilehandle?: GenericFilehandle tbiPath?: string csiPath?: string tbiUrl?: string csiUrl?: string path?: string url?: string }) { if (tbiFilehandle) { return new TBI({ filehandle: tbiFilehandle }) } if (csiFilehandle) { return new CSI({ filehandle: csiFilehandle }) } if (tbiPath) { return new TBI({ filehandle: new LocalFile(tbiPath) }) } if (csiPath) { return new CSI({ filehandle: new LocalFile(csiPath) }) } if (csiUrl) { return new CSI({ filehandle: new RemoteFile(csiUrl) }) } if (tbiUrl) { return new TBI({ filehandle: new RemoteFile(tbiUrl) }) } if (path) { return new TBI({ filehandle: new LocalFile(`${path}.tbi`) }) } if (url) { return new TBI({ filehandle: new RemoteFile(`${url}.tbi`) }) } throw new TypeError( 'must provide one of tbiFilehandle, tbiPath, csiFilehandle, csiPath, tbiUrl, csiUrl', ) } function calculateFileOffset( cpositions: ArrayLike, dpositions: ArrayLike, pos: number, blockStart: number, minvDataPosition: number, ) { return ( cpositions[pos]! * (1 << 8) + (blockStart - dpositions[pos]!) + minvDataPosition + 1 ) } function getVcfEnd( buffer: Uint8Array, startCoordinate: number, refStart: number, refEnd: number, infoStart: number, infoEnd: number, altEnd: number, ) { const refLen = refEnd - refStart let endCoordinate = startCoordinate + refLen let svlen = 0 // INFO is '.', no fields to check if (buffer[infoStart] === 46) { return endCoordinate } // Single pass over semicolon-delimited fields checking prefixes. // Avoids repeated indexOf scans for common bytes like 'S' and 'E' // that produce many false positives in typical INFO fields. let fieldStart = infoStart for (let i = infoStart; i <= infoEnd; i++) { if (i === infoEnd || buffer[i] === SEMICOLON) { const fieldLen = i - fieldStart if ( fieldLen >= 10 && buffer[fieldStart] === 83 && // S buffer[fieldStart + 1] === 86 && // V buffer[fieldStart + 2] === 84 && // T buffer[fieldStart + 3] === 89 && // Y buffer[fieldStart + 4] === 80 && // P buffer[fieldStart + 5] === 69 && // E buffer[fieldStart + 6] === 61 && // = buffer[fieldStart + 7] === 84 && // T buffer[fieldStart + 8] === 82 && // R buffer[fieldStart + 9] === 65 // A ) { return startCoordinate + 1 } if ( fieldLen >= 4 && buffer[fieldStart] === 69 && // E buffer[fieldStart + 1] === 78 && // N buffer[fieldStart + 2] === 68 && // D buffer[fieldStart + 3] === 61 // = ) { // an END at or before POS describes no span; htslib ignores it too const end = parseIntFromBytes(buffer, fieldStart + 4, i) if (end > startCoordinate) { endCoordinate = end } } else if ( fieldLen >= 6 && buffer[fieldStart] === 83 && // S buffer[fieldStart + 1] === 86 && // V buffer[fieldStart + 2] === 76 && // L buffer[fieldStart + 3] === 69 && // E buffer[fieldStart + 4] === 78 && // N buffer[fieldStart + 5] === 61 // = ) { svlen = maxSvlenOnRef(buffer, fieldStart + 6, i, refEnd + 1, altEnd) } fieldStart = i + 1 } } return Math.max(endCoordinate, startCoordinate + svlen) } const COMMA = 44 /** * htslib's `svlen_on_ref_for_vcf_alt`: whether an ALT's SVLEN is a length on * the reference, which it is for , , , and their subtypes. */ function svlenSpansRef(buffer: Uint8Array, start: number, end: number) { if (end - start < 5 || buffer[start] !== 60 || buffer[end - 1] !== 62) { return false } const after = buffer[start + 4] if (after !== 62 && after !== 58) { return false } const a = buffer[start + 1] const b = buffer[start + 2] const c = buffer[start + 3] return ( (a === 67 && b === 78 && c === 86) || // CNV (a === 68 && b === 69 && c === 76) || // DEL (a === 68 && b === 85 && c === 80) || // DUP (a === 73 && b === 78 && c === 86) // INV ) } /** * The longest reference length the SVLEN values state, each read against the * ALT it pairs with, as htslib's tbx_parse1 does. */ function maxSvlenOnRef( buffer: Uint8Array, valuesStart: number, valuesEnd: number, altStart: number, altEnd: number, ) { let max = 0 let value = valuesStart let alt = altStart while (value < valuesEnd && alt < altEnd) { let valueEnd = buffer.indexOf(COMMA, value) if (valueEnd === -1 || valueEnd > valuesEnd) { valueEnd = valuesEnd } let alleleEnd = buffer.indexOf(COMMA, alt) if (alleleEnd === -1 || alleleEnd > altEnd) { alleleEnd = altEnd } if (svlenSpansRef(buffer, alt, alleleEnd)) { const len = parseIntFromBytes( buffer, buffer[value] === 45 ? value + 1 : value, valueEnd, ) if (len > max) { max = len } } value = valueEnd + 1 alt = alleleEnd + 1 } return max } const textDecoder = new TextDecoder() /** * The leading run of meta-character lines — what `tabix -H` prints. Everything * from the first line that doesn't begin with the meta character is dropped. */ function trimToMetaLines(bytes: Uint8Array, metaChar: string) { let lastNewline = -1 const metaByte = metaChar.charCodeAt(0) for (let i = 0, l = bytes.length; i < l; i++) { const byte = bytes[i] if (i === lastNewline + 1 && byte !== metaByte) { break } if (byte === NEWLINE) { lastNewline = i } } return bytes.subarray(0, lastNewline + 1) } /** * The first `count` lines. Scans for the count-th newline and decodes only that * far, rather than decoding and splitting the whole buffer to keep its first * few lines — the buffer runs to the first data line, which for a file with a * long commented preamble above its counted rows can be megabytes. */ function firstLines(bytes: Uint8Array, count: number) { let end = 0 for (let i = 0; i < count; i++) { const n = bytes.indexOf(NEWLINE, end) if (n === -1) { end = bytes.length break } end = n + 1 } return textDecoder .decode(bytes.subarray(0, end)) .split(/\r?\n/) .slice(0, count) } function parseIntFromBytes(buffer: Uint8Array, start: number, end: number) { let val = 0 for (let i = start; i < end; i++) { const c = buffer[i]! if (c >= 48 && c <= 57) { val = val * 10 + (c - 48) } else { break } } return val } interface GafQuery { start: number end: number pathCol: number metaCharCode: number | undefined decoder: TextDecoder callback: GetLinesCallback } /** * The GAF scan of one chunk. A read spans the lowest to the highest node id on * its path, which htslib's tbx_parse1 reads the same way. Returns true once a * read starts at or past `end`: records are sorted by their lowest node. */ function scanGafChunk( buffer: Uint8Array, base: number, cpositions: ArrayLike, dpositions: ArrayLike, minvDataPosition: number, { start, end, pathCol, metaCharCode, decoder, callback }: GafQuery, ) { let blockStart = 0 let pos = 0 while (blockStart < buffer.length) { const n = buffer.indexOf(NEWLINE, blockStart) if (n === -1) { break } const lineStart = blockStart blockStart = n + 1 const target = lineStart + base + minvDataPosition while (pos < dpositions.length && target >= dpositions[pos]!) { pos++ } if (buffer[lineStart] === metaCharCode) { continue } let pathStart = lineStart for (let i = 1; i < pathCol; i++) { const t = buffer.indexOf(TAB, pathStart) if (t === -1 || t >= n) { pathStart = n break } pathStart = t + 1 } // A path without a leading step is a stable sequence name (or `*`), which // carries no node ids. htslib parses one anyway and indexes garbage // (`GRCh38#0#chr1` as nodes 0..38), so skip it rather than match that. const first = buffer[pathStart] if (first !== GREATER_THAN && first !== LESS_THAN) { continue } let pathEnd = buffer.indexOf(TAB, pathStart) if (pathEnd === -1 || pathEnd > n) { pathEnd = n } // like htslib, skip one byte (the orientation) before each node id let min = Infinity let max = -1 let i = pathStart while (i < pathEnd) { let id = 0 let j = i + 1 for (; j < pathEnd; j++) { const digit = buffer[j]! - 48 if (digit < 0 || digit > 9) { break } id = id * 10 + digit } if (id < min) { min = id } if (id > max) { max = id } i = j } if (min >= end) { return true } if (max >= start) { const lineEnd = buffer[n - 1] === CARRIAGE_RETURN ? n - 1 : n callback( decoder.decode(buffer.subarray(lineStart, lineEnd)), calculateFileOffset( cpositions, dpositions, pos, lineStart + base, minvDataPosition, ), min, max + 1, ) } } return false } /** * Reads Tabix-indexed files (bgzipped), supporting both .tbi and .csi index formats. */ export default class TabixIndexedFile { private filehandle: GenericFilehandle private index: IndexFile public chunkCache: SharedReadCache // Every chunk handed to the cache, by key, so a later chunk lying inside one // can read it instead of fetching its own span. withCachedContainers prunes // the entries the cache has dropped. private requested = new Map() /** * The parsed header, as a shared read — see {@link getParsedHeader}. One * entry, never evicted, which is what a memo is. */ private headerCache = new SharedReadCache< string, { header: string; skippedLines: string[] } >({}) /** see the constructor option of the same name */ private bgzfWorkerPool?: BgzfWorkerPool | Promise | undefined constructor({ path, filehandle, url, tbiPath, tbiUrl, tbiFilehandle, csiPath, csiUrl, csiFilehandle, chunkCacheSize = DEFAULT_CHUNK_CACHE_BYTES, chunkCacheIdleTimeoutMs = DEFAULT_CHUNK_CACHE_IDLE_TIMEOUT_MS, chunkCacheBudget, bgzfWorkerPool, }: { path?: string filehandle?: GenericFilehandle url?: string tbiPath?: string tbiUrl?: string tbiFilehandle?: GenericFilehandle csiPath?: string csiUrl?: string csiFilehandle?: GenericFilehandle /** * Budget for the decompressed chunk cache, in bytes. Default 1GB. * * **The unit changed in v3.5.2** (ADR 0001). Before that this was divided * by 64KB to get an entry count, so a caller passing `50 * 2**20` was * asking for 800 whole decompressed chunks — unbounded in practice. It now * means 50MB, twenty times under the default, and the name did not change * so nothing warns. If you pinned a value here before v3.5.2, it does not * mean what it did. * * What that costs is worth keeping, because it is the reason to check a * pinned value rather than assume it is harmless: jbrowse passed exactly * `50 * 2**20` in nine adapters, and measured on * `test/data/1kg.chr1.subset.vcf.gz` that was a **total miss** — 47 refills * out of 47 on the warm pass against 0 at the default, holding 82.7MB in a * single entry, over the budget it was given because the last settled entry * is kept whatever the budget. Those nine adapters now pass * `chunkCacheBudget` and no `chunkCacheSize` at all, so that particular * instance is gone; the trap it demonstrates is not. * * A retention bound, not a bound on peak memory: reads in flight are never * evicted and the last settled entry is kept whatever the budget. Size it * to hold several queries — below one query's working set the hit rate * drops to zero while the memory is retained anyway, so a number between * the two is the worst available choice. */ chunkCacheSize?: number /** * Drop a cached chunk once nothing has read it for this many milliseconds. * Default 3 minutes; `0` keeps chunks until `chunkCacheSize` evicts them. * * The only thing that lowers the cache while nothing is happening, and what * makes the budget above a peak rather than a resting level. */ chunkCacheIdleTimeoutMs?: number /** * A budget shared with other files, so that the ceiling applies to their * sum rather than to each of them. Any `@gmod/shared-read-cache` consumer * that weighs in the same unit can join it: `@gmod/bam` also weighs * decompressed bytes, while `@gmod/cram` weighs decoded records and * `@gmod/bbi` weighs entries, and a budget mixing those adds bytes to * records and bounds neither. * * {@link chunkCacheSize} is per file, which is not a bound on a consumer * that opens one file per track. @gmod/bam measured the shape: six tracks * browsing six windows retained 1442 MB with every cache still under its * own ceiling, so the ceiling was not holding the line and nothing else * was. The idle timeout cannot help there — it does nothing while the * reader is browsing, which is the whole case. * * Dividing {@link chunkCacheSize} by the track count instead reintroduces * the cliff it exists to avoid. A shared budget does not, because a member * yields only what is globally least-recently-used: files nobody is * reading hand their space to the one being panned. */ chunkCacheBudget?: Budget /** * A `@gmod/bgzf-filehandle` worker pool to inflate this file's chunks on, * instead of inflating them on the calling thread. * * BGZF decompression dominates a cold query and BGZF blocks are * independently inflatable, so this is the one remaining lever of that * size. @gmod/bam measured 1.95x end to end wiring the same pool into a * genome browser's read path. * * Accepts the promise `getSharedWorkerPool()` returns as well as a pool, * so a caller whose own construction is synchronous can hand the pending * pool straight over — it is awaited at the point of use, by which time it * has long since resolved. `undefined` (which is what that helper gives * back under node, or anywhere Workers cannot be created) keeps the * in-process path, so this is safe to pass unconditionally. */ bgzfWorkerPool?: BgzfWorkerPool | Promise | undefined }) { this.bgzfWorkerPool = bgzfWorkerPool this.filehandle = resolveFilehandle(filehandle, path, url) this.index = resolveIndex({ tbiFilehandle, csiFilehandle, tbiPath, csiPath, tbiUrl, csiUrl, path, url, }) this.chunkCache = new SharedReadCache({ maxSize: chunkCacheSize, // decompressed bytes, not entry count: we fetch compressed and cache // decompressed, and an entry is a whole chunk sizeOf: read => { let bytes = 0 for (const segment of read.segments) { bytes += segment.byteLength } return bytes }, cacheKey: chunk => chunk.toString(), idleTimeoutMs: chunkCacheIdleTimeoutMs, budget: chunkCacheBudget, fill: (chunk, signal) => this.readChunk(chunk, { signal }), }) } /** * Drops every decompressed chunk held by the cache, and stops the idle sweep * until something is cached again. * * `chunkCacheIdleTimeoutMs` reclaims a view the user has wandered away from; * this is for a consumer that knows it is finished — a closed track, a * changed assembly — and should not have to wait it out. */ clearChunkCache() { this.chunkCache.clear() this.requested.clear() } /** * Swaps each chunk for the smallest cached or in-flight chunk that contains * it, so a pan whose chunk starts later in an entry already read reuses it. * The scan reads only the wanted chunk's span of the container, so a query * returns the same lines whatever the cache holds. A container that would * overlap a neighbouring chunk stays unused, since the overlap would yield * its lines twice. See docs/optimizations.md. * * `has` builds a string key, so the loop calls it only on a chunk that * already contains this one, and a sweep prunes dropped entries once they * outnumber the cache. */ private withCachedContainers(chunks: Chunk[]) { if (this.requested.size > 2 * this.chunkCache.size) { for (const [key, held] of this.requested) { if (!this.chunkCache.has(held)) { this.requested.delete(key) } } } const out: Chunk[] = [] for (let i = 0; i < chunks.length; i++) { const chunk = chunks[i]! const prev = out[out.length - 1] const next = chunks[i + 1] let best: Chunk | undefined if (!this.chunkCache.has(chunk)) { for (const held of this.requested.values()) { if ( held.minv.compareTo(chunk.minv) <= 0 && held.maxv.compareTo(chunk.maxv) >= 0 && (!prev || held.minv.compareTo(prev.maxv) >= 0) && (!next || held.maxv.compareTo(next.minv) <= 0) && (!best || held.fetchedSize() < best.fetchedSize()) && this.chunkCache.has(held) ) { best = held } } } out.push(best ?? chunk) } return out } /** * Estimates the compressed byte size of the index chunks covering the given * regions. Useful for byte budgeting before issuing a `getLines` call to * decide whether a region is too large to fetch. */ async bytesForRegions( regions: { refName: string; start: number; end: number }[], opts: Options = {}, ) { const all: Chunk[] = [] for (const { refName, start, end } of regions) { const chunks = await this.index.blocksForRange(refName, start, end, opts) for (const chunk of chunks) { all.push(chunk) } } let bytes = 0 for (const chunk of optimizeChunks(all)) { bytes += chunk.fetchedSize() } return bytes } /** * @param refName name of the reference sequence * @param s start of the region (0-based half-open) * @param e end of the region (0-based half-open) * @param opts callback invoked for each line, or an options object with `lineCallback` and optional `signal` */ async getLines( refName: string, s: number | undefined, e: number | undefined, opts: GetLinesOpts | GetLinesCallback, ) { let signal: AbortSignal | undefined let options: Options = {} let callback: GetLinesCallback let onProgress: GetLinesOpts['onProgress'] if (typeof opts === 'function') { callback = opts } else { options = opts callback = opts.lineCallback signal = opts.signal onProgress = opts.onProgress } const metadata = await this.index.getMetadata(options) const start = s ?? 0 const end = e ?? metadata.maxRefLength if (start > end) { throw new TypeError( 'invalid start and end coordinates. start must be less than or equal to end', ) } if (start === end) { return } const wanted = await this.index.blocksForRange(refName, start, end, options) const chunks = this.withCachedContainers(wanted) const isVCF = metadata.format === 'VCF' const refCol = metadata.columnNumbers.ref || 0 const startCol = metadata.columnNumbers.start || 0 const endCol = isVCF ? 8 : metadata.columnNumbers.end || 0 const maxColumn = Math.max(refCol, startCol, endCol) const metaCharCode = metadata.metaChar?.charCodeAt(0) const coordinateOffset = metadata.coordinateType === '1-based-closed' ? -1 : 0 const encoder = new TextEncoder() const decoder = new TextDecoder() const regionRefNameBytes = encoder.encode(refName) // tabs[N] holds the byte offset of the N-th tab on the current line; with // the sentinel tabs[0] = blockStart - 1, column N spans tabs[N-1]+1..tabs[N] const tabs = new Int32Array(maxColumn + 1) const gaf: GafQuery | undefined = metadata.format === 'GAF' ? { start, end, pathCol: startCol, metaCharCode, decoder, callback } : undefined let totalBytes = 0 for (const c of chunks) { totalBytes += c.fetchedSize() } let downloadedBytes = 0 onProgress?.(0, totalBytes) // Read ahead, but only as far as the scan has earned. Every chunk is its // own range request, so a query spanning many of them pays a network round // trip apiece, serially — for a remote file that dominates, well ahead of // decompression (1kg.chr1 over a 1Mb window reads 22 chunks in a row). // // A fixed window would be wrong, though: blocksForRange offers a chunk per // overlapping bin across every level, and on a sparse file the early return // below can stop the scan inside the first one, leaving the rest untouched. // max_off drops only the chunks it can prove lie past the query, so the // scan can still end before the last one it is offered. Prefetching those // would multiply the bytes such a query fetches for no gain. // // Finishing a chunk without hitting the early return proves the next chunk // has to be examined, so the window starts at one and doubles per chunk // consumed. A query that stops in its first chunk issues exactly the reads // a sequential scan did; a long scan reaches full concurrency after three. let readAhead = 1 const reads: Promise[] = [] const ensureReadsStarted = (count: number) => { while (reads.length < Math.min(count, chunks.length)) { const c = chunks[reads.length]! this.requested.set(c.toString(), c) const read = this.chunkCache.get(c, signal) void read.catch(() => { // a prefetch the early return skips is never awaited, so swallow its // rejection here rather than let it surface unhandled }) reads.push(read) } } ensureReadsStarted(1) for (let ci = 0, cl = chunks.length; ci < cl; ci++) { const c = chunks[ci]! const read = await reads[ci]! const { cpositions, dpositions } = read downloadedBytes += c.fetchedSize() onProgress?.(downloadedBytes, totalBytes) const minvDataPosition = c.minv.dataPosition // in a container, scan only the bytes a read of the wanted chunk holds const want = wanted[ci]! let segments = read.segments let from = 0 if (want !== c) { from = chunkBufferOffset(cpositions, dpositions, want.minv) const to = chunkBufferOffset(cpositions, dpositions, want.maxv) + 1 segments = sliceSegments(segments, from, to) } if (gaf) { if ( forEachLinePiece(segments, from, (buffer, base) => scanGafChunk( buffer, base, cpositions, dpositions, minvDataPosition, gaf, ), ) ) { return } } else if ( forEachLinePiece(segments, from, (buffer, base) => { let blockStart = 0 let pos = 0 while (blockStart < buffer.length) { const n = buffer.indexOf(NEWLINE, blockStart) if (n === -1) { break } const target = blockStart + base + minvDataPosition while (pos < dpositions.length && target >= dpositions[pos]!) { pos++ } // skip meta lines if ( metaCharCode !== undefined && buffer[blockStart] === metaCharCode ) { blockStart = n + 1 continue } // find tab positions. Columns past the end of the line all get `n` // rather than breaking out, which would leave stale offsets from the // previous line in the tail of the array. tabs[0] = blockStart - 1 for (let i = 0; i < maxColumn; i++) { const prev = tabs[i]! const tabPos = prev < n ? buffer.indexOf(TAB, prev + 1) : -1 tabs[i + 1] = tabPos === -1 || tabPos >= n ? n : tabPos } // compare ref name bytes directly const refStart = tabs[refCol - 1]! + 1 const refEnd = tabs[refCol]! const refLen = refEnd - refStart if (refLen !== regionRefNameBytes.length) { blockStart = n + 1 continue } let isRefMatch = true for (let i = 0; i < refLen; i++) { if (buffer[refStart + i] !== regionRefNameBytes[i]) { isRefMatch = false break } } if (!isRefMatch) { blockStart = n + 1 continue } // parse start coordinate const startCoordinate = parseIntFromBytes( buffer, tabs[startCol - 1]! + 1, tabs[startCol]!, ) + coordinateOffset if (startCoordinate >= end) { return true } // parse end coordinate let endCoordinate: number if (endCol === 0 || endCol === startCol) { endCoordinate = startCoordinate + 1 } else if (isVCF) { endCoordinate = getVcfEnd( buffer, startCoordinate, tabs[3]! + 1, tabs[4]!, tabs[endCol - 1]! + 1, tabs[endCol]!, tabs[5]!, ) } else { endCoordinate = parseIntFromBytes( buffer, tabs[endCol - 1]! + 1, tabs[endCol]!, ) } if (endCoordinate > start) { // trim a CRLF terminator, matching htslib's line reader const lineEnd = buffer[n - 1] === CARRIAGE_RETURN ? n - 1 : n const line = decoder.decode(buffer.subarray(blockStart, lineEnd)) callback( line, calculateFileOffset( cpositions, dpositions, pos, blockStart + base, minvDataPosition, ), startCoordinate, endCoordinate, ) } blockStart = n + 1 } return false }) ) { return } // every line in this chunk was still inside the query, so the next chunk // has to be examined too - widen the window and start the reads for it readAhead = Math.min(readAhead * 2, MAX_READ_AHEAD_CHUNKS) ensureReadsStarted(ci + 1 + readAhead) } } async getMetadata(opts: Options = {}) { return this.index.getMetadata(opts) } /** * The file's leading blocks, decompressed: everything from the start through * the end of the block holding the first data line. */ private async readHeaderBytes(opts: Options) { const { firstDataLine, maxBlockSize } = await this.getMetadata(opts) // A file whose first data line opens it has no header to read. htslib // fills a contig's leading index windows with that contig's first record, // so this holds for its indexes; standalone tabix 0.2 left them at 0. if ( firstDataLine?.blockPosition === 0 && firstDataLine.dataPosition === 0 ) { return new Uint8Array(0) } const maxFetch = (firstDataLine?.blockPosition ?? 0) + maxBlockSize // TODO: what if we don't have a firstDataLine, and the header actually // takes up more than one block? this case is not covered here const buf = await this.filehandle.read(maxFetch, 0, opts) return unzip(buf) } /** * Both header forms, from one read of the same bytes: the commented block * `tabix -H` prints, and the rows `tabix -S N` counted. * * Memoized, because asking for one and then the other is the normal way to * find a header whichever way the file keeps it (see `getHeaderLines`), and * that used to fetch and decompress the file's leading blocks twice. Only * the parsed results are retained — the decompressed bytes are dropped, * which matters for a VCF header that can run to megabytes. */ private async parseHeader(opts: Options) { const { metaChar, skipLines = 0 } = await this.getMetadata(opts) const bytes = await this.readHeaderBytes(opts) return { header: textDecoder.decode( metaChar ? trimToMetaLines(bytes, metaChar) : bytes, ), skippedLines: skipLines > 0 ? firstLines(bytes, skipLines) : [], } } /** * Parse the header, or join the parse already running. * * `parseHeader` threads `opts` into both `getMetadata` and the header read, * so memoizing it on the first caller's opts put that caller's signal in * charge of a read every later caller joins: when it aborted, they failed * with its cancellation, their own signals untouched. * * The same cache the chunk reads use, and the same rule: the parse runs under * a signal of its own and is cancelled only once every caller waiting on it * has given up, so one caller's abort is reported to that caller alone and a * bystander gets the parse already in flight. There is no retry here because * there is nothing to retry — the parse a bystander joined is not cancelled by * someone else's abort. A rejection is dropped rather than cached, so a * transient failure does not poison the header for the life of the file. * * The fill is per call rather than on the cache, so the caller that starts the * parse has its `onProgress` reach the index download inside `getMetadata`. * * SYNC: ~/src/gmod/bam-js/src/bamFile.ts getHeader — same shape for the same * reason, on the header rather than the index. */ private getParsedHeader(opts: Options = {}) { return this.headerCache.get('header', opts.signal, signal => this.parseHeader({ ...opts, signal }), ) } /** * The bytes of the commented header. Deliberately not memoized, unlike the * string form: this hands back the buffer, and holding one for the lifetime * of the file is the caller's decision to make. */ async getHeaderBuffer(opts: Options = {}) { const { metaChar } = await this.getMetadata(opts) const bytes = await this.readHeaderBytes(opts) return metaChar ? trimToMetaLines(bytes, metaChar) : bytes } /** * The leading lines the index says to skip — `tabix -S N` — which is where a * file whose header row is not commented keeps it. Empty when the index * records no skipped lines. * * Deliberately not part of `getHeader`. htslib draws the same distinction: * its indexer treats a line as non-data when `lineno <= line_skip` OR it * begins with the meta character (tbx.c), while `tabix -H` prints only the * leading meta-character lines and never consults line_skip (tabix.c). * `getHeader` mirrors `-H`, so a bare header row is absent from it, and * callers that need one were left re-reading the file themselves — guessing * at a read size, and unable to tell a headerless file from an uncommented * one. PLINK `.ld`, bedGraph and BED deflines are all routinely written this * way. */ async getSkippedLines(opts: Options = {}) { const { skipLines = 0 } = await this.getMetadata(opts) // the index already answers this without reading the file at all if (skipLines <= 0) { return [] } return (await this.getParsedHeader(opts)).skippedLines } async getHeader(opts: Options = {}) { return (await this.getParsedHeader(opts)).header } /** * The file's header lines, however that file keeps them: the meta-character * block when there is one, and otherwise the rows the index counted. Empty * lines are dropped. * * The two halves answer different questions (see `getSkippedLines`), but * "what are this file's header lines" is nearly always the question a caller * actually has, and answering it from `getHeader` alone is wrong in a way * that doesn't announce itself: a bare header row comes back as the empty * string, indistinguishable from a file that has no header, so callers fall * back to an assumed column layout and quietly mis-name columns. Deciding it * here also means one read of the leading blocks instead of two. */ async getHeaderLines(opts: Options = {}) { const { header, skippedLines } = await this.getParsedHeader(opts) return (header ? header.split(/\r?\n/) : skippedLines).filter(Boolean) } async getReferenceSequenceNames(opts: Options = {}) { const metadata = await this.getMetadata(opts) return metadata.refIdToName } /** @param refName reference sequence name */ async lineCount(refName: string, opts: Options = {}) { return this.index.lineCount(refName, opts) } /** @internal */ async readChunk(c: Chunk, opts: Options = {}) { const ret = await this.filehandle.read( c.fetchedSize(), c.minv.blockPosition, opts, ) // LocalFile cannot cancel a read already under way, so a chunk every waiter // has abandoned still arrives here. The signal is the cache's shared one, // which fires only once nobody wants the bytes, so skip the inflate. // SYNC: ~/src/gmod/bam-js/src/bamFile.ts _readChunkFeatures throwIfAborted(opts.signal) // Awaited rather than stored resolved: the pool is commonly handed over as // the pending promise from getSharedWorkerPool(), and awaiting an // already-settled promise costs a microtask. const pool = await this.bgzfWorkerPool return unzipChunkSegments(ret, c, pool) } }