java-topology/defects/exposed/unit/ExposedTest.java

package unit;
import java.util.*;

/**
 * Unit test for Exposed ORM CWE-407 defects.
 *
 * exposed-0001: mapMissingColumnStatements — O(N×M) list scan during schema migration
 *   SchemaUtilityApi.kt:80-89 — find{} over existingColumns per column, contains() over List per index-column
 *
 * exposed-0002: isAKeyword — O(K) linear keyword scan per identifier (cache-miss path)
 *   IdentifierManagerApi.kt:72 — keywords.any { equals(it, true) } over ~500-entry list
 *
 * exposed-0003: Table.clone — O(P×C) repeated List allocation in property filter
 *   Table.kt:1686 — consParams.map(KParameter::name) allocated fresh each filter predicate call
 */
public class ExposedTest {

    // -------------------------------------------------------------------------
    // exposed-0001: schema migration column lookup
    // -------------------------------------------------------------------------

    /** Simulate a column name (just a String for this model). */
    static String[] makeColumns(int n) {
        String[] cols = new String[n];
        for (int i = 0; i < n; i++) cols[i] = "column_" + i;
        return cols;
    }

    /** Simulate existing DB column metadata (same schema, all present). */
    static String[] makeExistingColumns(int n) {
        String[] existing = new String[n];
        for (int i = 0; i < n; i++) existing[i] = "column_" + i;
        return existing;
    }

    /**
     * Slow path: for each column, do a linear scan over existingColumns to find it (as Exposed does).
     * Returns ops count.
     */
    static long schemaMigrationSlow(String[] columns, String[] existingColumns) {
        long ops = 0;
        // Step 1: find existing columns — O(N*M)
        Map<String, String> existingTableColumns = new HashMap<>();
        for (String col : columns) {
            for (String existing : existingColumns) {
                ops++;
                if (col.equalsIgnoreCase(existing)) {
                    existingTableColumns.put(col, existing);
                    break;
                }
            }
        }
        // Step 2: compute missing columns
        List<String> missingTableColumns = new ArrayList<>();
        for (String col : columns) {
            if (!existingTableColumns.containsKey(col)) missingTableColumns.add(col);
        }
        // Step 3: for each index (simulate 20 indices with 3 cols each), check if any col is missing — O(I*C*M)
        int numIndices = 20;
        int colsPerIndex = 3;
        for (int i = 0; i < numIndices; i++) {
            for (int c = 0; c < colsPerIndex; c++) {
                String indexCol = columns[(i * colsPerIndex + c) % columns.length];
                for (String missing : missingTableColumns) {
                    ops++;
                    if (indexCol.equals(missing)) break;
                }
            }
        }
        return ops;
    }

    /**
     * Fast path: pre-build HashMap for O(1) lookup (the CWE-407 fix).
     * Returns ops count.
     */
    static long schemaMigrationFast(String[] columns, String[] existingColumns) {
        long ops = 0;
        // Step 1: build O(1) lookup map — O(M) once
        Map<String, String> existingByName = new HashMap<>();
        for (String existing : existingColumns) {
            ops++;
            existingByName.put(existing.toLowerCase(), existing);
        }
        Map<String, String> existingTableColumns = new HashMap<>();
        for (String col : columns) {
            ops++;
            String found = existingByName.get(col.toLowerCase());
            if (found != null) existingTableColumns.put(col, found);
        }
        // Step 2: compute missing columns
        List<String> missingTableColumns = new ArrayList<>();
        for (String col : columns) {
            if (!existingTableColumns.containsKey(col)) missingTableColumns.add(col);
        }
        // Step 3: use HashSet for O(1) missing-column membership — O(I*C)
        Set<String> missingSet = new HashSet<>(missingTableColumns);
        int numIndices = 20;
        int colsPerIndex = 3;
        for (int i = 0; i < numIndices; i++) {
            for (int c = 0; c < colsPerIndex; c++) {
                String indexCol = columns[(i * colsPerIndex + c) % columns.length];
                ops++;
                missingSet.contains(indexCol);
            }
        }
        return ops;
    }

