[Static Analyzer] Checker for Obj-C generics

[xazax.hun]

Summary

This checker tries to infer type information based on the Obj-C lightweight generics annotation, and detects type errors that would cause runtime errors.
This type check is not done by the compiler because generic collections convert implicitly to the type erased variants due to backward compatibility.
This checker tries to preserver the type information flow sensitively and spot type errors.

[zaks.anna]

Here is a partial review. Some comments below and others are inline.

Thanks!
Anna.

• Add at least one test that tests for the full error message.
• Add a test that tests path-sensitive output (the plist file) after testing that that looks correct in Xcode. For example, how is GenericsBugVisitor tested? That should be easy with $ awk '{print "// CHECK: "$0}' in.txt > out.txt
• nit: It would be helpful if you could use descriptive names for each test.

lib/StaticAnalyzer/Checkers/Checkers.td

456

Please, provide better description of the checker.

lib/StaticAnalyzer/Checkers/ObjCGenericsChecker.cpp

11

"was" -> "were"

Please, add some documentation on what this checker is trying to catch and how it works.

92

"type with specified params" -> "specialized type"?

Also, maybe we should move this above the GenericsBugVisitor declaration for greater visibility?

173

"two" -> "to"

197

Could you add a comment on what this does?
Is there a precondition on the arguments (To and From)? We seem to be walking up the hierarchy of To.
Is To always guaranteed to have a super class? What ensures that?

224

Move this after the check?

229

Could you explain more why are we skipping kindoff?
Is there a test case for this?
Let's add more __kindof tests.

253

Comment does not seem to match the code below.

257

Should the Map be specialized in this example?

270

We ignore the cast on the else branch (mismatched type)?

280

Simplify the code by using early returns.

Also, try to add comments with intuition on what cases are covered.

297

This will not get caught by the check below?

326

Shouldn't we strip more than id casts?

test/Analysis/generics.m

45

I'd prefer if these were copied directly from the headers, without modifications. Ex:
@interface NSMutableArray<ObjectType> : NSArray<ObjectType>

• (void)addObject:(ObjectType)anObject;

[zaks.anna]

Add tests for checking element retrieval and tracking with ObjC subscript syntax for arrays and dictionaries.

Also see:
http://llvm.org/docs/CodingStandards.html#use-early-exits-and-continue-to-simplify-code
http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

lib/StaticAnalyzer/Checkers/ObjCGenericsChecker.cpp

334

Add comment explaining that this callback is used to infer the types. Specifically, if a class method is called on a symbol, we use it to infer the type of the symbol.

338

Move State down, where it's used.

346

Clarify what you are doing here.

414

Split funding a tighter method definition into a subroutine.

421

Should checking for id, class and kindof be a helper method?

425

What if ASTCtxt.canAssignObjCInterfaces is false here? Shouldn't we warn?
Will we warn elsewhere? Let's make sure we have a test case. And add a comment.

444

Should we use the type on which this is defined and not the tracked type?

453

Why are we not checking other parameter types? Will those bugs get caught by casts? I guess yes..

458

Why isObjCTypeParamDependent is not used here?

485

Let's not shadow TrackedType.

495

This would be simplified if you pull out the negation; you essentially, list the cases where we do not warn on parameters:

1. arg can be assigned to (subtype of) param
2. covariant parameter types and param is a subtype of arg

500

This just returns the previous state.

If you want to create a node, you need to tag it; see the tags on leak reports.

513

We should not use TrackedType in the case lookup failed.
Can the TrackedType be less specialized that the return type?
Maybe rename as IsDeclaredAsInstanceType?

532

What are we doing here?
I prefer not to have any AST pattern matching.

539

This returns predecessor..

[xazax.hun]

Updated to the latest trunk.
Incorporated the suggestions.

[xazax.hun]

Addressed the suggestions.

lib/StaticAnalyzer/Checkers/ObjCGenericsChecker.cpp

257

No, this case handles buggy implementations, when the type parameters are not forwarded. I reworded the comments to make this more clear.

297

You are right, I refactored the code.

326

We should. And we also should strip some sugar. I rewrote that function.

425

The tracked type might be the super class of the static type (for example when the super type is specialized but the subtype is not). We should not warn in that case. When the tracked type is not in subtyping relationship with the static type, there was a cast somewhere, and the checker issued the warning there. I already have testcase for these cases. I updated the names of the tests to reflect this.

444

The type arguments might be only available for the tracked type.

453

The analyzer does not visit template definitions, only the instantiations. I removed this redundant check.

495

The check there was overcomplicated. Passing a subtype of a parameter as argument should always be safe.

513

The lookup might fail when the tracked type is the super of the dynamic type (which might be the subtype of the static type). In some cases the tracked type might even end up be the super type of the static type (when that super type has more information about the type parameters.)

532

Right now in order to keep the state as low as possible, only generic types are tracked. If it is not a problem to have bigger state, a future improvement would be to track the dynamic type of every object, and utilize that info in this checker. Alternatively that could utilize the get/setDynamicTypeInfo API of ProgramState.

