// Copyright 2017 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-constructor-gen.h"
#include "src/builtins/builtins-iterator-gen.h"
#include "src/builtins/builtins-utils-gen.h"
#include "src/code-stub-assembler.h"
#include "src/factory-inl.h"
#include "src/objects/hash-table.h"

namespace v8 {
namespace internal {

using compiler::Node;

class CollectionsBuiltinsAssembler : public CodeStubAssembler {
 public:
  explicit CollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state)
      : CodeStubAssembler(state) {}

 protected:
  Node* AllocateJSMap(Node* js_map_function);

  template <typename CollectionType>
  Node* AllocateOrderedHashTable();
  Node* AllocateJSCollection(Node* js_map_function);
  template <typename IteratorType>
  Node* AllocateJSCollectionIterator(Node* context, int map_index,
                                     Node* collection);

  Node* GetHash(Node* const key);
  Node* CallGetHashRaw(Node* const key);
  Node* CallGetOrCreateHashRaw(Node* const key);

  // Transitions the iterator to the non obsolete backing store.
  // This is a NOP if the [table] is not obsolete.
  typedef std::function<void(Node* const table, Node* const index)>
      UpdateInTransition;
  template <typename TableType>
  std::tuple<Node*, Node*> Transition(
      Node* const table, Node* const index,
      UpdateInTransition const& update_in_transition);
  template <typename IteratorType, typename TableType>
  std::tuple<Node*, Node*> TransitionAndUpdate(Node* const iterator);
  template <typename TableType>
  std::tuple<Node*, Node*, Node*> NextSkipHoles(Node* table, Node* index,
                                                Label* if_end);

  // Builds code that finds OrderedHashTable entry for a key with hash code
  // {hash} with using the comparison code generated by {key_compare}. The code
  // jumps to {entry_found} if the key is found, or to {not_found} if the key
  // was not found. In the {entry_found} branch, the variable
  // entry_start_position will be bound to the index of the entry (relative to
  // OrderedHashTable::kHashTableStartIndex).
  //
  // The {CollectionType} template parameter stands for the particular instance
  // of OrderedHashTable, it should be OrderedHashMap or OrderedHashSet.
  template <typename CollectionType>
  void FindOrderedHashTableEntry(
      Node* table, Node* hash,
      std::function<void(Node* other, Label* if_same, Label* if_not_same)>
          key_compare,
      Variable* entry_start_position, Label* entry_found, Label* not_found);

  // Specialization for Smi.
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise.
  template <typename CollectionType>
  void FindOrderedHashTableEntryForSmiKey(Node* table, Node* key_tagged,
                                          Variable* result, Label* entry_found,
                                          Label* not_found);
  void SameValueZeroSmi(Node* key_smi, Node* candidate_key, Label* if_same,
                        Label* if_not_same);

  // Specialization for heap numbers.
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise.
  void SameValueZeroHeapNumber(Node* key_string, Node* candidate_key,
                               Label* if_same, Label* if_not_same);
  template <typename CollectionType>
  void FindOrderedHashTableEntryForHeapNumberKey(Node* context, Node* table,
                                                 Node* key_heap_number,
                                                 Variable* result,
                                                 Label* entry_found,
                                                 Label* not_found);

  // Specialization for bigints.
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise.
  void SameValueZeroBigInt(Node* key, Node* candidate_key, Label* if_same,
                           Label* if_not_same);
  template <typename CollectionType>
  void FindOrderedHashTableEntryForBigIntKey(Node* context, Node* table,
                                             Node* key, Variable* result,
                                             Label* entry_found,
                                             Label* not_found);

  // Specialization for string.
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise.
  template <typename CollectionType>
  void FindOrderedHashTableEntryForStringKey(Node* context, Node* table,
                                             Node* key_tagged, Variable* result,
                                             Label* entry_found,
                                             Label* not_found);
  Node* ComputeIntegerHashForString(Node* context, Node* string_key);
  void SameValueZeroString(Node* context, Node* key_string, Node* candidate_key,
                           Label* if_same, Label* if_not_same);

  // Specialization for non-strings, non-numbers. For those we only need
  // reference equality to compare the keys.
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise. If the hash-code has not been computed, it
  // should be Smi -1.
  template <typename CollectionType>
  void FindOrderedHashTableEntryForOtherKey(Node* context, Node* table,
                                            Node* key, Variable* result,
                                            Label* entry_found,
                                            Label* not_found);

  template <typename CollectionType>
  void TryLookupOrderedHashTableIndex(Node* const table, Node* const key,
                                      Node* const context, Variable* result,
                                      Label* if_entry_found,
                                      Label* if_not_found);

  Node* NormalizeNumberKey(Node* key);
  void StoreOrderedHashMapNewEntry(Node* const table, Node* const key,
                                   Node* const value, Node* const hash,
                                   Node* const number_of_buckets,
                                   Node* const occupancy);
  void StoreOrderedHashSetNewEntry(Node* const table, Node* const key,
                                   Node* const hash,
                                   Node* const number_of_buckets,
                                   Node* const occupancy);
};

template <typename CollectionType>
Node* CollectionsBuiltinsAssembler::AllocateOrderedHashTable() {
  static const int kCapacity = CollectionType::kMinCapacity;
  static const int kBucketCount = kCapacity / CollectionType::kLoadFactor;
  static const int kDataTableLength = kCapacity * CollectionType::kEntrySize;
  static const int kFixedArrayLength =
      CollectionType::kHashTableStartIndex + kBucketCount + kDataTableLength;
  static const int kDataTableStartIndex =
      CollectionType::kHashTableStartIndex + kBucketCount;

  STATIC_ASSERT(base::bits::IsPowerOfTwo(kCapacity));
  STATIC_ASSERT(kCapacity <= CollectionType::kMaxCapacity);

  // Allocate the table and add the proper map.
  const ElementsKind elements_kind = HOLEY_ELEMENTS;
  Node* const length_intptr = IntPtrConstant(kFixedArrayLength);
  Node* const table = AllocateFixedArray(elements_kind, length_intptr);
  CSA_ASSERT(this,
             IntPtrLessThanOrEqual(
                 length_intptr, IntPtrConstant(FixedArray::kMaxRegularLength)));
  Heap::RootListIndex map_index = Heap::kOrderedHashTableMapRootIndex;
  // TODO(gsathya): Directly store correct in AllocateFixedArray,
  // instead of overwriting here.
  StoreMapNoWriteBarrier(table, map_index);

  // Initialize the OrderedHashTable fields.
  const WriteBarrierMode barrier_mode = SKIP_WRITE_BARRIER;
  StoreFixedArrayElement(table, CollectionType::kNumberOfElementsIndex,
                         SmiConstant(0), barrier_mode);
  StoreFixedArrayElement(table, CollectionType::kNumberOfDeletedElementsIndex,
                         SmiConstant(0), barrier_mode);
  StoreFixedArrayElement(table, CollectionType::kNumberOfBucketsIndex,
                         SmiConstant(kBucketCount), barrier_mode);

  // Fill the buckets with kNotFound.
  Node* const not_found = SmiConstant(CollectionType::kNotFound);
  STATIC_ASSERT(CollectionType::kHashTableStartIndex ==
                CollectionType::kNumberOfBucketsIndex + 1);
  STATIC_ASSERT((CollectionType::kHashTableStartIndex + kBucketCount) ==
                kDataTableStartIndex);
  for (int i = 0; i < kBucketCount; i++) {
    StoreFixedArrayElement(table, CollectionType::kHashTableStartIndex + i,
                           not_found, barrier_mode);
  }

  // Fill the data table with undefined.
  STATIC_ASSERT(kDataTableStartIndex + kDataTableLength == kFixedArrayLength);
  for (int i = 0; i < kDataTableLength; i++) {
    StoreFixedArrayElement(table, kDataTableStartIndex + i, UndefinedConstant(),
                           barrier_mode);
  }

  return table;
}

Node* CollectionsBuiltinsAssembler::AllocateJSCollection(
    Node* js_map_function) {
  CSA_ASSERT(this, IsConstructorMap(LoadMap(js_map_function)));
  Node* const initial_map = LoadObjectField(
      js_map_function, JSFunction::kPrototypeOrInitialMapOffset);
  Node* const instance = AllocateJSObjectFromMap(initial_map);

  StoreObjectFieldRoot(instance, JSMap::kTableOffset,
                       Heap::kUndefinedValueRootIndex);

  return instance;
}

template <typename IteratorType>
Node* CollectionsBuiltinsAssembler::AllocateJSCollectionIterator(
    Node* context, int map_index, Node* collection) {
  Node* const table = LoadObjectField(collection, JSCollection::kTableOffset);
  Node* const native_context = LoadNativeContext(context);
  Node* const iterator_map = LoadContextElement(native_context, map_index);
  Node* const iterator = AllocateInNewSpace(IteratorType::kSize);
  StoreMapNoWriteBarrier(iterator, iterator_map);
  StoreObjectFieldRoot(iterator, IteratorType::kPropertiesOrHashOffset,
                       Heap::kEmptyFixedArrayRootIndex);
  StoreObjectFieldRoot(iterator, IteratorType::kElementsOffset,
                       Heap::kEmptyFixedArrayRootIndex);
  StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kTableOffset, table);
  StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset,
                                 SmiConstant(0));
  return iterator;
}

