rustdoc sidebar duplicate-anchor de-duplication appears to be quadratic

I tried this with the Rust build-tree rustdoc binary, rustdoc 1.98.0-dev, 4008bbdf34b.

cat > rustdoc_sidebar_deref_repro.py <<'PY'
#!/usr/bin/env python3
import os
import shutil
import subprocess
import time
from pathlib import Path

N = int(os.environ.get("N", "1600"))
RUSTDOC = os.environ.get("RUSTDOC", "rustdoc")


def write_deref_chain(path: Path) -> None:
    with path.open("w", encoding="ascii") as f:
        f.write("pub struct S0;\n")
        for i in range(1, N + 1):
            f.write(f"pub struct S{i};\n")
        for i in range(1, N + 1):
            f.write(f"impl S{i} {{ pub fn foo(&self) {{}} }}\n")
        for i in range(N):
            j = i + 1
            f.write(
                f"impl std::ops::Deref for S{i} {{ "
                f"type Target = S{j}; "
                f"fn deref(&self) -> &S{j} {{ static V: S{j} = S{j}; &V }} "
                "}\n"
            )


src = Path(f"sidebar_deref_{N}.rs")
write_deref_chain(src)
out = Path(f"rustdoc_sidebar_{N}")
if out.exists():
    shutil.rmtree(out)

start = time.perf_counter()
subprocess.run([RUSTDOC, str(src), "--crate-name", "sidebarpoc", "-o", str(out)], check=True)
seconds = time.perf_counter() - start
print(f"deref_depth={N} elapsed={seconds:.3f}s source={src.stat().st_size}")
PY

RUSTDOC=/path/to/rustdoc N=1600 python3 rustdoc_sidebar_deref_repro.py

It creates legal Rust code with a deep Deref chain:

pub struct S0;
pub struct S1;
pub struct S2;
// ...

impl S1 { pub fn foo(&self) {} }
impl S2 { pub fn foo(&self) {} }
impl S3 { pub fn foo(&self) {} }
// ...

impl std::ops::Deref for S0 { type Target = S1; /* ... */ }
impl std::ops::Deref for S1 { type Target = S2; /* ... */ }
impl std::ops::Deref for S2 { type Target = S3; /* ... */ }
// ...

When rustdoc renders the page for S0, it recursively collects methods from the
Deref targets for the sidebar. Every target contributes a method named foo, so
the sidebar needs many links with the same base anchor method.foo.

With N=1600, I see rustdoc spend about 49 seconds generating the docs:

deref_depth=1600 elapsed=49.054s source=261063

Here are the timings I collected with the same rustdoc binary:

deref_depth  source_bytes  exit_status  elapsed_ms
100          15357         0            357
200          31457         0            524
400          63657         0            1396
800          128057        0            7333
1600         261063        0            49054

The total number of hash
lookups and temporary string constructions is approximately 1 + 2 + ... + N.

Run rustdoc_sidebar_deref_repro.py with the listed N values to reproduce the scaling, then trace rustdoc's sidebar method-anchor de-duplication while rendering the generated S0 page. Confirm the fix with the same deep Deref-chain inputs and verify that runtime no longer grows quadratically as duplicate foo anchors increase.