[clang-tidy] new checker cppcoreguidelines-pro-lifetime

[mgehre]

Summary

This checker implements the lifetime rules presented in the paper
by Herb Sutter and Neil MacIntosh paper [1].
Basically, for each "Pointer" we track a set of possible "Owners" to which it
it directly or transitivly points, called its pset (points-to set).
If an Owner is invalidated, all Pointers that contain that Owner
in their pset get an "invalid" pset. For an in-depth explanation, please refer to the paper.

"Pointers" are not only variable with pointer type, but also references,
and objects that contain Pointers (e.g. iterators).

A pset can contain "null", "invalid", "static" (for static duration Owners that cannot
be invalidated), and tuples (Owner, order). Order 0 means that the
Pointer points to the object, e.g. int* p = &i => pset(p) = {(i,0)}.
Order 1 means that the Pointer points to something owned by the object,
e.g. int* p = o.getp() => pset(p) = {(o,1)}.

The paper, and thus the checker, are implemented in a path-independent
way. That leads to some false positives, but increases speed and
allows e.g. to reason about loops without unrolling.

Function bodies are analyzed separately. When calling a function,
the caller can assume how the psets of the Pointers change.
Those assumptions are checked for each analyzed function. (Just like for
const methods; callers assume that the object does not change; bodies of
const methods are not allowed to change the object).

The checker assumes that the code to be checked is valid
according to the C++ Core Guidelines type and bounds profile.
If "forbidden" expressions (such as pointer arithmetic) are used,
or if an unimplemented expression is encountered, the resulting pset
will be "unknown". Psets containing "unknown" will not cause any
warnings by the checker.

The checker will emit the pset of an variable if it finds a call to
"clang_analyzer_pset" in the C++ code. This is used by the tests to
display the pset of a Pointer.

For now, the checker is split into ProLifetimeCheck.cpp and
ProLifetimeVisitor.cpp. The only reason is that it speeds up the
compile time for me. ProLifetimeCheck.cpp is quite slow to compile
(I guess due to ASTMatchers.h). I can happily merge both cpp files before
the commiting, if required.

This checker is not complete. I would like to hear your comments
about high level stuff (e.g. architecture) and what is the best way
forward to get this upstream.

Currently state:

• Pointers are only variables of pointer type or reference type (no

objects containing Pointers, like iterators).

• Psets are computed through all expressions and conditionals.
• "(null)" will be removed from a pset in a branch

if the pointer appears in a conditional guarding that branch. It does
not handle all types of conditionals yet.

• Pointers are invalidated when the Owner they point to goes out of scope.
• Dereferencing invalid pointers is flagged.
• Pointers with static duration will be checked on assignment to only

have a pset of (null) and/or (static). Anything else is flagged.

• CFGs with loops are supported and lead to an iterative refinement
• I have run this on the llvm code base, and the diagnosed issues are mostly related to null pointer dereferencing. I would not call them

false-positives, because this checker assumes that pointer
arguments can be null, and otherwise gsl::not_null should be used.

If you like to see what it can diagnose, look at

test/clang-tidy/cppcoreguidelines-pro-lifetime.cpp

For the internal pset propagation, look at

test/clang-tidy/cppcoreguidelines-pro-lifetime-psets.cpp

(incomplete) TODO:

• track psets for objects containing Pointers
• compute pset of return values and out-parameters in function calls
• check correct pset in 'return' statments
• support annotations for non-standard lifetime behavior

[1] https://github.com/isocpp/CppCoreGuidelines/blob/master/docs/Lifetimes%20I%20and%20II%20-%20v0.9.1.pdf

Depends on D15031

[alexfh]

FYI, I'm waiting with reviewing this change until D15031 is landed, since it can affect this patch.

[mgehre]

Update for renaming in http://reviews.llvm.org/D15031

[aaron.ballman]

Thank you for working on this! A few initial nits (I don't have the chance to complete the review yet, but wanted to get you some early feedback).

clang-tidy/cppcoreguidelines/ProLifetimeCheck.cpp

35–36

These can be combined into a single matcher using anyOf() (should be slightly more efficient than registering two separate matchers).

clang-tidy/cppcoreguidelines/ProLifetimeCheck.h

19

Should write that short description. :-)

clang-tidy/cppcoreguidelines/ProLifetimeVisitor.cpp

95–98

I don't believe there's a need to explicitly default these (here and elsewhere), so they should just be removed.

100–102

Should be O instead of o per our usual conventions, here and elsewhere.

104–105

I would feel more comfortable using std::les<> for this to avoid comparisons between unrelated pointers not having a total ordering.

122

Comments should be properly punctuated (here and elsewhere).

154

Should remove this instead of leaving it commented out.

179

Don't use all caps for enumerators (that's generally reserved for just macros by our conventions), here and elsewhere.

230

I think this should return None instead.

549–550

Reformat the comment to fit a bit better?

553

Method can be const qualified.

[alexfh]

D15031 has landed quite a while ago. Could you rebase the patch?

[mgehre]

Upstreaming of this checker will happen with D63954 and following revisions.

clang-tidy/cppcoreguidelines/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyCppCoreGuidelinesModule
   CppCoreGuidelinesTidyModule.cpp
   ProBoundsArrayToPointerDecayCheck.cpp
   ProBoundsPointerArithmeticCheck.cpp
+  ProLifetimeCheck.cpp
+  ProLifetimeVisitor.cpp
   ProTypeConstCastCheck.cpp
   ProTypeCstyleCastCheck.cpp
   ProTypeReinterpretCastCheck.cpp
   ProTypeStaticCastDowncastCheck.cpp
   ProTypeUnionAccessCheck.cpp
   ProTypeVarargCheck.cpp
 
   LINK_LIBS

clang-tidy/cppcoreguidelines/CppCoreGuidelinesTidyModule.cpp

 //===--- CppCoreGuidelinesModule.cpp - clang-tidy -------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 #include "../misc/AssignOperatorSignatureCheck.h"
 #include "ProBoundsArrayToPointerDecayCheck.h"
 #include "ProBoundsPointerArithmeticCheck.h"
+#include "ProLifetimeCheck.h"
 #include "ProTypeConstCastCheck.h"
 #include "ProTypeCstyleCastCheck.h"
 #include "ProTypeReinterpretCastCheck.h"
 #include "ProTypeStaticCastDowncastCheck.h"
 #include "ProTypeUnionAccessCheck.h"
 #include "ProTypeVarargCheck.h"
 
 namespace clang {
 namespace tidy {
 namespace cppcoreguidelines {
 
 /// A module containing checks of the C++ Core Guidelines
 class CppCoreGuidelinesModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<ProBoundsArrayToPointerDecayCheck>(
         "cppcoreguidelines-pro-bounds-array-to-pointer-decay");
     CheckFactories.registerCheck<ProBoundsPointerArithmeticCheck>(
         "cppcoreguidelines-pro-bounds-pointer-arithmetic");
+    CheckFactories.registerCheck<ProLifetimeCheck>(
+        "cppcoreguidelines-pro-lifetime");
     CheckFactories.registerCheck<ProTypeConstCastCheck>(
         "cppcoreguidelines-pro-type-const-cast");
     CheckFactories.registerCheck<ProTypeCstyleCastCheck>(
         "cppcoreguidelines-pro-type-cstyle-cast");
     CheckFactories.registerCheck<ProTypeReinterpretCastCheck>(
         "cppcoreguidelines-pro-type-reinterpret-cast");
     CheckFactories.registerCheck<ProTypeStaticCastDowncastCheck>(
         "cppcoreguidelines-pro-type-static-cast-downcast");

clang-tidy/cppcoreguidelines/ProLifetimeCheck.h

+//===--- ProLifetimeCheck.h - clang-tidy-------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_CPPCOREGUIDELINES_PRO_LIFETIME_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_CPPCOREGUIDELINES_PRO_LIFETIME_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+
+/// FIXME: Write a short description.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/cppcoreguidelines-pro-lifetime.html
+class ProLifetimeCheck : public ClangTidyCheck {
+  ClangTidyContext *CTContext;
+  bool Debug;
+
+public:
+  ProLifetimeCheck(StringRef Name, ClangTidyContext *Context);
+  void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+};
+
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_CPPCOREGUIDELINES_PRO_LIFETIME_H

clang-tidy/cppcoreguidelines/ProLifetimeCheck.cpp

+//===--- ProLifetimeCheck.cpp - clang-tidy---------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ProLifetimeCheck.h"
+#include "ProLifetimeVisitor.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include <set>
+#include <unordered_map>
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+
+ProLifetimeCheck::ProLifetimeCheck(StringRef Name, ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context), CTContext(Context),
+      Debug(Options.get("Debug", false)) {}
+
+void ProLifetimeCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "Debug", Debug);
+}
+
+void ProLifetimeCheck::registerMatchers(MatchFinder *Finder) {
+  if (!getLangOpts().CPlusPlus)
+    return;
+
+  Finder->addMatcher(functionDecl().bind("fun"), this);
+  Finder->addMatcher(varDecl(hasGlobalStorage()).bind("globalVar"), this);
+}
+
+void ProLifetimeCheck::check(const MatchFinder::MatchResult &Result) {
+  if (const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("fun"))
+    VisitFunction(Func, Result.Context, Result.SourceManager, Debug, CTContext);
+
+  if (const auto *GlobalVar = Result.Nodes.getNodeAs<VarDecl>("globalVar"))
+    VisitGlobalVar(GlobalVar, Result.Context, Result.SourceManager, Debug,
+                   CTContext);
+}
+
+} // namespace tidy
+} // namespace clang

clang-tidy/cppcoreguidelines/ProLifetimeVisitor.h