TF_BUILTIN(MapConstructor, CollectionsBuiltinsAssembler) {
  const int kIterableArg = 0;

  Node* argc =
      ChangeInt32ToIntPtr(Parameter(BuiltinDescriptor::kArgumentsCount));
  CodeStubArguments args(this, argc);

  Node* const iterable = args.GetOptionalArgumentValue(kIterableArg);
  Node* const new_target = Parameter(BuiltinDescriptor::kNewTarget);
  Node* const context = Parameter(BuiltinDescriptor::kContext);

  Label if_target_is_undefined(this, Label::kDeferred);
  GotoIf(IsUndefined(new_target), &if_target_is_undefined);

  Node* const native_context = LoadNativeContext(context);
  Node* const js_map_fun =
      LoadContextElement(native_context, Context::JS_MAP_FUN_INDEX);

  VARIABLE(var_result, MachineRepresentation::kTagged);

  Label init(this), exit(this), if_targetisnotmodified(this),
      if_targetismodified(this);
  Branch(WordEqual(js_map_fun, new_target), &if_targetisnotmodified,
         &if_targetismodified);

  BIND(&if_targetisnotmodified);
  {
    Node* const instance = AllocateJSCollection(js_map_fun);
    var_result.Bind(instance);
    Goto(&init);
  }

  BIND(&if_targetismodified);
  {
    ConstructorBuiltinsAssembler constructor_assembler(this->state());
    Node* const instance = constructor_assembler.EmitFastNewObject(
        context, js_map_fun, new_target);
    var_result.Bind(instance);
    Goto(&init);
  }

  BIND(&init);
  Node* table = AllocateOrderedHashTable<OrderedHashMap>();
  StoreObjectField(var_result.value(), JSMap::kTableOffset, table);

  GotoIf(Word32Or(IsUndefined(iterable), IsNull(iterable)), &exit);

  Label if_notcallable(this);
  // TODO(gsathya): Add fast path for unmodified maps.
  Node* const adder = GetProperty(context, var_result.value(),
                                  isolate()->factory()->set_string());
  GotoIf(TaggedIsSmi(adder), &if_notcallable);
  GotoIfNot(IsCallable(adder), &if_notcallable);

  IteratorBuiltinsAssembler iterator_assembler(this->state());
  Node* const iterator = iterator_assembler.GetIterator(context, iterable);
  GotoIf(IsUndefined(iterator), &exit);

  Node* const fast_iterator_result_map =
      LoadContextElement(native_context, Context::ITERATOR_RESULT_MAP_INDEX);

  VARIABLE(var_exception, MachineRepresentation::kTagged, TheHoleConstant());

  Label loop(this), if_notobject(this), if_exception(this);
  Goto(&loop);

  BIND(&loop);
  {
    Node* const next = iterator_assembler.IteratorStep(
        context, iterator, &exit, fast_iterator_result_map);

    Node* const next_value = iterator_assembler.IteratorValue(
        context, next, fast_iterator_result_map);

    GotoIf(TaggedIsSmi(next_value), &if_notobject);
    GotoIfNot(IsJSReceiver(next_value), &if_notobject);

    Node* const k =
        GetProperty(context, next_value, isolate()->factory()->zero_string());
    GotoIfException(k, &if_exception, &var_exception);

    Node* const v =
        GetProperty(context, next_value, isolate()->factory()->one_string());
    GotoIfException(v, &if_exception, &var_exception);

    Node* add_call = CallJS(CodeFactory::Call(isolate()), context, adder,
                            var_result.value(), k, v);
    GotoIfException(add_call, &if_exception, &var_exception);
    Goto(&loop);

    BIND(&if_notobject);
    {
      Node* const exception = MakeTypeError(
          MessageTemplate::kIteratorValueNotAnObject, context, next_value);
      var_exception.Bind(exception);
      Goto(&if_exception);
    }
  }

  BIND(&if_exception);
  {
    iterator_assembler.IteratorCloseOnException(context, iterator,
                                                &var_exception);
  }

  BIND(&if_notcallable);
  {
    Node* const receiver_str = HeapConstant(isolate()->factory()->add_string());
    ThrowTypeError(context, MessageTemplate::kPropertyNotFunction, adder,
                   receiver_str, var_result.value());
  }

  BIND(&if_target_is_undefined);
  ThrowTypeError(context, MessageTemplate::kConstructorNotFunction,
                 HeapConstant(isolate()->factory()->Map_string()));

  BIND(&exit);
  args.PopAndReturn(var_result.value());
}

TF_BUILTIN(SetConstructor, CollectionsBuiltinsAssembler) {
  const int kIterableArg = 0;

  Node* argc =
      ChangeInt32ToIntPtr(Parameter(BuiltinDescriptor::kArgumentsCount));
  CodeStubArguments args(this, argc);

  Node* const iterable = args.GetOptionalArgumentValue(kIterableArg);
  Node* const new_target = Parameter(BuiltinDescriptor::kNewTarget);
  Node* const context = Parameter(BuiltinDescriptor::kContext);

  Label if_target_is_undefined(this, Label::kDeferred);
  GotoIf(IsUndefined(new_target), &if_target_is_undefined);

  Node* const native_context = LoadNativeContext(context);
  Node* const js_set_fun =
      LoadContextElement(native_context, Context::JS_SET_FUN_INDEX);

  VARIABLE(var_result, MachineRepresentation::kTagged);

  Label init(this), exit(this), if_targetisnotmodified(this),
      if_targetismodified(this);
  Branch(WordEqual(js_set_fun, new_target), &if_targetisnotmodified,
         &if_targetismodified);

  BIND(&if_targetisnotmodified);
  {
    Node* const instance = AllocateJSCollection(js_set_fun);
    var_result.Bind(instance);
    Goto(&init);
  }

  BIND(&if_targetismodified);
  {
    ConstructorBuiltinsAssembler constructor_assembler(this->state());
    Node* const instance = constructor_assembler.EmitFastNewObject(
        context, js_set_fun, new_target);
    var_result.Bind(instance);
    Goto(&init);
  }

  BIND(&init);
  Node* table = AllocateOrderedHashTable<OrderedHashSet>();
  StoreObjectField(var_result.value(), JSSet::kTableOffset, table);

  GotoIf(Word32Or(IsUndefined(iterable), IsNull(iterable)), &exit);

  Label if_notcallable(this);
  // TODO(gsathya): Add fast path for unmodified maps.
  Node* const adder = GetProperty(context, var_result.value(),
                                  isolate()->factory()->add_string());
  GotoIf(TaggedIsSmi(adder), &if_notcallable);
  GotoIfNot(IsCallable(adder), &if_notcallable);

  IteratorBuiltinsAssembler iterator_assembler(this->state());
  Node* const iterator = iterator_assembler.GetIterator(context, iterable);
  GotoIf(IsUndefined(iterator), &exit);

  Node* const fast_iterator_result_map =
      LoadContextElement(native_context, Context::ITERATOR_RESULT_MAP_INDEX);

  VARIABLE(var_exception, MachineRepresentation::kTagged, TheHoleConstant());

  Label loop(this), if_notobject(this), if_exception(this);
  Goto(&loop);

  BIND(&loop);
  {
    Node* const next = iterator_assembler.IteratorStep(
        context, iterator, &exit, fast_iterator_result_map);

    Node* const next_value = iterator_assembler.IteratorValue(
        context, next, fast_iterator_result_map);

    Node* add_call = CallJS(CodeFactory::Call(isolate()), context, adder,
                            var_result.value(), next_value);

    GotoIfException(add_call, &if_exception, &var_exception);
    Goto(&loop);
  }

  BIND(&if_exception);
  {
    iterator_assembler.IteratorCloseOnException(context, iterator,
                                                &var_exception);
  }

  BIND(&if_notcallable);
  ThrowTypeError(context, MessageTemplate::kPropertyNotFunction, adder,
                 HeapConstant(isolate()->factory()->add_string()),
                 var_result.value());

  BIND(&if_target_is_undefined);
  ThrowTypeError(context, MessageTemplate::kConstructorNotFunction,
                 HeapConstant(isolate()->factory()->Set_string()));

  BIND(&exit);
  args.PopAndReturn(var_result.value());
}

