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