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/. */
11 * JavaScript iterators.
14 #include "mozilla/ArrayUtils.h"
15 #include "mozilla/MemoryReporting.h"
17 #include "builtin/SelfHostingDefines.h"
18 #include "gc/Barrier.h"
24 class PropertyIteratorObject
;
26 struct NativeIterator
{
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_
= {};
32 // Internal iterator object.
33 const GCPtrObject iterObj_
= {};
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
39 GCPtrShape
* shapesEnd_
; // initialized by constructor
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
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
52 HashNumber shapesHash_
; // initialized by constructor
55 // For cacheable native iterators, whether the iterator is currently
56 // active. Not serialized by XDR.
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
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;
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;
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
79 static constexpr uint32_t HasUnvisitedPropertyDeletion
= 0x4;
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
;
90 static constexpr uint32_t FlagsBits
= 3;
91 static constexpr uint32_t FlagsMask
= (1 << FlagsBits
) - 1;
94 static constexpr uint32_t PropCountLimit
= 1 << (32 - FlagsBits
);
97 // While in compartment->enumerators, these form a doubly linked list.
98 NativeIterator
* next_
= nullptr;
99 NativeIterator
* prev_
= nullptr;
101 // Stores Flags bits in the lower bits and the initial property count above
103 uint32_t flagsAndCount_
= 0;
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;
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
120 * Initialize a NativeIterator properly allocated for |props.length()|
121 * properties and |numShapes| shapes.
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.
127 NativeIterator(JSContext
* cx
, Handle
<PropertyIteratorObject
*> propIter
,
128 Handle
<JSObject
*> objBeingIterated
, HandleIdVector props
,
129 uint32_t numShapes
, HashNumber shapesHash
, bool* hadError
);
131 /** Initialize an |ObjectRealm::enumerators| sentinel. */
134 JSObject
* objectBeingIterated() const { return objectBeingIterated_
; }
136 void changeObjectBeingIterated(JSObject
& obj
) { objectBeingIterated_
= &obj
; }
138 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
);
147 GCPtrShape
* shapesEnd() const { return shapesEnd_
; }
149 uint32_t shapeCount() const {
150 return mozilla::PointerRangeSize(shapesBegin(), shapesEnd());
153 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 "
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
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");
173 return reinterpret_cast<GCPtrLinearString
*>(shapesEnd_
);
176 GCPtrLinearString
* propertiesEnd() const { return propertiesEnd_
; }
178 GCPtrLinearString
* nextProperty() const { return propertyCursor_
; }
180 MOZ_ALWAYS_INLINE
JS::Value
nextIteratedValueAndAdvance() {
181 if (propertyCursor_
>= propertiesEnd_
) {
182 MOZ_ASSERT(propertyCursor_
== propertiesEnd_
);
183 return JS::MagicValue(JS_NO_ITER_VALUE
);
186 JSLinearString
* str
= *propertyCursor_
;
188 return JS::StringValue(str
);
191 void resetPropertyCursorForReuse() {
192 MOZ_ASSERT(isInitialized());
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?)
199 // Note: JIT code inlines |propertyCursor_| resetting when an iterator
200 // ends: see |CodeGenerator::visitIteratorEnd|.
201 propertyCursor_
= propertiesBegin();
204 bool previousPropertyWas(JS::Handle
<JSLinearString
*> str
) {
205 MOZ_ASSERT(isInitialized());
206 return propertyCursor_
> propertiesBegin() && propertyCursor_
[-1] == str
;
209 size_t numKeys() const {
210 return mozilla::PointerRangeSize(propertiesBegin(), propertiesEnd());
213 void trimLastProperty() {
214 MOZ_ASSERT(isInitialized());
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;
224 JSObject
* iterObj() const { return iterObj_
; }
225 GCPtrLinearString
* currentProperty() const {
226 MOZ_ASSERT(propertyCursor_
< propertiesEnd());
227 return propertyCursor_
;
230 NativeIterator
* next() { return next_
; }
233 MOZ_ASSERT(isInitialized());
237 HashNumber
shapesHash() const { return shapesHash_
; }
239 bool isInitialized() const { return flags() & Flags::Initialized
; }
241 size_t allocationSize() const;
244 void setMaybeHasIndexedPropertiesFromProto() {
245 maybeHasIndexedPropertiesFromProto_
= true;
247 bool maybeHasIndexedPropertiesFromProto() const {
248 return maybeHasIndexedPropertiesFromProto_
;
253 uint32_t flags() const { return flagsAndCount_
& FlagsMask
; }
255 uint32_t initialPropertyCount() const { return flagsAndCount_
>> FlagsBits
; }
257 static uint32_t initialFlagsAndCount(uint32_t count
) {
258 // No flags are initially set.
259 MOZ_ASSERT(count
< PropCountLimit
);
260 return count
<< FlagsBits
;
263 void setFlags(uint32_t flags
) {
264 MOZ_ASSERT((flags
& ~FlagsMask
) == 0);
265 flagsAndCount_
= (initialPropertyCount() << FlagsBits
) | flags
;
268 void markInitialized() {
269 MOZ_ASSERT(flags() == 0);
270 setFlags(Flags::Initialized
);
273 bool isUnlinked() const { return !prev_
&& !next_
; }
276 // Whether this is the shared empty iterator object used for iterating over
278 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());
288 bool isActive() const {
289 MOZ_ASSERT(isInitialized());
291 return flags() & Flags::Active
;
295 MOZ_ASSERT(isInitialized());
296 MOZ_ASSERT(!isEmptyIteratorSingleton());
298 flagsAndCount_
|= Flags::Active
;
301 void markInactive() {
302 MOZ_ASSERT(isInitialized());
303 MOZ_ASSERT(!isEmptyIteratorSingleton());
305 flagsAndCount_
&= ~Flags::Active
;
308 bool isReusable() const {
309 MOZ_ASSERT(isInitialized());
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
316 return flags() == Flags::Initialized
;
319 void markHasUnvisitedPropertyDeletion() {
320 MOZ_ASSERT(isInitialized());
321 MOZ_ASSERT(!isEmptyIteratorSingleton());
323 flagsAndCount_
|= Flags::HasUnvisitedPropertyDeletion
;
326 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
330 MOZ_ASSERT(isInitialized());
332 // The shared iterator used for for-in with null/undefined is immutable and
333 // shouldn't be linked.
334 MOZ_ASSERT(!isEmptyIteratorSingleton());
336 // A NativeIterator cannot appear in the enumerator list twice.
337 MOZ_ASSERT(isUnlinked());
340 this->prev_
= other
->prev_
;
341 other
->prev_
->next_
= this;
345 MOZ_ASSERT(isInitialized());
346 MOZ_ASSERT(!isEmptyIteratorSingleton());
348 next_
->prev_
= prev_
;
349 prev_
->next_
= next_
;
354 static NativeIterator
* allocateSentinel(JSContext
* cx
);
356 void trace(JSTracer
* trc
);
358 static constexpr size_t offsetOfObjectBeingIterated() {
359 return offsetof(NativeIterator
, objectBeingIterated_
);
362 static constexpr size_t offsetOfShapesEnd() {
363 return offsetof(NativeIterator
, shapesEnd_
);
366 static constexpr size_t offsetOfPropertyCursor() {
367 return offsetof(NativeIterator
, propertyCursor_
);
370 static constexpr size_t offsetOfPropertiesEnd() {
371 return offsetof(NativeIterator
, propertiesEnd_
);
374 static constexpr size_t offsetOfFlagsAndCount() {
375 return offsetof(NativeIterator
, flagsAndCount_
);
378 static constexpr size_t offsetOfNext() {
379 return offsetof(NativeIterator
, next_
);
382 static constexpr size_t offsetOfPrev() {
383 return offsetof(NativeIterator
, prev_
);
387 class PropertyIteratorObject
: public NativeObject
{
388 static const JSClassOps classOps_
;
390 enum { IteratorSlot
, SlotCount
};
393 static const JSClass class_
;
395 NativeIterator
* getNativeIterator() const {
396 return maybePtrFromReservedSlot
<NativeIterator
>(IteratorSlot
);
398 void initNativeIterator(js::NativeIterator
* ni
) {
399 initReservedSlot(IteratorSlot
, PrivateValue(ni
));
402 size_t sizeOfMisc(mozilla::MallocSizeOf mallocSizeOf
) const;
404 static size_t offsetOfIteratorSlot() {
405 return getFixedSlotOffset(IteratorSlot
);
409 static void trace(JSTracer
* trc
, JSObject
* obj
);
410 static void finalize(JSFreeOp
* fop
, JSObject
* obj
);
413 class ArrayIteratorObject
: public NativeObject
{
415 static const JSClass class_
;
418 ArrayIteratorObject
* NewArrayIteratorTemplate(JSContext
* cx
);
419 ArrayIteratorObject
* NewArrayIterator(JSContext
* cx
);
421 class StringIteratorObject
: public NativeObject
{
423 static const JSClass class_
;
426 StringIteratorObject
* NewStringIteratorTemplate(JSContext
* cx
);
427 StringIteratorObject
* NewStringIterator(JSContext
* cx
);
429 class RegExpStringIteratorObject
: public NativeObject
{
431 static const JSClass class_
;
434 RegExpStringIteratorObject
* NewRegExpStringIteratorTemplate(JSContext
* cx
);
435 RegExpStringIteratorObject
* NewRegExpStringIterator(JSContext
* cx
);
437 [[nodiscard
]] bool EnumerateProperties(JSContext
* cx
, HandleObject obj
,
438 MutableHandleIdVector props
);
440 PropertyIteratorObject
* LookupInIteratorCache(JSContext
* cx
, HandleObject obj
);
442 JSObject
* ValueToIterator(JSContext
* cx
, HandleValue vp
);
444 void CloseIterator(JSObject
* obj
);
446 bool IteratorCloseForException(JSContext
* cx
, HandleObject obj
);
448 void UnwindIteratorForUncatchableException(JSObject
* obj
);
450 extern bool SuppressDeletedProperty(JSContext
* cx
, HandleObject obj
, jsid id
);
452 extern bool SuppressDeletedElement(JSContext
* cx
, HandleObject obj
,
456 extern void AssertDenseElementsNotIterated(NativeObject
* obj
);
458 inline void AssertDenseElementsNotIterated(NativeObject
* obj
) {}
462 * IteratorMore() returns the next iteration value. If no value is available,
463 * MagicValue(JS_NO_ITER_VALUE) is returned.
465 inline Value
IteratorMore(JSObject
* iterobj
) {
467 iterobj
->as
<PropertyIteratorObject
>().getNativeIterator();
468 return ni
->nextIteratedValueAndAdvance();
472 * Create an object of the form { value: VALUE, done: DONE }.
473 * ES 2017 draft 7.4.7.
475 extern PlainObject
* CreateIterResultObject(JSContext
* cx
, HandleValue value
,
479 * Global Iterator constructor.
480 * Iterator Helpers proposal 2.1.3.
482 class IteratorObject
: public NativeObject
{
484 static const JSClass class_
;
485 static const JSClass protoClass_
;
489 * Wrapper for iterators created via Iterator.from.
490 * Iterator Helpers proposal 2.1.3.3.1.1.
492 class WrapForValidIteratorObject
: public NativeObject
{
494 static const JSClass class_
;
496 enum { IteratedSlot
, SlotCount
};
499 IteratedSlot
== ITERATED_SLOT
,
500 "IteratedSlot must match self-hosting define for iterated object slot.");
503 WrapForValidIteratorObject
* NewWrapForValidIterator(JSContext
* cx
);
506 * Generator-esque object returned by Iterator Helper methods.
508 class IteratorHelperObject
: public NativeObject
{
510 static const JSClass class_
;
513 // The implementation (an instance of one of the generators in
514 // builtin/Iterator.js).
521 static_assert(GeneratorSlot
== ITERATOR_HELPER_GENERATOR_SLOT
,
522 "GeneratorSlot must match self-hosting define for generator "
526 IteratorHelperObject
* NewIteratorHelper(JSContext
* cx
);
530 #endif /* vm_Iteration_h */