contrib/llvm-project/clang/lib/Format/Format.cpp

   1 //===--- Format.cpp - Format C++ code -------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// \file
  10 /// This file implements functions declared in Format.h. This will be
  11 /// split into separate files as we go.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/Format/Format.h"
  16 #include "AffectedRangeManager.h"
  17 #include "BreakableToken.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     IO.enumCase(Value, "CSharp", FormatStyle::LK_CSharp);
  66   }
  67 };
  68
  69 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
  70   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
  71     IO.enumCase(Value, "c++03", FormatStyle::LS_Cpp03);
  72     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03); // Legacy alias
  73     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03); // Legacy alias
  74
  75     IO.enumCase(Value, "c++11", FormatStyle::LS_Cpp11);
  76     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11); // Legacy alias
  77
  78     IO.enumCase(Value, "c++14", FormatStyle::LS_Cpp14);
  79     IO.enumCase(Value, "c++17", FormatStyle::LS_Cpp17);
  80     IO.enumCase(Value, "c++20", FormatStyle::LS_Cpp20);
  81
  82     IO.enumCase(Value, "Latest", FormatStyle::LS_Latest);
  83     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Latest); // Legacy alias
  84     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
  85   }
  86 };
  87
  88 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
  89   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
  90     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
  91     IO.enumCase(Value, "false", FormatStyle::UT_Never);
  92     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
  93     IO.enumCase(Value, "true", FormatStyle::UT_Always);
  94     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
  95     IO.enumCase(Value, "ForContinuationAndIndentation",
  96                 FormatStyle::UT_ForContinuationAndIndentation);
  97     IO.enumCase(Value, "AlignWithSpaces", FormatStyle::UT_AlignWithSpaces);
  98   }
  99 };
 100
 101 template <> struct ScalarEnumerationTraits<FormatStyle::JavaScriptQuoteStyle> {
 102   static void enumeration(IO &IO, FormatStyle::JavaScriptQuoteStyle &Value) {
 103     IO.enumCase(Value, "Leave", FormatStyle::JSQS_Leave);
 104     IO.enumCase(Value, "Single", FormatStyle::JSQS_Single);
 105     IO.enumCase(Value, "Double", FormatStyle::JSQS_Double);
 106   }
 107 };
 108
 109 template <> struct ScalarEnumerationTraits<FormatStyle::ShortBlockStyle> {
 110   static void enumeration(IO &IO, FormatStyle::ShortBlockStyle &Value) {
 111     IO.enumCase(Value, "Never", FormatStyle::SBS_Never);
 112     IO.enumCase(Value, "false", FormatStyle::SBS_Never);
 113     IO.enumCase(Value, "Always", FormatStyle::SBS_Always);
 114     IO.enumCase(Value, "true", FormatStyle::SBS_Always);
 115     IO.enumCase(Value, "Empty", FormatStyle::SBS_Empty);
 116   }
 117 };
 118
 119 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
 120   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
 121     IO.enumCase(Value, "None", FormatStyle::SFS_None);
 122     IO.enumCase(Value, "false", FormatStyle::SFS_None);
 123     IO.enumCase(Value, "All", FormatStyle::SFS_All);
 124     IO.enumCase(Value, "true", FormatStyle::SFS_All);
 125     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
 126     IO.enumCase(Value, "InlineOnly", FormatStyle::SFS_InlineOnly);
 127     IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
 128   }
 129 };
 130
 131 template <> struct ScalarEnumerationTraits<FormatStyle::ShortIfStyle> {
 132   static void enumeration(IO &IO, FormatStyle::ShortIfStyle &Value) {
 133     IO.enumCase(Value, "Never", FormatStyle::SIS_Never);
 134     IO.enumCase(Value, "Always", FormatStyle::SIS_Always);
 135     IO.enumCase(Value, "WithoutElse", FormatStyle::SIS_WithoutElse);
 136
 137     // For backward compatibility.
 138     IO.enumCase(Value, "false", FormatStyle::SIS_Never);
 139     IO.enumCase(Value, "true", FormatStyle::SIS_WithoutElse);
 140   }
 141 };
 142
 143 template <> struct ScalarEnumerationTraits<FormatStyle::ShortLambdaStyle> {
 144   static void enumeration(IO &IO, FormatStyle::ShortLambdaStyle &Value) {
 145     IO.enumCase(Value, "None", FormatStyle::SLS_None);
 146     IO.enumCase(Value, "false", FormatStyle::SLS_None);
 147     IO.enumCase(Value, "Empty", FormatStyle::SLS_Empty);
 148     IO.enumCase(Value, "Inline", FormatStyle::SLS_Inline);
 149     IO.enumCase(Value, "All", FormatStyle::SLS_All);
 150     IO.enumCase(Value, "true", FormatStyle::SLS_All);
 151   }
 152 };
 153
 154 template <> struct ScalarEnumerationTraits<FormatStyle::BinPackStyle> {
 155   static void enumeration(IO &IO, FormatStyle::BinPackStyle &Value) {
 156     IO.enumCase(Value, "Auto", FormatStyle::BPS_Auto);
 157     IO.enumCase(Value, "Always", FormatStyle::BPS_Always);
 158     IO.enumCase(Value, "Never", FormatStyle::BPS_Never);
 159   }
 160 };
 161
 162 template <> struct ScalarEnumerationTraits<FormatStyle::TrailingCommaStyle> {
 163   static void enumeration(IO &IO, FormatStyle::TrailingCommaStyle &Value) {
 164     IO.enumCase(Value, "None", FormatStyle::TCS_None);
 165     IO.enumCase(Value, "Wrapped", FormatStyle::TCS_Wrapped);
 166   }
 167 };
 168
 169 template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
 170   static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
 171     IO.enumCase(Value, "All", FormatStyle::BOS_All);
 172     IO.enumCase(Value, "true", FormatStyle::BOS_All);
 173     IO.enumCase(Value, "None", FormatStyle::BOS_None);
 174     IO.enumCase(Value, "false", FormatStyle::BOS_None);
 175     IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
 176   }
 177 };
 178
 179 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
 180   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
 181     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
 182     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
 183     IO.enumCase(Value, "Mozilla", FormatStyle::BS_Mozilla);
 184     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
 185     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
 186     IO.enumCase(Value, "Whitesmiths", FormatStyle::BS_Whitesmiths);
 187     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
 188     IO.enumCase(Value, "WebKit", FormatStyle::BS_WebKit);
 189     IO.enumCase(Value, "Custom", FormatStyle::BS_Custom);
 190   }
 191 };
 192
 193 template <>
 194 struct ScalarEnumerationTraits<
 195     FormatStyle::BraceWrappingAfterControlStatementStyle> {
 196   static void
 197   enumeration(IO &IO,
 198               FormatStyle::BraceWrappingAfterControlStatementStyle &Value) {
 199     IO.enumCase(Value, "Never", FormatStyle::BWACS_Never);
 200     IO.enumCase(Value, "MultiLine", FormatStyle::BWACS_MultiLine);
 201     IO.enumCase(Value, "Always", FormatStyle::BWACS_Always);
 202
 203     // For backward compatibility.
 204     IO.enumCase(Value, "false", FormatStyle::BWACS_Never);
 205     IO.enumCase(Value, "true", FormatStyle::BWACS_Always);
 206   }
 207 };
 208
 209 template <>
 210 struct ScalarEnumerationTraits<FormatStyle::BreakConstructorInitializersStyle> {
 211   static void
 212   enumeration(IO &IO, FormatStyle::BreakConstructorInitializersStyle &Value) {
 213     IO.enumCase(Value, "BeforeColon", FormatStyle::BCIS_BeforeColon);
 214     IO.enumCase(Value, "BeforeComma", FormatStyle::BCIS_BeforeComma);
 215     IO.enumCase(Value, "AfterColon", FormatStyle::BCIS_AfterColon);
 216   }
 217 };
 218
 219 template <>
 220 struct ScalarEnumerationTraits<FormatStyle::BreakInheritanceListStyle> {
 221   static void enumeration(IO &IO,
 222                           FormatStyle::BreakInheritanceListStyle &Value) {
 223     IO.enumCase(Value, "BeforeColon", FormatStyle::BILS_BeforeColon);
 224     IO.enumCase(Value, "BeforeComma", FormatStyle::BILS_BeforeComma);
 225     IO.enumCase(Value, "AfterColon", FormatStyle::BILS_AfterColon);
 226   }
 227 };
 228
 229 template <>
 230 struct ScalarEnumerationTraits<FormatStyle::PPDirectiveIndentStyle> {
 231   static void enumeration(IO &IO, FormatStyle::PPDirectiveIndentStyle &Value) {
 232     IO.enumCase(Value, "None", FormatStyle::PPDIS_None);
 233     IO.enumCase(Value, "AfterHash", FormatStyle::PPDIS_AfterHash);
 234     IO.enumCase(Value, "BeforeHash", FormatStyle::PPDIS_BeforeHash);
 235   }
 236 };
 237
 238 template <>
 239 struct ScalarEnumerationTraits<FormatStyle::IndentExternBlockStyle> {
 240   static void enumeration(IO &IO, FormatStyle::IndentExternBlockStyle &Value) {
 241     IO.enumCase(Value, "AfterExternBlock", FormatStyle::IEBS_AfterExternBlock);
 242     IO.enumCase(Value, "Indent", FormatStyle::IEBS_Indent);
 243     IO.enumCase(Value, "NoIndent", FormatStyle::IEBS_NoIndent);
 244     IO.enumCase(Value, "true", FormatStyle::IEBS_Indent);
 245     IO.enumCase(Value, "false", FormatStyle::IEBS_NoIndent);
 246   }
 247 };
 248
 249 template <>
 250 struct ScalarEnumerationTraits<FormatStyle::ReturnTypeBreakingStyle> {
 251   static void enumeration(IO &IO, FormatStyle::ReturnTypeBreakingStyle &Value) {
 252     IO.enumCase(Value, "None", FormatStyle::RTBS_None);
 253     IO.enumCase(Value, "All", FormatStyle::RTBS_All);
 254     IO.enumCase(Value, "TopLevel", FormatStyle::RTBS_TopLevel);
 255     IO.enumCase(Value, "TopLevelDefinitions",
 256                 FormatStyle::RTBS_TopLevelDefinitions);
 257     IO.enumCase(Value, "AllDefinitions", FormatStyle::RTBS_AllDefinitions);
 258   }
 259 };
 260
 261 template <>
 262 struct ScalarEnumerationTraits<FormatStyle::BreakTemplateDeclarationsStyle> {
 263   static void enumeration(IO &IO,
 264                           FormatStyle::BreakTemplateDeclarationsStyle &Value) {
 265     IO.enumCase(Value, "No", FormatStyle::BTDS_No);
 266     IO.enumCase(Value, "MultiLine", FormatStyle::BTDS_MultiLine);
 267     IO.enumCase(Value, "Yes", FormatStyle::BTDS_Yes);
 268
 269     // For backward compatibility.
 270     IO.enumCase(Value, "false", FormatStyle::BTDS_MultiLine);
 271     IO.enumCase(Value, "true", FormatStyle::BTDS_Yes);
 272   }
 273 };
 274
 275 template <>
 276 struct ScalarEnumerationTraits<FormatStyle::DefinitionReturnTypeBreakingStyle> {
 277   static void
 278   enumeration(IO &IO, FormatStyle::DefinitionReturnTypeBreakingStyle &Value) {
 279     IO.enumCase(Value, "None", FormatStyle::DRTBS_None);
 280     IO.enumCase(Value, "All", FormatStyle::DRTBS_All);
 281     IO.enumCase(Value, "TopLevel", FormatStyle::DRTBS_TopLevel);
 282
 283     // For backward compatibility.
 284     IO.enumCase(Value, "false", FormatStyle::DRTBS_None);
 285     IO.enumCase(Value, "true", FormatStyle::DRTBS_All);
 286   }
 287 };
 288
 289 template <>
 290 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
 291   static void enumeration(IO &IO,
 292                           FormatStyle::NamespaceIndentationKind &Value) {
 293     IO.enumCase(Value, "None", FormatStyle::NI_None);
 294     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
 295     IO.enumCase(Value, "All", FormatStyle::NI_All);
 296   }
 297 };
 298
 299 template <> struct ScalarEnumerationTraits<FormatStyle::BracketAlignmentStyle> {
 300   static void enumeration(IO &IO, FormatStyle::BracketAlignmentStyle &Value) {
 301     IO.enumCase(Value, "Align", FormatStyle::BAS_Align);
 302     IO.enumCase(Value, "DontAlign", FormatStyle::BAS_DontAlign);
 303     IO.enumCase(Value, "AlwaysBreak", FormatStyle::BAS_AlwaysBreak);
 304
 305     // For backward compatibility.
 306     IO.enumCase(Value, "true", FormatStyle::BAS_Align);
 307     IO.enumCase(Value, "false", FormatStyle::BAS_DontAlign);
 308   }
 309 };
 310
 311 template <>
 312 struct ScalarEnumerationTraits<FormatStyle::EscapedNewlineAlignmentStyle> {
 313   static void enumeration(IO &IO,
 314                           FormatStyle::EscapedNewlineAlignmentStyle &Value) {
 315     IO.enumCase(Value, "DontAlign", FormatStyle::ENAS_DontAlign);
 316     IO.enumCase(Value, "Left", FormatStyle::ENAS_Left);
 317     IO.enumCase(Value, "Right", FormatStyle::ENAS_Right);
 318
 319     // For backward compatibility.
 320     IO.enumCase(Value, "true", FormatStyle::ENAS_Left);
 321     IO.enumCase(Value, "false", FormatStyle::ENAS_Right);
 322   }
 323 };
 324
 325 template <> struct ScalarEnumerationTraits<FormatStyle::OperandAlignmentStyle> {
 326   static void enumeration(IO &IO, FormatStyle::OperandAlignmentStyle &Value) {
 327     IO.enumCase(Value, "DontAlign", FormatStyle::OAS_DontAlign);
 328     IO.enumCase(Value, "Align", FormatStyle::OAS_Align);
 329     IO.enumCase(Value, "AlignAfterOperator",
 330                 FormatStyle::OAS_AlignAfterOperator);
 331
 332     // For backward compatibility.
 333     IO.enumCase(Value, "true", FormatStyle::OAS_Align);
 334     IO.enumCase(Value, "false", FormatStyle::OAS_DontAlign);
 335   }
 336 };
 337
 338 template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
 339   static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
 340     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
 341     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
 342     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
 343
 344     // For backward compatibility.
 345     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
 346     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
 347   }
 348 };
 349
 350 template <>
 351 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
 352   static void enumeration(IO &IO,
 353                           FormatStyle::SpaceBeforeParensOptions &Value) {
 354     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
 355     IO.enumCase(Value, "ControlStatements",
 356                 FormatStyle::SBPO_ControlStatements);
 357     IO.enumCase(Value, "ControlStatementsExceptForEachMacros",
 358                 FormatStyle::SBPO_ControlStatementsExceptForEachMacros);
 359     IO.enumCase(Value, "NonEmptyParentheses",
 360                 FormatStyle::SBPO_NonEmptyParentheses);
 361     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
 362
 363     // For backward compatibility.
 364     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
 365     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
 366   }
 367 };
 368
 369 template <> struct MappingTraits<FormatStyle> {
 370   static void mapping(IO &IO, FormatStyle &Style) {
 371     // When reading, read the language first, we need it for getPredefinedStyle.
 372     IO.mapOptional("Language", Style.Language);
 373
 374     if (IO.outputting()) {
 375       StringRef StylesArray[] = {"LLVM",   "Google", "Chromium", "Mozilla",
 376                                  "WebKit", "GNU",    "Microsoft"};
 377       ArrayRef<StringRef> Styles(StylesArray);
 378       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
 379         StringRef StyleName(Styles[i]);
 380         FormatStyle PredefinedStyle;
 381         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
 382             Style == PredefinedStyle) {
 383           IO.mapOptional("# BasedOnStyle", StyleName);
 384           break;
 385         }
 386       }
 387     } else {
 388       StringRef BasedOnStyle;
 389       IO.mapOptional("BasedOnStyle", BasedOnStyle);
 390       if (!BasedOnStyle.empty()) {
 391         FormatStyle::LanguageKind OldLanguage = Style.Language;
 392         FormatStyle::LanguageKind Language =
 393             ((FormatStyle *)IO.getContext())->Language;
 394         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
 395           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
 396           return;
 397         }
 398         Style.Language = OldLanguage;
 399       }
 400     }
 401
 402     // For backward compatibility.
 403     if (!IO.outputting()) {
 404       IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlines);
 405       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
 406       IO.mapOptional("IndentFunctionDeclarationAfterType",
 407                      Style.IndentWrappedFunctionNames);
 408       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
 409       IO.mapOptional("SpaceAfterControlStatementKeyword",
 410                      Style.SpaceBeforeParens);
 411     }
 412
 413     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
 414     IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
 415     IO.mapOptional("AlignConsecutiveMacros", Style.AlignConsecutiveMacros);
 416     IO.mapOptional("AlignConsecutiveAssignments",
 417                    Style.AlignConsecutiveAssignments);
 418     IO.mapOptional("AlignConsecutiveBitFields",
 419                    Style.AlignConsecutiveBitFields);
 420     IO.mapOptional("AlignConsecutiveDeclarations",
 421                    Style.AlignConsecutiveDeclarations);
 422     IO.mapOptional("AlignEscapedNewlines", Style.AlignEscapedNewlines);
 423     IO.mapOptional("AlignOperands", Style.AlignOperands);
 424     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
 425     IO.mapOptional("AllowAllArgumentsOnNextLine",
 426                    Style.AllowAllArgumentsOnNextLine);
 427     IO.mapOptional("AllowAllConstructorInitializersOnNextLine",
 428                    Style.AllowAllConstructorInitializersOnNextLine);
 429     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
 430                    Style.AllowAllParametersOfDeclarationOnNextLine);
 431     IO.mapOptional("AllowShortEnumsOnASingleLine",
 432                    Style.AllowShortEnumsOnASingleLine);
 433     IO.mapOptional("AllowShortBlocksOnASingleLine",
 434                    Style.AllowShortBlocksOnASingleLine);
 435     IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
 436                    Style.AllowShortCaseLabelsOnASingleLine);
 437     IO.mapOptional("AllowShortFunctionsOnASingleLine",
 438                    Style.AllowShortFunctionsOnASingleLine);
 439     IO.mapOptional("AllowShortLambdasOnASingleLine",
 440                    Style.AllowShortLambdasOnASingleLine);
 441     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
 442                    Style.AllowShortIfStatementsOnASingleLine);
 443     IO.mapOptional("AllowShortLoopsOnASingleLine",
 444                    Style.AllowShortLoopsOnASingleLine);
 445     IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
 446                    Style.AlwaysBreakAfterDefinitionReturnType);
 447     IO.mapOptional("AlwaysBreakAfterReturnType",
 448                    Style.AlwaysBreakAfterReturnType);
 449
 450     // If AlwaysBreakAfterDefinitionReturnType was specified but
 451     // AlwaysBreakAfterReturnType was not, initialize the latter from the
 452     // former for backwards compatibility.
 453     if (Style.AlwaysBreakAfterDefinitionReturnType != FormatStyle::DRTBS_None &&
 454         Style.AlwaysBreakAfterReturnType == FormatStyle::RTBS_None) {
 455       if (Style.AlwaysBreakAfterDefinitionReturnType == FormatStyle::DRTBS_All)
 456         Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
 457       else if (Style.AlwaysBreakAfterDefinitionReturnType ==
 458                FormatStyle::DRTBS_TopLevel)
 459         Style.AlwaysBreakAfterReturnType =
 460             FormatStyle::RTBS_TopLevelDefinitions;
 461     }
 462
 463     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
 464                    Style.AlwaysBreakBeforeMultilineStrings);
 465     IO.mapOptional("AlwaysBreakTemplateDeclarations",
 466                    Style.AlwaysBreakTemplateDeclarations);
 467     IO.mapOptional("BinPackArguments", Style.BinPackArguments);
 468     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
 469     IO.mapOptional("BraceWrapping", Style.BraceWrapping);
 470     IO.mapOptional("BreakBeforeBinaryOperators",
 471                    Style.BreakBeforeBinaryOperators);
 472     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
 473
 474     bool BreakBeforeInheritanceComma = false;
 475     IO.mapOptional("BreakBeforeInheritanceComma", BreakBeforeInheritanceComma);
 476     IO.mapOptional("BreakInheritanceList", Style.BreakInheritanceList);
 477     // If BreakBeforeInheritanceComma was specified but
 478     // BreakInheritance was not, initialize the latter from the
 479     // former for backwards compatibility.
 480     if (BreakBeforeInheritanceComma &&
 481         Style.BreakInheritanceList == FormatStyle::BILS_BeforeColon)
 482       Style.BreakInheritanceList = FormatStyle::BILS_BeforeComma;
 483
 484     IO.mapOptional("BreakBeforeTernaryOperators",
 485                    Style.BreakBeforeTernaryOperators);
 486
 487     bool BreakConstructorInitializersBeforeComma = false;
 488     IO.mapOptional("BreakConstructorInitializersBeforeComma",
 489                    BreakConstructorInitializersBeforeComma);
 490     IO.mapOptional("BreakConstructorInitializers",
 491                    Style.BreakConstructorInitializers);
 492     // If BreakConstructorInitializersBeforeComma was specified but
 493     // BreakConstructorInitializers was not, initialize the latter from the
 494     // former for backwards compatibility.
 495     if (BreakConstructorInitializersBeforeComma &&
 496         Style.BreakConstructorInitializers == FormatStyle::BCIS_BeforeColon)
 497       Style.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
 498
 499     IO.mapOptional("BreakAfterJavaFieldAnnotations",
 500                    Style.BreakAfterJavaFieldAnnotations);
 501     IO.mapOptional("BreakStringLiterals", Style.BreakStringLiterals);
 502     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
 503     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
 504     IO.mapOptional("CompactNamespaces", Style.CompactNamespaces);
 505     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
 506                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
 507     IO.mapOptional("ConstructorInitializerIndentWidth",
 508                    Style.ConstructorInitializerIndentWidth);
 509     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
 510     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
 511     IO.mapOptional("DeriveLineEnding", Style.DeriveLineEnding);
 512     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
 513     IO.mapOptional("DisableFormat", Style.DisableFormat);
 514     IO.mapOptional("ExperimentalAutoDetectBinPacking",
 515                    Style.ExperimentalAutoDetectBinPacking);
 516     IO.mapOptional("FixNamespaceComments", Style.FixNamespaceComments);
 517     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
 518     IO.mapOptional("IncludeBlocks", Style.IncludeStyle.IncludeBlocks);
 519     IO.mapOptional("IncludeCategories", Style.IncludeStyle.IncludeCategories);
 520     IO.mapOptional("IncludeIsMainRegex", Style.IncludeStyle.IncludeIsMainRegex);
 521     IO.mapOptional("IncludeIsMainSourceRegex",
 522                    Style.IncludeStyle.IncludeIsMainSourceRegex);
 523     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
 524     IO.mapOptional("IndentCaseBlocks", Style.IndentCaseBlocks);
 525     IO.mapOptional("IndentGotoLabels", Style.IndentGotoLabels);
 526     IO.mapOptional("IndentPPDirectives", Style.IndentPPDirectives);
 527     IO.mapOptional("IndentExternBlock", Style.IndentExternBlock);
 528     IO.mapOptional("IndentWidth", Style.IndentWidth);
 529     IO.mapOptional("IndentWrappedFunctionNames",
 530                    Style.IndentWrappedFunctionNames);
 531     IO.mapOptional("InsertTrailingCommas", Style.InsertTrailingCommas);
 532     IO.mapOptional("JavaImportGroups", Style.JavaImportGroups);
 533     IO.mapOptional("JavaScriptQuotes", Style.JavaScriptQuotes);
 534     IO.mapOptional("JavaScriptWrapImports", Style.JavaScriptWrapImports);
 535     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
 536                    Style.KeepEmptyLinesAtTheStartOfBlocks);
 537     IO.mapOptional("MacroBlockBegin", Style.MacroBlockBegin);
 538     IO.mapOptional("MacroBlockEnd", Style.MacroBlockEnd);
 539     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
 540     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
 541     IO.mapOptional("NamespaceMacros", Style.NamespaceMacros);
 542     IO.mapOptional("ObjCBinPackProtocolList", Style.ObjCBinPackProtocolList);
 543     IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
 544     IO.mapOptional("ObjCBreakBeforeNestedBlockParam",
 545                    Style.ObjCBreakBeforeNestedBlockParam);
 546     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
 547     IO.mapOptional("ObjCSpaceBeforeProtocolList",
 548                    Style.ObjCSpaceBeforeProtocolList);
 549     IO.mapOptional("PenaltyBreakAssignment", Style.PenaltyBreakAssignment);
 550     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
 551                    Style.PenaltyBreakBeforeFirstCallParameter);
 552     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
 553     IO.mapOptional("PenaltyBreakFirstLessLess",
 554                    Style.PenaltyBreakFirstLessLess);
 555     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
 556     IO.mapOptional("PenaltyBreakTemplateDeclaration",
 557                    Style.PenaltyBreakTemplateDeclaration);
 558     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
 559     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
 560                    Style.PenaltyReturnTypeOnItsOwnLine);
 561     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
 562     IO.mapOptional("RawStringFormats", Style.RawStringFormats);
 563     IO.mapOptional("ReflowComments", Style.ReflowComments);
 564     IO.mapOptional("SortIncludes", Style.SortIncludes);
 565     IO.mapOptional("SortUsingDeclarations", Style.SortUsingDeclarations);
 566     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
 567     IO.mapOptional("SpaceAfterLogicalNot", Style.SpaceAfterLogicalNot);
 568     IO.mapOptional("SpaceAfterTemplateKeyword",
 569                    Style.SpaceAfterTemplateKeyword);
 570     IO.mapOptional("SpaceBeforeAssignmentOperators",
 571                    Style.SpaceBeforeAssignmentOperators);
 572     IO.mapOptional("SpaceBeforeCpp11BracedList",
 573                    Style.SpaceBeforeCpp11BracedList);
 574     IO.mapOptional("SpaceBeforeCtorInitializerColon",
 575                    Style.SpaceBeforeCtorInitializerColon);
 576     IO.mapOptional("SpaceBeforeInheritanceColon",
 577                    Style.SpaceBeforeInheritanceColon);
 578     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
 579     IO.mapOptional("SpaceBeforeRangeBasedForLoopColon",
 580                    Style.SpaceBeforeRangeBasedForLoopColon);
 581     IO.mapOptional("SpaceInEmptyBlock", Style.SpaceInEmptyBlock);
 582     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
 583     IO.mapOptional("SpacesBeforeTrailingComments",
 584                    Style.SpacesBeforeTrailingComments);
 585     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
 586     IO.mapOptional("SpacesInConditionalStatement",
 587                    Style.SpacesInConditionalStatement);
 588     IO.mapOptional("SpacesInContainerLiterals",
 589                    Style.SpacesInContainerLiterals);
 590     IO.mapOptional("SpacesInCStyleCastParentheses",
 591                    Style.SpacesInCStyleCastParentheses);
 592     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
 593     IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
 594     IO.mapOptional("SpaceBeforeSquareBrackets",
 595                    Style.SpaceBeforeSquareBrackets);
 596     IO.mapOptional("Standard", Style.Standard);
 597     IO.mapOptional("StatementMacros", Style.StatementMacros);
 598     IO.mapOptional("TabWidth", Style.TabWidth);
 599     IO.mapOptional("TypenameMacros", Style.TypenameMacros);
 600     IO.mapOptional("UseCRLF", Style.UseCRLF);
 601     IO.mapOptional("UseTab", Style.UseTab);
 602     IO.mapOptional("WhitespaceSensitiveMacros",
 603                    Style.WhitespaceSensitiveMacros);
 604   }
 605 };
 606
 607 template <> struct MappingTraits<FormatStyle::BraceWrappingFlags> {
 608   static void mapping(IO &IO, FormatStyle::BraceWrappingFlags &Wrapping) {
 609     IO.mapOptional("AfterCaseLabel", Wrapping.AfterCaseLabel);
 610     IO.mapOptional("AfterClass", Wrapping.AfterClass);
 611     IO.mapOptional("AfterControlStatement", Wrapping.AfterControlStatement);
 612     IO.mapOptional("AfterEnum", Wrapping.AfterEnum);
 613     IO.mapOptional("AfterFunction", Wrapping.AfterFunction);
 614     IO.mapOptional("AfterNamespace", Wrapping.AfterNamespace);
 615     IO.mapOptional("AfterObjCDeclaration", Wrapping.AfterObjCDeclaration);
 616     IO.mapOptional("AfterStruct", Wrapping.AfterStruct);
 617     IO.mapOptional("AfterUnion", Wrapping.AfterUnion);
 618     IO.mapOptional("AfterExternBlock", Wrapping.AfterExternBlock);
 619     IO.mapOptional("BeforeCatch", Wrapping.BeforeCatch);
 620     IO.mapOptional("BeforeElse", Wrapping.BeforeElse);
 621     IO.mapOptional("BeforeLambdaBody", Wrapping.BeforeLambdaBody);
 622     IO.mapOptional("BeforeWhile", Wrapping.BeforeWhile);
 623     IO.mapOptional("IndentBraces", Wrapping.IndentBraces);
 624     IO.mapOptional("SplitEmptyFunction", Wrapping.SplitEmptyFunction);
 625     IO.mapOptional("SplitEmptyRecord", Wrapping.SplitEmptyRecord);
 626     IO.mapOptional("SplitEmptyNamespace", Wrapping.SplitEmptyNamespace);
 627   }
 628 };
 629
 630 template <> struct MappingTraits<FormatStyle::RawStringFormat> {
 631   static void mapping(IO &IO, FormatStyle::RawStringFormat &Format) {
 632     IO.mapOptional("Language", Format.Language);
 633     IO.mapOptional("Delimiters", Format.Delimiters);
 634     IO.mapOptional("EnclosingFunctions", Format.EnclosingFunctions);
 635     IO.mapOptional("CanonicalDelimiter", Format.CanonicalDelimiter);
 636     IO.mapOptional("BasedOnStyle", Format.BasedOnStyle);
 637   }
 638 };
 639
 640 // Allows to read vector<FormatStyle> while keeping default values.
 641 // IO.getContext() should contain a pointer to the FormatStyle structure, that
 642 // will be used to get default values for missing keys.
 643 // If the first element has no Language specified, it will be treated as the
 644 // default one for the following elements.
 645 template <> struct DocumentListTraits<std::vector<FormatStyle>> {
 646   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
 647     return Seq.size();
 648   }
 649   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
 650                               size_t Index) {
 651     if (Index >= Seq.size()) {
 652       assert(Index == Seq.size());
 653       FormatStyle Template;
 654       if (!Seq.empty() && Seq[0].Language == FormatStyle::LK_None) {
 655         Template = Seq[0];
 656       } else {
 657         Template = *((const FormatStyle *)IO.getContext());
 658         Template.Language = FormatStyle::LK_None;
 659       }
 660       Seq.resize(Index + 1, Template);
 661     }
 662     return Seq[Index];
 663   }
 664 };
 665 } // namespace yaml
 666 } // namespace llvm
 667
 668 namespace clang {
 669 namespace format {
 670
 671 const std::error_category &getParseCategory() {
 672   static const ParseErrorCategory C{};
 673   return C;
 674 }
 675 std::error_code make_error_code(ParseError e) {
 676   return std::error_code(static_cast<int>(e), getParseCategory());
 677 }
 678
 679 inline llvm::Error make_string_error(const llvm::Twine &Message) {
 680   return llvm::make_error<llvm::StringError>(Message,
 681                                              llvm::inconvertibleErrorCode());
 682 }
 683
 684 const char *ParseErrorCategory::name() const noexcept {
 685   return "clang-format.parse_error";
 686 }
 687
 688 std::string ParseErrorCategory::message(int EV) const {
 689   switch (static_cast<ParseError>(EV)) {
 690   case ParseError::Success:
 691     return "Success";
 692   case ParseError::Error:
 693     return "Invalid argument";
 694   case ParseError::Unsuitable:
 695     return "Unsuitable";
 696   case ParseError::BinPackTrailingCommaConflict:
 697     return "trailing comma insertion cannot be used with bin packing";
 698   }
 699   llvm_unreachable("unexpected parse error");
 700 }
 701
 702 static FormatStyle expandPresets(const FormatStyle &Style) {
 703   if (Style.BreakBeforeBraces == FormatStyle::BS_Custom)
 704     return Style;
 705   FormatStyle Expanded = Style;
 706   Expanded.BraceWrapping = {/*AfterCaseLabel=*/false,
 707                             /*AfterClass=*/false,
 708                             /*AfterControlStatement=*/FormatStyle::BWACS_Never,
 709                             /*AfterEnum=*/false,
 710                             /*AfterFunction=*/false,
 711                             /*AfterNamespace=*/false,
 712                             /*AfterObjCDeclaration=*/false,
 713                             /*AfterStruct=*/false,
 714                             /*AfterUnion=*/false,
 715                             /*AfterExternBlock=*/false,
 716                             /*BeforeCatch=*/false,
 717                             /*BeforeElse=*/false,
 718                             /*BeforeLambdaBody=*/false,
 719                             /*BeforeWhile=*/false,
 720                             /*IndentBraces=*/false,
 721                             /*SplitEmptyFunction=*/true,
 722                             /*SplitEmptyRecord=*/true,
 723                             /*SplitEmptyNamespace=*/true};
 724   switch (Style.BreakBeforeBraces) {
 725   case FormatStyle::BS_Linux:
 726     Expanded.BraceWrapping.AfterClass = true;
 727     Expanded.BraceWrapping.AfterFunction = true;
 728     Expanded.BraceWrapping.AfterNamespace = true;
 729     break;
 730   case FormatStyle::BS_Mozilla:
 731     Expanded.BraceWrapping.AfterClass = true;
 732     Expanded.BraceWrapping.AfterEnum = true;
 733     Expanded.BraceWrapping.AfterFunction = true;
 734     Expanded.BraceWrapping.AfterStruct = true;
 735     Expanded.BraceWrapping.AfterUnion = true;
 736     Expanded.BraceWrapping.AfterExternBlock = true;
 737     Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
 738     Expanded.BraceWrapping.SplitEmptyFunction = true;
 739     Expanded.BraceWrapping.SplitEmptyRecord = false;
 740     break;
 741   case FormatStyle::BS_Stroustrup:
 742     Expanded.BraceWrapping.AfterFunction = true;
 743     Expanded.BraceWrapping.BeforeCatch = true;
 744     Expanded.BraceWrapping.BeforeElse = true;
 745     break;
 746   case FormatStyle::BS_Allman:
 747     Expanded.BraceWrapping.AfterCaseLabel = true;
 748     Expanded.BraceWrapping.AfterClass = true;
 749     Expanded.BraceWrapping.AfterControlStatement = FormatStyle::BWACS_Always;
 750     Expanded.BraceWrapping.AfterEnum = true;
 751     Expanded.BraceWrapping.AfterFunction = true;
 752     Expanded.BraceWrapping.AfterNamespace = true;
 753     Expanded.BraceWrapping.AfterObjCDeclaration = true;
 754     Expanded.BraceWrapping.AfterStruct = true;
 755     Expanded.BraceWrapping.AfterUnion = true;
 756     Expanded.BraceWrapping.AfterExternBlock = true;
 757     Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
 758     Expanded.BraceWrapping.BeforeCatch = true;
 759     Expanded.BraceWrapping.BeforeElse = true;
 760     break;
 761   case FormatStyle::BS_Whitesmiths:
 762     Expanded.BraceWrapping.AfterCaseLabel = true;
 763     Expanded.BraceWrapping.AfterClass = true;
 764     Expanded.BraceWrapping.AfterControlStatement = FormatStyle::BWACS_Always;
 765     Expanded.BraceWrapping.AfterEnum = true;
 766     Expanded.BraceWrapping.AfterFunction = true;
 767     Expanded.BraceWrapping.AfterNamespace = true;
 768     Expanded.BraceWrapping.AfterObjCDeclaration = true;
 769     Expanded.BraceWrapping.AfterStruct = true;
 770     Expanded.BraceWrapping.AfterExternBlock = true;
 771     Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
 772     Expanded.BraceWrapping.BeforeCatch = true;
 773     Expanded.BraceWrapping.BeforeElse = true;
 774     Expanded.BraceWrapping.BeforeLambdaBody = true;
 775     break;
 776   case FormatStyle::BS_GNU:
 777     Expanded.BraceWrapping = {
 778         /*AfterCaseLabel=*/true,
 779         /*AfterClass=*/true,
 780         /*AfterControlStatement=*/FormatStyle::BWACS_Always,
 781         /*AfterEnum=*/true,
 782         /*AfterFunction=*/true,
 783         /*AfterNamespace=*/true,
 784         /*AfterObjCDeclaration=*/true,
 785         /*AfterStruct=*/true,
 786         /*AfterUnion=*/true,
 787         /*AfterExternBlock=*/true,
 788         /*BeforeCatch=*/true,
 789         /*BeforeElse=*/true,
 790         /*BeforeLambdaBody=*/false,
 791         /*BeforeWhile=*/true,
 792         /*IndentBraces=*/true,
 793         /*SplitEmptyFunction=*/true,
 794         /*SplitEmptyRecord=*/true,
 795         /*SplitEmptyNamespace=*/true};
 796     Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
 797     break;
 798   case FormatStyle::BS_WebKit:
 799     Expanded.BraceWrapping.AfterFunction = true;
 800     break;
 801   default:
 802     break;
 803   }
 804   return Expanded;
 805 }
 806
 807 FormatStyle getLLVMStyle(FormatStyle::LanguageKind Language) {
 808   FormatStyle LLVMStyle;
 809   LLVMStyle.Language = Language;
 810   LLVMStyle.AccessModifierOffset = -2;
 811   LLVMStyle.AlignEscapedNewlines = FormatStyle::ENAS_Right;
 812   LLVMStyle.AlignAfterOpenBracket = FormatStyle::BAS_Align;
 813   LLVMStyle.AlignOperands = FormatStyle::OAS_Align;
 814   LLVMStyle.AlignTrailingComments = true;
 815   LLVMStyle.AlignConsecutiveAssignments = false;
 816   LLVMStyle.AlignConsecutiveBitFields = false;
 817   LLVMStyle.AlignConsecutiveDeclarations = false;
 818   LLVMStyle.AlignConsecutiveMacros = false;
 819   LLVMStyle.AllowAllArgumentsOnNextLine = true;
 820   LLVMStyle.AllowAllConstructorInitializersOnNextLine = true;
 821   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
 822   LLVMStyle.AllowShortEnumsOnASingleLine = true;
 823   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
 824   LLVMStyle.AllowShortBlocksOnASingleLine = FormatStyle::SBS_Never;
 825   LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
 826   LLVMStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
 827   LLVMStyle.AllowShortLambdasOnASingleLine = FormatStyle::SLS_All;
 828   LLVMStyle.AllowShortLoopsOnASingleLine = false;
 829   LLVMStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
 830   LLVMStyle.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
 831   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
 832   LLVMStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_MultiLine;
 833   LLVMStyle.BinPackArguments = true;
 834   LLVMStyle.BinPackParameters = true;
 835   LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
 836   LLVMStyle.BreakBeforeTernaryOperators = true;
 837   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
 838   LLVMStyle.BraceWrapping = {/*AfterCaseLabel=*/false,
 839                              /*AfterClass=*/false,
 840                              /*AfterControlStatement=*/FormatStyle::BWACS_Never,
 841                              /*AfterEnum=*/false,
 842                              /*AfterFunction=*/false,
 843                              /*AfterNamespace=*/false,
 844                              /*AfterObjCDeclaration=*/false,
 845                              /*AfterStruct=*/false,
 846                              /*AfterUnion=*/false,
 847                              /*AfterExternBlock=*/false,
 848                              /*BeforeCatch=*/false,
 849                              /*BeforeElse=*/false,
 850                              /*BeforeLambdaBody=*/false,
 851                              /*BeforeWhile=*/false,
 852                              /*IndentBraces=*/false,
 853                              /*SplitEmptyFunction=*/true,
 854                              /*SplitEmptyRecord=*/true,
 855                              /*SplitEmptyNamespace=*/true};
 856   LLVMStyle.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
 857   LLVMStyle.BreakAfterJavaFieldAnnotations = false;
 858   LLVMStyle.BreakConstructorInitializers = FormatStyle::BCIS_BeforeColon;
 859   LLVMStyle.BreakInheritanceList = FormatStyle::BILS_BeforeColon;
 860   LLVMStyle.BreakStringLiterals = true;
 861   LLVMStyle.ColumnLimit = 80;
 862   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
 863   LLVMStyle.CompactNamespaces = false;
 864   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
 865   LLVMStyle.ConstructorInitializerIndentWidth = 4;
 866   LLVMStyle.ContinuationIndentWidth = 4;
 867   LLVMStyle.Cpp11BracedListStyle = true;
 868   LLVMStyle.DeriveLineEnding = true;
 869   LLVMStyle.DerivePointerAlignment = false;
 870   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
 871   LLVMStyle.FixNamespaceComments = true;
 872   LLVMStyle.ForEachMacros.push_back("foreach");
 873   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
 874   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
 875   LLVMStyle.IncludeStyle.IncludeCategories = {
 876       {"^\"(llvm|llvm-c|clang|clang-c)/", 2, 0},
 877       {"^(<|\"(gtest|gmock|isl|json)/)", 3, 0},
 878       {".*", 1, 0}};
 879   LLVMStyle.IncludeStyle.IncludeIsMainRegex = "(Test)?$";
 880   LLVMStyle.IncludeStyle.IncludeBlocks = tooling::IncludeStyle::IBS_Preserve;
 881   LLVMStyle.IndentCaseLabels = false;
 882   LLVMStyle.IndentCaseBlocks = false;
 883   LLVMStyle.IndentGotoLabels = true;
 884   LLVMStyle.IndentPPDirectives = FormatStyle::PPDIS_None;
 885   LLVMStyle.IndentWrappedFunctionNames = false;
 886   LLVMStyle.IndentWidth = 2;
 887   LLVMStyle.InsertTrailingCommas = FormatStyle::TCS_None;
 888   LLVMStyle.JavaScriptQuotes = FormatStyle::JSQS_Leave;
 889   LLVMStyle.JavaScriptWrapImports = true;
 890   LLVMStyle.TabWidth = 8;
 891   LLVMStyle.MaxEmptyLinesToKeep = 1;
 892   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
 893   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
 894   LLVMStyle.ObjCBinPackProtocolList = FormatStyle::BPS_Auto;
 895   LLVMStyle.ObjCBlockIndentWidth = 2;
 896   LLVMStyle.ObjCBreakBeforeNestedBlockParam = true;
 897   LLVMStyle.ObjCSpaceAfterProperty = false;
 898   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
 899   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
 900   LLVMStyle.SpacesBeforeTrailingComments = 1;
 901   LLVMStyle.Standard = FormatStyle::LS_Latest;
 902   LLVMStyle.UseCRLF = false;
 903   LLVMStyle.UseTab = FormatStyle::UT_Never;
 904   LLVMStyle.ReflowComments = true;
 905   LLVMStyle.SpacesInParentheses = false;
 906   LLVMStyle.SpacesInSquareBrackets = false;
 907   LLVMStyle.SpaceInEmptyBlock = false;
 908   LLVMStyle.SpaceInEmptyParentheses = false;
 909   LLVMStyle.SpacesInContainerLiterals = true;
 910   LLVMStyle.SpacesInCStyleCastParentheses = false;
 911   LLVMStyle.SpaceAfterCStyleCast = false;
 912   LLVMStyle.SpaceAfterLogicalNot = false;
 913   LLVMStyle.SpaceAfterTemplateKeyword = true;
 914   LLVMStyle.SpaceBeforeCtorInitializerColon = true;
 915   LLVMStyle.SpaceBeforeInheritanceColon = true;
 916   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
 917   LLVMStyle.SpaceBeforeRangeBasedForLoopColon = true;
 918   LLVMStyle.SpaceBeforeAssignmentOperators = true;
 919   LLVMStyle.SpaceBeforeCpp11BracedList = false;
 920   LLVMStyle.SpaceBeforeSquareBrackets = false;
 921   LLVMStyle.SpacesInAngles = false;
 922   LLVMStyle.SpacesInConditionalStatement = false;
 923
 924   LLVMStyle.PenaltyBreakAssignment = prec::Assignment;
 925   LLVMStyle.PenaltyBreakComment = 300;
 926   LLVMStyle.PenaltyBreakFirstLessLess = 120;
 927   LLVMStyle.PenaltyBreakString = 1000;
 928   LLVMStyle.PenaltyExcessCharacter = 1000000;
 929   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
 930   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
 931   LLVMStyle.PenaltyBreakTemplateDeclaration = prec::Relational;
 932
 933   LLVMStyle.DisableFormat = false;
 934   LLVMStyle.SortIncludes = true;
 935   LLVMStyle.SortUsingDeclarations = true;
 936   LLVMStyle.StatementMacros.push_back("Q_UNUSED");
 937   LLVMStyle.StatementMacros.push_back("QT_REQUIRE_VERSION");
 938   LLVMStyle.WhitespaceSensitiveMacros.push_back("STRINGIZE");
 939   LLVMStyle.WhitespaceSensitiveMacros.push_back("PP_STRINGIZE");
 940   LLVMStyle.WhitespaceSensitiveMacros.push_back("BOOST_PP_STRINGIZE");
 941
 942   // Defaults that differ when not C++.
 943   if (Language == FormatStyle::LK_TableGen) {
 944     LLVMStyle.SpacesInContainerLiterals = false;
 945   }
 946
 947   return LLVMStyle;
 948 }
 949
 950 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
 951   if (Language == FormatStyle::LK_TextProto) {
 952     FormatStyle GoogleStyle = getGoogleStyle(FormatStyle::LK_Proto);
 953     GoogleStyle.Language = FormatStyle::LK_TextProto;
 954
 955     return GoogleStyle;
 956   }
 957
 958   FormatStyle GoogleStyle = getLLVMStyle(Language);
 959
 960   GoogleStyle.AccessModifierOffset = -1;
 961   GoogleStyle.AlignEscapedNewlines = FormatStyle::ENAS_Left;
 962   GoogleStyle.AllowShortIfStatementsOnASingleLine =
 963       FormatStyle::SIS_WithoutElse;
 964   GoogleStyle.AllowShortLoopsOnASingleLine = true;
 965   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
 966   GoogleStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_Yes;
 967   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
 968   GoogleStyle.DerivePointerAlignment = true;
 969   GoogleStyle.IncludeStyle.IncludeCategories = {{"^<ext/.*\\.h>", 2, 0},
 970                                                 {"^<.*\\.h>", 1, 0},
 971                                                 {"^<.*", 2, 0},
 972                                                 {".*", 3, 0}};
 973   GoogleStyle.IncludeStyle.IncludeIsMainRegex = "([-_](test|unittest))?$";
 974   GoogleStyle.IncludeStyle.IncludeBlocks = tooling::IncludeStyle::IBS_Regroup;
 975   GoogleStyle.IndentCaseLabels = true;
 976   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
 977   GoogleStyle.ObjCBinPackProtocolList = FormatStyle::BPS_Never;
 978   GoogleStyle.ObjCSpaceAfterProperty = false;
 979   GoogleStyle.ObjCSpaceBeforeProtocolList = true;
 980   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
 981   GoogleStyle.RawStringFormats = {
 982       {
 983           FormatStyle::LK_Cpp,
 984           /*Delimiters=*/
 985           {
 986               "cc",
 987               "CC",
 988               "cpp",
 989               "Cpp",
 990               "CPP",
 991               "c++",
 992               "C++",
 993           },
 994           /*EnclosingFunctionNames=*/
 995           {},
 996           /*CanonicalDelimiter=*/"",
 997           /*BasedOnStyle=*/"google",
 998       },
 999       {
1000           FormatStyle::LK_TextProto,
1001           /*Delimiters=*/
1002           {
1003               "pb",
1004               "PB",
1005               "proto",
1006               "PROTO",
1007           },
1008           /*EnclosingFunctionNames=*/
1009           {
1010               "EqualsProto",
1011               "EquivToProto",
1012               "PARSE_PARTIAL_TEXT_PROTO",
1013               "PARSE_TEST_PROTO",
1014               "PARSE_TEXT_PROTO",
1015               "ParseTextOrDie",
1016               "ParseTextProtoOrDie",
1017               "ParseTestProto",
1018               "ParsePartialTestProto",
1019           },
1020           /*CanonicalDelimiter=*/"",
1021           /*BasedOnStyle=*/"google",
1022       },
1023   };
1024   GoogleStyle.SpacesBeforeTrailingComments = 2;
1025   GoogleStyle.Standard = FormatStyle::LS_Auto;
1026
1027   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
1028   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
1029
1030   if (Language == FormatStyle::LK_Java) {
1031     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
1032     GoogleStyle.AlignOperands = FormatStyle::OAS_DontAlign;
1033     GoogleStyle.AlignTrailingComments = false;
1034     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1035     GoogleStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1036     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1037     GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
1038     GoogleStyle.ColumnLimit = 100;
1039     GoogleStyle.SpaceAfterCStyleCast = true;
1040     GoogleStyle.SpacesBeforeTrailingComments = 1;
1041   } else if (Language == FormatStyle::LK_JavaScript) {
1042     GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_AlwaysBreak;
1043     GoogleStyle.AlignOperands = FormatStyle::OAS_DontAlign;
1044     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1045     // TODO: still under discussion whether to switch to SLS_All.
1046     GoogleStyle.AllowShortLambdasOnASingleLine = FormatStyle::SLS_Empty;
1047     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1048     GoogleStyle.BreakBeforeTernaryOperators = false;
1049     // taze:, triple slash directives (`/// <...`), tslint:, and @see, which is
1050     // commonly followed by overlong URLs.
1051     GoogleStyle.CommentPragmas = "(taze:|^/[ \t]*<|tslint:|@see)";
1052     // TODO: enable once decided, in particular re disabling bin packing.
1053     // https://google.github.io/styleguide/jsguide.html#features-arrays-trailing-comma
1054     // GoogleStyle.InsertTrailingCommas = FormatStyle::TCS_Wrapped;
1055     GoogleStyle.MaxEmptyLinesToKeep = 3;
1056     GoogleStyle.NamespaceIndentation = FormatStyle::NI_All;
1057     GoogleStyle.SpacesInContainerLiterals = false;
1058     GoogleStyle.JavaScriptQuotes = FormatStyle::JSQS_Single;
1059     GoogleStyle.JavaScriptWrapImports = false;
1060   } else if (Language == FormatStyle::LK_Proto) {
1061     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1062     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1063     GoogleStyle.SpacesInContainerLiterals = false;
1064     GoogleStyle.Cpp11BracedListStyle = false;
1065     // This affects protocol buffer options specifications and text protos.
1066     // Text protos are currently mostly formatted inside C++ raw string literals
1067     // and often the current breaking behavior of string literals is not
1068     // beneficial there. Investigate turning this on once proper string reflow
1069     // has been implemented.
1070     GoogleStyle.BreakStringLiterals = false;
1071   } else if (Language == FormatStyle::LK_ObjC) {
1072     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1073     GoogleStyle.ColumnLimit = 100;
1074     // "Regroup" doesn't work well for ObjC yet (main header heuristic,
1075     // relationship between ObjC standard library headers and other heades,
1076     // #imports, etc.)
1077     GoogleStyle.IncludeStyle.IncludeBlocks =
1078         tooling::IncludeStyle::IBS_Preserve;
1079   } else if (Language == FormatStyle::LK_CSharp) {
1080     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1081     GoogleStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1082     GoogleStyle.BreakStringLiterals = false;
1083     GoogleStyle.ColumnLimit = 100;
1084     GoogleStyle.NamespaceIndentation = FormatStyle::NI_All;
1085   }
1086
1087   return GoogleStyle;
1088 }
1089
1090 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
1091   FormatStyle ChromiumStyle = getGoogleStyle(Language);
1092
1093   // Disable include reordering across blocks in Chromium code.
1094   // - clang-format tries to detect that foo.h is the "main" header for
1095   //   foo.cc and foo_unittest.cc via IncludeIsMainRegex. However, Chromium
1096   //   uses many other suffices (_win.cc, _mac.mm, _posix.cc, _browsertest.cc,
1097   //   _private.cc, _impl.cc etc) in different permutations
1098   //   (_win_browsertest.cc) so disable this until IncludeIsMainRegex has a
1099   //   better default for Chromium code.
1100   // - The default for .cc and .mm files is different (r357695) for Google style
1101   //   for the same reason. The plan is to unify this again once the main
1102   //   header detection works for Google's ObjC code, but this hasn't happened
1103   //   yet. Since Chromium has some ObjC code, switching Chromium is blocked
1104   //   on that.
1105   // - Finally, "If include reordering is harmful, put things in different
1106   //   blocks to prevent it" has been a recommendation for a long time that
1107   //   people are used to. We'll need a dev education push to change this to
1108   //   "If include reordering is harmful, put things in a different block and
1109   //   _prepend that with a comment_ to prevent it" before changing behavior.
1110   ChromiumStyle.IncludeStyle.IncludeBlocks =
1111       tooling::IncludeStyle::IBS_Preserve;
1112
1113   if (Language == FormatStyle::LK_Java) {
1114     ChromiumStyle.AllowShortIfStatementsOnASingleLine =
1115         FormatStyle::SIS_WithoutElse;
1116     ChromiumStyle.BreakAfterJavaFieldAnnotations = true;
1117     ChromiumStyle.ContinuationIndentWidth = 8;
1118     ChromiumStyle.IndentWidth = 4;
1119     // See styleguide for import groups:
1120     // https://chromium.googlesource.com/chromium/src/+/master/styleguide/java/java.md#Import-Order
1121     ChromiumStyle.JavaImportGroups = {
1122         "android",
1123         "androidx",
1124         "com",
1125         "dalvik",
1126         "junit",
1127         "org",
1128         "com.google.android.apps.chrome",
1129         "org.chromium",
1130         "java",
1131         "javax",
1132     };
1133     ChromiumStyle.SortIncludes = true;
1134   } else if (Language == FormatStyle::LK_JavaScript) {
1135     ChromiumStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1136     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
1137   } else {
1138     ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
1139     ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
1140     ChromiumStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1141     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
1142     ChromiumStyle.BinPackParameters = false;
1143     ChromiumStyle.DerivePointerAlignment = false;
1144     if (Language == FormatStyle::LK_ObjC)
1145       ChromiumStyle.ColumnLimit = 80;
1146   }
1147   return ChromiumStyle;
1148 }
1149
1150 FormatStyle getMozillaStyle() {
1151   FormatStyle MozillaStyle = getLLVMStyle();
1152   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
1153   MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
1154   MozillaStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_TopLevel;
1155   MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
1156       FormatStyle::DRTBS_TopLevel;
1157   MozillaStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_Yes;
1158   MozillaStyle.BinPackParameters = false;
1159   MozillaStyle.BinPackArguments = false;
1160   MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
1161   MozillaStyle.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
1162   MozillaStyle.BreakInheritanceList = FormatStyle::BILS_BeforeComma;
1163   MozillaStyle.ConstructorInitializerIndentWidth = 2;
1164   MozillaStyle.ContinuationIndentWidth = 2;
1165   MozillaStyle.Cpp11BracedListStyle = false;
1166   MozillaStyle.FixNamespaceComments = false;
1167   MozillaStyle.IndentCaseLabels = true;
1168   MozillaStyle.ObjCSpaceAfterProperty = true;
1169   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
1170   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
1171   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
1172   MozillaStyle.SpaceAfterTemplateKeyword = false;
1173   return MozillaStyle;
1174 }
1175
1176 FormatStyle getWebKitStyle() {
1177   FormatStyle Style = getLLVMStyle();
1178   Style.AccessModifierOffset = -4;
1179   Style.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
1180   Style.AlignOperands = FormatStyle::OAS_DontAlign;
1181   Style.AlignTrailingComments = false;
1182   Style.AllowShortBlocksOnASingleLine = FormatStyle::SBS_Empty;
1183   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
1184   Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
1185   Style.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
1186   Style.Cpp11BracedListStyle = false;
1187   Style.ColumnLimit = 0;
1188   Style.FixNamespaceComments = false;
1189   Style.IndentWidth = 4;
1190   Style.NamespaceIndentation = FormatStyle::NI_Inner;
1191   Style.ObjCBlockIndentWidth = 4;
1192   Style.ObjCSpaceAfterProperty = true;
1193   Style.PointerAlignment = FormatStyle::PAS_Left;
1194   Style.SpaceBeforeCpp11BracedList = true;
1195   Style.SpaceInEmptyBlock = true;
1196   return Style;
1197 }
1198
1199 FormatStyle getGNUStyle() {
1200   FormatStyle Style = getLLVMStyle();
1201   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
1202   Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
1203   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
1204   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
1205   Style.BreakBeforeTernaryOperators = true;
1206   Style.Cpp11BracedListStyle = false;
1207   Style.ColumnLimit = 79;
1208   Style.FixNamespaceComments = false;
1209   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
1210   Style.Standard = FormatStyle::LS_Cpp03;
1211   return Style;
1212 }
1213
1214 FormatStyle getMicrosoftStyle(FormatStyle::LanguageKind Language) {
1215   FormatStyle Style = getLLVMStyle(Language);
1216   Style.ColumnLimit = 120;
1217   Style.TabWidth = 4;
1218   Style.IndentWidth = 4;
1219   Style.UseTab = FormatStyle::UT_Never;
1220   Style.BreakBeforeBraces = FormatStyle::BS_Custom;
1221   Style.BraceWrapping.AfterClass = true;
1222   Style.BraceWrapping.AfterControlStatement = FormatStyle::BWACS_Always;
1223   Style.BraceWrapping.AfterEnum = true;
1224   Style.BraceWrapping.AfterFunction = true;
1225   Style.BraceWrapping.AfterNamespace = true;
1226   Style.BraceWrapping.AfterObjCDeclaration = true;
1227   Style.BraceWrapping.AfterStruct = true;
1228   Style.BraceWrapping.AfterExternBlock = true;
1229   Style.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
1230   Style.BraceWrapping.BeforeCatch = true;
1231   Style.BraceWrapping.BeforeElse = true;
1232   Style.BraceWrapping.BeforeWhile = false;
1233   Style.PenaltyReturnTypeOnItsOwnLine = 1000;
1234   Style.AllowShortEnumsOnASingleLine = false;
1235   Style.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
1236   Style.AllowShortCaseLabelsOnASingleLine = false;
1237   Style.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1238   Style.AllowShortLoopsOnASingleLine = false;
1239   Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
1240   Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
1241   return Style;
1242 }
1243
1244 FormatStyle getNoStyle() {
1245   FormatStyle NoStyle = getLLVMStyle();
1246   NoStyle.DisableFormat = true;
1247   NoStyle.SortIncludes = false;
1248   NoStyle.SortUsingDeclarations = false;
1249   return NoStyle;
1250 }
1251
1252 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
1253                         FormatStyle *Style) {
1254   if (Name.equals_lower("llvm")) {
1255     *Style = getLLVMStyle(Language);
1256   } else if (Name.equals_lower("chromium")) {
1257     *Style = getChromiumStyle(Language);
1258   } else if (Name.equals_lower("mozilla")) {
1259     *Style = getMozillaStyle();
1260   } else if (Name.equals_lower("google")) {
1261     *Style = getGoogleStyle(Language);
1262   } else if (Name.equals_lower("webkit")) {
1263     *Style = getWebKitStyle();
1264   } else if (Name.equals_lower("gnu")) {
1265     *Style = getGNUStyle();
1266   } else if (Name.equals_lower("microsoft")) {
1267     *Style = getMicrosoftStyle(Language);
1268   } else if (Name.equals_lower("none")) {
1269     *Style = getNoStyle();
1270   } else {
1271     return false;
1272   }
1273
1274   Style->Language = Language;
1275   return true;
1276 }
1277
1278 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
1279   assert(Style);
1280   FormatStyle::LanguageKind Language = Style->Language;
1281   assert(Language != FormatStyle::LK_None);
1282   if (Text.trim().empty())
1283     return make_error_code(ParseError::Error);
1284   Style->StyleSet.Clear();
1285   std::vector<FormatStyle> Styles;
1286   llvm::yaml::Input Input(Text);
1287   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
1288   // values for the fields, keys for which are missing from the configuration.
1289   // Mapping also uses the context to get the language to find the correct
1290   // base style.
1291   Input.setContext(Style);
1292   Input >> Styles;
1293   if (Input.error())
1294     return Input.error();
1295
1296   for (unsigned i = 0; i < Styles.size(); ++i) {
1297     // Ensures that only the first configuration can skip the Language option.
1298     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
1299       return make_error_code(ParseError::Error);
1300     // Ensure that each language is configured at most once.
1301     for (unsigned j = 0; j < i; ++j) {
1302       if (Styles[i].Language == Styles[j].Language) {
1303         LLVM_DEBUG(llvm::dbgs()
1304                    << "Duplicate languages in the config file on positions "
1305                    << j << " and " << i << "\n");
1306         return make_error_code(ParseError::Error);
1307       }
1308     }
1309   }
1310   // Look for a suitable configuration starting from the end, so we can
1311   // find the configuration for the specific language first, and the default
1312   // configuration (which can only be at slot 0) after it.
1313   FormatStyle::FormatStyleSet StyleSet;
1314   bool LanguageFound = false;
1315   for (int i = Styles.size() - 1; i >= 0; --i) {
1316     if (Styles[i].Language != FormatStyle::LK_None)
1317       StyleSet.Add(Styles[i]);
1318     if (Styles[i].Language == Language)
1319       LanguageFound = true;
1320   }
1321   if (!LanguageFound) {
1322     if (Styles.empty() || Styles[0].Language != FormatStyle::LK_None)
1323       return make_error_code(ParseError::Unsuitable);
1324     FormatStyle DefaultStyle = Styles[0];
1325     DefaultStyle.Language = Language;
1326     StyleSet.Add(std::move(DefaultStyle));
1327   }
1328   *Style = *StyleSet.Get(Language);
1329   if (Style->InsertTrailingCommas != FormatStyle::TCS_None &&
1330       Style->BinPackArguments) {
1331     // See comment on FormatStyle::TSC_Wrapped.
1332     return make_error_code(ParseError::BinPackTrailingCommaConflict);
1333   }
1334   return make_error_code(ParseError::Success);
1335 }
1336
1337 std::string configurationAsText(const FormatStyle &Style) {
1338   std::string Text;
1339   llvm::raw_string_ostream Stream(Text);
1340   llvm::yaml::Output Output(Stream);
1341   // We use the same mapping method for input and output, so we need a non-const
1342   // reference here.
1343   FormatStyle NonConstStyle = expandPresets(Style);
1344   Output << NonConstStyle;
1345   return Stream.str();
1346 }
1347
1348 llvm::Optional<FormatStyle>
1349 FormatStyle::FormatStyleSet::Get(FormatStyle::LanguageKind Language) const {
1350   if (!Styles)
1351     return None;
1352   auto It = Styles->find(Language);
1353   if (It == Styles->end())
1354     return None;
1355   FormatStyle Style = It->second;
1356   Style.StyleSet = *this;
1357   return Style;
1358 }
1359
1360 void FormatStyle::FormatStyleSet::Add(FormatStyle Style) {
1361   assert(Style.Language != LK_None &&
1362          "Cannot add a style for LK_None to a StyleSet");
1363   assert(
1364       !Style.StyleSet.Styles &&
1365       "Cannot add a style associated with an existing StyleSet to a StyleSet");
1366   if (!Styles)
1367     Styles = std::make_shared<MapType>();
1368   (*Styles)[Style.Language] = std::move(Style);
1369 }
1370
1371 void FormatStyle::FormatStyleSet::Clear() { Styles.reset(); }
1372
1373 llvm::Optional<FormatStyle>
1374 FormatStyle::GetLanguageStyle(FormatStyle::LanguageKind Language) const {
1375   return StyleSet.Get(Language);
1376 }
1377
1378 namespace {
1379
1380 class JavaScriptRequoter : public TokenAnalyzer {
1381 public:
1382   JavaScriptRequoter(const Environment &Env, const FormatStyle &Style)
1383       : TokenAnalyzer(Env, Style) {}
1384
1385   std::pair<tooling::Replacements, unsigned>
1386   analyze(TokenAnnotator &Annotator,
1387           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1388           FormatTokenLexer &Tokens) override {
1389     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1390     tooling::Replacements Result;
1391     requoteJSStringLiteral(AnnotatedLines, Result);
1392     return {Result, 0};
1393   }
1394
1395 private:
1396   // Replaces double/single-quoted string literal as appropriate, re-escaping
1397   // the contents in the process.
1398   void requoteJSStringLiteral(SmallVectorImpl<AnnotatedLine *> &Lines,
1399                               tooling::Replacements &Result) {
1400     for (AnnotatedLine *Line : Lines) {
1401       requoteJSStringLiteral(Line->Children, Result);
1402       if (!Line->Affected)
1403         continue;
1404       for (FormatToken *FormatTok = Line->First; FormatTok;
1405            FormatTok = FormatTok->Next) {
1406         StringRef Input = FormatTok->TokenText;
1407         if (FormatTok->Finalized || !FormatTok->isStringLiteral() ||
1408             // NB: testing for not starting with a double quote to avoid
1409             // breaking `template strings`.
1410             (Style.JavaScriptQuotes == FormatStyle::JSQS_Single &&
1411              !Input.startswith("\"")) ||
1412             (Style.JavaScriptQuotes == FormatStyle::JSQS_Double &&
1413              !Input.startswith("\'")))
1414           continue;
1415
1416         // Change start and end quote.
1417         bool IsSingle = Style.JavaScriptQuotes == FormatStyle::JSQS_Single;
1418         SourceLocation Start = FormatTok->Tok.getLocation();
1419         auto Replace = [&](SourceLocation Start, unsigned Length,
1420                            StringRef ReplacementText) {
1421           auto Err = Result.add(tooling::Replacement(
1422               Env.getSourceManager(), Start, Length, ReplacementText));
1423           // FIXME: handle error. For now, print error message and skip the
1424           // replacement for release version.
1425           if (Err) {
1426             llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1427             assert(false);
1428           }
1429         };
1430         Replace(Start, 1, IsSingle ? "'" : "\"");
1431         Replace(FormatTok->Tok.getEndLoc().getLocWithOffset(-1), 1,
1432                 IsSingle ? "'" : "\"");
1433
1434         // Escape internal quotes.
1435         bool Escaped = false;
1436         for (size_t i = 1; i < Input.size() - 1; i++) {
1437           switch (Input[i]) {
1438           case '\\':
1439             if (!Escaped && i + 1 < Input.size() &&
1440                 ((IsSingle && Input[i + 1] == '"') ||
1441                  (!IsSingle && Input[i + 1] == '\''))) {
1442               // Remove this \, it's escaping a " or ' that no longer needs
1443               // escaping
1444               Replace(Start.getLocWithOffset(i), 1, "");
1445               continue;
1446             }
1447             Escaped = !Escaped;
1448             break;
1449           case '\"':
1450           case '\'':
1451             if (!Escaped && IsSingle == (Input[i] == '\'')) {
1452               // Escape the quote.
1453               Replace(Start.getLocWithOffset(i), 0, "\\");
1454             }
1455             Escaped = false;
1456             break;
1457           default:
1458             Escaped = false;
1459             break;
1460           }
1461         }
1462       }
1463     }
1464   }
1465 };
1466
1467 class Formatter : public TokenAnalyzer {
1468 public:
1469   Formatter(const Environment &Env, const FormatStyle &Style,
1470             FormattingAttemptStatus *Status)
1471       : TokenAnalyzer(Env, Style), Status(Status) {}
1472
1473   std::pair<tooling::Replacements, unsigned>
1474   analyze(TokenAnnotator &Annotator,
1475           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1476           FormatTokenLexer &Tokens) override {
1477     tooling::Replacements Result;
1478     deriveLocalStyle(AnnotatedLines);
1479     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1480     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1481       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1482     }
1483     Annotator.setCommentLineLevels(AnnotatedLines);
1484
1485     WhitespaceManager Whitespaces(
1486         Env.getSourceManager(), Style,
1487         Style.DeriveLineEnding
1488             ? inputUsesCRLF(
1489                   Env.getSourceManager().getBufferData(Env.getFileID()),
1490                   Style.UseCRLF)
1491             : Style.UseCRLF);
1492     ContinuationIndenter Indenter(Style, Tokens.getKeywords(),
1493                                   Env.getSourceManager(), Whitespaces, Encoding,
1494                                   BinPackInconclusiveFunctions);
1495     unsigned Penalty =
1496         UnwrappedLineFormatter(&Indenter, &Whitespaces, Style,
1497                                Tokens.getKeywords(), Env.getSourceManager(),
1498                                Status)
1499             .format(AnnotatedLines, /*DryRun=*/false,
1500                     /*AdditionalIndent=*/0,
1501                     /*FixBadIndentation=*/false,
1502                     /*FirstStartColumn=*/Env.getFirstStartColumn(),
1503                     /*NextStartColumn=*/Env.getNextStartColumn(),
1504                     /*LastStartColumn=*/Env.getLastStartColumn());
1505     for (const auto &R : Whitespaces.generateReplacements())
1506       if (Result.add(R))
1507         return std::make_pair(Result, 0);
1508     return std::make_pair(Result, Penalty);
1509   }
1510
1511 private:
1512   static bool inputUsesCRLF(StringRef Text, bool DefaultToCRLF) {
1513     size_t LF = Text.count('\n');
1514     size_t CR = Text.count('\r') * 2;
1515     return LF == CR ? DefaultToCRLF : CR > LF;
1516   }
1517
1518   bool
1519   hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1520     for (const AnnotatedLine *Line : Lines) {
1521       if (hasCpp03IncompatibleFormat(Line->Children))
1522         return true;
1523       for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
1524         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1525           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
1526             return true;
1527           if (Tok->is(TT_TemplateCloser) &&
1528               Tok->Previous->is(TT_TemplateCloser))
1529             return true;
1530         }
1531       }
1532     }
1533     return false;
1534   }
1535
1536   int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1537     int AlignmentDiff = 0;
1538     for (const AnnotatedLine *Line : Lines) {
1539       AlignmentDiff += countVariableAlignments(Line->Children);
1540       for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
1541         if (!Tok->is(TT_PointerOrReference))
1542           continue;
1543         bool SpaceBefore =
1544             Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1545         bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
1546                           Tok->Next->WhitespaceRange.getEnd();
1547         if (SpaceBefore && !SpaceAfter)
1548           ++AlignmentDiff;
1549         if (!SpaceBefore && SpaceAfter)
1550           --AlignmentDiff;
1551       }
1552     }
1553     return AlignmentDiff;
1554   }
1555
1556   void
1557   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1558     bool HasBinPackedFunction = false;
1559     bool HasOnePerLineFunction = false;
1560     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1561       if (!AnnotatedLines[i]->First->Next)
1562         continue;
1563       FormatToken *Tok = AnnotatedLines[i]->First->Next;
1564       while (Tok->Next) {
1565         if (Tok->PackingKind == PPK_BinPacked)
1566           HasBinPackedFunction = true;
1567         if (Tok->PackingKind == PPK_OnePerLine)
1568           HasOnePerLineFunction = true;
1569
1570         Tok = Tok->Next;
1571       }
1572     }
1573     if (Style.DerivePointerAlignment)
1574       Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
1575                                    ? FormatStyle::PAS_Left
1576                                    : FormatStyle::PAS_Right;
1577     if (Style.Standard == FormatStyle::LS_Auto)
1578       Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
1579                            ? FormatStyle::LS_Latest
1580                            : FormatStyle::LS_Cpp03;
1581     BinPackInconclusiveFunctions =
1582         HasBinPackedFunction || !HasOnePerLineFunction;
1583   }
1584
1585   bool BinPackInconclusiveFunctions;
1586   FormattingAttemptStatus *Status;
1587 };
1588
1589 /// TrailingCommaInserter inserts trailing commas into container literals.
1590 /// E.g.:
1591 ///     const x = [
1592 ///       1,
1593 ///     ];
1594 /// TrailingCommaInserter runs after formatting. To avoid causing a required
1595 /// reformatting (and thus reflow), it never inserts a comma that'd exceed the
1596 /// ColumnLimit.
1597 ///
1598 /// Because trailing commas disable binpacking of arrays, TrailingCommaInserter
1599 /// is conceptually incompatible with bin packing.
1600 class TrailingCommaInserter : public TokenAnalyzer {
1601 public:
1602   TrailingCommaInserter(const Environment &Env, const FormatStyle &Style)
1603       : TokenAnalyzer(Env, Style) {}
1604
1605   std::pair<tooling::Replacements, unsigned>
1606   analyze(TokenAnnotator &Annotator,
1607           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1608           FormatTokenLexer &Tokens) override {
1609     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1610     tooling::Replacements Result;
1611     insertTrailingCommas(AnnotatedLines, Result);
1612     return {Result, 0};
1613   }
1614
1615 private:
1616   /// Inserts trailing commas in [] and {} initializers if they wrap over
1617   /// multiple lines.
1618   void insertTrailingCommas(SmallVectorImpl<AnnotatedLine *> &Lines,
1619                             tooling::Replacements &Result) {
1620     for (AnnotatedLine *Line : Lines) {
1621       insertTrailingCommas(Line->Children, Result);
1622       if (!Line->Affected)
1623         continue;
1624       for (FormatToken *FormatTok = Line->First; FormatTok;
1625            FormatTok = FormatTok->Next) {
1626         if (FormatTok->NewlinesBefore == 0)
1627           continue;
1628         FormatToken *Matching = FormatTok->MatchingParen;
1629         if (!Matching || !FormatTok->getPreviousNonComment())
1630           continue;
1631         if (!(FormatTok->is(tok::r_square) &&
1632               Matching->is(TT_ArrayInitializerLSquare)) &&
1633             !(FormatTok->is(tok::r_brace) && Matching->is(TT_DictLiteral)))
1634           continue;
1635         FormatToken *Prev = FormatTok->getPreviousNonComment();
1636         if (Prev->is(tok::comma) || Prev->is(tok::semi))
1637           continue;
1638         // getEndLoc is not reliably set during re-lexing, use text length
1639         // instead.
1640         SourceLocation Start =
1641             Prev->Tok.getLocation().getLocWithOffset(Prev->TokenText.size());
1642         // If inserting a comma would push the code over the column limit, skip
1643         // this location - it'd introduce an unstable formatting due to the
1644         // required reflow.
1645         unsigned ColumnNumber =
1646             Env.getSourceManager().getSpellingColumnNumber(Start);
1647         if (ColumnNumber > Style.ColumnLimit)
1648           continue;
1649         // Comma insertions cannot conflict with each other, and this pass has a
1650         // clean set of Replacements, so the operation below cannot fail.
1651         cantFail(Result.add(
1652             tooling::Replacement(Env.getSourceManager(), Start, 0, ",")));
1653       }
1654     }
1655   }
1656 };
1657
1658 // This class clean up the erroneous/redundant code around the given ranges in
1659 // file.
1660 class Cleaner : public TokenAnalyzer {
1661 public:
1662   Cleaner(const Environment &Env, const FormatStyle &Style)
1663       : TokenAnalyzer(Env, Style),
1664         DeletedTokens(FormatTokenLess(Env.getSourceManager())) {}
1665
1666   // FIXME: eliminate unused parameters.
1667   std::pair<tooling::Replacements, unsigned>
1668   analyze(TokenAnnotator &Annotator,
1669           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1670           FormatTokenLexer &Tokens) override {
1671     // FIXME: in the current implementation the granularity of affected range
1672     // is an annotated line. However, this is not sufficient. Furthermore,
1673     // redundant code introduced by replacements does not necessarily
1674     // intercept with ranges of replacements that result in the redundancy.
1675     // To determine if some redundant code is actually introduced by
1676     // replacements(e.g. deletions), we need to come up with a more
1677     // sophisticated way of computing affected ranges.
1678     AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1679
1680     checkEmptyNamespace(AnnotatedLines);
1681
1682     for (auto *Line : AnnotatedLines)
1683       cleanupLine(Line);
1684
1685     return {generateFixes(), 0};
1686   }
1687
1688 private:
1689   void cleanupLine(AnnotatedLine *Line) {
1690     for (auto *Child : Line->Children) {
1691       cleanupLine(Child);
1692     }
1693
1694     if (Line->Affected) {
1695       cleanupRight(Line->First, tok::comma, tok::comma);
1696       cleanupRight(Line->First, TT_CtorInitializerColon, tok::comma);
1697       cleanupRight(Line->First, tok::l_paren, tok::comma);
1698       cleanupLeft(Line->First, tok::comma, tok::r_paren);
1699       cleanupLeft(Line->First, TT_CtorInitializerComma, tok::l_brace);
1700       cleanupLeft(Line->First, TT_CtorInitializerColon, tok::l_brace);
1701       cleanupLeft(Line->First, TT_CtorInitializerColon, tok::equal);
1702     }
1703   }
1704
1705   bool containsOnlyComments(const AnnotatedLine &Line) {
1706     for (FormatToken *Tok = Line.First; Tok != nullptr; Tok = Tok->Next) {
1707       if (Tok->isNot(tok::comment))
1708         return false;
1709     }
1710     return true;
1711   }
1712
1713   // Iterate through all lines and remove any empty (nested) namespaces.
1714   void checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1715     std::set<unsigned> DeletedLines;
1716     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1717       auto &Line = *AnnotatedLines[i];
1718       if (Line.startsWithNamespace()) {
1719         checkEmptyNamespace(AnnotatedLines, i, i, DeletedLines);
1720       }
1721     }
1722
1723     for (auto Line : DeletedLines) {
1724       FormatToken *Tok = AnnotatedLines[Line]->First;
1725       while (Tok) {
1726         deleteToken(Tok);
1727         Tok = Tok->Next;
1728       }
1729     }
1730   }
1731
1732   // The function checks if the namespace, which starts from \p CurrentLine, and
1733   // its nested namespaces are empty and delete them if they are empty. It also
1734   // sets \p NewLine to the last line checked.
1735   // Returns true if the current namespace is empty.
1736   bool checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1737                            unsigned CurrentLine, unsigned &NewLine,
1738                            std::set<unsigned> &DeletedLines) {
1739     unsigned InitLine = CurrentLine, End = AnnotatedLines.size();
1740     if (Style.BraceWrapping.AfterNamespace) {
1741       // If the left brace is in a new line, we should consume it first so that
1742       // it does not make the namespace non-empty.
1743       // FIXME: error handling if there is no left brace.
1744       if (!AnnotatedLines[++CurrentLine]->startsWith(tok::l_brace)) {
1745         NewLine = CurrentLine;
1746         return false;
1747       }
1748     } else if (!AnnotatedLines[CurrentLine]->endsWith(tok::l_brace)) {
1749       return false;
1750     }
1751     while (++CurrentLine < End) {
1752       if (AnnotatedLines[CurrentLine]->startsWith(tok::r_brace))
1753         break;
1754
1755       if (AnnotatedLines[CurrentLine]->startsWithNamespace()) {
1756         if (!checkEmptyNamespace(AnnotatedLines, CurrentLine, NewLine,
1757                                  DeletedLines))
1758           return false;
1759         CurrentLine = NewLine;
1760         continue;
1761       }
1762
1763       if (containsOnlyComments(*AnnotatedLines[CurrentLine]))
1764         continue;
1765
1766       // If there is anything other than comments or nested namespaces in the
1767       // current namespace, the namespace cannot be empty.
1768       NewLine = CurrentLine;
1769       return false;
1770     }
1771
1772     NewLine = CurrentLine;
1773     if (CurrentLine >= End)
1774       return false;
1775
1776     // Check if the empty namespace is actually affected by changed ranges.
1777     if (!AffectedRangeMgr.affectsCharSourceRange(CharSourceRange::getCharRange(
1778             AnnotatedLines[InitLine]->First->Tok.getLocation(),
1779             AnnotatedLines[CurrentLine]->Last->Tok.getEndLoc())))
1780       return false;
1781
1782     for (unsigned i = InitLine; i <= CurrentLine; ++i) {
1783       DeletedLines.insert(i);
1784     }
1785
1786     return true;
1787   }
1788
1789   // Checks pairs {start, start->next},..., {end->previous, end} and deletes one
1790   // of the token in the pair if the left token has \p LK token kind and the
1791   // right token has \p RK token kind. If \p DeleteLeft is true, the left token
1792   // is deleted on match; otherwise, the right token is deleted.
1793   template <typename LeftKind, typename RightKind>
1794   void cleanupPair(FormatToken *Start, LeftKind LK, RightKind RK,
1795                    bool DeleteLeft) {
1796     auto NextNotDeleted = [this](const FormatToken &Tok) -> FormatToken * {
1797       for (auto *Res = Tok.Next; Res; Res = Res->Next)
1798         if (!Res->is(tok::comment) &&
1799             DeletedTokens.find(Res) == DeletedTokens.end())
1800           return Res;
1801       return nullptr;
1802     };
1803     for (auto *Left = Start; Left;) {
1804       auto *Right = NextNotDeleted(*Left);
1805       if (!Right)
1806         break;
1807       if (Left->is(LK) && Right->is(RK)) {
1808         deleteToken(DeleteLeft ? Left : Right);
1809         for (auto *Tok = Left->Next; Tok && Tok != Right; Tok = Tok->Next)
1810           deleteToken(Tok);
1811         // If the right token is deleted, we should keep the left token
1812         // unchanged and pair it with the new right token.
1813         if (!DeleteLeft)
1814           continue;
1815       }
1816       Left = Right;
1817     }
1818   }
1819
1820   template <typename LeftKind, typename RightKind>
1821   void cleanupLeft(FormatToken *Start, LeftKind LK, RightKind RK) {
1822     cleanupPair(Start, LK, RK, /*DeleteLeft=*/true);
1823   }
1824
1825   template <typename LeftKind, typename RightKind>
1826   void cleanupRight(FormatToken *Start, LeftKind LK, RightKind RK) {
1827     cleanupPair(Start, LK, RK, /*DeleteLeft=*/false);
1828   }
1829
1830   // Delete the given token.
1831   inline void deleteToken(FormatToken *Tok) {
1832     if (Tok)
1833       DeletedTokens.insert(Tok);
1834   }
1835
1836   tooling::Replacements generateFixes() {
1837     tooling::Replacements Fixes;
1838     std::vector<FormatToken *> Tokens;
1839     std::copy(DeletedTokens.begin(), DeletedTokens.end(),
1840               std::back_inserter(Tokens));
1841
1842     // Merge multiple continuous token deletions into one big deletion so that
1843     // the number of replacements can be reduced. This makes computing affected
1844     // ranges more efficient when we run reformat on the changed code.
1845     unsigned Idx = 0;
1846     while (Idx < Tokens.size()) {
1847       unsigned St = Idx, End = Idx;
1848       while ((End + 1) < Tokens.size() &&
1849              Tokens[End]->Next == Tokens[End + 1]) {
1850         End++;
1851       }
1852       auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
1853                                               Tokens[End]->Tok.getEndLoc());
1854       auto Err =
1855           Fixes.add(tooling::Replacement(Env.getSourceManager(), SR, ""));
1856       // FIXME: better error handling. for now just print error message and skip
1857       // for the release version.
1858       if (Err) {
1859         llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1860         assert(false && "Fixes must not conflict!");
1861       }
1862       Idx = End + 1;
1863     }
1864
1865     return Fixes;
1866   }
1867
1868   // Class for less-than inequality comparason for the set `RedundantTokens`.
1869   // We store tokens in the order they appear in the translation unit so that
1870   // we do not need to sort them in `generateFixes()`.
1871   struct FormatTokenLess {
1872     FormatTokenLess(const SourceManager &SM) : SM(SM) {}
1873
1874     bool operator()(const FormatToken *LHS, const FormatToken *RHS) const {
1875       return SM.isBeforeInTranslationUnit(LHS->Tok.getLocation(),
1876                                           RHS->Tok.getLocation());
1877     }
1878     const SourceManager &SM;
1879   };
1880
1881   // Tokens to be deleted.
1882   std::set<FormatToken *, FormatTokenLess> DeletedTokens;
1883 };
1884
1885 class ObjCHeaderStyleGuesser : public TokenAnalyzer {
1886 public:
1887   ObjCHeaderStyleGuesser(const Environment &Env, const FormatStyle &Style)
1888       : TokenAnalyzer(Env, Style), IsObjC(false) {}
1889
1890   std::pair<tooling::Replacements, unsigned>
1891   analyze(TokenAnnotator &Annotator,
1892           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1893           FormatTokenLexer &Tokens) override {
1894     assert(Style.Language == FormatStyle::LK_Cpp);
1895     IsObjC = guessIsObjC(Env.getSourceManager(), AnnotatedLines,
1896                          Tokens.getKeywords());
1897     tooling::Replacements Result;
1898     return {Result, 0};
1899   }
1900
1901   bool isObjC() { return IsObjC; }
1902
1903 private:
1904   static bool
1905   guessIsObjC(const SourceManager &SourceManager,
1906               const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1907               const AdditionalKeywords &Keywords) {
1908     // Keep this array sorted, since we are binary searching over it.
1909     static constexpr llvm::StringLiteral FoundationIdentifiers[] = {
1910         "CGFloat",
1911         "CGPoint",
1912         "CGPointMake",
1913         "CGPointZero",
1914         "CGRect",
1915         "CGRectEdge",
1916         "CGRectInfinite",
1917         "CGRectMake",
1918         "CGRectNull",
1919         "CGRectZero",
1920         "CGSize",
1921         "CGSizeMake",
1922         "CGVector",
1923         "CGVectorMake",
1924         "NSAffineTransform",
1925         "NSArray",
1926         "NSAttributedString",
1927         "NSBlockOperation",
1928         "NSBundle",
1929         "NSCache",
1930         "NSCalendar",
1931         "NSCharacterSet",
1932         "NSCountedSet",
1933         "NSData",
1934         "NSDataDetector",
1935         "NSDecimal",
1936         "NSDecimalNumber",
1937         "NSDictionary",
1938         "NSEdgeInsets",
1939         "NSHashTable",
1940         "NSIndexPath",
1941         "NSIndexSet",
1942         "NSInteger",
1943         "NSInvocationOperation",
1944         "NSLocale",
1945         "NSMapTable",
1946         "NSMutableArray",
1947         "NSMutableAttributedString",
1948         "NSMutableCharacterSet",
1949         "NSMutableData",
1950         "NSMutableDictionary",
1951         "NSMutableIndexSet",
1952         "NSMutableOrderedSet",
1953         "NSMutableSet",
1954         "NSMutableString",
1955         "NSNumber",
1956         "NSNumberFormatter",
1957         "NSObject",
1958         "NSOperation",
1959         "NSOperationQueue",
1960         "NSOperationQueuePriority",
1961         "NSOrderedSet",
1962         "NSPoint",
1963         "NSPointerArray",
1964         "NSQualityOfService",
1965         "NSRange",
1966         "NSRect",
1967         "NSRegularExpression",
1968         "NSSet",
1969         "NSSize",
1970         "NSString",
1971         "NSTimeZone",
1972         "NSUInteger",
1973         "NSURL",
1974         "NSURLComponents",
1975         "NSURLQueryItem",
1976         "NSUUID",
1977         "NSValue",
1978         "UIImage",
1979         "UIView",
1980     };
1981
1982     for (auto Line : AnnotatedLines) {
1983       for (const FormatToken *FormatTok = Line->First; FormatTok;
1984            FormatTok = FormatTok->Next) {
1985         if ((FormatTok->Previous && FormatTok->Previous->is(tok::at) &&
1986              (FormatTok->Tok.getObjCKeywordID() != tok::objc_not_keyword ||
1987               FormatTok->isOneOf(tok::numeric_constant, tok::l_square,
1988                                  tok::l_brace))) ||
1989             (FormatTok->Tok.isAnyIdentifier() &&
1990              std::binary_search(std::begin(FoundationIdentifiers),
1991                                 std::end(FoundationIdentifiers),
1992                                 FormatTok->TokenText)) ||
1993             FormatTok->is(TT_ObjCStringLiteral) ||
1994             FormatTok->isOneOf(Keywords.kw_NS_CLOSED_ENUM, Keywords.kw_NS_ENUM,
1995                                Keywords.kw_NS_OPTIONS, TT_ObjCBlockLBrace,
1996                                TT_ObjCBlockLParen, TT_ObjCDecl, TT_ObjCForIn,
1997                                TT_ObjCMethodExpr, TT_ObjCMethodSpecifier,
1998                                TT_ObjCProperty)) {
1999           LLVM_DEBUG(llvm::dbgs()
2000                      << "Detected ObjC at location "
2001                      << FormatTok->Tok.getLocation().printToString(
2002                             SourceManager)
2003                      << " token: " << FormatTok->TokenText << " token type: "
2004                      << getTokenTypeName(FormatTok->getType()) << "\n");
2005           return true;
2006         }
2007         if (guessIsObjC(SourceManager, Line->Children, Keywords))
2008           return true;
2009       }
2010     }
2011     return false;
2012   }
2013
2014   bool IsObjC;
2015 };
2016
2017 struct IncludeDirective {
2018   StringRef Filename;
2019   StringRef Text;
2020   unsigned Offset;
2021   int Category;
2022   int Priority;
2023 };
2024
2025 struct JavaImportDirective {
2026   StringRef Identifier;
2027   StringRef Text;
2028   unsigned Offset;
2029   std::vector<StringRef> AssociatedCommentLines;
2030   bool IsStatic;
2031 };
2032
2033 } // end anonymous namespace
2034
2035 // Determines whether 'Ranges' intersects with ('Start', 'End').
2036 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
2037                          unsigned End) {
2038   for (auto Range : Ranges) {
2039     if (Range.getOffset() < End &&
2040         Range.getOffset() + Range.getLength() > Start)
2041       return true;
2042   }
2043   return false;
2044 }
2045
2046 // Returns a pair (Index, OffsetToEOL) describing the position of the cursor
2047 // before sorting/deduplicating. Index is the index of the include under the
2048 // cursor in the original set of includes. If this include has duplicates, it is
2049 // the index of the first of the duplicates as the others are going to be
2050 // removed. OffsetToEOL describes the cursor's position relative to the end of
2051 // its current line.
2052 // If `Cursor` is not on any #include, `Index` will be UINT_MAX.
2053 static std::pair<unsigned, unsigned>
2054 FindCursorIndex(const SmallVectorImpl<IncludeDirective> &Includes,
2055                 const SmallVectorImpl<unsigned> &Indices, unsigned Cursor) {
2056   unsigned CursorIndex = UINT_MAX;
2057   unsigned OffsetToEOL = 0;
2058   for (int i = 0, e = Includes.size(); i != e; ++i) {
2059     unsigned Start = Includes[Indices[i]].Offset;
2060     unsigned End = Start + Includes[Indices[i]].Text.size();
2061     if (!(Cursor >= Start && Cursor < End))
2062       continue;
2063     CursorIndex = Indices[i];
2064     OffsetToEOL = End - Cursor;
2065     // Put the cursor on the only remaining #include among the duplicate
2066     // #includes.
2067     while (--i >= 0 && Includes[CursorIndex].Text == Includes[Indices[i]].Text)
2068       CursorIndex = i;
2069     break;
2070   }
2071   return std::make_pair(CursorIndex, OffsetToEOL);
2072 }
2073
2074 // Replace all "\r\n" with "\n".
2075 std::string replaceCRLF(const std::string &Code) {
2076   std::string NewCode;
2077   size_t Pos = 0, LastPos = 0;
2078
2079   do {
2080     Pos = Code.find("\r\n", LastPos);
2081     if (Pos == LastPos) {
2082       LastPos++;
2083       continue;
2084     }
2085     if (Pos == std::string::npos) {
2086       NewCode += Code.substr(LastPos);
2087       break;
2088     }
2089     NewCode += Code.substr(LastPos, Pos - LastPos) + "\n";
2090     LastPos = Pos + 2;
2091   } while (Pos != std::string::npos);
2092
2093   return NewCode;
2094 }
2095
2096 // Sorts and deduplicate a block of includes given by 'Includes' alphabetically
2097 // adding the necessary replacement to 'Replaces'. 'Includes' must be in strict
2098 // source order.
2099 // #include directives with the same text will be deduplicated, and only the
2100 // first #include in the duplicate #includes remains. If the `Cursor` is
2101 // provided and put on a deleted #include, it will be moved to the remaining
2102 // #include in the duplicate #includes.
2103 static void sortCppIncludes(const FormatStyle &Style,
2104                             const SmallVectorImpl<IncludeDirective> &Includes,
2105                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
2106                             StringRef Code, tooling::Replacements &Replaces,
2107                             unsigned *Cursor) {
2108   tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
2109   unsigned IncludesBeginOffset = Includes.front().Offset;
2110   unsigned IncludesEndOffset =
2111       Includes.back().Offset + Includes.back().Text.size();
2112   unsigned IncludesBlockSize = IncludesEndOffset - IncludesBeginOffset;
2113   if (!affectsRange(Ranges, IncludesBeginOffset, IncludesEndOffset))
2114     return;
2115   SmallVector<unsigned, 16> Indices;
2116   for (unsigned i = 0, e = Includes.size(); i != e; ++i) {
2117     Indices.push_back(i);
2118   }
2119   llvm::stable_sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
2120     return std::tie(Includes[LHSI].Priority, Includes[LHSI].Filename) <
2121            std::tie(Includes[RHSI].Priority, Includes[RHSI].Filename);
2122   });
2123   // The index of the include on which the cursor will be put after
2124   // sorting/deduplicating.
2125   unsigned CursorIndex;
2126   // The offset from cursor to the end of line.
2127   unsigned CursorToEOLOffset;
2128   if (Cursor)
2129     std::tie(CursorIndex, CursorToEOLOffset) =
2130         FindCursorIndex(Includes, Indices, *Cursor);
2131
2132   // Deduplicate #includes.
2133   Indices.erase(std::unique(Indices.begin(), Indices.end(),
2134                             [&](unsigned LHSI, unsigned RHSI) {
2135                               return Includes[LHSI].Text == Includes[RHSI].Text;
2136                             }),
2137                 Indices.end());
2138
2139   int CurrentCategory = Includes.front().Category;
2140
2141   // If the #includes are out of order, we generate a single replacement fixing
2142   // the entire block. Otherwise, no replacement is generated.
2143   // In case Style.IncldueStyle.IncludeBlocks != IBS_Preserve, this check is not
2144   // enough as additional newlines might be added or removed across #include
2145   // blocks. This we handle below by generating the updated #imclude blocks and
2146   // comparing it to the original.
2147   if (Indices.size() == Includes.size() && llvm::is_sorted(Indices) &&
2148       Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Preserve)
2149     return;
2150
2151   std::string result;
2152   for (unsigned Index : Indices) {
2153     if (!result.empty()) {
2154       result += "\n";
2155       if (Style.IncludeStyle.IncludeBlocks ==
2156               tooling::IncludeStyle::IBS_Regroup &&
2157           CurrentCategory != Includes[Index].Category)
2158         result += "\n";
2159     }
2160     result += Includes[Index].Text;
2161     if (Cursor && CursorIndex == Index)
2162       *Cursor = IncludesBeginOffset + result.size() - CursorToEOLOffset;
2163     CurrentCategory = Includes[Index].Category;
2164   }
2165
2166   // If the #includes are out of order, we generate a single replacement fixing
2167   // the entire range of blocks. Otherwise, no replacement is generated.
2168   if (replaceCRLF(result) == replaceCRLF(std::string(Code.substr(
2169                                  IncludesBeginOffset, IncludesBlockSize))))
2170     return;
2171
2172   auto Err = Replaces.add(tooling::Replacement(
2173       FileName, Includes.front().Offset, IncludesBlockSize, result));
2174   // FIXME: better error handling. For now, just skip the replacement for the
2175   // release version.
2176   if (Err) {
2177     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
2178     assert(false);
2179   }
2180 }
2181
2182 namespace {
2183
2184 const char CppIncludeRegexPattern[] =
2185     R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
2186
2187 } // anonymous namespace
2188
2189 tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
2190                                       ArrayRef<tooling::Range> Ranges,
2191                                       StringRef FileName,
2192                                       tooling::Replacements &Replaces,
2193                                       unsigned *Cursor) {
2194   unsigned Prev = 0;
2195   unsigned SearchFrom = 0;
2196   llvm::Regex IncludeRegex(CppIncludeRegexPattern);
2197   SmallVector<StringRef, 4> Matches;
2198   SmallVector<IncludeDirective, 16> IncludesInBlock;
2199
2200   // In compiled files, consider the first #include to be the main #include of
2201   // the file if it is not a system #include. This ensures that the header
2202   // doesn't have hidden dependencies
2203   // (http://llvm.org/docs/CodingStandards.html#include-style).
2204   //
2205   // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
2206   // cases where the first #include is unlikely to be the main header.
2207   tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
2208   bool FirstIncludeBlock = true;
2209   bool MainIncludeFound = false;
2210   bool FormattingOff = false;
2211
2212   for (;;) {
2213     auto Pos = Code.find('\n', SearchFrom);
2214     StringRef Line =
2215         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
2216
2217     StringRef Trimmed = Line.trim();
2218     if (Trimmed == "// clang-format off" || Trimmed == "/* clang-format off */")
2219       FormattingOff = true;
2220     else if (Trimmed == "// clang-format on" ||
2221              Trimmed == "/* clang-format on */")
2222       FormattingOff = false;
2223
2224     const bool EmptyLineSkipped =
2225         Trimmed.empty() &&
2226         (Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Merge ||
2227          Style.IncludeStyle.IncludeBlocks ==
2228              tooling::IncludeStyle::IBS_Regroup);
2229
2230     if (!FormattingOff && !Line.endswith("\\")) {
2231       if (IncludeRegex.match(Line, &Matches)) {
2232         StringRef IncludeName = Matches[2];
2233         int Category = Categories.getIncludePriority(
2234             IncludeName,
2235             /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
2236         int Priority = Categories.getSortIncludePriority(
2237             IncludeName, !MainIncludeFound && FirstIncludeBlock);
2238         if (Category == 0)
2239           MainIncludeFound = true;
2240         IncludesInBlock.push_back(
2241             {IncludeName, Line, Prev, Category, Priority});
2242       } else if (!IncludesInBlock.empty() && !EmptyLineSkipped) {
2243         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code,
2244                         Replaces, Cursor);
2245         IncludesInBlock.clear();
2246         FirstIncludeBlock = false;
2247       }
2248       Prev = Pos + 1;
2249     }
2250     if (Pos == StringRef::npos || Pos + 1 == Code.size())
2251       break;
2252     SearchFrom = Pos + 1;
2253   }
2254   if (!IncludesInBlock.empty()) {
2255     sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code, Replaces,
2256                     Cursor);
2257   }
2258   return Replaces;
2259 }
2260
2261 // Returns group number to use as a first order sort on imports. Gives UINT_MAX
2262 // if the import does not match any given groups.
2263 static unsigned findJavaImportGroup(const FormatStyle &Style,
2264                                     StringRef ImportIdentifier) {
2265   unsigned LongestMatchIndex = UINT_MAX;
2266   unsigned LongestMatchLength = 0;
2267   for (unsigned I = 0; I < Style.JavaImportGroups.size(); I++) {
2268     std::string GroupPrefix = Style.JavaImportGroups[I];
2269     if (ImportIdentifier.startswith(GroupPrefix) &&
2270         GroupPrefix.length() > LongestMatchLength) {
2271       LongestMatchIndex = I;
2272       LongestMatchLength = GroupPrefix.length();
2273     }
2274   }
2275   return LongestMatchIndex;
2276 }
2277
2278 // Sorts and deduplicates a block of includes given by 'Imports' based on
2279 // JavaImportGroups, then adding the necessary replacement to 'Replaces'.
2280 // Import declarations with the same text will be deduplicated. Between each
2281 // import group, a newline is inserted, and within each import group, a
2282 // lexicographic sort based on ASCII value is performed.
2283 static void sortJavaImports(const FormatStyle &Style,
2284                             const SmallVectorImpl<JavaImportDirective> &Imports,
2285                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
2286                             StringRef Code, tooling::Replacements &Replaces) {
2287   unsigned ImportsBeginOffset = Imports.front().Offset;
2288   unsigned ImportsEndOffset =
2289       Imports.back().Offset + Imports.back().Text.size();
2290   unsigned ImportsBlockSize = ImportsEndOffset - ImportsBeginOffset;
2291   if (!affectsRange(Ranges, ImportsBeginOffset, ImportsEndOffset))
2292     return;
2293   SmallVector<unsigned, 16> Indices;
2294   SmallVector<unsigned, 16> JavaImportGroups;
2295   for (unsigned i = 0, e = Imports.size(); i != e; ++i) {
2296     Indices.push_back(i);
2297     JavaImportGroups.push_back(
2298         findJavaImportGroup(Style, Imports[i].Identifier));
2299   }
2300   llvm::sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
2301     // Negating IsStatic to push static imports above non-static imports.
2302     return std::make_tuple(!Imports[LHSI].IsStatic, JavaImportGroups[LHSI],
2303                            Imports[LHSI].Identifier) <
2304            std::make_tuple(!Imports[RHSI].IsStatic, JavaImportGroups[RHSI],
2305                            Imports[RHSI].Identifier);
2306   });
2307
2308   // Deduplicate imports.
2309   Indices.erase(std::unique(Indices.begin(), Indices.end(),
2310                             [&](unsigned LHSI, unsigned RHSI) {
2311                               return Imports[LHSI].Text == Imports[RHSI].Text;
2312                             }),
2313                 Indices.end());
2314
2315   bool CurrentIsStatic = Imports[Indices.front()].IsStatic;
2316   unsigned CurrentImportGroup = JavaImportGroups[Indices.front()];
2317
2318   std::string result;
2319   for (unsigned Index : Indices) {
2320     if (!result.empty()) {
2321       result += "\n";
2322       if (CurrentIsStatic != Imports[Index].IsStatic ||
2323           CurrentImportGroup != JavaImportGroups[Index])
2324         result += "\n";
2325     }
2326     for (StringRef CommentLine : Imports[Index].AssociatedCommentLines) {
2327       result += CommentLine;
2328       result += "\n";
2329     }
2330     result += Imports[Index].Text;
2331     CurrentIsStatic = Imports[Index].IsStatic;
2332     CurrentImportGroup = JavaImportGroups[Index];
2333   }
2334
2335   // If the imports are out of order, we generate a single replacement fixing
2336   // the entire block. Otherwise, no replacement is generated.
2337   if (replaceCRLF(result) == replaceCRLF(std::string(Code.substr(
2338                                  Imports.front().Offset, ImportsBlockSize))))
2339     return;
2340
2341   auto Err = Replaces.add(tooling::Replacement(FileName, Imports.front().Offset,
2342                                                ImportsBlockSize, result));
2343   // FIXME: better error handling. For now, just skip the replacement for the
2344   // release version.
2345   if (Err) {
2346     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
2347     assert(false);
2348   }
2349 }
2350
2351 namespace {
2352
2353 const char JavaImportRegexPattern[] =
2354     "^[\t ]*import[\t ]+(static[\t ]*)?([^\t ]*)[\t ]*;";
2355
2356 } // anonymous namespace
2357
2358 tooling::Replacements sortJavaImports(const FormatStyle &Style, StringRef Code,
2359                                       ArrayRef<tooling::Range> Ranges,
2360                                       StringRef FileName,
2361                                       tooling::Replacements &Replaces) {
2362   unsigned Prev = 0;
2363   unsigned SearchFrom = 0;
2364   llvm::Regex ImportRegex(JavaImportRegexPattern);
2365   SmallVector<StringRef, 4> Matches;
2366   SmallVector<JavaImportDirective, 16> ImportsInBlock;
2367   std::vector<StringRef> AssociatedCommentLines;
2368
2369   bool FormattingOff = false;
2370
2371   for (;;) {
2372     auto Pos = Code.find('\n', SearchFrom);
2373     StringRef Line =
2374         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
2375
2376     StringRef Trimmed = Line.trim();
2377     if (Trimmed == "// clang-format off")
2378       FormattingOff = true;
2379     else if (Trimmed == "// clang-format on")
2380       FormattingOff = false;
2381
2382     if (ImportRegex.match(Line, &Matches)) {
2383       if (FormattingOff) {
2384         // If at least one import line has formatting turned off, turn off
2385         // formatting entirely.
2386         return Replaces;
2387       }
2388       StringRef Static = Matches[1];
2389       StringRef Identifier = Matches[2];
2390       bool IsStatic = false;
2391       if (Static.contains("static")) {
2392         IsStatic = true;
2393       }
2394       ImportsInBlock.push_back(
2395           {Identifier, Line, Prev, AssociatedCommentLines, IsStatic});
2396       AssociatedCommentLines.clear();
2397     } else if (Trimmed.size() > 0 && !ImportsInBlock.empty()) {
2398       // Associating comments within the imports with the nearest import below
2399       AssociatedCommentLines.push_back(Line);
2400     }
2401     Prev = Pos + 1;
2402     if (Pos == StringRef::npos || Pos + 1 == Code.size())
2403       break;
2404     SearchFrom = Pos + 1;
2405   }
2406   if (!ImportsInBlock.empty())
2407     sortJavaImports(Style, ImportsInBlock, Ranges, FileName, Code, Replaces);
2408   return Replaces;
2409 }
2410
2411 bool isMpegTS(StringRef Code) {
2412   // MPEG transport streams use the ".ts" file extension. clang-format should
2413   // not attempt to format those. MPEG TS' frame format starts with 0x47 every
2414   // 189 bytes - detect that and return.
2415   return Code.size() > 188 && Code[0] == 0x47 && Code[188] == 0x47;
2416 }
2417
2418 bool isLikelyXml(StringRef Code) { return Code.ltrim().startswith("<"); }
2419
2420 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
2421                                    ArrayRef<tooling::Range> Ranges,
2422                                    StringRef FileName, unsigned *Cursor) {
2423   tooling::Replacements Replaces;
2424   if (!Style.SortIncludes)
2425     return Replaces;
2426   if (isLikelyXml(Code))
2427     return Replaces;
2428   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript &&
2429       isMpegTS(Code))
2430     return Replaces;
2431   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
2432     return sortJavaScriptImports(Style, Code, Ranges, FileName);
2433   if (Style.Language == FormatStyle::LanguageKind::LK_Java)
2434     return sortJavaImports(Style, Code, Ranges, FileName, Replaces);
2435   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
2436   return Replaces;
2437 }
2438
2439 template <typename T>
2440 static llvm::Expected<tooling::Replacements>
2441 processReplacements(T ProcessFunc, StringRef Code,
2442                     const tooling::Replacements &Replaces,
2443                     const FormatStyle &Style) {
2444   if (Replaces.empty())
2445     return tooling::Replacements();
2446
2447   auto NewCode = applyAllReplacements(Code, Replaces);
2448   if (!NewCode)
2449     return NewCode.takeError();
2450   std::vector<tooling::Range> ChangedRanges = Replaces.getAffectedRanges();
2451   StringRef FileName = Replaces.begin()->getFilePath();
2452
2453   tooling::Replacements FormatReplaces =
2454       ProcessFunc(Style, *NewCode, ChangedRanges, FileName);
2455
2456   return Replaces.merge(FormatReplaces);
2457 }
2458
2459 llvm::Expected<tooling::Replacements>
2460 formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
2461                    const FormatStyle &Style) {
2462   // We need to use lambda function here since there are two versions of
2463   // `sortIncludes`.
2464   auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
2465                          std::vector<tooling::Range> Ranges,
2466                          StringRef FileName) -> tooling::Replacements {
2467     return sortIncludes(Style, Code, Ranges, FileName);
2468   };
2469   auto SortedReplaces =
2470       processReplacements(SortIncludes, Code, Replaces, Style);
2471   if (!SortedReplaces)
2472     return SortedReplaces.takeError();
2473
2474   // We need to use lambda function here since there are two versions of
2475   // `reformat`.
2476   auto Reformat = [](const FormatStyle &Style, StringRef Code,
2477                      std::vector<tooling::Range> Ranges,
2478                      StringRef FileName) -> tooling::Replacements {
2479     return reformat(Style, Code, Ranges, FileName);
2480   };
2481   return processReplacements(Reformat, Code, *SortedReplaces, Style);
2482 }
2483
2484 namespace {
2485
2486 inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
2487   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 0 &&
2488          llvm::Regex(CppIncludeRegexPattern)
2489              .match(Replace.getReplacementText());
2490 }
2491
2492 inline bool isHeaderDeletion(const tooling::Replacement &Replace) {
2493   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 1;
2494 }
2495
2496 // FIXME: insert empty lines between newly created blocks.
2497 tooling::Replacements
2498 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
2499                         const FormatStyle &Style) {
2500   if (!Style.isCpp())
2501     return Replaces;
2502
2503   tooling::Replacements HeaderInsertions;
2504   std::set<llvm::StringRef> HeadersToDelete;
2505   tooling::Replacements Result;
2506   for (const auto &R : Replaces) {
2507     if (isHeaderInsertion(R)) {
2508       // Replacements from \p Replaces must be conflict-free already, so we can
2509       // simply consume the error.
2510       llvm::consumeError(HeaderInsertions.add(R));
2511     } else if (isHeaderDeletion(R)) {
2512       HeadersToDelete.insert(R.getReplacementText());
2513     } else if (R.getOffset() == UINT_MAX) {
2514       llvm::errs() << "Insertions other than header #include insertion are "
2515                       "not supported! "
2516                    << R.getReplacementText() << "\n";
2517     } else {
2518       llvm::consumeError(Result.add(R));
2519     }
2520   }
2521   if (HeaderInsertions.empty() && HeadersToDelete.empty())
2522     return Replaces;
2523
2524   StringRef FileName = Replaces.begin()->getFilePath();
2525   tooling::HeaderIncludes Includes(FileName, Code, Style.IncludeStyle);
2526
2527   for (const auto &Header : HeadersToDelete) {
2528     tooling::Replacements Replaces =
2529         Includes.remove(Header.trim("\"<>"), Header.startswith("<"));
2530     for (const auto &R : Replaces) {
2531       auto Err = Result.add(R);
2532       if (Err) {
2533         // Ignore the deletion on conflict.
2534         llvm::errs() << "Failed to add header deletion replacement for "
2535                      << Header << ": " << llvm::toString(std::move(Err))
2536                      << "\n";
2537       }
2538     }
2539   }
2540
2541   llvm::Regex IncludeRegex = llvm::Regex(CppIncludeRegexPattern);
2542   llvm::SmallVector<StringRef, 4> Matches;
2543   for (const auto &R : HeaderInsertions) {
2544     auto IncludeDirective = R.getReplacementText();
2545     bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
2546     assert(Matched && "Header insertion replacement must have replacement text "
2547                       "'#include ...'");
2548     (void)Matched;
2549     auto IncludeName = Matches[2];
2550     auto Replace =
2551         Includes.insert(IncludeName.trim("\"<>"), IncludeName.startswith("<"));
2552     if (Replace) {
2553       auto Err = Result.add(*Replace);
2554       if (Err) {
2555         llvm::consumeError(std::move(Err));
2556         unsigned NewOffset =
2557             Result.getShiftedCodePosition(Replace->getOffset());
2558         auto Shifted = tooling::Replacement(FileName, NewOffset, 0,
2559                                             Replace->getReplacementText());
2560         Result = Result.merge(tooling::Replacements(Shifted));
2561       }
2562     }
2563   }
2564   return Result;
2565 }
2566
2567 } // anonymous namespace
2568
2569 llvm::Expected<tooling::Replacements>
2570 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
2571                           const FormatStyle &Style) {
2572   // We need to use lambda function here since there are two versions of
2573   // `cleanup`.
2574   auto Cleanup = [](const FormatStyle &Style, StringRef Code,
2575                     std::vector<tooling::Range> Ranges,
2576                     StringRef FileName) -> tooling::Replacements {
2577     return cleanup(Style, Code, Ranges, FileName);
2578   };
2579   // Make header insertion replacements insert new headers into correct blocks.
2580   tooling::Replacements NewReplaces =
2581       fixCppIncludeInsertions(Code, Replaces, Style);
2582   return processReplacements(Cleanup, Code, NewReplaces, Style);
2583 }
2584
2585 namespace internal {
2586 std::pair<tooling::Replacements, unsigned>
2587 reformat(const FormatStyle &Style, StringRef Code,
2588          ArrayRef<tooling::Range> Ranges, unsigned FirstStartColumn,
2589          unsigned NextStartColumn, unsigned LastStartColumn, StringRef FileName,
2590          FormattingAttemptStatus *Status) {
2591   FormatStyle Expanded = expandPresets(Style);
2592   if (Expanded.DisableFormat)
2593     return {tooling::Replacements(), 0};
2594   if (isLikelyXml(Code))
2595     return {tooling::Replacements(), 0};
2596   if (Expanded.Language == FormatStyle::LK_JavaScript && isMpegTS(Code))
2597     return {tooling::Replacements(), 0};
2598
2599   typedef std::function<std::pair<tooling::Replacements, unsigned>(
2600       const Environment &)>
2601       AnalyzerPass;
2602   SmallVector<AnalyzerPass, 4> Passes;
2603
2604   if (Style.Language == FormatStyle::LK_Cpp) {
2605     if (Style.FixNamespaceComments)
2606       Passes.emplace_back([&](const Environment &Env) {
2607         return NamespaceEndCommentsFixer(Env, Expanded).process();
2608       });
2609
2610     if (Style.SortUsingDeclarations)
2611       Passes.emplace_back([&](const Environment &Env) {
2612         return UsingDeclarationsSorter(Env, Expanded).process();
2613       });
2614   }
2615
2616   if (Style.Language == FormatStyle::LK_JavaScript &&
2617       Style.JavaScriptQuotes != FormatStyle::JSQS_Leave)
2618     Passes.emplace_back([&](const Environment &Env) {
2619       return JavaScriptRequoter(Env, Expanded).process();
2620     });
2621
2622   Passes.emplace_back([&](const Environment &Env) {
2623     return Formatter(Env, Expanded, Status).process();
2624   });
2625
2626   if (Style.Language == FormatStyle::LK_JavaScript &&
2627       Style.InsertTrailingCommas == FormatStyle::TCS_Wrapped)
2628     Passes.emplace_back([&](const Environment &Env) {
2629       return TrailingCommaInserter(Env, Expanded).process();
2630     });
2631
2632   auto Env =
2633       std::make_unique<Environment>(Code, FileName, Ranges, FirstStartColumn,
2634                                     NextStartColumn, LastStartColumn);
2635   llvm::Optional<std::string> CurrentCode = None;
2636   tooling::Replacements Fixes;
2637   unsigned Penalty = 0;
2638   for (size_t I = 0, E = Passes.size(); I < E; ++I) {
2639     std::pair<tooling::Replacements, unsigned> PassFixes = Passes[I](*Env);
2640     auto NewCode = applyAllReplacements(
2641         CurrentCode ? StringRef(*CurrentCode) : Code, PassFixes.first);
2642     if (NewCode) {
2643       Fixes = Fixes.merge(PassFixes.first);
2644       Penalty += PassFixes.second;
2645       if (I + 1 < E) {
2646         CurrentCode = std::move(*NewCode);
2647         Env = std::make_unique<Environment>(
2648             *CurrentCode, FileName,
2649             tooling::calculateRangesAfterReplacements(Fixes, Ranges),
2650             FirstStartColumn, NextStartColumn, LastStartColumn);
2651       }
2652     }
2653   }
2654
2655   return {Fixes, Penalty};
2656 }
2657 } // namespace internal
2658
2659 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2660                                ArrayRef<tooling::Range> Ranges,
2661                                StringRef FileName,
2662                                FormattingAttemptStatus *Status) {
2663   return internal::reformat(Style, Code, Ranges,
2664                             /*FirstStartColumn=*/0,
2665                             /*NextStartColumn=*/0,
2666                             /*LastStartColumn=*/0, FileName, Status)
2667       .first;
2668 }
2669
2670 tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
2671                               ArrayRef<tooling::Range> Ranges,
2672                               StringRef FileName) {
2673   // cleanups only apply to C++ (they mostly concern ctor commas etc.)
2674   if (Style.Language != FormatStyle::LK_Cpp)
2675     return tooling::Replacements();
2676   return Cleaner(Environment(Code, FileName, Ranges), Style).process().first;
2677 }
2678
2679 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2680                                ArrayRef<tooling::Range> Ranges,
2681                                StringRef FileName, bool *IncompleteFormat) {
2682   FormattingAttemptStatus Status;
2683   auto Result = reformat(Style, Code, Ranges, FileName, &Status);
2684   if (!Status.FormatComplete)
2685     *IncompleteFormat = true;
2686   return Result;
2687 }
2688
2689 tooling::Replacements fixNamespaceEndComments(const FormatStyle &Style,
2690                                               StringRef Code,
2691                                               ArrayRef<tooling::Range> Ranges,
2692                                               StringRef FileName) {
2693   return NamespaceEndCommentsFixer(Environment(Code, FileName, Ranges), Style)
2694       .process()
2695       .first;
2696 }
2697
2698 tooling::Replacements sortUsingDeclarations(const FormatStyle &Style,
2699                                             StringRef Code,
2700                                             ArrayRef<tooling::Range> Ranges,
2701                                             StringRef FileName) {
2702   return UsingDeclarationsSorter(Environment(Code, FileName, Ranges), Style)
2703       .process()
2704       .first;
2705 }
2706
2707 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
2708   LangOptions LangOpts;
2709
2710   FormatStyle::LanguageStandard LexingStd = Style.Standard;
2711   if (LexingStd == FormatStyle::LS_Auto)
2712     LexingStd = FormatStyle::LS_Latest;
2713   if (LexingStd == FormatStyle::LS_Latest)
2714     LexingStd = FormatStyle::LS_Cpp20;
2715   LangOpts.CPlusPlus = 1;
2716   LangOpts.CPlusPlus11 = LexingStd >= FormatStyle::LS_Cpp11;
2717   LangOpts.CPlusPlus14 = LexingStd >= FormatStyle::LS_Cpp14;
2718   LangOpts.CPlusPlus17 = LexingStd >= FormatStyle::LS_Cpp17;
2719   LangOpts.CPlusPlus20 = LexingStd >= FormatStyle::LS_Cpp20;
2720   LangOpts.Char8 = LexingStd >= FormatStyle::LS_Cpp20;
2721
2722   LangOpts.LineComment = 1;
2723   bool AlternativeOperators = Style.isCpp();
2724   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
2725   LangOpts.Bool = 1;
2726   LangOpts.ObjC = 1;
2727   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
2728   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
2729   return LangOpts;
2730 }
2731
2732 const char *StyleOptionHelpDescription =
2733     "Coding style, currently supports:\n"
2734     "  LLVM, GNU, Google, Chromium, Microsoft, Mozilla, WebKit.\n"
2735     "Use -style=file to load style configuration from\n"
2736     ".clang-format file located in one of the parent\n"
2737     "directories of the source file (or current\n"
2738     "directory for stdin).\n"
2739     "Use -style=\"{key: value, ...}\" to set specific\n"
2740     "parameters, e.g.:\n"
2741     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
2742
2743 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
2744   if (FileName.endswith(".java"))
2745     return FormatStyle::LK_Java;
2746   if (FileName.endswith_lower(".js") || FileName.endswith_lower(".mjs") ||
2747       FileName.endswith_lower(".ts"))
2748     return FormatStyle::LK_JavaScript; // (module) JavaScript or TypeScript.
2749   if (FileName.endswith(".m") || FileName.endswith(".mm"))
2750     return FormatStyle::LK_ObjC;
2751   if (FileName.endswith_lower(".proto") ||
2752       FileName.endswith_lower(".protodevel"))
2753     return FormatStyle::LK_Proto;
2754   if (FileName.endswith_lower(".textpb") ||
2755       FileName.endswith_lower(".pb.txt") ||
2756       FileName.endswith_lower(".textproto") ||
2757       FileName.endswith_lower(".asciipb"))
2758     return FormatStyle::LK_TextProto;
2759   if (FileName.endswith_lower(".td"))
2760     return FormatStyle::LK_TableGen;
2761   if (FileName.endswith_lower(".cs"))
2762     return FormatStyle::LK_CSharp;
2763   return FormatStyle::LK_Cpp;
2764 }
2765
2766 FormatStyle::LanguageKind guessLanguage(StringRef FileName, StringRef Code) {
2767   const auto GuessedLanguage = getLanguageByFileName(FileName);
2768   if (GuessedLanguage == FormatStyle::LK_Cpp) {
2769     auto Extension = llvm::sys::path::extension(FileName);
2770     // If there's no file extension (or it's .h), we need to check the contents
2771     // of the code to see if it contains Objective-C.
2772     if (Extension.empty() || Extension == ".h") {
2773       auto NonEmptyFileName = FileName.empty() ? "guess.h" : FileName;
2774       Environment Env(Code, NonEmptyFileName, /*Ranges=*/{});
2775       ObjCHeaderStyleGuesser Guesser(Env, getLLVMStyle());
2776       Guesser.process();
2777       if (Guesser.isObjC())
2778         return FormatStyle::LK_ObjC;
2779     }
2780   }
2781   return GuessedLanguage;
2782 }
2783
2784 const char *DefaultFormatStyle = "file";
2785
2786 const char *DefaultFallbackStyle = "LLVM";
2787
2788 llvm::Expected<FormatStyle> getStyle(StringRef StyleName, StringRef FileName,
2789                                      StringRef FallbackStyleName,
2790                                      StringRef Code,
2791                                      llvm::vfs::FileSystem *FS) {
2792   if (!FS) {
2793     FS = llvm::vfs::getRealFileSystem().get();
2794   }
2795   FormatStyle Style = getLLVMStyle(guessLanguage(FileName, Code));
2796
2797   FormatStyle FallbackStyle = getNoStyle();
2798   if (!getPredefinedStyle(FallbackStyleName, Style.Language, &FallbackStyle))
2799     return make_string_error("Invalid fallback style \"" + FallbackStyleName);
2800
2801   if (StyleName.startswith("{")) {
2802     // Parse YAML/JSON style from the command line.
2803     if (std::error_code ec = parseConfiguration(StyleName, &Style))
2804       return make_string_error("Error parsing -style: " + ec.message());
2805     return Style;
2806   }
2807
2808   if (!StyleName.equals_lower("file")) {
2809     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
2810       return make_string_error("Invalid value for -style");
2811     return Style;
2812   }
2813
2814   // Look for .clang-format/_clang-format file in the file's parent directories.
2815   SmallString<128> UnsuitableConfigFiles;
2816   SmallString<128> Path(FileName);
2817   if (std::error_code EC = FS->makeAbsolute(Path))
2818     return make_string_error(EC.message());
2819
2820   llvm::SmallVector<std::string, 2> FilesToLookFor;
2821   FilesToLookFor.push_back(".clang-format");
2822   FilesToLookFor.push_back("_clang-format");
2823
2824   for (StringRef Directory = Path; !Directory.empty();
2825        Directory = llvm::sys::path::parent_path(Directory)) {
2826
2827     auto Status = FS->status(Directory);
2828     if (!Status ||
2829         Status->getType() != llvm::sys::fs::file_type::directory_file) {
2830       continue;
2831     }
2832
2833     for (const auto &F : FilesToLookFor) {
2834       SmallString<128> ConfigFile(Directory);
2835
2836       llvm::sys::path::append(ConfigFile, F);
2837       LLVM_DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2838
2839       Status = FS->status(ConfigFile.str());
2840
2841       if (Status &&
2842           (Status->getType() == llvm::sys::fs::file_type::regular_file)) {
2843         llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2844             FS->getBufferForFile(ConfigFile.str());
2845         if (std::error_code EC = Text.getError())
2846           return make_string_error(EC.message());
2847         if (std::error_code ec =
2848                 parseConfiguration(Text.get()->getBuffer(), &Style)) {
2849           if (ec == ParseError::Unsuitable) {
2850             if (!UnsuitableConfigFiles.empty())
2851               UnsuitableConfigFiles.append(", ");
2852             UnsuitableConfigFiles.append(ConfigFile);
2853             continue;
2854           }
2855           return make_string_error("Error reading " + ConfigFile + ": " +
2856                                    ec.message());
2857         }
2858         LLVM_DEBUG(llvm::dbgs()
2859                    << "Using configuration file " << ConfigFile << "\n");
2860         return Style;
2861       }
2862     }
2863   }
2864   if (!UnsuitableConfigFiles.empty())
2865     return make_string_error("Configuration file(s) do(es) not support " +
2866                              getLanguageName(Style.Language) + ": " +
2867                              UnsuitableConfigFiles);
2868   return FallbackStyle;
2869 }
2870
2871 } // namespace format
2872 } // namespace clang