flow.java

是一款用JAVA 编写的编译器 具有很强的编译功能

/*
 * Copyright 1999-2006 Sun Microsystems, Inc.  All Rights Reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Sun designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Sun in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 */

//todo: one might eliminate uninits.andSets when monotonic

package com.sun.tools.javac.comp;

import com.sun.tools.javac.code.*;
import com.sun.tools.javac.tree.*;
import com.sun.tools.javac.util.*;
import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;

import com.sun.tools.javac.code.Symbol.*;
import com.sun.tools.javac.tree.JCTree.*;

import static com.sun.tools.javac.code.Flags.*;
import static com.sun.tools.javac.code.Kinds.*;
import static com.sun.tools.javac.code.TypeTags.*;

/** This pass implements dataflow analysis for Java programs.
 *  Liveness analysis checks that every statement is reachable.
 *  Exception analysis ensures that every checked exception that is
 *  thrown is declared or caught.  Definite assignment analysis
 *  ensures that each variable is assigned when used.  Definite
 *  unassignment analysis ensures that no final variable is assigned
 *  more than once.
 *
 *  <p>The second edition of the JLS has a number of problems in the
 *  specification of these flow analysis problems. This implementation
 *  attempts to address those issues.
 *
 *  <p>First, there is no accommodation for a finally clause that cannot
 *  complete normally. For liveness analysis, an intervening finally
 *  clause can cause a break, continue, or return not to reach its
 *  target.  For exception analysis, an intervening finally clause can
 *  cause any exception to be "caught".  For DA/DU analysis, the finally
 *  clause can prevent a transfer of control from propagating DA/DU
 *  state to the target.  In addition, code in the finally clause can
 *  affect the DA/DU status of variables.
 *
 *  <p>For try statements, we introduce the idea of a variable being
 *  definitely unassigned "everywhere" in a block.  A variable V is
 *  "unassigned everywhere" in a block iff it is unassigned at the
 *  beginning of the block and there is no reachable assignment to V
 *  in the block.  An assignment V=e is reachable iff V is not DA
 *  after e.  Then we can say that V is DU at the beginning of the
 *  catch block iff V is DU everywhere in the try block.  Similarly, V
 *  is DU at the beginning of the finally block iff V is DU everywhere
 *  in the try block and in every catch block.  Specifically, the
 *  following bullet is added to 16.2.2
 *  <pre>
 *	V is <em>unassigned everywhere</em> in a block if it is
 *	unassigned before the block and there is no reachable
 *	assignment to V within the block.
 *  </pre>
 *  <p>In 16.2.15, the third bullet (and all of its sub-bullets) for all
 *  try blocks is changed to
 *  <pre>
 *	V is definitely unassigned before a catch block iff V is
 *	definitely unassigned everywhere in the try block.
 *  </pre>
 *  <p>The last bullet (and all of its sub-bullets) for try blocks that
 *  have a finally block is changed to
 *  <pre>
 *	V is definitely unassigned before the finally block iff
 *	V is definitely unassigned everywhere in the try block
 *	and everywhere in each catch block of the try statement.
 *  </pre>
 *  <p>In addition,
 *  <pre>
 *	V is definitely assigned at the end of a constructor iff
 *	V is definitely assigned after the block that is the body
 *	of the constructor and V is definitely assigned at every
 *	return that can return from the constructor.
 *  </pre>
 *  <p>In addition, each continue statement with the loop as its target
 *  is treated as a jump to the end of the loop body, and "intervening"
 *  finally clauses are treated as follows: V is DA "due to the
 *  continue" iff V is DA before the continue statement or V is DA at
 *  the end of any intervening finally block.  V is DU "due to the
 *  continue" iff any intervening finally cannot complete normally or V
 *  is DU at the end of every intervening finally block.  This "due to
 *  the continue" concept is then used in the spec for the loops.
 *
 *  <p>Similarly, break statements must consider intervening finally
 *  blocks.  For liveness analysis, a break statement for which any
 *  intervening finally cannot complete normally is not considered to
 *  cause the target statement to be able to complete normally. Then
 *  we say V is DA "due to the break" iff V is DA before the break or
 *  V is DA at the end of any intervening finally block.  V is DU "due
 *  to the break" iff any intervening finally cannot complete normally
 *  or V is DU at the break and at the end of every intervening
 *  finally block.  (I suspect this latter condition can be
 *  simplified.)  This "due to the break" is then used in the spec for
 *  all statements that can be "broken".
 *
 *  <p>The return statement is treated similarly.  V is DA "due to a
 *  return statement" iff V is DA before the return statement or V is
 *  DA at the end of any intervening finally block.  Note that we
 *  don't have to worry about the return expression because this
 *  concept is only used for construcrors.
 *
 *  <p>There is no spec in JLS2 for when a variable is definitely
 *  assigned at the end of a constructor, which is needed for final
 *  fields (8.3.1.2).  We implement the rule that V is DA at the end
 *  of the constructor iff it is DA and the end of the body of the
 *  constructor and V is DA "due to" every return of the constructor.
 *
 *  <p>Intervening finally blocks similarly affect exception analysis.	An
 *  intervening finally that cannot complete normally allows us to ignore
 *  an otherwise uncaught exception.
 *
 *  <p>To implement the semantics of intervening finally clauses, all
 *  nonlocal transfers (break, continue, return, throw, method call that
 *  can throw a checked exception, and a constructor invocation that can
 *  thrown a checked exception) are recorded in a queue, and removed
 *  from the queue when we complete processing the target of the
 *  nonlocal transfer.  This allows us to modify the queue in accordance
 *  with the above rules when we encounter a finally clause.  The only
 *  exception to this [no pun intended] is that checked exceptions that
 *  are known to be caught or declared to be caught in the enclosing
 *  method are not recorded in the queue, but instead are recorded in a
 *  global variable "Set<Type> thrown" that records the type of all
 *  exceptions that can be thrown.
 *
 *  <p>Other minor issues the treatment of members of other classes
 *  (always considered DA except that within an anonymous class
 *  constructor, where DA status from the enclosing scope is
 *  preserved), treatment of the case expression (V is DA before the
 *  case expression iff V is DA after the switch expression),
 *  treatment of variables declared in a switch block (the implied
 *  DA/DU status after the switch expression is DU and not DA for
 *  variables defined in a switch block), the treatment of boolean ?:
 *  expressions (The JLS rules only handle b and c non-boolean; the
 *  new rule is that if b and c are boolean valued, then V is
 *  (un)assigned after a?b:c when true/false iff V is (un)assigned
 *  after b when true/false and V is (un)assigned after c when
 *  true/false).
 *
 *  <p>There is the remaining question of what syntactic forms constitute a
 *  reference to a variable.  It is conventional to allow this.x on the
 *  left-hand-side to initialize a final instance field named x, yet
 *  this.x isn't considered a "use" when appearing on a right-hand-side
 *  in most implementations.  Should parentheses affect what is
 *  considered a variable reference?  The simplest rule would be to
 *  allow unqualified forms only, parentheses optional, and phase out
 *  support for assigning to a final field via this.x.
 *
 *  <p><b>This is NOT part of any API supported by Sun Microsystems.  If
 *  you write code that depends on this, you do so at your own risk.
 *  This code and its internal interfaces are subject to change or
 *  deletion without notice.</b>
 */