test/Analysis/generics.m

45

I added some additional methods for NSArray to do some additional testing, but I made the rest of the methods more similar to the ones in the actual header files.

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   MallocSizeofChecker.cpp
   NSAutoreleasePoolChecker.cpp
   NSErrorChecker.cpp
   NoReturnFunctionChecker.cpp
   NonNullParamChecker.cpp
   ObjCAtSyncChecker.cpp
   ObjCContainersASTChecker.cpp
   ObjCContainersChecker.cpp
+  ObjCGenericsChecker.cpp
   ObjCMissingSuperCallChecker.cpp
   ObjCSelfInitChecker.cpp
   ObjCUnusedIVarsChecker.cpp
   PointerArithChecker.cpp
   PointerSubChecker.cpp
   PthreadLockChecker.cpp
   RetainCountChecker.cpp
   ReturnPointerRangeChecker.cpp

lib/StaticAnalyzer/Checkers/Checkers.td

 def DirectIvarAssignment : Checker<"DirectIvarAssignment">,
   HelpText<"Check for direct assignments to instance variables">,
   DescFile<"DirectIvarAssignment.cpp">;
 
 def DirectIvarAssignmentForAnnotatedFunctions : Checker<"DirectIvarAssignmentForAnnotatedFunctions">,
   HelpText<"Check for direct assignments to instance variables in the methods annotated with objc_no_direct_instance_variable_assignment">,
   DescFile<"DirectIvarAssignment.cpp">;
 
