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

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