////////////////////////////////////////////////
protected void addReferenceEdge( OwnershipNode referencer,
HeapRegionNode referencee,
- ReferenceEdgeProperties rep ) {
+ ReferenceEdge edge ) {
assert referencer != null;
assert referencee != null;
- assert rep != null;
- referencer.addReferencedRegion( referencee, rep );
- referencee.addReferencer( referencer );
- rep.setSrc( referencer );
- rep.setDst( referencee );
+ assert edge != null;
+ assert edge.getSrc() == referencer;
+ assert edge.getDst() == referencee;
+
+ referencer.addReferencee( edge );
+ referencee.addReferencer( edge );
}
- protected void removeReferenceEdge( OwnershipNode referencer,
- HeapRegionNode referencee ) {
+ protected void removeReferenceEdge( OwnershipNode referencer,
+ HeapRegionNode referencee,
+ FieldDescriptor fieldDesc ) {
assert referencer != null;
assert referencee != null;
- assert referencer.getReferenceTo( referencee ) != null;
- assert referencee.isReferencedBy( referencer );
+
+ ReferenceEdge edge = referencer.getReferenceTo( referencee,
+ fieldDesc );
+ assert edge != null;
+ assert edge == referencee.getReferenceFrom( referencer,
+ fieldDesc );
- referencer.removeReferencedRegion( referencee );
- referencee.removeReferencer( referencer );
+ referencer.removeReferencee( edge );
+ referencee.removeReferencer( edge );
}
- protected void clearReferenceEdgesFrom( OwnershipNode referencer ) {
+ protected void clearReferenceEdgesFrom( OwnershipNode referencer,
+ FieldDescriptor fieldDesc,
+ boolean removeAll ) {
assert referencer != null;
- // get a copy of the table to iterate over, otherwise
- // we will be trying to take apart the table as we
+ // get a copy of the set to iterate over, otherwise
+ // we will be trying to take apart the set as we
// are iterating over it, which won't work
- Iterator i = referencer.setIteratorToReferencedRegionsClone();
+ Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
while( i.hasNext() ) {
- Map.Entry me = (Map.Entry) i.next();
- HeapRegionNode referencee = (HeapRegionNode) me.getKey();
- removeReferenceEdge( referencer, referencee );
+ ReferenceEdge edge = i.next();
+
+ if( removeAll || edge.getFieldDesc() == fieldDesc ) {
+ HeapRegionNode referencee = edge.getDst();
+ removeReferenceEdge( referencer,
+ referencee,
+ edge.getFieldDesc() );
+ }
}
}
- protected void clearReferenceEdgesTo( HeapRegionNode referencee ) {
+ protected void clearReferenceEdgesTo( HeapRegionNode referencee,
+ FieldDescriptor fieldDesc,
+ boolean removeAll ) {
assert referencee != null;
- // get a copy of the table to iterate over, otherwise
- // we will be trying to take apart the table as we
+ // get a copy of the set to iterate over, otherwise
+ // we will be trying to take apart the set as we
// are iterating over it, which won't work
- Iterator i = referencee.iteratorToReferencersClone();
+ Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
while( i.hasNext() ) {
- OwnershipNode referencer = (OwnershipNode) i.next();
- removeReferenceEdge( referencer, referencee );
- }
+ ReferenceEdge edge = i.next();
+
+ if( removeAll || edge.getFieldDesc() == fieldDesc ) {
+ OwnershipNode referencer = edge.getSrc();
+ removeReferenceEdge( referencer,
+ referencee,
+ edge.getFieldDesc() );
+ }
+ }
}
+ /*
protected void propagateTokensOverNodes( HeapRegionNode nPrime,
ChangeTupleSet c0,
HashSet<HeapRegionNode> nodesWithNewAlpha,
}
}
}
+ */
////////////////////////////////////////////////////
// of the nodes and edges involved.
//
////////////////////////////////////////////////////
- public void assignTempToTemp( TempDescriptor src,
- TempDescriptor dst ) {
- LabelNode srcln = getLabelNodeFromTemp( src );
- LabelNode dstln = getLabelNodeFromTemp( dst );
-
- clearReferenceEdgesFrom( dstln );
-
- HeapRegionNode newReferencee = null;
- Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
- while( srcRegionsItr.hasNext() ) {
- Map.Entry me = (Map.Entry) srcRegionsItr.next();
- newReferencee = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
+ public void assignTempXToTempY( TempDescriptor x,
+ TempDescriptor y ) {
- addReferenceEdge( dstln, newReferencee, rep.copy() );
- }
- }
+ LabelNode lnX = getLabelNodeFromTemp( x );
+ LabelNode lnY = getLabelNodeFromTemp( y );
- public void assignTempToField( TempDescriptor src,
- TempDescriptor dst,
- FieldDescriptor fd ) {
- LabelNode srcln = getLabelNodeFromTemp( src );
- LabelNode dstln = getLabelNodeFromTemp( dst );
-
- clearReferenceEdgesFrom( dstln );
-
- HeapRegionNode hrn = null;
- Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
- while( srcRegionsItr.hasNext() ) {
- Map.Entry me = (Map.Entry) srcRegionsItr.next();
- hrn = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties rep1 = (ReferenceEdgeProperties) me.getValue();
- ReachabilitySet beta1 = rep1.getBeta();
-
- HeapRegionNode hrnOneHop = null;
- Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions();
- while( hrnRegionsItr.hasNext() ) {
- Map.Entry meH = (Map.Entry) hrnRegionsItr.next();
- hrnOneHop = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties rep2 = (ReferenceEdgeProperties) meH.getValue();
- ReachabilitySet beta2 = rep2.getBeta();
-
- ReferenceEdgeProperties rep =
- new ReferenceEdgeProperties( null,
- false,
- beta1.intersection( beta2 ) );
-
- addReferenceEdge( dstln, hrnOneHop, rep );
- }
+ clearReferenceEdgesFrom( lnX, null, true );
+
+ Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
+ while( itrYhrn.hasNext() ) {
+ ReferenceEdge edgeY = itrYhrn.next();
+ HeapRegionNode referencee = edgeY.getDst();
+ ReferenceEdge edgeNew = edgeY.copy();
+ edgeNew.setSrc( lnX );
+
+ addReferenceEdge( lnX, referencee, edgeNew );
}
}
+ public void assignTempXToTempYFieldF( TempDescriptor x,
+ TempDescriptor y,
+ FieldDescriptor f ) {
+ LabelNode lnX = getLabelNodeFromTemp( x );
+ LabelNode lnY = getLabelNodeFromTemp( y );
+ clearReferenceEdgesFrom( lnX, null, true );
- static int x = 0;
+ Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
+ while( itrYhrn.hasNext() ) {
+ ReferenceEdge edgeY = itrYhrn.next();
+ HeapRegionNode hrnY = edgeY.getDst();
+ ReachabilitySet betaY = edgeY.getBeta();
- public void assignFieldToTemp( TempDescriptor src,
- TempDescriptor dst,
- FieldDescriptor fd ) {
+ Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
+ while( itrHrnFhrn.hasNext() ) {
+ ReferenceEdge edgeHrn = itrHrnFhrn.next();
+ HeapRegionNode hrnHrn = edgeHrn.getDst();
+ ReachabilitySet betaHrn = edgeHrn.getBeta();
- // I think my use of src and dst are actually backwards in this method!
- // acccording to the Reachability Notes, think of dst at N and src as N prime
+ if( edgeHrn.getFieldDesc() == null ||
+ edgeHrn.getFieldDesc() == f ) {
- LabelNode srcln = getLabelNodeFromTemp( src );
- LabelNode dstln = getLabelNodeFromTemp( dst );
+ ReferenceEdge edgeNew = new ReferenceEdge( lnX,
+ hrnHrn,
+ f,
+ false,
+ betaY.intersection( betaHrn ) );
+
+ addReferenceEdge( lnX, hrnHrn, edgeNew );
+ }
+ }
+ }
+ }
- HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
- HashSet<ReferenceEdgeProperties> edgesWithNewBeta = new HashSet<ReferenceEdgeProperties>();
- HeapRegionNode hrn = null;
- ReferenceEdgeProperties rep = null;
- Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions();
- while( dstRegionsItr.hasNext() ) {
- Map.Entry me = (Map.Entry) dstRegionsItr.next();
- hrn = (HeapRegionNode) me.getKey();
- rep = (ReferenceEdgeProperties) me.getValue();
-
- ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() );
-
- HeapRegionNode hrnSrc = null;
- ReferenceEdgeProperties repSrc = null;
- Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
- while( srcRegionsItr.hasNext() ) {
- Map.Entry meS = (Map.Entry) srcRegionsItr.next();
- hrnSrc = (HeapRegionNode) meS.getKey();
- repSrc = (ReferenceEdgeProperties) meS.getValue();
-
- ReachabilitySet O = repSrc.getBeta();
+ public void assignTempXFieldFToTempY( TempDescriptor x,
+ FieldDescriptor f,
+ TempDescriptor y ) {
+ LabelNode lnX = getLabelNodeFromTemp( x );
+ LabelNode lnY = getLabelNodeFromTemp( y );
- x++;
- System.out.println( "x is "+x );
- if( x > 0 ) {
- String s = String.format( "debug%04d", x );
- try {
- writeGraph( s, true, true, true, false );
- } catch( Exception e ) {}
- }
+ /*
+ HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
+ HashSet<ReferenceEdgeProperties> edgesWithNewBeta = new HashSet<ReferenceEdgeProperties>();
+ */
+
+ Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
+ while( itrXhrn.hasNext() ) {
+ ReferenceEdge edgeX = itrXhrn.next();
+ HeapRegionNode hrnX = edgeX.getDst();
+ ReachabilitySet betaX = edgeX.getBeta();
+ //ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() );
- System.out.println( " O is "+O );
+ Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
+ while( itrYhrn.hasNext() ) {
+ ReferenceEdge edgeY = itrYhrn.next();
+ HeapRegionNode hrnY = edgeY.getDst();
+ ReachabilitySet betaY = edgeY.getBeta();
+
+ //ReachabilitySet O = repSrc.getBeta();
+ /*
// propagate tokens over nodes starting from hrnSrc, and it will
// take care of propagating back up edges from any touched nodes
ChangeTupleSet Cy = O.unionUpArityToChangeSet( R );
edgesWithNewBeta );
System.out.println( " Onew = "+repSrc.getBetaNew() );
+ */
+
+ // finally, create the actual reference edge hrnX.f -> hrnY
+ ReferenceEdge edgeNew = new ReferenceEdge( hrnX,
+ hrnY,
+ f,
+ false,
+ null );
- // finally, create the actual reference edge hrn->hrnSrc
- ReferenceEdgeProperties repNew
- = new ReferenceEdgeProperties( fd,
- false,
- repSrc.getBetaNew().pruneBy( hrn.getAlpha() )
- );
+ /*
+ repSrc.getBetaNew().pruneBy( hrn.getAlpha()
+ */
- addReferenceEdge( hrn, hrnSrc, repNew );
+ addReferenceEdge( hrnX, hrnY, edgeNew );
}
}
+ /*
Iterator nodeItr = nodesWithNewAlpha.iterator();
while( nodeItr.hasNext() ) {
((HeapRegionNode) nodeItr.next()).applyAlphaNew();
while( edgeItr.hasNext() ) {
((ReferenceEdgeProperties) edgeItr.next()).applyBetaNew();
}
+ */
}
+
public void assignTempToParameterAllocation( boolean isTask,
TempDescriptor td,
Integer paramIndex ) {
// and have a reference to themselves, because we can't know the
// structure of memory that is passed into the method. We're assuming
// the worst here.
- addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( null, false, beta ) );
- addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( null, true, beta ) );
+
+ ReferenceEdge edgeFromLabel =
+ new ReferenceEdge( lnParam, hrn, null, false, beta );
+
+ ReferenceEdge edgeReflexive =
+ new ReferenceEdge( hrn, hrn, null, true, beta );
+
+ addReferenceEdge( lnParam, hrn, edgeFromLabel );
+ addReferenceEdge( hrn, hrn, edgeReflexive );
}
+
- public void assignTempToNewAllocation( TempDescriptor td,
- AllocationSite as ) {
- assert td != null;
+ public void assignTempXToNewAllocation( TempDescriptor x,
+ AllocationSite as ) {
+ assert x != null;
assert as != null;
- age( as );
-
+ //age( as );
// after the age operation the newest (or zero-ith oldest)
// node associated with the allocation site should have
// no references to it as if it were a newly allocated
// heap region, so make a reference to it to complete
// this operation
+
+ /*
Integer idNewest = as.getIthOldest( 0 );
HeapRegionNode hrnNewest = id2hrn.get( idNewest );
assert hrnNewest != null;
- LabelNode dst = getLabelNodeFromTemp( td );
-
- clearReferenceEdgesFrom( dst );
+ LabelNode lnX = getLabelNodeFromTemp( x );
+ clearReferenceEdgesFrom( lnX, null, true );
+
+ ReferenceEdge edgeNew =
+ new ReferenceEdge( lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
- addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( null, false, hrnNewest.getAlpha() ) );
+ addReferenceEdge( lnX, hrnNewest, edgeNew );
+ */
}
+ /*
+
+
// use the allocation site (unique to entire analysis) to
// locate the heap region nodes in this ownership graph
// that should be aged. The process models the allocation
assert hrn0 != null;
// clear all references in and out of newest node
- clearReferenceEdgesFrom( hrn0 );
- clearReferenceEdgesTo ( hrn0 );
+ clearReferenceEdgesFrom( hrn0, null, true );
+ clearReferenceEdgesTo ( hrn0, null, true );
// now tokens in reachability sets need to "age" also
).makeCanonical()
);
}
-
+
protected HeapRegionNode getSummaryNode( AllocationSite as ) {
// replace hrnB reachability with hrnA's
hrnB.setAlpha( hrnA.getAlpha() );
}
-
+ */
protected void ageTokens( AllocationSite as, ReferenceEdgeProperties rep ) {
rep.setBeta( rep.getBeta().ageTokens( as ) );
*/
}
-
+ /*
private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
Integer idCallee,
FlatCall fc,
return possibleCallerHRNs;
}
-
+ */
////////////////////////////////////////////////////
}
protected void mergeReferenceEdges( OwnershipGraph og ) {
- // there is a data structure for storing label nodes
- // retireved by temp descriptors, and a data structure
- // for stroing heap region nodes retrieved by integer
- // ids. Because finding edges requires interacting
- // with these disparate data structures frequently the
- // process is nearly duplicated, one for each structure
- // that stores edges
// heap regions
Set sA = og.id2hrn.entrySet();
Integer idA = (Integer) meA.getKey();
HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
- HeapRegionNode hrnChildA = null;
- Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
+ Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
while( heapRegionsItrA.hasNext() ) {
- Map.Entry me = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
-
- Integer idChildA = hrnChildA.getID();
+ ReferenceEdge edgeA = heapRegionsItrA.next();
+ HeapRegionNode hrnChildA = edgeA.getDst();
+ Integer idChildA = hrnChildA.getID();
// at this point we know an edge in graph A exists
// idA -> idChildA, does this exist in B?
- boolean edgeFound = false;
assert id2hrn.containsKey( idA );
- HeapRegionNode hrnB = id2hrn.get( idA );
+ HeapRegionNode hrnB = id2hrn.get( idA );
+ ReferenceEdge edgeToMerge = null;
- HeapRegionNode hrnChildB = null;
- ReferenceEdgeProperties repB = null;
- Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) meC.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
+ Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
+ while( heapRegionsItrB.hasNext() &&
+ edgeToMerge == null ) {
- if( hrnChildB.equals( idChildA ) ) {
- edgeFound = true;
- repB = rep;
+ ReferenceEdge edgeB = heapRegionsItrB.next();
+ HeapRegionNode hrnChildB = edgeB.getDst();
+
+ // don't use the ReferenceEdge.equals() here because
+ // we're talking about existence between graphs
+ if( hrnChildB.equals( idChildA ) &&
+ edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
+ edgeToMerge = edgeB;
}
}
// if the edge from A was not found in B,
// add it to B.
- if( !edgeFound ) {
+ if( edgeToMerge == null ) {
assert id2hrn.containsKey( idChildA );
- hrnChildB = id2hrn.get( idChildA );
- repB = repA.copy();
- addReferenceEdge( hrnB, hrnChildB, repB );
+ HeapRegionNode hrnChildB = id2hrn.get( idChildA );
+ edgeToMerge = edgeA.copy();
+ edgeToMerge.setSrc( hrnB );
+ edgeToMerge.setDst( hrnChildB );
+ addReferenceEdge( hrnB, hrnChildB, edgeToMerge );
}
// otherwise, the edge already existed in both graphs
// so merge their reachability sets
else {
// just replace this beta set with the union
- assert repB != null;
- repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
+ assert edgeToMerge != null;
+ edgeToMerge.setBeta(
+ edgeToMerge.getBeta().union( edgeA.getBeta() )
+ );
+ if( !edgeA.isInitialParamReflexive() ) {
+ edgeToMerge.setIsInitialParamReflexive( false );
+ }
}
}
}
TempDescriptor tdA = (TempDescriptor) meA.getKey();
LabelNode lnA = (LabelNode) meA.getValue();
- HeapRegionNode hrnChildA = null;
- Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
+ Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
while( heapRegionsItrA.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
-
- Integer idChildA = hrnChildA.getID();
+ ReferenceEdge edgeA = heapRegionsItrA.next();
+ HeapRegionNode hrnChildA = edgeA.getDst();
+ Integer idChildA = hrnChildA.getID();
// at this point we know an edge in graph A exists
// tdA -> idChildA, does this exist in B?
- boolean edgeFound = false;
assert td2ln.containsKey( tdA );
- LabelNode lnB = td2ln.get( tdA );
+ LabelNode lnB = td2ln.get( tdA );
+ ReferenceEdge edgeToMerge = null;
- HeapRegionNode hrnChildB = null;
- ReferenceEdgeProperties repB = null;
- Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) meC.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
+ Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
+ while( heapRegionsItrB.hasNext() &&
+ edgeToMerge == null ) {
- if( hrnChildB.equals( idChildA ) ) {
- edgeFound = true;
- repB = rep;
+ ReferenceEdge edgeB = heapRegionsItrB.next();
+ HeapRegionNode hrnChildB = edgeB.getDst();
+
+ // don't use the ReferenceEdge.equals() here because
+ // we're talking about existence between graphs
+ if( hrnChildB.equals( idChildA ) &&
+ edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
+ edgeToMerge = edgeB;
}
}
// if the edge from A was not found in B,
// add it to B.
- if( !edgeFound ) {
+ if( edgeToMerge == null ) {
assert id2hrn.containsKey( idChildA );
- hrnChildB = id2hrn.get( idChildA );
- repB = repA.copy();
- addReferenceEdge( lnB, hrnChildB, repB );
+ HeapRegionNode hrnChildB = id2hrn.get( idChildA );
+ edgeToMerge = edgeA.copy();
+ edgeToMerge.setSrc( lnB );
+ edgeToMerge.setDst( hrnChildB );
+ addReferenceEdge( lnB, hrnChildB, edgeToMerge );
}
// otherwise, the edge already existed in both graphs
- // so merge the reachability sets
+ // so merge their reachability sets
else {
// just replace this beta set with the union
- assert repB != null;
- repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
+ assert edgeToMerge != null;
+ edgeToMerge.setBeta(
+ edgeToMerge.getBeta().union( edgeA.getBeta() )
+ );
+ if( !edgeA.isInitialParamReflexive() ) {
+ edgeToMerge.setIsInitialParamReflexive( false );
+ }
}
}
}
return false;
}
- if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
- return false;
- }
-
if( !areLabelNodesEqual( og ) ) {
return false;
}
- if( !areLabelToHeapRegionEdgesEqual( og ) ) {
+ if( !areReferenceEdgesEqual( og ) ) {
return false;
}
return true;
}
- protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
- // check all nodes in A for presence in graph B
- Set sA = og.id2hrn.entrySet();
+ protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
+
+ if( !areallHRNinAalsoinBandequal( this, og ) ) {
+ return false;
+ }
+
+ if( !areallHRNinAalsoinBandequal( og, this ) ) {
+ return false;
+ }
+
+ return true;
+ }
+
+ static protected boolean areallHRNinAalsoinBandequal( OwnershipGraph ogA,
+ OwnershipGraph ogB ) {
+ Set sA = ogA.id2hrn.entrySet();
Iterator iA = sA.iterator();
while( iA.hasNext() ) {
Map.Entry meA = (Map.Entry) iA.next();
Integer idA = (Integer) meA.getKey();
HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
- if( !id2hrn.containsKey( idA ) ) {
+ if( !ogB.id2hrn.containsKey( idA ) ) {
return false;
}
- //HeapRegionNode hrnB = og.id2hrn.get( idA );
- HeapRegionNode hrnB = id2hrn.get( idA );
+ HeapRegionNode hrnB = ogB.id2hrn.get( idA );
if( !hrnA.equals( hrnB ) ) {
return false;
}
- }
+ }
+
+ return true;
+ }
- // then check all nodes in B verses graph A
- Set sB = id2hrn.entrySet();
- Iterator iB = sB.iterator();
- while( iB.hasNext() ) {
- Map.Entry meB = (Map.Entry) iB.next();
- Integer idB = (Integer) meB.getKey();
- HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
- if( !og.id2hrn.containsKey( idB ) ) {
+ protected boolean areLabelNodesEqual( OwnershipGraph og ) {
+
+ if( !areallLNinAalsoinBandequal( this, og ) ) {
+ return false;
+ }
+
+ if( !areallLNinAalsoinBandequal( og, this ) ) {
+ return false;
+ }
+
+ return true;
+ }
+
+ static protected boolean areallLNinAalsoinBandequal( OwnershipGraph ogA,
+ OwnershipGraph ogB ) {
+ Set sA = ogA.td2ln.entrySet();
+ Iterator iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ TempDescriptor tdA = (TempDescriptor) meA.getKey();
+
+ if( !ogB.td2ln.containsKey( tdA ) ) {
return false;
}
-
- // we should have already checked the equality
- // of this pairing in the last pass if they both
- // exist so assert that they are equal now
- HeapRegionNode hrnA = og.id2hrn.get( idB );
- assert hrnB.equals( hrnA );
+ }
+
+ return true;
+ }
+
+
+ protected boolean areReferenceEdgesEqual( OwnershipGraph og ) {
+ if( !areallREinAandBequal( this, og ) ) {
+ return false;
}
return true;
}
- protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
- Set sA = og.id2hrn.entrySet();
+ static protected boolean areallREinAandBequal( OwnershipGraph ogA,
+ OwnershipGraph ogB ) {
+
+ // check all the heap region->heap region edges
+ Set sA = ogA.id2hrn.entrySet();
Iterator iA = sA.iterator();
while( iA.hasNext() ) {
Map.Entry meA = (Map.Entry) iA.next();
// we should have already checked that the same
// heap regions exist in both graphs
- assert id2hrn.containsKey( idA );
-
- // and are their edges the same? first check every
- // edge in A for presence and equality in B
- HeapRegionNode hrnChildA = null;
- Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
- while( heapRegionsItrA.hasNext() ) {
- Map.Entry me = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
-
- Integer idChildA = hrnChildA.getID();
- assert id2hrn.containsKey( idChildA );
-
- // at this point we know an edge in graph A exists
- // idA -> idChildA, does this edge exist in B?
- boolean edgeFound = false;
- HeapRegionNode hrnB = id2hrn.get( idA );
+ assert ogB.id2hrn.containsKey( idA );
- HeapRegionNode hrnChildB = null;
- Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
-
- if( idChildA.equals( hrnChildB.getID() ) ) {
- if( !repA.equals( repB ) ) {
- return false;
- }
- edgeFound = true;
- }
- }
-
- if( !edgeFound ) {
- return false;
- }
+ if( !areallREfromAequaltoB( ogA, hrnA, ogB ) ) {
+ return false;
}
// then check every edge in B for presence in A, starting
// from the same parent HeapRegionNode
- HeapRegionNode hrnB = id2hrn.get( idA );
-
- HeapRegionNode hrnChildB = null;
- Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry me = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
-
- Integer idChildB = hrnChildB.getID();
-
- // at this point we know an edge in graph B exists
- // idB -> idChildB, does this edge exist in A?
- boolean edgeFound = false;
-
- hrnChildA = null;
- heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
- while( heapRegionsItrA.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
-
- if( idChildB.equals( hrnChildA.getID() ) ) {
- assert repB.equals( repA );
- edgeFound = true;
- }
- }
+ HeapRegionNode hrnB = ogB.id2hrn.get( idA );
- if( !edgeFound ) {
- return false;
- }
- }
- }
-
- return true;
- }
+ if( !areallREfromAequaltoB( ogB, hrnB, ogA ) ) {
+ return false;
+ }
+ }
- protected boolean areLabelNodesEqual( OwnershipGraph og ) {
- // are all label nodes in A also in graph B?
- Set sA = og.td2ln.entrySet();
- Iterator iA = sA.iterator();
+ // then check all the label->heap region edges
+ sA = ogA.td2ln.entrySet();
+ iA = sA.iterator();
while( iA.hasNext() ) {
Map.Entry meA = (Map.Entry) iA.next();
TempDescriptor tdA = (TempDescriptor) meA.getKey();
+ LabelNode lnA = (LabelNode) meA.getValue();
+
+ // we should have already checked that the same
+ // label nodes exist in both graphs
+ assert ogB.td2ln.containsKey( tdA );
- if( !td2ln.containsKey( tdA ) ) {
+ if( !areallREfromAequaltoB( ogA, lnA, ogB ) ) {
return false;
}
- }
- // are all label nodes in B also in A?
- Set sB = td2ln.entrySet();
- Iterator iB = sB.iterator();
- while( iB.hasNext() ) {
- Map.Entry meB = (Map.Entry) iB.next();
- TempDescriptor tdB = (TempDescriptor) meB.getKey();
+ // then check every edge in B for presence in A, starting
+ // from the same parent LabelNode
+ LabelNode lnB = ogB.td2ln.get( tdA );
- if( !og.td2ln.containsKey( tdB ) ) {
+ if( !areallREfromAequaltoB( ogB, lnB, ogA ) ) {
return false;
}
}
return true;
}
- protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
- Set sA = og.td2ln.entrySet();
- Iterator iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- TempDescriptor tdA = (TempDescriptor) meA.getKey();
- LabelNode lnA = (LabelNode) meA.getValue();
- // we should have already checked that the same
- // label nodes exist in both graphs
- assert td2ln.containsKey( tdA );
+ static protected boolean areallREfromAequaltoB( OwnershipGraph ogA,
+ OwnershipNode onA,
+ OwnershipGraph ogB ) {
+
+ Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
+ while( itrA.hasNext() ) {
+ ReferenceEdge edgeA = itrA.next();
+ HeapRegionNode hrnChildA = edgeA.getDst();
+ Integer idChildA = hrnChildA.getID();
+
+ assert ogB.id2hrn.containsKey( idChildA );
+
+ // at this point we know an edge in graph A exists
+ // onA -> idChildA, does this exact edge exist in B?
+ boolean edgeFound = false;
+
+ OwnershipNode onB = null;
+ if( onA instanceof HeapRegionNode ) {
+ HeapRegionNode hrnA = (HeapRegionNode) onA;
+ onB = ogB.id2hrn.get( hrnA.getID() );
+ } else {
+ LabelNode lnA = (LabelNode) onA;
+ onB = ogB.td2ln.get( lnA.getTempDescriptor() );
+ }
- // and are their edges the same? first check every
- // edge in A for presence and equality in B
- HeapRegionNode hrnChildA = null;
- Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
- while( heapRegionsItrA.hasNext() ) {
- Map.Entry me = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
+ Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
+ while( itrB.hasNext() ) {
+ ReferenceEdge edgeB = itrB.next();
+ HeapRegionNode hrnChildB = edgeB.getDst();
- Integer idChildA = hrnChildA.getID();
- assert id2hrn.containsKey( idChildA );
+ if( idChildA.equals( hrnChildB.getID() ) &&
+ edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
- // at this point we know an edge in graph A exists
- // tdA -> idChildA, does this edge exist in B?
- boolean edgeFound = false;
- LabelNode lnB = td2ln.get( tdA );
-
- HeapRegionNode hrnChildB = null;
- Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
-
- if( idChildA.equals( hrnChildB.getID() ) ) {
- if( !repA.equals( repB ) ) {
- return false;
- }
+ // there is an edge in the right place with the right field,
+ // but do they have the same attributes?
+ if( edgeA.isInitialParamReflexive() == edgeB.isInitialParamReflexive() &&
+ edgeA.getBeta().equals( edgeB.getBeta() ) ) {
+
edgeFound = true;
+ } else {
+ return false;
}
}
-
- if( !edgeFound ) {
- return false;
- }
}
- // then check every edge in B for presence in A, starting
- // from the same parent LabelNode
- LabelNode lnB = td2ln.get( tdA );
-
- HeapRegionNode hrnChildB = null;
- Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry me = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
-
- Integer idChildB = hrnChildB.getID();
-
- // at this point we know an edge in graph B exists
- // tdB -> idChildB, does this edge exist in A?
- boolean edgeFound = false;
-
- hrnChildA = null;
- heapRegionsItrA = lnA.setIteratorToReferencedRegions();
- while( heapRegionsItrA.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
-
- if( idChildB.equals( hrnChildA.getID() ) ) {
- assert repB.equals( repA );
- edgeFound = true;
- }
- }
-
- if( !edgeFound ) {
- return false;
- }
- }
- }
-
+ if( !edgeFound ) {
+ return false;
+ }
+ }
+
return true;
}
}
-
+ /*
// given a set B of heap region node ID's, return the set of heap
// region node ID's that is reachable from B
public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
assert id2hrn.contains( id );
HeapRegionNode hrn = id2hrn.get( id );
- /*
- HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
-
- Iterator i = idSet.iterator();
- while( i.hasNext() ) {
- Integer idFromSet = (Integer) i.next();
- assert id2hrn.contains( idFromSet );
- hrnSet.add( id2hrn.get( idFromSet ) );
- }
- */
+
+ //HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
+
+ //Iterator i = idSet.iterator();
+ //while( i.hasNext() ) {
+ // Integer idFromSet = (Integer) i.next();
+ // assert id2hrn.contains( idFromSet );
+ // hrnSet.add( id2hrn.get( idFromSet ) );
+ //}
+
// do a traversal from hrn and see if any of the
// heap regions from the set come up during that
return false;
}
-
+ */
// for writing ownership graphs to dot files
}
}
- HeapRegionNode hrn = null;
- Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
+ Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
while( heapRegionsItr.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItr.next();
- hrn = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
+ ReferenceEdge edge = heapRegionsItr.next();
+ HeapRegionNode hrn = edge.getDst();
if( pruneGarbage && !visited.contains( hrn ) ) {
traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
bw.write( " " + ln.toString() +
" -> " + hrn.toString() +
- "[label=\"" + rep.toEdgeLabelString() +
+ "[label=\"" + edge.toGraphEdgeString() +
"\",decorate];\n" );
}
}
}
}
-
- HeapRegionNode hrnChild = null;
- Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
+ Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
while( childRegionsItr.hasNext() ) {
- Map.Entry me = (Map.Entry) childRegionsItr.next();
- hrnChild = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
+ ReferenceEdge edge = childRegionsItr.next();
+ HeapRegionNode hrnChild = edge.getDst();
switch( mode ) {
case VISIT_HRN_WRITE_FULL:
bw.write( " " + hrn.toString() +
" -> " + hrnChild.toString() +
- "[label=\"" + rep.toEdgeLabelString() +
+ "[label=\"" + edge.toGraphEdgeString() +
"\",decorate];\n" );
break;
}
public class Main {
+ static boolean aTestFailed;
+
+
protected static void test( String test,
boolean expected,
boolean result ) {
-
- String outcome = "...\tFAILED";
+ String outcome;
if( expected == result ) {
outcome = "...\tpassed";
+ } else {
+ outcome = "...\tFAILED";
+ aTestFailed = true;
}
System.out.println( test+" expected "+expected+outcome );
}
+
public static void main(String args[]) throws Exception {
- /*
+ aTestFailed = false;
+
+ testExample();
+ System.out.println( "---------------------------------------" );
+ testTokenTuple();
+ System.out.println( "---------------------------------------" );
+ testTokenTupleSet();
+ System.out.println( "---------------------------------------" );
+
+ if( aTestFailed ) {
+ System.out.println( "<><><><><><><><><><><><><><><><><><><><><><><><>" );
+ System.out.println( "<><><> WARNING: At least one test failed. <><><>" );
+ System.out.println( "<><><><><><><><><><><><><><><><><><><><><><><><>" );
+ } else {
+ System.out.println( "All tests passed." );
+ }
+ }
+
+
+ public static void testExample() {
+
// example test to know the testing routine is correct!
test( "4 == 5?", false, 4 == 5 );
test( "3 == 3?", true, 3 == 3 );
+ }
- TokenTuple tt0 = new TokenTuple( new Integer( 1 ),
- true,
- TokenTuple.ARITY_ONE );
-
- TokenTuple tt1 = new TokenTuple( new Integer( 1 ),
- true,
- TokenTuple.ARITY_ONE );
-
- TokenTuple tt2 = new TokenTuple( new Integer( 2 ),
- true,
- TokenTuple.ARITY_ONE );
+ public static void testTokenTuple() {
- TokenTuple tt3 = new TokenTuple( new Integer( 1 ),
- true,
- TokenTuple.ARITY_MANY );
+ TokenTuple tt0 = new TokenTuple( new Integer( 1 ), true, TokenTuple.ARITY_ONE );
+ TokenTuple tt1 = new TokenTuple( new Integer( 1 ), true, TokenTuple.ARITY_ONE );
+ TokenTuple tt2 = new TokenTuple( new Integer( 2 ), true, TokenTuple.ARITY_ONE );
+ TokenTuple tt3 = new TokenTuple( new Integer( 1 ), true, TokenTuple.ARITY_MANY );
+ TokenTuple tt4 = new TokenTuple( new Integer( 3 ), false, TokenTuple.ARITY_ONE );
+ TokenTuple tt5 = new TokenTuple( new Integer( 3 ), false, TokenTuple.ARITY_ONE );
test( "tt0 equals tt1?", true, tt0.equals( tt1 ) );
test( "tt1 equals tt0?", true, tt1.equals( tt0 ) );
+ test( "tt1.hashCode == tt0.hashCode?", true, tt1.hashCode() == tt0.hashCode() );
test( "tt0 equals tt2?", false, tt0.equals( tt2 ) );
test( "tt2 equals tt0?", false, tt2.equals( tt0 ) );
+ test( "tt2.hashCode == tt0.hashCode?", false, tt2.hashCode() == tt0.hashCode() );
test( "tt0 equals tt3?", false, tt0.equals( tt3 ) );
test( "tt3 equals tt0?", false, tt3.equals( tt0 ) );
+ test( "tt3.hashCode == tt0.hashCode?", false, tt3.hashCode() == tt0.hashCode() );
test( "tt2 equals tt3?", false, tt2.equals( tt3 ) );
test( "tt3 equals tt2?", false, tt3.equals( tt2 ) );
+ test( "tt3.hashCode == tt2.hashCode?", false, tt3.hashCode() == tt2.hashCode() );
tt1 = tt1.increaseArity();
test( "tt1 equals tt2?", false, tt1.equals( tt2 ) );
test( "tt2 equals tt1?", false, tt2.equals( tt1 ) );
+ test( "tt2.hashCode == tt1.hashCode?", false, tt2.hashCode() == tt1.hashCode() );
test( "tt1 equals tt3?", true, tt1.equals( tt3 ) );
- test( "tt3 equals tt1?", true, tt3.equals( tt1 ) );
+ test( "tt3 equals tt1?", true, tt3.equals( tt1 ) );
+ test( "tt3.hashCode == tt1.hashCode?", true, tt3.hashCode() == tt1.hashCode() );
+
+ test( "tt4 equals tt5?", true, tt4.equals( tt5 ) );
+ test( "tt5 equals tt4?", true, tt5.equals( tt4 ) );
+ test( "tt5.hashCode == tt4.hashCode?", true, tt5.hashCode() == tt4.hashCode() );
+
+ tt4 = tt4.increaseArity();
+
+ test( "tt4 equals tt5?", true, tt4.equals( tt5 ) );
+ test( "tt5 equals tt4?", true, tt5.equals( tt4 ) );
+ test( "tt5.hashCode == tt4.hashCode?", true, tt5.hashCode() == tt4.hashCode() );
+
+
+ TokenTuple tt6 = new TokenTuple( new Integer( 6 ), false, TokenTuple.ARITY_ONE );
+ TokenTuple tt7 = new TokenTuple( new Integer( 6 ), false, TokenTuple.ARITY_ONE );
+ TokenTuple tt8 = new TokenTuple( new Integer( 8 ), false, TokenTuple.ARITY_ONE );
+ TokenTuple tt9 = new TokenTuple( new Integer( 9 ), false, TokenTuple.ARITY_ONE );
+
+ test( "tt6 equals tt7?", true, tt6.equals( tt7 ) );
+ test( "tt6.hashCode == tt7.hashCode?", true, tt6.hashCode() == tt7.hashCode() );
+
+ test( "tt8 equals tt7?", false, tt8.equals( tt7 ) );
+ test( "tt8.hashCode == tt7.hashCode?", false, tt8.hashCode() == tt7.hashCode() );
+
+ // notice that this makes tt7 canonical
+ tt7 = tt7.changeTokenTo( new Integer( 8 ) );
+
+ test( "tt6 equals tt7?", false, tt6.equals( tt7 ) );
+ test( "tt6.hashCode == tt7.hashCode?", false, tt6.hashCode() == tt7.hashCode() );
+
+ test( "tt8 equals tt7?", true, tt8.equals( tt7 ) );
+ test( "tt8.hashCode == tt7.hashCode?", true, tt8.hashCode() == tt7.hashCode() );
+
+ test( "tt6 == tt7?", false, tt6 == tt7 );
+ test( "tt8 == tt7?", false, tt8 == tt7 );
+ test( "tt9 == tt7?", false, tt9 == tt7 );
+
+ tt6 = tt6.makeCanonical();
+ tt8 = tt8.makeCanonical();
+ tt9 = tt9.makeCanonical();
+
+ test( "tt6 == tt7?", false, tt6 == tt7 );
+ test( "tt8 == tt7?", true, tt8 == tt7 );
+ test( "tt9 == tt7?", false, tt9 == tt7 );
+ }
+
+
+ public static void testTokenTupleSet() {
+
+
+ }
+
+
+
+
+ public static void garbage() {
+ /*
+
+
TokenTupleSet tts0 = new TokenTupleSet( tt0 );
System.out.println( "rs3 is "+rs3 );
*/
-
+ /*
TokenTuple tt11 = new TokenTuple( new Integer( 1 ),
false,
TokenTuple.ARITY_ONE );
TokenTuple tt16 = new TokenTuple( new Integer( 6 ),
true,
TokenTuple.ARITY_MANY );
-
+ */
/*
TokenTupleSet tts10 = new TokenTupleSet();
tts10 = tts10.add( tt11 );
tts10 = tts10.add( tt16 );
*/
+ /*
TokenTuple tt21 = new TokenTuple( new Integer( 1 ),
false,
TokenTuple.ARITY_ONE );
TokenTuple tt26 = new TokenTuple( new Integer( 8 ),
true,
TokenTuple.ARITY_MANY );
-
+ */
/*
TokenTupleSet tts20 = new TokenTupleSet();
tts20 = tts20.add( tt21 );
System.out.println( "" );
System.out.println( "tts30 is "+tts30 );
*/
-
+ /*
TokenTupleSet tts40 = new TokenTupleSet();
tts40 = tts40.add( tt21 );
tts40 = tts40.add( tt23 );
System.out.println( "rs50 is "+rs50 );
System.out.println( "" );
System.out.println( "rs60 is "+rs60 );
+ */
}
}
projects / IRC.git / commitdiff