KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > aspectj > compiler > base > FlowCheckerPass


1 /* -*- Mode: Java; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2  *
3  * This file is part of the compiler and core tools for the AspectJ(tm)
4  * programming language; see http://aspectj.org
5  *
6  * The contents of this file are subject to the Mozilla Public License
7  * Version 1.1 (the "License"); you may not use this file except in
8  * compliance with the License. You may obtain a copy of the License at
9  * either http://www.mozilla.org/MPL/ or http://aspectj.org/MPL/.
10  *
11  * Software distributed under the License is distributed on an "AS IS" basis,
12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13  * for the specific language governing rights and limitations under the
14  * License.
15  *
16  * The Original Code is AspectJ.
17  *
18  * The Initial Developer of the Original Code is Xerox Corporation. Portions
19  * created by Xerox Corporation are Copyright (C) 1999-2002 Xerox Corporation.
20  * All Rights Reserved.
21  *
22  * Contributor(s):
23  */

24
25 package org.aspectj.compiler.base;
26
27 import org.aspectj.compiler.base.ast.*;
28 import org.aspectj.compiler.base.*;
29
30 import java.util.*;
31
32 /** This pass signals errors for
33
34     <ul>
35       <li>used-before-assigned vars and blank-final fields</li>
36       <li>assigned-twice blank finals</li>
37       <li>constructors not filling in blank final fields</li>
38       <li>unreachable stmts</li>
39       <li>missing return stmts</li>
40       <li>various illegal try/catch stmts</li>
41     </ul>
42
43     <p> It makes exactly one side-effect: In anonymous classes, it
44     sets up the throws clause to include any thrown checked
45     exceptions, as required by JLS 15.9.5.1. </p>
46
47     <p> Other than that one side-effect, it only signals errors. </p>
48 */

