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 "ContinuationIndenter.h"
18#include "TokenAnnotator.h"
19#include "UnwrappedLineFormatter.h"
20#include "UnwrappedLineParser.h"
21#include "WhitespaceManager.h"
22#include "clang/Basic/Diagnostic.h"
23#include "clang/Basic/DiagnosticOptions.h"
24#include "clang/Basic/SourceManager.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/Regex.h"
31#include "llvm/Support/YAMLTraits.h"
32#include <queue>
33#include <string>
34
35#define DEBUG_TYPE "format-formatter"
36
37using clang::format::FormatStyle;
38
39LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
40LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::IncludeCategory)
41
42namespace llvm {
43namespace yaml {
44template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
45  static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
46    IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
47    IO.enumCase(Value, "Java", FormatStyle::LK_Java);
48    IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
49    IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
50  }
51};
52
53template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
54  static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
55    IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
56    IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
57    IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
58    IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
59    IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
60  }
61};
62
63template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
64  static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
65    IO.enumCase(Value, "Never", FormatStyle::UT_Never);
66    IO.enumCase(Value, "false", FormatStyle::UT_Never);
67    IO.enumCase(Value, "Always", FormatStyle::UT_Always);
68    IO.enumCase(Value, "true", FormatStyle::UT_Always);
69    IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
70  }
71};
72
73template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
74  static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
75    IO.enumCase(Value, "None", FormatStyle::SFS_None);
76    IO.enumCase(Value, "false", FormatStyle::SFS_None);
77    IO.enumCase(Value, "All", FormatStyle::SFS_All);
78    IO.enumCase(Value, "true", FormatStyle::SFS_All);
79    IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
80    IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
81  }
82};
83
84template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
85  static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
86    IO.enumCase(Value, "All", FormatStyle::BOS_All);
87    IO.enumCase(Value, "true", FormatStyle::BOS_All);
88    IO.enumCase(Value, "None", FormatStyle::BOS_None);
89    IO.enumCase(Value, "false", FormatStyle::BOS_None);
90    IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
91  }
92};
93
94template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
95  static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
96    IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
97    IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
98    IO.enumCase(Value, "Mozilla", FormatStyle::BS_Mozilla);
99    IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
100    IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
101    IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
102    IO.enumCase(Value, "WebKit", FormatStyle::BS_WebKit);
103    IO.enumCase(Value, "Custom", FormatStyle::BS_Custom);
104  }
105};
106
107template <>
108struct ScalarEnumerationTraits<FormatStyle::ReturnTypeBreakingStyle> {
109  static void enumeration(IO &IO, FormatStyle::ReturnTypeBreakingStyle &Value) {
110    IO.enumCase(Value, "None", FormatStyle::RTBS_None);
111    IO.enumCase(Value, "All", FormatStyle::RTBS_All);
112    IO.enumCase(Value, "TopLevel", FormatStyle::RTBS_TopLevel);
113    IO.enumCase(Value, "TopLevelDefinitions",
114                FormatStyle::RTBS_TopLevelDefinitions);
115    IO.enumCase(Value, "AllDefinitions", FormatStyle::RTBS_AllDefinitions);
116  }
117};
118
119template <>
120struct ScalarEnumerationTraits<FormatStyle::DefinitionReturnTypeBreakingStyle> {
121  static void
122  enumeration(IO &IO, FormatStyle::DefinitionReturnTypeBreakingStyle &Value) {
123    IO.enumCase(Value, "None", FormatStyle::DRTBS_None);
124    IO.enumCase(Value, "All", FormatStyle::DRTBS_All);
125    IO.enumCase(Value, "TopLevel", FormatStyle::DRTBS_TopLevel);
126
127    // For backward compatibility.
128    IO.enumCase(Value, "false", FormatStyle::DRTBS_None);
129    IO.enumCase(Value, "true", FormatStyle::DRTBS_All);
130  }
131};
132
133template <>
134struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
135  static void enumeration(IO &IO,
136                          FormatStyle::NamespaceIndentationKind &Value) {
137    IO.enumCase(Value, "None", FormatStyle::NI_None);
138    IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
139    IO.enumCase(Value, "All", FormatStyle::NI_All);
140  }
141};
142
143template <> struct ScalarEnumerationTraits<FormatStyle::BracketAlignmentStyle> {
144  static void enumeration(IO &IO, FormatStyle::BracketAlignmentStyle &Value) {
145    IO.enumCase(Value, "Align", FormatStyle::BAS_Align);
146    IO.enumCase(Value, "DontAlign", FormatStyle::BAS_DontAlign);
147    IO.enumCase(Value, "AlwaysBreak", FormatStyle::BAS_AlwaysBreak);
148
149    // For backward compatibility.
150    IO.enumCase(Value, "true", FormatStyle::BAS_Align);
151    IO.enumCase(Value, "false", FormatStyle::BAS_DontAlign);
152  }
153};
154
155template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
156  static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
157    IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
158    IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
159    IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
160
161    // For backward compatibility.
162    IO.enumCase(Value, "true", FormatStyle::PAS_Left);
163    IO.enumCase(Value, "false", FormatStyle::PAS_Right);
164  }
165};
166
167template <>
168struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
169  static void enumeration(IO &IO,
170                          FormatStyle::SpaceBeforeParensOptions &Value) {
171    IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
172    IO.enumCase(Value, "ControlStatements",
173                FormatStyle::SBPO_ControlStatements);
174    IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
175
176    // For backward compatibility.
177    IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
178    IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
179  }
180};
181
182template <> struct MappingTraits<FormatStyle> {
183  static void mapping(IO &IO, FormatStyle &Style) {
184    // When reading, read the language first, we need it for getPredefinedStyle.
185    IO.mapOptional("Language", Style.Language);
186
187    if (IO.outputting()) {
188      StringRef StylesArray[] = {"LLVM",    "Google", "Chromium",
189                                 "Mozilla", "WebKit", "GNU"};
190      ArrayRef<StringRef> Styles(StylesArray);
191      for (size_t i = 0, e = Styles.size(); i < e; ++i) {
192        StringRef StyleName(Styles[i]);
193        FormatStyle PredefinedStyle;
194        if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
195            Style == PredefinedStyle) {
196          IO.mapOptional("# BasedOnStyle", StyleName);
197          break;
198        }
199      }
200    } else {
201      StringRef BasedOnStyle;
202      IO.mapOptional("BasedOnStyle", BasedOnStyle);
203      if (!BasedOnStyle.empty()) {
204        FormatStyle::LanguageKind OldLanguage = Style.Language;
205        FormatStyle::LanguageKind Language =
206            ((FormatStyle *)IO.getContext())->Language;
207        if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
208          IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
209          return;
210        }
211        Style.Language = OldLanguage;
212      }
213    }
214
215    // For backward compatibility.
216    if (!IO.outputting()) {
217      IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
218      IO.mapOptional("IndentFunctionDeclarationAfterType",
219                     Style.IndentWrappedFunctionNames);
220      IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
221      IO.mapOptional("SpaceAfterControlStatementKeyword",
222                     Style.SpaceBeforeParens);
223    }
224
225    IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
226    IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
227    IO.mapOptional("AlignConsecutiveAssignments",
228                   Style.AlignConsecutiveAssignments);
229    IO.mapOptional("AlignConsecutiveDeclarations",
230                   Style.AlignConsecutiveDeclarations);
231    IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
232    IO.mapOptional("AlignOperands", Style.AlignOperands);
233    IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
234    IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
235                   Style.AllowAllParametersOfDeclarationOnNextLine);
236    IO.mapOptional("AllowShortBlocksOnASingleLine",
237                   Style.AllowShortBlocksOnASingleLine);
238    IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
239                   Style.AllowShortCaseLabelsOnASingleLine);
240    IO.mapOptional("AllowShortFunctionsOnASingleLine",
241                   Style.AllowShortFunctionsOnASingleLine);
242    IO.mapOptional("AllowShortIfStatementsOnASingleLine",
243                   Style.AllowShortIfStatementsOnASingleLine);
244    IO.mapOptional("AllowShortLoopsOnASingleLine",
245                   Style.AllowShortLoopsOnASingleLine);
246    IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
247                   Style.AlwaysBreakAfterDefinitionReturnType);
248    IO.mapOptional("AlwaysBreakAfterReturnType",
249                   Style.AlwaysBreakAfterReturnType);
250    // If AlwaysBreakAfterDefinitionReturnType was specified but
251    // AlwaysBreakAfterReturnType was not, initialize the latter from the
252    // former for backwards compatibility.
253    if (Style.AlwaysBreakAfterDefinitionReturnType != FormatStyle::DRTBS_None &&
254        Style.AlwaysBreakAfterReturnType == FormatStyle::RTBS_None) {
255      if (Style.AlwaysBreakAfterDefinitionReturnType == FormatStyle::DRTBS_All)
256        Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
257      else if (Style.AlwaysBreakAfterDefinitionReturnType ==
258               FormatStyle::DRTBS_TopLevel)
259        Style.AlwaysBreakAfterReturnType =
260            FormatStyle::RTBS_TopLevelDefinitions;
261    }
262
263    IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
264                   Style.AlwaysBreakBeforeMultilineStrings);
265    IO.mapOptional("AlwaysBreakTemplateDeclarations",
266                   Style.AlwaysBreakTemplateDeclarations);
267    IO.mapOptional("BinPackArguments", Style.BinPackArguments);
268    IO.mapOptional("BinPackParameters", Style.BinPackParameters);
269    IO.mapOptional("BraceWrapping", Style.BraceWrapping);
270    IO.mapOptional("BreakBeforeBinaryOperators",
271                   Style.BreakBeforeBinaryOperators);
272    IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
273    IO.mapOptional("BreakBeforeTernaryOperators",
274                   Style.BreakBeforeTernaryOperators);
275    IO.mapOptional("BreakConstructorInitializersBeforeComma",
276                   Style.BreakConstructorInitializersBeforeComma);
277    IO.mapOptional("ColumnLimit", Style.ColumnLimit);
278    IO.mapOptional("CommentPragmas", Style.CommentPragmas);
279    IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
280                   Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
281    IO.mapOptional("ConstructorInitializerIndentWidth",
282                   Style.ConstructorInitializerIndentWidth);
283    IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
284    IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
285    IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
286    IO.mapOptional("DisableFormat", Style.DisableFormat);
287    IO.mapOptional("ExperimentalAutoDetectBinPacking",
288                   Style.ExperimentalAutoDetectBinPacking);
289    IO.mapOptional("ForEachMacros", Style.ForEachMacros);
290    IO.mapOptional("IncludeCategories", Style.IncludeCategories);
291    IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
292    IO.mapOptional("IndentWidth", Style.IndentWidth);
293    IO.mapOptional("IndentWrappedFunctionNames",
294                   Style.IndentWrappedFunctionNames);
295    IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
296                   Style.KeepEmptyLinesAtTheStartOfBlocks);
297    IO.mapOptional("MacroBlockBegin", Style.MacroBlockBegin);
298    IO.mapOptional("MacroBlockEnd", Style.MacroBlockEnd);
299    IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
300    IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
301    IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
302    IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
303    IO.mapOptional("ObjCSpaceBeforeProtocolList",
304                   Style.ObjCSpaceBeforeProtocolList);
305    IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
306                   Style.PenaltyBreakBeforeFirstCallParameter);
307    IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
308    IO.mapOptional("PenaltyBreakFirstLessLess",
309                   Style.PenaltyBreakFirstLessLess);
310    IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
311    IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
312    IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
313                   Style.PenaltyReturnTypeOnItsOwnLine);
314    IO.mapOptional("PointerAlignment", Style.PointerAlignment);
315    IO.mapOptional("ReflowComments", Style.ReflowComments);
316    IO.mapOptional("SortIncludes", Style.SortIncludes);
317    IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
318    IO.mapOptional("SpaceBeforeAssignmentOperators",
319                   Style.SpaceBeforeAssignmentOperators);
320    IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
321    IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
322    IO.mapOptional("SpacesBeforeTrailingComments",
323                   Style.SpacesBeforeTrailingComments);
324    IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
325    IO.mapOptional("SpacesInContainerLiterals",
326                   Style.SpacesInContainerLiterals);
327    IO.mapOptional("SpacesInCStyleCastParentheses",
328                   Style.SpacesInCStyleCastParentheses);
329    IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
330    IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
331    IO.mapOptional("Standard", Style.Standard);
332    IO.mapOptional("TabWidth", Style.TabWidth);
333    IO.mapOptional("UseTab", Style.UseTab);
334  }
335};
336
337template <> struct MappingTraits<FormatStyle::BraceWrappingFlags> {
338  static void mapping(IO &IO, FormatStyle::BraceWrappingFlags &Wrapping) {
339    IO.mapOptional("AfterClass", Wrapping.AfterClass);
340    IO.mapOptional("AfterControlStatement", Wrapping.AfterControlStatement);
341    IO.mapOptional("AfterEnum", Wrapping.AfterEnum);
342    IO.mapOptional("AfterFunction", Wrapping.AfterFunction);
343    IO.mapOptional("AfterNamespace", Wrapping.AfterNamespace);
344    IO.mapOptional("AfterObjCDeclaration", Wrapping.AfterObjCDeclaration);
345    IO.mapOptional("AfterStruct", Wrapping.AfterStruct);
346    IO.mapOptional("AfterUnion", Wrapping.AfterUnion);
347    IO.mapOptional("BeforeCatch", Wrapping.BeforeCatch);
348    IO.mapOptional("BeforeElse", Wrapping.BeforeElse);
349    IO.mapOptional("IndentBraces", Wrapping.IndentBraces);
350  }
351};
352
353template <> struct MappingTraits<FormatStyle::IncludeCategory> {
354  static void mapping(IO &IO, FormatStyle::IncludeCategory &Category) {
355    IO.mapOptional("Regex", Category.Regex);
356    IO.mapOptional("Priority", Category.Priority);
357  }
358};
359
360// Allows to read vector<FormatStyle> while keeping default values.
361// IO.getContext() should contain a pointer to the FormatStyle structure, that
362// will be used to get default values for missing keys.
363// If the first element has no Language specified, it will be treated as the
364// default one for the following elements.
365template <> struct DocumentListTraits<std::vector<FormatStyle>> {
366  static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
367    return Seq.size();
368  }
369  static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
370                              size_t Index) {
371    if (Index >= Seq.size()) {
372      assert(Index == Seq.size());
373      FormatStyle Template;
374      if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
375        Template = Seq[0];
376      } else {
377        Template = *((const FormatStyle *)IO.getContext());
378        Template.Language = FormatStyle::LK_None;
379      }
380      Seq.resize(Index + 1, Template);
381    }
382    return Seq[Index];
383  }
384};
385} // namespace yaml
386} // namespace llvm
387
388namespace clang {
389namespace format {
390
391const std::error_category &getParseCategory() {
392  static ParseErrorCategory C;
393  return C;
394}
395std::error_code make_error_code(ParseError e) {
396  return std::error_code(static_cast<int>(e), getParseCategory());
397}
398
399const char *ParseErrorCategory::name() const LLVM_NOEXCEPT {
400  return "clang-format.parse_error";
401}
402
403std::string ParseErrorCategory::message(int EV) const {
404  switch (static_cast<ParseError>(EV)) {
405  case ParseError::Success:
406    return "Success";
407  case ParseError::Error:
408    return "Invalid argument";
409  case ParseError::Unsuitable:
410    return "Unsuitable";
411  }
412  llvm_unreachable("unexpected parse error");
413}
414
415static FormatStyle expandPresets(const FormatStyle &Style) {
416  if (Style.BreakBeforeBraces == FormatStyle::BS_Custom)
417    return Style;
418  FormatStyle Expanded = Style;
419  Expanded.BraceWrapping = {false, false, false, false, false, false,
420                            false, false, false, false, false};
421  switch (Style.BreakBeforeBraces) {
422  case FormatStyle::BS_Linux:
423    Expanded.BraceWrapping.AfterClass = true;
424    Expanded.BraceWrapping.AfterFunction = true;
425    Expanded.BraceWrapping.AfterNamespace = true;
426    break;
427  case FormatStyle::BS_Mozilla:
428    Expanded.BraceWrapping.AfterClass = true;
429    Expanded.BraceWrapping.AfterEnum = true;
430    Expanded.BraceWrapping.AfterFunction = true;
431    Expanded.BraceWrapping.AfterStruct = true;
432    Expanded.BraceWrapping.AfterUnion = true;
433    break;
434  case FormatStyle::BS_Stroustrup:
435    Expanded.BraceWrapping.AfterFunction = true;
436    Expanded.BraceWrapping.BeforeCatch = true;
437    Expanded.BraceWrapping.BeforeElse = true;
438    break;
439  case FormatStyle::BS_Allman:
440    Expanded.BraceWrapping.AfterClass = true;
441    Expanded.BraceWrapping.AfterControlStatement = true;
442    Expanded.BraceWrapping.AfterEnum = true;
443    Expanded.BraceWrapping.AfterFunction = true;
444    Expanded.BraceWrapping.AfterNamespace = true;
445    Expanded.BraceWrapping.AfterObjCDeclaration = true;
446    Expanded.BraceWrapping.AfterStruct = true;
447    Expanded.BraceWrapping.BeforeCatch = true;
448    Expanded.BraceWrapping.BeforeElse = true;
449    break;
450  case FormatStyle::BS_GNU:
451    Expanded.BraceWrapping = {true, true, true, true, true, true,
452                              true, true, true, true, true};
453    break;
454  case FormatStyle::BS_WebKit:
455    Expanded.BraceWrapping.AfterFunction = true;
456    break;
457  default:
458    break;
459  }
460  return Expanded;
461}
462
463FormatStyle getLLVMStyle() {
464  FormatStyle LLVMStyle;
465  LLVMStyle.Language = FormatStyle::LK_Cpp;
466  LLVMStyle.AccessModifierOffset = -2;
467  LLVMStyle.AlignEscapedNewlinesLeft = false;
468  LLVMStyle.AlignAfterOpenBracket = FormatStyle::BAS_Align;
469  LLVMStyle.AlignOperands = true;
470  LLVMStyle.AlignTrailingComments = true;
471  LLVMStyle.AlignConsecutiveAssignments = false;
472  LLVMStyle.AlignConsecutiveDeclarations = false;
473  LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
474  LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
475  LLVMStyle.AllowShortBlocksOnASingleLine = false;
476  LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
477  LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
478  LLVMStyle.AllowShortLoopsOnASingleLine = false;
479  LLVMStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
480  LLVMStyle.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
481  LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
482  LLVMStyle.AlwaysBreakTemplateDeclarations = false;
483  LLVMStyle.BinPackParameters = true;
484  LLVMStyle.BinPackArguments = true;
485  LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
486  LLVMStyle.BreakBeforeTernaryOperators = true;
487  LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
488  LLVMStyle.BraceWrapping = {false, false, false, false, false, false,
489                             false, false, false, false, false};
490  LLVMStyle.BreakConstructorInitializersBeforeComma = false;
491  LLVMStyle.BreakAfterJavaFieldAnnotations = false;
492  LLVMStyle.ColumnLimit = 80;
493  LLVMStyle.CommentPragmas = "^ IWYU pragma:";
494  LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
495  LLVMStyle.ConstructorInitializerIndentWidth = 4;
496  LLVMStyle.ContinuationIndentWidth = 4;
497  LLVMStyle.Cpp11BracedListStyle = true;
498  LLVMStyle.DerivePointerAlignment = false;
499  LLVMStyle.ExperimentalAutoDetectBinPacking = false;
500  LLVMStyle.ForEachMacros.push_back("foreach");
501  LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
502  LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
503  LLVMStyle.IncludeCategories = {{"^\"(llvm|llvm-c|clang|clang-c)/", 2},
504                                 {"^(<|\"(gtest|isl|json)/)", 3},
505                                 {".*", 1}};
506  LLVMStyle.IndentCaseLabels = false;
507  LLVMStyle.IndentWrappedFunctionNames = false;
508  LLVMStyle.IndentWidth = 2;
509  LLVMStyle.TabWidth = 8;
510  LLVMStyle.MaxEmptyLinesToKeep = 1;
511  LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
512  LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
513  LLVMStyle.ObjCBlockIndentWidth = 2;
514  LLVMStyle.ObjCSpaceAfterProperty = false;
515  LLVMStyle.ObjCSpaceBeforeProtocolList = true;
516  LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
517  LLVMStyle.SpacesBeforeTrailingComments = 1;
518  LLVMStyle.Standard = FormatStyle::LS_Cpp11;
519  LLVMStyle.UseTab = FormatStyle::UT_Never;
520  LLVMStyle.ReflowComments = true;
521  LLVMStyle.SpacesInParentheses = false;
522  LLVMStyle.SpacesInSquareBrackets = false;
523  LLVMStyle.SpaceInEmptyParentheses = false;
524  LLVMStyle.SpacesInContainerLiterals = true;
525  LLVMStyle.SpacesInCStyleCastParentheses = false;
526  LLVMStyle.SpaceAfterCStyleCast = false;
527  LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
528  LLVMStyle.SpaceBeforeAssignmentOperators = true;
529  LLVMStyle.SpacesInAngles = false;
530
531  LLVMStyle.PenaltyBreakComment = 300;
532  LLVMStyle.PenaltyBreakFirstLessLess = 120;
533  LLVMStyle.PenaltyBreakString = 1000;
534  LLVMStyle.PenaltyExcessCharacter = 1000000;
535  LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
536  LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
537
538  LLVMStyle.DisableFormat = false;
539  LLVMStyle.SortIncludes = true;
540
541  return LLVMStyle;
542}
543
544FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
545  FormatStyle GoogleStyle = getLLVMStyle();
546  GoogleStyle.Language = Language;
547
548  GoogleStyle.AccessModifierOffset = -1;
549  GoogleStyle.AlignEscapedNewlinesLeft = true;
550  GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
551  GoogleStyle.AllowShortLoopsOnASingleLine = true;
552  GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
553  GoogleStyle.AlwaysBreakTemplateDeclarations = true;
554  GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
555  GoogleStyle.DerivePointerAlignment = true;
556  GoogleStyle.IncludeCategories = {{"^<.*\\.h>", 1}, {"^<.*", 2}, {".*", 3}};
557  GoogleStyle.IndentCaseLabels = true;
558  GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
559  GoogleStyle.ObjCSpaceAfterProperty = false;
560  GoogleStyle.ObjCSpaceBeforeProtocolList = false;
561  GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
562  GoogleStyle.SpacesBeforeTrailingComments = 2;
563  GoogleStyle.Standard = FormatStyle::LS_Auto;
564
565  GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
566  GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
567
568  if (Language == FormatStyle::LK_Java) {
569    GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
570    GoogleStyle.AlignOperands = false;
571    GoogleStyle.AlignTrailingComments = false;
572    GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
573    GoogleStyle.AllowShortIfStatementsOnASingleLine = false;
574    GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
575    GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
576    GoogleStyle.ColumnLimit = 100;
577    GoogleStyle.SpaceAfterCStyleCast = true;
578    GoogleStyle.SpacesBeforeTrailingComments = 1;
579  } else if (Language == FormatStyle::LK_JavaScript) {
580    GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_AlwaysBreak;
581    GoogleStyle.AlignOperands = false;
582    GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
583    GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
584    GoogleStyle.BreakBeforeTernaryOperators = false;
585    GoogleStyle.MaxEmptyLinesToKeep = 3;
586    GoogleStyle.SpacesInContainerLiterals = false;
587  } else if (Language == FormatStyle::LK_Proto) {
588    GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
589    GoogleStyle.SpacesInContainerLiterals = false;
590  }
591
592  return GoogleStyle;
593}
594
595FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
596  FormatStyle ChromiumStyle = getGoogleStyle(Language);
597  if (Language == FormatStyle::LK_Java) {
598    ChromiumStyle.AllowShortIfStatementsOnASingleLine = true;
599    ChromiumStyle.BreakAfterJavaFieldAnnotations = true;
600    ChromiumStyle.ContinuationIndentWidth = 8;
601    ChromiumStyle.IndentWidth = 4;
602  } else {
603    ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
604    ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
605    ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
606    ChromiumStyle.AllowShortLoopsOnASingleLine = false;
607    ChromiumStyle.BinPackParameters = false;
608    ChromiumStyle.DerivePointerAlignment = false;
609  }
610  return ChromiumStyle;
611}
612
613FormatStyle getMozillaStyle() {
614  FormatStyle MozillaStyle = getLLVMStyle();
615  MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
616  MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
617  MozillaStyle.AlwaysBreakAfterReturnType =
618      FormatStyle::RTBS_TopLevelDefinitions;
619  MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
620      FormatStyle::DRTBS_TopLevel;
621  MozillaStyle.AlwaysBreakTemplateDeclarations = true;
622  MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
623  MozillaStyle.BreakConstructorInitializersBeforeComma = true;
624  MozillaStyle.ConstructorInitializerIndentWidth = 2;
625  MozillaStyle.ContinuationIndentWidth = 2;
626  MozillaStyle.Cpp11BracedListStyle = false;
627  MozillaStyle.IndentCaseLabels = true;
628  MozillaStyle.ObjCSpaceAfterProperty = true;
629  MozillaStyle.ObjCSpaceBeforeProtocolList = false;
630  MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
631  MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
632  return MozillaStyle;
633}
634
635FormatStyle getWebKitStyle() {
636  FormatStyle Style = getLLVMStyle();
637  Style.AccessModifierOffset = -4;
638  Style.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
639  Style.AlignOperands = false;
640  Style.AlignTrailingComments = false;
641  Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
642  Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
643  Style.BreakConstructorInitializersBeforeComma = true;
644  Style.Cpp11BracedListStyle = false;
645  Style.ColumnLimit = 0;
646  Style.IndentWidth = 4;
647  Style.NamespaceIndentation = FormatStyle::NI_Inner;
648  Style.ObjCBlockIndentWidth = 4;
649  Style.ObjCSpaceAfterProperty = true;
650  Style.PointerAlignment = FormatStyle::PAS_Left;
651  Style.Standard = FormatStyle::LS_Cpp03;
652  return Style;
653}
654
655FormatStyle getGNUStyle() {
656  FormatStyle Style = getLLVMStyle();
657  Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
658  Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
659  Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
660  Style.BreakBeforeBraces = FormatStyle::BS_GNU;
661  Style.BreakBeforeTernaryOperators = true;
662  Style.Cpp11BracedListStyle = false;
663  Style.ColumnLimit = 79;
664  Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
665  Style.Standard = FormatStyle::LS_Cpp03;
666  return Style;
667}
668
669FormatStyle getNoStyle() {
670  FormatStyle NoStyle = getLLVMStyle();
671  NoStyle.DisableFormat = true;
672  NoStyle.SortIncludes = false;
673  return NoStyle;
674}
675
676bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
677                        FormatStyle *Style) {
678  if (Name.equals_lower("llvm")) {
679    *Style = getLLVMStyle();
680  } else if (Name.equals_lower("chromium")) {
681    *Style = getChromiumStyle(Language);
682  } else if (Name.equals_lower("mozilla")) {
683    *Style = getMozillaStyle();
684  } else if (Name.equals_lower("google")) {
685    *Style = getGoogleStyle(Language);
686  } else if (Name.equals_lower("webkit")) {
687    *Style = getWebKitStyle();
688  } else if (Name.equals_lower("gnu")) {
689    *Style = getGNUStyle();
690  } else if (Name.equals_lower("none")) {
691    *Style = getNoStyle();
692  } else {
693    return false;
694  }
695
696  Style->Language = Language;
697  return true;
698}
699
700std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
701  assert(Style);
702  FormatStyle::LanguageKind Language = Style->Language;
703  assert(Language != FormatStyle::LK_None);
704  if (Text.trim().empty())
705    return make_error_code(ParseError::Error);
706
707  std::vector<FormatStyle> Styles;
708  llvm::yaml::Input Input(Text);
709  // DocumentListTraits<vector<FormatStyle>> uses the context to get default
710  // values for the fields, keys for which are missing from the configuration.
711  // Mapping also uses the context to get the language to find the correct
712  // base style.
713  Input.setContext(Style);
714  Input >> Styles;
715  if (Input.error())
716    return Input.error();
717
718  for (unsigned i = 0; i < Styles.size(); ++i) {
719    // Ensures that only the first configuration can skip the Language option.
720    if (Styles[i].Language == FormatStyle::LK_None && i != 0)
721      return make_error_code(ParseError::Error);
722    // Ensure that each language is configured at most once.
723    for (unsigned j = 0; j < i; ++j) {
724      if (Styles[i].Language == Styles[j].Language) {
725        DEBUG(llvm::dbgs()
726              << "Duplicate languages in the config file on positions " << j
727              << " and " << i << "\n");
728        return make_error_code(ParseError::Error);
729      }
730    }
731  }
732  // Look for a suitable configuration starting from the end, so we can
733  // find the configuration for the specific language first, and the default
734  // configuration (which can only be at slot 0) after it.
735  for (int i = Styles.size() - 1; i >= 0; --i) {
736    if (Styles[i].Language == Language ||
737        Styles[i].Language == FormatStyle::LK_None) {
738      *Style = Styles[i];
739      Style->Language = Language;
740      return make_error_code(ParseError::Success);
741    }
742  }
743  return make_error_code(ParseError::Unsuitable);
744}
745
746std::string configurationAsText(const FormatStyle &Style) {
747  std::string Text;
748  llvm::raw_string_ostream Stream(Text);
749  llvm::yaml::Output Output(Stream);
750  // We use the same mapping method for input and output, so we need a non-const
751  // reference here.
752  FormatStyle NonConstStyle = expandPresets(Style);
753  Output << NonConstStyle;
754  return Stream.str();
755}
756
757namespace {
758
759class FormatTokenLexer {
760public:
761  FormatTokenLexer(SourceManager &SourceMgr, FileID ID, FormatStyle &Style,
762                   encoding::Encoding Encoding)
763      : FormatTok(nullptr), IsFirstToken(true), GreaterStashed(false),
764        LessStashed(false), Column(0), TrailingWhitespace(0),
765        SourceMgr(SourceMgr), ID(ID), Style(Style),
766        IdentTable(getFormattingLangOpts(Style)), Keywords(IdentTable),
767        Encoding(Encoding), FirstInLineIndex(0), FormattingDisabled(false),
768        MacroBlockBeginRegex(Style.MacroBlockBegin),
769        MacroBlockEndRegex(Style.MacroBlockEnd) {
770    Lex.reset(new Lexer(ID, SourceMgr.getBuffer(ID), SourceMgr,
771                        getFormattingLangOpts(Style)));
772    Lex->SetKeepWhitespaceMode(true);
773
774    for (const std::string &ForEachMacro : Style.ForEachMacros)
775      ForEachMacros.push_back(&IdentTable.get(ForEachMacro));
776    std::sort(ForEachMacros.begin(), ForEachMacros.end());
777  }
778
779  ArrayRef<FormatToken *> lex() {
780    assert(Tokens.empty());
781    assert(FirstInLineIndex == 0);
782    do {
783      Tokens.push_back(getNextToken());
784      if (Style.Language == FormatStyle::LK_JavaScript)
785        tryParseJSRegexLiteral();
786      tryMergePreviousTokens();
787      if (Tokens.back()->NewlinesBefore > 0 || Tokens.back()->IsMultiline)
788        FirstInLineIndex = Tokens.size() - 1;
789    } while (Tokens.back()->Tok.isNot(tok::eof));
790    return Tokens;
791  }
792
793  const AdditionalKeywords &getKeywords() { return Keywords; }
794
795private:
796  void tryMergePreviousTokens() {
797    if (tryMerge_TMacro())
798      return;
799    if (tryMergeConflictMarkers())
800      return;
801    if (tryMergeLessLess())
802      return;
803
804    if (Style.Language == FormatStyle::LK_JavaScript) {
805      if (tryMergeTemplateString())
806        return;
807
808      static const tok::TokenKind JSIdentity[] = {tok::equalequal, tok::equal};
809      static const tok::TokenKind JSNotIdentity[] = {tok::exclaimequal,
810                                                     tok::equal};
811      static const tok::TokenKind JSShiftEqual[] = {tok::greater, tok::greater,
812                                                    tok::greaterequal};
813      static const tok::TokenKind JSRightArrow[] = {tok::equal, tok::greater};
814      // FIXME: Investigate what token type gives the correct operator priority.
815      if (tryMergeTokens(JSIdentity, TT_BinaryOperator))
816        return;
817      if (tryMergeTokens(JSNotIdentity, TT_BinaryOperator))
818        return;
819      if (tryMergeTokens(JSShiftEqual, TT_BinaryOperator))
820        return;
821      if (tryMergeTokens(JSRightArrow, TT_JsFatArrow))
822        return;
823    }
824  }
825
826  bool tryMergeLessLess() {
827    // Merge X,less,less,Y into X,lessless,Y unless X or Y is less.
828    if (Tokens.size() < 3)
829      return false;
830
831    bool FourthTokenIsLess = false;
832    if (Tokens.size() > 3)
833      FourthTokenIsLess = (Tokens.end() - 4)[0]->is(tok::less);
834
835    auto First = Tokens.end() - 3;
836    if (First[2]->is(tok::less) || First[1]->isNot(tok::less) ||
837        First[0]->isNot(tok::less) || FourthTokenIsLess)
838      return false;
839
840    // Only merge if there currently is no whitespace between the two "<".
841    if (First[1]->WhitespaceRange.getBegin() !=
842        First[1]->WhitespaceRange.getEnd())
843      return false;
844
845    First[0]->Tok.setKind(tok::lessless);
846    First[0]->TokenText = "<<";
847    First[0]->ColumnWidth += 1;
848    Tokens.erase(Tokens.end() - 2);
849    return true;
850  }
851
852  bool tryMergeTokens(ArrayRef<tok::TokenKind> Kinds, TokenType NewType) {
853    if (Tokens.size() < Kinds.size())
854      return false;
855
856    SmallVectorImpl<FormatToken *>::const_iterator First =
857        Tokens.end() - Kinds.size();
858    if (!First[0]->is(Kinds[0]))
859      return false;
860    unsigned AddLength = 0;
861    for (unsigned i = 1; i < Kinds.size(); ++i) {
862      if (!First[i]->is(Kinds[i]) ||
863          First[i]->WhitespaceRange.getBegin() !=
864              First[i]->WhitespaceRange.getEnd())
865        return false;
866      AddLength += First[i]->TokenText.size();
867    }
868    Tokens.resize(Tokens.size() - Kinds.size() + 1);
869    First[0]->TokenText = StringRef(First[0]->TokenText.data(),
870                                    First[0]->TokenText.size() + AddLength);
871    First[0]->ColumnWidth += AddLength;
872    First[0]->Type = NewType;
873    return true;
874  }
875
876  // Returns \c true if \p Tok can only be followed by an operand in JavaScript.
877  bool precedesOperand(FormatToken *Tok) {
878    // NB: This is not entirely correct, as an r_paren can introduce an operand
879    // location in e.g. `if (foo) /bar/.exec(...);`. That is a rare enough
880    // corner case to not matter in practice, though.
881    return Tok->isOneOf(tok::period, tok::l_paren, tok::comma, tok::l_brace,
882                        tok::r_brace, tok::l_square, tok::semi, tok::exclaim,
883                        tok::colon, tok::question, tok::tilde) ||
884           Tok->isOneOf(tok::kw_return, tok::kw_do, tok::kw_case, tok::kw_throw,
885                        tok::kw_else, tok::kw_new, tok::kw_delete, tok::kw_void,
886                        tok::kw_typeof, Keywords.kw_instanceof,
887                        Keywords.kw_in) ||
888           Tok->isBinaryOperator();
889  }
890
891  bool canPrecedeRegexLiteral(FormatToken *Prev) {
892    if (!Prev)
893      return true;
894
895    // Regex literals can only follow after prefix unary operators, not after
896    // postfix unary operators. If the '++' is followed by a non-operand
897    // introducing token, the slash here is the operand and not the start of a
898    // regex.
899    if (Prev->isOneOf(tok::plusplus, tok::minusminus))
900      return (Tokens.size() < 3 || precedesOperand(Tokens[Tokens.size() - 3]));
901
902    // The previous token must introduce an operand location where regex
903    // literals can occur.
904    if (!precedesOperand(Prev))
905      return false;
906
907    return true;
908  }
909
910  // Tries to parse a JavaScript Regex literal starting at the current token,
911  // if that begins with a slash and is in a location where JavaScript allows
912  // regex literals. Changes the current token to a regex literal and updates
913  // its text if successful.
914  void tryParseJSRegexLiteral() {
915    FormatToken *RegexToken = Tokens.back();
916    if (!RegexToken->isOneOf(tok::slash, tok::slashequal))
917      return;
918
919    FormatToken *Prev = nullptr;
920    for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; ++I) {
921      // NB: Because previous pointers are not initialized yet, this cannot use
922      // Token.getPreviousNonComment.
923      if ((*I)->isNot(tok::comment)) {
924        Prev = *I;
925        break;
926      }
927    }
928
929    if (!canPrecedeRegexLiteral(Prev))
930      return;
931
932    // 'Manually' lex ahead in the current file buffer.
933    const char *Offset = Lex->getBufferLocation();
934    const char *RegexBegin = Offset - RegexToken->TokenText.size();
935    StringRef Buffer = Lex->getBuffer();
936    bool InCharacterClass = false;
937    bool HaveClosingSlash = false;
938    for (; !HaveClosingSlash && Offset != Buffer.end(); ++Offset) {
939      // Regular expressions are terminated with a '/', which can only be
940      // escaped using '\' or a character class between '[' and ']'.
941      // See http://www.ecma-international.org/ecma-262/5.1/#sec-7.8.5.
942      switch (*Offset) {
943      case '\\':
944        // Skip the escaped character.
945        ++Offset;
946        break;
947      case '[':
948        InCharacterClass = true;
949        break;
950      case ']':
951        InCharacterClass = false;
952        break;
953      case '/':
954        if (!InCharacterClass)
955          HaveClosingSlash = true;
956        break;
957      }
958    }
959
960    RegexToken->Type = TT_RegexLiteral;
961    // Treat regex literals like other string_literals.
962    RegexToken->Tok.setKind(tok::string_literal);
963    RegexToken->TokenText = StringRef(RegexBegin, Offset - RegexBegin);
964    RegexToken->ColumnWidth = RegexToken->TokenText.size();
965
966    resetLexer(SourceMgr.getFileOffset(Lex->getSourceLocation(Offset)));
967  }
968
969  bool tryMergeTemplateString() {
970    if (Tokens.size() < 2)
971      return false;
972
973    FormatToken *EndBacktick = Tokens.back();
974    // Backticks get lexed as tok::unknown tokens. If a template string contains
975    // a comment start, it gets lexed as a tok::comment, or tok::unknown if
976    // unterminated.
977    if (!EndBacktick->isOneOf(tok::comment, tok::string_literal,
978                              tok::char_constant, tok::unknown))
979      return false;
980    size_t CommentBacktickPos = EndBacktick->TokenText.find('`');
981    // Unknown token that's not actually a backtick, or a comment that doesn't
982    // contain a backtick.
983    if (CommentBacktickPos == StringRef::npos)
984      return false;
985
986    unsigned TokenCount = 0;
987    bool IsMultiline = false;
988    unsigned EndColumnInFirstLine =
989        EndBacktick->OriginalColumn + EndBacktick->ColumnWidth;
990    for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; I++) {
991      ++TokenCount;
992      if (I[0]->IsMultiline)
993        IsMultiline = true;
994
995      // If there was a preceding template string, this must be the start of a
996      // template string, not the end.
997      if (I[0]->is(TT_TemplateString))
998        return false;
999
1000      if (I[0]->isNot(tok::unknown) || I[0]->TokenText != "`") {
1001        // Keep track of the rhs offset of the last token to wrap across lines -
1002        // its the rhs offset of the first line of the template string, used to
1003        // determine its width.
1004        if (I[0]->IsMultiline)
1005          EndColumnInFirstLine = I[0]->OriginalColumn + I[0]->ColumnWidth;
1006        // If the token has newlines, the token before it (if it exists) is the
1007        // rhs end of the previous line.
1008        if (I[0]->NewlinesBefore > 0 && (I + 1 != E)) {
1009          EndColumnInFirstLine = I[1]->OriginalColumn + I[1]->ColumnWidth;
1010          IsMultiline = true;
1011        }
1012        continue;
1013      }
1014
1015      Tokens.resize(Tokens.size() - TokenCount);
1016      Tokens.back()->Type = TT_TemplateString;
1017      const char *EndOffset =
1018          EndBacktick->TokenText.data() + 1 + CommentBacktickPos;
1019      if (CommentBacktickPos != 0) {
1020        // If the backtick was not the first character (e.g. in a comment),
1021        // re-lex after the backtick position.
1022        SourceLocation Loc = EndBacktick->Tok.getLocation();
1023        resetLexer(SourceMgr.getFileOffset(Loc) + CommentBacktickPos + 1);
1024      }
1025      Tokens.back()->TokenText =
1026          StringRef(Tokens.back()->TokenText.data(),
1027                    EndOffset - Tokens.back()->TokenText.data());
1028
1029      unsigned EndOriginalColumn = EndBacktick->OriginalColumn;
1030      if (EndOriginalColumn == 0) {
1031        SourceLocation Loc = EndBacktick->Tok.getLocation();
1032        EndOriginalColumn = SourceMgr.getSpellingColumnNumber(Loc);
1033      }
1034      // If the ` is further down within the token (e.g. in a comment).
1035      EndOriginalColumn += CommentBacktickPos;
1036
1037      if (IsMultiline) {
1038        // ColumnWidth is from backtick to last token in line.
1039        // LastLineColumnWidth is 0 to backtick.
1040        // x = `some content
1041        //     until here`;
1042        Tokens.back()->ColumnWidth =
1043            EndColumnInFirstLine - Tokens.back()->OriginalColumn;
1044        // +1 for the ` itself.
1045        Tokens.back()->LastLineColumnWidth = EndOriginalColumn + 1;
1046        Tokens.back()->IsMultiline = true;
1047      } else {
1048        // Token simply spans from start to end, +1 for the ` itself.
1049        Tokens.back()->ColumnWidth =
1050            EndOriginalColumn - Tokens.back()->OriginalColumn + 1;
1051      }
1052      return true;
1053    }
1054    return false;
1055  }
1056
1057  bool tryMerge_TMacro() {
1058    if (Tokens.size() < 4)
1059      return false;
1060    FormatToken *Last = Tokens.back();
1061    if (!Last->is(tok::r_paren))
1062      return false;
1063
1064    FormatToken *String = Tokens[Tokens.size() - 2];
1065    if (!String->is(tok::string_literal) || String->IsMultiline)
1066      return false;
1067
1068    if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
1069      return false;
1070
1071    FormatToken *Macro = Tokens[Tokens.size() - 4];
1072    if (Macro->TokenText != "_T")
1073      return false;
1074
1075    const char *Start = Macro->TokenText.data();
1076    const char *End = Last->TokenText.data() + Last->TokenText.size();
1077    String->TokenText = StringRef(Start, End - Start);
1078    String->IsFirst = Macro->IsFirst;
1079    String->LastNewlineOffset = Macro->LastNewlineOffset;
1080    String->WhitespaceRange = Macro->WhitespaceRange;
1081    String->OriginalColumn = Macro->OriginalColumn;
1082    String->ColumnWidth = encoding::columnWidthWithTabs(
1083        String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
1084    String->NewlinesBefore = Macro->NewlinesBefore;
1085    String->HasUnescapedNewline = Macro->HasUnescapedNewline;
1086
1087    Tokens.pop_back();
1088    Tokens.pop_back();
1089    Tokens.pop_back();
1090    Tokens.back() = String;
1091    return true;
1092  }
1093
1094  bool tryMergeConflictMarkers() {
1095    if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(tok::eof))
1096      return false;
1097
1098    // Conflict lines look like:
1099    // <marker> <text from the vcs>
1100    // For example:
1101    // >>>>>>> /file/in/file/system at revision 1234
1102    //
1103    // We merge all tokens in a line that starts with a conflict marker
1104    // into a single token with a special token type that the unwrapped line
1105    // parser will use to correctly rebuild the underlying code.
1106
1107    FileID ID;
1108    // Get the position of the first token in the line.
1109    unsigned FirstInLineOffset;
1110    std::tie(ID, FirstInLineOffset) = SourceMgr.getDecomposedLoc(
1111        Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
1112    StringRef Buffer = SourceMgr.getBuffer(ID)->getBuffer();
1113    // Calculate the offset of the start of the current line.
1114    auto LineOffset = Buffer.rfind('\n', FirstInLineOffset);
1115    if (LineOffset == StringRef::npos) {
1116      LineOffset = 0;
1117    } else {
1118      ++LineOffset;
1119    }
1120
1121    auto FirstSpace = Buffer.find_first_of(" \n", LineOffset);
1122    StringRef LineStart;
1123    if (FirstSpace == StringRef::npos) {
1124      LineStart = Buffer.substr(LineOffset);
1125    } else {
1126      LineStart = Buffer.substr(LineOffset, FirstSpace - LineOffset);
1127    }
1128
1129    TokenType Type = TT_Unknown;
1130    if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
1131      Type = TT_ConflictStart;
1132    } else if (LineStart == "|||||||" || LineStart == "=======" ||
1133               LineStart == "====") {
1134      Type = TT_ConflictAlternative;
1135    } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
1136      Type = TT_ConflictEnd;
1137    }
1138
1139    if (Type != TT_Unknown) {
1140      FormatToken *Next = Tokens.back();
1141
1142      Tokens.resize(FirstInLineIndex + 1);
1143      // We do not need to build a complete token here, as we will skip it
1144      // during parsing anyway (as we must not touch whitespace around conflict
1145      // markers).
1146      Tokens.back()->Type = Type;
1147      Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
1148
1149      Tokens.push_back(Next);
1150      return true;
1151    }
1152
1153    return false;
1154  }
1155
1156  FormatToken *getStashedToken() {
1157    // Create a synthesized second '>' or '<' token.
1158    Token Tok = FormatTok->Tok;
1159    StringRef TokenText = FormatTok->TokenText;
1160
1161    unsigned OriginalColumn = FormatTok->OriginalColumn;
1162    FormatTok = new (Allocator.Allocate()) FormatToken;
1163    FormatTok->Tok = Tok;
1164    SourceLocation TokLocation =
1165        FormatTok->Tok.getLocation().getLocWithOffset(Tok.getLength() - 1);
1166    FormatTok->Tok.setLocation(TokLocation);
1167    FormatTok->WhitespaceRange = SourceRange(TokLocation, TokLocation);
1168    FormatTok->TokenText = TokenText;
1169    FormatTok->ColumnWidth = 1;
1170    FormatTok->OriginalColumn = OriginalColumn + 1;
1171
1172    return FormatTok;
1173  }
1174
1175  FormatToken *getNextToken() {
1176    if (GreaterStashed) {
1177      GreaterStashed = false;
1178      return getStashedToken();
1179    }
1180    if (LessStashed) {
1181      LessStashed = false;
1182      return getStashedToken();
1183    }
1184
1185    FormatTok = new (Allocator.Allocate()) FormatToken;
1186    readRawToken(*FormatTok);
1187    SourceLocation WhitespaceStart =
1188        FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
1189    FormatTok->IsFirst = IsFirstToken;
1190    IsFirstToken = false;
1191
1192    // Consume and record whitespace until we find a significant token.
1193    unsigned WhitespaceLength = TrailingWhitespace;
1194    while (FormatTok->Tok.is(tok::unknown)) {
1195      StringRef Text = FormatTok->TokenText;
1196      auto EscapesNewline = [&](int pos) {
1197        // A '\r' here is just part of '\r\n'. Skip it.
1198        if (pos >= 0 && Text[pos] == '\r')
1199          --pos;
1200        // See whether there is an odd number of '\' before this.
1201        unsigned count = 0;
1202        for (; pos >= 0; --pos, ++count)
1203          if (Text[pos] != '\\')
1204            break;
1205        return count & 1;
1206      };
1207      // FIXME: This miscounts tok:unknown tokens that are not just
1208      // whitespace, e.g. a '`' character.
1209      for (int i = 0, e = Text.size(); i != e; ++i) {
1210        switch (Text[i]) {
1211        case '\n':
1212          ++FormatTok->NewlinesBefore;
1213          FormatTok->HasUnescapedNewline = !EscapesNewline(i - 1);
1214          FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1215          Column = 0;
1216          break;
1217        case '\r':
1218          FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1219          Column = 0;
1220          break;
1221        case '\f':
1222        case '\v':
1223          Column = 0;
1224          break;
1225        case ' ':
1226          ++Column;
1227          break;
1228        case '\t':
1229          Column += Style.TabWidth - Column % Style.TabWidth;
1230          break;
1231        case '\\':
1232          if (i + 1 == e || (Text[i + 1] != '\r' && Text[i + 1] != '\n'))
1233            FormatTok->Type = TT_ImplicitStringLiteral;
1234          break;
1235        default:
1236          FormatTok->Type = TT_ImplicitStringLiteral;
1237          break;
1238        }
1239      }
1240
1241      if (FormatTok->is(TT_ImplicitStringLiteral))
1242        break;
1243      WhitespaceLength += FormatTok->Tok.getLength();
1244
1245      readRawToken(*FormatTok);
1246    }
1247
1248    // In case the token starts with escaped newlines, we want to
1249    // take them into account as whitespace - this pattern is quite frequent
1250    // in macro definitions.
1251    // FIXME: Add a more explicit test.
1252    while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
1253           FormatTok->TokenText[1] == '\n') {
1254      ++FormatTok->NewlinesBefore;
1255      WhitespaceLength += 2;
1256      FormatTok->LastNewlineOffset = 2;
1257      Column = 0;
1258      FormatTok->TokenText = FormatTok->TokenText.substr(2);
1259    }
1260
1261    FormatTok->WhitespaceRange = SourceRange(
1262        WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1263
1264    FormatTok->OriginalColumn = Column;
1265
1266    TrailingWhitespace = 0;
1267    if (FormatTok->Tok.is(tok::comment)) {
1268      // FIXME: Add the trimmed whitespace to Column.
1269      StringRef UntrimmedText = FormatTok->TokenText;
1270      FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
1271      TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1272    } else if (FormatTok->Tok.is(tok::raw_identifier)) {
1273      IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
1274      FormatTok->Tok.setIdentifierInfo(&Info);
1275      FormatTok->Tok.setKind(Info.getTokenID());
1276      if (Style.Language == FormatStyle::LK_Java &&
1277          FormatTok->isOneOf(tok::kw_struct, tok::kw_union, tok::kw_delete)) {
1278        FormatTok->Tok.setKind(tok::identifier);
1279        FormatTok->Tok.setIdentifierInfo(nullptr);
1280      } else if (Style.Language == FormatStyle::LK_JavaScript &&
1281                 FormatTok->isOneOf(tok::kw_struct, tok::kw_union)) {
1282        FormatTok->Tok.setKind(tok::identifier);
1283        FormatTok->Tok.setIdentifierInfo(nullptr);
1284      }
1285    } else if (FormatTok->Tok.is(tok::greatergreater)) {
1286      FormatTok->Tok.setKind(tok::greater);
1287      FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1288      GreaterStashed = true;
1289    } else if (FormatTok->Tok.is(tok::lessless)) {
1290      FormatTok->Tok.setKind(tok::less);
1291      FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1292      LessStashed = true;
1293    }
1294
1295    // Now FormatTok is the next non-whitespace token.
1296
1297    StringRef Text = FormatTok->TokenText;
1298    size_t FirstNewlinePos = Text.find('\n');
1299    if (FirstNewlinePos == StringRef::npos) {
1300      // FIXME: ColumnWidth actually depends on the start column, we need to
1301      // take this into account when the token is moved.
1302      FormatTok->ColumnWidth =
1303          encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
1304      Column += FormatTok->ColumnWidth;
1305    } else {
1306      FormatTok->IsMultiline = true;
1307      // FIXME: ColumnWidth actually depends on the start column, we need to
1308      // take this into account when the token is moved.
1309      FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1310          Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
1311
1312      // The last line of the token always starts in column 0.
1313      // Thus, the length can be precomputed even in the presence of tabs.
1314      FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1315          Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
1316          Encoding);
1317      Column = FormatTok->LastLineColumnWidth;
1318    }
1319
1320    if (Style.Language == FormatStyle::LK_Cpp) {
1321      if (!(Tokens.size() > 0 && Tokens.back()->Tok.getIdentifierInfo() &&
1322            Tokens.back()->Tok.getIdentifierInfo()->getPPKeywordID() ==
1323                tok::pp_define) &&
1324          std::find(ForEachMacros.begin(), ForEachMacros.end(),
1325                    FormatTok->Tok.getIdentifierInfo()) != ForEachMacros.end()) {
1326        FormatTok->Type = TT_ForEachMacro;
1327      } else if (FormatTok->is(tok::identifier)) {
1328        if (MacroBlockBeginRegex.match(Text)) {
1329          FormatTok->Type = TT_MacroBlockBegin;
1330        } else if (MacroBlockEndRegex.match(Text)) {
1331          FormatTok->Type = TT_MacroBlockEnd;
1332        }
1333      }
1334    }
1335
1336    return FormatTok;
1337  }
1338
1339  FormatToken *FormatTok;
1340  bool IsFirstToken;
1341  bool GreaterStashed, LessStashed;
1342  unsigned Column;
1343  unsigned TrailingWhitespace;
1344  std::unique_ptr<Lexer> Lex;
1345  SourceManager &SourceMgr;
1346  FileID ID;
1347  FormatStyle &Style;
1348  IdentifierTable IdentTable;
1349  AdditionalKeywords Keywords;
1350  encoding::Encoding Encoding;
1351  llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
1352  // Index (in 'Tokens') of the last token that starts a new line.
1353  unsigned FirstInLineIndex;
1354  SmallVector<FormatToken *, 16> Tokens;
1355  SmallVector<IdentifierInfo *, 8> ForEachMacros;
1356
1357  bool FormattingDisabled;
1358
1359  llvm::Regex MacroBlockBeginRegex;
1360  llvm::Regex MacroBlockEndRegex;
1361
1362  void readRawToken(FormatToken &Tok) {
1363    Lex->LexFromRawLexer(Tok.Tok);
1364    Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
1365                              Tok.Tok.getLength());
1366    // For formatting, treat unterminated string literals like normal string
1367    // literals.
1368    if (Tok.is(tok::unknown)) {
1369      if (!Tok.TokenText.empty() && Tok.TokenText[0] == '"') {
1370        Tok.Tok.setKind(tok::string_literal);
1371        Tok.IsUnterminatedLiteral = true;
1372      } else if (Style.Language == FormatStyle::LK_JavaScript &&
1373                 Tok.TokenText == "''") {
1374        Tok.Tok.setKind(tok::char_constant);
1375      }
1376    }
1377
1378    if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format on" ||
1379                                 Tok.TokenText == "/* clang-format on */")) {
1380      FormattingDisabled = false;
1381    }
1382
1383    Tok.Finalized = FormattingDisabled;
1384
1385    if (Tok.is(tok::comment) && (Tok.TokenText == "// clang-format off" ||
1386                                 Tok.TokenText == "/* clang-format off */")) {
1387      FormattingDisabled = true;
1388    }
1389  }
1390
1391  void resetLexer(unsigned Offset) {
1392    StringRef Buffer = SourceMgr.getBufferData(ID);
1393    Lex.reset(new Lexer(SourceMgr.getLocForStartOfFile(ID),
1394                        getFormattingLangOpts(Style), Buffer.begin(),
1395                        Buffer.begin() + Offset, Buffer.end()));
1396    Lex->SetKeepWhitespaceMode(true);
1397    TrailingWhitespace = 0;
1398  }
1399};
1400
1401static StringRef getLanguageName(FormatStyle::LanguageKind Language) {
1402  switch (Language) {
1403  case FormatStyle::LK_Cpp:
1404    return "C++";
1405  case FormatStyle::LK_Java:
1406    return "Java";
1407  case FormatStyle::LK_JavaScript:
1408    return "JavaScript";
1409  case FormatStyle::LK_Proto:
1410    return "Proto";
1411  default:
1412    return "Unknown";
1413  }
1414}
1415
1416class Formatter : public UnwrappedLineConsumer {
1417public:
1418  Formatter(const FormatStyle &Style, SourceManager &SourceMgr, FileID ID,
1419            ArrayRef<CharSourceRange> Ranges)
1420      : Style(Style), ID(ID), SourceMgr(SourceMgr),
1421        Whitespaces(SourceMgr, Style,
1422                    inputUsesCRLF(SourceMgr.getBufferData(ID))),
1423        Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1),
1424        Encoding(encoding::detectEncoding(SourceMgr.getBufferData(ID))) {
1425    DEBUG(llvm::dbgs() << "File encoding: "
1426                       << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
1427                                                               : "unknown")
1428                       << "\n");
1429    DEBUG(llvm::dbgs() << "Language: " << getLanguageName(Style.Language)
1430                       << "\n");
1431  }
1432
1433  tooling::Replacements format(bool *IncompleteFormat) {
1434    tooling::Replacements Result;
1435    FormatTokenLexer Tokens(SourceMgr, ID, Style, Encoding);
1436
1437    UnwrappedLineParser Parser(Style, Tokens.getKeywords(), Tokens.lex(),
1438                               *this);
1439    Parser.parse();
1440    assert(UnwrappedLines.rbegin()->empty());
1441    for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
1442         ++Run) {
1443      DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
1444      SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1445      for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
1446        AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
1447      }
1448      tooling::Replacements RunResult =
1449          format(AnnotatedLines, Tokens, IncompleteFormat);
1450      DEBUG({
1451        llvm::dbgs() << "Replacements for run " << Run << ":\n";
1452        for (tooling::Replacements::iterator I = RunResult.begin(),
1453                                             E = RunResult.end();
1454             I != E; ++I) {
1455          llvm::dbgs() << I->toString() << "\n";
1456        }
1457      });
1458      for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1459        delete AnnotatedLines[i];
1460      }
1461      Result.insert(RunResult.begin(), RunResult.end());
1462      Whitespaces.reset();
1463    }
1464    return Result;
1465  }
1466
1467  tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1468                               FormatTokenLexer &Tokens,
1469                               bool *IncompleteFormat) {
1470    TokenAnnotator Annotator(Style, Tokens.getKeywords());
1471    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1472      Annotator.annotate(*AnnotatedLines[i]);
1473    }
1474    deriveLocalStyle(AnnotatedLines);
1475    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1476      Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1477    }
1478    computeAffectedLines(AnnotatedLines.begin(), AnnotatedLines.end());
1479
1480    Annotator.setCommentLineLevels(AnnotatedLines);
1481    ContinuationIndenter Indenter(Style, Tokens.getKeywords(), SourceMgr,
1482                                  Whitespaces, Encoding,
1483                                  BinPackInconclusiveFunctions);
1484    UnwrappedLineFormatter(&Indenter, &Whitespaces, Style, Tokens.getKeywords(),
1485                           IncompleteFormat)
1486        .format(AnnotatedLines);
1487    return Whitespaces.generateReplacements();
1488  }
1489
1490private:
1491  // Determines which lines are affected by the SourceRanges given as input.
1492  // Returns \c true if at least one line between I and E or one of their
1493  // children is affected.
1494  bool computeAffectedLines(SmallVectorImpl<AnnotatedLine *>::iterator I,
1495                            SmallVectorImpl<AnnotatedLine *>::iterator E) {
1496    bool SomeLineAffected = false;
1497    const AnnotatedLine *PreviousLine = nullptr;
1498    while (I != E) {
1499      AnnotatedLine *Line = *I;
1500      Line->LeadingEmptyLinesAffected = affectsLeadingEmptyLines(*Line->First);
1501
1502      // If a line is part of a preprocessor directive, it needs to be formatted
1503      // if any token within the directive is affected.
1504      if (Line->InPPDirective) {
1505        FormatToken *Last = Line->Last;
1506        SmallVectorImpl<AnnotatedLine *>::iterator PPEnd = I + 1;
1507        while (PPEnd != E && !(*PPEnd)->First->HasUnescapedNewline) {
1508          Last = (*PPEnd)->Last;
1509          ++PPEnd;
1510        }
1511
1512        if (affectsTokenRange(*Line->First, *Last,
1513                              /*IncludeLeadingNewlines=*/false)) {
1514          SomeLineAffected = true;
1515          markAllAsAffected(I, PPEnd);
1516        }
1517        I = PPEnd;
1518        continue;
1519      }
1520
1521      if (nonPPLineAffected(Line, PreviousLine))
1522        SomeLineAffected = true;
1523
1524      PreviousLine = Line;
1525      ++I;
1526    }
1527    return SomeLineAffected;
1528  }
1529
1530  // Determines whether 'Line' is affected by the SourceRanges given as input.
1531  // Returns \c true if line or one if its children is affected.
1532  bool nonPPLineAffected(AnnotatedLine *Line,
1533                         const AnnotatedLine *PreviousLine) {
1534    bool SomeLineAffected = false;
1535    Line->ChildrenAffected =
1536        computeAffectedLines(Line->Children.begin(), Line->Children.end());
1537    if (Line->ChildrenAffected)
1538      SomeLineAffected = true;
1539
1540    // Stores whether one of the line's tokens is directly affected.
1541    bool SomeTokenAffected = false;
1542    // Stores whether we need to look at the leading newlines of the next token
1543    // in order to determine whether it was affected.
1544    bool IncludeLeadingNewlines = false;
1545
1546    // Stores whether the first child line of any of this line's tokens is
1547    // affected.
1548    bool SomeFirstChildAffected = false;
1549
1550    for (FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
1551      // Determine whether 'Tok' was affected.
1552      if (affectsTokenRange(*Tok, *Tok, IncludeLeadingNewlines))
1553        SomeTokenAffected = true;
1554
1555      // Determine whether the first child of 'Tok' was affected.
1556      if (!Tok->Children.empty() && Tok->Children.front()->Affected)
1557        SomeFirstChildAffected = true;
1558
1559      IncludeLeadingNewlines = Tok->Children.empty();
1560    }
1561
1562    // Was this line moved, i.e. has it previously been on the same line as an
1563    // affected line?
1564    bool LineMoved = PreviousLine && PreviousLine->Affected &&
1565                     Line->First->NewlinesBefore == 0;
1566
1567    bool IsContinuedComment =
1568        Line->First->is(tok::comment) && Line->First->Next == nullptr &&
1569        Line->First->NewlinesBefore < 2 && PreviousLine &&
1570        PreviousLine->Affected && PreviousLine->Last->is(tok::comment);
1571
1572    if (SomeTokenAffected || SomeFirstChildAffected || LineMoved ||
1573        IsContinuedComment) {
1574      Line->Affected = true;
1575      SomeLineAffected = true;
1576    }
1577    return SomeLineAffected;
1578  }
1579
1580  // Marks all lines between I and E as well as all their children as affected.
1581  void markAllAsAffected(SmallVectorImpl<AnnotatedLine *>::iterator I,
1582                         SmallVectorImpl<AnnotatedLine *>::iterator E) {
1583    while (I != E) {
1584      (*I)->Affected = true;
1585      markAllAsAffected((*I)->Children.begin(), (*I)->Children.end());
1586      ++I;
1587    }
1588  }
1589
1590  // Returns true if the range from 'First' to 'Last' intersects with one of the
1591  // input ranges.
1592  bool affectsTokenRange(const FormatToken &First, const FormatToken &Last,
1593                         bool IncludeLeadingNewlines) {
1594    SourceLocation Start = First.WhitespaceRange.getBegin();
1595    if (!IncludeLeadingNewlines)
1596      Start = Start.getLocWithOffset(First.LastNewlineOffset);
1597    SourceLocation End = Last.getStartOfNonWhitespace();
1598    End = End.getLocWithOffset(Last.TokenText.size());
1599    CharSourceRange Range = CharSourceRange::getCharRange(Start, End);
1600    return affectsCharSourceRange(Range);
1601  }
1602
1603  // Returns true if one of the input ranges intersect the leading empty lines
1604  // before 'Tok'.
1605  bool affectsLeadingEmptyLines(const FormatToken &Tok) {
1606    CharSourceRange EmptyLineRange = CharSourceRange::getCharRange(
1607        Tok.WhitespaceRange.getBegin(),
1608        Tok.WhitespaceRange.getBegin().getLocWithOffset(Tok.LastNewlineOffset));
1609    return affectsCharSourceRange(EmptyLineRange);
1610  }
1611
1612  // Returns true if 'Range' intersects with one of the input ranges.
1613  bool affectsCharSourceRange(const CharSourceRange &Range) {
1614    for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
1615                                                          E = Ranges.end();
1616         I != E; ++I) {
1617      if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
1618          !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
1619        return true;
1620    }
1621    return false;
1622  }
1623
1624  static bool inputUsesCRLF(StringRef Text) {
1625    return Text.count('\r') * 2 > Text.count('\n');
1626  }
1627
1628  bool
1629  hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1630    for (const AnnotatedLine* Line : Lines) {
1631      if (hasCpp03IncompatibleFormat(Line->Children))
1632        return true;
1633      for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
1634        if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1635          if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
1636            return true;
1637          if (Tok->is(TT_TemplateCloser) &&
1638              Tok->Previous->is(TT_TemplateCloser))
1639            return true;
1640        }
1641      }
1642    }
1643    return false;
1644  }
1645
1646  int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1647    int AlignmentDiff = 0;
1648    for (const AnnotatedLine* Line : Lines) {
1649      AlignmentDiff += countVariableAlignments(Line->Children);
1650      for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
1651        if (!Tok->is(TT_PointerOrReference))
1652          continue;
1653        bool SpaceBefore =
1654            Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1655        bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
1656                          Tok->Next->WhitespaceRange.getEnd();
1657        if (SpaceBefore && !SpaceAfter)
1658          ++AlignmentDiff;
1659        if (!SpaceBefore && SpaceAfter)
1660          --AlignmentDiff;
1661      }
1662    }
1663    return AlignmentDiff;
1664  }
1665
1666  void
1667  deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1668    bool HasBinPackedFunction = false;
1669    bool HasOnePerLineFunction = false;
1670    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1671      if (!AnnotatedLines[i]->First->Next)
1672        continue;
1673      FormatToken *Tok = AnnotatedLines[i]->First->Next;
1674      while (Tok->Next) {
1675        if (Tok->PackingKind == PPK_BinPacked)
1676          HasBinPackedFunction = true;
1677        if (Tok->PackingKind == PPK_OnePerLine)
1678          HasOnePerLineFunction = true;
1679
1680        Tok = Tok->Next;
1681      }
1682    }
1683    if (Style.DerivePointerAlignment)
1684      Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
1685                                   ? FormatStyle::PAS_Left
1686                                   : FormatStyle::PAS_Right;
1687    if (Style.Standard == FormatStyle::LS_Auto)
1688      Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
1689                           ? FormatStyle::LS_Cpp11
1690                           : FormatStyle::LS_Cpp03;
1691    BinPackInconclusiveFunctions =
1692        HasBinPackedFunction || !HasOnePerLineFunction;
1693  }
1694
1695  void consumeUnwrappedLine(const UnwrappedLine &TheLine) override {
1696    assert(!UnwrappedLines.empty());
1697    UnwrappedLines.back().push_back(TheLine);
1698  }
1699
1700  void finishRun() override {
1701    UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
1702  }
1703
1704  FormatStyle Style;
1705  FileID ID;
1706  SourceManager &SourceMgr;
1707  WhitespaceManager Whitespaces;
1708  SmallVector<CharSourceRange, 8> Ranges;
1709  SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
1710
1711  encoding::Encoding Encoding;
1712  bool BinPackInconclusiveFunctions;
1713};
1714
1715struct IncludeDirective {
1716  StringRef Filename;
1717  StringRef Text;
1718  unsigned Offset;
1719  int Category;
1720};
1721
1722} // end anonymous namespace
1723
1724// Determines whether 'Ranges' intersects with ('Start', 'End').
1725static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
1726                         unsigned End) {
1727  for (auto Range : Ranges) {
1728    if (Range.getOffset() < End &&
1729        Range.getOffset() + Range.getLength() > Start)
1730      return true;
1731  }
1732  return false;
1733}
1734
1735// Sorts a block of includes given by 'Includes' alphabetically adding the
1736// necessary replacement to 'Replaces'. 'Includes' must be in strict source
1737// order.
1738static void sortIncludes(const FormatStyle &Style,
1739                         const SmallVectorImpl<IncludeDirective> &Includes,
1740                         ArrayRef<tooling::Range> Ranges, StringRef FileName,
1741                         tooling::Replacements &Replaces, unsigned *Cursor) {
1742  if (!affectsRange(Ranges, Includes.front().Offset,
1743                    Includes.back().Offset + Includes.back().Text.size()))
1744    return;
1745  SmallVector<unsigned, 16> Indices;
1746  for (unsigned i = 0, e = Includes.size(); i != e; ++i)
1747    Indices.push_back(i);
1748  std::sort(Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
1749    return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
1750           std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
1751  });
1752
1753  // If the #includes are out of order, we generate a single replacement fixing
1754  // the entire block. Otherwise, no replacement is generated.
1755  bool OutOfOrder = false;
1756  for (unsigned i = 1, e = Indices.size(); i != e; ++i) {
1757    if (Indices[i] != i) {
1758      OutOfOrder = true;
1759      break;
1760    }
1761  }
1762  if (!OutOfOrder)
1763    return;
1764
1765  std::string result;
1766  bool CursorMoved = false;
1767  for (unsigned Index : Indices) {
1768    if (!result.empty())
1769      result += "\n";
1770    result += Includes[Index].Text;
1771
1772    if (Cursor && !CursorMoved) {
1773      unsigned Start = Includes[Index].Offset;
1774      unsigned End = Start + Includes[Index].Text.size();
1775      if (*Cursor >= Start && *Cursor < End) {
1776        *Cursor = Includes.front().Offset + result.size() + *Cursor - End;
1777        CursorMoved = true;
1778      }
1779    }
1780  }
1781
1782  // Sorting #includes shouldn't change their total number of characters.
1783  // This would otherwise mess up 'Ranges'.
1784  assert(result.size() ==
1785         Includes.back().Offset + Includes.back().Text.size() -
1786             Includes.front().Offset);
1787
1788  Replaces.insert(tooling::Replacement(FileName, Includes.front().Offset,
1789                                       result.size(), result));
1790}
1791
1792tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
1793                                   ArrayRef<tooling::Range> Ranges,
1794                                   StringRef FileName, unsigned *Cursor) {
1795  tooling::Replacements Replaces;
1796  if (!Style.SortIncludes)
1797    return Replaces;
1798
1799  unsigned Prev = 0;
1800  unsigned SearchFrom = 0;
1801  llvm::Regex IncludeRegex(
1802      R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))");
1803  SmallVector<StringRef, 4> Matches;
1804  SmallVector<IncludeDirective, 16> IncludesInBlock;
1805
1806  // In compiled files, consider the first #include to be the main #include of
1807  // the file if it is not a system #include. This ensures that the header
1808  // doesn't have hidden dependencies
1809  // (http://llvm.org/docs/CodingStandards.html#include-style).
1810  //
1811  // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
1812  // cases where the first #include is unlikely to be the main header.
1813  bool IsSource = FileName.endswith(".c") || FileName.endswith(".cc") ||
1814                  FileName.endswith(".cpp") || FileName.endswith(".c++") ||
1815                  FileName.endswith(".cxx") || FileName.endswith(".m") ||
1816                  FileName.endswith(".mm");
1817  StringRef FileStem = llvm::sys::path::stem(FileName);
1818  bool FirstIncludeBlock = true;
1819  bool MainIncludeFound = false;
1820
1821  // Create pre-compiled regular expressions for the #include categories.
1822  SmallVector<llvm::Regex, 4> CategoryRegexs;
1823  for (const auto &Category : Style.IncludeCategories)
1824    CategoryRegexs.emplace_back(Category.Regex);
1825
1826  bool FormattingOff = false;
1827
1828  for (;;) {
1829    auto Pos = Code.find('\n', SearchFrom);
1830    StringRef Line =
1831        Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
1832
1833    StringRef Trimmed = Line.trim();
1834    if (Trimmed == "// clang-format off")
1835      FormattingOff = true;
1836    else if (Trimmed == "// clang-format on")
1837      FormattingOff = false;
1838
1839    if (!FormattingOff && !Line.endswith("\\")) {
1840      if (IncludeRegex.match(Line, &Matches)) {
1841        StringRef IncludeName = Matches[2];
1842        int Category = INT_MAX;
1843        for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i) {
1844          if (CategoryRegexs[i].match(IncludeName)) {
1845            Category = Style.IncludeCategories[i].Priority;
1846            break;
1847          }
1848        }
1849        if (IsSource && !MainIncludeFound && Category > 0 &&
1850            FirstIncludeBlock && IncludeName.startswith("\"")) {
1851          StringRef HeaderStem =
1852              llvm::sys::path::stem(IncludeName.drop_front(1).drop_back(1));
1853          if (FileStem.startswith(HeaderStem)) {
1854            Category = 0;
1855            MainIncludeFound = true;
1856          }
1857        }
1858        IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
1859      } else if (!IncludesInBlock.empty()) {
1860        sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces,
1861                     Cursor);
1862        IncludesInBlock.clear();
1863        FirstIncludeBlock = false;
1864      }
1865      Prev = Pos + 1;
1866    }
1867    if (Pos == StringRef::npos || Pos + 1 == Code.size())
1868      break;
1869    SearchFrom = Pos + 1;
1870  }
1871  if (!IncludesInBlock.empty())
1872    sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces, Cursor);
1873  return Replaces;
1874}
1875
1876tooling::Replacements reformat(const FormatStyle &Style,
1877                               SourceManager &SourceMgr, FileID ID,
1878                               ArrayRef<CharSourceRange> Ranges,
1879                               bool *IncompleteFormat) {
1880  FormatStyle Expanded = expandPresets(Style);
1881  if (Expanded.DisableFormat)
1882    return tooling::Replacements();
1883  Formatter formatter(Expanded, SourceMgr, ID, Ranges);
1884  return formatter.format(IncompleteFormat);
1885}
1886
1887tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1888                               ArrayRef<tooling::Range> Ranges,
1889                               StringRef FileName, bool *IncompleteFormat) {
1890  if (Style.DisableFormat)
1891    return tooling::Replacements();
1892
1893  IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem(
1894      new vfs::InMemoryFileSystem);
1895  FileManager Files(FileSystemOptions(), InMemoryFileSystem);
1896  DiagnosticsEngine Diagnostics(
1897      IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1898      new DiagnosticOptions);
1899  SourceManager SourceMgr(Diagnostics, Files);
1900  InMemoryFileSystem->addFile(FileName, 0,
1901                              llvm::MemoryBuffer::getMemBuffer(Code, FileName));
1902  FileID ID = SourceMgr.createFileID(Files.getFile(FileName), SourceLocation(),
1903                                     clang::SrcMgr::C_User);
1904  SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1905  std::vector<CharSourceRange> CharRanges;
1906  for (const tooling::Range &Range : Ranges) {
1907    SourceLocation Start = StartOfFile.getLocWithOffset(Range.getOffset());
1908    SourceLocation End = Start.getLocWithOffset(Range.getLength());
1909    CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1910  }
1911  return reformat(Style, SourceMgr, ID, CharRanges, IncompleteFormat);
1912}
1913
1914LangOptions getFormattingLangOpts(const FormatStyle &Style) {
1915  LangOptions LangOpts;
1916  LangOpts.CPlusPlus = 1;
1917  LangOpts.CPlusPlus11 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1918  LangOpts.CPlusPlus14 = Style.Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1919  LangOpts.LineComment = 1;
1920  bool AlternativeOperators = Style.Language == FormatStyle::LK_Cpp;
1921  LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
1922  LangOpts.Bool = 1;
1923  LangOpts.ObjC1 = 1;
1924  LangOpts.ObjC2 = 1;
1925  LangOpts.MicrosoftExt = 1; // To get kw___try, kw___finally.
1926  LangOpts.DeclSpecKeyword = 1; // To get __declspec.
1927  return LangOpts;
1928}
1929
1930const char *StyleOptionHelpDescription =
1931    "Coding style, currently supports:\n"
1932    "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1933    "Use -style=file to load style configuration from\n"
1934    ".clang-format file located in one of the parent\n"
1935    "directories of the source file (or current\n"
1936    "directory for stdin).\n"
1937    "Use -style=\"{key: value, ...}\" to set specific\n"
1938    "parameters, e.g.:\n"
1939    "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1940
1941static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
1942  if (FileName.endswith(".java")) {
1943    return FormatStyle::LK_Java;
1944  } else if (FileName.endswith_lower(".js") || FileName.endswith_lower(".ts")) {
1945    // JavaScript or TypeScript.
1946    return FormatStyle::LK_JavaScript;
1947  } else if (FileName.endswith_lower(".proto") ||
1948             FileName.endswith_lower(".protodevel")) {
1949    return FormatStyle::LK_Proto;
1950  }
1951  return FormatStyle::LK_Cpp;
1952}
1953
1954FormatStyle getStyle(StringRef StyleName, StringRef FileName,
1955                     StringRef FallbackStyle) {
1956  FormatStyle Style = getLLVMStyle();
1957  Style.Language = getLanguageByFileName(FileName);
1958  if (!getPredefinedStyle(FallbackStyle, Style.Language, &Style)) {
1959    llvm::errs() << "Invalid fallback style \"" << FallbackStyle
1960                 << "\" using LLVM style\n";
1961    return Style;
1962  }
1963
1964  if (StyleName.startswith("{")) {
1965    // Parse YAML/JSON style from the command line.
1966    if (std::error_code ec = parseConfiguration(StyleName, &Style)) {
1967      llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
1968                   << FallbackStyle << " style\n";
1969    }
1970    return Style;
1971  }
1972
1973  if (!StyleName.equals_lower("file")) {
1974    if (!getPredefinedStyle(StyleName, Style.Language, &Style))
1975      llvm::errs() << "Invalid value for -style, using " << FallbackStyle
1976                   << " style\n";
1977    return Style;
1978  }
1979
1980  // Look for .clang-format/_clang-format file in the file's parent directories.
1981  SmallString<128> UnsuitableConfigFiles;
1982  SmallString<128> Path(FileName);
1983  llvm::sys::fs::make_absolute(Path);
1984  for (StringRef Directory = Path; !Directory.empty();
1985       Directory = llvm::sys::path::parent_path(Directory)) {
1986    if (!llvm::sys::fs::is_directory(Directory))
1987      continue;
1988    SmallString<128> ConfigFile(Directory);
1989
1990    llvm::sys::path::append(ConfigFile, ".clang-format");
1991    DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1992    bool IsFile = false;
1993    // Ignore errors from is_regular_file: we only need to know if we can read
1994    // the file or not.
1995    llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1996
1997    if (!IsFile) {
1998      // Try _clang-format too, since dotfiles are not commonly used on Windows.
1999      ConfigFile = Directory;
2000      llvm::sys::path::append(ConfigFile, "_clang-format");
2001      DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2002      llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
2003    }
2004
2005    if (IsFile) {
2006      llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2007          llvm::MemoryBuffer::getFile(ConfigFile.c_str());
2008      if (std::error_code EC = Text.getError()) {
2009        llvm::errs() << EC.message() << "\n";
2010        break;
2011      }
2012      if (std::error_code ec =
2013              parseConfiguration(Text.get()->getBuffer(), &Style)) {
2014        if (ec == ParseError::Unsuitable) {
2015          if (!UnsuitableConfigFiles.empty())
2016            UnsuitableConfigFiles.append(", ");
2017          UnsuitableConfigFiles.append(ConfigFile);
2018          continue;
2019        }
2020        llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
2021                     << "\n";
2022        break;
2023      }
2024      DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
2025      return Style;
2026    }
2027  }
2028  if (!UnsuitableConfigFiles.empty()) {
2029    llvm::errs() << "Configuration file(s) do(es) not support "
2030                 << getLanguageName(Style.Language) << ": "
2031                 << UnsuitableConfigFiles << "\n";
2032  }
2033  return Style;
2034}
2035
2036} // namespace format
2037} // namespace clang
2038