contrib/llvm/tools/clang/lib/Format/Format.cpp

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