use super::*;
pub(super) struct ThreadState {
pub(super) plain: PlainSearcher,
pub(super) ambiguous: AmbiguousSearcher,
pub(super) overhang: Option<(f32, AmbiguousSearcher)>,
pub(super) normalized: Vec<u8>,
pub(super) reversed: Vec<u8>,
pub(super) windows: Vec<(usize, usize, usize)>,
pub(super) mask: MaskScratch,
pub(super) head_flags: Vec<bool>,
pub(super) tail_flags: Vec<bool>,
}
impl ThreadState {
pub(super) fn new() -> Self {
Self {
plain: new_searcher(),
ambiguous: new_ambiguous_searcher(),
overhang: None,
normalized: Vec::new(),
reversed: Vec::new(),
windows: Vec::new(),
mask: MaskScratch::default(),
head_flags: Vec::new(),
tail_flags: Vec::new(),
}
}
}
pub(super) fn search(
engine: &mut Engine<'_>,
index: &CandidateIndex,
adapter_idx: usize,
pattern: &[u8],
text: Strands<'_>,
k: usize,
accept: impl FnMut(Hit),
) {
if engine.plain_read && index.plain[adapter_idx] {
for_each_hit(engine.plain, pattern, &text, k, accept);
} else {
for_each_hit(engine.ambiguous, pattern, &text, k, accept);
}
}
pub(super) const AMBIGUOUS_READ_BASE: u8 = b'X';
pub(crate) fn normalize_into<'a>(window: &'a [u8], buf: &'a mut Vec<u8>) -> (&'a [u8], bool) {
if is_upper_acgt(window) {
return (window, true);
}
buf.clear();
let mut plain = true;
buf.extend(window.iter().map(|&b| {
let normalized = normalize_base(b);
plain &= normalized != AMBIGUOUS_READ_BASE;
normalized
}));
(buf, plain)
}
#[inline]
pub(super) fn normalize_base(b: u8) -> u8 {
match b {
b'A' | b'C' | b'G' | b'T' => b,
b'a' | b'c' | b'g' | b't' => b.to_ascii_uppercase(),
_ => AMBIGUOUS_READ_BASE,
}
}
pub(super) fn is_upper_acgt(seq: &[u8]) -> bool {
let upper_acgt = |b: u8| (b == b'A') | (b == b'C') | (b == b'G') | (b == b'T');
let (chunks, remainder) = seq.as_chunks::<32>();
let body = chunks
.iter()
.all(|chunk| chunk.iter().fold(true, |ok, &b| ok & upper_acgt(b)));
body && remainder.iter().all(|&b| upper_acgt(b))
}
#[derive(Debug, Clone, Copy)]
pub(super) struct Read<'a> {
pub(super) window: &'a [u8],
pub(super) reversed: &'a [u8],
}
impl<'a> Read<'a> {
pub(super) fn strands(&self, start: usize, end: usize) -> Strands<'a> {
let n = self.window.len();
Strands {
forward: &self.window[start..end],
reversed: &self.reversed[n - end..n - start],
}
}
}
#[derive(Clone, Copy)]
pub(super) struct Context<'a> {
pub(super) cfg: &'a AdapterConfig,
pub(super) index: &'a CandidateIndex,
pub(super) read: Read<'a>,
}
pub(super) struct Engine<'a> {
pub(super) plain_read: bool,
pub(super) plain: &'a mut PlainSearcher,
pub(super) ambiguous: &'a mut AmbiguousSearcher,
pub(super) overhang: &'a mut AmbiguousSearcher,
pub(super) windows: &'a mut Vec<(usize, usize, usize)>,
pub(super) mask: &'a mut MaskScratch,
pub(super) head_flags: &'a mut Vec<bool>,
pub(super) tail_flags: &'a mut Vec<bool>,
}
pub(super) type Span = (usize, usize);
pub(super) fn search_batched(
ctx: Context<'_>,
span: Span,
searcher: &mut AmbiguousSearcher,
keep: &mut Keep<'_>,
) {
let (ws, we) = span;
let n = we - ws;
for batch in &ctx.index.terminal_batches {
let (head_end, tail_start) = terminal_windows(n, keep.end_size, batch.len, batch.k_end);
if !(keep.gate_panels && keep.five_bounded) {
let head = ctx.read.strands(ws, ws + head_end);
accept_batch_hits(batch, searcher, head, 0, Site::Head, keep);
}
if !(keep.gate_panels && keep.three_bounded) {
let tail = ctx.read.strands(ws + tail_start, we);
accept_batch_hits(
batch,
searcher,
tail,
tail_start,
Site::Tail { head_end },
keep,
);
}
}
}
pub(super) fn accept_batch_hits(
batch: &TerminalBatch,
searcher: &mut AmbiguousSearcher,
text: Strands<'_>,
offset: usize,
site: Site,
keep: &mut Keep<'_>,
) {
let accept = |pattern_idx: usize, hit: Hit| {
let adapter_idx = batch.adapter_indices[pattern_idx];
if hit.cost > keep.budgets[adapter_idx].k_end {
return;
}
keep.accept(site, adapter_idx, shifted(hit, offset));
};
encoded_pattern_hits(
searcher,
&batch.encoded,
text.forward,
text.reversed,
batch.k_end,
accept,
);
}
pub(super) fn search_singletons(
ctx: Context<'_>,
span: Span,
engine: &mut Engine<'_>,
keep: &mut Keep<'_>,
) {
let (ws, we) = span;
let n = we - ws;
for (adapter_idx, adapter) in ctx.cfg.adapters.iter().enumerate() {
if !ctx.index.singletons[adapter_idx] {
continue;
}
let Budget { len, k_end, .. } = ctx.index.budgets[adapter_idx];
let (head_end, tail_start) = terminal_windows(n, keep.end_size, len, k_end);
let reach = len + k_end;
let empty = ctx.read.strands(ws, ws);
let mut windows = [empty; 4];
let mut owned = [(0, Site::Head, 0, 0); 4];
let mut count = 0;
for (start, end, site) in [
(0, head_end, Site::Head),
(tail_start, n, Site::Tail { head_end }),
] {
let parts = if end - start >= 4 * reach {
let split = start + (end - start) / 2;
[
(start, split + reach + 1, start, split + 1),
(split - reach, end, split + 1, end + 1),
]
} else {
[(start, end, start, end + 1), (0, 0, 0, 0)]
};
for (text_start, text_end, first_end, last_end) in parts {
if text_end > text_start {
windows[count] = ctx.read.strands(ws + text_start, ws + text_end);
owned[count] = (text_start, site, first_end, last_end);
count += 1;
}
}
}
let mut found: Vec<(Site, Hit)> = Vec::new();
let accept = |text_idx: usize, h: Hit| {
let (offset, site, first_end, last_end) = owned[text_idx];
let h = shifted(h, offset);
if (first_end..last_end).contains(&h.end) {
found.push((site, h));
}
};
let windows = &windows[..count];
if engine.plain_read && ctx.index.plain[adapter_idx] {
for_each_hit_in_texts(engine.plain, &adapter.seq, windows, k_end, accept);
} else {
for_each_hit_in_texts(engine.ambiguous, &adapter.seq, windows, k_end, accept);
}
for &(site, h) in &found {
let dominated = found
.iter()
.any(|(_, g)| g.cost < h.cost && g.start < h.end && h.start < g.end);
if !dominated {
keep.accept(site, adapter_idx, h);
}
}
}
}
pub(super) fn search_partial(
ctx: Context<'_>,
span: Span,
engine: &mut Engine<'_>,
keep: &mut Keep<'_>,
) {
let (ws, we) = span;
let n = we - ws;
let head_open = keep.lo == 0;
let tail_open = keep.hi == n;
for (adapter_idx, adapter) in ctx.cfg.adapters.iter().enumerate() {
let Budget { len, k_end, .. } = ctx.index.budgets[adapter_idx];
let (head_end, tail_start) = terminal_windows(n, keep.end_size, len, k_end);
if head_open && engine.head_flags[adapter_idx] {
let head = ctx.read.strands(ws, ws + head_end);
for_each_hit(engine.overhang, &adapter.seq, &head, k_end, |h| {
if h.left_overhang > 0 {
keep.accept(Site::Head, adapter_idx, h);
}
});
}
if tail_open && engine.tail_flags[adapter_idx] {
let tail = ctx.read.strands(ws + tail_start, we);
for_each_hit(engine.overhang, &adapter.seq, &tail, k_end, |h| {
if h.right_overhang > 0 {
keep.accept(Site::Tail { head_end }, adapter_idx, shifted(h, tail_start));
}
});
}
}
}
pub(super) const RESIDUE_MASKS: &[usize] = &[12, 24, 36];
#[derive(Debug, Default)]
pub(super) struct MaskScratch {
pub(super) text: Vec<u8>,
pub(super) reversed: Vec<u8>,
}
impl MaskScratch {
pub(super) fn fill(&mut self, window: &[u8], mask: usize, head: bool) -> Strands<'_> {
self.text.clear();
self.text.extend_from_slice(window);
let n = self.text.len();
let masked = if head { 0..mask } else { n - mask..n };
self.text[masked].fill(b'N');
self.reversed.clear();
self.reversed.extend(self.text.iter().rev());
Strands {
forward: &self.text,
reversed: &self.reversed,
}
}
}
pub(super) fn search_residue(
ctx: Context<'_>,
span: Span,
engine: &mut Engine<'_>,
keep: &mut Keep<'_>,
) {
let (ws, we) = span;
let n = we - ws;
let window = ctx.read.window;
let retry_head = keep.lo == 0;
let retry_tail = keep.hi == n;
for (adapter_idx, adapter) in ctx.cfg.adapters.iter().enumerate() {
let retry_head = retry_head && engine.head_flags[adapter_idx];
let retry_tail = retry_tail && engine.tail_flags[adapter_idx];
if adapter.role != Role::Adapter || (!retry_head && !retry_tail) {
continue;
}
let Budget { len, k_end, .. } = ctx.index.budgets[adapter_idx];
let reach = (keep.end_size + len + k_end).min(n);
for &masked in RESIDUE_MASKS {
if masked + MIN_OVERLAP > reach {
break;
}
if retry_head {
let text = engine.mask.fill(&window[ws..ws + reach], masked, true);
for_each_hit(engine.overhang, &adapter.seq, &text, k_end, |h| {
let overlap = h.end.saturating_sub(masked.max(h.start));
if h.start <= masked
&& h.end <= keep.hi
&& h.right_overhang == 0
&& overlap >= MIN_OVERLAP
&& keep.residue_within_budget(h, overlap)
{
trace_hit(
&adapter.name,
h.start,
h.end,
h.cost,
Some(HitAction::TrimFivePrime),
);
keep.trim_five_fixed(h.end);
}
});
}
if retry_tail {
let start = n - reach;
let text = engine.mask.fill(&window[ws + start..we], masked, false);
let unmasked = reach - masked;
for_each_hit(engine.overhang, &adapter.seq, &text, k_end, |h| {
let overlap = unmasked.min(h.end).saturating_sub(h.start);
if h.end >= unmasked
&& start + h.start >= keep.lo
&& h.left_overhang == 0
&& overlap >= MIN_OVERLAP
&& keep.residue_within_budget(h, overlap)
{
let (s, e) = (start + h.start, start + h.end.min(reach));
trace_hit(&adapter.name, s, e, h.cost, Some(HitAction::TrimThreePrime));
keep.trim_three_fixed(s);
}
});
}
}
}
}
pub(super) fn shifted(hit: Hit, offset: usize) -> Hit {
Hit {
start: hit.start + offset,
end: hit.end + offset,
..hit
}
}
pub(super) fn search_interior(ctx: Context<'_>, engine: &mut Engine<'_>, keep: &mut Keep<'_>) {
let n = ctx.read.window.len();
ctx.index.candidate_windows(ctx.read.window, engine.windows);
for i in 0..engine.windows.len() {
let (adapter_idx, start, end) = engine.windows[i];
if !keep.splits(adapter_idx) {
continue;
}
let Budget { len, k_end, .. } = ctx.index.budgets[adapter_idx];
let reach = len + k_end;
let start = start.max((keep.end_size + 1).saturating_sub(reach));
let end = end.min(n.saturating_sub(keep.end_size + 1) + reach);
if end <= start || end - start < len.saturating_sub(k_end) {
continue;
}
let k_mid = ctx.index.budgets[adapter_idx].interior(n);
let pattern = &ctx.cfg.adapters[adapter_idx].seq;
let text = ctx.read.strands(start, end);
let Some(whole) = &ctx.index.whole_primers[adapter_idx] else {
search(engine, ctx.index, adapter_idx, pattern, text, k_mid, |h| {
keep.accept(Site::Interior, adapter_idx, shifted(h, start))
});
continue;
};
let mut found: Vec<Hit> = Vec::new();
search(engine, ctx.index, adapter_idx, pattern, text, k_mid, |h| {
found.push(shifted(h, start))
});
for hit in found {
match whole_primer_over(ctx, engine, whole, hit) {
Some(spanned) => keep.accept_standalone(adapter_idx, spanned),
None => keep.accept(Site::Interior, adapter_idx, hit),
}
}
}
}
fn whole_primer_over(
ctx: Context<'_>,
engine: &mut Engine<'_>,
whole: &WholePrimer,
hit: Hit,
) -> Option<Hit> {
let n = ctx.read.window.len();
let k = whole.k_mid[interior_class(n)];
let reach = whole.seq.len() + k;
let start = hit.start.saturating_sub(reach);
let end = (hit.end + reach).min(n);
let mut best: Option<Hit> = None;
for_each_hit(
engine.ambiguous,
&whole.seq,
&ctx.read.strands(start, end),
k,
|g| {
let g = shifted(g, start);
if g.rc == hit.rc
&& g.start < hit.end
&& hit.start < g.end
&& g.clip_start + g.clip_end < MIN_OVERLAP
&& best.is_none_or(|b| g.cost < b.cost)
{
best = Some(g);
}
},
);
let g = best?;
let (lo, hi) = (hit.start.min(g.start), hit.end.max(g.end));
let inner_start = (hit.start + hit.clip_start).min(g.start + g.clip_start);
let inner_end = (hit.end - hit.clip_end).max(g.end - g.clip_end);
Some(Hit {
start: lo,
end: hi,
clip_start: inner_start - lo,
clip_end: hi - inner_end,
..hit
})
}
pub(super) fn search_pairs(ctx: Context<'_>, engine: &mut Engine<'_>, keep: &mut Keep<'_>) {
let n = ctx.read.window.len();
let mut found: Vec<(usize, Hit)> = Vec::new();
for (adapter_idx, &paired) in ctx.index.paired.iter().enumerate() {
if !paired {
continue;
}
let Budget { len, k_end, .. } = ctx.index.budgets[adapter_idx];
let reach = len + k_end;
let start = (keep.end_size + 1).saturating_sub(reach);
let end = (n.saturating_sub(keep.end_size + 1) + reach).min(n);
if end <= start || end - start < len {
continue;
}
let first = found.len();
search(
engine,
ctx.index,
adapter_idx,
&ctx.cfg.adapters[adapter_idx].seq,
ctx.read.strands(start, end),
ctx.index.budgets[adapter_idx].pair(n),
|h| found.push((adapter_idx, shifted(h, start))),
);
let hits: Vec<Hit> = found[first..].iter().map(|&(_, h)| h).collect();
found.truncate(first);
found.extend(
hits.iter()
.filter(|h| {
!hits.iter().any(|g| {
g.rc == h.rc && g.cost < h.cost && g.start < h.end && h.start < g.end
})
})
.map(|&h| (adapter_idx, h)),
);
}
if found.len() < 2 {
return;
}
let opens = |&(adapter_idx, hit): &(usize, Hit)| ctx.index.opens[adapter_idx] != hit.rc;
for closing in found.iter().filter(|hit| !opens(hit)) {
for opening in found.iter().filter(|hit| opens(hit)) {
let (c, o) = (closing.1, opening.1);
if o.start > c.start
&& o.end > c.end
&& o.start <= c.end + FLANK_SLACK
&& o.start + FLANK_SLACK >= c.end
{
keep.accept_pair(*closing, *opening);
}
}
}
}
pub(super) fn search_terminal(
ctx: Context<'_>,
span: Span,
engine: &mut Engine<'_>,
keep: &mut Keep<'_>,
) {
search_singletons(ctx, span, engine, keep);
keep.settle();
if !ctx.index.terminal_batches.is_empty() {
search_batched(ctx, span, engine.ambiguous, keep);
keep.settle();
}
let (ws, we) = span;
if keep.lo != 0 && keep.hi != we - ws {
return;
}
ctx.index.end_candidates(
ctx.read.window,
ws,
we,
keep.end_size,
engine.head_flags,
engine.tail_flags,
);
search_partial(ctx, span, engine, keep);
search_residue(ctx, span, engine, keep);
keep.settle();
}
pub(super) fn segments_tallied(
window: &[u8],
cfg: &AdapterConfig,
acted: Option<&mut [bool]>,
) -> Vec<(usize, usize)> {
let n = window.len();
if n == 0 {
return vec![];
}
if cfg.adapters.is_empty() {
return vec![(0, n)];
}
let index = cfg
.candidate_index
.get_or_init(|| CandidateIndex::for_config(cfg));
let alpha = cfg.error_rate as f32;
STATE.with_borrow_mut(|state| {
let ThreadState {
plain,
ambiguous,
overhang,
normalized,
reversed,
windows,
mask,
head_flags,
tail_flags,
} = state;
let (window, plain_read) = normalize_into(window, normalized);
reversed.clear();
reversed.extend_from_slice(window);
reversed.reverse();
let overhang = match overhang {
Some((a, s)) if *a == alpha => s,
slot => &mut slot.insert((alpha, new_overhang_searcher(alpha))).1,
};
let ctx = Context {
cfg,
index,
read: Read { window, reversed },
};
let mut engine = Engine {
plain_read,
plain,
ambiguous,
overhang,
windows,
mask,
head_flags,
tail_flags,
};
segments_with(ctx, &mut engine, acted)
})
}
pub(super) fn segments_with(
ctx: Context<'_>,
engine: &mut Engine<'_>,
mut acted: Option<&mut [bool]>,
) -> Vec<(usize, usize)> {
let cfg = ctx.cfg;
let n = ctx.read.window.len();
let gate_panels = acted.is_none();
let mut tally = |keep: &Keep<'_>| {
if let Some(acted) = acted.as_deref_mut() {
for &adapter_idx in &keep.acted {
acted[adapter_idx] = true;
}
}
};
let mut keep = Keep::new(cfg, ctx.index, n, cfg.split);
keep.gate_panels = gate_panels;
search_terminal(ctx, (0, n), engine, &mut keep);
if cfg.split {
search_interior(ctx, engine, &mut keep);
search_pairs(ctx, engine, &mut keep);
}
keep.settle();
tally(&keep);
let (lo, hi, cuts) = keep.into_cuts(cfg.min_piece);
if lo >= hi {
return vec![];
}
if cuts.is_empty() {
return vec![(lo, hi)];
}
let mut segs = Vec::with_capacity(cuts.len() + 1);
let mut cursor = lo;
let mut push_piece = |s: usize, e: usize, segs: &mut Vec<(usize, usize)>| {
if s >= e {
return;
}
let mut keep = Keep::new(cfg, ctx.index, e - s, false);
keep.gate_panels = gate_panels;
search_terminal(ctx, (s, e), engine, &mut keep);
keep.refine();
tally(&keep);
if keep.lo < keep.hi {
segs.push((s + keep.lo, s + keep.hi));
}
};
for (s, e) in cuts {
push_piece(cursor, s, &mut segs);
cursor = cursor.max(e);
}
push_piece(cursor, hi, &mut segs);
segs
}