1// Copyright 2016 The SwiftShader Authors. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//    http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include "intermediate.h"
16
17//
18// Traverse the intermediate representation tree, and
19// call a node type specific function for each node.
20// Done recursively through the member function Traverse().
21// Node types can be skipped if their function to call is 0,
22// but their subtree will still be traversed.
23// Nodes with children can have their whole subtree skipped
24// if preVisit is turned on and the type specific function
25// returns false.
26//
27// preVisit, postVisit, and rightToLeft control what order
28// nodes are visited in.
29//
30
31//
32// Traversal functions for terminals are straighforward....
33//
34void TIntermSymbol::traverse(TIntermTraverser* it)
35{
36	it->visitSymbol(this);
37}
38
39void TIntermConstantUnion::traverse(TIntermTraverser* it)
40{
41	it->visitConstantUnion(this);
42}
43
44//
45// Traverse a binary node.
46//
47void TIntermBinary::traverse(TIntermTraverser* it)
48{
49	bool visit = true;
50
51	//
52	// visit the node before children if pre-visiting.
53	//
54	if(it->preVisit)
55	{
56		visit = it->visitBinary(PreVisit, this);
57	}
58
59	//
60	// Visit the children, in the right order.
61	//
62	if(visit)
63	{
64		it->incrementDepth(this);
65
66		if(it->rightToLeft)
67		{
68			if(right)
69			{
70				right->traverse(it);
71			}
72
73			if(it->inVisit)
74			{
75				visit = it->visitBinary(InVisit, this);
76			}
77
78			if(visit && left)
79			{
80				left->traverse(it);
81			}
82		}
83		else
84		{
85			if(left)
86			{
87				left->traverse(it);
88			}
89
90			if(it->inVisit)
91			{
92				visit = it->visitBinary(InVisit, this);
93			}
94
95			if(visit && right)
96			{
97				right->traverse(it);
98			}
99		}
100
101		it->decrementDepth();
102	}
103
104	//
105	// Visit the node after the children, if requested and the traversal
106	// hasn't been cancelled yet.
107	//
108	if(visit && it->postVisit)
109	{
110		it->visitBinary(PostVisit, this);
111	}
112}
113
114//
115// Traverse a unary node.  Same comments in binary node apply here.
116//
117void TIntermUnary::traverse(TIntermTraverser* it)
118{
119	bool visit = true;
120
121	if (it->preVisit)
122		visit = it->visitUnary(PreVisit, this);
123
124	if (visit) {
125		it->incrementDepth(this);
126		operand->traverse(it);
127		it->decrementDepth();
128	}
129
130	if (visit && it->postVisit)
131		it->visitUnary(PostVisit, this);
132}
133
134//
135// Traverse an aggregate node.  Same comments in binary node apply here.
136//
137void TIntermAggregate::traverse(TIntermTraverser* it)
138{
139	bool visit = true;
140
141	if(it->preVisit)
142	{
143		visit = it->visitAggregate(PreVisit, this);
144	}
145
146	if(visit)
147	{
148		it->incrementDepth(this);
149
150		if(it->rightToLeft)
151		{
152			for(TIntermSequence::reverse_iterator sit = sequence.rbegin(); sit != sequence.rend(); sit++)
153			{
154				(*sit)->traverse(it);
155
156				if(visit && it->inVisit)
157				{
158					if(*sit != sequence.front())
159					{
160						visit = it->visitAggregate(InVisit, this);
161					}
162				}
163			}
164		}
165		else
166		{
167			for(TIntermSequence::iterator sit = sequence.begin(); sit != sequence.end(); sit++)
168			{
169				(*sit)->traverse(it);
170
171				if(visit && it->inVisit)
172				{
173					if(*sit != sequence.back())
174					{
175						visit = it->visitAggregate(InVisit, this);
176					}
177				}
178			}
179		}
180
181		it->decrementDepth();
182	}
183
184	if(visit && it->postVisit)
185	{
186		it->visitAggregate(PostVisit, this);
187	}
188}
189
190//
191// Traverse a selection node.  Same comments in binary node apply here.
192//
193void TIntermSelection::traverse(TIntermTraverser* it)
194{
195	bool visit = true;
196
197	if (it->preVisit)
198		visit = it->visitSelection(PreVisit, this);
199
200	if (visit) {
201		it->incrementDepth(this);
202		if (it->rightToLeft) {
203			if (falseBlock)
204				falseBlock->traverse(it);
205			if (trueBlock)
206				trueBlock->traverse(it);
207			condition->traverse(it);
208		} else {
209			condition->traverse(it);
210			if (trueBlock)
211				trueBlock->traverse(it);
212			if (falseBlock)
213				falseBlock->traverse(it);
214		}
215		it->decrementDepth();
216	}
217
218	if (visit && it->postVisit)
219		it->visitSelection(PostVisit, this);
220}
221
222//
223// Traverse a switch node.  Same comments in binary node apply here.
224//
225void TIntermSwitch::traverse(TIntermTraverser *it)
226{
227	bool visit = true;
228
229	if(it->preVisit)
230		visit = it->visitSwitch(PreVisit, this);
231
232	if(visit)
233	{
234		it->incrementDepth(this);
235		if(it->inVisit)
236			visit = it->visitSwitch(InVisit, this);
237		it->decrementDepth();
238	}
239
240	if(visit && it->postVisit)
241		it->visitSwitch(PostVisit, this);
242}
243
244//
245// Traverse a switch node.  Same comments in binary node apply here.
246//
247void TIntermCase::traverse(TIntermTraverser *it)
248{
249	bool visit = true;
250
251	if(it->preVisit)
252		visit = it->visitCase(PreVisit, this);
253
254	if(visit && mCondition)
255		mCondition->traverse(it);
256
257	if(visit && it->postVisit)
258		it->visitCase(PostVisit, this);
259}
260
261//
262// Traverse a loop node.  Same comments in binary node apply here.
263//
264void TIntermLoop::traverse(TIntermTraverser* it)
265{
266	bool visit = true;
267
268	if(it->preVisit)
269	{
270		visit = it->visitLoop(PreVisit, this);
271	}
272
273	if(visit)
274	{
275		it->incrementDepth(this);
276
277		if(it->rightToLeft)
278		{
279			if(expr)
280			{
281				expr->traverse(it);
282			}
283
284			if(body)
285			{
286				body->traverse(it);
287			}
288
289			if(cond)
290			{
291				cond->traverse(it);
292			}
293		}
294		else
295		{
296			if(cond)
297			{
298				cond->traverse(it);
299			}
300
301			if(body)
302			{
303				body->traverse(it);
304			}
305
306			if(expr)
307			{
308				expr->traverse(it);
309			}
310		}
311
312		it->decrementDepth();
313	}
314
315	if(visit && it->postVisit)
316	{
317		it->visitLoop(PostVisit, this);
318	}
319}
320
321//
322// Traverse a branch node.  Same comments in binary node apply here.
323//
324void TIntermBranch::traverse(TIntermTraverser* it)
325{
326	bool visit = true;
327
328	if (it->preVisit)
329		visit = it->visitBranch(PreVisit, this);
330
331	if (visit && expression) {
332		it->incrementDepth(this);
333		expression->traverse(it);
334		it->decrementDepth();
335	}
336
337	if (visit && it->postVisit)
338		it->visitBranch(PostVisit, this);
339}
340
341