java-topology/defects/clementine/test/ClementineSongSenderTest.java

import java.util.*;

/**
 * CWE-407 simulation: Clementine SongSender indexOf/contains O(N^2)
 * Three call sites:
 *   1. SendAlbum: album.indexOf(s) in loop -> O(N^2)
 *   2. SendPlaylist: song_list.indexOf(s) in loop + requested_ids.contains O(P*R)
 *   3. SendUrls: song_list.indexOf(s) in loop -> O(N^2)
 *
 * Fix: Use integer counter instead of indexOf; QSet for requested_ids.
 */
public class ClementineSongSenderTest {

    // --- Defective: indexOf in loop ---
    static long sendAlbumDefective(List<String> album) {
        long ops = 0;
        for (String s : album) {
            // Simulates album.indexOf(s) — linear scan
            for (int i = 0; i < album.size(); i++) {
                ops++;
                if (album.get(i).equals(s)) break;
            }
        }
        return ops;
    }

    static long sendPlaylistDefective(List<String> songList, List<Integer> requestedIds) {
        long ops = 0;
        // Count phase with contains check
        for (String s : songList) {
            int id = s.hashCode();
            // requestedIds.contains(id) — linear scan
            for (int rid : requestedIds) {
                ops++;
                if (rid == id) break;
            }
        }
        // Send phase with indexOf + contains
        for (String s : songList) {
            int id = s.hashCode();
            for (int rid : requestedIds) {
                ops++;
                if (rid == id) break;
            }
            // indexOf
            for (int i = 0; i < songList.size(); i++) {
                ops++;
                if (songList.get(i).equals(s)) break;
            }
        }
        return ops;
    }

    // --- Fixed: counter + HashSet ---
    static long sendAlbumFixed(List<String> album) {
        long ops = 0;
        int pos = 0;
        for (String s : album) {
            pos++;
            ops++; // counter increment is O(1)
        }
        return ops;
    }

    static long sendPlaylistFixed(List<String> songList, List<Integer> requestedIds) {
        long ops = 0;
        Set<Integer> requestedIdsSet = new HashSet<>(requestedIds);
        ops += requestedIds.size();

        // Count phase
        for (String s : songList) {
            requestedIdsSet.contains(s.hashCode());
            ops++;
        }
        // Send phase
        int pos = 0;
        for (String s : songList) {
            pos++;
            requestedIdsSet.contains(s.hashCode());
            ops += 2; // counter + contains
        }
        return ops;
    }

    public static void main(String[] args) {
        int[] sizes = {100, 250, 500, 1000};

        System.out.println("=== Clementine SongSender CWE-407 Test ===");
        System.out.println("Defect: indexOf(s) O(N^2) in SendAlbum/SendPlaylist/SendUrls");
        System.out.println();

        // Test 1: SendAlbum
        System.out.println("--- SendAlbum (indexOf in loop) ---");
        System.out.printf("%-8s %-15s %-15s %-10s %-6s%n",
                "N", "Defective ops", "Fixed ops", "Ratio", "PASS");

        boolean allPass = true;
        for (int n : sizes) {
            List<String> album = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                album.add("track" + String.format("%04d", i) + ".mp3");
            }

            long defOps = sendAlbumDefective(album);
            long fixOps = sendAlbumFixed(album);
            double ratio = (double) defOps / fixOps;
            boolean pass = ratio > 5.0;
            allPass &= pass;

            System.out.printf("%-8d %-15d %-15d %-10.1fx %-6s%n",
                    n, defOps, fixOps, ratio, pass ? "PASS" : "FAIL");
        }

        // Test 2: SendPlaylist with requested_ids
        System.out.println();
        System.out.println("--- SendPlaylist (indexOf + requested_ids.contains) ---");
        System.out.printf("%-8s %-15s %-15s %-10s %-6s%n",
                "N", "Defective ops", "Fixed ops", "Ratio", "PASS");

        for (int n : sizes) {
            List<String> songList = new ArrayList<>();
            List<Integer> requestedIds = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                String name = "song" + String.format("%04d", i);
                songList.add(name);
                requestedIds.add(name.hashCode());
            }

            long defOps = sendPlaylistDefective(songList, requestedIds);
            long fixOps = sendPlaylistFixed(songList, requestedIds);
            double ratio = (double) defOps / fixOps;
            boolean pass = ratio > 5.0;
            allPass &= pass;

            System.out.printf("%-8d %-15d %-15d %-10.1fx %-6s%n",
                    n, defOps, fixOps, ratio, pass ? "PASS" : "FAIL");
        }

        System.out.println();
        System.out.println("Overall: " + (allPass ? "PASS" : "FAIL"));
        System.exit(allPass ? 0 : 1);
    }
}