Node* CollectionsBuiltinsAssembler::CallGetOrCreateHashRaw(Node* const key) {
  Node* const function_addr =
      ExternalConstant(ExternalReference::get_or_create_hash_raw(isolate()));
  Node* const isolate_ptr =
      ExternalConstant(ExternalReference::isolate_address(isolate()));

  MachineType type_ptr = MachineType::Pointer();
  MachineType type_tagged = MachineType::AnyTagged();

  Node* const result = CallCFunction2(type_tagged, type_ptr, type_tagged,
                                      function_addr, isolate_ptr, key);

  return result;
}

Node* CollectionsBuiltinsAssembler::CallGetHashRaw(Node* const key) {
  Node* const function_addr = ExternalConstant(
      ExternalReference::orderedhashmap_gethash_raw(isolate()));
  Node* const isolate_ptr =
      ExternalConstant(ExternalReference::isolate_address(isolate()));

  MachineType type_ptr = MachineType::Pointer();
  MachineType type_tagged = MachineType::AnyTagged();

  Node* const result = CallCFunction2(type_tagged, type_ptr, type_tagged,
                                      function_addr, isolate_ptr, key);
  return SmiUntag(result);
}

Node* CollectionsBuiltinsAssembler::GetHash(Node* const key) {
  VARIABLE(var_result, MachineType::PointerRepresentation());
  Label if_jsobject(this), other(this), done(this);
  Node* instance_type = LoadMapInstanceType(LoadMap(key));
  Branch(IsJSObjectInstanceType(instance_type), &if_jsobject, &other);

  BIND(&if_jsobject);
  {
    Node* hash = LoadHashForJSObject(key, instance_type);
    // TODO(gsathya): Change all uses of -1 to PropertyArray::kNoHashSentinel.
    var_result.Bind(SelectConstant(
        Word32Equal(hash, Int32Constant(PropertyArray::kNoHashSentinel)),
        IntPtrConstant(-1), ChangeInt32ToIntPtr(hash),
        MachineType::PointerRepresentation()));
    Goto(&done);
  }

  BIND(&other);
  {
    var_result.Bind(CallGetHashRaw(key));
    Goto(&done);
  }

  BIND(&done);
  return var_result.value();
}

void CollectionsBuiltinsAssembler::SameValueZeroSmi(Node* key_smi,
                                                    Node* candidate_key,
                                                    Label* if_same,
                                                    Label* if_not_same) {
  // If the key is the same, we are done.
  GotoIf(WordEqual(candidate_key, key_smi), if_same);

  // If the candidate key is smi, then it must be different (because
  // we already checked for equality above).
  GotoIf(TaggedIsSmi(candidate_key), if_not_same);

  // If the candidate key is not smi, we still have to check if it is a
  // heap number with the same value.
  GotoIfNot(IsHeapNumber(candidate_key), if_not_same);

  Node* const candidate_key_number = LoadHeapNumberValue(candidate_key);
  Node* const key_number = SmiToFloat64(key_smi);

  GotoIf(Float64Equal(candidate_key_number, key_number), if_same);

  Goto(if_not_same);
}

template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForSmiKey(
    Node* table, Node* smi_key, Variable* result, Label* entry_found,
    Label* not_found) {
  Node* const key_untagged = SmiUntag(smi_key);
  Node* const hash =
      ChangeInt32ToIntPtr(ComputeIntegerHash(key_untagged, Int32Constant(0)));
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  result->Bind(hash);
  FindOrderedHashTableEntry<CollectionType>(
      table, hash,
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        SameValueZeroSmi(smi_key, other_key, if_same, if_not_same);
      },
      result, entry_found, not_found);
}

template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForStringKey(
    Node* context, Node* table, Node* key_tagged, Variable* result,
    Label* entry_found, Label* not_found) {
  Node* const hash = ComputeIntegerHashForString(context, key_tagged);
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  result->Bind(hash);
  FindOrderedHashTableEntry<CollectionType>(
      table, hash,
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        SameValueZeroString(context, key_tagged, other_key, if_same,
                            if_not_same);
      },
      result, entry_found, not_found);
}

template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForHeapNumberKey(
    Node* context, Node* table, Node* key_heap_number, Variable* result,
    Label* entry_found, Label* not_found) {
  Node* hash = CallGetHashRaw(key_heap_number);
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  result->Bind(hash);
  Node* const key_float = LoadHeapNumberValue(key_heap_number);
  FindOrderedHashTableEntry<CollectionType>(
      table, hash,
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        SameValueZeroHeapNumber(key_float, other_key, if_same, if_not_same);
      },
      result, entry_found, not_found);
}

template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForBigIntKey(
    Node* context, Node* table, Node* key, Variable* result, Label* entry_found,
    Label* not_found) {
  Node* hash = CallGetHashRaw(key);
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  result->Bind(hash);
  FindOrderedHashTableEntry<CollectionType>(
      table, hash,
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        SameValueZeroBigInt(key, other_key, if_same, if_not_same);
      },
      result, entry_found, not_found);
}

template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForOtherKey(
    Node* context, Node* table, Node* key, Variable* result, Label* entry_found,
    Label* not_found) {
  Node* hash = GetHash(key);
  result->Bind(hash);
  FindOrderedHashTableEntry<CollectionType>(
      table, hash,
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        Branch(WordEqual(key, other_key), if_same, if_not_same);
      },
      result, entry_found, not_found);
}

Node* CollectionsBuiltinsAssembler::ComputeIntegerHashForString(
    Node* context, Node* string_key) {
  VARIABLE(var_result, MachineType::PointerRepresentation());

  Label hash_not_computed(this), done(this, &var_result);
  Node* hash =
      ChangeInt32ToIntPtr(LoadNameHash(string_key, &hash_not_computed));
  var_result.Bind(hash);
  Goto(&done);

  BIND(&hash_not_computed);
  var_result.Bind(CallGetHashRaw(string_key));
  Goto(&done);

  BIND(&done);
  return var_result.value();
}

void CollectionsBuiltinsAssembler::SameValueZeroString(Node* context,
                                                       Node* key_string,
                                                       Node* candidate_key,
                                                       Label* if_same,
                                                       Label* if_not_same) {
  // If the candidate is not a string, the keys are not equal.
  GotoIf(TaggedIsSmi(candidate_key), if_not_same);
  GotoIfNot(IsString(candidate_key), if_not_same);

  Branch(WordEqual(CallBuiltin(Builtins::kStringEqual, context, key_string,
                               candidate_key),
                   TrueConstant()),
         if_same, if_not_same);
}

void CollectionsBuiltinsAssembler::SameValueZeroBigInt(Node* key,
                                                       Node* candidate_key,
                                                       Label* if_same,
                                                       Label* if_not_same) {
  CSA_ASSERT(this, IsBigInt(key));
  GotoIf(TaggedIsSmi(candidate_key), if_not_same);
  GotoIfNot(IsBigInt(candidate_key), if_not_same);

  Branch(WordEqual(CallRuntime(Runtime::kBigIntEqual, NoContextConstant(), key,
                               candidate_key),
                   TrueConstant()),
         if_same, if_not_same);
}

