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     Tok = Qual->Next;
307   } else if (Tok->startsSequence(tok::identifier, QualifierType)) {
308     if (Tok->Next->Next && Tok->Next->Next->isOneOf(tok::identifier, tok::star,
309                                                     tok::amp, tok::ampamp)) {
310       // Don't swap `::iterator const` to `::const iterator`.
311       if (!Tok->Previous ||
312           (Tok->Previous && !Tok->Previous->is(tok::coloncolon))) {
313         rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/true);
314         Tok = Tok->Next;
315       }
316     } else if (Tok->startsSequence(tok::identifier, QualifierType,
317                                    TT_TemplateCloser)) {
318       FormatToken *Closer = Tok->Next->Next;
319       rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/true);
320       Tok = Closer;
321     }
322   }
323   if (Tok->is(TT_TemplateOpener) && Tok->Next &&
324       (Tok->Next->is(tok::identifier) || Tok->Next->isSimpleTypeSpecifier()) &&
325       Tok->Next->Next && Tok->Next->Next->is(QualifierType))
326     rotateTokens(SourceMgr, Fixes, Tok->Next, Tok->Next->Next, /*Left=*/true);
327   if (Tok->startsSequence(tok::identifier) && Tok->Next) {
328     if (Tok->Previous &&
329         Tok->Previous->isOneOf(tok::star, tok::ampamp, tok::amp))
330       return Tok;
331     const FormatToken *Next = Tok->Next;
332     // The case  `std::Foo<T> const` -> `const std::Foo<T> &&`
333     while (Next && Next->isOneOf(tok::identifier, tok::coloncolon))
334       Next = Next->Next;
335     if (Next && Next->Previous &&
336         Next->Previous->startsSequence(tok::identifier, TT_TemplateOpener)) {
337       // Read from to the end of the TemplateOpener to
338       // TemplateCloser const ArrayRef<int> a; const ArrayRef<int> &a;
339       if (Next->is(tok::comment) && Next->getNextNonComment())
340         Next = Next->getNextNonComment();
341       assert(Next->MatchingParen && "Missing template closer");
342       Next = Next->MatchingParen;
343 
344       // If the template closer is closing the requires clause,
345       // then stop and go back to the TemplateOpener and do whatever is
346       // inside the <>.
347       if (Next->ClosesRequiresClause)
348         return Next->MatchingParen;
349       Next = Next->Next;
350 
351       // Move to the end of any template class members e.g.
352       // `Foo<int>::iterator`.
353       if (Next && Next->startsSequence(tok::coloncolon, tok::identifier))
354         Next = Next->Next->Next;
355       if (Next && Next->is(QualifierType)) {
356         // Move the qualifier.
357         insertQualifierBefore(SourceMgr, Fixes, Tok, Qualifier);
358         removeToken(SourceMgr, Fixes, Next);
359         return Next;
360       }
361     }
362     if (Next && Next->Next &&
363         Next->Next->isOneOf(tok::amp, tok::ampamp, tok::star)) {
364       if (Next->is(QualifierType)) {
365         // Move the qualifier.
366         insertQualifierBefore(SourceMgr, Fixes, Tok, Qualifier);
367         removeToken(SourceMgr, Fixes, Next);
368         return Next;
369       }
370     }
371   }
372   return Tok;
373 }
374 
375 tok::TokenKind LeftRightQualifierAlignmentFixer::getTokenFromQualifier(
376     const std::string &Qualifier) {
377   // Don't let 'type' be an identifier, but steal typeof token.
378   return llvm::StringSwitch<tok::TokenKind>(Qualifier)
379       .Case("type", tok::kw_typeof)
380       .Case("const", tok::kw_const)
381       .Case("volatile", tok::kw_volatile)
382       .Case("static", tok::kw_static)
383       .Case("inline", tok::kw_inline)
384       .Case("constexpr", tok::kw_constexpr)
385       .Case("restrict", tok::kw_restrict)
386       .Default(tok::identifier);
387 }
388 
389 LeftRightQualifierAlignmentFixer::LeftRightQualifierAlignmentFixer(
390     const Environment &Env, const FormatStyle &Style,
391     const std::string &Qualifier,
392     const std::vector<tok::TokenKind> &QualifierTokens, bool RightAlign)
393     : TokenAnalyzer(Env, Style), Qualifier(Qualifier), RightAlign(RightAlign),
394       ConfiguredQualifierTokens(QualifierTokens) {}
395 
396 std::pair<tooling::Replacements, unsigned>
397 LeftRightQualifierAlignmentFixer::analyze(
398     TokenAnnotator & /*Annotator*/,
399     SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
400     FormatTokenLexer &Tokens) {
401   tooling::Replacements Fixes;
402   const AdditionalKeywords &Keywords = Tokens.getKeywords();
403   const SourceManager &SourceMgr = Env.getSourceManager();
404   AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
405 
406   tok::TokenKind QualifierToken = getTokenFromQualifier(Qualifier);
407   assert(QualifierToken != tok::identifier && "Unrecognised Qualifier");
408 
409   for (AnnotatedLine *Line : AnnotatedLines) {
410     FormatToken *First = Line->First;
411     assert(First);
412     if (First->Finalized)
413       continue;
414 
415     const auto *Last = Line->Last;
416 
417     for (const auto *Tok = First; Tok && Tok != Last && Tok->Next;
418          Tok = Tok->Next) {
419       if (Tok->is(tok::comment))
420         continue;
421       if (RightAlign)
422         Tok = analyzeRight(SourceMgr, Keywords, Fixes, Tok, Qualifier,
423                            QualifierToken);
424       else
425         Tok = analyzeLeft(SourceMgr, Keywords, Fixes, Tok, Qualifier,
426                           QualifierToken);
427     }
428   }
429   return {Fixes, 0};
430 }
431 
432 void QualifierAlignmentFixer::PrepareLeftRightOrdering(
433     const std::vector<std::string> &Order, std::vector<std::string> &LeftOrder,
434     std::vector<std::string> &RightOrder,
435     std::vector<tok::TokenKind> &Qualifiers) {
436 
437   // Depending on the position of type in the order you need
438   // To iterate forward or backward through the order list as qualifier
439   // can push through each other.
440   // The Order list must define the position of "type" to signify
441   assert(llvm::is_contained(Order, "type") &&
442          "QualifierOrder must contain type");
443   // Split the Order list by type and reverse the left side.
444 
445   bool left = true;
446   for (const auto &s : Order) {
447     if (s == "type") {
448       left = false;
449       continue;
450     }
451 
452     tok::TokenKind QualifierToken =
453         LeftRightQualifierAlignmentFixer::getTokenFromQualifier(s);
454     if (QualifierToken != tok::kw_typeof && QualifierToken != tok::identifier)
455       Qualifiers.push_back(QualifierToken);
456 
457     if (left)
458       // Reverse the order for left aligned items.
459       LeftOrder.insert(LeftOrder.begin(), s);
460     else
461       RightOrder.push_back(s);
462   }
463 }
464 
465 bool LeftRightQualifierAlignmentFixer::isQualifierOrType(
466     const FormatToken *Tok, const std::vector<tok::TokenKind> &specifiedTypes) {
467   return Tok && (Tok->isSimpleTypeSpecifier() || Tok->is(tok::kw_auto) ||
468                  llvm::is_contained(specifiedTypes, Tok->Tok.getKind()));
469 }
470 
471 // If a token is an identifier and it's upper case, it could
472 // be a macro and hence we need to be able to ignore it.
473 bool LeftRightQualifierAlignmentFixer::isPossibleMacro(const FormatToken *Tok) {
474   if (!Tok)
475     return false;
476   if (!Tok->is(tok::identifier))
477     return false;
478   if (Tok->TokenText.upper() == Tok->TokenText.str())
479     // T,K,U,V likely could be template arguments
480     return (Tok->TokenText.size() != 1);
481   return false;
482 }
483 
484 } // namespace format
485 } // namespace clang
486