Java > Open Source Codes > soot > jimple > toolkits > annotation > purity > PurityGraph


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2005 Antoine Mine
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 /**
21  * Implementation of the paper "A Combined Pointer and Purity Analysis for
22  * Java Programs" by Alexandru Salcianu and Martin Rinard, within the
23  * Soot Optimization Framework.
24  *
25  * by Antoine Mine, 2005/01/24
26  */
27
28 package soot.jimple.toolkits.annotation.purity;
29 import java.util.*;
30 import java.io.*;
31 import soot.*;
32 import soot.util.*;
33 import soot.util.dot.*;
34 import soot.jimple.*;
35
36 /**
37  * Purity graphs are mutable structures that are updated in-place.
38  * You can safely hash graphs. Equality comparison means isomorphism
39  * (equal nodes, equal edges).
40  */
41
42 /**
43  * Modifications with respect to the article:
44  *
45  * - "unanalizable call" are treated by first constructing a conservative
46  * calee graph where all parameters escape globally and return points to
47  * the global node, and then applying the standard analysable call construction
48  *
49  * - unanalysable calls add a mutation on the global node; the "field" is named
50  * "outside-world" and models the mutation of any static field, but also
51  * side-effects by native methods, such as I/O, that make methods impure
52  * (see below).
53  *
54  * - Whenever a method mutates the global node, it is marked as "impure"
55  * (this can be due to a side-effect or static field mutation), even if the
56  * global node is not rechable from parameter nodes through outside edges.
57  * It seems to me it was a defect from the article ?
58  * TODO: see if we must take the global node into account also when stating
59  * whether a parameter is read-only or safe.
60  *
61  * - "simplifyXXX" functions are experimiental... they may be unsound, and
62  * thus, not used now.
63  *
64  *
65  *
66  *
67  * NOTE:
68  * A lot of precision degradation comes from sequences of the form
69  * this.field = y; z = this.field
70  * in initialisers: the second statment creates a load node because, as a
71  * parameter, this may have escaped and this.field may be externally modified
72  * in-between the two instructions. I am not sure this can actually happend
73  * in an initialiser... in a a function called directly and only by
74  * initialisers.
75  *
76  * For the moment, summary of unanalised methods are either pure, completely
77  * impure (modify args & side-effects) or partially impure (modify args but
78  * not the gloal node). We should really be able to specify more precisely
79  * which arguments are r/o or safe within this methods.
80  * E.g., the analysis java.lang.String: void getChars(int,int,char [],int)
81  * imprecisely finds that this is not safe (because of the internal call to
82  * System.arraycopy that, in general, may introduce aliases) => it pollutes
83  * many things (e.g., StringBuffer append(String), and thus, exception
84  * constructors, etc.)
85  *
86  */
87 public class PurityGraph
88 {
89     public static final boolean doCheck = false;
90
91     protected Set nodes; // all nodes
92 protected Set paramNodes; // only parameter & this nodes
93 protected MultiMap edges; // source node -> edges
94 protected MultiMap locals; // local -> nodes
95 protected Set ret; // return -> nodes
96 protected Set globEscape; // nodes escaping globally
97 protected MultiMap backEdges; // target node -> edges
98 protected MultiMap backLocals; // target node -> local node sources
99 protected MultiMap mutated; // node -> field such that (node,field) is mutated
100
101     /**
102      * Initially empty graph.
103      */
104     PurityGraph()
105     {
106     // nodes & paramNodes are added lazily
107 nodes = new HashSet();
108     paramNodes = new HashSet();
109     edges = new HashMultiMap();
110     locals = new HashMultiMap();
111     ret = new HashSet();
112     globEscape = new HashSet();
113     backEdges = new HashMultiMap();
114     backLocals = new HashMultiMap();
115     mutated = new HashMultiMap();
116     if (doCheck) sanityCheck();
117     }
118
119     /**
120      * Copy constructor.
121      */
122     PurityGraph(PurityGraph x)
123     {
124     nodes = new HashSet(x.nodes);
125     paramNodes = new HashSet(x.paramNodes);
126     edges = new HashMultiMap(x.edges);
127     locals = new HashMultiMap(x.locals);
128     ret = new HashSet(x.ret);
129     globEscape = new HashSet(x.globEscape);
130     backEdges = new HashMultiMap(x.backEdges);
131     backLocals = new HashMultiMap(x.backLocals);
132     mutated = new HashMultiMap(x.mutated);
133     if (doCheck) sanityCheck();
134     }
135
136     public int hashCode()
137     {
138     return nodes.hashCode()
139         //+ paramNodes.hashCode() // redundant info
140 + edges.hashCode()
141         + locals.hashCode()
142         + ret.hashCode()
143         + globEscape.hashCode()
144         //+ backEdges.hashCode() // redundant info
145 //+ backLocals.hashCode() // redundant info
146 + mutated.hashCode()
147         ;
148     }
149
150     public boolean equals(Object o)
151     {
152     if (!(o instanceof PurityGraph)) return false;
153     PurityGraph g = (PurityGraph)o;
154     return nodes.equals(g.nodes)
155         //&& paramNodes.equals(g.paramNodes) // redundant info
156 && edges.equals(g.edges)
157         && locals.equals(g.locals)
158         && ret.equals(g.ret)
159         && globEscape.equals(g.globEscape)
160         //&& backEdges.equals(g.backEdges) // redundant info
161 //&& backLocals.equals(g.backLocals) // redundant info
162 && mutated.equals(g.mutated)
163         ;
164     }
165
166     /**
167      * Caching: this semm to actually improve both speed and memory
168      * consumption!
169      */
170     private static Map nodeCache = new HashMap();
171     private static Map edgeCache = new HashMap();
172     private static PurityNode cacheNode(PurityNode p)
173     {
174     if (!nodeCache.containsKey(p)) nodeCache.put(p,p);
175     return (PurityNode)nodeCache.get(p);
176     }
177     private static PurityEdge cacheEdge(PurityEdge e)
178     {
179     if (!edgeCache.containsKey(e)) edgeCache.put(e,e);
180     return (PurityEdge)edgeCache.get(e);
181     }
182
183     /**
184      * Conservative constructor for unanalysable calls.
185      *
186      * <p>Note: this gives a valid summary for all native methods, including
187      * Thread.start().
188      *
189      * @param withEffect add a mutated abstract field for the global node to
190      * account for side-effects in the environment (I/O, etc.).
191      */
192     public static PurityGraph conservativeGraph(SootMethod m,
193                         boolean withEffect)
194     {
195     PurityGraph g = new PurityGraph();
196     PurityNode glob = PurityGlobalNode.node;
197     g.nodes.add(glob);
198
199     // parameters & this escape globally
200 Iterator it = m.getParameterTypes().iterator();
201     int i = 0;
202     while (it.hasNext()) {
203         if (it.next() instanceof RefLikeType) {
204         PurityNode n = cacheNode(new PurityParamNode(i));
205         g.globEscape.add(n);
206         g.nodes.add(n);
207         g.paramNodes.add(n);
208         }
209         i++;
210     }
211
212     // return value escapes globally
213 if (m.getReturnType() instanceof RefLikeType) g.ret.add(glob);
214
215     // add a side-effect on the environment
216 // added by [AM]
217 if (withEffect) g.mutated.put(glob,"outside-world");
218
219     if (doCheck) g.sanityCheck();
220     return g;
221     }
222
223
224     /**
225      * Special constructor for "pure" methods returning a fresh object.
226      * (or simply pure if returns void or primitive).
227      */
228     public static PurityGraph freshGraph(SootMethod m)
229     {
230     PurityGraph g = new PurityGraph();
231     if (m.getReturnType() instanceof RefLikeType) {
232         PurityNode n = cacheNode(new PurityMethodNode(m));
233         g.ret.add(n);
234         g.nodes.add(n);
235     }
236     if (doCheck) g.sanityCheck();
237     return g;
238     }
239
240
241     /**
242      * Replace the current graph with its union with arg.
243      * arg is not modified.
244      */
245     void union(PurityGraph arg)
246     {
247     nodes.addAll(arg.nodes);
248     paramNodes.addAll(arg.paramNodes);
249     edges.putAll(arg.edges);
250     locals.putAll(arg.locals);
251     ret.addAll(arg.ret);
252     globEscape.addAll(arg.globEscape);
253     backEdges.putAll(arg.backEdges);
254     backLocals.putAll(arg.backLocals);
255     mutated.putAll(arg.mutated);
256     if (doCheck) sanityCheck();
257     }
258
259
260     /**
261      * Sanity check. Used internally for debugging!
262      */
263     protected void sanityCheck()
264     {
265     boolean err = false;
266     Iterator it = edges.keySet().iterator();
267     while (it.hasNext()) {
268         PurityNode src = (PurityNode)it.next();
269         Iterator itt = edges.get(src).iterator();
270         while (itt.hasNext()) {
271         PurityEdge e = (PurityEdge)itt.next();
272         if (!src.equals(e.getSource()))
273             {G.v().out.println("invalid edge source "+e+", should be "+src);err=true;}
274         if (!nodes.contains(e.getSource()))
275             {G.v().out.println("nodes does not contain edge source "+e);err=true;}
276         if (!nodes.contains(e.getTarget()))
277             {G.v().out.println("nodes does not contain edge target "+e);err=true;}
278         if (!backEdges.get(e.getTarget()).contains(e))
279             {G.v().out.println("backEdges does not contain edge "+e);err=true;}
280         if (!e.isInside() && !e.getTarget().isLoad())
281             {G.v().out.println("target of outside edge is not a load node "+e);err=true;}
282         }
283     }
284     it = backEdges.keySet().iterator();
285     while (it.hasNext()) {
286         PurityNode dst = (PurityNode)it.next();
287         Iterator itt = backEdges.get(dst).iterator();
288         while (itt.hasNext()) {
289         PurityEdge e = (PurityEdge)itt.next();
290         if (!dst.equals(e.getTarget()))
291             {G.v().out.println("invalid backEdge dest "+e+", should be "+dst);err=true;}
292         if (!edges.get(e.getSource()).contains(e))
293             {G.v().out.println("backEdge not in edges "+e);err=true;}
294         }
295     }
296     it = nodes.iterator();
297     while (it.hasNext()) {
298         PurityNode n = (PurityNode)it.next();
299         if (n.isParam() && !paramNodes.contains(n))
300         {G.v().out.println("paramNode not in paramNodes "+n);err=true;}
301     }
302     it = paramNodes.iterator();
303     while (it.hasNext()) {
304         PurityNode n = (PurityNode)it.next();
305         if (!n.isParam())
306         {G.v().out.println("paramNode contains a non-param node "+n);err=true;}
307         if (!nodes.contains(n))
308         {G.v().out.println("paramNode not in nodes "+n);err=true;}
309     }
310     it = globEscape.iterator();
311     while (it.hasNext()) {
312         PurityNode n = (PurityNode)it.next();
313         if (!nodes.contains(n))
314         {G.v().out.println("globEscape not in nodes "+n);err=true;}
315     }
316     it = locals.keySet().iterator();
317     while (it.hasNext()) {
318         Local l = (Local)it.next();
319         Iterator itt = locals.get(l).iterator();
320         while (itt.hasNext()) {
321         PurityNode n = (PurityNode)itt.next();
322         if (!nodes.contains(n))
323             {G.v().out.println("target of local node in nodes "+l+" / "+n);err=true;}
324         if (!backLocals.get(n).contains(l))
325             {G.v().out.println("backLocals does contain local "+l+" / "+n);err=true;}
326         }
327     }
328     it = backLocals.keySet().iterator();
329     while (it.hasNext()) {
330         PurityNode n = (PurityNode)it.next();
331         Iterator itt = backLocals.get(n).iterator();
332         while (itt.hasNext()) {
333         Local l = (Local)itt.next();
334         if (!nodes.contains(n))
335             {G.v().out.println("backLocal node not in in nodes "+l+" / "+n);err=true;}
336         if (!locals.get(l).contains(n))
337             {G.v().out.println("locals does contain backLocal "+l+" / "+n);err=true;}
338         }
339     }
340     it = ret.iterator();
341     while (it.hasNext()) {
342         PurityNode n = (PurityNode)it.next();
343         if (!nodes.contains(n))
344         {G.v().out.println("target of ret not in nodes "+n);err=true;}
345     }
346     it = mutated.keySet().iterator();
347     while (it.hasNext()) {
348         PurityNode n = (PurityNode)it.next();
349         if (!nodes.contains(n))
350         {G.v().out.println("mutated node not in nodes "+n);err=true;}
351     }
352     if (err) {
353         dump();
354         DotGraph dot = new DotGraph("sanityCheckFailure");
355         fillDotGraph("chk",dot);
356         dot.plot("sanityCheckFailure.dot");
357         throw new Error ("PurityGraph sanity check failed!!!");
358     }
359     }
360
361     ////////////////////////
362 // ESCAPE INFORMATION //
363 ////////////////////////
364
365     protected void internalPassEdges(Set toColor, Set dest,
366                      boolean consider_inside)
367     {
368     Iterator it = toColor.iterator();
369     while (it.hasNext()) {
370         PurityEdge edge = (PurityEdge) it.next();
371         if (consider_inside || !edge.isInside()) {
372         PurityNode node = edge.getTarget();
373         if (!dest.contains(node)) {
374             dest.add(node);
375             internalPassEdges(edges.get(node),dest,consider_inside);
376         }
377         }
378     }
379     }
380
381     protected void internalPassNode(PurityNode node, Set dest,
382                     boolean consider_inside)
383     {
384     if (!dest.contains(node)) {
385         dest.add(node);
386         internalPassEdges(edges.get(node),dest,consider_inside);
387     }
388     }
389
390     protected void internalPassNodes(Set toColor, Set dest,
391                      boolean consider_inside)
392     {
393     Iterator it = toColor.iterator();
394     while (it.hasNext())
395         internalPassNode((PurityNode)it.next(),
396                  dest, consider_inside);
397     }
398
399     protected Set getEscaping()
400     {
401     Set escaping = new HashSet();
402     internalPassNodes(ret,escaping,true);
403     internalPassNodes(globEscape,escaping,true);
404     internalPassNode(PurityGlobalNode.node,escaping,true);
405     internalPassNodes(paramNodes,escaping,true);
406     return escaping;
407     }
408
409
410     /**
411      * Call this on the merge of graphs at all return points of a method to
412      * know whether the method is pure.
413      */
414     public boolean isPure()
415     {
416     if (!mutated.get(PurityGlobalNode.node).isEmpty()) return false;
417     Set A = new HashSet();
418     Set B = new HashSet();
419     internalPassNodes(paramNodes, A, false);
420     internalPassNodes(globEscape, B, true);
421     internalPassNode(PurityGlobalNode.node,B,true);
422     Iterator it = A.iterator();
423     while (it.hasNext()) {
424         PurityNode n = (PurityNode)it.next();
425         if (B.contains(n) || !mutated.get(n).isEmpty()) return false;
426     }
427     return true;
428     }
429
430    /**
431     * We use a less restrictive notion of purity for constructors: pure
432     * constructors can mutate fields of this.
433     *
434     * @see isPure
435     */
436     public boolean isPureConstructor()
437     {
438     if (!mutated.get(PurityGlobalNode.node).isEmpty()) return false;
439     Set A = new HashSet();
440     Set B = new HashSet();
441     internalPassNodes(paramNodes, A, false);
442     internalPassNodes(globEscape, B, true);
443     internalPassNode(PurityGlobalNode.node,B,true);
444     PurityNode th = PurityThisNode.node;
445     Iterator it = A.iterator();
446     while (it.hasNext()) {
447         PurityNode n = (PurityNode)it.next();
448         if (B.contains(n) ||
449         (!n.equals(th) && !mutated.get(n).isEmpty())) return false;
450     }
451     return true;
452     }
453
454     /**
455      * A parameter (or this) can be:
456      * - read and write
457      * - read only
458      * - safe (read only & no externally visible alias is created)
459      */
460     static final int PARAM_RW = 0;
461     static final int PARAM_RO = 1;
462     static final int PARAM_SAFE = 2;
463
464     protected int internalParamStatus(PurityNode p)
465     {
466     if (!paramNodes.contains(p)) return PARAM_RW;
467
468     Set S1 = new HashSet();
469     internalPassNode(p, S1, false);
470     Iterator it = S1.iterator();
471     while (it.hasNext()) {
472         PurityNode n = (PurityNode)it.next();
473         if (n.isLoad() || n.equals(p)) {
474         if (!mutated.get(n).isEmpty() ||
475             globEscape.contains(n)) return PARAM_RW;
476         }
477     }
478
479     Set S2 = new HashSet();
480     internalPassNodes(ret,S2,true);
481     internalPassNodes(paramNodes,S2,true);
482     it = S2.iterator();
483     while (it.hasNext()) {
484         Iterator itt = edges.get(it.next()).iterator();
485         while (itt.hasNext()) {
486         PurityEdge e = (PurityEdge)itt.next();
487         if (e.isInside() && S1.contains(e.getTarget()))
488             return PARAM_RO;
489         }
490     }
491
492     return PARAM_SAFE;
493     }
494
495     /**
496      * Call this on the merge of graphs at all return points of a method to
497      * know whether an object passed as method parameter is read only
498      * (PARAM_RO), read write (PARAM_RW), or safe (PARAM_SAFE).
499      * Returns PARAM_RW for primitive-type parameters.
500      */
501     public int paramStatus(int param)
502     { return internalParamStatus(cacheNode(new PurityParamNode(param))); }
503
504     /**
505      * @see isParamReadOnly
506      */
507     public int thisStatus()
508     { return internalParamStatus(PurityThisNode.node); }
509
510
511     /////////////////////////
512 // GRAPH MANUPULATIONS //
513 /////////////////////////
514
515     public Object clone()
516     {
517     return new PurityGraph(this);
518     }
519
520     // utility functions to update local / backLocals constitently
521 protected final boolean localsRemove(Local local)
522     {
523     Iterator it = locals.get(local).iterator();
524     while (it.hasNext()) {
525         Object node = it.next();
526         backLocals.remove(node,local);
527     }
528     return locals.remove(local);
529     }
530
531     protected final boolean localsPut(Local local, PurityNode node)
532     {
533     backLocals.put(node,local);
534     return locals.put(local,node);
535     }
536
537     protected final boolean localsPutAll(Local local, Set nodes)
538     {
539     Iterator it = nodes.iterator();
540     while (it.hasNext()) {
541         Object node = it.next();
542         backLocals.put(node,local);
543     }
544     return locals.putAll(local,nodes);
545     }
546
547     /** Utility function to remove a node & all adjacent edges */
548     protected final void removeNode(PurityNode n)
549     {
550     Iterator it = edges.get(n).iterator();
551     while (it.hasNext()) {
552         PurityEdge e = (PurityEdge)it.next();
553         backEdges.remove(e.getTarget(),e);
554     }
555     it = backEdges.get(n).iterator();
556     while (it.hasNext()) {
557         PurityEdge e = (PurityEdge)it.next();
558         edges.remove(e.getSource(),e);
559     }
560     it = backLocals.get(n).iterator();
561     while (it.hasNext()) {
562         Local l = (Local)it.next();
563         locals.remove(l,n);
564     }
565     ret.remove(n);
566     edges.remove(n);
567     backEdges.remove(n);
568     backLocals.remove(n);
569     nodes.remove(n);
570     paramNodes.remove(n);
571     globEscape.remove(n);
572     mutated.remove(n);
573     }
574
575
576     /** Utility function to merge node src into dst; src is removed */
577     protected final void mergeNodes(PurityNode src, PurityNode dst)
578     {
579     Iterator it = (new LinkedList(edges.get(src))).iterator();
580     while (it.hasNext()) {
581         PurityEdge e = (PurityEdge)it.next();
582         PurityNode n = e.getTarget();
583         if (n.equals(src)) n = dst;
584         PurityEdge ee =
585         cacheEdge(new PurityEdge(dst, e.getField(), n, e.isInside()));
586         edges.remove(src, e);
587         edges.put(dst, ee);
588         backEdges.remove(n, e);
589         backEdges.put(n, ee);
590     }
591     it = (new LinkedList(backEdges.get(src))).iterator();
592     while (it.hasNext()) {
593         PurityEdge e = (PurityEdge)it.next();
594         PurityNode n = e.getSource();
595         if (n.equals(src)) n = dst;
596         PurityEdge ee =
597         cacheEdge(new PurityEdge(n, e.getField(), dst, e.isInside()));
598         edges.remove(n, e);
599         edges.put(n, ee);
600         backEdges.remove(src, e);
601         backEdges.put(dst, ee);
602     }
603     it = (new LinkedList(backLocals.get(src))).iterator();
604     while (it.hasNext()) {
605         Local l = (Local)it.next();
606         locals.remove(l, src);
607         backLocals.remove(src, l);
608         locals.put(l,dst);
609         backLocals.put(dst, l);
610     }
611     {
612         Set m = mutated.get(src);
613         mutated.remove(src);
614         mutated.putAll(dst,m);
615     }
616     if (ret.contains(src)) {
617         ret.remove(src);
618         ret.add(dst);
619     }
620     if (globEscape.contains(src)) {
621         globEscape.remove(src);
622         globEscape.add(dst);
623     }
624     nodes.remove(src);
625     nodes.add(dst);
626     paramNodes.remove(src);
627     if (dst.isParam()) paramNodes.add(dst);
628     }
629
630     /** Experimental simplification: merge redundant load nodes. */
631     void simplifyLoad()
632     {
633     Iterator it = (new LinkedList(nodes)).iterator();
634     while (it.hasNext()) {
635         PurityNode p = (PurityNode)it.next();
636         Map fmap = new HashMap();
637         Iterator itt = (new LinkedList(edges.get(p))).iterator();
638         while (itt.hasNext()) {
639         PurityEdge e = (PurityEdge)itt.next();
640         PurityNode tgt = e.getTarget();
641         if (!e.isInside() && !tgt.equals(p)) {
642             String f = e.getField();
643             if (fmap.containsKey(f) && nodes.contains(fmap.get(f)))
644             mergeNodes(tgt, (PurityNode)fmap.get(f));
645             else fmap.put(f,tgt);
646         }
647         }
648     }
649     if (doCheck) sanityCheck();
650     }
651
652     /** Experimental sumplification: remove inside nodes not reachables
653     from escaping nodes (params, ret, globEscape) or load nodes. */
654     void simplifyInside()
655     {
656     Set r = new HashSet();
657     internalPassNodes(paramNodes,r,true);
658     internalPassNodes(ret,r,true);
659     internalPassNodes(globEscape,r,true);
660     internalPassNode(PurityGlobalNode.node,r,true);
661     Iterator it = nodes.iterator();
662     while (it.hasNext()) {
663         PurityNode n = (PurityNode) it.next();
664         if (n.isLoad()) internalPassNode(n,r,true);
665     }
666     it = (new LinkedList(nodes)).iterator();
667     while (it.hasNext()) {
668         PurityNode n = (PurityNode) it.next();
669         if (n.isInside() && !r.contains(n)) removeNode(n);
670     }
671     if (doCheck) sanityCheck();
672     }
673
674     /**
675      * Remove all local bindings (except ret).
676      * This info is indeed superfluous on summary purity graphs representing
677      * the effect of a method. This saves a little memory, but also,
678      * simplify summary graph drawings a lot!
679      *
680      * DO NOT USE DURING INTRA-PROCEDURAL ANALYSIS!
681      */
682     void removeLocals()
683     {
684     locals = new HashMultiMap();
685     backLocals = new HashMultiMap();
686     }
687
688     /** Copy assignment left = right. */
689     void assignParamToLocal(int right, Local left)
690     {
691     // strong update on local
692 PurityNode node = cacheNode(new PurityParamNode(right));
693     localsRemove(left);
694     localsPut(left,node);
695     nodes.add(node);
696     paramNodes.add(node);
697     if (doCheck) sanityCheck();
698     }
699
700     /** Copy assignment left = this. */
701     void assignThisToLocal(Local left)
702     {
703     // strong update on local
704 PurityNode node = PurityThisNode.node;
705     localsRemove(left);
706     localsPut(left,node);
707     nodes.add(node);
708     paramNodes.add(node);
709     if (doCheck) sanityCheck();
710     }
711
712     /** Copy assignment left = right. */
713     void assignLocalToLocal(Local right, Local left)
714     {
715     // strong update on local
716 localsRemove(left);
717     localsPutAll(left,locals.get(right));
718     if (doCheck) sanityCheck();
719     }
720
721     /** return right statement . */
722     void returnLocal(Local right)
723     {
724     // strong update on ret
725 ret.clear();
726     ret.addAll(locals.get(right));
727     if (doCheck) sanityCheck();
728     }
729
730     /**
731      * Load non-static: left = right.field, or left = right[?] if field is [].
732      */
733     void assignFieldToLocal(Stmt stmt, Local right, String field, Local left)
734     {
735     Set esc = new HashSet();
736     Set escaping = getEscaping();
737
738     // strong update on local
739 localsRemove(left);
740     Iterator itRight = locals.get(right).iterator();
741     while (itRight.hasNext()) {
742         PurityNode nodeRight = (PurityNode) itRight.next();
743
744         Iterator itEdges = edges.get(nodeRight).iterator();
745         while (itEdges.hasNext()) {
746         PurityEdge edge = (PurityEdge) itEdges.next();
747         if (edge.isInside() && edge.getField().equals(field))
748             localsPut(left, edge.getTarget());
749         }
750
751         if (escaping.contains(nodeRight)) esc.add(nodeRight);
752     }
753     
754     if (!esc.isEmpty()) {
755         // right can escape
756
757         // we add a label load node & outside edges
758 PurityNode loadNode = cacheNode(new PurityStmtNode(stmt,false));
759         nodes.add(loadNode);
760         
761         Iterator itEsc = esc.iterator();
762         while (itEsc.hasNext()) {
763         PurityNode node = (PurityNode) itEsc.next();
764         PurityEdge edge =
765             cacheEdge(new PurityEdge(node, field, loadNode, false));
766         if (edges.put(node, edge))
767             backEdges.put(loadNode, edge);
768         }
769         localsPut(left, loadNode);
770     }
771     if (doCheck) sanityCheck();
772     }
773
774     /**
775      * Store non-static: left.field = right, or left[?] = right if field is [].
776      */
777     void assignLocalToField(Local right, Local left, String field)
778     {
779     // weak update on inside edges
780 Iterator itLeft = locals.get(left).iterator();
781     while (itLeft.hasNext()) {
782         PurityNode nodeLeft = (PurityNode) itLeft.next();
783         Iterator itRight = locals.get(right).iterator();
784         while (itRight.hasNext()) {
785         PurityNode nodeRight = (PurityNode) itRight.next();
786         PurityEdge edge =
787             cacheEdge(new PurityEdge(nodeLeft, field, nodeRight, true));
788         if (edges.put(nodeLeft, edge))
789             backEdges.put(nodeRight, edge);
790         }
791         if (!nodeLeft.isInside())
792         mutated.put(nodeLeft, field);
793     }
794     if (doCheck) sanityCheck();
795     }
796
797     /** Allocation: left = new or left = new[?]. */
798     void assignNewToLocal(Stmt stmt, Local left)
799     {
800     // strong update on local
801 // we add a label inside node
802 PurityNode node = cacheNode(new PurityStmtNode(stmt,true));
803     localsRemove(left);
804     localsPut(left, node);
805     nodes.add(node);
806     if (doCheck) sanityCheck();
807     }
808
809     /** A local variable is used in an unknown construct. */
810     void localEscapes(Local l)
811     {
812     // nodes escape globally
813 globEscape.addAll(locals.get(l));
814     if (doCheck) sanityCheck();
815     }
816
817     /** A local variable is assigned to some outside value. */
818     void localIsUnknown(Local l)
819     {
820     // strong update on local
821 PurityNode node = PurityGlobalNode.node;
822     localsRemove(l);
823     localsPut(l, node);
824     nodes.add(node);
825     if (doCheck) sanityCheck();
826     }
827
828     /**
829      * Store static: C.field = right.
830      */
831     void assignLocalToStaticField(Local right, String field)
832     {
833     PurityNode node = PurityGlobalNode.node;
834     localEscapes(right);
835     mutated.put(node, field);
836     nodes.add(node);
837     if (doCheck) sanityCheck();
838     }
839
840     /**
841      * Store a primitive type into a non-static field left.field = v
842      */
843     void mutateField(Local left, String field)
844     {
845     Iterator it = locals.get(left).iterator();
846     while (it.hasNext()) {
847         PurityNode n = (PurityNode)it.next();
848         if (!n.isInside())
849         mutated.put(n, field);
850     }
851     if (doCheck) sanityCheck();
852     }
853
854     /**
855      * Store a primitive type into a static field left.field = v
856      */
857     void mutateStaticField(String field)
858     {
859     PurityNode node = PurityGlobalNode.node;
860     mutated.put(node, field);
861     nodes.add(node);
862     if (doCheck) sanityCheck();
863     }
864
865     /**
866      * Method call left = right.method(args).
867      *
868      * @param g is method's summary PurityGraph
869      * @param left can be null (no return value)
870      * @param right can be null (static call)
871      * @param args is a list of Value
872      */
873     void methodCall(PurityGraph g, Local right, List args, Local left)
874     {
875     MultiMap mu = new HashMultiMap();
876
877     // compute mapping relation g -> this
878 /////////////////////////////////////
879
880     Iterator it = args.iterator(); // (1) rule
881 int nb = 0;
882     while (it.hasNext()) {
883         Value arg = (Value)it.next();
884         if (arg instanceof Local &&
885         ((Local)arg).getType() instanceof RefLikeType) {
886         mu.putAll(cacheNode(new PurityParamNode(nb)),locals.get(arg));
887         }
888         nb++;
889     }
890     if (right!=null) // (1) rule for "this" argument
891 mu.putAll(PurityThisNode.node,locals.get(right));
892
893     // COULD BE OPTIMIZED!
894 // many times, we need to copy sets cause we mutate them within iterators
895 boolean hasChanged = true;
896     while (hasChanged) { // (2) & (3) rules fixpoint
897 hasChanged = false;
898
899         // (2)
900 it = (new LinkedList(mu.keySet())).iterator();
901         while (it.hasNext()) {
902         PurityNode n1 = (PurityNode)it.next();
903         Iterator it3 = (new LinkedList(mu.get(n1))).iterator();
904         while (it3.hasNext()) {
905             PurityNode n3 = (PurityNode)it3.next();
906             Iterator it12 = g.edges.get(n1).iterator();
907             while (it12.hasNext()) {
908             PurityEdge e12 = (PurityEdge)it12.next();
909             if (!e12.isInside()) {
910                 Iterator it34 = edges.get(n3).iterator();
911                 while (it34.hasNext()) {
912                 PurityEdge e34 = (PurityEdge)it34.next();
913                 if (e34.isInside() &&
914                     e12.getField().equals(e34.getField()))
915                     if (mu.put(e12.getTarget(),e34.getTarget()))
916                     hasChanged = true;
917                 }
918             }
919             }
920         }
921         }
922         
923         // (3)
924 it = g.edges.keySet().iterator();
925         while (it.hasNext()) {
926         PurityNode n1 = (PurityNode)it.next();
927         Iterator it3 = g.edges.keySet().iterator();
928         while (it3.hasNext()) {
929             PurityNode n3 = (PurityNode)it3.next();
930
931             // ((mu(n1) U {n1}) inter (mu(n3) U {n3})) not empty
932 Set mu1 = new HashSet(mu.get(n1));
933             Set mu3 = new HashSet(mu.get(n3));
934             boolean cond = n1.equals(n3) ||
935             mu1.contains(n3) || mu3.contains(n1);
936             Iterator itt = mu1.iterator();
937             while (!cond && itt.hasNext()) {
938             cond = cond || mu3.contains(itt.next());
939             }
940             
941             // add (mu(n4) U ({n4} inter PNodes)) to mu(n2)
942 if (cond && (!n1.equals(n3) || n1.isLoad())) {
943             Iterator it12 = g.edges.get(n1).iterator();
944             while (it12.hasNext()) {
945                 PurityEdge e12 = (PurityEdge)it12.next();
946                 if (!e12.isInside()) {
947                 Iterator it34 = g.edges.get(n3).iterator();
948                 while (it34.hasNext()) {
949                     PurityEdge e34 = (PurityEdge)it34.next();
950                     if (e34.isInside()) {
951                     if (e12.getField().equals(e34.getField())) {
952                         PurityNode n2 = e12.getTarget();
953                         PurityNode n4 = e34.getTarget();
954                         
955                         // add n4 (if not param node) to mu(n2)
956 if (!n4.isParam() && mu.put(n2,n4))
957                         hasChanged = true;
958                         
959                         // add mu(n4) to mu(n2)
960 if (mu.putAll(n2,mu.get(n4)))
961                         hasChanged = true;
962                     }
963                     }
964                 }
965                 }
966             }
967             }
968         }
969         }
970     }
971     
972     // extend mu into mu'
973 it = g.nodes.iterator();
974     while (it.hasNext()) {
975         PurityNode n = (PurityNode)it.next();
976         if (!n.isParam()) {
977         mu.put(n,n);
978         nodes.add(n);
979         }
980     }
981
982
983     // combine g into this
984 //////////////////////
985
986     // project edges
987 it = g.edges.keySet().iterator();
988     while (it.hasNext()) {
989         PurityNode n1 = (PurityNode)it.next();
990         Iterator it12 = g.edges.get(n1).iterator();
991         while (it12.hasNext()) {
992         PurityEdge e12 = (PurityEdge)it12.next();
993         String f = e12.getField();
994         PurityNode n2 = e12.getTarget();
995         Iterator itm1 = mu.get(n1).iterator();
996         while (itm1.hasNext()) {
997             PurityNode mu1 = (PurityNode)itm1.next();
998
999             if (e12.isInside()) {
1000            Iterator itm2 = mu.get(n2).iterator();
1001            while (itm2.hasNext()) {
1002                PurityNode mu2 = (PurityNode)itm2.next();
1003                PurityEdge edge =
1004                cacheEdge(new PurityEdge(mu1,f,mu2,true));
1005                edges.put(mu1,edge);
1006                backEdges.put(mu2,edge);
1007            }
1008            }
1009            else {
1010            PurityEdge edge =
1011                cacheEdge(new PurityEdge(mu1,f,n2,false));
1012            edges.put(mu1,edge);
1013            backEdges.put(n2,edge);
1014            }
1015        }
1016        }
1017    }
1018
1019    // return value
1020 if (left!=null) {
1021        // strong update on locals
1022 localsRemove(left);
1023        it = g.ret.iterator();
1024        while (it.hasNext())
1025        localsPutAll(left, mu.get(it.next()));
1026    }
1027    
1028    // global escape
1029 it = g.globEscape.iterator();
1030    while (it.hasNext())
1031        globEscape.addAll(mu.get(it.next()));
1032
1033    if (doCheck) sanityCheck();
1034
1035
1036    // simplification
1037 /////////////////
1038
1039    Set escaping = getEscaping();
1040    it = (new LinkedList(nodes)).iterator();
1041    while (it.hasNext()) {
1042        PurityNode n = (PurityNode)it.next();
1043        if (!escaping.contains(n))
1044        if (n.isLoad())
1045            // remove captured load nodes
1046 removeNode(n);
1047        else {
1048            // ... and outside edges from captured nodes
1049 Iterator itt = (new LinkedList(edges.get(n))).iterator();
1050            while (itt.hasNext()) {
1051            PurityEdge e = (PurityEdge)itt.next();
1052            if (!e.isInside()) {
1053                edges.remove(n,e);
1054                backEdges.remove(e.getTarget(),e);
1055            }
1056            }
1057        }
1058    }
1059
1060    // update mutated
1061 /////////////////
1062
1063    it = g.mutated.keySet().iterator();
1064    while (it.hasNext()) {
1065        PurityNode n = (PurityNode)it.next();
1066        Iterator itt = mu.get(n).iterator();
1067        while (itt.hasNext()) {
1068        PurityNode nn = (PurityNode)itt.next();
1069        if (nodes.contains(nn) && !nn.isInside()) {
1070            Iterator ittt = g.mutated.get(n).iterator();
1071            while (ittt.hasNext()) {
1072            String f = (String )ittt.next();
1073            mutated.put(nn,f);
1074            }
1075        }
1076        }
1077    }
1078
1079    if (doCheck) sanityCheck();
1080    }
1081
1082
1083    /////////////
1084 // DRAWING //
1085 /////////////
1086
1087    /**
1088     * Fills a dot graph or subgraph with the graphical representation
1089     * of the purity graph.
1090     *
1091     * @param prefix is used to prefix all dot node and edge names. Use it
1092     * to avoid collision when several subgraphs are laid in the same dot
1093     * file!
1094     *
1095     * @param out is a newly created dot graph or subgraph where to put the
1096     * result.
1097     *
1098     * <p>Note: outside edges, param and load nodes are gray dashed, while
1099     * inside edges and nodes are solid black.
1100     * Globally escaping nodes have a red label.
1101     */
1102    void fillDotGraph(String prefix, DotGraph out)
1103    {
1104        Map nodeId = new HashMap();
1105    int id = 0;
1106
1107    // add nodes
1108 Iterator it = nodes.iterator();
1109    while (it.hasNext()) {
1110        PurityNode n = (PurityNode) it.next();
1111        String label = "N"+prefix+"_"+id;
1112        DotGraphNode node = out.drawNode(label);
1113        node.setLabel(n.toString());
1114        if (!n.isInside()) {
1115        node.setStyle("dashed");
1116        node.setAttribute("color","gray50");
1117        }
1118        if (globEscape.contains(n)) node.setAttribute("fontcolor","red");
1119        nodeId.put(n,label);
1120        id++;
1121    }
1122    
1123    // add edges
1124 it = edges.keySet().iterator();
1125    while (it.hasNext()) {
1126        PurityNode src = (PurityNode) it.next();
1127        Iterator itt = edges.get(src).iterator();
1128        while (itt.hasNext()) {
1129        PurityEdge e = (PurityEdge) itt.next();
1130        DotGraphEdge edge =
1131            out.drawEdge((String )nodeId.get(e.getSource()),
1132                 (String )nodeId.get(e.getTarget()));
1133        edge.setLabel(e.getField());
1134        if (!e.isInside()) {
1135            edge.setStyle("dashed");
1136            edge.setAttribute("color","gray50");
1137            edge.setAttribute("fontcolor","gray40");
1138        }
1139        }
1140    }
1141
1142    // add locals
1143 it = locals.keySet().iterator();
1144    while (it.hasNext()) {
1145        Local local = (Local) it.next();
1146        if (!locals.get(local).isEmpty()) {
1147        String label = "L"+prefix+"_"+id;
1148        DotGraphNode node = out.drawNode(label);
1149        node.setLabel(local.toString());
1150        node.setShape("plaintext");
1151        Iterator itt = locals.get(local).iterator();
1152        while (itt.hasNext()) {
1153            PurityNode dst = (PurityNode) itt.next();
1154            out.drawEdge(label,(String )nodeId.get(dst));
1155        }
1156        id++;
1157        }
1158    }
1159
1160    // ret
1161 if (!ret.isEmpty()) {
1162        DotGraphNode node = out.drawNode("ret_"+prefix);
1163        node.setLabel("ret");
1164        node.setShape("plaintext");
1165        Iterator itt = ret.iterator();
1166        while (itt.hasNext()) {
1167        PurityNode dst = (PurityNode) itt.next();
1168        out.drawEdge("ret_"+prefix,(String )nodeId.get(dst));
1169        }
1170    }
1171
1172    // add mutated
1173 it = mutated.keySet().iterator();
1174    while (it.hasNext()) {
1175        PurityNode n = (PurityNode)it.next();
1176        Iterator itt = mutated.get(n).iterator();
1177        while (itt.hasNext()) {
1178        String f = (String )itt.next();
1179        String label = "M"+prefix+"_"+id;
1180        DotGraphNode node = out.drawNode(label);
1181        node.setLabel("");
1182        node.setShape("plaintext");
1183        DotGraphEdge edge = out.drawEdge((String )nodeId.get(n),label);
1184        edge.setLabel(f);
1185        id++;
1186        }
1187    }
1188    }
1189
1190    /** Debugging... */
1191
1192    static private void dumpSet(String name, Set s) {
1193    G.v().out.println(name);
1194    Iterator it = s.iterator();
1195    while (it.hasNext()) G.v().out.println(" "+it.next().toString());
1196    }
1197
1198    static private void dumpMultiMap(String name, MultiMap s) {
1199    G.v().out.println(name);
1200    Iterator it = s.keySet().iterator();
1201    while (it.hasNext()) {
1202        Object o = it.next();
1203        G.v().out.println(" "+o.toString());
1204        Iterator itt = s.get(o).iterator();
1205        while (itt.hasNext())
1206        G.v().out.println(" "+itt.next().toString());
1207    }
1208    }
1209
1210    void dump()
1211    {
1212    dumpSet("nodes Set:",nodes);
1213    dumpSet("paramNodes Set:",paramNodes);
1214    dumpMultiMap("edges MultiMap:",edges);
1215    dumpMultiMap("locals MultiMap:",locals);
1216    dumpSet("ret Set:",ret);
1217    dumpSet("globEscape Set:",globEscape);
1218    dumpMultiMap("backEdges MultiMap:",backEdges);
1219    dumpMultiMap("backLocals MultiMap:",backLocals);
1220    dumpMultiMap("mutated MultiMap:",mutated);
1221    G.v().out.println("");
1222    }
1223
1224
1225    /** Simple statistics on maximal graph sizes.*/
1226
1227    static private int maxInsideNodes = 0;
1228    static private int maxLoadNodes = 0;
1229    static private int maxInsideEdges = 0;
1230    static private int maxOutsideEdges = 0;
1231    static private int maxMutated = 0;
1232
1233    void dumpStat()
1234    {
1235    G.v().out.println("Stat: "+
1236              maxInsideNodes+" inNodes, "+
1237              maxLoadNodes+" loadNodes, "+
1238              maxInsideEdges+" inEdges, "+
1239              maxOutsideEdges+" outEdges, "+
1240              maxMutated+" mutated.");
1241    }
1242
1243    void updateStat()
1244    {
1245    Iterator it = nodes.iterator();
1246    int insideNodes = 0;
1247    int loadNodes = 0;
1248    while (it.hasNext()) {
1249        PurityNode n = (PurityNode)it.next();
1250        if (n.isInside()) insideNodes++;
1251        else if (n.isLoad()) loadNodes++;
1252    }
1253    int insideEdges = 0;
1254    int outsideEdges = 0;
1255    it = edges.keySet().iterator();
1256    while (it.hasNext()) {
1257        Iterator itt = edges.get(it.next()).iterator();
1258        while (itt.hasNext()) {
1259        PurityEdge e = (PurityEdge)itt.next();
1260        if (e.isInside()) insideEdges++;
1261        else outsideEdges++;
1262        }
1263    }
1264    int mutatedFields = 0;
1265    it = mutated.keySet().iterator();
1266    while (it.hasNext()) mutatedFields += mutated.get(it.next()).size();
1267
1268    boolean changed = false;
1269    if (insideNodes>maxInsideNodes)
1270        { maxInsideNodes=insideNodes; changed=true; }
1271    if (loadNodes>maxLoadNodes)
1272        { maxLoadNodes=loadNodes; changed=true; }
1273    if (insideEdges>maxInsideEdges)
1274        { maxInsideEdges=insideEdges; changed=true; }
1275    if ( outsideEdges>maxOutsideEdges)
1276        { maxOutsideEdges=outsideEdges; changed=true; }
1277    if (mutatedFields>maxMutated)
1278        { maxMutated=mutatedFields; changed=true; }
1279    if (changed) dumpStat();
1280    }
1281}
1282

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags