1249261Sdim//===--- Format.cpp - Format C++ code -------------------------------------===// 2249261Sdim// 3249261Sdim// The LLVM Compiler Infrastructure 4249261Sdim// 5249261Sdim// This file is distributed under the University of Illinois Open Source 6249261Sdim// License. See LICENSE.TXT for details. 7249261Sdim// 8249261Sdim//===----------------------------------------------------------------------===// 9249261Sdim/// 10249261Sdim/// \file 11249261Sdim/// \brief This file implements functions declared in Format.h. This will be 12249261Sdim/// split into separate files as we go. 13249261Sdim/// 14249261Sdim//===----------------------------------------------------------------------===// 15249261Sdim 16249261Sdim#define DEBUG_TYPE "format-formatter" 17249261Sdim 18263508Sdim#include "ContinuationIndenter.h" 19249261Sdim#include "TokenAnnotator.h" 20249261Sdim#include "UnwrappedLineParser.h" 21251662Sdim#include "WhitespaceManager.h" 22249261Sdim#include "clang/Basic/Diagnostic.h" 23249261Sdim#include "clang/Basic/SourceManager.h" 24249261Sdim#include "clang/Format/Format.h" 25249261Sdim#include "clang/Lex/Lexer.h" 26249261Sdim#include "llvm/ADT/STLExtras.h" 27249261Sdim#include "llvm/Support/Allocator.h" 28249261Sdim#include "llvm/Support/Debug.h" 29263508Sdim#include "llvm/Support/YAMLTraits.h" 30263508Sdim#include "llvm/Support/Path.h" 31249261Sdim#include <queue> 32249261Sdim#include <string> 33249261Sdim 34263508Sdimnamespace llvm { 35263508Sdimnamespace yaml { 36263508Sdimtemplate <> 37263508Sdimstruct ScalarEnumerationTraits<clang::format::FormatStyle::LanguageStandard> { 38263508Sdim static void enumeration(IO &IO, 39263508Sdim clang::format::FormatStyle::LanguageStandard &Value) { 40263508Sdim IO.enumCase(Value, "Cpp03", clang::format::FormatStyle::LS_Cpp03); 41263508Sdim IO.enumCase(Value, "C++03", clang::format::FormatStyle::LS_Cpp03); 42263508Sdim IO.enumCase(Value, "Cpp11", clang::format::FormatStyle::LS_Cpp11); 43263508Sdim IO.enumCase(Value, "C++11", clang::format::FormatStyle::LS_Cpp11); 44263508Sdim IO.enumCase(Value, "Auto", clang::format::FormatStyle::LS_Auto); 45263508Sdim } 46263508Sdim}; 47263508Sdim 48263508Sdimtemplate <> 49263508Sdimstruct ScalarEnumerationTraits<clang::format::FormatStyle::UseTabStyle> { 50263508Sdim static void enumeration(IO &IO, 51263508Sdim clang::format::FormatStyle::UseTabStyle &Value) { 52263508Sdim IO.enumCase(Value, "Never", clang::format::FormatStyle::UT_Never); 53263508Sdim IO.enumCase(Value, "false", clang::format::FormatStyle::UT_Never); 54263508Sdim IO.enumCase(Value, "Always", clang::format::FormatStyle::UT_Always); 55263508Sdim IO.enumCase(Value, "true", clang::format::FormatStyle::UT_Always); 56263508Sdim IO.enumCase(Value, "ForIndentation", 57263508Sdim clang::format::FormatStyle::UT_ForIndentation); 58263508Sdim } 59263508Sdim}; 60263508Sdim 61263508Sdimtemplate <> 62263508Sdimstruct ScalarEnumerationTraits<clang::format::FormatStyle::BraceBreakingStyle> { 63263508Sdim static void 64263508Sdim enumeration(IO &IO, clang::format::FormatStyle::BraceBreakingStyle &Value) { 65263508Sdim IO.enumCase(Value, "Attach", clang::format::FormatStyle::BS_Attach); 66263508Sdim IO.enumCase(Value, "Linux", clang::format::FormatStyle::BS_Linux); 67263508Sdim IO.enumCase(Value, "Stroustrup", clang::format::FormatStyle::BS_Stroustrup); 68263508Sdim IO.enumCase(Value, "Allman", clang::format::FormatStyle::BS_Allman); 69263508Sdim } 70263508Sdim}; 71263508Sdim 72263508Sdimtemplate <> 73263508Sdimstruct ScalarEnumerationTraits< 74263508Sdim clang::format::FormatStyle::NamespaceIndentationKind> { 75263508Sdim static void 76263508Sdim enumeration(IO &IO, 77263508Sdim clang::format::FormatStyle::NamespaceIndentationKind &Value) { 78263508Sdim IO.enumCase(Value, "None", clang::format::FormatStyle::NI_None); 79263508Sdim IO.enumCase(Value, "Inner", clang::format::FormatStyle::NI_Inner); 80263508Sdim IO.enumCase(Value, "All", clang::format::FormatStyle::NI_All); 81263508Sdim } 82263508Sdim}; 83263508Sdim 84263508Sdimtemplate <> struct MappingTraits<clang::format::FormatStyle> { 85263508Sdim static void mapping(llvm::yaml::IO &IO, clang::format::FormatStyle &Style) { 86263508Sdim if (IO.outputting()) { 87263508Sdim StringRef StylesArray[] = { "LLVM", "Google", "Chromium", 88263508Sdim "Mozilla", "WebKit" }; 89263508Sdim ArrayRef<StringRef> Styles(StylesArray); 90263508Sdim for (size_t i = 0, e = Styles.size(); i < e; ++i) { 91263508Sdim StringRef StyleName(Styles[i]); 92263508Sdim clang::format::FormatStyle PredefinedStyle; 93263508Sdim if (clang::format::getPredefinedStyle(StyleName, &PredefinedStyle) && 94263508Sdim Style == PredefinedStyle) { 95263508Sdim IO.mapOptional("# BasedOnStyle", StyleName); 96263508Sdim break; 97263508Sdim } 98263508Sdim } 99263508Sdim } else { 100263508Sdim StringRef BasedOnStyle; 101263508Sdim IO.mapOptional("BasedOnStyle", BasedOnStyle); 102263508Sdim if (!BasedOnStyle.empty()) 103263508Sdim if (!clang::format::getPredefinedStyle(BasedOnStyle, &Style)) { 104263508Sdim IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle)); 105263508Sdim return; 106263508Sdim } 107263508Sdim } 108263508Sdim 109263508Sdim IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset); 110263508Sdim IO.mapOptional("ConstructorInitializerIndentWidth", 111263508Sdim Style.ConstructorInitializerIndentWidth); 112263508Sdim IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft); 113263508Sdim IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments); 114263508Sdim IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine", 115263508Sdim Style.AllowAllParametersOfDeclarationOnNextLine); 116263508Sdim IO.mapOptional("AllowShortIfStatementsOnASingleLine", 117263508Sdim Style.AllowShortIfStatementsOnASingleLine); 118263508Sdim IO.mapOptional("AllowShortLoopsOnASingleLine", 119263508Sdim Style.AllowShortLoopsOnASingleLine); 120263508Sdim IO.mapOptional("AlwaysBreakTemplateDeclarations", 121263508Sdim Style.AlwaysBreakTemplateDeclarations); 122263508Sdim IO.mapOptional("AlwaysBreakBeforeMultilineStrings", 123263508Sdim Style.AlwaysBreakBeforeMultilineStrings); 124263508Sdim IO.mapOptional("BreakBeforeBinaryOperators", 125263508Sdim Style.BreakBeforeBinaryOperators); 126263508Sdim IO.mapOptional("BreakBeforeTernaryOperators", 127263508Sdim Style.BreakBeforeTernaryOperators); 128263508Sdim IO.mapOptional("BreakConstructorInitializersBeforeComma", 129263508Sdim Style.BreakConstructorInitializersBeforeComma); 130263508Sdim IO.mapOptional("BinPackParameters", Style.BinPackParameters); 131263508Sdim IO.mapOptional("ColumnLimit", Style.ColumnLimit); 132263508Sdim IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine", 133263508Sdim Style.ConstructorInitializerAllOnOneLineOrOnePerLine); 134263508Sdim IO.mapOptional("DerivePointerBinding", Style.DerivePointerBinding); 135263508Sdim IO.mapOptional("ExperimentalAutoDetectBinPacking", 136263508Sdim Style.ExperimentalAutoDetectBinPacking); 137263508Sdim IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels); 138263508Sdim IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep); 139263508Sdim IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation); 140263508Sdim IO.mapOptional("ObjCSpaceBeforeProtocolList", 141263508Sdim Style.ObjCSpaceBeforeProtocolList); 142263508Sdim IO.mapOptional("PenaltyBreakBeforeFirstCallParameter", 143263508Sdim Style.PenaltyBreakBeforeFirstCallParameter); 144263508Sdim IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment); 145263508Sdim IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString); 146263508Sdim IO.mapOptional("PenaltyBreakFirstLessLess", 147263508Sdim Style.PenaltyBreakFirstLessLess); 148263508Sdim IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter); 149263508Sdim IO.mapOptional("PenaltyReturnTypeOnItsOwnLine", 150263508Sdim Style.PenaltyReturnTypeOnItsOwnLine); 151263508Sdim IO.mapOptional("PointerBindsToType", Style.PointerBindsToType); 152263508Sdim IO.mapOptional("SpacesBeforeTrailingComments", 153263508Sdim Style.SpacesBeforeTrailingComments); 154263508Sdim IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle); 155263508Sdim IO.mapOptional("Standard", Style.Standard); 156263508Sdim IO.mapOptional("IndentWidth", Style.IndentWidth); 157263508Sdim IO.mapOptional("TabWidth", Style.TabWidth); 158263508Sdim IO.mapOptional("UseTab", Style.UseTab); 159263508Sdim IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces); 160263508Sdim IO.mapOptional("IndentFunctionDeclarationAfterType", 161263508Sdim Style.IndentFunctionDeclarationAfterType); 162263508Sdim IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses); 163263508Sdim IO.mapOptional("SpacesInAngles", Style.SpacesInAngles); 164263508Sdim IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses); 165263508Sdim IO.mapOptional("SpacesInCStyleCastParentheses", 166263508Sdim Style.SpacesInCStyleCastParentheses); 167263508Sdim IO.mapOptional("SpaceAfterControlStatementKeyword", 168263508Sdim Style.SpaceAfterControlStatementKeyword); 169263508Sdim IO.mapOptional("SpaceBeforeAssignmentOperators", 170263508Sdim Style.SpaceBeforeAssignmentOperators); 171263508Sdim IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth); 172263508Sdim } 173263508Sdim}; 174263508Sdim} 175263508Sdim} 176263508Sdim 177249261Sdimnamespace clang { 178249261Sdimnamespace format { 179249261Sdim 180263508Sdimvoid setDefaultPenalties(FormatStyle &Style) { 181263508Sdim Style.PenaltyBreakComment = 60; 182263508Sdim Style.PenaltyBreakFirstLessLess = 120; 183263508Sdim Style.PenaltyBreakString = 1000; 184263508Sdim Style.PenaltyExcessCharacter = 1000000; 185263508Sdim} 186263508Sdim 187249261SdimFormatStyle getLLVMStyle() { 188249261Sdim FormatStyle LLVMStyle; 189251662Sdim LLVMStyle.AccessModifierOffset = -2; 190251662Sdim LLVMStyle.AlignEscapedNewlinesLeft = false; 191263508Sdim LLVMStyle.AlignTrailingComments = true; 192251662Sdim LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true; 193251662Sdim LLVMStyle.AllowShortIfStatementsOnASingleLine = false; 194263508Sdim LLVMStyle.AllowShortLoopsOnASingleLine = false; 195263508Sdim LLVMStyle.AlwaysBreakBeforeMultilineStrings = false; 196263508Sdim LLVMStyle.AlwaysBreakTemplateDeclarations = false; 197251662Sdim LLVMStyle.BinPackParameters = true; 198263508Sdim LLVMStyle.BreakBeforeBinaryOperators = false; 199263508Sdim LLVMStyle.BreakBeforeTernaryOperators = true; 200263508Sdim LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach; 201263508Sdim LLVMStyle.BreakConstructorInitializersBeforeComma = false; 202249261Sdim LLVMStyle.ColumnLimit = 80; 203251662Sdim LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false; 204263508Sdim LLVMStyle.ConstructorInitializerIndentWidth = 4; 205263508Sdim LLVMStyle.Cpp11BracedListStyle = false; 206249261Sdim LLVMStyle.DerivePointerBinding = false; 207263508Sdim LLVMStyle.ExperimentalAutoDetectBinPacking = false; 208249261Sdim LLVMStyle.IndentCaseLabels = false; 209263508Sdim LLVMStyle.IndentFunctionDeclarationAfterType = false; 210263508Sdim LLVMStyle.IndentWidth = 2; 211263508Sdim LLVMStyle.TabWidth = 8; 212251662Sdim LLVMStyle.MaxEmptyLinesToKeep = 1; 213263508Sdim LLVMStyle.NamespaceIndentation = FormatStyle::NI_None; 214249261Sdim LLVMStyle.ObjCSpaceBeforeProtocolList = true; 215251662Sdim LLVMStyle.PointerBindsToType = false; 216251662Sdim LLVMStyle.SpacesBeforeTrailingComments = 1; 217251662Sdim LLVMStyle.Standard = FormatStyle::LS_Cpp03; 218263508Sdim LLVMStyle.UseTab = FormatStyle::UT_Never; 219263508Sdim LLVMStyle.SpacesInParentheses = false; 220263508Sdim LLVMStyle.SpaceInEmptyParentheses = false; 221263508Sdim LLVMStyle.SpacesInCStyleCastParentheses = false; 222263508Sdim LLVMStyle.SpaceAfterControlStatementKeyword = true; 223263508Sdim LLVMStyle.SpaceBeforeAssignmentOperators = true; 224263508Sdim LLVMStyle.ContinuationIndentWidth = 4; 225263508Sdim LLVMStyle.SpacesInAngles = false; 226263508Sdim 227263508Sdim setDefaultPenalties(LLVMStyle); 228263508Sdim LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60; 229263508Sdim LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19; 230263508Sdim 231249261Sdim return LLVMStyle; 232249261Sdim} 233249261Sdim 234249261SdimFormatStyle getGoogleStyle() { 235249261Sdim FormatStyle GoogleStyle; 236251662Sdim GoogleStyle.AccessModifierOffset = -1; 237251662Sdim GoogleStyle.AlignEscapedNewlinesLeft = true; 238263508Sdim GoogleStyle.AlignTrailingComments = true; 239251662Sdim GoogleStyle.AllowAllParametersOfDeclarationOnNextLine = true; 240251662Sdim GoogleStyle.AllowShortIfStatementsOnASingleLine = true; 241263508Sdim GoogleStyle.AllowShortLoopsOnASingleLine = true; 242263508Sdim GoogleStyle.AlwaysBreakBeforeMultilineStrings = true; 243263508Sdim GoogleStyle.AlwaysBreakTemplateDeclarations = true; 244251662Sdim GoogleStyle.BinPackParameters = true; 245263508Sdim GoogleStyle.BreakBeforeBinaryOperators = false; 246263508Sdim GoogleStyle.BreakBeforeTernaryOperators = true; 247263508Sdim GoogleStyle.BreakBeforeBraces = FormatStyle::BS_Attach; 248263508Sdim GoogleStyle.BreakConstructorInitializersBeforeComma = false; 249249261Sdim GoogleStyle.ColumnLimit = 80; 250251662Sdim GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true; 251263508Sdim GoogleStyle.ConstructorInitializerIndentWidth = 4; 252263508Sdim GoogleStyle.Cpp11BracedListStyle = true; 253249261Sdim GoogleStyle.DerivePointerBinding = true; 254263508Sdim GoogleStyle.ExperimentalAutoDetectBinPacking = false; 255249261Sdim GoogleStyle.IndentCaseLabels = true; 256263508Sdim GoogleStyle.IndentFunctionDeclarationAfterType = true; 257263508Sdim GoogleStyle.IndentWidth = 2; 258263508Sdim GoogleStyle.TabWidth = 8; 259251662Sdim GoogleStyle.MaxEmptyLinesToKeep = 1; 260263508Sdim GoogleStyle.NamespaceIndentation = FormatStyle::NI_None; 261249261Sdim GoogleStyle.ObjCSpaceBeforeProtocolList = false; 262251662Sdim GoogleStyle.PointerBindsToType = true; 263251662Sdim GoogleStyle.SpacesBeforeTrailingComments = 2; 264251662Sdim GoogleStyle.Standard = FormatStyle::LS_Auto; 265263508Sdim GoogleStyle.UseTab = FormatStyle::UT_Never; 266263508Sdim GoogleStyle.SpacesInParentheses = false; 267263508Sdim GoogleStyle.SpaceInEmptyParentheses = false; 268263508Sdim GoogleStyle.SpacesInCStyleCastParentheses = false; 269263508Sdim GoogleStyle.SpaceAfterControlStatementKeyword = true; 270263508Sdim GoogleStyle.SpaceBeforeAssignmentOperators = true; 271263508Sdim GoogleStyle.ContinuationIndentWidth = 4; 272263508Sdim GoogleStyle.SpacesInAngles = false; 273263508Sdim 274263508Sdim setDefaultPenalties(GoogleStyle); 275263508Sdim GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200; 276263508Sdim GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1; 277263508Sdim 278249261Sdim return GoogleStyle; 279249261Sdim} 280249261Sdim 281249261SdimFormatStyle getChromiumStyle() { 282249261Sdim FormatStyle ChromiumStyle = getGoogleStyle(); 283249261Sdim ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false; 284251662Sdim ChromiumStyle.AllowShortIfStatementsOnASingleLine = false; 285263508Sdim ChromiumStyle.AllowShortLoopsOnASingleLine = false; 286249261Sdim ChromiumStyle.BinPackParameters = false; 287263508Sdim ChromiumStyle.DerivePointerBinding = false; 288249261Sdim ChromiumStyle.Standard = FormatStyle::LS_Cpp03; 289249261Sdim return ChromiumStyle; 290249261Sdim} 291249261Sdim 292251662SdimFormatStyle getMozillaStyle() { 293251662Sdim FormatStyle MozillaStyle = getLLVMStyle(); 294251662Sdim MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false; 295251662Sdim MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true; 296251662Sdim MozillaStyle.DerivePointerBinding = true; 297251662Sdim MozillaStyle.IndentCaseLabels = true; 298251662Sdim MozillaStyle.ObjCSpaceBeforeProtocolList = false; 299251662Sdim MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200; 300251662Sdim MozillaStyle.PointerBindsToType = true; 301251662Sdim return MozillaStyle; 302249261Sdim} 303249261Sdim 304263508SdimFormatStyle getWebKitStyle() { 305263508Sdim FormatStyle Style = getLLVMStyle(); 306263508Sdim Style.AccessModifierOffset = -4; 307263508Sdim Style.AlignTrailingComments = false; 308263508Sdim Style.BreakBeforeBinaryOperators = true; 309263508Sdim Style.BreakBeforeBraces = FormatStyle::BS_Stroustrup; 310263508Sdim Style.BreakConstructorInitializersBeforeComma = true; 311263508Sdim Style.ColumnLimit = 0; 312263508Sdim Style.IndentWidth = 4; 313263508Sdim Style.NamespaceIndentation = FormatStyle::NI_Inner; 314263508Sdim Style.PointerBindsToType = true; 315263508Sdim return Style; 316249261Sdim} 317249261Sdim 318263508Sdimbool getPredefinedStyle(StringRef Name, FormatStyle *Style) { 319263508Sdim if (Name.equals_lower("llvm")) 320263508Sdim *Style = getLLVMStyle(); 321263508Sdim else if (Name.equals_lower("chromium")) 322263508Sdim *Style = getChromiumStyle(); 323263508Sdim else if (Name.equals_lower("mozilla")) 324263508Sdim *Style = getMozillaStyle(); 325263508Sdim else if (Name.equals_lower("google")) 326263508Sdim *Style = getGoogleStyle(); 327263508Sdim else if (Name.equals_lower("webkit")) 328263508Sdim *Style = getWebKitStyle(); 329263508Sdim else 330263508Sdim return false; 331249261Sdim 332263508Sdim return true; 333263508Sdim} 334249261Sdim 335263508Sdimllvm::error_code parseConfiguration(StringRef Text, FormatStyle *Style) { 336263508Sdim if (Text.trim().empty()) 337263508Sdim return llvm::make_error_code(llvm::errc::invalid_argument); 338263508Sdim llvm::yaml::Input Input(Text); 339263508Sdim Input >> *Style; 340263508Sdim return Input.error(); 341263508Sdim} 342249261Sdim 343263508Sdimstd::string configurationAsText(const FormatStyle &Style) { 344263508Sdim std::string Text; 345263508Sdim llvm::raw_string_ostream Stream(Text); 346263508Sdim llvm::yaml::Output Output(Stream); 347263508Sdim // We use the same mapping method for input and output, so we need a non-const 348263508Sdim // reference here. 349263508Sdim FormatStyle NonConstStyle = Style; 350263508Sdim Output << NonConstStyle; 351263508Sdim return Stream.str(); 352263508Sdim} 353249261Sdim 354263508Sdimnamespace { 355249261Sdim 356263508Sdimclass NoColumnLimitFormatter { 357263508Sdimpublic: 358263508Sdim NoColumnLimitFormatter(ContinuationIndenter *Indenter) : Indenter(Indenter) {} 359263508Sdim 360263508Sdim /// \brief Formats the line starting at \p State, simply keeping all of the 361263508Sdim /// input's line breaking decisions. 362263508Sdim void format(unsigned FirstIndent, const AnnotatedLine *Line) { 363263508Sdim LineState State = 364263508Sdim Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false); 365263508Sdim while (State.NextToken != NULL) { 366263508Sdim bool Newline = 367263508Sdim Indenter->mustBreak(State) || 368263508Sdim (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0); 369263508Sdim Indenter->addTokenToState(State, Newline, /*DryRun=*/false); 370263508Sdim } 371249261Sdim } 372249261Sdim 373249261Sdimprivate: 374263508Sdim ContinuationIndenter *Indenter; 375263508Sdim}; 376249261Sdim 377263508Sdimclass LineJoiner { 378263508Sdimpublic: 379263508Sdim LineJoiner(const FormatStyle &Style) : Style(Style) {} 380249261Sdim 381263508Sdim /// \brief Calculates how many lines can be merged into 1 starting at \p I. 382263508Sdim unsigned 383263508Sdim tryFitMultipleLinesInOne(unsigned Indent, 384263508Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator &I, 385263508Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator E) { 386263508Sdim // We can never merge stuff if there are trailing line comments. 387263508Sdim AnnotatedLine *TheLine = *I; 388263508Sdim if (TheLine->Last->Type == TT_LineComment) 389263508Sdim return 0; 390249261Sdim 391263508Sdim if (Indent > Style.ColumnLimit) 392263508Sdim return 0; 393249261Sdim 394263508Sdim unsigned Limit = 395263508Sdim Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent; 396263508Sdim // If we already exceed the column limit, we set 'Limit' to 0. The different 397263508Sdim // tryMerge..() functions can then decide whether to still do merging. 398263508Sdim Limit = TheLine->Last->TotalLength > Limit 399263508Sdim ? 0 400263508Sdim : Limit - TheLine->Last->TotalLength; 401249261Sdim 402263508Sdim if (I + 1 == E || I[1]->Type == LT_Invalid) 403263508Sdim return 0; 404249261Sdim 405263508Sdim if (TheLine->Last->is(tok::l_brace)) { 406263508Sdim return tryMergeSimpleBlock(I, E, Limit); 407263508Sdim } else if (Style.AllowShortIfStatementsOnASingleLine && 408263508Sdim TheLine->First->is(tok::kw_if)) { 409263508Sdim return tryMergeSimpleControlStatement(I, E, Limit); 410263508Sdim } else if (Style.AllowShortLoopsOnASingleLine && 411263508Sdim TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) { 412263508Sdim return tryMergeSimpleControlStatement(I, E, Limit); 413263508Sdim } else if (TheLine->InPPDirective && (TheLine->First->HasUnescapedNewline || 414263508Sdim TheLine->First->IsFirst)) { 415263508Sdim return tryMergeSimplePPDirective(I, E, Limit); 416263508Sdim } 417263508Sdim return 0; 418263508Sdim } 419249261Sdim 420263508Sdimprivate: 421263508Sdim unsigned 422263508Sdim tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator &I, 423263508Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator E, 424263508Sdim unsigned Limit) { 425263508Sdim if (Limit == 0) 426263508Sdim return 0; 427263508Sdim if (!I[1]->InPPDirective || I[1]->First->HasUnescapedNewline) 428263508Sdim return 0; 429263508Sdim if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline) 430263508Sdim return 0; 431263508Sdim if (1 + I[1]->Last->TotalLength > Limit) 432263508Sdim return 0; 433263508Sdim return 1; 434263508Sdim } 435249261Sdim 436263508Sdim unsigned tryMergeSimpleControlStatement( 437263508Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator &I, 438263508Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) { 439263508Sdim if (Limit == 0) 440263508Sdim return 0; 441263508Sdim if (Style.BreakBeforeBraces == FormatStyle::BS_Allman && 442263508Sdim I[1]->First->is(tok::l_brace)) 443263508Sdim return 0; 444263508Sdim if (I[1]->InPPDirective != (*I)->InPPDirective || 445263508Sdim (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline)) 446263508Sdim return 0; 447263508Sdim AnnotatedLine &Line = **I; 448263508Sdim if (Line.Last->isNot(tok::r_paren)) 449263508Sdim return 0; 450263508Sdim if (1 + I[1]->Last->TotalLength > Limit) 451263508Sdim return 0; 452263508Sdim if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for, 453263508Sdim tok::kw_while) || 454263508Sdim I[1]->First->Type == TT_LineComment) 455263508Sdim return 0; 456263508Sdim // Only inline simple if's (no nested if or else). 457263508Sdim if (I + 2 != E && Line.First->is(tok::kw_if) && 458263508Sdim I[2]->First->is(tok::kw_else)) 459263508Sdim return 0; 460263508Sdim return 1; 461263508Sdim } 462249261Sdim 463263508Sdim unsigned 464263508Sdim tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator &I, 465263508Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator E, 466263508Sdim unsigned Limit) { 467263508Sdim // No merging if the brace already is on the next line. 468263508Sdim if (Style.BreakBeforeBraces != FormatStyle::BS_Attach) 469263508Sdim return 0; 470249261Sdim 471263508Sdim // First, check that the current line allows merging. This is the case if 472263508Sdim // we're not in a control flow statement and the last token is an opening 473263508Sdim // brace. 474263508Sdim AnnotatedLine &Line = **I; 475263508Sdim if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace, 476263508Sdim tok::kw_else, tok::kw_try, tok::kw_catch, 477263508Sdim tok::kw_for, 478263508Sdim // This gets rid of all ObjC @ keywords and methods. 479263508Sdim tok::at, tok::minus, tok::plus)) 480263508Sdim return 0; 481249261Sdim 482263508Sdim FormatToken *Tok = I[1]->First; 483263508Sdim if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore && 484263508Sdim (Tok->getNextNonComment() == NULL || 485263508Sdim Tok->getNextNonComment()->is(tok::semi))) { 486263508Sdim // We merge empty blocks even if the line exceeds the column limit. 487263508Sdim Tok->SpacesRequiredBefore = 0; 488263508Sdim Tok->CanBreakBefore = true; 489263508Sdim return 1; 490263508Sdim } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace)) { 491263508Sdim // Check that we still have three lines and they fit into the limit. 492263508Sdim if (I + 2 == E || I[2]->Type == LT_Invalid) 493263508Sdim return 0; 494249261Sdim 495263508Sdim if (!nextTwoLinesFitInto(I, Limit)) 496263508Sdim return 0; 497249261Sdim 498263508Sdim // Second, check that the next line does not contain any braces - if it 499263508Sdim // does, readability declines when putting it into a single line. 500263508Sdim if (I[1]->Last->Type == TT_LineComment || Tok->MustBreakBefore) 501263508Sdim return 0; 502263508Sdim do { 503263508Sdim if (Tok->isOneOf(tok::l_brace, tok::r_brace)) 504263508Sdim return 0; 505263508Sdim Tok = Tok->Next; 506263508Sdim } while (Tok != NULL); 507249261Sdim 508263508Sdim // Last, check that the third line contains a single closing brace. 509263508Sdim Tok = I[2]->First; 510263508Sdim if (Tok->getNextNonComment() != NULL || Tok->isNot(tok::r_brace) || 511263508Sdim Tok->MustBreakBefore) 512263508Sdim return 0; 513249261Sdim 514263508Sdim return 2; 515249261Sdim } 516263508Sdim return 0; 517263508Sdim } 518249261Sdim 519263508Sdim bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I, 520263508Sdim unsigned Limit) { 521263508Sdim return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit; 522263508Sdim } 523249261Sdim 524263508Sdim const FormatStyle &Style; 525263508Sdim}; 526249261Sdim 527263508Sdimclass UnwrappedLineFormatter { 528263508Sdimpublic: 529263508Sdim UnwrappedLineFormatter(SourceManager &SourceMgr, 530263508Sdim SmallVectorImpl<CharSourceRange> &Ranges, 531263508Sdim ContinuationIndenter *Indenter, 532263508Sdim WhitespaceManager *Whitespaces, 533263508Sdim const FormatStyle &Style) 534263508Sdim : SourceMgr(SourceMgr), Ranges(Ranges), Indenter(Indenter), 535263508Sdim Whitespaces(Whitespaces), Style(Style), Joiner(Style) {} 536249261Sdim 537263508Sdim unsigned format(const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun, 538263508Sdim int AdditionalIndent = 0) { 539263508Sdim assert(!Lines.empty()); 540263508Sdim unsigned Penalty = 0; 541263508Sdim std::vector<int> IndentForLevel; 542263508Sdim for (unsigned i = 0, e = Lines[0]->Level; i != e; ++i) 543263508Sdim IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent); 544263508Sdim bool PreviousLineWasTouched = false; 545263508Sdim const AnnotatedLine *PreviousLine = NULL; 546263508Sdim bool FormatPPDirective = false; 547263508Sdim for (SmallVectorImpl<AnnotatedLine *>::const_iterator I = Lines.begin(), 548263508Sdim E = Lines.end(); 549263508Sdim I != E; ++I) { 550263508Sdim const AnnotatedLine &TheLine = **I; 551263508Sdim const FormatToken *FirstTok = TheLine.First; 552263508Sdim int Offset = getIndentOffset(*FirstTok); 553249261Sdim 554263508Sdim // Check whether this line is part of a formatted preprocessor directive. 555263508Sdim if (FirstTok->HasUnescapedNewline) 556263508Sdim FormatPPDirective = false; 557263508Sdim if (!FormatPPDirective && TheLine.InPPDirective && 558263508Sdim (touchesLine(TheLine) || touchesPPDirective(I + 1, E))) 559263508Sdim FormatPPDirective = true; 560249261Sdim 561263508Sdim // Determine indent and try to merge multiple unwrapped lines. 562263508Sdim while (IndentForLevel.size() <= TheLine.Level) 563263508Sdim IndentForLevel.push_back(-1); 564263508Sdim IndentForLevel.resize(TheLine.Level + 1); 565263508Sdim unsigned Indent = getIndent(IndentForLevel, TheLine.Level); 566263508Sdim if (static_cast<int>(Indent) + Offset >= 0) 567263508Sdim Indent += Offset; 568263508Sdim unsigned MergedLines = Joiner.tryFitMultipleLinesInOne(Indent, I, E); 569263508Sdim if (!DryRun) { 570263508Sdim for (unsigned i = 0; i < MergedLines; ++i) { 571263508Sdim join(*I[i], *I[i + 1]); 572263508Sdim } 573263508Sdim } 574263508Sdim I += MergedLines; 575249261Sdim 576263508Sdim bool WasMoved = PreviousLineWasTouched && FirstTok->NewlinesBefore == 0; 577263508Sdim if (TheLine.First->is(tok::eof)) { 578263508Sdim if (PreviousLineWasTouched && !DryRun) { 579263508Sdim unsigned Newlines = std::min(FirstTok->NewlinesBefore, 1u); 580263508Sdim Whitespaces->replaceWhitespace(*TheLine.First, Newlines, 581263508Sdim /*IndentLevel=*/0, /*Spaces=*/0, 582263508Sdim /*TargetColumn=*/0); 583249261Sdim } 584263508Sdim } else if (TheLine.Type != LT_Invalid && 585263508Sdim (WasMoved || FormatPPDirective || touchesLine(TheLine))) { 586263508Sdim unsigned LevelIndent = 587263508Sdim getIndent(IndentForLevel, TheLine.Level); 588263508Sdim if (FirstTok->WhitespaceRange.isValid()) { 589263508Sdim if (!DryRun) 590263508Sdim formatFirstToken(*TheLine.First, PreviousLine, TheLine.Level, 591263508Sdim Indent, TheLine.InPPDirective); 592249261Sdim } else { 593263508Sdim Indent = LevelIndent = FirstTok->OriginalColumn; 594249261Sdim } 595263508Sdim 596263508Sdim // If everything fits on a single line, just put it there. 597263508Sdim unsigned ColumnLimit = Style.ColumnLimit; 598263508Sdim if (I + 1 != E) { 599263508Sdim AnnotatedLine *NextLine = I[1]; 600263508Sdim if (NextLine->InPPDirective && !NextLine->First->HasUnescapedNewline) 601263508Sdim ColumnLimit = getColumnLimit(TheLine.InPPDirective); 602249261Sdim } 603249261Sdim 604263508Sdim if (TheLine.Last->TotalLength + Indent <= ColumnLimit) { 605263508Sdim LineState State = Indenter->getInitialState(Indent, &TheLine, DryRun); 606263508Sdim while (State.NextToken != NULL) 607263508Sdim Indenter->addTokenToState(State, /*Newline=*/false, DryRun); 608263508Sdim } else if (Style.ColumnLimit == 0) { 609263508Sdim NoColumnLimitFormatter Formatter(Indenter); 610263508Sdim if (!DryRun) 611263508Sdim Formatter.format(Indent, &TheLine); 612263508Sdim } else { 613263508Sdim Penalty += format(TheLine, Indent, DryRun); 614249261Sdim } 615249261Sdim 616263508Sdim IndentForLevel[TheLine.Level] = LevelIndent; 617263508Sdim PreviousLineWasTouched = true; 618249261Sdim } else { 619263508Sdim // Format the first token if necessary, and notify the WhitespaceManager 620263508Sdim // about the unchanged whitespace. 621263508Sdim for (FormatToken *Tok = TheLine.First; Tok != NULL; Tok = Tok->Next) { 622263508Sdim if (Tok == TheLine.First && 623263508Sdim (Tok->NewlinesBefore > 0 || Tok->IsFirst)) { 624263508Sdim unsigned LevelIndent = Tok->OriginalColumn; 625263508Sdim if (!DryRun) { 626263508Sdim // Remove trailing whitespace of the previous line if it was 627263508Sdim // touched. 628263508Sdim if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine)) { 629263508Sdim formatFirstToken(*Tok, PreviousLine, TheLine.Level, LevelIndent, 630263508Sdim TheLine.InPPDirective); 631263508Sdim } else { 632263508Sdim Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective); 633263508Sdim } 634263508Sdim } 635251662Sdim 636263508Sdim if (static_cast<int>(LevelIndent) - Offset >= 0) 637263508Sdim LevelIndent -= Offset; 638263508Sdim if (Tok->isNot(tok::comment)) 639263508Sdim IndentForLevel[TheLine.Level] = LevelIndent; 640263508Sdim } else if (!DryRun) { 641263508Sdim Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective); 642263508Sdim } 643251662Sdim } 644263508Sdim // If we did not reformat this unwrapped line, the column at the end of 645263508Sdim // the last token is unchanged - thus, we can calculate the end of the 646263508Sdim // last token. 647263508Sdim PreviousLineWasTouched = false; 648251662Sdim } 649249261Sdim if (!DryRun) { 650263508Sdim for (FormatToken *Tok = TheLine.First; Tok != NULL; Tok = Tok->Next) { 651263508Sdim Tok->Finalized = true; 652263508Sdim } 653249261Sdim } 654263508Sdim PreviousLine = *I; 655251662Sdim } 656249261Sdim return Penalty; 657249261Sdim } 658249261Sdim 659263508Sdimprivate: 660263508Sdim /// \brief Formats an \c AnnotatedLine and returns the penalty. 661263508Sdim /// 662263508Sdim /// If \p DryRun is \c false, directly applies the changes. 663263508Sdim unsigned format(const AnnotatedLine &Line, unsigned FirstIndent, 664263508Sdim bool DryRun) { 665263508Sdim LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun); 666263508Sdim 667263508Sdim // If the ObjC method declaration does not fit on a line, we should format 668263508Sdim // it with one arg per line. 669263508Sdim if (State.Line->Type == LT_ObjCMethodDecl) 670263508Sdim State.Stack.back().BreakBeforeParameter = true; 671263508Sdim 672263508Sdim // Find best solution in solution space. 673263508Sdim return analyzeSolutionSpace(State, DryRun); 674249261Sdim } 675249261Sdim 676249261Sdim /// \brief An edge in the solution space from \c Previous->State to \c State, 677249261Sdim /// inserting a newline dependent on the \c NewLine. 678249261Sdim struct StateNode { 679249261Sdim StateNode(const LineState &State, bool NewLine, StateNode *Previous) 680249261Sdim : State(State), NewLine(NewLine), Previous(Previous) {} 681249261Sdim LineState State; 682249261Sdim bool NewLine; 683249261Sdim StateNode *Previous; 684249261Sdim }; 685249261Sdim 686249261Sdim /// \brief A pair of <penalty, count> that is used to prioritize the BFS on. 687249261Sdim /// 688249261Sdim /// In case of equal penalties, we want to prefer states that were inserted 689249261Sdim /// first. During state generation we make sure that we insert states first 690249261Sdim /// that break the line as late as possible. 691249261Sdim typedef std::pair<unsigned, unsigned> OrderedPenalty; 692249261Sdim 693249261Sdim /// \brief An item in the prioritized BFS search queue. The \c StateNode's 694249261Sdim /// \c State has the given \c OrderedPenalty. 695249261Sdim typedef std::pair<OrderedPenalty, StateNode *> QueueItem; 696249261Sdim 697249261Sdim /// \brief The BFS queue type. 698249261Sdim typedef std::priority_queue<QueueItem, std::vector<QueueItem>, 699249261Sdim std::greater<QueueItem> > QueueType; 700249261Sdim 701263508Sdim /// \brief Get the offset of the line relatively to the level. 702263508Sdim /// 703263508Sdim /// For example, 'public:' labels in classes are offset by 1 or 2 704263508Sdim /// characters to the left from their level. 705263508Sdim int getIndentOffset(const FormatToken &RootToken) { 706263508Sdim if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier()) 707263508Sdim return Style.AccessModifierOffset; 708263508Sdim return 0; 709263508Sdim } 710263508Sdim 711263508Sdim /// \brief Add a new line and the required indent before the first Token 712263508Sdim /// of the \c UnwrappedLine if there was no structural parsing error. 713263508Sdim void formatFirstToken(FormatToken &RootToken, 714263508Sdim const AnnotatedLine *PreviousLine, unsigned IndentLevel, 715263508Sdim unsigned Indent, bool InPPDirective) { 716263508Sdim unsigned Newlines = 717263508Sdim std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1); 718263508Sdim // Remove empty lines before "}" where applicable. 719263508Sdim if (RootToken.is(tok::r_brace) && 720263508Sdim (!RootToken.Next || 721263508Sdim (RootToken.Next->is(tok::semi) && !RootToken.Next->Next))) 722263508Sdim Newlines = std::min(Newlines, 1u); 723263508Sdim if (Newlines == 0 && !RootToken.IsFirst) 724263508Sdim Newlines = 1; 725263508Sdim 726263508Sdim // Insert extra new line before access specifiers. 727263508Sdim if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) && 728263508Sdim RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1) 729263508Sdim ++Newlines; 730263508Sdim 731263508Sdim // Remove empty lines after access specifiers. 732263508Sdim if (PreviousLine && PreviousLine->First->isAccessSpecifier()) 733263508Sdim Newlines = std::min(1u, Newlines); 734263508Sdim 735263508Sdim Whitespaces->replaceWhitespace( 736263508Sdim RootToken, Newlines, IndentLevel, Indent, Indent, 737263508Sdim InPPDirective && !RootToken.HasUnescapedNewline); 738263508Sdim } 739263508Sdim 740263508Sdim /// \brief Get the indent of \p Level from \p IndentForLevel. 741263508Sdim /// 742263508Sdim /// \p IndentForLevel must contain the indent for the level \c l 743263508Sdim /// at \p IndentForLevel[l], or a value < 0 if the indent for 744263508Sdim /// that level is unknown. 745263508Sdim unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) { 746263508Sdim if (IndentForLevel[Level] != -1) 747263508Sdim return IndentForLevel[Level]; 748263508Sdim if (Level == 0) 749263508Sdim return 0; 750263508Sdim return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth; 751263508Sdim } 752263508Sdim 753263508Sdim void join(AnnotatedLine &A, const AnnotatedLine &B) { 754263508Sdim assert(!A.Last->Next); 755263508Sdim assert(!B.First->Previous); 756263508Sdim A.Last->Next = B.First; 757263508Sdim B.First->Previous = A.Last; 758263508Sdim B.First->CanBreakBefore = true; 759263508Sdim unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore; 760263508Sdim for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) { 761263508Sdim Tok->TotalLength += LengthA; 762263508Sdim A.Last = Tok; 763263508Sdim } 764263508Sdim } 765263508Sdim 766263508Sdim unsigned getColumnLimit(bool InPPDirective) const { 767263508Sdim // In preprocessor directives reserve two chars for trailing " \" 768263508Sdim return Style.ColumnLimit - (InPPDirective ? 2 : 0); 769263508Sdim } 770263508Sdim 771263508Sdim bool touchesRanges(const CharSourceRange &Range) { 772263508Sdim for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(), 773263508Sdim E = Ranges.end(); 774263508Sdim I != E; ++I) { 775263508Sdim if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) && 776263508Sdim !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin())) 777263508Sdim return true; 778263508Sdim } 779263508Sdim return false; 780263508Sdim } 781263508Sdim 782263508Sdim bool touchesLine(const AnnotatedLine &TheLine) { 783263508Sdim const FormatToken *First = TheLine.First; 784263508Sdim const FormatToken *Last = TheLine.Last; 785263508Sdim CharSourceRange LineRange = CharSourceRange::getCharRange( 786263508Sdim First->WhitespaceRange.getBegin().getLocWithOffset( 787263508Sdim First->LastNewlineOffset), 788263508Sdim Last->getStartOfNonWhitespace().getLocWithOffset( 789263508Sdim Last->TokenText.size() - 1)); 790263508Sdim return touchesRanges(LineRange); 791263508Sdim } 792263508Sdim 793263508Sdim bool touchesPPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I, 794263508Sdim SmallVectorImpl<AnnotatedLine *>::const_iterator E) { 795263508Sdim for (; I != E; ++I) { 796263508Sdim if ((*I)->First->HasUnescapedNewline) 797263508Sdim return false; 798263508Sdim if (touchesLine(**I)) 799263508Sdim return true; 800263508Sdim } 801263508Sdim return false; 802263508Sdim } 803263508Sdim 804263508Sdim bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) { 805263508Sdim const FormatToken *First = TheLine.First; 806263508Sdim CharSourceRange LineRange = CharSourceRange::getCharRange( 807263508Sdim First->WhitespaceRange.getBegin(), 808263508Sdim First->WhitespaceRange.getBegin().getLocWithOffset( 809263508Sdim First->LastNewlineOffset)); 810263508Sdim return touchesRanges(LineRange); 811263508Sdim } 812263508Sdim 813249261Sdim /// \brief Analyze the entire solution space starting from \p InitialState. 814249261Sdim /// 815249261Sdim /// This implements a variant of Dijkstra's algorithm on the graph that spans 816249261Sdim /// the solution space (\c LineStates are the nodes). The algorithm tries to 817249261Sdim /// find the shortest path (the one with lowest penalty) from \p InitialState 818263508Sdim /// to a state where all tokens are placed. Returns the penalty. 819263508Sdim /// 820263508Sdim /// If \p DryRun is \c false, directly applies the changes. 821263508Sdim unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false) { 822249261Sdim std::set<LineState> Seen; 823249261Sdim 824263508Sdim // Increasing count of \c StateNode items we have created. This is used to 825263508Sdim // create a deterministic order independent of the container. 826263508Sdim unsigned Count = 0; 827263508Sdim QueueType Queue; 828263508Sdim 829249261Sdim // Insert start element into queue. 830249261Sdim StateNode *Node = 831249261Sdim new (Allocator.Allocate()) StateNode(InitialState, false, NULL); 832249261Sdim Queue.push(QueueItem(OrderedPenalty(0, Count), Node)); 833249261Sdim ++Count; 834249261Sdim 835263508Sdim unsigned Penalty = 0; 836263508Sdim 837249261Sdim // While not empty, take first element and follow edges. 838249261Sdim while (!Queue.empty()) { 839263508Sdim Penalty = Queue.top().first.first; 840249261Sdim StateNode *Node = Queue.top().second; 841249261Sdim if (Node->State.NextToken == NULL) { 842263508Sdim DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n"); 843249261Sdim break; 844249261Sdim } 845249261Sdim Queue.pop(); 846249261Sdim 847263508Sdim // Cut off the analysis of certain solutions if the analysis gets too 848263508Sdim // complex. See description of IgnoreStackForComparison. 849263508Sdim if (Count > 10000) 850263508Sdim Node->State.IgnoreStackForComparison = true; 851263508Sdim 852249261Sdim if (!Seen.insert(Node->State).second) 853249261Sdim // State already examined with lower penalty. 854249261Sdim continue; 855249261Sdim 856263508Sdim FormatDecision LastFormat = Node->State.NextToken->Decision; 857263508Sdim if (LastFormat == FD_Unformatted || LastFormat == FD_Continue) 858263508Sdim addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue); 859263508Sdim if (LastFormat == FD_Unformatted || LastFormat == FD_Break) 860263508Sdim addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue); 861249261Sdim } 862249261Sdim 863263508Sdim if (Queue.empty()) { 864249261Sdim // We were unable to find a solution, do nothing. 865249261Sdim // FIXME: Add diagnostic? 866263508Sdim DEBUG(llvm::dbgs() << "Could not find a solution.\n"); 867249261Sdim return 0; 868263508Sdim } 869249261Sdim 870249261Sdim // Reconstruct the solution. 871263508Sdim if (!DryRun) 872263508Sdim reconstructPath(InitialState, Queue.top().second); 873249261Sdim 874263508Sdim DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n"); 875263508Sdim DEBUG(llvm::dbgs() << "---\n"); 876263508Sdim 877263508Sdim return Penalty; 878249261Sdim } 879249261Sdim 880249261Sdim void reconstructPath(LineState &State, StateNode *Current) { 881263508Sdim std::deque<StateNode *> Path; 882263508Sdim // We do not need a break before the initial token. 883263508Sdim while (Current->Previous) { 884263508Sdim Path.push_front(Current); 885263508Sdim Current = Current->Previous; 886263508Sdim } 887263508Sdim for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end(); 888263508Sdim I != E; ++I) { 889263508Sdim unsigned Penalty = 0; 890263508Sdim formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty); 891263508Sdim Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false); 892263508Sdim 893263508Sdim DEBUG({ 894263508Sdim if ((*I)->NewLine) { 895263508Sdim llvm::dbgs() << "Penalty for placing " 896263508Sdim << (*I)->Previous->State.NextToken->Tok.getName() << ": " 897263508Sdim << Penalty << "\n"; 898263508Sdim } 899263508Sdim }); 900263508Sdim } 901249261Sdim } 902249261Sdim 903249261Sdim /// \brief Add the following state to the analysis queue \c Queue. 904249261Sdim /// 905249261Sdim /// Assume the current state is \p PreviousNode and has been reached with a 906249261Sdim /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true. 907249261Sdim void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode, 908263508Sdim bool NewLine, unsigned *Count, QueueType *Queue) { 909263508Sdim if (NewLine && !Indenter->canBreak(PreviousNode->State)) 910249261Sdim return; 911263508Sdim if (!NewLine && Indenter->mustBreak(PreviousNode->State)) 912249261Sdim return; 913249261Sdim 914249261Sdim StateNode *Node = new (Allocator.Allocate()) 915249261Sdim StateNode(PreviousNode->State, NewLine, PreviousNode); 916263508Sdim if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty)) 917263508Sdim return; 918249261Sdim 919263508Sdim Penalty += Indenter->addTokenToState(Node->State, NewLine, true); 920249261Sdim 921263508Sdim Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node)); 922263508Sdim ++(*Count); 923249261Sdim } 924249261Sdim 925263508Sdim /// \brief If the \p State's next token is an r_brace closing a nested block, 926263508Sdim /// format the nested block before it. 927263508Sdim /// 928263508Sdim /// Returns \c true if all children could be placed successfully and adapts 929263508Sdim /// \p Penalty as well as \p State. If \p DryRun is false, also directly 930263508Sdim /// creates changes using \c Whitespaces. 931263508Sdim /// 932263508Sdim /// The crucial idea here is that children always get formatted upon 933263508Sdim /// encountering the closing brace right after the nested block. Now, if we 934263508Sdim /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is 935263508Sdim /// \c false), the entire block has to be kept on the same line (which is only 936263508Sdim /// possible if it fits on the line, only contains a single statement, etc. 937263508Sdim /// 938263508Sdim /// If \p NewLine is true, we format the nested block on separate lines, i.e. 939263508Sdim /// break after the "{", format all lines with correct indentation and the put 940263508Sdim /// the closing "}" on yet another new line. 941263508Sdim /// 942263508Sdim /// This enables us to keep the simple structure of the 943263508Sdim /// \c UnwrappedLineFormatter, where we only have two options for each token: 944263508Sdim /// break or don't break. 945263508Sdim bool formatChildren(LineState &State, bool NewLine, bool DryRun, 946263508Sdim unsigned &Penalty) { 947263508Sdim FormatToken &Previous = *State.NextToken->Previous; 948263508Sdim const FormatToken *LBrace = State.NextToken->getPreviousNonComment(); 949263508Sdim if (!LBrace || LBrace->isNot(tok::l_brace) || 950263508Sdim LBrace->BlockKind != BK_Block || Previous.Children.size() == 0) 951263508Sdim // The previous token does not open a block. Nothing to do. We don't 952263508Sdim // assert so that we can simply call this function for all tokens. 953249261Sdim return true; 954263508Sdim 955263508Sdim if (NewLine) { 956263508Sdim int AdditionalIndent = State.Stack.back().Indent - 957263508Sdim Previous.Children[0]->Level * Style.IndentWidth; 958263508Sdim Penalty += format(Previous.Children, DryRun, AdditionalIndent); 959249261Sdim return true; 960263508Sdim } 961249261Sdim 962263508Sdim // Cannot merge multiple statements into a single line. 963263508Sdim if (Previous.Children.size() > 1) 964263508Sdim return false; 965263508Sdim 966263508Sdim // We can't put the closing "}" on a line with a trailing comment. 967263508Sdim if (Previous.Children[0]->Last->isTrailingComment()) 968263508Sdim return false; 969263508Sdim 970263508Sdim if (!DryRun) { 971263508Sdim Whitespaces->replaceWhitespace( 972263508Sdim *Previous.Children[0]->First, 973263508Sdim /*Newlines=*/0, /*IndentLevel=*/0, /*Spaces=*/1, 974263508Sdim /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective); 975263508Sdim } 976263508Sdim Penalty += format(*Previous.Children[0], State.Column + 1, DryRun); 977263508Sdim 978263508Sdim State.Column += 1 + Previous.Children[0]->Last->TotalLength; 979263508Sdim return true; 980249261Sdim } 981249261Sdim 982263508Sdim SourceManager &SourceMgr; 983263508Sdim SmallVectorImpl<CharSourceRange> &Ranges; 984263508Sdim ContinuationIndenter *Indenter; 985263508Sdim WhitespaceManager *Whitespaces; 986249261Sdim FormatStyle Style; 987263508Sdim LineJoiner Joiner; 988249261Sdim 989249261Sdim llvm::SpecificBumpPtrAllocator<StateNode> Allocator; 990249261Sdim}; 991249261Sdim 992263508Sdimclass FormatTokenLexer { 993249261Sdimpublic: 994263508Sdim FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr, FormatStyle &Style, 995263508Sdim encoding::Encoding Encoding) 996263508Sdim : FormatTok(NULL), IsFirstToken(true), GreaterStashed(false), Column(0), 997263508Sdim TrailingWhitespace(0), Lex(Lex), SourceMgr(SourceMgr), Style(Style), 998263508Sdim IdentTable(getFormattingLangOpts()), Encoding(Encoding) { 999249261Sdim Lex.SetKeepWhitespaceMode(true); 1000249261Sdim } 1001249261Sdim 1002263508Sdim ArrayRef<FormatToken *> lex() { 1003263508Sdim assert(Tokens.empty()); 1004263508Sdim do { 1005263508Sdim Tokens.push_back(getNextToken()); 1006263508Sdim maybeJoinPreviousTokens(); 1007263508Sdim } while (Tokens.back()->Tok.isNot(tok::eof)); 1008263508Sdim return Tokens; 1009263508Sdim } 1010263508Sdim 1011263508Sdim IdentifierTable &getIdentTable() { return IdentTable; } 1012263508Sdim 1013263508Sdimprivate: 1014263508Sdim void maybeJoinPreviousTokens() { 1015263508Sdim if (Tokens.size() < 4) 1016263508Sdim return; 1017263508Sdim FormatToken *Last = Tokens.back(); 1018263508Sdim if (!Last->is(tok::r_paren)) 1019263508Sdim return; 1020263508Sdim 1021263508Sdim FormatToken *String = Tokens[Tokens.size() - 2]; 1022263508Sdim if (!String->is(tok::string_literal) || String->IsMultiline) 1023263508Sdim return; 1024263508Sdim 1025263508Sdim if (!Tokens[Tokens.size() - 3]->is(tok::l_paren)) 1026263508Sdim return; 1027263508Sdim 1028263508Sdim FormatToken *Macro = Tokens[Tokens.size() - 4]; 1029263508Sdim if (Macro->TokenText != "_T") 1030263508Sdim return; 1031263508Sdim 1032263508Sdim const char *Start = Macro->TokenText.data(); 1033263508Sdim const char *End = Last->TokenText.data() + Last->TokenText.size(); 1034263508Sdim String->TokenText = StringRef(Start, End - Start); 1035263508Sdim String->IsFirst = Macro->IsFirst; 1036263508Sdim String->LastNewlineOffset = Macro->LastNewlineOffset; 1037263508Sdim String->WhitespaceRange = Macro->WhitespaceRange; 1038263508Sdim String->OriginalColumn = Macro->OriginalColumn; 1039263508Sdim String->ColumnWidth = encoding::columnWidthWithTabs( 1040263508Sdim String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding); 1041263508Sdim 1042263508Sdim Tokens.pop_back(); 1043263508Sdim Tokens.pop_back(); 1044263508Sdim Tokens.pop_back(); 1045263508Sdim Tokens.back() = String; 1046263508Sdim } 1047263508Sdim 1048263508Sdim FormatToken *getNextToken() { 1049249261Sdim if (GreaterStashed) { 1050263508Sdim // Create a synthesized second '>' token. 1051263508Sdim // FIXME: Increment Column and set OriginalColumn. 1052263508Sdim Token Greater = FormatTok->Tok; 1053263508Sdim FormatTok = new (Allocator.Allocate()) FormatToken; 1054263508Sdim FormatTok->Tok = Greater; 1055263508Sdim SourceLocation GreaterLocation = 1056263508Sdim FormatTok->Tok.getLocation().getLocWithOffset(1); 1057263508Sdim FormatTok->WhitespaceRange = 1058263508Sdim SourceRange(GreaterLocation, GreaterLocation); 1059263508Sdim FormatTok->TokenText = ">"; 1060263508Sdim FormatTok->ColumnWidth = 1; 1061249261Sdim GreaterStashed = false; 1062249261Sdim return FormatTok; 1063249261Sdim } 1064249261Sdim 1065263508Sdim FormatTok = new (Allocator.Allocate()) FormatToken; 1066263508Sdim readRawToken(*FormatTok); 1067263508Sdim SourceLocation WhitespaceStart = 1068263508Sdim FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace); 1069263508Sdim FormatTok->IsFirst = IsFirstToken; 1070263508Sdim IsFirstToken = false; 1071249261Sdim 1072249261Sdim // Consume and record whitespace until we find a significant token. 1073263508Sdim unsigned WhitespaceLength = TrailingWhitespace; 1074263508Sdim while (FormatTok->Tok.is(tok::unknown)) { 1075263508Sdim for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) { 1076263508Sdim switch (FormatTok->TokenText[i]) { 1077263508Sdim case '\n': 1078263508Sdim ++FormatTok->NewlinesBefore; 1079263508Sdim // FIXME: This is technically incorrect, as it could also 1080263508Sdim // be a literal backslash at the end of the line. 1081263508Sdim if (i == 0 || (FormatTok->TokenText[i - 1] != '\\' && 1082263508Sdim (FormatTok->TokenText[i - 1] != '\r' || i == 1 || 1083263508Sdim FormatTok->TokenText[i - 2] != '\\'))) 1084263508Sdim FormatTok->HasUnescapedNewline = true; 1085263508Sdim FormatTok->LastNewlineOffset = WhitespaceLength + i + 1; 1086263508Sdim Column = 0; 1087263508Sdim break; 1088263508Sdim case '\r': 1089263508Sdim case '\f': 1090263508Sdim case '\v': 1091263508Sdim Column = 0; 1092263508Sdim break; 1093263508Sdim case ' ': 1094263508Sdim ++Column; 1095263508Sdim break; 1096263508Sdim case '\t': 1097263508Sdim Column += Style.TabWidth - Column % Style.TabWidth; 1098263508Sdim break; 1099263508Sdim case '\\': 1100263508Sdim ++Column; 1101263508Sdim if (i + 1 == e || (FormatTok->TokenText[i + 1] != '\r' && 1102263508Sdim FormatTok->TokenText[i + 1] != '\n')) 1103263508Sdim FormatTok->Type = TT_ImplicitStringLiteral; 1104263508Sdim break; 1105263508Sdim default: 1106263508Sdim FormatTok->Type = TT_ImplicitStringLiteral; 1107263508Sdim ++Column; 1108263508Sdim break; 1109263508Sdim } 1110263508Sdim } 1111249261Sdim 1112263508Sdim if (FormatTok->Type == TT_ImplicitStringLiteral) 1113263508Sdim break; 1114263508Sdim WhitespaceLength += FormatTok->Tok.getLength(); 1115249261Sdim 1116263508Sdim readRawToken(*FormatTok); 1117251662Sdim } 1118251662Sdim 1119249261Sdim // In case the token starts with escaped newlines, we want to 1120249261Sdim // take them into account as whitespace - this pattern is quite frequent 1121249261Sdim // in macro definitions. 1122249261Sdim // FIXME: Add a more explicit test. 1123263508Sdim while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' && 1124263508Sdim FormatTok->TokenText[1] == '\n') { 1125263508Sdim // FIXME: ++FormatTok->NewlinesBefore is missing... 1126263508Sdim WhitespaceLength += 2; 1127263508Sdim Column = 0; 1128263508Sdim FormatTok->TokenText = FormatTok->TokenText.substr(2); 1129249261Sdim } 1130249261Sdim 1131263508Sdim FormatTok->WhitespaceRange = SourceRange( 1132263508Sdim WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength)); 1133249261Sdim 1134263508Sdim FormatTok->OriginalColumn = Column; 1135263508Sdim 1136263508Sdim TrailingWhitespace = 0; 1137263508Sdim if (FormatTok->Tok.is(tok::comment)) { 1138263508Sdim // FIXME: Add the trimmed whitespace to Column. 1139263508Sdim StringRef UntrimmedText = FormatTok->TokenText; 1140263508Sdim FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f"); 1141263508Sdim TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size(); 1142263508Sdim } else if (FormatTok->Tok.is(tok::raw_identifier)) { 1143263508Sdim IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText); 1144263508Sdim FormatTok->Tok.setIdentifierInfo(&Info); 1145263508Sdim FormatTok->Tok.setKind(Info.getTokenID()); 1146263508Sdim } else if (FormatTok->Tok.is(tok::greatergreater)) { 1147263508Sdim FormatTok->Tok.setKind(tok::greater); 1148263508Sdim FormatTok->TokenText = FormatTok->TokenText.substr(0, 1); 1149249261Sdim GreaterStashed = true; 1150249261Sdim } 1151249261Sdim 1152263508Sdim // Now FormatTok is the next non-whitespace token. 1153263508Sdim 1154263508Sdim StringRef Text = FormatTok->TokenText; 1155263508Sdim size_t FirstNewlinePos = Text.find('\n'); 1156263508Sdim if (FirstNewlinePos == StringRef::npos) { 1157263508Sdim // FIXME: ColumnWidth actually depends on the start column, we need to 1158263508Sdim // take this into account when the token is moved. 1159263508Sdim FormatTok->ColumnWidth = 1160263508Sdim encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding); 1161263508Sdim Column += FormatTok->ColumnWidth; 1162263508Sdim } else { 1163263508Sdim FormatTok->IsMultiline = true; 1164263508Sdim // FIXME: ColumnWidth actually depends on the start column, we need to 1165263508Sdim // take this into account when the token is moved. 1166263508Sdim FormatTok->ColumnWidth = encoding::columnWidthWithTabs( 1167263508Sdim Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding); 1168263508Sdim 1169263508Sdim // The last line of the token always starts in column 0. 1170263508Sdim // Thus, the length can be precomputed even in the presence of tabs. 1171263508Sdim FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs( 1172263508Sdim Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth, 1173263508Sdim Encoding); 1174263508Sdim Column = FormatTok->LastLineColumnWidth; 1175263508Sdim } 1176263508Sdim 1177249261Sdim return FormatTok; 1178249261Sdim } 1179249261Sdim 1180263508Sdim FormatToken *FormatTok; 1181263508Sdim bool IsFirstToken; 1182249261Sdim bool GreaterStashed; 1183263508Sdim unsigned Column; 1184263508Sdim unsigned TrailingWhitespace; 1185249261Sdim Lexer &Lex; 1186249261Sdim SourceManager &SourceMgr; 1187263508Sdim FormatStyle &Style; 1188249261Sdim IdentifierTable IdentTable; 1189263508Sdim encoding::Encoding Encoding; 1190263508Sdim llvm::SpecificBumpPtrAllocator<FormatToken> Allocator; 1191263508Sdim SmallVector<FormatToken *, 16> Tokens; 1192249261Sdim 1193263508Sdim void readRawToken(FormatToken &Tok) { 1194263508Sdim Lex.LexFromRawLexer(Tok.Tok); 1195263508Sdim Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()), 1196263508Sdim Tok.Tok.getLength()); 1197263508Sdim // For formatting, treat unterminated string literals like normal string 1198263508Sdim // literals. 1199263508Sdim if (Tok.is(tok::unknown) && !Tok.TokenText.empty() && 1200263508Sdim Tok.TokenText[0] == '"') { 1201263508Sdim Tok.Tok.setKind(tok::string_literal); 1202263508Sdim Tok.IsUnterminatedLiteral = true; 1203263508Sdim } 1204249261Sdim } 1205249261Sdim}; 1206249261Sdim 1207249261Sdimclass Formatter : public UnwrappedLineConsumer { 1208249261Sdimpublic: 1209263508Sdim Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr, 1210249261Sdim const std::vector<CharSourceRange> &Ranges) 1211263508Sdim : Style(Style), Lex(Lex), SourceMgr(SourceMgr), 1212263508Sdim Whitespaces(SourceMgr, Style, inputUsesCRLF(Lex.getBuffer())), 1213263508Sdim Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1), 1214263508Sdim Encoding(encoding::detectEncoding(Lex.getBuffer())) { 1215263508Sdim DEBUG(llvm::dbgs() << "File encoding: " 1216263508Sdim << (Encoding == encoding::Encoding_UTF8 ? "UTF8" 1217263508Sdim : "unknown") 1218263508Sdim << "\n"); 1219263508Sdim } 1220249261Sdim 1221263508Sdim tooling::Replacements format() { 1222263508Sdim tooling::Replacements Result; 1223263508Sdim FormatTokenLexer Tokens(Lex, SourceMgr, Style, Encoding); 1224249261Sdim 1225263508Sdim UnwrappedLineParser Parser(Style, Tokens.lex(), *this); 1226251662Sdim bool StructuralError = Parser.parse(); 1227263508Sdim assert(UnwrappedLines.rbegin()->empty()); 1228263508Sdim for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE; 1229263508Sdim ++Run) { 1230263508Sdim DEBUG(llvm::dbgs() << "Run " << Run << "...\n"); 1231263508Sdim SmallVector<AnnotatedLine *, 16> AnnotatedLines; 1232263508Sdim for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) { 1233263508Sdim AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i])); 1234263508Sdim } 1235263508Sdim tooling::Replacements RunResult = 1236263508Sdim format(AnnotatedLines, StructuralError, Tokens); 1237263508Sdim DEBUG({ 1238263508Sdim llvm::dbgs() << "Replacements for run " << Run << ":\n"; 1239263508Sdim for (tooling::Replacements::iterator I = RunResult.begin(), 1240263508Sdim E = RunResult.end(); 1241263508Sdim I != E; ++I) { 1242263508Sdim llvm::dbgs() << I->toString() << "\n"; 1243263508Sdim } 1244263508Sdim }); 1245263508Sdim for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) { 1246263508Sdim delete AnnotatedLines[i]; 1247263508Sdim } 1248263508Sdim Result.insert(RunResult.begin(), RunResult.end()); 1249263508Sdim Whitespaces.reset(); 1250263508Sdim } 1251263508Sdim return Result; 1252263508Sdim } 1253263508Sdim 1254263508Sdim tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines, 1255263508Sdim bool StructuralError, FormatTokenLexer &Tokens) { 1256263508Sdim TokenAnnotator Annotator(Style, Tokens.getIdentTable().get("in")); 1257249261Sdim for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) { 1258263508Sdim Annotator.annotate(*AnnotatedLines[i]); 1259249261Sdim } 1260263508Sdim deriveLocalStyle(AnnotatedLines); 1261249261Sdim for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) { 1262263508Sdim Annotator.calculateFormattingInformation(*AnnotatedLines[i]); 1263251662Sdim } 1264249261Sdim 1265263508Sdim Annotator.setCommentLineLevels(AnnotatedLines); 1266263508Sdim ContinuationIndenter Indenter(Style, SourceMgr, Whitespaces, Encoding, 1267263508Sdim BinPackInconclusiveFunctions); 1268263508Sdim UnwrappedLineFormatter Formatter(SourceMgr, Ranges, &Indenter, &Whitespaces, 1269263508Sdim Style); 1270263508Sdim Formatter.format(AnnotatedLines, /*DryRun=*/false); 1271249261Sdim return Whitespaces.generateReplacements(); 1272249261Sdim } 1273249261Sdim 1274249261Sdimprivate: 1275263508Sdim static bool inputUsesCRLF(StringRef Text) { 1276263508Sdim return Text.count('\r') * 2 > Text.count('\n'); 1277263508Sdim } 1278263508Sdim 1279263508Sdim void 1280263508Sdim deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) { 1281249261Sdim unsigned CountBoundToVariable = 0; 1282249261Sdim unsigned CountBoundToType = 0; 1283249261Sdim bool HasCpp03IncompatibleFormat = false; 1284263508Sdim bool HasBinPackedFunction = false; 1285263508Sdim bool HasOnePerLineFunction = false; 1286249261Sdim for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) { 1287263508Sdim if (!AnnotatedLines[i]->First->Next) 1288249261Sdim continue; 1289263508Sdim FormatToken *Tok = AnnotatedLines[i]->First->Next; 1290263508Sdim while (Tok->Next) { 1291249261Sdim if (Tok->Type == TT_PointerOrReference) { 1292263508Sdim bool SpacesBefore = 1293263508Sdim Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd(); 1294263508Sdim bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() != 1295263508Sdim Tok->Next->WhitespaceRange.getEnd(); 1296249261Sdim if (SpacesBefore && !SpacesAfter) 1297249261Sdim ++CountBoundToVariable; 1298249261Sdim else if (!SpacesBefore && SpacesAfter) 1299249261Sdim ++CountBoundToType; 1300249261Sdim } 1301249261Sdim 1302263508Sdim if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) { 1303263508Sdim if (Tok->is(tok::coloncolon) && 1304263508Sdim Tok->Previous->Type == TT_TemplateOpener) 1305263508Sdim HasCpp03IncompatibleFormat = true; 1306263508Sdim if (Tok->Type == TT_TemplateCloser && 1307263508Sdim Tok->Previous->Type == TT_TemplateCloser) 1308263508Sdim HasCpp03IncompatibleFormat = true; 1309263508Sdim } 1310263508Sdim 1311263508Sdim if (Tok->PackingKind == PPK_BinPacked) 1312263508Sdim HasBinPackedFunction = true; 1313263508Sdim if (Tok->PackingKind == PPK_OnePerLine) 1314263508Sdim HasOnePerLineFunction = true; 1315263508Sdim 1316263508Sdim Tok = Tok->Next; 1317249261Sdim } 1318249261Sdim } 1319249261Sdim if (Style.DerivePointerBinding) { 1320249261Sdim if (CountBoundToType > CountBoundToVariable) 1321249261Sdim Style.PointerBindsToType = true; 1322249261Sdim else if (CountBoundToType < CountBoundToVariable) 1323249261Sdim Style.PointerBindsToType = false; 1324249261Sdim } 1325249261Sdim if (Style.Standard == FormatStyle::LS_Auto) { 1326249261Sdim Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11 1327249261Sdim : FormatStyle::LS_Cpp03; 1328249261Sdim } 1329263508Sdim BinPackInconclusiveFunctions = 1330263508Sdim HasBinPackedFunction || !HasOnePerLineFunction; 1331249261Sdim } 1332249261Sdim 1333263508Sdim virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) { 1334263508Sdim assert(!UnwrappedLines.empty()); 1335263508Sdim UnwrappedLines.back().push_back(TheLine); 1336249261Sdim } 1337249261Sdim 1338263508Sdim virtual void finishRun() { 1339263508Sdim UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>()); 1340249261Sdim } 1341249261Sdim 1342263508Sdim FormatStyle Style; 1343263508Sdim Lexer &Lex; 1344263508Sdim SourceManager &SourceMgr; 1345263508Sdim WhitespaceManager Whitespaces; 1346263508Sdim SmallVector<CharSourceRange, 8> Ranges; 1347263508Sdim SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines; 1348249261Sdim 1349263508Sdim encoding::Encoding Encoding; 1350263508Sdim bool BinPackInconclusiveFunctions; 1351263508Sdim}; 1352249261Sdim 1353263508Sdim} // end anonymous namespace 1354249261Sdim 1355263508Sdimtooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex, 1356263508Sdim SourceManager &SourceMgr, 1357263508Sdim std::vector<CharSourceRange> Ranges) { 1358263508Sdim Formatter formatter(Style, Lex, SourceMgr, Ranges); 1359263508Sdim return formatter.format(); 1360263508Sdim} 1361249261Sdim 1362263508Sdimtooling::Replacements reformat(const FormatStyle &Style, StringRef Code, 1363263508Sdim std::vector<tooling::Range> Ranges, 1364263508Sdim StringRef FileName) { 1365263508Sdim FileManager Files((FileSystemOptions())); 1366263508Sdim DiagnosticsEngine Diagnostics( 1367263508Sdim IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs), 1368263508Sdim new DiagnosticOptions); 1369263508Sdim SourceManager SourceMgr(Diagnostics, Files); 1370263508Sdim llvm::MemoryBuffer *Buf = llvm::MemoryBuffer::getMemBuffer(Code, FileName); 1371263508Sdim const clang::FileEntry *Entry = 1372263508Sdim Files.getVirtualFile(FileName, Buf->getBufferSize(), 0); 1373263508Sdim SourceMgr.overrideFileContents(Entry, Buf); 1374263508Sdim FileID ID = 1375263508Sdim SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User); 1376263508Sdim Lexer Lex(ID, SourceMgr.getBuffer(ID), SourceMgr, 1377263508Sdim getFormattingLangOpts(Style.Standard)); 1378263508Sdim SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID); 1379263508Sdim std::vector<CharSourceRange> CharRanges; 1380263508Sdim for (unsigned i = 0, e = Ranges.size(); i != e; ++i) { 1381263508Sdim SourceLocation Start = StartOfFile.getLocWithOffset(Ranges[i].getOffset()); 1382263508Sdim SourceLocation End = Start.getLocWithOffset(Ranges[i].getLength()); 1383263508Sdim CharRanges.push_back(CharSourceRange::getCharRange(Start, End)); 1384249261Sdim } 1385263508Sdim return reformat(Style, Lex, SourceMgr, CharRanges); 1386263508Sdim} 1387249261Sdim 1388263508SdimLangOptions getFormattingLangOpts(FormatStyle::LanguageStandard Standard) { 1389263508Sdim LangOptions LangOpts; 1390263508Sdim LangOpts.CPlusPlus = 1; 1391263508Sdim LangOpts.CPlusPlus11 = Standard == FormatStyle::LS_Cpp03 ? 0 : 1; 1392263508Sdim LangOpts.LineComment = 1; 1393263508Sdim LangOpts.Bool = 1; 1394263508Sdim LangOpts.ObjC1 = 1; 1395263508Sdim LangOpts.ObjC2 = 1; 1396263508Sdim return LangOpts; 1397263508Sdim} 1398249261Sdim 1399263508Sdimconst char *StyleOptionHelpDescription = 1400263508Sdim "Coding style, currently supports:\n" 1401263508Sdim " LLVM, Google, Chromium, Mozilla, WebKit.\n" 1402263508Sdim "Use -style=file to load style configuration from\n" 1403263508Sdim ".clang-format file located in one of the parent\n" 1404263508Sdim "directories of the source file (or current\n" 1405263508Sdim "directory for stdin).\n" 1406263508Sdim "Use -style=\"{key: value, ...}\" to set specific\n" 1407263508Sdim "parameters, e.g.:\n" 1408263508Sdim " -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\""; 1409249261Sdim 1410263508SdimFormatStyle getStyle(StringRef StyleName, StringRef FileName) { 1411263508Sdim // Fallback style in case the rest of this function can't determine a style. 1412263508Sdim StringRef FallbackStyle = "LLVM"; 1413263508Sdim FormatStyle Style; 1414263508Sdim getPredefinedStyle(FallbackStyle, &Style); 1415249261Sdim 1416263508Sdim if (StyleName.startswith("{")) { 1417263508Sdim // Parse YAML/JSON style from the command line. 1418263508Sdim if (llvm::error_code ec = parseConfiguration(StyleName, &Style)) { 1419263508Sdim llvm::errs() << "Error parsing -style: " << ec.message() << ", using " 1420263508Sdim << FallbackStyle << " style\n"; 1421249261Sdim } 1422263508Sdim return Style; 1423249261Sdim } 1424249261Sdim 1425263508Sdim if (!StyleName.equals_lower("file")) { 1426263508Sdim if (!getPredefinedStyle(StyleName, &Style)) 1427263508Sdim llvm::errs() << "Invalid value for -style, using " << FallbackStyle 1428263508Sdim << " style\n"; 1429263508Sdim return Style; 1430249261Sdim } 1431249261Sdim 1432263508Sdim SmallString<128> Path(FileName); 1433263508Sdim llvm::sys::fs::make_absolute(Path); 1434263508Sdim for (StringRef Directory = Path; !Directory.empty(); 1435263508Sdim Directory = llvm::sys::path::parent_path(Directory)) { 1436263508Sdim if (!llvm::sys::fs::is_directory(Directory)) 1437263508Sdim continue; 1438263508Sdim SmallString<128> ConfigFile(Directory); 1439249261Sdim 1440263508Sdim llvm::sys::path::append(ConfigFile, ".clang-format"); 1441263508Sdim DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n"); 1442263508Sdim bool IsFile = false; 1443263508Sdim // Ignore errors from is_regular_file: we only need to know if we can read 1444263508Sdim // the file or not. 1445263508Sdim llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile); 1446263508Sdim 1447263508Sdim if (!IsFile) { 1448263508Sdim // Try _clang-format too, since dotfiles are not commonly used on Windows. 1449263508Sdim ConfigFile = Directory; 1450263508Sdim llvm::sys::path::append(ConfigFile, "_clang-format"); 1451263508Sdim DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n"); 1452263508Sdim llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile); 1453249261Sdim } 1454249261Sdim 1455263508Sdim if (IsFile) { 1456263508Sdim OwningPtr<llvm::MemoryBuffer> Text; 1457263508Sdim if (llvm::error_code ec = 1458263508Sdim llvm::MemoryBuffer::getFile(ConfigFile.c_str(), Text)) { 1459263508Sdim llvm::errs() << ec.message() << "\n"; 1460263508Sdim continue; 1461263508Sdim } 1462263508Sdim if (llvm::error_code ec = parseConfiguration(Text->getBuffer(), &Style)) { 1463263508Sdim llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message() 1464263508Sdim << "\n"; 1465263508Sdim continue; 1466263508Sdim } 1467263508Sdim DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n"); 1468263508Sdim return Style; 1469249261Sdim } 1470249261Sdim } 1471263508Sdim llvm::errs() << "Can't find usable .clang-format, using " << FallbackStyle 1472263508Sdim << " style\n"; 1473263508Sdim return Style; 1474249261Sdim} 1475249261Sdim 1476249261Sdim} // namespace format 1477249261Sdim} // namespace clang 1478