package unit;

import java.util.*;

/**
 * GodotFontCyclicTest — godot-0009 / godot-0010
 *
 * Standalone Java proof of the CWE-407 diamond-recursion patterns in Godot's
 * font fallback graph traversal.
 *
 * Two defects:
 *   godot-0009: Font::_is_cyclic() — no visited set, O(F^D) exponential
 *               re-traversal of shared fallback nodes in a diamond graph;
 *               fix: HashSet<Font*> visited passed through recursion → O(N).
 *
 *   godot-0010: Font::_update_rids_fb() — no visited set, O(N^2) re-traversal
 *               of shared fonts; rids[] accumulates duplicate RIDs; called on
 *               every text render op; fix: HashSet<Font*> visited → O(N),
 *               each font RID collected exactly once.
 *
 * Run: javac -d . GodotFontCyclicTest.java && java -ea unit.GodotFontCyclicTest
 */
public class GodotFontCyclicTest {

    // ── Minimal Font model ───────────────────────────────────────────────────

    static class Font {
        final String name;
        final List<Font> fallbacks = new ArrayList<>();
        final int rid; // simulated RID (renderer handle)

        Font(String name, int rid) {
            this.name = name;
            this.rid = rid;
        }

        void addFallback(Font f) { fallbacks.add(f); }

        @Override public String toString() { return name; }
    }

    // ── godot-0009: _is_cyclic without visited set ───────────────────────────

    /**
     * SLOW: Simulates Font::_is_cyclic without a visited set (the defect).
     * Counts nodes visited. Returns {isCyclic, nodesVisited}.
     */
    static long[] isCyclicSlow(Font thisFont, Font p_f, int depth, int maxDepth) {
        if (depth > maxDepth) return new long[]{1, 1};
        if (p_f == null)      return new long[]{0, 1};
        if (p_f == thisFont)  return new long[]{1, 1};

        long visits = 1;
        for (Font f : p_f.fallbacks) {
            long[] result = isCyclicSlow(thisFont, f, depth + 1, maxDepth);
            visits += result[1];
            if (result[0] == 1) return new long[]{1, visits};
        }
        return new long[]{0, visits};
    }

    /**
     * FAST: Simulates Font::_is_cyclic_internal with a visited set (the fix).
     * Returns {isCyclic, nodesVisited}.
     */
    static long[] isCyclicFast(Font thisFont, Font p_f, int depth, int maxDepth,
                                Set<Font> visited) {
        if (depth > maxDepth) return new long[]{1, 1};
        if (p_f == null)      return new long[]{0, 1};
        if (p_f == thisFont)  return new long[]{1, 1};
        if (visited.contains(p_f)) return new long[]{0, 0}; // skip — already proven safe

        visited.add(p_f);
        long visits = 1;
        for (Font f : p_f.fallbacks) {
            long[] result = isCyclicFast(thisFont, f, depth + 1, maxDepth, visited);
            visits += result[1];
            if (result[0] == 1) return new long[]{1, visits};
        }
        return new long[]{0, visits};
    }

    /**
     * Simulate set_fallbacks(p_fallbacks) for a diamond graph.
     * thisFont wants to add F new fallbacks; each new fallback shares D shared fonts
     * in a diamond topology below it.
     *
     * Diamond structure (depth=3, fanout=2):
     *   new[0]   new[1]   ... new[F-1]
     *    / \      / \
     *  mid0 mid1 ...        (fanout fonts at depth 1)
     *    \ /
     *   leaf0  leaf1 ...   (shared leafs — same Font objects)
     *
     * With no visited set, each leaf is visited 2^(depth-1) times per call.
     */
    static long setFallbacksOpsSlowDiamond(int F, int fanout, int depth) {
        // Build diamond: fanout^0 nodes at top, fanout^1 mid, ...
        // All paths converge to `fanout^(depth-1)` shared leaf nodes.

        // Create shared leaves
        int numLeaves = fanout;
        Font[] leaves = new Font[numLeaves];
        for (int i = 0; i < numLeaves; i++) {
            leaves[i] = new Font("leaf" + i, 100 + i);
        }

        // Build a diamond of given depth over the leaves
        Font[] currentLevel = leaves;
        for (int d = 1; d < depth; d++) {
            Font[] nextLevel = new Font[currentLevel.length]; // same width (shared convergence)
            for (int i = 0; i < nextLevel.length; i++) {
                nextLevel[i] = new Font("mid_d" + d + "_" + i, 200 + d * 10 + i);
                for (Font leaf : currentLevel) {
                    nextLevel[i].addFallback(leaf); // all mids point to all leaves → diamond
                }
            }
            currentLevel = nextLevel;
        }
        Font[] topLevel = currentLevel;

        // Create F new fonts, each pointing to all top-level nodes
        long totalOps = 0;
        Font thisFont = new Font("this", 0);
        for (int f = 0; f < F; f++) {
            Font newFb = new Font("newFb" + f, 300 + f);
            for (Font top : topLevel) {
                newFb.addFallback(top);
            }
            // Simulate set_fallbacks calling _is_cyclic(newFb, 0) — no visited set
            long[] result = isCyclicSlow(thisFont, newFb, 0, 64);
            totalOps += result[1];
        }
        return totalOps;
    }

