8.2 接口与组件

用于代码分析的 ASM API 在 org.objectweb.asm.tree.analysis 包中。由包的名字可以看出，它是基于树 API 的。事实上，这个包提供了一个进行正向数据流分析的框架。 为了能够以准确度不一的取值进行各种数据流分析，数据流分析算法分为两部分：一种是固定的，由框架提供，另一种是变化的，由用户提供。更准确地说：

• 整体数据流分析算法、将适当数量的值从栈中弹出和压回栈中的任务仅实现一次，用于 Analyzer 和 Frame 类中的所有内容。
• 合并值的任何和计算值集并集的任务由用户定义的 Interpreter 和 Value 抽象类的子类提供。提供了几个预定义的子类，下面几节将进行介绍。

尽管框架的主要目的是执行数据流分析，但 Analyzer 类也可构造所分析方法的控制流图。为此，可以重写这个类的newControlFlowEdge 和newControlFlowExceptionEdge 方法， 它们默认情况下不做任何事情。其结果可用于进行控制流分析。

8.2.1 基本数据流分析

Interpreter 类是抽象类中预定义的 Interpreter 子类之一。它利用在 BasicValue 类中定义的七个值集来模拟字节代码指令的效果：

• UNINITIALIZED_VALUE 指“所有可能值”。
• INT_VALUE 指“所有 int、short、byte、boolean 或 char 值”。
• FLOAT_VALUE 指“所有 float 值”。
• LONG_VALUE 指“所有 long 值”。
• DOUBLE_VALUE 指“所有 double 值”。
• REFERENCE_VALUE 指“所有对象和数组值”。
• RETURNADDRESS_VALUE 用于子例程（见附录 A.2）

这个解释器本身不是非常有用（方法帧中已经提供了这一信息，而且更为详细——见 3.1.5 节），但它可以用作一个“空的”Interpreter 实现，以构建一个 Analyzer。这个分析器可用于检测方法中的不可及代码。事实上，即使是沿着跳转指令的两条分支，也不可能到达那些不能由第一条指令到达的代码。其结果是：在分析之后，无论什么样的 Interpreter 实现，由Analyzer.getFrames 方法返回的计算帧，对于不可到达的指令都是 null。这一特性可用于非常轻松地实现一个 RemoveDeadCodeAdapter 类（还有一些更高效的方法，但它们需要编写的代码也更多）：

public class RemoveDeadCodeAdapter extends MethodVisitor {
    String owner;
    MethodVisitor next;

    public RemoveDeadCodeAdapter(String owner, int access, String name, String desc, MethodVisitor mv) {
        super(ASM4, new MethodNode(access, name, desc, null, null));
        this.owner = owner;
        next = mv;
    }

    @Override
    public void visitEnd() {
        MethodNode mn = (MethodNode) mv;
        Analyzer<BasicValue> a =
                new Analyzer<BasicValue>(new BasicInterpreter());
        try {
            a.analyze(owner, mn);

            Frame<BasicValue>[] frames = a.getFrames();
            AbstractInsnNode[] insns = mn.instructions.toArray();
            for (int i = 0; i < frames.length; ++i) {
                if (frames[i] == null && !(insns[i] instanceof LabelNode)) {
                    mn.instructions.remove(insns[i]);
                }
            }
        } catch (AnalyzerException ignored) {
        }
        mn.accept(next);
    }
}

结合 7.1.5 节的 OptimizeJumpAdapter，由跳转优化器引入的死代码被移除。例如，对checkAndSetF 方法应用这个适配器链将给出：

在 OptimizeJump 之后	在 RemoveDeadCode 之后
ILOAD 1	ILOAD 1
IFLT label	IFLT label
ALOAD 0	ALOAD 0
ILOAD 1	ILOAD 1
PUTFIELD ...	PUTFIELD ...
RETURN	RETURN
label:	label:
F_SAME	F_SAME
NEW ...	NEW ...
DUP	DUP
INVOKESPECIAL ...	INVOKESPECIAL ...
ATHROW	ATHROW
end:	end:

注意，死标记未被移除。这是故意的：它实际上没有改变最终代码，但避免删除一个尽管不可及但可能会在比如 LocalVariableNode 中引用的标记。