void CollectionsBuiltinsAssembler::SameValueZeroHeapNumber(Node* key_float,
                                                           Node* candidate_key,
                                                           Label* if_same,
                                                           Label* if_not_same) {
  Label if_smi(this), if_keyisnan(this);

  GotoIf(TaggedIsSmi(candidate_key), &if_smi);
  GotoIfNot(IsHeapNumber(candidate_key), if_not_same);

  {
    // {candidate_key} is a heap number.
    Node* const candidate_float = LoadHeapNumberValue(candidate_key);
    GotoIf(Float64Equal(key_float, candidate_float), if_same);

    // SameValueZero needs to treat NaNs as equal. First check if {key_float}
    // is NaN.
    BranchIfFloat64IsNaN(key_float, &if_keyisnan, if_not_same);

    BIND(&if_keyisnan);
    {
      // Return true iff {candidate_key} is NaN.
      Branch(Float64Equal(candidate_float, candidate_float), if_not_same,
             if_same);
    }
  }

  BIND(&if_smi);
  {
    Node* const candidate_float = SmiToFloat64(candidate_key);
    Branch(Float64Equal(key_float, candidate_float), if_same, if_not_same);
  }
}

template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntry(
    Node* table, Node* hash,
    std::function<void(Node*, Label*, Label*)> key_compare,
    Variable* entry_start_position, Label* entry_found, Label* not_found) {
  // Get the index of the bucket.
  Node* const number_of_buckets = SmiUntag(
      LoadFixedArrayElement(table, CollectionType::kNumberOfBucketsIndex));
  Node* const bucket =
      WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
  Node* const first_entry = SmiUntag(LoadFixedArrayElement(
      table, bucket, CollectionType::kHashTableStartIndex * kPointerSize));

  // Walk the bucket chain.
  Node* entry_start;
  Label if_key_found(this);
  {
    VARIABLE(var_entry, MachineType::PointerRepresentation(), first_entry);
    Label loop(this, {&var_entry, entry_start_position}),
        continue_next_entry(this);
    Goto(&loop);
    BIND(&loop);

    // If the entry index is the not-found sentinel, we are done.
    GotoIf(
        WordEqual(var_entry.value(), IntPtrConstant(CollectionType::kNotFound)),
        not_found);

    // Make sure the entry index is within range.
    CSA_ASSERT(
        this,
        UintPtrLessThan(
            var_entry.value(),
            SmiUntag(SmiAdd(
                LoadFixedArrayElement(table,
                                      CollectionType::kNumberOfElementsIndex),
                LoadFixedArrayElement(
                    table, CollectionType::kNumberOfDeletedElementsIndex)))));

    // Compute the index of the entry relative to kHashTableStartIndex.
    entry_start =
        IntPtrAdd(IntPtrMul(var_entry.value(),
                            IntPtrConstant(CollectionType::kEntrySize)),
                  number_of_buckets);

    // Load the key from the entry.
    Node* const candidate_key = LoadFixedArrayElement(
        table, entry_start,
        CollectionType::kHashTableStartIndex * kPointerSize);

    key_compare(candidate_key, &if_key_found, &continue_next_entry);

    BIND(&continue_next_entry);
    // Load the index of the next entry in the bucket chain.
    var_entry.Bind(SmiUntag(LoadFixedArrayElement(
        table, entry_start,
        (CollectionType::kHashTableStartIndex + CollectionType::kChainOffset) *
            kPointerSize)));

    Goto(&loop);
  }

  BIND(&if_key_found);
  entry_start_position->Bind(entry_start);
  Goto(entry_found);
}

TF_BUILTIN(OrderedHashTableHealIndex, CollectionsBuiltinsAssembler) {
  Node* table = Parameter(Descriptor::kTable);
  Node* index = Parameter(Descriptor::kIndex);
  CSA_ASSERT(this, TaggedIsNotSmi(table));
  CSA_ASSERT(this, TaggedIsSmi(index));
  Label return_index(this), return_zero(this);

  // Check if we need to update the {index}.
  GotoIfNot(SmiLessThan(SmiConstant(Smi::kZero), index), &return_zero);

  // Check if the {table} was cleared.
  Node* number_of_deleted_elements = LoadAndUntagObjectField(
      table, OrderedHashTableBase::kNumberOfDeletedElementsOffset);
  GotoIf(WordEqual(number_of_deleted_elements,
                   IntPtrConstant(OrderedHashTableBase::kClearedTableSentinel)),
         &return_zero);

  VARIABLE(var_i, MachineType::PointerRepresentation(), IntPtrConstant(0));
  VARIABLE(var_index, MachineRepresentation::kTagged, index);
  Label loop(this, {&var_i, &var_index});
  Goto(&loop);
  BIND(&loop);
  {
    Node* i = var_i.value();
    GotoIfNot(IntPtrLessThan(i, number_of_deleted_elements), &return_index);
    Node* removed_index = LoadFixedArrayElement(
        table, i, OrderedHashTableBase::kRemovedHolesIndex * kPointerSize);
    GotoIf(SmiGreaterThanOrEqual(removed_index, index), &return_index);
    Decrement(&var_index, 1, SMI_PARAMETERS);
    Increment(&var_i);
    Goto(&loop);
  }

  BIND(&return_index);
  Return(var_index.value());

  BIND(&return_zero);
  Return(SmiConstant(Smi::kZero));
}

template <typename TableType>
std::tuple<Node*, Node*> CollectionsBuiltinsAssembler::Transition(
    Node* const table, Node* const index,
    UpdateInTransition const& update_in_transition) {
  VARIABLE(var_index, MachineType::PointerRepresentation(), index);
  VARIABLE(var_table, MachineRepresentation::kTagged, table);
  Label if_done(this), if_transition(this, Label::kDeferred);
  Branch(TaggedIsSmi(
             LoadObjectField(var_table.value(), TableType::kNextTableOffset)),
         &if_done, &if_transition);

  BIND(&if_transition);
  {
    Label loop(this, {&var_table, &var_index}), done_loop(this);
    Goto(&loop);
    BIND(&loop);
    {
      Node* table = var_table.value();
      Node* index = var_index.value();

      Node* next_table = LoadObjectField(table, TableType::kNextTableOffset);
      GotoIf(TaggedIsSmi(next_table), &done_loop);

      var_table.Bind(next_table);
      var_index.Bind(
          SmiUntag(CallBuiltin(Builtins::kOrderedHashTableHealIndex,
                               NoContextConstant(), table, SmiTag(index))));
      Goto(&loop);
    }
    BIND(&done_loop);

    // Update with the new {table} and {index}.
    update_in_transition(var_table.value(), var_index.value());
    Goto(&if_done);
  }

  BIND(&if_done);
  return std::tuple<Node*, Node*>(var_table.value(), var_index.value());
}

template <typename IteratorType, typename TableType>
std::tuple<Node*, Node*> CollectionsBuiltinsAssembler::TransitionAndUpdate(
    Node* const iterator) {
  return Transition<TableType>(
      LoadObjectField(iterator, IteratorType::kTableOffset),
      LoadAndUntagObjectField(iterator, IteratorType::kIndexOffset),
      [this, iterator](Node* const table, Node* const index) {
        // Update the {iterator} with the new state.
        StoreObjectField(iterator, IteratorType::kTableOffset, table);
        StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset,
                                       SmiTag(index));
      });
}

template <typename TableType>
std::tuple<Node*, Node*, Node*> CollectionsBuiltinsAssembler::NextSkipHoles(
    Node* table, Node* index, Label* if_end) {
  // Compute the used capacity for the {table}.
  Node* number_of_buckets =
      LoadAndUntagObjectField(table, TableType::kNumberOfBucketsOffset);
  Node* number_of_elements =
      LoadAndUntagObjectField(table, TableType::kNumberOfElementsOffset);
  Node* number_of_deleted_elements =
      LoadAndUntagObjectField(table, TableType::kNumberOfDeletedElementsOffset);
  Node* used_capacity =
      IntPtrAdd(number_of_elements, number_of_deleted_elements);

  Node* entry_key;
  Node* entry_start_position;
  VARIABLE(var_index, MachineType::PointerRepresentation(), index);
  Label loop(this, &var_index), done_loop(this);
  Goto(&loop);
  BIND(&loop);
  {
    GotoIfNot(IntPtrLessThan(var_index.value(), used_capacity), if_end);
    entry_start_position = IntPtrAdd(
        IntPtrMul(var_index.value(), IntPtrConstant(TableType::kEntrySize)),
        number_of_buckets);
    entry_key =
        LoadFixedArrayElement(table, entry_start_position,
                              TableType::kHashTableStartIndex * kPointerSize);
    Increment(&var_index);
    Branch(IsTheHole(entry_key), &loop, &done_loop);
  }

  BIND(&done_loop);
  return std::tuple<Node*, Node*, Node*>(entry_key, entry_start_position,
                                         var_index.value());
}

