From f58b04b9704320c45739828d73b7583595a8f1cc Mon Sep 17 00:00:00 2001 From: jjenista Date: Fri, 18 Jul 2008 00:34:31 +0000 Subject: [PATCH] Added some functionality to reachability classes that is apparently not very helpful. They've been tested though, so might as well check it in, but the methods that are not of obvious use are committed but commented out. --- .../OwnershipAnalysis/OwnershipGraph.java | 20 ++- .../OwnershipAnalysis/ReachabilitySet.java | 80 +++++++++- .../OwnershipAnalysis/TokenTuple.java | 6 +- .../OwnershipAnalysis/TokenTupleSet.java | 73 +++++++++ .../OwnershipAnalysisTest/test01/test01.java | 12 +- .../testTokens/Main.java | 141 +++++++++++++++++- 6 files changed, 317 insertions(+), 15 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 6f902e53..ef55faed 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -399,8 +399,8 @@ public class OwnershipGraph { ReachabilitySet O = srcln.getReferenceTo( hrnSrc ).getBeta(); - ChangeTupleSet Cy = O.unionUpArity( R ); - ChangeTupleSet Cx = R.unionUpArity( O ); + ChangeTupleSet Cy = O.unionUpArityToChangeSet( R ); + ChangeTupleSet Cx = R.unionUpArityToChangeSet( O ); propagateTokens( hrnSrc, Cy, nodesWithNewAlpha, edgesWithNewBeta ); propagateTokens( hrn, Cx, nodesWithNewAlpha, edgesWithNewBeta ); @@ -604,9 +604,19 @@ public class OwnershipGraph { onReferencer = (OwnershipNode) itrReferencer.next(); ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnK ); - assert rep != null; - - addReferenceEdge( onReferencer, hrnSummary, rep.copy() ); + assert rep != null; + ReferenceEdgeProperties repSummary = onReferencer.getReferenceTo( hrnSummary ); + ReferenceEdgeProperties repMerged = rep.copy(); + + if( repSummary == null ) { + // the merge is trivial, nothing to be done + } else { + // otherwise an edge from the referencer to alpha_S exists already + // and the edge referencer->alpha_K should be merged with it + repMerged.setBeta( repMerged.getBeta().union( repSummary.getBeta() ) ); + } + + addReferenceEdge( onReferencer, hrnSummary, repMerged ); } diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java index 918d43c8..e7940741 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -26,6 +26,10 @@ public class ReachabilitySet extends Canonical { this( new TokenTupleSet( tt ).makeCanonical() ); } + public ReachabilitySet( HashSet possibleReachabilities ) { + this.possibleReachabilities = possibleReachabilities; + } + public ReachabilitySet( ReachabilitySet rs ) { assert rs != null; possibleReachabilities = (HashSet) rs.possibleReachabilities.clone(); // again, DEEP COPY?! @@ -40,6 +44,25 @@ public class ReachabilitySet extends Canonical { return possibleReachabilities.contains( tts ); } + public ReachabilitySet add( TokenTupleSet tts ) { + ReachabilitySet rsOut = new ReachabilitySet( tts ); + return this.union( rsOut ); + } + + public ReachabilitySet increaseArity( Integer token ) { + assert token != null; + + HashSet possibleReachabilitiesNew = new HashSet(); + + Iterator itr = iterator(); + while( itr.hasNext() ) { + TokenTupleSet tts = (TokenTupleSet) itr.next(); + possibleReachabilitiesNew.add( tts.increaseArity( token ) ); + } + + return new ReachabilitySet( possibleReachabilitiesNew ).makeCanonical(); + } + public Iterator iterator() { return possibleReachabilities.iterator(); } @@ -75,8 +98,63 @@ public class ReachabilitySet extends Canonical { return rsOut.makeCanonical(); } + + /* + public ReachabilitySet unionUpArity( ReachabilitySet rsIn ) { + assert rsIn != null; + + ReachabilitySet rsOut = new ReachabilitySet(); + Iterator itrIn; + Iterator itrThis; + + itrIn = rsIn.iterator(); + while( itrIn.hasNext() ) { + TokenTupleSet ttsIn = (TokenTupleSet) itrIn.next(); + + boolean foundEqual = false; + + itrThis = this.iterator(); + while( itrThis.hasNext() ) { + TokenTupleSet ttsThis = (TokenTupleSet) itrThis.next(); + + if( ttsIn.equalWithoutArity( ttsThis ) ) { + rsOut.possibleReachabilities.add( ttsIn.unionUpArity( ttsThis ) ); + foundEqual = true; + continue; + } + } + + if( !foundEqual ) { + rsOut.possibleReachabilities.add( ttsIn ); + } + } + + itrThis = this.iterator(); + while( itrThis.hasNext() ) { + TokenTupleSet ttsThis = (TokenTupleSet) itrThis.next(); + + boolean foundEqual = false; + + itrIn = rsIn.iterator(); + while( itrIn.hasNext() ) { + TokenTupleSet ttsIn = (TokenTupleSet) itrIn.next(); + + if( ttsThis.equalWithoutArity( ttsIn ) ) { + foundEqual = true; + continue; + } + } + + if( !foundEqual ) { + rsOut.possibleReachabilities.add( ttsThis ); + } + } + + return rsOut.makeCanonical(); + } + */ - public ChangeTupleSet unionUpArity( ReachabilitySet rsIn ) { + public ChangeTupleSet unionUpArityToChangeSet( ReachabilitySet rsIn ) { assert rsIn != null; ChangeTupleSet ctsOut = new ChangeTupleSet(); diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java index f198a0a0..cd2f248b 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java @@ -72,11 +72,11 @@ public class TokenTuple extends Canonical s = "S"; } - String t = "1"; + String t = ""; if( arity == ARITY_MANY ) { - t = "M"; + t = "*"; } - return new String( "<"+token+s+","+t+">" ); + return new String( token+s+t ); } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java index d8532901..d08c0073 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java @@ -31,12 +31,45 @@ public class TokenTupleSet extends Canonical { return tokenTuples.iterator(); } + public TokenTupleSet add( TokenTuple tt ) { + TokenTupleSet ttsOut = new TokenTupleSet( tt ); + return this.union( ttsOut ); + } + public TokenTupleSet union( TokenTupleSet ttsIn ) { TokenTupleSet ttsOut = new TokenTupleSet( this ); ttsOut.tokenTuples.addAll( ttsIn.tokenTuples ); return ttsOut.makeCanonical(); } + /* + public TokenTupleSet unionUpArity( TokenTupleSet ttsIn ) { + TokenTupleSet ttsOut = new TokenTupleSet(); + + Iterator itrIn = ttsIn.iterator(); + while( itrIn.hasNext() ) { + TokenTuple ttIn = (TokenTuple) itrIn.next(); + + if( this.containsToken( ttIn.getToken() ) ) { + ttsOut.tokenTuples.add( ttIn.increaseArity() ); + } else { + ttsOut.tokenTuples.add( ttIn ); + } + } + + Iterator itrThis = this.iterator(); + while( itrThis.hasNext() ) { + TokenTuple ttThis = (TokenTuple) itrThis.next(); + + if( !ttsIn.containsToken( ttThis.getToken() ) ) { + ttsOut.tokenTuples.add( ttThis ); + } + } + + return ttsOut.makeCanonical(); + } + */ + public boolean isEmpty() { return tokenTuples.isEmpty(); } @@ -45,6 +78,20 @@ public class TokenTupleSet extends Canonical { return tokenTuples.contains( tt ); } + // only needs to be done if newSummary is true? RIGHT? + public TokenTupleSet increaseArity( Integer token ) { + TokenTuple tt + = new TokenTuple( token, true, TokenTuple.ARITY_ONE ).makeCanonical(); + if( tokenTuples.contains( tt ) ) { + tokenTuples.remove( tt ); + tokenTuples.add( + new TokenTuple( token, true, TokenTuple.ARITY_MANY ).makeCanonical() + ); + } + + return makeCanonical(); + } + public boolean equals( Object o ) { if( !(o instanceof TokenTupleSet) ) { return false; @@ -58,6 +105,32 @@ public class TokenTupleSet extends Canonical { return tokenTuples.hashCode(); } + /* + public boolean equalWithoutArity( TokenTupleSet ttsIn ) { + Iterator itrIn = ttsIn.iterator(); + while( itrIn.hasNext() ) { + TokenTuple ttIn = (TokenTuple) itrIn.next(); + + if( !this.containsToken( ttIn.getToken() ) ) + { + return false; + } + } + + Iterator itrThis = this.iterator(); + while( itrThis.hasNext() ) { + TokenTuple ttThis = (TokenTuple) itrThis.next(); + + if( !ttsIn.containsToken( ttThis.getToken() ) ) + { + return false; + } + } + + return true; + } + */ + // this should be a hash table so we can do this by key public boolean containsToken( Integer token ) { Iterator itr = tokenTuples.iterator(); diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index ec5c6426..2072c0b4 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -54,13 +54,17 @@ public class Foo { // a heap region that is multi-object, flagged, not summary task Startup( StartupObject s{ initialstate } ) { - /* while( false ) { Foo a = new Foo(); a.x = new Foo(); - a.x.x = new Foo(); } - */ + + Foo b; + while( false ) { + Foo c = new Foo(); + c.x = b; + b = c; + } taskexit( s{ !initialstate } ); } @@ -76,6 +80,7 @@ task NewObject( Foo a{ f }, Foo b{ f } ) { } */ +/* task NewObjectA( Foo a{ f }, Foo b{ f } ) { Foo c = new Foo(); @@ -97,6 +102,7 @@ task NewObjectB( Foo a{ f }, Foo b{ f } ) { taskexit( a{ !f }, b{ !f } ); } +*/ /* task NewObject2( Foo a{ f }, Foo b{ f } ) { diff --git a/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java b/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java index ac115555..7fe74733 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java @@ -21,7 +21,7 @@ public class Main { public static void main(String args[]) throws Exception { - + /* // example test to know the testing routine is correct! test( "4 == 5?", false, 4 == 5 ); test( "3 == 3?", true, 3 == 3 ); @@ -106,7 +106,7 @@ public class Main { System.out.println( "rs1 is "+rs1 ); - ChangeTupleSet cts0 = rs0.unionUpArity( rs1 ); + ChangeTupleSet cts0 = rs0.unionUpArityToChangeSet( rs1 ); System.out.println( "cts0 is "+cts0 ); @@ -178,6 +178,141 @@ public class Main { tts01 = (TokenTupleSet) Canonical.makeCanonical( tts01 ); test( "tts00 equals tts01?", true, tts00.equals( tts01 ) ); - test( "tts00 == tts01?", true, tts00 == tts01 ); + test( "tts00 == tts01?", true, tts00 == tts01 ); + + + + ReachabilitySet rs2 = new ReachabilitySet( tts00 ); + ReachabilitySet rs3 = new ReachabilitySet( tts01 ).union( rs2 ); + + System.out.println( "rs3 is "+rs3 ); + + rs3 = rs3.increaseArity( new Integer( 11 ) ); + System.out.println( "rs3 is "+rs3 ); + */ + + + TokenTuple tt11 = new TokenTuple( new Integer( 1 ), + false, + TokenTuple.ARITY_ONE ); + + TokenTuple tt12 = new TokenTuple( new Integer( 2 ), + true, + TokenTuple.ARITY_ONE ); + + TokenTuple tt13 = new TokenTuple( new Integer( 3 ), + true, + TokenTuple.ARITY_MANY ); + + TokenTuple tt14 = new TokenTuple( new Integer( 4 ), + true, + TokenTuple.ARITY_ONE ); + + TokenTuple tt15 = new TokenTuple( new Integer( 5 ), + true, + 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( tt12 ); + tts10 = tts10.add( tt13 ); + tts10 = tts10.add( tt14 ); + tts10 = tts10.add( tt15 ); + tts10 = tts10.add( tt16 ); + */ + + TokenTuple tt21 = new TokenTuple( new Integer( 1 ), + false, + TokenTuple.ARITY_ONE ); + + TokenTuple tt22 = new TokenTuple( new Integer( 5 ), + true, + TokenTuple.ARITY_ONE ); + + TokenTuple tt23 = new TokenTuple( new Integer( 3 ), + true, + TokenTuple.ARITY_ONE ); + + TokenTuple tt24 = new TokenTuple( new Integer( 6 ), + true, + TokenTuple.ARITY_MANY ); + + TokenTuple tt25 = new TokenTuple( new Integer( 7 ), + true, + TokenTuple.ARITY_ONE ); + + TokenTuple tt26 = new TokenTuple( new Integer( 8 ), + true, + TokenTuple.ARITY_MANY ); + + /* + TokenTupleSet tts20 = new TokenTupleSet(); + tts20 = tts20.add( tt21 ); + tts20 = tts20.add( tt22 ); + tts20 = tts20.add( tt23 ); + tts20 = tts20.add( tt24 ); + tts20 = tts20.add( tt25 ); + tts20 = tts20.add( tt26 ); + + TokenTupleSet tts30 = tts10.unionUpArity( tts20 ); + + System.out.println( "tts10 is "+tts10 ); + System.out.println( "tts20 is "+tts20 ); + System.out.println( "" ); + System.out.println( "tts30 is "+tts30 ); + */ + + TokenTupleSet tts40 = new TokenTupleSet(); + tts40 = tts40.add( tt21 ); + tts40 = tts40.add( tt23 ); + + TokenTupleSet tts50 = new TokenTupleSet(); + tts50 = tts50.add( tt21 ); + tts50 = tts50.add( tt23 ); + tts50 = tts50.add( tt22 ); + + TokenTupleSet tts60 = new TokenTupleSet(); + tts60 = tts60.add( tt21 ); + tts60 = tts60.add( tt24 ); + + TokenTupleSet tts70 = new TokenTupleSet(); + tts70 = tts70.add( tt11 ); + tts70 = tts70.add( tt13 ); + tts70 = tts70.add( tt12 ); + + TokenTupleSet tts71 = new TokenTupleSet(); + tts71 = tts71.add( tt13 ); + tts71 = tts71.add( tt11 ); + tts71 = tts71.add( tt15 ); + + TokenTupleSet tts72 = new TokenTupleSet(); + tts72 = tts72.add( tt11 ); + tts72 = tts72.add( tt16 ); + + TokenTupleSet tts73 = new TokenTupleSet(); + tts73 = tts73.add( tt12 ); + + ReachabilitySet rs40 = new ReachabilitySet(); + rs40 = rs40.add( tts40 ); + rs40 = rs40.add( tts50 ); + rs40 = rs40.add( tts60 ); + + ReachabilitySet rs50 = new ReachabilitySet(); + rs50 = rs50.add( tts70 ); + rs50 = rs50.add( tts71 ); + rs50 = rs50.add( tts72 ); + rs50 = rs50.add( tts73 ); + + ReachabilitySet rs60 = rs50.unionUpArity( rs40 ); + + System.out.println( "rs40 is "+rs40 ); + System.out.println( "rs50 is "+rs50 ); + System.out.println( "" ); + System.out.println( "rs60 is "+rs60 ); } } -- 2.34.1