java-topology/defects/influxdb/unit/InfluxDBTest.java

import java.util.*;

/**
 * CWE-407 unit tests for InfluxDB 3 (Rust) — two defects:
 *
 *  influxdb-0001: update_persisted_files_with_snapshot (runtime path)
 *                 iterates new_parquet_files and calls Vec::contains on
 *                 table_files for each → O(F × T) where F = new files,
 *                 T = existing files per table. Also: add_persisted_file
 *                 calls Vec::contains on the same growing Vec → O(N²) if
 *                 called N times.
 *                 Location: influxdb3_write/src/write_buffer/persisted_files.rs
 *
 *  influxdb-0002: TableDefinitionV1::add_columns loops over incoming columns
 *                 and calls Vec::contains on self.series_key for each tag
 *                 column → O(C × K) where C = new columns, K = existing
 *                 series key length.
 *                 Location: influxdb3_catalog/src/catalog/versions/v1.rs
 */
public class InfluxDBTest {

    // ── influxdb-0001 ─────────────────────────────────────────────────────────

    /** Defective: List.contains inside a filter loop → O(F × T). */
    static List<String> mergeFiles_defective(List<String> tableFiles, List<String> newFiles) {
        List<String> result = new ArrayList<>(tableFiles);
        List<String> filtered = new ArrayList<>();
        for (String f : newFiles) {
            if (!result.contains(f)) {   // O(T) per file
                filtered.add(f);
            }
        }
        result.addAll(filtered);
        return result;
    }

    /** Fixed: HashSet for O(1) membership per file → O(F + T). */
    static List<String> mergeFiles_fixed(List<String> tableFiles, List<String> newFiles) {
        Set<String> existing = new HashSet<>(tableFiles);
        List<String> result = new ArrayList<>(tableFiles);
        for (String f : newFiles) {
            if (existing.add(f)) {   // O(1): add returns false if already present
                result.add(f);
            }
        }
        return result;
    }

    // ── influxdb-0002 ─────────────────────────────────────────────────────────

    /**
     * Defective: for each tag column, call List.contains on growing seriesKey → O(C × K).
     * seriesKey grows as tags are accepted, making this quadratic when all columns are tags.
     */
    static List<Integer> addColumns_defective(List<Integer> seriesKey, List<Integer> tagColumns) {
        List<Integer> key = new ArrayList<>(seriesKey);
        for (int id : tagColumns) {
            if (!key.contains(id)) {   // O(K) per column
                key.add(id);
            }
        }
        return key;
    }

    /** Fixed: pre-build HashSet → O(C + K). */
    static List<Integer> addColumns_fixed(List<Integer> seriesKey, List<Integer> tagColumns) {
        Set<Integer> keySet = new HashSet<>(seriesKey);
        List<Integer> key = new ArrayList<>(seriesKey);
        for (int id : tagColumns) {
            if (keySet.add(id)) {   // O(1)
                key.add(id);
            }
        }
        return key;
    }

    // ── helpers ───────────────────────────────────────────────────────────────

    static long bench(Runnable r) {
        long t0 = System.nanoTime();
        r.run();
        return System.nanoTime() - t0;
    }

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

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

        // --- influxdb-0001 correctness ---
        {
            List<String> existing = new ArrayList<>();
            for (int i = 0; i < 100; i++) existing.add("file-" + i + ".parquet");
            List<String> incoming = new ArrayList<>();
            for (int i = 50; i < 150; i++) incoming.add("file-" + i + ".parquet");

            List<String> def = mergeFiles_defective(existing, incoming);
            List<String> fix = mergeFiles_fixed(existing, incoming);
            Collections.sort(def); Collections.sort(fix);
            if (def.equals(fix)) {
                System.out.println("PASS influxdb-0001 correctness (total=" + def.size() + ")");
                pass++;
            } else {
                System.out.println("FAIL influxdb-0001 correctness def=" + def.size() + " fix=" + fix.size());
                fail++;
            }
        }

        // --- influxdb-0001 performance ---
        {
            List<String> existing = new ArrayList<>();
            for (int i = 0; i < 2000; i++) existing.add("snap-" + i + ".parquet");
            List<String> incoming = new ArrayList<>();
            for (int i = 1000; i < 3000; i++) incoming.add("snap-" + i + ".parquet");

            long tDef = bench(() -> mergeFiles_defective(existing, incoming));
            long tFix = bench(() -> mergeFiles_fixed(existing, incoming));
            double ratio = (double) tDef / Math.max(tFix, 1);
            System.out.printf("PASS influxdb-0001 perf  defective=%dms fixed=%dms ratio=%.1fx%n",
                    tDef / 1_000_000, tFix / 1_000_000, ratio);
            if (ratio >= 2.0) pass++; else { System.out.println("FAIL influxdb-0001 perf ratio too low"); fail++; }
        }

        // --- influxdb-0002 correctness ---
        {
            List<Integer> seriesKey = new ArrayList<>();
            for (int i = 0; i < 10; i++) seriesKey.add(i);
            List<Integer> tagCols = new ArrayList<>();
            // Mix of existing and new tag column ids
            for (int i = 5; i < 50; i++) tagCols.add(i);

            List<Integer> def = addColumns_defective(seriesKey, tagCols);
            List<Integer> fix = addColumns_fixed(seriesKey, tagCols);
            if (def.equals(fix)) {
                System.out.println("PASS influxdb-0002 correctness (keySize=" + def.size() + ")");
                pass++;
            } else {
                System.out.println("FAIL influxdb-0002 correctness def=" + def + " fix=" + fix);
                fail++;
            }
        }

        // --- influxdb-0002 performance ---
        {
            List<Integer> seriesKey = new ArrayList<>();
            for (int i = 0; i < 100; i++) seriesKey.add(i);
            List<Integer> tagCols = new ArrayList<>();
            for (int i = 0; i < 5000; i++) tagCols.add(i);   // many duplicates + new

            long tDef = bench(() -> addColumns_defective(seriesKey, tagCols));
            long tFix = bench(() -> addColumns_fixed(seriesKey, tagCols));
            double ratio = (double) tDef / Math.max(tFix, 1);
            System.out.printf("PASS influxdb-0002 perf  defective=%dms fixed=%dms ratio=%.1fx%n",
                    tDef / 1_000_000, tFix / 1_000_000, ratio);
            if (ratio >= 2.0) pass++; else { System.out.println("FAIL influxdb-0002 perf ratio too low"); fail++; }
        }

        System.out.println();
        System.out.println("Results: " + pass + " PASS, " + fail + " FAIL");
        if (fail > 0) System.exit(1);
    }
}