perex 0.1.0

An ECMAScript regex engine designed for explicit host memory ownership
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

//! Emission uses only the prepared arena and budget, never an input view.
use super::*;

impl core::fmt::Debug for Prepared<'_> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("Prepared")
            .field("required_words", &self.size)
            .field("remaining_work", &self.budget.remaining())
            .finish_non_exhaustive()
    }
}

impl Prepared<'_> {
    /// Exact final storage, including names, ranges and repetition metadata.
    pub fn required_words(&self) -> usize {
        self.size
    }

    pub fn remaining_work(&self) -> usize {
        self.budget.remaining()
    }

    pub(super) fn step(&mut self) -> Result<(), CompileError> {
        self.budget.charge(1).map_err(|_| CompileError::WorkLimit)
    }

    /// Emit once into caller storage and release every parse-scratch borrow.
    /// The returned program borrows only output. Insufficient storage consumes
    /// the plan too; query the exact size before allocating. Every error leaves
    /// the output's first word invalid, so no partial program is published.
    pub fn emit<'p>(self, output: &'p mut [u32]) -> Result<Program<'p>, CompileError> {
        if let Some(first) = output.first_mut() {
            *first = 0;
        }
        let size = self.size;
        if output.len() < size {
            return Err(CompileError::ProgramStorage {
                required_words: size,
            });
        }
        let output = &mut output[..size];
        if let Err(error) = self.emit_into(output) {
            output[0] = 0;
            return Err(error);
        }
        // emit_into has validated these exact immutable words under the same
        // operation budget. No callback or write occurs between that and here.
        Ok(Program { words: output })
    }

    fn emit_into(mut self, output: &mut [u32]) -> Result<(), CompileError> {
        let (root, count, bits, base_size) = (self.root, self.count, self.flags, self.base_size);
        let parser = &mut self;
        parser.write_names(output, base_size)?;
        // Emitter walks the topologically ordered arena backwards. It does not use
        // the native stack for a long sequence or expand counted repetitions.
        parser.nodes[root as usize].start = 1;
        let mut repeat_id = 0;
        let write = |out: &mut [u32], pc: u32, op: u32, a: u32, b: u32| {
            let at = HEADER + pc as usize * 3;
            out[at..at + 3].copy_from_slice(&[op, a, b]);
        };
        for i in (0..parser.used).rev() {
            parser.step()?;
            let n = parser.nodes[i];
            let pc = n.start;
            let mut child = |id: u32, start: u32, reverse: bool| {
                parser.nodes[id as usize].start = start;
                parser.nodes[id as usize].reverse = reverse;
            };
            match n.kind {
                EMPTY | NAME_META | NAME_DECL => {}
                WRAP => child(n.a, pc, n.reverse),
                SEQ => {
                    let (a, b) = if n.reverse { (n.b, n.a) } else { (n.a, n.b) };
                    let len = parser.nodes[a as usize].len;
                    parser.nodes[a as usize].start = pc;
                    parser.nodes[a as usize].reverse = n.reverse;
                    parser.nodes[b as usize].start = pc + len;
                    parser.nodes[b as usize].reverse = n.reverse;
                }
                ALT => {
                    let len = parser.nodes[n.a as usize].len;
                    let right = pc + len + 2;
                    parser.nodes[n.a as usize].start = pc + 1;
                    parser.nodes[n.a as usize].reverse = n.reverse;
                    parser.nodes[n.b as usize].start = right;
                    parser.nodes[n.b as usize].reverse = n.reverse;
                    write(output, pc, SPLIT, pc + 1, right);
                    write(output, right - 1, JUMP, pc + n.len, 0);
                }
                GROUP => {
                    child(n.a, pc + 1, n.reverse);
                    write(output, pc, SAVE, n.b * 2 + u32::from(n.reverse), 0);
                    write(
                        output,
                        pc + n.len - 1,
                        SAVE,
                        n.b * 2 + u32::from(!n.reverse),
                        0,
                    );
                }
                ASSERT => {
                    child(n.a, pc + 1, n.flags & 2 != 0);
                    write(output, pc, ASSERT, pc + n.len, n.flags);
                    write(output, pc + n.len - 1, ASSERT_END, 0, 0);
                }
                REPEAT => {
                    child(n.a, pc + 3, n.reverse);
                    for (delta, op) in [
                        (0, REPEAT_INIT),
                        (1, REPEAT_CHOICE),
                        (2, REPEAT_BODY),
                        (n.len - 1, REPEAT_NEXT),
                    ] {
                        write(output, pc + delta, op, repeat_id, 0);
                    }
                    let at = HEADER
                        + count as usize * 3
                        + parser.range_used * 2
                        + repeat_id as usize * 8;
                    output[at..at + 8].copy_from_slice(&[
                        n.b,
                        n.c,
                        n.flags,
                        pc + 2,
                        pc + n.len,
                        n.first,
                        n.end,
                        0,
                    ]);
                    repeat_id += 1;
                }
                op => write(output, pc, modified(op, n.flags), n.a, n.b),
            }
        }
        write(output, 0, SAVE, 0, 0);
        write(output, count - 2, SAVE, 1, 0);
        write(output, count - 1, MATCH, 0, 0);
        let start = HEADER + count as usize * 3;
        for (i, range) in parser.ranges[..parser.range_used].iter().enumerate() {
            parser
                .budget
                .charge(1)
                .map_err(|_| CompileError::WorkLimit)?;
            output[start + i * 2..start + i * 2 + 2].copy_from_slice(&[range.lo, range.hi]);
        }
        output[..HEADER].copy_from_slice(&[
            MAGIC,
            VERSION,
            bits | if parser.name_count != 0 { NAMES } else { 0 },
            parser.captures,
            count,
            parser.range_used as u32,
            parser.repeats,
            0,
            0,
            0,
        ]);
        // Preserve the existing atom instruction and its admission-hint address.
        // The entry selects a bounded retry record in the same evaluator; keeping
        // the generic body words avoids a second program or an AST relocation pass.
        for i in 0..parser.repeats as usize {
            parser.step()?;
            let p = Program { words: output };
            let r = p.repeat(i);
            let entry = r[3] as usize - 2;
            if r[4] as usize == entry + 5 && r[5] == r[6] && consuming(p.instruction(entry + 3)[0])
            {
                output[HEADER + entry * 3] = ATOM_REPEAT;
                let at = HEADER + count as usize * 3 + parser.range_used * 2 + i * 8;
                output[at + 7] = 1;
            }
        }
        if parser.repeats != 0 {
            let hint = parser.admission(Program { words: output }, root)?;
            output[2] |= hint;
        }
        parser.candidate()?;
        output[7] = parser.candidate_descriptor(root);
        output[8] = parser.end_candidate_descriptor(root);
        // Derived from the emitted instructions with the same function the
        // validator re-runs, so the stored word cannot disagree with the program.
        output[9] = crate::program::derive_run_skip(output, Program { words: output })
            | crate::program::derive_leading(output, count as usize)
            | if parser.forward {
                crate::program::ADMISSION_FORWARD
            } else {
                0
            };
        Program::from_words(output, parser.budget)
            .map(|_| ())
            .map_err(|e| match e {
                ProgramError::WorkLimit => CompileError::WorkLimit,
                ProgramError::Invalid => CompileError::InvalidProgram,
            })
    }
}