java-topology/defects/otel-collector/unit/OtelCollector0002Test.java

package unit;

import java.util.*;

/**
 * Standalone unit test for otel-collector-0002: CWE-407.
 *
 * otel-collector-0002: pdata/pprofile StringTable SetString — O(N) linear scan
 *   during Profiles.MergeTo profile batching.
 *
 *   slow() simulates SetString with O(N) linear scan on every insert:
 *         building a string table of N unique entries costs O(N²) comparisons.
 *   fast() simulates SetStringWithIndex using a pre-built map for O(1) lookup:
 *         building the same table costs O(N) operations.
 *   Assert: slowOps > fastOps * 10x for N=500 strings.
 *
 * This mirrors the actual Go code in pdata/pprofile/string_table.go.
 */
public class OtelCollector0002Test {

    /**
     * Simulates SetString — linear scan of growing string table per insert.
     * Each function.switchDictionary calls SetString up to 3 times.
     * For F=500 functions × 3 calls × T=500 average table size: O(N²) total.
     */
    static long slowStringTable(int numStrings) {
        long ops = 0;
        List<String> table = new ArrayList<>(numStrings);
        for (int i = 0; i < numStrings; i++) {
            String val = "string_" + i;
            // SetString: linear scan for duplicate
            boolean found = false;
            for (String existing : table) {
                ops++;
                if (existing.equals(val)) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                table.add(val);
            }
        }
        return ops;
    }

    /**
     * Simulates SetStringWithIndex — pre-built map for O(1) lookup per insert.
     * StringTableIndex() is called once; subsequent SetStringWithIndex calls
     * are O(1) each.
     */
    static long fastStringTable(int numStrings) {
        long ops = 0;
        List<String> table = new ArrayList<>(numStrings);
        Map<String, Integer> index = new HashMap<>(numStrings);

        // StringTableIndex: O(N) one-time build
        for (int i = 0; i < table.size(); i++) {
            ops++;
            index.put(table.get(i), i);
        }

        for (int i = 0; i < numStrings; i++) {
            String val = "string_" + i;
            // SetStringWithIndex: O(1) map lookup
            ops++;
            if (!index.containsKey(val)) {
                index.put(val, table.size());
                table.add(val);
            }
        }
        return ops;
    }

    /**
     * Simulates Profiles.MergeTo with F functions each referencing 3 unique strings.
     * slow: calls SetString (O(T) scan) for each string reference.
     * fast: builds StringTableIndex once, then O(1) per lookup.
     */
    static long slowMergeTo(int numFunctions) {
        long ops = 0;
        List<String> dstTable = new ArrayList<>();
        for (int f = 0; f < numFunctions; f++) {
            // Each function has 3 string references: name, systemName, filename
            for (int attr = 0; attr < 3; attr++) {
                String val = "str_" + f + "_" + attr;
                // SetString: O(T) scan per call
                boolean found = false;
                for (String existing : dstTable) {
                    ops++;
                    if (existing.equals(val)) { found = true; break; }
                }
                if (!found) {
                    dstTable.add(val);
                }
            }
        }
        return ops;
    }

    static long fastMergeTo(int numFunctions) {
        long ops = 0;
        List<String> dstTable = new ArrayList<>();
        Map<String, Integer> strIdx = new HashMap<>();

        // StringTableIndex: build once before merge loop — O(T_initial)
        for (int i = 0; i < dstTable.size(); i++) {
            ops++;
            strIdx.put(dstTable.get(i), i);
        }

        for (int f = 0; f < numFunctions; f++) {
            for (int attr = 0; attr < 3; attr++) {
                String val = "str_" + f + "_" + attr;
                // SetStringWithIndex: O(1) map lookup
                ops++;
                if (!strIdx.containsKey(val)) {
                    strIdx.put(val, dstTable.size());
                    dstTable.add(val);
                }
            }
        }
        return ops;
    }

    public static void main(String[] args) {
        // Test 1: Basic SetString pattern
        int N = 500;
        long slow1 = slowStringTable(N);
        long fast1 = fastStringTable(N);
        System.out.printf("SetString N=%d: slow=%d ops, fast=%d ops, ratio=%.1fx%n",
                N, slow1, fast1, (double) slow1 / fast1);
        assert slow1 > fast1 * 10 :
                "Expected slowOps > fastOps*10x, got slow=" + slow1 + " fast=" + fast1;

        // Test 2: MergeTo simulation with F=300 functions × 3 string refs
        int F = 300;
        long slow2 = slowMergeTo(F);
        long fast2 = fastMergeTo(F);
        System.out.printf("MergeTo F=%d functions: slow=%d ops, fast=%d ops, ratio=%.1fx%n",
                F, slow2, fast2, (double) slow2 / fast2);
        assert slow2 > fast2 * 10 :
                "Expected slowOps > fastOps*10x, got slow=" + slow2 + " fast=" + fast2;

        // Test 3: Scaling — ratio should grow with N
        int N2 = 1000;
        long slow3 = slowStringTable(N2);
        long fast3 = fastStringTable(N2);
        double ratio3 = (double) slow3 / fast3;
        System.out.printf("SetString N=%d: slow=%d ops, fast=%d ops, ratio=%.1fx%n",
                N2, slow3, fast3, ratio3);
        assert ratio3 > 50 : "Expected ratio>50x at N=1000, got " + ratio3;

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