Documenting Complexity Modules

Documenting Complexity Modules

Produce a complete, evidence-backed page rather than filling a prose template. Treat English documentation as the source of truth and complexity claims as the repository's highest-risk content.

Establish Scope and Evidence

1. Read AGENTS.md, CONTRIBUTING.md, and the reference pair:

   • docs/stdlib/csv.md
   • tests/test_csv_complexity.py

   That pair is the style anchor for every page and test file in this repository. The most recently modified pages are not a substitute: a page modelled on its neighbours inherits their departures from the reference and adds its own. Read the reference pair in full before writing, and compare the finished page against it, not against its neighbours.

2. Identify every public class, function, constant, and public method the page should cover. Use official Python documentation plus runtime inspection such as dir(module) and dir(class). Filter private names, then distinguish callables from data attributes. Record intentional omissions in the page or test rationale; do not silently omit APIs. Reconcile the result with the shared audit gate - see Coverage Is a Claim below.

3. Define every size variable before using it. Avoid an ambiguous n when an operation depends on several dimensions; use terms such as input length, output length, fields, vertices, edges, matches, or returned items.

4. Verify implementation-specific claims against the corresponding released CPython branch, never main. Read every Python version the project supports - a bound can move in a middle release - but run the pinned interpreter unless a claim is about a particular version, in which case run that one for the tests asserting it; CI covers the matrix. Use official documentation where behavior is contractual and source where implementation determines the bound.

Do not trust an existing claim, a plausible review comment, or a generic complexity rule without checking the operation's actual code path.

Write the Page

Use docs/stdlib/csv.md as the structural reference. The rules below describe its shape; where a rule allows a choice, choose what the csv page did:

1. Title: # <name> Module Complexity or the established builtin equivalent.

2. Give a short performance-focused introduction: what the module does, what its unit of work is, and what it does or does not hold in memory. Two paragraphs at most.

3. Define every size variable in prose right after the introduction, before the table, in one place: "n is rows, k is the characters in one row". State any cost-model assumption there too, such as treating key hashing as O(1). A variable used by a single subsection's table may instead be defined in that table's Notes, as s = sample length is in the Sniffer rows.

4. Put ## Complexity Reference next and include a table with exactly these semantic columns:

   | Operation | Time | Space | Notes |
   |-----------|------|-------|-------|
   

   Split the reference into ### subsections, one per class or natural group (### reader, ### DictReader, ### Dialects and field limits, ### Constants and exceptions), each with its own table. Head a subsection with the class name where there is one. Write the Operation cell as the qualified call with its signature (csv.DictReader(f, fieldnames=None, ...), DictWriter.writerow(rowdict)), the qualified name for an attribute or constant (DictReader.fieldnames, csv.QUOTE_ALL), and a short label for a protocol such as iteration ("Iterating a DictReader"), so the audit can match the name. Price every row, including constants and exception classes: reading a constant is O(1) attribute access, so say O(1) rather than leaving a dash, and a class whose construction does work gets that cost instead.

