聊一聊 – 泛型检索实现

前语

Java 编译器在编译泛型代码时，会将一切泛型类型参数替换为它们的限定类型或 Object 类型，而且刺进必要的类型转换，这被称为泛型擦除（Generic Type Erasure）。可是，假如咱们期望在编译时拿到泛型类型，就需求借助一些特殊的技术。

举个比如哈，一种常见的技术是运用 Annotation Processing Tool（APT），在编译期间生成代码。咱们能够编写一个承继自泛型类或完成泛型接口的包装类，然后运用 APT 在编译期间对这个包装类进行解析，然后获取泛型类型所对应的数据类型。

那么咱们需求如何完成获取泛型类型所对应的数据类型的逻辑呢？我查找了 Google 和 Stack Overflow，可是没有找到基于 Java 的通用泛型检索算法完成。因而，我将在本文中介绍一种自己完成的泛型检索算法，以供咱们参考和选择。

完成原理

泛型类

在进入泛型检索算法的原理之前，咱们需求先了解 Java 中泛型类承继的形式，以及明确咱们所需求完成的泛型检索的效果。

public class SuperGenericClass<T,F>{
    ...
}
​
​
public class CurrentClass extends SuperGenericClass<String,Double>{
   ...
}

在上述代码中，CurrentClass 是一个普通类，它承继自 SuperGenericClass 泛型类。因为父类 SuperGenericClass 运用了两个泛型类型 T 和 F，而在 CurrentClass 中指定了这两个泛型类型，分别为 String 和 Double。因而，咱们能够经过检索 CurrentClass 的承继完成联系，来获取泛型类型所对应的数据类型。具体来说，咱们能够得到以下成果：

• T 对应 String
• F 对应 Double

这样，咱们就能够在编译期间拿到泛型类型所对应的数据类型，以便进行相关操作。

在 Java 中，类的确只能单承继，可是接口能够多承继。因而，咱们能够将类和接口的承继联系都看做一个有向图，其中类是一个有向链，而接口能够有多个父接口，因而是一个有向无环图（DAG）。节点代表一个类或接口，边表明类或接口之间的承继联系。节点上承载一个加载了泛型类型的数组，用于存储泛型类型信息。

因而，咱们能够把问题转化为从一个节点开端，顺次沿着边向上遍历直到抵达根节点为止。在遍历进程中，咱们不断将当时节点上的泛型类型数组中的类型信息传递到上一个节点，直至抵达根节点，完成泛型类型检索的进程。

图A

在上图的首尾节点中，再刺进一个节点，并在这个节点中也完成了一个泛型类型指定数据类型的进程，那么关于泛型类型的检索是否仍是相同的呢？

图B

依据上图所示，转化进程仍是相差无几。那么咱们就加一点难度，在中心这个节点中，再加入一个泛型类型，而且改变泛型次序，如下图所示：

图C

依据图B和图C，读者可能现已注意到，在图B中，F 在 Node 的 Generic 数组中的索引方位为 0。而在图C中，F 在Node 的 Generic 数组中的索引方位为 1。这引出了第二个问题：在传递泛型类型的进程中，需求指定泛型类型在数组中的索引方位，而且在承继联系中过滤掉其他泛型类型。因而，更新后的结构如下所示：

查找泛型的伪代码如下：

public GenericInfo[] findByClass(Node targetClass) {
  // 核实操作
   ...
​
  // 递归，从尾节点开端往头节点记载
  GenericInfo[] parentGenericInfo = next.findByClass(targetClass);
    // 抵达尾节点后，将尾节点的方针装备泛型结构数据回来给上一个节点，然后开端递归填充泛型数据。
  if(parentGenericInfo == null){
    return targetClass.getTargetGeneric();
   }
​
  // 将需求检索的方针节点中的泛型，与当时节点的泛型完成相关。
  for (GenericInfo info : parentGenericInfo) {
    // 若当时泛型类型已相关数据类型，则记载数据类型。
    if(info.isDataType()){
      recordGeneric(info);
      continue;
     }
   
    // 不然
      // 1. 记载泛型与泛型的对照联系，如图中Node节点，两个F的坐标和值的映射
      // 2. 记载泛型和数据类型的对照联系，如图中Node节点，T对应了String类型
    // 得到泛型在下一节点绑定的方位
    int position = info.getPosition();
    // 在当时类的泛型信息
    GenericTypeEnum typeEnum = findTypeByPosition(position);
    // 当时类中界说的泛型方位
    int currentPosition = findCurrentPositionByPosition(position);
    // 记载这个方位上所绑定的泛型和方位信息，到record数组中
    recordGenericTypeAndPosition(typeEnum,currentPosition);
   }
​
  // 将记载泛型联系的数组回来到上一个节点
  return record;
}

