Skip to main content

rsomics_seq/operations/
grep.rs

1use std::collections::HashSet;
2use std::io::Write;
3
4use memchr::memmem;
5use rsomics_common::{Result, RsomicsError};
6use rsomics_seqio::Format;
7use serde::Serialize;
8
9use crate::input::copy_matching_records;
10use crate::operations::stats::{SeqType, classify_record};
11
12/// Record field selected by [`grep_records`].
13#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
14#[serde(rename_all = "lowercase")]
15pub enum GrepMode {
16    /// Match the identifier before its first ASCII whitespace.
17    Id,
18    /// Match the complete FASTA/FASTQ header.
19    Name,
20    /// Find a literal pattern within the sequence.
21    Sequence,
22}
23
24/// Options for literal FASTA/FASTQ record filtering.
25#[derive(Debug, Clone, PartialEq, Eq)]
26pub struct GrepOptions {
27    /// Literal patterns. ID and name matching use whole-string equality;
28    /// sequence matching uses substring search.
29    pub patterns: Vec<String>,
30    /// Record field to search.
31    pub mode: GrepMode,
32    /// Compare ASCII letters case-insensitively.
33    pub ignore_case: bool,
34    /// Keep non-matching records.
35    pub invert_match: bool,
36    /// Search only the positive strand in sequence mode.
37    pub only_positive_strand: bool,
38}
39
40/// Summary of one record-filtering pass.
41#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
42pub struct GrepReport {
43    /// Input path as supplied by the caller, or `-` for stdin.
44    pub input: String,
45    /// Detected input format.
46    pub format: &'static str,
47    /// Selected record field.
48    pub mode: GrepMode,
49    /// Number of distinct literal patterns.
50    pub pattern_count: usize,
51    /// Whether matching ignored ASCII case.
52    pub ignore_case: bool,
53    /// Whether the selection was inverted.
54    pub invert_match: bool,
55    /// Whether sequence matching searched only the positive strand.
56    pub only_positive_strand: bool,
57    /// Number of input records scanned.
58    pub total_records: u64,
59    /// Number of records emitted.
60    pub matched_records: u64,
61}
62
63enum Patterns {
64    Exact(HashSet<Vec<u8>>),
65    Substring(Vec<Vec<u8>>),
66}
67
68impl Patterns {
69    fn build(options: &GrepOptions) -> Result<Self> {
70        if options.patterns.is_empty() {
71            return Err(RsomicsError::InvalidInput(
72                "grep requires at least one pattern".into(),
73            ));
74        }
75        if options.only_positive_strand && options.mode != GrepMode::Sequence {
76            return Err(RsomicsError::InvalidInput(
77                "--only-positive-strand requires --by-seq".into(),
78            ));
79        }
80
81        let normalize = |pattern: &str| {
82            if options.ignore_case {
83                pattern.as_bytes().to_ascii_lowercase()
84            } else {
85                pattern.as_bytes().to_vec()
86            }
87        };
88        let normalized: HashSet<Vec<u8>> = options
89            .patterns
90            .iter()
91            .map(|value| normalize(value))
92            .collect();
93        if options.mode == GrepMode::Sequence {
94            for pattern in &options.patterns {
95                if !is_legal_sequence_pattern(pattern.as_bytes()) {
96                    return Err(RsomicsError::InvalidInput(format!(
97                        "illegal DNA/RNA/protein sequence pattern: {pattern}"
98                    )));
99                }
100            }
101            Ok(Self::Substring(normalized.into_iter().collect()))
102        } else {
103            Ok(Self::Exact(normalized))
104        }
105    }
106
107    fn matches(&self, target: &[u8], ignore_case: bool) -> bool {
108        let lowered;
109        let target = if ignore_case {
110            lowered = target.to_ascii_lowercase();
111            lowered.as_slice()
112        } else {
113            target
114        };
115        match self {
116            Self::Exact(patterns) => patterns.contains(target),
117            Self::Substring(patterns) => patterns.iter().any(|pattern| {
118                if pattern.is_empty() {
119                    target.is_empty()
120                } else {
121                    memmem::find(target, pattern).is_some()
122                }
123            }),
124        }
125    }
126}
127
128/// Filters records while preserving input order and format.
129///
130/// ID and full-name modes implement SeqKit's literal whole-target semantics.
131/// Sequence mode implements literal substring matching and searches both
132/// strands for DNA/RNA input unless `only_positive_strand` is set. Protein or
133/// unclassified input is searched on the positive strand only.
134///
135/// # Errors
136///
137/// Returns an error for an empty pattern set, an illegal sequence pattern,
138/// malformed input, count overflow, or output failure.
139pub fn grep_records(
140    input: &str,
141    options: &GrepOptions,
142    output: &mut dyn Write,
143) -> Result<GrepReport> {
144    let patterns = Patterns::build(options)?;
145    let pattern_count = match &patterns {
146        Patterns::Exact(patterns) => patterns.len(),
147        Patterns::Substring(patterns) => patterns.len(),
148    };
149    let mut sequence_type = None;
150
151    let (format, total_records, matched_records) =
152        copy_matching_records(input, output, |record| {
153            let sequence_type = *sequence_type.get_or_insert_with(|| classify_record(record.seq));
154            let hit = match options.mode {
155                GrepMode::Id => patterns.matches(split_id(record.id), options.ignore_case),
156                GrepMode::Name => patterns.matches(record.id, options.ignore_case),
157                GrepMode::Sequence => sequence_matches(
158                    record.seq,
159                    &patterns,
160                    options.ignore_case,
161                    options.only_positive_strand,
162                    sequence_type,
163                ),
164            };
165            Ok(hit != options.invert_match)
166        })?;
167
168    Ok(GrepReport {
169        input: input.to_owned(),
170        format: format_name(format),
171        mode: options.mode,
172        pattern_count,
173        ignore_case: options.ignore_case,
174        invert_match: options.invert_match,
175        only_positive_strand: options.only_positive_strand,
176        total_records,
177        matched_records,
178    })
179}
180
181fn split_id(name: &[u8]) -> &[u8] {
182    name.split(|byte| byte.is_ascii_whitespace())
183        .next()
184        .unwrap_or(name)
185}
186
187fn sequence_matches(
188    sequence: &[u8],
189    patterns: &Patterns,
190    ignore_case: bool,
191    only_positive: bool,
192    sequence_type: SeqType,
193) -> bool {
194    if patterns.matches(sequence, ignore_case) {
195        return true;
196    }
197    if only_positive || matches!(sequence_type, SeqType::Protein | SeqType::Unlimit) {
198        return false;
199    }
200    let reverse = reverse_complement(sequence, sequence_type);
201    patterns.matches(&reverse, ignore_case)
202}
203
204fn reverse_complement(sequence: &[u8], sequence_type: SeqType) -> Vec<u8> {
205    sequence
206        .iter()
207        .rev()
208        .map(|&byte| match byte {
209            b'A' => {
210                if sequence_type == SeqType::Rna {
211                    b'U'
212                } else {
213                    b'T'
214                }
215            }
216            b'a' => {
217                if sequence_type == SeqType::Rna {
218                    b'u'
219                } else {
220                    b't'
221                }
222            }
223            b'T' | b'U' => b'A',
224            b't' | b'u' => b'a',
225            b'C' => b'G',
226            b'c' => b'g',
227            b'G' => b'C',
228            b'g' => b'c',
229            b'R' => b'Y',
230            b'r' => b'y',
231            b'Y' => b'R',
232            b'y' => b'r',
233            b'K' => b'M',
234            b'k' => b'm',
235            b'M' => b'K',
236            b'm' => b'k',
237            b'B' => b'V',
238            b'b' => b'v',
239            b'V' => b'B',
240            b'v' => b'b',
241            b'D' => b'H',
242            b'd' => b'h',
243            b'H' => b'D',
244            b'h' => b'd',
245            other => other,
246        })
247        .collect()
248}
249
250fn is_legal_sequence_pattern(pattern: &[u8]) -> bool {
251    pattern
252        .iter()
253        .all(|byte| byte.is_ascii_alphabetic() || matches!(byte, b' ' | b'-' | b'.' | b'*' | b'_'))
254}
255
256fn format_name(format: Format) -> &'static str {
257    match format {
258        Format::Fasta => "FASTA",
259        Format::Fastq => "FASTQ",
260    }
261}
262
263#[cfg(test)]
264mod tests {
265    use super::*;
266
267    #[test]
268    fn id_is_first_header_token() {
269        assert_eq!(split_id(b"seq1 description"), b"seq1");
270    }
271
272    #[test]
273    fn reverse_complement_tracks_dna_and_rna() {
274        assert_eq!(reverse_complement(b"ACGT", SeqType::Dna), b"ACGT");
275        assert_eq!(reverse_complement(b"ACGU", SeqType::Rna), b"ACGU");
276        assert_eq!(
277            reverse_complement(b"RYSWKMBVDHN", SeqType::Dna),
278            b"NDHBVKMWSRY"
279        );
280    }
281
282    #[test]
283    fn empty_sequence_pattern_only_matches_empty_sequence() {
284        let patterns = Patterns::Substring(vec![Vec::new()]);
285        assert!(patterns.matches(b"", false));
286        assert!(!patterns.matches(b"A", false));
287    }
288}