Home | History | Annotate | Download | only in Format
      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
   1788