2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-2013 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 +----------------------------------------------------------------------+
17 #ifndef incl_HPHP_ARRAY_ITERATOR_H_
18 #define incl_HPHP_ARRAY_ITERATOR_H_
20 #include "hphp/runtime/base/types.h"
21 #include "hphp/runtime/base/util/smart_ptr.h"
22 #include "hphp/runtime/base/complex_types.h"
23 #include "hphp/runtime/base/array/hphp_array.h"
24 #include "hphp/util/min_max_macros.h"
27 ///////////////////////////////////////////////////////////////////////////////
38 * An iteration normally looks like this:
40 * for (ArrayIter iter(data); iter; ++iter) {
46 * Iterator for an immutable array.
53 TypeIterator
// for objects that implement Iterator or
61 explicit ArrayIter(const ArrayData
* data
);
63 enum NoInc
{ noInc
= 0 };
64 // Special constructor used by the VM. This constructor does not increment
65 // the refcount of the specified array.
66 ArrayIter(const ArrayData
* data
, NoInc
) {
69 m_pos
= data
->iter_begin();
71 m_pos
= ArrayData::invalid_index
;
74 // This is also a special constructor used by the VM. This constructor
75 // doesn't increment the array's refcount and assumes that the array is not
77 enum NoIncNonNull
{ noIncNonNull
= 0 };
78 ArrayIter(const HphpArray
* data
, NoIncNonNull
) {
81 m_pos
= data
->getIterBegin();
83 explicit ArrayIter(CArrRef array
);
88 // Either use ArrayIter(const ArrayData*) or
89 // ArrayIter(const HphpArray*, NoIncNonNull)
90 explicit ArrayIter(const HphpArray
*);
91 template <bool incRef
>
92 void objInit(ObjectData
* obj
);
95 explicit ArrayIter(ObjectData
* obj
);
96 ArrayIter(ObjectData
* obj
, NoInc
);
97 enum TransferOwner
{ transferOwner
};
98 ArrayIter(Object
& obj
, TransferOwner
);
102 explicit operator bool() { return !end(); }
103 void operator++() { next(); }
106 if (LIKELY(hasArrayData())) {
107 return m_pos
== ArrayData::invalid_index
;
112 if (LIKELY(hasArrayData())) {
113 const ArrayData
* ad
= getArrayData();
115 assert(m_pos
!= ArrayData::invalid_index
);
116 m_pos
= ad
->iter_advance(m_pos
);
123 if (LIKELY(hasArrayData())) {
124 const ArrayData
* ad
= getArrayData();
126 assert(m_pos
!= ArrayData::invalid_index
);
127 return ad
->getKey(m_pos
);
129 return firstHelper();
132 void second(Variant
& v
) {
133 if (LIKELY(hasArrayData())) {
134 const ArrayData
* ad
= getArrayData();
136 assert(m_pos
!= ArrayData::invalid_index
);
137 v
= ad
->getValueRef(m_pos
);
144 void nvFirst(TypedValue
* out
) {
145 const ArrayData
* ad
= getArrayData();
146 assert(ad
&& m_pos
!= ArrayData::invalid_index
);
147 const_cast<ArrayData
*>(ad
)->nvGetKey(out
, m_pos
);
149 TypedValue
* nvSecond() {
150 const ArrayData
* ad
= getArrayData();
151 assert(ad
&& m_pos
!= ArrayData::invalid_index
);
152 return const_cast<ArrayData
*>(ad
)->nvGetValueRef(m_pos
);
155 bool hasArrayData() {
156 return !((intptr_t)m_data
& 1);
158 bool hasCollection() {
159 return (!hasArrayData() && getObject()->isCollection());
161 bool hasIteratorObj() {
162 return (!hasArrayData() && !getObject()->isCollection());
166 // Specialized iterator for collections. Used via JIT
170 * Fixed is used for collections that are immutable in size.
171 * Templatized Fixed functions expect the collection to implement
173 * The key is the current position of the iterator.
177 * Versionable is used for collections that are mutable and throw if
178 * an insertion or deletion is made to the collection while iterating.
179 * Templatized Versionable functions expect the collection to implement
180 * size(), getVersion() and get().
181 * The key is the current position of the iterator.
183 enum class Versionable
{};
185 * VersionableSparse is used for collections that are mutable and throw if
186 * an insertion or deletion is made to the collection while iterating.
187 * Moreover the collection elements are accessed via an iterator.
188 * Templatized VersionableSparse functions expect the collection to implement
189 * getVersion(), iter_begin(), iter_next(), iter_value() and iter_key().
191 enum class VersionableSparse
{};
194 template<class Tuplish
>
195 ArrayIter(Tuplish
* coll
, Fixed
);
196 template<class Vectorish
>
197 ArrayIter(Vectorish
* coll
, Versionable
);
198 template<class Mappish
>
199 ArrayIter(Mappish
* coll
, VersionableSparse
);
201 // iterator "next", "value", "key" functions
202 template<class Tuplish
>
203 bool iterNext(Fixed
);
204 template<class Vectorish
>
205 bool iterNext(Versionable
);
206 template<class Mappish
>
207 bool iterNext(VersionableSparse
);
209 template<class Tuplish
>
210 Variant
iterValue(Fixed
);
211 template<class Vectorish
>
212 Variant
iterValue(Versionable
);
213 template<class Mappish
>
214 Variant
iterValue(VersionableSparse
);
216 template<class Tuplish
>
217 Variant
iterKey(Fixed
);
218 template<class Vectorish
>
219 Variant
iterKey(Versionable
);
220 template<class Mappish
>
221 Variant
iterKey(VersionableSparse
);
224 const ArrayData
* getArrayData() {
225 assert(hasArrayData());
231 void setPos(ssize_t newPos
) {
234 Type
getIterType() const {
237 void setIterType(Type iterType
) {
241 ObjectData
* getObject() {
242 assert(!hasArrayData());
243 return (ObjectData
*)((intptr_t)m_obj
& ~1);
247 c_Vector
* getVector() {
248 assert(hasCollection() && getCollectionType() == Collection::VectorType
);
249 return (c_Vector
*)((intptr_t)m_obj
& ~1);
252 assert(hasCollection() && getCollectionType() == Collection::MapType
);
253 return (c_Map
*)((intptr_t)m_obj
& ~1);
255 c_StableMap
* getStableMap() {
256 assert(hasCollection() && getCollectionType() == Collection::StableMapType
);
257 return (c_StableMap
*)((intptr_t)m_obj
& ~1);
260 assert(hasCollection() && getCollectionType() == Collection::SetType
);
261 return (c_Set
*)((intptr_t)m_obj
& ~1);
264 assert(hasCollection() && getCollectionType() == Collection::PairType
);
265 return (c_Pair
*)((intptr_t)m_obj
& ~1);
267 Collection::Type
getCollectionType() {
268 ObjectData
* obj
= getObject();
269 return obj
->getCollectionType();
271 ObjectData
* getIteratorObj() {
272 assert(hasIteratorObj());
276 void setArrayData(const ArrayData
* ad
) {
277 assert((intptr_t(ad
) & 1) == 0);
280 void setObject(ObjectData
* obj
) {
281 assert((intptr_t(obj
) & 1) == 0);
282 m_obj
= (ObjectData
*)((intptr_t)obj
| 1);
287 Variant
firstHelper();
288 void secondHelper(Variant
& v
);
291 const ArrayData
* m_data
;
303 ///////////////////////////////////////////////////////////////////////////////
306 * FullPos provides the necessary functionality for supporting "foreach by
307 * reference" (also called "strong foreach"). Note that the runtime does not
308 * use FullPos directly, but instead uses two classes derived from FullPos
309 * (MutableArrayIter and MArrayIter).
311 * In the common case, a FullPos is bound to a variable (m_var) when it is
312 * initialized. m_var points to an inner cell which points to the array to
313 * iterate over. For certain use cases, a FullPos is instead bound directly to
314 * an array which m_data points to.
316 * Foreach by reference is a pain. Iteration needs to be robust in the face of
317 * two challenges: (1) the case where an element is unset during iteration, and
318 * (2) the case where user code modifies the inner cell to be a different array
319 * or a non-array value. In such cases, we should never crash and ideally when
320 * an element is unset we should be able to keep track of where we are in the
323 * FullPos works by "registering" itself with the array being iterated over.
324 * The array maintains a linked list of the FullPos's actively iterating over
325 * it. When an element is unset, the FullPos's that were pointing to that
326 * element are moved back one position before the element is unset. Note that
327 * it is possible for an iterator to point to the position before the first
328 * element (this is what the "reset" flag is for). This dance allows FullPos to
329 * keep track of where it is in the array even when elements are unset.
331 * FullPos has also has a m_container field to keep track of which array it has
332 * "registered" itself with. By comparing the array pointed to by m_var with
333 * the array pointed to by m_container, FullPos can detect if user code has
334 * modified the inner cell to be a different array or a non-array value. When
335 * this happens, the FullPos unregisters itself with the old array (pointed to
336 * by m_container) and registers itself with the new array (pointed to
337 * by m_var->m_data.parr) and resumes iteration at the position pointed to by
338 * the new array's internal cursor (ArrayData::m_pos). If m_var points to a
339 * non-array value, iteration terminates.
343 FullPos() : m_pos(0), m_container(NULL
), m_next(NULL
) {}
346 void release() { delete this; }
348 // Returns true if the iterator points past the last element (or if
349 // it points before the first element)
352 // Move the iterator forward one element
355 // Returns true if the iterator points to a valid element
358 ArrayData
* getArray() const {
359 return hasVar() ? getData() : getAd();
362 bool hasVar() const {
363 return m_var
&& !(intptr_t(m_var
) & 3LL);
366 return bool(intptr_t(m_data
) & 1LL);
368 const Variant
* getVar() const {
372 ArrayData
* getAd() const {
374 return (ArrayData
*)(intptr_t(m_data
) & ~1LL);
376 void setVar(const Variant
* val
) {
379 void setAd(ArrayData
* val
) {
380 m_data
= (ArrayData
*)(intptr_t(val
) | 1LL);
382 ArrayData
* getContainer() const {
385 void setContainer(ArrayData
* arr
) {
388 FullPos
* getNext() const {
389 return (FullPos
*)(m_resetBits
& ~1);
391 void setNext(FullPos
* fp
) {
392 assert((intptr_t(fp
) & 1) == 0);
393 m_resetBits
= intptr_t(fp
) | intptr_t(getResetFlag());
395 bool getResetFlag() const {
396 return m_resetBits
& 1;
398 void setResetFlag(bool reset
) {
399 m_resetBits
= intptr_t(getNext()) | intptr_t(reset
);
403 ArrayData
* getData() const {
405 return m_var
->is(KindOfArray
) ? m_var
->getArrayData() : nullptr;
407 ArrayData
* cowCheck();
408 void escalateCheck();
409 ArrayData
* reregister();
411 // m_var/m_data are used to keep track of the array that were are supposed
412 // to be iterating over. The low bit is used to indicate whether we are using
413 // m_var or m_data. A helper function getArray() is provided to retrieve the
414 // array that this FullPos is supposed to be iterating over.
416 const Variant
* m_var
;
420 // m_pos is an opaque value used by the array implementation to track the
421 // current position in the array.
424 // m_container keeps track of which array we're "registered" with. Normally
425 // getArray() and m_container refer to the same array. However, the two may
426 // differ in cases where user code has modified the inner cell to be a
427 // different array or non-array value.
428 ArrayData
* m_container
;
429 // m_next is used so that multiple FullPos's iterating over the same array
430 // can be chained together into a singly linked list. The low bit of m_next
431 // is used to track the state of the "reset" flag.
434 intptr_t m_resetBits
;
439 * Range which visits each entry in a list of FullPos. Removing the
440 * front element will crash but removing an already-visited element
441 * or future element will work.
445 explicit FullPosRange(FullPos
* list
) : m_fpos(list
) {}
446 FullPosRange(const FullPosRange
& other
) : m_fpos(other
.m_fpos
) {}
447 bool empty() const { return m_fpos
== 0; }
448 FullPos
* front() const { assert(!empty()); return m_fpos
; }
449 void popFront() { assert(!empty()); m_fpos
= m_fpos
->getNext(); }
455 * MutableArrayIter is used internally within the HipHop runtime in several
456 * places. Ideally, we should phase it out and use MArrayIter instead.
458 class MutableArrayIter
: public FullPos
{
460 MutableArrayIter(const Variant
* var
, Variant
* key
, Variant
& val
);
461 MutableArrayIter(ArrayData
* data
, Variant
* key
, Variant
& val
);
472 * MArrayIter is used by the VM to handle the MIter* instructions
474 class MArrayIter
: public FullPos
{
476 MArrayIter() { m_data
= NULL
; }
477 explicit MArrayIter(const RefData
* ref
);
478 explicit MArrayIter(ArrayData
* data
);
482 * It is only safe to call key() and val() if all of the following
483 * conditions are met:
484 * 1) The calls to key() and/or val() are immediately preceded by
485 * a call to advance(), prepare(), or end().
486 * 2) The iterator points to a valid position in the array.
489 ArrayData
* data
= getArray();
490 assert(data
&& data
== getContainer());
491 assert(!getResetFlag() && data
->validFullPos(*this));
492 return data
->getKey(m_pos
);
495 ArrayData
* data
= getArray();
496 assert(data
&& data
== getContainer());
497 assert(data
->getCount() <= 1 || data
->noCopyOnWrite());
498 assert(!getResetFlag());
499 assert(data
->validFullPos(*this));
500 return data
->getValueRef(m_pos
);
510 const Func
* func() const { return m_func
; }
511 void* ctx() const { return m_ctx
; }
512 StringData
* name() const { return m_name
; }
514 void setFunc(const Func
* f
) { m_func
= f
; }
515 void setCtx(ObjectData
* obj
) { m_ctx
= obj
; }
516 void setCtx(const Class
* cls
) {
517 m_ctx
= cls
? (void*)((char*)cls
+ 1) : nullptr;
519 void setName(StringData
* name
) { m_name
= name
; }
521 static uint32_t funcOff() { return offsetof(CufIter
, m_func
); }
522 static uint32_t ctxOff() { return offsetof(CufIter
, m_ctx
); }
523 static uint32_t nameOff() { return offsetof(CufIter
, m_name
); }
531 const ArrayIter
& arr() const { return m_u
.aiter
; }
532 const MArrayIter
& marr() const { return m_u
.maiter
; }
533 const CufIter
& cuf() const { return m_u
.cufiter
; }
534 ArrayIter
& arr() { return m_u
.aiter
; }
535 MArrayIter
& marr() { return m_u
.maiter
; }
536 CufIter
& cuf() { return m_u
.cufiter
; }
538 bool init(TypedValue
* c1
);
551 } __attribute__ ((aligned(16)));
553 bool interp_init_iterator(Iter
* it
, TypedValue
* c1
);
554 bool interp_init_iterator_m(Iter
* it
, TypedValue
* v1
);
555 bool interp_iter_next(Iter
* it
);
556 bool interp_iter_next_m(Iter
* it
);
558 int64_t new_iter_array(Iter
* dest
, ArrayData
* arr
, TypedValue
* val
);
559 template <bool withRef
>
560 int64_t new_iter_array_key(Iter
* dest
, ArrayData
* arr
, TypedValue
* val
,
562 int64_t new_iter_object(Iter
* dest
, ObjectData
* obj
, Class
* ctx
,
563 TypedValue
* val
, TypedValue
* key
);
564 int64_t iter_next(Iter
* dest
, TypedValue
* val
);
565 template <bool withRef
>
566 int64_t iter_next_key(Iter
* dest
, TypedValue
* val
, TypedValue
* key
);
569 int64_t new_miter_array_key(Iter
* dest
, RefData
* arr
, TypedValue
* val
,
571 int64_t new_miter_object(Iter
* dest
, RefData
* obj
, Class
* ctx
,
572 TypedValue
* val
, TypedValue
* key
);
573 int64_t new_miter_other(Iter
* dest
, RefData
* data
);
574 int64_t miter_next_key(Iter
* dest
, TypedValue
* val
, TypedValue
* key
);
576 ///////////////////////////////////////////////////////////////////////////////
579 #endif // incl_HPHP_ARRAY_ITERATOR_H_