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 #include "ContinuationIndenter.h"
  17 #include "TokenAnnotator.h"
  18 #include "UnwrappedLineParser.h"
  19 #include "WhitespaceManager.h"
  20 #include "clang/Basic/Diagnostic.h"
  21 #include "clang/Basic/DiagnosticOptions.h"
  22 #include "clang/Basic/SourceManager.h"
  23 #include "clang/Format/Format.h"
  24 #include "clang/Lex/Lexer.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/Support/Allocator.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/Path.h"
  29 #include "llvm/Support/YAMLTraits.h"
  30 #include <queue>
  31 #include <string>
  32
  33 #define DEBUG_TYPE "format-formatter"
  34
  35 using clang::format::FormatStyle;
  36
  37 LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
  38
  39 namespace llvm {
  40 namespace yaml {
  41 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
  42   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
  43     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
  44     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
  45     IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
  46   }
  47 };
  48
  49 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
  50   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
  51     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
  52     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
  53     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
  54     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
  55     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
  56   }
  57 };
  58
  59 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
  60   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
  61     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
  62     IO.enumCase(Value, "false", FormatStyle::UT_Never);
  63     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
  64     IO.enumCase(Value, "true", FormatStyle::UT_Always);
  65     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
  66   }
  67 };
  68
  69 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
  70   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
  71     IO.enumCase(Value, "None", FormatStyle::SFS_None);
  72     IO.enumCase(Value, "false", FormatStyle::SFS_None);
  73     IO.enumCase(Value, "All", FormatStyle::SFS_All);
  74     IO.enumCase(Value, "true", FormatStyle::SFS_All);
  75     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
  76   }
  77 };
  78
  79 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
  80   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
  81     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
  82     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
  83     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
  84     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
  85     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
  86   }
  87 };
  88
  89 template <>
  90 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
  91   static void enumeration(IO &IO,
  92                           FormatStyle::NamespaceIndentationKind &Value) {
  93     IO.enumCase(Value, "None", FormatStyle::NI_None);
  94     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
  95     IO.enumCase(Value, "All", FormatStyle::NI_All);
  96   }
  97 };
  98
  99 template <>
 100 struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
 101   static void enumeration(IO &IO,
 102                           FormatStyle::PointerAlignmentStyle &Value) {
 103     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
 104     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
 105     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
 106
 107     // For backward compatibility.
 108     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
 109     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
 110   }
 111 };
 112
 113 template <>
 114 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
 115   static void enumeration(IO &IO,
 116                           FormatStyle::SpaceBeforeParensOptions &Value) {
 117     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
 118     IO.enumCase(Value, "ControlStatements",
 119                 FormatStyle::SBPO_ControlStatements);
 120     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
 121
 122     // For backward compatibility.
 123     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
 124     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
 125   }
 126 };
 127
 128 template <> struct MappingTraits<FormatStyle> {
 129   static void mapping(IO &IO, FormatStyle &Style) {
 130     // When reading, read the language first, we need it for getPredefinedStyle.
 131     IO.mapOptional("Language", Style.Language);
 132
 133     if (IO.outputting()) {
 134       StringRef StylesArray[] = { "LLVM",    "Google", "Chromium",
 135                                   "Mozilla", "WebKit", "GNU" };
 136       ArrayRef<StringRef> Styles(StylesArray);
 137       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
 138         StringRef StyleName(Styles[i]);
 139         FormatStyle PredefinedStyle;
 140         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
 141             Style == PredefinedStyle) {
 142           IO.mapOptional("# BasedOnStyle", StyleName);
 143           break;
 144         }
 145       }
 146     } else {
 147       StringRef BasedOnStyle;
 148       IO.mapOptional("BasedOnStyle", BasedOnStyle);
 149       if (!BasedOnStyle.empty()) {
 150         FormatStyle::LanguageKind OldLanguage = Style.Language;
 151         FormatStyle::LanguageKind Language =
 152             ((FormatStyle *)IO.getContext())->Language;
 153         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
 154           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
 155           return;
 156         }
 157         Style.Language = OldLanguage;
 158       }
 159     }
 160
 161     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
 162     IO.mapOptional("ConstructorInitializerIndentWidth",
 163                    Style.ConstructorInitializerIndentWidth);
 164     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
 165     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
 166     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
 167                    Style.AllowAllParametersOfDeclarationOnNextLine);
 168     IO.mapOptional("AllowShortBlocksOnASingleLine",
 169                    Style.AllowShortBlocksOnASingleLine);
 170     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
 171                    Style.AllowShortIfStatementsOnASingleLine);
 172     IO.mapOptional("AllowShortLoopsOnASingleLine",
 173                    Style.AllowShortLoopsOnASingleLine);
 174     IO.mapOptional("AllowShortFunctionsOnASingleLine",
 175                    Style.AllowShortFunctionsOnASingleLine);
 176     IO.mapOptional("AlwaysBreakTemplateDeclarations",
 177                    Style.AlwaysBreakTemplateDeclarations);
 178     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
 179                    Style.AlwaysBreakBeforeMultilineStrings);
 180     IO.mapOptional("BreakBeforeBinaryOperators",
 181                    Style.BreakBeforeBinaryOperators);
 182     IO.mapOptional("BreakBeforeTernaryOperators",
 183                    Style.BreakBeforeTernaryOperators);
 184     IO.mapOptional("BreakConstructorInitializersBeforeComma",
 185                    Style.BreakConstructorInitializersBeforeComma);
 186     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
 187     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
 188     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
 189                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
 190     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
 191     IO.mapOptional("ExperimentalAutoDetectBinPacking",
 192                    Style.ExperimentalAutoDetectBinPacking);
 193     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
 194     IO.mapOptional("IndentWrappedFunctionNames",
 195                    Style.IndentWrappedFunctionNames);
 196     IO.mapOptional("IndentFunctionDeclarationAfterType",
 197                    Style.IndentWrappedFunctionNames);
 198     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
 199     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
 200                    Style.KeepEmptyLinesAtTheStartOfBlocks);
 201     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
 202     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
 203     IO.mapOptional("ObjCSpaceBeforeProtocolList",
 204                    Style.ObjCSpaceBeforeProtocolList);
 205     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
 206                    Style.PenaltyBreakBeforeFirstCallParameter);
 207     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
 208     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
 209     IO.mapOptional("PenaltyBreakFirstLessLess",
 210                    Style.PenaltyBreakFirstLessLess);
 211     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
 212     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
 213                    Style.PenaltyReturnTypeOnItsOwnLine);
 214     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
 215     IO.mapOptional("SpacesBeforeTrailingComments",
 216                    Style.SpacesBeforeTrailingComments);
 217     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
 218     IO.mapOptional("Standard", Style.Standard);
 219     IO.mapOptional("IndentWidth", Style.IndentWidth);
 220     IO.mapOptional("TabWidth", Style.TabWidth);
 221     IO.mapOptional("UseTab", Style.UseTab);
 222     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
 223     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
 224     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
 225     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
 226     IO.mapOptional("SpacesInCStyleCastParentheses",
 227                    Style.SpacesInCStyleCastParentheses);
 228     IO.mapOptional("SpacesInContainerLiterals",
 229                    Style.SpacesInContainerLiterals);
 230     IO.mapOptional("SpaceBeforeAssignmentOperators",
 231                    Style.SpaceBeforeAssignmentOperators);
 232     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
 233     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
 234     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
 235
 236     // For backward compatibility.
 237     if (!IO.outputting()) {
 238       IO.mapOptional("SpaceAfterControlStatementKeyword",
 239                      Style.SpaceBeforeParens);
 240       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
 241       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
 242     }
 243     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
 244     IO.mapOptional("DisableFormat", Style.DisableFormat);
 245   }
 246 };
 247
 248 // Allows to read vector<FormatStyle> while keeping default values.
 249 // IO.getContext() should contain a pointer to the FormatStyle structure, that
 250 // will be used to get default values for missing keys.
 251 // If the first element has no Language specified, it will be treated as the
 252 // default one for the following elements.
 253 template <> struct DocumentListTraits<std::vector<FormatStyle> > {
 254   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
 255     return Seq.size();
 256   }
 257   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
 258                               size_t Index) {
 259     if (Index >= Seq.size()) {
 260       assert(Index == Seq.size());
 261       FormatStyle Template;
 262       if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
 263         Template = Seq[0];
 264       } else {
 265         Template = *((const FormatStyle *)IO.getContext());
 266         Template.Language = FormatStyle::LK_None;
 267       }
 268       Seq.resize(Index + 1, Template);
 269     }
 270     return Seq[Index];
 271   }
 272 };
 273 }
 274 }
 275
 276 namespace clang {
 277 namespace format {
 278
 279 const std::error_category &getParseCategory() {
 280   static ParseErrorCategory C;
 281   return C;
 282 }
 283 std::error_code make_error_code(ParseError e) {
 284   return std::error_code(static_cast<int>(e), getParseCategory());
 285 }
 286
 287 const char *ParseErrorCategory::name() const LLVM_NOEXCEPT {
 288   return "clang-format.parse_error";
 289 }
 290
 291 std::string ParseErrorCategory::message(int EV) const {
 292   switch (static_cast<ParseError>(EV)) {
 293   case ParseError::Success:
 294     return "Success";
 295   case ParseError::Error:
 296     return "Invalid argument";
 297   case ParseError::Unsuitable:
 298     return "Unsuitable";
 299   }
 300   llvm_unreachable("unexpected parse error");
 301 }
 302
 303 FormatStyle getLLVMStyle() {
 304   FormatStyle LLVMStyle;
 305   LLVMStyle.Language = FormatStyle::LK_Cpp;
 306   LLVMStyle.AccessModifierOffset = -2;
 307   LLVMStyle.AlignEscapedNewlinesLeft = false;
 308   LLVMStyle.AlignTrailingComments = true;
 309   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
 310   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
 311   LLVMStyle.AllowShortBlocksOnASingleLine = false;
 312   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
 313   LLVMStyle.AllowShortLoopsOnASingleLine = false;
 314   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
 315   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
 316   LLVMStyle.BinPackParameters = true;
 317   LLVMStyle.BreakBeforeBinaryOperators = false;
 318   LLVMStyle.BreakBeforeTernaryOperators = true;
 319   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
 320   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
 321   LLVMStyle.ColumnLimit = 80;
 322   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
 323   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
 324   LLVMStyle.ConstructorInitializerIndentWidth = 4;
 325   LLVMStyle.ContinuationIndentWidth = 4;
 326   LLVMStyle.Cpp11BracedListStyle = true;
 327   LLVMStyle.DerivePointerAlignment = false;
 328   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
 329   LLVMStyle.ForEachMacros.push_back("foreach");
 330   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
 331   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
 332   LLVMStyle.IndentCaseLabels = false;
 333   LLVMStyle.IndentWrappedFunctionNames = false;
 334   LLVMStyle.IndentWidth = 2;
 335   LLVMStyle.TabWidth = 8;
 336   LLVMStyle.MaxEmptyLinesToKeep = 1;
 337   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
 338   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
 339   LLVMStyle.ObjCSpaceAfterProperty = false;
 340   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
 341   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
 342   LLVMStyle.SpacesBeforeTrailingComments = 1;
 343   LLVMStyle.Standard = FormatStyle::LS_Cpp11;
 344   LLVMStyle.UseTab = FormatStyle::UT_Never;
 345   LLVMStyle.SpacesInParentheses = false;
 346   LLVMStyle.SpaceInEmptyParentheses = false;
 347   LLVMStyle.SpacesInContainerLiterals = true;
 348   LLVMStyle.SpacesInCStyleCastParentheses = false;
 349   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
 350   LLVMStyle.SpaceBeforeAssignmentOperators = true;
 351   LLVMStyle.SpacesInAngles = false;
 352
 353   LLVMStyle.PenaltyBreakComment = 300;
 354   LLVMStyle.PenaltyBreakFirstLessLess = 120;
 355   LLVMStyle.PenaltyBreakString = 1000;
 356   LLVMStyle.PenaltyExcessCharacter = 1000000;
 357   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
 358   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
 359
 360   LLVMStyle.DisableFormat = false;
 361
 362   return LLVMStyle;
 363 }
 364
 365 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
 366   FormatStyle GoogleStyle = getLLVMStyle();
 367   GoogleStyle.Language = Language;
 368
 369   GoogleStyle.AccessModifierOffset = -1;
 370   GoogleStyle.AlignEscapedNewlinesLeft = true;
 371   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
 372   GoogleStyle.AllowShortLoopsOnASingleLine = true;
 373   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
 374   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
 375   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
 376   GoogleStyle.DerivePointerAlignment = true;
 377   GoogleStyle.IndentCaseLabels = true;
 378   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
 379   GoogleStyle.ObjCSpaceAfterProperty = false;
 380   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
 381   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
 382   GoogleStyle.SpacesBeforeTrailingComments = 2;
 383   GoogleStyle.Standard = FormatStyle::LS_Auto;
 384
 385   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
 386   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
 387
 388   if (Language == FormatStyle::LK_JavaScript) {
 389     GoogleStyle.BreakBeforeTernaryOperators = false;
 390     GoogleStyle.MaxEmptyLinesToKeep = 3;
 391     GoogleStyle.SpacesInContainerLiterals = false;
 392   } else if (Language == FormatStyle::LK_Proto) {
 393     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
 394     GoogleStyle.SpacesInContainerLiterals = false;
 395   }
 396
 397   return GoogleStyle;
 398 }
 399
 400 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
 401   FormatStyle ChromiumStyle = getGoogleStyle(Language);
 402   ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
 403   ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
 404   ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
 405   ChromiumStyle.AllowShortLoopsOnASingleLine = false;
 406   ChromiumStyle.BinPackParameters = false;
 407   ChromiumStyle.DerivePointerAlignment = false;
 408   ChromiumStyle.Standard = FormatStyle::LS_Cpp03;
 409   return ChromiumStyle;
 410 }
 411
 412 FormatStyle getMozillaStyle() {
 413   FormatStyle MozillaStyle = getLLVMStyle();
 414   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
 415   MozillaStyle.Cpp11BracedListStyle = false;
 416   MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
 417   MozillaStyle.DerivePointerAlignment = true;
 418   MozillaStyle.IndentCaseLabels = true;
 419   MozillaStyle.ObjCSpaceAfterProperty = true;
 420   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
 421   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
 422   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
 423   MozillaStyle.Standard = FormatStyle::LS_Cpp03;
 424   return MozillaStyle;
 425 }
 426
 427 FormatStyle getWebKitStyle() {
 428   FormatStyle Style = getLLVMStyle();
 429   Style.AccessModifierOffset = -4;
 430   Style.AlignTrailingComments = false;
 431   Style.BreakBeforeBinaryOperators = true;
 432   Style.BreakBeforeBraces = FormatStyle::BS_Stroustrup;
 433   Style.BreakConstructorInitializersBeforeComma = true;
 434   Style.Cpp11BracedListStyle = false;
 435   Style.ColumnLimit = 0;
 436   Style.IndentWidth = 4;
 437   Style.NamespaceIndentation = FormatStyle::NI_Inner;
 438   Style.ObjCSpaceAfterProperty = true;
 439   Style.PointerAlignment = FormatStyle::PAS_Left;
 440   Style.Standard = FormatStyle::LS_Cpp03;
 441   return Style;
 442 }
 443
 444 FormatStyle getGNUStyle() {
 445   FormatStyle Style = getLLVMStyle();
 446   Style.BreakBeforeBinaryOperators = true;
 447   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
 448   Style.BreakBeforeTernaryOperators = true;
 449   Style.Cpp11BracedListStyle = false;
 450   Style.ColumnLimit = 79;
 451   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
 452   Style.Standard = FormatStyle::LS_Cpp03;
 453   return Style;
 454 }
 455
 456 FormatStyle getNoStyle() {
 457   FormatStyle NoStyle = getLLVMStyle();
 458   NoStyle.DisableFormat = true;
 459   return NoStyle;
 460 }
 461
 462 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
 463                         FormatStyle *Style) {
 464   if (Name.equals_lower("llvm")) {
 465     *Style = getLLVMStyle();
 466   } else if (Name.equals_lower("chromium")) {
 467     *Style = getChromiumStyle(Language);
 468   } else if (Name.equals_lower("mozilla")) {
 469     *Style = getMozillaStyle();
 470   } else if (Name.equals_lower("google")) {
 471     *Style = getGoogleStyle(Language);
 472   } else if (Name.equals_lower("webkit")) {
 473     *Style = getWebKitStyle();
 474   } else if (Name.equals_lower("gnu")) {
 475     *Style = getGNUStyle();
 476   } else if (Name.equals_lower("none")) {
 477     *Style = getNoStyle();
 478   } else {
 479     return false;
 480   }
 481
 482   Style->Language = Language;
 483   return true;
 484 }
 485
 486 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
 487   assert(Style);
 488   FormatStyle::LanguageKind Language = Style->Language;
 489   assert(Language != FormatStyle::LK_None);
 490   if (Text.trim().empty())
 491     return make_error_code(ParseError::Error);
 492
 493   std::vector<FormatStyle> Styles;
 494   llvm::yaml::Input Input(Text);
 495   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
 496   // values for the fields, keys for which are missing from the configuration.
 497   // Mapping also uses the context to get the language to find the correct
 498   // base style.
 499   Input.setContext(Style);
 500   Input >> Styles;
 501   if (Input.error())
 502     return Input.error();
 503
 504   for (unsigned i = 0; i < Styles.size(); ++i) {
 505     // Ensures that only the first configuration can skip the Language option.
 506     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
 507       return make_error_code(ParseError::Error);
 508     // Ensure that each language is configured at most once.
 509     for (unsigned j = 0; j < i; ++j) {
 510       if (Styles[i].Language == Styles[j].Language) {
 511         DEBUG(llvm::dbgs()
 512               << "Duplicate languages in the config file on positions " << j
 513               << " and " << i << "\n");
 514         return make_error_code(ParseError::Error);
 515       }
 516     }
 517   }
 518   // Look for a suitable configuration starting from the end, so we can
 519   // find the configuration for the specific language first, and the default
 520   // configuration (which can only be at slot 0) after it.
 521   for (int i = Styles.size() - 1; i >= 0; --i) {
 522     if (Styles[i].Language == Language ||
 523         Styles[i].Language == FormatStyle::LK_None) {
 524       *Style = Styles[i];
 525       Style->Language = Language;
 526       return make_error_code(ParseError::Success);
 527     }
 528   }
 529   return make_error_code(ParseError::Unsuitable);
 530 }
 531
 532 std::string configurationAsText(const FormatStyle &Style) {
 533   std::string Text;
 534   llvm::raw_string_ostream Stream(Text);
 535   llvm::yaml::Output Output(Stream);
 536   // We use the same mapping method for input and output, so we need a non-const
 537   // reference here.
 538   FormatStyle NonConstStyle = Style;
 539   Output << NonConstStyle;
 540   return Stream.str();
 541 }
 542
 543 namespace {
 544
 545 class NoColumnLimitFormatter {
 546 public:
 547   NoColumnLimitFormatter(ContinuationIndenter *Indenter) : Indenter(Indenter) {}
 548
 549   /// \brief Formats the line starting at \p State, simply keeping all of the
 550   /// input's line breaking decisions.
 551   void format(unsigned FirstIndent, const AnnotatedLine *Line) {
 552     LineState State =
 553         Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false);
 554     while (State.NextToken) {
 555       bool Newline =
 556           Indenter->mustBreak(State) ||
 557           (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
 558       Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
 559     }
 560   }
 561
 562 private:
 563   ContinuationIndenter *Indenter;
 564 };
 565
 566 class LineJoiner {
 567 public:
 568   LineJoiner(const FormatStyle &Style) : Style(Style) {}
 569
 570   /// \brief Calculates how many lines can be merged into 1 starting at \p I.
 571   unsigned
 572   tryFitMultipleLinesInOne(unsigned Indent,
 573                            SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 574                            SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
 575     // We can never merge stuff if there are trailing line comments.
 576     const AnnotatedLine *TheLine = *I;
 577     if (TheLine->Last->Type == TT_LineComment)
 578       return 0;
 579
 580     if (Style.ColumnLimit > 0 && Indent > Style.ColumnLimit)
 581       return 0;
 582
 583     unsigned Limit =
 584         Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;
 585     // If we already exceed the column limit, we set 'Limit' to 0. The different
 586     // tryMerge..() functions can then decide whether to still do merging.
 587     Limit = TheLine->Last->TotalLength > Limit
 588                 ? 0
 589                 : Limit - TheLine->Last->TotalLength;
 590
 591     if (I + 1 == E || I[1]->Type == LT_Invalid || I[1]->First->MustBreakBefore)
 592       return 0;
 593
 594     // FIXME: TheLine->Level != 0 might or might not be the right check to do.
 595     // If necessary, change to something smarter.
 596     bool MergeShortFunctions =
 597         Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All ||
 598         (Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_Inline &&
 599          TheLine->Level != 0);
 600
 601     if (TheLine->Last->Type == TT_FunctionLBrace &&
 602         TheLine->First != TheLine->Last) {
 603       return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0;
 604     }
 605     if (TheLine->Last->is(tok::l_brace)) {
 606       return Style.BreakBeforeBraces == FormatStyle::BS_Attach
 607                  ? tryMergeSimpleBlock(I, E, Limit)
 608                  : 0;
 609     }
 610     if (I[1]->First->Type == TT_FunctionLBrace &&
 611         Style.BreakBeforeBraces != FormatStyle::BS_Attach) {
 612       // Check for Limit <= 2 to account for the " {".
 613       if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine)))
 614         return 0;
 615       Limit -= 2;
 616
 617       unsigned MergedLines = 0;
 618       if (MergeShortFunctions) {
 619         MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
 620         // If we managed to merge the block, count the function header, which is
 621         // on a separate line.
 622         if (MergedLines > 0)
 623           ++MergedLines;
 624       }
 625       return MergedLines;
 626     }
 627     if (TheLine->First->is(tok::kw_if)) {
 628       return Style.AllowShortIfStatementsOnASingleLine
 629                  ? tryMergeSimpleControlStatement(I, E, Limit)
 630                  : 0;
 631     }
 632     if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
 633       return Style.AllowShortLoopsOnASingleLine
 634                  ? tryMergeSimpleControlStatement(I, E, Limit)
 635                  : 0;
 636     }
 637     if (TheLine->InPPDirective &&
 638         (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
 639       return tryMergeSimplePPDirective(I, E, Limit);
 640     }
 641     return 0;
 642   }
 643
 644 private:
 645   unsigned
 646   tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 647                             SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 648                             unsigned Limit) {
 649     if (Limit == 0)
 650       return 0;
 651     if (!I[1]->InPPDirective || I[1]->First->HasUnescapedNewline)
 652       return 0;
 653     if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
 654       return 0;
 655     if (1 + I[1]->Last->TotalLength > Limit)
 656       return 0;
 657     return 1;
 658   }
 659
 660   unsigned tryMergeSimpleControlStatement(
 661       SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 662       SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
 663     if (Limit == 0)
 664       return 0;
 665     if ((Style.BreakBeforeBraces == FormatStyle::BS_Allman ||
 666          Style.BreakBeforeBraces == FormatStyle::BS_GNU) &&
 667         (I[1]->First->is(tok::l_brace) && !Style.AllowShortBlocksOnASingleLine))
 668       return 0;
 669     if (I[1]->InPPDirective != (*I)->InPPDirective ||
 670         (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline))
 671       return 0;
 672     Limit = limitConsideringMacros(I + 1, E, Limit);
 673     AnnotatedLine &Line = **I;
 674     if (Line.Last->isNot(tok::r_paren))
 675       return 0;
 676     if (1 + I[1]->Last->TotalLength > Limit)
 677       return 0;
 678     if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
 679                              tok::kw_while) ||
 680         I[1]->First->Type == TT_LineComment)
 681       return 0;
 682     // Only inline simple if's (no nested if or else).
 683     if (I + 2 != E && Line.First->is(tok::kw_if) &&
 684         I[2]->First->is(tok::kw_else))
 685       return 0;
 686     return 1;
 687   }
 688
 689   unsigned
 690   tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 691                       SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 692                       unsigned Limit) {
 693     AnnotatedLine &Line = **I;
 694
 695     // Don't merge ObjC @ keywords and methods.
 696     if (Line.First->isOneOf(tok::at, tok::minus, tok::plus))
 697       return 0;
 698
 699     // Check that the current line allows merging. This depends on whether we
 700     // are in a control flow statements as well as several style flags.
 701     if (Line.First->isOneOf(tok::kw_else, tok::kw_case))
 702       return 0;
 703     if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::kw_try,
 704                             tok::kw_catch, tok::kw_for, tok::r_brace)) {
 705       if (!Style.AllowShortBlocksOnASingleLine)
 706         return 0;
 707       if (!Style.AllowShortIfStatementsOnASingleLine &&
 708           Line.First->is(tok::kw_if))
 709         return 0;
 710       if (!Style.AllowShortLoopsOnASingleLine &&
 711           Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for))
 712         return 0;
 713       // FIXME: Consider an option to allow short exception handling clauses on
 714       // a single line.
 715       if (Line.First->isOneOf(tok::kw_try, tok::kw_catch))
 716         return 0;
 717     }
 718
 719     FormatToken *Tok = I[1]->First;
 720     if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
 721         (Tok->getNextNonComment() == nullptr ||
 722          Tok->getNextNonComment()->is(tok::semi))) {
 723       // We merge empty blocks even if the line exceeds the column limit.
 724       Tok->SpacesRequiredBefore = 0;
 725       Tok->CanBreakBefore = true;
 726       return 1;
 727     } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace)) {
 728       // We don't merge short records.
 729       if (Line.First->isOneOf(tok::kw_class, tok::kw_union, tok::kw_struct))
 730         return 0;
 731
 732       // Check that we still have three lines and they fit into the limit.
 733       if (I + 2 == E || I[2]->Type == LT_Invalid)
 734         return 0;
 735       Limit = limitConsideringMacros(I + 2, E, Limit);
 736
 737       if (!nextTwoLinesFitInto(I, Limit))
 738         return 0;
 739
 740       // Second, check that the next line does not contain any braces - if it
 741       // does, readability declines when putting it into a single line.
 742       if (I[1]->Last->Type == TT_LineComment)
 743         return 0;
 744       do {
 745         if (Tok->is(tok::l_brace) && Tok->BlockKind != BK_BracedInit)
 746           return 0;
 747         Tok = Tok->Next;
 748       } while (Tok);
 749
 750       // Last, check that the third line starts with a closing brace.
 751       Tok = I[2]->First;
 752       if (Tok->isNot(tok::r_brace))
 753         return 0;
 754
 755       return 2;
 756     }
 757     return 0;
 758   }
 759
 760   /// Returns the modified column limit for \p I if it is inside a macro and
 761   /// needs a trailing '\'.
 762   unsigned
 763   limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 764                          SmallVectorImpl<AnnotatedLine *>::const_iterator E,
 765                          unsigned Limit) {
 766     if (I[0]->InPPDirective && I + 1 != E &&
 767         !I[1]->First->HasUnescapedNewline && !I[1]->First->is(tok::eof)) {
 768       return Limit < 2 ? 0 : Limit - 2;
 769     }
 770     return Limit;
 771   }
 772
 773   bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
 774                            unsigned Limit) {
 775     if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)
 776       return false;
 777     return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
 778   }
 779
 780   bool containsMustBreak(const AnnotatedLine *Line) {
 781     for (const FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
 782       if (Tok->MustBreakBefore)
 783         return true;
 784     }
 785     return false;
 786   }
 787
 788   const FormatStyle &Style;
 789 };
 790
 791 class UnwrappedLineFormatter {
 792 public:
 793   UnwrappedLineFormatter(ContinuationIndenter *Indenter,
 794                          WhitespaceManager *Whitespaces,
 795                          const FormatStyle &Style)
 796       : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style),
 797         Joiner(Style) {}
 798
 799   unsigned format(const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun,
 800                   int AdditionalIndent = 0, bool FixBadIndentation = false) {
 801     // Try to look up already computed penalty in DryRun-mode.
 802     std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey(
 803         &Lines, AdditionalIndent);
 804     auto CacheIt = PenaltyCache.find(CacheKey);
 805     if (DryRun && CacheIt != PenaltyCache.end())
 806       return CacheIt->second;
 807
 808     assert(!Lines.empty());
 809     unsigned Penalty = 0;
 810     std::vector<int> IndentForLevel;
 811     for (unsigned i = 0, e = Lines[0]->Level; i != e; ++i)
 812       IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);
 813     const AnnotatedLine *PreviousLine = nullptr;
 814     for (SmallVectorImpl<AnnotatedLine *>::const_iterator I = Lines.begin(),
 815                                                           E = Lines.end();
 816          I != E; ++I) {
 817       const AnnotatedLine &TheLine = **I;
 818       const FormatToken *FirstTok = TheLine.First;
 819       int Offset = getIndentOffset(*FirstTok);
 820
 821       // Determine indent and try to merge multiple unwrapped lines.
 822       unsigned Indent;
 823       if (TheLine.InPPDirective) {
 824         Indent = TheLine.Level * Style.IndentWidth;
 825       } else {
 826         while (IndentForLevel.size() <= TheLine.Level)
 827           IndentForLevel.push_back(-1);
 828         IndentForLevel.resize(TheLine.Level + 1);
 829         Indent = getIndent(IndentForLevel, TheLine.Level);
 830       }
 831       unsigned LevelIndent = Indent;
 832       if (static_cast<int>(Indent) + Offset >= 0)
 833         Indent += Offset;
 834
 835       // Merge multiple lines if possible.
 836       unsigned MergedLines = Joiner.tryFitMultipleLinesInOne(Indent, I, E);
 837       if (MergedLines > 0 && Style.ColumnLimit == 0) {
 838         // Disallow line merging if there is a break at the start of one of the
 839         // input lines.
 840         for (unsigned i = 0; i < MergedLines; ++i) {
 841           if (I[i + 1]->First->NewlinesBefore > 0)
 842             MergedLines = 0;
 843         }
 844       }
 845       if (!DryRun) {
 846         for (unsigned i = 0; i < MergedLines; ++i) {
 847           join(*I[i], *I[i + 1]);
 848         }
 849       }
 850       I += MergedLines;
 851
 852       bool FixIndentation =
 853           FixBadIndentation && (LevelIndent != FirstTok->OriginalColumn);
 854       if (TheLine.First->is(tok::eof)) {
 855         if (PreviousLine && PreviousLine->Affected && !DryRun) {
 856           // Remove the file's trailing whitespace.
 857           unsigned Newlines = std::min(FirstTok->NewlinesBefore, 1u);
 858           Whitespaces->replaceWhitespace(*TheLine.First, Newlines,
 859                                          /*IndentLevel=*/0, /*Spaces=*/0,
 860                                          /*TargetColumn=*/0);
 861         }
 862       } else if (TheLine.Type != LT_Invalid &&
 863                  (TheLine.Affected || FixIndentation)) {
 864         if (FirstTok->WhitespaceRange.isValid()) {
 865           if (!DryRun)
 866             formatFirstToken(*TheLine.First, PreviousLine, TheLine.Level,
 867                              Indent, TheLine.InPPDirective);
 868         } else {
 869           Indent = LevelIndent = FirstTok->OriginalColumn;
 870         }
 871
 872         // If everything fits on a single line, just put it there.
 873         unsigned ColumnLimit = Style.ColumnLimit;
 874         if (I + 1 != E) {
 875           AnnotatedLine *NextLine = I[1];
 876           if (NextLine->InPPDirective && !NextLine->First->HasUnescapedNewline)
 877             ColumnLimit = getColumnLimit(TheLine.InPPDirective);
 878         }
 879
 880         if (TheLine.Last->TotalLength + Indent <= ColumnLimit) {
 881           LineState State = Indenter->getInitialState(Indent, &TheLine, DryRun);
 882           while (State.NextToken) {
 883             formatChildren(State, /*Newline=*/false, /*DryRun=*/false, Penalty);
 884             Indenter->addTokenToState(State, /*Newline=*/false, DryRun);
 885           }
 886         } else if (Style.ColumnLimit == 0) {
 887           // FIXME: Implement nested blocks for ColumnLimit = 0.
 888           NoColumnLimitFormatter Formatter(Indenter);
 889           if (!DryRun)
 890             Formatter.format(Indent, &TheLine);
 891         } else {
 892           Penalty += format(TheLine, Indent, DryRun);
 893         }
 894
 895         if (!TheLine.InPPDirective)
 896           IndentForLevel[TheLine.Level] = LevelIndent;
 897       } else if (TheLine.ChildrenAffected) {
 898         format(TheLine.Children, DryRun);
 899       } else {
 900         // Format the first token if necessary, and notify the WhitespaceManager
 901         // about the unchanged whitespace.
 902         for (FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next) {
 903           if (Tok == TheLine.First &&
 904               (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
 905             unsigned LevelIndent = Tok->OriginalColumn;
 906             if (!DryRun) {
 907               // Remove trailing whitespace of the previous line.
 908               if ((PreviousLine && PreviousLine->Affected) ||
 909                   TheLine.LeadingEmptyLinesAffected) {
 910                 formatFirstToken(*Tok, PreviousLine, TheLine.Level, LevelIndent,
 911                                  TheLine.InPPDirective);
 912               } else {
 913                 Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
 914               }
 915             }
 916
 917             if (static_cast<int>(LevelIndent) - Offset >= 0)
 918               LevelIndent -= Offset;
 919             if (Tok->isNot(tok::comment) && !TheLine.InPPDirective)
 920               IndentForLevel[TheLine.Level] = LevelIndent;
 921           } else if (!DryRun) {
 922             Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
 923           }
 924         }
 925       }
 926       if (!DryRun) {
 927         for (FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next) {
 928           Tok->Finalized = true;
 929         }
 930       }
 931       PreviousLine = *I;
 932     }
 933     PenaltyCache[CacheKey] = Penalty;
 934     return Penalty;
 935   }
 936
 937 private:
 938   /// \brief Formats an \c AnnotatedLine and returns the penalty.
 939   ///
 940   /// If \p DryRun is \c false, directly applies the changes.
 941   unsigned format(const AnnotatedLine &Line, unsigned FirstIndent,
 942                   bool DryRun) {
 943     LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun);
 944
 945     // If the ObjC method declaration does not fit on a line, we should format
 946     // it with one arg per line.
 947     if (State.Line->Type == LT_ObjCMethodDecl)
 948       State.Stack.back().BreakBeforeParameter = true;
 949
 950     // Find best solution in solution space.
 951     return analyzeSolutionSpace(State, DryRun);
 952   }
 953
 954   /// \brief An edge in the solution space from \c Previous->State to \c State,
 955   /// inserting a newline dependent on the \c NewLine.
 956   struct StateNode {
 957     StateNode(const LineState &State, bool NewLine, StateNode *Previous)
 958         : State(State), NewLine(NewLine), Previous(Previous) {}
 959     LineState State;
 960     bool NewLine;
 961     StateNode *Previous;
 962   };
 963
 964   /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
 965   ///
 966   /// In case of equal penalties, we want to prefer states that were inserted
 967   /// first. During state generation we make sure that we insert states first
 968   /// that break the line as late as possible.
 969   typedef std::pair<unsigned, unsigned> OrderedPenalty;
 970
 971   /// \brief An item in the prioritized BFS search queue. The \c StateNode's
 972   /// \c State has the given \c OrderedPenalty.
 973   typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
 974
 975   /// \brief The BFS queue type.
 976   typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
 977                               std::greater<QueueItem> > QueueType;
 978
 979   /// \brief Get the offset of the line relatively to the level.
 980   ///
 981   /// For example, 'public:' labels in classes are offset by 1 or 2
 982   /// characters to the left from their level.
 983   int getIndentOffset(const FormatToken &RootToken) {
 984     if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
 985       return Style.AccessModifierOffset;
 986     return 0;
 987   }
 988
 989   /// \brief Add a new line and the required indent before the first Token
 990   /// of the \c UnwrappedLine if there was no structural parsing error.
 991   void formatFirstToken(FormatToken &RootToken,
 992                         const AnnotatedLine *PreviousLine, unsigned IndentLevel,
 993                         unsigned Indent, bool InPPDirective) {
 994     unsigned Newlines =
 995         std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
 996     // Remove empty lines before "}" where applicable.
 997     if (RootToken.is(tok::r_brace) &&
 998         (!RootToken.Next ||
 999          (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
1000       Newlines = std::min(Newlines, 1u);
1001     if (Newlines == 0 && !RootToken.IsFirst)
1002       Newlines = 1;
1003     if (RootToken.IsFirst && !RootToken.HasUnescapedNewline)
1004       Newlines = 0;
1005
1006     // Remove empty lines after "{".
1007     if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine &&
1008         PreviousLine->Last->is(tok::l_brace) &&
1009         PreviousLine->First->isNot(tok::kw_namespace))
1010       Newlines = 1;
1011
1012     // Insert extra new line before access specifiers.
1013     if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
1014         RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
1015       ++Newlines;
1016
1017     // Remove empty lines after access specifiers.
1018     if (PreviousLine && PreviousLine->First->isAccessSpecifier())
1019       Newlines = std::min(1u, Newlines);
1020
1021     Whitespaces->replaceWhitespace(RootToken, Newlines, IndentLevel, Indent,
1022                                    Indent, InPPDirective &&
1023                                                !RootToken.HasUnescapedNewline);
1024   }
1025
1026   /// \brief Get the indent of \p Level from \p IndentForLevel.
1027   ///
1028   /// \p IndentForLevel must contain the indent for the level \c l
1029   /// at \p IndentForLevel[l], or a value < 0 if the indent for
1030   /// that level is unknown.
1031   unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
1032     if (IndentForLevel[Level] != -1)
1033       return IndentForLevel[Level];
1034     if (Level == 0)
1035       return 0;
1036     return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
1037   }
1038
1039   void join(AnnotatedLine &A, const AnnotatedLine &B) {
1040     assert(!A.Last->Next);
1041     assert(!B.First->Previous);
1042     if (B.Affected)
1043       A.Affected = true;
1044     A.Last->Next = B.First;
1045     B.First->Previous = A.Last;
1046     B.First->CanBreakBefore = true;
1047     unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
1048     for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
1049       Tok->TotalLength += LengthA;
1050       A.Last = Tok;
1051     }
1052   }
1053
1054   unsigned getColumnLimit(bool InPPDirective) const {
1055     // In preprocessor directives reserve two chars for trailing " \"
1056     return Style.ColumnLimit - (InPPDirective ? 2 : 0);
1057   }
1058
1059   struct CompareLineStatePointers {
1060     bool operator()(LineState *obj1, LineState *obj2) const {
1061       return *obj1 < *obj2;
1062     }
1063   };
1064
1065   /// \brief Analyze the entire solution space starting from \p InitialState.
1066   ///
1067   /// This implements a variant of Dijkstra's algorithm on the graph that spans
1068   /// the solution space (\c LineStates are the nodes). The algorithm tries to
1069   /// find the shortest path (the one with lowest penalty) from \p InitialState
1070   /// to a state where all tokens are placed. Returns the penalty.
1071   ///
1072   /// If \p DryRun is \c false, directly applies the changes.
1073   unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false) {
1074     std::set<LineState *, CompareLineStatePointers> Seen;
1075
1076     // Increasing count of \c StateNode items we have created. This is used to
1077     // create a deterministic order independent of the container.
1078     unsigned Count = 0;
1079     QueueType Queue;
1080
1081     // Insert start element into queue.
1082     StateNode *Node =
1083         new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);
1084     Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
1085     ++Count;
1086
1087     unsigned Penalty = 0;
1088
1089     // While not empty, take first element and follow edges.
1090     while (!Queue.empty()) {
1091       Penalty = Queue.top().first.first;
1092       StateNode *Node = Queue.top().second;
1093       if (!Node->State.NextToken) {
1094         DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
1095         break;
1096       }
1097       Queue.pop();
1098
1099       // Cut off the analysis of certain solutions if the analysis gets too
1100       // complex. See description of IgnoreStackForComparison.
1101       if (Count > 10000)
1102         Node->State.IgnoreStackForComparison = true;
1103
1104       if (!Seen.insert(&Node->State).second)
1105         // State already examined with lower penalty.
1106         continue;
1107
1108       FormatDecision LastFormat = Node->State.NextToken->Decision;
1109       if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
1110         addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
1111       if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
1112         addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
1113     }
1114
1115     if (Queue.empty()) {
1116       // We were unable to find a solution, do nothing.
1117       // FIXME: Add diagnostic?
1118       DEBUG(llvm::dbgs() << "Could not find a solution.\n");
1119       return 0;
1120     }
1121
1122     // Reconstruct the solution.
1123     if (!DryRun)
1124       reconstructPath(InitialState, Queue.top().second);
1125
1126     DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
1127     DEBUG(llvm::dbgs() << "---\n");
1128
1129     return Penalty;
1130   }
1131
1132   void reconstructPath(LineState &State, StateNode *Current) {
1133     std::deque<StateNode *> Path;
1134     // We do not need a break before the initial token.
1135     while (Current->Previous) {
1136       Path.push_front(Current);
1137       Current = Current->Previous;
1138     }
1139     for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
1140          I != E; ++I) {
1141       unsigned Penalty = 0;
1142       formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
1143       Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
1144
1145       DEBUG({
1146         if ((*I)->NewLine) {
1147           llvm::dbgs() << "Penalty for placing "
1148                        << (*I)->Previous->State.NextToken->Tok.getName() << ": "
1149                        << Penalty << "\n";
1150         }
1151       });
1152     }
1153   }
1154
1155   /// \brief Add the following state to the analysis queue \c Queue.
1156   ///
1157   /// Assume the current state is \p PreviousNode and has been reached with a
1158   /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
1159   void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
1160                            bool NewLine, unsigned *Count, QueueType *Queue) {
1161     if (NewLine && !Indenter->canBreak(PreviousNode->State))
1162       return;
1163     if (!NewLine && Indenter->mustBreak(PreviousNode->State))
1164       return;
1165
1166     StateNode *Node = new (Allocator.Allocate())
1167         StateNode(PreviousNode->State, NewLine, PreviousNode);
1168     if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
1169       return;
1170
1171     Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
1172
1173     Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
1174     ++(*Count);
1175   }
1176
1177   /// \brief If the \p State's next token is an r_brace closing a nested block,
1178   /// format the nested block before it.
1179   ///
1180   /// Returns \c true if all children could be placed successfully and adapts
1181   /// \p Penalty as well as \p State. If \p DryRun is false, also directly
1182   /// creates changes using \c Whitespaces.
1183   ///
1184   /// The crucial idea here is that children always get formatted upon
1185   /// encountering the closing brace right after the nested block. Now, if we
1186   /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
1187   /// \c false), the entire block has to be kept on the same line (which is only
1188   /// possible if it fits on the line, only contains a single statement, etc.
1189   ///
1190   /// If \p NewLine is true, we format the nested block on separate lines, i.e.
1191   /// break after the "{", format all lines with correct indentation and the put
1192   /// the closing "}" on yet another new line.
1193   ///
1194   /// This enables us to keep the simple structure of the
1195   /// \c UnwrappedLineFormatter, where we only have two options for each token:
1196   /// break or don't break.
1197   bool formatChildren(LineState &State, bool NewLine, bool DryRun,
1198                       unsigned &Penalty) {
1199     FormatToken &Previous = *State.NextToken->Previous;
1200     const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
1201     if (!LBrace || LBrace->isNot(tok::l_brace) ||
1202         LBrace->BlockKind != BK_Block || Previous.Children.size() == 0)
1203       // The previous token does not open a block. Nothing to do. We don't
1204       // assert so that we can simply call this function for all tokens.
1205       return true;
1206
1207     if (NewLine) {
1208       int AdditionalIndent =
1209           State.FirstIndent - State.Line->Level * Style.IndentWidth;
1210       if (State.Stack.size() < 2 ||
1211           !State.Stack[State.Stack.size() - 2].JSFunctionInlined) {
1212         AdditionalIndent = State.Stack.back().Indent -
1213                            Previous.Children[0]->Level * Style.IndentWidth;
1214       }
1215
1216       Penalty += format(Previous.Children, DryRun, AdditionalIndent,
1217                         /*FixBadIndentation=*/true);
1218       return true;
1219     }
1220
1221     // Cannot merge multiple statements into a single line.
1222     if (Previous.Children.size() > 1)
1223       return false;
1224
1225     // Cannot merge into one line if this line ends on a comment.
1226     if (Previous.is(tok::comment))
1227       return false;
1228
1229     // We can't put the closing "}" on a line with a trailing comment.
1230     if (Previous.Children[0]->Last->isTrailingComment())
1231       return false;
1232
1233     // If the child line exceeds the column limit, we wouldn't want to merge it.
1234     // We add +2 for the trailing " }".
1235     if (Style.ColumnLimit > 0 &&
1236         Previous.Children[0]->Last->TotalLength + State.Column + 2 >
1237             Style.ColumnLimit)
1238       return false;
1239
1240     if (!DryRun) {
1241       Whitespaces->replaceWhitespace(
1242           *Previous.Children[0]->First,
1243           /*Newlines=*/0, /*IndentLevel=*/0, /*Spaces=*/1,
1244           /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
1245     }
1246     Penalty += format(*Previous.Children[0], State.Column + 1, DryRun);
1247
1248     State.Column += 1 + Previous.Children[0]->Last->TotalLength;
1249     return true;
1250   }
1251
1252   ContinuationIndenter *Indenter;
1253   WhitespaceManager *Whitespaces;
1254   FormatStyle Style;
1255   LineJoiner Joiner;
1256
1257   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
1258
1259   // Cache to store the penalty of formatting a vector of AnnotatedLines
1260   // starting from a specific additional offset. Improves performance if there
1261   // are many nested blocks.
1262   std::map<std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned>,
1263            unsigned> PenaltyCache;
1264 };
1265
1266 class FormatTokenLexer {
1267 public:
1268   FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr, FormatStyle &Style,
1269                    encoding::Encoding Encoding)
1270       : FormatTok(nullptr), IsFirstToken(true), GreaterStashed(false),
1271         Column(0), TrailingWhitespace(0), Lex(Lex), SourceMgr(SourceMgr),
1272         Style(Style), IdentTable(getFormattingLangOpts()), Encoding(Encoding),
1273         FirstInLineIndex(0) {
1274     Lex.SetKeepWhitespaceMode(true);
1275
1276     for (const std::string &ForEachMacro : Style.ForEachMacros)
1277       ForEachMacros.push_back(&IdentTable.get(ForEachMacro));
1278     std::sort(ForEachMacros.begin(), ForEachMacros.end());
1279   }
1280
1281   ArrayRef<FormatToken *> lex() {
1282     assert(Tokens.empty());
1283     assert(FirstInLineIndex == 0);
1284     do {
1285       Tokens.push_back(getNextToken());
1286       tryMergePreviousTokens();
1287       if (Tokens.back()->NewlinesBefore > 0)
1288         FirstInLineIndex = Tokens.size() - 1;
1289     } while (Tokens.back()->Tok.isNot(tok::eof));
1290     return Tokens;
1291   }
1292
1293   IdentifierTable &getIdentTable() { return IdentTable; }
1294
1295 private:
1296   void tryMergePreviousTokens() {
1297     if (tryMerge_TMacro())
1298       return;
1299     if (tryMergeConflictMarkers())
1300       return;
1301
1302     if (Style.Language == FormatStyle::LK_JavaScript) {
1303       if (tryMergeEscapeSequence())
1304         return;
1305       if (tryMergeJSRegexLiteral())
1306         return;
1307
1308       static tok::TokenKind JSIdentity[] = { tok::equalequal, tok::equal };
1309       static tok::TokenKind JSNotIdentity[] = { tok::exclaimequal, tok::equal };
1310       static tok::TokenKind JSShiftEqual[] = { tok::greater, tok::greater,
1311                                                tok::greaterequal };
1312       static tok::TokenKind JSRightArrow[] = { tok::equal, tok::greater };
1313       // FIXME: We probably need to change token type to mimic operator with the
1314       // correct priority.
1315       if (tryMergeTokens(JSIdentity))
1316         return;
1317       if (tryMergeTokens(JSNotIdentity))
1318         return;
1319       if (tryMergeTokens(JSShiftEqual))
1320         return;
1321       if (tryMergeTokens(JSRightArrow))
1322         return;
1323     }
1324   }
1325
1326   bool tryMergeTokens(ArrayRef<tok::TokenKind> Kinds) {
1327     if (Tokens.size() < Kinds.size())
1328       return false;
1329
1330     SmallVectorImpl<FormatToken *>::const_iterator First =
1331         Tokens.end() - Kinds.size();
1332     if (!First[0]->is(Kinds[0]))
1333       return false;
1334     unsigned AddLength = 0;
1335     for (unsigned i = 1; i < Kinds.size(); ++i) {
1336       if (!First[i]->is(Kinds[i]) || First[i]->WhitespaceRange.getBegin() !=
1337                                          First[i]->WhitespaceRange.getEnd())
1338         return false;
1339       AddLength += First[i]->TokenText.size();
1340     }
1341     Tokens.resize(Tokens.size() - Kinds.size() + 1);
1342     First[0]->TokenText = StringRef(First[0]->TokenText.data(),
1343                                     First[0]->TokenText.size() + AddLength);
1344     First[0]->ColumnWidth += AddLength;
1345     return true;
1346   }
1347
1348   // Tries to merge an escape sequence, i.e. a "\\" and the following
1349   // character. Use e.g. inside JavaScript regex literals.
1350   bool tryMergeEscapeSequence() {
1351     if (Tokens.size() < 2)
1352       return false;
1353     FormatToken *Previous = Tokens[Tokens.size() - 2];
1354     if (Previous->isNot(tok::unknown) || Previous->TokenText != "\\" ||
1355         Tokens.back()->NewlinesBefore != 0)
1356       return false;
1357     Previous->ColumnWidth += Tokens.back()->ColumnWidth;
1358     StringRef Text = Previous->TokenText;
1359     Previous->TokenText =
1360         StringRef(Text.data(), Text.size() + Tokens.back()->TokenText.size());
1361     Tokens.resize(Tokens.size() - 1);
1362     return true;
1363   }
1364
1365   // Try to determine whether the current token ends a JavaScript regex literal.
1366   // We heuristically assume that this is a regex literal if we find two
1367   // unescaped slashes on a line and the token before the first slash is one of
1368   // "(;,{}![:?", a binary operator or 'return', as those cannot be followed by
1369   // a division.
1370   bool tryMergeJSRegexLiteral() {
1371     if (Tokens.size() < 2 || Tokens.back()->isNot(tok::slash) ||
1372         (Tokens[Tokens.size() - 2]->is(tok::unknown) &&
1373          Tokens[Tokens.size() - 2]->TokenText == "\\"))
1374       return false;
1375     unsigned TokenCount = 0;
1376     unsigned LastColumn = Tokens.back()->OriginalColumn;
1377     for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; ++I) {
1378       ++TokenCount;
1379       if (I[0]->is(tok::slash) && I + 1 != E &&
1380           (I[1]->isOneOf(tok::l_paren, tok::semi, tok::l_brace, tok::r_brace,
1381                          tok::exclaim, tok::l_square, tok::colon, tok::comma,
1382                          tok::question, tok::kw_return) ||
1383            I[1]->isBinaryOperator())) {
1384         Tokens.resize(Tokens.size() - TokenCount);
1385         Tokens.back()->Tok.setKind(tok::unknown);
1386         Tokens.back()->Type = TT_RegexLiteral;
1387         Tokens.back()->ColumnWidth += LastColumn - I[0]->OriginalColumn;
1388         return true;
1389       }
1390
1391       // There can't be a newline inside a regex literal.
1392       if (I[0]->NewlinesBefore > 0)
1393         return false;
1394     }
1395     return false;
1396   }
1397
1398   bool tryMerge_TMacro() {
1399     if (Tokens.size() < 4)
1400       return false;
1401     FormatToken *Last = Tokens.back();
1402     if (!Last->is(tok::r_paren))
1403       return false;
1404
1405     FormatToken *String = Tokens[Tokens.size() - 2];
1406     if (!String->is(tok::string_literal) || String->IsMultiline)
1407       return false;
1408
1409     if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
1410       return false;
1411
1412     FormatToken *Macro = Tokens[Tokens.size() - 4];
1413     if (Macro->TokenText != "_T")
1414       return false;
1415
1416     const char *Start = Macro->TokenText.data();
1417     const char *End = Last->TokenText.data() + Last->TokenText.size();
1418     String->TokenText = StringRef(Start, End - Start);
1419     String->IsFirst = Macro->IsFirst;
1420     String->LastNewlineOffset = Macro->LastNewlineOffset;
1421     String->WhitespaceRange = Macro->WhitespaceRange;
1422     String->OriginalColumn = Macro->OriginalColumn;
1423     String->ColumnWidth = encoding::columnWidthWithTabs(
1424         String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
1425
1426     Tokens.pop_back();
1427     Tokens.pop_back();
1428     Tokens.pop_back();
1429     Tokens.back() = String;
1430     return true;
1431   }
1432
1433   bool tryMergeConflictMarkers() {
1434     if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(tok::eof))
1435       return false;
1436
1437     // Conflict lines look like:
1438     // <marker> <text from the vcs>
1439     // For example:
1440     // >>>>>>> /file/in/file/system at revision 1234
1441     //
1442     // We merge all tokens in a line that starts with a conflict marker
1443     // into a single token with a special token type that the unwrapped line
1444     // parser will use to correctly rebuild the underlying code.
1445
1446     FileID ID;
1447     // Get the position of the first token in the line.
1448     unsigned FirstInLineOffset;
1449     std::tie(ID, FirstInLineOffset) = SourceMgr.getDecomposedLoc(
1450         Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
1451     StringRef Buffer = SourceMgr.getBuffer(ID)->getBuffer();
1452     // Calculate the offset of the start of the current line.
1453     auto LineOffset = Buffer.rfind('\n', FirstInLineOffset);
1454     if (LineOffset == StringRef::npos) {
1455       LineOffset = 0;
1456     } else {
1457       ++LineOffset;
1458     }
1459
1460     auto FirstSpace = Buffer.find_first_of(" \n", LineOffset);
1461     StringRef LineStart;
1462     if (FirstSpace == StringRef::npos) {
1463       LineStart = Buffer.substr(LineOffset);
1464     } else {
1465       LineStart = Buffer.substr(LineOffset, FirstSpace - LineOffset);
1466     }
1467
1468     TokenType Type = TT_Unknown;
1469     if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
1470       Type = TT_ConflictStart;
1471     } else if (LineStart == "|||||||" || LineStart == "=======" ||
1472                LineStart == "====") {
1473       Type = TT_ConflictAlternative;
1474     } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
1475       Type = TT_ConflictEnd;
1476     }
1477
1478     if (Type != TT_Unknown) {
1479       FormatToken *Next = Tokens.back();
1480
1481       Tokens.resize(FirstInLineIndex + 1);
1482       // We do not need to build a complete token here, as we will skip it
1483       // during parsing anyway (as we must not touch whitespace around conflict
1484       // markers).
1485       Tokens.back()->Type = Type;
1486       Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
1487
1488       Tokens.push_back(Next);
1489       return true;
1490     }
1491
1492     return false;
1493   }
1494
1495   FormatToken *getNextToken() {
1496     if (GreaterStashed) {
1497       // Create a synthesized second '>' token.
1498       // FIXME: Increment Column and set OriginalColumn.
1499       Token Greater = FormatTok->Tok;
1500       FormatTok = new (Allocator.Allocate()) FormatToken;
1501       FormatTok->Tok = Greater;
1502       SourceLocation GreaterLocation =
1503           FormatTok->Tok.getLocation().getLocWithOffset(1);
1504       FormatTok->WhitespaceRange =
1505           SourceRange(GreaterLocation, GreaterLocation);
1506       FormatTok->TokenText = ">";
1507       FormatTok->ColumnWidth = 1;
1508       GreaterStashed = false;
1509       return FormatTok;
1510     }
1511
1512     FormatTok = new (Allocator.Allocate()) FormatToken;
1513     readRawToken(*FormatTok);
1514     SourceLocation WhitespaceStart =
1515         FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
1516     FormatTok->IsFirst = IsFirstToken;
1517     IsFirstToken = false;
1518
1519     // Consume and record whitespace until we find a significant token.
1520     unsigned WhitespaceLength = TrailingWhitespace;
1521     while (FormatTok->Tok.is(tok::unknown)) {
1522       for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) {
1523         switch (FormatTok->TokenText[i]) {
1524         case '\n':
1525           ++FormatTok->NewlinesBefore;
1526           // FIXME: This is technically incorrect, as it could also
1527           // be a literal backslash at the end of the line.
1528           if (i == 0 || (FormatTok->TokenText[i - 1] != '\\' &&
1529                          (FormatTok->TokenText[i - 1] != '\r' || i == 1 ||
1530                           FormatTok->TokenText[i - 2] != '\\')))
1531             FormatTok->HasUnescapedNewline = true;
1532           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1533           Column = 0;
1534           break;
1535         case '\r':
1536         case '\f':
1537         case '\v':
1538           Column = 0;
1539           break;
1540         case ' ':
1541           ++Column;
1542           break;
1543         case '\t':
1544           Column += Style.TabWidth - Column % Style.TabWidth;
1545           break;
1546         case '\\':
1547           ++Column;
1548           if (i + 1 == e || (FormatTok->TokenText[i + 1] != '\r' &&
1549                              FormatTok->TokenText[i + 1] != '\n'))
1550             FormatTok->Type = TT_ImplicitStringLiteral;
1551           break;
1552         default:
1553           FormatTok->Type = TT_ImplicitStringLiteral;
1554           ++Column;
1555           break;
1556         }
1557       }
1558
1559       if (FormatTok->Type == TT_ImplicitStringLiteral)
1560         break;
1561       WhitespaceLength += FormatTok->Tok.getLength();
1562
1563       readRawToken(*FormatTok);
1564     }
1565
1566     // In case the token starts with escaped newlines, we want to
1567     // take them into account as whitespace - this pattern is quite frequent
1568     // in macro definitions.
1569     // FIXME: Add a more explicit test.
1570     while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
1571            FormatTok->TokenText[1] == '\n') {
1572       ++FormatTok->NewlinesBefore;
1573       WhitespaceLength += 2;
1574       Column = 0;
1575       FormatTok->TokenText = FormatTok->TokenText.substr(2);
1576     }
1577
1578     FormatTok->WhitespaceRange = SourceRange(
1579         WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1580
1581     FormatTok->OriginalColumn = Column;
1582
1583     TrailingWhitespace = 0;
1584     if (FormatTok->Tok.is(tok::comment)) {
1585       // FIXME: Add the trimmed whitespace to Column.
1586       StringRef UntrimmedText = FormatTok->TokenText;
1587       FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
1588       TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1589     } else if (FormatTok->Tok.is(tok::raw_identifier)) {
1590       IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
1591       FormatTok->Tok.setIdentifierInfo(&Info);
1592       FormatTok->Tok.setKind(Info.getTokenID());
1593     } else if (FormatTok->Tok.is(tok::greatergreater)) {
1594       FormatTok->Tok.setKind(tok::greater);
1595       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1596       GreaterStashed = true;
1597     }
1598
1599     // Now FormatTok is the next non-whitespace token.
1600
1601     StringRef Text = FormatTok->TokenText;
1602     size_t FirstNewlinePos = Text.find('\n');
1603     if (FirstNewlinePos == StringRef::npos) {
1604       // FIXME: ColumnWidth actually depends on the start column, we need to
1605       // take this into account when the token is moved.
1606       FormatTok->ColumnWidth =
1607           encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
1608       Column += FormatTok->ColumnWidth;
1609     } else {
1610       FormatTok->IsMultiline = true;
1611       // FIXME: ColumnWidth actually depends on the start column, we need to
1612       // take this into account when the token is moved.
1613       FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1614           Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
1615
1616       // The last line of the token always starts in column 0.
1617       // Thus, the length can be precomputed even in the presence of tabs.
1618       FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1619           Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
1620           Encoding);
1621       Column = FormatTok->LastLineColumnWidth;
1622     }
1623
1624     FormatTok->IsForEachMacro =
1625         std::binary_search(ForEachMacros.begin(), ForEachMacros.end(),
1626                            FormatTok->Tok.getIdentifierInfo());
1627
1628     return FormatTok;
1629   }
1630
1631   FormatToken *FormatTok;
1632   bool IsFirstToken;
1633   bool GreaterStashed;
1634   unsigned Column;
1635   unsigned TrailingWhitespace;
1636   Lexer &Lex;
1637   SourceManager &SourceMgr;
1638   FormatStyle &Style;
1639   IdentifierTable IdentTable;
1640   encoding::Encoding Encoding;
1641   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
1642   // Index (in 'Tokens') of the last token that starts a new line.
1643   unsigned FirstInLineIndex;
1644   SmallVector<FormatToken *, 16> Tokens;
1645   SmallVector<IdentifierInfo *, 8> ForEachMacros;
1646
1647   void readRawToken(FormatToken &Tok) {
1648     Lex.LexFromRawLexer(Tok.Tok);
1649     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
1650                               Tok.Tok.getLength());
1651     // For formatting, treat unterminated string literals like normal string
1652     // literals.
1653     if (Tok.is(tok::unknown)) {
1654       if (!Tok.TokenText.empty() && Tok.TokenText[0] == '"') {
1655         Tok.Tok.setKind(tok::string_literal);
1656         Tok.IsUnterminatedLiteral = true;
1657       } else if (Style.Language == FormatStyle::LK_JavaScript &&
1658                  Tok.TokenText == "''") {
1659         Tok.Tok.setKind(tok::char_constant);
1660       }
1661     }
1662   }
1663 };
1664
1665 static StringRef getLanguageName(FormatStyle::LanguageKind Language) {
1666   switch (Language) {
1667   case FormatStyle::LK_Cpp:
1668     return "C++";
1669   case FormatStyle::LK_JavaScript:
1670     return "JavaScript";
1671   case FormatStyle::LK_Proto:
1672     return "Proto";
1673   default:
1674     return "Unknown";
1675   }
1676 }
1677
1678 class Formatter : public UnwrappedLineConsumer {
1679 public:
1680   Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
1681             const std::vector<CharSourceRange> &Ranges)
1682       : Style(Style), Lex(Lex), SourceMgr(SourceMgr),
1683         Whitespaces(SourceMgr, Style, inputUsesCRLF(Lex.getBuffer())),
1684         Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1),
1685         Encoding(encoding::detectEncoding(Lex.getBuffer())) {
1686     DEBUG(llvm::dbgs() << "File encoding: "
1687                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
1688                                                                : "unknown")
1689                        << "\n");
1690     DEBUG(llvm::dbgs() << "Language: " << getLanguageName(Style.Language)
1691                        << "\n");
1692   }
1693
1694   tooling::Replacements format() {
1695     tooling::Replacements Result;
1696     FormatTokenLexer Tokens(Lex, SourceMgr, Style, Encoding);
1697
1698     UnwrappedLineParser Parser(Style, Tokens.lex(), *this);
1699     bool StructuralError = Parser.parse();
1700     assert(UnwrappedLines.rbegin()->empty());
1701     for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
1702          ++Run) {
1703       DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
1704       SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1705       for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
1706         AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
1707       }
1708       tooling::Replacements RunResult =
1709           format(AnnotatedLines, StructuralError, Tokens);
1710       DEBUG({
1711         llvm::dbgs() << "Replacements for run " << Run << ":\n";
1712         for (tooling::Replacements::iterator I = RunResult.begin(),
1713                                              E = RunResult.end();
1714              I != E; ++I) {
1715           llvm::dbgs() << I->toString() << "\n";
1716         }
1717       });
1718       for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1719         delete AnnotatedLines[i];
1720       }
1721       Result.insert(RunResult.begin(), RunResult.end());
1722       Whitespaces.reset();
1723     }
1724     return Result;
1725   }
1726
1727   tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1728                                bool StructuralError, FormatTokenLexer &Tokens) {
1729     TokenAnnotator Annotator(Style, Tokens.getIdentTable().get("in"));
1730     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1731       Annotator.annotate(*AnnotatedLines[i]);
1732     }
1733     deriveLocalStyle(AnnotatedLines);
1734     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1735       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1736     }
1737     computeAffectedLines(AnnotatedLines.begin(), AnnotatedLines.end());
1738
1739     Annotator.setCommentLineLevels(AnnotatedLines);
1740     ContinuationIndenter Indenter(Style, SourceMgr, Whitespaces, Encoding,
1741                                   BinPackInconclusiveFunctions);
1742     UnwrappedLineFormatter Formatter(&Indenter, &Whitespaces, Style);
1743     Formatter.format(AnnotatedLines, /*DryRun=*/false);
1744     return Whitespaces.generateReplacements();
1745   }
1746
1747 private:
1748   // Determines which lines are affected by the SourceRanges given as input.
1749   // Returns \c true if at least one line between I and E or one of their
1750   // children is affected.
1751   bool computeAffectedLines(SmallVectorImpl<AnnotatedLine *>::iterator I,
1752                             SmallVectorImpl<AnnotatedLine *>::iterator E) {
1753     bool SomeLineAffected = false;
1754     const AnnotatedLine *PreviousLine = nullptr;
1755     while (I != E) {
1756       AnnotatedLine *Line = *I;
1757       Line->LeadingEmptyLinesAffected = affectsLeadingEmptyLines(*Line->First);
1758
1759       // If a line is part of a preprocessor directive, it needs to be formatted
1760       // if any token within the directive is affected.
1761       if (Line->InPPDirective) {
1762         FormatToken *Last = Line->Last;
1763         SmallVectorImpl<AnnotatedLine *>::iterator PPEnd = I + 1;
1764         while (PPEnd != E && !(*PPEnd)->First->HasUnescapedNewline) {
1765           Last = (*PPEnd)->Last;
1766           ++PPEnd;
1767         }
1768
1769         if (affectsTokenRange(*Line->First, *Last,
1770                               /*IncludeLeadingNewlines=*/false)) {
1771           SomeLineAffected = true;
1772           markAllAsAffected(I, PPEnd);
1773         }
1774         I = PPEnd;
1775         continue;
1776       }
1777
1778       if (nonPPLineAffected(Line, PreviousLine))
1779         SomeLineAffected = true;
1780
1781       PreviousLine = Line;
1782       ++I;
1783     }
1784     return SomeLineAffected;
1785   }
1786
1787   // Determines whether 'Line' is affected by the SourceRanges given as input.
1788   // Returns \c true if line or one if its children is affected.
1789   bool nonPPLineAffected(AnnotatedLine *Line,
1790                          const AnnotatedLine *PreviousLine) {
1791     bool SomeLineAffected = false;
1792     Line->ChildrenAffected =
1793         computeAffectedLines(Line->Children.begin(), Line->Children.end());
1794     if (Line->ChildrenAffected)
1795       SomeLineAffected = true;
1796
1797     // Stores whether one of the line's tokens is directly affected.
1798     bool SomeTokenAffected = false;
1799     // Stores whether we need to look at the leading newlines of the next token
1800     // in order to determine whether it was affected.
1801     bool IncludeLeadingNewlines = false;
1802
1803     // Stores whether the first child line of any of this line's tokens is
1804     // affected.
1805     bool SomeFirstChildAffected = false;
1806
1807     for (FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
1808       // Determine whether 'Tok' was affected.
1809       if (affectsTokenRange(*Tok, *Tok, IncludeLeadingNewlines))
1810         SomeTokenAffected = true;
1811
1812       // Determine whether the first child of 'Tok' was affected.
1813       if (!Tok->Children.empty() && Tok->Children.front()->Affected)
1814         SomeFirstChildAffected = true;
1815
1816       IncludeLeadingNewlines = Tok->Children.empty();
1817     }
1818
1819     // Was this line moved, i.e. has it previously been on the same line as an
1820     // affected line?
1821     bool LineMoved = PreviousLine && PreviousLine->Affected &&
1822                      Line->First->NewlinesBefore == 0;
1823
1824     bool IsContinuedComment =
1825         Line->First->is(tok::comment) && Line->First->Next == nullptr &&
1826         Line->First->NewlinesBefore < 2 && PreviousLine &&
1827         PreviousLine->Affected && PreviousLine->Last->is(tok::comment);
1828
1829     if (SomeTokenAffected || SomeFirstChildAffected || LineMoved ||
1830         IsContinuedComment) {
1831       Line->Affected = true;
1832       SomeLineAffected = true;
1833     }
1834     return SomeLineAffected;
1835   }
1836
1837   // Marks all lines between I and E as well as all their children as affected.
1838   void markAllAsAffected(SmallVectorImpl<AnnotatedLine *>::iterator I,
1839                          SmallVectorImpl<AnnotatedLine *>::iterator E) {
1840     while (I != E) {
1841       (*I)->Affected = true;
1842       markAllAsAffected((*I)->Children.begin(), (*I)->Children.end());
1843       ++I;
1844     }
1845   }
1846
1847   // Returns true if the range from 'First' to 'Last' intersects with one of the
1848   // input ranges.
1849   bool affectsTokenRange(const FormatToken &First, const FormatToken &Last,
1850                          bool IncludeLeadingNewlines) {
1851     SourceLocation Start = First.WhitespaceRange.getBegin();
1852     if (!IncludeLeadingNewlines)
1853       Start = Start.getLocWithOffset(First.LastNewlineOffset);
1854     SourceLocation End = Last.getStartOfNonWhitespace();
1855     if (Last.TokenText.size() > 0)
1856       End = End.getLocWithOffset(Last.TokenText.size() - 1);
1857     CharSourceRange Range = CharSourceRange::getCharRange(Start, End);
1858     return affectsCharSourceRange(Range);
1859   }
1860
1861   // Returns true if one of the input ranges intersect the leading empty lines
1862   // before 'Tok'.
1863   bool affectsLeadingEmptyLines(const FormatToken &Tok) {
1864     CharSourceRange EmptyLineRange = CharSourceRange::getCharRange(
1865         Tok.WhitespaceRange.getBegin(),
1866         Tok.WhitespaceRange.getBegin().getLocWithOffset(Tok.LastNewlineOffset));
1867     return affectsCharSourceRange(EmptyLineRange);
1868   }
1869
1870   // Returns true if 'Range' intersects with one of the input ranges.
1871   bool affectsCharSourceRange(const CharSourceRange &Range) {
1872     for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
1873                                                           E = Ranges.end();
1874          I != E; ++I) {
1875       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
1876           !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
1877         return true;
1878     }
1879     return false;
1880   }
1881
1882   static bool inputUsesCRLF(StringRef Text) {
1883     return Text.count('\r') * 2 > Text.count('\n');
1884   }
1885
1886   void
1887   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1888     unsigned CountBoundToVariable = 0;
1889     unsigned CountBoundToType = 0;
1890     bool HasCpp03IncompatibleFormat = false;
1891     bool HasBinPackedFunction = false;
1892     bool HasOnePerLineFunction = false;
1893     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1894       if (!AnnotatedLines[i]->First->Next)
1895         continue;
1896       FormatToken *Tok = AnnotatedLines[i]->First->Next;
1897       while (Tok->Next) {
1898         if (Tok->Type == TT_PointerOrReference) {
1899           bool SpacesBefore =
1900               Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1901           bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
1902                              Tok->Next->WhitespaceRange.getEnd();
1903           if (SpacesBefore && !SpacesAfter)
1904             ++CountBoundToVariable;
1905           else if (!SpacesBefore && SpacesAfter)
1906             ++CountBoundToType;
1907         }
1908
1909         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1910           if (Tok->is(tok::coloncolon) &&
1911               Tok->Previous->Type == TT_TemplateOpener)
1912             HasCpp03IncompatibleFormat = true;
1913           if (Tok->Type == TT_TemplateCloser &&
1914               Tok->Previous->Type == TT_TemplateCloser)
1915             HasCpp03IncompatibleFormat = true;
1916         }
1917
1918         if (Tok->PackingKind == PPK_BinPacked)
1919           HasBinPackedFunction = true;
1920         if (Tok->PackingKind == PPK_OnePerLine)
1921           HasOnePerLineFunction = true;
1922
1923         Tok = Tok->Next;
1924       }
1925     }
1926     if (Style.DerivePointerAlignment) {
1927       if (CountBoundToType > CountBoundToVariable)
1928         Style.PointerAlignment = FormatStyle::PAS_Left;
1929       else if (CountBoundToType < CountBoundToVariable)
1930         Style.PointerAlignment = FormatStyle::PAS_Right;
1931     }
1932     if (Style.Standard == FormatStyle::LS_Auto) {
1933       Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
1934                                                   : FormatStyle::LS_Cpp03;
1935     }
1936     BinPackInconclusiveFunctions =
1937         HasBinPackedFunction || !HasOnePerLineFunction;
1938   }
1939
1940   void consumeUnwrappedLine(const UnwrappedLine &TheLine) override {
1941     assert(!UnwrappedLines.empty());
1942     UnwrappedLines.back().push_back(TheLine);
1943   }
1944
1945   void finishRun() override {
1946     UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
1947   }
1948
1949   FormatStyle Style;
1950   Lexer &Lex;
1951   SourceManager &SourceMgr;
1952   WhitespaceManager Whitespaces;
1953   SmallVector<CharSourceRange, 8> Ranges;
1954   SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
1955
1956   encoding::Encoding Encoding;
1957   bool BinPackInconclusiveFunctions;
1958 };
1959
1960 } // end anonymous namespace
1961
1962 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1963                                SourceManager &SourceMgr,
1964                                std::vector<CharSourceRange> Ranges) {
1965   if (Style.DisableFormat) {
1966     tooling::Replacements EmptyResult;
1967     return EmptyResult;
1968   }
1969
1970   Formatter formatter(Style, Lex, SourceMgr, Ranges);
1971   return formatter.format();
1972 }
1973
1974 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1975                                std::vector<tooling::Range> Ranges,
1976                                StringRef FileName) {
1977   FileManager Files((FileSystemOptions()));
1978   DiagnosticsEngine Diagnostics(
1979       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1980       new DiagnosticOptions);
1981   SourceManager SourceMgr(Diagnostics, Files);
1982   llvm::MemoryBuffer *Buf = llvm::MemoryBuffer::getMemBuffer(Code, FileName);
1983   const clang::FileEntry *Entry =
1984       Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
1985   SourceMgr.overrideFileContents(Entry, Buf);
1986   FileID ID =
1987       SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
1988   Lexer Lex(ID, SourceMgr.getBuffer(ID), SourceMgr,
1989             getFormattingLangOpts(Style.Standard));
1990   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1991   std::vector<CharSourceRange> CharRanges;
1992   for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1993     SourceLocation Start = StartOfFile.getLocWithOffset(Ranges[i].getOffset());
1994     SourceLocation End = Start.getLocWithOffset(Ranges[i].getLength());
1995     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1996   }
1997   return reformat(Style, Lex, SourceMgr, CharRanges);
1998 }
1999
2000 LangOptions getFormattingLangOpts(FormatStyle::LanguageStandard Standard) {
2001   LangOptions LangOpts;
2002   LangOpts.CPlusPlus = 1;
2003   LangOpts.CPlusPlus11 = Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2004   LangOpts.CPlusPlus1y = Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2005   LangOpts.LineComment = 1;
2006   LangOpts.CXXOperatorNames = 1;
2007   LangOpts.Bool = 1;
2008   LangOpts.ObjC1 = 1;
2009   LangOpts.ObjC2 = 1;
2010   return LangOpts;
2011 }
2012
2013 const char *StyleOptionHelpDescription =
2014     "Coding style, currently supports:\n"
2015     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
2016     "Use -style=file to load style configuration from\n"
2017     ".clang-format file located in one of the parent\n"
2018     "directories of the source file (or current\n"
2019     "directory for stdin).\n"
2020     "Use -style=\"{key: value, ...}\" to set specific\n"
2021     "parameters, e.g.:\n"
2022     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
2023
2024 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
2025   if (FileName.endswith_lower(".js")) {
2026     return FormatStyle::LK_JavaScript;
2027   } else if (FileName.endswith_lower(".proto") ||
2028              FileName.endswith_lower(".protodevel")) {
2029     return FormatStyle::LK_Proto;
2030   }
2031   return FormatStyle::LK_Cpp;
2032 }
2033
2034 FormatStyle getStyle(StringRef StyleName, StringRef FileName,
2035                      StringRef FallbackStyle) {
2036   FormatStyle Style = getLLVMStyle();
2037   Style.Language = getLanguageByFileName(FileName);
2038   if (!getPredefinedStyle(FallbackStyle, Style.Language, &Style)) {
2039     llvm::errs() << "Invalid fallback style \"" << FallbackStyle
2040                  << "\" using LLVM style\n";
2041     return Style;
2042   }
2043
2044   if (StyleName.startswith("{")) {
2045     // Parse YAML/JSON style from the command line.
2046     if (std::error_code ec = parseConfiguration(StyleName, &Style)) {
2047       llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
2048                    << FallbackStyle << " style\n";
2049     }
2050     return Style;
2051   }
2052
2053   if (!StyleName.equals_lower("file")) {
2054     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
2055       llvm::errs() << "Invalid value for -style, using " << FallbackStyle
2056                    << " style\n";
2057     return Style;
2058   }
2059
2060   // Look for .clang-format/_clang-format file in the file's parent directories.
2061   SmallString<128> UnsuitableConfigFiles;
2062   SmallString<128> Path(FileName);
2063   llvm::sys::fs::make_absolute(Path);
2064   for (StringRef Directory = Path; !Directory.empty();
2065        Directory = llvm::sys::path::parent_path(Directory)) {
2066     if (!llvm::sys::fs::is_directory(Directory))
2067       continue;
2068     SmallString<128> ConfigFile(Directory);
2069
2070     llvm::sys::path::append(ConfigFile, ".clang-format");
2071     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2072     bool IsFile = false;
2073     // Ignore errors from is_regular_file: we only need to know if we can read
2074     // the file or not.
2075     llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
2076
2077     if (!IsFile) {
2078       // Try _clang-format too, since dotfiles are not commonly used on Windows.
2079       ConfigFile = Directory;
2080       llvm::sys::path::append(ConfigFile, "_clang-format");
2081       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2082       llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
2083     }
2084
2085     if (IsFile) {
2086       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2087           llvm::MemoryBuffer::getFile(ConfigFile.c_str());
2088       if (std::error_code EC = Text.getError()) {
2089         llvm::errs() << EC.message() << "\n";
2090         break;
2091       }
2092       if (std::error_code ec =
2093               parseConfiguration(Text.get()->getBuffer(), &Style)) {
2094         if (ec == ParseError::Unsuitable) {
2095           if (!UnsuitableConfigFiles.empty())
2096             UnsuitableConfigFiles.append(", ");
2097           UnsuitableConfigFiles.append(ConfigFile);
2098           continue;
2099         }
2100         llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
2101                      << "\n";
2102         break;
2103       }
2104       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
2105       return Style;
2106     }
2107   }
2108   llvm::errs() << "Can't find usable .clang-format, using " << FallbackStyle
2109                << " style\n";
2110   if (!UnsuitableConfigFiles.empty()) {
2111     llvm::errs() << "Configuration file(s) do(es) not support "
2112                  << getLanguageName(Style.Language) << ": "
2113                  << UnsuitableConfigFiles << "\n";
2114   }
2115   return Style;
2116 }
2117
2118 } // namespace format
2119 } // namespace clang