1 //===- DynamicTypePropagation.cpp ------------------------------*- C++ -*--===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file contains two checkers. One helps the static analyzer core to track 11 // types, the other does type inference on Obj-C generics and report type 12 // errors. 13 // 14 // Dynamic Type Propagation: 15 // This checker defines the rules for dynamic type gathering and propagation. 16 // 17 // Generics Checker for Objective-C: 18 // This checker tries to find type errors that the compiler is not able to catch 19 // due to the implicit conversions that were introduced for backward 20 // compatibility. 21 // 22 //===----------------------------------------------------------------------===// 23 24 #include "ClangSACheckers.h" 25 #include "clang/AST/RecursiveASTVisitor.h" 26 #include "clang/Basic/Builtins.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/DynamicTypeMap.h" 32 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.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 const ObjCObjectType *getObjectTypeForAllocAndNew(const ObjCMessageExpr *MsgE, 59 CheckerContext &C) const; 60 61 /// \brief Return a better dynamic type if one can be derived from the cast. 62 const ObjCObjectPointerType *getBetterObjCType(const Expr *CastE, 63 CheckerContext &C) const; 64 65 ExplodedNode *dynamicTypePropagationOnCasts(const CastExpr *CE, 66 ProgramStateRef &State, 67 CheckerContext &C) const; 68 69 mutable std::unique_ptr<BugType> ObjCGenericsBugType; 70 void initBugType() const { 71 if (!ObjCGenericsBugType) 72 ObjCGenericsBugType.reset( 73 new BugType(this, "Generics", categories::CoreFoundationObjectiveC)); 74 } 75 76 class GenericsBugVisitor : public BugReporterVisitorImpl<GenericsBugVisitor> { 77 public: 78 GenericsBugVisitor(SymbolRef S) : Sym(S) {} 79 80 void Profile(llvm::FoldingSetNodeID &ID) const override { 81 static int X = 0; 82 ID.AddPointer(&X); 83 ID.AddPointer(Sym); 84 } 85 86 PathDiagnosticPiece *VisitNode(const ExplodedNode *N, 87 const ExplodedNode *PrevN, 88 BugReporterContext &BRC, 89 BugReport &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 }; 113 } // end anonymous namespace 114 115 void DynamicTypePropagation::checkDeadSymbols(SymbolReaper &SR, 116 CheckerContext &C) const { 117 ProgramStateRef State = C.getState(); 118 DynamicTypeMapImpl TypeMap = State->get<DynamicTypeMap>(); 119 for (DynamicTypeMapImpl::iterator I = TypeMap.begin(), E = TypeMap.end(); 120 I != E; ++I) { 121 if (!SR.isLiveRegion(I->first)) { 122 State = State->remove<DynamicTypeMap>(I->first); 123 } 124 } 125 126 if (!SR.hasDeadSymbols()) { 127 C.addTransition(State); 128 return; 129 } 130 131 MostSpecializedTypeArgsMapTy TyArgMap = 132 State->get<MostSpecializedTypeArgsMap>(); 133 for (MostSpecializedTypeArgsMapTy::iterator I = TyArgMap.begin(), 134 E = TyArgMap.end(); 135 I != E; ++I) { 136 if (SR.isDead(I->first)) { 137 State = State->remove<MostSpecializedTypeArgsMap>(I->first); 138 } 139 } 140 141 C.addTransition(State); 142 } 143 144 static void recordFixedType(const MemRegion *Region, const CXXMethodDecl *MD, 145 CheckerContext &C) { 146 assert(Region); 147 assert(MD); 148 149 ASTContext &Ctx = C.getASTContext(); 150 QualType Ty = Ctx.getPointerType(Ctx.getRecordType(MD->getParent())); 151 152 ProgramStateRef State = C.getState(); 153 State = setDynamicTypeInfo(State, Region, Ty, /*CanBeSubclass=*/false); 154 C.addTransition(State); 155 } 156 157 void DynamicTypePropagation::checkPreCall(const CallEvent &Call, 158 CheckerContext &C) const { 159 if (const CXXConstructorCall *Ctor = dyn_cast<CXXConstructorCall>(&Call)) { 160 // C++11 [class.cdtor]p4: When a virtual function is called directly or 161 // indirectly from a constructor or from a destructor, including during 162 // the construction or destruction of the class's non-static data members, 163 // and the object to which the call applies is the object under 164 // construction or destruction, the function called is the final overrider 165 // in the constructor's or destructor's class and not one overriding it in 166 // a more-derived class. 167 168 switch (Ctor->getOriginExpr()->getConstructionKind()) { 169 case CXXConstructExpr::CK_Complete: 170 case CXXConstructExpr::CK_Delegating: 171 // No additional type info necessary. 172 return; 173 case CXXConstructExpr::CK_NonVirtualBase: 174 case CXXConstructExpr::CK_VirtualBase: 175 if (const MemRegion *Target = Ctor->getCXXThisVal().getAsRegion()) 176 recordFixedType(Target, Ctor->getDecl(), C); 177 return; 178 } 179 180 return; 181 } 182 183 if (const CXXDestructorCall *Dtor = dyn_cast<CXXDestructorCall>(&Call)) { 184 // C++11 [class.cdtor]p4 (see above) 185 if (!Dtor->isBaseDestructor()) 186 return; 187 188 const MemRegion *Target = Dtor->getCXXThisVal().getAsRegion(); 189 if (!Target) 190 return; 191 192 const Decl *D = Dtor->getDecl(); 193 if (!D) 194 return; 195 196 recordFixedType(Target, cast<CXXDestructorDecl>(D), C); 197 return; 198 } 199 } 200 201 void DynamicTypePropagation::checkPostCall(const CallEvent &Call, 202 CheckerContext &C) const { 203 // We can obtain perfect type info for return values from some calls. 204 if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(&Call)) { 205 206 // Get the returned value if it's a region. 207 const MemRegion *RetReg = Call.getReturnValue().getAsRegion(); 208 if (!RetReg) 209 return; 210 211 ProgramStateRef State = C.getState(); 212 const ObjCMethodDecl *D = Msg->getDecl(); 213 214 if (D && D->hasRelatedResultType()) { 215 switch (Msg->getMethodFamily()) { 216 default: 217 break; 218 219 // We assume that the type of the object returned by alloc and new are the 220 // pointer to the object of the class specified in the receiver of the 221 // message. 222 case OMF_alloc: 223 case OMF_new: { 224 // Get the type of object that will get created. 225 const ObjCMessageExpr *MsgE = Msg->getOriginExpr(); 226 const ObjCObjectType *ObjTy = getObjectTypeForAllocAndNew(MsgE, C); 227 if (!ObjTy) 228 return; 229 QualType DynResTy = 230 C.getASTContext().getObjCObjectPointerType(QualType(ObjTy, 0)); 231 C.addTransition(setDynamicTypeInfo(State, RetReg, DynResTy, false)); 232 break; 233 } 234 case OMF_init: { 235 // Assume, the result of the init method has the same dynamic type as 236 // the receiver and propagate the dynamic type info. 237 const MemRegion *RecReg = Msg->getReceiverSVal().getAsRegion(); 238 if (!RecReg) 239 return; 240 DynamicTypeInfo RecDynType = getDynamicTypeInfo(State, RecReg); 241 C.addTransition(setDynamicTypeInfo(State, RetReg, RecDynType)); 242 break; 243 } 244 } 245 } 246 return; 247 } 248 249 if (const CXXConstructorCall *Ctor = dyn_cast<CXXConstructorCall>(&Call)) { 250 // We may need to undo the effects of our pre-call check. 251 switch (Ctor->getOriginExpr()->getConstructionKind()) { 252 case CXXConstructExpr::CK_Complete: 253 case CXXConstructExpr::CK_Delegating: 254 // No additional work necessary. 255 // Note: This will leave behind the actual type of the object for 256 // complete constructors, but arguably that's a good thing, since it 257 // means the dynamic type info will be correct even for objects 258 // constructed with operator new. 259 return; 260 case CXXConstructExpr::CK_NonVirtualBase: 261 case CXXConstructExpr::CK_VirtualBase: 262 if (const MemRegion *Target = Ctor->getCXXThisVal().getAsRegion()) { 263 // We just finished a base constructor. Now we can use the subclass's 264 // type when resolving virtual calls. 265 const Decl *D = C.getLocationContext()->getDecl(); 266 recordFixedType(Target, cast<CXXConstructorDecl>(D), C); 267 } 268 return; 269 } 270 } 271 } 272 273 /// TODO: Handle explicit casts. 274 /// Handle C++ casts. 275 /// 276 /// Precondition: the cast is between ObjCObjectPointers. 277 ExplodedNode *DynamicTypePropagation::dynamicTypePropagationOnCasts( 278 const CastExpr *CE, ProgramStateRef &State, CheckerContext &C) const { 279 // We only track type info for regions. 280 const MemRegion *ToR = C.getSVal(CE).getAsRegion(); 281 if (!ToR) 282 return C.getPredecessor(); 283 284 if (isa<ExplicitCastExpr>(CE)) 285 return C.getPredecessor(); 286 287 if (const Type *NewTy = getBetterObjCType(CE, C)) { 288 State = setDynamicTypeInfo(State, ToR, QualType(NewTy, 0)); 289 return C.addTransition(State); 290 } 291 return C.getPredecessor(); 292 } 293 294 void DynamicTypePropagation::checkPostStmt(const CXXNewExpr *NewE, 295 CheckerContext &C) const { 296 if (NewE->isArray()) 297 return; 298 299 // We only track dynamic type info for regions. 300 const MemRegion *MR = C.getSVal(NewE).getAsRegion(); 301 if (!MR) 302 return; 303 304 C.addTransition(setDynamicTypeInfo(C.getState(), MR, NewE->getType(), 305 /*CanBeSubclass=*/false)); 306 } 307 308 const ObjCObjectType * 309 DynamicTypePropagation::getObjectTypeForAllocAndNew(const ObjCMessageExpr *MsgE, 310 CheckerContext &C) const { 311 if (MsgE->getReceiverKind() == ObjCMessageExpr::Class) { 312 if (const ObjCObjectType *ObjTy 313 = MsgE->getClassReceiver()->getAs<ObjCObjectType>()) 314 return ObjTy; 315 } 316 317 if (MsgE->getReceiverKind() == ObjCMessageExpr::SuperClass) { 318 if (const ObjCObjectType *ObjTy 319 = MsgE->getSuperType()->getAs<ObjCObjectType>()) 320 return ObjTy; 321 } 322 323 const Expr *RecE = MsgE->getInstanceReceiver(); 324 if (!RecE) 325 return nullptr; 326 327 RecE= RecE->IgnoreParenImpCasts(); 328 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(RecE)) { 329 const StackFrameContext *SFCtx = C.getStackFrame(); 330 // Are we calling [self alloc]? If this is self, get the type of the 331 // enclosing ObjC class. 332 if (DRE->getDecl() == SFCtx->getSelfDecl()) { 333 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(SFCtx->getDecl())) 334 if (const ObjCObjectType *ObjTy = 335 dyn_cast<ObjCObjectType>(MD->getClassInterface()->getTypeForDecl())) 336 return ObjTy; 337 } 338 } 339 return nullptr; 340 } 341 342 // Return a better dynamic type if one can be derived from the cast. 343 // Compare the current dynamic type of the region and the new type to which we 344 // are casting. If the new type is lower in the inheritance hierarchy, pick it. 345 const ObjCObjectPointerType * 346 DynamicTypePropagation::getBetterObjCType(const Expr *CastE, 347 CheckerContext &C) const { 348 const MemRegion *ToR = C.getSVal(CastE).getAsRegion(); 349 assert(ToR); 350 351 // Get the old and new types. 352 const ObjCObjectPointerType *NewTy = 353 CastE->getType()->getAs<ObjCObjectPointerType>(); 354 if (!NewTy) 355 return nullptr; 356 QualType OldDTy = getDynamicTypeInfo(C.getState(), ToR).getType(); 357 if (OldDTy.isNull()) { 358 return NewTy; 359 } 360 const ObjCObjectPointerType *OldTy = 361 OldDTy->getAs<ObjCObjectPointerType>(); 362 if (!OldTy) 363 return nullptr; 364 365 // Id the old type is 'id', the new one is more precise. 366 if (OldTy->isObjCIdType() && !NewTy->isObjCIdType()) 367 return NewTy; 368 369 // Return new if it's a subclass of old. 370 const ObjCInterfaceDecl *ToI = NewTy->getInterfaceDecl(); 371 const ObjCInterfaceDecl *FromI = OldTy->getInterfaceDecl(); 372 if (ToI && FromI && FromI->isSuperClassOf(ToI)) 373 return NewTy; 374 375 return nullptr; 376 } 377 378 static const ObjCObjectPointerType *getMostInformativeDerivedClassImpl( 379 const ObjCObjectPointerType *From, const ObjCObjectPointerType *To, 380 const ObjCObjectPointerType *MostInformativeCandidate, ASTContext &C) { 381 // Checking if from and to are the same classes modulo specialization. 382 if (From->getInterfaceDecl()->getCanonicalDecl() == 383 To->getInterfaceDecl()->getCanonicalDecl()) { 384 if (To->isSpecialized()) { 385 assert(MostInformativeCandidate->isSpecialized()); 386 return MostInformativeCandidate; 387 } 388 return From; 389 } 390 391 if (To->getObjectType()->getSuperClassType().isNull()) { 392 // If To has no super class and From and To aren't the same then 393 // To was not actually a descendent of From. In this case the best we can 394 // do is 'From'. 395 return From; 396 } 397 398 const auto *SuperOfTo = 399 To->getObjectType()->getSuperClassType()->getAs<ObjCObjectType>(); 400 assert(SuperOfTo); 401 QualType SuperPtrOfToQual = 402 C.getObjCObjectPointerType(QualType(SuperOfTo, 0)); 403 const auto *SuperPtrOfTo = SuperPtrOfToQual->getAs<ObjCObjectPointerType>(); 404 if (To->isUnspecialized()) 405 return getMostInformativeDerivedClassImpl(From, SuperPtrOfTo, SuperPtrOfTo, 406 C); 407 else 408 return getMostInformativeDerivedClassImpl(From, SuperPtrOfTo, 409 MostInformativeCandidate, C); 410 } 411 412 /// A downcast may loose specialization information. E. g.: 413 /// MutableMap<T, U> : Map 414 /// The downcast to MutableMap looses the information about the types of the 415 /// Map (due to the type parameters are not being forwarded to Map), and in 416 /// general there is no way to recover that information from the 417 /// declaration. In order to have to most information, lets find the most 418 /// derived type that has all the type parameters forwarded. 419 /// 420 /// Get the a subclass of \p From (which has a lower bound \p To) that do not 421 /// loose information about type parameters. \p To has to be a subclass of 422 /// \p From. From has to be specialized. 423 static const ObjCObjectPointerType * 424 getMostInformativeDerivedClass(const ObjCObjectPointerType *From, 425 const ObjCObjectPointerType *To, ASTContext &C) { 426 return getMostInformativeDerivedClassImpl(From, To, To, C); 427 } 428 429 /// Inputs: 430 /// \param StaticLowerBound Static lower bound for a symbol. The dynamic lower 431 /// bound might be the subclass of this type. 432 /// \param StaticUpperBound A static upper bound for a symbol. 433 /// \p StaticLowerBound expected to be the subclass of \p StaticUpperBound. 434 /// \param Current The type that was inferred for a symbol in a previous 435 /// context. Might be null when this is the first time that inference happens. 436 /// Precondition: 437 /// \p StaticLowerBound or \p StaticUpperBound is specialized. If \p Current 438 /// is not null, it is specialized. 439 /// Possible cases: 440 /// (1) The \p Current is null and \p StaticLowerBound <: \p StaticUpperBound 441 /// (2) \p StaticLowerBound <: \p Current <: \p StaticUpperBound 442 /// (3) \p Current <: \p StaticLowerBound <: \p StaticUpperBound 443 /// (4) \p StaticLowerBound <: \p StaticUpperBound <: \p Current 444 /// Effect: 445 /// Use getMostInformativeDerivedClass with the upper and lower bound of the 446 /// set {\p StaticLowerBound, \p Current, \p StaticUpperBound}. The computed 447 /// lower bound must be specialized. If the result differs from \p Current or 448 /// \p Current is null, store the result. 449 static bool 450 storeWhenMoreInformative(ProgramStateRef &State, SymbolRef Sym, 451 const ObjCObjectPointerType *const *Current, 452 const ObjCObjectPointerType *StaticLowerBound, 453 const ObjCObjectPointerType *StaticUpperBound, 454 ASTContext &C) { 455 // TODO: The above 4 cases are not exhaustive. In particular, it is possible 456 // for Current to be incomparable with StaticLowerBound, StaticUpperBound, 457 // or both. 458 // 459 // For example, suppose Foo<T> and Bar<T> are unrelated types. 460 // 461 // Foo<T> *f = ... 462 // Bar<T> *b = ... 463 // 464 // id t1 = b; 465 // f = t1; 466 // id t2 = f; // StaticLowerBound is Foo<T>, Current is Bar<T> 467 // 468 // We should either constrain the callers of this function so that the stated 469 // preconditions hold (and assert it) or rewrite the function to expicitly 470 // handle the additional cases. 471 472 // Precondition 473 assert(StaticUpperBound->isSpecialized() || 474 StaticLowerBound->isSpecialized()); 475 assert(!Current || (*Current)->isSpecialized()); 476 477 // Case (1) 478 if (!Current) { 479 if (StaticUpperBound->isUnspecialized()) { 480 State = State->set<MostSpecializedTypeArgsMap>(Sym, StaticLowerBound); 481 return true; 482 } 483 // Upper bound is specialized. 484 const ObjCObjectPointerType *WithMostInfo = 485 getMostInformativeDerivedClass(StaticUpperBound, StaticLowerBound, C); 486 State = State->set<MostSpecializedTypeArgsMap>(Sym, WithMostInfo); 487 return true; 488 } 489 490 // Case (3) 491 if (C.canAssignObjCInterfaces(StaticLowerBound, *Current)) { 492 return false; 493 } 494 495 // Case (4) 496 if (C.canAssignObjCInterfaces(*Current, StaticUpperBound)) { 497 // The type arguments might not be forwarded at any point of inheritance. 498 const ObjCObjectPointerType *WithMostInfo = 499 getMostInformativeDerivedClass(*Current, StaticUpperBound, C); 500 WithMostInfo = 501 getMostInformativeDerivedClass(WithMostInfo, StaticLowerBound, C); 502 if (WithMostInfo == *Current) 503 return false; 504 State = State->set<MostSpecializedTypeArgsMap>(Sym, WithMostInfo); 505 return true; 506 } 507 508 // Case (2) 509 const ObjCObjectPointerType *WithMostInfo = 510 getMostInformativeDerivedClass(*Current, StaticLowerBound, C); 511 if (WithMostInfo != *Current) { 512 State = State->set<MostSpecializedTypeArgsMap>(Sym, WithMostInfo); 513 return true; 514 } 515 516 return false; 517 } 518 519 /// Type inference based on static type information that is available for the 520 /// cast and the tracked type information for the given symbol. When the tracked 521 /// symbol and the destination type of the cast are unrelated, report an error. 522 void DynamicTypePropagation::checkPostStmt(const CastExpr *CE, 523 CheckerContext &C) const { 524 if (CE->getCastKind() != CK_BitCast) 525 return; 526 527 QualType OriginType = CE->getSubExpr()->getType(); 528 QualType DestType = CE->getType(); 529 530 const auto *OrigObjectPtrType = OriginType->getAs<ObjCObjectPointerType>(); 531 const auto *DestObjectPtrType = DestType->getAs<ObjCObjectPointerType>(); 532 533 if (!OrigObjectPtrType || !DestObjectPtrType) 534 return; 535 536 ProgramStateRef State = C.getState(); 537 ExplodedNode *AfterTypeProp = dynamicTypePropagationOnCasts(CE, State, C); 538 539 ASTContext &ASTCtxt = C.getASTContext(); 540 541 // This checker detects the subtyping relationships using the assignment 542 // rules. In order to be able to do this the kindofness must be stripped 543 // first. The checker treats every type as kindof type anyways: when the 544 // tracked type is the subtype of the static type it tries to look up the 545 // methods in the tracked type first. 546 OrigObjectPtrType = OrigObjectPtrType->stripObjCKindOfTypeAndQuals(ASTCtxt); 547 DestObjectPtrType = DestObjectPtrType->stripObjCKindOfTypeAndQuals(ASTCtxt); 548 549 // TODO: erase tracked information when there is a cast to unrelated type 550 // and everything is unspecialized statically. 551 if (OrigObjectPtrType->isUnspecialized() && 552 DestObjectPtrType->isUnspecialized()) 553 return; 554 555 SymbolRef Sym = State->getSVal(CE, C.getLocationContext()).getAsSymbol(); 556 if (!Sym) 557 return; 558 559 // Check which assignments are legal. 560 bool OrigToDest = 561 ASTCtxt.canAssignObjCInterfaces(DestObjectPtrType, OrigObjectPtrType); 562 bool DestToOrig = 563 ASTCtxt.canAssignObjCInterfaces(OrigObjectPtrType, DestObjectPtrType); 564 const ObjCObjectPointerType *const *TrackedType = 565 State->get<MostSpecializedTypeArgsMap>(Sym); 566 567 // Downcasts and upcasts handled in an uniform way regardless of being 568 // explicit. Explicit casts however can happen between mismatched types. 569 if (isa<ExplicitCastExpr>(CE) && !OrigToDest && !DestToOrig) { 570 // Mismatched types. If the DestType specialized, store it. Forget the 571 // tracked type otherwise. 572 if (DestObjectPtrType->isSpecialized()) { 573 State = State->set<MostSpecializedTypeArgsMap>(Sym, DestObjectPtrType); 574 C.addTransition(State, AfterTypeProp); 575 } else if (TrackedType) { 576 State = State->remove<MostSpecializedTypeArgsMap>(Sym); 577 C.addTransition(State, AfterTypeProp); 578 } 579 return; 580 } 581 582 // The tracked type should be the sub or super class of the static destination 583 // type. When an (implicit) upcast or a downcast happens according to static 584 // types, and there is no subtyping relationship between the tracked and the 585 // static destination types, it indicates an error. 586 if (TrackedType && 587 !ASTCtxt.canAssignObjCInterfaces(DestObjectPtrType, *TrackedType) && 588 !ASTCtxt.canAssignObjCInterfaces(*TrackedType, DestObjectPtrType)) { 589 static CheckerProgramPointTag IllegalConv(this, "IllegalConversion"); 590 ExplodedNode *N = C.addTransition(State, AfterTypeProp, &IllegalConv); 591 reportGenericsBug(*TrackedType, DestObjectPtrType, N, Sym, C); 592 return; 593 } 594 595 // Handle downcasts and upcasts. 596 597 const ObjCObjectPointerType *LowerBound = DestObjectPtrType; 598 const ObjCObjectPointerType *UpperBound = OrigObjectPtrType; 599 if (OrigToDest && !DestToOrig) 600 std::swap(LowerBound, UpperBound); 601 602 // The id type is not a real bound. Eliminate it. 603 LowerBound = LowerBound->isObjCIdType() ? UpperBound : LowerBound; 604 UpperBound = UpperBound->isObjCIdType() ? LowerBound : UpperBound; 605 606 if (storeWhenMoreInformative(State, Sym, TrackedType, LowerBound, UpperBound, 607 ASTCtxt)) { 608 C.addTransition(State, AfterTypeProp); 609 } 610 } 611 612 static const Expr *stripCastsAndSugar(const Expr *E) { 613 E = E->IgnoreParenImpCasts(); 614 if (const PseudoObjectExpr *POE = dyn_cast<PseudoObjectExpr>(E)) 615 E = POE->getSyntacticForm()->IgnoreParenImpCasts(); 616 if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) 617 E = OVE->getSourceExpr()->IgnoreParenImpCasts(); 618 return E; 619 } 620 621 static bool isObjCTypeParamDependent(QualType Type) { 622 // It is illegal to typedef parameterized types inside an interface. Therfore 623 // an Objective-C type can only be dependent on a type parameter when the type 624 // parameter structurally present in the type itself. 625 class IsObjCTypeParamDependentTypeVisitor 626 : public RecursiveASTVisitor<IsObjCTypeParamDependentTypeVisitor> { 627 public: 628 IsObjCTypeParamDependentTypeVisitor() : Result(false) {} 629 bool VisitTypedefType(const TypedefType *Type) { 630 if (isa<ObjCTypeParamDecl>(Type->getDecl())) { 631 Result = true; 632 return false; 633 } 634 return true; 635 } 636 637 bool Result; 638 }; 639 640 IsObjCTypeParamDependentTypeVisitor Visitor; 641 Visitor.TraverseType(Type); 642 return Visitor.Result; 643 } 644 645 /// A method might not be available in the interface indicated by the static 646 /// type. However it might be available in the tracked type. In order to 647 /// properly substitute the type parameters we need the declaration context of 648 /// the method. The more specialized the enclosing class of the method is, the 649 /// more likely that the parameter substitution will be successful. 650 static const ObjCMethodDecl * 651 findMethodDecl(const ObjCMessageExpr *MessageExpr, 652 const ObjCObjectPointerType *TrackedType, ASTContext &ASTCtxt) { 653 const ObjCMethodDecl *Method = nullptr; 654 655 QualType ReceiverType = MessageExpr->getReceiverType(); 656 const auto *ReceiverObjectPtrType = 657 ReceiverType->getAs<ObjCObjectPointerType>(); 658 659 // Do this "devirtualization" on instance and class methods only. Trust the 660 // static type on super and super class calls. 661 if (MessageExpr->getReceiverKind() == ObjCMessageExpr::Instance || 662 MessageExpr->getReceiverKind() == ObjCMessageExpr::Class) { 663 // When the receiver type is id, Class, or some super class of the tracked 664 // type, look up the method in the tracked type, not in the receiver type. 665 // This way we preserve more information. 666 if (ReceiverType->isObjCIdType() || ReceiverType->isObjCClassType() || 667 ASTCtxt.canAssignObjCInterfaces(ReceiverObjectPtrType, TrackedType)) { 668 const ObjCInterfaceDecl *InterfaceDecl = TrackedType->getInterfaceDecl(); 669 // The method might not be found. 670 Selector Sel = MessageExpr->getSelector(); 671 Method = InterfaceDecl->lookupInstanceMethod(Sel); 672 if (!Method) 673 Method = InterfaceDecl->lookupClassMethod(Sel); 674 } 675 } 676 677 // Fallback to statick method lookup when the one based on the tracked type 678 // failed. 679 return Method ? Method : MessageExpr->getMethodDecl(); 680 } 681 682 /// Get the returned ObjCObjectPointerType by a method based on the tracked type 683 /// information, or null pointer when the returned type is not an 684 /// ObjCObjectPointerType. 685 static QualType getReturnTypeForMethod( 686 const ObjCMethodDecl *Method, ArrayRef<QualType> TypeArgs, 687 const ObjCObjectPointerType *SelfType, ASTContext &C) { 688 QualType StaticResultType = Method->getReturnType(); 689 690 // Is the return type declared as instance type? 691 if (StaticResultType == C.getObjCInstanceType()) 692 return QualType(SelfType, 0); 693 694 // Check whether the result type depends on a type parameter. 695 if (!isObjCTypeParamDependent(StaticResultType)) 696 return QualType(); 697 698 QualType ResultType = StaticResultType.substObjCTypeArgs( 699 C, TypeArgs, ObjCSubstitutionContext::Result); 700 701 return ResultType; 702 } 703 704 /// When the receiver has a tracked type, use that type to validate the 705 /// argumments of the message expression and the return value. 706 void DynamicTypePropagation::checkPreObjCMessage(const ObjCMethodCall &M, 707 CheckerContext &C) const { 708 ProgramStateRef State = C.getState(); 709 SymbolRef Sym = M.getReceiverSVal().getAsSymbol(); 710 if (!Sym) 711 return; 712 713 const ObjCObjectPointerType *const *TrackedType = 714 State->get<MostSpecializedTypeArgsMap>(Sym); 715 if (!TrackedType) 716 return; 717 718 // Get the type arguments from tracked type and substitute type arguments 719 // before do the semantic check. 720 721 ASTContext &ASTCtxt = C.getASTContext(); 722 const ObjCMessageExpr *MessageExpr = M.getOriginExpr(); 723 const ObjCMethodDecl *Method = 724 findMethodDecl(MessageExpr, *TrackedType, ASTCtxt); 725 726 // It is possible to call non-existent methods in Obj-C. 727 if (!Method) 728 return; 729 730 Optional<ArrayRef<QualType>> TypeArgs = 731 (*TrackedType)->getObjCSubstitutions(Method->getDeclContext()); 732 // This case might happen when there is an unspecialized override of a 733 // specialized method. 734 if (!TypeArgs) 735 return; 736 737 for (unsigned i = 0; i < Method->param_size(); i++) { 738 const Expr *Arg = MessageExpr->getArg(i); 739 const ParmVarDecl *Param = Method->parameters()[i]; 740 741 QualType OrigParamType = Param->getType(); 742 if (!isObjCTypeParamDependent(OrigParamType)) 743 continue; 744 745 QualType ParamType = OrigParamType.substObjCTypeArgs( 746 ASTCtxt, *TypeArgs, ObjCSubstitutionContext::Parameter); 747 // Check if it can be assigned 748 const auto *ParamObjectPtrType = ParamType->getAs<ObjCObjectPointerType>(); 749 const auto *ArgObjectPtrType = 750 stripCastsAndSugar(Arg)->getType()->getAs<ObjCObjectPointerType>(); 751 if (!ParamObjectPtrType || !ArgObjectPtrType) 752 continue; 753 754 // Check if we have more concrete tracked type that is not a super type of 755 // the static argument type. 756 SVal ArgSVal = M.getArgSVal(i); 757 SymbolRef ArgSym = ArgSVal.getAsSymbol(); 758 if (ArgSym) { 759 const ObjCObjectPointerType *const *TrackedArgType = 760 State->get<MostSpecializedTypeArgsMap>(ArgSym); 761 if (TrackedArgType && 762 ASTCtxt.canAssignObjCInterfaces(ArgObjectPtrType, *TrackedArgType)) { 763 ArgObjectPtrType = *TrackedArgType; 764 } 765 } 766 767 // Warn when argument is incompatible with the parameter. 768 if (!ASTCtxt.canAssignObjCInterfaces(ParamObjectPtrType, 769 ArgObjectPtrType)) { 770 static CheckerProgramPointTag Tag(this, "ArgTypeMismatch"); 771 ExplodedNode *N = C.addTransition(State, &Tag); 772 reportGenericsBug(ArgObjectPtrType, ParamObjectPtrType, N, Sym, C, Arg); 773 return; 774 } 775 } 776 } 777 778 /// This callback is used to infer the types for Class variables. This info is 779 /// used later to validate messages that sent to classes. Class variables are 780 /// initialized with by invoking the 'class' method on a class. 781 /// This method is also used to infer the type information for the return 782 /// types. 783 // TODO: right now it only tracks generic types. Extend this to track every 784 // type in the DynamicTypeMap and diagnose type errors! 785 void DynamicTypePropagation::checkPostObjCMessage(const ObjCMethodCall &M, 786 CheckerContext &C) const { 787 const ObjCMessageExpr *MessageExpr = M.getOriginExpr(); 788 789 SymbolRef RetSym = M.getReturnValue().getAsSymbol(); 790 if (!RetSym) 791 return; 792 793 Selector Sel = MessageExpr->getSelector(); 794 ProgramStateRef State = C.getState(); 795 // Inference for class variables. 796 // We are only interested in cases where the class method is invoked on a 797 // class. This method is provided by the runtime and available on all classes. 798 if (MessageExpr->getReceiverKind() == ObjCMessageExpr::Class && 799 Sel.getAsString() == "class") { 800 QualType ReceiverType = MessageExpr->getClassReceiver(); 801 const auto *ReceiverClassType = ReceiverType->getAs<ObjCObjectType>(); 802 QualType ReceiverClassPointerType = 803 C.getASTContext().getObjCObjectPointerType( 804 QualType(ReceiverClassType, 0)); 805 806 if (!ReceiverClassType->isSpecialized()) 807 return; 808 const auto *InferredType = 809 ReceiverClassPointerType->getAs<ObjCObjectPointerType>(); 810 assert(InferredType); 811 812 State = State->set<MostSpecializedTypeArgsMap>(RetSym, InferredType); 813 C.addTransition(State); 814 return; 815 } 816 817 // Tracking for return types. 818 SymbolRef RecSym = M.getReceiverSVal().getAsSymbol(); 819 if (!RecSym) 820 return; 821 822 const ObjCObjectPointerType *const *TrackedType = 823 State->get<MostSpecializedTypeArgsMap>(RecSym); 824 if (!TrackedType) 825 return; 826 827 ASTContext &ASTCtxt = C.getASTContext(); 828 const ObjCMethodDecl *Method = 829 findMethodDecl(MessageExpr, *TrackedType, ASTCtxt); 830 if (!Method) 831 return; 832 833 Optional<ArrayRef<QualType>> TypeArgs = 834 (*TrackedType)->getObjCSubstitutions(Method->getDeclContext()); 835 if (!TypeArgs) 836 return; 837 838 QualType ResultType = 839 getReturnTypeForMethod(Method, *TypeArgs, *TrackedType, ASTCtxt); 840 // The static type is the same as the deduced type. 841 if (ResultType.isNull()) 842 return; 843 844 const MemRegion *RetRegion = M.getReturnValue().getAsRegion(); 845 ExplodedNode *Pred = C.getPredecessor(); 846 // When there is an entry available for the return symbol in DynamicTypeMap, 847 // the call was inlined, and the information in the DynamicTypeMap is should 848 // be precise. 849 if (RetRegion && !State->get<DynamicTypeMap>(RetRegion)) { 850 // TODO: we have duplicated information in DynamicTypeMap and 851 // MostSpecializedTypeArgsMap. We should only store anything in the later if 852 // the stored data differs from the one stored in the former. 853 State = setDynamicTypeInfo(State, RetRegion, ResultType, 854 /*CanBeSubclass=*/true); 855 Pred = C.addTransition(State); 856 } 857 858 const auto *ResultPtrType = ResultType->getAs<ObjCObjectPointerType>(); 859 860 if (!ResultPtrType || ResultPtrType->isUnspecialized()) 861 return; 862 863 // When the result is a specialized type and it is not tracked yet, track it 864 // for the result symbol. 865 if (!State->get<MostSpecializedTypeArgsMap>(RetSym)) { 866 State = State->set<MostSpecializedTypeArgsMap>(RetSym, ResultPtrType); 867 C.addTransition(State, Pred); 868 } 869 } 870 871 void DynamicTypePropagation::reportGenericsBug( 872 const ObjCObjectPointerType *From, const ObjCObjectPointerType *To, 873 ExplodedNode *N, SymbolRef Sym, CheckerContext &C, 874 const Stmt *ReportedNode) const { 875 if (!CheckGenerics) 876 return; 877 878 initBugType(); 879 SmallString<192> Buf; 880 llvm::raw_svector_ostream OS(Buf); 881 OS << "Conversion from value of type '"; 882 QualType::print(From, Qualifiers(), OS, C.getLangOpts(), llvm::Twine()); 883 OS << "' to incompatible type '"; 884 QualType::print(To, Qualifiers(), OS, C.getLangOpts(), llvm::Twine()); 885 OS << "'"; 886 std::unique_ptr<BugReport> R( 887 new BugReport(*ObjCGenericsBugType, OS.str(), N)); 888 R->markInteresting(Sym); 889 R->addVisitor(llvm::make_unique<GenericsBugVisitor>(Sym)); 890 if (ReportedNode) 891 R->addRange(ReportedNode->getSourceRange()); 892 C.emitReport(std::move(R)); 893 } 894 895 PathDiagnosticPiece *DynamicTypePropagation::GenericsBugVisitor::VisitNode( 896 const ExplodedNode *N, const ExplodedNode *PrevN, BugReporterContext &BRC, 897 BugReport &BR) { 898 ProgramStateRef state = N->getState(); 899 ProgramStateRef statePrev = PrevN->getState(); 900 901 const ObjCObjectPointerType *const *TrackedType = 902 state->get<MostSpecializedTypeArgsMap>(Sym); 903 const ObjCObjectPointerType *const *TrackedTypePrev = 904 statePrev->get<MostSpecializedTypeArgsMap>(Sym); 905 if (!TrackedType) 906 return nullptr; 907 908 if (TrackedTypePrev && *TrackedTypePrev == *TrackedType) 909 return nullptr; 910 911 // Retrieve the associated statement. 912 const Stmt *S = nullptr; 913 ProgramPoint ProgLoc = N->getLocation(); 914 if (Optional<StmtPoint> SP = ProgLoc.getAs<StmtPoint>()) { 915 S = SP->getStmt(); 916 } 917 918 if (!S) 919 return nullptr; 920 921 const LangOptions &LangOpts = BRC.getASTContext().getLangOpts(); 922 923 SmallString<256> Buf; 924 llvm::raw_svector_ostream OS(Buf); 925 OS << "Type '"; 926 QualType::print(*TrackedType, Qualifiers(), OS, LangOpts, llvm::Twine()); 927 OS << "' is inferred from "; 928 929 if (const auto *ExplicitCast = dyn_cast<ExplicitCastExpr>(S)) { 930 OS << "explicit cast (from '"; 931 QualType::print(ExplicitCast->getSubExpr()->getType().getTypePtr(), 932 Qualifiers(), OS, LangOpts, llvm::Twine()); 933 OS << "' to '"; 934 QualType::print(ExplicitCast->getType().getTypePtr(), Qualifiers(), OS, 935 LangOpts, llvm::Twine()); 936 OS << "')"; 937 } else if (const auto *ImplicitCast = dyn_cast<ImplicitCastExpr>(S)) { 938 OS << "implicit cast (from '"; 939 QualType::print(ImplicitCast->getSubExpr()->getType().getTypePtr(), 940 Qualifiers(), OS, LangOpts, llvm::Twine()); 941 OS << "' to '"; 942 QualType::print(ImplicitCast->getType().getTypePtr(), Qualifiers(), OS, 943 LangOpts, llvm::Twine()); 944 OS << "')"; 945 } else { 946 OS << "this context"; 947 } 948 949 // Generate the extra diagnostic. 950 PathDiagnosticLocation Pos(S, BRC.getSourceManager(), 951 N->getLocationContext()); 952 return new PathDiagnosticEventPiece(Pos, OS.str(), true, nullptr); 953 } 954 955 /// Register checkers. 956 void ento::registerObjCGenericsChecker(CheckerManager &mgr) { 957 DynamicTypePropagation *checker = 958 mgr.registerChecker<DynamicTypePropagation>(); 959 checker->CheckGenerics = true; 960 } 961 962 void ento::registerDynamicTypePropagation(CheckerManager &mgr) { 963 mgr.registerChecker<DynamicTypePropagation>(); 964 } 965