[Static Analyzer] The first implementation of nullability checker.

[xazax.hun]

Summary

This is the first implementation of a checker that supposed to catch nullability errors.
Unfortunately the nullability qualifiers do not have well defined meaning, one can not assume that nonnull implies that the pointer can not be null.
In fact, the contract is, when the nullability preconditions on the parameter is not violated, then the nullability postconditions of the return value must not be violated either.
Right now the checker only checks simple rules, for example nullable pointers must be checked before dereferenced, should not pass null or unchecked nullable pointer to nonnul parameter, should not return null or unchecked nullable pointer from a nonnull returning function. The check will probably be relaxed, if one of the (not nullable) parameters known to be null, it will be ok to return null or unchecked nonnull pointer from a nonnull returning function.

Some details are still being worked out, how to define the nullability rules (in terms of this checker) to be able to both discover real issues and avoid false positives, while making it possible for users to suppress warnings (possibly using explicit casts). Once the rules are clear, supporting documentation will be provided.

Note: In order to pass the tests, the following patches should be applied first:
http://reviews.llvm.org/D11433
http://reviews.llvm.org/D11432

[xazax.hun]

• Updated to the latest trunk.
• Relaxed an assert in ExprEngine which turned out to be unsound.
• The individual checks can be turned on or off.
• Added some framework specific heuristic to reduce the number of false positive results.
• Refactoring.

[zaks.anna]

Partial review...

lib/StaticAnalyzer/Checkers/Checkers.td

137

Should it be "pointer is used as a nonnull argument"?

149

"nullable pointer is used as a nonnull argument"?

lib/StaticAnalyzer/Checkers/NullabilityChecker.cpp

12

"is" -> "are"

How are we relying on this assumption? What happens if they are not fixed?

Also we should describe what we mean by nullability warnings, maybe refer to the annotations themselves here? It would be great to give a high level overflow of the algorithm and maybe even talk about the difference between the checks?

54

??

70

Same as above - there is no such thing as "nonnull pointer".

152

I don't like that we assume ordering here. Someone might sort the values in the enum and break this. Please, change this.

179

Please, add comments.
What is Source?

192

Is this used for optimization purposes? Can you describe the rules we use here?

What's the benefit of not tracking self?

259

Maybe rename to "getNullabilityAnnotation" ?

267

shouldn't this be an llvm_unreachable?

298

Are we sure that if "!TrackedNullability", the event complains about a dereference on the parent (like field access)?

317

Let's use an existing helper here:
inline bool Type::isAnyPointerType() const {

return isPointerType() || isObjCObjectPointerType();

}

[xazax.hun]

Thank you for the review. I will upload the new version of the patch once the rest of it was reviewed.

lib/StaticAnalyzer/Checkers/NullabilityChecker.cpp

12

There are no assumptions like that in the code of the checker right now. I updated the comment to reflect that.

54

Added a comment to clarify what it is and how it is used.

192

Initially it was not just an optimization. It was also intended to deal with the caching out issue, but eventually it turned out that caching out was ok, and not an error in the checker. I did not erase the code afterwards.

There are several possibilities now:

• Leave this part as it is.
• Only track symbolic regions.
• Delete this function.

Which one do you prefer?

267

There are several AttrKind.
Source: http://clang.llvm.org/doxygen/classclang_1_1AttributedType.html#ab4901f7a37f5539698cb5ebd706245ed

So that code is not unreachable.

298

Sometimes when there is an expression like p[0] or p->field, the event contains the region for the element or the field region. However the tracked information is only available for p. For this reason I also check whether the super region has some tracked nullability and complain about that region in this case.

[zaks.anna]

Another partial review.
Thanks!
Anna.

lib/StaticAnalyzer/Checkers/NullabilityChecker.cpp

312

Please, explain what this method does and add a TODO comment if this needs got be improved in the future.

332

You could cast and check "if (RetSVal.isUndef())" at the same time.

376

Please, add a high-level comment about what this method does.

398

Should you use the existing helper function here as well?

402

A lot of code here looks like a copy and paste from the "checkPreStmt(const ReturnStmt *S," above. Please, factor into a subroutine.

453

I do not understand this comment. You are setting the nullability below..

463

Is calling a function/method with multiple arguments with set nullability tested?

Looks like testArgumentTracking could be used for this but it is never called.

475

Use a subroutine.

496

The next 11 lines could be factored out. They are the same as in the method above.

513

Please, explain why we are ignoring these.
EX: Users might know that objectForKey and objectForKeyedSubscript of NSDictionary always return a non-null value. It's dynamic invariant that the analyzer cannot infer.

Why are we suppressing all methods on NSArray?

524

Again, explain why we have this heuristic.

540

Maybe getting nullability of the receiver could be split into a separate function to simplify readability?

542

+comment
// If the receiver is super, assume it's nonnull.

545

+comment
// Otherwise, look up the nullability info in the state.

558

+ comment:
// If we know that the receiver is constrained to not be null, assume it's nullability is Nonnull, regardless of what the type is.

