1/*
2   +----------------------------------------------------------------------+
3   | Zend Engine                                                          |
4   +----------------------------------------------------------------------+
5   | Copyright (c) 1998-2016 Zend Technologies Ltd. (http://www.zend.com) |
6   +----------------------------------------------------------------------+
7   | This source file is subject to version 2.00 of the Zend license,     |
8   | that is bundled with this package in the file LICENSE, and is        |
9   | available through the world-wide-web at the following url:           |
10   | http://www.zend.com/license/2_00.txt.                                |
11   | If you did not receive a copy of the Zend license and are unable to  |
12   | obtain it through the world-wide-web, please send a note to          |
13   | license@zend.com so we can mail you a copy immediately.              |
14   +----------------------------------------------------------------------+
15   | Authors: Nikita Popov <nikic@php.net>                                |
16   |          Bob Weinand <bobwei9@hotmail.com>                           |
17   +----------------------------------------------------------------------+
18*/
19
20/* $Id$ */
21
22#include "zend.h"
23#include "zend_API.h"
24#include "zend_interfaces.h"
25#include "zend_exceptions.h"
26#include "zend_generators.h"
27
28ZEND_API zend_class_entry *zend_ce_generator;
29ZEND_API zend_class_entry *zend_ce_ClosedGeneratorException;
30static zend_object_handlers zend_generator_handlers;
31
32static zend_object *zend_generator_create(zend_class_entry *class_type);
33
34static void zend_restore_call_stack(zend_generator *generator) /* {{{ */
35{
36	zend_execute_data *call, *new_call, *prev_call = NULL;
37
38	call = generator->frozen_call_stack;
39	do {
40		new_call = zend_vm_stack_push_call_frame(
41			(ZEND_CALL_INFO(call) & ~ZEND_CALL_ALLOCATED),
42			call->func,
43			ZEND_CALL_NUM_ARGS(call),
44			(Z_TYPE(call->This) == IS_UNDEF) ?
45				(zend_class_entry*)Z_OBJ(call->This) : NULL,
46			(Z_TYPE(call->This) != IS_UNDEF) ?
47				Z_OBJ(call->This) : NULL);
48		memcpy(((zval*)new_call) + ZEND_CALL_FRAME_SLOT, ((zval*)call) + ZEND_CALL_FRAME_SLOT, ZEND_CALL_NUM_ARGS(call) * sizeof(zval));
49		new_call->prev_execute_data = prev_call;
50		prev_call = new_call;
51
52		call = call->prev_execute_data;
53	} while (call);
54	generator->execute_data->call = prev_call;
55	efree(generator->frozen_call_stack);
56	generator->frozen_call_stack = NULL;
57}
58/* }}} */
59
60static zend_execute_data* zend_freeze_call_stack(zend_execute_data *execute_data) /* {{{ */
61{
62	size_t used_stack;
63	zend_execute_data *call, *new_call, *prev_call = NULL;
64	zval *stack;
65
66	/* calculate required stack size */
67	used_stack = 0;
68	call = EX(call);
69	do {
70		used_stack += ZEND_CALL_FRAME_SLOT + ZEND_CALL_NUM_ARGS(call);
71		call = call->prev_execute_data;
72	} while (call);
73
74	stack = emalloc(used_stack * sizeof(zval));
75
76	/* save stack, linking frames in reverse order */
77	call = EX(call);
78	do {
79		size_t frame_size = ZEND_CALL_FRAME_SLOT + ZEND_CALL_NUM_ARGS(call);
80
81		new_call = (zend_execute_data*)(stack + used_stack - frame_size);
82		memcpy(new_call, call, frame_size * sizeof(zval));
83		used_stack -= frame_size;
84		new_call->prev_execute_data = prev_call;
85		prev_call = new_call;
86
87		new_call = call->prev_execute_data;
88		zend_vm_stack_free_call_frame(call);
89		call = new_call;
90	} while (call);
91
92	execute_data->call = NULL;
93	ZEND_ASSERT(prev_call == (zend_execute_data*)stack);
94
95	return prev_call;
96}
97/* }}} */
98
99static void zend_generator_cleanup_unfinished_execution(
100		zend_generator *generator, uint32_t catch_op_num) /* {{{ */
101{
102	zend_execute_data *execute_data = generator->execute_data;
103
104	if (execute_data->opline != execute_data->func->op_array.opcodes) {
105		/* -1 required because we want the last run opcode, not the next to-be-run one. */
106		uint32_t op_num = execute_data->opline - execute_data->func->op_array.opcodes - 1;
107
108		if (UNEXPECTED(generator->frozen_call_stack)) {
109			zend_restore_call_stack(generator);
110		}
111		zend_cleanup_unfinished_execution(execute_data, op_num, 0);
112	}
113}
114/* }}} */
115
116ZEND_API void zend_generator_close(zend_generator *generator, zend_bool finished_execution) /* {{{ */
117{
118	if (EXPECTED(generator->execute_data)) {
119		zend_execute_data *execute_data = generator->execute_data;
120
121		if (EX_CALL_INFO() & ZEND_CALL_HAS_SYMBOL_TABLE) {
122			zend_clean_and_cache_symbol_table(execute_data->symbol_table);
123		}
124		/* always free the CV's, in the symtable are only not-free'd IS_INDIRECT's */
125		zend_free_compiled_variables(execute_data);
126
127		if (EX_CALL_INFO() & ZEND_CALL_RELEASE_THIS) {
128			OBJ_RELEASE(Z_OBJ(execute_data->This));
129		}
130
131		/* A fatal error / die occurred during the generator execution.
132		 * Trying to clean up the stack may not be safe in this case. */
133		if (UNEXPECTED(CG(unclean_shutdown))) {
134			generator->execute_data = NULL;
135			return;
136		}
137
138		zend_vm_stack_free_extra_args(generator->execute_data);
139
140		/* Some cleanups are only necessary if the generator was closed
141		 * before it could finish execution (reach a return statement). */
142		if (UNEXPECTED(!finished_execution)) {
143			zend_generator_cleanup_unfinished_execution(generator, 0);
144		}
145
146		/* Free closure object */
147		if (EX_CALL_INFO() & ZEND_CALL_CLOSURE) {
148			OBJ_RELEASE((zend_object *) EX(func)->common.prototype);
149		}
150
151		/* Free GC buffer. GC for closed generators doesn't need an allocated buffer */
152		if (generator->gc_buffer) {
153			efree(generator->gc_buffer);
154			generator->gc_buffer = NULL;
155		}
156
157		efree(generator->execute_data);
158		generator->execute_data = NULL;
159	}
160}
161/* }}} */
162
163static zend_generator *zend_generator_get_child(zend_generator_node *node, zend_generator *leaf);
164
165static void zend_generator_dtor_storage(zend_object *object) /* {{{ */
166{
167	zend_generator *generator = (zend_generator*) object;
168	zend_execute_data *ex = generator->execute_data;
169	uint32_t op_num, finally_op_num, finally_op_end;
170	int i;
171
172	/* leave yield from mode to properly allow finally execution */
173	if (UNEXPECTED(Z_TYPE(generator->values) != IS_UNDEF)) {
174		zval_ptr_dtor(&generator->values);
175		ZVAL_UNDEF(&generator->values);
176	}
177
178	if (EXPECTED(generator->node.children == 0)) {
179		zend_generator *root = generator->node.ptr.root, *next;
180		while (UNEXPECTED(root != generator)) {
181			next = zend_generator_get_child(&root->node, generator);
182			OBJ_RELEASE(&root->std);
183			root = next;
184		}
185		generator->node.parent = NULL;
186	}
187
188	if (EXPECTED(!ex) || EXPECTED(!(ex->func->op_array.fn_flags & ZEND_ACC_HAS_FINALLY_BLOCK))) {
189		return;
190	}
191
192	/* -1 required because we want the last run opcode, not the
193	 * next to-be-run one. */
194	op_num = ex->opline - ex->func->op_array.opcodes - 1;
195
196	/* Find next finally block */
197	finally_op_num = 0;
198	finally_op_end = 0;
199	for (i = 0; i < ex->func->op_array.last_try_catch; i++) {
200		zend_try_catch_element *try_catch = &ex->func->op_array.try_catch_array[i];
201
202		if (op_num < try_catch->try_op) {
203			break;
204		}
205
206		if (op_num < try_catch->finally_op) {
207			finally_op_num = try_catch->finally_op;
208			finally_op_end = try_catch->finally_end;
209		}
210	}
211
212	/* If a finally block was found we jump directly to it and
213	 * resume the generator. */
214	if (finally_op_num) {
215		zval *fast_call;
216
217		zend_generator_cleanup_unfinished_execution(generator, finally_op_num);
218
219		fast_call = ZEND_CALL_VAR(ex, ex->func->op_array.opcodes[finally_op_end].op1.var);
220		Z_OBJ_P(fast_call) = EG(exception);
221		EG(exception) = NULL;
222		fast_call->u2.lineno = (uint32_t)-1;
223
224		ex->opline = &ex->func->op_array.opcodes[finally_op_num];
225		generator->flags |= ZEND_GENERATOR_FORCED_CLOSE;
226		zend_generator_resume(generator);
227	}
228}
229/* }}} */
230
231static void zend_generator_free_storage(zend_object *object) /* {{{ */
232{
233	zend_generator *generator = (zend_generator*) object;
234
235	zend_generator_close(generator, 0);
236
237	/* we can't immediately free them in zend_generator_close() else yield from won't be able to fetch it */
238	zval_ptr_dtor(&generator->value);
239	zval_ptr_dtor(&generator->key);
240
241	if (EXPECTED(!Z_ISUNDEF(generator->retval))) {
242		zval_ptr_dtor(&generator->retval);
243	}
244
245	if (UNEXPECTED(generator->node.children > 4)) {
246		zend_hash_destroy(&generator->node.child.ht);
247	}
248
249	zend_object_std_dtor(&generator->std);
250
251	if (generator->iterator) {
252		zend_iterator_dtor(generator->iterator);
253	}
254}
255/* }}} */
256
257static uint32_t calc_gc_buffer_size(zend_generator *generator) /* {{{ */
258{
259	uint32_t size = 4; /* value, key, retval, values */
260	if (generator->execute_data) {
261		zend_execute_data *execute_data = generator->execute_data;
262		zend_op_array *op_array = &EX(func)->op_array;
263
264		/* Compiled variables */
265		if (!(EX_CALL_INFO() & ZEND_CALL_HAS_SYMBOL_TABLE)) {
266			size += op_array->last_var;
267		}
268		/* Extra args */
269		if (EX_CALL_INFO() & ZEND_CALL_FREE_EXTRA_ARGS) {
270			size += EX_NUM_ARGS() - op_array->num_args;
271		}
272		size += Z_TYPE(execute_data->This) == IS_OBJECT; /* $this */
273		size += (EX_CALL_INFO() & ZEND_CALL_CLOSURE) != 0; /* Closure object */
274
275		/* Yield from root references */
276		if (generator->node.children == 0) {
277			zend_generator *child = generator, *root = generator->node.ptr.root;
278			while (root != child) {
279				child = child->node.parent;
280				size++;
281			}
282		}
283	}
284	return size;
285}
286/* }}} */
287
288static HashTable *zend_generator_get_gc(zval *object, zval **table, int *n) /* {{{ */
289{
290	zend_generator *generator = (zend_generator*) Z_OBJ_P(object);
291	zend_execute_data *execute_data = generator->execute_data;
292	zend_op_array *op_array;
293	zval *gc_buffer;
294	uint32_t gc_buffer_size;
295
296	if (!execute_data) {
297		/* If the generator has been closed, it can only hold on to three values: The value, key
298		 * and retval. These three zvals are stored sequentially starting at &generator->value. */
299		*table = &generator->value;
300		*n = 3;
301		return NULL;
302	}
303
304	op_array = &EX(func)->op_array;
305	gc_buffer_size = calc_gc_buffer_size(generator);
306	if (generator->gc_buffer_size < gc_buffer_size) {
307		generator->gc_buffer = safe_erealloc(generator->gc_buffer, sizeof(zval), gc_buffer_size, 0);
308		generator->gc_buffer_size = gc_buffer_size;
309	}
310
311	*n = gc_buffer_size;
312	*table = gc_buffer = generator->gc_buffer;
313
314	ZVAL_COPY_VALUE(gc_buffer++, &generator->value);
315	ZVAL_COPY_VALUE(gc_buffer++, &generator->key);
316	ZVAL_COPY_VALUE(gc_buffer++, &generator->retval);
317	ZVAL_COPY_VALUE(gc_buffer++, &generator->values);
318
319	if (!(EX_CALL_INFO() & ZEND_CALL_HAS_SYMBOL_TABLE)) {
320		uint32_t i, num_cvs = EX(func)->op_array.last_var;
321		for (i = 0; i < num_cvs; i++) {
322			ZVAL_COPY_VALUE(gc_buffer++, EX_VAR_NUM(i));
323		}
324	}
325
326	if (EX_CALL_INFO() & ZEND_CALL_FREE_EXTRA_ARGS) {
327		zval *zv = EX_VAR_NUM(op_array->last_var + op_array->T);
328		zval *end = zv + (EX_NUM_ARGS() - op_array->num_args);
329		while (zv != end) {
330			ZVAL_COPY_VALUE(gc_buffer++, zv++);
331		}
332	}
333
334	if (Z_TYPE(execute_data->This) == IS_OBJECT) {
335		ZVAL_OBJ(gc_buffer++, Z_OBJ(execute_data->This));
336	}
337	if (EX_CALL_INFO() & ZEND_CALL_CLOSURE) {
338		ZVAL_OBJ(gc_buffer++, (zend_object *) EX(func)->common.prototype);
339	}
340
341	if (generator->node.children == 0) {
342		zend_generator *child = generator, *root = generator->node.ptr.root;
343		while (root != child) {
344			child = child->node.parent;
345			ZVAL_OBJ(gc_buffer++, &child->std);
346		}
347	}
348
349	if (EX_CALL_INFO() & ZEND_CALL_HAS_SYMBOL_TABLE) {
350		return execute_data->symbol_table;
351	} else {
352		return NULL;
353	}
354}
355/* }}} */
356
357static zend_object *zend_generator_create(zend_class_entry *class_type) /* {{{ */
358{
359	zend_generator *generator;
360
361	generator = emalloc(sizeof(zend_generator));
362	memset(generator, 0, sizeof(zend_generator));
363
364	/* The key will be incremented on first use, so it'll start at 0 */
365	generator->largest_used_integer_key = -1;
366
367	ZVAL_UNDEF(&generator->retval);
368	ZVAL_UNDEF(&generator->values);
369
370	/* By default we have a tree of only one node */
371	generator->node.parent = NULL;
372	generator->node.children = 0;
373	generator->node.ptr.root = generator;
374
375	zend_object_std_init(&generator->std, class_type);
376	generator->std.handlers = &zend_generator_handlers;
377
378	return (zend_object*)generator;
379}
380/* }}} */
381
382static ZEND_COLD zend_function *zend_generator_get_constructor(zend_object *object) /* {{{ */
383{
384	zend_throw_error(NULL, "The \"Generator\" class is reserved for internal use and cannot be manually instantiated");
385
386	return NULL;
387}
388/* }}} */
389
390ZEND_API zend_execute_data *zend_generator_check_placeholder_frame(zend_execute_data *ptr)
391{
392	if (!ptr->func && Z_TYPE(ptr->This) == IS_OBJECT) {
393		if (Z_OBJCE(ptr->This) == zend_ce_generator) {
394			zend_generator *generator = (zend_generator *) Z_OBJ(ptr->This);
395			zend_generator *root = (generator->node.children < 1 ? generator : generator->node.ptr.leaf)->node.ptr.root;
396			zend_execute_data *prev = ptr->prev_execute_data;
397			if (generator->node.parent != root) {
398				do {
399					generator->execute_data->prev_execute_data = prev;
400					prev = generator->execute_data;
401					generator = generator->node.parent;
402				} while (generator->node.parent != root);
403			}
404			generator->execute_data->prev_execute_data = prev;
405			ptr = generator->execute_data;
406		}
407	}
408	return ptr;
409}
410
411static void zend_generator_throw_exception(zend_generator *generator, zval *exception)
412{
413	zend_execute_data *original_execute_data = EG(current_execute_data);
414
415	/* if we don't stop an array/iterator yield from, the exception will only reach the generator after the values were all iterated over */
416	if (UNEXPECTED(Z_TYPE(generator->values) != IS_UNDEF)) {
417		zval_ptr_dtor(&generator->values);
418		ZVAL_UNDEF(&generator->values);
419	}
420
421	/* Throw the exception in the context of the generator. Decrementing the opline
422	 * to pretend the exception happened during the YIELD opcode. */
423	EG(current_execute_data) = generator->execute_data;
424	generator->execute_data->opline--;
425	if (exception) {
426		zend_throw_exception_object(exception);
427	} else {
428		zend_throw_exception_internal(NULL);
429	}
430	generator->execute_data->opline++;
431	EG(current_execute_data) = original_execute_data;
432}
433
434static zend_generator *zend_generator_get_child(zend_generator_node *node, zend_generator *leaf)
435{
436	switch (node->children) {
437		case 0:
438			return NULL;
439		case 1:
440			return node->child.array[0].child;
441
442#define ZEND_GEN_GET_CHILD(x) \
443			if (node->child.array[x].leaf == leaf) { \
444				return node->child.array[x].child; \
445			}
446		case 4:
447			ZEND_GEN_GET_CHILD(3)
448		case 3:
449			ZEND_GEN_GET_CHILD(2)
450		case 2:
451			ZEND_GEN_GET_CHILD(1)
452			ZEND_GEN_GET_CHILD(0)
453			ZEND_ASSERT(0); // we never should have no matching child
454	}
455
456	return zend_hash_index_find_ptr(&node->child.ht, (zend_ulong) leaf);
457}
458
459static zend_generator_node *zend_generator_search_multi_children_node(zend_generator_node *node)
460{
461	while (node->children == 1) {
462		node = &node->child.array[0].child->node;
463	}
464	return node->children > 1 ? node : NULL;
465}
466
467static void zend_generator_add_single_child(zend_generator_node *node, zend_generator *child, zend_generator *leaf)
468{
469	if (node->children < 4) {
470		node->child.array[node->children].leaf = leaf;
471		node->child.array[node->children].child = child;
472	} else if (node->children > 4) {
473		zend_hash_index_add_ptr(&node->child.ht, (zend_ulong) leaf, child);
474	} else {
475		struct {
476			zend_generator *leaf;
477			zend_generator *child;
478		} array[4];
479		int i;
480
481		memcpy(&array, &node->child.array, sizeof(array));
482		zend_hash_init(&node->child.ht, 5, sigh, NULL, 0);
483		for (i = 0; i < 4; i++) {
484			zend_hash_index_add_ptr(&node->child.ht, (zend_ulong) array[i].leaf, array[i].child);
485		}
486		zend_hash_index_add_ptr(&node->child.ht, (zend_ulong) leaf, child);
487	}
488
489	node->children++;
490}
491
492static void zend_generator_merge_child_nodes(zend_generator_node *dest, zend_generator_node *src, zend_generator *child)
493{
494	if (src->children <= 4) {
495		int i = src->children;
496		while (i--) {
497			zend_generator_add_single_child(dest, child, src->child.array[i].leaf);
498		}
499	} else {
500		zend_ulong leaf;
501		ZEND_HASH_FOREACH_NUM_KEY(&src->child.ht, leaf) {
502			zend_generator_add_single_child(dest, child, (zend_generator *) leaf);
503		} ZEND_HASH_FOREACH_END();
504	}
505}
506
507/* Make attention so that the root of each subtree of the Generators tree is referenced once per leaf */
508static void zend_generator_add_child(zend_generator *generator, zend_generator *child)
509{
510	zend_generator *leaf = child->node.children ? child->node.ptr.leaf : child;
511	zend_generator_node *multi_children_node;
512	zend_bool was_leaf = generator->node.children == 0;
513
514	if (was_leaf) {
515		zend_generator *next = generator->node.parent;
516		leaf->node.ptr.root = generator->node.ptr.root;
517		++GC_REFCOUNT(&generator->std); /* we need to increment the generator refcount here as it became integrated into the tree (no leaf), but we must not increment the refcount of the *whole* path in tree */
518		generator->node.ptr.leaf = leaf;
519
520		while (next) {
521			if (next->node.children > 1) {
522				if (next->node.children > 4) {
523					zend_generator *child = zend_hash_index_find_ptr(&next->node.child.ht, (zend_ulong) generator);
524					zend_hash_index_del(&next->node.child.ht, (zend_ulong) generator);
525					zend_hash_index_add_ptr(&next->node.child.ht, (zend_ulong) leaf, child);
526				} else {
527					switch (next->node.children) {
528#define ZEND_GEN_UPDATE_CHILD(x) \
529							if (next->node.child.array[x].leaf == generator) { \
530								next->node.child.array[x].leaf = leaf; \
531								break; \
532							}
533						case 4:
534							ZEND_GEN_UPDATE_CHILD(3)
535						case 3:
536							ZEND_GEN_UPDATE_CHILD(2)
537						case 2:
538							ZEND_GEN_UPDATE_CHILD(1)
539							ZEND_GEN_UPDATE_CHILD(0)
540							ZEND_ASSERT(0); // we never should have no matching child
541					}
542				}
543			}
544
545			next->node.ptr.leaf = leaf;
546			next = next->node.parent;
547		}
548
549		zend_generator_add_single_child(&generator->node, child, leaf);
550	} else if (generator->node.children == 1) {
551		multi_children_node = zend_generator_search_multi_children_node(&generator->node);
552		if (multi_children_node) {
553			generator->node.children = 0;
554			zend_generator_merge_child_nodes(&generator->node, multi_children_node, generator->node.child.array[0].child);
555		}
556	}
557
558	if (!was_leaf) {
559		multi_children_node = zend_generator_search_multi_children_node(&child->node);
560	} else {
561		multi_children_node = (zend_generator_node *) 0x1;
562	}
563
564	{
565		zend_generator *parent = generator->node.parent, *cur = generator;
566
567		if (multi_children_node > (zend_generator_node *) 0x1) {
568			zend_generator_merge_child_nodes(&generator->node, multi_children_node, child);
569		} else {
570			zend_generator_add_single_child(&generator->node, child, leaf);
571		}
572		while (parent) {
573			if (parent->node.children > 1) {
574				if (multi_children_node == (zend_generator_node *) 0x1) {
575					multi_children_node = zend_generator_search_multi_children_node(&child->node);
576				}
577				if (multi_children_node) {
578					zend_generator_merge_child_nodes(&parent->node, multi_children_node, cur);
579				} else {
580					zend_generator_add_single_child(&parent->node, cur, leaf);
581				}
582			}
583			cur = parent;
584			parent = parent->node.parent;
585		}
586	}
587}
588
589void zend_generator_yield_from(zend_generator *generator, zend_generator *from)
590{
591	zend_generator_add_child(from, generator);
592
593	generator->node.parent = from;
594	zend_generator_get_current(generator);
595	--GC_REFCOUNT(&from->std);
596}
597
598ZEND_API zend_generator *zend_generator_update_current(zend_generator *generator, zend_generator *leaf)
599{
600	zend_generator *old_root, *root = leaf->node.ptr.root;
601
602	/* generator at the root had stopped */
603	if (root != generator) {
604		old_root = root;
605		root = zend_generator_get_child(&root->node, leaf);
606	} else {
607		old_root = NULL;
608	}
609
610	while (!root->execute_data && root != generator) {
611		OBJ_RELEASE(&old_root->std);
612		old_root = root;
613
614		root = zend_generator_get_child(&root->node, leaf);
615	}
616
617	if (root->node.parent) {
618		if (root->node.parent->execute_data == NULL) {
619			if (EXPECTED(EG(exception) == NULL)) {
620				zend_op *yield_from = (zend_op *) root->execute_data->opline - 1;
621
622				if (yield_from->opcode == ZEND_YIELD_FROM) {
623					if (Z_ISUNDEF(root->node.parent->retval)) {
624						/* Throw the exception in the context of the generator */
625						zend_execute_data *original_execute_data = EG(current_execute_data);
626						EG(current_execute_data) = root->execute_data;
627
628						if (root == generator) {
629							root->execute_data->prev_execute_data = original_execute_data;
630						} else {
631							root->execute_data->prev_execute_data = &generator->execute_fake;
632							generator->execute_fake.prev_execute_data = original_execute_data;
633						}
634
635						zend_throw_exception(zend_ce_ClosedGeneratorException, "Generator yielded from aborted, no return value available", 0);
636
637						EG(current_execute_data) = original_execute_data;
638					} else {
639						zval_ptr_dtor(&root->value);
640						ZVAL_COPY(&root->value, &root->node.parent->value);
641						ZVAL_COPY(ZEND_CALL_VAR(root->execute_data, yield_from->result.var), &root->node.parent->retval);
642					}
643				}
644			}
645
646			root->node.parent = NULL;
647		} else {
648			do {
649				root = root->node.parent;
650				++GC_REFCOUNT(&root->std);
651			} while (root->node.parent);
652		}
653	}
654
655	if (old_root) {
656		OBJ_RELEASE(&old_root->std);
657	}
658
659	return leaf->node.ptr.root = root;
660}
661
662static int zend_generator_get_next_delegated_value(zend_generator *generator) /* {{{ */
663{
664	zval *value;
665	if (Z_TYPE(generator->values) == IS_ARRAY) {
666		HashTable *ht = Z_ARR(generator->values);
667		HashPosition pos = Z_FE_POS(generator->values);
668
669		Bucket *p;
670		do {
671			if (UNEXPECTED(pos >= ht->nNumUsed)) {
672				/* Reached end of array */
673				goto failure;
674			}
675
676			p = &ht->arData[pos];
677			value = &p->val;
678			if (Z_TYPE_P(value) == IS_INDIRECT) {
679				value = Z_INDIRECT_P(value);
680			}
681			pos++;
682		} while (Z_ISUNDEF_P(value));
683
684		zval_ptr_dtor(&generator->value);
685		ZVAL_COPY(&generator->value, value);
686
687		zval_ptr_dtor(&generator->key);
688		if (p->key) {
689			ZVAL_STR_COPY(&generator->key, p->key);
690		} else {
691			ZVAL_LONG(&generator->key, p->h);
692		}
693
694		Z_FE_POS(generator->values) = pos;
695	} else {
696		zend_object_iterator *iter = (zend_object_iterator *) Z_OBJ(generator->values);
697
698		if (iter->index++ > 0) {
699			iter->funcs->move_forward(iter);
700			if (UNEXPECTED(EG(exception) != NULL)) {
701				goto exception;
702			}
703		}
704
705		if (iter->funcs->valid(iter) == FAILURE) {
706			/* reached end of iteration */
707			goto failure;
708		}
709
710		value = iter->funcs->get_current_data(iter);
711		if (UNEXPECTED(EG(exception) != NULL)) {
712			goto exception;
713		} else if (UNEXPECTED(!value)) {
714			goto failure;
715		}
716
717		zval_ptr_dtor(&generator->value);
718		ZVAL_COPY(&generator->value, value);
719
720		zval_ptr_dtor(&generator->key);
721		if (iter->funcs->get_current_key) {
722			iter->funcs->get_current_key(iter, &generator->key);
723			if (UNEXPECTED(EG(exception) != NULL)) {
724				ZVAL_UNDEF(&generator->key);
725				goto exception;
726			}
727		} else {
728			ZVAL_LONG(&generator->key, iter->index);
729		}
730	}
731	return SUCCESS;
732
733exception: {
734		zend_execute_data *ex = EG(current_execute_data);
735		EG(current_execute_data) = generator->execute_data;
736		zend_throw_exception_internal(NULL);
737		EG(current_execute_data) = ex;
738	}
739
740failure:
741	zval_ptr_dtor(&generator->values);
742	ZVAL_UNDEF(&generator->values);
743	return FAILURE;
744}
745/* }}} */
746
747ZEND_API void zend_generator_resume(zend_generator *orig_generator) /* {{{ */
748{
749	zend_generator *generator;
750
751	/* The generator is already closed, thus can't resume */
752	if (UNEXPECTED(!orig_generator->execute_data)) {
753		return;
754	}
755
756	generator = zend_generator_get_current(orig_generator);
757
758try_again:
759	if (generator->flags & ZEND_GENERATOR_CURRENTLY_RUNNING) {
760		zend_throw_error(NULL, "Cannot resume an already running generator");
761		return;
762	}
763
764	if (UNEXPECTED((orig_generator->flags & ZEND_GENERATOR_DO_INIT) != 0 && !Z_ISUNDEF(generator->value))) {
765		/* We must not advance Generator if we yield from a Generator being currently run */
766		return;
767	}
768
769	if (UNEXPECTED(!Z_ISUNDEF(generator->values))) {
770		if (EXPECTED(zend_generator_get_next_delegated_value(generator) == SUCCESS)) {
771			return;
772		}
773		/* If there are no more deletegated values, resume the generator
774		 * after the "yield from" expression. */
775	}
776
777	/* Drop the AT_FIRST_YIELD flag */
778	orig_generator->flags &= ~ZEND_GENERATOR_AT_FIRST_YIELD;
779
780	{
781		/* Backup executor globals */
782		zend_execute_data *original_execute_data = EG(current_execute_data);
783
784		/* Set executor globals */
785		EG(current_execute_data) = generator->execute_data;
786
787		/* We want the backtrace to look as if the generator function was
788		 * called from whatever method we are current running (e.g. next()).
789		 * So we have to link generator call frame with caller call frame. */
790		if (generator == orig_generator) {
791			generator->execute_data->prev_execute_data = original_execute_data;
792		} else {
793			/* We need some execute_data placeholder in stacktrace to be replaced
794			 * by the real stack trace when needed */
795			generator->execute_data->prev_execute_data = &orig_generator->execute_fake;
796			orig_generator->execute_fake.prev_execute_data = original_execute_data;
797		}
798
799		if (UNEXPECTED(generator->frozen_call_stack)) {
800			/* Restore frozen call-stack */
801			zend_restore_call_stack(generator);
802		}
803
804		/* Resume execution */
805		generator->flags |= ZEND_GENERATOR_CURRENTLY_RUNNING;
806		zend_execute_ex(generator->execute_data);
807		generator->flags &= ~ZEND_GENERATOR_CURRENTLY_RUNNING;
808
809		generator->frozen_call_stack = NULL;
810		if (EXPECTED(generator->execute_data) &&
811		    UNEXPECTED(generator->execute_data->call)) {
812			/* Frize call-stack */
813			generator->frozen_call_stack = zend_freeze_call_stack(generator->execute_data);
814		}
815
816		/* Restore executor globals */
817		EG(current_execute_data) = original_execute_data;
818
819		/* If an exception was thrown in the generator we have to internally
820		 * rethrow it in the parent scope.
821		 * In case we did yield from, the Exception must be rethrown into
822		 * its calling frame (see above in if (check_yield_from). */
823		if (UNEXPECTED(EG(exception) != NULL)) {
824			if (generator == orig_generator) {
825				zend_generator_close(generator, 0);
826				zend_throw_exception_internal(NULL);
827			} else {
828				generator = zend_generator_get_current(orig_generator);
829				zend_generator_throw_exception(generator, NULL);
830				goto try_again;
831			}
832		}
833
834		/* yield from was used, try another resume. */
835		if (UNEXPECTED((generator != orig_generator && !Z_ISUNDEF(generator->retval)) || (generator->execute_data && (generator->execute_data->opline - 1)->opcode == ZEND_YIELD_FROM))) {
836			generator = zend_generator_get_current(orig_generator);
837			goto try_again;
838		}
839	}
840}
841/* }}} */
842
843static inline void zend_generator_ensure_initialized(zend_generator *generator) /* {{{ */
844{
845	if (UNEXPECTED(Z_TYPE(generator->value) == IS_UNDEF) && EXPECTED(generator->execute_data) && EXPECTED(generator->node.parent == NULL)) {
846		generator->flags |= ZEND_GENERATOR_DO_INIT;
847		zend_generator_resume(generator);
848		generator->flags &= ~ZEND_GENERATOR_DO_INIT;
849		generator->flags |= ZEND_GENERATOR_AT_FIRST_YIELD;
850	}
851}
852/* }}} */
853
854static inline void zend_generator_rewind(zend_generator *generator) /* {{{ */
855{
856	zend_generator_ensure_initialized(generator);
857
858	if (!(generator->flags & ZEND_GENERATOR_AT_FIRST_YIELD)) {
859		zend_throw_exception(NULL, "Cannot rewind a generator that was already run", 0);
860	}
861}
862/* }}} */
863
864/* {{{ proto void Generator::rewind()
865 * Rewind the generator */
866ZEND_METHOD(Generator, rewind)
867{
868	zend_generator *generator;
869
870	if (zend_parse_parameters_none() == FAILURE) {
871		return;
872	}
873
874	generator = (zend_generator *) Z_OBJ_P(getThis());
875
876	zend_generator_rewind(generator);
877}
878/* }}} */
879
880/* {{{ proto bool Generator::valid()
881 * Check whether the generator is valid */
882ZEND_METHOD(Generator, valid)
883{
884	zend_generator *generator;
885
886	if (zend_parse_parameters_none() == FAILURE) {
887		return;
888	}
889
890	generator = (zend_generator *) Z_OBJ_P(getThis());
891
892	zend_generator_ensure_initialized(generator);
893
894	zend_generator_get_current(generator);
895
896	RETURN_BOOL(EXPECTED(generator->execute_data != NULL));
897}
898/* }}} */
899
900/* {{{ proto mixed Generator::current()
901 * Get the current value */
902ZEND_METHOD(Generator, current)
903{
904	zend_generator *generator, *root;
905
906	if (zend_parse_parameters_none() == FAILURE) {
907		return;
908	}
909
910	generator = (zend_generator *) Z_OBJ_P(getThis());
911
912	zend_generator_ensure_initialized(generator);
913
914	root = zend_generator_get_current(generator);
915	if (EXPECTED(generator->execute_data != NULL && Z_TYPE(root->value) != IS_UNDEF)) {
916		zval *value = &root->value;
917
918		ZVAL_DEREF(value);
919		ZVAL_COPY(return_value, value);
920	}
921}
922/* }}} */
923
924/* {{{ proto mixed Generator::key()
925 * Get the current key */
926ZEND_METHOD(Generator, key)
927{
928	zend_generator *generator, *root;
929
930	if (zend_parse_parameters_none() == FAILURE) {
931		return;
932	}
933
934	generator = (zend_generator *) Z_OBJ_P(getThis());
935
936	zend_generator_ensure_initialized(generator);
937
938	root = zend_generator_get_current(generator);
939	if (EXPECTED(generator->execute_data != NULL && Z_TYPE(root->key) != IS_UNDEF)) {
940		zval *key = &root->key;
941
942		ZVAL_DEREF(key);
943		ZVAL_COPY(return_value, key);
944	}
945}
946/* }}} */
947
948/* {{{ proto void Generator::next()
949 * Advances the generator */
950ZEND_METHOD(Generator, next)
951{
952	zend_generator *generator;
953
954	if (zend_parse_parameters_none() == FAILURE) {
955		return;
956	}
957
958	generator = (zend_generator *) Z_OBJ_P(getThis());
959
960	zend_generator_ensure_initialized(generator);
961
962	zend_generator_resume(generator);
963}
964/* }}} */
965
966/* {{{ proto mixed Generator::send(mixed value)
967 * Sends a value to the generator */
968ZEND_METHOD(Generator, send)
969{
970	zval *value;
971	zend_generator *generator, *root;
972
973#ifndef FAST_ZPP
974	if (zend_parse_parameters(ZEND_NUM_ARGS(), "z", &value) == FAILURE) {
975		return;
976	}
977#else
978	ZEND_PARSE_PARAMETERS_START(1, 1)
979		Z_PARAM_ZVAL(value)
980	ZEND_PARSE_PARAMETERS_END();
981#endif
982
983	generator = (zend_generator *) Z_OBJ_P(getThis());
984
985	zend_generator_ensure_initialized(generator);
986
987	/* The generator is already closed, thus can't send anything */
988	if (UNEXPECTED(!generator->execute_data)) {
989		return;
990	}
991
992	root = zend_generator_get_current(generator);
993	/* Put sent value in the target VAR slot, if it is used */
994	if (root->send_target) {
995		ZVAL_COPY(root->send_target, value);
996	}
997
998	zend_generator_resume(generator);
999
1000	root = zend_generator_get_current(generator);
1001	if (EXPECTED(generator->execute_data)) {
1002		zval *value = &root->value;
1003
1004		ZVAL_DEREF(value);
1005		ZVAL_COPY(return_value, value);
1006	}
1007}
1008/* }}} */
1009
1010/* {{{ proto mixed Generator::throw(Exception exception)
1011 * Throws an exception into the generator */
1012ZEND_METHOD(Generator, throw)
1013{
1014	zval *exception, exception_copy;
1015	zend_generator *generator;
1016
1017#ifndef FAST_ZPP
1018	if (zend_parse_parameters(ZEND_NUM_ARGS(), "z", &exception) == FAILURE) {
1019		return;
1020	}
1021#else
1022	ZEND_PARSE_PARAMETERS_START(1, 1)
1023		Z_PARAM_ZVAL(exception)
1024	ZEND_PARSE_PARAMETERS_END();
1025#endif
1026
1027	ZVAL_DUP(&exception_copy, exception);
1028
1029	generator = (zend_generator *) Z_OBJ_P(getThis());
1030
1031	zend_generator_ensure_initialized(generator);
1032
1033	if (generator->execute_data) {
1034		zend_generator *root = zend_generator_get_current(generator);
1035
1036		zend_generator_throw_exception(root, &exception_copy);
1037
1038		zend_generator_resume(generator);
1039
1040		root = zend_generator_get_current(generator);
1041		if (generator->execute_data) {
1042			zval *value = &root->value;
1043
1044			ZVAL_DEREF(value);
1045			ZVAL_COPY(return_value, value);
1046		}
1047	} else {
1048		/* If the generator is already closed throw the exception in the
1049		 * current context */
1050		zend_throw_exception_object(&exception_copy);
1051	}
1052}
1053/* }}} */
1054
1055/* {{{ proto mixed Generator::getReturn()
1056 * Retrieves the return value of the generator */
1057ZEND_METHOD(Generator, getReturn)
1058{
1059	zend_generator *generator;
1060
1061	if (zend_parse_parameters_none() == FAILURE) {
1062		return;
1063	}
1064
1065	generator = (zend_generator *) Z_OBJ_P(getThis());
1066
1067	zend_generator_ensure_initialized(generator);
1068	if (UNEXPECTED(EG(exception))) {
1069		return;
1070	}
1071
1072	if (Z_ISUNDEF(generator->retval)) {
1073		/* Generator hasn't returned yet -> error! */
1074		zend_throw_exception(NULL,
1075			"Cannot get return value of a generator that hasn't returned", 0);
1076		return;
1077	}
1078
1079	ZVAL_COPY(return_value, &generator->retval);
1080}
1081/* }}} */
1082
1083/* {{{ proto void Generator::__wakeup()
1084 * Throws an Exception as generators can't be serialized */
1085ZEND_METHOD(Generator, __wakeup)
1086{
1087	/* Just specifying the zend_class_unserialize_deny handler is not enough,
1088	 * because it is only invoked for C unserialization. For O the error has
1089	 * to be thrown in __wakeup. */
1090
1091	if (zend_parse_parameters_none() == FAILURE) {
1092		return;
1093	}
1094
1095	zend_throw_exception(NULL, "Unserialization of 'Generator' is not allowed", 0);
1096}
1097/* }}} */
1098
1099/* get_iterator implementation */
1100
1101static void zend_generator_iterator_dtor(zend_object_iterator *iterator) /* {{{ */
1102{
1103	zend_generator *generator = (zend_generator*)Z_OBJ(iterator->data);
1104	generator->iterator = NULL;
1105	zval_ptr_dtor(&iterator->data);
1106	zend_iterator_dtor(iterator);
1107}
1108/* }}} */
1109
1110static int zend_generator_iterator_valid(zend_object_iterator *iterator) /* {{{ */
1111{
1112	zend_generator *generator = (zend_generator*)Z_OBJ(iterator->data);
1113
1114	zend_generator_ensure_initialized(generator);
1115
1116	zend_generator_get_current(generator);
1117
1118	return generator->execute_data ? SUCCESS : FAILURE;
1119}
1120/* }}} */
1121
1122static zval *zend_generator_iterator_get_data(zend_object_iterator *iterator) /* {{{ */
1123{
1124	zend_generator *generator = (zend_generator*)Z_OBJ(iterator->data), *root;
1125
1126	zend_generator_ensure_initialized(generator);
1127
1128	root = zend_generator_get_current(generator);
1129
1130	return &root->value;
1131}
1132/* }}} */
1133
1134static void zend_generator_iterator_get_key(zend_object_iterator *iterator, zval *key) /* {{{ */
1135{
1136	zend_generator *generator = (zend_generator*)Z_OBJ(iterator->data), *root;
1137
1138	zend_generator_ensure_initialized(generator);
1139
1140	root = zend_generator_get_current(generator);
1141
1142	if (EXPECTED(Z_TYPE(root->key) != IS_UNDEF)) {
1143		zval *zv = &root->key;
1144
1145		ZVAL_DEREF(zv);
1146		ZVAL_COPY(key, zv);
1147	} else {
1148		ZVAL_NULL(key);
1149	}
1150}
1151/* }}} */
1152
1153static void zend_generator_iterator_move_forward(zend_object_iterator *iterator) /* {{{ */
1154{
1155	zend_generator *generator = (zend_generator*)Z_OBJ(iterator->data);
1156
1157	zend_generator_ensure_initialized(generator);
1158
1159	zend_generator_resume(generator);
1160}
1161/* }}} */
1162
1163static void zend_generator_iterator_rewind(zend_object_iterator *iterator) /* {{{ */
1164{
1165	zend_generator *generator = (zend_generator*)Z_OBJ(iterator->data);
1166
1167	zend_generator_rewind(generator);
1168}
1169/* }}} */
1170
1171static zend_object_iterator_funcs zend_generator_iterator_functions = {
1172	zend_generator_iterator_dtor,
1173	zend_generator_iterator_valid,
1174	zend_generator_iterator_get_data,
1175	zend_generator_iterator_get_key,
1176	zend_generator_iterator_move_forward,
1177	zend_generator_iterator_rewind,
1178	NULL
1179};
1180
1181zend_object_iterator *zend_generator_get_iterator(zend_class_entry *ce, zval *object, int by_ref) /* {{{ */
1182{
1183	zend_object_iterator *iterator;
1184	zend_generator *generator = (zend_generator*)Z_OBJ_P(object);
1185
1186	if (!generator->execute_data) {
1187		zend_throw_exception(NULL, "Cannot traverse an already closed generator", 0);
1188		return NULL;
1189	}
1190
1191	if (UNEXPECTED(by_ref) && !(generator->execute_data->func->op_array.fn_flags & ZEND_ACC_RETURN_REFERENCE)) {
1192		zend_throw_exception(NULL, "You can only iterate a generator by-reference if it declared that it yields by-reference", 0);
1193		return NULL;
1194	}
1195
1196	iterator = generator->iterator = emalloc(sizeof(zend_object_iterator));
1197
1198	zend_iterator_init(iterator);
1199
1200	iterator->funcs = &zend_generator_iterator_functions;
1201	ZVAL_COPY(&iterator->data, object);
1202
1203	return iterator;
1204}
1205/* }}} */
1206
1207ZEND_BEGIN_ARG_INFO(arginfo_generator_void, 0)
1208ZEND_END_ARG_INFO()
1209
1210ZEND_BEGIN_ARG_INFO_EX(arginfo_generator_send, 0, 0, 1)
1211	ZEND_ARG_INFO(0, value)
1212ZEND_END_ARG_INFO()
1213
1214ZEND_BEGIN_ARG_INFO_EX(arginfo_generator_throw, 0, 0, 1)
1215	ZEND_ARG_INFO(0, exception)
1216ZEND_END_ARG_INFO()
1217
1218static const zend_function_entry generator_functions[] = {
1219	ZEND_ME(Generator, rewind,   arginfo_generator_void, ZEND_ACC_PUBLIC)
1220	ZEND_ME(Generator, valid,    arginfo_generator_void, ZEND_ACC_PUBLIC)
1221	ZEND_ME(Generator, current,  arginfo_generator_void, ZEND_ACC_PUBLIC)
1222	ZEND_ME(Generator, key,      arginfo_generator_void, ZEND_ACC_PUBLIC)
1223	ZEND_ME(Generator, next,     arginfo_generator_void, ZEND_ACC_PUBLIC)
1224	ZEND_ME(Generator, send,     arginfo_generator_send, ZEND_ACC_PUBLIC)
1225	ZEND_ME(Generator, throw,    arginfo_generator_throw, ZEND_ACC_PUBLIC)
1226	ZEND_ME(Generator, getReturn,arginfo_generator_void, ZEND_ACC_PUBLIC)
1227	ZEND_ME(Generator, __wakeup, arginfo_generator_void, ZEND_ACC_PUBLIC)
1228	ZEND_FE_END
1229};
1230
1231void zend_register_generator_ce(void) /* {{{ */
1232{
1233	zend_class_entry ce;
1234
1235	INIT_CLASS_ENTRY(ce, "Generator", generator_functions);
1236	zend_ce_generator = zend_register_internal_class(&ce);
1237	zend_ce_generator->ce_flags |= ZEND_ACC_FINAL;
1238	zend_ce_generator->create_object = zend_generator_create;
1239	zend_ce_generator->serialize = zend_class_serialize_deny;
1240	zend_ce_generator->unserialize = zend_class_unserialize_deny;
1241
1242	/* get_iterator has to be assigned *after* implementing the inferface */
1243	zend_class_implements(zend_ce_generator, 1, zend_ce_iterator);
1244	zend_ce_generator->get_iterator = zend_generator_get_iterator;
1245	zend_ce_generator->iterator_funcs.funcs = &zend_generator_iterator_functions;
1246
1247	memcpy(&zend_generator_handlers, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
1248	zend_generator_handlers.free_obj = zend_generator_free_storage;
1249	zend_generator_handlers.dtor_obj = zend_generator_dtor_storage;
1250	zend_generator_handlers.get_gc = zend_generator_get_gc;
1251	zend_generator_handlers.clone_obj = NULL;
1252	zend_generator_handlers.get_constructor = zend_generator_get_constructor;
1253
1254	INIT_CLASS_ENTRY(ce, "ClosedGeneratorException", NULL);
1255	zend_ce_ClosedGeneratorException = zend_register_internal_class_ex(&ce, zend_ce_exception);
1256}
1257/* }}} */
1258
1259/*
1260 * Local variables:
1261 * tab-width: 4
1262 * c-basic-offset: 4
1263 * indent-tabs-mode: t
1264 * End:
1265 */
1266