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            } elseif ($subNode instanceof Node) {
103                $traverseChildren = true;
104                $visitorIndex = -1;
105
106                foreach ($this->visitors as $visitorIndex => $visitor) {
107                    $return = $visitor->enterNode($subNode);
108                    if (null !== $return) {
109                        if ($return instanceof Node) {
110                            $this->ensureReplacementReasonable($subNode, $return);
111                            $subNode = $node->$name = $return;
112                        } elseif (NodeVisitor::DONT_TRAVERSE_CHILDREN === $return) {
113                            $traverseChildren = false;
114                        } elseif (NodeVisitor::DONT_TRAVERSE_CURRENT_AND_CHILDREN === $return) {
115                            $traverseChildren = false;
116                            break;
117                        } elseif (NodeVisitor::STOP_TRAVERSAL === $return) {
118                            $this->stopTraversal = true;
119                            break 2;
120                        } elseif (NodeVisitor::REPLACE_WITH_NULL === $return) {
121                            $node->$name = null;
122                            continue 2;
123                        } else {
124                            throw new \LogicException(
125                                'enterNode() returned invalid value of type ' . gettype($return)
126                            );
127                        }
128                    }
129                }
130
131                if ($traverseChildren) {
132                    $this->traverseNode($subNode);
133                    if ($this->stopTraversal) {
134                        break;
135                    }
136                }
137
138                for (; $visitorIndex >= 0; --$visitorIndex) {
139                    $visitor = $this->visitors[$visitorIndex];
140                    $return = $visitor->leaveNode($subNode);
141
142                    if (null !== $return) {
143                        if ($return instanceof Node) {
144                            $this->ensureReplacementReasonable($subNode, $return);
145                            $subNode = $node->$name = $return;
146                        } elseif (NodeVisitor::STOP_TRAVERSAL === $return) {
147                            $this->stopTraversal = true;
148                            break 2;
149                        } elseif (NodeVisitor::REPLACE_WITH_NULL === $return) {
150                            $node->$name = null;
151                            break;
152                        } elseif (\is_array($return)) {
153                            throw new \LogicException(
154                                'leaveNode() may only return an array ' .
155                                'if the parent structure is an array'
156                            );
157                        } else {
158                            throw new \LogicException(
159                                'leaveNode() returned invalid value of type ' . gettype($return)
160                            );
161                        }
162                    }
163                }
164            }
165        }
166    }
167
168    /**
169     * Recursively traverse array (usually of nodes).
170     *
171     * @param array $nodes Array to traverse
172     *
173     * @return array Result of traversal (may be original array or changed one)
174     */
175    protected function traverseArray(array $nodes): array {
176        $doNodes = [];
177
178        foreach ($nodes as $i => $node) {
179            if ($node instanceof Node) {
180                $traverseChildren = true;
181                $visitorIndex = -1;
182
183                foreach ($this->visitors as $visitorIndex => $visitor) {
184                    $return = $visitor->enterNode($node);
185                    if (null !== $return) {
186                        if ($return instanceof Node) {
187                            $this->ensureReplacementReasonable($node, $return);
188                            $nodes[$i] = $node = $return;
189                        } elseif (\is_array($return)) {
190                            $doNodes[] = [$i, $return];
191                            continue 2;
192                        } elseif (NodeVisitor::REMOVE_NODE === $return) {
193                            $doNodes[] = [$i, []];
194                            continue 2;
195                        } elseif (NodeVisitor::DONT_TRAVERSE_CHILDREN === $return) {
196                            $traverseChildren = false;
197                        } elseif (NodeVisitor::DONT_TRAVERSE_CURRENT_AND_CHILDREN === $return) {
198                            $traverseChildren = false;
199                            break;
200                        } elseif (NodeVisitor::STOP_TRAVERSAL === $return) {
201                            $this->stopTraversal = true;
202                            break 2;
203                        } elseif (NodeVisitor::REPLACE_WITH_NULL === $return) {
204                            throw new \LogicException(
205                                'REPLACE_WITH_NULL can not be used if the parent structure is an array');
206                        } else {
207                            throw new \LogicException(
208                                'enterNode() returned invalid value of type ' . gettype($return)
209                            );
210                        }
211                    }
212                }
213
214                if ($traverseChildren) {
215                    $this->traverseNode($node);
216                    if ($this->stopTraversal) {
217                        break;
218                    }
219                }
220
221                for (; $visitorIndex >= 0; --$visitorIndex) {
222                    $visitor = $this->visitors[$visitorIndex];
223                    $return = $visitor->leaveNode($node);
224
225                    if (null !== $return) {
226                        if ($return instanceof Node) {
227                            $this->ensureReplacementReasonable($node, $return);
228                            $nodes[$i] = $node = $return;
229                        } elseif (\is_array($return)) {
230                            $doNodes[] = [$i, $return];
231                            break;
232                        } elseif (NodeVisitor::REMOVE_NODE === $return) {
233                            $doNodes[] = [$i, []];
234                            break;
235                        } elseif (NodeVisitor::STOP_TRAVERSAL === $return) {
236                            $this->stopTraversal = true;
237                            break 2;
238                        } elseif (NodeVisitor::REPLACE_WITH_NULL === $return) {
239                            throw new \LogicException(
240                                'REPLACE_WITH_NULL can not be used if the parent structure is an array');
241                        } else {
242                            throw new \LogicException(
243                                'leaveNode() returned invalid value of type ' . gettype($return)
244                            );
245                        }
246                    }
247                }
248            } elseif (\is_array($node)) {
249                throw new \LogicException('Invalid node structure: Contains nested arrays');
250            }
251        }
252
253        if (!empty($doNodes)) {
254            while (list($i, $replace) = array_pop($doNodes)) {
255                array_splice($nodes, $i, 1, $replace);
256            }
257        }
258
259        return $nodes;
260    }
261
262    private function ensureReplacementReasonable(Node $old, Node $new): void {
263        if ($old instanceof Node\Stmt && $new instanceof Node\Expr) {
264            throw new \LogicException(
265                "Trying to replace statement ({$old->getType()}) " .
266                "with expression ({$new->getType()}). Are you missing a " .
267                "Stmt_Expression wrapper?"
268            );
269        }
270
271        if ($old instanceof Node\Expr && $new instanceof Node\Stmt) {
272            throw new \LogicException(
273                "Trying to replace expression ({$old->getType()}) " .
274                "with statement ({$new->getType()})"
275            );
276        }
277    }
278}
279