use crate::core::core_types::{Path, Step};
use crate::error::{PanGraphXError, PanResult};
use crate::proto_gen::vg_read;
use log::debug;
pub(super) type PackedStep = i64;
pub(super) fn pack_step(node_id: i64, is_reverse: bool) -> Option<PackedStep> {
node_id
.checked_mul(2)
.map(|id| id | PackedStep::from(is_reverse))
}
pub(super) fn node_id_out_of_range(node_id: i64) -> String {
format!("VG node id {node_id} is outside the supported range ±2^62")
}
pub(super) const fn unpack_step(step: PackedStep) -> (i64, bool) {
(step >> 1, step & 1 == 1)
}
pub(super) enum ChunkRanks {
Consecutive(i64),
Explicit(Vec<i64>),
}
pub(super) struct PathChunk {
pub(super) name: Vec<u8>,
pub(super) len: usize,
pub(super) ranks: ChunkRanks,
}
impl PathChunk {
pub(super) fn decode(path: vg_read::Path, steps: &mut Vec<PackedStep>) -> PanResult<Self> {
let name_error =
|message: &str| PanGraphXError::Parse(format!("Path {}: {message}", path.name));
let first = path.mapping.first().map_or(0, |m| m.rank);
let mut next_rank = Some(first);
let mut consecutive = true;
steps.reserve(path.mapping.len());
for mapping in &path.mapping {
let position = mapping
.position
.as_ref()
.ok_or_else(|| name_error("mapping is missing its position"))?;
let step = pack_step(position.node_id, position.is_reverse)
.ok_or_else(|| name_error(&node_id_out_of_range(position.node_id)))?;
steps.push(step);
consecutive &= next_rank == Some(mapping.rank);
next_rank = next_rank.and_then(|rank| rank.checked_add(1));
}
let ranks = if consecutive {
ChunkRanks::Consecutive(first)
} else {
ChunkRanks::Explicit(path.mapping.iter().map(|m| m.rank).collect())
};
Ok(Self {
name: path.name.into_bytes(),
len: path.mapping.len(),
ranks,
})
}
}
pub(super) enum PathRanks {
Implicit,
StreamOrder,
Explicit(Vec<i64>),
}
pub(super) struct VgPath {
name: Vec<u8>,
steps: Vec<PackedStep>,
ranks: PathRanks,
}
impl VgPath {
pub(super) const fn new(name: Vec<u8>) -> Self {
Self {
name,
steps: Vec::new(),
ranks: PathRanks::Implicit,
}
}
pub(super) fn append(&mut self, ranks: ChunkRanks, steps: &[PackedStep]) {
let start = self.steps.len();
match ranks {
ChunkRanks::Consecutive(first) => {
let continues = matches!(self.ranks, PathRanks::Implicit)
&& usize::try_from(first).is_ok_and(|first| first == start + 1);
if !continues && !matches!(self.ranks, PathRanks::StreamOrder) {
let ranks = std::iter::successors(Some(first), |rank| rank.checked_add(1));
for (offset, rank) in ranks.take(steps.len()).enumerate() {
self.push_rank(start + offset, rank);
}
}
}
ChunkRanks::Explicit(ranks) => {
for (offset, rank) in ranks.into_iter().enumerate() {
self.push_rank(start + offset, rank);
}
}
}
self.steps.extend_from_slice(steps);
}
fn push_rank(&mut self, position: usize, rank: i64) {
let next = match &mut self.ranks {
PathRanks::StreamOrder => return,
_ if rank <= 0 => PathRanks::StreamOrder,
PathRanks::Explicit(ranks) => {
ranks.push(rank);
return;
}
PathRanks::Implicit => match usize::try_from(rank) {
Ok(rank) if rank == position + 1 => return,
Ok(rank) if rank <= position => {
debug!(
"VG path {} has repeated mapping ranks, keeping stream order",
String::from_utf8_lossy(&self.name)
);
PathRanks::StreamOrder
}
_ => {
let mut ranks: Vec<i64> = (1..).take(position).collect();
ranks.push(rank);
PathRanks::Explicit(ranks)
}
},
};
self.ranks = next;
}
pub(super) fn into_path(
self,
convert: impl Fn(PackedStep) -> PanResult<Step>,
) -> PanResult<Path> {
let Self {
name,
mut steps,
ranks,
} = self;
if let PathRanks::Explicit(ranks) = ranks
&& !ranks.is_sorted()
{
let mut ranked: Vec<(i64, PackedStep)> =
ranks.into_iter().zip(steps.iter().copied()).collect();
ranked.sort_unstable_by_key(|&(rank, _)| rank);
if ranked.windows(2).any(|w| w[0].0 == w[1].0) {
debug!(
"VG path {} has repeated mapping ranks, keeping stream order",
String::from_utf8_lossy(&name)
);
} else {
steps = ranked.into_iter().map(|(_, step)| step).collect();
}
}
let steps = steps
.iter()
.map(|&step| convert(step))
.collect::<PanResult<Vec<Step>>>()?;
Ok(Path {
name,
steps,
overlaps: Vec::new(),
})
}
}
#[cfg(test)]
mod tests {
use super::*;
fn ranked_path(chunks: &[&[i64]]) -> VgPath {
let mut path = VgPath::new(b"p".to_vec());
let mut node_id = 0;
for ranks in chunks {
let mapping = ranks
.iter()
.map(|&rank| {
node_id += 1;
vg_read::Mapping {
position: Some(vg_read::Position {
node_id,
is_reverse: false,
}),
rank,
}
})
.collect();
let chunk = vg_read::Path {
name: "p".to_string(),
mapping,
};
let mut steps = Vec::new();
let chunk = PathChunk::decode(chunk, &mut steps).unwrap();
path.append(chunk.ranks, &steps);
}
path
}
fn node_order(path: VgPath) -> Vec<usize> {
let path = path
.into_path(|step| {
let (vg_id, is_reverse) = unpack_step(step);
Step::new(usize::try_from(vg_id).unwrap(), is_reverse.into())
})
.unwrap();
path.steps.iter().map(|step| step.node_id()).collect()
}
#[test]
fn test_sort_by_rank() {
assert_eq!(node_order(ranked_path(&[&[3, 1, 2]])), vec![2, 3, 1]);
assert_eq!(
node_order(ranked_path(&[&[3, 4], &[1, 2]])),
vec![3, 4, 1, 2]
);
assert_eq!(node_order(ranked_path(&[&[2, 0, 1]])), vec![1, 2, 3]);
assert_eq!(node_order(ranked_path(&[&[2, 4], &[6]])), vec![1, 2, 3]);
assert_eq!(node_order(ranked_path(&[&[3, 3, 1]])), vec![1, 2, 3]);
}
#[test]
fn test_positional_ranks_are_not_stored() {
let path = ranked_path(&[&[1, 2], &[3, 4], &[], &[5]]);
assert!(matches!(path.ranks, PathRanks::Implicit));
assert_eq!(node_order(path), vec![1, 2, 3, 4, 5]);
}
#[test]
fn test_restarting_ranks_keep_stream_order() {
let path = ranked_path(&[&[1, 2], &[1, 2]]);
assert!(matches!(path.ranks, PathRanks::StreamOrder));
assert_eq!(node_order(path), vec![1, 2, 3, 4]);
}
#[test]
fn test_packed_steps() {
for (node_id, is_reverse) in [(1, false), (7, true), (-3, true), (-(1 << 62), false)] {
let step = pack_step(node_id, is_reverse).unwrap();
assert_eq!(unpack_step(step), (node_id, is_reverse));
}
assert_eq!(pack_step(1 << 62, false), None);
}
}