29using namespace iterator;
33class ContainerModeling
34 :
public Checker<check::PostCall, check::LiveSymbols, check::DeadSymbols> {
56 const Expr *ContE)
const;
58 const char *Sep)
const override;
61 ContainerModeling() =
default;
75 {{{
"clear"}, 0}, &ContainerModeling::handleClear},
76 {{{
"assign"}, 2}, &ContainerModeling::handleAssign},
77 {{{
"push_back"}, 1}, &ContainerModeling::handlePushBack},
78 {{{
"emplace_back"}, 1}, &ContainerModeling::handlePushBack},
79 {{{
"pop_back"}, 0}, &ContainerModeling::handlePopBack},
80 {{{
"push_front"}, 1}, &ContainerModeling::handlePushFront},
81 {{{
"emplace_front"}, 1}, &ContainerModeling::handlePushFront},
82 {{{
"pop_front"}, 0}, &ContainerModeling::handlePopFront},
86 {{{
"insert"}, 2}, &ContainerModeling::handleInsert},
87 {{{
"emplace"}, 2}, &ContainerModeling::handleInsert},
88 {{{
"erase"}, 1}, &ContainerModeling::handleErase},
89 {{{
"erase_after"}, 1}, &ContainerModeling::handleEraseAfter},
93 {{{
"erase"}, 2}, &ContainerModeling::handleErase},
94 {{{
"erase_after"}, 2}, &ContainerModeling::handleEraseAfter},
108 unsigned BlockCount);
112 unsigned BlockCount);
148 const auto *
Func = dyn_cast_or_null<FunctionDecl>(
Call.getDecl());
152 if (
Func->isOverloadedOperator()) {
153 const auto Op =
Func->getOverloadedOperator();
154 if (Op == OO_Equal) {
156 const auto *InstCall = cast<CXXInstanceCall>(&
Call);
157 if (cast<CXXMethodDecl>(
Func)->isMoveAssignmentOperator()) {
167 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&
Call)) {
168 const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(
Call);
170 (this->**Handler0)(
C, InstCall->getCXXThisVal(),
171 InstCall->getCXXThisExpr());
175 const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(
Call);
177 (this->**Handler1)(
C, InstCall->getCXXThisVal(),
Call.getArgSVal(0));
181 const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(
Call);
183 (this->**Handler2)(
C, InstCall->getCXXThisVal(),
Call.getArgSVal(0),
188 const auto *OrigExpr =
Call.getOriginExpr();
192 if (isBeginCall(
Func)) {
193 handleBegin(
C, OrigExpr,
Call.getReturnValue(),
194 InstCall->getCXXThisVal());
198 if (isEndCall(
Func)) {
199 handleEnd(
C, OrigExpr,
Call.getReturnValue(),
200 InstCall->getCXXThisVal());
211 for (
const auto &Cont : ContMap) {
212 const auto CData = Cont.second;
213 if (CData.getBegin()) {
215 if(
const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
218 if (CData.getEnd()) {
220 if(
const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
226void ContainerModeling::checkDeadSymbols(
SymbolReaper &SR,
229 auto State =
C.getState();
232 for (
const auto &Cont : ContMap) {
236 if (!hasLiveIterators(State, Cont.first)) {
242 C.addTransition(State);
255 auto State =
C.getState();
256 auto BeginSym = getContainerBegin(State, ContReg);
258 State = createContainerBegin(State, ContReg, CE,
C.getASTContext().LongTy,
259 C.getLocationContext(),
C.blockCount());
260 BeginSym = getContainerBegin(State, ContReg);
264 C.addTransition(State);
277 auto State =
C.getState();
278 auto EndSym = getContainerEnd(State, ContReg);
280 State = createContainerEnd(State, ContReg, CE,
C.getASTContext().LongTy,
281 C.getLocationContext(),
C.blockCount());
282 EndSym = getContainerEnd(State, ContReg);
286 C.addTransition(State);
290 const Expr *CE,
SVal OldCont)
const {
299 auto State =
C.getState();
302 State = invalidateAllIteratorPositions(State, ContReg);
313 if (
const auto OldEndSym = OldCData->getEnd()) {
318 State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
320 auto &SymMgr =
C.getSymbolManager();
321 auto &SVB =
C.getSValBuilder();
324 SymMgr.conjureSymbol(CE,
C.getLocationContext(),
325 C.getASTContext().LongTy,
C.blockCount());
328 State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
330 State = setContainerData(State, ContReg,
335 State = rebaseSymbolInIteratorPositionsIf(
336 State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
340 State = reassignAllIteratorPositions(State, OldContReg, ContReg);
342 if (
const auto OldBeginSym = OldCData->getBegin()) {
347 setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
349 State = setContainerData(State, ContReg,
353 setContainerData(State, OldContReg, OldCData->newBegin(
nullptr));
358 State = reassignAllIteratorPositions(State, OldContReg, ContReg);
362 C.addTransition(State);
366 const Expr *ContE)
const {
374 auto State =
C.getState();
375 State = invalidateAllIteratorPositions(State, ContReg);
376 C.addTransition(State);
380 const Expr *ContE)
const {
389 auto State =
C.getState();
390 if (!hasSubscriptOperator(State, ContReg) ||
391 !backModifiable(State, ContReg)) {
394 if (
const auto EndSym = CData->getEnd()) {
396 invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
397 C.addTransition(State);
403 getChangeTag(
C,
"became empty", ContReg, ContE);
404 State = invalidateAllIteratorPositions(State, ContReg);
405 C.addTransition(State, ChangeTag);
409 const Expr *ContE)
const {
417 auto State =
C.getState();
418 if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
419 State = invalidateAllIteratorPositions(State, ContReg);
420 C.addTransition(State);
429 if (
const auto EndSym = CData->getEnd()) {
430 if (hasSubscriptOperator(State, ContReg)) {
431 State = invalidateIteratorPositions(State, EndSym, BO_GE);
433 auto &SymMgr =
C.getSymbolManager();
434 auto &BVF = SymMgr.getBasicVals();
435 auto &SVB =
C.getSValBuilder();
436 const auto newEndSym =
437 SVB.evalBinOp(State, BO_Add,
440 SymMgr.
getType(EndSym)).getAsSymbol();
442 getChangeTag(
C,
"extended to the back by 1 position", ContReg, ContE);
443 State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
444 C.addTransition(State, ChangeTag);
449 const Expr *ContE)
const {
456 auto State =
C.getState();
461 if (
const auto EndSym = CData->getEnd()) {
462 auto &SymMgr =
C.getSymbolManager();
463 auto &BVF = SymMgr.getBasicVals();
464 auto &SVB =
C.getSValBuilder();
466 SVB.evalBinOp(State, BO_Sub,
469 SymMgr.
getType(EndSym)).getAsSymbol();
471 getChangeTag(
C,
"shrank from the back by 1 position", ContReg, ContE);
475 if (hasSubscriptOperator(State, ContReg) &&
476 backModifiable(State, ContReg)) {
477 State = invalidateIteratorPositions(State, BackSym, BO_GE);
478 State = setContainerData(State, ContReg, CData->newEnd(
nullptr));
480 State = invalidateIteratorPositions(State, BackSym, BO_EQ);
482 auto newEndSym = BackSym;
483 State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
484 C.addTransition(State, ChangeTag);
489 const Expr *ContE)
const {
497 auto State =
C.getState();
498 if (hasSubscriptOperator(State, ContReg)) {
499 State = invalidateAllIteratorPositions(State, ContReg);
500 C.addTransition(State);
506 if (
const auto BeginSym = CData->getBegin()) {
507 auto &SymMgr =
C.getSymbolManager();
508 auto &BVF = SymMgr.getBasicVals();
509 auto &SVB =
C.getSValBuilder();
510 const auto newBeginSym =
511 SVB.evalBinOp(State, BO_Sub,
514 SymMgr.
getType(BeginSym)).getAsSymbol();
516 getChangeTag(
C,
"extended to the front by 1 position", ContReg, ContE);
517 State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
518 C.addTransition(State, ChangeTag);
524 const Expr *ContE)
const {
531 auto State =
C.getState();
538 if (
const auto BeginSym = CData->getBegin()) {
539 if (hasSubscriptOperator(State, ContReg)) {
540 State = invalidateIteratorPositions(State, BeginSym, BO_LE);
542 State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
544 auto &SymMgr =
C.getSymbolManager();
545 auto &BVF = SymMgr.getBasicVals();
546 auto &SVB =
C.getSValBuilder();
547 const auto newBeginSym =
548 SVB.evalBinOp(State, BO_Add,
551 SymMgr.
getType(BeginSym)).getAsSymbol();
553 getChangeTag(
C,
"shrank from the front by 1 position", ContReg, ContE);
554 State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
555 C.addTransition(State, ChangeTag);
567 auto State =
C.getState();
574 if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
575 if (frontModifiable(State, ContReg)) {
576 State = invalidateAllIteratorPositions(State, ContReg);
578 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
581 if (
const auto EndSym = CData->getEnd()) {
582 State = invalidateIteratorPositions(State, EndSym, BO_GE);
583 State = setContainerData(State, ContReg, CData->newEnd(
nullptr));
586 C.addTransition(State);
598 auto State =
C.getState();
606 if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
607 if (frontModifiable(State, ContReg)) {
608 State = invalidateAllIteratorPositions(State, ContReg);
610 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
613 if (
const auto EndSym = CData->getEnd()) {
614 State = invalidateIteratorPositions(State, EndSym, BO_GE);
615 State = setContainerData(State, ContReg, CData->newEnd(
nullptr));
619 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
621 C.addTransition(State);
631 auto State =
C.getState();
641 if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
642 if (frontModifiable(State, ContReg)) {
643 State = invalidateAllIteratorPositions(State, ContReg);
645 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
648 if (
const auto EndSym = CData->getEnd()) {
649 State = invalidateIteratorPositions(State, EndSym, BO_GE);
650 State = setContainerData(State, ContReg, CData->newEnd(
nullptr));
654 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
655 Pos2->getOffset(), BO_LT);
657 C.addTransition(State);
662 auto State =
C.getState();
669 auto &SymMgr =
C.getSymbolManager();
670 auto &BVF = SymMgr.getBasicVals();
671 auto &SVB =
C.getSValBuilder();
673 SVB.evalBinOp(State, BO_Add,
676 SymMgr.
getType(Pos->getOffset())).getAsSymbol();
677 State = invalidateIteratorPositions(State, NextSym, BO_EQ);
678 C.addTransition(State);
683 auto State =
C.getState();
690 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
691 Pos2->getOffset(), BO_LT);
692 C.addTransition(State);
698 const Expr *ContE)
const {
701 if (
const auto *DR = dyn_cast<DeclRegion>(ContReg)) {
702 Name = DR->getDecl()->getName();
704 }
else if (
const auto *DRE =
706 Name = DRE->getDecl()->getName();
715 llvm::raw_svector_ostream Out(Msg);
716 Out <<
"Container " << (!Name.empty() ? (
"'" + Name.str() +
"' ") :
"" )
718 return std::string(Out.str());
722void ContainerModeling::printState(raw_ostream &Out,
ProgramStateRef State,
723 const char *NL,
const char *Sep)
const {
726 if (!ContMap.isEmpty()) {
727 Out << Sep <<
"Container Data :" << NL;
728 for (
const auto &Cont : ContMap) {
731 const auto CData = Cont.second;
732 if (CData.getBegin())
738 CData.getEnd()->dumpToStream(Out);
749 const auto *IdInfo =
Func->getIdentifier();
752 return IdInfo->getName().ends_with_insensitive(
"begin");
756 const auto *IdInfo =
Func->getIdentifier();
759 return IdInfo->getName().ends_with_insensitive(
"end");
768 auto Type = TI.getType();
777 const auto *CRD = getCXXRecordDecl(State, Reg);
781 for (
const auto *Method : CRD->methods()) {
782 if (!Method->isOverloadedOperator())
784 const auto OPK = Method->getOverloadedOperator();
785 if (OPK == OO_Subscript) {
793 const auto *CRD = getCXXRecordDecl(State, Reg);
797 for (
const auto *Method : CRD->methods()) {
798 if (!Method->getDeclName().isIdentifier())
800 if (Method->getName() ==
"push_front" || Method->getName() ==
"pop_front") {
808 const auto *CRD = getCXXRecordDecl(State, Reg);
812 for (
const auto *Method : CRD->methods()) {
813 if (!Method->getDeclName().isIdentifier())
815 if (Method->getName() ==
"push_back" || Method->getName() ==
"pop_back") {
827 return CDataPtr->getBegin();
835 return CDataPtr->getEnd();
841 unsigned BlockCount) {
844 if (CDataPtr && CDataPtr->getBegin())
847 auto &SymMgr = State->getSymbolManager();
848 const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
853 const auto CData = CDataPtr->newBegin(Sym);
854 return setContainerData(State, Cont, CData);
858 return setContainerData(State, Cont, CData);
864 unsigned BlockCount) {
867 if (CDataPtr && CDataPtr->getEnd())
870 auto &SymMgr = State->getSymbolManager();
871 const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
876 const auto CData = CDataPtr->newEnd(Sym);
877 return setContainerData(State, Cont, CData);
881 return setContainerData(State, Cont, CData);
889template <
typename Condition,
typename Process>
895 for (
const auto &Reg : RegionMap) {
896 if (Cond(Reg.second)) {
897 RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
908 for (
const auto &Sym : SymbolMap) {
909 if (Cond(Sym.second)) {
910 SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
924 return Pos.getContainer() == Cont;
927 return Pos.invalidate();
929 return processIteratorPositions(State, MatchCont, Invalidate);
937 return Pos.getContainer() == Cont &&
938 !
compare(State, Pos.getOffset(), Offset, Opc);
941 return Pos.invalidate();
943 return processIteratorPositions(State, MatchContAndCompare, Invalidate);
950 return compare(State, Pos.getOffset(), Offset, Opc);
953 return Pos.invalidate();
955 return processIteratorPositions(State, Compare, Invalidate);
964 return compare(State, Pos.getOffset(), Offset1, Opc1) &&
965 compare(State, Pos.getOffset(), Offset2, Opc2);
968 return Pos.invalidate();
970 return processIteratorPositions(State, Compare, Invalidate);
977 return Pos.getContainer() == Cont;
980 return Pos.reAssign(NewCont);
982 return processIteratorPositions(State, MatchCont, ReAssign);
991 return Pos.getContainer() == Cont &&
992 !
compare(State, Pos.getOffset(), Offset, Opc);
995 return Pos.reAssign(NewCont);
997 return processIteratorPositions(State, MatchContAndCompare, ReAssign);
1007 return compare(State, Pos.getOffset(), CondSym, Opc);
1010 return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
1013 return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
1032 SymMgr.
getType(OrigExpr)).getAsSymbol();
1037 for (
const auto &Reg : RegionMap) {
1038 if (Reg.second.getContainer() == Cont)
1043 for (
const auto &Sym : SymbolMap) {
1044 if (Sym.second.getContainer() == Cont)
1057bool ento::shouldRegisterContainerModeling(
const CheckerManager &mgr) {
1063 diag::err_analyzer_checker_incompatible_analyzer_option)
1064 <<
"aggressive-binary-operation-simplification" <<
"false";
Defines the C++ template declaration subclasses.
static bool handleAssignment(EvalInfo &Info, const Expr *E, const LValue &LVal, QualType LValType, APValue &Val)
Perform an assignment of Val to LVal. Takes ownership of Val.
static bool compare(const PathDiagnostic &X, const PathDiagnostic &Y)
DiagnosticsEngine & getDiagnostics() const
Represents a C++ struct/union/class.
DiagnosticBuilder Report(SourceLocation Loc, unsigned DiagID)
Issue the message to the client.
This represents one expression.
Expr * IgnoreParenCasts() LLVM_READONLY
Skip past any parentheses and casts which might surround this expression until reaching a fixed point...
Represents a function declaration or definition.
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
A (possibly-)qualified type.
Base for LValueReferenceType and RValueReferenceType.
The base class of the type hierarchy.
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
QualType getPointeeType() const
If this is a pointer, ObjC object pointer, or block pointer, this returns the respective pointee.
const T * getAs() const
Member-template getAs<specific type>'.
const Type * getUnqualifiedDesugaredType() const
Return the specified type with any "sugar" removed from the type, removing any typedefs,...
An immutable map from CallDescriptions to arbitrary data.
Represents an abstract call to a function or method along a particular path.
virtual void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const
See CheckerManager::runCheckersForPrintState.
const AnalyzerOptions & getAnalyzerOptions() const
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
ASTContext & getASTContext() const
const LangOptions & getLangOpts() const
MemRegion - The root abstract class for all memory regions.
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getMostDerivedObjectRegion() const
Recursively retrieve the region of the most derived class instance of regions of C++ base class insta...
The tag upon which the TagVisitor reacts.
bool isInteresting(SymbolRef sym) const
virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy)=0
Create a new value which represents a binary expression with two non- location operands.
SymbolManager & getSymbolManager()
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
void dumpToStream(raw_ostream &OS) const
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
QualType getType(const ASTContext &) const
Try to get a reasonable type for the given value.
const MemRegion * getAsRegion() const
A symbol representing the result of an expression in the case when we do not know anything about what...
A class responsible for cleaning up unused symbols.
void markLive(SymbolRef sym)
Unconditionally marks a symbol as live.
bool isLiveRegion(const MemRegion *region)
Value representing integer constant.
Represents symbolic expression that isn't a location.
const IteratorPosition * getIteratorPosition(ProgramStateRef State, const SVal &Val)
ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, long Scale)
ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, const IteratorPosition &Pos)
const ContainerData * getContainerData(ProgramStateRef State, const MemRegion *Cont)
DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR)
Get dynamic type information for the region MR.
ComparisonCategoryResult Compare(const T &X, const T &Y)
Helper to compare two comparable types.
static ContainerData fromEnd(SymbolRef E)
static ContainerData fromBegin(SymbolRef B)
static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of)