public class Flow extends TreeScanner {
    protected static final Context.Key<Flow> flowKey =
	new Context.Key<Flow>();

    private final Name.Table names;
    private final Log log;
    private final Symtab syms;
    private final Types types;
    private final Check chk;
    private       TreeMaker make;
    private       Lint lint;

    public static Flow instance(Context context) {
	Flow instance = context.get(flowKey);
	if (instance == null)
	    instance = new Flow(context);
	return instance;
    }

    protected Flow(Context context) {
	context.put(flowKey, this);

	names = Name.Table.instance(context);
	log = Log.instance(context);
	syms = Symtab.instance(context);
        types = Types.instance(context);
	chk = Check.instance(context);
	lint = Lint.instance(context);
    }

    /** A flag that indicates whether the last statement could
     *	complete normally.
     */
    private boolean alive;

    /** The set of definitely assigned variables.
     */
    Bits inits;

    /** The set of definitely unassigned variables.
     */
    Bits uninits;

    /** The set of variables that are definitely unassigned everywhere
     *	in current try block. This variable is maintained lazily; it is
     *	updated only when something gets removed from uninits,
     *	typically by being assigned in reachable code.	To obtain the
     *	correct set of variables which are definitely unassigned
     *	anywhere in current try block, intersect uninitsTry and
     *	uninits.
     */
    Bits uninitsTry;

    /** When analyzing a condition, inits and uninits are null.
     *	Instead we have:
     */
    Bits initsWhenTrue;
    Bits initsWhenFalse;
    Bits uninitsWhenTrue;
    Bits uninitsWhenFalse;

    /** A mapping from addresses to variable symbols.
     */
    VarSymbol[] vars;

    /** The current class being defined.
     */
    JCClassDecl classDef;

    /** The first variable sequence number in this class definition.
     */
    int firstadr;

    /** The next available variable sequence number.
     */
    int nextadr;

    /** The list of possibly thrown declarable exceptions.
     */
    List<Type> thrown;

    /** The list of exceptions that are either caught or declared to be
     *	thrown.
     */
    List<Type> caught;

    /** Set when processing a loop body the second time for DU analysis. */
    boolean loopPassTwo = false;

    /*-------------------- Environments ----------------------*/

    /** A pending exit.	 These are the statements return, break, and
     *	continue.  In addition, exception-throwing expressions or
     *	statements are put here when not known to be caught.  This
     *	will typically result in an error unless it is within a
     *	try-finally whose finally block cannot complete normally.
     */
    static class PendingExit {
	JCTree tree;
	Bits inits;
	Bits uninits;
	Type thrown;
	PendingExit(JCTree tree, Bits inits, Bits uninits) {
	    this.tree = tree;
	    this.inits = inits.dup();
	    this.uninits = uninits.dup();
	}
	PendingExit(JCTree tree, Type thrown) {
	    this.tree = tree;
	    this.thrown = thrown;
	}
    }

