Bug 202471 – Implement String.prototype.replaceAll

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Mathias Bynens]

The proposal reached stage 3 at today’s TC39 meeting.

Repository: https://github.com/tc39/proposal-string-replaceall

[Radar WebKit Bug Importer]

<rdar://problem/55921557>

[Ross Kirsling]

Created attachment 383727 [details]
Patch

[Ross Kirsling]

Notes:

- This passes all Test262 tests (pending merge here: https://github.com/tc39/test262/pull/2423), except for one that also fails for `replace` itself.

- Instead of adding replaceAllUsingStringSearch, we could alternatively just add to replaceUsingStringSearch, but I was concerned about affecting performance for the existing path.

[Ross Kirsling]

Comment on attachment 383727 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=383727&action=review

> Source/JavaScriptCore/runtime/StringPrototype.cpp:883
> +        if (UNLIKELY(!searchStringLength)) {
> +            if (endOfLastMatch == string.length())
> +                break;
> +            matchStart = string.find(searchString, endOfLastMatch + 1);

It seems really backwards that findCommon has an early out for an empty search string *before* checking whether our start position is out of bounds:
https://github.com/WebKit/webkit/blob/master/Source/WTF/wtf/text/StringCommon.h#L573-L577

I hope to fix this in a separate patch (assuming other code isn't depending on it somehow...)

[Ross Kirsling]

Created attachment 383729 [details]
Patch

[Ross Kirsling]

Created attachment 383797 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 383797 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=383797&action=review

Nice! Some comments.

> Source/JavaScriptCore/builtins/StringPrototype.js:267
> +    if (@isUndefinedOrNull(this))
> +        @throwTypeError("String.prototype.replaceAll requires |this| not to be null nor undefined");

Can you test it?

> Source/JavaScriptCore/builtins/StringPrototype.js:270
> +        if (@isRegExp(search) && !@stringIncludesInternal.@call(@toString(search.flags), "g"))

Can you test the pattern that tells incorrect flag information, like,

class DerivedRegExp extends RegExp {
    constructor(pattern, flags) { super(pattern, flags); }
    get flags() { return "INVALID" };
};

> Source/JavaScriptCore/builtins/StringPrototype.js:271
> +            @throwTypeError("String.prototype.replaceAll argument must not be a non-global regular expression");

Can you test this error?

> Source/JavaScriptCore/builtins/StringPrototype.js:273
> +        let replacer = search.@replaceSymbol;

Use `var` in builtin as much as possible.

> Source/JavaScriptCore/builtins/StringPrototype.js:279
> +    }

Can you test the code when @@replace function is deleted, replaced etc.?

> Source/JavaScriptCore/runtime/StringPrototype.cpp:859
> +            JSValue replacement = call(globalObject, replaceValue, callType, callData, jsUndefined(), args);

Can you make this repeated calling efficient by using CachedCall?

[EWS Watchlist]

Comment on attachment 383797 [details]
Patch

Attachment 383797 [details] did not pass win-ews (win):
Output: https://webkit-queues.webkit.org/results/13265385

New failing tests:
fast/dom/domTokenListIterator.html
fast/dom/nodeListIterator.html
fast/dom/NodeList/nodelist-iterable.html
http/tests/security/cross-frame-access-enumeration.html

[EWS Watchlist]

Created attachment 383827 [details]
Archive of layout-test-results from ews212 for win-future

The attached test failures were seen while running run-webkit-tests on the win-ews.
Bot: ews212  Port: win-future  Platform: CYGWIN_NT-10.0-17763-3.0.5-338.x86_64-x86_64-64bit

[Ross Kirsling]

(In reply to Yusuke Suzuki from comment #7)
> > Source/JavaScriptCore/builtins/StringPrototype.js:270
> > +        if (@isRegExp(search) && !@stringIncludesInternal.@call(@toString(search.flags), "g"))
> 
> Can you test the pattern that tells incorrect flag information, like,
> 
> class DerivedRegExp extends RegExp {
>     constructor(pattern, flags) { super(pattern, flags); }
>     get flags() { return "INVALID" };
> };

But that'll just trigger a runtime SyntaxError when we parse the flags in regExpProtoFuncCompile, before we even manage to call the getter. We can test with objects like these though:

  // bad:
  { [Symbol.match]() {} }

  // good:
  { [Symbol.match]() {}, flags: 'g' }

That's what I did for the same path in String#matchAll, but I'd forgotten to do it here.

[Ross Kirsling]

Created attachment 383841 [details]
Patch

[Ross Kirsling]

Comment on attachment 383841 [details]
Patch

Addressed feedback.

Also switched to modifying replaceUsingStringSearch instead of duplicating it, as this appears to be perf-neutral on JetStream 2 after all.

[Ross Kirsling]

(In reply to Ross Kirsling from comment #10)
> But that'll just trigger a runtime SyntaxError when we parse the flags in
> regExpProtoFuncCompile, before we even manage to call the getter.

Er whoops, I misspoke here -- I meant to say "before we even manage to call stringIncludesInternal".

[EWS Watchlist]

Comment on attachment 383841 [details]
Patch

Attachment 383841 [details] did not pass win-ews (win):
Output: https://webkit-queues.webkit.org/results/13266312

New failing tests:
fast/dom/domTokenListIterator.html
fast/dom/nodeListIterator.html
fast/dom/NodeList/nodelist-iterable.html
http/tests/security/cross-frame-access-enumeration.html

[EWS Watchlist]

Created attachment 383856 [details]
Archive of layout-test-results from ews214 for win-future

The attached test failures were seen while running run-webkit-tests on the win-ews.
Bot: ews214  Port: win-future  Platform: CYGWIN_NT-10.0-17763-3.0.5-338.x86_64-x86_64-64bit

[Yusuke Suzuki]

Comment on attachment 383841 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=383841&action=review

r=me with nits.

> Source/JavaScriptCore/runtime/StringPrototype.cpp:803
> +        if (callType != CallType::None) {

`if (cachedCall)` would be nice since we are using cachedCall in this brace. And this is the same to `callType != CallType::None`.

> Source/JavaScriptCore/runtime/StringPrototype.cpp:823
> +        if (callType != CallType::None) {

`if (cachedCall)` would be clean.

> Source/JavaScriptCore/runtime/StringPrototype.cpp:842
> +    RELEASE_AND_RETURN(scope, jsSpliceSubstringsWithSeparators(globalObject, jsString, string, sourceRanges.data(), sourceRanges.size(), replacements.data(), replacements.size()));

Previously, we are calling `jsString()` with three substrings. But now, jsSpliceSubstringsWithSeparators is allocating a new String buffer for this case (`!isGlobal`) case.
Is it efficient in terms of memory? Should we do this in jsSpliceSubstringsWithSeparators?

[Ross Kirsling]

Created attachment 383940 [details]
Patch for landing

[WebKit Commit Bot]

The commit-queue encountered the following flaky tests while processing attachment 383940 [details]:

compositing/backing/backing-store-attachment-with-rotation.html bug 204394 (author: [e-mail])
The commit-queue is continuing to process your patch.

[WebKit Commit Bot]

Comment on attachment 383940 [details]
Patch for landing

Clearing flags on attachment: 383940

Committed r252683: <https://trac.webkit.org/changeset/252683>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Darin Adler]

Comment on attachment 383940 [details]
Patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=383940&action=review

> Source/JavaScriptCore/runtime/StringPrototype.cpp:779
> +static ALWAYS_INLINE JSString* replaceUsingStringSearch(VM& vm, JSGlobalObject* globalObject, CallFrame* callFrame, JSString* jsString, JSValue searchValue, JSValue replaceValue, bool isGlobal)

We normally use enumerations for arguments like this "isGlobal" one rather than using named constants at the call site.

> Source/JavaScriptCore/runtime/StringPrototype.cpp:807
> +    Vector<StringRange, 16> sourceRanges;
> +    Vector<String, 16> replacements;

This approach looks very different. Do we have performance test coverage?

> Source/JavaScriptCore/runtime/StringPrototype.cpp:817
> +            if (UNLIKELY(cachedCall->hasOverflowedArguments()))
> +                OUT_OF_MEMORY(globalObject, scope);

I don’t think this is needed when appending exactly 3 arguments. Maybe this was copied and pasted from code that appends arbitrary numbers of arguments, where it would be needed. Or did I miss something?

> Source/JavaScriptCore/runtime/StringPrototype.cpp:819
> +            RETURN_IF_EXCEPTION(scope, nullptr);

What operation makes this RETURN_IF_EXCEPTION needed? I don’t see anything above that can result in an exception. Or did I miss something?

> Source/JavaScriptCore/runtime/StringPrototype.cpp:828
> +        int ovector[2] = { static_cast<int>(matchStart),  static_cast<int>(matchEnd)};

Not new code, just moved: Formatting mistake here. Missing space before "}".

I think this should be moved inside else block just below.

> Source/JavaScriptCore/runtime/StringPrototype.cpp:831
> +            RETURN_IF_EXCEPTION(scope, nullptr);

What operation makes this RETURN_IF_EXCEPTION needed? I don’t see anything above that can result in an exception. Or did I miss something?

> Source/JavaScriptCore/runtime/StringPrototype.cpp:843
> +        matchStart = string.find(searchString, UNLIKELY(!searchStringLength) ? endOfLastMatch + 1 : endOfLastMatch);

Seems unnecessary to use this UNLIKELY here. Premature optimization perhaps.

I don’t understand the searchStringLength 0 case. I don’t see a test case covering this.

> Source/WTF/wtf/text/StringCommon.h:574
> +    if (start > haystack.length())
> +        return notFound;

This is a subtle change in behavior, and this helper is used in many places. How did you test that this is safe across all use of this in WebKit?

> Source/WTF/wtf/text/StringCommon.h:577
>      if (!needleLength)
>          return std::min(start, haystack.length());

This can now be simplified to just:

    if (!needleLength)
        return start;

Would be nice to do that.

[Ross Kirsling]

(In reply to Darin Adler from comment #21)
> > Source/JavaScriptCore/runtime/StringPrototype.cpp:779
> > +static ALWAYS_INLINE JSString* replaceUsingStringSearch(VM& vm, JSGlobalObject* globalObject, CallFrame* callFrame, JSString* jsString, JSValue searchValue, JSValue replaceValue, bool isGlobal)
> 
> We normally use enumerations for arguments like this "isGlobal" one rather
> than using named constants at the call site.

Can do.

> > Source/JavaScriptCore/runtime/StringPrototype.cpp:807
> > +    Vector<StringRange, 16> sourceRanges;
> > +    Vector<String, 16> replacements;
> 
> This approach looks very different. Do we have performance test coverage?

All the changes to this function are effectively aligning the replace('foo', ...) path with the replace(/foo/, ...) path (i.e. replaceUsingRegExpSearch with !global).

I was certainly worried about this affecting performance at first (comment 3), but JetStream 2 results appeared to be neutral (comment 12).

This should hopefully be confirmable by perf bots since this patch landed, but unfortunately I don't think they're externally visible right now(?).

> > Source/JavaScriptCore/runtime/StringPrototype.cpp:817
> > +            if (UNLIKELY(cachedCall->hasOverflowedArguments()))
> > +                OUT_OF_MEMORY(globalObject, scope);
> 
> I don’t think this is needed when appending exactly 3 arguments. Maybe this
> was copied and pasted from code that appends arbitrary numbers of arguments,
> where it would be needed. Or did I miss something?

Good point, given that this was an ASSERT before, it ought to still be one now.

> > Source/JavaScriptCore/runtime/StringPrototype.cpp:819
> > +            RETURN_IF_EXCEPTION(scope, nullptr);
> 
> What operation makes this RETURN_IF_EXCEPTION needed? I don’t see anything
> above that can result in an exception. Or did I miss something?

It's true that it wasn't here before, but it is an arbitrary function call, so I figured it had just been missing?

> > Source/JavaScriptCore/runtime/StringPrototype.cpp:828
> > +        int ovector[2] = { static_cast<int>(matchStart),  static_cast<int>(matchEnd)};
> 
> Not new code, just moved: Formatting mistake here. Missing space before "}".
> 
> I think this should be moved inside else block just below.

Indeed.

> > Source/JavaScriptCore/runtime/StringPrototype.cpp:831
> > +            RETURN_IF_EXCEPTION(scope, nullptr);
> 
> What operation makes this RETURN_IF_EXCEPTION needed? I don’t see anything
> above that can result in an exception. Or did I miss something?

Hmm, yeah, this one does seem like overkill.

> > Source/JavaScriptCore/runtime/StringPrototype.cpp:843
> > +        matchStart = string.find(searchString, UNLIKELY(!searchStringLength) ? endOfLastMatch + 1 : endOfLastMatch);
> 
> Seems unnecessary to use this UNLIKELY here. Premature optimization perhaps.

I went with it and figured I'd see if somebody complained. :) I can certainly reverse it.

> I don’t understand the searchStringLength 0 case. I don’t see a test case
> covering this.

Right, I should add one. The point is that replacing '' with 'z' in 'abc' should produce 'zazbzcz', but if we don't shove the start position over manually, we'll just keep inserting 'z' in place until we run out of memory.

> > Source/WTF/wtf/text/StringCommon.h:574
> > +    if (start > haystack.length())
> > +        return notFound;
> 
> This is a subtle change in behavior, and this helper is used in many places.
> How did you test that this is safe across all use of this in WebKit?

I originally planned to do this in a follow-up patch because I expected some degree of breakage (obsoleted comment 4), but was surprised to encounter none whatsoever.

I would hope that nobody is *silently* depending on this in untested behavior, but my hypothesis is that because of the unexpectedness of the existing logic, any callsite where this would be an issue was likely already guarding for it.

> > Source/WTF/wtf/text/StringCommon.h:577
> >      if (!needleLength)
> >          return std::min(start, haystack.length());
> 
> This can now be simplified to just:
> 
>     if (!needleLength)
>         return start;
> 
> Would be nice to do that.

Oops, thanks!

[Ross Kirsling]

Committed r252721: <https://trac.webkit.org/changeset/252721>

[Maciej Stachowiak]

This probably should have had a feature flag.

[Ross Kirsling]

(In reply to Maciej Stachowiak from comment #24)
> This probably should have had a feature flag.

I wasn't quite sure, since it seems like we've tended not to do so for new built-in methods (like String#matchAll or Promise.allSettled).

[WebKit Commit Bot]

Re-opened since this is blocked by bug 204475

[Ross Kirsling]

I guess the bots have spoken after all. I'll switch back to the duplicated approach.

[Yusuke Suzuki]

(In reply to WebKit Commit Bot from comment #26)
> Re-opened since this is blocked by bug 204475

Ooooooops, I was completely wrong. This regression is caused by r252684, not by r252683. I'm now manually re-landing.

[Yusuke Suzuki]

Committed r252754: <https://trac.webkit.org/changeset/252754>