Google GitGoogle Git
Sign in
chromium/v8/v8.git/main/./src/runtime/runtime-regexp.cc
blob: 2a1ba0758cba214b408468a5159871fb98df3ca6 [file]
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <functional>
#include <type_traits>
#include "hwy/highway.h"
#include "src/base/small-vector.h"
#include "src/base/strings.h"
#include "src/common/message-template.h"
#include "src/execution/arguments-inl.h"
#include "src/execution/isolate-inl.h"
#include "src/logging/counters.h"
#include "src/numbers/conversions-inl.h"
#include "src/objects/js-array-inl.h"
#include "src/objects/js-regexp-inl.h"
#include "src/objects/object-conversions-inl.h"
#include "src/regexp/regexp-utils.h"
#include "src/regexp/regexp.h"
#include "src/strings/string-builder-inl.h"
#include "src/strings/string-search.h"
namespace v8 {
namespace internal {
namespace {
// Fairly arbitrary, but intended to fit:
//
// - captures
// - results
// - parsed replacement pattern parts
//
// for small, common cases.
constexpr int kStaticVectorSlots = 8;
// Returns -1 for failure.
uint32_t GetArgcForReplaceCallable(uint32_t num_captures,
bool has_named_captures) {
const uint32_t kAdditionalArgsWithoutNamedCaptures = 2;
const uint32_t kAdditionalArgsWithNamedCaptures = 3;
if (num_captures > Code::kMaxArguments) return -1;
uint32_t argc = has_named_captures
? num_captures + kAdditionalArgsWithNamedCaptures
: num_captures + kAdditionalArgsWithoutNamedCaptures;
static_assert(Code::kMaxArguments < std::numeric_limits<uint32_t>::max() -
kAdditionalArgsWithNamedCaptures);
return (argc > Code::kMaxArguments) ? -1 : argc;
}
// Looks up the capture of the given name. Returns the (1-based) numbered
// capture index or -1 on failure.
// The lookup starts at index |index_in_out|. On success |index_in_out| is set
// to the index after the entry was found (i.e. the start index to continue the
// search in the presence of duplicate group names).
template <typename Matcher, typename = std::enable_if<std::is_invocable_r_v<
bool, Matcher, Tagged<String>>>>
int LookupNamedCapture(Matcher name_matches,
Tagged<TrustedFixedArray> capture_name_map,
int* index_in_out) {
int index_in_val = *index_in_out;
DCHECK_GE(index_in_val, 0);
// TODO(jgruber): Sort capture_name_map and do binary search via
// internalized strings.
int maybe_capture_index = -1;
const uint32_t named_capture_count = capture_name_map->ulength().value() >> 1;
DCHECK_LE(static_cast<uint32_t>(index_in_val), named_capture_count);
for (uint32_t j = static_cast<uint32_t>(index_in_val);
j < named_capture_count; j++) {
// The format of {capture_name_map} is documented at
// JSRegExp::kIrregexpCaptureNameMapIndex.
const uint32_t name_ix = j * 2;
const uint32_t index_ix = j * 2 + 1;
Tagged<String> capture_name = Cast<String>(capture_name_map->get(name_ix));
if (!name_matches(capture_name)) continue;
maybe_capture_index = Smi::ToInt(capture_name_map->get(index_ix));
*index_in_out = static_cast<int>(j + 1);
break;
}
return maybe_capture_index;
}
} // namespace
class CompiledReplacement {
public:
explicit CompiledReplacement(Isolate* isolate)
: replacement_substrings_(isolate) {}
// Return whether the replacement is simple.
bool Compile(Isolate* isolate, DirectHandle<JSRegExp> regexp,
DirectHandle<RegExpData> regexp_data,
DirectHandle<String> replacement, int capture_count,
int subject_length);
// Use Apply only if Compile returned false.
void Apply(ReplacementStringBuilder* builder, int match_from, int match_to,
int32_t* match);
// Number of distinct parts of the replacement pattern.
uint32_t parts() { return static_cast<uint32_t>(parts_.size()); }
private:
enum PartType {
SUBJECT_PREFIX = 1,
SUBJECT_SUFFIX,
SUBJECT_CAPTURE,
REPLACEMENT_SUBSTRING,
REPLACEMENT_STRING,
EMPTY_REPLACEMENT,
NUMBER_OF_PART_TYPES
};
struct ReplacementPart {
static inline ReplacementPart SubjectMatch() {
return ReplacementPart(SUBJECT_CAPTURE, 0);
}
static inline ReplacementPart SubjectCapture(int capture_index) {
return ReplacementPart(SUBJECT_CAPTURE, capture_index);
}
static inline ReplacementPart SubjectPrefix() {
return ReplacementPart(SUBJECT_PREFIX, 0);
}
static inline ReplacementPart SubjectSuffix(int subject_length) {
return ReplacementPart(SUBJECT_SUFFIX, subject_length);
}
static inline ReplacementPart ReplacementString() {
return ReplacementPart(REPLACEMENT_STRING, 0);
}
static inline ReplacementPart EmptyReplacement() {
return ReplacementPart(EMPTY_REPLACEMENT, 0);
}
static inline ReplacementPart ReplacementSubString(int from, int to) {
DCHECK_LE(0, from);
DCHECK_GT(to, from);
return ReplacementPart(-from, to);
}
// If tag <= 0 then it is the negation of a start index of a substring of
// the replacement pattern, otherwise it's a value from PartType.
ReplacementPart(int tag, int data) : tag(tag), data(data) {
// Must be non-positive or a PartType value.
DCHECK(tag < NUMBER_OF_PART_TYPES);
}
// Either a value of PartType or a non-positive number that is
// the negation of an index into the replacement string.
int tag;
// The data value's interpretation depends on the value of tag:
// tag == SUBJECT_PREFIX ||
// tag == SUBJECT_SUFFIX: data is unused.
// tag == SUBJECT_CAPTURE: data is the number of the capture.
// tag == REPLACEMENT_SUBSTRING ||
// tag == REPLACEMENT_STRING: data is index into array of substrings
// of the replacement string.
// tag == EMPTY_REPLACEMENT: data is unused.
// tag <= 0: Temporary representation of the substring of the replacement
// string ranging over -tag .. data.
// Is replaced by REPLACEMENT_{SUB,}STRING when we create the
// substring objects.
int data;
};
template <typename Char>
bool ParseReplacementPattern(base::Vector<Char> characters,
Tagged<TrustedFixedArray> capture_name_map,
int capture_count, int subject_length) {
// Equivalent to String::GetSubstitution, except that this method converts
// the replacement string into an internal representation that avoids
// repeated parsing when used repeatedly.
int length = characters.length();
int last = 0;
for (int i = 0; i < length; i++) {
Char c = characters[i];
if (c == '$') {
int next_index = i + 1;
if (next_index == length) { // No next character!
break;
}
Char c2 = characters[next_index];
switch (c2) {
case '$':
if (i > last) {
// There is a substring before. Include the first "$".
parts_.emplace_back(
ReplacementPart::ReplacementSubString(last, next_index));
last = next_index + 1; // Continue after the second "$".
} else {
// Let the next substring start with the second "$".
last = next_index;
}
i = next_index;
break;
case '`':
if (i > last) {
parts_.emplace_back(
ReplacementPart::ReplacementSubString(last, i));
}
parts_.emplace_back(ReplacementPart::SubjectPrefix());
i = next_index;
last = i + 1;
break;
case '\'':
if (i > last) {
parts_.emplace_back(
ReplacementPart::ReplacementSubString(last, i));
}
parts_.emplace_back(ReplacementPart::SubjectSuffix(subject_length));
i = next_index;
last = i + 1;
break;
case '&':
if (i > last) {
parts_.emplace_back(
ReplacementPart::ReplacementSubString(last, i));
}
parts_.emplace_back(ReplacementPart::SubjectMatch());
i = next_index;
last = i + 1;
break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9': {
int capture_ref = c2 - '0';
if (capture_ref > capture_count) {
i = next_index;
continue;
}
int second_digit_index = next_index + 1;
if (second_digit_index < length) {
// Peek ahead to see if we have two digits.
Char c3 = characters[second_digit_index];
if ('0' <= c3 && c3 <= '9') { // Double digits.
int double_digit_ref = capture_ref * 10 + c3 - '0';
if (double_digit_ref <= capture_count) {
next_index = second_digit_index;
capture_ref = double_digit_ref;
}
}
}
if (capture_ref > 0) {
if (i > last) {
parts_.emplace_back(
ReplacementPart::ReplacementSubString(last, i));
}
DCHECK(capture_ref <= capture_count);
parts_.emplace_back(ReplacementPart::SubjectCapture(capture_ref));
last = next_index + 1;
}
i = next_index;
break;
}
case '<': {
if (capture_name_map.is_null()) {
i = next_index;
break;
}
// Scan until the next '>', and let the enclosed substring be the
// groupName.
const int name_start_index = next_index + 1;
int closing_bracket_index = -1;
for (int j = name_start_index; j < length; j++) {
if (characters[j] == '>') {
closing_bracket_index = j;
break;
}
}
// If no closing bracket is found, '$<' is treated as a string
// literal.
if (closing_bracket_index == -1) {
i = next_index;
break;
}
if (i > last) {
parts_.emplace_back(
ReplacementPart::ReplacementSubString(last, i));
}
base::Vector<Char> requested_name =
characters.SubVector(name_start_index, closing_bracket_index);
// If capture is undefined or does not exist, replace the text
// through the following '>' with the empty string.
// Otherwise, replace the text through the following '>' with
// ? ToString(capture).
// For duplicated capture group names we don't know which of them
// matches at this point in time, so we create a separate
// replacement for each possible match. When applying the
// replacement unmatched groups will be skipped.
int capture_index = 0;
int capture_name_map_index = 0;
while (capture_index != -1) {
capture_index = LookupNamedCapture(
[=](Tagged<String> capture_name) {
return capture_name->IsEqualTo(requested_name);
},
capture_name_map, &capture_name_map_index);
DCHECK(capture_index == -1 ||
(1 <= capture_index && capture_index <= capture_count));
parts_.emplace_back(
capture_index == -1
? ReplacementPart::EmptyReplacement()
: ReplacementPart::SubjectCapture(capture_index));
}
last = closing_bracket_index + 1;
i = closing_bracket_index;
break;
}
default:
i = next_index;
break;
}
}
}
if (length > last) {
if (last == 0) {
// Replacement is simple. Do not use Apply to do the replacement.
return true;
} else {
parts_.emplace_back(
ReplacementPart::ReplacementSubString(last, length));
}
}
return false;
}
base::SmallVector<ReplacementPart, kStaticVectorSlots> parts_;
DirectHandleSmallVector<String, kStaticVectorSlots> replacement_substrings_;
};
bool CompiledReplacement::Compile(Isolate* isolate,
DirectHandle<JSRegExp> regexp,
DirectHandle<RegExpData> regexp_data,
DirectHandle<String> replacement,
int capture_count, int subject_length) {
{
DisallowGarbageCollection no_gc;
String::FlatContent content = replacement->GetFlatContent(no_gc);
DCHECK(content.IsFlat());
Tagged<TrustedFixedArray> capture_name_map;
if (capture_count > 0) {
// capture_count > 0 implies IrRegExpData. Since capture_count is in
// trusted space, this is not a SBXCHECK.
Tagged<IrRegExpData> re_data = TrustedCast<IrRegExpData>(*regexp_data);
if (re_data->has_capture_name_map()) {
capture_name_map = re_data->capture_name_map();
}
}
bool simple;
if (content.IsOneByte()) {
simple =
ParseReplacementPattern(content.ToOneByteVector(), capture_name_map,
capture_count, subject_length);
} else {
DCHECK(content.IsTwoByte());
simple = ParseReplacementPattern(content.ToUC16Vector(), capture_name_map,
capture_count, subject_length);
}
if (simple) return true;
}
// Find substrings of replacement string and create them as String objects.
replacement_substrings_.reserve(parts());
int substring_index = 0;
for (ReplacementPart& part : parts_) {
int tag = part.tag;
if (tag <= 0) { // A replacement string slice.
int from = -tag;
int to = part.data;
replacement_substrings_.emplace_back(
isolate->factory()->NewSubString(replacement, from, to));
part.tag = REPLACEMENT_SUBSTRING;
part.data = substring_index;
substring_index++;
} else if (tag == REPLACEMENT_STRING) {
replacement_substrings_.emplace_back(replacement);
part.data = substring_index;
substring_index++;
}
}
return false;
}
void CompiledReplacement::Apply(ReplacementStringBuilder* builder,
int match_from, int match_to, int32_t* match) {
DCHECK_LT(0, parts_.size());
for (ReplacementPart& part : parts_) {
switch (part.tag) {
case SUBJECT_PREFIX:
if (match_from > 0) builder->AddSubjectSlice(0, match_from);
break;
case SUBJECT_SUFFIX: {
int subject_length = part.data;
if (match_to < subject_length) {
builder->AddSubjectSlice(match_to, subject_length);
}
break;
}
case SUBJECT_CAPTURE: {
int capture = part.data;
int from = match[capture * 2];
int to = match[capture * 2 + 1];
if (from >= 0 && to > from) {
builder->AddSubjectSlice(from, to);
}
break;
}
case REPLACEMENT_SUBSTRING:
case REPLACEMENT_STRING:
builder->AddString(replacement_substrings_[part.data]);
break;
case EMPTY_REPLACEMENT:
break;
default:
UNREACHABLE();
}
}
}
void FindOneByteStringIndices(base::Vector<const uint8_t> subject,
uint8_t pattern, std::vector<int>* indices,
unsigned int limit, int start_index = 0) {
DCHECK_LT(0, limit);
// Collect indices of pattern in subject using memchr.
// Stop after finding at most limit values.
const uint8_t* subject_start = subject.begin();
const uint8_t* subject_end = subject_start + subject.length();
const uint8_t* pos = subject_start + start_index;
while (limit > 0) {
pos = reinterpret_cast<const uint8_t*>(
memchr(pos, pattern, subject_end - pos));
if (pos == nullptr) return;
indices->push_back(static_cast<int>(pos - subject_start));
pos++;
limit--;
}
}
void FindTwoByteStringIndices(const base::Vector<const base::uc16> subject,
base::uc16 pattern, std::vector<int>* indices,
unsigned int limit, int start_index = 0) {
DCHECK_LT(0, limit);
const base::uc16* subject_start = subject.begin();
const base::uc16* subject_end = subject_start + subject.length();
for (const base::uc16* pos = subject_start + start_index;
pos < subject_end && limit > 0; pos++) {
if (*pos == pattern) {
indices->push_back(static_cast<int>(pos - subject_start));
limit--;
}
}
}
template <typename SubjectChar, typename PatternChar>
void FindStringIndices(Isolate* isolate,
base::Vector<const SubjectChar> subject,
base::Vector<const PatternChar> pattern,
std::vector<int>* indices, unsigned int limit,
int start_index = 0) {
DCHECK_LT(0, limit);
// Collect indices of pattern in subject.
// Stop after finding at most limit values.
int pattern_length = pattern.length();
int index = start_index;
StringSearch<PatternChar, SubjectChar> search(isolate, pattern);
while (limit > 0) {
index = search.Search(subject, index);
if (index < 0) return;
indices->push_back(index);
index += pattern_length;
limit--;
}
}
void FindStringIndicesDispatch(Isolate* isolate, Tagged<String> subject,
Tagged<String> pattern,
std::vector<int>* indices, unsigned int limit,
int first_index = -1) {
int start_index = 0;
if (first_index >= 0) {
indices->push_back(first_index);
limit--;
if (limit == 0) return;
start_index = first_index + pattern->length();
}
{
DisallowGarbageCollection no_gc;
String::FlatContent subject_content = subject->GetFlatContent(no_gc);
String::FlatContent pattern_content = pattern->GetFlatContent(no_gc);
DCHECK(subject_content.IsFlat());
DCHECK(pattern_content.IsFlat());
if (subject_content.IsOneByte()) {
base::Vector<const uint8_t> subject_vector =
subject_content.ToOneByteVector();
if (pattern_content.IsOneByte()) {
base::Vector<const uint8_t> pattern_vector =
pattern_content.ToOneByteVector();
if (pattern_vector.length() == 1) {
FindOneByteStringIndices(subject_vector, pattern_vector[0], indices,
limit, start_index);
} else {
FindStringIndices(isolate, subject_vector, pattern_vector, indices,
limit, start_index);
}
} else {
FindStringIndices(isolate, subject_vector,
pattern_content.ToUC16Vector(), indices, limit,
start_index);
}
} else {
base::Vector<const base::uc16> subject_vector =
subject_content.ToUC16Vector();
if (pattern_content.IsOneByte()) {
base::Vector<const uint8_t> pattern_vector =
pattern_content.ToOneByteVector();
if (pattern_vector.length() == 1) {
FindTwoByteStringIndices(subject_vector, pattern_vector[0], indices,
limit, start_index);
} else {
FindStringIndices(isolate, subject_vector, pattern_vector, indices,
limit, start_index);
}
} else {
base::Vector<const base::uc16> pattern_vector =
pattern_content.ToUC16Vector();
if (pattern_vector.length() == 1) {
FindTwoByteStringIndices(subject_vector, pattern_vector[0], indices,
limit, start_index);
} else {
FindStringIndices(isolate, subject_vector, pattern_vector, indices,
limit, start_index);
}
}
}
}
}
namespace {
std::vector<int>* GetRewoundRegexpIndicesList(Isolate* isolate) {
std::vector<int>* list = isolate->regexp_indices();
list->clear();
return list;
}
void TruncateRegexpIndicesList(Isolate* isolate) {
// Same size as smallest zone segment, preserving behavior from the
// runtime zone.
// TODO(jgruber): Consider removing the reusable regexp_indices list and
// simply allocating a new list each time. It feels like we're needlessly
// optimizing an edge case.
static const int kMaxRegexpIndicesListCapacity = 8 * KB / kIntSize;
std::vector<int>* indices = isolate->regexp_indices();
if (indices->capacity() > kMaxRegexpIndicesListCapacity) {
// Throw away backing storage.
indices->clear();
indices->shrink_to_fit();
}
}
} // namespace
template <typename ResultSeqString>
V8_WARN_UNUSED_RESULT static Tagged<UnionOf<ExceptionHole, String>>
StringReplaceGlobalAtomRegExpWithString(
Isolate* isolate, DirectHandle<String> subject,
DirectHandle<JSRegExp> pattern_regexp, DirectHandle<String> replacement,
DirectHandle<RegExpMatchInfo> last_match_info,
DirectHandle<AtomRegExpData> regexp_data) {
DCHECK(subject->IsFlat());
DCHECK(replacement->IsFlat());
std::vector<int>* indices = GetRewoundRegexpIndicesList(isolate);
Tagged<String> pattern = regexp_data->pattern();
int subject_len = subject->length();
int pattern_len = pattern->length();
int replacement_len = replacement->length();
FindStringIndicesDispatch(isolate, *subject, pattern, indices, 0xFFFFFFFF);
if (indices->empty()) return *subject;
// Detect integer overflow.
int64_t result_len_64 = (static_cast<int64_t>(replacement_len) -
static_cast<int64_t>(pattern_len)) *
static_cast<int64_t>(indices->size()) +
static_cast<int64_t>(subject_len);
int result_len;
if (result_len_64 > static_cast<int64_t>(String::kMaxLength)) {
static_assert(String::kMaxLength < kMaxInt);
result_len = kMaxInt; // Provoke exception.
} else {
result_len = static_cast<int>(result_len_64);
}
if (result_len == 0) {
return ReadOnlyRoots(isolate).empty_string();
}
int subject_pos = 0;
int result_pos = 0;
MaybeDirectHandle<SeqString> maybe_res;
if (ResultSeqString::kHasOneByteEncoding) {
maybe_res = isolate->factory()->NewRawOneByteString(result_len);
} else {
maybe_res = isolate->factory()->NewRawTwoByteString(result_len);
}
DirectHandle<SeqString> untyped_res;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, untyped_res, maybe_res);
DirectHandle<ResultSeqString> result = Cast<ResultSeqString>(untyped_res);
DisallowGarbageCollection no_gc;
for (int index : *indices) {
// Copy non-matched subject content.
if (subject_pos < index) {
String::WriteToFlat(*subject, result->GetChars(no_gc) + result_pos,
subject_pos, index - subject_pos);
result_pos += index - subject_pos;
}
// Replace match.
if (replacement_len > 0) {
String::WriteToFlat(*replacement, result->GetChars(no_gc) + result_pos, 0,
replacement_len);
result_pos += replacement_len;
}
subject_pos = index + pattern_len;
}
// Add remaining subject content at the end.
if (subject_pos < subject_len) {
String::WriteToFlat(*subject, result->GetChars(no_gc) + result_pos,
subject_pos, subject_len - subject_pos);
}
int32_t match_indices[] = {indices->back(), indices->back() + pattern_len};
RegExp::SetLastMatchInfo(isolate, last_match_info, subject, 0, match_indices);
TruncateRegexpIndicesList(isolate);
return *result;
}
V8_WARN_UNUSED_RESULT static Tagged<UnionOf<ExceptionHole, String>>
StringReplaceGlobalRegExpWithString(
Isolate* isolate, DirectHandle<String> subject,
DirectHandle<JSRegExp> regexp, DirectHandle<RegExpData> regexp_data,
DirectHandle<String> replacement,
DirectHandle<RegExpMatchInfo> last_match_info) {
DCHECK(subject->IsFlat());
DCHECK(replacement->IsFlat());
int capture_count = regexp_data->capture_count();
int subject_length = subject->length();
// Ensure the RegExp is compiled so we can access the capture-name map.
if (!RegExp::EnsureFullyCompiled(isolate, regexp_data, subject)) {
return ReadOnlyRoots(isolate).exception();
}
CompiledReplacement compiled_replacement(isolate);
const bool simple_replace = compiled_replacement.Compile(
isolate, regexp, regexp_data, replacement, capture_count, subject_length);
// Shortcut for simple non-regexp global replacements.
if (regexp_data->type_tag() == RegExpData::Type::ATOM && simple_replace) {
if (subject->IsOneByteRepresentation() &&
replacement->IsOneByteRepresentation()) {
return StringReplaceGlobalAtomRegExpWithString<SeqOneByteString>(
isolate, subject, regexp, replacement, last_match_info,
TrustedCast<AtomRegExpData>(regexp_data));
} else {
return StringReplaceGlobalAtomRegExpWithString<SeqTwoByteString>(
isolate, subject, regexp, replacement, last_match_info,
TrustedCast<AtomRegExpData>(regexp_data));
}
}
regexp::GlobalExecRunner runner(direct_handle(*regexp_data, isolate), subject,
isolate);
if (runner.HasException()) return ReadOnlyRoots(isolate).exception();
int32_t* current_match = runner.FetchNext();
if (current_match == nullptr) {
if (runner.HasException()) return ReadOnlyRoots(isolate).exception();
return *subject;
}
// Guessing the number of parts that the final result string is built
// from. Global regexps can match any number of times, so we guess
// conservatively.
uint32_t expected_parts = (compiled_replacement.parts() + 1) * 4 + 1;
// TODO(v8:12843): improve the situation where the expected_parts exceeds
// the maximum size of the backing store.
ReplacementStringBuilder builder(isolate->heap(), subject, expected_parts);
int prev = 0;
do {
int start = current_match[0];
int end = current_match[1];
if (prev < start) {
builder.AddSubjectSlice(prev, start);
}
if (simple_replace) {
builder.AddString(replacement);
} else {
compiled_replacement.Apply(&builder, start, end, current_match);
}
prev = end;
current_match = runner.FetchNext();
} while (current_match != nullptr);
if (runner.HasException()) return ReadOnlyRoots(isolate).exception();
if (prev < subject_length) {
builder.AddSubjectSlice(prev, subject_length);
}
RegExp::SetLastMatchInfo(isolate, last_match_info, subject, capture_count,
runner.LastSuccessfulMatch());
RETURN_RESULT_OR_FAILURE(isolate, builder.ToString());
}
template <typename ResultSeqString>
V8_WARN_UNUSED_RESULT static Tagged<UnionOf<ExceptionHole, String>>
StringReplaceGlobalRegExpWithEmptyString(
Isolate* isolate, DirectHandle<String> subject,
DirectHandle<JSRegExp> regexp, DirectHandle<RegExpData> regexp_data,
DirectHandle<RegExpMatchInfo> last_match_info) {
DCHECK(subject->IsFlat());
// Shortcut for simple non-regexp global replacements.
if (regexp_data->type_tag() == RegExpData::Type::ATOM) {
DirectHandle<String> empty_string = isolate->factory()->empty_string();
if (subject->IsOneByteRepresentation()) {
return StringReplaceGlobalAtomRegExpWithString<SeqOneByteString>(
isolate, subject, regexp, empty_string, last_match_info,
TrustedCast<AtomRegExpData>(regexp_data));
} else {
return StringReplaceGlobalAtomRegExpWithString<SeqTwoByteString>(
isolate, subject, regexp, empty_string, last_match_info,
TrustedCast<AtomRegExpData>(regexp_data));
}
}
regexp::GlobalExecRunner runner(direct_handle(*regexp_data, isolate), subject,
isolate);
if (runner.HasException()) return ReadOnlyRoots(isolate).exception();
int32_t* current_match = runner.FetchNext();
if (current_match == nullptr) {
if (runner.HasException()) return ReadOnlyRoots(isolate).exception();
return *subject;
}
int start = current_match[0];
int end = current_match[1];
int capture_count = regexp_data->capture_count();
int subject_length = subject->length();
int new_length = subject_length - (end - start);
if (new_length == 0) return ReadOnlyRoots(isolate).empty_string();
DirectHandle<ResultSeqString> answer;
if (ResultSeqString::kHasOneByteEncoding) {
answer = Cast<ResultSeqString>(
isolate->factory()->NewRawOneByteString(new_length).ToHandleChecked());
} else {
answer = Cast<ResultSeqString>(
isolate->factory()->NewRawTwoByteString(new_length).ToHandleChecked());
}
int prev = 0;
int position = 0;
DisallowGarbageCollection no_gc;
do {
start = current_match[0];
end = current_match[1];
if (prev < start) {
// Add substring subject[prev;start] to answer string.
String::WriteToFlat(*subject, answer->GetChars(no_gc) + position, prev,
start - prev);
position += start - prev;
}
prev = end;
current_match = runner.FetchNext();
} while (current_match != nullptr);
if (runner.HasException()) return ReadOnlyRoots(isolate).exception();
RegExp::SetLastMatchInfo(isolate, last_match_info, subject, capture_count,
runner.LastSuccessfulMatch());
if (prev < subject_length) {
// Add substring subject[prev;length] to answer string.
String::WriteToFlat(*subject, answer->GetChars(no_gc) + position, prev,
subject_length - prev);
position += subject_length - prev;
}
if (position == 0) return ReadOnlyRoots(isolate).empty_string();
// Shorten string and fill
int string_size = ResultSeqString::SizeFor(position);
int allocated_string_size = ResultSeqString::SizeFor(new_length);
int delta = allocated_string_size - string_size;
answer->set_length(position);
if (delta == 0) return *answer;
Address end_of_string = answer->address() + string_size;
Heap* heap = isolate->heap();
// The trimming is performed on a newly allocated object, which is on a
// freshly allocated page or on an already swept page. Hence, the sweeper
// thread can not get confused with the filler creation. No synchronization
// needed.
if (!HeapLayout::InAnyLargeSpace(*answer)) {
heap->CreateFillerObjectAt(end_of_string, delta);
}
return *answer;
}
RUNTIME_FUNCTION(Runtime_StringSplit) {
HandleScope handle_scope(isolate);
DCHECK_EQ(4, args.length());
DirectHandle<String> subject = args.at<String>(0);
DirectHandle<String> pattern = args.at<String>(1);
uint32_t limit = NumberToUint32(args[2]);
int first_index = NumberToInt32(args[3]);
CHECK_LT(0, limit);
int subject_length = subject->length();
int pattern_length = pattern->length();
CHECK_LT(0, pattern_length);
if (limit == 0xFFFFFFFFu) {
Tagged<FixedArray> last_match_cache_unused;
DirectHandle<Object> cached_answer(
regexp::ResultsCache::Lookup(
isolate->heap(), *subject, *pattern, &last_match_cache_unused,
regexp::ResultsCache::STRING_SPLIT_SUBSTRINGS),
isolate);
if (*cached_answer != Smi::zero()) {
// The cache FixedArray is a COW-array and can therefore be reused.
DirectHandle<JSArray> result = isolate->factory()->NewJSArrayWithElements(
Cast<FixedArray>(cached_answer));
return *result;
}
}
// The limit can be very large (0xFFFFFFFFu), but since the pattern
// isn't empty, we can never create more parts than ~half the length
// of the subject.
subject = String::Flatten(isolate, subject);
pattern = String::Flatten(isolate, pattern);
std::vector<int>* indices = GetRewoundRegexpIndicesList(isolate);
FindStringIndicesDispatch(isolate, *subject, *pattern, indices, limit,
first_index);
if (static_cast<uint32_t>(indices->size()) < limit) {
indices->push_back(subject_length);
}
// The list indices now contains the end of each part to create.
// Create JSArray of substrings separated by separator.
int part_count = static_cast<int>(indices->size());
DirectHandle<JSArray> result = isolate->factory()->NewJSArray(
PACKED_ELEMENTS, part_count, part_count,
ArrayStorageAllocationMode::INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE);
DCHECK(result->HasObjectElements());
DirectHandle<FixedArray> elements(Cast<FixedArray>(result->elements()),
isolate);
if (part_count == 1 && indices->at(0) == subject_length) {
elements->set(0, *subject);
} else {
int part_start = 0;
FOR_WITH_HANDLE_SCOPE(isolate, int i = 0, i, i < part_count, i++) {
int part_end = indices->at(i);
DirectHandle<String> substring =
isolate->factory()->NewProperSubString(subject, part_start, part_end);
elements->set(i, *substring);
part_start = part_end + pattern_length;
}
}
if (limit == 0xFFFFFFFFu) {
if (result->HasObjectElements()) {
regexp::ResultsCache::Enter(
isolate, subject, pattern, elements,
isolate->factory()->empty_fixed_array(),
regexp::ResultsCache::STRING_SPLIT_SUBSTRINGS);
}
}
TruncateRegexpIndicesList(isolate);
return *result;
}
namespace {
std::optional<int> RegExpExec(Isolate* isolate,
DirectHandle<RegExpData> regexp_data,
DirectHandle<String> subject, int32_t index,
int32_t* result_offsets_vector,
uint32_t result_offsets_vector_length) {
// Due to the way the JS calls are constructed this must be less than the
// length of a string, i.e. it is always a Smi. We check anyway for security.
CHECK_LE(0, index);
CHECK_GE(subject->length(), index);
isolate->counters()->regexp_entry_runtime()->Increment();
return RegExp::Exec(isolate, regexp_data, subject, index,
result_offsets_vector, result_offsets_vector_length);
}
std::optional<int> ExperimentalOneshotExec(
Isolate* isolate, DirectHandle<RegExpData> regexp_data,
DirectHandle<String> subject, int32_t index, int32_t* result_offsets_vector,
uint32_t result_offsets_vector_length) {
CHECK_GE(result_offsets_vector_length,
JSRegExp::RegistersForCaptureCount(regexp_data->capture_count()));
// Due to the way the JS calls are constructed this must be less than the
// length of a string, i.e. it is always a Smi. We check anyway for security.
CHECK_LE(0, index);
CHECK_GE(subject->length(), index);
isolate->counters()->regexp_entry_runtime()->Increment();
return RegExp::ExperimentalOneshotExec(isolate, regexp_data, subject, index,
result_offsets_vector,
result_offsets_vector_length);
}
} // namespace
RUNTIME_FUNCTION(Runtime_RegExpExec) {
HandleScope scope(isolate);
DCHECK_EQ(4, args.length());
DirectHandle<RegExpData> regexp_data =
SbxCast<RegExpData>(TrustedCast<TrustedObject>(args.at<Object>(0)));
DirectHandle<String> subject = args.at<String>(1);
int32_t index = 0;
CHECK(Object::ToInt32(args[2], &index));
uint32_t result_offsets_vector_length = 0;
CHECK(Object::ToUint32(args[3], &result_offsets_vector_length));
// This untagged arg must be passed as an implicit arg.
int32_t* result_offsets_vector = reinterpret_cast<int32_t*>(
isolate->isolate_data()->regexp_exec_vector_argument());
DCHECK_NOT_NULL(result_offsets_vector);
std::optional<int> result =
RegExpExec(isolate, regexp_data, subject, index, result_offsets_vector,
result_offsets_vector_length);
DCHECK_EQ(!result, isolate->has_exception());
if (!result) return ReadOnlyRoots(isolate).exception();
return Smi::FromInt(result.value());
}
RUNTIME_FUNCTION(Runtime_RegExpGrowRegExpMatchInfo) {
HandleScope scope(isolate);
DCHECK_EQ(2, args.length());
DirectHandle<RegExpMatchInfo> match_info = args.at<RegExpMatchInfo>(0);
int32_t register_count;
CHECK(Object::ToInt32(args[1], &register_count));
// We never pass anything besides the global last_match_info.
DCHECK_EQ(*match_info, *isolate->regexp_last_match_info());
DirectHandle<RegExpMatchInfo> result = RegExpMatchInfo::ReserveCaptures(
isolate, match_info, JSRegExp::CaptureCountForRegisters(register_count));
if (*result != *match_info) {
isolate->native_context()->set_regexp_last_match_info(*result);
}
return *result;
}
RUNTIME_FUNCTION(Runtime_RegExpExperimentalOneshotExec) {
HandleScope scope(isolate);
DCHECK_EQ(4, args.length());
DirectHandle<RegExpData> regexp_data =
SbxCast<RegExpData>(TrustedCast<TrustedObject>(args.at<Object>(0)));
DirectHandle<String> subject = args.at<String>(1);
int32_t index = 0;
CHECK(Object::ToInt32(args[2], &index));
uint32_t result_offsets_vector_length = 0;
CHECK(Object::ToUint32(args[3], &result_offsets_vector_length));
// This untagged arg must be passed as an implicit arg.
int32_t* result_offsets_vector = reinterpret_cast<int32_t*>(
isolate->isolate_data()->regexp_exec_vector_argument());
DCHECK_NOT_NULL(result_offsets_vector);
std::optional<int> result = ExperimentalOneshotExec(
isolate, regexp_data, subject, index, result_offsets_vector,
result_offsets_vector_length);
DCHECK_EQ(!result, isolate->has_exception());
if (!result) return ReadOnlyRoots(isolate).exception();
return Smi::FromInt(result.value());
}
RUNTIME_FUNCTION(Runtime_RegExpBuildIndices) {
HandleScope scope(isolate);
DCHECK_EQ(2, args.length());
DirectHandle<JSRegExp> regexp = args.at<JSRegExp>(0);
DirectHandle<RegExpMatchInfo> match_info = args.at<RegExpMatchInfo>(1);
#ifdef DEBUG
DCHECK(regexp->flags() & JSRegExp::kHasIndices);
#endif
return *JSRegExpResultIndices::BuildIndices(
isolate, match_info, direct_handle(regexp->data(isolate), isolate));
}
namespace {
class MatchInfoBackedMatch : public String::Match {
public:
MatchInfoBackedMatch(Isolate* isolate, DirectHandle<JSRegExp> regexp,
DirectHandle<RegExpData> regexp_data,
DirectHandle<String> subject,
DirectHandle<RegExpMatchInfo> match_info)
: isolate_(isolate), match_info_(match_info) {
subject_ = String::Flatten(isolate, subject);
if (RegExpData::TypeSupportsCaptures(regexp_data->type_tag())) {
DCHECK(Is<IrRegExpData>(*regexp_data));
DirectHandle<IrRegExpData> re_data =
TrustedCast<IrRegExpData>(regexp_data);
has_named_captures_ = re_data->has_capture_name_map();
if (has_named_captures_) {
capture_name_map_ = direct_handle(re_data->capture_name_map(), isolate);
}
} else {
has_named_captures_ = false;
}
}
DirectHandle<String> GetMatch() override {
return regexp::Utils::GenericCaptureGetter(isolate_, match_info_, 0,
nullptr);
}
DirectHandle<String> GetPrefix() override {
const int match_start = match_info_->capture(0);
return isolate_->factory()->NewSubString(subject_, 0, match_start);
}
DirectHandle<String> GetSuffix() override {
const int match_end = match_info_->capture(1);
return isolate_->factory()->NewSubString(subject_, match_end,
subject_->length());
}
bool HasNamedCaptures() override { return has_named_captures_; }
int CaptureCount() override {
return match_info_->number_of_capture_registers() / 2;
}
MaybeDirectHandle<String> GetCapture(int i, bool* capture_exists) override {
DirectHandle<Object> capture_obj = regexp::Utils::GenericCaptureGetter(
isolate_, match_info_, i, capture_exists);
return (*capture_exists) ? Object::ToString(isolate_, capture_obj)
: isolate_->factory()->empty_string();
}
MaybeDirectHandle<String> GetNamedCapture(DirectHandle<String> name,
CaptureState* state) override {
DCHECK(has_named_captures_);
int capture_index = 0;
int capture_name_map_index = 0;
while (true) {
capture_index = LookupNamedCapture(
[=](Tagged<String> capture_name) {
return capture_name->Equals(*name);
},
*capture_name_map_, &capture_name_map_index);
if (capture_index == -1) {
*state = UNMATCHED;
return isolate_->factory()->empty_string();
}
if (regexp::Utils::IsMatchedCapture(*match_info_, capture_index)) {
DirectHandle<String> capture_value;
ASSIGN_RETURN_ON_EXCEPTION(
isolate_, capture_value,
Object::ToString(isolate_,
regexp::Utils::GenericCaptureGetter(
isolate_, match_info_, capture_index)));
*state = MATCHED;
return capture_value;
}
}
}
private:
Isolate* isolate_;
DirectHandle<String> subject_;
DirectHandle<RegExpMatchInfo> match_info_;
bool has_named_captures_;
DirectHandle<TrustedFixedArray> capture_name_map_;
};
class VectorBackedMatch : public String::Match {
public:
VectorBackedMatch(Isolate* isolate, DirectHandle<String> subject,
DirectHandle<String> match, uint32_t match_position,
base::Vector<DirectHandle<Object>> captures,
DirectHandle<Object> groups_obj)
: isolate_(isolate),
match_(match),
match_position_(match_position),
captures_(captures) {
subject_ = String::Flatten(isolate, subject);
DCHECK(IsUndefined(*groups_obj) || IsJSReceiver(*groups_obj));
has_named_captures_ = !IsUndefined(*groups_obj);
if (has_named_captures_) groups_obj_ = Cast<JSReceiver>(groups_obj);
}
DirectHandle<String> GetMatch() override { return match_; }
DirectHandle<String> GetPrefix() override {
// match_position_ and match_ are user-controlled, hence we manually clamp
// the index here.
uint32_t end = std::min(subject_->length(), match_position_);
return isolate_->factory()->NewSubString(subject_, 0, end);
}
DirectHandle<String> GetSuffix() override {
// match_position_ and match_ are user-controlled, hence we manually clamp
// the index here.
uint32_t start =
std::min(subject_->length(), match_position_ + match_->length());
return isolate_->factory()->NewSubString(subject_, start,
subject_->length());
}
bool HasNamedCaptures() override { return has_named_captures_; }
int CaptureCount() override { return captures_.length(); }
MaybeDirectHandle<String> GetCapture(int i, bool* capture_exists) override {
DirectHandle<Object> capture_obj = captures_[i];
if (IsUndefined(*capture_obj)) {
*capture_exists = false;
return isolate_->factory()->empty_string();
}
*capture_exists = true;
return Object::ToString(isolate_, capture_obj);
}
MaybeDirectHandle<String> GetNamedCapture(DirectHandle<String> name,
CaptureState* state) override {
DCHECK(has_named_captures_);
// Strings representing integer indices are not valid identifiers (and
// therefore not valid capture names).
{
size_t unused;
if (name->AsIntegerIndex(&unused)) {
*state = UNMATCHED;
return isolate_->factory()->empty_string();
}
}
DirectHandle<Object> capture_obj;
ASSIGN_RETURN_ON_EXCEPTION(
isolate_, capture_obj,
Object::GetProperty(isolate_, groups_obj_, name));
if (IsUndefined(*capture_obj)) {
*state = UNMATCHED;
return isolate_->factory()->empty_string();
} else {
*state = MATCHED;
return Object::ToString(isolate_, capture_obj);
}
}
private:
Isolate* isolate_;
DirectHandle<String> subject_;
DirectHandle<String> match_;
const uint32_t match_position_;
base::Vector<DirectHandle<Object>> captures_;
bool has_named_captures_;
DirectHandle<JSReceiver> groups_obj_;
};
// Create the groups object (see also the RegExp result creation in
// RegExpBuiltinsAssembler::ConstructNewResultFromMatchInfo).
// TODO(42203211): We cannot simply pass a std::function here, as the closure
// may contain direct handles and they cannot be stored off-stack.
template <typename FunctionType,
typename = std::enable_if_t<std::is_function_v<Tagged<Object>(int)>>>
DirectHandle<JSObject> ConstructNamedCaptureGroupsObject(
Isolate* isolate, DirectHandle<TrustedFixedArray> capture_map,
const FunctionType& f_get_capture) {
DirectHandle<JSObject> groups =
isolate->factory()->NewJSObjectWithNullProto();
const uint32_t named_capture_count = capture_map->ulength().value() >> 1;
for (uint32_t i = 0; i < named_capture_count; i++) {
const uint32_t name_ix = i * 2;
const uint32_t index_ix = i * 2 + 1;
DirectHandle<String> capture_name(Cast<String>(capture_map->get(name_ix)),
isolate);
const int capture_ix = Smi::ToInt(capture_map->get(index_ix));
DCHECK_GE(capture_ix, 1); // Explicit groups start at index 1.
DirectHandle<Object> capture_value(f_get_capture(capture_ix), isolate);
DCHECK(IsUndefined(*capture_value) || IsString(*capture_value));
LookupIterator it(isolate, groups, capture_name, groups,
LookupIterator::OWN_SKIP_INTERCEPTOR);
if (it.IsFound()) {
if (!IsUndefined(*capture_value)) {
DCHECK(IsUndefined(*it.GetDataValue()));
CHECK(Object::SetDataProperty(&it, capture_value).ToChecked());
}
} else {
CHECK(Object::AddDataProperty(&it, capture_value, NONE,
Just(ShouldThrow::kThrowOnError),
StoreOrigin::kNamed)
.IsJust());
}
}
return groups;
}
// Returns a copy of {matches} that shares nothing mutable with it: the array
// itself, and with named captures also the per-match argument arrays and the
// groups objects they hold.
//
// Callers must use this on both sides of the results cache: a replace callback
// can retain and mutate the groups object it is given, and the cache stores
// entries by reference. Copying on entry keeps the cached arrays unreachable
// from any callback, which is what lets the exit side be a plain clone.
DirectHandle<FixedArray> CopyMatches(Isolate* isolate,
DirectHandle<FixedArray> matches,
bool has_named_captures,
int capture_count) {
DirectHandle<FixedArray> copy = isolate->factory()->CopyFixedArrayWithMap(
matches, isolate->factory()->fixed_array_map());
if (!has_named_captures) return copy;
const uint32_t length = copy->ulength().value();
for (uint32_t i = 0; i < length; i++) {
// Subject slices are encoded as smis; only matches carry captures.
if (!IsJSArray(copy->get(i))) continue;
DirectHandle<FixedArray> elements(
Cast<FixedArray>(Cast<JSArray>(copy->get(i))->elements()), isolate);
DirectHandle<FixedArray> new_elements =
isolate->factory()->CopyFixedArrayWithMap(
elements, isolate->factory()->fixed_array_map());
// The groups object is appended last, after match, captures, index and
// subject. GetArgcForReplaceCallable counts the match itself as a capture.
DCHECK_EQ(new_elements->ulength().value(),
GetArgcForReplaceCallable(capture_count + 1, true));
const uint32_t groups_index = new_elements->ulength().value() - 1;
DCHECK(IsJSObject(new_elements->get(groups_index)));
DirectHandle<JSObject> groups(
Cast<JSObject>(new_elements->get(groups_index)), isolate);
DirectHandle<JSObject> groups_copy =
isolate->factory()->CopyJSObject(groups);
new_elements->set(groups_index, *groups_copy);
DirectHandle<JSArray> new_match =
isolate->factory()->NewJSArrayWithElements(new_elements);
copy->set(i, *new_match);
}
return copy;
}
// Only called from Runtime_RegExpExecMultiple so it doesn't need to maintain
// separate last match info. See comment on that function.
template <bool has_capture>
static Tagged<UnionOf<ExceptionHole, Null, FixedArray>> SearchRegExpMultiple(
Isolate* isolate, DirectHandle<String> subject,
DirectHandle<JSRegExp> regexp, DirectHandle<RegExpData> regexp_data,
DirectHandle<RegExpMatchInfo> last_match_array) {
DCHECK(regexp::Utils::IsUnmodifiedRegExp(isolate, regexp));
DCHECK_NE(has_capture, regexp_data->capture_count() == 0);
DCHECK_IMPLIES(has_capture, Is<IrRegExpData>(*regexp_data));
DCHECK(subject->IsFlat());
// Force tier up to native code for global replaces. The global replace is
// implemented differently for native code and bytecode execution, where the
// native code expects an array to store all the matches, and the bytecode
// matches one at a time, so it's easier to tier-up to native code from the
// start.
if (v8_flags.regexp_tier_up &&
regexp_data->type_tag() == RegExpData::Type::IRREGEXP) {
TrustedCast<IrRegExpData>(regexp_data)->MarkTierUpForNextExec();
if (v8_flags.trace_regexp_tier_up) {
PrintF("Forcing tier-up of JSRegExp object %p in SearchRegExpMultiple\n",
reinterpret_cast<void*>(regexp->ptr()));
}
}
int capture_count = regexp_data->capture_count();
int subject_length = subject->length();
// has_capture can only be true for IrRegExp.
DirectHandle<IrRegExpData> re_data;
if (has_capture) re_data = TrustedCast<IrRegExpData>(regexp_data);
static const int kMinLengthToCache = 0x1000;
if (subject_length > kMinLengthToCache) {
Tagged<FixedArray> last_match_cache;
Tagged<Object> cached_answer = regexp::ResultsCache::Lookup(
isolate->heap(), *subject, regexp_data->wrapper(), &last_match_cache,
regexp::ResultsCache::REGEXP_MULTIPLE_INDICES);
if (IsFixedArray(cached_answer)) {
int capture_registers = JSRegExp::RegistersForCaptureCount(capture_count);
std::unique_ptr<int32_t[]> last_match(new int32_t[capture_registers]);
int32_t* raw_last_match = last_match.get();
for (int i = 0; i < capture_registers; i++) {
raw_last_match[i] = Smi::ToInt(last_match_cache->get(i));
}
DirectHandle<FixedArray> cached_fixed_array(
Cast<FixedArray>(cached_answer), isolate);
// The cache FixedArray is a COW-array and we need to return a copy. A
// cache hit implies an earlier run compiled the pattern, so the capture
// name map is populated.
DirectHandle<FixedArray> copied_fixed_array = CopyMatches(
isolate, cached_fixed_array,
has_capture && re_data->has_capture_name_map(), capture_count);
RegExp::SetLastMatchInfo(isolate, last_match_array, subject,
capture_count, raw_last_match);
return *copied_fixed_array;
}
}
regexp::GlobalExecRunner runner(direct_handle(*regexp_data, isolate), subject,
isolate);
if (runner.HasException()) return ReadOnlyRoots(isolate).exception();
FixedArrayBuilder builder = FixedArrayBuilder::Lazy(isolate);
// Position to search from.
int match_start = -1;
int match_end = 0;
bool first = true;
// Two smis before and after the match, for very long strings.
static const uint32_t kMaxBuilderEntriesPerRegExpMatch = 5;
// The capture name map is populated lazily, so this must stay below the
// GlobalExecRunner constructor, which is what compiles the pattern.
const bool has_named_captures =
has_capture && re_data->has_capture_name_map();
while (true) {
int32_t* current_match = runner.FetchNext();
if (current_match == nullptr) break;
match_start = current_match[0];
builder.EnsureCapacity(isolate, kMaxBuilderEntriesPerRegExpMatch);
if (match_end < match_start) {
ReplacementStringBuilder::AddSubjectSlice(&builder, match_end,
match_start);
}
match_end = current_match[1];
{
// Avoid accumulating new handles inside loop.
HandleScope temp_scope(isolate);
DirectHandle<String> match;
if (!first) {
match = isolate->factory()->NewProperSubString(subject, match_start,
match_end);
} else {
match =
isolate->factory()->NewSubString(subject, match_start, match_end);
first = false;
}
if (has_capture) {
// Arguments array to replace function is match, captures, index and
// subject. If the RegExp contains named captures, they are also passed
// as the last argument. GetArgcForReplaceCallable counts the match
// itself as a capture, and cannot overflow here because kMaxCaptures
// is well below Code::kMaxArguments.
const uint32_t argc =
GetArgcForReplaceCallable(capture_count + 1, has_named_captures);
DCHECK_NE(argc, static_cast<uint32_t>(-1));
DirectHandle<FixedArray> elements =
isolate->factory()->NewFixedArray(argc);
int cursor = 0;
elements->set(cursor++, *match);
for (int i = 1; i <= capture_count; i++) {
int start = current_match[i * 2];
if (start >= 0) {
int end = current_match[i * 2 + 1];
DCHECK(start <= end);
DirectHandle<String> substring =
isolate->factory()->NewSubString(subject, start, end);
elements->set(cursor++, *substring);
} else {
DCHECK_GT(0, current_match[i * 2 + 1]);
elements->set(cursor++, ReadOnlyRoots(isolate).undefined_value());
}
}
elements->set(cursor++, Smi::FromInt(match_start));
elements->set(cursor++, *subject);
if (has_named_captures) {
DirectHandle<TrustedFixedArray> capture_map(
re_data->capture_name_map(), isolate);
DirectHandle<JSObject> groups = ConstructNamedCaptureGroupsObject(
isolate, capture_map, [=](int ix) { return elements->get(ix); });
elements->set(cursor++, *groups);
}
DCHECK_EQ(cursor, argc);
builder.Add(*isolate->factory()->NewJSArrayWithElements(elements));
} else {
builder.Add(*match);
}
}
}
if (runner.HasException()) return ReadOnlyRoots(isolate).exception();
if (match_start >= 0) {
// Finished matching, with at least one match.
if (match_end < subject_length) {
ReplacementStringBuilder::AddSubjectSlice(&builder, match_end,
subject_length);
}
RegExp::SetLastMatchInfo(isolate, last_match_array, subject, capture_count,
runner.LastSuccessfulMatch());
if (subject_length > kMinLengthToCache) {
// Store the last successful match into the array for caching.
int capture_registers = JSRegExp::RegistersForCaptureCount(capture_count);
DirectHandle<FixedArray> last_match_cache =
isolate->factory()->NewFixedArray(capture_registers);
int32_t* last_match = runner.LastSuccessfulMatch();
for (int i = 0; i < capture_registers; i++) {
last_match_cache->set(i, Smi::FromInt(last_match[i]));
}
DirectHandle<FixedArray> result_fixed_array =
FixedArray::RightTrimOrEmpty(isolate, builder.array(),
builder.length().value());
// Cache the result and copy the FixedArray into a COW array. The copy
// must be deep, or the entry would share its groups objects with the
// array returned below.
DirectHandle<FixedArray> copied_fixed_array = CopyMatches(
isolate, result_fixed_array, has_named_captures, capture_count);
regexp::ResultsCache::Enter(
isolate, subject,
direct_handle(regexp->data(isolate)->wrapper(), isolate),
copied_fixed_array, last_match_cache,
regexp::ResultsCache::REGEXP_MULTIPLE_INDICES);
}
return *builder.array();
} else {
return ReadOnlyRoots(isolate).null_value(); // No matches at all.
}
}
// Legacy implementation of RegExp.prototype[Symbol.replace] which
// doesn't properly call the underlying exec method.
V8_WARN_UNUSED_RESULT MaybeDirectHandle<String> RegExpReplace(
Isolate* isolate, DirectHandle<JSRegExp> regexp,
DirectHandle<String> string, DirectHandle<String> replace) {
// Functional fast-paths are dispatched directly by replace builtin.
DCHECK(regexp::Utils::IsUnmodifiedRegExp(isolate, regexp));
Factory* factory = isolate->factory();
const int flags = regexp->flags();
const bool global = (flags & JSRegExp::kGlobal) != 0;
const bool sticky = (flags & JSRegExp::kSticky) != 0;
replace = String::Flatten(isolate, replace);
DirectHandle<RegExpMatchInfo> last_match_info =
isolate->regexp_last_match_info();
DirectHandle<RegExpData> data(regexp->data(isolate), isolate);
if (!global) {
// Non-global regexp search, string replace.
uint32_t last_index = 0;
if (sticky) {
DirectHandle<Object> last_index_obj(regexp->last_index(), isolate);
ASSIGN_RETURN_ON_EXCEPTION(isolate, last_index_obj,
Object::ToLength(isolate, last_index_obj));
last_index = PositiveNumberToUint32(*last_index_obj);
}
DirectHandle<Object> match_indices_obj(ReadOnlyRoots(isolate).null_value(),
isolate);
// A lastIndex exceeding the string length always returns null (signalling
// failure) in RegExpBuiltinExec, thus we can skip the call.
if (last_index <= static_cast<uint32_t>(string->length())) {
ASSIGN_RETURN_ON_EXCEPTION(
isolate, match_indices_obj,
RegExp::Exec_Single(isolate, regexp, string, last_index,
last_match_info));
}
if (IsNull(*match_indices_obj)) {
if (sticky) regexp->set_last_index(Smi::zero(), SKIP_WRITE_BARRIER);
return string;
}
auto match_indices = Cast<RegExpMatchInfo>(match_indices_obj);
const int start_index = match_indices->capture(0);
const int end_index = match_indices->capture(1);
if (sticky) {
regexp->set_last_index(Smi::FromInt(end_index), SKIP_WRITE_BARRIER);
}
IncrementalStringBuilder builder(isolate);
builder.AppendString(factory->NewSubString(string, 0, start_index));
if (replace->length() > 0) {
MatchInfoBackedMatch m(isolate, regexp, data, string, match_indices);
DirectHandle<String> replacement;
ASSIGN_RETURN_ON_EXCEPTION(isolate, replacement,
String::GetSubstitution(isolate, &m, replace));
builder.AppendString(replacement);
}
builder.AppendString(
factory->NewSubString(string, end_index, string->length()));
return builder.Finish();
} else {
// Global regexp search, string replace.
DCHECK(global);
RETURN_ON_EXCEPTION(isolate,
regexp::Utils::SetLastIndex(isolate, regexp, 0));
// Force tier up to native code for global replaces. The global replace is
// implemented differently for native code and bytecode execution, where the
// native code expects an array to store all the matches, and the bytecode
// matches one at a time, so it's easier to tier-up to native code from the
// start.
if (v8_flags.regexp_tier_up &&
data->type_tag() == RegExpData::Type::IRREGEXP) {
TrustedCast<IrRegExpData>(data)->MarkTierUpForNextExec();
if (v8_flags.trace_regexp_tier_up) {
PrintF("Forcing tier-up of JSRegExp object %p in RegExpReplace\n",
reinterpret_cast<void*>(regexp->ptr()));
}
}
if (replace->length() == 0) {
if (string->IsOneByteRepresentation()) {
Tagged<UnionOf<ExceptionHole, String>> result =
StringReplaceGlobalRegExpWithEmptyString<SeqOneByteString>(
isolate, string, regexp, data, last_match_info);
return direct_handle(Cast<String>(result), isolate);
} else {
Tagged<UnionOf<ExceptionHole, String>> result =
StringReplaceGlobalRegExpWithEmptyString<SeqTwoByteString>(
isolate, string, regexp, data, last_match_info);
return direct_handle(Cast<String>(result), isolate);
}
}
Tagged<UnionOf<ExceptionHole, String>> result =
StringReplaceGlobalRegExpWithString(isolate, string, regexp, data,
replace, last_match_info);
if (IsExceptionHole(result)) {
return MaybeDirectHandle<String>();
} else {
return direct_handle(Cast<String>(result), isolate);
}
}
UNREACHABLE();
}
} // namespace
// This is only called for StringReplaceGlobalRegExpWithFunction.
RUNTIME_FUNCTION(Runtime_RegExpExecMultiple) {
HandleScope handles(isolate);
DCHECK_EQ(3, args.length());
DirectHandle<JSRegExp> regexp = args.at<JSRegExp>(0);
DirectHandle<String> subject = args.at<String>(1);
DirectHandle<RegExpMatchInfo> last_match_info = args.at<RegExpMatchInfo>(2);
DCHECK(regexp::Utils::IsUnmodifiedRegExp(isolate, regexp));
DirectHandle<RegExpData> regexp_data(regexp->data(isolate), isolate);
subject = String::Flatten(isolate, subject);
CHECK(regexp->flags() & JSRegExp::kGlobal);
Tagged<UnionOf<ExceptionHole, Null, FixedArray>> result;
if (regexp_data->capture_count() == 0) {
result = SearchRegExpMultiple<false>(isolate, subject, regexp, regexp_data,
last_match_info);
} else {
result = SearchRegExpMultiple<true>(isolate, subject, regexp, regexp_data,
last_match_info);
}
DCHECK(regexp::Utils::IsUnmodifiedRegExp(isolate, regexp));
return result;
}
RUNTIME_FUNCTION(Runtime_StringReplaceNonGlobalRegExpWithFunction) {
HandleScope scope(isolate);
DCHECK_EQ(3, args.length());
DirectHandle<String> subject = args.at<String>(0);
DirectHandle<JSRegExp> regexp = args.at<JSRegExp>(1);
DirectHandle<JSReceiver> replace_obj = args.at<JSReceiver>(2);
DCHECK(regexp::Utils::IsUnmodifiedRegExp(isolate, regexp));
DCHECK(replace_obj->map()->is_callable());
Factory* factory = isolate->factory();
DirectHandle<RegExpMatchInfo> last_match_info =
isolate->regexp_last_match_info();
DirectHandle<RegExpData> data(regexp->data(isolate), isolate);
const int flags = regexp->flags();
DCHECK_EQ(flags & JSRegExp::kGlobal, 0);
// TODO(jgruber): This should be an easy port to CSA with massive payback.
const bool sticky = (flags & JSRegExp::kSticky) != 0;
uint32_t last_index = 0;
if (sticky) {
DirectHandle<Object> last_index_obj(regexp->last_index(), isolate);
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, last_index_obj, Object::ToLength(isolate, last_index_obj));
last_index = PositiveNumberToUint32(*last_index_obj);
}
DirectHandle<Object> match_indices_obj(ReadOnlyRoots(isolate).null_value(),
isolate);
// A lastIndex exceeding the string length always returns null (signalling
// failure) in RegExpBuiltinExec, thus we can skip the call.
if (last_index <= static_cast<uint32_t>(subject->length())) {
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, match_indices_obj,
RegExp::Exec_Single(isolate, regexp, subject, last_index,
last_match_info));
}
if (IsNull(*match_indices_obj)) {
if (sticky) regexp->set_last_index(Smi::zero(), SKIP_WRITE_BARRIER);
return *subject;
}
auto match_indices = Cast<RegExpMatchInfo>(match_indices_obj);
const int index = match_indices->capture(0);
const int end_of_match = match_indices->capture(1);
if (sticky) {
regexp->set_last_index(Smi::FromInt(end_of_match), SKIP_WRITE_BARRIER);
}
IncrementalStringBuilder builder(isolate);
builder.AppendString(factory->NewSubString(subject, 0, index));
// Compute the parameter list consisting of the match, captures, index,
// and subject for the replace function invocation. If the RegExp contains
// named captures, they are also passed as the last argument.
// The number of captures plus one for the match.
const int m = match_indices->number_of_capture_registers() / 2;
bool has_named_captures = false;
DirectHandle<TrustedFixedArray> capture_map;
if (m > 1) {
DirectHandle<IrRegExpData> re_data = SbxCast<IrRegExpData>(data);
if (re_data->has_capture_name_map()) {
has_named_captures = true;
capture_map = direct_handle(re_data->capture_name_map(), isolate);
}
}
const uint32_t argc = GetArgcForReplaceCallable(m, has_named_captures);
if (argc == static_cast<uint32_t>(-1)) {
THROW_NEW_ERROR_RETURN_FAILURE(
isolate, NewRangeError(MessageTemplate::kTooManyArguments));
}
DirectHandleVector<Object> arguments(isolate, argc);
int cursor = 0;
for (int j = 0; j < m; j++) {
bool ok;
DirectHandle<String> capture =
regexp::Utils::GenericCaptureGetter(isolate, match_indices, j, &ok);
if (ok) {
arguments[cursor++] = capture;
} else {
arguments[cursor++] = factory->undefined_value();
}
}
arguments[cursor++] = direct_handle(Smi::FromInt(index), isolate);
arguments[cursor++] = subject;
if (has_named_captures) {
arguments[cursor++] = ConstructNamedCaptureGroupsObject(
isolate, capture_map, [&arguments](int ix) { return *arguments[ix]; });
}
DCHECK_EQ(cursor, argc);
DirectHandle<Object> replacement_obj;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, replacement_obj,
Execution::Call(isolate, replace_obj, factory->undefined_value(),
base::VectorOf(arguments)));
DirectHandle<String> replacement;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, replacement, Object::ToString(isolate, replacement_obj));
builder.AppendString(replacement);
builder.AppendString(
factory->NewSubString(subject, end_of_match, subject->length()));
RETURN_RESULT_OR_FAILURE(isolate, builder.Finish());
}
namespace {
V8_WARN_UNUSED_RESULT MaybeDirectHandle<Object> ToUint32(
Isolate* isolate, DirectHandle<Object> object, uint32_t* out) {
if (IsUndefined(*object)) {
*out = kMaxUInt32;
return object;
}
DirectHandle<Object> number;
ASSIGN_RETURN_ON_EXCEPTION(isolate, number,
Object::ToNumber(isolate, object));
*out = NumberToUint32(*number);
return object;
}
DirectHandle<JSArray> NewJSArrayWithElements(Isolate* isolate,
DirectHandle<FixedArray> elems,
int num_elems) {
return isolate->factory()->NewJSArrayWithElements(
FixedArray::RightTrimOrEmpty(isolate, elems, num_elems));
}
} // namespace
// Slow path for:
// https://tc39.es/ecma262/#sec-regexp.prototype-@@split
// RegExp.prototype [ @@split ] ( string, limit )
RUNTIME_FUNCTION(Runtime_RegExpSplit) {
HandleScope scope(isolate);
DCHECK_EQ(3, args.length());
DirectHandle<JSReceiver> recv = args.at<JSReceiver>(0);
DirectHandle<String> string = args.at<String>(1);
DirectHandle<Object> limit_obj = args.at(2);
Factory* factory = isolate->factory();
DirectHandle<JSFunction> regexp_fun = isolate->regexp_function();
DirectHandle<Object> ctor;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, ctor, Object::SpeciesConstructor(isolate, recv, regexp_fun));
if (!ctor.is_identical_to(regexp_fun)) {
isolate->CountUsage(v8::Isolate::kRegExpCustomSpecies);
}
DirectHandle<Object> flags_obj;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, flags_obj,
JSReceiver::GetProperty(isolate, recv, factory->flags_string()));
DirectHandle<String> flags;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, flags,
Object::ToString(isolate, flags_obj));
DirectHandle<String> u_str =
factory->LookupSingleCharacterStringFromCode('u');
DirectHandle<String> v_str =
factory->LookupSingleCharacterStringFromCode('v');
const bool unicode = (String::IndexOf(isolate, flags, u_str, 0) >= 0 ||
String::IndexOf(isolate, flags, v_str, 0) >= 0);
DirectHandle<String> y_str =
factory->LookupSingleCharacterStringFromCode('y');
const bool sticky = (String::IndexOf(isolate, flags, y_str, 0) >= 0);
DirectHandle<String> new_flags = flags;
if (!sticky) {
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, new_flags,
factory->NewConsString(flags, y_str));
}
DirectHandle<JSReceiver> splitter;
{
constexpr int argc = 2;
std::array<DirectHandle<Object>, argc> ctor_args = {recv, new_flags};
DirectHandle<Object> splitter_obj;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, splitter_obj,
Execution::New(isolate, ctor, base::VectorOf(ctor_args)));
splitter = Cast<JSReceiver>(splitter_obj);
if (IsJSRegExp(*splitter)) {
JSRegExp::Flags splitter_flags = Cast<JSRegExp>(*splitter)->flags();
bool splitter_sticky = (splitter_flags & JSRegExp::kSticky) != 0;
bool splitter_unicode =
(splitter_flags & (JSRegExp::kUnicode | JSRegExp::kUnicodeSets)) != 0;
if (!splitter_sticky || splitter_unicode != unicode) {
isolate->CountUsage(v8::Isolate::kRegExpMatcherFlagsMismatch);
}
} else {
isolate->CountUsage(v8::Isolate::kRegExpMatcherFlagsMismatch);
}
}
uint32_t limit;
RETURN_FAILURE_ON_EXCEPTION(isolate, ToUint32(isolate, limit_obj, &limit));
const uint32_t length = string->length();
if (limit == 0) return *factory->NewJSArray(0);
if (length == 0) {
DirectHandle<Object> result;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, result,
regexp::Utils::RegExpExec(isolate, splitter, string,
factory->undefined_value()));
if (!IsNull(*result)) return *factory->NewJSArray(0);
DirectHandle<FixedArray> elems = factory->NewFixedArray(1);
elems->set(0, *string);
return *factory->NewJSArrayWithElements(elems);
}
static const int kInitialArraySize = 8;
DirectHandle<FixedArray> elems =
factory->NewFixedArrayWithHoles(kInitialArraySize);
uint32_t num_elems = 0;
uint32_t string_index = 0;
uint32_t prev_string_index = 0;
while (string_index < length) {
RETURN_FAILURE_ON_EXCEPTION(
isolate, regexp::Utils::SetLastIndex(isolate, splitter, string_index));
DirectHandle<JSAny> result;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, result,
regexp::Utils::RegExpExec(isolate, splitter, string,
factory->undefined_value()));
if (IsNull(*result)) {
string_index = static_cast<uint32_t>(
regexp::Utils::AdvanceStringIndex(*string, string_index, unicode));
continue;
}
DirectHandle<Object> last_index_obj;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, last_index_obj,
regexp::Utils::GetLastIndex(isolate, splitter));
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, last_index_obj, Object::ToLength(isolate, last_index_obj));
const uint32_t end =
std::min(PositiveNumberToUint32(*last_index_obj), length);
if (end == prev_string_index) {
string_index = static_cast<uint32_t>(
regexp::Utils::AdvanceStringIndex(*string, string_index, unicode));
continue;
}
{
DirectHandle<String> substr =
factory->NewSubString(string, prev_string_index, string_index);
elems = FixedArray::SetAndGrow(isolate, elems, num_elems++, substr);
if (num_elems == limit) {
return *NewJSArrayWithElements(isolate, elems, num_elems);
}
}
prev_string_index = end;
DirectHandle<Object> num_captures_obj;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, num_captures_obj,
Object::GetProperty(isolate, result,
isolate->factory()->length_string()));
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, num_captures_obj, Object::ToLength(isolate, num_captures_obj));
const uint32_t num_captures = PositiveNumberToUint32(*num_captures_obj);
for (uint32_t i = 1; i < num_captures; i++) {
DirectHandle<Object> capture;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, capture, Object::GetElement(isolate, result, i));
elems = FixedArray::SetAndGrow(isolate, elems, num_elems++, capture);
if (num_elems == limit) {
return *NewJSArrayWithElements(isolate, elems, num_elems);
}
}
string_index = prev_string_index;
}
{
DirectHandle<String> substr =
factory->NewSubString(string, prev_string_index, length);
elems = FixedArray::SetAndGrow(isolate, elems, num_elems++, substr);
}
return *NewJSArrayWithElements(isolate, elems, num_elems);
}
namespace {
template <typename Char>
inline bool IsContainFlagImpl(Isolate* isolate, base::Vector<const Char> flags,
const char* target,
DisallowGarbageCollection& no_gc) {
StringSearch<uint8_t, Char> search(isolate, base::OneByteVector(target));
return search.Search(flags, 0) >= 0;
}
inline bool IsContainFlag(Isolate* isolate, String::FlatContent& flags,
const char* target,
DisallowGarbageCollection& no_gc) {
return flags.IsOneByte()
? IsContainFlagImpl<uint8_t>(isolate, flags.ToOneByteVector(),
target, no_gc)
: IsContainFlagImpl<base::uc16>(isolate, flags.ToUC16Vector(),
target, no_gc);
}
} // namespace
// Slow path for:
// https://tc39.es/ecma262/#sec-regexp.prototype-@@replace
// RegExp.prototype [ @@replace ] ( string, replaceValue )
RUNTIME_FUNCTION(Runtime_RegExpReplaceRT) {
HandleScope scope(isolate);
DCHECK_EQ(3, args.length());
DirectHandle<JSReceiver> recv = args.at<JSReceiver>(0);
DirectHandle<String> string = args.at<String>(1);
DirectHandle<Object> replace_obj = args.at(2);
Factory* factory = isolate->factory();
string = String::Flatten(isolate, string);
const bool functional_replace = IsCallable(*replace_obj);
DirectHandle<String> replace;
if (!functional_replace) {
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, replace,
Object::ToString(isolate, replace_obj));
}
// Fast-path for unmodified JSRegExps (and non-functional replace).
if (regexp::Utils::IsUnmodifiedRegExp(isolate, recv)) {
// We should never get here with functional replace because unmodified
// regexp and functional replace should be fully handled in CSA code.
CHECK(!functional_replace);
DirectHandle<Object> result;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, result,
RegExpReplace(isolate, Cast<JSRegExp>(recv), string, replace));
DCHECK(regexp::Utils::IsUnmodifiedRegExp(isolate, recv));
return *result;
}
const uint32_t length = string->length();
bool global = false;
bool fullUnicode = false;
DirectHandle<Object> flags_obj;
DirectHandle<String> flag_str;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, flags_obj,
JSReceiver::GetProperty(isolate, recv, factory->flags_string()));
// 7. Let flags be ? ToString(? Get(rx, "flags")).
// 8. If flags contains "g", let global be true. Otherwise, let global be
// false.
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, flag_str,
Object::ToString(isolate, flags_obj));
flag_str = String::Flatten(isolate, flag_str);
{
DisallowGarbageCollection no_gc;
String::FlatContent flat_flag = flag_str->GetFlatContent(no_gc);
global = IsContainFlag(isolate, flat_flag, "g", no_gc);
if (global) {
// b. If flags contains "u" or flags contains "v", let fullUnicode be
// true. Otherwise, let fullUnicode be false.
fullUnicode = IsContainFlag(isolate, flat_flag, "u", no_gc) ||
IsContainFlag(isolate, flat_flag, "v", no_gc);
}
}
if (global) {
RETURN_FAILURE_ON_EXCEPTION(isolate,
regexp::Utils::SetLastIndex(isolate, recv, 0));
}
DirectHandleSmallVector<JSAny, kStaticVectorSlots> results(isolate);
while (true) {
DirectHandle<JSAny> result;
{
HandleScope inner_scope(isolate);
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, result,
regexp::Utils::RegExpExec(isolate, recv, string,
factory->undefined_value()));
result = inner_scope.CloseAndEscape(result);
}
if (IsNull(*result)) break;
results.emplace_back(result);
if (!global) break;
{
HandleScope inner_scope(isolate);
DirectHandle<Object> match_obj;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, match_obj, Object::GetElement(isolate, result, 0));
DirectHandle<String> match;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match,
Object::ToString(isolate, match_obj));
if (match->length() == 0) {
RETURN_FAILURE_ON_EXCEPTION(isolate,
regexp::Utils::SetAdvancedStringIndex(
isolate, recv, string, fullUnicode));
}
}
}
// TODO(jgruber): Look into ReplacementStringBuilder instead.
IncrementalStringBuilder builder(isolate);
uint32_t next_source_position = 0;
for (const auto& result : results) {
HandleScope handle_scope(isolate);
DirectHandle<Object> captures_length_obj;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, captures_length_obj,
Object::GetProperty(isolate, result, factory->length_string()));
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, captures_length_obj,
Object::ToLength(isolate, captures_length_obj));
const uint32_t captures_length =
PositiveNumberToUint32(*captures_length_obj);
DirectHandle<Object> match_obj;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match_obj,
Object::GetElement(isolate, result, 0));
DirectHandle<String> match;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match,
Object::ToString(isolate, match_obj));
const int match_length = match->length();
DirectHandle<Object> position_obj;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, position_obj,
Object::GetProperty(isolate, result, factory->index_string()));
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, position_obj, Object::ToInteger(isolate, position_obj));
const uint32_t position =
std::min(PositiveNumberToUint32(*position_obj), length);
// Do not reserve capacity since captures_length is user-controlled.
DirectHandleSmallVector<Object, kStaticVectorSlots> captures(isolate);
captures.emplace_back(match);
for (uint32_t n = 1; n < captures_length; n++) {
DirectHandle<Object> capture;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, capture, Object::GetElement(isolate, result, n));
if (!IsUndefined(*capture)) {
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, capture,
Object::ToString(isolate, capture));
}
captures.emplace_back(capture);
}
DirectHandle<Object> groups_obj = isolate->factory()->undefined_value();
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, groups_obj,
Object::GetProperty(isolate, result, factory->groups_string()));
const bool has_named_captures = !IsUndefined(*groups_obj);
DirectHandle<String> replacement;
if (functional_replace) {
// The first argument is always match string itself. So min argc value
// should be 1.
const uint32_t argc = GetArgcForReplaceCallable(
static_cast<uint32_t>(captures.size()), has_named_captures);
if (argc == static_cast<uint32_t>(-1)) {
THROW_NEW_ERROR_RETURN_FAILURE(
isolate, NewRangeError(MessageTemplate::kTooManyArguments));
}
DirectHandleVector<Object> call_args(isolate, argc);
int cursor = 0;
for (uint32_t j = 0; j < captures.size(); j++) {
call_args[cursor++] = captures[j];
}
call_args[cursor++] = direct_handle(Smi::FromInt(position), isolate);
call_args[cursor++] = string;
if (has_named_captures) call_args[cursor++] = groups_obj;
DCHECK_EQ(cursor, argc);
DirectHandle<Object> replacement_obj;
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, replacement_obj,
Execution::Call(isolate, replace_obj, factory->undefined_value(),
base::VectorOf(call_args)));
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, replacement, Object::ToString(isolate, replacement_obj));
} else {
DCHECK(!functional_replace);
if (!IsUndefined(*groups_obj)) {
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, groups_obj, Object::ToObject(isolate, groups_obj));
}
VectorBackedMatch m(isolate, string, match, position,
base::VectorOf(captures), groups_obj);
ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
isolate, replacement, String::GetSubstitution(isolate, &m, replace));
}
if (position >= next_source_position) {
builder.AppendString(
factory->NewSubString(string, next_source_position, position));
builder.AppendString(replacement);
next_source_position = position + match_length;
}
}
if (next_source_position < length) {
builder.AppendString(
factory->NewSubString(string, next_source_position, length));
}
RETURN_RESULT_OR_FAILURE(isolate, builder.Finish());
}
RUNTIME_FUNCTION(Runtime_RegExpInitializeAndCompile) {
HandleScope scope(isolate);
DCHECK_EQ(3, args.length());
// TODO(pwong): To follow the spec more closely and simplify calling code,
// this could handle the canonicalization of pattern and flags. See
// https://tc39.es/ecma262/#sec-regexpinitialize
DirectHandle<JSRegExp> regexp = args.at<JSRegExp>(0);
DirectHandle<String> source = args.at<String>(1);
DirectHandle<String> flags = args.at<String>(2);
RETURN_FAILURE_ON_EXCEPTION(
isolate, JSRegExp::Initialize(isolate, regexp, source, flags));
return *regexp;
}
RUNTIME_FUNCTION(Runtime_RegExpStringFromFlags) {
HandleScope scope(isolate);
DCHECK_EQ(1, args.length());
auto regexp = Cast<JSRegExp>(args[0]);
DirectHandle<String> flags =
JSRegExp::StringFromFlags(isolate, regexp->flags());
return *flags;
}
namespace {
template <typename SChar, typename PChar>
inline void RegExpMatchGlobalAtom_OneCharPattern(
Isolate* isolate, base::Vector<const SChar> subject, const PChar pattern,
int start_index, uint32_t* number_of_matches, int* last_match_index,
const DisallowGarbageCollection& no_gc) {
static_assert(std::is_unsigned_v<SChar>);
static_assert(std::is_unsigned_v<PChar>);
// We can utilize SIMD to check multiple characters at once.
// Since the pattern is a single char, we create a mask setting each lane in
// the vector to the pattern char.
// Since reductions from a vector to a general purpose register (i.e.
// ReduceSum in this algorithm) are expensive, we keep a count for each lane
// in a vector until the count could potentially overflow and only reduce to
// a general purpose register then. I.e. if SChar is uint8_t, we have a
// 16xuint8_t vector to count matches, which we reduce to an int every 255
// blocks.
namespace hw = hwy::HWY_NAMESPACE;
hw::ScalableTag<SChar> tag;
// We need a wider tag to avoid overflows on lanes when summing up submatches.
using WidenedTag = hw::RepartitionToWide<decltype(tag)>;
WidenedTag sum_tag;
static const size_t stride = hw::Lanes(tag);
// Subtle: the valid variants are {SChar,PChar} in:
// {uint8_t,uint8_t}, {uc16,uc16}, {uc16,uint8_t}. In the latter case,
// we cast the uint8_t pattern to uc16 for the comparison.
const auto mask = hw::Set(tag, static_cast<const SChar>(pattern));
int matches = 0;
auto submatches = hw::Zero(tag);
const SChar* last_match_block = nullptr;
hw::Mask<decltype(tag)> last_match_vec;
const SChar* block = subject.data() + start_index;
const SChar* end = subject.data() + subject.length();
// ReduceSum is expensive, so we gather matches into a vector. max_count is
// the maximum number of matches we can count in the vector before it
// overflows.
int max_count = std::numeric_limits<SChar>::max();
while (stride * max_count <= static_cast<size_t>(end - block)) {
for (int i = 0; i < max_count; i++, block += stride) {
const auto input = hw::LoadU(tag, block);
// TODO(floitsch): use an operator for the comparison when it is available
// on RISC-V.
const auto match = hw::Eq(input, mask);
// Lanes with matches have all bits set, so we subtract to increase the
// count by 1.
submatches = hw::Sub(submatches, hw::VecFromMask(tag, match));
if (!hw::AllFalse(tag, match)) {
last_match_block = block;
last_match_vec = match;
}
}
// SumsOf2 promotes the sum of 2 consecutive lanes into a wider lane.
auto promoted_submatches = hw::SumsOf2(submatches);
// Wider lane sums can be reduces without overflows.
matches += hw::ReduceSum(sum_tag, promoted_submatches);
submatches = hw::Zero(tag);
}
// For blocks shorter than stride * max_count, lanes in submatches can't
// overflow.
DCHECK_LT(end - block, stride * max_count);
for (; stride <= static_cast<size_t>(end - block); block += stride) {
const auto input = hw::LoadU(tag, block);
// TODO(floitsch): use an operator for the comparison when it is available
// on RISC-V.
const auto match = hw::Eq(input, mask);
submatches = hw::Sub(submatches, hw::VecFromMask(tag, match));
if (!hw::AllFalse(tag, match)) {
last_match_block = block;
last_match_vec = match;
}
}
auto promoted_submatches = hw::SumsOf2(submatches);
matches += hw::ReduceSum(sum_tag, promoted_submatches);
// Handle remaining chars.
// last_match_block already contains the last match position, so use a special
// vector with lane 0 set to extract the last_match_index later.
const auto scalar_last_match_vec = hw::FirstN(tag, 1);
for (; block < end; ++block) {
SChar c = *block;
if (c != static_cast<const SChar>(pattern)) continue;
matches++;
last_match_block = block;
last_match_vec = scalar_last_match_vec;
}
// Store results.
*number_of_matches += matches;
if (last_match_block != nullptr) {
DCHECK(!hw::AllFalse(tag, last_match_vec));
*last_match_index = static_cast<int>(
last_match_block + hw::FindKnownLastTrue(tag, last_match_vec) -
subject.data());
}
}
// Unimplemented.
template <>
inline void RegExpMatchGlobalAtom_OneCharPattern(
Isolate* isolate, base::Vector<const uint8_t> subject,
const base::uc16 pattern, int start_index, uint32_t* number_of_matches,
int* last_match_index, const DisallowGarbageCollection& no_gc) = delete;
template <typename Char>
inline int AdvanceStringIndex(base::Vector<const Char> subject, int index,
bool is_unicode) {
// Taken from regexp::Utils::AdvanceStringIndex:
const int subject_length = subject.length();
if (is_unicode && index < subject_length) {
const uint16_t first = subject[index];
if (first >= 0xD800 && first <= 0xDBFF && index + 1 < subject_length) {
DCHECK_LT(index, std::numeric_limits<int>::max());
const uint16_t second = subject[index + 1];
if (second >= 0xDC00 && second <= 0xDFFF) {
return index + 2;
}
}
}
return index + 1;
}
template <typename SChar, typename PChar>
inline void RegExpMatchGlobalAtom_Generic(
Isolate* isolate, base::Vector<const SChar> subject,
base::Vector<const PChar> pattern, bool is_unicode, int start_index,
uint32_t* number_of_matches, int* last_match_index,
const DisallowGarbageCollection& no_gc) {
const int pattern_length = pattern.length();
StringSearch<PChar, SChar> search(isolate, pattern);
int found_at_index;
while (true) {
found_at_index = search.Search(subject, start_index);
if (found_at_index == -1) return;
(*number_of_matches)++;
(*last_match_index) = found_at_index;
start_index = pattern_length > 0
? found_at_index + pattern_length
: AdvanceStringIndex(subject, start_index, is_unicode);
}
}
inline void RegExpMatchGlobalAtom_Dispatch(
Isolate* isolate, const String::FlatContent& subject,
const String::FlatContent& pattern, bool is_unicode, int start_index,
uint32_t* number_of_matches, int* last_match_index,
const DisallowGarbageCollection& no_gc) {
#define CALL_Generic() \
RegExpMatchGlobalAtom_Generic(isolate, sv, pv, is_unicode, start_index, \
number_of_matches, last_match_index, no_gc);
#define CALL_OneCharPattern() \
RegExpMatchGlobalAtom_OneCharPattern(isolate, sv, pv[0], start_index, \
number_of_matches, last_match_index, \
no_gc);
DCHECK_NOT_NULL(number_of_matches);
DCHECK_NOT_NULL(last_match_index);
if (pattern.IsOneByte()) {
auto pv = pattern.ToOneByteVector();
if (subject.IsOneByte()) {
auto sv = subject.ToOneByteVector();
if (pattern.length() == 1) {
CALL_OneCharPattern();
} else {
CALL_Generic();
}
} else {
auto sv = subject.ToUC16Vector();
if (pattern.length() == 1) {
CALL_OneCharPattern();
} else {
CALL_Generic();
}
}
} else {
auto pv = pattern.ToUC16Vector();
if (subject.IsOneByte()) {
auto sv = subject.ToOneByteVector();
CALL_Generic();
} else {
auto sv = subject.ToUC16Vector();
if (pattern.length() == 1) {
CALL_OneCharPattern();
} else {
CALL_Generic();
}
}
}
#undef CALL_OneCharPattern
#undef CALL_Generic
}
} // namespace
RUNTIME_FUNCTION(Runtime_RegExpMatchGlobalAtom) {
HandleScope scope(isolate);
DCHECK_EQ(3, args.length());
DirectHandle<JSRegExp> regexp_handle = args.at<JSRegExp>(0);
DirectHandle<String> subject_handle =
String::Flatten(isolate, args.at<String>(1));
DirectHandle<AtomRegExpData> data_handle =
SbxCast<AtomRegExpData>(TrustedCast<TrustedObject>(args.at<Object>(2)));
DCHECK(regexp::Utils::IsUnmodifiedRegExp(isolate, regexp_handle));
DCHECK(regexp_handle->flags() & JSRegExp::kGlobal);
DCHECK_EQ(data_handle->type_tag(), RegExpData::Type::ATOM);
// Initialized below.
DirectHandle<String> pattern_handle;
int pattern_length;
uint32_t number_of_matches = 0;
int last_match_index = -1;
{
DisallowGarbageCollection no_gc;
Tagged<JSRegExp> regexp = *regexp_handle;
Tagged<String> subject = *subject_handle;
Tagged<String> pattern = data_handle->pattern();
DCHECK(pattern->IsFlat());
pattern_handle = direct_handle(pattern, isolate);
pattern_length = pattern->length();
// Reset lastIndex (the final state after this call is always 0).
regexp->set_last_index(Smi::zero(), SKIP_WRITE_BARRIER);
// Caching.
int start_index = 0; // Start matching at the beginning.
if (regexp::ResultsCache_MatchGlobalAtom::TryGet(
isolate, subject, pattern, &number_of_matches, &last_match_index)) {
DCHECK_GT(number_of_matches, 0);
DCHECK_NE(last_match_index, -1);
start_index = last_match_index + pattern_length;
}
const bool is_unicode = (regexp->flags() & JSRegExp::kUnicode) != 0;
String::FlatContent subject_content = subject->GetFlatContent(no_gc);
String::FlatContent pattern_content = pattern->GetFlatContent(no_gc);
RegExpMatchGlobalAtom_Dispatch(isolate, subject_content, pattern_content,
is_unicode, start_index, &number_of_matches,
&last_match_index, no_gc);
if (last_match_index == -1) {
// Not matched.
return ReadOnlyRoots(isolate).null_value();
}
// Successfully matched at least once:
DCHECK_GE(last_match_index, 0);
// Caching.
regexp::ResultsCache_MatchGlobalAtom::TryInsert(
isolate, subject, pattern, number_of_matches, last_match_index);
}
// Update the LastMatchInfo.
static constexpr int kNumberOfCaptures = 0; // ATOM.
int32_t match_indices[] = {last_match_index,
last_match_index + pattern_length};
DirectHandle<RegExpMatchInfo> last_match_info =
isolate->regexp_last_match_info();
RegExp::SetLastMatchInfo(isolate, last_match_info, subject_handle,
kNumberOfCaptures, match_indices);
// Create the result array.
auto elems = isolate->factory()->NewFixedArray(number_of_matches);
ObjectSlot dst_slot = elems->RawFieldOfFirstElement();
MemsetTagged(dst_slot, *pattern_handle, number_of_matches);
if (!HeapLayout::InReadOnlySpace(*pattern_handle)) {
WriteBarrier::ForRange(isolate->heap(), *elems, dst_slot,
dst_slot + number_of_matches);
}
DirectHandle<JSArray> result = isolate->factory()->NewJSArrayWithElements(
elems, TERMINAL_FAST_ELEMENTS_KIND, number_of_matches);
return *result;
}
} // namespace internal
} // namespace v8