diff options
Diffstat (limited to 'contrib/llvm/tools/clang/lib/Format/Format.cpp')
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Format/Format.cpp | 1763 |
1 files changed, 1763 insertions, 0 deletions
diff --git a/contrib/llvm/tools/clang/lib/Format/Format.cpp b/contrib/llvm/tools/clang/lib/Format/Format.cpp new file mode 100644 index 000000000000..101b16f1a18c --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Format/Format.cpp @@ -0,0 +1,1763 @@ +//===--- Format.cpp - Format C++ code -------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// \brief This file implements functions declared in Format.h. This will be +/// split into separate files as we go. +/// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "format-formatter" + +#include "TokenAnnotator.h" +#include "UnwrappedLineParser.h" +#include "clang/Basic/Diagnostic.h" +#include "clang/Basic/OperatorPrecedence.h" +#include "clang/Basic/SourceManager.h" +#include "clang/Format/Format.h" +#include "clang/Frontend/TextDiagnosticPrinter.h" +#include "clang/Lex/Lexer.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Debug.h" +#include <queue> +#include <string> + +namespace clang { +namespace format { + +FormatStyle getLLVMStyle() { + FormatStyle LLVMStyle; + LLVMStyle.ColumnLimit = 80; + LLVMStyle.MaxEmptyLinesToKeep = 1; + LLVMStyle.PointerBindsToType = false; + LLVMStyle.DerivePointerBinding = false; + LLVMStyle.AccessModifierOffset = -2; + LLVMStyle.Standard = FormatStyle::LS_Cpp03; + LLVMStyle.IndentCaseLabels = false; + LLVMStyle.SpacesBeforeTrailingComments = 1; + LLVMStyle.BinPackParameters = true; + LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true; + LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false; + LLVMStyle.AllowShortIfStatementsOnASingleLine = false; + LLVMStyle.ObjCSpaceBeforeProtocolList = true; + LLVMStyle.PenaltyExcessCharacter = 1000000; + LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 5; + return LLVMStyle; +} + +FormatStyle getGoogleStyle() { + FormatStyle GoogleStyle; + GoogleStyle.ColumnLimit = 80; + GoogleStyle.MaxEmptyLinesToKeep = 1; + GoogleStyle.PointerBindsToType = true; + GoogleStyle.DerivePointerBinding = true; + GoogleStyle.AccessModifierOffset = -1; + GoogleStyle.Standard = FormatStyle::LS_Auto; + GoogleStyle.IndentCaseLabels = true; + GoogleStyle.SpacesBeforeTrailingComments = 2; + GoogleStyle.BinPackParameters = true; + GoogleStyle.AllowAllParametersOfDeclarationOnNextLine = true; + GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true; + GoogleStyle.AllowShortIfStatementsOnASingleLine = false; + GoogleStyle.ObjCSpaceBeforeProtocolList = false; + GoogleStyle.PenaltyExcessCharacter = 1000000; + GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 100; + return GoogleStyle; +} + +FormatStyle getChromiumStyle() { + FormatStyle ChromiumStyle = getGoogleStyle(); + ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false; + ChromiumStyle.BinPackParameters = false; + ChromiumStyle.Standard = FormatStyle::LS_Cpp03; + ChromiumStyle.DerivePointerBinding = false; + return ChromiumStyle; +} + +static bool isTrailingComment(const AnnotatedToken &Tok) { + return Tok.is(tok::comment) && + (Tok.Children.empty() || Tok.Children[0].MustBreakBefore); +} + +static bool isComparison(const AnnotatedToken &Tok) { + prec::Level Precedence = getPrecedence(Tok); + return Tok.Type == TT_BinaryOperator && + (Precedence == prec::Equality || Precedence == prec::Relational); +} + +// Returns the length of everything up to the first possible line break after +// the ), ], } or > matching \c Tok. +static unsigned getLengthToMatchingParen(const AnnotatedToken &Tok) { + if (Tok.MatchingParen == NULL) + return 0; + AnnotatedToken *End = Tok.MatchingParen; + while (!End->Children.empty() && !End->Children[0].CanBreakBefore) { + End = &End->Children[0]; + } + return End->TotalLength - Tok.TotalLength + 1; +} + +static size_t +calculateColumnLimit(const FormatStyle &Style, bool InPPDirective) { + // In preprocessor directives reserve two chars for trailing " \" + return Style.ColumnLimit - (InPPDirective ? 2 : 0); +} + +/// \brief Manages the whitespaces around tokens and their replacements. +/// +/// This includes special handling for certain constructs, e.g. the alignment of +/// trailing line comments. +class WhitespaceManager { +public: + WhitespaceManager(SourceManager &SourceMgr, const FormatStyle &Style) + : SourceMgr(SourceMgr), Style(Style) {} + + /// \brief Replaces the whitespace in front of \p Tok. Only call once for + /// each \c AnnotatedToken. + void replaceWhitespace(const AnnotatedToken &Tok, unsigned NewLines, + unsigned Spaces, unsigned WhitespaceStartColumn) { + // 2+ newlines mean an empty line separating logic scopes. + if (NewLines >= 2) + alignComments(); + + SourceLocation TokenLoc = Tok.FormatTok.Tok.getLocation(); + bool LineExceedsColumnLimit = Spaces + WhitespaceStartColumn + + Tok.FormatTok.TokenLength > Style.ColumnLimit; + + // Align line comments if they are trailing or if they continue other + // trailing comments. + if (isTrailingComment(Tok)) { + // Remove the comment's trailing whitespace. + if (Tok.FormatTok.Tok.getLength() != Tok.FormatTok.TokenLength) + Replaces.insert(tooling::Replacement( + SourceMgr, TokenLoc.getLocWithOffset(Tok.FormatTok.TokenLength), + Tok.FormatTok.Tok.getLength() - Tok.FormatTok.TokenLength, "")); + + // Align comment with other comments. + if ((Tok.Parent != NULL || !Comments.empty()) && + !LineExceedsColumnLimit) { + StoredComment Comment; + Comment.Tok = Tok.FormatTok; + Comment.Spaces = Spaces; + Comment.NewLines = NewLines; + Comment.MinColumn = + NewLines > 0 ? Spaces : WhitespaceStartColumn + Spaces; + Comment.MaxColumn = Style.ColumnLimit - Tok.FormatTok.TokenLength; + Comment.Untouchable = false; + Comments.push_back(Comment); + return; + } + } + + // If this line does not have a trailing comment, align the stored comments. + if (Tok.Children.empty() && !isTrailingComment(Tok)) + alignComments(); + + if (Tok.Type == TT_BlockComment) { + indentBlockComment(Tok, Spaces, WhitespaceStartColumn, NewLines, false); + } else if (Tok.Type == TT_LineComment && LineExceedsColumnLimit) { + StringRef Line(SourceMgr.getCharacterData(TokenLoc), + Tok.FormatTok.TokenLength); + int StartColumn = Spaces + (NewLines == 0 ? WhitespaceStartColumn : 0); + StringRef Prefix = getLineCommentPrefix(Line); + std::string NewPrefix = std::string(StartColumn, ' ') + Prefix.str(); + splitLineInComment(Tok.FormatTok, Line.substr(Prefix.size()), + StartColumn + Prefix.size(), NewPrefix, + /*InPPDirective=*/ false, + /*CommentHasMoreLines=*/ false); + } + + storeReplacement(Tok.FormatTok, getNewLineText(NewLines, Spaces)); + } + + /// \brief Like \c replaceWhitespace, but additionally adds right-aligned + /// backslashes to escape newlines inside a preprocessor directive. + /// + /// This function and \c replaceWhitespace have the same behavior if + /// \c Newlines == 0. + void replacePPWhitespace(const AnnotatedToken &Tok, unsigned NewLines, + unsigned Spaces, unsigned WhitespaceStartColumn) { + if (Tok.Type == TT_BlockComment) + indentBlockComment(Tok, Spaces, WhitespaceStartColumn, NewLines, true); + + storeReplacement(Tok.FormatTok, + getNewLineText(NewLines, Spaces, WhitespaceStartColumn)); + } + + /// \brief Inserts a line break into the middle of a token. + /// + /// Will break at \p Offset inside \p Tok, putting \p Prefix before the line + /// break and \p Postfix before the rest of the token starts in the next line. + /// + /// \p InPPDirective, \p Spaces, \p WhitespaceStartColumn and \p Style are + /// used to generate the correct line break. + void breakToken(const FormatToken &Tok, unsigned Offset, + unsigned ReplaceChars, StringRef Prefix, StringRef Postfix, + bool InPPDirective, unsigned Spaces, + unsigned WhitespaceStartColumn) { + std::string NewLineText; + if (!InPPDirective) + NewLineText = getNewLineText(1, Spaces); + else + NewLineText = getNewLineText(1, Spaces, WhitespaceStartColumn); + std::string ReplacementText = (Prefix + NewLineText + Postfix).str(); + SourceLocation Location = Tok.Tok.getLocation().getLocWithOffset(Offset); + Replaces.insert(tooling::Replacement(SourceMgr, Location, ReplaceChars, + ReplacementText)); + } + + /// \brief Returns all the \c Replacements created during formatting. + const tooling::Replacements &generateReplacements() { + alignComments(); + return Replaces; + } + + void addUntouchableComment(unsigned Column) { + StoredComment Comment; + Comment.MinColumn = Column; + Comment.MaxColumn = Column; + Comment.Untouchable = true; + Comments.push_back(Comment); + } + +private: + static StringRef getLineCommentPrefix(StringRef Comment) { + const char *KnownPrefixes[] = { "/// ", "///", "// ", "//" }; + for (size_t i = 0; i < llvm::array_lengthof(KnownPrefixes); ++i) + if (Comment.startswith(KnownPrefixes[i])) + return KnownPrefixes[i]; + return ""; + } + + /// \brief Finds a common prefix of lines of a block comment to properly + /// indent (and possibly decorate with '*'s) added lines. + /// + /// The first line is ignored (it's special and starts with /*). The number of + /// lines should be more than one. + static StringRef findCommentLinesPrefix(ArrayRef<StringRef> Lines, + const char *PrefixChars = " *") { + assert(Lines.size() > 1); + StringRef Prefix(Lines[1].data(), Lines[1].find_first_not_of(PrefixChars)); + for (size_t i = 2; i < Lines.size(); ++i) { + for (size_t j = 0; j < Prefix.size() && j < Lines[i].size(); ++j) { + if (Prefix[j] != Lines[i][j]) { + Prefix = Prefix.substr(0, j); + break; + } + } + } + return Prefix; + } + + /// \brief Splits one line in a line or block comment, if it doesn't fit to + /// provided column limit. Removes trailing whitespace in each line. + /// + /// \param Line points to the line contents without leading // or /*. + /// + /// \param StartColumn is the column where the first character of Line will be + /// located after formatting. + /// + /// \param LinePrefix is inserted after each line break. + /// + /// When \param InPPDirective is true, each line break will be preceded by a + /// backslash in the last column to make line breaks inside the comment + /// visually consistent with line breaks outside the comment. This only makes + /// sense for block comments. + /// + /// When \param CommentHasMoreLines is false, no line breaks/trailing + /// backslashes will be inserted after it. + void splitLineInComment(const FormatToken &Tok, StringRef Line, + size_t StartColumn, StringRef LinePrefix, + bool InPPDirective, bool CommentHasMoreLines, + const char *WhiteSpaceChars = " ") { + size_t ColumnLimit = calculateColumnLimit(Style, InPPDirective); + const char *TokenStart = SourceMgr.getCharacterData(Tok.Tok.getLocation()); + + StringRef TrimmedLine = Line.rtrim(); + int TrailingSpaceLength = Line.size() - TrimmedLine.size(); + + // Don't touch leading whitespace. + Line = TrimmedLine.ltrim(); + StartColumn += TrimmedLine.size() - Line.size(); + + while (Line.size() + StartColumn > ColumnLimit) { + // Try to break at the last whitespace before the column limit. + size_t SpacePos = + Line.find_last_of(WhiteSpaceChars, ColumnLimit - StartColumn + 1); + if (SpacePos == StringRef::npos) { + // Try to find any whitespace in the line. + SpacePos = Line.find_first_of(WhiteSpaceChars); + if (SpacePos == StringRef::npos) // No whitespace found, give up. + break; + } + + StringRef NextCut = Line.substr(0, SpacePos).rtrim(); + StringRef RemainingLine = Line.substr(SpacePos).ltrim(); + if (RemainingLine.empty()) + break; + + if (RemainingLine == "*/" && LinePrefix.endswith("* ")) + LinePrefix = LinePrefix.substr(0, LinePrefix.size() - 2); + + Line = RemainingLine; + + size_t ReplaceChars = Line.begin() - NextCut.end(); + breakToken(Tok, NextCut.end() - TokenStart, ReplaceChars, "", LinePrefix, + InPPDirective, 0, NextCut.size() + StartColumn); + StartColumn = LinePrefix.size(); + } + + if (TrailingSpaceLength > 0 || (InPPDirective && CommentHasMoreLines)) { + // Remove trailing whitespace/insert backslash. + 1 is for \n + breakToken(Tok, Line.end() - TokenStart, TrailingSpaceLength + 1, "", "", + InPPDirective, 0, Line.size() + StartColumn); + } + } + + /// \brief Changes indentation of all lines in a block comment by Indent, + /// removes trailing whitespace from each line, splits lines that end up + /// exceeding the column limit. + void indentBlockComment(const AnnotatedToken &Tok, int Indent, + int WhitespaceStartColumn, int NewLines, + bool InPPDirective) { + assert(Tok.Type == TT_BlockComment); + int StartColumn = Indent + (NewLines == 0 ? WhitespaceStartColumn : 0); + const SourceLocation TokenLoc = Tok.FormatTok.Tok.getLocation(); + const int CurrentIndent = SourceMgr.getSpellingColumnNumber(TokenLoc) - 1; + const int IndentDelta = Indent - CurrentIndent; + const StringRef Text(SourceMgr.getCharacterData(TokenLoc), + Tok.FormatTok.TokenLength); + assert(Text.startswith("/*") && Text.endswith("*/")); + + SmallVector<StringRef, 16> Lines; + Text.split(Lines, "\n"); + + if (IndentDelta > 0) { + std::string WhiteSpace(IndentDelta, ' '); + for (size_t i = 1; i < Lines.size(); ++i) { + Replaces.insert(tooling::Replacement( + SourceMgr, TokenLoc.getLocWithOffset(Lines[i].data() - Text.data()), + 0, WhiteSpace)); + } + } else if (IndentDelta < 0) { + std::string WhiteSpace(-IndentDelta, ' '); + // Check that the line is indented enough. + for (size_t i = 1; i < Lines.size(); ++i) { + if (!Lines[i].startswith(WhiteSpace)) + return; + } + for (size_t i = 1; i < Lines.size(); ++i) { + Replaces.insert(tooling::Replacement( + SourceMgr, TokenLoc.getLocWithOffset(Lines[i].data() - Text.data()), + -IndentDelta, "")); + } + } + + // Split long lines in comments. + size_t OldPrefixSize = 0; + std::string NewPrefix; + if (Lines.size() > 1) { + StringRef CurrentPrefix = findCommentLinesPrefix(Lines); + OldPrefixSize = CurrentPrefix.size(); + NewPrefix = (IndentDelta < 0) + ? CurrentPrefix.substr(-IndentDelta).str() + : std::string(IndentDelta, ' ') + CurrentPrefix.str(); + if (CurrentPrefix.endswith("*")) { + NewPrefix += " "; + ++OldPrefixSize; + } + } else if (Tok.Parent == 0) { + NewPrefix = std::string(StartColumn, ' ') + " * "; + } + + StartColumn += 2; + for (size_t i = 0; i < Lines.size(); ++i) { + StringRef Line = Lines[i].substr(i == 0 ? 2 : OldPrefixSize); + splitLineInComment(Tok.FormatTok, Line, StartColumn, NewPrefix, + InPPDirective, i != Lines.size() - 1); + StartColumn = NewPrefix.size(); + } + } + + std::string getNewLineText(unsigned NewLines, unsigned Spaces) { + return std::string(NewLines, '\n') + std::string(Spaces, ' '); + } + + std::string getNewLineText(unsigned NewLines, unsigned Spaces, + unsigned WhitespaceStartColumn) { + std::string NewLineText; + if (NewLines > 0) { + unsigned Offset = + std::min<int>(Style.ColumnLimit - 1, WhitespaceStartColumn); + for (unsigned i = 0; i < NewLines; ++i) { + NewLineText += std::string(Style.ColumnLimit - Offset - 1, ' '); + NewLineText += "\\\n"; + Offset = 0; + } + } + return NewLineText + std::string(Spaces, ' '); + } + + /// \brief Structure to store a comment for later layout and alignment. + struct StoredComment { + FormatToken Tok; + unsigned MinColumn; + unsigned MaxColumn; + unsigned NewLines; + unsigned Spaces; + bool Untouchable; + }; + SmallVector<StoredComment, 16> Comments; + typedef SmallVector<StoredComment, 16>::iterator comment_iterator; + + /// \brief Try to align all stashed comments. + void alignComments() { + unsigned MinColumn = 0; + unsigned MaxColumn = UINT_MAX; + comment_iterator Start = Comments.begin(); + for (comment_iterator I = Start, E = Comments.end(); I != E; ++I) { + if (I->MinColumn > MaxColumn || I->MaxColumn < MinColumn) { + alignComments(Start, I, MinColumn); + MinColumn = I->MinColumn; + MaxColumn = I->MaxColumn; + Start = I; + } else { + MinColumn = std::max(MinColumn, I->MinColumn); + MaxColumn = std::min(MaxColumn, I->MaxColumn); + } + } + alignComments(Start, Comments.end(), MinColumn); + Comments.clear(); + } + + /// \brief Put all the comments between \p I and \p E into \p Column. + void alignComments(comment_iterator I, comment_iterator E, unsigned Column) { + while (I != E) { + if (!I->Untouchable) { + unsigned Spaces = I->Spaces + Column - I->MinColumn; + storeReplacement(I->Tok, getNewLineText(I->NewLines, Spaces)); + } + ++I; + } + } + + /// \brief Stores \p Text as the replacement for the whitespace in front of + /// \p Tok. + void storeReplacement(const FormatToken &Tok, const std::string Text) { + // Don't create a replacement, if it does not change anything. + if (StringRef(SourceMgr.getCharacterData(Tok.WhiteSpaceStart), + Tok.WhiteSpaceLength) == Text) + return; + + Replaces.insert(tooling::Replacement(SourceMgr, Tok.WhiteSpaceStart, + Tok.WhiteSpaceLength, Text)); + } + + SourceManager &SourceMgr; + tooling::Replacements Replaces; + const FormatStyle &Style; +}; + +class UnwrappedLineFormatter { +public: + UnwrappedLineFormatter(const FormatStyle &Style, SourceManager &SourceMgr, + const AnnotatedLine &Line, unsigned FirstIndent, + const AnnotatedToken &RootToken, + WhitespaceManager &Whitespaces, bool StructuralError) + : Style(Style), SourceMgr(SourceMgr), Line(Line), + FirstIndent(FirstIndent), RootToken(RootToken), + Whitespaces(Whitespaces), Count(0) {} + + /// \brief Formats an \c UnwrappedLine. + /// + /// \returns The column after the last token in the last line of the + /// \c UnwrappedLine. + unsigned format(const AnnotatedLine *NextLine) { + // Initialize state dependent on indent. + LineState State; + State.Column = FirstIndent; + State.NextToken = &RootToken; + State.Stack.push_back( + ParenState(FirstIndent, FirstIndent, !Style.BinPackParameters, + /*HasMultiParameterLine=*/ false)); + State.LineContainsContinuedForLoopSection = false; + State.ParenLevel = 0; + State.StartOfStringLiteral = 0; + State.StartOfLineLevel = State.ParenLevel; + + DEBUG({ + DebugTokenState(*State.NextToken); + }); + + // The first token has already been indented and thus consumed. + moveStateToNextToken(State, /*DryRun=*/ false); + + // If everything fits on a single line, just put it there. + unsigned ColumnLimit = Style.ColumnLimit; + if (NextLine && NextLine->InPPDirective && + !NextLine->First.FormatTok.HasUnescapedNewline) + ColumnLimit = getColumnLimit(); + if (Line.Last->TotalLength <= ColumnLimit - FirstIndent) { + while (State.NextToken != NULL) { + addTokenToState(false, false, State); + } + return State.Column; + } + + // If the ObjC method declaration does not fit on a line, we should format + // it with one arg per line. + if (Line.Type == LT_ObjCMethodDecl) + State.Stack.back().BreakBeforeParameter = true; + + // Find best solution in solution space. + return analyzeSolutionSpace(State); + } + +private: + void DebugTokenState(const AnnotatedToken &AnnotatedTok) { + const Token &Tok = AnnotatedTok.FormatTok.Tok; + llvm::errs() << StringRef(SourceMgr.getCharacterData(Tok.getLocation()), + Tok.getLength()); + llvm::errs(); + } + + struct ParenState { + ParenState(unsigned Indent, unsigned LastSpace, bool AvoidBinPacking, + bool HasMultiParameterLine) + : Indent(Indent), LastSpace(LastSpace), FirstLessLess(0), + BreakBeforeClosingBrace(false), QuestionColumn(0), + AvoidBinPacking(AvoidBinPacking), BreakBeforeParameter(false), + HasMultiParameterLine(HasMultiParameterLine), ColonPos(0), + StartOfFunctionCall(0), NestedNameSpecifierContinuation(0), + CallContinuation(0), VariablePos(0) {} + + /// \brief The position to which a specific parenthesis level needs to be + /// indented. + unsigned Indent; + + /// \brief The position of the last space on each level. + /// + /// Used e.g. to break like: + /// functionCall(Parameter, otherCall( + /// OtherParameter)); + unsigned LastSpace; + + /// \brief The position the first "<<" operator encountered on each level. + /// + /// Used to align "<<" operators. 0 if no such operator has been encountered + /// on a level. + unsigned FirstLessLess; + + /// \brief Whether a newline needs to be inserted before the block's closing + /// brace. + /// + /// We only want to insert a newline before the closing brace if there also + /// was a newline after the beginning left brace. + bool BreakBeforeClosingBrace; + + /// \brief The column of a \c ? in a conditional expression; + unsigned QuestionColumn; + + /// \brief Avoid bin packing, i.e. multiple parameters/elements on multiple + /// lines, in this context. + bool AvoidBinPacking; + + /// \brief Break after the next comma (or all the commas in this context if + /// \c AvoidBinPacking is \c true). + bool BreakBeforeParameter; + + /// \brief This context already has a line with more than one parameter. + bool HasMultiParameterLine; + + /// \brief The position of the colon in an ObjC method declaration/call. + unsigned ColonPos; + + /// \brief The start of the most recent function in a builder-type call. + unsigned StartOfFunctionCall; + + /// \brief If a nested name specifier was broken over multiple lines, this + /// contains the start column of the second line. Otherwise 0. + unsigned NestedNameSpecifierContinuation; + + /// \brief If a call expression was broken over multiple lines, this + /// contains the start column of the second line. Otherwise 0. + unsigned CallContinuation; + + /// \brief The column of the first variable name in a variable declaration. + /// + /// Used to align further variables if necessary. + unsigned VariablePos; + + bool operator<(const ParenState &Other) const { + if (Indent != Other.Indent) + return Indent < Other.Indent; + if (LastSpace != Other.LastSpace) + return LastSpace < Other.LastSpace; + if (FirstLessLess != Other.FirstLessLess) + return FirstLessLess < Other.FirstLessLess; + if (BreakBeforeClosingBrace != Other.BreakBeforeClosingBrace) + return BreakBeforeClosingBrace; + if (QuestionColumn != Other.QuestionColumn) + return QuestionColumn < Other.QuestionColumn; + if (AvoidBinPacking != Other.AvoidBinPacking) + return AvoidBinPacking; + if (BreakBeforeParameter != Other.BreakBeforeParameter) + return BreakBeforeParameter; + if (HasMultiParameterLine != Other.HasMultiParameterLine) + return HasMultiParameterLine; + if (ColonPos != Other.ColonPos) + return ColonPos < Other.ColonPos; + if (StartOfFunctionCall != Other.StartOfFunctionCall) + return StartOfFunctionCall < Other.StartOfFunctionCall; + if (NestedNameSpecifierContinuation != + Other.NestedNameSpecifierContinuation) + return NestedNameSpecifierContinuation < + Other.NestedNameSpecifierContinuation; + if (CallContinuation != Other.CallContinuation) + return CallContinuation < Other.CallContinuation; + if (VariablePos != Other.VariablePos) + return VariablePos < Other.VariablePos; + return false; + } + }; + + /// \brief The current state when indenting a unwrapped line. + /// + /// As the indenting tries different combinations this is copied by value. + struct LineState { + /// \brief The number of used columns in the current line. + unsigned Column; + + /// \brief The token that needs to be next formatted. + const AnnotatedToken *NextToken; + + /// \brief \c true if this line contains a continued for-loop section. + bool LineContainsContinuedForLoopSection; + + /// \brief The level of nesting inside (), [], <> and {}. + unsigned ParenLevel; + + /// \brief The \c ParenLevel at the start of this line. + unsigned StartOfLineLevel; + + /// \brief The start column of the string literal, if we're in a string + /// literal sequence, 0 otherwise. + unsigned StartOfStringLiteral; + + /// \brief A stack keeping track of properties applying to parenthesis + /// levels. + std::vector<ParenState> Stack; + + /// \brief Comparison operator to be able to used \c LineState in \c map. + bool operator<(const LineState &Other) const { + if (NextToken != Other.NextToken) + return NextToken < Other.NextToken; + if (Column != Other.Column) + return Column < Other.Column; + if (LineContainsContinuedForLoopSection != + Other.LineContainsContinuedForLoopSection) + return LineContainsContinuedForLoopSection; + if (ParenLevel != Other.ParenLevel) + return ParenLevel < Other.ParenLevel; + if (StartOfLineLevel != Other.StartOfLineLevel) + return StartOfLineLevel < Other.StartOfLineLevel; + if (StartOfStringLiteral != Other.StartOfStringLiteral) + return StartOfStringLiteral < Other.StartOfStringLiteral; + return Stack < Other.Stack; + } + }; + + /// \brief Appends the next token to \p State and updates information + /// necessary for indentation. + /// + /// Puts the token on the current line if \p Newline is \c true and adds a + /// line break and necessary indentation otherwise. + /// + /// If \p DryRun is \c false, also creates and stores the required + /// \c Replacement. + unsigned addTokenToState(bool Newline, bool DryRun, LineState &State) { + const AnnotatedToken &Current = *State.NextToken; + const AnnotatedToken &Previous = *State.NextToken->Parent; + + if (State.Stack.size() == 0 || Current.Type == TT_ImplicitStringLiteral) { + State.Column += State.NextToken->FormatTok.WhiteSpaceLength + + State.NextToken->FormatTok.TokenLength; + if (State.NextToken->Children.empty()) + State.NextToken = NULL; + else + State.NextToken = &State.NextToken->Children[0]; + return 0; + } + + // If we are continuing an expression, we want to indent an extra 4 spaces. + unsigned ContinuationIndent = + std::max(State.Stack.back().LastSpace, State.Stack.back().Indent) + 4; + if (Newline) { + unsigned WhitespaceStartColumn = State.Column; + if (Current.is(tok::r_brace)) { + State.Column = Line.Level * 2; + } else if (Current.is(tok::string_literal) && + State.StartOfStringLiteral != 0) { + State.Column = State.StartOfStringLiteral; + State.Stack.back().BreakBeforeParameter = true; + } else if (Current.is(tok::lessless) && + State.Stack.back().FirstLessLess != 0) { + State.Column = State.Stack.back().FirstLessLess; + } else if (Previous.is(tok::coloncolon)) { + if (State.Stack.back().NestedNameSpecifierContinuation == 0) { + State.Column = ContinuationIndent; + State.Stack.back().NestedNameSpecifierContinuation = State.Column; + } else { + State.Column = State.Stack.back().NestedNameSpecifierContinuation; + } + } else if (Current.isOneOf(tok::period, tok::arrow)) { + if (State.Stack.back().CallContinuation == 0) { + State.Column = ContinuationIndent; + State.Stack.back().CallContinuation = State.Column; + } else { + State.Column = State.Stack.back().CallContinuation; + } + } else if (Current.Type == TT_ConditionalExpr) { + State.Column = State.Stack.back().QuestionColumn; + } else if (Previous.is(tok::comma) && + State.Stack.back().VariablePos != 0) { + State.Column = State.Stack.back().VariablePos; + } else if (Previous.ClosesTemplateDeclaration || + (Current.Type == TT_StartOfName && State.ParenLevel == 0)) { + State.Column = State.Stack.back().Indent; + } else if (Current.Type == TT_ObjCSelectorName) { + if (State.Stack.back().ColonPos > Current.FormatTok.TokenLength) { + State.Column = + State.Stack.back().ColonPos - Current.FormatTok.TokenLength; + } else { + State.Column = State.Stack.back().Indent; + State.Stack.back().ColonPos = + State.Column + Current.FormatTok.TokenLength; + } + } else if (Current.Type == TT_StartOfName || Current.is(tok::question) || + Previous.is(tok::equal) || isComparison(Previous) || + Previous.Type == TT_ObjCMethodExpr) { + State.Column = ContinuationIndent; + } else { + State.Column = State.Stack.back().Indent; + // Ensure that we fall back to indenting 4 spaces instead of just + // flushing continuations left. + if (State.Column == FirstIndent) + State.Column += 4; + } + + if (Current.is(tok::question)) + State.Stack.back().BreakBeforeParameter = true; + if (Previous.isOneOf(tok::comma, tok::semi) && + !State.Stack.back().AvoidBinPacking) + State.Stack.back().BreakBeforeParameter = false; + + if (!DryRun) { + unsigned NewLines = 1; + if (Current.Type == TT_LineComment) + NewLines = + std::max(NewLines, std::min(Current.FormatTok.NewlinesBefore, + Style.MaxEmptyLinesToKeep + 1)); + if (!Line.InPPDirective) + Whitespaces.replaceWhitespace(Current, NewLines, State.Column, + WhitespaceStartColumn); + else + Whitespaces.replacePPWhitespace(Current, NewLines, State.Column, + WhitespaceStartColumn); + } + + State.Stack.back().LastSpace = State.Column; + State.StartOfLineLevel = State.ParenLevel; + + // Any break on this level means that the parent level has been broken + // and we need to avoid bin packing there. + for (unsigned i = 0, e = State.Stack.size() - 1; i != e; ++i) { + State.Stack[i].BreakBeforeParameter = true; + } + if (Current.isOneOf(tok::period, tok::arrow)) + State.Stack.back().BreakBeforeParameter = true; + + // If we break after {, we should also break before the corresponding }. + if (Previous.is(tok::l_brace)) + State.Stack.back().BreakBeforeClosingBrace = true; + + if (State.Stack.back().AvoidBinPacking) { + // If we are breaking after '(', '{', '<', this is not bin packing + // unless AllowAllParametersOfDeclarationOnNextLine is false. + if ((Previous.isNot(tok::l_paren) && Previous.isNot(tok::l_brace)) || + (!Style.AllowAllParametersOfDeclarationOnNextLine && + Line.MustBeDeclaration)) + State.Stack.back().BreakBeforeParameter = true; + } + } else { + if (Current.is(tok::equal) && + (RootToken.is(tok::kw_for) || State.ParenLevel == 0) && + State.Stack.back().VariablePos == 0) { + State.Stack.back().VariablePos = State.Column; + // Move over * and & if they are bound to the variable name. + const AnnotatedToken *Tok = &Previous; + while (Tok && + State.Stack.back().VariablePos >= Tok->FormatTok.TokenLength) { + State.Stack.back().VariablePos -= Tok->FormatTok.TokenLength; + if (Tok->SpacesRequiredBefore != 0) + break; + Tok = Tok->Parent; + } + if (Previous.PartOfMultiVariableDeclStmt) + State.Stack.back().LastSpace = State.Stack.back().VariablePos; + } + + unsigned Spaces = State.NextToken->SpacesRequiredBefore; + + if (!DryRun) + Whitespaces.replaceWhitespace(Current, 0, Spaces, State.Column); + + if (Current.Type == TT_ObjCSelectorName && + State.Stack.back().ColonPos == 0) { + if (State.Stack.back().Indent + Current.LongestObjCSelectorName > + State.Column + Spaces + Current.FormatTok.TokenLength) + State.Stack.back().ColonPos = + State.Stack.back().Indent + Current.LongestObjCSelectorName; + else + State.Stack.back().ColonPos = + State.Column + Spaces + Current.FormatTok.TokenLength; + } + + if (Current.Type != TT_LineComment && + (Previous.isOneOf(tok::l_paren, tok::l_brace) || + State.NextToken->Parent->Type == TT_TemplateOpener)) + State.Stack.back().Indent = State.Column + Spaces; + if (Previous.is(tok::comma) && !isTrailingComment(Current)) + State.Stack.back().HasMultiParameterLine = true; + + State.Column += Spaces; + if (Current.is(tok::l_paren) && Previous.isOneOf(tok::kw_if, tok::kw_for)) + // Treat the condition inside an if as if it was a second function + // parameter, i.e. let nested calls have an indent of 4. + State.Stack.back().LastSpace = State.Column + 1; // 1 is length of "(". + else if (Previous.is(tok::comma)) + State.Stack.back().LastSpace = State.Column; + else if ((Previous.Type == TT_BinaryOperator || + Previous.Type == TT_ConditionalExpr || + Previous.Type == TT_CtorInitializerColon) && + getPrecedence(Previous) != prec::Assignment) + State.Stack.back().LastSpace = State.Column; + else if (Previous.Type == TT_InheritanceColon) + State.Stack.back().Indent = State.Column; + else if (Previous.ParameterCount > 1 && + (Previous.isOneOf(tok::l_paren, tok::l_square, tok::l_brace) || + Previous.Type == TT_TemplateOpener)) + // If this function has multiple parameters, indent nested calls from + // the start of the first parameter. + State.Stack.back().LastSpace = State.Column; + } + + return moveStateToNextToken(State, DryRun); + } + + /// \brief Mark the next token as consumed in \p State and modify its stacks + /// accordingly. + unsigned moveStateToNextToken(LineState &State, bool DryRun) { + const AnnotatedToken &Current = *State.NextToken; + assert(State.Stack.size()); + + if (Current.Type == TT_InheritanceColon) + State.Stack.back().AvoidBinPacking = true; + if (Current.is(tok::lessless) && State.Stack.back().FirstLessLess == 0) + State.Stack.back().FirstLessLess = State.Column; + if (Current.is(tok::question)) + State.Stack.back().QuestionColumn = State.Column; + if (Current.isOneOf(tok::period, tok::arrow) && + Line.Type == LT_BuilderTypeCall && State.ParenLevel == 0) + State.Stack.back().StartOfFunctionCall = + Current.LastInChainOfCalls ? 0 : State.Column; + if (Current.Type == TT_CtorInitializerColon) { + if (Style.ConstructorInitializerAllOnOneLineOrOnePerLine) + State.Stack.back().AvoidBinPacking = true; + State.Stack.back().BreakBeforeParameter = false; + } + + // In ObjC method declaration we align on the ":" of parameters, but we need + // to ensure that we indent parameters on subsequent lines by at least 4. + if (Current.Type == TT_ObjCMethodSpecifier) + State.Stack.back().Indent += 4; + + // Insert scopes created by fake parenthesis. + for (unsigned i = 0, e = Current.FakeLParens; i != e; ++i) { + ParenState NewParenState = State.Stack.back(); + NewParenState.Indent = std::max(State.Column, State.Stack.back().Indent); + NewParenState.BreakBeforeParameter = false; + State.Stack.push_back(NewParenState); + } + + // If we encounter an opening (, [, { or <, we add a level to our stacks to + // prepare for the following tokens. + if (Current.isOneOf(tok::l_paren, tok::l_square, tok::l_brace) || + State.NextToken->Type == TT_TemplateOpener) { + unsigned NewIndent; + bool AvoidBinPacking; + if (Current.is(tok::l_brace)) { + NewIndent = 2 + State.Stack.back().LastSpace; + AvoidBinPacking = false; + } else { + NewIndent = 4 + std::max(State.Stack.back().LastSpace, + State.Stack.back().StartOfFunctionCall); + AvoidBinPacking = + !Style.BinPackParameters || State.Stack.back().AvoidBinPacking; + } + State.Stack.push_back( + ParenState(NewIndent, State.Stack.back().LastSpace, AvoidBinPacking, + State.Stack.back().HasMultiParameterLine)); + ++State.ParenLevel; + } + + // If this '[' opens an ObjC call, determine whether all parameters fit into + // one line and put one per line if they don't. + if (Current.is(tok::l_square) && Current.Type == TT_ObjCMethodExpr && + Current.MatchingParen != NULL) { + if (getLengthToMatchingParen(Current) + State.Column > getColumnLimit()) + State.Stack.back().BreakBeforeParameter = true; + } + + // If we encounter a closing ), ], } or >, we can remove a level from our + // stacks. + if (Current.isOneOf(tok::r_paren, tok::r_square) || + (Current.is(tok::r_brace) && State.NextToken != &RootToken) || + State.NextToken->Type == TT_TemplateCloser) { + State.Stack.pop_back(); + --State.ParenLevel; + } + + // Remove scopes created by fake parenthesis. + for (unsigned i = 0, e = Current.FakeRParens; i != e; ++i) { + unsigned VariablePos = State.Stack.back().VariablePos; + State.Stack.pop_back(); + State.Stack.back().VariablePos = VariablePos; + } + + if (Current.is(tok::string_literal)) { + State.StartOfStringLiteral = State.Column; + } else if (Current.isNot(tok::comment)) { + State.StartOfStringLiteral = 0; + } + + State.Column += Current.FormatTok.TokenLength; + + if (State.NextToken->Children.empty()) + State.NextToken = NULL; + else + State.NextToken = &State.NextToken->Children[0]; + + return breakProtrudingToken(Current, State, DryRun); + } + + /// \brief If the current token sticks out over the end of the line, break + /// it if possible. + unsigned breakProtrudingToken(const AnnotatedToken &Current, LineState &State, + bool DryRun) { + if (Current.isNot(tok::string_literal)) + return 0; + // Only break up default narrow strings. + const char *LiteralData = Current.FormatTok.Tok.getLiteralData(); + if (!LiteralData || *LiteralData != '"') + return 0; + + unsigned Penalty = 0; + unsigned TailOffset = 0; + unsigned TailLength = Current.FormatTok.TokenLength; + unsigned StartColumn = State.Column - Current.FormatTok.TokenLength; + unsigned OffsetFromStart = 0; + while (StartColumn + TailLength > getColumnLimit()) { + StringRef Text = StringRef(LiteralData + TailOffset, TailLength); + if (StartColumn + OffsetFromStart + 1 > getColumnLimit()) + break; + StringRef::size_type SplitPoint = getSplitPoint( + Text, getColumnLimit() - StartColumn - OffsetFromStart - 1); + if (SplitPoint == StringRef::npos) + break; + assert(SplitPoint != 0); + // +2, because 'Text' starts after the opening quotes, and does not + // include the closing quote we need to insert. + unsigned WhitespaceStartColumn = + StartColumn + OffsetFromStart + SplitPoint + 2; + State.Stack.back().LastSpace = StartColumn; + if (!DryRun) { + Whitespaces.breakToken(Current.FormatTok, TailOffset + SplitPoint + 1, + 0, "\"", "\"", Line.InPPDirective, StartColumn, + WhitespaceStartColumn); + } + TailOffset += SplitPoint + 1; + TailLength -= SplitPoint + 1; + OffsetFromStart = 1; + Penalty += Style.PenaltyExcessCharacter; + for (unsigned i = 0, e = State.Stack.size(); i != e; ++i) + State.Stack[i].BreakBeforeParameter = true; + } + State.Column = StartColumn + TailLength; + return Penalty; + } + + StringRef::size_type + getSplitPoint(StringRef Text, StringRef::size_type Offset) { + StringRef::size_type SpaceOffset = Text.rfind(' ', Offset); + if (SpaceOffset != StringRef::npos && SpaceOffset != 0) + return SpaceOffset; + StringRef::size_type SlashOffset = Text.rfind('/', Offset); + if (SlashOffset != StringRef::npos && SlashOffset != 0) + return SlashOffset; + StringRef::size_type Split = getStartOfCharacter(Text, Offset); + if (Split != StringRef::npos && Split > 1) + // Do not split at 0. + return Split - 1; + return StringRef::npos; + } + + StringRef::size_type + getStartOfCharacter(StringRef Text, StringRef::size_type Offset) { + StringRef::size_type NextEscape = Text.find('\\'); + while (NextEscape != StringRef::npos && NextEscape < Offset) { + StringRef::size_type SequenceLength = + getEscapeSequenceLength(Text.substr(NextEscape)); + if (Offset < NextEscape + SequenceLength) + return NextEscape; + NextEscape = Text.find('\\', NextEscape + SequenceLength); + } + return Offset; + } + + unsigned getEscapeSequenceLength(StringRef Text) { + assert(Text[0] == '\\'); + if (Text.size() < 2) + return 1; + + switch (Text[1]) { + case 'u': + return 6; + case 'U': + return 10; + case 'x': + return getHexLength(Text); + default: + if (Text[1] >= '0' && Text[1] <= '7') + return getOctalLength(Text); + return 2; + } + } + + unsigned getHexLength(StringRef Text) { + unsigned I = 2; // Point after '\x'. + while (I < Text.size() && ((Text[I] >= '0' && Text[I] <= '9') || + (Text[I] >= 'a' && Text[I] <= 'f') || + (Text[I] >= 'A' && Text[I] <= 'F'))) { + ++I; + } + return I; + } + + unsigned getOctalLength(StringRef Text) { + unsigned I = 1; + while (I < Text.size() && I < 4 && (Text[I] >= '0' && Text[I] <= '7')) { + ++I; + } + return I; + } + + unsigned getColumnLimit() { + return calculateColumnLimit(Style, Line.InPPDirective); + } + + /// \brief An edge in the solution space from \c Previous->State to \c State, + /// inserting a newline dependent on the \c NewLine. + struct StateNode { + StateNode(const LineState &State, bool NewLine, StateNode *Previous) + : State(State), NewLine(NewLine), Previous(Previous) {} + LineState State; + bool NewLine; + StateNode *Previous; + }; + + /// \brief A pair of <penalty, count> that is used to prioritize the BFS on. + /// + /// In case of equal penalties, we want to prefer states that were inserted + /// first. During state generation we make sure that we insert states first + /// that break the line as late as possible. + typedef std::pair<unsigned, unsigned> OrderedPenalty; + + /// \brief An item in the prioritized BFS search queue. The \c StateNode's + /// \c State has the given \c OrderedPenalty. + typedef std::pair<OrderedPenalty, StateNode *> QueueItem; + + /// \brief The BFS queue type. + typedef std::priority_queue<QueueItem, std::vector<QueueItem>, + std::greater<QueueItem> > QueueType; + + /// \brief Analyze the entire solution space starting from \p InitialState. + /// + /// This implements a variant of Dijkstra's algorithm on the graph that spans + /// the solution space (\c LineStates are the nodes). The algorithm tries to + /// find the shortest path (the one with lowest penalty) from \p InitialState + /// to a state where all tokens are placed. + unsigned analyzeSolutionSpace(LineState &InitialState) { + std::set<LineState> Seen; + + // Insert start element into queue. + StateNode *Node = + new (Allocator.Allocate()) StateNode(InitialState, false, NULL); + Queue.push(QueueItem(OrderedPenalty(0, Count), Node)); + ++Count; + + // While not empty, take first element and follow edges. + while (!Queue.empty()) { + unsigned Penalty = Queue.top().first.first; + StateNode *Node = Queue.top().second; + if (Node->State.NextToken == NULL) { + DEBUG(llvm::errs() << "\n---\nPenalty for line: " << Penalty << "\n"); + break; + } + Queue.pop(); + + if (!Seen.insert(Node->State).second) + // State already examined with lower penalty. + continue; + + addNextStateToQueue(Penalty, Node, /*NewLine=*/ false); + addNextStateToQueue(Penalty, Node, /*NewLine=*/ true); + } + + if (Queue.empty()) + // We were unable to find a solution, do nothing. + // FIXME: Add diagnostic? + return 0; + + // Reconstruct the solution. + reconstructPath(InitialState, Queue.top().second); + DEBUG(llvm::errs() << "---\n"); + + // Return the column after the last token of the solution. + return Queue.top().second->State.Column; + } + + void reconstructPath(LineState &State, StateNode *Current) { + // FIXME: This recursive implementation limits the possible number + // of tokens per line if compiled into a binary with small stack space. + // To become more independent of stack frame limitations we would need + // to also change the TokenAnnotator. + if (Current->Previous == NULL) + return; + reconstructPath(State, Current->Previous); + DEBUG({ + if (Current->NewLine) { + llvm::errs() + << "Penalty for splitting before " + << Current->Previous->State.NextToken->FormatTok.Tok.getName() + << ": " << Current->Previous->State.NextToken->SplitPenalty << "\n"; + } + }); + addTokenToState(Current->NewLine, false, State); + } + + /// \brief Add the following state to the analysis queue \c Queue. + /// + /// Assume the current state is \p PreviousNode and has been reached with a + /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true. + void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode, + bool NewLine) { + if (NewLine && !canBreak(PreviousNode->State)) + return; + if (!NewLine && mustBreak(PreviousNode->State)) + return; + if (NewLine) + Penalty += PreviousNode->State.NextToken->SplitPenalty; + + StateNode *Node = new (Allocator.Allocate()) + StateNode(PreviousNode->State, NewLine, PreviousNode); + Penalty += addTokenToState(NewLine, true, Node->State); + if (Node->State.Column > getColumnLimit()) { + unsigned ExcessCharacters = Node->State.Column - getColumnLimit(); + Penalty += Style.PenaltyExcessCharacter * ExcessCharacters; + } + + Queue.push(QueueItem(OrderedPenalty(Penalty, Count), Node)); + ++Count; + } + + /// \brief Returns \c true, if a line break after \p State is allowed. + bool canBreak(const LineState &State) { + if (!State.NextToken->CanBreakBefore && + !(State.NextToken->is(tok::r_brace) && + State.Stack.back().BreakBeforeClosingBrace)) + return false; + // Trying to insert a parameter on a new line if there are already more than + // one parameter on the current line is bin packing. + if (State.Stack.back().HasMultiParameterLine && + State.Stack.back().AvoidBinPacking) + return false; + return true; + } + + /// \brief Returns \c true, if a line break after \p State is mandatory. + bool mustBreak(const LineState &State) { + if (State.NextToken->MustBreakBefore) + return true; + if (State.NextToken->is(tok::r_brace) && + State.Stack.back().BreakBeforeClosingBrace) + return true; + if (State.NextToken->Parent->is(tok::semi) && + State.LineContainsContinuedForLoopSection) + return true; + if ((State.NextToken->Parent->isOneOf(tok::comma, tok::semi) || + State.NextToken->is(tok::question) || + State.NextToken->Type == TT_ConditionalExpr) && + State.Stack.back().BreakBeforeParameter && + !isTrailingComment(*State.NextToken) && + State.NextToken->isNot(tok::r_paren) && + State.NextToken->isNot(tok::r_brace)) + return true; + // FIXME: Comparing LongestObjCSelectorName to 0 is a hacky way of finding + // out whether it is the first parameter. Clean this up. + if (State.NextToken->Type == TT_ObjCSelectorName && + State.NextToken->LongestObjCSelectorName == 0 && + State.Stack.back().BreakBeforeParameter) + return true; + if ((State.NextToken->Type == TT_CtorInitializerColon || + (State.NextToken->Parent->ClosesTemplateDeclaration && + State.ParenLevel == 0))) + return true; + if (State.NextToken->Type == TT_InlineASMColon) + return true; + // This prevents breaks like: + // ... + // SomeParameter, OtherParameter).DoSomething( + // ... + // As they hide "DoSomething" and generally bad for readability. + if (State.NextToken->isOneOf(tok::period, tok::arrow) && + getRemainingLength(State) + State.Column > getColumnLimit() && + State.ParenLevel < State.StartOfLineLevel) + return true; + return false; + } + + // Returns the total number of columns required for the remaining tokens. + unsigned getRemainingLength(const LineState &State) { + if (State.NextToken && State.NextToken->Parent) + return Line.Last->TotalLength - State.NextToken->Parent->TotalLength; + return 0; + } + + FormatStyle Style; + SourceManager &SourceMgr; + const AnnotatedLine &Line; + const unsigned FirstIndent; + const AnnotatedToken &RootToken; + WhitespaceManager &Whitespaces; + + llvm::SpecificBumpPtrAllocator<StateNode> Allocator; + QueueType Queue; + // Increasing count of \c StateNode items we have created. This is used + // to create a deterministic order independent of the container. + unsigned Count; +}; + +class LexerBasedFormatTokenSource : public FormatTokenSource { +public: + LexerBasedFormatTokenSource(Lexer &Lex, SourceManager &SourceMgr) + : GreaterStashed(false), Lex(Lex), SourceMgr(SourceMgr), + IdentTable(Lex.getLangOpts()) { + Lex.SetKeepWhitespaceMode(true); + } + + virtual FormatToken getNextToken() { + if (GreaterStashed) { + FormatTok.NewlinesBefore = 0; + FormatTok.WhiteSpaceStart = + FormatTok.Tok.getLocation().getLocWithOffset(1); + FormatTok.WhiteSpaceLength = 0; + GreaterStashed = false; + return FormatTok; + } + + FormatTok = FormatToken(); + Lex.LexFromRawLexer(FormatTok.Tok); + StringRef Text = rawTokenText(FormatTok.Tok); + FormatTok.WhiteSpaceStart = FormatTok.Tok.getLocation(); + if (SourceMgr.getFileOffset(FormatTok.WhiteSpaceStart) == 0) + FormatTok.IsFirst = true; + + // Consume and record whitespace until we find a significant token. + while (FormatTok.Tok.is(tok::unknown)) { + unsigned Newlines = Text.count('\n'); + if (Newlines > 0) + FormatTok.LastNewlineOffset = + FormatTok.WhiteSpaceLength + Text.rfind('\n') + 1; + unsigned EscapedNewlines = Text.count("\\\n"); + FormatTok.NewlinesBefore += Newlines; + FormatTok.HasUnescapedNewline |= EscapedNewlines != Newlines; + FormatTok.WhiteSpaceLength += FormatTok.Tok.getLength(); + + if (FormatTok.Tok.is(tok::eof)) + return FormatTok; + Lex.LexFromRawLexer(FormatTok.Tok); + Text = rawTokenText(FormatTok.Tok); + } + + // Now FormatTok is the next non-whitespace token. + FormatTok.TokenLength = Text.size(); + + // In case the token starts with escaped newlines, we want to + // take them into account as whitespace - this pattern is quite frequent + // in macro definitions. + // FIXME: What do we want to do with other escaped spaces, and escaped + // spaces or newlines in the middle of tokens? + // FIXME: Add a more explicit test. + unsigned i = 0; + while (i + 1 < Text.size() && Text[i] == '\\' && Text[i + 1] == '\n') { + // FIXME: ++FormatTok.NewlinesBefore is missing... + FormatTok.WhiteSpaceLength += 2; + FormatTok.TokenLength -= 2; + i += 2; + } + + if (FormatTok.Tok.is(tok::raw_identifier)) { + IdentifierInfo &Info = IdentTable.get(Text); + FormatTok.Tok.setIdentifierInfo(&Info); + FormatTok.Tok.setKind(Info.getTokenID()); + } + + if (FormatTok.Tok.is(tok::greatergreater)) { + FormatTok.Tok.setKind(tok::greater); + FormatTok.TokenLength = 1; + GreaterStashed = true; + } + + // If we reformat comments, we remove trailing whitespace. Update the length + // accordingly. + if (FormatTok.Tok.is(tok::comment)) + FormatTok.TokenLength = Text.rtrim().size(); + + return FormatTok; + } + + IdentifierTable &getIdentTable() { return IdentTable; } + +private: + FormatToken FormatTok; + bool GreaterStashed; + Lexer &Lex; + SourceManager &SourceMgr; + IdentifierTable IdentTable; + + /// Returns the text of \c FormatTok. + StringRef rawTokenText(Token &Tok) { + return StringRef(SourceMgr.getCharacterData(Tok.getLocation()), + Tok.getLength()); + } +}; + +class Formatter : public UnwrappedLineConsumer { +public: + Formatter(DiagnosticsEngine &Diag, const FormatStyle &Style, Lexer &Lex, + SourceManager &SourceMgr, + const std::vector<CharSourceRange> &Ranges) + : Diag(Diag), Style(Style), Lex(Lex), SourceMgr(SourceMgr), + Whitespaces(SourceMgr, Style), Ranges(Ranges) {} + + virtual ~Formatter() {} + + tooling::Replacements format() { + LexerBasedFormatTokenSource Tokens(Lex, SourceMgr); + UnwrappedLineParser Parser(Diag, Style, Tokens, *this); + StructuralError = Parser.parse(); + unsigned PreviousEndOfLineColumn = 0; + TokenAnnotator Annotator(Style, SourceMgr, Lex, + Tokens.getIdentTable().get("in")); + for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) { + Annotator.annotate(AnnotatedLines[i]); + } + deriveLocalStyle(); + for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) { + Annotator.calculateFormattingInformation(AnnotatedLines[i]); + + // Adapt level to the next line if this is a comment. + // FIXME: Can/should this be done in the UnwrappedLineParser? + if (i + 1 != e && AnnotatedLines[i].First.is(tok::comment) && + AnnotatedLines[i].First.Children.empty() && + AnnotatedLines[i + 1].First.isNot(tok::r_brace)) + AnnotatedLines[i].Level = AnnotatedLines[i + 1].Level; + } + std::vector<int> IndentForLevel; + bool PreviousLineWasTouched = false; + const AnnotatedToken *PreviousLineLastToken = 0; + for (std::vector<AnnotatedLine>::iterator I = AnnotatedLines.begin(), + E = AnnotatedLines.end(); + I != E; ++I) { + const AnnotatedLine &TheLine = *I; + const FormatToken &FirstTok = TheLine.First.FormatTok; + int Offset = getIndentOffset(TheLine.First); + while (IndentForLevel.size() <= TheLine.Level) + IndentForLevel.push_back(-1); + IndentForLevel.resize(TheLine.Level + 1); + bool WasMoved = PreviousLineWasTouched && FirstTok.NewlinesBefore == 0; + if (TheLine.First.is(tok::eof)) { + if (PreviousLineWasTouched) { + unsigned NewLines = std::min(FirstTok.NewlinesBefore, 1u); + Whitespaces.replaceWhitespace(TheLine.First, NewLines, /*Indent*/ 0, + /*WhitespaceStartColumn*/ 0); + } + } else if (TheLine.Type != LT_Invalid && + (WasMoved || touchesLine(TheLine))) { + unsigned LevelIndent = getIndent(IndentForLevel, TheLine.Level); + unsigned Indent = LevelIndent; + if (static_cast<int>(Indent) + Offset >= 0) + Indent += Offset; + if (!FirstTok.WhiteSpaceStart.isValid() || StructuralError) { + Indent = LevelIndent = + SourceMgr.getSpellingColumnNumber(FirstTok.Tok.getLocation()) - 1; + } else { + formatFirstToken(TheLine.First, PreviousLineLastToken, Indent, + TheLine.InPPDirective, PreviousEndOfLineColumn); + } + tryFitMultipleLinesInOne(Indent, I, E); + UnwrappedLineFormatter Formatter(Style, SourceMgr, TheLine, Indent, + TheLine.First, Whitespaces, + StructuralError); + PreviousEndOfLineColumn = + Formatter.format(I + 1 != E ? &*(I + 1) : NULL); + IndentForLevel[TheLine.Level] = LevelIndent; + PreviousLineWasTouched = true; + } else { + if (FirstTok.NewlinesBefore > 0 || FirstTok.IsFirst) { + unsigned Indent = + SourceMgr.getSpellingColumnNumber(FirstTok.Tok.getLocation()) - 1; + unsigned LevelIndent = Indent; + if (static_cast<int>(LevelIndent) - Offset >= 0) + LevelIndent -= Offset; + if (TheLine.First.isNot(tok::comment)) + IndentForLevel[TheLine.Level] = LevelIndent; + + // Remove trailing whitespace of the previous line if it was touched. + if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine)) + formatFirstToken(TheLine.First, PreviousLineLastToken, Indent, + TheLine.InPPDirective, PreviousEndOfLineColumn); + } + // If we did not reformat this unwrapped line, the column at the end of + // the last token is unchanged - thus, we can calculate the end of the + // last token. + SourceLocation LastLoc = TheLine.Last->FormatTok.Tok.getLocation(); + PreviousEndOfLineColumn = + SourceMgr.getSpellingColumnNumber(LastLoc) + + Lex.MeasureTokenLength(LastLoc, SourceMgr, Lex.getLangOpts()) - 1; + PreviousLineWasTouched = false; + if (TheLine.Last->is(tok::comment)) + Whitespaces.addUntouchableComment(SourceMgr.getSpellingColumnNumber( + TheLine.Last->FormatTok.Tok.getLocation()) - 1); + } + PreviousLineLastToken = I->Last; + } + return Whitespaces.generateReplacements(); + } + +private: + void deriveLocalStyle() { + unsigned CountBoundToVariable = 0; + unsigned CountBoundToType = 0; + bool HasCpp03IncompatibleFormat = false; + for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) { + if (AnnotatedLines[i].First.Children.empty()) + continue; + AnnotatedToken *Tok = &AnnotatedLines[i].First.Children[0]; + while (!Tok->Children.empty()) { + if (Tok->Type == TT_PointerOrReference) { + bool SpacesBefore = Tok->FormatTok.WhiteSpaceLength > 0; + bool SpacesAfter = Tok->Children[0].FormatTok.WhiteSpaceLength > 0; + if (SpacesBefore && !SpacesAfter) + ++CountBoundToVariable; + else if (!SpacesBefore && SpacesAfter) + ++CountBoundToType; + } + + if (Tok->Type == TT_TemplateCloser && + Tok->Parent->Type == TT_TemplateCloser && + Tok->FormatTok.WhiteSpaceLength == 0) + HasCpp03IncompatibleFormat = true; + Tok = &Tok->Children[0]; + } + } + if (Style.DerivePointerBinding) { + if (CountBoundToType > CountBoundToVariable) + Style.PointerBindsToType = true; + else if (CountBoundToType < CountBoundToVariable) + Style.PointerBindsToType = false; + } + if (Style.Standard == FormatStyle::LS_Auto) { + Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11 + : FormatStyle::LS_Cpp03; + } + } + + /// \brief Get the indent of \p Level from \p IndentForLevel. + /// + /// \p IndentForLevel must contain the indent for the level \c l + /// at \p IndentForLevel[l], or a value < 0 if the indent for + /// that level is unknown. + unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) { + if (IndentForLevel[Level] != -1) + return IndentForLevel[Level]; + if (Level == 0) + return 0; + return getIndent(IndentForLevel, Level - 1) + 2; + } + + /// \brief Get the offset of the line relatively to the level. + /// + /// For example, 'public:' labels in classes are offset by 1 or 2 + /// characters to the left from their level. + int getIndentOffset(const AnnotatedToken &RootToken) { + if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier()) + return Style.AccessModifierOffset; + return 0; + } + + /// \brief Tries to merge lines into one. + /// + /// This will change \c Line and \c AnnotatedLine to contain the merged line, + /// if possible; note that \c I will be incremented when lines are merged. + /// + /// Returns whether the resulting \c Line can fit in a single line. + void tryFitMultipleLinesInOne(unsigned Indent, + std::vector<AnnotatedLine>::iterator &I, + std::vector<AnnotatedLine>::iterator E) { + // We can never merge stuff if there are trailing line comments. + if (I->Last->Type == TT_LineComment) + return; + + unsigned Limit = Style.ColumnLimit - Indent; + // If we already exceed the column limit, we set 'Limit' to 0. The different + // tryMerge..() functions can then decide whether to still do merging. + Limit = I->Last->TotalLength > Limit ? 0 : Limit - I->Last->TotalLength; + + if (I + 1 == E || (I + 1)->Type == LT_Invalid) + return; + + if (I->Last->is(tok::l_brace)) { + tryMergeSimpleBlock(I, E, Limit); + } else if (I->First.is(tok::kw_if)) { + tryMergeSimpleIf(I, E, Limit); + } else if (I->InPPDirective && (I->First.FormatTok.HasUnescapedNewline || + I->First.FormatTok.IsFirst)) { + tryMergeSimplePPDirective(I, E, Limit); + } + return; + } + + void tryMergeSimplePPDirective(std::vector<AnnotatedLine>::iterator &I, + std::vector<AnnotatedLine>::iterator E, + unsigned Limit) { + if (Limit == 0) + return; + AnnotatedLine &Line = *I; + if (!(I + 1)->InPPDirective || (I + 1)->First.FormatTok.HasUnescapedNewline) + return; + if (I + 2 != E && (I + 2)->InPPDirective && + !(I + 2)->First.FormatTok.HasUnescapedNewline) + return; + if (1 + (I + 1)->Last->TotalLength > Limit) + return; + join(Line, *(++I)); + } + + void tryMergeSimpleIf(std::vector<AnnotatedLine>::iterator &I, + std::vector<AnnotatedLine>::iterator E, + unsigned Limit) { + if (Limit == 0) + return; + if (!Style.AllowShortIfStatementsOnASingleLine) + return; + if ((I + 1)->InPPDirective != I->InPPDirective || + ((I + 1)->InPPDirective && + (I + 1)->First.FormatTok.HasUnescapedNewline)) + return; + AnnotatedLine &Line = *I; + if (Line.Last->isNot(tok::r_paren)) + return; + if (1 + (I + 1)->Last->TotalLength > Limit) + return; + if ((I + 1)->First.is(tok::kw_if) || (I + 1)->First.Type == TT_LineComment) + return; + // Only inline simple if's (no nested if or else). + if (I + 2 != E && (I + 2)->First.is(tok::kw_else)) + return; + join(Line, *(++I)); + } + + void tryMergeSimpleBlock(std::vector<AnnotatedLine>::iterator &I, + std::vector<AnnotatedLine>::iterator E, + unsigned Limit) { + // First, check that the current line allows merging. This is the case if + // we're not in a control flow statement and the last token is an opening + // brace. + AnnotatedLine &Line = *I; + if (Line.First.isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace, + tok::kw_else, tok::kw_try, tok::kw_catch, + tok::kw_for, + // This gets rid of all ObjC @ keywords and methods. + tok::at, tok::minus, tok::plus)) + return; + + AnnotatedToken *Tok = &(I + 1)->First; + if (Tok->Children.empty() && Tok->is(tok::r_brace) && + !Tok->MustBreakBefore) { + // We merge empty blocks even if the line exceeds the column limit. + Tok->SpacesRequiredBefore = 0; + Tok->CanBreakBefore = true; + join(Line, *(I + 1)); + I += 1; + } else if (Limit != 0) { + // Check that we still have three lines and they fit into the limit. + if (I + 2 == E || (I + 2)->Type == LT_Invalid || + !nextTwoLinesFitInto(I, Limit)) + return; + + // Second, check that the next line does not contain any braces - if it + // does, readability declines when putting it into a single line. + if ((I + 1)->Last->Type == TT_LineComment || Tok->MustBreakBefore) + return; + do { + if (Tok->isOneOf(tok::l_brace, tok::r_brace)) + return; + Tok = Tok->Children.empty() ? NULL : &Tok->Children.back(); + } while (Tok != NULL); + + // Last, check that the third line contains a single closing brace. + Tok = &(I + 2)->First; + if (!Tok->Children.empty() || Tok->isNot(tok::r_brace) || + Tok->MustBreakBefore) + return; + + join(Line, *(I + 1)); + join(Line, *(I + 2)); + I += 2; + } + } + + bool nextTwoLinesFitInto(std::vector<AnnotatedLine>::iterator I, + unsigned Limit) { + return 1 + (I + 1)->Last->TotalLength + 1 + (I + 2)->Last->TotalLength <= + Limit; + } + + void join(AnnotatedLine &A, const AnnotatedLine &B) { + unsigned LengthA = A.Last->TotalLength + B.First.SpacesRequiredBefore; + A.Last->Children.push_back(B.First); + while (!A.Last->Children.empty()) { + A.Last->Children[0].Parent = A.Last; + A.Last->Children[0].TotalLength += LengthA; + A.Last = &A.Last->Children[0]; + } + } + + bool touchesRanges(const CharSourceRange &Range) { + for (unsigned i = 0, e = Ranges.size(); i != e; ++i) { + if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), + Ranges[i].getBegin()) && + !SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(), + Range.getBegin())) + return true; + } + return false; + } + + bool touchesLine(const AnnotatedLine &TheLine) { + const FormatToken *First = &TheLine.First.FormatTok; + const FormatToken *Last = &TheLine.Last->FormatTok; + CharSourceRange LineRange = CharSourceRange::getTokenRange( + First->WhiteSpaceStart.getLocWithOffset(First->LastNewlineOffset), + Last->Tok.getLocation()); + return touchesRanges(LineRange); + } + + bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) { + const FormatToken *First = &TheLine.First.FormatTok; + CharSourceRange LineRange = CharSourceRange::getCharRange( + First->WhiteSpaceStart, + First->WhiteSpaceStart.getLocWithOffset(First->LastNewlineOffset)); + return touchesRanges(LineRange); + } + + virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) { + AnnotatedLines.push_back(AnnotatedLine(TheLine)); + } + + /// \brief Add a new line and the required indent before the first Token + /// of the \c UnwrappedLine if there was no structural parsing error. + /// Returns the indent level of the \c UnwrappedLine. + void formatFirstToken(const AnnotatedToken &RootToken, + const AnnotatedToken *PreviousToken, unsigned Indent, + bool InPPDirective, unsigned PreviousEndOfLineColumn) { + const FormatToken &Tok = RootToken.FormatTok; + + unsigned Newlines = + std::min(Tok.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1); + if (Newlines == 0 && !Tok.IsFirst) + Newlines = 1; + + if (!InPPDirective || Tok.HasUnescapedNewline) { + // Insert extra new line before access specifiers. + if (PreviousToken && PreviousToken->isOneOf(tok::semi, tok::r_brace) && + RootToken.isAccessSpecifier() && Tok.NewlinesBefore == 1) + ++Newlines; + + Whitespaces.replaceWhitespace(RootToken, Newlines, Indent, 0); + } else { + Whitespaces.replacePPWhitespace(RootToken, Newlines, Indent, + PreviousEndOfLineColumn); + } + } + + DiagnosticsEngine &Diag; + FormatStyle Style; + Lexer &Lex; + SourceManager &SourceMgr; + WhitespaceManager Whitespaces; + std::vector<CharSourceRange> Ranges; + std::vector<AnnotatedLine> AnnotatedLines; + bool StructuralError; +}; + +tooling::Replacements +reformat(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr, + std::vector<CharSourceRange> Ranges, DiagnosticConsumer *DiagClient) { + IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts = new DiagnosticOptions(); + OwningPtr<DiagnosticConsumer> DiagPrinter; + if (DiagClient == 0) { + DiagPrinter.reset(new TextDiagnosticPrinter(llvm::errs(), &*DiagOpts)); + DiagPrinter->BeginSourceFile(Lex.getLangOpts(), Lex.getPP()); + DiagClient = DiagPrinter.get(); + } + DiagnosticsEngine Diagnostics( + IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs()), &*DiagOpts, + DiagClient, false); + Diagnostics.setSourceManager(&SourceMgr); + Formatter formatter(Diagnostics, Style, Lex, SourceMgr, Ranges); + return formatter.format(); +} + +LangOptions getFormattingLangOpts() { + LangOptions LangOpts; + LangOpts.CPlusPlus = 1; + LangOpts.CPlusPlus11 = 1; + LangOpts.LineComment = 1; + LangOpts.Bool = 1; + LangOpts.ObjC1 = 1; + LangOpts.ObjC2 = 1; + return LangOpts; +} + +} // namespace format +} // namespace clang |