hphp/runtime/base/array-iterator.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2014 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    +----------------------------------------------------------------------+
  15 */
  16 #include "hphp/runtime/base/array-iterator.h"
  17
  18 #include <algorithm>
  19
  20 #include "folly/Likely.h"
  21
  22 #include "hphp/runtime/base/array-data.h"
  23 #include "hphp/runtime/base/mixed-array.h"
  24 #include "hphp/runtime/base/packed-array.h"
  25 #include "hphp/runtime/base/apc-local-array.h"
  26 #include "hphp/runtime/base/complex-types.h"
  27 #include "hphp/runtime/base/builtin-functions.h"
  28 #include "hphp/runtime/ext/ext_collections.h"
  29
  30 #include "hphp/runtime/base/mixed-array-defs.h"
  31 #include "hphp/runtime/base/packed-array-defs.h"
  32 #include "hphp/runtime/base/array-iterator-defs.h"
  33 #include "hphp/runtime/base/apc-local-array-defs.h"
  34
  35 namespace HPHP {
  36
  37 TRACE_SET_MOD(runtime);
  38
  39 //////////////////////////////////////////////////////////////////////
  40
  41 const StaticString
  42   s_rewind("rewind"),
  43   s_valid("valid"),
  44   s_next("next"),
  45   s_key("key"),
  46   s_current("current");
  47
  48 __thread MIterTable tl_miter_table;
  49
  50 //////////////////////////////////////////////////////////////////////
  51
  52 ArrayIter::ArrayIter(const ArrayData* data) {
  53   arrInit(data);
  54 }
  55
  56 ArrayIter::ArrayIter(const Array& array) {
  57   arrInit(array.get());
  58 }
  59
  60 ArrayIter::ArrayIter(ObjectData* obj)
  61   : m_pos(ArrayData::invalid_index) {
  62   objInit<true>(obj);
  63 }
  64
  65 ArrayIter::ArrayIter(ObjectData* obj, NoInc)
  66   : m_pos(ArrayData::invalid_index) {
  67   objInit<false>(obj);
  68 }
  69
  70 ArrayIter::ArrayIter(const Object& obj)
  71   : m_pos(ArrayData::invalid_index) {
  72   objInit<true>(obj.get());
  73 }
  74
  75 ArrayIter::ArrayIter(const Cell& c) {
  76   cellInit(c);
  77 }
  78
  79 ArrayIter::ArrayIter(const Variant& v) {
  80   cellInit(*v.asCell());
  81 }
  82
  83 ArrayIter::ArrayIter(const ArrayIter& iter) {
  84   m_data = iter.m_data;
  85   m_pos = iter.m_pos;
  86   m_version = iter.m_version;
  87   m_itype = iter.m_itype;
  88   m_nextHelperIdx = iter.m_nextHelperIdx;
  89   if (hasArrayData()) {
  90     const ArrayData* ad = getArrayData();
  91     if (ad) const_cast<ArrayData*>(ad)->incRefCount();
  92   } else {
  93     ObjectData* obj = getObject();
  94     assert(obj);
  95     obj->incRefCount();
  96   }
  97 }
  98
  99 void ArrayIter::arrInit(const ArrayData* arr) {
 100   setArrayData(arr);
 101   if (arr) {
 102     arr->incRefCount();
 103     m_pos = arr->iter_begin();
 104   } else {
 105     m_pos = ArrayData::invalid_index;
 106   }
 107 }
 108
 109 void ArrayIter::VectorInit(ArrayIter* iter, ObjectData* obj) {
 110   auto vec = static_cast<c_Vector*>(obj);
 111   iter->m_version = vec->getVersion();
 112   iter->m_pos = 0;
 113 }
 114
 115 void ArrayIter::MapInit(ArrayIter* iter, ObjectData* obj) {
 116   auto mp = static_cast<c_Map*>(obj);
 117   iter->m_version = mp->getVersion();
 118   iter->m_pos = mp->iter_begin();
 119 }
 120
 121 void ArrayIter::ImmMapInit(ArrayIter* iter, ObjectData* obj) {
 122   auto smp = static_cast<c_ImmMap*>(obj);
 123   iter->m_version = smp->getVersion();
 124   iter->m_pos = smp->iter_begin();
 125 }
 126
 127 void ArrayIter::SetInit(ArrayIter* iter, ObjectData* obj) {
 128   auto st = static_cast<c_Set*>(obj);
 129   iter->m_version = st->getVersion();
 130   iter->m_pos = st->iter_begin();
 131 }
 132
 133 void ArrayIter::PairInit(ArrayIter* iter, ObjectData* obj) {
 134   iter->m_pos = 0;
 135 }
 136
 137 void ArrayIter::ImmVectorInit(ArrayIter* iter, ObjectData* obj) {
 138   auto vec = static_cast<c_ImmVector*>(obj);
 139   iter->m_version = vec->getVersion();
 140   iter->m_pos = 0;
 141 }
 142 void ArrayIter::ImmSetInit(ArrayIter* iter, ObjectData* obj) {
 143   auto st = static_cast<c_ImmSet*>(obj);
 144   iter->m_version = st->getVersion();
 145   iter->m_pos = st->iter_begin();
 146 }
 147
 148 IterNextIndex ArrayIter::getNextHelperIdx(ObjectData* obj) {
 149   Class* cls = obj->getVMClass();
 150   if (cls == c_Vector::classof()) {
 151     return IterNextIndex::Vector;
 152   } else if (cls == c_Map::classof()) {
 153     return IterNextIndex::Map;
 154   } else if (cls == c_Set::classof()) {
 155     return IterNextIndex::Set;
 156   } else if (cls == c_ImmVector::classof()) {
 157     return IterNextIndex::ImmVector;
 158   } else if (cls == c_ImmMap::classof()) {
 159     return IterNextIndex::ImmMap;
 160   } else if (cls == c_ImmSet::classof()) {
 161     return IterNextIndex::ImmSet;
 162   } else if (cls == c_Pair::classof()) {
 163     return IterNextIndex::Pair;
 164   } else {
 165     return IterNextIndex::Object;
 166   }
 167 }
 168
 169 void ArrayIter::IteratorObjInit(ArrayIter* iter, ObjectData* obj) {
 170   assert(obj->instanceof(SystemLib::s_IteratorClass));
 171   try {
 172     obj->o_invoke_few_args(s_rewind, 0);
 173   } catch (...) {
 174     // Regardless of whether the incRef template parameter is true or
 175     // false, at this point this ArrayIter "owns" a reference to the
 176     // object and is responsible for decreffing the object when the
 177     // ArrayIter's lifetime ends. Normally ArrayIter's destructor takes
 178     // care of this, but the destructor will not get invoked if an
 179     // exception is thrown before the constructor finishes so we have
 180     // to manually handle decreffing the object here.
 181     iter->m_data = nullptr;
 182     if (debug) iter->m_itype = TypeUndefined;
 183     decRefObj(obj);
 184     throw;
 185   }
 186 }
 187
 188 const ArrayIter::InitFuncPtr
 189 ArrayIter::initFuncTable[Collection::MaxNumTypes] = {
 190   &ArrayIter::IteratorObjInit,
 191   &ArrayIter::VectorInit,
 192   &ArrayIter::MapInit,
 193   &ArrayIter::SetInit,
 194   &ArrayIter::PairInit,
 195   &ArrayIter::ImmVectorInit,
 196   &ArrayIter::ImmMapInit,
 197   &ArrayIter::ImmSetInit,
 198 };
 199
 200 template <bool incRef>
 201 void ArrayIter::objInit(ObjectData* obj) {
 202   assert(obj);
 203   setObject(obj);
 204   if (incRef) {
 205     obj->incRefCount();
 206   }
 207   initFuncTable[getCollectionType()](this, obj);
 208 }
 209
 210 void ArrayIter::cellInit(const Cell& c) {
 211   assert(cellIsPlausible(c));
 212   if (LIKELY(c.m_type == KindOfArray)) {
 213     arrInit(c.m_data.parr);
 214   } else if (LIKELY(c.m_type == KindOfObject)) {
 215     objInit<true>(c.m_data.pobj);
 216   } else {
 217     arrInit(nullptr);
 218   }
 219 }
 220
 221 void ArrayIter::destruct() {
 222   if (hasArrayData()) {
 223     const ArrayData* ad = getArrayData();
 224     if (debug) m_itype = TypeUndefined;
 225     if (ad) decRefArr(const_cast<ArrayData*>(ad));
 226     return;
 227   }
 228   ObjectData* obj = getObject();
 229   if (debug) m_itype = TypeUndefined;
 230   assert(obj);
 231   decRefObj(obj);
 232 }
 233
 234 ArrayIter& ArrayIter::operator=(const ArrayIter& iter) {
 235   reset();
 236   m_data = iter.m_data;
 237   m_pos = iter.m_pos;
 238   m_version = iter.m_version;
 239   m_itype = iter.m_itype;
 240   m_nextHelperIdx = iter.m_nextHelperIdx;
 241   if (hasArrayData()) {
 242     const ArrayData* ad = getArrayData();
 243     if (ad) const_cast<ArrayData*>(ad)->incRefCount();
 244   } else {
 245     ObjectData* obj = getObject();
 246     assert(obj);
 247     obj->incRefCount();
 248   }
 249   return *this;
 250 }
 251
 252 ArrayIter& ArrayIter::operator=(ArrayIter&& iter) {
 253   reset();
 254   m_data = iter.m_data;
 255   m_pos = iter.m_pos;
 256   m_version = iter.m_version;
 257   m_itype = iter.m_itype;
 258   m_nextHelperIdx = iter.m_nextHelperIdx;
 259   iter.m_data = nullptr;
 260   return *this;
 261 }
 262
 263 bool ArrayIter::endHelper() {
 264   switch (getCollectionType()) {
 265     case Collection::VectorType: {
 266       return m_pos >= getVector()->size();
 267     }
 268     case Collection::MapType:
 269     case Collection::ImmMapType: {
 270       return !getMap()->iter_valid(m_pos);
 271     }
 272     case Collection::SetType:
 273     case Collection::ImmSetType: {
 274       return !getSet()->iter_valid(m_pos);
 275     }
 276     case Collection::PairType: {
 277       return m_pos >= getPair()->size();
 278     }
 279     case Collection::ImmVectorType: {
 280       return m_pos >= getImmVector()->size();
 281     }
 282     case Collection::InvalidType: {
 283       ObjectData* obj = getIteratorObj();
 284       return !obj->o_invoke_few_args(s_valid, 0).toBoolean();
 285     }
 286   }
 287   not_reached();
 288 }
 289
 290 void ArrayIter::nextHelper() {
 291   switch (getCollectionType()) {
 292     case Collection::VectorType: {
 293       m_pos++;
 294       return;
 295     }
 296     case Collection::MapType:
 297     case Collection::ImmMapType: {
 298       BaseMap* mp = getMap();
 299       if (UNLIKELY(m_version != mp->getVersion())) {
 300         throw_collection_modified();
 301       }
 302       m_pos = mp->iter_next(m_pos);
 303       return;
 304     }
 305     case Collection::SetType: {
 306       BaseSet* st = getSet();
 307       if (UNLIKELY(m_version != st->getVersion())) {
 308         throw_collection_modified();
 309       }
 310       m_pos = st->iter_next(m_pos);
 311       return;
 312     }
 313     case Collection::PairType: {
 314       m_pos++;
 315       return;
 316     }
 317     case Collection::ImmVectorType: {
 318       m_pos++;
 319       return;
 320     }
 321     case Collection::ImmSetType: {
 322       c_ImmSet* st = getImmSet();
 323       assert(m_version == st->getVersion());
 324       m_pos = st->iter_next(m_pos);
 325       return;
 326     }
 327     case Collection::InvalidType: {
 328       ObjectData* obj = getIteratorObj();
 329       obj->o_invoke_few_args(s_next, 0);
 330     }
 331   }
 332 }
 333
 334 Variant ArrayIter::firstHelper() {
 335   switch (getCollectionType()) {
 336     case Collection::VectorType: {
 337       return m_pos;
 338     }
 339     case Collection::MapType:
 340     case Collection::ImmMapType: {
 341       BaseMap* mp = getMap();
 342       if (UNLIKELY(m_version != mp->getVersion())) {
 343         throw_collection_modified();
 344       }
 345       return mp->iter_key(m_pos);
 346     }
 347     case Collection::SetType: {
 348       BaseSet* st = getSet();
 349       if (UNLIKELY(m_version != st->getVersion())) {
 350         throw_collection_modified();
 351       }
 352       return st->iter_key(m_pos);
 353     }
 354     case Collection::PairType: {
 355       return m_pos;
 356     }
 357     case Collection::ImmVectorType: {
 358       return m_pos;
 359     }
 360     case Collection::ImmSetType: {
 361       c_ImmSet* st = getImmSet();
 362       if (UNLIKELY(m_version != st->getVersion())) {
 363         throw_collection_modified();
 364       }
 365       return st->iter_key(m_pos);
 366     }
 367     case Collection::InvalidType:
 368       break;
 369   }
 370   ObjectData* obj = getIteratorObj();
 371   return obj->o_invoke_few_args(s_key, 0);
 372 }
 373
 374 Variant ArrayIter::second() {
 375   if (LIKELY(hasArrayData())) {
 376     assert(m_pos != ArrayData::invalid_index);
 377     const ArrayData* ad = getArrayData();
 378     assert(ad);
 379     return ad->getValue(m_pos);
 380   }
 381   switch (getCollectionType()) {
 382     case Collection::VectorType: {
 383       auto* vec = getVector();
 384       if (UNLIKELY(m_version != vec->getVersion())) {
 385         throw_collection_modified();
 386       }
 387       return tvAsCVarRef(vec->at(m_pos));
 388     }
 389     case Collection::MapType:
 390     case Collection::ImmMapType: {
 391       BaseMap* mp = getMap();
 392       if (UNLIKELY(m_version != mp->getVersion())) {
 393         throw_collection_modified();
 394       }
 395       return tvAsCVarRef(mp->iter_value(m_pos));
 396     }
 397     case Collection::SetType: {
 398       BaseSet* st = getSet();
 399       if (UNLIKELY(m_version != st->getVersion())) {
 400         throw_collection_modified();
 401       }
 402       return tvAsCVarRef(st->iter_value(m_pos));
 403     }
 404     case Collection::PairType: {
 405       return tvAsCVarRef(getPair()->at(m_pos));
 406     }
 407     case Collection::ImmVectorType: {
 408       c_ImmVector* fvec = getImmVector();
 409       if (UNLIKELY(m_version != fvec->getVersion())) {
 410         throw_collection_modified();
 411       }
 412       return tvAsCVarRef(fvec->at(m_pos));
 413     }
 414     case Collection::ImmSetType: {
 415       c_ImmSet* st = getImmSet();
 416       assert(m_version == st->getVersion());
 417       return tvAsCVarRef(st->iter_value(m_pos));
 418     }
 419     case Collection::InvalidType:
 420       break;
 421   }
 422
 423   ObjectData* obj = getIteratorObj();
 424   return obj->o_invoke_few_args(s_current, 0);
 425 }
 426
 427 const Variant& ArrayIter::secondRef() {
 428   if (!hasArrayData()) {
 429     throw FatalErrorException("taking reference on iterator objects");
 430   }
 431   assert(hasArrayData());
 432   assert(m_pos != ArrayData::invalid_index);
 433   const ArrayData* ad = getArrayData();
 434   assert(ad);
 435   return ad->getValueRef(m_pos);
 436 }
 437
 438 const Variant& ArrayIter::secondRefPlus() {
 439   if (LIKELY(hasArrayData())) {
 440     assert(m_pos != ArrayData::invalid_index);
 441     const ArrayData* ad = getArrayData();
 442     assert(ad);
 443     return ad->getValueRef(m_pos);
 444   }
 445   switch (getCollectionType()) {
 446     case Collection::VectorType: {
 447       auto* vec = getVector();
 448       if (UNLIKELY(m_version != vec->getVersion())) {
 449         throw_collection_modified();
 450       }
 451       return tvAsCVarRef(vec->at(m_pos));
 452     }
 453     case Collection::MapType:
 454     case Collection::ImmMapType: {
 455       BaseMap* mp = getMap();
 456       if (UNLIKELY(m_version != mp->getVersion())) {
 457         throw_collection_modified();
 458       }
 459       return tvAsCVarRef(mp->iter_value(m_pos));
 460     }
 461     case Collection::SetType: {
 462       BaseSet* st = getSet();
 463       if (UNLIKELY(m_version != st->getVersion())) {
 464         throw_collection_modified();
 465       }
 466       return tvAsCVarRef(st->iter_value(m_pos));
 467     }
 468     case Collection::PairType: {
 469       return tvAsCVarRef(getPair()->at(m_pos));
 470     }
 471     case Collection::ImmVectorType: {
 472       c_ImmVector* fvec = getImmVector();
 473       if (UNLIKELY(m_version != fvec->getVersion())) {
 474         throw_collection_modified();
 475       }
 476       return tvAsCVarRef(fvec->at(m_pos));
 477     }
 478     case Collection::ImmSetType: {
 479       c_ImmSet* st = getImmSet();
 480       assert(m_version == st->getVersion());
 481       return tvAsCVarRef(st->iter_value(m_pos));
 482     }
 483     case Collection::InvalidType: {
 484       throw_param_is_not_container();
 485     }
 486   }
 487   not_reached();
 488 }
 489
 490 //
 491 // Collection iterator specialized functions.
 492 //
 493
 494 template<class Tuplish>
 495 ArrayIter::ArrayIter(Tuplish* coll, Fixed)
 496     : m_pos(0), m_itype(ArrayIter::TypeIterator) {
 497   assert(coll);
 498   setObject(coll);
 499   // TODO Task #4204598: In theory, we might be able to squeeze out a win
 500   // here by not checking the version for immutable collections, but we'd
 501   // to make sure all iteration implementations are consistent about this.
 502   m_version = coll->getVersion();
 503 }
 504
 505 template<class Vectorish>
 506 ArrayIter::ArrayIter(Vectorish* coll, Versionable)
 507     : m_pos(0), m_itype(ArrayIter::TypeIterator) {
 508   assert(coll && coll->size() > 0);
 509   setObject(coll);
 510   m_version = coll->getVersion();
 511 }
 512
 513 template<class Mappish>
 514 ArrayIter::ArrayIter(Mappish* coll, VersionableSparse)
 515     : m_itype(ArrayIter::TypeIterator) {
 516   assert(coll && coll->size() > 0);
 517   setObject(coll);
 518   m_version = coll->getVersion();
 519   m_pos = coll->iter_begin();
 520 }
 521
 522 template<class Tuplish>
 523 ALWAYS_INLINE
 524 bool ArrayIter::iterNext(Fixed) {
 525   return ++m_pos < static_cast<Tuplish*>(getObject())->size();
 526 }
 527
 528 template<class Vectorish>
 529 ALWAYS_INLINE
 530 bool ArrayIter::iterNext(Versionable) {
 531   Vectorish* vec = static_cast<Vectorish*>(getObject());
 532   if (UNLIKELY(m_version != vec->getVersion())) {
 533     throw_collection_modified();
 534   }
 535   return ++m_pos < vec->size();
 536 }
 537
 538 template<class Mappish>
 539 ALWAYS_INLINE
 540 bool ArrayIter::iterNext(VersionableSparse) {
 541   Mappish* coll = static_cast<Mappish*>(getObject());
 542   if (UNLIKELY(m_version != coll->getVersion())) {
 543     throw_collection_modified();
 544   }
 545   m_pos = coll->iter_next(m_pos);
 546   return coll->iter_valid(m_pos);
 547 }
 548
 549 template<class Tuplish>
 550 ALWAYS_INLINE
 551 Variant ArrayIter::iterKey(Fixed) {
 552   return m_pos;
 553 }
 554
 555 template<class Vectorish>
 556 ALWAYS_INLINE
 557 Variant ArrayIter::iterKey(Versionable) {
 558   return m_pos;
 559 }
 560
 561 template<class Mappish>
 562 ALWAYS_INLINE
 563 Variant ArrayIter::iterKey(VersionableSparse) {
 564   return static_cast<Mappish*>(getObject())->iter_key(m_pos);
 565 }
 566
 567 template<class Tuplish>
 568 ALWAYS_INLINE
 569 Variant ArrayIter::iterValue(Fixed) {
 570   return tvAsCVarRef(static_cast<Tuplish*>(getObject())->get(m_pos));
 571 }
 572
 573 template<class Vectorish>
 574 ALWAYS_INLINE
 575 Variant ArrayIter::iterValue(Versionable) {
 576   return tvAsCVarRef(static_cast<Vectorish*>(getObject())->get(m_pos));
 577 }
 578
 579 template<class Mappish>
 580 ALWAYS_INLINE
 581 Variant ArrayIter::iterValue(VersionableSparse) {
 582   return tvAsCVarRef(static_cast<Mappish*>(getObject())->iter_value(m_pos));
 583 }
 584
 585 RefData* ArrayIter::zSecond() {
 586   auto tv = nvSecond();
 587   if (tv->m_type != KindOfRef) {
 588     // FIXME: this is not allowed.
 589     tvBox(const_cast<TypedValue*>(tv));
 590   }
 591   return tv->m_data.pref;
 592 }
 593
 594 //////////////////////////////////////////////////////////////////////
 595
 596 namespace {
 597
 598 // Handle the cases where we didn't have enough preallocated Ents in
 599 // tl_miter_table, and we need to allocate from `extras'.
 600 NEVER_INLINE
 601 MIterTable::Ent* find_empty_strong_iter_slower() {
 602   return tl_miter_table.extras.find_unpopulated();
 603 }
 604
 605 // Handle finding an empty strong iterator slot when the first slot
 606 // was already in use.
 607 NEVER_INLINE
 608 MIterTable::Ent* find_empty_strong_iter_slow() {
 609 #define X(i) \
 610   if (LIKELY(!tl_miter_table.ents[i].array)) return &tl_miter_table.ents[i];
 611 X(1);
 612 X(2);
 613 X(3);
 614 X(4);
 615 X(5);
 616 X(6);
 617   static_assert(tl_miter_table.ents.size() == 7, "");
 618 #undef X
 619   return find_empty_strong_iter_slower();
 620 }
 621
 622 // Find a strong iterator slot that is empty.  Almost always the first
 623 // one will be empty, so that path is inlined---everything else
 624 // delegates to slow.
 625 ALWAYS_INLINE
 626 MIterTable::Ent* find_empty_strong_iter() {
 627   if (LIKELY(!tl_miter_table.ents[0].array)) {
 628     return &tl_miter_table.ents[0];
 629   }
 630   return find_empty_strong_iter_slow();
 631 }
 632
 633 void newMArrayIter(MArrayIter* marr, ArrayData* ad) {
 634   assert(!marr->getContainer());
 635   auto const slot = find_empty_strong_iter();
 636   assert(!slot->array);
 637   slot->iter = marr;
 638   slot->array = ad;
 639   marr->setContainer(ad);
 640   marr->m_pos = ad->getPosition();
 641   assert(strong_iterators_exist());
 642 }
 643
 644 template<class Cond>
 645 void free_strong_iterator_impl(Cond cond) {
 646   assert(strong_iterators_exist());
 647
 648   // We need to maintain the invariant that if there are any strong
 649   // iterators bound to arrays, one of the bindings is in slot zero.
 650   // This pvalid will point to something we can move into the first
 651   // slot if alreadyValid is false.  If when we're done alreadyValid
 652   // is false, and pvalid is also nullptr, it means this function
 653   // freed the last strong iterator.
 654   MIterTable::Ent* pvalid = nullptr;
 655   bool alreadyValid = true;  // because strong_iterators_exist()
 656
 657   auto rm = [&] (MIterTable::Ent& ent) {
 658     if (cond(ent)) {
 659       ent.iter->setContainer(nullptr);
 660       ent.array = nullptr;
 661       ent.iter = nullptr;
 662     } else if (!alreadyValid && ent.array) {
 663       pvalid = &ent;
 664     }
 665   };
 666
 667   if (cond(tl_miter_table.ents[0])) {
 668     tl_miter_table.ents[0].iter->setContainer(nullptr);
 669     tl_miter_table.ents[0].array = nullptr;
 670     tl_miter_table.ents[0].iter = nullptr;
 671     alreadyValid = false;
 672   }
 673   rm(tl_miter_table.ents[1]);
 674   rm(tl_miter_table.ents[2]);
 675   rm(tl_miter_table.ents[3]);
 676   rm(tl_miter_table.ents[4]);
 677   rm(tl_miter_table.ents[5]);
 678   rm(tl_miter_table.ents[6]);
 679   static_assert(tl_miter_table.ents.size() == 7, "");
 680
 681   if (UNLIKELY(pvalid != nullptr)) {
 682     std::swap(*pvalid, tl_miter_table.ents[0]);
 683     alreadyValid = true;
 684   }
 685   if (LIKELY(tl_miter_table.extras.empty())) return;
 686
 687   tl_miter_table.extras.release_if([&] (const MIterTable::Ent& e) {
 688     if (cond(e)) {
 689       e.iter->setContainer(nullptr);
 690       return true;
 691     }
 692     return false;
 693   });
 694
 695   // If we didn't manage to keep something in the first non-extra
 696   // slot, scan extras again to swap something over.
 697   if (LIKELY(alreadyValid)) return;
 698   if (!tl_miter_table.extras.empty()) {
 699     tl_miter_table.extras.visit_to_remove(
 700       [&] (const MIterTable::Ent& ent) {
 701         tl_miter_table.ents[0] = ent;
 702       }
 703     );
 704   }
 705 }
 706
 707 void freeMArrayIter(MArrayIter* marr) {
 708   assert(strong_iterators_exist());
 709   free_strong_iterator_impl(
 710     [marr] (const MIterTable::Ent& e) {
 711       return e.iter == marr;
 712     }
 713   );
 714 }
 715
 716 }
 717
 718 void free_strong_iterators(ArrayData* ad) {
 719   free_strong_iterator_impl([ad] (const MIterTable::Ent& e) {
 720     return e.array == ad;
 721   });
 722 }
 723
 724 /*
 725  * This function returns its first argument so that in some cases we
 726  * can do tails calls (or maybe avoid spills).
 727  *
 728  * Note that in some cases reusing the return value can be (very
 729  * slightly) worse.  The compiler won't know that the return value is
 730  * going to be the same as the argument, so if it didn't already have
 731  * to spill to make the call, or it can't tail call for some other
 732  * reason, you can cause an extra move after the return.
 733  */
 734 ArrayData* move_strong_iterators(ArrayData* dst, ArrayData* src) {
 735   for_each_strong_iterator([&] (MIterTable::Ent& ent) {
 736     if (ent.array == src) {
 737       ent.array = dst;
 738       ent.iter->setContainer(dst);
 739     }
 740   });
 741   return dst;
 742 }
 743
 744 //////////////////////////////////////////////////////////////////////
 745
 746 MArrayIter::MArrayIter(RefData* ref)
 747   : m_pos(0)
 748   , m_container(nullptr)
 749   , m_resetFlag(false)
 750 {
 751   ref->incRefCount();
 752   setRef(ref);
 753   assert(hasRef());
 754   escalateCheck();
 755   auto const data = cowCheck();
 756   if (!data) return;
 757   data->reset();
 758   newMArrayIter(this, data);
 759   setResetFlag(true);
 760   data->next();
 761   assert(getContainer() == data);
 762 }
 763
 764 MArrayIter::MArrayIter(ArrayData* data)
 765   : m_ref(nullptr)
 766   , m_pos(0)
 767   , m_container(nullptr)
 768   , m_resetFlag(false)
 769 {
 770   if (!data) return;
 771   assert(!data->isStatic());
 772   setAd(data);
 773   escalateCheck();
 774   data = cowCheck();
 775   data->reset();
 776   newMArrayIter(this, data);
 777   setResetFlag(true);
 778   data->next();
 779   assert(getContainer() == data);
 780 }
 781
 782 MArrayIter::~MArrayIter() {
 783   auto const container = getContainer();
 784   if (container) {
 785     freeMArrayIter(this);
 786     assert(getContainer() == nullptr);
 787   }
 788   if (hasRef()) {
 789     decRefRef(getRef());
 790   } else if (hasAd()) {
 791     decRefArr(getAd());
 792   }
 793 }
 794
 795 bool MArrayIter::end() const {
 796   return !const_cast<MArrayIter*>(this)->prepare();
 797 }
 798
 799 bool MArrayIter::advance() {
 800   ArrayData* data = getArray();
 801   ArrayData* container = getContainer();
 802   if (!data) {
 803     if (container) {
 804       freeMArrayIter(this);
 805     }
 806     setResetFlag(false);
 807     return false;
 808   }
 809   if (container == data) {
 810     return cowCheck()->advanceMArrayIter(*this);
 811   }
 812   data = reregister();
 813   assert(data && data == getContainer());
 814   assert(!getResetFlag());
 815   if (!data->validMArrayIter(*this)) return false;
 816   // To conform to PHP behavior, we need to set the internal
 817   // cursor to point to the next element.
 818   data->next();
 819   return true;
 820 }
 821
 822 bool MArrayIter::prepare() {
 823   ArrayData* data = getArray();
 824   ArrayData* container = getContainer();
 825   if (!data) {
 826     if (container) {
 827       freeMArrayIter(this);
 828     }
 829     setResetFlag(false);
 830     return false;
 831   }
 832   if (container != data) {
 833     data = reregister();
 834   }
 835   return data->validMArrayIter(*this);
 836 }
 837
 838 void MArrayIter::escalateCheck() {
 839   if (hasRef()) {
 840     auto const data = getData();
 841     if (!data) return;
 842     auto const esc = data->escalate();
 843     if (data != esc) {
 844       cellSet(make_tv<KindOfArray>(esc), *getRef()->tv());
 845     }
 846     return;
 847   }
 848
 849   assert(hasAd());
 850   auto const data = getAd();
 851   auto const esc = data->escalate();
 852   if (data != esc) {
 853     esc->incRefCount();
 854     decRefArr(data);
 855     setAd(esc);
 856   }
 857 }
 858
 859 ArrayData* MArrayIter::cowCheck() {
 860   if (hasRef()) {
 861     auto data = getData();
 862     if (!data) return nullptr;
 863     if (data->hasMultipleRefs() && !data->noCopyOnWrite()) {
 864       data = data->copyWithStrongIterators();
 865       cellSet(make_tv<KindOfArray>(data), *getRef()->tv());
 866     }
 867     return data;
 868   }
 869
 870   assert(hasAd());
 871   auto const data = getAd();
 872   if (data->hasMultipleRefs() && !data->noCopyOnWrite()) {
 873     ArrayData* copied = data->copyWithStrongIterators();
 874     copied->incRefCount();
 875     decRefArr(data);
 876     setAd(copied);
 877     return copied;
 878   }
 879   return data;
 880 }
 881
 882 ArrayData* MArrayIter::reregister() {
 883   ArrayData* container = getContainer();
 884   assert(getArray() != nullptr && container != getArray());
 885   if (container != nullptr) {
 886     freeMArrayIter(this);
 887   }
 888   setResetFlag(false);
 889   assert(getContainer() == nullptr);
 890   escalateCheck();
 891   ArrayData* data = cowCheck();
 892   newMArrayIter(this, data);
 893   return data;
 894 }
 895
 896 //////////////////////////////////////////////////////////////////////
 897
 898 CufIter::~CufIter() {
 899   if (m_ctx && !(uintptr_t(m_ctx) & 1)) {
 900     decRefObj((ObjectData*)m_ctx);
 901   }
 902   if (m_name) decRefStr(m_name);
 903 }
 904
 905 bool Iter::init(TypedValue* c1) {
 906   assert(c1->m_type != KindOfRef);
 907   bool hasElems = true;
 908   if (c1->m_type == KindOfArray) {
 909     if (!c1->m_data.parr->empty()) {
 910       (void) new (&arr()) ArrayIter(c1->m_data.parr);
 911       arr().setIterType(ArrayIter::TypeArray);
 912     } else {
 913       hasElems = false;
 914     }
 915   } else if (c1->m_type == KindOfObject) {
 916     bool isIterator;
 917     if (c1->m_data.pobj->isCollection()) {
 918       isIterator = true;
 919       (void) new (&arr()) ArrayIter(c1->m_data.pobj);
 920     } else {
 921       Object obj = c1->m_data.pobj->iterableObject(isIterator);
 922       if (isIterator) {
 923         (void) new (&arr()) ArrayIter(obj.detach(), ArrayIter::noInc);
 924       } else {
 925         Class* ctx = arGetContextClass(g_context->getFP());
 926         auto ctxStr = ctx ? ctx->nameStr() : StrNR();
 927         Array iterArray(obj->o_toIterArray(ctxStr));
 928         ArrayData* ad = iterArray.get();
 929         (void) new (&arr()) ArrayIter(ad);
 930       }
 931     }
 932     try {
 933       if (arr().end()) {
 934         // Iterator was empty; call the destructor on the iterator we
 935         // just constructed and branch to done case
 936         arr().~ArrayIter();
 937         hasElems = false;
 938       } else {
 939         arr().setIterType(
 940           isIterator ? ArrayIter::TypeIterator : ArrayIter::TypeArray);
 941       }
 942     } catch (...) {
 943       arr().~ArrayIter();
 944       throw;
 945     }
 946   } else {
 947     raise_warning("Invalid argument supplied for foreach()");
 948     hasElems = false;
 949   }
 950   return hasElems;
 951 }
 952
 953 bool Iter::next() {
 954   assert(arr().getIterType() == ArrayIter::TypeArray ||
 955          arr().getIterType() == ArrayIter::TypeIterator);
 956   // The emitter should never generate bytecode where the iterator
 957   // is at the end before IterNext is executed. However, even if
 958   // the iterator is at the end, it is safe to call next().
 959   ArrayIter* ai = &arr();
 960   ai->next();
 961   if (ai->end()) {
 962     // If after advancing the iterator we have reached the end, free
 963     // the iterator and fall through to the next instruction.
 964     // The ArrayIter destructor will decRef the array.
 965     ai->~ArrayIter();
 966     return false;
 967   }
 968   // If after advancing the iterator we have not reached the end,
 969   // jump to the location specified by the second immediate argument.
 970   return true;
 971 }
 972
 973 void Iter::free() {
 974   assert(arr().getIterType() == ArrayIter::TypeArray ||
 975          arr().getIterType() == ArrayIter::TypeIterator);
 976   arr().~ArrayIter();
 977 }
 978
 979 void Iter::mfree() {
 980   marr().~MArrayIter();
 981 }
 982
 983 void Iter::cfree() {
 984   cuf().~CufIter();
 985 }
 986
 987 /**
 988  * Helper functions for collection style iterators.
 989  * Iterators over collections are never by-ref so there is no reason to
 990  * unbox any value.
 991  * Templates are instantiated over the collection class and the iterator
 992  * style. See the definition of Fixed, Versionable and VersionableSparse
 993  * in the header for details.
 994  * IterInit and IterNext can be called directly from the JIT for specialized
 995  * iterators.
 996  */
 997 template<class Coll, class Style>
 998 static void iterValue(ArrayIter* iter, TypedValue* out) {
 999   Variant val = iter->iterValue<Coll>(Style());
1000   assert(val.getRawType() != KindOfRef);
1001   cellDup(*val.asTypedValue(), *out);
1002 }
1003
1004 template<class Coll, class Style>
1005 static void iterKey(ArrayIter* iter, TypedValue* out) {
1006   Variant key = iter->iterKey<Coll>(Style());
1007   cellDup(*key.asTypedValue(), *out);
1008 }
1009
1010 template<class Coll, class Style>
1011 static int64_t iterInit(Iter* dest, Coll* coll,
1012                         TypedValue* valOut, TypedValue* keyOut) {
1013   int64_t size = coll->size();
1014   if (UNLIKELY(size == 0)) {
1015     decRefObj(coll);
1016     return 0LL;
1017   }
1018   (void) new (&dest->arr()) ArrayIter(coll, Style());
1019
1020   DataType vType = valOut->m_type;
1021   assert(vType != KindOfRef);
1022   uint64_t vDatum = valOut->m_data.num;
1023   iterValue<Coll, Style>(&dest->arr(), valOut);
1024   tvRefcountedDecRefHelper(vType, vDatum);
1025
1026   if (keyOut) {
1027     DataType kType = keyOut->m_type;
1028     uint64_t kDatum = keyOut->m_data.num;
1029     iterKey<Coll, Style>(&dest->arr(), keyOut);
1030     tvRefcountedDecRefHelper(kType, kDatum);
1031   }
1032   return 1LL;
1033 }
1034
1035 template<class Coll, class Style>
1036 static
1037 int64_t iterNext(ArrayIter* iter, TypedValue* valOut, TypedValue* keyOut) {
1038   if (!iter->iterNext<Coll>(Style())) {
1039     iter->~ArrayIter();
1040     return 0LL;
1041   }
1042
1043   DataType vType = valOut->m_type;
1044   assert(vType != KindOfRef);
1045   uint64_t vDatum = valOut->m_data.num;
1046   iterValue<Coll, Style>(iter, valOut);
1047   tvRefcountedDecRefHelper(vType, vDatum);
1048
1049   if (keyOut) {
1050     DataType kType = keyOut->m_type;
1051     uint64_t kDatum = keyOut->m_data.num;
1052     iterKey<Coll, Style>(iter, keyOut);
1053     tvRefcountedDecRefHelper(kType, kDatum);
1054   }
1055   return 1LL;
1056 }
1057
1058 /*
1059  * iter_value_cell* will store a copy of the current value at the address
1060  * given by 'out'. iter_value_cell* will increment the refcount of the current
1061  * value if appropriate.
1062  */
1063
1064 template <bool typeArray, bool withRef>
1065 static inline void iter_value_cell_local_impl(Iter* iter, TypedValue* out) {
1066   DataType oldType = out->m_type;
1067   assert(withRef || oldType != KindOfRef);
1068   uint64_t oldDatum = out->m_data.num;
1069   TRACE(2, "%s: typeArray: %s, I %p, out %p\n",
1070            __func__, typeArray ? "true" : "false", iter, out);
1071   assert((typeArray && iter->arr().getIterType() == ArrayIter::TypeArray) ||
1072          (!typeArray && iter->arr().getIterType() == ArrayIter::TypeIterator));
1073   ArrayIter& arrIter = iter->arr();
1074   if (typeArray) {
1075     auto const cur = arrIter.nvSecond();
1076     if (cur->m_type == KindOfRef) {
1077       if (!withRef || !cur->m_data.pref->isReferenced()) {
1078         cellDup(*(cur->m_data.pref->tv()), *out);
1079       } else {
1080         refDup(*cur, *out);
1081       }
1082     } else {
1083       cellDup(*cur, *out);
1084     }
1085   } else {
1086     Variant val = arrIter.second();
1087     assert(val.getRawType() != KindOfRef);
1088     cellDup(*val.asTypedValue(), *out);
1089   }
1090   tvRefcountedDecRefHelper(oldType, oldDatum);
1091 }
1092
1093 template <bool typeArray, bool withRef>
1094 static inline void iter_key_cell_local_impl(Iter* iter, TypedValue* out) {
1095   DataType oldType = out->m_type;
1096   assert(withRef || oldType != KindOfRef);
1097   uint64_t oldDatum = out->m_data.num;
1098   TRACE(2, "%s: I %p, out %p\n", __func__, iter, out);
1099   assert((typeArray && iter->arr().getIterType() == ArrayIter::TypeArray) ||
1100          (!typeArray && iter->arr().getIterType() == ArrayIter::TypeIterator));
1101   ArrayIter& arr = iter->arr();
1102   if (typeArray) {
1103     arr.nvFirst(out);
1104   } else {
1105     Variant key = arr.first();
1106     cellDup(*key.asTypedValue(), *out);
1107   }
1108   tvRefcountedDecRefHelper(oldType, oldDatum);
1109 }
1110
1111 static NEVER_INLINE
1112 int64_t iter_next_free_packed(Iter* iter, ArrayData* arr) {
1113   assert(arr->hasExactlyOneRef());
1114   assert(arr->isPacked());
1115   PackedArray::Release(arr);
1116   if (debug) {
1117     iter->arr().setIterType(ArrayIter::TypeUndefined);
1118   }
1119   return 0;
1120 }
1121
1122 static NEVER_INLINE
1123 int64_t iter_next_free_mixed(Iter* iter, ArrayData* arr) {
1124   assert(arr->isMixed());
1125   assert(arr->hasExactlyOneRef());
1126   MixedArray::Release(arr);
1127   if (debug) {
1128     iter->arr().setIterType(ArrayIter::TypeUndefined);
1129   }
1130   return 0;
1131 }
1132
1133 NEVER_INLINE
1134 static int64_t iter_next_free_apc(Iter* iter, APCLocalArray* arr) {
1135   assert(arr->hasExactlyOneRef());
1136   APCLocalArray::Release(arr->asArrayData());
1137   if (debug) {
1138     iter->arr().setIterType(ArrayIter::TypeUndefined);
1139   }
1140   return 0;
1141 }
1142
1143 /*
1144  * new_iter_array creates an iterator for the specified array iff the
1145  * array is not empty.  If new_iter_array creates an iterator, it does
1146  * not increment the refcount of the specified array.  If
1147  * new_iter_array does not create an iterator, it decRefs the array.
1148  */
1149 template <bool withRef>
1150 NEVER_INLINE
1151 int64_t new_iter_array_cold(Iter* dest, ArrayData* arr, TypedValue* valOut,
1152                             TypedValue* keyOut) {
1153   TRACE(2, "%s: I %p, arr %p\n", __func__, dest, arr);
1154   if (!withRef) {
1155     valOut = tvToCell(valOut);
1156     if (keyOut) keyOut = tvToCell(keyOut);
1157   }
1158   if (!arr->empty()) {
1159     // We are transferring ownership of the array to the iterator, therefore
1160     // we do not need to adjust the refcount.
1161     (void) new (&dest->arr()) ArrayIter(arr, ArrayIter::noInc);
1162     dest->arr().setIterType(ArrayIter::TypeArray);
1163     iter_value_cell_local_impl<true, withRef>(dest, valOut);
1164     if (keyOut) {
1165       iter_key_cell_local_impl<true, withRef>(dest, keyOut);
1166     }
1167     return 1LL;
1168   }
1169   // We did not transfer ownership of the array to an iterator, so we need
1170   // to decRef the array.
1171   decRefArr(arr);
1172   return 0LL;
1173 }
1174
1175 int64_t new_iter_array(Iter* dest, ArrayData* ad, TypedValue* valOut) {
1176   TRACE(2, "%s: I %p, ad %p\n", __func__, dest, ad);
1177   if (UNLIKELY(ad->getSize() == 0)) {
1178     if (UNLIKELY(ad->hasExactlyOneRef())) {
1179       if (ad->isPacked()) return iter_next_free_packed(dest, ad);
1180       if (ad->isMixed()) return iter_next_free_mixed(dest, ad);
1181     }
1182     ad->decRefCount();
1183     return 0;
1184   }
1185   if (UNLIKELY(IS_REFCOUNTED_TYPE(valOut->m_type))) {
1186     return new_iter_array_cold<false>(dest, ad, valOut, nullptr);
1187   }
1188
1189   // We are transferring ownership of the array to the iterator, therefore
1190   // we do not need to adjust the refcount.
1191   auto& aiter = dest->arr();
1192   aiter.m_data = ad;
1193   auto const itypeU32 = static_cast<uint32_t>(ArrayIter::TypeArray);
1194
1195   if (LIKELY(ad->isPacked())) {
1196     aiter.m_pos = 0;
1197     aiter.m_itypeAndNextHelperIdx =
1198       static_cast<uint32_t>(IterNextIndex::ArrayPacked) << 16 | itypeU32;
1199     assert(aiter.m_itype == ArrayIter::TypeArray);
1200     assert(aiter.m_nextHelperIdx == IterNextIndex::ArrayPacked);;
1201     cellDup(*tvToCell(packedData(ad)), *valOut);
1202     return 1;
1203   }
1204
1205   if (LIKELY(ad->isMixed())) {
1206     auto const mixed = MixedArray::asMixed(ad);
1207     aiter.m_pos = mixed->getIterBegin();
1208     aiter.m_itypeAndNextHelperIdx =
1209       static_cast<uint32_t>(IterNextIndex::ArrayMixed) << 16 | itypeU32;
1210     assert(aiter.m_itype == ArrayIter::TypeArray);
1211     assert(aiter.m_nextHelperIdx == IterNextIndex::ArrayMixed);
1212     mixed->getArrayElm(aiter.m_pos, valOut);
1213     return 1;
1214   }
1215
1216   return new_iter_array_cold<false>(dest, ad, valOut, nullptr);
1217 }
1218
1219 template<bool WithRef>
1220 int64_t new_iter_array_key(Iter*       dest,
1221                            ArrayData*  ad,
1222                            TypedValue* valOut,
1223                            TypedValue* keyOut) {
1224   if (UNLIKELY(ad->getSize() == 0)) {
1225     if (UNLIKELY(ad->hasExactlyOneRef())) {
1226       if (ad->isPacked()) return iter_next_free_packed(dest, ad);
1227       if (ad->isMixed()) return iter_next_free_mixed(dest, ad);
1228     }
1229     ad->decRefCount();
1230     return 0;
1231   }
1232   if (UNLIKELY(IS_REFCOUNTED_TYPE(valOut->m_type))) {
1233     return new_iter_array_cold<false>(dest, ad, valOut, keyOut);
1234   }
1235   if (UNLIKELY(IS_REFCOUNTED_TYPE(keyOut->m_type))) {
1236     return new_iter_array_cold<false>(dest, ad, valOut, keyOut);
1237   }
1238
1239   // We are transferring ownership of the array to the iterator, therefore
1240   // we do not need to adjust the refcount.
1241   auto& aiter = dest->arr();
1242   aiter.m_data = ad;
1243   auto const itypeU32 = static_cast<uint32_t>(ArrayIter::TypeArray);
1244
1245   if (ad->isPacked()) {
1246     aiter.m_pos = 0;
1247     aiter.m_itypeAndNextHelperIdx =
1248       static_cast<uint32_t>(IterNextIndex::ArrayPacked) << 16 | itypeU32;
1249     assert(aiter.m_itype == ArrayIter::TypeArray);
1250     assert(aiter.m_nextHelperIdx == IterNextIndex::ArrayPacked);
1251     if (WithRef) {
1252       tvDupWithRef(*packedData(ad), *valOut);
1253     } else {
1254       cellDup(*tvToCell(packedData(ad)), *valOut);
1255     }
1256     keyOut->m_type = KindOfInt64;
1257     keyOut->m_data.num = 0;
1258     return 1;
1259   }
1260
1261   if (ad->isMixed()) {
1262     auto const mixed = MixedArray::asMixed(ad);
1263     aiter.m_pos = mixed->getIterBegin();
1264     aiter.m_itypeAndNextHelperIdx =
1265       static_cast<uint32_t>(IterNextIndex::ArrayMixed) << 16 | itypeU32;
1266     assert(aiter.m_itype == ArrayIter::TypeArray);
1267     assert(aiter.m_nextHelperIdx == IterNextIndex::ArrayMixed);
1268     if (WithRef) {
1269       mixed->dupArrayElmWithRef(aiter.m_pos, valOut, keyOut);
1270     } else {
1271       mixed->getArrayElm(aiter.m_pos, valOut, keyOut);
1272     }
1273     return 1;
1274   }
1275
1276   return new_iter_array_cold<false>(dest, ad, valOut, keyOut);
1277 }
1278
1279 template int64_t new_iter_array_key<false>(Iter* dest, ArrayData* ad,
1280                                            TypedValue* valOut,
1281                                            TypedValue* keyOut);
1282 template int64_t new_iter_array_key<true>(Iter* dest, ArrayData* ad,
1283                                           TypedValue* valOut,
1284                                           TypedValue* keyOut);
1285
1286 class FreeObj {
1287  public:
1288   FreeObj() : m_obj(0) {}
1289   void operator=(ObjectData* obj) { m_obj = obj; }
1290   ~FreeObj() { if (UNLIKELY(m_obj != nullptr)) decRefObj(m_obj); }
1291  private:
1292   ObjectData* m_obj;
1293 };
1294
1295 /**
1296  * new_iter_object_any creates an iterator for the specified object if the
1297  * object is iterable and it is non-empty (has properties). If
1298  * new_iter_object_any creates an iterator, it does not increment the refcount
1299  * of the specified object. If new_iter_object does not create an iterator,
1300  * it decRefs the object.
1301  *
1302  * If exceptions are thrown, new_iter_object_any takes care of decRefing the
1303  * object.
1304  */
1305 static int64_t new_iter_object_any(Iter* dest, ObjectData* obj, Class* ctx,
1306                                    TypedValue* valOut, TypedValue* keyOut) {
1307   valOut = tvToCell(valOut);
1308   if (keyOut) {
1309     keyOut = tvToCell(keyOut);
1310   }
1311   ArrayIter::Type itType;
1312   {
1313     FreeObj fo;
1314     if (obj->implementsIterator()) {
1315       TRACE(2, "%s: I %p, obj %p, ctx %p, collection or Iterator\n",
1316             __func__, dest, obj, ctx);
1317       (void) new (&dest->arr()) ArrayIter(obj, ArrayIter::noInc);
1318       itType = ArrayIter::TypeIterator;
1319     } else {
1320       bool isIteratorAggregate;
1321       /*
1322        * We are not going to transfer ownership of obj to the iterator,
1323        * so arrange to decRef it later. The actual decRef has to happen
1324        * after the call to arr().end() below, because both can have visible side
1325        * effects (calls to __destruct() and valid()). Similarly it has to
1326        * happen before the iter_*_cell_local_impl calls below, because they call
1327        * current() and key() (hence the explicit scope around FreeObj fo;)
1328        */
1329       fo = obj;
1330
1331       Object itObj = obj->iterableObject(isIteratorAggregate, false);
1332       if (isIteratorAggregate) {
1333         TRACE(2, "%s: I %p, obj %p, ctx %p, IteratorAggregate\n",
1334               __func__, dest, obj, ctx);
1335         (void) new (&dest->arr()) ArrayIter(itObj.detach(), ArrayIter::noInc);
1336         itType = ArrayIter::TypeIterator;
1337       } else {
1338         TRACE(2, "%s: I %p, obj %p, ctx %p, iterate as array\n",
1339               __func__, dest, obj, ctx);
1340         auto ctxStr = ctx ? ctx->nameStr() : StrNR();
1341         Array iterArray(itObj->o_toIterArray(ctxStr));
1342         ArrayData* ad = iterArray.get();
1343         (void) new (&dest->arr()) ArrayIter(ad);
1344         itType = ArrayIter::TypeArray;
1345       }
1346     }
1347     try {
1348       if (dest->arr().end()) {
1349         // Iterator was empty; call the destructor on the iterator we just
1350         // constructed.
1351         dest->arr().~ArrayIter();
1352         return 0LL;
1353       }
1354     } catch (...) {
1355       dest->arr().~ArrayIter();
1356       throw;
1357     }
1358   }
1359
1360   dest->arr().setIterType(itType);
1361   if (itType == ArrayIter::TypeIterator) {
1362     iter_value_cell_local_impl<false, false>(dest, valOut);
1363     if (keyOut) {
1364       iter_key_cell_local_impl<false, false>(dest, keyOut);
1365     }
1366   } else {
1367     iter_value_cell_local_impl<true, false>(dest, valOut);
1368     if (keyOut) {
1369       iter_key_cell_local_impl<true, false>(dest, keyOut);
1370     }
1371   }
1372   return 1LL;
1373 }
1374
1375 int64_t new_iter_object(Iter* dest, ObjectData* obj, Class* ctx,
1376                         TypedValue* valOut, TypedValue* keyOut) {
1377   TRACE(2, "%s: I %p, obj %p, ctx %p, collection or Iterator or Object\n",
1378         __func__, dest, obj, ctx);
1379   Collection::Type type = obj->getCollectionType();
1380   switch (type) {
1381     case Collection::VectorType:
1382       return iterInit<c_Vector, ArrayIter::Versionable>(
1383                                 dest, static_cast<c_Vector*>(obj),
1384                                 valOut, keyOut);
1385     case Collection::MapType:
1386     case Collection::ImmMapType:
1387       return iterInit<BaseMap, ArrayIter::VersionableSparse>(
1388                                 dest,
1389                                 static_cast<BaseMap*>(obj),
1390                                 valOut, keyOut);
1391     case Collection::SetType:
1392       return iterInit<c_Set, ArrayIter::VersionableSparse>(
1393                                 dest,
1394                                 static_cast<c_Set*>(obj),
1395                                 valOut, keyOut);
1396     case Collection::PairType:
1397       return iterInit<c_Pair, ArrayIter::Fixed>(
1398                                 dest,
1399                                 static_cast<c_Pair*>(obj),
1400                                 valOut, keyOut);
1401     case Collection::ImmVectorType:
1402       return iterInit<c_ImmVector, ArrayIter::Fixed>(
1403                                 dest, static_cast<c_ImmVector*>(obj),
1404                                 valOut, keyOut);
1405     case Collection::ImmSetType:
1406       return iterInit<c_ImmSet, ArrayIter::VersionableSparse>(
1407                                    dest,
1408                                    static_cast<c_ImmSet*>(obj),
1409                                    valOut, keyOut);
1410     case Collection::InvalidType:
1411       return new_iter_object_any(dest, obj, ctx, valOut, keyOut);
1412   }
1413   not_reached();
1414 }
1415
1416 template <bool withRef>
1417 NEVER_INLINE
1418 static int64_t iter_next_collection(ArrayIter* ai,
1419                                     TypedValue* valOut,
1420                                     TypedValue* keyOut,
1421                                     Collection::Type type) {
1422   assert(!ai->hasArrayData());
1423   assert(type != Collection::InvalidType);
1424
1425   switch (type) {
1426     case Collection::VectorType:
1427       return iterNext<c_Vector, ArrayIter::Versionable>(
1428         ai, valOut, keyOut);
1429     case Collection::MapType:
1430     case Collection::ImmMapType:
1431       return iterNext<BaseMap, ArrayIter::VersionableSparse>(
1432         ai, valOut, keyOut);
1433     case Collection::SetType:
1434       return iterNext<c_Set, ArrayIter::VersionableSparse>(
1435         ai, valOut, keyOut);
1436     case Collection::PairType:
1437       return iterNext<c_Pair, ArrayIter::Fixed>(
1438         ai, valOut, keyOut);
1439     case Collection::ImmVectorType:
1440       return iterNext<c_ImmVector, ArrayIter::Fixed>(
1441         ai, valOut, keyOut);
1442     case Collection::ImmSetType:
1443       return iterNext<c_ImmSet, ArrayIter::VersionableSparse>(
1444         ai, valOut, keyOut);
1445     case Collection::InvalidType:
1446       break;
1447   }
1448   not_reached();
1449 }
1450
1451 template <bool withRef>
1452 NEVER_INLINE
1453 int64_t iter_next_cold(Iter* iter, TypedValue* valOut, TypedValue* keyOut) {
1454   auto const ai = &iter->arr();
1455   assert(ai->getIterType() == ArrayIter::TypeArray ||
1456          ai->getIterType() == ArrayIter::TypeIterator);
1457   if (UNLIKELY(!ai->hasArrayData())) {
1458     auto const coll = ai->getObject()->getCollectionType();
1459     if (UNLIKELY(coll != Collection::InvalidType)) {
1460       return iter_next_collection<withRef>(ai, valOut, keyOut, coll);
1461     }
1462   }
1463
1464   ai->next();
1465   if (ai->end()) {
1466     // The ArrayIter destructor will decRef the array
1467     ai->~ArrayIter();
1468     return 0;
1469   }
1470   if (iter->arr().getIterType() == ArrayIter::TypeArray) {
1471     iter_value_cell_local_impl<true, withRef>(iter, valOut);
1472     if (keyOut) {
1473       iter_key_cell_local_impl<true, withRef>(iter, keyOut);
1474     }
1475   } else {
1476     iter_value_cell_local_impl<false, withRef>(iter, valOut);
1477     if (keyOut) {
1478       iter_key_cell_local_impl<false, withRef>(iter, keyOut);
1479     }
1480   }
1481   return 1;
1482 }
1483
1484 NEVER_INLINE
1485 static int64_t iter_next_apc_array(Iter* iter,
1486                                    TypedValue* valOut,
1487                                    TypedValue* keyOut,
1488                                    ArrayData* ad) {
1489   assert(ad->kind() == ArrayData::kSharedKind);
1490
1491   auto const arrIter = &iter->arr();
1492   auto const arr = APCLocalArray::asSharedArray(ad);
1493   ssize_t const pos = arr->iterAdvanceImpl(arrIter->getPos());
1494   if (UNLIKELY(pos == ArrayData::invalid_index)) {
1495     if (UNLIKELY(arr->hasExactlyOneRef())) {
1496       return iter_next_free_apc(iter, arr);
1497     }
1498     arr->decRefCount();
1499     if (debug) {
1500       iter->arr().setIterType(ArrayIter::TypeUndefined);
1501     }
1502     return 0;
1503   }
1504   arrIter->setPos(pos);
1505
1506   // Note that APCLocalArray can never return KindOfRefs.
1507   const Variant& var = APCLocalArray::GetValueRef(arr->asArrayData(), pos);
1508   assert(var.asTypedValue()->m_type != KindOfRef);
1509   cellSet(*var.asTypedValue(), *valOut);
1510   if (LIKELY(!keyOut)) return 1;
1511
1512   Cell key;
1513   APCLocalArray::NvGetKey(ad, &key, pos);
1514   auto const keyType  = keyOut->m_type;
1515   auto const keyDatum = keyOut->m_data.num;
1516   cellCopy(key, *keyOut);
1517   tvRefcountedDecRefHelper(keyType, keyDatum);
1518
1519   return 1;
1520 }
1521
1522 int64_t witer_next_key(Iter* iter, TypedValue* valOut, TypedValue* keyOut) {
1523   TRACE(2, "iter_next_key: I %p\n", iter);
1524   assert(iter->arr().getIterType() == ArrayIter::TypeArray ||
1525          iter->arr().getIterType() == ArrayIter::TypeIterator);
1526   auto const arrIter = &iter->arr();
1527   if (UNLIKELY(!arrIter->hasArrayData())) {
1528     goto cold;
1529   }
1530
1531   {
1532     auto const ad       = const_cast<ArrayData*>(arrIter->getArrayData());
1533     auto const isPacked = ad->isPacked();
1534     auto const isMixed  = ad->isMixed();
1535
1536     if (UNLIKELY(!isMixed && !isPacked)) {
1537       if (ad->isSharedArray()) {
1538         // TODO(#4055855): what if a local value in an apc array has
1539         // been turned into a ref?  Is this actually ok to do?
1540         return iter_next_apc_array(iter, valOut, keyOut, ad);
1541       }
1542       goto cold;
1543     }
1544
1545     if (LIKELY(isPacked)) {
1546       ssize_t pos = arrIter->getPos() + 1;
1547       if (size_t(pos) >= size_t(ad->getSize())) {
1548         if (UNLIKELY(ad->hasExactlyOneRef())) {
1549           return iter_next_free_packed(iter, ad);
1550         }
1551         ad->decRefCount();
1552         if (debug) {
1553           iter->arr().setIterType(ArrayIter::TypeUndefined);
1554         }
1555         return 0;
1556       }
1557
1558       if (UNLIKELY(tvDecRefWillCallHelper(valOut)) ||
1559           UNLIKELY(tvDecRefWillCallHelper(keyOut))) {
1560         goto cold;
1561       }
1562       tvDecRefOnly(valOut);
1563       tvDecRefOnly(keyOut);
1564
1565       arrIter->setPos(pos);
1566       tvDupWithRef(packedData(ad)[pos], *valOut);
1567       keyOut->m_type = KindOfInt64;
1568       keyOut->m_data.num = pos;
1569       return 1;
1570     }
1571
1572     auto const mixed = MixedArray::asMixed(ad);
1573     ssize_t pos = arrIter->getPos();
1574     do {
1575       ++pos;
1576       if (size_t(pos) >= size_t(mixed->iterLimit())) {
1577         if (UNLIKELY(mixed->hasExactlyOneRef())) {
1578           return iter_next_free_mixed(iter, mixed->asArrayData());
1579         }
1580         mixed->decRefCount();
1581         if (debug) {
1582           iter->arr().setIterType(ArrayIter::TypeUndefined);
1583         }
1584         return 0;
1585       }
1586     } while (UNLIKELY(mixed->isTombstone(pos)));
1587
1588     if (UNLIKELY(tvDecRefWillCallHelper(valOut)) ||
1589         UNLIKELY(tvDecRefWillCallHelper(keyOut))) {
1590       goto cold;
1591     }
1592     tvDecRefOnly(valOut);
1593     tvDecRefOnly(keyOut);
1594
1595     arrIter->setPos(pos);
1596     mixed->dupArrayElmWithRef(pos, valOut, keyOut);
1597     return 1;
1598   }
1599
1600 cold:
1601   return iter_next_cold<true>(iter, valOut, keyOut);
1602 }
1603
1604 ///////////////////////////////////////////////////////////////////////////////
1605 // MIter functions
1606
1607 int64_t new_miter_array_key(Iter* dest, RefData* v1,
1608                            TypedValue* valOut, TypedValue* keyOut) {
1609   TRACE(2, "%s: I %p, ad %p\n", __func__, dest, v1);
1610
1611   TypedValue* rtv = v1->tv();
1612   ArrayData* ad = rtv->m_data.parr;
1613
1614   if (UNLIKELY(ad->empty())) {
1615     return 0LL;
1616   }
1617
1618   (void) new (&dest->marr()) MArrayIter(v1);
1619   dest->marr().advance();
1620
1621   tvAsVariant(valOut).assignRef(dest->marr().val());
1622   if (keyOut) {
1623     tvAsVariant(keyOut).assign(dest->marr().key());
1624   }
1625
1626   return 1LL;
1627 }
1628
1629 int64_t new_miter_object(Iter* dest, RefData* ref, Class* ctx,
1630                       TypedValue* valOut, TypedValue* keyOut) {
1631   ObjectData *obj = ref->tv()->m_data.pobj;
1632   if (obj->isCollection()) {
1633     raise_error("Collection elements cannot be taken by reference");
1634   }
1635
1636   bool isIterator;
1637   Object itObj = obj->iterableObject(isIterator);
1638   if (isIterator) {
1639     raise_error("An iterator cannot be used with foreach by reference");
1640   }
1641
1642   TRACE(2, "%s: I %p, obj %p, ctx %p, iterate as array\n",
1643         __func__, dest, obj, ctx);
1644   auto ctxStr = ctx ? ctx->nameStr() : StrNR();
1645   Array iterArray(itObj->o_toIterArray(ctxStr, true));
1646   ArrayData* ad = iterArray.detach();
1647   (void) new (&dest->marr()) MArrayIter(ad);
1648   if (UNLIKELY(!dest->marr().advance())) {
1649     // Iterator was empty; call the destructor on the iterator we just
1650     // constructed.
1651     dest->marr().~MArrayIter();
1652     return 0LL;
1653   }
1654
1655   tvAsVariant(valOut).assignRef(dest->marr().val());
1656   if (keyOut) {
1657     tvAsVariant(keyOut).assign(dest->marr().key());
1658   }
1659   return 1LL;
1660 }
1661
1662 int64_t new_miter_other(Iter* dest, RefData* data) {
1663   TRACE(2, "%s: I %p, data %p, invalid type\n",
1664         __func__, dest, data);
1665
1666   // TODO(#2570852): we should really issue a warning here
1667   return 0LL;
1668 }
1669
1670 int64_t miter_next_key(Iter* iter, TypedValue* valOut, TypedValue* keyOut) {
1671   TRACE(2, "miter_next_key: I %p\n", iter);
1672   MArrayIter& marr = iter->marr();
1673
1674   if (UNLIKELY(!marr.advance())) {
1675     marr.~MArrayIter();
1676     return 0LL;
1677   }
1678
1679   tvAsVariant(valOut).assignRef(marr.val());
1680   if (keyOut) {
1681     tvAsVariant(keyOut).assign(marr.key());
1682   }
1683
1684   return 1LL;
1685 }
1686
1687 ///////////////////////////////////////////////////////////////////////////////
1688 // IterNext/IterNextK helpers
1689
1690 namespace {
1691
1692 template<bool HasKey>
1693 ALWAYS_INLINE
1694 int64_t iter_next_mixed_impl(Iter* it,
1695                              TypedValue* valOut,
1696                              TypedValue* keyOut) {
1697   ArrayIter& iter    = it->arr();
1698   auto const arrData = const_cast<ArrayData*>(iter.getArrayData());
1699   auto const arr     = MixedArray::asMixed(arrData);
1700   ssize_t pos        = iter.getPos();
1701
1702   do {
1703     if (size_t(++pos) >= size_t(arr->iterLimit())) {
1704       if (UNLIKELY(arr->hasExactlyOneRef())) {
1705         return iter_next_free_mixed(it, arr->asArrayData());
1706       }
1707       arr->decRefCount();
1708       if (debug) {
1709         iter.setIterType(ArrayIter::TypeUndefined);
1710       }
1711       return 0;
1712     }
1713   } while (UNLIKELY(arr->isTombstone(pos)));
1714
1715   if (UNLIKELY(tvDecRefWillCallHelper(valOut))) {
1716     return iter_next_cold<false>(it, valOut, keyOut);
1717   }
1718   if (HasKey && UNLIKELY(tvDecRefWillCallHelper(keyOut))) {
1719     return iter_next_cold<false>(it, valOut, keyOut);
1720   }
1721   tvDecRefOnly(valOut);
1722   if (HasKey) {
1723     tvDecRefOnly(keyOut);
1724   }
1725   iter.setPos(pos);
1726   if (HasKey) {
1727     arr->getArrayElm(pos, valOut, keyOut);
1728   } else {
1729     arr->getArrayElm(pos, valOut);
1730   }
1731   return 1;
1732 }
1733
1734 template<bool HasKey>
1735 int64_t iter_next_packed_impl(Iter* it,
1736                               TypedValue* valOut,
1737                               TypedValue* keyOut) {
1738   assert(it->arr().getIterType() == ArrayIter::TypeArray &&
1739          it->arr().hasArrayData() &&
1740          it->arr().getArrayData()->isPacked());
1741   auto& iter = it->arr();
1742   auto const ad = const_cast<ArrayData*>(iter.getArrayData());
1743   assert(PackedArray::checkInvariants(ad));
1744
1745   ssize_t pos = iter.getPos() + 1;
1746   if (LIKELY(pos < ad->getSize())) {
1747     if (UNLIKELY(tvDecRefWillCallHelper(valOut))) {
1748       return iter_next_cold<false>(it, valOut, keyOut);
1749     }
1750     if (HasKey && UNLIKELY(tvDecRefWillCallHelper(keyOut))) {
1751       return iter_next_cold<false>(it, valOut, keyOut);
1752     }
1753     tvDecRefOnly(valOut);
1754     iter.setPos(pos);
1755     cellDup(*tvToCell(packedData(ad) + pos), *valOut);
1756     if (HasKey) {
1757       tvDecRefOnly(keyOut);
1758       keyOut->m_data.num = pos;
1759       keyOut->m_type = KindOfInt64;
1760     }
1761     return 1;
1762   }
1763
1764   // Finished iterating---we need to free the array.
1765   if (UNLIKELY(ad->hasExactlyOneRef())) {
1766     return iter_next_free_packed(it, ad);
1767   }
1768   ad->decRefCount();
1769   if (debug) {
1770     iter.setIterType(ArrayIter::TypeUndefined);
1771   }
1772   return 0;
1773 }
1774
1775 }
1776
1777 int64_t iterNextArrayPacked(Iter* it, TypedValue* valOut) {
1778   TRACE(2, "iterNextArrayPacked: I %p\n", it);
1779   assert(it->arr().getIterType() == ArrayIter::TypeArray &&
1780          it->arr().hasArrayData() &&
1781          it->arr().getArrayData()->isPacked());
1782   return iter_next_packed_impl<false>(it, valOut, nullptr);
1783 }
1784
1785 int64_t iterNextKArrayPacked(Iter* it,
1786                              TypedValue* valOut,
1787                              TypedValue* keyOut) {
1788   TRACE(2, "iterNextKArrayPacked: I %p\n", it);
1789   assert(it->arr().getIterType() == ArrayIter::TypeArray &&
1790          it->arr().hasArrayData() &&
1791          it->arr().getArrayData()->isPacked());
1792   return iter_next_packed_impl<true>(it, valOut, keyOut);
1793 }
1794
1795 int64_t iterNextArrayMixed(Iter* it, TypedValue* valOut) {
1796   TRACE(2, "iterNextArrayMixed: I %p\n", it);
1797   assert(it->arr().getIterType() == ArrayIter::TypeArray &&
1798          it->arr().hasArrayData() &&
1799          it->arr().getArrayData()->isMixed());
1800   return iter_next_mixed_impl<false>(it, valOut, nullptr);
1801 }
1802
1803 int64_t iterNextKArrayMixed(Iter* it,
1804                             TypedValue* valOut,
1805                             TypedValue* keyOut) {
1806   TRACE(2, "iterNextKArrayMixed: I %p\n", it);
1807   assert(it->arr().getIterType() == ArrayIter::TypeArray &&
1808          it->arr().hasArrayData() &&
1809          it->arr().getArrayData()->isMixed());
1810   return iter_next_mixed_impl<true>(it, valOut, keyOut);
1811 }
1812
1813 int64_t iterNextArray(Iter* it, TypedValue* valOut) {
1814   TRACE(2, "iterNextArray: I %p\n", it);
1815   assert(it->arr().getIterType() == ArrayIter::TypeArray &&
1816          it->arr().hasArrayData());
1817   assert(!it->arr().getArrayData()->isPacked());
1818   assert(!it->arr().getArrayData()->isMixed());
1819
1820   ArrayIter& iter = it->arr();
1821   auto const ad = const_cast<ArrayData*>(iter.getArrayData());
1822   if (ad->isSharedArray()) {
1823     return iter_next_apc_array(it, valOut, nullptr, ad);
1824   }
1825   return iter_next_cold<false>(it, valOut, nullptr);
1826 }
1827
1828 int64_t iterNextKArray(Iter* it,
1829                        TypedValue* valOut,
1830                        TypedValue* keyOut) {
1831   TRACE(2, "iterNextKArray: I %p\n", it);
1832   assert(it->arr().getIterType() == ArrayIter::TypeArray &&
1833          it->arr().hasArrayData());
1834   assert(!it->arr().getArrayData()->isMixed());
1835   assert(!it->arr().getArrayData()->isPacked());
1836
1837   ArrayIter& iter = it->arr();
1838   auto const ad = const_cast<ArrayData*>(iter.getArrayData());
1839   if (ad->isSharedArray()) {
1840     return iter_next_apc_array(it, valOut, keyOut, ad);
1841   }
1842   return iter_next_cold<false>(it, valOut, keyOut);
1843 }
1844
1845 int64_t iterNextVector(Iter* it, TypedValue* valOut) {
1846   TRACE(2, "iterNextVector: I %p\n", it);
1847   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1848          it->arr().hasCollection());
1849
1850   auto const iter = &it->arr();
1851   return iterNext<c_Vector, ArrayIter::Versionable>(iter, valOut, nullptr);
1852 }
1853
1854 int64_t iterNextKVector(Iter* it,
1855                         TypedValue* valOut,
1856                         TypedValue* keyOut) {
1857   TRACE(2, "iterNextKVector: I %p\n", it);
1858   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1859          it->arr().hasCollection());
1860
1861   auto const iter = &it->arr();
1862   return iterNext<c_Vector, ArrayIter::Versionable>(iter, valOut, keyOut);
1863 }
1864
1865 int64_t iterNextImmVector(Iter* it, TypedValue* valOut) {
1866   TRACE(2, "iterFrozenNextVector: I %p\n", it);
1867   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1868          it->arr().hasCollection());
1869
1870   auto const iter = &it->arr();
1871   return iterNext<c_ImmVector, ArrayIter::Fixed>(iter, valOut, nullptr);
1872 }
1873
1874 int64_t iterNextKImmVector(Iter* it,
1875                               TypedValue* valOut,
1876                               TypedValue* keyOut) {
1877   TRACE(2, "iterFrozenNextKVector: I %p\n", it);
1878   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1879          it->arr().hasCollection());
1880
1881   auto const iter = &it->arr();
1882   return iterNext<c_ImmVector, ArrayIter::Fixed>(iter, valOut, keyOut);
1883 }
1884
1885 int64_t iterNextMap(Iter* it, TypedValue* valOut) {
1886   TRACE(2, "iterNextMap: I %p\n", it);
1887   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1888          it->arr().hasCollection());
1889
1890   auto const iter = &it->arr();
1891   return iterNext<c_Map, ArrayIter::VersionableSparse>(iter, valOut, nullptr);
1892 }
1893
1894 int64_t iterNextImmMap(Iter* it, TypedValue* valOut) {
1895   TRACE(2, "iterNextImmMap: I %p\n", it);
1896   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1897          it->arr().hasCollection());
1898
1899   auto const iter = &it->arr();
1900   return
1901     iterNext<c_ImmMap, ArrayIter::VersionableSparse>(iter, valOut, nullptr);
1902 }
1903
1904 int64_t iterNextKMap(Iter* it,
1905                      TypedValue* valOut,
1906                      TypedValue* keyOut) {
1907   TRACE(2, "iterNextKMap: I %p\n", it);
1908   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1909          it->arr().hasCollection());
1910
1911   auto const iter = &it->arr();
1912   return iterNext<c_Map, ArrayIter::VersionableSparse>(iter, valOut, keyOut);
1913 }
1914
1915 int64_t iterNextKImmMap(Iter* it,
1916                         TypedValue* valOut,
1917                         TypedValue* keyOut) {
1918   TRACE(2, "iterNextKImmMap: I %p\n", it);
1919   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1920          it->arr().hasCollection());
1921
1922   auto const iter = &it->arr();
1923   return iterNext<c_ImmMap, ArrayIter::VersionableSparse>(iter, valOut, keyOut);
1924 }
1925
1926 int64_t iterNextSet(Iter* it, TypedValue* valOut) {
1927   TRACE(2, "iterNextSet: I %p\n", it);
1928   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1929          it->arr().hasCollection());
1930
1931   auto const iter = &it->arr();
1932   return iterNext<c_Set, ArrayIter::VersionableSparse>(iter, valOut, nullptr);
1933 }
1934
1935 int64_t iterNextImmSet(Iter* it, TypedValue* valOut) {
1936   TRACE(2, "iterNextImmSet: I %p\n", it);
1937   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1938          it->arr().hasCollection());
1939
1940   auto const iter = &it->arr();
1941   return
1942     iterNext<c_ImmSet, ArrayIter::VersionableSparse>(iter, valOut, nullptr);
1943 }
1944
1945 int64_t iterNextKSet(Iter* it,
1946                      TypedValue* valOut,
1947                      TypedValue* keyOut) {
1948   TRACE(2, "iterNextKSet: I %p\n", it);
1949   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1950          it->arr().hasCollection());
1951
1952   auto const iter = &it->arr();
1953   return iterNext<c_Set, ArrayIter::VersionableSparse>(iter, valOut, keyOut);
1954 }
1955
1956 int64_t iterNextKImmSet(Iter* it,
1957                         TypedValue* valOut,
1958                         TypedValue* keyOut) {
1959   TRACE(2, "iterNextKImmSet: I %p\n", it);
1960   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1961          it->arr().hasCollection());
1962
1963   auto const iter = &it->arr();
1964   return iterNext<c_ImmSet, ArrayIter::VersionableSparse>(iter, valOut, keyOut);
1965 }
1966
1967 int64_t iterNextPair(Iter* it, TypedValue* valOut) {
1968   TRACE(2, "iterNextPair: I %p\n", it);
1969   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1970          it->arr().hasCollection());
1971
1972   auto const iter = &it->arr();
1973   return iterNext<c_Pair, ArrayIter::Fixed>(iter, valOut, nullptr);
1974 }
1975
1976 int64_t iterNextKPair(Iter* it,
1977                       TypedValue* valOut,
1978                       TypedValue* keyOut) {
1979   TRACE(2, "iterNextKPair: I %p\n", it);
1980   assert(it->arr().getIterType() == ArrayIter::TypeIterator &&
1981          it->arr().hasCollection());
1982
1983   auto const iter = &it->arr();
1984   return iterNext<c_Pair, ArrayIter::Fixed>(iter, valOut, keyOut);
1985 }
1986
1987 int64_t iterNextObject(Iter* it, TypedValue* valOut) {
1988   TRACE(2, "iterNextObject: I %p\n", it);
1989   // We can't just put the address of iter_next_cold in the table
1990   // below right now because we need to get a nullptr into the third
1991   // argument register for it.
1992   return iter_next_cold<false>(it, valOut, nullptr);
1993 }
1994
1995 using IterNextHelper  = int64_t (*)(Iter*, TypedValue*);
1996 using IterNextKHelper = int64_t (*)(Iter*, TypedValue*, TypedValue*);
1997
1998 const IterNextHelper g_iterNextHelpers[] = {
1999   &iterNextArrayPacked,
2000   &iterNextArrayMixed,
2001   &iterNextArray,
2002   &iterNextVector,
2003   &iterNextImmVector,
2004   &iterNextMap,
2005   &iterNextImmMap,
2006   &iterNextSet,
2007   &iterNextImmSet,
2008   &iterNextPair,
2009   &iterNextObject,
2010 };
2011
2012 const IterNextKHelper g_iterNextKHelpers[] = {
2013   &iterNextKArrayPacked,
2014   &iterNextKArrayMixed,
2015   &iterNextKArray,
2016   &iterNextKVector,
2017   &iterNextKImmVector,
2018   &iterNextKMap,
2019   &iterNextKImmMap,
2020   &iterNextKSet,
2021   &iterNextKImmSet,
2022   &iterNextKPair,
2023   &iter_next_cold<false>, // iterNextKObject
2024 };
2025
2026 int64_t iter_next_ind(Iter* iter, TypedValue* valOut) {
2027   TRACE(2, "iter_next_ind: I %p\n", iter);
2028   assert(iter->arr().getIterType() == ArrayIter::TypeArray ||
2029          iter->arr().getIterType() == ArrayIter::TypeIterator);
2030   auto const arrIter = &iter->arr();
2031   valOut = tvToCell(valOut);
2032   IterNextHelper iterNext =
2033       g_iterNextHelpers[static_cast<uint32_t>(arrIter->getHelperIndex())];
2034   return iterNext(iter, valOut);
2035 }
2036
2037 int64_t iter_next_key_ind(Iter* iter, TypedValue* valOut, TypedValue* keyOut) {
2038   TRACE(2, "iter_next_key_ind: I %p\n", iter);
2039   assert(iter->arr().getIterType() == ArrayIter::TypeArray ||
2040          iter->arr().getIterType() == ArrayIter::TypeIterator);
2041   auto const arrIter = &iter->arr();
2042   valOut = tvToCell(valOut);
2043   keyOut = tvToCell(keyOut);
2044   IterNextKHelper iterNextK =
2045       g_iterNextKHelpers[static_cast<uint32_t>(arrIter->getHelperIndex())];
2046   return iterNextK(iter, valOut, keyOut);
2047 }
2048
2049 ///////////////////////////////////////////////////////////////////////////////
2050 }