• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //
2 // Copyright 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 
16 namespace angle
17 {
18 
19 namespace pp
20 {
21 
22 namespace
23 {
24 
25 const size_t kMaxContextTokens = 10000;
26 
27 class TokenLexer : public Lexer
28 {
29   public:
30     typedef std::vector<Token> TokenVector;
31 
TokenLexer(TokenVector * tokens)32     TokenLexer(TokenVector *tokens)
33     {
34         tokens->swap(mTokens);
35         mIter = mTokens.begin();
36     }
37 
lex(Token * token)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 
58 class [[nodiscard]] MacroExpander::ScopedMacroReenabler final : angle::NonCopyable
59 {
60   public:
61     ScopedMacroReenabler(MacroExpander *expander);
62     ~ScopedMacroReenabler();
63 
64   private:
65     MacroExpander *mExpander;
66 };
67 
ScopedMacroReenabler(MacroExpander * expander)68 MacroExpander::ScopedMacroReenabler::ScopedMacroReenabler(MacroExpander *expander)
69     : mExpander(expander)
70 {
71     mExpander->mDeferReenablingMacros = true;
72 }
73 
~ScopedMacroReenabler()74 MacroExpander::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 
MacroExpander(Lexer * lexer,MacroSet * macroSet,Diagnostics * diagnostics,const PreprocessorSettings & settings,bool parseDefined)87 MacroExpander::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 
~MacroExpander()101 MacroExpander::~MacroExpander()
102 {
103     ASSERT(mMacrosToReenable.empty());
104     for (MacroContext *context : mContextStack)
105     {
106         delete context;
107     }
108 }
109 
lex(Token * token)110 void 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 
getToken(Token * token)194 void 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 
ungetToken(const Token & token)220 void 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 
isNextTokenLeftParen()235 bool MacroExpander::isNextTokenLeftParen()
236 {
237     Token token;
238     getToken(&token);
239 
240     bool lparen = token.type == '(';
241     ungetToken(token);
242 
243     return lparen;
244 }
245 
pushMacro(std::shared_ptr<Macro> macro,const Token & identifier)246 bool 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 
popMacro()268 void 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 
expandMacro(const Macro & macro,const Token & identifier,std::vector<Token> * replacements)291 bool 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 
collectMacroArgs(const Macro & macro,const Token & identifier,std::vector<MacroArg> * args,SourceLocation * closingParenthesisLocation)349 bool 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 
replaceMacroParams(const Macro & macro,const std::vector<MacroArg> & args,std::vector<Token> * replacements)463 void 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 
MacroContext()509 MacroExpander::MacroContext::MacroContext() : macro(0), index(0) {}
510 
~MacroContext()511 MacroExpander::MacroContext::~MacroContext() {}
512 
empty() const513 bool MacroExpander::MacroContext::empty() const
514 {
515     return index == replacements.size();
516 }
517 
get()518 const Token &MacroExpander::MacroContext::get()
519 {
520     return replacements[index++];
521 }
522 
unget()523 void MacroExpander::MacroContext::unget()
524 {
525     ASSERT(index > 0);
526     --index;
527 }
528 
529 }  // namespace pp
530 
531 }  // namespace angle
532