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   }
103   return {NonNoOpFixes, 0};
104 }
105 
106 static void replaceToken(const SourceManager &SourceMgr,
107                          tooling::Replacements &Fixes,
108                          const CharSourceRange &Range, std::string NewText) {
109   auto Replacement = tooling::Replacement(SourceMgr, Range, NewText);
110   auto Err = Fixes.add(Replacement);
111 
112   if (Err) {
113     llvm::errs() << "Error while rearranging Qualifier : "
114                  << llvm::toString(std::move(Err)) << "\n";
115   }
116 }
117 
118 static void removeToken(const SourceManager &SourceMgr,
119                         tooling::Replacements &Fixes,
120                         const FormatToken *First) {
121   auto Range = CharSourceRange::getCharRange(First->getStartOfNonWhitespace(),
122                                              First->Tok.getEndLoc());
123   replaceToken(SourceMgr, Fixes, Range, "");
124 }
125 
126 static void insertQualifierAfter(const SourceManager &SourceMgr,
127                                  tooling::Replacements &Fixes,
128                                  const FormatToken *First,
129                                  const std::string &Qualifier) {
130   FormatToken *Next = First->Next;
131   if (!Next)
132     return;
133   auto Range = CharSourceRange::getCharRange(Next->getStartOfNonWhitespace(),
134                                              Next->Tok.getEndLoc());
135 
136   std::string NewText = " " + Qualifier + " ";
137   NewText += Next->TokenText;
138   replaceToken(SourceMgr, Fixes, Range, NewText);
139 }
140 
141 static void insertQualifierBefore(const SourceManager &SourceMgr,
142                                   tooling::Replacements &Fixes,
143                                   const FormatToken *First,
144                                   const std::string &Qualifier) {
145   auto Range = CharSourceRange::getCharRange(First->getStartOfNonWhitespace(),
146                                              First->Tok.getEndLoc());
147 
148   std::string NewText = " " + Qualifier + " ";
149   NewText += First->TokenText;
150 
151   replaceToken(SourceMgr, Fixes, Range, NewText);
152 }
153 
154 static bool endsWithSpace(const std::string &s) {
155   if (s.empty())
156     return false;
157   return isspace(s.back());
158 }
159 
160 static bool startsWithSpace(const std::string &s) {
161   if (s.empty())
162     return false;
163   return isspace(s.front());
164 }
165 
166 static void rotateTokens(const SourceManager &SourceMgr,
167                          tooling::Replacements &Fixes, const FormatToken *First,
168                          const FormatToken *Last, bool Left) {
169   auto *End = Last;
170   auto *Begin = First;
171   if (!Left) {
172     End = Last->Next;
173     Begin = First->Next;
174   }
175 
176   std::string NewText;
177   // If we are rotating to the left we move the Last token to the front.
178   if (Left) {
179     NewText += Last->TokenText;
180     NewText += " ";
181   }
182 
183   // Then move through the other tokens.
184   auto *Tok = Begin;
185   while (Tok != End) {
186     if (!NewText.empty() && !endsWithSpace(NewText))
187       NewText += " ";
188 
189     NewText += Tok->TokenText;
190     Tok = Tok->Next;
191   }
192 
193   // If we are rotating to the right we move the first token to the back.
194   if (!Left) {
195     if (!NewText.empty() && !startsWithSpace(NewText))
196       NewText += " ";
197     NewText += First->TokenText;
198   }
199 
200   auto Range = CharSourceRange::getCharRange(First->getStartOfNonWhitespace(),
201                                              Last->Tok.getEndLoc());
202 
203   replaceToken(SourceMgr, Fixes, Range, NewText);
204 }
205 
206 const FormatToken *LeftRightQualifierAlignmentFixer::analyzeRight(
207     const SourceManager &SourceMgr, const AdditionalKeywords &Keywords,
208     tooling::Replacements &Fixes, const FormatToken *Tok,
209     const std::string &Qualifier, tok::TokenKind QualifierType) {
210   // We only need to think about streams that begin with a qualifier.
211   if (!Tok->is(QualifierType))
212     return Tok;
213   // Don't concern yourself if nothing follows the qualifier.
214   if (!Tok->Next)
215     return Tok;
216   if (LeftRightQualifierAlignmentFixer::isPossibleMacro(Tok->Next))
217     return Tok;
218 
219   FormatToken *Qual = Tok->Next;
220   FormatToken *LastQual = Qual;
221   while (Qual && isQualifierOrType(Qual, ConfiguredQualifierTokens)) {
222     LastQual = Qual;
223     Qual = Qual->Next;
224   }
225   if (LastQual && Qual != LastQual) {
226     rotateTokens(SourceMgr, Fixes, Tok, LastQual, /*Left=*/false);
227     Tok = LastQual;
228   } else if (Tok->startsSequence(QualifierType, tok::identifier,
229                                  TT_TemplateCloser)) {
230     FormatToken *Closer = Tok->Next->Next;
231     rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/false);
232     Tok = Closer;
233     return Tok;
234   } else if (Tok->startsSequence(QualifierType, tok::identifier,
235                                  TT_TemplateOpener)) {
236     // Read from the TemplateOpener to
237     // TemplateCloser as in const ArrayRef<int> a; const ArrayRef<int> &a;
238     FormatToken *EndTemplate = Tok->Next->Next->MatchingParen;
239     if (EndTemplate) {
240       // Move to the end of any template class members e.g.
241       // `Foo<int>::iterator`.
242       if (EndTemplate->startsSequence(TT_TemplateCloser, tok::coloncolon,
243                                       tok::identifier)) {
244         EndTemplate = EndTemplate->Next->Next;
245       }
246     }
247     if (EndTemplate && EndTemplate->Next &&
248         !EndTemplate->Next->isOneOf(tok::equal, tok::l_paren)) {
249       insertQualifierAfter(SourceMgr, Fixes, EndTemplate, Qualifier);
250       // Remove the qualifier.
251       removeToken(SourceMgr, Fixes, Tok);
252       return Tok;
253     }
254   } else if (Tok->startsSequence(QualifierType, tok::identifier)) {
255     FormatToken *Next = Tok->Next;
256     // The case  `const Foo` -> `Foo const`
257     // The case  `const Foo *` -> `Foo const *`
258     // The case  `const Foo &` -> `Foo const &`
259     // The case  `const Foo &&` -> `Foo const &&`
260     // The case  `const std::Foo &&` -> `std::Foo const &&`
261     // The case  `const std::Foo<T> &&` -> `std::Foo<T> const &&`
262     while (Next && Next->isOneOf(tok::identifier, tok::coloncolon))
263       Next = Next->Next;
264     if (Next && Next->is(TT_TemplateOpener)) {
265       Next = Next->MatchingParen;
266       // Move to the end of any template class members e.g.
267       // `Foo<int>::iterator`.
268       if (Next && Next->startsSequence(TT_TemplateCloser, tok::coloncolon,
269                                        tok::identifier)) {
270         return Tok;
271       }
272       assert(Next && "Missing template opener");
273       Next = Next->Next;
274     }
275     if (Next && Next->isOneOf(tok::star, tok::amp, tok::ampamp) &&
276         !Tok->Next->isOneOf(Keywords.kw_override, Keywords.kw_final)) {
277       if (Next->Previous && !Next->Previous->is(QualifierType)) {
278         insertQualifierAfter(SourceMgr, Fixes, Next->Previous, Qualifier);
279         removeToken(SourceMgr, Fixes, Tok);
280       }
281       return Next;
282     }
283   }
284 
285   return Tok;
286 }
287 
288 const FormatToken *LeftRightQualifierAlignmentFixer::analyzeLeft(
289     const SourceManager &SourceMgr, const AdditionalKeywords &Keywords,
290     tooling::Replacements &Fixes, const FormatToken *Tok,
291     const std::string &Qualifier, tok::TokenKind QualifierType) {
292   // if Tok is an identifier and possibly a macro then don't convert.
293   if (LeftRightQualifierAlignmentFixer::isPossibleMacro(Tok))
294     return Tok;
295 
296   const FormatToken *Qual = Tok;
297   const FormatToken *LastQual = Qual;
298   while (Qual && isQualifierOrType(Qual, ConfiguredQualifierTokens)) {
299     LastQual = Qual;
300     Qual = Qual->Next;
301     if (Qual && Qual->is(QualifierType))
302       break;
303   }
304 
305   if (!Qual)
306     return Tok;
307 
308   if (LastQual && Qual != LastQual && Qual->is(QualifierType)) {
309     rotateTokens(SourceMgr, Fixes, Tok, Qual, /*Left=*/true);
310     if (!Qual->Next)
311       return Tok;
312     Tok = Qual->Next;
313   } else if (Tok->startsSequence(tok::identifier, QualifierType)) {
314     if (Tok->Next->Next && Tok->Next->Next->isOneOf(tok::identifier, tok::star,
315                                                     tok::amp, tok::ampamp)) {
316       // Don't swap `::iterator const` to `::const iterator`.
317       if (!Tok->Previous ||
318           (Tok->Previous && !Tok->Previous->is(tok::coloncolon))) {
319         rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/true);
320         Tok = Tok->Next;
321       }
322     } else if (Tok->startsSequence(tok::identifier, QualifierType,
323                                    TT_TemplateCloser)) {
324       FormatToken *Closer = Tok->Next->Next;
325       rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/true);
326       Tok = Closer;
327     }
328   }
329   if (Tok->is(TT_TemplateOpener) && Tok->Next &&
330       (Tok->Next->is(tok::identifier) || Tok->Next->isSimpleTypeSpecifier()) &&
331       Tok->Next->Next && Tok->Next->Next->is(QualifierType)) {
332     rotateTokens(SourceMgr, Fixes, Tok->Next, Tok->Next->Next, /*Left=*/true);
333   }
334   if (Tok->startsSequence(tok::identifier) && Tok->Next) {
335     if (Tok->Previous &&
336         Tok->Previous->isOneOf(tok::star, tok::ampamp, tok::amp)) {
337       return Tok;
338     }
339     const FormatToken *Next = Tok->Next;
340     // The case  `std::Foo<T> const` -> `const std::Foo<T> &&`
341     while (Next && Next->isOneOf(tok::identifier, tok::coloncolon))
342       Next = Next->Next;
343     if (Next && Next->Previous &&
344         Next->Previous->startsSequence(tok::identifier, TT_TemplateOpener)) {
345       // Read from to the end of the TemplateOpener to
346       // TemplateCloser const ArrayRef<int> a; const ArrayRef<int> &a;
347       if (Next->is(tok::comment) && Next->getNextNonComment())
348         Next = Next->getNextNonComment();
349       assert(Next->MatchingParen && "Missing template closer");
350       Next = Next->MatchingParen;
351 
352       // If the template closer is closing the requires clause,
353       // then stop and go back to the TemplateOpener and do whatever is
354       // inside the <>.
355       if (Next->ClosesRequiresClause)
356         return Next->MatchingParen;
357       Next = Next->Next;
358 
359       // Move to the end of any template class members e.g.
360       // `Foo<int>::iterator`.
361       if (Next && Next->startsSequence(tok::coloncolon, tok::identifier))
362         Next = Next->Next->Next;
363       if (Next && Next->is(QualifierType)) {
364         // Move the qualifier.
365         insertQualifierBefore(SourceMgr, Fixes, Tok, Qualifier);
366         removeToken(SourceMgr, Fixes, Next);
367         return Next;
368       }
369     }
370     if (Next && Next->Next &&
371         Next->Next->isOneOf(tok::amp, tok::ampamp, tok::star)) {
372       if (Next->is(QualifierType)) {
373         // Move the qualifier.
374         insertQualifierBefore(SourceMgr, Fixes, Tok, Qualifier);
375         removeToken(SourceMgr, Fixes, Next);
376         return Next;
377       }
378     }
379   }
380   return Tok;
381 }
382 
383 tok::TokenKind LeftRightQualifierAlignmentFixer::getTokenFromQualifier(
384     const std::string &Qualifier) {
385   // Don't let 'type' be an identifier, but steal typeof token.
386   return llvm::StringSwitch<tok::TokenKind>(Qualifier)
387       .Case("type", tok::kw_typeof)
388       .Case("const", tok::kw_const)
389       .Case("volatile", tok::kw_volatile)
390       .Case("static", tok::kw_static)
391       .Case("inline", tok::kw_inline)
392       .Case("constexpr", tok::kw_constexpr)
393       .Case("restrict", tok::kw_restrict)
394       .Default(tok::identifier);
395 }
396 
397 LeftRightQualifierAlignmentFixer::LeftRightQualifierAlignmentFixer(
398     const Environment &Env, const FormatStyle &Style,
399     const std::string &Qualifier,
400     const std::vector<tok::TokenKind> &QualifierTokens, bool RightAlign)
401     : TokenAnalyzer(Env, Style), Qualifier(Qualifier), RightAlign(RightAlign),
402       ConfiguredQualifierTokens(QualifierTokens) {}
403 
404 std::pair<tooling::Replacements, unsigned>
405 LeftRightQualifierAlignmentFixer::analyze(
406     TokenAnnotator & /*Annotator*/,
407     SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
408     FormatTokenLexer &Tokens) {
409   tooling::Replacements Fixes;
410   const AdditionalKeywords &Keywords = Tokens.getKeywords();
411   const SourceManager &SourceMgr = Env.getSourceManager();
412   AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
413 
414   tok::TokenKind QualifierToken = getTokenFromQualifier(Qualifier);
415   assert(QualifierToken != tok::identifier && "Unrecognised Qualifier");
416 
417   for (AnnotatedLine *Line : AnnotatedLines) {
418     if (Line->InPPDirective)
419       continue;
420     FormatToken *First = Line->First;
421     assert(First);
422     if (First->Finalized)
423       continue;
424 
425     const auto *Last = Line->Last;
426 
427     for (const auto *Tok = First; Tok && Tok != Last && Tok->Next;
428          Tok = Tok->Next) {
429       if (Tok->is(tok::comment))
430         continue;
431       if (RightAlign) {
432         Tok = analyzeRight(SourceMgr, Keywords, Fixes, Tok, Qualifier,
433                            QualifierToken);
434       } else {
435         Tok = analyzeLeft(SourceMgr, Keywords, Fixes, Tok, Qualifier,
436                           QualifierToken);
437       }
438     }
439   }
440   return {Fixes, 0};
441 }
442 
443 void QualifierAlignmentFixer::PrepareLeftRightOrdering(
444     const std::vector<std::string> &Order, std::vector<std::string> &LeftOrder,
445     std::vector<std::string> &RightOrder,
446     std::vector<tok::TokenKind> &Qualifiers) {
447 
448   // Depending on the position of type in the order you need
449   // To iterate forward or backward through the order list as qualifier
450   // can push through each other.
451   // The Order list must define the position of "type" to signify
452   assert(llvm::is_contained(Order, "type") &&
453          "QualifierOrder must contain type");
454   // Split the Order list by type and reverse the left side.
455 
456   bool left = true;
457   for (const auto &s : Order) {
458     if (s == "type") {
459       left = false;
460       continue;
461     }
462 
463     tok::TokenKind QualifierToken =
464         LeftRightQualifierAlignmentFixer::getTokenFromQualifier(s);
465     if (QualifierToken != tok::kw_typeof && QualifierToken != tok::identifier)
466       Qualifiers.push_back(QualifierToken);
467 
468     if (left) {
469       // Reverse the order for left aligned items.
470       LeftOrder.insert(LeftOrder.begin(), s);
471     } else {
472       RightOrder.push_back(s);
473     }
474   }
475 }
476 
477 bool LeftRightQualifierAlignmentFixer::isQualifierOrType(
478     const FormatToken *Tok, const std::vector<tok::TokenKind> &specifiedTypes) {
479   return Tok && (Tok->isSimpleTypeSpecifier() || Tok->is(tok::kw_auto) ||
480                  llvm::is_contained(specifiedTypes, Tok->Tok.getKind()));
481 }
482 
483 // If a token is an identifier and it's upper case, it could
484 // be a macro and hence we need to be able to ignore it.
485 bool LeftRightQualifierAlignmentFixer::isPossibleMacro(const FormatToken *Tok) {
486   if (!Tok)
487     return false;
488   if (!Tok->is(tok::identifier))
489     return false;
490   if (Tok->TokenText.upper() == Tok->TokenText.str()) {
491     // T,K,U,V likely could be template arguments
492     return (Tok->TokenText.size() != 1);
493   }
494   return false;
495 }
496 
497 } // namespace format
498 } // namespace clang
499