5. Follow the reference with topic sections whose headings name the subject in Title Case (## Reading CSV Files, ### Lazy vs Eager Reading, ## Sniffing an Unknown Format), not a sentence stating the claim. Each opens with one or two sentences saying what the cost is and why, then a runnable example; where the sentences would only restate the table, go straight to the example. Nest ### under a ## topic where a topic has several facets.

6. Close with, in this order: ## Common Patterns where a realistic read-transform-write or aggregation example helps; ## Performance Best Practices as a ✅ Do list and a ❌ Avoid list, each item tied to a cost on this page; ## Version Notes as a bulleted list of **Python 3.x+**: ... entries for changes on supported versions and **All Python 3**: ... for a caveat that holds on every one; and ## Related Modules as **[name](name.md)** - why a reader would go there. Omit a closing section only when the module has nothing to put in it.

7. Cover all scoped operations at the altitude set by Document the Common Case below: one bound per operation, with its size variables defined. Distinguish best, average, amortized and worst only where they differ asymptotically and ordinary use can reach the difference; state eager versus lazy work, cache effects, output-sensitive terms, and version boundaries where they change the result on a version this project supports.

8. Add topic sections only where a non-obvious cost changes a practical choice. Exclude generic usage advice unrelated to complexity, and prefer no section to one that restates the table in sentences.

9. Include runnable examples that demonstrate the documented operation or a performance consequence. Write them the way the csv page does: import at the top, self-contained inputs (in memory, such as io.StringIO or a literal, where the API allows; a temporary resource the block creates and removes where it does not), a trailing # O(...) comment on the operations whose cost the example demonstrates (repeated calls and incidental setup need not each carry one), and assert statements that pin the result so the block proves something when the test suite runs it. Where the result is an exception, catch it, assert on its message, and add an else that raises, so a block that stops raising fails. No print() output to read by eye. Avoid huge allocations or slow benchmark-style examples in docs.

10. Link related operations when the comparison helps readers choose between different costs.

Every table row, annotation, caption, example comment, explanatory sentence, warning, and recommendation that describes cost or behavior is a claim. Make a claim inventory while writing; do not review only text containing O(...).

Document the Common Case

The page exists so a reader can choose between operations. Its subject is the Big-O characteristic that governs that choice, not a full account of the CPython code path that produced it. A row that is correct but exhaustive costs more than it returns: it reads worse, it goes stale sooner, and every added clause is one more claim to test.

Keep these off the page:

• Measured constant factors. "roughly 1,400x dearer", "some 50x", "wins by eight times". A ratio is a property of one machine, one input shape and one release. The page cannot re-run it, the reader cannot act on it, and nothing fails when it drifts. Where a magnitude really does drive a choice, say which side wins and why, not by how much; the number stays in the test that guards it.
• Pathological-input costs. An argument whose __hash__ scans 100,000 elements does make hashing dominate a cache hit, but pricing that into the cache's row teaches nothing about the cache. Document the cost the operation itself controls; where caller-supplied cost dominates, name it once as a variable (h, f, the callback) and move on.
• Per-release micro-changes. A version boundary earns a mention when it changes the bound or the recommendation on a supported version. Shifts in constant factors between minor releases do not, and neither does an implementation detail stated so precisely that the next release falsifies it.
• Restated mechanism. The C function reached, the struct field consulted, the order of two statements: that is evidence for the test file, not content for the page, unless the reader must do something differently because of it.

Apply one test to every note: would removing it change how someone uses the operation? If not, cut it. An empty Notes cell beside a correct bound is a good outcome, not an unfinished one.

A deliberately loose bound fails that test even when it is honest about being loose. Bounding a recursive tree walk by the whole tree's metadata is true, and tells the reader that shape does not matter - when two trees of equal entry count differ eightfold by shape. Give the tight bound and its size variables; "conservative" is a bound no release can ever falsify, which is the same as one no reader can use.

Coverage Is a Claim

Use the shared public API audit as the completeness gate for the page being written or reviewed. Run it before the claim review and again on the final page:

uv run python scripts/audit_documentation.py --page docs/stdlib/os.md --check --include-review

Replace the path with the actual English page. Scope by page, including submodule APIs assigned to it (such as os.path in os.md), rather than filtering output by a module-name prefix. The audit uses the current interpreter's versioned Python API inventory and deduplicates aliases across the full audit. Use that shared inventory instead of writing another dir(module) completeness test. Runtime inspection and official documentation still supplement inventory gaps.

Resolve every reported miss with substantive documentation or correct an audit classification/matching defect with a regression test. Group related APIs when they share a bound. Do not add token mentions to obtain a pass, silently suppress names, or treat an inspection failure or empty inventory as zero misses.

The gate checks name coverage, not complexity correctness. Review the scoped unresolved/unavailable and unclassified diagnostics too; record explicit names and reasons for intentional exclusions or platform/version limitations in the module test rationale. A successful exit does not discharge those diagnostics. Inspect the official inventory for relevant supported-version APIs absent from the running interpreter; run another version only when resolving a claim about that version. One platform's successful audit does not establish all-platform coverage.

A Foreign Platform's Gap Is Not This Platform's Blocker

Some modules cannot be imported where the work is happening: winreg, msvcrt and asyncio.windows_events on Linux, and their equivalents elsewhere. The audit reports each as an inspection error, and its exit status counts every inspection error as a failure. That conflates two different things, and only one of them is yours to fix.

Sort each inspection error into one of three classes:

• Imports here. The ordinary case, including your own platform's APIs. A miss or a failing test is a blocker.
• Belongs to another platform. winreg on Linux. Nothing you write makes it inspectable, and no build of this interpreter would, so it is not a coverage defect. Name it and its reason in the module test rationale, and move on.
• Belongs to this platform but is missing from this build. dbm.gnu without _gdbm. You cannot inspect it here either, so it does not block finishing - but it is not discharged, because an interpreter built with it would surface real misses. Record it as unresolved, under that name, and do not report the module's coverage as established.

So a --check run reporting zero missing names whose only inspection errors are foreign-platform modules has met the coverage bar, whatever its exit status says. Report it that way - "0 missing; the gate cannot exit clean on Linux because these two modules are Windows-only" - rather than presenting a red gate as an open coverage gap, or implying a green one the tool cannot produce. Never quote the exit status alone as evidence in either direction: read the missing-name count and the error list. Where a missing-build module is among the errors, say that the count is provisional on that build.

What this does not license: a reachable module that fails to import is a real failure, and an inspection error is never a reason to skip reading the official inventory for that module's APIs. A page still documents the APIs its module exposes on platforms you are not running, sourced from the official docs, with the platform named in the row.

A full review is complete only when the scoped gate reports no missing names, every remaining coverage diagnostic is accounted for - fixed if it imports here, discharged if it belongs to another platform, carried as an explicit unresolved item if this build simply lacks it - and every documented claim has evidence. Report API completeness and claim correctness separately. If the work is an explicitly scoped correction, report remaining API gaps rather than describing the whole page as reviewed. Newly documented APIs need the same claim inventory, behavioral tests, and example verification as the existing rows.

Test Every Claim

Use the testing-complexity-claims skill if available. Otherwise apply its core contract directly:

• A module-specific tests/test_<module>_complexity.py covers the page's table.
• Explanatory claims beyond the table receive focused tests, preferably based on observable behavior rather than elapsed time.
• Claims that execution cannot settle are listed with the reason in a relevant test module's docstring; do not add a fake or permanently skipped test.
• Test or explicitly account for every fenced code block using the code-section rules below.
• Maintain a one-to-one claim inventory showing a test or an explicit untestable rationale for each claim.

Do not write documentation first and defer its evidence to later work.

Test Every Code Section

Account for every fenced code block in the English page, not just blocks that contain complexity annotations. Test each block when safely and meaningfully possible; for a block that cannot be executed, record the block's location and the concrete reason, such as required network access, interactive input, deliberately incomplete names, destructive behavior, or an intentional exception without an established marker. Translations do not need duplicate execution because their code fences must be byte-for-byte identical to English.

Follow the isolation lessons from repository issue #7 when building or extending a documentation-code runner:

• dedent each extracted block so fences nested in admonitions compile correctly;
• run each block independently in a subprocess with a hard timeout, a fresh namespace, closed stdin, and a temporary working directory;
• do not rely on text matching for unsafe or interactive calls: breakpoint(), help(), pdb.set_trace(), sys.stdin.read(), and getpass.getpass() are pitfalls alongside obvious input() calls;
• isolate or explicitly exclude process, thread, network, browser, system, signal, destructive filesystem, and indefinitely blocking examples;
• support intentional exceptions through an explicit convention rather than treating all raised exceptions as broken examples;
• report every failure with its Markdown file and fence line number, and restore captured output before emitting diagnostics;
• assert the expected block count or accounted-for locations so extraction cannot silently test nothing;
• mutation-test the runner with a known broken example and first assert that the mutation actually changed its target.

Execution proves only that a block does not crash; it does not prove that the block demonstrates what its prose, comments, or output claims. Add semantic assertions for results, exceptions, state changes, operation counts, and complexity behavior wherever those claims can be tested. Retain claim-specific unit tests even when a generic code-block runner also executes the example.

Integrate the Page

1. Add the English page to the appropriate alphabetized navigation section in mkdocs.yml.

2. Run make audit to print live coverage without writing files. Coverage tests compare the current interpreter with the English documentation tree; CI also checks the pinned newest supported Python patch. Preserve navigation targets for historical modules even when the current interpreter no longer has them.

3. Look for existing translations at the equivalent docs/<locale>/... path. If they exist, faithfully mirror the English change and run:

   uv run python scripts/validate_translations.py --update-hashes <locale>
   

   Never hand-edit source_sha. Keep fenced code byte-for-byte identical to English, and preserve heading levels, table shape, links, and complexity notation. Missing translations may continue to fall back to English.

Verify

Run the narrowest useful checks while iterating, then finish with:

make check

Also inspect the final diff for:

• a scoped public API audit reporting no missing names, with every remaining coverage diagnostic accounted for and any unreachable-platform module named as such rather than left looking like a gap;
• defined size variables and bounds qualified only where the qualification changes a decision;
• notes that survive the removal test, carrying no measured constants, pathological-input pricing, or restated mechanism;
• the same section order, heading style, table layout and example shape as docs/stdlib/csv.md, checked against that page rather than against the pages edited most recently;
• every claim mapped to evidence;
• every fenced code section tested or explicitly accounted for, with semantic assertions where execution alone is insufficient;
• alphabetized navigation and passing live coverage checks;
• translations updated where an equivalent page exists;
• no unrelated formatting or content changes.

If a claim remains unverified, describe the missing evidence and do not present the page as complete.