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