source-root parent map appears to scan previous roots quadratically

I tried this with the rust-analyzer binary built from the Rust checkout:

rust-analyzer 0.0.0 (4008bbdf34b 2026-06-20)

cat > source_root_parent_map_repro.py <<'PY'
#!/usr/bin/env python3
import json
import os
import pathlib
import select
import shutil
import subprocess
import sys
import time

N = int(os.environ.get("N", "2400"))
RA = os.environ.get("RA", "rust-analyzer")
ROOT = pathlib.Path(f"ra_many_roots_{N}").resolve()


def write_workspace(root: pathlib.Path, n: int) -> None:
    if root.exists():
        shutil.rmtree(root)
    root.mkdir(parents=True)
    crates = []
    for i in range(1, n + 1):
        name = f"c{i:05d}"
        crate_dir = root / name
        crate_dir.mkdir()
        (crate_dir / "lib.rs").write_text(f"pub fn f{i}() {{}}\n", encoding="ascii")
        crates.append({
            "display_name": name,
            "root_module": f"{name}/lib.rs",
            "edition": "2021",
            "deps": [],
            "is_workspace_member": True,
        })
    (root / "rust-project.json").write_text(
        json.dumps({"crates": crates}, separators=(",", ":")), encoding="ascii"
    )


def send(proc: subprocess.Popen, msg: dict) -> None:
    data = json.dumps(msg, separators=(",", ":")).encode()
    proc.stdin.write(b"Content-Length: " + str(len(data)).encode() + b"\r\n\r\n" + data)
    proc.stdin.flush()


def read_one(proc: subprocess.Popen, timeout: float):
    fd = proc.stdout.fileno()
    end = time.time() + timeout
    header = b""
    while b"\r\n\r\n" not in header:
        remaining = end - time.time()
        if remaining <= 0:
            return None
        ready, _, _ = select.select([fd], [], [], remaining)
        if not ready:
            return None
        chunk = os.read(fd, 1)
        if not chunk:
            return None
        header += chunk
    length = 0
    for line in header.decode(errors="replace").split("\r\n"):
        if line.lower().startswith("content-length:"):
            length = int(line.split(":", 1)[1].strip())
    body = b""
    while len(body) < length:
        remaining = end - time.time()
        if remaining <= 0:
            return None
        ready, _, _ = select.select([fd], [], [], remaining)
        if not ready:
            return None
        body += os.read(fd, length - len(body))
    return json.loads(body)


def run(root: pathlib.Path, n: int):
    proc = subprocess.Popen([RA], stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.DEVNULL)
    next_id = 1
    start = time.time()
    root_uri = root.as_uri()
    send(proc, {
        "jsonrpc": "2.0",
        "id": next_id,
        "method": "initialize",
        "params": {
            "processId": None,
            "rootUri": root_uri,
            "capabilities": {"workspace": {"configuration": True, "workspaceFolders": True}},
            "workspaceFolders": [{"uri": root_uri, "name": f"ws{n}"}],
        },
    })
    init_id = next_id
    next_id += 1
    initialized = False
    status_id = None
    last_poll = 0.0
    loaded = False
    while time.time() - start < 180:
        msg = read_one(proc, 0.05)
        now = time.time()
        if msg is not None:
            if "id" in msg and "method" not in msg:
                if msg["id"] == init_id and not initialized:
                    send(proc, {"jsonrpc": "2.0", "method": "initialized", "params": {}})
                    initialized = True
                if status_id is not None and msg["id"] == status_id:
                    result = msg.get("result", "") or ""
                    if f"Loaded {n} packages" in result or f"Loaded {n} package" in result:
                        loaded = True
                        break
                    status_id = None
            elif "id" in msg and msg.get("method"):
                if msg["method"] == "workspace/configuration":
                    items = msg.get("params", {}).get("items", [])
                    send(proc, {"jsonrpc": "2.0", "id": msg["id"], "result": [{} for _ in items]})
                else:
                    send(proc, {"jsonrpc": "2.0", "id": msg["id"], "result": None})
        if initialized and status_id is None and now - last_poll > 0.1:
            status_id = next_id
            next_id += 1
            last_poll = now
            send(proc, {
                "jsonrpc": "2.0",
                "id": status_id,
                "method": "rust-analyzer/analyzerStatus",
                "params": {"textDocument": None},
            })
    elapsed_ms = int((time.time() - start) * 1000)
    try:
        send(proc, {"jsonrpc": "2.0", "id": next_id, "method": "shutdown", "params": None})
        read_one(proc, 1)
        send(proc, {"jsonrpc": "2.0", "method": "exit", "params": None})
    except Exception:
        pass
    proc.kill()
    return loaded, elapsed_ms


write_workspace(ROOT, N)
loaded, elapsed_ms = run(ROOT, N)
print(f"roots={N} loaded={int(loaded)} elapsed_ms={elapsed_ms}")
PY

RA=/path/to/rust-analyzer N=2400 python3 source_root_parent_map_repro.py

It creates a rust-project.json workspace with N independent member crates,
each in a separate sibling directory:

ra_many_roots_2400/
  rust-project.json
  c00001/lib.rs
  c00002/lib.rs
  c00003/lib.rs
  ...

Each crate is a workspace member and has no dependencies. The important part is
that the roots are local sibling roots, so none of them is the parent of another.
The script initializes rust-analyzer as an LSP server and polls
rust-analyzer/analyzerStatus until it reports that all packages are loaded.

With N=2400, I see rust-analyzer take about 24.6 seconds before becoming ready:

roots=2400 loaded=1 elapsed_ms=24575

Here are the timings I collected with the same rust-analyzer binary:

roots  loaded  elapsed_ms
200    1       120
400    1       224
800    1       1186
1600   1       7581
2400   1       24575

The readiness time grows superlinearly as the number of local source roots
increases.

Start by running source_root_parent_map_repro.py with the reported N values and observe rust-analyzer initialization through the analyzerStatus request. Trace the source-root parent map work involved while loading the generated rust-project.json workspace. Done means the same independent sibling-root workload no longer shows superlinear readiness times.