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 <cassert>
19
20#include "DiagnosticsBase.h"
21#include "pp_utils.h"
22#include "Token.h"
23
24namespace pp
25{
26
27namespace
28{
29
30const size_t kMaxContextTokens = 10000;
31
32class TokenLexer : public Lexer
33{
34 public:
35 typedef std::vector<Token> TokenVector;
36
37 TokenLexer(TokenVector *tokens)
38 {
39 tokens->swap(mTokens);
40 mIter = mTokens.begin();
41 }
42
43 void lex(Token *token) override
44 {
45 if (mIter == mTokens.end())
46 {
47 token->reset();
48 token->type = Token::LAST;
49 }
50 else
51 {
52 *token = *mIter++;
53 }
54 }
55
56 private:
57 PP_DISALLOW_COPY_AND_ASSIGN(TokenLexer);
58
59 TokenVector mTokens;
60 TokenVector::const_iterator mIter;
61};
62
63} // anonymous namespace
64
65class MacroExpander::ScopedMacroReenabler final
66{
67 public:
68 ScopedMacroReenabler(MacroExpander *expander);
69 ~ScopedMacroReenabler();
70
71 private:
72 PP_DISALLOW_COPY_AND_ASSIGN(ScopedMacroReenabler);
73
74 MacroExpander *mExpander;
75};
76
77MacroExpander::ScopedMacroReenabler::ScopedMacroReenabler(MacroExpander *expander)
78 : mExpander(expander)
79{
80 mExpander->mDeferReenablingMacros = true;
81}
82
83MacroExpander::ScopedMacroReenabler::~ScopedMacroReenabler()
84{
85 mExpander->mDeferReenablingMacros = false;
86 for (auto macro : mExpander->mMacrosToReenable)
87 {
88 // Copying the string here by using substr is a check for use-after-free. It detects
89 // use-after-free more reliably than just toggling the disabled flag.
90 assert(macro->name.substr() != "");
91 macro->disabled = false;
92 }
93 mExpander->mMacrosToReenable.clear();
94}
95
96MacroExpander::MacroExpander(Lexer *lexer,
97 MacroSet *macroSet,
98 Diagnostics *diagnostics,
99 bool parseDefined,
100 int allowedMacroExpansionDepth)
101 : mLexer(lexer),
102 mMacroSet(macroSet),
103 mDiagnostics(diagnostics),
104 mParseDefined(parseDefined),
105 mTotalTokensInContexts(0),
106 mAllowedMacroExpansionDepth(allowedMacroExpansionDepth),
107 mDeferReenablingMacros(false)
108{
109}
110
111MacroExpander::~MacroExpander()
112{
113 assert(mMacrosToReenable.empty());
114 for (MacroContext *context : mContextStack)
115 {
116 delete context;
117 }
118}
119
120void MacroExpander::lex(Token *token)
121{
122 while (true)
123 {
124 getToken(token);
125
126 if (token->type != Token::IDENTIFIER)
127 break;
128
129 // Defined operator is parsed here since it may be generated by macro expansion.
130 // Defined operator produced by macro expansion has undefined behavior according to C++
131 // spec, which the GLSL spec references (see C++14 draft spec section 16.1.4), but this
132 // behavior is needed for passing dEQP tests, which enforce stricter compatibility between
133 // implementations.
134 if (mParseDefined && token->text == "defined")
135 {
136 bool paren = false;
137 getToken(token);
138 if (token->type == '(')
139 {
140 paren = true;
141 getToken(token);
142 }
143 if (token->type != Token::IDENTIFIER)
144 {
145 mDiagnostics->report(Diagnostics::PP_UNEXPECTED_TOKEN, token->location,
146 token->text);
147 break;
148 }
149 auto iter = mMacroSet->find(token->text);
150 std::string expression = iter != mMacroSet->end() ? "1" : "0";
151
152 if (paren)
153 {
154 getToken(token);
155 if (token->type != ')')
156 {
157 mDiagnostics->report(Diagnostics::PP_UNEXPECTED_TOKEN, token->location,
158 token->text);
159 break;
160 }
161 }
162
163 // We have a valid defined operator.
164 // Convert the current token into a CONST_INT token.
165 token->type = Token::CONST_INT;
166 token->text = expression;
167 break;
168 }
169
170 if (token->expansionDisabled())
171 break;
172
173 MacroSet::const_iterator iter = mMacroSet->find(token->text);
174 if (iter == mMacroSet->end())
175 break;
176
177 std::shared_ptr<Macro> macro = iter->second;
178 if (macro->disabled)
179 {
180 // If a particular token is not expanded, it is never expanded.
181 token->setExpansionDisabled(true);
182 break;
183 }
184
185 // Bump the expansion count before peeking if the next token is a '('
186 // otherwise there could be a #undef of the macro before the next token.
187 macro->expansionCount++;
188 if ((macro->type == Macro::kTypeFunc) && !isNextTokenLeftParen())
189 {
190 // If the token immediately after the macro name is not a '(',
191 // this macro should not be expanded.
192 macro->expansionCount--;
193 break;
194 }
195
196 pushMacro(macro, *token);
197 }
198}
199
200void MacroExpander::getToken(Token *token)
201{
202 if (mReserveToken.get())
203 {
204 *token = *mReserveToken;
205 mReserveToken.reset();
206 return;
207 }
208
209 // First pop all empty macro contexts.
210 while (!mContextStack.empty() && mContextStack.back()->empty())
211 {
212 popMacro();
213 }
214
215 if (!mContextStack.empty())
216 {
217 *token = mContextStack.back()->get();
218 }
219 else
220 {
221 assert(mTotalTokensInContexts == 0);
222 mLexer->lex(token);
223 }
224}
225
226void MacroExpander::ungetToken(const Token &token)
227{
228 if (!mContextStack.empty())
229 {
230 MacroContext *context = mContextStack.back();
231 context->unget();
232 assert(context->replacements[context->index] == token);
233 }
234 else
235 {
236 assert(!mReserveToken.get());
237 mReserveToken.reset(new Token(token));
238 }
239}
240
241bool MacroExpander::isNextTokenLeftParen()
242{
243 Token token;
244 getToken(&token);
245
246 bool lparen = token.type == '(';
247 ungetToken(token);
248
249 return lparen;
250}
251
252bool MacroExpander::pushMacro(std::shared_ptr<Macro> macro, const Token &identifier)
253{
254 assert(!macro->disabled);
255 assert(!identifier.expansionDisabled());
256 assert(identifier.type == Token::IDENTIFIER);
257 assert(identifier.text == macro->name);
258
259 std::vector<Token> replacements;
260 if (!expandMacro(*macro, identifier, &replacements))
261 return false;
262
263 // Macro is disabled for expansion until it is popped off the stack.
264 macro->disabled = true;
265
266 MacroContext *context = new MacroContext;
267 context->macro = macro;
268 context->replacements.swap(replacements);
269 mContextStack.push_back(context);
270 mTotalTokensInContexts += context->replacements.size();
271 return true;
272}
273
274void MacroExpander::popMacro()
275{
276 assert(!mContextStack.empty());
277
278 MacroContext *context = mContextStack.back();
279 mContextStack.pop_back();
280
281 assert(context->empty());
282 assert(context->macro->disabled);
283 assert(context->macro->expansionCount > 0);
284 if (mDeferReenablingMacros)
285 {
286 mMacrosToReenable.push_back(context->macro);
287 }
288 else
289 {
290 context->macro->disabled = false;
291 }
292 context->macro->expansionCount--;
293 mTotalTokensInContexts -= context->replacements.size();
294 delete context;
295}
296
297bool MacroExpander::expandMacro(const Macro &macro,
298 const Token &identifier,
299 std::vector<Token> *replacements)
300{
301 replacements->clear();
302
303 // In the case of an object-like macro, the replacement list gets its location
304 // from the identifier, but in the case of a function-like macro, the replacement
305 // list gets its location from the closing parenthesis of the macro invocation.
306 // This is tested by dEQP-GLES3.functional.shaders.preprocessor.predefined_macros.*
307 SourceLocation replacementLocation = identifier.location;
308 if (macro.type == Macro::kTypeObj)
309 {
310 replacements->assign(macro.replacements.begin(), macro.replacements.end());
311
312 if (macro.predefined)
313 {
314 const char kLine[] = "__LINE__";
315 const char kFile[] = "__FILE__";
316
317 assert(replacements->size() == 1);
318 Token &repl = replacements->front();
319 if (macro.name == kLine)
320 {
321 repl.text = std::to_string(identifier.location.line);
322 }
323 else if (macro.name == kFile)
324 {
325 repl.text = std::to_string(identifier.location.file);
326 }
327 }
328 }
329 else
330 {
331 assert(macro.type == Macro::kTypeFunc);
332 std::vector<MacroArg> args;
333 args.reserve(macro.parameters.size());
334 if (!collectMacroArgs(macro, identifier, &args, &replacementLocation))
335 return false;
336
337 replaceMacroParams(macro, args, replacements);
338 }
339
340 for (std::size_t i = 0; i < replacements->size(); ++i)
341 {
342 Token &repl = replacements->at(i);
343 if (i == 0)
344 {
345 // The first token in the replacement list inherits the padding
346 // properties of the identifier token.
347 repl.setAtStartOfLine(identifier.atStartOfLine());
348 repl.setHasLeadingSpace(identifier.hasLeadingSpace());
349 }
350 repl.location = replacementLocation;
351 }
352 return true;
353}
354
355bool MacroExpander::collectMacroArgs(const Macro &macro,
356 const Token &identifier,
357 std::vector<MacroArg> *args,
358 SourceLocation *closingParenthesisLocation)
359{
360 Token token;
361 getToken(&token);
362 assert(token.type == '(');
363
364 args->push_back(MacroArg());
365
366 // Defer reenabling macros until args collection is finished to avoid the possibility of
367 // infinite recursion. Otherwise infinite recursion might happen when expanding the args after
368 // macros have been popped from the context stack when parsing the args.
369 ScopedMacroReenabler deferReenablingMacros(this);
370
371 int openParens = 1;
372 while (openParens != 0)
373 {
374 getToken(&token);
375
376 if (token.type == Token::LAST)
377 {
378 mDiagnostics->report(Diagnostics::PP_MACRO_UNTERMINATED_INVOCATION, identifier.location,
379 identifier.text);
380 // Do not lose EOF token.
381 ungetToken(token);
382 return false;
383 }
384
385 bool isArg = false; // True if token is part of the current argument.
386 switch (token.type)
387 {
388 case '(':
389 ++openParens;
390 isArg = true;
391 break;
392 case ')':
393 --openParens;
394 isArg = openParens != 0;
395 *closingParenthesisLocation = token.location;
396 break;
397 case ',':
398 // The individual arguments are separated by comma tokens, but
399 // the comma tokens between matching inner parentheses do not
400 // seperate arguments.
401 if (openParens == 1)
402 args->push_back(MacroArg());
403 isArg = openParens != 1;
404 break;
405 default:
406 isArg = true;
407 break;
408 }
409 if (isArg)
410 {
411 MacroArg &arg = args->back();
412 // Initial whitespace is not part of the argument.
413 if (arg.empty())
414 token.setHasLeadingSpace(false);
415 arg.push_back(token);
416 }
417 }
418
419 const Macro::Parameters &params = macro.parameters;
420 // If there is only one empty argument, it is equivalent to no argument.
421 if (params.empty() && (args->size() == 1) && args->front().empty())
422 {
423 args->clear();
424 }
425 // Validate the number of arguments.
426 if (args->size() != params.size())
427 {
428 Diagnostics::ID id = args->size() < macro.parameters.size() ?
429 Diagnostics::PP_MACRO_TOO_FEW_ARGS :
430 Diagnostics::PP_MACRO_TOO_MANY_ARGS;
431 mDiagnostics->report(id, identifier.location, identifier.text);
432 return false;
433 }
434
435 // Pre-expand each argument before substitution.
436 // This step expands each argument individually before they are
437 // inserted into the macro body.
438 size_t numTokens = 0;
439 for (auto &arg : *args)
440 {
441 TokenLexer lexer(&arg);
442 if (mAllowedMacroExpansionDepth < 1)
443 {
444 mDiagnostics->report(Diagnostics::PP_MACRO_INVOCATION_CHAIN_TOO_DEEP,
445 token.location, token.text);
446 return false;
447 }
448 MacroExpander expander(&lexer, mMacroSet, mDiagnostics, mParseDefined, mAllowedMacroExpansionDepth - 1);
449
450 arg.clear();
451 expander.lex(&token);
452 while (token.type != Token::LAST)
453 {
454 arg.push_back(token);
455 expander.lex(&token);
456 numTokens++;
457 if (numTokens + mTotalTokensInContexts > kMaxContextTokens)
458 {
459 mDiagnostics->report(Diagnostics::PP_OUT_OF_MEMORY, token.location, token.text);
460 return false;
461 }
462 }
463 }
464 return true;
465}
466
467void MacroExpander::replaceMacroParams(const Macro &macro,
468 const std::vector<MacroArg> &args,
469 std::vector<Token> *replacements)
470{
471 for (std::size_t i = 0; i < macro.replacements.size(); ++i)
472 {
473 if (!replacements->empty() &&
474 replacements->size() + mTotalTokensInContexts > kMaxContextTokens)
475 {
476 const Token &token = replacements->back();
477 mDiagnostics->report(Diagnostics::PP_OUT_OF_MEMORY, token.location, token.text);
478 return;
479 }
480
481 const Token &repl = macro.replacements[i];
482 if (repl.type != Token::IDENTIFIER)
483 {
484 replacements->push_back(repl);
485 continue;
486 }
487
488 // TODO(alokp): Optimize this.
489 // There is no need to search for macro params every time.
490 // The param index can be cached with the replacement token.
491 Macro::Parameters::const_iterator iter =
492 std::find(macro.parameters.begin(), macro.parameters.end(), repl.text);
493 if (iter == macro.parameters.end())
494 {
495 replacements->push_back(repl);
496 continue;
497 }
498
499 std::size_t iArg = std::distance(macro.parameters.begin(), iter);
500 const MacroArg &arg = args[iArg];
501 if (arg.empty())
502 {
503 continue;
504 }
505 std::size_t iRepl = replacements->size();
506 replacements->insert(replacements->end(), arg.begin(), arg.end());
507 // The replacement token inherits padding properties from
508 // macro replacement token.
509 replacements->at(iRepl).setHasLeadingSpace(repl.hasLeadingSpace());
510 }
511}
512
513MacroExpander::MacroContext::MacroContext() : macro(0), index(0)
514{
515}
516
517MacroExpander::MacroContext::~MacroContext()
518{
519}
520
521bool MacroExpander::MacroContext::empty() const
522{
523 return index == replacements.size();
524}
525
526const Token &MacroExpander::MacroContext::get()
527{
528 return replacements[index++];
529}
530
531void MacroExpander::MacroContext::unget()
532{
533 assert(index > 0);
534 --index;
535}
536
537} // namespace pp
538
539