[Analyzer] Iterator Checker - Part 5: Move Assignment of Containers

[baloghadamsoftware]

Summary

If a container is moved by its move assignment operator, according to the standard all their iterators except the past-end iterators remain valid but refer to the new container. This patch introduces support for this case in the iterator checkers.

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

1619–1641

I do not immediately understand what is this useful for. At least tests don't look like they make use of these offset manipulations(?)

Without full understanding, i wonder: when we overwrite one container with another, why don't we just overwrite all symbols associated with it, instead of creating a mixture of old and new symbols?

Or maybe this is an accidental part of another patch, that has something to do with resizes?

[baloghadamsoftware]

Rebased to current part 4. New tests added. Comments added.

[baloghadamsoftware]

Rebased.

[baloghadamsoftware]

One test failed after rebased to the current master branch. Depending on the internal implementation of the iterator and the move operation of the container it could happen that after moving a container the begin() or end() of the target of the move returns an already existing iterator position to the source of the move which is wrong. Therefore we must first check for begin() and end() and only then check for the existence of the iterator position of the return value of a function returning an iterator.

[baloghadamsoftware]

Rebased to rL335835.

[whisperity]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

1038

( is not closed

[baloghadamsoftware]

In D32859##inline-360206, @NoQ wrote:

I do not immediately understand what is this useful for. At least tests don't look like they make use of these offset manipulations(?)

Without full understanding, i wonder: when we overwrite one container with another, why don't we just overwrite all symbols associated with it, instead of creating a mixture of old and new symbols?

Or maybe this is an accidental part of another patch, that has something to do with resizes?

I do not see which lines exactly you commented but I suppose it is about not reassigning all iterator positions to the new container upon moving. According to [[ C++ Reference | en.cppreference.com/w/cpp/container/vector/operator%3D ]] the past-end iterators are not moved to the new container.

[NoQ]

I think this patch is in good shape.

In D32859#1187551, @baloghadamsoftware wrote:

I do not see which lines exactly you commented

This was about the replaceSymbol() sub. You can traverse history using the History tab, or if there's still a greyed out comment you can push the |<< button on it to jump to the respective historical diff.

In any case, i think in current form replaceSymbol() is much easier to understand, but still deserves a short comment, maybe a small example, maybe a better name (the word "rebase" comes to mind).

[baloghadamsoftware]

Comments added, functions renamed.

[baloghadamsoftware]

) added.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

public:
   static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
     return IteratorPosition(C, true, Of);
   }
 
   IteratorPosition setTo(SymbolRef NewOf) const {
     return IteratorPosition(Cont, Valid, NewOf);
   }
 
+  IteratorPosition reAssign(const MemRegion *NewCont) const {
+    return IteratorPosition(NewCont, Valid, Offset);
+  }
+
   bool operator==(const IteratorPosition &X) const {
     return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset;
   }
 
   bool operator!=(const IteratorPosition &X) const {
     return Cont != X.Cont || Valid != X.Valid || Offset != X.Offset;
   }
 
void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
                               const SVal &RetVal, const SVal &LHS,
                               const SVal &RHS) const;
   void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                    const SVal &Cont) const;
   void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                  const SVal &Cont) const;
   void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                          const MemRegion *Cont) const;
-  void handleAssign(CheckerContext &C, const SVal &Cont) const;
+  void handleAssign(CheckerContext &C, const SVal &Cont,
+                    const Expr *CE = nullptr,
+                    const SVal &OldCont = UndefinedVal()) const;
   void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
                               const SVal &RetVal, const SVal &LHS,
                               const SVal &RHS) const;
   void verifyMatch(CheckerContext &C, const SVal &Iter1,
                    const SVal &Iter2) const;
 
   void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
                            CheckerContext &C, ExplodedNode *ErrNode) const;
ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
                                        RegionOrSymbol RegOrSym,
                                        const IteratorPosition &Pos, bool Equal);
 ProgramStateRef relateIteratorPositions(ProgramStateRef State,
                                         const IteratorPosition &Pos1,
                                         const IteratorPosition &Pos2,
                                         bool Equal);
 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
                                                const MemRegion *Cont);
+ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
+                                             const MemRegion *Cont,
+                                             const MemRegion *NewCont);
+ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
+                                                   const MemRegion *Cont,
+                                                   const MemRegion *NewCont,
+                                                   SymbolRef Offset,
+                                                   BinaryOperator::Opcode Opc);
+ProgramStateRef rebaseSymbolInIteratorPositionsIf(
+    ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
+    SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
 const ContainerData *getContainerData(ProgramStateRef State,
                                       const MemRegion *Cont);
 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
                                  const ContainerData &CData);
 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
 bool isBoundThroughLazyCompoundVal(const Environment &Env,
                                    const MemRegion *Reg);
 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
void IteratorChecker::checkPostCall(const CallEvent &Call,
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)
     return;
 
   if (Func->isOverloadedOperator()) {
     const auto Op = Func->getOverloadedOperator();
     if (isAssignmentOperator(Op)) {
       const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call);
+      if (Func->getParamDecl(0)->getType()->isRValueReferenceType()) {
+        handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
+                     Call.getArgSVal(0));
+      } else {
         handleAssign(C, InstCall->getCXXThisVal());
+      }
     } else if (isSimpleComparisonOperator(Op)) {
       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
         handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
                          Call.getArgSVal(0), Op);
       } else {
         handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
                          Call.getArgSVal(1), Op);
       }
if (Func->isOverloadedOperator()) {
     const auto *OrigExpr = Call.getOriginExpr();
     if (!OrigExpr)
       return;
 
     if (!isIteratorType(Call.getResultType()))
       return;
 
     auto State = C.getState();
-    // Already bound to container?
-    if (getIteratorPosition(State, Call.getReturnValue()))
-      return;
 
     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(),
                   InstCall->getCXXThisVal());
         return;
       }
     }
 
+    // Already bound to container?
+    if (getIteratorPosition(State, Call.getReturnValue()))
+      return;
+
     // Copy-like and move constructors
     if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
       if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
         State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
         if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
           State = removeIteratorPosition(State, Call.getArgSVal(0));
         }
         C.addTransition(State);
void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
   auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
                                   C.getASTContext().LongTy, C.blockCount());
   State = assumeNoOverflow(State, Sym, 4);
   State = setIteratorPosition(State, RetVal,
                               IteratorPosition::getPosition(Cont, Sym));
   C.addTransition(State);
 }
 
-void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont) const {
+void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont,
+                                   const Expr *CE, const SVal &OldCont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
     ContReg = CBOR->getSuperRegion();
   }
 
   // Assignment of a new value to a container always invalidates all its
   // iterators
   auto State = C.getState();
   const auto CData = getContainerData(State, ContReg);
   if (CData) {
     State = invalidateAllIteratorPositions(State, ContReg);
   }
 
+  // In case of move, iterators of the old container (except the past-end
+  // iterators) remain valid but refer to the new container
+  if (!OldCont.isUndef()) {
+    const auto *OldContReg = OldCont.getAsRegion();
+    if (OldContReg) {
+      while (const auto *CBOR = OldContReg->getAs<CXXBaseObjectRegion>()) {
+        OldContReg = CBOR->getSuperRegion();
+      }
+      const auto OldCData = getContainerData(State, OldContReg);
+      if (OldCData) {
+        if (const auto OldEndSym = OldCData->getEnd()) {
+          // If we already assigned an "end" symbol to the old conainer, then
+          // first reassign all iterator positions to the new container which
+          // are not past the container (thus not greater or equal to the
+          // current "end" symbol).
+          State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
+                                                     OldEndSym, BO_GE);
+          auto &SymMgr = C.getSymbolManager();
+          auto &SVB = C.getSValBuilder();
+          // Then generate and assign a new "end" symbol for the new container.
+          auto NewEndSym =
+              SymMgr.conjureSymbol(CE, C.getLocationContext(),
+                                   C.getASTContext().LongTy, C.blockCount());
+          State = assumeNoOverflow(State, NewEndSym, 4);
+          if (CData) {
+            State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
+          } else {
+            State = setContainerData(State, ContReg,
+                                     ContainerData::fromEnd(NewEndSym));
+          }
+          // Finally, replace the old "end" symbol in the already reassigned
+          // iterator positions with the new "end" symbol.
+          State = rebaseSymbolInIteratorPositionsIf(
+              State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
+        } else {
+          // There was no "end" symbol assigned yet to the old container,
+          // so reassign all iterator positions to the new container.
+          State = reassignAllIteratorPositions(State, OldContReg, ContReg);
+        }
+        if (const auto OldBeginSym = OldCData->getBegin()) {
+          // If we already assigned a "begin" symbol to the old container, then
+          // assign it to the new container and remove it from the old one.
+          if (CData) {
+            State =
+                setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
+          } else {
+            State = setContainerData(State, ContReg,
+                                     ContainerData::fromBegin(OldBeginSym));
+          }
+          State =
+              setContainerData(State, OldContReg, OldCData->newEnd(nullptr));
+        }
+      } else {
+        // There was neither "begin" nor "end" symbol assigned yet to the old
+        // container, so reassign all iterator positions to the new container.
+        State = reassignAllIteratorPositions(State, OldContReg, ContReg);
+      }
+    }
+  }
   C.addTransition(State);
 }
 
 void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
                                           const SVal &Val, CheckerContext &C,
                                           ExplodedNode *ErrNode) const {
   auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
   R->markInteresting(Val);

 namespace {
 
 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool isGreaterOrEqual(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);
+SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
+                        SymbolRef OldSym, SymbolRef NewSym);
 
 bool isIteratorType(const QualType &Type) {
   if (Type->isPointerType())
     return true;
 
   const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
   return isIterator(CRD);
 }
auto MatchCont = [&](const IteratorPosition &Pos) {
     return Pos.getContainer() == Cont;
   };
   auto Invalidate = [&](const IteratorPosition &Pos) {
     return Pos.invalidate();
   };
   return processIteratorPositions(State, MatchCont, Invalidate);
 }
 
+ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
+                                             const MemRegion *Cont,
+                                             const MemRegion *NewCont) {
+  auto MatchCont = [&](const IteratorPosition &Pos) {
+    return Pos.getContainer() == Cont;
+  };
+  auto ReAssign = [&](const IteratorPosition &Pos) {
+    return Pos.reAssign(NewCont);
+  };
+  return processIteratorPositions(State, MatchCont, ReAssign);
+}
+
+ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
+                                                   const MemRegion *Cont,
+                                                   const MemRegion *NewCont,
+                                                   SymbolRef Offset,
+                                                   BinaryOperator::Opcode Opc) {
+  auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
+    return Pos.getContainer() == Cont &&
+    !compare(State, Pos.getOffset(), Offset, Opc);
+  };
+  auto ReAssign = [&](const IteratorPosition &Pos) {
+    return Pos.reAssign(NewCont);
+  };
+  return processIteratorPositions(State, MatchContAndCompare, ReAssign);
+}
+
+// This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`,
+// `OldSym - Int` to `NewSym - Int` and  `OldSym` to `NewSym` in any iterator
+// position offsets where `CondSym` is true.
+ProgramStateRef rebaseSymbolInIteratorPositionsIf(
+    ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
+    SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) {
+  auto LessThanEnd = [&](const IteratorPosition &Pos) {
+    return compare(State, Pos.getOffset(), CondSym, Opc);
+  };
+  auto RebaseSymbol = [&](const IteratorPosition &Pos) {
+    return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
+                                   NewSym));
+  };
+  return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
+}
+
+// This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`,
+// `OldExpr - Int` to `NewExpr - Int` and  `OldExpr` to `NewExpr` in expression
+// `OrigExpr`.
+SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
+                       SymbolRef OrigExpr, SymbolRef OldExpr,
+                       SymbolRef NewSym) {
+  auto &SymMgr = SVB.getSymbolManager();
+  auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr),
+                              nonloc::SymbolVal(OldExpr), 
+                              SymMgr.getType(OrigExpr));
+
+  const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>();
+  if (!DiffInt)
+    return OrigExpr;
+
+  return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),
+                         SymMgr.getType(OrigExpr)).getAsSymbol();
+}
+
 bool isZero(ProgramStateRef State, const NonLoc &Val) {
   auto &BVF = State->getBasicVals();
   return compare(State, Val,
                  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
                  BO_EQ);
 }
 
 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
   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();
 
   const auto comparison =
     SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
 
   assert(comparison.getAs<DefinedSVal>() &&
     "Symbol comparison must be a `DefinedSVal`");
 
   return !State->assume(comparison.castAs<DefinedSVal>(), false);
 }
 
 } // namespace
 
 #define REGISTER_CHECKER(name)                                                 \
   void ento::register##name(CheckerManager &Mgr) {                             \
     auto *checker = Mgr.registerChecker<IteratorChecker>();                    \
     checker->ChecksEnabled[IteratorChecker::CK_##name] = true;                 \
     checker->CheckNames[IteratorChecker::CK_##name] =                          \
         Mgr.getCurrentCheckName();                                             \
   }
 
 REGISTER_CHECKER(IteratorRangeChecker)
 REGISTER_CHECKER(MismatchedIteratorChecker)
 REGISTER_CHECKER(InvalidatedIteratorChecker)