This is an automated email from the ASF dual-hosted git repository.
garydgregory pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-bcel.git
The following commit(s) were added to refs/heads/master by this push:
new 38434609 Subroutines.noRecursiveCalls enumerates exponentially many
JSR call paths (f008).
38434609 is described below
commit 38434609d1873d5230f6817bc843799cae10aa36
Author: Gary Gregory <[email protected]>
AuthorDate: Fri Sep 4 16:04:51 2026 -0400
Subroutines.noRecursiveCalls enumerates exponentially many JSR call
paths (f008).
---
src/changes/changes.xml | 1 +
.../bcel/verifier/structurals/Subroutines.java | 87 ++++++++++++++++------
2 files changed, 66 insertions(+), 22 deletions(-)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 4003f910..d12360b7 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -95,6 +95,7 @@ The <action> type attribute can be add,update,fix,remove.
<action type="fix" dev="ggregory" due-to="Gary
Gregory">JustIce Pass 2 LVT check amplifies each 10-byte entry into ~131k
hashtable operations (f005).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">Pass 3b dataflow stores frames per instruction and clones ever-growing
execution chains (f006).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">Cubic handlers × range × subroutines scan in Subroutines constructor
hangs JustIce Pass 3b (f007).</action>
+ <action type="fix" dev="ggregory" due-to="Gary
Gregory">Subroutines.noRecursiveCalls enumerates exponentially many JSR call
paths (f008).</action>
<!-- ADD -->
<action type="add" dev="ggregory" due-to="nbauma109,
Gary Gregory">Add support for permitted subclasses #493.</action>
<action type="add" dev="ggregory" due-to="nbauma109,
Gary Gregory">Add RecordComponentInfo.getAttribute(byte tag)#494.</action>
diff --git
a/src/main/java/org/apache/bcel/verifier/structurals/Subroutines.java
b/src/main/java/org/apache/bcel/verifier/structurals/Subroutines.java
index 6addf24d..2013b7b4 100644
--- a/src/main/java/org/apache/bcel/verifier/structurals/Subroutines.java
+++ b/src/main/java/org/apache/bcel/verifier/structurals/Subroutines.java
@@ -19,6 +19,7 @@
package org.apache.bcel.verifier.structurals;
import java.util.ArrayList;
+import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
@@ -223,7 +224,7 @@ public class Subroutines {
for (final int lv : lvs) {
s.add(Integer.valueOf(lv));
}
- getRecursivelyAccessedLocalsIndicesHelper(s, subSubs());
+ getRecursivelyAccessedLocalsIndicesHelper(s, subSubs(), new
HashSet<>());
final int[] ret = new int[s.size()];
int j = -1;
for (final Integer index : s) {
@@ -234,18 +235,24 @@ public class Subroutines {
}
/**
- * A recursive helper method for getRecursivelyAccessedLocalsIndices().
+ * A recursive helper method for
getRecursivelyAccessedLocalsIndices(). Every subroutine is visited at most
+ * once: since the computed set is a plain union, re-exploring an
already visited subroutine cannot add
+ * anything, but doing so once per call path made this helper
exponential in the depth of the JSR call graph
+ * (and made it recurse forever on a cyclic one).
*
* @see #getRecursivelyAccessedLocalsIndices()
*/
- private void getRecursivelyAccessedLocalsIndicesHelper(final
Set<Integer> set, final Subroutine[] subs) {
+ private void getRecursivelyAccessedLocalsIndicesHelper(final
Set<Integer> set, final Subroutine[] subs, final Set<Subroutine> visited) {
for (final Subroutine sub : subs) {
+ if (!visited.add(sub)) {
+ continue;
+ }
final int[] lvs = sub.getAccessedLocalsIndices();
for (final int lv : lvs) {
set.add(Integer.valueOf(lv));
}
if (sub.subSubs().length != 0) {
- getRecursivelyAccessedLocalsIndicesHelper(set,
sub.subSubs());
+ getRecursivelyAccessedLocalsIndicesHelper(set,
sub.subSubs(), visited);
}
}
}
@@ -577,7 +584,7 @@ public class Subroutines {
// This includes that subroutines may not call themselves
// recursively, even not through intermediate calls to other
// subroutines.
- noRecursiveCalls(getTopLevel(), new HashSet<>());
+ noRecursiveCalls(getTopLevel());
}
@@ -617,30 +624,66 @@ public class Subroutines {
}
/**
- * This (recursive) utility method makes sure that no subroutine is
calling a subroutine that uses the same local
+ * This utility method makes sure that no subroutine is calling a
subroutine that uses the same local
* variable for the RET as themselves (recursively). This includes that
subroutines may not call themselves recursively,
* even not through intermediate calls to other subroutines.
*
+ * Every subroutine is fully validated exactly once, memoizing the RET
local variable indices used anywhere in its
+ * call subtree. The former implementation re-explored a subroutine once
per call path, which is exponential in the
+ * number of subroutines for a layered JSR call graph.
+ *
* @throws StructuralCodeConstraintException if the above constraint is
not satisfied.
*/
- private void noRecursiveCalls(final Subroutine sub, final Set<Integer>
set) {
- final Subroutine[] subs = sub.subSubs();
-
- for (final Subroutine sub2 : subs) {
- final int index = ((RET)
sub2.getLeavingRET().getInstruction()).getIndex();
-
- if (!set.add(Integer.valueOf(index))) {
- // Don't use toString() here because of possibly infinite
recursive subSubs() calls then.
- final SubroutineImpl si = (SubroutineImpl) sub2;
- throw new StructuralCodeConstraintException("Subroutine with
local variable '" + si.localVariable + "', JSRs '" + si.theJSRs + "', RET '"
- + si.theRET + "' is called by a subroutine which uses the
same local variable index as itself; maybe even a recursive call?"
- + " JustIce's clean definition of a subroutine forbids
both.");
- }
-
- noRecursiveCalls(sub2, set);
+ private void noRecursiveCalls(final Subroutine sub) {
+ noRecursiveCalls(sub, new BitSet(), new HashMap<>(), new HashMap<>());
+ }
- set.remove(Integer.valueOf(index));
+ /**
+ * The recursive helper for {@link #noRecursiveCalls(Subroutine)}.
+ *
+ * @param sub the subroutine whose callees are validated.
+ * @param pathLocals compact ids (see {@code localIds}) of the RET local
variables used by the subroutines on the current call path.
+ * @param validated maps every fully validated subroutine to the compact
ids of the RET local variables used by it and its entire call subtree.
+ * @param localIds maps a RET local variable index to a compact id so the
bit sets stay small.
+ * @return the compact ids of the RET local variables used by {@code
sub}'s callees and their call subtrees.
+ * @throws StructuralCodeConstraintException if a subroutine calls a
subroutine using the same RET local variable.
+ */
+ private BitSet noRecursiveCalls(final Subroutine sub, final BitSet
pathLocals, final Map<Subroutine, BitSet> validated,
+ final Map<Integer, Integer> localIds) {
+ final BitSet subtreeLocals = new BitSet();
+
+ for (final Subroutine sub2 : sub.subSubs()) {
+ final Integer index = Integer.valueOf(((RET)
sub2.getLeavingRET().getInstruction()).getIndex());
+ final int localId = localIds.computeIfAbsent(index, k ->
Integer.valueOf(localIds.size())).intValue();
+
+ BitSet childLocals = validated.get(sub2);
+ if (childLocals == null) {
+ if (pathLocals.get(localId)) {
+ // sub2 uses a RET local variable also used by a
subroutine on the current call path;
+ // this also covers (possibly indirect) recursive calls.
+ throw recursiveCallException(sub2);
+ }
+ pathLocals.set(localId);
+ childLocals = noRecursiveCalls(sub2, pathLocals, validated,
localIds);
+ pathLocals.clear(localId);
+ childLocals.set(localId);
+ validated.put(sub2, childLocals);
+ } else if (childLocals.intersects(pathLocals)) {
+ // A subroutine in sub2's (already validated) call subtree
uses a RET local variable also
+ // used by a subroutine on the current call path.
+ throw recursiveCallException(sub2);
+ }
+ subtreeLocals.or(childLocals);
}
+ return subtreeLocals;
+ }
+
+ private static StructuralCodeConstraintException
recursiveCallException(final Subroutine sub2) {
+ // Don't use toString() here because of possibly infinite recursive
subSubs() calls then.
+ final SubroutineImpl si = (SubroutineImpl) sub2;
+ return new StructuralCodeConstraintException("Subroutine with local
variable '" + si.localVariable + "', JSRs '" + si.theJSRs + "', RET '"
+ + si.theRET + "' is called by a subroutine which uses the same
local variable index as itself; maybe even a recursive call?"
+ + " JustIce's clean definition of a subroutine forbids both.");
}
/**
