hphp/runtime/base/sort-helpers.h

   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 #ifndef incl_HPHP_SORT_HELPERS_H_
  18 #define incl_HPHP_SORT_HELPERS_H_
  19
  20 #include "hphp/runtime/base/builtin-functions.h"
  21 #include "hphp/runtime/base/comparisons.h"
  22 #include "hphp/runtime/base/execution-context.h"
  23 #include "hphp/runtime/base/type-string.h"
  24 #include "hphp/runtime/base/type-variant.h"
  25 #include "hphp/runtime/base/zend-functions.h"
  26 #include "hphp/runtime/base/zend-string.h"
  27 #include "hphp/runtime/base/sort-flags.h"
  28 #include "hphp/runtime/base/mixed-array.h"
  29 #include "hphp/runtime/base/set-array.h"
  30
  31 #include "hphp/util/safesort.h"
  32
  33 namespace HPHP {
  34 ///////////////////////////////////////////////////////////////////////////////
  35
  36 // For sorting PackedArray and Vector
  37 struct TVAccessor {
  38   typedef const TypedValue& ElmT;
  39   bool isInt(ElmT elm) const { return elm.m_type == KindOfInt64; }
  40   bool isStr(ElmT elm) const { return isStringType(elm.m_type); }
  41   int64_t getInt(ElmT elm) const { return elm.m_data.num; }
  42   StringData* getStr(ElmT elm) const { return elm.m_data.pstr; }
  43   Variant getValue(ElmT elm) const { return tvAsCVarRef(&elm); }
  44 };
  45
  46 template<class Self, typename E>
  47 struct AssocKeyAccessorImpl {
  48   typedef const E& ElmT;
  49   bool isInt(ElmT elm) const { return elm.hasIntKey(); }
  50   bool isStr(ElmT elm) const { return elm.hasStrKey(); }
  51   Variant getValue(ElmT elm) const {
  52     if (isInt(elm)) {
  53       return Self::getInt(elm);
  54     }
  55     assert(isStr(elm));
  56     return Variant{Self::getStr(elm)};
  57   }
  58 };
  59
  60 template<typename E> struct AssocKeyAccessor;
  61
  62 template<>
  63 struct AssocKeyAccessor<MixedArray::Elm> :
  64   AssocKeyAccessorImpl<AssocKeyAccessor<MixedArray::Elm>, MixedArray::Elm> {
  65   static int64_t getInt(ElmT elm) { return elm.ikey; }
  66   static StringData* getStr(ElmT elm) { return elm.skey; }
  67 };
  68
  69 template<>
  70 struct AssocKeyAccessor<SetArray::Elm> :
  71   AssocKeyAccessorImpl<AssocKeyAccessor<SetArray::Elm>, SetArray::Elm> {
  72   static int64_t getInt(ElmT elm) { return elm.intKey(); }
  73   static StringData* getStr(ElmT elm) { return elm.strKey(); }
  74 };
  75
  76 template<typename E> struct AssocValAccessor {
  77   typedef const E& ElmT;
  78   bool isInt(ElmT elm) const { return elm.data.m_type == KindOfInt64; }
  79   bool isStr(ElmT elm) const { return isStringType(elm.data.m_type); }
  80   int64_t getInt(ElmT elm) const { return elm.data.m_data.num; }
  81   StringData* getStr(ElmT elm) const { return elm.data.m_data.pstr; }
  82   Variant getValue(ElmT elm) const { return tvAsCVarRef(&elm.data); }
  83 };
  84
  85
  86 /**
  87  * These comparators below are used together with safesort(), and safesort
  88  * requires that comparators return true iff left is GREATER than right.
  89  */
  90
  91 template <typename AccessorT, int sort_flags, bool ascending>
  92 struct IntElmCompare {
  93   typedef typename AccessorT::ElmT ElmT;
  94   AccessorT acc;
  95   bool operator()(ElmT left, ElmT right) const {
  96     int64_t iLeft = acc.getInt(left);
  97     int64_t iRight = acc.getInt(right);
  98     if (sort_flags == SORT_REGULAR || sort_flags == SORT_NUMERIC) {
  99       return ascending ? (iLeft > iRight) : (iLeft < iRight);
 100     }
 101     char bufLeft[21];
 102     char bufRight[21];
 103     const char* sLeft;
 104     const char* sRight;
 105     int lenLeft;
 106     int lenRight;
 107     // Take advantage of precomputed StringDatas if they are available
 108     const StringData* sdLeft = String::GetIntegerStringData(iLeft);
 109     if (sdLeft) {
 110       sLeft = sdLeft->data();
 111       lenLeft = sdLeft->size();
 112     } else {
 113       bufLeft[20] = '\0';
 114       auto sl = conv_10(iLeft, &bufLeft[20]);
 115       sLeft = sl.data();
 116       lenLeft = sl.size();
 117     }
 118     const StringData* sdRight = String::GetIntegerStringData(iRight);
 119     if (sdRight) {
 120       sRight = sdRight->data();
 121       lenRight = sdRight->size();
 122     } else {
 123       bufRight[20] = '\0';
 124       auto sl = conv_10(iRight, &bufRight[20]);
 125       sRight = sl.data();
 126       lenRight = sl.size();
 127     }
 128     if (sort_flags == SORT_STRING) {
 129       return ascending ?
 130                (string_strcmp(sLeft, lenLeft, sRight, lenRight) > 0) :
 131                (string_strcmp(sLeft, lenLeft, sRight, lenRight) < 0);
 132     }
 133     if (sort_flags == SORT_STRING_CASE) {
 134       return ascending ?
 135                (bstrcasecmp(sLeft, lenLeft, sRight, lenRight) > 0) :
 136                (bstrcasecmp(sLeft, lenLeft, sRight, lenRight) < 0);
 137     }
 138     if (sort_flags == SORT_LOCALE_STRING) {
 139       return ascending ? (strcoll(sLeft, sRight) > 0) :
 140                          (strcoll(sLeft, sRight) < 0);
 141     }
 142     if (sort_flags == SORT_NATURAL) {
 143       return ascending ?
 144                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 0) > 0) :
 145                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 0) < 0);
 146     }
 147     if (sort_flags == SORT_NATURAL_CASE) {
 148       return ascending ?
 149                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 1) > 0) :
 150                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 1) < 0);
 151     }
 152     assert(false);
 153     return true;
 154   }
 155 };
 156
 157 template <typename AccessorT, int sort_flags, bool ascending>
 158 struct StrElmCompare {
 159   typedef typename AccessorT::ElmT ElmT;
 160   AccessorT acc;
 161   bool operator()(ElmT left, ElmT right) const {
 162     StringData* sdLeft = acc.getStr(left);
 163     StringData* sdRight = acc.getStr(right);
 164     if (sort_flags == SORT_REGULAR) {
 165       return ascending ? (sdLeft->compare(sdRight) > 0) :
 166                          (sdLeft->compare(sdRight) < 0);
 167     }
 168     if (sort_flags == SORT_NUMERIC) {
 169       double dLeft = sdLeft->toDouble();
 170       double dRight = sdRight->toDouble();
 171       return ascending ? (dLeft > dRight) : (dLeft < dRight);
 172     }
 173     const char* sLeft = sdLeft->data();
 174     int lenLeft = sdLeft->size();
 175     const char* sRight = sdRight->data();
 176     int lenRight = sdRight->size();
 177     if (sort_flags == SORT_STRING) {
 178       return ascending ?
 179                (string_strcmp(sLeft, lenLeft, sRight, lenRight) > 0) :
 180                (string_strcmp(sLeft, lenLeft, sRight, lenRight) < 0);
 181     }
 182     if (sort_flags == SORT_STRING_CASE) {
 183       return ascending ?
 184                (bstrcasecmp(sLeft, lenLeft, sRight, lenRight) > 0) :
 185                (bstrcasecmp(sLeft, lenLeft, sRight, lenRight) < 0);
 186     }
 187     if (sort_flags == SORT_LOCALE_STRING) {
 188       return ascending ? (strcoll(sLeft, sRight) > 0) :
 189                          (strcoll(sLeft, sRight) < 0);
 190     }
 191     if (sort_flags == SORT_NATURAL) {
 192       return ascending ?
 193                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 0) > 0) :
 194                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 0) < 0);
 195     }
 196     if (sort_flags == SORT_NATURAL_CASE) {
 197       return ascending ?
 198                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 1) > 0) :
 199                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 1) < 0);
 200     }
 201     assert(false);
 202     return true;
 203   }
 204 };
 205
 206 template <typename AccessorT, int sort_flags, bool ascending>
 207 struct ElmCompare {
 208   typedef typename AccessorT::ElmT ElmT;
 209   AccessorT acc;
 210   bool operator()(ElmT left, ElmT right) const {
 211     // Fast paths
 212     if (sort_flags == SORT_REGULAR) {
 213       if (acc.isStr(left)) {
 214         if (LIKELY(acc.isStr(right))) {
 215           StringData* sLeft = acc.getStr(left);
 216           StringData* sRight = acc.getStr(right);
 217           return ascending ? (sLeft->compare(sRight) > 0) :
 218                              (sLeft->compare(sRight) < 0);
 219         }
 220       } else if (acc.isInt(left)) {
 221         if (LIKELY(acc.isInt(right))) {
 222           int64_t iLeft = acc.getInt(left);
 223           int64_t iRight = acc.getInt(right);
 224           return ascending ? (iLeft > iRight) : (iLeft < iRight);
 225         }
 226       }
 227     }
 228     if (sort_flags == SORT_NUMERIC) {
 229       if (acc.isInt(left)) {
 230         if (LIKELY(acc.isInt(right))) {
 231           int64_t iLeft = acc.getInt(left);
 232           int64_t iRight = acc.getInt(right);
 233           return ascending ? (iLeft > iRight) : (iLeft < iRight);
 234         }
 235       }
 236     }
 237     if (sort_flags == SORT_STRING || sort_flags == SORT_LOCALE_STRING ||
 238         sort_flags == SORT_NATURAL || sort_flags == SORT_NATURAL_CASE) {
 239       if (acc.isStr(left)) {
 240         if (LIKELY(acc.isStr(right))) {
 241           StringData* sdLeft = acc.getStr(left);
 242           StringData* sdRight = acc.getStr(right);
 243           const char* sLeft = sdLeft->data();
 244           int lenLeft = sdLeft->size();
 245           const char* sRight = sdRight->data();
 246           int lenRight = sdRight->size();
 247           if (sort_flags == SORT_STRING) {
 248             return ascending ?
 249                      (string_strcmp(sLeft, lenLeft, sRight, lenRight) > 0) :
 250                      (string_strcmp(sLeft, lenLeft, sRight, lenRight) < 0);
 251           }
 252           if (sort_flags == SORT_STRING_CASE) {
 253             return ascending ?
 254                      (bstrcasecmp(sLeft, lenLeft, sRight, lenRight) > 0) :
 255                      (bstrcasecmp(sLeft, lenLeft, sRight, lenRight) < 0);
 256           }
 257           if (sort_flags == SORT_LOCALE_STRING) {
 258             return ascending ? (strcoll(sLeft, sRight) > 0) :
 259                                (strcoll(sLeft, sRight) < 0);
 260           }
 261           if (sort_flags == SORT_NATURAL) {
 262             return ascending ?
 263               (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 0) > 0) :
 264               (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 0) < 0);
 265           }
 266           if (sort_flags == SORT_NATURAL_CASE) {
 267             return ascending ?
 268               (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 1) > 0) :
 269               (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 1) < 0);
 270           }
 271         }
 272       }
 273     }
 274     // Slow paths
 275     Variant vLeft = acc.getValue(left);
 276     Variant vRight = acc.getValue(right);
 277     if (sort_flags == SORT_REGULAR) {
 278       return ascending ? HPHP::more(vLeft, vRight) : HPHP::less(vLeft, vRight);
 279     }
 280     if (sort_flags == SORT_NUMERIC) {
 281       double dLeft = vLeft.toDouble();
 282       double dRight = vRight.toDouble();
 283       return ascending ? dLeft > dRight : dLeft < dRight;
 284     }
 285     String strLeft = vLeft.toString();
 286     String strRight = vRight.toString();
 287     const char* sLeft = strLeft.data();
 288     int lenLeft = strLeft.size();
 289     const char* sRight = strRight.data();
 290     int lenRight = strRight.size();
 291     if (sort_flags == SORT_STRING) {
 292       return ascending ?
 293                (string_strcmp(sLeft, lenLeft, sRight, lenRight) > 0) :
 294                (string_strcmp(sLeft, lenLeft, sRight, lenRight) < 0);
 295     }
 296     if (sort_flags == SORT_STRING_CASE) {
 297       return ascending ?
 298                (bstrcasecmp(sLeft, lenLeft, sRight, lenRight) > 0) :
 299                (bstrcasecmp(sLeft, lenLeft, sRight, lenRight) < 0);
 300     }
 301     if (sort_flags == SORT_LOCALE_STRING) {
 302       return ascending ?
 303                (strcoll(sLeft, sRight) > 0) :
 304                (strcoll(sLeft, sRight) < 0);
 305     }
 306     if (sort_flags == SORT_NATURAL) {
 307       return ascending ?
 308                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 0) > 0) :
 309                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 0) < 0);
 310     }
 311     if (sort_flags == SORT_NATURAL_CASE) {
 312       return ascending ?
 313                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 1) > 0) :
 314                (string_natural_cmp(sLeft, lenLeft, sRight, lenRight, 1) < 0);
 315     }
 316     assert(false);
 317     return true;
 318   }
 319 };
 320
 321 template <typename AccessorT>
 322 struct ElmUCompare {
 323   typedef typename AccessorT::ElmT ElmT;
 324   AccessorT acc;
 325   const CallCtx* ctx;
 326
 327   // only warn with HH syntax enabled
 328   ElmUCompare() : warned(!RuntimeOption::EnableHipHopSyntax) {}
 329
 330   bool operator()(ElmT left, ElmT right) const {
 331     TypedValue args[2] = {
 332       *acc.getValue(left).asCell(),
 333       *acc.getValue(right).asCell()
 334     };
 335     auto ret = Variant::attach(
 336       g_context->invokeFuncFew(*ctx, 2, args)
 337     );
 338     if (LIKELY(ret.isInteger())) {
 339       return ret.toInt64() > 0;
 340     }
 341     if (ret.isDouble()) {
 342       return ret.toDouble() > 0.0;
 343     }
 344     if (ret.isString()) {
 345       int64_t lval; double dval;
 346       auto dt = ret.getStringData()->isNumericWithVal(lval, dval, 0);
 347
 348       if (isIntType(dt)) {
 349         return lval > 0;
 350       } else if (isDoubleType(dt)) {
 351         return dval > 0;
 352       }
 353     }
 354     if (ret.isBoolean()) {
 355       if (!warned) {
 356         raise_warning("Sort comparators should not return a boolean because "
 357                       "it may result in a different sort order than expected. "
 358                       "The comparator should return an integer (negative if "
 359                       "left is less than right, positive if left is greater "
 360                       "than right, zero if they are equal).");
 361         warned = true;
 362       }
 363     }
 364     // If the comparator returned something other than int, double, or a
 365     // numeric string, we fall back to casting it to an integer.
 366     return ret.toInt64() > 0;
 367   }
 368 private:
 369   mutable bool warned;
 370 };
 371
 372 ///////////////////////////////////////////////////////////////////////////////
 373 }
 374
 375 #endif // incl_HPHP_SORT_HELPERS_H_