SAM Reader

The SAM reader MUST open a bgzf-compressed SAM file, parse its header, and locate a tabix (.tbi) or CSI (.csi) index file. If neither index exists, return an error suggesting samtools index or tabix -p sam.

If the file does not start with BGZF magic (1f 8b with BC subfield), the reader MUST reject it with an error explaining that plain SAM files must be bgzf-compressed for indexed access (bgzip file.sam).

The SAM header consists of all lines starting with @ at the beginning of the file. The reader MUST:

1. Read lines from the BGZF stream until a line does NOT start with @.
2. Record the BGZF virtual offset of the first alignment line (for seeking past the header).
3. Parse @SQ lines to extract target names (SN tag) and lengths (LN tag).
4. Construct a BamHeader from the parsed text via BamHeader::from_sam_text().

Lines starting with @ that appear after the first alignment line are NOT header continuation — they are malformed alignment lines and MUST be treated as parse errors.

If no @SQ lines are present, the reader MUST return an error. Without @SQ lines, target name→tid mapping is impossible and fetch_into cannot work.

The full header text (all @ lines joined with newlines) MUST be stored in BamHeader::header_text for downstream use (e.g., constructing htslib Header for BAM writing).

Each alignment line MUST be split on TAB characters into the 11 mandatory fields plus optional tag fields. The parser MUST handle:

| Field | SAM type | Conversion to internal representation | | ----- | --------------- | -------------------------------------------------------------------------- | ---- | | QNAME | string | stored as bytes in name slab | | FLAG | integer | u16 (identical to BAM flags) | | RNAME | string | converted to tid via header's name_to_tid map | | POS | 1-based integer | subtract 1 for 0-based internal pos (i64) | | MAPQ | integer | u8 (255 means unavailable) | | CIGAR | string | parsed to packed BAM CIGAR ops (u32 per op: len << 4 | op) | | RNEXT | string | = means same as RNAME, * means unavailable — not stored in RecordStore | | PNEXT | integer | not stored in RecordStore (mate info) | | TLEN | integer | not stored in RecordStore (template length) | | SEQ | string | each ASCII char decoded to Base enum | | QUAL | string | each char minus 33 for Phred score; * means all 0xFF |

The parser MUST validate each field and produce clear error messages for malformed records: non-integer POS, FLAG > 65535, negative MAPQ, etc. Real-world SAM files from non-standard tools may contain hand-edited or corrupted records.

SAM POS is 1-based; the internal representation is 0-based (matching BAM). The parser MUST subtract 1 from POS. A POS of 0 in SAM means unmapped — after subtraction this becomes -1 (as i64). Unmapped records are filtered by FLAG 0x4 before reaching this point, so -1 positions should not appear in the RecordStore.

The CIGAR string MUST be parsed into the same packed u32 format used by BAM: each operation is (length << 4) | op_code, where op_codes are M=0, I=1, D=2, N=3, S=4, H=5, P=6, =7, X=8. The string * means CIGAR unavailable (0 operations, and end_pos = pos).

SEQ characters MUST be decoded to Base values: A→A, C→C, G→G, T→T, all others (N, IUPAC codes)→Unknown. The string * means sequence unavailable (length 0).

QUAL characters MUST have 33 subtracted (Phred+33 encoding). The string * means quality unavailable; all quality bytes MUST be set to 0xFF (255). QUAL length MUST equal SEQ length when both are present.

Optional fields after the 11th column follow the format TAG:TYPE:VALUE. They MUST be serialized to BAM binary aux format for storage in the data slab:

• A (char): [tag0, tag1, 'A', char]
• i (integer): [tag0, tag1, type, bytes...] where type is the smallest fitting BAM integer type:
  • [-128, 127] → c (int8)
  • [128, 255] → C (uint8)
  • [-32768, -129] or [256, 32767] → s (int16)
  • [32768, 65535] → S (uint16)
  • [-2147483648, -32769] or [65536, 2147483647] → i (int32)
  • [2147483648, 4294967295] → I (uint32)
