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