//===--- Macros.h - Format C++ code -----------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file contains the main building blocks of macro support in
/// clang-format.
///
/// In order to not violate the requirement that clang-format can format files
/// in isolation, clang-format's macro support uses expansions users provide
/// as part of clang-format's style configuration.
///
/// Macro definitions are of the form "MACRO(p1, p2)=p1 + p2", but only support
/// one level of expansion (\see MacroExpander for a full description of what
/// is supported).
///
/// As part of parsing, clang-format uses the MacroExpander to expand the
/// spelled token streams into expanded token streams when it encounters a
/// macro call. The UnwrappedLineParser continues to parse UnwrappedLines
/// from the expanded token stream.
/// After the expanded unwrapped lines are parsed, the MacroCallReconstructor
/// matches the spelled token stream into unwrapped lines that best resemble the
/// structure of the expanded unwrapped lines. These reconstructed unwrapped
/// lines are aliasing the tokens in the expanded token stream, so that token
/// annotations will be reused when formatting the spelled macro calls.
///
/// When formatting, clang-format annotates and formats the expanded unwrapped
/// lines first, determining the token types. Next, it formats the spelled
/// unwrapped lines, keeping the token types fixed, while allowing other
/// formatting decisions to change.
///
//===----------------------------------------------------------------------===//
#ifndef CLANG_LIB_FORMAT_MACROS_H
#define CLANG_LIB_FORMAT_MACROS_H
#include <list>
#include <map>
#include <string>
#include <vector>
#include "FormatToken.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
namespace clang {
namespace format {
struct UnwrappedLine;
struct UnwrappedLineNode;
/// Takes a set of macro definitions as strings and allows expanding calls to
/// those macros.
///
/// For example:
/// Definition: A(x, y)=x + y
/// Call : A(int a = 1, 2)
/// Expansion : int a = 1 + 2
///
/// Expansion does not check arity of the definition.
/// If fewer arguments than expected are provided, the remaining parameters
/// are considered empty:
/// Call : A(a)
/// Expansion: a +
/// If more arguments than expected are provided, they will be discarded.
///
/// The expander does not support:
/// - recursive expansion
/// - stringification
/// - concatenation
/// - variadic macros
///
/// Furthermore, only a single expansion of each macro argument is supported,
/// so that we cannot get conflicting formatting decisions from different
/// expansions.
/// Definition: A(x)=x+x
/// Call : A(id)
/// Expansion : id+x
///
class MacroExpander {
public:
using ArgsList = llvm::ArrayRef<llvm::SmallVector<FormatToken *, 8>>;
/// Construct a macro expander from a set of macro definitions.
/// Macro definitions must be encoded as UTF-8.
///
/// Each entry in \p Macros must conform to the following simple
/// macro-definition language:
/// <definition> ::= <id> <expansion> | <id> "(" <params> ")" <expansion>
/// <params> ::= <id-list> | ""
/// <id-list> ::= <id> | <id> "," <params>
/// <expansion> ::= "=" <tail> | <eof>
/// <tail> ::= <tok> <tail> | <eof>
///
/// Macros that cannot be parsed will be silently discarded.
///
MacroExpander(const std::vector<std::string> &Macros,
clang::SourceManager &SourceMgr, const FormatStyle &Style,
llvm::SpecificBumpPtrAllocator<FormatToken> &Allocator,
IdentifierTable &IdentTable);
~MacroExpander();
/// Returns whether any macro \p Name is defined, regardless of overloads.
bool defined(llvm::StringRef Name) const;
/// Returns whetherh there is an object-like overload, i.e. where the macro
/// has no arguments and should not consume subsequent parentheses.
bool objectLike(llvm::StringRef Name) const;
/// Returns whether macro \p Name provides an overload with the given arity.
bool hasArity(llvm::StringRef Name, unsigned Arity) const;
/// Returns the expanded stream of format tokens for \p ID, where
/// each element in \p Args is a positional argument to the macro call.
/// If \p Args is not set, the object-like overload is used.
/// If \p Args is set, the overload with the arity equal to \c Args.size() is
/// used.
llvm::SmallVector<FormatToken *, 8>
expand(FormatToken *ID, std::optional<ArgsList> OptionalArgs) const;
private:
struct Definition;
class DefinitionParser;
void parseDefinition(const std::string &Macro);
clang::SourceManager &SourceMgr;
const FormatStyle &Style;
llvm::SpecificBumpPtrAllocator<FormatToken> &Allocator;
IdentifierTable &IdentTable;
SmallVector<std::unique_ptr<llvm::MemoryBuffer>> Buffers;
llvm::StringMap<llvm::DenseMap<int, Definition>> FunctionLike;
llvm::StringMap<Definition> ObjectLike;
};
/// Converts a sequence of UnwrappedLines containing expanded macros into a
/// single UnwrappedLine containing the macro calls. This UnwrappedLine may be
/// broken into child lines, in a way that best conveys the structure of the
/// expanded code.
///
/// In the simplest case, a spelled UnwrappedLine contains one macro, and after
/// expanding it we have one expanded UnwrappedLine. In general, macro
/// expansions can span UnwrappedLines, and multiple macros can contribute
/// tokens to the same line. We keep consuming expanded lines until:
/// * all expansions that started have finished (we're not chopping any macros
/// in half)
/// * *and* we've reached the end of a *spelled* unwrapped line.
///
/// A single UnwrappedLine represents this chunk of code.
///
/// After this point, the state of the spelled/expanded stream is "in sync"
/// (both at the start of an UnwrappedLine, with no macros open), so the
/// Reconstructor can be thrown away and parsing can continue.
///
/// Given a mapping from the macro name identifier token in the macro call
/// to the tokens of the macro call, for example:
/// CLASSA -> CLASSA({public: void x();})
///
/// When getting the formatted lines of the expansion via the \c addLine method
/// (each '->' specifies a call to \c addLine ):
/// -> class A {
/// -> public:
/// -> void x();
/// -> };
///
/// Creates the tree of unwrapped lines containing the macro call tokens so that
/// the macro call tokens fit the semantic structure of the expanded formatted
/// lines:
/// -> CLASSA({
/// -> public:
/// -> void x();
/// -> })
class MacroCallReconstructor {
public:
/// Create an Reconstructor whose resulting \p UnwrappedLine will start at
/// \p Level, using the map from name identifier token to the corresponding
/// tokens of the spelled macro call.
MacroCallReconstructor(
unsigned Level,
const llvm::DenseMap<FormatToken *, std::unique_ptr<UnwrappedLine>>
&ActiveExpansions);
/// For the given \p Line, match all occurences of tokens expanded from a
/// macro to unwrapped lines in the spelled macro call so that the resulting
/// tree of unwrapped lines best resembles the structure of unwrapped lines
/// passed in via \c addLine.
void addLine(const UnwrappedLine &Line);
/// Check whether at the current state there is no open macro expansion
/// that needs to be processed to finish an macro call.
/// Only when \c finished() is true, \c takeResult() can be called to retrieve
/// the resulting \c UnwrappedLine.
/// If there are multiple subsequent macro calls within an unwrapped line in
/// the spelled token stream, the calling code may also continue to call
/// \c addLine() when \c finished() is true.
bool finished() const { return ActiveExpansions.empty(); }
/// Retrieve the formatted \c UnwrappedLine containing the orginal
/// macro calls, formatted according to the expanded token stream received
/// via \c addLine().
/// Generally, this line tries to have the same structure as the expanded,
/// formatted unwrapped lines handed in via \c addLine(), with the exception
/// that for multiple top-level lines, each subsequent line will be the
/// child of the last token in its predecessor. This representation is chosen
/// because it is a precondition to the formatter that we get what looks like
/// a single statement in a single \c UnwrappedLine (i.e. matching parens).
///
/// If a token in a macro argument is a child of a token in the expansion,
/// the parent will be the corresponding token in the macro call.
/// For example:
/// #define C(a, b) class C { a b
/// C(int x;, int y;)
/// would expand to
/// class C { int x; int y;
/// where in a formatted line "int x;" and "int y;" would both be new separate
/// lines.
///
/// In the result, "int x;" will be a child of the opening parenthesis in "C("
/// and "int y;" will be a child of the "," token:
/// C (
/// \- int x;
/// ,
/// \- int y;
/// )
UnwrappedLine takeResult() &&;
private:
void add(FormatToken *Token, FormatToken *ExpandedParent, bool First);
void prepareParent(FormatToken *ExpandedParent, bool First);
FormatToken *getParentInResult(FormatToken *Parent);
void reconstruct(FormatToken *Token);
void startReconstruction(FormatToken *Token);
bool reconstructActiveCallUntil(FormatToken *Token);
void endReconstruction(FormatToken *Token);
bool processNextReconstructed();
void finalize();
struct ReconstructedLine;
void appendToken(FormatToken *Token, ReconstructedLine *L = nullptr);
UnwrappedLine createUnwrappedLine(const ReconstructedLine &Line, int Level);
void debug(const ReconstructedLine &Line, int Level);
ReconstructedLine &parentLine();
ReconstructedLine *currentLine();
void debugParentMap() const;
#ifndef NDEBUG
enum ReconstructorState {
Start, // No macro expansion was found in the input yet.
InProgress, // During a macro reconstruction.
Finalized, // Past macro reconstruction, the result is finalized.
};
ReconstructorState State = Start;
#endif
// Node in which we build up the resulting unwrapped line; this type is
// analogous to UnwrappedLineNode.
struct LineNode {
LineNode() = default;
LineNode(FormatToken *Tok) : Tok(Tok) {}
FormatToken *Tok = nullptr;
llvm::SmallVector<std::unique_ptr<ReconstructedLine>> Children;
};
// Line in which we build up the resulting unwrapped line.
// FIXME: Investigate changing UnwrappedLine to a pointer type and using it
// instead of rolling our own type.
struct ReconstructedLine {
llvm::SmallVector<std::unique_ptr<LineNode>> Tokens;
};
// The line in which we collect the resulting reconstructed output.
// To reduce special cases in the algorithm, the first level of the line
// contains a single null token that has the reconstructed incoming
// lines as children.
// In the end, we stich the lines together so that each subsequent line
// is a child of the last token of the previous line. This is necessary
// in order to format the overall expression as a single logical line -
// if we created separate lines, we'd format them with their own top-level
// indent depending on the semantic structure, which is not desired.
ReconstructedLine Result;
// Stack of currently "open" lines, where each line's predecessor's last
// token is the parent token for that line.
llvm::SmallVector<ReconstructedLine *> ActiveReconstructedLines;
// Maps from the expanded token to the token that takes its place in the
// reconstructed token stream in terms of parent-child relationships.
// Note that it might take multiple steps to arrive at the correct
// parent in the output.
// Given: #define C(a, b) []() { a; b; }
// And a call: C(f(), g())
// The structure in the incoming formatted unwrapped line will be:
// []() {
// |- f();
// \- g();
// }
// with f and g being children of the opening brace.
// In the reconstructed call:
// C(f(), g())
// \- f()
// \- g()
// We want f to be a child of the opening parenthesis and g to be a child
// of the comma token in the macro call.
// Thus, we map
// { -> (
// and add
// ( -> ,
// once we're past the comma in the reconstruction.
llvm::DenseMap<FormatToken *, FormatToken *>
SpelledParentToReconstructedParent;
// Keeps track of a single expansion while we're reconstructing tokens it
// generated.
struct Expansion {
// The identifier token of the macro call.
FormatToken *ID;
// Our current position in the reconstruction.
std::list<UnwrappedLineNode>::iterator SpelledI;
// The end of the reconstructed token sequence.
std::list<UnwrappedLineNode>::iterator SpelledE;
};
// Stack of macro calls for which we're in the middle of an expansion.
llvm::SmallVector<Expansion> ActiveExpansions;
struct MacroCallState {
MacroCallState(ReconstructedLine *Line, FormatToken *ParentLastToken,
FormatToken *MacroCallLParen);
ReconstructedLine *Line;
// The last token in the parent line or expansion, or nullptr if the macro
// expansion is on a top-level line.
//
// For example, in the macro call:
// auto f = []() { ID(1); };
// The MacroCallState for ID will have '{' as ParentLastToken.
//
// In the macro call:
// ID(ID(void f()));
// The MacroCallState of the outer ID will have nullptr as ParentLastToken,
// while the MacroCallState for the inner ID will have the '(' of the outer
// ID as ParentLastToken.
//
// In the macro call:
// ID2(a, ID(b));
// The MacroCallState of ID will have ',' as ParentLastToken.
FormatToken *ParentLastToken;
// The l_paren of this MacroCallState's macro call.
FormatToken *MacroCallLParen;
};
// Keeps track of the lines into which the opening brace/parenthesis &
// argument separating commas for each level in the macro call go in order to
// put the corresponding closing brace/parenthesis into the same line in the
// output and keep track of which parents in the expanded token stream map to
// which tokens in the reconstructed stream.
// When an opening brace/parenthesis has children, we want the structure of
// the output line to be:
// |- MACRO
// |- (
// | \- <argument>
// |- ,
// | \- <argument>
// \- )
llvm::SmallVector<MacroCallState> MacroCallStructure;
// Level the generated UnwrappedLine will be at.
const unsigned Level;
// Maps from identifier of the macro call to an unwrapped line containing
// all tokens of the macro call.
const llvm::DenseMap<FormatToken *, std::unique_ptr<UnwrappedLine>>
&IdToReconstructed;
};
} // namespace format
} // namespace clang
#endif
