use crate::core::core_types::{Edge, NodeId, Nodes, Orientation};
use crate::error::{PanGraphXError, PanResult};
use crate::formats::odgi::encoding::{Fields, le_u64, truncated_file};
use crate::formats::odgi::reader::paths::StepLink;
use crate::formats::odgi::{
EDGE_ON_REV, EDGE_OTHER_REV, EDGE_RECORD_LEN, EDGE_TO_CURR, MAX_STEP_RANK, STEP_END,
STEP_RECORD_LEN, STEP_REV, VACANT,
};
use rayon::prelude::*;
use std::io::Read;
pub(super) const MIN_RECORD_BYTES: u64 = 8 + 8 + 3 * (8 + 8 + 8 + 1 + 1);
pub(in crate::formats::odgi) struct RecordSpan {
pub(in crate::formats::odgi) start: usize,
pub(in crate::formats::odgi) end: usize,
pub(in crate::formats::odgi) steps: usize,
}
pub(in crate::formats::odgi) fn scan_record(bytes: &[u8], start: usize) -> Result<RecordSpan, u64> {
let field = |pos: u64| {
usize::try_from(pos)
.ok()
.and_then(|pos| pos.checked_add(start))
.and_then(|pos| bytes.get(pos..pos.checked_add(8)?))
.map(le_u64)
};
let sequence_len = field(0).ok_or(8_u64)?;
let id_pos = 8_u64.saturating_add(sequence_len);
let id = field(id_pos).ok_or_else(|| id_pos.saturating_add(8))?;
let mut pos = id_pos + 8;
let mut step_values = 0;
for _ in 0..3 {
let word_count = field(pos).ok_or_else(|| pos.saturating_add(8))?;
let len_pos = pos
.saturating_add(8)
.saturating_add(word_count.saturating_mul(8))
.saturating_add(8);
let len = field(len_pos).ok_or_else(|| len_pos.saturating_add(8))?;
let width = usize::try_from(len_pos.saturating_add(8))
.ok()
.and_then(|width_pos| bytes.get(width_pos.checked_add(start)?))
.map_or(0, |&width| u64::from(width));
let capacity = match width {
1..=64 => word_count.saturating_mul(64 / width),
_ => 0,
};
step_values = len.min(capacity);
pos = len_pos.saturating_add(8 + 1 + 1);
}
let end = usize::try_from(pos)
.ok()
.and_then(|size| size.checked_add(start))
.filter(|&end| end <= bytes.len())
.ok_or(pos)?;
let steps = if id == 0 {
0
} else {
usize::try_from(step_values).unwrap_or(usize::MAX) / STEP_RECORD_LEN
};
Ok(RecordSpan { start, end, steps })
}
pub(in crate::formats::odgi) const BLOCK_BYTES: usize = 16 << 20;
#[derive(Clone, Copy)]
pub(super) struct RecordContext {
pub(super) record_count: usize,
pub(super) id_increment: u64,
}
impl RecordContext {
#[allow(clippy::cast_possible_truncation)]
pub(super) fn rank(self, id: u64) -> PanResult<u32> {
id.checked_sub(self.id_increment)
.and_then(|id| id.checked_sub(1))
.filter(|&rank| rank < self.record_count as u64)
.map(|rank| rank as u32)
.ok_or_else(|| PanGraphXError::Parse(format!("ODGI node id {id} is out of range")))
}
}
#[derive(Default)]
pub(super) struct DecodedRecords {
sequences: Vec<Option<Vec<u8>>>,
edges: Vec<Edge>,
}
#[derive(Default)]
pub(super) struct RecordScratch {
edges: Vec<u64>,
decoding: Vec<u64>,
steps: Vec<u64>,
}
impl DecodedRecords {
fn decode(
&mut self,
bytes: &[u8],
rank: usize,
context: RecordContext,
scratch: &mut RecordScratch,
links: &mut [StepLink],
) -> PanResult<()> {
let mut fields = Fields { bytes };
let sequence_len = fields.len("sequence length")?;
let sequence = fields.take(sequence_len)?;
let stored_id = fields.u64()?;
fields.packed(&mut scratch.edges)?;
fields.packed(&mut scratch.decoding)?;
fields.packed(&mut scratch.steps)?;
if stored_id == 0 {
self.sequences.push(None);
return Ok(());
}
self.sequences.push(Some(sequence.to_vec()));
let odgi_id = rank as u64 + 1 + context.id_increment;
let invalid = |what: &str| PanGraphXError::Parse(format!("ODGI node {odgi_id} has {what}"));
let (edge_records, edge_rest) = scratch.edges.as_chunks::<EDGE_RECORD_LEN>();
if !edge_rest.is_empty() {
return Err(invalid("an incomplete edge record"));
}
for &[other, packed] in edge_records {
if packed & EDGE_TO_CURR != 0 {
continue;
}
self.edges.push(Edge {
from_node: rank,
from_orient: Orientation::from(packed & EDGE_ON_REV != 0),
to_node: context.rank(other)? as usize,
to_orient: Orientation::from(packed & EDGE_OTHER_REV != 0),
overlap: 0,
});
}
let (step_records, step_rest) = scratch.steps.as_chunks::<STEP_RECORD_LEN>();
if !step_rest.is_empty() || step_records.len() != links.len() {
return Err(invalid("an incomplete step record"));
}
for (record, link) in step_records.iter().zip(links) {
let step_type = record[1];
let is_reverse = u32::from(step_type & STEP_REV != 0);
if step_type & STEP_END != 0 {
*link = StepLink {
next_node: StepLink::END,
rank_rev: is_reverse,
};
continue;
}
let delta = usize::try_from(record[4])
.ok()
.and_then(|index| scratch.decoding.get(index))
.ok_or_else(|| invalid("a step with an invalid neighbor"))?;
let next_id = match delta {
0 => Some(stored_id),
d if d & 1 == 1 => stored_id.checked_add(d >> 1),
d => stored_id.checked_sub(d >> 1),
}
.ok_or_else(|| invalid("an invalid neighbor"))?;
let next_rank = u32::try_from(record[5])
.ok()
.filter(|&rank| rank <= MAX_STEP_RANK)
.ok_or_else(|| invalid("an invalid step rank"))?;
*link = StepLink {
next_node: context.rank(next_id)?,
rank_rev: next_rank << 1 | is_reverse,
};
}
Ok(())
}
}
pub(super) struct NodeSection {
pub(super) nodes: Nodes,
pub(super) edges: Vec<Edge>,
pub(super) offsets: Vec<usize>,
pub(super) links: Vec<StepLink>,
pub(super) rank_to_node: Vec<NodeId>,
}
pub(super) fn split_links<'a>(
mut links: &'a mut [StepLink],
chunks: std::slice::Chunks<'_, RecordSpan>,
) -> PanResult<Vec<&'a mut [StepLink]>> {
let mut parts = Vec::with_capacity(chunks.len());
for chunk in chunks {
let steps = chunk.iter().map(|span| span.steps).sum();
let (part, rest) = links
.split_at_mut_checked(steps)
.ok_or_else(truncated_file)?;
parts.push(part);
links = rest;
}
Ok(parts)
}
pub(super) fn next_block<R: Read>(
reader: &mut R,
buf: &mut Vec<u8>,
input_left: &mut u64,
records_left: usize,
) -> PanResult<Vec<RecordSpan>> {
let mut want = BLOCK_BYTES.saturating_sub(buf.len()) as u64;
let mut spans: Vec<RecordSpan> = Vec::new();
loop {
if want > 0 {
let request = want.min(*input_left);
let got = reader.by_ref().take(request).read_to_end(buf)? as u64;
*input_left = if got < request { 0 } else { *input_left - got };
want = 0;
}
let mut pos = 0;
while spans.len() < records_left {
match scan_record(buf, pos) {
Ok(span) => {
pos = span.end;
spans.push(span);
}
Err(needed) => {
if spans.is_empty() {
let missing = needed.saturating_sub(buf.len() as u64);
if missing > *input_left {
return Err(truncated_file());
}
want = missing;
}
break;
}
}
}
if !spans.is_empty() {
return Ok(spans);
}
}
}
impl NodeSection {
fn merge(&mut self, decoded: DecodedRecords, spans: &[RecordSpan]) {
for (sequence, span) in decoded.sequences.into_iter().zip(spans) {
match sequence {
Some(sequence) => {
self.rank_to_node.push(self.nodes.len());
self.nodes.push(sequence);
}
None => self.rank_to_node.push(VACANT),
}
let end = self.offsets.last().copied().unwrap_or_default() + span.steps;
self.offsets.push(end);
}
self.edges.extend(decoded.edges);
}
pub(super) fn decode_block(
&mut self,
buf: &[u8],
spans: &[RecordSpan],
first_rank: usize,
context: RecordContext,
) -> PanResult<()> {
let block_steps = spans
.iter()
.try_fold(0_usize, |sum, span| sum.checked_add(span.steps))
.filter(|&steps| steps as u64 <= buf.len() as u64 * 8)
.ok_or_else(truncated_file)?;
let base = self.links.len();
self.links.resize(
base + block_steps,
StepLink {
next_node: StepLink::END,
rank_rev: 0,
},
);
let per_task = spans.len().div_ceil(rayon::current_num_threads() * 4);
let parts = split_links(&mut self.links[base..], spans.chunks(per_task))?;
let decoded = spans
.par_chunks(per_task)
.zip(parts)
.enumerate()
.map(|(task, (chunk, mut links))| {
let mut decoded = DecodedRecords::default();
let mut scratch = RecordScratch::default();
for (i, span) in chunk.iter().enumerate() {
let (record_links, rest) = links
.split_at_mut_checked(span.steps)
.ok_or_else(truncated_file)?;
links = rest;
decoded.decode(
&buf[span.start..span.end],
first_rank + task * per_task + i,
context,
&mut scratch,
record_links,
)?;
}
Ok(decoded)
})
.collect::<PanResult<Vec<_>>>()?;
for (decoded, chunk) in decoded.into_iter().zip(spans.chunks(per_task)) {
self.merge(decoded, chunk);
}
Ok(())
}
pub(super) fn resolve_edges(&mut self) -> PanResult<()> {
for edge in &mut self.edges {
let (Some(&from), Some(&to)) = (
self.rank_to_node.get(edge.from_node),
self.rank_to_node.get(edge.to_node),
) else {
return Err(PanGraphXError::Parse(
"ODGI edge refers to a missing node".to_string(),
));
};
if to == VACANT {
return Err(PanGraphXError::Parse(
"ODGI edge refers to a deleted node".to_string(),
));
}
(edge.from_node, edge.to_node) = (from, to);
}
Ok(())
}
}