use std::collections::VecDeque;
use std::io;
use std::mem;
use bstr::{BStr, ByteSlice};
use noodles::sam::{self, alignment::record::Cigar as _, alignment::record::Flags};
use crate::auxiliary;
use crate::error::{Error, Result};
use crate::footprint::Footprint;
use crate::pileup::{Derived, LiveRecord, Pileup, RawEntry, record_name};
use crate::source::{AlignmentRecord, RecordSource};
pub const DEFAULT_EXCLUDE_FLAGS: Flags = Flags::from_bits_retain(0xF00);
pub const DEFAULT_MIN_BASE_QUALITY: u8 = 13;
const UNPLACED: usize = usize::MAX;
type ReadFilter<'f, R> = Box<dyn FnMut(&R) -> io::Result<bool> + Send + 'f>;
type Tap<'f, R> = Box<dyn FnMut(R) -> io::Result<()> + Send + 'f>;
#[derive(Clone, Debug)]
struct Options {
min_mapping_quality: u8,
exclude_flags: Flags,
min_base_quality: u8,
proper_pairs_only: bool,
aux_tags: Vec<[u8; 2]>,
}
impl Options {
fn passes(&self, flags: Flags, mapping_quality: u8) -> bool {
let paired = flags.is_properly_segmented() || !self.proper_pairs_only;
paired
&& passes(
flags,
mapping_quality,
self.exclude_flags,
self.min_mapping_quality,
)
}
}
pub(crate) fn passes(
flags: Flags,
mapping_quality: u8,
exclude_flags: Flags,
min_mapping_quality: u8,
) -> bool {
!(flags.is_unmapped()
|| flags.intersects(exclude_flags)
|| mapping_quality < min_mapping_quality)
}
fn admits<R: AlignmentRecord>(
options: &Options,
read_filter: Option<&mut ReadFilter<'_, R>>,
record: &R,
start: i64,
footprint: &mut Footprint,
) -> Result<bool> {
let bam = record.bam();
let mapping_quality = bam.mapping_quality().map_or(255, u8::from);
if bam.reference_sequence_id().is_none()
|| start < 0
|| !options.passes(bam.flags(), mapping_quality)
{
return Ok(false);
}
let placed = footprint
.fill(start, bam.cigar().as_bytes(), bam.sequence().len())
.map_err(|source| Error::InvalidRecord {
name: record_name(bam),
source,
})?;
Ok(placed
&& match read_filter {
Some(read_filter) => read_filter(record)?,
None => true,
})
}
impl Default for Options {
fn default() -> Self {
Self {
min_mapping_quality: 0,
exclude_flags: DEFAULT_EXCLUDE_FLAGS,
min_base_quality: DEFAULT_MIN_BASE_QUALITY,
proper_pairs_only: false,
aux_tags: Vec::new(),
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Stage {
Open,
Stopped,
Closing,
Closed,
}
pub struct StreamingPileupBuilder<'f, S: RecordSource> {
source: S,
header: sam::Header,
options: Options,
read_filter: Option<ReadFilter<'f, S::Record>>,
tap: Option<Tap<'f, S::Record>>,
pub(crate) slots: Vec<LiveRecord<S::Record>>,
pub(crate) free: Vec<u32>,
pub(crate) active: Vec<u32>,
pub(crate) waiting: VecDeque<u32>,
pub(crate) next: Option<u32>,
exhausted: bool,
active_reference_id: usize,
min_active_end: i64,
last_key: (usize, i64),
at: Option<(usize, usize)>,
built: bool,
entries: Vec<RawEntry>,
stage: Stage,
}
impl<'f, S: RecordSource> StreamingPileupBuilder<'f, S> {
pub fn new(source: S, header: &sam::Header) -> Result<Self> {
use sam::header::record::value::map::header::tag::SORT_ORDER;
let sort_order = header
.header()
.and_then(|map| map.other_fields().get(&SORT_ORDER));
if sort_order.is_none_or(|order| order.as_bytes() != b"coordinate") {
return Err(Error::NotCoordinateSorted {
found: sort_order.map(|order| order.to_str_lossy().into_owned()),
});
}
Ok(Self {
source,
header: header.clone(),
options: Options::default(),
read_filter: None,
tap: None,
slots: Vec::new(),
free: Vec::new(),
active: Vec::new(),
waiting: VecDeque::new(),
next: None,
exhausted: false,
active_reference_id: UNPLACED,
min_active_end: i64::MAX,
last_key: (0, i64::MIN),
at: None,
built: false,
entries: Vec::new(),
stage: Stage::Open,
})
}
#[must_use]
pub fn min_mapping_quality(mut self, min_mapping_quality: u8) -> Self {
self.options.min_mapping_quality = min_mapping_quality;
self
}
#[must_use]
pub fn exclude_flags(mut self, exclude_flags: Flags) -> Self {
self.options.exclude_flags = exclude_flags;
self
}
#[must_use]
pub fn min_base_quality(mut self, min_base_quality: u8) -> Self {
self.options.min_base_quality = min_base_quality;
self
}
#[must_use]
pub fn proper_pairs_only(mut self, proper_pairs_only: bool) -> Self {
self.options.proper_pairs_only = proper_pairs_only;
self
}
#[must_use]
pub fn index_aux_tags(mut self, tags: impl IntoIterator<Item = [u8; 2]>) -> Self {
self.options.aux_tags = tags.into_iter().collect();
self
}
#[must_use]
pub fn read_filter(self, mut read_filter: impl FnMut(&S::Record) -> bool + Send + 'f) -> Self {
self.try_read_filter(move |record| Ok(read_filter(record)))
}
#[must_use]
pub(crate) fn try_read_filter(
mut self,
read_filter: impl FnMut(&S::Record) -> io::Result<bool> + Send + 'f,
) -> Self {
self.read_filter = Some(Box::new(read_filter));
self
}
#[must_use]
pub fn tap(mut self, tap: impl FnMut(S::Record) -> io::Result<()> + Send + 'f) -> Self {
self.tap = Some(Box::new(tap));
self
}
pub fn header(&self) -> &sam::Header {
&self.header
}
pub fn accepts(&mut self, record: &S::Record) -> Result<bool> {
let bam = record.bam();
let start = bam
.alignment_start()
.transpose()
.map_err(|source| Error::InvalidRecord {
name: record_name(bam),
source,
})?
.map_or(-1, |start| usize::from(start) as i64 - 1);
let read_filter = self.read_filter.as_mut();
admits(
&self.options,
read_filter,
record,
start,
&mut Footprint::default(),
)
}
pub fn pileup(&mut self, contig: &str, position: usize) -> Result<Pileup<'_, S::Record>> {
self.check_open()?;
let reference_sequence_id = self.reference_sequence_id(contig)?;
self.pileup_at(reference_sequence_id, position)
}
pub fn pileup_at(
&mut self,
reference_sequence_id: usize,
position: usize,
) -> Result<Pileup<'_, S::Record>> {
self.check_open()?;
if self.built && self.at == Some((reference_sequence_id, position)) {
return Ok(self.view(reference_sequence_id, position));
}
if reference_sequence_id >= self.header.reference_sequences().len() {
return Err(Error::UnknownReferenceSequenceId(reference_sequence_id));
}
if let Some((from_id, from_position)) = self.at
&& (reference_sequence_id, position) < (from_id, from_position)
{
return Err(Error::Backwards {
contig: self.name_of(reference_sequence_id).to_string(),
position,
from_contig: self.name_of(from_id).to_string(),
from_position,
});
}
self.at = Some((reference_sequence_id, position));
self.built = false;
if let Err(error) = self.advance(reference_sequence_id, position as i64) {
self.stage = Stage::Stopped;
return Err(error);
}
self.collect(position as i64);
self.built = true;
Ok(self.view(reference_sequence_id, position))
}
pub fn columns(
&mut self,
contig: &str,
start: usize,
end: usize,
) -> Result<Columns<'_, 'f, S>> {
let reference_sequence_id = self.reference_sequence_id(contig)?;
self.columns_at(reference_sequence_id, start, end)
}
pub fn columns_at(
&mut self,
reference_sequence_id: usize,
start: usize,
end: usize,
) -> Result<Columns<'_, 'f, S>> {
if end < start {
return Err(Error::InvalidSpan { start, end });
}
Ok(Columns {
builder: self,
reference_sequence_id,
next: start,
end,
})
}
pub fn close(&mut self) -> Result<()> {
if self.stage == Stage::Closed {
return Ok(());
}
self.stage = Stage::Closing;
self.built = false;
self.active.clear();
self.entries.clear();
if let Some(tap) = self.tap.as_mut() {
while let Some(index) = self.waiting.pop_front() {
tap(mem::take(&mut self.slots[index as usize].record))?;
}
if let Some(index) = self.next.take() {
tap(mem::take(&mut self.slots[index as usize].record))?;
}
if !self.exhausted {
let mut record = S::Record::default();
while self.source.read_record(&mut record)? {
tap(mem::take(&mut record))?;
}
self.exhausted = true;
}
}
self.slots.clear();
self.free.clear();
self.waiting.clear();
self.next = None;
self.stage = Stage::Closed;
Ok(())
}
#[cfg(feature = "python")]
pub(crate) fn abandon(&mut self) {
self.stage = Stage::Closed;
self.built = false;
self.active.clear();
self.entries.clear();
self.slots.clear();
self.free.clear();
self.waiting.clear();
self.next = None;
}
fn check_open(&self) -> Result<()> {
match self.stage {
Stage::Open => Ok(()),
Stage::Stopped => Err(Error::Stopped),
Stage::Closing | Stage::Closed => Err(Error::Closed),
}
}
fn reference_sequence_id(&self, contig: &str) -> Result<usize> {
self.header
.reference_sequences()
.get_index_of(contig.as_bytes().as_bstr())
.ok_or_else(|| Error::UnknownContig(contig.to_owned()))
}
fn name_of(&self, reference_sequence_id: usize) -> &BStr {
self.header
.reference_sequences()
.get_index(reference_sequence_id)
.map_or(b"".as_bstr(), |(name, _)| name.as_bstr())
}
fn view(&self, reference_sequence_id: usize, position: usize) -> Pileup<'_, S::Record> {
Pileup {
reference_sequence_id,
reference_sequence_name: self.name_of(reference_sequence_id),
position,
min_base_quality: self.options.min_base_quality,
entries: &self.entries,
slots: &self.slots,
aux_tags: &self.options.aux_tags,
}
}
fn free(&mut self, index: u32) {
self.slots[index as usize].record.release();
self.free.push(index);
}
fn advance(&mut self, reference_sequence_id: usize, pos: i64) -> Result<()> {
if reference_sequence_id != self.active_reference_id {
self.evict(None);
self.active_reference_id = reference_sequence_id;
} else if self.min_active_end <= pos {
self.evict(Some(pos));
}
let target = (reference_sequence_id, pos + 1);
while let Some(index) = self.peek()? {
let live = &self.slots[index as usize];
let key = (live.reference_id, live.start);
if key > target {
break;
}
if key < self.last_key {
return Err(Error::OutOfOrder {
name: record_name(live.record.bam()),
});
}
self.last_key = key;
self.next = None;
let accepted = if key.0 == reference_sequence_id {
self.accept(index, pos)
} else {
Ok(false)
};
if self.tap.is_some() {
self.waiting.push_back(index);
}
if let Ok(true) = accepted {
self.activate(index);
} else if self.tap.is_none() {
self.free(index);
}
accepted?;
}
self.release(reference_sequence_id, pos)
}
fn peek(&mut self) -> Result<Option<u32>> {
if self.next.is_some() || self.exhausted {
return Ok(self.next);
}
let index = if let Some(index) = self.free.pop() {
index
} else {
self.slots.push(LiveRecord::default());
u32::try_from(self.slots.len() - 1)
.map_err(|_| io::Error::other("more than 4,294,967,295 records are held"))?
};
let tapped = self.tap.is_some();
let live = &mut self.slots[index as usize];
match self.source.read_record(&mut live.record) {
Ok(true) => {
if let Err(error) = describe(live, tapped) {
live.reference_id = UNPLACED;
if tapped {
self.waiting.push_back(index);
} else {
self.free(index);
}
return Err(error.into());
}
self.next = Some(index);
}
read => {
self.free(index);
read?;
self.exhausted = true;
}
}
Ok(self.next)
}
fn accept(&mut self, index: u32, pos: i64) -> Result<bool> {
let live = &mut self.slots[index as usize];
let read_filter = self.read_filter.as_mut();
let admitted = admits(
&self.options,
read_filter,
&live.record,
live.start,
&mut live.footprint,
)?;
if !admitted || live.footprint.end <= pos {
return Ok(false);
}
live.derived = Derived::default();
index_fields(live, &self.options.aux_tags).map_err(|error| match error {
Error::Io(source) => Error::InvalidRecord {
name: record_name(live.record.bam()),
source,
},
error => error,
})?;
Ok(true)
}
fn activate(&mut self, index: u32) {
let end = self.slots[index as usize].footprint.end;
self.min_active_end = self.min_active_end.min(end);
self.active.push(index);
}
fn evict(&mut self, before: Option<i64>) {
let mut active = mem::take(&mut self.active);
let mut kept = 0;
let mut min_end = i64::MAX;
for at in 0..active.len() {
let index = active[at];
let end = self.slots[index as usize].footprint.end;
if before.is_some_and(|pos| end > pos) {
active[kept] = index;
kept += 1;
min_end = min_end.min(end);
} else if self.tap.is_none() {
self.free(index);
}
}
active.truncate(kept);
self.active = active;
self.min_active_end = min_end;
}
fn release(&mut self, reference_sequence_id: usize, pos: i64) -> Result<()> {
let Some(tap) = self.tap.as_mut() else {
return Ok(());
};
while let Some(&index) = self.waiting.front() {
let live = &mut self.slots[index as usize];
let passed = live.reference_id < reference_sequence_id
|| (live.reference_id == reference_sequence_id && live.end <= pos);
if !passed {
break;
}
self.waiting.pop_front();
let record = mem::take(&mut live.record);
self.free.push(index);
tap(record)?;
}
Ok(())
}
fn collect(&mut self, pos: i64) {
self.entries.clear();
let entries = &mut self.entries;
for &index in &self.active {
self.slots[index as usize]
.footprint
.entries_at(pos, |kind, offset, length| {
entries.push(RawEntry {
slot: index,
kind,
offset,
length,
});
});
}
}
}
impl<S: RecordSource> Drop for StreamingPileupBuilder<'_, S> {
fn drop(&mut self) {
if !std::thread::panicking() {
let _ = self.close();
}
}
}
pub struct Columns<'b, 'f, S: RecordSource> {
builder: &'b mut StreamingPileupBuilder<'f, S>,
reference_sequence_id: usize,
next: usize,
end: usize,
}
impl<S: RecordSource> Columns<'_, '_, S> {
pub fn next_pileup(&mut self) -> Option<Result<Pileup<'_, S::Record>>> {
if self.next >= self.end {
return None;
}
let position = self.next;
self.next += 1;
Some(self.builder.pileup_at(self.reference_sequence_id, position))
}
}
fn describe<R: AlignmentRecord>(live: &mut LiveRecord<R>, tapped: bool) -> io::Result<()> {
let record = live.record.bam();
live.reference_id = record
.reference_sequence_id()
.transpose()?
.unwrap_or(UNPLACED);
live.start = record
.alignment_start()
.transpose()?
.map_or(-1, |start| usize::from(start) as i64 - 1);
live.flags = record.flags();
if tapped {
let cigar = record.cigar();
let length = if live.flags.is_unmapped() || cigar.is_empty() {
1
} else {
cigar.alignment_span()?.max(1) as i64
};
live.end = live.start + length;
}
Ok(())
}
fn index_fields<R: AlignmentRecord>(live: &mut LiveRecord<R>, tags: &[[u8; 2]]) -> Result<()> {
live.fields.clear();
live.fields.resize(tags.len(), None);
if tags.is_empty() {
return Ok(());
}
let fields = &mut live.fields;
auxiliary::walk(live.record.bam().data().as_bytes(), |tag, field| {
if let Some(index) = tags.iter().position(|wanted| *wanted == tag)
&& fields[index].is_none()
{
fields[index] = Some(field);
}
})?;
Ok(())
}