[Analyzer] Iterator Checkers - Model `empty()` method of containers

[baloghadamsoftware]

Summary

Modeling of the empty() method is essential for more accurate reporting past-the-end iterator access.

[Szelethus]

Hmm, an idea just popped into my head. I'm not sure whether we have a single checker that does so much complicated (and totally awesome) modeling as IteratorChecker. What do you think about a debug checker similar to debug.ExprInspection, like debug.IteratorInspection?

// RUN: %clang_analyzer_cc1 -analyzer-checker=core,debug.IteratorInspection

template <class Cont>
void clang_analyzer_container_size(const Cont &);

template <class It, class Cont>
void clang_analyzer_is_attached_to_container(const It &, const Cont &);

void non_empty1(const std::vector<int> &V) {
  assert(!V.empty());
  for (auto n: V) {}
  clang_analyzer_container_size(V); // expected-warning{{[1, intmax]}}
}

void non_empty2(const std::vector<int> &V) {
  for (auto n: V) {}
  assert(V.empty());
  clang_analyzer_container_size(V); // expected-warning{{[0, 0]}}
}

void foo(std::vector<int> v1, std::vector<int> v2) {
  clang_analyzer_is_attached_to_container(v1.begin(), v2); // expected-warning{{FALSE}}
}

etc etc.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

714

We seem to retrieve the CXXInstanceCall here too?

[Szelethus]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

1741–1763

But what if we have a container for which the iterator isn't an inline class, or we don't even have an in-class alias for it? I think whether the record has a begin/end method would be a better heuristic.

test/Analysis/iterator-range.cpp

247

Aha, the for loop is here to force a state split on whether V is empty or not, correct?

[sanaanajjar231288]

In D62688#1549574, @Szelethus wrote:

Hmm, an idea just popped into my head. I'm not sure whether we have a single checker that does so much complicated (and totally awesome) modeling as IteratorChecker. What do you think about a debug checker similar to debug.ExprInspection, like debug.IteratorInspection?

// RUN: %clang_analyzer_cc1 -analyzer-checker=core,debug.IteratorInspection

template <class Cont>
void clang_analyzer_container_size(const Cont &);

template <class It, class Cont>
void clang_analyzer_is_attached_to_container(const It &, const Cont &);

void non_empty1(const std::vector<int> &V) {
  assert(!V.empty());
  for (auto n: V) {}
  clang_analyzer_container_size(V); // expected-warning{{[1, intmax]}}
}

void non_empty2(const std::vector<int> &V) {
  for (auto n: V) {}
  assert(V.empty());
  clang_analyzer_container_size(V); // expected-warning{{[0, 0]}}
}

void foo(std::vector<int> v1, std::vector<int> v2) {
  clang_analyzer_is_attached_to_container(v1.begin(), v2); // expected-warning{{FALSE}}
}

etc etc.

[baloghadamsoftware]

In D62688#1549574, @Szelethus wrote:

Hmm, an idea just popped into my head. I'm not sure whether we have a single checker that does so much complicated (and totally awesome) modeling as IteratorChecker. What do you think about a debug checker similar to debug.ExprInspection, like debug.IteratorInspection?

Good idea! However, I would do it in a way that we can reuse our existing debug functions in the tests:

template <typename Iter> long clang_iterator_position(const Iter&);
template <typename Iter, typename Cont> const Cont& clang_iterator_container(const Iter&);
template <typename Iter> long clang_container_begin(const Iter&);
template <typename Iter> long clang_container_end(const Iter&);

Then we can nest calls for these functions into call of clang_analyzer_dump(), clang_analyzer_eval(), clang_analyzer_denote() etc.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

714

Eventually this function needs refactoring.

1741–1763

Or maybe both, or maybe either. I am not sure here.

test/Analysis/iterator-range.cpp

247

Yes.

[Szelethus]

In D62688#1606096, @baloghadamsoftware wrote:

In D62688#1549574, @Szelethus wrote:

Hmm, an idea just popped into my head. I'm not sure whether we have a single checker that does so much complicated (and totally awesome) modeling as IteratorChecker. What do you think about a debug checker similar to debug.ExprInspection, like debug.IteratorInspection?

Good idea! However, I would do it in a way that we can reuse our existing debug functions in the tests:

template <typename Iter> long clang_iterator_position(const Iter&);
template <typename Iter, typename Cont> const Cont& clang_iterator_container(const Iter&);
template <typename Iter> long clang_container_begin(const Iter&);
template <typename Iter> long clang_container_end(const Iter&);

Then we can nest calls for these functions into call of clang_analyzer_dump(), clang_analyzer_eval(), clang_analyzer_denote() etc.

Sounds awesome! I personally struggle a bit with these patches because the problem is so complex, I think this would help with reviewing tremendously.

[baloghadamsoftware]

Superseded by D76590.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

class IteratorChecker
 
   std::unique_ptr<BugType> OutOfRangeBugType;
   std::unique_ptr<BugType> MismatchedBugType;
   std::unique_ptr<BugType> InvalidatedBugType;
 
   void handleComparison(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                         const SVal &LVal, const SVal &RVal,
                         OverloadedOperatorKind Op) const;
+  void handleEmpty(CheckerContext &C, const Expr *CE, const SVal &Cont,
+                   const SVal &RetVal) const;
   void processComparison(CheckerContext &C, ProgramStateRef State,
                          SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
                          OverloadedOperatorKind Op) const;
   void verifyAccess(CheckerContext &C, const SVal &Val) const;
   void verifyDereference(CheckerContext &C, const SVal &Val) const;
   void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
                        bool Postfix) const;
   void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
                                IteratorPosition)
 
 REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
 
 namespace {
 
 bool isIteratorType(const QualType &Type);
 bool isIterator(const CXXRecordDecl *CRD);
+bool isContainerType(const QualType &Type);
 bool isComparisonOperator(OverloadedOperatorKind OK);
 bool isBeginCall(const FunctionDecl *Func);
 bool isEndCall(const FunctionDecl *Func);
 bool isAssignCall(const FunctionDecl *Func);
 bool isClearCall(const FunctionDecl *Func);
 bool isPushBackCall(const FunctionDecl *Func);
 bool isEmplaceBackCall(const FunctionDecl *Func);
+bool isEmptyCall(const FunctionDecl *Func);
 bool isPopBackCall(const FunctionDecl *Func);
 bool isPushFrontCall(const FunctionDecl *Func);
 bool isEmplaceFrontCall(const FunctionDecl *Func);
 bool isPopFrontCall(const FunctionDecl *Func);
 bool isInsertCall(const FunctionDecl *Func);
 bool isEraseCall(const FunctionDecl *Func);
 bool isEraseAfterCall(const FunctionDecl *Func);
 bool isEmplaceCall(const FunctionDecl *Func);
if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
         }
       }
     }
 
     const auto *OrigExpr = Call.getOriginExpr();
     if (!OrigExpr)
       return;
 