+/*
+ * ProLifetimeVisitor.h
+ *
+ *  Created on: Oct 23, 2015
+ *      Author: mgehre
+ */
+
+#ifndef CLANG_TIDY_CPPCOREGUIDELINES_PROLIFETIMEVISITOR_H_
+#define CLANG_TIDY_CPPCOREGUIDELINES_PROLIFETIMEVISITOR_H_
+#include "../ClangTidyDiagnosticConsumer.h"
+#include "clang/AST/ASTContext.h"
+
+namespace clang {
+namespace tidy {
+void VisitFunction(const FunctionDecl *Func, ASTContext *ASTCtxt,
+                   SourceManager *SourceMgr, bool DebugPSets,
+                   ClangTidyContext *CTContext);
+void VisitGlobalVar(const VarDecl *V, ASTContext *ASTCtxt,
+                    SourceManager *SourceMgr, bool DebugPSets,
+                    ClangTidyContext *CTContext);
+}
+}
+
+#endif /* CLANG_TIDY_CPPCOREGUIDELINES_PROLIFETIMEVISITOR_H_ */

clang-tidy/cppcoreguidelines/ProLifetimeVisitor.cpp

+//===--- ProLifetimeVisitor.cpp - clang-tidy---------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+// The pset of a (pointer/reference) variable can be modified by
+//   1) Initialization
+//   2) Assignment
+// It will be set to the pset of the expression on the right-hand-side.
+// Such expressions can contain:
+//   1) Casts: Ignored, pset(expr) == pset((cast)expr)
+//   2) Address-Of operator:
+//        It can only be applied to lvalues, i.e.
+//        VarDecl, pset(&a) = {a}
+//        a function returning a ref,
+//        result of an (compound) assignment, pset(&(a = b)) == {b}
+//        pre-in/decrement, pset(&(--a)) = {a}
+//        deref,
+//        array subscript, pset(&a[3]) = {a}
+//        a.b, a.*b: pset(&a.b) = {a}
+//        a->b, a->*b,
+//        comma expr, pset(&(a,b)) = {b}
+//        string literal, pset(&"string") = {static}
+//        static_cast<int&>(x)
+//
+//   3) Dereference operator
+//   4) Function calls and CXXMemberCallExpr
+//   5) MemberExpr: pset(this->a) = {a}; pset_ref(o->a) = {o}; pset_ptr(o->a) =
+//   {o'}
+//   6) Ternary: pset(cond ? a : b) == pset(a) union pset(b)
+//   7) Assignment operator: pset(a = b) == {b}
+// Rules:
+//  1) T& p1 = expr; T* p2 = &expr; -> pset(p1) == pset(p2) == pset_ref(expr)
+//  2) T& p1 = *expr; T* p2 = expr; -> pset(p1) == pset(p2) == pset_ptr(expr)
+//  3) Casts are ignored: pset(expr) == pset((cast)expr)
+//  4) T* p1 = &C.m; -> pset(p1) == {C} (per ex. 1.3)
+//  5) T* p2 = C.get(); -> pset(p2) == {C'} (per ex. 8.1)
+//
+// Assumptions:
+// - The 'this' pointer cannot be invalidated inside a member method (enforced
+// here: no delete on *this)
+// - Global variable's pset is (static) and/or (null) (enforced here)
+// - Arithmetic on pointer types is forbidden (enforced by
+// cppcoreguidelines-pro-type-pointer-arithmetic)
+// - A function does not modify const arguments (enforced by
+// cppcoreguidelines-pro-type-pointer-arithmetic)
+// - An access to an array through array subscription always points inside the
+// array (enforced by cppcoreguidelines-pro-bounds)
+//
+// TODO:
+//  track psets for objects containing Pointers (e.g. iterators)
+//  handle function/method call in PSetFromExpr
+//  check correct use of gsl::owner<> (delete only on 'valid' owner, delete must
+//  happen before owner goes out of scope)
+//  handle try-catch blocks (AC.getCFGBuildOptions().AddEHEdges = true)
+//
+//===----------------------------------------------------------------------===//
+
+#include "ProLifetimeVisitor.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/ExprCXX.h"
+#include "clang/Analysis/Analyses/PostOrderCFGView.h"
+#include "clang/Analysis/CFG.h"
+#include <algorithm>
+#include <map>
+#include <sstream>
+#include <unordered_map>
+
+namespace clang {
+namespace tidy {
+namespace {
+
+/// A Pointer is a
+/// 1) VarDecl or
+/// 2) FieldDecl (on 'this')
+/// and
+/// a) with pointer type, e.g. p in 'int* p' or
+/// b) with reference type, e.g. p in 'int& p' or
+/// c) of an object that contains a Pointer, e.g. p in 'struct { int* q; } p;'
+/// or
+/// TODO: implement case b) and c)
+/// Invariant: VD != FD && (!VD || !FD)
+class Pointer {
+  const VarDecl *VD = nullptr;
+  const FieldDecl *FD = nullptr;
+
+public:
+  Pointer(const VarDecl *VD) : VD(VD) { assert(VD); }
+  Pointer(const FieldDecl *FD) : FD(FD) { assert(FD); }
+  Pointer(Pointer &&) = default;
+  Pointer &operator=(Pointer &&) = default;
+  Pointer(const Pointer &) = default;
+  Pointer &operator=(const Pointer &) = default;
+
+  bool operator==(const Pointer &o) const { return VD == o.VD && FD == o.FD; }
+  bool operator!=(const Pointer &o) const { return !(*this == o); }
+  bool operator<(const Pointer &o) const {
+    if (VD != o.VD)
+      return VD < o.VD;
+    return FD < o.FD;
+  }
+
+  QualType getCanonicalType() const {
+    if (VD)
+      return VD->getType().getCanonicalType();
+    return FD->getType().getCanonicalType();
+  }
+
+  StringRef getName() const {
+    if (VD)
+      return VD->getName();
+    return FD->getName();
+  }
+
+  bool hasGlobalStorage() const { return VD && VD->hasGlobalStorage(); }
+  /// Returns true if this pointer is a member variable of the class of the
+  /// current method
+  bool isMemberVariable() const { return FD; }
+
+  bool mayBeNull() const {
+    // TODO: check if the type is gsl::not_null
+    return isa<PointerType>(getCanonicalType());
+  }
+
+  bool isRealPointer() const { return getCanonicalType()->isPointerType(); }
+  bool isReference() const { return getCanonicalType()->isReferenceType(); }
+
+  std::size_t hash() const noexcept {
+    return VD ? std::hash<const VarDecl *>()(VD)
+              : std::hash<const FieldDecl *>()(FD);
+  }
+
+  // Returns either a Pointer or None if ValD is not a Pointer
+  static Optional<Pointer> get(const ValueDecl *ValD) {
+    if (!ValD)
+      return Optional<Pointer>();
+
+    if (!Pointer::is(ValD->getType().getCanonicalType()))
+      return Optional<Pointer>();
+
+    if (auto *VD = dyn_cast<VarDecl>(ValD))
+      return {VD};
+    if (auto *FD = dyn_cast<FieldDecl>(ValD))
+      return {FD};
+
+    return Optional<Pointer>(); // TODO: can this happen?
+  }
+
+  // static bool is(const ValueDecl *VD) { return get(VD).hasValue(); }
+
+  /// Returns true if the given type has a pset
+  static bool is(QualType QT) {
+    return QT->isReferenceType() || QT->isPointerType();
+  }
+};
+}
+}
+}
+
+namespace std {
+template <> struct hash<clang::tidy::Pointer> {
+  std::size_t operator()(const clang::tidy::Pointer &P) const noexcept {
+    return P.hash();
+  }
+};
+}
+
+namespace clang {
+namespace tidy {
+namespace {
+/// An owner is anything that a Pointer can point to
+/// Invariant: VD != nullptr
+class Owner {
+  enum SpecialType { VARDECL = 0, NULLPTR = 1, STATIC = 2, TEMPORARY = 3 };
+
+  llvm::PointerIntPair<const ValueDecl *, 2> VD;
+
+  Owner(SpecialType ST) : VD(nullptr, ST) {}
+
+public:
+  Owner(const ValueDecl *VD) : VD(VD, VARDECL) {
+    assert(VD);
+    if (const auto *VarD = dyn_cast<VarDecl>(VD))
+      if (VarD->hasGlobalStorage())
+        *this = Static();
+  }
+  Owner(Owner &&) = default;
+  Owner &operator=(Owner &&) = default;
+  Owner(const Owner &) = default;
+  Owner &operator=(const Owner &) = default;
+  bool operator==(const Owner &o) const { return VD == o.VD; }
+  bool operator!=(const Owner &o) const { return !(*this == o); }
+  bool operator<(const Owner &o) const { return VD < o.VD; }
+
+  std::string getName() const {
+
+    switch (VD.getInt()) {
+    case VARDECL:
+      return VD.getPointer()->getNameAsString();
+    case NULLPTR:
+      return "(null)";
+    case STATIC:
+      return "(static)";
+    case TEMPORARY:
+      return "(temporary)";
+    }
+    llvm_unreachable("Unexpected type");
+  }
+
+  /// Special Owner to refer to a nullptr
+  static Owner Null() { return Owner(NULLPTR); }
+
+  /// An owner that can not be invalidated.
+  /// Used for variables with static duration
+  static Owner Static() { return Owner(STATIC); }
+
+  /// An owner that will vanish at the end of the full expression,
+  /// e.g. a temporary bound to const reference parameter.
+  static Owner Temporary() { return Owner(TEMPORARY); }
+
+  /// Returns either a Pointer or None if Owner is not a Pointer
+  Optional<Pointer> getPointer() const {
+    if (VD.getInt() == VARDECL)
+      return Pointer::get(VD.getPointer());
+    return Optional<Pointer>();
+  }
+};
+
+/// The reason why a pset became invalid
+/// Invariant: (Reason != POINTEE_LEFT_SCOPE || Pointee) && Loc.isValid()
+class InvalidationReason {
+  enum { NOT_INITIALIZED, POINTEE_LEFT_SCOPE, TEMPORARY_LEFT_SCOPE } Reason;
+  const VarDecl *Pointee = nullptr;
+  SourceLocation Loc;
+  InvalidationReason() = default;
+
+public:
+  SourceLocation getLoc() const { return Loc; }
+
+  std::string str() const {
+    switch (Reason) {
+    case NOT_INITIALIZED:
+      return "was never initialized";
+    case POINTEE_LEFT_SCOPE:
+      assert(Pointee);
+      return std::string("the pointee ") + Pointee->getNameAsString() +
+             " left the scope";
+    case TEMPORARY_LEFT_SCOPE:
+      return "temporary was destroyed at the end of the full expression";
+    }
+    return "";
+  }
+
+  static InvalidationReason NotInitialized(SourceLocation Loc) {
+    assert(Loc.isValid());
+    InvalidationReason R;
+    R.Loc = Loc;
+    R.Reason = NOT_INITIALIZED;
+    return R;
+  }
+
+  static InvalidationReason PointeeLeftScope(SourceLocation Loc,
+                                             const VarDecl *Pointee) {
+    assert(Loc.isValid());
+    assert(Pointee);
+    InvalidationReason R;
+    R.Loc = Loc;
+    R.Reason = POINTEE_LEFT_SCOPE;
+    R.Pointee = Pointee;
+    return R;
+  }
+
+  static InvalidationReason TemporaryLeftScope(SourceLocation Loc) {
+    assert(Loc.isValid());
+    InvalidationReason R;
+    R.Loc = Loc;
+    R.Reason = TEMPORARY_LEFT_SCOPE;
+    return R;
+  }
+};
+
+/// A pset (points-to set) can be unknown, invalid or valid.
+/// If it is valid, it can contain (static), (null) and a set of (Owner,order)
+/// Invariant: (!isInvalid() || Reason.hasValue())
+///         && (!isValid() || p.size() > 0)
+class PSet {
+public:
+  enum State {
+    Valid,           // the pointer points to one element of p
+    Unknown,         // we lost track of what it could point to
+    PossiblyInvalid, // the pointer had a pset containing multiple objects, and
+                     // one of them was killed
+    Invalid, // the pointer was never initialized or the single member of its
+             // pset was killed
+  };
+
+  PSet() : state(Unknown) {}
+
+  PSet(PSet &&) = default;
+  PSet &operator=(PSet &&) = default;
+  PSet(const PSet &) = default;
+  PSet &operator=(const PSet &) = default;
+
+  bool operator==(const PSet &o) const {
+    if (state == Valid)
+      return o.p == p;
+    return state == o.state;
+  }
+
+  bool operator!=(const PSet &o) const { return !(*this == o); }
+
+  State getState() const { return state; }
+
+  InvalidationReason getReason() const {
+    assert(isInvalid());
+    assert(Reason.hasValue());
+    return Reason.getValue();
+  }
+
+  bool isValid() const { return state == Valid; }
+
+  bool isInvalid() const {
+    return state == Invalid || state == PossiblyInvalid;
+  }
+
+  bool isUnknown() const { return state == Unknown; }
+
+  /// Returns true if this pset contains Owner with the same or a lower order
+  /// i.e. if invalidating (Owner, order) would invalidate this pset
+  bool contains(Owner Owner, unsigned order) const {
+    if (state != Valid)
+      return false;
+
+    for (const auto &i : p)
+      if (i.first == Owner && i.second >= order)
+        return true;
+
+    return false;
+  }
+
+  bool isSingular() const { return p.size() == 1; }
+
+  bool containsNull() const { return contains(Owner::Null(), 0); }
+
+  void removeNull() {
+    assert(isValid());
+    p.erase(Owner::Null());
+  }
+
+  bool isSubsetOf(const PSet &PS) {
+    assert(getState() != Unknown);
+    if (isInvalid())
+      return false;
+
+    return std::includes(PS.p.begin(), PS.p.end(), p.begin(), p.end());
+  }
+
+  std::string str() const {
+    std::stringstream ss;
+    switch (state) {
+    case Unknown:
+      ss << "(unknown)";
+      break;
+    case Invalid:
+      ss << "(invalid)";
+      break;
+    case PossiblyInvalid:
+      ss << "(possibly invalid)";
+      break;
+    case Valid:
+      bool first = true;
+      for (const auto &i : p) {
+        if (!first)
+          ss << ", ";
+        else
+          first = false;
+        ss << i.first.getName();
+        for (size_t j = 0; j < i.second; ++j)
+          ss << "'";
+      }
+      break;
+    }
+    return ss.str();
+  }
+
+  void print(raw_ostream &Out) const { Out << str() << "\n"; }
+
+  /// Merge contents of other pset into this
+  void merge(const PSet &otherPset) {
+    if (state == Unknown || otherPset.state == Unknown) {
+      state = Unknown;
+      return;
+    }
+    if (state == Invalid)
+      return;
+    if (otherPset.state == Invalid) {
+      state = Invalid;
+      assert(otherPset.Reason.hasValue());
+      Reason = otherPset.Reason;
+      return;
+    }
+    if (state == PossiblyInvalid)
+      return;
+    if (otherPset.state == PossiblyInvalid) {
+      state = PossiblyInvalid;
+      assert(otherPset.Reason.hasValue());
+      Reason = otherPset.Reason;
+      return;
+    }
+    assert(state == Valid && otherPset.state == Valid);
+
+    for (const auto &PO : otherPset.p) {
+      auto P = p.find(PO.first);
+      if (P == p.end()) {
+        p.insert(PO);
+      } else {
+        // if p contains obj' and otherPset.p contains obj''
+        // then the union shall be invalidated whenever obj' or obj'' is
+        // invalidated
+        // which is the same as whenever obj'' is invalidated
+        P->second = std::max(P->second, PO.second);
+      }
+    }
+  }
+
+  /// The pointer is dangling
+  static PSet invalid(InvalidationReason Reason) {
+    PSet ret;
+    ret.state = Invalid;
+    ret.Reason = Reason;
+    return ret;
+  }
+
+  /// We don't know the state of the pointer
+  static PSet unknown() {
+    PSet ret;
+    ret.state = Unknown;
+    return ret;
+  }
+
+  /// The pset contains obj, obj' or obj''
+  static PSet valid() {
+    PSet ret;
+    ret.state = Valid;
+    return ret;
+  }
+
+  /// The pset contains obj, obj' or obj''
+  static PSet validOwner(Owner Owner, unsigned order = 0) {
+    PSet ret;
+    ret.state = Valid;
+    ret.p.emplace(Owner, order);
+    return ret;
+  }
+
+  /// The pset contains obj, obj' or obj''
+  static PSet validOwnerOrNull(Owner Owner, unsigned order = 0) {
+    PSet ret = validOwner(Owner, order);
+    ret.p.emplace(Owner::Null(), 0);
+    return ret;
+  }
+
+  std::map<Owner, unsigned>::const_iterator begin() const { return p.begin(); }
+
+  std::map<Owner, unsigned>::const_iterator end() const { return p.end(); }
+
+  void insert(Owner Owner, unsigned order = 0) {
+    p.insert(std::make_pair(Owner, order));
+  }
+
+private:
+  State state = Unknown;
+  /// Maps owner obj to order.
+  /// (obj,0) == obj: points to obj
+  /// (obj,1) == obj': points to object owned directly by obj
+  /// (obj,2) == obj'': points an object kept alive indirectly (transitively)
+  /// via owner obj
+  std::map<Owner, unsigned> p;
+
+  Optional<InvalidationReason> Reason;
+};
+
+using PSetsMap = std::unordered_map<Pointer, PSet>;
+
+void dump(const PSetsMap &PSets) {
+  for (auto &i : PSets)
+    llvm::errs() << "pset(" << i.first.getName() << ") = " << i.second.str()
+                 << "\n";
+}
+
+class LifetimeReporter {
+  bool Debug; // TODO: remove me?
+  ClangTidyContext *CTContext;
+
+public:
+  LifetimeReporter(bool Debug, ClangTidyContext *CTContext)
+      : Debug(Debug), CTContext(CTContext) {}
+
+  /// This may either forward to a contained DiagnosticBuilder or no-op
+  class CondDiagnosticBuilder {
+    Optional<DiagnosticBuilder> DB;
+
+  public:
+    CondDiagnosticBuilder() = default;
+    CondDiagnosticBuilder(DiagnosticBuilder DB) : DB(std::move(DB)) {}
+    template <typename T>
+    const CondDiagnosticBuilder &operator<<(const T &v) const {
+      if (DB.hasValue())
+        DB.getValue() << v;
+      return *this;
+    }
+  };
+
+  CondDiagnosticBuilder DebugMsg(SourceLocation Loc, StringRef Message) const {
+    if (Debug)
+      return reportBug(Loc, Message);
+    return {};
+  }
+
+  void PsetDebug(const PSet &PS, SourceLocation Loc,
+                 const Pointer &Pointer) const {
+    DebugMsg(Loc, "pset(%0) = {%1}") << Pointer.getName() << PS.str();
+  }
+
+  DiagnosticBuilder reportBug(SourceLocation Loc, StringRef Message) const {
+    return CTContext->diag("cppcoreguidelines-pro-lifetime", Loc, Message,
+                           DiagnosticIDs::Warning);
+  }
+
+  DiagnosticBuilder reportNote(SourceLocation Loc, StringRef Message) const {
+    return CTContext->diag("cppcoreguidelines-pro-lifetime", Loc, Message,
+                           DiagnosticIDs::Note);
+  }
+};
+
+// Collection of methods to update/check PSets from statements/expressions
+class PSetsBuilder {
+
+  const LifetimeReporter *Reporter;
+  ASTContext *ASTCtxt;
+  PSetsMap &PSets;
+
+  /// IgnoreParenImpCasts - Ignore parentheses and implicit casts.  Strip off
+  /// any ParenExpr
+  /// or ImplicitCastExprs, returning their operand.
+  /// Does not ignore MaterializeTemporaryExpr as Expr::IgnoreParenImpCasts
+  /// would.
+  const Expr *IgnoreParenImpCasts(const Expr *E) {
+    while (true) {
+      E = E->IgnoreParens();
+      if (const auto *P = dyn_cast<ImplicitCastExpr>(E)) {
+        E = P->getSubExpr();
+        continue;
+      }
+      return E;
+    }
+  }
+
+  void EvalExpr(const Expr *E) {
+    E = E->IgnoreParenCasts();
+
+    switch (E->getStmtClass()) {
+    case Expr::BinaryOperatorClass: {
+      const auto *BinOp = cast<BinaryOperator>(E);
+      Optional<Pointer> P = PointerFromExpr(BinOp->getLHS());
+      if (P.hasValue() && P->isRealPointer()) {
+        switch (BinOp->getOpcode()) {
+        case BO_Assign: {
+          // This assignment updates a Pointer
+          EvalExpr(BinOp->getLHS()); // Eval for side-effects
+          PSet PS = EvalExprForPSet(BinOp->getRHS(), false);
+          SetPSet(P.getValue(), PS, BinOp->getExprLoc());
+          return;
+        }
+        case BO_AddAssign:
+        case BO_SubAssign:
+          // Affects pset; forbidden by the bounds profile.
+          SetPSet(P.getValue(), PSet::unknown(), BinOp->getExprLoc());
+        default:
+          break; // Traversing is done below
+        }
+      }
+      break;
+    }
+    case Expr::UnaryOperatorClass: {
+      const auto *UnOp = cast<UnaryOperator>(E);
+      Optional<Pointer> P = PointerFromExpr(UnOp->getSubExpr());
+      if (P.hasValue() && P->isRealPointer()) {
+        switch (UnOp->getOpcode()) {
+        case UO_Deref: {
+          // Check if dereferencing this pointer is valid
+          PSet PS = EvalExprForPSet(UnOp->getSubExpr(), false);
+          CheckPSetValidity(PS, UnOp->getExprLoc());
+          return;
+        }
+        case UO_PostInc:
+        case UO_PostDec:
+        case UO_PreInc:
+        case UO_PreDec:
+          // Affects pset; forbidden by the bounds profile.
+          SetPSet(P.getValue(), PSet::unknown(), UnOp->getExprLoc());
+        default:
+          break; // Traversing is done below
+        }
+      }
+      break;
+    }
+    case Expr::MemberExprClass: {
+      const auto *MemberE = cast<MemberExpr>(E);
+      const Expr *Base = MemberE->getBase();
+      // 'this' can never dangle
+      // TODO: check pset for !isArrow if Base is a reference
+      if (!isa<CXXThisExpr>(Base) && MemberE->isArrow()) {
+        PSet PS = EvalExprForPSet(Base, false);
+        CheckPSetValidity(PS, MemberE->getExprLoc());
+        return;
+      }
+      break;
+    }
+    case Expr::CallExprClass: {
+      if (EvalCallExpr(cast<CallExpr>(E)))
+        return;
+      break;
+    }
+    default:;
+    }
+    // Other Expr, just recurse
+    for (const Stmt *SubStmt : E->children())
+      EvalStmt(SubStmt);
+  }
+
+  /// Evaluates the CallExpr for effects on psets
+  /// When a non-const pointer to pointer or reference to pointer is passed
+  /// into
+  /// a function,
+  /// it's pointee's are invalidated.
+  /// Returns true if CallExpr was handeld
+  bool EvalCallExpr(const CallExpr *CallE) {
+    const auto *D = dyn_cast_or_null<FunctionDecl>(CallE->getCalleeDecl());
+    if (!D)
+      return false; // happens for CXXPseudoDestructorExpr
+
+    if (D->isVariadic())
+      return false; // Forbidden by type profile
+
+    if (D->getBuiltinID())
+      return false;
+
+    EvalExpr(CallE->getCallee());
+    const auto *CXXD = dyn_cast<CXXMethodDecl>(D);
+
+    if (const auto *MemberCallE = dyn_cast<CXXMemberCallExpr>(CallE)) {
+      const auto *ThisE = MemberCallE->getImplicitObjectArgument();
+      EvalExpr(ThisE);
+      // TODO: something like
+      // if(!MemberCallE->getMethodDecl()->isConst())
+      //   invalidateOwner(ThisE, 1, E->getExprLoc());
+    }
+
+    for (unsigned i = 0; i < CallE->getNumArgs(); ++i) {
+      const Expr *Arg = CallE->getArg(i);
+
+      QualType ParamType;
+      if (isa<CXXOperatorCallExpr>(CallE) && CXXD) {
+        // For CXXOperatorCallExpr, getArg(0) is the 'this' pointer
+        if (i == 0)
+          ParamType = CXXD->getThisType(*ASTCtxt).getCanonicalType();
+        else
+          ParamType = D->getParamDecl(i - 1)->getType().getCanonicalType();
+        //} else if (CXXD && !CXXD->isStatic()) {
+      } else
+        ParamType = D->getParamDecl(i)->getType().getCanonicalType();
+
+      QualType ArgType = Arg->getType().getCanonicalType();
+      // Check if the function can affect other psets through this argument
+      // (i.e. pointer to pointer or reference to pointer)
+      bool hasPSet = Pointer::is(ArgType);
+      bool canNotModifyPSet =
+          (ParamType->isPointerType() || ParamType->isReferenceType()) &&
+          ParamType->getPointeeType().isConstQualified();
+      if (!hasPSet || canNotModifyPSet) {
+        // Is not a Pointer, or its Pointee's are const and thus cannot be
+        // invalidated
+        EvalExpr(Arg);
+        continue;
+      }
+
+      PSet PS = EvalExprForPSet(Arg, !ParamType->isPointerType());
+      if (PS.isUnknown() || PS.isInvalid())
+        continue;
+
+      // Everything in this pset may be invalidated
+      for (auto &Entry : PS) {
+        if (Entry.first == Owner::Null() || Entry.first == Owner::Static())
+          continue;
+
+        // Check if this Owner is also a Pointer
+        Optional<Pointer> IndirectP = Entry.first.getPointer();
+        if (IndirectP.hasValue())
+          // TODO: add possible values; for now just stop tracking
+          SetPSet(IndirectP.getValue(), PSet::unknown(), CallE->getExprLoc());
+      }
+    }
+    return true;
+  }
+  /// Evaluates E for effects that change psets.
+  /// If ExprPset is not null and
+  /// 1) referenceCtx is true, set ExprPset to the pset of 'p' in 'auto &p =
+  /// E';
+  /// 2) referenceCtx is false, set ExprPset to the pset of 'p' in 'auto *p =
+  /// E';
+  ///
+  /// We use pset_ptr(E) to denote ExprPset when referenceCtx is true
+  /// and pset_ref(E) to denote ExprPset when referenceTxt is false.
+  /// We use pset(v) when v is a VarDecl to refer to the entry of v in the
+  /// PSets
+  /// map.
+  PSet EvalExprForPSet(const Expr *E, bool referenceCtx) {
+    E = IgnoreParenImpCasts(E);
+
+    switch (E->getStmtClass()) {
+    case Expr::MaterializeTemporaryExprClass: {
+      const auto *MaterializeTemporaryE = cast<MaterializeTemporaryExpr>(E);
+      assert(referenceCtx);
+      EvalExpr(MaterializeTemporaryE->GetTemporaryExpr());
+
+      if (MaterializeTemporaryE->getExtendingDecl())
+        return PSet::validOwner(MaterializeTemporaryE->getExtendingDecl(), 1);
+      else
+        return PSet::validOwner(Owner::Temporary(), 0);
+      break;
+    }
+    case Expr::DeclRefExprClass: {
+      const auto *DeclRef = cast<DeclRefExpr>(E);
+      const auto *VD = dyn_cast<VarDecl>(DeclRef->getDecl());
+      if (VD) {
+        if (referenceCtx) {
+          // T i; T &j = i; auto &p = j; -> pset_ref(p) = {i}
+          if (VD->getType()->isReferenceType())
+            return GetPSet(VD);
+          else
+            // T i; auto &p = i; -> pset_ref(p) = {i}
+            return PSet::validOwner(VD, 0);
+        } else {
+          if (VD->getType()->isArrayType())
+            // Forbidden by bounds profile
+            // Alternative would be: T a[]; auto *p = a; -> pset_ptr(p) = {a}
+            return PSet::unknown();
+          else
+            // T i; auto *p = i; -> pset_ptr(p) = pset(i)
+            return GetPSet(VD);
+        }
+      }
+      break;
+    }
+    case Expr::ArraySubscriptExprClass: {
+      const auto *ArraySubscriptE = cast<ArraySubscriptExpr>(E);
+      EvalExpr(ArraySubscriptE->getBase());
+      EvalExpr(ArraySubscriptE->getIdx());
+
+      // By the bounds profile, ArraySubscriptExpr is only allowed on arrays
+      // (not on pointers),
+      // thus the base needs to be a DeclRefExpr.
+      const auto *DeclRef = dyn_cast<DeclRefExpr>(
+          ArraySubscriptE->getBase()->IgnoreParenImpCasts());
+      if (DeclRef) {
+        const VarDecl *VD = dyn_cast<VarDecl>(DeclRef->getDecl());
+        if (VD && VD->getType().getCanonicalType()->isArrayType() &&
+            referenceCtx)
+          // T a[3]; -> pset_ref(a[i]) = {a}
+          return PSet::validOwner(VD, 0);
+      }
+      break;
+    }
+    case Expr::ConditionalOperatorClass: {
+      const auto *CO = cast<ConditionalOperator>(E);
+      // pset_ref(b ? a : b) = pset_ref(a) union pset_ref(b)
+      // pset_ptr(b ? a : b) = pset_ptr(a) union pset_ptr(b)
+      EvalExpr(CO->getCond());
+
+      PSet PSLHS = EvalExprForPSet(CO->getLHS(), referenceCtx);
+      PSet PSRHS = EvalExprForPSet(CO->getRHS(), referenceCtx);
+      PSRHS.merge(PSLHS);
+      return PSRHS;
+    }
+    case Expr::MemberExprClass: {
+      const auto *MemberE = cast<MemberExpr>(E);
+      const Expr *Base = MemberE->getBase();
+      if (isa<CXXThisExpr>(Base)) {
+        // We are inside the class, so track the members separately
+        const auto *FD = dyn_cast<FieldDecl>(MemberE->getMemberDecl());
+        if (FD) {
+          return PSet::validOwner(FD, 0);
+        }
+      } else {
+        return EvalExprForPSet(
+            Base, !Base->getType().getCanonicalType()->isPointerType());
+      }
+      break;
+    }
+    case Expr::BinaryOperatorClass: {
+      const auto *BinOp = cast<BinaryOperator>(E);
+      if (BinOp->getOpcode() == BO_Assign) {
+        EvalExpr(BinOp);
+        return EvalExprForPSet(BinOp->getLHS(), referenceCtx);
+      }
+      break;
+    }
+    case Expr::UnaryOperatorClass: {
+      const auto *UnOp = cast<UnaryOperator>(E);
+      if (UnOp->getOpcode() == UO_Deref) {
+        PSet PS = EvalExprForPSet(UnOp->getSubExpr(), false);
+        CheckPSetValidity(PS, UnOp->getOperatorLoc());
+        if (referenceCtx) {
+          // pset_ref(*p) = pset_ptr(p)
+          return PS;
+        } else {
+          if (PS.isInvalid() || PS.isUnknown())
+            return PS;
+
+          assert(PS.isValid());
+          // pset_ptr(*p) = replace each pset entry of pset_ptr(p) by its own
+          // pset
+          PSet RetPS = PSet::valid();
+          for (auto &Entry : PS) {
+            if (Entry.first == Owner::Null())
+              continue; // will be flagged by checkPSetValidity above
+            if (Entry.first == Owner::Static())
+              RetPS.merge(PSet::validOwner(Owner::Static()));
+            else {
+              Optional<Pointer> P = Entry.first.getPointer();
+              if (!P.hasValue())
+                // This can happen if P has array type; dereferencing an array
+                // is forbidden by the bounds profile
+                return PSet::unknown();
+              RetPS.merge(GetPSet(P.getValue()));
+            }
+          }
+          return RetPS;
+        }
+      } else if (UnOp->getOpcode() == UO_AddrOf) {
+        assert(!referenceCtx);
+        return EvalExprForPSet(UnOp->getSubExpr(), true);
+      }
+      break;
+    }
+    case Expr::CXXReinterpretCastExprClass:
+    case Expr::CStyleCastExprClass: {
+      const auto *CastE = cast<CastExpr>(E);
+      switch (CastE->getCastKind()) {
+      case CK_BitCast:
+      case CK_LValueBitCast:
+      case CK_IntegralToPointer:
+        // Those casts are forbidden by the type profile
+        return PSet::unknown();
+      default:
+        return EvalExprForPSet(CastE->getSubExpr(), referenceCtx);
+      }
+    }
+    default:;
+    }
+
+    if (E->isNullPointerConstant(*ASTCtxt, Expr::NPC_ValueDependentIsNotNull)) {
+      if (referenceCtx)
+        // It is illegal to bind a reference to null
+        return PSet::invalid(
+            InvalidationReason::NotInitialized(E->getExprLoc()));
+      else
+        return PSet::validOwner(Owner::Null());
+    }
+
+    // Unhandled case
+    EvalExpr(E);
+    return PSet::unknown();
+  }
+
+  /// Returns a Pointer if E is a DeclRefExpr of a Pointer
+  Optional<Pointer> PointerFromExpr(const Expr *E) {
+    E = E->IgnoreParenCasts();
+    const auto *DeclRef = dyn_cast<DeclRefExpr>(E);
+    if (!DeclRef)
+      return Optional<Pointer>();
+
+    return Pointer::get(DeclRef->getDecl());
+  }
+
+  void CheckPSetValidity(const PSet &PS, SourceLocation Loc);
+
+  // Traverse S in depth-first post-order and evaluate all effects on psets
+  void EvalStmt(const Stmt *S) {
+    if (const auto *DS = dyn_cast<DeclStmt>(S)) {
+      assert(DS->isSingleDecl());
+      const Decl *D = DS->getSingleDecl();
+      if (const auto *VD = dyn_cast<VarDecl>(D))
+        EvalVarDecl(VD);
+    } else if (const auto *E = dyn_cast<Expr>(S))
+      EvalExpr(E);
+  }
+
+  /// Invalidates all psets that point to V or something owned by V
+  void invalidateOwner(Owner O, unsigned order, InvalidationReason Reason) {
+    for (auto &i : PSets) {
+      const auto &Pointer = i.first;
+      PSet &PS = i.second;
+      if (!PS.isValid())
+        continue; // Nothing to invalidate
+
+      if (PS.contains(O, order))
+        SetPSet(Pointer, PSet::invalid(Reason), Reason.getLoc());
+    }
+  }
+  void erasePointer(Pointer P) { PSets.erase(P); }
+  PSet GetPSet(Pointer P);
+  void SetPSet(Pointer P, PSet PS, SourceLocation Loc);
+  void diagPSet(Pointer P, SourceLocation Loc) {
+    auto i = PSets.find(P);
+    if (i != PSets.end())
+      Reporter->PsetDebug(i->second, Loc, P);
+    else
+      Reporter->reportBug(Loc, "variable '%0' has no pset") << P.getName();
+  }
+
+  bool HandleClangAnalyzerPset(const Stmt *S, const LifetimeReporter *Reporter);
+
+public:
+  PSetsBuilder(const LifetimeReporter *Reporter, ASTContext *ASTCtxt,
+               PSetsMap &PSets)
+      : Reporter(Reporter), ASTCtxt(ASTCtxt), PSets(PSets) {}
+
+  void EvalVarDecl(const VarDecl *VD) {
+    const Expr *Initializer = VD->getInit();
+    auto P = Pointer::get(VD);
+
+    if (!P.hasValue()) {
+      // Not a Pointer, but initializer can have side-effects
+      if (Initializer)
+        EvalExpr(Initializer);
+      return;
+    }
+
+    SourceLocation Loc = VD->getLocEnd();
+
+    PSet PS; //== unknown
+
+    if (Initializer)
+      PS = EvalExprForPSet(Initializer, !P->isRealPointer());
+    else if (Loc.isValid())
+      PS = PSet::invalid(InvalidationReason::NotInitialized(Loc));
+
+    // We don't track the PSets of variables with global storage; just make
+    // sure that its pset is always {static} and/or {null}
+    if (P->hasGlobalStorage()) {
+      if (PS.isUnknown()) {
+        // Reporter.PsetDebug(PS, Loc, P.getValue());
+        return;
+      }
+
+      if (!PS.isSubsetOf(PSet::validOwnerOrNull(Owner::Static())) && Reporter)
+        Reporter->reportBug(Loc, "the pset of %0 must be a subset of "
+                                 "{(static), (null)}, but is {%1}")
+            << P->getName() << PS.str();
+      return;
+    }
+
+    SetPSet(VD, PS, Loc);
+    return;
+  }
+
+  void VisitBlock(const CFGBlock &B, const LifetimeReporter *Reporter);
+
+  void UpdatePSetsFromCondition(const Expr *E, bool positive,
+                                SourceLocation Loc);
+};
+
+// Manages lifetime information for the CFG of a FunctionDecl
+
+PSet PSetsBuilder::GetPSet(Pointer P) {
+  auto i = PSets.find(P);
+  if (i != PSets.end())
+    return i->second;
+
+  // Assumption: global Pointers have a pset of {static, null}
+  if (P.hasGlobalStorage() || P.isMemberVariable()) {
+    if (P.mayBeNull())
+      return PSet::validOwnerOrNull(Owner::Static());
+    return PSet::validOwner(Owner::Static());
+  }
+
+  llvm_unreachable("Missing pset for Pointer");
+}
+
+void PSetsBuilder::SetPSet(Pointer P, PSet PS, SourceLocation Loc) {
+  assert(P.getName() != "");
+
+  // Assumption: global Pointers have a pset that is a subset of {static,
+  // null}
+  if (P.hasGlobalStorage() && !PS.isUnknown() &&
+      !PS.isSubsetOf(PSet::validOwnerOrNull(Owner::Static())) && Reporter)
+    Reporter->reportBug(Loc, "the pset of %0 must be a subset of "
+                             "{(static), (null)}, but is {%1}")
+        << P.getName() << PS.str();
+
+  auto i = PSets.find(P);
+  if (i != PSets.end())
+    i->second = std::move(PS);
+  else
+    PSets.emplace(P, PS);
+}
+
+void PSetsBuilder::CheckPSetValidity(const PSet &PS, SourceLocation Loc) {
+  if (!Reporter)
+    return;
+
+  if (PS.getState() == PSet::Unknown) {
+    Reporter->DebugMsg(Loc, "dereferencing a unknown pointer");
+    return;
+  }
+
+  if (PS.getState() == PSet::Invalid) {
+    Reporter->reportBug(Loc, "dereferencing a dangling pointer");
+    Reporter->reportNote(PS.getReason().getLoc(),
+                         "it became invalid because %0 here")
+        << PS.getReason().str();
+    return;
+  }
+
+  if (PS.getState() == PSet::PossiblyInvalid) {
+    Reporter->reportBug(Loc, "dereferencing a possibly dangling pointer");
+    Reporter->reportNote(PS.getReason().getLoc(),
+                         "it became possibly invalid because %0 here")
+        << PS.getReason().str();
+    return;
+  }
+
+  if (PS.isValid() && PS.containsNull()) {
+    if (PS.isSingular())
+      Reporter->reportBug(Loc, "dereferencing a null pointer");
+    else
+      Reporter->reportBug(Loc, "dereferencing a (possible) null pointer");
+    return;
+  }
+}
+
+/// Updates psets to remove 'null' when entering conditional statements. If
+/// 'positive' is
+/// false,
+/// handles expression as-if it was negated.
+/// Examples:
+///   int* p = f();
+/// if(p)
+///  ... // pset of p does not contain 'null'
+/// else
+///  ... // pset of p still contains 'null'
+/// if(!p)
+///  ... // pset of p still contains 'null'
+/// else
+///  ... // pset of p does not contain 'null'
+/// TODO: Add condition like 'p == nullptr', 'p != nullptr', '!(p ==
+/// nullptr)',
+/// etc
+void PSetsBuilder::UpdatePSetsFromCondition(const Expr *E, bool positive,
+                                            SourceLocation Loc) {
+  E = E->IgnoreParenImpCasts();
+
+  if (positive) {
+    if (auto *BO = dyn_cast<BinaryOperator>(E)) {
+      if (BO->getOpcode() != BO_LAnd)
+        return;
+      UpdatePSetsFromCondition(BO->getLHS(), true, Loc);
+      UpdatePSetsFromCondition(BO->getRHS(), true, Loc);
+      return;
+    }
+
+    if (auto *DeclRef = dyn_cast<DeclRefExpr>(E)) {
+      Optional<Pointer> P = Pointer::get(DeclRef->getDecl());
+      if (!P.hasValue())
+        return;
+      auto PS = GetPSet(P.getValue());
+      if (!PS.isValid())
+        return;
+      if (PS.containsNull()) {
+        PS.removeNull();
+        SetPSet(P.getValue(), PS, Loc);
+      }
+    }
+  } else {
+    if (auto *BO = dyn_cast<BinaryOperator>(E)) {
+      if (BO->getOpcode() != BO_LOr)
+        return;
+      UpdatePSetsFromCondition(BO->getLHS(), false, Loc);
+      UpdatePSetsFromCondition(BO->getRHS(), false, Loc);
+      return;
+    }
+
+    if (auto *UO = dyn_cast<UnaryOperator>(E)) {
+      if (UO->getOpcode() != UO_LNot)
+        return;
+      UpdatePSetsFromCondition(UO->getSubExpr(), true, Loc);
+    }
+  }
+}
+
+/// Checks if the statement S is a call to clang_analyzer_pset and, if yes,
+/// diags the pset of its argument
+bool PSetsBuilder::HandleClangAnalyzerPset(const Stmt *S,
+                                           const LifetimeReporter *Reporter) {
+  assert(Reporter);
+  const auto *CallE = dyn_cast<CallExpr>(S);
+  if (!CallE)
+    return false;
+
+  const FunctionDecl *Callee = CallE->getDirectCallee();
+  if (!Callee)
+    return false;
+
+  const auto *I = Callee->getIdentifier();
+  if (!I)
+    return false;
+
+  if (I->getName() != "clang_analyzer_pset")
+    return false;
+
+  auto Loc = CallE->getLocStart();
+
+  if (CallE->getNumArgs() != 1) {
+    Reporter->reportBug(Loc, "clang_analyzer_pset takes one argument");
+    return true;
+  }
+
+  const auto *DeclRef =
+      dyn_cast<DeclRefExpr>(CallE->getArg(0)->IgnoreImpCasts());
+  if (!DeclRef) {
+    Reporter->reportBug(
+        Loc, "Argument to clang_analyzer_pset must be a DeclRefExpr");
+    return true;
+  }
+
+  const auto *VD = dyn_cast<VarDecl>(DeclRef->getDecl());
+  if (!VD) {
+    Reporter->reportBug(Loc,
+                        "Argument to clang_analyzer_pset must be a VarDecl");
+    return true;
+  }
+
+  diagPSet(VD, Loc);
+  return true;
+}
+
+// Update PSets in Builder through all CFGElements of this block
+void PSetsBuilder::VisitBlock(const CFGBlock &B,
+                              const LifetimeReporter *Reporter) {
+  for (auto i = B.begin(); i != B.end(); ++i) {
+    const CFGElement &E = *i;
+    switch (E.getKind()) {
+    case CFGElement::Statement: {
+      const Stmt *S = E.castAs<CFGStmt>().getStmt();
+
+      // Handle call to clang_analyzer_pset, which will print the pset of its
+      // argument
+      if (Reporter && HandleClangAnalyzerPset(S, Reporter))
+        break;
+
+      EvalStmt(S);
+
+      // Kill all temporaries that vanish at the end of the full expression
+      invalidateOwner(Owner::Temporary(), 0,
+                      InvalidationReason::TemporaryLeftScope(S->getLocEnd()));
+      break;
+    }
+    case CFGElement::AutomaticObjLeavesScope: {
+      auto Leaver = E.castAs<CFGAutomaticObjLeavesScope>();
+
+      // Stop tracking Pointers that leave scope
+      erasePointer(Leaver.getVarDecl());
+
+      // Invalidate all pointers that track leaving Owners
+      invalidateOwner(
+          Leaver.getVarDecl(), 0,
+          InvalidationReason::PointeeLeftScope(
+              Leaver.getTriggerStmt()->getLocEnd(), Leaver.getVarDecl()));
+      break;
+    }
+    case CFGElement::NewAllocator:
+    case CFGElement::AutomaticObjectDtor:
+    case CFGElement::DeleteDtor:
+    case CFGElement::BaseDtor:
+    case CFGElement::MemberDtor:
+    case CFGElement::TemporaryDtor:
+    case CFGElement::Initializer:
+      break;
+    }
+  }
+}
+
+class LifetimeContext {
+  /// Each CFGBlock has one (lazily allocated) BlockContext in the
+  /// BlockContextMap
+  struct BlockContext {
+    bool visited = false;
+    /// Merged PSets of all predecessors of this CFGBlock
+    PSetsMap EntryPSets;
+    /// Computed PSets after updating EntryPSets through all CFGElements of
+    /// this block
+    PSetsMap ExitPSets;
+  };
+
+  ASTContext *ASTCtxt;
+  LangOptions LangOptions;
+  SourceManager *SourceMgr;
+  CFG *ControlFlowGraph;
+  const FunctionDecl *FuncDecl;
+  std::vector<BlockContext> BlockContexts;
+  AnalysisDeclContextManager AnalysisDCMgr;
+  AnalysisDeclContext AC;
+  LifetimeReporter Reporter;
+
+  bool computeEntryPSets(const clang::CFGBlock &B, PSetsMap &EntryPSets);
+
+  BlockContext &getBlockContext(const CFGBlock *B) {
+    return BlockContexts[B->getBlockID()];
+  }
+
+  void dumpBlock(const CFGBlock &B) const {
+    auto Loc = getStartLocOfBlock(B);
+    llvm::errs() << "Block at " << SourceMgr->getBufferName(Loc) << ":"
+                 << SourceMgr->getSpellingLineNumber(Loc) << "\n";
+    B.dump(ControlFlowGraph, LangOptions, true);
+  }
+
+  void dumpCFG() const { ControlFlowGraph->dump(LangOptions, true); }
+
+  PSetsBuilder createPSetsBuilder(PSetsMap &PSets,
+                                  const LifetimeReporter *Reporter = nullptr) {
+    return PSetsBuilder(Reporter, ASTCtxt, PSets);
+  }
+
+  /// Approximate the SourceLocation of a Block for attaching pset debug
+  /// diagnostics
+  SourceLocation getStartLocOfBlock(const CFGBlock &B) const {
+    if (&B == &ControlFlowGraph->getEntry())
+      return FuncDecl->getLocStart();
+
+    if (&B == &ControlFlowGraph->getExit())
+      return FuncDecl->getLocEnd();
+
+    for (const CFGElement &E : B) {
+      switch (E.getKind()) {
+      case CFGElement::Statement:
+        return E.castAs<CFGStmt>().getStmt()->getLocStart();
+      case CFGElement::AutomaticObjLeavesScope:
+        return E.castAs<CFGAutomaticObjLeavesScope>()
+            .getTriggerStmt()
+            ->getLocEnd();
+      default:;
+      }
+    }
+    if (B.succ_empty())
+      return SourceLocation();
+    // for(auto i = B.succ_begin(); i != B.succ_end(); ++i)
+    //{
+    // TODO: this may lead to infinite recursion
+    return getStartLocOfBlock(**B.succ_begin());
+    //}
+    llvm_unreachable("Could not determine start loc of CFGBlock");
+  }
+
+public:
+  LifetimeContext(ASTContext *ASTCtxt, bool Debug, ClangTidyContext *CTContext,
+                  SourceManager *SourceMgr, const FunctionDecl *FuncDecl)
+      : ASTCtxt(ASTCtxt), LangOptions(CTContext->getLangOpts()),
+        SourceMgr(SourceMgr), FuncDecl(FuncDecl), AC(&AnalysisDCMgr, FuncDecl),
+        Reporter(Debug, CTContext) {
+    AC.getCFGBuildOptions().PruneTriviallyFalseEdges = true;
+    AC.getCFGBuildOptions().AddInitializers = true;
+    AC.getCFGBuildOptions().AddAutomaticObjLeavesScope = true;
+    AC.getCFGBuildOptions().AddStaticInitBranches = true;
+    AC.getCFGBuildOptions().AddCXXNewAllocator = true;
+    ControlFlowGraph = AC.getCFG();
+    BlockContexts.resize(ControlFlowGraph->getNumBlockIDs());
+  }
+
+  void TraverseBlocks();
+};
+
+/// Computes entry psets of this block by merging exit psets
+/// of all reachable predecessors.
+/// Returns true if this block is reachable, i.e. one of it predecessors has
+/// been visited.
+bool LifetimeContext::computeEntryPSets(const clang::CFGBlock &B,
+                                        PSetsMap &EntryPSets) {
+  // If no predecessors have been visited by now, this block is not
+  // reachable
+  bool isReachable = false;
+  for (auto i = B.pred_begin(); i != B.pred_end(); ++i) {
+    CFGBlock *PredBlock = i->getReachableBlock();
+    if (!PredBlock)
+      continue;
+
+    auto &PredBC = getBlockContext(PredBlock);
+    if (!PredBC.visited)
+      continue; // Skip this back edge.
+
+    isReachable = true;
+    auto PredPSets = PredBC.ExitPSets;
+    // If this block is only reachable from an IfStmt, modify pset according
+    // to condition.
+    if (auto TermStmt = PredBlock->getTerminator().getStmt()) {
+      // first successor is the then-branch, second sucessor is the
+      // else-branch.
+      bool thenBranch = (PredBlock->succ_begin()->getReachableBlock() == &B);
+      // TODO: also use for, do-while and while conditions
+      if (auto If = dyn_cast<IfStmt>(TermStmt)) {
+        assert(PredBlock->succ_size() == 2);
+        auto Builder = createPSetsBuilder(PredPSets);
+        Builder.UpdatePSetsFromCondition(If->getCond(), thenBranch,
+                                         If->getCond()->getLocStart());
+      } else if (const auto *CO = dyn_cast<ConditionalOperator>(TermStmt)) {
+        auto Builder = createPSetsBuilder(PredPSets);
+        Builder.UpdatePSetsFromCondition(CO->getCond(), thenBranch,
+                                         CO->getCond()->getLocStart());
+      }
+    }
+    if (EntryPSets.empty())
+      EntryPSets = PredPSets;
+    else {
+      // Merge PSets with pred's PSets; TODO: make this efficient
+      for (auto &i : EntryPSets) {
+        auto &Pointer = i.first;
+        auto &PS = i.second;
+        auto j = PredPSets.find(Pointer);
+        if (j == PredPSets.end()) {
+          // The only reason that predecessors have PSets for different
+          // variables is that some of them lazily added global variables
+          // or member variables.
+          // If a global pointer is not mentioned, its pset is implicitly
+          // {(null), (static)}
+
+          // OR there was a goto that stayed in the same scope but skipped
+          // back over the initialization of this Pointer.
+          // Then we don't care, because the variable will not be referenced in the C++
+          // code before it is declared.
+
+          PS = Pointer.mayBeNull() ? PSet::validOwnerOrNull(Owner::Static())
+                                   : PSet::validOwner(Owner::Static());
+          continue;
+        }
+        if (PS == j->second)
+          continue;
+
+        PS.merge(j->second);
+      }
+    }
+  }
+  return isReachable;
+}
+
+/// Traverse all blocks of the CFG.
+/// The traversal is repeated until the psets come to a steady state.
+void LifetimeContext::TraverseBlocks() {
+  const PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
+
+  bool updated;
+  do {
+    updated = false;
+    for (const auto *B : *SortedGraph) {
+      auto &BC = getBlockContext(B);
+
+      // The entry block introduces the function parameters into the psets
+      if (B == &ControlFlowGraph->getEntry()) {
+        if (BC.visited)
+          continue;
+
+        // ExitPSets are the function parameters.
+        for (const ParmVarDecl *PVD : FuncDecl->params()) {
+          auto P = Pointer::get(PVD);
+          if (!P.hasValue())
+            continue; // not a Pointer
+          // Parameters cannot be invalid (checked at call site).
+          auto PS = P->mayBeNull() ? PSet::validOwnerOrNull(PVD, 1)
+                                   : PSet::validOwner(PVD, 1);
+          // Reporter.PsetDebug(PS, PVD->getLocEnd(), P.getValue());
+          // PVD->dump();
+          BC.ExitPSets.emplace(P.getValue(), std::move(PS));
+        }
+        BC.visited = true;
+        continue;
+      }
+
+      if (B == &ControlFlowGraph->getExit())
+        continue;
+
+      // compute entry psets of this block by merging exit psets
+      // of all reachable predecessors.
+      PSetsMap EntryPSets;
+      bool isReachable = computeEntryPSets(*B, EntryPSets);
+      if (!isReachable)
+        continue;
+
+      if (BC.visited && EntryPSets == BC.EntryPSets) {
+        // Has been computed at least once and nothing changed; no need to
+        // recompute.
+        continue;
+      }
+
+      BC.EntryPSets = EntryPSets;
+      BC.ExitPSets = BC.EntryPSets;
+      auto Builder = createPSetsBuilder(BC.ExitPSets);
+      Builder.VisitBlock(*B, nullptr);
+      BC.visited = true;
+      updated = true;
+    }
+  } while (updated);
+
+  // Once more to emit diagnostics with final psets
+  for (const auto *B : *SortedGraph) {
+    auto &BC = getBlockContext(B);
+    if (!BC.visited)
+      continue;
+
+    BC.ExitPSets = BC.EntryPSets;
+    auto Builder = createPSetsBuilder(BC.ExitPSets, &Reporter);
+    Builder.VisitBlock(*B, &Reporter);
+  }
+}
+
+} // end unnamed namespace
+
+/// Check that the function adheres to the lifetime profile
+void VisitFunction(const FunctionDecl *Func, ASTContext *ASTCtxt,
+                   SourceManager *SourceMgr, bool Debug,
+                   ClangTidyContext *CTContext) {
+  if (!Func->doesThisDeclarationHaveABody())
+    return;
+
+  if (Func->getLocStart().isInvalid())
+    return;
+
+  if (SourceMgr->isInSystemHeader(Func->getLocStart()))
+    return;
+
+  if (!Func->getIdentifier())
+    return; // unnamed function
+
+  // We only check instantiations
+  if (cast<DeclContext>(Func)->isDependentContext())
+    return;
+
+  // llvm::errs() << "=== Entering " << Func->getName() << "\n";
+  // llvm::errs() << "at " << SourceMgr->getBufferName(Func->getLocStart()) <<
+  // ":" << SourceMgr->getSpellingLineNumber(Func->getLocStart()) << "\n";
+
+  LifetimeContext LC(ASTCtxt, Debug, CTContext, SourceMgr, Func);
+  LC.TraverseBlocks();
+}
+
+/// Check that each global variable is initialized to a pset of {static} and/or
+/// {null}
+void VisitGlobalVar(const VarDecl *VD, ASTContext *ASTCtxt,
+                    SourceManager *SourceMgr, bool Debug,
+                    ClangTidyContext *CTContext) {
+
+  auto P = Pointer::get(VD);
+  if (!P.hasValue())
+    return;
+
+  LifetimeReporter Reporter(Debug, CTContext);
+  PSetsMap PSets; // remove me
+  PSetsBuilder Builder(&Reporter, ASTCtxt, PSets);
+  Builder.EvalVarDecl(VD);
+}
+
+} // end namespace tidy
+} // end namespace clang