    static long setFallbacksOpsFastDiamond(int F, int fanout, int depth) {
        int numLeaves = fanout;
        Font[] leaves = new Font[numLeaves];
        for (int i = 0; i < numLeaves; i++) {
            leaves[i] = new Font("leaf" + i, 100 + i);
        }
        Font[] currentLevel = leaves;
        for (int d = 1; d < depth; d++) {
            Font[] nextLevel = new Font[currentLevel.length];
            for (int i = 0; i < nextLevel.length; i++) {
                nextLevel[i] = new Font("mid_d" + d + "_" + i, 200 + d * 10 + i);
                for (Font leaf : currentLevel) {
                    nextLevel[i].addFallback(leaf);
                }
            }
            currentLevel = nextLevel;
        }
        Font[] topLevel = currentLevel;

        long totalOps = 0;
        Font thisFont = new Font("this", 0);
        for (int f = 0; f < F; f++) {
            Font newFb = new Font("newFb" + f, 300 + f);
            for (Font top : topLevel) {
                newFb.addFallback(top);
            }
            // Fix: per-call visited set — shared across the entire _is_cyclic traversal
            Set<Font> visited = new HashSet<>();
            long[] result = isCyclicFast(thisFont, newFb, 0, 64, visited);
            totalOps += result[1];
        }
        return totalOps;
    }

    // ── godot-0010: _update_rids_fb without visited set ─────────────────────

    /**
     * SLOW: Simulates _update_rids_fb without visited set.
     * Returns list of collected RIDs (may contain duplicates).
     */
    static List<Integer> updateRidsSlow(Font p_f, int depth, int maxDepth) {
        List<Integer> rids = new ArrayList<>();
        updateRidsFbSlow(p_f, depth, maxDepth, rids);
        return rids;
    }

    static void updateRidsFbSlow(Font p_f, int depth, int maxDepth, List<Integer> rids) {
        if (depth > maxDepth || p_f == null) return;
        if (p_f.rid > 0) rids.add(p_f.rid);
        for (Font fb : p_f.fallbacks) {
            updateRidsFbSlow(fb, depth + 1, maxDepth, rids); // ← no visited guard
        }
    }

    /**
     * FAST: Simulates _update_rids_fb with visited set (the fix).
     * Returns list of collected RIDs (each font at most once).
     */
    static List<Integer> updateRidsFast(Font p_f, int depth, int maxDepth) {
        List<Integer> rids = new ArrayList<>();
        Set<Font> visited = new HashSet<>();
        updateRidsFbFast(p_f, depth, maxDepth, rids, visited);
        return rids;
    }

    static void updateRidsFbFast(Font p_f, int depth, int maxDepth,
                                  List<Integer> rids, Set<Font> visited) {
        if (depth > maxDepth || p_f == null) return;
        if (visited.contains(p_f)) return; // skip — already collected
        visited.add(p_f);
        if (p_f.rid > 0) rids.add(p_f.rid);
        for (Font fb : p_f.fallbacks) {
            updateRidsFbFast(fb, depth + 1, maxDepth, rids, visited);
        }
    }

    /**
     * Build a diamond font graph and count operations and RID list size.
     * Diamond: A → {B, C}, B → D, C → D (D is shared CJK fallback font).
     */
    static Font buildDiamondGraph(int sharedFonts) {
        Font root = new Font("root", 1);
        Font[] shared = new Font[sharedFonts];
        for (int i = 0; i < sharedFonts; i++) {
            shared[i] = new Font("cjk" + i, 10 + i);
        }
        // Create N "language" fonts, each referencing ALL shared CJK fonts
        int numLang = 4;
        for (int l = 0; l < numLang; l++) {
            Font lang = new Font("lang" + l, 50 + l);
            for (Font s : shared) lang.addFallback(s);
            root.addFallback(lang);
        }
        return root;
    }

    static void bench(String label, long slowOps, long fastOps) {
        double ratio = fastOps > 0 ? (double) slowOps / fastOps : 999;
        System.out.printf("  %-48s  slow: %,8d ops   fast: %,8d ops   ratio: %.0fx%n",
                label, slowOps, fastOps, ratio);
    }

