streampile 0.2.0

Forward-only pileups streamed from coordinate-sorted BAM records
Documentation
use std::io;

use crate::error::invalid_data;
use crate::pileup::{EntryKind, NONE};

const MATCH: u32 = 0;
const INSERTION: u32 = 1;
const DELETION: u32 = 2;
const SKIP: u32 = 3;
const SOFT_CLIP: u32 = 4;
const HARD_CLIP: u32 = 5;
const PAD: u32 = 6;
const SEQUENCE_MATCH: u32 = 7;
const SEQUENCE_MISMATCH: u32 = 8;

/// What a read holds at one reference position it spans.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Located {
    /// The query offset of the base aligned there.
    Base(u32),
    /// A deletion, with the query offset of the read's next base when one follows.
    Deletion(Option<u32>),
    /// A reference skip, the CIGAR `N` operator.
    Skip,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum BlockKind {
    Aligned,
    Deleted,
    Skipped,
}

/// One reference-consuming CIGAR operator: `query` is the offset of its first base, or for a
/// deletion or skip, of the read's next base.
#[derive(Clone, Copy, Debug)]
struct Block {
    start: i64,
    end: i64,
    query: u32,
    kind: BlockKind,
}

/// The inserted bases a read holds right after the reference position `anchor`.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Insertion {
    pub anchor: i64,
    pub offset: u32,
    pub length: u32,
}

/// Where one read sits on the reference, worked out once from its CIGAR.
///
/// The reference-consuming operators tile `start..end` as blocks, and each lookup moves a cursor
/// forward, so a read is located at each position of a forward sweep in constant time, and a
/// long reference skip costs one block, not one entry per skipped position. The buffers keep
/// their capacity when the footprint is filled again for another read.
#[derive(Debug, Default)]
pub(crate) struct Footprint {
    pub start: i64,
    pub end: i64,
    pub query_length: u32,
    blocks: Vec<Block>,
    insertions: Vec<Insertion>,
    block: usize,
    insertion: usize,
}

impl Footprint {
    /// Walks a raw BAM CIGAR from a 0-based start, and returns whether it has a
    /// reference-consuming operator: M, D, N, =, or X.
    ///
    /// A CIGAR whose query length differs from the number of stored bases is refused, as htslib
    /// refuses it, so a deletion is followed by a base exactly when its offset is within the read.
    pub fn fill(&mut self, start: i64, cigar: &[u8], stored_bases: usize) -> io::Result<bool> {
        self.blocks.clear();
        self.insertions.clear();
        self.block = 0;
        self.insertion = 0;
        self.start = start;
        let (ops, rest) = cigar.as_chunks::<4>();
        if !rest.is_empty() {
            return Err(invalid_data("a CIGAR is not a whole number of operators"));
        }
        let mut position = start;
        let mut query: u64 = 0;
        let mut placed = false;
        for op in ops {
            let op = u32::from_le_bytes(*op);
            let length = op >> 4;
            let offset = to_offset(query)?;
            match op & 0xF {
                MATCH | SEQUENCE_MATCH | SEQUENCE_MISMATCH => {
                    placed = true;
                    self.push_block(position, length, offset, BlockKind::Aligned);
                    position += i64::from(length);
                    query += u64::from(length);
                }
                INSERTION => {
                    self.push_insertion(position - 1, offset, length);
                    query += u64::from(length);
                }
                DELETION => {
                    placed = true;
                    self.push_block(position, length, offset, BlockKind::Deleted);
                    position += i64::from(length);
                }
                SKIP => {
                    placed = true;
                    self.push_block(position, length, offset, BlockKind::Skipped);
                    position += i64::from(length);
                }
                SOFT_CLIP => query += u64::from(length),
                HARD_CLIP | PAD => {}
                kind => return Err(invalid_data(format!("invalid CIGAR operation kind {kind}"))),
            }
        }
        self.end = position;
        if stored_bases > 0 && stored_bases as u64 != query {
            return Err(invalid_data("CIGAR and query sequence lengths differ"));
        }
        self.query_length = to_offset(query)?;
        Ok(placed)
    }

    fn push_block(&mut self, start: i64, length: u32, query: u32, kind: BlockKind) {
        if length > 0 {
            self.blocks.push(Block {
                start,
                end: start + i64::from(length),
                query,
                kind,
            });
        }
    }

    fn push_insertion(&mut self, anchor: i64, offset: u32, length: u32) {
        match self.insertions.last_mut() {
            Some(last)
                if last.anchor == anchor
                    && u64::from(last.offset) + u64::from(last.length) == u64::from(offset) =>
            {
                last.length = last.length.saturating_add(length);
            }
            Some(last) if last.anchor == anchor => {
                *last = Insertion {
                    anchor,
                    offset,
                    length,
                }
            }
            _ => self.insertions.push(Insertion {
                anchor,
                offset,
                length,
            }),
        }
    }

    /// Hands `push` the entries of the read at a position, moving the cursors forward to it: its
    /// base, deletion, or skip there, with the query offset of its base or next base, [`NONE`]
    /// with no next base, and then the bases it inserts right after the position, with their
    /// offset and length.
    ///
    /// Positions asked of one footprint must never decrease.
    pub fn entries_at(&mut self, pos: i64, mut push: impl FnMut(EntryKind, u32, u32)) {
        match self.locate(pos) {
            Some(Located::Base(offset)) => push(EntryKind::Base, offset, 0),
            Some(Located::Deletion(next)) => push(EntryKind::Deletion, next.unwrap_or(NONE), 0),
            Some(Located::Skip) => {
                let next = self.blocks[self.block].query;
                push(
                    EntryKind::Skip,
                    if next < self.query_length { next } else { NONE },
                    0,
                );
            }
            None => {}
        }
        if let Some(insertion) = self.insertion_at(pos) {
            push(EntryKind::Insertion, insertion.offset, insertion.length);
        }
    }

    /// What the read holds at a position, moving the cursor forward to it.
    ///
    /// Positions asked of one footprint must never decrease.
    pub fn locate(&mut self, pos: i64) -> Option<Located> {
        while let Some(block) = self.blocks.get(self.block)
            && block.end <= pos
        {
            self.block += 1;
        }
        let block = self.blocks.get(self.block)?;
        if block.start > pos {
            return None;
        }
        Some(match block.kind {
            BlockKind::Aligned => Located::Base(block.query + (pos - block.start) as u32),
            BlockKind::Deleted => {
                Located::Deletion((block.query < self.query_length).then_some(block.query))
            }
            BlockKind::Skipped => Located::Skip,
        })
    }

    /// The insertion right after a position, moving the cursor forward to it.
    ///
    /// Positions asked of one footprint must never decrease.
    pub fn insertion_at(&mut self, pos: i64) -> Option<Insertion> {
        while let Some(insertion) = self.insertions.get(self.insertion)
            && insertion.anchor < pos
        {
            self.insertion += 1;
        }
        self.insertions
            .get(self.insertion)
            .filter(|insertion| insertion.anchor == pos)
            .copied()
    }
}

fn to_offset(query: u64) -> io::Result<u32> {
    u32::try_from(query).map_err(|_| invalid_data("a read is longer than 4,294,967,295 bases"))
}