// Copyright 2016 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/strings/uri.h"

#include <algorithm>
#include <cstring>
#include <limits>
#include <new>
#include <vector>

#include "src/common/globals.h"
#include "src/execution/isolate-inl.h"
#include "src/strings/char-predicates-inl.h"
#include "src/strings/string-search.h"
#include "src/strings/unicode-inl.h"

namespace v8 {
namespace internal {

namespace {  // anonymous namespace for DecodeURI helper functions
bool IsReservedPredicate(base::uc16 c) {
  switch (c) {
    case '#':
    case '$':
    case '&':
    case '+':
    case ',':
    case '/':
    case ':':
    case ';':
    case '=':
    case '?':
    case '@':
      return true;
    default:
      return false;
  }
}

bool IsReplacementCharacter(const uint8_t* octets, int length) {
  // The replacement character is at codepoint U+FFFD in the Unicode Specials
  // table. Its UTF-8 encoding is 0xEF 0xBF 0xBD.
  if (length != 3 || octets[0] != 0xEF || octets[1] != 0xBF ||
      octets[2] != 0xBD) {
    return false;
  }
  return true;
}

bool DecodeOctets(const uint8_t* octets, int length,
                  std::vector<base::uc16>* buffer) {
  size_t cursor = 0;
  base::uc32 value = unibrow::Utf8::ValueOf(octets, length, &cursor);
  if (value == unibrow::Utf8::kBadChar &&
      !IsReplacementCharacter(octets, length)) {
    return false;
  }

  if (value <=
      static_cast<base::uc32>(unibrow::Utf16::kMaxNonSurrogateCharCode)) {
    buffer->push_back(value);
  } else {
    buffer->push_back(unibrow::Utf16::LeadSurrogate(value));
    buffer->push_back(unibrow::Utf16::TrailSurrogate(value));
  }
  return true;
}

int TwoDigitHex(base::uc16 character1, base::uc16 character2) {
  if (character1 > 'f') return -1;
  int high = base::HexValue(character1);
  if (high == -1) return -1;
  if (character2 > 'f') return -1;
  int low = base::HexValue(character2);
  if (low == -1) return -1;
  return (high << 4) + low;
}

template <typename T>
void AddToBuffer(base::uc16 decoded, String::FlatContent* uri_content,
                 int index, bool is_uri, std::vector<T>* buffer) {
  if (is_uri && IsReservedPredicate(decoded)) {
    buffer->push_back('%');
    base::uc16 first = uri_content->Get(index + 1);
    base::uc16 second = uri_content->Get(index + 2);
    DCHECK_GT(std::numeric_limits<T>::max(), first);
    DCHECK_GT(std::numeric_limits<T>::max(), second);

    buffer->push_back(first);
    buffer->push_back(second);
  } else {
    buffer->push_back(decoded);
  }
}

bool IntoTwoByte(int index, bool is_uri, int uri_length,
                 String::FlatContent* uri_content,
                 std::vector<base::uc16>* buffer) {
  for (int k = index; k < uri_length; k++) {
    base::uc16 code = uri_content->Get(k);
    if (code == '%') {
      int two_digits;
      if (k + 2 >= uri_length ||
          (two_digits = TwoDigitHex(uri_content->Get(k + 1),
                                    uri_content->Get(k + 2))) < 0) {
        return false;
      }
      k += 2;
      base::uc16 decoded = static_cast<base::uc16>(two_digits);
      if (decoded > unibrow::Utf8::kMaxOneByteChar) {
        uint8_t octets[unibrow::Utf8::kMaxEncodedSize];
        octets[0] = decoded;

        int number_of_continuation_bytes = 0;
        while ((decoded << ++number_of_continuation_bytes) & 0x80) {
          if (number_of_continuation_bytes > 3 || k + 3 >= uri_length) {
            return false;
          }
          if (uri_content->Get(++k) != '%' ||
              (two_digits = TwoDigitHex(uri_content->Get(k + 1),
                                        uri_content->Get(k + 2))) < 0) {
            return false;
          }
          k += 2;
          base::uc16 continuation_byte = static_cast<base::uc16>(two_digits);
          octets[number_of_continuation_bytes] = continuation_byte;
        }

        if (!DecodeOctets(octets, number_of_continuation_bytes, buffer)) {
          return false;
        }
      } else {
        AddToBuffer(decoded, uri_content, k - 2, is_uri, buffer);
      }
    } else {
      buffer->push_back(code);
    }
  }
  return true;
}

bool IntoOneAndTwoByte(DirectHandle<String> uri, bool is_uri,
                       std::vector<uint8_t>* one_byte_buffer,
                       std::vector<base::uc16>* two_byte_buffer) {
  DisallowGarbageCollection no_gc;
  String::FlatContent uri_content = uri->GetFlatContent(no_gc);

  int uri_length = uri->length();
  for (int k = 0; k < uri_length; k++) {
    base::uc16 code = uri_content.Get(k);
    if (code == '%') {
      int two_digits;
      if (k + 2 >= uri_length ||
          (two_digits = TwoDigitHex(uri_content.Get(k + 1),
                                    uri_content.Get(k + 2))) < 0) {
        return false;
      }

      base::uc16 decoded = static_cast<base::uc16>(two_digits);
      if (decoded > unibrow::Utf8::kMaxOneByteChar) {
        return IntoTwoByte(k, is_uri, uri_length, &uri_content,
                           two_byte_buffer);
      }

      AddToBuffer(decoded, &uri_content, k, is_uri, one_byte_buffer);
      k += 2;
    } else {
      if (code > unibrow::Utf8::kMaxOneByteChar) {
        return IntoTwoByte(k, is_uri, uri_length, &uri_content,
                           two_byte_buffer);
      }
      one_byte_buffer->push_back(code);
    }
  }
  return true;
}

}  // anonymous namespace

MaybeDirectHandle<String> Uri::Decode(Isolate* isolate,
                                      DirectHandle<String> uri, bool is_uri) {
  uri = String::Flatten(isolate, uri);
  std::vector<uint8_t> one_byte_buffer;
  std::vector<base::uc16> two_byte_buffer;

  if (!IntoOneAndTwoByte(uri, is_uri, &one_byte_buffer, &two_byte_buffer)) {
    THROW_NEW_ERROR(isolate, NewURIError());
  }

  if (two_byte_buffer.empty()) {
    return isolate->factory()->NewStringFromOneByte(base::Vector<const uint8_t>(
        one_byte_buffer.data(), static_cast<int>(one_byte_buffer.size())));
  }

  DirectHandle<SeqTwoByteString> result;
  int result_length =
      static_cast<int>(one_byte_buffer.size() + two_byte_buffer.size());
  ASSIGN_RETURN_ON_EXCEPTION(
      isolate, result, isolate->factory()->NewRawTwoByteString(result_length));

  DisallowGarbageCollection no_gc;
  base::uc16* chars = result->GetChars(no_gc);
  if (!one_byte_buffer.empty()) {
    CopyChars(chars, one_byte_buffer.data(), one_byte_buffer.size());
    chars += one_byte_buffer.size();
  }
  if (!two_byte_buffer.empty()) {
    CopyChars(chars, two_byte_buffer.data(), two_byte_buffer.size());
  }

  return result;
}

namespace {

template <typename T>
class ResizableBuffer {
 public:
  explicit ResizableBuffer(size_t initial_capacity, size_t max_capacity)
      : data_(new T[initial_capacity]),
        capacity_(initial_capacity),
        size_(0),
        max_capacity_(max_capacity) {
    DCHECK_LE(capacity_, max_capacity_);
    // Check that `max_capacity_` is not so large that `capacity_ * 2`
    // could overflow.
    DCHECK_LE(max_capacity_, std::numeric_limits<size_t>::max() / 2);
  }

