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 /// This is EXPERIMENTAL code under heavy development. It is not in a state yet,
15 /// where it can be used to format real code.
16 ///
17 //===----------------------------------------------------------------------===//
18 
19 #include "clang/Format/Format.h"
20 
21 #include "clang/Basic/SourceManager.h"
22 #include "clang/Lex/Lexer.h"
23 
24 #include "UnwrappedLineParser.h"
25 
26 namespace clang {
27 namespace format {
28 
29 // FIXME: Move somewhere sane.
30 struct TokenAnnotation {
31   enum TokenType { TT_Unknown, TT_TemplateOpener, TT_BinaryOperator,
32       TT_UnaryOperator, TT_OverloadedOperator, TT_PointerOrReference,
33       TT_ConditionalExpr, TT_LineComment, TT_BlockComment };
34 
35   TokenType Type;
36 
37   /// \brief The current parenthesis level, i.e. the number of opening minus
38   /// the number of closing parenthesis left of the current position.
39   unsigned ParenLevel;
40 
41   bool SpaceRequiredBefore;
42   bool CanBreakBefore;
43   bool MustBreakBefore;
44 };
45 
46 using llvm::MutableArrayRef;
47 
48 FormatStyle getLLVMStyle() {
49   FormatStyle LLVMStyle;
50   LLVMStyle.ColumnLimit = 80;
51   LLVMStyle.MaxEmptyLinesToKeep = 1;
52   LLVMStyle.PointerAndReferenceBindToType = false;
53   LLVMStyle.AccessModifierOffset = -2;
54   LLVMStyle.SplitTemplateClosingGreater = true;
55   return LLVMStyle;
56 }
57 
58 FormatStyle getGoogleStyle() {
59   FormatStyle GoogleStyle;
60   GoogleStyle.ColumnLimit = 80;
61   GoogleStyle.MaxEmptyLinesToKeep = 1;
62   GoogleStyle.PointerAndReferenceBindToType = true;
63   GoogleStyle.AccessModifierOffset = -1;
64   GoogleStyle.SplitTemplateClosingGreater = false;
65   return GoogleStyle;
66 }
67 
68 struct OptimizationParameters {
69   unsigned PenaltyExtraLine;
70   unsigned PenaltyIndentLevel;
71 };
72 
73 class UnwrappedLineFormatter {
74 public:
75   UnwrappedLineFormatter(const FormatStyle &Style, SourceManager &SourceMgr,
76                          const UnwrappedLine &Line,
77                          const std::vector<TokenAnnotation> &Annotations,
78                          tooling::Replacements &Replaces)
79       : Style(Style),
80         SourceMgr(SourceMgr),
81         Line(Line),
82         Annotations(Annotations),
83         Replaces(Replaces) {
84     Parameters.PenaltyExtraLine = 100;
85     Parameters.PenaltyIndentLevel = 5;
86   }
87 
88   void format() {
89     formatFirstToken();
90     count = 0;
91     IndentState State;
92     State.Column = Line.Level * 2 + Line.Tokens[0].Tok.getLength();
93     State.CtorInitializerOnNewLine = false;
94     State.InCtorInitializer = false;
95     State.ConsumedTokens = 1;
96 
97     //State.UsedIndent.push_back(Line.Level * 2);
98     State.Indent.push_back(Line.Level * 2 + 4);
99     State.LastSpace.push_back(Line.Level * 2);
100 
101     // Start iterating at 1 as we have correctly formatted of Token #0 above.
102     for (unsigned i = 1, n = Line.Tokens.size(); i != n; ++i) {
103       unsigned NoBreak = calcPenalty(State, false, UINT_MAX);
104       unsigned Break = calcPenalty(State, true, NoBreak);
105       addToken(Break < NoBreak, false, State);
106     }
107   }
108 
109 private:
110   /// \brief The current state when indenting a unwrapped line.
111   ///
112   /// As the indenting tries different combinations this is copied by value.
113   struct IndentState {
114     /// \brief The number of used columns in the current line.
115     unsigned Column;
116 
117     /// \brief The number of tokens already consumed.
118     unsigned ConsumedTokens;
119 
120     /// \brief The position to which a specific parenthesis level needs to be
121     /// indented.
122     std::vector<unsigned> Indent;
123 
124     std::vector<unsigned> LastSpace;
125 
126     bool CtorInitializerOnNewLine;
127     bool InCtorInitializer;
128 
129     /// \brief Comparison operator to be able to used \c IndentState in \c map.
130     bool operator<(const IndentState &Other) const {
131       if (Other.ConsumedTokens != ConsumedTokens)
132         return Other.ConsumedTokens > ConsumedTokens;
133       if (Other.Column != Column)
134         return Other.Column > Column;
135       if (Other.Indent.size() != Indent.size())
136         return Other.Indent.size() > Indent.size();
137       for (int i = 0, e = Indent.size(); i != e; ++i) {
138         if (Other.Indent[i] != Indent[i])
139           return Other.Indent[i] > Indent[i];
140       }
141       if (Other.LastSpace.size() != LastSpace.size())
142         return Other.LastSpace.size() > LastSpace.size();
143       for (int i = 0, e = LastSpace.size(); i != e; ++i) {
144         if (Other.LastSpace[i] != LastSpace[i])
145           return Other.LastSpace[i] > LastSpace[i];
146       }
147       return false;
148     }
149   };
150 
151   /// Append the next token to \p State.
152   void addToken(bool Newline, bool DryRun, IndentState &State) {
153     unsigned Index = State.ConsumedTokens;
154     const FormatToken &Current = Line.Tokens[Index];
155     const FormatToken &Previous = Line.Tokens[Index - 1];
156     unsigned ParenLevel = Annotations[Index].ParenLevel;
157 
158     if (Current.Tok.is(tok::l_paren) || Current.Tok.is(tok::l_square) ||
159         Annotations[Index].Type == TokenAnnotation::TT_TemplateOpener) {
160       State.Indent.push_back(4 + State.LastSpace.back());
161       State.LastSpace.push_back(State.LastSpace.back());
162     }
163 
164     if (Newline) {
165       if (Current.Tok.is(tok::string_literal) &&
166           Previous.Tok.is(tok::string_literal))
167         State.Column = State.Column - Previous.Tok.getLength();
168       else if (Previous.Tok.is(tok::equal) && ParenLevel != 0)
169         State.Column = State.Indent[ParenLevel] + 4;
170       else if (ParenLevel < State.Indent.size())
171         State.Column = State.Indent[ParenLevel];
172       if (!DryRun)
173         replaceWhitespace(Current, 1, State.Column);
174 
175       State.Column += Current.Tok.getLength();
176       if (ParenLevel < State.LastSpace.size())
177         State.LastSpace[ParenLevel] = State.Indent[ParenLevel];
178       if (Current.Tok.is(tok::colon) &&
179           Annotations[Index].Type != TokenAnnotation::TT_ConditionalExpr) {
180         State.Indent[ParenLevel] += 2;
181         State.CtorInitializerOnNewLine = true;
182         State.InCtorInitializer = true;
183       }
184     } else {
185       unsigned Spaces = Annotations[Index].SpaceRequiredBefore ? 1 : 0;
186       if (Annotations[Index].Type == TokenAnnotation::TT_LineComment)
187         Spaces = 2;
188       if (!DryRun)
189         replaceWhitespace(Current, 0, Spaces);
190       if (Previous.Tok.is(tok::l_paren))
191         State.Indent[ParenLevel] = State.Column;
192       if (Previous.Tok.is(tok::less) &&
193           Annotations[Index - 1].Type == TokenAnnotation::TT_TemplateOpener &&
194           ParenLevel < State.Indent.size())
195         State.Indent[ParenLevel] = State.Column;
196       if (Current.Tok.is(tok::colon)) {
197         State.Indent[ParenLevel] = State.Column + 3;
198         State.InCtorInitializer = true;
199       }
200       // Top-level spaces are exempt as that mostly leads to better results.
201       if (Spaces > 0 && ParenLevel != 0 &&
202           ParenLevel < State.LastSpace.size())
203         State.LastSpace[ParenLevel] = State.Column + Spaces;
204       State.Column += Current.Tok.getLength() + Spaces;
205     }
206 
207     if (!DryRun &&
208         (Current.Tok.is(tok::r_paren) || Current.Tok.is(tok::r_square) ||
209          Annotations[Index].Type == TokenAnnotation::TT_TemplateOpener)) {
210       State.Indent.pop_back();
211       State.LastSpace.pop_back();
212     }
213 
214     ++State.ConsumedTokens;
215   }
216 
217   typedef std::map<IndentState, unsigned> StateMap;
218   StateMap Memory;
219 
220   unsigned splitPenalty(const FormatToken &Token) {
221     if (Token.Tok.is(tok::semi))
222       return 0;
223     if (Token.Tok.is(tok::comma))
224       return 1;
225     if (Token.Tok.is(tok::equal) || Token.Tok.is(tok::l_paren) ||
226         Token.Tok.is(tok::pipepipe) || Token.Tok.is(tok::ampamp))
227       return 2;
228     return 3;
229   }
230 
231   /// \brief Calculate the number of lines needed to format the remaining part
232   /// of the unwrapped line.
233   ///
234   /// Assumes the formatting so far has led to
235   /// the \c IndentState \p State. If \p NewLine is set, a new line will be
236   /// added after the previous token.
237   ///
238   /// \param StopAt is used for optimization. If we can determine that we'll
239   /// definitely need at least \p StopAt additional lines, we already know of a
240   /// better solution.
241   unsigned calcPenalty(IndentState State, bool NewLine, unsigned StopAt) {
242     // We are at the end of the unwrapped line, so we don't need any more lines.
243     if (State.ConsumedTokens >= Line.Tokens.size())
244       return 0;
245 
246     if (!NewLine && Annotations[State.ConsumedTokens].MustBreakBefore)
247       return UINT_MAX;
248     if (NewLine && !Annotations[State.ConsumedTokens].CanBreakBefore)
249       return UINT_MAX;
250 
251     if (State.ConsumedTokens > 0 && !NewLine &&
252         State.CtorInitializerOnNewLine &&
253         Line.Tokens[State.ConsumedTokens - 1].Tok.is(tok::comma))
254       return UINT_MAX;
255 
256     if (NewLine && State.InCtorInitializer && !State.CtorInitializerOnNewLine)
257       return UINT_MAX;
258 
259     addToken(NewLine, true, State);
260 
261     // Exceeding column limit is bad.
262     if (State.Column > Style.ColumnLimit)
263       return UINT_MAX;
264 
265     unsigned CurrentPenalty = 0;
266     if (NewLine) {
267       CurrentPenalty += Parameters.PenaltyIndentLevel *
268           Annotations[State.ConsumedTokens - 1].ParenLevel +
269           Parameters.PenaltyExtraLine +
270           splitPenalty(Line.Tokens[State.ConsumedTokens - 2]);
271     }
272 
273     if (StopAt <= CurrentPenalty)
274       return UINT_MAX;
275     StopAt -= CurrentPenalty;
276 
277     // Has this state already been examined?
278     StateMap::iterator I = Memory.find(State);
279     if (I != Memory.end())
280       return I->second;
281     ++count;
282 
283     unsigned NoBreak = calcPenalty(State, false, StopAt);
284     unsigned WithBreak = calcPenalty(State, true, std::min(StopAt, NoBreak));
285     unsigned Result = std::min(NoBreak, WithBreak);
286     if (Result != UINT_MAX)
287       Result += CurrentPenalty;
288     Memory[State] = Result;
289     assert(Memory.find(State) != Memory.end());
290     return Result;
291   }
292 
293   /// \brief Replaces the whitespace in front of \p Tok. Only call once for
294   /// each \c FormatToken.
295   void replaceWhitespace(const FormatToken &Tok, unsigned NewLines,
296                          unsigned Spaces) {
297     Replaces.insert(tooling::Replacement(
298         SourceMgr, Tok.WhiteSpaceStart, Tok.WhiteSpaceLength,
299         std::string(NewLines, '\n') + std::string(Spaces, ' ')));
300   }
301 
302   /// \brief Add a new line and the required indent before the first Token
303   /// of the \c UnwrappedLine.
304   void formatFirstToken() {
305     const FormatToken &Token = Line.Tokens[0];
306     if (Token.WhiteSpaceStart.isValid()) {
307       unsigned Newlines =
308           std::min(Token.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
309       unsigned Offset = SourceMgr.getFileOffset(Token.WhiteSpaceStart);
310       if (Newlines == 0 && Offset != 0)
311         Newlines = 1;
312       unsigned Indent = Line.Level * 2;
313       if (Token.Tok.is(tok::kw_public) || Token.Tok.is(tok::kw_protected) ||
314           Token.Tok.is(tok::kw_private))
315         Indent += Style.AccessModifierOffset;
316       replaceWhitespace(Token, Newlines, Indent);
317     }
318   }
319 
320   FormatStyle Style;
321   SourceManager &SourceMgr;
322   const UnwrappedLine &Line;
323   const std::vector<TokenAnnotation> &Annotations;
324   tooling::Replacements &Replaces;
325   unsigned int count;
326 
327   OptimizationParameters Parameters;
328 };
329 
330 /// \brief Determines extra information about the tokens comprising an
331 /// \c UnwrappedLine.
332 class TokenAnnotator {
333 public:
334   TokenAnnotator(const UnwrappedLine &Line, const FormatStyle &Style,
335                  SourceManager &SourceMgr)
336       : Line(Line),
337         Style(Style),
338         SourceMgr(SourceMgr) {
339   }
340 
341   /// \brief A parser that gathers additional information about tokens.
342   ///
343   /// The \c TokenAnnotator tries to matches parenthesis and square brakets and
344   /// store a parenthesis levels. It also tries to resolve matching "<" and ">"
345   /// into template parameter lists.
346   class AnnotatingParser {
347   public:
348     AnnotatingParser(const SmallVector<FormatToken, 16> &Tokens,
349                      std::vector<TokenAnnotation> &Annotations)
350         : Tokens(Tokens),
351           Annotations(Annotations),
352           Index(0) {
353     }
354 
355     bool parseAngle(unsigned Level) {
356       while (Index < Tokens.size()) {
357         if (Tokens[Index].Tok.is(tok::greater)) {
358           Annotations[Index].Type = TokenAnnotation::TT_TemplateOpener;
359           Annotations[Index].ParenLevel = Level;
360           next();
361           return true;
362         }
363         if (Tokens[Index].Tok.is(tok::r_paren) ||
364             Tokens[Index].Tok.is(tok::r_square))
365           return false;
366         if (Tokens[Index].Tok.is(tok::pipepipe) ||
367             Tokens[Index].Tok.is(tok::ampamp) ||
368             Tokens[Index].Tok.is(tok::question) ||
369             Tokens[Index].Tok.is(tok::colon))
370           return false;
371         consumeToken(Level);
372       }
373       return false;
374     }
375 
376     bool parseParens(unsigned Level) {
377       while (Index < Tokens.size()) {
378         if (Tokens[Index].Tok.is(tok::r_paren)) {
379           Annotations[Index].ParenLevel = Level;
380           next();
381           return true;
382         }
383         if (Tokens[Index].Tok.is(tok::r_square))
384           return false;
385         consumeToken(Level);
386       }
387       return false;
388     }
389 
390     bool parseSquare(unsigned Level) {
391       while (Index < Tokens.size()) {
392         if (Tokens[Index].Tok.is(tok::r_square)) {
393           Annotations[Index].ParenLevel = Level;
394           next();
395           return true;
396         }
397         if (Tokens[Index].Tok.is(tok::r_paren))
398           return false;
399         consumeToken(Level);
400       }
401       return false;
402     }
403 
404     bool parseConditional(unsigned Level) {
405       while (Index < Tokens.size()) {
406         if (Tokens[Index].Tok.is(tok::colon)) {
407           Annotations[Index].Type = TokenAnnotation::TT_ConditionalExpr;
408           next();
409           return true;
410         }
411         consumeToken(Level);
412       }
413       return false;
414     }
415 
416     void consumeToken(unsigned Level) {
417       Annotations[Index].ParenLevel = Level;
418       unsigned CurrentIndex = Index;
419       next();
420       switch (Tokens[CurrentIndex].Tok.getKind()) {
421       case tok::l_paren:
422         parseParens(Level + 1);
423         break;
424       case tok::l_square:
425         parseSquare(Level + 1);
426         break;
427       case tok::less:
428         if (parseAngle(Level + 1))
429           Annotations[CurrentIndex].Type = TokenAnnotation::TT_TemplateOpener;
430         else {
431           Annotations[CurrentIndex].Type = TokenAnnotation::TT_BinaryOperator;
432           Index = CurrentIndex + 1;
433         }
434         break;
435       case tok::greater:
436         Annotations[CurrentIndex].Type = TokenAnnotation::TT_BinaryOperator;
437         break;
438       case tok::kw_operator:
439         if (!Tokens[Index].Tok.is(tok::l_paren))
440           Annotations[Index].Type = TokenAnnotation::TT_OverloadedOperator;
441         next();
442         break;
443       case tok::question:
444         parseConditional(Level);
445         break;
446       default:
447         break;
448       }
449     }
450 
451     void parseLine() {
452       while (Index < Tokens.size()) {
453         consumeToken(0);
454       }
455     }
456 
457     void next() {
458       ++Index;
459     }
460 
461   private:
462     const SmallVector<FormatToken, 16> &Tokens;
463     std::vector<TokenAnnotation> &Annotations;
464     unsigned Index;
465   };
466 
467   void annotate() {
468     Annotations.clear();
469     for (int i = 0, e = Line.Tokens.size(); i != e; ++i) {
470       Annotations.push_back(TokenAnnotation());
471     }
472 
473     AnnotatingParser Parser(Line.Tokens, Annotations);
474     Parser.parseLine();
475 
476     determineTokenTypes();
477 
478     for (int i = 1, e = Line.Tokens.size(); i != e; ++i) {
479       TokenAnnotation &Annotation = Annotations[i];
480 
481       Annotation.CanBreakBefore =
482           canBreakBetween(Line.Tokens[i - 1], Line.Tokens[i]);
483 
484       if (Line.Tokens[i].Tok.is(tok::colon)) {
485         if (Line.Tokens[0].Tok.is(tok::kw_case) || i == e - 1) {
486           Annotation.SpaceRequiredBefore = false;
487         } else {
488           Annotation.SpaceRequiredBefore = TokenAnnotation::TT_ConditionalExpr;
489         }
490       } else if (Annotations[i - 1].Type == TokenAnnotation::TT_UnaryOperator) {
491         Annotation.SpaceRequiredBefore = false;
492       } else if (Annotation.Type == TokenAnnotation::TT_UnaryOperator) {
493         Annotation.SpaceRequiredBefore =
494             Line.Tokens[i - 1].Tok.isNot(tok::l_paren);
495       } else if (Line.Tokens[i - 1].Tok.is(tok::greater) &&
496                  Line.Tokens[i].Tok.is(tok::greater)) {
497         if (Annotation.Type == TokenAnnotation::TT_TemplateOpener &&
498             Annotations[i - 1].Type == TokenAnnotation::TT_TemplateOpener)
499           Annotation.SpaceRequiredBefore = Style.SplitTemplateClosingGreater;
500         else
501           Annotation.SpaceRequiredBefore = false;
502       } else if (
503           Annotation.Type == TokenAnnotation::TT_BinaryOperator ||
504           Annotations[i - 1].Type == TokenAnnotation::TT_BinaryOperator) {
505         Annotation.SpaceRequiredBefore = true;
506       } else if (
507           Annotations[i - 1].Type == TokenAnnotation::TT_TemplateOpener &&
508           Line.Tokens[i].Tok.is(tok::l_paren)) {
509         Annotation.SpaceRequiredBefore = false;
510       } else {
511         Annotation.SpaceRequiredBefore =
512             spaceRequiredBetween(Line.Tokens[i - 1].Tok, Line.Tokens[i].Tok);
513       }
514 
515       if (Annotations[i - 1].Type == TokenAnnotation::TT_LineComment ||
516           (Line.Tokens[i].Tok.is(tok::string_literal) &&
517            Line.Tokens[i - 1].Tok.is(tok::string_literal))) {
518         Annotation.MustBreakBefore = true;
519       }
520 
521       if (Annotation.MustBreakBefore)
522         Annotation.CanBreakBefore = true;
523     }
524   }
525 
526   const std::vector<TokenAnnotation> &getAnnotations() {
527     return Annotations;
528   }
529 
530 private:
531   void determineTokenTypes() {
532     for (int i = 0, e = Line.Tokens.size(); i != e; ++i) {
533       TokenAnnotation &Annotation = Annotations[i];
534       const FormatToken &Tok = Line.Tokens[i];
535 
536       if (Tok.Tok.is(tok::star) || Tok.Tok.is(tok::amp))
537         Annotation.Type = determineStarAmpUsage(i);
538       else if (Tok.Tok.is(tok::minus) && Line.Tokens[i - 1].Tok.is(tok::equal))
539         Annotation.Type = TokenAnnotation::TT_UnaryOperator;
540       else if (isBinaryOperator(Line.Tokens[i]))
541         Annotation.Type = TokenAnnotation::TT_BinaryOperator;
542       else if (Tok.Tok.is(tok::comment)) {
543         StringRef Data(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
544                        Tok.Tok.getLength());
545         if (Data.startswith("//"))
546           Annotation.Type = TokenAnnotation::TT_LineComment;
547         else
548           Annotation.Type = TokenAnnotation::TT_BlockComment;
549       }
550     }
551   }
552 
553   bool isBinaryOperator(const FormatToken &Tok) {
554     switch (Tok.Tok.getKind()) {
555     case tok::equal:
556     case tok::equalequal:
557     case tok::star:
558       //case tok::amp:
559     case tok::plus:
560     case tok::slash:
561     case tok::minus:
562     case tok::ampamp:
563     case tok::pipe:
564     case tok::pipepipe:
565     case tok::percent:
566       return true;
567     default:
568       return false;
569     }
570   }
571 
572   TokenAnnotation::TokenType determineStarAmpUsage(unsigned Index) {
573     if (Index == Annotations.size())
574       return TokenAnnotation::TT_Unknown;
575 
576     if (Index == 0 || Line.Tokens[Index - 1].Tok.is(tok::l_paren) ||
577         Line.Tokens[Index - 1].Tok.is(tok::comma) ||
578         Annotations[Index - 1].Type == TokenAnnotation::TT_BinaryOperator)
579       return TokenAnnotation::TT_UnaryOperator;
580 
581     if (Line.Tokens[Index - 1].Tok.isLiteral() ||
582         Line.Tokens[Index + 1].Tok.isLiteral())
583       return TokenAnnotation::TT_BinaryOperator;
584 
585     return TokenAnnotation::TT_PointerOrReference;
586   }
587 
588   bool isIfForOrWhile(Token Tok) {
589     return Tok.is(tok::kw_if) || Tok.is(tok::kw_for) || Tok.is(tok::kw_while);
590   }
591 
592   bool spaceRequiredBetween(Token Left, Token Right) {
593     if (Left.is(tok::kw_template) && Right.is(tok::less))
594       return true;
595     if (Left.is(tok::arrow) || Right.is(tok::arrow))
596       return false;
597     if (Left.is(tok::exclaim) || Left.is(tok::tilde))
598       return false;
599     if (Left.is(tok::less) || Right.is(tok::greater) || Right.is(tok::less))
600       return false;
601     if (Left.is(tok::amp) || Left.is(tok::star))
602       return Right.isLiteral() || Style.PointerAndReferenceBindToType;
603     if (Right.is(tok::star) && Left.is(tok::l_paren))
604       return false;
605     if (Right.is(tok::amp) || Right.is(tok::star))
606       return Left.isLiteral() || !Style.PointerAndReferenceBindToType;
607     if (Left.is(tok::l_square) || Right.is(tok::l_square) ||
608         Right.is(tok::r_square))
609       return false;
610     if (Left.is(tok::coloncolon) || Right.is(tok::coloncolon))
611       return false;
612     if (Left.is(tok::period) || Right.is(tok::period))
613       return false;
614     if (Left.is(tok::colon) || Right.is(tok::colon))
615       return true;
616     if ((Left.is(tok::plusplus) && Right.isAnyIdentifier()) ||
617         (Left.isAnyIdentifier() && Right.is(tok::plusplus)) ||
618         (Left.is(tok::minusminus) && Right.isAnyIdentifier()) ||
619         (Left.isAnyIdentifier() && Right.is(tok::minusminus)))
620       return false;
621     if (Left.is(tok::l_paren))
622       return false;
623     if (Left.is(tok::hash))
624       return false;
625     if (Right.is(tok::r_paren) || Right.is(tok::semi) || Right.is(tok::comma))
626       return false;
627     if (Right.is(tok::l_paren)) {
628       return !Left.isAnyIdentifier() || isIfForOrWhile(Left);
629     }
630     return true;
631   }
632 
633   bool canBreakBetween(const FormatToken &Left, const FormatToken &Right) {
634     if (Right.Tok.is(tok::r_paren))
635       return false;
636     if (isBinaryOperator(Left))
637       return true;
638     return Right.Tok.is(tok::colon) || Left.Tok.is(tok::comma) || Left.Tok.is(
639         tok::semi) || Left.Tok.is(tok::equal) || Left.Tok.is(tok::ampamp) ||
640         (Left.Tok.is(tok::l_paren) && !Right.Tok.is(tok::r_paren));
641   }
642 
643   const UnwrappedLine &Line;
644   FormatStyle Style;
645   SourceManager &SourceMgr;
646   std::vector<TokenAnnotation> Annotations;
647 };
648 
649 class Formatter : public UnwrappedLineConsumer {
650 public:
651   Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
652             const std::vector<CharSourceRange> &Ranges)
653       : Style(Style),
654         Lex(Lex),
655         SourceMgr(SourceMgr),
656         Ranges(Ranges) {
657   }
658 
659   tooling::Replacements format() {
660     UnwrappedLineParser Parser(Lex, SourceMgr, *this);
661     Parser.parse();
662     return Replaces;
663   }
664 
665 private:
666   virtual void formatUnwrappedLine(const UnwrappedLine &TheLine) {
667     if (TheLine.Tokens.size() == 0)
668       return;
669 
670     CharSourceRange LineRange =
671         CharSourceRange::getTokenRange(TheLine.Tokens.front().Tok.getLocation(),
672                                        TheLine.Tokens.back().Tok.getLocation());
673 
674     for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
675       if (SourceMgr.isBeforeInTranslationUnit(LineRange.getEnd(),
676                                               Ranges[i].getBegin()) ||
677           SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(),
678                                               LineRange.getBegin()))
679         continue;
680 
681       TokenAnnotator Annotator(TheLine, Style, SourceMgr);
682       Annotator.annotate();
683       UnwrappedLineFormatter Formatter(Style, SourceMgr, TheLine,
684                                        Annotator.getAnnotations(), Replaces);
685       Formatter.format();
686       return;
687     }
688   }
689 
690   FormatStyle Style;
691   Lexer &Lex;
692   SourceManager &SourceMgr;
693   tooling::Replacements Replaces;
694   std::vector<CharSourceRange> Ranges;
695 };
696 
697 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
698                                SourceManager &SourceMgr,
699                                std::vector<CharSourceRange> Ranges) {
700   Formatter formatter(Style, Lex, SourceMgr, Ranges);
701   return formatter.format();
702 }
703 
704 }  // namespace format
705 }  // namespace clang
706