    /** The currently pending exits that go from current inner blocks
     *	to an enclosing block, in source order.
     */
    ListBuffer<PendingExit> pendingExits;

    /*-------------------- Exceptions ----------------------*/

    /** Complain that pending exceptions are not caught.
     */
    void errorUncaught() {
	for (PendingExit exit = pendingExits.next();
	     exit != null;
	     exit = pendingExits.next()) {
	    boolean synthetic = classDef != null &&
		classDef.pos == exit.tree.pos;
	    log.error(exit.tree.pos(),
		      synthetic
		      ? "unreported.exception.default.constructor"
		      : "unreported.exception.need.to.catch.or.throw",
		      exit.thrown);
	}
    }

    /** Record that exception is potentially thrown and check that it
     *	is caught.
     */
    void markThrown(JCTree tree, Type exc) {
	if (!chk.isUnchecked(tree.pos(), exc)) {
	    if (!chk.isHandled(exc, caught))
		pendingExits.append(new PendingExit(tree, exc));
	    thrown = chk.incl(exc, thrown);
	}
    }

    /*-------------- Processing variables ----------------------*/

    /** Do we need to track init/uninit state of this symbol?
     *	I.e. is symbol either a local or a blank final variable?
     */
    boolean trackable(VarSymbol sym) {
	return
	    (sym.owner.kind == MTH ||
	     ((sym.flags() & (FINAL | HASINIT | PARAMETER)) == FINAL &&
	      classDef.sym.isEnclosedBy((ClassSymbol)sym.owner)));
    }

    /** Initialize new trackable variable by setting its address field
     *	to the next available sequence number and entering it under that
     *	index into the vars array.
     */
    void newVar(VarSymbol sym) {
	if (nextadr == vars.length) {
	    VarSymbol[] newvars = new VarSymbol[nextadr * 2];
	    System.arraycopy(vars, 0, newvars, 0, nextadr);
	    vars = newvars;
	}
	sym.adr = nextadr;
	vars[nextadr] = sym;
	inits.excl(nextadr);
	uninits.incl(nextadr);
	nextadr++;
    }

    /** Record an initialization of a trackable variable.
     */
    void letInit(DiagnosticPosition pos, VarSymbol sym) {
	if (sym.adr >= firstadr && trackable(sym)) {
	    if ((sym.flags() & FINAL) != 0) {
		if ((sym.flags() & PARAMETER) != 0) {
		    log.error(pos, "final.parameter.may.not.be.assigned",
			      sym);
		} else if (!uninits.isMember(sym.adr)) {
		    log.error(pos,
			      loopPassTwo
			      ? "var.might.be.assigned.in.loop"
			      : "var.might.already.be.assigned",
			      sym);
		} else if (!inits.isMember(sym.adr)) {
		    // reachable assignment
		    uninits.excl(sym.adr);
		    uninitsTry.excl(sym.adr);
		} else {
		    //log.rawWarning(pos, "unreachable assignment");//DEBUG
		    uninits.excl(sym.adr);
		}
	    }
	    inits.incl(sym.adr);
	} else if ((sym.flags() & FINAL) != 0) {
	    log.error(pos, "var.might.already.be.assigned", sym);
	}
    }

    /** If tree is either a simple name or of the form this.name or
     *	C.this.name, and tree represents a trackable variable,
     *	record an initialization of the variable.
     */
    void letInit(JCTree tree) {
	tree = TreeInfo.skipParens(tree);
	if (tree.getTag() == JCTree.IDENT || tree.getTag() == JCTree.SELECT) {
	    Symbol sym = TreeInfo.symbol(tree);
	    letInit(tree.pos(), (VarSymbol)sym);
	}
    }

    /** Check that trackable variable is initialized.
     */
    void checkInit(DiagnosticPosition pos, VarSymbol sym) {
	if ((sym.adr >= firstadr || sym.owner.kind != TYP) &&
	    trackable(sym) &&
	    !inits.isMember(sym.adr)) {
	    log.error(pos, "var.might.not.have.been.initialized",
		      sym);
	    inits.incl(sym.adr);
	}
    }

    /*-------------------- Handling jumps ----------------------*/

    /** Record an outward transfer of control. */
    void recordExit(JCTree tree) {
	pendingExits.append(new PendingExit(tree, inits, uninits));
	markDead();
    }

    /** Resolve all breaks of this statement. */
    boolean resolveBreaks(JCTree tree,
			  ListBuffer<PendingExit> oldPendingExits) {
	boolean result = false;
	List<PendingExit> exits = pendingExits.toList();
	pendingExits = oldPendingExits;
	for (; exits.nonEmpty(); exits = exits.tail) {
	    PendingExit exit = exits.head;
	    if (exit.tree.getTag() == JCTree.BREAK &&
		((JCBreak) exit.tree).target == tree) {
		inits.andSet(exit.inits);
		uninits.andSet(exit.uninits);
		result = true;
	    } else {
		pendingExits.append(exit);
	    }
	}