1 //===- DynamicTypePropagation.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 // This file contains two checkers. One helps the static analyzer core to track 10 // types, the other does type inference on Obj-C generics and report type 11 // errors. 12 // 13 // Dynamic Type Propagation: 14 // This checker defines the rules for dynamic type gathering and propagation. 15 // 16 // Generics Checker for Objective-C: 17 // This checker tries to find type errors that the compiler is not able to catch 18 // due to the implicit conversions that were introduced for backward 19 // compatibility. 20 // 21 //===----------------------------------------------------------------------===// 22 23 #include "clang/AST/ParentMap.h" 24 #include "clang/AST/RecursiveASTVisitor.h" 25 #include "clang/Basic/Builtins.h" 26 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" 27 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 28 #include "clang/StaticAnalyzer/Core/Checker.h" 29 #include "clang/StaticAnalyzer/Core/CheckerManager.h" 30 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 31 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 32 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h" 33 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 34 #include <optional> 35 36 using namespace clang; 37 using namespace ento; 38 39 // ProgramState trait - The type inflation is tracked by DynamicTypeMap. This is 40 // an auxiliary map that tracks more information about generic types, because in 41 // some cases the most derived type is not the most informative one about the 42 // type parameters. This types that are stored for each symbol in this map must 43 // be specialized. 44 // TODO: In some case the type stored in this map is exactly the same that is 45 // stored in DynamicTypeMap. We should no store duplicated information in those 46 // cases. 47 REGISTER_MAP_WITH_PROGRAMSTATE(MostSpecializedTypeArgsMap, SymbolRef, 48 const ObjCObjectPointerType *) 49 50 namespace { 51 class DynamicTypePropagation: 52 public Checker< check::PreCall, 53 check::PostCall, 54 check::DeadSymbols, 55 check::PostStmt<CastExpr>, 56 check::PostStmt<CXXNewExpr>, 57 check::PreObjCMessage, 58 check::PostObjCMessage > { 59 60 /// Return a better dynamic type if one can be derived from the cast. 61 const ObjCObjectPointerType *getBetterObjCType(const Expr *CastE, 62 CheckerContext &C) const; 63 64 ExplodedNode *dynamicTypePropagationOnCasts(const CastExpr *CE, 65 ProgramStateRef &State, 66 CheckerContext &C) const; 67 68 mutable std::unique_ptr<BugType> ObjCGenericsBugType; 69 void initBugType() const { 70 if (!ObjCGenericsBugType) 71 ObjCGenericsBugType.reset(new BugType( 72 GenericCheckName, "Generics", categories::CoreFoundationObjectiveC)); 73 } 74 75 class GenericsBugVisitor : public BugReporterVisitor { 76 public: 77 GenericsBugVisitor(SymbolRef S) : Sym(S) {} 78 79 void Profile(llvm::FoldingSetNodeID &ID) const override { 80 static int X = 0; 81 ID.AddPointer(&X); 82 ID.AddPointer(Sym); 83 } 84 85 PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, 86 BugReporterContext &BRC, 87 PathSensitiveBugReport &BR) override; 88 89 private: 90 // The tracked symbol. 91 SymbolRef Sym; 92 }; 93 94 void reportGenericsBug(const ObjCObjectPointerType *From, 95 const ObjCObjectPointerType *To, ExplodedNode *N, 96 SymbolRef Sym, CheckerContext &C, 97 const Stmt *ReportedNode = nullptr) const; 98 99 public: 100 void checkPreCall(const CallEvent &Call, CheckerContext &C) const; 101 void checkPostCall(const CallEvent &Call, CheckerContext &C) const; 102 void checkPostStmt(const CastExpr *CastE, CheckerContext &C) const; 103 void checkPostStmt(const CXXNewExpr *NewE, CheckerContext &C) const; 104 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; 105 void checkPreObjCMessage(const ObjCMethodCall &M, CheckerContext &C) const; 106 void checkPostObjCMessage(const ObjCMethodCall &M, CheckerContext &C) const; 107 108 /// This value is set to true, when the Generics checker is turned on. 109 bool CheckGenerics = false; 110 CheckerNameRef GenericCheckName; 111 }; 112 113 bool isObjCClassType(QualType Type) { 114 if (const auto *PointerType = dyn_cast<ObjCObjectPointerType>(Type)) { 115 return PointerType->getObjectType()->isObjCClass(); 116 } 117 return false; 118 } 119 120 struct RuntimeType { 121 const ObjCObjectType *Type = nullptr; 122 bool Precise = false; 123 124 operator bool() const { return Type != nullptr; } 125 }; 126 127 RuntimeType inferReceiverType(const ObjCMethodCall &Message, 128 CheckerContext &C) { 129 const ObjCMessageExpr *MessageExpr = Message.getOriginExpr(); 130 131 // Check if we can statically infer the actual type precisely. 132 // 133 // 1. Class is written directly in the message: 134 // \code 135 // [ActualClass classMethod]; 136 // \endcode 137 if (MessageExpr->getReceiverKind() == ObjCMessageExpr::Class) { 138 return {MessageExpr->getClassReceiver()->getAs<ObjCObjectType>(), 139 /*Precise=*/true}; 140 } 141 142 // 2. Receiver is 'super' from a class method (a.k.a 'super' is a 143 // class object). 144 // \code 145 // [super classMethod]; 146 // \endcode 147 if (MessageExpr->getReceiverKind() == ObjCMessageExpr::SuperClass) { 148 return {MessageExpr->getSuperType()->getAs<ObjCObjectType>(), 149 /*Precise=*/true}; 150 } 151 152 // 3. Receiver is 'super' from an instance method (a.k.a 'super' is an 153 // instance of a super class). 154 // \code 155 // [super instanceMethod]; 156 // \encode 157 if (MessageExpr->getReceiverKind() == ObjCMessageExpr::SuperInstance) { 158 if (const auto *ObjTy = 159 MessageExpr->getSuperType()->getAs<ObjCObjectPointerType>()) 160 return {ObjTy->getObjectType(), /*Precise=*/true}; 161 } 162 163 const Expr *RecE = MessageExpr->getInstanceReceiver(); 164 165 if (!RecE) 166 return {}; 167 168 // Otherwise, let's try to get type information from our estimations of 169 // runtime types. 170 QualType InferredType; 171 SVal ReceiverSVal = C.getSVal(RecE); 172 ProgramStateRef State = C.getState(); 173 174 if (const MemRegion *ReceiverRegion = ReceiverSVal.getAsRegion()) { 175 if (DynamicTypeInfo DTI = getDynamicTypeInfo(State, ReceiverRegion)) { 176 InferredType = DTI.getType().getCanonicalType(); 177 } 178 } 179 180 if (SymbolRef ReceiverSymbol = ReceiverSVal.getAsSymbol()) { 181 if (InferredType.isNull()) { 182 InferredType = ReceiverSymbol->getType(); 183 } 184 185 // If receiver is a Class object, we want to figure out the type it 186 // represents. 187 if (isObjCClassType(InferredType)) { 188 // We actually might have some info on what type is contained in there. 189 if (DynamicTypeInfo DTI = 190 getClassObjectDynamicTypeInfo(State, ReceiverSymbol)) { 191 192 // Types in Class objects can be ONLY Objective-C types 193 return {cast<ObjCObjectType>(DTI.getType()), !DTI.canBeASubClass()}; 194 } 195 196 SVal SelfSVal = State->getSelfSVal(C.getLocationContext()); 197 198 // Another way we can guess what is in Class object, is when it is a 199 // 'self' variable of the current class method. 200 if (ReceiverSVal == SelfSVal) { 201 // In this case, we should return the type of the enclosing class 202 // declaration. 203 if (const ObjCMethodDecl *MD = 204 dyn_cast<ObjCMethodDecl>(C.getStackFrame()->getDecl())) 205 if (const ObjCObjectType *ObjTy = dyn_cast<ObjCObjectType>( 206 MD->getClassInterface()->getTypeForDecl())) 207 return {ObjTy}; 208 } 209 } 210 } 211 212 // Unfortunately, it seems like we have no idea what that type is. 213 if (InferredType.isNull()) { 214 return {}; 215 } 216 217 // We can end up here if we got some dynamic type info and the 218 // receiver is not one of the known Class objects. 219 if (const auto *ReceiverInferredType = 220 dyn_cast<ObjCObjectPointerType>(InferredType)) { 221 return {ReceiverInferredType->getObjectType()}; 222 } 223 224 // Any other type (like 'Class') is not really useful at this point. 225 return {}; 226 } 227 } // end anonymous namespace 228 229 void DynamicTypePropagation::checkDeadSymbols(SymbolReaper &SR, 230 CheckerContext &C) const { 231 ProgramStateRef State = removeDeadTypes(C.getState(), SR); 232 State = removeDeadClassObjectTypes(State, SR); 233 234 MostSpecializedTypeArgsMapTy TyArgMap = 235 State->get<MostSpecializedTypeArgsMap>(); 236 for (MostSpecializedTypeArgsMapTy::iterator I = TyArgMap.begin(), 237 E = TyArgMap.end(); 238 I != E; ++I) { 239 if (SR.isDead(I->first)) { 240 State = State->remove<MostSpecializedTypeArgsMap>(I->first); 241 } 242 } 243 244 C.addTransition(State); 245 } 246 247 static void recordFixedType(const MemRegion *Region, const CXXMethodDecl *MD, 248 CheckerContext &C) { 249 assert(Region); 250 assert(MD); 251 252 ASTContext &Ctx = C.getASTContext(); 253 QualType Ty = Ctx.getPointerType(Ctx.getRecordType(MD->getParent())); 254 255 ProgramStateRef State = C.getState(); 256 State = setDynamicTypeInfo(State, Region, Ty, /*CanBeSubClassed=*/false); 257 C.addTransition(State); 258 } 259 260 void DynamicTypePropagation::checkPreCall(const CallEvent &Call, 261 CheckerContext &C) const { 262 if (const CXXConstructorCall *Ctor = dyn_cast<CXXConstructorCall>(&Call)) { 263 // C++11 [class.cdtor]p4: When a virtual function is called directly or 264 // indirectly from a constructor or from a destructor, including during 265 // the construction or destruction of the class's non-static data members, 266 // and the object to which the call applies is the object under 267 // construction or destruction, the function called is the final overrider 268 // in the constructor's or destructor's class and not one overriding it in 269 // a more-derived class. 270 271 switch (Ctor->getOriginExpr()->getConstructionKind()) { 272 case CXXConstructExpr::CK_Complete: 273 case CXXConstructExpr::CK_Delegating: 274 // No additional type info necessary. 275 return; 276 case CXXConstructExpr::CK_NonVirtualBase: 277 case CXXConstructExpr::CK_VirtualBase: 278 if (const MemRegion *Target = Ctor->getCXXThisVal().getAsRegion()) 279 recordFixedType(Target, Ctor->getDecl(), C); 280 return; 281 } 282 283 return; 284 } 285 286 if (const CXXDestructorCall *Dtor = dyn_cast<CXXDestructorCall>(&Call)) { 287 // C++11 [class.cdtor]p4 (see above) 288 if (!Dtor->isBaseDestructor()) 289 return; 290 291 const MemRegion *Target = Dtor->getCXXThisVal().getAsRegion(); 292 if (!Target) 293 return; 294 295 const Decl *D = Dtor->getDecl(); 296 if (!D) 297 return; 298 299 recordFixedType(Target, cast<CXXDestructorDecl>(D), C); 300 return; 301 } 302 } 303 304 void DynamicTypePropagation::checkPostCall(const CallEvent &Call, 305 CheckerContext &C) const { 306 // We can obtain perfect type info for return values from some calls. 307 if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(&Call)) { 308 309 // Get the returned value if it's a region. 310 const MemRegion *RetReg = Call.getReturnValue().getAsRegion(); 311 if (!RetReg) 312 return; 313 314 ProgramStateRef State = C.getState(); 315 const ObjCMethodDecl *D = Msg->getDecl(); 316 317 if (D && D->hasRelatedResultType()) { 318 switch (Msg->getMethodFamily()) { 319 default: 320 break; 321 322 // We assume that the type of the object returned by alloc and new are the 323 // pointer to the object of the class specified in the receiver of the 324 // message. 325 case OMF_alloc: 326 case OMF_new: { 327 // Get the type of object that will get created. 328 RuntimeType ObjTy = inferReceiverType(*Msg, C); 329 330 if (!ObjTy) 331 return; 332 333 QualType DynResTy = 334 C.getASTContext().getObjCObjectPointerType(QualType(ObjTy.Type, 0)); 335 // We used to assume that whatever type we got from inferring the 336 // type is actually precise (and it is not exactly correct). 337 // A big portion of the existing behavior depends on that assumption 338 // (e.g. certain inlining won't take place). For this reason, we don't 339 // use ObjTy.Precise flag here. 340 // 341 // TODO: We should mitigate this problem some time in the future 342 // and replace hardcoded 'false' with '!ObjTy.Precise'. 343 C.addTransition(setDynamicTypeInfo(State, RetReg, DynResTy, false)); 344 break; 345 } 346 case OMF_init: { 347 // Assume, the result of the init method has the same dynamic type as 348 // the receiver and propagate the dynamic type info. 349 const MemRegion *RecReg = Msg->getReceiverSVal().getAsRegion(); 350 if (!RecReg) 351 return; 352 DynamicTypeInfo RecDynType = getDynamicTypeInfo(State, RecReg); 353 C.addTransition(setDynamicTypeInfo(State, RetReg, RecDynType)); 354 break; 355 } 356 } 357 } 358 return; 359 } 360 361 if (const CXXConstructorCall *Ctor = dyn_cast<CXXConstructorCall>(&Call)) { 362 // We may need to undo the effects of our pre-call check. 363 switch (Ctor->getOriginExpr()->getConstructionKind()) { 364 case CXXConstructExpr::CK_Complete: 365 case CXXConstructExpr::CK_Delegating: 366 // No additional work necessary. 367 // Note: This will leave behind the actual type of the object for 368 // complete constructors, but arguably that's a good thing, since it 369 // means the dynamic type info will be correct even for objects 370 // constructed with operator new. 371 return; 372 case CXXConstructExpr::CK_NonVirtualBase: 373 case CXXConstructExpr::CK_VirtualBase: 374 if (const MemRegion *Target = Ctor->getCXXThisVal().getAsRegion()) { 375 // We just finished a base constructor. Now we can use the subclass's 376 // type when resolving virtual calls. 377 const LocationContext *LCtx = C.getLocationContext(); 378 379 // FIXME: In C++17 classes with non-virtual bases may be treated as 380 // aggregates, and in such case no top-frame constructor will be called. 381 // Figure out if we need to do anything in this case. 382 // FIXME: Instead of relying on the ParentMap, we should have the 383 // trigger-statement (InitListExpr in this case) available in this 384 // callback, ideally as part of CallEvent. 385 if (isa_and_nonnull<InitListExpr>( 386 LCtx->getParentMap().getParent(Ctor->getOriginExpr()))) 387 return; 388 389 recordFixedType(Target, cast<CXXConstructorDecl>(LCtx->getDecl()), C); 390 } 391 return; 392 } 393 } 394 } 395 396 /// TODO: Handle explicit casts. 397 /// Handle C++ casts. 398 /// 399 /// Precondition: the cast is between ObjCObjectPointers. 400 ExplodedNode *DynamicTypePropagation::dynamicTypePropagationOnCasts( 401 const CastExpr *CE, ProgramStateRef &State, CheckerContext &C) const { 402 // We only track type info for regions. 403 const MemRegion *ToR = C.getSVal(CE).getAsRegion(); 404 if (!ToR) 405 return C.getPredecessor(); 406 407 if (isa<ExplicitCastExpr>(CE)) 408 return C.getPredecessor(); 409 410 if (const Type *NewTy = getBetterObjCType(CE, C)) { 411 State = setDynamicTypeInfo(State, ToR, QualType(NewTy, 0)); 412 return C.addTransition(State); 413 } 414 return C.getPredecessor(); 415 } 416 417 void DynamicTypePropagation::checkPostStmt(const CXXNewExpr *NewE, 418 CheckerContext &C) const { 419 if (NewE->isArray()) 420 return; 421 422 // We only track dynamic type info for regions. 423 const MemRegion *MR = C.getSVal(NewE).getAsRegion(); 424 if (!MR) 425 return; 426 427 C.addTransition(setDynamicTypeInfo(C.getState(), MR, NewE->getType(), 428 /*CanBeSubClassed=*/false)); 429 } 430 431 // Return a better dynamic type if one can be derived from the cast. 432 // Compare the current dynamic type of the region and the new type to which we 433 // are casting. If the new type is lower in the inheritance hierarchy, pick it. 434 const ObjCObjectPointerType * 435 DynamicTypePropagation::getBetterObjCType(const Expr *CastE, 436 CheckerContext &C) const { 437 const MemRegion *ToR = C.getSVal(CastE).getAsRegion(); 438 assert(ToR); 439 440 // Get the old and new types. 441 const ObjCObjectPointerType *NewTy = 442 CastE->getType()->getAs<ObjCObjectPointerType>(); 443 if (!NewTy) 444 return nullptr; 445 QualType OldDTy = getDynamicTypeInfo(C.getState(), ToR).getType(); 446 if (OldDTy.isNull()) { 447 return NewTy; 448 } 449 const ObjCObjectPointerType *OldTy = 450 OldDTy->getAs<ObjCObjectPointerType>(); 451 if (!OldTy) 452 return nullptr; 453 454 // Id the old type is 'id', the new one is more precise. 455 if (OldTy->isObjCIdType() && !NewTy->isObjCIdType()) 456 return NewTy; 457 458 // Return new if it's a subclass of old. 459 const ObjCInterfaceDecl *ToI = NewTy->getInterfaceDecl(); 460 const ObjCInterfaceDecl *FromI = OldTy->getInterfaceDecl(); 461 if (ToI && FromI && FromI->isSuperClassOf(ToI)) 462 return NewTy; 463 464 return nullptr; 465 } 466 467 static const ObjCObjectPointerType *getMostInformativeDerivedClassImpl( 468 const ObjCObjectPointerType *From, const ObjCObjectPointerType *To, 469 const ObjCObjectPointerType *MostInformativeCandidate, ASTContext &C) { 470 // Checking if from and to are the same classes modulo specialization. 471 if (From->getInterfaceDecl()->getCanonicalDecl() == 472 To->getInterfaceDecl()->getCanonicalDecl()) { 473 if (To->isSpecialized()) { 474 assert(MostInformativeCandidate->isSpecialized()); 475 return MostInformativeCandidate; 476 } 477 return From; 478 } 479 480 if (To->getObjectType()->getSuperClassType().isNull()) { 481 // If To has no super class and From and To aren't the same then 482 // To was not actually a descendent of From. In this case the best we can 483 // do is 'From'. 484 return From; 485 } 486 487 const auto *SuperOfTo = 488 To->getObjectType()->getSuperClassType()->castAs<ObjCObjectType>(); 489 assert(SuperOfTo); 490 QualType SuperPtrOfToQual = 491 C.getObjCObjectPointerType(QualType(SuperOfTo, 0)); 492 const auto *SuperPtrOfTo = SuperPtrOfToQual->castAs<ObjCObjectPointerType>(); 493 if (To->isUnspecialized()) 494 return getMostInformativeDerivedClassImpl(From, SuperPtrOfTo, SuperPtrOfTo, 495 C); 496 else 497 return getMostInformativeDerivedClassImpl(From, SuperPtrOfTo, 498 MostInformativeCandidate, C); 499 } 500 501 /// A downcast may loose specialization information. E. g.: 502 /// MutableMap<T, U> : Map 503 /// The downcast to MutableMap looses the information about the types of the 504 /// Map (due to the type parameters are not being forwarded to Map), and in 505 /// general there is no way to recover that information from the 506 /// declaration. In order to have to most information, lets find the most 507 /// derived type that has all the type parameters forwarded. 508 /// 509 /// Get the a subclass of \p From (which has a lower bound \p To) that do not 510 /// loose information about type parameters. \p To has to be a subclass of 511 /// \p From. From has to be specialized. 512 static const ObjCObjectPointerType * 513 getMostInformativeDerivedClass(const ObjCObjectPointerType *From, 514 const ObjCObjectPointerType *To, ASTContext &C) { 515 return getMostInformativeDerivedClassImpl(From, To, To, C); 516 } 517 518 /// Inputs: 519 /// \param StaticLowerBound Static lower bound for a symbol. The dynamic lower 520 /// bound might be the subclass of this type. 521 /// \param StaticUpperBound A static upper bound for a symbol. 522 /// \p StaticLowerBound expected to be the subclass of \p StaticUpperBound. 523 /// \param Current The type that was inferred for a symbol in a previous 524 /// context. Might be null when this is the first time that inference happens. 525 /// Precondition: 526 /// \p StaticLowerBound or \p StaticUpperBound is specialized. If \p Current 527 /// is not null, it is specialized. 528 /// Possible cases: 529 /// (1) The \p Current is null and \p StaticLowerBound <: \p StaticUpperBound 530 /// (2) \p StaticLowerBound <: \p Current <: \p StaticUpperBound 531 /// (3) \p Current <: \p StaticLowerBound <: \p StaticUpperBound 532 /// (4) \p StaticLowerBound <: \p StaticUpperBound <: \p Current 533 /// Effect: 534 /// Use getMostInformativeDerivedClass with the upper and lower bound of the 535 /// set {\p StaticLowerBound, \p Current, \p StaticUpperBound}. The computed 536 /// lower bound must be specialized. If the result differs from \p Current or 537 /// \p Current is null, store the result. 538 static bool 539 storeWhenMoreInformative(ProgramStateRef &State, SymbolRef Sym, 540 const ObjCObjectPointerType *const *Current, 541 const ObjCObjectPointerType *StaticLowerBound, 542 const ObjCObjectPointerType *StaticUpperBound, 543 ASTContext &C) { 544 // TODO: The above 4 cases are not exhaustive. In particular, it is possible 545 // for Current to be incomparable with StaticLowerBound, StaticUpperBound, 546 // or both. 547 // 548 // For example, suppose Foo<T> and Bar<T> are unrelated types. 549 // 550 // Foo<T> *f = ... 551 // Bar<T> *b = ... 552 // 553 // id t1 = b; 554 // f = t1; 555 // id t2 = f; // StaticLowerBound is Foo<T>, Current is Bar<T> 556 // 557 // We should either constrain the callers of this function so that the stated 558 // preconditions hold (and assert it) or rewrite the function to expicitly 559 // handle the additional cases. 560 561 // Precondition 562 assert(StaticUpperBound->isSpecialized() || 563 StaticLowerBound->isSpecialized()); 564 assert(!Current || (*Current)->isSpecialized()); 565 566 // Case (1) 567 if (!Current) { 568 if (StaticUpperBound->isUnspecialized()) { 569 State = State->set<MostSpecializedTypeArgsMap>(Sym, StaticLowerBound); 570 return true; 571 } 572 // Upper bound is specialized. 573 const ObjCObjectPointerType *WithMostInfo = 574 getMostInformativeDerivedClass(StaticUpperBound, StaticLowerBound, C); 575 State = State->set<MostSpecializedTypeArgsMap>(Sym, WithMostInfo); 576 return true; 577 } 578 579 // Case (3) 580 if (C.canAssignObjCInterfaces(StaticLowerBound, *Current)) { 581 return false; 582 } 583 584 // Case (4) 585 if (C.canAssignObjCInterfaces(*Current, StaticUpperBound)) { 586 // The type arguments might not be forwarded at any point of inheritance. 587 const ObjCObjectPointerType *WithMostInfo = 588 getMostInformativeDerivedClass(*Current, StaticUpperBound, C); 589 WithMostInfo = 590 getMostInformativeDerivedClass(WithMostInfo, StaticLowerBound, C); 591 if (WithMostInfo == *Current) 592 return false; 593 State = State->set<MostSpecializedTypeArgsMap>(Sym, WithMostInfo); 594 return true; 595 } 596 597 // Case (2) 598 const ObjCObjectPointerType *WithMostInfo = 599 getMostInformativeDerivedClass(*Current, StaticLowerBound, C); 600 if (WithMostInfo != *Current) { 601 State = State->set<MostSpecializedTypeArgsMap>(Sym, WithMostInfo); 602 return true; 603 } 604 605 return false; 606 } 607 608 /// Type inference based on static type information that is available for the 609 /// cast and the tracked type information for the given symbol. When the tracked 610 /// symbol and the destination type of the cast are unrelated, report an error. 611 void DynamicTypePropagation::checkPostStmt(const CastExpr *CE, 612 CheckerContext &C) const { 613 if (CE->getCastKind() != CK_BitCast) 614 return; 615 616 QualType OriginType = CE->getSubExpr()->getType(); 617 QualType DestType = CE->getType(); 618 619 const auto *OrigObjectPtrType = OriginType->getAs<ObjCObjectPointerType>(); 620 const auto *DestObjectPtrType = DestType->getAs<ObjCObjectPointerType>(); 621 622 if (!OrigObjectPtrType || !DestObjectPtrType) 623 return; 624 625 ProgramStateRef State = C.getState(); 626 ExplodedNode *AfterTypeProp = dynamicTypePropagationOnCasts(CE, State, C); 627 628 ASTContext &ASTCtxt = C.getASTContext(); 629 630 // This checker detects the subtyping relationships using the assignment 631 // rules. In order to be able to do this the kindofness must be stripped 632 // first. The checker treats every type as kindof type anyways: when the 633 // tracked type is the subtype of the static type it tries to look up the 634 // methods in the tracked type first. 635 OrigObjectPtrType = OrigObjectPtrType->stripObjCKindOfTypeAndQuals(ASTCtxt); 636 DestObjectPtrType = DestObjectPtrType->stripObjCKindOfTypeAndQuals(ASTCtxt); 637 638 if (OrigObjectPtrType->isUnspecialized() && 639 DestObjectPtrType->isUnspecialized()) 640 return; 641 642 SymbolRef Sym = C.getSVal(CE).getAsSymbol(); 643 if (!Sym) 644 return; 645 646 const ObjCObjectPointerType *const *TrackedType = 647 State->get<MostSpecializedTypeArgsMap>(Sym); 648 649 if (isa<ExplicitCastExpr>(CE)) { 650 // Treat explicit casts as an indication from the programmer that the 651 // Objective-C type system is not rich enough to express the needed 652 // invariant. In such cases, forget any existing information inferred 653 // about the type arguments. We don't assume the casted-to specialized 654 // type here because the invariant the programmer specifies in the cast 655 // may only hold at this particular program point and not later ones. 656 // We don't want a suppressing cast to require a cascade of casts down the 657 // line. 658 if (TrackedType) { 659 State = State->remove<MostSpecializedTypeArgsMap>(Sym); 660 C.addTransition(State, AfterTypeProp); 661 } 662 return; 663 } 664 665 // Check which assignments are legal. 666 bool OrigToDest = 667 ASTCtxt.canAssignObjCInterfaces(DestObjectPtrType, OrigObjectPtrType); 668 bool DestToOrig = 669 ASTCtxt.canAssignObjCInterfaces(OrigObjectPtrType, DestObjectPtrType); 670 671 // The tracked type should be the sub or super class of the static destination 672 // type. When an (implicit) upcast or a downcast happens according to static 673 // types, and there is no subtyping relationship between the tracked and the 674 // static destination types, it indicates an error. 675 if (TrackedType && 676 !ASTCtxt.canAssignObjCInterfaces(DestObjectPtrType, *TrackedType) && 677 !ASTCtxt.canAssignObjCInterfaces(*TrackedType, DestObjectPtrType)) { 678 static CheckerProgramPointTag IllegalConv(this, "IllegalConversion"); 679 ExplodedNode *N = C.addTransition(State, AfterTypeProp, &IllegalConv); 680 reportGenericsBug(*TrackedType, DestObjectPtrType, N, Sym, C); 681 return; 682 } 683 684 // Handle downcasts and upcasts. 685 686 const ObjCObjectPointerType *LowerBound = DestObjectPtrType; 687 const ObjCObjectPointerType *UpperBound = OrigObjectPtrType; 688 if (OrigToDest && !DestToOrig) 689 std::swap(LowerBound, UpperBound); 690 691 // The id type is not a real bound. Eliminate it. 692 LowerBound = LowerBound->isObjCIdType() ? UpperBound : LowerBound; 693 UpperBound = UpperBound->isObjCIdType() ? LowerBound : UpperBound; 694 695 if (storeWhenMoreInformative(State, Sym, TrackedType, LowerBound, UpperBound, 696 ASTCtxt)) { 697 C.addTransition(State, AfterTypeProp); 698 } 699 } 700 701 static const Expr *stripCastsAndSugar(const Expr *E) { 702 E = E->IgnoreParenImpCasts(); 703 if (const PseudoObjectExpr *POE = dyn_cast<PseudoObjectExpr>(E)) 704 E = POE->getSyntacticForm()->IgnoreParenImpCasts(); 705 if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) 706 E = OVE->getSourceExpr()->IgnoreParenImpCasts(); 707 return E; 708 } 709 710 static bool isObjCTypeParamDependent(QualType Type) { 711 // It is illegal to typedef parameterized types inside an interface. Therefore 712 // an Objective-C type can only be dependent on a type parameter when the type 713 // parameter structurally present in the type itself. 714 class IsObjCTypeParamDependentTypeVisitor 715 : public RecursiveASTVisitor<IsObjCTypeParamDependentTypeVisitor> { 716 public: 717 IsObjCTypeParamDependentTypeVisitor() : Result(false) {} 718 bool VisitObjCTypeParamType(const ObjCTypeParamType *Type) { 719 if (isa<ObjCTypeParamDecl>(Type->getDecl())) { 720 Result = true; 721 return false; 722 } 723 return true; 724 } 725 726 bool Result; 727 }; 728 729 IsObjCTypeParamDependentTypeVisitor Visitor; 730 Visitor.TraverseType(Type); 731 return Visitor.Result; 732 } 733 734 /// A method might not be available in the interface indicated by the static 735 /// type. However it might be available in the tracked type. In order to 736 /// properly substitute the type parameters we need the declaration context of 737 /// the method. The more specialized the enclosing class of the method is, the 738 /// more likely that the parameter substitution will be successful. 739 static const ObjCMethodDecl * 740 findMethodDecl(const ObjCMessageExpr *MessageExpr, 741 const ObjCObjectPointerType *TrackedType, ASTContext &ASTCtxt) { 742 const ObjCMethodDecl *Method = nullptr; 743 744 QualType ReceiverType = MessageExpr->getReceiverType(); 745 const auto *ReceiverObjectPtrType = 746 ReceiverType->getAs<ObjCObjectPointerType>(); 747 748 // Do this "devirtualization" on instance and class methods only. Trust the 749 // static type on super and super class calls. 750 if (MessageExpr->getReceiverKind() == ObjCMessageExpr::Instance || 751 MessageExpr->getReceiverKind() == ObjCMessageExpr::Class) { 752 // When the receiver type is id, Class, or some super class of the tracked 753 // type, look up the method in the tracked type, not in the receiver type. 754 // This way we preserve more information. 755 if (ReceiverType->isObjCIdType() || ReceiverType->isObjCClassType() || 756 ASTCtxt.canAssignObjCInterfaces(ReceiverObjectPtrType, TrackedType)) { 757 const ObjCInterfaceDecl *InterfaceDecl = TrackedType->getInterfaceDecl(); 758 // The method might not be found. 759 Selector Sel = MessageExpr->getSelector(); 760 Method = InterfaceDecl->lookupInstanceMethod(Sel); 761 if (!Method) 762 Method = InterfaceDecl->lookupClassMethod(Sel); 763 } 764 } 765 766 // Fallback to statick method lookup when the one based on the tracked type 767 // failed. 768 return Method ? Method : MessageExpr->getMethodDecl(); 769 } 770 771 /// Get the returned ObjCObjectPointerType by a method based on the tracked type 772 /// information, or null pointer when the returned type is not an 773 /// ObjCObjectPointerType. 774 static QualType getReturnTypeForMethod( 775 const ObjCMethodDecl *Method, ArrayRef<QualType> TypeArgs, 776 const ObjCObjectPointerType *SelfType, ASTContext &C) { 777 QualType StaticResultType = Method->getReturnType(); 778 779 // Is the return type declared as instance type? 780 if (StaticResultType == C.getObjCInstanceType()) 781 return QualType(SelfType, 0); 782 783 // Check whether the result type depends on a type parameter. 784 if (!isObjCTypeParamDependent(StaticResultType)) 785 return QualType(); 786 787 QualType ResultType = StaticResultType.substObjCTypeArgs( 788 C, TypeArgs, ObjCSubstitutionContext::Result); 789 790 return ResultType; 791 } 792 793 /// When the receiver has a tracked type, use that type to validate the 794 /// argumments of the message expression and the return value. 795 void DynamicTypePropagation::checkPreObjCMessage(const ObjCMethodCall &M, 796 CheckerContext &C) const { 797 ProgramStateRef State = C.getState(); 798 SymbolRef Sym = M.getReceiverSVal().getAsSymbol(); 799 if (!Sym) 800 return; 801 802 const ObjCObjectPointerType *const *TrackedType = 803 State->get<MostSpecializedTypeArgsMap>(Sym); 804 if (!TrackedType) 805 return; 806 807 // Get the type arguments from tracked type and substitute type arguments 808 // before do the semantic check. 809 810 ASTContext &ASTCtxt = C.getASTContext(); 811 const ObjCMessageExpr *MessageExpr = M.getOriginExpr(); 812 const ObjCMethodDecl *Method = 813 findMethodDecl(MessageExpr, *TrackedType, ASTCtxt); 814 815 // It is possible to call non-existent methods in Obj-C. 816 if (!Method) 817 return; 818 819 // If the method is declared on a class that has a non-invariant 820 // type parameter, don't warn about parameter mismatches after performing 821 // substitution. This prevents warning when the programmer has purposely 822 // casted the receiver to a super type or unspecialized type but the analyzer 823 // has a more precise tracked type than the programmer intends at the call 824 // site. 825 // 826 // For example, consider NSArray (which has a covariant type parameter) 827 // and NSMutableArray (a subclass of NSArray where the type parameter is 828 // invariant): 829 // NSMutableArray *a = [[NSMutableArray<NSString *> alloc] init; 830 // 831 // [a containsObject:number]; // Safe: -containsObject is defined on NSArray. 832 // NSArray<NSObject *> *other = [a arrayByAddingObject:number] // Safe 833 // 834 // [a addObject:number] // Unsafe: -addObject: is defined on NSMutableArray 835 // 836 837 const ObjCInterfaceDecl *Interface = Method->getClassInterface(); 838 if (!Interface) 839 return; 840 841 ObjCTypeParamList *TypeParams = Interface->getTypeParamList(); 842 if (!TypeParams) 843 return; 844 845 for (ObjCTypeParamDecl *TypeParam : *TypeParams) { 846 if (TypeParam->getVariance() != ObjCTypeParamVariance::Invariant) 847 return; 848 } 849 850 std::optional<ArrayRef<QualType>> TypeArgs = 851 (*TrackedType)->getObjCSubstitutions(Method->getDeclContext()); 852 // This case might happen when there is an unspecialized override of a 853 // specialized method. 854 if (!TypeArgs) 855 return; 856 857 for (unsigned i = 0; i < Method->param_size(); i++) { 858 const Expr *Arg = MessageExpr->getArg(i); 859 const ParmVarDecl *Param = Method->parameters()[i]; 860 861 QualType OrigParamType = Param->getType(); 862 if (!isObjCTypeParamDependent(OrigParamType)) 863 continue; 864 865 QualType ParamType = OrigParamType.substObjCTypeArgs( 866 ASTCtxt, *TypeArgs, ObjCSubstitutionContext::Parameter); 867 // Check if it can be assigned 868 const auto *ParamObjectPtrType = ParamType->getAs<ObjCObjectPointerType>(); 869 const auto *ArgObjectPtrType = 870 stripCastsAndSugar(Arg)->getType()->getAs<ObjCObjectPointerType>(); 871 if (!ParamObjectPtrType || !ArgObjectPtrType) 872 continue; 873 874 // Check if we have more concrete tracked type that is not a super type of 875 // the static argument type. 876 SVal ArgSVal = M.getArgSVal(i); 877 SymbolRef ArgSym = ArgSVal.getAsSymbol(); 878 if (ArgSym) { 879 const ObjCObjectPointerType *const *TrackedArgType = 880 State->get<MostSpecializedTypeArgsMap>(ArgSym); 881 if (TrackedArgType && 882 ASTCtxt.canAssignObjCInterfaces(ArgObjectPtrType, *TrackedArgType)) { 883 ArgObjectPtrType = *TrackedArgType; 884 } 885 } 886 887 // Warn when argument is incompatible with the parameter. 888 if (!ASTCtxt.canAssignObjCInterfaces(ParamObjectPtrType, 889 ArgObjectPtrType)) { 890 static CheckerProgramPointTag Tag(this, "ArgTypeMismatch"); 891 ExplodedNode *N = C.addTransition(State, &Tag); 892 reportGenericsBug(ArgObjectPtrType, ParamObjectPtrType, N, Sym, C, Arg); 893 return; 894 } 895 } 896 } 897 898 /// This callback is used to infer the types for Class variables. This info is 899 /// used later to validate messages that sent to classes. Class variables are 900 /// initialized with by invoking the 'class' method on a class. 901 /// This method is also used to infer the type information for the return 902 /// types. 903 // TODO: right now it only tracks generic types. Extend this to track every 904 // type in the DynamicTypeMap and diagnose type errors! 905 void DynamicTypePropagation::checkPostObjCMessage(const ObjCMethodCall &M, 906 CheckerContext &C) const { 907 const ObjCMessageExpr *MessageExpr = M.getOriginExpr(); 908 909 SymbolRef RetSym = M.getReturnValue().getAsSymbol(); 910 if (!RetSym) 911 return; 912 913 Selector Sel = MessageExpr->getSelector(); 914 ProgramStateRef State = C.getState(); 915 916 // Here we try to propagate information on Class objects. 917 if (Sel.getAsString() == "class") { 918 // We try to figure out the type from the receiver of the 'class' message. 919 if (RuntimeType ReceiverRuntimeType = inferReceiverType(M, C)) { 920 921 ReceiverRuntimeType.Type->getSuperClassType(); 922 QualType ReceiverClassType(ReceiverRuntimeType.Type, 0); 923 924 // We want to consider only precise information on generics. 925 if (ReceiverRuntimeType.Type->isSpecialized() && 926 ReceiverRuntimeType.Precise) { 927 QualType ReceiverClassPointerType = 928 C.getASTContext().getObjCObjectPointerType(ReceiverClassType); 929 const auto *InferredType = 930 ReceiverClassPointerType->castAs<ObjCObjectPointerType>(); 931 State = State->set<MostSpecializedTypeArgsMap>(RetSym, InferredType); 932 } 933 934 // Constrain the resulting class object to the inferred type. 935 State = setClassObjectDynamicTypeInfo(State, RetSym, ReceiverClassType, 936 !ReceiverRuntimeType.Precise); 937 938 C.addTransition(State); 939 return; 940 } 941 } 942 943 if (Sel.getAsString() == "superclass") { 944 // We try to figure out the type from the receiver of the 'superclass' 945 // message. 946 if (RuntimeType ReceiverRuntimeType = inferReceiverType(M, C)) { 947 948 // Result type would be a super class of the receiver's type. 949 QualType ReceiversSuperClass = 950 ReceiverRuntimeType.Type->getSuperClassType(); 951 952 // Check if it really had super class. 953 // 954 // TODO: we can probably pay closer attention to cases when the class 955 // object can be 'nil' as the result of such message. 956 if (!ReceiversSuperClass.isNull()) { 957 // Constrain the resulting class object to the inferred type. 958 State = setClassObjectDynamicTypeInfo( 959 State, RetSym, ReceiversSuperClass, !ReceiverRuntimeType.Precise); 960 961 C.addTransition(State); 962 } 963 return; 964 } 965 } 966 967 // Tracking for return types. 968 SymbolRef RecSym = M.getReceiverSVal().getAsSymbol(); 969 if (!RecSym) 970 return; 971 972 const ObjCObjectPointerType *const *TrackedType = 973 State->get<MostSpecializedTypeArgsMap>(RecSym); 974 if (!TrackedType) 975 return; 976 977 ASTContext &ASTCtxt = C.getASTContext(); 978 const ObjCMethodDecl *Method = 979 findMethodDecl(MessageExpr, *TrackedType, ASTCtxt); 980 if (!Method) 981 return; 982 983 std::optional<ArrayRef<QualType>> TypeArgs = 984 (*TrackedType)->getObjCSubstitutions(Method->getDeclContext()); 985 if (!TypeArgs) 986 return; 987 988 QualType ResultType = 989 getReturnTypeForMethod(Method, *TypeArgs, *TrackedType, ASTCtxt); 990 // The static type is the same as the deduced type. 991 if (ResultType.isNull()) 992 return; 993 994 const MemRegion *RetRegion = M.getReturnValue().getAsRegion(); 995 ExplodedNode *Pred = C.getPredecessor(); 996 // When there is an entry available for the return symbol in DynamicTypeMap, 997 // the call was inlined, and the information in the DynamicTypeMap is should 998 // be precise. 999 if (RetRegion && !getRawDynamicTypeInfo(State, RetRegion)) { 1000 // TODO: we have duplicated information in DynamicTypeMap and 1001 // MostSpecializedTypeArgsMap. We should only store anything in the later if 1002 // the stored data differs from the one stored in the former. 1003 State = setDynamicTypeInfo(State, RetRegion, ResultType, 1004 /*CanBeSubClassed=*/true); 1005 Pred = C.addTransition(State); 1006 } 1007 1008 const auto *ResultPtrType = ResultType->getAs<ObjCObjectPointerType>(); 1009 1010 if (!ResultPtrType || ResultPtrType->isUnspecialized()) 1011 return; 1012 1013 // When the result is a specialized type and it is not tracked yet, track it 1014 // for the result symbol. 1015 if (!State->get<MostSpecializedTypeArgsMap>(RetSym)) { 1016 State = State->set<MostSpecializedTypeArgsMap>(RetSym, ResultPtrType); 1017 C.addTransition(State, Pred); 1018 } 1019 } 1020 1021 void DynamicTypePropagation::reportGenericsBug( 1022 const ObjCObjectPointerType *From, const ObjCObjectPointerType *To, 1023 ExplodedNode *N, SymbolRef Sym, CheckerContext &C, 1024 const Stmt *ReportedNode) const { 1025 if (!CheckGenerics) 1026 return; 1027 1028 initBugType(); 1029 SmallString<192> Buf; 1030 llvm::raw_svector_ostream OS(Buf); 1031 OS << "Conversion from value of type '"; 1032 QualType::print(From, Qualifiers(), OS, C.getLangOpts(), llvm::Twine()); 1033 OS << "' to incompatible type '"; 1034 QualType::print(To, Qualifiers(), OS, C.getLangOpts(), llvm::Twine()); 1035 OS << "'"; 1036 auto R = std::make_unique<PathSensitiveBugReport>(*ObjCGenericsBugType, 1037 OS.str(), N); 1038 R->markInteresting(Sym); 1039 R->addVisitor(std::make_unique<GenericsBugVisitor>(Sym)); 1040 if (ReportedNode) 1041 R->addRange(ReportedNode->getSourceRange()); 1042 C.emitReport(std::move(R)); 1043 } 1044 1045 PathDiagnosticPieceRef DynamicTypePropagation::GenericsBugVisitor::VisitNode( 1046 const ExplodedNode *N, BugReporterContext &BRC, 1047 PathSensitiveBugReport &BR) { 1048 ProgramStateRef state = N->getState(); 1049 ProgramStateRef statePrev = N->getFirstPred()->getState(); 1050 1051 const ObjCObjectPointerType *const *TrackedType = 1052 state->get<MostSpecializedTypeArgsMap>(Sym); 1053 const ObjCObjectPointerType *const *TrackedTypePrev = 1054 statePrev->get<MostSpecializedTypeArgsMap>(Sym); 1055 if (!TrackedType) 1056 return nullptr; 1057 1058 if (TrackedTypePrev && *TrackedTypePrev == *TrackedType) 1059 return nullptr; 1060 1061 // Retrieve the associated statement. 1062 const Stmt *S = N->getStmtForDiagnostics(); 1063 if (!S) 1064 return nullptr; 1065 1066 const LangOptions &LangOpts = BRC.getASTContext().getLangOpts(); 1067 1068 SmallString<256> Buf; 1069 llvm::raw_svector_ostream OS(Buf); 1070 OS << "Type '"; 1071 QualType::print(*TrackedType, Qualifiers(), OS, LangOpts, llvm::Twine()); 1072 OS << "' is inferred from "; 1073 1074 if (const auto *ExplicitCast = dyn_cast<ExplicitCastExpr>(S)) { 1075 OS << "explicit cast (from '"; 1076 QualType::print(ExplicitCast->getSubExpr()->getType().getTypePtr(), 1077 Qualifiers(), OS, LangOpts, llvm::Twine()); 1078 OS << "' to '"; 1079 QualType::print(ExplicitCast->getType().getTypePtr(), Qualifiers(), OS, 1080 LangOpts, llvm::Twine()); 1081 OS << "')"; 1082 } else if (const auto *ImplicitCast = dyn_cast<ImplicitCastExpr>(S)) { 1083 OS << "implicit cast (from '"; 1084 QualType::print(ImplicitCast->getSubExpr()->getType().getTypePtr(), 1085 Qualifiers(), OS, LangOpts, llvm::Twine()); 1086 OS << "' to '"; 1087 QualType::print(ImplicitCast->getType().getTypePtr(), Qualifiers(), OS, 1088 LangOpts, llvm::Twine()); 1089 OS << "')"; 1090 } else { 1091 OS << "this context"; 1092 } 1093 1094 // Generate the extra diagnostic. 1095 PathDiagnosticLocation Pos(S, BRC.getSourceManager(), 1096 N->getLocationContext()); 1097 return std::make_shared<PathDiagnosticEventPiece>(Pos, OS.str(), true); 1098 } 1099 1100 /// Register checkers. 1101 void ento::registerObjCGenericsChecker(CheckerManager &mgr) { 1102 DynamicTypePropagation *checker = mgr.getChecker<DynamicTypePropagation>(); 1103 checker->CheckGenerics = true; 1104 checker->GenericCheckName = mgr.getCurrentCheckerName(); 1105 } 1106 1107 bool ento::shouldRegisterObjCGenericsChecker(const CheckerManager &mgr) { 1108 return true; 1109 } 1110 1111 void ento::registerDynamicTypePropagation(CheckerManager &mgr) { 1112 mgr.registerChecker<DynamicTypePropagation>(); 1113 } 1114 1115 bool ento::shouldRegisterDynamicTypePropagation(const CheckerManager &mgr) { 1116 return true; 1117 } 1118