TF_BUILTIN(MapGet, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.get");

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
  Node* index = CallBuiltin(Builtins::kMapLookupHashIndex, context, table, key);

  Label if_found(this), if_not_found(this);
  Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
         &if_not_found);

  BIND(&if_found);
  Return(LoadFixedArrayElement(table, SmiUntag(index)));

  BIND(&if_not_found);
  Return(UndefinedConstant());
}

TF_BUILTIN(MapHas, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.has");

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
  Node* index = CallBuiltin(Builtins::kMapLookupHashIndex, context, table, key);

  Label if_found(this), if_not_found(this);
  Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
         &if_not_found);

  BIND(&if_found);
  Return(TrueConstant());

  BIND(&if_not_found);
  Return(FalseConstant());
}

Node* CollectionsBuiltinsAssembler::NormalizeNumberKey(Node* const key) {
  VARIABLE(result, MachineRepresentation::kTagged, key);
  Label done(this);

  GotoIf(TaggedIsSmi(key), &done);
  GotoIfNot(IsHeapNumber(key), &done);
  Node* const number = LoadHeapNumberValue(key);
  GotoIfNot(Float64Equal(number, Float64Constant(0.0)), &done);
  // We know the value is zero, so we take the key to be Smi 0.
  // Another option would be to normalize to Smi here.
  result.Bind(SmiConstant(0));
  Goto(&done);

  BIND(&done);
  return result.value();
}

TF_BUILTIN(MapSet, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* key = Parameter(Descriptor::kKey);
  Node* const value = Parameter(Descriptor::kValue);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.set");

  key = NormalizeNumberKey(key);

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);

  VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  Label entry_found(this), not_found(this);

  TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
                                                 &entry_start_position_or_hash,
                                                 &entry_found, &not_found);

  BIND(&entry_found);
  // If we found the entry, we just store the value there.
  StoreFixedArrayElement(table, entry_start_position_or_hash.value(), value,
                         UPDATE_WRITE_BARRIER,
                         kPointerSize * (OrderedHashMap::kHashTableStartIndex +
                                         OrderedHashMap::kValueOffset));
  Return(receiver);

  Label no_hash(this), add_entry(this), store_new_entry(this);
  BIND(&not_found);
  {
    // If we have a hash code, we can start adding the new entry.
    GotoIf(IntPtrGreaterThanOrEqual(entry_start_position_or_hash.value(),
                                    IntPtrConstant(0)),
           &add_entry);

    // Otherwise, go to runtime to compute the hash code.
    entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key)));
    Goto(&add_entry);
  }

  BIND(&add_entry);
  VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
  VARIABLE(occupancy, MachineType::PointerRepresentation());
  VARIABLE(table_var, MachineRepresentation::kTaggedPointer, table);
  {
    // Check we have enough space for the entry.
    number_of_buckets.Bind(SmiUntag(
        LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex)));

    STATIC_ASSERT(OrderedHashMap::kLoadFactor == 2);
    Node* const capacity = WordShl(number_of_buckets.value(), 1);
    Node* const number_of_elements = SmiUntag(
        CAST(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset)));
    Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
        table, OrderedHashMap::kNumberOfDeletedElementsOffset)));
    occupancy.Bind(IntPtrAdd(number_of_elements, number_of_deleted));
    GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry);

    // We do not have enough space, grow the table and reload the relevant
    // fields.
    CallRuntime(Runtime::kMapGrow, context, receiver);
    table_var.Bind(LoadObjectField(receiver, JSMap::kTableOffset));
    number_of_buckets.Bind(SmiUntag(LoadFixedArrayElement(
        table_var.value(), OrderedHashMap::kNumberOfBucketsIndex)));
    Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
        table_var.value(), OrderedHashMap::kNumberOfElementsOffset)));
    Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
        table_var.value(), OrderedHashMap::kNumberOfDeletedElementsOffset)));
    occupancy.Bind(IntPtrAdd(new_number_of_elements, new_number_of_deleted));
    Goto(&store_new_entry);
  }
  BIND(&store_new_entry);
  // Store the key, value and connect the element to the bucket chain.
  StoreOrderedHashMapNewEntry(table_var.value(), key, value,
                              entry_start_position_or_hash.value(),
                              number_of_buckets.value(), occupancy.value());
  Return(receiver);
}

void CollectionsBuiltinsAssembler::StoreOrderedHashMapNewEntry(
    Node* const table, Node* const key, Node* const value, Node* const hash,
    Node* const number_of_buckets, Node* const occupancy) {
  Node* const bucket =
      WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
  Node* const bucket_entry = LoadFixedArrayElement(
      table, bucket, OrderedHashMap::kHashTableStartIndex * kPointerSize);

  // Store the entry elements.
  Node* const entry_start = IntPtrAdd(
      IntPtrMul(occupancy, IntPtrConstant(OrderedHashMap::kEntrySize)),
      number_of_buckets);
  StoreFixedArrayElement(table, entry_start, key, UPDATE_WRITE_BARRIER,
                         kPointerSize * OrderedHashMap::kHashTableStartIndex);
  StoreFixedArrayElement(table, entry_start, value, UPDATE_WRITE_BARRIER,
                         kPointerSize * (OrderedHashMap::kHashTableStartIndex +
                                         OrderedHashMap::kValueOffset));
  StoreFixedArrayElement(table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
                         kPointerSize * (OrderedHashMap::kHashTableStartIndex +
                                         OrderedHashMap::kChainOffset));

  // Update the bucket head.
  StoreFixedArrayElement(table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
                         OrderedHashMap::kHashTableStartIndex * kPointerSize);

  // Bump the elements count.
  Node* const number_of_elements =
      LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset);
  StoreObjectFieldNoWriteBarrier(table, OrderedHashMap::kNumberOfElementsOffset,
                                 SmiAdd(number_of_elements, SmiConstant(1)));
}

TF_BUILTIN(MapDelete, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
                         "Map.prototype.delete");

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);

  VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  Label entry_found(this), not_found(this);

  TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
                                                 &entry_start_position_or_hash,
                                                 &entry_found, &not_found);

  BIND(&not_found);
  Return(FalseConstant());

  BIND(&entry_found);
  // If we found the entry, mark the entry as deleted.
  StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
                         TheHoleConstant(), UPDATE_WRITE_BARRIER,
                         kPointerSize * OrderedHashMap::kHashTableStartIndex);
  StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
                         TheHoleConstant(), UPDATE_WRITE_BARRIER,
                         kPointerSize * (OrderedHashMap::kHashTableStartIndex +
                                         OrderedHashMap::kValueOffset));

  // Decrement the number of elements, increment the number of deleted elements.
  Node* const number_of_elements = SmiSub(
      CAST(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset)),
      SmiConstant(1));
  StoreObjectFieldNoWriteBarrier(table, OrderedHashMap::kNumberOfElementsOffset,
                                 number_of_elements);
  Node* const number_of_deleted =
      SmiAdd(CAST(LoadObjectField(
                 table, OrderedHashMap::kNumberOfDeletedElementsOffset)),
             SmiConstant(1));
  StoreObjectFieldNoWriteBarrier(
      table, OrderedHashMap::kNumberOfDeletedElementsOffset, number_of_deleted);

  Node* const number_of_buckets =
      LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex);

  // If there fewer elements than #buckets / 2, shrink the table.
  Label shrink(this);
  GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements),
                     number_of_buckets),
         &shrink);
  Return(TrueConstant());

  BIND(&shrink);
  CallRuntime(Runtime::kMapShrink, context, receiver);
  Return(TrueConstant());
}

