1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2  * vim: set ts=8 sts=4 et sw=4 tw=99: */
3 
4 // Copyright 2012 the V8 project authors. All rights reserved.
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 //     * Redistributions of source code must retain the above copyright
10 //       notice, this list of conditions and the following disclaimer.
11 //     * Redistributions in binary form must reproduce the above
12 //       copyright notice, this list of conditions and the following
13 //       disclaimer in the documentation and/or other materials provided
14 //       with the distribution.
15 //     * Neither the name of Google Inc. nor the names of its
16 //       contributors may be used to endorse or promote products derived
17 //       from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 
31 #ifndef V8_NATIVE_REGEXP_MACRO_ASSEMBLER_H_
32 #define V8_NATIVE_REGEXP_MACRO_ASSEMBLER_H_
33 
34 #include "irregexp/RegExpMacroAssembler.h"
35 
36 namespace js {
37 namespace irregexp {
38 
39 struct InputOutputData
40 {
41     const void* inputStart;
42     const void* inputEnd;
43 
44     // Index into inputStart (in chars) at which to begin matching.
45     size_t startIndex;
46 
47     MatchPairs* matches;
48 
49     // RegExpMacroAssembler::Result for non-global regexps, number of captures
50     // for global regexps.
51     int32_t result;
52 
53     template <typename CharT>
InputOutputDataInputOutputData54     InputOutputData(const CharT* inputStart, const CharT* inputEnd,
55                     size_t startIndex, MatchPairs* matches)
56       : inputStart(inputStart),
57         inputEnd(inputEnd),
58         startIndex(startIndex),
59         matches(matches),
60         result(0)
61     {}
62 };
63 
64 struct FrameData
65 {
66     // Copy of the input/output data's data.
67     char16_t* inputStart;
68     size_t startIndex;
69 
70     // Pointer to the character before the input start.
71     char16_t* inputStartMinusOne;
72 
73     // Copy of the input MatchPairs registers, may be modified by JIT code.
74     int32_t* outputRegisters;
75     int32_t numOutputRegisters;
76 
77     int32_t successfulCaptures;
78 
79     void* backtrackStackBase;
80 };
81 
82 class MOZ_STACK_CLASS NativeRegExpMacroAssembler : public RegExpMacroAssembler
83 {
84   public:
85     // Type of input string to generate code for.
86     enum Mode { ASCII = 1, CHAR16 = 2 };
87 
88     NativeRegExpMacroAssembler(LifoAlloc* alloc, RegExpShared* shared,
89                                JSRuntime* rt, Mode mode, int registers_to_save);
90 
91     // Inherited virtual methods.
92     RegExpCode GenerateCode(JSContext* cx, bool match_only);
93     int stack_limit_slack();
94     bool CanReadUnaligned();
95     void AdvanceCurrentPosition(int by);
96     void AdvanceRegister(int reg, int by);
97     void Backtrack();
98     void Bind(jit::Label* label);
99     void CheckAtStart(jit::Label* on_at_start);
100     void CheckCharacter(unsigned c, jit::Label* on_equal);
101     void CheckCharacterAfterAnd(unsigned c, unsigned and_with, jit::Label* on_equal);
102     void CheckCharacterGT(char16_t limit, jit::Label* on_greater);
103     void CheckCharacterLT(char16_t limit, jit::Label* on_less);
104     void CheckGreedyLoop(jit::Label* on_tos_equals_current_position);
105     void CheckNotAtStart(jit::Label* on_not_at_start);
106     void CheckNotBackReference(int start_reg, jit::Label* on_no_match);
107     void CheckNotBackReferenceIgnoreCase(int start_reg, jit::Label* on_no_match);
108     void CheckNotCharacter(unsigned c, jit::Label* on_not_equal);
109     void CheckNotCharacterAfterAnd(unsigned c, unsigned and_with, jit::Label* on_not_equal);
110     void CheckNotCharacterAfterMinusAnd(char16_t c, char16_t minus, char16_t and_with,
111                                         jit::Label* on_not_equal);
112     void CheckCharacterInRange(char16_t from, char16_t to,
113                                jit::Label* on_in_range);
114     void CheckCharacterNotInRange(char16_t from, char16_t to,
115                                   jit::Label* on_not_in_range);
116     void CheckBitInTable(uint8_t* table, jit::Label* on_bit_set);
117     void CheckPosition(int cp_offset, jit::Label* on_outside_input);
118     void JumpOrBacktrack(jit::Label* to);
119     bool CheckSpecialCharacterClass(char16_t type, jit::Label* on_no_match);
120     void Fail();
121     void IfRegisterGE(int reg, int comparand, jit::Label* if_ge);
122     void IfRegisterLT(int reg, int comparand, jit::Label* if_lt);
123     void IfRegisterEqPos(int reg, jit::Label* if_eq);
124     void LoadCurrentCharacter(int cp_offset, jit::Label* on_end_of_input,
125                               bool check_bounds = true, int characters = 1);
126     void PopCurrentPosition();
127     void PopRegister(int register_index);
128     void PushCurrentPosition();
129     void PushRegister(int register_index, StackCheckFlag check_stack_limit);
130     void ReadCurrentPositionFromRegister(int reg);
131     void ReadBacktrackStackPointerFromRegister(int reg);
132     void SetCurrentPositionFromEnd(int by);
133     void SetRegister(int register_index, int to);
134     bool Succeed();
135     void WriteCurrentPositionToRegister(int reg, int cp_offset);
136     void ClearRegisters(int reg_from, int reg_to);
137     void WriteBacktrackStackPointerToRegister(int reg);
138     void PushBacktrack(jit::Label* label);
139     void BindBacktrack(jit::Label* label);
140 
141     // Compares two-byte strings case insensitively.
142     // Called from generated RegExp code.
143     static int CaseInsensitiveCompareUC16(jit::Address byte_offset1,
144                                           jit::Address byte_offset2,
145                                           size_t byte_length);
146 
147     // Byte map of one byte characters with a 0xff if the character is a word
148     // character (digit, letter or underscore) and 0x00 otherwise.
149     // Used by generated RegExp code.
150     static const uint8_t word_character_map[256];
151 
152     // Byte size of chars in the string to match (decided by the Mode argument)
char_size()153     inline int char_size() { return static_cast<int>(mode_); }
factor()154     inline jit::Scale factor() { return mode_ == CHAR16 ? jit::TimesTwo : jit::TimesOne; }
155 
156     jit::Label* BranchOrBacktrack(jit::Label* branch);
157 
158     // Pushes a register or constant on the backtrack stack. Decrements the
159     // stack pointer by a word size and stores the register's value there.
160     void PushBacktrack(jit::Register value);
161     void PushBacktrack(int32_t value);
162 
163     // Pop a value from the backtrack stack.
164     void PopBacktrack(jit::Register target);
165 
166     // Check whether we are exceeding the stack limit on the backtrack stack.
167     void CheckBacktrackStackLimit();
168 
169     void LoadCurrentCharacterUnchecked(int cp_offset, int characters);
170 
171   private:
172     jit::MacroAssembler masm;
173 
174     JSRuntime* runtime;
175     Mode mode_;
176     jit::Label entry_label_;
177     jit::Label start_label_;
178     jit::Label backtrack_label_;
179     jit::Label success_label_;
180     jit::Label exit_label_;
181     jit::Label stack_overflow_label_;
182     jit::Label exit_with_exception_label_;
183 
184     // Set of registers which are used by the code generator, and as such which
185     // are saved.
186     jit::LiveGeneralRegisterSet savedNonVolatileRegisters;
187 
188     struct LabelPatch {
189         // Once it is bound via BindBacktrack, |label| becomes null and
190         // |labelOffset| is set.
191         jit::Label* label;
192         size_t labelOffset;
193 
194         jit::CodeOffset patchOffset;
195 
LabelPatchLabelPatch196         LabelPatch(jit::Label* label, jit::CodeOffset patchOffset)
197           : label(label), labelOffset(0), patchOffset(patchOffset)
198         {}
199     };
200 
201     Vector<LabelPatch, 4, SystemAllocPolicy> labelPatches;
202 
203     // See RegExpMacroAssembler.cpp for the meaning of these registers.
204     jit::Register input_end_pointer;
205     jit::Register current_character;
206     jit::Register current_position;
207     jit::Register backtrack_stack_pointer;
208     jit::Register temp0, temp1, temp2;
209 
210     // The frame_pointer-relative location of a regexp register.
register_location(int register_index)211     jit::Address register_location(int register_index) {
212         checkRegister(register_index);
213         return jit::Address(masm.getStackPointer(), register_offset(register_index));
214     }
215 
register_offset(int register_index)216     int32_t register_offset(int register_index) {
217         return sizeof(FrameData) + register_index * sizeof(void*);
218     }
219 };
220 
221 } }  // namespace js::irregexp
222 
223 #endif  // V8_NATIVE_REGEXP_MACRO_ASSEMBLER_H_
224