contrib/llvm/tools/clang/lib/Format/Format.cpp

   1 //===--- Format.cpp - Format C++ code -------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// \brief This file implements functions declared in Format.h. This will be
  12 /// split into separate files as we go.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "format-formatter"
  17
  18 #include "ContinuationIndenter.h"
  19 #include "TokenAnnotator.h"
  20 #include "UnwrappedLineParser.h"
  21 #include "WhitespaceManager.h"
  22 #include "clang/Basic/Diagnostic.h"
  23 #include "clang/Basic/SourceManager.h"
  24 #include "clang/Format/Format.h"
  25 #include "clang/Lex/Lexer.h"
  26 #include "llvm/ADT/STLExtras.h"
  27 #include "llvm/Support/Allocator.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/YAMLTraits.h"
  30 #include "llvm/Support/Path.h"
  31 #include <queue>
  32 #include <string>
  33
  34 namespace llvm {
  35 namespace yaml {
  36 template <>
  37 struct ScalarEnumerationTraits<clang::format::FormatStyle::LanguageStandard> {
  38   static void enumeration(IO &IO,
  39                           clang::format::FormatStyle::LanguageStandard &Value) {
  40     IO.enumCase(Value, "Cpp03", clang::format::FormatStyle::LS_Cpp03);
  41     IO.enumCase(Value, "C++03", clang::format::FormatStyle::LS_Cpp03);
  42     IO.enumCase(Value, "Cpp11", clang::format::FormatStyle::LS_Cpp11);
  43     IO.enumCase(Value, "C++11", clang::format::FormatStyle::LS_Cpp11);
  44     IO.enumCase(Value, "Auto", clang::format::FormatStyle::LS_Auto);
  45   }
  46 };
  47
  48 template <>
  49 struct ScalarEnumerationTraits<clang::format::FormatStyle::UseTabStyle> {
  50   static void enumeration(IO &IO,
  51                           clang::format::FormatStyle::UseTabStyle &Value) {
  52     IO.enumCase(Value, "Never", clang::format::FormatStyle::UT_Never);
  53     IO.enumCase(Value, "false", clang::format::FormatStyle::UT_Never);
  54     IO.enumCase(Value, "Always", clang::format::FormatStyle::UT_Always);
  55     IO.enumCase(Value, "true", clang::format::FormatStyle::UT_Always);
  56     IO.enumCase(Value, "ForIndentation",
  57                 clang::format::FormatStyle::UT_ForIndentation);
  58   }
  59 };
  60
  61 template <>
  62 struct ScalarEnumerationTraits<clang::format::FormatStyle::BraceBreakingStyle> {
  63   static void
  64   enumeration(IO &IO, clang::format::FormatStyle::BraceBreakingStyle &Value) {
  65     IO.enumCase(Value, "Attach", clang::format::FormatStyle::BS_Attach);
  66     IO.enumCase(Value, "Linux", clang::format::FormatStyle::BS_Linux);
  67     IO.enumCase(Value, "Stroustrup", clang::format::FormatStyle::BS_Stroustrup);
  68     IO.enumCase(Value, "Allman", clang::format::FormatStyle::BS_Allman);
  69   }
  70 };
  71
  72 template <>
  73 struct ScalarEnumerationTraits<
  74     clang::format::FormatStyle::NamespaceIndentationKind> {
  75   static void
  76   enumeration(IO &IO,
  77               clang::format::FormatStyle::NamespaceIndentationKind &Value) {
  78     IO.enumCase(Value, "None", clang::format::FormatStyle::NI_None);
  79     IO.enumCase(Value, "Inner", clang::format::FormatStyle::NI_Inner);
  80     IO.enumCase(Value, "All", clang::format::FormatStyle::NI_All);
  81   }
  82 };
  83
  84 template <> struct MappingTraits<clang::format::FormatStyle> {
  85   static void mapping(llvm::yaml::IO &IO, clang::format::FormatStyle &Style) {
  86     if (IO.outputting()) {
  87       StringRef StylesArray[] = { "LLVM",    "Google", "Chromium",
  88                                   "Mozilla", "WebKit" };
  89       ArrayRef<StringRef> Styles(StylesArray);
  90       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
  91         StringRef StyleName(Styles[i]);
  92         clang::format::FormatStyle PredefinedStyle;
  93         if (clang::format::getPredefinedStyle(StyleName, &PredefinedStyle) &&
  94             Style == PredefinedStyle) {
  95           IO.mapOptional("# BasedOnStyle", StyleName);
  96           break;
  97         }
  98       }
  99     } else {
 100       StringRef BasedOnStyle;
 101       IO.mapOptional("BasedOnStyle", BasedOnStyle);
 102       if (!BasedOnStyle.empty())
 103         if (!clang::format::getPredefinedStyle(BasedOnStyle, &Style)) {
 104           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
 105           return;
 106         }
 107     }
 108
 109     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
 110     IO.mapOptional("ConstructorInitializerIndentWidth",
 111                    Style.ConstructorInitializerIndentWidth);
 112     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
 113     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
 114     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
 115                    Style.AllowAllParametersOfDeclarationOnNextLine);
 116     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
 117                    Style.AllowShortIfStatementsOnASingleLine);
 118     IO.mapOptional("AllowShortLoopsOnASingleLine",
 119                    Style.AllowShortLoopsOnASingleLine);
 120     IO.mapOptional("AlwaysBreakTemplateDeclarations",
 121                    Style.AlwaysBreakTemplateDeclarations);
 122     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
 123                    Style.AlwaysBreakBeforeMultilineStrings);
 124     IO.mapOptional("BreakBeforeBinaryOperators",
 125                    Style.BreakBeforeBinaryOperators);
 126     IO.mapOptional("BreakBeforeTernaryOperators",
 127                    Style.BreakBeforeTernaryOperators);
 128     IO.mapOptional("BreakConstructorInitializersBeforeComma",
 129                    Style.BreakConstructorInitializersBeforeComma);
 130     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
 131     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
 132     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
 133                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
 134     IO.mapOptional("DerivePointerBinding", Style.DerivePointerBinding);
 135     IO.mapOptional("ExperimentalAutoDetectBinPacking",
 136                    Style.ExperimentalAutoDetectBinPacking);
 137     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
 138     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
 139     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
 140     IO.mapOptional("ObjCSpaceBeforeProtocolList",
 141                    Style.ObjCSpaceBeforeProtocolList);
 142     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
 143                    Style.PenaltyBreakBeforeFirstCallParameter);
 144     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
 145     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
 146     IO.mapOptional("PenaltyBreakFirstLessLess",
 147                    Style.PenaltyBreakFirstLessLess);
 148     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
 149     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
 150                    Style.PenaltyReturnTypeOnItsOwnLine);
 151     IO.mapOptional("PointerBindsToType", Style.PointerBindsToType);
 152     IO.mapOptional("SpacesBeforeTrailingComments",
 153                    Style.SpacesBeforeTrailingComments);
 154     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
 155     IO.mapOptional("Standard", Style.Standard);
 156     IO.mapOptional("IndentWidth", Style.IndentWidth);
 157     IO.mapOptional("TabWidth", Style.TabWidth);
 158     IO.mapOptional("UseTab", Style.UseTab);
 159     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
 160     IO.mapOptional("IndentFunctionDeclarationAfterType",
 161                    Style.IndentFunctionDeclarationAfterType);
 162     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
 163     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
 164     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
 165     IO.mapOptional("SpacesInCStyleCastParentheses",
 166                    Style.SpacesInCStyleCastParentheses);
 167     IO.mapOptional("SpaceAfterControlStatementKeyword",
 168                    Style.SpaceAfterControlStatementKeyword);
 169     IO.mapOptional("SpaceBeforeAssignmentOperators",
 170                    Style.SpaceBeforeAssignmentOperators);
 171     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
 172   }
 173 };
 174 }
 175 }
 176
 177 namespace clang {
 178 namespace format {
 179
 180 void setDefaultPenalties(FormatStyle &Style) {
 181   Style.PenaltyBreakComment = 60;
 182   Style.PenaltyBreakFirstLessLess = 120;
 183   Style.PenaltyBreakString = 1000;
 184   Style.PenaltyExcessCharacter = 1000000;
 185 }
 186
 187 FormatStyle getLLVMStyle() {
 188   FormatStyle LLVMStyle;
 189   LLVMStyle.AccessModifierOffset = -2;
 190   LLVMStyle.AlignEscapedNewlinesLeft = false;
 191   LLVMStyle.AlignTrailingComments = true;
 192   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
 193   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
 194   LLVMStyle.AllowShortLoopsOnASingleLine = false;
 195   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
 196   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
 197   LLVMStyle.BinPackParameters = true;
 198   LLVMStyle.BreakBeforeBinaryOperators = false;
 199   LLVMStyle.BreakBeforeTernaryOperators = true;
 200   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
 201   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
 202   LLVMStyle.ColumnLimit = 80;
 203   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
 204   LLVMStyle.ConstructorInitializerIndentWidth = 4;
 205   LLVMStyle.Cpp11BracedListStyle = false;
 206   LLVMStyle.DerivePointerBinding = false;
 207   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
 208   LLVMStyle.IndentCaseLabels = false;
 209   LLVMStyle.IndentFunctionDeclarationAfterType = false;
 210   LLVMStyle.IndentWidth = 2;
 211   LLVMStyle.TabWidth = 8;
 212   LLVMStyle.MaxEmptyLinesToKeep = 1;
 213   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
 214   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
 215   LLVMStyle.PointerBindsToType = false;
 216   LLVMStyle.SpacesBeforeTrailingComments = 1;
 217   LLVMStyle.Standard = FormatStyle::LS_Cpp03;
 218   LLVMStyle.UseTab = FormatStyle::UT_Never;
 219   LLVMStyle.SpacesInParentheses = false;
 220   LLVMStyle.SpaceInEmptyParentheses = false;
 221   LLVMStyle.SpacesInCStyleCastParentheses = false;
 222   LLVMStyle.SpaceAfterControlStatementKeyword = true;
 223   LLVMStyle.SpaceBeforeAssignmentOperators = true;
 224   LLVMStyle.ContinuationIndentWidth = 4;
 225   LLVMStyle.SpacesInAngles = false;
 226
 227   setDefaultPenalties(LLVMStyle);
 228   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
 229   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
 230
 231   return LLVMStyle;
 232 }
 233
 234 FormatStyle getGoogleStyle() {
 235   FormatStyle GoogleStyle;
 236   GoogleStyle.AccessModifierOffset = -1;
 237   GoogleStyle.AlignEscapedNewlinesLeft = true;
 238   GoogleStyle.AlignTrailingComments = true;
 239   GoogleStyle.AllowAllParametersOfDeclarationOnNextLine = true;
 240   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
 241   GoogleStyle.AllowShortLoopsOnASingleLine = true;
 242   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
 243   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
 244   GoogleStyle.BinPackParameters = true;
 245   GoogleStyle.BreakBeforeBinaryOperators = false;
 246   GoogleStyle.BreakBeforeTernaryOperators = true;
 247   GoogleStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
 248   GoogleStyle.BreakConstructorInitializersBeforeComma = false;
 249   GoogleStyle.ColumnLimit = 80;
 250   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
 251   GoogleStyle.ConstructorInitializerIndentWidth = 4;
 252   GoogleStyle.Cpp11BracedListStyle = true;
 253   GoogleStyle.DerivePointerBinding = true;
 254   GoogleStyle.ExperimentalAutoDetectBinPacking = false;
 255   GoogleStyle.IndentCaseLabels = true;
 256   GoogleStyle.IndentFunctionDeclarationAfterType = true;
 257   GoogleStyle.IndentWidth = 2;
 258   GoogleStyle.TabWidth = 8;
 259   GoogleStyle.MaxEmptyLinesToKeep = 1;
 260   GoogleStyle.NamespaceIndentation = FormatStyle::NI_None;
 261   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
 262   GoogleStyle.PointerBindsToType = true;
 263   GoogleStyle.SpacesBeforeTrailingComments = 2;
 264   GoogleStyle.Standard = FormatStyle::LS_Auto;
 265   GoogleStyle.UseTab = FormatStyle::UT_Never;
 266   GoogleStyle.SpacesInParentheses = false;
 267   GoogleStyle.SpaceInEmptyParentheses = false;
 268   GoogleStyle.SpacesInCStyleCastParentheses = false;
 269   GoogleStyle.SpaceAfterControlStatementKeyword = true;
 270   GoogleStyle.SpaceBeforeAssignmentOperators = true;
 271   GoogleStyle.ContinuationIndentWidth = 4;
 272   GoogleStyle.SpacesInAngles = false;
 273
 274   setDefaultPenalties(GoogleStyle);
 275   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
 276   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
 277
 278   return GoogleStyle;
 279 }
 280
 281 FormatStyle getChromiumStyle() {
 282   FormatStyle ChromiumStyle = getGoogleStyle();
 283   ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
 284   ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
 285   ChromiumStyle.AllowShortLoopsOnASingleLine = false;
 286   ChromiumStyle.BinPackParameters = false;
 287   ChromiumStyle.DerivePointerBinding = false;
 288   ChromiumStyle.Standard = FormatStyle::LS_Cpp03;
 289   return ChromiumStyle;
 290 }
 291
 292 FormatStyle getMozillaStyle() {
 293   FormatStyle MozillaStyle = getLLVMStyle();
 294   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
 295   MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
 296   MozillaStyle.DerivePointerBinding = true;
 297   MozillaStyle.IndentCaseLabels = true;
 298   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
 299   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
 300   MozillaStyle.PointerBindsToType = true;
 301   return MozillaStyle;
 302 }
 303
 304 FormatStyle getWebKitStyle() {
 305   FormatStyle Style = getLLVMStyle();
 306   Style.AccessModifierOffset = -4;
 307   Style.AlignTrailingComments = false;
 308   Style.BreakBeforeBinaryOperators = true;
 309   Style.BreakBeforeBraces = FormatStyle::BS_Stroustrup;
 310   Style.BreakConstructorInitializersBeforeComma = true;
 311   Style.ColumnLimit = 0;
 312   Style.IndentWidth = 4;
 313   Style.NamespaceIndentation = FormatStyle::NI_Inner;
 314   Style.PointerBindsToType = true;
 315   return Style;
 316 }
 317
 318 bool getPredefinedStyle(StringRef Name, FormatStyle *Style) {
 319   if (Name.equals_lower("llvm"))
 320     *Style = getLLVMStyle();
 321   else if (Name.equals_lower("chromium"))
 322     *Style = getChromiumStyle();
 323   else if (Name.equals_lower("mozilla"))
 324     *Style = getMozillaStyle();
 325   else if (Name.equals_lower("google"))
 326     *Style = getGoogleStyle();
 327   else if (Name.equals_lower("webkit"))
 328     *Style = getWebKitStyle();
 329   else
 330     return false;
 331
 332   return true;
 333 }
 334
 335 llvm::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
 336   if (Text.trim().empty())
 337     return llvm::make_error_code(llvm::errc::invalid_argument);
 338   llvm::yaml::Input Input(Text);
 339   Input >> *Style;
 340   return Input.error();
 341 }
 342
 343 std::string configurationAsText(const FormatStyle &Style) {
 344   std::string Text;
 345   llvm::raw_string_ostream Stream(Text);
 346   llvm::yaml::Output Output(Stream);
 347   // We use the same mapping method for input and output, so we need a non-const
 348   // reference here.
 349   FormatStyle NonConstStyle = Style;
 350   Output << NonConstStyle;
 351   return Stream.str();
 352 }
 353
 354 namespace {
 355
 356 class NoColumnLimitFormatter {
 357 public:
 358   NoColumnLimitFormatter(ContinuationIndenter *Indenter) : Indenter(Indenter) {}
 359
 360   /// \brief Formats the line starting at \p State, simply keeping all of the
 361   /// input's line breaking decisions.
 362   void format(unsigned FirstIndent, const AnnotatedLine *Line) {
 363     LineState State =
 364         Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false);
 365     while (State.NextToken != NULL) {
 366       bool Newline =
 367           Indenter->mustBreak(State) ||
 368           (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
 369       Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
 370     }
 371   }
 372
 373 private:
 374   ContinuationIndenter *Indenter;
 375 };
 376
 377 class LineJoiner {
 378 public:
 379   LineJoiner(const FormatStyle &Style) : Style(Style) {}
 380
 381   /// \brief Calculates how many lines can be merged into 1 starting at \p I.
 382   unsigned
 383   tryFitMultipleLinesInOne(unsigned Indent,
 384                            SmallVectorImpl<AnnotatedLine *>::const_iterator &I,
 385                            SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
 386     // We can never merge stuff if there are trailing line comments.
 387     AnnotatedLine *TheLine = *I;
 388     if (TheLine->Last->Type == TT_LineComment)
 389       return 0;
 390
 391     if (Indent > Style.ColumnLimit)
 392       return 0;
 393
 394     unsigned Limit =
 395         Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;
 396     // If we already exceed the column limit, we set 'Limit' to 0. The different
 397     // tryMerge..() functions can then decide whether to still do merging.
 398     Limit = TheLine->Last->TotalLength > Limit
 399                 ? 0
 400                 : Limit - TheLine->Last->TotalLength;
 401
 402     if (I + 1 == E || I[1]->Type == LT_Invalid)
 403       return 0;
 404
 405     if (TheLine->Last->is(tok::l_brace)) {
 406       return tryMergeSimpleBlock(I, E, Limit);
 407     } else if (Style.AllowShortIfStatementsOnASingleLine &&
 408                TheLine->First->is(tok::kw_if)) {
 409       return tryMergeSimpleControlStatement(I, E, Limit);
 410     } else if (Style.AllowShortLoopsOnASingleLine &&
 411                TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
 412       return tryMergeSimpleControlStatement(I, E, Limit);
 413     } else if (TheLine->InPPDirective && (TheLine->First->HasUnescapedNewline ||
 414                                           TheLine->First->IsFirst)) {
 415       return tryMergeSimplePPDirective(I, E, Limit);
 416     }
 417     return 0;
 418   }
 419
 420 private:
 421   unsigned
 422   tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator &I,
 423                             SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 424                             unsigned Limit) {
 425     if (Limit == 0)
 426       return 0;
 427     if (!I[1]->InPPDirective || I[1]->First->HasUnescapedNewline)
 428       return 0;
 429     if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
 430       return 0;
 431     if (1 + I[1]->Last->TotalLength > Limit)
 432       return 0;
 433     return 1;
 434   }
 435
 436   unsigned tryMergeSimpleControlStatement(
 437       SmallVectorImpl<AnnotatedLine *>::const_iterator &I,
 438       SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
 439     if (Limit == 0)
 440       return 0;
 441     if (Style.BreakBeforeBraces == FormatStyle::BS_Allman &&
 442         I[1]->First->is(tok::l_brace))
 443       return 0;
 444     if (I[1]->InPPDirective != (*I)->InPPDirective ||
 445         (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline))
 446       return 0;
 447     AnnotatedLine &Line = **I;
 448     if (Line.Last->isNot(tok::r_paren))
 449       return 0;
 450     if (1 + I[1]->Last->TotalLength > Limit)
 451       return 0;
 452     if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
 453                                    tok::kw_while) ||
 454         I[1]->First->Type == TT_LineComment)
 455       return 0;
 456     // Only inline simple if's (no nested if or else).
 457     if (I + 2 != E && Line.First->is(tok::kw_if) &&
 458         I[2]->First->is(tok::kw_else))
 459       return 0;
 460     return 1;
 461   }
 462
 463   unsigned
 464   tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator &I,
 465                       SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 466                       unsigned Limit) {
 467     // No merging if the brace already is on the next line.
 468     if (Style.BreakBeforeBraces != FormatStyle::BS_Attach)
 469       return 0;
 470
 471     // First, check that the current line allows merging. This is the case if
 472     // we're not in a control flow statement and the last token is an opening
 473     // brace.
 474     AnnotatedLine &Line = **I;
 475     if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace,
 476                             tok::kw_else, tok::kw_try, tok::kw_catch,
 477                             tok::kw_for,
 478                             // This gets rid of all ObjC @ keywords and methods.
 479                             tok::at, tok::minus, tok::plus))
 480       return 0;
 481
 482     FormatToken *Tok = I[1]->First;
 483     if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
 484         (Tok->getNextNonComment() == NULL ||
 485          Tok->getNextNonComment()->is(tok::semi))) {
 486       // We merge empty blocks even if the line exceeds the column limit.
 487       Tok->SpacesRequiredBefore = 0;
 488       Tok->CanBreakBefore = true;
 489       return 1;
 490     } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace)) {
 491       // Check that we still have three lines and they fit into the limit.
 492       if (I + 2 == E || I[2]->Type == LT_Invalid)
 493         return 0;
 494
 495       if (!nextTwoLinesFitInto(I, Limit))
 496         return 0;
 497
 498       // Second, check that the next line does not contain any braces - if it
 499       // does, readability declines when putting it into a single line.
 500       if (I[1]->Last->Type == TT_LineComment || Tok->MustBreakBefore)
 501         return 0;
 502       do {
 503         if (Tok->isOneOf(tok::l_brace, tok::r_brace))
 504           return 0;
 505         Tok = Tok->Next;
 506       } while (Tok != NULL);
 507
 508       // Last, check that the third line contains a single closing brace.
 509       Tok = I[2]->First;
 510       if (Tok->getNextNonComment() != NULL || Tok->isNot(tok::r_brace) ||
 511           Tok->MustBreakBefore)
 512         return 0;
 513
 514       return 2;
 515     }
 516     return 0;
 517   }
 518
 519   bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 520                            unsigned Limit) {
 521     return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
 522   }
 523
 524   const FormatStyle &Style;
 525 };
 526
 527 class UnwrappedLineFormatter {
 528 public:
 529   UnwrappedLineFormatter(SourceManager &SourceMgr,
 530                          SmallVectorImpl<CharSourceRange> &Ranges,
 531                          ContinuationIndenter *Indenter,
 532                          WhitespaceManager *Whitespaces,
 533                          const FormatStyle &Style)
 534       : SourceMgr(SourceMgr), Ranges(Ranges), Indenter(Indenter),
 535         Whitespaces(Whitespaces), Style(Style), Joiner(Style) {}
 536
 537   unsigned format(const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun,
 538                   int AdditionalIndent = 0) {
 539     assert(!Lines.empty());
 540     unsigned Penalty = 0;
 541     std::vector<int> IndentForLevel;
 542     for (unsigned i = 0, e = Lines[0]->Level; i != e; ++i)
 543       IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);
 544     bool PreviousLineWasTouched = false;
 545     const AnnotatedLine *PreviousLine = NULL;
 546     bool FormatPPDirective = false;
 547     for (SmallVectorImpl<AnnotatedLine *>::const_iterator I = Lines.begin(),
 548                                                           E = Lines.end();
 549          I != E; ++I) {
 550       const AnnotatedLine &TheLine = **I;
 551       const FormatToken *FirstTok = TheLine.First;
 552       int Offset = getIndentOffset(*FirstTok);
 553
 554       // Check whether this line is part of a formatted preprocessor directive.
 555       if (FirstTok->HasUnescapedNewline)
 556         FormatPPDirective = false;
 557       if (!FormatPPDirective && TheLine.InPPDirective &&
 558           (touchesLine(TheLine) || touchesPPDirective(I + 1, E)))
 559         FormatPPDirective = true;
 560
 561       // Determine indent and try to merge multiple unwrapped lines.
 562       while (IndentForLevel.size() <= TheLine.Level)
 563         IndentForLevel.push_back(-1);
 564       IndentForLevel.resize(TheLine.Level + 1);
 565       unsigned Indent = getIndent(IndentForLevel, TheLine.Level);
 566       if (static_cast<int>(Indent) + Offset >= 0)
 567         Indent += Offset;
 568       unsigned MergedLines = Joiner.tryFitMultipleLinesInOne(Indent, I, E);
 569       if (!DryRun) {
 570         for (unsigned i = 0; i < MergedLines; ++i) {
 571           join(*I[i], *I[i + 1]);
 572         }
 573       }
 574       I += MergedLines;
 575
 576       bool WasMoved = PreviousLineWasTouched && FirstTok->NewlinesBefore == 0;
 577       if (TheLine.First->is(tok::eof)) {
 578         if (PreviousLineWasTouched && !DryRun) {
 579           unsigned Newlines = std::min(FirstTok->NewlinesBefore, 1u);
 580           Whitespaces->replaceWhitespace(*TheLine.First, Newlines,
 581                                          /*IndentLevel=*/0, /*Spaces=*/0,
 582                                          /*TargetColumn=*/0);
 583         }
 584       } else if (TheLine.Type != LT_Invalid &&
 585                  (WasMoved || FormatPPDirective || touchesLine(TheLine))) {
 586         unsigned LevelIndent =
 587             getIndent(IndentForLevel, TheLine.Level);
 588         if (FirstTok->WhitespaceRange.isValid()) {
 589           if (!DryRun)
 590             formatFirstToken(*TheLine.First, PreviousLine, TheLine.Level,
 591                              Indent, TheLine.InPPDirective);
 592         } else {
 593           Indent = LevelIndent = FirstTok->OriginalColumn;
 594         }
 595
 596         // If everything fits on a single line, just put it there.
 597         unsigned ColumnLimit = Style.ColumnLimit;
 598         if (I + 1 != E) {
 599           AnnotatedLine *NextLine = I[1];
 600           if (NextLine->InPPDirective && !NextLine->First->HasUnescapedNewline)
 601             ColumnLimit = getColumnLimit(TheLine.InPPDirective);
 602         }
 603
 604         if (TheLine.Last->TotalLength + Indent <= ColumnLimit) {
 605           LineState State = Indenter->getInitialState(Indent, &TheLine, DryRun);
 606           while (State.NextToken != NULL)
 607             Indenter->addTokenToState(State, /*Newline=*/false, DryRun);
 608         } else if (Style.ColumnLimit == 0) {
 609           NoColumnLimitFormatter Formatter(Indenter);
 610           if (!DryRun)
 611             Formatter.format(Indent, &TheLine);
 612         } else {
 613           Penalty += format(TheLine, Indent, DryRun);
 614         }
 615
 616         IndentForLevel[TheLine.Level] = LevelIndent;
 617         PreviousLineWasTouched = true;
 618       } else {
 619         // Format the first token if necessary, and notify the WhitespaceManager
 620         // about the unchanged whitespace.
 621         for (FormatToken *Tok = TheLine.First; Tok != NULL; Tok = Tok->Next) {
 622           if (Tok == TheLine.First &&
 623               (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
 624             unsigned LevelIndent = Tok->OriginalColumn;
 625             if (!DryRun) {
 626               // Remove trailing whitespace of the previous line if it was
 627               // touched.
 628               if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine)) {
 629                 formatFirstToken(*Tok, PreviousLine, TheLine.Level, LevelIndent,
 630                                  TheLine.InPPDirective);
 631               } else {
 632                 Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
 633               }
 634             }
 635
 636             if (static_cast<int>(LevelIndent) - Offset >= 0)
 637               LevelIndent -= Offset;
 638             if (Tok->isNot(tok::comment))
 639               IndentForLevel[TheLine.Level] = LevelIndent;
 640           } else if (!DryRun) {
 641             Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
 642           }
 643         }
 644         // If we did not reformat this unwrapped line, the column at the end of
 645         // the last token is unchanged - thus, we can calculate the end of the
 646         // last token.
 647         PreviousLineWasTouched = false;
 648       }
 649       if (!DryRun) {
 650         for (FormatToken *Tok = TheLine.First; Tok != NULL; Tok = Tok->Next) {
 651           Tok->Finalized = true;
 652         }
 653       }
 654       PreviousLine = *I;
 655     }
 656     return Penalty;
 657   }
 658
 659 private:
 660   /// \brief Formats an \c AnnotatedLine and returns the penalty.
 661   ///
 662   /// If \p DryRun is \c false, directly applies the changes.
 663   unsigned format(const AnnotatedLine &Line, unsigned FirstIndent,
 664                   bool DryRun) {
 665     LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun);
 666
 667     // If the ObjC method declaration does not fit on a line, we should format
 668     // it with one arg per line.
 669     if (State.Line->Type == LT_ObjCMethodDecl)
 670       State.Stack.back().BreakBeforeParameter = true;
 671
 672     // Find best solution in solution space.
 673     return analyzeSolutionSpace(State, DryRun);
 674   }
 675
 676   /// \brief An edge in the solution space from \c Previous->State to \c State,
 677   /// inserting a newline dependent on the \c NewLine.
 678   struct StateNode {
 679     StateNode(const LineState &State, bool NewLine, StateNode *Previous)
 680         : State(State), NewLine(NewLine), Previous(Previous) {}
 681     LineState State;
 682     bool NewLine;
 683     StateNode *Previous;
 684   };
 685
 686   /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
 687   ///
 688   /// In case of equal penalties, we want to prefer states that were inserted
 689   /// first. During state generation we make sure that we insert states first
 690   /// that break the line as late as possible.
 691   typedef std::pair<unsigned, unsigned> OrderedPenalty;
 692
 693   /// \brief An item in the prioritized BFS search queue. The \c StateNode's
 694   /// \c State has the given \c OrderedPenalty.
 695   typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
 696
 697   /// \brief The BFS queue type.
 698   typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
 699                               std::greater<QueueItem> > QueueType;
 700
 701   /// \brief Get the offset of the line relatively to the level.
 702   ///
 703   /// For example, 'public:' labels in classes are offset by 1 or 2
 704   /// characters to the left from their level.
 705   int getIndentOffset(const FormatToken &RootToken) {
 706     if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
 707       return Style.AccessModifierOffset;
 708     return 0;
 709   }
 710
 711   /// \brief Add a new line and the required indent before the first Token
 712   /// of the \c UnwrappedLine if there was no structural parsing error.
 713   void formatFirstToken(FormatToken &RootToken,
 714                         const AnnotatedLine *PreviousLine, unsigned IndentLevel,
 715                         unsigned Indent, bool InPPDirective) {
 716     unsigned Newlines =
 717         std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
 718     // Remove empty lines before "}" where applicable.
 719     if (RootToken.is(tok::r_brace) &&
 720         (!RootToken.Next ||
 721          (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
 722       Newlines = std::min(Newlines, 1u);
 723     if (Newlines == 0 && !RootToken.IsFirst)
 724       Newlines = 1;
 725
 726     // Insert extra new line before access specifiers.
 727     if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
 728         RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
 729       ++Newlines;
 730
 731     // Remove empty lines after access specifiers.
 732     if (PreviousLine && PreviousLine->First->isAccessSpecifier())
 733       Newlines = std::min(1u, Newlines);
 734
 735     Whitespaces->replaceWhitespace(
 736         RootToken, Newlines, IndentLevel, Indent, Indent,
 737         InPPDirective && !RootToken.HasUnescapedNewline);
 738   }
 739
 740   /// \brief Get the indent of \p Level from \p IndentForLevel.
 741   ///
 742   /// \p IndentForLevel must contain the indent for the level \c l
 743   /// at \p IndentForLevel[l], or a value < 0 if the indent for
 744   /// that level is unknown.
 745   unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
 746     if (IndentForLevel[Level] != -1)
 747       return IndentForLevel[Level];
 748     if (Level == 0)
 749       return 0;
 750     return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
 751   }
 752
 753   void join(AnnotatedLine &A, const AnnotatedLine &B) {
 754     assert(!A.Last->Next);
 755     assert(!B.First->Previous);
 756     A.Last->Next = B.First;
 757     B.First->Previous = A.Last;
 758     B.First->CanBreakBefore = true;
 759     unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
 760     for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
 761       Tok->TotalLength += LengthA;
 762       A.Last = Tok;
 763     }
 764   }
 765
 766   unsigned getColumnLimit(bool InPPDirective) const {
 767     // In preprocessor directives reserve two chars for trailing " \"
 768     return Style.ColumnLimit - (InPPDirective ? 2 : 0);
 769   }
 770
 771   bool touchesRanges(const CharSourceRange &Range) {
 772     for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
 773                                                           E = Ranges.end();
 774          I != E; ++I) {
 775       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
 776           !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
 777         return true;
 778     }
 779     return false;
 780   }
 781
 782   bool touchesLine(const AnnotatedLine &TheLine) {
 783     const FormatToken *First = TheLine.First;
 784     const FormatToken *Last = TheLine.Last;
 785     CharSourceRange LineRange = CharSourceRange::getCharRange(
 786         First->WhitespaceRange.getBegin().getLocWithOffset(
 787             First->LastNewlineOffset),
 788         Last->getStartOfNonWhitespace().getLocWithOffset(
 789             Last->TokenText.size() - 1));
 790     return touchesRanges(LineRange);
 791   }
 792
 793   bool touchesPPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 794                           SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
 795     for (; I != E; ++I) {
 796       if ((*I)->First->HasUnescapedNewline)
 797         return false;
 798       if (touchesLine(**I))
 799         return true;
 800     }
 801     return false;
 802   }
 803
 804   bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) {
 805     const FormatToken *First = TheLine.First;
 806     CharSourceRange LineRange = CharSourceRange::getCharRange(
 807         First->WhitespaceRange.getBegin(),
 808         First->WhitespaceRange.getBegin().getLocWithOffset(
 809             First->LastNewlineOffset));
 810     return touchesRanges(LineRange);
 811   }
 812
 813   /// \brief Analyze the entire solution space starting from \p InitialState.
 814   ///
 815   /// This implements a variant of Dijkstra's algorithm on the graph that spans
 816   /// the solution space (\c LineStates are the nodes). The algorithm tries to
 817   /// find the shortest path (the one with lowest penalty) from \p InitialState
 818   /// to a state where all tokens are placed. Returns the penalty.
 819   ///
 820   /// If \p DryRun is \c false, directly applies the changes.
 821   unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false) {
 822     std::set<LineState> Seen;
 823
 824     // Increasing count of \c StateNode items we have created. This is used to
 825     // create a deterministic order independent of the container.
 826     unsigned Count = 0;
 827     QueueType Queue;
 828
 829     // Insert start element into queue.
 830     StateNode *Node =
 831         new (Allocator.Allocate()) StateNode(InitialState, false, NULL);
 832     Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
 833     ++Count;
 834
 835     unsigned Penalty = 0;
 836
 837     // While not empty, take first element and follow edges.
 838     while (!Queue.empty()) {
 839       Penalty = Queue.top().first.first;
 840       StateNode *Node = Queue.top().second;
 841       if (Node->State.NextToken == NULL) {
 842         DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
 843         break;
 844       }
 845       Queue.pop();
 846
 847       // Cut off the analysis of certain solutions if the analysis gets too
 848       // complex. See description of IgnoreStackForComparison.
 849       if (Count > 10000)
 850         Node->State.IgnoreStackForComparison = true;
 851
 852       if (!Seen.insert(Node->State).second)
 853         // State already examined with lower penalty.
 854         continue;
 855
 856       FormatDecision LastFormat = Node->State.NextToken->Decision;
 857       if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
 858         addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
 859       if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
 860         addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
 861     }
 862
 863     if (Queue.empty()) {
 864       // We were unable to find a solution, do nothing.
 865       // FIXME: Add diagnostic?
 866       DEBUG(llvm::dbgs() << "Could not find a solution.\n");
 867       return 0;
 868     }
 869
 870     // Reconstruct the solution.
 871     if (!DryRun)
 872       reconstructPath(InitialState, Queue.top().second);
 873
 874     DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
 875     DEBUG(llvm::dbgs() << "---\n");
 876
 877     return Penalty;
 878   }
 879
 880   void reconstructPath(LineState &State, StateNode *Current) {
 881     std::deque<StateNode *> Path;
 882     // We do not need a break before the initial token.
 883     while (Current->Previous) {
 884       Path.push_front(Current);
 885       Current = Current->Previous;
 886     }
 887     for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
 888          I != E; ++I) {
 889       unsigned Penalty = 0;
 890       formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
 891       Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
 892
 893       DEBUG({
 894         if ((*I)->NewLine) {
 895           llvm::dbgs() << "Penalty for placing "
 896                        << (*I)->Previous->State.NextToken->Tok.getName() << ": "
 897                        << Penalty << "\n";
 898         }
 899       });
 900     }
 901   }
 902
 903   /// \brief Add the following state to the analysis queue \c Queue.
 904   ///
 905   /// Assume the current state is \p PreviousNode and has been reached with a
 906   /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
 907   void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
 908                            bool NewLine, unsigned *Count, QueueType *Queue) {
 909     if (NewLine && !Indenter->canBreak(PreviousNode->State))
 910       return;
 911     if (!NewLine && Indenter->mustBreak(PreviousNode->State))
 912       return;
 913
 914     StateNode *Node = new (Allocator.Allocate())
 915         StateNode(PreviousNode->State, NewLine, PreviousNode);
 916     if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
 917       return;
 918
 919     Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
 920
 921     Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
 922     ++(*Count);
 923   }
 924
 925   /// \brief If the \p State's next token is an r_brace closing a nested block,
 926   /// format the nested block before it.
 927   ///
 928   /// Returns \c true if all children could be placed successfully and adapts
 929   /// \p Penalty as well as \p State. If \p DryRun is false, also directly
 930   /// creates changes using \c Whitespaces.
 931   ///
 932   /// The crucial idea here is that children always get formatted upon
 933   /// encountering the closing brace right after the nested block. Now, if we
 934   /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
 935   /// \c false), the entire block has to be kept on the same line (which is only
 936   /// possible if it fits on the line, only contains a single statement, etc.
 937   ///
 938   /// If \p NewLine is true, we format the nested block on separate lines, i.e.
 939   /// break after the "{", format all lines with correct indentation and the put
 940   /// the closing "}" on yet another new line.
 941   ///
 942   /// This enables us to keep the simple structure of the
 943   /// \c UnwrappedLineFormatter, where we only have two options for each token:
 944   /// break or don't break.
 945   bool formatChildren(LineState &State, bool NewLine, bool DryRun,
 946                       unsigned &Penalty) {
 947     FormatToken &Previous = *State.NextToken->Previous;
 948     const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
 949     if (!LBrace || LBrace->isNot(tok::l_brace) ||
 950         LBrace->BlockKind != BK_Block || Previous.Children.size() == 0)
 951       // The previous token does not open a block. Nothing to do. We don't
 952       // assert so that we can simply call this function for all tokens.
 953       return true;
 954
 955     if (NewLine) {
 956       int AdditionalIndent = State.Stack.back().Indent -
 957                              Previous.Children[0]->Level * Style.IndentWidth;
 958       Penalty += format(Previous.Children, DryRun, AdditionalIndent);
 959       return true;
 960     }
 961
 962     // Cannot merge multiple statements into a single line.
 963     if (Previous.Children.size() > 1)
 964       return false;
 965
 966     // We can't put the closing "}" on a line with a trailing comment.
 967     if (Previous.Children[0]->Last->isTrailingComment())
 968       return false;
 969
 970     if (!DryRun) {
 971       Whitespaces->replaceWhitespace(
 972           *Previous.Children[0]->First,
 973           /*Newlines=*/0, /*IndentLevel=*/0, /*Spaces=*/1,
 974           /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
 975     }
 976     Penalty += format(*Previous.Children[0], State.Column + 1, DryRun);
 977
 978     State.Column += 1 + Previous.Children[0]->Last->TotalLength;
 979     return true;
 980   }
 981
 982   SourceManager &SourceMgr;
 983   SmallVectorImpl<CharSourceRange> &Ranges;
 984   ContinuationIndenter *Indenter;
 985   WhitespaceManager *Whitespaces;
 986   FormatStyle Style;
 987   LineJoiner Joiner;
 988
 989   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
 990 };
 991
 992 class FormatTokenLexer {
 993 public:
 994   FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr, FormatStyle &Style,
 995                    encoding::Encoding Encoding)
 996       : FormatTok(NULL), IsFirstToken(true), GreaterStashed(false), Column(0),
 997         TrailingWhitespace(0), Lex(Lex), SourceMgr(SourceMgr), Style(Style),
 998         IdentTable(getFormattingLangOpts()), Encoding(Encoding) {
 999     Lex.SetKeepWhitespaceMode(true);
1000   }
1001
1002   ArrayRef<FormatToken *> lex() {
1003     assert(Tokens.empty());
1004     do {
1005       Tokens.push_back(getNextToken());
1006       maybeJoinPreviousTokens();
1007     } while (Tokens.back()->Tok.isNot(tok::eof));
1008     return Tokens;
1009   }
1010
1011   IdentifierTable &getIdentTable() { return IdentTable; }
1012
1013 private:
1014   void maybeJoinPreviousTokens() {
1015     if (Tokens.size() < 4)
1016       return;
1017     FormatToken *Last = Tokens.back();
1018     if (!Last->is(tok::r_paren))
1019       return;
1020
1021     FormatToken *String = Tokens[Tokens.size() - 2];
1022     if (!String->is(tok::string_literal) || String->IsMultiline)
1023       return;
1024
1025     if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
1026       return;
1027
1028     FormatToken *Macro = Tokens[Tokens.size() - 4];
1029     if (Macro->TokenText != "_T")
1030       return;
1031
1032     const char *Start = Macro->TokenText.data();
1033     const char *End = Last->TokenText.data() + Last->TokenText.size();
1034     String->TokenText = StringRef(Start, End - Start);
1035     String->IsFirst = Macro->IsFirst;
1036     String->LastNewlineOffset = Macro->LastNewlineOffset;
1037     String->WhitespaceRange = Macro->WhitespaceRange;
1038     String->OriginalColumn = Macro->OriginalColumn;
1039     String->ColumnWidth = encoding::columnWidthWithTabs(
1040         String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
1041
1042     Tokens.pop_back();
1043     Tokens.pop_back();
1044     Tokens.pop_back();
1045     Tokens.back() = String;
1046   }
1047
1048   FormatToken *getNextToken() {
1049     if (GreaterStashed) {
1050       // Create a synthesized second '>' token.
1051       // FIXME: Increment Column and set OriginalColumn.
1052       Token Greater = FormatTok->Tok;
1053       FormatTok = new (Allocator.Allocate()) FormatToken;
1054       FormatTok->Tok = Greater;
1055       SourceLocation GreaterLocation =
1056           FormatTok->Tok.getLocation().getLocWithOffset(1);
1057       FormatTok->WhitespaceRange =
1058           SourceRange(GreaterLocation, GreaterLocation);
1059       FormatTok->TokenText = ">";
1060       FormatTok->ColumnWidth = 1;
1061       GreaterStashed = false;
1062       return FormatTok;
1063     }
1064
1065     FormatTok = new (Allocator.Allocate()) FormatToken;
1066     readRawToken(*FormatTok);
1067     SourceLocation WhitespaceStart =
1068         FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
1069     FormatTok->IsFirst = IsFirstToken;
1070     IsFirstToken = false;
1071
1072     // Consume and record whitespace until we find a significant token.
1073     unsigned WhitespaceLength = TrailingWhitespace;
1074     while (FormatTok->Tok.is(tok::unknown)) {
1075       for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) {
1076         switch (FormatTok->TokenText[i]) {
1077         case '\n':
1078           ++FormatTok->NewlinesBefore;
1079           // FIXME: This is technically incorrect, as it could also
1080           // be a literal backslash at the end of the line.
1081           if (i == 0 || (FormatTok->TokenText[i - 1] != '\\' &&
1082                          (FormatTok->TokenText[i - 1] != '\r' || i == 1 ||
1083                           FormatTok->TokenText[i - 2] != '\\')))
1084             FormatTok->HasUnescapedNewline = true;
1085           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1086           Column = 0;
1087           break;
1088         case '\r':
1089         case '\f':
1090         case '\v':
1091           Column = 0;
1092           break;
1093         case ' ':
1094           ++Column;
1095           break;
1096         case '\t':
1097           Column += Style.TabWidth - Column % Style.TabWidth;
1098           break;
1099         case '\\':
1100           ++Column;
1101           if (i + 1 == e || (FormatTok->TokenText[i + 1] != '\r' &&
1102                              FormatTok->TokenText[i + 1] != '\n'))
1103             FormatTok->Type = TT_ImplicitStringLiteral;
1104           break;
1105         default:
1106           FormatTok->Type = TT_ImplicitStringLiteral;
1107           ++Column;
1108           break;
1109         }
1110       }
1111
1112       if (FormatTok->Type == TT_ImplicitStringLiteral)
1113         break;
1114       WhitespaceLength += FormatTok->Tok.getLength();
1115
1116       readRawToken(*FormatTok);
1117     }
1118
1119     // In case the token starts with escaped newlines, we want to
1120     // take them into account as whitespace - this pattern is quite frequent
1121     // in macro definitions.
1122     // FIXME: Add a more explicit test.
1123     while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
1124            FormatTok->TokenText[1] == '\n') {
1125       // FIXME: ++FormatTok->NewlinesBefore is missing...
1126       WhitespaceLength += 2;
1127       Column = 0;
1128       FormatTok->TokenText = FormatTok->TokenText.substr(2);
1129     }
1130
1131     FormatTok->WhitespaceRange = SourceRange(
1132         WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1133
1134     FormatTok->OriginalColumn = Column;
1135
1136     TrailingWhitespace = 0;
1137     if (FormatTok->Tok.is(tok::comment)) {
1138       // FIXME: Add the trimmed whitespace to Column.
1139       StringRef UntrimmedText = FormatTok->TokenText;
1140       FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
1141       TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1142     } else if (FormatTok->Tok.is(tok::raw_identifier)) {
1143       IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
1144       FormatTok->Tok.setIdentifierInfo(&Info);
1145       FormatTok->Tok.setKind(Info.getTokenID());
1146     } else if (FormatTok->Tok.is(tok::greatergreater)) {
1147       FormatTok->Tok.setKind(tok::greater);
1148       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1149       GreaterStashed = true;
1150     }
1151
1152     // Now FormatTok is the next non-whitespace token.
1153
1154     StringRef Text = FormatTok->TokenText;
1155     size_t FirstNewlinePos = Text.find('\n');
1156     if (FirstNewlinePos == StringRef::npos) {
1157       // FIXME: ColumnWidth actually depends on the start column, we need to
1158       // take this into account when the token is moved.
1159       FormatTok->ColumnWidth =
1160           encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
1161       Column += FormatTok->ColumnWidth;
1162     } else {
1163       FormatTok->IsMultiline = true;
1164       // FIXME: ColumnWidth actually depends on the start column, we need to
1165       // take this into account when the token is moved.
1166       FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1167           Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
1168
1169       // The last line of the token always starts in column 0.
1170       // Thus, the length can be precomputed even in the presence of tabs.
1171       FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1172           Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
1173           Encoding);
1174       Column = FormatTok->LastLineColumnWidth;
1175     }
1176
1177     return FormatTok;
1178   }
1179
1180   FormatToken *FormatTok;
1181   bool IsFirstToken;
1182   bool GreaterStashed;
1183   unsigned Column;
1184   unsigned TrailingWhitespace;
1185   Lexer &Lex;
1186   SourceManager &SourceMgr;
1187   FormatStyle &Style;
1188   IdentifierTable IdentTable;
1189   encoding::Encoding Encoding;
1190   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
1191   SmallVector<FormatToken *, 16> Tokens;
1192
1193   void readRawToken(FormatToken &Tok) {
1194     Lex.LexFromRawLexer(Tok.Tok);
1195     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
1196                               Tok.Tok.getLength());
1197     // For formatting, treat unterminated string literals like normal string
1198     // literals.
1199     if (Tok.is(tok::unknown) && !Tok.TokenText.empty() &&
1200         Tok.TokenText[0] == '"') {
1201       Tok.Tok.setKind(tok::string_literal);
1202       Tok.IsUnterminatedLiteral = true;
1203     }
1204   }
1205 };
1206
1207 class Formatter : public UnwrappedLineConsumer {
1208 public:
1209   Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
1210             const std::vector<CharSourceRange> &Ranges)
1211       : Style(Style), Lex(Lex), SourceMgr(SourceMgr),
1212         Whitespaces(SourceMgr, Style, inputUsesCRLF(Lex.getBuffer())),
1213         Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1),
1214         Encoding(encoding::detectEncoding(Lex.getBuffer())) {
1215     DEBUG(llvm::dbgs() << "File encoding: "
1216                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
1217                                                                : "unknown")
1218                        << "\n");
1219   }
1220
1221   tooling::Replacements format() {
1222     tooling::Replacements Result;
1223     FormatTokenLexer Tokens(Lex, SourceMgr, Style, Encoding);
1224
1225     UnwrappedLineParser Parser(Style, Tokens.lex(), *this);
1226     bool StructuralError = Parser.parse();
1227     assert(UnwrappedLines.rbegin()->empty());
1228     for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
1229          ++Run) {
1230       DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
1231       SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1232       for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
1233         AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
1234       }
1235       tooling::Replacements RunResult =
1236           format(AnnotatedLines, StructuralError, Tokens);
1237       DEBUG({
1238         llvm::dbgs() << "Replacements for run " << Run << ":\n";
1239         for (tooling::Replacements::iterator I = RunResult.begin(),
1240                                              E = RunResult.end();
1241              I != E; ++I) {
1242           llvm::dbgs() << I->toString() << "\n";
1243         }
1244       });
1245       for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1246         delete AnnotatedLines[i];
1247       }
1248       Result.insert(RunResult.begin(), RunResult.end());
1249       Whitespaces.reset();
1250     }
1251     return Result;
1252   }
1253
1254   tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1255                                bool StructuralError, FormatTokenLexer &Tokens) {
1256     TokenAnnotator Annotator(Style, Tokens.getIdentTable().get("in"));
1257     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1258       Annotator.annotate(*AnnotatedLines[i]);
1259     }
1260     deriveLocalStyle(AnnotatedLines);
1261     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1262       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1263     }
1264
1265     Annotator.setCommentLineLevels(AnnotatedLines);
1266     ContinuationIndenter Indenter(Style, SourceMgr, Whitespaces, Encoding,
1267                                   BinPackInconclusiveFunctions);
1268     UnwrappedLineFormatter Formatter(SourceMgr, Ranges, &Indenter, &Whitespaces,
1269                                      Style);
1270     Formatter.format(AnnotatedLines, /*DryRun=*/false);
1271     return Whitespaces.generateReplacements();
1272   }
1273
1274 private:
1275   static bool inputUsesCRLF(StringRef Text) {
1276     return Text.count('\r') * 2 > Text.count('\n');
1277   }
1278
1279   void
1280   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1281     unsigned CountBoundToVariable = 0;
1282     unsigned CountBoundToType = 0;
1283     bool HasCpp03IncompatibleFormat = false;
1284     bool HasBinPackedFunction = false;
1285     bool HasOnePerLineFunction = false;
1286     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1287       if (!AnnotatedLines[i]->First->Next)
1288         continue;
1289       FormatToken *Tok = AnnotatedLines[i]->First->Next;
1290       while (Tok->Next) {
1291         if (Tok->Type == TT_PointerOrReference) {
1292           bool SpacesBefore =
1293               Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1294           bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
1295                              Tok->Next->WhitespaceRange.getEnd();
1296           if (SpacesBefore && !SpacesAfter)
1297             ++CountBoundToVariable;
1298           else if (!SpacesBefore && SpacesAfter)
1299             ++CountBoundToType;
1300         }
1301
1302         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1303           if (Tok->is(tok::coloncolon) &&
1304               Tok->Previous->Type == TT_TemplateOpener)
1305             HasCpp03IncompatibleFormat = true;
1306           if (Tok->Type == TT_TemplateCloser &&
1307               Tok->Previous->Type == TT_TemplateCloser)
1308             HasCpp03IncompatibleFormat = true;
1309         }
1310
1311         if (Tok->PackingKind == PPK_BinPacked)
1312           HasBinPackedFunction = true;
1313         if (Tok->PackingKind == PPK_OnePerLine)
1314           HasOnePerLineFunction = true;
1315
1316         Tok = Tok->Next;
1317       }
1318     }
1319     if (Style.DerivePointerBinding) {
1320       if (CountBoundToType > CountBoundToVariable)
1321         Style.PointerBindsToType = true;
1322       else if (CountBoundToType < CountBoundToVariable)
1323         Style.PointerBindsToType = false;
1324     }
1325     if (Style.Standard == FormatStyle::LS_Auto) {
1326       Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
1327                                                   : FormatStyle::LS_Cpp03;
1328     }
1329     BinPackInconclusiveFunctions =
1330         HasBinPackedFunction || !HasOnePerLineFunction;
1331   }
1332
1333   virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
1334     assert(!UnwrappedLines.empty());
1335     UnwrappedLines.back().push_back(TheLine);
1336   }
1337
1338   virtual void finishRun() {
1339     UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
1340   }
1341
1342   FormatStyle Style;
1343   Lexer &Lex;
1344   SourceManager &SourceMgr;
1345   WhitespaceManager Whitespaces;
1346   SmallVector<CharSourceRange, 8> Ranges;
1347   SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
1348
1349   encoding::Encoding Encoding;
1350   bool BinPackInconclusiveFunctions;
1351 };
1352
1353 } // end anonymous namespace
1354
1355 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1356                                SourceManager &SourceMgr,
1357                                std::vector<CharSourceRange> Ranges) {
1358   Formatter formatter(Style, Lex, SourceMgr, Ranges);
1359   return formatter.format();
1360 }
1361
1362 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1363                                std::vector<tooling::Range> Ranges,
1364                                StringRef FileName) {
1365   FileManager Files((FileSystemOptions()));
1366   DiagnosticsEngine Diagnostics(
1367       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1368       new DiagnosticOptions);
1369   SourceManager SourceMgr(Diagnostics, Files);
1370   llvm::MemoryBuffer *Buf = llvm::MemoryBuffer::getMemBuffer(Code, FileName);
1371   const clang::FileEntry *Entry =
1372       Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
1373   SourceMgr.overrideFileContents(Entry, Buf);
1374   FileID ID =
1375       SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
1376   Lexer Lex(ID, SourceMgr.getBuffer(ID), SourceMgr,
1377             getFormattingLangOpts(Style.Standard));
1378   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1379   std::vector<CharSourceRange> CharRanges;
1380   for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1381     SourceLocation Start = StartOfFile.getLocWithOffset(Ranges[i].getOffset());
1382     SourceLocation End = Start.getLocWithOffset(Ranges[i].getLength());
1383     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1384   }
1385   return reformat(Style, Lex, SourceMgr, CharRanges);
1386 }
1387
1388 LangOptions getFormattingLangOpts(FormatStyle::LanguageStandard Standard) {
1389   LangOptions LangOpts;
1390   LangOpts.CPlusPlus = 1;
1391   LangOpts.CPlusPlus11 = Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1392   LangOpts.LineComment = 1;
1393   LangOpts.Bool = 1;
1394   LangOpts.ObjC1 = 1;
1395   LangOpts.ObjC2 = 1;
1396   return LangOpts;
1397 }
1398
1399 const char *StyleOptionHelpDescription =
1400     "Coding style, currently supports:\n"
1401     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1402     "Use -style=file to load style configuration from\n"
1403     ".clang-format file located in one of the parent\n"
1404     "directories of the source file (or current\n"
1405     "directory for stdin).\n"
1406     "Use -style=\"{key: value, ...}\" to set specific\n"
1407     "parameters, e.g.:\n"
1408     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1409
1410 FormatStyle getStyle(StringRef StyleName, StringRef FileName) {
1411   // Fallback style in case the rest of this function can't determine a style.
1412   StringRef FallbackStyle = "LLVM";
1413   FormatStyle Style;
1414   getPredefinedStyle(FallbackStyle, &Style);
1415
1416   if (StyleName.startswith("{")) {
1417     // Parse YAML/JSON style from the command line.
1418     if (llvm::error_code ec = parseConfiguration(StyleName, &Style)) {
1419       llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
1420                    << FallbackStyle << " style\n";
1421     }
1422     return Style;
1423   }
1424
1425   if (!StyleName.equals_lower("file")) {
1426     if (!getPredefinedStyle(StyleName, &Style))
1427       llvm::errs() << "Invalid value for -style, using " << FallbackStyle
1428                    << " style\n";
1429     return Style;
1430   }
1431
1432   SmallString<128> Path(FileName);
1433   llvm::sys::fs::make_absolute(Path);
1434   for (StringRef Directory = Path; !Directory.empty();
1435        Directory = llvm::sys::path::parent_path(Directory)) {
1436     if (!llvm::sys::fs::is_directory(Directory))
1437       continue;
1438     SmallString<128> ConfigFile(Directory);
1439
1440     llvm::sys::path::append(ConfigFile, ".clang-format");
1441     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1442     bool IsFile = false;
1443     // Ignore errors from is_regular_file: we only need to know if we can read
1444     // the file or not.
1445     llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1446
1447     if (!IsFile) {
1448       // Try _clang-format too, since dotfiles are not commonly used on Windows.
1449       ConfigFile = Directory;
1450       llvm::sys::path::append(ConfigFile, "_clang-format");
1451       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1452       llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1453     }
1454
1455     if (IsFile) {
1456       OwningPtr<llvm::MemoryBuffer> Text;
1457       if (llvm::error_code ec =
1458               llvm::MemoryBuffer::getFile(ConfigFile.c_str(), Text)) {
1459         llvm::errs() << ec.message() << "\n";
1460         continue;
1461       }
1462       if (llvm::error_code ec = parseConfiguration(Text->getBuffer(), &Style)) {
1463         llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
1464                      << "\n";
1465         continue;
1466       }
1467       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
1468       return Style;
1469     }
1470   }
1471   llvm::errs() << "Can't find usable .clang-format, using " << FallbackStyle
1472                << " style\n";
1473   return Style;
1474 }
1475
1476 } // namespace format
1477 } // namespace clang