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
23 namespace pp
24 {
25
26 class TokenLexer : public Lexer
27 {
28 public:
29 typedef std::vector<Token> TokenVector;
30
TokenLexer(TokenVector * tokens)31 TokenLexer(TokenVector* tokens)
32 {
33 tokens->swap(mTokens);
34 mIter = mTokens.begin();
35 }
36
lex(Token * token)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
MacroExpander(Lexer * lexer,MacroSet * macroSet,Diagnostics * diagnostics,bool parseDefined)57 MacroExpander::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
~MacroExpander()66 MacroExpander::~MacroExpander()
67 {
68 for (size_t i = 0; i < mContextStack.size(); ++i)
69 {
70 delete mContextStack[i];
71 }
72
73 delete mReserveToken;
74 }
75
lex(Token * token)76 void 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
getToken(Token * token)151 void 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
ungetToken(const Token & token)177 void 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
isNextTokenLeftParen()192 bool MacroExpander::isNextTokenLeftParen()
193 {
194 Token token;
195 getToken(&token);
196
197 bool lparen = token.type == '(';
198 ungetToken(token);
199
200 return lparen;
201 }
202
pushMacro(const Macro & macro,const Token & identifier)203 bool 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 = ¯o;
219 context->replacements.swap(replacements);
220 mContextStack.push_back(context);
221 return true;
222 }
223
popMacro()224 void 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
expandMacro(const Macro & macro,const Token & identifier,std::vector<Token> * replacements)237 bool 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
collectMacroArgs(const Macro & macro,const Token & identifier,std::vector<MacroArg> * args)294 bool 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
replaceMacroParams(const Macro & macro,const std::vector<MacroArg> & args,std::vector<Token> * replacements)383 void 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