Thanks for your comments. They were helpful. Now the interfaces get simplified a lot. Variables and functions are commented well.<br><br>Here I explain the main idea.<br><br>Some struct base is not mutable, e.g., struct s a; a.f = 3; Here the struct base 'a' is not mutable. But some can, e.g., <br>
<br>void foo(struct s* p) {<br> p->f = 3<br>}<br><br>When we getInitialStore(), p is initialized to have value loc::SymbolVal, which I call a symbolic pointer. (Note: here no symbolic region is involved).<br><br>In this patch we try to concretize the struct pointer p. We have several preconditions for this concretization:<br>
- the struct base is a pointer<br> - the pointer is symbolic<br> - the pointer is an lvalue, so that it can be modified.<br><br>When concretizing the struct base pointer, we pass the pointer's location to StoreManager. Therefore the pointer should be an lvalue and has a location. We get this location by calling <br>
GRExprEngine::getBasePtrLoc(). This method only handles a few cases. In other cases, BasePtrLoc is left Undefined intentionally.<br><br>These are the main ideas. Other issues were commented in the patch<br><br><div class="gmail_quote">
On Thu, Dec 11, 2008 at 9:43 AM, Ted Kremenek <span dir="ltr"><<a href="mailto:kremenek@apple.com">kremenek@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d"><br>
On Dec 9, 2008, at 10:58 PM, Zhongxing Xu wrote:<br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
New patch.<br>
- A new method CheckStructBase is taking care of the creation of AnonPointeeRegion.<br>
- A lightweight lvalue evaluation method is used to get the location of the base expr<br>
whose store may be changed.<br>
- AnonPointeeRegion is now identified the the memregion of the pointer pointing to it.<br>
</blockquote>
<br></div>
Nice work! This is definitely going in the right direction! Comments inline:<br>
<br>
Index: include/clang/Analysis/PathSensitive/Store.h<br>
===================================================================<br>
--- include/clang/Analysis/PathSensitive/Store.h (revision 60812)<br>
+++ include/clang/Analysis/PathSensitive/Store.h (working copy)<br>
@@ -86,6 +86,12 @@<br>
/// conversions between arrays and pointers.<br>
virtual SVal ArrayToPointer(SVal Array) = 0;<br>
<br>
+ /// CheckStructBase - StoreManagers can conditionally expand a symbolic<br>
+ /// pointer into a pointer to a struct region.<br>
+ virtual Store CheckStructBase(Store store, SVal BaseV, SVal BaseL, bool NonNull){<br>
+ return store;<br>
+ }<br>
<br>
Please add comments about what this method does. The comment above the method is a little content-free.<br>
<br>
Also please document what are the roles of 'BaseV' and 'BaseL'. As you will see in my later comments, there roles aren't really all that clear to me, and I wonder if we can make this interface even simpler.<br>
<br>
Moreover, why do we need the parameter 'NonNull'? Why not just have GRExprEngine check if that value is false and then not call this method in the first place. In other words, in the case where the pointer is null, GRExprEngine knows that the StoreManager isn't going to do anything. This also simplifies the implementation (and interface) for StoreManager.<br>
<br>
Finally, the name 'CheckStructBase' doesn't really mean anything to me.<br>
<br>
<br>
Index: include/clang/Analysis/PathSensitive/GRExprEngine.h<br>
===================================================================<br>
--- include/clang/Analysis/PathSensitive/GRExprEngine.h (revision 60812)<br>
+++ include/clang/Analysis/PathSensitive/GRExprEngine.h (working copy)<br>
@@ -505,6 +505,9 @@<br>
/// a DeclRefExpr, it evaluates to the MemRegionVal which represents its<br>
/// storage location. Note that not all kinds of expressions has lvalue.<br>
void VisitLValue(Expr* Ex, NodeTy* Pred, NodeSet& Dst);<br>
+<br>
+ /// getLValue - A lightweight lvalue evaluation method.<br>
+ SVal getLValue(const GRState* St, Expr* Ex);<br>
<br>
The purpose of this method is not really clear from the comment. Please elaborate. Moreover, it appears to only have one caller.<br>
<br>
Index: include/clang/Analysis/PathSensitive/MemRegion.h<br>
===================================================================<br>
--- include/clang/Analysis/PathSensitive/MemRegion.h (revision 60812)<br>
+++ include/clang/Analysis/PathSensitive/MemRegion.h (working copy)<br>
@@ -237,20 +237,20 @@<br>
/// parameters or pointer globals. In RegionStoreManager, we assume pointer<br>
/// parameters or globals point at some anonymous region. Such regions are not<br>
/// the regions associated with the pointer variables themselves. They are<br>
-/// identified with the VarDecl of the pointer variable. We create them lazily.<br>
+/// identified with the MemRegion of the pointer. We create them lazily.<br>
<br>
class AnonPointeeRegion : public TypedRegion {<br>
friend class MemRegionManager;<br>
// VD - the pointer variable that points at this region.<br>
- const VarDecl* Pointer;<br>
+ const TypedRegion* Pointer;<br>
<br>
<br>
All the AnonPointeeRegion stuff looks great! You can probably just commit that stuff as a separate patch since it naturally subsumes the current logic.<br>
<br>
<br>
Index: lib/Analysis/RegionStore.cpp<br>
===================================================================<br>
--- lib/Analysis/RegionStore.cpp (revision 60812)<br>
+++ lib/Analysis/RegionStore.cpp (working copy)<br>
@@ -101,6 +101,8 @@<br>
<br>
SVal ArrayToPointer(SVal Array);<br>
<br>
+ Store CheckStructBase(Store store, SVal BaseV, SVal BaseL, bool NonNull);<br>
+<br>
<br>
Please put a comment here as well. Again, what is the purpose of 'NonNull'. I don't think it's needed.<br>
<br>
<br>
<br>
<br>
+Store RegionStoreManager::CheckStructBase(Store store, SVal BaseV, SVal BaseL,<br>
+ bool NonNull) {<br>
+ // Expand the symbolic pointer only when it can be NonNull.<br>
+ if (isa<loc::SymbolVal>(BaseV) && NonNull) {<br>
+ // Get the location that points to the struct.<br>
+ loc::MemRegionVal& RV = cast<loc::MemRegionVal>(BaseL);<br>
+<br>
+ // Create an AnonPointeeRegion for it.<br>
+ AnonPointeeRegion* APR =<br>
+ MRMgr.getAnonPointeeRegion(cast<TypedRegion>(RV.getRegion()));<br>
+<br>
+ // Symbolize the struct region.<br>
+ store = BindStructToSymVal(store, APR);<br>
+<br>
+ // Update the base pointer.<br>
+ store = Bind(store, RV, Loc::MakeVal(APR));<br>
+ }<br>
<br>
Shouldn't BaseV always be symbolic? (i.e., an assertion, not an 'if').<br>
<br>
NonNull isn't needed. We can simplify the interface and make it assumed.<br>
<br>
Does this handle the case where a symbolic pointer to a struct has already had a region lazily created for it?<br>
<br>
I'm also confused about the difference between BaseL and BaseV. Don't we need just one? It seems like the basic interface is that we pass in a SymbolicRegion. No SVals at all. The interface then gets simpler and more obvious.<br>
<br>
Please document what CheckStructBase is, say its pre- and post- conditions (i.e., its interface), etc.<br>
<br>
<br>
SVal RegionStoreManager::Retrieve(const GRState* state, Loc L, QualType T) {<br>
assert(!isa<UnknownVal>(L) && "location unknown");<br>
assert(!isa<UndefinedVal>(L) && "location undefined");<br>
Index: lib/Analysis/GRExprEngine.cpp<br>
===================================================================<br>
--- lib/Analysis/GRExprEngine.cpp (revision 60812)<br>
+++ lib/Analysis/GRExprEngine.cpp (working copy)<br>
@@ -425,6 +425,28 @@<br>
}<br>
}<br>
<br>
+SVal GRExprEngine::getLValue(const GRState* St, Expr* Ex) {<br>
+ switch (Ex->getStmtClass()) {<br>
+ case Stmt::DeclRefExprClass: {<br>
+ const VarDecl* VD = cast<VarDecl>(cast<DeclRefExpr>(Ex)->getDecl());<br>
+ return StateMgr.GetLValue(St, VD);<br>
+ }<br>
+<br>
+ case Stmt::UnaryOperatorClass: {<br>
+ UnaryOperator* U = cast<UnaryOperator>(Ex);<br>
+ if (U->getOpcode() == UnaryOperator::Deref) {<br>
+ // The lvalue of *x is the rvalue of x, and it should be already evaluated.<br>
+ return GetSVal(St, U->getSubExpr());<br>
+ } else<br>
+ return UndefinedVal();<br>
+ }<br>
+<br>
+ default:<br>
+ assert(0 && "Unhandled Stmt class.");<br>
+ return UndefinedVal();<br>
+ }<br>
+}<br>
<br>
Please add some comments to 'getLValue'. Please clarifiy what purpose it serves (and for whom?). Since that name is so clase to GRStateManager::getLValue(), its worth having more comments (since it does something a little different). I'm not certain what it's role is compared to VisitLValue.<br>
<br>
void GRExprEngine::VisitLValue(Expr* Ex, NodeTy* Pred, NodeSet& Dst) {<br>
<br>
Ex = Ex->IgnoreParens();<br>
@@ -935,6 +957,29 @@<br>
// FIXME: Should we insert some assumption logic in here to determine<br>
// if "Base" is a valid piece of memory? Before we put this assumption<br>
// later when using FieldOffset lvals (which we no longer have).<br>
<br>
Please add comments saying what this code is doing.<br>
<br>
+<br>
+ // Some kinds of struct base are mutable. Get base expr's location.<br>
+ SVal BaseL;<br>
+<br>
+ if (M->isArrow()) {<br>
+ BaseL = getLValue(St, Base);<br>
+ } else {<br>
+ Expr* TmpEx = Base->IgnoreParens();<br>
+ // Check if the base expr is of (*p) pattern.<br>
+ if (UnaryOperator* U = dyn_cast<UnaryOperator>(TmpEx)) {<br>
+ assert(U->getOpcode() == UnaryOperator::Deref);<br>
+ BaseL = getLValue(St, U->getSubExpr());<br>
+ }<br>
<br>
This peeking at the syntax of the subexpression doesn't look all that clean, but partially because I don't understand the role of BaseL and BaseV. Couldn't the subexpression really be anything that returns an "lvalue"? For example, what about:<br>
<br>
foo().f<br>
[myobject foo].f<br>
<br>
I'm all about handling such things (e.g., the subexpression) with utility/recursive functions so we don't have to insert such grimy special cases into the main logic of the clients.<br>
<br>
There also appears to be cases here where 'BaseL' is never assigned a value and left in the 'UnknownVal' state. Is that intentional? If so, please comment.<br>
<br>
+ }<br>
+<br>
+ SVal BaseV = GetSVal(St, Base);<br>
<br>
What is the difference between BaseL and BaseV? This is a little confusing.<br>
<br>
+<br>
+ // Check if the base can be NonNull.<br>
+ bool isFeasibleNotNull = false;<br>
+ St = Assume(St, BaseV, true, isFeasibleNotNull);<br>
+<br>
+ St = StateMgr.CheckStructBase(St, BaseV, BaseL, Base, isFeasibleNotNull);<br>
+<br>
<br>
We should handle the two cases where 'BaseV' can be either null or not-null. If 'BaseV' can be null, what do we want to return as the value of this expression? For example, what does '&(x->f)' evaluate to when 'x' is null? Do we want to emit an error at this point (and stop) or do we want to compute the address of 0x0+offsetof(f).<br>
<br>
</blockquote></div><br>