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 "ContinuationIndenter.h"
17 #include "TokenAnnotator.h"
18 #include "UnwrappedLineFormatter.h"
19 #include "UnwrappedLineParser.h"
20 #include "WhitespaceManager.h"
21 #include "clang/Basic/Diagnostic.h"
22 #include "clang/Basic/DiagnosticOptions.h"
23 #include "clang/Basic/SourceManager.h"
24 #include "clang/Format/Format.h"
25 #include "clang/Lex/Lexer.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/Support/Allocator.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/Path.h"
30 #include "llvm/Support/YAMLTraits.h"
31 #include <queue>
32 #include <string>
33 
34 #define DEBUG_TYPE "format-formatter"
35 
36 using clang::format::FormatStyle;
37 
38 LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
39 
40 namespace llvm {
41 namespace yaml {
42 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
43   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
44     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
45     IO.enumCase(Value, "Java", FormatStyle::LK_Java);
46     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
47     IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
48   }
49 };
50 
51 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
52   static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
53     IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
54     IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
55     IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
56     IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
57     IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
58   }
59 };
60 
61 template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
62   static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
63     IO.enumCase(Value, "Never", FormatStyle::UT_Never);
64     IO.enumCase(Value, "false", FormatStyle::UT_Never);
65     IO.enumCase(Value, "Always", FormatStyle::UT_Always);
66     IO.enumCase(Value, "true", FormatStyle::UT_Always);
67     IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
68   }
69 };
70 
71 template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
72   static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
73     IO.enumCase(Value, "None", FormatStyle::SFS_None);
74     IO.enumCase(Value, "false", FormatStyle::SFS_None);
75     IO.enumCase(Value, "All", FormatStyle::SFS_All);
76     IO.enumCase(Value, "true", FormatStyle::SFS_All);
77     IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
78     IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
79   }
80 };
81 
82 template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
83   static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
84     IO.enumCase(Value, "All", FormatStyle::BOS_All);
85     IO.enumCase(Value, "true", FormatStyle::BOS_All);
86     IO.enumCase(Value, "None", FormatStyle::BOS_None);
87     IO.enumCase(Value, "false", FormatStyle::BOS_None);
88     IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
89   }
90 };
91 
92 template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
93   static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
94     IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
95     IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
96     IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
97     IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
98     IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
99   }
100 };
101 
102 template <>
103 struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
104   static void enumeration(IO &IO,
105                           FormatStyle::NamespaceIndentationKind &Value) {
106     IO.enumCase(Value, "None", FormatStyle::NI_None);
107     IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
108     IO.enumCase(Value, "All", FormatStyle::NI_All);
109   }
110 };
111 
112 template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
113   static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
114     IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
115     IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
116     IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
117 
118     // For backward compatibility.
119     IO.enumCase(Value, "true", FormatStyle::PAS_Left);
120     IO.enumCase(Value, "false", FormatStyle::PAS_Right);
121   }
122 };
123 
124 template <>
125 struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
126   static void enumeration(IO &IO,
127                           FormatStyle::SpaceBeforeParensOptions &Value) {
128     IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
129     IO.enumCase(Value, "ControlStatements",
130                 FormatStyle::SBPO_ControlStatements);
131     IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
132 
133     // For backward compatibility.
134     IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
135     IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
136   }
137 };
138 
139 template <> struct MappingTraits<FormatStyle> {
140   static void mapping(IO &IO, FormatStyle &Style) {
141     // When reading, read the language first, we need it for getPredefinedStyle.
142     IO.mapOptional("Language", Style.Language);
143 
144     if (IO.outputting()) {
145       StringRef StylesArray[] = {"LLVM",    "Google", "Chromium",
146                                  "Mozilla", "WebKit", "GNU"};
147       ArrayRef<StringRef> Styles(StylesArray);
148       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
149         StringRef StyleName(Styles[i]);
150         FormatStyle PredefinedStyle;
151         if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
152             Style == PredefinedStyle) {
153           IO.mapOptional("# BasedOnStyle", StyleName);
154           break;
155         }
156       }
157     } else {
158       StringRef BasedOnStyle;
159       IO.mapOptional("BasedOnStyle", BasedOnStyle);
160       if (!BasedOnStyle.empty()) {
161         FormatStyle::LanguageKind OldLanguage = Style.Language;
162         FormatStyle::LanguageKind Language =
163             ((FormatStyle *)IO.getContext())->Language;
164         if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
165           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
166           return;
167         }
168         Style.Language = OldLanguage;
169       }
170     }
171 
172     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
173     IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
174     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
175     IO.mapOptional("AlignOperands", Style.AlignOperands);
176     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
177     IO.mapOptional("AlignConsecutiveAssignments", Style.AlignConsecutiveAssignments);
178     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
179                    Style.AllowAllParametersOfDeclarationOnNextLine);
180     IO.mapOptional("AllowShortBlocksOnASingleLine",
181                    Style.AllowShortBlocksOnASingleLine);
182     IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
183                    Style.AllowShortCaseLabelsOnASingleLine);
184     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
185                    Style.AllowShortIfStatementsOnASingleLine);
186     IO.mapOptional("AllowShortLoopsOnASingleLine",
187                    Style.AllowShortLoopsOnASingleLine);
188     IO.mapOptional("AllowShortFunctionsOnASingleLine",
189                    Style.AllowShortFunctionsOnASingleLine);
190     IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
191                    Style.AlwaysBreakAfterDefinitionReturnType);
192     IO.mapOptional("AlwaysBreakTemplateDeclarations",
193                    Style.AlwaysBreakTemplateDeclarations);
194     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
195                    Style.AlwaysBreakBeforeMultilineStrings);
196     IO.mapOptional("BreakBeforeBinaryOperators",
197                    Style.BreakBeforeBinaryOperators);
198     IO.mapOptional("BreakBeforeTernaryOperators",
199                    Style.BreakBeforeTernaryOperators);
200     IO.mapOptional("BreakConstructorInitializersBeforeComma",
201                    Style.BreakConstructorInitializersBeforeComma);
202     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
203     IO.mapOptional("BinPackArguments", Style.BinPackArguments);
204     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
205     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
206                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
207     IO.mapOptional("ConstructorInitializerIndentWidth",
208                    Style.ConstructorInitializerIndentWidth);
209     IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
210     IO.mapOptional("ExperimentalAutoDetectBinPacking",
211                    Style.ExperimentalAutoDetectBinPacking);
212     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
213     IO.mapOptional("IndentWrappedFunctionNames",
214                    Style.IndentWrappedFunctionNames);
215     IO.mapOptional("IndentFunctionDeclarationAfterType",
216                    Style.IndentWrappedFunctionNames);
217     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
218     IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
219                    Style.KeepEmptyLinesAtTheStartOfBlocks);
220     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
221     IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
222     IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
223     IO.mapOptional("ObjCSpaceBeforeProtocolList",
224                    Style.ObjCSpaceBeforeProtocolList);
225     IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
226                    Style.PenaltyBreakBeforeFirstCallParameter);
227     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
228     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
229     IO.mapOptional("PenaltyBreakFirstLessLess",
230                    Style.PenaltyBreakFirstLessLess);
231     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
232     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
233                    Style.PenaltyReturnTypeOnItsOwnLine);
234     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
235     IO.mapOptional("SpacesBeforeTrailingComments",
236                    Style.SpacesBeforeTrailingComments);
237     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
238     IO.mapOptional("Standard", Style.Standard);
239     IO.mapOptional("IndentWidth", Style.IndentWidth);
240     IO.mapOptional("TabWidth", Style.TabWidth);
241     IO.mapOptional("UseTab", Style.UseTab);
242     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
243     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
244     IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
245     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
246     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
247     IO.mapOptional("SpacesInCStyleCastParentheses",
248                    Style.SpacesInCStyleCastParentheses);
249     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
250     IO.mapOptional("SpacesInContainerLiterals",
251                    Style.SpacesInContainerLiterals);
252     IO.mapOptional("SpaceBeforeAssignmentOperators",
253                    Style.SpaceBeforeAssignmentOperators);
254     IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
255     IO.mapOptional("CommentPragmas", Style.CommentPragmas);
256     IO.mapOptional("ForEachMacros", Style.ForEachMacros);
257 
258     // For backward compatibility.
259     if (!IO.outputting()) {
260       IO.mapOptional("SpaceAfterControlStatementKeyword",
261                      Style.SpaceBeforeParens);
262       IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
263       IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
264     }
265     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
266     IO.mapOptional("DisableFormat", Style.DisableFormat);
267   }
268 };
269 
270 // Allows to read vector<FormatStyle> while keeping default values.
271 // IO.getContext() should contain a pointer to the FormatStyle structure, that
272 // will be used to get default values for missing keys.
273 // If the first element has no Language specified, it will be treated as the
274 // default one for the following elements.
275 template <> struct DocumentListTraits<std::vector<FormatStyle>> {
276   static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
277     return Seq.size();
278   }
279   static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
280                               size_t Index) {
281     if (Index >= Seq.size()) {
282       assert(Index == Seq.size());
283       FormatStyle Template;
284       if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
285         Template = Seq[0];
286       } else {
287         Template = *((const FormatStyle *)IO.getContext());
288         Template.Language = FormatStyle::LK_None;
289       }
290       Seq.resize(Index + 1, Template);
291     }
292     return Seq[Index];
293   }
294 };
295 }
296 }
297 
298 namespace clang {
299 namespace format {
300 
301 const std::error_category &getParseCategory() {
302   static ParseErrorCategory C;
303   return C;
304 }
305 std::error_code make_error_code(ParseError e) {
306   return std::error_code(static_cast<int>(e), getParseCategory());
307 }
308 
309 const char *ParseErrorCategory::name() const LLVM_NOEXCEPT {
310   return "clang-format.parse_error";
311 }
312 
313 std::string ParseErrorCategory::message(int EV) const {
314   switch (static_cast<ParseError>(EV)) {
315   case ParseError::Success:
316     return "Success";
317   case ParseError::Error:
318     return "Invalid argument";
319   case ParseError::Unsuitable:
320     return "Unsuitable";
321   }
322   llvm_unreachable("unexpected parse error");
323 }
324 
325 FormatStyle getLLVMStyle() {
326   FormatStyle LLVMStyle;
327   LLVMStyle.Language = FormatStyle::LK_Cpp;
328   LLVMStyle.AccessModifierOffset = -2;
329   LLVMStyle.AlignEscapedNewlinesLeft = false;
330   LLVMStyle.AlignAfterOpenBracket = true;
331   LLVMStyle.AlignOperands = true;
332   LLVMStyle.AlignTrailingComments = true;
333   LLVMStyle.AlignConsecutiveAssignments = false;
334   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
335   LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
336   LLVMStyle.AllowShortBlocksOnASingleLine = false;
337   LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
338   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
339   LLVMStyle.AllowShortLoopsOnASingleLine = false;
340   LLVMStyle.AlwaysBreakAfterDefinitionReturnType = false;
341   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
342   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
343   LLVMStyle.BinPackParameters = true;
344   LLVMStyle.BinPackArguments = true;
345   LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
346   LLVMStyle.BreakBeforeTernaryOperators = true;
347   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
348   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
349   LLVMStyle.ColumnLimit = 80;
350   LLVMStyle.CommentPragmas = "^ IWYU pragma:";
351   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
352   LLVMStyle.ConstructorInitializerIndentWidth = 4;
353   LLVMStyle.ContinuationIndentWidth = 4;
354   LLVMStyle.Cpp11BracedListStyle = true;
355   LLVMStyle.DerivePointerAlignment = false;
356   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
357   LLVMStyle.ForEachMacros.push_back("foreach");
358   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
359   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
360   LLVMStyle.IndentCaseLabels = false;
361   LLVMStyle.IndentWrappedFunctionNames = false;
362   LLVMStyle.IndentWidth = 2;
363   LLVMStyle.TabWidth = 8;
364   LLVMStyle.MaxEmptyLinesToKeep = 1;
365   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
366   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
367   LLVMStyle.ObjCBlockIndentWidth = 2;
368   LLVMStyle.ObjCSpaceAfterProperty = false;
369   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
370   LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
371   LLVMStyle.SpacesBeforeTrailingComments = 1;
372   LLVMStyle.Standard = FormatStyle::LS_Cpp11;
373   LLVMStyle.UseTab = FormatStyle::UT_Never;
374   LLVMStyle.SpacesInParentheses = false;
375   LLVMStyle.SpacesInSquareBrackets = false;
376   LLVMStyle.SpaceInEmptyParentheses = false;
377   LLVMStyle.SpacesInContainerLiterals = true;
378   LLVMStyle.SpacesInCStyleCastParentheses = false;
379   LLVMStyle.SpaceAfterCStyleCast = false;
380   LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
381   LLVMStyle.SpaceBeforeAssignmentOperators = true;
382   LLVMStyle.SpacesInAngles = false;
383 
384   LLVMStyle.PenaltyBreakComment = 300;
385   LLVMStyle.PenaltyBreakFirstLessLess = 120;
386   LLVMStyle.PenaltyBreakString = 1000;
387   LLVMStyle.PenaltyExcessCharacter = 1000000;
388   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
389   LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
390 
391   LLVMStyle.DisableFormat = false;
392 
393   return LLVMStyle;
394 }
395 
396 FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
397   FormatStyle GoogleStyle = getLLVMStyle();
398   GoogleStyle.Language = Language;
399 
400   GoogleStyle.AccessModifierOffset = -1;
401   GoogleStyle.AlignEscapedNewlinesLeft = true;
402   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
403   GoogleStyle.AllowShortLoopsOnASingleLine = true;
404   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
405   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
406   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
407   GoogleStyle.DerivePointerAlignment = true;
408   GoogleStyle.IndentCaseLabels = true;
409   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
410   GoogleStyle.ObjCSpaceAfterProperty = false;
411   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
412   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
413   GoogleStyle.SpacesBeforeTrailingComments = 2;
414   GoogleStyle.Standard = FormatStyle::LS_Auto;
415 
416   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
417   GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
418 
419   if (Language == FormatStyle::LK_Java) {
420     GoogleStyle.AlignAfterOpenBracket = false;
421     GoogleStyle.AlignOperands = false;
422     GoogleStyle.AlignTrailingComments = false;
423     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
424     GoogleStyle.AllowShortIfStatementsOnASingleLine = false;
425     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
426     GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
427     GoogleStyle.ColumnLimit = 100;
428     GoogleStyle.SpaceAfterCStyleCast = true;
429     GoogleStyle.SpacesBeforeTrailingComments = 1;
430   } else if (Language == FormatStyle::LK_JavaScript) {
431     GoogleStyle.BreakBeforeTernaryOperators = false;
432     GoogleStyle.MaxEmptyLinesToKeep = 3;
433     GoogleStyle.SpacesInContainerLiterals = false;
434     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
435     GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
436   } else if (Language == FormatStyle::LK_Proto) {
437     GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
438     GoogleStyle.SpacesInContainerLiterals = false;
439   }
440 
441   return GoogleStyle;
442 }
443 
444 FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
445   FormatStyle ChromiumStyle = getGoogleStyle(Language);
446   if (Language == FormatStyle::LK_Java) {
447     ChromiumStyle.AllowShortIfStatementsOnASingleLine = true;
448     ChromiumStyle.IndentWidth = 4;
449     ChromiumStyle.ContinuationIndentWidth = 8;
450   } else {
451     ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
452     ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
453     ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
454     ChromiumStyle.AllowShortLoopsOnASingleLine = false;
455     ChromiumStyle.BinPackParameters = false;
456     ChromiumStyle.DerivePointerAlignment = false;
457   }
458   return ChromiumStyle;
459 }
460 
461 FormatStyle getMozillaStyle() {
462   FormatStyle MozillaStyle = getLLVMStyle();
463   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
464   MozillaStyle.Cpp11BracedListStyle = false;
465   MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
466   MozillaStyle.DerivePointerAlignment = true;
467   MozillaStyle.IndentCaseLabels = true;
468   MozillaStyle.ObjCSpaceAfterProperty = true;
469   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
470   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
471   MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
472   MozillaStyle.Standard = FormatStyle::LS_Cpp03;
473   return MozillaStyle;
474 }
475 
476 FormatStyle getWebKitStyle() {
477   FormatStyle Style = getLLVMStyle();
478   Style.AccessModifierOffset = -4;
479   Style.AlignAfterOpenBracket = false;
480   Style.AlignOperands = false;
481   Style.AlignTrailingComments = false;
482   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
483   Style.BreakBeforeBraces = FormatStyle::BS_Stroustrup;
484   Style.BreakConstructorInitializersBeforeComma = true;
485   Style.Cpp11BracedListStyle = false;
486   Style.ColumnLimit = 0;
487   Style.IndentWidth = 4;
488   Style.NamespaceIndentation = FormatStyle::NI_Inner;
489   Style.ObjCBlockIndentWidth = 4;
490   Style.ObjCSpaceAfterProperty = true;
491   Style.PointerAlignment = FormatStyle::PAS_Left;
492   Style.Standard = FormatStyle::LS_Cpp03;
493   return Style;
494 }
495 
496 FormatStyle getGNUStyle() {
497   FormatStyle Style = getLLVMStyle();
498   Style.AlwaysBreakAfterDefinitionReturnType = true;
499   Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
500   Style.BreakBeforeBraces = FormatStyle::BS_GNU;
501   Style.BreakBeforeTernaryOperators = true;
502   Style.Cpp11BracedListStyle = false;
503   Style.ColumnLimit = 79;
504   Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
505   Style.Standard = FormatStyle::LS_Cpp03;
506   return Style;
507 }
508 
509 FormatStyle getNoStyle() {
510   FormatStyle NoStyle = getLLVMStyle();
511   NoStyle.DisableFormat = true;
512   return NoStyle;
513 }
514 
515 bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
516                         FormatStyle *Style) {
517   if (Name.equals_lower("llvm")) {
518     *Style = getLLVMStyle();
519   } else if (Name.equals_lower("chromium")) {
520     *Style = getChromiumStyle(Language);
521   } else if (Name.equals_lower("mozilla")) {
522     *Style = getMozillaStyle();
523   } else if (Name.equals_lower("google")) {
524     *Style = getGoogleStyle(Language);
525   } else if (Name.equals_lower("webkit")) {
526     *Style = getWebKitStyle();
527   } else if (Name.equals_lower("gnu")) {
528     *Style = getGNUStyle();
529   } else if (Name.equals_lower("none")) {
530     *Style = getNoStyle();
531   } else {
532     return false;
533   }
534 
535   Style->Language = Language;
536   return true;
537 }
538 
539 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
540   assert(Style);
541   FormatStyle::LanguageKind Language = Style->Language;
542   assert(Language != FormatStyle::LK_None);
543   if (Text.trim().empty())
544     return make_error_code(ParseError::Error);
545 
546   std::vector<FormatStyle> Styles;
547   llvm::yaml::Input Input(Text);
548   // DocumentListTraits<vector<FormatStyle>> uses the context to get default
549   // values for the fields, keys for which are missing from the configuration.
550   // Mapping also uses the context to get the language to find the correct
551   // base style.
552   Input.setContext(Style);
553   Input >> Styles;
554   if (Input.error())
555     return Input.error();
556 
557   for (unsigned i = 0; i < Styles.size(); ++i) {
558     // Ensures that only the first configuration can skip the Language option.
559     if (Styles[i].Language == FormatStyle::LK_None && i != 0)
560       return make_error_code(ParseError::Error);
561     // Ensure that each language is configured at most once.
562     for (unsigned j = 0; j < i; ++j) {
563       if (Styles[i].Language == Styles[j].Language) {
564         DEBUG(llvm::dbgs()
565               << "Duplicate languages in the config file on positions " << j
566               << " and " << i << "\n");
567         return make_error_code(ParseError::Error);
568       }
569     }
570   }
571   // Look for a suitable configuration starting from the end, so we can
572   // find the configuration for the specific language first, and the default
573   // configuration (which can only be at slot 0) after it.
574   for (int i = Styles.size() - 1; i >= 0; --i) {
575     if (Styles[i].Language == Language ||
576         Styles[i].Language == FormatStyle::LK_None) {
577       *Style = Styles[i];
578       Style->Language = Language;
579       return make_error_code(ParseError::Success);
580     }
581   }
582   return make_error_code(ParseError::Unsuitable);
583 }
584 
585 std::string configurationAsText(const FormatStyle &Style) {
586   std::string Text;
587   llvm::raw_string_ostream Stream(Text);
588   llvm::yaml::Output Output(Stream);
589   // We use the same mapping method for input and output, so we need a non-const
590   // reference here.
591   FormatStyle NonConstStyle = Style;
592   Output << NonConstStyle;
593   return Stream.str();
594 }
595 
596 namespace {
597 
598 class FormatTokenLexer {
599 public:
600   FormatTokenLexer(SourceManager &SourceMgr, FileID ID, FormatStyle &Style,
601                    encoding::Encoding Encoding)
602       : FormatTok(nullptr), IsFirstToken(true), GreaterStashed(false),
603         LessStashed(false), Column(0), TrailingWhitespace(0),
604         SourceMgr(SourceMgr), ID(ID), Style(Style),
605         IdentTable(getFormattingLangOpts(Style)), Keywords(IdentTable),
606         Encoding(Encoding), FirstInLineIndex(0), FormattingDisabled(false) {
607     Lex.reset(new Lexer(ID, SourceMgr.getBuffer(ID), SourceMgr,
608                         getFormattingLangOpts(Style)));
609     Lex->SetKeepWhitespaceMode(true);
610 
611     for (const std::string &ForEachMacro : Style.ForEachMacros)
612       ForEachMacros.push_back(&IdentTable.get(ForEachMacro));
613     std::sort(ForEachMacros.begin(), ForEachMacros.end());
614   }
615 
616   ArrayRef<FormatToken *> lex() {
617     assert(Tokens.empty());
618     assert(FirstInLineIndex == 0);
619     do {
620       Tokens.push_back(getNextToken());
621       tryMergePreviousTokens();
622       if (Tokens.back()->NewlinesBefore > 0 || Tokens.back()->IsMultiline)
623         FirstInLineIndex = Tokens.size() - 1;
624     } while (Tokens.back()->Tok.isNot(tok::eof));
625     return Tokens;
626   }
627 
628   const AdditionalKeywords &getKeywords() { return Keywords; }
629 
630 private:
631   void tryMergePreviousTokens() {
632     if (tryMerge_TMacro())
633       return;
634     if (tryMergeConflictMarkers())
635       return;
636     if (tryMergeLessLess())
637       return;
638 
639     if (Style.Language == FormatStyle::LK_JavaScript) {
640       if (tryMergeJSRegexLiteral())
641         return;
642       if (tryMergeEscapeSequence())
643         return;
644       if (tryMergeTemplateString())
645         return;
646 
647       static const tok::TokenKind JSIdentity[] = {tok::equalequal, tok::equal};
648       static const tok::TokenKind JSNotIdentity[] = {tok::exclaimequal,
649                                                      tok::equal};
650       static const tok::TokenKind JSShiftEqual[] = {tok::greater, tok::greater,
651                                                     tok::greaterequal};
652       static const tok::TokenKind JSRightArrow[] = {tok::equal, tok::greater};
653       // FIXME: We probably need to change token type to mimic operator with the
654       // correct priority.
655       if (tryMergeTokens(JSIdentity))
656         return;
657       if (tryMergeTokens(JSNotIdentity))
658         return;
659       if (tryMergeTokens(JSShiftEqual))
660         return;
661       if (tryMergeTokens(JSRightArrow))
662         return;
663     }
664   }
665 
666   bool tryMergeLessLess() {
667     // Merge X,less,less,Y into X,lessless,Y unless X or Y is less.
668     if (Tokens.size() < 3)
669       return false;
670 
671     bool FourthTokenIsLess = false;
672     if (Tokens.size() > 3)
673       FourthTokenIsLess = (Tokens.end() - 4)[0]->is(tok::less);
674 
675     auto First = Tokens.end() - 3;
676     if (First[2]->is(tok::less) || First[1]->isNot(tok::less) ||
677         First[0]->isNot(tok::less) || FourthTokenIsLess)
678       return false;
679 
680     // Only merge if there currently is no whitespace between the two "<".
681     if (First[1]->WhitespaceRange.getBegin() !=
682         First[1]->WhitespaceRange.getEnd())
683       return false;
684 
685     First[0]->Tok.setKind(tok::lessless);
686     First[0]->TokenText = "<<";
687     First[0]->ColumnWidth += 1;
688     Tokens.erase(Tokens.end() - 2);
689     return true;
690   }
691 
692   bool tryMergeTokens(ArrayRef<tok::TokenKind> Kinds) {
693     if (Tokens.size() < Kinds.size())
694       return false;
695 
696     SmallVectorImpl<FormatToken *>::const_iterator First =
697         Tokens.end() - Kinds.size();
698     if (!First[0]->is(Kinds[0]))
699       return false;
700     unsigned AddLength = 0;
701     for (unsigned i = 1; i < Kinds.size(); ++i) {
702       if (!First[i]->is(Kinds[i]) ||
703           First[i]->WhitespaceRange.getBegin() !=
704               First[i]->WhitespaceRange.getEnd())
705         return false;
706       AddLength += First[i]->TokenText.size();
707     }
708     Tokens.resize(Tokens.size() - Kinds.size() + 1);
709     First[0]->TokenText = StringRef(First[0]->TokenText.data(),
710                                     First[0]->TokenText.size() + AddLength);
711     First[0]->ColumnWidth += AddLength;
712     return true;
713   }
714 
715   // Tries to merge an escape sequence, i.e. a "\\" and the following
716   // character. Use e.g. inside JavaScript regex literals.
717   bool tryMergeEscapeSequence() {
718     if (Tokens.size() < 2)
719       return false;
720     FormatToken *Previous = Tokens[Tokens.size() - 2];
721     if (Previous->isNot(tok::unknown) || Previous->TokenText != "\\")
722       return false;
723     ++Previous->ColumnWidth;
724     StringRef Text = Previous->TokenText;
725     Previous->TokenText = StringRef(Text.data(), Text.size() + 1);
726     resetLexer(SourceMgr.getFileOffset(Tokens.back()->Tok.getLocation()) + 1);
727     Tokens.resize(Tokens.size() - 1);
728     Column = Previous->OriginalColumn + Previous->ColumnWidth;
729     return true;
730   }
731 
732   // Try to determine whether the current token ends a JavaScript regex literal.
733   // We heuristically assume that this is a regex literal if we find two
734   // unescaped slashes on a line and the token before the first slash is one of
735   // "(;,{}![:?", a binary operator or 'return', as those cannot be followed by
736   // a division.
737   bool tryMergeJSRegexLiteral() {
738     if (Tokens.size() < 2)
739       return false;
740     // If a regex literal ends in "\//", this gets represented by an unknown
741     // token "\" and a comment.
742     bool MightEndWithEscapedSlash =
743         Tokens.back()->is(tok::comment) &&
744         Tokens.back()->TokenText.startswith("//") &&
745         Tokens[Tokens.size() - 2]->TokenText == "\\";
746     if (!MightEndWithEscapedSlash &&
747         (Tokens.back()->isNot(tok::slash) ||
748          (Tokens[Tokens.size() - 2]->is(tok::unknown) &&
749           Tokens[Tokens.size() - 2]->TokenText == "\\")))
750       return false;
751     unsigned TokenCount = 0;
752     unsigned LastColumn = Tokens.back()->OriginalColumn;
753     for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; ++I) {
754       ++TokenCount;
755       if (I[0]->is(tok::slash) && I + 1 != E &&
756           (I[1]->isOneOf(tok::l_paren, tok::semi, tok::l_brace, tok::r_brace,
757                          tok::exclaim, tok::l_square, tok::colon, tok::comma,
758                          tok::question, tok::kw_return) ||
759            I[1]->isBinaryOperator())) {
760         if (MightEndWithEscapedSlash) {
761           // This regex literal ends in '\//'. Skip past the '//' of the last
762           // token and re-start lexing from there.
763           SourceLocation Loc = Tokens.back()->Tok.getLocation();
764           resetLexer(SourceMgr.getFileOffset(Loc) + 2);
765         }
766         Tokens.resize(Tokens.size() - TokenCount);
767         Tokens.back()->Tok.setKind(tok::unknown);
768         Tokens.back()->Type = TT_RegexLiteral;
769         Tokens.back()->ColumnWidth += LastColumn - I[0]->OriginalColumn;
770         return true;
771       }
772 
773       // There can't be a newline inside a regex literal.
774       if (I[0]->NewlinesBefore > 0)
775         return false;
776     }
777     return false;
778   }
779 
780   bool tryMergeTemplateString() {
781     if (Tokens.size() < 2)
782       return false;
783 
784     FormatToken *EndBacktick = Tokens.back();
785     // Backticks get lexed as tok:unknown tokens. If a template string contains
786     // a comment start, it gets lexed as a tok::comment, or tok::unknown if
787     // unterminated.
788     if (!EndBacktick->isOneOf(tok::comment, tok::unknown))
789       return false;
790     size_t CommentBacktickPos = EndBacktick->TokenText.find('`');
791     // Unknown token that's not actually a backtick, or a comment that doesn't
792     // contain a backtick.
793     if (CommentBacktickPos == StringRef::npos)
794       return false;
795 
796     unsigned TokenCount = 0;
797     bool IsMultiline = false;
798     unsigned EndColumnInFirstLine = 0;
799     for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; I++) {
800       ++TokenCount;
801       if (I[0]->NewlinesBefore > 0 || I[0]->IsMultiline)
802         IsMultiline = true;
803 
804       // If there was a preceding template string, this must be the start of a
805       // template string, not the end.
806       if (I[0]->is(TT_TemplateString))
807         return false;
808 
809       if (I[0]->isNot(tok::unknown) || I[0]->TokenText != "`") {
810         // Keep track of the rhs offset of the last token to wrap across lines -
811         // its the rhs offset of the first line of the template string, used to
812         // determine its width.
813         if (I[0]->IsMultiline)
814           EndColumnInFirstLine = I[0]->OriginalColumn + I[0]->ColumnWidth;
815         // If the token has newlines, the token before it (if it exists) is the
816         // rhs end of the previous line.
817         if (I[0]->NewlinesBefore > 0 && (I + 1 != E))
818           EndColumnInFirstLine = I[1]->OriginalColumn + I[1]->ColumnWidth;
819 
820         continue;
821       }
822 
823       Tokens.resize(Tokens.size() - TokenCount);
824       Tokens.back()->Type = TT_TemplateString;
825       const char *EndOffset =
826           EndBacktick->TokenText.data() + 1 + CommentBacktickPos;
827       if (CommentBacktickPos != 0) {
828         // If the backtick was not the first character (e.g. in a comment),
829         // re-lex after the backtick position.
830         SourceLocation Loc = EndBacktick->Tok.getLocation();
831         resetLexer(SourceMgr.getFileOffset(Loc) + CommentBacktickPos + 1);
832       }
833       Tokens.back()->TokenText =
834           StringRef(Tokens.back()->TokenText.data(),
835                     EndOffset - Tokens.back()->TokenText.data());
836       if (IsMultiline) {
837         // ColumnWidth is from backtick to last token in line.
838         // LastLineColumnWidth is 0 to backtick.
839         // x = `some content
840         //     until here`;
841         Tokens.back()->ColumnWidth =
842             EndColumnInFirstLine - Tokens.back()->OriginalColumn;
843         Tokens.back()->LastLineColumnWidth = EndBacktick->OriginalColumn;
844         Tokens.back()->IsMultiline = true;
845       } else {
846         // Token simply spans from start to end, +1 for the ` itself.
847         Tokens.back()->ColumnWidth =
848             EndBacktick->OriginalColumn - Tokens.back()->OriginalColumn + 1;
849       }
850       return true;
851     }
852     return false;
853   }
854 
855   bool tryMerge_TMacro() {
856     if (Tokens.size() < 4)
857       return false;
858     FormatToken *Last = Tokens.back();
859     if (!Last->is(tok::r_paren))
860       return false;
861 
862     FormatToken *String = Tokens[Tokens.size() - 2];
863     if (!String->is(tok::string_literal) || String->IsMultiline)
864       return false;
865 
866     if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
867       return false;
868 
869     FormatToken *Macro = Tokens[Tokens.size() - 4];
870     if (Macro->TokenText != "_T")
871       return false;
872 
873     const char *Start = Macro->TokenText.data();
874     const char *End = Last->TokenText.data() + Last->TokenText.size();
875     String->TokenText = StringRef(Start, End - Start);
876     String->IsFirst = Macro->IsFirst;
877     String->LastNewlineOffset = Macro->LastNewlineOffset;
878     String->WhitespaceRange = Macro->WhitespaceRange;
879     String->OriginalColumn = Macro->OriginalColumn;
880     String->ColumnWidth = encoding::columnWidthWithTabs(
881         String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
882     String->NewlinesBefore = Macro->NewlinesBefore;
883     String->HasUnescapedNewline = Macro->HasUnescapedNewline;
884 
885     Tokens.pop_back();
886     Tokens.pop_back();
887     Tokens.pop_back();
888     Tokens.back() = String;
889     return true;
890   }
891 
892   bool tryMergeConflictMarkers() {
893     if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(tok::eof))
894       return false;
895 
896     // Conflict lines look like:
897     // <marker> <text from the vcs>
898     // For example:
899     // >>>>>>> /file/in/file/system at revision 1234
900     //
901     // We merge all tokens in a line that starts with a conflict marker
902     // into a single token with a special token type that the unwrapped line
903     // parser will use to correctly rebuild the underlying code.
904 
905     FileID ID;
906     // Get the position of the first token in the line.
907     unsigned FirstInLineOffset;
908     std::tie(ID, FirstInLineOffset) = SourceMgr.getDecomposedLoc(
909         Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
910     StringRef Buffer = SourceMgr.getBuffer(ID)->getBuffer();
911     // Calculate the offset of the start of the current line.
912     auto LineOffset = Buffer.rfind('\n', FirstInLineOffset);
913     if (LineOffset == StringRef::npos) {
914       LineOffset = 0;
915     } else {
916       ++LineOffset;
917     }
918 
919     auto FirstSpace = Buffer.find_first_of(" \n", LineOffset);
920     StringRef LineStart;
921     if (FirstSpace == StringRef::npos) {
922       LineStart = Buffer.substr(LineOffset);
923     } else {
924       LineStart = Buffer.substr(LineOffset, FirstSpace - LineOffset);
925     }
926 
927     TokenType Type = TT_Unknown;
928     if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
929       Type = TT_ConflictStart;
930     } else if (LineStart == "|||||||" || LineStart == "=======" ||
931                LineStart == "====") {
932       Type = TT_ConflictAlternative;
933     } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
934       Type = TT_ConflictEnd;
935     }
936 
937     if (Type != TT_Unknown) {
938       FormatToken *Next = Tokens.back();
939 
940       Tokens.resize(FirstInLineIndex + 1);
941       // We do not need to build a complete token here, as we will skip it
942       // during parsing anyway (as we must not touch whitespace around conflict
943       // markers).
944       Tokens.back()->Type = Type;
945       Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
946 
947       Tokens.push_back(Next);
948       return true;
949     }
950 
951     return false;
952   }
953 
954   FormatToken *getStashedToken() {
955     // Create a synthesized second '>' or '<' token.
956     Token Tok = FormatTok->Tok;
957     StringRef TokenText = FormatTok->TokenText;
958 
959     unsigned OriginalColumn = FormatTok->OriginalColumn;
960     FormatTok = new (Allocator.Allocate()) FormatToken;
961     FormatTok->Tok = Tok;
962     SourceLocation TokLocation =
963         FormatTok->Tok.getLocation().getLocWithOffset(Tok.getLength() - 1);
964     FormatTok->Tok.setLocation(TokLocation);
965     FormatTok->WhitespaceRange = SourceRange(TokLocation, TokLocation);
966     FormatTok->TokenText = TokenText;
967     FormatTok->ColumnWidth = 1;
968     FormatTok->OriginalColumn = OriginalColumn + 1;
969 
970     return FormatTok;
971   }
972 
973   FormatToken *getNextToken() {
974     if (GreaterStashed) {
975       GreaterStashed = false;
976       return getStashedToken();
977     }
978     if (LessStashed) {
979       LessStashed = false;
980       return getStashedToken();
981     }
982 
983     FormatTok = new (Allocator.Allocate()) FormatToken;
984     readRawToken(*FormatTok);
985     SourceLocation WhitespaceStart =
986         FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
987     FormatTok->IsFirst = IsFirstToken;
988     IsFirstToken = false;
989 
990     // Consume and record whitespace until we find a significant token.
991     unsigned WhitespaceLength = TrailingWhitespace;
992     while (FormatTok->Tok.is(tok::unknown)) {
993       // FIXME: This miscounts tok:unknown tokens that are not just
994       // whitespace, e.g. a '`' character.
995       for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) {
996         switch (FormatTok->TokenText[i]) {
997         case '\n':
998           ++FormatTok->NewlinesBefore;
999           // FIXME: This is technically incorrect, as it could also
1000           // be a literal backslash at the end of the line.
1001           if (i == 0 || (FormatTok->TokenText[i - 1] != '\\' &&
1002                          (FormatTok->TokenText[i - 1] != '\r' || i == 1 ||
1003                           FormatTok->TokenText[i - 2] != '\\')))
1004             FormatTok->HasUnescapedNewline = true;
1005           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1006           Column = 0;
1007           break;
1008         case '\r':
1009           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1010           Column = 0;
1011           break;
1012         case '\f':
1013         case '\v':
1014           Column = 0;
1015           break;
1016         case ' ':
1017           ++Column;
1018           break;
1019         case '\t':
1020           Column += Style.TabWidth - Column % Style.TabWidth;
1021           break;
1022         case '\\':
1023           if (i + 1 == e || (FormatTok->TokenText[i + 1] != '\r' &&
1024                              FormatTok->TokenText[i + 1] != '\n'))
1025             FormatTok->Type = TT_ImplicitStringLiteral;
1026           break;
1027         default:
1028           FormatTok->Type = TT_ImplicitStringLiteral;
1029           ++Column;
1030           break;
1031         }
1032       }
1033 
1034       if (FormatTok->is(TT_ImplicitStringLiteral))
1035         break;
1036       WhitespaceLength += FormatTok->Tok.getLength();
1037 
1038       readRawToken(*FormatTok);
1039     }
1040 
1041     // In case the token starts with escaped newlines, we want to
1042     // take them into account as whitespace - this pattern is quite frequent
1043     // in macro definitions.
1044     // FIXME: Add a more explicit test.
1045     while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
1046            FormatTok->TokenText[1] == '\n') {
1047       ++FormatTok->NewlinesBefore;
1048       WhitespaceLength += 2;
1049       Column = 0;
1050       FormatTok->TokenText = FormatTok->TokenText.substr(2);
1051     }
1052 
1053     FormatTok->WhitespaceRange = SourceRange(
1054         WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1055 
1056     FormatTok->OriginalColumn = Column;
1057 
1058     TrailingWhitespace = 0;
1059     if (FormatTok->Tok.is(tok::comment)) {
1060       // FIXME: Add the trimmed whitespace to Column.
1061       StringRef UntrimmedText = FormatTok->TokenText;
1062       FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
1063       TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1064     } else if (FormatTok->Tok.is(tok::raw_identifier)) {
1065       IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
1066       FormatTok->Tok.setIdentifierInfo(&Info);
1067       FormatTok->Tok.setKind(Info.getTokenID());
1068       if (Style.Language == FormatStyle::LK_Java &&
1069           FormatTok->isOneOf(tok::kw_struct, tok::kw_union, tok::kw_delete)) {
1070         FormatTok->Tok.setKind(tok::identifier);
1071         FormatTok->Tok.setIdentifierInfo(nullptr);
1072       }
1073     } else if (FormatTok->Tok.is(tok::greatergreater)) {
1074       FormatTok->Tok.setKind(tok::greater);
1075       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1076       GreaterStashed = true;
1077     } else if (FormatTok->Tok.is(tok::lessless)) {
1078       FormatTok->Tok.setKind(tok::less);
1079       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1080       LessStashed = true;
1081     }
1082 
1083     // Now FormatTok is the next non-whitespace token.
1084 
1085     StringRef Text = FormatTok->TokenText;
1086     size_t FirstNewlinePos = Text.find('\n');
1087     if (FirstNewlinePos == StringRef::npos) {
1088       // FIXME: ColumnWidth actually depends on the start column, we need to
1089       // take this into account when the token is moved.
1090       FormatTok->ColumnWidth =
1091           encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
1092       Column += FormatTok->ColumnWidth;
1093     } else {
1094       FormatTok->IsMultiline = true;
1095       // FIXME: ColumnWidth actually depends on the start column, we need to
1096       // take this into account when the token is moved.
1097       FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1098           Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
1099 
1100       // The last line of the token always starts in column 0.
1101       // Thus, the length can be precomputed even in the presence of tabs.
1102       FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1103           Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
1104           Encoding);
1105       Column = FormatTok->LastLineColumnWidth;
1106     }
1107 
1108     FormatTok->IsForEachMacro =
1109         std::binary_search(ForEachMacros.begin(), ForEachMacros.end(),
1110                            FormatTok->Tok.getIdentifierInfo());
1111 
1112     return FormatTok;
1113   }
1114 
1115   FormatToken *FormatTok;
1116   bool IsFirstToken;
1117   bool GreaterStashed, LessStashed;
1118   unsigned Column;
1119   unsigned TrailingWhitespace;
1120   std::unique_ptr<Lexer> Lex;
1121   SourceManager &SourceMgr;
1122   FileID ID;
1123   FormatStyle &Style;
1124   IdentifierTable IdentTable;
1125   AdditionalKeywords Keywords;
1126   encoding::Encoding Encoding;
1127   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
1128   // Index (in 'Tokens') of the last token that starts a new line.
1129   unsigned FirstInLineIndex;
1130   SmallVector<FormatToken *, 16> Tokens;
1131   SmallVector<IdentifierInfo *, 8> ForEachMacros;
1132 
1133   bool FormattingDisabled;
1134 
1135   void readRawToken(FormatToken &Tok) {
1136     Lex->LexFromRawLexer(Tok.Tok);
1137     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
1138                               Tok.Tok.getLength());
1139     // For formatting, treat unterminated string literals like normal string
1140     // literals.
1141     if (Tok.is(tok::unknown)) {
1142       if (!Tok.TokenText.empty() && Tok.TokenText[0] == '"') {
1143         Tok.Tok.setKind(tok::string_literal);
1144         Tok.IsUnterminatedLiteral = true;
1145       } else if (Style.Language == FormatStyle::LK_JavaScript &&
1146                  Tok.TokenText == "''") {
1147         Tok.Tok.setKind(tok::char_constant);
1148       }
1149     }
1150 
1151     if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format on" ||
1152                                  Tok.TokenText == "/* clang-format on */")) {
1153       FormattingDisabled = false;
1154     }
1155 
1156     Tok.Finalized = FormattingDisabled;
1157 
1158     if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format off" ||
1159                                  Tok.TokenText == "/* clang-format off */")) {
1160       FormattingDisabled = true;
1161     }
1162   }
1163 
1164   void resetLexer(unsigned Offset) {
1165     StringRef Buffer = SourceMgr.getBufferData(ID);
1166     Lex.reset(new Lexer(SourceMgr.getLocForStartOfFile(ID),
1167                         getFormattingLangOpts(Style), Buffer.begin(),
1168                         Buffer.begin() + Offset, Buffer.end()));
1169     Lex->SetKeepWhitespaceMode(true);
1170   }
1171 };
1172 
1173 static StringRef getLanguageName(FormatStyle::LanguageKind Language) {
1174   switch (Language) {
1175   case FormatStyle::LK_Cpp:
1176     return "C++";
1177   case FormatStyle::LK_Java:
1178     return "Java";
1179   case FormatStyle::LK_JavaScript:
1180     return "JavaScript";
1181   case FormatStyle::LK_Proto:
1182     return "Proto";
1183   default:
1184     return "Unknown";
1185   }
1186 }
1187 
1188 class Formatter : public UnwrappedLineConsumer {
1189 public:
1190   Formatter(const FormatStyle &Style, SourceManager &SourceMgr, FileID ID,
1191             ArrayRef<CharSourceRange> Ranges)
1192       : Style(Style), ID(ID), SourceMgr(SourceMgr),
1193         Whitespaces(SourceMgr, Style,
1194                     inputUsesCRLF(SourceMgr.getBufferData(ID))),
1195         Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1),
1196         Encoding(encoding::detectEncoding(SourceMgr.getBufferData(ID))) {
1197     DEBUG(llvm::dbgs() << "File encoding: "
1198                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
1199                                                                : "unknown")
1200                        << "\n");
1201     DEBUG(llvm::dbgs() << "Language: " << getLanguageName(Style.Language)
1202                        << "\n");
1203   }
1204 
1205   tooling::Replacements format() {
1206     tooling::Replacements Result;
1207     FormatTokenLexer Tokens(SourceMgr, ID, Style, Encoding);
1208 
1209     UnwrappedLineParser Parser(Style, Tokens.getKeywords(), Tokens.lex(),
1210                                *this);
1211     bool StructuralError = Parser.parse();
1212     assert(UnwrappedLines.rbegin()->empty());
1213     for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
1214          ++Run) {
1215       DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
1216       SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1217       for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
1218         AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
1219       }
1220       tooling::Replacements RunResult =
1221           format(AnnotatedLines, StructuralError, Tokens);
1222       DEBUG({
1223         llvm::dbgs() << "Replacements for run " << Run << ":\n";
1224         for (tooling::Replacements::iterator I = RunResult.begin(),
1225                                              E = RunResult.end();
1226              I != E; ++I) {
1227           llvm::dbgs() << I->toString() << "\n";
1228         }
1229       });
1230       for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1231         delete AnnotatedLines[i];
1232       }
1233       Result.insert(RunResult.begin(), RunResult.end());
1234       Whitespaces.reset();
1235     }
1236     return Result;
1237   }
1238 
1239   tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1240                                bool StructuralError, FormatTokenLexer &Tokens) {
1241     TokenAnnotator Annotator(Style, Tokens.getKeywords());
1242     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1243       Annotator.annotate(*AnnotatedLines[i]);
1244     }
1245     deriveLocalStyle(AnnotatedLines);
1246     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1247       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1248     }
1249     computeAffectedLines(AnnotatedLines.begin(), AnnotatedLines.end());
1250 
1251     Annotator.setCommentLineLevels(AnnotatedLines);
1252     ContinuationIndenter Indenter(Style, Tokens.getKeywords(), SourceMgr,
1253                                   Whitespaces, Encoding,
1254                                   BinPackInconclusiveFunctions);
1255     UnwrappedLineFormatter Formatter(&Indenter, &Whitespaces, Style,
1256                                      Tokens.getKeywords());
1257     Formatter.format(AnnotatedLines, /*DryRun=*/false);
1258     return Whitespaces.generateReplacements();
1259   }
1260 
1261 private:
1262   // Determines which lines are affected by the SourceRanges given as input.
1263   // Returns \c true if at least one line between I and E or one of their
1264   // children is affected.
1265   bool computeAffectedLines(SmallVectorImpl<AnnotatedLine *>::iterator I,
1266                             SmallVectorImpl<AnnotatedLine *>::iterator E) {
1267     bool SomeLineAffected = false;
1268     const AnnotatedLine *PreviousLine = nullptr;
1269     while (I != E) {
1270       AnnotatedLine *Line = *I;
1271       Line->LeadingEmptyLinesAffected = affectsLeadingEmptyLines(*Line->First);
1272 
1273       // If a line is part of a preprocessor directive, it needs to be formatted
1274       // if any token within the directive is affected.
1275       if (Line->InPPDirective) {
1276         FormatToken *Last = Line->Last;
1277         SmallVectorImpl<AnnotatedLine *>::iterator PPEnd = I + 1;
1278         while (PPEnd != E && !(*PPEnd)->First->HasUnescapedNewline) {
1279           Last = (*PPEnd)->Last;
1280           ++PPEnd;
1281         }
1282 
1283         if (affectsTokenRange(*Line->First, *Last,
1284                               /*IncludeLeadingNewlines=*/false)) {
1285           SomeLineAffected = true;
1286           markAllAsAffected(I, PPEnd);
1287         }
1288         I = PPEnd;
1289         continue;
1290       }
1291 
1292       if (nonPPLineAffected(Line, PreviousLine))
1293         SomeLineAffected = true;
1294 
1295       PreviousLine = Line;
1296       ++I;
1297     }
1298     return SomeLineAffected;
1299   }
1300 
1301   // Determines whether 'Line' is affected by the SourceRanges given as input.
1302   // Returns \c true if line or one if its children is affected.
1303   bool nonPPLineAffected(AnnotatedLine *Line,
1304                          const AnnotatedLine *PreviousLine) {
1305     bool SomeLineAffected = false;
1306     Line->ChildrenAffected =
1307         computeAffectedLines(Line->Children.begin(), Line->Children.end());
1308     if (Line->ChildrenAffected)
1309       SomeLineAffected = true;
1310 
1311     // Stores whether one of the line's tokens is directly affected.
1312     bool SomeTokenAffected = false;
1313     // Stores whether we need to look at the leading newlines of the next token
1314     // in order to determine whether it was affected.
1315     bool IncludeLeadingNewlines = false;
1316 
1317     // Stores whether the first child line of any of this line's tokens is
1318     // affected.
1319     bool SomeFirstChildAffected = false;
1320 
1321     for (FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
1322       // Determine whether 'Tok' was affected.
1323       if (affectsTokenRange(*Tok, *Tok, IncludeLeadingNewlines))
1324         SomeTokenAffected = true;
1325 
1326       // Determine whether the first child of 'Tok' was affected.
1327       if (!Tok->Children.empty() && Tok->Children.front()->Affected)
1328         SomeFirstChildAffected = true;
1329 
1330       IncludeLeadingNewlines = Tok->Children.empty();
1331     }
1332 
1333     // Was this line moved, i.e. has it previously been on the same line as an
1334     // affected line?
1335     bool LineMoved = PreviousLine && PreviousLine->Affected &&
1336                      Line->First->NewlinesBefore == 0;
1337 
1338     bool IsContinuedComment =
1339         Line->First->is(tok::comment) && Line->First->Next == nullptr &&
1340         Line->First->NewlinesBefore < 2 && PreviousLine &&
1341         PreviousLine->Affected && PreviousLine->Last->is(tok::comment);
1342 
1343     if (SomeTokenAffected || SomeFirstChildAffected || LineMoved ||
1344         IsContinuedComment) {
1345       Line->Affected = true;
1346       SomeLineAffected = true;
1347     }
1348     return SomeLineAffected;
1349   }
1350 
1351   // Marks all lines between I and E as well as all their children as affected.
1352   void markAllAsAffected(SmallVectorImpl<AnnotatedLine *>::iterator I,
1353                          SmallVectorImpl<AnnotatedLine *>::iterator E) {
1354     while (I != E) {
1355       (*I)->Affected = true;
1356       markAllAsAffected((*I)->Children.begin(), (*I)->Children.end());
1357       ++I;
1358     }
1359   }
1360 
1361   // Returns true if the range from 'First' to 'Last' intersects with one of the
1362   // input ranges.
1363   bool affectsTokenRange(const FormatToken &First, const FormatToken &Last,
1364                          bool IncludeLeadingNewlines) {
1365     SourceLocation Start = First.WhitespaceRange.getBegin();
1366     if (!IncludeLeadingNewlines)
1367       Start = Start.getLocWithOffset(First.LastNewlineOffset);
1368     SourceLocation End = Last.getStartOfNonWhitespace();
1369     End = End.getLocWithOffset(Last.TokenText.size());
1370     CharSourceRange Range = CharSourceRange::getCharRange(Start, End);
1371     return affectsCharSourceRange(Range);
1372   }
1373 
1374   // Returns true if one of the input ranges intersect the leading empty lines
1375   // before 'Tok'.
1376   bool affectsLeadingEmptyLines(const FormatToken &Tok) {
1377     CharSourceRange EmptyLineRange = CharSourceRange::getCharRange(
1378         Tok.WhitespaceRange.getBegin(),
1379         Tok.WhitespaceRange.getBegin().getLocWithOffset(Tok.LastNewlineOffset));
1380     return affectsCharSourceRange(EmptyLineRange);
1381   }
1382 
1383   // Returns true if 'Range' intersects with one of the input ranges.
1384   bool affectsCharSourceRange(const CharSourceRange &Range) {
1385     for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
1386                                                           E = Ranges.end();
1387          I != E; ++I) {
1388       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
1389           !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
1390         return true;
1391     }
1392     return false;
1393   }
1394 
1395   static bool inputUsesCRLF(StringRef Text) {
1396     return Text.count('\r') * 2 > Text.count('\n');
1397   }
1398 
1399   void
1400   deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1401     unsigned CountBoundToVariable = 0;
1402     unsigned CountBoundToType = 0;
1403     bool HasCpp03IncompatibleFormat = false;
1404     bool HasBinPackedFunction = false;
1405     bool HasOnePerLineFunction = false;
1406     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1407       if (!AnnotatedLines[i]->First->Next)
1408         continue;
1409       FormatToken *Tok = AnnotatedLines[i]->First->Next;
1410       while (Tok->Next) {
1411         if (Tok->is(TT_PointerOrReference)) {
1412           bool SpacesBefore =
1413               Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1414           bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
1415                              Tok->Next->WhitespaceRange.getEnd();
1416           if (SpacesBefore && !SpacesAfter)
1417             ++CountBoundToVariable;
1418           else if (!SpacesBefore && SpacesAfter)
1419             ++CountBoundToType;
1420         }
1421 
1422         if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1423           if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
1424             HasCpp03IncompatibleFormat = true;
1425           if (Tok->is(TT_TemplateCloser) &&
1426               Tok->Previous->is(TT_TemplateCloser))
1427             HasCpp03IncompatibleFormat = true;
1428         }
1429 
1430         if (Tok->PackingKind == PPK_BinPacked)
1431           HasBinPackedFunction = true;
1432         if (Tok->PackingKind == PPK_OnePerLine)
1433           HasOnePerLineFunction = true;
1434 
1435         Tok = Tok->Next;
1436       }
1437     }
1438     if (Style.DerivePointerAlignment) {
1439       if (CountBoundToType > CountBoundToVariable)
1440         Style.PointerAlignment = FormatStyle::PAS_Left;
1441       else if (CountBoundToType < CountBoundToVariable)
1442         Style.PointerAlignment = FormatStyle::PAS_Right;
1443     }
1444     if (Style.Standard == FormatStyle::LS_Auto) {
1445       Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
1446                                                   : FormatStyle::LS_Cpp03;
1447     }
1448     BinPackInconclusiveFunctions =
1449         HasBinPackedFunction || !HasOnePerLineFunction;
1450   }
1451 
1452   void consumeUnwrappedLine(const UnwrappedLine &TheLine) override {
1453     assert(!UnwrappedLines.empty());
1454     UnwrappedLines.back().push_back(TheLine);
1455   }
1456 
1457   void finishRun() override {
1458     UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
1459   }
1460 
1461   FormatStyle Style;
1462   FileID ID;
1463   SourceManager &SourceMgr;
1464   WhitespaceManager Whitespaces;
1465   SmallVector<CharSourceRange, 8> Ranges;
1466   SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
1467 
1468   encoding::Encoding Encoding;
1469   bool BinPackInconclusiveFunctions;
1470 };
1471 
1472 } // end anonymous namespace
1473 
1474 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1475                                SourceManager &SourceMgr,
1476                                ArrayRef<CharSourceRange> Ranges) {
1477   if (Style.DisableFormat)
1478     return tooling::Replacements();
1479   return reformat(Style, SourceMgr,
1480                   SourceMgr.getFileID(Lex.getSourceLocation()), Ranges);
1481 }
1482 
1483 tooling::Replacements reformat(const FormatStyle &Style,
1484                                SourceManager &SourceMgr, FileID ID,
1485                                ArrayRef<CharSourceRange> Ranges) {
1486   if (Style.DisableFormat)
1487     return tooling::Replacements();
1488   Formatter formatter(Style, SourceMgr, ID, Ranges);
1489   return formatter.format();
1490 }
1491 
1492 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1493                                ArrayRef<tooling::Range> Ranges,
1494                                StringRef FileName) {
1495   if (Style.DisableFormat)
1496     return tooling::Replacements();
1497 
1498   FileManager Files((FileSystemOptions()));
1499   DiagnosticsEngine Diagnostics(
1500       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1501       new DiagnosticOptions);
1502   SourceManager SourceMgr(Diagnostics, Files);
1503   std::unique_ptr<llvm::MemoryBuffer> Buf =
1504       llvm::MemoryBuffer::getMemBuffer(Code, FileName);
1505   const clang::FileEntry *Entry =
1506       Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
1507   SourceMgr.overrideFileContents(Entry, std::move(Buf));
1508   FileID ID =
1509       SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
1510   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1511   std::vector<CharSourceRange> CharRanges;
1512   for (const tooling::Range &Range : Ranges) {
1513     SourceLocation Start = StartOfFile.getLocWithOffset(Range.getOffset());
1514     SourceLocation End = Start.getLocWithOffset(Range.getLength());
1515     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1516   }
1517   return reformat(Style, SourceMgr, ID, CharRanges);
1518 }
1519 
1520 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
1521   LangOptions LangOpts;
1522   LangOpts.CPlusPlus = 1;
1523   LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1524   LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1525   LangOpts.LineComment = 1;
1526   bool AlternativeOperators = Style.Language == FormatStyle::LK_Cpp;
1527   LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
1528   LangOpts.Bool = 1;
1529   LangOpts.ObjC1 = 1;
1530   LangOpts.ObjC2 = 1;
1531   LangOpts.MicrosoftExt = 1; // To get kw___try, kw___finally.
1532   return LangOpts;
1533 }
1534 
1535 const char *StyleOptionHelpDescription =
1536     "Coding style, currently supports:\n"
1537     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1538     "Use -style=file to load style configuration from\n"
1539     ".clang-format file located in one of the parent\n"
1540     "directories of the source file (or current\n"
1541     "directory for stdin).\n"
1542     "Use -style=\"{key: value, ...}\" to set specific\n"
1543     "parameters, e.g.:\n"
1544     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1545 
1546 static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
1547   if (FileName.endswith(".java")) {
1548     return FormatStyle::LK_Java;
1549   } else if (FileName.endswith_lower(".js") || FileName.endswith_lower(".ts")) {
1550     // JavaScript or TypeScript.
1551     return FormatStyle::LK_JavaScript;
1552   } else if (FileName.endswith_lower(".proto") ||
1553              FileName.endswith_lower(".protodevel")) {
1554     return FormatStyle::LK_Proto;
1555   }
1556   return FormatStyle::LK_Cpp;
1557 }
1558 
1559 FormatStyle getStyle(StringRef StyleName, StringRef FileName,
1560                      StringRef FallbackStyle) {
1561   FormatStyle Style = getLLVMStyle();
1562   Style.Language = getLanguageByFileName(FileName);
1563   if (!getPredefinedStyle(FallbackStyle, Style.Language, &Style)) {
1564     llvm::errs() << "Invalid fallback style \"" << FallbackStyle
1565                  << "\" using LLVM style\n";
1566     return Style;
1567   }
1568 
1569   if (StyleName.startswith("{")) {
1570     // Parse YAML/JSON style from the command line.
1571     if (std::error_code ec = parseConfiguration(StyleName, &Style)) {
1572       llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
1573                    << FallbackStyle << " style\n";
1574     }
1575     return Style;
1576   }
1577 
1578   if (!StyleName.equals_lower("file")) {
1579     if (!getPredefinedStyle(StyleName, Style.Language, &Style))
1580       llvm::errs() << "Invalid value for -style, using " << FallbackStyle
1581                    << " style\n";
1582     return Style;
1583   }
1584 
1585   // Look for .clang-format/_clang-format file in the file's parent directories.
1586   SmallString<128> UnsuitableConfigFiles;
1587   SmallString<128> Path(FileName);
1588   llvm::sys::fs::make_absolute(Path);
1589   for (StringRef Directory = Path; !Directory.empty();
1590        Directory = llvm::sys::path::parent_path(Directory)) {
1591     if (!llvm::sys::fs::is_directory(Directory))
1592       continue;
1593     SmallString<128> ConfigFile(Directory);
1594 
1595     llvm::sys::path::append(ConfigFile, ".clang-format");
1596     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1597     bool IsFile = false;
1598     // Ignore errors from is_regular_file: we only need to know if we can read
1599     // the file or not.
1600     llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1601 
1602     if (!IsFile) {
1603       // Try _clang-format too, since dotfiles are not commonly used on Windows.
1604       ConfigFile = Directory;
1605       llvm::sys::path::append(ConfigFile, "_clang-format");
1606       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1607       llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1608     }
1609 
1610     if (IsFile) {
1611       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
1612           llvm::MemoryBuffer::getFile(ConfigFile.c_str());
1613       if (std::error_code EC = Text.getError()) {
1614         llvm::errs() << EC.message() << "\n";
1615         break;
1616       }
1617       if (std::error_code ec =
1618               parseConfiguration(Text.get()->getBuffer(), &Style)) {
1619         if (ec == ParseError::Unsuitable) {
1620           if (!UnsuitableConfigFiles.empty())
1621             UnsuitableConfigFiles.append(", ");
1622           UnsuitableConfigFiles.append(ConfigFile);
1623           continue;
1624         }
1625         llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
1626                      << "\n";
1627         break;
1628       }
1629       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
1630       return Style;
1631     }
1632   }
1633   llvm::errs() << "Can't find usable .clang-format, using " << FallbackStyle
1634                << " style\n";
1635   if (!UnsuitableConfigFiles.empty()) {
1636     llvm::errs() << "Configuration file(s) do(es) not support "
1637                  << getLanguageName(Style.Language) << ": "
1638                  << UnsuitableConfigFiles << "\n";
1639   }
1640   return Style;
1641 }
1642 
1643 } // namespace format
1644 } // namespace clang
1645