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   auto AnalyzeTemplate =
220       [&](const FormatToken *Tok,
221           const FormatToken *StartTemplate) -> const FormatToken * {
222     // Read from the TemplateOpener to TemplateCloser.
223     FormatToken *EndTemplate = StartTemplate->MatchingParen;
224     if (EndTemplate) {
225       // Move to the end of any template class members e.g.
226       // `Foo<int>::iterator`.
227       if (EndTemplate->startsSequence(TT_TemplateCloser, tok::coloncolon,
228                                       tok::identifier)) {
229         EndTemplate = EndTemplate->Next->Next;
230       }
231     }
232     if (EndTemplate && EndTemplate->Next &&
233         !EndTemplate->Next->isOneOf(tok::equal, tok::l_paren)) {
234       insertQualifierAfter(SourceMgr, Fixes, EndTemplate, Qualifier);
235       // Remove the qualifier.
236       removeToken(SourceMgr, Fixes, Tok);
237       return Tok;
238     }
239     return nullptr;
240   };
241 
242   FormatToken *Qual = Tok->Next;
243   FormatToken *LastQual = Qual;
244   while (Qual && isQualifierOrType(Qual, ConfiguredQualifierTokens)) {
245     LastQual = Qual;
246     Qual = Qual->Next;
247   }
248   if (LastQual && Qual != LastQual) {
249     rotateTokens(SourceMgr, Fixes, Tok, LastQual, /*Left=*/false);
250     Tok = LastQual;
251   } else if (Tok->startsSequence(QualifierType, tok::identifier,
252                                  TT_TemplateCloser)) {
253     FormatToken *Closer = Tok->Next->Next;
254     rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/false);
255     Tok = Closer;
256     return Tok;
257   } else if (Tok->startsSequence(QualifierType, tok::identifier,
258                                  TT_TemplateOpener)) {
259     // `const ArrayRef<int> a;`
260     // `const ArrayRef<int> &a;`
261     const FormatToken *NewTok = AnalyzeTemplate(Tok, Tok->Next->Next);
262     if (NewTok)
263       return NewTok;
264   } else if (Tok->startsSequence(QualifierType, tok::coloncolon,
265                                  tok::identifier, TT_TemplateOpener)) {
266     // `const ::ArrayRef<int> a;`
267     // `const ::ArrayRef<int> &a;`
268     const FormatToken *NewTok = AnalyzeTemplate(Tok, Tok->Next->Next->Next);
269     if (NewTok)
270       return NewTok;
271   } else if (Tok->startsSequence(QualifierType, tok::identifier) ||
272              Tok->startsSequence(QualifierType, tok::coloncolon,
273                                  tok::identifier)) {
274     FormatToken *Next = Tok->Next;
275     // The case  `const Foo` -> `Foo const`
276     // The case  `const ::Foo` -> `::Foo const`
277     // The case  `const Foo *` -> `Foo const *`
278     // The case  `const Foo &` -> `Foo const &`
279     // The case  `const Foo &&` -> `Foo const &&`
280     // The case  `const std::Foo &&` -> `std::Foo const &&`
281     // The case  `const std::Foo<T> &&` -> `std::Foo<T> const &&`
282     while (Next && Next->isOneOf(tok::identifier, tok::coloncolon))
283       Next = Next->Next;
284     if (Next && Next->is(TT_TemplateOpener)) {
285       Next = Next->MatchingParen;
286       // Move to the end of any template class members e.g.
287       // `Foo<int>::iterator`.
288       if (Next && Next->startsSequence(TT_TemplateCloser, tok::coloncolon,
289                                        tok::identifier)) {
290         return Tok;
291       }
292       assert(Next && "Missing template opener");
293       Next = Next->Next;
294     }
295     if (Next && Next->isOneOf(tok::star, tok::amp, tok::ampamp) &&
296         !Tok->Next->isOneOf(Keywords.kw_override, Keywords.kw_final)) {
297       if (Next->Previous && !Next->Previous->is(QualifierType)) {
298         insertQualifierAfter(SourceMgr, Fixes, Next->Previous, Qualifier);
299         removeToken(SourceMgr, Fixes, Tok);
300       }
301       return Next;
302     }
303   }
304 
305   return Tok;
306 }
307 
308 const FormatToken *LeftRightQualifierAlignmentFixer::analyzeLeft(
309     const SourceManager &SourceMgr, const AdditionalKeywords &Keywords,
310     tooling::Replacements &Fixes, const FormatToken *Tok,
311     const std::string &Qualifier, tok::TokenKind QualifierType) {
312   // if Tok is an identifier and possibly a macro then don't convert.
313   if (LeftRightQualifierAlignmentFixer::isPossibleMacro(Tok))
314     return Tok;
315 
316   const FormatToken *Qual = Tok;
317   const FormatToken *LastQual = Qual;
318   while (Qual && isQualifierOrType(Qual, ConfiguredQualifierTokens)) {
319     LastQual = Qual;
320     Qual = Qual->Next;
321     if (Qual && Qual->is(QualifierType))
322       break;
323   }
324 
325   if (!Qual)
326     return Tok;
327 
328   if (LastQual && Qual != LastQual && Qual->is(QualifierType)) {
329     rotateTokens(SourceMgr, Fixes, Tok, Qual, /*Left=*/true);
330     if (!Qual->Next)
331       return Tok;
332     Tok = Qual->Next;
333   } else if (Tok->startsSequence(tok::identifier, QualifierType)) {
334     if (Tok->Next->Next && Tok->Next->Next->isOneOf(tok::identifier, tok::star,
335                                                     tok::amp, tok::ampamp)) {
336       // Don't swap `::iterator const` to `::const iterator`.
337       if (!Tok->Previous ||
338           (Tok->Previous && !Tok->Previous->is(tok::coloncolon))) {
339         rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/true);
340         Tok = Tok->Next;
341       }
342     } else if (Tok->startsSequence(tok::identifier, QualifierType,
343                                    TT_TemplateCloser)) {
344       FormatToken *Closer = Tok->Next->Next;
345       rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/true);
346       Tok = Closer;
347     }
348   }
349   if (Tok->is(TT_TemplateOpener) && Tok->Next &&
350       (Tok->Next->is(tok::identifier) || Tok->Next->isSimpleTypeSpecifier()) &&
351       Tok->Next->Next && Tok->Next->Next->is(QualifierType)) {
352     rotateTokens(SourceMgr, Fixes, Tok->Next, Tok->Next->Next, /*Left=*/true);
353   }
354   if ((Tok->startsSequence(tok::coloncolon, tok::identifier) ||
355        Tok->is(tok::identifier)) &&
356       Tok->Next) {
357     if (Tok->Previous &&
358         Tok->Previous->isOneOf(tok::star, tok::ampamp, tok::amp)) {
359       return Tok;
360     }
361     const FormatToken *Next = Tok->Next;
362     // The case  `std::Foo<T> const` -> `const std::Foo<T> &&`
363     while (Next && Next->isOneOf(tok::identifier, tok::coloncolon))
364       Next = Next->Next;
365     if (Next && Next->Previous &&
366         Next->Previous->startsSequence(tok::identifier, TT_TemplateOpener)) {
367       // Read from to the end of the TemplateOpener to
368       // TemplateCloser const ArrayRef<int> a; const ArrayRef<int> &a;
369       if (Next->is(tok::comment) && Next->getNextNonComment())
370         Next = Next->getNextNonComment();
371       assert(Next->MatchingParen && "Missing template closer");
372       Next = Next->MatchingParen;
373 
374       // If the template closer is closing the requires clause,
375       // then stop and go back to the TemplateOpener and do whatever is
376       // inside the <>.
377       if (Next->ClosesRequiresClause)
378         return Next->MatchingParen;
379       Next = Next->Next;
380 
381       // Move to the end of any template class members e.g.
382       // `Foo<int>::iterator`.
383       if (Next && Next->startsSequence(tok::coloncolon, tok::identifier))
384         Next = Next->Next->Next;
385       if (Next && Next->is(QualifierType)) {
386         // Move the qualifier.
387         insertQualifierBefore(SourceMgr, Fixes, Tok, Qualifier);
388         removeToken(SourceMgr, Fixes, Next);
389         return Next;
390       }
391     }
392     if (Next && Next->Next &&
393         Next->Next->isOneOf(tok::amp, tok::ampamp, tok::star)) {
394       if (Next->is(QualifierType)) {
395         // Move the qualifier.
396         insertQualifierBefore(SourceMgr, Fixes, Tok, Qualifier);
397         removeToken(SourceMgr, Fixes, Next);
398         return Next;
399       }
400     }
401   }
402   return Tok;
403 }
404 
405 tok::TokenKind LeftRightQualifierAlignmentFixer::getTokenFromQualifier(
406     const std::string &Qualifier) {
407   // Don't let 'type' be an identifier, but steal typeof token.
408   return llvm::StringSwitch<tok::TokenKind>(Qualifier)
409       .Case("type", tok::kw_typeof)
410       .Case("const", tok::kw_const)
411       .Case("volatile", tok::kw_volatile)
412       .Case("static", tok::kw_static)
413       .Case("inline", tok::kw_inline)
414       .Case("constexpr", tok::kw_constexpr)
415       .Case("restrict", tok::kw_restrict)
416       .Default(tok::identifier);
417 }
418 
419 LeftRightQualifierAlignmentFixer::LeftRightQualifierAlignmentFixer(
420     const Environment &Env, const FormatStyle &Style,
421     const std::string &Qualifier,
422     const std::vector<tok::TokenKind> &QualifierTokens, bool RightAlign)
423     : TokenAnalyzer(Env, Style), Qualifier(Qualifier), RightAlign(RightAlign),
424       ConfiguredQualifierTokens(QualifierTokens) {}
425 
426 std::pair<tooling::Replacements, unsigned>
427 LeftRightQualifierAlignmentFixer::analyze(
428     TokenAnnotator & /*Annotator*/,
429     SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
430     FormatTokenLexer &Tokens) {
431   tooling::Replacements Fixes;
432   const AdditionalKeywords &Keywords = Tokens.getKeywords();
433   const SourceManager &SourceMgr = Env.getSourceManager();
434   AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
435 
436   tok::TokenKind QualifierToken = getTokenFromQualifier(Qualifier);
437   assert(QualifierToken != tok::identifier && "Unrecognised Qualifier");
438 
439   for (AnnotatedLine *Line : AnnotatedLines) {
440     if (Line->InPPDirective)
441       continue;
442     FormatToken *First = Line->First;
443     assert(First);
444     if (First->Finalized)
445       continue;
446 
447     const auto *Last = Line->Last;
448 
449     for (const auto *Tok = First; Tok && Tok != Last && Tok->Next;
450          Tok = Tok->Next) {
451       if (Tok->is(tok::comment))
452         continue;
453       if (RightAlign) {
454         Tok = analyzeRight(SourceMgr, Keywords, Fixes, Tok, Qualifier,
455                            QualifierToken);
456       } else {
457         Tok = analyzeLeft(SourceMgr, Keywords, Fixes, Tok, Qualifier,
458                           QualifierToken);
459       }
460     }
461   }
462   return {Fixes, 0};
463 }
464 
465 void QualifierAlignmentFixer::PrepareLeftRightOrdering(
466     const std::vector<std::string> &Order, std::vector<std::string> &LeftOrder,
467     std::vector<std::string> &RightOrder,
468     std::vector<tok::TokenKind> &Qualifiers) {
469 
470   // Depending on the position of type in the order you need
471   // To iterate forward or backward through the order list as qualifier
472   // can push through each other.
473   // The Order list must define the position of "type" to signify
474   assert(llvm::is_contained(Order, "type") &&
475          "QualifierOrder must contain type");
476   // Split the Order list by type and reverse the left side.
477 
478   bool left = true;
479   for (const auto &s : Order) {
480     if (s == "type") {
481       left = false;
482       continue;
483     }
484 
485     tok::TokenKind QualifierToken =
486         LeftRightQualifierAlignmentFixer::getTokenFromQualifier(s);
487     if (QualifierToken != tok::kw_typeof && QualifierToken != tok::identifier)
488       Qualifiers.push_back(QualifierToken);
489 
490     if (left) {
491       // Reverse the order for left aligned items.
492       LeftOrder.insert(LeftOrder.begin(), s);
493     } else {
494       RightOrder.push_back(s);
495     }
496   }
497 }
498 
499 bool LeftRightQualifierAlignmentFixer::isQualifierOrType(
500     const FormatToken *Tok, const std::vector<tok::TokenKind> &specifiedTypes) {
501   return Tok && (Tok->isSimpleTypeSpecifier() || Tok->is(tok::kw_auto) ||
502                  llvm::is_contained(specifiedTypes, Tok->Tok.getKind()));
503 }
504 
505 // If a token is an identifier and it's upper case, it could
506 // be a macro and hence we need to be able to ignore it.
507 bool LeftRightQualifierAlignmentFixer::isPossibleMacro(const FormatToken *Tok) {
508   if (!Tok)
509     return false;
510   if (!Tok->is(tok::identifier))
511     return false;
512   if (Tok->TokenText.upper() == Tok->TokenText.str()) {
513     // T,K,U,V likely could be template arguments
514     return (Tok->TokenText.size() != 1);
515   }
516   return false;
517 }
518 
519 } // namespace format
520 } // namespace clang
521