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