contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp

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