1<?php declare(strict_types=1);
2
3namespace PhpParser;
4
5class NodeTraverser implements NodeTraverserInterface {
6    /**
7     * @deprecated Use NodeVisitor::DONT_TRAVERSE_CHILDREN instead.
8     */
9    public const DONT_TRAVERSE_CHILDREN = NodeVisitor::DONT_TRAVERSE_CHILDREN;
10
11    /**
12     * @deprecated Use NodeVisitor::STOP_TRAVERSAL instead.
13     */
14    public const STOP_TRAVERSAL = NodeVisitor::STOP_TRAVERSAL;
15
16    /**
17     * @deprecated Use NodeVisitor::REMOVE_NODE instead.
18     */
19    public const REMOVE_NODE = NodeVisitor::REMOVE_NODE;
20
21    /**
22     * @deprecated Use NodeVisitor::DONT_TRAVERSE_CURRENT_AND_CHILDREN instead.
23     */
24    public const DONT_TRAVERSE_CURRENT_AND_CHILDREN = NodeVisitor::DONT_TRAVERSE_CURRENT_AND_CHILDREN;
25
26    /** @var list<NodeVisitor> Visitors */
27    protected array $visitors = [];
28
29    /** @var bool Whether traversal should be stopped */
30    protected bool $stopTraversal;
31
32    /**
33     * Create a traverser with the given visitors.
34     *
35     * @param NodeVisitor ...$visitors Node visitors
36     */
37    public function __construct(NodeVisitor ...$visitors) {
38        $this->visitors = $visitors;
39    }
40
41    /**
42     * Adds a visitor.
43     *
44     * @param NodeVisitor $visitor Visitor to add
45     */
46    public function addVisitor(NodeVisitor $visitor): void {
47        $this->visitors[] = $visitor;
48    }
49
50    /**
51     * Removes an added visitor.
52     */
53    public function removeVisitor(NodeVisitor $visitor): void {
54        $index = array_search($visitor, $this->visitors);
55        if ($index !== false) {
56            array_splice($this->visitors, $index, 1, []);
57        }
58    }
59
60    /**
61     * Traverses an array of nodes using the registered visitors.
62     *
63     * @param Node[] $nodes Array of nodes
64     *
65     * @return Node[] Traversed array of nodes
66     */
67    public function traverse(array $nodes): array {
68        $this->stopTraversal = false;
69
70        foreach ($this->visitors as $visitor) {
71            if (null !== $return = $visitor->beforeTraverse($nodes)) {
72                $nodes = $return;
73            }
74        }
75
76        $nodes = $this->traverseArray($nodes);
77
78        for ($i = \count($this->visitors) - 1; $i >= 0; --$i) {
79            $visitor = $this->visitors[$i];
80            if (null !== $return = $visitor->afterTraverse($nodes)) {
81                $nodes = $return;
82            }
83        }
84
85        return $nodes;
86    }
87
88    /**
89     * Recursively traverse a node.
90     *
91     * @param Node $node Node to traverse.
92     */
93    protected function traverseNode(Node $node): void {
94        foreach ($node->getSubNodeNames() as $name) {
95            $subNode = $node->$name;
96
97            if (\is_array($subNode)) {
98                $node->$name = $this->traverseArray($subNode);
99                if ($this->stopTraversal) {
100                    break;
101                }
102
103                continue;
104            }
105
106            if (!$subNode instanceof Node) {
107                continue;
108            }
109
110            $traverseChildren = true;
111            $visitorIndex = -1;
112
113            foreach ($this->visitors as $visitorIndex => $visitor) {
114                $return = $visitor->enterNode($subNode);
115                if (null !== $return) {
116                    if ($return instanceof Node) {
117                        $this->ensureReplacementReasonable($subNode, $return);
118                        $subNode = $node->$name = $return;
119                    } elseif (NodeVisitor::DONT_TRAVERSE_CHILDREN === $return) {
120                        $traverseChildren = false;
121                    } elseif (NodeVisitor::DONT_TRAVERSE_CURRENT_AND_CHILDREN === $return) {
122                        $traverseChildren = false;
123                        break;
124                    } elseif (NodeVisitor::STOP_TRAVERSAL === $return) {
125                        $this->stopTraversal = true;
126                        break 2;
127                    } elseif (NodeVisitor::REPLACE_WITH_NULL === $return) {
128                        $node->$name = null;
129                        continue 2;
130                    } else {
131                        throw new \LogicException(
132                            'enterNode() returned invalid value of type ' . gettype($return)
133                        );
134                    }
135                }
136            }
137
138            if ($traverseChildren) {
139                $this->traverseNode($subNode);
140                if ($this->stopTraversal) {
141                    break;
142                }
143            }
144
145            for (; $visitorIndex >= 0; --$visitorIndex) {
146                $visitor = $this->visitors[$visitorIndex];
147                $return = $visitor->leaveNode($subNode);
148
149                if (null !== $return) {
150                    if ($return instanceof Node) {
151                        $this->ensureReplacementReasonable($subNode, $return);
152                        $subNode = $node->$name = $return;
153                    } elseif (NodeVisitor::STOP_TRAVERSAL === $return) {
154                        $this->stopTraversal = true;
155                        break 2;
156                    } elseif (NodeVisitor::REPLACE_WITH_NULL === $return) {
157                        $node->$name = null;
158                        break;
159                    } elseif (\is_array($return)) {
160                        throw new \LogicException(
161                            'leaveNode() may only return an array ' .
162                            'if the parent structure is an array'
163                        );
164                    } else {
165                        throw new \LogicException(
166                            'leaveNode() returned invalid value of type ' . gettype($return)
167                        );
168                    }
169                }
170            }
171        }
172    }
173
174    /**
175     * Recursively traverse array (usually of nodes).
176     *
177     * @param array $nodes Array to traverse
178     *
179     * @return array Result of traversal (may be original array or changed one)
180     */
181    protected function traverseArray(array $nodes): array {
182        $doNodes = [];
183
184        foreach ($nodes as $i => $node) {
185            if (!$node instanceof Node) {
186                if (\is_array($node)) {
187                    throw new \LogicException('Invalid node structure: Contains nested arrays');
188                }
189                continue;
190            }
191
192            $traverseChildren = true;
193            $visitorIndex = -1;
194
195            foreach ($this->visitors as $visitorIndex => $visitor) {
196                $return = $visitor->enterNode($node);
197                if (null !== $return) {
198                    if ($return instanceof Node) {
199                        $this->ensureReplacementReasonable($node, $return);
200                        $nodes[$i] = $node = $return;
201                    } elseif (\is_array($return)) {
202                        $doNodes[] = [$i, $return];
203                        continue 2;
204                    } elseif (NodeVisitor::REMOVE_NODE === $return) {
205                        $doNodes[] = [$i, []];
206                        continue 2;
207                    } elseif (NodeVisitor::DONT_TRAVERSE_CHILDREN === $return) {
208                        $traverseChildren = false;
209                    } elseif (NodeVisitor::DONT_TRAVERSE_CURRENT_AND_CHILDREN === $return) {
210                        $traverseChildren = false;
211                        break;
212                    } elseif (NodeVisitor::STOP_TRAVERSAL === $return) {
213                        $this->stopTraversal = true;
214                        break 2;
215                    } elseif (NodeVisitor::REPLACE_WITH_NULL === $return) {
216                        throw new \LogicException(
217                            'REPLACE_WITH_NULL can not be used if the parent structure is an array');
218                    } else {
219                        throw new \LogicException(
220                            'enterNode() returned invalid value of type ' . gettype($return)
221                        );
222                    }
223                }
224            }
225
226            if ($traverseChildren) {
227                $this->traverseNode($node);
228                if ($this->stopTraversal) {
229                    break;
230                }
231            }
232
233            for (; $visitorIndex >= 0; --$visitorIndex) {
234                $visitor = $this->visitors[$visitorIndex];
235                $return = $visitor->leaveNode($node);
236
237                if (null !== $return) {
238                    if ($return instanceof Node) {
239                        $this->ensureReplacementReasonable($node, $return);
240                        $nodes[$i] = $node = $return;
241                    } elseif (\is_array($return)) {
242                        $doNodes[] = [$i, $return];
243                        break;
244                    } elseif (NodeVisitor::REMOVE_NODE === $return) {
245                        $doNodes[] = [$i, []];
246                        break;
247                    } elseif (NodeVisitor::STOP_TRAVERSAL === $return) {
248                        $this->stopTraversal = true;
249                        break 2;
250                    } elseif (NodeVisitor::REPLACE_WITH_NULL === $return) {
251                        throw new \LogicException(
252                            'REPLACE_WITH_NULL can not be used if the parent structure is an array');
253                    } else {
254                        throw new \LogicException(
255                            'leaveNode() returned invalid value of type ' . gettype($return)
256                        );
257                    }
258                }
259            }
260        }
261
262        if (!empty($doNodes)) {
263            while (list($i, $replace) = array_pop($doNodes)) {
264                array_splice($nodes, $i, 1, $replace);
265            }
266        }
267
268        return $nodes;
269    }
270
271    private function ensureReplacementReasonable(Node $old, Node $new): void {
272        if ($old instanceof Node\Stmt && $new instanceof Node\Expr) {
273            throw new \LogicException(
274                "Trying to replace statement ({$old->getType()}) " .
275                "with expression ({$new->getType()}). Are you missing a " .
276                "Stmt_Expression wrapper?"
277            );
278        }
279
280        if ($old instanceof Node\Expr && $new instanceof Node\Stmt) {
281            throw new \LogicException(
282                "Trying to replace expression ({$old->getType()}) " .
283                "with statement ({$new->getType()})"
284            );
285        }
286    }
287}
288