hphp/runtime/base/type_array.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010- 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
  17 #include <runtime/base/complex_types.h>
  18 #include <runtime/base/types.h>
  19 #include <runtime/base/comparisons.h>
  20 #include <util/exception.h>
  21 #include <runtime/base/shared/shared_map.h>
  22 #include <runtime/base/variable_serializer.h>
  23 #include <runtime/base/variable_unserializer.h>
  24 #include <runtime/base/comparisons.h>
  25 #include <runtime/base/zend/zend_string.h>
  26 #include <runtime/base/zend/zend_qsort.h>
  27 #include <runtime/base/zend/zend_printf.h>
  28 #include <runtime/base/array/array_util.h>
  29 #include <runtime/base/runtime_option.h>
  30 #include <runtime/ext/ext_iconv.h>
  31 #include <unicode/coll.h> // icu
  32 #include <util/parser/hphp.tab.hpp>
  33
  34 namespace HPHP {
  35
  36 const Array null_array = Array();
  37 const Array empty_array = HphpArray::GetStaticEmptyArray();
  38
  39 void Array::setEvalScalar() const {
  40   Array* thisPtr = const_cast<Array*>(this);
  41   if (!m_px) *thisPtr = ArrayData::Create();
  42   if (!m_px->isStatic()) {
  43     ArrayData *ad = ArrayData::GetScalarArray(m_px);
  44     *thisPtr = ad;
  45   }
  46 }
  47
  48 ///////////////////////////////////////////////////////////////////////////////
  49 // constructors
  50
  51 Array Array::Create(CVarRef name, CVarRef var) {
  52   return ArrayData::Create(name.isString() ? name.toKey() : name, var);
  53 }
  54
  55 Array::~Array() {}
  56
  57 ///////////////////////////////////////////////////////////////////////////////
  58 // operators
  59
  60 Array &Array::operator=(ArrayData *data) {
  61   ArrayBase::operator=(data);
  62   return *this;
  63 }
  64
  65 HOT_FUNC
  66 Array &Array::operator=(CArrRef arr) {
  67   ArrayBase::operator=(arr.m_px);
  68   return *this;
  69 }
  70
  71 Array &Array::operator=(CVarRef var) {
  72   return operator=(var.toArray());
  73 }
  74
  75 // Move assign
  76 Array &Array::operator =  (Variant&& v) {
  77   if (v.m_type == KindOfArray) {
  78     m_px = v.m_data.parr;
  79     v.reset();
  80   } else {
  81     *this = const_cast<CVarRef>(v);
  82   }
  83   return *this;
  84 }
  85
  86 Array Array::operator+(ArrayData *data) const {
  87   return Array(m_px).operator+=(data);
  88 }
  89
  90 Array Array::operator+(CVarRef var) const {
  91   if (var.getType() != KindOfArray) {
  92     throw BadArrayMergeException();
  93   }
  94   return operator+(var.getArrayData());
  95 }
  96
  97 Array Array::operator+(CArrRef arr) const {
  98   return operator+(arr.m_px);
  99 }
 100
 101 Array &Array::operator+=(ArrayData *data) {
 102   return mergeImpl(data, ArrayData::Plus);
 103 }
 104 Array &Array::operator+=(CVarRef var) {
 105   if (var.getType() != KindOfArray) {
 106     throw BadArrayMergeException();
 107   }
 108   return operator+=(var.getArrayData());
 109 }
 110
 111 Array &Array::operator+=(CArrRef arr) {
 112   return mergeImpl(arr.m_px, ArrayData::Plus);
 113 }
 114
 115 Array Array::diff(CVarRef array, bool by_key, bool by_value,
 116                   PFUNC_CMP key_cmp_function /* = NULL */,
 117                   const void *key_data /* = NULL */,
 118                   PFUNC_CMP value_cmp_function /* = NULL */,
 119                   const void *value_data /* = NULL */) const {
 120   if (!array.isArray()) {
 121     throw_bad_array_exception();
 122     return Array();
 123   }
 124   return diffImpl(array.getArrayData(), by_key, by_value, false,
 125                   key_cmp_function, key_data,
 126                   value_cmp_function, value_data);
 127 }
 128
 129 Array Array::intersect(CVarRef array, bool by_key, bool by_value,
 130                        PFUNC_CMP key_cmp_function /* = NULL */,
 131                        const void *key_data /* = NULL */,
 132                        PFUNC_CMP value_cmp_function /* = NULL */,
 133                        const void *value_data /* = NULL */) const {
 134   if (!array.isArray()) {
 135     throw_bad_array_exception();
 136     return Array();
 137   }
 138   return diffImpl(array.getArrayData(), by_key, by_value, true,
 139                   key_cmp_function, key_data,
 140                   value_cmp_function, value_data);
 141 }
 142
 143 int Array::CompareAsStrings(CVarRef v1, CVarRef v2, const void *data) {
 144   return equalAsStr(v1, v2) ? 0 : -1;
 145 }
 146
 147 Array Array::diffImpl(CArrRef array, bool by_key, bool by_value, bool match,
 148                       PFUNC_CMP key_cmp_function,
 149                       const void *key_data,
 150                       PFUNC_CMP value_cmp_function,
 151                       const void *value_data) const {
 152   assert(by_key || by_value);
 153   assert(by_key || key_cmp_function == nullptr);
 154   assert(by_value || value_cmp_function == nullptr);
 155   PFUNC_CMP value_cmp_as_string_function = value_cmp_function;
 156   if (!value_cmp_function) {
 157     value_cmp_function = SortStringAscending;
 158     value_cmp_as_string_function = CompareAsStrings;
 159   }
 160
 161   Array ret = Array::Create();
 162   if (by_key && !key_cmp_function) {
 163     // Fast case
 164     for (ArrayIter iter(*this); iter; ++iter) {
 165       Variant key(iter.first());
 166       CVarRef value(iter.secondRef());
 167       bool found = false;
 168       if (array->exists(key)) {
 169         if (by_value) {
 170           found = value_cmp_as_string_function(
 171             value, array.rvalAt(key, AccessFlags::Key), value_data) == 0;
 172         } else {
 173           found = true;
 174         }
 175       }
 176       if (found == match) {
 177         ret.addLval(key, true).setWithRef(value);
 178       }
 179     }
 180     return ret;
 181   }
 182
 183   if (!key_cmp_function) {
 184     key_cmp_function = SortRegularAscending;
 185   }
 186
 187   vector<int> perm1;
 188   SortData opaque1;
 189   int bottom = 0;
 190   int top = array.size();
 191   PFUNC_CMP cmp;
 192   const void *cmp_data;
 193   if (by_key) {
 194     cmp = key_cmp_function;
 195     cmp_data = key_data;
 196   } else {
 197     cmp = value_cmp_function;
 198     cmp_data = value_data;
 199   }
 200   SortImpl(perm1, array, opaque1, cmp, by_key, cmp_data);
 201
 202   for (ArrayIter iter(*this); iter; ++iter) {
 203     Variant target;
 204     if (by_key) {
 205       target = iter.first();
 206     } else {
 207       target = iter.second();
 208     }
 209
 210     int mid = -1;
 211     int min = bottom;
 212     int max = top;
 213     while (min < max) {
 214       mid = (max + min) / 2;
 215       ssize_t pos = opaque1.positions[perm1[mid]];
 216       int cmp_res =  cmp(target,
 217                          by_key ? array->getKey(pos)
 218                                 : array->getValueRef(pos),
 219                          cmp_data);
 220       if (cmp_res > 0) { // outer is bigger
 221         min = mid + 1;
 222       } else if (cmp_res == 0) {
 223         break;
 224       } else {
 225         max = mid;
 226       }
 227     }
 228     bool found = false;
 229     if (min < max) { // found
 230       // if checking both, check value
 231       if (by_key && by_value) {
 232         CVarRef val(iter.secondRef());
 233         // Have to look up and down for matches
 234         for (int i = mid; i < max; i++) {
 235           ssize_t pos = opaque1.positions[perm1[i]];
 236           if (key_cmp_function(target, array->getKey(pos), key_data) != 0) {
 237             break;
 238           }
 239           if (value_cmp_as_string_function(val, array->getValueRef(pos),
 240                                            value_data) == 0) {
 241             found = true;
 242             break;
 243           }
 244         }
 245         if (!found) {
 246           for (int i = mid-1; i >= min; i--) {
 247             ssize_t pos = opaque1.positions[perm1[i]];
 248             if (key_cmp_function(target, array->getKey(pos), key_data) != 0) {
 249               break;
 250             }
 251             if (value_cmp_as_string_function(val, array->getValueRef(pos),
 252                                              value_data) == 0) {
 253               found = true;
 254               break;
 255             }
 256           }
 257         }
 258       } else {
 259         // found at mid
 260         found = true;
 261       }
 262     }
 263
 264     if (found == match) {
 265       ret.addLval(iter.first(), true).setWithRef(iter.secondRef());
 266     }
 267   }
 268   return ret;
 269 }
 270
 271 ///////////////////////////////////////////////////////////////////////////////
 272 // manipulations
 273
 274 Array &Array::merge(CArrRef arr) {
 275   return mergeImpl(arr.m_px, ArrayData::Merge);
 276 }
 277
 278 HOT_FUNC
 279 Array &Array::mergeImpl(ArrayData *data, ArrayData::ArrayOp op) {
 280   if (m_px == nullptr || data == nullptr) {
 281     throw BadArrayMergeException();
 282   }
 283   if (!data->empty()) {
 284     if (op != ArrayData::Merge && m_px->empty()) {
 285       ArrayBase::operator=(data);
 286     } else if (m_px != data || op == ArrayData::Merge) {
 287       ArrayData *escalated = m_px->append(data, op, m_px->getCount() > 1);
 288       if (escalated != m_px) ArrayBase::operator=(escalated);
 289     }
 290   } else if (op == ArrayData::Merge) {
 291     m_px->renumber();
 292   }
 293   return *this;
 294 }
 295
 296 Array Array::slice(int offset, int length, bool preserve_keys) const {
 297   if (m_px == nullptr) return Array();
 298   return ArrayUtil::Slice(m_px, offset, length, preserve_keys);
 299 }
 300
 301 ///////////////////////////////////////////////////////////////////////////////
 302 // type conversions
 303
 304 Object Array::toObject() const {
 305   return HPHP::toObject(m_px);
 306 }
 307
 308 ///////////////////////////////////////////////////////////////////////////////
 309 // comparisons
 310
 311 bool Array::same(CArrRef v2) const {
 312   if (m_px == nullptr && v2.get() == nullptr) return true;
 313   if (m_px && v2.get()) {
 314     return m_px->equal(v2.get(), true);
 315   }
 316   return false;
 317 }
 318
 319 bool Array::same(CObjRef v2) const {
 320   return false;
 321 }
 322
 323 bool Array::equal(CArrRef v2) const {
 324   if (m_px == nullptr || v2.get() == nullptr) {
 325     return HPHP::equal(toBoolean(), v2.toBoolean());
 326   }
 327   return m_px->equal(v2.get(), false);
 328 }
 329
 330 bool Array::equal(CObjRef v2) const {
 331   if (m_px == nullptr || v2.get() == nullptr) {
 332     return HPHP::equal(toBoolean(), v2.toBoolean());
 333   }
 334   return false;
 335 }
 336
 337 bool Array::less(CArrRef v2, bool flip /* = false */) const {
 338   if (m_px == nullptr || v2.get() == nullptr) {
 339     return HPHP::less(toBoolean(), v2.toBoolean());
 340   }
 341   if (flip) {
 342     return v2.get()->compare(m_px) > 0;
 343   }
 344   return m_px->compare(v2.get()) < 0;
 345 }
 346
 347 bool Array::less(CObjRef v2) const {
 348   if (m_px == nullptr || v2.get() == nullptr) {
 349     return HPHP::less(toBoolean(), v2.toBoolean());
 350   }
 351   check_collection_compare(v2.get());
 352   return true;
 353 }
 354
 355 bool Array::less(CVarRef v2) const {
 356   if (m_px == nullptr || v2.isNull()) {
 357     return HPHP::less(toBoolean(), v2.toBoolean());
 358   }
 359   if (v2.getType() == KindOfArray) {
 360     return m_px->compare(v2.toArray().get()) < 0;
 361   }
 362   return v2.more(*this);
 363 }
 364
 365 bool Array::more(CArrRef v2, bool flip /* = true */) const {
 366   if (m_px == nullptr || v2.get() == nullptr) {
 367     return HPHP::more(toBoolean(), v2.toBoolean());
 368   }
 369   if (flip) {
 370     return v2.get()->compare(m_px) < 0;
 371   }
 372   return m_px->compare(v2.get()) > 0;
 373 }
 374
 375 bool Array::more(CObjRef v2) const {
 376   if (m_px == nullptr || v2.get() == nullptr) {
 377     return HPHP::more(toBoolean(), v2.toBoolean());
 378   }
 379   check_collection_compare(v2.get());
 380   return false;
 381 }
 382
 383 bool Array::more(CVarRef v2) const {
 384   if (m_px == nullptr || v2.isNull()) {
 385     return HPHP::more(toBoolean(), v2.toBoolean());
 386   }
 387   if (v2.getType() == KindOfArray) {
 388     return v2.toArray().get()->compare(m_px) < 0;
 389   }
 390   return v2.less(*this);
 391 }
 392
 393 ///////////////////////////////////////////////////////////////////////////////
 394 // iterator
 395
 396 HOT_FUNC
 397 ArrayIter Array::begin(CStrRef context /* = null_string */) const {
 398   return ArrayIter(m_px);
 399 }
 400
 401 void Array::escalate() {
 402   if (m_px) ArrayBase::operator=(m_px->escalate());
 403 }
 404
 405 ///////////////////////////////////////////////////////////////////////////////
 406 // offset functions
 407
 408 Variant Array::rvalAt(int key, ACCESSPARAMS_IMPL) const {
 409   if (m_px) return m_px->get((int64_t)key, flags & AccessFlags::Error);
 410   return null_variant;
 411 }
 412
 413 CVarRef Array::rvalAtRef(int key, ACCESSPARAMS_IMPL) const {
 414   if (m_px) return m_px->get((int64_t)key, flags & AccessFlags::Error);
 415   return null_variant;
 416 }
 417
 418 Variant Array::rvalAt(int64_t key, ACCESSPARAMS_IMPL) const {
 419   if (m_px) return m_px->get(key, flags & AccessFlags::Error);
 420   return null_variant;
 421 }
 422
 423 CVarRef Array::rvalAtRef(int64_t key, ACCESSPARAMS_IMPL) const {
 424   if (m_px) return m_px->get(key, flags & AccessFlags::Error);
 425   return null_variant;
 426 }
 427
 428 Variant Array::rvalAt(double key, ACCESSPARAMS_IMPL) const {
 429   if (m_px) return m_px->get(ToKey(key), flags & AccessFlags::Error);
 430   return null_variant;
 431 }
 432
 433 CVarRef Array::rvalAtRef(double key, ACCESSPARAMS_IMPL) const {
 434   if (m_px) return m_px->get(ToKey(key), flags & AccessFlags::Error);
 435   return null_variant;
 436 }
 437
 438 CVarRef Array::rvalAtRef(CStrRef key, ACCESSPARAMS_IMPL) const {
 439   if (m_px) {
 440     bool error = flags & AccessFlags::Error;
 441     if (flags & AccessFlags::Key) return m_px->get(key, error);
 442     if (key.isNull()) return m_px->get(empty_string, error);
 443     int64_t n;
 444     if (!key->isStrictlyInteger(n)) {
 445       return m_px->get(key, error);
 446     } else {
 447       return m_px->get(n, error);
 448     }
 449   }
 450   return null_variant;
 451 }
 452
 453 Variant Array::rvalAt(CStrRef key, ACCESSPARAMS_IMPL) const {
 454   return Array::rvalAtRef(key, flags);
 455 }
 456
 457 CVarRef Array::rvalAtRef(CVarRef key, ACCESSPARAMS_IMPL) const {
 458   if (!m_px) return null_variant;
 459   switch (key.m_type) {
 460   case KindOfUninit:
 461   case KindOfNull:
 462     return m_px->get(empty_string, flags & AccessFlags::Error);
 463   case KindOfBoolean:
 464   case KindOfInt64:
 465     return m_px->get(key.m_data.num, flags & AccessFlags::Error);
 466   case KindOfDouble:
 467     return m_px->get((int64_t)key.m_data.dbl, flags & AccessFlags::Error);
 468   case KindOfStaticString:
 469   case KindOfString: {
 470     int64_t n;
 471     if (!(flags & AccessFlags::Key) &&
 472         key.m_data.pstr->isStrictlyInteger(n)) {
 473       return m_px->get(n, flags & AccessFlags::Error);
 474     } else {
 475       return m_px->get(key.asCStrRef(), flags & AccessFlags::Error);
 476     }
 477   }
 478   case KindOfArray:
 479     throw_bad_type_exception("Invalid type used as key");
 480     break;
 481   case KindOfObject:
 482     if (key.isResource()) {
 483       return m_px->get(key.toInt64(), flags & AccessFlags::Error);
 484     }
 485     throw_bad_type_exception("Invalid type used as key");
 486     break;
 487   case KindOfRef:
 488     return rvalAtRef(*(key.m_data.pref->var()), flags);
 489   default:
 490     assert(false);
 491     break;
 492   }
 493   return null_variant;
 494 }
 495
 496 Variant Array::rvalAt(CVarRef key, ACCESSPARAMS_IMPL) const {
 497   return Array::rvalAtRef(key, flags);
 498 }
 499
 500 Variant *Array::lvalPtr(CStrRef key, bool forWrite, bool create) {
 501   if (create) {
 502     if (!m_px) ArrayBase::operator=(ArrayData::Create());
 503     return &lvalAt(key, AccessFlags::Key);
 504   }
 505   Variant *ret = nullptr;
 506   if (m_px) {
 507     ArrayData *escalated = m_px->lvalPtr(key, ret,
 508                                          forWrite && m_px->getCount() > 1,
 509                                          false);
 510     if (escalated != m_px) ArrayBase::operator=(escalated);
 511   }
 512   return ret;
 513 }
 514
 515 Variant &Array::lvalAt() {
 516   if (!m_px) ArrayBase::operator=(ArrayData::Create());
 517   Variant *ret = nullptr;
 518   ArrayData *arr = m_px;
 519   ArrayData *escalated = arr->lvalNew(ret, arr->getCount() > 1);
 520   if (escalated != arr) ArrayBase::operator=(escalated);
 521   assert(ret);
 522   return *ret;
 523 }
 524
 525 Variant &Array::lvalAt(CStrRef key, ACCESSPARAMS_IMPL) {
 526   if (flags & AccessFlags::Key) return lvalAtImpl(key, flags);
 527   return lvalAtImpl(key.toKey(), flags);
 528 }
 529
 530 Variant &Array::lvalAt(CVarRef key, ACCESSPARAMS_IMPL) {
 531   if (flags & AccessFlags::Key) return lvalAtImpl(key, flags);
 532   VarNR k(key.toKey());
 533   if (!k.isNull()) {
 534     return lvalAtImpl(k, flags);
 535   }
 536   return Variant::lvalBlackHole();
 537 }
 538
 539 template<typename T>
 540 inline ALWAYS_INLINE
 541 CVarRef Array::setImpl(const T &key, CVarRef v) {
 542   if (!m_px) {
 543     ArrayData *data = ArrayData::Create(key, v);
 544     ArrayBase::operator=(data);
 545   } else {
 546     ArrayData *escalated = m_px->set(key, v, (m_px->getCount() > 1));
 547     if (escalated != m_px) ArrayBase::operator=(escalated);
 548   }
 549   return v;
 550 }
 551
 552 template<typename T>
 553 inline ALWAYS_INLINE
 554 CVarRef Array::setRefImpl(const T &key, CVarRef v) {
 555   if (!m_px) {
 556     ArrayData *data = ArrayData::CreateRef(key, v);
 557     ArrayBase::operator=(data);
 558   } else {
 559     escalate();
 560     ArrayData *escalated = m_px->setRef(key, v, (m_px->getCount() > 1));
 561     if (escalated != m_px) ArrayBase::operator=(escalated);
 562   }
 563   return v;
 564 }
 565
 566 template<typename T>
 567 inline ALWAYS_INLINE
 568 CVarRef Array::addImpl(const T &key, CVarRef v) {
 569   if (!m_px) {
 570     ArrayData *data = ArrayData::Create(key, v);
 571     ArrayBase::operator=(data);
 572   } else {
 573     ArrayData *escalated = m_px->add(key, v, (m_px->getCount() > 1));
 574     if (escalated != m_px) ArrayBase::operator=(escalated);
 575   }
 576   return v;
 577 }
 578
 579 CVarRef Array::set(int64_t   key, CVarRef v) {
 580   return setImpl(key, v);
 581 }
 582
 583 CVarRef Array::set(CStrRef key, CVarRef v, bool isKey /* = false */) {
 584   if (isKey) return setImpl(key, v);
 585   return setImpl(key.toKey(), v);
 586 }
 587
 588 CVarRef Array::set(CVarRef key, CVarRef v, bool isKey /* = false */) {
 589   if (key.getRawType() == KindOfInt64) {
 590     return setImpl(key.getNumData(), v);
 591   }
 592   if (isKey) return setImpl(key, v);
 593   VarNR k(key.toKey());
 594   if (!k.isNull()) {
 595     return setImpl(k, v);
 596   }
 597   return Variant::lvalBlackHole();
 598 }
 599
 600 CVarRef Array::setRef(int64_t   key, CVarRef v) {
 601   return setRefImpl(key, v);
 602 }
 603
 604 CVarRef Array::setRef(CStrRef key, CVarRef v, bool isKey /* = false */) {
 605   if (isKey) return setRefImpl(key, v);
 606   return setRefImpl(key.toKey(), v);
 607 }
 608
 609 CVarRef Array::setRef(CVarRef key, CVarRef v, bool isKey /* = false */) {
 610   if (key.getRawType() == KindOfInt64) {
 611     return setRefImpl(key.getNumData(), v);
 612   }
 613   if (isKey) return setRefImpl(key, v);
 614   VarNR k(key.toKey());
 615   if (!k.isNull()) {
 616     return setRefImpl<Variant>(k, v);
 617   }
 618   return Variant::lvalBlackHole();
 619 }
 620
 621 CVarRef Array::add(int64_t   key, CVarRef v) {
 622   return addImpl(key, v);
 623 }
 624
 625 CVarRef Array::add(CStrRef key, CVarRef v, bool isKey /* = false */) {
 626   if (isKey) return addImpl(key, v);
 627   return addImpl(key.toKey(), v);
 628 }
 629
 630 CVarRef Array::add(CVarRef key, CVarRef v, bool isKey /* = false */) {
 631   if (key.getRawType() == KindOfInt64) {
 632     return addImpl(key.getNumData(), v);
 633   }
 634   if (isKey) return addImpl(key, v);
 635   VarNR k(key.toKey());
 636   if (!k.isNull()) {
 637     return addImpl(k, v);
 638   }
 639   return Variant::lvalBlackHole();
 640 }
 641
 642 Variant &Array::addLval(CStrRef key, bool isKey /* = false */) {
 643   if (isKey) return addLvalImpl(key);
 644   return addLvalImpl(key.toKey());
 645 }
 646
 647 Variant &Array::addLval(CVarRef key, bool isKey /* = false */) {
 648   if (key.getRawType() == KindOfInt64) {
 649     return addLvalImpl(key.getNumData());
 650   }
 651   if (isKey) return addLvalImpl(key);
 652   VarNR k(key.toKey());
 653   if (!k.isNull()) {
 654     return addLvalImpl(k);
 655   }
 656   return Variant::lvalBlackHole();
 657 }
 658
 659 ///////////////////////////////////////////////////////////////////////////////
 660 // membership functions
 661
 662 bool Array::valueExists(CVarRef search_value,
 663                         bool strict /* = false */) const {
 664   for (ArrayIter iter(*this); iter; ++iter) {
 665     if ((strict && iter.secondRef().same(search_value)) ||
 666         (!strict && iter.secondRef().equal(search_value))) {
 667       return true;
 668     }
 669   }
 670   return false;
 671 }
 672
 673 Variant Array::key(CVarRef search_value, bool strict /* = false */) const {
 674   for (ArrayIter iter(*this); iter; ++iter) {
 675     if ((strict && iter.secondRef().same(search_value)) ||
 676         (!strict && iter.secondRef().equal(search_value))) {
 677       return iter.first();
 678     }
 679   }
 680   return false; // PHP uses "false" over null in many places
 681 }
 682
 683 Array Array::keys(CVarRef search_value /* = null_variant */,
 684                   bool strict /* = false */) const {
 685   if (!search_value.isInitialized()) {
 686     ArrayInit ai(size(), ArrayInit::vectorInit);
 687     for (ArrayIter iter(*this); iter; ++iter) {
 688       ai.set(iter.first());
 689     }
 690     return ai.create();
 691   } else {
 692     Array ret = Array::Create();
 693     for (ArrayIter iter(*this); iter; ++iter) {
 694       if ((strict && iter.secondRef().same(search_value)) ||
 695           (!strict && iter.secondRef().equal(search_value))) {
 696         ret.append(iter.first());
 697       }
 698     }
 699     return ret;
 700   }
 701 }
 702
 703 Array Array::values() const {
 704   ArrayInit ai(size(), ArrayInit::vectorInit);
 705   for (ArrayIter iter(*this); iter; ++iter) {
 706     ai.set(withRefBind(iter.secondRef()));
 707   }
 708   return ai.create();
 709 }
 710
 711 bool Array::exists(CStrRef key, bool isKey /* = false */) const {
 712   if (isKey) return existsImpl(key);
 713   return existsImpl(key.toKey());
 714 }
 715
 716 bool Array::exists(CVarRef key, bool isKey /* = false */) const {
 717   switch(key.getType()) {
 718   case KindOfBoolean:
 719   case KindOfInt64:
 720     return existsImpl(key.toInt64());
 721   default:
 722     break;
 723   }
 724   if (isKey) return existsImpl(key);
 725   VarNR k(key.toKey());
 726   if (!k.isNull()) {
 727     return existsImpl(k);
 728   }
 729   return false;
 730 }
 731
 732 void Array::remove(CStrRef key, bool isString /* = false */) {
 733   if (isString) {
 734     removeImpl(key);
 735   } else {
 736     removeImpl(key.toKey());
 737   }
 738 }
 739
 740 void Array::remove(CVarRef key) {
 741   switch(key.getType()) {
 742   case KindOfBoolean:
 743   case KindOfInt64:
 744     removeImpl(key.toInt64());
 745     return;
 746   default:
 747     break;
 748   }
 749   VarNR k(key.toKey());
 750   if (!k.isNull()) {
 751     removeImpl(k);
 752   }
 753 }
 754
 755 void Array::removeAll() {
 756   operator=(Create());
 757 }
 758
 759 CVarRef Array::append(CVarRef v) {
 760   if (!m_px) {
 761     ArrayBase::operator=(ArrayData::Create(v));
 762   } else {
 763     ArrayData *escalated = m_px->append(v, (m_px->getCount() > 1));
 764     if (escalated != m_px) ArrayBase::operator=(escalated);
 765   }
 766   return v;
 767 }
 768
 769 CVarRef Array::appendRef(CVarRef v) {
 770   if (!m_px) {
 771     ArrayBase::operator=(ArrayData::CreateRef(v));
 772   } else {
 773     ArrayData *escalated = m_px->appendRef(v, (m_px->getCount() > 1));
 774     if (escalated != m_px) ArrayBase::operator=(escalated);
 775   }
 776   return v;
 777 }
 778
 779 CVarRef Array::appendWithRef(CVarRef v) {
 780   if (!m_px) ArrayBase::operator=(ArrayData::Create());
 781   ArrayData *escalated = m_px->appendWithRef(v, (m_px->getCount() > 1));
 782   if (escalated != m_px) ArrayBase::operator=(escalated);
 783   return v;
 784 }
 785
 786 Variant Array::appendOpEqual(int op, CVarRef v) {
 787   if (!m_px) ArrayBase::operator=(ArrayData::Create());
 788   Variant *cv = nullptr;
 789   ArrayData *escalated = m_px->lvalNew(cv, m_px->getCount() > 1);
 790   if (escalated != m_px) ArrayBase::operator=(escalated);
 791   assert(cv);
 792   switch (op) {
 793   case T_CONCAT_EQUAL: return concat_assign((*cv), v);
 794   case T_PLUS_EQUAL:   return ((*cv) += v);
 795   case T_MINUS_EQUAL:  return ((*cv) -= v);
 796   case T_MUL_EQUAL:    return ((*cv) *= v);
 797   case T_DIV_EQUAL:    return ((*cv) /= v);
 798   case T_MOD_EQUAL:    return ((*cv) %= v);
 799   case T_AND_EQUAL:    return ((*cv) &= v);
 800   case T_OR_EQUAL:     return ((*cv) |= v);
 801   case T_XOR_EQUAL:    return ((*cv) ^= v);
 802   case T_SL_EQUAL:     return ((*cv) <<= v);
 803   case T_SR_EQUAL:     return ((*cv) >>= v);
 804   default:
 805     throw FatalErrorException(0, "invalid operator %d", op);
 806   }
 807 }
 808
 809 Variant Array::pop() {
 810   if (m_px) {
 811     Variant ret;
 812     ArrayData *newarr = m_px->pop(ret);
 813     if (newarr != m_px) ArrayBase::operator=(newarr);
 814     return ret;
 815   }
 816   return null_variant;
 817 }
 818
 819 Variant Array::dequeue() {
 820   if (m_px) {
 821     Variant ret;
 822     ArrayData *newarr = m_px->dequeue(ret);
 823     if (newarr != m_px) ArrayBase::operator=(newarr);
 824     return ret;
 825   }
 826   return null_variant;
 827 }
 828
 829 void Array::prepend(CVarRef v) {
 830   if (!m_px) operator=(Create());
 831   assert(m_px);
 832   ArrayData *newarr = m_px->prepend(v, (m_px->getCount() > 1));
 833   if (newarr != m_px) ArrayBase::operator=(newarr);
 834 }
 835
 836 ///////////////////////////////////////////////////////////////////////////////
 837 // output functions
 838
 839 void Array::serialize(VariableSerializer *serializer,
 840                       bool isObject /* = false */) const {
 841   if (m_px) {
 842     m_px->serialize(serializer, isObject);
 843   } else {
 844     serializer->writeNull();
 845   }
 846 }
 847
 848 void Array::unserialize(VariableUnserializer *uns) {
 849   int64_t size = uns->readInt();
 850   char sep = uns->readChar();
 851   if (sep != ':') {
 852     throw Exception("Expected ':' but got '%c'", sep);
 853   }
 854   sep = uns->readChar();
 855   if (sep != '{') {
 856     throw Exception("Expected '{' but got '%c'", sep);
 857   }
 858
 859   if (size == 0) {
 860     operator=(Create());
 861   } else {
 862     // Pre-allocate an ArrayData of the given size, to avoid escalation in
 863     // the middle, which breaks references.
 864     operator=(ArrayInit(size).create());
 865     bool isAPC = (uns->getType() == VariableUnserializer::APCSerialize);
 866     for (int64_t i = 0; i < size; i++) {
 867       Variant key(uns->unserializeKey());
 868       if (!key.isString() && !key.isInteger()) {
 869         throw Exception("Invalid key");
 870       }
 871       Variant &value = isAPC ? addLval(key, true) :
 872         lvalAt(key, AccessFlags::Key);
 873       value.unserialize(uns);
 874     }
 875   }
 876
 877   sep = uns->readChar();
 878   if (sep != '}') {
 879     throw Exception("Expected '}' but got '%c'", sep);
 880   }
 881 }
 882
 883 void Array::dump() {
 884   if (m_px) {
 885     m_px->dump();
 886   } else {
 887     printf("(null)\n");
 888   }
 889 }
 890
 891 ///////////////////////////////////////////////////////////////////////////////
 892 // sorting
 893
 894 static int array_compare_func(const void *n1, const void *n2, const void *op) {
 895   int index1 = *(int*)n1;
 896   int index2 = *(int*)n2;
 897   Array::SortData *opaque = (Array::SortData*)op;
 898   ssize_t pos1 = opaque->positions[index1];
 899   ssize_t pos2 = opaque->positions[index2];
 900   if (opaque->by_key) {
 901     return opaque->cmp_func((*opaque->array)->getKey(pos1),
 902                             (*opaque->array)->getKey(pos2),
 903                             opaque->data);
 904   }
 905   return opaque->cmp_func((*opaque->array)->getValueRef(pos1),
 906                           (*opaque->array)->getValueRef(pos2),
 907                           opaque->data);
 908 }
 909
 910 static int multi_compare_func(const void *n1, const void *n2, const void *op) {
 911   int index1 = *(int*)n1;
 912   int index2 = *(int*)n2;
 913   const std::vector<Array::SortData> *opaques =
 914     (const std::vector<Array::SortData> *)op;
 915   for (unsigned int i = 0; i < opaques->size(); i++) {
 916     const Array::SortData *opaque = &opaques->at(i);
 917     ssize_t pos1 = opaque->positions[index1];
 918     ssize_t pos2 = opaque->positions[index2];
 919     int result;
 920     if (opaque->by_key) {
 921       result = opaque->cmp_func((*opaque->array)->getKey(pos1),
 922                                 (*opaque->array)->getKey(pos2),
 923                                 opaque->data);
 924     } else {
 925       result = opaque->cmp_func((*opaque->array)->getValueRef(pos1),
 926                                 (*opaque->array)->getValueRef(pos2),
 927                                 opaque->data);
 928     }
 929     if (result != 0) return result;
 930   }
 931   return 0;
 932 }
 933
 934 void Array::SortImpl(vector<int> &indices, CArrRef source,
 935                      Array::SortData &opaque, Array::PFUNC_CMP cmp_func,
 936                      bool by_key, const void *data /* = NULL */) {
 937   assert(cmp_func);
 938
 939   int count = source.size();
 940   if (count == 0) {
 941     return;
 942   }
 943   indices.reserve(count);
 944   for (int i = 0; i < count; i++) {
 945     indices.push_back(i);
 946   }
 947
 948   opaque.array = &source;
 949   opaque.by_key = by_key;
 950   opaque.cmp_func = cmp_func;
 951   opaque.data = data;
 952   opaque.positions.reserve(count);
 953   for (ssize_t pos = source->iter_begin(); pos != ArrayData::invalid_index;
 954        pos = source->iter_advance(pos)) {
 955     opaque.positions.push_back(pos);
 956   }
 957   zend_qsort(&indices[0], count, sizeof(int), array_compare_func, &opaque);
 958 }
 959
 960 void Array::sort(PFUNC_CMP cmp_func, bool by_key, bool renumber,
 961                  const void *data /* = NULL */) {
 962   Array sorted = Array::Create();
 963   SortData opaque;
 964   vector<int> indices;
 965   SortImpl(indices, *this, opaque, cmp_func, by_key, data);
 966   int count = size();
 967   for (int i = 0; i < count; i++) {
 968     ssize_t pos = opaque.positions[indices[i]];
 969     if (renumber) {
 970       sorted.appendWithRef(m_px->getValueRef(pos));
 971     } else {
 972       sorted.addLval(m_px->getKey(pos), true).
 973         setWithRef(m_px->getValueRef(pos));
 974     }
 975   }
 976   operator=(sorted);
 977 }
 978
 979 bool Array::MultiSort(std::vector<SortData> &data, bool renumber) {
 980   assert(!data.empty());
 981
 982   int count = -1;
 983   for (unsigned int k = 0; k < data.size(); k++) {
 984     SortData &opaque = data[k];
 985
 986     assert(opaque.array);
 987     assert(opaque.cmp_func);
 988     int size = opaque.array->size();
 989     if (count == -1) {
 990       count = size;
 991     } else if (count != size) {
 992       throw_invalid_argument("arrays: (inconsistent sizes)");
 993       return false;
 994     }
 995
 996     opaque.positions.reserve(size);
 997     CArrRef arr = *opaque.array;
 998     if (!arr.empty()) {
 999       for (ssize_t pos = arr->iter_begin(); pos != ArrayData::invalid_index;
1000            pos = arr->iter_advance(pos)) {
1001         opaque.positions.push_back(pos);
1002       }
1003     }
1004   }
1005   if (count == 0) {
1006     return true;
1007   }
1008
1009   int *indices = (int *)malloc(sizeof(int) * count);
1010   for (int i = 0; i < count; i++) {
1011     indices[i] = i;
1012   }
1013
1014   zend_qsort(indices, count, sizeof(int), multi_compare_func, (void *)&data);
1015
1016   for (unsigned int k = 0; k < data.size(); k++) {
1017     SortData &opaque = data[k];
1018     CArrRef arr = *opaque.array;
1019
1020     Array sorted;
1021     for (int i = 0; i < count; i++) {
1022       ssize_t pos = opaque.positions[indices[i]];
1023       Variant k(arr->getKey(pos));
1024       if (renumber && k.isInteger()) {
1025         sorted.append(arr->getValueRef(pos));
1026       } else {
1027         sorted.set(k, arr->getValueRef(pos));
1028       }
1029     }
1030     *opaque.original = sorted;
1031   }
1032
1033   free(indices);
1034   return true;
1035 }
1036
1037 int Array::SortRegularAscending(CVarRef v1, CVarRef v2, const void *data) {
1038   if (v1.less(v2)) return -1;
1039   if (v1.equal(v2)) return 0;
1040   return 1;
1041 }
1042 int Array::SortRegularDescending(CVarRef v1, CVarRef v2, const void *data) {
1043   if (v1.less(v2)) return 1;
1044   if (v1.equal(v2)) return 0;
1045   return -1;
1046 }
1047
1048 int Array::SortNumericAscending(CVarRef v1, CVarRef v2, const void *data) {
1049   double d1 = v1.toDouble();
1050   double d2 = v2.toDouble();
1051   if (d1 < d2) return -1;
1052   if (d1 == d2) return 0;
1053   return 1;
1054 }
1055 int Array::SortNumericDescending(CVarRef v1, CVarRef v2, const void *data) {
1056   double d1 = v1.toDouble();
1057   double d2 = v2.toDouble();
1058   if (d1 < d2) return 1;
1059   if (d1 == d2) return 0;
1060   return -1;
1061 }
1062
1063 int Array::SortStringAscending(CVarRef v1, CVarRef v2, const void *data) {
1064   String s1 = v1.toString();
1065   String s2 = v2.toString();
1066   return strcmp(s1.data(), s2.data());
1067 }
1068 int Array::SortStringDescending(CVarRef v1, CVarRef v2, const void *data) {
1069   String s1 = v1.toString();
1070   String s2 = v2.toString();
1071   return strcmp(s2.data(), s1.data());
1072 }
1073
1074 int Array::SortLocaleStringAscending(CVarRef v1, CVarRef v2,
1075                                      const void *data) {
1076   String s1 = v1.toString();
1077   String s2 = v2.toString();
1078
1079   return strcoll(s1.data(), s2.data());
1080 }
1081
1082 int Array::SortLocaleStringDescending(CVarRef v1, CVarRef v2,
1083                                       const void *data) {
1084   String s1 = v1.toString();
1085   String s2 = v2.toString();
1086
1087   return strcoll(s2.data(), s1.data());
1088 }
1089
1090 int Array::SortNatural(CVarRef v1, CVarRef v2, const void *data) {
1091   String s1 = v1.toString();
1092   String s2 = v2.toString();
1093   return string_natural_cmp(s1.data(), s1.size(), s2.data(), s2.size(), 0);
1094 }
1095
1096 int Array::SortNaturalCase(CVarRef v1, CVarRef v2, const void *data) {
1097   String s1 = v1.toString();
1098   String s2 = v2.toString();
1099   return string_natural_cmp(s1.data(), s1.size(), s2.data(), s2.size(), 1);
1100 }
1101
1102 ///////////////////////////////////////////////////////////////////////////////
1103 }