Skip to main content

rsomics_count/
count.rs

1use std::collections::{BTreeMap, HashMap};
2use std::io;
3use std::num::NonZeroUsize;
4use std::path::{Path, PathBuf};
5use std::sync::mpsc;
6
7use noodles::sam::header::record::value::map::header::{sort_order::QUERY_NAME, tag::SORT_ORDER};
8use rsomics_common::{Result, RsomicsError};
9use serde::Serialize;
10use smallvec::SmallVec;
11
12use crate::alignment::{NameMode, Reader, Segment};
13use crate::annotation::{self, AnnotationOptions};
14use crate::model::{Block, Blocks, FeatureSet, Hit, Hits, StrandMode};
15
16#[derive(Clone, Copy, Debug, Eq, PartialEq)]
17pub enum Contribution {
18    Exclude,
19    Full,
20    Fractional,
21}
22
23#[derive(Clone, Copy, Debug, Eq, PartialEq)]
24pub enum SplitMode {
25    Any,
26    Only,
27    Exclude,
28}
29
30#[derive(Clone, Debug)]
31pub struct PairOptions {
32    pub enabled: bool,
33    pub require_both_mapped: bool,
34    pub exclude_chimeric: bool,
35    pub check_fragment_length: bool,
36    pub min_fragment_length: u32,
37    pub max_fragment_length: u32,
38}
39
40impl Default for PairOptions {
41    fn default() -> Self {
42        Self {
43            enabled: false,
44            require_both_mapped: false,
45            exclude_chimeric: false,
46            check_fragment_length: false,
47            min_fragment_length: 50,
48            max_fragment_length: 600,
49        }
50    }
51}
52
53#[derive(Clone, Debug)]
54pub struct CountOptions {
55    pub strands: Vec<StrandMode>,
56    pub multi_overlap: Contribution,
57    pub multi_map: Contribution,
58    pub min_overlap: u64,
59    pub frac_overlap: f64,
60    pub frac_overlap_feature: f64,
61    pub min_mapq: u8,
62    pub primary_only: bool,
63    pub ignore_duplicates: bool,
64    pub split: SplitMode,
65    pub pair: PairOptions,
66    pub aliases: Option<PathBuf>,
67    pub threads: Option<NonZeroUsize>,
68}
69
70impl Default for CountOptions {
71    fn default() -> Self {
72        Self {
73            strands: vec![StrandMode::Unstranded],
74            multi_overlap: Contribution::Exclude,
75            multi_map: Contribution::Exclude,
76            min_overlap: 1,
77            frac_overlap: 0.0,
78            frac_overlap_feature: 0.0,
79            min_mapq: 0,
80            primary_only: false,
81            ignore_duplicates: false,
82            split: SplitMode::Any,
83            pair: PairOptions::default(),
84            aliases: None,
85            threads: None,
86        }
87    }
88}
89
90#[derive(Clone, Debug, Default, Eq, PartialEq, Serialize)]
91pub struct CountSummary {
92    pub assigned: u64,
93    pub unassigned_unmapped: u64,
94    pub unassigned_read_type: u64,
95    pub unassigned_singleton: u64,
96    pub unassigned_mapping_quality: u64,
97    pub unassigned_chimera: u64,
98    pub unassigned_fragment_length: u64,
99    pub unassigned_duplicate: u64,
100    pub unassigned_multi_mapping: u64,
101    pub unassigned_secondary: u64,
102    pub unassigned_non_split: u64,
103    pub unassigned_split: u64,
104    pub unassigned_no_features: u64,
105    pub unassigned_overlapping_length: u64,
106    pub unassigned_ambiguity: u64,
107}
108
109impl CountSummary {
110    #[must_use]
111    pub const fn total(&self) -> u64 {
112        self.assigned
113            + self.unassigned_unmapped
114            + self.unassigned_read_type
115            + self.unassigned_singleton
116            + self.unassigned_mapping_quality
117            + self.unassigned_chimera
118            + self.unassigned_fragment_length
119            + self.unassigned_duplicate
120            + self.unassigned_multi_mapping
121            + self.unassigned_secondary
122            + self.unassigned_non_split
123            + self.unassigned_split
124            + self.unassigned_no_features
125            + self.unassigned_overlapping_length
126            + self.unassigned_ambiguity
127    }
128
129    fn merge(&mut self, other: &Self) {
130        self.assigned += other.assigned;
131        self.unassigned_unmapped += other.unassigned_unmapped;
132        self.unassigned_read_type += other.unassigned_read_type;
133        self.unassigned_singleton += other.unassigned_singleton;
134        self.unassigned_mapping_quality += other.unassigned_mapping_quality;
135        self.unassigned_chimera += other.unassigned_chimera;
136        self.unassigned_fragment_length += other.unassigned_fragment_length;
137        self.unassigned_duplicate += other.unassigned_duplicate;
138        self.unassigned_multi_mapping += other.unassigned_multi_mapping;
139        self.unassigned_secondary += other.unassigned_secondary;
140        self.unassigned_non_split += other.unassigned_non_split;
141        self.unassigned_split += other.unassigned_split;
142        self.unassigned_no_features += other.unassigned_no_features;
143        self.unassigned_overlapping_length += other.unassigned_overlapping_length;
144        self.unassigned_ambiguity += other.unassigned_ambiguity;
145    }
146}
147
148#[derive(Clone, Debug, Serialize)]
149pub struct LibraryReport {
150    pub input: String,
151    pub total: u64,
152    pub assigned: u64,
153}
154
155#[derive(Clone, Debug, Serialize)]
156pub struct CountReport {
157    pub features: usize,
158    pub libraries: Vec<LibraryReport>,
159}
160
161pub(crate) struct LibraryCounts {
162    pub(crate) values: Vec<f64>,
163    pub(crate) summary: CountSummary,
164}
165
166impl LibraryCounts {
167    fn new(features: usize) -> Self {
168        Self {
169            values: vec![0.0; features],
170            summary: CountSummary::default(),
171        }
172    }
173
174    fn merge(&mut self, other: &Self) {
175        for (value, addition) in self.values.iter_mut().zip(&other.values) {
176            *value += addition;
177        }
178        self.summary.merge(&other.summary);
179    }
180}
181
182pub fn count(
183    inputs: &[PathBuf],
184    annotation_path: &Path,
185    counts_path: &Path,
186    summary_path: &Path,
187    annotation_options: &AnnotationOptions,
188    options: &CountOptions,
189) -> Result<CountReport> {
190    validate(inputs, counts_path, summary_path, options)?;
191    rsomics_common::reject_output_alias(
192        counts_path,
193        inputs
194            .iter()
195            .map(PathBuf::as_path)
196            .chain(std::iter::once(annotation_path))
197            .chain(options.aliases.as_deref())
198            .chain(std::iter::once(summary_path)),
199    )?;
200    rsomics_common::reject_output_alias(
201        summary_path,
202        inputs
203            .iter()
204            .map(PathBuf::as_path)
205            .chain(std::iter::once(annotation_path))
206            .chain(options.aliases.as_deref())
207            .chain(std::iter::once(counts_path)),
208    )?;
209    let features = annotation::load(annotation_path, annotation_options)?;
210    let aliases = annotation::load_aliases(options.aliases.as_deref())?;
211    let strands = expand_strands(&options.strands, inputs.len())?;
212    let mut libraries = Vec::with_capacity(inputs.len());
213    for (input, strand) in inputs.iter().zip(strands) {
214        libraries.push(count_library(input, &features, &aliases, strand, options)?);
215    }
216
217    rsomics_common::write_atomic_pair(counts_path, summary_path, |counts, summary| {
218        crate::output::write_counts(counts, &features, inputs, &libraries)?;
219        crate::output::write_summary(summary, inputs, &libraries, options.split)
220    })?;
221
222    Ok(CountReport {
223        features: features.rows().len(),
224        libraries: inputs
225            .iter()
226            .zip(&libraries)
227            .map(|(input, library)| LibraryReport {
228                input: input.display().to_string(),
229                total: library.summary.total(),
230                assigned: library.summary.assigned,
231            })
232            .collect(),
233    })
234}
235
236fn validate(
237    inputs: &[PathBuf],
238    counts_path: &Path,
239    summary_path: &Path,
240    options: &CountOptions,
241) -> Result<()> {
242    if inputs.is_empty() {
243        return Err(RsomicsError::ConfigError(
244            "at least one alignment input is required".to_owned(),
245        ));
246    }
247    if inputs
248        .iter()
249        .filter(|path| path.as_path() == Path::new("-"))
250        .count()
251        > 1
252    {
253        return Err(RsomicsError::ConfigError(
254            "standard input can name only one library".to_owned(),
255        ));
256    }
257    if counts_path == Path::new("-") || summary_path == Path::new("-") {
258        return Err(RsomicsError::ConfigError(
259            "counts and summary outputs must be named files".to_owned(),
260        ));
261    }
262    for (label, value) in [
263        ("--frac-overlap", options.frac_overlap),
264        ("--frac-overlap-feature", options.frac_overlap_feature),
265    ] {
266        if !value.is_finite() || !(0.0..=1.0).contains(&value) {
267            return Err(RsomicsError::ConfigError(format!(
268                "{label} must be finite and between 0 and 1"
269            )));
270        }
271    }
272    if options.min_overlap == 0 {
273        return Err(RsomicsError::ConfigError(
274            "--min-overlap must be at least 1".to_owned(),
275        ));
276    }
277    if options.pair.min_fragment_length > options.pair.max_fragment_length {
278        return Err(RsomicsError::ConfigError(
279            "minimum fragment length exceeds maximum fragment length".to_owned(),
280        ));
281    }
282    if options.pair.check_fragment_length && !options.pair.require_both_mapped {
283        return Err(RsomicsError::ConfigError(
284            "fragment-length checks require both mates to be mapped".to_owned(),
285        ));
286    }
287    Ok(())
288}
289
290fn expand_strands(strands: &[StrandMode], libraries: usize) -> Result<Vec<StrandMode>> {
291    match strands {
292        [strand] => Ok(vec![*strand; libraries]),
293        values if values.len() == libraries => Ok(values.to_vec()),
294        values => Err(RsomicsError::ConfigError(format!(
295            "--strand expects one value or one per library; found {} for {libraries} libraries",
296            values.len()
297        ))),
298    }
299}
300
301fn count_library(
302    input: &Path,
303    features: &FeatureSet,
304    aliases: &HashMap<String, String>,
305    strand: StrandMode,
306    options: &CountOptions,
307) -> Result<LibraryCounts> {
308    let threads = options
309        .threads
310        .unwrap_or_else(|| std::thread::available_parallelism().unwrap_or(NonZeroUsize::MIN));
311    let parallel_count = threads.get() > 1;
312    let mut reader = Reader::open(
313        input,
314        if parallel_count {
315            Some(NonZeroUsize::MIN)
316        } else {
317            options.threads
318        },
319    )?;
320    let header = reader.read_header()?;
321    let mut result = LibraryCounts::new(features.rows().len());
322    if options.pair.enabled {
323        count_pairs(
324            &mut reader,
325            &header,
326            CountContext {
327                aliases,
328                features,
329                strand,
330                options,
331            },
332            threads.get() - 1,
333            &mut result,
334        )?;
335    } else if parallel_count {
336        count_single_parallel(
337            &mut reader,
338            &header,
339            CountContext {
340                aliases,
341                features,
342                strand,
343                options,
344            },
345            threads.get() - 1,
346            &mut result,
347        )?;
348    } else {
349        reader.visit(
350            &header,
351            aliases,
352            &|name| features.chrom_id(name),
353            NameMode::None,
354            |segment| {
355                process_unit(
356                    Unit::single(segment),
357                    features,
358                    strand,
359                    options,
360                    &mut result,
361                )
362            },
363        )?;
364    }
365    Ok(result)
366}
367
368fn count_pairs(
369    reader: &mut Reader,
370    header: &noodles::sam::Header,
371    context: CountContext<'_>,
372    workers: usize,
373    result: &mut LibraryCounts,
374) -> Result<()> {
375    if is_queryname_sorted(header) && workers > 0 {
376        count_queryname_pairs_parallel(reader, header, context, workers, result)
377    } else if is_queryname_sorted(header) {
378        let mut group_active = false;
379        let mut buckets = PairBuckets::new();
380        reader.visit(
381            header,
382            context.aliases,
383            &|name| context.features.chrom_id(name),
384            NameMode::Grouped,
385            |segment| {
386                if !segment.segmented || segment.first == segment.last {
387                    result.summary.unassigned_read_type += 1;
388                    return Ok(());
389                }
390                if !segment.name_present {
391                    return Err(RsomicsError::InvalidInput(
392                        "paired alignment has no read name".to_owned(),
393                    ));
394                }
395                if segment.group_start {
396                    if group_active {
397                        process_pair_buckets(std::mem::take(&mut buckets), context, result)?;
398                    }
399                    group_active = true;
400                }
401                let hit_index = segment.hit_index.unwrap_or(1);
402                insert_pair_segment(pair_bucket(&mut buckets, hit_index), segment, None)
403            },
404        )?;
405        process_pair_buckets(buckets, context, result)
406    } else {
407        let mut pairs = BTreeMap::<(Vec<u8>, u32), PairBucket>::new();
408        reader.visit(
409            header,
410            context.aliases,
411            &|name| context.features.chrom_id(name),
412            NameMode::Owned,
413            |mut segment| {
414                if !segment.segmented || segment.first == segment.last {
415                    result.summary.unassigned_read_type += 1;
416                    return Ok(());
417                }
418                let name = segment.name.take().ok_or_else(|| {
419                    RsomicsError::InvalidInput("paired alignment has no read name".to_owned())
420                })?;
421                let hit_index = segment.hit_index.unwrap_or(1);
422                insert_pair_segment(
423                    pairs.entry((name.clone(), hit_index)).or_default(),
424                    segment,
425                    Some(&name),
426                )
427            },
428        )?;
429        for (_, pair) in pairs {
430            process_pair(
431                pair,
432                context.features,
433                context.strand,
434                context.options,
435                result,
436            )?;
437        }
438        Ok(())
439    }
440}
441
442fn count_queryname_pairs_parallel(
443    reader: &mut Reader,
444    header: &noodles::sam::Header,
445    context: CountContext<'_>,
446    workers: usize,
447    result: &mut LibraryCounts,
448) -> Result<()> {
449    const BATCH_SIZE: usize = 4 * 1024;
450
451    std::thread::scope(|scope| {
452        let mut senders = Vec::with_capacity(workers);
453        let mut handles = Vec::with_capacity(workers);
454        for _ in 0..workers {
455            let (sender, receiver) = mpsc::sync_channel::<Vec<PairBucket>>(2);
456            senders.push(sender);
457            handles.push(scope.spawn(move || {
458                let mut local = LibraryCounts::new(context.features.rows().len());
459                for batch in receiver {
460                    for pair in batch {
461                        process_pair(
462                            pair,
463                            context.features,
464                            context.strand,
465                            context.options,
466                            &mut local,
467                        )?;
468                    }
469                }
470                Ok::<_, RsomicsError>(local)
471            }));
472        }
473
474        let mut group_active = false;
475        let mut buckets = PairBuckets::new();
476        let mut batch = Vec::with_capacity(BATCH_SIZE);
477        let mut next_worker = 0;
478        let read_result = reader.visit(
479            header,
480            context.aliases,
481            &|name| context.features.chrom_id(name),
482            NameMode::Grouped,
483            |segment| {
484                if !segment.segmented || segment.first == segment.last {
485                    result.summary.unassigned_read_type += 1;
486                    return Ok(());
487                }
488                if !segment.name_present {
489                    return Err(RsomicsError::InvalidInput(
490                        "paired alignment has no read name".to_owned(),
491                    ));
492                }
493                if segment.group_start {
494                    if group_active {
495                        enqueue_pair_buckets(
496                            std::mem::take(&mut buckets),
497                            &mut batch,
498                            &senders,
499                            &mut next_worker,
500                            BATCH_SIZE,
501                        )?;
502                    }
503                    group_active = true;
504                }
505                let hit_index = segment.hit_index.unwrap_or(1);
506                insert_pair_segment(pair_bucket(&mut buckets, hit_index), segment, None)
507            },
508        );
509        if read_result.is_ok() {
510            enqueue_pair_buckets(buckets, &mut batch, &senders, &mut next_worker, BATCH_SIZE)?;
511            if !batch.is_empty() {
512                send_batch(&senders, &mut next_worker, batch)?;
513            }
514        }
515        drop(senders);
516
517        let worker_result = merge_workers(handles, result);
518        read_result?;
519        worker_result
520    })
521}
522
523fn enqueue_pair_buckets(
524    mut buckets: PairBuckets,
525    batch: &mut Vec<PairBucket>,
526    senders: &[mpsc::SyncSender<Vec<PairBucket>>],
527    next_worker: &mut usize,
528    batch_size: usize,
529) -> Result<()> {
530    buckets.sort_unstable_by_key(|(hit_index, _)| *hit_index);
531    for (_, pair) in buckets {
532        batch.push(pair);
533        if batch.len() == batch_size {
534            let ready = std::mem::replace(batch, Vec::with_capacity(batch_size));
535            send_batch(senders, next_worker, ready)?;
536        }
537    }
538    Ok(())
539}
540
541fn send_batch<T>(
542    senders: &[mpsc::SyncSender<Vec<T>>],
543    next_worker: &mut usize,
544    batch: Vec<T>,
545) -> Result<()> {
546    senders[*next_worker].send(batch).map_err(|_| {
547        RsomicsError::Io(io::Error::new(
548            io::ErrorKind::BrokenPipe,
549            "counting worker stopped",
550        ))
551    })?;
552    *next_worker = (*next_worker + 1) % senders.len();
553    Ok(())
554}
555
556fn merge_workers(
557    handles: Vec<std::thread::ScopedJoinHandle<'_, Result<LibraryCounts>>>,
558    result: &mut LibraryCounts,
559) -> Result<()> {
560    let mut worker_error = None;
561    for handle in handles {
562        match handle.join() {
563            Ok(Ok(local)) => result.merge(&local),
564            Ok(Err(error)) if worker_error.is_none() => worker_error = Some(error),
565            Err(_) if worker_error.is_none() => {
566                worker_error = Some(RsomicsError::Io(io::Error::other(
567                    "counting worker panicked",
568                )));
569            }
570            _ => {}
571        }
572    }
573    match worker_error {
574        Some(error) => Err(error),
575        None => Ok(()),
576    }
577}
578
579fn is_queryname_sorted(header: &noodles::sam::Header) -> bool {
580    header
581        .header()
582        .and_then(|value| value.other_fields().get(&SORT_ORDER))
583        .is_some_and(|order| order == QUERY_NAME)
584}
585
586fn insert_pair_segment(
587    bucket: &mut PairBucket,
588    segment: Segment,
589    name: Option<&[u8]>,
590) -> Result<()> {
591    let slot = if segment.first {
592        &mut bucket.first
593    } else {
594        &mut bucket.last
595    };
596    if slot.replace(segment).is_some() {
597        let identity = name.map_or_else(
598            || "group".to_owned(),
599            |name| format!("{:?}", String::from_utf8_lossy(name)),
600        );
601        return Err(RsomicsError::InvalidInput(format!(
602            "paired alignment {identity} repeats the same segment and HI value"
603        )));
604    }
605    Ok(())
606}
607
608fn process_pair_buckets(
609    mut buckets: PairBuckets,
610    context: CountContext<'_>,
611    result: &mut LibraryCounts,
612) -> Result<()> {
613    buckets.sort_unstable_by_key(|(hit_index, _)| *hit_index);
614    for (_, pair) in buckets {
615        process_pair(
616            pair,
617            context.features,
618            context.strand,
619            context.options,
620            result,
621        )?;
622    }
623    Ok(())
624}
625
626type PairBuckets = SmallVec<[(u32, PairBucket); 2]>;
627
628fn pair_bucket(buckets: &mut PairBuckets, hit_index: u32) -> &mut PairBucket {
629    if let Some(index) = buckets
630        .iter()
631        .position(|(candidate, _)| *candidate == hit_index)
632    {
633        return &mut buckets[index].1;
634    }
635    buckets.push((hit_index, PairBucket::default()));
636    &mut buckets.last_mut().unwrap().1
637}
638
639#[derive(Clone, Copy)]
640struct CountContext<'a> {
641    aliases: &'a HashMap<String, String>,
642    features: &'a FeatureSet,
643    strand: StrandMode,
644    options: &'a CountOptions,
645}
646
647fn count_single_parallel(
648    reader: &mut Reader,
649    header: &noodles::sam::Header,
650    context: CountContext<'_>,
651    workers: usize,
652    result: &mut LibraryCounts,
653) -> Result<()> {
654    const BATCH_SIZE: usize = 8 * 1024;
655
656    std::thread::scope(|scope| {
657        let mut senders = Vec::with_capacity(workers);
658        let mut handles = Vec::with_capacity(workers);
659        for _ in 0..workers {
660            let (sender, receiver) = mpsc::sync_channel::<Vec<Segment>>(2);
661            senders.push(sender);
662            handles.push(scope.spawn(move || {
663                let mut local = LibraryCounts::new(context.features.rows().len());
664                for batch in receiver {
665                    for segment in batch {
666                        process_unit(
667                            Unit::single(segment),
668                            context.features,
669                            context.strand,
670                            context.options,
671                            &mut local,
672                        )?;
673                    }
674                }
675                Ok::<_, RsomicsError>(local)
676            }));
677        }
678
679        let mut batch = Vec::with_capacity(BATCH_SIZE);
680        let mut next_worker = 0;
681        let read_result = reader.visit(
682            header,
683            context.aliases,
684            &|name| context.features.chrom_id(name),
685            NameMode::None,
686            |segment| {
687                batch.push(segment);
688                if batch.len() == BATCH_SIZE {
689                    let ready = std::mem::replace(&mut batch, Vec::with_capacity(BATCH_SIZE));
690                    send_batch(&senders, &mut next_worker, ready)?;
691                }
692                Ok(())
693            },
694        );
695        if read_result.is_ok()
696            && !batch.is_empty()
697            && let Err(error) = send_batch(&senders, &mut next_worker, batch)
698        {
699            drop(senders);
700            for handle in handles {
701                let _ = handle.join();
702            }
703            return Err(error);
704        }
705        drop(senders);
706
707        let worker_result = merge_workers(handles, result);
708        read_result?;
709        worker_result
710    })
711}
712
713#[derive(Default)]
714struct PairBucket {
715    first: Option<Segment>,
716    last: Option<Segment>,
717}
718
719fn process_pair(
720    pair: PairBucket,
721    features: &FeatureSet,
722    strand: StrandMode,
723    options: &CountOptions,
724    result: &mut LibraryCounts,
725) -> Result<()> {
726    if options.pair.require_both_mapped
727        && (pair.first.as_ref().is_none_or(|segment| segment.unmapped)
728            || pair.last.as_ref().is_none_or(|segment| segment.unmapped))
729    {
730        result.summary.unassigned_singleton += 1;
731        return Ok(());
732    }
733    if options.pair.exclude_chimeric
734        && let (Some(first), Some(last)) = (pair.first.as_ref(), pair.last.as_ref())
735        && !first.unmapped
736        && !last.unmapped
737        && (first.reference != last.reference || first.reverse == last.reverse)
738    {
739        result.summary.unassigned_chimera += 1;
740        return Ok(());
741    }
742    let invalid_fragment_length = if options.pair.check_fragment_length {
743        let length = pair
744            .first
745            .as_ref()
746            .or(pair.last.as_ref())
747            .map_or(0, |segment| segment.template_length.unsigned_abs());
748        length < options.pair.min_fragment_length || length > options.pair.max_fragment_length
749    } else {
750        false
751    };
752    let mut unit = Unit::pair(pair);
753    unit.invalid_fragment_length = invalid_fragment_length;
754    process_unit(unit, features, strand, options, result)
755}
756
757struct Unit {
758    block_groups: SmallVec<[BlockGroup; 2]>,
759    unmapped: bool,
760    secondary: bool,
761    duplicate: bool,
762    mapq: u8,
763    nh: u32,
764    split: bool,
765    invalid_fragment_length: bool,
766}
767
768struct BlockGroup {
769    blocks: Blocks,
770    reverse: bool,
771}
772
773impl Unit {
774    fn single(segment: Segment) -> Self {
775        let mut block_groups = SmallVec::new();
776        block_groups.push(BlockGroup {
777            blocks: segment.blocks,
778            reverse: segment.reverse,
779        });
780        Self {
781            block_groups,
782            unmapped: segment.unmapped,
783            secondary: segment.secondary,
784            duplicate: segment.duplicate,
785            mapq: segment.mapq,
786            nh: segment.nh,
787            split: segment.split,
788            invalid_fragment_length: false,
789        }
790    }
791
792    fn pair(pair: PairBucket) -> Self {
793        let segments = [pair.first, pair.last];
794        let secondary = segments.iter().flatten().any(|segment| segment.secondary);
795        let duplicate = segments.iter().flatten().any(|segment| segment.duplicate);
796        let mapq = segments
797            .iter()
798            .flatten()
799            .filter(|segment| !segment.unmapped)
800            .map(|segment| segment.mapq)
801            .min()
802            .unwrap_or(0);
803        let nh = segments
804            .iter()
805            .flatten()
806            .map(|segment| segment.nh)
807            .max()
808            .unwrap_or(1);
809        let split = segments.iter().flatten().any(|segment| segment.split);
810        let mut block_groups = SmallVec::new();
811        for segment in segments.into_iter().flatten() {
812            if !segment.unmapped {
813                block_groups.push(BlockGroup {
814                    blocks: segment.blocks,
815                    reverse: segment.reverse ^ segment.last,
816                });
817            }
818        }
819        Self {
820            unmapped: block_groups.is_empty(),
821            block_groups,
822            secondary,
823            duplicate,
824            mapq,
825            nh,
826            split,
827            invalid_fragment_length: false,
828        }
829    }
830}
831
832fn process_unit(
833    unit: Unit,
834    features: &FeatureSet,
835    strand: StrandMode,
836    options: &CountOptions,
837    result: &mut LibraryCounts,
838) -> Result<()> {
839    if unit.unmapped {
840        result.summary.unassigned_unmapped += 1;
841        return Ok(());
842    }
843    if options.primary_only && unit.secondary {
844        result.summary.unassigned_secondary += 1;
845        return Ok(());
846    }
847    if unit.mapq < options.min_mapq {
848        result.summary.unassigned_mapping_quality += 1;
849        return Ok(());
850    }
851    if options.ignore_duplicates && unit.duplicate {
852        result.summary.unassigned_duplicate += 1;
853        return Ok(());
854    }
855    if unit.nh > 1 && options.multi_map == Contribution::Exclude {
856        result.summary.unassigned_multi_mapping += 1;
857        return Ok(());
858    }
859    match options.split {
860        SplitMode::Only if !unit.split => {
861            result.summary.unassigned_non_split += 1;
862            return Ok(());
863        }
864        SplitMode::Exclude if unit.split => {
865            result.summary.unassigned_split += 1;
866            return Ok(());
867        }
868        _ => {}
869    }
870
871    let raw_hits = unit_hits(
872        features,
873        &unit.block_groups,
874        strand,
875        options.frac_overlap_feature > 0.0,
876    );
877    if raw_hits.is_empty() {
878        result.summary.unassigned_no_features += 1;
879        return Ok(());
880    }
881    let read_bases: u64 = unit
882        .block_groups
883        .iter()
884        .flat_map(|group| &group.blocks)
885        .map(Block::len)
886        .sum();
887    let overlap_hits: Hits = raw_hits
888        .into_iter()
889        .filter(|hit| {
890            hit.overlap_bases >= options.min_overlap
891                && ratio_at_least(hit.overlap_bases, read_bases, options.frac_overlap)
892        })
893        .collect();
894    if overlap_hits.is_empty() {
895        result.summary.unassigned_overlapping_length += 1;
896        return Ok(());
897    }
898    let hits: Hits = overlap_hits
899        .into_iter()
900        .filter(|hit| {
901            ratio_at_least(
902                hit.feature_overlap_bases,
903                hit.feature_length,
904                options.frac_overlap_feature,
905            )
906        })
907        .collect();
908    if hits.is_empty() {
909        result.summary.unassigned_no_features += 1;
910        return Ok(());
911    }
912    if hits.len() > 1 && options.multi_overlap == Contribution::Exclude {
913        result.summary.unassigned_ambiguity += 1;
914        return Ok(());
915    }
916    if unit.invalid_fragment_length {
917        result.summary.unassigned_fragment_length += 1;
918        return Ok(());
919    }
920
921    let mapping_factor = if unit.nh > 1 && options.multi_map == Contribution::Fractional {
922        1.0 / f64::from(unit.nh)
923    } else {
924        1.0
925    };
926    let overlap_factor = if hits.len() > 1 && options.multi_overlap == Contribution::Fractional {
927        1.0 / hits.len() as f64
928    } else {
929        1.0
930    };
931    let contribution = mapping_factor * overlap_factor;
932    for hit in hits {
933        result.values[hit.row] += contribution;
934    }
935    result.summary.assigned += 1;
936    Ok(())
937}
938
939fn ratio_at_least(numerator: u64, denominator: u64, threshold: f64) -> bool {
940    threshold == 0.0 || numerator as f64 / denominator as f64 >= threshold
941}
942
943fn unit_hits(
944    features: &FeatureSet,
945    groups: &[BlockGroup],
946    strand: StrandMode,
947    track_feature_fraction: bool,
948) -> Hits {
949    let per_group: SmallVec<[Hits; 2]> = groups
950        .iter()
951        .map(|group| features.hits(&group.blocks, strand, group.reverse, track_feature_fraction))
952        .collect();
953    if per_group.len() <= 1 {
954        return per_group.into_iter().next().unwrap_or_default();
955    }
956
957    let mut common: Option<std::collections::HashSet<usize>> = None;
958    for hits in &per_group {
959        let rows: std::collections::HashSet<_> = hits.iter().map(|hit| hit.row).collect();
960        common = Some(match common {
961            Some(current) => current.intersection(&rows).copied().collect(),
962            None => rows,
963        });
964    }
965    let common = common.unwrap_or_default();
966    let restrict_to_common = !common.is_empty();
967    let mut overlap = BTreeMap::<usize, Hit>::new();
968    for hits in per_group {
969        for hit in hits {
970            if !restrict_to_common || common.contains(&hit.row) {
971                overlap
972                    .entry(hit.row)
973                    .and_modify(|current| {
974                        current.overlap_bases += hit.overlap_bases;
975                        if u128::from(hit.feature_overlap_bases)
976                            * u128::from(current.feature_length)
977                            > u128::from(current.feature_overlap_bases)
978                                * u128::from(hit.feature_length)
979                        {
980                            current.feature_overlap_bases = hit.feature_overlap_bases;
981                            current.feature_length = hit.feature_length;
982                        }
983                    })
984                    .or_insert(hit);
985            }
986        }
987    }
988    overlap.into_values().collect()
989}
990
991#[cfg(test)]
992mod tests {
993    use crate::model::{CountLevel, PartInput, Strand};
994
995    use super::*;
996
997    fn features() -> FeatureSet {
998        FeatureSet::build(
999            vec![
1000                PartInput {
1001                    id: "a".to_owned(),
1002                    chrom: "chr1".to_owned(),
1003                    start: 100,
1004                    end: 150,
1005                    strand: Strand::Forward,
1006                },
1007                PartInput {
1008                    id: "b".to_owned(),
1009                    chrom: "chr1".to_owned(),
1010                    start: 140,
1011                    end: 200,
1012                    strand: Strand::Reverse,
1013                },
1014            ],
1015            CountLevel::MetaFeature,
1016        )
1017        .unwrap()
1018    }
1019
1020    fn unit() -> Unit {
1021        Unit {
1022            block_groups: smallvec::smallvec![BlockGroup {
1023                blocks: smallvec::smallvec![Block::new(Some(0), 145, 155).unwrap()],
1024                reverse: false,
1025            }],
1026            unmapped: false,
1027            secondary: false,
1028            duplicate: false,
1029            mapq: 60,
1030            nh: 1,
1031            split: false,
1032            invalid_fragment_length: false,
1033        }
1034    }
1035
1036    #[test]
1037    fn ambiguity_is_one_accounted_unit() {
1038        let mut result = LibraryCounts {
1039            values: vec![0.0; 2],
1040            summary: CountSummary::default(),
1041        };
1042        process_unit(
1043            unit(),
1044            &features(),
1045            StrandMode::Unstranded,
1046            &CountOptions::default(),
1047            &mut result,
1048        )
1049        .unwrap();
1050        assert_eq!(result.summary.unassigned_ambiguity, 1);
1051        assert_eq!(result.summary.total(), 1);
1052    }
1053
1054    #[test]
1055    fn fractional_multi_overlap_is_deterministic() {
1056        let mut result = LibraryCounts {
1057            values: vec![0.0; 2],
1058            summary: CountSummary::default(),
1059        };
1060        let options = CountOptions {
1061            multi_overlap: Contribution::Fractional,
1062            ..CountOptions::default()
1063        };
1064        process_unit(
1065            unit(),
1066            &features(),
1067            StrandMode::Unstranded,
1068            &options,
1069            &mut result,
1070        )
1071        .unwrap();
1072        assert_eq!(result.values, [0.5, 0.5]);
1073        assert_eq!(result.summary.assigned, 1);
1074    }
1075}