TF_BUILTIN(SetAdd, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.add");

  key = NormalizeNumberKey(key);

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);

  VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  Label entry_found(this), not_found(this);

  TryLookupOrderedHashTableIndex<OrderedHashSet>(table, key, context,
                                                 &entry_start_position_or_hash,
                                                 &entry_found, &not_found);

  BIND(&entry_found);
  // The entry was found, there is nothing to do.
  Return(receiver);

  Label no_hash(this), add_entry(this), store_new_entry(this);
  BIND(&not_found);
  {
    // If we have a hash code, we can start adding the new entry.
    GotoIf(IntPtrGreaterThanOrEqual(entry_start_position_or_hash.value(),
                                    IntPtrConstant(0)),
           &add_entry);

    // Otherwise, go to runtime to compute the hash code.
    entry_start_position_or_hash.Bind(SmiUntag((CallGetOrCreateHashRaw(key))));
    Goto(&add_entry);
  }

  BIND(&add_entry);
  VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
  VARIABLE(occupancy, MachineType::PointerRepresentation());
  VARIABLE(table_var, MachineRepresentation::kTaggedPointer, table);
  {
    // Check we have enough space for the entry.
    number_of_buckets.Bind(SmiUntag(
        LoadFixedArrayElement(table, OrderedHashSet::kNumberOfBucketsIndex)));

    STATIC_ASSERT(OrderedHashSet::kLoadFactor == 2);
    Node* const capacity = WordShl(number_of_buckets.value(), 1);
    Node* const number_of_elements = SmiUntag(
        CAST(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset)));
    Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
        table, OrderedHashSet::kNumberOfDeletedElementsOffset)));
    occupancy.Bind(IntPtrAdd(number_of_elements, number_of_deleted));
    GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry);

    // We do not have enough space, grow the table and reload the relevant
    // fields.
    CallRuntime(Runtime::kSetGrow, context, receiver);
    table_var.Bind(LoadObjectField(receiver, JSMap::kTableOffset));
    number_of_buckets.Bind(SmiUntag(LoadFixedArrayElement(
        table_var.value(), OrderedHashSet::kNumberOfBucketsIndex)));
    Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
        table_var.value(), OrderedHashSet::kNumberOfElementsOffset)));
    Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
        table_var.value(), OrderedHashSet::kNumberOfDeletedElementsOffset)));
    occupancy.Bind(IntPtrAdd(new_number_of_elements, new_number_of_deleted));
    Goto(&store_new_entry);
  }
  BIND(&store_new_entry);
  // Store the key, value and connect the element to the bucket chain.
  StoreOrderedHashSetNewEntry(table_var.value(), key,
                              entry_start_position_or_hash.value(),
                              number_of_buckets.value(), occupancy.value());
  Return(receiver);
}

void CollectionsBuiltinsAssembler::StoreOrderedHashSetNewEntry(
    Node* const table, Node* const key, Node* const hash,
    Node* const number_of_buckets, Node* const occupancy) {
  Node* const bucket =
      WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
  Node* const bucket_entry = LoadFixedArrayElement(
      table, bucket, OrderedHashSet::kHashTableStartIndex * kPointerSize);

  // Store the entry elements.
  Node* const entry_start = IntPtrAdd(
      IntPtrMul(occupancy, IntPtrConstant(OrderedHashSet::kEntrySize)),
      number_of_buckets);
  StoreFixedArrayElement(table, entry_start, key, UPDATE_WRITE_BARRIER,
                         kPointerSize * OrderedHashSet::kHashTableStartIndex);
  StoreFixedArrayElement(table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
                         kPointerSize * (OrderedHashSet::kHashTableStartIndex +
                                         OrderedHashSet::kChainOffset));

  // Update the bucket head.
  StoreFixedArrayElement(table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
                         OrderedHashSet::kHashTableStartIndex * kPointerSize);

  // Bump the elements count.
  Node* const number_of_elements =
      LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset);
  StoreObjectFieldNoWriteBarrier(table, OrderedHashSet::kNumberOfElementsOffset,
                                 SmiAdd(number_of_elements, SmiConstant(1)));
}

TF_BUILTIN(SetDelete, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
                         "Set.prototype.delete");

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);

  VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  Label entry_found(this), not_found(this);

  TryLookupOrderedHashTableIndex<OrderedHashSet>(table, key, context,
                                                 &entry_start_position_or_hash,
                                                 &entry_found, &not_found);

  BIND(&not_found);
  Return(FalseConstant());

  BIND(&entry_found);
  // If we found the entry, mark the entry as deleted.
  StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
                         TheHoleConstant(), UPDATE_WRITE_BARRIER,
                         kPointerSize * OrderedHashSet::kHashTableStartIndex);

  // Decrement the number of elements, increment the number of deleted elements.
  Node* const number_of_elements = SmiSub(
      CAST(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset)),
      SmiConstant(1));
  StoreObjectFieldNoWriteBarrier(table, OrderedHashSet::kNumberOfElementsOffset,
                                 number_of_elements);
  Node* const number_of_deleted =
      SmiAdd(CAST(LoadObjectField(
                 table, OrderedHashSet::kNumberOfDeletedElementsOffset)),
             SmiConstant(1));
  StoreObjectFieldNoWriteBarrier(
      table, OrderedHashSet::kNumberOfDeletedElementsOffset, number_of_deleted);

  Node* const number_of_buckets =
      LoadFixedArrayElement(table, OrderedHashSet::kNumberOfBucketsIndex);

  // If there fewer elements than #buckets / 2, shrink the table.
  Label shrink(this);
  GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements),
                     number_of_buckets),
         &shrink);
  Return(TrueConstant());

  BIND(&shrink);
  CallRuntime(Runtime::kSetShrink, context, receiver);
  Return(TrueConstant());
}

TF_BUILTIN(MapPrototypeEntries, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
                         "Map.prototype.entries");
  Return(AllocateJSCollectionIterator<JSMapIterator>(
      context, Context::MAP_KEY_VALUE_ITERATOR_MAP_INDEX, receiver));
}

TF_BUILTIN(MapPrototypeGetSize, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
                         "get Map.prototype.size");
  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
  Return(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset));
}

TF_BUILTIN(MapPrototypeForEach, CollectionsBuiltinsAssembler) {
  const char* const kMethodName = "Map.prototype.forEach";
  Node* const argc = Parameter(BuiltinDescriptor::kArgumentsCount);
  Node* const context = Parameter(BuiltinDescriptor::kContext);
  CodeStubArguments args(this, ChangeInt32ToIntPtr(argc));
  Node* const receiver = args.GetReceiver();
  Node* const callback = args.GetOptionalArgumentValue(0);
  Node* const this_arg = args.GetOptionalArgumentValue(1);

  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, kMethodName);

  // Ensure that {callback} is actually callable.
  Label callback_not_callable(this, Label::kDeferred);
  GotoIf(TaggedIsSmi(callback), &callback_not_callable);
  GotoIfNot(IsCallable(callback), &callback_not_callable);

  VARIABLE(var_index, MachineType::PointerRepresentation(), IntPtrConstant(0));
  VARIABLE(var_table, MachineRepresentation::kTagged,
           LoadObjectField(receiver, JSMap::kTableOffset));
  Label loop(this, {&var_index, &var_table}), done_loop(this);
  Goto(&loop);
  BIND(&loop);
  {
    // Transition {table} and {index} if there was any modification to
    // the {receiver} while we're iterating.
    Node* index = var_index.value();
    Node* table = var_table.value();
    std::tie(table, index) =
        Transition<OrderedHashMap>(table, index, [](Node*, Node*) {});

    // Read the next entry from the {table}, skipping holes.
    Node* entry_key;
    Node* entry_start_position;
    std::tie(entry_key, entry_start_position, index) =
        NextSkipHoles<OrderedHashMap>(table, index, &done_loop);

    // Load the entry value as well.
    Node* entry_value = LoadFixedArrayElement(
        table, entry_start_position,
        (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset) *
            kPointerSize);

    // Invoke the {callback} passing the {entry_key}, {entry_value} and the
    // {receiver}.
    CallJS(CodeFactory::Call(isolate()), context, callback, this_arg,
           entry_value, entry_key, receiver);

    // Continue with the next entry.
    var_index.Bind(index);
    var_table.Bind(table);
    Goto(&loop);
  }

  BIND(&done_loop);
  args.PopAndReturn(UndefinedConstant());

  BIND(&callback_not_callable);
  {
    CallRuntime(Runtime::kThrowCalledNonCallable, context, callback);
    Unreachable();
  }
}

