Skip to main content

dima_core/
normalise.rs

1//! Parallel normalisation of raw records into fixed-width rows of canonical residues.
2//!
3//! Every sequence byte is classified through the alphabet's [`ByteClassTable`]: residues become
4//! their upper-case canonical letter (T/U folded), every other column becomes 0 (it excludes the
5//! k-mers that contain it), whitespace is skipped (D37), a NUL byte is a structural error (D38)
6//! and unknown characters follow the validation mode (D3). Each record must have exactly as many
7//! alignment columns as the first (D36). Records are processed in parallel chunks and the results
8//! merged in input order, so statistics, examples and the first error are deterministic.
9
10use rayon::prelude::*;
11
12use crate::alphabet::{ByteClassTable, is_whitespace};
13use crate::config::ValidationMode;
14use crate::diagnostics::Tally;
15use crate::error::{DimaError, Location, Result};
16use crate::header::{HeaderPosition, HeaderSpec, HeaderStats, parse_header};
17use crate::input::RawBatch;
18use crate::model::ByteClass;
19
20/// Records per parallel task.
21const CHUNK_RECORDS: usize = 64;
22
23/// Number of alignment columns in a sequence: every byte except line feeds and whitespace.
24#[must_use]
25pub fn count_columns(seq: &[u8]) -> usize {
26    seq.iter()
27        .filter(|&&b| b != b'\n' && !is_whitespace(b))
28        .count()
29}
30
31/// Character and whitespace statistics of sequence lines, mergeable in input order.
32#[derive(Clone, Debug)]
33pub struct SequenceStats {
34    /// Occurrences of each byte value in sequence lines (line endings excluded).
35    pub characters: Box<[u64; 256]>,
36    /// Lower-case letters folded to upper case.
37    pub lowercase_folded: u64,
38    /// T (RNA) or U (DNA) folded to the alphabet's letter.
39    pub t_u_folded: u64,
40    /// Lines with trailing whitespace.
41    pub trailing_whitespace_lines: u64,
42    /// Lines with whitespace before a residue, with examples.
43    pub interior_whitespace: Tally,
44    /// Characters of class unknown (permissive/report modes), with examples.
45    pub unknown: Tally,
46}
47
48impl Default for SequenceStats {
49    fn default() -> Self {
50        Self {
51            characters: Box::new([0; 256]),
52            lowercase_folded: 0,
53            t_u_folded: 0,
54            trailing_whitespace_lines: 0,
55            interior_whitespace: Tally::default(),
56            unknown: Tally::default(),
57        }
58    }
59}
60
61impl SequenceStats {
62    /// Adds statistics of later input.
63    pub fn merge(&mut self, other: Self) {
64        for (a, b) in self.characters.iter_mut().zip(other.characters.iter()) {
65            *a += b;
66        }
67        self.lowercase_folded += other.lowercase_folded;
68        self.t_u_folded += other.t_u_folded;
69        self.trailing_whitespace_lines += other.trailing_whitespace_lines;
70        self.interior_whitespace.merge(other.interior_whitespace);
71        self.unknown.merge(other.unknown);
72    }
73}
74
75/// Printable description of a byte for messages: `'J' (0x4A)` or `0xC3`.
76#[must_use]
77pub fn describe_byte(b: u8) -> String {
78    if b.is_ascii_graphic() {
79        format!("'{}' (0x{b:02X})", char::from(b))
80    } else {
81        format!("0x{b:02X}")
82    }
83}
84
85/// The result of normalising one batch.
86#[derive(Debug, Default)]
87pub struct NormalisedBatch {
88    /// `records × width` canonical bytes (0 = excluded column).
89    pub rows: Vec<u8>,
90    /// Number of records.
91    pub records: usize,
92    /// Cleaned values of the stratified header fields, per record (empty without a format).
93    pub header_values: Vec<Vec<String>>,
94    /// Sequence statistics.
95    pub sequence_stats: SequenceStats,
96    /// Header statistics.
97    pub header_stats: HeaderStats,
98}
99
100/// Normalises batches for one alphabet, alignment width and header format.
101#[derive(Clone, Copy, Debug)]
102pub struct Normaliser<'a> {
103    /// Symbol table of the resolved alphabet.
104    pub table: &'a ByteClassTable,
105    /// Validation mode.
106    pub mode: ValidationMode,
107    /// Alignment width *L* (columns of the first record).
108    pub width: usize,
109    /// Header format, if metadata are parsed.
110    pub header: Option<&'a HeaderSpec>,
111    /// Input name for messages.
112    pub source: &'a str,
113}
114
115struct ChunkOut {
116    header_values: Vec<Vec<String>>,
117    sequence_stats: SequenceStats,
118    header_stats: HeaderStats,
119    error: Option<DimaError>,
120}
121
122impl Normaliser<'_> {
123    /// Normalises `batch` into `out` (reusing its allocations). Runs on the current rayon pool.
124    ///
125    /// # Errors
126    /// The first error in input order: invalid UTF-8 in a header (strict), a NUL byte, an
127    /// unknown character (strict), or a record whose length differs from the alignment width.
128    pub fn normalise(&self, batch: &RawBatch, out: &mut NormalisedBatch) -> Result<()> {
129        let n = batch.len();
130        out.records = n;
131        out.rows.clear();
132        out.rows.resize(n * self.width, 0);
133        out.header_values.clear();
134        out.sequence_stats = SequenceStats::default();
135        out.header_stats = HeaderStats::default();
136        if n == 0 {
137            return Ok(());
138        }
139        let chunk_bytes = (CHUNK_RECORDS * self.width).max(1);
140        let chunks: Vec<ChunkOut> = if self.width == 0 {
141            // Unreachable for valid input (the first record defines a positive width), but keep
142            // the record-level error path rather than dividing rows by zero.
143            vec![self.normalise_chunk(batch, 0, &mut [])]
144        } else {
145            out.rows
146                .par_chunks_mut(chunk_bytes)
147                .enumerate()
148                .map(|(c, rows)| self.normalise_chunk(batch, c * CHUNK_RECORDS, rows))
149                .collect()
150        };
151        for chunk in chunks {
152            if let Some(e) = chunk.error {
153                return Err(e);
154            }
155            out.header_values.extend(chunk.header_values);
156            out.sequence_stats.merge(chunk.sequence_stats);
157            out.header_stats.merge(chunk.header_stats);
158        }
159        Ok(())
160    }
161
162    fn normalise_chunk(&self, batch: &RawBatch, first: usize, rows: &mut [u8]) -> ChunkOut {
163        let mut out = ChunkOut {
164            header_values: Vec::new(),
165            sequence_stats: SequenceStats::default(),
166            header_stats: HeaderStats::default(),
167            error: None,
168        };
169        let count = rows
170            .len()
171            .checked_div(self.width)
172            .unwrap_or(batch.len() - first);
173        for j in 0..count {
174            let i = first + j;
175            let r = &batch.records[i];
176            let record_no = batch.first_record + i as u64;
177            if let Some(spec) = self.header {
178                let at = HeaderPosition {
179                    source: self.source,
180                    record: record_no,
181                    line: r.line,
182                    byte: r.byte,
183                };
184                match parse_header(batch.header(i), spec, self.mode, at, &mut out.header_stats) {
185                    Ok(v) => out.header_values.push(v),
186                    Err(e) => {
187                        out.error = Some(e);
188                        return out;
189                    }
190                }
191            }
192            let (seq, offset) = batch.sequence(i);
193            let row = if self.width == 0 {
194                &mut [][..]
195            } else {
196                &mut rows[j * self.width..(j + 1) * self.width]
197            };
198            let start = SeqStart {
199                record: record_no,
200                line: r.line + 1,
201                byte: r.byte + offset as u64,
202            };
203            if let Err(e) = self.normalise_record(seq, row, start, &mut out.sequence_stats) {
204                out.error = Some(e);
205                return out;
206            }
207        }
208        out
209    }
210
211    fn location(&self, start: SeqStart, line: u64, column: u64, byte: u64) -> Location {
212        Location::new(self.source)
213            .record(start.record)
214            .line(line)
215            .column(column)
216            .byte(byte)
217    }
218
219    fn normalise_record(
220        &self,
221        seq: &[u8],
222        row: &mut [u8],
223        start: SeqStart,
224        st: &mut SequenceStats,
225    ) -> Result<()> {
226        let strict = self.mode == ValidationMode::Strict;
227        let mut col = 0usize;
228        let mut line = start.line;
229        let mut pending_ws = false;
230        let mut interior_on_line = false;
231        let mut i = 0usize;
232        while i < seq.len() {
233            let b = seq[i];
234            if b == b'\n' || (b == b'\r' && seq.get(i + 1) == Some(&b'\n')) {
235                if b == b'\r' {
236                    i += 1; // CR LF: the CR is part of the line ending.
237                }
238                if pending_ws {
239                    st.trailing_whitespace_lines += 1;
240                }
241                if interior_on_line {
242                    let (r, l) = (start.record, line);
243                    st.interior_whitespace
244                        .add(1, || format!("record {r}, line {l}"));
245                }
246                pending_ws = false;
247                interior_on_line = false;
248                line += 1;
249                i += 1;
250                continue;
251            }
252            if b == 0 {
253                return Err(DimaError::input_format(
254                    self.location(start, line, col as u64 + 1, start.byte + i as u64),
255                    "NUL byte in a sequence",
256                )
257                .with_hint("the file is binary or corrupt; FASTA is plain text"));
258            }
259            st.characters[usize::from(b)] += 1;
260            let class = self.table.class(b);
261            if class == ByteClass::Whitespace {
262                pending_ws = true;
263                i += 1;
264                continue;
265            }
266            if pending_ws {
267                interior_on_line = true;
268                pending_ws = false;
269            }
270            let canonical = match class {
271                ByteClass::Unknown => {
272                    if strict {
273                        return Err(DimaError::input_data(
274                            Some(self.location(start, line, col as u64 + 1, start.byte + i as u64)),
275                            format!(
276                                "character {} is not valid in a {} alignment",
277                                describe_byte(b),
278                                self.table.alphabet()
279                            ),
280                        )
281                        .with_hint(
282                            "check --alphabet, or use --validation permissive to exclude the \
283                             k-mers that contain such characters (they are counted and reported)",
284                        ));
285                    }
286                    let (r, l, c) = (start.record, line, col + 1);
287                    st.unknown.add(1, || {
288                        format!("{} at record {r}, line {l}, column {c}", describe_byte(b))
289                    });
290                    0
291                }
292                ByteClass::Residue => {
293                    if b.is_ascii_lowercase() {
294                        st.lowercase_folded += 1;
295                    }
296                    if self.table.is_folded_t_u(b) {
297                        st.t_u_folded += 1;
298                    }
299                    self.table.canonical(b)
300                }
301                _ => {
302                    if b.is_ascii_lowercase() {
303                        st.lowercase_folded += 1;
304                    }
305                    0
306                }
307            };
308            if let Some(slot) = row.get_mut(col) {
309                *slot = canonical;
310            }
311            col += 1;
312            i += 1;
313        }
314        if pending_ws {
315            st.trailing_whitespace_lines += 1;
316        }
317        if col == 0 {
318            return Err(empty_sequence(self.source, start.record, start.line - 1));
319        }
320        if col != self.width {
321            return Err(DimaError::input_data(
322                Some(
323                    Location::new(self.source)
324                        .record(start.record)
325                        .line(start.line - 1),
326                ),
327                format!(
328                    "the sequence has {col} alignment columns, but the first record has {}",
329                    self.width
330                ),
331            )
332            .with_hint(
333                "DiMA needs a multiple sequence alignment: every sequence must have the same \
334                 length (align them first, e.g. with MAFFT or Clustal Omega)",
335            ));
336        }
337        Ok(())
338    }
339}
340
341/// A record without sequence data (its header is on `header_line`).
342pub(crate) fn empty_sequence(source: &str, record: u64, header_line: u64) -> DimaError {
343    DimaError::input_data(
344        Some(Location::new(source).record(record).line(header_line)),
345        "the sequence is empty",
346    )
347    .with_hint(
348        "every header line must be followed by its aligned sequence; remove records without \
349         one",
350    )
351}
352
353#[derive(Clone, Copy, Debug)]
354struct SeqStart {
355    record: u64,
356    line: u64,
357    byte: u64,
358}
359
360#[cfg(test)]
361mod tests {
362    use super::*;
363    use crate::config::Alphabet;
364    use crate::input::RawRecord;
365
366    fn batch(text: &[u8]) -> RawBatch {
367        // Minimal splitter for tests: records start at '>' at line start.
368        let mut b = RawBatch {
369            first_record: 1,
370            ..RawBatch::default()
371        };
372        b.data = text.to_vec();
373        let mut starts: Vec<usize> = vec![];
374        for (i, &c) in text.iter().enumerate() {
375            if c == b'>' && (i == 0 || text[i - 1] == b'\n') {
376                starts.push(i);
377            }
378        }
379        let mut line = 1u64;
380        for (k, &s) in starts.iter().enumerate() {
381            let e = starts.get(k + 1).copied().unwrap_or(text.len());
382            let header_end = text[s..e].iter().position(|&c| c == b'\n').unwrap();
383            b.records.push(RawRecord {
384                range: s..e,
385                header_end,
386                line,
387                byte: s as u64,
388            });
389            line += text[s..e].iter().filter(|&&c| c == b'\n').count() as u64;
390        }
391        b
392    }
393
394    fn run(
395        text: &[u8],
396        alphabet: Alphabet,
397        mode: ValidationMode,
398        header: Option<&HeaderSpec>,
399    ) -> Result<NormalisedBatch> {
400        let table = ByteClassTable::new(alphabet);
401        let b = batch(text);
402        let width = count_columns(b.sequence(0).0);
403        let n = Normaliser {
404            table: &table,
405            mode,
406            width,
407            header,
408            source: "t.fa",
409        };
410        let mut out = NormalisedBatch::default();
411        n.normalise(&b, &mut out)?;
412        Ok(out)
413    }
414
415    #[test]
416    fn rows_are_canonical_and_wrapping_invariant() {
417        let a = run(
418            b">a\nACGT-N\n>b\nacgu~?\n",
419            Alphabet::Dna,
420            ValidationMode::Strict,
421            None,
422        )
423        .unwrap();
424        assert_eq!(a.rows, b"ACGT\0\0ACGT\0\0");
425        assert_eq!(a.sequence_stats.lowercase_folded, 4);
426        assert_eq!(a.sequence_stats.t_u_folded, 1);
427        // Wrapped, CRLF, trailing and interior whitespace: same rows.
428        let b = run(
429            b">a\r\nAC\r\nGT-N  \r\n>b\nac gu\n~?\t\n",
430            Alphabet::Dna,
431            ValidationMode::Strict,
432            None,
433        )
434        .unwrap();
435        assert_eq!(b.rows, a.rows);
436        assert_eq!(b.sequence_stats.trailing_whitespace_lines, 2);
437        assert_eq!(b.sequence_stats.interior_whitespace.count, 1);
438        assert_eq!(
439            b.sequence_stats.interior_whitespace.examples,
440            ["record 2, line 5"]
441        );
442        assert_eq!(b.sequence_stats.characters[usize::from(b' ')], 3);
443        assert_eq!(
444            b.sequence_stats.characters[usize::from(b'\r')],
445            0,
446            "CR LF is a line ending"
447        );
448        // RNA folds T to U; protein keeps U and O as residues and excludes X, *, #.
449        let r = run(b">a\nACGT\n", Alphabet::Rna, ValidationMode::Strict, None).unwrap();
450        assert_eq!(r.rows, b"ACGU");
451        let p = run(
452            b">a\nMUOX*#$^\n",
453            Alphabet::Protein,
454            ValidationMode::Strict,
455            None,
456        )
457        .unwrap();
458        assert_eq!(p.rows, b"MUO\0\0\0\0\0");
459    }
460
461    #[test]
462    fn strict_and_permissive_unknown_characters() {
463        let e = run(
464            b">a\nACGT\n>b\nACJT\n",
465            Alphabet::Dna,
466            ValidationMode::Strict,
467            None,
468        )
469        .unwrap_err();
470        assert_eq!(
471            e.to_string(),
472            "t.fa: record 2 (line 4, column 3, byte 13): character 'J' (0x4A) is not valid in a dna alignment"
473        );
474        assert_eq!(e.class(), crate::error::ExitClass::InvalidInput);
475        let p = run(
476            b">a\nACGT\n>b\nACJT\n",
477            Alphabet::Dna,
478            ValidationMode::Permissive,
479            None,
480        )
481        .unwrap();
482        assert_eq!(&p.rows[4..], b"AC\0T");
483        assert_eq!(p.sequence_stats.unknown.count, 1);
484        assert_eq!(
485            p.sequence_stats.unknown.examples,
486            ["'J' (0x4A) at record 2, line 4, column 3"]
487        );
488        // Non-ASCII bytes are unknown too.
489        let p = run(
490            ">a\nAC\u{e9}T\n>b\nACGTT\n".as_bytes(),
491            Alphabet::Dna,
492            ValidationMode::Report,
493            None,
494        )
495        .unwrap();
496        assert_eq!(p.sequence_stats.unknown.count, 2, "both bytes of é");
497    }
498
499    #[test]
500    fn structural_errors() {
501        let e = run(
502            b">a\nACGT\n>b\nAC\0T\n",
503            Alphabet::Dna,
504            ValidationMode::Permissive,
505            None,
506        )
507        .unwrap_err();
508        assert!(e.to_string().contains("NUL byte"));
509        assert_eq!(e.class(), crate::error::ExitClass::InvalidInput);
510        let e = run(
511            b">a\nACGT\n>b\nACG\n",
512            Alphabet::Dna,
513            ValidationMode::Strict,
514            None,
515        )
516        .unwrap_err();
517        assert_eq!(
518            e.to_string(),
519            "t.fa: record 2 (line 3): the sequence has 3 alignment columns, but the first record has 4"
520        );
521        assert!(e.hint().unwrap().contains("MAFFT"));
522        let e = run(
523            b">a\nACGT\n>b\n\n",
524            Alphabet::Dna,
525            ValidationMode::Strict,
526            None,
527        )
528        .unwrap_err();
529        assert!(
530            e.to_string()
531                .contains("record 2 (line 3): the sequence is empty")
532        );
533        let e = run(
534            b">a\nACGT\n>b\nACGTA\n",
535            Alphabet::Dna,
536            ValidationMode::Strict,
537            None,
538        )
539        .unwrap_err();
540        assert!(e.to_string().contains("5 alignment columns"));
541    }
542
543    #[test]
544    fn headers_in_order_across_chunks() {
545        let mut text = Vec::new();
546        for i in 0..200 {
547            text.extend_from_slice(
548                format!(">ACC{i}|{}\nACGT\n", ["Camel", "Human"][i % 2]).as_bytes(),
549            );
550        }
551        let spec = HeaderSpec::new(
552            &["Accession".into(), "Host".into()],
553            Some(&["Host".into()]),
554            "U",
555        )
556        .unwrap();
557        let out = run(&text, Alphabet::Dna, ValidationMode::Strict, Some(&spec)).unwrap();
558        assert_eq!(out.records, 200);
559        assert_eq!(out.header_values.len(), 200);
560        assert_eq!(out.header_values[0], ["Camel"]);
561        assert_eq!(out.header_values[199], ["Human"]);
562        assert_eq!(out.header_stats.records, 200);
563        // Strict mode reports the first error in input order even across chunks.
564        let mut bad = text.clone();
565        bad.extend_from_slice(b">X|Y\nAC\xffT\n>Z|W\nACG\n");
566        let e = run(&bad, Alphabet::Dna, ValidationMode::Strict, Some(&spec)).unwrap_err();
567        assert!(e.to_string().contains("record 201"), "{e}");
568    }
569
570    #[test]
571    fn describe_bytes() {
572        assert_eq!(describe_byte(b'J'), "'J' (0x4A)");
573        assert_eq!(describe_byte(0xC3), "0xC3");
574        assert_eq!(describe_byte(b' '), "0x20");
575    }
576}