《leetcode-runner》【图解】【源码】如何手搓一个debug调试器——表达式计算
前文：
《leetcode-runner》如何手搓一个debug调试器——引言
《leetcode-runner》如何手搓一个debug调试器——架构
《leetcode-runner》如何手搓一个debug调试器——指令系统
《leetcode-runner》【图解】如何手搓一个debug调试器——调试程序【JDI开发】【万字详解】
文章目录
仓库地址：leetcode-runner
本文主要聚焦于如何编表达式计算功能
1. 什么是表达式计算
我们直接通过案例说明
画红框对应的功能逻辑就是表达式计算功能
在leetcode-runner项目中，也支持相关的计算逻辑
2. 解决思路
2.1 变量转换为常量
我们先看最简单的表达式——1 + 2
这好解决，直接将表达式输入给计算引擎，将引擎返回结果
在Java中，Jexl就是个不错的计算引擎，他还支持字符串的计算
比如 “123” + 4，计算返回"1234"
在leetcode-runner中，封装如下计算引擎，进行辅助计算
现在，我们上点难度
a + 2
这时候，有的同学要问了，尼玛，这个a是什么东西
a就是被debug代码中存在的变量捏
这时，我们初见麻烦的地方
用户输入的表达式不一定是纯粹的常量表达式，也有可能含有变量
因此，在计算表达式的时候，需要识别变量，同时将他更换为常量
比如代码中定义 int a = 10;
在计算 a + 2时，我们就需要将变量a处理成常量，得到10 + 2的表达式，在将其输入给计算引擎，进行计算
也就是说，对于表达式计算逻辑，我们需要识别所有变量，并将其处理为常量，然后将只含有常量的表达式输入计算引擎，执行计算逻辑
对于简单的变量取值，并不会有太大难度，但不同类型的变量，在JDI中获取他们实际的值是一件相当复杂且麻烦的事，下一节将会说明识别的难点
2.2 变量识别的难点
- 如何获取变量的Value
- 获取Value后，不同类型有着不同的处理逻辑
2.2.1 如何获取变量a的值
对于变量a，想要获取他的值相对简单，笔者将给出leetcode-runner简化后的代码
// 从Context中获取ThreadReference
var thread = context.getThread();
// 获取栈帧
StackFrame stack = thread.frame(0);
// 获取可见变量的引用
List<LocalVariable> localVariables = frame.visibleVariables();
// 获取局部变量的值
Map<LocalVariable, Value> values = frame.getValues(localVariables);
如果对Context不了解的读者，可以参考前一篇介绍JDI的文章《leetcode-runner》【图解】如何手搓一个debug调试器——调试程序【JDI开发】【万字详解】
当获取values后，只要通过变脸所有数据，判断是否存在一个名叫a的变量，即可获取a的值
但需要注意的是，JDI中所有数据都是封装为Value
因此我们还需要对他进一步处理
// 因为a是int类型, 所以他的Value是PrimitiveValue
Value a = ...
PrimitiveValue pv = (PrimitiveValue) a;
// 强转为IntegerValue
IntegerValue intValue = (IntegerValue) pv;
int intA = intValue.value();
tip: IntergerValue是int类型的镜像，不是Integer类型的镜像。Integer的镜像是ObjectReference！
嘿嘿，麻烦吧，巨tm麻烦，这还是我提前知道a是int类型。如果我不知道a是啥类型，只能枚举所有类型，逐层判断
基本类型处理起来就已经这么操蛋，再来个对象类型就更头疼了。对象越复杂，处理越麻烦…
因此，在leetcode-runner中，单独封装了一个类，专门负责处理Value，可以从Value中获取真正的数据，并以String的形式返回
这个类就是JavaValueInspector，该类为了简化分析逻辑，采用不少的递归算法，并对一些特殊数据结构做出特殊处理，以此返回更让人容易识别的数据。比如链表，二叉树等等，这些数据结构都会以可视化的方式返回，并不是如实反应他的实际数据
JavaValueInspector逻辑比较复杂，笔者就不做过多的解释，感兴趣的读者可以clone我的项目，或者直接查看下方源码。JavaValueInspector的入口方法是inspectValue(Value value)，看源码去吧，桀桀
package com.xhf.leetcode.plugin.debug.execute.java.p;
import com.sun.jdi.*;
import com.xhf.leetcode.plugin.debug.analysis.converter.convert.TreeNode;
import com.xhf.leetcode.plugin.utils.MapUtils;
import java.util.*;
import java.util.stream.Collectors;
/**
* 强转value, 并给出value的实际内容, md, 真恶心啊我靠
* 底层这些破玩意儿真是一点办法没有, 全得写死, 而且为了简化代码,
* 使用了不少递归处理, 最怕递归太深了, 出现StackOverflow, 爆栈什么的, 那种事情不要啊~
*/
public class JavaValueInspector {
// 单例
private static final JavaValueInspector INSTANCE = new JavaValueInspector();
private JavaValueInspector() {
}
public static JavaValueInspector getInstance() {
return INSTANCE;
}
public String inspectValue(Value value) {
return inspectValue(value, 0);
}
private String inspectValue(Value value, int depth) {
if (value == null) {
return null;
}
// 处理基本类型
if (value instanceof PrimitiveValue) {
return handlePrimitiveValue((PrimitiveValue) value);
}
// 处理引用类型
else if (value instanceof ObjectReference) {
return handleObjectReference((ObjectReference) value, depth);
}
// 其他未知类型
else {
return null;
}
}
private String handlePrimitiveValue(PrimitiveValue value) {
String res;
if (value instanceof BooleanValue) {
res = String.valueOf(((BooleanValue) value).value());
} else if (value instanceof ByteValue) {
res = String.valueOf(((ByteValue) value).value());
} else if (value instanceof CharValue) {
res = "\"" + ((CharValue) value).value() + "\"";
} else if (value instanceof DoubleValue) {
res = String.valueOf(((DoubleValue) value).value());
} else if (value instanceof FloatValue) {
res = String.valueOf(((FloatValue) value).value());
} else if (value instanceof IntegerValue) {
res = String.valueOf(((IntegerValue) value).value());
} else if (value instanceof LongValue) {
res = String.valueOf(((LongValue) value).value());
} else if (value instanceof ShortValue) {
res = String.valueOf(((ShortValue) value).value());
} else {
res = null;
}
return res;
}
private String handleObjectReference(ObjectReference objRef, int depth) {
String res;
if (objRef instanceof StringReference) {
res = "\"" + ((StringReference) objRef).value() + "\"";
} else if (objRef instanceof ArrayReference) {
if (((ArrayReference) objRef).length() == 0) {
return "[]";
}
Value value = ((ArrayReference) objRef).getValue(0);
if (value instanceof StringReference) {
res = "[" + ((ArrayReference) objRef).getValues().stream().map(String::valueOf).collect(Collectors.joining(", ")) + "]";
} else if (value instanceof PrimitiveValue) {
res = "[" + ((ArrayReference) objRef).getValues().stream().map(e -> handlePrimitiveValue((PrimitiveValue) e)).collect(Collectors.joining(", ")) + "]";
} else if (isWrapperType(value)) {
res = "[" + ((ArrayReference) objRef).getValues().stream().map(e -> handleWrapper((ObjectReference) e)).collect(Collectors.joining(", ")) + "]";
} else {
res = "[" + ((ArrayReference) objRef).getValues().stream().map(e -> handleObjectReference((ObjectReference) e, depth + 1)).collect(Collectors.joining(", ")) + "]";
}
} else if (objRef instanceof ThreadReference) {
res = ((ThreadReference) objRef).name();
} else if (objRef instanceof ClassObjectReference) {
res = String.valueOf(((ClassObjectReference) objRef).reflectedType());
} else if (objRef instanceof ClassLoaderReference) {
res = "ClassLoader...";
} else if (isWrapperType(objRef)) {
res = handleWrapper(objRef);
} else if (isArrayList(objRef)) {
res = handleArrayList(objRef, depth);
} else if (isArraysArrayList(objRef)) {
res = handleArraysArrayList(objRef, depth);
} else if (isLinkedList(objRef)) {
res = handleLinkedList(objRef, depth);
} else if (isSingletonList(objRef)) {
res = handleSingletonList(objRef, depth);
} else if (isArrayDeque(objRef)) {
res = handleArrayDeque(objRef, depth);
} else if (objRef instanceof ThreadGroupReference) {
res = "objRef 是 ThreadGroupReference, 不支持处理!";
} else if (isTreeNode(objRef)) {
res = handleTreeNode(objRef, depth);
} else if (isListNode(objRef)) {
res = handleListNode(objRef, depth);
} else if (isPriorityQueue(objRef)) {
res = handlePriorityQueue(objRef, depth);
} else {
res = handleComplexObject(objRef, depth);
}
return res;
}
private String handlePriorityQueue(ObjectReference objRef, int depth) {
if (objRef == null) {
return "null";
}
ReferenceType referenceType = objRef.referenceType();
Value value = objRef.getValue(referenceType.fieldByName("queue"));
if (value == null) {
return null;
}
return this.inspectValue(value, depth);
}
private boolean isPriorityQueue(ObjectReference objRef) {
if (objRef == null) {
return false;
}
return objRef.type().name().equals("java.util.PriorityQueue");
}
private String handleListNode(ObjectReference objRef, int depth) {
if (! isMyListNode(objRef)) {
return handleComplexObject(objRef, depth);
}
ReferenceType referenceType = objRef.referenceType();
Value val = objRef.getValue(referenceType.fieldByName("val"));
Value next = objRef.getValue(referenceType.fieldByName("next"));
StringBuilder sb = new StringBuilder("[");
while (next != null) {
val = objRef.getValue(referenceType.fieldByName("val"));
next = objRef.getValue(referenceType.fieldByName("next"));
objRef = (ObjectReference) next;
sb.append(getIntNodeVal(val)).append(",");
}
if (sb.charAt(sb.length() - 1) == ',') {
sb.deleteCharAt(sb.length() - 1);
}
sb.append("]");
return sb.toString();
}
private boolean isListNode(Value value) {
// 判断是否是 java.util.ArrayDeque
return value instanceof ObjectReference && value.type().name().contains("ListNode");
}
/**
* 判断是否是我提供的ListNode
* @param objRef
* @return
*/
private boolean isMyListNode(ObjectReference objRef) {
// 检查并获取变量
ReferenceType referenceType = objRef.referenceType();
Value val = objRef.getValue(referenceType.fieldByName("val"));
Value next = objRef.getValue(referenceType.fieldByName("next"));
if (val == null || next == null) {
return false;
}
if (! (val instanceof IntegerValue) ) {
return false;
}
// 判断类型
return next.type().name().equals(referenceType.name());
}
/**
* 处理复杂对象的打印
* @param objRef
* @param depth
* @return
*/
private String handleComplexObject(ObjectReference objRef, int depth) {
StringBuilder sb = new StringBuilder();
if (objRef == null || objRef.referenceType() == null) {
return "null";
}
List<String> results = new ArrayList<>();
for (Field field : objRef.referenceType().allFields()) {
if (!field.isStatic()) {
Value value = objRef.getValue(field);
// 过滤某些变量
if (isSkipWord(field.name())) {
continue;
}
results.add(field.name() + " : " + this.inspectValue(value, depth + 1)); // 深度+1
}
}
if (!results.isEmpty()) {
sb.append("\n").append(getTabsByDepth(depth)); // 外层缩进
sb.append("{\n");
for (String s : results) {
sb.append(getTabsByDepth(depth + 1)).append(s); // 字段缩进
sb.append("\n");
}
sb.append(getTabsByDepth(depth)).append("}"); // 结束的 右大括号 也要缩进
}else {
sb.append(getTabsByDepth(depth));
sb.append("{}");
}
return sb.toString();
}
private String handleTreeNode(ObjectReference objRef, int depth) {
// 检查是否和我项目提供的TreeNode一致, 否则不进行打印
// if (! isMyTreeNode(objRef)) {
// // 采用默认的复杂对象打印器
// return handleComplexObject(objRef, depth);
// }
// 创建头节点
TreeNode cp = dfs(objRef);
return new TreeNodePrinter(cp).visitAndReturn().toString();
}
/**
* 返回头节点
* @return
*/
private TreeNode dfs(ObjectReference objRef) {
if (objRef == null) {
return null;
}
ReferenceType referenceType = objRef.referenceType();
Value val = objRef.getValue(referenceType.fieldByName("val"));
Value left = objRef.getValue(referenceType.fieldByName("left"));
Value right = objRef.getValue(referenceType.fieldByName("right"));
TreeNode head = new TreeNode(getIntNodeVal(val));
head.left = dfs((ObjectReference) left);
head.right = dfs((ObjectReference) right);
return head;
}
private int getIntNodeVal(Value val) {
return ((IntegerValue)val).intValue();
}
/**
* 判断是否是我提供的TreeNode
*
* @param objRef
* @return
*/
@Deprecated // 因为debug内核采用的是我提供的TreeNode. 所以不用判断
private boolean isMyTreeNode(ObjectReference objRef) {
// 检查并获取变量
ReferenceType referenceType = objRef.referenceType();
Value val = objRef.getValue(referenceType.fieldByName("val"));
Value left = objRef.getValue(referenceType.fieldByName("left"));
Value right = objRef.getValue(referenceType.fieldByName("right"));
if (val == null || left == null || right == null) {
return false;
}
if (! (val instanceof IntegerValue) ) {
return false;
}
// 判断类型
if (!left.type().name().equals(referenceType.name())) {
return false;
}
return right.type().name().equals(referenceType.name());
}
private boolean isTreeNode(Value value) {
// 判断是否是 java.util.ArrayDeque
return value instanceof ObjectReference && value.type().name().contains("TreeNode");
}
// 在打印复杂对象时, 有些字段不需要打印
private final Set<String> skipWords = Set.of("hash", "next", "entrySet", "modCount", "threshold", "loadFactor", "keySet", "values", "comparator", "serialVersionUID", "DEFAULT_INITIAL_CAPACITY");
private boolean isSkipWord(String s) {
return skipWords.contains(s);
}
public String getTabsByDepth(int depth) {
return " ".repeat(Math.max(0, depth));
}
private boolean isArrayDeque(Value value) {
// 判断是否是 java.util.ArrayDeque
return value instanceof ObjectReference && "java.util.ArrayDeque".equals(value.type().name());
}
private String handleArrayDeque(ObjectReference objRef, int depth) {
ReferenceType referenceType = objRef.referenceType();
Value elements = objRef.getValue(referenceType.fieldByName("elements"));
Value head = objRef.getValue(referenceType.fieldByName("head"));
Value tail = objRef.getValue(referenceType.fieldByName("tail"));
if (elements != null && head != null && tail != null) {
StringBuilder sb = new StringBuilder("[");
// 迭代循环
ArrayReference arrayReference = (ArrayReference) elements;
int length = arrayReference.length();
for (int i = ((IntegerValue) head).value(); i != ((IntegerValue) tail).value(); i = (i + 1) % length) {
sb.append(this.inspectValue(arrayReference.getValue(i), depth + 1)).append(",");
}
// 如果最后一个是, 删除
if (sb.charAt(sb.length() - 1) == ',') {
sb.deleteCharAt(sb.length() - 1);
}
return sb.append(']').toString();
}
return null;
}
/**
* 获取 Collections.singletonList 的值
*/
private String handleSingletonList(ObjectReference objRef, int depth) {
Value value = objRef.getValue(objRef.referenceType().fieldByName("element"));
if (value != null) {
return "[" + this.inspectValue(value, depth + 1) + "]";
}
return null;
}
/**
* Collections.singletonList, 就很操蛋
*/
private boolean isSingletonList(Value value) {
return value instanceof ObjectReference && "java.util.Collections$SingletonList".equals(value.type().name());
}
private boolean isLinkedList(Value value) {
return value instanceof ObjectReference && "java.util.LinkedList".equals(value.type().name());
}
private boolean isLinkedListNode(Value value) {
return value instanceof ObjectReference && "java.util.LinkedList$Node".equals(value.type().name());
}
public String handleLinkedList(ObjectReference objRef, int depth) {
Field first = objRef.referenceType().fieldByName("first");
if (first != null) {
Value value = objRef.getValue(first);
StringBuilder sb = new StringBuilder("[");
// 循环迭代
while (isLinkedListNode(value)) {
ObjectReference node = (ObjectReference) value;
// 获取node.item
Field item = node.referenceType().fieldByName("item");
if (item != null) {
Value itemValue = node.getValue(item);
sb.append(inspectValue(itemValue, depth + 1)).append(",");
}
// 获取node.next
Field next = node.referenceType().fieldByName("next");
// 更新node(value)
if (next != null) {
value = node.getValue(next);
}
}
// 如果最后一位是逗号 移除最后一个逗号
if (sb.length() > 0 && sb.charAt(sb.length() - 1) == ',') {
sb.deleteCharAt(sb.length() - 1);
}
return sb.append("]").toString();
}
return "";
}
/**
* 判断是否是Arrays.ArrayList
*/
private boolean isArraysArrayList(Value value) {
return value instanceof ObjectReference && "java.util.Arrays$ArrayList".equals(value.type().name());
}
/**
* 获取Arrays.ArrayList
* @return 以String的形式表示Arrays.ArrayList
*/
private String handleArraysArrayList(ObjectReference objRef, int depth) {
Field a = objRef.referenceType().fieldByName("a");
if (a != null) {
Value value = objRef.getValue(a);
if (value instanceof ArrayReference) {
StringBuilder sb = new StringBuilder("[");
ArrayReference arrayReference = (ArrayReference) value;
for (int i = 0; i < arrayReference.getValues().size(); i++) {
sb.append(this.inspectValue(arrayReference.getValue(i), depth + 1));
if (i != arrayReference.getValues().size() - 1) {
sb.append(", ");
}
}
return sb.append("]").toString();
}
}
return "";
}
/**
* 获取ArrayList
* @return 以String的形式表示ArrayList
*/
private String handleArrayList(ObjectReference objRef, int depth) {
Field elementData = objRef.referenceType().fieldByName("elementData");
Field size = objRef.referenceType().fieldByName("size");
if (elementData != null && size != null) {
Value elementDataValue = objRef.getValue(elementData);
Value sizeValue = objRef.getValue(size);
if (elementDataValue instanceof ArrayReference && sizeValue instanceof IntegerValue) {
ArrayReference arrayReference = (ArrayReference) elementDataValue;
int sizeInt = ((IntegerValue) sizeValue).value();
StringBuilder sb = new StringBuilder("[");
// 递归判断ArrayList的每个元素
for (int i = 0; i < sizeInt; i++) {
Value value = arrayReference.getValue(i);
sb.append(this.inspectValue(value, depth + 1));
if (i != sizeInt - 1) {
sb.append(", ");
}
}
return sb.append("]").toString();
}
}
return "";
}
private boolean isArrayList(Value value) {
return value instanceof ObjectReference && "java.util.ArrayList".equals(value.type().name());
}
// 包装类集合
public final Map<String, String> WRAPPER_TO_PRIMITIVES = MapUtils.getMapFromList(
Arrays.asList(
"java.lang.Integer", "java.lang.Double", "java.lang.Character", "java.lang.Long",
"java.lang.Float", "java.lang.Boolean", "java.lang.Byte", "java.lang.Short"
),
Arrays.asList(
"int", "double", "char", "long",
"float", "boolean", "byte", "short"
)
);
public final Map<String, String> PRIMITIVES_TO_WRAPPER = MapUtils.getMapFromList(
Arrays.asList(
"int", "double", "char", "long",
"float", "boolean", "byte", "short"
),
Arrays.asList(
"java.lang.Integer", "java.lang.Double", "java.lang.Character", "java.lang.Long",
"java.lang.Float", "java.lang.Boolean", "java.lang.Byte", "java.lang.Short"
)
);
/**
* 通过包装类型返回对应的基本类型
* @param wrapperTypeName 包装类型
* @return 对应的基本类型
*/
public String getPrimitiveTypeByWrapperTypeName(String wrapperTypeName) {
return WRAPPER_TO_PRIMITIVES.get(wrapperTypeName);
}
/**
* 通过primitiveType获取对应的包装类型
* @param primitiveTypeName 基本类型
* @return 对应的包装类型
*/
public String getWrapperTypeByPrimitiveTypeName(String primitiveTypeName) {
return PRIMITIVES_TO_WRAPPER.get(primitiveTypeName);
}
/**
* 判断是不是primitiveType
* @param value
* @return
*/
public boolean isPrimitiveType(Value value) {
return value instanceof PrimitiveValue;
}
public boolean isPrimitiveType(String typeName) {
return PRIMITIVES_TO_WRAPPER.containsKey(typeName);
}
public boolean isWrapperType(String typeName) {
return WRAPPER_TO_PRIMITIVES.containsKey(typeName);
}
// 判断对象是否为包装类型
public boolean isWrapperType(Value value) {
if (value == null) {
return false;
}
if (value instanceof ObjectReference) {
// 获取对象的 ReferenceType
ObjectReference objRef = (ObjectReference) value;
ReferenceType refType = objRef.referenceType();
String className = refType.name();
// 判断该类是否是包装类型
return WRAPPER_TO_PRIMITIVES.containsKey(className);
}
return false; // 如果是基本类型值，则认为它不是包装类型
}
private String handleWrapper(ObjectReference objRef) {
if (objRef == null) {
return "null";
}
// 获取包装类型类的 'value' 字段
Field valueField = objRef.referenceType().fieldByName("value");
if (valueField != null) {
// 获取字段值
Value value = objRef.getValue(valueField);
// 将值转换为字符串并返回
return value.toString();
}
return "";
}
/**
* 获取包装类型类的 'value' 字段. 该字段是PrimitiveValue
* @param objRef
* @return
*/
public Value getWrapperValue(ObjectReference objRef) {
if (objRef == null) {
return null;
}
// 获取包装类型类的 'value' 字段
Field valueField = objRef.referenceType().fieldByName("value");
if (valueField != null) {
// 获取字段值
return objRef.getValue(valueField);
}
return null;
}
public List<String> getWrapperTypeList() {
return new ArrayList<>(WRAPPER_TO_PRIMITIVES.keySet());
}
}
2.2.2 不同类型的处理逻辑
在leetcode-runner中，将Value处理逻辑分为一下几大类
- 纯变量（如a，b，c这种单纯变量）
- 数组（如arr[0]）
- 表达式计算（如1+2，a+b这种）
- 实例方法调用（如demo.invoke()）
- 纯方法调用（ dfs()，takeLocalValue(a) ）
- 纯常量（如1，3.14，“nihao”， ‘&’）
- 运算符（如+,-,*,/,<<,&等）
以上五种类型的计算处理逻辑存在较大差异，因此单独令出来这五种类型
2.2.3 复杂表达式
a + 1很简单，只需要识别出a，获取a对应的Value，处理成int型常量，再将整体写入计算引擎即可
但如果表达式长这样呢？arr[b.invoke(1 + 2, c, arr2[0])] + dfs(1,2,c.invoke())呢？阁下又当如何应对呢？
我尼玛…
3. 计算架构
3.1 面向对象解决问题
面对复杂表达式识别计算，我们只能动用根源思想——面向对象来解决问题
所谓的面向对象，就是将数据结构和算法封装在同一个类中
如果我们将不同类型的表达式封装在对象中，这个对象又具备计算的能力。那么我们可以将表达式计算拆解为不同类型的类的组合，调用统一接口，得到计算值
像arr[b.invoke(1 + 2, c, arr2[0])] + dfs(1,2,c.invoke())这个表达式，从宏观上来看，就是一个计算表达式
在计算表达式当中，存在一个数组表达式arr[...]，和纯函数调用表达式dfs(...)
在数组的维度信息中，存在一个方法调用表达式——a.invoke(...)。方法调用的内部，又可以拆分为计算表达式1+2，纯变量表达式c，数组表达式arr2[0]
在纯函数调用的括号内，存在两个纯常量表达式——1，2，存在一个方法调用表达式c.invoke()
通过这么一套人肉拆解，如此复杂的表达式最终会被拆解为由基本表达式组合而成的复杂的表达式
有关具体的计算逻辑都被封装在对应类型当中，通过封装的方式减少单个类的处理复杂度，实现最终的计算
3.2 UML图
在leetcode-runner中，表达式统一由Token表示
Token封装了表达式的同时，也封装了表达式的计算逻辑
TokenFactory，负责识别用户输入的表达式，并根据不同的类型生成不同的表达式，在工厂内部，通过Rule判断输入类型
Rule，封装了表达式匹配规则。不同类型的规则对应着不同的Token
整体的工作流程如下
TokenFactory遍历所有Rule，执行匹配逻辑。如果匹配，则创建规则对应的Token
这里提供简化后的代码
Rule[] rules = new Rule[]{
new EvalRule(),
new OperatorRule(),
new PureCallRule(),
new PureCallRuleChain(), // 链式匹配, 后文会有介绍
new VariableRule(),
new VariableRuleChain(), // 因为链式匹配功能强大, 部分的Token功能被覆盖
new ArrayRule(),
new ArrayRuleChain(),
new ConstantRule()
};
/**
* 解析字符串得到对应的Token
*
* @param s 表达式
* @return token
*/
public Token parseToToken(String s, Context ctx) {
List<Rule> matches = new ArrayList<>(5);
// 根据解析规则解析得到不同的Token
for (Rule rule : rules) {
boolean match = rule.match(s);
if (match) {
matches.add(rule);
}
}
// 判断
if (matches.isEmpty()) {
throw new ComputeError("无法识别的内容! " + s);
}
if (matches.size() > 1) {
throw new ComputeError(s + " 被多条规则匹配! 请检查规则编写是否正确! + " + matches.stream().map(Rule::getName).collect(Collectors.joining(",")));
}
Rule targetRule = matches.get(0);
Class<? extends Token> tokenClass = targetRule.tokenClass();
String className = tokenClass.getName();
return tokenClass.getDeclaredConstructor(String.class, Context.class).newInstance(s, ctx);
}
3.3 递归处理
假设用户输入的是arr[1 + 2][c.invoke()]，在识别的过程中，它会被ArrayToken处理，但他在处理内部逻辑时，任然需要处理其他的内容，比如表达式计算1+2，再比如方法调用c.invoke()。如果这些处理逻辑都封装在ArayToken内部，那么这个类将会非常臃肿，因此在处理括号内部的内容时，需要将计算逻辑交给其他Token
也就是说，ArrayToken在处理时，需要使用TokenFactory提供的创建Token的功能，把处理逻辑外包除去
当然，不仅仅是ArrayToken需要调用TokenFactory外包，InvokeToken也需要外包功能
这种外包的思想，以笔者粗俗的间接，体现的就是递归思想
原本需要计算arr[1+2][c.invoke()]，现在只需要让别的Token计算1+2和c.invoke()
这就将原本复杂的计算逻辑拆解为更小的计算逻辑
因为这种递归的思想普遍存在于Token的计算过程中，因此在AbstractToken内部，封装了TokenFactory，方便子类直接使用，让每个Token都具备递归迭代处理表达式的能力
3.4 递归处理的case
以ArrayToken的计算逻辑为例
ArrayToken会优先解析出数组变量名，随后处理数组的每一个维度信息
对于维度内容，都会通过TokenFactory识别计算，交由别的Token递归处理
/**
* Array类型的Token, 规则详见{@link TokenFactory.ArrayRule}
*/
public static class ArrayToken extends AbstractToken {
public ArrayToken(String token, Context ctx) {
super(token, ctx);
}
/**
* 通过token查询array变量
* @return 返回array变量的引用
*/
private ArrayReference getArrayValue() {
return getArrayValue(this.token);
}
public ArrayReference getArrayValue(String arrayId) {
// 识别变量, 并获取array变量
int idx = arrayId.indexOf("[");
String vName = arrayId.substring(0, idx);
Value v = takeValueByVName(vName);
if (! (v instanceof ArrayReference) ) {
throw new ComputeError("变量 " + vName + " 不是数组类型");
}
return (ArrayReference) v;
}
// 该方法用于测试, 请勿随意调用
public List<String> getDimsStr() {
return getDimsStr(this.token);
}
/**
* 从token中解析维度信息
* @param token token 形如: arr[1][2][3], arr[1], arr[a.invoke()][1+2], [1][2] 属于完全的数组类型, 不会包含除数组外的任何内容. 此外, 为了配合隐式调用, 支持只有数组括号内容的解析
* @return 维度信息: 每一个维度的表达式: 如{1,2,3}; {1}, {a.invoke(), 1+2}, {1,2}
*/
public List<String> getDimsStr(String token) {
// 计算array的维度, 并计算索引
int idx = token.indexOf("[");
Pattern compile = Pattern.compile("(\\[[^\\]]*\\])");
String dimPart = token.substring(idx);
Matcher matcher = compile.matcher(dimPart);
List<String> dims = new ArrayList<>();
while (matcher.find()) {
// 匹配出每一个[]
String range = matcher.group().replace("[", "").replace("]", "");
dims.add(range);
}
return dims;
}
/**
* 通过this.token获取维度信息
* @return 维度信息: 每一个维度的整形数据
*/
public List<Integer> getDims() {
return getDims(this.token);
}
/**
* 从arrayId中解析维度
* @param arrayId 形如: arr[1][2][3], arr[1], arr[a.invoke()][1+2] 属于完全的数组类型, 不会包含除数组外的任何内容
* @return 维度信息: 每一个维度的int索引数据
*/
public List<Integer> getDims(String arrayId) {
List<String> dimsStr = getDimsStr(arrayId);
if (dimsStr.isEmpty()) {
throw new ComputeError("数组没有维度!");
}
List<Integer> dims = new ArrayList<>();
for (String s : dimsStr) {
// 获取索引数值
Token t = tf.parseToToken(s, ctx);
Value vv = t.getValue();
int value = getDimValue(vv);
dims.add(value);
}
return dims;
}
/**
* 将Value转换为索引数值
* @param vv Value
* @return int
*/
private int getDimValue(Value vv) {
String typeName = vv.type().name();
int value;
switch (typeName) {
case "int":
value = ((IntegerValue) vv).value();
break;
case "java.lang.Integer":
value = ((IntegerValue) WrapperObjReferenceToPrimitive(vv)).value();
break;
case "long":
// 忽略精度损失. 谁吃饱了撑着拿个long型的作为索引, feigebuge能支持这种离谱的计算都算是仁慈了
value = (int) ((LongValue) vv).value();
break;
case "java.lang.Long":
value = (int) ((LongValue) WrapperObjReferenceToPrimitive(vv)).value();
break;
case "short":
value = ((ShortValue) vv).value();
break;
case "java.lang.Short":
value = ((ShortValue) WrapperObjReferenceToPrimitive(vv)).value();
break;
default:
throw new ComputeError("数组索引必须为整型!!");
}
return value;
}
/**
* 迭代arrayReference
* @param array arrayReference
* @param dims 维度
* @return Value
*/
public Value itrArray(ArrayReference array, List<Integer> dims) {
return itrArray(array, dims, getArrayIdentify(this.token));
}
public Value itrArray(ArrayReference array, List<Integer> dims, String arrayId) {
Value value = null;
// 迭代array
for (int i = 0; i < dims.size(); i++) {
int dim = dims.get(i);
if (dim >= array.length()) {
throw new ComputeError("数组 " + arrayId + " 访问越界越界!! 数组第" + (i + 1) + "维度的元素个数=" + array.length() + ", 索引=" + dim);
}
if (dim <= -1) {
throw new ComputeError("数组索引必须为正数!! index = " + value);
}
value = array.getValue(dim);
// 如果没有迭代到最后一位, 则判断是否是数组类型
if (i != dims.size() - 1) {
if (!(value instanceof ArrayReference)) {
throw new ComputeError("变量" + arrayId + "第 " + i + " 维度不是数组类型, 是" + value.type().name() + "类型!!");
}
// 跟新array
array = (ArrayReference) value;
}
}
return value;
}
@Override
public Value getValue() {
// 获取array变量
ArrayReference array = getArrayValue();
// 获取索引
List<Integer> dims = getDims();
// 迭代所有的维度, 获取最终的value
return itrArray(array, dims);
}
protected Value getValue(String token) {
// 获取array变量
ArrayReference array = getArrayValue(token);
// 获取索引
List<Integer> dims = getDims(token);
// 迭代所有的维度, 获取最终的value
return itrArray(array, dims, token);
}
/**
* 从token解析数组的标识
* arr[1].invoke -> arr[1]
* @param token token
* @return 数组标识
*/
private String getArrayIdentify(String token) {
TokenFactory.MyMatcher matcher = arrayPattern.matcher(token);
if (! matcher.find()) {
throw new ComputeError("无法匹配数组, ArrayChainRule规则错误! " + token);
}
int end = matcher.end();
return token.substring(0, end);
}
}
在getValue()方法中，ArrayToken先调用getArrayValue()方法，获取数组变量的引用
随后通过调用getDims()方法，获得所有维度信息
最后，通过itrArray方法，迭代array变量，获取最终的值
以arr[0][0]为例，先获取arr对应的Value
然后解析出所有维度信息，封装为List。本例中将会得到{0, 0}
最后通过维度信息，迭代arr，获得arr[0][0]的数据
public Value getValue() {
// 获取array变量
ArrayReference array = getArrayValue();
// 获取索引
List<Integer> dims = getDims();
// 迭代所有的维度, 获取最终的value
return itrArray(array, dims);
}
在方法getDims()中，会调用TokenFactory，迭代计算维度信息
如下方代码所示，在循环体内，调用tf.parseToToken(s, ctx)获取对应Token，将计算逻辑交由对应的Token处理
/**
* 从arrayId中解析维度
* @param arrayId 形如: arr[1][2][3], arr[1], arr[a.invoke()][1+2] 属于完全的数组类型, 不会包含除数组外的任何内容
* @return 维度信息: 每一个维度的int索引数据
*/
public List<Integer> getDims(String arrayId) {
List<String> dimsStr = getDimsStr(arrayId);
if (dimsStr.isEmpty()) {
throw new ComputeError("数组没有维度!");
}
List<Integer> dims = new ArrayList<>();
for (String s : dimsStr) {
// 获取索引数值
Token t = tf.parseToToken(s, ctx);
Value vv = t.getValue();
int value = getDimValue(vv);
dims.add(value);
}
return dims;
}
4. 链式调用
在上一章节给出的计算架构已经能较为合理的处理绝大部分的内容。通过递归的处理，将不同的表达式交由不同的Token进行计算处理，简化每个类的处理逻辑
但如果用户给出的是链式表达式
比如：
- a.b.c
- a.invoke().c
- arr[0].invoke()
- arr[0].c
- dfs().arr[0].c
该抓虾还是抓虾。因为链式的计算逻辑和非链式的计算逻辑是不同的，除非在原有的ArrayToken，VariableToken等含有变量的Token中添加额外逻辑，否则只能是寄！
但如果在原有逻辑中添加新东西，就违背了开闭原则，而且会让单一类的功能变得臃肿
基于此，在leetcode-runner中，额外引入TokenChain，RuleChain。专门处理这种链式的计算
TokenChain
RuleChain
AbstractRuleChain
对于TokenChain，额外提供了getValue(PValue pV)方法，通过调用该方法，TokenChain就会知道，自己封装的Token并不是处于链式调用的开头，而是中间的某一段链式
其中，PValue封装前一段链式计算的结果
对于链式调用，只可能存在于数组类型，纯函数调用，实例方法调用，变量类型
因为链式存在的前提是拥有变量，因此新增ArrayTokenChain，PureCallTokenChain，InvokeTokenChain，VariableTokenChain
不过在后续代码编写的过程中，笔者发现VariableTokenChain的识别规则可以覆盖InvokeTokenChain的规则
所以InvokeTokenChain就被淘汰了
5. 链式Token
在leetcode-runner中，链式token的定义为
- token必须只能包含链式调用，不能是非链式
- 比如a.c就是链式，a不是链式。因此a不会被链式Token识别
- 不同类型的链式Token，识别的时候要求，token的开头必须是对应的基本类型
- 比如ArrayTokenChain，对应的基本类型是Array。所以他的合法Token必须形如：arr[0].invoke()，arr[0][1 + 2].c
在链式Token的计算过程中，需要迭代计算。而迭代就意味着离不开TokenFactory识别token，创建全新的TokenChain进行计算
为了更好的适配链式计算，TokenFactory新增parseToTokenChain(String s, Context ctx)：TokenChain
/**
* 解析TokenChain
* @param s s
* @param ctx ctx
* @return TokenChain
*/
public TokenChain parseToTokenChain(String s, Context ctx) {
List<Rule> matches = new ArrayList<>(3);
// 根据解析规则解析得到不同的Token
for (Rule rule : rules) {
if (rule.match(s)) {
matches.add(rule);
}
}
// 判断
if (matches.isEmpty()) {
throw new ComputeError("无法识别的内容! " + s);
}
if (matches.size() > 1) {
throw new ComputeError(s + " 被多条规则匹配! 请检查规则编写是否正确! + " + matches.stream().map(Rule::getName).collect(Collectors.joining(",")));
}
// 如果包含EvalRule, 报错
if (matches.stream().anyMatch(e -> e instanceof EvalRule)) {
throw new ComputeError(s + " 被EvalRule匹配! 无法得到对应的链式! parseToTokenChain方法使用错误! + " + matches.stream().map(Rule::getName).collect(Collectors.joining(",")));
}
Rule targetRule;
// 规则转换
if (! (matches.get(0) instanceof RuleChain) ) {
String key = matches.get(0).getName();
if (!ruleMap.containsKey(key)) {
throw new ComputeError(s + " 被" + key + "匹配! 无法得到对应的链式! parseToTokenChain方法使用错误! + " + matches.stream().map(Rule::getName).collect(Collectors.joining(",")));
}
targetRule = ruleMap.get(key);
}else {
targetRule = matches.get(0);
}
Class<? extends Token> tokenClass = targetRule.tokenClass();
String className = tokenClass.getName();
return (TokenChain) tokenClass.getDeclaredConstructor(String.class, Context.class).newInstance(s, ctx);
}
需要注意的是，如果匹配的是最后一段链式，是无法被RuleChain，也就是链式规则匹配的。因为它的token在结构上只有一个片段。但从整体上来看，它是链式的一部分，需要按照TokenChain的处理方式计算
所以parseToTokenChain需要做出额外的调整。如果规则识别得到的结果是ArrayRule，那么就需要转化为对应的链式规则ArrayRuleChain
原文地址：https://blog.csdn.net/qq_62835094/article/details/145180305
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！