TF_BUILTIN(MapPrototypeKeys, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.keys");
  Return(AllocateJSCollectionIterator<JSMapIterator>(
      context, Context::MAP_KEY_ITERATOR_MAP_INDEX, receiver));
}

TF_BUILTIN(MapPrototypeValues, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
                         "Map.prototype.values");
  Return(AllocateJSCollectionIterator<JSMapIterator>(
      context, Context::MAP_VALUE_ITERATOR_MAP_INDEX, receiver));
}

TF_BUILTIN(MapIteratorPrototypeNext, CollectionsBuiltinsAssembler) {
  const char* const kMethodName = "Map Iterator.prototype.next";
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);

  // Ensure that the {receiver} is actually a JSMapIterator.
  Label if_receiver_valid(this), if_receiver_invalid(this, Label::kDeferred);
  GotoIf(TaggedIsSmi(receiver), &if_receiver_invalid);
  Node* const receiver_instance_type = LoadInstanceType(receiver);
  GotoIf(
      InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_VALUE_ITERATOR_TYPE),
      &if_receiver_valid);
  GotoIf(InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_ITERATOR_TYPE),
         &if_receiver_valid);
  Branch(InstanceTypeEqual(receiver_instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
         &if_receiver_valid, &if_receiver_invalid);
  BIND(&if_receiver_invalid);
  ThrowIncompatibleMethodReceiver(context, kMethodName, receiver);
  BIND(&if_receiver_valid);

  // Check if the {receiver} is exhausted.
  VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
  VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
  Label return_value(this, {&var_done, &var_value}), return_entry(this),
      return_end(this, Label::kDeferred);

  // Transition the {receiver} table if necessary.
  Node* table;
  Node* index;
  std::tie(table, index) =
      TransitionAndUpdate<JSMapIterator, OrderedHashMap>(receiver);

  // Read the next entry from the {table}, skipping holes.
  Node* entry_key;
  Node* entry_start_position;
  std::tie(entry_key, entry_start_position, index) =
      NextSkipHoles<OrderedHashMap>(table, index, &return_end);
  StoreObjectFieldNoWriteBarrier(receiver, JSMapIterator::kIndexOffset,
                                 SmiTag(index));
  var_value.Bind(entry_key);
  var_done.Bind(FalseConstant());

  // Check how to return the {key} (depending on {receiver} type).
  GotoIf(InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_ITERATOR_TYPE),
         &return_value);
  var_value.Bind(LoadFixedArrayElement(
      table, entry_start_position,
      (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset) *
          kPointerSize));
  Branch(InstanceTypeEqual(receiver_instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
         &return_value, &return_entry);

  BIND(&return_entry);
  {
    Node* result =
        AllocateJSIteratorResultForEntry(context, entry_key, var_value.value());
    Return(result);
  }

  BIND(&return_value);
  {
    Node* result =
        AllocateJSIteratorResult(context, var_value.value(), var_done.value());
    Return(result);
  }

  BIND(&return_end);
  {
    StoreObjectFieldRoot(receiver, JSMapIterator::kTableOffset,
                         Heap::kEmptyOrderedHashTableRootIndex);
    Goto(&return_value);
  }
}

TF_BUILTIN(SetHas, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.has");

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);

  VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  VARIABLE(result, MachineRepresentation::kTaggedSigned, IntPtrConstant(0));
  Label if_key_smi(this), if_key_string(this), if_key_heap_number(this),
      if_key_bigint(this), entry_found(this), not_found(this), done(this);

  GotoIf(TaggedIsSmi(key), &if_key_smi);

  Node* key_map = LoadMap(key);
  Node* key_instance_type = LoadMapInstanceType(key_map);

  GotoIf(IsStringInstanceType(key_instance_type), &if_key_string);
  GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number);
  GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint);

  FindOrderedHashTableEntryForOtherKey<OrderedHashSet>(
      context, table, key, &entry_start_position, &entry_found, &not_found);

  BIND(&if_key_smi);
  {
    FindOrderedHashTableEntryForSmiKey<OrderedHashSet>(
        table, key, &entry_start_position, &entry_found, &not_found);
  }

  BIND(&if_key_string);
  {
    FindOrderedHashTableEntryForStringKey<OrderedHashSet>(
        context, table, key, &entry_start_position, &entry_found, &not_found);
  }

  BIND(&if_key_heap_number);
  {
    FindOrderedHashTableEntryForHeapNumberKey<OrderedHashSet>(
        context, table, key, &entry_start_position, &entry_found, &not_found);
  }

  BIND(&if_key_bigint);
  {
    FindOrderedHashTableEntryForBigIntKey<OrderedHashSet>(
        context, table, key, &entry_start_position, &entry_found, &not_found);
  }

  BIND(&entry_found);
  Return(TrueConstant());

  BIND(&not_found);
  Return(FalseConstant());
}

TF_BUILTIN(SetPrototypeEntries, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
                         "Set.prototype.entries");
  Return(AllocateJSCollectionIterator<JSSetIterator>(
      context, Context::SET_KEY_VALUE_ITERATOR_MAP_INDEX, receiver));
}

TF_BUILTIN(SetPrototypeGetSize, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
                         "get Set.prototype.size");
  Node* const table = LoadObjectField(receiver, JSSet::kTableOffset);
  Return(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset));
}

TF_BUILTIN(SetPrototypeForEach, CollectionsBuiltinsAssembler) {
  const char* const kMethodName = "Set.prototype.forEach";
  Node* const argc = Parameter(BuiltinDescriptor::kArgumentsCount);
  Node* const context = Parameter(BuiltinDescriptor::kContext);
  CodeStubArguments args(this, ChangeInt32ToIntPtr(argc));
  Node* const receiver = args.GetReceiver();
  Node* const callback = args.GetOptionalArgumentValue(0);
  Node* const this_arg = args.GetOptionalArgumentValue(1);

  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, kMethodName);

  // Ensure that {callback} is actually callable.
  Label callback_not_callable(this, Label::kDeferred);
  GotoIf(TaggedIsSmi(callback), &callback_not_callable);
  GotoIfNot(IsCallable(callback), &callback_not_callable);

  VARIABLE(var_index, MachineType::PointerRepresentation(), IntPtrConstant(0));
  VARIABLE(var_table, MachineRepresentation::kTagged,
           LoadObjectField(receiver, JSSet::kTableOffset));
  Label loop(this, {&var_index, &var_table}), done_loop(this);
  Goto(&loop);
  BIND(&loop);
  {
    // Transition {table} and {index} if there was any modification to
    // the {receiver} while we're iterating.
    Node* index = var_index.value();
    Node* table = var_table.value();
    std::tie(table, index) =
        Transition<OrderedHashSet>(table, index, [](Node*, Node*) {});

    // Read the next entry from the {table}, skipping holes.
    Node* entry_key;
    Node* entry_start_position;
    std::tie(entry_key, entry_start_position, index) =
        NextSkipHoles<OrderedHashSet>(table, index, &done_loop);

    // Invoke the {callback} passing the {entry_key} (twice) and the {receiver}.
    CallJS(CodeFactory::Call(isolate()), context, callback, this_arg, entry_key,
           entry_key, receiver);

    // Continue with the next entry.
    var_index.Bind(index);
    var_table.Bind(table);
    Goto(&loop);
  }

  BIND(&done_loop);
  args.PopAndReturn(UndefinedConstant());

  BIND(&callback_not_callable);
  {
    CallRuntime(Runtime::kThrowCalledNonCallable, context, callback);
    Unreachable();
  }
}

TF_BUILTIN(SetPrototypeValues, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
                         "Set.prototype.values");
  Return(AllocateJSCollectionIterator<JSSetIterator>(
      context, Context::SET_VALUE_ITERATOR_MAP_INDEX, receiver));
}