泛型接口

有了上述泛型类的查询逻辑做铺垫，咱们再来看看泛型接口是如何去查找的？

在 Java 中，一个接口能够承继自另一个或多个接口，所以无法运用链表来展现泛型检索，需求运用树来进行检索。中心逻辑与泛型类相似，首要找到方针泛型接口节点作为回溯起点，然后顺次将泛型信息记载回来到根节点。

第一步，先查找到根节点的一切子节点上，核实是否是方针节点，或许记载了方针节点的上级节点。如下图所示：

咱们发现，并没有查到方针节点，而且当时也并不知晓 Node2 这个节点下存在咱们的方针节点。因而，咱们需求再往下进行检索。那么咱们以那个节点优先，往下检索呢？这儿我才用的是优先完成 泛型类的检索逻辑 ，从类的承继这条链表上进行优先检索，所以我把这界说为 大局深搜。

第二步，咱们来到了 Node2 这个节点，核实这个节点的一切子节点，咱们发现仍是没有找到，同理再次查找 Node4 这个节点。

第三步，咱们来到 Node4 这个节点，核实这个节点的一切子节点，发现节点 Node10 就是咱们的方针节点。

第四步，以 Node10 这个节点开端，开端回溯记载节点信息，这又和泛型类的检索逻辑一致。

第五步，假如咱们的方针节点不是在 Node10 ，而是在 Node9 ，那么咱们在查找完Node5后，仍旧没有找到方针节点，咱们就需求在回溯的进程中，核实接口的承继联系。

第六步，顺次从 Node5 回到 Node4 ，发现Node10，并没有承继其他接口，所以在回到 Node2，Node2仍旧没有完成其他接口，于是回到RootNode，RootNode中 顺次查找 Node1和 Node3的子节点信息。于是咱们在Node3 下找到了Node9，因而重新开端从 Node9 -> Node3 -> RootNode 履行泛型回溯逻辑。

优化算法

在上述检索进程中，最坏的状况下，咱们需求把一切的节点都查找一遍，所以时刻复杂度为O(n)，而且每次检索都是O(n)，这个功率显着是能够进一步优化的。我的思路是，用空间换时刻，将已查找过的节点名字为键（在类或接口上，就是它的全类名），以泛型记载信息为值，记载缓存。

当下次再次检索到同一个节点时，这个节点存在泛型信息，则直接运用，不许检索其子节点。若这个节点不存在节点信息，则直接过滤。然后平均复杂度就能够降到 O(1) 。

编译时泛型检索

现在咱们回到编译时，经过中心逻辑来完成下泛型检索。这儿我以泛型类为例，泛型接口咱们能够来看源码。

第一步：核实当时类是否被检索过，优化功率。

// 当时类的全类名
String qualifiedName = element.getQualifiedName().toString();
​
// 核实当时类是否履行过检索
Map<String, RetrievalClassModel> retrievalMap = retrieval.retrievalClassMap();
// 当时的检索记载
RetrievalClassModel currentModel = retrievalMap.get(qualifiedName);
if (currentModel != null && currentModel.isCompeted()) {
  return currentModel;
}

第二步：核实当时是类，而且父类存在，以保证功用查找方向没有错（当时是「泛型类」检索类）。

// 当时类必需是类，而且父类必需存在，最终要承继方针类
if (isInterfaceOrNotHasParentClass(element)) {
  return null;
}

第三步：检索而且记载当时类信息

• 加载父类检索信息，存在则直接相关到当时类上，无需再度向上检索，不存在持续履行检索。

