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
44using clang::format::FormatStyle;
45
46LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
47LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::IncludeCategory)
48
49namespace llvm {
50namespace yaml {
51template <> 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
61template <> 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
71template <> 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
83template <> 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
91template <> 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
102template <> 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
112template <> 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
125template <>
126struct 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
137template <>
138struct 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
151template <>
152struct 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
161template <> 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
173template <> 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
185template <>
186struct 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
200template <> 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
361template <> 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
377template <> 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.
389template <> 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
412namespace clang {
413namespace format {
414
415const std::error_category &getParseCategory() {
416  static ParseErrorCategory C;
417  return C;
418}
419std::error_code make_error_code(ParseError e) {
420  return std::error_code(static_cast<int>(e), getParseCategory());
421}
422
423const char *ParseErrorCategory::name() const LLVM_NOEXCEPT {
424  return "clang-format.parse_error";
425}
426
427std::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
439static 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
487FormatStyle 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
573FormatStyle 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
629FormatStyle 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
648FormatStyle 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
670FormatStyle 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
690FormatStyle 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
704FormatStyle getNoStyle() {
705  FormatStyle NoStyle = getLLVMStyle();
706  NoStyle.DisableFormat = true;
707  NoStyle.SortIncludes = false;
708  return NoStyle;
709}
710
711bool 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
735std::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
781std::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
792namespace {
793
794class Formatter : public TokenAnalyzer {
795public:
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
830private:
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.
984class Cleaner : public TokenAnalyzer {
985public:
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
1019private:
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
1193struct 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').
1203static 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.
1216static 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
1264namespace {
1265
1266// This class manages priorities of #include categories and calculates
1267// priorities for headers.
1268class IncludeCategoryManager {
1269public:
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
1296private:
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
1318const char IncludeRegexPattern[] =
1319    R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
1320
1321} // anonymous namespace
1322
1323tooling::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
1383tooling::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
1395template <typename T>
1396static llvm::Expected<tooling::Replacements>
1397processReplacements(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
1416llvm::Expected<tooling::Replacements>
1417formatReplacements(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
1441namespace {
1442
1443inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
1444  return Replace.getOffset() == UINT_MAX &&
1445         llvm::Regex(IncludeRegexPattern).match(Replace.getReplacementText());
1446}
1447
1448void 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).
1457bool 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
1467unsigned 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.
1494tooling::Replacements
1495fixCppIncludeInsertions(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
1598llvm::Expected<tooling::Replacements>
1599cleanupAroundReplacements(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
1614tooling::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
1626tooling::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
1639tooling::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
1646tooling::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
1655LangOptions 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
1671const 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
1682static 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
1695FormatStyle 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