hphp/runtime/base/collections.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #include "hphp/runtime/base/collections.h"
  17
  18 #include "hphp/runtime/base/array-init.h"
  19 #include "hphp/runtime/base/variable-serializer.h"
  20 #include "hphp/runtime/base/variable-unserializer.h"
  21 #include "hphp/runtime/ext/collections/ext_collections-map.h"
  22 #include "hphp/runtime/ext/collections/ext_collections-pair.h"
  23 #include "hphp/runtime/ext/collections/ext_collections-set.h"
  24 #include "hphp/runtime/ext/collections/ext_collections-vector.h"
  25
  26 namespace HPHP { namespace collections {
  27 /////////////////////////////////////////////////////////////////////////////
  28
  29 #define X(type) const StaticString s_##type("HH\\" #type);
  30 COLLECTIONS_ALL_TYPES(X)
  31 #undef X
  32
  33 /////////////////////////////////////////////////////////////////////////////
  34 // Constructor/Initializer
  35
  36 ObjectData* allocPair(TypedValue c1, TypedValue c2) {
  37   return req::make<c_Pair>(c1, c2, c_Pair::NoIncRef{}).detach();
  38 }
  39
  40 #define X(type)                                    \
  41 ObjectData* allocEmpty##type() {                   \
  42   return req::make<c_##type>().detach();           \
  43 }                                                  \
  44 ObjectData* allocFromArray##type(ArrayData* arr) { \
  45   return req::make<c_##type>(arr).detach();        \
  46 }
  47 COLLECTIONS_PAIRED_TYPES(X)
  48 #undef X
  49
  50 newFromArrayFunc allocFromArrayFunc(CollectionType ctype) {
  51   switch (ctype) {
  52 #define X(type) case CollectionType::type: return allocFromArray##type;
  53 COLLECTIONS_PAIRED_TYPES(X)
  54 #undef X
  55     case CollectionType::Pair: not_reached();
  56   }
  57   not_reached();
  58 }
  59
  60 newEmptyInstanceFunc allocEmptyFunc(CollectionType ctype) {
  61   switch (ctype) {
  62 #define X(type) case CollectionType::type: return allocEmpty##type;
  63 COLLECTIONS_PAIRED_TYPES(X)
  64 #undef X
  65     case CollectionType::Pair: not_reached();
  66   }
  67   not_reached();
  68 }
  69
  70 /////////////////////////////////////////////////////////////////////////////
  71 // Misc
  72
  73 bool isType(const Class* cls, CollectionType ctype) {
  74   switch (ctype) {
  75 #define X(type) case CollectionType::type: return cls == c_##type::classof();
  76 COLLECTIONS_ALL_TYPES(X)
  77 #undef X
  78   }
  79   not_reached();
  80 }
  81
  82 /////////////////////////////////////////////////////////////////////////////
  83 // Casting and Copying
  84
  85 template <IntishCast IC>
  86 Array toArray(const ObjectData* obj) {
  87   assertx(obj->isCollection());
  88   switch (obj->collectionType()) {
  89 #define X(type) case CollectionType::type: return c_##type::ToArray<IC>(obj);
  90 COLLECTIONS_ALL_TYPES(X)
  91 #undef X
  92   }
  93   not_reached();
  94 }
  95
  96 template
  97 Array toArray<IntishCast::None>(const ObjectData*);
  98 template
  99 Array toArray<IntishCast::Cast>(const ObjectData*);
 100
 101 bool toBool(const ObjectData* obj) {
 102   assertx(obj->isCollection());
 103   switch (obj->collectionType()) {
 104 #define X(type) case CollectionType::type: return c_##type::ToBool(obj);
 105 COLLECTIONS_ALL_TYPES(X)
 106 #undef X
 107   }
 108   not_reached();
 109 }
 110
 111 ObjectData* clone(ObjectData* obj) {
 112   assertx(obj->isCollection());
 113   switch (obj->collectionType()) {
 114 #define X(type) case CollectionType::type: return c_##type::Clone(obj);
 115 COLLECTIONS_ALL_TYPES(X)
 116 #undef X
 117   }
 118   not_reached();
 119 }
 120
 121 ArrayData* asArray(ObjectData* obj) {
 122   assertx(obj->isCollection());
 123   switch (obj->collectionType()) {
 124   case CollectionType::ImmVector:
 125   case CollectionType::Vector:
 126     return static_cast<BaseVector*>(obj)->arrayData();
 127   case CollectionType::ImmMap:
 128   case CollectionType::Map:
 129   case CollectionType::ImmSet:
 130   case CollectionType::Set:
 131     return static_cast<HashCollection*>(obj)->arrayData()->asArrayData();
 132   case CollectionType::Pair:
 133     return nullptr;
 134   }
 135   not_reached();
 136 }
 137
 138 /////////////////////////////////////////////////////////////////////////////
 139 // Deep Copy
 140
 141 namespace {
 142
 143 ArrayData* deepCopyArray(ArrayData* arr) {
 144   assertx(arr->isPHPArrayType());
 145   Array ar(arr);
 146   IterateKV(
 147     arr,
 148     [&](TypedValue k, TypedValue v) {
 149       if (!isRefcountedType(v.m_type)) return false;
 150       Variant value{tvAsCVarRef(&v)};
 151       deepCopy(value.asTypedValue());
 152       if (value.asTypedValue()->m_data.num != v.m_data.num) {
 153         ar.set(k, *value.asTypedValue(), true);
 154       }
 155       return false;
 156     }
 157   );
 158   return ar.detach();
 159 }
 160
 161 ArrayData* deepCopyVecArray(ArrayData* arr) {
 162   assertx(arr->isVecArrayKind());
 163   Array ar(arr);
 164   PackedArray::IterateKV(
 165     arr,
 166     [&](TypedValue k, TypedValue v) {
 167       if (!isRefcountedType(v.m_type)) return false;
 168       Variant value{tvAsCVarRef(&v)};
 169       deepCopy(value.asTypedValue());
 170       if (value.asTypedValue()->m_data.num != v.m_data.num) {
 171         assertx(k.m_type == KindOfInt64);
 172         ar.set(k.m_data.num, value);
 173       }
 174       return false;
 175     }
 176   );
 177   return ar.detach();
 178 }
 179
 180 ArrayData* deepCopyDict(ArrayData* arr) {
 181   assertx(arr->isDictKind());
 182   Array ar(arr);
 183   MixedArray::IterateKV(
 184     MixedArray::asMixed(arr),
 185     [&](TypedValue k, TypedValue v) {
 186       if (!isRefcountedType(v.m_type)) return false;
 187       Variant value{tvAsCVarRef(&v)};
 188       deepCopy(value.asTypedValue());
 189       if (value.asTypedValue()->m_data.num != v.m_data.num) {
 190         ar.set(k, *value.asTypedValue());
 191       }
 192       return false;
 193     }
 194   );
 195   return ar.detach();
 196 }
 197
 198 ObjectData* deepCopySet(c_Set* st) {
 199   return c_Set::Clone(st);
 200 }
 201
 202 ObjectData* deepCopyImmSet(c_ImmSet* st) {
 203   return c_ImmSet::Clone(st);
 204 }
 205
 206 }  // namespace
 207
 208 void deepCopy(tv_lval lval) {
 209   switch (type(lval)) {
 210     DT_UNCOUNTED_CASE:
 211     case KindOfString:
 212     case KindOfResource:
 213     case KindOfKeyset:
 214     case KindOfClsMeth:
 215       return;
 216
 217     case KindOfVec: {
 218       auto& original = val(lval).parr;
 219       auto arr = deepCopyVecArray(original);
 220       decRefArr(original);
 221       original = arr;
 222       return;
 223     }
 224
 225     case KindOfDict: {
 226       auto& original = val(lval).parr;
 227       auto arr = deepCopyDict(original);
 228       decRefArr(original);
 229       original = arr;
 230       return;
 231     }
 232
 233     case KindOfDArray:
 234     case KindOfVArray:
 235     case KindOfArray: {
 236       auto& original = val(lval).parr;
 237       auto arr = deepCopyArray(original);
 238       decRefArr(original);
 239       original = arr;
 240       return;
 241     }
 242
 243     case KindOfObject: {
 244       auto& original = val(lval).pobj;
 245       auto obj = original;
 246       if (!obj->isCollection()) return;
 247       const auto copyVector = [](BaseVector* vec) {
 248         const auto size = vec->size();
 249         if (size > 0 && vec->arrayData()->isRefCounted()) {
 250           vec->mutate();
 251           int64_t i = 0;
 252           do {
 253             deepCopy(vec->dataAt(i));
 254           } while (++i < size);
 255         }
 256         return vec;
 257       };
 258       const auto copyMap = [](BaseMap* mp) {
 259         if (mp->size() > 0 && mp->arrayData()->isRefCounted()) {
 260           mp->mutate();
 261           auto used = mp->posLimit();
 262           for (uint32_t i = 0; i < used; ++i) {
 263             if (mp->isTombstone(i)) continue;
 264             auto* e = &mp->data()[i];
 265             deepCopy(&e->data);
 266           }
 267         }
 268         return mp;
 269       };
 270       switch (obj->collectionType()) {
 271         case CollectionType::Pair: {
 272           auto pair = c_Pair::Clone(static_cast<c_Pair*>(obj));
 273           Object o = Object::attach(pair);
 274           deepCopy(&pair->elm0);
 275           deepCopy(&pair->elm1);
 276           obj = o.detach();
 277           break;
 278         }
 279         case CollectionType::Vector:
 280           obj = copyVector(c_Vector::Clone(static_cast<c_Vector*>(obj)));
 281           break;
 282         case CollectionType::ImmVector:
 283           obj = copyVector(c_ImmVector::Clone(static_cast<c_ImmVector*>(obj)));
 284           break;
 285         case CollectionType::Map:
 286           obj = copyMap(c_Map::Clone(static_cast<c_Map*>(obj)));
 287           break;
 288         case CollectionType::ImmMap:
 289           obj = copyMap(c_ImmMap::Clone(static_cast<c_ImmMap*>(obj)));
 290           break;
 291         case CollectionType::Set:
 292           obj = c_Set::Clone(static_cast<c_Set*>(obj));
 293           break;
 294         case CollectionType::ImmSet:
 295           obj = c_ImmSet::Clone(static_cast<c_ImmSet*>(obj));
 296           break;
 297         default:
 298           assertx(false);
 299       }
 300       assertx(obj != original || original->hasMultipleRefs());
 301       decRefObj(original);
 302       original = obj;
 303       return;
 304     }
 305     case KindOfRecord:
 306       raise_error(Strings::RECORD_NOT_SUPPORTED); // TODO (T41020058)
 307   }
 308   not_reached();
 309 }
 310
 311 /////////////////////////////////////////////////////////////////////////////
 312 // Read/Write access
 313
 314 namespace {
 315
 316 // Value types (everything except Object and Resource) are handled specially:
 317 // any value-type members of an immutable collection are also immutable.
 318 inline bool isValueType(DataType type) {
 319   return type != KindOfObject && type != KindOfResource;
 320 }
 321
 322 template <bool throwOnMiss>
 323 inline tv_lval atImpl(ObjectData* obj, const TypedValue* key) {
 324   switch (obj->collectionType()) {
 325 #define X(type) case CollectionType::type: \
 326                   return c_##type::OffsetAt<throwOnMiss>(obj, key);
 327 COLLECTIONS_ALL_TYPES(X)
 328 #undef X
 329   }
 330   return nullptr;
 331 }
 332
 333 }  // namespace
 334
 335 tv_lval at(ObjectData* obj, const TypedValue* key) {
 336   return atImpl<true>(obj, key);
 337 }
 338 tv_lval get(ObjectData* obj, const TypedValue* key) {
 339   return atImpl<false>(obj, key);
 340 }
 341
 342 tv_lval atLval(ObjectData* obj, const TypedValue* key) {
 343   tv_lval ret;
 344   switch (obj->collectionType()) {
 345     case CollectionType::Pair:
 346       ret = c_Pair::OffsetAt<true>(obj, key);
 347       break;
 348
 349     case CollectionType::Vector: {
 350       ret = BaseVector::OffsetAt<true>(obj, key);
 351       // We're about to expose an element of a Vector in an lvalue context;
 352       // if the element is a value-type (anything other than objects and
 353       // resources) we need to sever any buffer sharing that might be going on
 354       auto* vec = static_cast<c_Vector*>(obj);
 355       if (UNLIKELY(!vec->canMutateBuffer() && isValueType(type(ret)))) {
 356         vec->mutate();
 357         ret = BaseVector::OffsetAt<true>(obj, key);
 358       }
 359       return ret;
 360     }
 361     case CollectionType::ImmVector:
 362       ret = BaseVector::OffsetAt<true>(obj, key);
 363       break;
 364
 365     case CollectionType::Map: {
 366       ret = BaseMap::OffsetAt<true>(obj, key);
 367       // We're about to expose an element of a Map in an lvalue context;
 368       // if the element is a value-type (anything other than objects and
 369       // resources) we need to sever any buffer sharing that might be going on
 370       auto* mp = static_cast<c_Map*>(obj);
 371       if (UNLIKELY(!mp->canMutateBuffer() && isValueType(type(ret)))) {
 372         mp->mutate();
 373         ret = BaseMap::OffsetAt<true>(obj, key);
 374       }
 375       return ret;
 376     }
 377     case CollectionType::ImmMap:
 378       ret = BaseMap::OffsetAt<true>(obj, key);
 379       break;
 380
 381     case CollectionType::Set:
 382     case CollectionType::ImmSet:
 383       BaseSet::throwNoMutableIndexAccess();
 384
 385   }
 386   // Value-type elements (anything other than objects and resources) of
 387   // an immutable collection "inherit" the collection's immutable status.
 388   // We do not allow value-type elements of an immutable collection to
 389   // be read in an "lvalue" context in order to prevent null->array
 390   // promotion, null->stdClass promotion, and mutating strings or arrays
 391   // in place (see "test/slow/collection_classes/invalid-operations.php"
 392   // for examples).
 393   if (isValueType(type(ret))) {
 394     throw_cannot_modify_immutable_object(obj->getClassName().data());
 395   }
 396   return ret;
 397 }
 398
 399 tv_lval atRw(ObjectData* obj, const TypedValue* key) {
 400   switch (obj->collectionType()) {
 401     case CollectionType::Vector:
 402       // Since we're exposing an element of a Vector in an read/write context,
 403       // we need to sever any buffer sharing that might be going on.
 404       static_cast<c_Vector*>(obj)->mutate();
 405       return BaseVector::OffsetAt<true>(obj, key);
 406     case CollectionType::Map:
 407       static_cast<c_Map*>(obj)->mutate();
 408       return BaseMap::OffsetAt<true>(obj, key);
 409     case CollectionType::Set:
 410     case CollectionType::ImmSet:
 411       BaseSet::throwNoMutableIndexAccess();
 412     case CollectionType::ImmVector:
 413     case CollectionType::ImmMap:
 414     case CollectionType::Pair:
 415       throw_cannot_modify_immutable_object(obj->getClassName().data());
 416   }
 417   return nullptr;
 418 }
 419
 420 bool contains(ObjectData* obj, const Variant& offset) {
 421   auto* key = offset.asTypedValue();
 422   switch (obj->collectionType()) {
 423     case CollectionType::Vector:
 424     case CollectionType::ImmVector:
 425       return BaseVector::OffsetContains(obj, key);
 426     case CollectionType::Map:
 427     case CollectionType::ImmMap:
 428       return BaseMap::OffsetContains(obj, key);
 429     case CollectionType::Set:
 430     case CollectionType::ImmSet:
 431       return BaseSet::OffsetContains(obj, key);
 432     case CollectionType::Pair:
 433       return c_Pair::OffsetContains(obj, key);
 434   }
 435   not_reached();
 436 }
 437
 438 bool isset(ObjectData* obj, const TypedValue* key) {
 439   switch (obj->collectionType()) {
 440     case CollectionType::Vector:
 441     case CollectionType::ImmVector:
 442       return BaseVector::OffsetIsset(obj, key);
 443     case CollectionType::Map:
 444     case CollectionType::ImmMap:
 445       return BaseMap::OffsetIsset(obj, key);
 446     case CollectionType::Set:
 447     case CollectionType::ImmSet:
 448       return BaseSet::OffsetIsset(obj, key);
 449     case CollectionType::Pair:
 450       return c_Pair::OffsetIsset(obj, key);
 451   }
 452   not_reached();
 453 }
 454
 455 void unset(ObjectData* obj, const TypedValue* key) {
 456   switch (obj->collectionType()) {
 457     case CollectionType::Vector:
 458       c_Vector::OffsetUnset(obj, key);
 459       break;
 460     case CollectionType::Map:
 461       c_Map::OffsetUnset(obj, key);
 462       break;
 463     case CollectionType::Set:
 464       BaseSet::OffsetUnset(obj, key);
 465       break;
 466     case CollectionType::ImmVector:
 467     case CollectionType::ImmMap:
 468     case CollectionType::ImmSet:
 469     case CollectionType::Pair:
 470       throw_cannot_modify_immutable_object(obj->getClassName().data());
 471   }
 472 }
 473
 474 void append(ObjectData* obj, TypedValue* val) {
 475   assertx(val->m_type != KindOfUninit);
 476   switch (obj->collectionType()) {
 477     case CollectionType::Vector:
 478       static_cast<c_Vector*>(obj)->add(*val);
 479       break;
 480     case CollectionType::Map:
 481       static_cast<c_Map*>(obj)->add(*val);
 482       break;
 483     case CollectionType::Set:
 484       static_cast<c_Set*>(obj)->add(*val);
 485       break;
 486     case CollectionType::ImmVector:
 487     case CollectionType::ImmMap:
 488     case CollectionType::ImmSet:
 489     case CollectionType::Pair:
 490       throw_cannot_modify_immutable_object(obj->getClassName().data());
 491   }
 492 }
 493
 494 void set(ObjectData* obj, const TypedValue* key, const TypedValue* val) {
 495   assertx(val->m_type != KindOfUninit);
 496   switch (obj->collectionType()) {
 497     case CollectionType::Vector:
 498       c_Vector::OffsetSet(obj, key, val);
 499       break;
 500     case CollectionType::Map:
 501       BaseMap::OffsetSet(obj, key, val);
 502       break;
 503     case CollectionType::Set:
 504     case CollectionType::ImmSet:
 505       BaseSet::throwNoMutableIndexAccess();
 506       break;
 507     case CollectionType::ImmVector:
 508     case CollectionType::ImmMap:
 509     case CollectionType::Pair:
 510       throw_cannot_modify_immutable_object(obj->getClassName().data());
 511   }
 512 }
 513
 514 bool equals(const ObjectData* obj1, const ObjectData* obj2) {
 515   assertx(isValidCollection(obj1->collectionType()));
 516   if (!obj2->isCollection()) return false;
 517   auto ct1 = obj1->collectionType();
 518   auto ct2 = obj2->collectionType();
 519
 520   // we intentionally allow mutable/immutable versions of the same collection
 521   // type to compare equal
 522   if (isMapCollection(ct1)) {
 523     return isMapCollection(ct2) && BaseMap::Equals(obj1, obj2);
 524   } else if (isVectorCollection(ct1)) {
 525     return isVectorCollection(ct2) && BaseVector::Equals(obj1, obj2);
 526   } else if (isSetCollection(ct1)) {
 527     return isSetCollection(ct2) && BaseSet::Equals(obj1, obj2);
 528   } else {
 529     assertx(ct1 == CollectionType::Pair);
 530     return (ct2 == CollectionType::Pair) && c_Pair::Equals(obj1, obj2);
 531   }
 532 }
 533
 534 Variant pop(ObjectData* obj) {
 535   assertx(obj->isCollection());
 536   assertx(isMutableCollection(obj->collectionType()));
 537   switch (obj->collectionType()) {
 538     case CollectionType::Vector:
 539       return static_cast<c_Vector*>(obj)->pop();
 540     case CollectionType::Map:
 541       return static_cast<c_Map*>(obj)->pop();
 542     case CollectionType::Set:
 543       return static_cast<c_Set*>(obj)->pop();
 544     default:
 545       assertx(false);
 546   }
 547   not_reached();
 548 }
 549
 550 Variant shift(ObjectData* obj) {
 551   assertx(obj->isCollection());
 552   assertx(isMutableCollection(obj->collectionType()));
 553   switch (obj->collectionType()) {
 554     case CollectionType::Vector:
 555       return static_cast<c_Vector*>(obj)->popFront();
 556     case CollectionType::Map:
 557       return static_cast<c_Map*>(obj)->popFront();
 558     case CollectionType::Set:
 559       return static_cast<c_Set*>(obj)->popFront();
 560     default:
 561       assertx(false);
 562   }
 563   not_reached();
 564 }
 565
 566 /////////////////////////////////////////////////////////////////////////////
 567 }}