8.2.2 基本数据流验证器

BasicVerifier 类扩展 BasicInterpreter 类。它使用的事件集相同，但不同于BasicInterpreter 的是，它会验证对指令的使用是否正确。例如，它会验证 IADD 指令的操作数为 INTEGER_VALUE 值（而 BasicInterpreter 只是返回结果，即 INTEGER_VALUE）。这个类可在开发类生成器或适配器时进行调试，见 3.3 节的解释。例如，这个类可以检测出 ISTORE 1 ALOAD 1 序列是无效的。它可以包含在像下面这样一个实用工具适配器中（在实践中，使用 CheckMethodAdapter 类要更简单一些，可以将其配置为使用 BasicVerifier）：

public class BasicVerifierAdapter extends MethodVisitor {
    String owner;
    MethodVisitor next;

    public BasicVerifierAdapter(String owner, int access, String name, String desc, MethodVisitor mv) {
        super(ASM4, new MethodNode(access, name, desc, null, null));
        this.owner = owner;
        next = mv;
    }

    @Override
    public void visitEnd() {

        MethodNode mn = (MethodNode) mv;
        Analyzer<BasicValue> a =
                new Analyzer<BasicValue(new BasicVerifier()); try {
            a.analyze(owner, mn);
        } catch (AnalyzerException e) {
            throw new RuntimeException(e.getMessage());
        }
        mn.accept(next);
    }
}

8.2.3 简单的数据流验证器

SimpleVerifier 类扩展了 BasicVerifier 类。它使用更多的集合来模拟字节代码指令的执行：事实上，每个类都由它自己的集合表示，这个集合表示了这个类的所有可能对象。因此， 它可以检测出更多的错误，比如如下情况：一个对象的可能值为“所有 Thread 类型的对象”，却对这个对象调用在 String 类中定义的方法。

这个类使用 Java 反射 API，以执行与类层次结构有关的验证和计算。然后，它将一个方法引用的类加载到 JVM 中。这一默认行为可以通过重写这个类的受保护方法来改变。

和 BasicVerifier 一样，这个类也可以在开发类生成器或适配器时使用，以便更轻松地找出 Bug。但它也可以用于其他目的。下面这个转换就是一个例子，它会删除方法中不必要的类型转换：如果这个分析器发现 CHECKCAST to 指令的操作数是“所有 from 类型的对象”值集， 如果 to 是 from 的一个超类，那 CHECKCAST 指令就是不必要的，可以删除。这个转换的实现如下：

public class RemoveUnusedCastTransformer extends MethodTransformer {
    String owner;

    public RemoveUnusedCastTransformer(String owner, MethodTransformer mt) {
        super(mt);
        this.owner = owner;
    }

    @Override
    public MethodNode transform(MethodNode mn) {
        Analyzer<BasicValue> a =
                new Analyzer<BasicValue>(new SimpleVerifier());
        try {
            a.analyze(owner, mn);
            Frame<BasicValue>[] frames = a.getFrames();
            AbstractInsnNode[] insns = mn.instructions.toArray();
            for (int i = 0; i < insns.length; ++i) {
                AbstractInsnNode insn = insns[i];
                if (insn.getOpcode() == CHECKCAST) {
                    Frame f = frames[i];
                    if (f != null && f.getStackSize() > 0) {
                        Object operand = f.getStack(f.getStackSize() - 1);
                        Class<?> to = getClass(((TypeInsnNode) insn).desc);
                        Class<?> from = getClass(((BasicValue) operand).getType());
                        if (to.isAssignableFrom(from)) {
                            mn.instructions.remove(insn);
                        }
                    }
                }

            }
        } catch (AnalyzerException ignored) {
        }
        return mt == null ? mn : mt.transform(mn);
    }

    private static Class<?> getClass(String desc) {
        try {
            return Class.forName(desc.replace(’ /’, ’.’));
        } catch (ClassNotFoundException e) {
            throw new RuntimeException(e.toString());
        }
    }

    private static Class<?> getClass(Type t) {
        if (t.getSort() == Type.OBJECT) {
            return getClass(t.getInternalName());
        }
        return getClass(t.getDescriptor());
    }
}

但对于 Java 6 类（或者用 COMPUTE_FRAMES 升级到 Java 6 的类），用 AnalyzerAdapter 以核心 API 来完成这一任务要更简单一些，效率要高得多：

public class RemoveUnusedCastAdapter extends MethodVisitor {
    public AnalyzerAdapter aa;

    public RemoveUnusedCastAdapter(MethodVisitor mv) {
        super(ASM4, mv);
    }

    @Override
    public void visitTypeInsn(int opcode, String desc) {
        if (opcode == CHECKCAST) {
            Class<?> to = getClass(desc);
            if (aa.stack != null && aa.stack.size() > 0) {
                Object operand = aa.stack.get(aa.stack.size() - 1);
                if (operand instanceof String) {
                    Class<?> from = getClass((String) operand);
                    if (to.isAssignableFrom(from)) {
                        return;
                    }
                }
            }
        }
        mv.visitTypeInsn(opcode, desc);
    }

    private static Class getClass(String desc) {
        try {
            return Class.forName(desc.replace(’ /’, ’.’));
        } catch (ClassNotFoundException e) {
            throw new RuntimeException(e.toString());
        }
    }
}

8.2.4 用户定义的数据流分析

假定我们希望检测出一些字段访问和方法调用的对象可能是 null，比如在下面的源代码段中（其中，第一行防止一些编译器检测 Bug，否则它可能会被认作一个“o 可能尚未初始化”错误）：

Object o = null; while (...) {
o = ...;
}
o.m(...); // 潜在的 NullPointerException！

于是我们需要一个数据流分析，它能告诉我们，在对应于最后一行的 INVOKEVIRTUAL 指令处，与 o 对应的底部栈值可能为 null。为此，我们需要为引用值区分三个集合：包含 null 值的 NULL 集，包含所有非 null 引用值的 NONNULL 集，以及包含所有引用值的 MAYBENULL 集。于是，我们只需要考虑 ACONST_NULL 将 NULL 集压入操作数栈，而所有其他在栈中压入引用值的指令将压入 NONNULL 集（换句话说，我们考虑任意字段访问或方法调用的结果都不是null，如果不对程序的所有类进行全局分析，那就不可能得到更好的结果）。为表示 NULL 和NONNULL 集的并集，MAYBENULL 集合是必需的。

上述规则必须在一个自定义的 Interpreter 子类中实现。完全可以从头实现它，但也可以通过扩展 BasicInterpreter 类来实现它，而且这种做法要容易得多。事实上，如果我们考虑 BasicValue.REFERENCE_VALUE 对应于 NONNULL 集，那只需重写模拟 ACONST_NULL 执行的方法，使它返回 NULL，还有计算并集的方法：

class IsNullInterpreter extends BasicInterpreter {
    public final static BasicValue NULL = new BasicValue(null);
    public final static BasicValue MAYBENULL = new BasicValue(null);

    public IsNullInterpreter() {
        super(ASM4);
    }

    @Override
    public BasicValue newOperation(AbstractInsnNode insn) {
        if (insn.getOpcode() == ACONST_NULL) {
            return NULL;
        }
        return super.newOperation(insn);
    }

    @Override
    public BasicValue merge(BasicValue v, BasicValue w) {
        if (isRef(v) && isRef(w) && v != w) {
            return MAYBENULL;
        }
        return super.merge(v, w);
    }

    private boolean isRef(Value v) {
        return v == REFERENCE_VALUE || v == NULL || v == MAYBENULL;
    }
}

于是，可以很容易地利用这个 IsNullnterpreter 来检测那些可能导致潜在 null 指针异常的指令：

public class NullDereferenceAnalyzer {
    public List<AbstractInsnNode> findNullDereferences(String owner, MethodNode mn) throws AnalyzerException {
        List<AbstractInsnNode> result = new ArrayList<AbstractInsnNode>();
        Analyzer<BasicValue> a =
                new Analyzer<BasicValue>(new IsNullInterpreter());
        a.analyze(owner, mn);
        Frame<BasicValue>[] frames = a.getFrames();
        AbstractInsnNode[] insns = mn.instructions.toArray();
        for (int i = 0; i < insns.length; ++i) {
            AbstractInsnNode insn = insns[i];
            if (frames[i] != null) {

                Value v = getTarget(insn, frames[i]);
                if (v == NULL || v == MAYBENULL) {
                    result.add(insn);
                }
            }
        }
        return result;
    }

