oxide_core/vm/
regexp.rs

1//! Regular-expression objects: the program store and the `RegExp` object kind.
2//! A literal allocates a new object on every evaluation, as the specification
3//! requires, over one compiled program per distinct `(source, flags)`, compiled
4//! on first use; `new RegExp(source, flags)` shares the store, so a program
5//! built in a loop does not grow it without bound. The store lives in the heap:
6//! a `RegExp` object's payload names its program, a collection marks the
7//! programs of the live objects (and their two atoms), and sweeps the rest.
8
9use oxide_regexp::CompiledRegExp;
10
11use super::error::{self, ErrorKind};
12use super::{Cx, Throw};
13use crate::heap::hash::FxHashMap;
14use crate::heap::object::ObjectKind;
15use crate::runtime::{Intrinsic, Names};
16use crate::shape::PropertyFlags;
17use crate::value::{BytecodeId, StringId, Value};
18
19/// One distinct `(source, flags)` pair, both atoms, which a live program
20/// keeps alive.
21#[derive(Clone, Copy, Debug)]
22pub struct RegExpRecord {
23    pub source: StringId,
24    pub flags: StringId,
25}
26
27#[derive(Default)]
28pub struct RegExpStore {
29    /// By program index; `None` for a free slot.
30    programs: Vec<Option<(RegExpRecord, CompiledRegExp)>>,
31    index: FxHashMap<(StringId, StringId), u32>,
32    /// Free slots, reused lowest first.
33    free: Vec<u32>,
34    /// Under `gc-stress`, slots freed by a sweep are reusable only after the
35    /// next one.
36    #[cfg(feature = "gc-stress")]
37    quarantine: Vec<u32>,
38    marks: Vec<u64>,
39    live: usize,
40    bytes: usize,
41}
42
43/// Bytes a program holds.
44fn program_bytes(program: &CompiledRegExp) -> usize {
45    size_of::<Option<(RegExpRecord, CompiledRegExp)>>()
46        + std::mem::size_of_val(program.instructions())
47        + program.group_names().map_or(0, |names| {
48            std::mem::size_of_val(names)
49                + names
50                    .iter()
51                    .flatten()
52                    .map(|name| std::mem::size_of_val(&**name))
53                    .sum::<usize>()
54        })
55}
56
57impl RegExpStore {
58    /// The program for `(source, flags)`, compiled and stored on first use;
59    /// the compiler's diagnostic when the pattern or the flags are invalid.
60    /// It allocates nothing on the heap: the caller stores the index in a
61    /// `RegExp` object before its next allocation.
62    pub(crate) fn intern(
63        &mut self,
64        strings: &crate::heap::arena::Arena<crate::heap::string::StringRecord>,
65        source: StringId,
66        flags: StringId,
67    ) -> Result<u32, String> {
68        if let Some(&index) = self.index.get(&(source, flags)) {
69            return Ok(index);
70        }
71        let units = |id: StringId| -> Vec<u16> {
72            strings
73                .get(id.index())
74                .flat()
75                .expect("an atom is flat")
76                .units()
77                .collect()
78        };
79        let program = oxide_regexp::compile(&units(source), &units(flags))
80            .map_err(|error| oxide_regexp::javascript_compile_error_message(&error).to_owned())?;
81        self.bytes += program_bytes(&program);
82        self.live += 1;
83        let entry = Some((RegExpRecord { source, flags }, program));
84        let index = match self.free.pop() {
85            Some(index) => {
86                self.programs[index as usize] = entry;
87                index
88            }
89            None => {
90                self.programs.push(entry);
91                let index = (self.programs.len() - 1) as u32;
92                if index as usize / 64 == self.marks.len() {
93                    self.marks.push(0);
94                }
95                index
96            }
97        };
98        self.index.insert((source, flags), index);
99        Ok(index)
100    }
101
102    #[track_caller]
103    fn entry(&self, index: u32) -> &(RegExpRecord, CompiledRegExp) {
104        self.programs[index as usize]
105            .as_ref()
106            .expect("a live regular-expression program")
107    }
108
109    pub fn get(&self, index: u32) -> RegExpRecord {
110        self.entry(index).0
111    }
112
113    pub fn program(&self, index: u32) -> &CompiledRegExp {
114        &self.entry(index).1
115    }
116
117    /// Live programs.
118    pub fn len(&self) -> usize {
119        self.live
120    }
121
122    pub fn is_empty(&self) -> bool {
123        self.live == 0
124    }
125
126    /// Bytes the live programs hold.
127    pub fn bytes(&self) -> usize {
128        self.bytes
129    }
130
131    pub(crate) fn clear_marks(&mut self) {
132        self.marks.fill(0);
133    }
134
135    /// Marks program `index`; its record if it was not marked yet.
136    #[inline]
137    pub(crate) fn mark(&mut self, index: u32) -> Option<RegExpRecord> {
138        let (word, mask) = ((index / 64) as usize, 1u64 << (index % 64));
139        if self.marks[word] & mask != 0 {
140            return None;
141        }
142        self.marks[word] |= mask;
143        Some(self.get(index))
144    }
145
146    fn is_marked(&self, index: u32) -> bool {
147        self.marks[(index / 64) as usize] & (1u64 << (index % 64)) != 0
148    }
149
150    /// Frees every unmarked program.
151    pub(crate) fn sweep(&mut self) {
152        #[cfg(feature = "gc-stress")]
153        let held = {
154            let released = std::mem::take(&mut self.quarantine);
155            self.free.extend_from_slice(&released);
156            self.free.len()
157        };
158        for index in (0..self.programs.len() as u32).rev() {
159            if self.is_marked(index) {
160                continue;
161            }
162            let Some((record, program)) = self.programs[index as usize].take() else {
163                continue;
164            };
165            self.index.remove(&(record.source, record.flags));
166            self.bytes -= program_bytes(&program);
167            self.live -= 1;
168            self.free.push(index);
169        }
170        #[cfg(feature = "gc-stress")]
171        self.quarantine.extend(self.free.drain(held..));
172    }
173
174    /// Debug check after marking: exactly the live programs are marked.
175    pub(crate) fn verify(&self) {
176        for (index, program) in self.programs.iter().enumerate() {
177            assert_eq!(
178                program.is_some(),
179                self.is_marked(index as u32),
180                "gc verify: regular-expression program {index} is {}",
181                if program.is_some() {
182                    "live but unreachable"
183                } else {
184                    "reachable but freed"
185                }
186            );
187        }
188    }
189}
190
191/// `NewRegExp`: a new `RegExp` object over the program for the literal's
192/// `(source, flags)`, constants `constant` and `constant + 1` of the running
193/// function, with an own writable `lastIndex` of 0.
194#[inline(never)]
195pub(crate) fn new_regexp(
196    cx: &mut Cx<'_>,
197    bytecode: BytecodeId,
198    constant: u32,
199) -> Result<Value, Throw> {
200    let source = cx.heap.bytecode_constant(bytecode, constant);
201    let flags = cx.heap.bytecode_constant(bytecode, constant + 1);
202    let source = source.as_string().expect("a source atom");
203    let flags = flags.as_string().expect("a flags atom");
204    regexp_object(cx, source, flags)
205}
206
207/// A new `RegExp` object over `(source, flags)` (atoms), compiling them on
208/// first use: a `SyntaxError` for an invalid pattern or flags.
209pub(crate) fn regexp_object(
210    cx: &mut Cx<'_>,
211    source: StringId,
212    flags: StringId,
213) -> Result<Value, Throw> {
214    let prototype = cx.realm.intrinsic(Intrinsic::RegExpPrototype);
215    regexp_object_with(cx, source, flags, prototype)
216}
217
218/// Gives `object` the program for `(source, flags)`: a `SyntaxError` when
219/// invalid. The program is compiled without allocating, so the object names
220/// it before any collection.
221pub(crate) fn set_program(
222    cx: &mut Cx<'_>,
223    object: crate::value::ObjectId,
224    source: StringId,
225    flags: StringId,
226) -> Result<(), Throw> {
227    let heap = &mut *cx.heap;
228    match heap.regexps.intern(&heap.strings, source, flags) {
229        Ok(program) => {
230            heap.set_payload(object, program);
231            Ok(())
232        }
233        Err(message) => Err(error::throw(cx, ErrorKind::Syntax, &message)),
234    }
235}
236
237/// [`regexp_object`] with `prototype` (a subclass's, from `new.target`).
238pub(crate) fn regexp_object_with(
239    cx: &mut Cx<'_>,
240    source: StringId,
241    flags: StringId,
242    prototype: crate::value::ObjectId,
243) -> Result<Value, Throw> {
244    let names = cx.realm.names;
245    let heap = &mut *cx.heap;
246    let mark = heap.roots().mark();
247    heap.roots().push(Value::string(source));
248    heap.roots().push(Value::string(flags));
249    let object = heap.alloc_object(ObjectKind::RegExp, Some(prototype), 1);
250    heap.roots().truncate(mark);
251    let object = object.map_err(|error| error::heap_error(cx, error))?;
252    set_program(cx, object, source, flags)?;
253    let heap = &mut *cx.heap;
254    heap.add_property(
255        object,
256        Names::key(names.last_index),
257        PropertyFlags::data(true, false, false),
258        Value::int32(0),
259    )
260    .map_err(|error| error::heap_error(cx, error))?;
261    if prototype == cx.realm.intrinsic(Intrinsic::RegExpPrototype)
262        && cx.realm.regexp_instance_shape.get().is_none()
263    {
264        let (slot, _) = cx
265            .heap
266            .lookup_own(object, Names::key(names.last_index))
267            .expect("lastIndex");
268        cx.realm
269            .regexp_instance_shape
270            .set(Some((cx.heap.shape_of(object), slot)));
271    }
272    Ok(Value::object(object))
273}
274
275#[cfg(test)]
276mod tests {
277    #[test]
278    fn unmarked_programs_are_freed_and_their_keys_forgotten() {
279        let mut heap = crate::Heap::default();
280        let source = heap.intern("a+b").unwrap();
281        let other = heap.intern("c").unwrap();
282        let flags = heap.intern("g").unwrap();
283        let store = &mut heap.regexps;
284        let kept = store.intern(&heap.strings, source, flags).unwrap();
285        store.intern(&heap.strings, other, flags).unwrap();
286        assert_eq!(store.intern(&heap.strings, source, flags), Ok(kept));
287        assert_eq!(store.len(), 2);
288        let bytes = store.bytes();
289        store.clear_marks();
290        assert!(store.mark(kept).is_some());
291        assert!(store.mark(kept).is_none(), "marked once");
292        store.sweep();
293        assert_eq!(store.len(), 1);
294        assert!(store.bytes() < bytes);
295        assert_eq!(store.get(kept).source, source);
296        // The dropped pair compiles again on its next use.
297        let again = store.intern(&heap.strings, other, flags).unwrap();
298        assert_eq!(store.get(again).source, other);
299        assert_ne!(again, kept);
300        assert!(
301            store.intern(&heap.strings, flags, source).is_err(),
302            "invalid flags"
303        );
304    }
305}
oxide_core/vm/regexp.rs

oxide_core/vm/
regexp.rs
