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