/*
 * Copyright (c) 1996, 2003, Oracle and/or its affiliates. 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.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package sun.tools.tree;

import sun.tools.java.*;

WARNING: The contents of this source file are not part of any
supported API.  Code that depends on them does so at its own risk:
they are subject to change or removal without notice.
/**
 * WARNING: The contents of this source file are not part of any
 * supported API.  Code that depends on them does so at its own risk:
 * they are subject to change or removal without notice.
 */
public final
class Vset implements Constants {
    long vset;                  // DA bits for first 64 variables
    long uset;                  // DU bits for first 64 variables

    // The extension array is interleaved, consisting of alternating
    // blocks of 64 DA bits followed by 64 DU bits followed by 64 DA
    // bits, and so on.

    long x[];                   // extension array for more bits

    // An infinite vector of zeroes or an infinite vector of ones is
    // represented by a special value of the extension array.
    //
    // IMPORTANT: The condition 'this.x == fullX' is used as a marker for
    // unreachable code, i.e., for a dead-end.  We maintain the invariant
    // that (this.x != fullX || (this.vset == -1 && this.uset == -1)).
    // A dead-end has the peculiar property that all variables are both
    // definitely assigned and definitely unassigned.  We always force this
    // condition to hold, even when the normal bitvector operations performed
    // during DA/DU analysis would produce a different result.  This supresses
    // reporting of DA/DU errors in unreachable code.

    static final long emptyX[] = new long[0]; // all zeroes
    static final long fullX[]  = new long[0]; // all ones

    // For more thorough testing of long vset support, it is helpful to
    // temporarily redefine this value to a smaller number, such as 1 or 2.

    static final int VBITS = 64; // number of bits in vset (uset)

    
This is the Vset which reports all vars assigned and unassigned.
This impossibility is degenerately true exactly when
control flow cannot reach this point.
/**
     * This is the Vset which reports all vars assigned and unassigned.
     * This impossibility is degenerately true exactly when
     * control flow cannot reach this point.
     */

    // We distinguish a canonical dead-end value generated initially for
    // statements that do not complete normally, making the next one unreachable.
    // Once an unreachable statement is reported, a non-canonical dead-end value
    // is used for subsequent statements in order to suppress redundant error
    // messages.

    static final Vset DEAD_END = new Vset(-1, -1, fullX);

    
Create an empty Vset.
/**
     * Create an empty Vset.
     */
    public Vset() {
        this.x = emptyX;
    }

    private Vset(long vset, long uset, long x[]) {
        this.vset = vset;
        this.uset = uset;
        this.x = x;
    }

    
Create an copy of the given Vset.
(However, DEAD_END simply returns itself.)
/**
     * Create an copy of the given Vset.
     * (However, DEAD_END simply returns itself.)
     */
    public Vset copy() {
        if (this == DEAD_END) {
            return this;
        }
        Vset vs = new Vset(vset, uset, x);
        if (x.length > 0) {
            vs.growX(x.length); // recopy the extension vector
        }
        return vs;
    }

    private void growX(int length) {
        long newX[] = new long[length];
        long oldX[] = x;
        for (int i = 0; i < oldX.length; i++) {
            newX[i] = oldX[i];
        }
        x = newX;
    }

    
Ask if this is a vset for a dead end.
Answer true only for the canonical dead-end, DEAD_END.
A canonical dead-end is produced only as a result of
a statement that cannot complete normally, as specified
by the JLS.  Due to the special-case rules for if-then
and if-then-else, this may fail to detect actual unreachable
code that could easily be identified.
/**
     * Ask if this is a vset for a dead end.
     * Answer true only for the canonical dead-end, DEAD_END.
     * A canonical dead-end is produced only as a result of
     * a statement that cannot complete normally, as specified
     * by the JLS.  Due to the special-case rules for if-then
     * and if-then-else, this may fail to detect actual unreachable
     * code that could easily be identified.
     */

