591 lines · cpp
1//===--- MacroCallReconstructor.cpp - Format C++ code -----------*- C++ -*-===//2//3// The LLVM Compiler Infrastructure4//5// This file is distributed under the University of Illinois Open Source6// License. See LICENSE.TXT for details.7//8//===----------------------------------------------------------------------===//9///10/// \file11/// This file contains the implementation of MacroCallReconstructor, which fits12/// an reconstructed macro call to a parsed set of UnwrappedLines.13///14//===----------------------------------------------------------------------===//15 16#include "Macros.h"17 18#include "UnwrappedLineParser.h"19#include "clang/Basic/TokenKinds.h"20#include "llvm/ADT/DenseSet.h"21#include "llvm/Support/Debug.h"22#include <cassert>23 24#define DEBUG_TYPE "format-reconstruct"25 26namespace clang {27namespace format {28 29// Call \p Call for each token in the unwrapped line given, passing30// the token, its parent and whether it is the first token in the line.31template <typename T>32void forEachToken(const UnwrappedLine &Line, const T &Call,33 FormatToken *Parent = nullptr) {34 bool First = true;35 for (const auto &N : Line.Tokens) {36 Call(N.Tok, Parent, First, Line.Level);37 First = false;38 for (const auto &Child : N.Children)39 forEachToken(Child, Call, N.Tok);40 }41}42 43MacroCallReconstructor::MacroCallReconstructor(44 unsigned Level,45 const llvm::DenseMap<FormatToken *, std::unique_ptr<UnwrappedLine>>46 &ActiveExpansions)47 : Result(Level), IdToReconstructed(ActiveExpansions) {48 Result.Tokens.push_back(std::make_unique<LineNode>());49 ActiveReconstructedLines.push_back(&Result);50}51 52void MacroCallReconstructor::addLine(const UnwrappedLine &Line) {53 assert(State != Finalized);54 LLVM_DEBUG(llvm::dbgs() << "MCR: new line...\n");55 forEachToken(Line, [&](FormatToken *Token, FormatToken *Parent, bool First,56 unsigned Level) { add(Token, Parent, First, Level); });57 assert(InProgress || finished());58}59 60UnwrappedLine MacroCallReconstructor::takeResult() && {61 finalize();62 assert(Result.Tokens.size() == 1 &&63 Result.Tokens.front()->Children.size() == 1);64 UnwrappedLine Final = createUnwrappedLine(65 *Result.Tokens.front()->Children.front(), Result.Level);66 assert(!Final.Tokens.empty());67 return Final;68}69 70// Reconstruct the position of the next \p Token, given its parent \p71// ExpandedParent in the incoming unwrapped line. \p First specifies whether it72// is the first token in a given unwrapped line.73void MacroCallReconstructor::add(FormatToken *Token,74 FormatToken *ExpandedParent, bool First,75 unsigned Level) {76 LLVM_DEBUG(77 llvm::dbgs() << "MCR: Token: " << Token->TokenText << ", Parent: "78 << (ExpandedParent ? ExpandedParent->TokenText : "<null>")79 << ", First: " << First << "\n");80 // In order to be able to find the correct parent in the reconstructed token81 // stream, we need to continue the last open reconstruction until we find the82 // given token if it is part of the reconstructed token stream.83 //84 // Note that hidden tokens can be part of the reconstructed stream in nested85 // macro calls.86 // For example, given87 // #define C(x, y) x y88 // #define B(x) {x}89 // And the call:90 // C(a, B(b))91 // The outer macro call will be C(a, {b}), and the hidden token '}' can be92 // found in the reconstructed token stream of that expansion level.93 // In the expanded token stream94 // a {b}95 // 'b' is a child of '{'. We need to continue the open expansion of the ','96 // in the call of 'C' in order to correctly set the ',' as the parent of '{',97 // so we later set the spelled token 'b' as a child of the ','.98 if (!ActiveExpansions.empty() && Token->MacroCtx &&99 (Token->MacroCtx->Role != MR_Hidden ||100 ActiveExpansions.size() != Token->MacroCtx->ExpandedFrom.size())) {101 if (/*PassedMacroComma = */ reconstructActiveCallUntil(Token))102 First = true;103 }104 105 prepareParent(ExpandedParent, First, Level);106 107 if (Token->MacroCtx) {108 // If this token was generated by a macro call, add the reconstructed109 // equivalent of the token.110 reconstruct(Token);111 } else {112 // Otherwise, we add it to the current line.113 appendToken(Token);114 }115}116 117// Adjusts the stack of active reconstructed lines so we're ready to push118// tokens. The tokens to be pushed are children of ExpandedParent in the119// expanded code.120//121// This may entail:122// - creating a new line, if the parent is on the active line123// - popping active lines, if the parent is further up the stack124//125// Postcondition:126// ActiveReconstructedLines.back() is the line that has \p ExpandedParent or its127// reconstructed replacement token as a parent (when possible) - that is, the128// last token in \c ActiveReconstructedLines[ActiveReconstructedLines.size()-2]129// is the parent of ActiveReconstructedLines.back() in the reconstructed130// unwrapped line.131void MacroCallReconstructor::prepareParent(FormatToken *ExpandedParent,132 bool NewLine, unsigned Level) {133 LLVM_DEBUG({134 llvm::dbgs() << "ParentMap:\n";135 debugParentMap();136 });137 // We want to find the parent in the new unwrapped line, where the expanded138 // parent might have been replaced during reconstruction.139 FormatToken *Parent = getParentInResult(ExpandedParent);140 LLVM_DEBUG(llvm::dbgs() << "MCR: New parent: "141 << (Parent ? Parent->TokenText : "<null>") << "\n");142 143 FormatToken *OpenMacroParent = nullptr;144 if (!MacroCallStructure.empty()) {145 // Inside a macro expansion, it is possible to lose track of the correct146 // parent - either because it is already popped, for example because it was147 // in a different macro argument (e.g. M({, })), or when we work on invalid148 // code.149 // Thus, we use the innermost macro call's parent as the parent at which150 // we stop; this allows us to stay within the macro expansion and keeps151 // any problems confined to the extent of the macro call.152 OpenMacroParent =153 getParentInResult(MacroCallStructure.back().MacroCallLParen);154 LLVM_DEBUG(llvm::dbgs()155 << "MacroCallLParen: "156 << MacroCallStructure.back().MacroCallLParen->TokenText157 << ", OpenMacroParent: "158 << (OpenMacroParent ? OpenMacroParent->TokenText : "<null>")159 << "\n");160 }161 if (NewLine ||162 (!ActiveReconstructedLines.back()->Tokens.empty() &&163 Parent == ActiveReconstructedLines.back()->Tokens.back()->Tok)) {164 // If we are at the first token in a new line, we want to also165 // create a new line in the resulting reconstructed unwrapped line.166 while (ActiveReconstructedLines.back()->Tokens.empty() ||167 (Parent != ActiveReconstructedLines.back()->Tokens.back()->Tok &&168 ActiveReconstructedLines.back()->Tokens.back()->Tok !=169 OpenMacroParent)) {170 ActiveReconstructedLines.pop_back();171 assert(!ActiveReconstructedLines.empty());172 }173 assert(!ActiveReconstructedLines.empty());174 ActiveReconstructedLines.back()->Tokens.back()->Children.push_back(175 std::make_unique<ReconstructedLine>(Level));176 ActiveReconstructedLines.push_back(177 &*ActiveReconstructedLines.back()->Tokens.back()->Children.back());178 } else if (parentLine().Tokens.back()->Tok != Parent) {179 // If we're not the first token in a new line, pop lines until we find180 // the child of \c Parent in the stack.181 while (Parent != parentLine().Tokens.back()->Tok &&182 parentLine().Tokens.back()->Tok &&183 parentLine().Tokens.back()->Tok != OpenMacroParent) {184 ActiveReconstructedLines.pop_back();185 assert(!ActiveReconstructedLines.empty());186 }187 }188 assert(!ActiveReconstructedLines.empty());189}190 191// For a given \p Parent in the incoming expanded token stream, find the192// corresponding parent in the output.193FormatToken *MacroCallReconstructor::getParentInResult(FormatToken *Parent) {194 FormatToken *Mapped = SpelledParentToReconstructedParent.lookup(Parent);195 if (!Mapped)196 return Parent;197 for (; Mapped; Mapped = SpelledParentToReconstructedParent.lookup(Parent))198 Parent = Mapped;199 // If we use a different token than the parent in the expanded token stream200 // as parent, mark it as a special parent, so the formatting code knows it201 // needs to have its children formatted.202 Parent->MacroParent = true;203 return Parent;204}205 206// Reconstruct a \p Token that was expanded from a macro call.207void MacroCallReconstructor::reconstruct(FormatToken *Token) {208 assert(Token->MacroCtx);209 // A single token can be the only result of a macro call:210 // Given: #define ID(x, y) ;211 // And the call: ID(<some>, <tokens>)212 // ';' in the expanded stream will reconstruct all of ID(<some>, <tokens>).213 if (Token->MacroCtx->StartOfExpansion) {214 startReconstruction(Token);215 // If the order of tokens in the expanded token stream is not the216 // same as the order of tokens in the reconstructed stream, we need217 // to reconstruct tokens that arrive later in the stream.218 if (Token->MacroCtx->Role != MR_Hidden)219 reconstructActiveCallUntil(Token);220 }221 assert(!ActiveExpansions.empty());222 if (ActiveExpansions.back().SpelledI != ActiveExpansions.back().SpelledE) {223 assert(ActiveExpansions.size() == Token->MacroCtx->ExpandedFrom.size());224 if (Token->MacroCtx->Role != MR_Hidden) {225 // The current token in the reconstructed token stream must be the token226 // we're looking for - we either arrive here after startReconstruction,227 // which initiates the stream to the first token, or after228 // continueReconstructionUntil skipped until the expected token in the229 // reconstructed stream at the start of add(...).230 assert(ActiveExpansions.back().SpelledI->Tok == Token);231 processNextReconstructed();232 } else if (!currentLine()->Tokens.empty()) {233 // Map all hidden tokens to the last visible token in the output.234 // If the hidden token is a parent, we'll use the last visible235 // token as the parent of the hidden token's children.236 SpelledParentToReconstructedParent[Token] =237 currentLine()->Tokens.back()->Tok;238 } else {239 for (auto I = ActiveReconstructedLines.rbegin(),240 E = ActiveReconstructedLines.rend();241 I != E; ++I) {242 if (!(*I)->Tokens.empty()) {243 SpelledParentToReconstructedParent[Token] = (*I)->Tokens.back()->Tok;244 break;245 }246 }247 }248 }249 if (Token->MacroCtx->EndOfExpansion)250 endReconstruction(Token);251}252 253// Given a \p Token that starts an expansion, reconstruct the beginning of the254// macro call.255// For example, given: #define ID(x) x256// And the call: ID(int a)257// Reconstructs: ID(258void MacroCallReconstructor::startReconstruction(FormatToken *Token) {259 assert(Token->MacroCtx);260 assert(!Token->MacroCtx->ExpandedFrom.empty());261 assert(ActiveExpansions.size() <= Token->MacroCtx->ExpandedFrom.size());262#ifndef NDEBUG263 // Check that the token's reconstruction stack matches our current264 // reconstruction stack.265 for (size_t I = 0; I < ActiveExpansions.size(); ++I) {266 assert(ActiveExpansions[I].ID ==267 Token->MacroCtx268 ->ExpandedFrom[Token->MacroCtx->ExpandedFrom.size() - 1 - I]);269 }270#endif271 // Start reconstruction for all calls for which this token is the first token272 // generated by the call.273 // Note that the token's expanded from stack is inside-to-outside, and the274 // expansions for which this token is not the first are the outermost ones.275 ArrayRef<FormatToken *> StartedMacros =276 ArrayRef(Token->MacroCtx->ExpandedFrom)277 .drop_back(ActiveExpansions.size());278 assert(StartedMacros.size() == Token->MacroCtx->StartOfExpansion);279 // We reconstruct macro calls outside-to-inside.280 for (FormatToken *ID : llvm::reverse(StartedMacros)) {281 // We found a macro call to be reconstructed; the next time our282 // reconstruction stack is empty we know we finished an reconstruction.283#ifndef NDEBUG284 State = InProgress;285#endif286 // Put the reconstructed macro call's token into our reconstruction stack.287 auto IU = IdToReconstructed.find(ID);288 assert(IU != IdToReconstructed.end());289 ActiveExpansions.push_back(290 {ID, IU->second->Tokens.begin(), IU->second->Tokens.end()});291 // Process the macro call's identifier.292 processNextReconstructed();293 if (ActiveExpansions.back().SpelledI == ActiveExpansions.back().SpelledE)294 continue;295 if (ActiveExpansions.back().SpelledI->Tok->is(tok::l_paren)) {296 // Process the optional opening parenthesis.297 processNextReconstructed();298 }299 }300}301 302// Add all tokens in the reconstruction stream to the output until we find the303// given \p Token.304bool MacroCallReconstructor::reconstructActiveCallUntil(FormatToken *Token) {305 assert(!ActiveExpansions.empty());306 bool PassedMacroComma = false;307 // FIXME: If Token was already expanded earlier, due to308 // a change in order, we will not find it, but need to309 // skip it.310 while (ActiveExpansions.back().SpelledI != ActiveExpansions.back().SpelledE &&311 ActiveExpansions.back().SpelledI->Tok != Token) {312 PassedMacroComma = processNextReconstructed() || PassedMacroComma;313 }314 return PassedMacroComma;315}316 317// End all reconstructions for which \p Token is the final token.318void MacroCallReconstructor::endReconstruction(FormatToken *Token) {319 assert(Token->MacroCtx &&320 (ActiveExpansions.size() >= Token->MacroCtx->EndOfExpansion));321 for (size_t I = 0; I < Token->MacroCtx->EndOfExpansion; ++I) {322 LLVM_DEBUG([&] {323 // Check all remaining tokens but the final closing parenthesis and324 // optional trailing comment were already reconstructed at an inner325 // expansion level.326 for (auto T = ActiveExpansions.back().SpelledI;327 T != ActiveExpansions.back().SpelledE; ++T) {328 FormatToken *Token = T->Tok;329 bool ClosingParen = (std::next(T) == ActiveExpansions.back().SpelledE ||330 std::next(T)->Tok->isTrailingComment()) &&331 !Token->MacroCtx && Token->is(tok::r_paren);332 bool TrailingComment = Token->isTrailingComment();333 bool PreviousLevel =334 Token->MacroCtx &&335 (ActiveExpansions.size() < Token->MacroCtx->ExpandedFrom.size());336 if (!ClosingParen && !TrailingComment && !PreviousLevel)337 llvm::dbgs() << "At token: " << Token->TokenText << "\n";338 // In addition to the following cases, we can also run into this339 // when a macro call had more arguments than expected; in that case,340 // the comma and the remaining tokens in the macro call will341 // potentially end up in the line when we finish the expansion.342 // FIXME: Add the information which arguments are unused, and assert343 // one of the cases below plus reconstructed macro argument tokens.344 // assert(ClosingParen || TrailingComment || PreviousLevel);345 }346 }());347 // Handle the remaining open tokens:348 // - expand the closing parenthesis, if it exists, including an optional349 // trailing comment350 // - handle tokens that were already reconstructed at an inner expansion351 // level352 // - handle tokens when a macro call had more than the expected number of353 // arguments, i.e. when #define M(x) is called as M(a, b, c) we'll end354 // up with the sequence ", b, c)" being open at the end of the355 // reconstruction; we want to gracefully handle that case356 //357 // FIXME: See the above debug-check for what we will need to do to be358 // able to assert this.359 for (auto T = ActiveExpansions.back().SpelledI;360 T != ActiveExpansions.back().SpelledE; ++T) {361 processNextReconstructed();362 }363 ActiveExpansions.pop_back();364 }365}366 367void MacroCallReconstructor::debugParentMap() const {368 llvm::DenseSet<FormatToken *> Values(369 llvm::from_range,370 llvm::make_second_range(SpelledParentToReconstructedParent));371 372 for (const auto &P : SpelledParentToReconstructedParent) {373 if (Values.contains(P.first))374 continue;375 llvm::dbgs() << (P.first ? P.first->TokenText : "<null>");376 for (auto I = SpelledParentToReconstructedParent.find(P.first),377 E = SpelledParentToReconstructedParent.end();378 I != E; I = SpelledParentToReconstructedParent.find(I->second)) {379 llvm::dbgs() << " -> " << (I->second ? I->second->TokenText : "<null>");380 }381 llvm::dbgs() << "\n";382 }383}384 385// If visible, add the next token of the reconstructed token sequence to the386// output. Returns whether reconstruction passed a comma that is part of a387// macro call.388bool MacroCallReconstructor::processNextReconstructed() {389 FormatToken *Token = ActiveExpansions.back().SpelledI->Tok;390 ++ActiveExpansions.back().SpelledI;391 if (Token->MacroCtx) {392 // Skip tokens that are not part of the macro call.393 if (Token->MacroCtx->Role == MR_Hidden)394 return false;395 // Skip tokens we already expanded during an inner reconstruction.396 // For example, given: #define ID(x) {x}397 // And the call: ID(ID(f))398 // We get two reconstructions:399 // ID(f) -> {f}400 // ID({f}) -> {{f}}401 // We reconstruct f during the first reconstruction, and skip it during the402 // second reconstruction.403 if (ActiveExpansions.size() < Token->MacroCtx->ExpandedFrom.size())404 return false;405 }406 // Tokens that do not have a macro context are tokens in that are part of the407 // macro call that have not taken part in expansion.408 if (!Token->MacroCtx) {409 // Put the parentheses and commas of a macro call into the same line;410 // if the arguments produce new unwrapped lines, they will become children411 // of the corresponding opening parenthesis or comma tokens in the412 // reconstructed call.413 if (Token->is(tok::l_paren)) {414 MacroCallStructure.push_back(MacroCallState(415 currentLine(), parentLine().Tokens.back()->Tok, Token));416 // All tokens that are children of the previous line's last token in the417 // reconstructed token stream will now be children of the l_paren token.418 // For example, for the line containing the macro calls:419 // auto x = ID({ID(2)});420 // We will build up a map <null> -> ( -> ( with the first and second421 // l_paren of the macro call respectively. New lines that come in with a422 // <null> parent will then become children of the l_paren token of the423 // currently innermost macro call.424 SpelledParentToReconstructedParent[MacroCallStructure.back()425 .ParentLastToken] = Token;426 appendToken(Token);427 prepareParent(Token, /*NewLine=*/true,428 MacroCallStructure.back().Line->Level);429 Token->MacroParent = true;430 return false;431 }432 if (!MacroCallStructure.empty()) {433 if (Token->is(tok::comma)) {434 // Make new lines inside the next argument children of the comma token.435 SpelledParentToReconstructedParent436 [MacroCallStructure.back().Line->Tokens.back()->Tok] = Token;437 Token->MacroParent = true;438 appendToken(Token, MacroCallStructure.back().Line);439 prepareParent(Token, /*NewLine=*/true,440 MacroCallStructure.back().Line->Level);441 return true;442 }443 if (Token->is(tok::r_paren)) {444 appendToken(Token, MacroCallStructure.back().Line);445 SpelledParentToReconstructedParent.erase(446 MacroCallStructure.back().ParentLastToken);447 MacroCallStructure.pop_back();448 return false;449 }450 }451 }452 // Note that any tokens that are tagged with MR_None have been passed as453 // arguments to the macro that have not been expanded, for example:454 // Given: #define ID(X) x455 // When calling: ID(a, b)456 // 'b' will be part of the reconstructed token stream, but tagged MR_None.457 // Given that erroring out in this case would be disruptive, we continue458 // pushing the (unformatted) token.459 // FIXME: This can lead to unfortunate formatting decisions - give the user460 // a hint that their macro definition is broken.461 appendToken(Token);462 return false;463}464 465void MacroCallReconstructor::finalize() {466#ifndef NDEBUG467 assert(State != Finalized && finished());468 State = Finalized;469#endif470 471 // We created corresponding unwrapped lines for each incoming line as children472 // the the toplevel null token.473 assert(Result.Tokens.size() == 1 && !Result.Tokens.front()->Children.empty());474 LLVM_DEBUG({475 llvm::dbgs() << "Finalizing reconstructed lines:\n";476 debug(Result, 0);477 });478 479 // The first line becomes the top level line in the resulting unwrapped line.480 LineNode &Top = *Result.Tokens.front();481 auto *I = Top.Children.begin();482 // Every subsequent line will become a child of the last token in the previous483 // line, which is the token prior to the first token in the line.484 LineNode *Last = (*I)->Tokens.back().get();485 ++I;486 for (auto *E = Top.Children.end(); I != E; ++I) {487 assert(Last->Children.empty());488 Last->Children.push_back(std::move(*I));489 490 // Mark the previous line's last token as generated by a macro expansion491 // so the formatting algorithm can take that into account.492 Last->Tok->MacroParent = true;493 494 Last = Last->Children.back()->Tokens.back().get();495 }496 Top.Children.resize(1);497}498 499void MacroCallReconstructor::appendToken(FormatToken *Token,500 ReconstructedLine *L) {501 L = L ? L : currentLine();502 LLVM_DEBUG(llvm::dbgs() << "-> " << Token->TokenText << "\n");503 L->Tokens.push_back(std::make_unique<LineNode>(Token));504}505 506UnwrappedLine507MacroCallReconstructor::createUnwrappedLine(const ReconstructedLine &Line,508 int Level) {509 UnwrappedLine Result;510 Result.Level = Level;511 for (const auto &N : Line.Tokens) {512 Result.Tokens.push_back(N->Tok);513 UnwrappedLineNode &Current = Result.Tokens.back();514 auto NumChildren = llvm::count_if(515 N->Children, [](const auto &Child) { return !Child->Tokens.empty(); });516 if (NumChildren == 1 && Current.Tok->isOneOf(tok::l_paren, tok::comma)) {517 // If we only have one child, and the child is due to a macro expansion518 // (either attached to a left parenthesis or comma), merge the child into519 // the current line to prevent forced breaks for macro arguments.520 auto *Child = llvm::find_if(N->Children, [](const auto &Child) {521 return !Child->Tokens.empty();522 });523 auto Line = createUnwrappedLine(**Child, Level);524 Result.Tokens.splice(Result.Tokens.end(), Line.Tokens);525 } else if (NumChildren > 0) {526 // When there are multiple children with different indent, make sure that527 // we indent them:528 // 1. One level below the current line's level.529 // 2. At the correct level relative to each other.530 unsigned MinChildLevel =531 llvm::min_element(N->Children,532 [](const auto &E1, const auto &E2) {533 return E1->Level < E2->Level;534 })535 ->get()536 ->Level;537 for (const auto &Child : N->Children) {538 if (Child->Tokens.empty())539 continue;540 Current.Children.push_back(createUnwrappedLine(541 *Child, Level + 1 + (Child->Level - MinChildLevel)));542 }543 }544 }545 return Result;546}547 548void MacroCallReconstructor::debug(const ReconstructedLine &Line, int Level) {549 for (int i = 0; i < Level; ++i)550 llvm::dbgs() << " ";551 for (const auto &N : Line.Tokens) {552 if (!N)553 continue;554 if (N->Tok)555 llvm::dbgs() << N->Tok->TokenText << " ";556 for (const auto &Child : N->Children) {557 llvm::dbgs() << "\n";558 debug(*Child, Level + 1);559 for (int i = 0; i < Level; ++i)560 llvm::dbgs() << " ";561 }562 }563 llvm::dbgs() << "\n";564}565 566MacroCallReconstructor::ReconstructedLine &567MacroCallReconstructor::parentLine() {568 return **std::prev(std::prev(ActiveReconstructedLines.end()));569}570 571MacroCallReconstructor::ReconstructedLine *572MacroCallReconstructor::currentLine() {573 return ActiveReconstructedLines.back();574}575 576MacroCallReconstructor::MacroCallState::MacroCallState(577 MacroCallReconstructor::ReconstructedLine *Line,578 FormatToken *ParentLastToken, FormatToken *MacroCallLParen)579 : Line(Line), ParentLastToken(ParentLastToken),580 MacroCallLParen(MacroCallLParen) {581 LLVM_DEBUG(582 llvm::dbgs() << "ParentLastToken: "583 << (ParentLastToken ? ParentLastToken->TokenText : "<null>")584 << "\n");585 586 assert(MacroCallLParen->is(tok::l_paren));587}588 589} // namespace format590} // namespace clang591