We should support CreateThis in the FTL
[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-2017 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", nullptr, nullptr, nullptr, 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 's':
63             if (flags & FlagDotAll)
64                 return InvalidFlags;
65             flags = static_cast<RegExpFlags>(flags | FlagDotAll);
66             break;
67             
68         case 'u':
69             if (flags & FlagUnicode)
70                 return InvalidFlags;
71             flags = static_cast<RegExpFlags>(flags | FlagUnicode);
72             break;
73                 
74         case 'y':
75             if (flags & FlagSticky)
76                 return InvalidFlags;
77             flags = static_cast<RegExpFlags>(flags | FlagSticky);
78             break;
79
80         default:
81             return InvalidFlags;
82         }
83     }
84
85     return flags;
86 }
87
88 #if REGEXP_FUNC_TEST_DATA_GEN
89 const char* const RegExpFunctionalTestCollector::s_fileName = "/tmp/RegExpTestsData";
90 RegExpFunctionalTestCollector* RegExpFunctionalTestCollector::s_instance = 0;
91
92 RegExpFunctionalTestCollector* RegExpFunctionalTestCollector::get()
93 {
94     if (!s_instance)
95         s_instance = new RegExpFunctionalTestCollector();
96
97     return s_instance;
98 }
99
100 void RegExpFunctionalTestCollector::outputOneTest(RegExp* regExp, const String& s, int startOffset, int* ovector, int result)
101 {
102     if ((!m_lastRegExp) || (m_lastRegExp != regExp)) {
103         m_lastRegExp = regExp;
104         fputc('/', m_file);
105         outputEscapedString(regExp->pattern(), true);
106         fputc('/', m_file);
107         if (regExp->global())
108             fputc('g', m_file);
109         if (regExp->ignoreCase())
110             fputc('i', m_file);
111         if (regExp->multiline())
112             fputc('m', m_file);
113         if (regExp->dotAll())
114             fputc('s', m_file);
115         if (regExp->unicode())
116             fputc('u', m_file);
117         if (regExp->sticky())
118             fputc('y', m_file);
119         fprintf(m_file, "\n");
120     }
121
122     fprintf(m_file, " \"");
123     outputEscapedString(s);
124     fprintf(m_file, "\", %d, %d, (", startOffset, result);
125     for (unsigned i = 0; i <= regExp->numSubpatterns(); i++) {
126         int subpatternBegin = ovector[i * 2];
127         int subpatternEnd = ovector[i * 2 + 1];
128         if (subpatternBegin == -1)
129             subpatternEnd = -1;
130         fprintf(m_file, "%d, %d", subpatternBegin, subpatternEnd);
131         if (i < regExp->numSubpatterns())
132             fputs(", ", m_file);
133     }
134
135     fprintf(m_file, ")\n");
136     fflush(m_file);
137 }
138
139 RegExpFunctionalTestCollector::RegExpFunctionalTestCollector()
140 {
141     m_file = fopen(s_fileName, "r+");
142     if  (!m_file)
143         m_file = fopen(s_fileName, "w+");
144
145     fseek(m_file, 0L, SEEK_END);
146 }
147
148 RegExpFunctionalTestCollector::~RegExpFunctionalTestCollector()
149 {
150     fclose(m_file);
151     s_instance = 0;
152 }
153
154 void RegExpFunctionalTestCollector::outputEscapedString(const String& s, bool escapeSlash)
155 {
156     int len = s.length();
157     
158     for (int i = 0; i < len; ++i) {
159         UChar c = s[i];
160
161         switch (c) {
162         case '\0':
163             fputs("\\0", m_file);
164             break;
165         case '\a':
166             fputs("\\a", m_file);
167             break;
168         case '\b':
169             fputs("\\b", m_file);
170             break;
171         case '\f':
172             fputs("\\f", m_file);
173             break;
174         case '\n':
175             fputs("\\n", m_file);
176             break;
177         case '\r':
178             fputs("\\r", m_file);
179             break;
180         case '\t':
181             fputs("\\t", m_file);
182             break;
183         case '\v':
184             fputs("\\v", m_file);
185             break;
186         case '/':
187             if (escapeSlash)
188                 fputs("\\/", m_file);
189             else
190                 fputs("/", m_file);
191             break;
192         case '\"':
193             fputs("\\\"", m_file);
194             break;
195         case '\\':
196             fputs("\\\\", m_file);
197             break;
198         case '\?':
199             fputs("\?", m_file);
200             break;
201         default:
202             if (c > 0x7f)
203                 fprintf(m_file, "\\u%04x", c);
204             else 
205                 fputc(c, m_file);
206             break;
207         }
208     }
209 }
210 #endif
211
212 RegExp::RegExp(VM& vm, const String& patternString, RegExpFlags flags)
213     : JSCell(vm, vm.regExpStructure.get())
214     , m_patternString(patternString)
215     , m_flags(flags)
216 {
217 }
218
219 void RegExp::finishCreation(VM& vm)
220 {
221     Base::finishCreation(vm);
222     Yarr::YarrPattern pattern(m_patternString, m_flags, m_constructionErrorCode, vm.stackLimit());
223     if (!isValid())
224         m_state = ParseError;
225     else {
226         m_numSubpatterns = pattern.m_numSubpatterns;
227         m_captureGroupNames.swap(pattern.m_captureGroupNames);
228         m_namedGroupToParenIndex.swap(pattern.m_namedGroupToParenIndex);
229     }
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, VM& vm)
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, vm) + 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
264 static std::unique_ptr<Yarr::BytecodePattern> byteCodeCompilePattern(VM* vm, Yarr::YarrPattern& pattern)
265 {
266     return Yarr::byteCompile(pattern, &vm->m_regExpAllocator, &vm->m_regExpAllocatorLock);
267 }
268
269 void RegExp::byteCodeCompileIfNecessary(VM* vm)
270 {
271     if (m_regExpBytecode)
272         return;
273
274     Yarr::YarrPattern pattern(m_patternString, m_flags, m_constructionErrorCode, vm->stackLimit());
275     if (hasError(m_constructionErrorCode)) {
276         RELEASE_ASSERT_NOT_REACHED();
277 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
278         m_state = ParseError;
279         return;
280 #endif
281     }
282     ASSERT(m_numSubpatterns == pattern.m_numSubpatterns);
283
284     m_regExpBytecode = byteCodeCompilePattern(vm, pattern);
285 }
286
287 void RegExp::compile(VM* vm, Yarr::YarrCharSize charSize)
288 {
289     ConcurrentJSLocker locker(m_lock);
290     
291     Yarr::YarrPattern pattern(m_patternString, m_flags, m_constructionErrorCode, vm->stackLimit());
292     if (hasError(m_constructionErrorCode)) {
293         RELEASE_ASSERT_NOT_REACHED();
294 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
295         m_state = ParseError;
296         return;
297 #endif
298     }
299     ASSERT(m_numSubpatterns == pattern.m_numSubpatterns);
300
301     if (!hasCode()) {
302         ASSERT(m_state == NotCompiled);
303         vm->regExpCache()->addToStrongCache(this);
304         m_state = ByteCode;
305     }
306
307 #if ENABLE(YARR_JIT)
308     if (!pattern.m_containsBackreferences && !pattern.containsUnsignedLengthPattern() && VM::canUseRegExpJIT()) {
309         Yarr::jitCompile(pattern, charSize, vm, m_regExpJITCode);
310         if (!m_regExpJITCode.failureReason()) {
311             m_state = JITCode;
312             return;
313         }
314     }
315 #else
316     UNUSED_PARAM(charSize);
317 #endif
318
319     if (Options::dumpCompiledRegExpPatterns())
320         dataLog("Can't JIT this regular expression: \"", m_patternString, "\"\n");
321
322     m_state = ByteCode;
323     m_regExpBytecode = byteCodeCompilePattern(vm, pattern);
324 }
325
326 int RegExp::match(VM& vm, const String& s, unsigned startOffset, Vector<int>& ovector)
327 {
328     return matchInline(vm, s, startOffset, ovector);
329 }
330
331 bool RegExp::matchConcurrently(
332     VM& vm, const String& s, unsigned startOffset, int& position, Vector<int>& ovector)
333 {
334     ConcurrentJSLocker locker(m_lock);
335
336     if (!hasCodeFor(s.is8Bit() ? Yarr::Char8 : Yarr::Char16))
337         return false;
338
339     position = match(vm, s, startOffset, ovector);
340     return true;
341 }
342
343 void RegExp::compileMatchOnly(VM* vm, Yarr::YarrCharSize charSize)
344 {
345     ConcurrentJSLocker locker(m_lock);
346     
347     Yarr::YarrPattern pattern(m_patternString, m_flags, m_constructionErrorCode, vm->stackLimit());
348     if (hasError(m_constructionErrorCode)) {
349         RELEASE_ASSERT_NOT_REACHED();
350 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
351         m_state = ParseError;
352         return;
353 #endif
354     }
355     ASSERT(m_numSubpatterns == pattern.m_numSubpatterns);
356
357     if (!hasCode()) {
358         ASSERT(m_state == NotCompiled);
359         vm->regExpCache()->addToStrongCache(this);
360         m_state = ByteCode;
361     }
362
363 #if ENABLE(YARR_JIT)
364     if (!pattern.m_containsBackreferences && !pattern.containsUnsignedLengthPattern() && VM::canUseRegExpJIT()) {
365         Yarr::jitCompile(pattern, charSize, vm, m_regExpJITCode, Yarr::MatchOnly);
366         if (!m_regExpJITCode.failureReason()) {
367             m_state = JITCode;
368             return;
369         }
370     }
371 #else
372     UNUSED_PARAM(charSize);
373 #endif
374
375     if (Options::dumpCompiledRegExpPatterns())
376         dataLog("Can't JIT this regular expression: \"", m_patternString, "\"\n");
377
378     m_state = ByteCode;
379     m_regExpBytecode = byteCodeCompilePattern(vm, pattern);
380 }
381
382 MatchResult RegExp::match(VM& vm, const String& s, unsigned startOffset)
383 {
384     return matchInline(vm, s, startOffset);
385 }
386
387 bool RegExp::matchConcurrently(VM& vm, const String& s, unsigned startOffset, MatchResult& result)
388 {
389     ConcurrentJSLocker locker(m_lock);
390
391     if (!hasMatchOnlyCodeFor(s.is8Bit() ? Yarr::Char8 : Yarr::Char16))
392         return false;
393
394     result = match(vm, s, startOffset);
395     return true;
396 }
397
398 void RegExp::deleteCode()
399 {
400     ConcurrentJSLocker locker(m_lock);
401     
402     if (!hasCode())
403         return;
404     m_state = NotCompiled;
405 #if ENABLE(YARR_JIT)
406     m_regExpJITCode.clear();
407 #endif
408     m_regExpBytecode = nullptr;
409 }
410
411 #if ENABLE(YARR_JIT_DEBUG)
412 void RegExp::matchCompareWithInterpreter(const String& s, int startOffset, int* offsetVector, int jitResult)
413 {
414     int offsetVectorSize = (m_numSubpatterns + 1) * 2;
415     Vector<int> interpreterOvector;
416     interpreterOvector.resize(offsetVectorSize);
417     int* interpreterOffsetVector = interpreterOvector.data();
418     int interpreterResult = 0;
419     int differences = 0;
420
421     // Initialize interpreterOffsetVector with the return value (index 0) and the 
422     // first subpattern start indicies (even index values) set to -1.
423     // No need to init the subpattern end indicies.
424     for (unsigned j = 0, i = 0; i < m_numSubpatterns + 1; j += 2, i++)
425         interpreterOffsetVector[j] = -1;
426
427     interpreterResult = Yarr::interpret(m_regExpBytecode.get(), s, startOffset, interpreterOffsetVector);
428
429     if (jitResult != interpreterResult)
430         differences++;
431
432     for (unsigned j = 2, i = 0; i < m_numSubpatterns; j +=2, i++)
433         if ((offsetVector[j] != interpreterOffsetVector[j])
434             || ((offsetVector[j] >= 0) && (offsetVector[j+1] != interpreterOffsetVector[j+1])))
435             differences++;
436
437     if (differences) {
438         dataLogF("RegExp Discrepency for /%s/\n    string input ", pattern().utf8().data());
439         unsigned segmentLen = s.length() - static_cast<unsigned>(startOffset);
440
441         dataLogF((segmentLen < 150) ? "\"%s\"\n" : "\"%148s...\"\n", s.utf8().data() + startOffset);
442
443         if (jitResult != interpreterResult) {
444             dataLogF("    JIT result = %d, blah interpreted result = %d\n", jitResult, interpreterResult);
445             differences--;
446         } else {
447             dataLogF("    Correct result = %d\n", jitResult);
448         }
449
450         if (differences) {
451             for (unsigned j = 2, i = 0; i < m_numSubpatterns; j +=2, i++) {
452                 if (offsetVector[j] != interpreterOffsetVector[j])
453                     dataLogF("    JIT offset[%d] = %d, interpreted offset[%d] = %d\n", j, offsetVector[j], j, interpreterOffsetVector[j]);
454                 if ((offsetVector[j] >= 0) && (offsetVector[j+1] != interpreterOffsetVector[j+1]))
455                     dataLogF("    JIT offset[%d] = %d, interpreted offset[%d] = %d\n", j+1, offsetVector[j+1], j+1, interpreterOffsetVector[j+1]);
456             }
457         }
458     }
459 }
460 #endif
461
462 #if ENABLE(REGEXP_TRACING)
463     void RegExp::printTraceData()
464     {
465         char formattedPattern[41];
466         char rawPattern[41];
467
468         strncpy(rawPattern, pattern().utf8().data(), 40);
469         rawPattern[40]= '\0';
470
471         int pattLen = strlen(rawPattern);
472
473         snprintf(formattedPattern, 41, (pattLen <= 38) ? "/%.38s/" : "/%.36s...", rawPattern);
474
475 #if ENABLE(YARR_JIT)
476         Yarr::YarrCodeBlock& codeBlock = m_regExpJITCode;
477
478         const size_t jitAddrSize = 20;
479         char jit8BitMatchOnlyAddr[jitAddrSize];
480         char jit16BitMatchOnlyAddr[jitAddrSize];
481         char jit8BitMatchAddr[jitAddrSize];
482         char jit16BitMatchAddr[jitAddrSize];
483         if (m_state == ByteCode) {
484             snprintf(jit8BitMatchOnlyAddr, jitAddrSize, "fallback    ");
485             snprintf(jit16BitMatchOnlyAddr, jitAddrSize, "----      ");
486             snprintf(jit8BitMatchAddr, jitAddrSize, "fallback    ");
487             snprintf(jit16BitMatchAddr, jitAddrSize, "----      ");
488         } else {
489             snprintf(jit8BitMatchOnlyAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get8BitMatchOnlyAddr()));
490             snprintf(jit16BitMatchOnlyAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get16BitMatchOnlyAddr()));
491             snprintf(jit8BitMatchAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get8BitMatchAddr()));
492             snprintf(jit16BitMatchAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.get16BitMatchAddr()));
493         }
494 #else
495         const char* jit8BitMatchOnlyAddr = "JIT Off";
496         const char* jit16BitMatchOnlyAddr = "";
497         const char* jit8BitMatchAddr = "JIT Off";
498         const char* jit16BitMatchAddr = "";
499 #endif
500         unsigned averageMatchOnlyStringLen = (unsigned)(m_rtMatchOnlyTotalSubjectStringLen / m_rtMatchOnlyCallCount);
501         unsigned averageMatchStringLen = (unsigned)(m_rtMatchTotalSubjectStringLen / m_rtMatchCallCount);
502
503         printf("%-40.40s %16.16s %16.16s %10d %10d %10u\n", formattedPattern, jit8BitMatchOnlyAddr, jit16BitMatchOnlyAddr, m_rtMatchOnlyCallCount, m_rtMatchOnlyFoundCount, averageMatchOnlyStringLen);
504         printf("                                         %16.16s %16.16s %10d %10d %10u\n", jit8BitMatchAddr, jit16BitMatchAddr, m_rtMatchCallCount, m_rtMatchFoundCount, averageMatchStringLen);
505     }
506 #endif
507
508 static CString regexpToSourceString(const RegExp* regExp)
509 {
510     char postfix[7] = { '/', 0, 0, 0, 0, 0, 0 };
511     int index = 1;
512     if (regExp->global())
513         postfix[index++] = 'g';
514     if (regExp->ignoreCase())
515         postfix[index++] = 'i';
516     if (regExp->multiline())
517         postfix[index] = 'm';
518     if (regExp->dotAll())
519         postfix[index++] = 's';
520     if (regExp->unicode())
521         postfix[index++] = 'u';
522     if (regExp->sticky())
523         postfix[index++] = 'y';
524
525     return toCString("/", regExp->pattern().impl(), postfix);
526 }
527
528 void RegExp::dumpToStream(const JSCell* cell, PrintStream& out)
529 {
530     out.print(regexpToSourceString(jsCast<const RegExp*>(cell)));
531 }
532
533 } // namespace JSC