2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com) |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
17 #include "hphp/runtime/base/mixed-array.h"
19 #include "hphp/runtime/base/apc-array.h"
20 #include "hphp/runtime/base/apc-local-array.h"
21 #include "hphp/runtime/base/apc-stats.h"
22 #include "hphp/runtime/base/array-data.h"
23 #include "hphp/runtime/base/array-helpers.h"
24 #include "hphp/runtime/base/array-init.h"
25 #include "hphp/runtime/base/array-iterator.h"
26 #include "hphp/runtime/base/array-provenance.h"
27 #include "hphp/runtime/base/comparisons.h"
28 #include "hphp/runtime/base/empty-array.h"
29 #include "hphp/runtime/base/execution-context.h"
30 #include "hphp/runtime/base/tv-val.h"
31 #include "hphp/runtime/base/runtime-option.h"
32 #include "hphp/runtime/base/runtime-error.h"
33 #include "hphp/runtime/base/stats.h"
34 #include "hphp/runtime/base/tv-comparisons.h"
35 #include "hphp/runtime/base/tv-refcount.h"
36 #include "hphp/runtime/base/tv-type.h"
37 #include "hphp/runtime/base/variable-serializer.h"
39 #include "hphp/runtime/vm/member-operations.h"
41 #include "hphp/util/alloc.h"
42 #include "hphp/util/hash.h"
43 #include "hphp/util/lock.h"
44 #include "hphp/util/trace.h"
46 #include <folly/CPortability.h>
47 #include <folly/portability/Constexpr.h>
52 #include "hphp/runtime/base/mixed-array-defs.h"
53 #include "hphp/runtime/base/packed-array-defs.h"
57 TRACE_SET_MOD(runtime
);
59 static_assert(MixedArray::computeAllocBytes(MixedArray::SmallScale
) ==
60 kEmptyMixedArraySize
, "");
62 std::aligned_storage
<kEmptyMixedArraySize
, 16>::type s_theEmptyDictArray
;
63 std::aligned_storage
<kEmptyMixedArraySize
, 16>::type s_theEmptyDArray
;
65 struct MixedArray::Initializer
{
67 auto const ad
= reinterpret_cast<MixedArray
*>(&s_theEmptyDictArray
);
72 ad
->initHeader(HeaderKind::Dict
, StaticValue
);
73 assertx(ad
->checkInvariants());
76 MixedArray::Initializer
MixedArray::s_initializer
;
78 struct MixedArray::DArrayInitializer
{
80 auto const ad
= reinterpret_cast<MixedArray
*>(&s_theEmptyDArray
);
85 ad
->initHeader_16(HeaderKind::Mixed
, StaticValue
, ArrayData::kDArray
);
86 assertx(RuntimeOption::EvalHackArrDVArrs
|| ad
->checkInvariants());
89 MixedArray::DArrayInitializer
MixedArray::s_darr_initializer
;
91 //////////////////////////////////////////////////////////////////////
94 ArrayData
* MixedArray::MakeReserveImpl(uint32_t size
,
96 ArrayData::DVArray dvArray
) {
97 assertx(hk
== HeaderKind::Mixed
|| hk
== HeaderKind::Dict
);
98 assertx(dvArray
== ArrayData::kNotDVArray
|| dvArray
== ArrayData::kDArray
);
99 assertx(hk
!= HeaderKind::Dict
|| dvArray
== ArrayData::kNotDVArray
);
100 assertx(!RuntimeOption::EvalHackArrDVArrs
||
101 dvArray
== ArrayData::kNotDVArray
);
103 auto const scale
= computeScaleFromSize(size
);
104 auto const ad
= reqAlloc(scale
);
106 // Intialize the hash table first, because the header is already in L1 cache,
107 // but the hash table may not be. So let's issue the cache request ASAP.
110 ad
->m_sizeAndPos
= 0; // size=0, pos=0
111 ad
->initHeader_16(hk
, OneReference
, dvArray
);
112 ad
->m_scale_used
= scale
; // used=0
115 assertx(ad
->m_kind
== hk
);
116 assertx(ad
->dvArray() == dvArray
);
117 assertx(ad
->m_size
== 0);
118 assertx(ad
->m_pos
== 0);
119 assertx(ad
->hasExactlyOneRef());
120 assertx(ad
->m_used
== 0);
121 assertx(ad
->m_nextKI
== 0);
122 assertx(ad
->m_scale
== scale
);
123 assertx(ad
->checkInvariants());
127 ArrayData
* MixedArray::MakeReserveMixed(uint32_t size
) {
128 auto ad
= MakeReserveImpl(size
, HeaderKind::Mixed
, ArrayData::kNotDVArray
);
129 assertx(ad
->isMixedKind());
130 assertx(ad
->isNotDVArray());
134 ArrayData
* MixedArray::MakeReserveDArray(uint32_t size
) {
135 assertx(!RuntimeOption::EvalHackArrDVArrs
);
136 auto ad
= MakeReserveImpl(size
, HeaderKind::Mixed
, ArrayData::kDArray
);
137 assertx(ad
->isMixedKind());
138 assertx(ad
->isDArray());
139 return tagArrProv(ad
);
142 ArrayData
* MixedArray::MakeReserveDict(uint32_t size
) {
143 auto ad
= MakeReserveImpl(size
, HeaderKind::Dict
, ArrayData::kNotDVArray
);
144 assertx(ad
->isDictKind());
145 return tagArrProv(ad
);
148 ArrayData
* MixedArray::MakeReserveLike(const ArrayData
* other
,
150 capacity
= (capacity
? capacity
: other
->size());
152 if (other
->hasVanillaPackedLayout()) {
153 return PackedArray::MakeReserve(capacity
);
155 return MixedArray::MakeReserveMixed(capacity
);
160 MixedArray
* MixedArray::MakeStructImpl(uint32_t size
,
161 const StringData
* const* keys
,
162 const TypedValue
* values
,
164 ArrayData::DVArray dvArray
) {
166 assertx(hk
== HeaderKind::Mixed
|| hk
== HeaderKind::Dict
);
167 assertx(dvArray
== ArrayData::kNotDVArray
||
168 dvArray
== ArrayData::kDArray
);
169 assertx(hk
!= HeaderKind::Dict
|| dvArray
== ArrayData::kNotDVArray
);
170 assertx(!RuntimeOption::EvalHackArrDVArrs
||
171 dvArray
== ArrayData::kNotDVArray
);
173 auto const scale
= computeScaleFromSize(size
);
174 auto const ad
= reqAlloc(scale
);
176 auto const aux
= MixedArrayKeys::packStaticStrsForAux() |
177 static_cast<uint16_t>(dvArray
);
179 ad
->m_sizeAndPos
= size
; // pos=0
180 ad
->initHeader_16(hk
, OneReference
, aux
);
181 ad
->m_scale_used
= scale
| uint64_t{size
} << 32; // used=size
184 auto const table
= ad
->initHash(scale
);
185 auto const mask
= ad
->mask();
186 auto const data
= ad
->data();
188 // Append values by moving -- Caller assumes we update refcount.
189 // Values are in reverse order since they come from the stack, which
191 for (uint32_t i
= 0; i
< size
; i
++) {
192 assertx(keys
[i
]->isStatic());
195 data
[i
].setStaticKey(const_cast<StringData
*>(k
), h
);
196 const auto& tv
= values
[size
- i
- 1];
197 data
[i
].data
.m_data
= tv
.m_data
;
198 data
[i
].data
.m_type
= tv
.m_type
;
199 auto ei
= ad
->findForNewInsert(table
, mask
, h
);
203 assertx(ad
->m_size
== size
);
204 assertx(ad
->dvArray() == dvArray
);
205 assertx(ad
->m_pos
== 0);
206 assertx(ad
->m_kind
== hk
);
207 assertx(ad
->m_scale
== scale
);
208 assertx(ad
->hasExactlyOneRef());
209 assertx(ad
->m_used
== size
);
210 assertx(ad
->m_nextKI
== 0);
211 assertx(ad
->checkInvariants());
215 MixedArray
* MixedArray::MakeStruct(uint32_t size
,
216 const StringData
* const* keys
,
217 const TypedValue
* values
) {
218 return MakeStructImpl(size
, keys
, values
,
220 ArrayData::kNotDVArray
);
223 MixedArray
* MixedArray::MakeStructDict(uint32_t size
,
224 const StringData
* const* keys
,
225 const TypedValue
* values
) {
226 auto const ad
= MakeStructImpl(size
, keys
, values
,
228 ArrayData::kNotDVArray
);
229 return asMixed(tagArrProv(ad
));
232 MixedArray
* MixedArray::MakeStructDArray(uint32_t size
,
233 const StringData
* const* keys
,
234 const TypedValue
* values
) {
235 assertx(!RuntimeOption::EvalHackArrDVArrs
);
236 auto const ad
= MakeStructImpl(size
, keys
, values
,
239 return asMixed(tagArrProv(ad
));
243 MixedArray
* MixedArray::AllocStructImpl(uint32_t size
,
246 ArrayData::DVArray dvArray
) {
248 assertx(hk
== HeaderKind::Mixed
|| hk
== HeaderKind::Dict
);
249 assertx(dvArray
== ArrayData::kNotDVArray
||
250 dvArray
== ArrayData::kDArray
);
251 assertx(hk
!= HeaderKind::Dict
|| dvArray
== ArrayData::kNotDVArray
);
252 assertx(!RuntimeOption::EvalHackArrDVArrs
||
253 dvArray
== ArrayData::kNotDVArray
);
255 auto const scale
= computeScaleFromSize(size
);
256 auto const ad
= reqAlloc(scale
);
258 auto const aux
= MixedArrayKeys::packStaticStrsForAux() |
259 static_cast<uint16_t>(dvArray
);
261 ad
->m_sizeAndPos
= size
; // pos=0
262 ad
->initHeader_16(hk
, OneReference
, aux
);
263 ad
->m_scale_used
= scale
| uint64_t{size
} << 32; // used=size
266 CopyHash(ad
->hashTab(), hash
, scale
);
268 // If we don't trash the elements here, `ad` may fail checkInvariants
269 // because some of its element's type bytes happen to be tombstones.
271 // Trashing the elements isn't likely to hide real failures, because if we
272 // fail to initialize them later, any lookups will return implausible TVs.
273 if (debug
) memset(ad
->data(), kMixedElmFill
, sizeof(MixedArrayElm
) * size
);
275 assertx(ad
->m_size
== size
);
276 assertx(ad
->dvArray() == dvArray
);
277 assertx(ad
->m_pos
== 0);
278 assertx(ad
->m_kind
== hk
);
279 assertx(ad
->m_scale
== scale
);
280 assertx(ad
->hasExactlyOneRef());
281 assertx(ad
->m_used
== size
);
282 assertx(ad
->m_nextKI
== 0);
283 assertx(ad
->checkInvariants());
287 MixedArray
* MixedArray::AllocStruct(uint32_t size
, const int32_t* hash
) {
288 return AllocStructImpl(size
, hash
, HeaderKind::Mixed
, ArrayData::kNotDVArray
);
291 MixedArray
* MixedArray::AllocStructDict(uint32_t size
, const int32_t* hash
) {
292 auto const ad
= AllocStructImpl(size
, hash
, HeaderKind::Dict
,
293 ArrayData::kNotDVArray
);
294 return asMixed(tagArrProv(ad
));
297 MixedArray
* MixedArray::AllocStructDArray(uint32_t size
, const int32_t* hash
) {
298 assertx(!RuntimeOption::EvalHackArrDVArrs
);
299 auto const ad
= AllocStructImpl(size
, hash
, HeaderKind::Mixed
,
301 return asMixed(tagArrProv(ad
));
304 template<HeaderKind hdr
, ArrayData::DVArray dv
>
305 MixedArray
* MixedArray::MakeMixedImpl(uint32_t size
, const TypedValue
* kvs
) {
308 auto const scale
= computeScaleFromSize(size
);
309 auto const ad
= reqAlloc(scale
);
313 ad
->m_sizeAndPos
= size
; // pos=0
314 ad
->initHeader_16(hdr
, OneReference
, dv
);
315 ad
->m_scale_used
= scale
| uint64_t{size
} << 32; // used=size
318 // Append values by moving -- no refcounts are updated.
319 auto const data
= ad
->data();
320 for (uint32_t i
= 0; i
< size
; i
++) {
321 auto& kTv
= kvs
[i
* 2];
322 if (isStringType(kTv
.m_type
)) {
323 auto k
= kTv
.m_data
.pstr
;
325 auto ei
= ad
->findForInsertUpdate(k
, h
);
326 if (isValidPos(ei
)) {
327 // it's the caller's responsibility to free kvs
332 data
[i
].setStrKeyNoIncRef(k
, h
);
333 ad
->mutableKeyTypes()->recordStr(k
);
336 assertx(kTv
.m_type
== KindOfInt64
);
337 auto k
= kTv
.m_data
.num
;
338 auto h
= hash_int64(k
);
339 auto ei
= ad
->findForInsertUpdate(k
, h
);
340 if (isValidPos(ei
)) {
341 // it's the caller's responsibility to free kvs
346 data
[i
].setIntKey(k
, h
);
347 ad
->mutableKeyTypes()->recordInt();
350 const auto& tv
= kvs
[(i
* 2) + 1];
351 data
[i
].data
.m_data
= tv
.m_data
;
352 data
[i
].data
.m_type
= tv
.m_type
;
355 assertx(ad
->m_size
== size
);
356 assertx(ad
->m_pos
== 0);
357 assertx(ad
->m_scale
== scale
);
358 assertx(ad
->hasExactlyOneRef());
359 assertx(ad
->m_used
== size
);
360 assertx(ad
->m_nextKI
== 0);
361 assertx(ad
->checkInvariants());
365 MixedArray
* MixedArray::MakeMixed(uint32_t size
, const TypedValue
* kvs
) {
367 MakeMixedImpl
<HeaderKind::Mixed
, ArrayData::kNotDVArray
>(size
, kvs
);
368 assertx(ad
== nullptr || ad
->kind() == kMixedKind
);
369 assertx(ad
== nullptr || ad
->isNotDVArray());
373 MixedArray
* MixedArray::MakeDArray(uint32_t size
, const TypedValue
* kvs
) {
374 if (RuntimeOption::EvalHackArrDVArrs
) return MakeDict(size
, kvs
);
377 MakeMixedImpl
<HeaderKind::Mixed
, ArrayData::kDArray
>(size
, kvs
);
378 assertx(ad
== nullptr || ad
->kind() == kMixedKind
);
379 assertx(ad
== nullptr || ad
->isDArray());
380 return ad
? asMixed(tagArrProv(ad
)) : nullptr;
383 MixedArray
* MixedArray::MakeDict(uint32_t size
, const TypedValue
* kvs
) {
385 MakeMixedImpl
<HeaderKind::Dict
, ArrayData::kNotDVArray
>(size
, kvs
);
386 assertx(ad
== nullptr || ad
->kind() == kDictKind
);
387 return ad
? asMixed(tagArrProv(ad
)) : nullptr;
390 MixedArray
* MixedArray::MakeDArrayNatural(uint32_t size
,
391 const TypedValue
* vals
) {
394 auto const scale
= computeScaleFromSize(size
);
395 auto const ad
= reqAlloc(scale
);
399 ad
->m_sizeAndPos
= size
; // pos=0
400 if (RuntimeOption::EvalHackArrDVArrs
) {
401 auto const aux
= MixedArrayKeys::packIntsForAux() |
402 static_cast<uint16_t>(ArrayData::kNotDVArray
);
403 ad
->initHeader_16(HeaderKind::Dict
, OneReference
, aux
);
405 auto const aux
= MixedArrayKeys::packIntsForAux() |
406 static_cast<uint16_t>(ArrayData::kDArray
);
407 ad
->initHeader_16(HeaderKind::Mixed
, OneReference
, aux
);
409 ad
->m_scale_used
= scale
| uint64_t{size
} << 32; // used=size
412 // Append values by moving -- no refcounts are updated.
413 auto const data
= ad
->data();
414 for (uint32_t i
= 0; i
< size
; i
++) {
415 auto h
= hash_int64(i
);
416 auto ei
= ad
->findForInsertUpdate(i
, h
);
417 assertx(!isValidPos(ei
));
418 data
[i
].setIntKey(i
, h
);
421 const auto& tv
= vals
[i
];
422 data
[i
].data
.m_data
= tv
.m_data
;
423 data
[i
].data
.m_type
= tv
.m_type
;
426 assertx(ad
->m_size
== size
);
427 assertx(ad
->m_pos
== 0);
428 assertx(ad
->m_scale
== scale
);
429 assertx(ad
->hasExactlyOneRef());
430 assertx(ad
->m_used
== size
);
431 assertx(ad
->m_nextKI
== size
);
432 assertx(ad
->checkInvariants());
433 return asMixed(tagArrProv(ad
));
437 MixedArray
* MixedArray::SlowCopy(MixedArray
* ad
, const ArrayData
& old
,
438 MixedArrayElm
* elm
, MixedArrayElm
* end
) {
439 assertx(ad
->isRefCounted());
441 for (; elm
< end
; ++elm
) {
442 if (elm
->hasStrKey()) elm
->skey
->incRefCount();
443 // When we convert an element to a tombstone, we set its value type to
444 // kInvalidDataType, which is not a refcounted type.
445 tvIncRefGenUnsafe(elm
->data
);
450 // for internal use by copyStatic() and copyMixed()
452 MixedArray
* MixedArray::CopyMixed(const MixedArray
& other
,
455 ArrayData::DVArray dvArray
) {
456 assertx(dest_hk
== HeaderKind::Mixed
|| dest_hk
== HeaderKind::Dict
);
457 assertx(dvArray
== ArrayData::kNotDVArray
|| dvArray
== ArrayData::kDArray
);
458 assertx(dest_hk
!= HeaderKind::Dict
|| dvArray
== ArrayData::kNotDVArray
);
459 if (mode
== AllocMode::Static
) {
460 assertx(other
.m_size
== other
.m_used
);
461 assertx(!other
.keyTypes().mayIncludeCounted());
462 assertx(!other
.keyTypes().mayIncludeTombstone());
465 auto const scale
= other
.m_scale
;
466 auto const ad
= mode
== AllocMode::Request
468 : staticAlloc(scale
, arrprov::tagSize(&other
));
470 // Copy everything including tombstones. We want to copy the elements and
471 // the hash separately, because the array may not be very full.
472 assertx(reinterpret_cast<uintptr_t>(ad
) % 16 == 0);
473 assertx(reinterpret_cast<uintptr_t>(&other
) % 16 == 0);
474 // Adding 24 bytes so that we can copy in 32-byte groups. This might
475 // overwrite the hash table, but won't overrun the allocated space as long as
476 // `malloc' returns multiple of 16 bytes.
477 bcopy32_inline(ad
, &other
,
478 sizeof(MixedArray
) + sizeof(Elm
) * other
.m_used
+ 24);
480 memcpy(ad
, &other
, sizeof(MixedArray
) + sizeof(Elm
) * other
.m_used
);
482 auto const count
= mode
== AllocMode::Request
? OneReference
: StaticValue
;
484 other
.keyTypes().packForAux() |
485 (dvArray
| (other
.isLegacyArray() ? ArrayData::kLegacyArray
: 0));
486 ad
->initHeader_16(dest_hk
, count
, aux
);
488 // We want SlowCopy to be a tail call in the opt build, but we still want to
489 // check assertions in debug builds, so we check them in this helper.
490 auto const check
= [&](MixedArray
* res
) {
491 assertx(res
->checkInvariants());
492 assertx(res
->m_kind
== dest_hk
);
493 assertx(res
->dvArray() == dvArray
);
494 assertx(res
->isLegacyArray() == other
.isLegacyArray());
495 assertx(res
->keyTypes() == other
.keyTypes());
496 assertx(res
->m_size
== other
.m_size
);
497 assertx(res
->m_pos
== other
.m_pos
);
498 assertx(res
->m_used
== other
.m_used
);
499 assertx(res
->m_scale
== scale
);
503 CopyHash(ad
->hashTab(), other
.hashTab(), scale
);
504 if (mode
== AllocMode::Static
) return check(ad
);
506 // Bump up refcounts as needed.
507 MixedArrayElm
* elm
= ad
->data();
508 auto const end
= elm
+ ad
->m_used
;
509 if (other
.keyTypes().mayIncludeCounted()) {
510 return check(SlowCopy(ad
, other
, elm
, end
));
512 for (; elm
< end
; ++elm
) {
513 assertx(IMPLIES(elm
->hasStrKey(), elm
->strKey()->isStatic()));
514 // When we convert an element to a tombstone, we set its key type to int
515 // and value type to kInvalidDataType, neither of which are refcounted.
516 tvIncRefGenUnsafe(elm
->data
);
521 NEVER_INLINE ArrayData
* MixedArray::CopyStatic(const ArrayData
* in
) {
522 auto a
= asMixed(in
);
523 assertx(a
->checkInvariants());
524 auto ret
= CopyMixed(*a
, AllocMode::Static
, in
->m_kind
, in
->dvArray());
526 if (RuntimeOption::EvalArrayProvenance
) {
527 assertx(!ret
->hasProvenanceData());
528 auto const tag
= arrprov::getTag(in
);
530 arrprov::setTag(ret
, tag
);
533 assertx(!arrprov::arrayWantsTag(ret
) ||
534 !!arrprov::getTag(ret
) == !!arrprov::getTag(in
));
538 NEVER_INLINE MixedArray
* MixedArray::copyMixed() const {
539 assertx(checkInvariants());
540 auto const out
= CopyMixed(*this, AllocMode::Request
, m_kind
, dvArray());
541 return asMixed(tagArrProv(out
, this));
544 //////////////////////////////////////////////////////////////////////
546 ArrayData
* MixedArray::MakeUncounted(ArrayData
* array
,
547 bool withApcTypedValue
,
548 DataWalker::PointerMap
* seen
) {
549 auto const updateSeen
= seen
&& array
->hasMultipleRefs();
551 auto it
= seen
->find(array
);
552 assertx(it
!= seen
->end());
553 if (auto const arr
= static_cast<ArrayData
*>(it
->second
)) {
554 if (arr
->uncountedIncRef()) {
559 auto a
= asMixed(array
);
560 assertx(!a
->empty());
561 auto const extra
= uncountedAllocExtra(array
, withApcTypedValue
);
562 auto const ad
= uncountedAlloc(a
->scale(), extra
);
563 auto const used
= a
->m_used
;
564 // Do a raw copy first, without worrying about counted types or refcount
565 // manipulation. To copy in 32-byte chunks, we add 24 bytes to the length.
566 // This might overwrite the hash table, but won't go beyond the space
567 // allocated for the MixedArray, assuming `malloc()' always allocates
568 // multiple of 16 bytes and extra is also a multiple of 16.
569 assertx((extra
& 0xf) == 0);
570 bcopy32_inline(ad
, a
, sizeof(MixedArray
) + sizeof(Elm
) * used
+ 24);
571 ad
->m_count
= UncountedValue
; // after bcopy, update count
572 if (withApcTypedValue
) {
573 ad
->m_aux16
|= kHasApcTv
;
575 ad
->m_aux16
&= ~kHasApcTv
;
577 ad
->m_aux16
&= ~kHasProvenanceData
;
578 assertx(ad
->keyTypes() == a
->keyTypes());
579 CopyHash(ad
->hashTab(), a
->hashTab(), a
->scale());
580 ad
->mutableKeyTypes()->makeStatic();
582 // Need to make sure keys and values are all uncounted.
583 auto dstElem
= ad
->data();
584 for (uint32_t i
= 0; i
< used
; ++i
) {
585 auto& te
= dstElem
[i
];
586 auto const type
= te
.data
.m_type
;
587 if (UNLIKELY(isTombstone(type
))) continue;
588 if (te
.hasStrKey() && !te
.skey
->isStatic()) {
589 if (te
.skey
->isUncounted() && te
.skey
->uncountedIncRef()) {
590 ad
->mutableKeyTypes()->recordNonStaticStr();
593 if (auto const st
= lookupStaticString(te
.skey
)) return st
;
594 ad
->mutableKeyTypes()->recordNonStaticStr();
595 HeapObject
** seenStr
= nullptr;
596 if (seen
&& te
.skey
->hasMultipleRefs()) {
597 seenStr
= &(*seen
)[te
.skey
];
598 if (auto const st
= static_cast<StringData
*>(*seenStr
)) {
599 if (st
->uncountedIncRef()) return st
;
602 auto const st
= StringData::MakeUncounted(te
.skey
->slice());
603 if (seenStr
) *seenStr
= st
;
608 ConvertTvToUncounted(&te
.data
, seen
);
610 if (APCStats::IsCreated()) {
611 APCStats::getAPCStats().addAPCUncountedBlock();
613 if (updateSeen
) (*seen
)[array
] = ad
;
614 assertx(ad
->checkInvariants());
615 return tagArrProv(ad
, array
);
618 ArrayData
* MixedArray::MakeDictFromAPC(const APCArray
* apc
) {
619 assertx(apc
->isDict());
620 auto const apcSize
= apc
->size();
621 DictInit init
{apcSize
};
622 for (uint32_t i
= 0; i
< apcSize
; ++i
) {
623 init
.setValidKey(apc
->getKey(i
), apc
->getValue(i
)->toLocal());
625 auto const ad
= init
.create();
626 return tagArrProv(ad
, apc
);
629 ArrayData
* MixedArray::MakeDArrayFromAPC(const APCArray
* apc
) {
630 assertx(!RuntimeOption::EvalHackArrDVArrs
);
631 assertx(apc
->isDArray());
632 auto const apcSize
= apc
->size();
633 DArrayInit init
{apcSize
};
634 for (uint32_t i
= 0; i
< apcSize
; ++i
) {
635 init
.setValidKey(apc
->getKey(i
), apc
->getValue(i
)->toLocal());
637 auto const ad
= init
.create();
638 return tagArrProv(ad
, apc
);
641 //=============================================================================
645 void MixedArray::SlowRelease(MixedArray
* ad
) {
646 assertx(ad
->isRefCounted());
647 assertx(ad
->hasExactlyOneRef());
648 assertx(!ad
->isZombie());
650 MixedArrayElm
* elm
= ad
->data();
651 for (auto const end
= elm
+ ad
->m_used
; elm
< end
; ++elm
) {
652 if (elm
->hasStrKey()) {
653 decRefStr(elm
->skey
);
654 // Keep GC from asserting on freed string keys in debug mode.
655 if (debug
) elm
->skey
= nullptr;
657 // When we convert an element to a tombstone, we set its key type to int
658 // and value type to kInvalidDataType, neither of which are refcounted.
659 tvDecRefGen(&elm
->data
);
661 tl_heap
->objFree(ad
, ad
->heapSize());
665 void MixedArray::Release(ArrayData
* in
) {
666 in
->fixCountForRelease();
667 assertx(in
->isRefCounted());
668 assertx(in
->hasExactlyOneRef());
670 if (RuntimeOption::EvalArrayProvenance
) {
671 arrprov::clearTag(in
);
673 auto const ad
= asMixed(in
);
675 if (!ad
->isZombie()) {
676 assertx(ad
->checkInvariants());
677 // keyTypes checks are too slow to go in MixedArray::checkInvariants.
678 assertx(ad
->keyTypes().checkInvariants(ad
));
679 if (ad
->keyTypes().mayIncludeCounted()) return SlowRelease(ad
);
681 MixedArrayElm
* elm
= ad
->data();
682 for (auto const end
= elm
+ ad
->m_used
; elm
< end
; ++elm
) {
683 // Keep the GC from asserting on freed string keys in debug mode.
684 assertx(IMPLIES(elm
->hasStrKey(), elm
->strKey()->isStatic()));
685 if (debug
&& elm
->hasStrKey()) elm
->skey
= nullptr;
686 // When we convert an element to a tombstone, we set its key type to int
687 // and value type to kInvalidDataType, neither of which are refcounted.
688 tvDecRefGen(&elm
->data
);
691 tl_heap
->objFree(ad
, ad
->heapSize());
692 AARCH64_WALKABLE_FRAME();
696 void MixedArray::ReleaseUncounted(ArrayData
* in
) {
697 auto const ad
= asMixed(in
);
698 if (!ad
->uncountedDecRef()) return;
700 if (RuntimeOption::EvalArrayProvenance
) {
701 arrprov::clearTag(in
);
703 if (!ad
->isZombie()) {
704 auto const data
= ad
->data();
705 auto const stop
= data
+ ad
->m_used
;
707 for (auto ptr
= data
; ptr
!= stop
; ++ptr
) {
708 if (isTombstone(ptr
->data
.m_type
)) continue;
709 if (ptr
->hasStrKey()) {
710 assertx(!ptr
->skey
->isRefCounted());
711 if (ptr
->skey
->isUncounted()) {
712 StringData::ReleaseUncounted(ptr
->skey
);
715 ReleaseUncountedTv(&ptr
->data
);
718 auto const extra
= uncountedAllocExtra(ad
, ad
->hasApcTv());
719 uncounted_sized_free(reinterpret_cast<char*>(ad
) - extra
,
720 computeAllocBytes(ad
->scale()) + extra
);
721 if (APCStats::IsCreated()) {
722 APCStats::getAPCStats().removeAPCUncountedBlock();
726 //=============================================================================
731 * All arrays are either in a mode, or in zombie state. The zombie
732 * state happens if an array is "moved from"---the only legal
733 * operation on a zombie array is to decref and release it.
735 * All arrays (zombie or not):
737 * m_scale is 2^k (1/4 of the hashtable size and 1/3 of capacity)
738 * mask is 4*scale - 1 (even power of 2 required for quadratic probe)
739 * mask == folly::nextPowTwo(capacity()) - 1;
743 * m_used == UINT32_MAX
747 * m_size <= m_used; m_used <= capacity()
748 * last element cannot be a tombstone
749 * m_pos and all external iterators can't be on a tombstone
750 * m_nextKI >= highest actual int key
751 * Elm.data.m_type maybe kInvalidDataType (tombstone)
752 * hash[] maybe Tombstone
753 * static arrays cannot contain tombstones
755 bool MixedArray::checkInvariants() const {
756 static_assert(ssize_t(Empty
) == ssize_t(-1), "");
757 static_assert(Tombstone
< 0, "");
758 static_assert((Tombstone
& 1) == 0, "");
759 static_assert(sizeof(Elm
) == 24, "");
760 static_assert(sizeof(ArrayData
) == 2 * sizeof(uint64_t), "");
762 sizeof(MixedArray
) == sizeof(ArrayData
) + 2 * sizeof(uint64_t),
763 "Performance is sensitive to sizeof(MixedArray)."
764 " Make sure you changed it with good reason and then update this assert."
768 assertx(hasVanillaMixedLayout());
769 assertx(!isMixedKind() || !isVArray());
770 assertx(!isDictKind() || isNotDVArray());
771 assertx(!RuntimeOption::EvalHackArrDVArrs
|| isNotDVArray());
772 assertx(checkCount());
773 assertx(m_scale
>= 1 && (m_scale
& (m_scale
- 1)) == 0);
774 assertx(MixedArray::HashSize(m_scale
) ==
775 folly::nextPowTwo
<uint64_t>(capacity()));
776 assertx(arrprov::arrayWantsTag(this) || !hasProvenanceData());
778 if (isZombie()) return true;
781 assertx(m_size
<= m_used
);
782 assertx(m_used
<= capacity());
783 assertx(IMPLIES(isStatic(), m_used
== m_size
));
784 if (m_pos
!= m_used
) {
785 assertx(size_t(m_pos
) < m_used
);
786 assertx(!isTombstone(data()[m_pos
].data
.m_type
));
791 //=============================================================================
794 size_t MixedArray::Vsize(const ArrayData
*) { not_reached(); }
796 tv_rval
MixedArray::RvalPos(const ArrayData
* ad
, ssize_t pos
) {
797 auto a
= asMixed(ad
);
798 assertx(a
->checkInvariants());
799 assertx(pos
!= a
->m_used
);
800 auto const& e
= a
->data()[pos
];
801 assertx(!e
.isTombstone());
805 bool MixedArray::IsVectorData(const ArrayData
* ad
) {
806 auto a
= asMixed(ad
);
807 if (a
->m_size
== 0) {
808 // any 0-length array is "vector-like" for the sake of this function.
811 auto const elms
= a
->data();
813 for (uint32_t pos
= 0, limit
= a
->m_used
; pos
< limit
; ++pos
) {
814 auto const& e
= elms
[pos
];
815 if (isTombstone(e
.data
.m_type
)) {
818 if (e
.hasStrKey() || e
.ikey
!= i
) {
826 //=============================================================================
830 int32_t* warnUnbalanced(MixedArray
* a
, size_t n
, int32_t* ei
) {
831 if (n
> size_t(RuntimeOption::MaxArrayChain
)) {
832 decRefArr(a
->asArrayData()); // otherwise, a leaks when exn propagates
833 raise_error("Array is too unbalanced (%lu)", n
);
838 MixedArray::InsertPos
MixedArray::insert(int64_t k
) {
840 auto h
= hash_int64(k
);
841 auto ei
= findForInsertUpdate(k
, h
);
842 if (isValidPos(ei
)) {
843 return InsertPos(true, data()[(int32_t)*ei
].data
);
845 if (k
>= m_nextKI
&& m_nextKI
>= 0) m_nextKI
= static_cast<uint64_t>(k
) + 1;
846 auto e
= allocElm(ei
);
848 mutableKeyTypes()->recordInt();
849 return InsertPos(false, e
->data
);
852 MixedArray::InsertPos
MixedArray::insert(StringData
* k
) {
854 auto const h
= k
->hash();
855 auto ei
= findForInsertUpdate(k
, h
);
856 if (isValidPos(ei
)) {
857 return InsertPos(true, data()[(int32_t)*ei
].data
);
859 auto e
= allocElm(ei
);
861 mutableKeyTypes()->recordStr(k
);
862 return InsertPos(false, e
->data
);
866 int32_t MixedArray::findForRemove(int64_t ki
, inthash_t h
, bool updateNext
) {
867 // all vector methods should work w/out touching the hashtable
868 return findForRemove(ki
, h
,
869 [this, ki
, updateNext
] (Elm
& e
) {
870 assertx(ki
== e
.ikey
);
871 // Conform to PHP5 behavior
872 // Hacky: don't removed the unsigned cast, else g++ can optimize away
873 // the check for == 0x7fff..., since there is no signed int k
874 // for which k-1 == 0x7fff...
875 if (((uint64_t)ki
== (uint64_t)m_nextKI
-1) &&
877 (ki
== 0x7fffffffffffffffLL
|| updateNext
)) {
884 int32_t MixedArray::findForRemove(const StringData
* s
, strhash_t h
) {
885 return findForRemove(s
, h
,
888 e
.setIntKey(0, hash_int64(0));
893 bool MixedArray::ExistsInt(const ArrayData
* ad
, int64_t k
) {
894 return asMixed(ad
)->findForExists(k
, hash_int64(k
));
897 bool MixedArray::ExistsStr(const ArrayData
* ad
, const StringData
* k
) {
898 return NvGetStr(ad
, k
).is_set();
901 //=============================================================================
902 // Append/insert/update.
905 * This is a streamlined copy of Variant.constructValHelper()
906 * with no incref+decref because we're moving v to this array.
909 MixedArray
* MixedArray::moveVal(TypedValue
& tv
, TypedValue v
) {
910 tv
.m_type
= v
.m_type
== KindOfUninit
? KindOfNull
: v
.m_type
;
911 tv
.m_data
.num
= v
.m_data
.num
;
915 NEVER_INLINE MixedArray
*
916 MixedArray::InsertCheckUnbalanced(MixedArray
* ad
,
921 for (uint32_t i
= 0; iter
!= stop
; ++iter
, ++i
) {
923 if (e
.isTombstone()) continue;
924 *ad
->findForNewInsertWarn(table
,
932 MixedArray
* MixedArray::SlowGrow(MixedArray
* ad
, const ArrayData
& old
,
933 MixedArrayElm
* elm
, MixedArrayElm
* end
) {
934 for (; elm
< end
; ++elm
) {
935 if (elm
->hasStrKey()) elm
->skey
->incRefCount();
936 // When we convert an element to a tombstone, we set its value type to
937 // kInvalidDataType, which is not a refcounted type.
938 tvIncRefGenUnsafe(elm
->data
);
941 auto const table
= ad
->initHash(ad
->m_scale
);
942 auto const mask
= MixedArray::Mask(ad
->m_scale
);
945 if (UNLIKELY(ad
->m_used
>= 2000)) {
946 return InsertCheckUnbalanced(ad
, table
, mask
, elm
, end
);
948 for (uint32_t i
= 0; elm
!= end
; ++elm
, ++i
) {
949 if (elm
->isTombstone()) continue;
950 *ad
->findForNewInsert(table
, mask
, elm
->probe()) = i
;
956 MixedArray
* MixedArray::Grow(MixedArray
* old
, uint32_t newScale
, bool copy
) {
957 assertx(old
->m_size
> 0);
958 assertx(MixedArray::Capacity(newScale
) >= old
->m_size
);
959 assertx(newScale
>= 1 && (newScale
& (newScale
- 1)) == 0);
961 auto ad
= reqAlloc(newScale
);
962 auto const oldUsed
= old
->m_used
;
963 ad
->m_sizeAndPos
= old
->m_sizeAndPos
;
964 ad
->initHeader_16(old
->m_kind
, OneReference
, old
->m_aux16
);
965 ad
->m_scale_used
= newScale
| uint64_t{oldUsed
} << 32;
966 ad
->m_aux16
&= ~ArrayData::kHasProvenanceData
;
968 copyElmsNextUnsafe(ad
, old
, oldUsed
);
970 // We want SlowGrow to be a tail call in the opt build, but we still want to
971 // check assertions in debug builds, so we check them in this helper.
972 auto const check
= [&](MixedArray
* res
) {
973 assertx(res
->checkInvariants());
974 assertx(res
->hasExactlyOneRef());
975 assertx(res
->kind() == old
->kind());
976 assertx(res
->dvArray() == old
->dvArray());
977 assertx(res
->isLegacyArray() == old
->isLegacyArray());
978 assertx(res
->keyTypes() == old
->keyTypes());
979 assertx(res
->m_size
== old
->m_size
);
980 assertx(res
->m_pos
== old
->m_pos
);
981 assertx(res
->m_used
== oldUsed
);
982 assertx(res
->m_scale
== newScale
);
983 return asMixed(tagArrProv(res
, old
));
987 MixedArrayElm
* elm
= ad
->data();
988 auto const end
= elm
+ oldUsed
;
989 if (ad
->keyTypes().mayIncludeCounted()) {
990 return check(SlowGrow(ad
, *old
, elm
, end
));
992 for (; elm
< end
; ++elm
) {
993 // When we convert an element to a tombstone, we set its key type to int
994 // and value type to kInvalidDataType, neither of which are refcounted.
995 tvIncRefGenUnsafe(elm
->data
);
1001 auto const table
= ad
->initHash(newScale
);
1003 auto iter
= ad
->data();
1004 auto const stop
= iter
+ oldUsed
;
1005 assertx(newScale
== ad
->m_scale
);
1006 auto mask
= MixedArray::Mask(newScale
);
1008 if (UNLIKELY(oldUsed
>= 2000)) {
1009 return check(InsertCheckUnbalanced(ad
, table
, mask
, iter
, stop
));
1011 for (uint32_t i
= 0; iter
!= stop
; ++iter
, ++i
) {
1013 if (e
.isTombstone()) continue;
1014 *ad
->findForNewInsert(table
, mask
, e
.probe()) = i
;
1020 MixedArray
* MixedArray::prepareForInsert(bool copy
) {
1021 assertx(checkInvariants());
1022 if (isFull()) return Grow(this, m_scale
* 2, copy
);
1023 if (copy
) return copyMixed();
1027 void MixedArray::compact(bool renumber
/* = false */) {
1028 bool updatePosAfterCompact
= false;
1031 // Prep work before beginning the compaction process
1032 if (LIKELY(!renumber
)) {
1033 if (m_pos
== m_used
) {
1034 // If m_pos is the canonical invalid position, we need to update it to
1035 // what the new canonical invalid position will be after compaction
1037 } else if (m_pos
!= 0) {
1038 // Cache key for element associated with m_pos in order to
1039 // update m_pos after the compaction has been performed.
1040 // We only need to do this if m_pos is nonzero and is not
1041 // the canonical invalid position.
1042 updatePosAfterCompact
= true;
1043 assertx(size_t(m_pos
) < m_used
);
1044 auto& e
= data()[m_pos
];
1045 mPos
.hash
= e
.hash();
1050 // Set m_nextKI to 0 for now to prepare for renumbering integer keys
1054 // Perform compaction
1056 auto const mask
= this->mask();
1057 auto const table
= initHash(m_scale
);
1058 for (uint32_t frPos
= 0, toPos
= 0; toPos
< m_size
; ++toPos
, ++frPos
) {
1059 while (elms
[frPos
].isTombstone()) {
1060 assertx(frPos
+ 1 < m_used
);
1063 auto& toE
= elms
[toPos
];
1064 if (toPos
!= frPos
) {
1067 if (UNLIKELY(renumber
&& toE
.hasIntKey())) {
1068 toE
.setIntKey(m_nextKI
, hash_int64(m_nextKI
));
1071 *findForNewInsert(table
, mask
, toE
.probe()) = toPos
;
1074 if (updatePosAfterCompact
) {
1075 // Update m_pos, now that compaction is complete
1076 m_pos
= mPos
.hash
>= 0 ? ssize_t(find(mPos
.skey
, mPos
.hash
))
1077 : ssize_t(find(mPos
.ikey
, mPos
.hash
));
1078 assertx(m_pos
>= 0 && m_pos
< m_size
);
1082 // Even if renumber is true, we'll leave string keys in the array untouched,
1083 // so the only keyTypes update we can do here is to unset the tombstone bit.
1084 mutableKeyTypes()->makeCompact();
1085 assertx(checkInvariants());
1088 void MixedArray::nextInsert(TypedValue v
) {
1089 assertx(m_nextKI
>= 0);
1092 int64_t ki
= m_nextKI
;
1093 auto h
= hash_int64(ki
);
1094 // The check above enforces an invariant that allows us to always
1095 // know that m_nextKI is not present in the array, so it is safe
1096 // to use findForNewInsert()
1097 auto ei
= findForNewInsert(h
);
1098 assertx(!isValidPos(ei
));
1099 // Allocate and initialize a new element.
1100 auto e
= allocElm(ei
);
1101 e
->setIntKey(ki
, h
);
1102 mutableKeyTypes()->recordInt();
1103 m_nextKI
= static_cast<uint64_t>(ki
) + 1; // Update next free element.
1107 template <class K
, bool move
> ALWAYS_INLINE
1108 ArrayData
* MixedArray::update(K k
, TypedValue data
) {
1112 setElem(p
.tv
, data
, move
);
1115 initElem(p
.tv
, data
, move
);
1119 arr_lval
MixedArray::LvalInt(ArrayData
* ad
, int64_t k
, bool copy
) {
1120 return asMixed(ad
)->prepareForInsert(copy
)->addLvalImpl
<true>(k
);
1123 arr_lval
MixedArray::LvalStr(ArrayData
* ad
, StringData
* key
, bool copy
) {
1124 return asMixed(ad
)->prepareForInsert(copy
)->addLvalImpl
<true>(key
);
1127 tv_lval
MixedArray::LvalInPlace(ArrayData
* ad
, const Variant
& k
) {
1128 auto arr
= asMixed(ad
);
1129 assertx(!arr
->isFull());
1130 assertx(!arr
->cowCheck());
1131 return k
.isInteger() ? arr
->addLvalImpl
<false>(k
.asInt64Val())
1132 : arr
->addLvalImpl
<false>(k
.asCStrRef().get());
1135 arr_lval
MixedArray::LvalSilentInt(ArrayData
* ad
, int64_t k
, bool copy
) {
1136 auto a
= asMixed(ad
);
1137 auto const pos
= a
->find(k
, hash_int64(k
));
1138 if (UNLIKELY(!validPos(pos
))) return arr_lval
{ a
, nullptr };
1139 if (copy
) a
= a
->copyMixed();
1140 return arr_lval
{ a
, &a
->data()[pos
].data
};
1143 arr_lval
MixedArray::LvalSilentStr(ArrayData
* ad
, StringData
* k
, bool copy
) {
1144 auto a
= asMixed(ad
);
1145 auto const pos
= a
->find(k
, k
->hash());
1146 if (UNLIKELY(!validPos(pos
))) return arr_lval
{ a
, nullptr };
1147 if (copy
) a
= a
->copyMixed();
1148 return arr_lval
{ a
, &a
->data()[pos
].data
};
1151 ArrayData
* MixedArray::SetInt(ArrayData
* ad
, int64_t k
, TypedValue v
) {
1152 assertx(ad
->cowCheck() || ad
->notCyclic(v
));
1153 return asMixed(ad
)->prepareForInsert(ad
->cowCheck())->update(k
, v
);
1156 ArrayData
* MixedArray::SetIntMove(ArrayData
* ad
, int64_t k
, TypedValue v
) {
1157 assertx(ad
->cowCheck() || ad
->notCyclic(v
));
1158 auto const preped
= asMixed(ad
)->prepareForInsert(ad
->cowCheck());
1159 auto const result
= preped
->update
<int64_t, true>(k
, v
);
1160 if (ad
!= result
&& ad
->decReleaseCheck()) MixedArray::Release(ad
);
1164 ArrayData
* MixedArray::SetIntInPlace(ArrayData
* ad
, int64_t k
, TypedValue v
) {
1165 assertx(!ad
->cowCheck());
1166 assertx(ad
->notCyclic(v
));
1167 return asMixed(ad
)->prepareForInsert(false/*copy*/)->update(k
, v
);
1170 ArrayData
* MixedArray::SetStr(ArrayData
* ad
, StringData
* k
, TypedValue v
) {
1171 assertx(ad
->cowCheck() || ad
->notCyclic(v
));
1172 return asMixed(ad
)->prepareForInsert(ad
->cowCheck())->update(k
, v
);
1175 ArrayData
* MixedArray::SetStrMove(ArrayData
* ad
, StringData
* k
, TypedValue v
) {
1176 assertx(ad
->cowCheck() || ad
->notCyclic(v
));
1177 auto const preped
= asMixed(ad
)->prepareForInsert(ad
->cowCheck());
1178 auto const result
= preped
->update
<StringData
*, true>(k
, v
);
1179 if (ad
!= result
&& ad
->decReleaseCheck()) MixedArray::Release(ad
);
1183 ArrayData
* MixedArray::SetStrInPlace(ArrayData
* ad
, StringData
* k
, TypedValue v
) {
1184 assertx(!ad
->cowCheck());
1185 assertx(ad
->notCyclic(v
));
1186 return asMixed(ad
)->prepareForInsert(false/*copy*/)->update(k
, v
);
1189 ArrayData
* MixedArray::AddInt(ArrayData
* ad
, int64_t k
, TypedValue v
, bool copy
) {
1190 assertx(!ad
->exists(k
));
1191 return asMixed(ad
)->prepareForInsert(copy
)->addVal(k
, v
);
1194 ArrayData
* MixedArray::AddStr(ArrayData
* ad
, StringData
* k
, TypedValue v
, bool copy
) {
1195 assertx(!ad
->exists(k
));
1196 return asMixed(ad
)->prepareForInsert(copy
)->addVal(k
, v
);
1199 //=============================================================================
1202 void MixedArray::eraseNoCompact(ssize_t pos
) {
1203 assertx(validPos(pos
));
1205 // If the internal pointer points to this element, advance it.
1208 m_pos
= nextElm(elms
, pos
);
1211 auto& e
= elms
[pos
];
1212 auto const oldTV
= e
.data
;
1213 if (e
.hasStrKey()) {
1217 mutableKeyTypes()->recordTombstone();
1220 // Mark the hash entry as "deleted".
1221 assertx(m_used
<= capacity());
1223 // Finally, decref the old value
1227 ArrayData
* MixedArray::RemoveIntImpl(ArrayData
* ad
, int64_t k
, bool copy
) {
1228 auto a
= asMixed(ad
);
1229 if (copy
) a
= a
->copyMixed();
1230 auto pos
= a
->findForRemove(k
, hash_int64(k
), false/*updateNext*/);
1231 if (validPos(pos
)) a
->erase(pos
);
1235 ArrayData
* MixedArray::RemoveInt(ArrayData
* ad
, int64_t k
) {
1236 return RemoveIntImpl(ad
, k
, ad
->cowCheck());
1240 MixedArray::RemoveStrImpl(ArrayData
* ad
, const StringData
* key
, bool copy
) {
1241 auto a
= asMixed(ad
);
1242 if (copy
) a
= a
->copyMixed();
1243 auto pos
= a
->findForRemove(key
, key
->hash());
1244 if (validPos(pos
)) a
->erase(pos
);
1248 ArrayData
* MixedArray::RemoveStr(ArrayData
* ad
, const StringData
* key
) {
1249 return RemoveStrImpl(ad
, key
, ad
->cowCheck());
1252 ArrayData
* MixedArray::Copy(const ArrayData
* ad
) {
1253 return asMixed(ad
)->copyMixed();
1256 ArrayData
* MixedArray::AppendImpl(ArrayData
* ad
, TypedValue v
, bool copy
) {
1257 assertx(copy
|| ad
->notCyclic(v
));
1258 auto a
= asMixed(ad
);
1259 if (UNLIKELY(a
->m_nextKI
< 0)) {
1260 raise_warning("Cannot add element to the array as the next element is "
1261 "already occupied");
1264 a
= a
->prepareForInsert(copy
);
1269 ArrayData
* MixedArray::Append(ArrayData
* ad
, TypedValue v
) {
1270 return AppendImpl(ad
, v
, ad
->cowCheck());
1274 * Copy an array to a new array of mixed kind, with a particular
1275 * pre-reserved size.
1278 MixedArray
* MixedArray::CopyReserve(const MixedArray
* src
,
1279 size_t expectedSize
) {
1280 auto const scale
= computeScaleFromSize(expectedSize
);
1281 auto const ad
= reqAlloc(scale
);
1282 auto const oldUsed
= src
->m_used
;
1284 auto const aux
= MixedArrayKeys::compactPacked(src
->m_aux16
) &
1285 ~ArrayData::kHasProvenanceData
;
1287 ad
->m_sizeAndPos
= src
->m_sizeAndPos
;
1288 ad
->initHeader_16(src
->m_kind
, OneReference
, aux
);
1289 ad
->m_scale
= scale
; // don't set m_used yet
1290 ad
->m_nextKI
= src
->m_nextKI
;
1292 auto const table
= ad
->initHash(scale
);
1294 auto dstElm
= ad
->data();
1295 auto srcElm
= src
->data();
1296 auto const srcStop
= src
->data() + oldUsed
;
1299 // We're not copying the tombstones over to the new array, so the
1300 // positions of the elements in the new array may be shifted. Cache
1301 // the key for element associated with src->m_pos so that we can
1302 // properly initialize ad->m_pos below.
1304 bool updatePosAfterCopy
= src
->m_pos
!= 0 && src
->m_pos
< src
->m_used
;
1305 if (updatePosAfterCopy
) {
1306 assertx(size_t(src
->m_pos
) < src
->m_used
);
1307 auto& e
= srcElm
[src
->m_pos
];
1308 mPos
.hash
= e
.probe();
1312 // Copy the elements
1313 auto mask
= MixedArray::Mask(scale
);
1314 for (; srcElm
!= srcStop
; ++srcElm
) {
1315 if (srcElm
->isTombstone()) continue;
1316 tvDup(srcElm
->data
, dstElm
->data
);
1317 auto const hash
= static_cast<int32_t>(srcElm
->probe());
1319 dstElm
->setIntKey(srcElm
->ikey
, hash
);
1321 dstElm
->setStrKey(srcElm
->skey
, hash
);
1323 *ad
->findForNewInsert(table
, mask
, hash
) = i
;
1328 // Now that we have finished copying the elements, update ad->m_pos
1329 if (updatePosAfterCopy
) {
1330 ad
->m_pos
= mPos
.hash
>= 0 ? ssize_t(ad
->find(mPos
.skey
, mPos
.hash
))
1331 : ssize_t(ad
->find(mPos
.ikey
, mPos
.hash
));
1332 assertx(ad
->m_pos
>=0 && ad
->m_pos
< ad
->m_size
);
1334 // If src->m_pos is equal to src's canonical invalid position, then
1335 // set ad->m_pos to ad's canonical invalid position.
1336 if (src
->m_pos
!= 0)
1337 ad
->m_pos
= ad
->m_size
;
1340 // Set new used value (we've removed any tombstones).
1341 assertx(i
== dstElm
- ad
->data());
1344 assertx(ad
->kind() == src
->kind());
1345 assertx(ad
->dvArray() == src
->dvArray());
1346 assertx(ad
->m_size
== src
->m_size
);
1347 assertx(ad
->hasExactlyOneRef());
1348 assertx(ad
->m_used
<= oldUsed
);
1349 assertx(ad
->m_used
== dstElm
- ad
->data());
1350 assertx(ad
->m_scale
== scale
);
1351 assertx(ad
->m_nextKI
== src
->m_nextKI
);
1352 assertx(ad
->checkInvariants());
1357 ArrayData
* MixedArray::ArrayPlusEqGeneric(ArrayData
* ad
,
1359 const ArrayData
* elems
,
1360 size_t neededSize
) {
1361 assertx(ad
->isPHPArrayType());
1362 assertx(elems
->isPHPArrayType());
1363 assertx(ret
->isMixedKind());
1365 for (ArrayIter
it(elems
); !it
.end(); it
.next()) {
1366 Variant key
= it
.first();
1367 auto const value
= it
.secondVal();
1369 if (UNLIKELY(ret
->isFull())) {
1371 ret
= CopyReserve(asMixed(ad
), neededSize
);
1374 auto tv
= key
.asTypedValue();
1375 auto p
= tv
->m_type
== KindOfInt64
1376 ? ret
->insert(tv
->m_data
.num
)
1377 : ret
->insert(tv
->m_data
.pstr
);
1386 // Note: the logic relating to how to grow in this function is coupled
1387 // to PackedArray::PlusEq.
1388 ArrayData
* MixedArray::PlusEq(ArrayData
* ad
, const ArrayData
* elems
) {
1389 assertx(asMixed(ad
)->checkInvariants());
1391 if (!ad
->isPHPArrayType()) throwInvalidAdditionException(ad
);
1392 if (!elems
->isPHPArrayType()) throwInvalidAdditionException(elems
);
1394 auto const neededSize
= ad
->size() + elems
->size();
1397 ad
->cowCheck() ? CopyReserve(asMixed(ad
), neededSize
) :
1400 if (UNLIKELY(!elems
->hasVanillaMixedLayout())) {
1401 return ArrayPlusEqGeneric(ad
, ret
, elems
, neededSize
);
1404 auto const rhs
= asMixed(elems
);
1406 auto srcElem
= rhs
->data();
1407 auto const srcStop
= rhs
->data() + rhs
->m_used
;
1408 for (; srcElem
!= srcStop
; ++srcElem
) {
1409 if (srcElem
->isTombstone()) continue;
1411 if (UNLIKELY(ret
->isFull())) {
1413 ret
= CopyReserve(ret
, neededSize
);
1416 auto const hash
= srcElem
->hash();
1417 if (srcElem
->hasStrKey()) {
1418 auto const ei
= ret
->findForInsertUpdate(srcElem
->skey
, hash
);
1419 if (isValidPos(ei
)) continue;
1420 auto e
= ret
->allocElm(ei
);
1421 e
->setStrKey(srcElem
->skey
, hash
);
1422 ret
->mutableKeyTypes()->recordStr(srcElem
->skey
);
1423 tvDup(srcElem
->data
, e
->data
);
1425 auto const ei
= ret
->findForInsertUpdate(srcElem
->ikey
, hash
);
1426 if (isValidPos(ei
)) continue;
1427 auto e
= ret
->allocElm(ei
);
1428 e
->setIntKey(srcElem
->ikey
, hash
);
1429 ret
->mutableKeyTypes()->recordInt();
1430 tvDup(srcElem
->data
, e
->data
);
1438 ArrayData
* MixedArray::ArrayMergeGeneric(MixedArray
* ret
,
1439 const ArrayData
* elems
) {
1440 assertx(ret
->isMixedKind());
1441 assertx(ret
->isNotDVArray());
1443 for (ArrayIter
it(elems
); !it
.end(); it
.next()) {
1444 Variant key
= it
.first();
1445 auto const value
= it
.secondVal();
1446 if (key
.asTypedValue()->m_type
== KindOfInt64
) {
1447 ret
->nextInsert(value
);
1449 StringData
* sd
= key
.getStringData();
1450 auto const lval
= ret
->addLvalImpl
<false>(sd
);
1451 assertx(value
.m_type
!= KindOfUninit
);
1458 ArrayData
* MixedArray::Merge(ArrayData
* ad
, const ArrayData
* elems
) {
1459 assertx(asMixed(ad
)->checkInvariants());
1460 auto const ret
= CopyReserve(asMixed(ad
), ad
->size() + elems
->size());
1461 assertx(ret
->hasExactlyOneRef());
1462 // Output is always a non-darray
1463 auto const aux
= asMixed(ad
)->keyTypes().packForAux();
1464 ret
->initHeader_16(HeaderKind::Mixed
, OneReference
, aux
);
1466 if (elems
->hasVanillaMixedLayout()) {
1467 auto const rhs
= asMixed(elems
);
1468 auto srcElem
= rhs
->data();
1469 auto const srcStop
= rhs
->data() + rhs
->m_used
;
1471 for (; srcElem
!= srcStop
; ++srcElem
) {
1472 if (isTombstone(srcElem
->data
.m_type
)) continue;
1474 if (srcElem
->hasIntKey()) {
1475 ret
->nextInsert(srcElem
->data
);
1477 auto const lval
= ret
->addLvalImpl
<false>(srcElem
->skey
);
1478 assertx(srcElem
->data
.m_type
!= KindOfUninit
);
1479 tvSet(srcElem
->data
, lval
);
1485 if (UNLIKELY(!elems
->hasVanillaPackedLayout())) {
1486 return ArrayMergeGeneric(ret
, elems
);
1489 assertx(PackedArray::checkInvariants(elems
));
1490 auto src
= packedData(elems
);
1491 auto const srcStop
= src
+ elems
->m_size
;
1492 for (; src
!= srcStop
; ++src
) {
1493 ret
->nextInsert(*src
);
1498 // Note: currently caller is responsible for calling renumber after
1499 // this. Should refactor so we handle it (we already know things
1500 // about the array).
1503 ArrayData
* MixedArray::Pop(ArrayData
* ad
, Variant
& value
) {
1504 auto a
= asMixed(ad
);
1505 if (a
->cowCheck()) a
= a
->copyMixed();
1506 auto elms
= a
->data();
1508 ssize_t pos
= IterLast(a
);
1509 assertx(pos
>= 0 && pos
< a
->m_used
);
1510 auto& e
= elms
[pos
];
1511 assertx(!isTombstone(e
.data
.m_type
));
1512 value
= tvAsCVarRef(&e
.data
);
1513 auto pos2
= e
.hasStrKey() ? a
->findForRemove(e
.skey
, e
.hash())
1514 : a
->findForRemove(e
.ikey
, e
.hash(), true);
1515 assertx(pos2
== pos
);
1518 value
= uninit_null();
1520 // To conform to PHP5 behavior, the pop operation resets the array's
1521 // internal iterator.
1522 a
->m_pos
= a
->nextElm(elms
, -1);
1526 ArrayData
* MixedArray::Dequeue(ArrayData
* adInput
, Variant
& value
) {
1527 auto a
= asMixed(adInput
);
1528 if (a
->cowCheck()) a
= a
->copyMixed();
1529 auto elms
= a
->data();
1531 ssize_t pos
= a
->nextElm(elms
, -1);
1532 assertx(pos
>= 0 && pos
< a
->m_used
);
1533 auto& e
= elms
[pos
];
1534 assertx(!isTombstone(e
.data
.m_type
));
1535 value
= tvAsCVarRef(&e
.data
);
1536 auto pos2
= e
.hasStrKey() ? a
->findForRemove(e
.skey
, e
.hash())
1537 : a
->findForRemove(e
.ikey
, e
.hash(), false);
1538 assertx(pos2
== pos
);
1541 value
= uninit_null();
1543 // Even if the array is empty, for PHP5 conformity we need call
1544 // compact() because it has side-effects that are important
1549 ArrayData
* MixedArray::Prepend(ArrayData
* adInput
, TypedValue v
) {
1550 auto a
= asMixed(adInput
)->prepareForInsert(adInput
->cowCheck());
1552 auto elms
= a
->data();
1553 if (a
->m_used
> 0 && !isTombstone(elms
[0].data
.m_type
)) {
1554 // Move the existing elements to make element 0 available.
1555 memmove(&elms
[1], &elms
[0], a
->m_used
* sizeof(*elms
));
1562 e
.setIntKey(0, hash_int64(0));
1563 a
->mutableKeyTypes()->recordInt();
1571 ArrayData
* MixedArray::ToPHPArray(ArrayData
* in
, bool copy
) {
1572 auto adIn
= asMixed(in
);
1573 assertx(adIn
->isPHPArrayKind());
1574 if (adIn
->isNotDVArray()) return adIn
;
1575 assertx(adIn
->isDArray());
1576 if (adIn
->getSize() == 0) return ArrayData::Create();
1577 auto ad
= copy
? adIn
->copyMixed() : adIn
;
1578 ad
->setDVArray(ArrayData::kNotDVArray
);
1579 if (RO::EvalArrayProvenance
) arrprov::clearTag(ad
);
1580 assertx(ad
->checkInvariants());
1584 bool MixedArray::hasIntishKeys() const {
1585 auto const elms
= data();
1586 for (uint32_t i
= 0, limit
= m_used
; i
< limit
; ++i
) {
1587 auto const& e
= elms
[i
];
1588 if (e
.isTombstone()) continue;
1589 if (e
.hasStrKey()) {
1591 if (e
.skey
->isStrictlyInteger(ignore
)) {
1600 * Copy this from adIn, intish casting all the intish string keys in
1601 * accordance with the value of the intishCast template parameter
1603 template <IntishCast IC
>
1605 ArrayData
* MixedArray::copyWithIntishCast(MixedArray
* adIn
,
1606 bool asDArray
/* = false */) {
1607 auto size
= adIn
->size();
1608 auto const elms
= adIn
->data();
1610 asMixed(asDArray
? MakeReserveDArray(size
) : MakeReserveMixed(size
));
1611 for (uint32_t i
= 0, limit
= adIn
->m_used
; i
< limit
; ++i
) {
1612 auto const& e
= elms
[i
];
1613 if (e
.isTombstone()) continue;
1614 if (e
.hasIntKey()) {
1615 out
->update(e
.ikey
, e
.data
);
1617 if (auto const intish
= tryIntishCast
<IC
>(e
.skey
)) {
1618 out
->update(*intish
, e
.data
);
1620 out
->update(e
.skey
, e
.data
);
1625 assertx(out
->isMixedKind());
1626 assertx(out
->checkInvariants());
1627 assertx(out
->hasExactlyOneRef());
1631 ArrayData
* MixedArray::ToPHPArrayIntishCast(ArrayData
* in
, bool copy
) {
1632 // the input array should already be a PHP-array so we just need to
1633 // clear DV array bits and cast any intish strings that may appear
1634 auto adIn
= asMixed(in
);
1635 assertx(adIn
->isPHPArrayKind());
1636 if (adIn
->size() == 0) return ArrayData::Create();
1638 if (copy
|| adIn
->hasIntishKeys()) {
1639 return copyWithIntishCast
<IntishCast::Cast
>(adIn
);
1641 // we don't need to CoW and there were no intish keys, so we can just update
1642 // dv-arrayness in place and get on with our day
1643 adIn
->setDVArray(ArrayData::kNotDVArray
);
1648 template <IntishCast IC
>
1650 ArrayData
* MixedArray::FromDictImpl(ArrayData
* adIn
,
1653 assertx(adIn
->isDictKind());
1654 auto a
= asMixed(adIn
);
1656 auto const size
= a
->size();
1658 if (!size
) return toDArray
? ArrayData::CreateDArray() : ArrayData::Create();
1660 // If we don't necessarily have to make a copy, first scan the dict looking
1661 // for any int-like string keys. If we don't find any, we can transform the
1663 if (!copy
&& !a
->hasIntishKeys()) {
1664 // No int-like string keys, so transform in place.
1665 a
->m_kind
= HeaderKind::Mixed
;
1666 if (toDArray
) a
->setDVArray(ArrayData::kDArray
);
1667 a
->setLegacyArray(false);
1668 if (RO::EvalArrayProvenance
) arrprov::reassignTag(a
);
1669 assertx(a
->checkInvariants());
1672 // Either we need to make a copy anyways, or we don't, but there are
1673 // int-like string keys. In either case, create the array from scratch,
1674 // inserting each element one-by-one, doing key conversion as necessary.
1675 return copyWithIntishCast
<IC
>(a
, toDArray
);
1679 ArrayData
* MixedArray::ToPHPArrayDict(ArrayData
* adIn
, bool copy
) {
1680 auto out
= FromDictImpl
<IntishCast::None
>(adIn
, copy
, false);
1681 assertx(out
->isNotDVArray());
1682 assertx(!out
->isLegacyArray());
1686 ArrayData
* MixedArray::ToPHPArrayIntishCastDict(ArrayData
* adIn
, bool copy
) {
1687 auto out
= FromDictImpl
<IntishCast::Cast
>(adIn
, copy
, false);
1688 assertx(out
->isNotDVArray());
1689 assertx(!out
->isLegacyArray());
1693 ArrayData
* MixedArray::ToDArray(ArrayData
* in
, bool copy
) {
1694 auto a
= asMixed(in
);
1695 assertx(a
->isMixedKind());
1696 if (RuntimeOption::EvalHackArrDVArrs
) return ToDict(in
, copy
);
1697 if (a
->isDArray()) return a
;
1698 if (a
->getSize() == 0) return ArrayData::CreateDArray();
1699 auto out
= copy
? a
->copyMixed() : a
;
1700 out
->setDVArray(ArrayData::kDArray
);
1701 out
->setLegacyArray(false);
1702 assertx(out
->checkInvariants());
1703 if (RO::EvalArrayProvenance
) arrprov::reassignTag(out
);
1707 ArrayData
* MixedArray::ToDArrayDict(ArrayData
* in
, bool copy
) {
1708 if (RuntimeOption::EvalHackArrDVArrs
) return in
;
1709 auto out
= FromDictImpl
<IntishCast::None
>(in
, copy
, true);
1710 assertx(out
->isDArray());
1711 assertx(!out
->isLegacyArray());
1715 MixedArray
* MixedArray::ToDictInPlace(ArrayData
* ad
) {
1716 auto a
= asMixed(ad
);
1717 assertx(a
->isMixedKind());
1718 assertx(!a
->cowCheck());
1719 a
->m_kind
= HeaderKind::Dict
;
1720 a
->setDVArray(ArrayData::kNotDVArray
);
1721 if (RO::EvalArrayProvenance
) arrprov::reassignTag(a
);
1725 ArrayData
* MixedArray::ToDict(ArrayData
* ad
, bool copy
) {
1726 auto a
= asMixed(ad
);
1727 assertx(a
->isMixedKind());
1729 if (a
->empty() && a
->m_nextKI
== 0) return ArrayData::CreateDict();
1732 auto const out
= CopyMixed(
1733 *a
, AllocMode::Request
,
1734 HeaderKind::Dict
, ArrayData::kNotDVArray
1736 return tagArrProv(out
);
1738 return tagArrProv(ToDictInPlace(a
));
1742 ArrayData
* MixedArray::ToDictDict(ArrayData
* ad
, bool) {
1743 assertx(asMixed(ad
)->checkInvariants());
1744 assertx(ad
->isDictKind());
1748 void MixedArray::Renumber(ArrayData
* ad
) {
1749 asMixed(ad
)->compact(true);
1752 void MixedArray::OnSetEvalScalar(ArrayData
* ad
) {
1753 auto a
= asMixed(ad
);
1754 if (UNLIKELY(a
->m_size
< a
->m_used
)) {
1755 a
->compact(/*renumber=*/false);
1757 a
->mutableKeyTypes()->makeStatic();
1758 auto elm
= a
->data();
1759 for (auto const end
= elm
+ a
->m_used
; elm
< end
; ++elm
) {
1760 assertx(!elm
->isTombstone());
1761 auto key
= elm
->skey
;
1762 if (elm
->hasStrKey() && !key
->isStatic()) {
1763 elm
->skey
= makeStaticString(key
);
1766 tvAsVariant(&elm
->data
).setEvalScalar();
1770 //////////////////////////////////////////////////////////////////////
1773 bool MixedArray::DictEqualHelper(const ArrayData
* ad1
, const ArrayData
* ad2
,
1775 assertx(asMixed(ad1
)->checkInvariants());
1776 assertx(asMixed(ad2
)->checkInvariants());
1777 assertx(ad1
->isDictKind());
1778 assertx(ad2
->isDictKind());
1780 if (ad1
== ad2
) return true;
1781 if (ad1
->size() != ad2
->size()) return false;
1783 // Prevent circular referenced objects/arrays or deep ones.
1784 check_recursion_error();
1787 auto const arr1
= asMixed(ad1
);
1788 auto const arr2
= asMixed(ad2
);
1789 auto elm1
= arr1
->data();
1790 auto elm2
= arr2
->data();
1791 auto i1
= arr1
->m_used
;
1792 auto i2
= arr2
->m_used
;
1793 while (i1
> 0 && i2
> 0) {
1794 if (UNLIKELY(elm1
->isTombstone())) {
1799 if (UNLIKELY(elm2
->isTombstone())) {
1804 if (elm1
->hasIntKey()) {
1805 if (!elm2
->hasIntKey()) return false;
1806 if (elm1
->ikey
!= elm2
->ikey
) return false;
1808 assertx(elm1
->hasStrKey());
1809 if (!elm2
->hasStrKey()) return false;
1810 if (!same(elm1
->skey
, elm2
->skey
)) return false;
1812 if (!tvSame(*tvAssertPlausible(&elm1
->data
), *tvAssertPlausible(&elm2
->data
))) {
1823 if (UNLIKELY(!elm2
->isTombstone())) return false;
1830 if (UNLIKELY(!elm1
->isTombstone())) return false;
1836 auto const arr1
= asMixed(ad1
);
1837 auto elm
= arr1
->data();
1838 for (auto i
= arr1
->m_used
; i
--; elm
++) {
1839 if (UNLIKELY(elm
->isTombstone())) continue;
1840 auto const other_rval
= [&] {
1841 if (elm
->hasIntKey()) {
1842 return NvGetIntDict(ad2
, elm
->ikey
);
1844 assertx(elm
->hasStrKey());
1845 return NvGetStrDict(ad2
, elm
->skey
);
1849 !tvEqual(tvAssertPlausible(elm
->data
),
1850 tvAssertPlausible(other_rval
.tv()))) {
1859 bool MixedArray::DictEqual(const ArrayData
* ad1
, const ArrayData
* ad2
) {
1860 return DictEqualHelper(ad1
, ad2
, false);
1863 bool MixedArray::DictNotEqual(const ArrayData
* ad1
, const ArrayData
* ad2
) {
1864 return !DictEqualHelper(ad1
, ad2
, false);
1867 bool MixedArray::DictSame(const ArrayData
* ad1
, const ArrayData
* ad2
) {
1868 return DictEqualHelper(ad1
, ad2
, true);
1871 bool MixedArray::DictNotSame(const ArrayData
* ad1
, const ArrayData
* ad2
) {
1872 return !DictEqualHelper(ad1
, ad2
, true);
1875 //////////////////////////////////////////////////////////////////////