1// Copyright 2018 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_BUILTINS_BUILTINS_COLLECTIONS_GEN_H_
6#define V8_BUILTINS_BUILTINS_COLLECTIONS_GEN_H_
7
8#include "src/codegen/code-stub-assembler.h"
9
10namespace v8 {
11namespace internal {
12
13void BranchIfIterableWithOriginalKeyOrValueMapIterator(
14    compiler::CodeAssemblerState* state, TNode<Object> iterable,
15    TNode<Context> context, compiler::CodeAssemblerLabel* if_true,
16    compiler::CodeAssemblerLabel* if_false);
17
18void BranchIfIterableWithOriginalValueSetIterator(
19    compiler::CodeAssemblerState* state, TNode<Object> iterable,
20    TNode<Context> context, compiler::CodeAssemblerLabel* if_true,
21    compiler::CodeAssemblerLabel* if_false);
22
23class BaseCollectionsAssembler : public CodeStubAssembler {
24 public:
25  explicit BaseCollectionsAssembler(compiler::CodeAssemblerState* state)
26      : CodeStubAssembler(state) {}
27
28  virtual ~BaseCollectionsAssembler() = default;
29
30  void GotoIfCannotBeHeldWeakly(const TNode<Object> obj,
31                                Label* if_cannot_be_held_weakly);
32
33 protected:
34  enum Variant { kMap, kSet, kWeakMap, kWeakSet };
35
36  // Adds an entry to a collection.  For Maps, properly handles extracting the
37  // key and value from the entry (see LoadKeyValue()).
38  void AddConstructorEntry(Variant variant, TNode<Context> context,
39                           TNode<Object> collection, TNode<Object> add_function,
40                           TNode<Object> key_value,
41                           Label* if_may_have_side_effects = nullptr,
42                           Label* if_exception = nullptr,
43                           TVariable<Object>* var_exception = nullptr);
44
45  // Adds constructor entries to a collection.  Choosing a fast path when
46  // possible.
47  void AddConstructorEntries(Variant variant, TNode<Context> context,
48                             TNode<Context> native_context,
49                             TNode<HeapObject> collection,
50                             TNode<Object> initial_entries);
51
52  // Fast path for adding constructor entries.  Assumes the entries are a fast
53  // JS array (see CodeStubAssembler::BranchIfFastJSArray()).
54  void AddConstructorEntriesFromFastJSArray(Variant variant,
55                                            TNode<Context> context,
56                                            TNode<Context> native_context,
57                                            TNode<Object> collection,
58                                            TNode<JSArray> fast_jsarray,
59                                            Label* if_may_have_side_effects);
60
61  // Adds constructor entries to a collection using the iterator protocol.
62  void AddConstructorEntriesFromIterable(Variant variant,
63                                         TNode<Context> context,
64                                         TNode<Context> native_context,
65                                         TNode<Object> collection,
66                                         TNode<Object> iterable);
67
68  // Constructs a collection instance. Choosing a fast path when possible.
69  TNode<JSObject> AllocateJSCollection(TNode<Context> context,
70                                       TNode<JSFunction> constructor,
71                                       TNode<JSReceiver> new_target);
72
73  // Fast path for constructing a collection instance if the constructor
74  // function has not been modified.
75  TNode<JSObject> AllocateJSCollectionFast(TNode<JSFunction> constructor);
76
77  // Fallback for constructing a collection instance if the constructor function
78  // has been modified.
79  TNode<JSObject> AllocateJSCollectionSlow(TNode<Context> context,
80                                           TNode<JSFunction> constructor,
81                                           TNode<JSReceiver> new_target);
82
83  // Allocates the backing store for a collection.
84  virtual TNode<HeapObject> AllocateTable(
85      Variant variant, TNode<IntPtrT> at_least_space_for) = 0;
86
87  // Main entry point for a collection constructor builtin.
88  void GenerateConstructor(Variant variant,
89                           Handle<String> constructor_function_name,
90                           TNode<Object> new_target, TNode<IntPtrT> argc,
91                           TNode<Context> context);
92
93  // Retrieves the collection function that adds an entry. `set` for Maps and
94  // `add` for Sets.
95  TNode<Object> GetAddFunction(Variant variant, TNode<Context> context,
96                               TNode<Object> collection);
97
98  // Retrieves the collection constructor function.
99  TNode<JSFunction> GetConstructor(Variant variant,
100                                   TNode<Context> native_context);
101
102  // Retrieves the initial collection function that adds an entry. Should only
103  // be called when it is certain that a collection prototype's map hasn't been
104  // changed.
105  TNode<JSFunction> GetInitialAddFunction(Variant variant,
106                                          TNode<Context> native_context);
107
108  // Checks whether {collection}'s initial add/set function has been modified
109  // (depending on {variant}, loaded from {native_context}).
110  void GotoIfInitialAddFunctionModified(Variant variant,
111                                        TNode<NativeContext> native_context,
112                                        TNode<HeapObject> collection,
113                                        Label* if_modified);
114
115  // Gets root index for the name of the add/set function.
116  RootIndex GetAddFunctionNameIndex(Variant variant);
117
118  // Retrieves the offset to access the backing table from the collection.
119  int GetTableOffset(Variant variant);
120
121  // Estimates the number of entries the collection will have after adding the
122  // entries passed in the constructor. AllocateTable() can use this to avoid
123  // the time of growing/rehashing when adding the constructor entries.
124  TNode<IntPtrT> EstimatedInitialSize(TNode<Object> initial_entries,
125                                      TNode<BoolT> is_fast_jsarray);
126
127  // Determines whether the collection's prototype has been modified.
128  TNode<BoolT> HasInitialCollectionPrototype(Variant variant,
129                                             TNode<Context> native_context,
130                                             TNode<Object> collection);
131
132  // Gets the initial prototype map for given collection {variant}.
133  TNode<Map> GetInitialCollectionPrototype(Variant variant,
134                                           TNode<Context> native_context);
135
136  // Loads an element from a fixed array.  If the element is the hole, returns
137  // `undefined`.
138  TNode<Object> LoadAndNormalizeFixedArrayElement(TNode<FixedArray> elements,
139                                                  TNode<IntPtrT> index);
140
141  // Loads an element from a fixed double array.  If the element is the hole,
142  // returns `undefined`.
143  TNode<Object> LoadAndNormalizeFixedDoubleArrayElement(
144      TNode<HeapObject> elements, TNode<IntPtrT> index);
145};
146
147class WeakCollectionsBuiltinsAssembler : public BaseCollectionsAssembler {
148 public:
149  explicit WeakCollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state)
150      : BaseCollectionsAssembler(state) {}
151
152 protected:
153  void AddEntry(TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
154                TNode<Object> key, TNode<Object> value,
155                TNode<IntPtrT> number_of_elements);
156
157  TNode<HeapObject> AllocateTable(Variant variant,
158                                  TNode<IntPtrT> at_least_space_for) override;
159
160  TNode<IntPtrT> GetHash(const TNode<HeapObject> key, Label* if_no_hash);
161  // Generates and sets the identity for a JSRececiver.
162  TNode<Smi> CreateIdentityHash(TNode<Object> receiver);
163  TNode<IntPtrT> EntryMask(TNode<IntPtrT> capacity);
164
165  // Builds code that finds the EphemeronHashTable entry for a {key} using the
166  // comparison code generated by {key_compare}. The key index is returned if
167  // the {key} is found.
168  using KeyComparator =
169      std::function<void(TNode<Object> entry_key, Label* if_same)>;
170  TNode<IntPtrT> FindKeyIndex(TNode<HeapObject> table, TNode<IntPtrT> key_hash,
171                              TNode<IntPtrT> entry_mask,
172                              const KeyComparator& key_compare);
173
174  // Builds code that finds an EphemeronHashTable entry available for a new
175  // entry.
176  TNode<IntPtrT> FindKeyIndexForInsertion(TNode<HeapObject> table,
177                                          TNode<IntPtrT> key_hash,
178                                          TNode<IntPtrT> entry_mask);
179
180  // Builds code that finds the EphemeronHashTable entry with key that matches
181  // {key} and returns the entry's key index. If {key} cannot be found, jumps to
182  // {if_not_found}.
183  TNode<IntPtrT> FindKeyIndexForKey(TNode<HeapObject> table, TNode<Object> key,
184                                    TNode<IntPtrT> hash,
185                                    TNode<IntPtrT> entry_mask,
186                                    Label* if_not_found);
187
188  TNode<Word32T> InsufficientCapacityToAdd(TNode<IntPtrT> capacity,
189                                           TNode<IntPtrT> number_of_elements,
190                                           TNode<IntPtrT> number_of_deleted);
191  TNode<IntPtrT> KeyIndexFromEntry(TNode<IntPtrT> entry);
192
193  TNode<IntPtrT> LoadNumberOfElements(TNode<EphemeronHashTable> table,
194                                      int offset);
195  TNode<IntPtrT> LoadNumberOfDeleted(TNode<EphemeronHashTable> table,
196                                     int offset = 0);
197  TNode<EphemeronHashTable> LoadTable(TNode<JSWeakCollection> collection);
198  TNode<IntPtrT> LoadTableCapacity(TNode<EphemeronHashTable> table);
199
200  void RemoveEntry(TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
201                   TNode<IntPtrT> number_of_elements);
202  TNode<BoolT> ShouldRehash(TNode<IntPtrT> number_of_elements,
203                            TNode<IntPtrT> number_of_deleted);
204  TNode<Word32T> ShouldShrink(TNode<IntPtrT> capacity,
205                              TNode<IntPtrT> number_of_elements);
206  TNode<IntPtrT> ValueIndexFromKeyIndex(TNode<IntPtrT> key_index);
207};
208
209}  // namespace internal
210}  // namespace v8
211
212#endif  // V8_BUILTINS_BUILTINS_COLLECTIONS_GEN_H_
213