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