java-topology/defects/ipfs-cluster-0001/test/ipfs_cluster_0001_test.go

package ipfscluster0001

// Unit test for ipfs-cluster-0001: filterMetrics containsPeer O(N²)
//
// Defect: filterMetrics() calls containsPeer() (linear scan) for blacklist,
// currentAllocs, and priorityList on every metric in our nested loop.
// Complexity: O(M * (B + C + P)) where M = total metrics, B/C/P = list sizes.
//
// Fix: Convert slices to map[string]struct{} sets before our loop.
// Patched complexity: O(M + B + C + P).

import (
	"fmt"
	"testing"
)

// Simulates our peer.ID as a string (same underlying type in libp2p).
type peerID string

// --- BEFORE: linear scan (defective) ---

func containsPeer(list []peerID, peer peerID) bool {
	for _, p := range list {
		if p == peer {
			return true
		}
	}
	return false
}

func filterMetricsBefore(
	metrics []peerID,
	blacklist []peerID,
	currentAllocs []peerID,
	priorityList []peerID,
) (cur, prio, cand []peerID) {
	for _, m := range metrics {
		switch {
		case containsPeer(blacklist, m):
			continue
		case containsPeer(currentAllocs, m):
			cur = append(cur, m)
		case containsPeer(priorityList, m):
			prio = append(prio, m)
		default:
			cand = append(cand, m)
		}
	}
	return
}

// --- AFTER: set lookup (patched) ---

func peerInSet(set map[peerID]struct{}, p peerID) bool {
	_, ok := set[p]
	return ok
}

func toSet(list []peerID) map[peerID]struct{} {
	s := make(map[peerID]struct{}, len(list))
	for _, p := range list {
		s[p] = struct{}{}
	}
	return s
}

func filterMetricsAfter(
	metrics []peerID,
	blacklist []peerID,
	currentAllocs []peerID,
	priorityList []peerID,
) (cur, prio, cand []peerID) {
	blacklistSet := toSet(blacklist)
	currentAllocsSet := toSet(currentAllocs)
	prioritySet := toSet(priorityList)

	for _, m := range metrics {
		switch {
		case peerInSet(blacklistSet, m):
			continue
		case peerInSet(currentAllocsSet, m):
			cur = append(cur, m)
		case peerInSet(prioritySet, m):
			prio = append(prio, m)
		default:
			cand = append(cand, m)
		}
	}
	return
}

// --- Correctness ---

func TestCorrectness(t *testing.T) {
	metrics := []peerID{"p1", "p2", "p3", "p4", "p5", "p6"}
	blacklist := []peerID{"p1"}
	currentAllocs := []peerID{"p2", "p3"}
	priorityList := []peerID{"p4"}

	curB, prioB, candB := filterMetricsBefore(metrics, blacklist, currentAllocs, priorityList)
	curA, prioA, candA := filterMetricsAfter(metrics, blacklist, currentAllocs, priorityList)

	if fmt.Sprint(curB) != fmt.Sprint(curA) {
		t.Fatalf("current mismatch: before=%v after=%v", curB, curA)
	}
	if fmt.Sprint(prioB) != fmt.Sprint(prioA) {
		t.Fatalf("priority mismatch: before=%v after=%v", prioB, prioA)
	}
	if fmt.Sprint(candB) != fmt.Sprint(candA) {
		t.Fatalf("candidate mismatch: before=%v after=%v", candB, candA)
	}

	// Verify expected classification
	if fmt.Sprint(curA) != "[p2 p3]" {
		t.Fatalf("expected cur=[p2 p3], got %v", curA)
	}
	if fmt.Sprint(prioA) != "[p4]" {
		t.Fatalf("expected prio=[p4], got %v", prioA)
	}
	if fmt.Sprint(candA) != "[p5 p6]" {
		t.Fatalf("expected cand=[p5 p6], got %v", candA)
	}
}

// --- Benchmarks ---

func makePeers(n int, prefix string) []peerID {
	peers := make([]peerID, n)
	for i := 0; i < n; i++ {
		peers[i] = peerID(fmt.Sprintf("%s-%d", prefix, i))
	}
	return peers
}

func BenchmarkBefore(b *testing.B) {
	// 500 metrics, 100 blacklisted, 100 current, 100 priority, 200 candidates
	metrics := makePeers(500, "m")
	blacklist := makePeers(100, "m")  // first 100 overlap
	current := makePeers(100, "cur")
	priority := makePeers(100, "pri")

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		filterMetricsBefore(metrics, blacklist, current, priority)
	}
}

func BenchmarkAfter(b *testing.B) {
	metrics := makePeers(500, "m")
	blacklist := makePeers(100, "m")
	current := makePeers(100, "cur")
	priority := makePeers(100, "pri")

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		filterMetricsAfter(metrics, blacklist, current, priority)
	}
}