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