// 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 {
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));
    }
  }
  return -1;
}

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;
  }

  // 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;
  }

  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);
      }
    }
    return -1;
  }
}

transitioning macro
ThrowIfNotGlobal(implicit context: Context)(searchValue: JSAny): void {
  let shouldThrow: bool;
  typeswitch (searchValue) {
    case (fastRegExp: FastJSRegExp): {
      shouldThrow = !fastRegExp.global;
    }
    case (Object): {
      const flags = GetProperty(searchValue, 'flags');
      RequireObjectCoercible(flags, 'String.prototype.replaceAll');
      shouldThrow =
          StringIndexOf(ToString_Inline(flags), StringConstant('g'), 0) == -1;
    }
  }
  if (shouldThrow) {
    ThrowTypeError(
        MessageTemplate::kRegExpGlobalInvokedOnNonGlobal,
        'String.prototype.replaceAll');
  }
}

// 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);
    }

    // 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 {}
  }

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

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

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

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

  // 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);
    }

    // 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)));

    // 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;

    // e. Let endOfLastMatch be position + searchLength.
    endOfLastMatch = position + searchLength;

    position =
        AbstractStringIndexOf(string, searchString, position + advanceBy);
  }

  // 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));
  }

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