(Could this actually disagree with what's in the state?)

566

TrackedNullability -> NullabilityOfReturn?

Where is the nullability of the method declaration is bound / stored into the nullability of the return value? (I don't see it happening in the preCall..) I might be missing something. Is this for inlined cases?

569

+ comment

629

Could all this code be factored into shouldTrackRegion helper function?
auto RegionSVal = ExprSVal.getAs<loc::MemRegionVal>();

if (!RegionSVal)
  return;

const MemRegion *Region = RegionSVal->getRegion();
if (!shouldTrackRegion(Region, C.getCurrentAnalysisDeclContext()))
  return;

[zaks.anna]

Gabor, there is a lot of the same steps that all callbacks go through. I think refactoring those into subroutines will help with readability of the checker.

Looking forward to seeing a new version soon!
Anna.

lib/StaticAnalyzer/Checkers/NullabilityChecker.cpp

607

+ comment

// We trust the explicit casts. If there is a disagreement in nullability annotations of destination and source or if '0' is casted to a nonnull type, track the value as having contradictory nullability. This will allow users to suppress nullability warnings.

618

What is users try to suppress a FP using a cast to unspecified?

671

We know that V is not undef here?

676

This comment is not clear.

[xazax.hun]

Addressed the comments.
Added some more tests.
Added a design document.

[xazax.hun]

• Fine tuned the heuristics for cocoa APIs.
• Only track "nullable" and "contradicted" nullability for symbols. Use the rest statically.
• Cleanups.

[zaks.anna]

Looks good overall. I might have additional post-commit comments.

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   MacOSXAPIChecker.cpp
   MallocChecker.cpp
   MallocOverflowSecurityChecker.cpp
   MallocSizeofChecker.cpp
   NSAutoreleasePoolChecker.cpp
   NSErrorChecker.cpp
   NoReturnFunctionChecker.cpp
   NonNullParamChecker.cpp
+  NullabilityChecker.cpp
   ObjCAtSyncChecker.cpp
   ObjCContainersASTChecker.cpp
   ObjCContainersChecker.cpp
   ObjCGenericsChecker.cpp
   ObjCMissingSuperCallChecker.cpp
   ObjCSelfInitChecker.cpp
   ObjCUnusedIVarsChecker.cpp
   PointerArithChecker.cpp

lib/StaticAnalyzer/Checkers/Checkers.td

 //===----------------------------------------------------------------------===//
 
 def Alpha : Package<"alpha">;
 
 def Core : Package<"core">;
 def CoreBuiltin : Package<"builtin">, InPackage<Core>;
 def CoreUninitialized  : Package<"uninitialized">, InPackage<Core>;
 def CoreAlpha : Package<"core">, InPackage<Alpha>, Hidden;
+def Nullability : Package<"nullability">, InPackage<CoreAlpha>, Hidden;
 
 def Cplusplus : Package<"cplusplus">;
 def CplusplusAlpha : Package<"cplusplus">, InPackage<Alpha>, Hidden;
 
 def DeadCode : Package<"deadcode">;
 def DeadCodeAlpha : Package<"deadcode">, InPackage<Alpha>, Hidden;
 
 def Security : Package <"security">;
def CallAndMessageUnInitRefArg : Checker<"CallAndMessageUnInitRefArg">,
   DescFile<"CallAndMessageChecker.cpp">;
 
 def TestAfterDivZeroChecker : Checker<"TestAfterDivZero">,
   HelpText<"Check for division by variable that is later compared against 0. Either the comparison is useless or there is division by zero.">,
   DescFile<"TestAfterDivZeroChecker.cpp">;
 
 } // end "alpha.core"
 
+let ParentPackage = Nullability in {
+
+def NullPassedToNonnullChecker : Checker<"NullPassedToNonnull">,
+  HelpText<"Warns when a null pointer is passed to a nonnull pointer.">,
+  DescFile<"NullabilityChecker.cpp">;
+
+def NullReturnedFromNonnullChecker : Checker<"NullReturnedFromNonnull">,
+  HelpText<"Warns when a null pointer is returned from a nonnull returning function.">,
+  DescFile<"NullabilityChecker.cpp">;
+
+def NullableDereferencedChecker : Checker<"NullableDereferenced">,
+  HelpText<"Warns when a nullable pointer is dereferenced.">,
+  DescFile<"NullabilityChecker.cpp">;
+
+def NullablePassedToNonnullChecker : Checker<"NullablePassedToNonnull">,
+  HelpText<"Warns when a nullable pointer is passed to a nonnull pointer.">,
+  DescFile<"NullabilityChecker.cpp">;
+
+def NullableReturnedFromNonnullChecker : Checker<"NullablePassedToNonnull">,
+  HelpText<"Warns when a nullable pointer is returned from a nonnull returning function.">,
+  DescFile<"NullabilityChecker.cpp">;
+
+} // end "alpha.core.nullability"
+
 //===----------------------------------------------------------------------===//
 // Evaluate "builtin" functions.
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = CoreBuiltin in {
 
 def NoReturnFunctionChecker : Checker<"NoReturnFunctions">,
   HelpText<"Evaluate \"panic\" functions that are known to not return to the caller">,

lib/StaticAnalyzer/Checkers/NullabilityChecker.cpp

+//== Nullabilityhecker.cpp - Nullability checker ----------------*- 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 nullability violations. The assumption of the
+// checker is that, the user is running this checker after all the nullability
+// warnings that is emitted by the compiler was fixed.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "llvm/Support/Path.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/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+enum class Nullability : char {
+  Contradicted, // Tracked nullability is contradicted by an explicit cast.
+  Nullable,
+  Unspecified, // Optimization: Most pointers expected to be unspecified. When
+               // memory region is not stored in the state, it implicitly means
+               // unspecified.
+  Nonnull
+};
+
+static const char *getNullabilityString(Nullability Nullab) {
+  switch (Nullab) {
+  case Nullability::Contradicted:
+    return "contradicted";
+  case Nullability::Nullable:
+    return "nullable";
+  case Nullability::Unspecified:
+    return "unspecified";
+  case Nullability::Nonnull:
+    return "nonnull";
+  }
+  assert(false);
+  return "";
+}
+
+static Nullability getMostNullable(Nullability Lhs, Nullability Rhs) {
+  return static_cast<Nullability>(
+      std::min(static_cast<char>(Lhs), static_cast<char>(Rhs)));
+}
+
+enum class ErrorKind : int {
+  NilAssignedToNonnull,
+  NilPassedToNonnull,
+  NilReturnedToNonnull,
+  NullPointerEnd,
+  NullableAssignedToNonnull,
+  NullableReturnedToNonnull,
+  NullableDereferenced,
+  NullableAssignedToReference,
+  NullablePassedToNonnull
+};
+
+const char *ErrorMessages[] = {
+    "Null pointer is assigned to nonnull pointer",
+    "Null pointer is passed to a nonnull parameter",
+    "Null pointer is returned from a nonnull returning function",
+    nullptr,
+    "Nullable pointer is assigned to nonnull",
+    "Nullable pointer is returned from a nonnull returning function",
+    "Nullable pointer is dereferenced",
+    "Nullable pointer is assigned to a reference",
+    "Nullable pointer is passed to a nonnull parameter"};
+
+class NullabilityChecker
+    : public Checker<check::Bind, check::PreCall, check::PreStmt<ReturnStmt>,
+                     check::PostCall, check::PostStmt<ExplicitCastExpr>,
+                     check::PostObjCMessage, check::DeadSymbols,
+                     check::Event<ImplicitNullDerefEvent>> {
+  mutable std::unique_ptr<BugType> BT;
+
+public:
+  void checkBind(SVal L, SVal V, const Stmt *S, CheckerContext &C) const;
+  void checkPostStmt(const ExplicitCastExpr *CE, CheckerContext &C) const;
+  void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
+  void checkPostObjCMessage(const ObjCMethodCall &M, CheckerContext &C) const;
+  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
+  void checkEvent(ImplicitNullDerefEvent Event) const;
+
+  void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
+                  const char *Sep) const override;
+
+  struct NullabilityChecksFilter {
+    DefaultBool CheckNullPassedToNonnull;
+    DefaultBool CheckNullReturnedFromNonnull;
+    DefaultBool CheckNullableDereferenced;
+    DefaultBool CheckNullablePassedToNonnull;
+    DefaultBool CheckNullableReturnedFromNonnull;
+
+    CheckName CheckNameNullPassedToNonnull;
+    CheckName CheckNameNullReturnedFromNonnull;
+    CheckName CheckNameNullableDereferenced;
+    CheckName CheckNameNullablePassedToNonnull;
+    CheckName CheckNameNullableReturnedFromNonnull;
+  };
+
+  NullabilityChecksFilter Filter;
+
+private:
+  class NullabilityBugVisitor
+      : public BugReporterVisitorImpl<NullabilityBugVisitor> {
+  public:
+    NullabilityBugVisitor(const MemRegion *M) : Region(M) {}
+    ~NullabilityBugVisitor() override {}
+
+    void Profile(llvm::FoldingSetNodeID &ID) const override {
+      static int X = 0;
+      ID.AddPointer(&X);
+      ID.AddPointer(Region);
+    }
+
+    PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
+                                   const ExplodedNode *PrevN,
+                                   BugReporterContext &BRC,
+                                   BugReport &BR) override;
+
+  private:
+    // The tracked region.
+    const MemRegion *Region;
+  };
+
+  void reportBug(ErrorKind Error, ExplodedNode *N, const MemRegion *Region,
+                 BugReporter &BR, const Stmt *ValueExpr = nullptr) const {
+    if (!BT)
+      BT.reset(new BugType(this, "Nullability", "Memory error"));
+    const char *Msg = ErrorMessages[static_cast<int>(Error)];
+    assert(Msg);
+    std::unique_ptr<BugReport> R(new BugReport(*BT, Msg, N));
+    if (Region) {
+      R->markInteresting(Region);
+      R->addVisitor(llvm::make_unique<NullabilityBugVisitor>(Region));
+    }
+    if (ValueExpr) {
+      R->addRange(ValueExpr->getSourceRange());
+      if (Error < ErrorKind::NullPointerEnd)
+        bugreporter::trackNullOrUndefValue(N, ValueExpr, *R);
+    }
+    BR.emitReport(std::move(R));
+  }
+};
+
+class NullabilityState {
+public:
+  NullabilityState(Nullability Nullab, const Stmt *Source = nullptr)
+      : Nullab(Nullab), Source(Source) {}
+
+  const Stmt *getNullabilitySource() const { return Source; }
+
+  Nullability getValue() const { return Nullab; }
+
+  void Profile(llvm::FoldingSetNodeID &ID) const {
+    ID.AddInteger(static_cast<char>(Nullab));
+    ID.AddPointer(Source);
+  }
+
+  void print(raw_ostream &Out) const {
+    Out << getNullabilityString(Nullab) << "\n";
+  }
+
+private:
+  Nullability Nullab;
+  const Stmt *Source;
+};
+
+bool operator==(NullabilityState Lhs, NullabilityState Rhs) {
+  return Lhs.getValue() == Rhs.getValue() &&
+         Lhs.getNullabilitySource() == Rhs.getNullabilitySource();
+}
+
+} // end anonymous namespace
+
+REGISTER_MAP_WITH_PROGRAMSTATE(NullabilityMap, const MemRegion *,
+                               NullabilityState)
+
+static bool shouldTrackRegion(const MemRegion *Region,
+                              AnalysisDeclContext *DeclContext) {
+  // Literals are never null, so we should not track them. This information is
+  // always available.
+  if (Region->getAs<StringRegion>() || Region->getAs<ObjCStringRegion>())
+    return false;
+
+  const SymbolicRegion *SymReg = Region->getAs<SymbolicRegion>();
+  if (!SymReg)
+    return true;
+
+  const SymbolRegionValue *SymRegVal =
+      dyn_cast<SymbolRegionValue>(SymReg->getSymbol());
+  if (!SymRegVal)
+    return true;
+
+  const DeclRegion *MemReg = SymRegVal->getRegion()->getAs<DeclRegion>();
+  if (!MemReg)
+    return true;
+
+  // Self is mostly nonnull. No tracking needed.
+  // FIXME: there are some code that assigns to self.
+  if (MemReg->getDecl() == DeclContext->getSelfDecl())
+    return false;
+
+  return true;
+}
+
+PathDiagnosticPiece *NullabilityChecker::NullabilityBugVisitor::VisitNode(
+    const ExplodedNode *N, const ExplodedNode *PrevN, BugReporterContext &BRC,
+    BugReport &BR) {
+  ProgramStateRef state = N->getState();
+  ProgramStateRef statePrev = PrevN->getState();
+
+  const NullabilityState *TrackedNullab = state->get<NullabilityMap>(Region);
+  const NullabilityState *TrackedNullabPrev =
+      statePrev->get<NullabilityMap>(Region);
+  if (!TrackedNullab)
+    return nullptr;
+
+  if (TrackedNullabPrev &&
+      TrackedNullabPrev->getValue() == TrackedNullab->getValue())
+    return nullptr;
+
+  // Retrieve the associated statement.
+  const Stmt *S = TrackedNullab->getNullabilitySource();
+  if (!S) {
+    ProgramPoint ProgLoc = N->getLocation();
+    if (Optional<StmtPoint> SP = ProgLoc.getAs<StmtPoint>()) {
+      S = SP->getStmt();
+    }
+  }
+
+  if (!S)
+    return nullptr;
+
+  std::string InfoText =
+      (llvm::Twine("Nullability '") +
+       getNullabilityString(TrackedNullab->getValue()) + "' is infered")
+          .str();
+
+  // Generate the extra diagnostic.
+  PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
+                             N->getLocationContext());
+  return new PathDiagnosticEventPiece(Pos, InfoText, true, nullptr);
+}
+
+static Nullability getNullability(QualType Type) {
+  const auto *AttrType = Type->getAs<AttributedType>();
+  if (!AttrType)
+    return Nullability::Unspecified;
+  if (AttrType->getAttrKind() == AttributedType::attr_nullable)
+    return Nullability::Nullable;
+  else if (AttrType->getAttrKind() == AttributedType::attr_nonnull)
+    return Nullability::Nonnull;
+  return Nullability::Unspecified;
+}
+
+void NullabilityChecker::checkDeadSymbols(SymbolReaper &SR,
+                                          CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  NullabilityMapTy Nullabilities = State->get<NullabilityMap>();
+  for (NullabilityMapTy::iterator I = Nullabilities.begin(),
+                                  E = Nullabilities.end();
+       I != E; ++I) {
+    if (!SR.isLiveRegion(I->first)) {
+      State = State->remove<NullabilityMap>(I->first);
+    }
+  }
+}
+
+void NullabilityChecker::checkEvent(ImplicitNullDerefEvent Event) const {
+  SVal DereferencedSVal = Event.Location;
+
+  auto RegionSVal = DereferencedSVal.getAs<loc::MemRegionVal>();
+  if (!RegionSVal)
+    return;
+
+  ProgramStateRef State = Event.SinkNode->getState();
+  const MemRegion *Region = RegionSVal->getRegion();
+  const NullabilityState *TrackedNullability =
+      State->get<NullabilityMap>(Region);
+
+  if (!TrackedNullability) {
+    // Maybe a field or an element is loaded of a nullable pointer.
+    TrackedNullability = State->get<NullabilityMap>(
+        Region->getAs<SubRegion>()->getSuperRegion());
+    if (!TrackedNullability)
+      return;
+  }
+
+  if (Filter.CheckNullableDereferenced &&
+      TrackedNullability->getValue() == Nullability::Nullable) {
+    BugReporter &BR = *Event.BR;
+    reportBug(ErrorKind::NullableDereferenced, Event.SinkNode, Region, BR);
+  }
+}
+
+void NullabilityChecker::checkPreStmt(const ReturnStmt *S,
+                                      CheckerContext &C) const {
+  auto RetExpr = S->getRetValue();
+  if (!RetExpr)
+    return;
+
+  QualType RetExprType = RetExpr->getType();
+  if (!RetExprType->isPointerType() && !RetExprType->isObjCObjectPointerType())
+    return;
+
+  ProgramStateRef State = C.getState();
+  SVal RetSVal = State->getSVal(S, C.getLocationContext());
+  if (RetSVal.isUndef())
+    return;
+
+  AnalysisDeclContext *DeclCtxt =
+      C.getLocationContext()->getAnalysisDeclContext();
+  const FunctionType *FuncType = DeclCtxt->getDecl()->getFunctionType();
+  if (!FuncType)
+    return;
+
+  ConditionTruthVal Nullness =
+      State->isNull(RetSVal.castAs<DefinedOrUnknownSVal>());
+  bool IsNotNull = Nullness.isConstrainedFalse();
+  bool IsNull = Nullness.isConstrainedTrue();
+
+  Nullability StaticNullability = getNullability(FuncType->getReturnType());
+
+  if (Filter.CheckNullReturnedFromNonnull && IsNull &&
+      StaticNullability == Nullability::Nonnull) {
+    static CheckerProgramPointTag Tag(this, "NullReturnedFromNonnull");
+    ExplodedNode *N = C.addTransition(State, C.getPredecessor(), &Tag);
+    reportBug(ErrorKind::NilReturnedToNonnull, N, nullptr, C.getBugReporter(),
+              S);
+    return;
+  }
+
+  auto RetRegionSVal = RetSVal.getAs<loc::MemRegionVal>();
+  if (!RetRegionSVal)
+    return;
+
+  const MemRegion *Region = RetRegionSVal->getRegion();
+  if (!shouldTrackRegion(Region, C.getCurrentAnalysisDeclContext()))
+    return;
+
+  const NullabilityState *TrackedNullability =
+      State->get<NullabilityMap>(Region);
+  if (TrackedNullability) {
+    Nullability TrackedNullabValue = TrackedNullability->getValue();
+    if (Filter.CheckNullableReturnedFromNonnull && !IsNotNull &&
+        TrackedNullabValue == Nullability::Nullable &&
+        StaticNullability == Nullability::Nonnull) {
+      static CheckerProgramPointTag Tag(this, "NullableReturnedFromNonnull");
+      ExplodedNode *N = C.addTransition(State, C.getPredecessor(), &Tag);
+      reportBug(ErrorKind::NullableReturnedToNonnull, N, Region,
+                C.getBugReporter());
+    }
+    return;
+  }
+  if (StaticNullability != Nullability::Unspecified) {
+    State = State->set<NullabilityMap>(Region,
+                                       NullabilityState(StaticNullability, S));
+    C.addTransition(State);
+  }
+}
+
+void NullabilityChecker::checkPreCall(const CallEvent &Call,
+                                      CheckerContext &C) const {
+  if (!Call.getDecl())
+    return;
+
+  ProgramStateRef State = C.getState();
+  ProgramStateRef OrigState = State;
+
+  unsigned Idx = 0;
+  for (const ParmVarDecl *Param : Call.parameters()) {
+    if (Param->isParameterPack())
+      break;
+
+    const Expr *ArgExpr = nullptr;
+    if (Idx < Call.getNumArgs())
+      ArgExpr = Call.getArgExpr(Idx);
+    SVal ArgSVal = Call.getArgSVal(Idx++);
+    if (ArgSVal.isUndef())
+      continue;
+
+    if (!Param->getType()->isPointerType() &&
+        !Param->getType()->isReferenceType() &&
+        !Param->getType()->isObjCObjectPointerType()) {
+      continue;
+    }
+
+    ConditionTruthVal Nullness =
+        State->isNull(ArgSVal.castAs<DefinedOrUnknownSVal>());
+    bool IsNotNull = Nullness.isConstrainedFalse();
+    bool IsNull = Nullness.isConstrainedTrue();
+
+    Nullability ParamNullability = getNullability(Param->getType());
+
+    if (Filter.CheckNullPassedToNonnull && IsNull &&
+        ParamNullability == Nullability::Nonnull) {
+      static CheckerProgramPointTag Tag(this, "NullPassedToNonnull");
+      ExplodedNode *N = C.generateSink(State, C.getPredecessor(), &Tag);
+      reportBug(ErrorKind::NilPassedToNonnull, N, nullptr, C.getBugReporter(),
+                ArgExpr);
+      return;
+    }
+
+    auto ArgRegionSVal = ArgSVal.getAs<loc::MemRegionVal>();
+    if (!ArgRegionSVal)
+      continue;
+
+    const MemRegion *Region = ArgRegionSVal->getRegion();
+    const NullabilityState *TrackedNullability =
+        State->get<NullabilityMap>(Region);
+
+    if (!shouldTrackRegion(Region, C.getCurrentAnalysisDeclContext()))
+      continue;
+
+    if (TrackedNullability) {
+      if (IsNotNull || TrackedNullability->getValue() != Nullability::Nullable)
+        continue;
+
+      if (Filter.CheckNullablePassedToNonnull &&
+          ParamNullability == Nullability::Nonnull) {
+        static CheckerProgramPointTag Tag(this, "NullablePassedToNonnull");
+        ExplodedNode *N = C.generateSink(State, C.getPredecessor(), &Tag);
+        reportBug(ErrorKind::NullablePassedToNonnull, N, Region,
+                  C.getBugReporter(), ArgExpr);
+        return;
+      }
+      if (Filter.CheckNullableDereferenced &&
+          Param->getType()->isReferenceType()) {
+        static CheckerProgramPointTag Tag(this, "NullableDereferenced");
+        ExplodedNode *N = C.generateSink(State, C.getPredecessor(), &Tag);
+        reportBug(ErrorKind::NullableAssignedToReference, N, Region,
+                  C.getBugReporter(), ArgExpr);
+        return;
+      }
+      continue;
+    }
+    // No tracked nullability yet.
+    // Marking memory regions of variables to be nullable would be a mistake.
+    // Marking otherwise is redundant.
+    if (!Region->getAs<SymbolicRegion>())
+      continue;
+    Nullability ArgNullability = getNullability(ArgExpr->getType());
+    if (ArgNullability == Nullability::Unspecified)
+      continue;
+    State = State->set<NullabilityMap>(
+        Region, NullabilityState(ArgNullability, ArgExpr));
+  }
+  if (State != OrigState)
+    C.addTransition(State);
+}
+
+void NullabilityChecker::checkPostCall(const CallEvent &Call,
+                                       CheckerContext &C) const {
+  auto Decl = Call.getDecl();
+  if (!Decl)
+    return;
+  const FunctionType *FuncType = Decl->getFunctionType();
+  if (!FuncType)
+    return;
+  QualType RetType = FuncType->getReturnType();
+  if (!RetType->isPointerType() && !RetType->isObjCObjectPointerType())
+    return;
+  SVal ResultSVal = Call.getReturnValue();
+  auto MemRegVal = ResultSVal.getAs<loc::MemRegionVal>();
+  if (!MemRegVal)
+    return;
+
+  // CG headers are misannotated. Do not warn for symbols that are the results
+  // of CG calls.
+  const SourceManager &SM = C.getSourceManager();
+  StringRef FilePath = SM.getFilename(SM.getSpellingLoc(Decl->getLocStart()));
+  if (llvm::sys::path::filename(FilePath).startswith("CG")) {
+    ProgramStateRef State = C.getState();
+    const MemRegion *Region = MemRegVal->getRegion();
+    State = State->set<NullabilityMap>(Region, Nullability::Contradicted);
+    C.addTransition(State);
+  }
+}
+
+void NullabilityChecker::checkPostObjCMessage(const ObjCMethodCall &M,
+                                              CheckerContext &C) const {
+  auto Decl = M.getDecl();
+  if (!Decl)
+    return;
+  QualType RetType = Decl->getReturnType();
+  if (!RetType->isPointerType() && !RetType->isObjCObjectPointerType())
+    return;
+
+  SVal ResultSVal = M.getReturnValue();
+  auto MemRegVal = ResultSVal.getAs<loc::MemRegionVal>();
+  if (!MemRegVal)
+    return;
+
+  ProgramStateRef State = C.getState();
+  const MemRegion *ReturnRegion = MemRegVal->getRegion();
+
+  auto Interface = Decl->getClassInterface();
+  auto Name = Interface ? Interface->getName() : "";
+  // Frameworks related heuristics.
+  if (Name.startswith("NS")) {
+    // Ignore the return value of container methods.
+    if (Name.find("Array") != StringRef::npos ||
+        Name.find("Dictionary") != StringRef::npos) {
+      State =
+          State->set<NullabilityMap>(ReturnRegion, Nullability::Contradicted);
+      C.addTransition(State);
+      return;
+    }
+
+    // Ignore the return value of string encoding methods.
+    if (Name.find("String") != StringRef::npos) {
+      for (auto Param : M.parameters()) {
+        if (Param->getName() == "encoding") {
+          State = State->set<NullabilityMap>(ReturnRegion,
+                                             Nullability::Contradicted);
+          C.addTransition(State);
+          return;
+        }
+      }
+    }
+  }
+
+  if (!shouldTrackRegion(ReturnRegion, C.getCurrentAnalysisDeclContext()))
+    return;
+
+  const ObjCMessageExpr *Message = M.getOriginExpr();
+  Nullability SelfNullability = Nullability::Unspecified;
+  if (Message->getReceiverKind() == ObjCMessageExpr::SuperClass ||
+      Message->getReceiverKind() == ObjCMessageExpr::SuperInstance) {
+    SelfNullability = Nullability::Nonnull;
+  } else {
+    SVal Receiver = M.getReceiverSVal();
+    auto ValueRegionSVal = Receiver.getAs<loc::MemRegionVal>();
+    if (ValueRegionSVal) {
+      const MemRegion *SelfRegion = ValueRegionSVal->getRegion();
+      assert(SelfRegion);
+
+      const NullabilityState *TrackedSelfNullability =
+          State->get<NullabilityMap>(SelfRegion);
+      if (TrackedSelfNullability) {
+        SelfNullability = TrackedSelfNullability->getValue();
+      }
+    }
+    if (!Receiver.isUndef()) {
+      ConditionTruthVal Nullness =
+          State->isNull(Receiver.castAs<DefinedOrUnknownSVal>());
+      if (Nullness.isConstrainedFalse())
+        SelfNullability = Nullability::Nonnull;
+    }
+  }
+
+  const NullabilityState *TrackedNullability =
+      State->get<NullabilityMap>(ReturnRegion);
+
+  if (TrackedNullability) {
+    Nullability RetValTracked = TrackedNullability->getValue();
+    Nullability ComputedNullab =
+        getMostNullable(RetValTracked, SelfNullability);
+    if (ComputedNullab != RetValTracked &&
+        ComputedNullab != Nullability::Unspecified) {
+      const Stmt *NullabilitySource =
+          ComputedNullab == RetValTracked
+              ? TrackedNullability->getNullabilitySource()
+              : Message->getInstanceReceiver();
+      State = State->set<NullabilityMap>(
+          ReturnRegion, NullabilityState(ComputedNullab, NullabilitySource));
+      C.addTransition(State);
+    }
+    return;
+  }
+
+  // No tracked information. Use static type information for return value.
+  Nullability RetNullability = getNullability(RetType);
+
+  // Properties might be computed. For this reason the static analyzer creates a
+  // new symbol each time an unknown property  is read. To avoid false pozitives
+  // do not treat unknown properties as nullable, even when they explicitly
+  // marked nullable.
+  if (M.getMessageKind() == OCM_PropertyAccess && !C.wasInlined)
+    RetNullability = Nullability::Nonnull;
+
+  Nullability ComputedNullab = getMostNullable(RetNullability, SelfNullability);
+  if (ComputedNullab != Nullability::Unspecified) {
+    const Stmt *NullabilitySource = ComputedNullab == RetNullability
+                                        ? Message
+                                        : Message->getInstanceReceiver();
+    State = State->set<NullabilityMap>(
+        ReturnRegion, NullabilityState(ComputedNullab, NullabilitySource));
+    C.addTransition(State);
+  }
+}
+
+void NullabilityChecker::checkPostStmt(const ExplicitCastExpr *CE,
+                                       CheckerContext &C) const {
+  QualType OriginType = CE->getSubExpr()->getType();
+  QualType DestType = CE->getType();
+  if (!OriginType->isPointerType() && !OriginType->isObjCObjectPointerType())
+    return;
+  if (!DestType->isPointerType() && !DestType->isObjCObjectPointerType())
+    return;
+
+  Nullability DestNullability = getNullability(DestType);
+
+  if (DestNullability == Nullability::Unspecified)
+    return;
+
+  ProgramStateRef State = C.getState();
+  SVal ExprSVal = State->getSVal(CE, C.getLocationContext());
+  auto RegionSVal = ExprSVal.getAs<loc::MemRegionVal>();
+  if (!RegionSVal)
+    return;
+
+  const MemRegion *Region = RegionSVal->getRegion();
+  if (!shouldTrackRegion(Region, C.getCurrentAnalysisDeclContext()))
+    return;
+
+  // When 0 is converted to nonnull mark it as contradicted.
+  if (DestNullability == Nullability::Nonnull && !ExprSVal.isUndef()) {
+    ConditionTruthVal IsNull =
+        State->isNull(ExprSVal.castAs<DefinedOrUnknownSVal>());
+    if (IsNull.isConstrainedTrue()) {
+      State = State->set<NullabilityMap>(Region, Nullability::Contradicted);
+      C.addTransition(State);
+      return;
+    }
+  }
+
+  const NullabilityState *TrackedNullability =
+      State->get<NullabilityMap>(Region);
+
+  if (!TrackedNullability) {
+    State = State->set<NullabilityMap>(Region,
+                                       NullabilityState(DestNullability, CE));
+    C.addTransition(State);
+    return;
+  }
+
+  if (TrackedNullability->getValue() != DestNullability &&
+      TrackedNullability->getValue() != Nullability::Contradicted) {
+    State = State->set<NullabilityMap>(Region, Nullability::Contradicted);
+    C.addTransition(State);
+  }
+}
+
+void NullabilityChecker::checkBind(SVal L, SVal V, const Stmt *S,
+                                   CheckerContext &C) const {
+  const MemRegion *MR = L.getAsRegion();
+  const TypedValueRegion *TVR = dyn_cast_or_null<TypedValueRegion>(MR);
+  if (!TVR)
+    return;
+
+  QualType LocType = TVR->getValueType();
+  if (!LocType->isPointerType() && !LocType->isReferenceType())
+    return;
+
+  ProgramStateRef State = C.getState();
+  ConditionTruthVal IsNull = State->isNull(V.castAs<DefinedOrUnknownSVal>());
+  bool RhsIsNull = IsNull.isConstrainedTrue();
+  bool RhsIsNotNull = IsNull.isConstrainedFalse();
+
+  Nullability LocNullability = getNullability(LocType);
+  // The null pointer is loaded to a reference is handled in another checker.
+  if (Filter.CheckNullPassedToNonnull && RhsIsNull &&
+      LocNullability == Nullability::Nonnull) {
+    static CheckerProgramPointTag Tag(this, "NullPassedToNonnull");
+    ExplodedNode *N = C.addTransition(State, C.getPredecessor(), &Tag);
+    reportBug(ErrorKind::NilAssignedToNonnull, N, nullptr, C.getBugReporter(),
+              S);
+    return;
+  }
+
+  auto ValueRegionSVal = V.getAs<loc::MemRegionVal>();
+  if (!ValueRegionSVal)
+    return;
+
+  const MemRegion *ValueRegion = ValueRegionSVal->getRegion();
+  if (!shouldTrackRegion(ValueRegion, C.getCurrentAnalysisDeclContext()))
+    return;
+
+  Nullability ValNullability = Nullability::Unspecified;
+  if (SymbolRef Sym = V.getAsSymbol())
+    ValNullability = getNullability(Sym->getType());
+
+  const NullabilityState *TrackedNullability =
+      State->get<NullabilityMap>(ValueRegion);
+
+  if (TrackedNullability) {
+    if (RhsIsNotNull || TrackedNullability->getValue() != Nullability::Nullable)
+      return;
+    if (Filter.CheckNullablePassedToNonnull &&
+        LocNullability == Nullability::Nonnull) {
+      static CheckerProgramPointTag Tag(this, "NullablePassedToNonnull");
+      ExplodedNode *N = C.addTransition(State, C.getPredecessor(), &Tag);
+      reportBug(ErrorKind::NullableAssignedToNonnull, N, ValueRegion,
+                C.getBugReporter());
+    }
+    return;
+  }
+
+  const auto *BinOp = dyn_cast<BinaryOperator>(S);
+
+  if (ValNullability != Nullability::Unspecified) {
+    // Trust the static information of the value more than the static
+    // information on the location.
+    const Stmt *NullabilitySource = BinOp ? BinOp->getRHS() : S;
+    State = State->set<NullabilityMap>(
+        ValueRegion, NullabilityState(ValNullability, NullabilitySource));
+    C.addTransition(State);
+    return;
+  }
+
+  if (LocNullability != Nullability::Unspecified) {
+    const Stmt *NullabilitySource = BinOp ? BinOp->getLHS() : S;
+    State = State->set<NullabilityMap>(
+        ValueRegion, NullabilityState(LocNullability, NullabilitySource));
+    C.addTransition(State);
+  }
+}
+
+void NullabilityChecker::printState(raw_ostream &Out, ProgramStateRef State,
+                                    const char *NL, const char *Sep) const {
+
+  NullabilityMapTy B = State->get<NullabilityMap>();
+
+  if (B.isEmpty())
+    return;
+
+  Out << Sep << NL;
+
+  for (NullabilityMapTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
+    Out << I->first << " : ";
+    I->second.print(Out);
+    Out << NL;
+  }
+}
+
+#define REGISTER_CHECKER(name)                                                 \
+  void ento::register##name##Checker(CheckerManager &mgr) {                    \
+    NullabilityChecker *checker = mgr.registerChecker<NullabilityChecker>();   \
+    checker->Filter.Check##name = true;                                        \
+    checker->Filter.CheckName##name = mgr.getCurrentCheckName();               \
+  }
+
+REGISTER_CHECKER(NullPassedToNonnull)
+REGISTER_CHECKER(NullReturnedFromNonnull)
+REGISTER_CHECKER(NullableDereferenced)
+REGISTER_CHECKER(NullablePassedToNonnull)
+REGISTER_CHECKER(NullableReturnedFromNonnull)

