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