1use 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
20const CHUNK_RECORDS: usize = 64;
22
23#[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#[derive(Clone, Debug)]
33pub struct SequenceStats {
34 pub characters: Box<[u64; 256]>,
36 pub lowercase_folded: u64,
38 pub t_u_folded: u64,
40 pub trailing_whitespace_lines: u64,
42 pub interior_whitespace: Tally,
44 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 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#[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#[derive(Debug, Default)]
87pub struct NormalisedBatch {
88 pub rows: Vec<u8>,
90 pub records: usize,
92 pub header_values: Vec<Vec<String>>,
94 pub sequence_stats: SequenceStats,
96 pub header_stats: HeaderStats,
98}
99
100#[derive(Clone, Copy, Debug)]
102pub struct Normaliser<'a> {
103 pub table: &'a ByteClassTable,
105 pub mode: ValidationMode,
107 pub width: usize,
109 pub header: Option<&'a HeaderSpec>,
111 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 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 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; }
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
341pub(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 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 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 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 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 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}