dx/src/com/android/dx/cf/code/Merger.java - platform/dalvik2 - Git at Google

 /*
  * 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;
         }
     }
 }
	/*
	* 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;
	}
	}
	}