| import-irregexp.py |
|
5789 |
- |
| imported |
|
|
93 % |
| LICENSE.v8 |
|
1527 |
- |
| moz.build |
|
2220 |
- |
| moz.yaml |
|
1134 |
- |
| patches |
|
|
- |
| properties_glue |
|
|
100 % |
| RegExpAPI.cpp |
|
36888 |
- |
| RegExpAPI.h |
This is the interface that the regexp engine exposes to SpiderMonkey. |
3410 |
- |
| RegExpNativeMacroAssembler.cpp |
|
65006 |
92 % |
| RegExpNativeMacroAssembler.h |
[SMDOC] RegExp backtrack stack
Irregexp is a backtracking engine. To keep track of possible backtrack
points, it maintains a backtrack stack, where the engine keeps information
about other possible matches to consider if the current match fails. For
example, the engine may push a code location (represented as an offset from
the code base address) that can be jumped to if the current attempted match
fails. The engine may also push a position in the input string: see
PushCurrentPosition and CheckFixedLengthLoop. The backtrack stack grows
downward in memory, like the hardware stack.
This stack can be quite deep, so instead of using the native stack, we
allocate space on the heap. This is managed by regexp::Stack (implemented in
imported/regexp_stack.cc). To avoid allocation overhead for simple regexps,
regexp::Stack owns a 1KB static buffer that is not freed between executions.
If the current buffer fills up, the regexp will call GrowBacktrackStack to
grow it.
The backtrack stack is allocated per-context. If a regexp is interrupted,
and the interrupt handler executes another regexp, we have to ensure that
the backtrack stack is reentrant-safe. To accomplish this, regexp::Stack
has a `stack_pointer` field that represents the base of the stack for the
purposes of the next regexp to execute. This will normally be the base of
the backtrack stack itself, but if a regexp is interrupted, it will store
the top of its current backtrack stack, ensuring that it won't be clobbered
by reentrant regexp execution in the interrupt handler.
We track three backtrack-stack-related values in regexp jitcode:
1. backtrack_stack_pointer_: the top of the backtrack stack, pinned to a
register. This corresponds to regexp::Stack::stack_pointer().
2. FrameData::backtrackStackBase: a pointer to the base of the backing buffer
for the stack. This corresponds to regexp::Stack::memory_top(). It is
used in WriteStackPointerToRegister / ReadStackPointerFromRegister, which
store a position in the backtrack stack to a Register (irregexp's
confusing name for a local stack slot). By storing the position as an
offset from the base instead of a raw pointer, we avoid corruption when
the stack is reallocated.
3. FrameData::initialBacktrackStackPointer: the top of the backtrack stack
before we were invoked, stored as a byte offset from backtrackStackBase.
This is initialized during the prologue. In the epilogue, we use it to
restore the correct value. By storing it as an offset instead of a raw
pointer, we ensure that if the backtrack stack has been reallocated,
we will store a pointer into the current buffer, not the old one.
Whenever we call into C++ that can reallocate the backtrack stack (that is,
GrowBacktrackStack or HandleRegExpInterrupt), we update the stack pointer
in the regexp::Stack with the current value of backtrack_stack_pointer_.
When we return, we reload backtrack_stack_pointer_ and backtrackStackBase,
and store the stack base into our local FrameData.
|
17907 |
90 % |
| RegExpShim.cpp |
|
11386 |
- |
| RegExpShim.h |
unsupported |
55632 |
85 % |
| RegExpTypes.h |
|
3083 |
100 % |
| util |
|
|
81 % |