java-topology/defects/pandas/unit/PandasTest.java

package unit;

import java.util.*;

/**
 * Standalone unit tests for pandas CWE-407 defects.
 *
 * pandas-0001: Styler render — O(R×H) hidden_rows list membership in render loops
 *   Simulates: [r for r in range(len(index)) if r not in self.hidden_rows]
 *   and the body-cell loop: if r not in self.hidden_rows (O(H) per row).
 *   slow(): list.contains(r) per row iteration — O(R×H)
 *   fast(): HashSet.contains(r) per row iteration — O(R)
 *   Assert: slowOps >= fastOps * 10 for R=2000 rows, H=500 hidden rows
 *
 * pandas-0002: _get_level_lengths — hidden_elements list scan O(R×L×H)
 *   Real code (pandas/io/formats/style_render.py:1840-1870):
 *     hidden_elements: Sequence[int] = []     # list
 *     for j, row in enumerate(lvl):
 *         if j not in hidden_elements:        # O(H) list scan per cell
 *   Called on every Styler.render()/to_html()/to_latex() with MultiIndex.
 *   Fix: frozenset(hidden_elements) for O(1) membership.
 */
public class PandasTest {

    // ── pandas-0001 ───────────────────────────────────────────────────────────

    /**
     * Slow path: hidden rows stored as a List<Integer>.
     * Each membership test scans up to H entries — O(H) per row.
     * Total for R rows: O(R × H).
     *
     * @param totalRows   total row count R
     * @param hiddenRows  set of hidden row indices (stored as list)
     * @return op count (each element comparison in list.contains() = 1 op)
     */
    static long slowRenderRows(int totalRows, List<Integer> hiddenRows) {
        long ops = 0;
        List<Integer> visibleRows = new ArrayList<>();

        for (int r = 0; r < totalRows; r++) {
            // Mirrors: if r not in self.hidden_rows — linear scan
            boolean found = false;
            for (int i = 0; i < hiddenRows.size(); i++) {
                ops++;
                if (hiddenRows.get(i) == r) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                visibleRows.add(r);
            }
        }
        return ops;
    }

    /**
     * Fast path: hidden rows stored as a HashSet<Integer>.
     * Each membership test is O(1). Total for R rows: O(R + H).
     *
     * @param totalRows   total row count R
     * @param hiddenRows  set of hidden row indices (stored as list — converted once)
     * @return op count (1 op per row for set.contains + 1 op per hidden row to build set)
     */
    static long fastRenderRows(int totalRows, List<Integer> hiddenRows) {
        long ops = 0;
        List<Integer> visibleRows = new ArrayList<>();

        // Build set once: O(H)
        Set<Integer> hiddenSet = new HashSet<>(hiddenRows.size() * 2);
        for (int h : hiddenRows) {
            hiddenSet.add(h);
            ops++;
        }

        for (int r = 0; r < totalRows; r++) {
            ops++;                              // O(1) set.contains
            if (!hiddenSet.contains(r)) {
                visibleRows.add(r);
            }
        }
        return ops;
    }

    static void testRenderRows() {
        int R = 2000;   // total rows
        int H = 500;    // hidden rows (scattered through the middle — maximizes scan depth)

        List<Integer> hiddenRows = new ArrayList<>(H);
        // Hidden rows in the range [R/4, R/4+H) — they appear late in the list
        for (int i = R / 4; i < R / 4 + H; i++) hiddenRows.add(i);

        long slowOps = slowRenderRows(R, hiddenRows);
        long fastOps = fastRenderRows(R, hiddenRows);

        System.out.printf(
            "pandas-0001  R=%-5d H=%-4d  slowOps=%-8d  fastOps=%-6d  ratio=%.1fx%n",
            R, H, slowOps, fastOps, (double) slowOps / fastOps
        );

        assert slowOps > fastOps * 10 :
            "pandas-0001 FAIL: expected slowOps > 10×fastOps, got " + slowOps + " vs " + fastOps;
        System.out.println("pandas-0001  PASS");
    }

    // ── pandas-0002: _get_level_lengths hidden_elements list scan ─────────────

    /**
     * Simulates _get_level_lengths with list hidden_elements.
     * For each (level, row) cell in a MultiIndex render, checks j not in hidden_elements.
     * O(R×L×H) total — R rows, L levels, H hidden elements.
     */
    static long slowGetLevelLengths(int rows, int levels, int hidden) {
        List<Integer> hiddenElements = new ArrayList<>();
        for (int i = 0; i < hidden; i++) hiddenElements.add(i * 2);  // spread out evenly

        long ops = 0;
        for (int lev = 0; lev < levels; lev++) {
            for (int j = 0; j < rows; j++) {
                // Main check: if j not in hidden_elements
                boolean found = false;
                for (int k = 0; k < hiddenElements.size(); k++) {
                    ops++;
                    if (hiddenElements.get(k) == j) { found = true; break; }
                }
                // Else-branch check (sparsify path also checks j not in hidden_elements)
                if (!found) {
                    for (int k = 0; k < hiddenElements.size(); k++) {
                        ops++;
                        if (hiddenElements.get(k) == j) { found = true; break; }
                    }
                }
            }
        }
        return ops;
    }

    /**
     * Simulates fixed _get_level_lengths with frozenset(hidden_elements).
     * O(R×L) total — O(1) set probe per cell.
     */
    static long fastGetLevelLengths(int rows, int levels, int hidden) {
        Set<Integer> hiddenSet = new HashSet<>();
        for (int i = 0; i < hidden; i++) hiddenSet.add(i * 2);

        long ops = 0;
        for (int lev = 0; lev < levels; lev++) {
            for (int j = 0; j < rows; j++) {
                ops++;  // O(1) set probe (main check)
                if (!hiddenSet.contains(j)) ops++;  // O(1) set probe (else-branch)
            }
        }
        return ops;
    }

    static void testGetLevelLengths() {
        int R = 5000, L = 3, H = 2500;

        long slowOps = slowGetLevelLengths(R, L, H);
        long fastOps = fastGetLevelLengths(R, L, H);

        System.out.printf(
            "pandas-0002  R=%-5d L=%d H=%-5d  slowOps=%-12d  fastOps=%-8d  ratio=%.1fx%n",
            R, L, H, slowOps, fastOps, (double) slowOps / fastOps
        );

        assert slowOps > fastOps * 100 :
            "pandas-0002 FAIL: expected >100x ratio; slow=" + slowOps + " fast=" + fastOps;
        System.out.println("pandas-0002  PASS");
    }

    // ── main ──────────────────────────────────────────────────────────────────

    public static void main(String[] args) {
        int pass = 0, total = 2;

        try { testRenderRows(); pass++; } catch (AssertionError e) { System.err.println(e.getMessage()); }
        try { testGetLevelLengths(); pass++; } catch (AssertionError e) { System.err.println(e.getMessage()); }

        System.out.printf("%n%d/%d PASS%n", pass, total);
        if (pass != total) System.exit(1);
    }
}