2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com) |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
22 #include "hphp/runtime/base/array-data-defs.h"
23 #include "hphp/runtime/base/mixed-array.h"
24 #include "hphp/runtime/base/tv-val.h"
25 #include "hphp/runtime/base/set-array.h"
26 #include "hphp/runtime/base/type-variant.h"
27 #include "hphp/runtime/vm/class-meth-data-ref.h"
28 #include "hphp/util/type-scan.h"
32 ///////////////////////////////////////////////////////////////////////////////
36 enum class IterTypeOp
{ NonLocal
, LocalBaseConst
, LocalBaseMutable
};
38 enum class IterNextIndex
: uint8_t {
44 // JIT-only "pointer iteration", designed for good specialized code-gen.
45 // In pointer iteration, the iterator has a pointer directly into the base.
47 // We only use this mode if all the following conditions are met:
48 // - The array is guaranteed to be unchanged during iteration
49 // - The array is a MixedArray (a dict or a darray)
50 // - The array is free of tombstones
53 // Helpers specific to bespoke array-likes.
57 // For iterator specialization, we pack all the information we need to generate
58 // specialized code in a single byte so that we can check it in one comparison.
60 // This byte should be 0 for unspecialized iterators, as created by calling the
61 // normal IterImpl constructor instead of using a specialized initializer.
62 struct IterSpecialization
{
63 enum BaseType
: uint8_t { Packed
= 0, Mixed
, Vec
, Dict
, kNumBaseTypes
};
64 enum KeyTypes
: uint8_t { ArrayKey
= 0, Int
, Str
, StaticStr
, kNumKeyTypes
};
66 // Returns a generic (unspecialized) IterSpecialization value.
67 static IterSpecialization
generic() {
68 IterSpecialization result
;
70 assertx(!result
.specialized
);
77 // `base_type` and `key_types` are 2-bit encodings of the enums above.
81 // When we JIT a specialized iterator, we set `specialized` to true,
82 // We set `output_key` for key-value iters but not for value-only iters.
83 // We set `base_const` if we know the base is const during iteration.
93 std::string
show(IterSpecialization type
);
94 std::string
show(IterSpecialization::BaseType type
);
95 std::string
show(IterSpecialization::KeyTypes type
);
98 * Iterator over an array, a collection, or an object implementing the Hack
99 * Iterator interface. This iterator is used by the JIT and its usage is
100 * mediated through the "Iter" wrapper below.
102 * By default, iterators inc-ref their base to ensure that it won't be mutated
103 * during the iteration. HHBBC can do an analysis that marks certain iterators
104 * as "local" iterators, which means that their base only changes in certain
105 * controlled ways during iteration. (Specifically: either the base does not
106 * change at all, or the current key is assigned a new value in the loop.)
108 * For local iterators, the base is kept in a frame local and passed to the
109 * iterator on each iteration. Local iterators are never used for objects,
110 * since we can't constrain writes to them in this way.
112 * The purpose of the local iter optimization is to try to keep local bases at
113 * a refcount of 1, so that they won't be COWed by the "set the current key"
114 * type of mutating operations. Apparently, this pattern is somewhat common...
117 enum NoInc
{ noInc
= 0 };
118 enum Local
{ local
= 0 };
121 * Constructors. Note that sometimes IterImpl objects are created
122 * without running their C++ constructor. (See new_iter_array.)
125 explicit IterImpl(const ArrayData
* data
);
126 IterImpl(const ArrayData
* data
, NoInc
) {
127 setArrayData
<false>(data
);
129 IterImpl(const ArrayData
* data
, Local
) {
130 setArrayData
<true>(data
);
132 explicit IterImpl(ObjectData
* obj
);
133 IterImpl(ObjectData
* obj
, NoInc
);
138 // Pass a non-NULL ad to checkInvariants iff this iterator is local.
139 // These invariants hold as long as the iterator hasn't yet reached the end.
140 bool checkInvariants(const ArrayData
* ad
= nullptr) const;
142 explicit operator bool() { return !end(); }
144 // Returns true if we've reached the end. endHelper is used for iterators
145 // over objects implementing the Iterator interface.
147 if (UNLIKELY(!hasArrayData())) return endHelper();
148 return getArrayData() == nullptr || m_pos
== m_end
;
150 bool endHelper() const;
152 // Advance the iterator's position. Assumes that end() is false. nextHelper
153 // is used for iterators over objects implementing the Iterator interface.
155 assertx(checkInvariants());
156 if (UNLIKELY(!hasArrayData())) return nextHelper();
157 m_pos
= getArrayData()->iter_advance(m_pos
);
161 bool nextLocal(const ArrayData
* ad
) {
162 assertx(checkInvariants(ad
));
163 m_pos
= ad
->iter_advance(m_pos
);
164 return m_pos
== m_end
;
167 // Return the key at the current position. firstHelper is used for Objects.
168 // This method and its variants inc-ref the key before returning it.
170 if (UNLIKELY(!hasArrayData())) return firstHelper();
171 return getArrayData()->getKey(m_pos
);
173 Variant
firstHelper();
175 // TypedValue versions of first. Used by the JIT iterator helpers.
176 // These methods do NOT inc-ref the key before returning it.
177 TypedValue
nvFirst() const {
178 return getArrayData()->nvGetKey(m_pos
);
180 TypedValue
nvFirstLocal(const ArrayData
* ad
) const {
181 assertx(getArrayData() == nullptr);
182 return ad
->nvGetKey(m_pos
);
185 // Return the value at the current position. firstHelper is used for Objects.
186 // This method and its variants inc-ref the value before returning it.
190 * Get the value at the current iterator position, without refcount ops.
192 * If called when iterating an Iterable object the secondVal() will fatal.
194 TypedValue
secondVal() const;
196 // TypedValue versions of second. Used by the JIT iterator helpers.
197 // These methods do NOT inc-ref the value before returning it.
198 TypedValue
nvSecond() const {
199 return getArrayData()->nvGetVal(m_pos
);
201 TypedValue
nvSecondLocal(const ArrayData
* ad
) const {
202 assertx(getArrayData() == nullptr);
203 return ad
->nvGetVal(m_pos
);
206 // This method returns null for local iterators, and for non-local iterators
207 // with an empty array base. It must be checked in end() for this reason.
208 bool hasArrayData() const {
209 return !((intptr_t)m_data
& objectBaseTag());
212 const ArrayData
* getArrayData() const {
213 assertx(hasArrayData());
216 ssize_t
getPos() const {
219 ssize_t
getEnd() const {
222 void setPos(ssize_t newPos
) {
226 // It's valid to call end() on a killed iter, but the iter is otherwise dead.
227 // In debug builds, this method will overwrite the iterator with garbage.
230 IterNextIndex
getHelperIndex() {
231 return m_nextHelperIdx
;
234 ObjectData
* getObject() const {
235 assertx(!hasArrayData());
236 return (ObjectData
*)((intptr_t)m_obj
& ~objectBaseTag());
239 // Used by native code and by the JIT to pack the m_typeFields components.
240 static uint32_t packTypeFields(IterNextIndex index
) {
241 return static_cast<uint32_t>(index
) << 24;
243 static uint32_t packTypeFields(
244 IterNextIndex index
, IterSpecialization spec
, uint16_t layout
) {
245 return static_cast<uint32_t>(index
) << 24 |
246 static_cast<uint32_t>(spec
.as_byte
) << 16 |
247 static_cast<uint32_t>(layout
);
250 // JIT helpers used for specializing iterators.
251 static constexpr size_t baseOffset() {
252 return offsetof(IterImpl
, m_data
);
254 static constexpr size_t baseSize() {
255 return sizeof(m_data
);
257 static constexpr size_t typeOffset() {
258 return offsetof(IterImpl
, m_typeFields
);
260 static constexpr size_t typeSize() {
261 return sizeof(m_typeFields
);
263 static constexpr size_t posOffset() {
264 return offsetof(IterImpl
, m_pos
);
266 static constexpr size_t posSize() {
267 return sizeof(m_pos
);
269 static constexpr size_t endOffset() {
270 return offsetof(IterImpl
, m_end
);
272 static constexpr size_t endSize() {
273 return sizeof(m_end
);
276 // When we specialize an iterator, we must *set* all m_type components (so as
277 // to be compatible with native helpers) but we only need to check this byte.
278 static constexpr size_t specializationOffset() {
279 return offsetof(IterImpl
, m_specialization
);
282 // ObjectData bases have this additional bit set; ArrayData bases do not.
283 static constexpr intptr_t objectBaseTag() {
288 template<IterTypeOp Type
>
289 friend int64_t new_iter_array(Iter
*, ArrayData
*, TypedValue
*);
290 template<IterTypeOp Type
>
291 friend int64_t new_iter_array_key(Iter
*, ArrayData
*, TypedValue
*,
293 template<bool HasKey
, bool Local
>
294 friend int64_t iter_next_packed_pointer(
295 Iter
*, TypedValue
*, TypedValue
*, ArrayData
*);
296 template<bool HasKey
, bool Local
>
297 friend int64_t iter_next_mixed_pointer(
298 Iter
*, TypedValue
*, TypedValue
*, ArrayData
*);
300 template <bool incRef
= true>
301 void arrInit(const ArrayData
* arr
);
303 template <bool incRef
>
304 void objInit(ObjectData
* obj
);
306 // Set all IterImpl fields for iteration over an array:
307 // - m_data is either the array, or null (for local iterators).
308 // - The type fields union is set based on the array type.
309 // - m_pos and m_end are set based on its virtual iter helpers.
310 template <bool Local
= false>
311 void setArrayData(const ArrayData
* ad
) {
312 assertx((intptr_t(ad
) & objectBaseTag()) == 0);
313 assertx(!Local
|| ad
);
314 m_data
= Local
? nullptr : ad
;
315 setArrayNext(IterNextIndex::Array
);
317 if (ad
->hasVanillaPackedLayout()) {
318 setArrayNext(IterNextIndex::ArrayPacked
);
319 } else if (ad
->hasVanillaMixedLayout()) {
320 setArrayNext(IterNextIndex::ArrayMixed
);
322 m_pos
= ad
->iter_begin();
323 m_end
= ad
->iter_end();
327 // Set all IterImpl fields for iteration over an object:
328 // - m_data is is always the object, with the lowest bit set as a flag.
329 // - We set the type fields union here.
330 void setObject(ObjectData
* obj
) {
331 assertx((intptr_t(obj
) & objectBaseTag()) == 0);
332 m_obj
= (ObjectData
*)((intptr_t)obj
| objectBaseTag());
333 m_typeFields
= packTypeFields(IterNextIndex::Object
);
334 assertx(m_nextHelperIdx
== IterNextIndex::Object
);
335 assertx(!m_specialization
.specialized
);
338 // Set the type fields of an array. These fields are packed so that we
339 // can set them with a single mov-immediate to the union.
340 void setArrayNext(IterNextIndex index
) {
341 m_typeFields
= packTypeFields(index
);
342 assertx(m_nextHelperIdx
== index
);
343 assertx(!m_specialization
.specialized
);
346 // The iterator base. Will be null for local iterators. We set the lowest
347 // bit for object iterators to distinguish them from array iterators.
349 const ArrayData
* m_data
;
352 // This field is a union so new_iter_array can set it in one instruction.
356 IterSpecialization m_specialization
;
357 IterNextIndex m_nextHelperIdx
;
359 uint32_t m_typeFields
;
361 // Current position. Beware that when m_data is null, m_pos is uninitialized.
362 // For the pointer iteration types, we use the appropriate pointers instead.
365 TypedValue
* m_packed_elm
;
366 MixedArrayElm
* m_mixed_elm
;
370 TypedValue
* m_packed_end
;
371 MixedArrayElm
* m_mixed_end
;
374 // These elements are always referenced elsewhere, either in the m_data field
375 // of this iterator or in a local. (If we weren't using pointer iteration, we
376 // would track elements by index, not by pointer, but GC would still work.)
377 TYPE_SCAN_IGNORE_FIELD(m_packed_end
);
378 TYPE_SCAN_IGNORE_FIELD(m_mixed_end
);
379 TYPE_SCAN_IGNORE_FIELD(m_packed_elm
);
380 TYPE_SCAN_IGNORE_FIELD(m_mixed_elm
);
383 ///////////////////////////////////////////////////////////////////////////////
386 * The iterator API used by the interpreter and the JIT. This API is relatively
387 * limited, because there are only two ways to interact with iterators in Hack:
388 * 1. In a "foreach" loop, using the *IterInit* / *IterNext* bytecodes.
389 * 2. As a delegated generator ("yield from").
391 * (*IterInit* here refers to {IterInit, IterInitK, LIterInit, LIterInitK}).
393 * The methods exposed here should be sufficient to implement both kinds of
394 * iterator behavior. To speed up "foreach" loops, we also provide helpers
395 * implementing *IterInit* / *IterNext* through helpers below.
397 * These helpers are faster than using the Iter class's methods directly
398 * because they do one vtable lookup on the array type and then execute the
399 * advance / bounds check / output key-value sequence based on that lookup,
400 * rather than doing a separate vtable lookup for each step.
402 * NOTE: If you initialize an iterator using the faster init helpers, you MUST
403 * use the faster next helpers for IterNext ops. That's because the helpers may
404 * make iterators that use pointer iteration, which Iter::next doesn't handle.
405 * doesn't handle. This invariant is checked in debug builds.
407 * In practice, this constraint shouldn't be a problem, because we always use
408 * the helpers to do IterNext. That's true both in the interpreter and the JIT.
410 struct alignas(16) Iter
{
414 // Returns true if the base is non-empty. Only used for non-local iterators.
415 // For local iterators, use new_iter_array / new_iter_array_key below.
416 bool init(TypedValue
* base
);
418 // Returns true if there are more elems. Only used for non-local iterators.
419 // For local iterators, use liter_next_ind / liter_next_key_ind below.
422 // Returns true if the iterator is at its end.
423 bool end() const { return m_iter
.end(); }
425 // Get the current key and value. Assumes that the iter is not at its end.
426 // These methods will inc-ref the key and value before returning it.
427 Variant
key() { return m_iter
.first(); }
428 Variant
val() { return m_iter
.second(); };
430 // It's valid to call end() on a killed iter, but the iter is otherwise dead.
431 // In debug builds, this method will overwrite the iterator with garbage.
432 void kill() { m_iter
.kill(); }
434 // Dec-refs the base, for non-local iters. Safe to call for local iters.
437 // Debug string, used when printing a frame.
438 std::string
toString() const;
441 // Used to implement the separate helper functions below. These functions
442 // peek into the Iter and directly manipulate m_iter's fields.
443 friend IterImpl
* unwrap(Iter
*);
448 // Native helpers for the interpreter + JIT used to implement *IterInit* ops.
449 // These helpers return 1 if the base has any elements and 0 otherwise.
450 // (They would return a bool, but native method calls from the JIT produce GP
451 // register outputs, so we extend the return type to an int64_t.)
453 // If these helpers return 1, they set `val` (and `key`, for key-value iters)
454 // from the first key-value pair of the base.
456 // For non-local iters, if these helpers return 0, they also dec-ref the base.
458 // For the array helpers, first provide an IterTypeOp to get an IterInit helper
459 // to call, then call it. This indirection lets us burn the appropriate helper
460 // into the JIT (where we know IterTypeOp statically). For objects, we don't
461 // need it because the type is always NonLocal.
462 using IterInitArr
= int64_t(*)(Iter
*, ArrayData
*, TypedValue
*);
463 using IterInitArrKey
= int64_t(*)(Iter
*, ArrayData
*, TypedValue
*, TypedValue
*);
465 IterInitArr
new_iter_array_helper(IterTypeOp type
);
466 IterInitArrKey
new_iter_array_key_helper(IterTypeOp type
);
468 int64_t new_iter_object(Iter
* dest
, ObjectData
* obj
, Class
* ctx
,
469 TypedValue
* val
, TypedValue
* key
);
472 // Native helpers for the interpreter + JIT used to implement *IterInit* ops.
473 // These helpers return 1 if the base has more elements and 0 otherwise.
474 // (As above, they return a logical bool which we extend to a GP register.)
476 // If these helpers return 1, they set `val` (and `key`, for key-value iters)
477 // from the next key-value pair of the base.
479 // For non-local iters, if these helpers return 0, they also dec-ref the base.
480 NEVER_INLINE
int64_t iter_next_ind(Iter
* iter
, TypedValue
* valOut
);
481 NEVER_INLINE
int64_t iter_next_key_ind(Iter
* iter
, TypedValue
* valOut
, TypedValue
* keyOut
);
482 NEVER_INLINE
int64_t liter_next_ind(Iter
*, TypedValue
*, ArrayData
*);
483 NEVER_INLINE
int64_t liter_next_key_ind(Iter
*, TypedValue
*, TypedValue
*, ArrayData
*);
485 //////////////////////////////////////////////////////////////////////