[Analyzer] Model default constructors of containers

[baloghadamsoftware]

Summary

Model default constructors of containers by setting their abstract begin() and end() symbols to equal.

clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp

 
 class ContainerModeling
   : public Checker<check::PostCall, check::LiveSymbols, check::DeadSymbols> {
 
   void handleBegin(CheckerContext &C, const Expr *CE, SVal RetVal,
                    SVal Cont) const;
   void handleEnd(CheckerContext &C, const Expr *CE, SVal RetVal,
                  SVal Cont) const;
+  void handleDefaultConstruction(CheckerContext &C, const Expr *CE,
+                                 SVal Cont) const;
   void handleAssignment(CheckerContext &C, SVal Cont, const Expr *CE = nullptr,
                         SVal OldCont = UndefinedVal()) const;
   void handleAssign(CheckerContext &C, SVal Cont, const Expr *ContE) const;
   void handleClear(CheckerContext &C, SVal Cont, const Expr *ContE) const;
   void handlePushBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
   void handlePopBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
   void handlePushFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
   void handlePopFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
CallDescriptionMap<TwoItParamFn> TwoIterParamFunctions = {
     {{0, "erase_after", 2},
      &ContainerModeling::handleEraseAfter},
   };
                                                           
 };
 
 bool isBeginCall(const FunctionDecl *Func);
 bool isEndCall(const FunctionDecl *Func);
+bool isContainer(const CXXRecordDecl *CRD);
 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
 ProgramStateRef createContainerBegin(ProgramStateRef State,
                                      const MemRegion *Cont, const Expr *E,
                                      QualType T, const LocationContext *LCtx,
if (Op == OO_Equal) {
         handleAssignment(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
                      Call.getArgSVal(0));
         return;
       }
 
       handleAssignment(C, InstCall->getCXXThisVal());
       return;
     }
+  } else if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Func)) {
+    if (!isContainer(Ctor->getParent()))
+      return;
+
+    if (Ctor->getNumParams() == 0)
+      handleDefaultConstruction(C, Call.getOriginExpr(),
+                                *Call.getReturnValueUnderConstruction());
   } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
     const auto *OrigExpr = Call.getOriginExpr();
     if (!OrigExpr)
       return;
 
     if (isBeginCall(Func)) {
       handleBegin(C, OrigExpr, getReturnIterator(Call),
                   InstCall->getCXXThisVal());
if (!EndSym) {
     EndSym = getContainerEnd(State, ContReg);
   }
 
   State = setIteratorPosition(State, RetVal,
                               IteratorPosition::getPosition(ContReg, EndSym));
   C.addTransition(State);
 }
 
