diff options
| author | Dimitry Andric <dim@FreeBSD.org> | 2022-07-14 18:50:02 +0000 |
|---|---|---|
| committer | Dimitry Andric <dim@FreeBSD.org> | 2022-07-14 18:50:02 +0000 |
| commit | 1f917f69ff07f09b6dbb670971f57f8efe718b84 (patch) | |
| tree | 99293cbc1411737cd995dac10a99b2c40ef0944c /clang/lib/Format/MacroCallReconstructor.cpp | |
| parent | 145449b1e420787bb99721a429341fa6be3adfb6 (diff) | |
Diffstat (limited to 'clang/lib/Format/MacroCallReconstructor.cpp')
| -rw-r--r-- | clang/lib/Format/MacroCallReconstructor.cpp | 573 |
1 files changed, 573 insertions, 0 deletions
diff --git a/clang/lib/Format/MacroCallReconstructor.cpp b/clang/lib/Format/MacroCallReconstructor.cpp new file mode 100644 index 000000000000..ccff183cf0da --- /dev/null +++ b/clang/lib/Format/MacroCallReconstructor.cpp @@ -0,0 +1,573 @@ +//===--- MacroCallReconstructor.cpp - Format C++ code -----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file contains the implementation of MacroCallReconstructor, which fits +/// an reconstructed macro call to a parsed set of UnwrappedLines. +/// +//===----------------------------------------------------------------------===// + +#include "Macros.h" + +#include "UnwrappedLineParser.h" +#include "clang/Basic/TokenKinds.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/Support/Debug.h" +#include <cassert> + +#define DEBUG_TYPE "format-reconstruct" + +namespace clang { +namespace format { + +// Call \p Call for each token in the unwrapped line given, passing +// the token, its parent and whether it is the first token in the line. +template <typename T> +void forEachToken(const UnwrappedLine &Line, const T &Call, + FormatToken *Parent = nullptr) { + bool First = true; + for (const auto &N : Line.Tokens) { + Call(N.Tok, Parent, First); + First = false; + for (const auto &Child : N.Children) { + forEachToken(Child, Call, N.Tok); + } + } +} + +MacroCallReconstructor::MacroCallReconstructor( + unsigned Level, + const llvm::DenseMap<FormatToken *, std::unique_ptr<UnwrappedLine>> + &ActiveExpansions) + : Level(Level), IdToReconstructed(ActiveExpansions) { + Result.Tokens.push_back(std::make_unique<LineNode>()); + ActiveReconstructedLines.push_back(&Result); +} + +void MacroCallReconstructor::addLine(const UnwrappedLine &Line) { + assert(State != Finalized); + LLVM_DEBUG(llvm::dbgs() << "MCR: new line...\n"); + forEachToken(Line, [&](FormatToken *Token, FormatToken *Parent, bool First) { + add(Token, Parent, First); + }); + assert(InProgress || finished()); +} + +UnwrappedLine MacroCallReconstructor::takeResult() && { + finalize(); + assert(Result.Tokens.size() == 1 && Result.Tokens.front()->Children.size() == 1); + UnwrappedLine Final = + createUnwrappedLine(*Result.Tokens.front()->Children.front(), Level); + assert(!Final.Tokens.empty()); + return Final; +} + +// Reconstruct the position of the next \p Token, given its parent \p +// ExpandedParent in the incoming unwrapped line. \p First specifies whether it +// is the first token in a given unwrapped line. +void MacroCallReconstructor::add(FormatToken *Token, + FormatToken *ExpandedParent, bool First) { + LLVM_DEBUG( + llvm::dbgs() << "MCR: Token: " << Token->TokenText << ", Parent: " + << (ExpandedParent ? ExpandedParent->TokenText : "<null>") + << ", First: " << First << "\n"); + // In order to be able to find the correct parent in the reconstructed token + // stream, we need to continue the last open reconstruction until we find the + // given token if it is part of the reconstructed token stream. + // + // Note that hidden tokens can be part of the reconstructed stream in nested + // macro calls. + // For example, given + // #define C(x, y) x y + // #define B(x) {x} + // And the call: + // C(a, B(b)) + // The outer macro call will be C(a, {b}), and the hidden token '}' can be + // found in the reconstructed token stream of that expansion level. + // In the expanded token stream + // a {b} + // 'b' is a child of '{'. We need to continue the open expansion of the ',' + // in the call of 'C' in order to correctly set the ',' as the parent of '{', + // so we later set the spelled token 'b' as a child of the ','. + if (!ActiveExpansions.empty() && Token->MacroCtx && + (Token->MacroCtx->Role != MR_Hidden || + ActiveExpansions.size() != Token->MacroCtx->ExpandedFrom.size())) { + if (/*PassedMacroComma = */ reconstructActiveCallUntil(Token)) + First = true; + } + + prepareParent(ExpandedParent, First); + + if (Token->MacroCtx) { + // If this token was generated by a macro call, add the reconstructed + // equivalent of the token. + reconstruct(Token); + } else { + // Otherwise, we add it to the current line. + appendToken(Token); + } +} + +// Adjusts the stack of active reconstructed lines so we're ready to push +// tokens. The tokens to be pushed are children of ExpandedParent in the +// expanded code. +// +// This may entail: +// - creating a new line, if the parent is on the active line +// - popping active lines, if the parent is further up the stack +// +// Postcondition: +// ActiveReconstructedLines.back() is the line that has \p ExpandedParent or its +// reconstructed replacement token as a parent (when possible) - that is, the +// last token in \c ActiveReconstructedLines[ActiveReconstructedLines.size()-2] +// is the parent of ActiveReconstructedLines.back() in the reconstructed +// unwrapped line. +void MacroCallReconstructor::prepareParent(FormatToken *ExpandedParent, + bool NewLine) { + LLVM_DEBUG({ + llvm::dbgs() << "ParentMap:\n"; + debugParentMap(); + }); + // We want to find the parent in the new unwrapped line, where the expanded + // parent might have been replaced during reconstruction. + FormatToken *Parent = getParentInResult(ExpandedParent); + LLVM_DEBUG(llvm::dbgs() << "MCR: New parent: " + << (Parent ? Parent->TokenText : "<null>") << "\n"); + + FormatToken *OpenMacroParent = nullptr; + if (!MacroCallStructure.empty()) { + // Inside a macro expansion, it is possible to lose track of the correct + // parent - either because it is already popped, for example because it was + // in a different macro argument (e.g. M({, })), or when we work on invalid + // code. + // Thus, we use the innermost macro call's parent as the parent at which + // we stop; this allows us to stay within the macro expansion and keeps + // any problems confined to the extent of the macro call. + OpenMacroParent = + getParentInResult(MacroCallStructure.back().MacroCallLParen); + LLVM_DEBUG(llvm::dbgs() + << "MacroCallLParen: " + << MacroCallStructure.back().MacroCallLParen->TokenText + << ", OpenMacroParent: " + << (OpenMacroParent ? OpenMacroParent->TokenText : "<null>") + << "\n"); + } + if (NewLine || + (!ActiveReconstructedLines.back()->Tokens.empty() && + Parent == ActiveReconstructedLines.back()->Tokens.back()->Tok)) { + // If we are at the first token in a new line, we want to also + // create a new line in the resulting reconstructed unwrapped line. + while (ActiveReconstructedLines.back()->Tokens.empty() || + (Parent != ActiveReconstructedLines.back()->Tokens.back()->Tok && + ActiveReconstructedLines.back()->Tokens.back()->Tok != + OpenMacroParent)) { + ActiveReconstructedLines.pop_back(); + assert(!ActiveReconstructedLines.empty()); + } + assert(!ActiveReconstructedLines.empty()); + ActiveReconstructedLines.back()->Tokens.back()->Children.push_back( + std::make_unique<ReconstructedLine>()); + ActiveReconstructedLines.push_back( + &*ActiveReconstructedLines.back()->Tokens.back()->Children.back()); + } else if (parentLine().Tokens.back()->Tok != Parent) { + // If we're not the first token in a new line, pop lines until we find + // the child of \c Parent in the stack. + while (Parent != parentLine().Tokens.back()->Tok && + parentLine().Tokens.back()->Tok && + parentLine().Tokens.back()->Tok != OpenMacroParent) { + ActiveReconstructedLines.pop_back(); + assert(!ActiveReconstructedLines.empty()); + } + } + assert(!ActiveReconstructedLines.empty()); +} + +// For a given \p Parent in the incoming expanded token stream, find the +// corresponding parent in the output. +FormatToken *MacroCallReconstructor::getParentInResult(FormatToken *Parent) { + FormatToken *Mapped = SpelledParentToReconstructedParent.lookup(Parent); + if (!Mapped) + return Parent; + for (; Mapped; Mapped = SpelledParentToReconstructedParent.lookup(Parent)) { + Parent = Mapped; + } + // If we use a different token than the parent in the expanded token stream + // as parent, mark it as a special parent, so the formatting code knows it + // needs to have its children formatted. + Parent->MacroParent = true; + return Parent; +} + +// Reconstruct a \p Token that was expanded from a macro call. +void MacroCallReconstructor::reconstruct(FormatToken *Token) { + assert(Token->MacroCtx); + // A single token can be the only result of a macro call: + // Given: #define ID(x, y) ; + // And the call: ID(<some>, <tokens>) + // ';' in the expanded stream will reconstruct all of ID(<some>, <tokens>). + if (Token->MacroCtx->StartOfExpansion) { + startReconstruction(Token); + // If the order of tokens in the expanded token stream is not the + // same as the order of tokens in the reconstructed stream, we need + // to reconstruct tokens that arrive later in the stream. + if (Token->MacroCtx->Role != MR_Hidden) { + reconstructActiveCallUntil(Token); + } + } + assert(!ActiveExpansions.empty()); + if (ActiveExpansions.back().SpelledI != ActiveExpansions.back().SpelledE) { + assert(ActiveExpansions.size() == Token->MacroCtx->ExpandedFrom.size()); + if (Token->MacroCtx->Role != MR_Hidden) { + // The current token in the reconstructed token stream must be the token + // we're looking for - we either arrive here after startReconstruction, + // which initiates the stream to the first token, or after + // continueReconstructionUntil skipped until the expected token in the + // reconstructed stream at the start of add(...). + assert(ActiveExpansions.back().SpelledI->Tok == Token); + processNextReconstructed(); + } else if (!currentLine()->Tokens.empty()) { + // Map all hidden tokens to the last visible token in the output. + // If the hidden token is a parent, we'll use the last visible + // token as the parent of the hidden token's children. + SpelledParentToReconstructedParent[Token] = + currentLine()->Tokens.back()->Tok; + } else { + for (auto I = ActiveReconstructedLines.rbegin(), + E = ActiveReconstructedLines.rend(); + I != E; ++I) { + if (!(*I)->Tokens.empty()) { + SpelledParentToReconstructedParent[Token] = (*I)->Tokens.back()->Tok; + break; + } + } + } + } + if (Token->MacroCtx->EndOfExpansion) + endReconstruction(Token); +} + +// Given a \p Token that starts an expansion, reconstruct the beginning of the +// macro call. +// For example, given: #define ID(x) x +// And the call: ID(int a) +// Reconstructs: ID( +void MacroCallReconstructor::startReconstruction(FormatToken *Token) { + assert(Token->MacroCtx); + assert(!Token->MacroCtx->ExpandedFrom.empty()); + assert(ActiveExpansions.size() <= Token->MacroCtx->ExpandedFrom.size()); +#ifndef NDEBUG + // Check that the token's reconstruction stack matches our current + // reconstruction stack. + for (size_t I = 0; I < ActiveExpansions.size(); ++I) { + assert(ActiveExpansions[I].ID == + Token->MacroCtx + ->ExpandedFrom[Token->MacroCtx->ExpandedFrom.size() - 1 - I]); + } +#endif + // Start reconstruction for all calls for which this token is the first token + // generated by the call. + // Note that the token's expanded from stack is inside-to-outside, and the + // expansions for which this token is not the first are the outermost ones. + ArrayRef<FormatToken *> StartedMacros = + makeArrayRef(Token->MacroCtx->ExpandedFrom) + .drop_back(ActiveExpansions.size()); + assert(StartedMacros.size() == Token->MacroCtx->StartOfExpansion); + // We reconstruct macro calls outside-to-inside. + for (FormatToken *ID : llvm::reverse(StartedMacros)) { + // We found a macro call to be reconstructed; the next time our + // reconstruction stack is empty we know we finished an reconstruction. +#ifndef NDEBUG + State = InProgress; +#endif + // Put the reconstructed macro call's token into our reconstruction stack. + auto IU = IdToReconstructed.find(ID); + assert(IU != IdToReconstructed.end()); + ActiveExpansions.push_back( + {ID, IU->second->Tokens.begin(), IU->second->Tokens.end()}); + // Process the macro call's identifier. + processNextReconstructed(); + if (ActiveExpansions.back().SpelledI == ActiveExpansions.back().SpelledE) + continue; + if (ActiveExpansions.back().SpelledI->Tok->is(tok::l_paren)) { + // Process the optional opening parenthesis. + processNextReconstructed(); + } + } +} + +// Add all tokens in the reconstruction stream to the output until we find the +// given \p Token. +bool MacroCallReconstructor::reconstructActiveCallUntil(FormatToken *Token) { + assert(!ActiveExpansions.empty()); + bool PassedMacroComma = false; + // FIXME: If Token was already expanded earlier, due to + // a change in order, we will not find it, but need to + // skip it. + while (ActiveExpansions.back().SpelledI != ActiveExpansions.back().SpelledE && + ActiveExpansions.back().SpelledI->Tok != Token) { + PassedMacroComma = processNextReconstructed() || PassedMacroComma; + } + return PassedMacroComma; +} + +// End all reconstructions for which \p Token is the final token. +void MacroCallReconstructor::endReconstruction(FormatToken *Token) { + assert(Token->MacroCtx && + (ActiveExpansions.size() >= Token->MacroCtx->EndOfExpansion)); + for (size_t I = 0; I < Token->MacroCtx->EndOfExpansion; ++I) { +#ifndef NDEBUG + // Check all remaining tokens but the final closing parenthesis and optional + // trailing comment were already reconstructed at an inner expansion level. + for (auto T = ActiveExpansions.back().SpelledI; + T != ActiveExpansions.back().SpelledE; ++T) { + FormatToken *Token = T->Tok; + bool ClosingParen = (std::next(T) == ActiveExpansions.back().SpelledE || + std::next(T)->Tok->isTrailingComment()) && + !Token->MacroCtx && Token->is(tok::r_paren); + bool TrailingComment = Token->isTrailingComment(); + bool PreviousLevel = + Token->MacroCtx && + (ActiveExpansions.size() < Token->MacroCtx->ExpandedFrom.size()); + if (!ClosingParen && !TrailingComment && !PreviousLevel) { + llvm::dbgs() << "At token: " << Token->TokenText << "\n"; + } + // In addition to the following cases, we can also run into this + // when a macro call had more arguments than expected; in that case, + // the comma and the remaining tokens in the macro call will potentially + // end up in the line when we finish the expansion. + // FIXME: Add the information which arguments are unused, and assert + // one of the cases below plus reconstructed macro argument tokens. + // assert(ClosingParen || TrailingComment || PreviousLevel); + } +#endif + // Handle the remaining open tokens: + // - expand the closing parenthesis, if it exists, including an optional + // trailing comment + // - handle tokens that were already reconstructed at an inner expansion + // level + // - handle tokens when a macro call had more than the expected number of + // arguments, i.e. when #define M(x) is called as M(a, b, c) we'll end + // up with the sequence ", b, c)" being open at the end of the + // reconstruction; we want to gracefully handle that case + // + // FIXME: See the above debug-check for what we will need to do to be + // able to assert this. + for (auto T = ActiveExpansions.back().SpelledI; + T != ActiveExpansions.back().SpelledE; ++T) { + processNextReconstructed(); + } + ActiveExpansions.pop_back(); + } +} + +void MacroCallReconstructor::debugParentMap() const { + llvm::DenseSet<FormatToken *> Values; + for (const auto &P : SpelledParentToReconstructedParent) + Values.insert(P.second); + + for (const auto &P : SpelledParentToReconstructedParent) { + if (Values.contains(P.first)) + continue; + llvm::dbgs() << (P.first ? P.first->TokenText : "<null>"); + for (auto I = SpelledParentToReconstructedParent.find(P.first), + E = SpelledParentToReconstructedParent.end(); + I != E; I = SpelledParentToReconstructedParent.find(I->second)) { + llvm::dbgs() << " -> " << (I->second ? I->second->TokenText : "<null>"); + } + llvm::dbgs() << "\n"; + } +} + +// If visible, add the next token of the reconstructed token sequence to the +// output. Returns whether reconstruction passed a comma that is part of a +// macro call. +bool MacroCallReconstructor::processNextReconstructed() { + FormatToken *Token = ActiveExpansions.back().SpelledI->Tok; + ++ActiveExpansions.back().SpelledI; + if (Token->MacroCtx) { + // Skip tokens that are not part of the macro call. + if (Token->MacroCtx->Role == MR_Hidden) { + return false; + } + // Skip tokens we already expanded during an inner reconstruction. + // For example, given: #define ID(x) {x} + // And the call: ID(ID(f)) + // We get two reconstructions: + // ID(f) -> {f} + // ID({f}) -> {{f}} + // We reconstruct f during the first reconstruction, and skip it during the + // second reconstruction. + if (ActiveExpansions.size() < Token->MacroCtx->ExpandedFrom.size()) { + return false; + } + } + // Tokens that do not have a macro context are tokens in that are part of the + // macro call that have not taken part in expansion. + if (!Token->MacroCtx) { + // Put the parentheses and commas of a macro call into the same line; + // if the arguments produce new unwrapped lines, they will become children + // of the corresponding opening parenthesis or comma tokens in the + // reconstructed call. + if (Token->is(tok::l_paren)) { + MacroCallStructure.push_back(MacroCallState( + currentLine(), parentLine().Tokens.back()->Tok, Token)); + // All tokens that are children of the previous line's last token in the + // reconstructed token stream will now be children of the l_paren token. + // For example, for the line containing the macro calls: + // auto x = ID({ID(2)}); + // We will build up a map <null> -> ( -> ( with the first and second + // l_paren of the macro call respectively. New lines that come in with a + // <null> parent will then become children of the l_paren token of the + // currently innermost macro call. + SpelledParentToReconstructedParent[MacroCallStructure.back() + .ParentLastToken] = Token; + appendToken(Token); + prepareParent(Token, /*NewLine=*/true); + Token->MacroParent = true; + return false; + } + if (!MacroCallStructure.empty()) { + if (Token->is(tok::comma)) { + // Make new lines inside the next argument children of the comma token. + SpelledParentToReconstructedParent + [MacroCallStructure.back().Line->Tokens.back()->Tok] = Token; + Token->MacroParent = true; + appendToken(Token, MacroCallStructure.back().Line); + prepareParent(Token, /*NewLine=*/true); + return true; + } + if (Token->is(tok::r_paren)) { + appendToken(Token, MacroCallStructure.back().Line); + SpelledParentToReconstructedParent.erase( + MacroCallStructure.back().ParentLastToken); + MacroCallStructure.pop_back(); + return false; + } + } + } + // Note that any tokens that are tagged with MR_None have been passed as + // arguments to the macro that have not been expanded, for example: + // Given: #define ID(X) x + // When calling: ID(a, b) + // 'b' will be part of the reconstructed token stream, but tagged MR_None. + // Given that erroring out in this case would be disruptive, we continue + // pushing the (unformatted) token. + // FIXME: This can lead to unfortunate formatting decisions - give the user + // a hint that their macro definition is broken. + appendToken(Token); + return false; +} + +void MacroCallReconstructor::finalize() { +#ifndef NDEBUG + assert(State != Finalized && finished()); + State = Finalized; +#endif + + // We created corresponding unwrapped lines for each incoming line as children + // the the toplevel null token. + assert(Result.Tokens.size() == 1 && !Result.Tokens.front()->Children.empty()); + LLVM_DEBUG({ + llvm::dbgs() << "Finalizing reconstructed lines:\n"; + debug(Result, 0); + }); + + // The first line becomes the top level line in the resulting unwrapped line. + LineNode &Top = *Result.Tokens.front(); + auto *I = Top.Children.begin(); + // Every subsequent line will become a child of the last token in the previous + // line, which is the token prior to the first token in the line. + LineNode *Last = (*I)->Tokens.back().get(); + ++I; + for (auto *E = Top.Children.end(); I != E; ++I) { + assert(Last->Children.empty()); + Last->Children.push_back(std::move(*I)); + + // Mark the previous line's last token as generated by a macro expansion + // so the formatting algorithm can take that into account. + Last->Tok->MacroParent = true; + + Last = Last->Children.back()->Tokens.back().get(); + } + Top.Children.resize(1); +} + +void MacroCallReconstructor::appendToken(FormatToken *Token, + ReconstructedLine *L) { + L = L ? L : currentLine(); + LLVM_DEBUG(llvm::dbgs() << "-> " << Token->TokenText << "\n"); + L->Tokens.push_back(std::make_unique<LineNode>(Token)); +} + +UnwrappedLine +MacroCallReconstructor::createUnwrappedLine(const ReconstructedLine &Line, + int Level) { + UnwrappedLine Result; + Result.Level = Level; + for (const auto &N : Line.Tokens) { + Result.Tokens.push_back(N->Tok); + UnwrappedLineNode &Current = Result.Tokens.back(); + for (const auto &Child : N->Children) { + if (Child->Tokens.empty()) + continue; + Current.Children.push_back(createUnwrappedLine(*Child, Level + 1)); + } + if (Current.Children.size() == 1 && + Current.Tok->isOneOf(tok::l_paren, tok::comma)) { + Result.Tokens.splice(Result.Tokens.end(), + Current.Children.front().Tokens); + Current.Children.clear(); + } + } + return Result; +} + +void MacroCallReconstructor::debug(const ReconstructedLine &Line, int Level) { + for (int i = 0; i < Level; ++i) + llvm::dbgs() << " "; + for (const auto &N : Line.Tokens) { + if (!N) + continue; + if (N->Tok) + llvm::dbgs() << N->Tok->TokenText << " "; + for (const auto &Child : N->Children) { + llvm::dbgs() << "\n"; + debug(*Child, Level + 1); + for (int i = 0; i < Level; ++i) + llvm::dbgs() << " "; + } + } + llvm::dbgs() << "\n"; +} + +MacroCallReconstructor::ReconstructedLine & +MacroCallReconstructor::parentLine() { + return **std::prev(std::prev(ActiveReconstructedLines.end())); +} + +MacroCallReconstructor::ReconstructedLine * +MacroCallReconstructor::currentLine() { + return ActiveReconstructedLines.back(); +} + +MacroCallReconstructor::MacroCallState::MacroCallState( + MacroCallReconstructor::ReconstructedLine *Line, + FormatToken *ParentLastToken, FormatToken *MacroCallLParen) + : Line(Line), ParentLastToken(ParentLastToken), + MacroCallLParen(MacroCallLParen) { + LLVM_DEBUG( + llvm::dbgs() << "ParentLastToken: " + << (ParentLastToken ? ParentLastToken->TokenText : "<null>") + << "\n"); + + assert(MacroCallLParen->is(tok::l_paren)); +} + +} // namespace format +} // namespace clang |
