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 "UnwrappedLineParser.h"
19#include "WhitespaceManager.h"
20#include "clang/Basic/Diagnostic.h"
21#include "clang/Basic/DiagnosticOptions.h"
22#include "clang/Basic/SourceManager.h"
23#include "clang/Format/Format.h"
24#include "clang/Lex/Lexer.h"
25#include "llvm/ADT/STLExtras.h"
26#include "llvm/Support/Allocator.h"
27#include "llvm/Support/Debug.h"
28#include "llvm/Support/Path.h"
29#include "llvm/Support/YAMLTraits.h"
30#include <queue>
31#include <string>
32
33#define DEBUG_TYPE "format-formatter"
34
35using clang::format::FormatStyle;
36
37LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(std::string)
38
39namespace llvm {
40namespace yaml {
41template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
42  static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
43    IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
44    IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
45    IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
46  }
47};
48
49template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
50  static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
51    IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03);
52    IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03);
53    IO.enumCase(Value, "Cpp11", FormatStyle::LS_Cpp11);
54    IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11);
55    IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
56  }
57};
58
59template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
60  static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
61    IO.enumCase(Value, "Never", FormatStyle::UT_Never);
62    IO.enumCase(Value, "false", FormatStyle::UT_Never);
63    IO.enumCase(Value, "Always", FormatStyle::UT_Always);
64    IO.enumCase(Value, "true", FormatStyle::UT_Always);
65    IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
66  }
67};
68
69template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
70  static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
71    IO.enumCase(Value, "None", FormatStyle::SFS_None);
72    IO.enumCase(Value, "false", FormatStyle::SFS_None);
73    IO.enumCase(Value, "All", FormatStyle::SFS_All);
74    IO.enumCase(Value, "true", FormatStyle::SFS_All);
75    IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
76  }
77};
78
79template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
80  static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
81    IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
82    IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
83    IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
84    IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
85    IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
86  }
87};
88
89template <>
90struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
91  static void enumeration(IO &IO,
92                          FormatStyle::NamespaceIndentationKind &Value) {
93    IO.enumCase(Value, "None", FormatStyle::NI_None);
94    IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
95    IO.enumCase(Value, "All", FormatStyle::NI_All);
96  }
97};
98
99template <>
100struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
101  static void enumeration(IO &IO,
102                          FormatStyle::PointerAlignmentStyle &Value) {
103    IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
104    IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
105    IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
106
107    // For backward compability.
108    IO.enumCase(Value, "true", FormatStyle::PAS_Left);
109    IO.enumCase(Value, "false", FormatStyle::PAS_Right);
110  }
111};
112
113template <>
114struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
115  static void enumeration(IO &IO,
116                          FormatStyle::SpaceBeforeParensOptions &Value) {
117    IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
118    IO.enumCase(Value, "ControlStatements",
119                FormatStyle::SBPO_ControlStatements);
120    IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
121
122    // For backward compatibility.
123    IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
124    IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
125  }
126};
127
128template <> struct MappingTraits<FormatStyle> {
129  static void mapping(IO &IO, FormatStyle &Style) {
130    // When reading, read the language first, we need it for getPredefinedStyle.
131    IO.mapOptional("Language", Style.Language);
132
133    if (IO.outputting()) {
134      StringRef StylesArray[] = { "LLVM",    "Google", "Chromium",
135                                  "Mozilla", "WebKit", "GNU" };
136      ArrayRef<StringRef> Styles(StylesArray);
137      for (size_t i = 0, e = Styles.size(); i < e; ++i) {
138        StringRef StyleName(Styles[i]);
139        FormatStyle PredefinedStyle;
140        if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
141            Style == PredefinedStyle) {
142          IO.mapOptional("# BasedOnStyle", StyleName);
143          break;
144        }
145      }
146    } else {
147      StringRef BasedOnStyle;
148      IO.mapOptional("BasedOnStyle", BasedOnStyle);
149      if (!BasedOnStyle.empty()) {
150        FormatStyle::LanguageKind OldLanguage = Style.Language;
151        FormatStyle::LanguageKind Language =
152            ((FormatStyle *)IO.getContext())->Language;
153        if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
154          IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
155          return;
156        }
157        Style.Language = OldLanguage;
158      }
159    }
160
161    IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
162    IO.mapOptional("ConstructorInitializerIndentWidth",
163                   Style.ConstructorInitializerIndentWidth);
164    IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
165    IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
166    IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
167                   Style.AllowAllParametersOfDeclarationOnNextLine);
168    IO.mapOptional("AllowShortBlocksOnASingleLine",
169                   Style.AllowShortBlocksOnASingleLine);
170    IO.mapOptional("AllowShortIfStatementsOnASingleLine",
171                   Style.AllowShortIfStatementsOnASingleLine);
172    IO.mapOptional("AllowShortLoopsOnASingleLine",
173                   Style.AllowShortLoopsOnASingleLine);
174    IO.mapOptional("AllowShortFunctionsOnASingleLine",
175                   Style.AllowShortFunctionsOnASingleLine);
176    IO.mapOptional("AlwaysBreakTemplateDeclarations",
177                   Style.AlwaysBreakTemplateDeclarations);
178    IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
179                   Style.AlwaysBreakBeforeMultilineStrings);
180    IO.mapOptional("BreakBeforeBinaryOperators",
181                   Style.BreakBeforeBinaryOperators);
182    IO.mapOptional("BreakBeforeTernaryOperators",
183                   Style.BreakBeforeTernaryOperators);
184    IO.mapOptional("BreakConstructorInitializersBeforeComma",
185                   Style.BreakConstructorInitializersBeforeComma);
186    IO.mapOptional("BinPackParameters", Style.BinPackParameters);
187    IO.mapOptional("ColumnLimit", Style.ColumnLimit);
188    IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
189                   Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
190    IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
191    IO.mapOptional("ExperimentalAutoDetectBinPacking",
192                   Style.ExperimentalAutoDetectBinPacking);
193    IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
194    IO.mapOptional("IndentWrappedFunctionNames",
195                   Style.IndentWrappedFunctionNames);
196    IO.mapOptional("IndentFunctionDeclarationAfterType",
197                   Style.IndentWrappedFunctionNames);
198    IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
199    IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
200                   Style.KeepEmptyLinesAtTheStartOfBlocks);
201    IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
202    IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
203    IO.mapOptional("ObjCSpaceBeforeProtocolList",
204                   Style.ObjCSpaceBeforeProtocolList);
205    IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
206                   Style.PenaltyBreakBeforeFirstCallParameter);
207    IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
208    IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
209    IO.mapOptional("PenaltyBreakFirstLessLess",
210                   Style.PenaltyBreakFirstLessLess);
211    IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
212    IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
213                   Style.PenaltyReturnTypeOnItsOwnLine);
214    IO.mapOptional("PointerAlignment", Style.PointerAlignment);
215    IO.mapOptional("SpacesBeforeTrailingComments",
216                   Style.SpacesBeforeTrailingComments);
217    IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
218    IO.mapOptional("Standard", Style.Standard);
219    IO.mapOptional("IndentWidth", Style.IndentWidth);
220    IO.mapOptional("TabWidth", Style.TabWidth);
221    IO.mapOptional("UseTab", Style.UseTab);
222    IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
223    IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
224    IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
225    IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
226    IO.mapOptional("SpacesInCStyleCastParentheses",
227                   Style.SpacesInCStyleCastParentheses);
228    IO.mapOptional("SpacesInContainerLiterals",
229                   Style.SpacesInContainerLiterals);
230    IO.mapOptional("SpaceBeforeAssignmentOperators",
231                   Style.SpaceBeforeAssignmentOperators);
232    IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
233    IO.mapOptional("CommentPragmas", Style.CommentPragmas);
234    IO.mapOptional("ForEachMacros", Style.ForEachMacros);
235
236    // For backward compatibility.
237    if (!IO.outputting()) {
238      IO.mapOptional("SpaceAfterControlStatementKeyword",
239                     Style.SpaceBeforeParens);
240      IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
241      IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
242    }
243    IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
244    IO.mapOptional("DisableFormat", Style.DisableFormat);
245  }
246};
247
248// Allows to read vector<FormatStyle> while keeping default values.
249// IO.getContext() should contain a pointer to the FormatStyle structure, that
250// will be used to get default values for missing keys.
251// If the first element has no Language specified, it will be treated as the
252// default one for the following elements.
253template <> struct DocumentListTraits<std::vector<FormatStyle> > {
254  static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
255    return Seq.size();
256  }
257  static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
258                              size_t Index) {
259    if (Index >= Seq.size()) {
260      assert(Index == Seq.size());
261      FormatStyle Template;
262      if (Seq.size() > 0 && Seq[0].Language == FormatStyle::LK_None) {
263        Template = Seq[0];
264      } else {
265        Template = *((const FormatStyle *)IO.getContext());
266        Template.Language = FormatStyle::LK_None;
267      }
268      Seq.resize(Index + 1, Template);
269    }
270    return Seq[Index];
271  }
272};
273}
274}
275
276namespace clang {
277namespace format {
278
279const std::error_category &getParseCategory() {
280  static ParseErrorCategory C;
281  return C;
282}
283std::error_code make_error_code(ParseError e) {
284  return std::error_code(static_cast<int>(e), getParseCategory());
285}
286
287const char *ParseErrorCategory::name() const LLVM_NOEXCEPT {
288  return "clang-format.parse_error";
289}
290
291std::string ParseErrorCategory::message(int EV) const {
292  switch (static_cast<ParseError>(EV)) {
293  case ParseError::Success:
294    return "Success";
295  case ParseError::Error:
296    return "Invalid argument";
297  case ParseError::Unsuitable:
298    return "Unsuitable";
299  }
300  llvm_unreachable("unexpected parse error");
301}
302
303FormatStyle getLLVMStyle() {
304  FormatStyle LLVMStyle;
305  LLVMStyle.Language = FormatStyle::LK_Cpp;
306  LLVMStyle.AccessModifierOffset = -2;
307  LLVMStyle.AlignEscapedNewlinesLeft = false;
308  LLVMStyle.AlignTrailingComments = true;
309  LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
310  LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
311  LLVMStyle.AllowShortBlocksOnASingleLine = false;
312  LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
313  LLVMStyle.AllowShortLoopsOnASingleLine = false;
314  LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
315  LLVMStyle.AlwaysBreakTemplateDeclarations = false;
316  LLVMStyle.BinPackParameters = true;
317  LLVMStyle.BreakBeforeBinaryOperators = false;
318  LLVMStyle.BreakBeforeTernaryOperators = true;
319  LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
320  LLVMStyle.BreakConstructorInitializersBeforeComma = false;
321  LLVMStyle.ColumnLimit = 80;
322  LLVMStyle.CommentPragmas = "^ IWYU pragma:";
323  LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
324  LLVMStyle.ConstructorInitializerIndentWidth = 4;
325  LLVMStyle.ContinuationIndentWidth = 4;
326  LLVMStyle.Cpp11BracedListStyle = true;
327  LLVMStyle.DerivePointerAlignment = false;
328  LLVMStyle.ExperimentalAutoDetectBinPacking = false;
329  LLVMStyle.ForEachMacros.push_back("foreach");
330  LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
331  LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
332  LLVMStyle.IndentCaseLabels = false;
333  LLVMStyle.IndentWrappedFunctionNames = false;
334  LLVMStyle.IndentWidth = 2;
335  LLVMStyle.TabWidth = 8;
336  LLVMStyle.MaxEmptyLinesToKeep = 1;
337  LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
338  LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
339  LLVMStyle.ObjCSpaceAfterProperty = false;
340  LLVMStyle.ObjCSpaceBeforeProtocolList = true;
341  LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
342  LLVMStyle.SpacesBeforeTrailingComments = 1;
343  LLVMStyle.Standard = FormatStyle::LS_Cpp11;
344  LLVMStyle.UseTab = FormatStyle::UT_Never;
345  LLVMStyle.SpacesInParentheses = false;
346  LLVMStyle.SpaceInEmptyParentheses = false;
347  LLVMStyle.SpacesInContainerLiterals = true;
348  LLVMStyle.SpacesInCStyleCastParentheses = false;
349  LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
350  LLVMStyle.SpaceBeforeAssignmentOperators = true;
351  LLVMStyle.SpacesInAngles = false;
352
353  LLVMStyle.PenaltyBreakComment = 300;
354  LLVMStyle.PenaltyBreakFirstLessLess = 120;
355  LLVMStyle.PenaltyBreakString = 1000;
356  LLVMStyle.PenaltyExcessCharacter = 1000000;
357  LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
358  LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
359
360  LLVMStyle.DisableFormat = false;
361
362  return LLVMStyle;
363}
364
365FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
366  FormatStyle GoogleStyle = getLLVMStyle();
367  GoogleStyle.Language = Language;
368
369  GoogleStyle.AccessModifierOffset = -1;
370  GoogleStyle.AlignEscapedNewlinesLeft = true;
371  GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
372  GoogleStyle.AllowShortLoopsOnASingleLine = true;
373  GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
374  GoogleStyle.AlwaysBreakTemplateDeclarations = true;
375  GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
376  GoogleStyle.DerivePointerAlignment = true;
377  GoogleStyle.IndentCaseLabels = true;
378  GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
379  GoogleStyle.ObjCSpaceAfterProperty = false;
380  GoogleStyle.ObjCSpaceBeforeProtocolList = false;
381  GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
382  GoogleStyle.SpacesBeforeTrailingComments = 2;
383  GoogleStyle.Standard = FormatStyle::LS_Auto;
384
385  GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
386  GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
387
388  if (Language == FormatStyle::LK_JavaScript) {
389    GoogleStyle.BreakBeforeTernaryOperators = false;
390    GoogleStyle.MaxEmptyLinesToKeep = 3;
391    GoogleStyle.SpacesInContainerLiterals = false;
392  } else if (Language == FormatStyle::LK_Proto) {
393    GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
394    GoogleStyle.SpacesInContainerLiterals = false;
395  }
396
397  return GoogleStyle;
398}
399
400FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
401  FormatStyle ChromiumStyle = getGoogleStyle(Language);
402  ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
403  ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
404  ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
405  ChromiumStyle.AllowShortLoopsOnASingleLine = false;
406  ChromiumStyle.BinPackParameters = false;
407  ChromiumStyle.DerivePointerAlignment = false;
408  ChromiumStyle.Standard = FormatStyle::LS_Cpp03;
409  return ChromiumStyle;
410}
411
412FormatStyle getMozillaStyle() {
413  FormatStyle MozillaStyle = getLLVMStyle();
414  MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
415  MozillaStyle.Cpp11BracedListStyle = false;
416  MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
417  MozillaStyle.DerivePointerAlignment = true;
418  MozillaStyle.IndentCaseLabels = true;
419  MozillaStyle.ObjCSpaceAfterProperty = true;
420  MozillaStyle.ObjCSpaceBeforeProtocolList = false;
421  MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
422  MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
423  MozillaStyle.Standard = FormatStyle::LS_Cpp03;
424  return MozillaStyle;
425}
426
427FormatStyle getWebKitStyle() {
428  FormatStyle Style = getLLVMStyle();
429  Style.AccessModifierOffset = -4;
430  Style.AlignTrailingComments = false;
431  Style.BreakBeforeBinaryOperators = true;
432  Style.BreakBeforeBraces = FormatStyle::BS_Stroustrup;
433  Style.BreakConstructorInitializersBeforeComma = true;
434  Style.Cpp11BracedListStyle = false;
435  Style.ColumnLimit = 0;
436  Style.IndentWidth = 4;
437  Style.NamespaceIndentation = FormatStyle::NI_Inner;
438  Style.ObjCSpaceAfterProperty = true;
439  Style.PointerAlignment = FormatStyle::PAS_Left;
440  Style.Standard = FormatStyle::LS_Cpp03;
441  return Style;
442}
443
444FormatStyle getGNUStyle() {
445  FormatStyle Style = getLLVMStyle();
446  Style.BreakBeforeBinaryOperators = true;
447  Style.BreakBeforeBraces = FormatStyle::BS_GNU;
448  Style.BreakBeforeTernaryOperators = true;
449  Style.Cpp11BracedListStyle = false;
450  Style.ColumnLimit = 79;
451  Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
452  Style.Standard = FormatStyle::LS_Cpp03;
453  return Style;
454}
455
456FormatStyle getNoStyle() {
457  FormatStyle NoStyle = getLLVMStyle();
458  NoStyle.DisableFormat = true;
459  return NoStyle;
460}
461
462bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
463                        FormatStyle *Style) {
464  if (Name.equals_lower("llvm")) {
465    *Style = getLLVMStyle();
466  } else if (Name.equals_lower("chromium")) {
467    *Style = getChromiumStyle(Language);
468  } else if (Name.equals_lower("mozilla")) {
469    *Style = getMozillaStyle();
470  } else if (Name.equals_lower("google")) {
471    *Style = getGoogleStyle(Language);
472  } else if (Name.equals_lower("webkit")) {
473    *Style = getWebKitStyle();
474  } else if (Name.equals_lower("gnu")) {
475    *Style = getGNUStyle();
476  } else if (Name.equals_lower("none")) {
477    *Style = getNoStyle();
478  } else {
479    return false;
480  }
481
482  Style->Language = Language;
483  return true;
484}
485
486std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
487  assert(Style);
488  FormatStyle::LanguageKind Language = Style->Language;
489  assert(Language != FormatStyle::LK_None);
490  if (Text.trim().empty())
491    return make_error_code(ParseError::Error);
492
493  std::vector<FormatStyle> Styles;
494  llvm::yaml::Input Input(Text);
495  // DocumentListTraits<vector<FormatStyle>> uses the context to get default
496  // values for the fields, keys for which are missing from the configuration.
497  // Mapping also uses the context to get the language to find the correct
498  // base style.
499  Input.setContext(Style);
500  Input >> Styles;
501  if (Input.error())
502    return Input.error();
503
504  for (unsigned i = 0; i < Styles.size(); ++i) {
505    // Ensures that only the first configuration can skip the Language option.
506    if (Styles[i].Language == FormatStyle::LK_None && i != 0)
507      return make_error_code(ParseError::Error);
508    // Ensure that each language is configured at most once.
509    for (unsigned j = 0; j < i; ++j) {
510      if (Styles[i].Language == Styles[j].Language) {
511        DEBUG(llvm::dbgs()
512              << "Duplicate languages in the config file on positions " << j
513              << " and " << i << "\n");
514        return make_error_code(ParseError::Error);
515      }
516    }
517  }
518  // Look for a suitable configuration starting from the end, so we can
519  // find the configuration for the specific language first, and the default
520  // configuration (which can only be at slot 0) after it.
521  for (int i = Styles.size() - 1; i >= 0; --i) {
522    if (Styles[i].Language == Language ||
523        Styles[i].Language == FormatStyle::LK_None) {
524      *Style = Styles[i];
525      Style->Language = Language;
526      return make_error_code(ParseError::Success);
527    }
528  }
529  return make_error_code(ParseError::Unsuitable);
530}
531
532std::string configurationAsText(const FormatStyle &Style) {
533  std::string Text;
534  llvm::raw_string_ostream Stream(Text);
535  llvm::yaml::Output Output(Stream);
536  // We use the same mapping method for input and output, so we need a non-const
537  // reference here.
538  FormatStyle NonConstStyle = Style;
539  Output << NonConstStyle;
540  return Stream.str();
541}
542
543namespace {
544
545class NoColumnLimitFormatter {
546public:
547  NoColumnLimitFormatter(ContinuationIndenter *Indenter) : Indenter(Indenter) {}
548
549  /// \brief Formats the line starting at \p State, simply keeping all of the
550  /// input's line breaking decisions.
551  void format(unsigned FirstIndent, const AnnotatedLine *Line) {
552    LineState State =
553        Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false);
554    while (State.NextToken) {
555      bool Newline =
556          Indenter->mustBreak(State) ||
557          (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
558      Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
559    }
560  }
561
562private:
563  ContinuationIndenter *Indenter;
564};
565
566class LineJoiner {
567public:
568  LineJoiner(const FormatStyle &Style) : Style(Style) {}
569
570  /// \brief Calculates how many lines can be merged into 1 starting at \p I.
571  unsigned
572  tryFitMultipleLinesInOne(unsigned Indent,
573                           SmallVectorImpl<AnnotatedLine *>::const_iterator I,
574                           SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
575    // We can never merge stuff if there are trailing line comments.
576    const AnnotatedLine *TheLine = *I;
577    if (TheLine->Last->Type == TT_LineComment)
578      return 0;
579
580    if (Style.ColumnLimit > 0 && Indent > Style.ColumnLimit)
581      return 0;
582
583    unsigned Limit =
584        Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;
585    // If we already exceed the column limit, we set 'Limit' to 0. The different
586    // tryMerge..() functions can then decide whether to still do merging.
587    Limit = TheLine->Last->TotalLength > Limit
588                ? 0
589                : Limit - TheLine->Last->TotalLength;
590
591    if (I + 1 == E || I[1]->Type == LT_Invalid || I[1]->First->MustBreakBefore)
592      return 0;
593
594    // FIXME: TheLine->Level != 0 might or might not be the right check to do.
595    // If necessary, change to something smarter.
596    bool MergeShortFunctions =
597        Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_All ||
598        (Style.AllowShortFunctionsOnASingleLine == FormatStyle::SFS_Inline &&
599         TheLine->Level != 0);
600
601    if (TheLine->Last->Type == TT_FunctionLBrace &&
602        TheLine->First != TheLine->Last) {
603      return MergeShortFunctions ? tryMergeSimpleBlock(I, E, Limit) : 0;
604    }
605    if (TheLine->Last->is(tok::l_brace)) {
606      return Style.BreakBeforeBraces == FormatStyle::BS_Attach
607                 ? tryMergeSimpleBlock(I, E, Limit)
608                 : 0;
609    }
610    if (I[1]->First->Type == TT_FunctionLBrace &&
611        Style.BreakBeforeBraces != FormatStyle::BS_Attach) {
612      // Check for Limit <= 2 to account for the " {".
613      if (Limit <= 2 || (Style.ColumnLimit == 0 && containsMustBreak(TheLine)))
614        return 0;
615      Limit -= 2;
616
617      unsigned MergedLines = 0;
618      if (MergeShortFunctions) {
619        MergedLines = tryMergeSimpleBlock(I + 1, E, Limit);
620        // If we managed to merge the block, count the function header, which is
621        // on a separate line.
622        if (MergedLines > 0)
623          ++MergedLines;
624      }
625      return MergedLines;
626    }
627    if (TheLine->First->is(tok::kw_if)) {
628      return Style.AllowShortIfStatementsOnASingleLine
629                 ? tryMergeSimpleControlStatement(I, E, Limit)
630                 : 0;
631    }
632    if (TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
633      return Style.AllowShortLoopsOnASingleLine
634                 ? tryMergeSimpleControlStatement(I, E, Limit)
635                 : 0;
636    }
637    if (TheLine->InPPDirective &&
638        (TheLine->First->HasUnescapedNewline || TheLine->First->IsFirst)) {
639      return tryMergeSimplePPDirective(I, E, Limit);
640    }
641    return 0;
642  }
643
644private:
645  unsigned
646  tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
647                            SmallVectorImpl<AnnotatedLine *>::const_iterator E,
648                            unsigned Limit) {
649    if (Limit == 0)
650      return 0;
651    if (!I[1]->InPPDirective || I[1]->First->HasUnescapedNewline)
652      return 0;
653    if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
654      return 0;
655    if (1 + I[1]->Last->TotalLength > Limit)
656      return 0;
657    return 1;
658  }
659
660  unsigned tryMergeSimpleControlStatement(
661      SmallVectorImpl<AnnotatedLine *>::const_iterator I,
662      SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
663    if (Limit == 0)
664      return 0;
665    if ((Style.BreakBeforeBraces == FormatStyle::BS_Allman ||
666         Style.BreakBeforeBraces == FormatStyle::BS_GNU) &&
667        (I[1]->First->is(tok::l_brace) && !Style.AllowShortBlocksOnASingleLine))
668      return 0;
669    if (I[1]->InPPDirective != (*I)->InPPDirective ||
670        (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline))
671      return 0;
672    Limit = limitConsideringMacros(I + 1, E, Limit);
673    AnnotatedLine &Line = **I;
674    if (Line.Last->isNot(tok::r_paren))
675      return 0;
676    if (1 + I[1]->Last->TotalLength > Limit)
677      return 0;
678    if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
679                             tok::kw_while) ||
680        I[1]->First->Type == TT_LineComment)
681      return 0;
682    // Only inline simple if's (no nested if or else).
683    if (I + 2 != E && Line.First->is(tok::kw_if) &&
684        I[2]->First->is(tok::kw_else))
685      return 0;
686    return 1;
687  }
688
689  unsigned
690  tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
691                      SmallVectorImpl<AnnotatedLine *>::const_iterator E,
692                      unsigned Limit) {
693    AnnotatedLine &Line = **I;
694
695    // Don't merge ObjC @ keywords and methods.
696    if (Line.First->isOneOf(tok::at, tok::minus, tok::plus))
697      return 0;
698
699    // Check that the current line allows merging. This depends on whether we
700    // are in a control flow statements as well as several style flags.
701    if (Line.First->isOneOf(tok::kw_else, tok::kw_case))
702      return 0;
703    if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::kw_try,
704                            tok::kw_catch, tok::kw_for, tok::r_brace)) {
705      if (!Style.AllowShortBlocksOnASingleLine)
706        return 0;
707      if (!Style.AllowShortIfStatementsOnASingleLine &&
708          Line.First->is(tok::kw_if))
709        return 0;
710      if (!Style.AllowShortLoopsOnASingleLine &&
711          Line.First->isOneOf(tok::kw_while, tok::kw_do, tok::kw_for))
712        return 0;
713      // FIXME: Consider an option to allow short exception handling clauses on
714      // a single line.
715      if (Line.First->isOneOf(tok::kw_try, tok::kw_catch))
716        return 0;
717    }
718
719    FormatToken *Tok = I[1]->First;
720    if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
721        (Tok->getNextNonComment() == nullptr ||
722         Tok->getNextNonComment()->is(tok::semi))) {
723      // We merge empty blocks even if the line exceeds the column limit.
724      Tok->SpacesRequiredBefore = 0;
725      Tok->CanBreakBefore = true;
726      return 1;
727    } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace)) {
728      // We don't merge short records.
729      if (Line.First->isOneOf(tok::kw_class, tok::kw_union, tok::kw_struct))
730        return 0;
731
732      // Check that we still have three lines and they fit into the limit.
733      if (I + 2 == E || I[2]->Type == LT_Invalid)
734        return 0;
735      Limit = limitConsideringMacros(I + 2, E, Limit);
736
737      if (!nextTwoLinesFitInto(I, Limit))
738        return 0;
739
740      // Second, check that the next line does not contain any braces - if it
741      // does, readability declines when putting it into a single line.
742      if (I[1]->Last->Type == TT_LineComment)
743        return 0;
744      do {
745        if (Tok->is(tok::l_brace) && Tok->BlockKind != BK_BracedInit)
746          return 0;
747        Tok = Tok->Next;
748      } while (Tok);
749
750      // Last, check that the third line starts with a closing brace.
751      Tok = I[2]->First;
752      if (Tok->isNot(tok::r_brace))
753        return 0;
754
755      return 2;
756    }
757    return 0;
758  }
759
760  /// Returns the modified column limit for \p I if it is inside a macro and
761  /// needs a trailing '\'.
762  unsigned
763  limitConsideringMacros(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
764                         SmallVectorImpl<AnnotatedLine *>::const_iterator E,
765                         unsigned Limit) {
766    if (I[0]->InPPDirective && I + 1 != E &&
767        !I[1]->First->HasUnescapedNewline && !I[1]->First->is(tok::eof)) {
768      return Limit < 2 ? 0 : Limit - 2;
769    }
770    return Limit;
771  }
772
773  bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
774                           unsigned Limit) {
775    if (I[1]->First->MustBreakBefore || I[2]->First->MustBreakBefore)
776      return false;
777    return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
778  }
779
780  bool containsMustBreak(const AnnotatedLine *Line) {
781    for (const FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
782      if (Tok->MustBreakBefore)
783        return true;
784    }
785    return false;
786  }
787
788  const FormatStyle &Style;
789};
790
791class UnwrappedLineFormatter {
792public:
793  UnwrappedLineFormatter(ContinuationIndenter *Indenter,
794                         WhitespaceManager *Whitespaces,
795                         const FormatStyle &Style)
796      : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style),
797        Joiner(Style) {}
798
799  unsigned format(const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun,
800                  int AdditionalIndent = 0, bool FixBadIndentation = false) {
801    // Try to look up already computed penalty in DryRun-mode.
802    std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned> CacheKey(
803        &Lines, AdditionalIndent);
804    auto CacheIt = PenaltyCache.find(CacheKey);
805    if (DryRun && CacheIt != PenaltyCache.end())
806      return CacheIt->second;
807
808    assert(!Lines.empty());
809    unsigned Penalty = 0;
810    std::vector<int> IndentForLevel;
811    for (unsigned i = 0, e = Lines[0]->Level; i != e; ++i)
812      IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);
813    const AnnotatedLine *PreviousLine = nullptr;
814    for (SmallVectorImpl<AnnotatedLine *>::const_iterator I = Lines.begin(),
815                                                          E = Lines.end();
816         I != E; ++I) {
817      const AnnotatedLine &TheLine = **I;
818      const FormatToken *FirstTok = TheLine.First;
819      int Offset = getIndentOffset(*FirstTok);
820
821      // Determine indent and try to merge multiple unwrapped lines.
822      unsigned Indent;
823      if (TheLine.InPPDirective) {
824        Indent = TheLine.Level * Style.IndentWidth;
825      } else {
826        while (IndentForLevel.size() <= TheLine.Level)
827          IndentForLevel.push_back(-1);
828        IndentForLevel.resize(TheLine.Level + 1);
829        Indent = getIndent(IndentForLevel, TheLine.Level);
830      }
831      unsigned LevelIndent = Indent;
832      if (static_cast<int>(Indent) + Offset >= 0)
833        Indent += Offset;
834
835      // Merge multiple lines if possible.
836      unsigned MergedLines = Joiner.tryFitMultipleLinesInOne(Indent, I, E);
837      if (MergedLines > 0 && Style.ColumnLimit == 0) {
838        // Disallow line merging if there is a break at the start of one of the
839        // input lines.
840        for (unsigned i = 0; i < MergedLines; ++i) {
841          if (I[i + 1]->First->NewlinesBefore > 0)
842            MergedLines = 0;
843        }
844      }
845      if (!DryRun) {
846        for (unsigned i = 0; i < MergedLines; ++i) {
847          join(*I[i], *I[i + 1]);
848        }
849      }
850      I += MergedLines;
851
852      bool FixIndentation =
853          FixBadIndentation && (LevelIndent != FirstTok->OriginalColumn);
854      if (TheLine.First->is(tok::eof)) {
855        if (PreviousLine && PreviousLine->Affected && !DryRun) {
856          // Remove the file's trailing whitespace.
857          unsigned Newlines = std::min(FirstTok->NewlinesBefore, 1u);
858          Whitespaces->replaceWhitespace(*TheLine.First, Newlines,
859                                         /*IndentLevel=*/0, /*Spaces=*/0,
860                                         /*TargetColumn=*/0);
861        }
862      } else if (TheLine.Type != LT_Invalid &&
863                 (TheLine.Affected || FixIndentation)) {
864        if (FirstTok->WhitespaceRange.isValid()) {
865          if (!DryRun)
866            formatFirstToken(*TheLine.First, PreviousLine, TheLine.Level,
867                             Indent, TheLine.InPPDirective);
868        } else {
869          Indent = LevelIndent = FirstTok->OriginalColumn;
870        }
871
872        // If everything fits on a single line, just put it there.
873        unsigned ColumnLimit = Style.ColumnLimit;
874        if (I + 1 != E) {
875          AnnotatedLine *NextLine = I[1];
876          if (NextLine->InPPDirective && !NextLine->First->HasUnescapedNewline)
877            ColumnLimit = getColumnLimit(TheLine.InPPDirective);
878        }
879
880        if (TheLine.Last->TotalLength + Indent <= ColumnLimit) {
881          LineState State = Indenter->getInitialState(Indent, &TheLine, DryRun);
882          while (State.NextToken) {
883            formatChildren(State, /*Newline=*/false, /*DryRun=*/false, Penalty);
884            Indenter->addTokenToState(State, /*Newline=*/false, DryRun);
885          }
886        } else if (Style.ColumnLimit == 0) {
887          // FIXME: Implement nested blocks for ColumnLimit = 0.
888          NoColumnLimitFormatter Formatter(Indenter);
889          if (!DryRun)
890            Formatter.format(Indent, &TheLine);
891        } else {
892          Penalty += format(TheLine, Indent, DryRun);
893        }
894
895        if (!TheLine.InPPDirective)
896          IndentForLevel[TheLine.Level] = LevelIndent;
897      } else if (TheLine.ChildrenAffected) {
898        format(TheLine.Children, DryRun);
899      } else {
900        // Format the first token if necessary, and notify the WhitespaceManager
901        // about the unchanged whitespace.
902        for (FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next) {
903          if (Tok == TheLine.First &&
904              (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
905            unsigned LevelIndent = Tok->OriginalColumn;
906            if (!DryRun) {
907              // Remove trailing whitespace of the previous line.
908              if ((PreviousLine && PreviousLine->Affected) ||
909                  TheLine.LeadingEmptyLinesAffected) {
910                formatFirstToken(*Tok, PreviousLine, TheLine.Level, LevelIndent,
911                                 TheLine.InPPDirective);
912              } else {
913                Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
914              }
915            }
916
917            if (static_cast<int>(LevelIndent) - Offset >= 0)
918              LevelIndent -= Offset;
919            if (Tok->isNot(tok::comment) && !TheLine.InPPDirective)
920              IndentForLevel[TheLine.Level] = LevelIndent;
921          } else if (!DryRun) {
922            Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
923          }
924        }
925      }
926      if (!DryRun) {
927        for (FormatToken *Tok = TheLine.First; Tok; Tok = Tok->Next) {
928          Tok->Finalized = true;
929        }
930      }
931      PreviousLine = *I;
932    }
933    PenaltyCache[CacheKey] = Penalty;
934    return Penalty;
935  }
936
937private:
938  /// \brief Formats an \c AnnotatedLine and returns the penalty.
939  ///
940  /// If \p DryRun is \c false, directly applies the changes.
941  unsigned format(const AnnotatedLine &Line, unsigned FirstIndent,
942                  bool DryRun) {
943    LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun);
944
945    // If the ObjC method declaration does not fit on a line, we should format
946    // it with one arg per line.
947    if (State.Line->Type == LT_ObjCMethodDecl)
948      State.Stack.back().BreakBeforeParameter = true;
949
950    // Find best solution in solution space.
951    return analyzeSolutionSpace(State, DryRun);
952  }
953
954  /// \brief An edge in the solution space from \c Previous->State to \c State,
955  /// inserting a newline dependent on the \c NewLine.
956  struct StateNode {
957    StateNode(const LineState &State, bool NewLine, StateNode *Previous)
958        : State(State), NewLine(NewLine), Previous(Previous) {}
959    LineState State;
960    bool NewLine;
961    StateNode *Previous;
962  };
963
964  /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
965  ///
966  /// In case of equal penalties, we want to prefer states that were inserted
967  /// first. During state generation we make sure that we insert states first
968  /// that break the line as late as possible.
969  typedef std::pair<unsigned, unsigned> OrderedPenalty;
970
971  /// \brief An item in the prioritized BFS search queue. The \c StateNode's
972  /// \c State has the given \c OrderedPenalty.
973  typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
974
975  /// \brief The BFS queue type.
976  typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
977                              std::greater<QueueItem> > QueueType;
978
979  /// \brief Get the offset of the line relatively to the level.
980  ///
981  /// For example, 'public:' labels in classes are offset by 1 or 2
982  /// characters to the left from their level.
983  int getIndentOffset(const FormatToken &RootToken) {
984    if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
985      return Style.AccessModifierOffset;
986    return 0;
987  }
988
989  /// \brief Add a new line and the required indent before the first Token
990  /// of the \c UnwrappedLine if there was no structural parsing error.
991  void formatFirstToken(FormatToken &RootToken,
992                        const AnnotatedLine *PreviousLine, unsigned IndentLevel,
993                        unsigned Indent, bool InPPDirective) {
994    unsigned Newlines =
995        std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
996    // Remove empty lines before "}" where applicable.
997    if (RootToken.is(tok::r_brace) &&
998        (!RootToken.Next ||
999         (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
1000      Newlines = std::min(Newlines, 1u);
1001    if (Newlines == 0 && !RootToken.IsFirst)
1002      Newlines = 1;
1003    if (RootToken.IsFirst && !RootToken.HasUnescapedNewline)
1004      Newlines = 0;
1005
1006    // Remove empty lines after "{".
1007    if (!Style.KeepEmptyLinesAtTheStartOfBlocks && PreviousLine &&
1008        PreviousLine->Last->is(tok::l_brace) &&
1009        PreviousLine->First->isNot(tok::kw_namespace))
1010      Newlines = 1;
1011
1012    // Insert extra new line before access specifiers.
1013    if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
1014        RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
1015      ++Newlines;
1016
1017    // Remove empty lines after access specifiers.
1018    if (PreviousLine && PreviousLine->First->isAccessSpecifier())
1019      Newlines = std::min(1u, Newlines);
1020
1021    Whitespaces->replaceWhitespace(RootToken, Newlines, IndentLevel, Indent,
1022                                   Indent, InPPDirective &&
1023                                               !RootToken.HasUnescapedNewline);
1024  }
1025
1026  /// \brief Get the indent of \p Level from \p IndentForLevel.
1027  ///
1028  /// \p IndentForLevel must contain the indent for the level \c l
1029  /// at \p IndentForLevel[l], or a value < 0 if the indent for
1030  /// that level is unknown.
1031  unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
1032    if (IndentForLevel[Level] != -1)
1033      return IndentForLevel[Level];
1034    if (Level == 0)
1035      return 0;
1036    return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
1037  }
1038
1039  void join(AnnotatedLine &A, const AnnotatedLine &B) {
1040    assert(!A.Last->Next);
1041    assert(!B.First->Previous);
1042    if (B.Affected)
1043      A.Affected = true;
1044    A.Last->Next = B.First;
1045    B.First->Previous = A.Last;
1046    B.First->CanBreakBefore = true;
1047    unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
1048    for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
1049      Tok->TotalLength += LengthA;
1050      A.Last = Tok;
1051    }
1052  }
1053
1054  unsigned getColumnLimit(bool InPPDirective) const {
1055    // In preprocessor directives reserve two chars for trailing " \"
1056    return Style.ColumnLimit - (InPPDirective ? 2 : 0);
1057  }
1058
1059  struct CompareLineStatePointers {
1060    bool operator()(LineState *obj1, LineState *obj2) const {
1061      return *obj1 < *obj2;
1062    }
1063  };
1064
1065  /// \brief Analyze the entire solution space starting from \p InitialState.
1066  ///
1067  /// This implements a variant of Dijkstra's algorithm on the graph that spans
1068  /// the solution space (\c LineStates are the nodes). The algorithm tries to
1069  /// find the shortest path (the one with lowest penalty) from \p InitialState
1070  /// to a state where all tokens are placed. Returns the penalty.
1071  ///
1072  /// If \p DryRun is \c false, directly applies the changes.
1073  unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false) {
1074    std::set<LineState *, CompareLineStatePointers> Seen;
1075
1076    // Increasing count of \c StateNode items we have created. This is used to
1077    // create a deterministic order independent of the container.
1078    unsigned Count = 0;
1079    QueueType Queue;
1080
1081    // Insert start element into queue.
1082    StateNode *Node =
1083        new (Allocator.Allocate()) StateNode(InitialState, false, nullptr);
1084    Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
1085    ++Count;
1086
1087    unsigned Penalty = 0;
1088
1089    // While not empty, take first element and follow edges.
1090    while (!Queue.empty()) {
1091      Penalty = Queue.top().first.first;
1092      StateNode *Node = Queue.top().second;
1093      if (!Node->State.NextToken) {
1094        DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
1095        break;
1096      }
1097      Queue.pop();
1098
1099      // Cut off the analysis of certain solutions if the analysis gets too
1100      // complex. See description of IgnoreStackForComparison.
1101      if (Count > 10000)
1102        Node->State.IgnoreStackForComparison = true;
1103
1104      if (!Seen.insert(&Node->State).second)
1105        // State already examined with lower penalty.
1106        continue;
1107
1108      FormatDecision LastFormat = Node->State.NextToken->Decision;
1109      if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
1110        addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
1111      if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
1112        addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
1113    }
1114
1115    if (Queue.empty()) {
1116      // We were unable to find a solution, do nothing.
1117      // FIXME: Add diagnostic?
1118      DEBUG(llvm::dbgs() << "Could not find a solution.\n");
1119      return 0;
1120    }
1121
1122    // Reconstruct the solution.
1123    if (!DryRun)
1124      reconstructPath(InitialState, Queue.top().second);
1125
1126    DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
1127    DEBUG(llvm::dbgs() << "---\n");
1128
1129    return Penalty;
1130  }
1131
1132  void reconstructPath(LineState &State, StateNode *Current) {
1133    std::deque<StateNode *> Path;
1134    // We do not need a break before the initial token.
1135    while (Current->Previous) {
1136      Path.push_front(Current);
1137      Current = Current->Previous;
1138    }
1139    for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
1140         I != E; ++I) {
1141      unsigned Penalty = 0;
1142      formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
1143      Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
1144
1145      DEBUG({
1146        if ((*I)->NewLine) {
1147          llvm::dbgs() << "Penalty for placing "
1148                       << (*I)->Previous->State.NextToken->Tok.getName() << ": "
1149                       << Penalty << "\n";
1150        }
1151      });
1152    }
1153  }
1154
1155  /// \brief Add the following state to the analysis queue \c Queue.
1156  ///
1157  /// Assume the current state is \p PreviousNode and has been reached with a
1158  /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
1159  void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
1160                           bool NewLine, unsigned *Count, QueueType *Queue) {
1161    if (NewLine && !Indenter->canBreak(PreviousNode->State))
1162      return;
1163    if (!NewLine && Indenter->mustBreak(PreviousNode->State))
1164      return;
1165
1166    StateNode *Node = new (Allocator.Allocate())
1167        StateNode(PreviousNode->State, NewLine, PreviousNode);
1168    if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
1169      return;
1170
1171    Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
1172
1173    Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
1174    ++(*Count);
1175  }
1176
1177  /// \brief If the \p State's next token is an r_brace closing a nested block,
1178  /// format the nested block before it.
1179  ///
1180  /// Returns \c true if all children could be placed successfully and adapts
1181  /// \p Penalty as well as \p State. If \p DryRun is false, also directly
1182  /// creates changes using \c Whitespaces.
1183  ///
1184  /// The crucial idea here is that children always get formatted upon
1185  /// encountering the closing brace right after the nested block. Now, if we
1186  /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
1187  /// \c false), the entire block has to be kept on the same line (which is only
1188  /// possible if it fits on the line, only contains a single statement, etc.
1189  ///
1190  /// If \p NewLine is true, we format the nested block on separate lines, i.e.
1191  /// break after the "{", format all lines with correct indentation and the put
1192  /// the closing "}" on yet another new line.
1193  ///
1194  /// This enables us to keep the simple structure of the
1195  /// \c UnwrappedLineFormatter, where we only have two options for each token:
1196  /// break or don't break.
1197  bool formatChildren(LineState &State, bool NewLine, bool DryRun,
1198                      unsigned &Penalty) {
1199    FormatToken &Previous = *State.NextToken->Previous;
1200    const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
1201    if (!LBrace || LBrace->isNot(tok::l_brace) ||
1202        LBrace->BlockKind != BK_Block || Previous.Children.size() == 0)
1203      // The previous token does not open a block. Nothing to do. We don't
1204      // assert so that we can simply call this function for all tokens.
1205      return true;
1206
1207    if (NewLine) {
1208      int AdditionalIndent =
1209          State.FirstIndent - State.Line->Level * Style.IndentWidth;
1210      if (State.Stack.size() < 2 ||
1211          !State.Stack[State.Stack.size() - 2].JSFunctionInlined) {
1212        AdditionalIndent = State.Stack.back().Indent -
1213                           Previous.Children[0]->Level * Style.IndentWidth;
1214      }
1215
1216      Penalty += format(Previous.Children, DryRun, AdditionalIndent,
1217                        /*FixBadIndentation=*/true);
1218      return true;
1219    }
1220
1221    // Cannot merge multiple statements into a single line.
1222    if (Previous.Children.size() > 1)
1223      return false;
1224
1225    // Cannot merge into one line if this line ends on a comment.
1226    if (Previous.is(tok::comment))
1227      return false;
1228
1229    // We can't put the closing "}" on a line with a trailing comment.
1230    if (Previous.Children[0]->Last->isTrailingComment())
1231      return false;
1232
1233    // If the child line exceeds the column limit, we wouldn't want to merge it.
1234    // We add +2 for the trailing " }".
1235    if (Style.ColumnLimit > 0 &&
1236        Previous.Children[0]->Last->TotalLength + State.Column + 2 >
1237            Style.ColumnLimit)
1238      return false;
1239
1240    if (!DryRun) {
1241      Whitespaces->replaceWhitespace(
1242          *Previous.Children[0]->First,
1243          /*Newlines=*/0, /*IndentLevel=*/0, /*Spaces=*/1,
1244          /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
1245    }
1246    Penalty += format(*Previous.Children[0], State.Column + 1, DryRun);
1247
1248    State.Column += 1 + Previous.Children[0]->Last->TotalLength;
1249    return true;
1250  }
1251
1252  ContinuationIndenter *Indenter;
1253  WhitespaceManager *Whitespaces;
1254  FormatStyle Style;
1255  LineJoiner Joiner;
1256
1257  llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
1258
1259  // Cache to store the penalty of formatting a vector of AnnotatedLines
1260  // starting from a specific additional offset. Improves performance if there
1261  // are many nested blocks.
1262  std::map<std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned>,
1263           unsigned> PenaltyCache;
1264};
1265
1266class FormatTokenLexer {
1267public:
1268  FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr, FormatStyle &Style,
1269                   encoding::Encoding Encoding)
1270      : FormatTok(nullptr), IsFirstToken(true), GreaterStashed(false),
1271        Column(0), TrailingWhitespace(0), Lex(Lex), SourceMgr(SourceMgr),
1272        Style(Style), IdentTable(getFormattingLangOpts()), Encoding(Encoding),
1273        FirstInLineIndex(0) {
1274    Lex.SetKeepWhitespaceMode(true);
1275
1276    for (const std::string &ForEachMacro : Style.ForEachMacros)
1277      ForEachMacros.push_back(&IdentTable.get(ForEachMacro));
1278    std::sort(ForEachMacros.begin(), ForEachMacros.end());
1279  }
1280
1281  ArrayRef<FormatToken *> lex() {
1282    assert(Tokens.empty());
1283    assert(FirstInLineIndex == 0);
1284    do {
1285      Tokens.push_back(getNextToken());
1286      tryMergePreviousTokens();
1287      if (Tokens.back()->NewlinesBefore > 0)
1288        FirstInLineIndex = Tokens.size() - 1;
1289    } while (Tokens.back()->Tok.isNot(tok::eof));
1290    return Tokens;
1291  }
1292
1293  IdentifierTable &getIdentTable() { return IdentTable; }
1294
1295private:
1296  void tryMergePreviousTokens() {
1297    if (tryMerge_TMacro())
1298      return;
1299    if (tryMergeConflictMarkers())
1300      return;
1301
1302    if (Style.Language == FormatStyle::LK_JavaScript) {
1303      if (tryMergeEscapeSequence())
1304        return;
1305      if (tryMergeJSRegexLiteral())
1306        return;
1307
1308      static tok::TokenKind JSIdentity[] = { tok::equalequal, tok::equal };
1309      static tok::TokenKind JSNotIdentity[] = { tok::exclaimequal, tok::equal };
1310      static tok::TokenKind JSShiftEqual[] = { tok::greater, tok::greater,
1311                                               tok::greaterequal };
1312      static tok::TokenKind JSRightArrow[] = { tok::equal, tok::greater };
1313      // FIXME: We probably need to change token type to mimic operator with the
1314      // correct priority.
1315      if (tryMergeTokens(JSIdentity))
1316        return;
1317      if (tryMergeTokens(JSNotIdentity))
1318        return;
1319      if (tryMergeTokens(JSShiftEqual))
1320        return;
1321      if (tryMergeTokens(JSRightArrow))
1322        return;
1323    }
1324  }
1325
1326  bool tryMergeTokens(ArrayRef<tok::TokenKind> Kinds) {
1327    if (Tokens.size() < Kinds.size())
1328      return false;
1329
1330    SmallVectorImpl<FormatToken *>::const_iterator First =
1331        Tokens.end() - Kinds.size();
1332    if (!First[0]->is(Kinds[0]))
1333      return false;
1334    unsigned AddLength = 0;
1335    for (unsigned i = 1; i < Kinds.size(); ++i) {
1336      if (!First[i]->is(Kinds[i]) || First[i]->WhitespaceRange.getBegin() !=
1337                                         First[i]->WhitespaceRange.getEnd())
1338        return false;
1339      AddLength += First[i]->TokenText.size();
1340    }
1341    Tokens.resize(Tokens.size() - Kinds.size() + 1);
1342    First[0]->TokenText = StringRef(First[0]->TokenText.data(),
1343                                    First[0]->TokenText.size() + AddLength);
1344    First[0]->ColumnWidth += AddLength;
1345    return true;
1346  }
1347
1348  // Tries to merge an escape sequence, i.e. a "\\" and the following
1349  // character. Use e.g. inside JavaScript regex literals.
1350  bool tryMergeEscapeSequence() {
1351    if (Tokens.size() < 2)
1352      return false;
1353    FormatToken *Previous = Tokens[Tokens.size() - 2];
1354    if (Previous->isNot(tok::unknown) || Previous->TokenText != "\\" ||
1355        Tokens.back()->NewlinesBefore != 0)
1356      return false;
1357    Previous->ColumnWidth += Tokens.back()->ColumnWidth;
1358    StringRef Text = Previous->TokenText;
1359    Previous->TokenText =
1360        StringRef(Text.data(), Text.size() + Tokens.back()->TokenText.size());
1361    Tokens.resize(Tokens.size() - 1);
1362    return true;
1363  }
1364
1365  // Try to determine whether the current token ends a JavaScript regex literal.
1366  // We heuristically assume that this is a regex literal if we find two
1367  // unescaped slashes on a line and the token before the first slash is one of
1368  // "(;,{}![:?", a binary operator or 'return', as those cannot be followed by
1369  // a division.
1370  bool tryMergeJSRegexLiteral() {
1371    if (Tokens.size() < 2 || Tokens.back()->isNot(tok::slash) ||
1372        (Tokens[Tokens.size() - 2]->is(tok::unknown) &&
1373         Tokens[Tokens.size() - 2]->TokenText == "\\"))
1374      return false;
1375    unsigned TokenCount = 0;
1376    unsigned LastColumn = Tokens.back()->OriginalColumn;
1377    for (auto I = Tokens.rbegin() + 1, E = Tokens.rend(); I != E; ++I) {
1378      ++TokenCount;
1379      if (I[0]->is(tok::slash) && I + 1 != E &&
1380          (I[1]->isOneOf(tok::l_paren, tok::semi, tok::l_brace, tok::r_brace,
1381                         tok::exclaim, tok::l_square, tok::colon, tok::comma,
1382                         tok::question, tok::kw_return) ||
1383           I[1]->isBinaryOperator())) {
1384        Tokens.resize(Tokens.size() - TokenCount);
1385        Tokens.back()->Tok.setKind(tok::unknown);
1386        Tokens.back()->Type = TT_RegexLiteral;
1387        Tokens.back()->ColumnWidth += LastColumn - I[0]->OriginalColumn;
1388        return true;
1389      }
1390
1391      // There can't be a newline inside a regex literal.
1392      if (I[0]->NewlinesBefore > 0)
1393        return false;
1394    }
1395    return false;
1396  }
1397
1398  bool tryMerge_TMacro() {
1399    if (Tokens.size() < 4)
1400      return false;
1401    FormatToken *Last = Tokens.back();
1402    if (!Last->is(tok::r_paren))
1403      return false;
1404
1405    FormatToken *String = Tokens[Tokens.size() - 2];
1406    if (!String->is(tok::string_literal) || String->IsMultiline)
1407      return false;
1408
1409    if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
1410      return false;
1411
1412    FormatToken *Macro = Tokens[Tokens.size() - 4];
1413    if (Macro->TokenText != "_T")
1414      return false;
1415
1416    const char *Start = Macro->TokenText.data();
1417    const char *End = Last->TokenText.data() + Last->TokenText.size();
1418    String->TokenText = StringRef(Start, End - Start);
1419    String->IsFirst = Macro->IsFirst;
1420    String->LastNewlineOffset = Macro->LastNewlineOffset;
1421    String->WhitespaceRange = Macro->WhitespaceRange;
1422    String->OriginalColumn = Macro->OriginalColumn;
1423    String->ColumnWidth = encoding::columnWidthWithTabs(
1424        String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
1425
1426    Tokens.pop_back();
1427    Tokens.pop_back();
1428    Tokens.pop_back();
1429    Tokens.back() = String;
1430    return true;
1431  }
1432
1433  bool tryMergeConflictMarkers() {
1434    if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(tok::eof))
1435      return false;
1436
1437    // Conflict lines look like:
1438    // <marker> <text from the vcs>
1439    // For example:
1440    // >>>>>>> /file/in/file/system at revision 1234
1441    //
1442    // We merge all tokens in a line that starts with a conflict marker
1443    // into a single token with a special token type that the unwrapped line
1444    // parser will use to correctly rebuild the underlying code.
1445
1446    FileID ID;
1447    // Get the position of the first token in the line.
1448    unsigned FirstInLineOffset;
1449    std::tie(ID, FirstInLineOffset) = SourceMgr.getDecomposedLoc(
1450        Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
1451    StringRef Buffer = SourceMgr.getBuffer(ID)->getBuffer();
1452    // Calculate the offset of the start of the current line.
1453    auto LineOffset = Buffer.rfind('\n', FirstInLineOffset);
1454    if (LineOffset == StringRef::npos) {
1455      LineOffset = 0;
1456    } else {
1457      ++LineOffset;
1458    }
1459
1460    auto FirstSpace = Buffer.find_first_of(" \n", LineOffset);
1461    StringRef LineStart;
1462    if (FirstSpace == StringRef::npos) {
1463      LineStart = Buffer.substr(LineOffset);
1464    } else {
1465      LineStart = Buffer.substr(LineOffset, FirstSpace - LineOffset);
1466    }
1467
1468    TokenType Type = TT_Unknown;
1469    if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
1470      Type = TT_ConflictStart;
1471    } else if (LineStart == "|||||||" || LineStart == "=======" ||
1472               LineStart == "====") {
1473      Type = TT_ConflictAlternative;
1474    } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
1475      Type = TT_ConflictEnd;
1476    }
1477
1478    if (Type != TT_Unknown) {
1479      FormatToken *Next = Tokens.back();
1480
1481      Tokens.resize(FirstInLineIndex + 1);
1482      // We do not need to build a complete token here, as we will skip it
1483      // during parsing anyway (as we must not touch whitespace around conflict
1484      // markers).
1485      Tokens.back()->Type = Type;
1486      Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
1487
1488      Tokens.push_back(Next);
1489      return true;
1490    }
1491
1492    return false;
1493  }
1494
1495  FormatToken *getNextToken() {
1496    if (GreaterStashed) {
1497      // Create a synthesized second '>' token.
1498      // FIXME: Increment Column and set OriginalColumn.
1499      Token Greater = FormatTok->Tok;
1500      FormatTok = new (Allocator.Allocate()) FormatToken;
1501      FormatTok->Tok = Greater;
1502      SourceLocation GreaterLocation =
1503          FormatTok->Tok.getLocation().getLocWithOffset(1);
1504      FormatTok->WhitespaceRange =
1505          SourceRange(GreaterLocation, GreaterLocation);
1506      FormatTok->TokenText = ">";
1507      FormatTok->ColumnWidth = 1;
1508      GreaterStashed = false;
1509      return FormatTok;
1510    }
1511
1512    FormatTok = new (Allocator.Allocate()) FormatToken;
1513    readRawToken(*FormatTok);
1514    SourceLocation WhitespaceStart =
1515        FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
1516    FormatTok->IsFirst = IsFirstToken;
1517    IsFirstToken = false;
1518
1519    // Consume and record whitespace until we find a significant token.
1520    unsigned WhitespaceLength = TrailingWhitespace;
1521    while (FormatTok->Tok.is(tok::unknown)) {
1522      for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) {
1523        switch (FormatTok->TokenText[i]) {
1524        case '\n':
1525          ++FormatTok->NewlinesBefore;
1526          // FIXME: This is technically incorrect, as it could also
1527          // be a literal backslash at the end of the line.
1528          if (i == 0 || (FormatTok->TokenText[i - 1] != '\\' &&
1529                         (FormatTok->TokenText[i - 1] != '\r' || i == 1 ||
1530                          FormatTok->TokenText[i - 2] != '\\')))
1531            FormatTok->HasUnescapedNewline = true;
1532          FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1533          Column = 0;
1534          break;
1535        case '\r':
1536        case '\f':
1537        case '\v':
1538          Column = 0;
1539          break;
1540        case ' ':
1541          ++Column;
1542          break;
1543        case '\t':
1544          Column += Style.TabWidth - Column % Style.TabWidth;
1545          break;
1546        case '\\':
1547          ++Column;
1548          if (i + 1 == e || (FormatTok->TokenText[i + 1] != '\r' &&
1549                             FormatTok->TokenText[i + 1] != '\n'))
1550            FormatTok->Type = TT_ImplicitStringLiteral;
1551          break;
1552        default:
1553          FormatTok->Type = TT_ImplicitStringLiteral;
1554          ++Column;
1555          break;
1556        }
1557      }
1558
1559      if (FormatTok->Type == TT_ImplicitStringLiteral)
1560        break;
1561      WhitespaceLength += FormatTok->Tok.getLength();
1562
1563      readRawToken(*FormatTok);
1564    }
1565
1566    // In case the token starts with escaped newlines, we want to
1567    // take them into account as whitespace - this pattern is quite frequent
1568    // in macro definitions.
1569    // FIXME: Add a more explicit test.
1570    while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
1571           FormatTok->TokenText[1] == '\n') {
1572      ++FormatTok->NewlinesBefore;
1573      WhitespaceLength += 2;
1574      Column = 0;
1575      FormatTok->TokenText = FormatTok->TokenText.substr(2);
1576    }
1577
1578    FormatTok->WhitespaceRange = SourceRange(
1579        WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1580
1581    FormatTok->OriginalColumn = Column;
1582
1583    TrailingWhitespace = 0;
1584    if (FormatTok->Tok.is(tok::comment)) {
1585      // FIXME: Add the trimmed whitespace to Column.
1586      StringRef UntrimmedText = FormatTok->TokenText;
1587      FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
1588      TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1589    } else if (FormatTok->Tok.is(tok::raw_identifier)) {
1590      IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
1591      FormatTok->Tok.setIdentifierInfo(&Info);
1592      FormatTok->Tok.setKind(Info.getTokenID());
1593    } else if (FormatTok->Tok.is(tok::greatergreater)) {
1594      FormatTok->Tok.setKind(tok::greater);
1595      FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1596      GreaterStashed = true;
1597    }
1598
1599    // Now FormatTok is the next non-whitespace token.
1600
1601    StringRef Text = FormatTok->TokenText;
1602    size_t FirstNewlinePos = Text.find('\n');
1603    if (FirstNewlinePos == StringRef::npos) {
1604      // FIXME: ColumnWidth actually depends on the start column, we need to
1605      // take this into account when the token is moved.
1606      FormatTok->ColumnWidth =
1607          encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
1608      Column += FormatTok->ColumnWidth;
1609    } else {
1610      FormatTok->IsMultiline = true;
1611      // FIXME: ColumnWidth actually depends on the start column, we need to
1612      // take this into account when the token is moved.
1613      FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1614          Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
1615
1616      // The last line of the token always starts in column 0.
1617      // Thus, the length can be precomputed even in the presence of tabs.
1618      FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1619          Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
1620          Encoding);
1621      Column = FormatTok->LastLineColumnWidth;
1622    }
1623
1624    FormatTok->IsForEachMacro =
1625        std::binary_search(ForEachMacros.begin(), ForEachMacros.end(),
1626                           FormatTok->Tok.getIdentifierInfo());
1627
1628    return FormatTok;
1629  }
1630
1631  FormatToken *FormatTok;
1632  bool IsFirstToken;
1633  bool GreaterStashed;
1634  unsigned Column;
1635  unsigned TrailingWhitespace;
1636  Lexer &Lex;
1637  SourceManager &SourceMgr;
1638  FormatStyle &Style;
1639  IdentifierTable IdentTable;
1640  encoding::Encoding Encoding;
1641  llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
1642  // Index (in 'Tokens') of the last token that starts a new line.
1643  unsigned FirstInLineIndex;
1644  SmallVector<FormatToken *, 16> Tokens;
1645  SmallVector<IdentifierInfo *, 8> ForEachMacros;
1646
1647  void readRawToken(FormatToken &Tok) {
1648    Lex.LexFromRawLexer(Tok.Tok);
1649    Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
1650                              Tok.Tok.getLength());
1651    // For formatting, treat unterminated string literals like normal string
1652    // literals.
1653    if (Tok.is(tok::unknown)) {
1654      if (!Tok.TokenText.empty() && Tok.TokenText[0] == '"') {
1655        Tok.Tok.setKind(tok::string_literal);
1656        Tok.IsUnterminatedLiteral = true;
1657      } else if (Style.Language == FormatStyle::LK_JavaScript &&
1658                 Tok.TokenText == "''") {
1659        Tok.Tok.setKind(tok::char_constant);
1660      }
1661    }
1662  }
1663};
1664
1665static StringRef getLanguageName(FormatStyle::LanguageKind Language) {
1666  switch (Language) {
1667  case FormatStyle::LK_Cpp:
1668    return "C++";
1669  case FormatStyle::LK_JavaScript:
1670    return "JavaScript";
1671  case FormatStyle::LK_Proto:
1672    return "Proto";
1673  default:
1674    return "Unknown";
1675  }
1676}
1677
1678class Formatter : public UnwrappedLineConsumer {
1679public:
1680  Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
1681            const std::vector<CharSourceRange> &Ranges)
1682      : Style(Style), Lex(Lex), SourceMgr(SourceMgr),
1683        Whitespaces(SourceMgr, Style, inputUsesCRLF(Lex.getBuffer())),
1684        Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1),
1685        Encoding(encoding::detectEncoding(Lex.getBuffer())) {
1686    DEBUG(llvm::dbgs() << "File encoding: "
1687                       << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
1688                                                               : "unknown")
1689                       << "\n");
1690    DEBUG(llvm::dbgs() << "Language: " << getLanguageName(Style.Language)
1691                       << "\n");
1692  }
1693
1694  tooling::Replacements format() {
1695    tooling::Replacements Result;
1696    FormatTokenLexer Tokens(Lex, SourceMgr, Style, Encoding);
1697
1698    UnwrappedLineParser Parser(Style, Tokens.lex(), *this);
1699    bool StructuralError = Parser.parse();
1700    assert(UnwrappedLines.rbegin()->empty());
1701    for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
1702         ++Run) {
1703      DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
1704      SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1705      for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
1706        AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
1707      }
1708      tooling::Replacements RunResult =
1709          format(AnnotatedLines, StructuralError, Tokens);
1710      DEBUG({
1711        llvm::dbgs() << "Replacements for run " << Run << ":\n";
1712        for (tooling::Replacements::iterator I = RunResult.begin(),
1713                                             E = RunResult.end();
1714             I != E; ++I) {
1715          llvm::dbgs() << I->toString() << "\n";
1716        }
1717      });
1718      for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1719        delete AnnotatedLines[i];
1720      }
1721      Result.insert(RunResult.begin(), RunResult.end());
1722      Whitespaces.reset();
1723    }
1724    return Result;
1725  }
1726
1727  tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1728                               bool StructuralError, FormatTokenLexer &Tokens) {
1729    TokenAnnotator Annotator(Style, Tokens.getIdentTable().get("in"));
1730    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1731      Annotator.annotate(*AnnotatedLines[i]);
1732    }
1733    deriveLocalStyle(AnnotatedLines);
1734    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1735      Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1736    }
1737    computeAffectedLines(AnnotatedLines.begin(), AnnotatedLines.end());
1738
1739    Annotator.setCommentLineLevels(AnnotatedLines);
1740    ContinuationIndenter Indenter(Style, SourceMgr, Whitespaces, Encoding,
1741                                  BinPackInconclusiveFunctions);
1742    UnwrappedLineFormatter Formatter(&Indenter, &Whitespaces, Style);
1743    Formatter.format(AnnotatedLines, /*DryRun=*/false);
1744    return Whitespaces.generateReplacements();
1745  }
1746
1747private:
1748  // Determines which lines are affected by the SourceRanges given as input.
1749  // Returns \c true if at least one line between I and E or one of their
1750  // children is affected.
1751  bool computeAffectedLines(SmallVectorImpl<AnnotatedLine *>::iterator I,
1752                            SmallVectorImpl<AnnotatedLine *>::iterator E) {
1753    bool SomeLineAffected = false;
1754    const AnnotatedLine *PreviousLine = nullptr;
1755    while (I != E) {
1756      AnnotatedLine *Line = *I;
1757      Line->LeadingEmptyLinesAffected = affectsLeadingEmptyLines(*Line->First);
1758
1759      // If a line is part of a preprocessor directive, it needs to be formatted
1760      // if any token within the directive is affected.
1761      if (Line->InPPDirective) {
1762        FormatToken *Last = Line->Last;
1763        SmallVectorImpl<AnnotatedLine *>::iterator PPEnd = I + 1;
1764        while (PPEnd != E && !(*PPEnd)->First->HasUnescapedNewline) {
1765          Last = (*PPEnd)->Last;
1766          ++PPEnd;
1767        }
1768
1769        if (affectsTokenRange(*Line->First, *Last,
1770                              /*IncludeLeadingNewlines=*/false)) {
1771          SomeLineAffected = true;
1772          markAllAsAffected(I, PPEnd);
1773        }
1774        I = PPEnd;
1775        continue;
1776      }
1777
1778      if (nonPPLineAffected(Line, PreviousLine))
1779        SomeLineAffected = true;
1780
1781      PreviousLine = Line;
1782      ++I;
1783    }
1784    return SomeLineAffected;
1785  }
1786
1787  // Determines whether 'Line' is affected by the SourceRanges given as input.
1788  // Returns \c true if line or one if its children is affected.
1789  bool nonPPLineAffected(AnnotatedLine *Line,
1790                         const AnnotatedLine *PreviousLine) {
1791    bool SomeLineAffected = false;
1792    Line->ChildrenAffected =
1793        computeAffectedLines(Line->Children.begin(), Line->Children.end());
1794    if (Line->ChildrenAffected)
1795      SomeLineAffected = true;
1796
1797    // Stores whether one of the line's tokens is directly affected.
1798    bool SomeTokenAffected = false;
1799    // Stores whether we need to look at the leading newlines of the next token
1800    // in order to determine whether it was affected.
1801    bool IncludeLeadingNewlines = false;
1802
1803    // Stores whether the first child line of any of this line's tokens is
1804    // affected.
1805    bool SomeFirstChildAffected = false;
1806
1807    for (FormatToken *Tok = Line->First; Tok; Tok = Tok->Next) {
1808      // Determine whether 'Tok' was affected.
1809      if (affectsTokenRange(*Tok, *Tok, IncludeLeadingNewlines))
1810        SomeTokenAffected = true;
1811
1812      // Determine whether the first child of 'Tok' was affected.
1813      if (!Tok->Children.empty() && Tok->Children.front()->Affected)
1814        SomeFirstChildAffected = true;
1815
1816      IncludeLeadingNewlines = Tok->Children.empty();
1817    }
1818
1819    // Was this line moved, i.e. has it previously been on the same line as an
1820    // affected line?
1821    bool LineMoved = PreviousLine && PreviousLine->Affected &&
1822                     Line->First->NewlinesBefore == 0;
1823
1824    bool IsContinuedComment =
1825        Line->First->is(tok::comment) && Line->First->Next == nullptr &&
1826        Line->First->NewlinesBefore < 2 && PreviousLine &&
1827        PreviousLine->Affected && PreviousLine->Last->is(tok::comment);
1828
1829    if (SomeTokenAffected || SomeFirstChildAffected || LineMoved ||
1830        IsContinuedComment) {
1831      Line->Affected = true;
1832      SomeLineAffected = true;
1833    }
1834    return SomeLineAffected;
1835  }
1836
1837  // Marks all lines between I and E as well as all their children as affected.
1838  void markAllAsAffected(SmallVectorImpl<AnnotatedLine *>::iterator I,
1839                         SmallVectorImpl<AnnotatedLine *>::iterator E) {
1840    while (I != E) {
1841      (*I)->Affected = true;
1842      markAllAsAffected((*I)->Children.begin(), (*I)->Children.end());
1843      ++I;
1844    }
1845  }
1846
1847  // Returns true if the range from 'First' to 'Last' intersects with one of the
1848  // input ranges.
1849  bool affectsTokenRange(const FormatToken &First, const FormatToken &Last,
1850                         bool IncludeLeadingNewlines) {
1851    SourceLocation Start = First.WhitespaceRange.getBegin();
1852    if (!IncludeLeadingNewlines)
1853      Start = Start.getLocWithOffset(First.LastNewlineOffset);
1854    SourceLocation End = Last.getStartOfNonWhitespace();
1855    if (Last.TokenText.size() > 0)
1856      End = End.getLocWithOffset(Last.TokenText.size() - 1);
1857    CharSourceRange Range = CharSourceRange::getCharRange(Start, End);
1858    return affectsCharSourceRange(Range);
1859  }
1860
1861  // Returns true if one of the input ranges intersect the leading empty lines
1862  // before 'Tok'.
1863  bool affectsLeadingEmptyLines(const FormatToken &Tok) {
1864    CharSourceRange EmptyLineRange = CharSourceRange::getCharRange(
1865        Tok.WhitespaceRange.getBegin(),
1866        Tok.WhitespaceRange.getBegin().getLocWithOffset(Tok.LastNewlineOffset));
1867    return affectsCharSourceRange(EmptyLineRange);
1868  }
1869
1870  // Returns true if 'Range' intersects with one of the input ranges.
1871  bool affectsCharSourceRange(const CharSourceRange &Range) {
1872    for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
1873                                                          E = Ranges.end();
1874         I != E; ++I) {
1875      if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
1876          !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
1877        return true;
1878    }
1879    return false;
1880  }
1881
1882  static bool inputUsesCRLF(StringRef Text) {
1883    return Text.count('\r') * 2 > Text.count('\n');
1884  }
1885
1886  void
1887  deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1888    unsigned CountBoundToVariable = 0;
1889    unsigned CountBoundToType = 0;
1890    bool HasCpp03IncompatibleFormat = false;
1891    bool HasBinPackedFunction = false;
1892    bool HasOnePerLineFunction = false;
1893    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1894      if (!AnnotatedLines[i]->First->Next)
1895        continue;
1896      FormatToken *Tok = AnnotatedLines[i]->First->Next;
1897      while (Tok->Next) {
1898        if (Tok->Type == TT_PointerOrReference) {
1899          bool SpacesBefore =
1900              Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1901          bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
1902                             Tok->Next->WhitespaceRange.getEnd();
1903          if (SpacesBefore && !SpacesAfter)
1904            ++CountBoundToVariable;
1905          else if (!SpacesBefore && SpacesAfter)
1906            ++CountBoundToType;
1907        }
1908
1909        if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1910          if (Tok->is(tok::coloncolon) &&
1911              Tok->Previous->Type == TT_TemplateOpener)
1912            HasCpp03IncompatibleFormat = true;
1913          if (Tok->Type == TT_TemplateCloser &&
1914              Tok->Previous->Type == TT_TemplateCloser)
1915            HasCpp03IncompatibleFormat = true;
1916        }
1917
1918        if (Tok->PackingKind == PPK_BinPacked)
1919          HasBinPackedFunction = true;
1920        if (Tok->PackingKind == PPK_OnePerLine)
1921          HasOnePerLineFunction = true;
1922
1923        Tok = Tok->Next;
1924      }
1925    }
1926    if (Style.DerivePointerAlignment) {
1927      if (CountBoundToType > CountBoundToVariable)
1928        Style.PointerAlignment = FormatStyle::PAS_Left;
1929      else if (CountBoundToType < CountBoundToVariable)
1930        Style.PointerAlignment = FormatStyle::PAS_Right;
1931    }
1932    if (Style.Standard == FormatStyle::LS_Auto) {
1933      Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
1934                                                  : FormatStyle::LS_Cpp03;
1935    }
1936    BinPackInconclusiveFunctions =
1937        HasBinPackedFunction || !HasOnePerLineFunction;
1938  }
1939
1940  void consumeUnwrappedLine(const UnwrappedLine &TheLine) override {
1941    assert(!UnwrappedLines.empty());
1942    UnwrappedLines.back().push_back(TheLine);
1943  }
1944
1945  void finishRun() override {
1946    UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
1947  }
1948
1949  FormatStyle Style;
1950  Lexer &Lex;
1951  SourceManager &SourceMgr;
1952  WhitespaceManager Whitespaces;
1953  SmallVector<CharSourceRange, 8> Ranges;
1954  SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
1955
1956  encoding::Encoding Encoding;
1957  bool BinPackInconclusiveFunctions;
1958};
1959
1960} // end anonymous namespace
1961
1962tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1963                               SourceManager &SourceMgr,
1964                               std::vector<CharSourceRange> Ranges) {
1965  if (Style.DisableFormat) {
1966    tooling::Replacements EmptyResult;
1967    return EmptyResult;
1968  }
1969
1970  Formatter formatter(Style, Lex, SourceMgr, Ranges);
1971  return formatter.format();
1972}
1973
1974tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1975                               std::vector<tooling::Range> Ranges,
1976                               StringRef FileName) {
1977  FileManager Files((FileSystemOptions()));
1978  DiagnosticsEngine Diagnostics(
1979      IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1980      new DiagnosticOptions);
1981  SourceManager SourceMgr(Diagnostics, Files);
1982  llvm::MemoryBuffer *Buf = llvm::MemoryBuffer::getMemBuffer(Code, FileName);
1983  const clang::FileEntry *Entry =
1984      Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
1985  SourceMgr.overrideFileContents(Entry, Buf);
1986  FileID ID =
1987      SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
1988  Lexer Lex(ID, SourceMgr.getBuffer(ID), SourceMgr,
1989            getFormattingLangOpts(Style.Standard));
1990  SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1991  std::vector<CharSourceRange> CharRanges;
1992  for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1993    SourceLocation Start = StartOfFile.getLocWithOffset(Ranges[i].getOffset());
1994    SourceLocation End = Start.getLocWithOffset(Ranges[i].getLength());
1995    CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1996  }
1997  return reformat(Style, Lex, SourceMgr, CharRanges);
1998}
1999
2000LangOptions getFormattingLangOpts(FormatStyle::LanguageStandard Standard) {
2001  LangOptions LangOpts;
2002  LangOpts.CPlusPlus = 1;
2003  LangOpts.CPlusPlus11 = Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2004  LangOpts.CPlusPlus1y = Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
2005  LangOpts.LineComment = 1;
2006  LangOpts.CXXOperatorNames = 1;
2007  LangOpts.Bool = 1;
2008  LangOpts.ObjC1 = 1;
2009  LangOpts.ObjC2 = 1;
2010  return LangOpts;
2011}
2012
2013const char *StyleOptionHelpDescription =
2014    "Coding style, currently supports:\n"
2015    "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
2016    "Use -style=file to load style configuration from\n"
2017    ".clang-format file located in one of the parent\n"
2018    "directories of the source file (or current\n"
2019    "directory for stdin).\n"
2020    "Use -style=\"{key: value, ...}\" to set specific\n"
2021    "parameters, e.g.:\n"
2022    "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
2023
2024static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
2025  if (FileName.endswith_lower(".js")) {
2026    return FormatStyle::LK_JavaScript;
2027  } else if (FileName.endswith_lower(".proto") ||
2028             FileName.endswith_lower(".protodevel")) {
2029    return FormatStyle::LK_Proto;
2030  }
2031  return FormatStyle::LK_Cpp;
2032}
2033
2034FormatStyle getStyle(StringRef StyleName, StringRef FileName,
2035                     StringRef FallbackStyle) {
2036  FormatStyle Style = getLLVMStyle();
2037  Style.Language = getLanguageByFileName(FileName);
2038  if (!getPredefinedStyle(FallbackStyle, Style.Language, &Style)) {
2039    llvm::errs() << "Invalid fallback style \"" << FallbackStyle
2040                 << "\" using LLVM style\n";
2041    return Style;
2042  }
2043
2044  if (StyleName.startswith("{")) {
2045    // Parse YAML/JSON style from the command line.
2046    if (std::error_code ec = parseConfiguration(StyleName, &Style)) {
2047      llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
2048                   << FallbackStyle << " style\n";
2049    }
2050    return Style;
2051  }
2052
2053  if (!StyleName.equals_lower("file")) {
2054    if (!getPredefinedStyle(StyleName, Style.Language, &Style))
2055      llvm::errs() << "Invalid value for -style, using " << FallbackStyle
2056                   << " style\n";
2057    return Style;
2058  }
2059
2060  // Look for .clang-format/_clang-format file in the file's parent directories.
2061  SmallString<128> UnsuitableConfigFiles;
2062  SmallString<128> Path(FileName);
2063  llvm::sys::fs::make_absolute(Path);
2064  for (StringRef Directory = Path; !Directory.empty();
2065       Directory = llvm::sys::path::parent_path(Directory)) {
2066    if (!llvm::sys::fs::is_directory(Directory))
2067      continue;
2068    SmallString<128> ConfigFile(Directory);
2069
2070    llvm::sys::path::append(ConfigFile, ".clang-format");
2071    DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2072    bool IsFile = false;
2073    // Ignore errors from is_regular_file: we only need to know if we can read
2074    // the file or not.
2075    llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
2076
2077    if (!IsFile) {
2078      // Try _clang-format too, since dotfiles are not commonly used on Windows.
2079      ConfigFile = Directory;
2080      llvm::sys::path::append(ConfigFile, "_clang-format");
2081      DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2082      llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
2083    }
2084
2085    if (IsFile) {
2086      llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2087          llvm::MemoryBuffer::getFile(ConfigFile.c_str());
2088      if (std::error_code EC = Text.getError()) {
2089        llvm::errs() << EC.message() << "\n";
2090        break;
2091      }
2092      if (std::error_code ec =
2093              parseConfiguration(Text.get()->getBuffer(), &Style)) {
2094        if (ec == ParseError::Unsuitable) {
2095          if (!UnsuitableConfigFiles.empty())
2096            UnsuitableConfigFiles.append(", ");
2097          UnsuitableConfigFiles.append(ConfigFile);
2098          continue;
2099        }
2100        llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
2101                     << "\n";
2102        break;
2103      }
2104      DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
2105      return Style;
2106    }
2107  }
2108  llvm::errs() << "Can't find usable .clang-format, using " << FallbackStyle
2109               << " style\n";
2110  if (!UnsuitableConfigFiles.empty()) {
2111    llvm::errs() << "Configuration file(s) do(es) not support "
2112                 << getLanguageName(Style.Language) << ": "
2113                 << UnsuitableConfigFiles << "\n";
2114  }
2115  return Style;
2116}
2117
2118} // namespace format
2119} // namespace clang
2120