426 lines · cpp
1//===----------------------------------------------------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "DeclRefExprUtils.h"10#include "Matchers.h"11#include "clang/AST/ASTContext.h"12#include "clang/AST/DeclCXX.h"13#include "clang/AST/ExprCXX.h"14#include "clang/ASTMatchers/ASTMatchFinder.h"15#include <cassert>16 17namespace clang::tidy::utils::decl_ref_expr {18 19using namespace ::clang::ast_matchers;20using llvm::SmallPtrSet;21 22template <typename S>23static bool isSetDifferenceEmpty(const S &S1, const S &S2) {24 for (auto E : S1)25 if (S2.count(E) == 0)26 return false;27 return true;28}29 30// Extracts all Nodes keyed by ID from Matches and inserts them into Nodes.31template <typename Node>32static void extractNodesByIdTo(ArrayRef<BoundNodes> Matches, StringRef ID,33 SmallPtrSet<const Node *, 16> &Nodes) {34 for (const auto &Match : Matches)35 Nodes.insert(Match.getNodeAs<Node>(ID));36}37 38// Returns true if both types refer to the same type,39// ignoring the const-qualifier.40static bool isSameTypeIgnoringConst(QualType A, QualType B) {41 A = A.getCanonicalType();42 B = B.getCanonicalType();43 A.addConst();44 B.addConst();45 return A == B;46}47 48// Returns true if `D` and `O` have the same parameter types.49static bool hasSameParameterTypes(const CXXMethodDecl &D,50 const CXXMethodDecl &O) {51 if (D.getNumParams() != O.getNumParams())52 return false;53 for (int I = 0, E = D.getNumParams(); I < E; ++I) {54 if (!isSameTypeIgnoringConst(D.getParamDecl(I)->getType(),55 O.getParamDecl(I)->getType()))56 return false;57 }58 return true;59}60 61// If `D` has a const-qualified overload with otherwise identical62// ref-qualifiers and parameter types, returns that overload.63static const CXXMethodDecl *findConstOverload(const CXXMethodDecl &D) {64 assert(!D.isConst());65 66 const DeclContext::lookup_result LookupResult =67 D.getParent()->lookup(D.getNameInfo().getName());68 if (LookupResult.isSingleResult()) {69 // No overload.70 return nullptr;71 }72 for (const Decl *Overload : LookupResult) {73 const auto *O = dyn_cast<CXXMethodDecl>(Overload);74 if (O && !O->isDeleted() && O->isConst() &&75 O->getRefQualifier() == D.getRefQualifier() &&76 hasSameParameterTypes(D, *O))77 return O;78 }79 return nullptr;80}81 82// Returns true if both types are pointers or reference to the same type,83// ignoring the const-qualifier.84static bool pointsToSameTypeIgnoringConst(QualType A, QualType B) {85 assert(A->isPointerType() || A->isReferenceType());86 assert(B->isPointerType() || B->isReferenceType());87 return isSameTypeIgnoringConst(A->getPointeeType(), B->getPointeeType());88}89 90// Return true if non-const member function `M` likely does not mutate `*this`.91//92// Note that if the member call selects a method/operator `f` that93// is not const-qualified, then we also consider that the object is94// not mutated if:95// - (A) there is a const-qualified overload `cf` of `f` that has96// the97// same ref-qualifiers;98// - (B) * `f` returns a value, or99// * if `f` returns a `T&`, `cf` returns a `const T&` (up to100// possible aliases such as `reference` and101// `const_reference`), or102// * if `f` returns a `T*`, `cf` returns a `const T*` (up to103// possible aliases).104// - (C) the result of the call is not mutated.105//106// The assumption that `cf` has the same semantics as `f`.107// For example:108// - In `std::vector<T> v; const T t = v[...];`, we consider that109// expression `v[...]` does not mutate `v` as110// `T& std::vector<T>::operator[]` has a const overload111// `const T& std::vector<T>::operator[] const`, and the112// result expression of type `T&` is only used as a `const T&`;113// - In `std::map<K, V> m; V v = m.at(...);`, we consider114// `m.at(...)` to be an immutable access for the same reason.115// However:116// - In `std::map<K, V> m; const V v = m[...];`, We consider that117// `m[...]` mutates `m` as `V& std::map<K, V>::operator[]` does118// not have a const overload.119// - In `std::vector<T> v; T& t = v[...];`, we consider that120// expression `v[...]` mutates `v` as the result is kept as a121// mutable reference.122//123// This function checks (A) ad (B), but the caller should make sure that the124// object is not mutated through the return value.125static bool isLikelyShallowConst(const CXXMethodDecl &M) {126 assert(!M.isConst());127 // The method can mutate our variable.128 129 // (A)130 const CXXMethodDecl *ConstOverload = findConstOverload(M);131 if (ConstOverload == nullptr) {132 return false;133 }134 135 // (B)136 const QualType CallTy = M.getReturnType().getCanonicalType();137 const QualType OverloadTy = ConstOverload->getReturnType().getCanonicalType();138 if (CallTy->isReferenceType()) {139 return OverloadTy->isReferenceType() &&140 pointsToSameTypeIgnoringConst(CallTy, OverloadTy);141 }142 if (CallTy->isPointerType()) {143 return OverloadTy->isPointerType() &&144 pointsToSameTypeIgnoringConst(CallTy, OverloadTy);145 }146 return isSameTypeIgnoringConst(CallTy, OverloadTy);147}148 149namespace {150 151// A matcher that matches DeclRefExprs that are used in ways such that the152// underlying declaration is not modified.153// If the declaration is of pointer type, `Indirections` specifies the level154// of indirection of the object whose mutations we are tracking.155//156// For example, given:157// ```158// int i;159// int* p;160// p = &i; // (A)161// *p = 3; // (B)162// ```163//164// `declRefExpr(to(varDecl(hasName("p"))), doesNotMutateObject(0))` matches165// (B), but `declRefExpr(to(varDecl(hasName("p"))), doesNotMutateObject(1))`166// matches (A).167//168AST_MATCHER_P(DeclRefExpr, doesNotMutateObject, int, Indirections) {169 // We walk up the parents of the DeclRefExpr recursively. There are a few170 // kinds of expressions:171 // - Those that cannot be used to mutate the underlying variable. We can stop172 // recursion there.173 // - Those that can be used to mutate the underlying variable in analyzable174 // ways (such as taking the address or accessing a subobject). We have to175 // examine the parents.176 // - Those that we don't know how to analyze. In that case we stop there and177 // we assume that they can modify the expression.178 179 struct StackEntry {180 StackEntry(const Expr *E, int Indirections)181 : E(E), Indirections(Indirections) {}182 // The expression to analyze.183 const Expr *E;184 // The number of pointer indirections of the object being tracked (how185 // many times an address was taken).186 int Indirections;187 };188 189 llvm::SmallVector<StackEntry, 4> Stack;190 Stack.emplace_back(&Node, Indirections);191 ASTContext &Ctx = Finder->getASTContext();192 193 while (!Stack.empty()) {194 const StackEntry Entry = Stack.back();195 Stack.pop_back();196 197 // If the expression type is const-qualified at the appropriate indirection198 // level then we can not mutate the object.199 QualType Ty = Entry.E->getType().getCanonicalType();200 for (int I = 0; I < Entry.Indirections; ++I) {201 assert(Ty->isPointerType());202 Ty = Ty->getPointeeType().getCanonicalType();203 }204 if (Ty->isVoidType() || Ty.isConstQualified())205 continue;206 207 // Otherwise we have to look at the parents to see how the expression is208 // used.209 const DynTypedNodeList Parents = Ctx.getParents(*Entry.E);210 // Note: most nodes have a single parents, but there exist nodes that have211 // several parents, such as `InitListExpr` that have semantic and syntactic212 // forms.213 for (const auto &Parent : Parents) {214 if (Parent.get<CompoundStmt>()) {215 // Unused block-scope statement.216 continue;217 }218 const Expr *const P = Parent.get<Expr>();219 if (P == nullptr) {220 // `Parent` is not an expr (e.g. a `VarDecl`).221 // The case of binding to a `const&` or `const*` variable is handled by222 // the fact that there is going to be a `NoOp` cast to const below the223 // `VarDecl`, so we're not even going to get there.224 // The case of copying into a value-typed variable is handled by the225 // rvalue cast.226 // This triggers only when binding to a mutable reference/ptr variable.227 // FIXME: When we take a mutable reference we could keep checking the228 // new variable for const usage only.229 return false;230 }231 // Cosmetic nodes.232 if (isa<ParenExpr>(P) || isa<MaterializeTemporaryExpr>(P)) {233 Stack.emplace_back(P, Entry.Indirections);234 continue;235 }236 if (const auto *const Cast = dyn_cast<CastExpr>(P)) {237 switch (Cast->getCastKind()) {238 // NoOp casts are used to add `const`. We'll check whether adding that239 // const prevents modification when we process the cast.240 case CK_NoOp:241 // These do nothing w.r.t. to mutability.242 case CK_BaseToDerived:243 case CK_DerivedToBase:244 case CK_UncheckedDerivedToBase:245 case CK_Dynamic:246 case CK_BaseToDerivedMemberPointer:247 case CK_DerivedToBaseMemberPointer:248 Stack.emplace_back(Cast, Entry.Indirections);249 continue;250 case CK_ToVoid:251 case CK_PointerToBoolean:252 // These do not mutate the underlying variable.253 continue;254 case CK_LValueToRValue: {255 // An rvalue is immutable.256 if (Entry.Indirections == 0)257 continue;258 Stack.emplace_back(Cast, Entry.Indirections);259 continue;260 }261 default:262 // Bail out on casts that we cannot analyze.263 return false;264 }265 }266 if (const auto *const Member = dyn_cast<MemberExpr>(P)) {267 if (const auto *const Method =268 dyn_cast<CXXMethodDecl>(Member->getMemberDecl())) {269 if (Method->isConst() || Method->isStatic()) {270 // The method call cannot mutate our variable.271 continue;272 }273 if (isLikelyShallowConst(*Method)) {274 // We still have to check that the object is not modified through275 // the method's return value (C).276 const auto MemberParents = Ctx.getParents(*Member);277 assert(MemberParents.size() == 1);278 const auto *Call = MemberParents[0].get<CallExpr>();279 // If `o` is an object of class type and `f` is a member function,280 // then `o.f` has to be used as part of a call expression.281 assert(Call != nullptr && "member function has to be called");282 Stack.emplace_back(283 Call,284 Method->getReturnType().getCanonicalType()->isPointerType()285 ? 1286 : 0);287 continue;288 }289 return false;290 }291 Stack.emplace_back(Member, 0);292 continue;293 }294 if (const auto *const OpCall = dyn_cast<CXXOperatorCallExpr>(P)) {295 // Operator calls have function call syntax. The `*this` parameter296 // is the first parameter.297 if (OpCall->getNumArgs() == 0 || OpCall->getArg(0) != Entry.E) {298 return false;299 }300 const auto *const Method =301 dyn_cast_or_null<CXXMethodDecl>(OpCall->getDirectCallee());302 303 if (Method == nullptr) {304 // This is not a member operator. Typically, a friend operator. These305 // are handled like function calls.306 return false;307 }308 309 if (Method->isConst() || Method->isStatic()) {310 continue;311 }312 if (isLikelyShallowConst(*Method)) {313 // We still have to check that the object is not modified through314 // the operator's return value (C).315 Stack.emplace_back(316 OpCall,317 Method->getReturnType().getCanonicalType()->isPointerType() ? 1318 : 0);319 continue;320 }321 return false;322 }323 324 if (const auto *const Op = dyn_cast<UnaryOperator>(P)) {325 switch (Op->getOpcode()) {326 case UO_AddrOf:327 Stack.emplace_back(Op, Entry.Indirections + 1);328 continue;329 case UO_Deref:330 assert(Entry.Indirections > 0);331 Stack.emplace_back(Op, Entry.Indirections - 1);332 continue;333 default:334 // Bail out on unary operators that we cannot analyze.335 return false;336 }337 }338 339 // Assume any other expression can modify the underlying variable.340 return false;341 }342 }343 344 // No parent can modify the variable.345 return true;346}347 348} // namespace349 350SmallPtrSet<const DeclRefExpr *, 16>351constReferenceDeclRefExprs(const VarDecl &VarDecl, const Stmt &Stmt,352 ASTContext &Context, int Indirections) {353 auto Matches = match(findAll(declRefExpr(to(varDecl(equalsNode(&VarDecl))),354 doesNotMutateObject(Indirections))355 .bind("declRef")),356 Stmt, Context);357 SmallPtrSet<const DeclRefExpr *, 16> DeclRefs;358 extractNodesByIdTo(Matches, "declRef", DeclRefs);359 360 return DeclRefs;361}362 363bool isOnlyUsedAsConst(const VarDecl &Var, const Stmt &Stmt,364 ASTContext &Context, int Indirections) {365 // Collect all DeclRefExprs to the loop variable and all CallExprs and366 // CXXConstructExprs where the loop variable is used as argument to a const367 // reference parameter.368 // If the difference is empty it is safe for the loop variable to be a const369 // reference.370 auto AllDeclRefs = allDeclRefExprs(Var, Stmt, Context);371 auto ConstReferenceDeclRefs =372 constReferenceDeclRefExprs(Var, Stmt, Context, Indirections);373 return isSetDifferenceEmpty(AllDeclRefs, ConstReferenceDeclRefs);374}375 376SmallPtrSet<const DeclRefExpr *, 16>377allDeclRefExprs(const VarDecl &VarDecl, const Stmt &Stmt, ASTContext &Context) {378 auto Matches = match(379 findAll(declRefExpr(to(varDecl(equalsNode(&VarDecl)))).bind("declRef")),380 Stmt, Context);381 SmallPtrSet<const DeclRefExpr *, 16> DeclRefs;382 extractNodesByIdTo(Matches, "declRef", DeclRefs);383 return DeclRefs;384}385 386SmallPtrSet<const DeclRefExpr *, 16>387allDeclRefExprs(const VarDecl &VarDecl, const Decl &Decl, ASTContext &Context) {388 auto Matches = match(389 decl(forEachDescendant(390 declRefExpr(to(varDecl(equalsNode(&VarDecl)))).bind("declRef"))),391 Decl, Context);392 SmallPtrSet<const DeclRefExpr *, 16> DeclRefs;393 extractNodesByIdTo(Matches, "declRef", DeclRefs);394 return DeclRefs;395}396 397bool isCopyConstructorArgument(const DeclRefExpr &DeclRef, const Decl &Decl,398 ASTContext &Context) {399 auto UsedAsConstRefArg = forEachArgumentWithParam(400 declRefExpr(equalsNode(&DeclRef)),401 parmVarDecl(hasType(matchers::isReferenceToConst())));402 auto Matches = match(403 decl(hasDescendant(404 cxxConstructExpr(UsedAsConstRefArg, hasDeclaration(cxxConstructorDecl(405 isCopyConstructor())))406 .bind("constructExpr"))),407 Decl, Context);408 return !Matches.empty();409}410 411bool isCopyAssignmentArgument(const DeclRefExpr &DeclRef, const Decl &Decl,412 ASTContext &Context) {413 auto UsedAsConstRefArg = forEachArgumentWithParam(414 declRefExpr(equalsNode(&DeclRef)),415 parmVarDecl(hasType(matchers::isReferenceToConst())));416 auto Matches = match(417 decl(hasDescendant(418 cxxOperatorCallExpr(UsedAsConstRefArg, hasOverloadedOperatorName("="),419 callee(cxxMethodDecl(isCopyAssignmentOperator())))420 .bind("operatorCallExpr"))),421 Decl, Context);422 return !Matches.empty();423}424 425} // namespace clang::tidy::utils::decl_ref_expr426