[analyzer] Invalidate regions indirectly accessible through const pointers.

In this case, the value of 'x' may be changed after the call to indirectAccess:

  struct Wrapper {
    int *ptr;
  };

  void indirectAccess(const Wrapper &w);

  void test() {
    int x = 42;
    Wrapper w = { x };

    clang_analyzer_eval(x == 42); // TRUE
    indirectAccess(w);
    clang_analyzer_eval(x == 42); // UNKNOWN
  }

This is important for modelling return-by-value objects in C++, to show
that the contents of the struct are escaping in the return copy-constructor.

<rdar://problem/13239826>

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177570 91177308-0d34-0410-b5e6-96231b3b80d8

6 files changed, 185 insertions, 75 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
index 39e7429344..fe5325b5d7 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
@@ -240,12 +240,15 @@ public:
   /// \param IS the set of invalidated symbols.
   /// \param Call if non-null, the invalidated regions represent parameters to
   ///        the call and should be considered directly invalidated.
-  ProgramStateRef invalidateRegions(ArrayRef<const MemRegion *> Regions,
-                                    const Expr *E, unsigned BlockCount,
-                                    const LocationContext *LCtx,
-                                    bool CausesPointerEscape,
-                                    InvalidatedSymbols *IS = 0,
-                                    const CallEvent *Call = 0) const;
+  /// \param ConstRegions the set of regions whose contents are accessible,
+  ///        even though the regions themselves should not be invalidated.
+  ProgramStateRef
+  invalidateRegions(ArrayRef<const MemRegion *> Regions, const Expr *E,
+                    unsigned BlockCount, const LocationContext *LCtx,
+                    bool CausesPointerEscape, InvalidatedSymbols *IS = 0,
+                    const CallEvent *Call = 0,
+                    ArrayRef<const MemRegion *> ConstRegions =
+                      ArrayRef<const MemRegion *>()) const;
 
   /// enterStackFrame - Returns the state for entry to the given stack frame,
   ///  preserving the current state.
@@ -415,14 +418,16 @@ public:
 private:
   friend void ProgramStateRetain(const ProgramState *state);
   friend void ProgramStateRelease(const ProgramState *state);
-  
-  ProgramStateRef 
+
+  /// \sa invalidateRegions()
+  ProgramStateRef
   invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions,
                         const Expr *E, unsigned BlockCount,
                         const LocationContext *LCtx,
                         bool ResultsInSymbolEscape,
                         InvalidatedSymbols &IS,
-                        const CallEvent *Call) const;
+                        const CallEvent *Call,
+                        ArrayRef<const MemRegion *> ConstRegions) const;
 };
 
 //===----------------------------------------------------------------------===//
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
index 066cd20e18..8318fe0c26 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
@@ -197,6 +197,7 @@ public:
                                      const LocationContext *LCtx,
                                      InvalidatedSymbols &IS,
                                      const CallEvent *Call,
+                                     ArrayRef<const MemRegion *> ConstRegions,
                                      InvalidatedRegions *Invalidated) = 0;
 
   /// enterStackFrame - Let the StoreManager to do something when execution