    public static void main(String[] args) {
        System.out.println("=== UNIT godot-0009 / godot-0010: Godot Font Fallback CWE-407 ===");
        System.out.println();

        // ── godot-0009: _is_cyclic diamond test ─────────────────────────────
        System.out.println("godot-0009: Font::_is_cyclic — diamond fallback graph");

        // Diamond parameters
        int F = 5;      // number of new fallbacks to validate
        int fanout = 3; // fonts at each level
        int depth = 6;  // depth of the diamond graph

        long slowOps0009 = setFallbacksOpsSlowDiamond(F, fanout, depth);
        long fastOps0009 = setFallbacksOpsFastDiamond(F, fanout, depth);

        bench(String.format("isCyclic(F=%d,fanout=%d,depth=%d)", F, fanout, depth),
              slowOps0009, fastOps0009);

        // Deeper diamond
        int F2 = 4; int fanout2 = 4; int depth2 = 8;
        long slowOps0009b = setFallbacksOpsSlowDiamond(F2, fanout2, depth2);
        long fastOps0009b = setFallbacksOpsFastDiamond(F2, fanout2, depth2);
        bench(String.format("isCyclic(F=%d,fanout=%d,depth=%d)", F2, fanout2, depth2),
              slowOps0009b, fastOps0009b);

        System.out.println();

        // Assertions
        assert slowOps0009 > fastOps0009 * 10 :
            "godot-0009: expected slow >> fast; slow=" + slowOps0009 + " fast=" + fastOps0009;
        assert slowOps0009b > fastOps0009b * 100 :
            "godot-0009 deep: expected slow >> fast; slow=" + slowOps0009b + " fast=" + fastOps0009b;

        // ── godot-0010: _update_rids_fb diamond test ─────────────────────────
        System.out.println("godot-0010: Font::_update_rids_fb — duplicate RIDs in diamond graph");

        int sharedFonts = 8; // 8 shared CJK fallback fonts
        Font root = buildDiamondGraph(sharedFonts);

        List<Integer> slowRids = updateRidsSlow(root, 0, 64);
        List<Integer> fastRids = updateRidsFast(root, 0, 64);

        System.out.printf("  %-48s  slow rids.size(): %d   fast rids.size(): %d   duplicates eliminated: %d%n",
                String.format("updateRids(sharedFonts=%d, langFonts=4)", sharedFonts),
                slowRids.size(), fastRids.size(), slowRids.size() - fastRids.size());

        // Verify fast has no duplicates
        Set<Integer> fastRidSet = new HashSet<>(fastRids);
        assert fastRidSet.size() == fastRids.size() :
            "godot-0010: fast path must have no duplicate RIDs";

        // Verify slow has duplicates
        Set<Integer> slowRidSet = new HashSet<>(slowRids);
        assert slowRids.size() > slowRidSet.size() :
            "godot-0010: slow path must produce duplicate RIDs (diamond graph)";

        // Count ops (traversal steps)
        long[] slowResult = new long[]{0};
        long[] fastResult = new long[]{0};
        countOpsUpdateRidsSlow(root, 0, 64, slowResult);
        Set<Font> vis = new HashSet<>();
        countOpsUpdateRidsFast(root, 0, 64, fastResult, vis);

        bench(String.format("updateRids(sharedFonts=%d, langFonts=4)", sharedFonts),
              slowResult[0], fastResult[0]);

        assert slowResult[0] > fastResult[0] * 2 :
            "godot-0010: expected slow >> fast; slow=" + slowResult[0] + " fast=" + fastResult[0];

        System.out.println();
        System.out.println("ALL ASSERTIONS PASS");
        System.out.println();
        System.out.println("Summary:");
        System.out.println("  godot-0009: Font::_is_cyclic O(F^D) → O(N) — visited set eliminates");
        System.out.println("             exponential re-traversal of shared fallback fonts");
        System.out.println("  godot-0010: Font::_update_rids_fb — no visited set causes duplicate");
        System.out.println("             RIDs and O(N^2) traversal; fix collects each font once");
    }

    static void countOpsUpdateRidsSlow(Font p_f, int depth, int maxDepth, long[] ops) {
        if (depth > maxDepth || p_f == null) return;
        ops[0]++;
        for (Font fb : p_f.fallbacks) countOpsUpdateRidsSlow(fb, depth + 1, maxDepth, ops);
    }

    static void countOpsUpdateRidsFast(Font p_f, int depth, int maxDepth,
                                        long[] ops, Set<Font> visited) {
        if (depth > maxDepth || p_f == null) return;
        if (visited.contains(p_f)) return;
        visited.add(p_f);
        ops[0]++;
        for (Font fb : p_f.fallbacks) countOpsUpdateRidsFast(fb, depth + 1, maxDepth, ops, visited);
    }
}