Format.cpp revision ce912f45660613c1bc49696eb07ff7f8aecffe18 
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 "BreakableToken.h"
19#include "TokenAnnotator.h"
20#include "UnwrappedLineParser.h"
21#include "WhitespaceManager.h"
22#include "clang/Basic/Diagnostic.h"
23#include "clang/Basic/OperatorPrecedence.h"
24#include "clang/Basic/SourceManager.h"
25#include "clang/Format/Format.h"
26#include "clang/Lex/Lexer.h"
27#include "llvm/ADT/STLExtras.h"
28#include "llvm/Support/Allocator.h"
29#include "llvm/Support/Debug.h"
30#include "llvm/Support/YAMLTraits.h"
31#include <queue>
32#include <string>
33
34namespace llvm {
35namespace yaml {
36template <>
37struct ScalarEnumerationTraits<clang::format::FormatStyle::LanguageStandard> {
38  static void enumeration(IO &IO,
39                          clang::format::FormatStyle::LanguageStandard &Value) {
40    IO.enumCase(Value, "C++03", clang::format::FormatStyle::LS_Cpp03);
41    IO.enumCase(Value, "C++11", clang::format::FormatStyle::LS_Cpp11);
42    IO.enumCase(Value, "Auto", clang::format::FormatStyle::LS_Auto);
43  }
44};
45
46template <>
47struct ScalarEnumerationTraits<clang::format::FormatStyle::BraceBreakingStyle> {
48  static void
49  enumeration(IO &IO, clang::format::FormatStyle::BraceBreakingStyle &Value) {
50    IO.enumCase(Value, "Attach", clang::format::FormatStyle::BS_Attach);
51    IO.enumCase(Value, "Linux", clang::format::FormatStyle::BS_Linux);
52    IO.enumCase(Value, "Stroustrup", clang::format::FormatStyle::BS_Stroustrup);
53  }
54};
55
56template <> struct MappingTraits<clang::format::FormatStyle> {
57  static void mapping(llvm::yaml::IO &IO, clang::format::FormatStyle &Style) {
58    if (IO.outputting()) {
59      StringRef StylesArray[] = { "LLVM", "Google", "Chromium", "Mozilla" };
60      ArrayRef<StringRef> Styles(StylesArray);
61      for (size_t i = 0, e = Styles.size(); i < e; ++i) {
62        StringRef StyleName(Styles[i]);
63        clang::format::FormatStyle PredefinedStyle;
64        if (clang::format::getPredefinedStyle(StyleName, &PredefinedStyle) &&
65            Style == PredefinedStyle) {
66          IO.mapOptional("# BasedOnStyle", StyleName);
67          break;
68        }
69      }
70    } else {
71      StringRef BasedOnStyle;
72      IO.mapOptional("BasedOnStyle", BasedOnStyle);
73      if (!BasedOnStyle.empty())
74        if (!clang::format::getPredefinedStyle(BasedOnStyle, &Style)) {
75          IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
76          return;
77        }
78    }
79
80    IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
81    IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
82    IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
83                   Style.AllowAllParametersOfDeclarationOnNextLine);
84    IO.mapOptional("AllowShortIfStatementsOnASingleLine",
85                   Style.AllowShortIfStatementsOnASingleLine);
86    IO.mapOptional("AllowShortLoopsOnASingleLine",
87                   Style.AllowShortLoopsOnASingleLine);
88    IO.mapOptional("AlwaysBreakTemplateDeclarations",
89                   Style.AlwaysBreakTemplateDeclarations);
90    IO.mapOptional("BinPackParameters", Style.BinPackParameters);
91    IO.mapOptional("ColumnLimit", Style.ColumnLimit);
92    IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
93                   Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
94    IO.mapOptional("DerivePointerBinding", Style.DerivePointerBinding);
95    IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
96    IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
97    IO.mapOptional("ObjCSpaceBeforeProtocolList",
98                   Style.ObjCSpaceBeforeProtocolList);
99    IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
100    IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
101                   Style.PenaltyReturnTypeOnItsOwnLine);
102    IO.mapOptional("PointerBindsToType", Style.PointerBindsToType);
103    IO.mapOptional("SpacesBeforeTrailingComments",
104                   Style.SpacesBeforeTrailingComments);
105    IO.mapOptional("SpacesInBracedLists", Style.SpacesInBracedLists);
106    IO.mapOptional("Standard", Style.Standard);
107    IO.mapOptional("IndentWidth", Style.IndentWidth);
108    IO.mapOptional("UseTab", Style.UseTab);
109    IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
110  }
111};
112}
113}
114
115namespace clang {
116namespace format {
117
118FormatStyle getLLVMStyle() {
119  FormatStyle LLVMStyle;
120  LLVMStyle.AccessModifierOffset = -2;
121  LLVMStyle.AlignEscapedNewlinesLeft = false;
122  LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
123  LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
124  LLVMStyle.AllowShortLoopsOnASingleLine = false;
125  LLVMStyle.AlwaysBreakTemplateDeclarations = false;
126  LLVMStyle.BinPackParameters = true;
127  LLVMStyle.ColumnLimit = 80;
128  LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
129  LLVMStyle.DerivePointerBinding = false;
130  LLVMStyle.IndentCaseLabels = false;
131  LLVMStyle.MaxEmptyLinesToKeep = 1;
132  LLVMStyle.ObjCSpaceBeforeProtocolList = true;
133  LLVMStyle.PenaltyExcessCharacter = 1000000;
134  LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 75;
135  LLVMStyle.PointerBindsToType = false;
136  LLVMStyle.SpacesBeforeTrailingComments = 1;
137  LLVMStyle.SpacesInBracedLists = true;
138  LLVMStyle.Standard = FormatStyle::LS_Cpp03;
139  LLVMStyle.IndentWidth = 2;
140  LLVMStyle.UseTab = false;
141  LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
142  return LLVMStyle;
143}
144
145FormatStyle getGoogleStyle() {
146  FormatStyle GoogleStyle;
147  GoogleStyle.AccessModifierOffset = -1;
148  GoogleStyle.AlignEscapedNewlinesLeft = true;
149  GoogleStyle.AllowAllParametersOfDeclarationOnNextLine = true;
150  GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
151  GoogleStyle.AllowShortLoopsOnASingleLine = true;
152  GoogleStyle.AlwaysBreakTemplateDeclarations = true;
153  GoogleStyle.BinPackParameters = true;
154  GoogleStyle.ColumnLimit = 80;
155  GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
156  GoogleStyle.DerivePointerBinding = true;
157  GoogleStyle.IndentCaseLabels = true;
158  GoogleStyle.MaxEmptyLinesToKeep = 1;
159  GoogleStyle.ObjCSpaceBeforeProtocolList = false;
160  GoogleStyle.PenaltyExcessCharacter = 1000000;
161  GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
162  GoogleStyle.PointerBindsToType = true;
163  GoogleStyle.SpacesBeforeTrailingComments = 2;
164  GoogleStyle.SpacesInBracedLists = false;
165  GoogleStyle.Standard = FormatStyle::LS_Auto;
166  GoogleStyle.IndentWidth = 2;
167  GoogleStyle.UseTab = false;
168  GoogleStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
169  return GoogleStyle;
170}
171
172FormatStyle getChromiumStyle() {
173  FormatStyle ChromiumStyle = getGoogleStyle();
174  ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
175  ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
176  ChromiumStyle.AllowShortLoopsOnASingleLine = false;
177  ChromiumStyle.BinPackParameters = false;
178  ChromiumStyle.Standard = FormatStyle::LS_Cpp03;
179  ChromiumStyle.DerivePointerBinding = false;
180  return ChromiumStyle;
181}
182
183FormatStyle getMozillaStyle() {
184  FormatStyle MozillaStyle = getLLVMStyle();
185  MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
186  MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
187  MozillaStyle.DerivePointerBinding = true;
188  MozillaStyle.IndentCaseLabels = true;
189  MozillaStyle.ObjCSpaceBeforeProtocolList = false;
190  MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
191  MozillaStyle.PointerBindsToType = true;
192  return MozillaStyle;
193}
194
195bool getPredefinedStyle(StringRef Name, FormatStyle *Style) {
196  if (Name.equals_lower("llvm"))
197    *Style = getLLVMStyle();
198  else if (Name.equals_lower("chromium"))
199    *Style = getChromiumStyle();
200  else if (Name.equals_lower("mozilla"))
201    *Style = getMozillaStyle();
202  else if (Name.equals_lower("google"))
203    *Style = getGoogleStyle();
204  else
205    return false;
206
207  return true;
208}
209
210llvm::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
211  if (Text.trim().empty())
212    return llvm::make_error_code(llvm::errc::invalid_argument);
213  llvm::yaml::Input Input(Text);
214  Input >> *Style;
215  return Input.error();
216}
217
218std::string configurationAsText(const FormatStyle &Style) {
219  std::string Text;
220  llvm::raw_string_ostream Stream(Text);
221  llvm::yaml::Output Output(Stream);
222  // We use the same mapping method for input and output, so we need a non-const
223  // reference here.
224  FormatStyle NonConstStyle = Style;
225  Output << NonConstStyle;
226  return Stream.str();
227}
228
229// Returns the length of everything up to the first possible line break after
230// the ), ], } or > matching \c Tok.
231static unsigned getLengthToMatchingParen(const FormatToken &Tok) {
232  if (Tok.MatchingParen == NULL)
233    return 0;
234  FormatToken *End = Tok.MatchingParen;
235  while (End->Next && !End->Next->CanBreakBefore) {
236    End = End->Next;
237  }
238  return End->TotalLength - Tok.TotalLength + 1;
239}
240
241class UnwrappedLineFormatter {
242public:
243  UnwrappedLineFormatter(const FormatStyle &Style, SourceManager &SourceMgr,
244                         const AnnotatedLine &Line, unsigned FirstIndent,
245                         const FormatToken *RootToken,
246                         WhitespaceManager &Whitespaces)
247      : Style(Style), SourceMgr(SourceMgr), Line(Line),
248        FirstIndent(FirstIndent), RootToken(RootToken),
249        Whitespaces(Whitespaces), Count(0) {}
250
251  /// \brief Formats an \c UnwrappedLine.
252  void format(const AnnotatedLine *NextLine) {
253    // Initialize state dependent on indent.
254    LineState State;
255    State.Column = FirstIndent;
256    State.NextToken = RootToken;
257    State.Stack.push_back(
258        ParenState(FirstIndent, FirstIndent, /*AvoidBinPacking=*/ false,
259                   /*NoLineBreak=*/ false));
260    State.LineContainsContinuedForLoopSection = false;
261    State.ParenLevel = 0;
262    State.StartOfStringLiteral = 0;
263    State.StartOfLineLevel = State.ParenLevel;
264    State.LowestCallLevel = State.ParenLevel;
265    State.IgnoreStackForComparison = false;
266
267    // The first token has already been indented and thus consumed.
268    moveStateToNextToken(State, /*DryRun=*/ false);
269
270    // If everything fits on a single line, just put it there.
271    unsigned ColumnLimit = Style.ColumnLimit;
272    if (NextLine && NextLine->InPPDirective &&
273        !NextLine->First->HasUnescapedNewline)
274      ColumnLimit = getColumnLimit();
275    if (Line.Last->TotalLength <= ColumnLimit - FirstIndent) {
276      while (State.NextToken != NULL) {
277        addTokenToState(false, false, State);
278      }
279    }
280
281    // If the ObjC method declaration does not fit on a line, we should format
282    // it with one arg per line.
283    if (Line.Type == LT_ObjCMethodDecl)
284      State.Stack.back().BreakBeforeParameter = true;
285
286    // Find best solution in solution space.
287    analyzeSolutionSpace(State);
288  }
289
290private:
291  void DebugTokenState(const FormatToken &FormatTok) {
292    const Token &Tok = FormatTok.Tok;
293    llvm::dbgs() << StringRef(SourceMgr.getCharacterData(Tok.getLocation()),
294                              Tok.getLength());
295    llvm::dbgs();
296  }
297
298  struct ParenState {
299    ParenState(unsigned Indent, unsigned LastSpace, bool AvoidBinPacking,
300               bool NoLineBreak)
301        : Indent(Indent), LastSpace(LastSpace), FirstLessLess(0),
302          BreakBeforeClosingBrace(false), QuestionColumn(0),
303          AvoidBinPacking(AvoidBinPacking), BreakBeforeParameter(false),
304          NoLineBreak(NoLineBreak), ColonPos(0), StartOfFunctionCall(0),
305          NestedNameSpecifierContinuation(0), CallContinuation(0),
306          VariablePos(0), ForFakeParenthesis(false) {}
307
308    /// \brief The position to which a specific parenthesis level needs to be
309    /// indented.
310    unsigned Indent;
311
312    /// \brief The position of the last space on each level.
313    ///
314    /// Used e.g. to break like:
315    /// functionCall(Parameter, otherCall(
316    ///                             OtherParameter));
317    unsigned LastSpace;
318
319    /// \brief The position the first "<<" operator encountered on each level.
320    ///
321    /// Used to align "<<" operators. 0 if no such operator has been encountered
322    /// on a level.
323    unsigned FirstLessLess;
324
325    /// \brief Whether a newline needs to be inserted before the block's closing
326    /// brace.
327    ///
328    /// We only want to insert a newline before the closing brace if there also
329    /// was a newline after the beginning left brace.
330    bool BreakBeforeClosingBrace;
331
332    /// \brief The column of a \c ? in a conditional expression;
333    unsigned QuestionColumn;
334
335    /// \brief Avoid bin packing, i.e. multiple parameters/elements on multiple
336    /// lines, in this context.
337    bool AvoidBinPacking;
338
339    /// \brief Break after the next comma (or all the commas in this context if
340    /// \c AvoidBinPacking is \c true).
341    bool BreakBeforeParameter;
342
343    /// \brief Line breaking in this context would break a formatting rule.
344    bool NoLineBreak;
345
346    /// \brief The position of the colon in an ObjC method declaration/call.
347    unsigned ColonPos;
348
349    /// \brief The start of the most recent function in a builder-type call.
350    unsigned StartOfFunctionCall;
351
352    /// \brief If a nested name specifier was broken over multiple lines, this
353    /// contains the start column of the second line. Otherwise 0.
354    unsigned NestedNameSpecifierContinuation;
355
356    /// \brief If a call expression was broken over multiple lines, this
357    /// contains the start column of the second line. Otherwise 0.
358    unsigned CallContinuation;
359
360    /// \brief The column of the first variable name in a variable declaration.
361    ///
362    /// Used to align further variables if necessary.
363    unsigned VariablePos;
364
365    /// \brief \c true if this \c ParenState was created for a fake parenthesis.
366    ///
367    /// Does not need to be considered for memoization / the comparison function
368    /// as otherwise identical states will have the same fake/non-fake
369    /// \c ParenStates.
370    bool ForFakeParenthesis;
371
372    bool operator<(const ParenState &Other) const {
373      if (Indent != Other.Indent)
374        return Indent < Other.Indent;
375      if (LastSpace != Other.LastSpace)
376        return LastSpace < Other.LastSpace;
377      if (FirstLessLess != Other.FirstLessLess)
378        return FirstLessLess < Other.FirstLessLess;
379      if (BreakBeforeClosingBrace != Other.BreakBeforeClosingBrace)
380        return BreakBeforeClosingBrace;
381      if (QuestionColumn != Other.QuestionColumn)
382        return QuestionColumn < Other.QuestionColumn;
383      if (AvoidBinPacking != Other.AvoidBinPacking)
384        return AvoidBinPacking;
385      if (BreakBeforeParameter != Other.BreakBeforeParameter)
386        return BreakBeforeParameter;
387      if (NoLineBreak != Other.NoLineBreak)
388        return NoLineBreak;
389      if (ColonPos != Other.ColonPos)
390        return ColonPos < Other.ColonPos;
391      if (StartOfFunctionCall != Other.StartOfFunctionCall)
392        return StartOfFunctionCall < Other.StartOfFunctionCall;
393      if (CallContinuation != Other.CallContinuation)
394        return CallContinuation < Other.CallContinuation;
395      if (VariablePos != Other.VariablePos)
396        return VariablePos < Other.VariablePos;
397      return false;
398    }
399  };
400
401  /// \brief The current state when indenting a unwrapped line.
402  ///
403  /// As the indenting tries different combinations this is copied by value.
404  struct LineState {
405    /// \brief The number of used columns in the current line.
406    unsigned Column;
407
408    /// \brief The token that needs to be next formatted.
409    const FormatToken *NextToken;
410
411    /// \brief \c true if this line contains a continued for-loop section.
412    bool LineContainsContinuedForLoopSection;
413
414    /// \brief The level of nesting inside (), [], <> and {}.
415    unsigned ParenLevel;
416
417    /// \brief The \c ParenLevel at the start of this line.
418    unsigned StartOfLineLevel;
419
420    /// \brief The lowest \c ParenLevel of "." or "->" on the current line.
421    unsigned LowestCallLevel;
422
423    /// \brief The start column of the string literal, if we're in a string
424    /// literal sequence, 0 otherwise.
425    unsigned StartOfStringLiteral;
426
427    /// \brief A stack keeping track of properties applying to parenthesis
428    /// levels.
429    std::vector<ParenState> Stack;
430
431    /// \brief Ignore the stack of \c ParenStates for state comparison.
432    ///
433    /// In long and deeply nested unwrapped lines, the current algorithm can
434    /// be insufficient for finding the best formatting with a reasonable amount
435    /// of time and memory. Setting this flag will effectively lead to the
436    /// algorithm not analyzing some combinations. However, these combinations
437    /// rarely contain the optimal solution: In short, accepting a higher
438    /// penalty early would need to lead to different values in the \c
439    /// ParenState stack (in an otherwise identical state) and these different
440    /// values would need to lead to a significant amount of avoided penalty
441    /// later.
442    ///
443    /// FIXME: Come up with a better algorithm instead.
444    bool IgnoreStackForComparison;
445
446    /// \brief Comparison operator to be able to used \c LineState in \c map.
447    bool operator<(const LineState &Other) const {
448      if (NextToken != Other.NextToken)
449        return NextToken < Other.NextToken;
450      if (Column != Other.Column)
451        return Column < Other.Column;
452      if (LineContainsContinuedForLoopSection !=
453          Other.LineContainsContinuedForLoopSection)
454        return LineContainsContinuedForLoopSection;
455      if (ParenLevel != Other.ParenLevel)
456        return ParenLevel < Other.ParenLevel;
457      if (StartOfLineLevel != Other.StartOfLineLevel)
458        return StartOfLineLevel < Other.StartOfLineLevel;
459      if (LowestCallLevel != Other.LowestCallLevel)
460        return LowestCallLevel < Other.LowestCallLevel;
461      if (StartOfStringLiteral != Other.StartOfStringLiteral)
462        return StartOfStringLiteral < Other.StartOfStringLiteral;
463      if (IgnoreStackForComparison || Other.IgnoreStackForComparison)
464        return false;
465      return Stack < Other.Stack;
466    }
467  };
468
469  /// \brief Appends the next token to \p State and updates information
470  /// necessary for indentation.
471  ///
472  /// Puts the token on the current line if \p Newline is \c true and adds a
473  /// line break and necessary indentation otherwise.
474  ///
475  /// If \p DryRun is \c false, also creates and stores the required
476  /// \c Replacement.
477  unsigned addTokenToState(bool Newline, bool DryRun, LineState &State) {
478    const FormatToken &Current = *State.NextToken;
479    const FormatToken &Previous = *State.NextToken->Previous;
480
481    if (State.Stack.size() == 0 || Current.Type == TT_ImplicitStringLiteral) {
482      // FIXME: Is this correct?
483      int WhitespaceLength = SourceMgr.getSpellingColumnNumber(
484                                 State.NextToken->WhitespaceRange.getEnd()) -
485                             SourceMgr.getSpellingColumnNumber(
486                                 State.NextToken->WhitespaceRange.getBegin());
487      State.Column += WhitespaceLength + State.NextToken->TokenLength;
488      State.NextToken = State.NextToken->Next;
489      return 0;
490    }
491
492    // If we are continuing an expression, we want to indent an extra 4 spaces.
493    unsigned ContinuationIndent =
494        std::max(State.Stack.back().LastSpace, State.Stack.back().Indent) + 4;
495    if (Newline) {
496      if (Current.is(tok::r_brace)) {
497        State.Column = Line.Level * Style.IndentWidth;
498      } else if (Current.is(tok::string_literal) &&
499                 State.StartOfStringLiteral != 0) {
500        State.Column = State.StartOfStringLiteral;
501        State.Stack.back().BreakBeforeParameter = true;
502      } else if (Current.is(tok::lessless) &&
503                 State.Stack.back().FirstLessLess != 0) {
504        State.Column = State.Stack.back().FirstLessLess;
505      } else if (Current.isOneOf(tok::period, tok::arrow) &&
506                 Current.Type != TT_DesignatedInitializerPeriod) {
507        if (State.Stack.back().CallContinuation == 0) {
508          State.Column = ContinuationIndent;
509          State.Stack.back().CallContinuation = State.Column;
510        } else {
511          State.Column = State.Stack.back().CallContinuation;
512        }
513      } else if (Current.Type == TT_ConditionalExpr) {
514        State.Column = State.Stack.back().QuestionColumn;
515      } else if (Previous.is(tok::comma) &&
516                 State.Stack.back().VariablePos != 0) {
517        State.Column = State.Stack.back().VariablePos;
518      } else if (Previous.ClosesTemplateDeclaration ||
519                 (Current.Type == TT_StartOfName && State.ParenLevel == 0 &&
520                  Line.StartsDefinition)) {
521        State.Column = State.Stack.back().Indent;
522      } else if (Current.Type == TT_ObjCSelectorName) {
523        if (State.Stack.back().ColonPos > Current.TokenLength) {
524          State.Column = State.Stack.back().ColonPos - Current.TokenLength;
525        } else {
526          State.Column = State.Stack.back().Indent;
527          State.Stack.back().ColonPos = State.Column + Current.TokenLength;
528        }
529      } else if (Current.Type == TT_StartOfName ||
530                 Previous.isOneOf(tok::coloncolon, tok::equal) ||
531                 Previous.Type == TT_ObjCMethodExpr) {
532        State.Column = ContinuationIndent;
533      } else {
534        State.Column = State.Stack.back().Indent;
535        // Ensure that we fall back to indenting 4 spaces instead of just
536        // flushing continuations left.
537        if (State.Column == FirstIndent)
538          State.Column += 4;
539      }
540
541      if (Current.is(tok::question))
542        State.Stack.back().BreakBeforeParameter = true;
543      if ((Previous.isOneOf(tok::comma, tok::semi) &&
544           !State.Stack.back().AvoidBinPacking) ||
545          Previous.Type == TT_BinaryOperator)
546        State.Stack.back().BreakBeforeParameter = false;
547      if (Previous.Type == TT_TemplateCloser && State.ParenLevel == 0)
548        State.Stack.back().BreakBeforeParameter = false;
549
550      if (!DryRun) {
551        unsigned NewLines = 1;
552        if (Current.Type == TT_LineComment)
553          NewLines = std::max(
554              NewLines,
555              std::min(Current.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1));
556        Whitespaces.replaceWhitespace(Current, NewLines, State.Column,
557                                      State.Column, Line.InPPDirective);
558      }
559
560      State.Stack.back().LastSpace = State.Column;
561      if (Current.isOneOf(tok::arrow, tok::period) &&
562          Current.Type != TT_DesignatedInitializerPeriod)
563        State.Stack.back().LastSpace += Current.TokenLength;
564      State.StartOfLineLevel = State.ParenLevel;
565      State.LowestCallLevel = State.ParenLevel;
566
567      // Any break on this level means that the parent level has been broken
568      // and we need to avoid bin packing there.
569      for (unsigned i = 0, e = State.Stack.size() - 1; i != e; ++i) {
570        State.Stack[i].BreakBeforeParameter = true;
571      }
572      const FormatToken *TokenBefore = Current.getPreviousNoneComment();
573      if (TokenBefore && !TokenBefore->isOneOf(tok::comma, tok::semi) &&
574          TokenBefore->Type != TT_TemplateCloser &&
575          TokenBefore->Type != TT_BinaryOperator && !TokenBefore->opensScope())
576        State.Stack.back().BreakBeforeParameter = true;
577
578      // If we break after {, we should also break before the corresponding }.
579      if (Previous.is(tok::l_brace))
580        State.Stack.back().BreakBeforeClosingBrace = true;
581
582      if (State.Stack.back().AvoidBinPacking) {
583        // If we are breaking after '(', '{', '<', this is not bin packing
584        // unless AllowAllParametersOfDeclarationOnNextLine is false.
585        if (!(Previous.isOneOf(tok::l_paren, tok::l_brace) ||
586              Previous.Type == TT_BinaryOperator) ||
587            (!Style.AllowAllParametersOfDeclarationOnNextLine &&
588             Line.MustBeDeclaration))
589          State.Stack.back().BreakBeforeParameter = true;
590      }
591    } else {
592      if (Current.is(tok::equal) &&
593          (RootToken->is(tok::kw_for) || State.ParenLevel == 0) &&
594          State.Stack.back().VariablePos == 0) {
595        State.Stack.back().VariablePos = State.Column;
596        // Move over * and & if they are bound to the variable name.
597        const FormatToken *Tok = &Previous;
598        while (Tok && State.Stack.back().VariablePos >= Tok->TokenLength) {
599          State.Stack.back().VariablePos -= Tok->TokenLength;
600          if (Tok->SpacesRequiredBefore != 0)
601            break;
602          Tok = Tok->Previous;
603        }
604        if (Previous.PartOfMultiVariableDeclStmt)
605          State.Stack.back().LastSpace = State.Stack.back().VariablePos;
606      }
607
608      unsigned Spaces = State.NextToken->SpacesRequiredBefore;
609
610      if (!DryRun)
611        Whitespaces.replaceWhitespace(Current, 0, Spaces,
612                                      State.Column + Spaces);
613
614      if (Current.Type == TT_ObjCSelectorName &&
615          State.Stack.back().ColonPos == 0) {
616        if (State.Stack.back().Indent + Current.LongestObjCSelectorName >
617            State.Column + Spaces + Current.TokenLength)
618          State.Stack.back().ColonPos =
619              State.Stack.back().Indent + Current.LongestObjCSelectorName;
620        else
621          State.Stack.back().ColonPos =
622              State.Column + Spaces + Current.TokenLength;
623      }
624
625      if (Previous.opensScope() && Previous.Type != TT_ObjCMethodExpr &&
626          Current.Type != TT_LineComment)
627        State.Stack.back().Indent = State.Column + Spaces;
628      if (Previous.is(tok::comma) && !Current.isTrailingComment() &&
629          State.Stack.back().AvoidBinPacking)
630        State.Stack.back().NoLineBreak = true;
631
632      State.Column += Spaces;
633      if (Current.is(tok::l_paren) && Previous.isOneOf(tok::kw_if, tok::kw_for))
634        // Treat the condition inside an if as if it was a second function
635        // parameter, i.e. let nested calls have an indent of 4.
636        State.Stack.back().LastSpace = State.Column + 1; // 1 is length of "(".
637      else if (Previous.is(tok::comma))
638        State.Stack.back().LastSpace = State.Column;
639      else if ((Previous.Type == TT_BinaryOperator ||
640                Previous.Type == TT_ConditionalExpr ||
641                Previous.Type == TT_CtorInitializerColon) &&
642               !(Previous.getPrecedence() == prec::Assignment &&
643                 Current.FakeLParens.empty()))
644        // Always indent relative to the RHS of the expression unless this is a
645        // simple assignment without binary expression on the RHS.
646        State.Stack.back().LastSpace = State.Column;
647      else if (Previous.Type == TT_InheritanceColon)
648        State.Stack.back().Indent = State.Column;
649      else if (Previous.opensScope() && !Current.FakeLParens.empty())
650        // If this function has multiple parameters or a binary expression
651        // parameter, indent nested calls from the start of the first parameter.
652        State.Stack.back().LastSpace = State.Column;
653    }
654
655    return moveStateToNextToken(State, DryRun);
656  }
657
658  /// \brief Mark the next token as consumed in \p State and modify its stacks
659  /// accordingly.
660  unsigned moveStateToNextToken(LineState &State, bool DryRun) {
661    const FormatToken &Current = *State.NextToken;
662    assert(State.Stack.size());
663
664    if (Current.Type == TT_InheritanceColon)
665      State.Stack.back().AvoidBinPacking = true;
666    if (Current.is(tok::lessless) && State.Stack.back().FirstLessLess == 0)
667      State.Stack.back().FirstLessLess = State.Column;
668    if (Current.is(tok::question))
669      State.Stack.back().QuestionColumn = State.Column;
670    if (Current.isOneOf(tok::period, tok::arrow)) {
671      State.LowestCallLevel = std::min(State.LowestCallLevel, State.ParenLevel);
672      if (Line.Type == LT_BuilderTypeCall && State.ParenLevel == 0)
673        State.Stack.back().StartOfFunctionCall =
674            Current.LastInChainOfCalls ? 0 : State.Column + Current.TokenLength;
675    }
676    if (Current.Type == TT_CtorInitializerColon) {
677      // Indent 2 from the column, so:
678      // SomeClass::SomeClass()
679      //     : First(...), ...
680      //       Next(...)
681      //       ^ line up here.
682      State.Stack.back().Indent = State.Column + 2;
683      if (Style.ConstructorInitializerAllOnOneLineOrOnePerLine)
684        State.Stack.back().AvoidBinPacking = true;
685      State.Stack.back().BreakBeforeParameter = false;
686    }
687
688    // If return returns a binary expression, align after it.
689    if (Current.is(tok::kw_return) && !Current.FakeLParens.empty())
690      State.Stack.back().LastSpace = State.Column + 7;
691
692    // In ObjC method declaration we align on the ":" of parameters, but we need
693    // to ensure that we indent parameters on subsequent lines by at least 4.
694    if (Current.Type == TT_ObjCMethodSpecifier)
695      State.Stack.back().Indent += 4;
696
697    // Insert scopes created by fake parenthesis.
698    const FormatToken *Previous = Current.getPreviousNoneComment();
699    // Don't add extra indentation for the first fake parenthesis after
700    // 'return', assignements or opening <({[. The indentation for these cases
701    // is special cased.
702    bool SkipFirstExtraIndent =
703        Current.is(tok::kw_return) ||
704        (Previous && (Previous->opensScope() ||
705                      Previous->getPrecedence() == prec::Assignment));
706    for (SmallVector<prec::Level, 4>::const_reverse_iterator
707             I = Current.FakeLParens.rbegin(),
708             E = Current.FakeLParens.rend();
709         I != E; ++I) {
710      ParenState NewParenState = State.Stack.back();
711      NewParenState.ForFakeParenthesis = true;
712      NewParenState.Indent =
713          std::max(std::max(State.Column, NewParenState.Indent),
714                   State.Stack.back().LastSpace);
715
716      // Always indent conditional expressions. Never indent expression where
717      // the 'operator' is ',', ';' or an assignment (i.e. *I <=
718      // prec::Assignment) as those have different indentation rules. Indent
719      // other expression, unless the indentation needs to be skipped.
720      if (*I == prec::Conditional ||
721          (!SkipFirstExtraIndent && *I > prec::Assignment))
722        NewParenState.Indent += 4;
723      if (Previous && !Previous->opensScope())
724        NewParenState.BreakBeforeParameter = false;
725      State.Stack.push_back(NewParenState);
726      SkipFirstExtraIndent = false;
727    }
728
729    // If we encounter an opening (, [, { or <, we add a level to our stacks to
730    // prepare for the following tokens.
731    if (Current.opensScope()) {
732      unsigned NewIndent;
733      unsigned LastSpace = State.Stack.back().LastSpace;
734      bool AvoidBinPacking;
735      if (Current.is(tok::l_brace)) {
736        NewIndent = Style.IndentWidth + LastSpace;
737        const FormatToken *NextNoComment = Current.getNextNoneComment();
738        AvoidBinPacking = NextNoComment &&
739                          NextNoComment->Type == TT_DesignatedInitializerPeriod;
740      } else {
741        NewIndent =
742            4 + std::max(LastSpace, State.Stack.back().StartOfFunctionCall);
743        AvoidBinPacking = !Style.BinPackParameters;
744      }
745
746      State.Stack.push_back(ParenState(NewIndent, LastSpace, AvoidBinPacking,
747                                       State.Stack.back().NoLineBreak));
748      ++State.ParenLevel;
749    }
750
751    // If this '[' opens an ObjC call, determine whether all parameters fit into
752    // one line and put one per line if they don't.
753    if (Current.is(tok::l_square) && Current.Type == TT_ObjCMethodExpr &&
754        Current.MatchingParen != NULL) {
755      if (getLengthToMatchingParen(Current) + State.Column > getColumnLimit())
756        State.Stack.back().BreakBeforeParameter = true;
757    }
758
759    // If we encounter a closing ), ], } or >, we can remove a level from our
760    // stacks.
761    if (Current.isOneOf(tok::r_paren, tok::r_square) ||
762        (Current.is(tok::r_brace) && State.NextToken != RootToken) ||
763        State.NextToken->Type == TT_TemplateCloser) {
764      State.Stack.pop_back();
765      --State.ParenLevel;
766    }
767
768    // Remove scopes created by fake parenthesis.
769    for (unsigned i = 0, e = Current.FakeRParens; i != e; ++i) {
770      unsigned VariablePos = State.Stack.back().VariablePos;
771      State.Stack.pop_back();
772      State.Stack.back().VariablePos = VariablePos;
773    }
774
775    if (Current.is(tok::string_literal) && State.StartOfStringLiteral == 0) {
776      State.StartOfStringLiteral = State.Column;
777    } else if (!Current.isOneOf(tok::comment, tok::identifier, tok::hash,
778                                tok::string_literal)) {
779      State.StartOfStringLiteral = 0;
780    }
781
782    State.Column += Current.TokenLength;
783
784    State.NextToken = State.NextToken->Next;
785
786    return breakProtrudingToken(Current, State, DryRun);
787  }
788
789  /// \brief If the current token sticks out over the end of the line, break
790  /// it if possible.
791  ///
792  /// \returns An extra penalty if a token was broken, otherwise 0.
793  ///
794  /// Note that the penalty of the token protruding the allowed line length is
795  /// already handled in \c addNextStateToQueue; the returned penalty will only
796  /// cover the cost of the additional line breaks.
797  unsigned breakProtrudingToken(const FormatToken &Current, LineState &State,
798                                bool DryRun) {
799    unsigned UnbreakableTailLength = Current.UnbreakableTailLength;
800    llvm::OwningPtr<BreakableToken> Token;
801    unsigned StartColumn = State.Column - Current.TokenLength;
802    unsigned OriginalStartColumn =
803        SourceMgr.getSpellingColumnNumber(Current.getStartOfNonWhitespace()) -
804        1;
805
806    if (Current.is(tok::string_literal) &&
807        Current.Type != TT_ImplicitStringLiteral) {
808      // Only break up default narrow strings.
809      const char *LiteralData =
810          SourceMgr.getCharacterData(Current.getStartOfNonWhitespace());
811      if (!LiteralData || *LiteralData != '"')
812        return 0;
813
814      Token.reset(new BreakableStringLiteral(Current, StartColumn));
815    } else if (Current.Type == TT_BlockComment) {
816      BreakableBlockComment *BBC = new BreakableBlockComment(
817          Style, Current, StartColumn, OriginalStartColumn, !Current.Previous);
818      Token.reset(BBC);
819    } else if (Current.Type == TT_LineComment &&
820               (Current.Previous == NULL ||
821                Current.Previous->Type != TT_ImplicitStringLiteral)) {
822      Token.reset(new BreakableLineComment(Current, StartColumn));
823    } else {
824      return 0;
825    }
826    if (UnbreakableTailLength >= getColumnLimit())
827      return 0;
828    unsigned RemainingSpace = getColumnLimit() - UnbreakableTailLength;
829
830    bool BreakInserted = false;
831    unsigned Penalty = 0;
832    unsigned PositionAfterLastLineInToken = 0;
833    for (unsigned LineIndex = 0, EndIndex = Token->getLineCount();
834         LineIndex != EndIndex; ++LineIndex) {
835      if (!DryRun) {
836        Token->replaceWhitespaceBefore(LineIndex, Line.InPPDirective,
837                                       Whitespaces);
838      }
839      unsigned TailOffset = 0;
840      unsigned RemainingTokenLength =
841          Token->getLineLengthAfterSplit(LineIndex, TailOffset);
842      while (RemainingTokenLength > RemainingSpace) {
843        BreakableToken::Split Split =
844            Token->getSplit(LineIndex, TailOffset, getColumnLimit());
845        if (Split.first == StringRef::npos)
846          break;
847        assert(Split.first != 0);
848        unsigned NewRemainingTokenLength = Token->getLineLengthAfterSplit(
849            LineIndex, TailOffset + Split.first + Split.second);
850        assert(NewRemainingTokenLength < RemainingTokenLength);
851        if (!DryRun) {
852          Token->insertBreak(LineIndex, TailOffset, Split, Line.InPPDirective,
853                             Whitespaces);
854        }
855        TailOffset += Split.first + Split.second;
856        RemainingTokenLength = NewRemainingTokenLength;
857        Penalty += Style.PenaltyExcessCharacter;
858        BreakInserted = true;
859      }
860      PositionAfterLastLineInToken = RemainingTokenLength;
861    }
862
863    if (BreakInserted) {
864      State.Column = PositionAfterLastLineInToken;
865      for (unsigned i = 0, e = State.Stack.size(); i != e; ++i)
866        State.Stack[i].BreakBeforeParameter = true;
867      State.Stack.back().LastSpace = StartColumn;
868    }
869    return Penalty;
870  }
871
872  unsigned getColumnLimit() {
873    // In preprocessor directives reserve two chars for trailing " \"
874    return Style.ColumnLimit - (Line.InPPDirective ? 2 : 0);
875  }
876
877  /// \brief An edge in the solution space from \c Previous->State to \c State,
878  /// inserting a newline dependent on the \c NewLine.
879  struct StateNode {
880    StateNode(const LineState &State, bool NewLine, StateNode *Previous)
881        : State(State), NewLine(NewLine), Previous(Previous) {}
882    LineState State;
883    bool NewLine;
884    StateNode *Previous;
885  };
886
887  /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
888  ///
889  /// In case of equal penalties, we want to prefer states that were inserted
890  /// first. During state generation we make sure that we insert states first
891  /// that break the line as late as possible.
892  typedef std::pair<unsigned, unsigned> OrderedPenalty;
893
894  /// \brief An item in the prioritized BFS search queue. The \c StateNode's
895  /// \c State has the given \c OrderedPenalty.
896  typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
897
898  /// \brief The BFS queue type.
899  typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
900                              std::greater<QueueItem> > QueueType;
901
902  /// \brief Analyze the entire solution space starting from \p InitialState.
903  ///
904  /// This implements a variant of Dijkstra's algorithm on the graph that spans
905  /// the solution space (\c LineStates are the nodes). The algorithm tries to
906  /// find the shortest path (the one with lowest penalty) from \p InitialState
907  /// to a state where all tokens are placed.
908  void analyzeSolutionSpace(LineState &InitialState) {
909    std::set<LineState> Seen;
910
911    // Insert start element into queue.
912    StateNode *Node =
913        new (Allocator.Allocate()) StateNode(InitialState, false, NULL);
914    Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
915    ++Count;
916
917    // While not empty, take first element and follow edges.
918    while (!Queue.empty()) {
919      unsigned Penalty = Queue.top().first.first;
920      StateNode *Node = Queue.top().second;
921      if (Node->State.NextToken == NULL) {
922        DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
923        break;
924      }
925      Queue.pop();
926
927      // Cut off the analysis of certain solutions if the analysis gets too
928      // complex. See description of IgnoreStackForComparison.
929      if (Count > 10000)
930        Node->State.IgnoreStackForComparison = true;
931
932      if (!Seen.insert(Node->State).second)
933        // State already examined with lower penalty.
934        continue;
935
936      addNextStateToQueue(Penalty, Node, /*NewLine=*/ false);
937      addNextStateToQueue(Penalty, Node, /*NewLine=*/ true);
938    }
939
940    if (Queue.empty())
941      // We were unable to find a solution, do nothing.
942      // FIXME: Add diagnostic?
943      return;
944
945    // Reconstruct the solution.
946    reconstructPath(InitialState, Queue.top().second);
947    DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
948    DEBUG(llvm::dbgs() << "---\n");
949  }
950
951  void reconstructPath(LineState &State, StateNode *Current) {
952    std::deque<StateNode *> Path;
953    // We do not need a break before the initial token.
954    while (Current->Previous) {
955      Path.push_front(Current);
956      Current = Current->Previous;
957    }
958    for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
959         I != E; ++I) {
960      DEBUG({
961        if ((*I)->NewLine) {
962          llvm::dbgs() << "Penalty for splitting before "
963                       << (*I)->Previous->State.NextToken->Tok.getName() << ": "
964                       << (*I)->Previous->State.NextToken->SplitPenalty << "\n";
965        }
966      });
967      addTokenToState((*I)->NewLine, false, State);
968    }
969  }
970
971  /// \brief Add the following state to the analysis queue \c Queue.
972  ///
973  /// Assume the current state is \p PreviousNode and has been reached with a
974  /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
975  void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
976                           bool NewLine) {
977    if (NewLine && !canBreak(PreviousNode->State))
978      return;
979    if (!NewLine && mustBreak(PreviousNode->State))
980      return;
981    if (NewLine)
982      Penalty += PreviousNode->State.NextToken->SplitPenalty;
983
984    StateNode *Node = new (Allocator.Allocate())
985        StateNode(PreviousNode->State, NewLine, PreviousNode);
986    Penalty += addTokenToState(NewLine, true, Node->State);
987    if (Node->State.Column > getColumnLimit()) {
988      unsigned ExcessCharacters = Node->State.Column - getColumnLimit();
989      Penalty += Style.PenaltyExcessCharacter * ExcessCharacters;
990    }
991
992    Queue.push(QueueItem(OrderedPenalty(Penalty, Count), Node));
993    ++Count;
994  }
995
996  /// \brief Returns \c true, if a line break after \p State is allowed.
997  bool canBreak(const LineState &State) {
998    const FormatToken &Current = *State.NextToken;
999    const FormatToken &Previous = *Current.Previous;
1000    assert(&Previous == Current.Previous);
1001    if (!Current.CanBreakBefore &&
1002        !(Current.is(tok::r_brace) &&
1003          State.Stack.back().BreakBeforeClosingBrace))
1004      return false;
1005    // The opening "{" of a braced list has to be on the same line as the first
1006    // element if it is nested in another braced init list or function call.
1007    if (!Current.MustBreakBefore && Previous.is(tok::l_brace) &&
1008        Previous.Previous &&
1009        Previous.Previous->isOneOf(tok::l_brace, tok::l_paren, tok::comma))
1010      return false;
1011    // This prevents breaks like:
1012    //   ...
1013    //   SomeParameter, OtherParameter).DoSomething(
1014    //   ...
1015    // As they hide "DoSomething" and are generally bad for readability.
1016    if (Previous.opensScope() && State.LowestCallLevel < State.StartOfLineLevel)
1017      return false;
1018    return !State.Stack.back().NoLineBreak;
1019  }
1020
1021  /// \brief Returns \c true, if a line break after \p State is mandatory.
1022  bool mustBreak(const LineState &State) {
1023    const FormatToken &Current = *State.NextToken;
1024    const FormatToken &Previous = *Current.Previous;
1025    if (Current.MustBreakBefore || Current.Type == TT_InlineASMColon)
1026      return true;
1027    if (Current.is(tok::r_brace) && State.Stack.back().BreakBeforeClosingBrace)
1028      return true;
1029    if (Previous.is(tok::semi) && State.LineContainsContinuedForLoopSection)
1030      return true;
1031    if ((Previous.isOneOf(tok::comma, tok::semi) || Current.is(tok::question) ||
1032         Current.Type == TT_ConditionalExpr) &&
1033        State.Stack.back().BreakBeforeParameter &&
1034        !Current.isTrailingComment() &&
1035        !Current.isOneOf(tok::r_paren, tok::r_brace))
1036      return true;
1037
1038    // If we need to break somewhere inside the LHS of a binary expression, we
1039    // should also break after the operator.
1040    if (Previous.Type == TT_BinaryOperator &&
1041        Current.Type != TT_BinaryOperator && // Special case for ">>".
1042        !Current.isTrailingComment() &&
1043        !Previous.isOneOf(tok::lessless, tok::question) &&
1044        Previous.getPrecedence() != prec::Assignment &&
1045        State.Stack.back().BreakBeforeParameter)
1046      return true;
1047
1048    // FIXME: Comparing LongestObjCSelectorName to 0 is a hacky way of finding
1049    // out whether it is the first parameter. Clean this up.
1050    if (Current.Type == TT_ObjCSelectorName &&
1051        Current.LongestObjCSelectorName == 0 &&
1052        State.Stack.back().BreakBeforeParameter)
1053      return true;
1054    if ((Current.Type == TT_CtorInitializerColon ||
1055         (Previous.ClosesTemplateDeclaration && State.ParenLevel == 0)))
1056      return true;
1057
1058    if (Current.Type == TT_StartOfName && Line.MightBeFunctionDecl &&
1059        State.Stack.back().BreakBeforeParameter && State.ParenLevel == 0)
1060      return true;
1061    return false;
1062  }
1063
1064  // Returns the total number of columns required for the remaining tokens.
1065  unsigned getRemainingLength(const LineState &State) {
1066    if (State.NextToken && State.NextToken->Previous)
1067      return Line.Last->TotalLength - State.NextToken->Previous->TotalLength;
1068    return 0;
1069  }
1070
1071  FormatStyle Style;
1072  SourceManager &SourceMgr;
1073  const AnnotatedLine &Line;
1074  const unsigned FirstIndent;
1075  const FormatToken *RootToken;
1076  WhitespaceManager &Whitespaces;
1077
1078  llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
1079  QueueType Queue;
1080  // Increasing count of \c StateNode items we have created. This is used
1081  // to create a deterministic order independent of the container.
1082  unsigned Count;
1083};
1084
1085class FormatTokenLexer {
1086public:
1087  FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr)
1088      : FormatTok(NULL), GreaterStashed(false), TrailingWhitespace(0), Lex(Lex),
1089        SourceMgr(SourceMgr), IdentTable(Lex.getLangOpts()) {
1090    Lex.SetKeepWhitespaceMode(true);
1091  }
1092
1093  ArrayRef<FormatToken *> lex() {
1094    assert(Tokens.empty());
1095    do {
1096      Tokens.push_back(getNextToken());
1097    } while (Tokens.back()->Tok.isNot(tok::eof));
1098    return Tokens;
1099  }
1100
1101  IdentifierTable &getIdentTable() { return IdentTable; }
1102
1103private:
1104  FormatToken *getNextToken() {
1105    if (GreaterStashed) {
1106      // Create a synthesized second '>' token.
1107      Token Greater = FormatTok->Tok;
1108      FormatTok = new (Allocator.Allocate()) FormatToken;
1109      FormatTok->Tok = Greater;
1110      SourceLocation GreaterLocation =
1111          FormatTok->Tok.getLocation().getLocWithOffset(1);
1112      FormatTok->WhitespaceRange =
1113          SourceRange(GreaterLocation, GreaterLocation);
1114      FormatTok->TokenLength = 1;
1115      GreaterStashed = false;
1116      return FormatTok;
1117    }
1118
1119    FormatTok = new (Allocator.Allocate()) FormatToken;
1120    Lex.LexFromRawLexer(FormatTok->Tok);
1121    StringRef Text = rawTokenText(FormatTok->Tok);
1122    SourceLocation WhitespaceStart =
1123        FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
1124    if (SourceMgr.getFileOffset(WhitespaceStart) == 0)
1125      FormatTok->IsFirst = true;
1126
1127    // Consume and record whitespace until we find a significant token.
1128    unsigned WhitespaceLength = TrailingWhitespace;
1129    while (FormatTok->Tok.is(tok::unknown)) {
1130      unsigned Newlines = Text.count('\n');
1131      if (Newlines > 0)
1132        FormatTok->LastNewlineOffset = WhitespaceLength + Text.rfind('\n') + 1;
1133      unsigned EscapedNewlines = Text.count("\\\n");
1134      FormatTok->NewlinesBefore += Newlines;
1135      FormatTok->HasUnescapedNewline |= EscapedNewlines != Newlines;
1136      WhitespaceLength += FormatTok->Tok.getLength();
1137
1138      if (FormatTok->Tok.is(tok::eof)) {
1139        FormatTok->WhitespaceRange =
1140            SourceRange(WhitespaceStart,
1141                        WhitespaceStart.getLocWithOffset(WhitespaceLength));
1142        return FormatTok;
1143      }
1144      Lex.LexFromRawLexer(FormatTok->Tok);
1145      Text = rawTokenText(FormatTok->Tok);
1146    }
1147
1148    // Now FormatTok is the next non-whitespace token.
1149    FormatTok->TokenLength = Text.size();
1150
1151    TrailingWhitespace = 0;
1152    if (FormatTok->Tok.is(tok::comment)) {
1153      TrailingWhitespace = Text.size() - Text.rtrim().size();
1154      FormatTok->TokenLength -= TrailingWhitespace;
1155    }
1156
1157    // In case the token starts with escaped newlines, we want to
1158    // take them into account as whitespace - this pattern is quite frequent
1159    // in macro definitions.
1160    // FIXME: What do we want to do with other escaped spaces, and escaped
1161    // spaces or newlines in the middle of tokens?
1162    // FIXME: Add a more explicit test.
1163    unsigned i = 0;
1164    while (i + 1 < Text.size() && Text[i] == '\\' && Text[i + 1] == '\n') {
1165      // FIXME: ++FormatTok->NewlinesBefore is missing...
1166      WhitespaceLength += 2;
1167      FormatTok->TokenLength -= 2;
1168      i += 2;
1169    }
1170
1171    if (FormatTok->Tok.is(tok::raw_identifier)) {
1172      IdentifierInfo &Info = IdentTable.get(Text);
1173      FormatTok->Tok.setIdentifierInfo(&Info);
1174      FormatTok->Tok.setKind(Info.getTokenID());
1175    }
1176
1177    if (FormatTok->Tok.is(tok::greatergreater)) {
1178      FormatTok->Tok.setKind(tok::greater);
1179      FormatTok->TokenLength = 1;
1180      GreaterStashed = true;
1181    }
1182
1183    FormatTok->WhitespaceRange = SourceRange(
1184        WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1185    FormatTok->TokenText = StringRef(
1186        SourceMgr.getCharacterData(FormatTok->getStartOfNonWhitespace()),
1187        FormatTok->TokenLength);
1188    return FormatTok;
1189  }
1190
1191  FormatToken *FormatTok;
1192  bool GreaterStashed;
1193  unsigned TrailingWhitespace;
1194  Lexer &Lex;
1195  SourceManager &SourceMgr;
1196  IdentifierTable IdentTable;
1197  llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
1198  SmallVector<FormatToken *, 16> Tokens;
1199
1200  /// Returns the text of \c FormatTok.
1201  StringRef rawTokenText(Token &Tok) {
1202    return StringRef(SourceMgr.getCharacterData(Tok.getLocation()),
1203                     Tok.getLength());
1204  }
1205};
1206
1207class Formatter : public UnwrappedLineConsumer {
1208public:
1209  Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
1210            const std::vector<CharSourceRange> &Ranges)
1211      : Style(Style), Lex(Lex), SourceMgr(SourceMgr),
1212        Whitespaces(SourceMgr, Style), Ranges(Ranges) {}
1213
1214  virtual ~Formatter() {}
1215
1216  tooling::Replacements format() {
1217    FormatTokenLexer Tokens(Lex, SourceMgr);
1218
1219    UnwrappedLineParser Parser(Style, Tokens.lex(), *this);
1220    bool StructuralError = Parser.parse();
1221    TokenAnnotator Annotator(Style, SourceMgr, Lex,
1222                             Tokens.getIdentTable().get("in"));
1223    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1224      Annotator.annotate(AnnotatedLines[i]);
1225    }
1226    deriveLocalStyle();
1227    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1228      Annotator.calculateFormattingInformation(AnnotatedLines[i]);
1229    }
1230
1231    // Adapt level to the next line if this is a comment.
1232    // FIXME: Can/should this be done in the UnwrappedLineParser?
1233    const AnnotatedLine *NextNoneCommentLine = NULL;
1234    for (unsigned i = AnnotatedLines.size() - 1; i > 0; --i) {
1235      if (NextNoneCommentLine && AnnotatedLines[i].First->is(tok::comment) &&
1236          !AnnotatedLines[i].First->Next)
1237        AnnotatedLines[i].Level = NextNoneCommentLine->Level;
1238      else
1239        NextNoneCommentLine =
1240            AnnotatedLines[i].First->isNot(tok::r_brace) ? &AnnotatedLines[i]
1241                                                         : NULL;
1242    }
1243
1244    std::vector<int> IndentForLevel;
1245    bool PreviousLineWasTouched = false;
1246    const FormatToken *PreviousLineLastToken = 0;
1247    bool FormatPPDirective = false;
1248    for (std::vector<AnnotatedLine>::iterator I = AnnotatedLines.begin(),
1249                                              E = AnnotatedLines.end();
1250         I != E; ++I) {
1251      const AnnotatedLine &TheLine = *I;
1252      const FormatToken *FirstTok = TheLine.First;
1253      int Offset = getIndentOffset(*TheLine.First);
1254
1255      // Check whether this line is part of a formatted preprocessor directive.
1256      if (FirstTok->HasUnescapedNewline)
1257        FormatPPDirective = false;
1258      if (!FormatPPDirective && TheLine.InPPDirective &&
1259          (touchesLine(TheLine) || touchesPPDirective(I + 1, E)))
1260        FormatPPDirective = true;
1261
1262      // Determine indent and try to merge multiple unwrapped lines.
1263      while (IndentForLevel.size() <= TheLine.Level)
1264        IndentForLevel.push_back(-1);
1265      IndentForLevel.resize(TheLine.Level + 1);
1266      unsigned Indent = getIndent(IndentForLevel, TheLine.Level);
1267      if (static_cast<int>(Indent) + Offset >= 0)
1268        Indent += Offset;
1269      tryFitMultipleLinesInOne(Indent, I, E);
1270
1271      bool WasMoved = PreviousLineWasTouched && FirstTok->NewlinesBefore == 0;
1272      if (TheLine.First->is(tok::eof)) {
1273        if (PreviousLineWasTouched) {
1274          unsigned NewLines = std::min(FirstTok->NewlinesBefore, 1u);
1275          Whitespaces.replaceWhitespace(*TheLine.First, NewLines, /*Indent*/ 0,
1276                                        /*TargetColumn*/ 0);
1277        }
1278      } else if (TheLine.Type != LT_Invalid &&
1279                 (WasMoved || FormatPPDirective || touchesLine(TheLine))) {
1280        unsigned LevelIndent = getIndent(IndentForLevel, TheLine.Level);
1281        if (FirstTok->WhitespaceRange.isValid() &&
1282            // Insert a break even if there is a structural error in case where
1283            // we break apart a line consisting of multiple unwrapped lines.
1284            (FirstTok->NewlinesBefore == 0 || !StructuralError)) {
1285          formatFirstToken(*TheLine.First, PreviousLineLastToken, Indent,
1286                           TheLine.InPPDirective);
1287        } else {
1288          Indent = LevelIndent =
1289              SourceMgr.getSpellingColumnNumber(FirstTok->Tok.getLocation()) -
1290              1;
1291        }
1292        UnwrappedLineFormatter Formatter(Style, SourceMgr, TheLine, Indent,
1293                                         TheLine.First, Whitespaces);
1294        Formatter.format(I + 1 != E ? &*(I + 1) : NULL);
1295        IndentForLevel[TheLine.Level] = LevelIndent;
1296        PreviousLineWasTouched = true;
1297      } else {
1298        // Format the first token if necessary, and notify the WhitespaceManager
1299        // about the unchanged whitespace.
1300        for (const FormatToken *Tok = TheLine.First; Tok != NULL;
1301             Tok = Tok->Next) {
1302          if (Tok == TheLine.First &&
1303              (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
1304            unsigned LevelIndent =
1305                SourceMgr.getSpellingColumnNumber(Tok->Tok.getLocation()) - 1;
1306            // Remove trailing whitespace of the previous line if it was
1307            // touched.
1308            if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine)) {
1309              formatFirstToken(*Tok, PreviousLineLastToken, LevelIndent,
1310                               TheLine.InPPDirective);
1311            } else {
1312              Whitespaces.addUntouchableToken(*Tok, TheLine.InPPDirective);
1313            }
1314
1315            if (static_cast<int>(LevelIndent) - Offset >= 0)
1316              LevelIndent -= Offset;
1317            if (Tok->isNot(tok::comment))
1318              IndentForLevel[TheLine.Level] = LevelIndent;
1319          } else {
1320            Whitespaces.addUntouchableToken(*Tok, TheLine.InPPDirective);
1321          }
1322        }
1323        // If we did not reformat this unwrapped line, the column at the end of
1324        // the last token is unchanged - thus, we can calculate the end of the
1325        // last token.
1326        PreviousLineWasTouched = false;
1327      }
1328      PreviousLineLastToken = I->Last;
1329    }
1330    return Whitespaces.generateReplacements();
1331  }
1332
1333private:
1334  void deriveLocalStyle() {
1335    unsigned CountBoundToVariable = 0;
1336    unsigned CountBoundToType = 0;
1337    bool HasCpp03IncompatibleFormat = false;
1338    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1339      if (!AnnotatedLines[i].First->Next)
1340        continue;
1341      FormatToken *Tok = AnnotatedLines[i].First->Next;
1342      while (Tok->Next) {
1343        if (Tok->Type == TT_PointerOrReference) {
1344          bool SpacesBefore =
1345              Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1346          bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
1347                             Tok->Next->WhitespaceRange.getEnd();
1348          if (SpacesBefore && !SpacesAfter)
1349            ++CountBoundToVariable;
1350          else if (!SpacesBefore && SpacesAfter)
1351            ++CountBoundToType;
1352        }
1353
1354        if (Tok->Type == TT_TemplateCloser &&
1355            Tok->Previous->Type == TT_TemplateCloser &&
1356            Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd())
1357          HasCpp03IncompatibleFormat = true;
1358        Tok = Tok->Next;
1359      }
1360    }
1361    if (Style.DerivePointerBinding) {
1362      if (CountBoundToType > CountBoundToVariable)
1363        Style.PointerBindsToType = true;
1364      else if (CountBoundToType < CountBoundToVariable)
1365        Style.PointerBindsToType = false;
1366    }
1367    if (Style.Standard == FormatStyle::LS_Auto) {
1368      Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
1369                                                  : FormatStyle::LS_Cpp03;
1370    }
1371  }
1372
1373  /// \brief Get the indent of \p Level from \p IndentForLevel.
1374  ///
1375  /// \p IndentForLevel must contain the indent for the level \c l
1376  /// at \p IndentForLevel[l], or a value < 0 if the indent for
1377  /// that level is unknown.
1378  unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
1379    if (IndentForLevel[Level] != -1)
1380      return IndentForLevel[Level];
1381    if (Level == 0)
1382      return 0;
1383    return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
1384  }
1385
1386  /// \brief Get the offset of the line relatively to the level.
1387  ///
1388  /// For example, 'public:' labels in classes are offset by 1 or 2
1389  /// characters to the left from their level.
1390  int getIndentOffset(const FormatToken &RootToken) {
1391    if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
1392      return Style.AccessModifierOffset;
1393    return 0;
1394  }
1395
1396  /// \brief Tries to merge lines into one.
1397  ///
1398  /// This will change \c Line and \c AnnotatedLine to contain the merged line,
1399  /// if possible; note that \c I will be incremented when lines are merged.
1400  void tryFitMultipleLinesInOne(unsigned Indent,
1401                                std::vector<AnnotatedLine>::iterator &I,
1402                                std::vector<AnnotatedLine>::iterator E) {
1403    // We can never merge stuff if there are trailing line comments.
1404    if (I->Last->Type == TT_LineComment)
1405      return;
1406
1407    unsigned Limit = Style.ColumnLimit - Indent;
1408    // If we already exceed the column limit, we set 'Limit' to 0. The different
1409    // tryMerge..() functions can then decide whether to still do merging.
1410    Limit = I->Last->TotalLength > Limit ? 0 : Limit - I->Last->TotalLength;
1411
1412    if (I + 1 == E || (I + 1)->Type == LT_Invalid)
1413      return;
1414
1415    if (I->Last->is(tok::l_brace)) {
1416      tryMergeSimpleBlock(I, E, Limit);
1417    } else if (Style.AllowShortIfStatementsOnASingleLine &&
1418               I->First->is(tok::kw_if)) {
1419      tryMergeSimpleControlStatement(I, E, Limit);
1420    } else if (Style.AllowShortLoopsOnASingleLine &&
1421               I->First->isOneOf(tok::kw_for, tok::kw_while)) {
1422      tryMergeSimpleControlStatement(I, E, Limit);
1423    } else if (I->InPPDirective &&
1424               (I->First->HasUnescapedNewline || I->First->IsFirst)) {
1425      tryMergeSimplePPDirective(I, E, Limit);
1426    }
1427  }
1428
1429  void tryMergeSimplePPDirective(std::vector<AnnotatedLine>::iterator &I,
1430                                 std::vector<AnnotatedLine>::iterator E,
1431                                 unsigned Limit) {
1432    if (Limit == 0)
1433      return;
1434    AnnotatedLine &Line = *I;
1435    if (!(I + 1)->InPPDirective || (I + 1)->First->HasUnescapedNewline)
1436      return;
1437    if (I + 2 != E && (I + 2)->InPPDirective &&
1438        !(I + 2)->First->HasUnescapedNewline)
1439      return;
1440    if (1 + (I + 1)->Last->TotalLength > Limit)
1441      return;
1442    join(Line, *(++I));
1443  }
1444
1445  void tryMergeSimpleControlStatement(std::vector<AnnotatedLine>::iterator &I,
1446                                      std::vector<AnnotatedLine>::iterator E,
1447                                      unsigned Limit) {
1448    if (Limit == 0)
1449      return;
1450    if ((I + 1)->InPPDirective != I->InPPDirective ||
1451        ((I + 1)->InPPDirective && (I + 1)->First->HasUnescapedNewline))
1452      return;
1453    AnnotatedLine &Line = *I;
1454    if (Line.Last->isNot(tok::r_paren))
1455      return;
1456    if (1 + (I + 1)->Last->TotalLength > Limit)
1457      return;
1458    if ((I + 1)->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
1459                                tok::kw_while) ||
1460        (I + 1)->First->Type == TT_LineComment)
1461      return;
1462    // Only inline simple if's (no nested if or else).
1463    if (I + 2 != E && Line.First->is(tok::kw_if) &&
1464        (I + 2)->First->is(tok::kw_else))
1465      return;
1466    join(Line, *(++I));
1467  }
1468
1469  void tryMergeSimpleBlock(std::vector<AnnotatedLine>::iterator &I,
1470                           std::vector<AnnotatedLine>::iterator E,
1471                           unsigned Limit) {
1472    // No merging if the brace already is on the next line.
1473    if (Style.BreakBeforeBraces != FormatStyle::BS_Attach)
1474      return;
1475
1476    // First, check that the current line allows merging. This is the case if
1477    // we're not in a control flow statement and the last token is an opening
1478    // brace.
1479    AnnotatedLine &Line = *I;
1480    if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace,
1481                            tok::kw_else, tok::kw_try, tok::kw_catch,
1482                            tok::kw_for,
1483                            // This gets rid of all ObjC @ keywords and methods.
1484                            tok::at, tok::minus, tok::plus))
1485      return;
1486
1487    FormatToken *Tok = (I + 1)->First;
1488    if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
1489        (Tok->getNextNoneComment() == NULL ||
1490         Tok->getNextNoneComment()->is(tok::semi))) {
1491      // We merge empty blocks even if the line exceeds the column limit.
1492      Tok->SpacesRequiredBefore = 0;
1493      Tok->CanBreakBefore = true;
1494      join(Line, *(I + 1));
1495      I += 1;
1496    } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace)) {
1497      // Check that we still have three lines and they fit into the limit.
1498      if (I + 2 == E || (I + 2)->Type == LT_Invalid ||
1499          !nextTwoLinesFitInto(I, Limit))
1500        return;
1501
1502      // Second, check that the next line does not contain any braces - if it
1503      // does, readability declines when putting it into a single line.
1504      if ((I + 1)->Last->Type == TT_LineComment || Tok->MustBreakBefore)
1505        return;
1506      do {
1507        if (Tok->isOneOf(tok::l_brace, tok::r_brace))
1508          return;
1509        Tok = Tok->Next;
1510      } while (Tok != NULL);
1511
1512      // Last, check that the third line contains a single closing brace.
1513      Tok = (I + 2)->First;
1514      if (Tok->getNextNoneComment() != NULL || Tok->isNot(tok::r_brace) ||
1515          Tok->MustBreakBefore)
1516        return;
1517
1518      join(Line, *(I + 1));
1519      join(Line, *(I + 2));
1520      I += 2;
1521    }
1522  }
1523
1524  bool nextTwoLinesFitInto(std::vector<AnnotatedLine>::iterator I,
1525                           unsigned Limit) {
1526    return 1 + (I + 1)->Last->TotalLength + 1 + (I + 2)->Last->TotalLength <=
1527           Limit;
1528  }
1529
1530  void join(AnnotatedLine &A, const AnnotatedLine &B) {
1531    assert(!A.Last->Next);
1532    assert(!B.First->Previous);
1533    A.Last->Next = B.First;
1534    B.First->Previous = A.Last;
1535    unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
1536    for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
1537      Tok->TotalLength += LengthA;
1538      A.Last = Tok;
1539    }
1540  }
1541
1542  bool touchesRanges(const CharSourceRange &Range) {
1543    for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1544      if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),
1545                                               Ranges[i].getBegin()) &&
1546          !SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(),
1547                                               Range.getBegin()))
1548        return true;
1549    }
1550    return false;
1551  }
1552
1553  bool touchesLine(const AnnotatedLine &TheLine) {
1554    const FormatToken *First = TheLine.First;
1555    const FormatToken *Last = TheLine.Last;
1556    CharSourceRange LineRange = CharSourceRange::getCharRange(
1557        First->WhitespaceRange.getBegin().getLocWithOffset(
1558            First->LastNewlineOffset),
1559        Last->Tok.getLocation().getLocWithOffset(Last->TokenLength - 1));
1560    return touchesRanges(LineRange);
1561  }
1562
1563  bool touchesPPDirective(std::vector<AnnotatedLine>::iterator I,
1564                          std::vector<AnnotatedLine>::iterator E) {
1565    for (; I != E; ++I) {
1566      if (I->First->HasUnescapedNewline)
1567        return false;
1568      if (touchesLine(*I))
1569        return true;
1570    }
1571    return false;
1572  }
1573
1574  bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) {
1575    const FormatToken *First = TheLine.First;
1576    CharSourceRange LineRange = CharSourceRange::getCharRange(
1577        First->WhitespaceRange.getBegin(),
1578        First->WhitespaceRange.getBegin().getLocWithOffset(
1579            First->LastNewlineOffset));
1580    return touchesRanges(LineRange);
1581  }
1582
1583  virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
1584    AnnotatedLines.push_back(AnnotatedLine(TheLine));
1585  }
1586
1587  /// \brief Add a new line and the required indent before the first Token
1588  /// of the \c UnwrappedLine if there was no structural parsing error.
1589  /// Returns the indent level of the \c UnwrappedLine.
1590  void formatFirstToken(const FormatToken &RootToken,
1591                        const FormatToken *PreviousToken, unsigned Indent,
1592                        bool InPPDirective) {
1593    unsigned Newlines =
1594        std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
1595    if (Newlines == 0 && !RootToken.IsFirst)
1596      Newlines = 1;
1597
1598    // Insert extra new line before access specifiers.
1599    if (PreviousToken && PreviousToken->isOneOf(tok::semi, tok::r_brace) &&
1600        RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
1601      ++Newlines;
1602
1603    Whitespaces.replaceWhitespace(
1604        RootToken, Newlines, Indent, Indent,
1605        InPPDirective && !RootToken.HasUnescapedNewline);
1606  }
1607
1608  FormatStyle Style;
1609  Lexer &Lex;
1610  SourceManager &SourceMgr;
1611  WhitespaceManager Whitespaces;
1612  std::vector<CharSourceRange> Ranges;
1613  std::vector<AnnotatedLine> AnnotatedLines;
1614};
1615
1616tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1617                               SourceManager &SourceMgr,
1618                               std::vector<CharSourceRange> Ranges) {
1619  Formatter formatter(Style, Lex, SourceMgr, Ranges);
1620  return formatter.format();
1621}
1622
1623tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1624                               std::vector<tooling::Range> Ranges,
1625                               StringRef FileName) {
1626  FileManager Files((FileSystemOptions()));
1627  DiagnosticsEngine Diagnostics(
1628      IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1629      new DiagnosticOptions);
1630  SourceManager SourceMgr(Diagnostics, Files);
1631  llvm::MemoryBuffer *Buf = llvm::MemoryBuffer::getMemBuffer(Code, FileName);
1632  const clang::FileEntry *Entry =
1633      Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
1634  SourceMgr.overrideFileContents(Entry, Buf);
1635  FileID ID =
1636      SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
1637  Lexer Lex(ID, SourceMgr.getBuffer(ID), SourceMgr, getFormattingLangOpts());
1638  SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1639  std::vector<CharSourceRange> CharRanges;
1640  for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1641    SourceLocation Start = StartOfFile.getLocWithOffset(Ranges[i].getOffset());
1642    SourceLocation End = Start.getLocWithOffset(Ranges[i].getLength());
1643    CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1644  }
1645  return reformat(Style, Lex, SourceMgr, CharRanges);
1646}
1647
1648LangOptions getFormattingLangOpts() {
1649  LangOptions LangOpts;
1650  LangOpts.CPlusPlus = 1;
1651  LangOpts.CPlusPlus11 = 1;
1652  LangOpts.LineComment = 1;
1653  LangOpts.Bool = 1;
1654  LangOpts.ObjC1 = 1;
1655  LangOpts.ObjC2 = 1;
1656  return LangOpts;
1657}
1658
1659} // namespace format
1660} // namespace clang
1661