daggrs 0.1.1

A fast Double-Array Aho-Corasick implementation for multi-pattern matching
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

use crate::types::Match;

use super::{Trie, DEAD_STATE};

/// Iterator over matches found in text using the trie.
pub struct TrieFindIter<'a> {
    trie: &'a Trie,
    text: &'a [u8],
    pos: usize,
    state: usize,
    outpos: u32,
}

impl<'a> TrieFindIter<'a> {
    pub(super) fn new(trie: &'a Trie, text: &'a [u8]) -> Self {
        Self {
            trie,
            text,
            pos: 0,
            state: 0,
            outpos: u32::MAX,
        }
    }

    #[inline]
    fn next_overlapping(&mut self) -> Option<Match> {
        // Yield pending outputs from output chain
        if self.outpos != u32::MAX {
            let output = &self.trie.outputs[self.outpos as usize];
            self.outpos = output.parent;
            return Some(Match {
                pattern_id: output.pattern_id,
                start: self.pos - output.length as usize,
                end: self.pos,
            });
        }

        // Process input bytes
        while self.pos < self.text.len() {
            let byte = self.text[self.pos];
            self.pos += 1;

            // Follow failure links until we find a transition or reach root
            while self.state != 0 && !self.trie.states[self.state].edges.contains_key(&byte) {
                self.state = self.trie.states[self.state].fail as usize;
            }
            self.state = self.trie.states[self.state]
                .edges
                .get(&byte)
                .copied()
                .unwrap_or(0) as usize;

            // Check for outputs
            self.outpos = self.trie.states[self.state].outpos.unwrap_or(u32::MAX);
            if self.outpos != u32::MAX {
                let output = &self.trie.outputs[self.outpos as usize];
                self.outpos = output.parent;
                return Some(Match {
                    pattern_id: output.pattern_id,
                    start: self.pos - output.length as usize,
                    end: self.pos,
                });
            }
        }

        None
    }

    #[inline]
    fn next_leftmost(&mut self) -> Option<Match> {
        let mut state: usize = 0;
        let mut last_outpos: Option<u32> = None;

        for read_pos in self.pos..self.text.len() {
            let byte = self.text[read_pos];

            // Transition with failure link fallback
            loop {
                if let Some(&next) = self.trie.states[state].edges.get(&byte) {
                    state = next as usize;
                    break;
                } else if state == 0 {
                    break;
                } else {
                    let fail = self.trie.states[state].fail;
                    if fail == DEAD_STATE {
                        if let Some(outpos) = last_outpos {
                            let output = &self.trie.outputs[outpos as usize];
                            return Some(Match {
                                pattern_id: output.pattern_id,
                                start: self.pos - output.length as usize,
                                end: self.pos,
                            });
                        }
                        state = 0;
                        break;
                    }
                    state = fail as usize;
                }
            }

            if let Some(outpos) = self.trie.states[state].outpos {
                last_outpos = Some(outpos);
                self.pos = read_pos + 1;
            }
        }

        // Yield any remaining match at end of text
        if let Some(outpos) = last_outpos {
            let output = &self.trie.outputs[outpos as usize];
            return Some(Match {
                pattern_id: output.pattern_id,
                start: self.pos - output.length as usize,
                end: self.pos,
            });
        }

        None
    }
}

impl Iterator for TrieFindIter<'_> {
    type Item = Match;

    #[inline]
    fn next(&mut self) -> Option<Match> {
        match self.trie.match_kind {
            crate::types::MatchKind::Overlapping => self.next_overlapping(),
            crate::types::MatchKind::LeftmostFirst
            | crate::types::MatchKind::LeftmostLongest
            | crate::types::MatchKind::WordPiece => self.next_leftmost(),
        }
    }
}