Faster string.replace with regexp pattern.

String.replace implemented in C++.

[Lasse Reichstein, 2009-03-12 09:06:30]

Review, please.

[Erik Corry, 2009-03-12 10:13:00]

http://codereview.chromium.org/42115/diff/1/5
File src/objects-inl.h (right):

http://codereview.chromium.org/42115/diff/1/5#newcode2321
Line 2321: case ATOM: return 0;
Indentation is wrong here.

http://codereview.chromium.org/42115/diff/1/8
File src/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/42115/diff/1/8#newcode994
Line 994: String* subject_ptr = *subject;
Please add an AssertNoAllocation object here.

http://codereview.chromium.org/42115/diff/1/10
File src/runtime.cc (right):

http://codereview.chromium.org/42115/diff/1/10#newcode1183
Line 1183: class ReplacementStringBuilder {
I think you should use StringBuilderConcatHelper instead of Cons Strings.

http://codereview.chromium.org/42115/diff/1/10#newcode1215
Line 1215: ParseReplacement(replacement, capture_count);
Nontrivial work shouldn't be in constructors.

http://codereview.chromium.org/42115/diff/1/10#newcode1238
Line 1238: FixedArray* match_info = last_match_info->elements();
Move outside loop?  Actually, you should move this outside the function
completely so you can get it outside the /g loop.

http://codereview.chromium.org/42115/diff/1/10#newcode1254
Line 1254: SUBJECT_MATCH = -1,
Subject match seems like a special case of subject capture.

http://codereview.chromium.org/42115/diff/1/10#newcode1258
Line 1258: REPLACEMENT_SUBSTRING = -5
I'd prefer these to be positive and the offsets negative.  That way the switch
is with positive values which seems like the more common case for the C++
compiler implementer.

http://codereview.chromium.org/42115/diff/1/10#newcode1267
Line 1267: int data;
'data' is too generic a name, there's no comment to explain what it's for.

http://codereview.chromium.org/42115/diff/1/10#newcode1297
Line 1297: parts->Add(ReplacementPart(last, i));
Perhaps parts->Add could check for last == i to save you doing it in 4 out of 5
places.

http://codereview.chromium.org/42115/diff/1/10#newcode1319
Line 1319: case '0':
Are $0 and $04 allowed?  Should $0 be taken verbatim?

http://codereview.chromium.org/42115/diff/1/10#newcode1356
Line 1356: default:
Should $F00 replace with $FOO or FOO?

http://codereview.chromium.org/42115/diff/1/10#newcode1435
Line 1435: FixedArray* match_data = last_match_info_handle->elements();
Not using a handle is a little dodgy.  If you move this outside the loop you
don't have to worry about the Handle copying overhead.

http://codereview.chromium.org/42115/diff/1/10#newcode1504
Line 1504: CONVERT_CHECKED(JSArray, last_match_info, args[3]);
You need to check here that the last_match_info has fast elements and you need
to check that is is big enough somewhere.

http://codereview.chromium.org/42115/diff/1/12
File src/string.js (right):

http://codereview.chromium.org/42115/diff/1/12#newcode239
Line 239: var reusableMatchInfo = [2, -1, -1, "", ""];
Do we still need both of these?

http://codereview.chromium.org/42115/diff/1/12#newcode254
Line 254: // the result.
Do we still need this?

[Lasse Reichstein, 2009-03-13 08:36:51]

Addressed review comments, with significant changes.
Please rereview.

http://codereview.chromium.org/42115/diff/1/5
File src/objects-inl.h (right):

http://codereview.chromium.org/42115/diff/1/5#newcode2321
Line 2321: case ATOM: return 0;
On 2009/03/12 10:13:00, Erik Corry wrote:
> Indentation is wrong here.

Done.

http://codereview.chromium.org/42115/diff/1/8
File src/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/42115/diff/1/8#newcode994
Line 994: String* subject_ptr = *subject;
Rewritten to use handles everywhere.

http://codereview.chromium.org/42115/diff/1/10
File src/runtime.cc (right):

http://codereview.chromium.org/42115/diff/1/10#newcode1183
Line 1183: class ReplacementStringBuilder {
On 2009/03/12 10:13:00, Erik Corry wrote:
> I think you should use StringBuilderConcatHelper instead of Cons Strings.

Done.

http://codereview.chromium.org/42115/diff/1/10#newcode1215
Line 1215: ParseReplacement(replacement, capture_count);
On 2009/03/12 10:13:00, Erik Corry wrote:
> Nontrivial work shouldn't be in constructors.

Done.

http://codereview.chromium.org/42115/diff/1/10#newcode1238
Line 1238: FixedArray* match_info = last_match_info->elements();
As commented later, it can't be moved that far out.
It could be moved out of this loop, but then it would be computed even when it's
not used (e.g., replacing with a constant string).

http://codereview.chromium.org/42115/diff/1/10#newcode1254
Line 1254: SUBJECT_MATCH = -1,
True. Slightly faster to implement since I already have the match start and end
indices computed. Probably not worth it. I'll remove it for now.

http://codereview.chromium.org/42115/diff/1/10#newcode1258
Line 1258: REPLACEMENT_SUBSTRING = -5
On 2009/03/12 10:13:00, Erik Corry wrote:
> I'd prefer these to be positive and the offsets negative.  That way the
switch
> is with positive values which seems like the more common case for the C++
> compiler implementer.

Done.

http://codereview.chromium.org/42115/diff/1/10#newcode1267
Line 1267: int data;
Comments added.

http://codereview.chromium.org/42115/diff/1/10#newcode1297
Line 1297: parts->Add(ReplacementPart(last, i));
Parts is just a ZoneList, and this is a self-contained static function, so I
don't think the overhead of moving those tests somewhere else is worth it.

http://codereview.chromium.org/42115/diff/1/10#newcode1319
Line 1319: case '0':
Yes and yes.

http://codereview.chromium.org/42115/diff/1/10#newcode1356
Line 1356: default:
With "$F00".

http://codereview.chromium.org/42115/diff/1/10#newcode1435
Line 1435: FixedArray* match_data = last_match_info_handle->elements();
Won't work. The loop might be preempted (since it calls RegExps) and some other
code might extend the last_match_info array, so it's not safe to retain a
reference to the current backing FixedArray. We need to extract it on every
iteration.

To avoid creating a handle for every iteration, I just extract the pointer and
use it immediately.

http://codereview.chromium.org/42115/diff/1/10#newcode1504
Line 1504: CONVERT_CHECKED(JSArray, last_match_info, args[3]);
I only ever use last_match_info after having executed a regular expression
successfully. That should ensure the size as well as check that the array has
fast elements.
But yes, failing fast is a good thing, so I'll add an extra test here.

http://codereview.chromium.org/42115/diff/1/12
File src/string.js (right):

http://codereview.chromium.org/42115/diff/1/12#newcode239
Line 239: var reusableMatchInfo = [2, -1, -1, "", ""];
No, well spotted, the reusabeMatchArray isn't used any more.

http://codereview.chromium.org/42115/diff/1/12#newcode254
Line 254: // the result.
Sadly, yes. Replacing with a string pattern, instead of a RegExp, is still in
Javascript (using indexOf), and it uses this for replacement.

[Erik Corry, 2009-03-13 09:12:34]

LGTM if it lints, passes tests and compiles on ARM.

http://codereview.chromium.org/42115/diff/1/10
File src/runtime.cc (right):

http://codereview.chromium.org/42115/diff/1/10#newcode1435
Line 1435: FixedArray* match_data = last_match_info_handle->elements();
On 2009/03/13 08:36:51, Lasse Reichstein wrote:
> Won't work. The loop might be preempted (since it calls RegExps) and some
other
> code might extend the last_match_info array, so it's not safe to retain a
> reference to the current backing FixedArray. We need to extract it on every
> iteration.

If you retain a reference to the old FixedArray then it will not be collected
and you can write your captures to it.  The static properties on RegExp will not
reflect your changes but if you are using regexps in multiple threads that is
not unexpected.  But we can save that for another afsnit.

> 
> To avoid creating a handle for every iteration, I just extract the pointer and
> use it immediately.

http://codereview.chromium.org/42115/diff/1/12
File src/string.js (right):

http://codereview.chromium.org/42115/diff/1/12#newcode254
Line 254: // the result.
On 2009/03/13 08:36:51, Lasse Reichstein wrote:
> Sadly, yes. Replacing with a string pattern, instead of a RegExp, is still in
> Javascript (using indexOf), and it uses this for replacement.

But knowing that number of captures is always zero should permit simplifications
here.

http://codereview.chromium.org/42115/diff/17/26
File src/runtime.cc (right):

http://codereview.chromium.org/42115/diff/17/26#newcode1207
Line 1207: if (length < (1 << 11) && from < (1 << 19)) {
Not your fault (it's mine :-) but 11 and 19 should be named constants.

http://codereview.chromium.org/42115/diff/17/26#newcode1211
Line 1211: Handle<String> slice = Factory::NewStringSlice(subject_, from, to);
Do we have test coverage of this branch?

http://codereview.chromium.org/42115/diff/17/26#newcode1309
Line 1309: void Compile(Handle<String> replacement,
This method is (way!) too big to be inline in the class declaration.

http://codereview.chromium.org/42115/diff/17/26#newcode1351
Line 1351: void Apply(ReplacementStringBuilder* builder,
Ditto.

http://codereview.chromium.org/42115/diff/17/26#newcode1590
Line 1590: // Guessing the number of parts that the final result string is build
built

[Lasse Reichstein, 2011-06-14 11:51:17]

http://codereview.chromium.org/42115/diff/1/src/string.js
File src/string.js (right):

http://codereview.chromium.org/42115/diff/1/src/string.js#newcode254
src/string.js:254: // the result.
True. I'll leave it as-is for now, expecting that we will want to move
string.replace(string,string) to C++ and remove it completely.

http://codereview.chromium.org/42115/diff/17/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/42115/diff/17/src/runtime.cc#newcode1207
src/runtime.cc:1207: if (length < (1 << 11) && from < (1 << 19)) {
Fixed to use BitField<int,0,11> and BitField<int,11,19>.

http://codereview.chromium.org/42115/diff/17/src/runtime.cc#newcode1211
src/runtime.cc:1211: Handle<String> slice = Factory::NewStringSlice(subject_,
from, to);
Probably not. Lets make sure.
Some extra string.replace-tests added.

http://codereview.chromium.org/42115/diff/17/src/runtime.cc#newcode1309
src/runtime.cc:1309: void Compile(Handle<String> replacement,
Refactored outside. Just after, but outside.

http://codereview.chromium.org/42115/diff/17/src/runtime.cc#newcode1351
src/runtime.cc:1351: void Apply(ReplacementStringBuilder* builder,
On 2009/03/13 09:12:34, Erik Corry wrote:
> Ditto.

Done.

http://codereview.chromium.org/42115/diff/17/src/runtime.cc#newcode1590
src/runtime.cc:1590: // Guessing the number of parts that the final result
string is build
On 2009/03/13 09:12:34, Erik Corry wrote:
> built

Done.