StaticAnalyzer/Checkers/IteratorModeling.cpp

93   void processComparison(CheckerContext &C, ProgramStateRef State,
124   void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
136   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
152 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
153 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
154 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
155 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
156 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
157 ProgramStateRef createContainerBegin(ProgramStateRef State,
161 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
165 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
167 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
168 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
170 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
173 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
176 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
179 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
184 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
187 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
193     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
195 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
197 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
199 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
351     auto State = C.getState();
368     if (getIteratorPosition(State, Call.getReturnValue()))
373       if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
374         State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
376           State = removeIteratorPosition(State, Call.getArgSVal(0));
378         C.addTransition(State);
390         if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
402   auto State = C.getState();
403   const auto *Pos = getIteratorPosition(State, Val);
405     State = setIteratorPosition(State, Loc, *Pos);
406     C.addTransition(State);
408     const auto *OldPos = getIteratorPosition(State, Loc);
410       State = removeIteratorPosition(State, Loc);
411       C.addTransition(State);
419   auto State = C.getState();
420   const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));
423   State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
424   C.addTransition(State);
427 void IteratorModeling::checkLiveSymbols(ProgramStateRef State,
431   auto RegionMap = State->get<IteratorRegionMap>();
439   auto SymbolMap = State->get<IteratorSymbolMap>();
447   auto ContMap = State->get<ContainerMap>();
466   auto State = C.getState();
468   auto RegionMap = State->get<IteratorRegionMap>();
474       if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
475         State = State->remove<IteratorRegionMap>(Reg.first);
480   auto SymbolMap = State->get<IteratorSymbolMap>();
483       State = State->remove<IteratorSymbolMap>(Sym.first);
487   auto ContMap = State->get<ContainerMap>();
492       if (!hasLiveIterators(State, Cont.first)) {
493         State = State->remove<ContainerMap>(Cont.first);
498   C.addTransition(State);
509    auto State = C.getState();
510   const auto *LPos = getIteratorPosition(State, LVal);
511   const auto *RPos = getIteratorPosition(State, RVal);
528     State = assumeNoOverflow(State, Sym, 4);
532     State = setIteratorPosition(State, LVal,
534     LPos = getIteratorPosition(State, LVal);
536     State = setIteratorPosition(State, RVal,
538     RPos = getIteratorPosition(State, RVal);
548     State = State->BindExpr(CE, LCtx, RetVal);
551   processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
555                                          ProgramStateRef State, SymbolRef Sym1,
559     if ((State = relateSymbols(State, Sym1, Sym2,
562       C.addTransition(State);
564       C.generateSink(State, C.getPredecessor());
573   if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) {
578   if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
588   auto State = C.getState();
591   const auto *Pos = getIteratorPosition(State, Iter);
596     advancePosition(State, Iter, OO_Plus,
605   State = setIteratorPosition(State, Iter, *NewPos);
606   State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
607   C.addTransition(State);
614   auto State = C.getState();
617   const auto *Pos = getIteratorPosition(State, Iter);
622     advancePosition(State, Iter, OO_Minus,
631   State = setIteratorPosition(State, Iter, *NewPos);
632   State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
633   C.addTransition(State);
644   auto State = C.getState();
646   const auto *Pos = getIteratorPosition(State, LHS);
652     const auto val = State->getRawSVal(*loc);
659     advancePosition(State, LHS, Op, *value);
665     State = setIteratorPosition(NewState, TgtVal, *NewPos);
666     C.addTransition(State);
682   auto State = C.getState();
683   auto BeginSym = getContainerBegin(State, ContReg);
685     State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
687     BeginSym = getContainerBegin(State, ContReg);
689   State = setIteratorPosition(State, RetVal,
691   C.addTransition(State);
704   auto State = C.getState();
705   auto EndSym = getContainerEnd(State, ContReg);
707     State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
709     EndSym = getContainerEnd(State, ContReg);
711   State = setIteratorPosition(State, RetVal,
713   C.addTransition(State);
721   auto State = C.getState();
725   State = assumeNoOverflow(State, Sym, 4);
726   State = setIteratorPosition(State, RetVal,
728   C.addTransition(State);
741   auto State = C.getState();
742   const auto CData = getContainerData(State, ContReg);
744     State = invalidateAllIteratorPositions(State, ContReg);
753       const auto OldCData = getContainerData(State, OldContReg);
760           State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
768           State = assumeNoOverflow(State, NewEndSym, 4);
770             State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
772             State = setContainerData(State, ContReg,
777           State = rebaseSymbolInIteratorPositionsIf(
778               State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
782           State = reassignAllIteratorPositions(State, OldContReg, ContReg);
788             State =
789                 setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
791             State = setContainerData(State, ContReg,
794           State =
795               setContainerData(State, OldContReg, OldCData->newEnd(nullptr));
800         State = reassignAllIteratorPositions(State, OldContReg, ContReg);
804   C.addTransition(State);
816   auto State = C.getState();
817   if (!hasSubscriptOperator(State, ContReg) ||
818       !backModifiable(State, ContReg)) {
819     const auto CData = getContainerData(State, ContReg);
822         State =
823             invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
824         C.addTransition(State);
829   State = invalidateAllIteratorPositions(State, ContReg);
830   C.addTransition(State);
842   auto State = C.getState();
843   if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
844     State = invalidateAllIteratorPositions(State, ContReg);
845     C.addTransition(State);
849   const auto CData = getContainerData(State, ContReg);
855     if (hasSubscriptOperator(State, ContReg)) {
856       State = invalidateIteratorPositions(State, EndSym, BO_GE);
862       SVB.evalBinOp(State, BO_Add,
866     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
868   C.addTransition(State);
879   auto State = C.getState();
880   const auto CData = getContainerData(State, ContReg);
889       SVB.evalBinOp(State, BO_Sub,
896     if (hasSubscriptOperator(State, ContReg) &&
897         backModifiable(State, ContReg)) {
898       State = invalidateIteratorPositions(State, BackSym, BO_GE);
899       State = setContainerData(State, ContReg, CData->newEnd(nullptr));
901       State = invalidateIteratorPositions(State, BackSym, BO_EQ);
904     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
905     C.addTransition(State);
918   auto State = C.getState();
919   if (hasSubscriptOperator(State, ContReg)) {
920     State = invalidateAllIteratorPositions(State, ContReg);
921     C.addTransition(State);
923     const auto CData = getContainerData(State, ContReg);
932         SVB.evalBinOp(State, BO_Sub,
936       State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
937       C.addTransition(State);
950   auto State = C.getState();
951   const auto CData = getContainerData(State, ContReg);
958     if (hasSubscriptOperator(State, ContReg)) {
959       State = invalidateIteratorPositions(State, BeginSym, BO_LE);
961       State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
967       SVB.evalBinOp(State, BO_Add,
971     State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
972     C.addTransition(State);
977   auto State = C.getState();
978   const auto *Pos = getIteratorPosition(State, Iter);
985   if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
986     if (frontModifiable(State, Cont)) {
987       State = invalidateAllIteratorPositions(State, Cont);
989       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
991     if (const auto *CData = getContainerData(State, Cont)) {
993         State = invalidateIteratorPositions(State, EndSym, BO_GE);
994         State = setContainerData(State, Cont, CData->newEnd(nullptr));
997     C.addTransition(State);
1002   auto State = C.getState();
1003   const auto *Pos = getIteratorPosition(State, Iter);
1011   if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1012     if (frontModifiable(State, Cont)) {
1013       State = invalidateAllIteratorPositions(State, Cont);
1015       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
1017     if (const auto *CData = getContainerData(State, Cont)) {
1019         State = invalidateIteratorPositions(State, EndSym, BO_GE);
1020         State = setContainerData(State, Cont, CData->newEnd(nullptr));
1024     State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
1026   C.addTransition(State);
1031   auto State = C.getState();
1032   const auto *Pos1 = getIteratorPosition(State, Iter1);
1033   const auto *Pos2 = getIteratorPosition(State, Iter2);
1042   if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1043     if (frontModifiable(State, Cont)) {
1044       State = invalidateAllIteratorPositions(State, Cont);
1046       State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
1048     if (const auto *CData = getContainerData(State, Cont)) {
1050         State = invalidateIteratorPositions(State, EndSym, BO_GE);
1051         State = setContainerData(State, Cont, CData->newEnd(nullptr));
1055     State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
1058   C.addTransition(State);
1063   auto State = C.getState();
1064   const auto *Pos = getIteratorPosition(State, Iter);
1074     SVB.evalBinOp(State, BO_Add,
1078   State = invalidateIteratorPositions(State, NextSym, BO_EQ);
1079   C.addTransition(State);
1084   auto State = C.getState();
1085   const auto *Pos1 = getIteratorPosition(State, Iter1);
1086   const auto *Pos2 = getIteratorPosition(State, Iter2);
1091   State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
1093   C.addTransition(State);
1096 void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State,
1099   auto ContMap = State->get<ContainerMap>();
1120   auto SymbolMap = State->get<IteratorSymbolMap>();
1121   auto RegionMap = State->get<IteratorRegionMap>();
1150 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1245 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
1246   const auto *CRD = getCXXRecordDecl(State, Reg);
1261 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) {
1262   const auto *CRD = getCXXRecordDecl(State, Reg);
1276 bool backModifiable(ProgramStateRef State, const MemRegion *Reg) {
1277   const auto *CRD = getCXXRecordDecl(State, Reg);
1291 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1293   auto TI = getDynamicTypeInfo(State, Reg);
1305 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
1306   const auto *CDataPtr = getContainerData(State, Cont);
1313 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
1314   const auto *CDataPtr = getContainerData(State, Cont);
1321 ProgramStateRef createContainerBegin(ProgramStateRef State,
1326   const auto *CDataPtr = getContainerData(State, Cont);
1328     return State;
1330   auto &SymMgr = State->getSymbolManager();
1333   State = assumeNoOverflow(State, Sym, 4);
1337     return setContainerData(State, Cont, CData);
1341   return setContainerData(State, Cont, CData);
1344 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
1349   const auto *CDataPtr = getContainerData(State, Cont);
1351     return State;
1353   auto &SymMgr = State->getSymbolManager();
1356   State = assumeNoOverflow(State, Sym, 4);
1360     return setContainerData(State, Cont, CData);
1364   return setContainerData(State, Cont, CData);
1367 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
1369   return State->set<ContainerMap>(Cont, CData);
1372 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
1375     return State->remove<IteratorRegionMap>(Reg);
1377     return State->remove<IteratorSymbolMap>(Sym);
1379     return State->remove<IteratorRegionMap>(LCVal->getRegion());
1391 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
1393   SValBuilder &SVB = State->getStateManager().getSValBuilder();
1400   ProgramStateRef NewState = State;
1404       SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
1409       return State;
1414       SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
1419       return State;
1425 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
1427   auto &SVB = State->getStateManager().getSValBuilder();
1435     SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
1441   auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
1457 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
1458   auto RegionMap = State->get<IteratorRegionMap>();
1464   auto SymbolMap = State->get<IteratorSymbolMap>();
1486 ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
1488   auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
1489   auto RegionMap = State->get<IteratorRegionMap>();
1499     State = State->set<IteratorRegionMap>(RegionMap);
1501   auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
1502   auto SymbolMap = State->get<IteratorSymbolMap>();
1512     State = State->set<IteratorSymbolMap>(SymbolMap);
1514   return State;
1517 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
1525   return processIteratorPositions(State, MatchCont, Invalidate);
1529 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
1534            !compare(State, Pos.getOffset(), Offset, Opc);
1539   return processIteratorPositions(State, MatchContAndCompare, Invalidate);
1542 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
1546     return compare(State, Pos.getOffset(), Offset, Opc);
1551   return processIteratorPositions(State, Compare, Invalidate);
1554 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
1560     return compare(State, Pos.getOffset(), Offset1, Opc1) &&
1561            compare(State, Pos.getOffset(), Offset2, Opc2);
1566   return processIteratorPositions(State, Compare, Invalidate);
1569 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
1578   return processIteratorPositions(State, MatchCont, ReAssign);
1581 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
1588     !compare(State, Pos.getOffset(), Offset, Opc);
1593   return processIteratorPositions(State, MatchContAndCompare, ReAssign);
1600     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
1603     return compare(State, Pos.getOffset(), CondSym, Opc);
1606     return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
1609   return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
1615 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
1619   auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr),
1627   return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),