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