java-topology/defects/simplex-chat/patch/simplex-chat-0004-introduce-to-remaining-notelem.md

UNDF: UNDF-2026-000000831

Defect: simplex-chat-0004 — introduceToRemaining notElem O(N×M) member dedup

Project: simplex-chat
File: src/Simplex/Chat/Library/Internal.hs
Function: introduceToRemaining / introduceMemP
Complexity: O(|members| × |introducedGMIds|) per member join event
Severity: MEDIUM
Fix: Convert introducedGMIds :: [GroupMemberId] to Set GroupMemberId before filter

Pattern

-- DEFECT: O(|members| × |introducedGMIds|)
introduceToRemaining vr user gInfo m = do
  (members, introducedGMIds) <-
    withStore' $ \db -> (,) <$> getGroupMembers db vr user gInfo
                            <*> getIntroducedGroupMemberIds db m
  let recipients = filter (introduceMemP introducedGMIds) members
  ...
  where
    introduceMemP introducedGMIds mem =
      memberCurrent mem
        && groupMemberId' mem `notElem` introducedGMIds   -- O(|introducedGMIds|) scan
        && groupMemberId' mem /= groupMemberId' m

Fix

-- FIX: O(|members| × log|introducedGMIds|)
import qualified Data.Set as S

introduceToRemaining vr user gInfo m = do
  (members, introducedGMIds) <-
    withStore' $ \db -> (,) <$> getGroupMembers db vr user gInfo
                            <*> getIntroducedGroupMemberIds db m
  let introducedSet = S.fromList introducedGMIds
      recipients = filter (introduceMemP introducedSet) members
  ...
  where
    introduceMemP introducedSet mem =
      memberCurrent mem
        && groupMemberId' mem `S.notMember` introducedSet   -- O(log N)
        && groupMemberId' mem /= groupMemberId' m

Impact

In a group with N members where M introductions have been made:

• Per new member join: O(N×M) → O(N log M)
• At N=1000 members, M=500 introductions: 500,000 → 9,000 comparisons (55× overhead)