From b17c5bbd637ff915a48ca536d140c09679ab758f Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 21 Aug 2008 23:51:40 +0000 Subject: [PATCH] more method call stuff, still partial --- .../OwnershipAnalysis/OwnershipGraph.java | 7 +- .../OwnershipAnalysis/ReachabilitySet.java | 49 +++++++++++++ .../OwnershipAnalysis/TokenTupleSet.java | 68 +++++++++---------- .../testTokens/Main.java | 17 +++++ 4 files changed, 103 insertions(+), 38 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 7c9575a0..42725d10 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -997,6 +997,7 @@ public class OwnershipGraph { ReferenceEdge edge = edgeItr.next(); D_i = D_i.union( edge.getBeta() ); } + D_i = D_i.exhaustiveArityCombinations(); paramIndex2rewriteD.put( paramIndex, D_i ); } @@ -1159,7 +1160,7 @@ public class OwnershipGraph { Iterator ttsItr = rules.iterator(); while( ttsItr.hasNext() ) { TokenTupleSet tts = ttsItr.next(); - r0 = r0.union( tts.simpleRewriteToken( tokenToRewrite, hrn.getAlpha() ) ); + r0 = r0.union( tts.rewriteToken( tokenToRewrite, hrn.getAlpha() ) ); } ReachabilitySet r1 = new ReachabilitySet().makeCanonical(); @@ -1198,7 +1199,7 @@ public class OwnershipGraph { TokenTuple tokenToRewriteJ = paramIndex2paramToken.get( paramIndexJ ); assert tokenToRewriteJ != null; if( ttsIn.containsTuple( tokenToRewriteJ ) ) { - ReachabilitySet r = ttsIn.exhaustiveRewriteToken( tokenToRewriteJ, D_j ); + ReachabilitySet r = ttsIn.rewriteToken( tokenToRewriteJ, D_j ); Iterator ttsItr = r.iterator(); while( ttsItr.hasNext() ) { TokenTupleSet tts = ttsItr.next(); @@ -1216,7 +1217,7 @@ public class OwnershipGraph { TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get( paramIndexJ ); assert tokenStarToRewriteJ != null; if( ttsIn.containsTuple( tokenStarToRewriteJ ) ) { - ReachabilitySet r = ttsIn.exhaustiveRewriteToken( tokenStarToRewriteJ, D_j ); + ReachabilitySet r = ttsIn.rewriteToken( tokenStarToRewriteJ, D_j ); Iterator ttsItr = r.iterator(); while( ttsItr.hasNext() ) { TokenTupleSet tts = ttsItr.next(); diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java index 2be4158c..2f45849f 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -210,6 +210,55 @@ public class ReachabilitySet extends Canonical { } + public ReachabilitySet exhaustiveArityCombinations() { + ReachabilitySet rsOut = new ReachabilitySet(); + + int numDimensions = this.possibleReachabilities.size(); + + // add an extra digit to detect termination + int[] digits = new int[numDimensions+1]; + + int minArity = 0; + int maxArity = 2; + + // start with the minimum possible coordinate + for( int i = 0; i < numDimensions+1; ++i ) { + digits[i] = minArity; + } + + // and stop when the highest-ordered axis rolls above the minimum + while( digits[numDimensions] == minArity ) { + + // spit out a "coordinate" made from these digits + TokenTupleSet ttsCoordinate = new TokenTupleSet(); + Iterator ttsItr = this.iterator(); + for( int i = 0; i < numDimensions; ++i ) { + assert ttsItr.hasNext(); + TokenTupleSet ttsUnit = ttsItr.next(); + for( int j = 0; j < digits[i]; ++j ) { + ttsCoordinate = ttsCoordinate.unionUpArity( ttsUnit ); + } + } + rsOut = rsOut.add( ttsCoordinate.makeCanonical() ); + + // increment + for( int i = 0; i < numDimensions+1; ++i ) { + digits[i]++; + if( digits[i] > maxArity ) { + // this axis reached its max, so roll it back to min and increment next higher digit + digits[i] = minArity; + + } else { + // this axis did not reach its max so we just enumerated a new unique coordinate, stop + break; + } + } + } + + return rsOut.makeCanonical(); + } + + public boolean equals(Object o) { if( o == null ) { return false; diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java index 69b954a8..51e21242 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java @@ -58,6 +58,33 @@ public class TokenTupleSet extends Canonical { return ttsOut.makeCanonical(); } + public TokenTupleSet unionUpArity( TokenTupleSet ttsIn ) { + assert ttsIn != null; + TokenTupleSet ttsOut = new TokenTupleSet(); + + Iterator ttItr = this.iterator(); + while( ttItr.hasNext() ) { + TokenTuple tt = ttItr.next(); + + if( ttsIn.containsToken( tt.getToken() ) ) { + ttsOut.tokenTuples.add(tt.increaseArity()); + } else { + ttsOut.tokenTuples.add(tt); + } + } + + ttItr = ttsIn.iterator(); + while( ttItr.hasNext() ) { + TokenTuple tt = ttItr.next(); + + if( !ttsOut.containsToken(tt.getToken()) ) { + ttsOut.tokenTuples.add(tt); + } + } + + return ttsOut.makeCanonical(); + } + public TokenTupleSet add(TokenTuple tt) { assert tt != null; TokenTupleSet ttsOut = new TokenTupleSet(tt); @@ -181,46 +208,18 @@ public class TokenTupleSet extends Canonical { } - public ReachabilitySet simpleRewriteToken( TokenTuple tokenToRewrite, - ReachabilitySet replacements ) { + public ReachabilitySet rewriteToken( TokenTuple tokenToRewrite, + ReachabilitySet replacements ) { ReachabilitySet rsOut = new ReachabilitySet().makeCanonical(); - - if( !tokenTuples.contains( tokenToRewrite ) ) { - rsOut = rsOut.add( this ); - - } else { - TokenTupleSet ttsMinusToken = new TokenTupleSet( this ); - ttsMinusToken.tokenTuples.remove( tokenToRewrite ); - - Iterator replaceItr = replacements.iterator(); - while( replaceItr.hasNext() ) { - TokenTupleSet replacement = replaceItr.next(); - TokenTupleSet replaced = new TokenTupleSet(); - replaced.tokenTuples.addAll( ttsMinusToken.tokenTuples ); - replaced.tokenTuples.addAll( replacement.tokenTuples ); - replaced = replaced.makeCanonical(); - rsOut = rsOut.add( replaced ); - } - } - - return rsOut; - } - - - public ReachabilitySet exhaustiveRewriteToken( TokenTuple tokenToRewrite, - ReachabilitySet replacements ) { - ReachabilitySet rsOut = new ReachabilitySet().makeCanonical(); - - /* if( !tokenTuples.contains( tokenToRewrite ) ) { rsOut = rsOut.add( this ); - + } else { TokenTupleSet ttsMinusToken = new TokenTupleSet( this ); ttsMinusToken.tokenTuples.remove( tokenToRewrite ); - + Iterator replaceItr = replacements.iterator(); while( replaceItr.hasNext() ) { TokenTupleSet replacement = replaceItr.next(); @@ -231,11 +230,10 @@ public class TokenTupleSet extends Canonical { rsOut = rsOut.add( replaced ); } } - */ - + return rsOut; } - + public String toString() { return tokenTuples.toString(); diff --git a/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java b/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java index 131f6b07..7c5a4cf6 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java @@ -549,5 +549,22 @@ public class Main { test( "cts1 == cts0?", true, cts1 == cts0 ); test( "cts1.hashCode() == cts0.hashCode()?", true, cts1.hashCode() == cts0.hashCode() ); + + TokenTuple tt173 = new TokenTuple( new Integer( 173 ), false, TokenTuple.ARITY_ONE ).makeCanonical(); + TokenTuple tt174 = new TokenTuple( new Integer( 174 ), true, TokenTuple.ARITY_ONE ).makeCanonical(); + TokenTuple tt174b = new TokenTuple( new Integer( 174 ), true, TokenTuple.ARITY_MANY ).makeCanonical(); + TokenTuple tt177 = new TokenTuple( new Integer( 177 ), true, TokenTuple.ARITY_ONE ).makeCanonical(); + + TokenTupleSet tts3 = new TokenTupleSet().add( tt173 ); + TokenTupleSet tts4 = new TokenTupleSet().add( tt174 ); + TokenTupleSet tts7 = new TokenTupleSet().add( tt177 ); + TokenTupleSet tts4b7 = new TokenTupleSet().add( tt174b ).add( tt177 ); + TokenTupleSet tts43 = new TokenTupleSet().add( tt174 ).add( tt173 ); + + ReachabilitySet rs100 = new ReachabilitySet().add( tts3 ).add( tts4 ).add( tts7 ).add( tts4b7 ).add( tts43 ); + ReachabilitySet rs101 = rs100.exhaustiveArityCombinations(); + + System.out.println( "#####################\nrs100 = \n"+rs100 ); + System.out.println( "#####################\nrs101 = \n"+rs101 ); } } -- 2.34.1