49
50 public final class FlowCheckerPass extends WalkerPass {
51     public FlowCheckerPass(JavaCompiler jc) {
52         super(jc);
53     }
54
55     public FlowCheckerPass(JavaCompiler jc, TypeDec currentTypeDec) {
56         super(jc);
57         currentType = currentTypeDec.getType();
58     }
59
60     public FlowCheckerPass(JavaCompiler jc, Set da, TypeDec currentTypeDec) {
61         super(jc);
62         setVars(Vars.makeSets(da, Set.getNone()));
63         currentType = currentTypeDec.getType();
64     }
65
66     public FlowCheckerPass(JavaCompiler jc, Vars v, TypeDec currentTypeDec) {
67         super(jc);
68         setVars(v);
69         currentType = currentTypeDec.getType();
70     }
71
72     private Type currentType = null;
73     public boolean isCurrent(FieldDec fd) {
74         return fd.getDeclaringType() == currentType;
75     }
76
77     public String JavaDoc getDisplayName() { return "analyzing control flow"; }
78
79     // all process does is walk through types until we get to
80
// something useful. This is never called within exprs/stmts,
81
// except for local classes.
82

83     public ASTObject process(ASTObject object) {
84         return this.process(object, true);
85     }
86     public ASTObject processBoolean(ASTObject object) {
87         return this.process(object, false);
88     }
89
90     private ASTObject process(ASTObject object, boolean cleanUp) {
91         if (object == null) return object;
92         //printDebug(i++, object, true);
93
if (! isLive() && object instanceof Stmt && ((Stmt)object).mustBeLive()) {
94             object.showError("unreachable statement");
95         } else {
96             object.walkFlow(this);
97         }
98         if (cleanUp) {
99             setVars(getVars().getTrue().join(getVars().getFalse()));
100         }
101         //printDebug(--i, object, false);
102

103         return object;
104     }
105
106     int i = 0;
107     private void printDebug(int i, ASTObject object, boolean in) {
108         for (int j = 0; j < i; j++) System.err.print(" ");
109         System.err.println("[" + i + "] da/dua:" + vars + " pa:" + possbilyAssigned
110                            + " exns:" + getExns() + " "
111                            + (liveFlag ? "live" : "dead") + " "
112                            + (in ? " --> " : " <-- ") + object);
113     }
114
115     // ------------------------------
116
// state
117

118     private Vars vars = Vars.noVars;
119     private Set possbilyAssigned = Set.empty;
120     private ESet possibleExns = ESet.getEmpty();
121     private boolean liveFlag = true;
122     private ControlContext context = new ControlContext();
123
124     // methods
125

126     public Vars getVars() { return vars; }
127     public void setVars(Vars v) { vars = v; }
128     public void setVars(Vars v0, Vars v1) { vars = Vars.makePair(v0, v1); }
129
130     //
131
public void addPossiblyAssigned(VarDec dec) {
132         possbilyAssigned = possbilyAssigned.add(dec);
133     }
134     public Set popPossiblyAssigned() {
135         Set pa = possbilyAssigned;
136         possbilyAssigned = Set.empty;
137         return pa;
138     }
139     public void mergePossiblyAssigned(Set pa) {
140         possbilyAssigned = possbilyAssigned.union(pa);
141     }
142
143     //
144
public ESet popExns() {
145         ESet e = possibleExns;
146         possibleExns = ESet.getEmpty();
147         return e;
148     }
149     public void setExns(ESet e) { possibleExns = e; }
150     public ESet getExns() { return possibleExns; }
151
152     public TypeDs getCheckedExns() {
153         AST ast = getAST();
154         TypeDs ds = ast.makeTypeDs();
155         for (Iterator i = possibleExns.iterator(); i.hasNext(); ) {
156             NameType ty = (NameType) i.next();
157             if (ty.isSubtypeOf(getTypeManager().getRuntimeExceptionType())) continue;
158             if (ty.isSubtypeOf(getTypeManager().getErrorType())) continue;
159             else ds.add(ty.makeTypeD());
160         }
161         return ds;
162     }
163
164     //
165
public void setLive(boolean b) { liveFlag = b; }
166     public boolean isLive() { return liveFlag; }
167
168
169     // ------------------------------
170
// Useful vars methods
171

172     public static Vars getAllVars() { return Vars.allVars; }
173     public static Vars getNoVars() { return Vars.noVars; }
174
175     // ------------------------------
176
// error showing
177

178     java.util.Set JavaDoc errorVars = new java.util.HashSet JavaDoc();
179     public void showVarError(ASTObject o, VarDec v, String JavaDoc msg) {
180         if (! errorVars.contains(v)) {
181             o.showError(msg);
182             errorVars.add(v);
183         }
184     }
185
186     // ------------------------------
187
// control context
188

189     public ControlContext popControlContext() {
190         ControlContext c = this.context;
191         context = new ControlContext();
192         return c;
193     }
194
195     public void enterContext(Stmt s) { context.enter(s); }
196     public void leaveContext() { context.exit(); }
197
198     public boolean isLabelUsed(String JavaDoc name) {
199         return context.isLabelUsed(name);
200     }
201
202     public void doBreak(String JavaDoc label) {
203         Stmt target = context.getBreakTarget(label);
204         Vars v = getVars();
205         annotateWindsUntil(target, v);
206         annotate(breaks, target, v);
207         addPendingTransfer(true, target);
208     }
209
210     public void doContinue(String JavaDoc label) {
211         Stmt target = context.getContinueTarget(label);
212         Vars v = getVars();
213         annotateWindsUntil(target, v);
214         annotate(continues, target, v);
215         addPendingTransfer(false, target);
216     }
217
218     public void doReturn() {
219         Vars v = getVars();
220         annotateWindsUntil(null, v);
221     }
222
223     private void annotateWindsUntil(Stmt target, Vars v) {
224         for (Iterator i = context.getWindsUntil(target); i.hasNext(); ) {
225             Object JavaDoc o = i.next();
226             annotate(tries, o, v);
227         }
228     }
229
230     private Map breaks = new HashMap();
231     private Map continues = new HashMap();
232     private Map tries = new HashMap();
233     private void annotate(Map m, Object JavaDoc s, Vars v) {
234         Vars tab = (Vars) m.get(s);
235         if (tab == null) {
236             m.put(s, v);
237         } else {
238             m.put(s, tab.join(v));
239         }
240     }
241
242     public Vars getBreakVars(Stmt s) { return getVars(breaks, s); }
243     public Vars getContinueVars(Stmt s) { return getVars(continues, s); }
244     public Vars getTryVars(Stmt s) { return getVars(tries, s); }
245     private Vars getVars(Map m, Stmt s) {
246         Vars tab = (Vars) m.get(s);
247         if (tab == null) {
248             return getAllVars();
249         } else {
250             return tab;
251         }
252     }
253
254     public void checkLoopingFinals(Stmt stmt, Set pa, Vars v) {
255         // forall x in pa, x must be in v.dua
256
// in other words, pa.diff(v.dua) == empty
257
Set s = pa.diff(v.getDua());
258         while (! s.isEmpty()) {
259             VarDec dec = s.first();
260             s = s.rest();
261             showVarError(stmt, dec, "variable " + dec.getId() +
262                          " might be assigned in loop");
263         }
264     }
265
266     public static Vars buildCatchVars(Vars daHolder, Vars duaHolder) {
267         return Vars.makeSets(daHolder.getDa(), duaHolder.getDua());
268     }
269
270     // ------------------------------
271

272     // for break and continue control, we need to annotate the next
273
// try stmt up that it should 're-break' if it finds that it
274
// completes normally. This is because s: try { break s; }
275
// finally { return; } is not broken. Strangely enough, this is
276
// _just_ for control, not for variables. !!! Note that it is for
277
// exceptions also, which we don't check either. So we may want to
278
// change TryStmt to make sure that we signal an unreachable catch
279
// clause error for try {try { throw new E(); } finally { return; } }
280
// catch (E e) { ... }
281

282     private java.util.Set JavaDoc broken = new HashSet();
283     private java.util.Set JavaDoc continued = new HashSet();
284
285     public boolean isBroken(Stmt s) { return broken.contains(s); }
286     public boolean isContinued(Stmt s) { return continued.contains(s); }
287
288     // SEE
289
// http://developer.java.sun.com/developer/bugParade/bugs/4088988.html
290
// for a description of why we have all this damn verbiage here
291
// and we don't use any of it. When we want to check this kind of
292
// bug, we should comment out the below text.
293

294     public void releasePendingTransfers(TryStmt s) {
295         if (getOptions().strict) {
296             Redo l = (Redo) pendingTransfers.get(s);
297             if (l == null) return;
298             l.redo();
299         }
300     }
301
302     private Map/*<TryStmt, Redo>*/ pendingTransfers = new HashMap();
303
304     private class Redo {
305         boolean isBreak; Stmt target;
306         Redo(boolean isBreak, Stmt target) {
307             this.isBreak = isBreak; this.target = target;
308         }
309         void redo() {
310             Iterator i = context.getWindsUntil(target);
311             if (i.hasNext()) {
312                 pendingTransfers.put(i.next(), this);
313             } else {
314                 (isBreak ? broken : continued).add(target);
315             }
316         }
317     }
318
319     private void addPendingTransfer(boolean isBreak, Stmt target) {
320         if (! getOptions().strict) {
321             (isBreak ? broken : continued).add(target);
322         } else {
323             Iterator i = context.getWindsUntil(target);
324             if (i.hasNext()) {
325                 pendingTransfers.put(i.next(), new Redo(isBreak, target));
326             } else {
327                 (isBreak ? broken : continued).add(target);
328             }
329         }
330     }
331
332     // ------------------------------
333

334     public static abstract class Vars {
335         public static Vars getEmpty() { return noVars; }
336         public abstract Vars getTrue();
337         public abstract Vars getFalse();
338         public abstract Set getDa();
339         public abstract Set getDua();
340         public abstract Vars join(Vars other);
341         public abstract Vars joinUnion(Vars other);
342         public abstract Vars addAssigned(VarDec v);
343         public abstract Vars addUnassigned(VarDec v);
344         public abstract boolean isDefinitelyAssigned(VarDec dec);
345         public abstract boolean isDefinitelyUnassigned(VarDec dec);
346
347         public static Vars allVars = new Sets(Set.full, Set.full);
348         public static Vars noVars = new Sets(Set.empty, Set.empty);
349         public static Vars makePair(Vars v0, Vars v1) {
350             return new Pair(v0, v1);
351         }
352         public static Vars makeSets(Set v0, Set v1) {
353             return new Sets(v0, v1);
354         }
355
356         private static final class Pair extends Vars {
357             final Vars ifTrue, ifFalse;
358             Pair(Vars ifTrue, Vars ifFalse) {
359                 this.ifTrue = ifTrue; this.ifFalse = ifFalse;
360             }
361             public Vars getTrue() { return ifTrue; }
362             public Vars getFalse() { return ifFalse; }
363             public Set getDa() { return normalize().getDa(); }
364             public Set getDua() { return normalize().getDua(); }
365             public Vars join(Vars other) { return normalize().join(other); }
366             public Vars joinUnion(Vars other) { return normalize().joinUnion(other); }
367             public Vars addAssigned(VarDec v) { return normalize().addAssigned(v); }
368             public Vars addUnassigned(VarDec v) { return normalize().addUnassigned(v); }
369             public boolean isDefinitelyAssigned(VarDec dec) {
370                 return normalize().isDefinitelyAssigned(dec);
371             }
372             public boolean isDefinitelyUnassigned(VarDec dec) {
373                 return normalize().isDefinitelyUnassigned(dec);
374             }
375             private Vars normalForm = null;
376             private Vars normalize() {
377                 if (normalForm == null)
378                     normalForm = ifTrue.join(ifFalse);
379                 return normalForm;
380             }
381             public String JavaDoc toString() {
382                 return "<" + ifTrue + ", " + ifFalse + ">";
383             }
384         }
385
386         private static final class Sets extends Vars {
387             final Set da, dua;
388             Sets(Set da, Set dua) { this.da = da; this.dua = dua; }
389             public Vars getTrue() { return this; }
390             public Vars getFalse() { return this; }
391             public Set getDa() { return da; }
392             public Set getDua() { return dua; }
393
394             public Vars join(Vars other) {
395                 return new Sets(da.inter(other.getDa()), dua.inter(other.getDua()));
396             }
397             public Vars joinUnion(Vars other) {
398                 return new Sets(da.union(other.getDa()), dua.union(other.getDua()));
399             }
400             public Vars addAssigned(VarDec v) {
401                 return new Sets(da.add(v), dua.remove(v));
402             }
403             public Vars addUnassigned(VarDec v) {
404                 // guaranteed to be new
405
return new Sets(da, dua.add(v));
406             }
407             public boolean isDefinitelyAssigned(VarDec dec) {
408                 return da.contains(dec);
409             }
410             public boolean isDefinitelyUnassigned(VarDec dec) {
411                 return dua.contains(dec);
412             }
413             public String JavaDoc toString() {
414                 return "<" + da + ", " + dua + ">";
415             }
416         }
417     }
418
419     public static abstract class Set {
420         private static Zero empty = new Zero();
421         private static Neg full = new Neg(empty);
422         public static Set getAll() { return full; }
423         public static Set getNone() { return empty; }
424
425         public abstract Set neg();
426         public abstract Set add(VarDec v);
427         public abstract Set remove(VarDec v);
428         public abstract boolean contains(VarDec v);
429         public abstract Set union(Set s);
430         public abstract Set inter(Set s);
431         public abstract Set diff(Set s);
432         public abstract boolean isEmpty();
433         public VarDec first() { throw new RuntimeException JavaDoc("can't take first"); }
434         public NonNeg rest() { throw new RuntimeException JavaDoc("can't take first"); }
435         public String JavaDoc toStringRest() {
436             throw new RuntimeException JavaDoc("can't get rest of set");
437         }
438         public static abstract class NonNeg extends Set {
439             protected abstract Set union1(Set s);
440             protected abstract Set inter1(Set s);
441             protected abstract Set diff1(Set s);
442         }
443         private static class Zero extends NonNeg {
444             public Set neg() { return full; }
445             public Set add(VarDec v) { return new One(v, this); }
446             public Set remove(VarDec v) { return this; }
447             public boolean contains(VarDec v) { return false; }
448             public Set union(Set s) { return s; }
449             public Set inter(Set s) { return this; }
450             public Set diff(Set s) { return this; }
451             protected Set union1(Set s) { return s; }
452             protected Set inter1(Set s) { return this; }
453             protected Set diff1(Set s) { return this; }
454             public boolean isEmpty() { return true; }
455             public String JavaDoc toStringRest() { return "}"; }
456             public String JavaDoc toString() { return "{}"; }
457         }
458         private static class Neg extends Set {
459             private NonNeg x;
460             Neg(NonNeg x) { this.x = x; }
461             public Set neg() { return x; }
462             public Set add(VarDec v) { return x.remove(v).neg(); }
463             public Set remove(VarDec v) { return x.add(v).neg(); }
464             public boolean contains(VarDec v) { return ! x.contains(v); }
465             public Set union(Set s) {
466                 if (s instanceof Neg) return x.inter(s.neg()).neg();
467                 else return x.diff(s).neg();
468             }
469             public Set inter(Set s) {
470                 if (s instanceof Neg) return x.union(s.neg()).neg();
471                 else return s.diff(x);
472             }
473             public Set diff(Set s) {
474                 if (s instanceof Neg) return s.neg().diff(x);
475                 else return x.union(s).neg();
476             }
477             public boolean isEmpty() { return false; }
478             public String JavaDoc toString() { return "!" + x; }
479         }
480         private static class One extends NonNeg {
481             VarDec v;
482             NonNeg rest;
483             // note, was private, but javac 1.4 didn't like
484
One(VarDec v, NonNeg rest) { this.v = v; this.rest = rest; }
485             public Set neg() { return new Neg(this); }
486             public Set add(VarDec v) { return contains(v) ? this : new One(v, this); }
487             public Set remove(VarDec v) {
488                 return (v == this.v) ? rest : rest.remove(v).add(this.v);
489             }
490             public boolean contains(VarDec v) {
491                 return (v == this.v) || rest.contains(v);
492             }
493             public Set union(Set s) {
494                 return (s instanceof Neg) ? s.union(this) : this.union1(s);
495             }
496             public Set inter(Set s) {
497                 return (s instanceof Neg) ? s.inter(this) : this.inter1(s);
498             }
499             public Set diff(Set s) {
500                 return (s instanceof Neg) ? this.inter(s.neg()) : this.diff1(s);
501             }
502             public boolean isEmpty() { return false; }
503             public VarDec first() { return v; }
504             public NonNeg rest() { return rest; }
505
506             protected Set union1(Set s) {
507                 return s.contains(v) ? rest.union1(s) : rest.union1(s).add(v);
508             }
509             protected Set inter1(Set s) {
510                 return s.contains(v) ? rest.inter1(s).add(v) : rest.inter1(s);
511             }
512             protected Set diff1(Set s) {
513                 return s.contains(v) ? rest.diff1(s) : rest.diff1(s).add(v);
514             }
515
516             public String JavaDoc toString() { return "{" + v.getId() + rest.toStringRest(); }
517             public String JavaDoc toStringRest() {
518                 return ", " + v.getId() + rest.toStringRest();
519             }
520         }
521     }
522
523     public static abstract class ESet {
524         static ESet empty = new Null();
525         public static ESet getEmpty() { return empty; }
526         abstract ESet remove(NameType v);
527         public abstract boolean containsSuperOrSub(NameType v);
528         public abstract boolean containsSuper(NameType v);
529         public abstract ESet union(ESet s);
530         public abstract ESet diff(ESet s);
531         public Iterator iterator() {
532             return new Iterator() {
533                     private ESet e = ESet.this;
534                     public boolean hasNext() { return !(e instanceof Null); }
535                     public Object JavaDoc next() {
536                         One o = (One) e;
537                         e = o.rest;
538                         return o.v;
539                     }
540                     public void remove() {
541                         throw new UnsupportedOperationException JavaDoc();
542                     }
543                 };
544         }
545         public String JavaDoc toStringRest() {
546             throw new RuntimeException JavaDoc("can't get rest of set");
547         }
548         public ESet add(NameType v) {
549             return v.isUncheckedThrowable() ? this : this.add1(v);
550         }
551         abstract ESet add1(NameType v);
552
553         private static class Null extends ESet {
554             ESet add1(NameType v) { return new One(v, this); }
555             ESet remove(NameType v) { return this; }
556             public boolean containsSuperOrSub(NameType v) { return false; }
557             public boolean containsSuper(NameType v) { return false; }
558             public ESet union(ESet s) { return s; }
559             public ESet diff(ESet s) { return this; }
560             public boolean isEmpty() { return true; }
561             public String JavaDoc toStringRest() { return "}"; }
562             public String JavaDoc toString() { return "{}"; }
563         }
564
565         private static class One extends ESet {
566             NameType v;
567             ESet rest;
568             // note, was private, but javac 1.4 didn't like it
569
One(NameType v, ESet rest) { this.v = v; this.rest = rest; }
570             ESet add1(NameType v) { return containsSuper(v) ? this : new One(v, this); }
571             ESet remove(NameType v) {
572                 return (v == this.v) ? rest : rest.remove(v).add(this.v);
573             }
574             public boolean containsSuperOrSub(NameType v) {
575                 return v.isSubtypeOf(this.v) || this.v.isSubtypeOf(v) ||
576                     rest.containsSuperOrSub(v); }
577             public boolean containsSuper(NameType v) {
578                 return v.isSubtypeOf(this.v) || rest.containsSuper(v);
579             }
580             public ESet union(ESet s) {
581                 return s.containsSuper(v) ? rest.union(s) : rest.union(s).add(v);
582             }
583             public ESet diff(ESet s) {
584                 return s.containsSuper(v) ? rest.diff(s) : rest.diff(s).add(v);
585             }
586             public String JavaDoc toString() { return "{" + v.getId() + rest.toStringRest(); }
587             public String JavaDoc toStringRest() {
588                 return ", " + v.getId() + rest.toStringRest();
589             }
590         }
591     }
592 }
593
594 /*
595 There's a tricky bit in dealing with blank finals. That tricky bit is
596 in the looping constructs.
597
598 The basic thing for:
599
600    do S0 while E1
601    while E0 S1
602
603 is this:
604
605    If I _relied on_ some variable V being in dua to evaluate 0, and
606    later I find that after the flow of 1 V is not in dua, show an
607    error for V.
608
609 Thus, we return, conceptually TWO values from statements:
610
611   da: variables definitely assigned
612   dua: variables definitely unassigned
613
614 and save one in the state
615
616   ba: blank finals _possibly_ assigned
617
618 where ba: is _only_ checked in the checkers for loops, but it has to
619 be maintained for everyone.
620
621 A better job of this could be done by annotating loop statements with
622 bit vectors for every blank final closed over.
623
624 */

625
Popular Tags