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