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 24 namespace pp 25 { 26 27 namespace 28 { 29 30 const size_t kMaxContextTokens = 10000; 31 32 class 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 65 class 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 77 MacroExpander::ScopedMacroReenabler::ScopedMacroReenabler(MacroExpander *expander) 78 : mExpander(expander) 79 { 80 mExpander->mDeferReenablingMacros = true; 81 } 82 83 MacroExpander::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 96 MacroExpander::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 111 MacroExpander::~MacroExpander() 112 { 113 assert(mMacrosToReenable.empty()); 114 for (MacroContext *context : mContextStack) 115 { 116 delete context; 117 } 118 } 119 120 void 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 200 void 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 226 void 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 241 bool MacroExpander::isNextTokenLeftParen() 242 { 243 Token token; 244 getToken(&token); 245 246 bool lparen = token.type == '('; 247 ungetToken(token); 248 249 return lparen; 250 } 251 252 bool 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 274 void 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 297 bool MacroExpander::expandMacro(const Macro ¯o, 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 355 bool MacroExpander::collectMacroArgs(const Macro ¯o, 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 ¶ms = 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 467 void MacroExpander::replaceMacroParams(const Macro ¯o, 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 513 MacroExpander::MacroContext::MacroContext() : macro(0), index(0) 514 { 515 } 516 517 MacroExpander::MacroContext::~MacroContext() 518 { 519 } 520 521 bool MacroExpander::MacroContext::empty() const 522 { 523 return index == replacements.size(); 524 } 525 526 const Token &MacroExpander::MacroContext::get() 527 { 528 return replacements[index++]; 529 } 530 531 void MacroExpander::MacroContext::unget() 532 { 533 assert(index > 0); 534 --index; 535 } 536 537 } // namespace pp 538 539