TF_BUILTIN(SetIteratorPrototypeNext, CollectionsBuiltinsAssembler) {
  const char* const kMethodName = "Set Iterator.prototype.next";
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);

  // Ensure that the {receiver} is actually a JSSetIterator.
  Label if_receiver_valid(this), if_receiver_invalid(this, Label::kDeferred);
  GotoIf(TaggedIsSmi(receiver), &if_receiver_invalid);
  Node* const receiver_instance_type = LoadInstanceType(receiver);
  GotoIf(InstanceTypeEqual(receiver_instance_type, JS_SET_VALUE_ITERATOR_TYPE),
         &if_receiver_valid);
  Branch(
      InstanceTypeEqual(receiver_instance_type, JS_SET_KEY_VALUE_ITERATOR_TYPE),
      &if_receiver_valid, &if_receiver_invalid);
  BIND(&if_receiver_invalid);
  ThrowIncompatibleMethodReceiver(context, kMethodName, receiver);
  BIND(&if_receiver_valid);

  // Check if the {receiver} is exhausted.
  VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
  VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
  Label return_value(this, {&var_done, &var_value}), return_entry(this),
      return_end(this, Label::kDeferred);

  // Transition the {receiver} table if necessary.
  Node* table;
  Node* index;
  std::tie(table, index) =
      TransitionAndUpdate<JSSetIterator, OrderedHashSet>(receiver);

  // Read the next entry from the {table}, skipping holes.
  Node* entry_key;
  Node* entry_start_position;
  std::tie(entry_key, entry_start_position, index) =
      NextSkipHoles<OrderedHashSet>(table, index, &return_end);
  StoreObjectFieldNoWriteBarrier(receiver, JSSetIterator::kIndexOffset,
                                 SmiTag(index));
  var_value.Bind(entry_key);
  var_done.Bind(FalseConstant());

  // Check how to return the {key} (depending on {receiver} type).
  Branch(InstanceTypeEqual(receiver_instance_type, JS_SET_VALUE_ITERATOR_TYPE),
         &return_value, &return_entry);

  BIND(&return_entry);
  {
    Node* result = AllocateJSIteratorResultForEntry(context, var_value.value(),
                                                    var_value.value());
    Return(result);
  }

  BIND(&return_value);
  {
    Node* result =
        AllocateJSIteratorResult(context, var_value.value(), var_done.value());
    Return(result);
  }

  BIND(&return_end);
  {
    StoreObjectFieldRoot(receiver, JSSetIterator::kTableOffset,
                         Heap::kEmptyOrderedHashTableRootIndex);
    Goto(&return_value);
  }
}

template <typename CollectionType>
void CollectionsBuiltinsAssembler::TryLookupOrderedHashTableIndex(
    Node* const table, Node* const key, Node* const context, Variable* result,
    Label* if_entry_found, Label* if_not_found) {
  Label if_key_smi(this), if_key_string(this), if_key_heap_number(this),
      if_key_bigint(this);

  GotoIf(TaggedIsSmi(key), &if_key_smi);

  Node* key_map = LoadMap(key);
  Node* key_instance_type = LoadMapInstanceType(key_map);

  GotoIf(IsStringInstanceType(key_instance_type), &if_key_string);
  GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number);
  GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint);

  FindOrderedHashTableEntryForOtherKey<CollectionType>(
      context, table, key, result, if_entry_found, if_not_found);

  BIND(&if_key_smi);
  {
    FindOrderedHashTableEntryForSmiKey<CollectionType>(
        table, key, result, if_entry_found, if_not_found);
  }

  BIND(&if_key_string);
  {
    FindOrderedHashTableEntryForStringKey<CollectionType>(
        context, table, key, result, if_entry_found, if_not_found);
  }

  BIND(&if_key_heap_number);
  {
    FindOrderedHashTableEntryForHeapNumberKey<CollectionType>(
        context, table, key, result, if_entry_found, if_not_found);
  }

  BIND(&if_key_bigint);
  {
    FindOrderedHashTableEntryForBigIntKey<CollectionType>(
        context, table, key, result, if_entry_found, if_not_found);
  }
}

TF_BUILTIN(MapLookupHashIndex, CollectionsBuiltinsAssembler) {
  Node* const table = Parameter(Descriptor::kTable);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  Label entry_found(this), not_found(this);

  TryLookupOrderedHashTableIndex<OrderedHashMap>(
      table, key, context, &entry_start_position, &entry_found, &not_found);

  BIND(&entry_found);
  Node* index = IntPtrAdd(entry_start_position.value(),
                          IntPtrConstant(OrderedHashMap::kHashTableStartIndex +
                                         OrderedHashMap::kValueOffset));
  Return(SmiTag(index));

  BIND(&not_found);
  Return(SmiConstant(-1));
}

TF_BUILTIN(WeakMapLookupHashIndex, CollectionsBuiltinsAssembler) {
  Node* const table = Parameter(Descriptor::kTable);
  Node* const key = Parameter(Descriptor::kKey);

  Label if_found(this), if_not_found(this);

  Node* const capacity =
      SmiUntag(LoadFixedArrayElement(table, WeakHashTable::kCapacityIndex));
  Node* const mask = IntPtrSub(capacity, IntPtrConstant(1));

  Node* const hash = GetHash(key);

  GotoIf(IntPtrLessThan(hash, IntPtrConstant(0)), &if_not_found);

  // See HashTable::FirstProbe().
  Node* entry = WordAnd(hash, mask);

  VARIABLE(var_count, MachineType::PointerRepresentation(), IntPtrConstant(0));
  VARIABLE(var_entry, MachineType::PointerRepresentation(), entry);
  Variable* loop_vars[] = {&var_count, &var_entry};
  Label loop(this, arraysize(loop_vars), loop_vars);
  Goto(&loop);
  BIND(&loop);
  Node* index;
  {
    Node* entry = var_entry.value();

    index = IntPtrMul(entry, IntPtrConstant(WeakHashTable::kEntrySize));
    index =
        IntPtrAdd(index, IntPtrConstant(WeakHashTable::kElementsStartIndex));

    Node* current = LoadFixedArrayElement(table, index);
    GotoIf(WordEqual(current, UndefinedConstant()), &if_not_found);
    GotoIf(WordEqual(current, key), &if_found);

    // See HashTable::NextProbe().
    Increment(&var_count);
    entry = WordAnd(IntPtrAdd(entry, var_count.value()), mask);

    var_entry.Bind(entry);
    Goto(&loop);
  }

  BIND(&if_not_found);
  Return(SmiConstant(-1));

  BIND(&if_found);
  Return(SmiTag(Signed(IntPtrAdd(index, IntPtrConstant(1)))));
}

TF_BUILTIN(WeakMapGet, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  Label return_undefined(this);

  ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
                         "WeakMap.prototype.get");

  GotoIf(TaggedIsSmi(key), &return_undefined);
  GotoIfNot(IsJSReceiver(key), &return_undefined);

  Node* const table = LoadObjectField(receiver, JSWeakCollection::kTableOffset);

  Node* const index =
      CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);

  GotoIf(WordEqual(index, SmiConstant(-1)), &return_undefined);

  Return(LoadFixedArrayElement(table, SmiUntag(index)));

  BIND(&return_undefined);
  Return(UndefinedConstant());
}

TF_BUILTIN(WeakMapHas, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  Label return_false(this);

  ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
                         "WeakMap.prototype.get");

  GotoIf(TaggedIsSmi(key), &return_false);
  GotoIfNot(IsJSReceiver(key), &return_false);

  Node* const table = LoadObjectField(receiver, JSWeakCollection::kTableOffset);

  Node* const index =
      CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);

  GotoIf(WordEqual(index, SmiConstant(-1)), &return_false);

  Return(TrueConstant());

  BIND(&return_false);
  Return(FalseConstant());
}

TF_BUILTIN(WeakSetHas, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  Label return_false(this);

  ThrowIfNotInstanceType(context, receiver, JS_WEAK_SET_TYPE,
                         "WeakSet.prototype.get");

  GotoIf(TaggedIsSmi(key), &return_false);
  GotoIfNot(IsJSReceiver(key), &return_false);

  Node* const table = LoadObjectField(receiver, JSWeakCollection::kTableOffset);

  Node* const index =
      CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);

  GotoIf(WordEqual(index, SmiConstant(-1)), &return_false);

  Return(TrueConstant());

  BIND(&return_false);
  Return(FalseConstant());
}

}  // namespace internal
}  // namespace v8