hphp/runtime/base/zend-sort.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    | Copyright (c) 2014-2015 Etsy, Inc. (http://www.etsy.com)             |
   7    +----------------------------------------------------------------------+
   8    | This source file is subject to version 2.00 of the Zend license,     |
   9    | that is bundled with this package in the file LICENSE, and is        |
  10    | available through the world-wide-web at the following url:           |
  11    | http://www.zend.com/license/2_00.txt.                                |
  12    | If you did not receive a copy of the Zend license and are unable to  |
  13    | obtain it through the world-wide-web, please send a note to          |
  14    | license@zend.com so we can mail you a copy immediately.              |
  15    +----------------------------------------------------------------------+
  16 */
  17 #include "hphp/runtime/base/sort-flags.h"
  18 #include "hphp/runtime/base/zend-string.h"
  19 #include "hphp/runtime/base/comparisons.h"
  20 #include "hphp/runtime/base/type-array.h"
  21 #include <string.h>
  22
  23 namespace HPHP {
  24
  25 #define COMPARE_AND_RETURN(o1, o2) do { \
  26   if (equal(o1, o2)) return 0; \
  27   else if (less(o1, o2)) return -1; \
  28   else return 1; \
  29 } while (0)
  30
  31 static inline int zend_numeric_compare(const Variant& v1,
  32                                        const Variant& v2,
  33                                        UNUSED const void* unused) {
  34   auto v1_d = v1.toDouble();
  35   auto v2_d = v2.toDouble();
  36   COMPARE_AND_RETURN(v1_d, v2_d);
  37 }
  38
  39 enum StringType {
  40   REGULAR_STRING,
  41   NATURAL_STRING,
  42   LOCALE_STRING
  43 };
  44
  45 static inline int zend_string_compare_function(StringType type,
  46                                                const Variant& v1,
  47                                                const Variant& v2,
  48                                                bool case_insensitive) {
  49   int ret = 0;
  50   const auto &v1_str = v1.toString();
  51   const auto &v2_str = v2.toString();
  52
  53   switch (type) {
  54   case REGULAR_STRING:
  55     if (case_insensitive) {
  56       ret = bstrcasecmp(v1_str.data(), v1_str.size(),
  57                         v2_str.data(), v2_str.size());
  58     } else {
  59       ret = string_strcmp(v1_str.data(), v1_str.size(),
  60                           v2_str.data(), v2_str.size());
  61     }
  62     break;
  63
  64   case NATURAL_STRING:
  65     ret = string_natural_cmp(v1_str.data(), v1_str.size(),
  66                              v2_str.data(), v2_str.size(),
  67                              (int) case_insensitive);
  68     break;
  69
  70   case LOCALE_STRING:
  71     ret = strcoll(v1_str.data(), v2_str.data());
  72     break;
  73   }
  74
  75   return ret;
  76 }
  77
  78 static inline int zend_locale_string_compare(const Variant& v1,
  79                                              const Variant& v2,
  80                                              UNUSED const void* unused) {
  81   bool case_insensitive = false;
  82   return zend_string_compare_function(LOCALE_STRING, v1, v2,
  83                                       case_insensitive);
  84 }
  85
  86 static inline int zend_string_compare(const Variant& v1,
  87                                       const Variant& v2,
  88                                       UNUSED const void* unused) {
  89   bool case_insensitive = false;
  90   return zend_string_compare_function(REGULAR_STRING, v1, v2,
  91                                       case_insensitive);
  92 }
  93
  94 static inline int zend_string_case_compare(const Variant& v1,
  95                                            const Variant& v2,
  96                                            UNUSED const void* unused) {
  97   bool case_insensitive = true;
  98   return zend_string_compare_function(REGULAR_STRING, v1, v2,
  99                                       case_insensitive);
 100 }
 101
 102 static inline int zend_natural_string_compare(const Variant& v1,
 103                                               const Variant& v2,
 104                                               UNUSED const void* unused) {
 105   bool case_insensitive = false;
 106   return zend_string_compare_function(NATURAL_STRING, v1, v2,
 107                                       case_insensitive);
 108 }
 109
 110 static inline int zend_natural_string_case_compare(const Variant& v1,
 111                                                    const Variant& v2,
 112                                                    UNUSED const void* unused) {
 113   bool case_insensitive = true;
 114   return zend_string_compare_function(NATURAL_STRING, v1, v2,
 115                                       case_insensitive);
 116 }
 117
 118 static inline Variant convert_object_for_comparison(const Variant& obj) {
 119   if (obj.isObject()) return obj.toString();
 120   else return obj;
 121 }
 122
 123 static inline int zend_regular_compare(const Variant& v1,
 124                                        const Variant& v2,
 125                                        UNUSED const void* unused) {
 126   if ((v1.isNull() || v1.isInteger() || v1.isDouble() || v1.isBoolean()) &&
 127       (v2.isNull() || v2.isInteger() || v2.isDouble() || v2.isBoolean())) {
 128     return zend_numeric_compare(v1, v2, nullptr);
 129   } else if (v1.isString() && v2.isString()) {
 130     return zend_string_compare(v1, v2, nullptr);
 131   } else if (v1.isNull() && v2.isString()) {
 132     return v2.toString().size() ? 0 : -1;
 133   } else if (v1.isString() && v2.isNull()) {
 134     return v1.toString().size() ? 0 : 1;
 135   } else if (v1.isNull() && v2.isObject()) {
 136     return -1;
 137   } else if (v1.isObject() && v2.isNull()) {
 138     return 1;
 139   } else if (v1.isArray() && v2.isArray()) {
 140     const auto &v1_arr = v1.toArray();
 141     const auto &v2_arr = v2.toArray();
 142     COMPARE_AND_RETURN(v1_arr, v2_arr);
 143   } else if (v1.isObject() && v2.isObject()) {
 144     const auto &v1_obj = v1.toObject();
 145     const auto &v2_obj = v2.toObject();
 146     COMPARE_AND_RETURN(v1_obj, v2_obj);
 147   } else {
 148     /* Out of options. Do what the zend-collator code does */
 149     const auto &v1_mod = convert_object_for_comparison(v1);
 150     const auto &v2_mod = convert_object_for_comparison(v2);
 151     COMPARE_AND_RETURN(v1_mod, v2_mod);
 152   }
 153 }
 154
 155 #undef COMPARE_AND_RETURN
 156
 157 typedef struct {
 158   Array::PFUNC_CMP cmp_func;
 159   bool ascending;
 160 } SortData;
 161
 162 static inline int zend_sort_wrapper(const Variant& v1,
 163                                     const Variant& v2,
 164                                     const void *data) {
 165   SortData *sort_data = (SortData *) data;
 166   int ret = sort_data->cmp_func(v1, v2, nullptr);
 167   return sort_data->ascending ? ret : (-ret);
 168 }
 169
 170 static bool zend_sort_handler(bool renumber, Variant& array,
 171                               int sort_flags, bool ascending, bool byKey) {
 172   Array temp = array.toArray();
 173   SortData sort_data;
 174
 175   sort_data.ascending = ascending;
 176
 177   switch (sort_flags) {
 178   case SORT_NUMERIC:
 179     sort_data.cmp_func = zend_numeric_compare;
 180     break;
 181   case SORT_STRING_CASE:
 182     sort_data.cmp_func = zend_string_case_compare;
 183     break;
 184   case SORT_STRING:
 185     sort_data.cmp_func = zend_string_compare;
 186     break;
 187   case SORT_LOCALE_STRING:
 188     sort_data.cmp_func = zend_locale_string_compare;
 189     break;
 190   case SORT_NATURAL_CASE:
 191     sort_data.cmp_func = zend_natural_string_case_compare;
 192     break;
 193   case SORT_NATURAL:
 194     sort_data.cmp_func = zend_natural_string_compare;
 195     break;
 196   case SORT_REGULAR:
 197   default:
 198     sort_data.cmp_func = zend_regular_compare;
 199     break;
 200   }
 201
 202   /* Sort specified array. */
 203   temp.sort(zend_sort_wrapper, byKey, renumber, &sort_data);
 204
 205   array = temp;
 206   return true;
 207 }
 208
 209 #define CREATE_ZEND_SORT_FUNCTION(NAME, RENUMBER, BYKEY) \
 210   bool zend_ ## NAME (Variant &array, int sort_flags, bool ascending) { \
 211     return zend_sort_handler(RENUMBER, array, sort_flags, ascending, BYKEY); \
 212   }
 213
 214 CREATE_ZEND_SORT_FUNCTION(sort, true, false);
 215 CREATE_ZEND_SORT_FUNCTION(asort, false, false);
 216 CREATE_ZEND_SORT_FUNCTION(ksort, false, true);
 217
 218 #undef CREATE_ZEND_SORT_FUNCTION
 219
 220 }