1//===--- UseRangesCheck.cpp - clang-tidy ----------------------------------===//
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#include "UseRangesCheck.h"
10#include "Matchers.h"
11#include "clang/AST/ASTContext.h"
12#include "clang/AST/Decl.h"
13#include "clang/AST/Expr.h"
14#include "clang/ASTMatchers/ASTMatchFinder.h"
15#include "clang/ASTMatchers/ASTMatchers.h"
16#include "clang/ASTMatchers/ASTMatchersInternal.h"
17#include "clang/Basic/Diagnostic.h"
18#include "clang/Basic/LLVM.h"
19#include "clang/Basic/SourceLocation.h"
20#include "clang/Basic/SourceManager.h"
21#include "clang/Lex/Lexer.h"
22#include "llvm/ADT/ArrayRef.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SmallBitVector.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/ADT/StringRef.h"
27#include "llvm/ADT/Twine.h"
28#include "llvm/Support/raw_ostream.h"
29#include <cassert>
30#include <optional>
31#include <string>
32
33using namespace clang::ast_matchers;
34
35static constexpr const char BoundCall[] = "CallExpr";
36static constexpr const char FuncDecl[] = "FuncDecl";
37static constexpr const char ArgName[] = "ArgName";
38
39namespace clang::tidy::utils {
40
41static std::string getFullPrefix(ArrayRef<UseRangesCheck::Indexes> Signature) {
42 std::string Output;
43 llvm::raw_string_ostream OS(Output);
44 for (const UseRangesCheck::Indexes &Item : Signature)
45 OS << Item.BeginArg << ":" << Item.EndArg << ":"
46 << (Item.ReplaceArg == Item.First ? '0' : '1');
47 return Output;
48}
49
50namespace {
51
52AST_MATCHER(Expr, hasSideEffects) {
53 return Node.HasSideEffects(Ctx: Finder->getASTContext());
54}
55} // namespace
56
57static auto
58makeExprMatcher(ast_matchers::internal::Matcher<Expr> ArgumentMatcher,
59 ArrayRef<StringRef> MethodNames,
60 ArrayRef<StringRef> FreeNames) {
61 return expr(
62 anyOf(cxxMemberCallExpr(argumentCountIs(N: 0),
63 callee(InnerMatcher: cxxMethodDecl(hasAnyName(MethodNames))),
64 on(InnerMatcher: ArgumentMatcher)),
65 callExpr(argumentCountIs(N: 1), hasArgument(N: 0, InnerMatcher: ArgumentMatcher),
66 hasDeclaration(InnerMatcher: functionDecl(hasAnyName(FreeNames))))));
67}
68
69static ast_matchers::internal::Matcher<CallExpr>
70makeMatcherPair(StringRef State, const UseRangesCheck::Indexes &Indexes,
71 ArrayRef<StringRef> BeginFreeNames,
72 ArrayRef<StringRef> EndFreeNames,
73 const std::optional<UseRangesCheck::ReverseIteratorDescriptor>
74 &ReverseDescriptor) {
75 std::string ArgBound = (ArgName + llvm::Twine(Indexes.BeginArg)).str();
76 SmallString<64> ID = {BoundCall, State};
77 ast_matchers::internal::Matcher<CallExpr> ArgumentMatcher = allOf(
78 hasArgument(N: Indexes.BeginArg,
79 InnerMatcher: makeExprMatcher(ArgumentMatcher: expr(unless(hasSideEffects())).bind(ID: ArgBound),
80 MethodNames: {"begin", "cbegin"}, FreeNames: BeginFreeNames)),
81 hasArgument(N: Indexes.EndArg,
82 InnerMatcher: makeExprMatcher(
83 ArgumentMatcher: expr(matchers::isStatementIdenticalToBoundNode(ID: ArgBound)),
84 MethodNames: {"end", "cend"}, FreeNames: EndFreeNames)));
85 if (ReverseDescriptor) {
86 ArgBound.push_back(c: 'R');
87 SmallVector<StringRef> RBegin{
88 llvm::make_first_range(c: ReverseDescriptor->FreeReverseNames)};
89 SmallVector<StringRef> REnd{
90 llvm::make_second_range(c: ReverseDescriptor->FreeReverseNames)};
91 ArgumentMatcher = anyOf(
92 ArgumentMatcher,
93 allOf(hasArgument(
94 N: Indexes.BeginArg,
95 InnerMatcher: makeExprMatcher(ArgumentMatcher: expr(unless(hasSideEffects())).bind(ID: ArgBound),
96 MethodNames: {"rbegin", "crbegin"}, FreeNames: RBegin)),
97 hasArgument(
98 N: Indexes.EndArg,
99 InnerMatcher: makeExprMatcher(
100 ArgumentMatcher: expr(matchers::isStatementIdenticalToBoundNode(ID: ArgBound)),
101 MethodNames: {"rend", "crend"}, FreeNames: REnd))));
102 }
103 return callExpr(argumentCountAtLeast(
104 N: std::max(a: Indexes.BeginArg, b: Indexes.EndArg) + 1),
105 ArgumentMatcher)
106 .bind(ID);
107}
108
109void UseRangesCheck::registerMatchers(MatchFinder *Finder) {
110 auto Replaces = getReplacerMap();
111 ReverseDescriptor = getReverseDescriptor();
112 auto BeginEndNames = getFreeBeginEndMethods();
113 llvm::SmallVector<StringRef, 4> BeginNames{
114 llvm::make_first_range(c&: BeginEndNames)};
115 llvm::SmallVector<StringRef, 4> EndNames{
116 llvm::make_second_range(c&: BeginEndNames)};
117 Replacers.clear();
118 llvm::DenseSet<Replacer *> SeenRepl;
119 for (auto I = Replaces.begin(), E = Replaces.end(); I != E; ++I) {
120 auto Replacer = I->getValue();
121 if (!SeenRepl.insert(V: Replacer.get()).second)
122 continue;
123 Replacers.push_back(x: Replacer);
124 assert(!Replacer->getReplacementSignatures().empty() &&
125 llvm::all_of(Replacer->getReplacementSignatures(),
126 [](auto Index) { return !Index.empty(); }));
127 std::vector<StringRef> Names(1, I->getKey());
128 for (auto J = std::next(x: I); J != E; ++J)
129 if (J->getValue() == Replacer)
130 Names.push_back(x: J->getKey());
131
132 std::vector<ast_matchers::internal::DynTypedMatcher> TotalMatchers;
133 // As we match on the first matched signature, we need to sort the
134 // signatures in order of length(longest to shortest). This way any
135 // signature that is a subset of another signature will be matched after the
136 // other.
137 SmallVector<Signature> SigVec(Replacer->getReplacementSignatures());
138 llvm::sort(C&: SigVec, Comp: [](auto &L, auto &R) { return R.size() < L.size(); });
139 for (const auto &Signature : SigVec) {
140 std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
141 for (const auto &ArgPair : Signature)
142 Matchers.push_back(x: makeMatcherPair(State: getFullPrefix(Signature), Indexes: ArgPair,
143 BeginFreeNames: BeginNames, EndFreeNames: EndNames,
144 ReverseDescriptor));
145 TotalMatchers.push_back(
146 x: ast_matchers::internal::DynTypedMatcher::constructVariadic(
147 Op: ast_matchers::internal::DynTypedMatcher::VO_AllOf,
148 SupportedKind: ASTNodeKind::getFromNodeKind<CallExpr>(), InnerMatchers: std::move(Matchers)));
149 }
150 Finder->addMatcher(
151 NodeMatch: callExpr(
152 callee(InnerMatcher: functionDecl(hasAnyName(std::move(Names)))
153 .bind(ID: (FuncDecl + Twine(Replacers.size() - 1).str()))),
154 ast_matchers::internal::DynTypedMatcher::constructVariadic(
155 Op: ast_matchers::internal::DynTypedMatcher::VO_AnyOf,
156 SupportedKind: ASTNodeKind::getFromNodeKind<CallExpr>(),
157 InnerMatchers: std::move(TotalMatchers))
158 .convertTo<CallExpr>()),
159 Action: this);
160 }
161}
162
163static void removeFunctionArgs(DiagnosticBuilder &Diag, const CallExpr &Call,
164 ArrayRef<unsigned> Indexes,
165 const ASTContext &Ctx) {
166 llvm::SmallVector<unsigned> Sorted(Indexes);
167 llvm::sort(C&: Sorted);
168 // Keep track of commas removed
169 llvm::SmallBitVector Commas(Call.getNumArgs());
170 // The first comma is actually the '(' which we can't remove
171 Commas[0] = true;
172 for (unsigned Index : Sorted) {
173 const Expr *Arg = Call.getArg(Arg: Index);
174 if (Commas[Index]) {
175 if (Index >= Commas.size()) {
176 Diag << FixItHint::CreateRemoval(Arg->getSourceRange());
177 } else {
178 // Remove the next comma
179 Commas[Index + 1] = true;
180 Diag << FixItHint::CreateRemoval(CharSourceRange::getTokenRange(
181 {Arg->getBeginLoc(),
182 Lexer::getLocForEndOfToken(
183 Loc: Arg->getEndLoc(), Offset: 0, SM: Ctx.getSourceManager(), LangOpts: Ctx.getLangOpts())
184 .getLocWithOffset(1)}));
185 }
186 } else {
187 Diag << FixItHint::CreateRemoval(CharSourceRange::getTokenRange(
188 Arg->getBeginLoc().getLocWithOffset(-1), Arg->getEndLoc()));
189 Commas[Index] = true;
190 }
191 }
192}
193
194void UseRangesCheck::check(const MatchFinder::MatchResult &Result) {
195 Replacer *Replacer = nullptr;
196 const FunctionDecl *Function = nullptr;
197 for (auto [Node, Value] : Result.Nodes.getMap()) {
198 StringRef NodeStr(Node);
199 if (!NodeStr.consume_front(Prefix: FuncDecl))
200 continue;
201 Function = Value.get<FunctionDecl>();
202 size_t Index;
203 if (NodeStr.getAsInteger(Radix: 10, Result&: Index)) {
204 llvm_unreachable("Unable to extract replacer index");
205 }
206 assert(Index < Replacers.size());
207 Replacer = Replacers[Index].get();
208 break;
209 }
210 assert(Replacer && Function);
211 SmallString<64> Buffer;
212 for (const Signature &Sig : Replacer->getReplacementSignatures()) {
213 Buffer.assign(Refs: {BoundCall, getFullPrefix(Signature: Sig)});
214 const auto *Call = Result.Nodes.getNodeAs<CallExpr>(ID: Buffer);
215 if (!Call)
216 continue;
217
218 // FIXME: This check specifically handles `CXXNullPtrLiteralExpr`, but
219 // a more general solution might be needed.
220 if (Function->getName() == "find") {
221 const unsigned ValueArgIndex = 2;
222 if (Call->getNumArgs() <= ValueArgIndex)
223 continue;
224 const Expr *ValueExpr =
225 Call->getArg(Arg: ValueArgIndex)->IgnoreParenImpCasts();
226 if (isa<CXXNullPtrLiteralExpr>(Val: ValueExpr))
227 return;
228 }
229
230 auto Diag = createDiag(Call: *Call);
231 if (auto ReplaceName = Replacer->getReplaceName(*Function))
232 Diag << FixItHint::CreateReplacement(Call->getCallee()->getSourceRange(),
233 *ReplaceName);
234 if (auto Include = Replacer->getHeaderInclusion(*Function))
235 Diag << Inserter.createIncludeInsertion(
236 FileID: Result.SourceManager->getFileID(SpellingLoc: Call->getBeginLoc()), Header: *Include);
237 llvm::SmallVector<unsigned, 3> ToRemove;
238 for (const auto &[First, Second, Replace] : Sig) {
239 auto ArgNode = ArgName + std::to_string(val: First);
240 if (const auto *ArgExpr = Result.Nodes.getNodeAs<Expr>(ID: ArgNode)) {
241 Diag << FixItHint::CreateReplacement(
242 Call->getArg(Arg: Replace == Indexes::Second ? Second : First)
243 ->getSourceRange(),
244 Lexer::getSourceText(
245 Range: CharSourceRange::getTokenRange(ArgExpr->getSourceRange()),
246 SM: Result.Context->getSourceManager(),
247 LangOpts: Result.Context->getLangOpts()));
248 } else {
249 assert(ReverseDescriptor && "Couldn't find forward argument");
250 ArgNode.push_back(c: 'R');
251 ArgExpr = Result.Nodes.getNodeAs<Expr>(ID: ArgNode);
252 assert(ArgExpr && "Couldn't find forward or reverse argument");
253 if (ReverseDescriptor->ReverseHeader)
254 Diag << Inserter.createIncludeInsertion(
255 FileID: Result.SourceManager->getFileID(SpellingLoc: Call->getBeginLoc()),
256 Header: *ReverseDescriptor->ReverseHeader);
257 StringRef ArgText = Lexer::getSourceText(
258 Range: CharSourceRange::getTokenRange(ArgExpr->getSourceRange()),
259 SM: Result.Context->getSourceManager(), LangOpts: Result.Context->getLangOpts());
260 SmallString<128> ReplaceText;
261 if (ReverseDescriptor->IsPipeSyntax)
262 ReplaceText.assign(
263 Refs: {ArgText, " | ", ReverseDescriptor->ReverseAdaptorName});
264 else
265 ReplaceText.assign(
266 Refs: {ReverseDescriptor->ReverseAdaptorName, "(", ArgText, ")"});
267 Diag << FixItHint::CreateReplacement(
268 Call->getArg(Arg: Replace == Indexes::Second ? Second : First)
269 ->getSourceRange(),
270 ReplaceText);
271 }
272 ToRemove.push_back(Elt: Replace == Indexes::Second ? First : Second);
273 }
274 removeFunctionArgs(Diag, Call: *Call, Indexes: ToRemove, Ctx: *Result.Context);
275 return;
276 }
277 llvm_unreachable("No valid signature found");
278}
279
280bool UseRangesCheck::isLanguageVersionSupported(
281 const LangOptions &LangOpts) const {
282 return LangOpts.CPlusPlus11;
283}
284
285UseRangesCheck::UseRangesCheck(StringRef Name, ClangTidyContext *Context)
286 : ClangTidyCheck(Name, Context),
287 Inserter(Options.getLocalOrGlobal(LocalName: "IncludeStyle",
288 Default: utils::IncludeSorter::IS_LLVM),
289 areDiagsSelfContained()) {}
290
291void UseRangesCheck::registerPPCallbacks(const SourceManager &,
292 Preprocessor *PP, Preprocessor *) {
293 Inserter.registerPreprocessor(PP);
294}
295
296void UseRangesCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
297 Options.store(Options&: Opts, LocalName: "IncludeStyle", Value: Inserter.getStyle());
298}
299
300std::optional<std::string>
301UseRangesCheck::Replacer::getHeaderInclusion(const NamedDecl &) const {
302 return std::nullopt;
303}
304
305DiagnosticBuilder UseRangesCheck::createDiag(const CallExpr &Call) {
306 return diag(Loc: Call.getBeginLoc(), Description: "use a ranges version of this algorithm");
307}
308
309std::optional<UseRangesCheck::ReverseIteratorDescriptor>
310UseRangesCheck::getReverseDescriptor() const {
311 return std::nullopt;
312}
313
314ArrayRef<std::pair<StringRef, StringRef>>
315UseRangesCheck::getFreeBeginEndMethods() const {
316 return {};
317}
318
319std::optional<TraversalKind> UseRangesCheck::getCheckTraversalKind() const {
320 return TK_IgnoreUnlessSpelledInSource;
321}
322} // namespace clang::tidy::utils
323

source code of clang-tools-extra/clang-tidy/utils/UseRangesCheck.cpp