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