hphp/runtime/base/array-util.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/runtime/base/array-util.h"
  18
  19 #include "hphp/runtime/base/array-data-defs.h"
  20 #include "hphp/runtime/base/array-init.h"
  21 #include "hphp/runtime/base/array-iterator.h"
  22 #include "hphp/runtime/base/builtin-functions.h"
  23 #include "hphp/runtime/base/comparisons.h"
  24 #include "hphp/runtime/base/runtime-error.h"
  25 #include "hphp/runtime/base/string-util.h"
  26 #include "hphp/runtime/base/thread-info.h"
  27
  28 #include "hphp/runtime/ext/std/ext_std_math.h"
  29 #include "hphp/runtime/ext/string/ext_string.h"
  30
  31 #include <folly/Optional.h>
  32
  33 #include <set>
  34 #include <utility>
  35 #include <vector>
  36
  37 namespace HPHP {
  38 ///////////////////////////////////////////////////////////////////////////////
  39 // compositions
  40
  41 Variant ArrayUtil::Splice(const Array& input, int offset, int64_t length /* = 0 */,
  42                           const Variant& replacement /* = uninit_variant */,
  43                           Array *removed /* = NULL */) {
  44   int num_in = input.size();
  45   if (offset > num_in) {
  46     offset = num_in;
  47   } else if (offset < 0 && (offset = (num_in + offset)) < 0) {
  48     offset = 0;
  49   }
  50
  51   if (length < 0) {
  52     length = num_in - offset + length;
  53   } else if (((unsigned)offset + (unsigned)length) > (unsigned)num_in) {
  54     length = num_in - offset;
  55   }
  56
  57   Array out_hash = Array::Create();
  58   int pos = 0;
  59   ArrayIter iter(input);
  60   for (; pos < offset && iter; ++pos, ++iter) {
  61     Variant key(iter.first());
  62     auto const v = iter.secondVal();
  63     if (key.isNumeric()) {
  64       out_hash.appendWithRef(v);
  65     } else {
  66       out_hash.setWithRef(key, v, true);
  67     }
  68   }
  69
  70   for (; pos < offset + length && iter; ++pos, ++iter) {
  71     if (removed) {
  72       Variant key(iter.first());
  73       auto const v = iter.secondVal();
  74       if (key.isNumeric()) {
  75         removed->appendWithRef(v);
  76       } else {
  77         removed->setWithRef(key, v, true);
  78       }
  79     }
  80   }
  81
  82   Array arr = replacement.toArray();
  83   if (!arr.empty()) {
  84     for (ArrayIter iterb(arr); iterb; ++iterb) {
  85       auto const v = iterb.secondVal();
  86       out_hash.appendWithRef(v);
  87     }
  88   }
  89
  90   for (; iter; ++iter) {
  91     Variant key(iter.first());
  92     auto const v = iter.secondVal();
  93     if (key.isNumeric()) {
  94       out_hash.appendWithRef(v);
  95     } else {
  96       out_hash.setWithRef(key, v, true);
  97     }
  98   }
  99
 100   return out_hash;
 101 }
 102
 103 Variant ArrayUtil::PadRight(const Array& input, const Variant& pad_value,
 104                             int pad_size) {
 105   int input_size = input.size();
 106   if (input_size >= pad_size) {
 107     return input;
 108   }
 109
 110   Array ret = input;
 111   for (int i = input_size; i < pad_size; i++) {
 112     ret.append(pad_value);
 113   }
 114   return ret;
 115 }
 116
 117 Variant ArrayUtil::PadLeft(const Array& input, const Variant& pad_value,
 118                            int pad_size) {
 119   int input_size = input.size();
 120   if (input_size >= pad_size) {
 121     return input;
 122   }
 123
 124   auto ret = Array::attach(
 125     MixedArray::MakeReserveLike(input.get(), pad_size)
 126   );
 127   for (int i = input_size; i < pad_size; i++) {
 128     ret.append(pad_value);
 129   }
 130   for (ArrayIter iter(input); iter; ++iter) {
 131     Variant key(iter.first());
 132     auto const v = iter.secondVal();
 133     if (key.isNumeric()) {
 134       ret.appendWithRef(v);
 135     } else {
 136       ret.setWithRef(key, v, true);
 137     }
 138   }
 139   return ret;
 140 }
 141
 142 Variant ArrayUtil::Range(unsigned char low, unsigned char high,
 143                          int64_t step /* = 1 */) {
 144   if (step <= 0) {
 145     throw_invalid_argument("step exceeds the specified range");
 146     return false;
 147   }
 148
 149   Array ret;
 150   if (low > high) { // Negative Steps
 151     for (; low >= high; low -= (unsigned int)step) {
 152       ret.append(String::FromChar(low));
 153       if (((signed int)low - step) < 0) {
 154         break;
 155       }
 156     }
 157   } else if (high > low) { // Positive Steps
 158     for (; low <= high; low += (unsigned int)step) {
 159       ret.append(String::FromChar(low));
 160       if (((signed int)low + step) > 255) {
 161         break;
 162       }
 163     }
 164   } else {
 165     ret.append(String::FromChar(low));
 166   }
 167   return ret;
 168 }
 169
 170 #define DOUBLE_DRIFT_FIX 0.000000000000001
 171
 172 namespace {
 173 // Some inputs can cause us to allocate gigantic arrays, so we have to make sure
 174 // we're not exceeding the memory limit.
 175 void rangeCheckAlloc(double estNumSteps) {
 176   // An array can hold at most INT_MAX elements
 177   if (estNumSteps > std::numeric_limits<int32_t>::max()) {
 178     tl_heap->forceOOM();
 179     check_non_safepoint_surprise();
 180     return;
 181   }
 182
 183   int32_t numElms = static_cast<int32_t>(estNumSteps);
 184   if (tl_heap->preAllocOOM(MixedArray::computeAllocBytesFromMaxElms(numElms))) {
 185     check_non_safepoint_surprise();
 186   }
 187 }
 188 }
 189
 190 Variant ArrayUtil::Range(double low, double high, double step /* = 1.0 */) {
 191   Array ret;
 192   double element;
 193   int64_t i;
 194   if (low > high) { // Negative steps
 195     if (low - high < step || step <= 0) {
 196       throw_invalid_argument("step exceeds the specified range");
 197       return false;
 198     }
 199     rangeCheckAlloc((low - high) / step);
 200     for (i = 0, element = low; element >= (high - DOUBLE_DRIFT_FIX);
 201          i++, element = low - (i * step)) {
 202       ret.append(element);
 203     }
 204   } else if (high > low) { // Positive steps
 205     if (high - low < step || step <= 0) {
 206       throw_invalid_argument("step exceeds the specified range");
 207       return false;
 208     }
 209     rangeCheckAlloc((high - low) / step);
 210     for (i = 0, element = low; element <= (high + DOUBLE_DRIFT_FIX);
 211          i++, element = low + (i * step)) {
 212       ret.append(element);
 213     }
 214   } else {
 215     ret.append(low);
 216   }
 217   return ret;
 218 }
 219
 220 Variant ArrayUtil::Range(int64_t low, int64_t high, int64_t step /* = 1 */) {
 221   Array ret;
 222   if (low > high) { // Negative steps
 223     if (low - high < step || step <= 0) {
 224       throw_invalid_argument("step exceeds the specified range");
 225       return false;
 226     }
 227     rangeCheckAlloc((low - high) / step);
 228     for (; low >= high; low -= step) {
 229       ret.append(low);
 230     }
 231   } else if (high > low) { // Positive steps
 232     if (high - low < step || step <= 0) {
 233       throw_invalid_argument("step exceeds the specified range");
 234       return false;
 235     }
 236     rangeCheckAlloc((high - low) / step);
 237     for (; low <= high; low += step) {
 238       ret.append(low);
 239     }
 240   } else {
 241     ret.append(low);
 242   }
 243   return ret;
 244 }
 245
 246 ///////////////////////////////////////////////////////////////////////////////
 247 // information and calculations
 248
 249 Variant ArrayUtil::CountValues(const Array& input) {
 250   Array ret = Array::Create();
 251   for (ArrayIter iter(input); iter; ++iter) {
 252     auto const inner = iter.secondRval().unboxed();
 253     if (isIntType(inner.type()) || isStringType(inner.type())) {
 254       if (!ret.exists(inner.tv())) {
 255         ret.set(inner.tv(), make_tv<KindOfInt64>(1));
 256       } else {
 257         ret.set(inner.tv(),
 258                 make_tv<KindOfInt64>(ret[inner.tv()].toInt64() + 1));
 259       }
 260     } else {
 261       raise_warning("Can only count STRING and INTEGER values!");
 262     }
 263   }
 264   return ret;
 265 }
 266
 267 ///////////////////////////////////////////////////////////////////////////////
 268 // manipulations
 269
 270 Variant ArrayUtil::ChangeKeyCase(const Array& input, bool lower) {
 271   Array ret = Array::Create();
 272   for (ArrayIter iter(input); iter; ++iter) {
 273     Variant key(iter.first());
 274     if (key.isString()) {
 275       if (lower) {
 276         ret.set(HHVM_FN(strtolower)(key.toString()), iter.secondVal());
 277       } else {
 278         ret.set(HHVM_FN(strtoupper)(key.toString()), iter.secondVal());
 279       }
 280     } else {
 281       ret.set(key, iter.secondVal());
 282     }
 283   }
 284   return ret;
 285 }
 286
 287 Variant ArrayUtil::Reverse(const Array& input, bool preserve_keys /* = false */) {
 288   if (input.empty()) {
 289     return empty_array();
 290   }
 291
 292   auto ret = Array::Create();
 293   auto pos_limit = input->iter_end();
 294   for (ssize_t pos = input->iter_last(); pos != pos_limit;
 295        pos = input->iter_rewind(pos)) {
 296     auto const key = input->nvGetKey(pos);
 297     if (preserve_keys || isStringType(key.m_type)) {
 298       ret.setWithRef(key, input->atPos(pos), true);
 299     } else {
 300       ret.appendWithRef(input->atPos(pos));
 301     }
 302   }
 303   return ret;
 304 }
 305
 306 static void php_array_data_shuffle(std::vector<ssize_t> &indices) {
 307   int n_elems = indices.size();
 308   if (n_elems > 1) {
 309     int n_left = n_elems;
 310     while (--n_left) {
 311       int rnd_idx = HHVM_FN(rand)(0, n_left);
 312       if (rnd_idx != n_left) {
 313         ssize_t temp = indices[n_left];
 314         indices[n_left] = indices[rnd_idx];
 315         indices[rnd_idx] = temp;
 316       }
 317     }
 318   }
 319 }
 320
 321 Variant ArrayUtil::Shuffle(const Array& input) {
 322   int count = input.size();
 323   if (count == 0) {
 324     return input;
 325   }
 326
 327   std::vector<ssize_t> indices;
 328   indices.reserve(count);
 329   auto pos_limit = input->iter_end();
 330   for (ssize_t pos = input->iter_begin(); pos != pos_limit;
 331        pos = input->iter_advance(pos)) {
 332     indices.push_back(pos);
 333   }
 334   php_array_data_shuffle(indices);
 335
 336   if (input.isVecArray()) {
 337     VecArrayInit ret(count);
 338     for (int i = 0; i < count; i++) {
 339       ssize_t pos = indices[i];
 340       ret.append(input->atPos(pos));
 341     }
 342     return ret.toVariant();
 343   } else if (input.isDict()) {
 344     DictInit ret(count);
 345     for (int i = 0; i < count; i++) {
 346       ssize_t pos = indices[i];
 347       ret.append(input->atPos(pos));
 348     }
 349     return ret.toVariant();
 350   } else if (input.isKeyset()) {
 351     KeysetInit ret(count);
 352     for (int i = 0; i < count; i++) {
 353       ssize_t pos = indices[i];
 354       ret.add(input->atPos(pos));
 355     }
 356     return ret.toVariant();
 357   } else {
 358     PackedArrayInit ret(count);
 359     for (int i = 0; i < count; i++) {
 360       ssize_t pos = indices[i];
 361       ret.appendWithRef(input->atPos(pos));
 362     }
 363     return ret.toVariant();
 364   }
 365 }
 366
 367 Variant ArrayUtil::RandomKeys(const Array& input, int num_req /* = 1 */) {
 368   int count = input.size();
 369   if (num_req <= 0 || num_req > count) {
 370     raise_warning("Second argument has to be between 1 and the "
 371                   "number of elements in the array");
 372     return init_null();
 373   }
 374
 375   if (num_req == 1) {
 376     // Iterating through the counter is correct but a bit inefficient
 377     // compared to being able to access the right offset into array data,
 378     // but necessary for this code to be agnostic to the array's internal
 379     // representation.  Assuming uniform distribution, we'll expect to
 380     // iterate through half of the array's data.
 381     ssize_t index = HHVM_FN(rand)(0, count-1);
 382     ssize_t pos = input->iter_begin();
 383     while (index--) {
 384       pos = input->iter_advance(pos);
 385     }
 386     return input->getKey(pos);
 387   }
 388
 389   std::vector<ssize_t> indices;
 390   indices.reserve(count);
 391   auto pos_limit = input->iter_end();
 392   for (ssize_t pos = input->iter_begin(); pos != pos_limit;
 393        pos = input->iter_advance(pos)) {
 394     indices.push_back(pos);
 395   }
 396   php_array_data_shuffle(indices);
 397
 398   PackedArrayInit ret(num_req);
 399   for (int i = 0; i < num_req; i++) {
 400     ssize_t pos = indices[i];
 401     ret.append(input->getKey(pos));
 402   }
 403   return ret.toVariant();
 404 }
 405
 406 Variant ArrayUtil::StringUnique(const Array& input) {
 407   Array seenValues;
 408   Array ret = Array::Create();
 409   for (ArrayIter iter(input); iter; ++iter) {
 410     auto const str = tvCastToString(iter.secondVal());
 411     if (!seenValues.exists(str)) {
 412       seenValues.set(str, 1);
 413       ret.set(iter.first(), iter.secondVal());
 414     }
 415   }
 416   return ret;
 417 }
 418
 419 Variant ArrayUtil::NumericUnique(const Array& input) {
 420   std::set<double> seenValues;
 421   Array ret = Array::Create();
 422   for (ArrayIter iter(input); iter; ++iter) {
 423     auto const value = tvCastToDouble(iter.secondVal());
 424     std::pair<std::set<double>::iterator, bool> res =
 425       seenValues.insert(value);
 426     if (res.second) { // it was inserted
 427       ret.set(iter.first(), iter.secondVal());
 428     }
 429   }
 430   return ret;
 431 }
 432
 433 Variant ArrayUtil::RegularSortUnique(const Array& input) {
 434   /* The output of this function in PHP strictly depends on the implementation
 435    * of the sort function and on whether values that compare as equal end
 436    * up in contiguous positions in the sorted array (which is not really
 437    * well-defined in case of mixed strings/numbers). To get the same result
 438    * as in PHP we thus need to replicate the PHP algorithm more closely than
 439    * in the other versions of array_unique.
 440    */
 441   if (input.size() <= 1) return input;
 442
 443   Array::SortData opaque;
 444   std::vector<int> indices;
 445   Array::SortImpl(indices, input, opaque, Array::SortRegularAscending, false);
 446
 447   int duplicates_count = 0;
 448   std::vector<bool> duplicates(indices.size(), false);
 449   int lastIdx = indices[0];
 450   Variant last = input->getValue(opaque.positions[lastIdx]);
 451   for (unsigned int i = 1; i < indices.size(); ++i) {
 452     int currentIdx = indices[i];
 453     Variant current = input->getValue(opaque.positions[currentIdx]);
 454     if (equal(current, last)) {
 455       ++duplicates_count;
 456       if (currentIdx > lastIdx) {
 457         duplicates[currentIdx] = true;
 458         continue;
 459       }
 460       duplicates[lastIdx] = true;
 461     }
 462     lastIdx = currentIdx;
 463     last = current;
 464   }
 465
 466   ArrayInit ret(indices.size() - duplicates_count, ArrayInit::Map{});
 467   int i = 0;
 468   for (ArrayIter iter(input); iter; ++iter, ++i) {
 469     if (!duplicates[i]) {
 470       ret.setValidKey(*iter.first().asTypedValue(), iter.secondVal());
 471     }
 472   }
 473   return ret.toVariant();
 474 }
 475
 476 ///////////////////////////////////////////////////////////////////////////////
 477 // iterations
 478
 479 static void create_miter_for_walk(folly::Optional<MArrayIter>& miter,
 480                                   Variant& var) {
 481   if (!var.is(KindOfObject)) {
 482     miter.emplace(var.asRef()->m_data.pref);
 483     return;
 484   }
 485
 486   auto const odata = var.getObjectData();
 487   if (odata->isCollection()) {
 488     raise_error("Collection elements cannot be taken by reference");
 489   }
 490   bool isIterable;
 491   Object iterable = odata->iterableObject(isIterable);
 492   if (isIterable) {
 493     raise_fatal_error("An iterator cannot be used with "
 494                               "foreach by reference");
 495   }
 496   Array properties = iterable->o_toIterArray(null_string,
 497                                              ObjectData::CreateRefs);
 498   miter.emplace(properties.detach());
 499 }
 500
 501 void ArrayUtil::Walk(Variant& input, PFUNC_WALK walk_function,
 502                      const void *data, bool recursive /* = false */,
 503                      PointerSet *seen /* = NULL */,
 504                      const Variant& userdata /* = uninit_variant */) {
 505   assertx(walk_function);
 506
 507   // The Optional is just to avoid copy constructing MArrayIter.
 508   folly::Optional<MArrayIter> miter;
 509   create_miter_for_walk(miter, input);
 510   assertx(miter.hasValue());
 511
 512   Variant k;
 513   Variant v;
 514   while (miter->advance()) {
 515     k = miter->key();
 516     v.assignRef(miter->val());
 517     if (recursive && v.isArray()) {
 518       assertx(seen);
 519       ArrayData *arr = v.getArrayData();
 520
 521       if (v.isReferenced()) {
 522         if (seen->find((void*)arr) != seen->end()) {
 523           raise_warning("array_walk_recursive(): recursion detected");
 524           return;
 525         }
 526         seen->insert((void*)arr);
 527       }
 528
 529       Walk(v, walk_function, data, recursive, seen, userdata);
 530       if (v.isReferenced()) {
 531         seen->erase((void*)arr);
 532       }
 533     } else {
 534       walk_function(v, k, userdata, data);
 535     }
 536   }
 537 }
 538
 539 Variant ArrayUtil::Reduce(const Array& input, PFUNC_REDUCE reduce_function,
 540                           const void *data,
 541                           const Variant& initial /* = uninit_variant */) {
 542   Variant result(initial);
 543   for (ArrayIter iter(input); iter; ++iter) {
 544     result = reduce_function(result, iter.second(), data);
 545   }
 546   return result;
 547 }
 548
 549 ///////////////////////////////////////////////////////////////////////////////
 550 }