diff --git a/lib/StaticAnalyzer/Core/CallEvent.cpp b/lib/StaticAnalyzer/Core/CallEvent.cpp
index d7e1b1253e..78400ba359 100644
--- a/lib/StaticAnalyzer/Core/CallEvent.cpp
+++ b/lib/StaticAnalyzer/Core/CallEvent.cpp
@@ -125,7 +125,7 @@ static bool isPointerToConst(QualType Ty) {
 // Try to retrieve the function declaration and find the function parameter
 // types which are pointers/references to a non-pointer const.
 // We will not invalidate the corresponding argument regions.
-static void findPtrToConstParams(llvm::SmallSet<unsigned, 1> &PreserveArgs,
+static void findPtrToConstParams(llvm::SmallSet<unsigned, 4> &PreserveArgs,
                                  const CallEvent &Call) {
   unsigned Idx = 0;
   for (CallEvent::param_type_iterator I = Call.param_type_begin(),
@@ -137,36 +137,29 @@ static void findPtrToConstParams(llvm::SmallSet<unsigned, 1> &PreserveArgs,
 }
 
 ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount,
-                                              ProgramStateRef Orig) const {
+                                             ProgramStateRef Orig) const {
   ProgramStateRef Result = (Orig ? Orig : getState());
 
+  SmallVector<const MemRegion *, 8> ConstRegions;
   SmallVector<const MemRegion *, 8> RegionsToInvalidate;
   getExtraInvalidatedRegions(RegionsToInvalidate);
 
   // Indexes of arguments whose values will be preserved by the call.
-  llvm::SmallSet<unsigned, 1> PreserveArgs;
+  llvm::SmallSet<unsigned, 4> PreserveArgs;
   if (!argumentsMayEscape())
     findPtrToConstParams(PreserveArgs, *this);
 
   for (unsigned Idx = 0, Count = getNumArgs(); Idx != Count; ++Idx) {
-    if (PreserveArgs.count(Idx))
-      continue;
-
-    SVal V = getArgSVal(Idx);
-
-    // If we are passing a location wrapped as an integer, unwrap it and
-    // invalidate the values referred by the location.
-    if (Optional<nonloc::LocAsInteger> Wrapped =
-            V.getAs<nonloc::LocAsInteger>())
-      V = Wrapped->getLoc();
-    else if (!V.getAs<Loc>())
+    const MemRegion *R = getArgSVal(Idx).getAsRegion();
+    if (!R)
       continue;
 
-    if (const MemRegion *R = V.getAsRegion()) {
-      // Mark this region for invalidation.  We batch invalidate regions
-      // below for efficiency.
+    // Mark this region for invalidation.  We batch invalidate regions
+    // below for efficiency.
+    if (PreserveArgs.count(Idx))
+      ConstRegions.push_back(R);
+    else
       RegionsToInvalidate.push_back(R);
-    }
   }
 
   // Invalidate designated regions using the batch invalidation API.
@@ -175,7 +168,7 @@ ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount,
   return Result->invalidateRegions(RegionsToInvalidate, getOriginExpr(),
                                    BlockCount, getLocationContext(),
                                    /*CausedByPointerEscape*/ true,
-                                   /*Symbols=*/0, this);
+                                   /*Symbols=*/0, this, ConstRegions);
 }
 
 ProgramPoint CallEvent::getProgramPoint(bool IsPreVisit,
diff --git a/lib/StaticAnalyzer/Core/ProgramState.cpp b/lib/StaticAnalyzer/Core/ProgramState.cpp
index 64205f8d99..3e47dcef2b 100644
--- a/lib/StaticAnalyzer/Core/ProgramState.cpp
+++ b/lib/StaticAnalyzer/Core/ProgramState.cpp
@@ -140,30 +140,34 @@ ProgramStateRef ProgramState::bindDefault(SVal loc, SVal V) const {
            new_state;
 }
 
+typedef ArrayRef<const MemRegion *> RegionList;
+
 ProgramStateRef 
-ProgramState::invalidateRegions(ArrayRef<const MemRegion *> Regions,
+ProgramState::invalidateRegions(RegionList Regions,
                                 const Expr *E, unsigned Count,
                                 const LocationContext *LCtx,
                                 bool CausedByPointerEscape,
                                 InvalidatedSymbols *IS,
-                                const CallEvent *Call) const {
+                                const CallEvent *Call,
+                                RegionList ConstRegions) const {
   if (!IS) {
     InvalidatedSymbols invalidated;
     return invalidateRegionsImpl(Regions, E, Count, LCtx,
                                  CausedByPointerEscape,
-                                 invalidated, Call);
+                                 invalidated, Call, ConstRegions);
   }
   return invalidateRegionsImpl(Regions, E, Count, LCtx, CausedByPointerEscape,
-                               *IS, Call);
+                               *IS, Call, ConstRegions);
 }
 
 ProgramStateRef 
-ProgramState::invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions,
+ProgramState::invalidateRegionsImpl(RegionList Regions,
                                     const Expr *E, unsigned Count,
                                     const LocationContext *LCtx,
                                     bool CausedByPointerEscape,
                                     InvalidatedSymbols &IS,
-                                    const CallEvent *Call) const {
+                                    const CallEvent *Call,
+                                    RegionList ConstRegions) const {
   ProgramStateManager &Mgr = getStateManager();
   SubEngine* Eng = Mgr.getOwningEngine();
  
@@ -171,7 +175,7 @@ ProgramState::invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions,
     StoreManager::InvalidatedRegions Invalidated;
     const StoreRef &newStore
       = Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, LCtx, IS,
-                                        Call, &Invalidated);
+                                        Call, ConstRegions, &Invalidated);
 
     ProgramStateRef newState = makeWithStore(newStore);
 
@@ -184,7 +188,7 @@ ProgramState::invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions,
 
   const StoreRef &newStore =
     Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, LCtx, IS,
-                                    Call, NULL);
+                                    Call, ConstRegions, NULL);
   return makeWithStore(newStore);
 }
 
diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp
index 731c3ed8cc..cf7858fd5f 100644
--- a/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ b/lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -370,6 +370,7 @@ public:
                              const LocationContext *LCtx,
                              InvalidatedSymbols &IS,
                              const CallEvent *Call,