+    if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+      if (isContainerType(InstCall->getCXXThisExpr()->getType())) {
+        if (isEmptyCall(Func)) {
+          handleEmpty(C, OrigExpr, InstCall->getCXXThisVal(),
+                      Call.getReturnValue());
+        }
+      }
+    }
+
+
+
     if (!isIteratorType(Call.getResultType()))
       return;
 
     auto State = C.getState();
 
     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
       if (isBeginCall(Func)) {
         handleBegin(C, OrigExpr, Call.getReturnValue(),
                     InstCall->getCXXThisVal());
         return;
       }
       
       if (isEndCall(Func)) {
         handleEnd(C, OrigExpr, Call.getReturnValue(),
if (!LPos) {
     State = setIteratorPosition(State, RVal,
                                 IteratorPosition::getPosition(Cont, Sym));
     RPos = getIteratorPosition(State, RVal);
   }
 
   processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
 }
 
+void IteratorChecker::handleEmpty(CheckerContext &C, const Expr *CE,
+                                  const SVal &Cont, const SVal &RetVal) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  ContReg = ContReg->getMostDerivedObjectRegion();
+
+  // If the container already has a begin symbol then use it. Otherwise first
+  // create a new one.
+  auto State = C.getState();
+  auto BeginSym = getContainerBegin(State, ContReg);
+  if (!BeginSym) {
+    State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
+                                 C.getLocationContext(), C.blockCount());
+    BeginSym = getContainerBegin(State, ContReg);
+  }
+  auto EndSym = getContainerEnd(State, ContReg);
+  if (!EndSym) {
+    State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
+                                 C.getLocationContext(), C.blockCount());
+    EndSym = getContainerEnd(State, ContReg);
+  }
+
+  processComparison(C, State, BeginSym, EndSym, RetVal, OO_EqualEqual);
+}
+
 void IteratorChecker::processComparison(CheckerContext &C,
                                         ProgramStateRef State, SymbolRef Sym1,
                                         SymbolRef Sym2, const SVal &RetVal,
                                         OverloadedOperatorKind Op) const {
   if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
     if ((State = relateSymbols(State, Sym1, Sym2,
                               (Op == OO_EqualEqual) ==
                                (TruthVal->getValue() != 0)))) {
void IteratorChecker::reportInvalidatedBug(const StringRef &Message,
                                            ExplodedNode *ErrNode) const {
   auto R = llvm::make_unique<BugReport>(*InvalidatedBugType, Message, ErrNode);
   R->markInteresting(Val);
   C.emitReport(std::move(R));
 }
 
 namespace {
 
+bool isContainer(const CXXRecordDecl *CRD);
 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
              BinaryOperator::Opcode Opc);
 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
              BinaryOperator::Opcode Opc);
 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
if (OPK == OO_Star) {
       continue;
     }
   }
 
   return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
          HasPostIncrOp && HasDerefOp;
 }
 