+def ObjCGenericsChecker : Checker<"ObjCGenerics">,
+  HelpText<"Checks for type errors.">,
+  DescFile<"ObjCGenericsChecker.cpp">;
+
 } // end "alpha.osx.cocoa"
 
 let ParentPackage = CoreFoundation in {
 
 def CFNumberCreateChecker : Checker<"CFNumber">,
   HelpText<"Check for proper uses of CFNumberCreate">,
   DescFile<"BasicObjCFoundationChecks.cpp">;
 

lib/StaticAnalyzer/Checkers/ObjCGenericsChecker.cpp

+//=== ObjCGenericsChecker.cpp - Path sensitive checker for Generics *- C++ -*=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This checker tries to find type errors that the compiler is not able to catch
+// due to the implicit conversions that was introduced for backward
+// compatibility.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/AST/ParentMap.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
+using namespace clang;
+using namespace ento;
+
+namespace {
+class ObjCGenericsChecker
+    : public Checker<check::DeadSymbols, check::PreObjCMessage,
+                     check::PostObjCMessage, check::PostStmt<CastExpr>> {
+public:
+  ProgramStateRef checkPointerEscape(ProgramStateRef State,
+                                     const InvalidatedSymbols &Escaped,
+                                     const CallEvent *Call,
+                                     PointerEscapeKind Kind) const;
+
+  void checkPreObjCMessage(const ObjCMethodCall &M, CheckerContext &C) const;
+  void checkPostObjCMessage(const ObjCMethodCall &M, CheckerContext &C) const;
+  void checkPostStmt(const CastExpr *CE, CheckerContext &C) const;
+  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
+
+private:
+  mutable std::unique_ptr<BugType> BT;
+  void initBugType() const {
+    if (!BT)
+      BT.reset(
+          new BugType(this, "Generics", categories::CoreFoundationObjectiveC));
+  }
+
+  class GenericsBugVisitor : public BugReporterVisitorImpl<GenericsBugVisitor> {
+  public:
+    GenericsBugVisitor(SymbolRef S) : Sym(S) {}
+    ~GenericsBugVisitor() override {}
+
+    void Profile(llvm::FoldingSetNodeID &ID) const override {
+      static int X = 0;
+      ID.AddPointer(&X);
+      ID.AddPointer(Sym);
+    }
+
+    PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
+                                   const ExplodedNode *PrevN,
+                                   BugReporterContext &BRC,
+                                   BugReport &BR) override;
+
+  private:
+    // The tracked symbol.
+    SymbolRef Sym;
+  };
+
+  void reportBug(const ObjCObjectPointerType *From,
+                 const ObjCObjectPointerType *To, ExplodedNode *N,
+                 SymbolRef Sym, CheckerContext &C) const {
+    initBugType();
+    SmallString<64> Buf;
+    llvm::raw_svector_ostream OS(Buf);
+    OS << "Incompatible pointer types assigning to '";
+    QualType::print(From, Qualifiers(), OS, C.getLangOpts(), llvm::Twine());
+    OS << "' from '";
+    QualType::print(To, Qualifiers(), OS, C.getLangOpts(), llvm::Twine());
+    OS << "'";
+    std::unique_ptr<BugReport> R(new BugReport(*BT, OS.str(), N));
+    R->markInteresting(Sym);
+    R->addVisitor(llvm::make_unique<GenericsBugVisitor>(Sym));
+    C.emitReport(std::move(R));
+  }
+};
+} // end anonymous namespace
+
+// ProgramState trait - a map from symbol to its type with specified params.
+REGISTER_MAP_WITH_PROGRAMSTATE(TypeParamMap, SymbolRef,
+                               const ObjCObjectPointerType *)
+
+PathDiagnosticPiece *ObjCGenericsChecker::GenericsBugVisitor::VisitNode(
+    const ExplodedNode *N, const ExplodedNode *PrevN, BugReporterContext &BRC,
+    BugReport &BR) {
+  ProgramStateRef state = N->getState();
+  ProgramStateRef statePrev = PrevN->getState();
+
+  const ObjCObjectPointerType *const *TrackedType =
+      state->get<TypeParamMap>(Sym);
+  const ObjCObjectPointerType *const *TrackedTypePrev =
+      statePrev->get<TypeParamMap>(Sym);
+  if (!TrackedType)
+    return nullptr;
+
+  if (TrackedTypePrev && *TrackedTypePrev == *TrackedType)
+    return nullptr;
+
+  // Retrieve the associated statement.
+  const Stmt *S = nullptr;
+  ProgramPoint ProgLoc = N->getLocation();
+  if (Optional<StmtPoint> SP = ProgLoc.getAs<StmtPoint>()) {
+    S = SP->getStmt();
+  }
+
+  if (!S)
+    return nullptr;
+
+  const LangOptions &LangOpts = BRC.getASTContext().getLangOpts();
+
+  SmallString<64> Buf;
+  llvm::raw_svector_ostream OS(Buf);
+  OS << "Type '";
+  QualType::print(*TrackedType, Qualifiers(), OS, LangOpts, llvm::Twine());
+  OS << "' is infered from ";
+
+  if (const auto *ExplicitCast = dyn_cast<ExplicitCastExpr>(S)) {
+    OS << "explicit cast (from '";
+    QualType::print(ExplicitCast->getSubExpr()->getType().getTypePtr(),
+                    Qualifiers(), OS, LangOpts, llvm::Twine());
+    OS << "' to '";
+    QualType::print(ExplicitCast->getType().getTypePtr(), Qualifiers(), OS,
+                    LangOpts, llvm::Twine());
+    OS << "')";
+  } else if (const auto *ImplicitCast = dyn_cast<ImplicitCastExpr>(S)) {
+    OS << "implicit cast (from '";
+    QualType::print(ImplicitCast->getSubExpr()->getType().getTypePtr(),
+                    Qualifiers(), OS, LangOpts, llvm::Twine());
+    OS << "' to '";
+    QualType::print(ImplicitCast->getType().getTypePtr(), Qualifiers(), OS,
+                    LangOpts, llvm::Twine());
+    OS << "')";
+  } else {
+    OS << "this context";
+  }
+
+  // Generate the extra diagnostic.
+  PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
+                             N->getLocationContext());
+  return new PathDiagnosticEventPiece(Pos, OS.str(), true, nullptr);
+}
+
+void ObjCGenericsChecker::checkDeadSymbols(SymbolReaper &SR,
+                                           CheckerContext &C) const {
+  if (!SR.hasDeadSymbols())
+    return;
+
+  ProgramStateRef State = C.getState();
+  TypeParamMapTy TyParMap = State->get<TypeParamMap>();
+  for (TypeParamMapTy::iterator I = TyParMap.begin(), E = TyParMap.end();
+       I != E; ++I) {
+    if (SR.isDead(I->first)) {
+      State = State->remove<TypeParamMap>(I->first);
+    }
+  }
+}
+
+static const ObjCObjectPointerType *getMostInformativeDerivedClassImpl(
+    const ObjCObjectPointerType *From, const ObjCObjectPointerType *To,
+    const ObjCObjectPointerType *MostInformativeCandidate, ASTContext &C) {
+  // Checking if from and two are the same classes modulo specialization.
+  if (From->getInterfaceDecl()->getCanonicalDecl() ==
+      To->getInterfaceDecl()->getCanonicalDecl()) {
+    if (To->isSpecialized()) {
+      assert(MostInformativeCandidate->isSpecialized());
+      return MostInformativeCandidate;
+    }
+    return From;
+  }
+  const auto *SuperOfTo =
+      To->getObjectType()->getSuperClassType()->getAs<ObjCObjectType>();
+  assert(SuperOfTo);
+  QualType SuperPtrOfToQual =
+      C.getObjCObjectPointerType(QualType(SuperOfTo, 0));
+  const auto *SuperPtrOfTo = SuperPtrOfToQual->getAs<ObjCObjectPointerType>();
+  if (To->isUnspecialized())
+    return getMostInformativeDerivedClassImpl(From, SuperPtrOfTo, SuperPtrOfTo,
+                                              C);
+  else
+    return getMostInformativeDerivedClassImpl(From, SuperPtrOfTo,
+                                              MostInformativeCandidate, C);
+}
+
+static const ObjCObjectPointerType *
+getMostInformativeDerivedClass(const ObjCObjectPointerType *From,
+                               const ObjCObjectPointerType *To, ASTContext &C) {
+  return getMostInformativeDerivedClassImpl(From, To, To, C);
+}
+
+static bool storeWhenMoreInformative(ProgramStateRef &State, SymbolRef Sym,
+                                     const ObjCObjectPointerType *const *Old,
+                                     const ObjCObjectPointerType *New,
+                                     ASTContext &C) {
+  if (!Old || C.canAssignObjCInterfaces(*Old, New)) {
+    State = State->set<TypeParamMap>(Sym, New);
+    return true;
+  }
+  return false;
+}
+
+void ObjCGenericsChecker::checkPostStmt(const CastExpr *CE,
+                                        CheckerContext &C) const {
+  if (CE->getCastKind() != CK_BitCast)
+    return;
+
+  QualType OriginType = CE->getSubExpr()->getType();
+  QualType DestType = CE->getType();
+
+  const auto *OrigObjectPtrType = OriginType->getAs<ObjCObjectPointerType>();
+  const auto *DestObjectPtrType = DestType->getAs<ObjCObjectPointerType>();
+
+  ASTContext &ASTCtxt = C.getASTContext();
+
+  if (!OrigObjectPtrType || !DestObjectPtrType)
+    return;
+
+  // In order to detect subtype relation properly, strip the kindofness.
+  OrigObjectPtrType = OrigObjectPtrType->stripObjCKindOfTypeAndQuals(ASTCtxt);
+  DestObjectPtrType = DestObjectPtrType->stripObjCKindOfTypeAndQuals(ASTCtxt);
+
+  const ObjCObjectType *OrigObjectType = OrigObjectPtrType->getObjectType();
+  const ObjCObjectType *DestObjectType = DestObjectPtrType->getObjectType();
+
+  if (OrigObjectType->isUnspecialized() && DestObjectType->isUnspecialized())
+    return;
+
+  ProgramStateRef State = C.getState();
+  SymbolRef Sym = State->getSVal(CE, C.getLocationContext()).getAsSymbol();
+  if (!Sym)
+    return;
+
+  // Check which assignments are legal.
+  bool OrigToDest =
+      ASTCtxt.canAssignObjCInterfaces(DestObjectPtrType, OrigObjectPtrType);
+  bool DestToOrig =
+      ASTCtxt.canAssignObjCInterfaces(OrigObjectPtrType, DestObjectPtrType);
+  const ObjCObjectPointerType *const *TrackedType =
+      State->get<TypeParamMap>(Sym);
+
+  // If OrigObjectType could convert to DestObjectType, this could be an
+  // implicit cast. Handle it as implicit cast.
+  if (isa<ExplicitCastExpr>(CE) && !OrigToDest) {
+    // Trust explicit downcasts.
+    // However a downcast may also lose information. E. g.:
+    //   MutableMap<T, U> : Map
+    // The downcast to mutable map loses the information about the types of the
+    // map, and in general there is no way to recover that information from the
+    // declaration. So no checks possible against APIs that expect specialized
+    // Maps.
+    if (DestToOrig) {
+      const ObjCObjectPointerType *WithMostInfo =
+          getMostInformativeDerivedClass(OrigObjectPtrType, DestObjectPtrType,
+                                         C.getASTContext());
+      if (storeWhenMoreInformative(State, Sym, TrackedType, WithMostInfo,
+                                   ASTCtxt))
+        C.addTransition(State);
+    }
+    return;
+  }
+
+  if (DestObjectType->isUnspecialized()) {
+    // In case we already have some type information for this symbol from a
+    // Specialized -> Specialized conversion, do not record the OrigType,
+    // because it might contain less type information than the tracked type.
+    assert(OrigObjectType->isSpecialized());
+    if (!TrackedType) {
+      State = State->set<TypeParamMap>(Sym, OrigObjectPtrType);
+      C.addTransition(State);
+    }
+  } else {
+    // When upcast happens, store the type with the most information about the
+    // type parameters.
+    if (OrigToDest && !DestToOrig) {
+      const ObjCObjectPointerType *WithMostInfo =
+          getMostInformativeDerivedClass(DestObjectPtrType, OrigObjectPtrType,
+                                         C.getASTContext());
+      // When an (implicit) upcast or a downcast happens according to static
+      // types,the destination type of the cast may contradict the tracked type.
+      // In this case a warning should be emitted.
+      if (TrackedType &&
+          !ASTCtxt.canAssignObjCInterfaces(DestObjectPtrType, *TrackedType) &&
+          !ASTCtxt.canAssignObjCInterfaces(*TrackedType, DestObjectPtrType)) {
+        ExplodedNode *N = C.addTransition();
+        reportBug(*TrackedType, DestObjectPtrType, N, Sym, C);
+        return;
+      }
+      if (storeWhenMoreInformative(State, Sym, TrackedType, WithMostInfo,
+                                   ASTCtxt))
+        C.addTransition(State);
+      return;
+    }
+    // Trust tracked type on unspecialized value -> specialized implicit
+    // downcasts.
+    if (TrackedType) {
+      if (storeWhenMoreInformative(State, Sym, TrackedType, DestObjectPtrType,
+                                   ASTCtxt)) {
+        C.addTransition(State);
+        return;
+      }
+      // Illegal cast.
+      if (!ASTCtxt.canAssignObjCInterfaces(DestObjectPtrType, *TrackedType)) {
+        ExplodedNode *N = C.addTransition();
+        reportBug(*TrackedType, DestObjectPtrType, N, Sym, C);
+      }
+    } else {
+      // Just found out what the type of this symbol should be.
+      State = State->set<TypeParamMap>(Sym, DestObjectPtrType);
+      C.addTransition(State);
+    }
+  }
+}
+
+static const Expr *stripImplicitIdCast(const Expr *E, ASTContext &ASTCtxt) {
+  const ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(E);
+  if (CE && CE->getCastKind() == CK_BitCast &&
+      CE->getType() == ASTCtxt.getObjCIdType())
+    return CE->getSubExpr();
+  else
+    return E;
+}
+
+void ObjCGenericsChecker::checkPostObjCMessage(const ObjCMethodCall &M,
+                                               CheckerContext &C) const {
+  const ObjCMessageExpr *MessageExpr = M.getOriginExpr();
+
+  ProgramStateRef State = C.getState();
+  SymbolRef Sym = M.getReturnValue().getAsSymbol();
+  if (!Sym)
+    return;
+
+  Selector Sel = MessageExpr->getSelector();
+  // When invoking the class selector, store the class to the state.
+  if (MessageExpr->getReceiverKind() != ObjCMessageExpr::Class ||
+      Sel.getAsString() != "class")
+    return;
+
+  QualType ReceiverType = MessageExpr->getClassReceiver();
+  const auto *ReceiverClassType = ReceiverType->getAs<ObjCObjectType>();
+  QualType ReceiverClassPointerType =
+      C.getASTContext().getObjCObjectPointerType(
+          QualType(ReceiverClassType, 0));
+
+  if (!ReceiverClassType->isSpecialized())
+    return;
+  const auto *InferredType =
+      ReceiverClassPointerType->getAs<ObjCObjectPointerType>();
+  assert(InferredType);
+  State = State->set<TypeParamMap>(Sym, InferredType);
+  C.addTransition(State);
+}
+
+class IsObjCTypeParamDependentTypeVisitor
+    : public RecursiveASTVisitor<IsObjCTypeParamDependentTypeVisitor> {
+public:
+  IsObjCTypeParamDependentTypeVisitor() : Result(false) {}
+  bool VisitTypedefType(const TypedefType *Type) {
+    if (isa<ObjCTypeParamDecl>(Type->getDecl())) {
+      Result = true;
+      return false;
+    }
+    return true;
+  }
+  bool getResult() { return Result; }
+
+private:
+  bool Result;
+};
+
+static bool isObjCTypeParamDependent(QualType Type) {
+  IsObjCTypeParamDependentTypeVisitor Visitor;
+  Visitor.TraverseType(Type);
+  return Visitor.getResult();
+}
+
+void ObjCGenericsChecker::checkPreObjCMessage(const ObjCMethodCall &M,
+                                              CheckerContext &C) const {
+  const ObjCMessageExpr *MessageExpr = M.getOriginExpr();
+
+  ProgramStateRef State = C.getState();
+  SymbolRef Sym = M.getReceiverSVal().getAsSymbol();
+  if (!Sym)
+    return;
+
+  QualType ReceiverType = MessageExpr->getReceiverType();
+
+  const auto *ReceiverObjectPtrType =
+      ReceiverType->getAs<ObjCObjectPointerType>();
+
+  if (!ReceiverObjectPtrType)
+    return;
+
+  const ObjCObjectPointerType *const *TrackedType =
+      State->get<TypeParamMap>(Sym);
+  if (!TrackedType)
+    return;
+
+  ASTContext &ASTCtxt = C.getASTContext();
+
+  // Get the type arguments from tracked type and substitute type arguments
+  // before do the semantic check.
+
+  // When the receiver type is id, or some super class of the tracked type (and
+  // kindof type), look up the method in the tracked type, not in the receiver
+  // type. This way we preserve more information. Do this "devirtualization" on
+  // instance and class methods only. Otherwise trust the static type.
+  const ObjCMethodDecl *Method = nullptr;
+  if (MessageExpr->getReceiverKind() == ObjCMessageExpr::Instance ||
+      MessageExpr->getReceiverKind() == ObjCMessageExpr::Class) {
+    if (ASTCtxt.getObjCIdType() == ReceiverType ||
+        ASTCtxt.getObjCClassType() == ReceiverType ||
+        (ReceiverObjectPtrType->getObjectType()->isKindOfType() &&
+         ASTCtxt.canAssignObjCInterfaces(ReceiverObjectPtrType,
+                                         *TrackedType))) {
+      const ObjCInterfaceDecl *InterfaceDecl =
+          (*TrackedType)->getInterfaceDecl();
+      // The method might not be found.
+      Selector Sel = MessageExpr->getSelector();
+      Method = InterfaceDecl->lookupInstanceMethod(Sel);
+      if (!Method)
+        Method = InterfaceDecl->lookupClassMethod(Sel);
+    }
+  }
+
+  if (!Method) {
+    Method = MessageExpr->getMethodDecl();
+    // When arc is disabled non-existent methods can be called.
+    if (!Method)
+      return;
+  }
+
+  Optional<ArrayRef<QualType>> TypeArgs =
+      (*TrackedType)->getObjCSubstitutions(Method->getDeclContext());
+  // This case might happen when there is an unspecialized override of a
+  // specialized method.
+  if (!TypeArgs)
+    return;
+
+  for (unsigned i = 0; i < Method->param_size(); i++) {
+    const Expr *Arg = MessageExpr->getArg(i);
+    // We can't do any type-checking on a type-dependent argument.
+    if (Arg->isTypeDependent())
+      continue;
+
+    const ParmVarDecl *Param = Method->parameters()[i];
+
+    QualType OrigParamType = Param->getType();
+    const auto *ParamTypedef = OrigParamType->getAs<TypedefType>();
+    if (!ParamTypedef)
+      continue;
+
+    const auto *TypeParamDecl =
+        dyn_cast<ObjCTypeParamDecl>(ParamTypedef->getDecl());
+    if (!TypeParamDecl)
+      continue;
+
+    ObjCTypeParamVariance ParamVariance = TypeParamDecl->getVariance();
+
+    QualType ParamType = OrigParamType.substObjCTypeArgs(
+        ASTCtxt, *TypeArgs, ObjCSubstitutionContext::Parameter);
+    // Check if it can be assigned
+    const auto *ParamObjectPtrType = ParamType->getAs<ObjCObjectPointerType>();
+    const auto *ArgObjectPtrType = stripImplicitIdCast(Arg, ASTCtxt)
+                                       ->getType()
+                                       ->getAs<ObjCObjectPointerType>();
+    if (!ParamObjectPtrType || !ArgObjectPtrType)
+      continue;
+
+    // Check if we have more concrete tracked type that is not a super type of
+    // the static argument type.
+    SVal ArgSVal = M.getArgSVal(i);
+    SymbolRef ArgSym = ArgSVal.getAsSymbol();
+    if (ArgSym) {
+      const ObjCObjectPointerType *const *TrackedType =
+          State->get<TypeParamMap>(ArgSym);
+      if (TrackedType && ASTCtxt.canAssignObjCInterfaces(ArgObjectPtrType,
+                                         *TrackedType)){
+        ArgObjectPtrType = *TrackedType;
+      }
+    }
+
+    // For covariant type parameters every subclasses and supertypes are both
+    // accepted.
+    if (!ASTCtxt.canAssignObjCInterfaces(ParamObjectPtrType,
+                                         ArgObjectPtrType) &&
+        (ParamVariance != ObjCTypeParamVariance::Covariant ||
+         !ASTCtxt.canAssignObjCInterfaces(ArgObjectPtrType,
+                                          ParamObjectPtrType))) {
+      ExplodedNode *N = C.addTransition();
+      reportBug(ArgObjectPtrType, ParamObjectPtrType, N, Sym, C);
+      return;
+    }
+  }
+  QualType StaticResultType = Method->getReturnType();
+  // Check whether the result type was a type parameter.
+  bool IsInstanceType = StaticResultType == ASTCtxt.getObjCInstanceType();
+  if (!isObjCTypeParamDependent(StaticResultType) && !IsInstanceType)
+    return;
+
+  QualType ResultType = Method->getReturnType().substObjCTypeArgs(
+      ASTCtxt, *TypeArgs, ObjCSubstitutionContext::Result);
+  if (IsInstanceType)
+    ResultType = QualType(*TrackedType, 0);
+
+  const Stmt *Parent =
+      C.getCurrentAnalysisDeclContext()->getParentMap().getParent(MessageExpr);
+  if (M.getMessageKind() != OCM_Message) {
+    // Properties and subscripts are not direct parents.
+    Parent =
+        C.getCurrentAnalysisDeclContext()->getParentMap().getParent(Parent);
+  }
+
+  const auto *ImplicitCast = dyn_cast_or_null<ImplicitCastExpr>(Parent);
+  if (!ImplicitCast || ImplicitCast->getCastKind() != CK_BitCast)
+    return;
+
+  const auto *ExprTypeAboveCast =
+      ImplicitCast->getType()->getAs<ObjCObjectPointerType>();
+  const auto *ResultPtrType = ResultType->getAs<ObjCObjectPointerType>();
+
+  if (!ExprTypeAboveCast || !ResultPtrType)
+    return;
+
+  // Only warn on unrelated types to avoid too many false positives on
+  // downcasts.
+  if (!ASTCtxt.canAssignObjCInterfaces(ExprTypeAboveCast, ResultPtrType) &&
+      !ASTCtxt.canAssignObjCInterfaces(ResultPtrType, ExprTypeAboveCast)) {
+    ExplodedNode *N = C.addTransition();
+    reportBug(ResultPtrType, ExprTypeAboveCast, N, Sym, C);
+    return;
+  }
+}
+
+/// Register checker.
+void ento::registerObjCGenericsChecker(CheckerManager &mgr) {
+  mgr.registerChecker<ObjCGenericsChecker>();
+}