+                             ArrayRef<const MemRegion *> ConstRegions,
                              InvalidatedRegions *Invalidated);
 
   bool scanReachableSymbols(Store S, const MemRegion *R,
@@ -595,7 +596,8 @@ template <typename DERIVED>
 class ClusterAnalysis  {
 protected:
   typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap;
-  typedef SmallVector<const MemRegion *, 10> WorkList;
+  typedef llvm::PointerIntPair<const MemRegion *, 1, bool> WorkListElement;
+  typedef SmallVector<WorkListElement, 10> WorkList;
 
   llvm::SmallPtrSet<const ClusterBindings *, 16> Visited;
 
@@ -642,35 +644,35 @@ public:
     }
   }
 
-  bool AddToWorkList(const MemRegion *R, const ClusterBindings *C) {
+  bool AddToWorkList(WorkListElement E, const ClusterBindings *C) {
     if (C && !Visited.insert(C))
       return false;
-    WL.push_back(R);
+    WL.push_back(E);
     return true;
   }
 
-  bool AddToWorkList(const MemRegion *R) {
-    const MemRegion *baseR = R->getBaseRegion();
-    return AddToWorkList(baseR, getCluster(baseR));
+  bool AddToWorkList(const MemRegion *R, bool Flag = false) {
+    const MemRegion *BaseR = R->getBaseRegion();
+    return AddToWorkList(WorkListElement(BaseR, Flag), getCluster(BaseR));
   }
 
   void RunWorkList() {
     while (!WL.empty()) {
-      const MemRegion *baseR = WL.pop_back_val();
+      WorkListElement E = WL.pop_back_val();
+      const MemRegion *BaseR = E.getPointer();
 
-      // First visit the cluster.
-      if (const ClusterBindings *Cluster = getCluster(baseR))
-        static_cast<DERIVED*>(this)->VisitCluster(baseR, *Cluster);
-
-      // Next, visit the base region.
-      static_cast<DERIVED*>(this)->VisitBaseRegion(baseR);
+      static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR),
+                                                E.getInt());
     }
   }
 
-public:
   void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {}
-  void VisitCluster(const MemRegion *baseR, const ClusterBindings &C) {}
-  void VisitBaseRegion(const MemRegion *baseR) {}
+  void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {}
+
+  void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C,
+                    bool Flag) {
+    static_cast<DERIVED*>(this)->VisitCluster(BaseR, C);
+  }
 };
 }
 
@@ -884,10 +886,8 @@ public:
     : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, includeGlobals),
       Ex(ex), Count(count), LCtx(lctx), IS(is), Regions(r) {}
 
-  void VisitCluster(const MemRegion *baseR, const ClusterBindings &C);
-  void VisitBaseRegion(const MemRegion *baseR);
-
-private:
+  void VisitCluster(const MemRegion *baseR, const ClusterBindings *C,
+                    bool Flag);
   void VisitBinding(SVal V);
 };
 }
@@ -917,18 +917,16 @@ void invalidateRegionsWorker::VisitBinding(SVal V) {
   }
 }
 
-void invalidateRegionsWorker::VisitCluster(const MemRegion *BaseR,
-                                           const ClusterBindings &C) {
-  for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I)
-    VisitBinding(I.getData());
+void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
+                                           const ClusterBindings *C,
+                                           bool IsConst) {
+  if (C) {
+    for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
+      VisitBinding(I.getData());
 
-  B = B.remove(BaseR);
-}
-
-void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) {
-  // Symbolic region?  Mark that symbol touched by the invalidation.
-  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
-    IS.insert(SR->getSymbol());
+    if (!IsConst)
+      B = B.remove(baseR);
+  }
 
   // BlockDataRegion?  If so, invalidate captured variables that are passed
   // by reference.
@@ -957,6 +955,13 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) {
     return;
   }
 
+  if (IsConst)
+    return;
+
+  // Symbolic region?  Mark that symbol touched by the invalidation.
+  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
+    IS.insert(SR->getSymbol());
+
   // Otherwise, we have a normal data region. Record that we touched the region.
   if (Regions)
     Regions->push_back(baseR);
@@ -1043,10 +1048,11 @@ RegionStoreManager::invalidateRegions(Store store,
                                       const LocationContext *LCtx,
                                       InvalidatedSymbols &IS,
                                       const CallEvent *Call,
+                                      ArrayRef<const MemRegion *> ConstRegions,
                                       InvalidatedRegions *Invalidated) {
-  invalidateRegionsWorker W(*this, StateMgr,
-                            RegionStoreManager::getRegionBindings(store),
-                            Ex, Count, LCtx, IS, Invalidated, false);
+  RegionBindingsRef B = RegionStoreManager::getRegionBindings(store);
+  invalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS,
+                            Invalidated, false);
 
   // Scan the bindings and generate the clusters.
   W.GenerateClusters();
