michael@0: //
michael@0: // Copyright (c) 2011 The ANGLE Project Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: //
michael@0: 
michael@0: #include "MacroExpander.h"
michael@0: 
michael@0: #include <algorithm>
michael@0: #include <sstream>
michael@0: 
michael@0: #include "DiagnosticsBase.h"
michael@0: #include "Token.h"
michael@0: 
michael@0: namespace pp
michael@0: {
michael@0: 
michael@0: class TokenLexer : public Lexer
michael@0: {
michael@0:  public:
michael@0:     typedef std::vector<Token> TokenVector;
michael@0: 
michael@0:     TokenLexer(TokenVector* tokens)
michael@0:     {
michael@0:         tokens->swap(mTokens);
michael@0:         mIter = mTokens.begin();
michael@0:     }
michael@0: 
michael@0:     virtual void lex(Token* token)
michael@0:     {
michael@0:         if (mIter == mTokens.end())
michael@0:         {
michael@0:             token->reset();
michael@0:             token->type = Token::LAST;
michael@0:         }
michael@0:         else
michael@0:         {
michael@0:             *token = *mIter++;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:  private:
michael@0:     PP_DISALLOW_COPY_AND_ASSIGN(TokenLexer);
michael@0: 
michael@0:     TokenVector mTokens;
michael@0:     TokenVector::const_iterator mIter;
michael@0: };
michael@0: 
michael@0: MacroExpander::MacroExpander(Lexer* lexer,
michael@0:                              MacroSet* macroSet,
michael@0:                              Diagnostics* diagnostics) :
michael@0:     mLexer(lexer),
michael@0:     mMacroSet(macroSet),
michael@0:     mDiagnostics(diagnostics)
michael@0: {
michael@0: }
michael@0: 
michael@0: MacroExpander::~MacroExpander()
michael@0: {
michael@0:     for (std::size_t i = 0; i < mContextStack.size(); ++i)
michael@0:     {
michael@0:         delete mContextStack[i];
michael@0:     }
michael@0: }
michael@0: 
michael@0: void MacroExpander::lex(Token* token)
michael@0: {
michael@0:     while (true)
michael@0:     {
michael@0:         getToken(token);
michael@0: 
michael@0:         if (token->type != Token::IDENTIFIER)
michael@0:             break;
michael@0: 
michael@0:         if (token->expansionDisabled())
michael@0:             break;
michael@0: 
michael@0:         MacroSet::const_iterator iter = mMacroSet->find(token->text);
michael@0:         if (iter == mMacroSet->end())
michael@0:             break;
michael@0: 
michael@0:         const Macro& macro = iter->second;
michael@0:         if (macro.disabled)
michael@0:         {
michael@0:             // If a particular token is not expanded, it is never expanded.
michael@0:             token->setExpansionDisabled(true);
michael@0:             break;
michael@0:         }
michael@0:         if ((macro.type == Macro::kTypeFunc) && !isNextTokenLeftParen())
michael@0:         {
michael@0:             // If the token immediately after the macro name is not a '(',
michael@0:             // this macro should not be expanded.
michael@0:             break;
michael@0:         }
michael@0: 
michael@0:         pushMacro(macro, *token);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void MacroExpander::getToken(Token* token)
michael@0: {
michael@0:     if (mReserveToken.get())
michael@0:     {
michael@0:         *token = *mReserveToken;
michael@0:         mReserveToken.reset();
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     // First pop all empty macro contexts.
michael@0:     while (!mContextStack.empty() && mContextStack.back()->empty())
michael@0:     {
michael@0:         popMacro();
michael@0:     }
michael@0: 
michael@0:     if (!mContextStack.empty())
michael@0:     {
michael@0:         *token = mContextStack.back()->get();
michael@0:     }
michael@0:     else
michael@0:     {
michael@0:         mLexer->lex(token);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void MacroExpander::ungetToken(const Token& token)
michael@0: {
michael@0:     if (!mContextStack.empty())
michael@0:     {
michael@0:         MacroContext* context = mContextStack.back();
michael@0:         context->unget();
michael@0:         assert(context->replacements[context->index] == token);
michael@0:     }
michael@0:     else
michael@0:     {
michael@0:         assert(!mReserveToken.get());
michael@0:         mReserveToken.reset(new Token(token));
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool MacroExpander::isNextTokenLeftParen()
michael@0: {
michael@0:     Token token;
michael@0:     getToken(&token);
michael@0: 
michael@0:     bool lparen = token.type == '(';
michael@0:     ungetToken(token);
michael@0: 
michael@0:     return lparen;
michael@0: }
michael@0: 
michael@0: bool MacroExpander::pushMacro(const Macro& macro, const Token& identifier)
michael@0: {
michael@0:     assert(!macro.disabled);
michael@0:     assert(!identifier.expansionDisabled());
michael@0:     assert(identifier.type == Token::IDENTIFIER);
michael@0:     assert(identifier.text == macro.name);
michael@0: 
michael@0:     std::vector<Token> replacements;
michael@0:     if (!expandMacro(macro, identifier, &replacements))
michael@0:         return false;
michael@0: 
michael@0:     // Macro is disabled for expansion until it is popped off the stack.
michael@0:     macro.disabled = true;
michael@0: 
michael@0:     MacroContext* context = new MacroContext;
michael@0:     context->macro = &macro;
michael@0:     context->replacements.swap(replacements);
michael@0:     mContextStack.push_back(context);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void MacroExpander::popMacro()
michael@0: {
michael@0:     assert(!mContextStack.empty());
michael@0: 
michael@0:     MacroContext* context = mContextStack.back();
michael@0:     mContextStack.pop_back();
michael@0: 
michael@0:     assert(context->empty());
michael@0:     assert(context->macro->disabled);
michael@0:     context->macro->disabled = false;
michael@0:     delete context;
michael@0: }
michael@0: 
michael@0: bool MacroExpander::expandMacro(const Macro& macro,
michael@0:                                 const Token& identifier,
michael@0:                                 std::vector<Token>* replacements)
michael@0: {
michael@0:     replacements->clear();
michael@0:     if (macro.type == Macro::kTypeObj)
michael@0:     {
michael@0:         replacements->assign(macro.replacements.begin(),
michael@0:                              macro.replacements.end());
michael@0: 
michael@0:         if (macro.predefined)
michael@0:         {
michael@0:             static const std::string kLine = "__LINE__";
michael@0:             static const std::string kFile = "__FILE__";
michael@0: 
michael@0:             assert(replacements->size() == 1);
michael@0:             Token& repl = replacements->front();
michael@0:             if (macro.name == kLine)
michael@0:             {
michael@0:                 std::ostringstream stream;
michael@0:                 stream << identifier.location.line;
michael@0:                 repl.text = stream.str();
michael@0:             }
michael@0:             else if (macro.name == kFile)
michael@0:             {
michael@0:                 std::ostringstream stream;
michael@0:                 stream << identifier.location.file;
michael@0:                 repl.text = stream.str();
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     else
michael@0:     {
michael@0:         assert(macro.type == Macro::kTypeFunc);
michael@0:         std::vector<MacroArg> args;
michael@0:         args.reserve(macro.parameters.size());
michael@0:         if (!collectMacroArgs(macro, identifier, &args))
michael@0:             return false;
michael@0: 
michael@0:         replaceMacroParams(macro, args, replacements);
michael@0:     }
michael@0: 
michael@0:     for (std::size_t i = 0; i < replacements->size(); ++i)
michael@0:     {
michael@0:         Token& repl = replacements->at(i);
michael@0:         if (i == 0)
michael@0:         {
michael@0:             // The first token in the replacement list inherits the padding
michael@0:             // properties of the identifier token.
michael@0:             repl.setAtStartOfLine(identifier.atStartOfLine());
michael@0:             repl.setHasLeadingSpace(identifier.hasLeadingSpace());
michael@0:         }
michael@0:         repl.location = identifier.location;
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool MacroExpander::collectMacroArgs(const Macro& macro,
michael@0:                                      const Token& identifier,
michael@0:                                      std::vector<MacroArg>* args)
michael@0: {
michael@0:     Token token;
michael@0:     getToken(&token);
michael@0:     assert(token.type == '(');
michael@0: 
michael@0:     args->push_back(MacroArg());
michael@0:     for (int openParens = 1; openParens != 0; )
michael@0:     {
michael@0:         getToken(&token);
michael@0: 
michael@0:         if (token.type == Token::LAST)
michael@0:         {
michael@0:             mDiagnostics->report(Diagnostics::MACRO_UNTERMINATED_INVOCATION,
michael@0:                                  identifier.location, identifier.text);
michael@0:             // Do not lose EOF token.
michael@0:             ungetToken(token);
michael@0:             return false;
michael@0:         }
michael@0: 
michael@0:         bool isArg = false; // True if token is part of the current argument.
michael@0:         switch (token.type)
michael@0:         {
michael@0:           case '(':
michael@0:             ++openParens;
michael@0:             isArg = true;
michael@0:             break;
michael@0:           case ')':
michael@0:             --openParens;
michael@0:             isArg = openParens != 0;
michael@0:             break;
michael@0:           case ',':
michael@0:             // The individual arguments are separated by comma tokens, but
michael@0:             // the comma tokens between matching inner parentheses do not
michael@0:             // seperate arguments.
michael@0:             if (openParens == 1) args->push_back(MacroArg());
michael@0:             isArg = openParens != 1;
michael@0:             break;
michael@0:           default:
michael@0:             isArg = true;
michael@0:             break;
michael@0:         }
michael@0:         if (isArg)
michael@0:         {
michael@0:             MacroArg& arg = args->back();
michael@0:             // Initial whitespace is not part of the argument.
michael@0:             if (arg.empty()) token.setHasLeadingSpace(false);
michael@0:             arg.push_back(token);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     const Macro::Parameters& params = macro.parameters;
michael@0:     // If there is only one empty argument, it is equivalent to no argument.
michael@0:     if (params.empty() && (args->size() == 1) && args->front().empty())
michael@0:     {
michael@0:         args->clear();
michael@0:     }
michael@0:     // Validate the number of arguments.
michael@0:     if (args->size() != params.size())
michael@0:     {
michael@0:         Diagnostics::ID id = args->size() < macro.parameters.size() ?
michael@0:             Diagnostics::MACRO_TOO_FEW_ARGS :
michael@0:             Diagnostics::MACRO_TOO_MANY_ARGS;
michael@0:         mDiagnostics->report(id, identifier.location, identifier.text);
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     // Pre-expand each argument before substitution.
michael@0:     // This step expands each argument individually before they are
michael@0:     // inserted into the macro body.
michael@0:     for (std::size_t i = 0; i < args->size(); ++i)
michael@0:     {
michael@0:         MacroArg& arg = args->at(i);
michael@0:         TokenLexer lexer(&arg);
michael@0:         MacroExpander expander(&lexer, mMacroSet, mDiagnostics);
michael@0: 
michael@0:         arg.clear();
michael@0:         expander.lex(&token);
michael@0:         while (token.type != Token::LAST)
michael@0:         {
michael@0:             arg.push_back(token);
michael@0:             expander.lex(&token);
michael@0:         }
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void MacroExpander::replaceMacroParams(const Macro& macro,
michael@0:                                        const std::vector<MacroArg>& args,
michael@0:                                        std::vector<Token>* replacements)
michael@0: {
michael@0:     for (std::size_t i = 0; i < macro.replacements.size(); ++i)
michael@0:     {
michael@0:         const Token& repl = macro.replacements[i];
michael@0:         if (repl.type != Token::IDENTIFIER)
michael@0:         {
michael@0:             replacements->push_back(repl);
michael@0:             continue;
michael@0:         }
michael@0: 
michael@0:         // TODO(alokp): Optimize this.
michael@0:         // There is no need to search for macro params every time.
michael@0:         // The param index can be cached with the replacement token.
michael@0:         Macro::Parameters::const_iterator iter = std::find(
michael@0:             macro.parameters.begin(), macro.parameters.end(), repl.text);
michael@0:         if (iter == macro.parameters.end())
michael@0:         {
michael@0:             replacements->push_back(repl);
michael@0:             continue;
michael@0:         }
michael@0: 
michael@0:         std::size_t iArg = std::distance(macro.parameters.begin(), iter);
michael@0:         const MacroArg& arg = args[iArg];
michael@0:         if (arg.empty())
michael@0:         {
michael@0:             continue;
michael@0:         }
michael@0:         std::size_t iRepl = replacements->size();
michael@0:         replacements->insert(replacements->end(), arg.begin(), arg.end());
michael@0:         // The replacement token inherits padding properties from
michael@0:         // macro replacement token.
michael@0:         replacements->at(iRepl).setHasLeadingSpace(repl.hasLeadingSpace());
michael@0:     }
michael@0: }
michael@0: 
michael@0: }  // namespace pp
michael@0: