Please examine each of the following points so that we can help you as soon and best as possible.
Describe the bug
Spark’s SCC-collapsing optimization merges PAG nodes which should be in separate components.
Input file
package soot.jimple.spark.solver;
import java.util.Collections;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import soot.Scene;
import soot.Type;
import soot.jimple.spark.pag.PAG;
import soot.jimple.spark.pag.VarNode;
import soot.options.SparkOptions;
public class SCCCollapserTest {
@Test
public void testSeparateComponents() {
Scene.v().loadBasicClasses();
Type type = Scene.v().getObjectType();
SparkOptions sparkOptions = new SparkOptions(Collections.emptyMap());
PAG pag = new PAG(sparkOptions);
VarNode a = pag.makeGlobalVarNode("a", type);
VarNode b = pag.makeGlobalVarNode("b", type);
VarNode c = pag.makeGlobalVarNode("c", type);
pag.addEdge(a, b);
pag.addEdge(a, c);
pag.addEdge(b, c);
SCCCollapser sccCollapser = new SCCCollapser(pag, false);
sccCollapser.collapse();
pag.cleanUpMerges();
assertEquals(a, a.getReplacement());
assertEquals(b, b.getReplacement());
assertEquals(c, c.getReplacement());
}
}
To reproduce
The second assertion fails in the test above.
Expected behavior
The test above should pass, since nodes a, b, and c should each be in their own component.
Stacktrace
N/A
Additional context
It appears that the SCC computation, following Kosaraju’s algorithm, is based on an invalid topological order. The topological sort should order node b before c. Instead, c gets ordered before b. This results in c being the SCC-root for b.
Please examine each of the following points so that we can help you as soon and best as possible.
Describe the bug
Spark’s SCC-collapsing optimization merges PAG nodes which should be in separate components.
Input file
To reproduce
The second assertion fails in the test above.
Expected behavior
The test above should pass, since nodes a, b, and c should each be in their own component.
Stacktrace
N/A
Additional context
It appears that the SCC computation, following Kosaraju’s algorithm, is based on an invalid topological order. The topological sort should order node b before c. Instead, c gets ordered before b. This results in c being the SCC-root for b.