lib/StaticAnalyzer/Core/ExprEngineObjC.cpp

if (UpdatedMsg->isInstanceMessage()) {
           // If we raise an exception, for now treat it as a sink.
           // Eventually we will want to handle exceptions properly.
           Bldr.generateSink(ME, Pred, State);
           continue;
         }
         
         // Generate a transition to non-Nil state.
         if (notNilState != State) {
+          ExplodedNode *RealPred = Pred;
           Pred = Bldr.generateNode(ME, Pred, notNilState);
-          assert(Pred && "Should have cached out already!");
+          assert((Pred || RealPred->getLocation().getTag())
+                  && "Should have cached out already!");
+          if (!Pred)
+            continue;
         }
       }
     } else {
       // Check for special class methods that are known to not return
       // and that we should treat as a sink.
       if (ObjCNoRet.isImplicitNoReturn(ME)) {
         // If we raise an exception, for now treat it as a sink.
         // Eventually we will want to handle exceptions properly.

test/Analysis/nullability.mm

+// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.core.nullability -verify %s
+
+#define nil 0
+#define BOOL int
+
+@protocol NSObject
++ (id)alloc;
+- (id)init;
+@end
+
+@protocol NSCopying
+@end
+
+__attribute__((objc_root_class))
+@interface
+NSObject<NSObject>
+@end
+
+@interface NSString : NSObject<NSCopying>
+- (BOOL)isEqualToString : (NSString *_Nonnull)aString;
+- (NSString *)stringByAppendingString:(NSString *_Nonnull)aString;
+@end
+
+@interface TestObject : NSObject
+- (int *_Nonnull)returnsNonnull;
+- (int *_Nullable)returnsNullable;
+- (int *)returnsUnspecified;
+- (void)takesNonnull:(int *_Nonnull)p;
+- (void)takesNullable:(int *_Nullable)p;
+- (void)takesUnspecified:(int *)p;
+@property(readonly, strong) NSString *stuff;
+@end
+
+TestObject * getUnspecifiedTestObject();
+TestObject *_Nonnull getNonnullTestObject();
+TestObject *_Nullable getNullableTestObject();
+
+int getRandom();
+
+typedef struct Dummy { int val; } Dummy;
+
+void takesNullable(Dummy *_Nullable);
+void takesNonnull(Dummy *_Nonnull);
+void takesUnspecified(Dummy *);
+
+Dummy *_Nullable returnsNullable();
+Dummy *_Nonnull returnsNonnull();
+Dummy *returnsUnspecified();
+int *_Nullable returnsNullableInt();
+
+template <typename T> T *eraseNullab(T *p) { return p; }
+
+void testBasicRules() {
+  Dummy *p = returnsNullable();
+  int *ptr = returnsNullableInt();
+  // Make every dereference a different path to avoid sinks after errors.
+  switch (getRandom()) {
+  case 0: {
+    Dummy &r = *p; // expected-warning {{}}
+  } break;
+  case 1: {
+    int b = p->val; // expected-warning {{}}
+  } break;
+  case 2: {
+    int stuff = *ptr; // expected-warning {{}}
+  } break;
+  case 3:
+    takesNonnull(p); // expected-warning {{}}
+    break;
+  case 4: {
+    Dummy d;
+    takesNullable(&d);
+    Dummy dd(d);
+    break;
+  }
+  // Here the copy constructor is called, so a reference is initialized with the
+  // value of p. No ImplicitNullDereference event will be dispatched for this
+  // case. A followup patch is expected to fix this in NonNullParamChecker.
+  default: { Dummy d = *p; } break; // No warning.
+  }
+  if (p) {
+    takesNonnull(p);
+    if (getRandom()) {
+      Dummy &r = *p;
+    } else {
+      int b = p->val;
+    }
+  }
+  Dummy *q = 0;
+  if (getRandom()) {
+    takesNullable(q);
+    takesNonnull(q); // expected-warning {{}}
+  }
+  Dummy a;
+  Dummy *_Nonnull nonnull = &a;
+  nonnull = q; // expected-warning {{}}
+  q = &a;
+  takesNullable(q);
+  takesNonnull(q);
+}
+
+void testArgumentTracking(Dummy *_Nonnull nonnull, Dummy *_Nullable nullable) {
+  Dummy *p = nullable;
+  nonnull = p; // expected-warning {{}}
+  p = 0;
+  Dummy *q = nonnull;
+  q = p;
+}
+
+Dummy *_Nonnull testNullableReturn(Dummy *_Nullable a) {
+  Dummy *p = a;
+  return p; // expected-warning {{}}
+}
+
+Dummy *_Nonnull testNullReturn() {
+  Dummy *p = 0;
+  return p; // expected-warning {{}}
+}
+
+void testObjCMessageResultNullability() {
+  // The expected result: the most nullable of self and method return type.
+  TestObject *o = getUnspecifiedTestObject();
+  int *shouldBeNullable = [eraseNullab(getNullableTestObject()) returnsNonnull];
+  switch (getRandom()) {
+  case 0:
+    // The core analyzer assumes that the receiver is non-null after a message
+    // send. This is to avoid some false positives, and increase performance
+    // but it also reduces the coverage and makes this checker unable to reason
+    // about the nullness of the receiver. 
+    [o takesNonnull:shouldBeNullable]; // No warning expected.
+    break;
+  case 1:
+    shouldBeNullable =
+        [eraseNullab(getNullableTestObject()) returnsUnspecified];
+    [o takesNonnull:shouldBeNullable]; // No warning expected.
+    break;
+  case 3:
+    shouldBeNullable = [eraseNullab(getNullableTestObject()) returnsNullable];
+    [o takesNonnull:shouldBeNullable]; // expected-warning {{}}
+    break;
+  case 4:
+    shouldBeNullable = [eraseNullab(getNonnullTestObject()) returnsNullable];
+    [o takesNonnull:shouldBeNullable]; // expected-warning {{}}
+    break;
+  case 5:
+    shouldBeNullable =
+        [eraseNullab(getUnspecifiedTestObject()) returnsNullable];
+    [o takesNonnull:shouldBeNullable]; // expected-warning {{}}
+    break;
+  case 6:
+    shouldBeNullable = [eraseNullab(getNullableTestObject()) returnsNullable];
+    [o takesNonnull:shouldBeNullable]; // expected-warning {{}}
+    break;
+  case 7: {
+    int *shouldBeNonnull = [eraseNullab(getNonnullTestObject()) returnsNonnull];
+    [o takesNonnull:shouldBeNonnull];
+  } break;
+  }
+}
+
+void testCast() {
+  Dummy *p = (Dummy * _Nonnull)returnsNullable();
+  takesNonnull(p);
+}
+
+void testInvalidPropagation() {
+  Dummy *p = returnsUnspecified();
+  takesNullable(p);
+  takesNonnull(p);
+}