rop/type/Type.java

/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.rop.type;

import com.android.dx.util.Hex;

import java.util.HashMap;

/**
 * Representation of a value type, such as may appear in a field, in a
 * local, on a stack, or in a method descriptor. Instances of this
 * class are generally interned and may be usefully compared with each
 * other using {@code ==}.
 */
public final class Type implements TypeBearer, Comparable<Type> {
    /**
     * {@code non-null;} intern table mapping string descriptors to
     * instances
     */
    private static final HashMap<String, Type> internTable =
        new HashMap<String, Type>(500);

    /** basic type constant for {@code void} */
    public static final int BT_VOID = 0;

    /** basic type constant for {@code boolean} */
    public static final int BT_BOOLEAN = 1;

    /** basic type constant for {@code byte} */
    public static final int BT_BYTE = 2;

    /** basic type constant for {@code char} */
    public static final int BT_CHAR = 3;

    /** basic type constant for {@code double} */
    public static final int BT_DOUBLE = 4;

    /** basic type constant for {@code float} */
    public static final int BT_FLOAT = 5;

    /** basic type constant for {@code int} */
    public static final int BT_INT = 6;

    /** basic type constant for {@code long} */
    public static final int BT_LONG = 7;

    /** basic type constant for {@code short} */
    public static final int BT_SHORT = 8;

    /** basic type constant for {@code Object} */
    public static final int BT_OBJECT = 9;

    /** basic type constant for a return address */
    public static final int BT_ADDR = 10;

    /** count of basic type constants */
    public static final int BT_COUNT = 11;

    /** {@code non-null;} instance representing {@code boolean} */
    public static final Type BOOLEAN = new Type("Z", BT_BOOLEAN);

    /** {@code non-null;} instance representing {@code byte} */
    public static final Type BYTE = new Type("B", BT_BYTE);

    /** {@code non-null;} instance representing {@code char} */
    public static final Type CHAR = new Type("C", BT_CHAR);

    /** {@code non-null;} instance representing {@code double} */
    public static final Type DOUBLE = new Type("D", BT_DOUBLE);

    /** {@code non-null;} instance representing {@code float} */
    public static final Type FLOAT = new Type("F", BT_FLOAT);

    /** {@code non-null;} instance representing {@code int} */
    public static final Type INT = new Type("I", BT_INT);

    /** {@code non-null;} instance representing {@code long} */
    public static final Type LONG = new Type("J", BT_LONG);

    /** {@code non-null;} instance representing {@code short} */
    public static final Type SHORT = new Type("S", BT_SHORT);

    /** {@code non-null;} instance representing {@code void} */
    public static final Type VOID = new Type("V", BT_VOID);

    /** {@code non-null;} instance representing a known-{@code null} */
    public static final Type KNOWN_NULL = new Type("<null>", BT_OBJECT);

    /** {@code non-null;} instance representing a subroutine return address */
    public static final Type RETURN_ADDRESS = new Type("<addr>", BT_ADDR);

    static {
        /*
         * Put all the primitive types into the intern table. This needs
         * to happen before the array types below get interned.
         */
        putIntern(BOOLEAN);
        putIntern(BYTE);
        putIntern(CHAR);
        putIntern(DOUBLE);
        putIntern(FLOAT);
        putIntern(INT);
        putIntern(LONG);
        putIntern(SHORT);
        /*
         * Note: VOID isn't put in the intern table, since it's special and
         * shouldn't be found by a normal call to intern().
         */
    }

    /**
     * {@code non-null;} instance representing
     * {@code java.lang.annotation.Annotation}
     */
    public static final Type ANNOTATION =
        intern("Ljava/lang/annotation/Annotation;");

    /** {@code non-null;} instance representing {@code java.lang.Class} */
    public static final Type CLASS = intern("Ljava/lang/Class;");

    /** {@code non-null;} instance representing {@code java.lang.Cloneable} */
    public static final Type CLONEABLE = intern("Ljava/lang/Cloneable;");

    /** {@code non-null;} instance representing {@code java.lang.Object} */
    public static final Type OBJECT = intern("Ljava/lang/Object;");

    /** {@code non-null;} instance representing {@code java.io.Serializable} */
    public static final Type SERIALIZABLE = intern("Ljava/io/Serializable;");

    /** {@code non-null;} instance representing {@code java.lang.String} */
    public static final Type STRING = intern("Ljava/lang/String;");

    /** {@code non-null;} instance representing {@code java.lang.Throwable} */
    public static final Type THROWABLE = intern("Ljava/lang/Throwable;");

    /**
     * {@code non-null;} instance representing {@code java.lang.Boolean}; the
     * suffix on the name helps disambiguate this from the instance
     * representing a primitive type
     */
    public static final Type BOOLEAN_CLASS = intern("Ljava/lang/Boolean;");

    /**
     * {@code non-null;} instance representing {@code java.lang.Byte}; the
     * suffix on the name helps disambiguate this from the instance
     * representing a primitive type
     */
    public static final Type BYTE_CLASS = intern("Ljava/lang/Byte;");

    /**
     * {@code non-null;} instance representing {@code java.lang.Character}; the
     * suffix on the name helps disambiguate this from the instance
     * representing a primitive type
     */
    public static final Type CHARACTER_CLASS = intern("Ljava/lang/Character;");

    /**
     * {@code non-null;} instance representing {@code java.lang.Double}; the
     * suffix on the name helps disambiguate this from the instance
     * representing a primitive type
     */
    public static final Type DOUBLE_CLASS = intern("Ljava/lang/Double;");

    /**
     * {@code non-null;} instance representing {@code java.lang.Float}; the
     * suffix on the name helps disambiguate this from the instance
     * representing a primitive type
     */
    public static final Type FLOAT_CLASS = intern("Ljava/lang/Float;");

    /**
     * {@code non-null;} instance representing {@code java.lang.Integer}; the
     * suffix on the name helps disambiguate this from the instance
     * representing a primitive type
     */
    public static final Type INTEGER_CLASS = intern("Ljava/lang/Integer;");

    /**
     * {@code non-null;} instance representing {@code java.lang.Long}; the
     * suffix on the name helps disambiguate this from the instance
     * representing a primitive type
     */
    public static final Type LONG_CLASS = intern("Ljava/lang/Long;");

    /**
     * {@code non-null;} instance representing {@code java.lang.Short}; the
     * suffix on the name helps disambiguate this from the instance
     * representing a primitive type
     */
    public static final Type SHORT_CLASS = intern("Ljava/lang/Short;");

    /**
     * {@code non-null;} instance representing {@code java.lang.Void}; the
     * suffix on the name helps disambiguate this from the instance
     * representing a primitive type
     */
    public static final Type VOID_CLASS = intern("Ljava/lang/Void;");

    /** {@code non-null;} instance representing {@code boolean[]} */
    public static final Type BOOLEAN_ARRAY = BOOLEAN.getArrayType();

    /** {@code non-null;} instance representing {@code byte[]} */
    public static final Type BYTE_ARRAY = BYTE.getArrayType();

    /** {@code non-null;} instance representing {@code char[]} */
    public static final Type CHAR_ARRAY = CHAR.getArrayType();

    /** {@code non-null;} instance representing {@code double[]} */
    public static final Type DOUBLE_ARRAY = DOUBLE.getArrayType();

    /** {@code non-null;} instance representing {@code float[]} */
    public static final Type FLOAT_ARRAY = FLOAT.getArrayType();

    /** {@code non-null;} instance representing {@code int[]} */
    public static final Type INT_ARRAY = INT.getArrayType();

    /** {@code non-null;} instance representing {@code long[]} */
    public static final Type LONG_ARRAY = LONG.getArrayType();

    /** {@code non-null;} instance representing {@code Object[]} */
    public static final Type OBJECT_ARRAY = OBJECT.getArrayType();

    /** {@code non-null;} instance representing {@code short[]} */
    public static final Type SHORT_ARRAY = SHORT.getArrayType();

    /** {@code non-null;} field descriptor for the type */
    private final String descriptor;

    /**
     * basic type corresponding to this type; one of the
     * {@code BT_*} constants
     */
    private final int basicType;

    /**
     * {@code >= -1;} for an uninitialized type, bytecode index that this
     * instance was allocated at; {@code Integer.MAX_VALUE} if it
     * was an incoming uninitialized instance; {@code -1} if this
     * is an <i>inititialized</i> instance
     */
    private final int newAt;

    /**
     * {@code null-ok;} the internal-form class name corresponding to
     * this type, if calculated; only valid if {@code this} is a
     * reference type and additionally not a return address
     */
    private String className;

    /**
     * {@code null-ok;} the type corresponding to an array of this type, if
     * calculated
     */
    private Type arrayType;

    /**
     * {@code null-ok;} the type corresponding to elements of this type, if
     * calculated; only valid if {@code this} is an array type
     */
    private Type componentType;

    /**
     * {@code null-ok;} the type corresponding to the initialized version of
     * this type, if this instance is in fact an uninitialized type
     */
    private Type initializedType;

    /**
     * Returns the unique instance corresponding to the type with the
     * given descriptor. See vmspec-2 sec4.3.2 for details on the
     * field descriptor syntax. This method does <i>not</i> allow
     * {@code "V"} (that is, type {@code void}) as a valid
     * descriptor.
     *
     * @param descriptor {@code non-null;} the descriptor
     * @return {@code non-null;} the corresponding instance
     * @throws IllegalArgumentException thrown if the descriptor has
     * invalid syntax
     */
    public static Type intern(String descriptor) {
        Type result;
        synchronized (internTable) {
            result = internTable.get(descriptor);
        }
        if (result != null) {
            return result;
        }

        char firstChar;
        try {
            firstChar = descriptor.charAt(0);
        } catch (IndexOutOfBoundsException ex) {
            // Translate the exception.
            throw new IllegalArgumentException("descriptor is empty");
        } catch (NullPointerException ex) {
            // Elucidate the exception.
            throw new NullPointerException("descriptor == null");
        }

        if (firstChar == '[') {
            /*
             * Recursively strip away array markers to get at the underlying
             * type, and build back on to form the result.
             */
            result = intern(descriptor.substring(1));
            return result.getArrayType();
        }

        /*
         * If the first character isn't '[' and it wasn't found in the
         * intern cache, then it had better be the descriptor for a class.
         */

        int length = descriptor.length();
        if ((firstChar != 'L') ||
            (descriptor.charAt(length - 1) != ';')) {
            throw new IllegalArgumentException("bad descriptor: " + descriptor);
        }

        /*
         * Validate the characters of the class name itself. Note that
         * vmspec-2 does not have a coherent definition for valid
         * internal-form class names, and the definition here is fairly
         * liberal: A name is considered valid as long as it doesn't
         * contain any of '[' ';' '.' '(' ')', and it has no more than one
         * '/' in a row, and no '/' at either end.
         */

        int limit = (length - 1); // Skip the final ';'.
        for (int i = 1; i < limit; i++) {
            char c = descriptor.charAt(i);
            switch (c) {
                case '[':
                case ';':
                case '.':
                case '(':
                case ')': {
                    throw new IllegalArgumentException("bad descriptor: " + descriptor);
                }
                case '/': {
                    if ((i == 1) ||
                        (i == (length - 1)) ||
                        (descriptor.charAt(i - 1) == '/')) {
                        throw new IllegalArgumentException("bad descriptor: " + descriptor);
                    }
                    break;
                }
            }
        }

        result = new Type(descriptor, BT_OBJECT);
        return putIntern(result);
    }

    /**
     * Returns the unique instance corresponding to the type with the
     * given descriptor, allowing {@code "V"} to return the type
     * for {@code void}. Other than that one caveat, this method
     * is identical to {@link #intern}.
     *
     * @param descriptor {@code non-null;} the descriptor
     * @return {@code non-null;} the corresponding instance
     * @throws IllegalArgumentException thrown if the descriptor has
     * invalid syntax
     */
    public static Type internReturnType(String descriptor) {
        try {
            if (descriptor.equals("V")) {
                // This is the one special case where void may be returned.
                return VOID;
            }
        } catch (NullPointerException ex) {
            // Elucidate the exception.
            throw new NullPointerException("descriptor == null");
        }

        return intern(descriptor);
    }

    /**
     * Returns the unique instance corresponding to the type of the
     * class with the given name. Calling this method is equivalent to
     * calling {@code intern(name)} if {@code name} begins
     * with {@code "["} and calling {@code intern("L" + name + ";")}
     * in all other cases.
     *
     * @param name {@code non-null;} the name of the class whose type
     * is desired
     * @return {@code non-null;} the corresponding type
     * @throws IllegalArgumentException thrown if the name has
     * invalid syntax
     */
    public static Type internClassName(String name) {
        if (name == null) {
            throw new NullPointerException("name == null");
        }

        if (name.startsWith("[")) {
            return intern(name);
        }

        return intern('L' + name + ';');
    }

    /**
     * Constructs an instance corresponding to an "uninitialized type."
     * This is a private constructor; use one of the public static
     * methods to get instances.
     *
     * @param descriptor {@code non-null;} the field descriptor for the type
     * @param basicType basic type corresponding to this type; one of the
     * {@code BT_*} constants
     * @param newAt {@code >= -1;} allocation bytecode index
     */
    private Type(String descriptor, int basicType, int newAt) {
        if (descriptor == null) {
            throw new NullPointerException("descriptor == null");
        }

        if ((basicType < 0) || (basicType >= BT_COUNT)) {
            throw new IllegalArgumentException("bad basicType");
        }

        if (newAt < -1) {
            throw new IllegalArgumentException("newAt < -1");
        }

        this.descriptor = descriptor;
        this.basicType = basicType;
        this.newAt = newAt;
        this.arrayType = null;
        this.componentType = null;
        this.initializedType = null;
    }

    /**
     * Constructs an instance corresponding to an "initialized type."
     * This is a private constructor; use one of the public static
     * methods to get instances.
     *
     * @param descriptor {@code non-null;} the field descriptor for the type
     * @param basicType basic type corresponding to this type; one of the
     * {@code BT_*} constants
     */
    private Type(String descriptor, int basicType) {
        this(descriptor, basicType, -1);
    }

    /** {@inheritDoc} */
    @Override
    public boolean equals(Object other) {
        if (this == other) {
            /*
             * Since externally-visible types are interned, this check
             * helps weed out some easy cases.
             */
            return true;
        }

        if (!(other instanceof Type)) {
            return false;
        }

        return descriptor.equals(((Type) other).descriptor);
    }

    /** {@inheritDoc} */
    @Override
    public int hashCode() {
        return descriptor.hashCode();
    }

    /** {@inheritDoc} */
    public int compareTo(Type other) {
        return descriptor.compareTo(other.descriptor);
    }

    /** {@inheritDoc} */
    @Override
    public String toString() {
        return descriptor;
    }

    /** {@inheritDoc} */
    public String toHuman() {
        switch (basicType) {
            case BT_VOID:    return "void";
            case BT_BOOLEAN: return "boolean";
            case BT_BYTE:    return "byte";
            case BT_CHAR:    return "char";
            case BT_DOUBLE:  return "double";
            case BT_FLOAT:   return "float";
            case BT_INT:     return "int";
            case BT_LONG:    return "long";
            case BT_SHORT:   return "short";
            case BT_OBJECT:  break;
            default:         return descriptor;
        }

        if (isArray()) {
            return getComponentType().toHuman() + "[]";
        }

        // Remove the "L...;" around the type and convert "/" to ".".
        return getClassName().replace("/", ".");
    }

    /** {@inheritDoc} */
    public Type getType() {
        return this;
    }

    /** {@inheritDoc} */
    public Type getFrameType() {
        switch (basicType) {
            case BT_BOOLEAN:
            case BT_BYTE:
            case BT_CHAR:
            case BT_INT:
            case BT_SHORT: {
                return INT;
            }
        }

        return this;
    }

    /** {@inheritDoc} */
    public int getBasicType() {
        return basicType;
    }

    /** {@inheritDoc} */
    public int getBasicFrameType() {
        switch (basicType) {
            case BT_BOOLEAN:
            case BT_BYTE:
            case BT_CHAR:
            case BT_INT:
            case BT_SHORT: {
                return BT_INT;
            }
        }

        return basicType;
    }

    /** {@inheritDoc} */
    public boolean isConstant() {
        return false;
    }

    /**
     * Gets the descriptor.
     *
     * @return {@code non-null;} the descriptor
     */
    public String getDescriptor() {
        return descriptor;
    }

    /**
     * Gets the name of the class this type corresponds to, in internal
     * form. This method is only valid if this instance is for a
     * normal reference type (that is, a reference type and
     * additionally not a return address).
     *
     * @return {@code non-null;} the internal-form class name
     */
    public String getClassName() {
        if (className == null) {
            if (!isReference()) {
                throw new IllegalArgumentException("not an object type: " +
                                                   descriptor);
            }

            if (descriptor.charAt(0) == '[') {
                className = descriptor;
            } else {
                className = descriptor.substring(1, descriptor.length() - 1);
            }
        }

        return className;
    }

    /**
     * Gets the category. Most instances are category 1. {@code long}
     * and {@code double} are the only category 2 types.
     *
     * @see #isCategory1
     * @see #isCategory2
     * @return the category
     */
    public int getCategory() {
        switch (basicType) {
            case BT_LONG:
            case BT_DOUBLE: {
                return 2;
            }
        }

        return 1;
    }

    /**
     * Returns whether or not this is a category 1 type.
     *
     * @see #getCategory
     * @see #isCategory2
     * @return whether or not this is a category 1 type
     */
    public boolean isCategory1() {
        switch (basicType) {
            case BT_LONG:
            case BT_DOUBLE: {
                return false;
            }
        }

        return true;
    }

    /**
     * Returns whether or not this is a category 2 type.
     *
     * @see #getCategory
     * @see #isCategory1
     * @return whether or not this is a category 2 type
     */
    public boolean isCategory2() {
        switch (basicType) {
            case BT_LONG:
            case BT_DOUBLE: {
                return true;
            }
        }

        return false;
    }

    /**
     * Gets whether this type is "intlike." An intlike type is one which, when
     * placed on a stack or in a local, is automatically converted to an
     * {@code int}.
     *
     * @return whether this type is "intlike"
     */
    public boolean isIntlike() {
        switch (basicType) {
            case BT_BOOLEAN:
            case BT_BYTE:
            case BT_CHAR:
            case BT_INT:
            case BT_SHORT: {
                return true;
            }
        }

        return false;
    }

    /**
     * Gets whether this type is a primitive type. All types are either
     * primitive or reference types.
     *
     * @return whether this type is primitive
     */
    public boolean isPrimitive() {
        switch (basicType) {
            case BT_BOOLEAN:
            case BT_BYTE:
            case BT_CHAR:
            case BT_DOUBLE:
            case BT_FLOAT:
            case BT_INT:
            case BT_LONG:
            case BT_SHORT:
            case BT_VOID: {
                return true;
            }
        }

        return false;
    }

    /**
     * Gets whether this type is a normal reference type. A normal
     * reference type is a reference type that is not a return
     * address. This method is just convenient shorthand for
     * {@code getBasicType() == Type.BT_OBJECT}.
     *
     * @return whether this type is a normal reference type
     */
    public boolean isReference() {
        return (basicType == BT_OBJECT);
    }

    /**
     * Gets whether this type is an array type. If this method returns
     * {@code true}, then it is safe to use {@link #getComponentType}
     * to determine the component type.
     *
     * @return whether this type is an array type
     */
    public boolean isArray() {
        return (descriptor.charAt(0) == '[');
    }

    /**
     * Gets whether this type is an array type or is a known-null, and
     * hence is compatible with array types.
     *
     * @return whether this type is an array type
     */
    public boolean isArrayOrKnownNull() {
        return isArray() || equals(KNOWN_NULL);
    }

    /**
     * Gets whether this type represents an uninitialized instance. An
     * uninitialized instance is what one gets back from the {@code new}
     * opcode, and remains uninitialized until a valid constructor is
     * invoked on it.
     *
     * @return whether this type is "uninitialized"
     */
    public boolean isUninitialized() {
        return (newAt >= 0);
    }

    /**
     * Gets the bytecode index at which this uninitialized type was
     * allocated.  This returns {@code Integer.MAX_VALUE} if this
     * type is an uninitialized incoming parameter (i.e., the
     * {@code this} of an {@code <init>} method) or
     * {@code -1} if this type is in fact <i>initialized</i>.
     *
     * @return {@code >= -1;} the allocation bytecode index
     */
    public int getNewAt() {
        return newAt;
    }

    /**
     * Gets the initialized type corresponding to this instance, but only
     * if this instance is in fact an uninitialized object type.
     *
     * @return {@code non-null;} the initialized type
     */
    public Type getInitializedType() {
        if (initializedType == null) {
            throw new IllegalArgumentException("initialized type: " +
                                               descriptor);
        }

        return initializedType;
    }

    /**
     * Gets the type corresponding to an array of this type.
     *
     * @return {@code non-null;} the array type
     */
    public Type getArrayType() {
        if (arrayType == null) {
            arrayType = putIntern(new Type('[' + descriptor, BT_OBJECT));
        }

        return arrayType;
    }

    /**
     * Gets the component type of this type. This method is only valid on
     * array types.
     *
     * @return {@code non-null;} the component type
     */
    public Type getComponentType() {
        if (componentType == null) {
            if (descriptor.charAt(0) != '[') {
                throw new IllegalArgumentException("not an array type: " +
                                                   descriptor);
            }
            componentType = intern(descriptor.substring(1));
        }

        return componentType;
    }

    /**
     * Returns a new interned instance which is identical to this one, except
     * it is indicated as uninitialized and allocated at the given bytecode
     * index. This instance must be an initialized object type.
     *
     * @param newAt {@code >= 0;} the allocation bytecode index
     * @return {@code non-null;} an appropriately-constructed instance
     */
    public Type asUninitialized(int newAt) {
        if (newAt < 0) {
            throw new IllegalArgumentException("newAt < 0");
        }

        if (!isReference()) {
            throw new IllegalArgumentException("not a reference type: " +
                                               descriptor);
        }

        if (isUninitialized()) {
            /*
             * Dealing with uninitialized types as a starting point is
             * a pain, and it's not clear that it'd ever be used, so
             * just disallow it.
             */
            throw new IllegalArgumentException("already uninitialized: " +
                                               descriptor);
        }

        /*
         * Create a new descriptor that is unique and shouldn't conflict
         * with "normal" type descriptors
         */
        String newDesc = 'N' + Hex.u2(newAt) + descriptor;
        Type result = new Type(newDesc, BT_OBJECT, newAt);
        result.initializedType = this;
        return putIntern(result);
    }

    /**
     * Puts the given instance in the intern table if it's not already
     * there. If a conflicting value is already in the table, then leave it.
     * Return the interned value.
     *
     * @param type {@code non-null;} instance to make interned
     * @return {@code non-null;} the actual interned object
     */
    private static Type putIntern(Type type) {
        synchronized (internTable) {
            String descriptor = type.getDescriptor();
            Type already = internTable.get(descriptor);
            if (already != null) {
                return already;
            }
            internTable.put(descriptor, type);
            return type;
        }
    }
}