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 "clang/Format/Format.h"
  17 #include "AffectedRangeManager.h"
  18 #include "ContinuationIndenter.h"
  19 #include "FormatTokenLexer.h"
  20 #include "NamespaceEndCommentsFixer.h"
  21 #include "SortJavaScriptImports.h"
  22 #include "TokenAnalyzer.h"
  23 #include "TokenAnnotator.h"
  24 #include "UnwrappedLineFormatter.h"
  25 #include "UnwrappedLineParser.h"
  26 #include "WhitespaceManager.h"
  27 #include "clang/Basic/Diagnostic.h"
  28 #include "clang/Basic/DiagnosticOptions.h"
  29 #include "clang/Basic/SourceManager.h"
  30 #include "clang/Basic/VirtualFileSystem.h"
  31 #include "clang/Lex/Lexer.h"
  32 #include "llvm/ADT/STLExtras.h"
  33 #include "llvm/Support/Allocator.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/Path.h"
  36 #include "llvm/Support/Regex.h"
  37 #include "llvm/Support/YAMLTraits.h"
  38 #include <algorithm>
  39 #include <memory>
  40 #include <string>
  41
  42 #define DEBUG_TYPE "format-formatter"
  43
  44 using clang::format::FormatStyle;
  45
  46 LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
  47 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::IncludeCategory)
  48
  49 namespace llvm {
  50 namespace yaml {
  51 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
  52   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
  53     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
  54     IO.enumCase(Value, "Java", FormatStyle::LK_Java);
  55     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
  56     IO.enumCase(Value, "ObjC", FormatStyle::LK_ObjC);
  57     IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
  58     IO.enumCase(Value, "TableGen", FormatStyle::LK_TableGen);
  59   }
  60 };
  61
  62 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
  63   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
  64     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
  65     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
  66     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
  67     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
  68     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
  69   }
  70 };
  71
  72 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
  73   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
  74     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
  75     IO.enumCase(Value, "false", FormatStyle::UT_Never);
  76     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
  77     IO.enumCase(Value, "true", FormatStyle::UT_Always);
  78     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
  79     IO.enumCase(Value, "ForContinuationAndIndentation",
  80                 FormatStyle::UT_ForContinuationAndIndentation);
  81   }
  82 };
  83
  84 template <> struct ScalarEnumerationTraits<FormatStyle::JavaScriptQuoteStyle> {
  85   static void enumeration(IO &IO, FormatStyle::JavaScriptQuoteStyle &Value) {
  86     IO.enumCase(Value, "Leave", FormatStyle::JSQS_Leave);
  87     IO.enumCase(Value, "Single", FormatStyle::JSQS_Single);
  88     IO.enumCase(Value, "Double", FormatStyle::JSQS_Double);
  89   }
  90 };
  91
  92 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
  93   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
  94     IO.enumCase(Value, "None", FormatStyle::SFS_None);
  95     IO.enumCase(Value, "false", FormatStyle::SFS_None);
  96     IO.enumCase(Value, "All", FormatStyle::SFS_All);
  97     IO.enumCase(Value, "true", FormatStyle::SFS_All);
  98     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
  99     IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
 100   }
 101 };
 102
 103 template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
 104   static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
 105     IO.enumCase(Value, "All", FormatStyle::BOS_All);
 106     IO.enumCase(Value, "true", FormatStyle::BOS_All);
 107     IO.enumCase(Value, "None", FormatStyle::BOS_None);
 108     IO.enumCase(Value, "false", FormatStyle::BOS_None);
 109     IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
 110   }
 111 };
 112
 113 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
 114   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
 115     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
 116     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
 117     IO.enumCase(Value, "Mozilla", FormatStyle::BS_Mozilla);
 118     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
 119     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
 120     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
 121     IO.enumCase(Value, "WebKit", FormatStyle::BS_WebKit);
 122     IO.enumCase(Value, "Custom", FormatStyle::BS_Custom);
 123   }
 124 };
 125
 126 template <>
 127 struct ScalarEnumerationTraits<FormatStyle::ReturnTypeBreakingStyle> {
 128   static void enumeration(IO &IO, FormatStyle::ReturnTypeBreakingStyle &Value) {
 129     IO.enumCase(Value, "None", FormatStyle::RTBS_None);
 130     IO.enumCase(Value, "All", FormatStyle::RTBS_All);
 131     IO.enumCase(Value, "TopLevel", FormatStyle::RTBS_TopLevel);
 132     IO.enumCase(Value, "TopLevelDefinitions",
 133                 FormatStyle::RTBS_TopLevelDefinitions);
 134     IO.enumCase(Value, "AllDefinitions", FormatStyle::RTBS_AllDefinitions);
 135   }
 136 };
 137
 138 template <>
 139 struct ScalarEnumerationTraits<FormatStyle::DefinitionReturnTypeBreakingStyle> {
 140   static void
 141   enumeration(IO &IO, FormatStyle::DefinitionReturnTypeBreakingStyle &Value) {
 142     IO.enumCase(Value, "None", FormatStyle::DRTBS_None);
 143     IO.enumCase(Value, "All", FormatStyle::DRTBS_All);
 144     IO.enumCase(Value, "TopLevel", FormatStyle::DRTBS_TopLevel);
 145
 146     // For backward compatibility.
 147     IO.enumCase(Value, "false", FormatStyle::DRTBS_None);
 148     IO.enumCase(Value, "true", FormatStyle::DRTBS_All);
 149   }
 150 };
 151
 152 template <>
 153 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
 154   static void enumeration(IO &IO,
 155                           FormatStyle::NamespaceIndentationKind &Value) {
 156     IO.enumCase(Value, "None", FormatStyle::NI_None);
 157     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
 158     IO.enumCase(Value, "All", FormatStyle::NI_All);
 159   }
 160 };
 161
 162 template <> struct ScalarEnumerationTraits<FormatStyle::BracketAlignmentStyle> {
 163   static void enumeration(IO &IO, FormatStyle::BracketAlignmentStyle &Value) {
 164     IO.enumCase(Value, "Align", FormatStyle::BAS_Align);
 165     IO.enumCase(Value, "DontAlign", FormatStyle::BAS_DontAlign);
 166     IO.enumCase(Value, "AlwaysBreak", FormatStyle::BAS_AlwaysBreak);
 167
 168     // For backward compatibility.
 169     IO.enumCase(Value, "true", FormatStyle::BAS_Align);
 170     IO.enumCase(Value, "false", FormatStyle::BAS_DontAlign);
 171   }
 172 };
 173
 174 template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
 175   static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
 176     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
 177     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
 178     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
 179
 180     // For backward compatibility.
 181     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
 182     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
 183   }
 184 };
 185
 186 template <>
 187 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
 188   static void enumeration(IO &IO,
 189                           FormatStyle::SpaceBeforeParensOptions &Value) {
 190     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
 191     IO.enumCase(Value, "ControlStatements",
 192                 FormatStyle::SBPO_ControlStatements);
 193     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
 194
 195     // For backward compatibility.
 196     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
 197     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
 198   }
 199 };
 200
 201 template <> struct MappingTraits<FormatStyle> {
 202   static void mapping(IO &IO, FormatStyle &Style) {
 203     // When reading, read the language first, we need it for getPredefinedStyle.
 204     IO.mapOptional("Language", Style.Language);
 205
 206     if (IO.outputting()) {
 207       StringRef StylesArray[] = {"LLVM",    "Google", "Chromium",
 208                                  "Mozilla", "WebKit", "GNU"};
 209       ArrayRef<StringRef> Styles(StylesArray);
 210       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
 211         StringRef StyleName(Styles[i]);
 212         FormatStyle PredefinedStyle;
 213         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
 214             Style == PredefinedStyle) {
 215           IO.mapOptional("# BasedOnStyle", StyleName);
 216           break;
 217         }
 218       }
 219     } else {
 220       StringRef BasedOnStyle;
 221       IO.mapOptional("BasedOnStyle", BasedOnStyle);
 222       if (!BasedOnStyle.empty()) {
 223         FormatStyle::LanguageKind OldLanguage = Style.Language;
 224         FormatStyle::LanguageKind Language =
 225             ((FormatStyle *)IO.getContext())->Language;
 226         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
 227           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
 228           return;
 229         }
 230         Style.Language = OldLanguage;
 231       }
 232     }
 233
 234     // For backward compatibility.
 235     if (!IO.outputting()) {
 236       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
 237       IO.mapOptional("IndentFunctionDeclarationAfterType",
 238                      Style.IndentWrappedFunctionNames);
 239       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
 240       IO.mapOptional("SpaceAfterControlStatementKeyword",
 241                      Style.SpaceBeforeParens);
 242     }
 243
 244     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
 245     IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
 246     IO.mapOptional("AlignConsecutiveAssignments",
 247                    Style.AlignConsecutiveAssignments);
 248     IO.mapOptional("AlignConsecutiveDeclarations",
 249                    Style.AlignConsecutiveDeclarations);
 250     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
 251     IO.mapOptional("AlignOperands", Style.AlignOperands);
 252     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
 253     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
 254                    Style.AllowAllParametersOfDeclarationOnNextLine);
 255     IO.mapOptional("AllowShortBlocksOnASingleLine",
 256                    Style.AllowShortBlocksOnASingleLine);
 257     IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
 258                    Style.AllowShortCaseLabelsOnASingleLine);
 259     IO.mapOptional("AllowShortFunctionsOnASingleLine",
 260                    Style.AllowShortFunctionsOnASingleLine);
 261     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
 262                    Style.AllowShortIfStatementsOnASingleLine);
 263     IO.mapOptional("AllowShortLoopsOnASingleLine",
 264                    Style.AllowShortLoopsOnASingleLine);
 265     IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
 266                    Style.AlwaysBreakAfterDefinitionReturnType);
 267     IO.mapOptional("AlwaysBreakAfterReturnType",
 268                    Style.AlwaysBreakAfterReturnType);
 269     // If AlwaysBreakAfterDefinitionReturnType was specified but
 270     // AlwaysBreakAfterReturnType was not, initialize the latter from the
 271     // former for backwards compatibility.
 272     if (Style.AlwaysBreakAfterDefinitionReturnType != FormatStyle::DRTBS_None &&
 273         Style.AlwaysBreakAfterReturnType == FormatStyle::RTBS_None) {
 274       if (Style.AlwaysBreakAfterDefinitionReturnType == FormatStyle::DRTBS_All)
 275         Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
 276       else if (Style.AlwaysBreakAfterDefinitionReturnType ==
 277                FormatStyle::DRTBS_TopLevel)
 278         Style.AlwaysBreakAfterReturnType =
 279             FormatStyle::RTBS_TopLevelDefinitions;
 280     }
 281
 282     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
 283                    Style.AlwaysBreakBeforeMultilineStrings);
 284     IO.mapOptional("AlwaysBreakTemplateDeclarations",
 285                    Style.AlwaysBreakTemplateDeclarations);
 286     IO.mapOptional("BinPackArguments", Style.BinPackArguments);
 287     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
 288     IO.mapOptional("BraceWrapping", Style.BraceWrapping);
 289     IO.mapOptional("BreakBeforeBinaryOperators",
 290                    Style.BreakBeforeBinaryOperators);
 291     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
 292     IO.mapOptional("BreakBeforeTernaryOperators",
 293                    Style.BreakBeforeTernaryOperators);
 294     IO.mapOptional("BreakConstructorInitializersBeforeComma",
 295                    Style.BreakConstructorInitializersBeforeComma);
 296     IO.mapOptional("BreakAfterJavaFieldAnnotations",
 297                    Style.BreakAfterJavaFieldAnnotations);
 298     IO.mapOptional("BreakStringLiterals", Style.BreakStringLiterals);
 299     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
 300     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
 301     IO.mapOptional("BreakBeforeInheritanceComma",
 302                    Style.BreakBeforeInheritanceComma);
 303     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
 304                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
 305     IO.mapOptional("ConstructorInitializerIndentWidth",
 306                    Style.ConstructorInitializerIndentWidth);
 307     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
 308     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
 309     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
 310     IO.mapOptional("DisableFormat", Style.DisableFormat);
 311     IO.mapOptional("ExperimentalAutoDetectBinPacking",
 312                    Style.ExperimentalAutoDetectBinPacking);
 313     IO.mapOptional("FixNamespaceComments", Style.FixNamespaceComments);
 314     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
 315     IO.mapOptional("IncludeCategories", Style.IncludeCategories);
 316     IO.mapOptional("IncludeIsMainRegex", Style.IncludeIsMainRegex);
 317     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
 318     IO.mapOptional("IndentWidth", Style.IndentWidth);
 319     IO.mapOptional("IndentWrappedFunctionNames",
 320                    Style.IndentWrappedFunctionNames);
 321     IO.mapOptional("JavaScriptQuotes", Style.JavaScriptQuotes);
 322     IO.mapOptional("JavaScriptWrapImports", Style.JavaScriptWrapImports);
 323     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
 324                    Style.KeepEmptyLinesAtTheStartOfBlocks);
 325     IO.mapOptional("MacroBlockBegin", Style.MacroBlockBegin);
 326     IO.mapOptional("MacroBlockEnd", Style.MacroBlockEnd);
 327     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
 328     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
 329     IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
 330     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
 331     IO.mapOptional("ObjCSpaceBeforeProtocolList",
 332                    Style.ObjCSpaceBeforeProtocolList);
 333     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
 334                    Style.PenaltyBreakBeforeFirstCallParameter);
 335     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
 336     IO.mapOptional("PenaltyBreakFirstLessLess",
 337                    Style.PenaltyBreakFirstLessLess);
 338     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
 339     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
 340     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
 341                    Style.PenaltyReturnTypeOnItsOwnLine);
 342     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
 343     IO.mapOptional("ReflowComments", Style.ReflowComments);
 344     IO.mapOptional("SortIncludes", Style.SortIncludes);
 345     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
 346     IO.mapOptional("SpaceAfterTemplateKeyword", Style.SpaceAfterTemplateKeyword);
 347     IO.mapOptional("SpaceBeforeAssignmentOperators",
 348                    Style.SpaceBeforeAssignmentOperators);
 349     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
 350     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
 351     IO.mapOptional("SpacesBeforeTrailingComments",
 352                    Style.SpacesBeforeTrailingComments);
 353     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
 354     IO.mapOptional("SpacesInContainerLiterals",
 355                    Style.SpacesInContainerLiterals);
 356     IO.mapOptional("SpacesInCStyleCastParentheses",
 357                    Style.SpacesInCStyleCastParentheses);
 358     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
 359     IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
 360     IO.mapOptional("Standard", Style.Standard);
 361     IO.mapOptional("TabWidth", Style.TabWidth);
 362     IO.mapOptional("UseTab", Style.UseTab);
 363   }
 364 };
 365
 366 template <> struct MappingTraits<FormatStyle::BraceWrappingFlags> {
 367   static void mapping(IO &IO, FormatStyle::BraceWrappingFlags &Wrapping) {
 368     IO.mapOptional("AfterClass", Wrapping.AfterClass);
 369     IO.mapOptional("AfterControlStatement", Wrapping.AfterControlStatement);
 370     IO.mapOptional("AfterEnum", Wrapping.AfterEnum);
 371     IO.mapOptional("AfterFunction", Wrapping.AfterFunction);
 372     IO.mapOptional("AfterNamespace", Wrapping.AfterNamespace);
 373     IO.mapOptional("AfterObjCDeclaration", Wrapping.AfterObjCDeclaration);
 374     IO.mapOptional("AfterStruct", Wrapping.AfterStruct);
 375     IO.mapOptional("AfterUnion", Wrapping.AfterUnion);
 376     IO.mapOptional("BeforeCatch", Wrapping.BeforeCatch);
 377     IO.mapOptional("BeforeElse", Wrapping.BeforeElse);
 378     IO.mapOptional("IndentBraces", Wrapping.IndentBraces);
 379   }
 380 };
 381
 382 template <> struct MappingTraits<FormatStyle::IncludeCategory> {
 383   static void mapping(IO &IO, FormatStyle::IncludeCategory &Category) {
 384     IO.mapOptional("Regex", Category.Regex);
 385     IO.mapOptional("Priority", Category.Priority);
 386   }
 387 };
 388
 389 // Allows to read vector<FormatStyle> while keeping default values.
 390 // IO.getContext() should contain a pointer to the FormatStyle structure, that
 391 // will be used to get default values for missing keys.
 392 // If the first element has no Language specified, it will be treated as the
 393 // default one for the following elements.
 394 template <> struct DocumentListTraits<std::vector<FormatStyle>> {
 395   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
 396     return Seq.size();
 397   }
 398   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
 399                               size_t Index) {
 400     if (Index >= Seq.size()) {
 401       assert(Index == Seq.size());
 402       FormatStyle Template;
 403       if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
 404         Template = Seq[0];
 405       } else {
 406         Template = *((const FormatStyle *)IO.getContext());
 407         Template.Language = FormatStyle::LK_None;
 408       }
 409       Seq.resize(Index + 1, Template);
 410     }
 411     return Seq[Index];
 412   }
 413 };
 414 } // namespace yaml
 415 } // namespace llvm
 416
 417 namespace clang {
 418 namespace format {
 419
 420 const std::error_category &getParseCategory() {
 421   static ParseErrorCategory C;
 422   return C;
 423 }
 424 std::error_code make_error_code(ParseError e) {
 425   return std::error_code(static_cast<int>(e), getParseCategory());
 426 }
 427
 428 inline llvm::Error make_string_error(const llvm::Twine &Message) {
 429   return llvm::make_error<llvm::StringError>(Message,
 430                                              llvm::inconvertibleErrorCode());
 431 }
 432
 433 const char *ParseErrorCategory::name() const noexcept {
 434   return "clang-format.parse_error";
 435 }
 436
 437 std::string ParseErrorCategory::message(int EV) const {
 438   switch (static_cast<ParseError>(EV)) {
 439   case ParseError::Success:
 440     return "Success";
 441   case ParseError::Error:
 442     return "Invalid argument";
 443   case ParseError::Unsuitable:
 444     return "Unsuitable";
 445   }
 446   llvm_unreachable("unexpected parse error");
 447 }
 448
 449 static FormatStyle expandPresets(const FormatStyle &Style) {
 450   if (Style.BreakBeforeBraces == FormatStyle::BS_Custom)
 451     return Style;
 452   FormatStyle Expanded = Style;
 453   Expanded.BraceWrapping = {false, false, false, false, false, false,
 454                             false, false, false, false, false};
 455   switch (Style.BreakBeforeBraces) {
 456   case FormatStyle::BS_Linux:
 457     Expanded.BraceWrapping.AfterClass = true;
 458     Expanded.BraceWrapping.AfterFunction = true;
 459     Expanded.BraceWrapping.AfterNamespace = true;
 460     break;
 461   case FormatStyle::BS_Mozilla:
 462     Expanded.BraceWrapping.AfterClass = true;
 463     Expanded.BraceWrapping.AfterEnum = true;
 464     Expanded.BraceWrapping.AfterFunction = true;
 465     Expanded.BraceWrapping.AfterStruct = true;
 466     Expanded.BraceWrapping.AfterUnion = true;
 467     break;
 468   case FormatStyle::BS_Stroustrup:
 469     Expanded.BraceWrapping.AfterFunction = true;
 470     Expanded.BraceWrapping.BeforeCatch = true;
 471     Expanded.BraceWrapping.BeforeElse = true;
 472     break;
 473   case FormatStyle::BS_Allman:
 474     Expanded.BraceWrapping.AfterClass = true;
 475     Expanded.BraceWrapping.AfterControlStatement = true;
 476     Expanded.BraceWrapping.AfterEnum = true;
 477     Expanded.BraceWrapping.AfterFunction = true;
 478     Expanded.BraceWrapping.AfterNamespace = true;
 479     Expanded.BraceWrapping.AfterObjCDeclaration = true;
 480     Expanded.BraceWrapping.AfterStruct = true;
 481     Expanded.BraceWrapping.BeforeCatch = true;
 482     Expanded.BraceWrapping.BeforeElse = true;
 483     break;
 484   case FormatStyle::BS_GNU:
 485     Expanded.BraceWrapping = {true, true, true, true, true, true,
 486                               true, true, true, true, true};
 487     break;
 488   case FormatStyle::BS_WebKit:
 489     Expanded.BraceWrapping.AfterFunction = true;
 490     break;
 491   default:
 492     break;
 493   }
 494   return Expanded;
 495 }
 496
 497 FormatStyle getLLVMStyle() {
 498   FormatStyle LLVMStyle;
 499   LLVMStyle.Language = FormatStyle::LK_Cpp;
 500   LLVMStyle.AccessModifierOffset = -2;
 501   LLVMStyle.AlignEscapedNewlinesLeft = false;
 502   LLVMStyle.AlignAfterOpenBracket = FormatStyle::BAS_Align;
 503   LLVMStyle.AlignOperands = true;
 504   LLVMStyle.AlignTrailingComments = true;
 505   LLVMStyle.AlignConsecutiveAssignments = false;
 506   LLVMStyle.AlignConsecutiveDeclarations = false;
 507   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
 508   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
 509   LLVMStyle.AllowShortBlocksOnASingleLine = false;
 510   LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
 511   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
 512   LLVMStyle.AllowShortLoopsOnASingleLine = false;
 513   LLVMStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
 514   LLVMStyle.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
 515   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
 516   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
 517   LLVMStyle.BinPackParameters = true;
 518   LLVMStyle.BinPackArguments = true;
 519   LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
 520   LLVMStyle.BreakBeforeTernaryOperators = true;
 521   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
 522   LLVMStyle.BraceWrapping = {false, false, false, false, false, false,
 523                              false, false, false, false, false};
 524   LLVMStyle.BreakAfterJavaFieldAnnotations = false;
 525   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
 526   LLVMStyle.BreakBeforeInheritanceComma = false;
 527   LLVMStyle.BreakStringLiterals = true;
 528   LLVMStyle.ColumnLimit = 80;
 529   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
 530   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
 531   LLVMStyle.ConstructorInitializerIndentWidth = 4;
 532   LLVMStyle.ContinuationIndentWidth = 4;
 533   LLVMStyle.Cpp11BracedListStyle = true;
 534   LLVMStyle.DerivePointerAlignment = false;
 535   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
 536   LLVMStyle.FixNamespaceComments = true;
 537   LLVMStyle.ForEachMacros.push_back("foreach");
 538   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
 539   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
 540   LLVMStyle.IncludeCategories = {{"^\"(llvm|llvm-c|clang|clang-c)/", 2},
 541                                  {"^(<|\"(gtest|isl|json)/)", 3},
 542                                  {".*", 1}};
 543   LLVMStyle.IncludeIsMainRegex = "$";
 544   LLVMStyle.IndentCaseLabels = false;
 545   LLVMStyle.IndentWrappedFunctionNames = false;
 546   LLVMStyle.IndentWidth = 2;
 547   LLVMStyle.JavaScriptQuotes = FormatStyle::JSQS_Leave;
 548   LLVMStyle.JavaScriptWrapImports = true;
 549   LLVMStyle.TabWidth = 8;
 550   LLVMStyle.MaxEmptyLinesToKeep = 1;
 551   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
 552   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
 553   LLVMStyle.ObjCBlockIndentWidth = 2;
 554   LLVMStyle.ObjCSpaceAfterProperty = false;
 555   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
 556   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
 557   LLVMStyle.SpacesBeforeTrailingComments = 1;
 558   LLVMStyle.Standard = FormatStyle::LS_Cpp11;
 559   LLVMStyle.UseTab = FormatStyle::UT_Never;
 560   LLVMStyle.ReflowComments = true;
 561   LLVMStyle.SpacesInParentheses = false;
 562   LLVMStyle.SpacesInSquareBrackets = false;
 563   LLVMStyle.SpaceInEmptyParentheses = false;
 564   LLVMStyle.SpacesInContainerLiterals = true;
 565   LLVMStyle.SpacesInCStyleCastParentheses = false;
 566   LLVMStyle.SpaceAfterCStyleCast = false;
 567   LLVMStyle.SpaceAfterTemplateKeyword = true;
 568   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
 569   LLVMStyle.SpaceBeforeAssignmentOperators = true;
 570   LLVMStyle.SpacesInAngles = false;
 571
 572   LLVMStyle.PenaltyBreakComment = 300;
 573   LLVMStyle.PenaltyBreakFirstLessLess = 120;
 574   LLVMStyle.PenaltyBreakString = 1000;
 575   LLVMStyle.PenaltyExcessCharacter = 1000000;
 576   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
 577   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
 578
 579   LLVMStyle.DisableFormat = false;
 580   LLVMStyle.SortIncludes = true;
 581
 582   return LLVMStyle;
 583 }
 584
 585 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
 586   FormatStyle GoogleStyle = getLLVMStyle();
 587   GoogleStyle.Language = Language;
 588
 589   GoogleStyle.AccessModifierOffset = -1;
 590   GoogleStyle.AlignEscapedNewlinesLeft = true;
 591   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
 592   GoogleStyle.AllowShortLoopsOnASingleLine = true;
 593   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
 594   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
 595   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
 596   GoogleStyle.DerivePointerAlignment = true;
 597   GoogleStyle.IncludeCategories = {{"^<.*\\.h>", 1}, {"^<.*", 2}, {".*", 3}};
 598   GoogleStyle.IncludeIsMainRegex = "([-_](test|unittest))?$";
 599   GoogleStyle.IndentCaseLabels = true;
 600   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
 601   GoogleStyle.ObjCSpaceAfterProperty = false;
 602   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
 603   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
 604   GoogleStyle.SpacesBeforeTrailingComments = 2;
 605   GoogleStyle.Standard = FormatStyle::LS_Auto;
 606
 607   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
 608   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
 609
 610   if (Language == FormatStyle::LK_Java) {
 611     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
 612     GoogleStyle.AlignOperands = false;
 613     GoogleStyle.AlignTrailingComments = false;
 614     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
 615     GoogleStyle.AllowShortIfStatementsOnASingleLine = false;
 616     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
 617     GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
 618     GoogleStyle.ColumnLimit = 100;
 619     GoogleStyle.SpaceAfterCStyleCast = true;
 620     GoogleStyle.SpacesBeforeTrailingComments = 1;
 621   } else if (Language == FormatStyle::LK_JavaScript) {
 622     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_AlwaysBreak;
 623     GoogleStyle.AlignOperands = false;
 624     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
 625     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
 626     GoogleStyle.BreakBeforeTernaryOperators = false;
 627     // taze:, @tag followed by { for a lot of JSDoc tags, and @see, which is
 628     // commonly followed by overlong URLs.
 629     GoogleStyle.CommentPragmas = "(taze:|(@[A-Za-z_0-9-]+[ \\t]*{)|@see)";
 630     GoogleStyle.MaxEmptyLinesToKeep = 3;
 631     GoogleStyle.NamespaceIndentation = FormatStyle::NI_All;
 632     GoogleStyle.SpacesInContainerLiterals = false;
 633     GoogleStyle.JavaScriptQuotes = FormatStyle::JSQS_Single;
 634     GoogleStyle.JavaScriptWrapImports = false;
 635   } else if (Language == FormatStyle::LK_Proto) {
 636     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
 637     GoogleStyle.SpacesInContainerLiterals = false;
 638   } else if (Language == FormatStyle::LK_ObjC) {
 639     GoogleStyle.ColumnLimit = 100;
 640   }
 641
 642   return GoogleStyle;
 643 }
 644
 645 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
 646   FormatStyle ChromiumStyle = getGoogleStyle(Language);
 647   if (Language == FormatStyle::LK_Java) {
 648     ChromiumStyle.AllowShortIfStatementsOnASingleLine = true;
 649     ChromiumStyle.BreakAfterJavaFieldAnnotations = true;
 650     ChromiumStyle.ContinuationIndentWidth = 8;
 651     ChromiumStyle.IndentWidth = 4;
 652   } else if (Language == FormatStyle::LK_JavaScript) {
 653     ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
 654     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
 655   } else {
 656     ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
 657     ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
 658     ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
 659     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
 660     ChromiumStyle.BinPackParameters = false;
 661     ChromiumStyle.DerivePointerAlignment = false;
 662     if (Language == FormatStyle::LK_ObjC)
 663       ChromiumStyle.ColumnLimit = 80;
 664   }
 665   return ChromiumStyle;
 666 }
 667
 668 FormatStyle getMozillaStyle() {
 669   FormatStyle MozillaStyle = getLLVMStyle();
 670   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
 671   MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
 672   MozillaStyle.AlwaysBreakAfterReturnType =
 673       FormatStyle::RTBS_TopLevel;
 674   MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
 675       FormatStyle::DRTBS_TopLevel;
 676   MozillaStyle.AlwaysBreakTemplateDeclarations = true;
 677   MozillaStyle.BinPackParameters = false;
 678   MozillaStyle.BinPackArguments = false;
 679   MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
 680   MozillaStyle.BreakConstructorInitializersBeforeComma = true;
 681   MozillaStyle.BreakBeforeInheritanceComma = true;
 682   MozillaStyle.ConstructorInitializerIndentWidth = 2;
 683   MozillaStyle.ContinuationIndentWidth = 2;
 684   MozillaStyle.Cpp11BracedListStyle = false;
 685   MozillaStyle.FixNamespaceComments = false;
 686   MozillaStyle.IndentCaseLabels = true;
 687   MozillaStyle.ObjCSpaceAfterProperty = true;
 688   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
 689   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
 690   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
 691   MozillaStyle.SpaceAfterTemplateKeyword = false;
 692   return MozillaStyle;
 693 }
 694
 695 FormatStyle getWebKitStyle() {
 696   FormatStyle Style = getLLVMStyle();
 697   Style.AccessModifierOffset = -4;
 698   Style.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
 699   Style.AlignOperands = false;
 700   Style.AlignTrailingComments = false;
 701   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
 702   Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
 703   Style.BreakConstructorInitializersBeforeComma = true;
 704   Style.Cpp11BracedListStyle = false;
 705   Style.ColumnLimit = 0;
 706   Style.FixNamespaceComments = false;
 707   Style.IndentWidth = 4;
 708   Style.NamespaceIndentation = FormatStyle::NI_Inner;
 709   Style.ObjCBlockIndentWidth = 4;
 710   Style.ObjCSpaceAfterProperty = true;
 711   Style.PointerAlignment = FormatStyle::PAS_Left;
 712   return Style;
 713 }
 714
 715 FormatStyle getGNUStyle() {
 716   FormatStyle Style = getLLVMStyle();
 717   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
 718   Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
 719   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
 720   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
 721   Style.BreakBeforeTernaryOperators = true;
 722   Style.Cpp11BracedListStyle = false;
 723   Style.ColumnLimit = 79;
 724   Style.FixNamespaceComments = false;
 725   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
 726   Style.Standard = FormatStyle::LS_Cpp03;
 727   return Style;
 728 }
 729
 730 FormatStyle getNoStyle() {
 731   FormatStyle NoStyle = getLLVMStyle();
 732   NoStyle.DisableFormat = true;
 733   NoStyle.SortIncludes = false;
 734   return NoStyle;
 735 }
 736
 737 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
 738                         FormatStyle *Style) {
 739   if (Name.equals_lower("llvm")) {
 740     *Style = getLLVMStyle();
 741   } else if (Name.equals_lower("chromium")) {
 742     *Style = getChromiumStyle(Language);
 743   } else if (Name.equals_lower("mozilla")) {
 744     *Style = getMozillaStyle();
 745   } else if (Name.equals_lower("google")) {
 746     *Style = getGoogleStyle(Language);
 747   } else if (Name.equals_lower("webkit")) {
 748     *Style = getWebKitStyle();
 749   } else if (Name.equals_lower("gnu")) {
 750     *Style = getGNUStyle();
 751   } else if (Name.equals_lower("none")) {
 752     *Style = getNoStyle();
 753   } else {
 754     return false;
 755   }
 756
 757   Style->Language = Language;
 758   return true;
 759 }
 760
 761 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
 762   assert(Style);
 763   FormatStyle::LanguageKind Language = Style->Language;
 764   assert(Language != FormatStyle::LK_None);
 765   if (Text.trim().empty())
 766     return make_error_code(ParseError::Error);
 767
 768   std::vector<FormatStyle> Styles;
 769   llvm::yaml::Input Input(Text);
 770   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
 771   // values for the fields, keys for which are missing from the configuration.
 772   // Mapping also uses the context to get the language to find the correct
 773   // base style.
 774   Input.setContext(Style);
 775   Input >> Styles;
 776   if (Input.error())
 777     return Input.error();
 778
 779   for (unsigned i = 0; i < Styles.size(); ++i) {
 780     // Ensures that only the first configuration can skip the Language option.
 781     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
 782       return make_error_code(ParseError::Error);
 783     // Ensure that each language is configured at most once.
 784     for (unsigned j = 0; j < i; ++j) {
 785       if (Styles[i].Language == Styles[j].Language) {
 786         DEBUG(llvm::dbgs()
 787               << "Duplicate languages in the config file on positions " << j
 788               << " and " << i << "\n");
 789         return make_error_code(ParseError::Error);
 790       }
 791     }
 792   }
 793   // Look for a suitable configuration starting from the end, so we can
 794   // find the configuration for the specific language first, and the default
 795   // configuration (which can only be at slot 0) after it.
 796   for (int i = Styles.size() - 1; i >= 0; --i) {
 797     if (Styles[i].Language == Language ||
 798         Styles[i].Language == FormatStyle::LK_None) {
 799       *Style = Styles[i];
 800       Style->Language = Language;
 801       return make_error_code(ParseError::Success);
 802     }
 803   }
 804   return make_error_code(ParseError::Unsuitable);
 805 }
 806
 807 std::string configurationAsText(const FormatStyle &Style) {
 808   std::string Text;
 809   llvm::raw_string_ostream Stream(Text);
 810   llvm::yaml::Output Output(Stream);
 811   // We use the same mapping method for input and output, so we need a non-const
 812   // reference here.
 813   FormatStyle NonConstStyle = expandPresets(Style);
 814   Output << NonConstStyle;
 815   return Stream.str();
 816 }
 817
 818 namespace {
 819
 820 class JavaScriptRequoter : public TokenAnalyzer {
 821 public:
 822   JavaScriptRequoter(const Environment &Env, const FormatStyle &Style)
 823       : TokenAnalyzer(Env, Style) {}
 824
 825   tooling::Replacements
 826   analyze(TokenAnnotator &Annotator,
 827           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
 828           FormatTokenLexer &Tokens) override {
 829     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
 830                                           AnnotatedLines.end());
 831     tooling::Replacements Result;
 832     requoteJSStringLiteral(AnnotatedLines, Result);
 833     return Result;
 834   }
 835
 836 private:
 837   // Replaces double/single-quoted string literal as appropriate, re-escaping
 838   // the contents in the process.
 839   void requoteJSStringLiteral(SmallVectorImpl<AnnotatedLine *> &Lines,
 840                               tooling::Replacements &Result) {
 841     for (AnnotatedLine *Line : Lines) {
 842       requoteJSStringLiteral(Line->Children, Result);
 843       if (!Line->Affected)
 844         continue;
 845       for (FormatToken *FormatTok = Line->First; FormatTok;
 846            FormatTok = FormatTok->Next) {
 847         StringRef Input = FormatTok->TokenText;
 848         if (FormatTok->Finalized || !FormatTok->isStringLiteral() ||
 849             // NB: testing for not starting with a double quote to avoid
 850             // breaking `template strings`.
 851             (Style.JavaScriptQuotes == FormatStyle::JSQS_Single &&
 852              !Input.startswith("\"")) ||
 853             (Style.JavaScriptQuotes == FormatStyle::JSQS_Double &&
 854              !Input.startswith("\'")))
 855           continue;
 856
 857         // Change start and end quote.
 858         bool IsSingle = Style.JavaScriptQuotes == FormatStyle::JSQS_Single;
 859         SourceLocation Start = FormatTok->Tok.getLocation();
 860         auto Replace = [&](SourceLocation Start, unsigned Length,
 861                            StringRef ReplacementText) {
 862           auto Err = Result.add(tooling::Replacement(
 863               Env.getSourceManager(), Start, Length, ReplacementText));
 864           // FIXME: handle error. For now, print error message and skip the
 865           // replacement for release version.
 866           if (Err) {
 867             llvm::errs() << llvm::toString(std::move(Err)) << "\n";
 868             assert(false);
 869           }
 870         };
 871         Replace(Start, 1, IsSingle ? "'" : "\"");
 872         Replace(FormatTok->Tok.getEndLoc().getLocWithOffset(-1), 1,
 873                 IsSingle ? "'" : "\"");
 874
 875         // Escape internal quotes.
 876         bool Escaped = false;
 877         for (size_t i = 1; i < Input.size() - 1; i++) {
 878           switch (Input[i]) {
 879           case '\\':
 880             if (!Escaped && i + 1 < Input.size() &&
 881                 ((IsSingle && Input[i + 1] == '"') ||
 882                  (!IsSingle && Input[i + 1] == '\''))) {
 883               // Remove this \, it's escaping a " or ' that no longer needs
 884               // escaping
 885               Replace(Start.getLocWithOffset(i), 1, "");
 886               continue;
 887             }
 888             Escaped = !Escaped;
 889             break;
 890           case '\"':
 891           case '\'':
 892             if (!Escaped && IsSingle == (Input[i] == '\'')) {
 893               // Escape the quote.
 894               Replace(Start.getLocWithOffset(i), 0, "\\");
 895             }
 896             Escaped = false;
 897             break;
 898           default:
 899             Escaped = false;
 900             break;
 901           }
 902         }
 903       }
 904     }
 905   }
 906 };
 907
 908 class Formatter : public TokenAnalyzer {
 909 public:
 910   Formatter(const Environment &Env, const FormatStyle &Style,
 911             FormattingAttemptStatus *Status)
 912       : TokenAnalyzer(Env, Style), Status(Status) {}
 913
 914   tooling::Replacements
 915   analyze(TokenAnnotator &Annotator,
 916           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
 917           FormatTokenLexer &Tokens) override {
 918     tooling::Replacements Result;
 919     deriveLocalStyle(AnnotatedLines);
 920     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
 921                                           AnnotatedLines.end());
 922     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
 923       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
 924     }
 925     Annotator.setCommentLineLevels(AnnotatedLines);
 926
 927     WhitespaceManager Whitespaces(
 928         Env.getSourceManager(), Style,
 929         inputUsesCRLF(Env.getSourceManager().getBufferData(Env.getFileID())));
 930     ContinuationIndenter Indenter(Style, Tokens.getKeywords(),
 931                                   Env.getSourceManager(), Whitespaces, Encoding,
 932                                   BinPackInconclusiveFunctions);
 933     UnwrappedLineFormatter(&Indenter, &Whitespaces, Style, Tokens.getKeywords(),
 934                            Env.getSourceManager(), Status)
 935         .format(AnnotatedLines);
 936     for (const auto &R : Whitespaces.generateReplacements())
 937       if (Result.add(R))
 938         return Result;
 939     return Result;
 940   }
 941
 942 private:
 943
 944   static bool inputUsesCRLF(StringRef Text) {
 945     return Text.count('\r') * 2 > Text.count('\n');
 946   }
 947
 948   bool
 949   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
 950     for (const AnnotatedLine *Line : Lines) {
 951       if (hasCpp03IncompatibleFormat(Line->Children))
 952         return true;
 953       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
 954         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
 955           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
 956             return true;
 957           if (Tok->is(TT_TemplateCloser) &&
 958               Tok->Previous->is(TT_TemplateCloser))
 959             return true;
 960         }
 961       }
 962     }
 963     return false;
 964   }
 965
 966   int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
 967     int AlignmentDiff = 0;
 968     for (const AnnotatedLine *Line : Lines) {
 969       AlignmentDiff += countVariableAlignments(Line->Children);
 970       for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
 971         if (!Tok->is(TT_PointerOrReference))
 972           continue;
 973         bool SpaceBefore =
 974             Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
 975         bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
 976                           Tok->Next->WhitespaceRange.getEnd();
 977         if (SpaceBefore && !SpaceAfter)
 978           ++AlignmentDiff;
 979         if (!SpaceBefore && SpaceAfter)
 980           --AlignmentDiff;
 981       }
 982     }
 983     return AlignmentDiff;
 984   }
 985
 986   void
 987   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
 988     bool HasBinPackedFunction = false;
 989     bool HasOnePerLineFunction = false;
 990     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
 991       if (!AnnotatedLines[i]->First->Next)
 992         continue;
 993       FormatToken *Tok = AnnotatedLines[i]->First->Next;
 994       while (Tok->Next) {
 995         if (Tok->PackingKind == PPK_BinPacked)
 996           HasBinPackedFunction = true;
 997         if (Tok->PackingKind == PPK_OnePerLine)
 998           HasOnePerLineFunction = true;
 999
1000         Tok = Tok->Next;
1001       }
1002     }
1003     if (Style.DerivePointerAlignment)
1004       Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
1005                                    ? FormatStyle::PAS_Left
1006                                    : FormatStyle::PAS_Right;
1007     if (Style.Standard == FormatStyle::LS_Auto)
1008       Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
1009                            ? FormatStyle::LS_Cpp11
1010                            : FormatStyle::LS_Cpp03;
1011     BinPackInconclusiveFunctions =
1012         HasBinPackedFunction || !HasOnePerLineFunction;
1013   }
1014
1015   bool BinPackInconclusiveFunctions;
1016   FormattingAttemptStatus *Status;
1017 };
1018
1019 // This class clean up the erroneous/redundant code around the given ranges in
1020 // file.
1021 class Cleaner : public TokenAnalyzer {
1022 public:
1023   Cleaner(const Environment &Env, const FormatStyle &Style)
1024       : TokenAnalyzer(Env, Style),
1025         DeletedTokens(FormatTokenLess(Env.getSourceManager())) {}
1026
1027   // FIXME: eliminate unused parameters.
1028   tooling::Replacements
1029   analyze(TokenAnnotator &Annotator,
1030           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1031           FormatTokenLexer &Tokens) override {
1032     // FIXME: in the current implementation the granularity of affected range
1033     // is an annotated line. However, this is not sufficient. Furthermore,
1034     // redundant code introduced by replacements does not necessarily
1035     // intercept with ranges of replacements that result in the redundancy.
1036     // To determine if some redundant code is actually introduced by
1037     // replacements(e.g. deletions), we need to come up with a more
1038     // sophisticated way of computing affected ranges.
1039     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
1040                                           AnnotatedLines.end());
1041
1042     checkEmptyNamespace(AnnotatedLines);
1043
1044     for (auto &Line : AnnotatedLines) {
1045       if (Line->Affected) {
1046         cleanupRight(Line->First, tok::comma, tok::comma);
1047         cleanupRight(Line->First, TT_CtorInitializerColon, tok::comma);
1048         cleanupRight(Line->First, tok::l_paren, tok::comma);
1049         cleanupLeft(Line->First, tok::comma, tok::r_paren);
1050         cleanupLeft(Line->First, TT_CtorInitializerComma, tok::l_brace);
1051         cleanupLeft(Line->First, TT_CtorInitializerColon, tok::l_brace);
1052         cleanupLeft(Line->First, TT_CtorInitializerColon, tok::equal);
1053       }
1054     }
1055
1056     return generateFixes();
1057   }
1058
1059 private:
1060   bool containsOnlyComments(const AnnotatedLine &Line) {
1061     for (FormatToken *Tok = Line.First; Tok != nullptr; Tok = Tok->Next) {
1062       if (Tok->isNot(tok::comment))
1063         return false;
1064     }
1065     return true;
1066   }
1067
1068   // Iterate through all lines and remove any empty (nested) namespaces.
1069   void checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1070     std::set<unsigned> DeletedLines;
1071     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1072       auto &Line = *AnnotatedLines[i];
1073       if (Line.startsWith(tok::kw_namespace) ||
1074           Line.startsWith(tok::kw_inline, tok::kw_namespace)) {
1075         checkEmptyNamespace(AnnotatedLines, i, i, DeletedLines);
1076       }
1077     }
1078
1079     for (auto Line : DeletedLines) {
1080       FormatToken *Tok = AnnotatedLines[Line]->First;
1081       while (Tok) {
1082         deleteToken(Tok);
1083         Tok = Tok->Next;
1084       }
1085     }
1086   }
1087
1088   // The function checks if the namespace, which starts from \p CurrentLine, and
1089   // its nested namespaces are empty and delete them if they are empty. It also
1090   // sets \p NewLine to the last line checked.
1091   // Returns true if the current namespace is empty.
1092   bool checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1093                            unsigned CurrentLine, unsigned &NewLine,
1094                            std::set<unsigned> &DeletedLines) {
1095     unsigned InitLine = CurrentLine, End = AnnotatedLines.size();
1096     if (Style.BraceWrapping.AfterNamespace) {
1097       // If the left brace is in a new line, we should consume it first so that
1098       // it does not make the namespace non-empty.
1099       // FIXME: error handling if there is no left brace.
1100       if (!AnnotatedLines[++CurrentLine]->startsWith(tok::l_brace)) {
1101         NewLine = CurrentLine;
1102         return false;
1103       }
1104     } else if (!AnnotatedLines[CurrentLine]->endsWith(tok::l_brace)) {
1105       return false;
1106     }
1107     while (++CurrentLine < End) {
1108       if (AnnotatedLines[CurrentLine]->startsWith(tok::r_brace))
1109         break;
1110
1111       if (AnnotatedLines[CurrentLine]->startsWith(tok::kw_namespace) ||
1112           AnnotatedLines[CurrentLine]->startsWith(tok::kw_inline,
1113                                                   tok::kw_namespace)) {
1114         if (!checkEmptyNamespace(AnnotatedLines, CurrentLine, NewLine,
1115                                  DeletedLines))
1116           return false;
1117         CurrentLine = NewLine;
1118         continue;
1119       }
1120
1121       if (containsOnlyComments(*AnnotatedLines[CurrentLine]))
1122         continue;
1123
1124       // If there is anything other than comments or nested namespaces in the
1125       // current namespace, the namespace cannot be empty.
1126       NewLine = CurrentLine;
1127       return false;
1128     }
1129
1130     NewLine = CurrentLine;
1131     if (CurrentLine >= End)
1132       return false;
1133
1134     // Check if the empty namespace is actually affected by changed ranges.
1135     if (!AffectedRangeMgr.affectsCharSourceRange(CharSourceRange::getCharRange(
1136             AnnotatedLines[InitLine]->First->Tok.getLocation(),
1137             AnnotatedLines[CurrentLine]->Last->Tok.getEndLoc())))
1138       return false;
1139
1140     for (unsigned i = InitLine; i <= CurrentLine; ++i) {
1141       DeletedLines.insert(i);
1142     }
1143
1144     return true;
1145   }
1146
1147   // Checks pairs {start, start->next},..., {end->previous, end} and deletes one
1148   // of the token in the pair if the left token has \p LK token kind and the
1149   // right token has \p RK token kind. If \p DeleteLeft is true, the left token
1150   // is deleted on match; otherwise, the right token is deleted.
1151   template <typename LeftKind, typename RightKind>
1152   void cleanupPair(FormatToken *Start, LeftKind LK, RightKind RK,
1153                    bool DeleteLeft) {
1154     auto NextNotDeleted = [this](const FormatToken &Tok) -> FormatToken * {
1155       for (auto *Res = Tok.Next; Res; Res = Res->Next)
1156         if (!Res->is(tok::comment) &&
1157             DeletedTokens.find(Res) == DeletedTokens.end())
1158           return Res;
1159       return nullptr;
1160     };
1161     for (auto *Left = Start; Left;) {
1162       auto *Right = NextNotDeleted(*Left);
1163       if (!Right)
1164         break;
1165       if (Left->is(LK) && Right->is(RK)) {
1166         deleteToken(DeleteLeft ? Left : Right);
1167         for (auto *Tok = Left->Next; Tok && Tok != Right; Tok = Tok->Next)
1168           deleteToken(Tok);
1169         // If the right token is deleted, we should keep the left token
1170         // unchanged and pair it with the new right token.
1171         if (!DeleteLeft)
1172           continue;
1173       }
1174       Left = Right;
1175     }
1176   }
1177
1178   template <typename LeftKind, typename RightKind>
1179   void cleanupLeft(FormatToken *Start, LeftKind LK, RightKind RK) {
1180     cleanupPair(Start, LK, RK, /*DeleteLeft=*/true);
1181   }
1182
1183   template <typename LeftKind, typename RightKind>
1184   void cleanupRight(FormatToken *Start, LeftKind LK, RightKind RK) {
1185     cleanupPair(Start, LK, RK, /*DeleteLeft=*/false);
1186   }
1187
1188   // Delete the given token.
1189   inline void deleteToken(FormatToken *Tok) {
1190     if (Tok)
1191       DeletedTokens.insert(Tok);
1192   }
1193
1194   tooling::Replacements generateFixes() {
1195     tooling::Replacements Fixes;
1196     std::vector<FormatToken *> Tokens;
1197     std::copy(DeletedTokens.begin(), DeletedTokens.end(),
1198               std::back_inserter(Tokens));
1199
1200     // Merge multiple continuous token deletions into one big deletion so that
1201     // the number of replacements can be reduced. This makes computing affected
1202     // ranges more efficient when we run reformat on the changed code.
1203     unsigned Idx = 0;
1204     while (Idx < Tokens.size()) {
1205       unsigned St = Idx, End = Idx;
1206       while ((End + 1) < Tokens.size() &&
1207              Tokens[End]->Next == Tokens[End + 1]) {
1208         End++;
1209       }
1210       auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
1211                                               Tokens[End]->Tok.getEndLoc());
1212       auto Err =
1213           Fixes.add(tooling::Replacement(Env.getSourceManager(), SR, ""));
1214       // FIXME: better error handling. for now just print error message and skip
1215       // for the release version.
1216       if (Err) {
1217         llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1218         assert(false && "Fixes must not conflict!");
1219       }
1220       Idx = End + 1;
1221     }
1222
1223     return Fixes;
1224   }
1225
1226   // Class for less-than inequality comparason for the set `RedundantTokens`.
1227   // We store tokens in the order they appear in the translation unit so that
1228   // we do not need to sort them in `generateFixes()`.
1229   struct FormatTokenLess {
1230     FormatTokenLess(const SourceManager &SM) : SM(SM) {}
1231
1232     bool operator()(const FormatToken *LHS, const FormatToken *RHS) const {
1233       return SM.isBeforeInTranslationUnit(LHS->Tok.getLocation(),
1234                                           RHS->Tok.getLocation());
1235     }
1236     const SourceManager &SM;
1237   };
1238
1239   // Tokens to be deleted.
1240   std::set<FormatToken *, FormatTokenLess> DeletedTokens;
1241 };
1242
1243 struct IncludeDirective {
1244   StringRef Filename;
1245   StringRef Text;
1246   unsigned Offset;
1247   int Category;
1248 };
1249
1250 } // end anonymous namespace
1251
1252 // Determines whether 'Ranges' intersects with ('Start', 'End').
1253 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
1254                          unsigned End) {
1255   for (auto Range : Ranges) {
1256     if (Range.getOffset() < End &&
1257         Range.getOffset() + Range.getLength() > Start)
1258       return true;
1259   }
1260   return false;
1261 }
1262
1263 // Returns a pair (Index, OffsetToEOL) describing the position of the cursor
1264 // before sorting/deduplicating. Index is the index of the include under the
1265 // cursor in the original set of includes. If this include has duplicates, it is
1266 // the index of the first of the duplicates as the others are going to be
1267 // removed. OffsetToEOL describes the cursor's position relative to the end of
1268 // its current line.
1269 // If `Cursor` is not on any #include, `Index` will be UINT_MAX.
1270 static std::pair<unsigned, unsigned>
1271 FindCursorIndex(const SmallVectorImpl<IncludeDirective> &Includes,
1272                 const SmallVectorImpl<unsigned> &Indices, unsigned Cursor) {
1273   unsigned CursorIndex = UINT_MAX;
1274   unsigned OffsetToEOL = 0;
1275   for (int i = 0, e = Includes.size(); i != e; ++i) {
1276     unsigned Start = Includes[Indices[i]].Offset;
1277     unsigned End = Start + Includes[Indices[i]].Text.size();
1278     if (!(Cursor >= Start && Cursor < End))
1279       continue;
1280     CursorIndex = Indices[i];
1281     OffsetToEOL = End - Cursor;
1282     // Put the cursor on the only remaining #include among the duplicate
1283     // #includes.
1284     while (--i >= 0 && Includes[CursorIndex].Text == Includes[Indices[i]].Text)
1285       CursorIndex = i;
1286     break;
1287   }
1288   return std::make_pair(CursorIndex, OffsetToEOL);
1289 }
1290
1291 // Sorts and deduplicate a block of includes given by 'Includes' alphabetically
1292 // adding the necessary replacement to 'Replaces'. 'Includes' must be in strict
1293 // source order.
1294 // #include directives with the same text will be deduplicated, and only the
1295 // first #include in the duplicate #includes remains. If the `Cursor` is
1296 // provided and put on a deleted #include, it will be moved to the remaining
1297 // #include in the duplicate #includes.
1298 static void sortCppIncludes(const FormatStyle &Style,
1299                             const SmallVectorImpl<IncludeDirective> &Includes,
1300                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
1301                             tooling::Replacements &Replaces, unsigned *Cursor) {
1302   unsigned IncludesBeginOffset = Includes.front().Offset;
1303   unsigned IncludesEndOffset =
1304       Includes.back().Offset + Includes.back().Text.size();
1305   unsigned IncludesBlockSize = IncludesEndOffset - IncludesBeginOffset;
1306   if (!affectsRange(Ranges, IncludesBeginOffset, IncludesEndOffset))
1307     return;
1308   SmallVector<unsigned, 16> Indices;
1309   for (unsigned i = 0, e = Includes.size(); i != e; ++i)
1310     Indices.push_back(i);
1311   std::stable_sort(
1312       Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
1313         return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
1314                std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
1315       });
1316   // The index of the include on which the cursor will be put after
1317   // sorting/deduplicating.
1318   unsigned CursorIndex;
1319   // The offset from cursor to the end of line.
1320   unsigned CursorToEOLOffset;
1321   if (Cursor)
1322     std::tie(CursorIndex, CursorToEOLOffset) =
1323         FindCursorIndex(Includes, Indices, *Cursor);
1324
1325   // Deduplicate #includes.
1326   Indices.erase(std::unique(Indices.begin(), Indices.end(),
1327                             [&](unsigned LHSI, unsigned RHSI) {
1328                               return Includes[LHSI].Text == Includes[RHSI].Text;
1329                             }),
1330                 Indices.end());
1331
1332   // If the #includes are out of order, we generate a single replacement fixing
1333   // the entire block. Otherwise, no replacement is generated.
1334   if (Indices.size() == Includes.size() &&
1335       std::is_sorted(Indices.begin(), Indices.end()))
1336     return;
1337
1338   std::string result;
1339   for (unsigned Index : Indices) {
1340     if (!result.empty())
1341       result += "\n";
1342     result += Includes[Index].Text;
1343     if (Cursor && CursorIndex == Index)
1344       *Cursor = IncludesBeginOffset + result.size() - CursorToEOLOffset;
1345   }
1346
1347   auto Err = Replaces.add(tooling::Replacement(
1348       FileName, Includes.front().Offset, IncludesBlockSize, result));
1349   // FIXME: better error handling. For now, just skip the replacement for the
1350   // release version.
1351   if (Err) {
1352     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1353     assert(false);
1354   }
1355 }
1356
1357 namespace {
1358
1359 // This class manages priorities of #include categories and calculates
1360 // priorities for headers.
1361 class IncludeCategoryManager {
1362 public:
1363   IncludeCategoryManager(const FormatStyle &Style, StringRef FileName)
1364       : Style(Style), FileName(FileName) {
1365     FileStem = llvm::sys::path::stem(FileName);
1366     for (const auto &Category : Style.IncludeCategories)
1367       CategoryRegexs.emplace_back(Category.Regex);
1368     IsMainFile = FileName.endswith(".c") || FileName.endswith(".cc") ||
1369                  FileName.endswith(".cpp") || FileName.endswith(".c++") ||
1370                  FileName.endswith(".cxx") || FileName.endswith(".m") ||
1371                  FileName.endswith(".mm");
1372   }
1373
1374   // Returns the priority of the category which \p IncludeName belongs to.
1375   // If \p CheckMainHeader is true and \p IncludeName is a main header, returns
1376   // 0. Otherwise, returns the priority of the matching category or INT_MAX.
1377   int getIncludePriority(StringRef IncludeName, bool CheckMainHeader) {
1378     int Ret = INT_MAX;
1379     for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i)
1380       if (CategoryRegexs[i].match(IncludeName)) {
1381         Ret = Style.IncludeCategories[i].Priority;
1382         break;
1383       }
1384     if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName))
1385       Ret = 0;
1386     return Ret;
1387   }
1388
1389 private:
1390   bool isMainHeader(StringRef IncludeName) const {
1391     if (!IncludeName.startswith("\""))
1392       return false;
1393     StringRef HeaderStem =
1394         llvm::sys::path::stem(IncludeName.drop_front(1).drop_back(1));
1395     if (FileStem.startswith(HeaderStem)) {
1396       llvm::Regex MainIncludeRegex(
1397           (HeaderStem + Style.IncludeIsMainRegex).str());
1398       if (MainIncludeRegex.match(FileStem))
1399         return true;
1400     }
1401     return false;
1402   }
1403
1404   const FormatStyle &Style;
1405   bool IsMainFile;
1406   StringRef FileName;
1407   StringRef FileStem;
1408   SmallVector<llvm::Regex, 4> CategoryRegexs;
1409 };
1410
1411 const char IncludeRegexPattern[] =
1412     R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
1413
1414 } // anonymous namespace
1415
1416 tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
1417                                       ArrayRef<tooling::Range> Ranges,
1418                                       StringRef FileName,
1419                                       tooling::Replacements &Replaces,
1420                                       unsigned *Cursor) {
1421   unsigned Prev = 0;
1422   unsigned SearchFrom = 0;
1423   llvm::Regex IncludeRegex(IncludeRegexPattern);
1424   SmallVector<StringRef, 4> Matches;
1425   SmallVector<IncludeDirective, 16> IncludesInBlock;
1426
1427   // In compiled files, consider the first #include to be the main #include of
1428   // the file if it is not a system #include. This ensures that the header
1429   // doesn't have hidden dependencies
1430   // (http://llvm.org/docs/CodingStandards.html#include-style).
1431   //
1432   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
1433   // cases where the first #include is unlikely to be the main header.
1434   IncludeCategoryManager Categories(Style, FileName);
1435   bool FirstIncludeBlock = true;
1436   bool MainIncludeFound = false;
1437   bool FormattingOff = false;
1438
1439   for (;;) {
1440     auto Pos = Code.find('\n', SearchFrom);
1441     StringRef Line =
1442         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
1443
1444     StringRef Trimmed = Line.trim();
1445     if (Trimmed == "// clang-format off")
1446       FormattingOff = true;
1447     else if (Trimmed == "// clang-format on")
1448       FormattingOff = false;
1449
1450     if (!FormattingOff && !Line.endswith("\\")) {
1451       if (IncludeRegex.match(Line, &Matches)) {
1452         StringRef IncludeName = Matches[2];
1453         int Category = Categories.getIncludePriority(
1454             IncludeName,
1455             /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
1456         if (Category == 0)
1457           MainIncludeFound = true;
1458         IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
1459       } else if (!IncludesInBlock.empty()) {
1460         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces,
1461                         Cursor);
1462         IncludesInBlock.clear();
1463         FirstIncludeBlock = false;
1464       }
1465       Prev = Pos + 1;
1466     }
1467     if (Pos == StringRef::npos || Pos + 1 == Code.size())
1468       break;
1469     SearchFrom = Pos + 1;
1470   }
1471   if (!IncludesInBlock.empty())
1472     sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces, Cursor);
1473   return Replaces;
1474 }
1475
1476 bool isMpegTS(StringRef Code) {
1477   // MPEG transport streams use the ".ts" file extension. clang-format should
1478   // not attempt to format those. MPEG TS' frame format starts with 0x47 every
1479   // 189 bytes - detect that and return.
1480   return Code.size() > 188 && Code[0] == 0x47 && Code[188] == 0x47;
1481 }
1482
1483 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
1484                                    ArrayRef<tooling::Range> Ranges,
1485                                    StringRef FileName, unsigned *Cursor) {
1486   tooling::Replacements Replaces;
1487   if (!Style.SortIncludes)
1488     return Replaces;
1489   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript &&
1490       isMpegTS(Code))
1491     return Replaces;
1492   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
1493     return sortJavaScriptImports(Style, Code, Ranges, FileName);
1494   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
1495   return Replaces;
1496 }
1497
1498 template <typename T>
1499 static llvm::Expected<tooling::Replacements>
1500 processReplacements(T ProcessFunc, StringRef Code,
1501                     const tooling::Replacements &Replaces,
1502                     const FormatStyle &Style) {
1503   if (Replaces.empty())
1504     return tooling::Replacements();
1505
1506   auto NewCode = applyAllReplacements(Code, Replaces);
1507   if (!NewCode)
1508     return NewCode.takeError();
1509   std::vector<tooling::Range> ChangedRanges = Replaces.getAffectedRanges();
1510   StringRef FileName = Replaces.begin()->getFilePath();
1511
1512   tooling::Replacements FormatReplaces =
1513       ProcessFunc(Style, *NewCode, ChangedRanges, FileName);
1514
1515   return Replaces.merge(FormatReplaces);
1516 }
1517
1518 llvm::Expected<tooling::Replacements>
1519 formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
1520                    const FormatStyle &Style) {
1521   // We need to use lambda function here since there are two versions of
1522   // `sortIncludes`.
1523   auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
1524                          std::vector<tooling::Range> Ranges,
1525                          StringRef FileName) -> tooling::Replacements {
1526     return sortIncludes(Style, Code, Ranges, FileName);
1527   };
1528   auto SortedReplaces =
1529       processReplacements(SortIncludes, Code, Replaces, Style);
1530   if (!SortedReplaces)
1531     return SortedReplaces.takeError();
1532
1533   // We need to use lambda function here since there are two versions of
1534   // `reformat`.
1535   auto Reformat = [](const FormatStyle &Style, StringRef Code,
1536                      std::vector<tooling::Range> Ranges,
1537                      StringRef FileName) -> tooling::Replacements {
1538     return reformat(Style, Code, Ranges, FileName);
1539   };
1540   return processReplacements(Reformat, Code, *SortedReplaces, Style);
1541 }
1542
1543 namespace {
1544
1545 inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
1546   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 0 &&
1547          llvm::Regex(IncludeRegexPattern).match(Replace.getReplacementText());
1548 }
1549
1550 inline bool isHeaderDeletion(const tooling::Replacement &Replace) {
1551   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 1;
1552 }
1553
1554 // Returns the offset after skipping a sequence of tokens, matched by \p
1555 // GetOffsetAfterSequence, from the start of the code.
1556 // \p GetOffsetAfterSequence should be a function that matches a sequence of
1557 // tokens and returns an offset after the sequence.
1558 unsigned getOffsetAfterTokenSequence(
1559     StringRef FileName, StringRef Code, const FormatStyle &Style,
1560     llvm::function_ref<unsigned(const SourceManager &, Lexer &, Token &)>
1561         GetOffsetAfterSequence) {
1562   std::unique_ptr<Environment> Env =
1563       Environment::CreateVirtualEnvironment(Code, FileName, /*Ranges=*/{});
1564   const SourceManager &SourceMgr = Env->getSourceManager();
1565   Lexer Lex(Env->getFileID(), SourceMgr.getBuffer(Env->getFileID()), SourceMgr,
1566             getFormattingLangOpts(Style));
1567   Token Tok;
1568   // Get the first token.
1569   Lex.LexFromRawLexer(Tok);
1570   return GetOffsetAfterSequence(SourceMgr, Lex, Tok);
1571 }
1572
1573 // Check if a sequence of tokens is like "#<Name> <raw_identifier>". If it is,
1574 // \p Tok will be the token after this directive; otherwise, it can be any token
1575 // after the given \p Tok (including \p Tok).
1576 bool checkAndConsumeDirectiveWithName(Lexer &Lex, StringRef Name, Token &Tok) {
1577   bool Matched = Tok.is(tok::hash) && !Lex.LexFromRawLexer(Tok) &&
1578                  Tok.is(tok::raw_identifier) &&
1579                  Tok.getRawIdentifier() == Name && !Lex.LexFromRawLexer(Tok) &&
1580                  Tok.is(tok::raw_identifier);
1581   if (Matched)
1582     Lex.LexFromRawLexer(Tok);
1583   return Matched;
1584 }
1585
1586 void skipComments(Lexer &Lex, Token &Tok) {
1587   while (Tok.is(tok::comment))
1588     if (Lex.LexFromRawLexer(Tok))
1589       return;
1590 }
1591
1592 // Returns the offset after header guard directives and any comments
1593 // before/after header guards. If no header guard presents in the code, this
1594 // will returns the offset after skipping all comments from the start of the
1595 // code.
1596 unsigned getOffsetAfterHeaderGuardsAndComments(StringRef FileName,
1597                                                StringRef Code,
1598                                                const FormatStyle &Style) {
1599   return getOffsetAfterTokenSequence(
1600       FileName, Code, Style,
1601       [](const SourceManager &SM, Lexer &Lex, Token Tok) {
1602         skipComments(Lex, Tok);
1603         unsigned InitialOffset = SM.getFileOffset(Tok.getLocation());
1604         if (checkAndConsumeDirectiveWithName(Lex, "ifndef", Tok)) {
1605           skipComments(Lex, Tok);
1606           if (checkAndConsumeDirectiveWithName(Lex, "define", Tok))
1607             return SM.getFileOffset(Tok.getLocation());
1608         }
1609         return InitialOffset;
1610       });
1611 }
1612
1613 // Check if a sequence of tokens is like
1614 //    "#include ("header.h" | <header.h>)".
1615 // If it is, \p Tok will be the token after this directive; otherwise, it can be
1616 // any token after the given \p Tok (including \p Tok).
1617 bool checkAndConsumeInclusiveDirective(Lexer &Lex, Token &Tok) {
1618   auto Matched = [&]() {
1619     Lex.LexFromRawLexer(Tok);
1620     return true;
1621   };
1622   if (Tok.is(tok::hash) && !Lex.LexFromRawLexer(Tok) &&
1623       Tok.is(tok::raw_identifier) && Tok.getRawIdentifier() == "include") {
1624     if (Lex.LexFromRawLexer(Tok))
1625       return false;
1626     if (Tok.is(tok::string_literal))
1627       return Matched();
1628     if (Tok.is(tok::less)) {
1629       while (!Lex.LexFromRawLexer(Tok) && Tok.isNot(tok::greater)) {
1630       }
1631       if (Tok.is(tok::greater))
1632         return Matched();
1633     }
1634   }
1635   return false;
1636 }
1637
1638 // Returns the offset of the last #include directive after which a new
1639 // #include can be inserted. This ignores #include's after the #include block(s)
1640 // in the beginning of a file to avoid inserting headers into code sections
1641 // where new #include's should not be added by default.
1642 // These code sections include:
1643 //      - raw string literals (containing #include).
1644 //      - #if blocks.
1645 //      - Special #include's among declarations (e.g. functions).
1646 //
1647 // If no #include after which a new #include can be inserted, this returns the
1648 // offset after skipping all comments from the start of the code.
1649 // Inserting after an #include is not allowed if it comes after code that is not
1650 // #include (e.g. pre-processing directive that is not #include, declarations).
1651 unsigned getMaxHeaderInsertionOffset(StringRef FileName, StringRef Code,
1652                                      const FormatStyle &Style) {
1653   return getOffsetAfterTokenSequence(
1654       FileName, Code, Style,
1655       [](const SourceManager &SM, Lexer &Lex, Token Tok) {
1656         skipComments(Lex, Tok);
1657         unsigned MaxOffset = SM.getFileOffset(Tok.getLocation());
1658         while (checkAndConsumeInclusiveDirective(Lex, Tok))
1659           MaxOffset = SM.getFileOffset(Tok.getLocation());
1660         return MaxOffset;
1661       });
1662 }
1663
1664 bool isDeletedHeader(llvm::StringRef HeaderName,
1665                      const std::set<llvm::StringRef> &HeadersToDelete) {
1666   return HeadersToDelete.count(HeaderName) ||
1667          HeadersToDelete.count(HeaderName.trim("\"<>"));
1668 }
1669
1670 // FIXME: insert empty lines between newly created blocks.
1671 tooling::Replacements
1672 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
1673                         const FormatStyle &Style) {
1674   if (!Style.isCpp())
1675     return Replaces;
1676
1677   tooling::Replacements HeaderInsertions;
1678   std::set<llvm::StringRef> HeadersToDelete;
1679   tooling::Replacements Result;
1680   for (const auto &R : Replaces) {
1681     if (isHeaderInsertion(R)) {
1682       // Replacements from \p Replaces must be conflict-free already, so we can
1683       // simply consume the error.
1684       llvm::consumeError(HeaderInsertions.add(R));
1685     } else if (isHeaderDeletion(R)) {
1686       HeadersToDelete.insert(R.getReplacementText());
1687     } else if (R.getOffset() == UINT_MAX) {
1688       llvm::errs() << "Insertions other than header #include insertion are "
1689                       "not supported! "
1690                    << R.getReplacementText() << "\n";
1691     } else {
1692       llvm::consumeError(Result.add(R));
1693     }
1694   }
1695   if (HeaderInsertions.empty() && HeadersToDelete.empty())
1696     return Replaces;
1697
1698   llvm::Regex IncludeRegex(IncludeRegexPattern);
1699   llvm::Regex DefineRegex(R"(^[\t\ ]*#[\t\ ]*define[\t\ ]*[^\\]*$)");
1700   SmallVector<StringRef, 4> Matches;
1701
1702   StringRef FileName = Replaces.begin()->getFilePath();
1703   IncludeCategoryManager Categories(Style, FileName);
1704
1705   // Record the offset of the end of the last include in each category.
1706   std::map<int, int> CategoryEndOffsets;
1707   // All possible priorities.
1708   // Add 0 for main header and INT_MAX for headers that are not in any category.
1709   std::set<int> Priorities = {0, INT_MAX};
1710   for (const auto &Category : Style.IncludeCategories)
1711     Priorities.insert(Category.Priority);
1712   int FirstIncludeOffset = -1;
1713   // All new headers should be inserted after this offset.
1714   unsigned MinInsertOffset =
1715       getOffsetAfterHeaderGuardsAndComments(FileName, Code, Style);
1716   StringRef TrimmedCode = Code.drop_front(MinInsertOffset);
1717   // Max insertion offset in the original code.
1718   unsigned MaxInsertOffset =
1719       MinInsertOffset +
1720       getMaxHeaderInsertionOffset(FileName, TrimmedCode, Style);
1721   SmallVector<StringRef, 32> Lines;
1722   TrimmedCode.split(Lines, '\n');
1723   unsigned Offset = MinInsertOffset;
1724   unsigned NextLineOffset;
1725   std::set<StringRef> ExistingIncludes;
1726   for (auto Line : Lines) {
1727     NextLineOffset = std::min(Code.size(), Offset + Line.size() + 1);
1728     if (IncludeRegex.match(Line, &Matches)) {
1729       // The header name with quotes or angle brackets.
1730       StringRef IncludeName = Matches[2];
1731       ExistingIncludes.insert(IncludeName);
1732       // Only record the offset of current #include if we can insert after it.
1733       if (Offset <= MaxInsertOffset) {
1734         int Category = Categories.getIncludePriority(
1735             IncludeName, /*CheckMainHeader=*/FirstIncludeOffset < 0);
1736         CategoryEndOffsets[Category] = NextLineOffset;
1737         if (FirstIncludeOffset < 0)
1738           FirstIncludeOffset = Offset;
1739       }
1740       if (isDeletedHeader(IncludeName, HeadersToDelete)) {
1741         // If this is the last line without trailing newline, we need to make
1742         // sure we don't delete across the file boundary.
1743         unsigned Length = std::min(Line.size() + 1, Code.size() - Offset);
1744         llvm::Error Err =
1745             Result.add(tooling::Replacement(FileName, Offset, Length, ""));
1746         if (Err) {
1747           // Ignore the deletion on conflict.
1748           llvm::errs() << "Failed to add header deletion replacement for "
1749                        << IncludeName << ": " << llvm::toString(std::move(Err))
1750                        << "\n";
1751         }
1752       }
1753     }
1754     Offset = NextLineOffset;
1755   }
1756
1757   // Populate CategoryEndOfssets:
1758   // - Ensure that CategoryEndOffset[Highest] is always populated.
1759   // - If CategoryEndOffset[Priority] isn't set, use the next higher value that
1760   //   is set, up to CategoryEndOffset[Highest].
1761   auto Highest = Priorities.begin();
1762   if (CategoryEndOffsets.find(*Highest) == CategoryEndOffsets.end()) {
1763     if (FirstIncludeOffset >= 0)
1764       CategoryEndOffsets[*Highest] = FirstIncludeOffset;
1765     else
1766       CategoryEndOffsets[*Highest] = MinInsertOffset;
1767   }
1768   // By this point, CategoryEndOffset[Highest] is always set appropriately:
1769   //  - to an appropriate location before/after existing #includes, or
1770   //  - to right after the header guard, or
1771   //  - to the beginning of the file.
1772   for (auto I = ++Priorities.begin(), E = Priorities.end(); I != E; ++I)
1773     if (CategoryEndOffsets.find(*I) == CategoryEndOffsets.end())
1774       CategoryEndOffsets[*I] = CategoryEndOffsets[*std::prev(I)];
1775
1776   bool NeedNewLineAtEnd = !Code.empty() && Code.back() != '\n';
1777   for (const auto &R : HeaderInsertions) {
1778     auto IncludeDirective = R.getReplacementText();
1779     bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
1780     assert(Matched && "Header insertion replacement must have replacement text "
1781                       "'#include ...'");
1782     (void)Matched;
1783     auto IncludeName = Matches[2];
1784     if (ExistingIncludes.find(IncludeName) != ExistingIncludes.end()) {
1785       DEBUG(llvm::dbgs() << "Skip adding existing include : " << IncludeName
1786                          << "\n");
1787       continue;
1788     }
1789     int Category =
1790         Categories.getIncludePriority(IncludeName, /*CheckMainHeader=*/true);
1791     Offset = CategoryEndOffsets[Category];
1792     std::string NewInclude = !IncludeDirective.endswith("\n")
1793                                  ? (IncludeDirective + "\n").str()
1794                                  : IncludeDirective.str();
1795     // When inserting headers at end of the code, also append '\n' to the code
1796     // if it does not end with '\n'.
1797     if (NeedNewLineAtEnd && Offset == Code.size()) {
1798       NewInclude = "\n" + NewInclude;
1799       NeedNewLineAtEnd = false;
1800     }
1801     auto NewReplace = tooling::Replacement(FileName, Offset, 0, NewInclude);
1802     auto Err = Result.add(NewReplace);
1803     if (Err) {
1804       llvm::consumeError(std::move(Err));
1805       unsigned NewOffset = Result.getShiftedCodePosition(Offset);
1806       NewReplace = tooling::Replacement(FileName, NewOffset, 0, NewInclude);
1807       Result = Result.merge(tooling::Replacements(NewReplace));
1808     }
1809   }
1810   return Result;
1811 }
1812
1813 } // anonymous namespace
1814
1815 llvm::Expected<tooling::Replacements>
1816 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
1817                           const FormatStyle &Style) {
1818   // We need to use lambda function here since there are two versions of
1819   // `cleanup`.
1820   auto Cleanup = [](const FormatStyle &Style, StringRef Code,
1821                     std::vector<tooling::Range> Ranges,
1822                     StringRef FileName) -> tooling::Replacements {
1823     return cleanup(Style, Code, Ranges, FileName);
1824   };
1825   // Make header insertion replacements insert new headers into correct blocks.
1826   tooling::Replacements NewReplaces =
1827       fixCppIncludeInsertions(Code, Replaces, Style);
1828   return processReplacements(Cleanup, Code, NewReplaces, Style);
1829 }
1830
1831 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1832                                ArrayRef<tooling::Range> Ranges,
1833                                StringRef FileName,
1834                                FormattingAttemptStatus *Status) {
1835   FormatStyle Expanded = expandPresets(Style);
1836   if (Expanded.DisableFormat)
1837     return tooling::Replacements();
1838   if (Expanded.Language == FormatStyle::LK_JavaScript && isMpegTS(Code))
1839     return tooling::Replacements();
1840   auto Env = Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1841
1842   auto reformatAfterApplying = [&] (TokenAnalyzer& Fixer) {
1843     tooling::Replacements Fixes = Fixer.process();
1844     if (!Fixes.empty()) {
1845       auto NewCode = applyAllReplacements(Code, Fixes);
1846       if (NewCode) {
1847         auto NewEnv = Environment::CreateVirtualEnvironment(
1848             *NewCode, FileName,
1849             tooling::calculateRangesAfterReplacements(Fixes, Ranges));
1850         Formatter Format(*NewEnv, Expanded, Status);
1851         return Fixes.merge(Format.process());
1852       }
1853     }
1854     Formatter Format(*Env, Expanded, Status);
1855     return Format.process();
1856   };
1857
1858   if (Style.Language == FormatStyle::LK_Cpp &&
1859       Style.FixNamespaceComments) {
1860     NamespaceEndCommentsFixer CommentsFixer(*Env, Expanded);
1861     return reformatAfterApplying(CommentsFixer);
1862   }
1863
1864   if (Style.Language == FormatStyle::LK_JavaScript &&
1865       Style.JavaScriptQuotes != FormatStyle::JSQS_Leave) {
1866     JavaScriptRequoter Requoter(*Env, Expanded);
1867     return reformatAfterApplying(Requoter);
1868   }
1869
1870   Formatter Format(*Env, Expanded, Status);
1871   return Format.process();
1872 }
1873
1874 tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
1875                               ArrayRef<tooling::Range> Ranges,
1876                               StringRef FileName) {
1877   std::unique_ptr<Environment> Env =
1878       Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1879   Cleaner Clean(*Env, Style);
1880   return Clean.process();
1881 }
1882
1883 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1884                                ArrayRef<tooling::Range> Ranges,
1885                                StringRef FileName, bool *IncompleteFormat) {
1886   FormattingAttemptStatus Status;
1887   auto Result = reformat(Style, Code, Ranges, FileName, &Status);
1888   if (!Status.FormatComplete)
1889     *IncompleteFormat = true;
1890   return Result;
1891 }
1892
1893 tooling::Replacements fixNamespaceEndComments(const FormatStyle &Style,
1894                                               StringRef Code,
1895                                               ArrayRef<tooling::Range> Ranges,
1896                                               StringRef FileName) {
1897   std::unique_ptr<Environment> Env =
1898       Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
1899   NamespaceEndCommentsFixer Fix(*Env, Style);
1900   return Fix.process();
1901 }
1902
1903 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
1904   LangOptions LangOpts;
1905   LangOpts.CPlusPlus = 1;
1906   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1907   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1908   LangOpts.CPlusPlus1z = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1909   LangOpts.LineComment = 1;
1910   bool AlternativeOperators = Style.isCpp();
1911   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
1912   LangOpts.Bool = 1;
1913   LangOpts.ObjC1 = 1;
1914   LangOpts.ObjC2 = 1;
1915   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
1916   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
1917   return LangOpts;
1918 }
1919
1920 const char *StyleOptionHelpDescription =
1921     "Coding style, currently supports:\n"
1922     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1923     "Use -style=file to load style configuration from\n"
1924     ".clang-format file located in one of the parent\n"
1925     "directories of the source file (or current\n"
1926     "directory for stdin).\n"
1927     "Use -style=\"{key: value, ...}\" to set specific\n"
1928     "parameters, e.g.:\n"
1929     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1930
1931 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
1932   if (FileName.endswith(".java"))
1933     return FormatStyle::LK_Java;
1934   if (FileName.endswith_lower(".js") || FileName.endswith_lower(".ts"))
1935     return FormatStyle::LK_JavaScript; // JavaScript or TypeScript.
1936   if (FileName.endswith(".m") || FileName.endswith(".mm"))
1937     return FormatStyle::LK_ObjC;
1938   if (FileName.endswith_lower(".proto") ||
1939       FileName.endswith_lower(".protodevel"))
1940     return FormatStyle::LK_Proto;
1941   if (FileName.endswith_lower(".td"))
1942     return FormatStyle::LK_TableGen;
1943   return FormatStyle::LK_Cpp;
1944 }
1945
1946 llvm::Expected<FormatStyle> getStyle(StringRef StyleName, StringRef FileName,
1947                                      StringRef FallbackStyleName,
1948                                      StringRef Code, vfs::FileSystem *FS) {
1949   if (!FS) {
1950     FS = vfs::getRealFileSystem().get();
1951   }
1952   FormatStyle Style = getLLVMStyle();
1953   Style.Language = getLanguageByFileName(FileName);
1954
1955   // This is a very crude detection of whether a header contains ObjC code that
1956   // should be improved over time and probably be done on tokens, not one the
1957   // bare content of the file.
1958   if (Style.Language == FormatStyle::LK_Cpp && FileName.endswith(".h") &&
1959       (Code.contains("\n- (") || Code.contains("\n+ (")))
1960     Style.Language = FormatStyle::LK_ObjC;
1961
1962   FormatStyle FallbackStyle = getNoStyle();
1963   if (!getPredefinedStyle(FallbackStyleName, Style.Language, &FallbackStyle))
1964     return make_string_error("Invalid fallback style \"" + FallbackStyleName);
1965
1966   if (StyleName.startswith("{")) {
1967     // Parse YAML/JSON style from the command line.
1968     if (std::error_code ec = parseConfiguration(StyleName, &Style))
1969       return make_string_error("Error parsing -style: " + ec.message());
1970     return Style;
1971   }
1972
1973   if (!StyleName.equals_lower("file")) {
1974     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
1975       return make_string_error("Invalid value for -style");
1976     return Style;
1977   }
1978
1979   // Look for .clang-format/_clang-format file in the file's parent directories.
1980   SmallString<128> UnsuitableConfigFiles;
1981   SmallString<128> Path(FileName);
1982   if (std::error_code EC = FS->makeAbsolute(Path))
1983     return make_string_error(EC.message());
1984
1985   for (StringRef Directory = Path; !Directory.empty();
1986        Directory = llvm::sys::path::parent_path(Directory)) {
1987
1988     auto Status = FS->status(Directory);
1989     if (!Status ||
1990         Status->getType() != llvm::sys::fs::file_type::directory_file) {
1991       continue;
1992     }
1993
1994     SmallString<128> ConfigFile(Directory);
1995
1996     llvm::sys::path::append(ConfigFile, ".clang-format");
1997     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1998
1999     Status = FS->status(ConfigFile.str());
2000     bool FoundConfigFile =
2001         Status && (Status->getType() == llvm::sys::fs::file_type::regular_file);
2002     if (!FoundConfigFile) {
2003       // Try _clang-format too, since dotfiles are not commonly used on Windows.
2004       ConfigFile = Directory;
2005       llvm::sys::path::append(ConfigFile, "_clang-format");
2006       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2007       Status = FS->status(ConfigFile.str());
2008       FoundConfigFile = Status && (Status->getType() ==
2009                                    llvm::sys::fs::file_type::regular_file);
2010     }
2011
2012     if (FoundConfigFile) {
2013       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2014           FS->getBufferForFile(ConfigFile.str());
2015       if (std::error_code EC = Text.getError())
2016         return make_string_error(EC.message());
2017       if (std::error_code ec =
2018               parseConfiguration(Text.get()->getBuffer(), &Style)) {
2019         if (ec == ParseError::Unsuitable) {
2020           if (!UnsuitableConfigFiles.empty())
2021             UnsuitableConfigFiles.append(", ");
2022           UnsuitableConfigFiles.append(ConfigFile);
2023           continue;
2024         }
2025         return make_string_error("Error reading " + ConfigFile + ": " +
2026                                  ec.message());
2027       }
2028       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
2029       return Style;
2030     }
2031   }
2032   if (!UnsuitableConfigFiles.empty())
2033     return make_string_error("Configuration file(s) do(es) not support " +
2034                              getLanguageName(Style.Language) + ": " +
2035                              UnsuitableConfigFiles);
2036   return FallbackStyle;
2037 }
2038
2039 } // namespace format
2040 } // namespace clang