use crate::scan::{Hit, located};
pub(in crate::fix) const SETTLE: usize = 3;
#[derive(Debug, Clone, Copy)]
pub(in crate::fix) struct Extent {
pub(in crate::fix) byte: usize,
pub(in crate::fix) len: usize,
pub(in crate::fix) to: usize,
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub(in crate::fix) struct Trail {
layers: Vec<Layer>,
}
impl Trail {
pub(in crate::fix) const fn new() -> Self {
Self { layers: Vec::new() }
}
pub(in crate::fix) fn push(&mut self, layer: Layer) {
self.layers.push(layer);
}
pub(in crate::fix) fn origins(
&self,
original: &str,
hits: &[Hit],
) -> Vec<Hit> {
let mut out = hits.to_vec();
self.place(original, &mut out, itself);
out
}
pub(in crate::fix) fn place<T>(
&self,
original: &str,
items: &mut [T],
hit: HitOf<T>,
) {
if self.layers.is_empty() {
return;
}
let mut order: Vec<(usize, usize)> = items
.iter_mut()
.enumerate()
.map(|(at, item)| (self.back(hit(item).position.byte), at))
.collect();
order.sort_unstable();
relocate(original, &order, items, hit);
}
fn back(&self, byte: usize) -> usize {
self.layers
.iter()
.rev()
.fold(byte, |at, layer| layer.back(at))
}
}
fn relocate<T>(
original: &str,
order: &[(usize, usize)],
out: &mut [T],
hit: HitOf<T>,
) {
let mut walk = located(original).peekable();
for &(byte, at) in order {
while walk.next_if(|seen| seen.position.byte < byte).is_some() {}
let here = walk.peek().filter(|seen| seen.position.byte == byte);
if let (Some(slot), Some(seen)) = (out.get_mut(at), here) {
hit(slot).position = seen.position;
}
}
}
pub(in crate::fix) type HitOf<T> = fn(&mut T) -> &mut Hit;
pub(in crate::fix) const fn itself(hit: &mut Hit) -> &mut Hit {
hit
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub(in crate::fix) struct Layer {
marks: Vec<Mark>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Mark {
input: usize,
input_end: usize,
output: usize,
output_end: usize,
}
impl Layer {
pub(in crate::fix) fn of(spans: impl Iterator<Item = Extent>) -> Self {
let mut read = Reading::default();
Self {
marks: spans.map(|span| read.mark(span)).collect(),
}
}
pub(in crate::fix) fn back(&self, byte: usize) -> usize {
let after = self.marks.partition_point(|mark| mark.output <= byte);
let last = after.checked_sub(1).and_then(|at| self.marks.get(at));
let Some(mark) = last else {
return byte;
};
if byte < mark.output_end {
return mark.input;
}
mark.input_end
.saturating_add(byte.saturating_sub(mark.output_end))
}
}
#[derive(Debug, Default)]
struct Reading {
input: usize,
output: usize,
}
impl Reading {
fn mark(&mut self, span: Extent) -> Mark {
let gap = span.byte.saturating_sub(self.input);
let start = self.output.saturating_add(gap);
self.input = span.byte.saturating_add(span.len);
self.output = start.saturating_add(span.to);
Mark {
input: span.byte,
input_end: self.input,
output: start,
output_end: self.output,
}
}
}