1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #ifndef vm_Iteration_h
8 #define vm_Iteration_h
9
10 /*
11 * JavaScript iterators.
12 */
13
14 #include "mozilla/ArrayUtils.h"
15 #include "mozilla/MemoryReporting.h"
16
17 #include "builtin/SelfHostingDefines.h"
18 #include "gc/Barrier.h"
19 #include "vm/Stack.h"
20
21 namespace js {
22
23 class PlainObject;
24 class PropertyIteratorObject;
25
26 struct NativeIterator {
27 private:
28 // Object being iterated. Non-null except in NativeIterator sentinels and
29 // empty property iterators created when |null| or |undefined| is iterated.
30 GCPtrObject objectBeingIterated_ = {};
31
32 // Internal iterator object.
33 const GCPtrObject iterObj_ = {};
34
35 // The end of GCPtrShapes that appear directly after |this|, as part of an
36 // overall allocation that stores |*this|, shapes, and iterated strings.
37 // Once this has been fully initialized, it also equals the start of iterated
38 // strings.
39 GCPtrShape* shapesEnd_; // initialized by constructor
40
41 // The next property, pointing into an array of strings directly after any
42 // GCPtrShapes that appear directly after |*this|, as part of an overall
43 // allocation that stores |*this|, shapes, and iterated strings.
44 GCPtrLinearString* propertyCursor_; // initialized by constructor
45
46 // The limit/end of properties to iterate (and, assuming no error occurred
47 // while constructing this NativeIterator, the end of the full allocation
48 // storing |*this|, shapes, and strings). Beware! This value may change as
49 // properties are deleted from the observed object.
50 GCPtrLinearString* propertiesEnd_; // initialized by constructor
51
52 HashNumber shapesHash_; // initialized by constructor
53
54 public:
55 // For cacheable native iterators, whether the iterator is currently
56 // active. Not serialized by XDR.
57 struct Flags {
58 // This flag is set when all shapes and properties associated with this
59 // NativeIterator have been initialized, such that |shapesEnd_|, in
60 // addition to being the end of shapes, is also the beginning of
61 // properties.
62 //
63 // This flag is only *not* set when a NativeIterator is in the process
64 // of being constructed. At such time |shapesEnd_| accounts only for
65 // shapes that have been initialized -- potentially none of them.
66 // Instead, |propertyCursor_| is initialized to the ultimate/actual
67 // start of properties and must be used instead of |propertiesBegin()|,
68 // which asserts that this flag is present to guard against misuse.
69 static constexpr uint32_t Initialized = 0x1;
70
71 // This flag indicates that this NativeIterator is currently being used
72 // to enumerate an object's properties and has not yet been closed.
73 static constexpr uint32_t Active = 0x2;
74
75 // This flag indicates that the object being enumerated by this
76 // |NativeIterator| had a property deleted from it before it was
77 // visited, forcing the properties array in this to be mutated to
78 // remove it.
79 static constexpr uint32_t HasUnvisitedPropertyDeletion = 0x4;
80
81 // If any of these bits are set on a |NativeIterator|, it isn't
82 // currently reusable. (An active |NativeIterator| can't be stolen
83 // *right now*; a |NativeIterator| that's had its properties mutated
84 // can never be reused, because it would give incorrect results.)
85 static constexpr uint32_t NotReusable =
86 Active | HasUnvisitedPropertyDeletion;
87 };
88
89 private:
90 static constexpr uint32_t FlagsBits = 3;
91 static constexpr uint32_t FlagsMask = (1 << FlagsBits) - 1;
92
93 public:
94 static constexpr uint32_t PropCountLimit = 1 << (32 - FlagsBits);
95
96 private:
97 // While in compartment->enumerators, these form a doubly linked list.
98 NativeIterator* next_ = nullptr;
99 NativeIterator* prev_ = nullptr;
100
101 // Stores Flags bits in the lower bits and the initial property count above
102 // them.
103 uint32_t flagsAndCount_ = 0;
104
105 #ifdef DEBUG
106 // If true, this iterator may contain indexed properties that came from
107 // objects on the prototype chain. This is used by certain debug assertions.
108 bool maybeHasIndexedPropertiesFromProto_ = false;
109 #endif
110
111 // END OF PROPERTIES
112
113 // No further fields appear after here *in NativeIterator*, but this class
114 // is always allocated with space tacked on immediately after |this| to
115 // store iterated property names up to |props_end| and |numShapes| shapes
116 // after that.
117
118 public:
119 /**
120 * Initialize a NativeIterator properly allocated for |props.length()|
121 * properties and |numShapes| shapes.
122 *
123 * Despite being a constructor, THIS FUNCTION CAN REPORT ERRORS. Users
124 * MUST set |*hadError = false| on entry and consider |*hadError| on return
125 * to mean this function failed.
126 */
127 NativeIterator(JSContext* cx, Handle<PropertyIteratorObject*> propIter,
128 Handle<JSObject*> objBeingIterated, HandleIdVector props,
129 uint32_t numShapes, HashNumber shapesHash, bool* hadError);
130
131 /** Initialize an |ObjectRealm::enumerators| sentinel. */
132 NativeIterator();
133
objectBeingIteratedNativeIterator134 JSObject* objectBeingIterated() const { return objectBeingIterated_; }
135
changeObjectBeingIteratedNativeIterator136 void changeObjectBeingIterated(JSObject& obj) { objectBeingIterated_ = &obj; }
137
shapesBeginNativeIterator138 GCPtrShape* shapesBegin() const {
139 static_assert(alignof(GCPtrShape) <= alignof(NativeIterator),
140 "NativeIterator must be aligned to begin storing "
141 "GCPtrShapes immediately after it with no required padding");
142 const NativeIterator* immediatelyAfter = this + 1;
143 auto* afterNonConst = const_cast<NativeIterator*>(immediatelyAfter);
144 return reinterpret_cast<GCPtrShape*>(afterNonConst);
145 }
146
shapesEndNativeIterator147 GCPtrShape* shapesEnd() const { return shapesEnd_; }
148
shapeCountNativeIterator149 uint32_t shapeCount() const {
150 return mozilla::PointerRangeSize(shapesBegin(), shapesEnd());
151 }
152
propertiesBeginNativeIterator153 GCPtrLinearString* propertiesBegin() const {
154 static_assert(alignof(GCPtrShape) >= alignof(GCPtrLinearString),
155 "GCPtrLinearStrings for properties must be able to appear "
156 "directly after any GCPtrShapes after this NativeIterator, "
157 "with no padding space required for correct alignment");
158 static_assert(alignof(NativeIterator) >= alignof(GCPtrLinearString),
159 "GCPtrLinearStrings for properties must be able to appear "
160 "directly after this NativeIterator when no GCPtrShapes are "
161 "present, with no padding space required for correct "
162 "alignment");
163
164 // We *could* just check the assertion below if we wanted, but the
165 // incompletely-initialized NativeIterator case matters for so little
166 // code that we prefer not imposing the condition-check on every single
167 // user.
168 MOZ_ASSERT(isInitialized(),
169 "NativeIterator must be initialized, or else |shapesEnd_| "
170 "isn't necessarily the start of properties and instead "
171 "|propertyCursor_| is");
172
173 return reinterpret_cast<GCPtrLinearString*>(shapesEnd_);
174 }
175
propertiesEndNativeIterator176 GCPtrLinearString* propertiesEnd() const { return propertiesEnd_; }
177
nextPropertyNativeIterator178 GCPtrLinearString* nextProperty() const { return propertyCursor_; }
179
nextIteratedValueAndAdvanceNativeIterator180 MOZ_ALWAYS_INLINE JS::Value nextIteratedValueAndAdvance() {
181 if (propertyCursor_ >= propertiesEnd_) {
182 MOZ_ASSERT(propertyCursor_ == propertiesEnd_);
183 return JS::MagicValue(JS_NO_ITER_VALUE);
184 }
185
186 JSLinearString* str = *propertyCursor_;
187 incCursor();
188 return JS::StringValue(str);
189 }
190
resetPropertyCursorForReuseNativeIterator191 void resetPropertyCursorForReuse() {
192 MOZ_ASSERT(isInitialized());
193
194 // This function is called unconditionally on IteratorClose, so
195 // unvisited properties might have been deleted, so we can't assert
196 // this NativeIterator is reusable. (Should we not bother resetting
197 // the cursor in that case?)
198
199 // Note: JIT code inlines |propertyCursor_| resetting when an iterator
200 // ends: see |CodeGenerator::visitIteratorEnd|.
201 propertyCursor_ = propertiesBegin();
202 }
203
previousPropertyWasNativeIterator204 bool previousPropertyWas(JS::Handle<JSLinearString*> str) {
205 MOZ_ASSERT(isInitialized());
206 return propertyCursor_ > propertiesBegin() && propertyCursor_[-1] == str;
207 }
208
numKeysNativeIterator209 size_t numKeys() const {
210 return mozilla::PointerRangeSize(propertiesBegin(), propertiesEnd());
211 }
212
trimLastPropertyNativeIterator213 void trimLastProperty() {
214 MOZ_ASSERT(isInitialized());
215
216 propertiesEnd_--;
217
218 // This invokes the pre barrier on this property, since it's no longer
219 // going to be marked, and it ensures that any existing remembered set
220 // entry will be dropped.
221 *propertiesEnd_ = nullptr;
222 }
223
iterObjNativeIterator224 JSObject* iterObj() const { return iterObj_; }
currentPropertyNativeIterator225 GCPtrLinearString* currentProperty() const {
226 MOZ_ASSERT(propertyCursor_ < propertiesEnd());
227 return propertyCursor_;
228 }
229
nextNativeIterator230 NativeIterator* next() { return next_; }
231
incCursorNativeIterator232 void incCursor() {
233 MOZ_ASSERT(isInitialized());
234 propertyCursor_++;
235 }
236
shapesHashNativeIterator237 HashNumber shapesHash() const { return shapesHash_; }
238
isInitializedNativeIterator239 bool isInitialized() const { return flags() & Flags::Initialized; }
240
241 size_t allocationSize() const;
242
243 #ifdef DEBUG
setMaybeHasIndexedPropertiesFromProtoNativeIterator244 void setMaybeHasIndexedPropertiesFromProto() {
245 maybeHasIndexedPropertiesFromProto_ = true;
246 }
maybeHasIndexedPropertiesFromProtoNativeIterator247 bool maybeHasIndexedPropertiesFromProto() const {
248 return maybeHasIndexedPropertiesFromProto_;
249 }
250 #endif
251
252 private:
flagsNativeIterator253 uint32_t flags() const { return flagsAndCount_ & FlagsMask; }
254
initialPropertyCountNativeIterator255 uint32_t initialPropertyCount() const { return flagsAndCount_ >> FlagsBits; }
256
initialFlagsAndCountNativeIterator257 static uint32_t initialFlagsAndCount(uint32_t count) {
258 // No flags are initially set.
259 MOZ_ASSERT(count < PropCountLimit);
260 return count << FlagsBits;
261 }
262
setFlagsNativeIterator263 void setFlags(uint32_t flags) {
264 MOZ_ASSERT((flags & ~FlagsMask) == 0);
265 flagsAndCount_ = (initialPropertyCount() << FlagsBits) | flags;
266 }
267
markInitializedNativeIterator268 void markInitialized() {
269 MOZ_ASSERT(flags() == 0);
270 setFlags(Flags::Initialized);
271 }
272
isUnlinkedNativeIterator273 bool isUnlinked() const { return !prev_ && !next_; }
274
275 public:
276 // Whether this is the shared empty iterator object used for iterating over
277 // null/undefined.
isEmptyIteratorSingletonNativeIterator278 bool isEmptyIteratorSingleton() const {
279 // Note: equivalent code is inlined in MacroAssembler::iteratorClose.
280 bool res = objectBeingIterated() == nullptr;
281 MOZ_ASSERT_IF(res, flags() == Flags::Initialized);
282 MOZ_ASSERT_IF(res, initialPropertyCount() == 0);
283 MOZ_ASSERT_IF(res, shapeCount() == 0);
284 MOZ_ASSERT_IF(res, isUnlinked());
285 return res;
286 }
287
isActiveNativeIterator288 bool isActive() const {
289 MOZ_ASSERT(isInitialized());
290
291 return flags() & Flags::Active;
292 }
293
markActiveNativeIterator294 void markActive() {
295 MOZ_ASSERT(isInitialized());
296 MOZ_ASSERT(!isEmptyIteratorSingleton());
297
298 flagsAndCount_ |= Flags::Active;
299 }
300
markInactiveNativeIterator301 void markInactive() {
302 MOZ_ASSERT(isInitialized());
303 MOZ_ASSERT(!isEmptyIteratorSingleton());
304
305 flagsAndCount_ &= ~Flags::Active;
306 }
307
isReusableNativeIterator308 bool isReusable() const {
309 MOZ_ASSERT(isInitialized());
310
311 // Cached NativeIterators are reusable if they're not currently active
312 // and their properties array hasn't been mutated, i.e. if only
313 // |Flags::Initialized| is set. Using |Flags::NotReusable| to test
314 // would also work, but this formulation is safer against memory
315 // corruption.
316 return flags() == Flags::Initialized;
317 }
318
markHasUnvisitedPropertyDeletionNativeIterator319 void markHasUnvisitedPropertyDeletion() {
320 MOZ_ASSERT(isInitialized());
321 MOZ_ASSERT(!isEmptyIteratorSingleton());
322
323 flagsAndCount_ |= Flags::HasUnvisitedPropertyDeletion;
324 }
325
linkNativeIterator326 void link(NativeIterator* other) {
327 // The NativeIterator sentinel doesn't have to be linked, because it's
328 // the start of the list. Anything else added should have been
329 // initialized.
330 MOZ_ASSERT(isInitialized());
331
332 // The shared iterator used for for-in with null/undefined is immutable and
333 // shouldn't be linked.
334 MOZ_ASSERT(!isEmptyIteratorSingleton());
335
336 // A NativeIterator cannot appear in the enumerator list twice.
337 MOZ_ASSERT(isUnlinked());
338
339 this->next_ = other;
340 this->prev_ = other->prev_;
341 other->prev_->next_ = this;
342 other->prev_ = this;
343 }
unlinkNativeIterator344 void unlink() {
345 MOZ_ASSERT(isInitialized());
346 MOZ_ASSERT(!isEmptyIteratorSingleton());
347
348 next_->prev_ = prev_;
349 prev_->next_ = next_;
350 next_ = nullptr;
351 prev_ = nullptr;
352 }
353
354 static NativeIterator* allocateSentinel(JSContext* cx);
355
356 void trace(JSTracer* trc);
357
offsetOfObjectBeingIteratedNativeIterator358 static constexpr size_t offsetOfObjectBeingIterated() {
359 return offsetof(NativeIterator, objectBeingIterated_);
360 }
361
offsetOfShapesEndNativeIterator362 static constexpr size_t offsetOfShapesEnd() {
363 return offsetof(NativeIterator, shapesEnd_);
364 }
365
offsetOfPropertyCursorNativeIterator366 static constexpr size_t offsetOfPropertyCursor() {
367 return offsetof(NativeIterator, propertyCursor_);
368 }
369
offsetOfPropertiesEndNativeIterator370 static constexpr size_t offsetOfPropertiesEnd() {
371 return offsetof(NativeIterator, propertiesEnd_);
372 }
373
offsetOfFlagsAndCountNativeIterator374 static constexpr size_t offsetOfFlagsAndCount() {
375 return offsetof(NativeIterator, flagsAndCount_);
376 }
377
offsetOfNextNativeIterator378 static constexpr size_t offsetOfNext() {
379 return offsetof(NativeIterator, next_);
380 }
381
offsetOfPrevNativeIterator382 static constexpr size_t offsetOfPrev() {
383 return offsetof(NativeIterator, prev_);
384 }
385 };
386
387 class PropertyIteratorObject : public NativeObject {
388 static const JSClassOps classOps_;
389
390 enum { IteratorSlot, SlotCount };
391
392 public:
393 static const JSClass class_;
394
getNativeIterator()395 NativeIterator* getNativeIterator() const {
396 return maybePtrFromReservedSlot<NativeIterator>(IteratorSlot);
397 }
initNativeIterator(js::NativeIterator * ni)398 void initNativeIterator(js::NativeIterator* ni) {
399 initReservedSlot(IteratorSlot, PrivateValue(ni));
400 }
401
402 size_t sizeOfMisc(mozilla::MallocSizeOf mallocSizeOf) const;
403
offsetOfIteratorSlot()404 static size_t offsetOfIteratorSlot() {
405 return getFixedSlotOffset(IteratorSlot);
406 }
407
408 private:
409 static void trace(JSTracer* trc, JSObject* obj);
410 static void finalize(JSFreeOp* fop, JSObject* obj);
411 };
412
413 class ArrayIteratorObject : public NativeObject {
414 public:
415 static const JSClass class_;
416 };
417
418 ArrayIteratorObject* NewArrayIteratorTemplate(JSContext* cx);
419 ArrayIteratorObject* NewArrayIterator(JSContext* cx);
420
421 class StringIteratorObject : public NativeObject {
422 public:
423 static const JSClass class_;
424 };
425
426 StringIteratorObject* NewStringIteratorTemplate(JSContext* cx);
427 StringIteratorObject* NewStringIterator(JSContext* cx);
428
429 class RegExpStringIteratorObject : public NativeObject {
430 public:
431 static const JSClass class_;
432 };
433
434 RegExpStringIteratorObject* NewRegExpStringIteratorTemplate(JSContext* cx);
435 RegExpStringIteratorObject* NewRegExpStringIterator(JSContext* cx);
436
437 [[nodiscard]] bool EnumerateProperties(JSContext* cx, HandleObject obj,
438 MutableHandleIdVector props);
439
440 PropertyIteratorObject* LookupInIteratorCache(JSContext* cx, HandleObject obj);
441
442 JSObject* ValueToIterator(JSContext* cx, HandleValue vp);
443
444 void CloseIterator(JSObject* obj);
445
446 bool IteratorCloseForException(JSContext* cx, HandleObject obj);
447
448 void UnwindIteratorForUncatchableException(JSObject* obj);
449
450 extern bool SuppressDeletedProperty(JSContext* cx, HandleObject obj, jsid id);
451
452 extern bool SuppressDeletedElement(JSContext* cx, HandleObject obj,
453 uint32_t index);
454
455 #ifdef DEBUG
456 extern void AssertDenseElementsNotIterated(NativeObject* obj);
457 #else
AssertDenseElementsNotIterated(NativeObject * obj)458 inline void AssertDenseElementsNotIterated(NativeObject* obj) {}
459 #endif
460
461 /*
462 * IteratorMore() returns the next iteration value. If no value is available,
463 * MagicValue(JS_NO_ITER_VALUE) is returned.
464 */
IteratorMore(JSObject * iterobj)465 inline Value IteratorMore(JSObject* iterobj) {
466 NativeIterator* ni =
467 iterobj->as<PropertyIteratorObject>().getNativeIterator();
468 return ni->nextIteratedValueAndAdvance();
469 }
470
471 /*
472 * Create an object of the form { value: VALUE, done: DONE }.
473 * ES 2017 draft 7.4.7.
474 */
475 extern PlainObject* CreateIterResultObject(JSContext* cx, HandleValue value,
476 bool done);
477
478 /*
479 * Global Iterator constructor.
480 * Iterator Helpers proposal 2.1.3.
481 */
482 class IteratorObject : public NativeObject {
483 public:
484 static const JSClass class_;
485 static const JSClass protoClass_;
486 };
487
488 /*
489 * Wrapper for iterators created via Iterator.from.
490 * Iterator Helpers proposal 2.1.3.3.1.1.
491 */
492 class WrapForValidIteratorObject : public NativeObject {
493 public:
494 static const JSClass class_;
495
496 enum { IteratedSlot, SlotCount };
497
498 static_assert(
499 IteratedSlot == ITERATED_SLOT,
500 "IteratedSlot must match self-hosting define for iterated object slot.");
501 };
502
503 WrapForValidIteratorObject* NewWrapForValidIterator(JSContext* cx);
504
505 /*
506 * Generator-esque object returned by Iterator Helper methods.
507 */
508 class IteratorHelperObject : public NativeObject {
509 public:
510 static const JSClass class_;
511
512 enum {
513 // The implementation (an instance of one of the generators in
514 // builtin/Iterator.js).
515 // Never null.
516 GeneratorSlot,
517
518 SlotCount,
519 };
520
521 static_assert(GeneratorSlot == ITERATOR_HELPER_GENERATOR_SLOT,
522 "GeneratorSlot must match self-hosting define for generator "
523 "object slot.");
524 };
525
526 IteratorHelperObject* NewIteratorHelper(JSContext* cx);
527
528 } /* namespace js */
529
530 #endif /* vm_Iteration_h */
531