docs/clang-tidy/checks/cppcoreguidelines-pro-lifetime.rst

+cppcoreguidelines-pro-lifetime
+==============================
+
+This checker implements the lifetime rules presented in the paper
+by Herb Sutter and Neil MacIntosh paper [1].
+Basically, for each pointer we track to which owner it directly or
+transitivly points to. If the owner are invalidated, all their pointers
+will become invalid, too.
+This should eliminate all possibilites for dangling pointers or null pointer
+dereferences.
+
+[1] https://github.com/isocpp/CppCoreGuidelines/blob/master/docs/Lifetimes%20I%20and%20II%20-%20v0.9.1.pdf

docs/clang-tidy/checks/list.rst

 List of clang-tidy Checks
 =========================
 
 .. toctree::
    cert-setlongjmp
    cert-thrown-exception-type
    cert-variadic-function-def
    cppcoreguidelines-pro-bounds-array-to-pointer-decay
    cppcoreguidelines-pro-bounds-pointer-arithmetic
+   cppcoreguidelines-pro-lifetime
    cppcoreguidelines-pro-type-const-cast
    cppcoreguidelines-pro-type-cstyle-cast
    cppcoreguidelines-pro-type-reinterpret-cast
    cppcoreguidelines-pro-type-static-cast-downcast
    cppcoreguidelines-pro-type-union-access
    cppcoreguidelines-pro-type-vararg
    google-build-explicit-make-pair
    google-build-namespaces