@@ -1054,12 +1060,18 @@ RegionStoreManager::invalidateRegions(Store store,
   // Add the regions to the worklist.
   for (ArrayRef<const MemRegion *>::iterator
        I = Regions.begin(), E = Regions.end(); I != E; ++I)
-    W.AddToWorkList(*I);
+    W.AddToWorkList(*I, /*IsConst=*/false);
+
+  for (ArrayRef<const MemRegion *>::iterator I = ConstRegions.begin(),
+                                             E = ConstRegions.end();
+       I != E; ++I) {
+    W.AddToWorkList(*I, /*IsConst=*/true);
+  }
 
   W.RunWorkList();
 
   // Return the new bindings.
-  RegionBindingsRef B = W.getRegionBindings();
+  B = W.getRegionBindings();
 
   // For all globals which are not static nor immutable: determine which global
   // regions should be invalidated and invalidate them.
@@ -2051,7 +2063,8 @@ public:
 
   // Called by ClusterAnalysis.
   void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C);
-  void VisitCluster(const MemRegion *baseR, const ClusterBindings &C);
+  void VisitCluster(const MemRegion *baseR, const ClusterBindings *C);
+  using ClusterAnalysis::VisitCluster;
 
   bool UpdatePostponed();
   void VisitBinding(SVal V);
@@ -2094,13 +2107,16 @@ void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,
 }
 
 void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
-                                            const ClusterBindings &C) {
+                                            const ClusterBindings *C) {
+  if (!C)
+    return;
+
   // Mark the symbol for any SymbolicRegion with live bindings as live itself.
   // This means we should continue to track that symbol.
   if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR))
     SymReaper.markLive(SymR->getSymbol());
 
-  for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I)
+  for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
     VisitBinding(I.getData());
 }
 
diff --git a/test/Analysis/call-invalidation.cpp b/test/Analysis/call-invalidation.cpp
new file mode 100644
index 0000000000..54281cc98a
--- /dev/null
+++ b/test/Analysis/call-invalidation.cpp
@@ -0,0 +1,91 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(bool);
+
+void usePointer(int * const *);
+void useReference(int * const &);
+
+void testPointer() {
+  int x;
+  int *p;
+
+  p = &x;
+  x = 42;
+  clang_analyzer_eval(x == 42); // expected-warning{{TRUE}}
+  usePointer(&p);
+  clang_analyzer_eval(x == 42); // expected-warning{{UNKNOWN}}
+
+  p = &x;
+  x = 42;
+  clang_analyzer_eval(x == 42); // expected-warning{{TRUE}}
+  useReference(p);
+  clang_analyzer_eval(x == 42); // expected-warning{{UNKNOWN}}
+
+  int * const cp1 = &x;
+  x = 42;
+  clang_analyzer_eval(x == 42); // expected-warning{{TRUE}}
+  usePointer(&cp1);
+  clang_analyzer_eval(x == 42); // expected-warning{{UNKNOWN}}
+
+  int * const cp2 = &x;
+  x = 42;
+  clang_analyzer_eval(x == 42); // expected-warning{{TRUE}}
+  useReference(cp2);
+  clang_analyzer_eval(x == 42); // expected-warning{{UNKNOWN}}
+}
+
+
+struct Wrapper {
+  int *ptr;
+};
+
+void useStruct(Wrapper &w);
+void useConstStruct(const Wrapper &w);
+
+void testPointerStruct() {
+  int x;
+  Wrapper w;
+
+  w.ptr = &x;
+  x = 42;
+  clang_analyzer_eval(x == 42); // expected-warning{{TRUE}}
+  useStruct(w);
+  clang_analyzer_eval(x == 42); // expected-warning{{UNKNOWN}}
+
+  w.ptr = &x;
+  x = 42;
+  clang_analyzer_eval(x == 42); // expected-warning{{TRUE}}
+  useConstStruct(w);
+  clang_analyzer_eval(x == 42); // expected-warning{{UNKNOWN}}
+}
+
+
+struct RefWrapper {
+  int &ref;
+};
+
+void useStruct(RefWrapper &w);
+void useConstStruct(const RefWrapper &w);
+
+void testReferenceStruct() {
+  int x;
+  RefWrapper w = { x };
+
+  x = 42;
+  clang_analyzer_eval(x == 42); // expected-warning{{TRUE}}
+  useStruct(w);
+  clang_analyzer_eval(x == 42); // expected-warning{{UNKNOWN}}
+}
+
+// FIXME: This test is split into two functions because region invalidation
+// does not preserve reference bindings. <rdar://problem/13320347>
+void testConstReferenceStruct() {
+  int x;
+  RefWrapper w = { x };
+
+  x = 42;
+  clang_analyzer_eval(x == 42); // expected-warning{{TRUE}}
+  useConstStruct(w);
+  clang_analyzer_eval(x == 42); // expected-warning{{UNKNOWN}}
+}
+