Skip to content

Commit c635614

Browse files
gselzergselzer
committed
Improve IterableTypeExtractor
Allow the IterableTypeExtractor to determine the greatest common supertype of all of the elements in the Iterable. This required adding a 'greatest common supertype resolver' in Types.
1 parent 16653e7 commit c635614

3 files changed

Lines changed: 355 additions & 4 deletions

File tree

‎src/main/java/org/scijava/ops/types/IterableTypeExtractor.java‎

Lines changed: 15 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -30,11 +30,14 @@
3030
package org.scijava.ops.types;
3131

3232
import java.lang.reflect.Type;
33+
import java.util.ArrayList;
3334
import java.util.Iterator;
35+
import java.util.List;
3436

3537
import org.scijava.Priority;
3638
import org.scijava.plugin.Parameter;
3739
import org.scijava.plugin.Plugin;
40+
import org.scijava.util.Types;
3841

3942
/**
4043
* {@link TypeExtractor} plugin which operates on {@link Iterable} objects.
@@ -54,15 +57,23 @@ public class IterableTypeExtractor implements TypeExtractor<Iterable<?>> {
5457

5558
@Override
5659
public Type reify(final Iterable<?> o, final int n) {
57-
if (n != 0) throw new IndexOutOfBoundsException();
60+
if (n != 0)
61+
throw new IndexOutOfBoundsException();
5862

5963
final Iterator<?> iterator = o.iterator();
60-
if (!iterator.hasNext()) return null;
64+
if (!iterator.hasNext())
65+
return null;
6166

6267
// Obtain the element type using the TypeService.
63-
final Object element = iterator.next();
64-
return typeService.reify(element);
68+
int typesToCheck = 100;
69+
//can we make this more efficient?
70+
List<Type> typeList = new ArrayList<>();
71+
for (int i = 0; i < typesToCheck; i++) {
72+
if(!iterator.hasNext()) break;
73+
typeList.add(typeService.reify(iterator.next()));
74+
}
6575

76+
return Types.greatestCommonSuperType(typeList.toArray(new Type[] {}), true);
6677
// TODO: Avoid infinite recursion when the list references itself.
6778
}
6879

‎src/main/java/org/scijava/util/Types.java‎

Lines changed: 163 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -63,10 +63,12 @@
6363
import java.util.HashMap;
6464
import java.util.HashSet;
6565
import java.util.LinkedHashSet;
66+
import java.util.LinkedList;
6667
import java.util.List;
6768
import java.util.Map;
6869
import java.util.Objects;
6970
import java.util.Optional;
71+
import java.util.Queue;
7072
import java.util.Set;
7173
import java.util.stream.IntStream;
7274

@@ -741,6 +743,167 @@ public static Type param(final Type type, final Class<?> c, final int no) {
741743
c.getTypeParameters()[no]);
742744
}
743745

746+
/**
747+
* Determines the greatest common supertype of all types in the input array
748+
*
749+
* @param types
750+
* The array of subtypes, for which the supertype is found.
751+
* @param wildcardSingleIface
752+
* The default behavior, when the method finds multiple suitable
753+
* interfaces, is to create a wildcard with all suitable interfaces
754+
* as upper bounds. If this {@code boolean} is set to true, a
755+
* wildcard will also be created if only one suitable interface is
756+
* found. If false, the return will be the interface itself (i.e. not
757+
* a wildcard).
758+
* @return a {@link Type} that is a supertype of all {@link Type}s in the types array.
759+
*/
760+
public static Type greatestCommonSuperType(final Type[] types, final boolean wildcardSingleIface) {
761+
762+
if (types.length == 0)
763+
return null;
764+
// make sure that all types are supported
765+
// TODO: are there any other types that aren't fully supported?
766+
for (Type t : types) {
767+
if (t instanceof TypeVariable<?>)
768+
throw new UnsupportedOperationException("Unsupported type: " + t);
769+
}
770+
771+
// We can effectively find the greatest common super type by assuming that
772+
// either:
773+
// 1) superType extends a superclass of all types in types (this check is
774+
// symmetric)
775+
// 2) superType implements an interface implemented by all types in typws (this
776+
// check is symmetric)
777+
778+
Type superType = types[0];
779+
780+
// 1)
781+
// prefer any non-Object superClass over implemented interfaces.
782+
while (Types.raw(superType) != Object.class) {
783+
// check assignability of superclass with type params
784+
Type pType = Types.getExactSuperType(types[0], Types.raw(superType));
785+
if (Types.isAssignable(types, pType) == -1)
786+
return superType;
787+
788+
// if we have a parameterizedtype whose rawtype is assignable to all of types,
789+
// we just have to resolve each of pType's type variables.
790+
if (pType instanceof ParameterizedType && //
791+
Types.isAssignable(types, Types.raw(superType)) == -1) {
792+
ParameterizedType[] castedTypes = new ParameterizedType[types.length];
793+
castedTypes[0] = (ParameterizedType) pType;
794+
// generate parameterizedTypes of each type in types w.r.t. supertype
795+
for (int i = 1; i < castedTypes.length; i++) {
796+
Type t = Types.getExactSuperType(types[i], Types.raw(superType));
797+
if (!(t instanceof ParameterizedType))
798+
continue;
799+
castedTypes[i] = (ParameterizedType) t;
800+
}
801+
// resolve each of the i type variables of superType using
802+
// greatestCommonSupertype
803+
Type[] resolvedTypeArgs = new Type[castedTypes[0].getActualTypeArguments().length];
804+
for (int i = 0; i < resolvedTypeArgs.length; i++) {
805+
Type[] typeVarsI = new Type[types.length];
806+
for (int j = 0; j < typeVarsI.length; j++) {
807+
typeVarsI[j] = castedTypes[j].getActualTypeArguments()[i];
808+
}
809+
resolvedTypeArgs[i] = wildcard(new Type[] { greatestCommonSuperType(typeVarsI, true) },
810+
new Type[] {});
811+
}
812+
813+
// return supertype parameterized with the resolved type args
814+
return Types.parameterize(Types.raw(superType), resolvedTypeArgs);
815+
}
816+
if (Types.raw(superType).isInterface())
817+
break;
818+
superType = Types.getExactSuperType(superType, Types.raw(superType).getSuperclass());
819+
}
820+
821+
// 2)
822+
List<Type> sharedInterfaces = new ArrayList<>();
823+
Queue<Type> superInterfaces = new LinkedList<>();
824+
if (Types.raw(types[0]).isInterface())
825+
superInterfaces.add(types[0]);
826+
else
827+
for (Type superT1 : Types.raw(types[0]).getGenericInterfaces())
828+
superInterfaces.add(superT1);
829+
while (superInterfaces.size() > 0) {
830+
Type type = superInterfaces.remove();
831+
Type pType = Types.getExactSuperType(types[0], Types.raw(type));
832+
if (Types.isAssignable(types, pType) == -1) {
833+
sharedInterfaces.add(pType);
834+
continue;
835+
}
836+
// if we have a parameterizedtype whose rawtype is assignable to all of types,
837+
// we just have to resolve each of pType's type variables.
838+
if (pType instanceof ParameterizedType && //
839+
Types.isAssignable(types, Types.raw(pType)) == -1) {
840+
ParameterizedType[] castedTypes = new ParameterizedType[types.length];
841+
castedTypes[0] = (ParameterizedType) pType;
842+
// generate parameterizedTypes of each type in types w.r.t. supertype
843+
for (int i = 1; i < castedTypes.length; i++) {
844+
Type t = Types.getExactSuperType(types[i], Types.raw(pType));
845+
if (!(t instanceof ParameterizedType))
846+
continue;
847+
castedTypes[i] = (ParameterizedType) t;
848+
}
849+
// resolve each of the i type variables of pType using greatestCommonSupertype
850+
Type[] resolvedTypeArgs = new Type[castedTypes[0].getActualTypeArguments().length];
851+
for (int i = 0; i < resolvedTypeArgs.length; i++) {
852+
Type[] typeVarsI = new Type[types.length];
853+
for (int j = 0; j < typeVarsI.length; j++) {
854+
typeVarsI[j] = castedTypes[j].getActualTypeArguments()[i];
855+
}
856+
// If each of these types implements some recursive interface, e.g. Comparable,
857+
// the best we can do is return an unbounded wildcard.
858+
if (Arrays.equals(types, typeVarsI))
859+
resolvedTypeArgs[i] = wildcard();
860+
else
861+
resolvedTypeArgs[i] = greatestCommonSuperType(typeVarsI, true);
862+
}
863+
864+
// return supertype parameterized with the resolved type args
865+
return Types.parameterize(Types.raw(pType), resolvedTypeArgs);
866+
}
867+
868+
// if this interface is not a supertype of all of types, maybe one of its
869+
// inherited interfaces is. N.B. we don't want to keep searching through the
870+
// interface hierarchy, however, if we have have found a type that satisfies all
871+
// of types. Thus we stop adding to the list if we have found at least one
872+
// satisfying interface. Do note, however, that this does not prevent multiple
873+
// satisfying interfaces at the same depth from being found.
874+
if (sharedInterfaces.size() == 0)
875+
for (Type superT1 : Types.raw(type).getGenericInterfaces())
876+
superInterfaces.add(superT1);
877+
}
878+
if (sharedInterfaces.size() == 1 && !wildcardSingleIface) {
879+
return sharedInterfaces.get(0);
880+
} else if (sharedInterfaces.size() > 0) {
881+
return wildcard(sharedInterfaces.toArray(new Type[] {}), new Type[] {});
882+
}
883+
return Object.class;
884+
}
885+
886+
/**
887+
* Discerns whether it would be legal to assign a group of references of types
888+
* {@code source} to a reference of type {@code target}.
889+
*
890+
* @param source
891+
* The types from which assignment is desired.
892+
* @param target
893+
* The type to which assignment is desired.
894+
* @return the index of the first type not assignable to {@code target}. If all
895+
* types are assignable, returns {@code -1}
896+
* @throws NullPointerException
897+
* if {@code target} is null.
898+
* @see Class#isAssignableFrom(Class)
899+
*/
900+
private static int isAssignable(final Type[] sources, final Type target) {
901+
for(int i = 0; i < sources.length; i++) {
902+
if(!Types.isAssignable(sources[i], target)) return i;
903+
}
904+
return -1;
905+
}
906+
744907
/**
745908
* Discerns whether it would be legal to assign a reference of type
746909
* {@code source} to a reference of type {@code target}.

0 commit comments

Comments
 (0)