text: // Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com)
  #include "objects.h"
  
  #include <cstring>
  
  #include "bytes-builtins.h"
  #include "byteslike.h"
  #include "frame.h"
  #include "runtime.h"
  #include "thread.h"
  #include "unicode.h"
  #include "view.h"
  
  namespace py {
  
  static inline word offset(const byte* data, word len, word index, word count) {
    if (count >= 0) {
      while (count-- && index < len) {
        index += UTF8::numChars(data[index]);
      }
      return Utils::minimum(index, len);
    }
    while (count < 0) {
      index--;
      if (index < 0) return -1;
      if (UTF8::isLeadByte(data[index])) count++;
    }
    return index;
  }
  
  static inline int32_t decodeCodePoint(const byte* data, word src_length,
                                        word index, word* char_length) {
    DCHECK_INDEX(index, src_length);
    byte b0 = data[index];
    if (b0 <= kMaxASCII) {
      *char_length = 1;
      return b0;
    }
    DCHECK_INDEX(index + 1, src_length);
    byte b1 = data[index + 1] & byte{0x3F};
    // 0b110xxxxx begins a sequence with one continuation byte.
    if (b0 < 0xE0) {
      DCHECK(b0 >= 0xC, "unexpected continuation byte");
      *char_length = 2;
      return ((b0 & 0x1F) << 6) | b1;
    }
    DCHECK_INDEX(index + 2, src_length);
    byte b2 = data[index + 2] & byte{0x3F};
    // 0b1110xxxx starts a sequence with two continuation bytes.
    if (b0 < 0xF0) {
      *char_length = 3;
      return ((b0 & 0xF) << 12) | (b1 << 6) | b2;
    }
    // 0b11110xxx starts a sequence with three continuation bytes.
    DCHECK((b0 & 0xF8) == 0xF0, "invalid code unit");
    DCHECK_INDEX(index + 2, src_length);
    byte b3 = data[index + 3] & byte{0x3F};
    *char_length = 4;
    return ((b0 & 0x7) << 18) | (b1 << 12) | (b2 << 6) | b3;
  }
  
  // RawSmallData
  
  int32_t RawSmallData::codePointAt(word index, word* char_length) const {
    const byte* data = smallDataData(this);
    return decodeCodePoint(data, length(), index, char_length);
  }
  
  word RawSmallData::codePointLength() const {
    uword block = raw() >> kBitsPerByte;
    uword mask_0 = ~uword{0} / 0xFF;  // 0x010101...
    uword mask_7 = mask_0 << 7;       // 0x808080...
    block = ((block & mask_7) >> 7) & ((~block) >> 6);
    // TODO(cshapiro): evaluate using popcount instead of multiplication
    word num_trailing = (block * mask_0) >> ((kWordSize - 1) * kBitsPerByte);
    return length() - num_trailing;
  }
  
  word RawSmallData::findByte(byte value, word start, word length) const {
    DCHECK_BOUND(start, this->length());
    DCHECK_BOUND(start + length, this->length());
    for (word i = 0; i < length; i++) {
      if (byteAt(start + i) == value) return start + i;
    }
    return -1;
  }
  
  static uword hasZeroByte(uword value) {
    uword mask_0 = ~uword{0} / 0xFF;  // 0x010101...
    uword mask_7 = mask_0 << 7;       // 0x808080...
    return (value - mask_0) & ~value & mask_7;
  }
  
  bool RawSmallData::includesByte(byte b) const {
    DCHECK(b != 0, "Due to padding bytes, cannot check for 0.");
    uword block = raw() >> kBitsPerByte;
    uword surrogate_mask = (~uword{0} / 0xFF) * b;
    return hasZeroByte(block ^ surrogate_mask);
  }
  
  bool RawSmallData::isASCII() const {
    uword block = raw() >> kBitsPerByte;
    uword non_ascii_mask = (~uword{0} / 0xFF) << (kBitsPerByte - 1);
    return (block & non_ascii_mask) == 0;
  }
  
  word RawSmallData::offsetByCodePoints(word index, word count) const {
    const byte* data = smallDataData(this);
    return offset(data, length(), index, count);
  }
  
  char* RawSmallData::toCStr() const {
    word length = this->length();
    byte* result = static_cast<byte*>(std::malloc(length + 1));
    CHECK(result != nullptr, "out of memory");
    copyTo(result, length);
    result[length] = '\0';
    return reinterpret_cast<char*>(result);
  }
  
  // RawSmallBytes
  
  RawObject RawSmallBytes::becomeStr() const {
    return RawObject{raw() ^ kSmallBytesTag ^ kSmallStrTag};
  }
  
  RawSmallBytes RawSmallBytes::fromBytes(View<byte> data) {
    word length = data.length();
    DCHECK_BOUND(length, kMaxLength);
    uword result = 0;
    for (word i = length - 1; i >= 0; i--) {
      result = (result << kBitsPerByte) | data.get(i);
    }
    return RawSmallBytes(result << kBitsPerByte | length << kImmediateTagBits |
                         kSmallBytesTag);
  }
  
  // RawSmallStr
  
  RawObject RawSmallStr::becomeBytes() const {
    return RawObject{raw() ^ kSmallStrTag ^ kSmallBytesTag};
  }
  
  word RawSmallStr::compare(RawObject that) const {
    word length = this->length();
    for (word i = 0; i < length; i++) {
      word result = byteAt(i) - RawLargeStr::cast(that).byteAt(i);
      if (result != 0) return result;
    }
    return -1;
  }
  
  word RawSmallStr::equalsCStr(const char* c_str) const {
    const char* cp = c_str;
    const word len = length();
    for (word i = 0; i < len; i++, cp++) {
      byte ch = static_cast<byte>(*cp);
      if (ch == '\0' || ch != byteAt(i)) {
        return false;
      }
    }
    return *cp == '\0';
  }
  
  RawSmallStr RawSmallStr::fromBytes(View<byte> data) {
    word length = data.length();
    DCHECK_BOUND(length, kMaxLength);
    uword result = 0;
    for (word i = length - 1; i >= 0; i--) {
      result = (result << kBitsPerByte) | data.get(i);
    }
    return RawSmallStr(result << kBitsPerByte | length << kImmediateTagBits |
                       kSmallStrTag);
  }
  
  RawSmallStr RawSmallStr::fromCodePoint(int32_t code_point) {
    DCHECK_BOUND(code_point, kMaxUnicode);
    uword cp = static_cast<uword>(code_point);
    // 0xxxxxxx
    if (cp <= kMaxASCII) {  // 01111111
      return RawSmallStr(cp << 8 | (1 << kImmediateTagBits) | kSmallStrTag);
    }
    uword result = cp & 0x3F;  // 00111111
    cp >>= 6;
    result <<= kBitsPerByte;
    // 110xxxxx 10xxxxxx
    if (cp <= 0x1F) {  // 00011111
      result |= cp;
      result |= 0x80C0;  // 10xxxxxx 110xxxxx
      result <<= kBitsPerByte;
      return RawSmallStr(result | (2 << kImmediateTagBits) | kSmallStrTag);
    }
  
    result |= cp & 0x3F;  // 00111111
    cp >>= 6;
    result <<= kBitsPerByte;
    // 1110xxxx 10xxxxxx 10xxxxxx
    if (cp <= 0xF) {  // 00001111
      result |= cp;
      result |= 0x8080E0;  // 10xxxxxx 10xxxxxx 1110xxxx
      result <<= kBitsPerByte;
      return RawSmallStr(result | (3 << kImmediateTagBits) | kSmallStrTag);
    }
    result |= cp & 0x3F;  // 00111111
    cp >>= 6;
    result <<= kBitsPerByte;
    // 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
    result |= cp;
    result |= 0x808080F0;  // 10xxxxxx 10xxxxxx 10xxxxxx 11110xxx
    result <<= kBitsPerByte;
    return RawSmallStr(result | (4 << kImmediateTagBits) | kSmallStrTag);
  }
  
  RawSmallStr RawSmallStr::fromCStr(const char* value) {
    word len = std::strlen(value);
    return fromBytes(View<byte>(reinterpret_cast<const byte*>(value), len));
  }
  
  bool RawSmallStr::includesByte(byte b) const {
    DCHECK(b != 0, "Due to padding bytes, cannot check for 0.");
    uword block = raw() >> kBitsPerByte;
    uword surrogate_mask = (~uword{0} / 0xFF) * b;
    return hasZeroByte(block ^ surrogate_mask);
  }
  
  bool RawSmallStr::includes(RawObject that) const {
    if (!that.isSmallStr()) {
      return false;
    }
    word haystack_len = length();
    word needle_len = SmallStr::cast(that).length();
    word diff = haystack_len - needle_len;
    if (diff < 0) {
      return false;
    }
    uword haystack = raw() >> kBitsPerByte;
    uword needle = that.raw() >> kBitsPerByte;
    uword mask = ~0UL >> ((kWordSize - needle_len) * kBitsPerByte);
    for (word i = 0; i <= diff; i++) {
      if ((haystack & mask) == needle) {
        return true;
      }
      haystack >>= kBitsPerByte;
    }
    return false;
  }
  
  word RawSmallStr::occurrencesOf(RawObject that) const {
    DCHECK(that.isStr(), "must be searching for a Str object");
    if (!that.isSmallStr()) {
      return 0;
    }
    word haystack_len = length();
    word needle_len = SmallStr::cast(that).length();
    DCHECK(needle_len >= 0, "needle length must be non-negative");
    if (needle_len == 0) {
      return 0;
    }
    word diff = haystack_len - needle_len;
    uword needle = that.raw() >> kBitsPerByte;
    uword haystack = raw() >> kBitsPerByte;
    uword mask = (1 << (needle_len * kBitsPerByte)) - 1;
    word result = 0;
    for (word i = 0; i <= diff; i++) {
      if ((haystack & mask) == needle) {
        result++;
        i += needle_len - 1;
        haystack >>= (kBitsPerByte * (needle_len - 1));
      }
      haystack >>= kBitsPerByte;
    }
    return result;
  }
  
  // RawSmallInt
  
  const word RawSmallInt::kMinValue;
  const word RawSmallInt::kMaxValue;
  
  // RawBytearray
  
  word RawBytearray::compare(RawBytes that, word that_len) {
    DCHECK_BOUND(that_len, that.length());
    word this_len = this->numItems();
    word len = Utils::minimum(this_len, that_len);
    for (word i = 0; i < len; i++) {
      word diff = this->byteAt(i) - that.byteAt(i);
      if (diff != 0) return diff;
    }
    return this_len - that_len;
  }
  
  void RawBytearray::downsize(word new_length) const {
    word original_length = numItems();
    DCHECK_BOUND(new_length, original_length);
    if (original_length == 0) return;
    byte* dst = reinterpret_cast<byte*>(RawMutableBytes::cast(items()).address());
    std::memset(dst + new_length, 0, original_length - new_length);
    setNumItems(new_length);
  }
  
  void RawBytearray::replaceFromWith(word dst_start, RawBytearray src,
                                     word count) const {
    DCHECK_BOUND(dst_start + count, numItems());
    MutableBytes::cast(items()).replaceFromWithBytes(
        dst_start, Bytes::cast(src.items()), count);
  }
  
  void RawBytearray::replaceFromWithStartAt(word dst_start, RawBytearray src,
                                            word count, word src_start) const {
    DCHECK_BOUND(dst_start + count, numItems());
    DCHECK_BOUND(src_start + count, src.numItems());
    MutableBytes::cast(items()).replaceFromWithBytesStartAt(
        dst_start, Bytes::cast(src.items()), count, src_start);
  }
  
  // RawBytes
  
  word RawBytes::compare(RawBytes that) const {
    word this_len = this->length();
    word that_len = that.length();
    word len = Utils::minimum(this_len, that_len);
    for (word i = 0; i < len; i++) {
      word diff = this->byteAt(i) - that.byteAt(i);
      if (diff != 0) return diff;
    }
    return this_len - that_len;
  }
  
  // RawCode
  
  word RawCode::offsetToLineNum(word offset) const {
    offset /= kCodeUnitScale;
    // See https://github.com/python/cpython/blob/master/Objects/lnotab_notes.txt
    // for details about the line number table format
    RawBytes table = Bytes::cast(lnotab());
    word line = firstlineno();
    word cur_offset = 0;
    for (word i = 0; i < table.length(); i += 2) {
      cur_offset += table.byteAt(i);
      if (cur_offset > offset) {
        break;
      }
      line += static_cast<int8_t>(table.byteAt(i + 1));
    }
    return line;
  }
  
  // RawDataArray
  
  static inline const byte* dataArrayData(RawDataArray obj) {
    return reinterpret_cast<const byte*>(obj.address());
  }
  
  int32_t RawDataArray::codePointAt(word index, word* char_length) const {
    const byte* data = dataArrayData(*this);
    return decodeCodePoint(data, length(), index, char_length);
  }
  
  word RawDataArray::codePointLength() const {
    // This is a vectorized loop for processing code units in groups the size of a
    // machine word.  The garbage collector ensures the following invariants that
    // simplify the algorithm, eliminating the need for a scalar pre-loop or a
    // scalar-post loop:
    //
    //   1) The base address of instance data is always word aligned
    //   2) The allocation sizes are always rounded-up to the next word
    //   3) Unused bytes at the end of an allocation are always zero
    //
    // This algorithm works by counting the number of UTF-8 trailing bytes found
    // in the string from the total number of byte in the string.  Because the
    // unused bytes at the end of a string are zero they are conveniently ignored
    // by the counting.
    word length = this->length();
    word size_in_words = (length + kWordSize - 1) >> kWordSizeLog2;
    word result = length;
    const uword* data = reinterpret_cast<const uword*>(dataArrayData(*this));
    uword mask_0 = ~uword{0} / 0xFF;  // 0x010101...
    uword mask_7 = mask_0 << 7;       // 0x808080...
    for (word i = 0; i < size_in_words; i++) {
      // Read an entire word of code units.
      uword block = data[i];
      // The bit pattern 0b10xxxxxx identifies a UTF-8 trailing byte.  For each
      // byte in a word, we isolate bit 6 and 7 and logically and the complement
      // of bit 6 with bit 7.  That leaves one set bit for each trailing byte in a
      // word.
      block = ((block & mask_7) >> 7) & ((~block) >> 6);
      // Count the number of bits leftover in the word.  That is equal to the
      // number of trailing bytes.
      // TODO(cshapiro): evaluate using popcount instead of multiplication
      word num_trailing = (block * mask_0) >> ((kWordSize - 1) * kBitsPerByte);
      // Finally, subtract the number of trailing bytes from the number of bytes
      // in the string leaving just the number of ASCII code points and UTF-8
      // leading bytes in the count.
      result -= num_trailing;
    }
    return result;
  }
  
  word RawDataArray::compare(RawDataArray that) const {
    word this_length = length();
    word that_length = that.length();
    word length = Utils::minimum(this_length, that_length);
    const void* s1 = reinterpret_cast<const void*>(address());
    const void* s2 = reinterpret_cast<const void*>(that.address());
    word result = std::memcmp(s1, s2, length);
    return result != 0 ? result : this_length - that_length;
  }
  
  bool RawDataArray::equals(RawDataArray that) const {
    word len = this->length();
    if (len != that.length()) {
      return false;
    }
    const void* s1 = reinterpret_cast<const void*>(address());
    const void* s2 = reinterpret_cast<const void*>(that.address());
    return std::memcmp(s1, s2, len) == 0;
  }
  
  bool RawDataArray::equalsBytes(View<byte> bytes) const {
    word length = this->length();
    if (bytes.length() != length) {
      return false;
    }
    return std::memcmp(dataArrayData(*this), bytes.data(), length) == 0;
  }
  
  bool RawDataArray::equalsCStr(const char* c_str) const {
    const char* cp = c_str;
    const word len = length();
    for (word i = 0; i < len; i++, cp++) {
      byte ch = static_cast<byte>(*cp);
      if (ch == '\0' || ch != byteAt(i)) {
        return false;
      }
    }
    return *cp == '\0';
  }
  
  word RawDataArray::findByte(byte value, word start, word length) const {
    DCHECK_BOUND(start, this->length());
    DCHECK_BOUND(start + length, this->length());
    word result =
        Utils::memoryFindChar(dataArrayData(*this) + start, length, value);
    if (result != -1) result += start;
    return result;
  }
  
  bool RawDataArray::includesByte(byte b) const {
    DCHECK(b != 0, "Due to padding bytes, cannot check for 0.");
    word length = this->length();
    word size_in_words = (length + kWordSize - 1) >> kWordSizeLog2;
    const uword* data = reinterpret_cast<const uword*>(dataArrayData(*this));
    uword mask = (~uword{0} / 0xFF) * b;
    for (word i = 0; i < size_in_words; i++) {
      uword block = data[i];
      if (hasZeroByte(block ^ mask)) {
        return true;
      }
    }
    return false;
  }
  
  bool RawDataArray::isASCII() const {
    // Depends on invariants specified in RawLargeStr::codePointLength
    word length = this->length();
    word size_in_words = (length + kWordSize - 1) >> kWordSizeLog2;
    const uword* data = reinterpret_cast<const uword*>(dataArrayData(*this));
    uword non_ascii_mask = (~uword{0} / 0xFF) << (kBitsPerByte - 1);
    for (word i = 0; i < size_in_words; i++) {
      // Read an entire word of code units.
      uword block = data[i];
      if ((block & non_ascii_mask) != 0) return false;
    }
    return true;
  }
  
  word RawDataArray::offsetByCodePoints(word index, word count) const {
    const byte* data = dataArrayData(*this);
    return offset(data, length(), index, count);
  }
  
  char* RawDataArray::toCStr() const {
    word length = this->length();
    byte* result = static_cast<byte*>(std::malloc(length + 1));
    CHECK(result != nullptr, "out of memory");
    copyTo(result, length);
    result[length] = '\0';
    return reinterpret_cast<char*>(result);
  }
  
  // RawLargeBytes
  
  RawObject RawLargeBytes::becomeStr() const {
    DCHECK(bytesIsValidStr(RawBytes::cast(*this)), "must contain valid utf-8");
    setHeader(header().withLayoutId(LayoutId::kLargeStr));
    return *this;
  }
  
  // RawLargeStr
  
  static bool includes1(const byte* haystack, word haystack_len, byte needle) {
    const uword* p = reinterpret_cast<const uword*>(haystack);
    uword mask = ((~0UL / 255) * needle);
    while (haystack_len >= kWordSize) {
      if (hasZeroByte(*p ^ mask)) {
        return true;
      }
      haystack_len -= kWordSize;
      p++;
    }
    if (haystack_len != 0) {
      word shift = (kWordSize - haystack_len) * kBitsPerByte;
      return (hasZeroByte(*p ^ mask) << shift) != 0;
    }
    return false;
  }
  
  bool RawLargeStr::includes(RawObject that) const {
    enum { kMask = kBitsPerWord - 1 };
  
    if (that == Str::empty()) {
      return true;
    }
  
    word haystack_len = length();
    word needle_len = Str::cast(that).length();
  
    word diff = haystack_len - needle_len;
    if (diff < 0) {
      return false;
    }
  
    const byte* haystack = dataArrayData(*this);
  
    if (needle_len == 1) {
      byte ch = SmallStr::cast(that).byteAt(0);
      return includes1(haystack, haystack_len, ch);
    }
  
    byte buffer[SmallStr::kMaxLength];
    const byte* needle;
    if (that.isSmallStr()) {
      SmallStr::cast(that).copyTo(buffer, needle_len);
      needle = buffer;
    } else {
      needle = dataArrayData(LargeStr::cast(that));
    }
  
    word needle_last = needle_len - 1;
    word skip = needle_last - 1;
    uword delta1 = 0;
    for (word i = 0; i < needle_last; i++) {
      delta1 |= (1 << (needle[i] & kMask));
      if (needle[i] == needle[needle_last]) {
        skip = needle_last - i - 1;
      }
    }
    delta1 |= (1 << (needle[needle_last] & kMask));
    for (word i = 0; i <= diff; i++) {
      if (haystack[i + needle_last] == needle[needle_last]) {
        word j = 0;
        for (; j < needle_last; j++) {
          if (haystack[i + j] != needle[j]) {
            break;
          }
        }
        if (j == needle_last) {
          return true;
        }
        if ((delta1 & (1 << (haystack[i + needle_len] & kMask))) == 0) {
          i += needle_len;
        } else {
          i += skip;
        }
      } else {
        if ((delta1 & (1 << (haystack[i + needle_len] & kMask))) == 0) {
          i += needle_len;
        }
      }
    }
    return false;
  }
  
  word RawLargeStr::occurrencesOf(RawObject that) const {
    DCHECK(that.isStr(), "must be searching for a Str object");
    const byte* needle;
    word needle_len;
    byte buffer[SmallStr::kMaxLength];
    if (that.isSmallStr()) {
      RawSmallStr str = RawSmallStr::cast(that);
      needle_len = str.length();
      str.copyTo(buffer, needle_len);
      needle = buffer;
    } else {
      RawLargeStr str = RawLargeStr::cast(that);
      needle = dataArrayData(str);
      needle_len = str.length();
    }
    DCHECK(needle != nullptr, "needle cannot be null");
    DCHECK(needle_len >= 0, "needle length must be non-negative");
    word haystack_len = length();
    const byte* haystack = dataArrayData(*this);
    if (haystack_len < needle_len) {
      return 0;
    }
    word result = 0;
    for (word pos = Utils::memoryFind(haystack, haystack_len, needle, needle_len);
         pos != -1 && pos + needle_len <= haystack_len; result++) {
      pos += needle_len;
      haystack += pos;
      haystack_len -= pos;
      pos = Utils::memoryFind(haystack, haystack_len, needle, needle_len);
    }
    return result;
  }
  
  // RawList
  
  void RawList::replaceFromWith(word start, RawList src, word count) const {
    DCHECK_BOUND(start + count, numItems());
    MutableTuple::cast(items()).replaceFromWith(start, Tuple::cast(src.items()),
                                                count);
  }
  
  void RawList::replaceFromWithStartAt(word start, RawList src, word count,
                                       word src_start) const {
    DCHECK_BOUND(start + count, numItems());
    DCHECK_BOUND(src_start + count, src.numItems());
    MutableTuple::cast(items()).replaceFromWithStartAt(
        start, Tuple::cast(src.items()), count, src_start);
  }
  
  // RawInt
  
  word RawInt::compare(RawInt that) const {
    if (this->isSmallInt() && that.isSmallInt()) {
      return this->asWord() - that.asWord();
    }
    // compare with large ints always returns -1, 0, or 1
    bool is_negative = this->isNegative();
    if (is_negative != that.isNegative()) {
      return is_negative ? -1 : 1;
    }
  
    word left_digits = this->numDigits();
    word right_digits = that.numDigits();
  
    if (left_digits > right_digits) {
      return is_negative ? -1 : 1;
    }
    if (left_digits < right_digits) {
      return is_negative ? 1 : -1;
    }
    for (word i = left_digits - 1; i >= 0; i--) {
      uword left_digit = this->digitAt(i);
      uword right_digit = that.digitAt(i);
      if (left_digit > right_digit) {
        return 1;
      }
      if (left_digit < right_digit) {
        return -1;
      }
    }
    return 0;
  }
  
  word RawInt::copyTo(byte* dst, word max_length) const {
    if (isLargeInt()) {
      return RawLargeInt::cast(*this).copyTo(dst, max_length);
    }
  
    DCHECK(isSmallInt() || isBool(), "not an integer");
    uword val = isSmallInt() ? RawSmallInt::cast(*this).value()
                             : RawBool::cast(*this).value();
    word memcpy_length = std::min(word{kWordSize}, max_length);
    std::memcpy(dst, &val, memcpy_length);
    return memcpy_length;
  }
  
  // RawLargeInt
  
  bool RawLargeInt::isValid() const {
    word digits = numDigits();
    if (digits <= 0) {
      return false;
    }
    if (digits == 1) {
      // Enforce a canonical representation for all ints.
      return !RawSmallInt::isValid(digitAt(0));
    }
  
    word high_digit = digitAt(digits - 1);
    word next_digit = digitAt(digits - 2);
  
    // Redundant sign-extension for negative values.
    if (high_digit == -1 && next_digit < 0) {
      return false;
    }
  
    // Redundant zero-extension for positive values.
    if (high_digit == 0 && next_digit >= 0) {
      return false;
    }
  
    return true;
  }
  
  word RawLargeInt::bitLength() const {
    word num_digits = numDigits();
    word high_digit = digitAt(num_digits - 1);
  
    if (high_digit < 0) {
      // We're negative. Calculate what high_digit would be after negation.
      uword carry = [&] {
        for (word i = 0; i < num_digits - 1; i++) {
          if (digitAt(i) != 0) return 0;
        }
        return 1;
      }();
      high_digit = ~high_digit + carry;
    }
    return (num_digits - 1) * kBitsPerWord + Utils::highestBit(high_digit);
  }
  
  word RawLargeInt::copyTo(byte* dst, word copy_length) const {
    word length = numDigits() * kWordSize;
    auto digits = reinterpret_cast<uword*>(address() + kValueOffset);
    word memcpy_size = std::min(length, copy_length);
    std::memcpy(dst, digits, memcpy_size);
    return memcpy_size;
  }
  
  void RawLargeInt::copyFrom(RawBytes bytes, byte sign_extension) const {
    auto dst = reinterpret_cast<byte*>(address() + kValueOffset);
    word bytes_len = bytes.length();
    DCHECK(bytes_len <= numDigits() * kWordSize, "too many bytes");
    bytes.copyTo(dst, bytes_len);
    std::memset(dst + bytes_len, sign_extension,
                (numDigits() * kWordSize) - bytes_len);
  }
  
  // RawMutableBytes
  
  word RawMutableBytes::indexOfAny(View<byte> needle, word start) const {
    DCHECK(needle.length() >= 0, "needle length must be non-negative");
    if (needle.length() == 0) {
      return length();
    }
    uword bitmap[(kMaxByte + 1) / kBitsPerWord] = {0};
    for (word i = 0; i < needle.length(); i++) {
      byte ch = needle.get(i);
      bitmap[ch / kBitsPerWord] |= uword{1} << (ch % kBitsPerWord);
    }
    word result;
    for (result = start; result < length(); result++) {
      byte ch = byteAt(result);
      if (bitmap[ch / kBitsPerWord] & (uword{1} << (ch % kBitsPerWord))) {
        break;
      }
    }
    return result;
  }
  
  void RawMutableBytes::replaceFromWith(word dst_start, RawDataArray src,
                                        word count) const {
    DCHECK_BOUND(dst_start + count, length());
    byte* dst = reinterpret_cast<byte*>(address());
    src.copyTo(dst + dst_start, count);
  }
  
  void RawMutableBytes::replaceFromWithStartAt(word dst_start, RawDataArray src,
                                               word count, word src_start) const {
    DCHECK_BOUND(dst_start + count, length());
    DCHECK_BOUND(src_start + count, src.length());
    src.copyToStartAt(reinterpret_cast<byte*>(address() + dst_start), count,
                      src_start);
  }
  
  void RawMutableBytes::replaceFromWithBytes(word dst_start, RawBytes src,
                                             word count) const {
    DCHECK_BOUND(dst_start + count, length());
    byte* dst = reinterpret_cast<byte*>(address());
    src.copyTo(dst + dst_start, count);
  }
  
  void RawMutableBytes::replaceFromWithByte(word dst_start, byte value,
                                            word count) const {
    DCHECK_BOUND(dst_start + count, length());
    byte* dst = reinterpret_cast<byte*>(address());
    std::memset(dst + dst_start, value, count);
  }
  
  void RawMutableBytes::replaceFromWithBytesStartAt(word dst_start, RawBytes src,
                                                    word count,
                                                    word src_start) const {
    DCHECK_BOUND(dst_start + count, length());
    DCHECK_BOUND(src_start + count, src.length());
    src.copyToStartAt(reinterpret_cast<byte*>(address() + dst_start), count,
                      src_start);
  }
  
  void RawMutableBytes::replaceFromWithAll(word dst_start, View<byte> src) const {
    DCHECK_BOUND(dst_start + src.length(), length());
    byte* dst = reinterpret_cast<byte*>(address());
    std::memcpy(dst + dst_start, src.data(), src.length());
  }
  
  void RawMutableBytes::replaceFromWithByteslike(word dst_start,
                                                 const Byteslike& byteslike,
                                                 word count) const {
    DCHECK_BOUND(count, byteslike.length());
    DCHECK_BOUND(dst_start, length() - count);
    byte* dst = reinterpret_cast<byte*>(address() + dst_start);
    const byte* src = reinterpret_cast<const byte*>(byteslike.address());
    std::memcpy(dst, src, count);
  }
  
  void RawMutableBytes::replaceFromWithByteslikeStartAt(
      word dst_start, const Byteslike& byteslike, word count,
      word src_start) const {
    DCHECK(count >= 0, "count must not be negative");
    DCHECK_BOUND(src_start, byteslike.length() - count);
    DCHECK_BOUND(dst_start, length() - count);
    byte* dst = reinterpret_cast<byte*>(address() + dst_start);
    const byte* src =
        reinterpret_cast<const byte*>(byteslike.address() + src_start);
    std::memcpy(dst, src, count);
  }
  
  void RawMutableBytes::replaceFromWithStr(word index, RawStr src,
                                           word char_length) const {
    DCHECK_BOUND(index + char_length, length());
    byte* dst = reinterpret_cast<byte*>(address());
    src.copyTo(dst + index, char_length);
  }
  
  void RawMutableBytes::replaceFromWithStrStartAt(word dst_start, RawStr src,
                                                  word char_length,
                                                  word src_start_char) const {
    DCHECK_BOUND(dst_start + char_length, length());
    byte* dst = reinterpret_cast<byte*>(address());
    src.copyToStartAt(dst + dst_start, char_length, src_start_char);
  }
  
  RawObject RawMutableBytes::becomeImmutable() const {
    word len = length();
    if (len <= SmallBytes::kMaxLength) {
      return SmallBytes::fromBytes({dataArrayData(*this), len});
    }
    setHeader(header().withLayoutId(LayoutId::kLargeBytes));
    return *this;
  }
  
  RawObject RawMutableBytes::becomeStr() const {
    DCHECK(bytesIsValidStr(RawBytes::cast(*this)), "must contain valid utf-8");
    word len = length();
    if (len <= SmallStr::kMaxLength) {
      return SmallStr::fromBytes({dataArrayData(*this), len});
    }
    setHeader(header().withLayoutId(LayoutId::kLargeStr));
    return *this;
  }
  
  // RawMutableTuple
  
  void RawMutableTuple::fill(RawObject value) const {
    word len = length();
    if (value.isNoneType()) {
      std::memset(reinterpret_cast<byte*>(address()), -1, len * kWordSize);
      return;
    }
    for (word i = 0; i < len; i++) {
      atPut(i, value);
    }
  }
  
  void RawMutableTuple::replaceFromWith(word dst_start, RawTuple src,
                                        word count) const {
    replaceFromWithStartAt(dst_start, src, count, 0);
  }
  
  void RawMutableTuple::replaceFromWithStartAt(word dst_start, RawTuple src,
                                               word count, word src_start) const {
    if (src != *this) {
      // No overlap
      for (word i = dst_start, j = src_start; count != 0; i++, j++, count--) {
        atPut(i, src.at(j));
      }
    } else if (src_start < dst_start) {
      // Overlap; copy backward
      for (word i = dst_start + count - 1, j = src_start + count - 1; count != 0;
           i--, j--, count--) {
        atPut(i, src.at(j));
      }
    } else if (src_start > dst_start) {
      // Overlap; copy forward
      for (word i = dst_start, j = src_start; count != 0; i++, j++, count--) {
        atPut(i, src.at(j));
      }
    }
  }
  
  // RawTuple
  
  bool RawTuple::contains(RawObject object) const {
    word len = length();
    for (word i = 0; i < len; i++) {
      if (at(i) == object) {
        return true;
      }
    }
    return false;
  }
  
  // RawSlice
  
  word RawSlice::length(word start, word stop, word step) {
    if (step < 0) {
      if (stop < start) {
        return (start - stop - 1) / (-step) + 1;
      }
    } else if (start < stop) {
      return (stop - start - 1) / step + 1;
    }
    return 0;
  }
  
  word RawSlice::adjustIndices(word length, word* start, word* stop, word step) {
    DCHECK(step != 0, "Step should be non zero");
  
    if (*start < 0) {
      *start += length;
      if (*start < 0) {
        *start = (step < 0) ? -1 : 0;
      }
    } else if (*start >= length) {
      *start = (step < 0) ? length - 1 : length;
    }
  
    if (*stop < 0) {
      *stop += length;
      if (*stop < 0) {
        *stop = (step < 0) ? -1 : 0;
      }
    } else if (*stop >= length) {
      *stop = (step < 0) ? length - 1 : length;
    }
  
    return RawSlice::length(*start, *stop, step);
  }
  
  void RawSlice::adjustSearchIndices(word* start, word* end, word length) {
    if (*start < 0) {
      *start = Utils::maximum(*start + length, word{0});
    }
    if (*end < 0) {
      *end = Utils::maximum(*end + length, word{0});
    } else if (*end > length) {
      *end = length;
    }
  }
  
  // RawStr
  
  word RawStr::compareCStr(const char* c_str) const {
    word c_length = std::strlen(c_str);
    word length = Utils::minimum(this->length(), c_length);
    for (word i = 0; i < length; i++) {
      word diff = byteAt(i) - static_cast<byte>(c_str[i]);
      if (diff != 0) {
        return (diff > 0) ? 1 : -1;
      }
    }
    word diff = this->length() - c_length;
    return (diff > 0) ? 1 : ((diff < 0) ? -1 : 0);
  }
  
  // RawStrArray
  
  int32_t RawStrArray::codePointAt(word index, word* char_length) const {
    RawMutableBytes buffer = RawMutableBytes::cast(items());
    return decodeCodePoint(dataArrayData(buffer), numItems(), index, char_length);
  }
  
  word RawStrArray::offsetByCodePoints(word index, word count) const {
    RawMutableBytes buffer = RawMutableBytes::cast(items());
    const byte* data = dataArrayData(buffer);
    return offset(data, numItems(), index, count);
  }
  
  void RawStrArray::rotateCodePoint(word first, word last) const {
    DCHECK_BOUND(first, last);
    DCHECK_INDEX(last, numItems());
    if (first == last) {
      return;
    }
  
    byte code_point[UTF8::kMaxLength];
    byte* buffer =
        reinterpret_cast<byte*>(RawMutableBytes::cast(items()).address());
    word char_length = UTF8::numChars(buffer[last]);
    std::memcpy(code_point, &buffer[last], char_length);
    std::memmove(&buffer[first + char_length], &buffer[first], last - first);
    std::memcpy(&buffer[first], code_point, char_length);
  }
  
  // Linked list helpers
  
  static void enqueueReference(RawObject reference, RawObject* tail,
                               word reference_link_offset,
                               word tail_link_offset) {
    DCHECK(Instance::cast(reference)
               .instanceVariableAt(reference_link_offset)
               .isNoneType(),
           "Attempting to enqueue object that's already in queue");
    if (*tail == RawNoneType::object()) {
      Instance::cast(reference).instanceVariableAtPut(reference_link_offset,
                                                      reference);
    } else {
      RawObject head = Instance::cast(*tail).instanceVariableAt(tail_link_offset);
      Instance::cast(*tail).instanceVariableAtPut(tail_link_offset, reference);
      Instance::cast(reference).instanceVariableAtPut(reference_link_offset,
                                                      head);
    }
    *tail = reference;
  }
  
  static void dequeueReference(RawObject head, RawObject* tail,
                               word head_link_offset, word tail_link_offset) {
    if (head == *tail) {
      *tail = RawNoneType::object();
    } else {
      RawObject next = Instance::cast(head).instanceVariableAt(head_link_offset);
      Instance::cast(*tail).instanceVariableAtPut(tail_link_offset, next);
    }
    Instance::cast(head).instanceVariableAtPut(head_link_offset,
                                               RawNoneType::object());
  }
  
  // RawWeakRef
  
  void RawWeakRef::enqueue(RawObject reference, RawObject* tail) {
    enqueueReference(reference, tail, RawWeakRef::kLinkOffset,
                     RawWeakRef::kLinkOffset);
  }
  
  RawObject RawWeakRef::dequeue(RawObject* tail) {
    RawObject head =
        Instance::cast(*tail).instanceVariableAt(RawWeakRef::kLinkOffset);
    dequeueReference(head, tail, RawWeakRef::kLinkOffset,
                     RawWeakRef::kLinkOffset);
    return head;
  }
  
  // Append tail2 to tail1 and return the new tail.
  RawObject RawWeakRef::spliceQueue(RawObject tail1, RawObject tail2) {
    if (tail1 == RawNoneType::object() && tail2 == RawNoneType::object()) {
      return RawNoneType::object();
    }
    if (tail1 == RawNoneType::object()) {
      return tail2;
    }
    if (tail2 == RawNoneType::object()) {
      return tail1;
    }
    // merge two list, tail1 -> head2 -> ... -> tail2 -> head1
    RawObject head1 = RawWeakRef::cast(tail1).link();
    RawObject head2 = RawWeakRef::cast(tail2).link();
    RawWeakRef::cast(tail1).setLink(head2);
    RawWeakRef::cast(tail2).setLink(head1);
    return tail2;
  }
  
  // RawNativeProxy
  
  static word nativeProxyAttributeOffset(const RawObject* object,
                                         int offset_from_end) {
    DCHECK(offset_from_end < 0, "negative offset is expected");
    return RawHeapObject::cast(*object).headerCountOrOverflow() * kPointerSize +
           offset_from_end;
  }
  
  RawObject RawNativeProxy::native() const {
    return instanceVariableAt(
        nativeProxyAttributeOffset(this, kNativeOffsetFromEnd));
  }
  
  void RawNativeProxy::setNative(RawObject native_ptr) const {
    instanceVariableAtPut(nativeProxyAttributeOffset(this, kNativeOffsetFromEnd),
                          native_ptr);
  }
  
  RawObject RawNativeProxy::dict() const {
    return instanceVariableAt(
        nativeProxyAttributeOffset(this, kDictOffsetFromEnd));
  }
  
  void RawNativeProxy::setDict(RawObject dict) const {
    instanceVariableAtPut(nativeProxyAttributeOffset(this, kDictOffsetFromEnd),
                          dict);
  }
  
  RawObject RawNativeProxy::link() const {
    return instanceVariableAt(
        nativeProxyAttributeOffset(this, kLinkOffsetFromEnd));
  }
  
  void RawNativeProxy::setLink(RawObject reference) const {
    instanceVariableAtPut(nativeProxyAttributeOffset(this, kLinkOffsetFromEnd),
                          reference);
  }
  
  void RawNativeProxy::enqueue(RawObject reference, RawObject* tail) {
    DCHECK(Thread::current()->runtime()->isInstanceOfNativeProxy(reference),
           "reference is expected to be native proxy");
    DCHECK(*tail == RawNoneType::object() ||
               Thread::current()->runtime()->isInstanceOfNativeProxy(*tail),
           "tail is expected to be none of native proxy");
    int reference_link_offset =
        nativeProxyAttributeOffset(&reference, kLinkOffsetFromEnd);
    int tail_link_offset = -1;
    if (*tail != RawNoneType::object()) {
      tail_link_offset = nativeProxyAttributeOffset(tail, kLinkOffsetFromEnd);
    }
    enqueueReference(reference, tail, reference_link_offset, tail_link_offset);
  }
  
  RawObject RawNativeProxy::dequeue(RawObject* tail) {
    DCHECK(Thread::current()->runtime()->isInstanceOfNativeProxy(*tail),
           "expected native proxy");
    DCHECK(*tail != RawNoneType::object(), "empty queue");
    int tail_link_offset = nativeProxyAttributeOffset(tail, kLinkOffsetFromEnd);
    RawObject head = Instance::cast(*tail).instanceVariableAt(tail_link_offset);
    int head_link_offset = nativeProxyAttributeOffset(&head, kLinkOffsetFromEnd);
    dequeueReference(head, tail, head_link_offset, tail_link_offset);
    return head;
  }
  
  // RawGeneratorFrame
  
  word RawGeneratorFrame::virtualPC() const { return frame()->virtualPC(); }
  
  void RawGeneratorFrame::setVirtualPC(word value) const {
    return frame()->setVirtualPC(value);
  }
  
  RawObject* RawGeneratorFrame::valueStackTop() const {
    return frame()->stashedValueStackTop();
  }
  
  RawObject RawGeneratorFrame::popValue() const {
    return frame()->stashedPopValue();
  }
  
  }  // namespace py
  