/*
 * Javassist, a Java-bytecode translator toolkit.
 * Copyright (C) 1999- Shigeru Chiba. All Rights Reserved.
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License.  Alternatively, the contents of this file may be used under
 * the terms of the GNU Lesser General Public License Version 2.1 or later,
 * or the Apache License Version 2.0.
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 */
package javassist.bytecode.analysis;

import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Map;

import javassist.ClassPool;
import javassist.CtClass;
import javassist.NotFoundException;

Represents a JVM type in data-flow analysis. This abstraction is necessary since a JVM type not only includes all normal Java types, but also a few special types that are used by the JVM internally. See the static field types on this class for more info on these special types. All primitive and special types reuse the same instance, so identity comparison can be used when examining them. Normal java types must use equals(Object) to compare type instances. In most cases, applications which consume this API, only need to call getCtClass() to obtain the needed type information. 
Author:
Jason T. Greene/**
 * Represents a JVM type in data-flow analysis. This abstraction is necessary since
 * a JVM type not only includes all normal Java types, but also a few special types
 * that are used by the JVM internally. See the static field types on this class for
 * more info on these special types.
 *
 * All primitive and special types reuse the same instance, so identity comparison can
 * be used when examining them. Normal java types must use {@link #equals(Object)} to
 * compare type instances.
 *
 * In most cases, applications which consume this API, only need to call {@link #getCtClass()}
 * to obtain the needed type information.
 *
 * @author Jason T. Greene
 */
public class Type {
    private final CtClass clazz;
    private final boolean special;

    private static final Map<CtClass,Type> prims = new IdentityHashMap<CtClass,Type>();
    
Represents the double primitive type /** Represents the double primitive type */
    public static final Type DOUBLE = new Type(CtClass.doubleType);
    
Represents the boolean primitive type /** Represents the boolean primitive type */
    public static final Type BOOLEAN = new Type(CtClass.booleanType);
    
Represents the long primitive type /** Represents the long primitive type */
    public static final Type LONG = new Type(CtClass.longType);
    
Represents the char primitive type /** Represents the char primitive type */
    public static final Type CHAR = new Type(CtClass.charType);
    
Represents the byte primitive type /** Represents the byte primitive type */
    public static final Type BYTE = new Type(CtClass.byteType);
    
Represents the short primitive type /** Represents the short primitive type */
    public static final Type SHORT = new Type(CtClass.shortType);
    
Represents the integer primitive type /** Represents the integer primitive type */
    public static final Type INTEGER = new Type(CtClass.intType);
    
Represents the float primitive type /** Represents the float primitive type */
    public static final Type FLOAT = new Type(CtClass.floatType);
    
Represents the void primitive type /** Represents the void primitive type */
    public static final Type VOID = new Type(CtClass.voidType);

    
Represents an unknown, or null type. This occurs when aconst_null is used.
It is important not to treat this type as java.lang.Object, since a null can
be assigned to any reference type. The analyzer will replace these with
an actual known type if it can be determined by a merged path with known type
information. If this type is encountered on a frame then it is guaranteed to
be null, and the type information is simply not available. Any attempts to
infer the type, without further information from the compiler would be a guess.
/**
     * Represents an unknown, or null type. This occurs when aconst_null is used.
     * It is important not to treat this type as java.lang.Object, since a null can
     * be assigned to any reference type. The analyzer will replace these with
     * an actual known type if it can be determined by a merged path with known type
     * information. If this type is encountered on a frame then it is guaranteed to
     * be null, and the type information is simply not available. Any attempts to
     * infer the type, without further information from the compiler would be a guess.
     */
    public static final Type UNINIT = new Type(null);

    
Represents an internal JVM return address, which is used by the RET
instruction to return to a JSR that invoked the subroutine.
/**
     * Represents an internal JVM return address, which is used by the RET
     * instruction to return to a JSR that invoked the subroutine.
     */
    public static final Type RETURN_ADDRESS = new Type(null, true);

    
A placeholder used by the analyzer for the second word position of a double-word type /** A placeholder used by the analyzer for the second word position of a double-word type */
    public static final Type TOP = new Type(null, true);

    
Represents a non-accessible value. Code cannot access the value this type
represents. It occurs when bytecode reuses a local variable table
position with non-mergable types. An example would be compiled code which
uses the same position for a primitive type in one branch, and a reference type
in another branch.
/**
     * Represents a non-accessible value. Code cannot access the value this type
     * represents. It occurs when bytecode reuses a local variable table
     * position with non-mergable types. An example would be compiled code which
     * uses the same position for a primitive type in one branch, and a reference type
     * in another branch.
     */
    public static final Type BOGUS = new Type(null, true);

    
Represents the java.lang.Object reference type /** Represents the java.lang.Object reference type */
    public static final Type OBJECT = lookupType("java.lang.Object");
    
Represents the java.io.Serializable reference type /** Represents the java.io.Serializable reference type */
    public static final Type SERIALIZABLE = lookupType("java.io.Serializable");
    
Represents the java.lang.Coneable reference type /** Represents the java.lang.Coneable reference type */
    public static final Type CLONEABLE = lookupType("java.lang.Cloneable");
    
Represents the java.lang.Throwable reference type /** Represents the java.lang.Throwable reference type */
    public static final Type THROWABLE = lookupType("java.lang.Throwable");

    static {
        prims.put(CtClass.doubleType, DOUBLE);
        prims.put(CtClass.longType, LONG);
        prims.put(CtClass.charType, CHAR);
        prims.put(CtClass.shortType, SHORT);
        prims.put(CtClass.intType, INTEGER);
        prims.put(CtClass.floatType, FLOAT);
        prims.put(CtClass.byteType, BYTE);
        prims.put(CtClass.booleanType, BOOLEAN);
        prims.put(CtClass.voidType, VOID);

    }

    
Obtain the Type for a given class. If the class is a primitive,
the the unique type instance for the primitive will be returned.
Otherwise a new Type instance representing the class is returned.
Params:
clazz – The java class
Returns:
a type instance for this class/**
     * Obtain the Type for a given class. If the class is a primitive,
     * the the unique type instance for the primitive will be returned.
     * Otherwise a new Type instance representing the class is returned.
     *
     * @param clazz The java class
     * @return a type instance for this class
     */
    public static Type get(CtClass clazz) {
        Type type = (Type)prims.get(clazz);
        return type != null ? type : new Type(clazz);
    }

    private static Type lookupType(String name) {
        try {
             return new Type(ClassPool.getDefault().get(name));
        } catch (NotFoundException e) {
            throw new RuntimeException(e);
        }
    }

    Type(CtClass clazz) {
        this(clazz, false);
    }

    private Type(CtClass clazz, boolean special) {
        this.clazz = clazz;
        this.special = special;
    }

    // Used to indicate a merge internally triggered a change
    boolean popChanged() {
        return false;
    }

    
Gets the word size of this type. Double-word types, such as long and double
will occupy two positions on the local variable table or stack.
Returns:
the number of words needed to hold this type/**
     * Gets the word size of this type. Double-word types, such as long and double
     * will occupy two positions on the local variable table or stack.
     *
     * @return the number of words needed to hold this type
     */
    public int getSize() {
        return clazz == CtClass.doubleType || clazz == CtClass.longType || this == TOP ? 2 : 1;
    }

    
Returns the class this type represents. If the type is special, null will be returned.
Returns:
the class for this type, or null if special/**
     * Returns the class this type represents. If the type is special, null will be returned.
     *
     * @return the class for this type, or null if special
     */
    public CtClass getCtClass() {
        return clazz;
    }

    
Returns whether or not this type is a normal java reference, i.e. it is or extends java.lang.Object.
Returns:
true if a java reference, false if a primitive or special/**
     * Returns whether or not this type is a normal java reference, i.e. it is or extends java.lang.Object.
     *
     * @return true if a java reference, false if a primitive or special
     */
    public boolean isReference() {
        return !special && (clazz == null || !clazz.isPrimitive());
    }

    
Returns whether or not the type is special. A special type is one that is either used
for internal tracking, or is only used internally by the JVM.
Returns:
true if special, false if not/**
     * Returns whether or not the type is special. A special type is one that is either used
     * for internal tracking, or is only used internally by the JVM.
     *
     * @return true if special, false if not
     */
    public boolean isSpecial() {
        return special;
    }

    
Returns whether or not this type is an array.
Returns:
true if an array, false if not/**
     * Returns whether or not this type is an array.
     *
     * @return true if an array, false if not
     */
    public boolean isArray() {
        return clazz != null && clazz.isArray();
    }

    
Returns the number of dimensions of this array. If the type is not an
array zero is returned.
Returns:
zero if not an array, otherwise the number of array dimensions./**
     * Returns the number of dimensions of this array. If the type is not an
     * array zero is returned.
     *
     * @return zero if not an array, otherwise the number of array dimensions.
     */
    public int getDimensions() {
        if (!isArray()) return 0;

        String name = clazz.getName();
        int pos = name.length() - 1;
        int count = 0;
        while (name.charAt(pos) == ']' ) {
            pos -= 2;
            count++;
        }

        return count;
    }

    
Returns the array component if this type is an array. If the type
is not an array null is returned.
Returns:
the array component if an array, otherwise null/**
     * Returns the array component if this type is an array. If the type
     * is not an array null is returned.
     *
     * @return the array component if an array, otherwise null
     */
    public Type getComponent() {
        if (this.clazz == null || !this.clazz.isArray())
            return null;

        CtClass component;
        try {
            component = this.clazz.getComponentType();
        } catch (NotFoundException e) {
            throw new RuntimeException(e);
        }

        Type type = (Type)prims.get(component);
        return (type != null) ? type : new Type(component);
    }

    
Determines whether this type is assignable, to the passed type.
A type is assignable to another if it is either the same type, or
a sub-type.
Params:
type – the type to test assignability to
Returns:
true if this is assignable to type, otherwise false/**
     * Determines whether this type is assignable, to the passed type.
     * A type is assignable to another if it is either the same type, or
     * a sub-type.
     *
     * @param type the type to test assignability to
     * @return true if this is assignable to type, otherwise false
     */
    public boolean isAssignableFrom(Type type) {
        if (this == type)
            return true;

        if ((type == UNINIT && isReference()) || this == UNINIT && type.isReference())
            return true;

        if (type instanceof MultiType)
            return ((MultiType)type).isAssignableTo(this);

        if (type instanceof MultiArrayType)
            return ((MultiArrayType)type).isAssignableTo(this);


        // Primitives and Special types must be identical
        if (clazz == null || clazz.isPrimitive())
            return false;

        try {
            return type.clazz.subtypeOf(clazz);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    
Finds the common base type, or interface which both this and the specified type can be assigned. If there is more than one possible answer, then a MultiType, or a MultiArrayType is returned. Multi-types have special rules, and successive merges and assignment tests on them will alter their internal state, as well as other multi-types they have been merged with. This method is used by the data-flow analyzer to merge the type state from multiple branches. 
Params:
type – the type to merge with
Returns:
the merged type/**
     * Finds the common base type, or interface which both this and the specified
     * type can be assigned. If there is more than one possible answer, then a {@link MultiType},
     * or a {@link MultiArrayType} is returned. Multi-types have special rules,
     * and successive merges and assignment tests on them will alter their internal state,
     * as well as other multi-types they have been merged with. This method is used by
     * the data-flow analyzer to merge the type state from multiple branches.
     *
     * @param type the type to merge with
     * @return the merged type
     */
    public Type merge(Type type) {
        if (type == this)
            return this;
        if (type == null)
            return this;
        if (type == Type.UNINIT)
            return this;
        if (this == Type.UNINIT)
            return type;

        // Unequal primitives and special types can not be merged
        if (! type.isReference() || ! this.isReference())
            return BOGUS;

        // Centralize merging of multi-interface types
        if (type instanceof MultiType)
            return type.merge(this);

        if (type.isArray() && this.isArray())
            return mergeArray(type);

        try {
            return mergeClasses(type);
        } catch (NotFoundException e) {
            throw new RuntimeException(e);
        }
    }

   Type getRootComponent(Type type) {
        while (type.isArray())
            type = type.getComponent();

        return type;
    }

    private Type createArray(Type rootComponent, int dims) {
        if (rootComponent instanceof MultiType)
            return new MultiArrayType((MultiType) rootComponent, dims);

        String name = arrayName(rootComponent.clazz.getName(), dims);

        Type type;
        try {
            type = Type.get(getClassPool(rootComponent).get(name));
        } catch (NotFoundException e) {
            throw new RuntimeException(e);
        }

        return type;
    }

    String arrayName(String component, int dims) {
     // Using char[] since we have no StringBuilder in JDK4, and StringBuffer is slow.
        // Although, this is more efficient even if we did have one.
        int i = component.length();
        int size = i + dims * 2;
        char[] string = new char[size];
        component.getChars(0, i, string, 0);
        while (i < size) {
            string[i++] = '[';
            string[i++] = ']';
        }
        component = new String(string);
        return component;
    }

    private ClassPool getClassPool(Type rootComponent) {
        ClassPool pool = rootComponent.clazz.getClassPool();
        return pool != null ? pool : ClassPool.getDefault();
    }

    private Type mergeArray(Type type) {
        Type typeRoot = getRootComponent(type);
        Type thisRoot = getRootComponent(this);
        int typeDims = type.getDimensions();
        int thisDims = this.getDimensions();

        // Array commponents can be merged when the dimensions are equal
        if (typeDims == thisDims) {
            Type mergedComponent = thisRoot.merge(typeRoot);

            // If the components can not be merged (a primitive component mixed with a different type)
            // then Object is the common type.
            if (mergedComponent == Type.BOGUS)
                return Type.OBJECT;

            return createArray(mergedComponent, thisDims);
        }

        Type targetRoot;
        int targetDims;

        if (typeDims < thisDims) {
            targetRoot = typeRoot;
            targetDims = typeDims;
        } else {
            targetRoot = thisRoot;
            targetDims = thisDims;
        }

        // Special case, arrays are cloneable and serializable, so prefer them when dimensions differ
        if (eq(CLONEABLE.clazz, targetRoot.clazz) || eq(SERIALIZABLE.clazz, targetRoot.clazz))
            return createArray(targetRoot, targetDims);

        return createArray(OBJECT, targetDims);
    }

    private static CtClass findCommonSuperClass(CtClass one, CtClass two) throws NotFoundException {
        CtClass deep = one;
        CtClass shallow = two;
        CtClass backupShallow = shallow;
        CtClass backupDeep = deep;

        // Phase 1 - Find the deepest hierarchy, set deep and shallow correctly
        for (;;) {
            // In case we get lucky, and find a match early
            if (eq(deep, shallow) && deep.getSuperclass() != null)
                return deep;

            CtClass deepSuper = deep.getSuperclass();
            CtClass shallowSuper = shallow.getSuperclass();

            if (shallowSuper == null) {
                // right, now reset shallow
                shallow = backupShallow;
                break;
            }

            if (deepSuper == null) {
                // wrong, swap them, since deep is now useless, its our tmp before we swap it
                deep = backupDeep;
                backupDeep = backupShallow;
                backupShallow = deep;

                deep = shallow;
                shallow = backupShallow;
                break;
            }

            deep = deepSuper;
            shallow = shallowSuper;
        }

        // Phase 2 - Move deepBackup up by (deep end - deep)
        for (;;) {
            deep = deep.getSuperclass();
            if (deep == null)
                break;

            backupDeep = backupDeep.getSuperclass();
        }

        deep = backupDeep;

        // Phase 3 - The hierarchy positions are now aligned
        // The common super class is easy to find now
        while (!eq(deep, shallow)) {
            deep = deep.getSuperclass();
            shallow = shallow.getSuperclass();
        }

        return deep;
    }

    private Type mergeClasses(Type type) throws NotFoundException {
        CtClass superClass = findCommonSuperClass(this.clazz, type.clazz);

        // If its Object, then try and find a common interface(s)
        if (superClass.getSuperclass() == null) {
            Map<String,CtClass> interfaces = findCommonInterfaces(type);
            if (interfaces.size() == 1)
                return new Type((CtClass) interfaces.values().iterator().next());
            if (interfaces.size() > 1)
                return new MultiType(interfaces);

            // Only Object is in common
            return new Type(superClass);
        }

        // Check for a common interface that is not on the found supertype
        Map<String,CtClass> commonDeclared = findExclusiveDeclaredInterfaces(type, superClass);
        if (commonDeclared.size() > 0) {
            return new MultiType(commonDeclared, new Type(superClass));
        }

        return new Type(superClass);
    }

    private Map<String,CtClass> findCommonInterfaces(Type type) {
        Map<String,CtClass> typeMap = getAllInterfaces(type.clazz, null);
        Map<String,CtClass> thisMap = getAllInterfaces(this.clazz, null);

        return findCommonInterfaces(typeMap, thisMap);
    }

    private Map<String,CtClass> findExclusiveDeclaredInterfaces(Type type, CtClass exclude) {
        Map<String,CtClass> typeMap = getDeclaredInterfaces(type.clazz, null);
        Map<String,CtClass> thisMap = getDeclaredInterfaces(this.clazz, null);
        Map<String,CtClass> excludeMap = getAllInterfaces(exclude, null);

        for (String intf:excludeMap.keySet()) {
            typeMap.remove(intf);
            thisMap.remove(intf);
        }

        return findCommonInterfaces(typeMap, thisMap);
    }


    Map<String,CtClass> findCommonInterfaces(Map<String,CtClass> typeMap, Map<String,CtClass> alterMap) {
        if (alterMap == null)
            alterMap = new HashMap<String,CtClass>();

        if (typeMap == null||typeMap.isEmpty())
            alterMap.clear();

        for (String name:alterMap.keySet())
            if (!typeMap.containsKey(name))
                alterMap.remove(name);

        // Reduce to subinterfaces
        // This does not need to be recursive since we make a copy,
        // and that copy contains all super types for the whole hierarchy
        for (CtClass intf:alterMap.values()) {
            CtClass[] interfaces;
            try {
                interfaces = intf.getInterfaces();
            } catch (NotFoundException e) {
                throw new RuntimeException(e);
            }

            for (CtClass c:interfaces)
                alterMap.remove(c.getName());
        }

        return alterMap;
    }

    Map<String,CtClass> getAllInterfaces(CtClass clazz, Map<String,CtClass> map) {
        if (map == null)
            map = new HashMap<String,CtClass>();

        if (clazz.isInterface())
            map.put(clazz.getName(), clazz);
        do {
            try {
                CtClass[] interfaces = clazz.getInterfaces();
                for (CtClass intf:interfaces) {
                    map.put(intf.getName(), intf);
                    getAllInterfaces(intf, map);
                }

                clazz = clazz.getSuperclass();
            } catch (NotFoundException e) {
                throw new RuntimeException(e);
            }
        } while (clazz != null);

        return map;
    }

    Map<String,CtClass> getDeclaredInterfaces(CtClass clazz, Map<String,CtClass> map) {
        if (map == null)
            map = new HashMap<String,CtClass>();

        if (clazz.isInterface())
            map.put(clazz.getName(), clazz);

        CtClass[] interfaces;
        try {
            interfaces = clazz.getInterfaces();
        } catch (NotFoundException e) {
            throw new RuntimeException(e);
        }

        for (CtClass intf:interfaces) {
            map.put(intf.getName(), intf);
            getDeclaredInterfaces(intf, map);
        }

        return map;
    }

    @Override
    public int hashCode() {
        return getClass().hashCode() + clazz.hashCode();
    }

    @Override
    public boolean equals(Object o) {
        if (! (o instanceof Type))
            return false;

        return o.getClass() == getClass() && eq(clazz, ((Type)o).clazz);
    }

    static boolean eq(CtClass one, CtClass two) {
        return one == two || (one != null && two != null && one.getName().equals(two.getName()));
    }

    @Override
    public String toString() {
        if (this == BOGUS)
            return "BOGUS";
        if (this == UNINIT)
            return "UNINIT";
        if (this == RETURN_ADDRESS)
            return "RETURN ADDRESS";
        if (this == TOP)
            return "TOP";

        return clazz == null ? "null" : clazz.getName();
    }
}