c31cf52a572c90141fca4e083feb9b1a0fa02b57
[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, 2016 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 "JSCInlines.h"
28 #include "RegExpCache.h"
29 #include "RegExpInlines.h"
30 #include "Yarr.h"
31 #include "YarrJIT.h"
32 #include <wtf/Assertions.h>
33
34 namespace JSC {
35
36 const ClassInfo RegExp::s_info = { "RegExp", 0, 0, CREATE_METHOD_TABLE(RegExp) };
37
38 RegExpFlags regExpFlags(const String& string)
39 {
40     RegExpFlags flags = NoFlags;
41
42     for (unsigned i = 0; i < string.length(); ++i) {
43         switch (string[i]) {
44         case 'g':
45             if (flags & FlagGlobal)
46                 return InvalidFlags;
47             flags = static_cast<RegExpFlags>(flags | FlagGlobal);
48             break;
49
50         case 'i':
51             if (flags & FlagIgnoreCase)
52                 return InvalidFlags;
53             flags = static_cast<RegExpFlags>(flags | FlagIgnoreCase);
54             break;
55
56         case 'm':
57             if (flags & FlagMultiline)
58                 return InvalidFlags;
59             flags = static_cast<RegExpFlags>(flags | FlagMultiline);
60             break;
61
62         case 'u':
63             if (flags & FlagUnicode)
64                 return InvalidFlags;
65             flags = static_cast<RegExpFlags>(flags | FlagUnicode);
66             break;
67                 
68         case 'y':
69             if (flags & FlagSticky)
70                 return InvalidFlags;
71             flags = static_cast<RegExpFlags>(flags | FlagSticky);
72             break;
73
74         default:
75             return InvalidFlags;
76         }
77     }
78
79     return flags;
80 }
81
82 #if REGEXP_FUNC_TEST_DATA_GEN
83 const char* const RegExpFunctionalTestCollector::s_fileName = "/tmp/RegExpTestsData";
84 RegExpFunctionalTestCollector* RegExpFunctionalTestCollector::s_instance = 0;
85
86 RegExpFunctionalTestCollector* RegExpFunctionalTestCollector::get()
87 {
88     if (!s_instance)
89         s_instance = new RegExpFunctionalTestCollector();
90
91     return s_instance;
92 }
93
94 void RegExpFunctionalTestCollector::outputOneTest(RegExp* regExp, const String& s, int startOffset, int* ovector, int result)
95 {
96     if ((!m_lastRegExp) || (m_lastRegExp != regExp)) {
97         m_lastRegExp = regExp;
98         fputc('/', m_file);
99         outputEscapedString(regExp->pattern(), true);
100         fputc('/', m_file);
101         if (regExp->global())
102             fputc('g', m_file);
103         if (regExp->ignoreCase())
104             fputc('i', m_file);
105         if (regExp->multiline())
106             fputc('m', m_file);
107         if (regExp->sticky())
108             fputc('y', m_file);
109         if (regExp->unicode())
110             fputc('u', m_file);
111         fprintf(m_file, "\n");
112     }
113
114     fprintf(m_file, " \"");
115     outputEscapedString(s);
116     fprintf(m_file, "\", %d, %d, (", startOffset, result);
117     for (unsigned i = 0; i <= regExp->numSubpatterns(); i++) {
118         int subpatternBegin = ovector[i * 2];
119         int subpatternEnd = ovector[i * 2 + 1];
120         if (subpatternBegin == -1)
121             subpatternEnd = -1;
122         fprintf(m_file, "%d, %d", subpatternBegin, subpatternEnd);
123         if (i < regExp->numSubpatterns())
124             fputs(", ", m_file);
125     }
126
127     fprintf(m_file, ")\n");
128     fflush(m_file);
129 }
130
131 RegExpFunctionalTestCollector::RegExpFunctionalTestCollector()
132 {
133     m_file = fopen(s_fileName, "r+");
134     if  (!m_file)
135         m_file = fopen(s_fileName, "w+");
136
137     fseek(m_file, 0L, SEEK_END);
138 }
139
140 RegExpFunctionalTestCollector::~RegExpFunctionalTestCollector()
141 {
142     fclose(m_file);
143     s_instance = 0;
144 }
145
146 void RegExpFunctionalTestCollector::outputEscapedString(const String& s, bool escapeSlash)
147 {
148     int len = s.length();
149     
150     for (int i = 0; i < len; ++i) {
151         UChar c = s[i];
152
153         switch (c) {
154         case '\0':
155             fputs("\\0", m_file);
156             break;
157         case '\a':
158             fputs("\\a", m_file);
159             break;
160         case '\b':
161             fputs("\\b", m_file);
162             break;
163         case '\f':
164             fputs("\\f", m_file);
165             break;
166         case '\n':
167             fputs("\\n", m_file);
168             break;
169         case '\r':
170             fputs("\\r", m_file);
171             break;
172         case '\t':
173             fputs("\\t", m_file);
174             break;
175         case '\v':
176             fputs("\\v", m_file);
177             break;
178         case '/':
179             if (escapeSlash)
180                 fputs("\\/", m_file);
181             else
182                 fputs("/", m_file);
183             break;
184         case '\"':
185             fputs("\\\"", m_file);
186             break;
187         case '\\':
188             fputs("\\\\", m_file);
189             break;
190         case '\?':
191             fputs("\?", m_file);
192             break;
193         default:
194             if (c > 0x7f)
195                 fprintf(m_file, "\\u%04x", c);
196             else 
197                 fputc(c, m_file);
198             break;
199         }
200     }
201 }
202 #endif
203
204 RegExp::RegExp(VM& vm, const String& patternString, RegExpFlags flags)
205     : JSCell(vm, vm.regExpStructure.get())
206     , m_state(NotCompiled)
207     , m_patternString(patternString)
208     , m_flags(flags)
209     , m_constructionError(0)
210     , m_numSubpatterns(0)
211 #if ENABLE(REGEXP_TRACING)
212     , m_rtMatchOnlyTotalSubjectStringLen(0.0)
213     , m_rtMatchTotalSubjectStringLen(0.0)
214     , m_rtMatchOnlyCallCount(0)
215     , m_rtMatchOnlyFoundCount(0)
216     , m_rtMatchCallCount(0)
217     , m_rtMatchFoundCount(0)
218 #endif
219 {
220 }
221
222 void RegExp::finishCreation(VM& vm)
223 {
224     Base::finishCreation(vm);
225     Yarr::YarrPattern pattern(m_patternString, m_flags, &m_constructionError);
226     if (m_constructionError)
227         m_state = ParseError;
228     else
229         m_numSubpatterns = pattern.m_numSubpatterns;
230 }
231
232 void RegExp::destroy(JSCell* cell)
233 {
234     RegExp* thisObject = static_cast<RegExp*>(cell);
235 #if REGEXP_FUNC_TEST_DATA_GEN
236     RegExpFunctionalTestCollector::get()->clearRegExp(this);
237 #endif
238     thisObject->RegExp::~RegExp();
239 }
240
241 size_t RegExp::estimatedSize(JSCell* cell)
242 {
243     RegExp* thisObject = static_cast<RegExp*>(cell);
244     size_t regexDataSize = thisObject->m_regExpBytecode ? thisObject->m_regExpBytecode->estimatedSizeInBytes() : 0;
245 #if ENABLE(YARR_JIT)
246     regexDataSize += thisObject->m_regExpJITCode.size();
247 #endif
248     return Base::estimatedSize(cell) + regexDataSize;
249 }
250
251 RegExp* RegExp::createWithoutCaching(VM& vm, const String& patternString, RegExpFlags flags)
252 {
253     RegExp* regExp = new (NotNull, allocateCell<RegExp>(vm.heap)) RegExp(vm, patternString, flags);
254     regExp->finishCreation(vm);
255     return regExp;
256 }
257
258 RegExp* RegExp::create(VM& vm, const String& patternString, RegExpFlags flags)
259 {
260     return vm.regExpCache()->lookupOrCreate(patternString, flags);
261 }
262
263 void RegExp::compile(VM* vm, Yarr::YarrCharSize charSize)
264 {
265     Yarr::YarrPattern pattern(m_patternString, m_flags, &m_constructionError);
266     if (m_constructionError) {
267         RELEASE_ASSERT_NOT_REACHED();
268 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
269         m_state = ParseError;
270         return;
271 #endif
272     }
273     ASSERT(m_numSubpatterns == pattern.m_numSubpatterns);
274
275     if (!hasCode()) {
276         ASSERT(m_state == NotCompiled);
277         vm->regExpCache()->addToStrongCache(this);
278         m_state = ByteCode;
279     }
280
281 #if ENABLE(YARR_JIT)
282     if (!pattern.m_containsBackreferences && !pattern.containsUnsignedLengthPattern() && !unicode() && vm->canUseRegExpJIT()) {
283         Yarr::jitCompile(pattern, charSize, vm, m_regExpJITCode);
284         if (!m_regExpJITCode.isFallBack()) {
285             m_state = JITCode;
286             return;
287         }
288     }
289 #else
290     UNUSED_PARAM(charSize);
291 #endif
292
293     m_state = ByteCode;
294     m_regExpBytecode = Yarr::byteCompile(pattern, &vm->m_regExpAllocator);
295 }
296
297 int RegExp::match(VM& vm, const String& s, unsigned startOffset, Vector<int, 32>& ovector)
298 {
299     return matchInline(vm, s, startOffset, ovector);
300 }
301
302 void RegExp::compileMatchOnly(VM* vm, Yarr::YarrCharSize charSize)
303 {
304     Yarr::YarrPattern pattern(m_patternString, m_flags, &m_constructionError);
305     if (m_constructionError) {
306         RELEASE_ASSERT_NOT_REACHED();
307 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
308         m_state = ParseError;
309         return;
310 #endif
311     }
312     ASSERT(m_numSubpatterns == pattern.m_numSubpatterns);
313
314     if (!hasCode()) {
315         ASSERT(m_state == NotCompiled);
316         vm->regExpCache()->addToStrongCache(this);
317         m_state = ByteCode;
318     }
319
320 #if ENABLE(YARR_JIT)
321     if (!pattern.m_containsBackreferences && !pattern.containsUnsignedLengthPattern() && !unicode() && vm->canUseRegExpJIT()) {
322         Yarr::jitCompile(pattern, charSize, vm, m_regExpJITCode, Yarr::MatchOnly);
323         if (!m_regExpJITCode.isFallBack()) {
324             m_state = JITCode;
325             return;
326         }
327     }
328 #else
329     UNUSED_PARAM(charSize);
330 #endif
331
332     m_state = ByteCode;
333     m_regExpBytecode = Yarr::byteCompile(pattern, &vm->m_regExpAllocator);
334 }
335
336 MatchResult RegExp::match(VM& vm, const String& s, unsigned startOffset)
337 {
338     return matchInline(vm, s, startOffset);
339 }
340
341 void RegExp::deleteCode()
342 {
343     if (!hasCode())
344         return;
345     m_state = NotCompiled;
346 #if ENABLE(YARR_JIT)
347     m_regExpJITCode.clear();
348 #endif
349     m_regExpBytecode = nullptr;
350 }
351
352 #if ENABLE(YARR_JIT_DEBUG)
353 void RegExp::matchCompareWithInterpreter(const String& s, int startOffset, int* offsetVector, int jitResult)
354 {
355     int offsetVectorSize = (m_numSubpatterns + 1) * 2;
356     Vector<int, 32> interpreterOvector;
357     interpreterOvector.resize(offsetVectorSize);
358     int* interpreterOffsetVector = interpreterOvector.data();
359     int interpreterResult = 0;
360     int differences = 0;
361
362     // Initialize interpreterOffsetVector with the return value (index 0) and the 
363     // first subpattern start indicies (even index values) set to -1.
364     // No need to init the subpattern end indicies.
365     for (unsigned j = 0, i = 0; i < m_numSubpatterns + 1; j += 2, i++)
366         interpreterOffsetVector[j] = -1;
367
368     interpreterResult = Yarr::interpret(m_regExpBytecode.get(), s, startOffset, interpreterOffsetVector);
369
370     if (jitResult != interpreterResult)
371         differences++;
372
373     for (unsigned j = 2, i = 0; i < m_numSubpatterns; j +=2, i++)
374         if ((offsetVector[j] != interpreterOffsetVector[j])
375             || ((offsetVector[j] >= 0) && (offsetVector[j+1] != interpreterOffsetVector[j+1])))
376             differences++;
377
378     if (differences) {
379         dataLogF("RegExp Discrepency for /%s/\n    string input ", pattern().utf8().data());
380         unsigned segmentLen = s.length() - static_cast<unsigned>(startOffset);
381
382         dataLogF((segmentLen < 150) ? "\"%s\"\n" : "\"%148s...\"\n", s.utf8().data() + startOffset);
383
384         if (jitResult != interpreterResult) {
385             dataLogF("    JIT result = %d, blah interpreted result = %d\n", jitResult, interpreterResult);
386             differences--;
387         } else {
388             dataLogF("    Correct result = %d\n", jitResult);
389         }
390
391         if (differences) {
392             for (unsigned j = 2, i = 0; i < m_numSubpatterns; j +=2, i++) {
393                 if (offsetVector[j] != interpreterOffsetVector[j])
394                     dataLogF("    JIT offset[%d] = %d, interpreted offset[%d] = %d\n", j, offsetVector[j], j, interpreterOffsetVector[j]);
395                 if ((offsetVector[j] >= 0) && (offsetVector[j+1] != interpreterOffsetVector[j+1]))
396                     dataLogF("    JIT offset[%d] = %d, interpreted offset[%d] = %d\n", j+1, offsetVector[j+1], j+1, interpreterOffsetVector[j+1]);
397             }
398         }
399     }
400 }
401 #endif
402
403 #if ENABLE(REGEXP_TRACING)
404     void RegExp::printTraceData()
405     {
406         char formattedPattern[41];
407         char rawPattern[41];
408
409         strncpy(rawPattern, pattern().utf8().data(), 40);
410         rawPattern[40]= '\0';
411
412         int pattLen = strlen(rawPattern);
413
414         snprintf(formattedPattern, 41, (pattLen <= 38) ? "/%.38s/" : "/%.36s...", rawPattern);
415
416 #if ENABLE(YARR_JIT)
417         Yarr::YarrCodeBlock& codeBlock = m_regExpJITCode;
418
419         const size_t jitAddrSize = 20;
420         char jit8BitMatchOnlyAddr[jitAddrSize];
421         char jit16BitMatchOnlyAddr[jitAddrSize];
422         char jit8BitMatchAddr[jitAddrSize];
423         char jit16BitMatchAddr[jitAddrSize];
424         if (m_state == ByteCode) {
425             snprintf(jit8BitMatchOnlyAddr, jitAddrSize, "fallback    ");
426             snprintf(jit16BitMatchOnlyAddr, jitAddrSize, "----      ");
427             snprintf(jit8BitMatchAddr, jitAddrSize, "fallback    ");
428             snprintf(jit16BitMatchAddr, jitAddrSize, "----      ");
429         } else {
430             snprintf(jit8BitMatchOnlyAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get8BitMatchOnlyAddr()));
431             snprintf(jit16BitMatchOnlyAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get16BitMatchOnlyAddr()));
432             snprintf(jit8BitMatchAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get8BitMatchAddr()));
433             snprintf(jit16BitMatchAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get16BitMatchAddr()));
434         }
435 #else
436         const char* jit8BitMatchOnlyAddr = "JIT Off";
437         const char* jit16BitMatchOnlyAddr = "";
438         const char* jit8BitMatchAddr = "JIT Off";
439         const char* jit16BitMatchAddr = "";
440 #endif
441         unsigned averageMatchOnlyStringLen = (unsigned)(m_rtMatchOnlyTotalSubjectStringLen / m_rtMatchOnlyCallCount);
442         unsigned averageMatchStringLen = (unsigned)(m_rtMatchTotalSubjectStringLen / m_rtMatchCallCount);
443
444         printf("%-40.40s %16.16s %16.16s %10d %10d %10u\n", formattedPattern, jit8BitMatchOnlyAddr, jit16BitMatchOnlyAddr, m_rtMatchOnlyCallCount, m_rtMatchOnlyFoundCount, averageMatchOnlyStringLen);
445         printf("                                         %16.16s %16.16s %10d %10d %10u\n", jit8BitMatchAddr, jit16BitMatchAddr, m_rtMatchCallCount, m_rtMatchFoundCount, averageMatchStringLen);
446     }
447 #endif
448
449 } // namespace JSC