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