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

[baloghadamsoftware]

Summary

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

[baloghadamsoftware]

Gentle ping.

[baloghadamsoftware]

Superseded by D76604.

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 handleSize(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 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);
+bool isSizeCall(const FunctionDecl *Func);
 bool isAssignmentOperator(OverloadedOperatorKind OK);
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 bool isAccessOperator(OverloadedOperatorKind OK);
 bool isDereferenceOperator(OverloadedOperatorKind OK);
 bool isIncrementOperator(OverloadedOperatorKind OK);
 bool isDecrementOperator(OverloadedOperatorKind OK);
 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
                                    unsigned BlockCount);
 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
                                             const SVal &Val);
 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
                                     const IteratorPosition &Pos);
 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
                                  long Scale);
+const llvm::APSInt* calculateSize(ProgramStateRef State, SymbolRef Begin,
+                                  SymbolRef End);
 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
                                                const MemRegion *Cont);
 ProgramStateRef
 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
                                      const MemRegion *Cont, SymbolRef Offset,
                                      BinaryOperator::Opcode Opc);
 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
                                             SymbolRef Offset,
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 (isSizeCall(Func)) {
+          handleSize(C, OrigExpr, InstCall->getCXXThisVal(),
+                     Call.getReturnValue());
+          return;
+        }
+      }
+    }
+
     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(),
void IteratorChecker::processComparison(CheckerContext &C,
   }
   
   if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
     StateFalse = StateFalse->assume(*ConditionVal, false);
     C.addTransition(StateFalse);
   }
 }
 
+void IteratorChecker::handleSize(CheckerContext &C, const Expr *CE,
+                                 const SVal &Cont, const SVal &RetVal) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  ContReg = ContReg->getMostDerivedObjectRegion();
+ 
+  auto State = C.getState();
+
+  State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
+                               C.getLocationContext(), C.blockCount());
+  auto BeginSym = getContainerBegin(State, ContReg);
+  State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
+                             C.getLocationContext(), C.blockCount());
+  auto EndSym = getContainerEnd(State, ContReg);
+  const llvm::APSInt *CalcSize = calculateSize(State, BeginSym, EndSym);
+
+  auto &SVB = C.getSValBuilder();
+  auto &BVF = State->getBasicVals();
+  const llvm::APSInt *RetSize = nullptr;
+  if (const auto *KnownSize = SVB.getKnownValue(State, RetVal)) {
+    RetSize = &BVF.Convert(C.getASTContext().LongTy, *KnownSize);
+  }
+
+  if (RetSize) {
+    // If the return value is a concrete integer, then try to adjust the size
+    // of the container (the difference between its `begin()` and `end()` to
+    // this size. Function `relateSymbols()` returns null if it contradits
+    // the current size.
+    const auto CalcEnd =
+      SVB.evalBinOp(State, BO_Add, nonloc::SymbolVal(EndSym),
+                    nonloc::ConcreteInt(*RetSize), C.getASTContext().LongTy)
+      .getAsSymbol();
+    if (CalcEnd) {
+      State = relateSymbols(State, BeginSym, EndSym, true);
+    }
+  } else {
+    if (CalcSize) {
+      // If the current size is a concrete integer, bind this to the return
+      // value of the function instead of the current one.
+      auto CSize = nonloc::ConcreteInt(BVF.Convert(CE->getType(), *CalcSize));
+      State = State->BindExpr(CE, C.getLocationContext(), CSize);
+    } else {
+      // If neither the returned nor the current size is a concrete integer,
+      // replace the return value with the symbolic difference of the
+      // container's `begin()` and `end()` symbols.
+      auto Size = SVB.evalBinOp(State, BO_Sub, nonloc::SymbolVal(EndSym),
+                                nonloc::SymbolVal(BeginSym),
+                                C.getASTContext().LongTy);
+      if (Size.isUnknown())
+        return;
+
+      auto CastedSize = SVB.evalCast(Size, CE->getType(),
+                                     C.getASTContext().LongTy);
+      State = State->BindExpr(CE, C.getLocationContext(), CastedSize);
+    }
+  }
+
+  C.addTransition(State);
+}
+
 void IteratorChecker::verifyDereference(CheckerContext &C,
                                         const SVal &Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos && isPastTheEnd(State, *Pos)) {
     auto *N = C.generateNonFatalErrorNode(State);
     if (!N)
       return;
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 isSizeCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() > 0)
+    return false;
+  if (!Func->getReturnType()->isUnsignedIntegerType())
+    return false;
+  return IdInfo->getName() == "size";
+}
+
 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) ||
if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
     NewState = NewState->assume(*DV, true);
     if (!NewState)
       return State;
   }
 
   return NewState;
 }
 
+const llvm::APSInt* calculateSize(ProgramStateRef State, SymbolRef Begin,
+                                  SymbolRef End) {
+  if (!Begin || !End)
+    return nullptr;
+
+  auto &SVB = State->getStateManager().getSValBuilder();
+  auto &SymMgr = State->getSymbolManager();
+  auto Size = SVB.evalBinOp(State, BO_Sub, nonloc::SymbolVal(End),
+                            nonloc::SymbolVal(Begin),
+                            SymMgr.getType(End)).getAsSymbol();
+  if (!Size)
+    return nullptr;
+
+  llvm::APSInt Diff = llvm::APSInt::get(0);
+  if (const auto *SizeExpr = dyn_cast<SymIntExpr>(Size)) {
+    assert(BinaryOperator::isAdditiveOp(SizeExpr->getOpcode()) &&
+           "Symbolic positions must be additive expressions");
+    if (SizeExpr->getOpcode() == BO_Add) {
+      Diff = SizeExpr->getRHS();
+    } else {
+      Diff = -SizeExpr->getRHS();
+    }
+    Size = SizeExpr->getLHS();
+  }
+
+  auto &CM = State->getConstraintManager();
+  if (const auto *SizeInt = CM.getSymVal(State, Size)) {
+    auto &BVF = SymMgr.getBasicVals();
+    return &BVF.getValue(Diff + *SizeInt);
+  }
+
+  return nullptr;
+}
+
 template <typename Condition, typename Process>
 ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
                                          Process Proc) {
   auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
   auto RegionMap = State->get<IteratorRegionMap>();
   bool Changed = false;
   for (const auto Reg : RegionMap) {
     if (Cond(Reg.second)) {

test/Analysis/iterator-range.cpp

 
 void good_derived(simple_container c) {
   auto i0 = c.end();
   if (i0 != c.end()) {
     clang_analyzer_warnIfReached();
     *i0; // no-warning
   }
 }
+
+void size0(const std::vector<int>& V) {
+  if (V.size() != 0)
+    return;
+
+  *V.begin(); // expected-warning{{Past-the-end iterator dereferenced}}
+}
+
+void size1(const std::vector<int>& V) {
+  if(V.size() != 1)
+    return;
+  *V.begin(); // no-warning
+  auto i = V.cbegin();
+  ++i;
+  *i; // expected-warning{{Past-the-end iterator dereferenced}}
+}