1 //
2 // Copyright (C) 2002-2005 3Dlabs Inc. Ltd.
3 // Copyright (C) 2013 LunarG, Inc.
4 // Copyright (c) 2002-2010 The ANGLE Project Authors.
5 //
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions
10 // are met:
11 //
12 // Redistributions of source code must retain the above copyright
13 // notice, this list of conditions and the following disclaimer.
14 //
15 // Redistributions in binary form must reproduce the above
16 // copyright notice, this list of conditions and the following
17 // disclaimer in the documentation and/or other materials provided
18 // with the distribution.
19 //
20 // Neither the name of 3Dlabs Inc. Ltd. nor the names of its
21 // contributors may be used to endorse or promote products derived
22 // from this software without specific prior written permission.
23 //
24 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
27 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
28 // COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
29 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
30 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
31 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
32 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
34 // ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 // POSSIBILITY OF SUCH DAMAGE.
36 //
37
38 #include "../Include/intermediate.h"
39
40 namespace glslang {
41
42 //
43 // Traverse the intermediate representation tree, and
44 // call a node type specific function for each node.
45 // Done recursively through the member function Traverse().
46 // Node types can be skipped if their function to call is 0,
47 // but their subtree will still be traversed.
48 // Nodes with children can have their whole subtree skipped
49 // if preVisit is turned on and the type specific function
50 // returns false.
51 //
52 // preVisit, postVisit, and rightToLeft control what order
53 // nodes are visited in.
54 //
55
56 //
57 // Traversal functions for terminals are straightforward....
58 //
traverse(TIntermTraverser *)59 void TIntermMethod::traverse(TIntermTraverser*)
60 {
61 // Tree should always resolve all methods as a non-method.
62 }
63
traverse(TIntermTraverser * it)64 void TIntermSymbol::traverse(TIntermTraverser *it)
65 {
66 it->visitSymbol(this);
67 }
68
traverse(TIntermTraverser * it)69 void TIntermConstantUnion::traverse(TIntermTraverser *it)
70 {
71 it->visitConstantUnion(this);
72 }
73
74 //
75 // Traverse a binary node.
76 //
traverse(TIntermTraverser * it)77 void TIntermBinary::traverse(TIntermTraverser *it)
78 {
79 bool visit = true;
80
81 //
82 // visit the node before children if pre-visiting.
83 //
84 if (it->preVisit)
85 visit = it->visitBinary(EvPreVisit, this);
86
87 //
88 // Visit the children, in the right order.
89 //
90 if (visit) {
91 it->incrementDepth(this);
92
93 if (it->rightToLeft) {
94 if (right)
95 right->traverse(it);
96
97 if (it->inVisit)
98 visit = it->visitBinary(EvInVisit, this);
99
100 if (visit && left)
101 left->traverse(it);
102 } else {
103 if (left)
104 left->traverse(it);
105
106 if (it->inVisit)
107 visit = it->visitBinary(EvInVisit, this);
108
109 if (visit && right)
110 right->traverse(it);
111 }
112
113 it->decrementDepth();
114 }
115
116 //
117 // Visit the node after the children, if requested and the traversal
118 // hasn't been canceled yet.
119 //
120 if (visit && it->postVisit)
121 it->visitBinary(EvPostVisit, this);
122 }
123
124 //
125 // Traverse a unary node. Same comments in binary node apply here.
126 //
traverse(TIntermTraverser * it)127 void TIntermUnary::traverse(TIntermTraverser *it)
128 {
129 bool visit = true;
130
131 if (it->preVisit)
132 visit = it->visitUnary(EvPreVisit, this);
133
134 if (visit) {
135 it->incrementDepth(this);
136 operand->traverse(it);
137 it->decrementDepth();
138 }
139
140 if (visit && it->postVisit)
141 it->visitUnary(EvPostVisit, this);
142 }
143
144 //
145 // Traverse an aggregate node. Same comments in binary node apply here.
146 //
traverse(TIntermTraverser * it)147 void TIntermAggregate::traverse(TIntermTraverser *it)
148 {
149 bool visit = true;
150
151 if (it->preVisit)
152 visit = it->visitAggregate(EvPreVisit, this);
153
154 if (visit) {
155 it->incrementDepth(this);
156
157 if (it->rightToLeft) {
158 for (TIntermSequence::reverse_iterator sit = sequence.rbegin(); sit != sequence.rend(); sit++) {
159 (*sit)->traverse(it);
160
161 if (visit && it->inVisit) {
162 if (*sit != sequence.front())
163 visit = it->visitAggregate(EvInVisit, this);
164 }
165 }
166 } else {
167 for (TIntermSequence::iterator sit = sequence.begin(); sit != sequence.end(); sit++) {
168 (*sit)->traverse(it);
169
170 if (visit && it->inVisit) {
171 if (*sit != sequence.back())
172 visit = it->visitAggregate(EvInVisit, this);
173 }
174 }
175 }
176
177 it->decrementDepth();
178 }
179
180 if (visit && it->postVisit)
181 it->visitAggregate(EvPostVisit, this);
182 }
183
184 //
185 // Traverse a selection node. Same comments in binary node apply here.
186 //
traverse(TIntermTraverser * it)187 void TIntermSelection::traverse(TIntermTraverser *it)
188 {
189 bool visit = true;
190
191 if (it->preVisit)
192 visit = it->visitSelection(EvPreVisit, this);
193
194 if (visit) {
195 it->incrementDepth(this);
196 if (it->rightToLeft) {
197 if (falseBlock)
198 falseBlock->traverse(it);
199 if (trueBlock)
200 trueBlock->traverse(it);
201 condition->traverse(it);
202 } else {
203 condition->traverse(it);
204 if (trueBlock)
205 trueBlock->traverse(it);
206 if (falseBlock)
207 falseBlock->traverse(it);
208 }
209 it->decrementDepth();
210 }
211
212 if (visit && it->postVisit)
213 it->visitSelection(EvPostVisit, this);
214 }
215
216 //
217 // Traverse a loop node. Same comments in binary node apply here.
218 //
traverse(TIntermTraverser * it)219 void TIntermLoop::traverse(TIntermTraverser *it)
220 {
221 bool visit = true;
222
223 if (it->preVisit)
224 visit = it->visitLoop(EvPreVisit, this);
225
226 if (visit) {
227 it->incrementDepth(this);
228
229 if (it->rightToLeft) {
230 if (terminal)
231 terminal->traverse(it);
232
233 if (body)
234 body->traverse(it);
235
236 if (test)
237 test->traverse(it);
238 } else {
239 if (test)
240 test->traverse(it);
241
242 if (body)
243 body->traverse(it);
244
245 if (terminal)
246 terminal->traverse(it);
247 }
248
249 it->decrementDepth();
250 }
251
252 if (visit && it->postVisit)
253 it->visitLoop(EvPostVisit, this);
254 }
255
256 //
257 // Traverse a branch node. Same comments in binary node apply here.
258 //
traverse(TIntermTraverser * it)259 void TIntermBranch::traverse(TIntermTraverser *it)
260 {
261 bool visit = true;
262
263 if (it->preVisit)
264 visit = it->visitBranch(EvPreVisit, this);
265
266 if (visit && expression) {
267 it->incrementDepth(this);
268 expression->traverse(it);
269 it->decrementDepth();
270 }
271
272 if (visit && it->postVisit)
273 it->visitBranch(EvPostVisit, this);
274 }
275
276 //
277 // Traverse a switch node.
278 //
traverse(TIntermTraverser * it)279 void TIntermSwitch::traverse(TIntermTraverser* it)
280 {
281 bool visit = true;
282
283 if (it->preVisit)
284 visit = it->visitSwitch(EvPreVisit, this);
285
286 if (visit) {
287 it->incrementDepth(this);
288 if (it->rightToLeft) {
289 body->traverse(it);
290 condition->traverse(it);
291 } else {
292 condition->traverse(it);
293 body->traverse(it);
294 }
295 it->decrementDepth();
296 }
297
298 if (visit && it->postVisit)
299 it->visitSwitch(EvPostVisit, this);
300 }
301
302 } // end namespace glslang
303