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