• 核实是否是方针类，是则与当时类相关，不然持续检索。
• 核实是否在排除包中，是则阐明查找不到，回来null，不然持续检索。
• 回到第一步，检索父类信息

/**
 * 检索得到当时类的泛型存储信息，需求得到当时类的泛型存储信息：
 * 1.父类必定是 TypeElement 类型元素。
 * 2.核实父类是否已加载泛型存储数据，有则依据是否泛型填充完好，做相关行为，
 * 若填充完好，则浅拷贝，共用同一个存储方针。
 * 若不完好，则深拷贝，避免更改时影响父类的存储元素。
 * 3.核实是否是方针节点类，是则遍历相关泛型信息。
 * 4.核实父类是否是在过滤包中，是则回来null，无需再次查找。
 * 5.父类信息检索不到，则向祖父类检索 回到 searchClassGenerics()方法
 * 6.从父类得到数据后，将泛型数据相关「同类-层级相关」+「承继类-坐标相关」。
 *
 * @param element 当时类的元素
 * @param types  类型工具
 * @return RetrievalClassModel 检索泛型数据信息
 */
private RetrievalClassModel retrievalCurrentClass(TypeElement element, Types types) {
  TypeMirror superTypeMirror = element.getSuperclass();
  if (superTypeMirror == null) {
    return null;
   }
​
  Element superElement = types.asElement(superTypeMirror);
  if (!(superElement instanceof TypeElement)) {
    return null;
   }
​
  // 获取父类信息
  Map<String, RetrievalClassModel> classMap = retrieval.retrievalClassMap();
  TypeElement superTypeElement = (TypeElement) superElement;
  // 父类RetrievalClassModel
  String superclassName = superTypeElement.getQualifiedName().toString();
  RetrievalClassModel superRetrievalModel = classMap.get(superclassName);
  // 当时类的RetrievalClassModel
  String qualifiedName = element.getQualifiedName().toString();
  RetrievalClassModel currentModel = classMap.get(qualifiedName);
​
  // 先核实一步，若存在，可削减后续方针节点和过滤节点的盘点耗时
  RetrievalClassModel checkLoaded = GenericsRecordUtils.checkLoaded(superRetrievalModel, currentModel, element, retrieval);
  if (checkLoaded != null && checkLoaded.isCompeted()) {
    return checkLoaded;
   }
​
  // 方针节点
  String targetClassName = retrieval.canonicalName();
  if (Objects.equals(superclassName, targetClassName)) {
    // 方针节点
    RetrievalClassModel nodeClass = GenericsRecordUtils.traverseTargetGenerics(superTypeMirror, qualifiedName, retrieval);
    if (nodeClass == null) {
      return null;
     }
    GenericsRecordUtils.appendBindPosition(nodeClass, element.getTypeParameters());
    return nodeClass;
   }
​
​
  // 根节点/需求过滤的节点
  Set<String> filterablePackages = retrieval.filterablePackages();
  for (String filterablePackage : filterablePackages) {
    if (superclassName.startsWith(filterablePackage)) {
      return null;
     }
   }
​
  // 得到父类检索信息
  RetrievalClassModel superClassModel = searchGenerics(superTypeElement, types);
  if (superClassModel == null) {
    return null;
   }
​
  // 将泛型数据相关「同类-层级相关」+「承继类-坐标相关」
  return GenericsRecordUtils.traverseNodeAndBindPosition(superTypeMirror, currentModel, superClassModel, element, retrieval);
}

第四步，相关行为，分为「同类-层级相关」和「承继类-坐标相关」。

• 在 ParentClass 类中的 形式类 TargetClass<K,String> 和 实践类 TargetClass<T,K> 进行泛型相关。

  • 状况一：将泛型类型和泛型类型相关，TargetClass<K,String>中的K 和 TargetClass<T,K> 的T相关。
  • 状况二：将数据类型 String 与 K 绑定。
  • 由此，在 ParentClass 实践相关的 TargetClass 泛型为 T 和 K=String