test/clang-tidy/cppcoreguidelines-pro-lifetime-psets.cpp

+// RUN: %check_clang_tidy %s cppcoreguidelines-pro-lifetime %t -- -config="{CheckOptions: [{key: cppcoreguidelines-pro-lifetime.Debug, value: 1}]}" -- -std=c++11
+
+// TODO:
+// lifetime annotations
+// lambda
+// function calls
+
+template<typename T>
+void clang_analyzer_pset(const T&);
+
+int rand();
+
+struct S {
+  ~S();
+  int m;
+  void f() {
+    int* p = &m; // pset becomes m, not *this
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {m}
+  }
+};
+
+struct D : public S {
+  ~D();
+};
+
+void pointer_exprs() {
+  int *p;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(invalid)} [cppcoreguidelines-pro-lifetime]
+  int *q = nullptr;
+  clang_analyzer_pset(q);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(q) = {(null)}
+  int *q2 = 0;
+  clang_analyzer_pset(q2);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(q2) = {(null)}
+  S s;
+  p = &s.m;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {s}
+  int a[2];
+  p = &a[0];
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {a}
+
+  D d;
+  S* ps = &d; // Ignore implicit cast
+  clang_analyzer_pset(ps);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(ps) = {d}
+
+  D* pd = (D*)&s; // Ignore explicit cast
+  clang_analyzer_pset(pd);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(pd) = {s}
+
+  int i;
+  p = q = &i;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i}
+  clang_analyzer_pset(q);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(q) = {i}
+
+  p = rand()%2 ? &i : nullptr;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(null), i}
+}
+
+void ref_exprs() {
+  bool b;
+  int i, j;
+  int& ref1 = i;
+  clang_analyzer_pset(ref1);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(ref1) = {i}
+
+  int *p = &ref1;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i}
+
+  int& ref2 = b ? i : j;
+  clang_analyzer_pset(ref2);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(ref2) = {i, j}
+
+  // Lifetime extension
+  const int& ref3 = 3;
+  clang_analyzer_pset(ref3);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(ref3) = {ref3'}
+
+  // Lifetime extension of pointer; FIXME is that correct?
+  int *const &refp = &i;
+  clang_analyzer_pset(refp);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(refp) = {refp'}
+
+}
+
+void addr_and_dref() {
+  int i;
+  int *p = &i;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i}
+
+  int **p2 = &p;
+  clang_analyzer_pset(p2);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p2) = {p}
+
+  int ***p3 = &p2;
+  clang_analyzer_pset(p3);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p3) = {p2}
+
+  int **d2 = *p3;
+  clang_analyzer_pset(d2);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(d2) = {p}
+
+  int *d1 = **p3;
+  clang_analyzer_pset(d1);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(d1) = {i}
+
+  int **a = &**p3;
+  clang_analyzer_pset(a);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(a) = {p}
+
+  int *b = **&*p3;
+  clang_analyzer_pset(b);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(b) = {i}
+
+  int *c = ***&p3;
+  clang_analyzer_pset(c);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(c) = {i}
+
+}
+
+void forbidden() {
+
+  int i;
+  int *p = &i;
+  p++;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(unknown)}
+
+  p = &i;
+  p--;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(unknown)}
+
+  p = &i;
+  ++p;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(unknown)}
+
+  p = &i;
+  --p;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(unknown)}
+
+  p = &i + 3;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(unknown)}
+
+  int *q = &p[3];
+  clang_analyzer_pset(q);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(q) = {(unknown)}
+}
+
+void ref_leaves_scope() {
+  int *p;
+  {
+    int i = 0;
+    p = &i;
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {i}
+  }
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(invalid)}
+}
+
+void pset_scope_if(bool bb) {
+  int* p;
+  int i, j;
+  if (bb) {
+    p = &i;
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {i}
+  }
+  else
+  {
+    p = &j;
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {j}
+  }
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i, j}
+}
+
+
+void ref_leaves_scope_if(bool bb) {
+  int* p;
+  int j = 0;
+  if (bb) {
+    int i = 0;
+    p = &i;
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {i}
+  }
+  else
+  {
+    p = &j;
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {j}
+  }
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(invalid)}
+}
+
+void ref_to_declarator_leaves_scope_if() {
+  int* p;
+  int j = 0;
+  if (int i = 0) {
+    p = &i;
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {i}
+  }
+  else {
+    p = &j;
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {j}
+  }
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(invalid)}
+}
+
+void ignore_pointer_to_member() {
+  int S::* mp = &S::m; // pointer to member object; has no pset
+  void (S::*mpf)() = &S::f; // pointer to member function; has no pset
+}
+
+void if_stmt(int* p) {
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(null), p'}
+
+  if(p) {
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {p'}
+  } else {
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {(null), p'}
+  }
+
+  if(!p) {
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {(null), p'}
+  } else {
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {p'}
+  }
+
+  char* q;
+  if(p && q) {
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {p'}
+  } else {
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {(null), p'}
+  }
+
+  if(!p || !q) {
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {(null), p'}
+  } else {
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {p'}
+  }
+}
+
+void implicit_else() {
+  int i = 0;
+  int j = 0;
+  int* p = rand()%2 ? &j : nullptr;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(null), j}
+
+  if(!p) {
+    p = &i;
+  }
+
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i, j}
+}
+
+void condition_short_circuit(S *p) {
+  // FIXME: should not warn
+  if(p && p->m)
+  //CHECK-MESSAGES: :[[@LINE-1]]:14: warning: dereferencing a (possible) null pointer [cppcoreguidelines-pro-lifetime]
+    ;
+}
+
+void switch_stmt() {
+  int initial;
+  int* p = &initial;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {initial}
+  int i;
+  int j;
+  switch(i)
+  {
+  case 0:
+    p = &i;
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {i}
+    break;
+  case 1:
+    int k;
+    p = &k;
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {k}
+  case 2:
+    p = &j;
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {j}
+  }
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {initial, i, j}
+}
+
+void for_stmt() {
+  int initial;
+  int* p = &initial;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {initial}
+  int j;
+  // There are different psets on the first and further iterations.
+  for(int i = 0; i < 1024; ++i) {
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {initial, j}
+    p = &j;
+  }
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {initial, j}
+}
+
+void for_stmt_ptr_decl() {
+  int i;
+  for (int *p = &i; ; ) {
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {i}
+  }
+}
+
+void goto_stmt(bool b) {
+  int *p = nullptr;
+  int i;
+l1:
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(null), i}
+  p = &i;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i}
+  if(b)
+    goto l1;
+
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i}
+}
+
+void goto_skipping_decl(bool b) {
+  // When entering function start, there is no p;
+  // when entering from the goto, there was a p
+int i;
+l1:
+  int* p = nullptr;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(null)}
+  if (b)
+    p = &i;
+    goto l1;
+}
+
+int goto_forward_over_decl() {
+  // When jumping over the declaration of p, we will never see that
+  // DeclStmt in the CFG
+  int j;
+  goto e;
+  int *p;
+e:
+  // FIXME: should be pset(p) = {(invalid)}
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: variable 'p' has no pset
+}
+
+
+void for_local_variable() {
+  int i;
+  int* p = &i;
+  while(true) {
+    clang_analyzer_pset(p);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(p) = {(invalid)}
+    int j;
+    p = &j; // p will become invalid on the next iteration, because j leaves scope
+  }
+}
+
+//Simplified from assert.h
+void __assert_fail () __attribute__ ((__noreturn__));
+# define assert(expr)                   \
+  ((expr)                               \
+   ? static_cast<void>(0)               \
+   : __assert_fail ())
+
+void asserting(int *p) {
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(null), p'}
+  assert(p);
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {p'}
+}
+
+int* global_p1 = nullptr;
+int* global_p2 = nullptr;
+int global_i;
+
+void namespace_scoped_vars(int param_i, int* param_p) {
+  clang_analyzer_pset(param_p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(param_p) = {(null), param_p'}
+
+  if(global_p1)
+  {
+    clang_analyzer_pset(global_p1);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: pset(global_p1) = {(static)}
+    *global_p1 = 3;
+  }
+
+  int local_i;
+  global_p1 = &local_i;
+  // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: the pset of global_p1 must be a subset of {(static), (null)}, but is {local_i} [cppcoreguidelines-pro-lifetime]
+  global_p1 = &param_i;
+  // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: the pset of global_p1 must be a subset of {(static), (null)}, but is {param_i} [cppcoreguidelines-pro-lifetime]
+  global_p1 = param_p;
+  // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: the pset of global_p1 must be a subset of {(static), (null)}, but is {(null), param_p'} [cppcoreguidelines-pro-lifetime]
+
+  global_p1 = nullptr; // OK
+  clang_analyzer_pset(global_p1);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(global_p1) = {(null)}
+  global_p1 = &global_i; // OK
+  clang_analyzer_pset(global_p1);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(global_p1) = {(static)}
+  global_p1 = global_p2; // OK
+  clang_analyzer_pset(global_p1);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(global_p1) = {(null), (static)}
+}
+
+void function_call() {
+  void f(int *p);
+
+  int i;
+  int *p = &i;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i}
+  f(p);
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i}
+}
+
+void function_call2() {
+  void f(int **p);
+  void const_f(int *const* p); //cannot change *p
+
+  int i;
+  int *p = &i;
+  int **pp = &p;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i}
+  clang_analyzer_pset(pp);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(pp) = {p}
+
+  const_f(pp);
+  clang_analyzer_pset(pp);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(pp) = {p}
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i}
+
+  // TODO: fix me
+  f(pp);
+  clang_analyzer_pset(pp);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(pp) = {p}
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(unknown)}
+}
+
+void function_call3() {
+  void f(int *&p);
+
+  int i;
+  int *p = &i;
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {i}
+  f(p);
+  // TODO: fix me
+  clang_analyzer_pset(p);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(p) = {(unknown)}
+}
+
+void argument_ref_to_temporary() {
+  //like std::min
+  const int& min(const int& a, const int& b);
+  int x=10, y=2;
+  const int& good = min(x,y); // ok, pset(good) == {x,y}
+  //FIXME: pset should be {x, y}
+  clang_analyzer_pset(good);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(good) = {(unknown)}
+
+  const int& bad = min(x,y+1);
+  //FIXME: pset should be {(invalid)}
+  clang_analyzer_pset(bad);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: pset(bad) = {(unknown)}
+}

