001 /*
002 * Copyright 1999-2008 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025
026 //todo: one might eliminate uninits.andSets when monotonic
027
028 package com.sun.tools.javac.comp;
029
030 import com.sun.tools.javac.code.*;
031 import com.sun.tools.javac.tree.*;
032 import com.sun.tools.javac.util.*;
033 import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;
034
035 import com.sun.tools.javac.code.Symbol.*;
036 import com.sun.tools.javac.tree.JCTree.*;
037
038 import static com.sun.tools.javac.code.Flags.*;
039 import static com.sun.tools.javac.code.Kinds.*;
040 import static com.sun.tools.javac.code.TypeTags.*;
041
042 /** This pass implements dataflow analysis for Java programs.
043 * Liveness analysis checks that every statement is reachable.
044 * Exception analysis ensures that every checked exception that is
045 * thrown is declared or caught. Definite assignment analysis
046 * ensures that each variable is assigned when used. Definite
047 * unassignment analysis ensures that no final variable is assigned
048 * more than once.
049 *
050 * <p>The second edition of the JLS has a number of problems in the
051 * specification of these flow analysis problems. This implementation
052 * attempts to address those issues.
053 *
054 * <p>First, there is no accommodation for a finally clause that cannot
055 * complete normally. For liveness analysis, an intervening finally
056 * clause can cause a break, continue, or return not to reach its
057 * target. For exception analysis, an intervening finally clause can
058 * cause any exception to be "caught". For DA/DU analysis, the finally
059 * clause can prevent a transfer of control from propagating DA/DU
060 * state to the target. In addition, code in the finally clause can
061 * affect the DA/DU status of variables.
062 *
063 * <p>For try statements, we introduce the idea of a variable being
064 * definitely unassigned "everywhere" in a block. A variable V is
065 * "unassigned everywhere" in a block iff it is unassigned at the
066 * beginning of the block and there is no reachable assignment to V
067 * in the block. An assignment V=e is reachable iff V is not DA
068 * after e. Then we can say that V is DU at the beginning of the
069 * catch block iff V is DU everywhere in the try block. Similarly, V
070 * is DU at the beginning of the finally block iff V is DU everywhere
071 * in the try block and in every catch block. Specifically, the
072 * following bullet is added to 16.2.2
073 * <pre>
074 * V is <em>unassigned everywhere</em> in a block if it is
075 * unassigned before the block and there is no reachable
076 * assignment to V within the block.
077 * </pre>
078 * <p>In 16.2.15, the third bullet (and all of its sub-bullets) for all
079 * try blocks is changed to
080 * <pre>
081 * V is definitely unassigned before a catch block iff V is
082 * definitely unassigned everywhere in the try block.
083 * </pre>
084 * <p>The last bullet (and all of its sub-bullets) for try blocks that
085 * have a finally block is changed to
086 * <pre>
087 * V is definitely unassigned before the finally block iff
088 * V is definitely unassigned everywhere in the try block
089 * and everywhere in each catch block of the try statement.
090 * </pre>
091 * <p>In addition,
092 * <pre>
093 * V is definitely assigned at the end of a constructor iff
094 * V is definitely assigned after the block that is the body
095 * of the constructor and V is definitely assigned at every
096 * return that can return from the constructor.
097 * </pre>
098 * <p>In addition, each continue statement with the loop as its target
099 * is treated as a jump to the end of the loop body, and "intervening"
100 * finally clauses are treated as follows: V is DA "due to the
101 * continue" iff V is DA before the continue statement or V is DA at
102 * the end of any intervening finally block. V is DU "due to the
103 * continue" iff any intervening finally cannot complete normally or V
104 * is DU at the end of every intervening finally block. This "due to
105 * the continue" concept is then used in the spec for the loops.
106 *
107 * <p>Similarly, break statements must consider intervening finally
108 * blocks. For liveness analysis, a break statement for which any
109 * intervening finally cannot complete normally is not considered to
110 * cause the target statement to be able to complete normally. Then
111 * we say V is DA "due to the break" iff V is DA before the break or
112 * V is DA at the end of any intervening finally block. V is DU "due
113 * to the break" iff any intervening finally cannot complete normally
114 * or V is DU at the break and at the end of every intervening
115 * finally block. (I suspect this latter condition can be
116 * simplified.) This "due to the break" is then used in the spec for
117 * all statements that can be "broken".
118 *
119 * <p>The return statement is treated similarly. V is DA "due to a
120 * return statement" iff V is DA before the return statement or V is
121 * DA at the end of any intervening finally block. Note that we
122 * don't have to worry about the return expression because this
123 * concept is only used for construcrors.
124 *
125 * <p>There is no spec in JLS2 for when a variable is definitely
126 * assigned at the end of a constructor, which is needed for final
127 * fields (8.3.1.2). We implement the rule that V is DA at the end
128 * of the constructor iff it is DA and the end of the body of the
129 * constructor and V is DA "due to" every return of the constructor.
130 *
131 * <p>Intervening finally blocks similarly affect exception analysis. An
132 * intervening finally that cannot complete normally allows us to ignore
133 * an otherwise uncaught exception.
134 *
135 * <p>To implement the semantics of intervening finally clauses, all
136 * nonlocal transfers (break, continue, return, throw, method call that
137 * can throw a checked exception, and a constructor invocation that can
138 * thrown a checked exception) are recorded in a queue, and removed
139 * from the queue when we complete processing the target of the
140 * nonlocal transfer. This allows us to modify the queue in accordance
141 * with the above rules when we encounter a finally clause. The only
142 * exception to this [no pun intended] is that checked exceptions that
143 * are known to be caught or declared to be caught in the enclosing
144 * method are not recorded in the queue, but instead are recorded in a
145 * global variable "Set<Type> thrown" that records the type of all
146 * exceptions that can be thrown.
147 *
148 * <p>Other minor issues the treatment of members of other classes
149 * (always considered DA except that within an anonymous class
150 * constructor, where DA status from the enclosing scope is
151 * preserved), treatment of the case expression (V is DA before the
152 * case expression iff V is DA after the switch expression),
153 * treatment of variables declared in a switch block (the implied
154 * DA/DU status after the switch expression is DU and not DA for
155 * variables defined in a switch block), the treatment of boolean ?:
156 * expressions (The JLS rules only handle b and c non-boolean; the
157 * new rule is that if b and c are boolean valued, then V is
158 * (un)assigned after a?b:c when true/false iff V is (un)assigned
159 * after b when true/false and V is (un)assigned after c when
160 * true/false).
161 *
162 * <p>There is the remaining question of what syntactic forms constitute a
163 * reference to a variable. It is conventional to allow this.x on the
164 * left-hand-side to initialize a final instance field named x, yet
165 * this.x isn't considered a "use" when appearing on a right-hand-side
166 * in most implementations. Should parentheses affect what is
167 * considered a variable reference? The simplest rule would be to
168 * allow unqualified forms only, parentheses optional, and phase out
169 * support for assigning to a final field via this.x.
170 *
171 * <p><b>This is NOT part of any API supported by Sun Microsystems. If
172 * you write code that depends on this, you do so at your own risk.
173 * This code and its internal interfaces are subject to change or
174 * deletion without notice.</b>
175 */
176 public class Flow extends TreeScanner {
177 protected static final Context.Key<Flow> flowKey =
178 new Context.Key<Flow>();
179
180 private final Names names;
181 private final Log log;
182 private final Symtab syms;
183 private final Types types;
184 private final Check chk;
185 private TreeMaker make;
186 private Lint lint;
187
188 public static Flow instance(Context context) {
189 Flow instance = context.get(flowKey);
190 if (instance == null)
191 instance = new Flow(context);
192 return instance;
193 }
194
195 protected Flow(Context context) {
196 context.put(flowKey, this);
197
198 names = Names.instance(context);
199 log = Log.instance(context);
200 syms = Symtab.instance(context);
201 types = Types.instance(context);
202 chk = Check.instance(context);
203 lint = Lint.instance(context);
204 }
205
206 /** A flag that indicates whether the last statement could
207 * complete normally.
208 */
209 private boolean alive;
210
211 /** The set of definitely assigned variables.
212 */
213 Bits inits;
214
215 /** The set of definitely unassigned variables.
216 */
217 Bits uninits;
218
219 /** The set of variables that are definitely unassigned everywhere
220 * in current try block. This variable is maintained lazily; it is
221 * updated only when something gets removed from uninits,
222 * typically by being assigned in reachable code. To obtain the
223 * correct set of variables which are definitely unassigned
224 * anywhere in current try block, intersect uninitsTry and
225 * uninits.
226 */
227 Bits uninitsTry;
228
229 /** When analyzing a condition, inits and uninits are null.
230 * Instead we have:
231 */
232 Bits initsWhenTrue;
233 Bits initsWhenFalse;
234 Bits uninitsWhenTrue;
235 Bits uninitsWhenFalse;
236
237 /** A mapping from addresses to variable symbols.
238 */
239 VarSymbol[] vars;
240
241 /** The current class being defined.
242 */
243 JCClassDecl classDef;
244
245 /** The first variable sequence number in this class definition.
246 */
247 int firstadr;
248
249 /** The next available variable sequence number.
250 */
251 int nextadr;
252
253 /** The list of possibly thrown declarable exceptions.
254 */
255 List<Type> thrown;
256
257 /** The list of exceptions that are either caught or declared to be
258 * thrown.
259 */
260 List<Type> caught;
261
262 /** Set when processing a loop body the second time for DU analysis. */
263 boolean loopPassTwo = false;
264
265 /*-------------------- Environments ----------------------*/
266
267 /** A pending exit. These are the statements return, break, and
268 * continue. In addition, exception-throwing expressions or
269 * statements are put here when not known to be caught. This
270 * will typically result in an error unless it is within a
271 * try-finally whose finally block cannot complete normally.
272 */
273 static class PendingExit {
274 JCTree tree;
275 Bits inits;
276 Bits uninits;
277 Type thrown;
278 PendingExit(JCTree tree, Bits inits, Bits uninits) {
279 this.tree = tree;
280 this.inits = inits.dup();
281 this.uninits = uninits.dup();
282 }
283 PendingExit(JCTree tree, Type thrown) {
284 this.tree = tree;
285 this.thrown = thrown;
286 }
287 }
288
289 /** The currently pending exits that go from current inner blocks
290 * to an enclosing block, in source order.
291 */
292 ListBuffer<PendingExit> pendingExits;
293
294 /*-------------------- Exceptions ----------------------*/
295
296 /** Complain that pending exceptions are not caught.
297 */
298 void errorUncaught() {
299 for (PendingExit exit = pendingExits.next();
300 exit != null;
301 exit = pendingExits.next()) {
302 boolean synthetic = classDef != null &&
303 classDef.pos == exit.tree.pos;
304 log.error(exit.tree.pos(),
305 synthetic
306 ? "unreported.exception.default.constructor"
307 : "unreported.exception.need.to.catch.or.throw",
308 exit.thrown);
309 }
310 }
311
312 /** Record that exception is potentially thrown and check that it
313 * is caught.
314 */
315 void markThrown(JCTree tree, Type exc) {
316 if (!chk.isUnchecked(tree.pos(), exc)) {
317 if (!chk.isHandled(exc, caught))
318 pendingExits.append(new PendingExit(tree, exc));
319 thrown = chk.incl(exc, thrown);
320 }
321 }
322
323 /*-------------- Processing variables ----------------------*/
324
325 /** Do we need to track init/uninit state of this symbol?
326 * I.e. is symbol either a local or a blank final variable?
327 */
328 boolean trackable(VarSymbol sym) {
329 return
330 (sym.owner.kind == MTH ||
331 ((sym.flags() & (FINAL | HASINIT | PARAMETER)) == FINAL &&
332 classDef.sym.isEnclosedBy((ClassSymbol)sym.owner)));
333 }
334
335 /** Initialize new trackable variable by setting its address field
336 * to the next available sequence number and entering it under that
337 * index into the vars array.
338 */
339 void newVar(VarSymbol sym) {
340 if (nextadr == vars.length) {
341 VarSymbol[] newvars = new VarSymbol[nextadr * 2];
342 System.arraycopy(vars, 0, newvars, 0, nextadr);
343 vars = newvars;
344 }
345 sym.adr = nextadr;
346 vars[nextadr] = sym;
347 inits.excl(nextadr);
348 uninits.incl(nextadr);
349 nextadr++;
350 }
351
352 /** Record an initialization of a trackable variable.
353 */
354 void letInit(DiagnosticPosition pos, VarSymbol sym) {
355 if (sym.adr >= firstadr && trackable(sym)) {
356 if ((sym.flags() & FINAL) != 0) {
357 if ((sym.flags() & PARAMETER) != 0) {
358 log.error(pos, "final.parameter.may.not.be.assigned",
359 sym);
360 } else if (!uninits.isMember(sym.adr)) {
361 log.error(pos,
362 loopPassTwo
363 ? "var.might.be.assigned.in.loop"
364 : "var.might.already.be.assigned",
365 sym);
366 } else if (!inits.isMember(sym.adr)) {
367 // reachable assignment
368 uninits.excl(sym.adr);
369 uninitsTry.excl(sym.adr);
370 } else {
371 //log.rawWarning(pos, "unreachable assignment");//DEBUG
372 uninits.excl(sym.adr);
373 }
374 }
375 inits.incl(sym.adr);
376 } else if ((sym.flags() & FINAL) != 0) {
377 log.error(pos, "var.might.already.be.assigned", sym);
378 }
379 }
380
381 /** If tree is either a simple name or of the form this.name or
382 * C.this.name, and tree represents a trackable variable,
383 * record an initialization of the variable.
384 */
385 void letInit(JCTree tree) {
386 tree = TreeInfo.skipParens(tree);
387 if (tree.getTag() == JCTree.IDENT || tree.getTag() == JCTree.SELECT) {
388 Symbol sym = TreeInfo.symbol(tree);
389 letInit(tree.pos(), (VarSymbol)sym);
390 }
391 }
392
393 /** Check that trackable variable is initialized.
394 */
395 void checkInit(DiagnosticPosition pos, VarSymbol sym) {
396 if ((sym.adr >= firstadr || sym.owner.kind != TYP) &&
397 trackable(sym) &&
398 !inits.isMember(sym.adr)) {
399 log.error(pos, "var.might.not.have.been.initialized",
400 sym);
401 inits.incl(sym.adr);
402 }
403 }
404
405 /*-------------------- Handling jumps ----------------------*/
406
407 /** Record an outward transfer of control. */
408 void recordExit(JCTree tree) {
409 pendingExits.append(new PendingExit(tree, inits, uninits));
410 markDead();
411 }
412
413 /** Resolve all breaks of this statement. */
414 boolean resolveBreaks(JCTree tree,
415 ListBuffer<PendingExit> oldPendingExits) {
416 boolean result = false;
417 List<PendingExit> exits = pendingExits.toList();
418 pendingExits = oldPendingExits;
419 for (; exits.nonEmpty(); exits = exits.tail) {
420 PendingExit exit = exits.head;
421 if (exit.tree.getTag() == JCTree.BREAK &&
422 ((JCBreak) exit.tree).target == tree) {
423 inits.andSet(exit.inits);
424 uninits.andSet(exit.uninits);
425 result = true;
426 } else {
427 pendingExits.append(exit);
428 }
429 }
430 return result;
431 }
432
433 /** Resolve all continues of this statement. */
434 boolean resolveContinues(JCTree tree) {
435 boolean result = false;
436 List<PendingExit> exits = pendingExits.toList();
437 pendingExits = new ListBuffer<PendingExit>();
438 for (; exits.nonEmpty(); exits = exits.tail) {
439 PendingExit exit = exits.head;
440 if (exit.tree.getTag() == JCTree.CONTINUE &&
441 ((JCContinue) exit.tree).target == tree) {
442 inits.andSet(exit.inits);
443 uninits.andSet(exit.uninits);
444 result = true;
445 } else {
446 pendingExits.append(exit);
447 }
448 }
449 return result;
450 }
451
452 /** Record that statement is unreachable.
453 */
454 void markDead() {
455 inits.inclRange(firstadr, nextadr);
456 uninits.inclRange(firstadr, nextadr);
457 alive = false;
458 }
459
460 /** Split (duplicate) inits/uninits into WhenTrue/WhenFalse sets
461 */
462 void split() {
463 initsWhenFalse = inits.dup();
464 uninitsWhenFalse = uninits.dup();
465 initsWhenTrue = inits;
466 uninitsWhenTrue = uninits;
467 inits = uninits = null;
468 }
469
470 /** Merge (intersect) inits/uninits from WhenTrue/WhenFalse sets.
471 */
472 void merge() {
473 inits = initsWhenFalse.andSet(initsWhenTrue);
474 uninits = uninitsWhenFalse.andSet(uninitsWhenTrue);
475 }
476
477 /* ************************************************************************
478 * Visitor methods for statements and definitions
479 *************************************************************************/
480
481 /** Analyze a definition.
482 */
483 void scanDef(JCTree tree) {
484 scanStat(tree);
485 if (tree != null && tree.getTag() == JCTree.BLOCK && !alive) {
486 log.error(tree.pos(),
487 "initializer.must.be.able.to.complete.normally");
488 }
489 }
490
491 /** Analyze a statement. Check that statement is reachable.
492 */
493 void scanStat(JCTree tree) {
494 if (!alive && tree != null) {
495 log.error(tree.pos(), "unreachable.stmt");
496 if (tree.getTag() != JCTree.SKIP) alive = true;
497 }
498 scan(tree);
499 }
500
501 /** Analyze list of statements.
502 */
503 void scanStats(List<? extends JCStatement> trees) {
504 if (trees != null)
505 for (List<? extends JCStatement> l = trees; l.nonEmpty(); l = l.tail)
506 scanStat(l.head);
507 }
508
509 /** Analyze an expression. Make sure to set (un)inits rather than
510 * (un)initsWhenTrue(WhenFalse) on exit.
511 */
512 void scanExpr(JCTree tree) {
513 if (tree != null) {
514 scan(tree);
515 if (inits == null) merge();
516 }
517 }
518
519 /** Analyze a list of expressions.
520 */
521 void scanExprs(List<? extends JCExpression> trees) {
522 if (trees != null)
523 for (List<? extends JCExpression> l = trees; l.nonEmpty(); l = l.tail)
524 scanExpr(l.head);
525 }
526
527 /** Analyze a condition. Make sure to set (un)initsWhenTrue(WhenFalse)
528 * rather than (un)inits on exit.
529 */
530 void scanCond(JCTree tree) {
531 if (tree.type.isFalse()) {
532 if (inits == null) merge();
533 initsWhenTrue = inits.dup();
534 initsWhenTrue.inclRange(firstadr, nextadr);
535 uninitsWhenTrue = uninits.dup();
536 uninitsWhenTrue.inclRange(firstadr, nextadr);
537 initsWhenFalse = inits;
538 uninitsWhenFalse = uninits;
539 } else if (tree.type.isTrue()) {
540 if (inits == null) merge();
541 initsWhenFalse = inits.dup();
542 initsWhenFalse.inclRange(firstadr, nextadr);
543 uninitsWhenFalse = uninits.dup();
544 uninitsWhenFalse.inclRange(firstadr, nextadr);
545 initsWhenTrue = inits;
546 uninitsWhenTrue = uninits;
547 } else {
548 scan(tree);
549 if (inits != null) split();
550 }
551 inits = uninits = null;
552 }
553
554 /* ------------ Visitor methods for various sorts of trees -------------*/
555
556 public void visitClassDef(JCClassDecl tree) {
557 if (tree.sym == null) return;
558
559 JCClassDecl classDefPrev = classDef;
560 List<Type> thrownPrev = thrown;
561 List<Type> caughtPrev = caught;
562 boolean alivePrev = alive;
563 int firstadrPrev = firstadr;
564 int nextadrPrev = nextadr;
565 ListBuffer<PendingExit> pendingExitsPrev = pendingExits;
566 Lint lintPrev = lint;
567
568 pendingExits = new ListBuffer<PendingExit>();
569 if (tree.name != names.empty) {
570 caught = List.nil();
571 firstadr = nextadr;
572 }
573 classDef = tree;
574 thrown = List.nil();
575 lint = lint.augment(tree.sym.attributes_field);
576
577 try {
578 // define all the static fields
579 for (List<JCTree> l = tree.defs; l.nonEmpty(); l = l.tail) {
580 if (l.head.getTag() == JCTree.VARDEF) {
581 JCVariableDecl def = (JCVariableDecl)l.head;
582 if ((def.mods.flags & STATIC) != 0) {
583 VarSymbol sym = def.sym;
584 if (trackable(sym))
585 newVar(sym);
586 }
587 }
588 }
589
590 // process all the static initializers
591 for (List<JCTree> l = tree.defs; l.nonEmpty(); l = l.tail) {
592 if (l.head.getTag() != JCTree.METHODDEF &&
593 (TreeInfo.flags(l.head) & STATIC) != 0) {
594 scanDef(l.head);
595 errorUncaught();
596 }
597 }
598
599 // add intersection of all thrown clauses of initial constructors
600 // to set of caught exceptions, unless class is anonymous.
601 if (tree.name != names.empty) {
602 boolean firstConstructor = true;
603 for (List<JCTree> l = tree.defs; l.nonEmpty(); l = l.tail) {
604 if (TreeInfo.isInitialConstructor(l.head)) {
605 List<Type> mthrown =
606 ((JCMethodDecl) l.head).sym.type.getThrownTypes();
607 if (firstConstructor) {
608 caught = mthrown;
609 firstConstructor = false;
610 } else {
611 caught = chk.intersect(mthrown, caught);
612 }
613 }
614 }
615 }
616
617 // define all the instance fields
618 for (List<JCTree> l = tree.defs; l.nonEmpty(); l = l.tail) {
619 if (l.head.getTag() == JCTree.VARDEF) {
620 JCVariableDecl def = (JCVariableDecl)l.head;
621 if ((def.mods.flags & STATIC) == 0) {
622 VarSymbol sym = def.sym;
623 if (trackable(sym))
624 newVar(sym);
625 }
626 }
627 }
628
629 // process all the instance initializers
630 for (List<JCTree> l = tree.defs; l.nonEmpty(); l = l.tail) {
631 if (l.head.getTag() != JCTree.METHODDEF &&
632 (TreeInfo.flags(l.head) & STATIC) == 0) {
633 scanDef(l.head);
634 errorUncaught();
635 }
636 }
637
638 // in an anonymous class, add the set of thrown exceptions to
639 // the throws clause of the synthetic constructor and propagate
640 // outwards.
641 if (tree.name == names.empty) {
642 for (List<JCTree> l = tree.defs; l.nonEmpty(); l = l.tail) {
643 if (TreeInfo.isInitialConstructor(l.head)) {
644 JCMethodDecl mdef = (JCMethodDecl)l.head;
645 mdef.thrown = make.Types(thrown);
646 mdef.sym.type.setThrown(thrown);
647 }
648 }
649 thrownPrev = chk.union(thrown, thrownPrev);
650 }
651
652 // process all the methods
653 for (List<JCTree> l = tree.defs; l.nonEmpty(); l = l.tail) {
654 if (l.head.getTag() == JCTree.METHODDEF) {
655 scan(l.head);
656 errorUncaught();
657 }
658 }
659
660 thrown = thrownPrev;
661 } finally {
662 pendingExits = pendingExitsPrev;
663 alive = alivePrev;
664 nextadr = nextadrPrev;
665 firstadr = firstadrPrev;
666 caught = caughtPrev;
667 classDef = classDefPrev;
668 lint = lintPrev;
669 }
670 }
671
672 public void visitMethodDef(JCMethodDecl tree) {
673 if (tree.body == null) return;
674
675 List<Type> caughtPrev = caught;
676 List<Type> mthrown = tree.sym.type.getThrownTypes();
677 Bits initsPrev = inits.dup();
678 Bits uninitsPrev = uninits.dup();
679 int nextadrPrev = nextadr;
680 int firstadrPrev = firstadr;
681 Lint lintPrev = lint;
682
683 lint = lint.augment(tree.sym.attributes_field);
684
685 assert pendingExits.isEmpty();
686
687 try {
688 boolean isInitialConstructor =
689 TreeInfo.isInitialConstructor(tree);
690
691 if (!isInitialConstructor)
692 firstadr = nextadr;
693 for (List<JCVariableDecl> l = tree.params; l.nonEmpty(); l = l.tail) {
694 JCVariableDecl def = l.head;
695 scan(def);
696 inits.incl(def.sym.adr);
697 uninits.excl(def.sym.adr);
698 }
699 if (isInitialConstructor)
700 caught = chk.union(caught, mthrown);
701 else if ((tree.sym.flags() & (BLOCK | STATIC)) != BLOCK)
702 caught = mthrown;
703 // else we are in an instance initializer block;
704 // leave caught unchanged.
705
706 alive = true;
707 scanStat(tree.body);
708
709 if (alive && tree.sym.type.getReturnType().tag != VOID)
710 log.error(TreeInfo.diagEndPos(tree.body), "missing.ret.stmt");
711
712 if (isInitialConstructor) {
713 for (int i = firstadr; i < nextadr; i++)
714 if (vars[i].owner == classDef.sym)
715 checkInit(TreeInfo.diagEndPos(tree.body), vars[i]);
716 }
717 List<PendingExit> exits = pendingExits.toList();
718 pendingExits = new ListBuffer<PendingExit>();
719 while (exits.nonEmpty()) {
720 PendingExit exit = exits.head;
721 exits = exits.tail;
722 if (exit.thrown == null) {
723 assert exit.tree.getTag() == JCTree.RETURN;
724 if (isInitialConstructor) {
725 inits = exit.inits;
726 for (int i = firstadr; i < nextadr; i++)
727 checkInit(exit.tree.pos(), vars[i]);
728 }
729 } else {
730 // uncaught throws will be reported later
731 pendingExits.append(exit);
732 }
733 }
734 } finally {
735 inits = initsPrev;
736 uninits = uninitsPrev;
737 nextadr = nextadrPrev;
738 firstadr = firstadrPrev;
739 caught = caughtPrev;
740 lint = lintPrev;
741 }
742 }
743
744 public void visitVarDef(JCVariableDecl tree) {
745 boolean track = trackable(tree.sym);
746 if (track && tree.sym.owner.kind == MTH) newVar(tree.sym);
747 if (tree.init != null) {
748 Lint lintPrev = lint;
749 lint = lint.augment(tree.sym.attributes_field);
750 try{
751 scanExpr(tree.init);
752 if (track) letInit(tree.pos(), tree.sym);
753 } finally {
754 lint = lintPrev;
755 }
756 }
757 }
758
759 public void visitBlock(JCBlock tree) {
760 int nextadrPrev = nextadr;
761 scanStats(tree.stats);
762 nextadr = nextadrPrev;
763 }
764
765 public void visitDoLoop(JCDoWhileLoop tree) {
766 ListBuffer<PendingExit> prevPendingExits = pendingExits;
767 boolean prevLoopPassTwo = loopPassTwo;
768 pendingExits = new ListBuffer<PendingExit>();
769 do {
770 Bits uninitsEntry = uninits.dup();
771 scanStat(tree.body);
772 alive |= resolveContinues(tree);
773 scanCond(tree.cond);
774 if (log.nerrors != 0 ||
775 loopPassTwo ||
776 uninitsEntry.diffSet(uninitsWhenTrue).nextBit(firstadr)==-1)
777 break;
778 inits = initsWhenTrue;
779 uninits = uninitsEntry.andSet(uninitsWhenTrue);
780 loopPassTwo = true;
781 alive = true;
782 } while (true);
783 loopPassTwo = prevLoopPassTwo;
784 inits = initsWhenFalse;
785 uninits = uninitsWhenFalse;
786 alive = alive && !tree.cond.type.isTrue();
787 alive |= resolveBreaks(tree, prevPendingExits);
788 }
789
790 public void visitWhileLoop(JCWhileLoop tree) {
791 ListBuffer<PendingExit> prevPendingExits = pendingExits;
792 boolean prevLoopPassTwo = loopPassTwo;
793 Bits initsCond;
794 Bits uninitsCond;
795 pendingExits = new ListBuffer<PendingExit>();
796 do {
797 Bits uninitsEntry = uninits.dup();
798 scanCond(tree.cond);
799 initsCond = initsWhenFalse;
800 uninitsCond = uninitsWhenFalse;
801 inits = initsWhenTrue;
802 uninits = uninitsWhenTrue;
803 alive = !tree.cond.type.isFalse();
804 scanStat(tree.body);
805 alive |= resolveContinues(tree);
806 if (log.nerrors != 0 ||
807 loopPassTwo ||
808 uninitsEntry.diffSet(uninits).nextBit(firstadr) == -1)
809 break;
810 uninits = uninitsEntry.andSet(uninits);
811 loopPassTwo = true;
812 alive = true;
813 } while (true);
814 loopPassTwo = prevLoopPassTwo;
815 inits = initsCond;
816 uninits = uninitsCond;
817 alive = resolveBreaks(tree, prevPendingExits) ||
818 !tree.cond.type.isTrue();
819 }
820
821 public void visitForLoop(JCForLoop tree) {
822 ListBuffer<PendingExit> prevPendingExits = pendingExits;
823 boolean prevLoopPassTwo = loopPassTwo;
824 int nextadrPrev = nextadr;
825 scanStats(tree.init);
826 Bits initsCond;
827 Bits uninitsCond;
828 pendingExits = new ListBuffer<PendingExit>();
829 do {
830 Bits uninitsEntry = uninits.dup();
831 if (tree.cond != null) {
832 scanCond(tree.cond);
833 initsCond = initsWhenFalse;
834 uninitsCond = uninitsWhenFalse;
835 inits = initsWhenTrue;
836 uninits = uninitsWhenTrue;
837 alive = !tree.cond.type.isFalse();
838 } else {
839 initsCond = inits.dup();
840 initsCond.inclRange(firstadr, nextadr);
841 uninitsCond = uninits.dup();
842 uninitsCond.inclRange(firstadr, nextadr);
843 alive = true;
844 }
845 scanStat(tree.body);
846 alive |= resolveContinues(tree);
847 scan(tree.step);
848 if (log.nerrors != 0 ||
849 loopPassTwo ||
850 uninitsEntry.dup().diffSet(uninits).nextBit(firstadr) == -1)
851 break;
852 uninits = uninitsEntry.andSet(uninits);
853 loopPassTwo = true;
854 alive = true;
855 } while (true);
856 loopPassTwo = prevLoopPassTwo;
857 inits = initsCond;
858 uninits = uninitsCond;
859 alive = resolveBreaks(tree, prevPendingExits) ||
860 tree.cond != null && !tree.cond.type.isTrue();
861 nextadr = nextadrPrev;
862 }
863
864 public void visitForeachLoop(JCEnhancedForLoop tree) {
865 visitVarDef(tree.var);
866
867 ListBuffer<PendingExit> prevPendingExits = pendingExits;
868 boolean prevLoopPassTwo = loopPassTwo;
869 int nextadrPrev = nextadr;
870 scan(tree.expr);
871 Bits initsStart = inits.dup();
872 Bits uninitsStart = uninits.dup();
873
874 letInit(tree.pos(), tree.var.sym);
875 pendingExits = new ListBuffer<PendingExit>();
876 do {
877 Bits uninitsEntry = uninits.dup();
878 scanStat(tree.body);
879 alive |= resolveContinues(tree);
880 if (log.nerrors != 0 ||
881 loopPassTwo ||
882 uninitsEntry.diffSet(uninits).nextBit(firstadr) == -1)
883 break;
884 uninits = uninitsEntry.andSet(uninits);
885 loopPassTwo = true;
886 alive = true;
887 } while (true);
888 loopPassTwo = prevLoopPassTwo;
889 inits = initsStart;
890 uninits = uninitsStart.andSet(uninits);
891 resolveBreaks(tree, prevPendingExits);
892 alive = true;
893 nextadr = nextadrPrev;
894 }
895
896 public void visitLabelled(JCLabeledStatement tree) {
897 ListBuffer<PendingExit> prevPendingExits = pendingExits;
898 pendingExits = new ListBuffer<PendingExit>();
899 scanStat(tree.body);
900 alive |= resolveBreaks(tree, prevPendingExits);
901 }
902
903 public void visitSwitch(JCSwitch tree) {
904 ListBuffer<PendingExit> prevPendingExits = pendingExits;
905 pendingExits = new ListBuffer<PendingExit>();
906 int nextadrPrev = nextadr;
907 scanExpr(tree.selector);
908 Bits initsSwitch = inits;
909 Bits uninitsSwitch = uninits.dup();
910 boolean hasDefault = false;
911 for (List<JCCase> l = tree.cases; l.nonEmpty(); l = l.tail) {
912 alive = true;
913 inits = initsSwitch.dup();
914 uninits = uninits.andSet(uninitsSwitch);
915 JCCase c = l.head;
916 if (c.pat == null)
917 hasDefault = true;
918 else
919 scanExpr(c.pat);
920 scanStats(c.stats);
921 addVars(c.stats, initsSwitch, uninitsSwitch);
922 // Warn about fall-through if lint switch fallthrough enabled.
923 if (!loopPassTwo &&
924 alive &&
925 lint.isEnabled(Lint.LintCategory.FALLTHROUGH) &&
926 c.stats.nonEmpty() && l.tail.nonEmpty())
927 log.warning(l.tail.head.pos(),
928 "possible.fall-through.into.case");
929 }
930 if (!hasDefault) {
931 inits.andSet(initsSwitch);
932 alive = true;
933 }
934 alive |= resolveBreaks(tree, prevPendingExits);
935 nextadr = nextadrPrev;
936 }
937 // where
938 /** Add any variables defined in stats to inits and uninits. */
939 private static void addVars(List<JCStatement> stats, Bits inits,
940 Bits uninits) {
941 for (;stats.nonEmpty(); stats = stats.tail) {
942 JCTree stat = stats.head;
943 if (stat.getTag() == JCTree.VARDEF) {
944 int adr = ((JCVariableDecl) stat).sym.adr;
945 inits.excl(adr);
946 uninits.incl(adr);
947 }
948 }
949 }
950
951 public void visitTry(JCTry tree) {
952 List<Type> caughtPrev = caught;
953 List<Type> thrownPrev = thrown;
954 thrown = List.nil();
955 for (List<JCCatch> l = tree.catchers; l.nonEmpty(); l = l.tail)
956 caught = chk.incl(l.head.param.type, caught);
957 Bits uninitsTryPrev = uninitsTry;
958 ListBuffer<PendingExit> prevPendingExits = pendingExits;
959 pendingExits = new ListBuffer<PendingExit>();
960 Bits initsTry = inits.dup();
961 uninitsTry = uninits.dup();
962 scanStat(tree.body);
963 List<Type> thrownInTry = thrown;
964 thrown = thrownPrev;
965 caught = caughtPrev;
966 boolean aliveEnd = alive;
967 uninitsTry.andSet(uninits);
968 Bits initsEnd = inits;
969 Bits uninitsEnd = uninits;
970 int nextadrCatch = nextadr;
971
972 List<Type> caughtInTry = List.nil();
973 for (List<JCCatch> l = tree.catchers; l.nonEmpty(); l = l.tail) {
974 alive = true;
975 JCVariableDecl param = l.head.param;
976 Type exc = param.type;
977 if (chk.subset(exc, caughtInTry)) {
978 log.error(l.head.pos(),
979 "except.already.caught", exc);
980 } else if (!chk.isUnchecked(l.head.pos(), exc) &&
981 exc.tsym != syms.throwableType.tsym &&
982 exc.tsym != syms.exceptionType.tsym &&
983 !chk.intersects(exc, thrownInTry)) {
984 log.error(l.head.pos(),
985 "except.never.thrown.in.try", exc);
986 }
987 caughtInTry = chk.incl(exc, caughtInTry);
988 inits = initsTry.dup();
989 uninits = uninitsTry.dup();
990 scan(param);
991 inits.incl(param.sym.adr);
992 uninits.excl(param.sym.adr);
993 scanStat(l.head.body);
994 initsEnd.andSet(inits);
995 uninitsEnd.andSet(uninits);
996 nextadr = nextadrCatch;
997 aliveEnd |= alive;
998 }
999 if (tree.finalizer != null) {
1000 List<Type> savedThrown = thrown;
1001 thrown = List.nil();
1002 inits = initsTry.dup();
1003 uninits = uninitsTry.dup();
1004 ListBuffer<PendingExit> exits = pendingExits;
1005 pendingExits = prevPendingExits;
1006 alive = true;
1007 scanStat(tree.finalizer);
1008 if (!alive) {
1009 // discard exits and exceptions from try and finally
1010 thrown = chk.union(thrown, thrownPrev);
1011 if (!loopPassTwo &&
1012 lint.isEnabled(Lint.LintCategory.FINALLY)) {
1013 log.warning(TreeInfo.diagEndPos(tree.finalizer),
1014 "finally.cannot.complete");
1015 }
1016 } else {
1017 thrown = chk.union(thrown, chk.diff(thrownInTry, caughtInTry));
1018 thrown = chk.union(thrown, savedThrown);
1019 uninits.andSet(uninitsEnd);
1020 // FIX: this doesn't preserve source order of exits in catch
1021 // versus finally!
1022 while (exits.nonEmpty()) {
1023 PendingExit exit = exits.next();
1024 if (exit.inits != null) {
1025 exit.inits.orSet(inits);
1026 exit.uninits.andSet(uninits);
1027 }
1028 pendingExits.append(exit);
1029 }
1030 inits.orSet(initsEnd);
1031 alive = aliveEnd;
1032 }
1033 } else {
1034 thrown = chk.union(thrown, chk.diff(thrownInTry, caughtInTry));
1035 inits = initsEnd;
1036 uninits = uninitsEnd;
1037 alive = aliveEnd;
1038 ListBuffer<PendingExit> exits = pendingExits;
1039 pendingExits = prevPendingExits;
1040 while (exits.nonEmpty()) pendingExits.append(exits.next());
1041 }
1042 uninitsTry.andSet(uninitsTryPrev).andSet(uninits);
1043 }
1044
1045 public void visitConditional(JCConditional tree) {
1046 scanCond(tree.cond);
1047 Bits initsBeforeElse = initsWhenFalse;
1048 Bits uninitsBeforeElse = uninitsWhenFalse;
1049 inits = initsWhenTrue;
1050 uninits = uninitsWhenTrue;
1051 if (tree.truepart.type.tag == BOOLEAN &&
1052 tree.falsepart.type.tag == BOOLEAN) {
1053 // if b and c are boolean valued, then
1054 // v is (un)assigned after a?b:c when true iff
1055 // v is (un)assigned after b when true and
1056 // v is (un)assigned after c when true
1057 scanCond(tree.truepart);
1058 Bits initsAfterThenWhenTrue = initsWhenTrue.dup();
1059 Bits initsAfterThenWhenFalse = initsWhenFalse.dup();
1060 Bits uninitsAfterThenWhenTrue = uninitsWhenTrue.dup();
1061 Bits uninitsAfterThenWhenFalse = uninitsWhenFalse.dup();
1062 inits = initsBeforeElse;
1063 uninits = uninitsBeforeElse;
1064 scanCond(tree.falsepart);
1065 initsWhenTrue.andSet(initsAfterThenWhenTrue);
1066 initsWhenFalse.andSet(initsAfterThenWhenFalse);
1067 uninitsWhenTrue.andSet(uninitsAfterThenWhenTrue);
1068 uninitsWhenFalse.andSet(uninitsAfterThenWhenFalse);
1069 } else {
1070 scanExpr(tree.truepart);
1071 Bits initsAfterThen = inits.dup();
1072 Bits uninitsAfterThen = uninits.dup();
1073 inits = initsBeforeElse;
1074 uninits = uninitsBeforeElse;
1075 scanExpr(tree.falsepart);
1076 inits.andSet(initsAfterThen);
1077 uninits.andSet(uninitsAfterThen);
1078 }
1079 }
1080
1081 public void visitIf(JCIf tree) {
1082 scanCond(tree.cond);
1083 Bits initsBeforeElse = initsWhenFalse;
1084 Bits uninitsBeforeElse = uninitsWhenFalse;
1085 inits = initsWhenTrue;
1086 uninits = uninitsWhenTrue;
1087 scanStat(tree.thenpart);
1088 if (tree.elsepart != null) {
1089 boolean aliveAfterThen = alive;
1090 alive = true;
1091 Bits initsAfterThen = inits.dup();
1092 Bits uninitsAfterThen = uninits.dup();
1093 inits = initsBeforeElse;
1094 uninits = uninitsBeforeElse;
1095 scanStat(tree.elsepart);
1096 inits.andSet(initsAfterThen);
1097 uninits.andSet(uninitsAfterThen);
1098 alive = alive | aliveAfterThen;
1099 } else {
1100 inits.andSet(initsBeforeElse);
1101 uninits.andSet(uninitsBeforeElse);
1102 alive = true;
1103 }
1104 }
1105
1106
1107
1108 public void visitBreak(JCBreak tree) {
1109 recordExit(tree);
1110 }
1111
1112 public void visitContinue(JCContinue tree) {
1113 recordExit(tree);
1114 }
1115
1116 public void visitReturn(JCReturn tree) {
1117 scanExpr(tree.expr);
1118 // if not initial constructor, should markDead instead of recordExit
1119 recordExit(tree);
1120 }
1121
1122 public void visitThrow(JCThrow tree) {
1123 scanExpr(tree.expr);
1124 markThrown(tree, tree.expr.type);
1125 markDead();
1126 }
1127
1128 public void visitApply(JCMethodInvocation tree) {
1129 scanExpr(tree.meth);
1130 scanExprs(tree.args);
1131 for (List<Type> l = tree.meth.type.getThrownTypes(); l.nonEmpty(); l = l.tail)
1132 markThrown(tree, l.head);
1133 }
1134
1135 public void visitNewClass(JCNewClass tree) {
1136 scanExpr(tree.encl);
1137 scanExprs(tree.args);
1138 // scan(tree.def);
1139 for (List<Type> l = tree.constructorType.getThrownTypes();
1140 l.nonEmpty();
1141 l = l.tail) {
1142 markThrown(tree, l.head);
1143 }
1144 List<Type> caughtPrev = caught;
1145 try {
1146 // If the new class expression defines an anonymous class,
1147 // analysis of the anonymous constructor may encounter thrown
1148 // types which are unsubstituted type variables.
1149 // However, since the constructor's actual thrown types have
1150 // already been marked as thrown, it is safe to simply include
1151 // each of the constructor's formal thrown types in the set of
1152 // 'caught/declared to be thrown' types, for the duration of
1153 // the class def analysis.
1154 if (tree.def != null)
1155 for (List<Type> l = tree.constructor.type.getThrownTypes();
1156 l.nonEmpty();
1157 l = l.tail) {
1158 caught = chk.incl(l.head, caught);
1159 }
1160 scan(tree.def);
1161 }
1162 finally {
1163 caught = caughtPrev;
1164 }
1165 }
1166
1167 public void visitNewArray(JCNewArray tree) {
1168 scanExprs(tree.dims);
1169 scanExprs(tree.elems);
1170 }
1171
1172 public void visitAssert(JCAssert tree) {
1173 Bits initsExit = inits.dup();
1174 Bits uninitsExit = uninits.dup();
1175 scanCond(tree.cond);
1176 uninitsExit.andSet(uninitsWhenTrue);
1177 if (tree.detail != null) {
1178 inits = initsWhenFalse;
1179 uninits = uninitsWhenFalse;
1180 scanExpr(tree.detail);
1181 }
1182 inits = initsExit;
1183 uninits = uninitsExit;
1184 }
1185
1186 public void visitAssign(JCAssign tree) {
1187 JCTree lhs = TreeInfo.skipParens(tree.lhs);
1188 if (!(lhs instanceof JCIdent)) scanExpr(lhs);
1189 scanExpr(tree.rhs);
1190 letInit(lhs);
1191 }
1192
1193 public void visitAssignop(JCAssignOp tree) {
1194 scanExpr(tree.lhs);
1195 scanExpr(tree.rhs);
1196 letInit(tree.lhs);
1197 }
1198
1199 public void visitUnary(JCUnary tree) {
1200 switch (tree.getTag()) {
1201 case JCTree.NOT:
1202 scanCond(tree.arg);
1203 Bits t = initsWhenFalse;
1204 initsWhenFalse = initsWhenTrue;
1205 initsWhenTrue = t;
1206 t = uninitsWhenFalse;
1207 uninitsWhenFalse = uninitsWhenTrue;
1208 uninitsWhenTrue = t;
1209 break;
1210 case JCTree.PREINC: case JCTree.POSTINC:
1211 case JCTree.PREDEC: case JCTree.POSTDEC:
1212 scanExpr(tree.arg);
1213 letInit(tree.arg);
1214 break;
1215 default:
1216 scanExpr(tree.arg);
1217 }
1218 }
1219
1220 public void visitBinary(JCBinary tree) {
1221 switch (tree.getTag()) {
1222 case JCTree.AND:
1223 scanCond(tree.lhs);
1224 Bits initsWhenFalseLeft = initsWhenFalse;
1225 Bits uninitsWhenFalseLeft = uninitsWhenFalse;
1226 inits = initsWhenTrue;
1227 uninits = uninitsWhenTrue;
1228 scanCond(tree.rhs);
1229 initsWhenFalse.andSet(initsWhenFalseLeft);
1230 uninitsWhenFalse.andSet(uninitsWhenFalseLeft);
1231 break;
1232 case JCTree.OR:
1233 scanCond(tree.lhs);
1234 Bits initsWhenTrueLeft = initsWhenTrue;
1235 Bits uninitsWhenTrueLeft = uninitsWhenTrue;
1236 inits = initsWhenFalse;
1237 uninits = uninitsWhenFalse;
1238 scanCond(tree.rhs);
1239 initsWhenTrue.andSet(initsWhenTrueLeft);
1240 uninitsWhenTrue.andSet(uninitsWhenTrueLeft);
1241 break;
1242 default:
1243 scanExpr(tree.lhs);
1244 scanExpr(tree.rhs);
1245 }
1246 }
1247
1248 public void visitIdent(JCIdent tree) {
1249 if (tree.sym.kind == VAR)
1250 checkInit(tree.pos(), (VarSymbol)tree.sym);
1251 }
1252
1253 public void visitTypeCast(JCTypeCast tree) {
1254 super.visitTypeCast(tree);
1255 if (!tree.type.isErroneous()
1256 && lint.isEnabled(Lint.LintCategory.CAST)
1257 && types.isSameType(tree.expr.type, tree.clazz.type)) {
1258 log.warning(tree.pos(), "redundant.cast", tree.expr.type);
1259 }
1260 }
1261
1262 // FIXME: do flow for let expressions
1263 public void visitLetExpr(LetExpr tree) {
1264 super.visitLetExpr(tree);
1265 }
1266
1267 public void visitTopLevel(JCCompilationUnit tree) {
1268 // Do nothing for TopLevel since each class is visited individually
1269 }
1270
1271 /**************************************************************************
1272 * main method
1273 *************************************************************************/
1274
1275 /** Perform definite assignment/unassignment analysis on a tree.
1276 */
1277 public void analyzeTree(JCTree tree, TreeMaker make) {
1278 try {
1279 this.make = make;
1280 inits = new Bits();
1281 uninits = new Bits();
1282 uninitsTry = new Bits();
1283 initsWhenTrue = initsWhenFalse =
1284 uninitsWhenTrue = uninitsWhenFalse = null;
1285 if (vars == null)
1286 vars = new VarSymbol[32];
1287 else
1288 for (int i=0; i<vars.length; i++)
1289 vars[i] = null;
1290 firstadr = 0;
1291 nextadr = 0;
1292 pendingExits = new ListBuffer<PendingExit>();
1293 alive = true;
1294 this.thrown = this.caught = null;
1295 this.classDef = null;
1296 scan(tree);
1297 } finally {
1298 // note that recursive invocations of this method fail hard
1299 inits = uninits = uninitsTry = null;
1300 initsWhenTrue = initsWhenFalse =
1301 uninitsWhenTrue = uninitsWhenFalse = null;
1302 if (vars != null) for (int i=0; i<vars.length; i++)
1303 vars[i] = null;
1304 firstadr = 0;
1305 nextadr = 0;
1306 pendingExits = null;
1307 this.make = null;
1308 this.thrown = this.caught = null;
1309 this.classDef = null;
1310 }
1311 }
1312 }