git:20260911.48774e9 to git:20260911.05fa0fb

---

name: documenting-complexity-modules

description: Authors, expands, or reviews Python builtin and standard-library complexity pages, including API coverage, navigation, examples, translations, audit metadata, and verification. Use when adding a module/type page, materially expanding one, or reviewing an existing one for correctness - a review covers what the page omits as well as what it claims.

---

# 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 representative nearby pages and

tests. Prefer recent page/test pairs such as:

- `docs/stdlib/graphlib.md` and `tests/test_graphlib_complexity.py`

- `docs/stdlib/struct.md` and `tests/test_struct_complexity.py`

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. Then pin the result with a

coverage test - 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

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

Follow the local style of adjacent pages:

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

2. Give a short performance-focused introduction.

3. Put `## Complexity Reference` first and include a table with exactly these

semantic columns:

```markdown

| Operation | Time | Space | Notes |

|-----------|------|-------|-------|

```

4. 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.

5. Add concise 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.

6. Include runnable examples that demonstrate the documented operation or a

performance consequence. Annotate relevant operations with their complexity.

Avoid huge allocations or slow benchmark-style examples in docs.

7. 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

The set of APIs a page documents is a claim about the module, and it is the one

claim a reader of the page cannot check. A table covering a fifth of its module

reads exactly like one covering all of it, and the toolchain agrees: lint,

types and the whole suite pass either way.

So test it. Enumerate the module's public names before writing, and pin the

result when the page is done:

```python

def test_no_public_name_is_missing_from_the_table(self) -> None:

public = {name for name in dir(module) if not name.startswith("_")}

missing = sorted(public - _documented_names())

assert not missing, f"{len(missing)} public names absent: {missing}"

```

`_documented_names()` parses the page's own Complexity Reference table, so it

has to match how that table writes names. Assert both directions - a name the

table invents is as wrong as one it omits - and allow, explicitly and by name,

only those documented APIs that a supported version lacks, checking that each

such row carries its version marker.

Confirm the extractor is not vacuous before trusting it. One that matches

nothing reports perfect coverage: drop a known row from the set it returns and

assert that the check would have failed.

Re-run that check whenever the allowlist widens. Platform- and version-gated

names need an exemption, but exempt them **by name**: excluding a pattern such

as `CLOCK_*` also exempts `CLOCK_NONSENSE`, and the "the table names nothing

that does not exist" half of the coverage test quietly stops working. An

explicit list keeps the typo check alive and says which absences were reviewed.

Two things make this affordable on a wide module:

- **Group families into one row.** `module.sin/cos/tan(x)` names three

functions in one line, and a slash-separated run parses back to three names.

Twenty-odd rows can cover sixty-odd names without a wall of table.

- **Cover first, then look for content.** Most of a wide module is one bound

repeated. Give those a row and move on; the reading is only worth doing where

the row would otherwise be a guess.

Expect the coverage pass to produce claims, not just rows. The APIs a page

skipped are where its remaining defects sit, and the rows added arrive with

none of the scrutiny the existing ones have had - inventory them the same way.

## 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:

```bash

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:

```bash

make check

```

Also inspect the final diff for:

- complete public API coverage or explained omissions, pinned by a coverage

test rather than by having looked once;

- 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;

- 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.