russell@unturf.com
fac760d8f1
MOAD-0001 CWE-407 — 2 new defects:
- calibre-0003: depth_first() in src/calibre/ebooks/html/input.py calls flat.index(link)
inside a while loop over all ebook links. O(L * F) where L = links, F = flat list size.
Fix: pre-build flat_map = {hf: hf for hf in flat} before loop, O(1) lookup.
Measured: 38x at F=500 files (linear chain), 13.5x at F=200.
- calibre-0004: HTMLFile.find_links() uses list membership for dedup: `if link not in
self.links`. O(L^2) per HTML chapter file. Fix: parallel _links_seen set.
Measured: 124x at L=1000 unique links, 68x at L=500.
MOAD-0002/0003/0004/0005 — CLEAN. See TICKET.md for full analysis.
117 lines
3.5 KiB
Python
117 lines
3.5 KiB
Python
"""
|
|
Unit test for calibre-0004: HTMLFile.find_links list dedup O(L^2) -> set O(L)
|
|
|
|
Simulates the HTMLFile.find_links() method from src/calibre/ebooks/html/input.py.
|
|
The defective version does `if link not in self.links: self.links.append(link)`.
|
|
self.links is a plain list, so membership check is O(L) per candidate.
|
|
Our patched version uses a parallel set self._links_seen for O(1) membership.
|
|
"""
|
|
import time
|
|
import sys
|
|
|
|
PYTHONUNBUFFERED = True
|
|
|
|
|
|
class FakeLink:
|
|
"""Minimal Link substitute — equality and hash by path."""
|
|
def __init__(self, path):
|
|
self.path = path
|
|
|
|
def __eq__(self, other):
|
|
return self.path == getattr(other, 'path', other)
|
|
|
|
def __hash__(self):
|
|
return hash(self.path)
|
|
|
|
def __repr__(self):
|
|
return f'Link({self.path!r})'
|
|
|
|
|
|
# --- DEFECTIVE: list membership check O(L^2) ---
|
|
class HTMLFileDefective:
|
|
def __init__(self):
|
|
self.links = []
|
|
|
|
def find_links(self, candidate_paths):
|
|
for path in candidate_paths:
|
|
link = FakeLink(path)
|
|
if link not in self.links: # O(L) scan
|
|
self.links.append(link)
|
|
|
|
|
|
# --- PATCHED: set membership check O(L) total ---
|
|
class HTMLFilePatched:
|
|
def __init__(self):
|
|
self.links = []
|
|
self._links_seen = set()
|
|
|
|
def find_links(self, candidate_paths):
|
|
for path in candidate_paths:
|
|
link = FakeLink(path)
|
|
if link not in self._links_seen: # O(1)
|
|
self._links_seen.add(link)
|
|
self.links.append(link)
|
|
|
|
|
|
def make_paths(n_unique, n_total):
|
|
"""
|
|
Generate n_total paths with n_unique distinct values.
|
|
Simulates duplicate link patterns in an HTML chapter.
|
|
"""
|
|
unique = [f'/chapter/section_{i}.html' for i in range(n_unique)]
|
|
# repeat unique paths to fill n_total (many duplicate references are common)
|
|
paths = []
|
|
for i in range(n_total):
|
|
paths.append(unique[i % n_unique])
|
|
return paths
|
|
|
|
|
|
def run_and_time(cls, paths, reps):
|
|
t0 = time.perf_counter()
|
|
for _ in range(reps):
|
|
obj = cls()
|
|
obj.find_links(paths)
|
|
t1 = time.perf_counter()
|
|
return obj.links, (t1 - t0)
|
|
|
|
|
|
def test(n_unique, n_total, reps=20):
|
|
paths = make_paths(n_unique, n_total)
|
|
|
|
# correctness
|
|
def_obj = HTMLFileDefective()
|
|
def_obj.find_links(paths)
|
|
pat_obj = HTMLFilePatched()
|
|
pat_obj.find_links(paths)
|
|
def_paths = [l.path for l in def_obj.links]
|
|
pat_paths = [l.path for l in pat_obj.links]
|
|
assert def_paths == pat_paths, f'Dedup mismatch: {def_paths} vs {pat_paths}'
|
|
assert len(def_obj.links) == n_unique, f'Expected {n_unique} unique links, got {len(def_obj.links)}'
|
|
|
|
# warmup
|
|
for _ in range(3):
|
|
HTMLFileDefective().find_links(paths)
|
|
HTMLFilePatched().find_links(paths)
|
|
|
|
_, t_def = run_and_time(HTMLFileDefective, paths, reps)
|
|
_, t_pat = run_and_time(HTMLFilePatched, paths, reps)
|
|
ratio = t_def / t_pat if t_pat > 0 else float('inf')
|
|
print(f' n_unique={n_unique:4d} n_total={n_total:5d} defective={t_def*1000:.1f}ms patched={t_pat*1000:.1f}ms ratio={ratio:.1f}x')
|
|
return ratio
|
|
|
|
|
|
if __name__ == '__main__':
|
|
print('calibre-0004: HTMLFile.find_links list dedup O(L^2) -> set O(L)')
|
|
print('Simulating duplicate link dedup across HTML chapter files.')
|
|
print()
|
|
|
|
r100 = test(100, 1000)
|
|
r500 = test(500, 5000)
|
|
r1000 = test(1000, 5000)
|
|
|
|
ok = r500 > 3.0 or r1000 > 3.0
|
|
print()
|
|
print(f'Speedup at n_unique=500: {r500:.1f}x n_unique=1000: {r1000:.1f}x')
|
|
print('PASS' if ok else 'FAIL')
|
|
if not ok:
|
|
sys.exit(1)
|