granicus.if.org Git - clang/blob - 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 "clang/Format/Format.h"
  17 #include "ContinuationIndenter.h"
  18 #include "TokenAnnotator.h"
  19 #include "UnwrappedLineFormatter.h"
  20 #include "UnwrappedLineParser.h"
  21 #include "WhitespaceManager.h"
  22 #include "clang/Basic/Diagnostic.h"
  23 #include "clang/Basic/DiagnosticOptions.h"
  24 #include "clang/Basic/SourceManager.h"
  25 #include "clang/Lex/Lexer.h"
  26 #include "llvm/ADT/STLExtras.h"
  27 #include "llvm/Support/Allocator.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/Path.h"
  30 #include "llvm/Support/Regex.h"
  31 #include "llvm/Support/YAMLTraits.h"
  32 #include <queue>
  33 #include <string>
  34
  35 #define DEBUG_TYPE "format-formatter"
  36
  37 using clang::format::FormatStyle;
  38
  39 LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
  40 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::IncludeCategory)
  41
  42 namespace llvm {
  43 namespace yaml {
  44 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
  45   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
  46     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
  47     IO.enumCase(Value, "Java", FormatStyle::LK_Java);
  48     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
  49     IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
  50   }
  51 };
  52
  53 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
  54   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
  55     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
  56     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
  57     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
  58     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
  59     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
  60   }
  61 };
  62
  63 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
  64   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
  65     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
  66     IO.enumCase(Value, "false", FormatStyle::UT_Never);
  67     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
  68     IO.enumCase(Value, "true", FormatStyle::UT_Always);
  69     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
  70   }
  71 };
  72
  73 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
  74   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
  75     IO.enumCase(Value, "None", FormatStyle::SFS_None);
  76     IO.enumCase(Value, "false", FormatStyle::SFS_None);
  77     IO.enumCase(Value, "All", FormatStyle::SFS_All);
  78     IO.enumCase(Value, "true", FormatStyle::SFS_All);
  79     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
  80     IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
  81   }
  82 };
  83
  84 template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
  85   static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
  86     IO.enumCase(Value, "All", FormatStyle::BOS_All);
  87     IO.enumCase(Value, "true", FormatStyle::BOS_All);
  88     IO.enumCase(Value, "None", FormatStyle::BOS_None);
  89     IO.enumCase(Value, "false", FormatStyle::BOS_None);
  90     IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
  91   }
  92 };
  93
  94 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
  95   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
  96     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
  97     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
  98     IO.enumCase(Value, "Mozilla", FormatStyle::BS_Mozilla);
  99     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
 100     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
 101     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
 102     IO.enumCase(Value, "WebKit", FormatStyle::BS_WebKit);
 103     IO.enumCase(Value, "Custom", FormatStyle::BS_Custom);
 104   }
 105 };
 106
 107 template <>
 108 struct ScalarEnumerationTraits<FormatStyle::DefinitionReturnTypeBreakingStyle> {
 109   static void
 110   enumeration(IO &IO, FormatStyle::DefinitionReturnTypeBreakingStyle &Value) {
 111     IO.enumCase(Value, "None", FormatStyle::DRTBS_None);
 112     IO.enumCase(Value, "All", FormatStyle::DRTBS_All);
 113     IO.enumCase(Value, "TopLevel", FormatStyle::DRTBS_TopLevel);
 114
 115     // For backward compatibility.
 116     IO.enumCase(Value, "false", FormatStyle::DRTBS_None);
 117     IO.enumCase(Value, "true", FormatStyle::DRTBS_All);
 118   }
 119 };
 120
 121 template <>
 122 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
 123   static void enumeration(IO &IO,
 124                           FormatStyle::NamespaceIndentationKind &Value) {
 125     IO.enumCase(Value, "None", FormatStyle::NI_None);
 126     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
 127     IO.enumCase(Value, "All", FormatStyle::NI_All);
 128   }
 129 };
 130
 131 template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
 132   static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
 133     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
 134     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
 135     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
 136
 137     // For backward compatibility.
 138     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
 139     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
 140   }
 141 };
 142
 143 template <>
 144 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
 145   static void enumeration(IO &IO,
 146                           FormatStyle::SpaceBeforeParensOptions &Value) {
 147     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
 148     IO.enumCase(Value, "ControlStatements",
 149                 FormatStyle::SBPO_ControlStatements);
 150     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
 151
 152     // For backward compatibility.
 153     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
 154     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
 155   }
 156 };
 157
 158 template <> struct MappingTraits<FormatStyle> {
 159   static void mapping(IO &IO, FormatStyle &Style) {
 160     // When reading, read the language first, we need it for getPredefinedStyle.
 161     IO.mapOptional("Language", Style.Language);
 162
 163     if (IO.outputting()) {
 164       StringRef StylesArray[] = {"LLVM",    "Google", "Chromium",
 165                                  "Mozilla", "WebKit", "GNU"};
 166       ArrayRef<StringRef> Styles(StylesArray);
 167       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
 168         StringRef StyleName(Styles[i]);
 169         FormatStyle PredefinedStyle;
 170         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
 171             Style == PredefinedStyle) {
 172           IO.mapOptional("# BasedOnStyle", StyleName);
 173           break;
 174         }
 175       }
 176     } else {
 177       StringRef BasedOnStyle;
 178       IO.mapOptional("BasedOnStyle", BasedOnStyle);
 179       if (!BasedOnStyle.empty()) {
 180         FormatStyle::LanguageKind OldLanguage = Style.Language;
 181         FormatStyle::LanguageKind Language =
 182             ((FormatStyle *)IO.getContext())->Language;
 183         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
 184           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
 185           return;
 186         }
 187         Style.Language = OldLanguage;
 188       }
 189     }
 190
 191     // For backward compatibility.
 192     if (!IO.outputting()) {
 193       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
 194       IO.mapOptional("IndentFunctionDeclarationAfterType",
 195                      Style.IndentWrappedFunctionNames);
 196       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
 197       IO.mapOptional("SpaceAfterControlStatementKeyword",
 198                      Style.SpaceBeforeParens);
 199     }
 200
 201     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
 202     IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
 203     IO.mapOptional("AlignConsecutiveAssignments",
 204                    Style.AlignConsecutiveAssignments);
 205     IO.mapOptional("AlignConsecutiveDeclarations",
 206                    Style.AlignConsecutiveDeclarations);
 207     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
 208     IO.mapOptional("AlignOperands", Style.AlignOperands);
 209     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
 210     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
 211                    Style.AllowAllParametersOfDeclarationOnNextLine);
 212     IO.mapOptional("AllowShortBlocksOnASingleLine",
 213                    Style.AllowShortBlocksOnASingleLine);
 214     IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
 215                    Style.AllowShortCaseLabelsOnASingleLine);
 216     IO.mapOptional("AllowShortFunctionsOnASingleLine",
 217                    Style.AllowShortFunctionsOnASingleLine);
 218     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
 219                    Style.AllowShortIfStatementsOnASingleLine);
 220     IO.mapOptional("AllowShortLoopsOnASingleLine",
 221                    Style.AllowShortLoopsOnASingleLine);
 222     IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
 223                    Style.AlwaysBreakAfterDefinitionReturnType);
 224     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
 225                    Style.AlwaysBreakBeforeMultilineStrings);
 226     IO.mapOptional("AlwaysBreakTemplateDeclarations",
 227                    Style.AlwaysBreakTemplateDeclarations);
 228     IO.mapOptional("BinPackArguments", Style.BinPackArguments);
 229     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
 230     IO.mapOptional("BraceWrapping", Style.BraceWrapping);
 231     IO.mapOptional("BreakBeforeBinaryOperators",
 232                    Style.BreakBeforeBinaryOperators);
 233     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
 234     IO.mapOptional("BreakBeforeTernaryOperators",
 235                    Style.BreakBeforeTernaryOperators);
 236     IO.mapOptional("BreakConstructorInitializersBeforeComma",
 237                    Style.BreakConstructorInitializersBeforeComma);
 238     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
 239     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
 240     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
 241                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
 242     IO.mapOptional("ConstructorInitializerIndentWidth",
 243                    Style.ConstructorInitializerIndentWidth);
 244     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
 245     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
 246     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
 247     IO.mapOptional("DisableFormat", Style.DisableFormat);
 248     IO.mapOptional("ExperimentalAutoDetectBinPacking",
 249                    Style.ExperimentalAutoDetectBinPacking);
 250     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
 251     IO.mapOptional("IncludeCategories", Style.IncludeCategories);
 252     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
 253     IO.mapOptional("IndentWidth", Style.IndentWidth);
 254     IO.mapOptional("IndentWrappedFunctionNames",
 255                    Style.IndentWrappedFunctionNames);
 256     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
 257                    Style.KeepEmptyLinesAtTheStartOfBlocks);
 258     IO.mapOptional("MacroBlockBegin", Style.MacroBlockBegin);
 259     IO.mapOptional("MacroBlockEnd", Style.MacroBlockEnd);
 260     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
 261     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
 262     IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
 263     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
 264     IO.mapOptional("ObjCSpaceBeforeProtocolList",
 265                    Style.ObjCSpaceBeforeProtocolList);
 266     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
 267                    Style.PenaltyBreakBeforeFirstCallParameter);
 268     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
 269     IO.mapOptional("PenaltyBreakFirstLessLess",
 270                    Style.PenaltyBreakFirstLessLess);
 271     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
 272     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
 273     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
 274                    Style.PenaltyReturnTypeOnItsOwnLine);
 275     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
 276     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
 277     IO.mapOptional("SpaceBeforeAssignmentOperators",
 278                    Style.SpaceBeforeAssignmentOperators);
 279     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
 280     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
 281     IO.mapOptional("SpacesBeforeTrailingComments",
 282                    Style.SpacesBeforeTrailingComments);
 283     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
 284     IO.mapOptional("SpacesInContainerLiterals",
 285                    Style.SpacesInContainerLiterals);
 286     IO.mapOptional("SpacesInCStyleCastParentheses",
 287                    Style.SpacesInCStyleCastParentheses);
 288     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
 289     IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
 290     IO.mapOptional("Standard", Style.Standard);
 291     IO.mapOptional("TabWidth", Style.TabWidth);
 292     IO.mapOptional("UseTab", Style.UseTab);
 293   }
 294 };
 295
 296 template <> struct MappingTraits<FormatStyle::BraceWrappingFlags> {
 297   static void mapping(IO &IO, FormatStyle::BraceWrappingFlags &Wrapping) {
 298     IO.mapOptional("AfterClass", Wrapping.AfterClass);
 299     IO.mapOptional("AfterControlStatement", Wrapping.AfterControlStatement);
 300     IO.mapOptional("AfterEnum", Wrapping.AfterEnum);
 301     IO.mapOptional("AfterFunction", Wrapping.AfterFunction);
 302     IO.mapOptional("AfterNamespace", Wrapping.AfterNamespace);
 303     IO.mapOptional("AfterObjCDeclaration", Wrapping.AfterObjCDeclaration);
 304     IO.mapOptional("AfterStruct", Wrapping.AfterStruct);
 305     IO.mapOptional("AfterUnion", Wrapping.AfterUnion);
 306     IO.mapOptional("BeforeCatch", Wrapping.BeforeCatch);
 307     IO.mapOptional("BeforeElse", Wrapping.BeforeElse);
 308     IO.mapOptional("IndentBraces", Wrapping.IndentBraces);
 309   }
 310 };
 311
 312 template <> struct MappingTraits<FormatStyle::IncludeCategory> {
 313   static void mapping(IO &IO, FormatStyle::IncludeCategory &Category) {
 314     IO.mapOptional("Regex", Category.Regex);
 315     IO.mapOptional("Priority", Category.Priority);
 316   }
 317 };
 318
 319 // Allows to read vector<FormatStyle> while keeping default values.
 320 // IO.getContext() should contain a pointer to the FormatStyle structure, that
 321 // will be used to get default values for missing keys.
 322 // If the first element has no Language specified, it will be treated as the
 323 // default one for the following elements.
 324 template <> struct DocumentListTraits<std::vector<FormatStyle>> {
 325   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
 326     return Seq.size();
 327   }
 328   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
 329                               size_t Index) {
 330     if (Index >= Seq.size()) {
 331       assert(Index == Seq.size());
 332       FormatStyle Template;
 333       if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
 334         Template = Seq[0];
 335       } else {
 336         Template = *((const FormatStyle *)IO.getContext());
 337         Template.Language = FormatStyle::LK_None;
 338       }
 339       Seq.resize(Index + 1, Template);
 340     }
 341     return Seq[Index];
 342   }
 343 };
 344 } // namespace yaml
 345 } // namespace llvm
 346
 347 namespace clang {
 348 namespace format {
 349
 350 const std::error_category &getParseCategory() {
 351   static ParseErrorCategory C;
 352   return C;
 353 }
 354 std::error_code make_error_code(ParseError e) {
 355   return std::error_code(static_cast<int>(e), getParseCategory());
 356 }
 357
 358 const char *ParseErrorCategory::name() const LLVM_NOEXCEPT {
 359   return "clang-format.parse_error";
 360 }
 361
 362 std::string ParseErrorCategory::message(int EV) const {
 363   switch (static_cast<ParseError>(EV)) {
 364   case ParseError::Success:
 365     return "Success";
 366   case ParseError::Error:
 367     return "Invalid argument";
 368   case ParseError::Unsuitable:
 369     return "Unsuitable";
 370   }
 371   llvm_unreachable("unexpected parse error");
 372 }
 373
 374 static FormatStyle expandPresets(const FormatStyle &Style) {
 375   if (Style.BreakBeforeBraces == FormatStyle::BS_Custom)
 376     return Style;
 377   FormatStyle Expanded = Style;
 378   Expanded.BraceWrapping = {false, false, false, false, false, false,
 379                             false, false, false, false, false};
 380   switch (Style.BreakBeforeBraces) {
 381   case FormatStyle::BS_Linux:
 382     Expanded.BraceWrapping.AfterClass = true;
 383     Expanded.BraceWrapping.AfterFunction = true;
 384     Expanded.BraceWrapping.AfterNamespace = true;
 385     Expanded.BraceWrapping.BeforeElse = true;
 386     break;
 387   case FormatStyle::BS_Mozilla:
 388     Expanded.BraceWrapping.AfterClass = true;
 389     Expanded.BraceWrapping.AfterEnum = true;
 390     Expanded.BraceWrapping.AfterFunction = true;
 391     Expanded.BraceWrapping.AfterStruct = true;
 392     Expanded.BraceWrapping.AfterUnion = true;
 393     break;
 394   case FormatStyle::BS_Stroustrup:
 395     Expanded.BraceWrapping.AfterFunction = true;
 396     Expanded.BraceWrapping.BeforeCatch = true;
 397     Expanded.BraceWrapping.BeforeElse = true;
 398     break;
 399   case FormatStyle::BS_Allman:
 400     Expanded.BraceWrapping.AfterClass = true;
 401     Expanded.BraceWrapping.AfterControlStatement = true;
 402     Expanded.BraceWrapping.AfterEnum = true;
 403     Expanded.BraceWrapping.AfterFunction = true;
 404     Expanded.BraceWrapping.AfterNamespace = true;
 405     Expanded.BraceWrapping.AfterObjCDeclaration = true;
 406     Expanded.BraceWrapping.AfterStruct = true;
 407     Expanded.BraceWrapping.BeforeCatch = true;
 408     Expanded.BraceWrapping.BeforeElse = true;
 409     break;
 410   case FormatStyle::BS_GNU:
 411     Expanded.BraceWrapping = {true, true, true, true, true, true,
 412                               true, true, true, true, true};
 413     break;
 414   case FormatStyle::BS_WebKit:
 415     Expanded.BraceWrapping.AfterFunction = true;
 416     break;
 417   default:
 418     break;
 419   }
 420   return Expanded;
 421 }
 422
 423 FormatStyle getLLVMStyle() {
 424   FormatStyle LLVMStyle;
 425   LLVMStyle.Language = FormatStyle::LK_Cpp;
 426   LLVMStyle.AccessModifierOffset = -2;
 427   LLVMStyle.AlignEscapedNewlinesLeft = false;
 428   LLVMStyle.AlignAfterOpenBracket = true;
 429   LLVMStyle.AlignOperands = true;
 430   LLVMStyle.AlignTrailingComments = true;
 431   LLVMStyle.AlignConsecutiveAssignments = false;
 432   LLVMStyle.AlignConsecutiveDeclarations = false;
 433   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
 434   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
 435   LLVMStyle.AllowShortBlocksOnASingleLine = false;
 436   LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
 437   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
 438   LLVMStyle.AllowShortLoopsOnASingleLine = false;
 439   LLVMStyle.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
 440   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
 441   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
 442   LLVMStyle.BinPackParameters = true;
 443   LLVMStyle.BinPackArguments = true;
 444   LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
 445   LLVMStyle.BreakBeforeTernaryOperators = true;
 446   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
 447   LLVMStyle.BraceWrapping = {false, false, false, false, false, false,
 448                              false, false, false, false, false};
 449   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
 450   LLVMStyle.BreakAfterJavaFieldAnnotations = false;
 451   LLVMStyle.ColumnLimit = 80;
 452   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
 453   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
 454   LLVMStyle.ConstructorInitializerIndentWidth = 4;
 455   LLVMStyle.ContinuationIndentWidth = 4;
 456   LLVMStyle.Cpp11BracedListStyle = true;
 457   LLVMStyle.DerivePointerAlignment = false;
 458   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
 459   LLVMStyle.ForEachMacros.push_back("foreach");
 460   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
 461   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
 462   LLVMStyle.IncludeCategories = {{"^\"(llvm|llvm-c|clang|clang-c)/", 2},
 463                                  {"^(<|\"(gtest|isl|json)/)", 3},
 464                                  {".*", 1}};
 465   LLVMStyle.IndentCaseLabels = false;
 466   LLVMStyle.IndentWrappedFunctionNames = false;
 467   LLVMStyle.IndentWidth = 2;
 468   LLVMStyle.TabWidth = 8;
 469   LLVMStyle.MaxEmptyLinesToKeep = 1;
 470   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
 471   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
 472   LLVMStyle.ObjCBlockIndentWidth = 2;
 473   LLVMStyle.ObjCSpaceAfterProperty = false;
 474   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
 475   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
 476   LLVMStyle.SpacesBeforeTrailingComments = 1;
 477   LLVMStyle.Standard = FormatStyle::LS_Cpp11;
 478   LLVMStyle.UseTab = FormatStyle::UT_Never;
 479   LLVMStyle.SpacesInParentheses = false;
 480   LLVMStyle.SpacesInSquareBrackets = false;
 481   LLVMStyle.SpaceInEmptyParentheses = false;
 482   LLVMStyle.SpacesInContainerLiterals = true;
 483   LLVMStyle.SpacesInCStyleCastParentheses = false;
 484   LLVMStyle.SpaceAfterCStyleCast = false;
 485   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
 486   LLVMStyle.SpaceBeforeAssignmentOperators = true;
 487   LLVMStyle.SpacesInAngles = false;
 488
 489   LLVMStyle.PenaltyBreakComment = 300;
 490   LLVMStyle.PenaltyBreakFirstLessLess = 120;
 491   LLVMStyle.PenaltyBreakString = 1000;
 492   LLVMStyle.PenaltyExcessCharacter = 1000000;
 493   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
 494   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
 495
 496   LLVMStyle.DisableFormat = false;
 497
 498   return LLVMStyle;
 499 }
 500
 501 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
 502   FormatStyle GoogleStyle = getLLVMStyle();
 503   GoogleStyle.Language = Language;
 504
 505   GoogleStyle.AccessModifierOffset = -1;
 506   GoogleStyle.AlignEscapedNewlinesLeft = true;
 507   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
 508   GoogleStyle.AllowShortLoopsOnASingleLine = true;
 509   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
 510   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
 511   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
 512   GoogleStyle.DerivePointerAlignment = true;
 513   GoogleStyle.IncludeCategories = {{"^<.*\\.h>", 1}, {"^<.*", 2}, {".*", 3}};
 514   GoogleStyle.IndentCaseLabels = true;
 515   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
 516   GoogleStyle.ObjCSpaceAfterProperty = false;
 517   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
 518   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
 519   GoogleStyle.SpacesBeforeTrailingComments = 2;
 520   GoogleStyle.Standard = FormatStyle::LS_Auto;
 521
 522   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
 523   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
 524
 525   if (Language == FormatStyle::LK_Java) {
 526     GoogleStyle.AlignAfterOpenBracket = false;
 527     GoogleStyle.AlignOperands = false;
 528     GoogleStyle.AlignTrailingComments = false;
 529     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
 530     GoogleStyle.AllowShortIfStatementsOnASingleLine = false;
 531     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
 532     GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
 533     GoogleStyle.ColumnLimit = 100;
 534     GoogleStyle.SpaceAfterCStyleCast = true;
 535     GoogleStyle.SpacesBeforeTrailingComments = 1;
 536   } else if (Language == FormatStyle::LK_JavaScript) {
 537     GoogleStyle.BreakBeforeTernaryOperators = false;
 538     GoogleStyle.MaxEmptyLinesToKeep = 3;
 539     GoogleStyle.SpacesInContainerLiterals = false;
 540     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
 541     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
 542   } else if (Language == FormatStyle::LK_Proto) {
 543     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
 544     GoogleStyle.SpacesInContainerLiterals = false;
 545   }
 546
 547   return GoogleStyle;
 548 }
 549
 550 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
 551   FormatStyle ChromiumStyle = getGoogleStyle(Language);
 552   if (Language == FormatStyle::LK_Java) {
 553     ChromiumStyle.AllowShortIfStatementsOnASingleLine = true;
 554     ChromiumStyle.BreakAfterJavaFieldAnnotations = true;
 555     ChromiumStyle.ContinuationIndentWidth = 8;
 556     ChromiumStyle.IndentWidth = 4;
 557   } else {
 558     ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
 559     ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
 560     ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
 561     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
 562     ChromiumStyle.BinPackParameters = false;
 563     ChromiumStyle.DerivePointerAlignment = false;
 564   }
 565   return ChromiumStyle;
 566 }
 567
 568 FormatStyle getMozillaStyle() {
 569   FormatStyle MozillaStyle = getLLVMStyle();
 570   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
 571   MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
 572   MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
 573       FormatStyle::DRTBS_TopLevel;
 574   MozillaStyle.AlwaysBreakTemplateDeclarations = true;
 575   MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
 576   MozillaStyle.BreakConstructorInitializersBeforeComma = true;
 577   MozillaStyle.ConstructorInitializerIndentWidth = 2;
 578   MozillaStyle.ContinuationIndentWidth = 2;
 579   MozillaStyle.Cpp11BracedListStyle = false;
 580   MozillaStyle.IndentCaseLabels = true;
 581   MozillaStyle.ObjCSpaceAfterProperty = true;
 582   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
 583   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
 584   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
 585   return MozillaStyle;
 586 }
 587
 588 FormatStyle getWebKitStyle() {
 589   FormatStyle Style = getLLVMStyle();
 590   Style.AccessModifierOffset = -4;
 591   Style.AlignAfterOpenBracket = false;
 592   Style.AlignOperands = false;
 593   Style.AlignTrailingComments = false;
 594   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
 595   Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
 596   Style.BreakConstructorInitializersBeforeComma = true;
 597   Style.Cpp11BracedListStyle = false;
 598   Style.ColumnLimit = 0;
 599   Style.IndentWidth = 4;
 600   Style.NamespaceIndentation = FormatStyle::NI_Inner;
 601   Style.ObjCBlockIndentWidth = 4;
 602   Style.ObjCSpaceAfterProperty = true;
 603   Style.PointerAlignment = FormatStyle::PAS_Left;
 604   Style.Standard = FormatStyle::LS_Cpp03;
 605   return Style;
 606 }
 607
 608 FormatStyle getGNUStyle() {
 609   FormatStyle Style = getLLVMStyle();
 610   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
 611   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
 612   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
 613   Style.BreakBeforeTernaryOperators = true;
 614   Style.Cpp11BracedListStyle = false;
 615   Style.ColumnLimit = 79;
 616   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
 617   Style.Standard = FormatStyle::LS_Cpp03;
 618   return Style;
 619 }
 620
 621 FormatStyle getNoStyle() {
 622   FormatStyle NoStyle = getLLVMStyle();
 623   NoStyle.DisableFormat = true;
 624   return NoStyle;
 625 }
 626
 627 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
 628                         FormatStyle *Style) {
 629   if (Name.equals_lower("llvm")) {
 630     *Style = getLLVMStyle();
 631   } else if (Name.equals_lower("chromium")) {
 632     *Style = getChromiumStyle(Language);
 633   } else if (Name.equals_lower("mozilla")) {
 634     *Style = getMozillaStyle();
 635   } else if (Name.equals_lower("google")) {
 636     *Style = getGoogleStyle(Language);
 637   } else if (Name.equals_lower("webkit")) {
 638     *Style = getWebKitStyle();
 639   } else if (Name.equals_lower("gnu")) {
 640     *Style = getGNUStyle();
 641   } else if (Name.equals_lower("none")) {
 642     *Style = getNoStyle();
 643   } else {
 644     return false;
 645   }
 646
 647   Style->Language = Language;
 648   return true;
 649 }
 650
 651 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
 652   assert(Style);
 653   FormatStyle::LanguageKind Language = Style->Language;
 654   assert(Language != FormatStyle::LK_None);
 655   if (Text.trim().empty())
 656     return make_error_code(ParseError::Error);
 657
 658   std::vector<FormatStyle> Styles;
 659   llvm::yaml::Input Input(Text);
 660   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
 661   // values for the fields, keys for which are missing from the configuration.
 662   // Mapping also uses the context to get the language to find the correct
 663   // base style.
 664   Input.setContext(Style);
 665   Input >> Styles;
 666   if (Input.error())
 667     return Input.error();
 668
 669   for (unsigned i = 0; i < Styles.size(); ++i) {
 670     // Ensures that only the first configuration can skip the Language option.
 671     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
 672       return make_error_code(ParseError::Error);
 673     // Ensure that each language is configured at most once.
 674     for (unsigned j = 0; j < i; ++j) {
 675       if (Styles[i].Language == Styles[j].Language) {
 676         DEBUG(llvm::dbgs()
 677               << "Duplicate languages in the config file on positions " << j
 678               << " and " << i << "\n");
 679         return make_error_code(ParseError::Error);
 680       }
 681     }
 682   }
 683   // Look for a suitable configuration starting from the end, so we can
 684   // find the configuration for the specific language first, and the default
 685   // configuration (which can only be at slot 0) after it.
 686   for (int i = Styles.size() - 1; i >= 0; --i) {
 687     if (Styles[i].Language == Language ||
 688         Styles[i].Language == FormatStyle::LK_None) {
 689       *Style = Styles[i];
 690       Style->Language = Language;
 691       return make_error_code(ParseError::Success);
 692     }
 693   }
 694   return make_error_code(ParseError::Unsuitable);
 695 }
 696
 697 std::string configurationAsText(const FormatStyle &Style) {
 698   std::string Text;
 699   llvm::raw_string_ostream Stream(Text);
 700   llvm::yaml::Output Output(Stream);
 701   // We use the same mapping method for input and output, so we need a non-const
 702   // reference here.
 703   FormatStyle NonConstStyle = expandPresets(Style);
 704   Output << NonConstStyle;
 705   return Stream.str();
 706 }
 707
 708 namespace {
 709
 710 class FormatTokenLexer {
 711 public:
 712   FormatTokenLexer(SourceManager &SourceMgr, FileID ID, FormatStyle &Style,
 713                    encoding::Encoding Encoding)
 714       : FormatTok(nullptr), IsFirstToken(true), GreaterStashed(false),
 715         LessStashed(false), Column(0), TrailingWhitespace(0),
 716         SourceMgr(SourceMgr), ID(ID), Style(Style),
 717         IdentTable(getFormattingLangOpts(Style)), Keywords(IdentTable),
 718         Encoding(Encoding), FirstInLineIndex(0), FormattingDisabled(false),
 719         MacroBlockBeginRegex(Style.MacroBlockBegin),
 720         MacroBlockEndRegex(Style.MacroBlockEnd) {
 721     Lex.reset(new Lexer(ID, SourceMgr.getBuffer(ID), SourceMgr,
 722                         getFormattingLangOpts(Style)));
 723     Lex->SetKeepWhitespaceMode(true);
 724
 725     for (const std::string &ForEachMacro : Style.ForEachMacros)
 726       ForEachMacros.push_back(&IdentTable.get(ForEachMacro));
 727     std::sort(ForEachMacros.begin(), ForEachMacros.end());
 728   }
 729
 730   ArrayRef<FormatToken *> lex() {
 731     assert(Tokens.empty());
 732     assert(FirstInLineIndex == 0);
 733     do {
 734       Tokens.push_back(getNextToken());
 735       if (Style.Language == FormatStyle::LK_JavaScript)
 736         tryParseJSRegexLiteral();
 737       tryMergePreviousTokens();
 738       if (Tokens.back()->NewlinesBefore > 0 || Tokens.back()->IsMultiline)
 739         FirstInLineIndex = Tokens.size() - 1;
 740     } while (Tokens.back()->Tok.isNot(tok::eof));
 741     return Tokens;
 742   }
 743
 744   const AdditionalKeywords &getKeywords() { return Keywords; }
 745
 746 private:
 747   void tryMergePreviousTokens() {
 748     if (tryMerge_TMacro())
 749       return;
 750     if (tryMergeConflictMarkers())
 751       return;
 752     if (tryMergeLessLess())
 753       return;
 754
 755     if (Style.Language == FormatStyle::LK_JavaScript) {
 756       if (tryMergeTemplateString())
 757         return;
 758
 759       static const tok::TokenKind JSIdentity[] = {tok::equalequal, tok::equal};
 760       static const tok::TokenKind JSNotIdentity[] = {tok::exclaimequal,
 761                                                      tok::equal};
 762       static const tok::TokenKind JSShiftEqual[] = {tok::greater, tok::greater,
 763                                                     tok::greaterequal};
 764       static const tok::TokenKind JSRightArrow[] = {tok::equal, tok::greater};
 765       // FIXME: Investigate what token type gives the correct operator priority.
 766       if (tryMergeTokens(JSIdentity, TT_BinaryOperator))
 767         return;
 768       if (tryMergeTokens(JSNotIdentity, TT_BinaryOperator))
 769         return;
 770       if (tryMergeTokens(JSShiftEqual, TT_BinaryOperator))
 771         return;
 772       if (tryMergeTokens(JSRightArrow, TT_JsFatArrow))
 773         return;
 774     }
 775   }
 776
 777   bool tryMergeLessLess() {
 778     // Merge X,less,less,Y into X,lessless,Y unless X or Y is less.
 779     if (Tokens.size() < 3)
 780       return false;
 781
 782     bool FourthTokenIsLess = false;
 783     if (Tokens.size() > 3)
 784       FourthTokenIsLess = (Tokens.end() - 4)[0]->is(tok::less);
 785
 786     auto First = Tokens.end() - 3;
 787     if (First[2]->is(tok::less) || First[1]->isNot(tok::less) ||
 788         First[0]->isNot(tok::less) || FourthTokenIsLess)
 789       return false;
 790
 791     // Only merge if there currently is no whitespace between the two "<".
 792     if (First[1]->WhitespaceRange.getBegin() !=
 793         First[1]->WhitespaceRange.getEnd())
 794       return false;
 795
 796     First[0]->Tok.setKind(tok::lessless);
 797     First[0]->TokenText = "<<";
 798     First[0]->ColumnWidth += 1;
 799     Tokens.erase(Tokens.end() - 2);
 800     return true;
 801   }
 802
 803   bool tryMergeTokens(ArrayRef<tok::TokenKind> Kinds, TokenType NewType) {
 804     if (Tokens.size() < Kinds.size())
 805       return false;
 806
 807     SmallVectorImpl<FormatToken *>::const_iterator First =
 808         Tokens.end() - Kinds.size();
 809     if (!First[0]->is(Kinds[0]))
 810       return false;
 811     unsigned AddLength = 0;
 812     for (unsigned i = 1; i < Kinds.size(); ++i) {
 813       if (!First[i]->is(Kinds[i]) ||
 814           First[i]->WhitespaceRange.getBegin() !=
 815               First[i]->WhitespaceRange.getEnd())
 816         return false;
 817       AddLength += First[i]->TokenText.size();
 818     }
 819     Tokens.resize(Tokens.size() - Kinds.size() + 1);
 820     First[0]->TokenText = StringRef(First[0]->TokenText.data(),
 821                                     First[0]->TokenText.size() + AddLength);
 822     First[0]->ColumnWidth += AddLength;
 823     First[0]->Type = NewType;
 824     return true;
 825   }
 826
 827   // Returns \c true if \p Tok can only be followed by an operand in JavaScript.
 828   bool precedesOperand(FormatToken *Tok) {
 829     // NB: This is not entirely correct, as an r_paren can introduce an operand
 830     // location in e.g. `if (foo) /bar/.exec(...);`. That is a rare enough
 831     // corner case to not matter in practice, though.
 832     return Tok->isOneOf(tok::period, tok::l_paren, tok::comma, tok::l_brace,
 833                         tok::r_brace, tok::l_square, tok::semi, tok::exclaim,
 834                         tok::colon, tok::question, tok::tilde) ||
 835            Tok->isOneOf(tok::kw_return, tok::kw_do, tok::kw_case, tok::kw_throw,
 836                         tok::kw_else, tok::kw_new, tok::kw_delete, tok::kw_void,
 837                         tok::kw_typeof, Keywords.kw_instanceof,
 838                         Keywords.kw_in) ||
 839            Tok->isBinaryOperator();
 840   }
 841
 842   bool canPrecedeRegexLiteral(FormatToken *Prev) {
 843     if (!Prev)
 844       return true;
 845
 846     // Regex literals can only follow after prefix unary operators, not after
 847     // postfix unary operators. If the '++' is followed by a non-operand
 848     // introducing token, the slash here is the operand and not the start of a
 849     // regex.
 850     if (Prev->isOneOf(tok::plusplus, tok::minusminus))
 851       return (Tokens.size() < 3 || precedesOperand(Tokens[Tokens.size() - 3]));
 852
 853     // The previous token must introduce an operand location where regex
 854     // literals can occur.
 855     if (!precedesOperand(Prev))
 856       return false;
 857
 858     return true;
 859   }
 860
 861   // Tries to parse a JavaScript Regex literal starting at the current token,
 862   // if that begins with a slash and is in a location where JavaScript allows
 863   // regex literals. Changes the current token to a regex literal and updates
 864   // its text if successful.
 865   void tryParseJSRegexLiteral() {
 866     FormatToken *RegexToken = Tokens.back();
 867     if (!RegexToken->isOneOf(tok::slash, tok::slashequal))
 868       return;
 869
 870     FormatToken *Prev = nullptr;
 871     for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; ++I) {
 872       // NB: Because previous pointers are not initialized yet, this cannot use
 873       // Token.getPreviousNonComment.
 874       if ((*I)->isNot(tok::comment)) {
 875         Prev = *I;
 876         break;
 877       }
 878     }
 879
 880     if (!canPrecedeRegexLiteral(Prev))
 881       return;
 882
 883     // 'Manually' lex ahead in the current file buffer.
 884     const char *Offset = Lex->getBufferLocation();
 885     const char *RegexBegin = Offset - RegexToken->TokenText.size();
 886     StringRef Buffer = Lex->getBuffer();
 887     bool InCharacterClass = false;
 888     bool HaveClosingSlash = false;
 889     for (; !HaveClosingSlash && Offset != Buffer.end(); ++Offset) {
 890       // Regular expressions are terminated with a '/', which can only be
 891       // escaped using '\' or a character class between '[' and ']'.
 892       // See http://www.ecma-international.org/ecma-262/5.1/#sec-7.8.5.
 893       switch (*Offset) {
 894       case '\\':
 895         // Skip the escaped character.
 896         ++Offset;
 897         break;
 898       case '[':
 899         InCharacterClass = true;
 900         break;
 901       case ']':
 902         InCharacterClass = false;
 903         break;
 904       case '/':
 905         if (!InCharacterClass)
 906           HaveClosingSlash = true;
 907         break;
 908       }
 909     }
 910
 911     RegexToken->Type = TT_RegexLiteral;
 912     // Treat regex literals like other string_literals.
 913     RegexToken->Tok.setKind(tok::string_literal);
 914     RegexToken->TokenText = StringRef(RegexBegin, Offset - RegexBegin);
 915     RegexToken->ColumnWidth = RegexToken->TokenText.size();
 916
 917     resetLexer(SourceMgr.getFileOffset(Lex->getSourceLocation(Offset)));
 918   }
 919
 920   bool tryMergeTemplateString() {
 921     if (Tokens.size() < 2)
 922       return false;
 923
 924     FormatToken *EndBacktick = Tokens.back();
 925     // Backticks get lexed as tok::unknown tokens. If a template string contains
 926     // a comment start, it gets lexed as a tok::comment, or tok::unknown if
 927     // unterminated.
 928     if (!EndBacktick->isOneOf(tok::comment, tok::string_literal,
 929                               tok::char_constant, tok::unknown))
 930       return false;
 931     size_t CommentBacktickPos = EndBacktick->TokenText.find('`');
 932     // Unknown token that's not actually a backtick, or a comment that doesn't
 933     // contain a backtick.
 934     if (CommentBacktickPos == StringRef::npos)
 935       return false;
 936
 937     unsigned TokenCount = 0;
 938     bool IsMultiline = false;
 939     unsigned EndColumnInFirstLine =
 940         EndBacktick->OriginalColumn + EndBacktick->ColumnWidth;
 941     for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; I++) {
 942       ++TokenCount;
 943       if (I[0]->IsMultiline)
 944         IsMultiline = true;
 945
 946       // If there was a preceding template string, this must be the start of a
 947       // template string, not the end.
 948       if (I[0]->is(TT_TemplateString))
 949         return false;
 950
 951       if (I[0]->isNot(tok::unknown) || I[0]->TokenText != "`") {
 952         // Keep track of the rhs offset of the last token to wrap across lines -
 953         // its the rhs offset of the first line of the template string, used to
 954         // determine its width.
 955         if (I[0]->IsMultiline)
 956           EndColumnInFirstLine = I[0]->OriginalColumn + I[0]->ColumnWidth;
 957         // If the token has newlines, the token before it (if it exists) is the
 958         // rhs end of the previous line.
 959         if (I[0]->NewlinesBefore > 0 && (I + 1 != E)) {
 960           EndColumnInFirstLine = I[1]->OriginalColumn + I[1]->ColumnWidth;
 961           IsMultiline = true;
 962         }
 963         continue;
 964       }
 965
 966       Tokens.resize(Tokens.size() - TokenCount);
 967       Tokens.back()->Type = TT_TemplateString;
 968       const char *EndOffset =
 969           EndBacktick->TokenText.data() + 1 + CommentBacktickPos;
 970       if (CommentBacktickPos != 0) {
 971         // If the backtick was not the first character (e.g. in a comment),
 972         // re-lex after the backtick position.
 973         SourceLocation Loc = EndBacktick->Tok.getLocation();
 974         resetLexer(SourceMgr.getFileOffset(Loc) + CommentBacktickPos + 1);
 975       }
 976       Tokens.back()->TokenText =
 977           StringRef(Tokens.back()->TokenText.data(),
 978                     EndOffset - Tokens.back()->TokenText.data());
 979
 980       unsigned EndOriginalColumn = EndBacktick->OriginalColumn;
 981       if (EndOriginalColumn == 0) {
 982         SourceLocation Loc = EndBacktick->Tok.getLocation();
 983         EndOriginalColumn = SourceMgr.getSpellingColumnNumber(Loc);
 984       }
 985       // If the ` is further down within the token (e.g. in a comment).
 986       EndOriginalColumn += CommentBacktickPos;
 987
 988       if (IsMultiline) {
 989         // ColumnWidth is from backtick to last token in line.
 990         // LastLineColumnWidth is 0 to backtick.
 991         // x = `some content
 992         //     until here`;
 993         Tokens.back()->ColumnWidth =
 994             EndColumnInFirstLine - Tokens.back()->OriginalColumn;
 995         // +1 for the ` itself.
 996         Tokens.back()->LastLineColumnWidth = EndOriginalColumn + 1;
 997         Tokens.back()->IsMultiline = true;
 998       } else {
 999         // Token simply spans from start to end, +1 for the ` itself.
1000         Tokens.back()->ColumnWidth =
1001             EndOriginalColumn - Tokens.back()->OriginalColumn + 1;
1002       }
1003       return true;
1004     }
1005     return false;
1006   }
1007
1008   bool tryMerge_TMacro() {
1009     if (Tokens.size() < 4)
1010       return false;
1011     FormatToken *Last = Tokens.back();
1012     if (!Last->is(tok::r_paren))
1013       return false;
1014
1015     FormatToken *String = Tokens[Tokens.size() - 2];
1016     if (!String->is(tok::string_literal) || String->IsMultiline)
1017       return false;
1018
1019     if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
1020       return false;
1021
1022     FormatToken *Macro = Tokens[Tokens.size() - 4];
1023     if (Macro->TokenText != "_T")
1024       return false;
1025
1026     const char *Start = Macro->TokenText.data();
1027     const char *End = Last->TokenText.data() + Last->TokenText.size();
1028     String->TokenText = StringRef(Start, End - Start);
1029     String->IsFirst = Macro->IsFirst;
1030     String->LastNewlineOffset = Macro->LastNewlineOffset;
1031     String->WhitespaceRange = Macro->WhitespaceRange;
1032     String->OriginalColumn = Macro->OriginalColumn;
1033     String->ColumnWidth = encoding::columnWidthWithTabs(
1034         String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
1035     String->NewlinesBefore = Macro->NewlinesBefore;
1036     String->HasUnescapedNewline = Macro->HasUnescapedNewline;
1037
1038     Tokens.pop_back();
1039     Tokens.pop_back();
1040     Tokens.pop_back();
1041     Tokens.back() = String;
1042     return true;
1043   }
1044
1045   bool tryMergeConflictMarkers() {
1046     if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(tok::eof))
1047       return false;
1048
1049     // Conflict lines look like:
1050     // <marker> <text from the vcs>
1051     // For example:
1052     // >>>>>>> /file/in/file/system at revision 1234
1053     //
1054     // We merge all tokens in a line that starts with a conflict marker
1055     // into a single token with a special token type that the unwrapped line
1056     // parser will use to correctly rebuild the underlying code.
1057
1058     FileID ID;
1059     // Get the position of the first token in the line.
1060     unsigned FirstInLineOffset;
1061     std::tie(ID, FirstInLineOffset) = SourceMgr.getDecomposedLoc(
1062         Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
1063     StringRef Buffer = SourceMgr.getBuffer(ID)->getBuffer();
1064     // Calculate the offset of the start of the current line.
1065     auto LineOffset = Buffer.rfind('\n', FirstInLineOffset);
1066     if (LineOffset == StringRef::npos) {
1067       LineOffset = 0;
1068     } else {
1069       ++LineOffset;
1070     }
1071
1072     auto FirstSpace = Buffer.find_first_of(" \n", LineOffset);
1073     StringRef LineStart;
1074     if (FirstSpace == StringRef::npos) {
1075       LineStart = Buffer.substr(LineOffset);
1076     } else {
1077       LineStart = Buffer.substr(LineOffset, FirstSpace - LineOffset);
1078     }
1079
1080     TokenType Type = TT_Unknown;
1081     if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
1082       Type = TT_ConflictStart;
1083     } else if (LineStart == "|||||||" || LineStart == "=======" ||
1084                LineStart == "====") {
1085       Type = TT_ConflictAlternative;
1086     } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
1087       Type = TT_ConflictEnd;
1088     }
1089
1090     if (Type != TT_Unknown) {
1091       FormatToken *Next = Tokens.back();
1092
1093       Tokens.resize(FirstInLineIndex + 1);
1094       // We do not need to build a complete token here, as we will skip it
1095       // during parsing anyway (as we must not touch whitespace around conflict
1096       // markers).
1097       Tokens.back()->Type = Type;
1098       Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
1099
1100       Tokens.push_back(Next);
1101       return true;
1102     }
1103
1104     return false;
1105   }
1106
1107   FormatToken *getStashedToken() {
1108     // Create a synthesized second '>' or '<' token.
1109     Token Tok = FormatTok->Tok;
1110     StringRef TokenText = FormatTok->TokenText;
1111
1112     unsigned OriginalColumn = FormatTok->OriginalColumn;
1113     FormatTok = new (Allocator.Allocate()) FormatToken;
1114     FormatTok->Tok = Tok;
1115     SourceLocation TokLocation =
1116         FormatTok->Tok.getLocation().getLocWithOffset(Tok.getLength() - 1);
1117     FormatTok->Tok.setLocation(TokLocation);
1118     FormatTok->WhitespaceRange = SourceRange(TokLocation, TokLocation);
1119     FormatTok->TokenText = TokenText;
1120     FormatTok->ColumnWidth = 1;
1121     FormatTok->OriginalColumn = OriginalColumn + 1;
1122
1123     return FormatTok;
1124   }
1125
1126   FormatToken *getNextToken() {
1127     if (GreaterStashed) {
1128       GreaterStashed = false;
1129       return getStashedToken();
1130     }
1131     if (LessStashed) {
1132       LessStashed = false;
1133       return getStashedToken();
1134     }
1135
1136     FormatTok = new (Allocator.Allocate()) FormatToken;
1137     readRawToken(*FormatTok);
1138     SourceLocation WhitespaceStart =
1139         FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
1140     FormatTok->IsFirst = IsFirstToken;
1141     IsFirstToken = false;
1142
1143     // Consume and record whitespace until we find a significant token.
1144     unsigned WhitespaceLength = TrailingWhitespace;
1145     while (FormatTok->Tok.is(tok::unknown)) {
1146       StringRef Text = FormatTok->TokenText;
1147       auto EscapesNewline = [&](int pos) {
1148         // A '\r' here is just part of '\r\n'. Skip it.
1149         if (pos >= 0 && Text[pos] == '\r')
1150           --pos;
1151         // See whether there is an odd number of '\' before this.
1152         unsigned count = 0;
1153         for (; pos >= 0; --pos, ++count)
1154           if (Text[pos] != '\\')
1155             break;
1156         return count & 1;
1157       };
1158       // FIXME: This miscounts tok:unknown tokens that are not just
1159       // whitespace, e.g. a '`' character.
1160       for (int i = 0, e = Text.size(); i != e; ++i) {
1161         switch (Text[i]) {
1162         case '\n':
1163           ++FormatTok->NewlinesBefore;
1164           FormatTok->HasUnescapedNewline = !EscapesNewline(i - 1);
1165           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1166           Column = 0;
1167           break;
1168         case '\r':
1169           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1170           Column = 0;
1171           break;
1172         case '\f':
1173         case '\v':
1174           Column = 0;
1175           break;
1176         case ' ':
1177           ++Column;
1178           break;
1179         case '\t':
1180           Column += Style.TabWidth - Column % Style.TabWidth;
1181           break;
1182         case '\\':
1183           if (i + 1 == e || (Text[i + 1] != '\r' && Text[i + 1] != '\n'))
1184             FormatTok->Type = TT_ImplicitStringLiteral;
1185           break;
1186         default:
1187           FormatTok->Type = TT_ImplicitStringLiteral;
1188           break;
1189         }
1190       }
1191
1192       if (FormatTok->is(TT_ImplicitStringLiteral))
1193         break;
1194       WhitespaceLength += FormatTok->Tok.getLength();
1195
1196       readRawToken(*FormatTok);
1197     }
1198
1199     // In case the token starts with escaped newlines, we want to
1200     // take them into account as whitespace - this pattern is quite frequent
1201     // in macro definitions.
1202     // FIXME: Add a more explicit test.
1203     while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
1204            FormatTok->TokenText[1] == '\n') {
1205       ++FormatTok->NewlinesBefore;
1206       WhitespaceLength += 2;
1207       FormatTok->LastNewlineOffset = 2;
1208       Column = 0;
1209       FormatTok->TokenText = FormatTok->TokenText.substr(2);
1210     }
1211
1212     FormatTok->WhitespaceRange = SourceRange(
1213         WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1214
1215     FormatTok->OriginalColumn = Column;
1216
1217     TrailingWhitespace = 0;
1218     if (FormatTok->Tok.is(tok::comment)) {
1219       // FIXME: Add the trimmed whitespace to Column.
1220       StringRef UntrimmedText = FormatTok->TokenText;
1221       FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
1222       TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1223     } else if (FormatTok->Tok.is(tok::raw_identifier)) {
1224       IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
1225       FormatTok->Tok.setIdentifierInfo(&Info);
1226       FormatTok->Tok.setKind(Info.getTokenID());
1227       if (Style.Language == FormatStyle::LK_Java &&
1228           FormatTok->isOneOf(tok::kw_struct, tok::kw_union, tok::kw_delete)) {
1229         FormatTok->Tok.setKind(tok::identifier);
1230         FormatTok->Tok.setIdentifierInfo(nullptr);
1231       }
1232     } else if (FormatTok->Tok.is(tok::greatergreater)) {
1233       FormatTok->Tok.setKind(tok::greater);
1234       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1235       GreaterStashed = true;
1236     } else if (FormatTok->Tok.is(tok::lessless)) {
1237       FormatTok->Tok.setKind(tok::less);
1238       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1239       LessStashed = true;
1240     }
1241
1242     // Now FormatTok is the next non-whitespace token.
1243
1244     StringRef Text = FormatTok->TokenText;
1245     size_t FirstNewlinePos = Text.find('\n');
1246     if (FirstNewlinePos == StringRef::npos) {
1247       // FIXME: ColumnWidth actually depends on the start column, we need to
1248       // take this into account when the token is moved.
1249       FormatTok->ColumnWidth =
1250           encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
1251       Column += FormatTok->ColumnWidth;
1252     } else {
1253       FormatTok->IsMultiline = true;
1254       // FIXME: ColumnWidth actually depends on the start column, we need to
1255       // take this into account when the token is moved.
1256       FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1257           Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
1258
1259       // The last line of the token always starts in column 0.
1260       // Thus, the length can be precomputed even in the presence of tabs.
1261       FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1262           Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
1263           Encoding);
1264       Column = FormatTok->LastLineColumnWidth;
1265     }
1266
1267     if (Style.Language == FormatStyle::LK_Cpp) {
1268       if (!(Tokens.size() > 0 && Tokens.back()->Tok.getIdentifierInfo() &&
1269             Tokens.back()->Tok.getIdentifierInfo()->getPPKeywordID() ==
1270                 tok::pp_define) &&
1271           std::find(ForEachMacros.begin(), ForEachMacros.end(),
1272                     FormatTok->Tok.getIdentifierInfo()) != ForEachMacros.end()) {
1273         FormatTok->Type = TT_ForEachMacro;
1274       } else if (FormatTok->is(tok::identifier)) {
1275         if (MacroBlockBeginRegex.match(Text)) {
1276           FormatTok->Type = TT_MacroBlockBegin;
1277         } else if (MacroBlockEndRegex.match(Text)) {
1278           FormatTok->Type = TT_MacroBlockEnd;
1279         }
1280       }
1281     }
1282
1283     return FormatTok;
1284   }
1285
1286   FormatToken *FormatTok;
1287   bool IsFirstToken;
1288   bool GreaterStashed, LessStashed;
1289   unsigned Column;
1290   unsigned TrailingWhitespace;
1291   std::unique_ptr<Lexer> Lex;
1292   SourceManager &SourceMgr;
1293   FileID ID;
1294   FormatStyle &Style;
1295   IdentifierTable IdentTable;
1296   AdditionalKeywords Keywords;
1297   encoding::Encoding Encoding;
1298   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
1299   // Index (in 'Tokens') of the last token that starts a new line.
1300   unsigned FirstInLineIndex;
1301   SmallVector<FormatToken *, 16> Tokens;
1302   SmallVector<IdentifierInfo *, 8> ForEachMacros;
1303
1304   bool FormattingDisabled;
1305
1306   llvm::Regex MacroBlockBeginRegex;
1307   llvm::Regex MacroBlockEndRegex;
1308
1309   void readRawToken(FormatToken &Tok) {
1310     Lex->LexFromRawLexer(Tok.Tok);
1311     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
1312                               Tok.Tok.getLength());
1313     // For formatting, treat unterminated string literals like normal string
1314     // literals.
1315     if (Tok.is(tok::unknown)) {
1316       if (!Tok.TokenText.empty() && Tok.TokenText[0] == '"') {
1317         Tok.Tok.setKind(tok::string_literal);
1318         Tok.IsUnterminatedLiteral = true;
1319       } else if (Style.Language == FormatStyle::LK_JavaScript &&
1320                  Tok.TokenText == "''") {
1321         Tok.Tok.setKind(tok::char_constant);
1322       }
1323     }
1324
1325     if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format on" ||
1326                                  Tok.TokenText == "/* clang-format on */")) {
1327       FormattingDisabled = false;
1328     }
1329
1330     Tok.Finalized = FormattingDisabled;
1331
1332     if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format off" ||
1333                                  Tok.TokenText == "/* clang-format off */")) {
1334       FormattingDisabled = true;
1335     }
1336   }
1337
1338   void resetLexer(unsigned Offset) {
1339     StringRef Buffer = SourceMgr.getBufferData(ID);
1340     Lex.reset(new Lexer(SourceMgr.getLocForStartOfFile(ID),
1341                         getFormattingLangOpts(Style), Buffer.begin(),
1342                         Buffer.begin() + Offset, Buffer.end()));
1343     Lex->SetKeepWhitespaceMode(true);
1344     TrailingWhitespace = 0;
1345   }
1346 };
1347
1348 static StringRef getLanguageName(FormatStyle::LanguageKind Language) {
1349   switch (Language) {
1350   case FormatStyle::LK_Cpp:
1351     return "C++";
1352   case FormatStyle::LK_Java:
1353     return "Java";
1354   case FormatStyle::LK_JavaScript:
1355     return "JavaScript";
1356   case FormatStyle::LK_Proto:
1357     return "Proto";
1358   default:
1359     return "Unknown";
1360   }
1361 }
1362
1363 class Formatter : public UnwrappedLineConsumer {
1364 public:
1365   Formatter(const FormatStyle &Style, SourceManager &SourceMgr, FileID ID,
1366             ArrayRef<CharSourceRange> Ranges)
1367       : Style(Style), ID(ID), SourceMgr(SourceMgr),
1368         Whitespaces(SourceMgr, Style,
1369                     inputUsesCRLF(SourceMgr.getBufferData(ID))),
1370         Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1),
1371         Encoding(encoding::detectEncoding(SourceMgr.getBufferData(ID))) {
1372     DEBUG(llvm::dbgs() << "File encoding: "
1373                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
1374                                                                : "unknown")
1375                        << "\n");
1376     DEBUG(llvm::dbgs() << "Language: " << getLanguageName(Style.Language)
1377                        << "\n");
1378   }
1379
1380   tooling::Replacements format(bool *IncompleteFormat) {
1381     tooling::Replacements Result;
1382     FormatTokenLexer Tokens(SourceMgr, ID, Style, Encoding);
1383
1384     UnwrappedLineParser Parser(Style, Tokens.getKeywords(), Tokens.lex(),
1385                                *this);
1386     Parser.parse();
1387     assert(UnwrappedLines.rbegin()->empty());
1388     for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
1389          ++Run) {
1390       DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
1391       SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1392       for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
1393         AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
1394       }
1395       tooling::Replacements RunResult =
1396           format(AnnotatedLines, Tokens, IncompleteFormat);
1397       DEBUG({
1398         llvm::dbgs() << "Replacements for run " << Run << ":\n";
1399         for (tooling::Replacements::iterator I = RunResult.begin(),
1400                                              E = RunResult.end();
1401              I != E; ++I) {
1402           llvm::dbgs() << I->toString() << "\n";
1403         }
1404       });
1405       for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1406         delete AnnotatedLines[i];
1407       }
1408       Result.insert(RunResult.begin(), RunResult.end());
1409       Whitespaces.reset();
1410     }
1411     return Result;
1412   }
1413
1414   tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1415                                FormatTokenLexer &Tokens,
1416                                bool *IncompleteFormat) {
1417     TokenAnnotator Annotator(Style, Tokens.getKeywords());
1418     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1419       Annotator.annotate(*AnnotatedLines[i]);
1420     }
1421     deriveLocalStyle(AnnotatedLines);
1422     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1423       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1424     }
1425     computeAffectedLines(AnnotatedLines.begin(), AnnotatedLines.end());
1426
1427     Annotator.setCommentLineLevels(AnnotatedLines);
1428     ContinuationIndenter Indenter(Style, Tokens.getKeywords(), SourceMgr,
1429                                   Whitespaces, Encoding,
1430                                   BinPackInconclusiveFunctions);
1431     UnwrappedLineFormatter(&Indenter, &Whitespaces, Style, Tokens.getKeywords(),
1432                            IncompleteFormat)
1433         .format(AnnotatedLines);
1434     return Whitespaces.generateReplacements();
1435   }
1436
1437 private:
1438   // Determines which lines are affected by the SourceRanges given as input.
1439   // Returns \c true if at least one line between I and E or one of their
1440   // children is affected.
1441   bool computeAffectedLines(SmallVectorImpl<AnnotatedLine *>::iterator I,
1442                             SmallVectorImpl<AnnotatedLine *>::iterator E) {
1443     bool SomeLineAffected = false;
1444     const AnnotatedLine *PreviousLine = nullptr;
1445     while (I != E) {
1446       AnnotatedLine *Line = *I;
1447       Line->LeadingEmptyLinesAffected = affectsLeadingEmptyLines(*Line->First);
1448
1449       // If a line is part of a preprocessor directive, it needs to be formatted
1450       // if any token within the directive is affected.
1451       if (Line->InPPDirective) {
1452         FormatToken *Last = Line->Last;
1453         SmallVectorImpl<AnnotatedLine *>::iterator PPEnd = I + 1;
1454         while (PPEnd != E && !(*PPEnd)->First->HasUnescapedNewline) {
1455           Last = (*PPEnd)->Last;
1456           ++PPEnd;
1457         }
1458
1459         if (affectsTokenRange(*Line->First, *Last,
1460                               /*IncludeLeadingNewlines=*/false)) {
1461           SomeLineAffected = true;
1462           markAllAsAffected(I, PPEnd);
1463         }
1464         I = PPEnd;
1465         continue;
1466       }
1467
1468       if (nonPPLineAffected(Line, PreviousLine))
1469         SomeLineAffected = true;
1470
1471       PreviousLine = Line;
1472       ++I;
1473     }
1474     return SomeLineAffected;
1475   }
1476
1477   // Determines whether 'Line' is affected by the SourceRanges given as input.
1478   // Returns \c true if line or one if its children is affected.
1479   bool nonPPLineAffected(AnnotatedLine *Line,
1480                          const AnnotatedLine *PreviousLine) {
1481     bool SomeLineAffected = false;
1482     Line->ChildrenAffected =
1483         computeAffectedLines(Line->Children.begin(), Line->Children.end());
1484     if (Line->ChildrenAffected)
1485       SomeLineAffected = true;
1486
1487     // Stores whether one of the line's tokens is directly affected.
1488     bool SomeTokenAffected = false;
1489     // Stores whether we need to look at the leading newlines of the next token
1490     // in order to determine whether it was affected.
1491     bool IncludeLeadingNewlines = false;
1492
1493     // Stores whether the first child line of any of this line's tokens is
1494     // affected.
1495     bool SomeFirstChildAffected = false;
1496
1497     for (FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
1498       // Determine whether 'Tok' was affected.
1499       if (affectsTokenRange(*Tok, *Tok, IncludeLeadingNewlines))
1500         SomeTokenAffected = true;
1501
1502       // Determine whether the first child of 'Tok' was affected.
1503       if (!Tok->Children.empty() && Tok->Children.front()->Affected)
1504         SomeFirstChildAffected = true;
1505
1506       IncludeLeadingNewlines = Tok->Children.empty();
1507     }
1508
1509     // Was this line moved, i.e. has it previously been on the same line as an
1510     // affected line?
1511     bool LineMoved = PreviousLine && PreviousLine->Affected &&
1512                      Line->First->NewlinesBefore == 0;
1513
1514     bool IsContinuedComment =
1515         Line->First->is(tok::comment) && Line->First->Next == nullptr &&
1516         Line->First->NewlinesBefore < 2 && PreviousLine &&
1517         PreviousLine->Affected && PreviousLine->Last->is(tok::comment);
1518
1519     if (SomeTokenAffected || SomeFirstChildAffected || LineMoved ||
1520         IsContinuedComment) {
1521       Line->Affected = true;
1522       SomeLineAffected = true;
1523     }
1524     return SomeLineAffected;
1525   }
1526
1527   // Marks all lines between I and E as well as all their children as affected.
1528   void markAllAsAffected(SmallVectorImpl<AnnotatedLine *>::iterator I,
1529                          SmallVectorImpl<AnnotatedLine *>::iterator E) {
1530     while (I != E) {
1531       (*I)->Affected = true;
1532       markAllAsAffected((*I)->Children.begin(), (*I)->Children.end());
1533       ++I;
1534     }
1535   }
1536
1537   // Returns true if the range from 'First' to 'Last' intersects with one of the
1538   // input ranges.
1539   bool affectsTokenRange(const FormatToken &First, const FormatToken &Last,
1540                          bool IncludeLeadingNewlines) {
1541     SourceLocation Start = First.WhitespaceRange.getBegin();
1542     if (!IncludeLeadingNewlines)
1543       Start = Start.getLocWithOffset(First.LastNewlineOffset);
1544     SourceLocation End = Last.getStartOfNonWhitespace();
1545     End = End.getLocWithOffset(Last.TokenText.size());
1546     CharSourceRange Range = CharSourceRange::getCharRange(Start, End);
1547     return affectsCharSourceRange(Range);
1548   }
1549
1550   // Returns true if one of the input ranges intersect the leading empty lines
1551   // before 'Tok'.
1552   bool affectsLeadingEmptyLines(const FormatToken &Tok) {
1553     CharSourceRange EmptyLineRange = CharSourceRange::getCharRange(
1554         Tok.WhitespaceRange.getBegin(),
1555         Tok.WhitespaceRange.getBegin().getLocWithOffset(Tok.LastNewlineOffset));
1556     return affectsCharSourceRange(EmptyLineRange);
1557   }
1558
1559   // Returns true if 'Range' intersects with one of the input ranges.
1560   bool affectsCharSourceRange(const CharSourceRange &Range) {
1561     for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
1562                                                           E = Ranges.end();
1563          I != E; ++I) {
1564       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
1565           !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
1566         return true;
1567     }
1568     return false;
1569   }
1570
1571   static bool inputUsesCRLF(StringRef Text) {
1572     return Text.count('\r') * 2 > Text.count('\n');
1573   }
1574
1575   bool
1576   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1577     for (const AnnotatedLine* Line : Lines) {
1578       if (hasCpp03IncompatibleFormat(Line->Children))
1579         return true;
1580       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
1581         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1582           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
1583             return true;
1584           if (Tok->is(TT_TemplateCloser) &&
1585               Tok->Previous->is(TT_TemplateCloser))
1586             return true;
1587         }
1588       }
1589     }
1590     return false;
1591   }
1592
1593   int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1594     int AlignmentDiff = 0;
1595     for (const AnnotatedLine* Line : Lines) {
1596       AlignmentDiff += countVariableAlignments(Line->Children);
1597       for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
1598         if (!Tok->is(TT_PointerOrReference))
1599           continue;
1600         bool SpaceBefore =
1601             Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1602         bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
1603                           Tok->Next->WhitespaceRange.getEnd();
1604         if (SpaceBefore && !SpaceAfter)
1605           ++AlignmentDiff;
1606         if (!SpaceBefore && SpaceAfter)
1607           --AlignmentDiff;
1608       }
1609     }
1610     return AlignmentDiff;
1611   }
1612
1613   void
1614   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1615     bool HasBinPackedFunction = false;
1616     bool HasOnePerLineFunction = false;
1617     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1618       if (!AnnotatedLines[i]->First->Next)
1619         continue;
1620       FormatToken *Tok = AnnotatedLines[i]->First->Next;
1621       while (Tok->Next) {
1622         if (Tok->PackingKind == PPK_BinPacked)
1623           HasBinPackedFunction = true;
1624         if (Tok->PackingKind == PPK_OnePerLine)
1625           HasOnePerLineFunction = true;
1626
1627         Tok = Tok->Next;
1628       }
1629     }
1630     if (Style.DerivePointerAlignment)
1631       Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
1632                                    ? FormatStyle::PAS_Left
1633                                    : FormatStyle::PAS_Right;
1634     if (Style.Standard == FormatStyle::LS_Auto)
1635       Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
1636                            ? FormatStyle::LS_Cpp11
1637                            : FormatStyle::LS_Cpp03;
1638     BinPackInconclusiveFunctions =
1639         HasBinPackedFunction || !HasOnePerLineFunction;
1640   }
1641
1642   void consumeUnwrappedLine(const UnwrappedLine &TheLine) override {
1643     assert(!UnwrappedLines.empty());
1644     UnwrappedLines.back().push_back(TheLine);
1645   }
1646
1647   void finishRun() override {
1648     UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
1649   }
1650
1651   FormatStyle Style;
1652   FileID ID;
1653   SourceManager &SourceMgr;
1654   WhitespaceManager Whitespaces;
1655   SmallVector<CharSourceRange, 8> Ranges;
1656   SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
1657
1658   encoding::Encoding Encoding;
1659   bool BinPackInconclusiveFunctions;
1660 };
1661
1662 struct IncludeDirective {
1663   StringRef Filename;
1664   StringRef Text;
1665   unsigned Offset;
1666   unsigned Category;
1667 };
1668
1669 } // end anonymous namespace
1670
1671 // Determines whether 'Ranges' intersects with ('Start', 'End').
1672 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
1673                          unsigned End) {
1674   for (auto Range : Ranges) {
1675     if (Range.getOffset() < End &&
1676         Range.getOffset() + Range.getLength() > Start)
1677       return true;
1678   }
1679   return false;
1680 }
1681
1682 // Sorts a block of includes given by 'Includes' alphabetically adding the
1683 // necessary replacement to 'Replaces'. 'Includes' must be in strict source
1684 // order.
1685 static void sortIncludes(const FormatStyle &Style,
1686                          const SmallVectorImpl<IncludeDirective> &Includes,
1687                          ArrayRef<tooling::Range> Ranges, StringRef FileName,
1688                          tooling::Replacements &Replaces) {
1689   if (!affectsRange(Ranges, Includes.front().Offset,
1690                     Includes.back().Offset + Includes.back().Text.size()))
1691     return;
1692   SmallVector<unsigned, 16> Indices;
1693   for (unsigned i = 0, e = Includes.size(); i != e; ++i)
1694     Indices.push_back(i);
1695   std::sort(Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
1696     return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
1697            std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
1698   });
1699
1700   // If the #includes are out of order, we generate a single replacement fixing
1701   // the entire block. Otherwise, no replacement is generated.
1702   bool OutOfOrder = false;
1703   for (unsigned i = 1, e = Indices.size(); i != e; ++i) {
1704     if (Indices[i] != i) {
1705       OutOfOrder = true;
1706       break;
1707     }
1708   }
1709   if (!OutOfOrder)
1710     return;
1711
1712   std::string result = Includes[Indices[0]].Text;
1713   for (unsigned i = 1, e = Indices.size(); i != e; ++i) {
1714     result += "\n";
1715     result += Includes[Indices[i]].Text;
1716   }
1717
1718   // Sorting #includes shouldn't change their total number of characters.
1719   // This would otherwise mess up 'Ranges'.
1720   assert(result.size() ==
1721          Includes.back().Offset + Includes.back().Text.size() -
1722              Includes.front().Offset);
1723
1724   Replaces.insert(tooling::Replacement(FileName, Includes.front().Offset,
1725                                        result.size(), result));
1726 }
1727
1728 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
1729                                    ArrayRef<tooling::Range> Ranges,
1730                                    StringRef FileName) {
1731   tooling::Replacements Replaces;
1732   unsigned Prev = 0;
1733   unsigned SearchFrom = 0;
1734   llvm::Regex IncludeRegex(
1735       R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))");
1736   SmallVector<StringRef, 4> Matches;
1737   SmallVector<IncludeDirective, 16> IncludesInBlock;
1738
1739   // In compiled files, consider the first #include to be the main #include of
1740   // the file if it is not a system #include. This ensures that the header
1741   // doesn't have hidden dependencies
1742   // (http://llvm.org/docs/CodingStandards.html#include-style).
1743   //
1744   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
1745   // cases where the first #include is unlikely to be the main header.
1746   bool LookForMainHeader = FileName.endswith(".c") ||
1747                            FileName.endswith(".cc") ||
1748                            FileName.endswith(".cpp")||
1749                            FileName.endswith(".c++")||
1750                            FileName.endswith(".cxx") ||
1751                            FileName.endswith(".m")||
1752                            FileName.endswith(".mm");
1753
1754   // Create pre-compiled regular expressions for the #include categories.
1755   SmallVector<llvm::Regex, 4> CategoryRegexs;
1756   for (const auto &Category : Style.IncludeCategories)
1757     CategoryRegexs.emplace_back(Category.Regex);
1758
1759   for (;;) {
1760     auto Pos = Code.find('\n', SearchFrom);
1761     StringRef Line =
1762         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
1763     if (!Line.endswith("\\")) {
1764       if (IncludeRegex.match(Line, &Matches)) {
1765         StringRef IncludeName = Matches[2];
1766         unsigned Category;
1767         if (LookForMainHeader && !IncludeName.startswith("<")) {
1768           Category = 0;
1769         } else {
1770           Category = UINT_MAX;
1771           for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i) {
1772             if (CategoryRegexs[i].match(IncludeName)) {
1773               Category = Style.IncludeCategories[i].Priority;
1774               break;
1775             }
1776           }
1777         }
1778         LookForMainHeader = false;
1779         IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
1780       } else if (!IncludesInBlock.empty()) {
1781         sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces);
1782         IncludesInBlock.clear();
1783       }
1784       Prev = Pos + 1;
1785     }
1786     if (Pos == StringRef::npos || Pos + 1 == Code.size())
1787       break;
1788     SearchFrom = Pos + 1;
1789   }
1790   if (!IncludesInBlock.empty())
1791     sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces);
1792   return Replaces;
1793 }
1794
1795 tooling::Replacements reformat(const FormatStyle &Style,
1796                                SourceManager &SourceMgr, FileID ID,
1797                                ArrayRef<CharSourceRange> Ranges,
1798                                bool *IncompleteFormat) {
1799   FormatStyle Expanded = expandPresets(Style);
1800   if (Expanded.DisableFormat)
1801     return tooling::Replacements();
1802   Formatter formatter(Expanded, SourceMgr, ID, Ranges);
1803   return formatter.format(IncompleteFormat);
1804 }
1805
1806 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1807                                ArrayRef<tooling::Range> Ranges,
1808                                StringRef FileName, bool *IncompleteFormat) {
1809   if (Style.DisableFormat)
1810     return tooling::Replacements();
1811
1812   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem(
1813       new vfs::InMemoryFileSystem);
1814   FileManager Files(FileSystemOptions(), InMemoryFileSystem);
1815   DiagnosticsEngine Diagnostics(
1816       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1817       new DiagnosticOptions);
1818   SourceManager SourceMgr(Diagnostics, Files);
1819   InMemoryFileSystem->addFile(FileName, 0,
1820                               llvm::MemoryBuffer::getMemBuffer(Code, FileName));
1821   FileID ID = SourceMgr.createFileID(Files.getFile(FileName), SourceLocation(),
1822                                      clang::SrcMgr::C_User);
1823   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1824   std::vector<CharSourceRange> CharRanges;
1825   for (const tooling::Range &Range : Ranges) {
1826     SourceLocation Start = StartOfFile.getLocWithOffset(Range.getOffset());
1827     SourceLocation End = Start.getLocWithOffset(Range.getLength());
1828     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1829   }
1830   return reformat(Style, SourceMgr, ID, CharRanges, IncompleteFormat);
1831 }
1832
1833 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
1834   LangOptions LangOpts;
1835   LangOpts.CPlusPlus = 1;
1836   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1837   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1838   LangOpts.LineComment = 1;
1839   bool AlternativeOperators = Style.Language == FormatStyle::LK_Cpp;
1840   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
1841   LangOpts.Bool = 1;
1842   LangOpts.ObjC1 = 1;
1843   LangOpts.ObjC2 = 1;
1844   LangOpts.MicrosoftExt = 1; // To get kw___try, kw___finally.
1845   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
1846   return LangOpts;
1847 }
1848
1849 const char *StyleOptionHelpDescription =
1850     "Coding style, currently supports:\n"
1851     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1852     "Use -style=file to load style configuration from\n"
1853     ".clang-format file located in one of the parent\n"
1854     "directories of the source file (or current\n"
1855     "directory for stdin).\n"
1856     "Use -style=\"{key: value, ...}\" to set specific\n"
1857     "parameters, e.g.:\n"
1858     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1859
1860 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
1861   if (FileName.endswith(".java")) {
1862     return FormatStyle::LK_Java;
1863   } else if (FileName.endswith_lower(".js") || FileName.endswith_lower(".ts")) {
1864     // JavaScript or TypeScript.
1865     return FormatStyle::LK_JavaScript;
1866   } else if (FileName.endswith_lower(".proto") ||
1867              FileName.endswith_lower(".protodevel")) {
1868     return FormatStyle::LK_Proto;
1869   }
1870   return FormatStyle::LK_Cpp;
1871 }
1872
1873 FormatStyle getStyle(StringRef StyleName, StringRef FileName,
1874                      StringRef FallbackStyle) {
1875   FormatStyle Style = getLLVMStyle();
1876   Style.Language = getLanguageByFileName(FileName);
1877   if (!getPredefinedStyle(FallbackStyle, Style.Language, &Style)) {
1878     llvm::errs() << "Invalid fallback style \"" << FallbackStyle
1879                  << "\" using LLVM style\n";
1880     return Style;
1881   }
1882
1883   if (StyleName.startswith("{")) {
1884     // Parse YAML/JSON style from the command line.
1885     if (std::error_code ec = parseConfiguration(StyleName, &Style)) {
1886       llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
1887                    << FallbackStyle << " style\n";
1888     }
1889     return Style;
1890   }
1891
1892   if (!StyleName.equals_lower("file")) {
1893     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
1894       llvm::errs() << "Invalid value for -style, using " << FallbackStyle
1895                    << " style\n";
1896     return Style;
1897   }
1898
1899   // Look for .clang-format/_clang-format file in the file's parent directories.
1900   SmallString<128> UnsuitableConfigFiles;
1901   SmallString<128> Path(FileName);
1902   llvm::sys::fs::make_absolute(Path);
1903   for (StringRef Directory = Path; !Directory.empty();
1904        Directory = llvm::sys::path::parent_path(Directory)) {
1905     if (!llvm::sys::fs::is_directory(Directory))
1906       continue;
1907     SmallString<128> ConfigFile(Directory);
1908
1909     llvm::sys::path::append(ConfigFile, ".clang-format");
1910     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1911     bool IsFile = false;
1912     // Ignore errors from is_regular_file: we only need to know if we can read
1913     // the file or not.
1914     llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1915
1916     if (!IsFile) {
1917       // Try _clang-format too, since dotfiles are not commonly used on Windows.
1918       ConfigFile = Directory;
1919       llvm::sys::path::append(ConfigFile, "_clang-format");
1920       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1921       llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1922     }
1923
1924     if (IsFile) {
1925       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
1926           llvm::MemoryBuffer::getFile(ConfigFile.c_str());
1927       if (std::error_code EC = Text.getError()) {
1928         llvm::errs() << EC.message() << "\n";
1929         break;
1930       }
1931       if (std::error_code ec =
1932               parseConfiguration(Text.get()->getBuffer(), &Style)) {
1933         if (ec == ParseError::Unsuitable) {
1934           if (!UnsuitableConfigFiles.empty())
1935             UnsuitableConfigFiles.append(", ");
1936           UnsuitableConfigFiles.append(ConfigFile);
1937           continue;
1938         }
1939         llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
1940                      << "\n";
1941         break;
1942       }
1943       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
1944       return Style;
1945     }
1946   }
1947   if (!UnsuitableConfigFiles.empty()) {
1948     llvm::errs() << "Configuration file(s) do(es) not support "
1949                  << getLanguageName(Style.Language) << ": "
1950                  << UnsuitableConfigFiles << "\n";
1951   }
1952   return Style;
1953 }
1954
1955 } // namespace format
1956 } // namespace clang