+void ContainerModeling::handleDefaultConstruction(CheckerContext &C,
+                                                  const Expr *CE,
+                                                  SVal Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  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);
+
+  State = relateSymbols(State, BeginSym, EndSym, true);
+  assert(State &&
+         "Setting size of newly constructed containers must always succeed");
+  C.addTransition(State);
+}
+
 void ContainerModeling::handleAssignment(CheckerContext &C, SVal Cont,
                                          const Expr *CE, SVal OldCont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 

 
 bool isEndCall(const FunctionDecl *Func) {
   const auto *IdInfo = Func->getIdentifier();
   if (!IdInfo)
     return false;
   return IdInfo->getName().endswith_lower("end");
 }
 
+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 *Typ = TD->getTypeForDecl();
+    if (!Typ)
+      continue;
+
+    if (isIteratorType(Typ))
+      return true;
+  }
+
+  return false;
+}
+
 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
                                       const MemRegion *Reg) {
   auto TI = getDynamicTypeInfo(State, Reg);
   if (!TI.isValid())
     return nullptr;
 
   auto Type = TI.getType();
   if (const auto *RefT = Type->getAs<ReferenceType>()) {

clang/lib/StaticAnalyzer/Checkers/Iterator.h

 template<>
 struct ProgramStateTrait<iterator::ContainerMap>
   : public ProgramStatePartialTrait<iterator::ContainerMapTy> {
   static void *GDMIndex() { static int Index; return &Index; }
 };
 
 namespace iterator {
 
-bool isIteratorType(const QualType &Type);
+bool isIteratorType(const QualType &QTyp);
+bool isIteratorType(const Type* Typ);
 bool isIterator(const CXXRecordDecl *CRD);
 bool isComparisonOperator(OverloadedOperatorKind OK);
 bool isInsertCall(const FunctionDecl *Func);
 bool isEraseCall(const FunctionDecl *Func);
 bool isEraseAfterCall(const FunctionDecl *Func);
 bool isEmplaceCall(const FunctionDecl *Func);
 bool isAccessOperator(OverloadedOperatorKind OK);
 bool isAccessOperator(UnaryOperatorKind OK);
ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val,
                                        const LocationContext *LCtx,
                                        unsigned blockCount);
 ProgramStateRef advancePosition(ProgramStateRef State,
                                 const SVal &Iter,
                                 OverloadedOperatorKind Op,
                                 const SVal &Distance);
 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
                                  long Scale);
+ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
+                              SymbolRef Sym2, bool Equal);
 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
              BinaryOperator::Opcode Opc);
 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
              BinaryOperator::Opcode Opc);
 
 // Returns the value of the iterator argument if it non-class value (a pointer
 // or a reference). Otherwise it returns the iterator parameter location (see
 // CallEvent::getParameterLocation()).

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp

 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 
 #include "Iterator.h"
 
 namespace clang {
 namespace ento {
 namespace iterator {
 
-bool isIteratorType(const QualType &Type) {
-  if (Type->isPointerType())
+bool isIteratorType(const QualType &QTyp) {
+  return isIteratorType(QTyp.getTypePtr());
+}
+
+bool isIteratorType(const Type *Typ) {
+  if (Typ->isPointerType())
     return true;
 
-  const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+  const auto *CRD = Typ->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+  if (!CRD)
+    return false;
+
+  if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CRD))
+    CRD = CTSD->getSpecializedTemplate()->getTemplatedDecl();
+
   return isIterator(CRD);
 }
 
 bool isIterator(const CXXRecordDecl *CRD) {
   if (!CRD)
     return false;
 
   const auto Name = CRD->getName();
   if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
         Name.endswith_lower("it")))
     return false;
 
-  bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
-       HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
+  if ((!CRD->hasSimpleCopyConstructor() &&
+       !CRD->hasUserDeclaredCopyConstructor()) ||
+      (!CRD->hasSimpleCopyAssignment() &&
+       !CRD->hasUserDeclaredCopyAssignment()) ||
+      (!CRD->hasSimpleDestructor() &&
+       !CRD->hasUserDeclaredDestructor()))
+    return false;
+
+  bool HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
   for (const auto *Method : CRD->methods()) {
-    if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
-      if (Ctor->isCopyConstructor()) {
-        HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
-      }
-      continue;
-    }
-    if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
-      HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
-      continue;
-    }
-    if (Method->isCopyAssignmentOperator()) {
-      HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
-      continue;
-    }
     if (!Method->isOverloadedOperator())
       continue;
     const auto OPK = Method->getOverloadedOperator();
     if (OPK == OO_PlusPlus) {
       HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
       HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
       continue;
     }
     if (OPK == OO_Star) {
       HasDerefOp = (Method->getNumParams() == 0);
       continue;
     }
   }
 
-  return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
-         HasPostIncrOp && HasDerefOp;
+  return HasPreIncrOp && HasPostIncrOp && HasDerefOp;
 }
 
 bool isComparisonOperator(OverloadedOperatorKind OK) {
   return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
          OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
 }
 
 bool isInsertCall(const FunctionDecl *Func) {
if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
     NewState = NewState->assume(*DV, true);
     if (!NewState)
       return State;
   }
 
   return NewState;
 }
 
+ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
+                              SymbolRef Sym2, bool Equal) {
+  auto &SVB = State->getStateManager().getSValBuilder();
+
+  // FIXME: This code should be reworked as follows:
+  // 1. Subtract the operands using evalBinOp().
+  // 2. Assume that the result doesn't overflow.
+  // 3. Compare the result to 0.
+  // 4. Assume the result of the comparison.
+  const auto comparison =
+    SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
+                  nonloc::SymbolVal(Sym2), SVB.getConditionType());
+
+  assert(comparison.getAs<DefinedSVal>() &&
+    "Symbol comparison must be a `DefinedSVal`");
+
+  auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
+  if (!NewState)
+    return nullptr;
+
+  if (const auto CompSym = comparison.getAsSymbol()) {
+    assert(isa<SymIntExpr>(CompSym) &&
+           "Symbol comparison must be a `SymIntExpr`");
+    assert(BinaryOperator::isComparisonOp(
+               cast<SymIntExpr>(CompSym)->getOpcode()) &&
+           "Symbol comparison must be a comparison");
+    return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
+  }
+
+  return NewState;
+}
+
 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
              BinaryOperator::Opcode Opc) {
   return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
 }
 
 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
              BinaryOperator::Opcode Opc) {
   auto &SVB = State->getStateManager().getSValBuilder();

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

public:
   void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 };
 
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 bool isSimpleComparisonOperator(BinaryOperatorKind OK);
 ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val);
-ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
-                              SymbolRef Sym2, bool Equal);
 const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call);
 
 } // namespace
 
 void IteratorModeling::checkPostCall(const CallEvent &Call,
                                      CheckerContext &C) const {
   // Record new iterator positions and iterator position changes
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
if (auto Reg = Val.getAsRegion()) {
     Reg = Reg->getMostDerivedObjectRegion();
     return State->remove<IteratorRegionMap>(Reg);
   } else if (const auto Sym = Val.getAsSymbol()) {
     return State->remove<IteratorSymbolMap>(Sym);
   }
   return State;
 }
 
-ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
-                              SymbolRef Sym2, bool Equal) {
-  auto &SVB = State->getStateManager().getSValBuilder();
-
-  // FIXME: This code should be reworked as follows:
-  // 1. Subtract the operands using evalBinOp().
-  // 2. Assume that the result doesn't overflow.
-  // 3. Compare the result to 0.
-  // 4. Assume the result of the comparison.
-  const auto comparison =
-    SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
-                  nonloc::SymbolVal(Sym2), SVB.getConditionType());
-
-  assert(comparison.getAs<DefinedSVal>() &&
-    "Symbol comparison must be a `DefinedSVal`");
-
-  auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
-  if (!NewState)
-    return nullptr;
-
-  if (const auto CompSym = comparison.getAsSymbol()) {
-    assert(isa<SymIntExpr>(CompSym) &&
-           "Symbol comparison must be a `SymIntExpr`");
-    assert(BinaryOperator::isComparisonOp(
-               cast<SymIntExpr>(CompSym)->getOpcode()) &&
-           "Symbol comparison must be a comparison");
-    return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
-  }
-
-  return NewState;
-}
-
 const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) {
   while (Node) {
     ProgramPoint PP = Node->getLocation();
     if (auto Enter = PP.getAs<CallEnter>()) {
       if (Enter->getCallExpr() == Call)
         break;
     }
 

clang/test/Analysis/container-modeling.cpp

void end(const std::vector<int> &V) {
 
   clang_analyzer_denote(clang_analyzer_container_end(V), "$V.end()");
   clang_analyzer_express(clang_analyzer_container_end(V)); // expected-warning{{$V.end()}}
                                                            // expected-note@-1{{$V.end()}}
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 ///
+/// C O N T A I N E R   C O N S T R U C T O R S
+///
+////////////////////////////////////////////////////////////////////////////////
+
+// Default Constructor
+
+void default_constructor() {
+  std::vector<int> V;
+
+  clang_analyzer_eval(clang_analyzer_container_begin(V) ==
+                      clang_analyzer_container_end(V));
+  // expected-warning@-2{{TRUE}}
+  // expected-note@-3   {{TRUE}}
+}
+
+////////////////////////////////////////////////////////////////////////////////
+///
 /// C O N T A I N E R   A S S I G N M E N T S
 ///
 ////////////////////////////////////////////////////////////////////////////////
 
 // Move
 
 void move_assignment(std::vector<int> &V1, std::vector<int> &V2) {
   V1.cbegin();