1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 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 #ifndef ZEND_GENERATORS_H
21 #define ZEND_GENERATORS_H
22
23 #include <stdint.h>
24
25 #include "zend_compile.h"
26
27 BEGIN_EXTERN_C()
28
29 extern ZEND_API zend_class_entry *zend_ce_generator;
30 extern ZEND_API zend_class_entry *zend_ce_ClosedGeneratorException;
31
32 typedef struct _zend_generator_node zend_generator_node;
33 typedef struct _zend_generator zend_generator;
34
35 /* The concept of `yield from` exposes problems when accessed at different levels of the chain of delegated generators. We need to be able to reference the currently executed Generator in all cases and still being able to access the return values of finished Generators.
36 * The solution to this problem is a doubly-linked tree, which all Generators referenced in maintain a reference to. It should be impossible to avoid walking the tree in all cases. This way, we only need tree walks from leaf to root in case where some part of the `yield from` chain is passed to another `yield from`. (Update of leaf node pointer and list of multi-children nodes needed when leaf gets a child in direct path from leaf to root node.) But only in that case, which should be a fairly rare case (which is then possible, but not totally cheap).
37 * The root of the tree is then the currently executed Generator. The subnodes of the tree (all except the root node) are all Generators which do `yield from`. Each node of the tree knows a pointer to one leaf descendant node. Each node with multiple children needs a list of all leaf descendant nodes paired with pointers to their respective child node. (The stack is determined by leaf node pointers) Nodes with only one child just don't need a list, there it is enough to just have a pointer to the child node. Further, leaf nodes store a pointer to the root node.
38 * That way, when we advance any generator, we just need to look up a leaf node (which all have a reference to a root node). Then we can see at the root node whether current Generator is finished. If it isn't, all is fine and we can just continue. If the Generator finished, there will be two cases. Either it is a simple node with just one child, then go down to child node. Or it has multiple children and we now will remove the current leaf node from the list of nodes (unnecessary, is microoptimization) and go down to the child node whose reference was paired with current leaf node. Child node is then removed its parent reference and becomes new top node. Or the current node references the Generator we're currently executing, then we can continue from the YIELD_FROM opcode. When a node referenced as root node in a leaf node has a parent, then we go the way up until we find a root node without parent.
39 * In case we go into a new `yield from` level, a node is created on top of current root and becomes the new root. Leaf node needs to be updated with new root node then.
40 * When a Generator referenced by a node of the tree is added to `yield from`, that node now gets a list of children (we need to walk the descendants of that node and nodes of the tree of the other Generator down to the first multi-children node and copy all the leaf node pointers from there). In case there was no multi-children node (linear tree), we just add a pair (pointer to leaf node, pointer to child node), with the child node being in a direct path from leaf to this node.
41 */
42
43 struct _zend_generator_node {
44 zend_generator *parent; /* NULL for root */
45 uint32_t children;
46 union {
47 HashTable *ht; /* if multiple children */
48 zend_generator *single; /* if one child */
49 } child;
50 /* One generator can cache a direct pointer to the current root.
51 * The leaf member points back to the generator using the root cache. */
52 union {
53 zend_generator *leaf; /* if parent != NULL */
54 zend_generator *root; /* if parent == NULL */
55 } ptr;
56 };
57
58 struct _zend_generator {
59 zend_object std;
60
61 /* The suspended execution context. */
62 zend_execute_data *execute_data;
63
64 /* Frozen call stack for "yield" used in context of other calls */
65 zend_execute_data *frozen_call_stack;
66
67 /* Current value */
68 zval value;
69 /* Current key */
70 zval key;
71 /* Return value */
72 zval retval;
73 /* Variable to put sent value into */
74 zval *send_target;
75 /* Largest used integer key for auto-incrementing keys */
76 zend_long largest_used_integer_key;
77
78 /* Values specified by "yield from" to yield from this generator.
79 * This is only used for arrays or non-generator Traversables.
80 * This zval also uses the u2 structure in the same way as
81 * by-value foreach. */
82 zval values;
83
84 /* Node of waiting generators when multiple "yield from" expressions
85 * are nested. */
86 zend_generator_node node;
87
88 /* Fake execute_data for stacktraces */
89 zend_execute_data execute_fake;
90
91 /* The underlying function, equivalent to execute_data->func while
92 * the generator is alive. */
93 zend_function *func;
94
95 /* ZEND_GENERATOR_* flags */
96 uint8_t flags;
97 };
98
99 static const uint8_t ZEND_GENERATOR_CURRENTLY_RUNNING = 0x1;
100 static const uint8_t ZEND_GENERATOR_FORCED_CLOSE = 0x2;
101 static const uint8_t ZEND_GENERATOR_AT_FIRST_YIELD = 0x4;
102 static const uint8_t ZEND_GENERATOR_DO_INIT = 0x8;
103 static const uint8_t ZEND_GENERATOR_IN_FIBER = 0x10;
104 static const uint8_t ZEND_GENERATOR_DTOR_VISITED = 0x20;
105
106 void zend_register_generator_ce(void);
107 ZEND_API void zend_generator_close(zend_generator *generator, bool finished_execution);
108 ZEND_API void zend_generator_resume(zend_generator *generator);
109
110 ZEND_API void zend_generator_restore_call_stack(zend_generator *generator);
111 ZEND_API zend_execute_data* zend_generator_freeze_call_stack(zend_execute_data *execute_data);
112
113 void zend_generator_yield_from(zend_generator *generator, zend_generator *from);
114 ZEND_API zend_execute_data *zend_generator_check_placeholder_frame(zend_execute_data *ptr);
115
116 ZEND_API zend_generator *zend_generator_update_current(zend_generator *generator);
117 ZEND_API zend_generator *zend_generator_update_root(zend_generator *generator);
zend_generator_get_current(zend_generator * generator)118 static zend_always_inline zend_generator *zend_generator_get_current(zend_generator *generator)
119 {
120 if (EXPECTED(generator->node.parent == NULL)) {
121 /* we're not in yield from mode */
122 return generator;
123 }
124
125 zend_generator *root = generator->node.ptr.root;
126 if (!root) {
127 root = zend_generator_update_root(generator);
128 }
129
130 if (EXPECTED(root->execute_data)) {
131 /* generator still running */
132 return root;
133 }
134
135 return zend_generator_update_current(generator);
136 }
137
138 END_EXTERN_C()
139
140 #endif
141