    public boolean isDeadEnd() {
        return (this == DEAD_END);
    }

    
Ask if this is a vset for a dead end.
Answer true for any dead-end.
Since 'clearDeadEnd' has no effect on this predicate,
if-then and if-then-else are handled in the more 'obvious'
and precise way.  This predicate is to be preferred for
dead code elimination purposes.
(Presently used in workaround for bug 4173473 in MethodExpression.java)
/**
     * Ask if this is a vset for a dead end.
     * Answer true for any dead-end.
     * Since 'clearDeadEnd' has no effect on this predicate,
     * if-then and if-then-else are handled in the more 'obvious'
     * and precise way.  This predicate is to be preferred for
     * dead code elimination purposes.
     * (Presently used in workaround for bug 4173473 in MethodExpression.java)
     */
    public boolean isReallyDeadEnd() {
        return (x == fullX);
    }

    
Replace canonical DEAD_END with a distinct but
equivalent Vset.  The bits are unaltered, but
the result does not answer true to 'isDeadEnd'.

Used mostly for error recovery, but see
'IfStatement.check', where it is used to
implement the special-case treatment of
statement reachability for such statements.
/**
     * Replace canonical DEAD_END with a distinct but
     * equivalent Vset.  The bits are unaltered, but
     * the result does not answer true to 'isDeadEnd'.
     * <p>
     * Used mostly for error recovery, but see
     * 'IfStatement.check', where it is used to
     * implement the special-case treatment of
     * statement reachability for such statements.
     */
    public Vset clearDeadEnd() {
        if (this == DEAD_END) {
            return new Vset(-1, -1, fullX);
        }
        return this;
    }

    
Ask if a var is definitely assigned.
/**
     * Ask if a var is definitely assigned.
     */
    public boolean testVar(int varNumber) {
        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            int i = (varNumber / VBITS - 1) * 2;
            if (i >= x.length) {
                return (x == fullX);
            }
            return (x[i] & bit) != 0;
        } else {
            return (vset & bit) != 0;
        }
    }

    
Ask if a var is definitely un-assigned.
(This is not just the negation of testVar:
It's possible for neither to be true.)
/**
     * Ask if a var is definitely un-assigned.
     * (This is not just the negation of testVar:
     * It's possible for neither to be true.)
     */
    public boolean testVarUnassigned(int varNumber) {
        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            // index "uset" extension
            int i = ((varNumber / VBITS - 1) * 2) + 1;
            if (i >= x.length) {
                return (x == fullX);
            }
            return (x[i] & bit) != 0;
        } else {
            return (uset & bit) != 0;
        }
    }

    
Note that a var is definitely assigned.
(Side-effecting.)
/**
     * Note that a var is definitely assigned.
     * (Side-effecting.)
     */
    public Vset addVar(int varNumber) {
        if (x == fullX) {
            return this;
        }

        // gen DA, kill DU

        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            int i = (varNumber / VBITS - 1) * 2;
            if (i >= x.length) {
                growX(i+1);
            }
            x[i] |= bit;
            if (i+1 < x.length) {
                x[i+1] &=~ bit;
            }
        } else {
            vset |= bit;
            uset &=~ bit;
        }
        return this;
    }

    
Note that a var is definitely un-assigned.
(Side-effecting.)
/**
     * Note that a var is definitely un-assigned.
     * (Side-effecting.)
     */
    public Vset addVarUnassigned(int varNumber) {
        if (x == fullX) {
            return this;
        }

        // gen DU, kill DA

        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            // index "uset" extension
            int i = ((varNumber / VBITS - 1) * 2) + 1;
            if (i >= x.length) {
                growX(i+1);
            }
            x[i] |= bit;
            x[i-1] &=~ bit;
        } else {
            uset |= bit;
            vset &=~ bit;
        }
        return this;
    }

    
Retract any assertion about the var.
This operation is ineffective on a dead-end.
(Side-effecting.)
/**
     * Retract any assertion about the var.
     * This operation is ineffective on a dead-end.
     * (Side-effecting.)
     */
    public Vset clearVar(int varNumber) {
        if (x == fullX) {
            return this;
        }
        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            int i = (varNumber / VBITS - 1) * 2;
            if (i >= x.length) {
                return this;
            }
            x[i] &=~ bit;
            if (i+1 < x.length) {
                x[i+1] &=~ bit;
            }
        } else {
            vset &=~ bit;
            uset &=~ bit;
        }
        return this;
    }

    
Join with another vset.  This is set intersection.
(Side-effecting.)
/**
     * Join with another vset.  This is set intersection.
     * (Side-effecting.)
     */
    public Vset join(Vset other) {

        // Return a dead-end if both vsets are dead-ends.
        // Return the canonical DEAD_END only if both vsets
        // are the canonical DEAD_END.  Otherwise, an incoming
        // dead-end vset has already produced an error message,
        // and is now assumed to be reachable.
        if (this == DEAD_END) {
            return other.copy();
        }
        if (other == DEAD_END) {
            return this;
        }
        if (x == fullX) {
            return other.copy();
        }
        if (other.x == fullX) {
            return this;
        }

        // DA = DA intersection DA
        // DU = DU intersection DU

        vset &= other.vset;
        uset &= other.uset;

        if (other.x == emptyX) {
            x = emptyX;
        } else {
            // ASSERT(otherX.length > 0);
            long otherX[] = other.x;
            int selfLength = x.length;
            int limit = (otherX.length < selfLength) ? otherX.length : selfLength;
            for (int i = 0; i < limit; i++) {
                x[i] &= otherX[i];
            }
            // If self is longer than other, all remaining
            // bits are implicitly 0.  In the result, then,
            // the remaining DA and DU bits are cleared.
            for (int i = limit; i < selfLength; i++) {
                x[i] = 0;
            }
        }
        return this;
    }

    
Add in the definite assignment bits of another vset,
but join the definite unassignment bits.  This unusual
operation is used only for 'finally' blocks.  The
original vset 'this' is destroyed by this operation.
(Part of fix for 4068688.)
/**
     * Add in the definite assignment bits of another vset,
     * but join the definite unassignment bits.  This unusual
     * operation is used only for 'finally' blocks.  The
     * original vset 'this' is destroyed by this operation.
     * (Part of fix for 4068688.)
     */

    public Vset addDAandJoinDU(Vset other) {

        // Return a dead-end if either vset is a dead end.
        // If either vset is the canonical DEAD_END, the
        // result is also the canonical DEAD_END.
        if (this == DEAD_END) {
            return this;
        }
        if (other == DEAD_END) {
            return other;
        }
        if (x == fullX) {
            return this;
        }
        if (other.x == fullX) {
            return other.copy();
        }

        // DA = DA union DA'
        // DU = (DU intersection DU') - DA'

        vset = vset | other.vset;
        uset = (uset & other.uset) & ~other.vset;

        int selfLength = x.length;
        long otherX[] = other.x;
        int otherLength = otherX.length;

        if (otherX != emptyX) {
            // ASSERT(otherX.length > 0);
            if (otherLength > selfLength) {
                growX(otherLength);
            }
            int i = 0;
            while (i < otherLength) {
                x[i] |= otherX[i];
                i++;
                if (i == otherLength) break;
                x[i] = ((x[i] & otherX[i]) & ~otherX[i-1]);
                i++;
            }
        }
        // If self is longer than other, all remaining
        // bits are implicitly 0. In the result, then,
        // the remaining DA bits are left unchanged, and
        // the DU bits are all cleared. First, align
        // index to the next block of DU bits (odd index).
        for (int i = (otherLength | 1); i < selfLength; i += 2) {
            x[i] = 0;
        }
        return this;
    }


    
Construct a vset consisting of the DA bits of the first argument
and the DU bits of the second argument.  This is a higly unusual
operation, as it implies a case where the flowgraph for DA analysis
differs from that for DU analysis.  It is only needed for analysing
'try' blocks.  The result is a dead-end iff the first argument is
dead-end. (Part of fix for 4068688.)
/**
     * Construct a vset consisting of the DA bits of the first argument
     * and the DU bits of the second argument.  This is a higly unusual
     * operation, as it implies a case where the flowgraph for DA analysis
     * differs from that for DU analysis.  It is only needed for analysing
     * 'try' blocks.  The result is a dead-end iff the first argument is
     * dead-end. (Part of fix for 4068688.)
     */

    public static Vset firstDAandSecondDU(Vset sourceDA, Vset sourceDU) {

        // Note that reachability status is received via 'sourceDA' only!
        // This is a consequence of the fact that reachability and DA
        // analysis are performed on an identical flow graph, whereas the
        // flowgraph for DU analysis differs in the case of a 'try' statement.
        if (sourceDA.x == fullX) {
            return sourceDA.copy();
        }

        long sourceDAx[] = sourceDA.x;
        int lenDA = sourceDAx.length;
        long sourceDUx[] = sourceDU.x;
        int lenDU = sourceDUx.length;
        int limit = (lenDA > lenDU) ? lenDA : lenDU;
        long x[] = emptyX;

        if (limit > 0) {
            x = new long[limit];
            for (int i = 0; i < lenDA; i += 2) {
                x[i] = sourceDAx[i];
            }
            for (int i = 1; i < lenDU; i += 2) {
                x[i] = sourceDUx[i];
            }
        }

        return new Vset(sourceDA.vset, sourceDU.uset, x);
    }

    
Remove variables from the vset that are no longer part of
a context.  Zeroes are stored past varNumber.
(Side-effecting.)

However, if this is a dead end, keep it so.
That is, leave an infinite tail of bits set.
/**
     * Remove variables from the vset that are no longer part of
     * a context.  Zeroes are stored past varNumber.
     * (Side-effecting.)<p>
     * However, if this is a dead end, keep it so.
     * That is, leave an infinite tail of bits set.
     */
    public Vset removeAdditionalVars(int varNumber) {
        if (x == fullX) {
            return this;
        }
        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            int i = (varNumber / VBITS - 1) * 2;
            if (i < x.length) {
                x[i] &= (bit - 1);
                if (++i < x.length) {
                    x[i] &= (bit - 1); // do the "uset" extension also
                }
                while (++i < x.length) {
                    x[i] = 0;
                }
            }
        } else {
            if (x.length > 0) {
                x = emptyX;
            }
            vset &= (bit - 1);
            uset &= (bit - 1);
        }
        return this;
    }

    
Return one larger than the highest bit set.
/**
     * Return one larger than the highest bit set.
     */
    public int varLimit() {
        long vset;
        int result;
    scan: {
            for (int i = (x.length / 2) * 2; i >= 0; i -= 2) {
                if (i == x.length)  continue; // oops
                vset = x[i];
                if (i+1 < x.length) {
                    vset |= x[i+1]; // check the "uset" also
                }
                if (vset != 0) {
                    result = (i/2 + 1) * VBITS;
                    break scan;
                }
            }
            vset = this.vset;
            vset |= this.uset;  // check the "uset" also
            if (vset != 0) {
                result = 0;
                break scan;
            } else {
                return 0;
            }
        }
        while (vset != 0) {
            result += 1;
            vset >>>= 1;
        }
        return result;
    }

    public String toString() {
        if (this == DEAD_END)
            return "{DEAD_END}";
        StringBuilder sb = new StringBuilder("{");
        int maxVar = VBITS * (1 + (x.length+1)/2);
        for (int i = 0; i < maxVar; i++) {
            if (!testVarUnassigned(i)) {
                if (sb.length() > 1) {
                    sb.append(' ');
                }
                sb.append(i);
                if (!testVar(i)) {
                    sb.append('?'); // not definitely unassigned
                }
            }
        }
        if (x == fullX) {
            sb.append("...DEAD_END");
        }
        sb.append('}');
        return sb.toString();
    }

}