test/clang-tidy/cppcoreguidelines-pro-lifetime.cpp

+// RUN: %check_clang_tidy %s cppcoreguidelines-pro-lifetime %t -- -config="{CheckOptions: [{key: cppcoreguidelines-pro-lifetime.Debug, value: 1}]}" -- -std=c++11
+
+struct S {
+  ~S();
+  int m;
+  int f();
+};
+
+void deref_uninitialized() {
+  int *p;
+  *p = 3;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: dereferencing a dangling pointer [cppcoreguidelines-pro-lifetime]
+  // CHECK-MESSAGES: :[[@LINE-3]]:8: note: it became invalid because was never initialized here
+}
+
+void deref_nullptr() {
+  int *q = nullptr;
+  *q = 3;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: dereferencing a null pointer
+}
+
+void ref_leaves_scope() {
+  int *p;
+  {
+    int i = 0;
+    p = &i;
+    *p = 2; // OK
+  }
+  *p = 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: dereferencing a dangling pointer
+  // CHECK-MESSAGES: :[[@LINE-3]]:3: note: it became invalid because the pointee i left the scope here
+}
+
+void ref_to_member_leaves_scope_call() {
+  S *p;
+  {
+    S s;
+    p = &s;
+    p->f(); // OK
+  }
+  p->f();
+  // CHECK-MESSAGES: :[[@LINE-1]]:6: warning: dereferencing a dangling pointer
+  // CHECK-MESSAGES: :[[@LINE-3]]:3: note: it became invalid because the pointee s left the scope here
+  int i = p->m;
+  // CHECK-MESSAGES: :[[@LINE-1]]:14: warning: dereferencing a dangling pointer
+  // CHECK-MESSAGES: :[[@LINE-6]]:3: note: it became invalid because the pointee s left the scope here
+  p->m = 4;
+  // CHECK-MESSAGES: :[[@LINE-1]]:6: warning: dereferencing a dangling pointer
+  // CHECK-MESSAGES: :[[@LINE-9]]:3: note: it became invalid because the pointee s left the scope here
+}
+
+// No Pointer involved, thus not checked
+void ignore_access_on_non_ref_ptr() {
+  S s;
+  s.m = 3;
+  s.f();
+}
+
+// Note: the messages below are for the template instantiation in instantiate_ref_leaves_scope_template
+// The checker only checks instantiations
+template<typename T>
+void ref_leaves_scope_template() {
+  T p;
+  {
+    int i = 0;
+    p = &i;
+    *p = 2; // OK
+  }
+  *p = 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: dereferencing a dangling pointer
+  // CHECK-MESSAGES: :[[@LINE-3]]:3: note: it became invalid because the pointee i left the scope here
+}
+
+void instantiate_ref_leaves_scope_template() {
+  ref_leaves_scope_template<int*>();
+}
+
+int global_i = 4;
+int *global_init_p = &global_i; // OK
+int *global_uninit_p;
+// CHECK-MESSAGES: :[[@LINE-1]]:6: warning: the pset of global_uninit_p must be a subset of {(static), (null)}, but is {(invalid)}
+int *global_null_p = nullptr; // OK
+
+void uninitialized_static() {
+  static int* p;
+  // CHECK-MESSAGES: :[[@LINE-1]]:15: warning: the pset of p must be a subset of {(static), (null)}, but is {(invalid)}
+}