java-topology/defects/ruffle-0001/test/RuffleTest.java

import java.util.*;

/**
 * ruffle-0001: AVM2 optimizer type_aware.rs process_jump() worklist dedup
 *
 * Defect: worklist is a Vec<usize>; process_jump() calls worklist.contains()
 * before pushing a new block ID. Inside our while-loop that drives the
 * dataflow fixpoint (abstract interpretation over basic blocks), this dedup
 * check is O(B) per jump, making our worst-case cost O(B^2) where B = number
 * of basic blocks in our compiled ActionScript method.
 *
 * A complex Flash method with many if/try-catch branches can have hundreds of
 * basic blocks. O(B^2) makes our optimizer visibly slow on pathological SWFs.
 *
 * Fix: carry a companion HashSet<usize> (worklist_set) alongside our Vec.
 *   - On push: if worklist_set.insert(id) returns true, push to Vec.
 *   - On pop:  worklist_set.remove(id).
 * Dedup is now O(1); total pass complexity drops from O(B^2) to O(B).
 *
 * Measurement approach: count scan-length ops for defective vs fixed.
 * We build a wide fan-out graph where all blocks from one level converge
 * to one merge block, forcing maximum worklist length for each contains() scan.
 */
public class RuffleTest {

    /**
     * Build a graph: block 0 fans out to blocks 1..N-1,
     * all of which fan back to block N (merge point, no successors).
     * This maximizes worklist size when processing convergence.
     * Block 0 -> {1, 2, ..., N-1}
     * Block i (1..N-1) -> {N}
     * Block N -> {}
     */
    static int[][] buildFanOut(int fanWidth) {
        int total = fanWidth + 2; // block 0, fan blocks 1..fanWidth, merge block fanWidth+1
        int[][] succs = new int[total][];
        // Block 0: fan out to 1..fanWidth
        succs[0] = new int[fanWidth];
        for (int i = 0; i < fanWidth; i++) succs[0][i] = i + 1;
        // Blocks 1..fanWidth: all go to merge
        int merge = fanWidth + 1;
        for (int i = 1; i <= fanWidth; i++) succs[i] = new int[]{merge};
        // Merge block: no successors
        succs[merge] = new int[]{};
        return succs;
    }

    /**
     * Simulate defective algorithm: Vec.contains() O(|worklist|) per check.
     * Returns total scan steps paid.
     */
    static long defectiveWorklist(int[][] successors) {
        List<Integer> worklist = new ArrayList<>();
        worklist.add(0);
        long totalScanSteps = 0;
        while (!worklist.isEmpty()) {
            int blockId = worklist.remove(worklist.size() - 1);
            for (int succ : successors[blockId]) {
                totalScanSteps += worklist.size(); // O(B) linear scan cost
                if (!worklist.contains(succ)) {
                    worklist.add(succ);
                }
            }
        }
        return totalScanSteps;
    }

    /**
     * Simulate fixed algorithm: HashSet.add() O(1) per check.
     * Returns total hash ops paid.
     */
    static long fixedWorklist(int[][] successors) {
        List<Integer> worklist = new ArrayList<>();
        Set<Integer> worklistSet = new HashSet<>();
        worklist.add(0);
        worklistSet.add(0);
        long totalHashOps = 0;
        while (!worklist.isEmpty()) {
            int blockId = worklist.remove(worklist.size() - 1);
            worklistSet.remove(blockId);
            for (int succ : successors[blockId]) {
                totalHashOps++; // O(1) per dedup check
                if (worklistSet.add(succ)) {
                    worklist.add(succ);
                }
            }
        }
        return totalHashOps;
    }

    public static void main(String[] args) {
        System.out.println("ruffle-0001: AVM2 optimizer worklist dedup O(B^2) -> O(B)");

        // Small: fanWidth=10 (12 total blocks)
        int W_SMALL = 10;
        int[][] g10 = buildFanOut(W_SMALL);
        long defSmall = defectiveWorklist(g10);
        long fixSmall = fixedWorklist(g10);
        System.out.printf("  fanWidth=%d  defective_scan_steps=%d  fixed_hash_ops=%d%n",
                W_SMALL, defSmall, fixSmall);
        assert defSmall > fixSmall
                : "defective must pay more scan steps than fixed (small): def=" + defSmall + " fix=" + fixSmall;

        // Medium: fanWidth=100
        int W_MED = 100;
        int[][] g100 = buildFanOut(W_MED);
        long defMed = defectiveWorklist(g100);
        long fixMed = fixedWorklist(g100);
        double ratioMed = (double) defMed / Math.max(1, fixMed);
        System.out.printf("  fanWidth=%d  defective_scan_steps=%d  fixed_hash_ops=%d  ratio=%.1fx%n",
                W_MED, defMed, fixMed, ratioMed);
        assert ratioMed >= 20.0
                : "expected >=20x ratio at fanWidth=100, got " + ratioMed;

        // Large: fanWidth=500
        int W_LARGE = 500;
        int[][] g500 = buildFanOut(W_LARGE);
        long defLarge = defectiveWorklist(g500);
        long fixLarge = fixedWorklist(g500);
        double ratioLarge = (double) defLarge / Math.max(1, fixLarge);
        System.out.printf("  fanWidth=%d  defective_scan_steps=%d  fixed_hash_ops=%d  ratio=%.1fx%n",
                W_LARGE, defLarge, fixLarge, ratioLarge);
        assert ratioLarge >= 100.0
                : "expected >=100x ratio at fanWidth=500, got " + ratioLarge;

        // Correctness: fixed and defective must agree on which blocks to visit
        int W_CHECK = 20;
        int[][] gCheck = buildFanOut(W_CHECK);
        Set<Integer> visitedDef = visitedByDefective(gCheck);
        Set<Integer> visitedFix = visitedByFixed(gCheck);
        assert visitedDef.equals(visitedFix)
                : "both must visit same blocks: def=" + visitedDef + " fix=" + visitedFix;

        System.out.println("PASS");
    }

    static Set<Integer> visitedByDefective(int[][] succ) {
        Set<Integer> visited = new LinkedHashSet<>();
        List<Integer> wl = new ArrayList<>(List.of(0));
        while (!wl.isEmpty()) {
            int id = wl.remove(wl.size() - 1);
            visited.add(id);
            for (int s : succ[id]) {
                if (!wl.contains(s) && !visited.contains(s)) wl.add(s);
            }
        }
        return visited;
    }

    static Set<Integer> visitedByFixed(int[][] succ) {
        Set<Integer> visited = new LinkedHashSet<>();
        List<Integer> wl = new ArrayList<>(List.of(0));
        Set<Integer> inWl = new HashSet<>(List.of(0));
        while (!wl.isEmpty()) {
            int id = wl.remove(wl.size() - 1);
            inWl.remove(id);
            visited.add(id);
            for (int s : succ[id]) {
                if (!visited.contains(s) && inWl.add(s)) wl.add(s);
            }
        }
        return visited;
    }
}