• f (float): [tag0, tag1, 'f', le_f32_bytes]
• Z (string): [tag0, tag1, 'Z', string_bytes, 0x00]
• H (hex): [tag0, tag1, 'H', hex_bytes, 0x00]
• B (array): [tag0, tag1, 'B', subtype, count_le32, values...]

Malformed aux tag values MUST return an error, not silently default to zero. For integer (i) typed tags, if the value cannot be parsed as an integer, the reader MUST return a SamRecordError::InvalidAuxValue error.

SAM aux integer values (type i) are serialized into the smallest BAM integer type that fits, using the ranges defined in r[sam.record.aux_tags]. Values that exceed the u32 range (i.e., val > u32::MAX or val < i32::MIN when interpreted as i64) cannot be represented in any BAM integer type and MUST return a SamRecordError::AuxIntOutOfRange error instead of silently truncating.

fetch_into(tid, start, end, store) MUST:

1. Query the tabix/CSI index for BGZF virtual offset ranges overlapping the region.
2. Use RegionBuf (or equivalent bulk read) to load compressed bytes.
3. Decompress BGZF blocks to text.
4. Split text into lines (on \n).
5. Parse each alignment line.
6. Filter: skip lines where RNAME's tid doesn't match, or where the record doesn't overlap [start, end].
7. Skip unmapped reads (FLAG 0x4).
8. Push passing records into the RecordStore.

The overlap filter uses half-open intervals (0-based). end_pos MUST be computed from the parsed CIGAR. When CIGAR is * (unavailable), end_pos = pos (point record).

A record overlaps [start, end) iff pos < end && end_pos > start. Records where pos == end or end_pos == start do NOT overlap and MUST be filtered out.

Records MUST be added to the store in coordinate-sorted order. Since bgzf-compressed indexed SAM files are coordinate-sorted by construction (indexing requires it), the natural parse order is correct.

The reader MUST support tabix (.tbi) indexes. Tabix is a generic index for bgzf-compressed, TAB-delimited files. For SAM, the format code is 1 (not 0/generic). The column configuration (seq_col=3, beg_col=4, end_col=0) is implicit for format=1 and may be ignored by some implementations; the reader SHOULD NOT reject a tabix file based on stored column values when format=1 is present.

Index file lookup order: <path>.tbi, <path>.bai. If neither exists, return a clear error. CSI (.csi) lookup should be added when CSI support is implemented.

When SEQ is *, the record has no sequence data. seq_len MUST be 0 and no bases are pushed to the bases slab. This is valid per the SAM spec for secondary alignments that omit sequence.

When QUAL is *, all quality bytes MUST be 0xFF. This matches BAM's representation of unavailable quality.

BAM encodes CIGARs with >65535 operations using a CG:B:I aux tag and a placeholder CIGAR. SAM has no such limitation — the CIGAR string can be arbitrarily long. The parser MUST handle CIGARs of any length.

Blank lines (empty or whitespace-only) between alignment records MUST be silently skipped.

RNAME of * means unmapped. Combined with FLAG 0x4, these records MUST be filtered out by fetch_into (same as BAM's unmapped filtering). RNAME * without FLAG 0x4 is malformed but SHOULD be treated as unmapped.

A single SAM alignment line may span multiple BGZF blocks. The reader MUST buffer partial lines across block boundaries and only parse complete lines (terminated by \n). The parser MUST also strip \r at line boundaries to handle \r\n (Windows-style) line endings that may appear in files from mixed-platform pipelines.

Integer parsing functions (parse_u8, parse_u16, parse_u32) MUST reject empty input by returning None. An empty byte slice is not a valid integer representation and MUST NOT silently produce zero.

Like BAM, the SAM reader SHOULD use RegionBuf-style bulk I/O: read all compressed bytes for the region in one large I/O operation, then decompress and parse from memory. This is critical for NFS/Lustre performance.