    private static BasicValue getTarget(AbstractInsnNode insn, Frame<BasicValue> f) {
        switch (insn.getOpcode()) {
            case GETFIELD:
            case ARRAYLENGTH:
            case MONITORENTER:
            case MONITOREXIT:
                return getStackValue(f, 0);
            case PUTFIELD:
                return getStackValue(f, 1);
            case INVOKEVIRTUAL:
            case INVOKESPECIAL:
            case INVOKEINTERFACE:
                String desc = ((MethodInsnNode) insn).desc;
                return getStackValue(f, Type.getArgumentTypes(desc).length);
        }
        return null;
    }

    private static BasicValue getStackValue(Frame<BasicValue> f, int index) {
        int top = f.getStackSize() - 1;
        return index <= top ? f.getStack(top - index) : null;
    }
}

findNullDereferences 方法用一个 IsNullInterpreter 分析给定方法节点。然后， 对于每条指令，检测其引用操作数（如果有的话）的可能值集是不是 NULL 集或 NONNULL 集。若是，则这条指令可能导致一个 null 指针异常，将它添加到此类指令的列表中，该列表由这一方法返回。

getTarget 方法在帧 f 中返回与 insn 对象操作数相对应的 Value，如果 insn 没有对象操作数，则返回 null。它的主要任务就是计算这个值相对于操作数栈顶端的偏移量，这一数量取决于指令类型。

8.2.5 控制流分析

控制流分析可以有许多应用。一个简单的例子就是计算方法的“圆复杂度”。这一度量定义为控制流图的边数减去节点数，再加上 2。例如，checkAndSetF 方法的控制流图如 8.1.2 节所示，它的圈复杂度为 11-12+2=1。这个度量很好地表征了一个方法的“复杂度”（在这个数字与方法的平均 bug 数之间存在一种关联）。它还给出了要“正确”测试一个方法所需要的建议测试情景数目。

用于计算这一度量的算法可以用 ASM 分析框架来实现（还有仅基于核心 API 的更高效方法， 只是它们需要编写更多的代码）。第一步是构建控制流图。我们在本章开头曾经说过，可以通过重写 Analyzer 类的 newControlFlowEdge 方法来构建。这个类将节点表示为 Frame 对象。 如果希望将这个图存储在这些对象中，则需要扩展 Frame 类：

class Node<V extends Value> extends Frame<V> {
    Set<Node<V>> successors = new HashSet<Node<V>>();

    public Node(int nLocals, int nStack) {
        super(nLocals, nStack);
    }

    public Node(Frame<? extends V> src) {
        super(src);
    }
}

随后，可以提供一个 Analyzer 子类，用来构建控制流图，并用它的结果来计算边数、节点数，最终计算出圈复杂度：

public class CyclomaticComplexity {
    public int getCyclomaticComplexity(String owner, MethodNode mn) throws AnalyzerException {
        Analyzer<BasicValue> a =
                new Analyzer<BasicValue>(new BasicInterpreter()) {
                    protected Frame<BasicValue> newFrame(int nLocals, int nStack) {
                        return new Node<BasicValue>(nLocals, nStack);
                    }

                    protected Frame<BasicValue> newFrame(Frame<? extends BasicValue> src) {
                        return new Node<BasicValue>(src);
                    }

                    protected void newControlFlowEdge(int src, int dst) {
                        Node<BasicValue> s = (Node<BasicValue>) getFrames()[src];
                        s.successors.add((Node<BasicValue>) getFrames()[dst]);
                    }
                };
        a.analyze(owner, mn);
        Frame<BasicValue>[] frames = a.getFrames();
        int edges = 0;
        int nodes = 0;
        for (int i = 0; i < frames.length; ++i) {
            if (frames[i] != null) {
                edges += ((Node<BasicValue>) frames[i]).successors.size();
                nodes += 1;
            }
        }
        return edges - nodes + 2;
    }
}