2.1/user/src/com/google/gwt/user/rebind/rpc/TypeConstrainer.java - gwt - Git at Google

 /*
  * Copyright 2008 Google Inc.
  *
  * 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.google.gwt.user.rebind.rpc;

 import com.google.gwt.core.ext.typeinfo.JArrayType;
 import com.google.gwt.core.ext.typeinfo.JClassType;
 import com.google.gwt.core.ext.typeinfo.JGenericType;
 import com.google.gwt.core.ext.typeinfo.JParameterizedType;
 import com.google.gwt.core.ext.typeinfo.JRawType;
 import com.google.gwt.core.ext.typeinfo.JRealClassType;
 import com.google.gwt.core.ext.typeinfo.JType;
 import com.google.gwt.core.ext.typeinfo.JTypeParameter;
 import com.google.gwt.core.ext.typeinfo.JWildcardType;
 import com.google.gwt.core.ext.typeinfo.TypeOracle;

 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;

 /**
  * This class defines the method
  * {@link #constrainTypeBy(JClassType, JClassType)}.
  */
 public class TypeConstrainer {
   /**
    * Check whether two base types have any subclasses in common. Note: this
    * could surely be implemented much more efficiently.
    */
   private static boolean baseTypesOverlap(JClassType type1, JClassType type2) {
     assert (type1 == getBaseType(type1));
     assert (type2 == getBaseType(type2));

     if (type1 == type2) {
       return true;
     }

     HashSet<JClassType> subtypes1 = new HashSet<JClassType>();
     subtypes1.add(type1);
     for (JClassType sub1 : type1.getSubtypes()) {
       subtypes1.add(getBaseType(sub1));
     }

     List<JClassType> subtypes2 = new ArrayList<JClassType>();
     subtypes2.add(type2);
     for (JClassType sub2 : type2.getSubtypes()) {
       subtypes2.add(getBaseType(sub2));
     }

     for (JClassType sub2 : subtypes2) {
       if (subtypes1.contains(sub2)) {
         return true;
       }
     }

     return false;
   }

   private static JClassType getBaseType(JClassType type) {
     return SerializableTypeOracleBuilder.getBaseType(type);
   }

   private static boolean isRealOrParameterized(JClassType type) {
     if (type.isParameterized() != null) {
       return true;
     }
     if (type instanceof JRealClassType) {
       return true;
     }
     return false;
   }

   private static JClassType[] makeArray(JClassType... classTypes) {
     return classTypes;
   }

   /**
    * Check whether <code>param</code> occurs anywhere within <code>type</code>.
    */
   private static boolean occurs(final JTypeParameter param, JClassType type) {
     class OccursVisitor extends JTypeVisitor {
       boolean foundIt = false;

       @Override
       public void endVisit(JTypeParameter seenParam) {
         if (seenParam == param) {
           foundIt = true;
         }
       }
     }

     OccursVisitor visitor = new OccursVisitor();
     visitor.accept(type);
     return visitor.foundIt;
   }

   private int freshTypeVariableCounter;

   private final TypeOracle typeOracle;

   public TypeConstrainer(TypeOracle typeOracle) {
     this.typeOracle = typeOracle;
   }

   /**
    * Return a subtype of <code>subType</code> that includes all values in both
    * <code>subType</code> and <code>superType</code>. The returned type
    * must have the same base type as <code>subType</code>. If there are
    * definitely no such values, return <code>null</code>.
    */
   public JClassType constrainTypeBy(JClassType subType, JClassType superType) {
     JParameterizedType superAsParameterized = superType.isParameterized();
     if (superAsParameterized == null) {
       // If the supertype is not parameterized, it will not be possible to
       // constrain
       // the subtype further.
       return subType;
     }

     // Replace each wildcard in the subType with a fresh type variable.
     // These type variables will be the ones that are constrained.
     Map<JTypeParameter, JClassType> constraints = new HashMap<JTypeParameter, JClassType>();
     JClassType subWithWildcardsReplaced = replaceWildcardsWithFreshTypeVariables(
         subType, constraints);

     // Rewrite subType so that it has the same base type as superType.
     JParameterizedType subAsParameterized = subWithWildcardsReplaced.asParameterizationOf(superAsParameterized.getBaseType());
     if (subAsParameterized == null) {
       // The subtype's base does not inherit from the supertype's base,
       // so again no constraint will be possible.
       return subType;
     }

     // Check the rewritten type against superType
     if (!typesMatch(subAsParameterized, superAsParameterized, constraints)) {
       // The types are completely incompatible
       return null;
     }

     // Apply the revised constraints to the original type
     return substitute(subWithWildcardsReplaced, constraints);
   }

   /**
    * Check whether two types can have any values in common. The
    * <code>constraints</code> field holds known constraints for type
    * parameters that appear in <code>type1</code>; this method may take
    * advantage of those constraints in its decision, and it may tighten them so
    * long as the tightening does not reject any values from the overlap of the
    * two types.
    *
    * As an invariant, no key in <code>constraints</code> may occur inside any
    * value in <code>constraints</code>.
    *
    * Note that this algorithm looks for overlap matches in the arguments of
    * parameterized types rather than looking for exact matches. Looking for
    * overlaps simplifies the algorithm but returns true more often than it has
    * to.
    */
   boolean typesMatch(JClassType type1, JClassType type2,
       Map<JTypeParameter, JClassType> constraints) {
     JGenericType type1Generic = type1.isGenericType();
     if (type1Generic != null) {
       return typesMatch(type1Generic.asParameterizedByWildcards(), type2,
           constraints);
     }

     JGenericType type2Generic = type2.isGenericType();
     if (type2Generic != null) {
       return typesMatch(type1, type2Generic.asParameterizedByWildcards(),
           constraints);
     }

     JWildcardType type1Wild = type1.isWildcard();
     if (type1Wild != null) {
       return typesMatch(type1Wild.getUpperBound(), type2, constraints);
     }

     JWildcardType type2Wild = type2.isWildcard();
     if (type2Wild != null) {
       return typesMatch(type1, type2Wild.getUpperBound(), constraints);
     }

     JRawType type1Raw = type1.isRawType();
     if (type1Raw != null) {
       return typesMatch(type1Raw.asParameterizedByWildcards(), type2,
           constraints);
     }

     JRawType type2Raw = type2.isRawType();
     if (type2Raw != null) {
       return typesMatch(type1, type2Raw.asParameterizedByWildcards(),
           constraints);
     }

     // The following assertions are known to be true, given the tests above.
 //    assert (type1Generic == null);
 //    assert (type2Generic == null);
 //    assert (type1Wild == null);
 //    assert (type2Wild == null);
 //    assert (type1Raw == null);
 //    assert (type2Raw == null);

     if (type1 == type2) {
       return true;
     }

     if (constraints.containsKey(type1)) {
       JTypeParameter type1Parameter = (JTypeParameter) type1;
       JClassType type2Class = type2;
       JClassType type1Bound = constraints.get(type1Parameter);
       assert (!occurs(type1Parameter, type1Bound));
       if (!typesMatch(type1Bound, type2, constraints)) {
         return false;
       }

       if (type1Bound.isAssignableFrom(type2Class)) {
         constraints.put(type1Parameter, type2Class);
       }
     }

     if (type1 == typeOracle.getJavaLangObject()) {
       return true;
     }

     if (type2 == typeOracle.getJavaLangObject()) {
       return true;
     }

     JTypeParameter type1Param = type1.isTypeParameter();
     if (type1Param != null) {
       // It would be nice to check that type1Param's bound is a match
       // for type2, but that can introduce infinite recursions.
       return true;
     }

     JTypeParameter type2Param = type2.isTypeParameter();
     if (type2Param != null) {
       // It would be nice to check that type1Param's bound is a match
       // for type2, but that can introduce infinite recursions.
       return true;
     }

     JArrayType type1Array = type1.isArray();
     JArrayType type2Array = type2.isArray();
     if (type1Array != null && type2Array != null) {
       if (typesMatch(type1Array.getComponentType(),
           type2Array.getComponentType(), constraints)) {
         return true;
       }
     }

     if (isRealOrParameterized(type1) && isRealOrParameterized(type2)) {
       JClassType baseType1 = getBaseType(type1);
       JClassType baseType2 = getBaseType(type2);
       JParameterizedType type1Parameterized = type1.isParameterized();
       JParameterizedType type2Parameterized = type2.isParameterized();

       if (baseType1 == baseType2 && type1Parameterized != null
           && type2Parameterized != null) {
         // type1 and type2 are parameterized types with the same base type;
         // compare their arguments
         JClassType[] args1 = type1Parameterized.getTypeArgs();
         JClassType[] args2 = type2Parameterized.getTypeArgs();
         boolean allMatch = true;
         for (int i = 0; i < args1.length; i++) {
           if (!typesMatch(args1[i], args2[i], constraints)) {
             allMatch = false;
           }
         }

         if (allMatch) {
           return true;
         }
       } else {
         // The types have different base types, so just compare the base types
         // for overlap.
         if (baseTypesOverlap(baseType1, baseType2)) {
           return true;
         }
       }
     }

     return false;
   }

   /**
    * The same as {@link #typesMatch(JClassType, JClassType, Map)}, but
    * additionally support primitive types as well as class types.
    */
   boolean typesMatch(JType type1, JType type2,
       Map<JTypeParameter, JClassType> constraints) {
     if (type1 == type2) {
       // This covers the case where both are primitives
       return true;
     }

     JClassType type1Class = type1.isClassOrInterface();
     JClassType type2Class = type2.isClassOrInterface();
     if (type1Class != null && type2Class != null
         && typesMatch(type1Class, type2Class, constraints)) {
       return true;
     }

     return false;
   }

   /**
    * Replace all wildcards in <code>type</code> with a fresh type variable.
    * For each type variable created, add an entry in <code>constraints</code>
    * mapping the type variable to its upper bound.
    */
   private JClassType replaceWildcardsWithFreshTypeVariables(JClassType type,
       final Map<JTypeParameter, JClassType> constraints) {

     JModTypeVisitor replacer = new JModTypeVisitor() {
       @Override
       public void endVisit(JWildcardType wildcardType) {
         JTypeParameter newParam = new JTypeParameter("TP$"
             + freshTypeVariableCounter++, -1);
         newParam.setBounds(makeArray(typeOracle.getJavaLangObject()));
         constraints.put(newParam, wildcardType.getUpperBound());
         replacement = newParam;
       }
     };

     return replacer.transform(type);
   }

   /**
    * Substitute all occurrences in <code>type</code> of type parameters in
    * <code>constraints</code> for a wildcard bounded by the parameter's entry
    * in <code>constraints</code>. If the argument is <code>null</code>,
    * return <code>null</code>.
    */
   private JClassType substitute(JClassType type,
       final Map<JTypeParameter, JClassType> constraints) {
     JModTypeVisitor substituter = new JModTypeVisitor() {
       @Override
       public void endVisit(JTypeParameter param) {
         JClassType constr = constraints.get(param);
         if (constr != null) {
           replacement = constr;
         }
       }
     };
     return substituter.transform(type);
   }
 }
	/*
	* Copyright 2008 Google Inc.
	*
	* 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.google.gwt.user.rebind.rpc;

	import com.google.gwt.core.ext.typeinfo.JArrayType;
	import com.google.gwt.core.ext.typeinfo.JClassType;
	import com.google.gwt.core.ext.typeinfo.JGenericType;
	import com.google.gwt.core.ext.typeinfo.JParameterizedType;
	import com.google.gwt.core.ext.typeinfo.JRawType;
	import com.google.gwt.core.ext.typeinfo.JRealClassType;
	import com.google.gwt.core.ext.typeinfo.JType;
	import com.google.gwt.core.ext.typeinfo.JTypeParameter;
	import com.google.gwt.core.ext.typeinfo.JWildcardType;
	import com.google.gwt.core.ext.typeinfo.TypeOracle;

	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Map;

	/**
	* This class defines the method
	* {@link #constrainTypeBy(JClassType, JClassType)}.
	*/
	public class TypeConstrainer {
	/**
	* Check whether two base types have any subclasses in common. Note: this
	* could surely be implemented much more efficiently.
	*/
	private static boolean baseTypesOverlap(JClassType type1, JClassType type2) {
	assert (type1 == getBaseType(type1));
	assert (type2 == getBaseType(type2));

	if (type1 == type2) {
	return true;
	}

	HashSet<JClassType> subtypes1 = new HashSet<JClassType>();
	subtypes1.add(type1);
	for (JClassType sub1 : type1.getSubtypes()) {
	subtypes1.add(getBaseType(sub1));
	}

	List<JClassType> subtypes2 = new ArrayList<JClassType>();
	subtypes2.add(type2);
	for (JClassType sub2 : type2.getSubtypes()) {
	subtypes2.add(getBaseType(sub2));
	}

	for (JClassType sub2 : subtypes2) {
	if (subtypes1.contains(sub2)) {
	return true;
	}
	}

	return false;
	}

	private static JClassType getBaseType(JClassType type) {
	return SerializableTypeOracleBuilder.getBaseType(type);
	}

	private static boolean isRealOrParameterized(JClassType type) {
	if (type.isParameterized() != null) {
	return true;
	}
	if (type instanceof JRealClassType) {
	return true;
	}
	return false;
	}

	private static JClassType[] makeArray(JClassType... classTypes) {
	return classTypes;
	}

	/**
	* Check whether <code>param</code> occurs anywhere within <code>type</code>.
	*/
	private static boolean occurs(final JTypeParameter param, JClassType type) {
	class OccursVisitor extends JTypeVisitor {
	boolean foundIt = false;

	@Override
	public void endVisit(JTypeParameter seenParam) {
	if (seenParam == param) {
	foundIt = true;
	}
	}
	}

	OccursVisitor visitor = new OccursVisitor();
	visitor.accept(type);
	return visitor.foundIt;
	}

	private int freshTypeVariableCounter;

	private final TypeOracle typeOracle;

	public TypeConstrainer(TypeOracle typeOracle) {
	this.typeOracle = typeOracle;
	}

	/**
	* Return a subtype of <code>subType</code> that includes all values in both
	* <code>subType</code> and <code>superType</code>. The returned type
	* must have the same base type as <code>subType</code>. If there are
	* definitely no such values, return <code>null</code>.
	*/
	public JClassType constrainTypeBy(JClassType subType, JClassType superType) {
	JParameterizedType superAsParameterized = superType.isParameterized();
	if (superAsParameterized == null) {
	// If the supertype is not parameterized, it will not be possible to
	// constrain
	// the subtype further.
	return subType;
	}

	// Replace each wildcard in the subType with a fresh type variable.
	// These type variables will be the ones that are constrained.
	Map<JTypeParameter, JClassType> constraints = new HashMap<JTypeParameter, JClassType>();
	JClassType subWithWildcardsReplaced = replaceWildcardsWithFreshTypeVariables(
	subType, constraints);

	// Rewrite subType so that it has the same base type as superType.
	JParameterizedType subAsParameterized = subWithWildcardsReplaced.asParameterizationOf(superAsParameterized.getBaseType());
	if (subAsParameterized == null) {
	// The subtype's base does not inherit from the supertype's base,
	// so again no constraint will be possible.
	return subType;
	}

	// Check the rewritten type against superType
	if (!typesMatch(subAsParameterized, superAsParameterized, constraints)) {
	// The types are completely incompatible
	return null;
	}

	// Apply the revised constraints to the original type
	return substitute(subWithWildcardsReplaced, constraints);
	}

	/**
	* Check whether two types can have any values in common. The
	* <code>constraints</code> field holds known constraints for type
	* parameters that appear in <code>type1</code>; this method may take
	* advantage of those constraints in its decision, and it may tighten them so
	* long as the tightening does not reject any values from the overlap of the
	* two types.
	*
	* As an invariant, no key in <code>constraints</code> may occur inside any
	* value in <code>constraints</code>.
	*
	* Note that this algorithm looks for overlap matches in the arguments of
	* parameterized types rather than looking for exact matches. Looking for
	* overlaps simplifies the algorithm but returns true more often than it has
	* to.
	*/
	boolean typesMatch(JClassType type1, JClassType type2,
	Map<JTypeParameter, JClassType> constraints) {
	JGenericType type1Generic = type1.isGenericType();
	if (type1Generic != null) {
	return typesMatch(type1Generic.asParameterizedByWildcards(), type2,
	constraints);
	}

	JGenericType type2Generic = type2.isGenericType();
	if (type2Generic != null) {
	return typesMatch(type1, type2Generic.asParameterizedByWildcards(),
	constraints);
	}

	JWildcardType type1Wild = type1.isWildcard();
	if (type1Wild != null) {
	return typesMatch(type1Wild.getUpperBound(), type2, constraints);
	}

	JWildcardType type2Wild = type2.isWildcard();
	if (type2Wild != null) {
	return typesMatch(type1, type2Wild.getUpperBound(), constraints);
	}

	JRawType type1Raw = type1.isRawType();
	if (type1Raw != null) {
	return typesMatch(type1Raw.asParameterizedByWildcards(), type2,
	constraints);
	}

	JRawType type2Raw = type2.isRawType();
	if (type2Raw != null) {
	return typesMatch(type1, type2Raw.asParameterizedByWildcards(),
	constraints);
	}

	// The following assertions are known to be true, given the tests above.
	// assert (type1Generic == null);
	// assert (type2Generic == null);
	// assert (type1Wild == null);
	// assert (type2Wild == null);
	// assert (type1Raw == null);
	// assert (type2Raw == null);

	if (type1 == type2) {
	return true;
	}

	if (constraints.containsKey(type1)) {
	JTypeParameter type1Parameter = (JTypeParameter) type1;
	JClassType type2Class = type2;
	JClassType type1Bound = constraints.get(type1Parameter);
	assert (!occurs(type1Parameter, type1Bound));
	if (!typesMatch(type1Bound, type2, constraints)) {
	return false;
	}

	if (type1Bound.isAssignableFrom(type2Class)) {
	constraints.put(type1Parameter, type2Class);
	}
	}

	if (type1 == typeOracle.getJavaLangObject()) {
	return true;
	}

	if (type2 == typeOracle.getJavaLangObject()) {
	return true;
	}

	JTypeParameter type1Param = type1.isTypeParameter();
	if (type1Param != null) {
	// It would be nice to check that type1Param's bound is a match
	// for type2, but that can introduce infinite recursions.
	return true;
	}

	JTypeParameter type2Param = type2.isTypeParameter();
	if (type2Param != null) {
	// It would be nice to check that type1Param's bound is a match
	// for type2, but that can introduce infinite recursions.
	return true;
	}

	JArrayType type1Array = type1.isArray();
	JArrayType type2Array = type2.isArray();
	if (type1Array != null && type2Array != null) {
	if (typesMatch(type1Array.getComponentType(),
	type2Array.getComponentType(), constraints)) {
	return true;
	}
	}

	if (isRealOrParameterized(type1) && isRealOrParameterized(type2)) {
	JClassType baseType1 = getBaseType(type1);
	JClassType baseType2 = getBaseType(type2);
	JParameterizedType type1Parameterized = type1.isParameterized();
	JParameterizedType type2Parameterized = type2.isParameterized();

	if (baseType1 == baseType2 && type1Parameterized != null
	&& type2Parameterized != null) {
	// type1 and type2 are parameterized types with the same base type;
	// compare their arguments
	JClassType[] args1 = type1Parameterized.getTypeArgs();
	JClassType[] args2 = type2Parameterized.getTypeArgs();
	boolean allMatch = true;
	for (int i = 0; i < args1.length; i++) {
	if (!typesMatch(args1[i], args2[i], constraints)) {
	allMatch = false;
	}
	}

	if (allMatch) {
	return true;
	}
	} else {
	// The types have different base types, so just compare the base types
	// for overlap.
	if (baseTypesOverlap(baseType1, baseType2)) {
	return true;
	}
	}
	}

	return false;
	}

	/**
	* The same as {@link #typesMatch(JClassType, JClassType, Map)}, but
	* additionally support primitive types as well as class types.
	*/
	boolean typesMatch(JType type1, JType type2,
	Map<JTypeParameter, JClassType> constraints) {
	if (type1 == type2) {
	// This covers the case where both are primitives
	return true;
	}

	JClassType type1Class = type1.isClassOrInterface();
	JClassType type2Class = type2.isClassOrInterface();
	if (type1Class != null && type2Class != null
	&& typesMatch(type1Class, type2Class, constraints)) {
	return true;
	}

	return false;
	}

	/**
	* Replace all wildcards in <code>type</code> with a fresh type variable.
	* For each type variable created, add an entry in <code>constraints</code>
	* mapping the type variable to its upper bound.
	*/
	private JClassType replaceWildcardsWithFreshTypeVariables(JClassType type,
	final Map<JTypeParameter, JClassType> constraints) {

	JModTypeVisitor replacer = new JModTypeVisitor() {
	@Override
	public void endVisit(JWildcardType wildcardType) {
	JTypeParameter newParam = new JTypeParameter("TP$"
	+ freshTypeVariableCounter++, -1);
	newParam.setBounds(makeArray(typeOracle.getJavaLangObject()));
	constraints.put(newParam, wildcardType.getUpperBound());
	replacement = newParam;
	}
	};

	return replacer.transform(type);
	}

	/**
	* Substitute all occurrences in <code>type</code> of type parameters in
	* <code>constraints</code> for a wildcard bounded by the parameter's entry
	* in <code>constraints</code>. If the argument is <code>null</code>,
	* return <code>null</code>.
	*/
	private JClassType substitute(JClassType type,
	final Map<JTypeParameter, JClassType> constraints) {
	JModTypeVisitor substituter = new JModTypeVisitor() {
	@Override
	public void endVisit(JTypeParameter param) {
	JClassType constr = constraints.get(param);
	if (constr != null) {
	replacement = constr;
	}
	}
	};
	return substituter.transform(type);
	}
	}