string-replaceall.tq 8.03 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2019 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 'src/builtins/builtins-string-gen.h'

namespace string {
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
extern macro ReplaceSymbolConstant(): Symbol;

extern macro StringBuiltinsAssembler::GetSubstitution(
    implicit context: Context)(String, Smi, Smi, String): String;

extern builtin
StringIndexOf(implicit context: Context)(String, String, Smi): Smi;

macro TryFastAbstractStringIndexOf(implicit context: Context)(
    string: String, searchString: String, fromIndex: Smi): Smi labels Slow {
  const stringLen = string.length_uintptr;
  const searchLen = searchString.length_uintptr;
  const directString = Cast<DirectString>(string) otherwise Slow;
  const directSearchStr = Cast<DirectString>(searchString) otherwise Slow;
  const fromIndexUint = Unsigned(SmiUntag(fromIndex));

  for (let i: uintptr = fromIndexUint; i < stringLen; i++) {
    let j = i;
    let k: uintptr = 0;
    while (j < stringLen && k < searchLen &&
           StringCharCodeAt(directString, j) ==
               StringCharCodeAt(directSearchStr, k)) {
      j++;
      k++;
    }
    if (k == searchLen) {
      return SmiTag(Signed(i));
35 36
    }
  }
37 38
  return -1;
}
39

40 41 42 43 44 45 46 47
macro AbstractStringIndexOf(implicit context: Context)(
    string: String, searchString: String, fromIndex: Smi): Smi {
  // Special case the empty string.
  const searchStringLength = searchString.length_intptr;
  const stringLength = string.length_intptr;
  if (searchStringLength == 0 && SmiUntag(fromIndex) <= stringLength) {
    return fromIndex;
  }
48

49 50 51 52 53 54
  // Don't bother to search if the searchString would go past the end
  // of the string. This is actually necessary because of runtime
  // checks.
  if (SmiUntag(fromIndex) + searchStringLength > stringLength) {
    return -1;
  }
55

56 57 58 59 60 61 62 63 64 65
  try {
    return TryFastAbstractStringIndexOf(string, searchString, fromIndex)
        otherwise Slow;
  } label Slow {
    for (let i: intptr = SmiUntag(fromIndex);
         i + searchStringLength <= stringLength; i++) {
      if (StringCompareSequence(
              context, string, searchString, Convert<Number>(SmiTag(i))) ==
          True) {
        return SmiTag(i);
66 67
      }
    }
68
    return -1;
69
  }
70
}
71

72 73 74 75 76 77
transitioning macro
ThrowIfNotGlobal(implicit context: Context)(searchValue: JSAny): void {
  let shouldThrow: bool;
  typeswitch (searchValue) {
    case (fastRegExp: FastJSRegExp): {
      shouldThrow = !fastRegExp.global;
78
    }
79 80 81 82 83
    case (Object): {
      const flags = GetProperty(searchValue, 'flags');
      RequireObjectCoercible(flags, 'String.prototype.replaceAll');
      shouldThrow =
          StringIndexOf(ToString_Inline(flags), StringConstant('g'), 0) == -1;
84 85
    }
  }
86 87 88 89 90 91
  if (shouldThrow) {
    ThrowTypeError(
        MessageTemplate::kRegExpGlobalInvokedOnNonGlobal,
        'String.prototype.replaceAll');
  }
}
92

93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
// https://tc39.es/ecma262/#sec-string.prototype.replaceall
transitioning javascript builtin StringPrototypeReplaceAll(
    js-implicit context: NativeContext, receiver: JSAny)(
    searchValue: JSAny, replaceValue: JSAny): JSAny {
  // 1. Let O be ? RequireObjectCoercible(this value).
  RequireObjectCoercible(receiver, 'String.prototype.replaceAll');

  // 2. If searchValue is neither undefined nor null, then
  if (searchValue != Undefined && searchValue != Null) {
    // a. Let isRegExp be ? IsRegExp(searchString).
    // b. If isRegExp is true, then
    //   i. Let flags be ? Get(searchValue, "flags").
    //  ii. Perform ? RequireObjectCoercible(flags).
    // iii. If ? ToString(flags) does not contain "g", throw a
    //      TypeError exception.
    if (regexp::IsRegExp(searchValue)) {
      ThrowIfNotGlobal(searchValue);
110 111
    }

112 113 114 115 116 117 118 119 120 121 122
    // TODO(joshualitt): We could easily add fast paths for string
    //                   searchValues and potential FastRegExps.
    // c. Let replacer be ? GetMethod(searchValue, @@replace).
    // d. If replacer is not undefined, then
    //   i. Return ? Call(replacer, searchValue, « O, replaceValue »).
    try {
      const replacer = GetMethod(searchValue, ReplaceSymbolConstant())
          otherwise ReplaceSymbolIsNullOrUndefined;
      return Call(context, replacer, searchValue, receiver, replaceValue);
    } label ReplaceSymbolIsNullOrUndefined {}
  }
123

124 125
  // 3. Let string be ? ToString(O).
  const string = ToString_Inline(receiver);
126

127 128
  // 4. Let searchString be ? ToString(searchValue).
  const searchString = ToString_Inline(searchValue);
129

130 131 132
  // 5. Let functionalReplace be IsCallable(replaceValue).
  let replaceValueArg = replaceValue;
  const functionalReplace = Is<Callable>(replaceValue);
133

134 135 136 137 138
  // 6. If functionalReplace is false, then
  if (!functionalReplace) {
    // a. Let replaceValue be ? ToString(replaceValue).
    replaceValueArg = ToString_Inline(replaceValue);
  }
139

140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184
  // 7. Let searchLength be the length of searchString.
  const searchLength = searchString.length_smi;

  // 8. Let advanceBy be max(1, searchLength).
  const advanceBy = SmiMax(1, searchLength);

  // We combine the two loops from the spec into one to avoid
  // needing a growable array.
  //
  // 9. Let matchPositions be a new empty List.
  // 10. Let position be ! StringIndexOf(string, searchString, 0).
  // 11. Repeat, while position is not -1
  //   a. Append position to the end of matchPositions.
  //   b. Let position be ! StringIndexOf(string, searchString,
  //                                      position + advanceBy).
  // 12. Let endOfLastMatch be 0.
  // 13. Let result be the empty string value.
  // 14. For each position in matchPositions, do
  let endOfLastMatch: Smi = 0;
  let result: String = kEmptyString;
  let position = AbstractStringIndexOf(string, searchString, 0);
  while (position != -1) {
    // a. If functionalReplace is true, then
    // b. Else,
    let replacement: String;
    if (functionalReplace) {
      // i. Let replacement be ? ToString(? Call(replaceValue, undefined,
      //                                         « searchString, position,
      //                                           string »).
      replacement = ToString_Inline(Call(
          context, UnsafeCast<Callable>(replaceValueArg), Undefined,
          searchString, position, string));
    } else {
      // i. Assert: Type(replaceValue) is String.
      const replaceValueString = UnsafeCast<String>(replaceValueArg);

      // ii. Let captures be a new empty List.
      // iii. Let replacement be GetSubstitution(searchString,
      //                                         string, position, captures,
      //                                         undefined, replaceValue).
      // Note: Instead we just call a simpler GetSubstitution primitive.
      const matchEndPosition = position + searchLength;
      replacement = GetSubstitution(
          string, position, matchEndPosition, replaceValueString);
    }
185

186 187 188 189 190 191
    // c. Let stringSlice be the substring of string consisting of the code
    //    units from endOfLastMatch (inclusive) up through position
    //    (exclusive).
    const stringSlice = string::SubString(
        string, Unsigned(SmiUntag(endOfLastMatch)),
        Unsigned(SmiUntag(position)));
192

193 194 195 196 197
    // d. Let result be the string-concatenation of result, stringSlice,
    //    and replacement.
    // TODO(joshualitt): This leaves a completely degenerate ConsString tree.
    //                   We could be smarter here.
    result = result + stringSlice + replacement;
198

199 200
    // e. Let endOfLastMatch be position + searchLength.
    endOfLastMatch = position + searchLength;
201

202 203 204
    position =
        AbstractStringIndexOf(string, searchString, position + advanceBy);
  }
205

206 207 208 209 210 211 212 213 214
  // 15. If endOfLastMatch < the length of string, then
  if (endOfLastMatch < string.length_smi) {
    // a. Let result be the string-concatenation of result and the substring
    //    of string consisting of the code units from endOfLastMatch
    //    (inclusive) up through the final code unit of string (inclusive).
    result = result +
        string::SubString(
                 string, Unsigned(SmiUntag(endOfLastMatch)),
                 Unsigned(string.length_intptr));
215
  }
216 217 218 219

  // 16. Return result.
  return result;
}
220
}