2011-05-25 Ryosuke Niwa <rniwa@webkit.org>
[WebKit-https.git] / Source / JavaScriptCore / runtime / RegExp.cpp
1 /*
2  *  Copyright (C) 1999-2001, 2004 Harri Porten (porten@kde.org)
3  *  Copyright (c) 2007, 2008 Apple Inc. All rights reserved.
4  *  Copyright (C) 2009 Torch Mobile, Inc.
5  *  Copyright (C) 2010 Peter Varga (pvarga@inf.u-szeged.hu), University of Szeged
6  *
7  *  This library is free software; you can redistribute it and/or
8  *  modify it under the terms of the GNU Lesser General Public
9  *  License as published by the Free Software Foundation; either
10  *  version 2 of the License, or (at your option) any later version.
11  *
12  *  This library is distributed in the hope that it will be useful,
13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  *  Lesser General Public License for more details.
16  *
17  *  You should have received a copy of the GNU Lesser General Public
18  *  License along with this library; if not, write to the Free Software
19  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
20  *
21  */
22
23 #include "config.h"
24 #include "RegExp.h"
25
26 #include "Lexer.h"
27 #include "yarr/Yarr.h"
28 #include "yarr/YarrJIT.h"
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <wtf/Assertions.h>
33 #include <wtf/OwnArrayPtr.h>
34
35 namespace JSC {
36
37 const ClassInfo RegExp::s_info = { "RegExp", 0, 0, 0 };
38
39 RegExpFlags regExpFlags(const UString& string)
40 {
41     RegExpFlags flags = NoFlags;
42
43     for (unsigned i = 0; i < string.length(); ++i) {
44         switch (string.characters()[i]) {
45         case 'g':
46             if (flags & FlagGlobal)
47                 return InvalidFlags;
48             flags = static_cast<RegExpFlags>(flags | FlagGlobal);
49             break;
50
51         case 'i':
52             if (flags & FlagIgnoreCase)
53                 return InvalidFlags;
54             flags = static_cast<RegExpFlags>(flags | FlagIgnoreCase);
55             break;
56
57         case 'm':
58             if (flags & FlagMultiline)
59                 return InvalidFlags;
60             flags = static_cast<RegExpFlags>(flags | FlagMultiline);
61             break;
62
63         default:
64             return InvalidFlags;
65         }
66     }
67
68     return flags;
69 }
70   
71 struct RegExpRepresentation {
72 #if ENABLE(YARR_JIT)
73     Yarr::YarrCodeBlock m_regExpJITCode;
74 #endif
75     OwnPtr<Yarr::BytecodePattern> m_regExpBytecode;
76 };
77
78 inline RegExp::RegExp(JSGlobalData* globalData, const UString& patternString, RegExpFlags flags)
79     : JSCell(*globalData, globalData->regExpStructure.get())
80     , m_state(NotCompiled)
81     , m_patternString(patternString)
82     , m_flags(flags)
83     , m_constructionError(0)
84     , m_numSubpatterns(0)
85 #if ENABLE(REGEXP_TRACING)
86     , m_rtMatchCallCount(0)
87     , m_rtMatchFoundCount(0)
88 #endif
89 {
90     Yarr::YarrPattern pattern(m_patternString, ignoreCase(), multiline(), &m_constructionError);
91     if (m_constructionError)
92         m_state = ParseError;
93     else
94         m_numSubpatterns = pattern.m_numSubpatterns;
95 }
96
97 RegExp::~RegExp()
98 {
99 }
100
101 RegExp* RegExp::create(JSGlobalData* globalData, const UString& patternString, RegExpFlags flags)
102 {
103     RegExp* res = new (globalData) RegExp(globalData, patternString, flags);
104 #if ENABLE(REGEXP_TRACING)
105     globalData->addRegExpToTrace(res);
106 #endif
107     return res;
108 }
109
110 void RegExp::compile(JSGlobalData* globalData)
111 {
112     ASSERT(m_state == NotCompiled);
113     m_representation = adoptPtr(new RegExpRepresentation);
114     Yarr::YarrPattern pattern(m_patternString, ignoreCase(), multiline(), &m_constructionError);
115     if (m_constructionError) {
116         ASSERT_NOT_REACHED();
117         m_state = ParseError;
118         return;
119     }
120
121     ASSERT(m_numSubpatterns == pattern.m_numSubpatterns);
122
123     m_state = ByteCode;
124
125 #if ENABLE(YARR_JIT)
126     if (!pattern.m_containsBackreferences && globalData->canUseJIT()) {
127         Yarr::jitCompile(pattern, globalData, m_representation->m_regExpJITCode);
128 #if ENABLE(YARR_JIT_DEBUG)
129         if (!m_representation->m_regExpJITCode.isFallBack())
130             m_state = JITCode;
131         else
132             m_state = ByteCode;
133 #else
134         if (!m_representation->m_regExpJITCode.isFallBack()) {
135             m_state = JITCode;
136             return;
137         }
138 #endif
139     }
140 #endif
141
142     m_representation->m_regExpBytecode = Yarr::byteCompile(pattern, &globalData->m_regExpAllocator);
143 }
144
145 int RegExp::match(JSGlobalData& globalData, const UString& s, int startOffset, Vector<int, 32>* ovector)
146 {
147     if (startOffset < 0)
148         startOffset = 0;
149
150 #if ENABLE(REGEXP_TRACING)
151     m_rtMatchCallCount++;
152 #endif
153
154     if (static_cast<unsigned>(startOffset) > s.length() || s.isNull())
155         return -1;
156
157     if (m_state != ParseError) {
158         compileIfNecessary(globalData);
159         int offsetVectorSize = (m_numSubpatterns + 1) * 2;
160         int* offsetVector;
161         Vector<int, 32> nonReturnedOvector;
162         if (ovector) {
163             ovector->resize(offsetVectorSize);
164             offsetVector = ovector->data();
165         } else {
166             nonReturnedOvector.resize(offsetVectorSize);
167             offsetVector = nonReturnedOvector.data();
168         }
169
170         ASSERT(offsetVector);
171         // Initialize offsetVector with the return value (index 0) and the 
172         // first subpattern start indicies (even index values) set to -1.
173         // No need to init the subpattern end indicies.
174         for (unsigned j = 0, i = 0; i < m_numSubpatterns + 1; j += 2, i++)            
175             offsetVector[j] = -1;
176
177         int result;
178 #if ENABLE(YARR_JIT)
179         if (m_state == JITCode) {
180             result = Yarr::execute(m_representation->m_regExpJITCode, s.characters(), startOffset, s.length(), offsetVector);
181 #if ENABLE(YARR_JIT_DEBUG)
182             matchCompareWithInterpreter(s, startOffset, offsetVector, result);
183 #endif
184         } else
185 #endif
186             result = Yarr::interpret(m_representation->m_regExpBytecode.get(), s.characters(), startOffset, s.length(), offsetVector);
187         ASSERT(result >= -1);
188
189 #if ENABLE(REGEXP_TRACING)
190         if (result != -1)
191             m_rtMatchFoundCount++;
192 #endif
193
194         return result;
195     }
196
197     return -1;
198 }
199
200 void RegExp::invalidateCode()
201 {
202     m_representation.clear();
203 }
204
205 #if ENABLE(YARR_JIT_DEBUG)
206 void RegExp::matchCompareWithInterpreter(const UString& s, int startOffset, int* offsetVector, int jitResult)
207 {
208     int offsetVectorSize = (m_numSubpatterns + 1) * 2;
209     Vector<int, 32> interpreterOvector;
210     interpreterOvector.resize(offsetVectorSize);
211     int* interpreterOffsetVector = interpreterOvector.data();
212     int interpreterResult = 0;
213     int differences = 0;
214
215     // Initialize interpreterOffsetVector with the return value (index 0) and the 
216     // first subpattern start indicies (even index values) set to -1.
217     // No need to init the subpattern end indicies.
218     for (unsigned j = 0, i = 0; i < m_numSubpatterns + 1; j += 2, i++)
219         interpreterOffsetVector[j] = -1;
220
221     interpreterResult = Yarr::interpret(m_representation->m_regExpBytecode.get(), s.characters(), startOffset, s.length(), interpreterOffsetVector);
222
223     if (jitResult != interpreterResult)
224         differences++;
225
226     for (unsigned j = 2, i = 0; i < m_numSubpatterns; j +=2, i++)
227         if ((offsetVector[j] != interpreterOffsetVector[j])
228             || ((offsetVector[j] >= 0) && (offsetVector[j+1] != interpreterOffsetVector[j+1])))
229             differences++;
230
231     if (differences) {
232         fprintf(stderr, "RegExp Discrepency for /%s/\n    string input ", pattern().utf8().data());
233         unsigned segmentLen = s.length() - static_cast<unsigned>(startOffset);
234
235         fprintf(stderr, (segmentLen < 150) ? "\"%s\"\n" : "\"%148s...\"\n", s.utf8().data() + startOffset);
236
237         if (jitResult != interpreterResult) {
238             fprintf(stderr, "    JIT result = %d, blah interpreted result = %d\n", jitResult, interpreterResult);
239             differences--;
240         } else {
241             fprintf(stderr, "    Correct result = %d\n", jitResult);
242         }
243
244         if (differences) {
245             for (unsigned j = 2, i = 0; i < m_numSubpatterns; j +=2, i++) {
246                 if (offsetVector[j] != interpreterOffsetVector[j])
247                     fprintf(stderr, "    JIT offset[%d] = %d, interpreted offset[%d] = %d\n", j, offsetVector[j], j, interpreterOffsetVector[j]);
248                 if ((offsetVector[j] >= 0) && (offsetVector[j+1] != interpreterOffsetVector[j+1]))
249                     fprintf(stderr, "    JIT offset[%d] = %d, interpreted offset[%d] = %d\n", j+1, offsetVector[j+1], j+1, interpreterOffsetVector[j+1]);
250             }
251         }
252     }
253 }
254 #endif
255
256 #if ENABLE(REGEXP_TRACING)
257     void RegExp::printTraceData()
258     {
259         char formattedPattern[41];
260         char rawPattern[41];
261
262         strncpy(rawPattern, pattern().utf8().data(), 40);
263         rawPattern[40]= '\0';
264
265         int pattLen = strlen(rawPattern);
266
267         snprintf(formattedPattern, 41, (pattLen <= 38) ? "/%.38s/" : "/%.36s...", rawPattern);
268
269 #if ENABLE(YARR_JIT)
270         Yarr::YarrCodeBlock& codeBlock = m_representation->m_regExpJITCode;
271
272         const size_t jitAddrSize = 20;
273         char jitAddr[jitAddrSize];
274         if (m_state == JITCode)
275             snprintf(jitAddr, jitAddrSize, "fallback");
276         else
277             snprintf(jitAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.getAddr()));
278 #else
279         const char* jitAddr = "JIT Off";
280 #endif
281
282         printf("%-40.40s %16.16s %10d %10d\n", formattedPattern, jitAddr, m_rtMatchCallCount, m_rtMatchFoundCount);
283     }
284 #endif
285
286 } // namespace JSC