Incorrect topological sorting leads to incorrect SCC computation in Spark

[michael-emmi]

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.

[michael-emmi]

This appears to have been broken by #1843