• 承继类-坐标相关:

  • 同样在 ParentClass 类中，ParentClass<K,Model> 和 TargetClass<K,String> 要进行方位上的相关。
  • 由「泛型相关」可知 TargetClass<K,String> 中的K，实践上是「方针类」中的T，
  • 所以对等，要将 ParentClass中的K 等效为T，然后记载格式而且向子类传递。

/**
 * 「同类-层级相关」+「承继类-坐标相关」
 *
 * @param superTypeMirror 父类类型
 * @param currentModel   当时类的泛型数据存储
 * @param superClassModel 父类的泛型数据存储
 * @param element     当时类的类型元素
 * @return 父类检索信息绑定到当时类
 */
public static RetrievalClassModel traverseNodeAndBindPosition(TypeMirror superTypeMirror,
                               RetrievalClassModel currentModel,
                               RetrievalClassModel superClassModel,
                               TypeElement element,
                               IRetrieval retrieval) {
​
  // 采用深拷贝
  IGenericsRecord record = cloneBySuperRecord(retrieval,
      superClassModel.getRecord());
  currentModel.bindGenericsRecord(record);
​
  traverseNodeGenerics(superTypeMirror, currentModel, superClassModel);
  appendBindPosition(currentModel, element.getTypeParameters());
  return currentModel;
}
​
/**
 * 遍历方针泛型集合
 * 将当时制定的实体类型 填充到
 * 方针类的泛型上
 * 流程
 * 1. 获取当时类的父类形式泛型
 * 2. 获取实在父类的泛型类型
 * 3. 匹配形式泛型kind == TypeKind.DECLARED，代表能够填充
 * 4. 不匹配的记载到对照表中
 */
public static RetrievalClassModel traverseTargetGenerics(TypeMirror superTypeMirror,
                             String currentQualifiedName,
                             IRetrieval retrieval) {
  if (!(superTypeMirror instanceof DeclaredType)) {
    return null;
   }
​
  DeclaredType declaredType = (DeclaredType) superTypeMirror;
​
  TypeElement superElement = (TypeElement) declaredType.asElement();
  List<? extends TypeParameterElement> superParameters = superElement.getTypeParameters();
  List<? extends TypeMirror> typeArguments = declaredType.getTypeArguments();
  // 未设置泛型，或设置的泛型个数不一致
  if (typeArguments.isEmpty() || superParameters.size() != typeArguments.size()) {
    return null;
   }
​
  // 「同类-层级相关」
  Map<String, RetrievalClassModel> classMap = retrieval == null ? new HashMap<>() : retrieval.retrievalClassMap();
  RetrievalClassModel classModel = classMap.get(currentQualifiedName);
  for (int index = 0; index < superParameters.size(); index++) {
    TypeParameterElement element = superParameters.get(index);
    String typeName = element.asType().toString();
​
    TypeMirror mirror = typeArguments.get(index);
    if (mirror.getKind() == TypeKind.DECLARED) {
      classModel.addTargetGenericsRecord(typeName, mirror);
     } else {
      classModel.recordType(mirror.toString(), RetrievalClassModel.PREFIX + typeName);
     }
   }
  return classModel;
}
​
/**
 * 追加绑定泛型类型的方位，「承继类-坐标相关」
 * AClass<T> extends BClass<T>{
 * <p>
 * }
 * 绑定T的方位为0
 *
 * @param nodeClass     节点Class信息
 * @param currentParameters 当时类的泛型参数 AClass<T> 中的T
 */
public static void appendBindPosition(RetrievalClassModel nodeClass, List<? extends TypeParameterElement> currentParameters) {
  int index = 0;
  for (TypeParameterElement parameter : currentParameters) {
    nodeClass.bindPosition(parameter.asType().toString(), index);
    index++;
   }
}

完好代码：github.com/Sheedon/Com…

结束语

在实践开发中，需求进行泛型检索的状况比较少，但当咱们在构思一种解决方案而且没有供给API供咱们运用时，将结构简化为数据结构和根底算法是一个解决问题的有效方法。本文旨在向读者介绍如何经过将复杂结构转化为数据结构和根底算法来解决问题，并经过泛型检索的比如进行阐明。当然，这只是为各位供给了一个思路，假如读者有更好的解决方案，也欢迎分享给咱们。