mod edges;
mod numbering;
mod steps;
#[cfg(test)]
pub(super) use edges::SMALL_NODE_DEGREE;
#[cfg(test)]
pub(super) use steps::MAX_RANK_HINTS;
use crate::core::core_types::NodeId;
use crate::core::graph_dto::CoreGraphDTO;
use crate::error::PanResult;
use crate::formats::odgi::encoding::{push_packed, push_u64};
use crate::formats::odgi::{ODGI_MAGIC, STEP_END, STEP_START};
use edges::{EDGE_TYPE_BITS, EdgeIndex};
use log::warn;
use numbering::Numbering;
use rayon::prelude::*;
use rustc_hash::FxHashMap;
use std::io::Write;
use steps::{StepIndex, StepNumber};
const CHUNK_BYTES: usize = 1 << 20;
const MAX_WINDOW_CHUNKS: usize = 64;
pub(super) const SMALL_DECODING: usize = 16;
#[derive(Default)]
struct Scratch {
values: Vec<u64>,
prev_hints: Vec<(NodeId, usize)>,
next_hints: Vec<(NodeId, usize)>,
decoding: Vec<u64>,
decoding_index: FxHashMap<u64, u64>,
}
impl Scratch {
fn clear_decoding(&mut self) {
if self.decoding.len() > SMALL_DECODING {
self.decoding_index.clear();
}
self.decoding.clear();
}
fn encode(&mut self, own_id: u64, other_id: u64) -> u64 {
let delta = match other_id.cmp(&own_id) {
std::cmp::Ordering::Equal => 0,
std::cmp::Ordering::Greater => (other_id - own_id) << 1 | 1,
std::cmp::Ordering::Less => (own_id - other_id) << 1,
};
let next = self.decoding.len() as u64;
if self.decoding.len() <= SMALL_DECODING {
if let Some(index) = self.decoding.iter().position(|&entry| entry == delta) {
return index as u64;
}
self.decoding.push(delta);
if self.decoding.len() > SMALL_DECODING {
self.decoding_index
.extend((0..).zip(self.decoding.iter()).map(|(i, &d)| (d, i)));
}
return next;
}
*self.decoding_index.entry(delta).or_insert_with(|| {
self.decoding.push(delta);
next
})
}
}
struct OdgiWriter<'a, I> {
graph: &'a CoreGraphDTO,
numbering: Numbering,
edges: EdgeIndex,
steps: StepIndex<I>,
}
impl<I: StepNumber> OdgiWriter<'_, I> {
fn header(&self) -> Vec<u8> {
let ranks = || {
(0..self.numbering.records)
.filter_map(|r| self.numbering.node_at(r).map(|_| r as u64 + 1))
};
let mut buf = Vec::with_capacity(60);
buf.extend_from_slice(&ODGI_MAGIC.to_be_bytes());
push_u64(&mut buf, ranks().next_back().unwrap_or(0));
push_u64(&mut buf, ranks().next().unwrap_or(0));
push_u64(&mut buf, self.numbering.records as u64);
push_u64(&mut buf, self.edges.edge_count as u64);
push_u64(&mut buf, self.graph.paths().len() as u64);
push_u64(&mut buf, self.graph.paths().len() as u64);
push_u64(&mut buf, 0); buf
}
fn push_record(&self, rank: usize, buf: &mut Vec<u8>, scratch: &mut Scratch) {
let Some(node) = self.numbering.node_at(rank) else {
push_u64(buf, 0);
push_u64(buf, 0);
for _ in 0..3 {
push_packed(buf, &[]);
}
return;
};
let own_id = rank as u64 + 1;
let sequence = &self.graph.nodes().as_slice()[node].sequence;
push_u64(buf, sequence.len() as u64);
buf.extend_from_slice(sequence);
push_u64(buf, own_id);
scratch.values.clear();
let edges = &self.edges;
for &record in &edges.records[edges.offsets[node]..edges.offsets[node + 1]] {
#[allow(clippy::cast_possible_truncation)]
let other = (record >> EDGE_TYPE_BITS) as usize;
scratch.values.push(self.numbering.id(other));
scratch.values.push(record & ((1 << EDGE_TYPE_BITS) - 1));
}
push_packed(buf, &scratch.values);
scratch.values.clear();
scratch.clear_decoding();
let steps = &self.steps;
if steps.offsets[node] < steps.offsets[node + 1] {
scratch.encode(own_id, own_id);
}
scratch.prev_hints.clear();
scratch.next_hints.clear();
let mut path_end = 0;
for &slot in &steps.slots[steps.offsets[node]..steps.offsets[node + 1]] {
let global = slot.index();
let (path_index, position) = steps.locate_after(&mut path_end, global);
let path = &self.graph.paths()[path_index].steps;
let is_start = position == 0;
let is_end = position + 1 == path.len();
let (prev_id, prev_rank) = if is_start {
(own_id, 0)
} else {
let prev = path[position - 1].node_id();
(
self.numbering.id(prev),
steps.rank_after(&mut scratch.prev_hints, prev, global - 1),
)
};
let (next_id, next_rank) = if is_end {
(own_id, 0)
} else {
let next = path[position + 1].node_id();
(
self.numbering.id(next),
steps.rank_after(&mut scratch.next_hints, next, global + 1),
)
};
let step_type = u64::from(path[position].is_reverse())
| (u64::from(is_start) * STEP_START)
| (u64::from(is_end) * STEP_END);
let prev = scratch.encode(own_id, prev_id);
let next = scratch.encode(own_id, next_id);
scratch.values.extend_from_slice(&[
path_index as u64 + 1,
step_type,
prev,
prev_rank,
next,
next_rank,
]);
}
push_packed(buf, &scratch.decoding);
push_packed(buf, &scratch.values);
}
fn ranks_per_chunk(&self) -> usize {
let records = self.numbering.records.max(1);
let sequence_bytes: usize = self
.graph
.nodes()
.par_iter()
.map(|node| node.sequence.len())
.sum();
let average =
(sequence_bytes + 16 * self.edges.records.len() + 48 * self.steps.slots.len())
/ records
+ 100;
(CHUNK_BYTES / average).clamp(1, 1 << 14)
}
fn encode_window(&self, window: std::ops::Range<usize>, per_chunk: usize) -> Vec<Vec<u8>> {
window
.clone()
.into_par_iter()
.step_by(per_chunk)
.map(|start| {
let mut buf = Vec::new();
let mut scratch = Scratch::default();
for rank in start..(start + per_chunk).min(window.end) {
self.push_record(rank, &mut buf, &mut scratch);
}
buf
})
.collect()
}
fn write_records(&self, writer: &mut dyn Write) -> PanResult<()> {
let per_chunk = self.ranks_per_chunk();
let records = self.numbering.records;
let threads = rayon::current_num_threads();
let window = per_chunk * (threads * 4).min(MAX_WINDOW_CHUNKS).max(threads);
let mut current = self.encode_window(0..window.min(records), per_chunk);
for start in (window..records).step_by(window) {
let mut next = Vec::new();
rayon::in_place_scope(|scope| {
scope.spawn(|_| {
next = self.encode_window(start..(start + window).min(records), per_chunk);
});
current.iter().try_for_each(|buf| writer.write_all(buf))
})?;
current = next;
}
for buf in current {
writer.write_all(&buf)?;
}
Ok(())
}
fn write_paths(&self, writer: &mut dyn Write) -> PanResult<()> {
let mut buf = Vec::new();
for (index, path) in self.graph.paths().iter().enumerate() {
let step_handle = |position: usize| {
let step = path.steps[position];
let rank = self.numbering.id(step.node_id()) - 1;
let global = self.steps.path_starts[index] + position;
(
rank << 1 | u64::from(step.is_reverse()),
self.steps.rank(step.node_id(), global),
)
};
let (first, last) = match path.steps.len() {
0 => ((0, 0), (0, 0)),
len => (step_handle(0), step_handle(len - 1)),
};
push_u64(&mut buf, path.steps.len() as u64);
for value in [first.0, first.1, last.0, last.1, path.name.len() as u64] {
push_u64(&mut buf, value);
}
buf.extend_from_slice(&path.name);
if buf.len() >= CHUNK_BYTES {
writer.write_all(&buf)?;
buf.clear();
}
}
writer.write_all(&buf)?;
Ok(())
}
}
pub(super) fn write_odgi<I: StepNumber>(
graph: &CoreGraphDTO,
writer: &mut dyn Write,
) -> PanResult<()> {
let node_count = graph.nodes().len();
let ((numbering, edges), steps) = rayon::join(
|| {
rayon::join(
|| Numbering::new(graph),
|| EdgeIndex::new(node_count, graph.edges()),
)
},
|| StepIndex::new(node_count, graph.paths()),
);
let odgi = OdgiWriter::<I> {
graph,
numbering,
edges,
steps: steps?,
};
writer.write_all(&odgi.header())?;
odgi.write_records(writer)?;
odgi.write_paths(writer)
}
pub(super) fn write(graph: &CoreGraphDTO, writer: &mut dyn Write) -> PanResult<()> {
if graph.edges().par_iter().any(|edge| edge.overlap != 0)
|| graph
.paths()
.par_iter()
.any(|path| path.overlaps.iter().any(|&overlap| overlap != 0))
{
warn!("ODGI files don't support overlaps; overlaps are dropped.");
}
let total_steps: usize = graph.paths().iter().map(|path| path.steps.len()).sum();
if u32::try_from(total_steps).is_ok() {
write_odgi::<u32>(graph, writer)
} else {
write_odgi::<u64>(graph, writer)
}
}