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