test/Analysis/generics.m

+// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.osx.cocoa.ObjCGenerics -verify -Wno-objc-method-access %s
+
+#if !__has_feature(objc_generics)
+#  error Compiler does not support Objective-C generics?
+#endif
+
+#if !__has_feature(objc_generics_variance)
+#  error Compiler does not support co- and contr-variance?
+#endif
+
+#define nil 0
+
+@protocol NSObject
++ (id)alloc;
+- (id)init;
+@end
+
+@protocol NSCopying
+@end
+
+__attribute__((objc_root_class))
+@interface NSObject <NSObject>
+@end
+
+@interface NSString : NSObject <NSCopying>
+@end
+
+@interface NSMutableString : NSString
+@end
+
+@interface NSNumber : NSObject <NSCopying>
+@end
+
+@interface NSArray<__covariant T> : NSObject
++ (instancetype)arrayWithObjects:(const T [])objects count:(int)count;
++ (instancetype)getEmpty;
++ (NSArray<T> *)getEmpty2;
+- (int)contains:(T)obj;
+- (T)getObjAtIndex:(int)idx;
+- (T)objectAtIndexedSubscript:(int)idx;
+@property(readonly) T firstObject;
+@end
+
+@interface MutableArray<T> : NSArray<T>
+- (int)addObject:(T)obj;
+@end
+
+@interface LegacyMutableArray : MutableArray
+@end
+
+@interface LegacySpecialMutableArray : LegacyMutableArray
+@end
+
+@interface BuggyMutableArray<T> : MutableArray
+@end
+
+@interface BuggySpecialMutableArray<T> : BuggyMutableArray<T>
+@end
+
+@interface MyMutableStringArray : MutableArray<NSString *>
+@end
+
+@interface ExceptionalArray<ExceptionType> : MutableArray<NSString *>
+- (ExceptionType) getException;
+@end
+
+int getUnknown();
+NSArray *getStuff();
+NSArray *getTypedStuff() {
+  NSArray<NSNumber *> *c = getStuff();
+  return c;
+}
+
+void doStuff(NSArray<NSNumber *> *);
+void withArrString(NSArray<NSString *> *);
+void withArrMutableString(NSArray<NSMutableString *> *);
+void withMutArrString(MutableArray<NSString *> *);
+void withMutArrMutableString(MutableArray<NSMutableString *> *);
+
+void test(NSArray *a, NSArray<NSString *> *b,
+          NSArray<NSNumber *> *c) {
+  a = b;
+  c = a; // expected-warning  {{Incompatible}}
+  [a contains: [[NSNumber alloc] init]]; // expected-warning {{Incompatible}}
+  [a contains: [[NSString alloc] init]];
+  doStuff(a); // expected-warning {{Incompatible}}
+}
+
+void test2() {
+  NSArray<NSString *> *a = getTypedStuff(); // expected-warning {{Incompatible}}
+}
+
+void test3(NSArray *a, NSArray<NSString *> *b) {
+  b = a;
+  [a contains: [[NSNumber alloc] init]]; // expected-warning {{Incompatible}}
+  [a contains: [[NSString alloc] init]];
+  doStuff(a); // expected-warning {{Incompatible}}
+}
+
+void test4(id a, NSArray<NSString *> *b) {
+  b = a;
+  [a contains: [[NSNumber alloc] init]]; // expected-warning {{Incompatible}}
+  [a contains: [[NSString alloc] init]];
+  doStuff(a); // expected-warning {{Incompatible}}
+}
+
+void test5(id a, NSArray<NSString *> *b,
+           NSArray<NSNumber *> *c) {
+  a = b;
+  c = a; // expected-warning {{Incompatible}}
+  [a contains: [[NSNumber alloc] init]]; // expected-warning {{Incompatible}}
+  [a contains: [[NSString alloc] init]];
+  doStuff(a); // expected-warning {{Incompatible}}
+}
+
+void test6(MutableArray *m, MutableArray<NSString *> *a,
+           MutableArray<NSMutableString *> *b) {
+  if (getUnknown() == 5) {
+    m = a;  
+    [m contains: [[NSString alloc] init]];
+  } else {
+    m = b;
+    [m contains: [[NSMutableString alloc] init]];
+  }
+  [m addObject: [[NSString alloc] init]]; // expected-warning {{Incompatible}}
+  [m addObject: [[NSMutableString alloc] init]];
+}
+
+void test8(id a, MutableArray<NSString *> *b) {
+  b = a;
+  doStuff(a); // expected-warning {{Incompatible}}
+}
+
+void test9(MutableArray *a,
+           MutableArray<NSMutableString *> *b) {
+  b = (MutableArray<NSMutableString *> *)a;
+  [a addObject: [[NSString alloc] init]]; // expected-warning {{Incompatible}}
+}
+
+void test10(id d, MyMutableStringArray *a,
+            MutableArray<NSString *> *b,
+            MutableArray<NSNumber *> *c) {
+  d = a;
+  b = d;
+  c = d; // expected-warning {{Incompatible}}
+}
+
+void test11(id d, ExceptionalArray<NSString *> *a,
+            MutableArray<NSString *> *b,
+            MutableArray<NSNumber *> *c) {
+  d = a;
+  [d contains: [[NSString alloc] init]];
+  [d contains: [[NSNumber alloc] init]]; // expected-warning {{Incompatible}}
+  b = d;
+  c = d; // expected-warning {{Incompatible}}
+}
+
+void test12(id d, ExceptionalArray<NSString *> *a,
+            MutableArray<NSString *> *b,
+            MutableArray<NSNumber *> *c) {
+  a = d;
+  [d contains: [[NSString alloc] init]];
+  [d contains: [[NSNumber alloc] init]]; // expected-warning {{Incompatible}}
+  b = d;
+  c = d; // expected-warning {{Incompatible}}
+}
+
+void test13(id a) {
+  withMutArrString(a);
+  withMutArrMutableString(a); // expected-warning {{Incompatible}}
+}
+
+void test14(id a) {
+  withMutArrMutableString(a);
+  withMutArrString(a); // expected-warning {{Incompatible}}
+}
+
+void test15(LegacyMutableArray *a) {
+  withMutArrMutableString(a);
+  withMutArrString(a); // expected-warning {{Incompatible}}
+}
+
+void test16(LegacySpecialMutableArray *a) {
+  withMutArrString(a);
+  withMutArrMutableString(a); // expected-warning {{Incompatible}}
+}
+
+void test17(BuggyMutableArray<NSMutableString *> *a) {
+  withMutArrString(a);
+  withMutArrMutableString(a); // expected-warning {{Incompatible}}
+}
+
+void test18(BuggySpecialMutableArray<NSMutableString *> *a) {
+  withMutArrMutableString(a);
+  withMutArrString(a); // expected-warning {{Incompatible}}
+}
+
+NSArray<NSString *> *getStrings();
+void test19(NSArray<NSNumber *> *a) {
+  NSArray *b = a;
+  // Valid uses of NSArray of NSNumbers.
+  b = getStrings();
+  // Valid uses of NSArray of NSStrings.
+}
+
+void test20(NSArray<NSNumber *> *a) {
+  NSArray *b = a;
+  NSString *str = [b getObjAtIndex: 0]; // expected-warning {{Incompatible}}
+  NSNumber *num = [b getObjAtIndex: 0];
+  str = [b firstObject]; // expected-warning {{Incompatible}}
+  num = [b firstObject];
+  str = b.firstObject; // expected-warning {{Incompatible}}
+  num = b.firstObject;
+  str = b[0]; // expected-warning {{Incompatible}}
+  num = b[0];
+}
+
+void test21(id m, NSArray<NSMutableString *> *a,
+            MutableArray<NSMutableString *> *b) {
+  a = b;
+  if (getUnknown() == 5) {
+    m = a;  
+    [m addObject: [[NSString alloc] init]]; // expected-warning {{Incompatible}}
+  } else {
+    m = b;
+    [m addObject: [[NSMutableString alloc] init]];
+  }
+}
+
+void test22(__kindof NSArray<NSString *> *a,
+            MutableArray<NSMutableString *> *b) {
+  a = b;
+  if (getUnknown() == 5) {
+    [a addObject: [[NSString alloc] init]]; // expected-warning {{Incompatible}}
+  } else {
+    [a addObject: [[NSMutableString alloc] init]];
+  }
+}
+
+void test23() {
+  // ObjCArrayLiterals are not specialized in the AST. 
+  NSArray *arr = @[@"A", @"B"];
+  [arr contains: [[NSNumber alloc] init]];
+}
+
+void test24() {
+  NSArray<NSString *> *arr = @[@"A", @"B"];
+  NSArray *arr2 = arr;
+  [arr2 contains: [[NSNumber alloc] init]]; // expected-warning {{Incompatible}}
+}
+
+void test25(id a, MutableArray<NSMutableString *> *b) {
+  a = b;
+  [a nonExistentMethod];
+}
+
+void test26() {
+  Class c = [NSArray<NSString *> class];
+  NSArray<NSNumber *> *a = [c getEmpty]; // expected-warning {{Incompatible}}
+  a = [c getEmpty2]; // expected-warning {{Incompatible}}
+}
+
+void test27(NSArray<NSArray<NSNumber *> *> *mat, NSArray<NSString *> *row) {
+  id temp = row;
+  [mat contains: temp]; // expected-warning {{Incompatible}}
+}