1 //===--- LeftRightQualifierAlignmentFixer.cpp -------------------*- C++--*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This file implements LeftRightQualifierAlignmentFixer, a TokenAnalyzer that
11 /// enforces either left or right const depending on the style.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #include "QualifierAlignmentFixer.h"
16 #include "FormatToken.h"
17 #include "llvm/Support/Debug.h"
18 #include "llvm/Support/Regex.h"
19 
20 #include <algorithm>
21 
22 #define DEBUG_TYPE "format-qualifier-alignment-fixer"
23 
24 namespace clang {
25 namespace format {
26 
27 QualifierAlignmentFixer::QualifierAlignmentFixer(
28     const Environment &Env, const FormatStyle &Style, StringRef &Code,
29     ArrayRef<tooling::Range> Ranges, unsigned FirstStartColumn,
30     unsigned NextStartColumn, unsigned LastStartColumn, StringRef FileName)
31     : TokenAnalyzer(Env, Style), Code(Code), Ranges(Ranges),
32       FirstStartColumn(FirstStartColumn), NextStartColumn(NextStartColumn),
33       LastStartColumn(LastStartColumn), FileName(FileName) {
34   std::vector<std::string> LeftOrder;
35   std::vector<std::string> RightOrder;
36   std::vector<tok::TokenKind> ConfiguredQualifierTokens;
37   PrepareLeftRightOrdering(Style.QualifierOrder, LeftOrder, RightOrder,
38                            ConfiguredQualifierTokens);
39 
40   // Handle the left and right alignment separately.
41   for (const auto &Qualifier : LeftOrder) {
42     Passes.emplace_back(
43         [&, Qualifier, ConfiguredQualifierTokens](const Environment &Env) {
44           return LeftRightQualifierAlignmentFixer(Env, Style, Qualifier,
45                                                   ConfiguredQualifierTokens,
46                                                   /*RightAlign=*/false)
47               .process();
48         });
49   }
50   for (const auto &Qualifier : RightOrder) {
51     Passes.emplace_back(
52         [&, Qualifier, ConfiguredQualifierTokens](const Environment &Env) {
53           return LeftRightQualifierAlignmentFixer(Env, Style, Qualifier,
54                                                   ConfiguredQualifierTokens,
55                                                   /*RightAlign=*/true)
56               .process();
57         });
58   }
59 }
60 
61 std::pair<tooling::Replacements, unsigned> QualifierAlignmentFixer::analyze(
62     TokenAnnotator & /*Annotator*/,
63     SmallVectorImpl<AnnotatedLine *> & /*AnnotatedLines*/,
64     FormatTokenLexer & /*Tokens*/) {
65   auto Env = Environment::make(Code, FileName, Ranges, FirstStartColumn,
66                                NextStartColumn, LastStartColumn);
67   if (!Env)
68     return {};
69   llvm::Optional<std::string> CurrentCode = None;
70   tooling::Replacements Fixes;
71   for (size_t I = 0, E = Passes.size(); I < E; ++I) {
72     std::pair<tooling::Replacements, unsigned> PassFixes = Passes[I](*Env);
73     auto NewCode = applyAllReplacements(
74         CurrentCode ? StringRef(*CurrentCode) : Code, PassFixes.first);
75     if (NewCode) {
76       Fixes = Fixes.merge(PassFixes.first);
77       if (I + 1 < E) {
78         CurrentCode = std::move(*NewCode);
79         Env = Environment::make(
80             *CurrentCode, FileName,
81             tooling::calculateRangesAfterReplacements(Fixes, Ranges),
82             FirstStartColumn, NextStartColumn, LastStartColumn);
83         if (!Env)
84           return {};
85       }
86     }
87   }
88 
89   // Don't make replacements that replace nothing.
90   tooling::Replacements NonNoOpFixes;
91 
92   for (const tooling::Replacement &Fix : Fixes) {
93     StringRef OriginalCode = Code.substr(Fix.getOffset(), Fix.getLength());
94 
95     if (!OriginalCode.equals(Fix.getReplacementText())) {
96       auto Err = NonNoOpFixes.add(Fix);
97       if (Err)
98         llvm::errs() << "Error adding replacements : "
99                      << llvm::toString(std::move(Err)) << "\n";
100     }
101   }
102   return {NonNoOpFixes, 0};
103 }
104 
105 static void replaceToken(const SourceManager &SourceMgr,
106                          tooling::Replacements &Fixes,
107                          const CharSourceRange &Range, std::string NewText) {
108   auto Replacement = tooling::Replacement(SourceMgr, Range, NewText);
109   auto Err = Fixes.add(Replacement);
110 
111   if (Err)
112     llvm::errs() << "Error while rearranging Qualifier : "
113                  << llvm::toString(std::move(Err)) << "\n";
114 }
115 
116 static void removeToken(const SourceManager &SourceMgr,
117                         tooling::Replacements &Fixes,
118                         const FormatToken *First) {
119   auto Range = CharSourceRange::getCharRange(First->getStartOfNonWhitespace(),
120                                              First->Tok.getEndLoc());
121   replaceToken(SourceMgr, Fixes, Range, "");
122 }
123 
124 static void insertQualifierAfter(const SourceManager &SourceMgr,
125                                  tooling::Replacements &Fixes,
126                                  const FormatToken *First,
127                                  const std::string &Qualifier) {
128   FormatToken *Next = First->Next;
129   if (!Next)
130     return;
131   auto Range = CharSourceRange::getCharRange(Next->getStartOfNonWhitespace(),
132                                              Next->Tok.getEndLoc());
133 
134   std::string NewText = " " + Qualifier + " ";
135   NewText += Next->TokenText;
136   replaceToken(SourceMgr, Fixes, Range, NewText);
137 }
138 
139 static void insertQualifierBefore(const SourceManager &SourceMgr,
140                                   tooling::Replacements &Fixes,
141                                   const FormatToken *First,
142                                   const std::string &Qualifier) {
143   auto Range = CharSourceRange::getCharRange(First->getStartOfNonWhitespace(),
144                                              First->Tok.getEndLoc());
145 
146   std::string NewText = " " + Qualifier + " ";
147   NewText += First->TokenText;
148 
149   replaceToken(SourceMgr, Fixes, Range, NewText);
150 }
151 
152 static bool endsWithSpace(const std::string &s) {
153   if (s.empty())
154     return false;
155   return isspace(s.back());
156 }
157 
158 static bool startsWithSpace(const std::string &s) {
159   if (s.empty())
160     return false;
161   return isspace(s.front());
162 }
163 
164 static void rotateTokens(const SourceManager &SourceMgr,
165                          tooling::Replacements &Fixes, const FormatToken *First,
166                          const FormatToken *Last, bool Left) {
167   auto *End = Last;
168   auto *Begin = First;
169   if (!Left) {
170     End = Last->Next;
171     Begin = First->Next;
172   }
173 
174   std::string NewText;
175   // If we are rotating to the left we move the Last token to the front.
176   if (Left) {
177     NewText += Last->TokenText;
178     NewText += " ";
179   }
180 
181   // Then move through the other tokens.
182   auto *Tok = Begin;
183   while (Tok != End) {
184     if (!NewText.empty() && !endsWithSpace(NewText))
185       NewText += " ";
186 
187     NewText += Tok->TokenText;
188     Tok = Tok->Next;
189   }
190 
191   // If we are rotating to the right we move the first token to the back.
192   if (!Left) {
193     if (!NewText.empty() && !startsWithSpace(NewText))
194       NewText += " ";
195     NewText += First->TokenText;
196   }
197 
198   auto Range = CharSourceRange::getCharRange(First->getStartOfNonWhitespace(),
199                                              Last->Tok.getEndLoc());
200 
201   replaceToken(SourceMgr, Fixes, Range, NewText);
202 }
203 
204 const FormatToken *LeftRightQualifierAlignmentFixer::analyzeRight(
205     const SourceManager &SourceMgr, const AdditionalKeywords &Keywords,
206     tooling::Replacements &Fixes, const FormatToken *Tok,
207     const std::string &Qualifier, tok::TokenKind QualifierType) {
208   // We only need to think about streams that begin with a qualifier.
209   if (!Tok->is(QualifierType))
210     return Tok;
211   // Don't concern yourself if nothing follows the qualifier.
212   if (!Tok->Next)
213     return Tok;
214   if (LeftRightQualifierAlignmentFixer::isPossibleMacro(Tok->Next))
215     return Tok;
216 
217   FormatToken *Qual = Tok->Next;
218   FormatToken *LastQual = Qual;
219   while (Qual && isQualifierOrType(Qual, ConfiguredQualifierTokens)) {
220     LastQual = Qual;
221     Qual = Qual->Next;
222   }
223   if (LastQual && Qual != LastQual) {
224     rotateTokens(SourceMgr, Fixes, Tok, LastQual, /*Left=*/false);
225     Tok = LastQual;
226   } else if (Tok->startsSequence(QualifierType, tok::identifier,
227                                  TT_TemplateCloser)) {
228     FormatToken *Closer = Tok->Next->Next;
229     rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/false);
230     Tok = Closer;
231     return Tok;
232   } else if (Tok->startsSequence(QualifierType, tok::identifier,
233                                  TT_TemplateOpener)) {
234     // Read from the TemplateOpener to
235     // TemplateCloser as in const ArrayRef<int> a; const ArrayRef<int> &a;
236     FormatToken *EndTemplate = Tok->Next->Next->MatchingParen;
237     if (EndTemplate) {
238       // Move to the end of any template class members e.g.
239       // `Foo<int>::iterator`.
240       if (EndTemplate->startsSequence(TT_TemplateCloser, tok::coloncolon,
241                                       tok::identifier))
242         EndTemplate = EndTemplate->Next->Next;
243     }
244     if (EndTemplate && EndTemplate->Next &&
245         !EndTemplate->Next->isOneOf(tok::equal, tok::l_paren)) {
246       insertQualifierAfter(SourceMgr, Fixes, EndTemplate, Qualifier);
247       // Remove the qualifier.
248       removeToken(SourceMgr, Fixes, Tok);
249       return Tok;
250     }
251   } else if (Tok->startsSequence(QualifierType, tok::identifier)) {
252     FormatToken *Next = Tok->Next;
253     // The case  `const Foo` -> `Foo const`
254     // The case  `const Foo *` -> `Foo const *`
255     // The case  `const Foo &` -> `Foo const &`
256     // The case  `const Foo &&` -> `Foo const &&`
257     // The case  `const std::Foo &&` -> `std::Foo const &&`
258     // The case  `const std::Foo<T> &&` -> `std::Foo<T> const &&`
259     while (Next && Next->isOneOf(tok::identifier, tok::coloncolon))
260       Next = Next->Next;
261     if (Next && Next->is(TT_TemplateOpener)) {
262       Next = Next->MatchingParen;
263       // Move to the end of any template class members e.g.
264       // `Foo<int>::iterator`.
265       if (Next && Next->startsSequence(TT_TemplateCloser, tok::coloncolon,
266                                        tok::identifier))
267         return Tok;
268       assert(Next && "Missing template opener");
269       Next = Next->Next;
270     }
271     if (Next && Next->isOneOf(tok::star, tok::amp, tok::ampamp) &&
272         !Tok->Next->isOneOf(Keywords.kw_override, Keywords.kw_final)) {
273       if (Next->Previous && !Next->Previous->is(QualifierType)) {
274         insertQualifierAfter(SourceMgr, Fixes, Next->Previous, Qualifier);
275         removeToken(SourceMgr, Fixes, Tok);
276       }
277       return Next;
278     }
279   }
280 
281   return Tok;
282 }
283 
284 const FormatToken *LeftRightQualifierAlignmentFixer::analyzeLeft(
285     const SourceManager &SourceMgr, const AdditionalKeywords &Keywords,
286     tooling::Replacements &Fixes, const FormatToken *Tok,
287     const std::string &Qualifier, tok::TokenKind QualifierType) {
288   // if Tok is an identifier and possibly a macro then don't convert.
289   if (LeftRightQualifierAlignmentFixer::isPossibleMacro(Tok))
290     return Tok;
291 
292   const FormatToken *Qual = Tok;
293   const FormatToken *LastQual = Qual;
294   while (Qual && isQualifierOrType(Qual, ConfiguredQualifierTokens)) {
295     LastQual = Qual;
296     Qual = Qual->Next;
297     if (Qual && Qual->is(QualifierType))
298       break;
299   }
300 
301   if (!Qual)
302     return Tok;
303 
304   if (LastQual && Qual != LastQual && Qual->is(QualifierType)) {
305     rotateTokens(SourceMgr, Fixes, Tok, Qual, /*Left=*/true);
306     if (!Qual->Next)
307       return Tok;
308     Tok = Qual->Next;
309   } else if (Tok->startsSequence(tok::identifier, QualifierType)) {
310     if (Tok->Next->Next && Tok->Next->Next->isOneOf(tok::identifier, tok::star,
311                                                     tok::amp, tok::ampamp)) {
312       // Don't swap `::iterator const` to `::const iterator`.
313       if (!Tok->Previous ||
314           (Tok->Previous && !Tok->Previous->is(tok::coloncolon))) {
315         rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/true);
316         Tok = Tok->Next;
317       }
318     } else if (Tok->startsSequence(tok::identifier, QualifierType,
319                                    TT_TemplateCloser)) {
320       FormatToken *Closer = Tok->Next->Next;
321       rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/true);
322       Tok = Closer;
323     }
324   }
325   if (Tok->is(TT_TemplateOpener) && Tok->Next &&
326       (Tok->Next->is(tok::identifier) || Tok->Next->isSimpleTypeSpecifier()) &&
327       Tok->Next->Next && Tok->Next->Next->is(QualifierType))
328     rotateTokens(SourceMgr, Fixes, Tok->Next, Tok->Next->Next, /*Left=*/true);
329   if (Tok->startsSequence(tok::identifier) && Tok->Next) {
330     if (Tok->Previous &&
331         Tok->Previous->isOneOf(tok::star, tok::ampamp, tok::amp))
332       return Tok;
333     const FormatToken *Next = Tok->Next;
334     // The case  `std::Foo<T> const` -> `const std::Foo<T> &&`
335     while (Next && Next->isOneOf(tok::identifier, tok::coloncolon))
336       Next = Next->Next;
337     if (Next && Next->Previous &&
338         Next->Previous->startsSequence(tok::identifier, TT_TemplateOpener)) {
339       // Read from to the end of the TemplateOpener to
340       // TemplateCloser const ArrayRef<int> a; const ArrayRef<int> &a;
341       if (Next->is(tok::comment) && Next->getNextNonComment())
342         Next = Next->getNextNonComment();
343       assert(Next->MatchingParen && "Missing template closer");
344       Next = Next->MatchingParen;
345 
346       // If the template closer is closing the requires clause,
347       // then stop and go back to the TemplateOpener and do whatever is
348       // inside the <>.
349       if (Next->ClosesRequiresClause)
350         return Next->MatchingParen;
351       Next = Next->Next;
352 
353       // Move to the end of any template class members e.g.
354       // `Foo<int>::iterator`.
355       if (Next && Next->startsSequence(tok::coloncolon, tok::identifier))
356         Next = Next->Next->Next;
357       if (Next && Next->is(QualifierType)) {
358         // Move the qualifier.
359         insertQualifierBefore(SourceMgr, Fixes, Tok, Qualifier);
360         removeToken(SourceMgr, Fixes, Next);
361         return Next;
362       }
363     }
364     if (Next && Next->Next &&
365         Next->Next->isOneOf(tok::amp, tok::ampamp, tok::star)) {
366       if (Next->is(QualifierType)) {
367         // Move the qualifier.
368         insertQualifierBefore(SourceMgr, Fixes, Tok, Qualifier);
369         removeToken(SourceMgr, Fixes, Next);
370         return Next;
371       }
372     }
373   }
374   return Tok;
375 }
376 
377 tok::TokenKind LeftRightQualifierAlignmentFixer::getTokenFromQualifier(
378     const std::string &Qualifier) {
379   // Don't let 'type' be an identifier, but steal typeof token.
380   return llvm::StringSwitch<tok::TokenKind>(Qualifier)
381       .Case("type", tok::kw_typeof)
382       .Case("const", tok::kw_const)
383       .Case("volatile", tok::kw_volatile)
384       .Case("static", tok::kw_static)
385       .Case("inline", tok::kw_inline)
386       .Case("constexpr", tok::kw_constexpr)
387       .Case("restrict", tok::kw_restrict)
388       .Default(tok::identifier);
389 }
390 
391 LeftRightQualifierAlignmentFixer::LeftRightQualifierAlignmentFixer(
392     const Environment &Env, const FormatStyle &Style,
393     const std::string &Qualifier,
394     const std::vector<tok::TokenKind> &QualifierTokens, bool RightAlign)
395     : TokenAnalyzer(Env, Style), Qualifier(Qualifier), RightAlign(RightAlign),
396       ConfiguredQualifierTokens(QualifierTokens) {}
397 
398 std::pair<tooling::Replacements, unsigned>
399 LeftRightQualifierAlignmentFixer::analyze(
400     TokenAnnotator & /*Annotator*/,
401     SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
402     FormatTokenLexer &Tokens) {
403   tooling::Replacements Fixes;
404   const AdditionalKeywords &Keywords = Tokens.getKeywords();
405   const SourceManager &SourceMgr = Env.getSourceManager();
406   AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
407 
408   tok::TokenKind QualifierToken = getTokenFromQualifier(Qualifier);
409   assert(QualifierToken != tok::identifier && "Unrecognised Qualifier");
410 
411   for (AnnotatedLine *Line : AnnotatedLines) {
412     if (Line->InPPDirective)
413       continue;
414     FormatToken *First = Line->First;
415     assert(First);
416     if (First->Finalized)
417       continue;
418 
419     const auto *Last = Line->Last;
420 
421     for (const auto *Tok = First; Tok && Tok != Last && Tok->Next;
422          Tok = Tok->Next) {
423       if (Tok->is(tok::comment))
424         continue;
425       if (RightAlign)
426         Tok = analyzeRight(SourceMgr, Keywords, Fixes, Tok, Qualifier,
427                            QualifierToken);
428       else
429         Tok = analyzeLeft(SourceMgr, Keywords, Fixes, Tok, Qualifier,
430                           QualifierToken);
431     }
432   }
433   return {Fixes, 0};
434 }
435 
436 void QualifierAlignmentFixer::PrepareLeftRightOrdering(
437     const std::vector<std::string> &Order, std::vector<std::string> &LeftOrder,
438     std::vector<std::string> &RightOrder,
439     std::vector<tok::TokenKind> &Qualifiers) {
440 
441   // Depending on the position of type in the order you need
442   // To iterate forward or backward through the order list as qualifier
443   // can push through each other.
444   // The Order list must define the position of "type" to signify
445   assert(llvm::is_contained(Order, "type") &&
446          "QualifierOrder must contain type");
447   // Split the Order list by type and reverse the left side.
448 
449   bool left = true;
450   for (const auto &s : Order) {
451     if (s == "type") {
452       left = false;
453       continue;
454     }
455 
456     tok::TokenKind QualifierToken =
457         LeftRightQualifierAlignmentFixer::getTokenFromQualifier(s);
458     if (QualifierToken != tok::kw_typeof && QualifierToken != tok::identifier)
459       Qualifiers.push_back(QualifierToken);
460 
461     if (left)
462       // Reverse the order for left aligned items.
463       LeftOrder.insert(LeftOrder.begin(), s);
464     else
465       RightOrder.push_back(s);
466   }
467 }
468 
469 bool LeftRightQualifierAlignmentFixer::isQualifierOrType(
470     const FormatToken *Tok, const std::vector<tok::TokenKind> &specifiedTypes) {
471   return Tok && (Tok->isSimpleTypeSpecifier() || Tok->is(tok::kw_auto) ||
472                  llvm::is_contained(specifiedTypes, Tok->Tok.getKind()));
473 }
474 
475 // If a token is an identifier and it's upper case, it could
476 // be a macro and hence we need to be able to ignore it.
477 bool LeftRightQualifierAlignmentFixer::isPossibleMacro(const FormatToken *Tok) {
478   if (!Tok)
479     return false;
480   if (!Tok->is(tok::identifier))
481     return false;
482   if (Tok->TokenText.upper() == Tok->TokenText.str())
483     // T,K,U,V likely could be template arguments
484     return (Tok->TokenText.size() != 1);
485   return false;
486 }
487 
488 } // namespace format
489 } // namespace clang
490