granicus.if.org Git - clang/blob - lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp

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