hphp/runtime/ext/ext_collections.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010- Facebook, Inc. (http://www.facebook.com)         |
   6    | Copyright (c) 1997-2010 The PHP Group                                |
   7    +----------------------------------------------------------------------+
   8    | This source file is subject to version 3.01 of the PHP license,      |
   9    | that is bundled with this package in the file LICENSE, and is        |
  10    | available through the world-wide-web at the following url:           |
  11    | http://www.php.net/license/3_01.txt                                  |
  12    | If you did not receive a copy of the PHP license and are unable to   |
  13    | obtain it through the world-wide-web, please send a note to          |
  14    | license@php.net so we can mail you a copy immediately.               |
  15    +----------------------------------------------------------------------+
  16 */
  17
  18 #include "hphp/runtime/ext/ext_collections.h"
  19 #include "hphp/runtime/base/variable_serializer.h"
  20 #include "hphp/runtime/base/array/sort_helpers.h"
  21 #include "hphp/runtime/ext/ext_array.h"
  22 #include "hphp/runtime/ext/ext_math.h"
  23 #include "hphp/runtime/ext/ext_intl.h"
  24 #include "hphp/runtime/vm/translator/translator-inline.h"
  25 #include "hphp/system/lib/systemlib.h"
  26
  27 namespace HPHP {
  28 ///////////////////////////////////////////////////////////////////////////////
  29
  30 static void throwIntOOB(int64_t key, bool isVector = false) ATTRIBUTE_COLD
  31   ATTRIBUTE_NORETURN;
  32
  33 void throwIntOOB(int64_t key, bool isVector /* = false */) {
  34   static const size_t reserveSize = 50;
  35   String msg(reserveSize, ReserveString);
  36   char* buf = msg.mutableSlice().ptr;
  37   int sz = sprintf(buf, "Integer key %" PRId64 " is %s", key,
  38                    isVector ? "out of bounds" : "not defined");
  39   assert(sz <= reserveSize);
  40   msg.setSize(sz);
  41   Object e(SystemLib::AllocOutOfBoundsExceptionObject(msg));
  42   throw e;
  43 }
  44
  45 static void throwStrOOB(StringData* key) ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
  46
  47 void throwStrOOB(StringData* key) {
  48   const size_t maxDisplaySize = 20;
  49   const char* dots = "...";
  50   size_t dotsSize = strlen(dots);
  51   int keySize = key->size();
  52   bool keyIsLarge = (keySize > maxDisplaySize);
  53   size_t displaySize = keyIsLarge ? (maxDisplaySize - dotsSize) : keySize;
  54   const char* part1 = "String key \"";
  55   size_t part1Size = strlen(part1);
  56   size_t part2Size = keyIsLarge ? maxDisplaySize : keySize;
  57   const char* part3 = "\" is not defined";
  58   size_t part3Size = strlen(part3);
  59   // Do some math ahead of time so we know exactly how large
  60   // the String needs to be
  61   String msg(part1Size + part2Size + part3Size, ReserveString);
  62   msg += StringSlice(part1, part1Size);
  63   msg += StringSlice(key->data(), displaySize);
  64   if (keyIsLarge) msg += StringSlice(dots, dotsSize);
  65   msg += StringSlice(part3, part3Size);
  66   Object e(SystemLib::AllocOutOfBoundsExceptionObject(msg));
  67   throw e;
  68 }
  69
  70 static inline ArrayIter getArrayIterHelper(CVarRef v, size_t& sz) {
  71   if (v.isArray()) {
  72     ArrayData* ad = v.getArrayData();
  73     sz = ad->size();
  74     return ArrayIter(ad);
  75   }
  76   if (v.isObject()) {
  77     ObjectData* obj = v.getObjectData();
  78     if (obj->isCollection()) {
  79       sz = collectionSize(obj);
  80       return ArrayIter(obj);
  81     }
  82     bool isIterable;
  83     Object iterable = obj->iterableObject(isIterable);
  84     if (isIterable) {
  85       sz = 0;
  86       return ArrayIter(iterable, ArrayIter::transferOwner);
  87     }
  88   }
  89   Object e(SystemLib::AllocInvalidArgumentExceptionObject(
  90     "Parameter must be an array or an instance of Traversable"));
  91   throw e;
  92 }
  93
  94 ///////////////////////////////////////////////////////////////////////////////
  95
  96 c_Vector::c_Vector(Class* cb) :
  97     ExtObjectDataFlags<ObjectData::VectorAttrInit|
  98                        ObjectData::UseGet|
  99                        ObjectData::UseSet|
 100                        ObjectData::UseIsset|
 101                        ObjectData::UseUnset>(cb),
 102     m_data(nullptr), m_size(0), m_capacity(0), m_version(0) {
 103 }
 104
 105 c_Vector::~c_Vector() {
 106   uint sz = m_size;
 107   for (uint i = 0; i < sz; ++i) {
 108     tvRefcountedDecRef(&m_data[i]);
 109   }
 110   c_Vector::freeData();
 111 }
 112
 113 void c_Vector::freeData() {
 114   if (m_data) {
 115     smart_free(m_data);
 116     m_data = nullptr;
 117   }
 118 }
 119
 120 void c_Vector::t___construct(CVarRef iterable /* = null_variant */) {
 121   if (!iterable.isInitialized()) {
 122     return;
 123   }
 124   size_t sz;
 125   ArrayIter iter = getArrayIterHelper(iterable, sz);
 126   if (sz) {
 127     reserve(sz);
 128   }
 129   for (; iter; ++iter) {
 130     Variant v = iter.second();
 131     TypedValue* tv = cvarToCell(&v);
 132     add(tv);
 133   }
 134 }
 135
 136 void c_Vector::grow() {
 137   if (m_capacity) {
 138     m_capacity += m_capacity;
 139   } else {
 140     m_capacity = 8;
 141   }
 142   m_data = (TypedValue*)smart_realloc(m_data, m_capacity * sizeof(TypedValue));
 143 }
 144
 145 void c_Vector::resize(int64_t sz, TypedValue* val) {
 146   assert(val && val->m_type != KindOfRef);
 147   ++m_version;
 148   assert(sz >= 0);
 149   uint requestedSize = (uint)sz;
 150   if (m_capacity < requestedSize) {
 151     m_capacity = requestedSize;
 152     m_data =
 153       (TypedValue*)smart_realloc(m_data, m_capacity * sizeof(TypedValue));
 154   }
 155   if (m_size > requestedSize) {
 156     do {
 157       --m_size;
 158       tvRefcountedDecRef(&m_data[m_size]);
 159     } while (m_size > requestedSize);
 160   } else {
 161     for (; m_size < requestedSize; ++m_size) {
 162       tvDup(val, &m_data[m_size]);
 163     }
 164   }
 165 }
 166
 167 void c_Vector::reserve(int64_t sz) {
 168   if (sz <= 0) return;
 169   if (m_capacity < sz) {
 170     ++m_version;
 171     m_capacity = sz;
 172     m_data =
 173       (TypedValue*)smart_realloc(m_data, m_capacity * sizeof(TypedValue));
 174   }
 175 }
 176
 177 Array c_Vector::toArrayImpl() const {
 178   ArrayInit ai(m_size, ArrayInit::vectorInit);
 179   uint sz = m_size;
 180   for (uint i = 0; i < sz; ++i) {
 181     ai.set(tvAsCVarRef(&m_data[i]));
 182   }
 183   return ai.create();
 184 }
 185
 186 Array c_Vector::o_toArray() const {
 187   check_collection_cast_to_array();
 188   return toArrayImpl();
 189 }
 190
 191 ObjectData* c_Vector::clone() {
 192   ObjectData* obj = ObjectData::clone();
 193   auto target = static_cast<c_Vector*>(obj);
 194   uint sz = m_size;
 195   TypedValue* data;
 196   target->m_capacity = target->m_size = sz;
 197   target->m_data = data = (TypedValue*)smart_malloc(sz * sizeof(TypedValue));
 198   for (int i = 0; i < sz; ++i) {
 199     tvDup(&m_data[i], &data[i]);
 200   }
 201   return obj;
 202 }
 203
 204 Object c_Vector::t_add(CVarRef val) {
 205   TypedValue* tv = cvarToCell(&val);
 206   add(tv);
 207   return this;
 208 }
 209
 210 Object c_Vector::t_addall(CVarRef iterable) {
 211   size_t sz;
 212   ArrayIter iter = getArrayIterHelper(iterable, sz);
 213   if (sz) {
 214     reserve(m_size + sz);
 215   }
 216   for (; iter; ++iter) {
 217     Variant v = iter.second();
 218     TypedValue* tv = cvarToCell(&v);
 219     add(tv);
 220   }
 221   return this;
 222 }
 223
 224 Object c_Vector::t_append(CVarRef val) {
 225   TypedValue* tv = cvarToCell(&val);
 226   add(tv);
 227   return this;
 228 }
 229
 230 Variant c_Vector::t_pop() {
 231   ++m_version;
 232   if (m_size) {
 233     --m_size;
 234     Variant ret = tvAsCVarRef(&m_data[m_size]);
 235     tvRefcountedDecRef(&m_data[m_size]);
 236     return ret;
 237   } else {
 238     Object e(SystemLib::AllocRuntimeExceptionObject(
 239       "Cannot pop empty Vector"));
 240     throw e;
 241   }
 242 }
 243
 244 void c_Vector::t_resize(CVarRef sz, CVarRef value) {
 245   if (!sz.isInteger()) {
 246     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 247       "Parameter sz must be a non-negative integer"));
 248     throw e;
 249   }
 250   int64_t intSz = sz.toInt64();
 251   if (intSz < 0) {
 252     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 253       "Parameter sz must be a non-negative integer"));
 254     throw e;
 255   }
 256   TypedValue* val = cvarToCell(&value);
 257   resize(intSz, val);
 258 }
 259
 260 Object c_Vector::t_clear() {
 261   ++m_version;
 262   uint sz = m_size;
 263   for (int i = 0; i < sz; ++i) {
 264     tvRefcountedDecRef(&m_data[i]);
 265   }
 266   smart_free(m_data);
 267   m_data = nullptr;
 268   m_size = 0;
 269   m_capacity = 0;
 270   return this;
 271 }
 272
 273 bool c_Vector::t_isempty() {
 274   return (m_size == 0);
 275 }
 276
 277 int64_t c_Vector::t_count() {
 278   return m_size;
 279 }
 280
 281 Object c_Vector::t_items() {
 282   return SystemLib::AllocIterableViewObject(this);
 283 }
 284
 285 Object c_Vector::t_keys() {
 286   c_Vector* vec;
 287   Object obj = vec = NEWOBJ(c_Vector)();
 288   vec->reserve(m_size);
 289   vec->m_size = m_size;
 290   for (uint i = 0; i < m_size; ++i) {
 291     vec->m_data[i].m_data.num = i;
 292     vec->m_data[i].m_type = KindOfInt64;
 293   }
 294   return obj;
 295 }
 296
 297 Object c_Vector::t_view() {
 298   return SystemLib::AllocKeyedIterableViewObject(this);
 299 }
 300
 301 Object c_Vector::t_kvzip() {
 302   c_Vector* vec;
 303   Object obj = vec = NEWOBJ(c_Vector)();
 304   vec->reserve(m_size);
 305   for (uint i = 0; i < m_size; ++i) {
 306     c_Pair* pair = NEWOBJ(c_Pair)();
 307     pair->incRefCount();
 308     pair->elm0.m_type = KindOfInt64;
 309     pair->elm0.m_data.num = i;
 310     ++pair->m_size;
 311     pair->add(&m_data[i]);
 312     vec->m_data[i].m_data.pobj = pair;
 313     vec->m_data[i].m_type = KindOfObject;
 314     ++vec->m_size;
 315   }
 316   return obj;
 317 }
 318
 319 Variant c_Vector::t_at(CVarRef key) {
 320   if (key.isInteger()) {
 321     return tvAsCVarRef(at(key.toInt64()));
 322   }
 323   throwBadKeyType();
 324   return uninit_null();
 325 }
 326
 327 Variant c_Vector::t_get(CVarRef key) {
 328   if (key.isInteger()) {
 329     TypedValue* tv = get(key.toInt64());
 330     if (tv) {
 331       return tvAsCVarRef(tv);
 332     } else {
 333       return uninit_null();
 334     }
 335   }
 336   throwBadKeyType();
 337   return uninit_null();
 338 }
 339
 340 bool c_Vector::t_contains(CVarRef key) {
 341   return t_containskey(key);
 342 }
 343
 344 bool c_Vector::t_containskey(CVarRef key) {
 345   if (key.isInteger()) {
 346     return contains(key.toInt64());
 347   }
 348   throwBadKeyType();
 349   return false;
 350 }
 351
 352 Object c_Vector::t_removekey(CVarRef key) {
 353   if (!key.isInteger()) {
 354     throwBadKeyType();
 355   }
 356   int64_t k = key.toInt64();
 357   if (!contains(k)) {
 358     return this;
 359   }
 360   uint64_t datum = m_data[k].m_data.num;
 361   DataType t = m_data[k].m_type;
 362   if (k+1 < m_size) {
 363     memmove(&m_data[k], &m_data[k+1],
 364             (m_size-(k+1)) * sizeof(TypedValue));
 365   }
 366   --m_size;
 367   tvRefcountedDecRefHelper(t, datum);
 368   return this;
 369 }
 370
 371 Array c_Vector::t_toarray() {
 372   return toArrayImpl();
 373 }
 374
 375 void c_Vector::t_sort(CVarRef col /* = null */) {
 376   raise_warning("Vector::sort() is deprecated, please use the builtin sort() "
 377                 "function or usort() function instead");
 378   // Terribly inefficient, but produces correct results for now
 379   Variant arr = t_toarray();
 380   if (col.isNull()) {
 381     f_sort(ref(arr));
 382   } else {
 383     if (!col.isObject()) {
 384       Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 385         "Expected col to be an instance of Collator"));
 386       throw e;
 387     }
 388     ObjectData* obj = col.getObjectData();
 389     if (!obj->instanceof(c_Collator::s_cls)) {
 390       Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 391         "Expected col to be an instance of Collator"));
 392       throw e;
 393     }
 394     auto collator = static_cast<c_Collator*>(obj);
 395     // TODO Task #1429976: What do we do if the Collator encountered errors
 396     // while sorting? How is this reported to the user?
 397     collator->t_sort(ref(arr));
 398   }
 399   if (!arr.isArray()) {
 400     assert(false);
 401     return;
 402   }
 403   ArrayData* ad = arr.getArrayData();
 404   int sz = ad->size();
 405   ssize_t pos = ad->iter_begin();
 406   for (int i = 0; i < sz; ++i, pos = ad->iter_advance(pos)) {
 407     assert(pos != ArrayData::invalid_index);
 408     tvAsVariant(&m_data[i]) = ad->getValue(pos);
 409   }
 410 }
 411
 412 void c_Vector::t_reverse() {
 413   if (m_size <= 1) return;
 414   TypedValue* start = m_data;
 415   TypedValue* end = m_data + m_size - 1;
 416   for (; start < end; ++start, --end) {
 417     std::swap(start->m_data.num, end->m_data.num);
 418     std::swap(start->m_type, end->m_type);
 419   }
 420 }
 421
 422 void c_Vector::t_splice(CVarRef offset, CVarRef len /* = null */,
 423                         CVarRef replacement /* = null */) {
 424   if (!offset.isInteger()) {
 425     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 426       "Parameter offset must be an integer"));
 427     throw e;
 428   }
 429   if (!len.isNull() && !len.isInteger()) {
 430     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 431       "Parameter len must be null or an integer"));
 432     throw e;
 433   }
 434   if (!replacement.isNull()) {
 435     Object e(SystemLib::AllocRuntimeExceptionObject(
 436       "Vector::splice does not support replacement parameter"));
 437     throw e;
 438   }
 439   int64_t sz = m_size;
 440   int64_t startPos = offset.toInt64();
 441   if (UNLIKELY(uint64_t(startPos) >= uint64_t(sz))) {
 442     if (startPos >= 0) {
 443       return;
 444     }
 445     startPos += sz;
 446     if (startPos < 0) {
 447       startPos = 0;
 448     }
 449   }
 450   int64_t endPos;
 451   if (len.isInteger()) {
 452     int64_t intLen = len.toInt64();
 453     if (LIKELY(intLen > 0)) {
 454       endPos = startPos + intLen;
 455       if (endPos > sz) {
 456         endPos = sz;
 457       }
 458     } else {
 459       if (intLen == 0) {
 460         return;
 461       }
 462       endPos = sz + intLen;
 463       if (endPos <= startPos) {
 464         return;
 465       }
 466     }
 467   } else {
 468     endPos = sz;
 469   }
 470   // Null out each element before decreffing it. We need to do this in case
 471   // a __destruct method reenters and accesses this Vector object.
 472   for (int64_t i = startPos; i < endPos; ++i) {
 473     uint64_t datum = m_data[i].m_data.num;
 474     DataType t = m_data[i].m_type;
 475     tvWriteNull(&m_data[i]);
 476     tvRefcountedDecRefHelper(t, datum);
 477   }
 478   // Move elements that came after the deleted elements (if there are any)
 479   if (endPos < sz) {
 480     memmove(&m_data[startPos], &m_data[endPos],
 481             (sz - endPos) * sizeof(TypedValue));
 482   }
 483   m_size -= (endPos - startPos);
 484 }
 485
 486 int64_t c_Vector::t_linearsearch(CVarRef search_value) {
 487   uint sz = m_size;
 488   for (uint i = 0; i < sz; ++i) {
 489     if (search_value.same(tvAsCVarRef(&m_data[i]))) {
 490       return i;
 491     }
 492   }
 493   return -1;
 494 }
 495
 496 void c_Vector::t_shuffle() {
 497   for (uint i = 1; i < m_size; ++i) {
 498     uint j = f_mt_rand(0, i);
 499     std::swap(m_data[i], m_data[j]);
 500   }
 501 }
 502
 503 Object c_Vector::t_getiterator() {
 504   c_VectorIterator* it = NEWOBJ(c_VectorIterator)();
 505   it->m_obj = this;
 506   it->m_pos = 0;
 507   it->m_version = getVersion();
 508   return it;
 509 }
 510
 511 Object c_Vector::t_map(CVarRef callback) {
 512   CallCtx ctx;
 513   vm_decode_function(callback, nullptr, false, ctx);
 514   if (!ctx.func) {
 515     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 516       "Parameter must be a valid callback"));
 517     throw e;
 518   }
 519   c_Vector* vec;
 520   Object obj = vec = NEWOBJ(c_Vector)();
 521   vec->reserve(m_size);
 522   for (uint i = 0; i < m_size; ++i) {
 523     TypedValue* tv = &vec->m_data[i];
 524     int32_t version = m_version;
 525     TypedValue args[1];
 526     tvDup(&m_data[i], args + 0);
 527     g_vmContext->invokeFuncFew(tv, ctx, 1, args);
 528     if (UNLIKELY(version != m_version)) {
 529       tvRefcountedDecRef(tv);
 530       throw_collection_modified();
 531     }
 532     ++vec->m_size;
 533   }
 534   return obj;
 535 }
 536
 537 Object c_Vector::t_filter(CVarRef callback) {
 538   CallCtx ctx;
 539   vm_decode_function(callback, nullptr, false, ctx);
 540   if (!ctx.func) {
 541     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 542       "Parameter must be a valid callback"));
 543     throw e;
 544   }
 545   c_Vector* vec;
 546   Object obj = vec = NEWOBJ(c_Vector)();
 547   for (uint i = 0; i < m_size; ++i) {
 548     Variant ret;
 549     int32_t version = m_version;
 550     TypedValue args[1];
 551     tvDup(&m_data[i], args + 0);
 552     g_vmContext->invokeFuncFew(ret.asTypedValue(), ctx, 1, args);
 553     if (UNLIKELY(version != m_version)) {
 554       throw_collection_modified();
 555     }
 556     if (ret.toBoolean()) {
 557       vec->add(&m_data[i]);
 558     }
 559   }
 560   return obj;
 561 }
 562
 563 Object c_Vector::t_zip(CVarRef iterable) {
 564   size_t sz;
 565   ArrayIter iter = getArrayIterHelper(iterable, sz);
 566   c_Vector* vec;
 567   Object obj = vec = NEWOBJ(c_Vector)();
 568   vec->reserve(std::min(sz, size_t(m_size)));
 569   for (uint i = 0; i < m_size && iter; ++i, ++iter) {
 570     Variant v = iter.second();
 571     if (vec->m_capacity <= vec->m_size) {
 572       vec->grow();
 573     }
 574     c_Pair* pair = NEWOBJ(c_Pair)();
 575     pair->incRefCount();
 576     pair->add(&m_data[i]);
 577     pair->add(cvarToCell(&v));
 578     vec->m_data[i].m_data.pobj = pair;
 579     vec->m_data[i].m_type = KindOfObject;
 580     ++vec->m_size;
 581   }
 582   return obj;
 583 }
 584
 585 Object c_Vector::t_set(CVarRef key, CVarRef value) {
 586   if (key.isInteger()) {
 587     TypedValue* tv = cvarToCell(&value);
 588     set(key.toInt64(), tv);
 589     return this;
 590   }
 591   throwBadKeyType();
 592   return this;
 593 }
 594
 595 Object c_Vector::t_setall(CVarRef iterable) {
 596   size_t sz;
 597   ArrayIter iter = getArrayIterHelper(iterable, sz);
 598   for (; iter; ++iter) {
 599     Variant k = iter.first();
 600     Variant v = iter.second();
 601     TypedValue* tvKey = cvarToCell(&k);
 602     TypedValue* tvVal = cvarToCell(&v);
 603     if (tvKey->m_type != KindOfInt64) {
 604       throwBadKeyType();
 605     }
 606     set(tvKey->m_data.num, tvVal);
 607   }
 608   return this;
 609 }
 610
 611 Object c_Vector::t_put(CVarRef key, CVarRef value) {
 612   return t_set(key, value);
 613 }
 614
 615 Object c_Vector::ti_fromitems(CVarRef iterable) {
 616   size_t sz;
 617   ArrayIter iter = getArrayIterHelper(iterable, sz);
 618   c_Vector* target;
 619   Object ret = target = NEWOBJ(c_Vector)();
 620   for (uint i = 0; iter; ++i, ++iter) {
 621     Variant v = iter.second();
 622     TypedValue* tv = tvToCell(v.asTypedValue());
 623     target->add(tv);
 624   }
 625   return ret;
 626 }
 627
 628 Object c_Vector::ti_fromarray(CVarRef arr) {
 629   if (!arr.isArray()) {
 630     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 631       "Parameter arr must be an array"));
 632     throw e;
 633   }
 634   c_Vector* target;
 635   Object ret = target = NEWOBJ(c_Vector)();
 636   ArrayData* ad = arr.getArrayData();
 637   uint sz = ad->size();
 638   target->m_capacity = target->m_size = sz;
 639   TypedValue* data;
 640   target->m_data = data = (TypedValue*)smart_malloc(sz * sizeof(TypedValue));
 641   ssize_t pos = ad->iter_begin();
 642   for (uint i = 0; i < sz; ++i, pos = ad->iter_advance(pos)) {
 643     assert(pos != ArrayData::invalid_index);
 644     TypedValue* tv = cvarToCell(&ad->getValueRef(pos));
 645     tvRefcountedIncRef(tv);
 646     data[i].m_data.num = tv->m_data.num;
 647     data[i].m_type = tv->m_type;
 648   }
 649   return ret;
 650 }
 651
 652 Object c_Vector::ti_fromvector(CVarRef vec) {
 653   if (!vec.isObject()) {
 654     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 655       "vec must be an instance of Vector"));
 656     throw e;
 657   }
 658   ObjectData* obj = vec.getObjectData();
 659   if (!obj->instanceof(c_Vector::s_cls)) {
 660     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 661       "vec must be an instance of Vector"));
 662     throw e;
 663   }
 664   auto v = static_cast<c_Vector*>(obj);
 665   c_Vector* target;
 666   Object ret = target = NEWOBJ(c_Vector)();
 667   uint sz = v->m_size;
 668   TypedValue* data;
 669   target->m_capacity = target->m_size = sz;
 670   target->m_data = data = (TypedValue*)smart_malloc(sz * sizeof(TypedValue));
 671   for (uint i = 0; i < sz; ++i) {
 672     tvDup(&v->m_data[i], &data[i]);
 673   }
 674   return ret;
 675 }
 676
 677 Variant c_Vector::ti_slice(CVarRef vec, CVarRef offset,
 678                            CVarRef len /* = null */) {
 679   if (!vec.isObject()) {
 680     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 681       "vec must be an instance of Vector"));
 682     throw e;
 683   }
 684   ObjectData* obj = vec.getObjectData();
 685   if (!obj->instanceof(c_Vector::s_cls)) {
 686     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 687       "vec must be an instance of Vector"));
 688     throw e;
 689   }
 690   if (!offset.isInteger()) {
 691     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 692       "Parameter offset must be an integer"));
 693     throw e;
 694   }
 695   if (!len.isNull() && !len.isInteger()) {
 696     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 697       "Parameter len must be null or an integer"));
 698     throw e;
 699   }
 700   c_Vector* target;
 701   Object ret = target = NEWOBJ(c_Vector)();
 702   auto v = static_cast<c_Vector*>(obj);
 703   int64_t sz = v->m_size;
 704   int64_t startPos = offset.toInt64();
 705   if (UNLIKELY(uint64_t(startPos) >= uint64_t(sz))) {
 706     if (startPos >= 0) {
 707       return ret;
 708     }
 709     startPos += sz;
 710     if (startPos < 0) {
 711       startPos = 0;
 712     }
 713   }
 714   int64_t endPos;
 715   if (len.isInteger()) {
 716     int64_t intLen = len.toInt64();
 717     if (LIKELY(intLen > 0)) {
 718       endPos = startPos + intLen;
 719       if (endPos > sz) {
 720         endPos = sz;
 721       }
 722     } else {
 723       if (intLen == 0) {
 724         return ret;
 725       }
 726       endPos = sz + intLen;
 727       if (endPos <= startPos) {
 728         return ret;
 729       }
 730     }
 731   } else {
 732     endPos = sz;
 733   }
 734   assert(startPos < endPos);
 735   uint targetSize = endPos - startPos;
 736   TypedValue* data;
 737   target->m_capacity = target->m_size = targetSize;
 738   target->m_data = data =
 739     (TypedValue*)smart_malloc(targetSize * sizeof(TypedValue));
 740   for (uint i = 0; i < targetSize; ++i, ++startPos) {
 741     tvDup(&v->m_data[startPos], &data[i]);
 742   }
 743   return ret;
 744 }
 745
 746 void c_Vector::throwOOB(int64_t key) {
 747   throwIntOOB(key, true);
 748 }
 749
 750 struct VectorValAccessor {
 751   typedef const TypedValue& ElmT;
 752   bool isInt(ElmT elm) const { return elm.m_type == KindOfInt64; }
 753   bool isStr(ElmT elm) const { return IS_STRING_TYPE(elm.m_type); }
 754   int64_t getInt(ElmT elm) const { return elm.m_data.num; }
 755   StringData* getStr(ElmT elm) const { return elm.m_data.pstr; }
 756   Variant getValue(ElmT elm) const { return tvAsCVarRef(&elm); }
 757 };
 758
 759 /**
 760  * preSort() does an initial pass over the array to do some preparatory work
 761  * before the sort algorithm runs. For sorts that use builtin comparators, the
 762  * types of values are also observed during this first pass. By observing the
 763  * types during this initial pass, we can often use a specialized comparator
 764  * and avoid performing type checks during the actual sort.
 765  */
 766 template <typename AccessorT>
 767 c_Vector::SortFlavor c_Vector::preSort(const AccessorT& acc) {
 768   assert(m_size > 0);
 769   uint sz = m_size;
 770   bool allInts = true;
 771   bool allStrs = true;
 772   for (uint i = 0; i < sz; ++i) {
 773     allInts = (allInts && acc.isInt(m_data[i]));
 774     allStrs = (allStrs && acc.isStr(m_data[i]));
 775   }
 776   return allStrs ? StringSort : allInts ? IntegerSort : GenericSort;
 777 }
 778
 779 #define SORT_CASE(flag, cmp_type, acc_type) \
 780   case flag: { \
 781     if (ascending) { \
 782       cmp_type##Compare<acc_type, flag, true> comp; \
 783       HPHP::Sort::sort(m_data, m_data + m_size, comp); \
 784     } else { \
 785       cmp_type##Compare<acc_type, flag, false> comp; \
 786       HPHP::Sort::sort(m_data, m_data + m_size, comp); \
 787     } \
 788     break; \
 789   }
 790 #define SORT_CASE_BLOCK(cmp_type, acc_type) \
 791   switch (sort_flags) { \
 792     default: /* fall through to SORT_REGULAR case */ \
 793     SORT_CASE(SORT_REGULAR, cmp_type, acc_type) \
 794     SORT_CASE(SORT_NUMERIC, cmp_type, acc_type) \
 795     SORT_CASE(SORT_STRING, cmp_type, acc_type) \
 796     SORT_CASE(SORT_LOCALE_STRING, cmp_type, acc_type) \
 797     SORT_CASE(SORT_NATURAL, cmp_type, acc_type) \
 798     SORT_CASE(SORT_NATURAL_CASE, cmp_type, acc_type) \
 799   }
 800 #define CALL_SORT(acc_type) \
 801   if (flav == StringSort) { \
 802     SORT_CASE_BLOCK(StrElm, acc_type) \
 803   } else if (flav == IntegerSort) { \
 804     SORT_CASE_BLOCK(IntElm, acc_type) \
 805   } else { \
 806     SORT_CASE_BLOCK(Elm, acc_type) \
 807   }
 808
 809 void c_Vector::sort(int sort_flags, bool ascending) {
 810   if (!m_size) {
 811     return;
 812   }
 813   SortFlavor flav = preSort<VectorValAccessor>(VectorValAccessor());
 814   CALL_SORT(VectorValAccessor);
 815 }
 816
 817 #undef SORT_CASE
 818 #undef SORT_CASE_BLOCK
 819 #undef CALL_SORT
 820
 821 void c_Vector::usort(CVarRef cmp_function) {
 822   if (!m_size) {
 823     return;
 824   }
 825   ElmUCompare<VectorValAccessor> comp;
 826   CallCtx ctx;
 827   Transl::CallerFrame cf;
 828   vm_decode_function(cmp_function, cf(), false, ctx);
 829   comp.ctx = &ctx;
 830   HPHP::Sort::sort(m_data, m_data + m_size, comp);
 831 }
 832
 833 void c_Vector::throwBadKeyType() {
 834   Object e(SystemLib::AllocInvalidArgumentExceptionObject(
 835     "Only integer keys may be used with Vectors"));
 836   throw e;
 837 }
 838
 839 TypedValue* c_Vector::OffsetGet(ObjectData* obj, TypedValue* key) {
 840   assert(key->m_type != KindOfRef);
 841   auto vec = static_cast<c_Vector*>(obj);
 842   if (key->m_type == KindOfInt64) {
 843     return vec->at(key->m_data.num);
 844   }
 845   throwBadKeyType();
 846   return nullptr;
 847 }
 848
 849 void c_Vector::OffsetSet(ObjectData* obj, TypedValue* key, TypedValue* val) {
 850   assert(key->m_type != KindOfRef);
 851   assert(val->m_type != KindOfRef);
 852   auto vec = static_cast<c_Vector*>(obj);
 853   if (key->m_type == KindOfInt64) {
 854     vec->set(key->m_data.num, val);
 855     return;
 856   }
 857   throwBadKeyType();
 858 }
 859
 860 bool c_Vector::OffsetIsset(ObjectData* obj, TypedValue* key) {
 861   assert(key->m_type != KindOfRef);
 862   auto vec = static_cast<c_Vector*>(obj);
 863   TypedValue* result;
 864   if (key->m_type == KindOfInt64) {
 865     result = vec->get(key->m_data.num);
 866   } else {
 867     throwBadKeyType();
 868     result = nullptr;
 869   }
 870   return result ? isset(tvAsCVarRef(result)) : false;
 871 }
 872
 873 bool c_Vector::OffsetEmpty(ObjectData* obj, TypedValue* key) {
 874   assert(key->m_type != KindOfRef);
 875   auto vec = static_cast<c_Vector*>(obj);
 876   TypedValue* result;
 877   if (key->m_type == KindOfInt64) {
 878     result = vec->get(key->m_data.num);
 879   } else {
 880     throwBadKeyType();
 881     result = nullptr;
 882   }
 883   return result ? empty(tvAsCVarRef(result)) : true;
 884 }
 885
 886 bool c_Vector::OffsetContains(ObjectData* obj, TypedValue* key) {
 887   assert(key->m_type != KindOfRef);
 888   auto vec = static_cast<c_Vector*>(obj);
 889   if (key->m_type == KindOfInt64) {
 890     return vec->contains(key->m_data.num);
 891   } else {
 892     throwBadKeyType();
 893     return false;
 894   }
 895 }
 896
 897 void c_Vector::OffsetAppend(ObjectData* obj, TypedValue* val) {
 898   assert(val->m_type != KindOfRef);
 899   auto vec = static_cast<c_Vector*>(obj);
 900   vec->add(val);
 901 }
 902
 903 void c_Vector::OffsetUnset(ObjectData* obj, TypedValue* key) {
 904   Object e(SystemLib::AllocRuntimeExceptionObject(
 905     "Cannot unset element of a Vector"));
 906   throw e;
 907 }
 908
 909 bool c_Vector::Equals(ObjectData* obj1, ObjectData* obj2) {
 910   auto vec1 = static_cast<c_Vector*>(obj1);
 911   auto vec2 = static_cast<c_Vector*>(obj2);
 912   uint sz = vec1->m_size;
 913   if (sz != vec2->m_size) {
 914     return false;
 915   }
 916   for (uint i = 0; i < sz; ++i) {
 917     if (!equal(tvAsCVarRef(&vec1->m_data[i]),
 918                tvAsCVarRef(&vec2->m_data[i]))) {
 919       return false;
 920     }
 921   }
 922   return true;
 923 }
 924
 925 void c_Vector::Unserialize(ObjectData* obj,
 926                            VariableUnserializer* uns,
 927                            int64_t sz,
 928                            char type) {
 929   if (type != 'V') {
 930     throw Exception("Vector does not support the '%c' serialization "
 931                     "format", type);
 932   }
 933   auto vec = static_cast<c_Vector*>(obj);
 934   vec->reserve(sz);
 935   for (int64_t i = 0; i < sz; ++i) {
 936     auto tv = &vec->m_data[vec->m_size];
 937     tv->m_type = KindOfNull;
 938     ++vec->m_size;
 939     tvAsVariant(tv).unserialize(uns, Uns::ColValueMode);
 940   }
 941 }
 942
 943 c_VectorIterator::c_VectorIterator(Class* cb) :
 944     ExtObjectData(cb) {
 945 }
 946
 947 c_VectorIterator::~c_VectorIterator() {
 948 }
 949
 950 void c_VectorIterator::t___construct() {
 951 }
 952
 953 Variant c_VectorIterator::t_current() {
 954   c_Vector* vec = m_obj.get();
 955   if (UNLIKELY(m_version != vec->getVersion())) {
 956     throw_collection_modified();
 957   }
 958   if (!vec->contains(m_pos)) {
 959     throw_iterator_not_valid();
 960   }
 961   return tvAsCVarRef(&vec->m_data[m_pos]);
 962 }
 963
 964 Variant c_VectorIterator::t_key() {
 965   c_Vector* vec = m_obj.get();
 966   if (!vec->contains(m_pos)) {
 967     throw_iterator_not_valid();
 968   }
 969   return m_pos;
 970 }
 971
 972 bool c_VectorIterator::t_valid() {
 973   assert(m_pos >= 0);
 974   c_Vector* vec = m_obj.get();
 975   return vec && (m_pos < (ssize_t)vec->m_size);
 976 }
 977
 978 void c_VectorIterator::t_next() {
 979   m_pos++;
 980 }
 981
 982 void c_VectorIterator::t_rewind() {
 983   m_pos = 0;
 984 }
 985
 986 ///////////////////////////////////////////////////////////////////////////////
 987
 988 static const char emptyMapSlot[sizeof(c_Map::Bucket)] = { 0 };
 989
 990 c_Map::c_Map(Class* cb) :
 991     ExtObjectDataFlags<ObjectData::MapAttrInit|
 992                        ObjectData::UseGet|
 993                        ObjectData::UseSet|
 994                        ObjectData::UseIsset|
 995                        ObjectData::UseUnset>(cb),
 996     m_size(0), m_load(0), m_nLastSlot(0), m_version(0) {
 997   m_data = (Bucket*)emptyMapSlot;
 998 }
 999
