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