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