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