    // -------------------------------------------------------------------------
    // exposed-0002: keyword lookup
    // -------------------------------------------------------------------------

    static List<String> makeKeywordList(int k) {
        List<String> kw = new ArrayList<>(k);
        for (int i = 0; i < k; i++) kw.add("KEYWORD_" + i);
        // Add a few real SQL keywords at the end to ensure misses go all the way
        kw.add("SELECT"); kw.add("FROM"); kw.add("WHERE"); kw.add("TABLE");
        return kw;
    }

    /**
     * Slow: linear scan with case-insensitive compare (as Exposed does via .any { equals(it, true) }).
     */
    static long keywordLookupSlow(List<String> keywords, String[] identifiers) {
        long ops = 0;
        Map<String, Boolean> cache = new HashMap<>();
        for (String id : identifiers) {
            String lower = id.toLowerCase();
            if (!cache.containsKey(lower)) {
                boolean found = false;
                for (String kw : keywords) {
                    ops++;
                    if (lower.equalsIgnoreCase(kw)) { found = true; break; }
                }
                cache.put(lower, found);
            }
        }
        return ops;
    }

    /**
     * Fast: pre-built lowercase HashSet, O(1) lookup per cache miss.
     */
    static long keywordLookupFast(List<String> keywords, String[] identifiers) {
        long ops = 0;
        // Pre-build lowercased set — O(K) once
        Set<String> keywordsLower = new HashSet<>();
        for (String kw : keywords) { ops++; keywordsLower.add(kw.toLowerCase()); }
        Map<String, Boolean> cache = new HashMap<>();
        for (String id : identifiers) {
            String lower = id.toLowerCase();
            if (!cache.containsKey(lower)) {
                ops++;
                cache.put(lower, keywordsLower.contains(lower));
            }
        }
        return ops;
    }

    // -------------------------------------------------------------------------
    // exposed-0003: clone() constructor parameter name lookup
    // -------------------------------------------------------------------------

    static String[] makePropertyNames(int p) {
        String[] props = new String[p];
        for (int i = 0; i < p; i++) props[i] = "prop_" + i;
        return props;
    }

    static String[] makeConsParamNames(int c) {
        String[] params = new String[c];
        for (int i = 0; i < c; i++) params[i] = "prop_" + i; // first C props are constructor params
        return params;
    }

    /**
     * Slow: for each property, call consParams.map(name) fresh — allocates a new List per property.
     * Simulates the Kotlin lambda `it.name in consParams.map(KParameter::name)`.
     * Op count = P * C (each property scans all C param names via List.contains).
     */
    static long cloneFilterSlow(String[] memberProperties, String[] consParamNames, int cloneCalls) {
        long ops = 0;
        Set<String> mutableProps = new HashSet<>(Arrays.asList(memberProperties)); // all are mutable in sim
        for (int call = 0; call < cloneCalls; call++) {
            for (String prop : memberProperties) {
                // Simulate: consParams.map(KParameter::name) — creates a new List, then List.contains = O(C)
                List<String> paramNameList = new ArrayList<>(Arrays.asList(consParamNames));
                for (String pn : paramNameList) {
                    ops++;
                    if (pn.equals(prop)) break;
                }
                boolean inMutable = mutableProps.contains(prop);
                @SuppressWarnings("unused")
                boolean keep = inMutable;
            }
        }
        return ops;
    }

    /**
     * Fast: pre-compute consParamNames as HashSet once before the filter loop.
     * Op count = C (build set once) + P (O(1) lookups).
     */
    static long cloneFilterFast(String[] memberProperties, String[] consParamNames, int cloneCalls) {
        long ops = 0;
        Set<String> mutableProps = new HashSet<>(Arrays.asList(memberProperties));
        for (int call = 0; call < cloneCalls; call++) {
            // Pre-compute once per clone() call — O(C)
            Set<String> paramNameSet = new HashSet<>();
            for (String pn : consParamNames) { ops++; paramNameSet.add(pn); }
            for (String prop : memberProperties) {
                ops++;
                boolean inParams = paramNameSet.contains(prop);
                boolean inMutable = mutableProps.contains(prop);
                @SuppressWarnings("unused")
                boolean keep = inMutable || inParams;
            }
        }
        return ops;
    }

