9a5e69f55e30697575f8fae78def97c28eb765ea
[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, vm.osStackLimitWithReserve());
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     ConcurrentJITLocker locker(m_lock);
266     
267     Yarr::YarrPattern pattern(m_patternString, m_flags, &m_constructionError, vm->osStackLimitWithReserve());
268     if (m_constructionError) {
269         RELEASE_ASSERT_NOT_REACHED();
270 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
271         m_state = ParseError;
272         return;
273 #endif
274     }
275     ASSERT(m_numSubpatterns == pattern.m_numSubpatterns);
276
277     if (!hasCode()) {
278         ASSERT(m_state == NotCompiled);
279         vm->regExpCache()->addToStrongCache(this);
280         m_state = ByteCode;
281     }
282
283 #if ENABLE(YARR_JIT)
284     if (!pattern.m_containsBackreferences && !pattern.containsUnsignedLengthPattern() && !unicode() && vm->canUseRegExpJIT()) {
285         Yarr::jitCompile(pattern, charSize, vm, m_regExpJITCode);
286         if (!m_regExpJITCode.isFallBack()) {
287             m_state = JITCode;
288             return;
289         }
290     }
291 #else
292     UNUSED_PARAM(charSize);
293 #endif
294
295     m_state = ByteCode;
296     m_regExpBytecode = Yarr::byteCompile(pattern, &vm->m_regExpAllocator, &vm->m_regExpAllocatorLock);
297 }
298
299 int RegExp::match(VM& vm, const String& s, unsigned startOffset, Vector<int, 32>& ovector)
300 {
301     return matchInline(vm, s, startOffset, ovector);
302 }
303
304 bool RegExp::matchConcurrently(
305     VM& vm, const String& s, unsigned startOffset, int& position, Vector<int, 32>& ovector)
306 {
307     ConcurrentJITLocker locker(m_lock);
308
309     if (!hasCodeFor(s.is8Bit() ? Yarr::Char8 : Yarr::Char16))
310         return false;
311
312     position = match(vm, s, startOffset, ovector);
313     return true;
314 }
315
316 void RegExp::compileMatchOnly(VM* vm, Yarr::YarrCharSize charSize)
317 {
318     ConcurrentJITLocker locker(m_lock);
319     
320     Yarr::YarrPattern pattern(m_patternString, m_flags, &m_constructionError, vm->osStackLimitWithReserve());
321     if (m_constructionError) {
322         RELEASE_ASSERT_NOT_REACHED();
323 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
324         m_state = ParseError;
325         return;
326 #endif
327     }
328     ASSERT(m_numSubpatterns == pattern.m_numSubpatterns);
329
330     if (!hasCode()) {
331         ASSERT(m_state == NotCompiled);
332         vm->regExpCache()->addToStrongCache(this);
333         m_state = ByteCode;
334     }
335
336 #if ENABLE(YARR_JIT)
337     if (!pattern.m_containsBackreferences && !pattern.containsUnsignedLengthPattern() && !unicode() && vm->canUseRegExpJIT()) {
338         Yarr::jitCompile(pattern, charSize, vm, m_regExpJITCode, Yarr::MatchOnly);
339         if (!m_regExpJITCode.isFallBack()) {
340             m_state = JITCode;
341             return;
342         }
343     }
344 #else
345     UNUSED_PARAM(charSize);
346 #endif
347
348     m_state = ByteCode;
349     m_regExpBytecode = Yarr::byteCompile(pattern, &vm->m_regExpAllocator, &vm->m_regExpAllocatorLock);
350 }
351
352 MatchResult RegExp::match(VM& vm, const String& s, unsigned startOffset)
353 {
354     return matchInline(vm, s, startOffset);
355 }
356
357 bool RegExp::matchConcurrently(VM& vm, const String& s, unsigned startOffset, MatchResult& result)
358 {
359     ConcurrentJITLocker locker(m_lock);
360
361     if (!hasMatchOnlyCodeFor(s.is8Bit() ? Yarr::Char8 : Yarr::Char16))
362         return false;
363
364     result = match(vm, s, startOffset);
365     return true;
366 }
367
368 void RegExp::deleteCode()
369 {
370     ConcurrentJITLocker locker(m_lock);
371     
372     if (!hasCode())
373         return;
374     m_state = NotCompiled;
375 #if ENABLE(YARR_JIT)
376     m_regExpJITCode.clear();
377 #endif
378     m_regExpBytecode = nullptr;
379 }
380
381 #if ENABLE(YARR_JIT_DEBUG)
382 void RegExp::matchCompareWithInterpreter(const String& s, int startOffset, int* offsetVector, int jitResult)
383 {
384     int offsetVectorSize = (m_numSubpatterns + 1) * 2;
385     Vector<int, 32> interpreterOvector;
386     interpreterOvector.resize(offsetVectorSize);
387     int* interpreterOffsetVector = interpreterOvector.data();
388     int interpreterResult = 0;
389     int differences = 0;
390
391     // Initialize interpreterOffsetVector with the return value (index 0) and the 
392     // first subpattern start indicies (even index values) set to -1.
393     // No need to init the subpattern end indicies.
394     for (unsigned j = 0, i = 0; i < m_numSubpatterns + 1; j += 2, i++)
395         interpreterOffsetVector[j] = -1;
396
397     interpreterResult = Yarr::interpret(m_regExpBytecode.get(), s, startOffset, interpreterOffsetVector);
398
399     if (jitResult != interpreterResult)
400         differences++;
401
402     for (unsigned j = 2, i = 0; i < m_numSubpatterns; j +=2, i++)
403         if ((offsetVector[j] != interpreterOffsetVector[j])
404             || ((offsetVector[j] >= 0) && (offsetVector[j+1] != interpreterOffsetVector[j+1])))
405             differences++;
406
407     if (differences) {
408         dataLogF("RegExp Discrepency for /%s/\n    string input ", pattern().utf8().data());
409         unsigned segmentLen = s.length() - static_cast<unsigned>(startOffset);
410
411         dataLogF((segmentLen < 150) ? "\"%s\"\n" : "\"%148s...\"\n", s.utf8().data() + startOffset);
412
413         if (jitResult != interpreterResult) {
414             dataLogF("    JIT result = %d, blah interpreted result = %d\n", jitResult, interpreterResult);
415             differences--;
416         } else {
417             dataLogF("    Correct result = %d\n", jitResult);
418         }
419
420         if (differences) {
421             for (unsigned j = 2, i = 0; i < m_numSubpatterns; j +=2, i++) {
422                 if (offsetVector[j] != interpreterOffsetVector[j])
423                     dataLogF("    JIT offset[%d] = %d, interpreted offset[%d] = %d\n", j, offsetVector[j], j, interpreterOffsetVector[j]);
424                 if ((offsetVector[j] >= 0) && (offsetVector[j+1] != interpreterOffsetVector[j+1]))
425                     dataLogF("    JIT offset[%d] = %d, interpreted offset[%d] = %d\n", j+1, offsetVector[j+1], j+1, interpreterOffsetVector[j+1]);
426             }
427         }
428     }
429 }
430 #endif
431
432 #if ENABLE(REGEXP_TRACING)
433     void RegExp::printTraceData()
434     {
435         char formattedPattern[41];
436         char rawPattern[41];
437
438         strncpy(rawPattern, pattern().utf8().data(), 40);
439         rawPattern[40]= '\0';
440
441         int pattLen = strlen(rawPattern);
442
443         snprintf(formattedPattern, 41, (pattLen <= 38) ? "/%.38s/" : "/%.36s...", rawPattern);
444
445 #if ENABLE(YARR_JIT)
446         Yarr::YarrCodeBlock& codeBlock = m_regExpJITCode;
447
448         const size_t jitAddrSize = 20;
449         char jit8BitMatchOnlyAddr[jitAddrSize];
450         char jit16BitMatchOnlyAddr[jitAddrSize];
451         char jit8BitMatchAddr[jitAddrSize];
452         char jit16BitMatchAddr[jitAddrSize];
453         if (m_state == ByteCode) {
454             snprintf(jit8BitMatchOnlyAddr, jitAddrSize, "fallback    ");
455             snprintf(jit16BitMatchOnlyAddr, jitAddrSize, "----      ");
456             snprintf(jit8BitMatchAddr, jitAddrSize, "fallback    ");
457             snprintf(jit16BitMatchAddr, jitAddrSize, "----      ");
458         } else {
459             snprintf(jit8BitMatchOnlyAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get8BitMatchOnlyAddr()));
460             snprintf(jit16BitMatchOnlyAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get16BitMatchOnlyAddr()));
461             snprintf(jit8BitMatchAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get8BitMatchAddr()));
462             snprintf(jit16BitMatchAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get16BitMatchAddr()));
463         }
464 #else
465         const char* jit8BitMatchOnlyAddr = "JIT Off";
466         const char* jit16BitMatchOnlyAddr = "";
467         const char* jit8BitMatchAddr = "JIT Off";
468         const char* jit16BitMatchAddr = "";
469 #endif
470         unsigned averageMatchOnlyStringLen = (unsigned)(m_rtMatchOnlyTotalSubjectStringLen / m_rtMatchOnlyCallCount);
471         unsigned averageMatchStringLen = (unsigned)(m_rtMatchTotalSubjectStringLen / m_rtMatchCallCount);
472
473         printf("%-40.40s %16.16s %16.16s %10d %10d %10u\n", formattedPattern, jit8BitMatchOnlyAddr, jit16BitMatchOnlyAddr, m_rtMatchOnlyCallCount, m_rtMatchOnlyFoundCount, averageMatchOnlyStringLen);
474         printf("                                         %16.16s %16.16s %10d %10d %10u\n", jit8BitMatchAddr, jit16BitMatchAddr, m_rtMatchCallCount, m_rtMatchFoundCount, averageMatchStringLen);
475     }
476 #endif
477
478 } // namespace JSC