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 #define DEBUG_TYPE "format-formatter"
17 
18 #include "ContinuationIndenter.h"
19 #include "TokenAnnotator.h"
20 #include "UnwrappedLineParser.h"
21 #include "WhitespaceManager.h"
22 #include "clang/Basic/Diagnostic.h"
23 #include "clang/Basic/SourceManager.h"
24 #include "clang/Format/Format.h"
25 #include "clang/Lex/Lexer.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/Support/Allocator.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/YAMLTraits.h"
30 #include "llvm/Support/Path.h"
31 #include <queue>
32 #include <string>
33 
34 namespace llvm {
35 namespace yaml {
36 template <>
37 struct ScalarEnumerationTraits<clang::format::FormatStyle::LanguageStandard> {
38   static void enumeration(IO &IO,
39                           clang::format::FormatStyle::LanguageStandard &Value) {
40     IO.enumCase(Value, "Cpp03", clang::format::FormatStyle::LS_Cpp03);
41     IO.enumCase(Value, "C++03", clang::format::FormatStyle::LS_Cpp03);
42     IO.enumCase(Value, "Cpp11", clang::format::FormatStyle::LS_Cpp11);
43     IO.enumCase(Value, "C++11", clang::format::FormatStyle::LS_Cpp11);
44     IO.enumCase(Value, "Auto", clang::format::FormatStyle::LS_Auto);
45   }
46 };
47 
48 template <>
49 struct ScalarEnumerationTraits<clang::format::FormatStyle::UseTabStyle> {
50   static void
51   enumeration(IO &IO, clang::format::FormatStyle::UseTabStyle &Value) {
52     IO.enumCase(Value, "Never", clang::format::FormatStyle::UT_Never);
53     IO.enumCase(Value, "false", clang::format::FormatStyle::UT_Never);
54     IO.enumCase(Value, "Always", clang::format::FormatStyle::UT_Always);
55     IO.enumCase(Value, "true", clang::format::FormatStyle::UT_Always);
56     IO.enumCase(Value, "ForIndentation",
57                 clang::format::FormatStyle::UT_ForIndentation);
58   }
59 };
60 
61 template <>
62 struct ScalarEnumerationTraits<clang::format::FormatStyle::BraceBreakingStyle> {
63   static void
64   enumeration(IO &IO, clang::format::FormatStyle::BraceBreakingStyle &Value) {
65     IO.enumCase(Value, "Attach", clang::format::FormatStyle::BS_Attach);
66     IO.enumCase(Value, "Linux", clang::format::FormatStyle::BS_Linux);
67     IO.enumCase(Value, "Stroustrup", clang::format::FormatStyle::BS_Stroustrup);
68     IO.enumCase(Value, "Allman", clang::format::FormatStyle::BS_Allman);
69   }
70 };
71 
72 template <>
73 struct ScalarEnumerationTraits<
74     clang::format::FormatStyle::NamespaceIndentationKind> {
75   static void
76   enumeration(IO &IO,
77               clang::format::FormatStyle::NamespaceIndentationKind &Value) {
78     IO.enumCase(Value, "None", clang::format::FormatStyle::NI_None);
79     IO.enumCase(Value, "Inner", clang::format::FormatStyle::NI_Inner);
80     IO.enumCase(Value, "All", clang::format::FormatStyle::NI_All);
81   }
82 };
83 
84 template <> struct MappingTraits<clang::format::FormatStyle> {
85   static void mapping(llvm::yaml::IO &IO, clang::format::FormatStyle &Style) {
86     if (IO.outputting()) {
87       StringRef StylesArray[] = { "LLVM",    "Google", "Chromium",
88                                   "Mozilla", "WebKit" };
89       ArrayRef<StringRef> Styles(StylesArray);
90       for (size_t i = 0, e = Styles.size(); i < e; ++i) {
91         StringRef StyleName(Styles[i]);
92         clang::format::FormatStyle PredefinedStyle;
93         if (clang::format::getPredefinedStyle(StyleName, &PredefinedStyle) &&
94             Style == PredefinedStyle) {
95           IO.mapOptional("# BasedOnStyle", StyleName);
96           break;
97         }
98       }
99     } else {
100       StringRef BasedOnStyle;
101       IO.mapOptional("BasedOnStyle", BasedOnStyle);
102       if (!BasedOnStyle.empty())
103         if (!clang::format::getPredefinedStyle(BasedOnStyle, &Style)) {
104           IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
105           return;
106         }
107     }
108 
109     IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
110     IO.mapOptional("ConstructorInitializerIndentWidth",
111                    Style.ConstructorInitializerIndentWidth);
112     IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
113     IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
114     IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
115                    Style.AllowAllParametersOfDeclarationOnNextLine);
116     IO.mapOptional("AllowShortIfStatementsOnASingleLine",
117                    Style.AllowShortIfStatementsOnASingleLine);
118     IO.mapOptional("AllowShortLoopsOnASingleLine",
119                    Style.AllowShortLoopsOnASingleLine);
120     IO.mapOptional("AlwaysBreakTemplateDeclarations",
121                    Style.AlwaysBreakTemplateDeclarations);
122     IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
123                    Style.AlwaysBreakBeforeMultilineStrings);
124     IO.mapOptional("BreakBeforeBinaryOperators",
125                    Style.BreakBeforeBinaryOperators);
126     IO.mapOptional("BreakConstructorInitializersBeforeComma",
127                    Style.BreakConstructorInitializersBeforeComma);
128     IO.mapOptional("BinPackParameters", Style.BinPackParameters);
129     IO.mapOptional("ColumnLimit", Style.ColumnLimit);
130     IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
131                    Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
132     IO.mapOptional("DerivePointerBinding", Style.DerivePointerBinding);
133     IO.mapOptional("ExperimentalAutoDetectBinPacking",
134                    Style.ExperimentalAutoDetectBinPacking);
135     IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
136     IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
137     IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
138     IO.mapOptional("ObjCSpaceBeforeProtocolList",
139                    Style.ObjCSpaceBeforeProtocolList);
140     IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
141     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
142     IO.mapOptional("PenaltyBreakFirstLessLess",
143                    Style.PenaltyBreakFirstLessLess);
144     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
145     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
146                    Style.PenaltyReturnTypeOnItsOwnLine);
147     IO.mapOptional("PointerBindsToType", Style.PointerBindsToType);
148     IO.mapOptional("SpacesBeforeTrailingComments",
149                    Style.SpacesBeforeTrailingComments);
150     IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
151     IO.mapOptional("Standard", Style.Standard);
152     IO.mapOptional("IndentWidth", Style.IndentWidth);
153     IO.mapOptional("TabWidth", Style.TabWidth);
154     IO.mapOptional("UseTab", Style.UseTab);
155     IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
156     IO.mapOptional("IndentFunctionDeclarationAfterType",
157                    Style.IndentFunctionDeclarationAfterType);
158     IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
159     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
160     IO.mapOptional("SpacesInCStyleCastParentheses",
161                    Style.SpacesInCStyleCastParentheses);
162     IO.mapOptional("SpaceAfterControlStatementKeyword",
163                    Style.SpaceAfterControlStatementKeyword);
164     IO.mapOptional("SpaceBeforeAssignmentOperators",
165                    Style.SpaceBeforeAssignmentOperators);
166   }
167 };
168 }
169 }
170 
171 namespace clang {
172 namespace format {
173 
174 void setDefaultPenalties(FormatStyle &Style) {
175   Style.PenaltyBreakComment = 60;
176   Style.PenaltyBreakFirstLessLess = 120;
177   Style.PenaltyBreakString = 1000;
178   Style.PenaltyExcessCharacter = 1000000;
179 }
180 
181 FormatStyle getLLVMStyle() {
182   FormatStyle LLVMStyle;
183   LLVMStyle.AccessModifierOffset = -2;
184   LLVMStyle.AlignEscapedNewlinesLeft = false;
185   LLVMStyle.AlignTrailingComments = true;
186   LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
187   LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
188   LLVMStyle.AllowShortLoopsOnASingleLine = false;
189   LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
190   LLVMStyle.AlwaysBreakTemplateDeclarations = false;
191   LLVMStyle.BinPackParameters = true;
192   LLVMStyle.BreakBeforeBinaryOperators = false;
193   LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
194   LLVMStyle.BreakConstructorInitializersBeforeComma = false;
195   LLVMStyle.ColumnLimit = 80;
196   LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
197   LLVMStyle.ConstructorInitializerIndentWidth = 4;
198   LLVMStyle.Cpp11BracedListStyle = false;
199   LLVMStyle.DerivePointerBinding = false;
200   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
201   LLVMStyle.IndentCaseLabels = false;
202   LLVMStyle.IndentFunctionDeclarationAfterType = false;
203   LLVMStyle.IndentWidth = 2;
204   LLVMStyle.TabWidth = 8;
205   LLVMStyle.MaxEmptyLinesToKeep = 1;
206   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
207   LLVMStyle.ObjCSpaceBeforeProtocolList = true;
208   LLVMStyle.PointerBindsToType = false;
209   LLVMStyle.SpacesBeforeTrailingComments = 1;
210   LLVMStyle.Standard = FormatStyle::LS_Cpp03;
211   LLVMStyle.UseTab = FormatStyle::UT_Never;
212   LLVMStyle.SpacesInParentheses = false;
213   LLVMStyle.SpaceInEmptyParentheses = false;
214   LLVMStyle.SpacesInCStyleCastParentheses = false;
215   LLVMStyle.SpaceAfterControlStatementKeyword = true;
216   LLVMStyle.SpaceBeforeAssignmentOperators = true;
217 
218   setDefaultPenalties(LLVMStyle);
219   LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
220 
221   return LLVMStyle;
222 }
223 
224 FormatStyle getGoogleStyle() {
225   FormatStyle GoogleStyle;
226   GoogleStyle.AccessModifierOffset = -1;
227   GoogleStyle.AlignEscapedNewlinesLeft = true;
228   GoogleStyle.AlignTrailingComments = true;
229   GoogleStyle.AllowAllParametersOfDeclarationOnNextLine = true;
230   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
231   GoogleStyle.AllowShortLoopsOnASingleLine = true;
232   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
233   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
234   GoogleStyle.BinPackParameters = true;
235   GoogleStyle.BreakBeforeBinaryOperators = false;
236   GoogleStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
237   GoogleStyle.BreakConstructorInitializersBeforeComma = false;
238   GoogleStyle.ColumnLimit = 80;
239   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
240   GoogleStyle.ConstructorInitializerIndentWidth = 4;
241   GoogleStyle.Cpp11BracedListStyle = true;
242   GoogleStyle.DerivePointerBinding = true;
243   GoogleStyle.ExperimentalAutoDetectBinPacking = false;
244   GoogleStyle.IndentCaseLabels = true;
245   GoogleStyle.IndentFunctionDeclarationAfterType = true;
246   GoogleStyle.IndentWidth = 2;
247   GoogleStyle.TabWidth = 8;
248   GoogleStyle.MaxEmptyLinesToKeep = 1;
249   GoogleStyle.NamespaceIndentation = FormatStyle::NI_None;
250   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
251   GoogleStyle.PointerBindsToType = true;
252   GoogleStyle.SpacesBeforeTrailingComments = 2;
253   GoogleStyle.Standard = FormatStyle::LS_Auto;
254   GoogleStyle.UseTab = FormatStyle::UT_Never;
255   GoogleStyle.SpacesInParentheses = false;
256   GoogleStyle.SpaceInEmptyParentheses = false;
257   GoogleStyle.SpacesInCStyleCastParentheses = false;
258   GoogleStyle.SpaceAfterControlStatementKeyword = true;
259   GoogleStyle.SpaceBeforeAssignmentOperators = true;
260 
261   setDefaultPenalties(GoogleStyle);
262   GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
263 
264   return GoogleStyle;
265 }
266 
267 FormatStyle getChromiumStyle() {
268   FormatStyle ChromiumStyle = getGoogleStyle();
269   ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
270   ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
271   ChromiumStyle.AllowShortLoopsOnASingleLine = false;
272   ChromiumStyle.BinPackParameters = false;
273   ChromiumStyle.DerivePointerBinding = false;
274   ChromiumStyle.Standard = FormatStyle::LS_Cpp03;
275   return ChromiumStyle;
276 }
277 
278 FormatStyle getMozillaStyle() {
279   FormatStyle MozillaStyle = getLLVMStyle();
280   MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
281   MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
282   MozillaStyle.DerivePointerBinding = true;
283   MozillaStyle.IndentCaseLabels = true;
284   MozillaStyle.ObjCSpaceBeforeProtocolList = false;
285   MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
286   MozillaStyle.PointerBindsToType = true;
287   return MozillaStyle;
288 }
289 
290 FormatStyle getWebKitStyle() {
291   FormatStyle Style = getLLVMStyle();
292   Style.AccessModifierOffset = -4;
293   Style.AlignTrailingComments = false;
294   Style.BreakBeforeBinaryOperators = true;
295   Style.BreakBeforeBraces = FormatStyle::BS_Stroustrup;
296   Style.BreakConstructorInitializersBeforeComma = true;
297   Style.ColumnLimit = 0;
298   Style.IndentWidth = 4;
299   Style.NamespaceIndentation = FormatStyle::NI_Inner;
300   Style.PointerBindsToType = true;
301   return Style;
302 }
303 
304 bool getPredefinedStyle(StringRef Name, FormatStyle *Style) {
305   if (Name.equals_lower("llvm"))
306     *Style = getLLVMStyle();
307   else if (Name.equals_lower("chromium"))
308     *Style = getChromiumStyle();
309   else if (Name.equals_lower("mozilla"))
310     *Style = getMozillaStyle();
311   else if (Name.equals_lower("google"))
312     *Style = getGoogleStyle();
313   else if (Name.equals_lower("webkit"))
314     *Style = getWebKitStyle();
315   else
316     return false;
317 
318   return true;
319 }
320 
321 llvm::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
322   if (Text.trim().empty())
323     return llvm::make_error_code(llvm::errc::invalid_argument);
324   llvm::yaml::Input Input(Text);
325   Input >> *Style;
326   return Input.error();
327 }
328 
329 std::string configurationAsText(const FormatStyle &Style) {
330   std::string Text;
331   llvm::raw_string_ostream Stream(Text);
332   llvm::yaml::Output Output(Stream);
333   // We use the same mapping method for input and output, so we need a non-const
334   // reference here.
335   FormatStyle NonConstStyle = Style;
336   Output << NonConstStyle;
337   return Stream.str();
338 }
339 
340 namespace {
341 
342 class NoColumnLimitFormatter {
343 public:
344   NoColumnLimitFormatter(ContinuationIndenter *Indenter) : Indenter(Indenter) {}
345 
346   /// \brief Formats the line starting at \p State, simply keeping all of the
347   /// input's line breaking decisions.
348   void format(unsigned FirstIndent, const AnnotatedLine *Line) {
349     LineState State =
350         Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false);
351     while (State.NextToken != NULL) {
352       bool Newline =
353           Indenter->mustBreak(State) ||
354           (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
355       Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
356     }
357   }
358 
359 private:
360   ContinuationIndenter *Indenter;
361 };
362 
363 class UnwrappedLineFormatter {
364 public:
365   UnwrappedLineFormatter(ContinuationIndenter *Indenter,
366                          WhitespaceManager *Whitespaces,
367                          const FormatStyle &Style, const AnnotatedLine &Line)
368       : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style), Line(Line),
369         Count(0) {}
370 
371   /// \brief Formats an \c UnwrappedLine and returns the penalty.
372   ///
373   /// If \p DryRun is \c false, directly applies the changes.
374   unsigned format(unsigned FirstIndent, bool DryRun = false) {
375     LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun);
376 
377     // If the ObjC method declaration does not fit on a line, we should format
378     // it with one arg per line.
379     if (Line.Type == LT_ObjCMethodDecl)
380       State.Stack.back().BreakBeforeParameter = true;
381 
382     // Find best solution in solution space.
383     return analyzeSolutionSpace(State, DryRun);
384   }
385 
386 private:
387   /// \brief An edge in the solution space from \c Previous->State to \c State,
388   /// inserting a newline dependent on the \c NewLine.
389   struct StateNode {
390     StateNode(const LineState &State, bool NewLine, StateNode *Previous)
391         : State(State), NewLine(NewLine), Previous(Previous) {}
392     LineState State;
393     bool NewLine;
394     StateNode *Previous;
395   };
396 
397   /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
398   ///
399   /// In case of equal penalties, we want to prefer states that were inserted
400   /// first. During state generation we make sure that we insert states first
401   /// that break the line as late as possible.
402   typedef std::pair<unsigned, unsigned> OrderedPenalty;
403 
404   /// \brief An item in the prioritized BFS search queue. The \c StateNode's
405   /// \c State has the given \c OrderedPenalty.
406   typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
407 
408   /// \brief The BFS queue type.
409   typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
410                               std::greater<QueueItem> > QueueType;
411 
412   /// \brief Analyze the entire solution space starting from \p InitialState.
413   ///
414   /// This implements a variant of Dijkstra's algorithm on the graph that spans
415   /// the solution space (\c LineStates are the nodes). The algorithm tries to
416   /// find the shortest path (the one with lowest penalty) from \p InitialState
417   /// to a state where all tokens are placed. Returns the penalty.
418   ///
419   /// If \p DryRun is \c false, directly applies the changes.
420   unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false) {
421     std::set<LineState> Seen;
422 
423     // Insert start element into queue.
424     StateNode *Node =
425         new (Allocator.Allocate()) StateNode(InitialState, false, NULL);
426     Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
427     ++Count;
428 
429     unsigned Penalty = 0;
430 
431     // While not empty, take first element and follow edges.
432     while (!Queue.empty()) {
433       Penalty = Queue.top().first.first;
434       StateNode *Node = Queue.top().second;
435       if (Node->State.NextToken == NULL) {
436         DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
437         break;
438       }
439       Queue.pop();
440 
441       // Cut off the analysis of certain solutions if the analysis gets too
442       // complex. See description of IgnoreStackForComparison.
443       if (Count > 10000)
444         Node->State.IgnoreStackForComparison = true;
445 
446       if (!Seen.insert(Node->State).second)
447         // State already examined with lower penalty.
448         continue;
449 
450       addNextStateToQueue(Penalty, Node, /*NewLine=*/false);
451       addNextStateToQueue(Penalty, Node, /*NewLine=*/true);
452     }
453 
454     if (Queue.empty())
455       // We were unable to find a solution, do nothing.
456       // FIXME: Add diagnostic?
457       return 0;
458 
459     // Reconstruct the solution.
460     if (!DryRun)
461       reconstructPath(InitialState, Queue.top().second);
462 
463     DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
464     DEBUG(llvm::dbgs() << "---\n");
465 
466     return Penalty;
467   }
468 
469   void reconstructPath(LineState &State, StateNode *Current) {
470     std::deque<StateNode *> Path;
471     // We do not need a break before the initial token.
472     while (Current->Previous) {
473       Path.push_front(Current);
474       Current = Current->Previous;
475     }
476     for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
477          I != E; ++I) {
478       unsigned Penalty = 0;
479       formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
480       Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
481 
482       DEBUG({
483         if ((*I)->NewLine) {
484           llvm::dbgs() << "Penalty for placing "
485                        << (*I)->Previous->State.NextToken->Tok.getName() << ": "
486                        << Penalty << "\n";
487         }
488       });
489     }
490   }
491 
492   /// \brief Add the following state to the analysis queue \c Queue.
493   ///
494   /// Assume the current state is \p PreviousNode and has been reached with a
495   /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
496   void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
497                            bool NewLine) {
498     if (NewLine && !Indenter->canBreak(PreviousNode->State))
499       return;
500     if (!NewLine && Indenter->mustBreak(PreviousNode->State))
501       return;
502 
503     StateNode *Node = new (Allocator.Allocate())
504         StateNode(PreviousNode->State, NewLine, PreviousNode);
505     if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
506       return;
507 
508     Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
509 
510     Queue.push(QueueItem(OrderedPenalty(Penalty, Count), Node));
511     ++Count;
512   }
513 
514   /// \brief If the \p State's next token is an r_brace closing a nested block,
515   /// format the nested block before it.
516   ///
517   /// Returns \c true if all children could be placed successfully and adapts
518   /// \p Penalty as well as \p State. If \p DryRun is false, also directly
519   /// creates changes using \c Whitespaces.
520   ///
521   /// The crucial idea here is that children always get formatted upon
522   /// encountering the closing brace right after the nested block. Now, if we
523   /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
524   /// \c false), the entire block has to be kept on the same line (which is only
525   /// possible if it fits on the line, only contains a single statement, etc.
526   ///
527   /// If \p NewLine is true, we format the nested block on separate lines, i.e.
528   /// break after the "{", format all lines with correct indentation and the put
529   /// the closing "}" on yet another new line.
530   ///
531   /// This enables us to keep the simple structure of the
532   /// \c UnwrappedLineFormatter, where we only have two options for each token:
533   /// break or don't break.
534   bool formatChildren(LineState &State, bool NewLine, bool DryRun,
535                       unsigned &Penalty) {
536     const FormatToken &LBrace = *State.NextToken->Previous;
537     if (LBrace.isNot(tok::l_brace) || LBrace.BlockKind != BK_Block ||
538         LBrace.Children.size() == 0)
539       // The previous token does not open a block. Nothing to do. We don't
540       // assert so that we can simply call this function for all tokens.
541       return true;
542 
543     if (NewLine) {
544       unsigned ParentIndent = State.Stack.back().Indent;
545       for (SmallVector<AnnotatedLine *, 1>::const_iterator
546                I = LBrace.Children.begin(),
547                E = LBrace.Children.end();
548            I != E; ++I) {
549         unsigned Indent =
550             ParentIndent + ((*I)->Level - Line.Level - 1) * Style.IndentWidth;
551         if (!DryRun) {
552           unsigned Newlines = std::min((*I)->First->NewlinesBefore,
553                                        Style.MaxEmptyLinesToKeep + 1);
554           Newlines = std::max(1u, Newlines);
555           Whitespaces->replaceWhitespace(
556               *(*I)->First, Newlines, (*I)->Level, /*Spaces=*/Indent,
557               /*StartOfTokenColumn=*/Indent, Line.InPPDirective);
558         }
559         UnwrappedLineFormatter Formatter(Indenter, Whitespaces, Style, **I);
560         Penalty += Formatter.format(Indent, DryRun);
561       }
562       return true;
563     }
564 
565     if (LBrace.Children.size() > 1)
566       return false; // Cannot merge multiple statements into a single line.
567 
568     // We can't put the closing "}" on a line with a trailing comment.
569     if (LBrace.Children[0]->Last->isTrailingComment())
570       return false;
571 
572     if (!DryRun) {
573       Whitespaces->replaceWhitespace(
574           *LBrace.Children[0]->First,
575           /*Newlines=*/0, /*IndentLevel=*/1, /*Spaces=*/1,
576           /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
577       UnwrappedLineFormatter Formatter(Indenter, Whitespaces, Style,
578                                        *LBrace.Children[0]);
579       Penalty += Formatter.format(State.Column + 1, DryRun);
580     }
581 
582     State.Column += 1 + LBrace.Children[0]->Last->TotalLength;
583     return true;
584   }
585 
586   ContinuationIndenter *Indenter;
587   WhitespaceManager *Whitespaces;
588   FormatStyle Style;
589   const AnnotatedLine &Line;
590 
591   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
592   QueueType Queue;
593   // Increasing count of \c StateNode items we have created. This is used
594   // to create a deterministic order independent of the container.
595   unsigned Count;
596 };
597 
598 class FormatTokenLexer {
599 public:
600   FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr, FormatStyle &Style,
601                    encoding::Encoding Encoding)
602       : FormatTok(NULL), GreaterStashed(false), Column(0),
603         TrailingWhitespace(0), Lex(Lex), SourceMgr(SourceMgr), Style(Style),
604         IdentTable(getFormattingLangOpts()), Encoding(Encoding) {
605     Lex.SetKeepWhitespaceMode(true);
606   }
607 
608   ArrayRef<FormatToken *> lex() {
609     assert(Tokens.empty());
610     do {
611       Tokens.push_back(getNextToken());
612       maybeJoinPreviousTokens();
613     } while (Tokens.back()->Tok.isNot(tok::eof));
614     return Tokens;
615   }
616 
617   IdentifierTable &getIdentTable() { return IdentTable; }
618 
619 private:
620   void maybeJoinPreviousTokens() {
621     if (Tokens.size() < 4)
622       return;
623     FormatToken *Last = Tokens.back();
624     if (!Last->is(tok::r_paren))
625       return;
626 
627     FormatToken *String = Tokens[Tokens.size() - 2];
628     if (!String->is(tok::string_literal) || String->IsMultiline)
629       return;
630 
631     if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
632       return;
633 
634     FormatToken *Macro = Tokens[Tokens.size() - 4];
635     if (Macro->TokenText != "_T")
636       return;
637 
638     const char *Start = Macro->TokenText.data();
639     const char *End = Last->TokenText.data() + Last->TokenText.size();
640     String->TokenText = StringRef(Start, End - Start);
641     String->IsFirst = Macro->IsFirst;
642     String->LastNewlineOffset = Macro->LastNewlineOffset;
643     String->WhitespaceRange = Macro->WhitespaceRange;
644     String->OriginalColumn = Macro->OriginalColumn;
645     String->ColumnWidth = encoding::columnWidthWithTabs(
646         String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
647 
648     Tokens.pop_back();
649     Tokens.pop_back();
650     Tokens.pop_back();
651     Tokens.back() = String;
652   }
653 
654   FormatToken *getNextToken() {
655     if (GreaterStashed) {
656       // Create a synthesized second '>' token.
657       // FIXME: Increment Column and set OriginalColumn.
658       Token Greater = FormatTok->Tok;
659       FormatTok = new (Allocator.Allocate()) FormatToken;
660       FormatTok->Tok = Greater;
661       SourceLocation GreaterLocation =
662           FormatTok->Tok.getLocation().getLocWithOffset(1);
663       FormatTok->WhitespaceRange =
664           SourceRange(GreaterLocation, GreaterLocation);
665       FormatTok->TokenText = ">";
666       FormatTok->ColumnWidth = 1;
667       GreaterStashed = false;
668       return FormatTok;
669     }
670 
671     FormatTok = new (Allocator.Allocate()) FormatToken;
672     readRawToken(*FormatTok);
673     SourceLocation WhitespaceStart =
674         FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
675     if (SourceMgr.getFileOffset(WhitespaceStart) == 0)
676       FormatTok->IsFirst = true;
677 
678     // Consume and record whitespace until we find a significant token.
679     unsigned WhitespaceLength = TrailingWhitespace;
680     while (FormatTok->Tok.is(tok::unknown)) {
681       for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) {
682         switch (FormatTok->TokenText[i]) {
683         case '\n':
684           ++FormatTok->NewlinesBefore;
685           // FIXME: This is technically incorrect, as it could also
686           // be a literal backslash at the end of the line.
687           if (i == 0 || (FormatTok->TokenText[i - 1] != '\\' &&
688                          (FormatTok->TokenText[i - 1] != '\r' || i == 1 ||
689                           FormatTok->TokenText[i - 2] != '\\')))
690             FormatTok->HasUnescapedNewline = true;
691           FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
692           Column = 0;
693           break;
694         case ' ':
695           ++Column;
696           break;
697         case '\t':
698           Column += Style.TabWidth - Column % Style.TabWidth;
699           break;
700         default:
701           ++Column;
702           break;
703         }
704       }
705 
706       WhitespaceLength += FormatTok->Tok.getLength();
707 
708       readRawToken(*FormatTok);
709     }
710 
711     // In case the token starts with escaped newlines, we want to
712     // take them into account as whitespace - this pattern is quite frequent
713     // in macro definitions.
714     // FIXME: Add a more explicit test.
715     while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
716            FormatTok->TokenText[1] == '\n') {
717       // FIXME: ++FormatTok->NewlinesBefore is missing...
718       WhitespaceLength += 2;
719       Column = 0;
720       FormatTok->TokenText = FormatTok->TokenText.substr(2);
721     }
722 
723     FormatTok->WhitespaceRange = SourceRange(
724         WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
725 
726     FormatTok->OriginalColumn = Column;
727 
728     TrailingWhitespace = 0;
729     if (FormatTok->Tok.is(tok::comment)) {
730       // FIXME: Add the trimmed whitespace to Column.
731       StringRef UntrimmedText = FormatTok->TokenText;
732       FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
733       TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
734     } else if (FormatTok->Tok.is(tok::raw_identifier)) {
735       IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
736       FormatTok->Tok.setIdentifierInfo(&Info);
737       FormatTok->Tok.setKind(Info.getTokenID());
738     } else if (FormatTok->Tok.is(tok::greatergreater)) {
739       FormatTok->Tok.setKind(tok::greater);
740       FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
741       GreaterStashed = true;
742     }
743 
744     // Now FormatTok is the next non-whitespace token.
745 
746     StringRef Text = FormatTok->TokenText;
747     size_t FirstNewlinePos = Text.find('\n');
748     if (FirstNewlinePos == StringRef::npos) {
749       // FIXME: ColumnWidth actually depends on the start column, we need to
750       // take this into account when the token is moved.
751       FormatTok->ColumnWidth =
752           encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
753       Column += FormatTok->ColumnWidth;
754     } else {
755       FormatTok->IsMultiline = true;
756       // FIXME: ColumnWidth actually depends on the start column, we need to
757       // take this into account when the token is moved.
758       FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
759           Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
760 
761       // The last line of the token always starts in column 0.
762       // Thus, the length can be precomputed even in the presence of tabs.
763       FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
764           Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
765           Encoding);
766       Column = FormatTok->LastLineColumnWidth;
767     }
768 
769     return FormatTok;
770   }
771 
772   FormatToken *FormatTok;
773   bool GreaterStashed;
774   unsigned Column;
775   unsigned TrailingWhitespace;
776   Lexer &Lex;
777   SourceManager &SourceMgr;
778   FormatStyle &Style;
779   IdentifierTable IdentTable;
780   encoding::Encoding Encoding;
781   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
782   SmallVector<FormatToken *, 16> Tokens;
783 
784   void readRawToken(FormatToken &Tok) {
785     Lex.LexFromRawLexer(Tok.Tok);
786     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
787                               Tok.Tok.getLength());
788     // For formatting, treat unterminated string literals like normal string
789     // literals.
790     if (Tok.is(tok::unknown) && !Tok.TokenText.empty() &&
791         Tok.TokenText[0] == '"') {
792       Tok.Tok.setKind(tok::string_literal);
793       Tok.IsUnterminatedLiteral = true;
794     }
795   }
796 };
797 
798 class Formatter : public UnwrappedLineConsumer {
799 public:
800   Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
801             const std::vector<CharSourceRange> &Ranges)
802       : Style(Style), Lex(Lex), SourceMgr(SourceMgr),
803         Whitespaces(SourceMgr, Style, inputUsesCRLF(Lex.getBuffer())),
804         Ranges(Ranges), Encoding(encoding::detectEncoding(Lex.getBuffer())) {
805     DEBUG(llvm::dbgs() << "File encoding: "
806                        << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
807                                                                : "unknown")
808                        << "\n");
809   }
810 
811   virtual ~Formatter() {
812     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
813       delete AnnotatedLines[i];
814     }
815   }
816 
817   tooling::Replacements format() {
818     FormatTokenLexer Tokens(Lex, SourceMgr, Style, Encoding);
819 
820     UnwrappedLineParser Parser(Style, Tokens.lex(), *this);
821     bool StructuralError = Parser.parse();
822     TokenAnnotator Annotator(Style, Tokens.getIdentTable().get("in"));
823     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
824       Annotator.annotate(*AnnotatedLines[i]);
825     }
826     deriveLocalStyle();
827     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
828       Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
829     }
830 
831     Annotator.setCommentLineLevels(AnnotatedLines);
832 
833     std::vector<int> IndentForLevel;
834     bool PreviousLineWasTouched = false;
835     const AnnotatedLine *PreviousLine = NULL;
836     bool FormatPPDirective = false;
837     for (SmallVectorImpl<AnnotatedLine *>::iterator I = AnnotatedLines.begin(),
838                                                     E = AnnotatedLines.end();
839          I != E; ++I) {
840       const AnnotatedLine &TheLine = **I;
841       const FormatToken *FirstTok = TheLine.First;
842       int Offset = getIndentOffset(*TheLine.First);
843 
844       // Check whether this line is part of a formatted preprocessor directive.
845       if (FirstTok->HasUnescapedNewline)
846         FormatPPDirective = false;
847       if (!FormatPPDirective && TheLine.InPPDirective &&
848           (touchesLine(TheLine) || touchesPPDirective(I + 1, E)))
849         FormatPPDirective = true;
850 
851       // Determine indent and try to merge multiple unwrapped lines.
852       while (IndentForLevel.size() <= TheLine.Level)
853         IndentForLevel.push_back(-1);
854       IndentForLevel.resize(TheLine.Level + 1);
855       unsigned Indent = getIndent(IndentForLevel, TheLine.Level);
856       if (static_cast<int>(Indent) + Offset >= 0)
857         Indent += Offset;
858       tryFitMultipleLinesInOne(Indent, I, E);
859 
860       bool WasMoved = PreviousLineWasTouched && FirstTok->NewlinesBefore == 0;
861       if (TheLine.First->is(tok::eof)) {
862         if (PreviousLineWasTouched) {
863           unsigned NewLines = std::min(FirstTok->NewlinesBefore, 1u);
864           Whitespaces.replaceWhitespace(*TheLine.First, NewLines,
865                                         /*IndentLevel=*/0, /*Spaces=*/0,
866                                         /*TargetColumn=*/0);
867         }
868       } else if (TheLine.Type != LT_Invalid &&
869                  (WasMoved || FormatPPDirective || touchesLine(TheLine))) {
870         unsigned LevelIndent = getIndent(IndentForLevel, TheLine.Level);
871         if (FirstTok->WhitespaceRange.isValid() &&
872             // Insert a break even if there is a structural error in case where
873             // we break apart a line consisting of multiple unwrapped lines.
874             (FirstTok->NewlinesBefore == 0 || !StructuralError)) {
875           formatFirstToken(*TheLine.First, PreviousLine, Indent,
876                            TheLine.InPPDirective);
877         } else {
878           Indent = LevelIndent = FirstTok->OriginalColumn;
879         }
880         ContinuationIndenter Indenter(Style, SourceMgr, Whitespaces, Encoding,
881                                       BinPackInconclusiveFunctions);
882 
883         // If everything fits on a single line, just put it there.
884         unsigned ColumnLimit = Style.ColumnLimit;
885         AnnotatedLine *NextLine = *(I + 1);
886         if ((I + 1) != E && NextLine->InPPDirective &&
887             !NextLine->First->HasUnescapedNewline)
888           ColumnLimit = getColumnLimit(TheLine.InPPDirective);
889 
890         if (TheLine.Last->TotalLength + Indent <= ColumnLimit) {
891           LineState State =
892               Indenter.getInitialState(Indent, &TheLine, /*DryRun=*/false);
893           while (State.NextToken != NULL)
894             Indenter.addTokenToState(State, false, false);
895         } else if (Style.ColumnLimit == 0) {
896           NoColumnLimitFormatter Formatter(&Indenter);
897           Formatter.format(Indent, &TheLine);
898         } else {
899           UnwrappedLineFormatter Formatter(&Indenter, &Whitespaces, Style,
900                                            TheLine);
901           Formatter.format(Indent);
902         }
903 
904         IndentForLevel[TheLine.Level] = LevelIndent;
905         PreviousLineWasTouched = true;
906       } else {
907         // Format the first token if necessary, and notify the WhitespaceManager
908         // about the unchanged whitespace.
909         for (const FormatToken *Tok = TheLine.First; Tok != NULL;
910              Tok = Tok->Next) {
911           if (Tok == TheLine.First &&
912               (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
913             unsigned LevelIndent = Tok->OriginalColumn;
914             // Remove trailing whitespace of the previous line if it was
915             // touched.
916             if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine)) {
917               formatFirstToken(*Tok, PreviousLine, LevelIndent,
918                                TheLine.InPPDirective);
919             } else {
920               Whitespaces.addUntouchableToken(*Tok, TheLine.InPPDirective);
921             }
922 
923             if (static_cast<int>(LevelIndent) - Offset >= 0)
924               LevelIndent -= Offset;
925             if (Tok->isNot(tok::comment))
926               IndentForLevel[TheLine.Level] = LevelIndent;
927           } else {
928             Whitespaces.addUntouchableToken(*Tok, TheLine.InPPDirective);
929           }
930         }
931         // If we did not reformat this unwrapped line, the column at the end of
932         // the last token is unchanged - thus, we can calculate the end of the
933         // last token.
934         PreviousLineWasTouched = false;
935       }
936       PreviousLine = *I;
937     }
938     return Whitespaces.generateReplacements();
939   }
940 
941 private:
942   static bool inputUsesCRLF(StringRef Text) {
943     return Text.count('\r') * 2 > Text.count('\n');
944   }
945 
946   void deriveLocalStyle() {
947     unsigned CountBoundToVariable = 0;
948     unsigned CountBoundToType = 0;
949     bool HasCpp03IncompatibleFormat = false;
950     bool HasBinPackedFunction = false;
951     bool HasOnePerLineFunction = false;
952     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
953       if (!AnnotatedLines[i]->First->Next)
954         continue;
955       FormatToken *Tok = AnnotatedLines[i]->First->Next;
956       while (Tok->Next) {
957         if (Tok->Type == TT_PointerOrReference) {
958           bool SpacesBefore =
959               Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
960           bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
961                              Tok->Next->WhitespaceRange.getEnd();
962           if (SpacesBefore && !SpacesAfter)
963             ++CountBoundToVariable;
964           else if (!SpacesBefore && SpacesAfter)
965             ++CountBoundToType;
966         }
967 
968         if (Tok->Type == TT_TemplateCloser &&
969             Tok->Previous->Type == TT_TemplateCloser &&
970             Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd())
971           HasCpp03IncompatibleFormat = true;
972 
973         if (Tok->PackingKind == PPK_BinPacked)
974           HasBinPackedFunction = true;
975         if (Tok->PackingKind == PPK_OnePerLine)
976           HasOnePerLineFunction = true;
977 
978         Tok = Tok->Next;
979       }
980     }
981     if (Style.DerivePointerBinding) {
982       if (CountBoundToType > CountBoundToVariable)
983         Style.PointerBindsToType = true;
984       else if (CountBoundToType < CountBoundToVariable)
985         Style.PointerBindsToType = false;
986     }
987     if (Style.Standard == FormatStyle::LS_Auto) {
988       Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
989                                                   : FormatStyle::LS_Cpp03;
990     }
991     BinPackInconclusiveFunctions =
992         HasBinPackedFunction || !HasOnePerLineFunction;
993   }
994 
995   /// \brief Get the indent of \p Level from \p IndentForLevel.
996   ///
997   /// \p IndentForLevel must contain the indent for the level \c l
998   /// at \p IndentForLevel[l], or a value < 0 if the indent for
999   /// that level is unknown.
1000   unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
1001     if (IndentForLevel[Level] != -1)
1002       return IndentForLevel[Level];
1003     if (Level == 0)
1004       return 0;
1005     return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
1006   }
1007 
1008   /// \brief Get the offset of the line relatively to the level.
1009   ///
1010   /// For example, 'public:' labels in classes are offset by 1 or 2
1011   /// characters to the left from their level.
1012   int getIndentOffset(const FormatToken &RootToken) {
1013     if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
1014       return Style.AccessModifierOffset;
1015     return 0;
1016   }
1017 
1018   /// \brief Tries to merge lines into one.
1019   ///
1020   /// This will change \c Line and \c AnnotatedLine to contain the merged line,
1021   /// if possible; note that \c I will be incremented when lines are merged.
1022   void tryFitMultipleLinesInOne(unsigned Indent,
1023                                 SmallVectorImpl<AnnotatedLine *>::iterator &I,
1024                                 SmallVectorImpl<AnnotatedLine *>::iterator E) {
1025     // We can never merge stuff if there are trailing line comments.
1026     AnnotatedLine *TheLine = *I;
1027     if (TheLine->Last->Type == TT_LineComment)
1028       return;
1029 
1030     if (Indent > Style.ColumnLimit)
1031       return;
1032 
1033     unsigned Limit = Style.ColumnLimit - Indent;
1034     // If we already exceed the column limit, we set 'Limit' to 0. The different
1035     // tryMerge..() functions can then decide whether to still do merging.
1036     Limit = TheLine->Last->TotalLength > Limit
1037                 ? 0
1038                 : Limit - TheLine->Last->TotalLength;
1039 
1040     if (I + 1 == E || (*(I + 1))->Type == LT_Invalid)
1041       return;
1042 
1043     if (TheLine->Last->is(tok::l_brace)) {
1044       tryMergeSimpleBlock(I, E, Limit);
1045     } else if (Style.AllowShortIfStatementsOnASingleLine &&
1046                TheLine->First->is(tok::kw_if)) {
1047       tryMergeSimpleControlStatement(I, E, Limit);
1048     } else if (Style.AllowShortLoopsOnASingleLine &&
1049                TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
1050       tryMergeSimpleControlStatement(I, E, Limit);
1051     } else if (TheLine->InPPDirective && (TheLine->First->HasUnescapedNewline ||
1052                                           TheLine->First->IsFirst)) {
1053       tryMergeSimplePPDirective(I, E, Limit);
1054     }
1055   }
1056 
1057   void tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::iterator &I,
1058                                  SmallVectorImpl<AnnotatedLine *>::iterator E,
1059                                  unsigned Limit) {
1060     if (Limit == 0)
1061       return;
1062     AnnotatedLine &Line = **I;
1063     if (!(*(I + 1))->InPPDirective || (*(I + 1))->First->HasUnescapedNewline)
1064       return;
1065     if (I + 2 != E && (*(I + 2))->InPPDirective &&
1066         !(*(I + 2))->First->HasUnescapedNewline)
1067       return;
1068     if (1 + (*(I + 1))->Last->TotalLength > Limit)
1069       return;
1070     join(Line, **(++I));
1071   }
1072 
1073   void
1074   tryMergeSimpleControlStatement(SmallVectorImpl<AnnotatedLine *>::iterator &I,
1075                                  SmallVectorImpl<AnnotatedLine *>::iterator E,
1076                                  unsigned Limit) {
1077     if (Limit == 0)
1078       return;
1079     if (Style.BreakBeforeBraces == FormatStyle::BS_Allman &&
1080         (*(I + 1))->First->is(tok::l_brace))
1081       return;
1082     if ((*(I + 1))->InPPDirective != (*I)->InPPDirective ||
1083         ((*(I + 1))->InPPDirective && (*(I + 1))->First->HasUnescapedNewline))
1084       return;
1085     AnnotatedLine &Line = **I;
1086     if (Line.Last->isNot(tok::r_paren))
1087       return;
1088     if (1 + (*(I + 1))->Last->TotalLength > Limit)
1089       return;
1090     if ((*(I + 1))->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
1091                                    tok::kw_while) ||
1092         (*(I + 1))->First->Type == TT_LineComment)
1093       return;
1094     // Only inline simple if's (no nested if or else).
1095     if (I + 2 != E && Line.First->is(tok::kw_if) &&
1096         (*(I + 2))->First->is(tok::kw_else))
1097       return;
1098     join(Line, **(++I));
1099   }
1100 
1101   void tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::iterator &I,
1102                            SmallVectorImpl<AnnotatedLine *>::iterator E,
1103                            unsigned Limit) {
1104     // No merging if the brace already is on the next line.
1105     if (Style.BreakBeforeBraces != FormatStyle::BS_Attach)
1106       return;
1107 
1108     // First, check that the current line allows merging. This is the case if
1109     // we're not in a control flow statement and the last token is an opening
1110     // brace.
1111     AnnotatedLine &Line = **I;
1112     if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace,
1113                             tok::kw_else, tok::kw_try, tok::kw_catch,
1114                             tok::kw_for,
1115                             // This gets rid of all ObjC @ keywords and methods.
1116                             tok::at, tok::minus, tok::plus))
1117       return;
1118 
1119     FormatToken *Tok = (*(I + 1))->First;
1120     if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
1121         (Tok->getNextNonComment() == NULL ||
1122          Tok->getNextNonComment()->is(tok::semi))) {
1123       // We merge empty blocks even if the line exceeds the column limit.
1124       Tok->SpacesRequiredBefore = 0;
1125       Tok->CanBreakBefore = true;
1126       join(Line, **(I + 1));
1127       I += 1;
1128     } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace)) {
1129       // Check that we still have three lines and they fit into the limit.
1130       if (I + 2 == E || (*(I + 2))->Type == LT_Invalid ||
1131           !nextTwoLinesFitInto(I, Limit))
1132         return;
1133 
1134       // Second, check that the next line does not contain any braces - if it
1135       // does, readability declines when putting it into a single line.
1136       if ((*(I + 1))->Last->Type == TT_LineComment || Tok->MustBreakBefore)
1137         return;
1138       do {
1139         if (Tok->isOneOf(tok::l_brace, tok::r_brace))
1140           return;
1141         Tok = Tok->Next;
1142       } while (Tok != NULL);
1143 
1144       // Last, check that the third line contains a single closing brace.
1145       Tok = (*(I + 2))->First;
1146       if (Tok->getNextNonComment() != NULL || Tok->isNot(tok::r_brace) ||
1147           Tok->MustBreakBefore)
1148         return;
1149 
1150       join(Line, **(I + 1));
1151       join(Line, **(I + 2));
1152       I += 2;
1153     }
1154   }
1155 
1156   bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::iterator I,
1157                            unsigned Limit) {
1158     return 1 + (*(I + 1))->Last->TotalLength + 1 +
1159                (*(I + 2))->Last->TotalLength <=
1160            Limit;
1161   }
1162 
1163   void join(AnnotatedLine &A, const AnnotatedLine &B) {
1164     assert(!A.Last->Next);
1165     assert(!B.First->Previous);
1166     A.Last->Next = B.First;
1167     B.First->Previous = A.Last;
1168     unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
1169     for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
1170       Tok->TotalLength += LengthA;
1171       A.Last = Tok;
1172     }
1173   }
1174 
1175   bool touchesRanges(const CharSourceRange &Range) {
1176     for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1177       if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),
1178                                                Ranges[i].getBegin()) &&
1179           !SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(),
1180                                                Range.getBegin()))
1181         return true;
1182     }
1183     return false;
1184   }
1185 
1186   bool touchesLine(const AnnotatedLine &TheLine) {
1187     const FormatToken *First = TheLine.First;
1188     const FormatToken *Last = TheLine.Last;
1189     CharSourceRange LineRange = CharSourceRange::getCharRange(
1190         First->WhitespaceRange.getBegin().getLocWithOffset(
1191             First->LastNewlineOffset),
1192         Last->getStartOfNonWhitespace().getLocWithOffset(
1193             Last->TokenText.size() - 1));
1194     return touchesRanges(LineRange);
1195   }
1196 
1197   bool touchesPPDirective(SmallVectorImpl<AnnotatedLine *>::iterator I,
1198                           SmallVectorImpl<AnnotatedLine *>::iterator E) {
1199     for (; I != E; ++I) {
1200       if ((*I)->First->HasUnescapedNewline)
1201         return false;
1202       if (touchesLine(**I))
1203         return true;
1204     }
1205     return false;
1206   }
1207 
1208   bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) {
1209     const FormatToken *First = TheLine.First;
1210     CharSourceRange LineRange = CharSourceRange::getCharRange(
1211         First->WhitespaceRange.getBegin(),
1212         First->WhitespaceRange.getBegin().getLocWithOffset(
1213             First->LastNewlineOffset));
1214     return touchesRanges(LineRange);
1215   }
1216 
1217   virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
1218     AnnotatedLines.push_back(new AnnotatedLine(TheLine));
1219   }
1220 
1221   /// \brief Add a new line and the required indent before the first Token
1222   /// of the \c UnwrappedLine if there was no structural parsing error.
1223   /// Returns the indent level of the \c UnwrappedLine.
1224   void formatFirstToken(const FormatToken &RootToken,
1225                         const AnnotatedLine *PreviousLine, unsigned Indent,
1226                         bool InPPDirective) {
1227     unsigned Newlines =
1228         std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
1229     // Remove empty lines before "}" where applicable.
1230     if (RootToken.is(tok::r_brace) &&
1231         (!RootToken.Next ||
1232          (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
1233       Newlines = std::min(Newlines, 1u);
1234     if (Newlines == 0 && !RootToken.IsFirst)
1235       Newlines = 1;
1236 
1237     // Insert extra new line before access specifiers.
1238     if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
1239         RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
1240       ++Newlines;
1241 
1242     // Remove empty lines after access specifiers.
1243     if (PreviousLine && PreviousLine->First->isAccessSpecifier())
1244       Newlines = std::min(1u, Newlines);
1245 
1246     Whitespaces.replaceWhitespace(
1247         RootToken, Newlines, Indent / Style.IndentWidth, Indent, Indent,
1248         InPPDirective && !RootToken.HasUnescapedNewline);
1249   }
1250 
1251   unsigned getColumnLimit(bool InPPDirective) const {
1252     // In preprocessor directives reserve two chars for trailing " \"
1253     return Style.ColumnLimit - (InPPDirective ? 2 : 0);
1254   }
1255 
1256   FormatStyle Style;
1257   Lexer &Lex;
1258   SourceManager &SourceMgr;
1259   WhitespaceManager Whitespaces;
1260   std::vector<CharSourceRange> Ranges;
1261   SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1262 
1263   encoding::Encoding Encoding;
1264   bool BinPackInconclusiveFunctions;
1265 };
1266 
1267 } // end anonymous namespace
1268 
1269 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1270                                SourceManager &SourceMgr,
1271                                std::vector<CharSourceRange> Ranges) {
1272   Formatter formatter(Style, Lex, SourceMgr, Ranges);
1273   return formatter.format();
1274 }
1275 
1276 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1277                                std::vector<tooling::Range> Ranges,
1278                                StringRef FileName) {
1279   FileManager Files((FileSystemOptions()));
1280   DiagnosticsEngine Diagnostics(
1281       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1282       new DiagnosticOptions);
1283   SourceManager SourceMgr(Diagnostics, Files);
1284   llvm::MemoryBuffer *Buf = llvm::MemoryBuffer::getMemBuffer(Code, FileName);
1285   const clang::FileEntry *Entry =
1286       Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
1287   SourceMgr.overrideFileContents(Entry, Buf);
1288   FileID ID =
1289       SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
1290   Lexer Lex(ID, SourceMgr.getBuffer(ID), SourceMgr,
1291             getFormattingLangOpts(Style.Standard));
1292   SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1293   std::vector<CharSourceRange> CharRanges;
1294   for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1295     SourceLocation Start = StartOfFile.getLocWithOffset(Ranges[i].getOffset());
1296     SourceLocation End = Start.getLocWithOffset(Ranges[i].getLength());
1297     CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1298   }
1299   return reformat(Style, Lex, SourceMgr, CharRanges);
1300 }
1301 
1302 LangOptions getFormattingLangOpts(FormatStyle::LanguageStandard Standard) {
1303   LangOptions LangOpts;
1304   LangOpts.CPlusPlus = 1;
1305   LangOpts.CPlusPlus11 = Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1306   LangOpts.LineComment = 1;
1307   LangOpts.Bool = 1;
1308   LangOpts.ObjC1 = 1;
1309   LangOpts.ObjC2 = 1;
1310   return LangOpts;
1311 }
1312 
1313 const char *StyleOptionHelpDescription =
1314     "Coding style, currently supports:\n"
1315     "  LLVM, Google, Chromium, Mozilla, WebKit.\n"
1316     "Use -style=file to load style configuration from\n"
1317     ".clang-format file located in one of the parent\n"
1318     "directories of the source file (or current\n"
1319     "directory for stdin).\n"
1320     "Use -style=\"{key: value, ...}\" to set specific\n"
1321     "parameters, e.g.:\n"
1322     "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1323 
1324 FormatStyle getStyle(StringRef StyleName, StringRef FileName) {
1325   // Fallback style in case the rest of this function can't determine a style.
1326   StringRef FallbackStyle = "LLVM";
1327   FormatStyle Style;
1328   getPredefinedStyle(FallbackStyle, &Style);
1329 
1330   if (StyleName.startswith("{")) {
1331     // Parse YAML/JSON style from the command line.
1332     if (llvm::error_code ec = parseConfiguration(StyleName, &Style)) {
1333       llvm::errs() << "Error parsing -style: " << ec.message()
1334                    << ", using " << FallbackStyle << " style\n";
1335     }
1336     return Style;
1337   }
1338 
1339   if (!StyleName.equals_lower("file")) {
1340     if (!getPredefinedStyle(StyleName, &Style))
1341       llvm::errs() << "Invalid value for -style, using " << FallbackStyle
1342                    << " style\n";
1343     return Style;
1344   }
1345 
1346   SmallString<128> Path(FileName);
1347   llvm::sys::fs::make_absolute(Path);
1348   for (StringRef Directory = Path;
1349        !Directory.empty();
1350        Directory = llvm::sys::path::parent_path(Directory)) {
1351     if (!llvm::sys::fs::is_directory(Directory))
1352       continue;
1353     SmallString<128> ConfigFile(Directory);
1354 
1355     llvm::sys::path::append(ConfigFile, ".clang-format");
1356     DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1357     bool IsFile = false;
1358     // Ignore errors from is_regular_file: we only need to know if we can read
1359     // the file or not.
1360     llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1361 
1362     if (!IsFile) {
1363       // Try _clang-format too, since dotfiles are not commonly used on Windows.
1364       ConfigFile = Directory;
1365       llvm::sys::path::append(ConfigFile, "_clang-format");
1366       DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1367       llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1368     }
1369 
1370     if (IsFile) {
1371       OwningPtr<llvm::MemoryBuffer> Text;
1372       if (llvm::error_code ec = llvm::MemoryBuffer::getFile(ConfigFile, Text)) {
1373         llvm::errs() << ec.message() << "\n";
1374         continue;
1375       }
1376       if (llvm::error_code ec = parseConfiguration(Text->getBuffer(), &Style)) {
1377         llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
1378                      << "\n";
1379         continue;
1380       }
1381       DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
1382       return Style;
1383     }
1384   }
1385   llvm::errs() << "Can't find usable .clang-format, using " << FallbackStyle
1386                << " style\n";
1387   return Style;
1388 }
1389 
1390 } // namespace format
1391 } // namespace clang
1392