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 "MacroExpander.h"
16
17#include <algorithm>
18#include <sstream>
19
20#include "Diagnostics.h"
21#include "Token.h"
22
23namespace pp
24{
25
26class TokenLexer : public Lexer
27{
28 public:
29	typedef std::vector<Token> TokenVector;
30
31	TokenLexer(TokenVector* tokens)
32	{
33		tokens->swap(mTokens);
34		mIter = mTokens.begin();
35	}
36
37	virtual void lex(Token* token)
38	{
39		if (mIter == mTokens.end())
40		{
41			token->reset();
42			token->type = Token::LAST;
43		}
44		else
45		{
46			*token = *mIter++;
47		}
48	}
49
50 private:
51	PP_DISALLOW_COPY_AND_ASSIGN(TokenLexer);
52
53	TokenVector mTokens;
54	TokenVector::const_iterator mIter;
55};
56
57MacroExpander::MacroExpander(Lexer* lexer,
58                             MacroSet* macroSet,
59                             Diagnostics* diagnostics,
60                             bool parseDefined) :
61	mLexer(lexer), mMacroSet(macroSet), mDiagnostics(diagnostics), mParseDefined(parseDefined)
62{
63	mReserveToken = nullptr;
64}
65
66MacroExpander::~MacroExpander()
67{
68	for (size_t i = 0; i < mContextStack.size(); ++i)
69	{
70		delete mContextStack[i];
71	}
72
73	delete mReserveToken;
74}
75
76void MacroExpander::lex(Token* token)
77{
78	while (true)
79	{
80		getToken(token);
81
82		if (token->type != Token::IDENTIFIER)
83			break;
84
85		// Defined operator is parsed here since it may be generated by macro expansion.
86		// Defined operator produced by macro expansion has undefined behavior according to C++
87		// spec, which the GLSL spec references (see C++14 draft spec section 16.1.4), but this
88		// behavior is needed for passing dEQP tests, which enforce stricter compatibility between
89		// implementations.
90		if (mParseDefined && token->text == "defined")
91		{
92			bool paren = false;
93			getToken(token);
94			if (token->type == '(')
95			{
96				paren = true;
97				getToken(token);
98			}
99			if (token->type != Token::IDENTIFIER)
100			{
101				mDiagnostics->report(Diagnostics::UNEXPECTED_TOKEN, token->location,
102				                     token->text);
103				break;
104			}
105			auto iter = mMacroSet->find(token->text);
106			std::string expression = iter != mMacroSet->end() ? "1" : "0";
107
108			if (paren)
109			{
110				getToken(token);
111				if (token->type != ')')
112				{
113					mDiagnostics->report(Diagnostics::UNEXPECTED_TOKEN, token->location,
114					                     token->text);
115					break;
116				}
117			}
118
119			// We have a valid defined operator.
120			// Convert the current token into a CONST_INT token.
121			token->type = Token::CONST_INT;
122			token->text = expression;
123			break;
124		}
125
126		if (token->expansionDisabled())
127			break;
128
129		MacroSet::const_iterator iter = mMacroSet->find(token->text);
130		if (iter == mMacroSet->end())
131			break;
132
133		const Macro& macro = iter->second;
134		if (macro.disabled)
135		{
136			// If a particular token is not expanded, it is never expanded.
137			token->setExpansionDisabled(true);
138			break;
139		}
140		if ((macro.type == Macro::kTypeFunc) && !isNextTokenLeftParen())
141		{
142			// If the token immediately after the macro name is not a '(',
143			// this macro should not be expanded.
144			break;
145		}
146
147		pushMacro(macro, *token);
148	}
149}
150
151void MacroExpander::getToken(Token* token)
152{
153	if (mReserveToken)
154	{
155		*token = *mReserveToken;
156		delete mReserveToken;
157		mReserveToken = nullptr;
158		return;
159	}
160
161	// First pop all empty macro contexts.
162	while (!mContextStack.empty() && mContextStack.back()->empty())
163	{
164		popMacro();
165	}
166
167	if (!mContextStack.empty())
168	{
169		*token = mContextStack.back()->get();
170	}
171	else
172	{
173		mLexer->lex(token);
174	}
175}
176
177void MacroExpander::ungetToken(const Token& token)
178{
179	if (!mContextStack.empty())
180	{
181		MacroContext* context = mContextStack.back();
182		context->unget();
183		assert(context->replacements[context->index] == token);
184	}
185	else
186	{
187		assert(!mReserveToken);
188		mReserveToken = new Token(token);
189	}
190}
191
192bool MacroExpander::isNextTokenLeftParen()
193{
194	Token token;
195	getToken(&token);
196
197	bool lparen = token.type == '(';
198	ungetToken(token);
199
200	return lparen;
201}
202
203bool MacroExpander::pushMacro(const Macro& macro, const Token& identifier)
204{
205	assert(!macro.disabled);
206	assert(!identifier.expansionDisabled());
207	assert(identifier.type == Token::IDENTIFIER);
208	assert(identifier.text == macro.name);
209
210	std::vector<Token> replacements;
211	if (!expandMacro(macro, identifier, &replacements))
212		return false;
213
214	// Macro is disabled for expansion until it is popped off the stack.
215	macro.disabled = true;
216
217	MacroContext* context = new MacroContext;
218	context->macro = &macro;
219	context->replacements.swap(replacements);
220	mContextStack.push_back(context);
221	return true;
222}
223
224void MacroExpander::popMacro()
225{
226	assert(!mContextStack.empty());
227
228	MacroContext* context = mContextStack.back();
229	mContextStack.pop_back();
230
231	assert(context->empty());
232	assert(context->macro->disabled);
233	context->macro->disabled = false;
234	delete context;
235}
236
237bool MacroExpander::expandMacro(const Macro& macro,
238                                const Token& identifier,
239                                std::vector<Token>* replacements)
240{
241	replacements->clear();
242	if (macro.type == Macro::kTypeObj)
243	{
244		replacements->assign(macro.replacements.begin(),
245		                     macro.replacements.end());
246
247		if (macro.predefined)
248		{
249			static const std::string kLine = "__LINE__";
250			static const std::string kFile = "__FILE__";
251
252			assert(replacements->size() == 1);
253			Token& repl = replacements->front();
254			if (macro.name == kLine)
255			{
256				std::ostringstream stream;
257				stream << identifier.location.line;
258				repl.text = stream.str();
259			}
260			else if (macro.name == kFile)
261			{
262				std::ostringstream stream;
263				stream << identifier.location.file;
264				repl.text = stream.str();
265			}
266		}
267	}
268	else
269	{
270		assert(macro.type == Macro::kTypeFunc);
271		std::vector<MacroArg> args;
272		args.reserve(macro.parameters.size());
273		if (!collectMacroArgs(macro, identifier, &args))
274			return false;
275
276		replaceMacroParams(macro, args, replacements);
277	}
278
279	for (size_t i = 0; i < replacements->size(); ++i)
280	{
281		Token& repl = replacements->at(i);
282		if (i == 0)
283		{
284			// The first token in the replacement list inherits the padding
285			// properties of the identifier token.
286			repl.setAtStartOfLine(identifier.atStartOfLine());
287			repl.setHasLeadingSpace(identifier.hasLeadingSpace());
288		}
289		repl.location = identifier.location;
290	}
291	return true;
292}
293
294bool MacroExpander::collectMacroArgs(const Macro& macro,
295                                     const Token& identifier,
296                                     std::vector<MacroArg>* args)
297{
298	Token token;
299	getToken(&token);
300	assert(token.type == '(');
301
302	args->push_back(MacroArg());
303	for (int openParens = 1; openParens != 0; )
304	{
305		getToken(&token);
306
307		if (token.type == Token::LAST)
308		{
309			mDiagnostics->report(Diagnostics::MACRO_UNTERMINATED_INVOCATION,
310			                     identifier.location, identifier.text);
311			// Do not lose EOF token.
312			ungetToken(token);
313			return false;
314		}
315
316		bool isArg = false; // True if token is part of the current argument.
317		switch (token.type)
318		{
319		case '(':
320			++openParens;
321			isArg = true;
322			break;
323		case ')':
324			--openParens;
325			isArg = openParens != 0;
326			break;
327		case ',':
328			// The individual arguments are separated by comma tokens, but
329			// the comma tokens between matching inner parentheses do not
330			// seperate arguments.
331			if (openParens == 1) args->push_back(MacroArg());
332			isArg = openParens != 1;
333			break;
334		default:
335			isArg = true;
336			break;
337		}
338		if (isArg)
339		{
340			MacroArg& arg = args->back();
341			// Initial whitespace is not part of the argument.
342			if (arg.empty()) token.setHasLeadingSpace(false);
343			arg.push_back(token);
344		}
345	}
346
347	const Macro::Parameters& params = macro.parameters;
348	// If there is only one empty argument, it is equivalent to no argument.
349	if (params.empty() && (args->size() == 1) && args->front().empty())
350	{
351		args->clear();
352	}
353	// Validate the number of arguments.
354	if (args->size() != params.size())
355	{
356		Diagnostics::ID id = args->size() < macro.parameters.size() ?
357			Diagnostics::MACRO_TOO_FEW_ARGS :
358			Diagnostics::MACRO_TOO_MANY_ARGS;
359		mDiagnostics->report(id, identifier.location, identifier.text);
360		return false;
361	}
362
363	// Pre-expand each argument before substitution.
364	// This step expands each argument individually before they are
365	// inserted into the macro body.
366	for (size_t i = 0; i < args->size(); ++i)
367	{
368		MacroArg& arg = args->at(i);
369		TokenLexer lexer(&arg);
370		MacroExpander expander(&lexer, mMacroSet, mDiagnostics, mParseDefined);
371
372		arg.clear();
373		expander.lex(&token);
374		while (token.type != Token::LAST)
375		{
376			arg.push_back(token);
377			expander.lex(&token);
378		}
379	}
380	return true;
381}
382
383void MacroExpander::replaceMacroParams(const Macro& macro,
384                                       const std::vector<MacroArg>& args,
385                                       std::vector<Token>* replacements)
386{
387	for (size_t i = 0; i < macro.replacements.size(); ++i)
388	{
389		const Token& repl = macro.replacements[i];
390		if (repl.type != Token::IDENTIFIER)
391		{
392			replacements->push_back(repl);
393			continue;
394		}
395
396		// TODO(alokp): Optimize this.
397		// There is no need to search for macro params every time.
398		// The param index can be cached with the replacement token.
399		Macro::Parameters::const_iterator iter = std::find(
400			macro.parameters.begin(), macro.parameters.end(), repl.text);
401		if (iter == macro.parameters.end())
402		{
403			replacements->push_back(repl);
404			continue;
405		}
406
407		size_t iArg = std::distance(macro.parameters.begin(), iter);
408		const MacroArg& arg = args[iArg];
409		if (arg.empty())
410		{
411			continue;
412		}
413		size_t iRepl = replacements->size();
414		replacements->insert(replacements->end(), arg.begin(), arg.end());
415		// The replacement token inherits padding properties from
416		// macro replacement token.
417		replacements->at(iRepl).setHasLeadingSpace(repl.hasLeadingSpace());
418	}
419}
420
421}  // namespace pp
422
423