107 lines
3.4 KiB
Python
107 lines
3.4 KiB
Python
"""
|
|
Unit test for trezor-0001: _distinguishable_cred_list O(N^2) list scan.
|
|
|
|
The original code scans the entire cred_list for each new credential using
|
|
a nested for loop with account_name() comparison, giving O(N^2).
|
|
The fix uses a dict keyed by account_name() for O(1) lookup, giving O(N).
|
|
"""
|
|
|
|
import time
|
|
|
|
|
|
class FakeFido2Credential:
|
|
"""Minimal mock of Fido2Credential for testing dedup logic."""
|
|
|
|
def __init__(self, name: str, creation_time: int = 0):
|
|
self._name = name
|
|
self._creation_time = creation_time
|
|
|
|
def account_name(self) -> str:
|
|
return self._name
|
|
|
|
def __lt__(self, other):
|
|
# Lower creation_time = newer (for test purposes)
|
|
return self._creation_time < other._creation_time
|
|
|
|
|
|
# --- ORIGINAL (defective) ---
|
|
def _distinguishable_cred_list_original(credentials):
|
|
cred_list = []
|
|
for cred in credentials:
|
|
for i, prev_cred in enumerate(cred_list):
|
|
if prev_cred.account_name() == cred.account_name():
|
|
if isinstance(cred, FakeFido2Credential) and cred < prev_cred:
|
|
cred_list[i] = cred
|
|
break
|
|
else:
|
|
cred_list.append(cred)
|
|
return cred_list
|
|
|
|
|
|
# --- PATCHED ---
|
|
def _distinguishable_cred_list_patched(credentials):
|
|
cred_list = []
|
|
seen = {}
|
|
for cred in credentials:
|
|
name = cred.account_name()
|
|
if name in seen:
|
|
i = seen[name]
|
|
prev_cred = cred_list[i]
|
|
if isinstance(cred, FakeFido2Credential) and cred < prev_cred:
|
|
cred_list[i] = cred
|
|
else:
|
|
cred_list.append(cred)
|
|
seen[name] = len(cred_list) - 1
|
|
return cred_list
|
|
|
|
|
|
def test_correctness():
|
|
"""Both versions must produce the same result."""
|
|
creds = [
|
|
FakeFido2Credential("alice", 10),
|
|
FakeFido2Credential("bob", 20),
|
|
FakeFido2Credential("alice", 5), # newer alice (lower time), should replace
|
|
FakeFido2Credential("carol", 30),
|
|
FakeFido2Credential("bob", 25), # older bob, should NOT replace
|
|
]
|
|
|
|
orig = _distinguishable_cred_list_original(list(creds))
|
|
patched = _distinguishable_cred_list_patched(list(creds))
|
|
|
|
orig_names = [(c.account_name(), c._creation_time) for c in orig]
|
|
patched_names = [(c.account_name(), c._creation_time) for c in patched]
|
|
|
|
assert orig_names == patched_names, f"Mismatch: {orig_names} != {patched_names}"
|
|
# alice should be the newer one (time=5), bob stays at 20, carol at 30
|
|
assert orig_names == [("alice", 5), ("bob", 20), ("carol", 30)]
|
|
print("PASS: correctness")
|
|
|
|
|
|
def test_performance():
|
|
"""Patched version should be significantly faster at scale."""
|
|
N = 2000
|
|
# All unique names to maximize the inner loop cost
|
|
creds = [FakeFido2Credential(f"user_{i}", i) for i in range(N)]
|
|
|
|
start = time.time()
|
|
for _ in range(3):
|
|
_distinguishable_cred_list_original(list(creds))
|
|
t_orig = time.time() - start
|
|
|
|
start = time.time()
|
|
for _ in range(3):
|
|
_distinguishable_cred_list_patched(list(creds))
|
|
t_patched = time.time() - start
|
|
|
|
ratio = t_orig / t_patched if t_patched > 0 else float("inf")
|
|
print(f" Original: {t_orig:.4f}s")
|
|
print(f" Patched: {t_patched:.4f}s")
|
|
print(f" Ratio: {ratio:.1f}x")
|
|
assert ratio > 2.0, f"Expected at least 2x speedup, got {ratio:.1f}x"
|
|
print("PASS: performance")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
test_correctness()
|
|
test_performance()
|
|
print("\nAll tests PASS")
|