+bool isContainerType(const QualType &Type) {
+  if (isIteratorType(Type))
+    return false;
+
+  const auto *CRD = Type.getNonReferenceType()
+    ->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+  return isContainer(CRD);
+}
+
+bool isContainer(const CXXRecordDecl *CRD) {
+  if (!CRD)
+    return false;
+
+  for (const auto *Decl : CRD->decls()) {
+    const auto *TD = dyn_cast<TypeDecl>(Decl);
+    if (!TD)
+      continue;
+
+    const auto *Type = TD->getTypeForDecl();
+    if (!Type)
+      continue;
+    
+    const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+    if(!CRD)
+      continue;
+    
+    if (isIterator(CRD))
+      return true;
+  }
+
+  return false;
+}
+
 bool isComparisonOperator(OverloadedOperatorKind OK) {
   return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
          OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
 }
 
 bool isBeginCall(const FunctionDecl *Func) {
   const auto *IdInfo = Func->getIdentifier();
   if (!IdInfo)
bool isEraseAfterCall(const FunctionDecl *Func) {
   if (!isIteratorType(Func->getParamDecl(0)->getType()))
     return false;
   if (Func->getNumParams() == 2 &&
       !isIteratorType(Func->getParamDecl(1)->getType()))
     return false;
   return IdInfo->getName() == "erase_after";
 }
 
+bool isEmptyCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() > 0)
+    return false;
+  return IdInfo->getName() == "empty";
+}
+
 bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; }
 
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 }
 
 bool isAccessOperator(OverloadedOperatorKind OK) {
   return isDereferenceOperator(OK) || isIncrementOperator(OK) ||

test/Analysis/Inputs/system-header-simulator-cxx.h

public:
     const_iterator cbegin() const { return const_iterator(_start); }
     iterator end() { return iterator(_finish); }
     const_iterator end() const { return const_iterator(_finish); }
     const_iterator cend() const { return const_iterator(_finish); }
     T& front() { return *begin(); }
     const T& front() const { return *begin(); }
     T& back() { return *(end() - 1); }
     const T& back() const { return *(end() - 1); }
+
+    bool empty() const;
   };
   
   template<typename T>
   class list {
     struct __item {
       T data;
       __item *prev, *next;
     } *_start, *_finish;
public:
     iterator end() { return iterator(_finish); }
     const_iterator end() const { return const_iterator(_finish); }
     const_iterator cend() const { return const_iterator(_finish); }
 
     T& front() { return *begin(); }
     const T& front() const { return *begin(); }
     T& back() { return *--end(); }
     const T& back() const { return *--end(); }
+
+    bool empty() const;
   };
 
   template<typename T>
   class deque {
     typedef T value_type;
     typedef size_t size_type;
     typedef __deque_iterator<T, T *, T &> iterator;
     typedef __deque_iterator<T, const T *, const T &> const_iterator;
public:
     const_iterator cbegin() const { return const_iterator(_start); }
     iterator end() { return iterator(_finish); }
     const_iterator end() const { return const_iterator(_finish); }
     const_iterator cend() const { return const_iterator(_finish); }
     T& front() { return *begin(); }
     const T& front() const { return *begin(); }
     T& back() { return *(end() - 1); }
     const T& back() const { return *(end() - 1); }
+
+    bool empty() const;
   };
 
   template<typename T>
   class forward_list {
     struct __item {
       T data;
       __item *next;
     } *_start;
public:
     const_iterator begin() const { return const_iterator(_start); }
     const_iterator cbegin() const { return const_iterator(_start); }
     iterator end() { return iterator(); }
     const_iterator end() const { return const_iterator(); }
     const_iterator cend() const { return const_iterator(); }
 
     T& front() { return *begin(); }
     const T& front() const { return *begin(); }
+
+    bool empty() const;
   };
 
   template <typename CharT>
   class basic_string {
   public:
     basic_string();
     basic_string(const CharT *s);
 

test/Analysis/diagnostics/explicit-suppression.cpp

class C {
   // The virtual function is to make C not trivially copy assignable so that we call the
   // variant of std::copy() that does not defer to memmove().
   virtual int f();
 };
 
 void testCopyNull(C *I, C *E) {
   std::copy(I, E, (C *)0);
 #ifndef SUPPRESSED
-  // expected-warning@../Inputs/system-header-simulator-cxx.h:677 {{Called C++ object pointer is null}}
+  // expected-warning@../Inputs/system-header-simulator-cxx.h:685 {{Called C++ object pointer is null}}
 #endif
 }

test/Analysis/iterator-range.cpp

 // RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=false %s -verify
 // RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
 
 #include "Inputs/system-header-simulator-cxx.h"
 
 void clang_analyzer_warnIfReached();
 
+extern void __assert_fail (__const char *__assertion, __const char *__file,
+    unsigned int __line, __const char *__function)
+     __attribute__ ((__noreturn__));
+#define assert(expr) \
+  ((expr)  ? (void)(0)  : __assert_fail (#expr, __FILE__, __LINE__, __func__))
+
 void simple_good_end(const std::vector<int> &v) {
   auto i = v.end();
   if (i != v.end()) {
     clang_analyzer_warnIfReached();
     *i; // no-warning
   }
 }
 

 
 void good_derived(simple_container c) {
   auto i0 = c.end();
   if (i0 != c.end()) {
     clang_analyzer_warnIfReached();
     *i0; // no-warning
   }
 }
+
+void empty(const std::vector<int> &V) {
+  for (auto n: V) {}
+  *V.begin(); // expected-warning{{Past-the-end iterator dereferenced}}
+}
+
+void non_empty1(const std::vector<int> &V) {
+  assert(!V.empty());
+  for (auto n: V) {}
+  *V.begin(); // no-warning
+}
+
+void non_empty2(const std::vector<int> &V) {
+  for (auto n: V) {}
+  assert(!V.empty());
+  *V.begin(); // no-warning
+}
+
+bool is_empty_V() {
+  std::vector<int> V;
+  bool e = V.empty();
+  return e;
+}
+
+void deferred_emptiness_check() {
+  bool b = is_empty_V();
+  if (b) {
+  }
+}