    // -------------------------------------------------------------------------
    // Harness
    // -------------------------------------------------------------------------

    static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
        slow.run(); fast.run(); // warmup
        long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime() - t0) / 1_000_000;
        long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime() - t1) / 1_000_000;
        double r = fOps > 0 ? (double) sOps / fOps : 0;
        System.out.printf("  %-52s  slow:%4dms (%,d ops)  fast:%4dms (%,d ops)  speedup:%.0fx%n",
                label, sMs, sOps, fMs, fOps, r);
    }

    public static void main(String[] args) {
        System.out.println("=== UNIT exposed-0001..: Exposed ORM CWE-407 ===");

        // exposed-0001: schema migration — N=500 columns, M=500 existing
        final int N0 = 500;
        final String[] cols0 = makeColumns(N0);
        final String[] existing0 = makeExistingColumns(N0);
        final long[] ops0 = new long[2];
        ops0[0] = schemaMigrationSlow(cols0, existing0);
        ops0[1] = schemaMigrationFast(cols0, existing0);
        bench(
            "exposed-0001 schemaMigration N=500cols/M=500existing",
            () -> schemaMigrationSlow(cols0, existing0),
            () -> schemaMigrationFast(cols0, existing0),
            ops0[0], ops0[1]
        );

        // exposed-0002: keyword lookup — K=504 keywords, 2000 identifiers
        final int K = 504;
        final int I = 2000;
        final List<String> keywords = makeKeywordList(K);
        final String[] identifiers = new String[I];
        for (int i = 0; i < I; i++) identifiers[i] = "col_" + (i % 200); // 200 distinct
        final long[] ops2 = new long[2];
        ops2[0] = keywordLookupSlow(keywords, identifiers);
        ops2[1] = keywordLookupFast(keywords, identifiers);
        bench(
            "exposed-0002 keywordLookup K=504 I=2000",
            () -> keywordLookupSlow(keywords, identifiers),
            () -> keywordLookupFast(keywords, identifiers),
            ops2[0], ops2[1]
        );

        // exposed-0003: clone filter — P=20 properties, C=15 constructor params, 5000 clone calls
        final int P = 20, C = 15, CALLS = 5000;
        final String[] memberProps = makePropertyNames(P);
        final String[] consParams3 = makeConsParamNames(C);
        final long[] ops3 = new long[2];
        ops3[0] = cloneFilterSlow(memberProps, consParams3, CALLS);
        ops3[1] = cloneFilterFast(memberProps, consParams3, CALLS);
        bench(
            "exposed-0003 cloneFilter P=20 C=15 calls=5000",
            () -> cloneFilterSlow(memberProps, consParams3, CALLS),
            () -> cloneFilterFast(memberProps, consParams3, CALLS),
            ops3[0], ops3[1]
        );

        // Assertions
        int pass = 0;
        long s0 = ops0[0], f0 = ops0[1];
        long s2 = ops2[0], f2 = ops2[1];
        long s3 = ops3[0], f3 = ops3[1];

        assert s0 > f0 * 5 : "exposed-0001 expected >5x ops reduction; slow=" + s0 + " fast=" + f0;
        pass++;
        assert s2 > f2 * 5 : "exposed-0002 expected >5x ops reduction; slow=" + s2 + " fast=" + f2;
        pass++;
        assert s3 > f3 * 2 : "exposed-0003 expected >2x ops reduction; slow=" + s3 + " fast=" + f3;
        pass++;

        System.out.printf("%d/3 PASS%n", pass);
    }
}