1000 c_Map::~c_Map() {
1001   deleteBuckets();
1002   freeData();
1003 }
1004
1005 void c_Map::freeData() {
1006   if (m_data != (Bucket*)emptyMapSlot) {
1007     smart_free(m_data);
1008   }
1009   m_data = (Bucket*)emptyMapSlot;
1010 }
1011
1012 void c_Map::deleteBuckets() {
1013   if (!m_size) return;
1014   for (uint i = 0; i <= m_nLastSlot; ++i) {
1015     Bucket& p = m_data[i];
1016     if (p.validValue()) {
1017       tvRefcountedDecRef(&p.data);
1018       if (p.hasStrKey() && p.skey->decRefCount() == 0) {
1019         DELETE(StringData)(p.skey);
1020       }
1021     }
1022   }
1023 }
1024
1025 void c_Map::t___construct(CVarRef iterable /* = null_variant */) {
1026   if (!iterable.isInitialized()) {
1027     return;
1028   }
1029   size_t sz;
1030   ArrayIter iter = getArrayIterHelper(iterable, sz);
1031   if (sz) {
1032     reserve(sz);
1033   }
1034   for (; iter; ++iter) {
1035     Variant k = iter.first();
1036     Variant v = iter.second();
1037     TypedValue* tv = tvToCell(v.asTypedValue());
1038     if (k.isInteger()) {
1039       update(k.toInt64(), tv);
1040     } else if (k.isString()) {
1041       update(k.getStringData(), tv);
1042     } else {
1043       throwBadKeyType();
1044     }
1045   }
1046 }
1047
1048 Array c_Map::toArrayImpl() const {
1049   ArrayInit ai(m_size);
1050   for (uint i = 0; i <= m_nLastSlot; ++i) {
1051     Bucket& p = m_data[i];
1052     if (p.validValue()) {
1053       if (p.hasIntKey()) {
1054         ai.set((int64_t)p.ikey, tvAsCVarRef(&p.data));
1055       } else {
1056         ai.set(*(const String*)(&p.skey), tvAsCVarRef(&p.data));
1057       }
1058     }
1059   }
1060   return ai.create();
1061 }
1062
1063 Array c_Map::o_toArray() const {
1064   check_collection_cast_to_array();
1065   return toArrayImpl();
1066 }
1067
1068 ObjectData* c_Map::clone() {
1069   ObjectData* obj = ObjectData::clone();
1070   auto target = static_cast<c_Map*>(obj);
1071
1072   if (!m_size) return obj;
1073
1074   assert(m_nLastSlot != 0);
1075   target->m_size = m_size;
1076   target->m_load = m_load;
1077   target->m_nLastSlot = m_nLastSlot;
1078   target->m_data = (Bucket*)smart_malloc(numSlots() * sizeof(Bucket));
1079   memcpy(target->m_data, m_data, numSlots() * sizeof(Bucket));
1080
1081   for (uint i = 0; i <= m_nLastSlot; ++i) {
1082     Bucket& p = m_data[i];
1083     if (p.validValue()) {
1084       tvRefcountedIncRef(&p.data);
1085       if (p.hasStrKey()) {
1086         p.skey->incRefCount();
1087       }
1088     }
1089   }
1090
1091   return obj;
1092 }
1093
1094 Object c_Map::t_add(CVarRef val) {
1095   TypedValue* tv = cvarToCell(&val);
1096   add(tv);
1097   return this;
1098 }
1099
1100 Object c_Map::t_addall(CVarRef iterable) {
1101   size_t sz;
1102   ArrayIter iter = getArrayIterHelper(iterable, sz);
1103   reserve(std::max(sz, size_t(m_size)));
1104   for (; iter; ++iter) {
1105     Variant v = iter.second();
1106     TypedValue* tv = cvarToCell(&v);
1107     add(tv);
1108   }
1109   return this;
1110 }
1111
1112 Object c_Map::t_clear() {
1113   deleteBuckets();
1114   freeData();
1115   m_size = 0;
1116   m_load = 0;
1117   m_nLastSlot = 0;
1118   m_data = (Bucket*)emptyMapSlot;
1119   return this;
1120 }
1121
1122 bool c_Map::t_isempty() {
1123   return (m_size == 0);
1124 }
1125
1126 int64_t c_Map::t_count() {
1127   return m_size;
1128 }
1129
1130 Object c_Map::t_items() {
1131   return SystemLib::AllocKVZippedIterableObject(this);
1132 }
1133
1134 Object c_Map::t_keys() {
1135   c_Vector* vec;
1136   Object obj = vec = NEWOBJ(c_Vector)();
1137   vec->reserve(m_size);
1138   for (uint i = 0, j = 0; i <= m_nLastSlot; ++i) {
1139     Bucket& p = m_data[i];
1140     if (!p.validValue()) continue;
1141     if (p.hasIntKey()) {
1142       vec->m_data[j].m_data.num = p.ikey;
1143       vec->m_data[j].m_type = KindOfInt64;
1144     } else {
1145       p.skey->incRefCount();
1146       vec->m_data[j].m_data.pstr = p.skey;
1147       vec->m_data[j].m_type = KindOfString;
1148     }
1149     ++vec->m_size;
1150     ++j;
1151   }
1152   return obj;
1153 }
1154
1155 Object c_Map::t_view() {
1156   return SystemLib::AllocKeyedIterableViewObject(this);
1157 }
1158
1159 Object c_Map::t_kvzip() {
1160   c_Vector* vec;
1161   Object obj = vec = NEWOBJ(c_Vector)();
1162   vec->reserve(m_size);
1163   for (uint i = 0, j = 0; i <= m_nLastSlot; ++i) {
1164     Bucket& p = m_data[i];
1165     if (!p.validValue()) continue;
1166     c_Pair* pair = NEWOBJ(c_Pair)();
1167     pair->incRefCount();
1168     if (p.hasIntKey()) {
1169       pair->elm0.m_data.num = p.ikey;
1170       pair->elm0.m_type = KindOfInt64;
1171     } else {
1172       p.skey->incRefCount();
1173       pair->elm0.m_data.pstr = p.skey;
1174       pair->elm0.m_type = KindOfString;
1175     }
1176     ++pair->m_size;
1177     pair->add(&p.data);
1178     vec->m_data[j].m_data.pobj = pair;
1179     vec->m_data[j].m_type = KindOfObject;
1180     ++vec->m_size;
1181     ++j;
1182   }
1183   return obj;
1184 }
1185
1186 Variant c_Map::t_at(CVarRef key) {
1187   if (key.isInteger()) {
1188     return tvAsCVarRef(at(key.toInt64()));
1189   } else if (key.isString()) {
1190     return tvAsCVarRef(at(key.getStringData()));
1191   }
1192   throwBadKeyType();
1193   return uninit_null();
1194 }
1195
1196 Variant c_Map::t_get(CVarRef key) {
1197   if (key.isInteger()) {
1198     TypedValue* tv = get(key.toInt64());
1199     if (tv) {
1200       return tvAsCVarRef(tv);
1201     } else {
1202       return uninit_null();
1203     }
1204   } else if (key.isString()) {
1205     TypedValue* tv = get(key.getStringData());
1206     if (tv) {
1207       return tvAsCVarRef(tv);
1208     } else {
1209       return uninit_null();
1210     }
1211   }
1212   throwBadKeyType();
1213   return uninit_null();
1214 }
1215
1216 Object c_Map::t_set(CVarRef key, CVarRef value) {
1217   TypedValue* val = cvarToCell(&value);
1218   if (key.isInteger()) {
1219     update(key.toInt64(), val);
1220   } else if (key.isString()) {
1221     update(key.getStringData(), val);
1222   } else {
1223     throwBadKeyType();
1224   }
1225   return this;
1226 }
1227
1228 Object c_Map::t_setall(CVarRef iterable) {
1229   size_t sz;
1230   ArrayIter iter = getArrayIterHelper(iterable, sz);
1231   for (; iter; ++iter) {
1232     Variant k = iter.first();
1233     Variant v = iter.second();
1234     TypedValue* tvKey = cvarToCell(&k);
1235     TypedValue* tvVal = cvarToCell(&v);
1236     if (tvKey->m_type == KindOfInt64) {
1237       set(tvKey->m_data.num, tvVal);
1238     } else if (IS_STRING_TYPE(tvKey->m_type)) {
1239       set(tvKey->m_data.pstr, tvVal);
1240     } else {
1241       throwBadKeyType();
1242     }
1243   }
1244   return this;
1245 }
1246
1247 Object c_Map::t_put(CVarRef key, CVarRef value) {
1248   return t_set(key, value);
1249 }
1250
1251 bool c_Map::t_contains(CVarRef key) {
1252   DataType t = key.getType();
1253   if (t == KindOfInt64) {
1254     return contains(key.toInt64());
1255   }
1256   if (IS_STRING_TYPE(t)) {
1257     return contains(key.getStringData());
1258   }
1259   throwBadKeyType();
1260   return false;
1261 }
1262
1263 bool c_Map::t_containskey(CVarRef key) {
1264   return t_contains(key);
1265 }
1266
1267 Object c_Map::t_remove(CVarRef key) {
1268   DataType t = key.getType();
1269   if (t == KindOfInt64) {
1270     remove(key.toInt64());
1271   } else if (IS_STRING_TYPE(t)) {
1272     remove(key.getStringData());
1273   } else {
1274     throwBadKeyType();
1275   }
1276   return this;
1277 }
1278
1279 Object c_Map::t_removekey(CVarRef key) {
1280   return t_remove(key);
1281 }
1282
1283 Object c_Map::t_discard(CVarRef key) {
1284   return t_remove(key);
1285 }
1286
1287 Array c_Map::t_toarray() {
1288   return toArrayImpl();
1289 }
1290
1291 Array c_Map::t_copyasarray() {
1292   return toArrayImpl();
1293 }
1294
1295 Array c_Map::t_tokeysarray() {
1296   ArrayInit ai(m_size, ArrayInit::vectorInit);
1297   for (uint i = 0; i <= m_nLastSlot; ++i) {
1298     Bucket& p = m_data[i];
1299     if (!p.validValue()) continue;
1300     if (p.hasIntKey()) {
1301       ai.set((int64_t)p.ikey);
1302     } else {
1303       ai.set(*(const String*)(&p.skey));
1304     }
1305   }
1306   return ai.create();
1307 }
1308
1309 Object c_Map::t_values() {
1310   c_Vector* target;
1311   Object ret = target = NEWOBJ(c_Vector)();
1312   int64_t sz = m_size;
1313   if (!sz) {
1314     return ret;
1315   }
1316   TypedValue* data;
1317   target->m_capacity = target->m_size = m_size;
1318   target->m_data = data = (TypedValue*)smart_malloc(sz * sizeof(TypedValue));
1319
1320   int64_t j = 0;
1321   for (uint i = 0; i <= m_nLastSlot; ++i) {
1322     Bucket& p = m_data[i];
1323     if (!p.validValue()) continue;
1324     TypedValue* tv = &p.data;
1325     tvRefcountedIncRef(tv);
1326     data[j].m_data.num = tv->m_data.num;
1327     data[j].m_type = tv->m_type;
1328     ++j;
1329   }
1330   return ret;
1331 }
1332
1333 Array c_Map::t_tovaluesarray() {
1334   ArrayInit ai(m_size, ArrayInit::vectorInit);
1335   for (uint i = 0; i <= m_nLastSlot; ++i) {
1336     Bucket& p = m_data[i];
1337     if (!p.validValue()) continue;
1338     ai.set(tvAsCVarRef(&p.data));
1339   }
1340   return ai.create();
1341 }
1342
1343 Object c_Map::t_updatefromarray(CVarRef arr) {
1344   if (!arr.isArray()) {
1345     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
1346       "Expected arr to be an array"));
1347     throw e;
1348   }
1349   ArrayData* ad = arr.getArrayData();
1350   for (ssize_t pos = ad->iter_begin(); pos != ArrayData::invalid_index;
1351        pos = ad->iter_advance(pos)) {
1352     Variant k = ad->getKey(pos);
1353     TypedValue* tv = cvarToCell(&ad->getValueRef(pos));
1354     if (k.isInteger()) {
1355       update(k.toInt64(), tv);
1356     } else {
1357       assert(k.isString());
1358       update(k.getStringData(), tv);
1359     }
1360   }
1361   return this;
1362 }
1363
1364 Object c_Map::t_updatefromiterable(CVarRef it) {
1365   if (!it.isObject()) {
1366     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
1367       "Parameter it must be an instance of Iterable"));
1368     throw e;
1369   }
1370   ObjectData* obj = it.getObjectData();
1371   if (obj->getCollectionType() == Collection::MapType) {
1372     auto mp = static_cast<c_Map*>(obj);
1373     for (uint i = 0; i <= mp->m_nLastSlot; ++i) {
1374       c_Map::Bucket& p = mp->m_data[i];
1375       if (!p.validValue()) continue;
1376       if (p.hasIntKey()) {
1377         update((int64_t)p.ikey, &p.data);
1378       } else {
1379         update(p.skey, &p.data);
1380       }
1381     }
1382     return this;
1383   }
1384   for (ArrayIter iter = obj->begin(); iter; ++iter) {
1385     Variant k = iter.first();
1386     Variant v = iter.second();
1387     TypedValue* tv = tvToCell(v.asTypedValue());
1388     if (k.isInteger()) {
1389       update(k.toInt64(), tv);
1390     } else {
1391       assert(k.isString());
1392       update(k.getStringData(), tv);
1393     }
1394   }
1395   return this;
1396 }
1397
1398 Object c_Map::t_differencebykey(CVarRef it) {
1399   if (!it.isObject()) {
1400     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
1401       "Parameter it must be an instance of Iterable"));
1402     throw e;
1403   }
1404   ObjectData* obj = it.getObjectData();
1405   c_Map* target;
1406   Object ret = target = static_cast<c_Map*>(clone());
1407   if (obj->getCollectionType() == Collection::MapType) {
1408     auto mp = static_cast<c_Map*>(obj);
1409     for (uint i = 0; i <= mp->m_nLastSlot; ++i) {
1410       c_Map::Bucket& p = mp->m_data[i];
1411       if (!p.validValue()) continue;
1412       if (p.hasIntKey()) {
1413         target->remove((int64_t)p.ikey);
1414       } else {
1415         target->remove(p.skey);
1416       }
1417     }
1418     return ret;
1419   }
1420   for (ArrayIter iter = obj->begin(); iter; ++iter) {
1421     Variant k = iter.first();
1422     if (k.isInteger()) {
1423       target->remove(k.toInt64());
1424     } else {
1425       assert(k.isString());
1426       target->remove(k.getStringData());
1427     }
1428   }
1429   return ret;
1430 }
1431
1432 Object c_Map::t_getiterator() {
1433   c_MapIterator* it = NEWOBJ(c_MapIterator)();
1434   it->m_obj = this;
1435   it->m_pos = iter_begin();
1436   it->m_version = getVersion();
1437   return it;
1438 }
1439
1440 Object c_Map::t_map(CVarRef callback) {
1441   CallCtx ctx;
1442   vm_decode_function(callback, nullptr, false, ctx);
1443   if (!ctx.func) {
1444     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
1445       "Parameter must be a valid callback"));
1446     throw e;
1447   }
1448   c_Map* mp;
1449   Object obj = mp = NEWOBJ(c_Map)();
1450   if (!m_size) return obj;
1451   assert(m_nLastSlot != 0);
1452   mp->m_size = m_size;
1453   mp->m_load = m_load;
1454   mp->m_nLastSlot = 0;
1455   mp->m_data = (Bucket*)smart_malloc(numSlots() * sizeof(Bucket));
1456   // We need to zero out the first slot in case an exception
1457   // is thrown during the first iteration, because ~c_Map()
1458   // will decRef all slots up to (and including) m_nLastSlot.
1459   mp->m_data[0].data.m_type = (DataType)0;
1460   for (uint i = 0; i <= m_nLastSlot; mp->m_nLastSlot = i++) {
1461     Bucket& p = m_data[i];
1462     Bucket& np = mp->m_data[i];
1463     if (!p.validValue()) {
1464       np.data.m_type = p.data.m_type;
1465       continue;
1466     }
1467     TypedValue* tv = &np.data;
1468     int32_t version = m_version;
1469     TypedValue args[1];
1470     tvDup(&p.data, args + 0);
1471     g_vmContext->invokeFuncFew(tv, ctx, 1, args);
1472     if (UNLIKELY(version != m_version)) {
1473       tvRefcountedDecRef(tv);
1474       throw_collection_modified();
1475     }
1476     if (p.hasStrKey()) {
1477       p.skey->incRefCount();
1478     }
1479     np.ikey = p.ikey;
1480     np.data.hash() = p.data.hash();
1481   }
1482   return obj;
1483 }
1484
1485 Object c_Map::t_filter(CVarRef callback) {
1486   CallCtx ctx;
1487   vm_decode_function(callback, nullptr, false, ctx);
1488   if (!ctx.func) {
1489     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
1490       "Parameter must be a valid callback"));
1491     throw e;
1492   }
1493   c_Map* mp;
1494   Object obj = mp = NEWOBJ(c_Map)();
1495   if (!m_size) return obj;
1496   for (uint i = 0; i <= m_nLastSlot; ++i) {
1497     Bucket& p = m_data[i];
1498     if (!p.validValue()) continue;
1499     Variant ret;
1500     int32_t version = m_version;
1501     TypedValue args[1];
1502     tvDup(&p.data, args + 0);
1503     g_vmContext->invokeFuncFew(ret.asTypedValue(), ctx, 1, args);
1504     if (UNLIKELY(version != m_version)) {
1505       throw_collection_modified();
1506     }
1507     if (!ret.toBoolean()) continue;
1508     if (p.hasIntKey()) {
1509       mp->update(p.ikey, &p.data);
1510     } else {
1511       mp->update(p.skey, &p.data);
1512     }
1513   }
1514   return obj;
1515 }
1516
1517 Object c_Map::t_zip(CVarRef iterable) {
1518   size_t sz;
1519   ArrayIter iter = getArrayIterHelper(iterable, sz);
1520   c_Map* mp;
1521   Object obj = mp = NEWOBJ(c_Map)();
1522   mp->reserve(std::min(sz, size_t(m_size)));
1523   for (uint i = 0; i <= m_nLastSlot && iter; ++i) {
1524     Bucket& p = m_data[i];
1525     if (!p.validValue()) continue;
1526     Variant v = iter.second();
1527     c_Pair* pair;
1528     Object pairObj = pair = NEWOBJ(c_Pair)();
1529     pair->add(&p.data);
1530     pair->add(cvarToCell(&v));
1531     TypedValue tv;
1532     tv.m_data.pobj = pair;
1533     tv.m_type = KindOfObject;
1534     if (p.hasIntKey()) {
1535       mp->update(p.ikey, &tv);
1536     } else {
1537       mp->update(p.skey, &tv);
1538     }
1539     ++iter;
1540   }
1541   return obj;
1542 }
1543
1544 Object c_Map::ti_fromitems(CVarRef iterable) {
1545   size_t sz;
1546   ArrayIter iter = getArrayIterHelper(iterable, sz);
1547   c_Map* target;
1548   Object ret = target = NEWOBJ(c_Map)();
1549   if (sz) {
1550     target->reserve(sz);
1551   }
1552   for (; iter; ++iter) {
1553     Variant v = iter.second();
1554     TypedValue* tv = tvToCell(v.asTypedValue());
1555     if (UNLIKELY(tv->m_type != KindOfObject ||
1556                  !tv->m_data.pobj->instanceof(c_Pair::s_cls))) {
1557       Object e(SystemLib::AllocInvalidArgumentExceptionObject(
1558         "Parameter must be an instance of Iterable<Pair>"));
1559       throw e;
1560     }
1561     auto pair = static_cast<c_Pair*>(tv->m_data.pobj);
1562     TypedValue* tvKey = &pair->elm0;
1563     TypedValue* tvValue = &pair->elm1;
1564     assert(tvKey->m_type != KindOfRef);
1565     assert(tvValue->m_type != KindOfRef);
1566     if (tvKey->m_type == KindOfInt64) {
1567       target->update(tvKey->m_data.num, tvValue);
1568     } else if (IS_STRING_TYPE(tvKey->m_type)) {
1569       target->update(tvKey->m_data.pstr, tvValue);
1570     } else {
1571       throwBadKeyType();
1572     }
1573   }
1574   return ret;
1575 }
1576
1577 Object c_Map::ti_fromarray(CVarRef arr) {
1578   if (!arr.isArray()) {
1579     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
1580       "Parameter arr must be an array"));
1581     throw e;
1582   }
1583   c_Map* mp;
1584   Object ret = mp = NEWOBJ(c_Map)();
1585   ArrayData* ad = arr.getArrayData();
1586   for (ssize_t pos = ad->iter_begin(); pos != ArrayData::invalid_index;
1587        pos = ad->iter_advance(pos)) {
1588     Variant k = ad->getKey(pos);
1589     TypedValue* tv = cvarToCell(&ad->getValueRef(pos));
1590     if (k.isInteger()) {
1591       mp->update(k.toInt64(), tv);
1592     } else {
1593       assert(k.isString());
1594       mp->update(k.getStringData(), tv);
1595     }
1596   }
1597   return ret;
1598 }
1599
1600 Object c_Map::ti_fromiterable(CVarRef it) {
1601   if (!it.isObject()) {
1602     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
1603       "Parameter it must be an instance of Iterable"));
1604     throw e;
1605   }
1606   ObjectData* obj = it.getObjectData();
1607   Object ret;
1608   if (obj->getCollectionType() == Collection::MapType) {
1609     ret = obj->clone();
1610     return ret;
1611   }
1612   c_Map* target;
1613   ret = target = NEWOBJ(c_Map)();
1614   for (ArrayIter iter = obj->begin(); iter; ++iter) {
1615     Variant k = iter.first();
1616     Variant v = iter.second();
1617     TypedValue* tv = cvarToCell(&v);
1618     if (k.isInteger()) {
1619       target->update(k.toInt64(), tv);
1620     } else {
1621       assert(k.isString());
1622       target->update(k.getStringData(), tv);
1623     }
1624   }
1625   return ret;
1626 }
1627
1628 void c_Map::throwOOB(int64_t key) {
1629   throwIntOOB(key);
1630 }
1631
1632 void c_Map::throwOOB(StringData* key) {
1633   throwStrOOB(key);
1634 }
1635
1636 void c_Map::add(TypedValue* val) {
1637   if (UNLIKELY(val->m_type != KindOfObject ||
1638                !val->m_data.pobj->instanceof(c_Pair::s_cls))) {
1639     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
1640       "Parameter must be an instance of Pair"));
1641     throw e;
1642   }
1643   auto pair = static_cast<c_Pair*>(val->m_data.pobj);
1644   TypedValue* tvKey = &pair->elm0;
1645   TypedValue* tvValue = &pair->elm1;
1646   assert(tvKey->m_type != KindOfRef);
1647   assert(tvValue->m_type != KindOfRef);
1648   if (tvKey->m_type == KindOfInt64) {
1649     update(tvKey->m_data.num, tvValue);
1650   } else if (IS_STRING_TYPE(tvKey->m_type)) {
1651     update(tvKey->m_data.pstr, tvValue);
1652   } else {
1653     throwBadKeyType();
1654   }
1655 }
1656
1657 #define STRING_HASH(x)   (int32_t(x) | 0x80000000)
1658
1659 bool inline hitStringKey(const c_Map::Bucket* p, const char* k,
1660                          int len, int32_t hash) ALWAYS_INLINE;
1661 bool inline hitStringKey(const c_Map::Bucket* p, const char* k,
1662                   int len, int32_t hash) {
1663   assert(p->validValue());
1664   if (p->hasIntKey()) return false;
1665   const char* data = p->skey->data();
1666   return data == k || (p->hash() == hash &&
1667                        p->skey->size() == len &&
1668                        memcmp(data, k, len) == 0);
1669 }
1670
1671 bool inline hitIntKey(const c_Map::Bucket* p, int64_t ki) ALWAYS_INLINE;
1672 bool inline hitIntKey(const c_Map::Bucket* p, int64_t ki) {
1673   assert(p->validValue());
1674   return p->ikey == ki && p->hasIntKey();
1675 }
1676
1677 #define FIND_BODY(h0, hit) \
1678   size_t tableMask = m_nLastSlot; \
1679   size_t probeIndex = size_t(h0) & tableMask; \
1680   Bucket* p = fetchBucket(probeIndex); \
1681   if (LIKELY(p->validValue() && (hit))) { \
1682     return p; \
1683   } \
1684   if (LIKELY(p->empty())) { \
1685     return nullptr; \
1686   } \
1687   for (size_t i = 1;; ++i) { \
1688     assert(i <= tableMask); \
1689     probeIndex = (probeIndex + i) & tableMask; \
1690     assert(((size_t(h0)+((i + i*i) >> 1)) & tableMask) == probeIndex); \
1691     p = fetchBucket(probeIndex); \
1692     if (p->validValue() && (hit)) { \
1693       return p; \
1694     } \
1695     if (p->empty()) { \
1696       return nullptr; \
1697     } \
1698   }
1699
1700 #define FIND_FOR_INSERT_BODY(h0, hit) \
1701   size_t tableMask = m_nLastSlot; \
1702   size_t probeIndex = size_t(h0) & tableMask; \
1703   Bucket* p = fetchBucket(h0 & tableMask); \
1704   if (LIKELY((p->validValue() && (hit)) || \
1705              p->empty())) { \
1706     return p; \
1707   } \
1708   Bucket* ts = nullptr; \
1709   for (size_t i = 1;; ++i) { \
1710     if (UNLIKELY(p->tombstone() && !ts)) { \
1711       ts = p; \
1712     } \
1713     assert(i <= tableMask); \
1714     probeIndex = (probeIndex + i) & tableMask; \
1715     assert(((size_t(h0)+((i + i*i) >> 1)) & tableMask) == probeIndex); \
1716     p = fetchBucket(probeIndex); \
1717     if (LIKELY(p->validValue() && (hit))) { \
1718       return p; \
1719     } \
1720     if (LIKELY(p->empty())) { \
1721       if (LIKELY(!ts)) { \
1722         return p; \
1723       } \
1724       return ts; \
1725     } \
1726   }
1727
1728 c_Map::Bucket* c_Map::find(int64_t h) const {
1729   FIND_BODY(h, hitIntKey(p, h));
1730 }
1731
1732 c_Map::Bucket* c_Map::find(const char* k, int len, strhash_t prehash) const {
1733   FIND_BODY(prehash, hitStringKey(p, k, len, STRING_HASH(prehash)));
1734 }
1735
1736 c_Map::Bucket* c_Map::findForInsert(int64_t h) const {
1737   FIND_FOR_INSERT_BODY(h, hitIntKey(p, h));
1738 }
1739
1740 c_Map::Bucket* c_Map::findForInsert(const char* k, int len,
1741                                     strhash_t prehash) const {
1742   FIND_FOR_INSERT_BODY(prehash, hitStringKey(p, k, len, STRING_HASH(prehash)));
1743 }
1744
1745 // findForNewInsert() is only safe to use if you know for sure that the
1746 // key is not already present in the Map.
1747 inline ALWAYS_INLINE
1748 c_Map::Bucket* c_Map::findForNewInsert(size_t h0) const {
1749   size_t tableMask = m_nLastSlot;
1750   size_t probeIndex = h0 & tableMask;
1751   Bucket* p = fetchBucket(probeIndex);
1752   if (LIKELY(p->empty())) {
1753     return p;
1754   }
1755   for (size_t i = 1;; ++i) {
1756     assert(i <= tableMask);
1757     probeIndex = (probeIndex + i) & tableMask;
1758     assert(((size_t(h0)+((i + i*i) >> 1)) & tableMask) == probeIndex);
1759     p = fetchBucket(probeIndex);
1760     if (LIKELY(p->empty())) {
1761       return p;
1762     }
1763   }
1764 }
1765
1766 #undef STRING_HASH
1767 #undef FIND_BODY
1768 #undef FIND_FOR_INSERT_BODY
1769
1770 bool c_Map::update(int64_t h, TypedValue* data) {
1771   assert(data->m_type != KindOfRef);
1772   Bucket* p = findForInsert(h);
1773   assert(p);
1774   if (p->validValue()) {
1775     tvRefcountedIncRef(data);
1776     tvRefcountedDecRef(&p->data);
1777     p->data.m_data.num = data->m_data.num;
1778     p->data.m_type = data->m_type;
1779     return true;
1780   }
1781   ++m_version;
1782   ++m_size;
1783   if (!p->tombstone()) {
1784     if (UNLIKELY(++m_load >= computeMaxLoad())) {
1785       adjustCapacity();
1786       p = findForInsert(h);
1787       assert(p);
1788     }
1789   }
1790   tvRefcountedIncRef(data);
1791   p->data.m_data.num = data->m_data.num;
1792   p->data.m_type = data->m_type;
1793   p->setIntKey(h);
1794   return true;
1795 }
1796
1797 bool c_Map::update(StringData *key, TypedValue* data) {
1798   strhash_t h = key->hash();
1799   Bucket* p = findForInsert(key->data(), key->size(), h);
1800   assert(p);
1801   if (p->validValue()) {
1802     tvRefcountedIncRef(data);
1803     tvRefcountedDecRef(&p->data);
1804     p->data.m_data.num = data->m_data.num;
1805     p->data.m_type = data->m_type;
1806     return true;
1807   }
1808   ++m_version;
1809   ++m_size;
1810   if (!p->tombstone()) {
1811     if (UNLIKELY(++m_load >= computeMaxLoad())) {
1812       adjustCapacity();
1813       p = findForInsert(key->data(), key->size(), h);
1814       assert(p);
1815     }
1816   }
1817   tvRefcountedIncRef(data);
1818   p->data.m_data.num = data->m_data.num;
1819   p->data.m_type = data->m_type;
1820   p->setStrKey(key, h);
1821   return true;
1822 }
1823
1824 void c_Map::erase(Bucket* p) {
1825   if (!p) {
1826     return;
1827   }
1828   if (p->validValue()) {
1829     m_size--;
1830     tvRefcountedDecRef(&p->data);
1831     if (p->hasStrKey() && p->skey->decRefCount() == 0) {
1832       DELETE(StringData)(p->skey);
1833     }
1834     p->data.m_type = (DataType)KindOfTombstone;
1835     if (m_size < computeMinElements() && m_size) {
1836       adjustCapacity();
1837     }
1838   }
1839 }
1840
1841 void c_Map::adjustCapacityImpl(int64_t sz) {
1842   ++m_version;
1843   if (sz < 2) {
1844     if (sz <= 0) return;
1845     sz = 2;
1846   }
1847   if (m_nLastSlot == 0) {
1848     assert(m_data == (Bucket*)emptyMapSlot);
1849     m_nLastSlot = Util::roundUpToPowerOfTwo(sz << 1) - 1;
1850     m_data = (Bucket*)smart_calloc(numSlots(), sizeof(Bucket));
1851     return;
1852   }
1853   size_t oldNumSlots = numSlots();
1854   m_nLastSlot = Util::roundUpToPowerOfTwo(sz << 1) - 1;
1855   m_load = m_size;
1856   Bucket* oldBuckets = m_data;
1857   m_data = (Bucket*)smart_calloc(numSlots(), sizeof(Bucket));
1858   for (uint i = 0; i < oldNumSlots; ++i) {
1859     Bucket* p = &oldBuckets[i];
1860     if (p->validValue()) {
1861       Bucket* np = findForNewInsert(p->hasIntKey() ? p->ikey : p->hash());
1862       memcpy(np, p, sizeof(Bucket));
1863     }
1864   }
1865   smart_free(oldBuckets);
1866 }
1867
1868 ssize_t c_Map::iter_begin() const {
1869   if (!m_size) return 0;
1870   for (uint i = 0; i <= m_nLastSlot; ++i) {
1871     Bucket* p = fetchBucket(i);
1872     if (p->validValue()) {
1873       return reinterpret_cast<ssize_t>(p);
1874     }
1875   }
1876   return 0;
1877 }
1878
1879 ssize_t c_Map::iter_next(ssize_t pos) const {
1880   if (pos == 0) {
1881     return 0;
1882   }
1883   Bucket* p = reinterpret_cast<Bucket*>(pos);
1884   Bucket* pLast = fetchBucket(m_nLastSlot);
1885   ++p;
1886   while (p <= pLast) {
1887     if (p->validValue()) {
1888       return reinterpret_cast<ssize_t>(p);
1889     }
1890     ++p;
1891   }
1892   return 0;
1893 }
1894
1895 ssize_t c_Map::iter_prev(ssize_t pos) const {
1896   if (pos == 0) {
1897     return 0;
1898   }
1899   Bucket* p = reinterpret_cast<Bucket*>(pos);
1900   Bucket* pStart = m_data;
1901   --p;
1902   while (p >= pStart) {
1903     if (p->validValue()) {
1904       return reinterpret_cast<ssize_t>(p);
1905     }
1906     --p;
1907   }
1908   return 0;
1909 }
1910
1911 Variant c_Map::iter_key(ssize_t pos) const {
1912   assert(pos);
1913   Bucket* p = reinterpret_cast<Bucket*>(pos);
1914   if (p->hasStrKey()) {
1915     return p->skey;
1916   }
1917   return (int64_t)p->ikey;
1918 }
1919
1920 Variant c_Map::iter_value(ssize_t pos) const {
1921   assert(pos);
1922   Bucket* p = reinterpret_cast<Bucket*>(pos);
1923   return tvAsCVarRef(&p->data);
1924 }
1925
1926 void c_Map::throwBadKeyType() {
1927   Object e(SystemLib::AllocInvalidArgumentExceptionObject(
1928     "Only integer keys and string keys may be used with Maps"));
1929   throw e;
1930 }
1931
1932 void c_Map::Bucket::dump() {
1933   if (!validValue()) {
1934     printf("c_Map::Bucket: %s\n", (empty() ? "empty" : "tombstone"));
1935     return;
1936   }
1937   printf("c_Map::Bucket: %" PRIx64 "\n", hashKey());
1938   if (hasStrKey()) {
1939     skey->dump();
1940   }
1941   tvAsCVarRef(&data).dump();
1942 }
1943
1944 TypedValue* c_Map::OffsetGet(ObjectData* obj, TypedValue* key) {
1945   assert(key->m_type != KindOfRef);
1946   auto mp = static_cast<c_Map*>(obj);
1947   if (key->m_type == KindOfInt64) {
1948     return mp->at(key->m_data.num);
1949   }
1950   if (IS_STRING_TYPE(key->m_type)) {
1951     return mp->at(key->m_data.pstr);
1952   }
1953   throwBadKeyType();
1954   return nullptr;
1955 }
1956
1957 void c_Map::OffsetSet(ObjectData* obj, TypedValue* key, TypedValue* val) {
1958   assert(key->m_type != KindOfRef);
1959   assert(val->m_type != KindOfRef);
1960   auto mp = static_cast<c_Map*>(obj);
1961   if (key->m_type == KindOfInt64) {
1962     mp->set(key->m_data.num, val);
1963     return;
1964   }
1965   if (IS_STRING_TYPE(key->m_type)) {
1966     mp->set(key->m_data.pstr, val);
1967     return;
1968   }
1969   throwBadKeyType();
1970 }
1971
1972 bool c_Map::OffsetIsset(ObjectData* obj, TypedValue* key) {
1973   assert(key->m_type != KindOfRef);
1974   auto mp = static_cast<c_Map*>(obj);
1975   TypedValue* result;
1976   if (key->m_type == KindOfInt64) {
1977     result = mp->get(key->m_data.num);
1978   } else if (IS_STRING_TYPE(key->m_type)) {
1979     result = mp->get(key->m_data.pstr);
1980   } else {
1981     throwBadKeyType();
1982     result = nullptr;
1983   }
1984   return result ? isset(tvAsCVarRef(result)) : false;
1985 }
1986
1987 bool c_Map::OffsetEmpty(ObjectData* obj, TypedValue* key) {
1988   assert(key->m_type != KindOfRef);
1989   auto mp = static_cast<c_Map*>(obj);
1990   TypedValue* result;
1991   if (key->m_type == KindOfInt64) {
1992     result = mp->get(key->m_data.num);
1993   } else if (IS_STRING_TYPE(key->m_type)) {
1994     result = mp->get(key->m_data.pstr);
1995   } else {
1996     throwBadKeyType();
1997     result = nullptr;
1998   }
1999   return result ? empty(tvAsCVarRef(result)) : true;
2000 }
2001
2002 bool c_Map::OffsetContains(ObjectData* obj, TypedValue* key) {
2003   assert(key->m_type != KindOfRef);
2004   auto mp = static_cast<c_Map*>(obj);
2005   if (key->m_type == KindOfInt64) {
2006     return mp->contains(key->m_data.num);
2007   } else if (IS_STRING_TYPE(key->m_type)) {
2008     return mp->contains(key->m_data.pstr);
2009   } else {
2010     throwBadKeyType();
2011     return false;
2012   }
2013 }
2014
2015 void c_Map::OffsetAppend(ObjectData* obj, TypedValue* val) {
2016   assert(val->m_type != KindOfRef);
2017   auto mp = static_cast<c_Map*>(obj);
2018   mp->add(val);
2019 }
2020
2021 void c_Map::OffsetUnset(ObjectData* obj, TypedValue* key) {
2022   assert(key->m_type != KindOfRef);
2023   auto mp = static_cast<c_Map*>(obj);
2024   if (key->m_type == KindOfInt64) {
2025     mp->remove(key->m_data.num);
2026     return;
2027   }
2028   if (IS_STRING_TYPE(key->m_type)) {
2029     mp->remove(key->m_data.pstr);
2030     return;
2031   }
2032   throwBadKeyType();
2033 }
2034
2035 bool c_Map::Equals(ObjectData* obj1, ObjectData* obj2) {
2036   auto mp1 = static_cast<c_Map*>(obj1);
2037   auto mp2 = static_cast<c_Map*>(obj2);
2038   if (mp1->m_size != mp2->m_size) return false;
2039   for (uint i = 0; i <= mp1->m_nLastSlot; ++i) {
2040     c_Map::Bucket& p = mp1->m_data[i];
2041     if (p.validValue()) {
2042       TypedValue* tv2;
2043       if (p.hasIntKey()) {
2044         tv2 = mp2->get(p.ikey);
2045       } else {
2046         assert(p.hasStrKey());
2047         tv2 = mp2->get(p.skey);
2048       }
2049       if (!tv2) return false;
2050       if (!equal(tvAsCVarRef(&p.data), tvAsCVarRef(tv2))) return false;
2051     }
2052   }
2053   return true;
2054 }
2055
2056 void c_Map::Unserialize(ObjectData* obj,
2057                         VariableUnserializer* uns,
2058                         int64_t sz,
2059                         char type) {
2060   if (type != 'K') {
2061     throw Exception("Map does not support the '%c' serialization "
2062                     "format", type);
2063   }
2064   auto mp = static_cast<c_Map*>(obj);
2065   mp->reserve(sz);
2066   for (int64_t i = 0; i < sz; ++i) {
2067     Variant k;
2068     k.unserialize(uns, Uns::ColKeyMode);
2069     Bucket* p;
2070     if (k.isInteger()) {
2071       auto h = k.toInt64();
2072       p = mp->findForInsert(h);
2073       if (UNLIKELY(p->validValue())) goto do_unserialize;
2074       p->setIntKey(h);
2075     } else if (k.isString()) {
2076       auto key = k.getStringData();
2077       auto h = key->hash();
2078       p = mp->findForInsert(key->data(), key->size(), h);
2079       if (UNLIKELY(p->validValue())) goto do_unserialize;
2080       p->setStrKey(key, h);
2081     } else {
2082       throw Exception("Invalid key");
2083     }
2084     ++mp->m_size;
2085     ++mp->m_load;
2086     p->data.m_type = KindOfNull;
2087 do_unserialize:
2088     tvAsVariant(&p->data).unserialize(uns, Uns::ColValueMode);
2089   }
2090 }
2091
2092 c_MapIterator::c_MapIterator(Class* cb) :
2093     ExtObjectData(cb) {
2094 }
2095
2096 c_MapIterator::~c_MapIterator() {
2097 }
2098
2099 void c_MapIterator::t___construct() {
2100 }
2101
2102 Variant c_MapIterator::t_current() {
2103   c_Map* mp = m_obj.get();
2104   if (UNLIKELY(m_version != mp->getVersion())) {
2105     throw_collection_modified();
2106   }
2107   if (!m_pos) {
2108     throw_iterator_not_valid();
2109   }
2110   return mp->iter_value(m_pos);
2111 }
2112
2113 Variant c_MapIterator::t_key() {
2114   c_Map* mp = m_obj.get();
2115   if (UNLIKELY(m_version != mp->getVersion())) {
2116     throw_collection_modified();
2117   }
2118   if (!m_pos) {
2119     throw_iterator_not_valid();
2120   }
2121   return mp->iter_key(m_pos);
2122 }
2123
2124 bool c_MapIterator::t_valid() {
2125   return m_pos != 0;
2126 }
2127
2128 void c_MapIterator::t_next() {
2129   c_Map* mp = m_obj.get();
2130   if (UNLIKELY(m_version != mp->getVersion())) {
2131     throw_collection_modified();
2132   }
2133   m_pos = mp->iter_next(m_pos);
2134 }
2135
2136 void c_MapIterator::t_rewind() {
2137   c_Map* mp = m_obj.get();
2138   if (UNLIKELY(m_version != mp->getVersion())) {
2139     throw_collection_modified();
2140   }
2141   m_pos = mp->iter_begin();
2142 }
2143
2144 ///////////////////////////////////////////////////////////////////////////////
2145
2146 IMPLEMENT_SMART_ALLOCATION_CLS(c_StableMap, Bucket);
2147
2148 #define CONNECT_TO_GLOBAL_DLLIST(mapobj, element)                       \
2149 do {                                                                    \
2150   (element)->pListLast = (mapobj)->m_pListTail;                         \
2151   (mapobj)->m_pListTail = (element);                                    \
2152   (element)->pListNext = nullptr;                                       \
2153   if ((element)->pListLast != nullptr) {                                \
2154     (element)->pListLast->pListNext = (element);                        \
2155   }                                                                     \
2156   if (!(mapobj)->m_pListHead) {                                         \
2157     (mapobj)->m_pListHead = (element);                                  \
2158   }                                                                     \
2159 } while (false)
2160
2161 static const char emptyStableMapSlot[sizeof(c_StableMap::Bucket*)] = { 0 };
2162
2163 c_StableMap::c_StableMap(Class* cb) :
2164     ExtObjectDataFlags<ObjectData::StableMapAttrInit|
2165                        ObjectData::UseGet|
2166                        ObjectData::UseSet|
2167                        ObjectData::UseIsset|
2168                        ObjectData::UseUnset>(cb),
2169     m_version(0), m_pListHead(nullptr), m_pListTail(nullptr) {
2170   m_size = 0;
2171   m_nTableSize = 0;
2172   m_nTableMask = 0;
2173   m_arBuckets = (Bucket**)emptyStableMapSlot;
2174 }
2175
2176 c_StableMap::~c_StableMap() {
2177   deleteBuckets();
2178   freeData();
2179 }
2180
2181 void c_StableMap::freeData() {
2182   if (m_arBuckets != (Bucket**)emptyStableMapSlot) {
2183     smart_free(m_arBuckets);
2184   }
2185   m_arBuckets = (Bucket**)emptyStableMapSlot;
2186 }
2187
2188 void c_StableMap::deleteBuckets() {
2189   Bucket* p = m_pListHead;
2190   while (p) {
2191     Bucket* q = p;
2192     p = p->pListNext;
2193     DELETE(Bucket)(q);
2194   }
2195 }
2196
2197 void c_StableMap::t___construct(CVarRef iterable /* = null_variant */) {
2198   if (!iterable.isInitialized()) {
2199     return;
2200   }
2201   size_t sz;
2202   ArrayIter iter = getArrayIterHelper(iterable, sz);
2203   if (sz) {
2204     reserve(sz);
2205   }
2206   for (; iter; ++iter) {
2207     Variant k = iter.first();
2208     Variant v = iter.second();
2209     TypedValue* tv = cvarToCell(&v);
2210     if (k.isInteger()) {
2211       update(k.toInt64(), tv);
2212     } else if (k.isString()) {
2213       update(k.getStringData(), tv);
2214     } else {
2215       throwBadKeyType();
2216     }
2217   }
2218 }
2219
2220 Array c_StableMap::toArrayImpl() const {
2221   ArrayInit ai(m_size);
2222   Bucket* p = m_pListHead;
2223   while (p) {
2224     if (p->hasIntKey()) {
2225       ai.set((int64_t)p->ikey, tvAsCVarRef(&p->data));
2226     } else {
2227       ai.set(*(const String*)(&p->skey), tvAsCVarRef(&p->data));
2228     }
2229     p = p->pListNext;
2230   }
2231   return ai.create();
2232 }
2233
2234 Array c_StableMap::o_toArray() const {
2235   check_collection_cast_to_array();
2236   return toArrayImpl();
2237 }
2238
2239 ObjectData* c_StableMap::clone() {
2240   ObjectData* obj = ObjectData::clone();
2241   auto target = static_cast<c_StableMap*>(obj);
2242
2243   if (!m_size) return obj;
2244
2245   target->m_size = m_size;
2246   target->m_nTableSize = m_nTableSize;
2247   target->m_nTableMask = m_nTableMask;
2248   target->m_arBuckets = (Bucket**)smart_calloc(m_nTableSize, sizeof(Bucket*));
2249
2250   Bucket *last = nullptr;
2251   for (Bucket* p = m_pListHead; p; p = p->pListNext) {
2252     Bucket *np = NEW(Bucket)();
2253     tvDup(&p->data, &np->data);
2254     uint nIndex;
2255     if (p->hasIntKey()) {
2256       np->setIntKey(p->ikey);
2257       nIndex = p->ikey & target->m_nTableMask;
2258     } else {
2259       np->setStrKey(p->skey, p->hash());
2260       nIndex = p->hash() & target->m_nTableMask;
2261     }
2262
2263     np->pNext = target->m_arBuckets[nIndex];
2264     target->m_arBuckets[nIndex] = np;
2265
2266     if (last) {
2267       last->pListNext = np;
2268       np->pListLast = last;
2269     } else {
2270       target->m_pListHead = np;
2271     }
2272     last = np;
2273   }
2274   target->m_pListTail = last;
2275
2276   return obj;
2277 }
2278
2279 Object c_StableMap::t_add(CVarRef val) {
2280   TypedValue* tv = cvarToCell(&val);
2281   add(tv);
2282   return this;
2283 }
2284
2285 Object c_StableMap::t_addall(CVarRef iterable) {
2286   size_t sz;
2287   ArrayIter iter = getArrayIterHelper(iterable, sz);
2288   reserve(std::max(sz, size_t(m_size)));
2289   for (; iter; ++iter) {
2290     Variant v = iter.second();
2291     TypedValue* tv = cvarToCell(&v);
2292     add(tv);
2293   }
2294   return this;
2295 }
2296
2297 Object c_StableMap::t_clear() {
2298   deleteBuckets();
2299   freeData();
2300   m_pListHead = nullptr;
2301   m_pListTail = nullptr;
2302   m_size = 0;
2303   m_nTableSize = 0;
2304   m_nTableMask = 0;
2305   m_arBuckets = (Bucket**)emptyStableMapSlot;
2306   return this;
2307 }
2308
2309 bool c_StableMap::t_isempty() {
2310   return (m_size == 0);
2311 }
2312
2313 int64_t c_StableMap::t_count() {
2314   return m_size;
2315 }
2316
2317 Object c_StableMap::t_items() {
2318   return SystemLib::AllocKVZippedIterableObject(this);
2319 }
2320
2321 Object c_StableMap::t_keys() {
2322   c_Vector* vec;
2323   Object obj = vec = NEWOBJ(c_Vector)();
2324   vec->reserve(m_size);
2325   uint64_t j = 0;
2326   for (Bucket* p = m_pListHead; p; p = p->pListNext) {
2327     if (p->hasIntKey()) {
2328       vec->m_data[j].m_data.num = p->ikey;
2329       vec->m_data[j].m_type = KindOfInt64;
2330     } else {
2331       p->skey->incRefCount();
2332       vec->m_data[j].m_data.pstr = p->skey;
2333       vec->m_data[j].m_type = KindOfString;
2334     }
2335     ++vec->m_size;
2336     ++j;
2337   }
2338   return obj;
2339 }
2340
2341 Object c_StableMap::t_view() {
2342   return SystemLib::AllocKeyedIterableViewObject(this);
2343 }
2344
2345 Object c_StableMap::t_kvzip() {
2346   c_Vector* vec;
2347   Object obj = vec = NEWOBJ(c_Vector)();
2348   vec->reserve(m_size);
2349   uint64_t j = 0;
2350   for (Bucket* p = m_pListHead; p; p = p->pListNext) {
2351     c_Pair* pair = NEWOBJ(c_Pair)();
2352     pair->incRefCount();
2353     if (p->hasIntKey()) {
2354       pair->elm0.m_data.num = p->ikey;
2355       pair->elm0.m_type = KindOfInt64;
2356     } else {
2357       p->skey->incRefCount();
2358       pair->elm0.m_data.pstr = p->skey;
2359       pair->elm0.m_type = KindOfString;
2360     }
2361     ++pair->m_size;
2362     pair->add(&p->data);
2363     vec->m_data[j].m_data.pobj = pair;
2364     vec->m_data[j].m_type = KindOfObject;
2365     ++vec->m_size;
2366     ++j;
2367   }
2368   return obj;
2369 }
2370
2371 Variant c_StableMap::t_at(CVarRef key) {
2372   if (key.isInteger()) {
2373     return tvAsCVarRef(at(key.toInt64()));
2374   } else if (key.isString()) {
2375     return tvAsCVarRef(at(key.getStringData()));
2376   }
2377   throwBadKeyType();
2378   return uninit_null();
2379 }
2380
2381 Variant c_StableMap::t_get(CVarRef key) {
2382   if (key.isInteger()) {
2383     TypedValue* tv = get(key.toInt64());
2384     if (tv) {
2385       return tvAsCVarRef(tv);
2386     } else {
2387       return uninit_null();
2388     }
2389   } else if (key.isString()) {
2390     TypedValue* tv = get(key.getStringData());
2391     if (tv) {
2392       return tvAsCVarRef(tv);
2393     } else {
2394       return uninit_null();
2395     }
2396   }
2397   throwBadKeyType();
2398   return uninit_null();
2399 }
2400
2401 Object c_StableMap::t_set(CVarRef key, CVarRef value) {
2402   TypedValue* val = cvarToCell(&value);
2403   if (key.isInteger()) {
2404     update(key.toInt64(), val);
2405   } else if (key.isString()) {
2406     update(key.getStringData(), val);
2407   } else {
2408     throwBadKeyType();
2409   }
2410   return this;
2411 }
2412
2413 Object c_StableMap::t_setall(CVarRef iterable) {
2414   size_t sz;
2415   ArrayIter iter = getArrayIterHelper(iterable, sz);
2416   for (; iter; ++iter) {
2417     Variant k = iter.first();
2418     Variant v = iter.second();
2419     TypedValue* tvKey = cvarToCell(&k);
2420     TypedValue* tvVal = cvarToCell(&v);
2421     if (tvKey->m_type == KindOfInt64) {
2422       set(tvKey->m_data.num, tvVal);
2423     } else if (IS_STRING_TYPE(tvKey->m_type)) {
2424       set(tvKey->m_data.pstr, tvVal);
2425     } else {
2426       throwBadKeyType();
2427     }
2428   }
2429   return this;
2430 }
2431
2432 Object c_StableMap::t_put(CVarRef key, CVarRef value) {
2433   return t_set(key, value);
2434 }
2435
2436 bool c_StableMap::t_contains(CVarRef key) {
2437   DataType t = key.getType();
2438   if (t == KindOfInt64) {
2439     return contains(key.toInt64());
2440   }
2441   if (IS_STRING_TYPE(t)) {
2442     return contains(key.getStringData());
2443   }
2444   throwBadKeyType();
2445   return false;
2446 }
2447
2448 bool c_StableMap::t_containskey(CVarRef key) {
2449   return t_contains(key);
2450 }
2451
2452 Object c_StableMap::t_remove(CVarRef key) {
2453   DataType t = key.getType();
2454   if (t == KindOfInt64) {
2455     remove(key.toInt64());
2456   } else if (IS_STRING_TYPE(t)) {
2457     remove(key.getStringData());
2458   } else {
2459     throwBadKeyType();
2460   }
2461   return this;
2462 }
2463
2464 Object c_StableMap::t_removekey(CVarRef key) {
2465   return t_remove(key);
2466 }
2467
2468 Object c_StableMap::t_discard(CVarRef key) {
2469   return t_remove(key);
2470 }
2471
2472 Array c_StableMap::t_toarray() {
2473   return toArrayImpl();
2474 }
2475
2476 Array c_StableMap::t_copyasarray() {
2477   return toArrayImpl();
2478 }
2479
2480 Array c_StableMap::t_tokeysarray() {
2481   ArrayInit ai(m_size, ArrayInit::vectorInit);
2482   Bucket* p = m_pListHead;
2483   while (p) {
2484     if (p->hasIntKey()) {
2485       ai.set((int64_t)p->ikey);
2486     } else {
2487       ai.set(*(const String*)(&p->skey));
2488     }
2489     p = p->pListNext;
2490   }
2491   return ai.create();
2492 }
2493
2494 Object c_StableMap::t_values() {
2495   c_Vector* target;
2496   Object ret = target = NEWOBJ(c_Vector)();
2497   int64_t sz = m_size;
2498   if (!sz) {
2499     return ret;
2500   }
2501   TypedValue* data;
2502   target->m_capacity = target->m_size = m_size;
2503   target->m_data = data = (TypedValue*)smart_malloc(sz * sizeof(TypedValue));
2504   Bucket* p = m_pListHead;
2505   for (int64_t i = 0; i < sz; ++i) {
2506     assert(p);
2507     tvDup(&p->data, &data[i]);
2508     p = p->pListNext;
2509   }
2510   return ret;
2511 }
2512
2513 Array c_StableMap::t_tovaluesarray() {
2514   ArrayInit ai(m_size, ArrayInit::vectorInit);
2515   Bucket* p = m_pListHead;
2516   while (p) {
2517     ai.set(tvAsCVarRef(&p->data));
2518     p = p->pListNext;
2519   }
2520   return ai.create();
2521 }
2522
2523 Object c_StableMap::t_updatefromarray(CVarRef arr) {
2524   if (!arr.isArray()) {
2525     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
2526       "Parameter arr must be an array"));
2527     throw e;
2528   }
2529   ArrayData* ad = arr.getArrayData();
2530   for (ssize_t pos = ad->iter_begin(); pos != ArrayData::invalid_index;
2531        pos = ad->iter_advance(pos)) {
2532     Variant k = ad->getKey(pos);
2533     TypedValue* tv = cvarToCell(&ad->getValueRef(pos));
2534     if (k.isInteger()) {
2535       update(k.toInt64(), tv);
2536     } else {
2537       assert(k.isString());
2538       update(k.getStringData(), tv);
2539     }
2540   }
2541   return this;
2542 }
2543
2544 Object c_StableMap::t_updatefromiterable(CVarRef it) {
2545   if (!it.isObject()) {
2546     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
2547       "Parameter it must be an instance of Iterable"));
2548     throw e;
2549   }
2550   ObjectData* obj = it.getObjectData();
2551   if (obj->getCollectionType() == Collection::StableMapType) {
2552     auto smp = static_cast<c_StableMap*>(obj);
2553     c_StableMap::Bucket* p = smp->m_pListHead;
2554     while (p) {
2555       if (p->hasIntKey()) {
2556         update((int64_t)p->ikey, &p->data);
2557       } else {
2558         update(p->skey, &p->data);
2559       }
2560       p = p->pListNext;
2561     }
2562     return this;
2563   }
2564   for (ArrayIter iter = obj->begin(); iter; ++iter) {
2565     Variant k = iter.first();
2566     Variant v = iter.second();
2567     TypedValue* tv = cvarToCell(&v);
2568     if (k.isInteger()) {
2569       update(k.toInt64(), tv);
2570     } else {
2571       assert(k.isString());
2572       update(k.getStringData(), tv);
2573     }
2574   }
2575   return this;
2576 }
2577
2578 Object c_StableMap::t_differencebykey(CVarRef it) {
2579   if (!it.isObject()) {
2580     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
2581       "Parameter it must be an instance of Iterable"));
2582     throw e;
2583   }
2584   ObjectData* obj = it.getObjectData();
2585   c_StableMap* target;
2586   Object ret = target = static_cast<c_StableMap*>(clone());
2587   if (obj->getCollectionType() == Collection::StableMapType) {
2588     auto smp = static_cast<c_StableMap*>(obj);
2589     c_StableMap::Bucket* p = smp->m_pListHead;
2590     while (p) {
2591       if (p->hasIntKey()) {
2592         target->remove((int64_t)p->ikey);
2593       } else {
2594         target->remove(p->skey);
2595       }
2596       p = p->pListNext;
2597     }
2598   }
2599   for (ArrayIter iter = obj->begin(); iter; ++iter) {
2600     Variant k = iter.first();
2601     if (k.isInteger()) {
2602       target->remove(k.toInt64());
2603     } else {
2604       assert(k.isString());
2605       target->remove(k.getStringData());
2606     }
2607   }
2608   return ret;
2609 }
2610
2611 Object c_StableMap::t_getiterator() {
2612   c_StableMapIterator* it = NEWOBJ(c_StableMapIterator)();
2613   it->m_obj = this;
2614   it->m_pos = iter_begin();
2615   it->m_version = getVersion();
2616   return it;
2617 }
2618
2619 Object c_StableMap::t_map(CVarRef callback) {
2620   CallCtx ctx;
2621   vm_decode_function(callback, nullptr, false, ctx);
2622   if (!ctx.func) {
2623     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
2624       "Parameter must be a valid callback"));
2625     throw e;
2626   }
2627   c_StableMap* smp;
2628   Object obj = smp = NEWOBJ(c_StableMap)();
2629   if (!m_size) return obj;
2630   smp->m_size = m_size;
2631   smp->m_nTableSize = m_nTableSize;
2632   smp->m_nTableMask = m_nTableMask;
2633   smp->m_arBuckets = (Bucket**)smart_calloc(m_nTableSize, sizeof(Bucket*));
2634   Bucket *last = nullptr;
2635   for (Bucket* p = m_pListHead; p; p = p->pListNext) {
2636     Variant ret;
2637     int32_t version = m_version;
2638     TypedValue args[1];
2639     tvDup(&p->data, args + 0);
2640     g_vmContext->invokeFuncFew(ret.asTypedValue(), ctx, 1, args);
2641     if (UNLIKELY(version != m_version)) {
2642       throw_collection_modified();
2643     }
2644     Bucket *np = NEW(Bucket)(ret.asTypedValue());
2645     uint nIndex;
2646     if (p->hasIntKey()) {
2647       np->setIntKey(p->ikey);
2648       nIndex = p->ikey & smp->m_nTableMask;
2649     } else {
2650       np->setStrKey(p->skey, p->hash());
2651       nIndex = p->hash() & smp->m_nTableMask;
2652     }
2653     np->pNext = smp->m_arBuckets[nIndex];
2654     smp->m_arBuckets[nIndex] = np;
2655     if (last) {
2656       last->pListNext = np;
2657       np->pListLast = last;
2658     } else {
2659       smp->m_pListHead = np;
2660     }
2661     last = np;
2662   }
2663   smp->m_pListTail = last;
2664   return obj;
2665 }
2666
2667 Object c_StableMap::t_filter(CVarRef callback) {
2668   CallCtx ctx;
2669   vm_decode_function(callback, nullptr, false, ctx);
2670   if (!ctx.func) {
2671     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
2672       "Parameter must be a valid callback"));
2673     throw e;
2674   }
2675   c_StableMap* smp;
2676   Object obj = smp = NEWOBJ(c_StableMap)();
2677   if (!m_size) return obj;
2678   for (Bucket* p = m_pListHead; p; p = p->pListNext) {
2679     Variant ret;
2680     int32_t version = m_version;
2681     TypedValue args[1];
2682     tvDup(&p->data, args + 0);
2683     g_vmContext->invokeFuncFew(ret.asTypedValue(), ctx, 1, args);
2684     if (UNLIKELY(version != m_version)) {
2685       throw_collection_modified();
2686     }
2687     if (!ret.toBoolean()) continue;
2688     if (p->hasIntKey()) {
2689       smp->update(p->ikey, &p->data);
2690     } else {
2691       smp->update(p->skey, &p->data);
2692     }
2693   }
2694   return obj;
2695 }
2696
2697 Object c_StableMap::t_zip(CVarRef iterable) {
2698   size_t sz;
2699   ArrayIter iter = getArrayIterHelper(iterable, sz);
2700   c_StableMap* smp;
2701   Object obj = smp = NEWOBJ(c_StableMap)();
2702   smp->reserve(std::min(sz, size_t(m_size)));
2703   for (Bucket* p = m_pListHead; p && iter; p = p->pListNext, ++iter) {
2704     Variant v = iter.second();
2705     c_Pair* pair;
2706     Object pairObj = pair = NEWOBJ(c_Pair)();
2707     pair->add(&p->data);
2708     pair->add(cvarToCell(&v));
2709     TypedValue tv;
2710     tv.m_data.pobj = pair;
2711     tv.m_type = KindOfObject;
2712     if (p->hasIntKey()) {
2713       smp->update(p->ikey, &tv);
2714     } else {
2715       smp->update(p->skey, &tv);
2716     }
2717   }
2718   return obj;
2719 }
2720
2721 Object c_StableMap::ti_fromitems(CVarRef iterable) {
2722   size_t sz;
2723   ArrayIter iter = getArrayIterHelper(iterable, sz);
2724   c_StableMap* target;
2725   Object ret = target = NEWOBJ(c_StableMap)();
2726   if (sz) {
2727     target->reserve(sz);
2728   }
2729   for (; iter; ++iter) {
2730     Variant v = iter.second();
2731     TypedValue* tv = cvarToCell(&v);
2732     if (UNLIKELY(tv->m_type != KindOfObject ||
2733                  !tv->m_data.pobj->instanceof(c_Pair::s_cls))) {
2734       Object e(SystemLib::AllocInvalidArgumentExceptionObject(
2735         "Parameter must be an instance of Iterable<Pair>"));
2736       throw e;
2737     }
2738     auto pair = static_cast<c_Pair*>(tv->m_data.pobj);
2739     TypedValue* tvKey = &pair->elm0;
2740     TypedValue* tvValue = &pair->elm1;
2741     assert(tvKey->m_type != KindOfRef);
2742     assert(tvValue->m_type != KindOfRef);
2743     if (tvKey->m_type == KindOfInt64) {
2744       target->update(tvKey->m_data.num, tvValue);
2745     } else if (IS_STRING_TYPE(tvKey->m_type)) {
2746       target->update(tvKey->m_data.pstr, tvValue);
2747     } else {
2748       throwBadKeyType();
2749     }
2750   }
2751   return ret;
2752 }
2753
2754 Object c_StableMap::ti_fromarray(CVarRef arr) {
2755   if (!arr.isArray()) {
2756     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
2757       "Parameter arr must be an array"));
2758     throw e;
2759   }
2760   c_StableMap* smp;
2761   Object ret = smp = NEWOBJ(c_StableMap)();
2762   ArrayData* ad = arr.getArrayData();
2763   for (ssize_t pos = ad->iter_begin(); pos != ArrayData::invalid_index;
2764        pos = ad->iter_advance(pos)) {
2765     Variant k = ad->getKey(pos);
2766     Variant v = ad->getValue(pos);
2767     TypedValue* tv = cvarToCell(&v);
2768     if (k.isInteger()) {
2769       smp->update(k.toInt64(), tv);
2770     } else {
2771       assert(k.isString());
2772       smp->update(k.getStringData(), tv);
2773     }
2774   }
2775   return ret;
2776 }
2777
2778 Object c_StableMap::ti_fromiterable(CVarRef it) {
2779   if (!it.isObject()) {
2780     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
2781       "Parameter it must be an instance of Iterable"));
2782     throw e;
2783   }
2784   ObjectData* obj = it.getObjectData();
2785   Object ret;
2786   if (obj->getCollectionType() == Collection::StableMapType) {
2787     ret = obj->clone();
2788     return ret;
2789   }
2790   c_StableMap* target;
2791   ret = target = NEWOBJ(c_StableMap)();
2792   for (ArrayIter iter = obj->begin(); iter; ++iter) {
2793     Variant k = iter.first();
2794     Variant v = iter.second();
2795     TypedValue* tv = cvarToCell(&v);
2796     if (k.isInteger()) {
2797       target->update(k.toInt64(), tv);
2798     } else {
2799       assert(k.isString());
2800       target->update(k.getStringData(), tv);
2801     }
2802   }
2803   return ret;
2804 }
2805
2806 void c_StableMap::throwOOB(int64_t key) {
2807   throwIntOOB(key);
2808 }
2809
2810 void c_StableMap::throwOOB(StringData* key) {
2811   throwStrOOB(key);
2812 }
2813
2814 void c_StableMap::add(TypedValue* val) {
2815   if (UNLIKELY(val->m_type != KindOfObject ||
2816                !val->m_data.pobj->instanceof(c_Pair::s_cls))) {
2817     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
2818       "Parameter must be an instance of Pair"));
2819     throw e;
2820   }
2821   auto pair = static_cast<c_Pair*>(val->m_data.pobj);
2822   TypedValue* tvKey = &pair->elm0;
2823   TypedValue* tvValue = &pair->elm1;
2824   assert(tvKey->m_type != KindOfRef);
2825   assert(tvValue->m_type != KindOfRef);
2826   if (tvKey->m_type == KindOfInt64) {
2827     update(tvKey->m_data.num, tvValue);
2828   } else if (IS_STRING_TYPE(tvKey->m_type)) {
2829     update(tvKey->m_data.pstr, tvValue);
2830   } else {
2831     throwBadKeyType();
2832   }
2833 }
2834
2835 bool inline sm_hit_string_key(const c_StableMap::Bucket* p,
2836                               const char* k, int len, int32_t hash) ALWAYS_INLINE;
2837 bool inline sm_hit_string_key(const c_StableMap::Bucket* p,
2838                               const char* k, int len, int32_t hash) {
2839   if (p->hasIntKey()) return false;
2840   const char* data = p->skey->data();
2841   return data == k || (p->hash() == hash &&
2842                        p->skey->size() == len &&
2843                        memcmp(data, k, len) == 0);
2844 }
2845
2846 c_StableMap::Bucket* c_StableMap::find(int64_t h) const {
2847   for (Bucket* p = m_arBuckets[h & m_nTableMask]; p; p = p->pNext) {
2848     if (p->hasIntKey() && p->ikey == h) {
2849       return p;
2850     }
2851   }
2852   return nullptr;
2853 }
2854
2855 c_StableMap::Bucket* c_StableMap::find(const char* k, int len,
2856                                        strhash_t prehash) const {
2857   int32_t hash = c_StableMap::Bucket::encodeHash(prehash);
2858   for (Bucket* p = m_arBuckets[prehash & m_nTableMask]; p; p = p->pNext) {
2859     if (sm_hit_string_key(p, k, len, hash)) return p;
2860   }
2861   return nullptr;
2862 }
2863
2864 c_StableMap::Bucket** c_StableMap::findForErase(int64_t h) const {
2865   Bucket** ret = &(m_arBuckets[h & m_nTableMask]);
2866   Bucket* p = *ret;
2867   while (p) {
2868     if (p->hasIntKey() && p->ikey == h) {
2869       return ret;
2870     }
2871     ret = &(p->pNext);
2872     p = *ret;
2873   }
2874   return nullptr;
2875 }
2876
2877 c_StableMap::Bucket** c_StableMap::findForErase(const char* k, int len,
2878                                                 strhash_t prehash) const {
2879   Bucket** ret = &(m_arBuckets[prehash & m_nTableMask]);
2880   Bucket* p = *ret;
2881   int32_t hash = c_StableMap::Bucket::encodeHash(prehash);
2882   while (p) {
2883     if (sm_hit_string_key(p, k, len, hash)) return ret;
2884     ret = &(p->pNext);
2885     p = *ret;
2886   }
2887   return nullptr;
2888 }
2889
2890 bool c_StableMap::update(int64_t h, TypedValue* data) {
2891   Bucket* p = find(h);
2892   if (p) {
2893     tvRefcountedIncRef(data);
2894     tvRefcountedDecRef(&p->data);
2895     p->data.m_data.num = data->m_data.num;
2896     p->data.m_type = data->m_type;
2897     return true;
2898   }
2899   ++m_version;
2900   if (++m_size > m_nTableSize) {
2901     adjustCapacity();
2902   }
2903   p = NEW(Bucket)(data);
2904   p->setIntKey(h);
2905   uint nIndex = (h & m_nTableMask);
2906   p->pNext = m_arBuckets[nIndex];
2907   m_arBuckets[nIndex] = p;
2908   CONNECT_TO_GLOBAL_DLLIST(this, p);
2909   return true;
2910 }
2911
2912 bool c_StableMap::update(StringData *key, TypedValue* data) {
2913   strhash_t h = key->hash();
2914   Bucket* p = find(key->data(), key->size(), h);
2915   if (p) {
2916     tvRefcountedIncRef(data);
2917     tvRefcountedDecRef(&p->data);
2918     p->data.m_data.num = data->m_data.num;
2919     p->data.m_type = data->m_type;
2920     return true;
2921   }
2922   ++m_version;
2923   if (++m_size > m_nTableSize) {
2924     adjustCapacity();
2925   }
2926   p = NEW(Bucket)(data);
2927   p->setStrKey(key, h);
2928   uint nIndex = (h & m_nTableMask);
2929   p->pNext = m_arBuckets[nIndex];
2930   m_arBuckets[nIndex] = p;
2931   CONNECT_TO_GLOBAL_DLLIST(this, p);
2932   return true;
2933 }
2934
2935 void c_StableMap::erase(Bucket** prev) {
2936   if (!prev) {
2937     return;
2938   }
2939   Bucket* p = *prev;
2940   if (p) {
2941     *prev = p->pNext;
2942     if (p->pListLast) {
2943       p->pListLast->pListNext = p->pListNext;
2944     } else {
2945       /* Deleting the head of the list */
2946       assert(m_pListHead == p);
2947       m_pListHead = p->pListNext;
2948     }
2949     if (p->pListNext) {
2950       p->pListNext->pListLast = p->pListLast;
2951     } else {
2952       assert(m_pListTail == p);
2953       m_pListTail = p->pListLast;
2954     }
2955     m_size--;
2956     DELETE(Bucket)(p);
2957   }
2958 }
2959
2960 void c_StableMap::adjustCapacityImpl(int64_t sz) {
2961   ++m_version;
2962   if (sz < 4) {
2963     if (sz <= 0) return;
2964     sz = 4;
2965   } else {
2966     sz = Util::roundUpToPowerOfTwo(sz);
2967   }
2968   if (m_nTableSize == 0) {
2969     m_nTableSize = sz;
2970     m_nTableMask = m_nTableSize - 1;
2971     m_arBuckets = (Bucket**)smart_calloc(m_nTableSize, sizeof(Bucket*));
2972     return;
2973   }
2974   m_nTableSize = sz;
2975   m_nTableMask = m_nTableSize - 1;
2976   smart_free(m_arBuckets);
2977   m_arBuckets = (Bucket**)smart_calloc(m_nTableSize, sizeof(Bucket*));
2978   for (Bucket* p = m_pListHead; p; p = p->pListNext) {
2979     uint nIndex = (p->hashKey() & m_nTableMask);
2980     p->pNext = m_arBuckets[nIndex];
2981     m_arBuckets[nIndex] = p;
2982   }
2983 }
2984
2985 ssize_t c_StableMap::iter_begin() const {
2986   Bucket* p = m_pListHead;
2987   return reinterpret_cast<ssize_t>(p);
2988 }
2989
2990 ssize_t c_StableMap::iter_next(ssize_t pos) const {
2991   if (pos == 0) {
2992     return 0;
2993   }
2994   Bucket* p = reinterpret_cast<Bucket*>(pos);
2995   p = p->pListNext;
2996   return reinterpret_cast<ssize_t>(p);
2997 }
2998
2999 ssize_t c_StableMap::iter_prev(ssize_t pos) const {
3000   if (pos == 0) {
3001     return 0;
3002   }
3003   Bucket* p = reinterpret_cast<Bucket*>(pos);
3004   p = p->pListLast;
3005   return reinterpret_cast<ssize_t>(p);
3006 }
3007
3008 Variant c_StableMap::iter_key(ssize_t pos) const {
3009   assert(pos);
3010   Bucket* p = reinterpret_cast<Bucket*>(pos);
3011   if (p->hasStrKey()) {
3012     return p->skey;
3013   }
3014   return (int64_t)p->ikey;
3015 }
3016
3017 Variant c_StableMap::iter_value(ssize_t pos) const {
3018   assert(pos);
3019   Bucket* p = reinterpret_cast<Bucket*>(pos);
3020   return tvAsCVarRef(&p->data);
3021 }
3022
3023 struct StableMapKeyAccessor {
3024   typedef const c_StableMap::Bucket* ElmT;
3025   bool isInt(ElmT elm) const { return elm->hasIntKey(); }
3026   bool isStr(ElmT elm) const { return elm->hasStrKey(); }
3027   int64_t getInt(ElmT elm) const { return elm->ikey; }
3028   StringData* getStr(ElmT elm) const { return elm->skey; }
3029   Variant getValue(ElmT elm) const {
3030     if (isInt(elm)) {
3031       return getInt(elm);
3032     }
3033     assert(isStr(elm));
3034     return getStr(elm);
3035   }
3036 };
3037
3038 struct StableMapValAccessor {
3039   typedef const c_StableMap::Bucket* ElmT;
3040   bool isInt(ElmT elm) const { return elm->data.m_type == KindOfInt64; }
3041   bool isStr(ElmT elm) const { return IS_STRING_TYPE(elm->data.m_type); }
3042   int64_t getInt(ElmT elm) const { return elm->data.m_data.num; }
3043   StringData* getStr(ElmT elm) const { return elm->data.m_data.pstr; }
3044   Variant getValue(ElmT elm) const { return tvAsCVarRef(&elm->data); }
3045 };
3046
3047 /**
3048  * preSort() does an initial pass over the array to do some preparatory work
3049  * before the sort algorithm runs. For sorts that use builtin comparators, the
3050  * types of values are also observed during this first pass. By observing the
3051  * types during this initial pass, we can often use a specialized comparator
3052  * and avoid performing type checks during the actual sort.
3053  */
3054 template <typename AccessorT>
3055 c_StableMap::SortFlavor c_StableMap::preSort(Bucket** buffer,
3056                                              const AccessorT& acc,
3057                                              bool checkTypes) {
3058   assert(m_size > 0);
3059   bool allInts UNUSED = true;
3060   bool allStrs UNUSED = true;
3061   uint i = 0;
3062   // Build up an auxillary array of Bucket pointers. We will
3063   // sort this auxillary array, and then we will rebuild the
3064   // linked list based on the result.
3065   if (checkTypes) {
3066     for (Bucket* p = m_pListHead; p; ++i, p = p->pListNext) {
3067       allInts = (allInts && acc.isInt(p));
3068       allStrs = (allStrs && acc.isStr(p));
3069       buffer[i] = p;
3070     }
3071     return allStrs ? StringSort : allInts ? IntegerSort : GenericSort;
3072   } else {
3073     for (Bucket* p = m_pListHead; p; ++i, p = p->pListNext) {
3074       buffer[i] = p;
3075     }
3076     return GenericSort;
3077   }
3078 }
3079
3080 /**
3081  * postSort() runs after sorting has been performed. For StableMap, postSort()
3082  * handles rewiring the linked list according to the results of the sort.
3083  */
3084 void c_StableMap::postSort(Bucket** buffer) {
3085   uint last = m_size-1;
3086   Bucket* b = m_pListHead = buffer[0];
3087   b->pListLast = nullptr;
3088   for (uint i = 0; i < last; ++i) {
3089     Bucket* bNext = buffer[i+1];
3090     b->pListNext = bNext;
3091     bNext->pListLast = b;
3092     b = bNext;
3093   }
3094   m_pListTail = b;
3095   b->pListNext = nullptr;
3096 }
3097
3098 #define SORT_CASE(flag, cmp_type, acc_type) \
3099   case flag: { \
3100     if (ascending) { \
3101       cmp_type##Compare<acc_type, flag, true> comp; \
3102       HPHP::Sort::sort(buffer, buffer + m_size, comp); \
3103     } else { \
3104       cmp_type##Compare<acc_type, flag, false> comp; \
3105       HPHP::Sort::sort(buffer, buffer + m_size, comp); \
3106     } \
3107     break; \
3108   }
3109 #define SORT_CASE_BLOCK(cmp_type, acc_type) \
3110   switch (sort_flags) { \
3111     default: /* fall through to SORT_REGULAR case */ \
3112     SORT_CASE(SORT_REGULAR, cmp_type, acc_type) \
3113     SORT_CASE(SORT_NUMERIC, cmp_type, acc_type) \
3114     SORT_CASE(SORT_STRING, cmp_type, acc_type) \
3115     SORT_CASE(SORT_LOCALE_STRING, cmp_type, acc_type) \
3116     SORT_CASE(SORT_NATURAL, cmp_type, acc_type) \
3117     SORT_CASE(SORT_NATURAL_CASE, cmp_type, acc_type) \
3118   }
3119 #define CALL_SORT(acc_type) \
3120   if (flav == StringSort) { \
3121     SORT_CASE_BLOCK(StrElm, acc_type) \
3122   } else if (flav == IntegerSort) { \
3123     SORT_CASE_BLOCK(IntElm, acc_type) \
3124   } else { \
3125     SORT_CASE_BLOCK(Elm, acc_type) \
3126   }
3127 #define SORT_BODY(acc_type) \
3128   do { \
3129     if (!m_size) { \
3130       return; \
3131     } \
3132     Bucket** buffer = (Bucket**)smart_malloc(m_size * sizeof(Bucket*)); \
3133     SortFlavor flav = preSort<acc_type>(buffer, acc_type(), true); \
3134     try { \
3135       CALL_SORT(acc_type); \
3136     } catch (...) { \
3137       postSort(buffer); \
3138       smart_free(buffer); \
3139       throw; \
3140     } \
3141     postSort(buffer); \
3142     smart_free(buffer); \
3143   } while(0)
3144
3145 void c_StableMap::asort(int sort_flags, bool ascending) {
3146   SORT_BODY(StableMapValAccessor);
3147 }
3148
3149 void c_StableMap::ksort(int sort_flags, bool ascending) {
3150   SORT_BODY(StableMapKeyAccessor);
3151 }
3152
3153 #undef SORT_CASE
3154 #undef SORT_CASE_BLOCK
3155 #undef CALL_SORT
3156 #undef SORT_BODY
3157
3158 #define USER_SORT_BODY(acc_type)                                        \
3159   do {                                                                  \
3160     if (!m_size) {                                                      \
3161       return;                                                           \
3162     }                                                                   \
3163     Bucket** buffer = (Bucket**)smart_malloc(m_size * sizeof(Bucket*)); \
3164     preSort<acc_type>(buffer, acc_type(), false);                       \
3165     ElmUCompare<acc_type> comp;                                         \
3166     CallCtx ctx;                                                        \
3167     Transl::CallerFrame cf;                                         \
3168     vm_decode_function(cmp_function, cf(), false, ctx);                 \
3169     comp.ctx = &ctx;                                                    \
3170     try {                                                               \
3171       HPHP::Sort::sort(buffer, buffer + m_size, comp);                  \
3172     } catch (...) {                                                     \
3173       postSort(buffer);                                                 \
3174       smart_free(buffer);                                               \
3175       throw;                                                            \
3176     }                                                                   \
3177     postSort(buffer);                                                   \
3178     smart_free(buffer);                                                 \
3179   } while (0)
3180
3181 void c_StableMap::uasort(CVarRef cmp_function) {
3182   USER_SORT_BODY(StableMapValAccessor);
3183 }
3184
3185 void c_StableMap::uksort(CVarRef cmp_function) {
3186   USER_SORT_BODY(StableMapKeyAccessor);
3187 }
3188
3189 #undef USER_SORT_BODY
3190
3191 void c_StableMap::throwBadKeyType() {
3192   Object e(SystemLib::AllocInvalidArgumentExceptionObject(
3193     "Only integer keys and string keys may be used with StableMaps"));
3194   throw e;
3195 }
3196
3197 c_StableMap::Bucket::~Bucket() {
3198   if (hasStrKey() && skey->decRefCount() == 0) {
3199     DELETE(StringData)(skey);
3200   }
3201   tvRefcountedDecRef(&data);
3202 }
3203
3204 void c_StableMap::Bucket::dump() {
3205   printf("c_StableMap::Bucket: %" PRIx64 ", %p, %p, %p\n",
3206          hashKey(), pListNext, pListLast, pNext);
3207   if (hasStrKey()) {
3208     skey->dump();
3209   }
3210   tvAsCVarRef(&data).dump();
3211 }
3212
3213 TypedValue* c_StableMap::OffsetGet(ObjectData* obj, TypedValue* key) {
3214   assert(key->m_type != KindOfRef);
3215   auto smp = static_cast<c_StableMap*>(obj);
3216   if (key->m_type == KindOfInt64) {
3217     return smp->at(key->m_data.num);
3218   }
3219   if (IS_STRING_TYPE(key->m_type)) {
3220     return smp->at(key->m_data.pstr);
3221   }
3222   throwBadKeyType();
3223   return nullptr;
3224 }
3225
3226 void c_StableMap::OffsetSet(ObjectData* obj, TypedValue* key, TypedValue* val) {
3227   assert(key->m_type != KindOfRef);
3228   assert(val->m_type != KindOfRef);
3229   auto smp = static_cast<c_StableMap*>(obj);
3230   if (key->m_type == KindOfInt64) {
3231     smp->set(key->m_data.num, val);
3232     return;
3233   }
3234   if (IS_STRING_TYPE(key->m_type)) {
3235     smp->set(key->m_data.pstr, val);
3236     return;
3237   }
3238   throwBadKeyType();
3239 }
3240
3241 bool c_StableMap::OffsetIsset(ObjectData* obj, TypedValue* key) {
3242   assert(key->m_type != KindOfRef);
3243   auto smp = static_cast<c_StableMap*>(obj);
3244   TypedValue* result;
3245   if (key->m_type == KindOfInt64) {
3246     result = smp->get(key->m_data.num);
3247   } else if (IS_STRING_TYPE(key->m_type)) {
3248     result = smp->get(key->m_data.pstr);
3249   } else {
3250     throwBadKeyType();
3251     result = nullptr;
3252   }
3253   return result ? isset(tvAsCVarRef(result)) : false;
3254 }
3255
3256 bool c_StableMap::OffsetEmpty(ObjectData* obj, TypedValue* key) {
3257   assert(key->m_type != KindOfRef);
3258   auto smp = static_cast<c_StableMap*>(obj);
3259   TypedValue* result;
3260   if (key->m_type == KindOfInt64) {
3261     result = smp->get(key->m_data.num);
3262   } else if (IS_STRING_TYPE(key->m_type)) {
3263     result = smp->get(key->m_data.pstr);
3264   } else {
3265     throwBadKeyType();
3266     result = nullptr;
3267   }
3268   return result ? empty(tvAsCVarRef(result)) : true;
3269 }
3270
3271 bool c_StableMap::OffsetContains(ObjectData* obj, TypedValue* key) {
3272   assert(key->m_type != KindOfRef);
3273   auto smp = static_cast<c_StableMap*>(obj);
3274   if (key->m_type == KindOfInt64) {
3275     return smp->contains(key->m_data.num);
3276   } else if (IS_STRING_TYPE(key->m_type)) {
3277     return smp->contains(key->m_data.pstr);
3278   } else {
3279     throwBadKeyType();
3280     return false;
3281   }
3282 }
3283
3284 void c_StableMap::OffsetAppend(ObjectData* obj, TypedValue* val) {
3285   assert(val->m_type != KindOfRef);
3286   auto smp = static_cast<c_StableMap*>(obj);
3287   smp->add(val);
3288 }
3289
3290 void c_StableMap::OffsetUnset(ObjectData* obj, TypedValue* key) {
3291   assert(key->m_type != KindOfRef);
3292   auto smp = static_cast<c_StableMap*>(obj);
3293   if (key->m_type == KindOfInt64) {
3294     smp->remove(key->m_data.num);
3295     return;
3296   }
3297   if (IS_STRING_TYPE(key->m_type)) {
3298     smp->remove(key->m_data.pstr);
3299     return;
3300   }
3301   throwBadKeyType();
3302 }
3303
3304 bool c_StableMap::Equals(ObjectData* obj1, ObjectData* obj2) {
3305   auto smp1 = static_cast<c_StableMap*>(obj1);
3306   auto smp2 = static_cast<c_StableMap*>(obj2);
3307   if (smp1->m_size != smp2->m_size) return false;
3308   auto p1 = smp1->m_pListHead;
3309   auto p2 = smp2->m_pListHead;
3310   for (; p1; p1 = p1->pListNext, p2 = p2->pListNext) {
3311     assert(p2);
3312     // Check if the keys are identical (===)
3313     if (p1->hasIntKey()) {
3314       if (!p2->hasIntKey()) return false;
3315       if (p1->ikey != p2->ikey) return false;
3316     } else {
3317       assert(p1->hasStrKey());
3318       if (!p2->hasStrKey()) return false;
3319       if (!p1->skey->same(p2->skey)) return false;
3320     }
3321     // Compare the values using equals (==)
3322     if (!equal(tvAsCVarRef(&p1->data), tvAsCVarRef(&p2->data))) {
3323       return false;
3324     }
3325   }
3326   return true;
3327 }
3328
3329 void c_StableMap::Unserialize(ObjectData* obj,
3330                               VariableUnserializer* uns,
3331                               int64_t sz,
3332                               char type) {
3333   if (type != 'K') {
3334     throw Exception("StableMap does not support the '%c' serialization "
3335                     "format", type);
3336   }
3337   auto smp = static_cast<c_StableMap*>(obj);
3338   smp->reserve(sz);
3339   for (int64_t i = 0; i < sz; ++i) {
3340     Variant k;
3341     k.unserialize(uns, Uns::ColKeyMode);
3342     Bucket* p;
3343     uint nIndex;
3344     if (k.isInteger()) {
3345       auto h = k.toInt64();
3346       p = smp->find(h);
3347       if (UNLIKELY(p != nullptr)) goto do_unserialize;
3348       p = NEW(Bucket)();
3349       p->setIntKey(h);
3350       nIndex = (h & smp->m_nTableMask);
3351     } else if (k.isString()) {
3352       auto key = k.getStringData();
3353       auto h = key->hash();
3354       p = smp->find(key->data(), key->size(), h);
3355       if (UNLIKELY(p != nullptr)) goto do_unserialize;
3356       p = NEW(Bucket)();
3357       p->setStrKey(key, h);
3358       nIndex = (h & smp->m_nTableMask);
3359     } else {
3360       throw Exception("Invalid key");
3361     }
3362     ++smp->m_size;
3363     p->data.m_type = KindOfNull;
3364     p->pNext = smp->m_arBuckets[nIndex];
3365     smp->m_arBuckets[nIndex] = p;
3366     CONNECT_TO_GLOBAL_DLLIST(smp, p);
3367 do_unserialize:
3368     tvAsVariant(&p->data).unserialize(uns, Uns::ColValueMode);
3369   }
3370 }
3371
3372 #undef CONNECT_TO_GLOBAL_DLLIST
3373
3374 c_StableMapIterator::c_StableMapIterator(Class* cb) :
3375     ExtObjectData(cb) {
3376 }
3377
3378 c_StableMapIterator::~c_StableMapIterator() {
3379 }
3380
3381 void c_StableMapIterator::t___construct() {
3382 }
3383
3384 Variant c_StableMapIterator::t_current() {
3385   c_StableMap* smp = m_obj.get();
3386   if (UNLIKELY(m_version != smp->getVersion())) {
3387     throw_collection_modified();
3388   }
3389   if (!m_pos) {
3390     throw_iterator_not_valid();
3391   }
3392   return smp->iter_value(m_pos);
3393 }
3394
3395 Variant c_StableMapIterator::t_key() {
3396   c_StableMap* smp = m_obj.get();
3397   if (UNLIKELY(m_version != smp->getVersion())) {
3398     throw_collection_modified();
3399   }
3400   if (!m_pos) {
3401     throw_iterator_not_valid();
3402   }
3403   return smp->iter_key(m_pos);
3404 }
3405
3406 bool c_StableMapIterator::t_valid() {
3407   return m_pos != 0;
3408 }
3409
3410 void c_StableMapIterator::t_next() {
3411   c_StableMap* smp = m_obj.get();
3412   if (UNLIKELY(m_version != smp->getVersion())) {
3413     throw_collection_modified();
3414   }
3415   m_pos = smp->iter_next(m_pos);
3416 }
3417
3418 void c_StableMapIterator::t_rewind() {
3419   c_StableMap* smp = m_obj.get();
3420   if (UNLIKELY(m_version != smp->getVersion())) {
3421     throw_collection_modified();
3422   }
3423   m_pos = smp->iter_begin();
3424 }
3425
3426 ///////////////////////////////////////////////////////////////////////////////
3427
3428 static const char emptySetSlot[sizeof(c_Set::Bucket)] = { 0 };
3429
3430 c_Set::c_Set(Class* cb) :
3431     ExtObjectDataFlags<ObjectData::SetAttrInit|
3432                        ObjectData::UseGet|
3433                        ObjectData::UseSet|
3434                        ObjectData::UseIsset|
3435                        ObjectData::UseUnset>(cb),
3436     m_size(0), m_load(0), m_nLastSlot(0), m_version(0) {
3437   m_data = (Bucket*)emptySetSlot;
3438 }
3439
3440 c_Set::~c_Set() {
3441   deleteBuckets();
3442   freeData();
3443 }
3444
3445 void c_Set::freeData() {
3446   if (m_data != (Bucket*)emptySetSlot) {
3447     smart_free(m_data);
3448   }
3449   m_data = (Bucket*)emptySetSlot;
3450 }
3451
3452 void c_Set::deleteBuckets() {
3453   if (!m_size) return;
3454   for (uint i = 0; i <= m_nLastSlot; ++i) {
3455     Bucket& p = m_data[i];
3456     if (p.validValue()) {
3457       tvRefcountedDecRef(&p.data);
3458     }
3459   }
3460 }
3461
3462 void c_Set::t___construct(CVarRef iterable /* = null_variant */) {
3463   if (!iterable.isInitialized()) {
3464     return;
3465   }
3466   size_t sz;
3467   ArrayIter iter = getArrayIterHelper(iterable, sz);
3468   for (; iter; ++iter) {
3469     Variant v = iter.second();
3470     if (v.isInteger()) {
3471       update(v.toInt64());
3472     } else if (v.isString()) {
3473       update(v.getStringData());
3474     } else {
3475       throwBadValueType();
3476     }
3477   }
3478 }
3479
3480 Array c_Set::toArrayImpl() const {
3481   ArrayInit ai(m_size, ArrayInit::vectorInit);
3482   for (uint i = 0; i <= m_nLastSlot; ++i) {
3483     Bucket& p = m_data[i];
3484     if (p.validValue()) {
3485       ai.set(tvAsCVarRef(&p.data));
3486     }
3487   }
3488   return ai.create();
3489 }
3490
3491 Array c_Set::o_toArray() const {
3492   check_collection_cast_to_array();
3493   return toArrayImpl();
3494 }
3495
3496 ObjectData* c_Set::clone() {
3497   ObjectData* obj = ObjectData::clone();
3498   auto target = static_cast<c_Set*>(obj);
3499
3500   if (!m_size) return obj;
3501
3502   assert(m_nLastSlot != 0);
3503   target->m_size = m_size;
3504   target->m_load = m_load;
3505   target->m_nLastSlot = m_nLastSlot;
3506   target->m_data = (Bucket*)smart_malloc(numSlots() * sizeof(Bucket));
3507   memcpy(target->m_data, m_data, numSlots() * sizeof(Bucket));
3508
3509   for (uint i = 0; i <= m_nLastSlot; ++i) {
3510     Bucket& p = m_data[i];
3511     if (p.validValue()) {
3512       tvRefcountedIncRef(&p.data);
3513     }
3514   }
3515
3516   return obj;
3517 }
3518
3519 Object c_Set::t_add(CVarRef val) {
3520   TypedValue* tv = cvarToCell(&val);
3521   add(tv);
3522   return this;
3523 }
3524
3525 Object c_Set::t_addall(CVarRef iterable) {
3526   size_t sz;
3527   ArrayIter iter = getArrayIterHelper(iterable, sz);
3528   for (; iter; ++iter) {
3529     Variant v = iter.second();
3530     TypedValue* tv = cvarToCell(&v);
3531     add(tv);
3532   }
3533   return this;
3534 }
3535
3536 Object c_Set::t_clear() {
3537   deleteBuckets();
3538   freeData();
3539   m_size = 0;
3540   m_load = 0;
3541   m_nLastSlot = 0;
3542   m_data = (Bucket*)emptySetSlot;
3543   return this;
3544 }
3545
3546 bool c_Set::t_isempty() {
3547   return (m_size == 0);
3548 }
3549
3550 int64_t c_Set::t_count() {
3551   return m_size;
3552 }
3553
3554 Object c_Set::t_items() {
3555   return SystemLib::AllocIterableViewObject(this);
3556 }
3557
3558 Object c_Set::t_view() {
3559   return SystemLib::AllocIterableViewObject(this);
3560 }
3561
3562 bool c_Set::t_contains(CVarRef key) {
3563   DataType t = key.getType();
3564   if (t == KindOfInt64) {
3565     return contains(key.toInt64());
3566   }
3567   if (IS_STRING_TYPE(t)) {
3568     return contains(key.getStringData());
3569   }
3570   throwBadValueType();
3571   return false;
3572 }
3573
3574 Object c_Set::t_remove(CVarRef key) {
3575   DataType t = key.getType();
3576   if (t == KindOfInt64) {
3577     remove(key.toInt64());
3578   } else if (IS_STRING_TYPE(t)) {
3579     remove(key.getStringData());
3580   } else {
3581     throwBadValueType();
3582   }
3583   return this;
3584 }
3585
3586 Array c_Set::t_toarray() {
3587   return toArrayImpl();
3588 }
3589
3590 Object c_Set::t_getiterator() {
3591   c_SetIterator* it = NEWOBJ(c_SetIterator)();
3592   it->m_obj = this;
3593   it->m_pos = iter_begin();
3594   it->m_version = getVersion();
3595   return it;
3596 }
3597
3598 Object c_Set::t_map(CVarRef callback) {
3599   CallCtx ctx;
3600   vm_decode_function(callback, nullptr, false, ctx);
3601   if (!ctx.func) {
3602     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
3603       "Parameter must be a valid callback"));
3604     throw e;
3605   }
3606   c_Set* st;
3607   Object obj = st = NEWOBJ(c_Set)();
3608   if (!m_size) return obj;
3609   assert(m_nLastSlot != 0);
3610   st->m_size = m_size;
3611   st->m_load = m_load;
3612   st->m_nLastSlot = 0;
3613   st->m_data = (Bucket*)smart_malloc(numSlots() * sizeof(Bucket));
3614   // We need to zero out the first slot in case an exception
3615   // is thrown during the first iteration, because ~c_Set()
3616   // will decRef all slots up to (and including) m_nLastSlot.
3617   st->m_data[0].data.m_type = (DataType)0;
3618   for (uint i = 0; i <= m_nLastSlot; st->m_nLastSlot = i++) {
3619     Bucket& p = m_data[i];
3620     Bucket& np = st->m_data[i];
3621     if (!p.validValue()) {
3622       np.data.m_type = p.data.m_type;
3623       continue;
3624     }
3625     TypedValue* tv = &np.data;
3626     int32_t version = m_version;
3627     TypedValue args[1];
3628     tvDup(&p.data, args + 0);
3629     g_vmContext->invokeFuncFew(tv, ctx, 1, args);
3630     if (UNLIKELY(version != m_version)) {
3631       tvRefcountedDecRef(tv);
3632       throw_collection_modified();
3633     }
3634     np.data.hash() = p.data.hash();
3635   }
3636   return obj;
3637 }
3638
3639 Object c_Set::t_filter(CVarRef callback) {
3640   CallCtx ctx;
3641   vm_decode_function(callback, nullptr, false, ctx);
3642   if (!ctx.func) {
3643     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
3644       "Parameter must be a valid callback"));
3645     throw e;
3646   }
3647   c_Set* st;
3648   Object obj = st = NEWOBJ(c_Set)();
3649   if (!m_size) return obj;
3650   for (uint i = 0; i <= m_nLastSlot; ++i) {
3651     Bucket& p = m_data[i];
3652     if (!p.validValue()) continue;
3653     Variant ret;
3654     int32_t version = m_version;
3655     TypedValue args[1];
3656     tvDup(&p.data, args + 0);
3657     g_vmContext->invokeFuncFew(ret.asTypedValue(), ctx, 1, args);
3658     if (UNLIKELY(version != m_version)) {
3659       throw_collection_modified();
3660     }
3661     if (!ret.toBoolean()) continue;
3662     if (p.hasInt()) {
3663       st->update(p.data.m_data.num);
3664     } else {
3665       assert(p.hasStr());
3666       st->update(p.data.m_data.pstr);
3667     }
3668   }
3669   return obj;
3670 }
3671
3672 Object c_Set::t_zip(CVarRef iterable) {
3673   size_t sz;
3674   ArrayIter iter = getArrayIterHelper(iterable, sz);
3675   if (m_size && iter) {
3676     // At present, Sets only support int values and string values,
3677     // so if this Set is non empty and the iterable is non empty
3678     // the zip operation will always fail
3679     throwBadValueType();
3680   }
3681   Object obj = NEWOBJ(c_Set)();
3682   return obj;
3683 }
3684
3685 Object c_Set::ti_fromitems(CVarRef iterable) {
3686   size_t sz;
3687   ArrayIter iter = getArrayIterHelper(iterable, sz);
3688   c_Set* target;
3689   Object ret = target = NEWOBJ(c_Set)();
3690   for (; iter; ++iter) {
3691     Variant v = iter.second();
3692     if (v.isInteger()) {
3693       target->update(v.toInt64());
3694     } else if (v.isString()) {
3695       target->update(v.getStringData());
3696     } else {
3697       throwBadValueType();
3698     }
3699   }
3700   return ret;
3701 }
3702
3703 Object c_Set::ti_fromarray(CVarRef arr) {
3704   if (!arr.isArray()) {
3705     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
3706       "Parameter arr must be an array"));
3707     throw e;
3708   }
3709   c_Set* st;
3710   Object ret = st = NEWOBJ(c_Set)();
3711   ArrayData* ad = arr.getArrayData();
3712   for (ssize_t pos = ad->iter_begin(); pos != ArrayData::invalid_index;
3713        pos = ad->iter_advance(pos)) {
3714     CVarRef v = ad->getValueRef(pos);
3715     if (v.isInteger()) {
3716       st->update(v.toInt64());
3717     } else if (v.isString()) {
3718       st->update(v.getStringData());
3719     } else {
3720       throwBadValueType();
3721     }
3722   }
3723   return ret;
3724 }
3725
3726 Object c_Set::t_discard(CVarRef key) {
3727   return t_remove(key);
3728 }
3729
3730 Object c_Set::t_difference(CVarRef iterable) {
3731   if (!iterable.isObject()) {
3732     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
3733       "Parameter iterable must be an instance of Iterable"));
3734     throw e;
3735   }
3736   size_t sz;
3737   ArrayIter iter = getArrayIterHelper(iterable, sz);
3738   for (; iter; ++iter) {
3739     t_remove(iter.second());
3740   }
3741   return this;
3742 }
3743
3744 Object c_Set::t_updatefromarrayvalues(CVarRef arr) {
3745   if (!arr.isArray()) {
3746     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
3747       "Parameter arr must be an array"));
3748     throw e;
3749   }
3750   size_t sz;
3751   ArrayIter iter = getArrayIterHelper(arr, sz);
3752   for (; iter; ++iter) {
3753     t_add(iter.second());
3754   }
3755   return this;
3756 }
3757
3758 Object c_Set::t_updatefromiterablevalues(CVarRef iterable) {
3759   if (!iterable.isObject()) {
3760     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
3761       "Parameter iterable must be an instance of Iterable"));
3762     throw e;
3763   }
3764   size_t sz;
3765   ArrayIter iter = getArrayIterHelper(iterable, sz);
3766   for (; iter; ++iter) {
3767     t_add(iter.second());
3768   }
3769   return this;
3770 }
3771
3772 Object c_Set::ti_fromarrays(int _argc,
3773                             CArrRef _argv /* = null_array */) {
3774   c_Set* st;
3775   Object ret = st = NEWOBJ(c_Set)();
3776   for (ArrayIter iter(_argv); iter; ++iter) {
3777     Variant arr = iter.second();
3778     if (!arr.isArray()) {
3779       Object e(SystemLib::AllocInvalidArgumentExceptionObject(
3780         "Parameters must be arrays"));
3781       throw e;
3782     }
3783     ArrayData* ad = arr.getArrayData();
3784     for (ssize_t pos = ad->iter_begin(); pos != ArrayData::invalid_index;
3785          pos = ad->iter_advance(pos)) {
3786       st->t_add(ad->getValueRef(pos));
3787     }
3788   }
3789   return ret;
3790 }
3791
3792 Object c_Set::ti_fromiterablevalues(CVarRef iterable) {
3793   if (!iterable.isObject()) {
3794     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
3795       "Parameter iterable must be an instance of Iterable"));
3796     throw e;
3797   }
3798   size_t sz;
3799   ArrayIter iter = getArrayIterHelper(iterable, sz);
3800   c_Set* st;
3801   Object ret = st = NEWOBJ(c_Set)();
3802   for (; iter; ++iter) {
3803     st->t_add(iter.second());
3804   }
3805   return ret;
3806 }
3807
3808 void c_Set::throwOOB(int64_t val) {
3809   throwIntOOB(val);
3810 }
3811
3812 void c_Set::throwOOB(StringData* val) {
3813   throwStrOOB(val);
3814 }
3815
3816 void c_Set::throwNoIndexAccess() {
3817   Object e(SystemLib::AllocRuntimeExceptionObject(
3818     "Cannot use object of type Set as array"));
3819   throw e;
3820 }
3821
3822 void c_Set::add(TypedValue* val) {
3823   if (val->m_type == KindOfInt64) {
3824     update(val->m_data.num);
3825   } else if (IS_STRING_TYPE(val->m_type)) {
3826     update(val->m_data.pstr);
3827   } else {
3828     throwBadValueType();
3829   }
3830 }
3831
3832 #define STRING_HASH(x)   (int32_t(x) | 0x80000000)
3833
3834 bool inline hitString(const c_Set::Bucket* p, const char* k,
3835                          int len, int32_t hash) ALWAYS_INLINE;
3836 bool inline hitString(const c_Set::Bucket* p, const char* k,
3837                          int len, int32_t hash) {
3838   assert(p->validValue());
3839   if (p->hasInt()) return false;
3840   const char* data = p->data.m_data.pstr->data();
3841   return data == k || (p->hash() == hash &&
3842                        p->data.m_data.pstr->size() == len &&
3843                        memcmp(data, k, len) == 0);
3844 }
3845
3846 bool inline hitInt(const c_Set::Bucket* p, int64_t ki) ALWAYS_INLINE;
3847 bool inline hitInt(const c_Set::Bucket* p, int64_t ki) {
3848   assert(p->validValue());
3849   return p->hasInt() && p->data.m_data.num == ki;
3850 }
3851
3852 #define FIND_BODY(h0, hit) \
3853   size_t tableMask = m_nLastSlot; \
3854   size_t probeIndex = size_t(h0) & tableMask; \
3855   Bucket* p = fetchBucket(probeIndex); \
3856   if (LIKELY(p->validValue() && (hit))) { \
3857     return p; \
3858   } \
3859   if (LIKELY(p->empty())) { \
3860     return nullptr; \
3861   } \
3862   for (size_t i = 1;; ++i) { \
3863     assert(i <= tableMask); \
3864     probeIndex = (probeIndex + i) & tableMask; \
3865     assert(((size_t(h0)+((i + i*i) >> 1)) & tableMask) == probeIndex); \
3866     p = fetchBucket(probeIndex); \
3867     if (p->validValue() && (hit)) { \
3868       return p; \
3869     } \
3870     if (p->empty()) { \
3871       return nullptr; \
3872     } \
3873   }
3874
3875 #define FIND_FOR_INSERT_BODY(h0, hit) \
3876   size_t tableMask = m_nLastSlot; \
3877   size_t probeIndex = size_t(h0) & tableMask; \
3878   Bucket* p = fetchBucket(h0 & tableMask); \
3879   if (LIKELY((p->validValue() && (hit)) || \
3880              p->empty())) { \
3881     return p; \
3882   } \
3883   Bucket* ts = nullptr; \
3884   for (size_t i = 1;; ++i) { \
3885     if (UNLIKELY(p->tombstone() && !ts)) { \
3886       ts = p; \
3887     } \
3888     assert(i <= tableMask); \
3889     probeIndex = (probeIndex + i) & tableMask; \
3890     assert(((size_t(h0)+((i + i*i) >> 1)) & tableMask) == probeIndex); \
3891     p = fetchBucket(probeIndex); \
3892     if (LIKELY(p->validValue() && (hit))) { \
3893       return p; \
3894     } \
3895     if (LIKELY(p->empty())) { \
3896       if (LIKELY(!ts)) { \
3897         return p; \
3898       } \
3899       return ts; \
3900     } \
3901   }
3902
3903 c_Set::Bucket* c_Set::find(int64_t h) const {
3904   FIND_BODY(h, hitInt(p, h));
3905 }
3906
3907 c_Set::Bucket* c_Set::find(const char* k, int len, strhash_t prehash) const {
3908   FIND_BODY(prehash, hitString(p, k, len, STRING_HASH(prehash)));
3909 }
3910
3911 c_Set::Bucket* c_Set::findForInsert(int64_t h) const {
3912   FIND_FOR_INSERT_BODY(h, hitInt(p, h));
3913 }
3914
3915 c_Set::Bucket* c_Set::findForInsert(const char* k, int len,
3916                                     strhash_t prehash) const {
3917   FIND_FOR_INSERT_BODY(prehash, hitString(p, k, len, STRING_HASH(prehash)));
3918 }
3919
3920 // findForNewInsert() is only safe to use if you know for sure that the
3921 // value is not already present in the Set.
3922 inline ALWAYS_INLINE
3923 c_Set::Bucket* c_Set::findForNewInsert(size_t h0) const {
3924   size_t tableMask = m_nLastSlot;
3925   size_t probeIndex = h0 & tableMask;
3926   Bucket* p = fetchBucket(probeIndex);
3927   if (LIKELY(p->empty())) {
3928     return p;
3929   }
3930   for (size_t i = 1;; ++i) {
3931     assert(i <= tableMask);
3932     probeIndex = (probeIndex + i) & tableMask;
3933     assert(((size_t(h0)+((i + i*i) >> 1)) & tableMask) == probeIndex);
3934     p = fetchBucket(probeIndex);
3935     if (LIKELY(p->empty())) {
3936       return p;
3937     }
3938   }
3939 }
3940
3941 #undef STRING_HASH
3942 #undef FIND_BODY
3943 #undef FIND_FOR_INSERT_BODY
3944
3945 void c_Set::update(int64_t h) {
3946   Bucket* p = findForInsert(h);
3947   assert(p);
3948   if (p->validValue()) {
3949     return;
3950   }
3951   ++m_version;
3952   ++m_size;
3953   if (!p->tombstone()) {
3954     if (UNLIKELY(++m_load >= computeMaxLoad())) {
3955       adjustCapacity();
3956       p = findForInsert(h);
3957       assert(p);
3958     }
3959   }
3960   p->setInt(h);
3961 }
3962
3963 void c_Set::update(StringData *key) {
3964   strhash_t h = key->hash();
3965   Bucket* p = findForInsert(key->data(), key->size(), h);
3966   assert(p);
3967   if (p->validValue()) {
3968     return;
3969   }
3970   ++m_version;
3971   ++m_size;
3972   if (!p->tombstone()) {
3973     if (UNLIKELY(++m_load >= computeMaxLoad())) {
3974       adjustCapacity();
3975       p = findForInsert(key->data(), key->size(), h);
3976       assert(p);
3977     }
3978   }
3979   p->setStr(key, h);
3980 }
3981
3982 void c_Set::erase(Bucket* p) {
3983   if (!p) {
3984     return;
3985   }
3986   if (p->validValue()) {
3987     m_size--;
3988     tvRefcountedDecRef(&p->data);
3989     p->data.m_type = (DataType)KindOfTombstone;
3990     if (m_size < computeMinElements() && m_size) {
3991       adjustCapacity();
3992     }
3993   }
3994 }
3995
3996 void c_Set::adjustCapacityImpl(int64_t sz) {
3997   ++m_version;
3998   if (sz < 2) {
3999     if (sz <= 0) return;
4000     sz = 2;
4001   }
4002   if (m_nLastSlot == 0) {
4003     assert(m_data == (Bucket*)emptySetSlot);
4004     m_nLastSlot = Util::roundUpToPowerOfTwo(sz << 1) - 1;
4005     m_data = (Bucket*)smart_calloc(numSlots(), sizeof(Bucket));
4006     return;
4007   }
4008   size_t oldNumSlots = numSlots();
4009   m_nLastSlot = Util::roundUpToPowerOfTwo(sz << 1) - 1;
4010   m_load = m_size;
4011   Bucket* oldBuckets = m_data;
4012   m_data = (Bucket*)smart_calloc(numSlots(), sizeof(Bucket));
4013   for (uint i = 0; i < oldNumSlots; ++i) {
4014     Bucket* p = &oldBuckets[i];
4015     if (p->validValue()) {
4016       Bucket* np =
4017         findForNewInsert(p->hasInt() ? p->data.m_data.num : p->hash());
4018       memcpy(np, p, sizeof(Bucket));
4019     }
4020   }
4021   smart_free(oldBuckets);
4022 }
4023
4024 ssize_t c_Set::iter_begin() const {
4025   if (!m_size) return 0;
4026   for (uint i = 0; i <= m_nLastSlot; ++i) {
4027     Bucket* p = fetchBucket(i);
4028     if (p->validValue()) {
4029       return reinterpret_cast<ssize_t>(p);
4030     }
4031   }
4032   return 0;
4033 }
4034
4035 ssize_t c_Set::iter_next(ssize_t pos) const {
4036   if (pos == 0) {
4037     return 0;
4038   }
4039   Bucket* p = reinterpret_cast<Bucket*>(pos);
4040   Bucket* pLast = fetchBucket(m_nLastSlot);
4041   ++p;
4042   while (p <= pLast) {
4043     if (p->validValue()) {
4044       return reinterpret_cast<ssize_t>(p);
4045     }
4046     ++p;
4047   }
4048   return 0;
4049 }
4050
4051 ssize_t c_Set::iter_prev(ssize_t pos) const {
4052   if (pos == 0) {
4053     return 0;
4054   }
4055   Bucket* p = reinterpret_cast<Bucket*>(pos);
4056   Bucket* pStart = m_data;
4057   --p;
4058   while (p >= pStart) {
4059     if (p->validValue()) {
4060       return reinterpret_cast<ssize_t>(p);
4061     }
4062     --p;
4063   }
4064   return 0;
4065 }
4066
4067 Variant c_Set::iter_value(ssize_t pos) const {
4068   assert(pos);
4069   Bucket* p = reinterpret_cast<Bucket*>(pos);
4070   return tvAsCVarRef(&p->data);
4071 }
4072
4073 void c_Set::throwBadValueType() {
4074   Object e(SystemLib::AllocInvalidArgumentExceptionObject(
4075     "Only integer values and string values may be used with Sets"));
4076   throw e;
4077 }
4078
4079 void c_Set::Bucket::dump() {
4080   if (!validValue()) {
4081     printf("c_Set::Bucket: %s\n", (empty() ? "empty" : "tombstone"));
4082     return;
4083   }
4084   printf("c_Set::Bucket: %d\n", hash());
4085   tvAsCVarRef(&data).dump();
4086 }
4087
4088 TypedValue* c_Set::OffsetGet(ObjectData* obj, TypedValue* key) {
4089   c_Set::throwNoIndexAccess();
4090 }
4091
4092 void c_Set::OffsetSet(ObjectData* obj, TypedValue* key, TypedValue* val) {
4093   c_Set::throwNoIndexAccess();
4094 }
4095
4096 bool c_Set::OffsetIsset(ObjectData* obj, TypedValue* key) {
4097   c_Set::throwNoIndexAccess();
4098 }
4099
4100 bool c_Set::OffsetEmpty(ObjectData* obj, TypedValue* key) {
4101   c_Set::throwNoIndexAccess();
4102 }
4103
4104 bool c_Set::OffsetContains(ObjectData* obj, TypedValue* key) {
4105   c_Set::throwNoIndexAccess();
4106 }
4107
4108 void c_Set::OffsetAppend(ObjectData* obj, TypedValue* val) {
4109   assert(val->m_type != KindOfRef);
4110   auto st = static_cast<c_Set*>(obj);
4111   st->add(val);
4112 }
4113
4114 void c_Set::OffsetUnset(ObjectData* obj, TypedValue* key) {
4115   c_Set::throwNoIndexAccess();
4116 }
4117
4118 bool c_Set::Equals(ObjectData* obj1, ObjectData* obj2) {
4119   auto st1 = static_cast<c_Set*>(obj1);
4120   auto st2 = static_cast<c_Set*>(obj2);
4121   if (st1->m_size != st2->m_size) return false;
4122   for (uint i = 0; i <= st1->m_nLastSlot; ++i) {
4123     c_Set::Bucket& p = st1->m_data[i];
4124     if (p.validValue()) {
4125       if (p.hasInt()) {
4126         int64_t key = p.data.m_data.num;
4127         if (!st2->find(key)) return false;
4128       } else {
4129         assert(p.hasStr());
4130         StringData* key = p.data.m_data.pstr;
4131         if (!st2->find(key->data(), key->size(), key->hash())) return false;
4132       }
4133     }
4134   }
4135   return true;
4136 }
4137
4138 void c_Set::Unserialize(ObjectData* obj,
4139                         VariableUnserializer* uns,
4140                         int64_t sz,
4141                         char type) {
4142   if (type != 'V') {
4143     throw Exception("Set does not support the '%c' serialization "
4144                     "format", type);
4145   }
4146   auto st = static_cast<c_Set*>(obj);
4147   st->reserve(sz);
4148   for (int64_t i = 0; i < sz; ++i) {
4149     Variant k;
4150     // When unserializing an element of a Set, we use ColKeyMode for now.
4151     // This will make the unserializer to reserve an id for the element
4152     // but won't allow referencing the element via 'r' or 'R'.
4153     k.unserialize(uns, Uns::ColKeyMode);
4154     Bucket* p;
4155     if (k.isInteger()) {
4156       auto h = k.toInt64();
4157       p = st->findForInsert(h);
4158       if (UNLIKELY(p->validValue())) continue;
4159       p->setInt(h);
4160     } else if (k.isString()) {
4161       auto key = k.getStringData();
4162       auto h = key->hash();
4163       p = st->findForInsert(key->data(), key->size(), h);
4164       if (UNLIKELY(p->validValue())) continue;
4165       p->setStr(key, h);
4166     } else {
4167       throw Exception("Set values must be integers or strings");
4168     }
4169     ++st->m_size;
4170     ++st->m_load;
4171   }
4172 }
4173
4174 c_SetIterator::c_SetIterator(Class* cb) :
4175     ExtObjectData(cb) {
4176 }
4177
4178 c_SetIterator::~c_SetIterator() {
4179 }
4180
4181 void c_SetIterator::t___construct() {
4182 }
4183
4184 Variant c_SetIterator::t_current() {
4185   c_Set* st = m_obj.get();
4186   if (UNLIKELY(m_version != st->getVersion())) {
4187     throw_collection_modified();
4188   }
4189   if (!m_pos) {
4190     throw_iterator_not_valid();
4191   }
4192   return st->iter_value(m_pos);
4193 }
4194
4195 Variant c_SetIterator::t_key() {
4196   return uninit_null();
4197 }
4198
4199 bool c_SetIterator::t_valid() {
4200   return m_pos != 0;
4201 }
4202
4203 void c_SetIterator::t_next() {
4204   c_Set* st = m_obj.get();
4205   if (UNLIKELY(m_version != st->getVersion())) {
4206     throw_collection_modified();
4207   }
4208   m_pos = st->iter_next(m_pos);
4209 }
4210
4211 void c_SetIterator::t_rewind() {
4212   c_Set* st = m_obj.get();
4213   if (UNLIKELY(m_version != st->getVersion())) {
4214     throw_collection_modified();
4215   }
4216   m_pos = st->iter_begin();
4217 }
4218
4219 ///////////////////////////////////////////////////////////////////////////////
4220
4221 c_Pair::c_Pair(Class* cb) :
4222     ExtObjectDataFlags<ObjectData::PairAttrInit|
4223                        ObjectData::UseGet|
4224                        ObjectData::UseSet|
4225                        ObjectData::UseIsset|
4226                        ObjectData::UseUnset>(cb),
4227     m_size(0) {
4228 }
4229
4230 c_Pair::~c_Pair() {
4231   if (LIKELY(m_size == 2)) {
4232     tvRefcountedDecRef(&elm0);
4233     tvRefcountedDecRef(&elm1);
4234     return;
4235   }
4236   if (m_size == 1) {
4237     tvRefcountedDecRef(&elm0);
4238   }
4239 }
4240
4241 void c_Pair::t___construct() {
4242   Object e(SystemLib::AllocRuntimeExceptionObject(
4243     "Pairs cannot be created using the new operator"));
4244   throw e;
4245 }
4246
4247 Array c_Pair::toArrayImpl() const {
4248   ArrayInit ai(2, ArrayInit::vectorInit);
4249   ai.set(tvAsCVarRef(&elm0));
4250   ai.set(tvAsCVarRef(&elm1));
4251   return ai.create();
4252 }
4253
4254 Array c_Pair::o_toArray() const {
4255   check_collection_cast_to_array();
4256   return toArrayImpl();
4257 }
4258
4259 ObjectData* c_Pair::clone() {
4260   auto pair = NEWOBJ(c_Pair)();
4261   pair->incRefCount();
4262   pair->m_size = 2;
4263   tvDup(&elm0, &pair->elm0);
4264   tvDup(&elm1, &pair->elm1);
4265   return pair;
4266 }
4267
4268 bool c_Pair::t_isempty() {
4269   return false;
4270 }
4271
4272 int64_t c_Pair::t_count() {
4273   return 2;
4274 }
4275
4276 Object c_Pair::t_items() {
4277   return SystemLib::AllocIterableViewObject(this);
4278 }
4279
4280 Object c_Pair::t_keys() {
4281   c_Vector* vec;
4282   Object obj = vec = NEWOBJ(c_Vector)();
4283   vec->reserve(2);
4284   vec->m_size = 2;
4285   vec->m_data[0].m_data.num = 0;
4286   vec->m_data[0].m_type = KindOfInt64;
4287   vec->m_data[1].m_data.num = 1;
4288   vec->m_data[1].m_type = KindOfInt64;
4289   return obj;
4290 }
4291
4292 Object c_Pair::t_view() {
4293   return SystemLib::AllocKeyedIterableViewObject(this);
4294 }
4295
4296 Object c_Pair::t_kvzip() {
4297   c_Vector* vec;
4298   Object obj = vec = NEWOBJ(c_Vector)();
4299   vec->reserve(2);
4300   for (uint i = 0; i < 2; ++i) {
4301     c_Pair* pair = NEWOBJ(c_Pair)();
4302     pair->incRefCount();
4303     pair->elm0.m_type = KindOfInt64;
4304     pair->elm0.m_data.num = i;
4305     ++pair->m_size;
4306     pair->add(&getElms()[i]);
4307     vec->m_data[i].m_data.pobj = pair;
4308     vec->m_data[i].m_type = KindOfObject;
4309     ++vec->m_size;
4310   }
4311   return obj;
4312 }
4313
4314 Variant c_Pair::t_at(CVarRef key) {
4315   if (key.isInteger()) {
4316     return tvAsCVarRef(at(key.toInt64()));
4317   }
4318   throwBadKeyType();
4319   return init_null_variant;
4320 }
4321
4322 Variant c_Pair::t_get(CVarRef key) {
4323   if (key.isInteger()) {
4324     TypedValue* tv = get(key.toInt64());
4325     if (tv) {
4326       return tvAsCVarRef(tv);
4327     } else {
4328       return init_null_variant;
4329     }
4330   }
4331   throwBadKeyType();
4332   return init_null_variant;
4333 }
4334
4335 bool c_Pair::t_containskey(CVarRef key) {
4336   if (key.isInteger()) {
4337     return contains(key.toInt64());
4338   }
4339   throwBadKeyType();
4340   return false;
4341 }
4342
4343 Array c_Pair::t_toarray() {
4344   return toArrayImpl();
4345 }
4346
4347 Object c_Pair::t_getiterator() {
4348   c_PairIterator* it = NEWOBJ(c_PairIterator)();
4349   it->m_obj = this;
4350   it->m_pos = 0;
4351   return it;
4352 }
4353
4354 Object c_Pair::t_map(CVarRef callback) {
4355   CallCtx ctx;
4356   vm_decode_function(callback, nullptr, false, ctx);
4357   if (!ctx.func) {
4358     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
4359       "Parameter must be a valid callback"));
4360     throw e;
4361   }
4362   c_Vector* vec;
4363   Object obj = vec = NEWOBJ(c_Vector)();
4364   vec->reserve(2);
4365   for (uint64_t i = 0; i < 2; ++i) {
4366     TypedValue args[1];
4367     tvDup(&getElms()[i], args + 0);
4368     g_vmContext->invokeFuncFew(&vec->m_data[i], ctx, 1, args);
4369     ++vec->m_size;
4370   }
4371   return obj;
4372 }
4373
4374 Object c_Pair::t_filter(CVarRef callback) {
4375   CallCtx ctx;
4376   vm_decode_function(callback, nullptr, false, ctx);
4377   if (!ctx.func) {
4378     Object e(SystemLib::AllocInvalidArgumentExceptionObject(
4379       "Parameter must be a valid callback"));
4380     throw e;
4381   }
4382   c_Vector* vec;
4383   Object obj = vec = NEWOBJ(c_Vector)();
4384   for (uint64_t i = 0; i < 2; ++i) {
4385     Variant ret;
4386     TypedValue args[1];
4387     tvDup(&getElms()[i], args + 0);
4388     g_vmContext->invokeFuncFew(ret.asTypedValue(), ctx, 1, args);
4389     if (ret.toBoolean()) {
4390       vec->add(&getElms()[i]);
4391     }
4392   }
4393   return obj;
4394 }
4395
4396 Object c_Pair::t_zip(CVarRef iterable) {
4397   size_t sz;
4398   ArrayIter iter = getArrayIterHelper(iterable, sz);
4399   c_Vector* vec;
4400   Object obj = vec = NEWOBJ(c_Vector)();
4401   vec->reserve(std::min(sz, size_t(2)));
4402   for (uint64_t i = 0; i < 2 && iter; ++i, ++iter) {
4403     Variant v = iter.second();
4404     if (vec->m_capacity <= vec->m_size) {
4405       vec->grow();
4406     }
4407     c_Pair* pair = NEWOBJ(c_Pair)();
4408     pair->incRefCount();
4409     pair->add(&getElms()[i]);
4410     pair->add(cvarToCell(&v));
4411     vec->m_data[i].m_data.pobj = pair;
4412     vec->m_data[i].m_type = KindOfObject;
4413     ++vec->m_size;
4414   }
4415   return obj;
4416 }
4417
4418 void c_Pair::throwOOB(int64_t key) {
4419   throwIntOOB(key, true);
4420 }
4421
4422 void c_Pair::throwBadKeyType() {
4423   Object e(SystemLib::AllocInvalidArgumentExceptionObject(
4424     "Only integer keys may be used with Pairs"));
4425   throw e;
4426 }
4427
4428 TypedValue* c_Pair::OffsetGet(ObjectData* obj, TypedValue* key) {
4429   assert(key->m_type != KindOfRef);
4430   auto pair = static_cast<c_Pair*>(obj);
4431   if (key->m_type == KindOfInt64) {
4432     return pair->at(key->m_data.num);
4433   }
4434   throwBadKeyType();
4435   return nullptr;
4436 }
4437
4438 void c_Pair::OffsetSet(ObjectData* obj, TypedValue* key, TypedValue* val) {
4439   Object e(SystemLib::AllocRuntimeExceptionObject(
4440     "Cannot assign to an element of a Pair"));
4441   throw e;
4442 }
4443
4444 bool c_Pair::OffsetIsset(ObjectData* obj, TypedValue* key) {
4445   assert(key->m_type != KindOfRef);
4446   auto pair = static_cast<c_Pair*>(obj);
4447   TypedValue* result;
4448   if (key->m_type == KindOfInt64) {
4449     result = pair->get(key->m_data.num);
4450   } else {
4451     throwBadKeyType();
4452     result = nullptr;
4453   }
4454   return result ? isset(tvAsCVarRef(result)) : false;
4455 }
4456
4457 bool c_Pair::OffsetEmpty(ObjectData* obj, TypedValue* key) {
4458   assert(key->m_type != KindOfRef);
4459   auto pair = static_cast<c_Pair*>(obj);
4460   TypedValue* result;
4461   if (key->m_type == KindOfInt64) {
4462     result = pair->get(key->m_data.num);
4463   } else {
4464     throwBadKeyType();
4465     result = nullptr;
4466   }
4467   return result ? empty(tvAsCVarRef(result)) : true;
4468 }
4469
4470 bool c_Pair::OffsetContains(ObjectData* obj, TypedValue* key) {
4471   assert(key->m_type != KindOfRef);
4472   auto pair = static_cast<c_Pair*>(obj);
4473   if (key->m_type == KindOfInt64) {
4474     return pair->contains(key->m_data.num);
4475   } else {
4476     throwBadKeyType();
4477     return false;
4478   }
4479 }
4480
4481 void c_Pair::OffsetAppend(ObjectData* obj, TypedValue* val) {
4482   assert(val->m_type != KindOfRef);
4483   auto pair = static_cast<c_Pair*>(obj);
4484   pair->add(val);
4485 }
4486
4487 void c_Pair::OffsetUnset(ObjectData* obj, TypedValue* key) {
4488   Object e(SystemLib::AllocRuntimeExceptionObject(
4489     "Cannot unset element of a Pair"));
4490   throw e;
4491 }
4492
4493 bool c_Pair::Equals(ObjectData* obj1, ObjectData* obj2) {
4494   auto pair1 = static_cast<c_Pair*>(obj1);
4495   auto pair2 = static_cast<c_Pair*>(obj2);
4496   return equal(tvAsCVarRef(&pair1->elm0), tvAsCVarRef(&pair2->elm0)) &&
4497          equal(tvAsCVarRef(&pair1->elm1), tvAsCVarRef(&pair2->elm1));
4498 }
4499
4500 void c_Pair::Unserialize(ObjectData* obj,
4501                           VariableUnserializer* uns,
4502                           int64_t sz,
4503                           char type) {
4504   assert(sz == 2);
4505   if (type != 'V') {
4506     throw Exception("Pair does not support the '%c' serialization "
4507                     "format", type);
4508   }
4509   auto pair = static_cast<c_Pair*>(obj);
4510   pair->m_size = 2;
4511   pair->elm0.m_type = KindOfNull;
4512   pair->elm1.m_type = KindOfNull;
4513   tvAsVariant(&pair->elm0).unserialize(uns, Uns::ColValueMode);
4514   tvAsVariant(&pair->elm1).unserialize(uns, Uns::ColValueMode);
4515 }
4516
4517 c_PairIterator::c_PairIterator(Class* cb) :
4518     ExtObjectData(cb) {
4519 }
4520
4521 c_PairIterator::~c_PairIterator() {
4522 }
4523
4524 void c_PairIterator::t___construct() {
4525 }
4526
4527 Variant c_PairIterator::t_current() {
4528   c_Pair* pair = m_obj.get();
4529   if (!pair->contains(m_pos)) {
4530     throw_iterator_not_valid();
4531   }
4532   return tvAsCVarRef(&pair->getElms()[m_pos]);
4533 }
4534
4535 Variant c_PairIterator::t_key() {
4536   c_Pair* pair = m_obj.get();
4537   if (!pair->contains(m_pos)) {
4538     throw_iterator_not_valid();
4539   }
4540   return m_pos;
4541 }
4542
4543 bool c_PairIterator::t_valid() {
4544   assert(m_pos >= 0);
4545   c_Pair* pair = m_obj.get();
4546   return pair && (m_pos < ssize_t(2));
4547 }
4548
4549 void c_PairIterator::t_next() {
4550   m_pos++;
4551 }
4552
4553 void c_PairIterator::t_rewind() {
4554   m_pos = 0;
4555 }
4556
4557 ///////////////////////////////////////////////////////////////////////////////
4558
4559 #define COLLECTION_MAGIC_METHODS(cls) \
4560   String c_##cls::t___tostring() { \
4561     return #cls; \
4562   } \
4563   Variant c_##cls::t___get(Variant name) { \
4564     throw_collection_property_exception(); \
4565   } \
4566   Variant c_##cls::t___set(Variant name, Variant value) { \
4567     throw_collection_property_exception(); \
4568   } \
4569   bool c_##cls::t___isset(Variant name) { \
4570     throw_collection_property_exception(); \
4571   } \
4572   Variant c_##cls::t___unset(Variant name) { \
4573     throw_collection_property_exception(); \
4574   }
4575
4576 COLLECTION_MAGIC_METHODS(Vector)
4577 COLLECTION_MAGIC_METHODS(Map)
4578 COLLECTION_MAGIC_METHODS(StableMap)
4579 COLLECTION_MAGIC_METHODS(Set)
4580 COLLECTION_MAGIC_METHODS(Pair)
4581
4582 #undef COLLECTION_MAGIC_METHODS
4583
4584 void collectionSerialize(ObjectData* obj, VariableSerializer* serializer) {
4585   assert(obj->isCollection());
4586   int64_t sz = collectionSize(obj);
4587   if (obj->getCollectionType() == Collection::VectorType ||
4588       obj->getCollectionType() == Collection::SetType ||
4589       obj->getCollectionType() == Collection::PairType) {
4590     serializer->setObjectInfo(obj->o_getClassName(), obj->o_getId(), 'V');
4591     serializer->writeArrayHeader(sz, true);
4592     if (serializer->getType() == VariableSerializer::Serialize ||
4593         serializer->getType() == VariableSerializer::APCSerialize ||
4594         serializer->getType() == VariableSerializer::DebuggerSerialize ||
4595         serializer->getType() == VariableSerializer::VarExport ||
4596         serializer->getType() == VariableSerializer::PHPOutput) {
4597       // For the 'V' serialization format, we don't print out keys
4598       // for Serialize, APCSerialize, DebuggerSerialize
4599       for (ArrayIter iter(obj); iter; ++iter) {
4600         serializer->writeCollectionKeylessPrefix();
4601         serializer->writeArrayValue(iter.second());
4602       }
4603     } else {
4604       for (ArrayIter iter(obj); iter; ++iter) {
4605         if (obj->getCollectionType() != Collection::SetType) {
4606           serializer->writeCollectionKey(iter.first());
4607         } else {
4608           serializer->writeCollectionKeylessPrefix();
4609         }
4610         serializer->writeArrayValue(iter.second());
4611       }
4612     }
4613     serializer->writeArrayFooter();
4614   } else {
4615     assert(obj->getCollectionType() == Collection::MapType ||
4616            obj->getCollectionType() == Collection::StableMapType);
4617     serializer->setObjectInfo(obj->o_getClassName(), obj->o_getId(), 'K');
4618     serializer->writeArrayHeader(sz, false);
4619     for (ArrayIter iter(obj); iter; ++iter) {
4620       serializer->writeCollectionKey(iter.first());
4621       serializer->writeArrayValue(iter.second());
4622     }
4623     serializer->writeArrayFooter();
4624   }
4625 }
4626
4627 void collectionDeepCopyTV(TypedValue* tv) {
4628   switch (tv->m_type) {
4629     case KindOfArray: {
4630       ArrayData* arr = collectionDeepCopyArray(tv->m_data.parr);
4631       if (tv->m_data.parr->decRefCount() == 0) {
4632         tv->m_data.parr->release();
4633       }
4634       tv->m_data.parr = arr;
4635       break;
4636     }
4637     case KindOfObject: {
4638       ObjectData* obj = tv->m_data.pobj;
4639       if (!obj->isCollection()) break;
4640       switch (obj->getCollectionType()) {
4641         case Collection::VectorType:
4642           obj = collectionDeepCopyVector(static_cast<c_Vector*>(obj));
4643           break;
4644         case Collection::MapType:
4645           obj = collectionDeepCopyMap(static_cast<c_Map*>(obj));
4646           break;
4647         case Collection::StableMapType:
4648           obj = collectionDeepCopyStableMap(static_cast<c_StableMap*>(obj));
4649           break;
4650         case Collection::PairType:
4651           obj = collectionDeepCopyPair(static_cast<c_Pair*>(obj));
4652           break;
4653         default:
4654           assert(false);
4655           obj = nullptr;
4656           break;
4657       }
4658       if (tv->m_data.pobj->decRefCount() == 0) {
4659         tv->m_data.pobj->release();
4660       }
4661       tv->m_data.pobj = obj;
4662       break;
4663     }
4664     case KindOfRef: {
4665       assert(false);
4666       break;
4667     }
4668     default: break;
4669   }
4670 }
4671
4672 ArrayData* collectionDeepCopyArray(ArrayData* arr) {
4673   Array a = arr = arr->copy();
4674   for (ArrayIter iter(arr); iter; ++iter) {
4675     collectionDeepCopyTV((TypedValue*)(&iter.secondRef()));
4676   }
4677   return a.detach();
4678 }
4679
4680 ObjectData* collectionDeepCopyVector(c_Vector* vec) {
4681   Object o = vec = static_cast<c_Vector*>(vec->clone());
4682   size_t sz = vec->m_size;
4683   for (size_t i = 0; i < sz; ++i) {
4684     collectionDeepCopyTV(&vec->m_data[i]);
4685   }
4686   return o.detach();
4687 }
4688
4689 ObjectData* collectionDeepCopyMap(c_Map* mp) {
4690   Object o = mp = static_cast<c_Map*>(mp->clone());
4691   uint lastSlot = mp->m_nLastSlot;
4692   for (uint i = 0; i <= lastSlot; ++i) {
4693     c_Map::Bucket* p = mp->fetchBucket(i);
4694     if (p->validValue()) {
4695       collectionDeepCopyTV(&p->data);
4696     }
4697   }
4698   return o.detach();
4699 }
4700
4701 ObjectData* collectionDeepCopyStableMap(c_StableMap* smp) {
4702   Object o = smp = static_cast<c_StableMap*>(smp->clone());
4703   for (c_StableMap::Bucket* p = smp->m_pListHead; p; p = p->pListNext) {
4704     collectionDeepCopyTV(&p->data);
4705   }
4706   return o.detach();
4707 }
4708
4709 ObjectData* collectionDeepCopySet(c_Set* st) {
4710   Object o = st = static_cast<c_Set*>(st->clone());
4711   return o.detach();
4712 }
4713
4714 ObjectData* collectionDeepCopyPair(c_Pair* pair) {
4715   Object o = pair = static_cast<c_Pair*>(pair->clone());
4716   collectionDeepCopyTV(&pair->elm0);
4717   collectionDeepCopyTV(&pair->elm1);
4718   return o.detach();
4719 }
4720
4721 ///////////////////////////////////////////////////////////////////////////////
4722 }