java-topology/docs/tickets/pylons-0002-toposorter-sorted-names-list-scan.md

pylons-0002: TopologicalSorter.sorted() — O(N*E) if a in names list scan over edges

Severity: HIGH File: src/pyramid/util.py (Pyramid web framework, Pylons project) Line: 528 Status: PATCHED

Description

TopologicalSorter.sorted() builds a local names list (line 506-507):

names = [self.first, self.last]
names.extend(self.names)

Then iterates over all ordering edges with a list membership test on each side:

for a, b in order:                    # O(E) edges
    if a in names and b in names:     # O(N) list scan — CWE-407 x2
        add_arc(a, b)

With E edges and N nodes, this is O(N*E) = O(N²) when E ~ N (typical tween chain).

Root Cause

names is built as a list for no reason; it is never mutated or indexed after construction. Only membership tests are needed.

Fix

Replace names list with a names_set:

names_set = set()
names_set.add(self.first)
names_set.add(self.last)
names_set.update(self.names)

for a, b in order:
    if a in names_set and b in names_set:   # O(1) — fixed
        add_arc(a, b)

See patch: defects/pylons/patch/pylons-0002-toposorter-sorted-names-set.patch

Speedup

N=500 nodes, E=2000 edges (Pyramid app with many predicates):

• Slow: ~500 * 2000 * 2 = 2,000,000 element comparisons
• Fast: ~2000 * 2 = 4,000 hash lookups
• Speedup: ~500x; grows linearly with N