  ~ResizableBuffer() { delete[] data_; }

  ResizableBuffer(const ResizableBuffer&) = delete;
  ResizableBuffer& operator=(const ResizableBuffer&) = delete;

  template <typename... Args>
  bool TryPushBack(Args... args) {
    constexpr size_t arg_count = sizeof...(args);
    if (V8_UNLIKELY(size_ + arg_count > capacity_)) {
      if (!TryExpand(arg_count)) return false;
    }
    ((data_[size_++] = args), ...);
    return true;
  }

  const T* data() const { return data_; }
  size_t size() const { return size_; }

 private:
  V8_PRESERVE_MOST bool TryExpand(size_t required_size) {
    size_t minimum_capacity = size_ + required_size;
    size_t new_capacity =
        std::min(capacity_ * 2 + required_size, max_capacity_);
    if (new_capacity < minimum_capacity) return false;

    T* new_data = new T[new_capacity];
    std::memcpy(new_data, data_, size_ * sizeof(T));
    delete[] data_;
    data_ = new_data;
    capacity_ = new_capacity;
    return true;
  }

  T* data_;
  size_t capacity_;
  size_t size_;
  const size_t max_capacity_;
};

bool IsUnescapePredicateInUriComponent(base::uc16 c) {
  if (IsAlphaNumeric(c)) {
    return true;
  }

  switch (c) {
    case '!':
    case '\'':
    case '(':
    case ')':
    case '*':
    case '-':
    case '.':
    case '_':
    case '~':
      return true;
    default:
      return false;
  }
}

bool IsUriSeparator(base::uc16 c) {
  switch (c) {
    case '#':
    case ':':
    case ';':
    case '/':
    case '?':
    case '$':
    case '&':
    case '+':
    case ',':
    case '@':
    case '=':
      return true;
    default:
      return false;
  }
}

bool AddEncodedOctetToBuffer(uint8_t octet, ResizableBuffer<uint8_t>* buffer) {
  return buffer->TryPushBack('%', base::HexCharOfValue(octet >> 4),
                             base::HexCharOfValue(octet & 0x0F));
}

bool Encode(unibrow::uchar c, ResizableBuffer<uint8_t>* buffer) {
  char s[4] = {};
  int number_of_bytes =
      unibrow::Utf8::Encode(s, c, unibrow::Utf16::kNoPreviousCharacter, false);
  for (int k = 0; k < number_of_bytes; k++) {
    if (!AddEncodedOctetToBuffer(s[k], buffer)) return false;
  }
  return true;
}

enum class EncodeStatus { kSuccess, kUriError, kAllocationFailure };

V8_NODISCARD EncodeStatus
EncodeHelperOneByte(base::Vector<const uint8_t> uri_content, bool is_uri,
                    ResizableBuffer<uint8_t>* buffer) {
  for (uint8_t c : uri_content) {
    if (IsUnescapePredicateInUriComponent(c) || (is_uri && IsUriSeparator(c))) {
      if (!buffer->TryPushBack(c)) {
        return EncodeStatus::kAllocationFailure;
      }
    } else {
      if (!Encode(c, buffer)) {
        return EncodeStatus::kAllocationFailure;
      }
    }
  }
  return EncodeStatus::kSuccess;
}

V8_NODISCARD EncodeStatus
EncodeHelperTwoByte(base::Vector<const base::uc16> uri_content, bool is_uri,
                    ResizableBuffer<uint8_t>* buffer) {
  for (int k = 0; k < uri_content.length(); k++) {
    base::uc16 cc1 = uri_content[k];
    if (unibrow::Utf16::IsLeadSurrogate(cc1)) {
      k++;
      if (k >= uri_content.length()) {
        // A lead surrogate was found without a tail surrogate.
        return EncodeStatus::kUriError;
      }
      base::uc16 cc2 = uri_content[k];
      if (!unibrow::Utf16::IsTrailSurrogate(cc2)) {
        // A lead surrogate was found without a tail surrogate.
        return EncodeStatus::kUriError;
      }

      if (!Encode(unibrow::Utf16::CombineSurrogatePair(cc1, cc2), buffer)) {
        return EncodeStatus::kAllocationFailure;
      }
      continue;
    }

    if (unibrow::Utf16::IsTrailSurrogate(cc1)) {
      // A tail surrogate was found without a preceding lead surrogate.
      return EncodeStatus::kUriError;
    }

    if (IsUnescapePredicateInUriComponent(cc1) ||
        (is_uri && IsUriSeparator(cc1))) {
      if (!buffer->TryPushBack(cc1)) {
        return EncodeStatus::kAllocationFailure;
      }
    } else {
      if (!Encode(cc1, buffer)) {
        return EncodeStatus::kAllocationFailure;
      }
    }
  }
  return EncodeStatus::kSuccess;
}

V8_NODISCARD EncodeStatus EncodeHelper(DirectHandle<String> uri, bool is_uri,
                                       ResizableBuffer<uint8_t>* buffer) {
  DisallowGarbageCollection no_gc;
  String::FlatContent uri_content = uri->GetFlatContent(no_gc);
  if (uri_content.IsOneByte()) {
    return EncodeHelperOneByte(uri_content.ToOneByteVector(), is_uri, buffer);
  }
  return EncodeHelperTwoByte(uri_content.ToUC16Vector(), is_uri, buffer);
}

}  // anonymous namespace

MaybeDirectHandle<String> Uri::Encode(Isolate* isolate,
                                      DirectHandle<String> uri, bool is_uri) {
  uri = String::Flatten(isolate, uri);
  ResizableBuffer<uint8_t> buffer(uri->length(), v8::String::kMaxLength);

  EncodeStatus status = EncodeHelper(uri, is_uri, &buffer);

  switch (status) {
    case EncodeStatus::kSuccess:
      return isolate->factory()->NewStringFromOneByte(base::VectorOf(buffer));
    case EncodeStatus::kUriError:
      THROW_NEW_ERROR(isolate, NewURIError());
    case EncodeStatus::kAllocationFailure:
      THROW_NEW_ERROR(isolate, NewInvalidStringLengthError());
  }
}

namespace {  // Anonymous namespace for Escape and Unescape

template <typename Char>
int UnescapeChar(base::Vector<const Char> vector, int i, int length,
                 int* step) {
  uint16_t character = vector[i];
  int32_t hi = 0;
  int32_t lo = 0;
  if (character == '%' && i <= length - 6 && vector[i + 1] == 'u' &&
      (hi = TwoDigitHex(vector[i + 2], vector[i + 3])) > -1 &&
      (lo = TwoDigitHex(vector[i + 4], vector[i + 5])) > -1) {
    *step = 6;
    return (hi << 8) + lo;
  } else if (character == '%' && i <= length - 3 &&
             (lo = TwoDigitHex(vector[i + 1], vector[i + 2])) > -1) {
    *step = 3;
    return lo;
  } else {
    *step = 1;
    return character;
  }
}

template <typename Char>
MaybeHandle<String> UnescapeSlow(Isolate* isolate, DirectHandle<String> string,
                                 int start_index) {
  bool one_byte = true;
  uint32_t length = string->length();

  int unescaped_length = 0;
  {
    DisallowGarbageCollection no_gc;
    base::Vector<const Char> vector = string->GetCharVector<Char>(no_gc);
    for (uint32_t i = start_index; i < length; unescaped_length++) {
      int step;
      if (UnescapeChar(vector, i, length, &step) >
          String::kMaxOneByteCharCode) {
        one_byte = false;
      }
      i += step;
    }
  }

  DCHECK_LT(start_index, length);
  Handle<String> first_part =
      isolate->factory()->NewProperSubString(string, 0, start_index);

  int dest_position = 0;
  Handle<String> second_part;
  DCHECK_LE(unescaped_length, String::kMaxLength);
  if (one_byte) {
    Handle<SeqOneByteString> dest = isolate->factory()
                                        ->NewRawOneByteString(unescaped_length)
                                        .ToHandleChecked();
    DisallowGarbageCollection no_gc;
    base::Vector<const Char> vector = string->GetCharVector<Char>(no_gc);
    for (uint32_t i = start_index; i < length; dest_position++) {
      int step;
      dest->SeqOneByteStringSet(dest_position,
                                UnescapeChar(vector, i, length, &step));
      i += step;
    }
    second_part = dest;
  } else {
    Handle<SeqTwoByteString> dest = isolate->factory()
                                        ->NewRawTwoByteString(unescaped_length)
                                        .ToHandleChecked();
    DisallowGarbageCollection no_gc;
    base::Vector<const Char> vector = string->GetCharVector<Char>(no_gc);
    for (uint32_t i = start_index; i < length; dest_position++) {
      int step;
      dest->SeqTwoByteStringSet(dest_position,
                                UnescapeChar(vector, i, length, &step));
      i += step;
    }
    second_part = dest;
  }
  return isolate->factory()->NewConsString(first_part, second_part);
}

bool IsNotEscaped(uint16_t c) {
  if (IsAlphaNumeric(c)) {
    return true;
  }
  //  @*_+-./
  switch (c) {
    case '@':
    case '*':
    case '_':
    case '+':
    case '-':
    case '.':
    case '/':
      return true;
    default:
      return false;
  }
}

template <typename Char>
static MaybeHandle<String> UnescapePrivate(Isolate* isolate,
                                           Handle<String> source) {
  int index;
  {
    DisallowGarbageCollection no_gc;
    StringSearch<uint8_t, Char> search(isolate, base::StaticOneByteVector("%"));
    index = search.Search(source->GetCharVector<Char>(no_gc), 0);
    if (index < 0) return source;
  }
  return UnescapeSlow<Char>(isolate, source, index);
}

template <typename Char>
static MaybeHandle<String> EscapePrivate(Isolate* isolate,
                                         Handle<String> string) {
  DCHECK(string->IsFlat());
  uint32_t escaped_length = 0;
  uint32_t length = string->length();

  {
    DisallowGarbageCollection no_gc;
    base::Vector<const Char> vector = string->GetCharVector<Char>(no_gc);
    for (uint32_t i = 0; i < length; i++) {
      uint16_t c = vector[i];
      if (c >= 256) {
        escaped_length += 6;
      } else if (IsNotEscaped(c)) {
        escaped_length++;
      } else {
        escaped_length += 3;
      }

      // We don't allow strings that are longer than a maximal length.
      DCHECK_LT(String::kMaxLength, 0x7FFFFFFF - 6);   // Cannot overflow.
      if (escaped_length > String::kMaxLength) break;  // Provoke exception.
    }
  }

  // No length change implies no change.  Return original string if no change.
  if (escaped_length == length) return string;

  Handle<SeqOneByteString> dest;
  ASSIGN_RETURN_ON_EXCEPTION(
      isolate, dest, isolate->factory()->NewRawOneByteString(escaped_length));
  int dest_position = 0;

  {
    DisallowGarbageCollection no_gc;
    base::Vector<const Char> vector = string->GetCharVector<Char>(no_gc);
    for (uint32_t i = 0; i < length; i++) {
      uint16_t c = vector[i];
      if (c >= 256) {
        dest->SeqOneByteStringSet(dest_position, '%');
        dest->SeqOneByteStringSet(dest_position + 1, 'u');
        dest->SeqOneByteStringSet(dest_position + 2,
                                  base::HexCharOfValue(c >> 12));
        dest->SeqOneByteStringSet(dest_position + 3,
                                  base::HexCharOfValue((c >> 8) & 0xF));
        dest->SeqOneByteStringSet(dest_position + 4,
                                  base::HexCharOfValue((c >> 4) & 0xF));
        dest->SeqOneByteStringSet(dest_position + 5,
                                  base::HexCharOfValue(c & 0xF));
        dest_position += 6;
      } else if (IsNotEscaped(c)) {
        dest->SeqOneByteStringSet(dest_position, c);
        dest_position++;
      } else {
        dest->SeqOneByteStringSet(dest_position, '%');
        dest->SeqOneByteStringSet(dest_position + 1,
                                  base::HexCharOfValue(c >> 4));
        dest->SeqOneByteStringSet(dest_position + 2,
                                  base::HexCharOfValue(c & 0xF));
        dest_position += 3;
      }
    }
  }

  return dest;
}

}  // anonymous namespace

MaybeDirectHandle<String> Uri::Escape(Isolate* isolate, Handle<String> string) {
  string = String::Flatten(isolate, string);
  return String::IsOneByteRepresentationUnderneath(*string)
             ? EscapePrivate<uint8_t>(isolate, string)
             : EscapePrivate<base::uc16>(isolate, string);
}

MaybeDirectHandle<String> Uri::Unescape(Isolate* isolate,
                                        Handle<String> string) {
  string = String::Flatten(isolate, string);
  return String::IsOneByteRepresentationUnderneath(*string)
             ? UnescapePrivate<uint8_t>(isolate, string)
             : UnescapePrivate<base::uc16>(isolate, string);
}

}  // namespace internal
}  // namespace v8