Add support for RegExp "dotAll" flag
[WebKit-https.git] / Source / JavaScriptCore / runtime / RegExpPrototype.cpp
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003-2017 Apple Inc. All Rights Reserved.
4  *
5  *  This library is free software; you can redistribute it and/or
6  *  modify it under the terms of the GNU Lesser General Public
7  *  License as published by the Free Software Foundation; either
8  *  version 2 of the License, or (at your option) any later version.
9  *
10  *  This library is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  *  Lesser General Public License for more details.
14  *
15  *  You should have received a copy of the GNU Lesser General Public
16  *  License along with this library; if not, write to the Free Software
17  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18  *
19  */
20
21 #include "config.h"
22 #include "RegExpPrototype.h"
23
24 #include "ArrayPrototype.h"
25 #include "BuiltinNames.h"
26 #include "Error.h"
27 #include "JSArray.h"
28 #include "JSCBuiltins.h"
29 #include "JSCInlines.h"
30 #include "JSCJSValue.h"
31 #include "JSFunction.h"
32 #include "JSObject.h"
33 #include "JSString.h"
34 #include "JSStringBuilder.h"
35 #include "Lexer.h"
36 #include "ObjectPrototype.h"
37 #include "RegExp.h"
38 #include "RegExpCache.h"
39 #include "RegExpConstructor.h"
40 #include "RegExpObject.h"
41 #include "StringObject.h"
42 #include "StringRecursionChecker.h"
43 #include <wtf/text/StringBuilder.h>
44
45 namespace JSC {
46
47 static EncodedJSValue JSC_HOST_CALL regExpProtoFuncExec(ExecState*);
48 static EncodedJSValue JSC_HOST_CALL regExpProtoFuncCompile(ExecState*);
49 static EncodedJSValue JSC_HOST_CALL regExpProtoFuncToString(ExecState*);
50 static EncodedJSValue JSC_HOST_CALL regExpProtoGetterGlobal(ExecState*);
51 static EncodedJSValue JSC_HOST_CALL regExpProtoGetterIgnoreCase(ExecState*);
52 static EncodedJSValue JSC_HOST_CALL regExpProtoGetterMultiline(ExecState*);
53 static EncodedJSValue JSC_HOST_CALL regExpProtoGetterDotAll(ExecState*);
54 static EncodedJSValue JSC_HOST_CALL regExpProtoGetterSticky(ExecState*);
55 static EncodedJSValue JSC_HOST_CALL regExpProtoGetterUnicode(ExecState*);
56 static EncodedJSValue JSC_HOST_CALL regExpProtoGetterSource(ExecState*);
57 static EncodedJSValue JSC_HOST_CALL regExpProtoGetterFlags(ExecState*);
58
59 const ClassInfo RegExpPrototype::s_info = { "Object", &Base::s_info, nullptr, nullptr, CREATE_METHOD_TABLE(RegExpPrototype) };
60
61 RegExpPrototype::RegExpPrototype(VM& vm, Structure* structure)
62     : JSNonFinalObject(vm, structure)
63 {
64 }
65
66 void RegExpPrototype::finishCreation(VM& vm, JSGlobalObject* globalObject)
67 {
68     Base::finishCreation(vm);
69     ASSERT(inherits(vm, info()));
70     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->compile, regExpProtoFuncCompile, DontEnum, 2);
71     JSC_NATIVE_INTRINSIC_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->exec, regExpProtoFuncExec, DontEnum, 1, RegExpExecIntrinsic);
72     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->toString, regExpProtoFuncToString, DontEnum, 0);
73     JSC_NATIVE_GETTER(vm.propertyNames->global, regExpProtoGetterGlobal, DontEnum | Accessor);
74     JSC_NATIVE_GETTER(vm.propertyNames->dotAll, regExpProtoGetterDotAll, DontEnum | Accessor);
75     JSC_NATIVE_GETTER(vm.propertyNames->ignoreCase, regExpProtoGetterIgnoreCase, DontEnum | Accessor);
76     JSC_NATIVE_GETTER(vm.propertyNames->multiline, regExpProtoGetterMultiline, DontEnum | Accessor);
77     JSC_NATIVE_GETTER(vm.propertyNames->sticky, regExpProtoGetterSticky, DontEnum | Accessor);
78     JSC_NATIVE_GETTER(vm.propertyNames->unicode, regExpProtoGetterUnicode, DontEnum | Accessor);
79     JSC_NATIVE_GETTER(vm.propertyNames->source, regExpProtoGetterSource, DontEnum | Accessor);
80     JSC_NATIVE_GETTER(vm.propertyNames->flags, regExpProtoGetterFlags, DontEnum | Accessor);
81
82     JSFunction* matchFunction = JSFunction::createBuiltinFunction(vm, regExpPrototypeMatchCodeGenerator(vm), globalObject, ASCIILiteral("[Symbol.match]"));
83     putDirectWithoutTransition(vm, vm.propertyNames->matchSymbol, matchFunction, DontEnum);
84     JSFunction* replaceFunction = JSFunction::createBuiltinFunction(vm, regExpPrototypeReplaceCodeGenerator(vm), globalObject, ASCIILiteral("[Symbol.replace]"));
85     putDirectWithoutTransition(vm, vm.propertyNames->replaceSymbol, replaceFunction, DontEnum);
86     JSFunction* searchFunction = JSFunction::createBuiltinFunction(vm, regExpPrototypeSearchCodeGenerator(vm), globalObject, ASCIILiteral("[Symbol.search]"));
87     putDirectWithoutTransition(vm, vm.propertyNames->searchSymbol, searchFunction, DontEnum);
88     JSFunction* splitFunction = JSFunction::createBuiltinFunction(vm, regExpPrototypeSplitCodeGenerator(vm), globalObject, ASCIILiteral("[Symbol.split]"));
89     putDirectWithoutTransition(vm, vm.propertyNames->splitSymbol, splitFunction, DontEnum);
90
91     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->test, regExpPrototypeTestCodeGenerator, DontEnum);
92
93     m_emptyRegExp.set(vm, this, RegExp::create(vm, "", NoFlags));
94 }
95
96 void RegExpPrototype::visitChildren(JSCell* cell, SlotVisitor& visitor)
97 {
98     RegExpPrototype* thisObject = jsCast<RegExpPrototype*>(cell);
99     ASSERT_GC_OBJECT_INHERITS(thisObject, info());
100     Base::visitChildren(thisObject, visitor);
101     
102     visitor.append(thisObject->m_emptyRegExp);
103 }
104
105 // ------------------------------ Functions ---------------------------
106
107 EncodedJSValue JSC_HOST_CALL regExpProtoFuncTestFast(ExecState* exec)
108 {
109     VM& vm = exec->vm();
110     auto scope = DECLARE_THROW_SCOPE(vm);
111
112     JSValue thisValue = exec->thisValue();
113     if (!thisValue.inherits(vm, RegExpObject::info()))
114         return throwVMTypeError(exec, scope);
115     JSString* string = exec->argument(0).toStringOrNull(exec);
116     ASSERT(!!scope.exception() == !string);
117     if (!string)
118         return JSValue::encode(jsUndefined());
119     scope.release();
120     return JSValue::encode(jsBoolean(asRegExpObject(thisValue)->test(exec, exec->lexicalGlobalObject(), string)));
121 }
122
123 EncodedJSValue JSC_HOST_CALL regExpProtoFuncExec(ExecState* exec)
124 {
125     VM& vm = exec->vm();
126     auto scope = DECLARE_THROW_SCOPE(vm);
127
128     JSValue thisValue = exec->thisValue();
129     if (!thisValue.inherits(vm, RegExpObject::info()))
130         return throwVMTypeError(exec, scope, "Builtin RegExp exec can only be called on a RegExp object");
131     JSString* string = exec->argument(0).toStringOrNull(exec);
132     ASSERT(!!scope.exception() == !string);
133     if (!string)
134         return JSValue::encode(jsUndefined());
135     scope.release();
136     return JSValue::encode(asRegExpObject(thisValue)->exec(exec, exec->lexicalGlobalObject(), string));
137 }
138
139 EncodedJSValue JSC_HOST_CALL regExpProtoFuncMatchFast(ExecState* exec)
140 {
141     VM& vm = exec->vm();
142     auto scope = DECLARE_THROW_SCOPE(vm);
143
144     JSValue thisValue = exec->thisValue();
145     if (!thisValue.inherits(vm, RegExpObject::info()))
146         return throwVMTypeError(exec, scope);
147     JSString* string = exec->argument(0).toStringOrNull(exec);
148     ASSERT(!!scope.exception() == !string);
149     if (!string)
150         return encodedJSValue();
151     if (!asRegExpObject(thisValue)->regExp()->global()) {
152         scope.release();
153         return JSValue::encode(asRegExpObject(thisValue)->exec(exec, exec->lexicalGlobalObject(), string));
154     }
155     scope.release();
156     return JSValue::encode(asRegExpObject(thisValue)->matchGlobal(exec, exec->lexicalGlobalObject(), string));
157 }
158
159 EncodedJSValue JSC_HOST_CALL regExpProtoFuncCompile(ExecState* exec)
160 {
161     VM& vm = exec->vm();
162     auto scope = DECLARE_THROW_SCOPE(vm);
163
164     JSValue thisValue = exec->thisValue();
165     if (!thisValue.inherits(vm, RegExpObject::info()))
166         return throwVMTypeError(exec, scope);
167
168     RegExp* regExp;
169     JSValue arg0 = exec->argument(0);
170     JSValue arg1 = exec->argument(1);
171     
172     if (arg0.inherits(vm, RegExpObject::info())) {
173         if (!arg1.isUndefined())
174             return throwVMTypeError(exec, scope, ASCIILiteral("Cannot supply flags when constructing one RegExp from another."));
175         regExp = asRegExpObject(arg0)->regExp();
176     } else {
177         String pattern = arg0.isUndefined() ? emptyString() : arg0.toWTFString(exec);
178         RETURN_IF_EXCEPTION(scope, encodedJSValue());
179
180         RegExpFlags flags = NoFlags;
181         if (!arg1.isUndefined()) {
182             flags = regExpFlags(arg1.toWTFString(exec));
183             RETURN_IF_EXCEPTION(scope, encodedJSValue());
184             if (flags == InvalidFlags)
185                 return throwVMError(exec, scope, createSyntaxError(exec, ASCIILiteral("Invalid flags supplied to RegExp constructor.")));
186         }
187         regExp = RegExp::create(vm, pattern, flags);
188     }
189
190     if (!regExp->isValid())
191         return throwVMError(exec, scope, createSyntaxError(exec, regExp->errorMessage()));
192
193     asRegExpObject(thisValue)->setRegExp(vm, regExp);
194     scope.release();
195     asRegExpObject(thisValue)->setLastIndex(exec, 0);
196     return JSValue::encode(thisValue);
197 }
198
199 typedef std::array<char, 5 + 1> FlagsString; // 5 different flags and a null character terminator.
200
201 static inline FlagsString flagsString(ExecState* exec, JSObject* regexp)
202 {
203     FlagsString string;
204     string[0] = 0;
205
206     VM& vm = exec->vm();
207     auto scope = DECLARE_THROW_SCOPE(vm);
208
209     JSValue globalValue = regexp->get(exec, vm.propertyNames->global);
210     RETURN_IF_EXCEPTION(scope, string);
211     JSValue ignoreCaseValue = regexp->get(exec, vm.propertyNames->ignoreCase);
212     RETURN_IF_EXCEPTION(scope, string);
213     JSValue multilineValue = regexp->get(exec, vm.propertyNames->multiline);
214     RETURN_IF_EXCEPTION(scope, string);
215     JSValue dotAllValue = regexp->get(exec, vm.propertyNames->dotAll);
216     RETURN_IF_EXCEPTION(scope, string);
217     JSValue unicodeValue = regexp->get(exec, vm.propertyNames->unicode);
218     RETURN_IF_EXCEPTION(scope, string);
219     JSValue stickyValue = regexp->get(exec, vm.propertyNames->sticky);
220     RETURN_IF_EXCEPTION(scope, string);
221
222     unsigned index = 0;
223     if (globalValue.toBoolean(exec))
224         string[index++] = 'g';
225     if (ignoreCaseValue.toBoolean(exec))
226         string[index++] = 'i';
227     if (multilineValue.toBoolean(exec))
228         string[index++] = 'm';
229     if (dotAllValue.toBoolean(exec))
230         string[index++] = 's';
231     if (unicodeValue.toBoolean(exec))
232         string[index++] = 'u';
233     if (stickyValue.toBoolean(exec))
234         string[index++] = 'y';
235     ASSERT(index < string.size());
236     string[index] = 0;
237     return string;
238 }
239
240 EncodedJSValue JSC_HOST_CALL regExpProtoFuncToString(ExecState* exec)
241 {
242     VM& vm = exec->vm();
243     auto scope = DECLARE_THROW_SCOPE(vm);
244
245     JSValue thisValue = exec->thisValue();
246     if (!thisValue.isObject())
247         return throwVMTypeError(exec, scope);
248
249     JSObject* thisObject = asObject(thisValue);
250
251     StringRecursionChecker checker(exec, thisObject);
252     ASSERT(!scope.exception() || checker.earlyReturnValue());
253     if (JSValue earlyReturnValue = checker.earlyReturnValue())
254         return JSValue::encode(earlyReturnValue);
255
256     JSValue sourceValue = thisObject->get(exec, vm.propertyNames->source);
257     RETURN_IF_EXCEPTION(scope, encodedJSValue());
258     String source = sourceValue.toWTFString(exec);
259     RETURN_IF_EXCEPTION(scope, encodedJSValue());
260
261     JSValue flagsValue = thisObject->get(exec, vm.propertyNames->flags);
262     RETURN_IF_EXCEPTION(scope, encodedJSValue());
263     String flags = flagsValue.toWTFString(exec);
264     RETURN_IF_EXCEPTION(scope, encodedJSValue());
265
266     scope.release();
267     return JSValue::encode(jsMakeNontrivialString(exec, '/', source, '/', flags));
268 }
269
270 EncodedJSValue JSC_HOST_CALL regExpProtoGetterGlobal(ExecState* exec)
271 {
272     VM& vm = exec->vm();
273     auto scope = DECLARE_THROW_SCOPE(vm);
274
275     JSValue thisValue = exec->thisValue();
276     if (UNLIKELY(!thisValue.inherits(vm, RegExpObject::info()))) {
277         if (thisValue.inherits(vm, RegExpPrototype::info()))
278             return JSValue::encode(jsUndefined());
279         return throwVMTypeError(exec, scope, ASCIILiteral("The RegExp.prototype.global getter can only be called on a RegExp object"));
280     }
281
282     return JSValue::encode(jsBoolean(asRegExpObject(thisValue)->regExp()->global()));
283 }
284
285 EncodedJSValue JSC_HOST_CALL regExpProtoGetterIgnoreCase(ExecState* exec)
286 {
287     VM& vm = exec->vm();
288     auto scope = DECLARE_THROW_SCOPE(vm);
289
290     JSValue thisValue = exec->thisValue();
291     if (UNLIKELY(!thisValue.inherits(vm, RegExpObject::info()))) {
292         if (thisValue.inherits(vm, RegExpPrototype::info()))
293             return JSValue::encode(jsUndefined());
294         return throwVMTypeError(exec, scope, ASCIILiteral("The RegExp.prototype.ignoreCase getter can only be called on a RegExp object"));
295     }
296
297     return JSValue::encode(jsBoolean(asRegExpObject(thisValue)->regExp()->ignoreCase()));
298 }
299
300 EncodedJSValue JSC_HOST_CALL regExpProtoGetterMultiline(ExecState* exec)
301 {
302     VM& vm = exec->vm();
303     auto scope = DECLARE_THROW_SCOPE(vm);
304
305     JSValue thisValue = exec->thisValue();
306     if (UNLIKELY(!thisValue.inherits(vm, RegExpObject::info()))) {
307         if (thisValue.inherits(vm, RegExpPrototype::info()))
308             return JSValue::encode(jsUndefined());
309         return throwVMTypeError(exec, scope, ASCIILiteral("The RegExp.prototype.multiline getter can only be called on a RegExp object"));
310     }
311
312     return JSValue::encode(jsBoolean(asRegExpObject(thisValue)->regExp()->multiline()));
313 }
314
315 EncodedJSValue JSC_HOST_CALL regExpProtoGetterDotAll(ExecState* exec)
316 {
317     VM& vm = exec->vm();
318     auto scope = DECLARE_THROW_SCOPE(vm);
319     
320     JSValue thisValue = exec->thisValue();
321     if (UNLIKELY(!thisValue.inherits(vm, RegExpObject::info()))) {
322         if (thisValue.inherits(vm, RegExpPrototype::info()))
323             return JSValue::encode(jsUndefined());
324         return throwVMTypeError(exec, scope, ASCIILiteral("The RegExp.prototype.dotAll getter can only be called on a RegExp object"));
325     }
326     
327     return JSValue::encode(jsBoolean(asRegExpObject(thisValue)->regExp()->dotAll()));
328 }
329     
330 EncodedJSValue JSC_HOST_CALL regExpProtoGetterSticky(ExecState* exec)
331 {
332     VM& vm = exec->vm();
333     auto scope = DECLARE_THROW_SCOPE(vm);
334
335     JSValue thisValue = exec->thisValue();
336     if (UNLIKELY(!thisValue.inherits(vm, RegExpObject::info()))) {
337         if (thisValue.inherits(vm, RegExpPrototype::info()))
338             return JSValue::encode(jsUndefined());
339         return throwVMTypeError(exec, scope, ASCIILiteral("The RegExp.prototype.sticky getter can only be called on a RegExp object"));
340     }
341     
342     return JSValue::encode(jsBoolean(asRegExpObject(thisValue)->regExp()->sticky()));
343 }
344
345 EncodedJSValue JSC_HOST_CALL regExpProtoGetterUnicode(ExecState* exec)
346 {
347     VM& vm = exec->vm();
348     auto scope = DECLARE_THROW_SCOPE(vm);
349
350     JSValue thisValue = exec->thisValue();
351     if (UNLIKELY(!thisValue.inherits(vm, RegExpObject::info()))) {
352         if (thisValue.inherits(vm, RegExpPrototype::info()))
353             return JSValue::encode(jsUndefined());
354         return throwVMTypeError(exec, scope, ASCIILiteral("The RegExp.prototype.unicode getter can only be called on a RegExp object"));
355     }
356     
357     return JSValue::encode(jsBoolean(asRegExpObject(thisValue)->regExp()->unicode()));
358 }
359
360 EncodedJSValue JSC_HOST_CALL regExpProtoGetterFlags(ExecState* exec)
361 {
362     VM& vm = exec->vm();
363     auto scope = DECLARE_THROW_SCOPE(vm);
364
365     JSValue thisValue = exec->thisValue();
366     if (UNLIKELY(!thisValue.isObject()))
367         return throwVMTypeError(exec, scope, ASCIILiteral("The RegExp.prototype.flags getter can only be called on an object"));
368
369     auto flags = flagsString(exec, asObject(thisValue));
370     RETURN_IF_EXCEPTION(scope, encodedJSValue());
371
372     return JSValue::encode(jsString(exec, flags.data()));
373 }
374
375 template <typename CharacterType>
376 static inline void appendLineTerminatorEscape(StringBuilder&, CharacterType);
377
378 template <>
379 inline void appendLineTerminatorEscape<LChar>(StringBuilder& builder, LChar lineTerminator)
380 {
381     if (lineTerminator == '\n')
382         builder.append('n');
383     else
384         builder.append('r');
385 }
386
387 template <>
388 inline void appendLineTerminatorEscape<UChar>(StringBuilder& builder, UChar lineTerminator)
389 {
390     if (lineTerminator == '\n')
391         builder.append('n');
392     else if (lineTerminator == '\r')
393         builder.append('r');
394     else if (lineTerminator == 0x2028)
395         builder.appendLiteral("u2028");
396     else
397         builder.appendLiteral("u2029");
398 }
399
400 template <typename CharacterType>
401 static inline JSValue regExpProtoGetterSourceInternal(ExecState* exec, const String& pattern, const CharacterType* characters, unsigned length)
402 {
403     bool previousCharacterWasBackslash = false;
404     bool inBrackets = false;
405     bool shouldEscape = false;
406
407     // 15.10.6.4 specifies that RegExp.prototype.toString must return '/' + source + '/',
408     // and also states that the result must be a valid RegularExpressionLiteral. '//' is
409     // not a valid RegularExpressionLiteral (since it is a single line comment), and hence
410     // source cannot ever validly be "". If the source is empty, return a different Pattern
411     // that would match the same thing.
412     if (!length)
413         return jsNontrivialString(exec, ASCIILiteral("(?:)"));
414
415     // early return for strings that don't contain a forwards slash and LineTerminator
416     for (unsigned i = 0; i < length; ++i) {
417         CharacterType ch = characters[i];
418         if (!previousCharacterWasBackslash) {
419             if (inBrackets) {
420                 if (ch == ']')
421                     inBrackets = false;
422             } else {
423                 if (ch == '/') {
424                     shouldEscape = true;
425                     break;
426                 }
427                 if (ch == '[')
428                     inBrackets = true;
429             }
430         }
431
432         if (Lexer<CharacterType>::isLineTerminator(ch)) {
433             shouldEscape = true;
434             break;
435         }
436
437         if (previousCharacterWasBackslash)
438             previousCharacterWasBackslash = false;
439         else
440             previousCharacterWasBackslash = ch == '\\';
441     }
442
443     if (!shouldEscape)
444         return jsString(exec, pattern);
445
446     previousCharacterWasBackslash = false;
447     inBrackets = false;
448     StringBuilder result;
449     for (unsigned i = 0; i < length; ++i) {
450         CharacterType ch = characters[i];
451         if (!previousCharacterWasBackslash) {
452             if (inBrackets) {
453                 if (ch == ']')
454                     inBrackets = false;
455             } else {
456                 if (ch == '/')
457                     result.append('\\');
458                 else if (ch == '[')
459                     inBrackets = true;
460             }
461         }
462
463         // escape LineTerminator
464         if (Lexer<CharacterType>::isLineTerminator(ch)) {
465             if (!previousCharacterWasBackslash)
466                 result.append('\\');
467
468             appendLineTerminatorEscape<CharacterType>(result, ch);
469         } else
470             result.append(ch);
471
472         if (previousCharacterWasBackslash)
473             previousCharacterWasBackslash = false;
474         else
475             previousCharacterWasBackslash = ch == '\\';
476     }
477
478     return jsString(exec, result.toString());
479 }
480
481 EncodedJSValue JSC_HOST_CALL regExpProtoGetterSource(ExecState* exec)
482 {
483     VM& vm = exec->vm();
484     auto scope = DECLARE_THROW_SCOPE(vm);
485
486     JSValue thisValue = exec->thisValue();
487     if (UNLIKELY(!thisValue.inherits(vm, RegExpObject::info()))) {
488         if (thisValue.inherits(vm, RegExpPrototype::info()))
489             return JSValue::encode(jsString(exec, ASCIILiteral("(?:)")));
490         return throwVMTypeError(exec, scope, ASCIILiteral("The RegExp.prototype.source getter can only be called on a RegExp object"));
491     }
492
493     String pattern = asRegExpObject(thisValue)->regExp()->pattern();
494     if (pattern.is8Bit())
495         return JSValue::encode(regExpProtoGetterSourceInternal(exec, pattern, pattern.characters8(), pattern.length()));
496     return JSValue::encode(regExpProtoGetterSourceInternal(exec, pattern, pattern.characters16(), pattern.length()));
497 }
498
499 EncodedJSValue JSC_HOST_CALL regExpProtoFuncSearchFast(ExecState* exec)
500 {
501     VM& vm = exec->vm();
502     auto scope = DECLARE_THROW_SCOPE(vm);
503     JSValue thisValue = exec->thisValue();
504     RegExp* regExp = asRegExpObject(thisValue)->regExp();
505
506     JSString* string = exec->uncheckedArgument(0).toString(exec);
507     String s = string->value(exec);
508     RETURN_IF_EXCEPTION(scope, encodedJSValue());
509
510     RegExpConstructor* regExpConstructor = exec->lexicalGlobalObject()->regExpConstructor();
511     MatchResult result = regExpConstructor->performMatch(vm, regExp, string, s, 0);
512     return JSValue::encode(result ? jsNumber(result.start) : jsNumber(-1));
513 }
514
515 static inline unsigned advanceStringIndex(String str, unsigned strSize, unsigned index, bool isUnicode)
516 {
517     if (!isUnicode)
518         return ++index;
519     return RegExpObject::advanceStringUnicode(str, strSize, index);
520 }
521
522 enum SplitControl {
523     ContinueSplit,
524     AbortSplit
525 };
526
527 template<typename ControlFunc, typename PushFunc>
528 void genericSplit(
529     VM& vm, RegExp* regexp, const String& input, unsigned inputSize, unsigned& position,
530     unsigned& matchPosition, bool regExpIsSticky, bool regExpIsUnicode,
531     const ControlFunc& control, const PushFunc& push)
532 {
533     Vector<int> ovector;
534         
535     while (matchPosition < inputSize) {
536         if (control() == AbortSplit)
537             return;
538         
539         ovector.shrink(0);
540         
541         // a. Perform ? Set(splitter, "lastIndex", q, true).
542         // b. Let z be ? RegExpExec(splitter, S).
543         int mpos = regexp->match(vm, input, matchPosition, ovector);
544
545         // c. If z is null, let q be AdvanceStringIndex(S, q, unicodeMatching).
546         if (mpos < 0) {
547             if (!regExpIsSticky)
548                 break;
549             matchPosition = advanceStringIndex(input, inputSize, matchPosition, regExpIsUnicode);
550             continue;
551         }
552         if (static_cast<unsigned>(mpos) >= inputSize) {
553             // The spec redoes the RegExpExec starting at the next character of the input.
554             // But in our case, mpos < 0 means that the native regexp already searched all permutations
555             // and know that we won't be able to find a match for the separator even if we redo the
556             // RegExpExec starting at the next character of the input. So, just bail.
557             break;
558         }
559
560         // d. Else, z is not null
561         //    i. Let e be ? ToLength(? Get(splitter, "lastIndex")).
562         //   ii. Let e be min(e, size).
563         matchPosition = mpos;
564         unsigned matchEnd = ovector[1];
565
566         //  iii. If e = p, let q be AdvanceStringIndex(S, q, unicodeMatching).
567         if (matchEnd == position) {
568             matchPosition = advanceStringIndex(input, inputSize, matchPosition, regExpIsUnicode);
569             continue;
570         }
571         // if matchEnd == 0 then position should also be zero and thus matchEnd should equal position.
572         ASSERT(matchEnd);
573
574         //   iv. Else e != p,
575         unsigned numberOfCaptures = regexp->numSubpatterns();
576         
577         // 1. Let T be a String value equal to the substring of S consisting of the elements at indices p (inclusive) through q (exclusive).
578         // 2. Perform ! CreateDataProperty(A, ! ToString(lengthA), T).
579         if (push(true, position, matchPosition - position) == AbortSplit)
580             return;
581         
582         // 5. Let p be e.
583         position = matchEnd;
584         
585         // 6. Let numberOfCaptures be ? ToLength(? Get(z, "length")).
586         // 7. Let numberOfCaptures be max(numberOfCaptures-1, 0).
587         // 8. Let i be 1.
588         // 9. Repeat, while i <= numberOfCaptures,
589         for (unsigned i = 1; i <= numberOfCaptures; ++i) {
590             // a. Let nextCapture be ? Get(z, ! ToString(i)).
591             // b. Perform ! CreateDataProperty(A, ! ToString(lengthA), nextCapture).
592             int sub = ovector[i * 2];
593             if (push(sub >= 0, sub, ovector[i * 2 + 1] - sub) == AbortSplit)
594                 return;
595         }
596         
597         // 10. Let q be p.
598         matchPosition = position;
599     }
600 }
601
602 // ES 21.2.5.11 RegExp.prototype[@@split](string, limit)
603 EncodedJSValue JSC_HOST_CALL regExpProtoFuncSplitFast(ExecState* exec)
604 {
605     VM& vm = exec->vm();
606     auto scope = DECLARE_THROW_SCOPE(vm);
607
608     // 1. [handled by JS builtin] Let rx be the this value.
609     // 2. [handled by JS builtin] If Type(rx) is not Object, throw a TypeError exception.
610     JSValue thisValue = exec->thisValue();
611     RegExp* regexp = asRegExpObject(thisValue)->regExp();
612
613     // 3. [handled by JS builtin] Let S be ? ToString(string).
614     JSString* inputString = exec->argument(0).toString(exec);
615     String input = inputString->value(exec);
616     RETURN_IF_EXCEPTION(scope, encodedJSValue());
617     ASSERT(!input.isNull());
618
619     // 4. [handled by JS builtin] Let C be ? SpeciesConstructor(rx, %RegExp%).
620     // 5. [handled by JS builtin] Let flags be ? ToString(? Get(rx, "flags")).
621     // 6. [handled by JS builtin] If flags contains "u", let unicodeMatching be true.
622     // 7. [handled by JS builtin] Else, let unicodeMatching be false.
623     // 8. [handled by JS builtin] If flags contains "y", let newFlags be flags.
624     // 9. [handled by JS builtin] Else, let newFlags be the string that is the concatenation of flags and "y".
625     // 10. [handled by JS builtin] Let splitter be ? Construct(C, « rx, newFlags »).
626
627     // 11. Let A be ArrayCreate(0).
628     // 12. Let lengthA be 0.
629     JSArray* result = constructEmptyArray(exec, 0);
630     RETURN_IF_EXCEPTION(scope, encodedJSValue());
631     unsigned resultLength = 0;
632
633     // 13. If limit is undefined, let lim be 2^32-1; else let lim be ? ToUint32(limit).
634     JSValue limitValue = exec->argument(1);
635     unsigned limit = limitValue.isUndefined() ? 0xFFFFFFFFu : limitValue.toUInt32(exec);
636
637     // 14. Let size be the number of elements in S.
638     unsigned inputSize = input.length();
639
640     // 15. Let p = 0.
641     unsigned position = 0;
642
643     // 16. If lim == 0, return A.
644     if (!limit)
645         return JSValue::encode(result);
646
647     // 17. If size == 0, then
648     if (input.isEmpty()) {
649         // a. Let z be ? RegExpExec(splitter, S).
650         // b. If z is not null, return A.
651         // c. Perform ! CreateDataProperty(A, "0", S).
652         // d. Return A.
653         if (!regexp->match(vm, input, 0)) {
654             result->putDirectIndex(exec, 0, inputString);
655             RETURN_IF_EXCEPTION(scope, encodedJSValue());
656         }
657         return JSValue::encode(result);
658     }
659
660     // 18. Let q = p.
661     unsigned matchPosition = position;
662     // 19. Repeat, while q < size
663     bool regExpIsSticky = regexp->sticky();
664     bool regExpIsUnicode = regexp->unicode();
665     
666     unsigned maxSizeForDirectPath = 100000;
667     
668     genericSplit(
669         vm, regexp, input, inputSize, position, matchPosition, regExpIsSticky, regExpIsUnicode,
670         [&] () -> SplitControl {
671             if (resultLength >= maxSizeForDirectPath)
672                 return AbortSplit;
673             return ContinueSplit;
674         },
675         [&] (bool isDefined, unsigned start, unsigned length) -> SplitControl {
676             result->putDirectIndex(exec, resultLength++, isDefined ? JSRopeString::createSubstringOfResolved(vm, inputString, start, length) : jsUndefined());
677             RETURN_IF_EXCEPTION(scope, AbortSplit);
678             if (resultLength >= limit)
679                 return AbortSplit;
680             return ContinueSplit;
681         });
682     RETURN_IF_EXCEPTION(scope, encodedJSValue());
683
684     if (resultLength >= limit)
685         return JSValue::encode(result);
686     if (resultLength < maxSizeForDirectPath) {
687         // 20. Let T be a String value equal to the substring of S consisting of the elements at indices p (inclusive) through size (exclusive).
688         // 21. Perform ! CreateDataProperty(A, ! ToString(lengthA), T).
689         scope.release();
690         result->putDirectIndex(exec, resultLength, JSRopeString::createSubstringOfResolved(vm, inputString, position, inputSize - position));
691         
692         // 22. Return A.
693         return JSValue::encode(result);
694     }
695     
696     // Now do a dry run to see how big things get. Give up if they get absurd.
697     unsigned savedPosition = position;
698     unsigned savedMatchPosition = matchPosition;
699     unsigned dryRunCount = 0;
700     genericSplit(
701         vm, regexp, input, inputSize, position, matchPosition, regExpIsSticky, regExpIsUnicode,
702         [&] () -> SplitControl {
703             if (resultLength + dryRunCount > MAX_STORAGE_VECTOR_LENGTH)
704                 return AbortSplit;
705             return ContinueSplit;
706         },
707         [&] (bool, unsigned, unsigned) -> SplitControl {
708             dryRunCount++;
709             if (resultLength + dryRunCount >= limit)
710                 return AbortSplit;
711             return ContinueSplit;
712         });
713     
714     if (resultLength + dryRunCount > MAX_STORAGE_VECTOR_LENGTH) {
715         throwOutOfMemoryError(exec, scope);
716         return encodedJSValue();
717     }
718     
719     // OK, we know that if we finish the split, we won't have to OOM.
720     position = savedPosition;
721     matchPosition = savedMatchPosition;
722     
723     genericSplit(
724         vm, regexp, input, inputSize, position, matchPosition, regExpIsSticky, regExpIsUnicode,
725         [&] () -> SplitControl {
726             return ContinueSplit;
727         },
728         [&] (bool isDefined, unsigned start, unsigned length) -> SplitControl {
729             result->putDirectIndex(exec, resultLength++, isDefined ? JSRopeString::createSubstringOfResolved(vm, inputString, start, length) : jsUndefined());
730             RETURN_IF_EXCEPTION(scope, AbortSplit);
731             if (resultLength >= limit)
732                 return AbortSplit;
733             return ContinueSplit;
734         });
735     RETURN_IF_EXCEPTION(scope, encodedJSValue());
736
737     if (resultLength >= limit)
738         return JSValue::encode(result);
739     
740     // 20. Let T be a String value equal to the substring of S consisting of the elements at indices p (inclusive) through size (exclusive).
741     // 21. Perform ! CreateDataProperty(A, ! ToString(lengthA), T).
742     scope.release();
743     result->putDirectIndex(exec, resultLength, JSRopeString::createSubstringOfResolved(vm, inputString, position, inputSize - position));
744     // 22. Return A.
745     return JSValue::encode(result);
746 }
747
748 } // namespace JSC