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