120 lines
4.5 KiB
Java
120 lines
4.5 KiB
Java
package unit;
|
|
|
|
import java.util.*;
|
|
import java.util.stream.*;
|
|
|
|
/**
|
|
* Models jitsi-meet MessageContainer.componentDidUpdate() new-message detection.
|
|
*
|
|
* Defect: messages.filter(m => !prevMessages.includes(m)) — O(M²) on every update.
|
|
* then .map().includes() — O(M) second scan that .some() replaces in O(M).
|
|
* Fix: build Set from prevMessages once, use Set.contains() — O(M) total.
|
|
* use stream().anyMatch() instead of .map().contains().
|
|
*
|
|
* jitsi-meet-0002 MOAD-0001 CWE-407
|
|
* No JUnit — compile and run standalone.
|
|
*/
|
|
public class JitsiMeetMessageDedupTest {
|
|
|
|
static final String LOCAL = "local";
|
|
static final String REMOTE = "remote";
|
|
|
|
record Message(int id, String messageType) {}
|
|
|
|
// -------------------------------------------------------------------
|
|
// DEFECT: O(M²) — List.contains() inside filter per message
|
|
// -------------------------------------------------------------------
|
|
static long slowFindNew(List<Message> messages, List<Message> prevMessages) {
|
|
long ops = 0;
|
|
List<Message> newMessages = new ArrayList<>();
|
|
for (Message m : messages) {
|
|
ops += prevMessages.size(); // O(M) per entry
|
|
if (!prevMessages.contains(m)) newMessages.add(m);
|
|
}
|
|
// Secondary scan: .map().contains() — another O(N)
|
|
List<String> types = new ArrayList<>();
|
|
for (Message m : newMessages) types.add(m.messageType());
|
|
ops += types.size();
|
|
boolean hasLocal = types.contains(LOCAL);
|
|
return ops;
|
|
}
|
|
|
|
// -------------------------------------------------------------------
|
|
// FIX: O(M) — Set built once, anyMatch() replaces map+contains
|
|
// -------------------------------------------------------------------
|
|
static long fastFindNew(List<Message> messages, List<Message> prevMessages) {
|
|
long ops = 0;
|
|
Set<Message> prevSet = new HashSet<>(prevMessages);
|
|
List<Message> newMessages = new ArrayList<>();
|
|
for (Message m : messages) {
|
|
ops++; // O(1) Set.contains
|
|
if (!prevSet.contains(m)) newMessages.add(m);
|
|
}
|
|
ops++;
|
|
boolean hasLocal = newMessages.stream().anyMatch(m -> LOCAL.equals(m.messageType()));
|
|
return ops;
|
|
}
|
|
|
|
static List<Message> makeMessages(int n) {
|
|
List<Message> list = new ArrayList<>();
|
|
for (int i = 0; i < n; i++) {
|
|
list.add(new Message(i, i % 10 == 0 ? LOCAL : REMOTE));
|
|
}
|
|
return list;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
int tests = 0, passed = 0;
|
|
|
|
// --- correctness: single new message ---
|
|
tests++;
|
|
{
|
|
List<Message> prev = makeMessages(50);
|
|
List<Message> cur = new ArrayList<>(prev);
|
|
Message newMsg = new Message(999, LOCAL);
|
|
cur.add(newMsg);
|
|
|
|
long slowOps = slowFindNew(cur, prev);
|
|
long fastOps = fastFindNew(cur, prev);
|
|
boolean ok = slowOps > fastOps;
|
|
System.out.printf("%s correctness-one-new slowOps=%d fastOps=%d%n",
|
|
ok ? "PASS" : "FAIL", slowOps, fastOps);
|
|
if (ok) passed++;
|
|
}
|
|
|
|
// --- correctness: no new messages ---
|
|
tests++;
|
|
{
|
|
List<Message> messages = makeMessages(30);
|
|
long slowOps = slowFindNew(messages, messages);
|
|
long fastOps = fastFindNew(messages, messages);
|
|
// Both find zero new messages; slow must do more work
|
|
boolean ok = slowOps > fastOps;
|
|
System.out.printf("%s correctness-no-new slowOps=%d fastOps=%d%n",
|
|
ok ? "PASS" : "FAIL", slowOps, fastOps);
|
|
if (ok) passed++;
|
|
}
|
|
|
|
// --- speedup benchmarks ---
|
|
int[] benchSizes = {50, 100, 250, 500};
|
|
for (int M : benchSizes) {
|
|
tests++;
|
|
List<Message> prev = makeMessages(M);
|
|
List<Message> cur = new ArrayList<>(prev);
|
|
cur.add(new Message(M + 1, LOCAL));
|
|
|
|
long slowOps = slowFindNew(cur, prev);
|
|
long fastOps = fastFindNew(cur, prev);
|
|
double ratio = (double) slowOps / fastOps;
|
|
|
|
// At M=500: slow = 500*500 = 250,000; fast = 501 → ~499x
|
|
boolean ok = ratio >= 5.0;
|
|
System.out.printf("%s speedup M=%d slowOps=%d fastOps=%d ratio=%.1fx%n",
|
|
ok ? "PASS" : "FAIL", M, slowOps, fastOps, ratio);
|
|
if (ok) passed++;
|
|
}
|
|
|
|
System.out.println("\n" + passed + "/" + tests + " PASS");
|
|
if (passed != tests) System.exit(1);
|
|
}
|
|
}
|