Unreviewed, rolling out r221327.
[WebKit-https.git] / Source / JavaScriptCore / builtins / RegExpPrototype.js
1 /*
2  * Copyright (C) 2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 @globalPrivate
27 function advanceStringIndex(string, index, unicode)
28 {
29     // This function implements AdvanceStringIndex described in ES6 21.2.5.2.3.
30     "use strict";
31
32     if (!unicode)
33         return index + 1;
34
35     if (index + 1 >= string.length)
36         return index + 1;
37
38     let first = string.@charCodeAt(index);
39     if (first < 0xD800 || first > 0xDBFF)
40         return index + 1;
41
42     let second = string.@charCodeAt(index + 1);
43     if (second < 0xDC00 || second > 0xDFFF)
44         return index + 1;
45
46     return index + 2;
47 }
48
49 @globalPrivate
50 function regExpExec(regexp, str)
51 {
52     "use strict";
53
54     let exec = regexp.exec;
55     let builtinExec = @regExpBuiltinExec;
56     if (exec !== builtinExec && typeof exec === "function") {
57         let result = exec.@call(regexp, str);
58         if (result !== null && !@isObject(result))
59             @throwTypeError("The result of a RegExp exec must be null or an object");
60         return result;
61     }
62     return builtinExec.@call(regexp, str);
63 }
64
65 @globalPrivate
66 function hasObservableSideEffectsForRegExpMatch(regexp) {
67     // This is accessed by the RegExpExec internal function.
68     let regexpExec = @tryGetById(regexp, "exec");
69     if (regexpExec !== @regExpBuiltinExec)
70         return true;
71
72     let regexpGlobal = @tryGetById(regexp, "global");
73     if (regexpGlobal !== @regExpProtoGlobalGetter)
74         return true;
75     let regexpUnicode = @tryGetById(regexp, "unicode");
76     if (regexpUnicode !== @regExpProtoUnicodeGetter)
77         return true;
78
79     return !@isRegExpObject(regexp);
80 }
81
82 function match(strArg)
83 {
84     "use strict";
85
86     if (!@isObject(this))
87         @throwTypeError("RegExp.prototype.@@match requires that |this| be an Object");
88
89     let regexp = this;
90
91     // Check for observable side effects and call the fast path if there aren't any.
92     if (!@hasObservableSideEffectsForRegExpMatch(regexp))
93         return @regExpMatchFast.@call(regexp, strArg);
94
95     let str = @toString(strArg);
96
97     if (!regexp.global)
98         return @regExpExec(regexp, str);
99     
100     let unicode = regexp.unicode;
101     regexp.lastIndex = 0;
102     let resultList = [];
103
104     // FIXME: It would be great to implement a solution similar to what we do in
105     // RegExpObject::matchGlobal(). It's not clear if this is possible, since this loop has
106     // effects. https://bugs.webkit.org/show_bug.cgi?id=158145
107     const maximumReasonableMatchSize = 100000000;
108
109     while (true) {
110         let result = @regExpExec(regexp, str);
111         
112         if (result === null) {
113             if (resultList.length === 0)
114                 return null;
115             return resultList;
116         }
117
118         if (resultList.length > maximumReasonableMatchSize)
119             @throwOutOfMemoryError();
120
121         if (!@isObject(result))
122             @throwTypeError("RegExp.prototype.@@match call to RegExp.exec didn't return null or an object");
123
124         let resultString = @toString(result[0]);
125
126         if (!resultString.length)
127             regexp.lastIndex = @advanceStringIndex(str, regexp.lastIndex, unicode);
128
129         resultList.@push(resultString);
130     }
131 }
132
133 function replace(strArg, replace)
134 {
135     "use strict";
136
137     function getSubstitution(matched, str, position, captures, replacement)
138     {
139         "use strict";
140
141         let matchLength = matched.length;
142         let stringLength = str.length;
143         let tailPos = position + matchLength;
144         let m = captures.length;
145         let replacementLength = replacement.length;
146         let result = "";
147         let lastStart = 0;
148
149         for (let start = 0; start = replacement.indexOf("$", lastStart), start !== -1; lastStart = start) {
150             if (start - lastStart > 0)
151                 result = result + replacement.substring(lastStart, start);
152             start++;
153             let ch = replacement.charAt(start);
154             if (ch === "")
155                 result = result + "$";
156             else {
157                 switch (ch)
158                 {
159                 case "$":
160                     result = result + "$";
161                     start++;
162                     break;
163                 case "&":
164                     result = result + matched;
165                     start++;
166                     break;
167                 case "`":
168                     if (position > 0)
169                         result = result + str.substring(0, position);
170                     start++;
171                     break;
172                 case "'":
173                     if (tailPos < stringLength)
174                         result = result + str.substring(tailPos);
175                     start++;
176                     break;
177                 default:
178                     let chCode = ch.charCodeAt(0);
179                     if (chCode >= 0x30 && chCode <= 0x39) {
180                         start++;
181                         let n = chCode - 0x30;
182                         if (n > m)
183                             break;
184                         if (start < replacementLength) {
185                             let nextChCode = replacement.charCodeAt(start);
186                             if (nextChCode >= 0x30 && nextChCode <= 0x39) {
187                                 let nn = 10 * n + nextChCode - 0x30;
188                                 if (nn <= m) {
189                                     n = nn;
190                                     start++;
191                                 }
192                             }
193                         }
194
195                         if (n == 0)
196                             break;
197
198                         if (captures[n] != @undefined)
199                             result = result + captures[n];
200                     } else
201                         result = result + "$";
202                     break;
203                 }
204             }
205         }
206
207         return result + replacement.substring(lastStart);
208     }
209
210     if (!@isObject(this))
211         @throwTypeError("RegExp.prototype.@@replace requires that |this| be an Object");
212
213     let regexp = this;
214
215     let str = @toString(strArg);
216     let stringLength = str.length;
217     let functionalReplace = typeof replace === 'function';
218
219     if (!functionalReplace)
220         replace = @toString(replace);
221
222     let global = regexp.global;
223     let unicode = false;
224
225     if (global) {
226         unicode = regexp.unicode;
227         regexp.lastIndex = 0;
228     }
229
230     let resultList = [];
231     let result;
232     let done = false;
233     while (!done) {
234         result = @regExpExec(regexp, str);
235
236         if (result === null)
237             done = true;
238         else {
239             resultList.@push(result);
240             if (!global)
241                 done = true;
242             else {
243                 let matchStr = @toString(result[0]);
244
245                 if (!matchStr.length)
246                     regexp.lastIndex = @advanceStringIndex(str, regexp.lastIndex, unicode);
247             }
248         }
249     }
250
251     let accumulatedResult = "";
252     let nextSourcePosition = 0;
253     let lastPosition = 0;
254
255     for (let i = 0, resultListLength = resultList.length; i < resultListLength; ++i) {
256         let result = resultList[i];
257         let nCaptures = result.length - 1;
258         if (nCaptures < 0)
259             nCaptures = 0;
260         let matched = @toString(result[0]);
261         let matchLength = matched.length;
262         let position = result.index;
263         position = (position > stringLength) ? stringLength : position;
264         position = (position < 0) ? 0 : position;
265
266         let captures = [];
267         for (let n = 1; n <= nCaptures; n++) {
268             let capN = result[n];
269             if (capN !== @undefined)
270                 capN = @toString(capN);
271             captures[n] = capN;
272         }
273
274         let replacement;
275
276         if (functionalReplace) {
277             let replacerArgs = [ matched ].concat(captures.slice(1));
278             replacerArgs.@push(position);
279             replacerArgs.@push(str);
280
281             let replValue = replace.@apply(@undefined, replacerArgs);
282             replacement = @toString(replValue);
283         } else
284             replacement = getSubstitution(matched, str, position, captures, replace);
285
286         if (position >= nextSourcePosition && position >= lastPosition) {
287             accumulatedResult = accumulatedResult + str.substring(nextSourcePosition, position) + replacement;
288             nextSourcePosition = position + matchLength;
289             lastPosition = position;
290         }
291     }
292
293     if (nextSourcePosition >= stringLength)
294         return  accumulatedResult;
295
296     return accumulatedResult + str.substring(nextSourcePosition);
297 }
298
299 // 21.2.5.9 RegExp.prototype[@@search] (string)
300 function search(strArg)
301 {
302     "use strict";
303
304     let regexp = this;
305
306     // Check for observable side effects and call the fast path if there aren't any.
307     if (@isRegExpObject(regexp) && @tryGetById(regexp, "exec") === @regExpBuiltinExec)
308         return @regExpSearchFast.@call(regexp, strArg);
309
310     // 1. Let rx be the this value.
311     // 2. If Type(rx) is not Object, throw a TypeError exception.
312     if (!@isObject(this))
313         @throwTypeError("RegExp.prototype.@@search requires that |this| be an Object");
314
315     // 3. Let S be ? ToString(string).
316     let str = @toString(strArg)
317
318     // 4. Let previousLastIndex be ? Get(rx, "lastIndex").
319     let previousLastIndex = regexp.lastIndex;
320
321     // 5.If SameValue(previousLastIndex, 0) is false, then
322     // 5.a. Perform ? Set(rx, "lastIndex", 0, true).
323     // FIXME: Add SameValue support. https://bugs.webkit.org/show_bug.cgi?id=173226
324     if (previousLastIndex !== 0)
325         regexp.lastIndex = 0;
326
327     // 6. Let result be ? RegExpExec(rx, S).
328     let result = @regExpExec(regexp, str);
329
330     // 7. Let currentLastIndex be ? Get(rx, "lastIndex").
331     // 8. If SameValue(currentLastIndex, previousLastIndex) is false, then
332     // 8.a. Perform ? Set(rx, "lastIndex", previousLastIndex, true).
333     // FIXME: Add SameValue support. https://bugs.webkit.org/show_bug.cgi?id=173226
334     if (regexp.lastIndex !== previousLastIndex)
335         regexp.lastIndex = previousLastIndex;
336
337     // 9. If result is null, return -1.
338     if (result === null)
339         return -1;
340
341     // 10. Return ? Get(result, "index").
342     return result.index;
343 }
344
345 @globalPrivate
346 function hasObservableSideEffectsForRegExpSplit(regexp) {
347     // This is accessed by the RegExpExec internal function.
348     let regexpExec = @tryGetById(regexp, "exec");
349     if (regexpExec !== @regExpBuiltinExec)
350         return true;
351     
352     // This is accessed by step 5 below.
353     let regexpFlags = @tryGetById(regexp, "flags");
354     if (regexpFlags !== @regExpProtoFlagsGetter)
355         return true;
356     
357     // These are accessed by the builtin flags getter.
358     let regexpGlobal = @tryGetById(regexp, "global");
359     if (regexpGlobal !== @regExpProtoGlobalGetter)
360         return true;
361     let regexpIgnoreCase = @tryGetById(regexp, "ignoreCase");
362     if (regexpIgnoreCase !== @regExpProtoIgnoreCaseGetter)
363         return true;
364     let regexpMultiline = @tryGetById(regexp, "multiline");
365     if (regexpMultiline !== @regExpProtoMultilineGetter)
366         return true;
367     let regexpSticky = @tryGetById(regexp, "sticky");
368     if (regexpSticky !== @regExpProtoStickyGetter)
369         return true;
370     let regexpUnicode = @tryGetById(regexp, "unicode");
371     if (regexpUnicode !== @regExpProtoUnicodeGetter)
372         return true;
373     
374     // This is accessed by the RegExp species constructor.
375     let regexpSource = @tryGetById(regexp, "source");
376     if (regexpSource !== @regExpProtoSourceGetter)
377         return true;
378     
379     return !@isRegExpObject(regexp);
380 }
381
382 // ES 21.2.5.11 RegExp.prototype[@@split](string, limit)
383 function split(string, limit)
384 {
385     "use strict";
386
387     // 1. Let rx be the this value.
388     // 2. If Type(rx) is not Object, throw a TypeError exception.
389     if (!@isObject(this))
390         @throwTypeError("RegExp.prototype.@@split requires that |this| be an Object");
391     let regexp = this;
392
393     // 3. Let S be ? ToString(string).
394     let str = @toString(string);
395
396     // 4. Let C be ? SpeciesConstructor(rx, %RegExp%).
397     let speciesConstructor = @speciesConstructor(regexp, @RegExp);
398
399     if (speciesConstructor === @RegExp && !@hasObservableSideEffectsForRegExpSplit(regexp))
400         return @regExpSplitFast.@call(regexp, str, limit);
401
402     // 5. Let flags be ? ToString(? Get(rx, "flags")).
403     let flags = @toString(regexp.flags);
404
405     // 6. If flags contains "u", let unicodeMatching be true.
406     // 7. Else, let unicodeMatching be false.
407     let unicodeMatching = @stringIncludesInternal.@call(flags, "u");
408     // 8. If flags contains "y", let newFlags be flags.
409     // 9. Else, let newFlags be the string that is the concatenation of flags and "y".
410     let newFlags = @stringIncludesInternal.@call(flags, "y") ? flags : flags + "y";
411
412     // 10. Let splitter be ? Construct(C, « rx, newFlags »).
413     let splitter = new speciesConstructor(regexp, newFlags);
414
415     // We need to check again for RegExp subclasses that will fail the speciesConstructor test
416     // but can still use the fast path after we invoke the constructor above.
417     if (!@hasObservableSideEffectsForRegExpSplit(splitter))
418         return @regExpSplitFast.@call(splitter, str, limit);
419
420     // 11. Let A be ArrayCreate(0).
421     // 12. Let lengthA be 0.
422     let result = [];
423
424     // 13. If limit is undefined, let lim be 2^32-1; else let lim be ? ToUint32(limit).
425     limit = (limit === @undefined) ? 0xffffffff : limit >>> 0;
426
427     // 16. If lim = 0, return A.
428     if (!limit)
429         return result;
430
431     // 14. [Defered from above] Let size be the number of elements in S.
432     let size = str.length;
433
434     // 17. If size = 0, then
435     if (!size) {
436         // a. Let z be ? RegExpExec(splitter, S).
437         let z = @regExpExec(splitter, str);
438         // b. If z is not null, return A.
439         if (z != null)
440             return result;
441         // c. Perform ! CreateDataProperty(A, "0", S).
442         @putByValDirect(result, 0, str);
443         // d. Return A.
444         return result;
445     }
446
447     // 15. [Defered from above] Let p be 0.
448     let position = 0;
449     // 18. Let q be p.
450     let matchPosition = 0;
451
452     // 19. Repeat, while q < size
453     while (matchPosition < size) {
454         // a. Perform ? Set(splitter, "lastIndex", q, true).
455         splitter.lastIndex = matchPosition;
456         // b. Let z be ? RegExpExec(splitter, S).
457         let matches = @regExpExec(splitter, str);
458         // c. If z is null, let q be AdvanceStringIndex(S, q, unicodeMatching).
459         if (matches === null)
460             matchPosition = @advanceStringIndex(str, matchPosition, unicodeMatching);
461         // d. Else z is not null,
462         else {
463             // i. Let e be ? ToLength(? Get(splitter, "lastIndex")).
464             let endPosition = @toLength(splitter.lastIndex);
465             // ii. Let e be min(e, size).
466             endPosition = (endPosition <= size) ? endPosition : size;
467             // iii. If e = p, let q be AdvanceStringIndex(S, q, unicodeMatching).
468             if (endPosition === position)
469                 matchPosition = @advanceStringIndex(str, matchPosition, unicodeMatching);
470             // iv. Else e != p,
471             else {
472                 // 1. Let T be a String value equal to the substring of S consisting of the elements at indices p (inclusive) through q (exclusive).
473                 let subStr = @stringSubstrInternal.@call(str, position, matchPosition - position);
474                 // 2. Perform ! CreateDataProperty(A, ! ToString(lengthA), T).
475                 // 3. Let lengthA be lengthA + 1.
476                 @putByValDirect(result, result.length, subStr);
477                 // 4. If lengthA = lim, return A.
478                 if (result.length == limit)
479                     return result;
480
481                 // 5. Let p be e.
482                 position = endPosition;
483                 // 6. Let numberOfCaptures be ? ToLength(? Get(z, "length")).
484                 // 7. Let numberOfCaptures be max(numberOfCaptures-1, 0).
485                 let numberOfCaptures = matches.length > 1 ? matches.length - 1 : 0;
486
487                 // 8. Let i be 1.
488                 let i = 1;
489                 // 9. Repeat, while i <= numberOfCaptures,
490                 while (i <= numberOfCaptures) {
491                     // a. Let nextCapture be ? Get(z, ! ToString(i)).
492                     let nextCapture = matches[i];
493                     // b. Perform ! CreateDataProperty(A, ! ToString(lengthA), nextCapture).
494                     // d. Let lengthA be lengthA + 1.
495                     @putByValDirect(result, result.length, nextCapture);
496                     // e. If lengthA = lim, return A.
497                     if (result.length == limit)
498                         return result;
499                     // c. Let i be i + 1.
500                     i++;
501                 }
502                 // 10. Let q be p.
503                 matchPosition = position;
504             }
505         }
506     }
507     // 20. Let T be a String value equal to the substring of S consisting of the elements at indices p (inclusive) through size (exclusive).
508     let remainingStr = @stringSubstrInternal.@call(str, position, size);
509     // 21. Perform ! CreateDataProperty(A, ! ToString(lengthA), T).
510     @putByValDirect(result, result.length, remainingStr);
511     // 22. Return A.
512     return result;
513 }
514
515 // ES 21.2.5.13 RegExp.prototype.test(string)
516 @intrinsic=RegExpTestIntrinsic
517 function test(strArg)
518 {
519     "use strict";
520
521     let regexp = this;
522
523     // Check for observable side effects and call the fast path if there aren't any.
524     if (@isRegExpObject(regexp) && @tryGetById(regexp, "exec") === @regExpBuiltinExec)
525         return @regExpTestFast.@call(regexp, strArg);
526
527     // 1. Let R be the this value.
528     // 2. If Type(R) is not Object, throw a TypeError exception.
529     if (!@isObject(regexp))
530         @throwTypeError("RegExp.prototype.test requires that |this| be an Object");
531
532     // 3. Let string be ? ToString(S).
533     let str = @toString(strArg);
534
535     // 4. Let match be ? RegExpExec(R, string).
536     let match = @regExpExec(regexp, str);
537
538     // 5. If match is not null, return true; else return false.
539     if (match !== null)
540         return true;
541     return false;
542 }