1: <?php declare(strict_types = 1);
2:
3: namespace PHPStan\PhpDocParser\Ast;
4:
5: use LogicException;
6: use PHPStan\PhpDocParser\Ast\ConstExpr\ConstExprNode;
7: use PHPStan\PhpDocParser\Ast\PhpDoc\PhpDocChildNode;
8: use PHPStan\PhpDocParser\Ast\PhpDoc\PhpDocTagValueNode;
9: use PHPStan\PhpDocParser\Ast\Type\TypeNode;
10: use function array_keys;
11: use function array_pop;
12: use function array_splice;
13: use function count;
14: use function get_class;
15: use function get_object_vars;
16: use function gettype;
17: use function is_array;
18: use function sprintf;
19:
20: /**
21: * Inspired by https://github.com/nikic/PHP-Parser/tree/36a6dcd04e7b0285e8f0868f44bd4927802f7df1
22: *
23: * Copyright (c) 2011, Nikita Popov
24: * All rights reserved.
25: */
26: final class NodeTraverser
27: {
28:
29: /**
30: * If NodeVisitor::enterNode() returns DONT_TRAVERSE_CHILDREN, child nodes
31: * of the current node will not be traversed for any visitors.
32: *
33: * For subsequent visitors enterNode() will still be called on the current
34: * node and leaveNode() will also be invoked for the current node.
35: */
36: public const DONT_TRAVERSE_CHILDREN = 1;
37:
38: /**
39: * If NodeVisitor::enterNode() or NodeVisitor::leaveNode() returns
40: * STOP_TRAVERSAL, traversal is aborted.
41: *
42: * The afterTraverse() method will still be invoked.
43: */
44: public const STOP_TRAVERSAL = 2;
45:
46: /**
47: * If NodeVisitor::leaveNode() returns REMOVE_NODE for a node that occurs
48: * in an array, it will be removed from the array.
49: *
50: * For subsequent visitors leaveNode() will still be invoked for the
51: * removed node.
52: */
53: public const REMOVE_NODE = 3;
54:
55: /**
56: * If NodeVisitor::enterNode() returns DONT_TRAVERSE_CURRENT_AND_CHILDREN, child nodes
57: * of the current node will not be traversed for any visitors.
58: *
59: * For subsequent visitors enterNode() will not be called as well.
60: * leaveNode() will be invoked for visitors that has enterNode() method invoked.
61: */
62: public const DONT_TRAVERSE_CURRENT_AND_CHILDREN = 4;
63:
64: /** @var list<NodeVisitor> Visitors */
65: private $visitors = [];
66:
67: /** @var bool Whether traversal should be stopped */
68: private $stopTraversal;
69:
70: /**
71: * @param list<NodeVisitor> $visitors
72: */
73: public function __construct(array $visitors)
74: {
75: $this->visitors = $visitors;
76: }
77:
78: /**
79: * Traverses an array of nodes using the registered visitors.
80: *
81: * @param Node[] $nodes Array of nodes
82: *
83: * @return Node[] Traversed array of nodes
84: */
85: public function traverse(array $nodes): array
86: {
87: $this->stopTraversal = false;
88:
89: foreach ($this->visitors as $visitor) {
90: $return = $visitor->beforeTraverse($nodes);
91: if ($return === null) {
92: continue;
93: }
94:
95: $nodes = $return;
96: }
97:
98: $nodes = $this->traverseArray($nodes);
99:
100: foreach ($this->visitors as $visitor) {
101: $return = $visitor->afterTraverse($nodes);
102: if ($return === null) {
103: continue;
104: }
105:
106: $nodes = $return;
107: }
108:
109: return $nodes;
110: }
111:
112: /**
113: * Recursively traverse a node.
114: *
115: * @param Node $node Node to traverse.
116: *
117: * @return Node Result of traversal (may be original node or new one)
118: */
119: private function traverseNode(Node $node): Node
120: {
121: $subNodeNames = array_keys(get_object_vars($node));
122: foreach ($subNodeNames as $name) {
123: $subNode =& $node->$name;
124:
125: if (is_array($subNode)) {
126: $subNode = $this->traverseArray($subNode);
127: if ($this->stopTraversal) {
128: break;
129: }
130: } elseif ($subNode instanceof Node) {
131: $traverseChildren = true;
132: $breakVisitorIndex = null;
133:
134: foreach ($this->visitors as $visitorIndex => $visitor) {
135: $return = $visitor->enterNode($subNode);
136: if ($return === null) {
137: continue;
138: }
139:
140: if ($return instanceof Node) {
141: $this->ensureReplacementReasonable($subNode, $return);
142: $subNode = $return;
143: } elseif ($return === self::DONT_TRAVERSE_CHILDREN) {
144: $traverseChildren = false;
145: } elseif ($return === self::DONT_TRAVERSE_CURRENT_AND_CHILDREN) {
146: $traverseChildren = false;
147: $breakVisitorIndex = $visitorIndex;
148: break;
149: } elseif ($return === self::STOP_TRAVERSAL) {
150: $this->stopTraversal = true;
151: break 2;
152: } else {
153: throw new LogicException(
154: 'enterNode() returned invalid value of type ' . gettype($return)
155: );
156: }
157: }
158:
159: if ($traverseChildren) {
160: $subNode = $this->traverseNode($subNode);
161: if ($this->stopTraversal) {
162: break;
163: }
164: }
165:
166: foreach ($this->visitors as $visitorIndex => $visitor) {
167: $return = $visitor->leaveNode($subNode);
168:
169: if ($return !== null) {
170: if ($return instanceof Node) {
171: $this->ensureReplacementReasonable($subNode, $return);
172: $subNode = $return;
173: } elseif ($return === self::STOP_TRAVERSAL) {
174: $this->stopTraversal = true;
175: break 2;
176: } elseif (is_array($return)) {
177: throw new LogicException(
178: 'leaveNode() may only return an array ' .
179: 'if the parent structure is an array'
180: );
181: } else {
182: throw new LogicException(
183: 'leaveNode() returned invalid value of type ' . gettype($return)
184: );
185: }
186: }
187:
188: if ($breakVisitorIndex === $visitorIndex) {
189: break;
190: }
191: }
192: }
193: }
194:
195: return $node;
196: }
197:
198: /**
199: * Recursively traverse array (usually of nodes).
200: *
201: * @param mixed[] $nodes Array to traverse
202: *
203: * @return mixed[] Result of traversal (may be original array or changed one)
204: */
205: private function traverseArray(array $nodes): array
206: {
207: $doNodes = [];
208:
209: foreach ($nodes as $i => &$node) {
210: if ($node instanceof Node) {
211: $traverseChildren = true;
212: $breakVisitorIndex = null;
213:
214: foreach ($this->visitors as $visitorIndex => $visitor) {
215: $return = $visitor->enterNode($node);
216: if ($return === null) {
217: continue;
218: }
219:
220: if ($return instanceof Node) {
221: $this->ensureReplacementReasonable($node, $return);
222: $node = $return;
223: } elseif (is_array($return)) {
224: $doNodes[] = [$i, $return];
225: continue 2;
226: } elseif ($return === self::REMOVE_NODE) {
227: $doNodes[] = [$i, []];
228: continue 2;
229: } elseif ($return === self::DONT_TRAVERSE_CHILDREN) {
230: $traverseChildren = false;
231: } elseif ($return === self::DONT_TRAVERSE_CURRENT_AND_CHILDREN) {
232: $traverseChildren = false;
233: $breakVisitorIndex = $visitorIndex;
234: break;
235: } elseif ($return === self::STOP_TRAVERSAL) {
236: $this->stopTraversal = true;
237: break 2;
238: } else {
239: throw new LogicException(
240: 'enterNode() returned invalid value of type ' . gettype($return)
241: );
242: }
243: }
244:
245: if ($traverseChildren) {
246: $node = $this->traverseNode($node);
247: if ($this->stopTraversal) {
248: break;
249: }
250: }
251:
252: foreach ($this->visitors as $visitorIndex => $visitor) {
253: $return = $visitor->leaveNode($node);
254:
255: if ($return !== null) {
256: if ($return instanceof Node) {
257: $this->ensureReplacementReasonable($node, $return);
258: $node = $return;
259: } elseif (is_array($return)) {
260: $doNodes[] = [$i, $return];
261: break;
262: } elseif ($return === self::REMOVE_NODE) {
263: $doNodes[] = [$i, []];
264: break;
265: } elseif ($return === self::STOP_TRAVERSAL) {
266: $this->stopTraversal = true;
267: break 2;
268: } else {
269: throw new LogicException(
270: 'leaveNode() returned invalid value of type ' . gettype($return)
271: );
272: }
273: }
274:
275: if ($breakVisitorIndex === $visitorIndex) {
276: break;
277: }
278: }
279: } elseif (is_array($node)) {
280: throw new LogicException('Invalid node structure: Contains nested arrays');
281: }
282: }
283:
284: if (count($doNodes) > 0) {
285: while ([$i, $replace] = array_pop($doNodes)) {
286: array_splice($nodes, $i, 1, $replace);
287: }
288: }
289:
290: return $nodes;
291: }
292:
293: private function ensureReplacementReasonable(Node $old, Node $new): void
294: {
295: if ($old instanceof TypeNode && !$new instanceof TypeNode) {
296: throw new LogicException(sprintf('Trying to replace TypeNode with %s', get_class($new)));
297: }
298:
299: if ($old instanceof ConstExprNode && !$new instanceof ConstExprNode) {
300: throw new LogicException(sprintf('Trying to replace ConstExprNode with %s', get_class($new)));
301: }
302:
303: if ($old instanceof PhpDocChildNode && !$new instanceof PhpDocChildNode) {
304: throw new LogicException(sprintf('Trying to replace PhpDocChildNode with %s', get_class($new)));
305: }
306:
307: if ($old instanceof PhpDocTagValueNode && !$new instanceof PhpDocTagValueNode) {
308: throw new LogicException(sprintf('Trying to replace PhpDocTagValueNode with %s', get_class($new)));
309: }
310: }
311:
312: }
313: