cf/code/Merger.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.cf.code;

import com.android.dx.rop.type.Type;
import com.android.dx.rop.type.TypeBearer;
import com.android.dx.util.Hex;

/**
 * Utility methods to merge various frame information.
 */
public final class Merger {
    /**
     * This class is uninstantiable.
     */
    private Merger() {
        // This space intentionally left blank.
    }

    /**
     * Merges two locals arrays. If the merged result is the same as the first
     * argument, then return the first argument (not a copy).
     *
     * @param locals1 {@code non-null;} a locals array
     * @param locals2 {@code non-null;} another locals array
     * @return {@code non-null;} the result of merging the two locals arrays
     */
    public static OneLocalsArray mergeLocals(OneLocalsArray locals1,
                                          OneLocalsArray locals2) {
        if (locals1 == locals2) {
            // Easy out.
            return locals1;
        }

        int sz = locals1.getMaxLocals();
        OneLocalsArray result = null;

        if (locals2.getMaxLocals() != sz) {
            throw new SimException("mismatched maxLocals values");
        }

        for (int i = 0; i < sz; i++) {
            TypeBearer tb1 = locals1.getOrNull(i);
            TypeBearer tb2 = locals2.getOrNull(i);
            TypeBearer resultType = mergeType(tb1, tb2);
            if (resultType != tb1) {
                /*
                 * We only need to do anything when the result differs
                 * from what is in the first array, since that's what the
                 * result gets initialized to.
                 */
                if (result == null) {
                    result = locals1.copy();
                }

                if (resultType == null) {
                    result.invalidate(i);
                } else {
                    result.set(i, resultType);
                }
            }
        }

        if (result == null) {
            return locals1;
        }

        result.setImmutable();
        return result;
    }

    /**
     * Merges two stacks. If the merged result is the same as the first
     * argument, then return the first argument (not a copy).
     *
     * @param stack1 {@code non-null;} a stack
     * @param stack2 {@code non-null;} another stack
     * @return {@code non-null;} the result of merging the two stacks
     */
    public static ExecutionStack mergeStack(ExecutionStack stack1,
                                            ExecutionStack stack2) {
        if (stack1 == stack2) {
            // Easy out.
            return stack1;
        }

        int sz = stack1.size();
        ExecutionStack result = null;

        if (stack2.size() != sz) {
            throw new SimException("mismatched stack depths");
        }

        for (int i = 0; i < sz; i++) {
            TypeBearer tb1 = stack1.peek(i);
            TypeBearer tb2 = stack2.peek(i);
            TypeBearer resultType = mergeType(tb1, tb2);
            if (resultType != tb1) {
                /*
                 * We only need to do anything when the result differs
                 * from what is in the first stack, since that's what the
                 * result gets initialized to.
                 */
                if (result == null) {
                    result = stack1.copy();
                }

                try {
                    if (resultType == null) {
                        throw new SimException("incompatible: " + tb1 + ", " +
                                               tb2);
                    } else {
                        result.change(i, resultType);
                    }
                } catch (SimException ex) {
                    ex.addContext("...while merging stack[" + Hex.u2(i) + "]");
                    throw ex;
                }
            }
        }

        if (result == null) {
            return stack1;
        }

        result.setImmutable();
        return result;
    }

    /**
     * Merges two frame types.
     *
     * @param ft1 {@code non-null;} a frame type
     * @param ft2 {@code non-null;} another frame type
     * @return {@code non-null;} the result of merging the two types
     */
    public static TypeBearer mergeType(TypeBearer ft1, TypeBearer ft2) {
        if ((ft1 == null) || ft1.equals(ft2)) {
            return ft1;
        } else if (ft2 == null) {
            return null;
        } else {
            Type type1 = ft1.getType();
            Type type2 = ft2.getType();

            if (type1 == type2) {
                return type1;
            } else if (type1.isReference() && type2.isReference()) {
                if (type1 == Type.KNOWN_NULL) {
                    /*
                     * A known-null merges with any other reference type to
                     * be that reference type.
                     */
                    return type2;
                } else if (type2 == Type.KNOWN_NULL) {
                    /*
                     * The same as above, but this time it's type2 that's
                     * the known-null.
                     */
                    return type1;
                } else if (type1.isArray() && type2.isArray()) {
                    TypeBearer componentUnion =
                        mergeType(type1.getComponentType(),
                                type2.getComponentType());
                    if (componentUnion == null) {
                        /*
                         * At least one of the types is a primitive type,
                         * so the merged result is just Object.
                         */
                        return Type.OBJECT;
                    }
                    return ((Type) componentUnion).getArrayType();
                } else {
                    /*
                     * All other unequal reference types get merged to be
                     * Object in this phase. This is fine here, but it
                     * won't be the right thing to do in the verifier.
                     */
                    return Type.OBJECT;
                }
            } else if (type1.isIntlike() && type2.isIntlike()) {
                /*
                 * Merging two non-identical int-like types results in
                 * the type int.
                 */
                return Type.INT;
            } else {
                return null;
            }
        }
    }

    /**
     * Returns whether the given supertype is possibly assignable from
     * the given subtype. This takes into account primitiveness,
     * int-likeness, known-nullness, and array dimensions, but does
     * not assume anything about class hierarchy other than that the
     * type {@code Object} is the supertype of all reference
     * types and all arrays are assignable to
     * {@code Serializable} and {@code Cloneable}.
     *
     * @param supertypeBearer {@code non-null;} the supertype
     * @param subtypeBearer {@code non-null;} the subtype
     */
    public static boolean isPossiblyAssignableFrom(TypeBearer supertypeBearer,
            TypeBearer subtypeBearer) {
        Type supertype = supertypeBearer.getType();
        Type subtype = subtypeBearer.getType();

        if (supertype.equals(subtype)) {
            // Easy out.
            return true;
        }

        int superBt = supertype.getBasicType();
        int subBt = subtype.getBasicType();

        // Treat return types as Object for the purposes of this method.

        if (superBt == Type.BT_ADDR) {
            supertype = Type.OBJECT;
            superBt = Type.BT_OBJECT;
        }

        if (subBt == Type.BT_ADDR) {
            subtype = Type.OBJECT;
            subBt = Type.BT_OBJECT;
        }

        if ((superBt != Type.BT_OBJECT) || (subBt != Type.BT_OBJECT)) {
            /*
             * No two distinct primitive types are assignable in this sense,
             * unless they are both int-like.
             */
            return supertype.isIntlike() && subtype.isIntlike();
        }

        // At this point, we know both types are reference types.

        if (supertype == Type.KNOWN_NULL) {
            /*
             * A known-null supertype is only assignable from another
             * known-null (handled in the easy out at the top of the
             * method).
             */
            return false;
        } else if (subtype == Type.KNOWN_NULL) {
            /*
             * A known-null subtype is in fact assignable to any
             * reference type.
             */
            return true;
        } else if (supertype == Type.OBJECT) {
            /*
             * Object is assignable from any reference type.
             */
            return true;
        } else if (supertype.isArray()) {
            // The supertype is an array type.
            if (! subtype.isArray()) {
                // The subtype isn't an array, and so can't be assignable.
                return false;
            }

            /*
             * Strip off as many matched component types from both
             * types as possible, and check the assignability of the
             * results.
             */
            do {
                supertype = supertype.getComponentType();
                subtype = subtype.getComponentType();
            } while (supertype.isArray() && subtype.isArray());

            return isPossiblyAssignableFrom(supertype, subtype);
        } else if (subtype.isArray()) {
            /*
             * Other than Object (handled above), array types are
             * assignable only to Serializable and Cloneable.
             */
            return (supertype == Type.SERIALIZABLE) ||
                (supertype == Type.CLONEABLE);
        } else {
            /*
             * All other unequal reference types are considered at
             * least possibly assignable.
             */
            return true;
        }
    }
}