使用ASM (5.x)：如何在运行时用字节码检测递归方法调用？

Question

问题如下；Java代码中的方法是：

Rule foo()
{
    return sequence(foo(), x());
}

这将引发一个解析循环，当然应该避免这个循环；但是，这是合法的：

Rule foo()
{
    return sequence(x(), foo());
}

现在，在代码中的其他地方，我确实可以访问RuleMethod，这是一个扩展MethodNode的类，因此我可以访问以下信息：

• ruleMethod.name：foo；(在MethodNode中定义)
• ruleMethod.desc：()Lorg/parboiled/Rule; (用MethodNode定义)
• ruleMethod.ownerClass：com.github.fge.grappa.experiments.SelfReferringRule.MyParser (以RuleMethod定义)

上面第一个代码摘录的字节码如下：

Method 'foo':
 0    L0
 1     ALOAD 0
 2     ALOAD 0
 3     INVOKEVIRTUAL com/github/fge/grappa/experiments/SelfReferringRule$MyParser.foo ()Lorg/parboiled/Rule;
 4     ALOAD 0
 5     INVOKEVIRTUAL com/github/fge/grappa/experiments/SelfReferringRule$MyParser.x ()Lorg/parboiled/Rule;
 6     ICONST_0
 7     ANEWARRAY java/lang/Object
 8     INVOKEVIRTUAL com/github/fge/grappa/experiments/SelfReferringRule$MyParser.sequence (Ljava/lang/Object;Ljava/lang/Object;[Ljava/lang/Object;)Lorg/parboiled/Rule;
 9     ARETURN
10    L1

这意味着我拥有所有可用的信息，至少可以在上面的字节码中发现，foo()是-- sequence()调用的第一个参数，因为构造函数接受三个参数，堆栈上有三个元素。

但我当然不能在运行时进行“眼睛检查”。所以我需要一种方法来做这件事。

看起来我需要的是一个MethodVisitor和一些visitInsn()，然后看看有什么参数，并适当地检测.

但是我一点也不知道从哪里开始；在网上搜索似乎只给出了如何修改字节码的例子，而没有检测到这样的情况:/

我从哪里开始？

Answer 1

使用树api分析通常要容易得多，因为它允许您轻松地回溯并提供对流分析的支持。

如果我正确地理解了您的问题，那么您所需要做的(如果您希望支持的只是简单的案例，比如您的示例)是从调用到序列的反向扫描。正如您所知道的，代码编译堆栈上的内容必须是有效的，所以只需数回三个方法调用/ field get/ etc。

如果您想支持更复杂的场景，其中输入由分支语句分配给变量，则需要某种类型的流分析。

Answer 2

创建一个MethodVistor，当您处于方法的visitCode()中时，foo()查找visitMethodInsn()，如果visitMethodInsn()中的name参数是foo，则知道您对该方法进行了递归调用。

在字节码清单中，您有三个INVOKEVIRTUAL指令，这些指令由visitMethodInsn()函数按顺序访问。如果要检查顺序，可以跟踪发出方法调用的顺序。您将首先看到foo()，然后是x()，最后是sequence()。

3     INVOKEVIRTUAL com/github/fge/grappa/experiments/SelfReferringRule$MyParser.foo ()Lorg/parboiled/Rule;
4     ALOAD 0
5     INVOKEVIRTUAL com/github/fge/grappa/experiments/SelfReferringRule$MyParser.x ()Lorg/parboiled/Rule;
6     ICONST_0
7     ANEWARRAY java/lang/Object
8     INVOKEVIRTUAL com/github/fge/grappa/experiments/SelfReferringRule$MyParser.sequence (Ljava/lang/Object;Ljava/lang/Object;[Ljava/lang/Object;)Lorg/parboiled/Rule;

Answer 3

如果我正确地理解了你的意图，你想要检测到直接的左递归，这是半煮沸不能处理的。但是，左递归可以处理：

本质上，解析器必须检测左递归并在那里失败，但请记住，左递归发生了。当以递归方式使用的规则成功时，结果将保存为“种子”，解析过程将在原始输入位置重新启动。这一次，当左递归发生时，将使用种子而不是失败。这一过程是重复的。

有关这篇论文的解释，请参见packrat.pdf。该算法可以很容易地适应于PEG解析器。

一个类似于使用这种技术的解析库是https://github.com/ruediste/lambda-peg-parser。