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