Format.cpp revision 249261
1249261Sdim//===--- Format.cpp - Format C++ code -------------------------------------===//
2249261Sdim//
3249261Sdim//                     The LLVM Compiler Infrastructure
4249261Sdim//
5249261Sdim// This file is distributed under the University of Illinois Open Source
6249261Sdim// License. See LICENSE.TXT for details.
7249261Sdim//
8249261Sdim//===----------------------------------------------------------------------===//
9249261Sdim///
10249261Sdim/// \file
11249261Sdim/// \brief This file implements functions declared in Format.h. This will be
12249261Sdim/// split into separate files as we go.
13249261Sdim///
14249261Sdim//===----------------------------------------------------------------------===//
15249261Sdim
16249261Sdim#define DEBUG_TYPE "format-formatter"
17249261Sdim
18249261Sdim#include "TokenAnnotator.h"
19249261Sdim#include "UnwrappedLineParser.h"
20249261Sdim#include "clang/Basic/Diagnostic.h"
21249261Sdim#include "clang/Basic/OperatorPrecedence.h"
22249261Sdim#include "clang/Basic/SourceManager.h"
23249261Sdim#include "clang/Format/Format.h"
24249261Sdim#include "clang/Frontend/TextDiagnosticPrinter.h"
25249261Sdim#include "clang/Lex/Lexer.h"
26249261Sdim#include "llvm/ADT/STLExtras.h"
27249261Sdim#include "llvm/Support/Allocator.h"
28249261Sdim#include "llvm/Support/Debug.h"
29249261Sdim#include <queue>
30249261Sdim#include <string>
31249261Sdim
32249261Sdimnamespace clang {
33249261Sdimnamespace format {
34249261Sdim
35249261SdimFormatStyle getLLVMStyle() {
36249261Sdim  FormatStyle LLVMStyle;
37249261Sdim  LLVMStyle.ColumnLimit = 80;
38249261Sdim  LLVMStyle.MaxEmptyLinesToKeep = 1;
39249261Sdim  LLVMStyle.PointerBindsToType = false;
40249261Sdim  LLVMStyle.DerivePointerBinding = false;
41249261Sdim  LLVMStyle.AccessModifierOffset = -2;
42249261Sdim  LLVMStyle.Standard = FormatStyle::LS_Cpp03;
43249261Sdim  LLVMStyle.IndentCaseLabels = false;
44249261Sdim  LLVMStyle.SpacesBeforeTrailingComments = 1;
45249261Sdim  LLVMStyle.BinPackParameters = true;
46249261Sdim  LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
47249261Sdim  LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
48249261Sdim  LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
49249261Sdim  LLVMStyle.ObjCSpaceBeforeProtocolList = true;
50249261Sdim  LLVMStyle.PenaltyExcessCharacter = 1000000;
51249261Sdim  LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 5;
52249261Sdim  return LLVMStyle;
53249261Sdim}
54249261Sdim
55249261SdimFormatStyle getGoogleStyle() {
56249261Sdim  FormatStyle GoogleStyle;
57249261Sdim  GoogleStyle.ColumnLimit = 80;
58249261Sdim  GoogleStyle.MaxEmptyLinesToKeep = 1;
59249261Sdim  GoogleStyle.PointerBindsToType = true;
60249261Sdim  GoogleStyle.DerivePointerBinding = true;
61249261Sdim  GoogleStyle.AccessModifierOffset = -1;
62249261Sdim  GoogleStyle.Standard = FormatStyle::LS_Auto;
63249261Sdim  GoogleStyle.IndentCaseLabels = true;
64249261Sdim  GoogleStyle.SpacesBeforeTrailingComments = 2;
65249261Sdim  GoogleStyle.BinPackParameters = true;
66249261Sdim  GoogleStyle.AllowAllParametersOfDeclarationOnNextLine = true;
67249261Sdim  GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
68249261Sdim  GoogleStyle.AllowShortIfStatementsOnASingleLine = false;
69249261Sdim  GoogleStyle.ObjCSpaceBeforeProtocolList = false;
70249261Sdim  GoogleStyle.PenaltyExcessCharacter = 1000000;
71249261Sdim  GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 100;
72249261Sdim  return GoogleStyle;
73249261Sdim}
74249261Sdim
75249261SdimFormatStyle getChromiumStyle() {
76249261Sdim  FormatStyle ChromiumStyle = getGoogleStyle();
77249261Sdim  ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
78249261Sdim  ChromiumStyle.BinPackParameters = false;
79249261Sdim  ChromiumStyle.Standard = FormatStyle::LS_Cpp03;
80249261Sdim  ChromiumStyle.DerivePointerBinding = false;
81249261Sdim  return ChromiumStyle;
82249261Sdim}
83249261Sdim
84249261Sdimstatic bool isTrailingComment(const AnnotatedToken &Tok) {
85249261Sdim  return Tok.is(tok::comment) &&
86249261Sdim         (Tok.Children.empty() || Tok.Children[0].MustBreakBefore);
87249261Sdim}
88249261Sdim
89249261Sdimstatic bool isComparison(const AnnotatedToken &Tok) {
90249261Sdim  prec::Level Precedence = getPrecedence(Tok);
91249261Sdim  return Tok.Type == TT_BinaryOperator &&
92249261Sdim         (Precedence == prec::Equality || Precedence == prec::Relational);
93249261Sdim}
94249261Sdim
95249261Sdim// Returns the length of everything up to the first possible line break after
96249261Sdim// the ), ], } or > matching \c Tok.
97249261Sdimstatic unsigned getLengthToMatchingParen(const AnnotatedToken &Tok) {
98249261Sdim  if (Tok.MatchingParen == NULL)
99249261Sdim    return 0;
100249261Sdim  AnnotatedToken *End = Tok.MatchingParen;
101249261Sdim  while (!End->Children.empty() && !End->Children[0].CanBreakBefore) {
102249261Sdim    End = &End->Children[0];
103249261Sdim  }
104249261Sdim  return End->TotalLength - Tok.TotalLength + 1;
105249261Sdim}
106249261Sdim
107249261Sdimstatic size_t
108249261SdimcalculateColumnLimit(const FormatStyle &Style, bool InPPDirective) {
109249261Sdim  // In preprocessor directives reserve two chars for trailing " \"
110249261Sdim  return Style.ColumnLimit - (InPPDirective ? 2 : 0);
111249261Sdim}
112249261Sdim
113249261Sdim/// \brief Manages the whitespaces around tokens and their replacements.
114249261Sdim///
115249261Sdim/// This includes special handling for certain constructs, e.g. the alignment of
116249261Sdim/// trailing line comments.
117249261Sdimclass WhitespaceManager {
118249261Sdimpublic:
119249261Sdim  WhitespaceManager(SourceManager &SourceMgr, const FormatStyle &Style)
120249261Sdim      : SourceMgr(SourceMgr), Style(Style) {}
121249261Sdim
122249261Sdim  /// \brief Replaces the whitespace in front of \p Tok. Only call once for
123249261Sdim  /// each \c AnnotatedToken.
124249261Sdim  void replaceWhitespace(const AnnotatedToken &Tok, unsigned NewLines,
125249261Sdim                         unsigned Spaces, unsigned WhitespaceStartColumn) {
126249261Sdim    // 2+ newlines mean an empty line separating logic scopes.
127249261Sdim    if (NewLines >= 2)
128249261Sdim      alignComments();
129249261Sdim
130249261Sdim    SourceLocation TokenLoc = Tok.FormatTok.Tok.getLocation();
131249261Sdim    bool LineExceedsColumnLimit = Spaces + WhitespaceStartColumn +
132249261Sdim                                  Tok.FormatTok.TokenLength > Style.ColumnLimit;
133249261Sdim
134249261Sdim    // Align line comments if they are trailing or if they continue other
135249261Sdim    // trailing comments.
136249261Sdim    if (isTrailingComment(Tok)) {
137249261Sdim      // Remove the comment's trailing whitespace.
138249261Sdim      if (Tok.FormatTok.Tok.getLength() != Tok.FormatTok.TokenLength)
139249261Sdim        Replaces.insert(tooling::Replacement(
140249261Sdim            SourceMgr, TokenLoc.getLocWithOffset(Tok.FormatTok.TokenLength),
141249261Sdim            Tok.FormatTok.Tok.getLength() - Tok.FormatTok.TokenLength, ""));
142249261Sdim
143249261Sdim      // Align comment with other comments.
144249261Sdim      if ((Tok.Parent != NULL || !Comments.empty()) &&
145249261Sdim          !LineExceedsColumnLimit) {
146249261Sdim        StoredComment Comment;
147249261Sdim        Comment.Tok = Tok.FormatTok;
148249261Sdim        Comment.Spaces = Spaces;
149249261Sdim        Comment.NewLines = NewLines;
150249261Sdim        Comment.MinColumn =
151249261Sdim            NewLines > 0 ? Spaces : WhitespaceStartColumn + Spaces;
152249261Sdim        Comment.MaxColumn = Style.ColumnLimit - Tok.FormatTok.TokenLength;
153249261Sdim        Comment.Untouchable = false;
154249261Sdim        Comments.push_back(Comment);
155249261Sdim        return;
156249261Sdim      }
157249261Sdim    }
158249261Sdim
159249261Sdim    // If this line does not have a trailing comment, align the stored comments.
160249261Sdim    if (Tok.Children.empty() && !isTrailingComment(Tok))
161249261Sdim      alignComments();
162249261Sdim
163249261Sdim    if (Tok.Type == TT_BlockComment) {
164249261Sdim      indentBlockComment(Tok, Spaces, WhitespaceStartColumn, NewLines, false);
165249261Sdim    } else if (Tok.Type == TT_LineComment && LineExceedsColumnLimit) {
166249261Sdim      StringRef Line(SourceMgr.getCharacterData(TokenLoc),
167249261Sdim                     Tok.FormatTok.TokenLength);
168249261Sdim      int StartColumn = Spaces + (NewLines == 0 ? WhitespaceStartColumn : 0);
169249261Sdim      StringRef Prefix = getLineCommentPrefix(Line);
170249261Sdim      std::string NewPrefix = std::string(StartColumn, ' ') + Prefix.str();
171249261Sdim      splitLineInComment(Tok.FormatTok, Line.substr(Prefix.size()),
172249261Sdim                         StartColumn + Prefix.size(), NewPrefix,
173249261Sdim                         /*InPPDirective=*/ false,
174249261Sdim                         /*CommentHasMoreLines=*/ false);
175249261Sdim    }
176249261Sdim
177249261Sdim    storeReplacement(Tok.FormatTok, getNewLineText(NewLines, Spaces));
178249261Sdim  }
179249261Sdim
180249261Sdim  /// \brief Like \c replaceWhitespace, but additionally adds right-aligned
181249261Sdim  /// backslashes to escape newlines inside a preprocessor directive.
182249261Sdim  ///
183249261Sdim  /// This function and \c replaceWhitespace have the same behavior if
184249261Sdim  /// \c Newlines == 0.
185249261Sdim  void replacePPWhitespace(const AnnotatedToken &Tok, unsigned NewLines,
186249261Sdim                           unsigned Spaces, unsigned WhitespaceStartColumn) {
187249261Sdim    if (Tok.Type == TT_BlockComment)
188249261Sdim      indentBlockComment(Tok, Spaces, WhitespaceStartColumn, NewLines, true);
189249261Sdim
190249261Sdim    storeReplacement(Tok.FormatTok,
191249261Sdim                     getNewLineText(NewLines, Spaces, WhitespaceStartColumn));
192249261Sdim  }
193249261Sdim
194249261Sdim  /// \brief Inserts a line break into the middle of a token.
195249261Sdim  ///
196249261Sdim  /// Will break at \p Offset inside \p Tok, putting \p Prefix before the line
197249261Sdim  /// break and \p Postfix before the rest of the token starts in the next line.
198249261Sdim  ///
199249261Sdim  /// \p InPPDirective, \p Spaces, \p WhitespaceStartColumn and \p Style are
200249261Sdim  /// used to generate the correct line break.
201249261Sdim  void breakToken(const FormatToken &Tok, unsigned Offset,
202249261Sdim                  unsigned ReplaceChars, StringRef Prefix, StringRef Postfix,
203249261Sdim                  bool InPPDirective, unsigned Spaces,
204249261Sdim                  unsigned WhitespaceStartColumn) {
205249261Sdim    std::string NewLineText;
206249261Sdim    if (!InPPDirective)
207249261Sdim      NewLineText = getNewLineText(1, Spaces);
208249261Sdim    else
209249261Sdim      NewLineText = getNewLineText(1, Spaces, WhitespaceStartColumn);
210249261Sdim    std::string ReplacementText = (Prefix + NewLineText + Postfix).str();
211249261Sdim    SourceLocation Location = Tok.Tok.getLocation().getLocWithOffset(Offset);
212249261Sdim    Replaces.insert(tooling::Replacement(SourceMgr, Location, ReplaceChars,
213249261Sdim                                         ReplacementText));
214249261Sdim  }
215249261Sdim
216249261Sdim  /// \brief Returns all the \c Replacements created during formatting.
217249261Sdim  const tooling::Replacements &generateReplacements() {
218249261Sdim    alignComments();
219249261Sdim    return Replaces;
220249261Sdim  }
221249261Sdim
222249261Sdim  void addUntouchableComment(unsigned Column) {
223249261Sdim    StoredComment Comment;
224249261Sdim    Comment.MinColumn = Column;
225249261Sdim    Comment.MaxColumn = Column;
226249261Sdim    Comment.Untouchable = true;
227249261Sdim    Comments.push_back(Comment);
228249261Sdim  }
229249261Sdim
230249261Sdimprivate:
231249261Sdim  static StringRef getLineCommentPrefix(StringRef Comment) {
232249261Sdim    const char *KnownPrefixes[] = { "/// ", "///", "// ", "//" };
233249261Sdim    for (size_t i = 0; i < llvm::array_lengthof(KnownPrefixes); ++i)
234249261Sdim      if (Comment.startswith(KnownPrefixes[i]))
235249261Sdim        return KnownPrefixes[i];
236249261Sdim    return "";
237249261Sdim  }
238249261Sdim
239249261Sdim  /// \brief Finds a common prefix of lines of a block comment to properly
240249261Sdim  /// indent (and possibly decorate with '*'s) added lines.
241249261Sdim  ///
242249261Sdim  /// The first line is ignored (it's special and starts with /*). The number of
243249261Sdim  /// lines should be more than one.
244249261Sdim  static StringRef findCommentLinesPrefix(ArrayRef<StringRef> Lines,
245249261Sdim                                          const char *PrefixChars = " *") {
246249261Sdim    assert(Lines.size() > 1);
247249261Sdim    StringRef Prefix(Lines[1].data(), Lines[1].find_first_not_of(PrefixChars));
248249261Sdim    for (size_t i = 2; i < Lines.size(); ++i) {
249249261Sdim      for (size_t j = 0; j < Prefix.size() && j < Lines[i].size(); ++j) {
250249261Sdim        if (Prefix[j] != Lines[i][j]) {
251249261Sdim          Prefix = Prefix.substr(0, j);
252249261Sdim          break;
253249261Sdim        }
254249261Sdim      }
255249261Sdim    }
256249261Sdim    return Prefix;
257249261Sdim  }
258249261Sdim
259249261Sdim  /// \brief Splits one line in a line or block comment, if it doesn't fit to
260249261Sdim  /// provided column limit. Removes trailing whitespace in each line.
261249261Sdim  ///
262249261Sdim  /// \param Line points to the line contents without leading // or /*.
263249261Sdim  ///
264249261Sdim  /// \param StartColumn is the column where the first character of Line will be
265249261Sdim  /// located after formatting.
266249261Sdim  ///
267249261Sdim  /// \param LinePrefix is inserted after each line break.
268249261Sdim  ///
269249261Sdim  /// When \param InPPDirective is true, each line break will be preceded by a
270249261Sdim  /// backslash in the last column to make line breaks inside the comment
271249261Sdim  /// visually consistent with line breaks outside the comment. This only makes
272249261Sdim  /// sense for block comments.
273249261Sdim  ///
274249261Sdim  /// When \param CommentHasMoreLines is false, no line breaks/trailing
275249261Sdim  /// backslashes will be inserted after it.
276249261Sdim  void splitLineInComment(const FormatToken &Tok, StringRef Line,
277249261Sdim                          size_t StartColumn, StringRef LinePrefix,
278249261Sdim                          bool InPPDirective, bool CommentHasMoreLines,
279249261Sdim                          const char *WhiteSpaceChars = " ") {
280249261Sdim    size_t ColumnLimit = calculateColumnLimit(Style, InPPDirective);
281249261Sdim    const char *TokenStart = SourceMgr.getCharacterData(Tok.Tok.getLocation());
282249261Sdim
283249261Sdim    StringRef TrimmedLine = Line.rtrim();
284249261Sdim    int TrailingSpaceLength = Line.size() - TrimmedLine.size();
285249261Sdim
286249261Sdim    // Don't touch leading whitespace.
287249261Sdim    Line = TrimmedLine.ltrim();
288249261Sdim    StartColumn += TrimmedLine.size() - Line.size();
289249261Sdim
290249261Sdim    while (Line.size() + StartColumn > ColumnLimit) {
291249261Sdim      // Try to break at the last whitespace before the column limit.
292249261Sdim      size_t SpacePos =
293249261Sdim          Line.find_last_of(WhiteSpaceChars, ColumnLimit - StartColumn + 1);
294249261Sdim      if (SpacePos == StringRef::npos) {
295249261Sdim        // Try to find any whitespace in the line.
296249261Sdim        SpacePos = Line.find_first_of(WhiteSpaceChars);
297249261Sdim        if (SpacePos == StringRef::npos) // No whitespace found, give up.
298249261Sdim          break;
299249261Sdim      }
300249261Sdim
301249261Sdim      StringRef NextCut = Line.substr(0, SpacePos).rtrim();
302249261Sdim      StringRef RemainingLine = Line.substr(SpacePos).ltrim();
303249261Sdim      if (RemainingLine.empty())
304249261Sdim        break;
305249261Sdim
306249261Sdim      if (RemainingLine == "*/" && LinePrefix.endswith("* "))
307249261Sdim        LinePrefix = LinePrefix.substr(0, LinePrefix.size() - 2);
308249261Sdim
309249261Sdim      Line = RemainingLine;
310249261Sdim
311249261Sdim      size_t ReplaceChars = Line.begin() - NextCut.end();
312249261Sdim      breakToken(Tok, NextCut.end() - TokenStart, ReplaceChars, "", LinePrefix,
313249261Sdim                 InPPDirective, 0, NextCut.size() + StartColumn);
314249261Sdim      StartColumn = LinePrefix.size();
315249261Sdim    }
316249261Sdim
317249261Sdim    if (TrailingSpaceLength > 0 || (InPPDirective && CommentHasMoreLines)) {
318249261Sdim      // Remove trailing whitespace/insert backslash. + 1 is for \n
319249261Sdim      breakToken(Tok, Line.end() - TokenStart, TrailingSpaceLength + 1, "", "",
320249261Sdim                 InPPDirective, 0, Line.size() + StartColumn);
321249261Sdim    }
322249261Sdim  }
323249261Sdim
324249261Sdim  /// \brief Changes indentation of all lines in a block comment by Indent,
325249261Sdim  /// removes trailing whitespace from each line, splits lines that end up
326249261Sdim  /// exceeding the column limit.
327249261Sdim  void indentBlockComment(const AnnotatedToken &Tok, int Indent,
328249261Sdim                          int WhitespaceStartColumn, int NewLines,
329249261Sdim                          bool InPPDirective) {
330249261Sdim    assert(Tok.Type == TT_BlockComment);
331249261Sdim    int StartColumn = Indent + (NewLines == 0 ? WhitespaceStartColumn : 0);
332249261Sdim    const SourceLocation TokenLoc = Tok.FormatTok.Tok.getLocation();
333249261Sdim    const int CurrentIndent = SourceMgr.getSpellingColumnNumber(TokenLoc) - 1;
334249261Sdim    const int IndentDelta = Indent - CurrentIndent;
335249261Sdim    const StringRef Text(SourceMgr.getCharacterData(TokenLoc),
336249261Sdim                         Tok.FormatTok.TokenLength);
337249261Sdim    assert(Text.startswith("/*") && Text.endswith("*/"));
338249261Sdim
339249261Sdim    SmallVector<StringRef, 16> Lines;
340249261Sdim    Text.split(Lines, "\n");
341249261Sdim
342249261Sdim    if (IndentDelta > 0) {
343249261Sdim      std::string WhiteSpace(IndentDelta, ' ');
344249261Sdim      for (size_t i = 1; i < Lines.size(); ++i) {
345249261Sdim        Replaces.insert(tooling::Replacement(
346249261Sdim            SourceMgr, TokenLoc.getLocWithOffset(Lines[i].data() - Text.data()),
347249261Sdim            0, WhiteSpace));
348249261Sdim      }
349249261Sdim    } else if (IndentDelta < 0) {
350249261Sdim      std::string WhiteSpace(-IndentDelta, ' ');
351249261Sdim      // Check that the line is indented enough.
352249261Sdim      for (size_t i = 1; i < Lines.size(); ++i) {
353249261Sdim        if (!Lines[i].startswith(WhiteSpace))
354249261Sdim          return;
355249261Sdim      }
356249261Sdim      for (size_t i = 1; i < Lines.size(); ++i) {
357249261Sdim        Replaces.insert(tooling::Replacement(
358249261Sdim            SourceMgr, TokenLoc.getLocWithOffset(Lines[i].data() - Text.data()),
359249261Sdim            -IndentDelta, ""));
360249261Sdim      }
361249261Sdim    }
362249261Sdim
363249261Sdim    // Split long lines in comments.
364249261Sdim    size_t OldPrefixSize = 0;
365249261Sdim    std::string NewPrefix;
366249261Sdim    if (Lines.size() > 1) {
367249261Sdim      StringRef CurrentPrefix = findCommentLinesPrefix(Lines);
368249261Sdim      OldPrefixSize = CurrentPrefix.size();
369249261Sdim      NewPrefix = (IndentDelta < 0)
370249261Sdim                  ? CurrentPrefix.substr(-IndentDelta).str()
371249261Sdim                  : std::string(IndentDelta, ' ') + CurrentPrefix.str();
372249261Sdim      if (CurrentPrefix.endswith("*")) {
373249261Sdim        NewPrefix += " ";
374249261Sdim        ++OldPrefixSize;
375249261Sdim      }
376249261Sdim    } else if (Tok.Parent == 0) {
377249261Sdim      NewPrefix = std::string(StartColumn, ' ') + " * ";
378249261Sdim    }
379249261Sdim
380249261Sdim    StartColumn += 2;
381249261Sdim    for (size_t i = 0; i < Lines.size(); ++i) {
382249261Sdim      StringRef Line = Lines[i].substr(i == 0 ? 2 : OldPrefixSize);
383249261Sdim      splitLineInComment(Tok.FormatTok, Line, StartColumn, NewPrefix,
384249261Sdim                         InPPDirective, i != Lines.size() - 1);
385249261Sdim      StartColumn = NewPrefix.size();
386249261Sdim    }
387249261Sdim  }
388249261Sdim
389249261Sdim  std::string getNewLineText(unsigned NewLines, unsigned Spaces) {
390249261Sdim    return std::string(NewLines, '\n') + std::string(Spaces, ' ');
391249261Sdim  }
392249261Sdim
393249261Sdim  std::string getNewLineText(unsigned NewLines, unsigned Spaces,
394249261Sdim                             unsigned WhitespaceStartColumn) {
395249261Sdim    std::string NewLineText;
396249261Sdim    if (NewLines > 0) {
397249261Sdim      unsigned Offset =
398249261Sdim          std::min<int>(Style.ColumnLimit - 1, WhitespaceStartColumn);
399249261Sdim      for (unsigned i = 0; i < NewLines; ++i) {
400249261Sdim        NewLineText += std::string(Style.ColumnLimit - Offset - 1, ' ');
401249261Sdim        NewLineText += "\\\n";
402249261Sdim        Offset = 0;
403249261Sdim      }
404249261Sdim    }
405249261Sdim    return NewLineText + std::string(Spaces, ' ');
406249261Sdim  }
407249261Sdim
408249261Sdim  /// \brief Structure to store a comment for later layout and alignment.
409249261Sdim  struct StoredComment {
410249261Sdim    FormatToken Tok;
411249261Sdim    unsigned MinColumn;
412249261Sdim    unsigned MaxColumn;
413249261Sdim    unsigned NewLines;
414249261Sdim    unsigned Spaces;
415249261Sdim    bool Untouchable;
416249261Sdim  };
417249261Sdim  SmallVector<StoredComment, 16> Comments;
418249261Sdim  typedef SmallVector<StoredComment, 16>::iterator comment_iterator;
419249261Sdim
420249261Sdim  /// \brief Try to align all stashed comments.
421249261Sdim  void alignComments() {
422249261Sdim    unsigned MinColumn = 0;
423249261Sdim    unsigned MaxColumn = UINT_MAX;
424249261Sdim    comment_iterator Start = Comments.begin();
425249261Sdim    for (comment_iterator I = Start, E = Comments.end(); I != E; ++I) {
426249261Sdim      if (I->MinColumn > MaxColumn || I->MaxColumn < MinColumn) {
427249261Sdim        alignComments(Start, I, MinColumn);
428249261Sdim        MinColumn = I->MinColumn;
429249261Sdim        MaxColumn = I->MaxColumn;
430249261Sdim        Start = I;
431249261Sdim      } else {
432249261Sdim        MinColumn = std::max(MinColumn, I->MinColumn);
433249261Sdim        MaxColumn = std::min(MaxColumn, I->MaxColumn);
434249261Sdim      }
435249261Sdim    }
436249261Sdim    alignComments(Start, Comments.end(), MinColumn);
437249261Sdim    Comments.clear();
438249261Sdim  }
439249261Sdim
440249261Sdim  /// \brief Put all the comments between \p I and \p E into \p Column.
441249261Sdim  void alignComments(comment_iterator I, comment_iterator E, unsigned Column) {
442249261Sdim    while (I != E) {
443249261Sdim      if (!I->Untouchable) {
444249261Sdim        unsigned Spaces = I->Spaces + Column - I->MinColumn;
445249261Sdim        storeReplacement(I->Tok, getNewLineText(I->NewLines, Spaces));
446249261Sdim      }
447249261Sdim      ++I;
448249261Sdim    }
449249261Sdim  }
450249261Sdim
451249261Sdim  /// \brief Stores \p Text as the replacement for the whitespace in front of
452249261Sdim  /// \p Tok.
453249261Sdim  void storeReplacement(const FormatToken &Tok, const std::string Text) {
454249261Sdim    // Don't create a replacement, if it does not change anything.
455249261Sdim    if (StringRef(SourceMgr.getCharacterData(Tok.WhiteSpaceStart),
456249261Sdim                  Tok.WhiteSpaceLength) == Text)
457249261Sdim      return;
458249261Sdim
459249261Sdim    Replaces.insert(tooling::Replacement(SourceMgr, Tok.WhiteSpaceStart,
460249261Sdim                                         Tok.WhiteSpaceLength, Text));
461249261Sdim  }
462249261Sdim
463249261Sdim  SourceManager &SourceMgr;
464249261Sdim  tooling::Replacements Replaces;
465249261Sdim  const FormatStyle &Style;
466249261Sdim};
467249261Sdim
468249261Sdimclass UnwrappedLineFormatter {
469249261Sdimpublic:
470249261Sdim  UnwrappedLineFormatter(const FormatStyle &Style, SourceManager &SourceMgr,
471249261Sdim                         const AnnotatedLine &Line, unsigned FirstIndent,
472249261Sdim                         const AnnotatedToken &RootToken,
473249261Sdim                         WhitespaceManager &Whitespaces, bool StructuralError)
474249261Sdim      : Style(Style), SourceMgr(SourceMgr), Line(Line),
475249261Sdim        FirstIndent(FirstIndent), RootToken(RootToken),
476249261Sdim        Whitespaces(Whitespaces), Count(0) {}
477249261Sdim
478249261Sdim  /// \brief Formats an \c UnwrappedLine.
479249261Sdim  ///
480249261Sdim  /// \returns The column after the last token in the last line of the
481249261Sdim  /// \c UnwrappedLine.
482249261Sdim  unsigned format(const AnnotatedLine *NextLine) {
483249261Sdim    // Initialize state dependent on indent.
484249261Sdim    LineState State;
485249261Sdim    State.Column = FirstIndent;
486249261Sdim    State.NextToken = &RootToken;
487249261Sdim    State.Stack.push_back(
488249261Sdim        ParenState(FirstIndent, FirstIndent, !Style.BinPackParameters,
489249261Sdim                   /*HasMultiParameterLine=*/ false));
490249261Sdim    State.LineContainsContinuedForLoopSection = false;
491249261Sdim    State.ParenLevel = 0;
492249261Sdim    State.StartOfStringLiteral = 0;
493249261Sdim    State.StartOfLineLevel = State.ParenLevel;
494249261Sdim
495249261Sdim    DEBUG({
496249261Sdim      DebugTokenState(*State.NextToken);
497249261Sdim    });
498249261Sdim
499249261Sdim    // The first token has already been indented and thus consumed.
500249261Sdim    moveStateToNextToken(State, /*DryRun=*/ false);
501249261Sdim
502249261Sdim    // If everything fits on a single line, just put it there.
503249261Sdim    unsigned ColumnLimit = Style.ColumnLimit;
504249261Sdim    if (NextLine && NextLine->InPPDirective &&
505249261Sdim        !NextLine->First.FormatTok.HasUnescapedNewline)
506249261Sdim      ColumnLimit = getColumnLimit();
507249261Sdim    if (Line.Last->TotalLength <= ColumnLimit - FirstIndent) {
508249261Sdim      while (State.NextToken != NULL) {
509249261Sdim        addTokenToState(false, false, State);
510249261Sdim      }
511249261Sdim      return State.Column;
512249261Sdim    }
513249261Sdim
514249261Sdim    // If the ObjC method declaration does not fit on a line, we should format
515249261Sdim    // it with one arg per line.
516249261Sdim    if (Line.Type == LT_ObjCMethodDecl)
517249261Sdim      State.Stack.back().BreakBeforeParameter = true;
518249261Sdim
519249261Sdim    // Find best solution in solution space.
520249261Sdim    return analyzeSolutionSpace(State);
521249261Sdim  }
522249261Sdim
523249261Sdimprivate:
524249261Sdim  void DebugTokenState(const AnnotatedToken &AnnotatedTok) {
525249261Sdim    const Token &Tok = AnnotatedTok.FormatTok.Tok;
526249261Sdim    llvm::errs() << StringRef(SourceMgr.getCharacterData(Tok.getLocation()),
527249261Sdim                              Tok.getLength());
528249261Sdim    llvm::errs();
529249261Sdim  }
530249261Sdim
531249261Sdim  struct ParenState {
532249261Sdim    ParenState(unsigned Indent, unsigned LastSpace, bool AvoidBinPacking,
533249261Sdim               bool HasMultiParameterLine)
534249261Sdim        : Indent(Indent), LastSpace(LastSpace), FirstLessLess(0),
535249261Sdim          BreakBeforeClosingBrace(false), QuestionColumn(0),
536249261Sdim          AvoidBinPacking(AvoidBinPacking), BreakBeforeParameter(false),
537249261Sdim          HasMultiParameterLine(HasMultiParameterLine), ColonPos(0),
538249261Sdim          StartOfFunctionCall(0), NestedNameSpecifierContinuation(0),
539249261Sdim          CallContinuation(0), VariablePos(0) {}
540249261Sdim
541249261Sdim    /// \brief The position to which a specific parenthesis level needs to be
542249261Sdim    /// indented.
543249261Sdim    unsigned Indent;
544249261Sdim
545249261Sdim    /// \brief The position of the last space on each level.
546249261Sdim    ///
547249261Sdim    /// Used e.g. to break like:
548249261Sdim    /// functionCall(Parameter, otherCall(
549249261Sdim    ///                             OtherParameter));
550249261Sdim    unsigned LastSpace;
551249261Sdim
552249261Sdim    /// \brief The position the first "<<" operator encountered on each level.
553249261Sdim    ///
554249261Sdim    /// Used to align "<<" operators. 0 if no such operator has been encountered
555249261Sdim    /// on a level.
556249261Sdim    unsigned FirstLessLess;
557249261Sdim
558249261Sdim    /// \brief Whether a newline needs to be inserted before the block's closing
559249261Sdim    /// brace.
560249261Sdim    ///
561249261Sdim    /// We only want to insert a newline before the closing brace if there also
562249261Sdim    /// was a newline after the beginning left brace.
563249261Sdim    bool BreakBeforeClosingBrace;
564249261Sdim
565249261Sdim    /// \brief The column of a \c ? in a conditional expression;
566249261Sdim    unsigned QuestionColumn;
567249261Sdim
568249261Sdim    /// \brief Avoid bin packing, i.e. multiple parameters/elements on multiple
569249261Sdim    /// lines, in this context.
570249261Sdim    bool AvoidBinPacking;
571249261Sdim
572249261Sdim    /// \brief Break after the next comma (or all the commas in this context if
573249261Sdim    /// \c AvoidBinPacking is \c true).
574249261Sdim    bool BreakBeforeParameter;
575249261Sdim
576249261Sdim    /// \brief This context already has a line with more than one parameter.
577249261Sdim    bool HasMultiParameterLine;
578249261Sdim
579249261Sdim    /// \brief The position of the colon in an ObjC method declaration/call.
580249261Sdim    unsigned ColonPos;
581249261Sdim
582249261Sdim    /// \brief The start of the most recent function in a builder-type call.
583249261Sdim    unsigned StartOfFunctionCall;
584249261Sdim
585249261Sdim    /// \brief If a nested name specifier was broken over multiple lines, this
586249261Sdim    /// contains the start column of the second line. Otherwise 0.
587249261Sdim    unsigned NestedNameSpecifierContinuation;
588249261Sdim
589249261Sdim    /// \brief If a call expression was broken over multiple lines, this
590249261Sdim    /// contains the start column of the second line. Otherwise 0.
591249261Sdim    unsigned CallContinuation;
592249261Sdim
593249261Sdim    /// \brief The column of the first variable name in a variable declaration.
594249261Sdim    ///
595249261Sdim    /// Used to align further variables if necessary.
596249261Sdim    unsigned VariablePos;
597249261Sdim
598249261Sdim    bool operator<(const ParenState &Other) const {
599249261Sdim      if (Indent != Other.Indent)
600249261Sdim        return Indent < Other.Indent;
601249261Sdim      if (LastSpace != Other.LastSpace)
602249261Sdim        return LastSpace < Other.LastSpace;
603249261Sdim      if (FirstLessLess != Other.FirstLessLess)
604249261Sdim        return FirstLessLess < Other.FirstLessLess;
605249261Sdim      if (BreakBeforeClosingBrace != Other.BreakBeforeClosingBrace)
606249261Sdim        return BreakBeforeClosingBrace;
607249261Sdim      if (QuestionColumn != Other.QuestionColumn)
608249261Sdim        return QuestionColumn < Other.QuestionColumn;
609249261Sdim      if (AvoidBinPacking != Other.AvoidBinPacking)
610249261Sdim        return AvoidBinPacking;
611249261Sdim      if (BreakBeforeParameter != Other.BreakBeforeParameter)
612249261Sdim        return BreakBeforeParameter;
613249261Sdim      if (HasMultiParameterLine != Other.HasMultiParameterLine)
614249261Sdim        return HasMultiParameterLine;
615249261Sdim      if (ColonPos != Other.ColonPos)
616249261Sdim        return ColonPos < Other.ColonPos;
617249261Sdim      if (StartOfFunctionCall != Other.StartOfFunctionCall)
618249261Sdim        return StartOfFunctionCall < Other.StartOfFunctionCall;
619249261Sdim      if (NestedNameSpecifierContinuation !=
620249261Sdim              Other.NestedNameSpecifierContinuation)
621249261Sdim        return NestedNameSpecifierContinuation <
622249261Sdim               Other.NestedNameSpecifierContinuation;
623249261Sdim      if (CallContinuation != Other.CallContinuation)
624249261Sdim        return CallContinuation < Other.CallContinuation;
625249261Sdim      if (VariablePos != Other.VariablePos)
626249261Sdim        return VariablePos < Other.VariablePos;
627249261Sdim      return false;
628249261Sdim    }
629249261Sdim  };
630249261Sdim
631249261Sdim  /// \brief The current state when indenting a unwrapped line.
632249261Sdim  ///
633249261Sdim  /// As the indenting tries different combinations this is copied by value.
634249261Sdim  struct LineState {
635249261Sdim    /// \brief The number of used columns in the current line.
636249261Sdim    unsigned Column;
637249261Sdim
638249261Sdim    /// \brief The token that needs to be next formatted.
639249261Sdim    const AnnotatedToken *NextToken;
640249261Sdim
641249261Sdim    /// \brief \c true if this line contains a continued for-loop section.
642249261Sdim    bool LineContainsContinuedForLoopSection;
643249261Sdim
644249261Sdim    /// \brief The level of nesting inside (), [], <> and {}.
645249261Sdim    unsigned ParenLevel;
646249261Sdim
647249261Sdim    /// \brief The \c ParenLevel at the start of this line.
648249261Sdim    unsigned StartOfLineLevel;
649249261Sdim
650249261Sdim    /// \brief The start column of the string literal, if we're in a string
651249261Sdim    /// literal sequence, 0 otherwise.
652249261Sdim    unsigned StartOfStringLiteral;
653249261Sdim
654249261Sdim    /// \brief A stack keeping track of properties applying to parenthesis
655249261Sdim    /// levels.
656249261Sdim    std::vector<ParenState> Stack;
657249261Sdim
658249261Sdim    /// \brief Comparison operator to be able to used \c LineState in \c map.
659249261Sdim    bool operator<(const LineState &Other) const {
660249261Sdim      if (NextToken != Other.NextToken)
661249261Sdim        return NextToken < Other.NextToken;
662249261Sdim      if (Column != Other.Column)
663249261Sdim        return Column < Other.Column;
664249261Sdim      if (LineContainsContinuedForLoopSection !=
665249261Sdim              Other.LineContainsContinuedForLoopSection)
666249261Sdim        return LineContainsContinuedForLoopSection;
667249261Sdim      if (ParenLevel != Other.ParenLevel)
668249261Sdim        return ParenLevel < Other.ParenLevel;
669249261Sdim      if (StartOfLineLevel != Other.StartOfLineLevel)
670249261Sdim        return StartOfLineLevel < Other.StartOfLineLevel;
671249261Sdim      if (StartOfStringLiteral != Other.StartOfStringLiteral)
672249261Sdim        return StartOfStringLiteral < Other.StartOfStringLiteral;
673249261Sdim      return Stack < Other.Stack;
674249261Sdim    }
675249261Sdim  };
676249261Sdim
677249261Sdim  /// \brief Appends the next token to \p State and updates information
678249261Sdim  /// necessary for indentation.
679249261Sdim  ///
680249261Sdim  /// Puts the token on the current line if \p Newline is \c true and adds a
681249261Sdim  /// line break and necessary indentation otherwise.
682249261Sdim  ///
683249261Sdim  /// If \p DryRun is \c false, also creates and stores the required
684249261Sdim  /// \c Replacement.
685249261Sdim  unsigned addTokenToState(bool Newline, bool DryRun, LineState &State) {
686249261Sdim    const AnnotatedToken &Current = *State.NextToken;
687249261Sdim    const AnnotatedToken &Previous = *State.NextToken->Parent;
688249261Sdim
689249261Sdim    if (State.Stack.size() == 0 || Current.Type == TT_ImplicitStringLiteral) {
690249261Sdim      State.Column += State.NextToken->FormatTok.WhiteSpaceLength +
691249261Sdim                      State.NextToken->FormatTok.TokenLength;
692249261Sdim      if (State.NextToken->Children.empty())
693249261Sdim        State.NextToken = NULL;
694249261Sdim      else
695249261Sdim        State.NextToken = &State.NextToken->Children[0];
696249261Sdim      return 0;
697249261Sdim    }
698249261Sdim
699249261Sdim    // If we are continuing an expression, we want to indent an extra 4 spaces.
700249261Sdim    unsigned ContinuationIndent =
701249261Sdim        std::max(State.Stack.back().LastSpace, State.Stack.back().Indent) + 4;
702249261Sdim    if (Newline) {
703249261Sdim      unsigned WhitespaceStartColumn = State.Column;
704249261Sdim      if (Current.is(tok::r_brace)) {
705249261Sdim        State.Column = Line.Level * 2;
706249261Sdim      } else if (Current.is(tok::string_literal) &&
707249261Sdim                 State.StartOfStringLiteral != 0) {
708249261Sdim        State.Column = State.StartOfStringLiteral;
709249261Sdim        State.Stack.back().BreakBeforeParameter = true;
710249261Sdim      } else if (Current.is(tok::lessless) &&
711249261Sdim                 State.Stack.back().FirstLessLess != 0) {
712249261Sdim        State.Column = State.Stack.back().FirstLessLess;
713249261Sdim      } else if (Previous.is(tok::coloncolon)) {
714249261Sdim        if (State.Stack.back().NestedNameSpecifierContinuation == 0) {
715249261Sdim          State.Column = ContinuationIndent;
716249261Sdim          State.Stack.back().NestedNameSpecifierContinuation = State.Column;
717249261Sdim        } else {
718249261Sdim          State.Column = State.Stack.back().NestedNameSpecifierContinuation;
719249261Sdim        }
720249261Sdim      } else if (Current.isOneOf(tok::period, tok::arrow)) {
721249261Sdim        if (State.Stack.back().CallContinuation == 0) {
722249261Sdim          State.Column = ContinuationIndent;
723249261Sdim          State.Stack.back().CallContinuation = State.Column;
724249261Sdim        } else {
725249261Sdim          State.Column = State.Stack.back().CallContinuation;
726249261Sdim        }
727249261Sdim      } else if (Current.Type == TT_ConditionalExpr) {
728249261Sdim        State.Column = State.Stack.back().QuestionColumn;
729249261Sdim      } else if (Previous.is(tok::comma) &&
730249261Sdim                 State.Stack.back().VariablePos != 0) {
731249261Sdim        State.Column = State.Stack.back().VariablePos;
732249261Sdim      } else if (Previous.ClosesTemplateDeclaration ||
733249261Sdim                 (Current.Type == TT_StartOfName && State.ParenLevel == 0)) {
734249261Sdim        State.Column = State.Stack.back().Indent;
735249261Sdim      } else if (Current.Type == TT_ObjCSelectorName) {
736249261Sdim        if (State.Stack.back().ColonPos > Current.FormatTok.TokenLength) {
737249261Sdim          State.Column =
738249261Sdim              State.Stack.back().ColonPos - Current.FormatTok.TokenLength;
739249261Sdim        } else {
740249261Sdim          State.Column = State.Stack.back().Indent;
741249261Sdim          State.Stack.back().ColonPos =
742249261Sdim              State.Column + Current.FormatTok.TokenLength;
743249261Sdim        }
744249261Sdim      } else if (Current.Type == TT_StartOfName || Current.is(tok::question) ||
745249261Sdim                 Previous.is(tok::equal) || isComparison(Previous) ||
746249261Sdim                 Previous.Type == TT_ObjCMethodExpr) {
747249261Sdim        State.Column = ContinuationIndent;
748249261Sdim      } else {
749249261Sdim        State.Column = State.Stack.back().Indent;
750249261Sdim        // Ensure that we fall back to indenting 4 spaces instead of just
751249261Sdim        // flushing continuations left.
752249261Sdim        if (State.Column == FirstIndent)
753249261Sdim          State.Column += 4;
754249261Sdim      }
755249261Sdim
756249261Sdim      if (Current.is(tok::question))
757249261Sdim        State.Stack.back().BreakBeforeParameter = true;
758249261Sdim      if (Previous.isOneOf(tok::comma, tok::semi) &&
759249261Sdim          !State.Stack.back().AvoidBinPacking)
760249261Sdim        State.Stack.back().BreakBeforeParameter = false;
761249261Sdim
762249261Sdim      if (!DryRun) {
763249261Sdim        unsigned NewLines = 1;
764249261Sdim        if (Current.Type == TT_LineComment)
765249261Sdim          NewLines =
766249261Sdim              std::max(NewLines, std::min(Current.FormatTok.NewlinesBefore,
767249261Sdim                                          Style.MaxEmptyLinesToKeep + 1));
768249261Sdim        if (!Line.InPPDirective)
769249261Sdim          Whitespaces.replaceWhitespace(Current, NewLines, State.Column,
770249261Sdim                                        WhitespaceStartColumn);
771249261Sdim        else
772249261Sdim          Whitespaces.replacePPWhitespace(Current, NewLines, State.Column,
773249261Sdim                                          WhitespaceStartColumn);
774249261Sdim      }
775249261Sdim
776249261Sdim      State.Stack.back().LastSpace = State.Column;
777249261Sdim      State.StartOfLineLevel = State.ParenLevel;
778249261Sdim
779249261Sdim      // Any break on this level means that the parent level has been broken
780249261Sdim      // and we need to avoid bin packing there.
781249261Sdim      for (unsigned i = 0, e = State.Stack.size() - 1; i != e; ++i) {
782249261Sdim        State.Stack[i].BreakBeforeParameter = true;
783249261Sdim      }
784249261Sdim      if (Current.isOneOf(tok::period, tok::arrow))
785249261Sdim        State.Stack.back().BreakBeforeParameter = true;
786249261Sdim
787249261Sdim      // If we break after {, we should also break before the corresponding }.
788249261Sdim      if (Previous.is(tok::l_brace))
789249261Sdim        State.Stack.back().BreakBeforeClosingBrace = true;
790249261Sdim
791249261Sdim      if (State.Stack.back().AvoidBinPacking) {
792249261Sdim        // If we are breaking after '(', '{', '<', this is not bin packing
793249261Sdim        // unless AllowAllParametersOfDeclarationOnNextLine is false.
794249261Sdim        if ((Previous.isNot(tok::l_paren) && Previous.isNot(tok::l_brace)) ||
795249261Sdim            (!Style.AllowAllParametersOfDeclarationOnNextLine &&
796249261Sdim             Line.MustBeDeclaration))
797249261Sdim          State.Stack.back().BreakBeforeParameter = true;
798249261Sdim      }
799249261Sdim    } else {
800249261Sdim      if (Current.is(tok::equal) &&
801249261Sdim          (RootToken.is(tok::kw_for) || State.ParenLevel == 0) &&
802249261Sdim          State.Stack.back().VariablePos == 0) {
803249261Sdim        State.Stack.back().VariablePos = State.Column;
804249261Sdim        // Move over * and & if they are bound to the variable name.
805249261Sdim        const AnnotatedToken *Tok = &Previous;
806249261Sdim        while (Tok &&
807249261Sdim               State.Stack.back().VariablePos >= Tok->FormatTok.TokenLength) {
808249261Sdim          State.Stack.back().VariablePos -= Tok->FormatTok.TokenLength;
809249261Sdim          if (Tok->SpacesRequiredBefore != 0)
810249261Sdim            break;
811249261Sdim          Tok = Tok->Parent;
812249261Sdim        }
813249261Sdim        if (Previous.PartOfMultiVariableDeclStmt)
814249261Sdim          State.Stack.back().LastSpace = State.Stack.back().VariablePos;
815249261Sdim      }
816249261Sdim
817249261Sdim      unsigned Spaces = State.NextToken->SpacesRequiredBefore;
818249261Sdim
819249261Sdim      if (!DryRun)
820249261Sdim        Whitespaces.replaceWhitespace(Current, 0, Spaces, State.Column);
821249261Sdim
822249261Sdim      if (Current.Type == TT_ObjCSelectorName &&
823249261Sdim          State.Stack.back().ColonPos == 0) {
824249261Sdim        if (State.Stack.back().Indent + Current.LongestObjCSelectorName >
825249261Sdim                State.Column + Spaces + Current.FormatTok.TokenLength)
826249261Sdim          State.Stack.back().ColonPos =
827249261Sdim              State.Stack.back().Indent + Current.LongestObjCSelectorName;
828249261Sdim        else
829249261Sdim          State.Stack.back().ColonPos =
830249261Sdim              State.Column + Spaces + Current.FormatTok.TokenLength;
831249261Sdim      }
832249261Sdim
833249261Sdim      if (Current.Type != TT_LineComment &&
834249261Sdim          (Previous.isOneOf(tok::l_paren, tok::l_brace) ||
835249261Sdim           State.NextToken->Parent->Type == TT_TemplateOpener))
836249261Sdim        State.Stack.back().Indent = State.Column + Spaces;
837249261Sdim      if (Previous.is(tok::comma) && !isTrailingComment(Current))
838249261Sdim        State.Stack.back().HasMultiParameterLine = true;
839249261Sdim
840249261Sdim      State.Column += Spaces;
841249261Sdim      if (Current.is(tok::l_paren) && Previous.isOneOf(tok::kw_if, tok::kw_for))
842249261Sdim        // Treat the condition inside an if as if it was a second function
843249261Sdim        // parameter, i.e. let nested calls have an indent of 4.
844249261Sdim        State.Stack.back().LastSpace = State.Column + 1; // 1 is length of "(".
845249261Sdim      else if (Previous.is(tok::comma))
846249261Sdim        State.Stack.back().LastSpace = State.Column;
847249261Sdim      else if ((Previous.Type == TT_BinaryOperator ||
848249261Sdim                Previous.Type == TT_ConditionalExpr ||
849249261Sdim                Previous.Type == TT_CtorInitializerColon) &&
850249261Sdim               getPrecedence(Previous) != prec::Assignment)
851249261Sdim        State.Stack.back().LastSpace = State.Column;
852249261Sdim      else if (Previous.Type == TT_InheritanceColon)
853249261Sdim        State.Stack.back().Indent = State.Column;
854249261Sdim      else if (Previous.ParameterCount > 1 &&
855249261Sdim               (Previous.isOneOf(tok::l_paren, tok::l_square, tok::l_brace) ||
856249261Sdim                Previous.Type == TT_TemplateOpener))
857249261Sdim        // If this function has multiple parameters, indent nested calls from
858249261Sdim        // the start of the first parameter.
859249261Sdim        State.Stack.back().LastSpace = State.Column;
860249261Sdim    }
861249261Sdim
862249261Sdim    return moveStateToNextToken(State, DryRun);
863249261Sdim  }
864249261Sdim
865249261Sdim  /// \brief Mark the next token as consumed in \p State and modify its stacks
866249261Sdim  /// accordingly.
867249261Sdim  unsigned moveStateToNextToken(LineState &State, bool DryRun) {
868249261Sdim    const AnnotatedToken &Current = *State.NextToken;
869249261Sdim    assert(State.Stack.size());
870249261Sdim
871249261Sdim    if (Current.Type == TT_InheritanceColon)
872249261Sdim      State.Stack.back().AvoidBinPacking = true;
873249261Sdim    if (Current.is(tok::lessless) && State.Stack.back().FirstLessLess == 0)
874249261Sdim      State.Stack.back().FirstLessLess = State.Column;
875249261Sdim    if (Current.is(tok::question))
876249261Sdim      State.Stack.back().QuestionColumn = State.Column;
877249261Sdim    if (Current.isOneOf(tok::period, tok::arrow) &&
878249261Sdim        Line.Type == LT_BuilderTypeCall && State.ParenLevel == 0)
879249261Sdim      State.Stack.back().StartOfFunctionCall =
880249261Sdim          Current.LastInChainOfCalls ? 0 : State.Column;
881249261Sdim    if (Current.Type == TT_CtorInitializerColon) {
882249261Sdim      if (Style.ConstructorInitializerAllOnOneLineOrOnePerLine)
883249261Sdim        State.Stack.back().AvoidBinPacking = true;
884249261Sdim      State.Stack.back().BreakBeforeParameter = false;
885249261Sdim    }
886249261Sdim
887249261Sdim    // In ObjC method declaration we align on the ":" of parameters, but we need
888249261Sdim    // to ensure that we indent parameters on subsequent lines by at least 4.
889249261Sdim    if (Current.Type == TT_ObjCMethodSpecifier)
890249261Sdim      State.Stack.back().Indent += 4;
891249261Sdim
892249261Sdim    // Insert scopes created by fake parenthesis.
893249261Sdim    for (unsigned i = 0, e = Current.FakeLParens; i != e; ++i) {
894249261Sdim      ParenState NewParenState = State.Stack.back();
895249261Sdim      NewParenState.Indent = std::max(State.Column, State.Stack.back().Indent);
896249261Sdim      NewParenState.BreakBeforeParameter = false;
897249261Sdim      State.Stack.push_back(NewParenState);
898249261Sdim    }
899249261Sdim
900249261Sdim    // If we encounter an opening (, [, { or <, we add a level to our stacks to
901249261Sdim    // prepare for the following tokens.
902249261Sdim    if (Current.isOneOf(tok::l_paren, tok::l_square, tok::l_brace) ||
903249261Sdim        State.NextToken->Type == TT_TemplateOpener) {
904249261Sdim      unsigned NewIndent;
905249261Sdim      bool AvoidBinPacking;
906249261Sdim      if (Current.is(tok::l_brace)) {
907249261Sdim        NewIndent = 2 + State.Stack.back().LastSpace;
908249261Sdim        AvoidBinPacking = false;
909249261Sdim      } else {
910249261Sdim        NewIndent = 4 + std::max(State.Stack.back().LastSpace,
911249261Sdim                                 State.Stack.back().StartOfFunctionCall);
912249261Sdim        AvoidBinPacking =
913249261Sdim            !Style.BinPackParameters || State.Stack.back().AvoidBinPacking;
914249261Sdim      }
915249261Sdim      State.Stack.push_back(
916249261Sdim          ParenState(NewIndent, State.Stack.back().LastSpace, AvoidBinPacking,
917249261Sdim                     State.Stack.back().HasMultiParameterLine));
918249261Sdim      ++State.ParenLevel;
919249261Sdim    }
920249261Sdim
921249261Sdim    // If this '[' opens an ObjC call, determine whether all parameters fit into
922249261Sdim    // one line and put one per line if they don't.
923249261Sdim    if (Current.is(tok::l_square) && Current.Type == TT_ObjCMethodExpr &&
924249261Sdim        Current.MatchingParen != NULL) {
925249261Sdim      if (getLengthToMatchingParen(Current) + State.Column > getColumnLimit())
926249261Sdim        State.Stack.back().BreakBeforeParameter = true;
927249261Sdim    }
928249261Sdim
929249261Sdim    // If we encounter a closing ), ], } or >, we can remove a level from our
930249261Sdim    // stacks.
931249261Sdim    if (Current.isOneOf(tok::r_paren, tok::r_square) ||
932249261Sdim        (Current.is(tok::r_brace) && State.NextToken != &RootToken) ||
933249261Sdim        State.NextToken->Type == TT_TemplateCloser) {
934249261Sdim      State.Stack.pop_back();
935249261Sdim      --State.ParenLevel;
936249261Sdim    }
937249261Sdim
938249261Sdim    // Remove scopes created by fake parenthesis.
939249261Sdim    for (unsigned i = 0, e = Current.FakeRParens; i != e; ++i) {
940249261Sdim      unsigned VariablePos = State.Stack.back().VariablePos;
941249261Sdim      State.Stack.pop_back();
942249261Sdim      State.Stack.back().VariablePos = VariablePos;
943249261Sdim    }
944249261Sdim
945249261Sdim    if (Current.is(tok::string_literal)) {
946249261Sdim      State.StartOfStringLiteral = State.Column;
947249261Sdim    } else if (Current.isNot(tok::comment)) {
948249261Sdim      State.StartOfStringLiteral = 0;
949249261Sdim    }
950249261Sdim
951249261Sdim    State.Column += Current.FormatTok.TokenLength;
952249261Sdim
953249261Sdim    if (State.NextToken->Children.empty())
954249261Sdim      State.NextToken = NULL;
955249261Sdim    else
956249261Sdim      State.NextToken = &State.NextToken->Children[0];
957249261Sdim
958249261Sdim    return breakProtrudingToken(Current, State, DryRun);
959249261Sdim  }
960249261Sdim
961249261Sdim  /// \brief If the current token sticks out over the end of the line, break
962249261Sdim  /// it if possible.
963249261Sdim  unsigned breakProtrudingToken(const AnnotatedToken &Current, LineState &State,
964249261Sdim                                bool DryRun) {
965249261Sdim    if (Current.isNot(tok::string_literal))
966249261Sdim      return 0;
967249261Sdim    // Only break up default narrow strings.
968249261Sdim    const char *LiteralData = Current.FormatTok.Tok.getLiteralData();
969249261Sdim    if (!LiteralData || *LiteralData != '"')
970249261Sdim      return 0;
971249261Sdim
972249261Sdim    unsigned Penalty = 0;
973249261Sdim    unsigned TailOffset = 0;
974249261Sdim    unsigned TailLength = Current.FormatTok.TokenLength;
975249261Sdim    unsigned StartColumn = State.Column - Current.FormatTok.TokenLength;
976249261Sdim    unsigned OffsetFromStart = 0;
977249261Sdim    while (StartColumn + TailLength > getColumnLimit()) {
978249261Sdim      StringRef Text = StringRef(LiteralData + TailOffset, TailLength);
979249261Sdim      if (StartColumn + OffsetFromStart + 1 > getColumnLimit())
980249261Sdim        break;
981249261Sdim      StringRef::size_type SplitPoint = getSplitPoint(
982249261Sdim          Text, getColumnLimit() - StartColumn - OffsetFromStart - 1);
983249261Sdim      if (SplitPoint == StringRef::npos)
984249261Sdim        break;
985249261Sdim      assert(SplitPoint != 0);
986249261Sdim      // +2, because 'Text' starts after the opening quotes, and does not
987249261Sdim      // include the closing quote we need to insert.
988249261Sdim      unsigned WhitespaceStartColumn =
989249261Sdim          StartColumn + OffsetFromStart + SplitPoint + 2;
990249261Sdim      State.Stack.back().LastSpace = StartColumn;
991249261Sdim      if (!DryRun) {
992249261Sdim        Whitespaces.breakToken(Current.FormatTok, TailOffset + SplitPoint + 1,
993249261Sdim                               0, "\"", "\"", Line.InPPDirective, StartColumn,
994249261Sdim                               WhitespaceStartColumn);
995249261Sdim      }
996249261Sdim      TailOffset += SplitPoint + 1;
997249261Sdim      TailLength -= SplitPoint + 1;
998249261Sdim      OffsetFromStart = 1;
999249261Sdim      Penalty += Style.PenaltyExcessCharacter;
1000249261Sdim      for (unsigned i = 0, e = State.Stack.size(); i != e; ++i)
1001249261Sdim        State.Stack[i].BreakBeforeParameter = true;
1002249261Sdim    }
1003249261Sdim    State.Column = StartColumn + TailLength;
1004249261Sdim    return Penalty;
1005249261Sdim  }
1006249261Sdim
1007249261Sdim  StringRef::size_type
1008249261Sdim  getSplitPoint(StringRef Text, StringRef::size_type Offset) {
1009249261Sdim    StringRef::size_type SpaceOffset = Text.rfind(' ', Offset);
1010249261Sdim    if (SpaceOffset != StringRef::npos && SpaceOffset != 0)
1011249261Sdim      return SpaceOffset;
1012249261Sdim    StringRef::size_type SlashOffset = Text.rfind('/', Offset);
1013249261Sdim    if (SlashOffset != StringRef::npos && SlashOffset != 0)
1014249261Sdim      return SlashOffset;
1015249261Sdim    StringRef::size_type Split = getStartOfCharacter(Text, Offset);
1016249261Sdim    if (Split != StringRef::npos && Split > 1)
1017249261Sdim      // Do not split at 0.
1018249261Sdim      return Split - 1;
1019249261Sdim    return StringRef::npos;
1020249261Sdim  }
1021249261Sdim
1022249261Sdim  StringRef::size_type
1023249261Sdim  getStartOfCharacter(StringRef Text, StringRef::size_type Offset) {
1024249261Sdim    StringRef::size_type NextEscape = Text.find('\\');
1025249261Sdim    while (NextEscape != StringRef::npos && NextEscape < Offset) {
1026249261Sdim      StringRef::size_type SequenceLength =
1027249261Sdim          getEscapeSequenceLength(Text.substr(NextEscape));
1028249261Sdim      if (Offset < NextEscape + SequenceLength)
1029249261Sdim        return NextEscape;
1030249261Sdim      NextEscape = Text.find('\\', NextEscape + SequenceLength);
1031249261Sdim    }
1032249261Sdim    return Offset;
1033249261Sdim  }
1034249261Sdim
1035249261Sdim  unsigned getEscapeSequenceLength(StringRef Text) {
1036249261Sdim    assert(Text[0] == '\\');
1037249261Sdim    if (Text.size() < 2)
1038249261Sdim      return 1;
1039249261Sdim
1040249261Sdim    switch (Text[1]) {
1041249261Sdim    case 'u':
1042249261Sdim      return 6;
1043249261Sdim    case 'U':
1044249261Sdim      return 10;
1045249261Sdim    case 'x':
1046249261Sdim      return getHexLength(Text);
1047249261Sdim    default:
1048249261Sdim      if (Text[1] >= '0' && Text[1] <= '7')
1049249261Sdim        return getOctalLength(Text);
1050249261Sdim      return 2;
1051249261Sdim    }
1052249261Sdim  }
1053249261Sdim
1054249261Sdim  unsigned getHexLength(StringRef Text) {
1055249261Sdim    unsigned I = 2; // Point after '\x'.
1056249261Sdim    while (I < Text.size() && ((Text[I] >= '0' && Text[I] <= '9') ||
1057249261Sdim                               (Text[I] >= 'a' && Text[I] <= 'f') ||
1058249261Sdim                               (Text[I] >= 'A' && Text[I] <= 'F'))) {
1059249261Sdim      ++I;
1060249261Sdim    }
1061249261Sdim    return I;
1062249261Sdim  }
1063249261Sdim
1064249261Sdim  unsigned getOctalLength(StringRef Text) {
1065249261Sdim    unsigned I = 1;
1066249261Sdim    while (I < Text.size() && I < 4 && (Text[I] >= '0' && Text[I] <= '7')) {
1067249261Sdim      ++I;
1068249261Sdim    }
1069249261Sdim    return I;
1070249261Sdim  }
1071249261Sdim
1072249261Sdim  unsigned getColumnLimit() {
1073249261Sdim    return calculateColumnLimit(Style, Line.InPPDirective);
1074249261Sdim  }
1075249261Sdim
1076249261Sdim  /// \brief An edge in the solution space from \c Previous->State to \c State,
1077249261Sdim  /// inserting a newline dependent on the \c NewLine.
1078249261Sdim  struct StateNode {
1079249261Sdim    StateNode(const LineState &State, bool NewLine, StateNode *Previous)
1080249261Sdim        : State(State), NewLine(NewLine), Previous(Previous) {}
1081249261Sdim    LineState State;
1082249261Sdim    bool NewLine;
1083249261Sdim    StateNode *Previous;
1084249261Sdim  };
1085249261Sdim
1086249261Sdim  /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
1087249261Sdim  ///
1088249261Sdim  /// In case of equal penalties, we want to prefer states that were inserted
1089249261Sdim  /// first. During state generation we make sure that we insert states first
1090249261Sdim  /// that break the line as late as possible.
1091249261Sdim  typedef std::pair<unsigned, unsigned> OrderedPenalty;
1092249261Sdim
1093249261Sdim  /// \brief An item in the prioritized BFS search queue. The \c StateNode's
1094249261Sdim  /// \c State has the given \c OrderedPenalty.
1095249261Sdim  typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
1096249261Sdim
1097249261Sdim  /// \brief The BFS queue type.
1098249261Sdim  typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
1099249261Sdim                              std::greater<QueueItem> > QueueType;
1100249261Sdim
1101249261Sdim  /// \brief Analyze the entire solution space starting from \p InitialState.
1102249261Sdim  ///
1103249261Sdim  /// This implements a variant of Dijkstra's algorithm on the graph that spans
1104249261Sdim  /// the solution space (\c LineStates are the nodes). The algorithm tries to
1105249261Sdim  /// find the shortest path (the one with lowest penalty) from \p InitialState
1106249261Sdim  /// to a state where all tokens are placed.
1107249261Sdim  unsigned analyzeSolutionSpace(LineState &InitialState) {
1108249261Sdim    std::set<LineState> Seen;
1109249261Sdim
1110249261Sdim    // Insert start element into queue.
1111249261Sdim    StateNode *Node =
1112249261Sdim        new (Allocator.Allocate()) StateNode(InitialState, false, NULL);
1113249261Sdim    Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
1114249261Sdim    ++Count;
1115249261Sdim
1116249261Sdim    // While not empty, take first element and follow edges.
1117249261Sdim    while (!Queue.empty()) {
1118249261Sdim      unsigned Penalty = Queue.top().first.first;
1119249261Sdim      StateNode *Node = Queue.top().second;
1120249261Sdim      if (Node->State.NextToken == NULL) {
1121249261Sdim        DEBUG(llvm::errs() << "\n---\nPenalty for line: " << Penalty << "\n");
1122249261Sdim        break;
1123249261Sdim      }
1124249261Sdim      Queue.pop();
1125249261Sdim
1126249261Sdim      if (!Seen.insert(Node->State).second)
1127249261Sdim        // State already examined with lower penalty.
1128249261Sdim        continue;
1129249261Sdim
1130249261Sdim      addNextStateToQueue(Penalty, Node, /*NewLine=*/ false);
1131249261Sdim      addNextStateToQueue(Penalty, Node, /*NewLine=*/ true);
1132249261Sdim    }
1133249261Sdim
1134249261Sdim    if (Queue.empty())
1135249261Sdim      // We were unable to find a solution, do nothing.
1136249261Sdim      // FIXME: Add diagnostic?
1137249261Sdim      return 0;
1138249261Sdim
1139249261Sdim    // Reconstruct the solution.
1140249261Sdim    reconstructPath(InitialState, Queue.top().second);
1141249261Sdim    DEBUG(llvm::errs() << "---\n");
1142249261Sdim
1143249261Sdim    // Return the column after the last token of the solution.
1144249261Sdim    return Queue.top().second->State.Column;
1145249261Sdim  }
1146249261Sdim
1147249261Sdim  void reconstructPath(LineState &State, StateNode *Current) {
1148249261Sdim    // FIXME: This recursive implementation limits the possible number
1149249261Sdim    // of tokens per line if compiled into a binary with small stack space.
1150249261Sdim    // To become more independent of stack frame limitations we would need
1151249261Sdim    // to also change the TokenAnnotator.
1152249261Sdim    if (Current->Previous == NULL)
1153249261Sdim      return;
1154249261Sdim    reconstructPath(State, Current->Previous);
1155249261Sdim    DEBUG({
1156249261Sdim      if (Current->NewLine) {
1157249261Sdim        llvm::errs()
1158249261Sdim            << "Penalty for splitting before "
1159249261Sdim            << Current->Previous->State.NextToken->FormatTok.Tok.getName()
1160249261Sdim            << ": " << Current->Previous->State.NextToken->SplitPenalty << "\n";
1161249261Sdim      }
1162249261Sdim    });
1163249261Sdim    addTokenToState(Current->NewLine, false, State);
1164249261Sdim  }
1165249261Sdim
1166249261Sdim  /// \brief Add the following state to the analysis queue \c Queue.
1167249261Sdim  ///
1168249261Sdim  /// Assume the current state is \p PreviousNode and has been reached with a
1169249261Sdim  /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
1170249261Sdim  void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
1171249261Sdim                           bool NewLine) {
1172249261Sdim    if (NewLine && !canBreak(PreviousNode->State))
1173249261Sdim      return;
1174249261Sdim    if (!NewLine && mustBreak(PreviousNode->State))
1175249261Sdim      return;
1176249261Sdim    if (NewLine)
1177249261Sdim      Penalty += PreviousNode->State.NextToken->SplitPenalty;
1178249261Sdim
1179249261Sdim    StateNode *Node = new (Allocator.Allocate())
1180249261Sdim        StateNode(PreviousNode->State, NewLine, PreviousNode);
1181249261Sdim    Penalty += addTokenToState(NewLine, true, Node->State);
1182249261Sdim    if (Node->State.Column > getColumnLimit()) {
1183249261Sdim      unsigned ExcessCharacters = Node->State.Column - getColumnLimit();
1184249261Sdim      Penalty += Style.PenaltyExcessCharacter * ExcessCharacters;
1185249261Sdim    }
1186249261Sdim
1187249261Sdim    Queue.push(QueueItem(OrderedPenalty(Penalty, Count), Node));
1188249261Sdim    ++Count;
1189249261Sdim  }
1190249261Sdim
1191249261Sdim  /// \brief Returns \c true, if a line break after \p State is allowed.
1192249261Sdim  bool canBreak(const LineState &State) {
1193249261Sdim    if (!State.NextToken->CanBreakBefore &&
1194249261Sdim        !(State.NextToken->is(tok::r_brace) &&
1195249261Sdim          State.Stack.back().BreakBeforeClosingBrace))
1196249261Sdim      return false;
1197249261Sdim    // Trying to insert a parameter on a new line if there are already more than
1198249261Sdim    // one parameter on the current line is bin packing.
1199249261Sdim    if (State.Stack.back().HasMultiParameterLine &&
1200249261Sdim        State.Stack.back().AvoidBinPacking)
1201249261Sdim      return false;
1202249261Sdim    return true;
1203249261Sdim  }
1204249261Sdim
1205249261Sdim  /// \brief Returns \c true, if a line break after \p State is mandatory.
1206249261Sdim  bool mustBreak(const LineState &State) {
1207249261Sdim    if (State.NextToken->MustBreakBefore)
1208249261Sdim      return true;
1209249261Sdim    if (State.NextToken->is(tok::r_brace) &&
1210249261Sdim        State.Stack.back().BreakBeforeClosingBrace)
1211249261Sdim      return true;
1212249261Sdim    if (State.NextToken->Parent->is(tok::semi) &&
1213249261Sdim        State.LineContainsContinuedForLoopSection)
1214249261Sdim      return true;
1215249261Sdim    if ((State.NextToken->Parent->isOneOf(tok::comma, tok::semi) ||
1216249261Sdim         State.NextToken->is(tok::question) ||
1217249261Sdim         State.NextToken->Type == TT_ConditionalExpr) &&
1218249261Sdim        State.Stack.back().BreakBeforeParameter &&
1219249261Sdim        !isTrailingComment(*State.NextToken) &&
1220249261Sdim        State.NextToken->isNot(tok::r_paren) &&
1221249261Sdim        State.NextToken->isNot(tok::r_brace))
1222249261Sdim      return true;
1223249261Sdim    // FIXME: Comparing LongestObjCSelectorName to 0 is a hacky way of finding
1224249261Sdim    // out whether it is the first parameter. Clean this up.
1225249261Sdim    if (State.NextToken->Type == TT_ObjCSelectorName &&
1226249261Sdim        State.NextToken->LongestObjCSelectorName == 0 &&
1227249261Sdim        State.Stack.back().BreakBeforeParameter)
1228249261Sdim      return true;
1229249261Sdim    if ((State.NextToken->Type == TT_CtorInitializerColon ||
1230249261Sdim         (State.NextToken->Parent->ClosesTemplateDeclaration &&
1231249261Sdim          State.ParenLevel == 0)))
1232249261Sdim      return true;
1233249261Sdim    if (State.NextToken->Type == TT_InlineASMColon)
1234249261Sdim      return true;
1235249261Sdim    // This prevents breaks like:
1236249261Sdim    //   ...
1237249261Sdim    //   SomeParameter, OtherParameter).DoSomething(
1238249261Sdim    //   ...
1239249261Sdim    // As they hide "DoSomething" and generally bad for readability.
1240249261Sdim    if (State.NextToken->isOneOf(tok::period, tok::arrow) &&
1241249261Sdim        getRemainingLength(State) + State.Column > getColumnLimit() &&
1242249261Sdim        State.ParenLevel < State.StartOfLineLevel)
1243249261Sdim      return true;
1244249261Sdim    return false;
1245249261Sdim  }
1246249261Sdim
1247249261Sdim  // Returns the total number of columns required for the remaining tokens.
1248249261Sdim  unsigned getRemainingLength(const LineState &State) {
1249249261Sdim    if (State.NextToken && State.NextToken->Parent)
1250249261Sdim      return Line.Last->TotalLength - State.NextToken->Parent->TotalLength;
1251249261Sdim    return 0;
1252249261Sdim  }
1253249261Sdim
1254249261Sdim  FormatStyle Style;
1255249261Sdim  SourceManager &SourceMgr;
1256249261Sdim  const AnnotatedLine &Line;
1257249261Sdim  const unsigned FirstIndent;
1258249261Sdim  const AnnotatedToken &RootToken;
1259249261Sdim  WhitespaceManager &Whitespaces;
1260249261Sdim
1261249261Sdim  llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
1262249261Sdim  QueueType Queue;
1263249261Sdim  // Increasing count of \c StateNode items we have created. This is used
1264249261Sdim  // to create a deterministic order independent of the container.
1265249261Sdim  unsigned Count;
1266249261Sdim};
1267249261Sdim
1268249261Sdimclass LexerBasedFormatTokenSource : public FormatTokenSource {
1269249261Sdimpublic:
1270249261Sdim  LexerBasedFormatTokenSource(Lexer &Lex, SourceManager &SourceMgr)
1271249261Sdim      : GreaterStashed(false), Lex(Lex), SourceMgr(SourceMgr),
1272249261Sdim        IdentTable(Lex.getLangOpts()) {
1273249261Sdim    Lex.SetKeepWhitespaceMode(true);
1274249261Sdim  }
1275249261Sdim
1276249261Sdim  virtual FormatToken getNextToken() {
1277249261Sdim    if (GreaterStashed) {
1278249261Sdim      FormatTok.NewlinesBefore = 0;
1279249261Sdim      FormatTok.WhiteSpaceStart =
1280249261Sdim          FormatTok.Tok.getLocation().getLocWithOffset(1);
1281249261Sdim      FormatTok.WhiteSpaceLength = 0;
1282249261Sdim      GreaterStashed = false;
1283249261Sdim      return FormatTok;
1284249261Sdim    }
1285249261Sdim
1286249261Sdim    FormatTok = FormatToken();
1287249261Sdim    Lex.LexFromRawLexer(FormatTok.Tok);
1288249261Sdim    StringRef Text = rawTokenText(FormatTok.Tok);
1289249261Sdim    FormatTok.WhiteSpaceStart = FormatTok.Tok.getLocation();
1290249261Sdim    if (SourceMgr.getFileOffset(FormatTok.WhiteSpaceStart) == 0)
1291249261Sdim      FormatTok.IsFirst = true;
1292249261Sdim
1293249261Sdim    // Consume and record whitespace until we find a significant token.
1294249261Sdim    while (FormatTok.Tok.is(tok::unknown)) {
1295249261Sdim      unsigned Newlines = Text.count('\n');
1296249261Sdim      if (Newlines > 0)
1297249261Sdim        FormatTok.LastNewlineOffset =
1298249261Sdim            FormatTok.WhiteSpaceLength + Text.rfind('\n') + 1;
1299249261Sdim      unsigned EscapedNewlines = Text.count("\\\n");
1300249261Sdim      FormatTok.NewlinesBefore += Newlines;
1301249261Sdim      FormatTok.HasUnescapedNewline |= EscapedNewlines != Newlines;
1302249261Sdim      FormatTok.WhiteSpaceLength += FormatTok.Tok.getLength();
1303249261Sdim
1304249261Sdim      if (FormatTok.Tok.is(tok::eof))
1305249261Sdim        return FormatTok;
1306249261Sdim      Lex.LexFromRawLexer(FormatTok.Tok);
1307249261Sdim      Text = rawTokenText(FormatTok.Tok);
1308249261Sdim    }
1309249261Sdim
1310249261Sdim    // Now FormatTok is the next non-whitespace token.
1311249261Sdim    FormatTok.TokenLength = Text.size();
1312249261Sdim
1313249261Sdim    // In case the token starts with escaped newlines, we want to
1314249261Sdim    // take them into account as whitespace - this pattern is quite frequent
1315249261Sdim    // in macro definitions.
1316249261Sdim    // FIXME: What do we want to do with other escaped spaces, and escaped
1317249261Sdim    // spaces or newlines in the middle of tokens?
1318249261Sdim    // FIXME: Add a more explicit test.
1319249261Sdim    unsigned i = 0;
1320249261Sdim    while (i + 1 < Text.size() && Text[i] == '\\' && Text[i + 1] == '\n') {
1321249261Sdim      // FIXME: ++FormatTok.NewlinesBefore is missing...
1322249261Sdim      FormatTok.WhiteSpaceLength += 2;
1323249261Sdim      FormatTok.TokenLength -= 2;
1324249261Sdim      i += 2;
1325249261Sdim    }
1326249261Sdim
1327249261Sdim    if (FormatTok.Tok.is(tok::raw_identifier)) {
1328249261Sdim      IdentifierInfo &Info = IdentTable.get(Text);
1329249261Sdim      FormatTok.Tok.setIdentifierInfo(&Info);
1330249261Sdim      FormatTok.Tok.setKind(Info.getTokenID());
1331249261Sdim    }
1332249261Sdim
1333249261Sdim    if (FormatTok.Tok.is(tok::greatergreater)) {
1334249261Sdim      FormatTok.Tok.setKind(tok::greater);
1335249261Sdim      FormatTok.TokenLength = 1;
1336249261Sdim      GreaterStashed = true;
1337249261Sdim    }
1338249261Sdim
1339249261Sdim    // If we reformat comments, we remove trailing whitespace. Update the length
1340249261Sdim    // accordingly.
1341249261Sdim    if (FormatTok.Tok.is(tok::comment))
1342249261Sdim      FormatTok.TokenLength = Text.rtrim().size();
1343249261Sdim
1344249261Sdim    return FormatTok;
1345249261Sdim  }
1346249261Sdim
1347249261Sdim  IdentifierTable &getIdentTable() { return IdentTable; }
1348249261Sdim
1349249261Sdimprivate:
1350249261Sdim  FormatToken FormatTok;
1351249261Sdim  bool GreaterStashed;
1352249261Sdim  Lexer &Lex;
1353249261Sdim  SourceManager &SourceMgr;
1354249261Sdim  IdentifierTable IdentTable;
1355249261Sdim
1356249261Sdim  /// Returns the text of \c FormatTok.
1357249261Sdim  StringRef rawTokenText(Token &Tok) {
1358249261Sdim    return StringRef(SourceMgr.getCharacterData(Tok.getLocation()),
1359249261Sdim                     Tok.getLength());
1360249261Sdim  }
1361249261Sdim};
1362249261Sdim
1363249261Sdimclass Formatter : public UnwrappedLineConsumer {
1364249261Sdimpublic:
1365249261Sdim  Formatter(DiagnosticsEngine &Diag, const FormatStyle &Style, Lexer &Lex,
1366249261Sdim            SourceManager &SourceMgr,
1367249261Sdim            const std::vector<CharSourceRange> &Ranges)
1368249261Sdim      : Diag(Diag), Style(Style), Lex(Lex), SourceMgr(SourceMgr),
1369249261Sdim        Whitespaces(SourceMgr, Style), Ranges(Ranges) {}
1370249261Sdim
1371249261Sdim  virtual ~Formatter() {}
1372249261Sdim
1373249261Sdim  tooling::Replacements format() {
1374249261Sdim    LexerBasedFormatTokenSource Tokens(Lex, SourceMgr);
1375249261Sdim    UnwrappedLineParser Parser(Diag, Style, Tokens, *this);
1376249261Sdim    StructuralError = Parser.parse();
1377249261Sdim    unsigned PreviousEndOfLineColumn = 0;
1378249261Sdim    TokenAnnotator Annotator(Style, SourceMgr, Lex,
1379249261Sdim                             Tokens.getIdentTable().get("in"));
1380249261Sdim    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1381249261Sdim      Annotator.annotate(AnnotatedLines[i]);
1382249261Sdim    }
1383249261Sdim    deriveLocalStyle();
1384249261Sdim    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1385249261Sdim      Annotator.calculateFormattingInformation(AnnotatedLines[i]);
1386249261Sdim
1387249261Sdim      // Adapt level to the next line if this is a comment.
1388249261Sdim      // FIXME: Can/should this be done in the UnwrappedLineParser?
1389249261Sdim      if (i + 1 != e && AnnotatedLines[i].First.is(tok::comment) &&
1390249261Sdim          AnnotatedLines[i].First.Children.empty() &&
1391249261Sdim          AnnotatedLines[i + 1].First.isNot(tok::r_brace))
1392249261Sdim        AnnotatedLines[i].Level = AnnotatedLines[i + 1].Level;
1393249261Sdim    }
1394249261Sdim    std::vector<int> IndentForLevel;
1395249261Sdim    bool PreviousLineWasTouched = false;
1396249261Sdim    const AnnotatedToken *PreviousLineLastToken = 0;
1397249261Sdim    for (std::vector<AnnotatedLine>::iterator I = AnnotatedLines.begin(),
1398249261Sdim                                              E = AnnotatedLines.end();
1399249261Sdim         I != E; ++I) {
1400249261Sdim      const AnnotatedLine &TheLine = *I;
1401249261Sdim      const FormatToken &FirstTok = TheLine.First.FormatTok;
1402249261Sdim      int Offset = getIndentOffset(TheLine.First);
1403249261Sdim      while (IndentForLevel.size() <= TheLine.Level)
1404249261Sdim        IndentForLevel.push_back(-1);
1405249261Sdim      IndentForLevel.resize(TheLine.Level + 1);
1406249261Sdim      bool WasMoved = PreviousLineWasTouched && FirstTok.NewlinesBefore == 0;
1407249261Sdim      if (TheLine.First.is(tok::eof)) {
1408249261Sdim        if (PreviousLineWasTouched) {
1409249261Sdim          unsigned NewLines = std::min(FirstTok.NewlinesBefore, 1u);
1410249261Sdim          Whitespaces.replaceWhitespace(TheLine.First, NewLines, /*Indent*/ 0,
1411249261Sdim                                        /*WhitespaceStartColumn*/ 0);
1412249261Sdim        }
1413249261Sdim      } else if (TheLine.Type != LT_Invalid &&
1414249261Sdim                 (WasMoved || touchesLine(TheLine))) {
1415249261Sdim        unsigned LevelIndent = getIndent(IndentForLevel, TheLine.Level);
1416249261Sdim        unsigned Indent = LevelIndent;
1417249261Sdim        if (static_cast<int>(Indent) + Offset >= 0)
1418249261Sdim          Indent += Offset;
1419249261Sdim        if (!FirstTok.WhiteSpaceStart.isValid() || StructuralError) {
1420249261Sdim          Indent = LevelIndent =
1421249261Sdim              SourceMgr.getSpellingColumnNumber(FirstTok.Tok.getLocation()) - 1;
1422249261Sdim        } else {
1423249261Sdim          formatFirstToken(TheLine.First, PreviousLineLastToken, Indent,
1424249261Sdim                           TheLine.InPPDirective, PreviousEndOfLineColumn);
1425249261Sdim        }
1426249261Sdim        tryFitMultipleLinesInOne(Indent, I, E);
1427249261Sdim        UnwrappedLineFormatter Formatter(Style, SourceMgr, TheLine, Indent,
1428249261Sdim                                         TheLine.First, Whitespaces,
1429249261Sdim                                         StructuralError);
1430249261Sdim        PreviousEndOfLineColumn =
1431249261Sdim            Formatter.format(I + 1 != E ? &*(I + 1) : NULL);
1432249261Sdim        IndentForLevel[TheLine.Level] = LevelIndent;
1433249261Sdim        PreviousLineWasTouched = true;
1434249261Sdim      } else {
1435249261Sdim        if (FirstTok.NewlinesBefore > 0 || FirstTok.IsFirst) {
1436249261Sdim          unsigned Indent =
1437249261Sdim              SourceMgr.getSpellingColumnNumber(FirstTok.Tok.getLocation()) - 1;
1438249261Sdim          unsigned LevelIndent = Indent;
1439249261Sdim          if (static_cast<int>(LevelIndent) - Offset >= 0)
1440249261Sdim            LevelIndent -= Offset;
1441249261Sdim          if (TheLine.First.isNot(tok::comment))
1442249261Sdim            IndentForLevel[TheLine.Level] = LevelIndent;
1443249261Sdim
1444249261Sdim          // Remove trailing whitespace of the previous line if it was touched.
1445249261Sdim          if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine))
1446249261Sdim            formatFirstToken(TheLine.First, PreviousLineLastToken, Indent,
1447249261Sdim                             TheLine.InPPDirective, PreviousEndOfLineColumn);
1448249261Sdim        }
1449249261Sdim        // If we did not reformat this unwrapped line, the column at the end of
1450249261Sdim        // the last token is unchanged - thus, we can calculate the end of the
1451249261Sdim        // last token.
1452249261Sdim        SourceLocation LastLoc = TheLine.Last->FormatTok.Tok.getLocation();
1453249261Sdim        PreviousEndOfLineColumn =
1454249261Sdim            SourceMgr.getSpellingColumnNumber(LastLoc) +
1455249261Sdim            Lex.MeasureTokenLength(LastLoc, SourceMgr, Lex.getLangOpts()) - 1;
1456249261Sdim        PreviousLineWasTouched = false;
1457249261Sdim        if (TheLine.Last->is(tok::comment))
1458249261Sdim          Whitespaces.addUntouchableComment(SourceMgr.getSpellingColumnNumber(
1459249261Sdim              TheLine.Last->FormatTok.Tok.getLocation()) - 1);
1460249261Sdim      }
1461249261Sdim      PreviousLineLastToken = I->Last;
1462249261Sdim    }
1463249261Sdim    return Whitespaces.generateReplacements();
1464249261Sdim  }
1465249261Sdim
1466249261Sdimprivate:
1467249261Sdim  void deriveLocalStyle() {
1468249261Sdim    unsigned CountBoundToVariable = 0;
1469249261Sdim    unsigned CountBoundToType = 0;
1470249261Sdim    bool HasCpp03IncompatibleFormat = false;
1471249261Sdim    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1472249261Sdim      if (AnnotatedLines[i].First.Children.empty())
1473249261Sdim        continue;
1474249261Sdim      AnnotatedToken *Tok = &AnnotatedLines[i].First.Children[0];
1475249261Sdim      while (!Tok->Children.empty()) {
1476249261Sdim        if (Tok->Type == TT_PointerOrReference) {
1477249261Sdim          bool SpacesBefore = Tok->FormatTok.WhiteSpaceLength > 0;
1478249261Sdim          bool SpacesAfter = Tok->Children[0].FormatTok.WhiteSpaceLength > 0;
1479249261Sdim          if (SpacesBefore && !SpacesAfter)
1480249261Sdim            ++CountBoundToVariable;
1481249261Sdim          else if (!SpacesBefore && SpacesAfter)
1482249261Sdim            ++CountBoundToType;
1483249261Sdim        }
1484249261Sdim
1485249261Sdim        if (Tok->Type == TT_TemplateCloser &&
1486249261Sdim            Tok->Parent->Type == TT_TemplateCloser &&
1487249261Sdim            Tok->FormatTok.WhiteSpaceLength == 0)
1488249261Sdim          HasCpp03IncompatibleFormat = true;
1489249261Sdim        Tok = &Tok->Children[0];
1490249261Sdim      }
1491249261Sdim    }
1492249261Sdim    if (Style.DerivePointerBinding) {
1493249261Sdim      if (CountBoundToType > CountBoundToVariable)
1494249261Sdim        Style.PointerBindsToType = true;
1495249261Sdim      else if (CountBoundToType < CountBoundToVariable)
1496249261Sdim        Style.PointerBindsToType = false;
1497249261Sdim    }
1498249261Sdim    if (Style.Standard == FormatStyle::LS_Auto) {
1499249261Sdim      Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
1500249261Sdim                                                  : FormatStyle::LS_Cpp03;
1501249261Sdim    }
1502249261Sdim  }
1503249261Sdim
1504249261Sdim  /// \brief Get the indent of \p Level from \p IndentForLevel.
1505249261Sdim  ///
1506249261Sdim  /// \p IndentForLevel must contain the indent for the level \c l
1507249261Sdim  /// at \p IndentForLevel[l], or a value < 0 if the indent for
1508249261Sdim  /// that level is unknown.
1509249261Sdim  unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
1510249261Sdim    if (IndentForLevel[Level] != -1)
1511249261Sdim      return IndentForLevel[Level];
1512249261Sdim    if (Level == 0)
1513249261Sdim      return 0;
1514249261Sdim    return getIndent(IndentForLevel, Level - 1) + 2;
1515249261Sdim  }
1516249261Sdim
1517249261Sdim  /// \brief Get the offset of the line relatively to the level.
1518249261Sdim  ///
1519249261Sdim  /// For example, 'public:' labels in classes are offset by 1 or 2
1520249261Sdim  /// characters to the left from their level.
1521249261Sdim  int getIndentOffset(const AnnotatedToken &RootToken) {
1522249261Sdim    if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
1523249261Sdim      return Style.AccessModifierOffset;
1524249261Sdim    return 0;
1525249261Sdim  }
1526249261Sdim
1527249261Sdim  /// \brief Tries to merge lines into one.
1528249261Sdim  ///
1529249261Sdim  /// This will change \c Line and \c AnnotatedLine to contain the merged line,
1530249261Sdim  /// if possible; note that \c I will be incremented when lines are merged.
1531249261Sdim  ///
1532249261Sdim  /// Returns whether the resulting \c Line can fit in a single line.
1533249261Sdim  void tryFitMultipleLinesInOne(unsigned Indent,
1534249261Sdim                                std::vector<AnnotatedLine>::iterator &I,
1535249261Sdim                                std::vector<AnnotatedLine>::iterator E) {
1536249261Sdim    // We can never merge stuff if there are trailing line comments.
1537249261Sdim    if (I->Last->Type == TT_LineComment)
1538249261Sdim      return;
1539249261Sdim
1540249261Sdim    unsigned Limit = Style.ColumnLimit - Indent;
1541249261Sdim    // If we already exceed the column limit, we set 'Limit' to 0. The different
1542249261Sdim    // tryMerge..() functions can then decide whether to still do merging.
1543249261Sdim    Limit = I->Last->TotalLength > Limit ? 0 : Limit - I->Last->TotalLength;
1544249261Sdim
1545249261Sdim    if (I + 1 == E || (I + 1)->Type == LT_Invalid)
1546249261Sdim      return;
1547249261Sdim
1548249261Sdim    if (I->Last->is(tok::l_brace)) {
1549249261Sdim      tryMergeSimpleBlock(I, E, Limit);
1550249261Sdim    } else if (I->First.is(tok::kw_if)) {
1551249261Sdim      tryMergeSimpleIf(I, E, Limit);
1552249261Sdim    } else if (I->InPPDirective && (I->First.FormatTok.HasUnescapedNewline ||
1553249261Sdim                                    I->First.FormatTok.IsFirst)) {
1554249261Sdim      tryMergeSimplePPDirective(I, E, Limit);
1555249261Sdim    }
1556249261Sdim    return;
1557249261Sdim  }
1558249261Sdim
1559249261Sdim  void tryMergeSimplePPDirective(std::vector<AnnotatedLine>::iterator &I,
1560249261Sdim                                 std::vector<AnnotatedLine>::iterator E,
1561249261Sdim                                 unsigned Limit) {
1562249261Sdim    if (Limit == 0)
1563249261Sdim      return;
1564249261Sdim    AnnotatedLine &Line = *I;
1565249261Sdim    if (!(I + 1)->InPPDirective || (I + 1)->First.FormatTok.HasUnescapedNewline)
1566249261Sdim      return;
1567249261Sdim    if (I + 2 != E && (I + 2)->InPPDirective &&
1568249261Sdim        !(I + 2)->First.FormatTok.HasUnescapedNewline)
1569249261Sdim      return;
1570249261Sdim    if (1 + (I + 1)->Last->TotalLength > Limit)
1571249261Sdim      return;
1572249261Sdim    join(Line, *(++I));
1573249261Sdim  }
1574249261Sdim
1575249261Sdim  void tryMergeSimpleIf(std::vector<AnnotatedLine>::iterator &I,
1576249261Sdim                        std::vector<AnnotatedLine>::iterator E,
1577249261Sdim                        unsigned Limit) {
1578249261Sdim    if (Limit == 0)
1579249261Sdim      return;
1580249261Sdim    if (!Style.AllowShortIfStatementsOnASingleLine)
1581249261Sdim      return;
1582249261Sdim    if ((I + 1)->InPPDirective != I->InPPDirective ||
1583249261Sdim        ((I + 1)->InPPDirective &&
1584249261Sdim         (I + 1)->First.FormatTok.HasUnescapedNewline))
1585249261Sdim      return;
1586249261Sdim    AnnotatedLine &Line = *I;
1587249261Sdim    if (Line.Last->isNot(tok::r_paren))
1588249261Sdim      return;
1589249261Sdim    if (1 + (I + 1)->Last->TotalLength > Limit)
1590249261Sdim      return;
1591249261Sdim    if ((I + 1)->First.is(tok::kw_if) || (I + 1)->First.Type == TT_LineComment)
1592249261Sdim      return;
1593249261Sdim    // Only inline simple if's (no nested if or else).
1594249261Sdim    if (I + 2 != E && (I + 2)->First.is(tok::kw_else))
1595249261Sdim      return;
1596249261Sdim    join(Line, *(++I));
1597249261Sdim  }
1598249261Sdim
1599249261Sdim  void tryMergeSimpleBlock(std::vector<AnnotatedLine>::iterator &I,
1600249261Sdim                           std::vector<AnnotatedLine>::iterator E,
1601249261Sdim                           unsigned Limit) {
1602249261Sdim    // First, check that the current line allows merging. This is the case if
1603249261Sdim    // we're not in a control flow statement and the last token is an opening
1604249261Sdim    // brace.
1605249261Sdim    AnnotatedLine &Line = *I;
1606249261Sdim    if (Line.First.isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace,
1607249261Sdim                           tok::kw_else, tok::kw_try, tok::kw_catch,
1608249261Sdim                           tok::kw_for,
1609249261Sdim                           // This gets rid of all ObjC @ keywords and methods.
1610249261Sdim                           tok::at, tok::minus, tok::plus))
1611249261Sdim      return;
1612249261Sdim
1613249261Sdim    AnnotatedToken *Tok = &(I + 1)->First;
1614249261Sdim    if (Tok->Children.empty() && Tok->is(tok::r_brace) &&
1615249261Sdim        !Tok->MustBreakBefore) {
1616249261Sdim      // We merge empty blocks even if the line exceeds the column limit.
1617249261Sdim      Tok->SpacesRequiredBefore = 0;
1618249261Sdim      Tok->CanBreakBefore = true;
1619249261Sdim      join(Line, *(I + 1));
1620249261Sdim      I += 1;
1621249261Sdim    } else if (Limit != 0) {
1622249261Sdim      // Check that we still have three lines and they fit into the limit.
1623249261Sdim      if (I + 2 == E || (I + 2)->Type == LT_Invalid ||
1624249261Sdim          !nextTwoLinesFitInto(I, Limit))
1625249261Sdim        return;
1626249261Sdim
1627249261Sdim      // Second, check that the next line does not contain any braces - if it
1628249261Sdim      // does, readability declines when putting it into a single line.
1629249261Sdim      if ((I + 1)->Last->Type == TT_LineComment || Tok->MustBreakBefore)
1630249261Sdim        return;
1631249261Sdim      do {
1632249261Sdim        if (Tok->isOneOf(tok::l_brace, tok::r_brace))
1633249261Sdim          return;
1634249261Sdim        Tok = Tok->Children.empty() ? NULL : &Tok->Children.back();
1635249261Sdim      } while (Tok != NULL);
1636249261Sdim
1637249261Sdim      // Last, check that the third line contains a single closing brace.
1638249261Sdim      Tok = &(I + 2)->First;
1639249261Sdim      if (!Tok->Children.empty() || Tok->isNot(tok::r_brace) ||
1640249261Sdim          Tok->MustBreakBefore)
1641249261Sdim        return;
1642249261Sdim
1643249261Sdim      join(Line, *(I + 1));
1644249261Sdim      join(Line, *(I + 2));
1645249261Sdim      I += 2;
1646249261Sdim    }
1647249261Sdim  }
1648249261Sdim
1649249261Sdim  bool nextTwoLinesFitInto(std::vector<AnnotatedLine>::iterator I,
1650249261Sdim                           unsigned Limit) {
1651249261Sdim    return 1 + (I + 1)->Last->TotalLength + 1 + (I + 2)->Last->TotalLength <=
1652249261Sdim           Limit;
1653249261Sdim  }
1654249261Sdim
1655249261Sdim  void join(AnnotatedLine &A, const AnnotatedLine &B) {
1656249261Sdim    unsigned LengthA = A.Last->TotalLength + B.First.SpacesRequiredBefore;
1657249261Sdim    A.Last->Children.push_back(B.First);
1658249261Sdim    while (!A.Last->Children.empty()) {
1659249261Sdim      A.Last->Children[0].Parent = A.Last;
1660249261Sdim      A.Last->Children[0].TotalLength += LengthA;
1661249261Sdim      A.Last = &A.Last->Children[0];
1662249261Sdim    }
1663249261Sdim  }
1664249261Sdim
1665249261Sdim  bool touchesRanges(const CharSourceRange &Range) {
1666249261Sdim    for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1667249261Sdim      if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),
1668249261Sdim                                               Ranges[i].getBegin()) &&
1669249261Sdim          !SourceMgr.isBeforeInTranslationUnit(Ranges[i].getEnd(),
1670249261Sdim                                               Range.getBegin()))
1671249261Sdim        return true;
1672249261Sdim    }
1673249261Sdim    return false;
1674249261Sdim  }
1675249261Sdim
1676249261Sdim  bool touchesLine(const AnnotatedLine &TheLine) {
1677249261Sdim    const FormatToken *First = &TheLine.First.FormatTok;
1678249261Sdim    const FormatToken *Last = &TheLine.Last->FormatTok;
1679249261Sdim    CharSourceRange LineRange = CharSourceRange::getTokenRange(
1680249261Sdim        First->WhiteSpaceStart.getLocWithOffset(First->LastNewlineOffset),
1681249261Sdim        Last->Tok.getLocation());
1682249261Sdim    return touchesRanges(LineRange);
1683249261Sdim  }
1684249261Sdim
1685249261Sdim  bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) {
1686249261Sdim    const FormatToken *First = &TheLine.First.FormatTok;
1687249261Sdim    CharSourceRange LineRange = CharSourceRange::getCharRange(
1688249261Sdim        First->WhiteSpaceStart,
1689249261Sdim        First->WhiteSpaceStart.getLocWithOffset(First->LastNewlineOffset));
1690249261Sdim    return touchesRanges(LineRange);
1691249261Sdim  }
1692249261Sdim
1693249261Sdim  virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
1694249261Sdim    AnnotatedLines.push_back(AnnotatedLine(TheLine));
1695249261Sdim  }
1696249261Sdim
1697249261Sdim  /// \brief Add a new line and the required indent before the first Token
1698249261Sdim  /// of the \c UnwrappedLine if there was no structural parsing error.
1699249261Sdim  /// Returns the indent level of the \c UnwrappedLine.
1700249261Sdim  void formatFirstToken(const AnnotatedToken &RootToken,
1701249261Sdim                        const AnnotatedToken *PreviousToken, unsigned Indent,
1702249261Sdim                        bool InPPDirective, unsigned PreviousEndOfLineColumn) {
1703249261Sdim    const FormatToken &Tok = RootToken.FormatTok;
1704249261Sdim
1705249261Sdim    unsigned Newlines =
1706249261Sdim        std::min(Tok.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
1707249261Sdim    if (Newlines == 0 && !Tok.IsFirst)
1708249261Sdim      Newlines = 1;
1709249261Sdim
1710249261Sdim    if (!InPPDirective || Tok.HasUnescapedNewline) {
1711249261Sdim      // Insert extra new line before access specifiers.
1712249261Sdim      if (PreviousToken && PreviousToken->isOneOf(tok::semi, tok::r_brace) &&
1713249261Sdim          RootToken.isAccessSpecifier() && Tok.NewlinesBefore == 1)
1714249261Sdim        ++Newlines;
1715249261Sdim
1716249261Sdim      Whitespaces.replaceWhitespace(RootToken, Newlines, Indent, 0);
1717249261Sdim    } else {
1718249261Sdim      Whitespaces.replacePPWhitespace(RootToken, Newlines, Indent,
1719249261Sdim                                      PreviousEndOfLineColumn);
1720249261Sdim    }
1721249261Sdim  }
1722249261Sdim
1723249261Sdim  DiagnosticsEngine &Diag;
1724249261Sdim  FormatStyle Style;
1725249261Sdim  Lexer &Lex;
1726249261Sdim  SourceManager &SourceMgr;
1727249261Sdim  WhitespaceManager Whitespaces;
1728249261Sdim  std::vector<CharSourceRange> Ranges;
1729249261Sdim  std::vector<AnnotatedLine> AnnotatedLines;
1730249261Sdim  bool StructuralError;
1731249261Sdim};
1732249261Sdim
1733249261Sdimtooling::Replacements
1734249261Sdimreformat(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
1735249261Sdim         std::vector<CharSourceRange> Ranges, DiagnosticConsumer *DiagClient) {
1736249261Sdim  IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts = new DiagnosticOptions();
1737249261Sdim  OwningPtr<DiagnosticConsumer> DiagPrinter;
1738249261Sdim  if (DiagClient == 0) {
1739249261Sdim    DiagPrinter.reset(new TextDiagnosticPrinter(llvm::errs(), &*DiagOpts));
1740249261Sdim    DiagPrinter->BeginSourceFile(Lex.getLangOpts(), Lex.getPP());
1741249261Sdim    DiagClient = DiagPrinter.get();
1742249261Sdim  }
1743249261Sdim  DiagnosticsEngine Diagnostics(
1744249261Sdim      IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs()), &*DiagOpts,
1745249261Sdim      DiagClient, false);
1746249261Sdim  Diagnostics.setSourceManager(&SourceMgr);
1747249261Sdim  Formatter formatter(Diagnostics, Style, Lex, SourceMgr, Ranges);
1748249261Sdim  return formatter.format();
1749249261Sdim}
1750249261Sdim
1751249261SdimLangOptions getFormattingLangOpts() {
1752249261Sdim  LangOptions LangOpts;
1753249261Sdim  LangOpts.CPlusPlus = 1;
1754249261Sdim  LangOpts.CPlusPlus11 = 1;
1755249261Sdim  LangOpts.LineComment = 1;
1756249261Sdim  LangOpts.Bool = 1;
1757249261Sdim  LangOpts.ObjC1 = 1;
1758249261Sdim  LangOpts.ObjC2 = 1;
1759249261Sdim  return LangOpts;
1760249261Sdim}
1761249261Sdim
1762249261Sdim} // namespace format
1763249261Sdim} // namespace clang
1764