xref: /php-src/ext/standard/array.c (revision 5d6bc250)
1 /*
2    +----------------------------------------------------------------------+
3    | Copyright (c) The PHP Group                                          |
4    +----------------------------------------------------------------------+
5    | This source file is subject to version 3.01 of the PHP license,      |
6    | that is bundled with this package in the file LICENSE, and is        |
7    | available through the world-wide-web at the following url:           |
8    | https://www.php.net/license/3_01.txt                                 |
9    | If you did not receive a copy of the PHP license and are unable to   |
10    | obtain it through the world-wide-web, please send a note to          |
11    | license@php.net so we can mail you a copy immediately.               |
12    +----------------------------------------------------------------------+
13    | Authors: Andi Gutmans <andi@php.net>                                 |
14    |          Zeev Suraski <zeev@php.net>                                 |
15    |          Rasmus Lerdorf <rasmus@php.net>                             |
16    |          Andrei Zmievski <andrei@php.net>                            |
17    |          Stig Venaas <venaas@php.net>                                |
18    |          Jason Greene <jason@php.net>                                |
19    +----------------------------------------------------------------------+
20 */
21 
22 #include "php.h"
23 #include "php_ini.h"
24 #include <stdarg.h>
25 #include <stdlib.h>
26 #include <math.h>
27 #include <time.h>
28 #include <stdio.h>
29 #include <string.h>
30 #ifdef PHP_WIN32
31 #include "win32/unistd.h"
32 #endif
33 #include "zend_globals.h"
34 #include "zend_interfaces.h"
35 #include "php_globals.h"
36 #include "php_array.h"
37 #include "basic_functions.h"
38 #include "php_string.h"
39 #include "php_rand.h"
40 #include "php_math.h"
41 #include "zend_smart_str.h"
42 #include "zend_bitset.h"
43 #include "zend_exceptions.h"
44 #include "ext/spl/spl_array.h"
45 
46 /* {{{ defines */
47 #define EXTR_OVERWRITE			0
48 #define EXTR_SKIP				1
49 #define EXTR_PREFIX_SAME		2
50 #define	EXTR_PREFIX_ALL			3
51 #define	EXTR_PREFIX_INVALID		4
52 #define	EXTR_PREFIX_IF_EXISTS	5
53 #define	EXTR_IF_EXISTS			6
54 
55 #define EXTR_REFS				0x100
56 
57 #define CASE_LOWER				0
58 #define CASE_UPPER				1
59 
60 #define DIFF_NORMAL			1
61 #define DIFF_KEY			2
62 #define DIFF_ASSOC			6
63 #define DIFF_COMP_DATA_NONE    -1
64 #define DIFF_COMP_DATA_INTERNAL 0
65 #define DIFF_COMP_DATA_USER     1
66 #define DIFF_COMP_KEY_INTERNAL  0
67 #define DIFF_COMP_KEY_USER      1
68 
69 #define INTERSECT_NORMAL		1
70 #define INTERSECT_KEY			2
71 #define INTERSECT_ASSOC			6
72 #define INTERSECT_COMP_DATA_NONE    -1
73 #define INTERSECT_COMP_DATA_INTERNAL 0
74 #define INTERSECT_COMP_DATA_USER     1
75 #define INTERSECT_COMP_KEY_INTERNAL  0
76 #define INTERSECT_COMP_KEY_USER      1
77 /* }}} */
78 
ZEND_DECLARE_MODULE_GLOBALS(array)79 ZEND_DECLARE_MODULE_GLOBALS(array)
80 
81 /* {{{ php_array_init_globals */
82 static void php_array_init_globals(zend_array_globals *array_globals)
83 {
84 	memset(array_globals, 0, sizeof(zend_array_globals));
85 }
86 /* }}} */
87 
PHP_MINIT_FUNCTION(array)88 PHP_MINIT_FUNCTION(array) /* {{{ */
89 {
90 	ZEND_INIT_MODULE_GLOBALS(array, php_array_init_globals, NULL);
91 
92 	REGISTER_LONG_CONSTANT("EXTR_OVERWRITE", EXTR_OVERWRITE, CONST_CS | CONST_PERSISTENT);
93 	REGISTER_LONG_CONSTANT("EXTR_SKIP", EXTR_SKIP, CONST_CS | CONST_PERSISTENT);
94 	REGISTER_LONG_CONSTANT("EXTR_PREFIX_SAME", EXTR_PREFIX_SAME, CONST_CS | CONST_PERSISTENT);
95 	REGISTER_LONG_CONSTANT("EXTR_PREFIX_ALL", EXTR_PREFIX_ALL, CONST_CS | CONST_PERSISTENT);
96 	REGISTER_LONG_CONSTANT("EXTR_PREFIX_INVALID", EXTR_PREFIX_INVALID, CONST_CS | CONST_PERSISTENT);
97 	REGISTER_LONG_CONSTANT("EXTR_PREFIX_IF_EXISTS", EXTR_PREFIX_IF_EXISTS, CONST_CS | CONST_PERSISTENT);
98 	REGISTER_LONG_CONSTANT("EXTR_IF_EXISTS", EXTR_IF_EXISTS, CONST_CS | CONST_PERSISTENT);
99 	REGISTER_LONG_CONSTANT("EXTR_REFS", EXTR_REFS, CONST_CS | CONST_PERSISTENT);
100 
101 	REGISTER_LONG_CONSTANT("SORT_ASC", PHP_SORT_ASC, CONST_CS | CONST_PERSISTENT);
102 	REGISTER_LONG_CONSTANT("SORT_DESC", PHP_SORT_DESC, CONST_CS | CONST_PERSISTENT);
103 
104 	REGISTER_LONG_CONSTANT("SORT_REGULAR", PHP_SORT_REGULAR, CONST_CS | CONST_PERSISTENT);
105 	REGISTER_LONG_CONSTANT("SORT_NUMERIC", PHP_SORT_NUMERIC, CONST_CS | CONST_PERSISTENT);
106 	REGISTER_LONG_CONSTANT("SORT_STRING", PHP_SORT_STRING, CONST_CS | CONST_PERSISTENT);
107 	REGISTER_LONG_CONSTANT("SORT_LOCALE_STRING", PHP_SORT_LOCALE_STRING, CONST_CS | CONST_PERSISTENT);
108 	REGISTER_LONG_CONSTANT("SORT_NATURAL", PHP_SORT_NATURAL, CONST_CS | CONST_PERSISTENT);
109 	REGISTER_LONG_CONSTANT("SORT_FLAG_CASE", PHP_SORT_FLAG_CASE, CONST_CS | CONST_PERSISTENT);
110 
111 	REGISTER_LONG_CONSTANT("CASE_LOWER", CASE_LOWER, CONST_CS | CONST_PERSISTENT);
112 	REGISTER_LONG_CONSTANT("CASE_UPPER", CASE_UPPER, CONST_CS | CONST_PERSISTENT);
113 
114 	REGISTER_LONG_CONSTANT("COUNT_NORMAL", COUNT_NORMAL, CONST_CS | CONST_PERSISTENT);
115 	REGISTER_LONG_CONSTANT("COUNT_RECURSIVE", COUNT_RECURSIVE, CONST_CS | CONST_PERSISTENT);
116 
117 	REGISTER_LONG_CONSTANT("ARRAY_FILTER_USE_BOTH", ARRAY_FILTER_USE_BOTH, CONST_CS | CONST_PERSISTENT);
118 	REGISTER_LONG_CONSTANT("ARRAY_FILTER_USE_KEY", ARRAY_FILTER_USE_KEY, CONST_CS | CONST_PERSISTENT);
119 
120 	return SUCCESS;
121 }
122 /* }}} */
123 
PHP_MSHUTDOWN_FUNCTION(array)124 PHP_MSHUTDOWN_FUNCTION(array) /* {{{ */
125 {
126 #ifdef ZTS
127 	ts_free_id(array_globals_id);
128 #endif
129 
130 	return SUCCESS;
131 }
132 /* }}} */
133 
stable_sort_fallback(Bucket * a,Bucket * b)134 static zend_never_inline ZEND_COLD int stable_sort_fallback(Bucket *a, Bucket *b) {
135 	if (Z_EXTRA(a->val) > Z_EXTRA(b->val)) {
136 		return 1;
137 	} else if (Z_EXTRA(a->val) < Z_EXTRA(b->val)) {
138 		return -1;
139 	} else {
140 		return 0;
141 	}
142 }
143 
144 #define RETURN_STABLE_SORT(a, b, result) do { \
145 	int _result = (result); \
146 	if (EXPECTED(_result)) { \
147 		return _result; \
148 	} \
149 	return stable_sort_fallback((a), (b)); \
150 } while (0)
151 
152 /* Generate inlined unstable and stable variants, and non-inlined reversed variants. */
153 #define DEFINE_SORT_VARIANTS(name) \
154 	static zend_never_inline int php_array_##name##_unstable(Bucket *a, Bucket *b) { \
155 		return php_array_##name##_unstable_i(a, b); \
156 	} \
157 	static zend_never_inline int php_array_##name(Bucket *a, Bucket *b) { \
158 		RETURN_STABLE_SORT(a, b, php_array_##name##_unstable_i(a, b)); \
159 	} \
160 	static zend_never_inline int php_array_reverse_##name##_unstable(Bucket *a, Bucket *b) { \
161 		return php_array_##name##_unstable(a, b) * -1; \
162 	} \
163 	static zend_never_inline int php_array_reverse_##name(Bucket *a, Bucket *b) { \
164 		RETURN_STABLE_SORT(a, b, php_array_reverse_##name##_unstable(a, b)); \
165 	} \
166 
php_array_key_compare_unstable_i(Bucket * f,Bucket * s)167 static zend_always_inline int php_array_key_compare_unstable_i(Bucket *f, Bucket *s) /* {{{ */
168 {
169 	zend_uchar t;
170 	zend_long l1, l2;
171 	double d;
172 
173 	if (f->key == NULL) {
174 		if (s->key == NULL) {
175 			return (zend_long)f->h > (zend_long)s->h ? 1 : -1;
176 		} else {
177 			l1 = (zend_long)f->h;
178 			t = is_numeric_string(s->key->val, s->key->len, &l2, &d, 1);
179 			if (t == IS_LONG) {
180 				/* pass */
181 			} else if (t == IS_DOUBLE) {
182 				return ZEND_NORMALIZE_BOOL((double)l1 - d);
183 			} else {
184 				l2 = 0;
185 			}
186 		}
187 	} else {
188 		if (s->key) {
189 			return zendi_smart_strcmp(f->key, s->key);
190 		} else {
191 			l2 = (zend_long)s->h;
192 			t = is_numeric_string(f->key->val, f->key->len, &l1, &d, 1);
193 			if (t == IS_LONG) {
194 				/* pass */
195 			} else if (t == IS_DOUBLE) {
196 				return ZEND_NORMALIZE_BOOL(d - (double)l2);
197 			} else {
198 				l1 = 0;
199 			}
200 		}
201 	}
202 	return ZEND_NORMALIZE_BOOL(l1 - l2);
203 }
204 /* }}} */
205 
php_array_key_compare_numeric_unstable_i(Bucket * f,Bucket * s)206 static zend_always_inline int php_array_key_compare_numeric_unstable_i(Bucket *f, Bucket *s) /* {{{ */
207 {
208 	if (f->key == NULL && s->key == NULL) {
209 		return (zend_long)f->h > (zend_long)s->h ? 1 : -1;
210 	} else {
211 		double d1, d2;
212 		if (f->key) {
213 			d1 = zend_strtod(f->key->val, NULL);
214 		} else {
215 			d1 = (double)(zend_long)f->h;
216 		}
217 		if (s->key) {
218 			d2 = zend_strtod(s->key->val, NULL);
219 		} else {
220 			d2 = (double)(zend_long)s->h;
221 		}
222 		return ZEND_NORMALIZE_BOOL(d1 - d2);
223 	}
224 }
225 /* }}} */
226 
php_array_key_compare_string_case_unstable_i(Bucket * f,Bucket * s)227 static zend_always_inline int php_array_key_compare_string_case_unstable_i(Bucket *f, Bucket *s) /* {{{ */
228 {
229 	const char *s1, *s2;
230 	size_t l1, l2;
231 	char buf1[MAX_LENGTH_OF_LONG + 1];
232 	char buf2[MAX_LENGTH_OF_LONG + 1];
233 
234 	if (f->key) {
235 		s1 = f->key->val;
236 		l1 = f->key->len;
237 	} else {
238 		s1 = zend_print_long_to_buf(buf1 + sizeof(buf1) - 1, f->h);
239 		l1 = buf1 + sizeof(buf1) - 1 - s1;
240 	}
241 	if (s->key) {
242 		s2 = s->key->val;
243 		l2 = s->key->len;
244 	} else {
245 		s2 = zend_print_long_to_buf(buf2 + sizeof(buf2) - 1, s->h);
246 		l2 = buf2 + sizeof(buf2) - 1 - s1;
247 	}
248 	return zend_binary_strcasecmp_l(s1, l1, s2, l2);
249 }
250 /* }}} */
251 
php_array_key_compare_string_unstable_i(Bucket * f,Bucket * s)252 static zend_always_inline int php_array_key_compare_string_unstable_i(Bucket *f, Bucket *s) /* {{{ */
253 {
254 	const char *s1, *s2;
255 	size_t l1, l2;
256 	char buf1[MAX_LENGTH_OF_LONG + 1];
257 	char buf2[MAX_LENGTH_OF_LONG + 1];
258 
259 	if (f->key) {
260 		s1 = f->key->val;
261 		l1 = f->key->len;
262 	} else {
263 		s1 = zend_print_long_to_buf(buf1 + sizeof(buf1) - 1, f->h);
264 		l1 = buf1 + sizeof(buf1) - 1 - s1;
265 	}
266 	if (s->key) {
267 		s2 = s->key->val;
268 		l2 = s->key->len;
269 	} else {
270 		s2 = zend_print_long_to_buf(buf2 + sizeof(buf2) - 1, s->h);
271 		l2 = buf2 + sizeof(buf2) - 1 - s2;
272 	}
273 	return zend_binary_strcmp(s1, l1, s2, l2);
274 }
275 /* }}} */
276 
php_array_key_compare_string_natural_general(Bucket * f,Bucket * s,int fold_case)277 static int php_array_key_compare_string_natural_general(Bucket *f, Bucket *s, int fold_case) /* {{{ */
278 {
279 	const char *s1, *s2;
280 	size_t l1, l2;
281 	char buf1[MAX_LENGTH_OF_LONG + 1];
282 	char buf2[MAX_LENGTH_OF_LONG + 1];
283 
284 	if (f->key) {
285 		s1 = f->key->val;
286 		l1 = f->key->len;
287 	} else {
288 		s1 = zend_print_long_to_buf(buf1 + sizeof(buf1) - 1, f->h);
289 		l1 = buf1 + sizeof(buf1) - 1 - s1;
290 	}
291 	if (s->key) {
292 		s2 = s->key->val;
293 		l2 = s->key->len;
294 	} else {
295 		s2 = zend_print_long_to_buf(buf2 + sizeof(buf2) - 1, s->h);
296 		l2 = buf2 + sizeof(buf2) - 1 - s1;
297 	}
298 	return strnatcmp_ex(s1, l1, s2, l2, fold_case);
299 }
300 /* }}} */
301 
php_array_key_compare_string_natural_case(Bucket * a,Bucket * b)302 static int php_array_key_compare_string_natural_case(Bucket *a, Bucket *b) /* {{{ */
303 {
304 	RETURN_STABLE_SORT(a, b, php_array_key_compare_string_natural_general(a, b, 1));
305 }
306 /* }}} */
307 
php_array_reverse_key_compare_string_natural_case(Bucket * a,Bucket * b)308 static int php_array_reverse_key_compare_string_natural_case(Bucket *a, Bucket *b) /* {{{ */
309 {
310 	RETURN_STABLE_SORT(a, b, php_array_key_compare_string_natural_general(b, a, 1));
311 }
312 /* }}} */
313 
php_array_key_compare_string_natural(Bucket * a,Bucket * b)314 static int php_array_key_compare_string_natural(Bucket *a, Bucket *b) /* {{{ */
315 {
316 	RETURN_STABLE_SORT(a, b, php_array_key_compare_string_natural_general(a, b, 0));
317 }
318 /* }}} */
319 
php_array_reverse_key_compare_string_natural(Bucket * a,Bucket * b)320 static int php_array_reverse_key_compare_string_natural(Bucket *a, Bucket *b) /* {{{ */
321 {
322 	RETURN_STABLE_SORT(a, b, php_array_key_compare_string_natural_general(b, a, 0));
323 }
324 /* }}} */
325 
php_array_key_compare_string_locale_unstable_i(Bucket * f,Bucket * s)326 static zend_always_inline int php_array_key_compare_string_locale_unstable_i(Bucket *f, Bucket *s) /* {{{ */
327 {
328 	const char *s1, *s2;
329 	char buf1[MAX_LENGTH_OF_LONG + 1];
330 	char buf2[MAX_LENGTH_OF_LONG + 1];
331 
332 	if (f->key) {
333 		s1 = f->key->val;
334 	} else {
335 		s1 = zend_print_long_to_buf(buf1 + sizeof(buf1) - 1, f->h);
336 	}
337 	if (s->key) {
338 		s2 = s->key->val;
339 	} else {
340 		s2 = zend_print_long_to_buf(buf2 + sizeof(buf2) - 1, s->h);
341 	}
342 	return strcoll(s1, s2);
343 }
344 /* }}} */
345 
php_array_data_compare_unstable_i(Bucket * f,Bucket * s)346 static zend_always_inline int php_array_data_compare_unstable_i(Bucket *f, Bucket *s) /* {{{ */
347 {
348 	return zend_compare(&f->val, &s->val);
349 }
350 /* }}} */
351 
php_array_data_compare_numeric_unstable_i(Bucket * f,Bucket * s)352 static zend_always_inline int php_array_data_compare_numeric_unstable_i(Bucket *f, Bucket *s) /* {{{ */
353 {
354 	return numeric_compare_function(&f->val, &s->val);
355 }
356 /* }}} */
357 
php_array_data_compare_string_case_unstable_i(Bucket * f,Bucket * s)358 static zend_always_inline int php_array_data_compare_string_case_unstable_i(Bucket *f, Bucket *s) /* {{{ */
359 {
360 	return string_case_compare_function(&f->val, &s->val);
361 }
362 /* }}} */
363 
php_array_data_compare_string_unstable_i(Bucket * f,Bucket * s)364 static zend_always_inline int php_array_data_compare_string_unstable_i(Bucket *f, Bucket *s) /* {{{ */
365 {
366 	return string_compare_function(&f->val, &s->val);
367 }
368 /* }}} */
369 
php_array_natural_general_compare(Bucket * f,Bucket * s,int fold_case)370 static int php_array_natural_general_compare(Bucket *f, Bucket *s, int fold_case) /* {{{ */
371 {
372 	zend_string *tmp_str1, *tmp_str2;
373 	zend_string *str1 = zval_get_tmp_string(&f->val, &tmp_str1);
374 	zend_string *str2 = zval_get_tmp_string(&s->val, &tmp_str2);
375 
376 	int result = strnatcmp_ex(ZSTR_VAL(str1), ZSTR_LEN(str1), ZSTR_VAL(str2), ZSTR_LEN(str2), fold_case);
377 
378 	zend_tmp_string_release(tmp_str1);
379 	zend_tmp_string_release(tmp_str2);
380 	return result;
381 }
382 /* }}} */
383 
php_array_natural_compare_unstable_i(Bucket * a,Bucket * b)384 static zend_always_inline int php_array_natural_compare_unstable_i(Bucket *a, Bucket *b) /* {{{ */
385 {
386 	return php_array_natural_general_compare(a, b, 0);
387 }
388 /* }}} */
389 
php_array_natural_case_compare_unstable_i(Bucket * a,Bucket * b)390 static zend_always_inline int php_array_natural_case_compare_unstable_i(Bucket *a, Bucket *b) /* {{{ */
391 {
392 	return php_array_natural_general_compare(a, b, 1);
393 }
394 /* }}} */
395 
php_array_data_compare_string_locale_unstable_i(Bucket * f,Bucket * s)396 static int php_array_data_compare_string_locale_unstable_i(Bucket *f, Bucket *s) /* {{{ */
397 {
398 	return string_locale_compare_function(&f->val, &s->val);
399 }
400 /* }}} */
401 
402 DEFINE_SORT_VARIANTS(key_compare);
403 DEFINE_SORT_VARIANTS(key_compare_numeric);
404 DEFINE_SORT_VARIANTS(key_compare_string_case);
405 DEFINE_SORT_VARIANTS(key_compare_string);
406 DEFINE_SORT_VARIANTS(key_compare_string_locale);
407 DEFINE_SORT_VARIANTS(data_compare);
408 DEFINE_SORT_VARIANTS(data_compare_numeric);
409 DEFINE_SORT_VARIANTS(data_compare_string_case);
410 DEFINE_SORT_VARIANTS(data_compare_string);
411 DEFINE_SORT_VARIANTS(data_compare_string_locale);
412 DEFINE_SORT_VARIANTS(natural_compare);
413 DEFINE_SORT_VARIANTS(natural_case_compare);
414 
php_get_key_compare_func(zend_long sort_type,int reverse)415 static bucket_compare_func_t php_get_key_compare_func(zend_long sort_type, int reverse) /* {{{ */
416 {
417 	switch (sort_type & ~PHP_SORT_FLAG_CASE) {
418 		case PHP_SORT_NUMERIC:
419 			if (reverse) {
420 				return php_array_reverse_key_compare_numeric;
421 			} else {
422 				return php_array_key_compare_numeric;
423 			}
424 			break;
425 
426 		case PHP_SORT_STRING:
427 			if (sort_type & PHP_SORT_FLAG_CASE) {
428 				if (reverse) {
429 					return php_array_reverse_key_compare_string_case;
430 				} else {
431 					return php_array_key_compare_string_case;
432 				}
433 			} else {
434 				if (reverse) {
435 					return php_array_reverse_key_compare_string;
436 				} else {
437 					return php_array_key_compare_string;
438 				}
439 			}
440 			break;
441 
442 		case PHP_SORT_NATURAL:
443 			if (sort_type & PHP_SORT_FLAG_CASE) {
444 				if (reverse) {
445 					return php_array_reverse_key_compare_string_natural_case;
446 				} else {
447 					return php_array_key_compare_string_natural_case;
448 				}
449 			} else {
450 				if (reverse) {
451 					return php_array_reverse_key_compare_string_natural;
452 				} else {
453 					return php_array_key_compare_string_natural;
454 				}
455 			}
456 			break;
457 
458 		case PHP_SORT_LOCALE_STRING:
459 			if (reverse) {
460 				return php_array_reverse_key_compare_string_locale;
461 			} else {
462 				return php_array_key_compare_string_locale;
463 			}
464 			break;
465 
466 		case PHP_SORT_REGULAR:
467 		default:
468 			if (reverse) {
469 				return php_array_reverse_key_compare;
470 			} else {
471 				return php_array_key_compare;
472 			}
473 			break;
474 	}
475 	return NULL;
476 }
477 /* }}} */
478 
php_get_data_compare_func(zend_long sort_type,int reverse)479 static bucket_compare_func_t php_get_data_compare_func(zend_long sort_type, int reverse) /* {{{ */
480 {
481 	switch (sort_type & ~PHP_SORT_FLAG_CASE) {
482 		case PHP_SORT_NUMERIC:
483 			if (reverse) {
484 				return php_array_reverse_data_compare_numeric;
485 			} else {
486 				return php_array_data_compare_numeric;
487 			}
488 			break;
489 
490 		case PHP_SORT_STRING:
491 			if (sort_type & PHP_SORT_FLAG_CASE) {
492 				if (reverse) {
493 					return php_array_reverse_data_compare_string_case;
494 				} else {
495 					return php_array_data_compare_string_case;
496 				}
497 			} else {
498 				if (reverse) {
499 					return php_array_reverse_data_compare_string;
500 				} else {
501 					return php_array_data_compare_string;
502 				}
503 			}
504 			break;
505 
506 		case PHP_SORT_NATURAL:
507 			if (sort_type & PHP_SORT_FLAG_CASE) {
508 				if (reverse) {
509 					return php_array_reverse_natural_case_compare;
510 				} else {
511 					return php_array_natural_case_compare;
512 				}
513 			} else {
514 				if (reverse) {
515 					return php_array_reverse_natural_compare;
516 				} else {
517 					return php_array_natural_compare;
518 				}
519 			}
520 			break;
521 
522 		case PHP_SORT_LOCALE_STRING:
523 			if (reverse) {
524 				return php_array_reverse_data_compare_string_locale;
525 			} else {
526 				return php_array_data_compare_string_locale;
527 			}
528 			break;
529 
530 		case PHP_SORT_REGULAR:
531 		default:
532 			if (reverse) {
533 				return php_array_reverse_data_compare;
534 			} else {
535 				return php_array_data_compare;
536 			}
537 			break;
538 	}
539 	return NULL;
540 }
541 /* }}} */
542 
php_get_data_compare_func_unstable(zend_long sort_type,int reverse)543 static bucket_compare_func_t php_get_data_compare_func_unstable(zend_long sort_type, int reverse) /* {{{ */
544 {
545 	switch (sort_type & ~PHP_SORT_FLAG_CASE) {
546 		case PHP_SORT_NUMERIC:
547 			if (reverse) {
548 				return php_array_reverse_data_compare_numeric_unstable;
549 			} else {
550 				return php_array_data_compare_numeric_unstable;
551 			}
552 			break;
553 
554 		case PHP_SORT_STRING:
555 			if (sort_type & PHP_SORT_FLAG_CASE) {
556 				if (reverse) {
557 					return php_array_reverse_data_compare_string_case_unstable;
558 				} else {
559 					return php_array_data_compare_string_case_unstable;
560 				}
561 			} else {
562 				if (reverse) {
563 					return php_array_reverse_data_compare_string_unstable;
564 				} else {
565 					return php_array_data_compare_string_unstable;
566 				}
567 			}
568 			break;
569 
570 		case PHP_SORT_NATURAL:
571 			if (sort_type & PHP_SORT_FLAG_CASE) {
572 				if (reverse) {
573 					return php_array_reverse_natural_case_compare_unstable;
574 				} else {
575 					return php_array_natural_case_compare_unstable;
576 				}
577 			} else {
578 				if (reverse) {
579 					return php_array_reverse_natural_compare_unstable;
580 				} else {
581 					return php_array_natural_compare_unstable;
582 				}
583 			}
584 			break;
585 
586 		case PHP_SORT_LOCALE_STRING:
587 			if (reverse) {
588 				return php_array_reverse_data_compare_string_locale_unstable;
589 			} else {
590 				return php_array_data_compare_string_locale_unstable;
591 			}
592 			break;
593 
594 		case PHP_SORT_REGULAR:
595 		default:
596 			if (reverse) {
597 				return php_array_reverse_data_compare_unstable;
598 			} else {
599 				return php_array_data_compare_unstable;
600 			}
601 			break;
602 	}
603 	return NULL;
604 }
605 /* }}} */
606 
607 /* {{{ Sort an array by key value in reverse order */
PHP_FUNCTION(krsort)608 PHP_FUNCTION(krsort)
609 {
610 	zval *array;
611 	zend_long sort_type = PHP_SORT_REGULAR;
612 	bucket_compare_func_t cmp;
613 
614 	ZEND_PARSE_PARAMETERS_START(1, 2)
615 		Z_PARAM_ARRAY_EX(array, 0, 1)
616 		Z_PARAM_OPTIONAL
617 		Z_PARAM_LONG(sort_type)
618 	ZEND_PARSE_PARAMETERS_END();
619 
620 	cmp = php_get_key_compare_func(sort_type, 1);
621 
622 	zend_hash_sort(Z_ARRVAL_P(array), cmp, 0);
623 
624 	RETURN_TRUE;
625 }
626 /* }}} */
627 
628 /* {{{ Sort an array by key */
PHP_FUNCTION(ksort)629 PHP_FUNCTION(ksort)
630 {
631 	zval *array;
632 	zend_long sort_type = PHP_SORT_REGULAR;
633 	bucket_compare_func_t cmp;
634 
635 	ZEND_PARSE_PARAMETERS_START(1, 2)
636 		Z_PARAM_ARRAY_EX(array, 0, 1)
637 		Z_PARAM_OPTIONAL
638 		Z_PARAM_LONG(sort_type)
639 	ZEND_PARSE_PARAMETERS_END();
640 
641 	cmp = php_get_key_compare_func(sort_type, 0);
642 
643 	zend_hash_sort(Z_ARRVAL_P(array), cmp, 0);
644 
645 	RETURN_TRUE;
646 }
647 /* }}} */
648 
php_count_recursive(HashTable * ht)649 PHPAPI zend_long php_count_recursive(HashTable *ht) /* {{{ */
650 {
651 	zend_long cnt = 0;
652 	zval *element;
653 
654 	if (!(GC_FLAGS(ht) & GC_IMMUTABLE)) {
655 		if (GC_IS_RECURSIVE(ht)) {
656 			php_error_docref(NULL, E_WARNING, "Recursion detected");
657 			return 0;
658 		}
659 		GC_PROTECT_RECURSION(ht);
660 	}
661 
662 	cnt = zend_hash_num_elements(ht);
663 	ZEND_HASH_FOREACH_VAL(ht, element) {
664 		ZVAL_DEREF(element);
665 		if (Z_TYPE_P(element) == IS_ARRAY) {
666 			cnt += php_count_recursive(Z_ARRVAL_P(element));
667 		}
668 	} ZEND_HASH_FOREACH_END();
669 
670 	GC_TRY_UNPROTECT_RECURSION(ht);
671 	return cnt;
672 }
673 /* }}} */
674 
675 /* {{{ Count the number of elements in a variable (usually an array) */
PHP_FUNCTION(count)676 PHP_FUNCTION(count)
677 {
678 	zval *array;
679 	zend_long mode = COUNT_NORMAL;
680 	zend_long cnt;
681 
682 	ZEND_PARSE_PARAMETERS_START(1, 2)
683 		Z_PARAM_ZVAL(array)
684 		Z_PARAM_OPTIONAL
685 		Z_PARAM_LONG(mode)
686 	ZEND_PARSE_PARAMETERS_END();
687 
688 	if (mode != COUNT_NORMAL && mode != COUNT_RECURSIVE) {
689 		zend_argument_value_error(2, "must be either COUNT_NORMAL or COUNT_RECURSIVE");
690 		RETURN_THROWS();
691 	}
692 
693 	switch (Z_TYPE_P(array)) {
694 		case IS_ARRAY:
695 			if (mode != COUNT_RECURSIVE) {
696 				cnt = zend_hash_num_elements(Z_ARRVAL_P(array));
697 			} else {
698 				cnt = php_count_recursive(Z_ARRVAL_P(array));
699 			}
700 			RETURN_LONG(cnt);
701 			break;
702 		case IS_OBJECT: {
703 			zval retval;
704 			/* first, we check if the handler is defined */
705 			zend_object *zobj = Z_OBJ_P(array);
706 			if (zobj->handlers->count_elements) {
707 				RETVAL_LONG(1);
708 				if (SUCCESS == zobj->handlers->count_elements(zobj, &Z_LVAL_P(return_value))) {
709 					return;
710 				}
711 				if (EG(exception)) {
712 					RETURN_THROWS();
713 				}
714 			}
715 			/* if not and the object implements Countable we call its count() method */
716 			if (instanceof_function(zobj->ce, zend_ce_countable)) {
717 				zend_function *count_fn = zend_hash_find_ptr(&zobj->ce->function_table, ZSTR_KNOWN(ZEND_STR_COUNT));
718 				zend_call_known_instance_method_with_0_params(count_fn, zobj, &retval);
719 				if (Z_TYPE(retval) != IS_UNDEF) {
720 					RETVAL_LONG(zval_get_long(&retval));
721 					zval_ptr_dtor(&retval);
722 				}
723 				return;
724 			}
725 		}
726 		ZEND_FALLTHROUGH;
727 		default:
728 			zend_argument_type_error(1, "must be of type Countable|array, %s given", zend_zval_type_name(array));
729 			RETURN_THROWS();
730 	}
731 }
732 /* }}} */
733 
php_natsort(INTERNAL_FUNCTION_PARAMETERS,int fold_case)734 static void php_natsort(INTERNAL_FUNCTION_PARAMETERS, int fold_case) /* {{{ */
735 {
736 	zval *array;
737 
738 	ZEND_PARSE_PARAMETERS_START(1, 1)
739 		Z_PARAM_ARRAY_EX(array, 0, 1)
740 	ZEND_PARSE_PARAMETERS_END();
741 
742 	if (fold_case) {
743 		zend_hash_sort(Z_ARRVAL_P(array), php_array_natural_case_compare, 0);
744 	} else {
745 		zend_hash_sort(Z_ARRVAL_P(array), php_array_natural_compare, 0);
746 	}
747 
748 	RETURN_TRUE;
749 }
750 /* }}} */
751 
752 /* {{{ Sort an array using natural sort */
PHP_FUNCTION(natsort)753 PHP_FUNCTION(natsort)
754 {
755 	php_natsort(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0);
756 }
757 /* }}} */
758 
759 /* {{{ Sort an array using case-insensitive natural sort */
PHP_FUNCTION(natcasesort)760 PHP_FUNCTION(natcasesort)
761 {
762 	php_natsort(INTERNAL_FUNCTION_PARAM_PASSTHRU, 1);
763 }
764 /* }}} */
765 
766 /* {{{ Sort an array and maintain index association */
PHP_FUNCTION(asort)767 PHP_FUNCTION(asort)
768 {
769 	zval *array;
770 	zend_long sort_type = PHP_SORT_REGULAR;
771 	bucket_compare_func_t cmp;
772 
773 	ZEND_PARSE_PARAMETERS_START(1, 2)
774 		Z_PARAM_ARRAY_EX(array, 0, 1)
775 		Z_PARAM_OPTIONAL
776 		Z_PARAM_LONG(sort_type)
777 	ZEND_PARSE_PARAMETERS_END();
778 
779 	cmp = php_get_data_compare_func(sort_type, 0);
780 
781 	zend_hash_sort(Z_ARRVAL_P(array), cmp, 0);
782 
783 	RETURN_TRUE;
784 }
785 /* }}} */
786 
787 /* {{{ Sort an array in reverse order and maintain index association */
PHP_FUNCTION(arsort)788 PHP_FUNCTION(arsort)
789 {
790 	zval *array;
791 	zend_long sort_type = PHP_SORT_REGULAR;
792 	bucket_compare_func_t cmp;
793 
794 	ZEND_PARSE_PARAMETERS_START(1, 2)
795 		Z_PARAM_ARRAY_EX(array, 0, 1)
796 		Z_PARAM_OPTIONAL
797 		Z_PARAM_LONG(sort_type)
798 	ZEND_PARSE_PARAMETERS_END();
799 
800 	cmp = php_get_data_compare_func(sort_type, 1);
801 
802 	zend_hash_sort(Z_ARRVAL_P(array), cmp, 0);
803 
804 	RETURN_TRUE;
805 }
806 /* }}} */
807 
808 /* {{{ Sort an array */
PHP_FUNCTION(sort)809 PHP_FUNCTION(sort)
810 {
811 	zval *array;
812 	zend_long sort_type = PHP_SORT_REGULAR;
813 	bucket_compare_func_t cmp;
814 
815 	ZEND_PARSE_PARAMETERS_START(1, 2)
816 		Z_PARAM_ARRAY_EX(array, 0, 1)
817 		Z_PARAM_OPTIONAL
818 		Z_PARAM_LONG(sort_type)
819 	ZEND_PARSE_PARAMETERS_END();
820 
821 	cmp = php_get_data_compare_func(sort_type, 0);
822 
823 	zend_hash_sort(Z_ARRVAL_P(array), cmp, 1);
824 
825 	RETURN_TRUE;
826 }
827 /* }}} */
828 
829 /* {{{ Sort an array in reverse order */
PHP_FUNCTION(rsort)830 PHP_FUNCTION(rsort)
831 {
832 	zval *array;
833 	zend_long sort_type = PHP_SORT_REGULAR;
834 	bucket_compare_func_t cmp;
835 
836 	ZEND_PARSE_PARAMETERS_START(1, 2)
837 		Z_PARAM_ARRAY_EX(array, 0, 1)
838 		Z_PARAM_OPTIONAL
839 		Z_PARAM_LONG(sort_type)
840 	ZEND_PARSE_PARAMETERS_END();
841 
842 	cmp = php_get_data_compare_func(sort_type, 1);
843 
844 	zend_hash_sort(Z_ARRVAL_P(array), cmp, 1);
845 
846 	RETURN_TRUE;
847 }
848 /* }}} */
849 
php_array_user_compare_unstable(Bucket * f,Bucket * s)850 static inline int php_array_user_compare_unstable(Bucket *f, Bucket *s) /* {{{ */
851 {
852 	zval args[2];
853 	zval retval;
854 	bool call_failed;
855 
856 	ZVAL_COPY(&args[0], &f->val);
857 	ZVAL_COPY(&args[1], &s->val);
858 
859 	BG(user_compare_fci).param_count = 2;
860 	BG(user_compare_fci).params = args;
861 	BG(user_compare_fci).retval = &retval;
862 	call_failed = zend_call_function(&BG(user_compare_fci), &BG(user_compare_fci_cache)) == FAILURE || Z_TYPE(retval) == IS_UNDEF;
863 	zval_ptr_dtor(&args[1]);
864 	zval_ptr_dtor(&args[0]);
865 	if (UNEXPECTED(call_failed)) {
866 		return 0;
867 	}
868 
869 	if (UNEXPECTED(Z_TYPE(retval) == IS_FALSE || Z_TYPE(retval) == IS_TRUE)) {
870 		if (!ARRAYG(compare_deprecation_thrown)) {
871 			php_error_docref(NULL, E_DEPRECATED,
872 				"Returning bool from comparison function is deprecated, "
873 				"return an integer less than, equal to, or greater than zero");
874 			ARRAYG(compare_deprecation_thrown) = 1;
875 		}
876 
877 		if (Z_TYPE(retval) == IS_FALSE) {
878 			/* Retry with swapped operands. */
879 			ZVAL_COPY(&args[0], &s->val);
880 			ZVAL_COPY(&args[1], &f->val);
881 			call_failed = zend_call_function(&BG(user_compare_fci), &BG(user_compare_fci_cache)) == FAILURE || Z_TYPE(retval) == IS_UNDEF;
882 			zval_ptr_dtor(&args[1]);
883 			zval_ptr_dtor(&args[0]);
884 			if (call_failed) {
885 				return 0;
886 			}
887 
888 			zend_long ret = zval_get_long(&retval);
889 			zval_ptr_dtor(&retval);
890 			return -ZEND_NORMALIZE_BOOL(ret);
891 		}
892 	}
893 
894 	zend_long ret = zval_get_long(&retval);
895 	zval_ptr_dtor(&retval);
896 	return ZEND_NORMALIZE_BOOL(ret);
897 }
898 /* }}} */
899 
php_array_user_compare(Bucket * a,Bucket * b)900 static int php_array_user_compare(Bucket *a, Bucket *b) /* {{{ */
901 {
902 	RETURN_STABLE_SORT(a, b, php_array_user_compare_unstable(a, b));
903 }
904 /* }}} */
905 
906 #define PHP_ARRAY_CMP_FUNC_VARS \
907 	zend_fcall_info old_user_compare_fci; \
908 	zend_fcall_info_cache old_user_compare_fci_cache \
909 
910 #define PHP_ARRAY_CMP_FUNC_BACKUP() \
911 	old_user_compare_fci = BG(user_compare_fci); \
912 	old_user_compare_fci_cache = BG(user_compare_fci_cache); \
913 	ARRAYG(compare_deprecation_thrown) = 0; \
914 	BG(user_compare_fci_cache) = empty_fcall_info_cache; \
915 
916 #define PHP_ARRAY_CMP_FUNC_RESTORE() \
917 	BG(user_compare_fci) = old_user_compare_fci; \
918 	BG(user_compare_fci_cache) = old_user_compare_fci_cache; \
919 
php_usort(INTERNAL_FUNCTION_PARAMETERS,bucket_compare_func_t compare_func,bool renumber)920 static void php_usort(INTERNAL_FUNCTION_PARAMETERS, bucket_compare_func_t compare_func, bool renumber) /* {{{ */
921 {
922 	zval *array;
923 	zend_array *arr;
924 	PHP_ARRAY_CMP_FUNC_VARS;
925 
926 	PHP_ARRAY_CMP_FUNC_BACKUP();
927 
928 	ZEND_PARSE_PARAMETERS_START(2, 2)
929 		Z_PARAM_ARRAY_EX2(array, 0, 1, 0)
930 		Z_PARAM_FUNC(BG(user_compare_fci), BG(user_compare_fci_cache))
931 	ZEND_PARSE_PARAMETERS_END_EX( PHP_ARRAY_CMP_FUNC_RESTORE(); return );
932 
933 	arr = Z_ARR_P(array);
934 	if (zend_hash_num_elements(arr) == 0)  {
935 		PHP_ARRAY_CMP_FUNC_RESTORE();
936 		RETURN_TRUE;
937 	}
938 
939 	/* Copy array, so the in-place modifications will not be visible to the callback function */
940 	arr = zend_array_dup(arr);
941 
942 	zend_hash_sort(arr, compare_func, renumber);
943 
944 	zval garbage;
945 	ZVAL_COPY_VALUE(&garbage, array);
946 	ZVAL_ARR(array, arr);
947 	zval_ptr_dtor(&garbage);
948 
949 	PHP_ARRAY_CMP_FUNC_RESTORE();
950 	RETURN_TRUE;
951 }
952 /* }}} */
953 
954 /* {{{ Sort an array by values using a user-defined comparison function */
PHP_FUNCTION(usort)955 PHP_FUNCTION(usort)
956 {
957 	php_usort(INTERNAL_FUNCTION_PARAM_PASSTHRU, php_array_user_compare, 1);
958 }
959 /* }}} */
960 
961 /* {{{ Sort an array with a user-defined comparison function and maintain index association */
PHP_FUNCTION(uasort)962 PHP_FUNCTION(uasort)
963 {
964 	php_usort(INTERNAL_FUNCTION_PARAM_PASSTHRU, php_array_user_compare, 0);
965 }
966 /* }}} */
967 
php_array_user_key_compare_unstable(Bucket * f,Bucket * s)968 static inline int php_array_user_key_compare_unstable(Bucket *f, Bucket *s) /* {{{ */
969 {
970 	zval args[2];
971 	zval retval;
972 	bool call_failed;
973 
974 	if (f->key == NULL) {
975 		ZVAL_LONG(&args[0], f->h);
976 	} else {
977 		ZVAL_STR_COPY(&args[0], f->key);
978 	}
979 	if (s->key == NULL) {
980 		ZVAL_LONG(&args[1], s->h);
981 	} else {
982 		ZVAL_STR_COPY(&args[1], s->key);
983 	}
984 
985 	BG(user_compare_fci).param_count = 2;
986 	BG(user_compare_fci).params = args;
987 	BG(user_compare_fci).retval = &retval;
988 	call_failed = zend_call_function(&BG(user_compare_fci), &BG(user_compare_fci_cache)) == FAILURE || Z_TYPE(retval) == IS_UNDEF;
989 	zval_ptr_dtor(&args[1]);
990 	zval_ptr_dtor(&args[0]);
991 	if (UNEXPECTED(call_failed)) {
992 		return 0;
993 	}
994 
995 	if (UNEXPECTED(Z_TYPE(retval) == IS_FALSE || Z_TYPE(retval) == IS_TRUE)) {
996 		if (!ARRAYG(compare_deprecation_thrown)) {
997 			php_error_docref(NULL, E_DEPRECATED,
998 				"Returning bool from comparison function is deprecated, "
999 				"return an integer less than, equal to, or greater than zero");
1000 			ARRAYG(compare_deprecation_thrown) = 1;
1001 		}
1002 
1003 		if (Z_TYPE(retval) == IS_FALSE) {
1004 			/* Retry with swapped operands. */
1005 			if (s->key == NULL) {
1006 				ZVAL_LONG(&args[0], s->h);
1007 			} else {
1008 				ZVAL_STR_COPY(&args[0], s->key);
1009 			}
1010 			if (f->key == NULL) {
1011 				ZVAL_LONG(&args[1], f->h);
1012 			} else {
1013 				ZVAL_STR_COPY(&args[1], f->key);
1014 			}
1015 
1016 			call_failed = zend_call_function(&BG(user_compare_fci), &BG(user_compare_fci_cache)) == FAILURE || Z_TYPE(retval) == IS_UNDEF;
1017 			zval_ptr_dtor(&args[1]);
1018 			zval_ptr_dtor(&args[0]);
1019 			if (call_failed) {
1020 				return 0;
1021 			}
1022 
1023 			zend_long ret = zval_get_long(&retval);
1024 			zval_ptr_dtor(&retval);
1025 			return -ZEND_NORMALIZE_BOOL(ret);
1026 		}
1027 	}
1028 
1029 	zend_long result = zval_get_long(&retval);
1030 	zval_ptr_dtor(&retval);
1031 	return ZEND_NORMALIZE_BOOL(result);
1032 }
1033 /* }}} */
1034 
php_array_user_key_compare(Bucket * a,Bucket * b)1035 static int php_array_user_key_compare(Bucket *a, Bucket *b) /* {{{ */
1036 {
1037 	RETURN_STABLE_SORT(a, b, php_array_user_key_compare_unstable(a, b));
1038 }
1039 /* }}} */
1040 
1041 /* {{{ Sort an array by keys using a user-defined comparison function */
PHP_FUNCTION(uksort)1042 PHP_FUNCTION(uksort)
1043 {
1044 	php_usort(INTERNAL_FUNCTION_PARAM_PASSTHRU, php_array_user_key_compare, 0);
1045 }
1046 /* }}} */
1047 
get_ht_for_iap(zval * zv,bool separate)1048 static inline HashTable *get_ht_for_iap(zval *zv, bool separate) {
1049 	if (EXPECTED(Z_TYPE_P(zv) == IS_ARRAY)) {
1050 		return Z_ARRVAL_P(zv);
1051 	}
1052 
1053 	ZEND_ASSERT(Z_TYPE_P(zv) == IS_OBJECT);
1054 	php_error_docref(NULL, E_DEPRECATED,
1055 		"Calling %s() on an object is deprecated", get_active_function_name());
1056 
1057 	zend_object *zobj = Z_OBJ_P(zv);
1058 	if (separate && zobj->properties && UNEXPECTED(GC_REFCOUNT(zobj->properties) > 1)) {
1059 		if (EXPECTED(!(GC_FLAGS(zobj->properties) & IS_ARRAY_IMMUTABLE))) {
1060 			GC_DELREF(zobj->properties);
1061 		}
1062 		zobj->properties = zend_array_dup(zobj->properties);
1063 	}
1064 	return zobj->handlers->get_properties(zobj);
1065 }
1066 
1067 /* {{{ Advances array argument's internal pointer to the last element and return it */
PHP_FUNCTION(end)1068 PHP_FUNCTION(end)
1069 {
1070 	zval *array_zv;
1071 	zval *entry;
1072 
1073 	ZEND_PARSE_PARAMETERS_START(1, 1)
1074 		Z_PARAM_ARRAY_OR_OBJECT_EX(array_zv, 0, 1)
1075 	ZEND_PARSE_PARAMETERS_END();
1076 
1077 	HashTable *array = get_ht_for_iap(array_zv, /* separate */ true);
1078 	zend_hash_internal_pointer_end(array);
1079 
1080 	if (USED_RET()) {
1081 		if ((entry = zend_hash_get_current_data(array)) == NULL) {
1082 			RETURN_FALSE;
1083 		}
1084 
1085 		if (Z_TYPE_P(entry) == IS_INDIRECT) {
1086 			entry = Z_INDIRECT_P(entry);
1087 		}
1088 
1089 		RETURN_COPY_DEREF(entry);
1090 	}
1091 }
1092 /* }}} */
1093 
1094 /* {{{ Move array argument's internal pointer to the previous element and return it */
PHP_FUNCTION(prev)1095 PHP_FUNCTION(prev)
1096 {
1097 	zval *array_zv;
1098 	zval *entry;
1099 
1100 	ZEND_PARSE_PARAMETERS_START(1, 1)
1101 		Z_PARAM_ARRAY_OR_OBJECT_EX(array_zv, 0, 1)
1102 	ZEND_PARSE_PARAMETERS_END();
1103 
1104 	HashTable *array = get_ht_for_iap(array_zv, /* separate */ true);
1105 	zend_hash_move_backwards(array);
1106 
1107 	if (USED_RET()) {
1108 		if ((entry = zend_hash_get_current_data(array)) == NULL) {
1109 			RETURN_FALSE;
1110 		}
1111 
1112 		if (Z_TYPE_P(entry) == IS_INDIRECT) {
1113 			entry = Z_INDIRECT_P(entry);
1114 		}
1115 
1116 		RETURN_COPY_DEREF(entry);
1117 	}
1118 }
1119 /* }}} */
1120 
1121 /* {{{ Move array argument's internal pointer to the next element and return it */
PHP_FUNCTION(next)1122 PHP_FUNCTION(next)
1123 {
1124 	zval *array_zv;
1125 	zval *entry;
1126 
1127 	ZEND_PARSE_PARAMETERS_START(1, 1)
1128 		Z_PARAM_ARRAY_OR_OBJECT_EX(array_zv, 0, 1)
1129 	ZEND_PARSE_PARAMETERS_END();
1130 
1131 	HashTable *array = get_ht_for_iap(array_zv, /* separate */ true);
1132 	zend_hash_move_forward(array);
1133 
1134 	if (USED_RET()) {
1135 		if ((entry = zend_hash_get_current_data(array)) == NULL) {
1136 			RETURN_FALSE;
1137 		}
1138 
1139 		if (Z_TYPE_P(entry) == IS_INDIRECT) {
1140 			entry = Z_INDIRECT_P(entry);
1141 		}
1142 
1143 		RETURN_COPY_DEREF(entry);
1144 	}
1145 }
1146 /* }}} */
1147 
1148 /* {{{ Set array argument's internal pointer to the first element and return it */
PHP_FUNCTION(reset)1149 PHP_FUNCTION(reset)
1150 {
1151 	zval *array_zv;
1152 	zval *entry;
1153 
1154 	ZEND_PARSE_PARAMETERS_START(1, 1)
1155 		Z_PARAM_ARRAY_OR_OBJECT_EX(array_zv, 0, 1)
1156 	ZEND_PARSE_PARAMETERS_END();
1157 
1158 	HashTable *array = get_ht_for_iap(array_zv, /* separate */ true);
1159 	zend_hash_internal_pointer_reset(array);
1160 
1161 	if (USED_RET()) {
1162 		if ((entry = zend_hash_get_current_data(array)) == NULL) {
1163 			RETURN_FALSE;
1164 		}
1165 
1166 		if (Z_TYPE_P(entry) == IS_INDIRECT) {
1167 			entry = Z_INDIRECT_P(entry);
1168 		}
1169 
1170 		RETURN_COPY_DEREF(entry);
1171 	}
1172 }
1173 /* }}} */
1174 
1175 /* {{{ Return the element currently pointed to by the internal array pointer */
PHP_FUNCTION(current)1176 PHP_FUNCTION(current)
1177 {
1178 	zval *array_zv;
1179 	zval *entry;
1180 
1181 	ZEND_PARSE_PARAMETERS_START(1, 1)
1182 		Z_PARAM_ARRAY_OR_OBJECT(array_zv)
1183 	ZEND_PARSE_PARAMETERS_END();
1184 
1185 	HashTable *array = get_ht_for_iap(array_zv, /* separate */ false);
1186 	if ((entry = zend_hash_get_current_data(array)) == NULL) {
1187 		RETURN_FALSE;
1188 	}
1189 
1190 	if (Z_TYPE_P(entry) == IS_INDIRECT) {
1191 		entry = Z_INDIRECT_P(entry);
1192 	}
1193 
1194 	RETURN_COPY_DEREF(entry);
1195 }
1196 /* }}} */
1197 
1198 /* {{{ Return the key of the element currently pointed to by the internal array pointer */
PHP_FUNCTION(key)1199 PHP_FUNCTION(key)
1200 {
1201 	zval *array_zv;
1202 
1203 	ZEND_PARSE_PARAMETERS_START(1, 1)
1204 		Z_PARAM_ARRAY_OR_OBJECT(array_zv)
1205 	ZEND_PARSE_PARAMETERS_END();
1206 
1207 	HashTable *array = get_ht_for_iap(array_zv, /* separate */ false);
1208 	zend_hash_get_current_key_zval(array, return_value);
1209 }
1210 /* }}} */
1211 
php_data_compare(const void * f,const void * s)1212 static int php_data_compare(const void *f, const void *s) /* {{{ */
1213 {
1214 	return zend_compare((zval*)f, (zval*)s);
1215 }
1216 /* }}} */
1217 
1218 /* {{{
1219  * proto mixed min(array values)
1220  * proto mixed min(mixed arg1 [, mixed arg2 [, mixed ...]])
1221    Return the lowest value in an array or a series of arguments */
PHP_FUNCTION(min)1222 PHP_FUNCTION(min)
1223 {
1224 	int argc;
1225 	zval *args = NULL;
1226 
1227 	ZEND_PARSE_PARAMETERS_START(1, -1)
1228 		Z_PARAM_VARIADIC('+', args, argc)
1229 	ZEND_PARSE_PARAMETERS_END();
1230 
1231 	/* mixed min ( array $values ) */
1232 	if (argc == 1) {
1233 		if (Z_TYPE(args[0]) != IS_ARRAY) {
1234 			zend_argument_type_error(1, "must be of type array, %s given", zend_zval_type_name(&args[0]));
1235 			RETURN_THROWS();
1236 		} else {
1237 			zval *result = zend_hash_minmax(Z_ARRVAL(args[0]), php_data_compare, 0);
1238 			if (result) {
1239 				RETURN_COPY_DEREF(result);
1240 			} else {
1241 				zend_argument_value_error(1, "must contain at least one element");
1242 				RETURN_THROWS();
1243 			}
1244 		}
1245 	} else {
1246 		/* mixed min ( mixed $value1 , mixed $value2 [, mixed $value3... ] ) */
1247 		zval *min, result;
1248 		int i;
1249 
1250 		min = &args[0];
1251 
1252 		for (i = 1; i < argc; i++) {
1253 			is_smaller_function(&result, &args[i], min);
1254 			if (Z_TYPE(result) == IS_TRUE) {
1255 				min = &args[i];
1256 			}
1257 		}
1258 
1259 		RETURN_COPY(min);
1260 	}
1261 }
1262 /* }}} */
1263 
1264 /* {{{
1265  * proto mixed max(array values)
1266  * proto mixed max(mixed arg1 [, mixed arg2 [, mixed ...]])
1267    Return the highest value in an array or a series of arguments */
PHP_FUNCTION(max)1268 PHP_FUNCTION(max)
1269 {
1270 	zval *args = NULL;
1271 	int argc;
1272 
1273 	ZEND_PARSE_PARAMETERS_START(1, -1)
1274 		Z_PARAM_VARIADIC('+', args, argc)
1275 	ZEND_PARSE_PARAMETERS_END();
1276 
1277 	/* mixed max ( array $values ) */
1278 	if (argc == 1) {
1279 		if (Z_TYPE(args[0]) != IS_ARRAY) {
1280 			zend_argument_type_error(1, "must be of type array, %s given", zend_zval_type_name(&args[0]));
1281 			RETURN_THROWS();
1282 		} else {
1283 			zval *result = zend_hash_minmax(Z_ARRVAL(args[0]), php_data_compare, 1);
1284 			if (result) {
1285 				RETURN_COPY_DEREF(result);
1286 			} else {
1287 				zend_argument_value_error(1, "must contain at least one element");
1288 				RETURN_THROWS();
1289 			}
1290 		}
1291 	} else {
1292 		/* mixed max ( mixed $value1 , mixed $value2 [, mixed $value3... ] ) */
1293 		zval *max, result;
1294 		int i;
1295 
1296 		max = &args[0];
1297 
1298 		for (i = 1; i < argc; i++) {
1299 			is_smaller_or_equal_function(&result, &args[i], max);
1300 			if (Z_TYPE(result) == IS_FALSE) {
1301 				max = &args[i];
1302 			}
1303 		}
1304 
1305 		RETURN_COPY(max);
1306 	}
1307 }
1308 /* }}} */
1309 
1310 typedef struct {
1311 	zend_fcall_info fci;
1312 	zend_fcall_info_cache fci_cache;
1313 } php_array_walk_context;
1314 
php_array_walk(php_array_walk_context * context,zval * array,zval * userdata,int recursive)1315 static int php_array_walk(
1316 	php_array_walk_context *context, zval *array, zval *userdata, int recursive)
1317 {
1318 	zval args[3],		/* Arguments to userland function */
1319 		 retval,		/* Return value - unused */
1320 		 *zv;
1321 	HashTable *target_hash = HASH_OF(array);
1322 	HashPosition pos;
1323 	uint32_t ht_iter;
1324 	int result = SUCCESS;
1325 
1326 	/* Create a local copy of fci, as we want to use different arguments at different
1327 	 * levels of recursion. */
1328 	zend_fcall_info fci = context->fci;
1329 
1330 	/* Set up known arguments */
1331 	ZVAL_UNDEF(&args[1]);
1332 	if (userdata) {
1333 		ZVAL_COPY(&args[2], userdata);
1334 	}
1335 
1336 	fci.retval = &retval;
1337 	fci.param_count = userdata ? 3 : 2;
1338 	fci.params = args;
1339 
1340 	zend_hash_internal_pointer_reset_ex(target_hash, &pos);
1341 	ht_iter = zend_hash_iterator_add(target_hash, pos);
1342 
1343 	/* Iterate through hash */
1344 	do {
1345 		/* Retrieve value */
1346 		zv = zend_hash_get_current_data_ex(target_hash, &pos);
1347 		if (zv == NULL) {
1348 			break;
1349 		}
1350 
1351 		/* Skip undefined indirect elements */
1352 		if (Z_TYPE_P(zv) == IS_INDIRECT) {
1353 			zv = Z_INDIRECT_P(zv);
1354 			if (Z_TYPE_P(zv) == IS_UNDEF) {
1355 				zend_hash_move_forward_ex(target_hash, &pos);
1356 				continue;
1357 			}
1358 
1359 			/* Add type source for property references. */
1360 			if (Z_TYPE_P(zv) != IS_REFERENCE && Z_TYPE_P(array) == IS_OBJECT) {
1361 				zend_property_info *prop_info =
1362 					zend_get_typed_property_info_for_slot(Z_OBJ_P(array), zv);
1363 				if (prop_info) {
1364 					ZVAL_NEW_REF(zv, zv);
1365 					ZEND_REF_ADD_TYPE_SOURCE(Z_REF_P(zv), prop_info);
1366 				}
1367 			}
1368 		}
1369 
1370 		/* Ensure the value is a reference. Otherwise the location of the value may be freed. */
1371 		ZVAL_MAKE_REF(zv);
1372 
1373 		/* Retrieve key */
1374 		zend_hash_get_current_key_zval_ex(target_hash, &args[1], &pos);
1375 
1376 		/* Move to next element already now -- this mirrors the approach used by foreach
1377 		 * and ensures proper behavior with regard to modifications. */
1378 		zend_hash_move_forward_ex(target_hash, &pos);
1379 
1380 		/* Back up hash position, as it may change */
1381 		EG(ht_iterators)[ht_iter].pos = pos;
1382 
1383 		if (recursive && Z_TYPE_P(Z_REFVAL_P(zv)) == IS_ARRAY) {
1384 			HashTable *thash;
1385 			zval ref;
1386 			ZVAL_COPY_VALUE(&ref, zv);
1387 
1388 			ZVAL_DEREF(zv);
1389 			SEPARATE_ARRAY(zv);
1390 			thash = Z_ARRVAL_P(zv);
1391 			if (GC_IS_RECURSIVE(thash)) {
1392 				zend_throw_error(NULL, "Recursion detected");
1393 				result = FAILURE;
1394 				break;
1395 			}
1396 
1397 			Z_ADDREF(ref);
1398 			GC_PROTECT_RECURSION(thash);
1399 			result = php_array_walk(context, zv, userdata, recursive);
1400 			if (Z_TYPE_P(Z_REFVAL(ref)) == IS_ARRAY && thash == Z_ARRVAL_P(Z_REFVAL(ref))) {
1401 				/* If the hashtable changed in the meantime, we'll "leak" this apply count
1402 				 * increment -- our reference to thash is no longer valid. */
1403 				GC_UNPROTECT_RECURSION(thash);
1404 			}
1405 			zval_ptr_dtor(&ref);
1406 		} else {
1407 			ZVAL_COPY(&args[0], zv);
1408 
1409 			/* Call the userland function */
1410 			result = zend_call_function(&fci, &context->fci_cache);
1411 			if (result == SUCCESS) {
1412 				zval_ptr_dtor(&retval);
1413 			}
1414 
1415 			zval_ptr_dtor(&args[0]);
1416 		}
1417 
1418 		if (Z_TYPE(args[1]) != IS_UNDEF) {
1419 			zval_ptr_dtor(&args[1]);
1420 			ZVAL_UNDEF(&args[1]);
1421 		}
1422 
1423 		if (result == FAILURE) {
1424 			break;
1425 		}
1426 
1427 		/* Reload array and position -- both may have changed */
1428 		if (Z_TYPE_P(array) == IS_ARRAY) {
1429 			pos = zend_hash_iterator_pos_ex(ht_iter, array);
1430 			target_hash = Z_ARRVAL_P(array);
1431 		} else if (Z_TYPE_P(array) == IS_OBJECT) {
1432 			target_hash = Z_OBJPROP_P(array);
1433 			pos = zend_hash_iterator_pos(ht_iter, target_hash);
1434 		} else {
1435 			zend_type_error("Iterated value is no longer an array or object");
1436 			result = FAILURE;
1437 			break;
1438 		}
1439 	} while (!EG(exception));
1440 
1441 	if (userdata) {
1442 		zval_ptr_dtor(&args[2]);
1443 	}
1444 	zend_hash_iterator_del(ht_iter);
1445 	return result;
1446 }
1447 
1448 /* {{{ Apply a user function to every member of an array */
PHP_FUNCTION(array_walk)1449 PHP_FUNCTION(array_walk)
1450 {
1451 	zval *array;
1452 	zval *userdata = NULL;
1453 	php_array_walk_context context;
1454 
1455 	ZEND_PARSE_PARAMETERS_START(2, 3)
1456 		Z_PARAM_ARRAY_OR_OBJECT_EX(array, 0, 1)
1457 		Z_PARAM_FUNC(context.fci, context.fci_cache)
1458 		Z_PARAM_OPTIONAL
1459 		Z_PARAM_ZVAL(userdata)
1460 	ZEND_PARSE_PARAMETERS_END();
1461 
1462 	php_array_walk(&context, array, userdata, 0);
1463 	RETURN_TRUE;
1464 }
1465 /* }}} */
1466 
1467 /* {{{ Apply a user function recursively to every member of an array */
PHP_FUNCTION(array_walk_recursive)1468 PHP_FUNCTION(array_walk_recursive)
1469 {
1470 	zval *array;
1471 	zval *userdata = NULL;
1472 	php_array_walk_context context;
1473 
1474 	ZEND_PARSE_PARAMETERS_START(2, 3)
1475 		Z_PARAM_ARRAY_OR_OBJECT_EX(array, 0, 1)
1476 		Z_PARAM_FUNC(context.fci, context.fci_cache)
1477 		Z_PARAM_OPTIONAL
1478 		Z_PARAM_ZVAL(userdata)
1479 	ZEND_PARSE_PARAMETERS_END();
1480 
1481 	php_array_walk(&context, array, userdata, 1);
1482 	RETURN_TRUE;
1483 }
1484 /* }}} */
1485 
1486 /* void php_search_array(INTERNAL_FUNCTION_PARAMETERS, int behavior)
1487  * 0 = return boolean
1488  * 1 = return key
1489  */
php_search_array(INTERNAL_FUNCTION_PARAMETERS,int behavior)1490 static inline void php_search_array(INTERNAL_FUNCTION_PARAMETERS, int behavior) /* {{{ */
1491 {
1492 	zval *value,				/* value to check for */
1493 		 *array,				/* array to check in */
1494 		 *entry;				/* pointer to array entry */
1495 	zend_ulong num_idx;
1496 	zend_string *str_idx;
1497 	bool strict = 0;		/* strict comparison or not */
1498 
1499 	ZEND_PARSE_PARAMETERS_START(2, 3)
1500 		Z_PARAM_ZVAL(value)
1501 		Z_PARAM_ARRAY(array)
1502 		Z_PARAM_OPTIONAL
1503 		Z_PARAM_BOOL(strict)
1504 	ZEND_PARSE_PARAMETERS_END();
1505 
1506 	if (strict) {
1507 		if (Z_TYPE_P(value) == IS_LONG) {
1508 			ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
1509 				ZVAL_DEREF(entry);
1510 				if (Z_TYPE_P(entry) == IS_LONG && Z_LVAL_P(entry) == Z_LVAL_P(value)) {
1511 					if (behavior == 0) {
1512 						RETURN_TRUE;
1513 					} else {
1514 						if (str_idx) {
1515 							RETURN_STR_COPY(str_idx);
1516 						} else {
1517 							RETURN_LONG(num_idx);
1518 						}
1519 					}
1520 				}
1521 			} ZEND_HASH_FOREACH_END();
1522 		} else {
1523 			ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
1524 				ZVAL_DEREF(entry);
1525 				if (fast_is_identical_function(value, entry)) {
1526 					if (behavior == 0) {
1527 						RETURN_TRUE;
1528 					} else {
1529 						if (str_idx) {
1530 							RETURN_STR_COPY(str_idx);
1531 						} else {
1532 							RETURN_LONG(num_idx);
1533 						}
1534 					}
1535 				}
1536 			} ZEND_HASH_FOREACH_END();
1537 		}
1538 	} else {
1539 		if (Z_TYPE_P(value) == IS_LONG) {
1540 			ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
1541 				if (fast_equal_check_long(value, entry)) {
1542 					if (behavior == 0) {
1543 						RETURN_TRUE;
1544 					} else {
1545 						if (str_idx) {
1546 							RETURN_STR_COPY(str_idx);
1547 						} else {
1548 							RETURN_LONG(num_idx);
1549 						}
1550 					}
1551 				}
1552 			} ZEND_HASH_FOREACH_END();
1553 		} else if (Z_TYPE_P(value) == IS_STRING) {
1554 			ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
1555 				if (fast_equal_check_string(value, entry)) {
1556 					if (behavior == 0) {
1557 						RETURN_TRUE;
1558 					} else {
1559 						if (str_idx) {
1560 							RETURN_STR_COPY(str_idx);
1561 						} else {
1562 							RETURN_LONG(num_idx);
1563 						}
1564 					}
1565 				}
1566 			} ZEND_HASH_FOREACH_END();
1567 		} else {
1568 			ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
1569 				if (fast_equal_check_function(value, entry)) {
1570 					if (behavior == 0) {
1571 						RETURN_TRUE;
1572 					} else {
1573 						if (str_idx) {
1574 							RETURN_STR_COPY(str_idx);
1575 						} else {
1576 							RETURN_LONG(num_idx);
1577 						}
1578 					}
1579 				}
1580 			} ZEND_HASH_FOREACH_END();
1581 		}
1582 	}
1583 
1584 	RETURN_FALSE;
1585 }
1586 /* }}} */
1587 
1588 /* {{{ Checks if the given value exists in the array */
PHP_FUNCTION(in_array)1589 PHP_FUNCTION(in_array)
1590 {
1591 	php_search_array(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0);
1592 }
1593 /* }}} */
1594 
1595 /* {{{ Searches the array for a given value and returns the corresponding key if successful */
PHP_FUNCTION(array_search)1596 PHP_FUNCTION(array_search)
1597 {
1598 	php_search_array(INTERNAL_FUNCTION_PARAM_PASSTHRU, 1);
1599 }
1600 /* }}} */
1601 
php_valid_var_name(const char * var_name,size_t var_name_len)1602 static zend_always_inline int php_valid_var_name(const char *var_name, size_t var_name_len) /* {{{ */
1603 {
1604 #if 1
1605 	/* first 256 bits for first character, and second 256 bits for the next */
1606 	static const uint32_t charset[8] = {
1607 	     /*  31      0   63     32   95     64   127    96 */
1608 			0x00000000, 0x00000000, 0x87fffffe, 0x07fffffe,
1609 			0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff};
1610 	static const uint32_t charset2[8] = {
1611 	     /*  31      0   63     32   95     64   127    96 */
1612 			0x00000000, 0x03ff0000, 0x87fffffe, 0x07fffffe,
1613 			0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff};
1614 #endif
1615 	size_t i;
1616 	uint32_t ch;
1617 
1618 	if (UNEXPECTED(!var_name_len)) {
1619 		return 0;
1620 	}
1621 
1622 	/* These are allowed as first char: [a-zA-Z_\x7f-\xff] */
1623 	ch = (uint32_t)((unsigned char *)var_name)[0];
1624 #if 1
1625 	if (UNEXPECTED(!ZEND_BIT_TEST(charset, ch))) {
1626 #else
1627 	if (var_name[0] != '_' &&
1628 		(ch < 65  /* A    */ || /* Z    */ ch > 90)  &&
1629 		(ch < 97  /* a    */ || /* z    */ ch > 122) &&
1630 		(ch < 127 /* 0x7f */ || /* 0xff */ ch > 255)
1631 	) {
1632 #endif
1633 		return 0;
1634 	}
1635 
1636 	/* And these as the rest: [a-zA-Z0-9_\x7f-\xff] */
1637 	if (var_name_len > 1) {
1638 		i = 1;
1639 		do {
1640 			ch = (uint32_t)((unsigned char *)var_name)[i];
1641 #if 1
1642 			if (UNEXPECTED(!ZEND_BIT_TEST(charset2, ch))) {
1643 #else
1644 			if (var_name[i] != '_' &&
1645 				(ch < 48  /* 0    */ || /* 9    */ ch > 57)  &&
1646 				(ch < 65  /* A    */ || /* Z    */ ch > 90)  &&
1647 				(ch < 97  /* a    */ || /* z    */ ch > 122) &&
1648 				(ch < 127 /* 0x7f */ || /* 0xff */ ch > 255)
1649 			) {
1650 #endif
1651 				return 0;
1652 			}
1653 		} while (++i < var_name_len);
1654 	}
1655 	return 1;
1656 }
1657 /* }}} */
1658 
1659 PHPAPI int php_prefix_varname(zval *result, zend_string *prefix, const char *var_name, size_t var_name_len, bool add_underscore) /* {{{ */
1660 {
1661 	ZVAL_NEW_STR(result, zend_string_alloc(ZSTR_LEN(prefix) + (add_underscore ? 1 : 0) + var_name_len, 0));
1662 	memcpy(Z_STRVAL_P(result), ZSTR_VAL(prefix), ZSTR_LEN(prefix));
1663 
1664 	if (add_underscore) {
1665 		Z_STRVAL_P(result)[ZSTR_LEN(prefix)] = '_';
1666 	}
1667 
1668 	memcpy(Z_STRVAL_P(result) + ZSTR_LEN(prefix) + (add_underscore ? 1 : 0), var_name, var_name_len + 1);
1669 
1670 	return SUCCESS;
1671 }
1672 /* }}} */
1673 
1674 static zend_long php_extract_ref_if_exists(zend_array *arr, zend_array *symbol_table) /* {{{ */
1675 {
1676 	zend_long count = 0;
1677 	zend_string *var_name;
1678 	zval *entry, *orig_var;
1679 
1680 	if (HT_IS_PACKED(arr)) {
1681 		return 0;
1682 	}
1683 	ZEND_HASH_MAP_FOREACH_STR_KEY_VAL(arr, var_name, entry) {
1684 		if (!var_name) {
1685 			continue;
1686 		}
1687 		orig_var = zend_hash_find_known_hash(symbol_table, var_name);
1688 		if (orig_var) {
1689 			if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1690 				orig_var = Z_INDIRECT_P(orig_var);
1691 				if (Z_TYPE_P(orig_var) == IS_UNDEF) {
1692 					continue;
1693 				}
1694 			}
1695 			if (!php_valid_var_name(ZSTR_VAL(var_name), ZSTR_LEN(var_name))) {
1696 				continue;
1697 			}
1698 			if (zend_string_equals_literal(var_name, "GLOBALS")) {
1699 				continue;
1700 			}
1701 			if (zend_string_equals_literal(var_name, "this")) {
1702 				zend_throw_error(NULL, "Cannot re-assign $this");
1703 				return -1;
1704 			}
1705 			if (Z_ISREF_P(entry)) {
1706 				Z_ADDREF_P(entry);
1707 			} else {
1708 				ZVAL_MAKE_REF_EX(entry, 2);
1709 			}
1710 			zval_ptr_dtor(orig_var);
1711 			ZVAL_REF(orig_var, Z_REF_P(entry));
1712 			count++;
1713 		}
1714 	} ZEND_HASH_FOREACH_END();
1715 
1716 	return count;
1717 }
1718 /* }}} */
1719 
1720 static zend_long php_extract_if_exists(zend_array *arr, zend_array *symbol_table) /* {{{ */
1721 {
1722 	zend_long count = 0;
1723 	zend_string *var_name;
1724 	zval *entry, *orig_var;
1725 
1726 	if (HT_IS_PACKED(arr)) {
1727 		return 0;
1728 	}
1729 	ZEND_HASH_MAP_FOREACH_STR_KEY_VAL(arr, var_name, entry) {
1730 		if (!var_name) {
1731 			continue;
1732 		}
1733 		orig_var = zend_hash_find_known_hash(symbol_table, var_name);
1734 		if (orig_var) {
1735 			if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1736 				orig_var = Z_INDIRECT_P(orig_var);
1737 				if (Z_TYPE_P(orig_var) == IS_UNDEF) {
1738 					continue;
1739 				}
1740 			}
1741 			if (!php_valid_var_name(ZSTR_VAL(var_name), ZSTR_LEN(var_name))) {
1742 				continue;
1743 			}
1744 			if (zend_string_equals_literal(var_name, "GLOBALS")) {
1745 				continue;
1746 			}
1747 			if (zend_string_equals_literal(var_name, "this")) {
1748 				zend_throw_error(NULL, "Cannot re-assign $this");
1749 				return -1;
1750 			}
1751 			ZVAL_DEREF(entry);
1752 			ZEND_TRY_ASSIGN_COPY_EX(orig_var, entry, 0);
1753 			if (UNEXPECTED(EG(exception))) {
1754 				return -1;
1755 			}
1756 			count++;
1757 		}
1758 	} ZEND_HASH_FOREACH_END();
1759 
1760 	return count;
1761 }
1762 /* }}} */
1763 
1764 static zend_long php_extract_ref_overwrite(zend_array *arr, zend_array *symbol_table) /* {{{ */
1765 {
1766 	zend_long count = 0;
1767 	zend_string *var_name;
1768 	zval *entry, *orig_var;
1769 
1770 	if (HT_IS_PACKED(arr)) {
1771 		return 0;
1772 	}
1773 	ZEND_HASH_MAP_FOREACH_STR_KEY_VAL(arr, var_name, entry) {
1774 		if (!var_name) {
1775 			continue;
1776 		}
1777 		if (!php_valid_var_name(ZSTR_VAL(var_name), ZSTR_LEN(var_name))) {
1778 			continue;
1779 		}
1780 		if (zend_string_equals_literal(var_name, "this")) {
1781 			zend_throw_error(NULL, "Cannot re-assign $this");
1782 			return -1;
1783 		}
1784 		orig_var = zend_hash_find_known_hash(symbol_table, var_name);
1785 		if (orig_var) {
1786 			if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1787 				orig_var = Z_INDIRECT_P(orig_var);
1788 			}
1789 			if (zend_string_equals_literal(var_name, "GLOBALS")) {
1790 				continue;
1791 			}
1792 			if (Z_ISREF_P(entry)) {
1793 				Z_ADDREF_P(entry);
1794 			} else {
1795 				ZVAL_MAKE_REF_EX(entry, 2);
1796 			}
1797 			zval_ptr_dtor(orig_var);
1798 			ZVAL_REF(orig_var, Z_REF_P(entry));
1799 		} else {
1800 			if (Z_ISREF_P(entry)) {
1801 				Z_ADDREF_P(entry);
1802 			} else {
1803 				ZVAL_MAKE_REF_EX(entry, 2);
1804 			}
1805 			zend_hash_add_new(symbol_table, var_name, entry);
1806 		}
1807 		count++;
1808 	} ZEND_HASH_FOREACH_END();
1809 
1810 	return count;
1811 }
1812 /* }}} */
1813 
1814 static zend_long php_extract_overwrite(zend_array *arr, zend_array *symbol_table) /* {{{ */
1815 {
1816 	zend_long count = 0;
1817 	zend_string *var_name;
1818 	zval *entry, *orig_var;
1819 
1820 	if (HT_IS_PACKED(arr)) {
1821 		return 0;
1822 	}
1823 	ZEND_HASH_MAP_FOREACH_STR_KEY_VAL(arr, var_name, entry) {
1824 		if (!var_name) {
1825 			continue;
1826 		}
1827 		if (!php_valid_var_name(ZSTR_VAL(var_name), ZSTR_LEN(var_name))) {
1828 			continue;
1829 		}
1830 		if (zend_string_equals_literal(var_name, "this")) {
1831 			zend_throw_error(NULL, "Cannot re-assign $this");
1832 			return -1;
1833 		}
1834 		orig_var = zend_hash_find_known_hash(symbol_table, var_name);
1835 		if (orig_var) {
1836 			if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1837 				orig_var = Z_INDIRECT_P(orig_var);
1838 			}
1839 			if (zend_string_equals_literal(var_name, "GLOBALS")) {
1840 				continue;
1841 			}
1842 			ZVAL_DEREF(entry);
1843 			ZEND_TRY_ASSIGN_COPY_EX(orig_var, entry, 0);
1844 			if (UNEXPECTED(EG(exception))) {
1845 				return -1;
1846 			}
1847 		} else {
1848 			ZVAL_DEREF(entry);
1849 			Z_TRY_ADDREF_P(entry);
1850 			zend_hash_add_new(symbol_table, var_name, entry);
1851 		}
1852 		count++;
1853 	} ZEND_HASH_FOREACH_END();
1854 
1855 	return count;
1856 }
1857 /* }}} */
1858 
1859 static zend_long php_extract_ref_prefix_if_exists(zend_array *arr, zend_array *symbol_table, zend_string *prefix) /* {{{ */
1860 {
1861 	zend_long count = 0;
1862 	zend_string *var_name;
1863 	zval *entry, *orig_var, final_name;
1864 
1865 	if (HT_IS_PACKED(arr)) {
1866 		return 0;
1867 	}
1868 	ZEND_HASH_MAP_FOREACH_STR_KEY_VAL(arr, var_name, entry) {
1869 		if (!var_name) {
1870 			continue;
1871 		}
1872 		orig_var = zend_hash_find_known_hash(symbol_table, var_name);
1873 		if (orig_var) {
1874 			if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1875 				orig_var = Z_INDIRECT_P(orig_var);
1876 				if (Z_TYPE_P(orig_var) == IS_UNDEF) {
1877 					if (Z_ISREF_P(entry)) {
1878 						Z_ADDREF_P(entry);
1879 					} else {
1880 						ZVAL_MAKE_REF_EX(entry, 2);
1881 					}
1882 					ZVAL_REF(orig_var, Z_REF_P(entry));
1883 					count++;
1884 					continue;
1885 				}
1886 			}
1887 			php_prefix_varname(&final_name, prefix, ZSTR_VAL(var_name), ZSTR_LEN(var_name), 1);
1888 			if (php_valid_var_name(Z_STRVAL(final_name), Z_STRLEN(final_name))) {
1889 				if (zend_string_equals_literal(Z_STR(final_name), "this")) {
1890 					zend_throw_error(NULL, "Cannot re-assign $this");
1891 					return -1;
1892 				} else {
1893 					if (Z_ISREF_P(entry)) {
1894 						Z_ADDREF_P(entry);
1895 					} else {
1896 						ZVAL_MAKE_REF_EX(entry, 2);
1897 					}
1898 					if ((orig_var = zend_hash_find(symbol_table, Z_STR(final_name))) != NULL) {
1899 						if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1900 							orig_var = Z_INDIRECT_P(orig_var);
1901 						}
1902 						zval_ptr_dtor(orig_var);
1903 						ZVAL_REF(orig_var, Z_REF_P(entry));
1904 					} else {
1905 						zend_hash_add_new(symbol_table, Z_STR(final_name), entry);
1906 					}
1907 					count++;
1908 				}
1909 			}
1910 			zval_ptr_dtor_str(&final_name);
1911 		}
1912 	} ZEND_HASH_FOREACH_END();
1913 
1914 	return count;
1915 }
1916 /* }}} */
1917 
1918 static zend_long php_extract_prefix_if_exists(zend_array *arr, zend_array *symbol_table, zend_string *prefix) /* {{{ */
1919 {
1920 	zend_long count = 0;
1921 	zend_string *var_name;
1922 	zval *entry, *orig_var, final_name;
1923 
1924 	if (HT_IS_PACKED(arr)) {
1925 		return 0;
1926 	}
1927 	ZEND_HASH_MAP_FOREACH_STR_KEY_VAL(arr, var_name, entry) {
1928 		if (!var_name) {
1929 			continue;
1930 		}
1931 		orig_var = zend_hash_find_known_hash(symbol_table, var_name);
1932 		if (orig_var) {
1933 			if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1934 				orig_var = Z_INDIRECT_P(orig_var);
1935 				if (Z_TYPE_P(orig_var) == IS_UNDEF) {
1936 					ZVAL_COPY_DEREF(orig_var, entry);
1937 					count++;
1938 					continue;
1939 				}
1940 			}
1941 			php_prefix_varname(&final_name, prefix, ZSTR_VAL(var_name), ZSTR_LEN(var_name), 1);
1942 			if (php_valid_var_name(Z_STRVAL(final_name), Z_STRLEN(final_name))) {
1943 				if (zend_string_equals_literal(Z_STR(final_name), "this")) {
1944 					zend_throw_error(NULL, "Cannot re-assign $this");
1945 					return -1;
1946 				} else {
1947 					ZVAL_DEREF(entry);
1948 					if ((orig_var = zend_hash_find(symbol_table, Z_STR(final_name))) != NULL) {
1949 						if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1950 							orig_var = Z_INDIRECT_P(orig_var);
1951 						}
1952 						ZEND_TRY_ASSIGN_COPY_EX(orig_var, entry, 0);
1953 						if (UNEXPECTED(EG(exception))) {
1954 							zend_string_release_ex(Z_STR(final_name), 0);
1955 							return -1;
1956 						}
1957 					} else {
1958 						Z_TRY_ADDREF_P(entry);
1959 						zend_hash_add_new(symbol_table, Z_STR(final_name), entry);
1960 					}
1961 					count++;
1962 				}
1963 			}
1964 			zval_ptr_dtor_str(&final_name);
1965 		}
1966 	} ZEND_HASH_FOREACH_END();
1967 
1968 	return count;
1969 }
1970 /* }}} */
1971 
1972 static zend_long php_extract_ref_prefix_same(zend_array *arr, zend_array *symbol_table, zend_string *prefix) /* {{{ */
1973 {
1974 	zend_long count = 0;
1975 	zend_string *var_name;
1976 	zval *entry, *orig_var, final_name;
1977 
1978 	if (HT_IS_PACKED(arr)) {
1979 		return 0;
1980 	}
1981 	ZEND_HASH_MAP_FOREACH_STR_KEY_VAL(arr, var_name, entry) {
1982 		if (!var_name) {
1983 			continue;
1984 		}
1985 		if (ZSTR_LEN(var_name) == 0) {
1986 			continue;
1987 		}
1988 		orig_var = zend_hash_find_known_hash(symbol_table, var_name);
1989 		if (orig_var) {
1990 			if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1991 				orig_var = Z_INDIRECT_P(orig_var);
1992 				if (Z_TYPE_P(orig_var) == IS_UNDEF) {
1993 					if (Z_ISREF_P(entry)) {
1994 						Z_ADDREF_P(entry);
1995 					} else {
1996 						ZVAL_MAKE_REF_EX(entry, 2);
1997 					}
1998 					ZVAL_REF(orig_var, Z_REF_P(entry));
1999 					count++;
2000 					continue;
2001 				}
2002 			}
2003 prefix:
2004 			php_prefix_varname(&final_name, prefix, ZSTR_VAL(var_name), ZSTR_LEN(var_name), 1);
2005 			if (php_valid_var_name(Z_STRVAL(final_name), Z_STRLEN(final_name))) {
2006 				if (zend_string_equals_literal(Z_STR(final_name), "this")) {
2007 					zend_throw_error(NULL, "Cannot re-assign $this");
2008 					return -1;
2009 				} else {
2010 					if (Z_ISREF_P(entry)) {
2011 						Z_ADDREF_P(entry);
2012 					} else {
2013 						ZVAL_MAKE_REF_EX(entry, 2);
2014 					}
2015 					if ((orig_var = zend_hash_find(symbol_table, Z_STR(final_name))) != NULL) {
2016 						if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
2017 							orig_var = Z_INDIRECT_P(orig_var);
2018 						}
2019 						zval_ptr_dtor(orig_var);
2020 						ZVAL_REF(orig_var, Z_REF_P(entry));
2021 					} else {
2022 						zend_hash_add_new(symbol_table, Z_STR(final_name), entry);
2023 					}
2024 					count++;
2025 				}
2026 			}
2027 			zval_ptr_dtor_str(&final_name);
2028 		} else {
2029 			if (!php_valid_var_name(ZSTR_VAL(var_name), ZSTR_LEN(var_name))) {
2030 				continue;
2031 			}
2032 			if (zend_string_equals_literal(var_name, "this")) {
2033 				goto prefix;
2034 			}
2035 			if (Z_ISREF_P(entry)) {
2036 				Z_ADDREF_P(entry);
2037 			} else {
2038 				ZVAL_MAKE_REF_EX(entry, 2);
2039 			}
2040 			zend_hash_add_new(symbol_table, var_name, entry);
2041 			count++;
2042 		}
2043 	} ZEND_HASH_FOREACH_END();
2044 
2045 	return count;
2046 }
2047 /* }}} */
2048 
2049 static zend_long php_extract_prefix_same(zend_array *arr, zend_array *symbol_table, zend_string *prefix) /* {{{ */
2050 {
2051 	zend_long count = 0;
2052 	zend_string *var_name;
2053 	zval *entry, *orig_var, final_name;
2054 
2055 	if (HT_IS_PACKED(arr)) {
2056 		return 0;
2057 	}
2058 	ZEND_HASH_MAP_FOREACH_STR_KEY_VAL(arr, var_name, entry) {
2059 		if (!var_name) {
2060 			continue;
2061 		}
2062 		if (ZSTR_LEN(var_name) == 0) {
2063 			continue;
2064 		}
2065 		orig_var = zend_hash_find_known_hash(symbol_table, var_name);
2066 		if (orig_var) {
2067 			if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
2068 				orig_var = Z_INDIRECT_P(orig_var);
2069 				if (Z_TYPE_P(orig_var) == IS_UNDEF) {
2070 					ZVAL_COPY_DEREF(orig_var, entry);
2071 					count++;
2072 					continue;
2073 				}
2074 			}
2075 prefix:
2076 			php_prefix_varname(&final_name, prefix, ZSTR_VAL(var_name), ZSTR_LEN(var_name), 1);
2077 			if (php_valid_var_name(Z_STRVAL(final_name), Z_STRLEN(final_name))) {
2078 				if (zend_string_equals_literal(Z_STR(final_name), "this")) {
2079 					zend_throw_error(NULL, "Cannot re-assign $this");
2080 					return -1;
2081 				} else {
2082 					ZVAL_DEREF(entry);
2083 					if ((orig_var = zend_hash_find(symbol_table, Z_STR(final_name))) != NULL) {
2084 						if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
2085 							orig_var = Z_INDIRECT_P(orig_var);
2086 						}
2087 						ZEND_TRY_ASSIGN_COPY_EX(orig_var, entry, 0);
2088 						if (UNEXPECTED(EG(exception))) {
2089 							zend_string_release_ex(Z_STR(final_name), 0);
2090 							return -1;
2091 						}
2092 					} else {
2093 						Z_TRY_ADDREF_P(entry);
2094 						zend_hash_add_new(symbol_table, Z_STR(final_name), entry);
2095 					}
2096 					count++;
2097 				}
2098 			}
2099 			zval_ptr_dtor_str(&final_name);
2100 		} else {
2101 			if (!php_valid_var_name(ZSTR_VAL(var_name), ZSTR_LEN(var_name))) {
2102 				continue;
2103 			}
2104 			if (zend_string_equals_literal(var_name, "this")) {
2105 				goto prefix;
2106 			}
2107 			ZVAL_DEREF(entry);
2108 			Z_TRY_ADDREF_P(entry);
2109 			zend_hash_add_new(symbol_table, var_name, entry);
2110 			count++;
2111 		}
2112 	} ZEND_HASH_FOREACH_END();
2113 
2114 	return count;
2115 }
2116 /* }}} */
2117 
2118 static zend_long php_extract_ref_prefix_all(zend_array *arr, zend_array *symbol_table, zend_string *prefix) /* {{{ */
2119 {
2120 	zend_long count = 0;
2121 	zend_string *var_name;
2122 	zend_ulong num_key;
2123 	zval *entry, *orig_var, final_name;
2124 
2125 	ZEND_HASH_FOREACH_KEY_VAL(arr, num_key, var_name, entry) {
2126 		if (var_name) {
2127 			if (ZSTR_LEN(var_name) == 0) {
2128 				continue;
2129 			}
2130 			php_prefix_varname(&final_name, prefix, ZSTR_VAL(var_name), ZSTR_LEN(var_name), 1);
2131 		} else {
2132 			zend_string *str = zend_long_to_str(num_key);
2133 			php_prefix_varname(&final_name, prefix, ZSTR_VAL(str), ZSTR_LEN(str), 1);
2134 			zend_string_release_ex(str, 0);
2135 		}
2136 		if (php_valid_var_name(Z_STRVAL(final_name), Z_STRLEN(final_name))) {
2137 			if (zend_string_equals_literal(Z_STR(final_name), "this")) {
2138 				zend_throw_error(NULL, "Cannot re-assign $this");
2139 				return -1;
2140 			} else {
2141 				if (Z_ISREF_P(entry)) {
2142 					Z_ADDREF_P(entry);
2143 				} else {
2144 					ZVAL_MAKE_REF_EX(entry, 2);
2145 				}
2146 				if ((orig_var = zend_hash_find(symbol_table, Z_STR(final_name))) != NULL) {
2147 					if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
2148 						orig_var = Z_INDIRECT_P(orig_var);
2149 					}
2150 					zval_ptr_dtor(orig_var);
2151 					ZVAL_REF(orig_var, Z_REF_P(entry));
2152 				} else {
2153 					zend_hash_add_new(symbol_table, Z_STR(final_name), entry);
2154 				}
2155 				count++;
2156 			}
2157 		}
2158 		zval_ptr_dtor_str(&final_name);
2159 	} ZEND_HASH_FOREACH_END();
2160 
2161 	return count;
2162 }
2163 /* }}} */
2164 
2165 static zend_long php_extract_prefix_all(zend_array *arr, zend_array *symbol_table, zend_string *prefix) /* {{{ */
2166 {
2167 	zend_long count = 0;
2168 	zend_string *var_name;
2169 	zend_ulong num_key;
2170 	zval *entry, *orig_var, final_name;
2171 
2172 	ZEND_HASH_FOREACH_KEY_VAL(arr, num_key, var_name, entry) {
2173 		if (var_name) {
2174 			if (ZSTR_LEN(var_name) == 0) {
2175 				continue;
2176 			}
2177 			php_prefix_varname(&final_name, prefix, ZSTR_VAL(var_name), ZSTR_LEN(var_name), 1);
2178 		} else {
2179 			zend_string *str = zend_long_to_str(num_key);
2180 			php_prefix_varname(&final_name, prefix, ZSTR_VAL(str), ZSTR_LEN(str), 1);
2181 			zend_string_release_ex(str, 0);
2182 		}
2183 		if (php_valid_var_name(Z_STRVAL(final_name), Z_STRLEN(final_name))) {
2184 			if (zend_string_equals_literal(Z_STR(final_name), "this")) {
2185 				zend_throw_error(NULL, "Cannot re-assign $this");
2186 				return -1;
2187 			} else {
2188 				ZVAL_DEREF(entry);
2189 				if ((orig_var = zend_hash_find(symbol_table, Z_STR(final_name))) != NULL) {
2190 					if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
2191 						orig_var = Z_INDIRECT_P(orig_var);
2192 					}
2193 					ZEND_TRY_ASSIGN_COPY_EX(orig_var, entry, 0);
2194 					if (UNEXPECTED(EG(exception))) {
2195 						zend_string_release_ex(Z_STR(final_name), 0);
2196 						return -1;
2197 					}
2198 				} else {
2199 					Z_TRY_ADDREF_P(entry);
2200 					zend_hash_add_new(symbol_table, Z_STR(final_name), entry);
2201 				}
2202 				count++;
2203 			}
2204 		}
2205 		zval_ptr_dtor_str(&final_name);
2206 	} ZEND_HASH_FOREACH_END();
2207 
2208 	return count;
2209 }
2210 /* }}} */
2211 
2212 static zend_long php_extract_ref_prefix_invalid(zend_array *arr, zend_array *symbol_table, zend_string *prefix) /* {{{ */
2213 {
2214 	zend_long count = 0;
2215 	zend_string *var_name;
2216 	zend_ulong num_key;
2217 	zval *entry, *orig_var, final_name;
2218 
2219 	ZEND_HASH_FOREACH_KEY_VAL(arr, num_key, var_name, entry) {
2220 		if (var_name) {
2221 			if (!php_valid_var_name(ZSTR_VAL(var_name), ZSTR_LEN(var_name))
2222 			 || zend_string_equals_literal(var_name, "this")) {
2223 				php_prefix_varname(&final_name, prefix, ZSTR_VAL(var_name), ZSTR_LEN(var_name), 1);
2224 				if (!php_valid_var_name(Z_STRVAL(final_name), Z_STRLEN(final_name))) {
2225 					zval_ptr_dtor_str(&final_name);
2226 					continue;
2227 				}
2228 			} else {
2229 				ZVAL_STR_COPY(&final_name, var_name);
2230 			}
2231 		} else {
2232 			zend_string *str = zend_long_to_str(num_key);
2233 			php_prefix_varname(&final_name, prefix, ZSTR_VAL(str), ZSTR_LEN(str), 1);
2234 			zend_string_release_ex(str, 0);
2235 			if (!php_valid_var_name(Z_STRVAL(final_name), Z_STRLEN(final_name))) {
2236 				zval_ptr_dtor_str(&final_name);
2237 				continue;
2238 			}
2239 		}
2240 		if (zend_string_equals_literal(Z_STR(final_name), "this")) {
2241 			zend_throw_error(NULL, "Cannot re-assign $this");
2242 			return -1;
2243 		} else {
2244 			if (Z_ISREF_P(entry)) {
2245 				Z_ADDREF_P(entry);
2246 			} else {
2247 				ZVAL_MAKE_REF_EX(entry, 2);
2248 			}
2249 			if ((orig_var = zend_hash_find(symbol_table, Z_STR(final_name))) != NULL) {
2250 				if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
2251 					orig_var = Z_INDIRECT_P(orig_var);
2252 				}
2253 				zval_ptr_dtor(orig_var);
2254 				ZVAL_REF(orig_var, Z_REF_P(entry));
2255 			} else {
2256 				zend_hash_add_new(symbol_table, Z_STR(final_name), entry);
2257 			}
2258 			count++;
2259 		}
2260 		zval_ptr_dtor_str(&final_name);
2261 	} ZEND_HASH_FOREACH_END();
2262 
2263 	return count;
2264 }
2265 /* }}} */
2266 
2267 static zend_long php_extract_prefix_invalid(zend_array *arr, zend_array *symbol_table, zend_string *prefix) /* {{{ */
2268 {
2269 	zend_long count = 0;
2270 	zend_string *var_name;
2271 	zend_ulong num_key;
2272 	zval *entry, *orig_var, final_name;
2273 
2274 	ZEND_HASH_FOREACH_KEY_VAL(arr, num_key, var_name, entry) {
2275 		if (var_name) {
2276 			if (!php_valid_var_name(ZSTR_VAL(var_name), ZSTR_LEN(var_name))
2277 			 || zend_string_equals_literal(var_name, "this")) {
2278 				php_prefix_varname(&final_name, prefix, ZSTR_VAL(var_name), ZSTR_LEN(var_name), 1);
2279 				if (!php_valid_var_name(Z_STRVAL(final_name), Z_STRLEN(final_name))) {
2280 					zval_ptr_dtor_str(&final_name);
2281 					continue;
2282 				}
2283 			} else {
2284 				ZVAL_STR_COPY(&final_name, var_name);
2285 			}
2286 		} else {
2287 			zend_string *str = zend_long_to_str(num_key);
2288 			php_prefix_varname(&final_name, prefix, ZSTR_VAL(str), ZSTR_LEN(str), 1);
2289 			zend_string_release_ex(str, 0);
2290 			if (!php_valid_var_name(Z_STRVAL(final_name), Z_STRLEN(final_name))) {
2291 				zval_ptr_dtor_str(&final_name);
2292 				continue;
2293 			}
2294 		}
2295 		if (zend_string_equals_literal(Z_STR(final_name), "this")) {
2296 			zend_throw_error(NULL, "Cannot re-assign $this");
2297 			return -1;
2298 		} else {
2299 			ZVAL_DEREF(entry);
2300 			if ((orig_var = zend_hash_find(symbol_table, Z_STR(final_name))) != NULL) {
2301 				if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
2302 					orig_var = Z_INDIRECT_P(orig_var);
2303 				}
2304 				ZEND_TRY_ASSIGN_COPY_EX(orig_var, entry, 0);
2305 				if (UNEXPECTED(EG(exception))) {
2306 					zend_string_release_ex(Z_STR(final_name), 0);
2307 					return -1;
2308 				}
2309 			} else {
2310 				Z_TRY_ADDREF_P(entry);
2311 				zend_hash_add_new(symbol_table, Z_STR(final_name), entry);
2312 			}
2313 			count++;
2314 		}
2315 		zval_ptr_dtor_str(&final_name);
2316 	} ZEND_HASH_FOREACH_END();
2317 
2318 	return count;
2319 }
2320 /* }}} */
2321 
2322 static zend_long php_extract_ref_skip(zend_array *arr, zend_array *symbol_table) /* {{{ */
2323 {
2324 	zend_long count = 0;
2325 	zend_string *var_name;
2326 	zval *entry, *orig_var;
2327 
2328 	if (HT_IS_PACKED(arr)) {
2329 		return 0;
2330 	}
2331 	ZEND_HASH_MAP_FOREACH_STR_KEY_VAL(arr, var_name, entry) {
2332 		if (!var_name) {
2333 			continue;
2334 		}
2335 		if (!php_valid_var_name(ZSTR_VAL(var_name), ZSTR_LEN(var_name))) {
2336 			continue;
2337 		}
2338 		if (zend_string_equals_literal(var_name, "this")) {
2339 			continue;
2340 		}
2341 		orig_var = zend_hash_find_known_hash(symbol_table, var_name);
2342 		if (orig_var) {
2343 			if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
2344 				orig_var = Z_INDIRECT_P(orig_var);
2345 				if (Z_TYPE_P(orig_var) == IS_UNDEF) {
2346 					if (Z_ISREF_P(entry)) {
2347 						Z_ADDREF_P(entry);
2348 					} else {
2349 						ZVAL_MAKE_REF_EX(entry, 2);
2350 					}
2351 					ZVAL_REF(orig_var, Z_REF_P(entry));
2352 					count++;
2353 				}
2354 			}
2355 		} else {
2356 			if (Z_ISREF_P(entry)) {
2357 				Z_ADDREF_P(entry);
2358 			} else {
2359 				ZVAL_MAKE_REF_EX(entry, 2);
2360 			}
2361 			zend_hash_add_new(symbol_table, var_name, entry);
2362 			count++;
2363 		}
2364 	} ZEND_HASH_FOREACH_END();
2365 
2366 	return count;
2367 }
2368 /* }}} */
2369 
2370 static zend_long php_extract_skip(zend_array *arr, zend_array *symbol_table) /* {{{ */
2371 {
2372 	zend_long count = 0;
2373 	zend_string *var_name;
2374 	zval *entry, *orig_var;
2375 
2376 	if (HT_IS_PACKED(arr)) {
2377 		return 0;
2378 	}
2379 	ZEND_HASH_MAP_FOREACH_STR_KEY_VAL(arr, var_name, entry) {
2380 		if (!var_name) {
2381 			continue;
2382 		}
2383 		if (!php_valid_var_name(ZSTR_VAL(var_name), ZSTR_LEN(var_name))) {
2384 			continue;
2385 		}
2386 		if (zend_string_equals_literal(var_name, "this")) {
2387 			continue;
2388 		}
2389 		orig_var = zend_hash_find_known_hash(symbol_table, var_name);
2390 		if (orig_var) {
2391 			if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
2392 				orig_var = Z_INDIRECT_P(orig_var);
2393 				if (Z_TYPE_P(orig_var) == IS_UNDEF) {
2394 					ZVAL_COPY_DEREF(orig_var, entry);
2395 					count++;
2396 				}
2397 			}
2398 		} else {
2399 			ZVAL_DEREF(entry);
2400 			Z_TRY_ADDREF_P(entry);
2401 			zend_hash_add_new(symbol_table, var_name, entry);
2402 			count++;
2403 		}
2404 	} ZEND_HASH_FOREACH_END();
2405 
2406 	return count;
2407 }
2408 /* }}} */
2409 
2410 /* {{{ Imports variables into symbol table from an array */
2411 PHP_FUNCTION(extract)
2412 {
2413 	zval *var_array_param;
2414 	zend_long extract_refs;
2415 	zend_long extract_type = EXTR_OVERWRITE;
2416 	zend_string *prefix = NULL;
2417 	zend_long count;
2418 	zend_array *symbol_table;
2419 
2420 	ZEND_PARSE_PARAMETERS_START(1, 3)
2421 		Z_PARAM_ARRAY_EX2(var_array_param, 0, 1, 0)
2422 		Z_PARAM_OPTIONAL
2423 		Z_PARAM_LONG(extract_type)
2424 		Z_PARAM_STR(prefix)
2425 	ZEND_PARSE_PARAMETERS_END();
2426 
2427 	extract_refs = (extract_type & EXTR_REFS);
2428 	if (extract_refs) {
2429 		SEPARATE_ARRAY(var_array_param);
2430 	}
2431 	extract_type &= 0xff;
2432 
2433 	if (extract_type < EXTR_OVERWRITE || extract_type > EXTR_IF_EXISTS) {
2434 		zend_argument_value_error(2, "must be a valid extract type");
2435 		RETURN_THROWS();
2436 	}
2437 
2438 	if (extract_type > EXTR_SKIP && extract_type <= EXTR_PREFIX_IF_EXISTS && ZEND_NUM_ARGS() < 3) {
2439 		zend_argument_value_error(3, "is required when using this extract type");
2440 		RETURN_THROWS();
2441 	}
2442 
2443 	if (prefix) {
2444 		if (ZSTR_LEN(prefix) && !php_valid_var_name(ZSTR_VAL(prefix), ZSTR_LEN(prefix))) {
2445 			zend_argument_value_error(3, "must be a valid identifier");
2446 			RETURN_THROWS();
2447 		}
2448 	}
2449 
2450 	if (zend_forbid_dynamic_call() == FAILURE) {
2451 		return;
2452 	}
2453 
2454 	symbol_table = zend_rebuild_symbol_table();
2455 	ZEND_ASSERT(symbol_table && "A symbol table should always be available here");
2456 
2457 	if (extract_refs) {
2458 		switch (extract_type) {
2459 			case EXTR_IF_EXISTS:
2460 				count = php_extract_ref_if_exists(Z_ARRVAL_P(var_array_param), symbol_table);
2461 				break;
2462 			case EXTR_OVERWRITE:
2463 				count = php_extract_ref_overwrite(Z_ARRVAL_P(var_array_param), symbol_table);
2464 				break;
2465 			case EXTR_PREFIX_IF_EXISTS:
2466 				count = php_extract_ref_prefix_if_exists(Z_ARRVAL_P(var_array_param), symbol_table, prefix);
2467 				break;
2468 			case EXTR_PREFIX_SAME:
2469 				count = php_extract_ref_prefix_same(Z_ARRVAL_P(var_array_param), symbol_table, prefix);
2470 				break;
2471 			case EXTR_PREFIX_ALL:
2472 				count = php_extract_ref_prefix_all(Z_ARRVAL_P(var_array_param), symbol_table, prefix);
2473 				break;
2474 			case EXTR_PREFIX_INVALID:
2475 				count = php_extract_ref_prefix_invalid(Z_ARRVAL_P(var_array_param), symbol_table, prefix);
2476 				break;
2477 			default:
2478 				count = php_extract_ref_skip(Z_ARRVAL_P(var_array_param), symbol_table);
2479 				break;
2480 		}
2481 	} else {
2482 		/* The array might be stored in a local variable that will be overwritten */
2483 		zval array_copy;
2484 		ZVAL_COPY(&array_copy, var_array_param);
2485 		switch (extract_type) {
2486 			case EXTR_IF_EXISTS:
2487 				count = php_extract_if_exists(Z_ARRVAL(array_copy), symbol_table);
2488 				break;
2489 			case EXTR_OVERWRITE:
2490 				count = php_extract_overwrite(Z_ARRVAL(array_copy), symbol_table);
2491 				break;
2492 			case EXTR_PREFIX_IF_EXISTS:
2493 				count = php_extract_prefix_if_exists(Z_ARRVAL(array_copy), symbol_table, prefix);
2494 				break;
2495 			case EXTR_PREFIX_SAME:
2496 				count = php_extract_prefix_same(Z_ARRVAL(array_copy), symbol_table, prefix);
2497 				break;
2498 			case EXTR_PREFIX_ALL:
2499 				count = php_extract_prefix_all(Z_ARRVAL(array_copy), symbol_table, prefix);
2500 				break;
2501 			case EXTR_PREFIX_INVALID:
2502 				count = php_extract_prefix_invalid(Z_ARRVAL(array_copy), symbol_table, prefix);
2503 				break;
2504 			default:
2505 				count = php_extract_skip(Z_ARRVAL(array_copy), symbol_table);
2506 				break;
2507 		}
2508 		zval_ptr_dtor(&array_copy);
2509 	}
2510 
2511 	RETURN_LONG(count);
2512 }
2513 /* }}} */
2514 
2515 static void php_compact_var(HashTable *eg_active_symbol_table, zval *return_value, zval *entry, uint32_t pos) /* {{{ */
2516 {
2517 	zval *value_ptr, data;
2518 
2519 	ZVAL_DEREF(entry);
2520 	if (Z_TYPE_P(entry) == IS_STRING) {
2521 		if ((value_ptr = zend_hash_find_ind(eg_active_symbol_table, Z_STR_P(entry))) != NULL) {
2522 			ZVAL_DEREF(value_ptr);
2523 			Z_TRY_ADDREF_P(value_ptr);
2524 			zend_hash_update(Z_ARRVAL_P(return_value), Z_STR_P(entry), value_ptr);
2525 		} else if (zend_string_equals_literal(Z_STR_P(entry), "this")) {
2526 			zend_object *object = zend_get_this_object(EG(current_execute_data));
2527 			if (object) {
2528 				ZVAL_OBJ_COPY(&data, object);
2529 				zend_hash_update(Z_ARRVAL_P(return_value), Z_STR_P(entry), &data);
2530 			}
2531 		} else {
2532 			php_error_docref(NULL, E_WARNING, "Undefined variable $%s", ZSTR_VAL(Z_STR_P(entry)));
2533 		}
2534 	} else if (Z_TYPE_P(entry) == IS_ARRAY) {
2535 	    if (Z_REFCOUNTED_P(entry)) {
2536 			if (Z_IS_RECURSIVE_P(entry)) {
2537 				zend_throw_error(NULL, "Recursion detected");
2538 				return;
2539 			}
2540 			Z_PROTECT_RECURSION_P(entry);
2541 		}
2542 		ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(entry), value_ptr) {
2543 			php_compact_var(eg_active_symbol_table, return_value, value_ptr, pos);
2544 		} ZEND_HASH_FOREACH_END();
2545 	    if (Z_REFCOUNTED_P(entry)) {
2546 			Z_UNPROTECT_RECURSION_P(entry);
2547 		}
2548 	} else {
2549 		php_error_docref(NULL, E_WARNING, "Argument #%d must be string or array of strings, %s given", pos, zend_zval_type_name(entry));
2550 		return;
2551 	}
2552 }
2553 /* }}} */
2554 
2555 /* {{{ Creates a hash containing variables and their values */
2556 PHP_FUNCTION(compact)
2557 {
2558 	zval *args = NULL;	/* function arguments array */
2559 	uint32_t num_args, i;
2560 	zend_array *symbol_table;
2561 
2562 	ZEND_PARSE_PARAMETERS_START(1, -1)
2563 		Z_PARAM_VARIADIC('+', args, num_args)
2564 	ZEND_PARSE_PARAMETERS_END();
2565 
2566 	if (zend_forbid_dynamic_call() == FAILURE) {
2567 		return;
2568 	}
2569 
2570 	symbol_table = zend_rebuild_symbol_table();
2571 	ZEND_ASSERT(symbol_table && "A symbol table should always be available here");
2572 
2573 	/* compact() is probably most used with a single array of var_names
2574 	   or multiple string names, rather than a combination of both.
2575 	   So quickly guess a minimum result size based on that */
2576 	if (num_args && Z_TYPE(args[0]) == IS_ARRAY) {
2577 		array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL(args[0])));
2578 	} else {
2579 		array_init_size(return_value, num_args);
2580 	}
2581 
2582 	for (i = 0; i < num_args; i++) {
2583 		php_compact_var(symbol_table, return_value, &args[i], i + 1);
2584 	}
2585 }
2586 /* }}} */
2587 
2588 /* {{{ Create an array containing num elements starting with index start_key each initialized to val */
2589 PHP_FUNCTION(array_fill)
2590 {
2591 	zval *val;
2592 	zend_long start_key, num;
2593 
2594 	ZEND_PARSE_PARAMETERS_START(3, 3)
2595 		Z_PARAM_LONG(start_key)
2596 		Z_PARAM_LONG(num)
2597 		Z_PARAM_ZVAL(val)
2598 	ZEND_PARSE_PARAMETERS_END();
2599 
2600 	if (EXPECTED(num > 0)) {
2601 		if (sizeof(num) > 4 && UNEXPECTED(EXPECTED(num > 0x7fffffff))) {
2602 			zend_argument_value_error(2, "is too large");
2603 			RETURN_THROWS();
2604 		} else if (UNEXPECTED(start_key > ZEND_LONG_MAX - num + 1)) {
2605 			zend_throw_error(NULL, "Cannot add element to the array as the next element is already occupied");
2606 			RETURN_THROWS();
2607 		} else if (EXPECTED(start_key >= 0) && EXPECTED(start_key < num)) {
2608 			/* create packed array */
2609 			zval *zv;
2610 
2611 			array_init_size(return_value, (uint32_t)(start_key + num));
2612 			zend_hash_real_init_packed(Z_ARRVAL_P(return_value));
2613 			Z_ARRVAL_P(return_value)->nNumUsed = (uint32_t)(start_key + num);
2614 			Z_ARRVAL_P(return_value)->nNumOfElements = (uint32_t)num;
2615 			Z_ARRVAL_P(return_value)->nNextFreeElement = (zend_long)(start_key + num);
2616 
2617 			if (Z_REFCOUNTED_P(val)) {
2618 				GC_ADDREF_EX(Z_COUNTED_P(val), (uint32_t)num);
2619 			}
2620 
2621 			zv = Z_ARRVAL_P(return_value)->arPacked;
2622 
2623 			while (start_key--) {
2624 				ZVAL_UNDEF(zv);
2625 				zv++;
2626 			}
2627 			while (num--) {
2628 				ZVAL_COPY_VALUE(zv, val);
2629 				zv++;
2630 			}
2631 		} else {
2632 			/* create hash */
2633 			array_init_size(return_value, (uint32_t)num);
2634 			zend_hash_real_init_mixed(Z_ARRVAL_P(return_value));
2635 			if (Z_REFCOUNTED_P(val)) {
2636 				GC_ADDREF_EX(Z_COUNTED_P(val), (uint32_t)num);
2637 			}
2638 			zend_hash_index_add_new(Z_ARRVAL_P(return_value), start_key, val);
2639 			while (--num) {
2640 				zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), val);
2641 				start_key++;
2642 			}
2643 		}
2644 	} else if (EXPECTED(num == 0)) {
2645 		RETURN_EMPTY_ARRAY();
2646 	} else {
2647 		zend_argument_value_error(2, "must be greater than or equal to 0");
2648 		RETURN_THROWS();
2649 	}
2650 }
2651 /* }}} */
2652 
2653 /* {{{ Create an array using the elements of the first parameter as keys each initialized to val */
2654 PHP_FUNCTION(array_fill_keys)
2655 {
2656 	zval *keys, *val, *entry;
2657 
2658 	ZEND_PARSE_PARAMETERS_START(2, 2)
2659 		Z_PARAM_ARRAY(keys)
2660 		Z_PARAM_ZVAL(val)
2661 	ZEND_PARSE_PARAMETERS_END();
2662 
2663 	/* Initialize return array */
2664 	array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(keys)));
2665 
2666 	ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(keys), entry) {
2667 		ZVAL_DEREF(entry);
2668 		Z_TRY_ADDREF_P(val);
2669 		if (Z_TYPE_P(entry) == IS_LONG) {
2670 			zend_hash_index_update(Z_ARRVAL_P(return_value), Z_LVAL_P(entry), val);
2671 		} else {
2672 			zend_string *tmp_key;
2673 			zend_string *key = zval_get_tmp_string(entry, &tmp_key);
2674 			zend_symtable_update(Z_ARRVAL_P(return_value), key, val);
2675 			zend_tmp_string_release(tmp_key);
2676 		}
2677 	} ZEND_HASH_FOREACH_END();
2678 }
2679 /* }}} */
2680 
2681 #define RANGE_CHECK_DOUBLE_INIT_ARRAY(start, end) do { \
2682 		double __calc_size = ((start - end) / step) + 1; \
2683 		if (__calc_size >= (double)HT_MAX_SIZE) { \
2684 			zend_value_error(\
2685 					"The supplied range exceeds the maximum array size: start=%0.0f end=%0.0f", end, start); \
2686 			RETURN_THROWS(); \
2687 		} \
2688 		size = (uint32_t)_php_math_round(__calc_size, 0, PHP_ROUND_HALF_UP); \
2689 		array_init_size(return_value, size); \
2690 		zend_hash_real_init_packed(Z_ARRVAL_P(return_value)); \
2691 	} while (0)
2692 
2693 #define RANGE_CHECK_LONG_INIT_ARRAY(start, end) do { \
2694 		zend_ulong __calc_size = ((zend_ulong) start - end) / lstep; \
2695 		if (__calc_size >= HT_MAX_SIZE - 1) { \
2696 			zend_value_error(\
2697 					"The supplied range exceeds the maximum array size: start=" ZEND_LONG_FMT " end=" ZEND_LONG_FMT, end, start); \
2698 			RETURN_THROWS(); \
2699 		} \
2700 		size = (uint32_t)(__calc_size + 1); \
2701 		array_init_size(return_value, size); \
2702 		zend_hash_real_init_packed(Z_ARRVAL_P(return_value)); \
2703 	} while (0)
2704 
2705 /* {{{ Create an array containing the range of integers or characters from low to high (inclusive) */
2706 PHP_FUNCTION(range)
2707 {
2708 	zval *zlow, *zhigh, *zstep = NULL, tmp;
2709 	int err = 0, is_step_double = 0;
2710 	double step = 1.0;
2711 
2712 	ZEND_PARSE_PARAMETERS_START(2, 3)
2713 		Z_PARAM_ZVAL(zlow)
2714 		Z_PARAM_ZVAL(zhigh)
2715 		Z_PARAM_OPTIONAL
2716 		Z_PARAM_NUMBER(zstep)
2717 	ZEND_PARSE_PARAMETERS_END();
2718 
2719 	if (zstep) {
2720 		is_step_double = Z_TYPE_P(zstep) == IS_DOUBLE;
2721 		step = zval_get_double(zstep);
2722 
2723 		/* We only want positive step values. */
2724 		if (step < 0.0) {
2725 			step *= -1;
2726 		}
2727 	}
2728 
2729 	/* If the range is given as strings, generate an array of characters. */
2730 	if (Z_TYPE_P(zlow) == IS_STRING && Z_TYPE_P(zhigh) == IS_STRING && Z_STRLEN_P(zlow) >= 1 && Z_STRLEN_P(zhigh) >= 1) {
2731 		int type1, type2;
2732 		unsigned char low, high;
2733 		zend_long lstep = (zend_long) step;
2734 
2735 		type1 = is_numeric_string(Z_STRVAL_P(zlow), Z_STRLEN_P(zlow), NULL, NULL, 0);
2736 		type2 = is_numeric_string(Z_STRVAL_P(zhigh), Z_STRLEN_P(zhigh), NULL, NULL, 0);
2737 
2738 		if (type1 == IS_DOUBLE || type2 == IS_DOUBLE || is_step_double) {
2739 			goto double_str;
2740 		} else if (type1 == IS_LONG || type2 == IS_LONG) {
2741 			goto long_str;
2742 		}
2743 
2744 		low = (unsigned char)Z_STRVAL_P(zlow)[0];
2745 		high = (unsigned char)Z_STRVAL_P(zhigh)[0];
2746 
2747 		if (low > high) {		/* Negative Steps */
2748 			if (low - high < lstep || lstep <= 0) {
2749 				err = 1;
2750 				goto err;
2751 			}
2752 			/* Initialize the return_value as an array. */
2753 			array_init_size(return_value, (uint32_t)(((low - high) / lstep) + 1));
2754 			zend_hash_real_init_packed(Z_ARRVAL_P(return_value));
2755 			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2756 				for (; low >= high; low -= (unsigned int)lstep) {
2757 					ZEND_HASH_FILL_SET_INTERNED_STR(ZSTR_CHAR(low));
2758 					ZEND_HASH_FILL_NEXT();
2759 					if (((signed int)low - lstep) < 0) {
2760 						break;
2761 					}
2762 				}
2763 			} ZEND_HASH_FILL_END();
2764 		} else if (high > low) {	/* Positive Steps */
2765 			if (high - low < lstep || lstep <= 0) {
2766 				err = 1;
2767 				goto err;
2768 			}
2769 			array_init_size(return_value, (uint32_t)(((high - low) / lstep) + 1));
2770 			zend_hash_real_init_packed(Z_ARRVAL_P(return_value));
2771 			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2772 				for (; low <= high; low += (unsigned int)lstep) {
2773 					ZEND_HASH_FILL_SET_INTERNED_STR(ZSTR_CHAR(low));
2774 					ZEND_HASH_FILL_NEXT();
2775 					if (((signed int)low + lstep) > 255) {
2776 						break;
2777 					}
2778 				}
2779 			} ZEND_HASH_FILL_END();
2780 		} else {
2781 			array_init(return_value);
2782 			ZVAL_CHAR(&tmp, low);
2783 			zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
2784 		}
2785 	} else if (Z_TYPE_P(zlow) == IS_DOUBLE || Z_TYPE_P(zhigh) == IS_DOUBLE || is_step_double) {
2786 		double low, high, element;
2787 		uint32_t i, size;
2788 double_str:
2789 		low = zval_get_double(zlow);
2790 		high = zval_get_double(zhigh);
2791 
2792 		if (zend_isinf(high) || zend_isinf(low)) {
2793 			zend_value_error("Invalid range supplied: start=%0.0f end=%0.0f", low, high);
2794 			RETURN_THROWS();
2795 		}
2796 
2797 		if (low > high) { 		/* Negative steps */
2798 			if (low - high < step || step <= 0) {
2799 				err = 1;
2800 				goto err;
2801 			}
2802 
2803 			RANGE_CHECK_DOUBLE_INIT_ARRAY(low, high);
2804 
2805 			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2806 				for (i = 0, element = low; i < size && element >= high; ++i, element = low - (i * step)) {
2807 					ZEND_HASH_FILL_SET_DOUBLE(element);
2808 					ZEND_HASH_FILL_NEXT();
2809 				}
2810 			} ZEND_HASH_FILL_END();
2811 		} else if (high > low) { 	/* Positive steps */
2812 			if (high - low < step || step <= 0) {
2813 				err = 1;
2814 				goto err;
2815 			}
2816 
2817 			RANGE_CHECK_DOUBLE_INIT_ARRAY(high, low);
2818 
2819 			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2820 				for (i = 0, element = low; i < size && element <= high; ++i, element = low + (i * step)) {
2821 					ZEND_HASH_FILL_SET_DOUBLE(element);
2822 					ZEND_HASH_FILL_NEXT();
2823 				}
2824 			} ZEND_HASH_FILL_END();
2825 		} else {
2826 			array_init(return_value);
2827 			ZVAL_DOUBLE(&tmp, low);
2828 			zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
2829 		}
2830 	} else {
2831 		zend_long low, high;
2832 		/* lstep is a zend_ulong so that comparisons to it don't overflow, i.e. low - high < lstep */
2833 		zend_ulong lstep;
2834 		uint32_t i, size;
2835 long_str:
2836 		low = zval_get_long(zlow);
2837 		high = zval_get_long(zhigh);
2838 
2839 		if (step <= 0) {
2840 			err = 1;
2841 			goto err;
2842 		}
2843 
2844 		lstep = (zend_ulong)step;
2845 		if (step <= 0) {
2846 			err = 1;
2847 			goto err;
2848 		}
2849 
2850 		if (low > high) { 		/* Negative steps */
2851 			if ((zend_ulong)low - high < lstep) {
2852 				err = 1;
2853 				goto err;
2854 			}
2855 
2856 			RANGE_CHECK_LONG_INIT_ARRAY(low, high);
2857 
2858 			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2859 				for (i = 0; i < size; ++i) {
2860 					ZEND_HASH_FILL_SET_LONG(low - (i * lstep));
2861 					ZEND_HASH_FILL_NEXT();
2862 				}
2863 			} ZEND_HASH_FILL_END();
2864 		} else if (high > low) { 	/* Positive steps */
2865 			if ((zend_ulong)high - low < lstep) {
2866 				err = 1;
2867 				goto err;
2868 			}
2869 
2870 			RANGE_CHECK_LONG_INIT_ARRAY(high, low);
2871 
2872 			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2873 				for (i = 0; i < size; ++i) {
2874 					ZEND_HASH_FILL_SET_LONG(low + (i * lstep));
2875 					ZEND_HASH_FILL_NEXT();
2876 				}
2877 			} ZEND_HASH_FILL_END();
2878 		} else {
2879 			array_init(return_value);
2880 			ZVAL_LONG(&tmp, low);
2881 			zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
2882 		}
2883 	}
2884 err:
2885 	if (err) {
2886 		zend_argument_value_error(3, "must not exceed the specified range");
2887 		RETURN_THROWS();
2888 	}
2889 }
2890 /* }}} */
2891 
2892 #undef RANGE_CHECK_DOUBLE_INIT_ARRAY
2893 #undef RANGE_CHECK_LONG_INIT_ARRAY
2894 
2895 static void php_array_data_shuffle(zval *array) /* {{{ */
2896 {
2897 	uint32_t idx, j, n_elems;
2898 	zval *zv, temp;
2899 	HashTable *hash;
2900 	zend_long rnd_idx;
2901 	uint32_t n_left;
2902 
2903 	n_elems = zend_hash_num_elements(Z_ARRVAL_P(array));
2904 
2905 	if (n_elems < 1) {
2906 		return;
2907 	}
2908 
2909 	hash = Z_ARRVAL_P(array);
2910 	n_left = n_elems;
2911 
2912 	if (!HT_IS_PACKED(hash)) {
2913 		if (!HT_HAS_STATIC_KEYS_ONLY(hash)) {
2914 			Bucket *p = hash->arData;
2915 			uint32_t i = hash->nNumUsed;
2916 
2917 			for (; i > 0; p++, i--) {
2918 				if (p->key) {
2919 					zend_string_release(p->key);
2920 					p->key = NULL;
2921 				}
2922 			}
2923 		}
2924 		zend_hash_to_packed(hash);
2925 	}
2926 
2927 	if (EXPECTED(!HT_HAS_ITERATORS(hash))) {
2928 		if (hash->nNumUsed != hash->nNumOfElements) {
2929 			for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) {
2930 				zv = hash->arPacked + idx;
2931 				if (Z_TYPE_P(zv) == IS_UNDEF) continue;
2932 				if (j != idx) {
2933 					ZVAL_COPY_VALUE(&hash->arPacked[j], zv);
2934 				}
2935 				j++;
2936 			}
2937 		}
2938 		while (--n_left) {
2939 			rnd_idx = php_mt_rand_range(0, n_left);
2940 			if (rnd_idx != n_left) {
2941 				ZVAL_COPY_VALUE(&temp, &hash->arPacked[n_left]);
2942 				ZVAL_COPY_VALUE(&hash->arPacked[n_left], &hash->arPacked[rnd_idx]);
2943 				ZVAL_COPY_VALUE(&hash->arPacked[rnd_idx], &temp);
2944 			}
2945 		}
2946 	} else {
2947 		uint32_t iter_pos = zend_hash_iterators_lower_pos(hash, 0);
2948 
2949 		if (hash->nNumUsed != hash->nNumOfElements) {
2950 			for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) {
2951 				zv = hash->arPacked + idx;
2952 				if (Z_TYPE_P(zv) == IS_UNDEF) continue;
2953 				if (j != idx) {
2954 					ZVAL_COPY_VALUE(&hash->arPacked[j], zv);
2955 					if (idx == iter_pos) {
2956 						zend_hash_iterators_update(hash, idx, j);
2957 						iter_pos = zend_hash_iterators_lower_pos(hash, iter_pos + 1);
2958 					}
2959 				}
2960 				j++;
2961 			}
2962 		}
2963 		while (--n_left) {
2964 			rnd_idx = php_mt_rand_range(0, n_left);
2965 			if (rnd_idx != n_left) {
2966 				ZVAL_COPY_VALUE(&temp, &hash->arPacked[n_left]);
2967 				ZVAL_COPY_VALUE(&hash->arPacked[n_left], &hash->arPacked[rnd_idx]);
2968 				ZVAL_COPY_VALUE(&hash->arPacked[rnd_idx], &temp);
2969 				zend_hash_iterators_update(hash, (uint32_t)rnd_idx, n_left);
2970 			}
2971 		}
2972 	}
2973 	hash->nNumUsed = n_elems;
2974 	hash->nInternalPointer = 0;
2975 	hash->nNextFreeElement = n_elems;
2976 }
2977 /* }}} */
2978 
2979 /* {{{ Randomly shuffle the contents of an array */
2980 PHP_FUNCTION(shuffle)
2981 {
2982 	zval *array;
2983 
2984 	ZEND_PARSE_PARAMETERS_START(1, 1)
2985 		Z_PARAM_ARRAY_EX(array, 0, 1)
2986 	ZEND_PARSE_PARAMETERS_END();
2987 
2988 	php_array_data_shuffle(array);
2989 
2990 	RETURN_TRUE;
2991 }
2992 /* }}} */
2993 
2994 static void php_splice(HashTable *in_hash, zend_long offset, zend_long length, HashTable *replace, HashTable *removed) /* {{{ */
2995 {
2996 	HashTable 	 out_hash;			/* Output hashtable */
2997 	zend_long	 num_in;			/* Number of entries in the input hashtable */
2998 	zend_long	 pos;				/* Current position in the hashtable */
2999 	uint32_t     idx;
3000 	zval		*entry;				/* Hash entry */
3001 	uint32_t    iter_pos = zend_hash_iterators_lower_pos(in_hash, 0);
3002 
3003 	/* Get number of entries in the input hash */
3004 	num_in = zend_hash_num_elements(in_hash);
3005 
3006 	/* Clamp the offset.. */
3007 	if (offset > num_in) {
3008 		offset = num_in;
3009 	} else if (offset < 0 && (offset = (num_in + offset)) < 0) {
3010 		offset = 0;
3011 	}
3012 
3013 	/* ..and the length */
3014 	if (length < 0) {
3015 		length = num_in - offset + length;
3016 	} else if (((unsigned)offset + (unsigned)length) > (unsigned)num_in) {
3017 		length = num_in - offset;
3018 	}
3019 
3020 	/* Create and initialize output hash */
3021 	zend_hash_init(&out_hash, (length > 0 ? num_in - length : 0) + (replace ? zend_hash_num_elements(replace) : 0), NULL, ZVAL_PTR_DTOR, 0);
3022 
3023 	if (HT_IS_PACKED(in_hash)) {
3024 		/* Start at the beginning of the input hash and copy entries to output hash until offset is reached */
3025 		entry = in_hash->arPacked;
3026 		for (pos = 0, idx = 0; pos < offset && idx < in_hash->nNumUsed; idx++, entry++) {
3027 			if (Z_TYPE_P(entry) == IS_UNDEF) continue;
3028 
3029 			zend_hash_next_index_insert_new(&out_hash, entry);
3030 			if (idx == iter_pos) {
3031 				if ((zend_long)idx != pos) {
3032 					zend_hash_iterators_update(in_hash, idx, pos);
3033 				}
3034 				iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos + 1);
3035 			}
3036 			pos++;
3037 		}
3038 
3039 		/* If hash for removed entries exists, go until offset+length and copy the entries to it */
3040 		if (removed != NULL) {
3041 			for ( ; pos < offset + length && idx < in_hash->nNumUsed; idx++, entry++) {
3042 				if (Z_TYPE_P(entry) == IS_UNDEF) continue;
3043 				pos++;
3044 				Z_TRY_ADDREF_P(entry);
3045 				zend_hash_next_index_insert_new(removed, entry);
3046 				zend_hash_packed_del_val(in_hash, entry);
3047 			}
3048 		} else { /* otherwise just skip those entries */
3049 			int pos2 = pos;
3050 
3051 			for ( ; pos2 < offset + length && idx < in_hash->nNumUsed; idx++, entry++) {
3052 				if (Z_TYPE_P(entry) == IS_UNDEF) continue;
3053 				pos2++;
3054 				zend_hash_packed_del_val(in_hash, entry);
3055 			}
3056 		}
3057 		iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos);
3058 
3059 		/* If there are entries to insert.. */
3060 		if (replace) {
3061 			ZEND_HASH_FOREACH_VAL(replace, entry) {
3062 				Z_TRY_ADDREF_P(entry);
3063 				zend_hash_next_index_insert_new(&out_hash, entry);
3064 				pos++;
3065 			} ZEND_HASH_FOREACH_END();
3066 		}
3067 
3068 		/* Copy the remaining input hash entries to the output hash */
3069 		entry = in_hash->arPacked + idx;
3070 		for ( ; idx < in_hash->nNumUsed ; idx++, entry++) {
3071 			if (Z_TYPE_P(entry) == IS_UNDEF) continue;
3072 			zend_hash_next_index_insert_new(&out_hash, entry);
3073 			if (idx == iter_pos) {
3074 				if ((zend_long)idx != pos) {
3075 					zend_hash_iterators_update(in_hash, idx, pos);
3076 				}
3077 				iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos + 1);
3078 			}
3079 			pos++;
3080 		}
3081 	} else {
3082 		Bucket *p = in_hash->arData;
3083 
3084 		/* Start at the beginning of the input hash and copy entries to output hash until offset is reached */
3085 		for (pos = 0, idx = 0; pos < offset && idx < in_hash->nNumUsed; idx++, p++) {
3086 			if (Z_TYPE(p->val) == IS_UNDEF) continue;
3087 			entry = &p->val;
3088 
3089 			/* Update output hash depending on key type */
3090 			if (p->key == NULL) {
3091 				zend_hash_next_index_insert_new(&out_hash, entry);
3092 			} else {
3093 				zend_hash_add_new(&out_hash, p->key, entry);
3094 			}
3095 			if (idx == iter_pos) {
3096 				if ((zend_long)idx != pos) {
3097 					zend_hash_iterators_update(in_hash, idx, pos);
3098 				}
3099 				iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos + 1);
3100 			}
3101 			pos++;
3102 		}
3103 
3104 		/* If hash for removed entries exists, go until offset+length and copy the entries to it */
3105 		if (removed != NULL) {
3106 			for ( ; pos < offset + length && idx < in_hash->nNumUsed; idx++, p++) {
3107 				if (Z_TYPE(p->val) == IS_UNDEF) continue;
3108 				pos++;
3109 				entry = &p->val;
3110 				Z_TRY_ADDREF_P(entry);
3111 				if (p->key == NULL) {
3112 					zend_hash_next_index_insert_new(removed, entry);
3113 				} else {
3114 					zend_hash_add_new(removed, p->key, entry);
3115 				}
3116 				zend_hash_del_bucket(in_hash, p);
3117 			}
3118 		} else { /* otherwise just skip those entries */
3119 			int pos2 = pos;
3120 
3121 			for ( ; pos2 < offset + length && idx < in_hash->nNumUsed; idx++, p++) {
3122 				if (Z_TYPE(p->val) == IS_UNDEF) continue;
3123 				pos2++;
3124 				zend_hash_del_bucket(in_hash, p);
3125 			}
3126 		}
3127 		iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos);
3128 
3129 		/* If there are entries to insert.. */
3130 		if (replace) {
3131 			ZEND_HASH_FOREACH_VAL(replace, entry) {
3132 				Z_TRY_ADDREF_P(entry);
3133 				zend_hash_next_index_insert_new(&out_hash, entry);
3134 				pos++;
3135 			} ZEND_HASH_FOREACH_END();
3136 		}
3137 
3138 		/* Copy the remaining input hash entries to the output hash */
3139 		for ( ; idx < in_hash->nNumUsed ; idx++, p++) {
3140 			if (Z_TYPE(p->val) == IS_UNDEF) continue;
3141 			entry = &p->val;
3142 			if (p->key == NULL) {
3143 				zend_hash_next_index_insert_new(&out_hash, entry);
3144 			} else {
3145 				zend_hash_add_new(&out_hash, p->key, entry);
3146 			}
3147 			if (idx == iter_pos) {
3148 				if ((zend_long)idx != pos) {
3149 					zend_hash_iterators_update(in_hash, idx, pos);
3150 				}
3151 				iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos + 1);
3152 			}
3153 			pos++;
3154 		}
3155 	}
3156 
3157 	/* replace HashTable data */
3158 	HT_SET_ITERATORS_COUNT(&out_hash, HT_ITERATORS_COUNT(in_hash));
3159 	HT_SET_ITERATORS_COUNT(in_hash, 0);
3160 	in_hash->pDestructor = NULL;
3161 	zend_hash_destroy(in_hash);
3162 
3163 	HT_FLAGS(in_hash)          = HT_FLAGS(&out_hash);
3164 	in_hash->nTableSize        = out_hash.nTableSize;
3165 	in_hash->nTableMask        = out_hash.nTableMask;
3166 	in_hash->nNumUsed          = out_hash.nNumUsed;
3167 	in_hash->nNumOfElements    = out_hash.nNumOfElements;
3168 	in_hash->nNextFreeElement  = out_hash.nNextFreeElement;
3169 	in_hash->arData            = out_hash.arData;
3170 	in_hash->pDestructor       = out_hash.pDestructor;
3171 
3172 	zend_hash_internal_pointer_reset(in_hash);
3173 }
3174 /* }}} */
3175 
3176 /* {{{ Pushes elements onto the end of the array */
3177 PHP_FUNCTION(array_push)
3178 {
3179 	zval   *args,		/* Function arguments array */
3180 		   *stack,		/* Input array */
3181 		    new_var;	/* Variable to be pushed */
3182 	int i,				/* Loop counter */
3183 		argc;			/* Number of function arguments */
3184 
3185 
3186 	ZEND_PARSE_PARAMETERS_START(1, -1)
3187 		Z_PARAM_ARRAY_EX(stack, 0, 1)
3188 		Z_PARAM_VARIADIC('+', args, argc)
3189 	ZEND_PARSE_PARAMETERS_END();
3190 
3191 	/* For each subsequent argument, make it a reference, increase refcount, and add it to the end of the array */
3192 	for (i = 0; i < argc; i++) {
3193 		ZVAL_COPY(&new_var, &args[i]);
3194 
3195 		if (zend_hash_next_index_insert(Z_ARRVAL_P(stack), &new_var) == NULL) {
3196 			Z_TRY_DELREF(new_var);
3197 			zend_throw_error(NULL, "Cannot add element to the array as the next element is already occupied");
3198 			RETURN_THROWS();
3199 		}
3200 	}
3201 
3202 	/* Clean up and return the number of values in the stack */
3203 	RETVAL_LONG(zend_hash_num_elements(Z_ARRVAL_P(stack)));
3204 }
3205 /* }}} */
3206 
3207 /* {{{ Pops an element off the end of the array */
3208 PHP_FUNCTION(array_pop)
3209 {
3210 	zval *stack,	/* Input stack */
3211 		 *val;		/* Value to be popped */
3212 	uint32_t idx;
3213 
3214 	ZEND_PARSE_PARAMETERS_START(1, 1)
3215 		Z_PARAM_ARRAY_EX(stack, 0, 1)
3216 	ZEND_PARSE_PARAMETERS_END();
3217 
3218 	if (zend_hash_num_elements(Z_ARRVAL_P(stack)) == 0) {
3219 		return;
3220 	}
3221 
3222 	if (HT_IS_PACKED(Z_ARRVAL_P(stack))) {
3223 		/* Get the last value and copy it into the return value */
3224 		idx = Z_ARRVAL_P(stack)->nNumUsed;
3225 		while (1) {
3226 			if (idx == 0) {
3227 				return;
3228 			}
3229 			idx--;
3230 			val = Z_ARRVAL_P(stack)->arPacked + idx;
3231 			if (Z_TYPE_P(val) != IS_UNDEF) {
3232 				break;
3233 			}
3234 		}
3235 		RETVAL_COPY_DEREF(val);
3236 
3237 		if (idx == (Z_ARRVAL_P(stack)->nNextFreeElement - 1)) {
3238 			Z_ARRVAL_P(stack)->nNextFreeElement = Z_ARRVAL_P(stack)->nNextFreeElement - 1;
3239 		}
3240 
3241 		/* Delete the last value */
3242 		zend_hash_packed_del_val(Z_ARRVAL_P(stack), val);
3243 	} else {
3244 		Bucket *p;
3245 
3246 		/* Get the last value and copy it into the return value */
3247 		idx = Z_ARRVAL_P(stack)->nNumUsed;
3248 		while (1) {
3249 			if (idx == 0) {
3250 				return;
3251 			}
3252 			idx--;
3253 			p = Z_ARRVAL_P(stack)->arData + idx;
3254 			val = &p->val;
3255 			if (Z_TYPE_P(val) != IS_UNDEF) {
3256 				break;
3257 			}
3258 		}
3259 		RETVAL_COPY_DEREF(val);
3260 
3261 		if (!p->key && (zend_long)p->h == (Z_ARRVAL_P(stack)->nNextFreeElement - 1)) {
3262 			Z_ARRVAL_P(stack)->nNextFreeElement = Z_ARRVAL_P(stack)->nNextFreeElement - 1;
3263 		}
3264 
3265 		/* Delete the last value */
3266 		zend_hash_del_bucket(Z_ARRVAL_P(stack), p);
3267 	}
3268 	zend_hash_internal_pointer_reset(Z_ARRVAL_P(stack));
3269 }
3270 /* }}} */
3271 
3272 /* {{{ Pops an element off the beginning of the array */
3273 PHP_FUNCTION(array_shift)
3274 {
3275 	zval *stack,	/* Input stack */
3276 		 *val;		/* Value to be popped */
3277 	uint32_t idx;
3278 
3279 	ZEND_PARSE_PARAMETERS_START(1, 1)
3280 		Z_PARAM_ARRAY_EX(stack, 0, 1)
3281 	ZEND_PARSE_PARAMETERS_END();
3282 
3283 	if (zend_hash_num_elements(Z_ARRVAL_P(stack)) == 0) {
3284 		return;
3285 	}
3286 
3287 	/* re-index like it did before */
3288 	if (HT_IS_PACKED(