1 //===--- WhitespaceManager.cpp - Format C++ code --------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief This file implements WhitespaceManager class.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #include "WhitespaceManager.h"
16 #include "llvm/ADT/STLExtras.h"
17 
18 namespace clang {
19 namespace format {
20 
21 bool
22 WhitespaceManager::Change::IsBeforeInFile::operator()(const Change &C1,
23                                                       const Change &C2) const {
24   return SourceMgr.isBeforeInTranslationUnit(
25       C1.OriginalWhitespaceRange.getBegin(),
26       C2.OriginalWhitespaceRange.getBegin());
27 }
28 
29 WhitespaceManager::Change::Change(
30     bool CreateReplacement, const SourceRange &OriginalWhitespaceRange,
31     unsigned IndentLevel, int Spaces, unsigned StartOfTokenColumn,
32     unsigned NewlinesBefore, StringRef PreviousLinePostfix,
33     StringRef CurrentLinePrefix, tok::TokenKind Kind, bool ContinuesPPDirective)
34     : CreateReplacement(CreateReplacement),
35       OriginalWhitespaceRange(OriginalWhitespaceRange),
36       StartOfTokenColumn(StartOfTokenColumn), NewlinesBefore(NewlinesBefore),
37       PreviousLinePostfix(PreviousLinePostfix),
38       CurrentLinePrefix(CurrentLinePrefix), Kind(Kind),
39       ContinuesPPDirective(ContinuesPPDirective), IndentLevel(IndentLevel),
40       Spaces(Spaces) {}
41 
42 void WhitespaceManager::reset() {
43   Changes.clear();
44   Replaces.clear();
45 }
46 
47 void WhitespaceManager::replaceWhitespace(FormatToken &Tok, unsigned Newlines,
48                                           unsigned IndentLevel, unsigned Spaces,
49                                           unsigned StartOfTokenColumn,
50                                           bool InPPDirective) {
51   if (Tok.Finalized)
52     return;
53   Tok.Decision = (Newlines > 0) ? FD_Break : FD_Continue;
54   Changes.push_back(Change(true, Tok.WhitespaceRange, IndentLevel, Spaces,
55                            StartOfTokenColumn, Newlines, "", "",
56                            Tok.Tok.getKind(), InPPDirective && !Tok.IsFirst));
57 }
58 
59 void WhitespaceManager::addUntouchableToken(const FormatToken &Tok,
60                                             bool InPPDirective) {
61   if (Tok.Finalized)
62     return;
63   Changes.push_back(Change(false, Tok.WhitespaceRange, /*IndentLevel=*/0,
64                            /*Spaces=*/0, Tok.OriginalColumn, Tok.NewlinesBefore,
65                            "", "", Tok.Tok.getKind(),
66                            InPPDirective && !Tok.IsFirst));
67 }
68 
69 void WhitespaceManager::replaceWhitespaceInToken(
70     const FormatToken &Tok, unsigned Offset, unsigned ReplaceChars,
71     StringRef PreviousPostfix, StringRef CurrentPrefix, bool InPPDirective,
72     unsigned Newlines, unsigned IndentLevel, int Spaces) {
73   if (Tok.Finalized)
74     return;
75   SourceLocation Start = Tok.getStartOfNonWhitespace().getLocWithOffset(Offset);
76   Changes.push_back(Change(
77       true, SourceRange(Start, Start.getLocWithOffset(ReplaceChars)),
78       IndentLevel, Spaces, std::max(0, Spaces), Newlines, PreviousPostfix,
79       CurrentPrefix,
80       // If we don't add a newline this change doesn't start a comment. Thus,
81       // when we align line comments, we don't need to treat this change as one.
82       // FIXME: We still need to take this change in account to properly
83       // calculate the new length of the comment and to calculate the changes
84       // for which to do the alignment when aligning comments.
85       Tok.Type == TT_LineComment && Newlines > 0 ? tok::comment : tok::unknown,
86       InPPDirective && !Tok.IsFirst));
87 }
88 
89 const tooling::Replacements &WhitespaceManager::generateReplacements() {
90   if (Changes.empty())
91     return Replaces;
92 
93   std::sort(Changes.begin(), Changes.end(), Change::IsBeforeInFile(SourceMgr));
94   calculateLineBreakInformation();
95   alignTrailingComments();
96   alignEscapedNewlines();
97   generateChanges();
98 
99   return Replaces;
100 }
101 
102 void WhitespaceManager::calculateLineBreakInformation() {
103   Changes[0].PreviousEndOfTokenColumn = 0;
104   for (unsigned i = 1, e = Changes.size(); i != e; ++i) {
105     unsigned OriginalWhitespaceStart =
106         SourceMgr.getFileOffset(Changes[i].OriginalWhitespaceRange.getBegin());
107     unsigned PreviousOriginalWhitespaceEnd = SourceMgr.getFileOffset(
108         Changes[i - 1].OriginalWhitespaceRange.getEnd());
109     Changes[i - 1].TokenLength = OriginalWhitespaceStart -
110                                  PreviousOriginalWhitespaceEnd +
111                                  Changes[i].PreviousLinePostfix.size() +
112                                  Changes[i - 1].CurrentLinePrefix.size();
113 
114     Changes[i].PreviousEndOfTokenColumn =
115         Changes[i - 1].StartOfTokenColumn + Changes[i - 1].TokenLength;
116 
117     Changes[i - 1].IsTrailingComment =
118         (Changes[i].NewlinesBefore > 0 || Changes[i].Kind == tok::eof) &&
119         Changes[i - 1].Kind == tok::comment;
120   }
121   // FIXME: The last token is currently not always an eof token; in those
122   // cases, setting TokenLength of the last token to 0 is wrong.
123   Changes.back().TokenLength = 0;
124   Changes.back().IsTrailingComment = Changes.back().Kind == tok::comment;
125 
126   const WhitespaceManager::Change *LastBlockComment = nullptr;
127   for (auto &Change : Changes) {
128     Change.StartOfBlockComment = nullptr;
129     Change.IndentationOffset = 0;
130     if (Change.Kind == tok::comment) {
131       LastBlockComment = &Change;
132     } else if (Change.Kind == tok::unknown) {
133       if ((Change.StartOfBlockComment = LastBlockComment))
134         Change.IndentationOffset =
135             Change.StartOfTokenColumn -
136             Change.StartOfBlockComment->StartOfTokenColumn;
137     } else {
138       LastBlockComment = nullptr;
139     }
140   }
141 }
142 
143 void WhitespaceManager::alignTrailingComments() {
144   unsigned MinColumn = 0;
145   unsigned MaxColumn = UINT_MAX;
146   unsigned StartOfSequence = 0;
147   bool BreakBeforeNext = false;
148   unsigned Newlines = 0;
149   for (unsigned i = 0, e = Changes.size(); i != e; ++i) {
150     if (Changes[i].StartOfBlockComment)
151       continue;
152     Newlines += Changes[i].NewlinesBefore;
153     if (!Changes[i].IsTrailingComment)
154       continue;
155 
156     unsigned ChangeMinColumn = Changes[i].StartOfTokenColumn;
157     // FIXME: Correctly handle ChangeMaxColumn in PP directives.
158     unsigned ChangeMaxColumn = Style.ColumnLimit - Changes[i].TokenLength;
159     // If this comment follows an } in column 0, it probably documents the
160     // closing of a namespace and we don't want to align it.
161     bool FollowsRBraceInColumn0 = i > 0 && Changes[i].NewlinesBefore == 0 &&
162                                   Changes[i - 1].Kind == tok::r_brace &&
163                                   Changes[i - 1].StartOfTokenColumn == 0;
164     bool WasAlignedWithStartOfNextLine = false;
165     if (Changes[i].NewlinesBefore == 1) { // A comment on its own line.
166       for (unsigned j = i + 1; j != e; ++j) {
167         if (Changes[j].Kind != tok::comment) { // Skip over comments.
168           // The start of the next token was previously aligned with the
169           // start of this comment.
170           WasAlignedWithStartOfNextLine =
171               (SourceMgr.getSpellingColumnNumber(
172                    Changes[i].OriginalWhitespaceRange.getEnd()) ==
173                SourceMgr.getSpellingColumnNumber(
174                    Changes[j].OriginalWhitespaceRange.getEnd()));
175           break;
176         }
177       }
178     }
179     if (!Style.AlignTrailingComments || FollowsRBraceInColumn0) {
180       alignTrailingComments(StartOfSequence, i, MinColumn);
181       MinColumn = ChangeMinColumn;
182       MaxColumn = ChangeMinColumn;
183       StartOfSequence = i;
184     } else if (BreakBeforeNext || Newlines > 1 ||
185                (ChangeMinColumn > MaxColumn || ChangeMaxColumn < MinColumn) ||
186                // Break the comment sequence if the previous line did not end
187                // in a trailing comment.
188                (Changes[i].NewlinesBefore == 1 && i > 0 &&
189                 !Changes[i - 1].IsTrailingComment) ||
190                WasAlignedWithStartOfNextLine) {
191       alignTrailingComments(StartOfSequence, i, MinColumn);
192       MinColumn = ChangeMinColumn;
193       MaxColumn = ChangeMaxColumn;
194       StartOfSequence = i;
195     } else {
196       MinColumn = std::max(MinColumn, ChangeMinColumn);
197       MaxColumn = std::min(MaxColumn, ChangeMaxColumn);
198     }
199     BreakBeforeNext =
200         (i == 0) || (Changes[i].NewlinesBefore > 1) ||
201         // Never start a sequence with a comment at the beginning of
202         // the line.
203         (Changes[i].NewlinesBefore == 1 && StartOfSequence == i);
204     Newlines = 0;
205   }
206   alignTrailingComments(StartOfSequence, Changes.size(), MinColumn);
207 }
208 
209 void WhitespaceManager::alignTrailingComments(unsigned Start, unsigned End,
210                                               unsigned Column) {
211   for (unsigned i = Start; i != End; ++i) {
212     int Shift = 0;
213     if (Changes[i].IsTrailingComment) {
214       Shift = Column - Changes[i].StartOfTokenColumn;
215     }
216     if (Changes[i].StartOfBlockComment) {
217       Shift = Changes[i].IndentationOffset +
218               Changes[i].StartOfBlockComment->StartOfTokenColumn -
219               Changes[i].StartOfTokenColumn;
220     }
221     assert(Shift >= 0);
222     Changes[i].Spaces += Shift;
223     if (i + 1 != End)
224       Changes[i + 1].PreviousEndOfTokenColumn += Shift;
225     Changes[i].StartOfTokenColumn += Shift;
226   }
227 }
228 
229 void WhitespaceManager::alignEscapedNewlines() {
230   unsigned MaxEndOfLine =
231       Style.AlignEscapedNewlinesLeft ? 0 : Style.ColumnLimit;
232   unsigned StartOfMacro = 0;
233   for (unsigned i = 1, e = Changes.size(); i < e; ++i) {
234     Change &C = Changes[i];
235     if (C.NewlinesBefore > 0) {
236       if (C.ContinuesPPDirective) {
237         MaxEndOfLine = std::max(C.PreviousEndOfTokenColumn + 2, MaxEndOfLine);
238       } else {
239         alignEscapedNewlines(StartOfMacro + 1, i, MaxEndOfLine);
240         MaxEndOfLine = Style.AlignEscapedNewlinesLeft ? 0 : Style.ColumnLimit;
241         StartOfMacro = i;
242       }
243     }
244   }
245   alignEscapedNewlines(StartOfMacro + 1, Changes.size(), MaxEndOfLine);
246 }
247 
248 void WhitespaceManager::alignEscapedNewlines(unsigned Start, unsigned End,
249                                              unsigned Column) {
250   for (unsigned i = Start; i < End; ++i) {
251     Change &C = Changes[i];
252     if (C.NewlinesBefore > 0) {
253       assert(C.ContinuesPPDirective);
254       if (C.PreviousEndOfTokenColumn + 1 > Column)
255         C.EscapedNewlineColumn = 0;
256       else
257         C.EscapedNewlineColumn = Column;
258     }
259   }
260 }
261 
262 void WhitespaceManager::generateChanges() {
263   for (unsigned i = 0, e = Changes.size(); i != e; ++i) {
264     const Change &C = Changes[i];
265     if (C.CreateReplacement) {
266       std::string ReplacementText = C.PreviousLinePostfix;
267       if (C.ContinuesPPDirective)
268         appendNewlineText(ReplacementText, C.NewlinesBefore,
269                           C.PreviousEndOfTokenColumn, C.EscapedNewlineColumn);
270       else
271         appendNewlineText(ReplacementText, C.NewlinesBefore);
272       appendIndentText(ReplacementText, C.IndentLevel, std::max(0, C.Spaces),
273                        C.StartOfTokenColumn - std::max(0, C.Spaces));
274       ReplacementText.append(C.CurrentLinePrefix);
275       storeReplacement(C.OriginalWhitespaceRange, ReplacementText);
276     }
277   }
278 }
279 
280 void WhitespaceManager::storeReplacement(const SourceRange &Range,
281                                          StringRef Text) {
282   unsigned WhitespaceLength = SourceMgr.getFileOffset(Range.getEnd()) -
283                               SourceMgr.getFileOffset(Range.getBegin());
284   // Don't create a replacement, if it does not change anything.
285   if (StringRef(SourceMgr.getCharacterData(Range.getBegin()),
286                 WhitespaceLength) == Text)
287     return;
288   Replaces.insert(tooling::Replacement(
289       SourceMgr, CharSourceRange::getCharRange(Range), Text));
290 }
291 
292 void WhitespaceManager::appendNewlineText(std::string &Text,
293                                           unsigned Newlines) {
294   for (unsigned i = 0; i < Newlines; ++i)
295     Text.append(UseCRLF ? "\r\n" : "\n");
296 }
297 
298 void WhitespaceManager::appendNewlineText(std::string &Text, unsigned Newlines,
299                                           unsigned PreviousEndOfTokenColumn,
300                                           unsigned EscapedNewlineColumn) {
301   if (Newlines > 0) {
302     unsigned Offset =
303         std::min<int>(EscapedNewlineColumn - 1, PreviousEndOfTokenColumn);
304     for (unsigned i = 0; i < Newlines; ++i) {
305       Text.append(std::string(EscapedNewlineColumn - Offset - 1, ' '));
306       Text.append(UseCRLF ? "\\\r\n" : "\\\n");
307       Offset = 0;
308     }
309   }
310 }
311 
312 void WhitespaceManager::appendIndentText(std::string &Text,
313                                          unsigned IndentLevel, unsigned Spaces,
314                                          unsigned WhitespaceStartColumn) {
315   switch (Style.UseTab) {
316   case FormatStyle::UT_Never:
317     Text.append(std::string(Spaces, ' '));
318     break;
319   case FormatStyle::UT_Always: {
320     unsigned FirstTabWidth =
321         Style.TabWidth - WhitespaceStartColumn % Style.TabWidth;
322     // Indent with tabs only when there's at least one full tab.
323     if (FirstTabWidth + Style.TabWidth <= Spaces) {
324       Spaces -= FirstTabWidth;
325       Text.append("\t");
326     }
327     Text.append(std::string(Spaces / Style.TabWidth, '\t'));
328     Text.append(std::string(Spaces % Style.TabWidth, ' '));
329     break;
330   }
331   case FormatStyle::UT_ForIndentation:
332     if (WhitespaceStartColumn == 0) {
333       unsigned Indentation = IndentLevel * Style.IndentWidth;
334       // This happens, e.g. when a line in a block comment is indented less than
335       // the first one.
336       if (Indentation > Spaces)
337         Indentation = Spaces;
338       unsigned Tabs = Indentation / Style.TabWidth;
339       Text.append(std::string(Tabs, '\t'));
340       Spaces -= Tabs * Style.TabWidth;
341     }
342     Text.append(std::string(Spaces, ' '));
343     break;
344   }
345 }
346 
347 } // namespace format
348 } // namespace clang
349