use std::collections::HashMap;
use std::hash::{BuildHasherDefault, DefaultHasher, Hash, Hasher};
use std::sync::OnceLock;
use bstr::{BStr, ByteSlice};
use noodles::bam;
use noodles::sam::alignment::record::Flags;
use crate::auxiliary::{self, AuxElement, AuxValue, Field};
use crate::error::Result;
use crate::footprint::Footprint;
use crate::overlap::{AgreementStrategy, DisagreementStrategy, Observation, Vote};
use crate::source::AlignmentRecord;
use crate::template::{self, Ends};
pub const MISSING_BASE_QUALITY: u8 = 255;
pub(crate) const NONE: u32 = u32::MAX;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum EntryKind {
Base,
Deletion,
Insertion,
Skip,
}
impl EntryKind {
pub fn as_str(self) -> &'static str {
match self {
EntryKind::Base => "base",
EntryKind::Deletion => "deletion",
EntryKind::Insertion => "insertion",
EntryKind::Skip => "skip",
}
}
}
#[derive(Debug)]
pub(crate) struct LiveRecord<R = bam::Record> {
pub record: R,
pub reference_id: usize,
pub start: i64,
pub end: i64,
pub flags: Flags,
pub footprint: Footprint,
pub fields: Vec<Option<Field>>,
pub derived: Derived,
}
impl<R: Default> Default for LiveRecord<R> {
fn default() -> Self {
Self {
record: R::default(),
reference_id: usize::MAX,
start: -1,
end: 0,
flags: Flags::empty(),
footprint: Footprint::default(),
fields: Vec::new(),
derived: Derived::default(),
}
}
}
impl<R: AlignmentRecord> LiveRecord<R> {
pub fn template(&self, slot: u32) -> TemplateName<'_> {
TemplateName::of(self.record.bam(), &self.derived, slot as usize)
}
}
#[derive(Debug, Default)]
pub(crate) struct Derived {
name_hash: OnceLock<u64>,
ends: OnceLock<Option<Ends>>,
}
impl Derived {
fn name_hash(&self, record: &bam::Record) -> u64 {
*self.name_hash.get_or_init(|| {
let mut hasher = DefaultHasher::new();
hasher.write(name_of(record));
hasher.finish()
})
}
pub(crate) fn ends(&self, record: &bam::Record) -> Result<Option<&Ends>> {
if let Some(ends) = self.ends.get() {
return Ok(ends.as_ref());
}
let ends = template::ends(record, &noodles::sam::Header::default())?;
Ok(self.ends.get_or_init(|| ends).as_ref())
}
pub(crate) fn is_fr_pair(&self, record: &bam::Record) -> Result<bool> {
match self.ends(record) {
Ok(ends) => Ok(ends.is_some()),
Err(_) => crate::is_fr_pair(record, &noodles::sam::Header::default()),
}
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct TemplateName<'n> {
hash: u64,
name: Option<&'n [u8]>,
read: usize,
}
impl<'n> TemplateName<'n> {
pub(crate) fn of(record: &'n bam::Record, derived: &Derived, read: usize) -> Self {
let name = record.name().map(|name| name.as_bytes());
Self {
hash: match name {
Some(_) => derived.name_hash(record),
None => read as u64,
},
name,
read,
}
}
}
impl Hash for TemplateName<'_> {
fn hash<H: Hasher>(&self, state: &mut H) {
state.write_u64(self.hash);
}
}
impl PartialEq for TemplateName<'_> {
fn eq(&self, other: &Self) -> bool {
match (self.name, other.name) {
(Some(name), Some(other)) => name == other,
(None, None) => self.read == other.read,
_ => false,
}
}
}
impl Eq for TemplateName<'_> {}
#[derive(Default)]
struct Prehashed(u64);
impl Hasher for Prehashed {
fn finish(&self) -> u64 {
self.0
}
fn write(&mut self, bytes: &[u8]) {
for &byte in bytes {
self.0 = self.0.rotate_left(8) ^ u64::from(byte);
}
}
fn write_u64(&mut self, hash: u64) {
self.0 = hash;
}
}
pub(crate) fn name_of(record: &bam::Record) -> &[u8] {
record.name().map_or(b"*", |name| name.as_bytes())
}
pub(crate) fn number_templates<'n, T>(
entries: &'n [T],
name: impl Fn(&'n T) -> Option<TemplateName<'n>>,
) -> Vec<Option<usize>> {
let mut numbers: HashMap<TemplateName<'n>, usize, BuildHasherDefault<Prehashed>> =
HashMap::with_capacity_and_hasher(entries.len(), BuildHasherDefault::default());
entries
.iter()
.map(|entry| {
let name = name(entry)?;
let next = numbers.len();
Some(*numbers.entry(name).or_insert(next))
})
.collect()
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct RawEntry {
pub slot: u32,
pub kind: EntryKind,
pub offset: u32,
pub length: u32,
}
#[derive(Debug)]
pub struct Pileup<'a, R = bam::Record> {
pub(crate) reference_sequence_id: usize,
pub(crate) reference_sequence_name: &'a BStr,
pub(crate) position: usize,
pub(crate) min_base_quality: u8,
pub(crate) entries: &'a [RawEntry],
pub(crate) slots: &'a [LiveRecord<R>],
pub(crate) aux_tags: &'a [[u8; 2]],
}
impl<R> Clone for Pileup<'_, R> {
fn clone(&self) -> Self {
*self
}
}
impl<R> Copy for Pileup<'_, R> {}
impl<'a, R: AlignmentRecord> Pileup<'a, R> {
pub fn reference_sequence_id(&self) -> usize {
self.reference_sequence_id
}
pub fn reference_sequence_name(&self) -> &'a BStr {
self.reference_sequence_name
}
pub fn position(&self) -> usize {
self.position
}
pub fn min_base_quality(&self) -> u8 {
self.min_base_quality
}
pub fn len(&self) -> usize {
self.entries.len()
}
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
pub fn get(&self, index: usize) -> Option<PileupEntry<'a, R>> {
self.entries.get(index).map(|raw| self.entry(*raw))
}
pub fn iter(&self) -> impl ExactSizeIterator<Item = PileupEntry<'a, R>> + 'a {
let pileup = *self;
self.entries.iter().map(move |raw| pileup.entry(*raw))
}
fn entry(&self, raw: RawEntry) -> PileupEntry<'a, R> {
PileupEntry {
live: &self.slots[raw.slot as usize],
raw,
position: self.position as i64,
aux_tags: self.aux_tags,
}
}
pub fn unfiltered_depth(&self) -> usize {
self.entries
.iter()
.filter(|raw| raw.kind != EntryKind::Insertion)
.count()
}
pub fn filtered_depth(&self) -> usize {
let floor = self.min_base_quality;
self.iter()
.filter(|entry| entry.kind() != EntryKind::Insertion && entry.passes(floor))
.count()
}
pub fn bases(&self) -> impl Iterator<Item = u8> + 'a {
let floor = self.min_base_quality;
self.iter()
.filter(move |entry| entry.passes(floor))
.filter_map(|entry| entry.base())
}
pub fn qualities(&self) -> impl Iterator<Item = u8> + 'a {
let floor = self.min_base_quality;
self.iter()
.filter(|entry| entry.kind() == EntryKind::Base)
.filter_map(|entry| entry.quality())
.filter(move |&quality| quality >= floor)
}
pub fn templates(
&self,
agreement: AgreementStrategy,
disagreement: DisagreementStrategy,
) -> Vec<PileupTemplate<'a, R>> {
let slots = self.slots;
let numbers = number_templates(self.entries, |raw| {
(raw.kind != EntryKind::Insertion).then(|| slots[raw.slot as usize].template(raw.slot))
});
let entries = self
.entries
.iter()
.zip(numbers)
.filter_map(|(raw, number)| {
let entry = self.entry(*raw);
number.map(|number| (number, entry, entry.observation()))
});
templates(
entries,
agreement,
disagreement,
i64::from(self.min_base_quality),
)
.into_iter()
.map(PileupTemplate)
.collect()
}
}
#[derive(Debug)]
pub struct PileupEntry<'a, R = bam::Record> {
pub(crate) live: &'a LiveRecord<R>,
raw: RawEntry,
position: i64,
aux_tags: &'a [[u8; 2]],
}
impl<R> Clone for PileupEntry<'_, R> {
fn clone(&self) -> Self {
*self
}
}
impl<R> Copy for PileupEntry<'_, R> {}
impl<'a, R: AlignmentRecord> PileupEntry<'a, R> {
pub fn record(&self) -> &'a bam::Record {
self.live.record.bam()
}
pub fn source_record(&self) -> &'a R {
&self.live.record
}
pub fn flags(&self) -> Flags {
self.live.flags
}
pub fn kind(&self) -> EntryKind {
self.raw.kind
}
pub fn is_deletion(&self) -> bool {
self.raw.kind == EntryKind::Deletion
}
pub fn is_insertion(&self) -> bool {
self.raw.kind == EntryKind::Insertion
}
pub fn is_skip(&self) -> bool {
self.raw.kind == EntryKind::Skip
}
pub fn is_no_call(&self) -> bool {
self.base() == Some(b'N')
}
pub fn is_reverse(&self) -> bool {
self.live.flags.is_reverse_complemented()
}
pub fn query_position(&self) -> Option<usize> {
(self.raw.kind == EntryKind::Base).then_some(self.raw.offset as usize)
}
pub fn query_position_or_next(&self) -> Option<usize> {
match self.raw.kind {
EntryKind::Base | EntryKind::Deletion if self.raw.offset != NONE => {
Some(self.raw.offset as usize)
}
_ => None,
}
}
pub fn insertion_offset(&self) -> Option<usize> {
(self.raw.kind == EntryKind::Insertion).then_some(self.raw.offset as usize)
}
pub fn insertion_length(&self) -> usize {
if self.raw.kind == EntryKind::Insertion {
self.raw.length as usize
} else {
0
}
}
pub fn base(&self) -> Option<u8> {
self.query_position()
.and_then(|offset| self.record().sequence().get(offset))
}
pub fn sequenced_base(&self) -> Option<u8> {
let base = self.base()?;
Some(if self.is_reverse() {
complement(base)
} else {
base
})
}
pub fn quality(&self) -> Option<u8> {
quality_of(self.record(), self.raw.kind, self.raw.offset)
}
pub fn passes(&self, min_base_quality: u8) -> bool {
self.quality()
.is_some_and(|quality| quality >= min_base_quality)
}
pub(crate) fn observation(&self) -> Observation {
Observation {
kind: self.kind(),
base: self.base(),
quality: self.quality(),
}
}
pub fn inserted_bases(&self) -> Option<impl Iterator<Item = u8> + 'a> {
let offset = self.insertion_offset()?;
let sequence = self.record().sequence();
if sequence.is_empty() {
return None;
}
let end = (offset + self.insertion_length()).min(sequence.len());
Some((offset.min(end)..end).filter_map(move |index| sequence.get(index)))
}
pub fn inserted_qualities(&self) -> Option<impl Iterator<Item = u8> + 'a> {
let offset = self.insertion_offset()?;
let record = self.record();
let stored = record.sequence().len();
if stored == 0 {
return None;
}
let qualities = record.quality_scores().as_bytes();
let length = self.insertion_length();
let (bytes, missing): (&'a [u8], usize) = if qualities.is_empty() {
(&[], length)
} else {
let end = (offset + length).min(qualities.len());
(&qualities[offset.min(end)..end], 0)
};
Some(
bytes
.iter()
.copied()
.chain(std::iter::repeat_n(MISSING_BASE_QUALITY, missing)),
)
}
pub fn five_prime_distance(&self) -> Option<usize> {
let length = self.live.footprint.query_length as usize;
let offset = (self.raw.offset != NONE).then_some(self.raw.offset as usize);
crate::template::entry_from_five_prime(self.raw.kind, self.is_reverse(), length, offset)
}
pub fn template_end_distance(&self) -> Result<Option<usize>> {
let ends = self.live.derived.ends(self.record())?;
Ok(ends.and_then(|ends| ends.distance(self.position as usize)))
}
pub fn is_fr_pair(&self) -> Result<bool> {
self.live.derived.is_fr_pair(self.record())
}
pub fn aux(&self, tag: [u8; 2]) -> Result<Option<AuxValue<'a>>> {
let data = self.record().data().as_bytes();
match self.aux_tags.iter().position(|indexed| *indexed == tag) {
Some(index) => match self.live.fields.get(index).copied().flatten() {
Some(field) => field.value(data).map(Some),
None => Ok(None),
},
None => auxiliary::find(data, tag),
}
}
pub fn aux_at(&self, tag: [u8; 2]) -> Result<Option<AuxElement>> {
let Some(offset) = self.query_position() else {
return Ok(None);
};
Ok(self.aux(tag)?.and_then(|value| value.get(offset)))
}
}
pub(crate) trait TemplateRead {
fn flags(&self) -> Flags;
fn five_prime_distance(&self) -> Option<usize>;
fn template_end_distance(&self) -> Result<Option<usize>>;
fn is_fr_pair(&self) -> Result<bool>;
}
impl<R: AlignmentRecord> TemplateRead for PileupEntry<'_, R> {
fn flags(&self) -> Flags {
PileupEntry::flags(self)
}
fn five_prime_distance(&self) -> Option<usize> {
PileupEntry::five_prime_distance(self)
}
fn template_end_distance(&self) -> Result<Option<usize>> {
PileupEntry::template_end_distance(self)
}
fn is_fr_pair(&self) -> Result<bool> {
PileupEntry::is_fr_pair(self)
}
}
#[derive(Clone, Debug)]
pub(crate) struct Template<E> {
first: E,
second: Option<E>,
others: Vec<E>,
vote: Vote,
}
impl<E> Template<E> {
fn of(entry: E) -> Self {
Self {
first: entry,
second: None,
others: Vec::new(),
vote: Vote::default(),
}
}
fn push(&mut self, entry: E) {
if self.second.is_none() {
self.second = Some(entry);
} else {
self.others.push(entry);
}
}
pub(crate) fn first(&self) -> &E {
&self.first
}
pub(crate) fn entries(&self) -> impl Iterator<Item = &E> {
std::iter::once(&self.first)
.chain(&self.second)
.chain(&self.others)
}
pub(crate) fn called(&self) -> Observation {
self.vote.result()
}
}
impl<E: TemplateRead> Template<E> {
pub(crate) fn is_reverse(&self) -> bool {
match self.first_read() {
Some(first) => first.flags().is_reverse_complemented(),
None => self.first.flags().is_mate_reverse_complemented(),
}
}
pub(crate) fn five_prime_distance(&self) -> Result<Option<usize>> {
if let Some(distance) = self
.first_read()
.and_then(TemplateRead::five_prime_distance)
{
return Ok(Some(distance));
}
match self.second_read() {
Some(second) => second.template_end_distance(),
None => Ok(None),
}
}
pub(crate) fn template_end_distance(&self) -> Result<Option<usize>> {
match self.first_read() {
Some(first) => first.template_end_distance(),
None if self.first.is_fr_pair()? => Ok(self.first.five_prime_distance()),
None => Ok(None),
}
}
fn first_read(&self) -> Option<&E> {
self.entries().find(|entry| !is_second(entry.flags()))
}
fn second_read(&self) -> Option<&E> {
self.entries().find(|entry| is_second(entry.flags()))
}
}
pub(crate) fn templates<E>(
entries: impl IntoIterator<Item = (usize, E, Observation)>,
agreement: AgreementStrategy,
disagreement: DisagreementStrategy,
min_base_quality: i64,
) -> Vec<Template<E>> {
let mut templates: Vec<Template<E>> = Vec::new();
for (number, entry, observation) in entries {
if let Some(template) = templates.get_mut(number) {
template.push(entry);
} else {
templates.push(Template::of(entry));
}
templates[number]
.vote
.add(observation, agreement, disagreement, min_base_quality);
}
templates
}
#[derive(Debug)]
pub struct PileupTemplate<'a, R = bam::Record>(Template<PileupEntry<'a, R>>);
impl<R> Clone for PileupTemplate<'_, R> {
fn clone(&self) -> Self {
Self(self.0.clone())
}
}
impl<'a, R: AlignmentRecord> PileupTemplate<'a, R> {
pub fn name(&self) -> &'a BStr {
name_of(self.0.first().record()).as_bstr()
}
pub fn entries(&self) -> impl Iterator<Item = PileupEntry<'a, R>> + '_ {
self.0.entries().copied()
}
pub fn kind(&self) -> EntryKind {
self.0.called().kind
}
pub fn is_deletion(&self) -> bool {
self.kind() == EntryKind::Deletion
}
pub fn is_skip(&self) -> bool {
self.kind() == EntryKind::Skip
}
pub fn is_no_call(&self) -> bool {
self.base() == Some(b'N')
}
pub fn base(&self) -> Option<u8> {
self.0.called().base
}
pub fn quality(&self) -> Option<u8> {
self.0.called().quality
}
pub fn passes(&self, min_base_quality: u8) -> bool {
self.quality()
.is_some_and(|quality| quality >= min_base_quality)
}
pub fn is_reverse(&self) -> bool {
self.0.is_reverse()
}
pub fn five_prime_distance(&self) -> Result<Option<usize>> {
self.0.five_prime_distance()
}
pub fn template_end_distance(&self) -> Result<Option<usize>> {
self.0.template_end_distance()
}
}
fn is_second(flags: Flags) -> bool {
flags.is_segmented() && flags.is_last_segment()
}
pub(crate) fn quality_of(record: &bam::Record, kind: EntryKind, offset: u32) -> Option<u8> {
if offset == NONE || !matches!(kind, EntryKind::Base | EntryKind::Deletion) {
return None;
}
let offset = offset as usize;
let qualities = record.quality_scores().as_bytes();
if qualities.is_empty() {
(offset < record.sequence().len()).then_some(MISSING_BASE_QUALITY)
} else {
qualities.get(offset).copied()
}
}
fn complement(base: u8) -> u8 {
match base {
b'A' => b'T',
b'C' => b'G',
b'G' => b'C',
b'T' => b'A',
b'M' => b'K',
b'K' => b'M',
b'R' => b'Y',
b'Y' => b'R',
b'B' => b'V',
b'V' => b'B',
b'D' => b'H',
b'H' => b'D',
other => other,
}
}
pub(crate) fn record_name<R: noodles::sam::alignment::Record + ?Sized>(record: &R) -> String {
record
.name()
.map_or_else(|| "*".to_owned(), |name| name.to_str_lossy().into_owned())
}