`asyncio.print_call_graph()` output is exponential in the number of tasks

Bug report

Bug description:

The size of the asyncio.print_call_graph() output is proportional to the number of paths through the "awaited by" graph, not to the number of tasks:

import asyncio
import time

async def waits_for(*deps):
    await asyncio.gather(*deps)

async def main(levels):
    fut = asyncio.Future()
    layer = [fut]
    for _ in range(levels):
        layer = [asyncio.create_task(waits_for(*layer)) for _ in range(2)]
    await asyncio.sleep(0)

    t0 = time.perf_counter()
    graph = asyncio.format_call_graph(fut)
    dt = time.perf_counter() - t0
    print(f"{2 * levels:3d} tasks -> {graph.count('* Task'):9d} nodes,"
          f"{len(graph) / 1e6:9.1f} MB,{dt:8.2f} s")

for levels in (2, 4, 6, 8, 10, 12, 14, 16, 18, 20):
    asyncio.run(main(levels))

Actual output:

  4 tasks ->         6 nodes,      0.0 MB,    0.00 s
  8 tasks ->        30 nodes,      0.0 MB,    0.00 s
 12 tasks ->       126 nodes,      0.0 MB,    0.00 s
 16 tasks ->       510 nodes,      0.1 MB,    0.00 s
 20 tasks ->      2046 nodes,      0.6 MB,    0.00 s
 24 tasks ->      8190 nodes,      2.4 MB,    0.02 s
 28 tasks ->     32766 nodes,     10.7 MB,    0.07 s
 32 tasks ->    131070 nodes,     46.4 MB,    0.33 s
 36 tasks ->    524286 nodes,    200.3 MB,    1.96 s
 40 tasks ->   2097150 nodes,    859.8 MB,    9.90 s

Expected:

 4 tasks ->         6 nodes,      0.0 MB,    0.00 s
  8 tasks ->        14 nodes,      0.0 MB,    0.00 s
 12 tasks ->        22 nodes,      0.0 MB,    0.00 s
 16 tasks ->        30 nodes,      0.0 MB,    0.00 s
 20 tasks ->        38 nodes,      0.0 MB,    0.00 s
 24 tasks ->        46 nodes,      0.0 MB,    0.00 s
 28 tasks ->        54 nodes,      0.0 MB,    0.00 s
 32 tasks ->        62 nodes,      0.0 MB,    0.00 s
 36 tasks ->        70 nodes,      0.0 MB,    0.00 s
 40 tasks ->        78 nodes,      0.0 MB,    0.00 s

Besides that, the graph is impossible to read. The cause is that capture_call_graph() renders relations as a tree, but that relation is a DAG.

Proposed fix: expand each future's "awaited by" only once

Have a fix ready for that

CPython versions tested on:

CPython main branch

Operating systems tested on:

macOS

Linked PRs

• gh-156861

Start at the asyncio call-graph implementation, especially capture_call_graph(), and run the reproducer in the issue to observe the exponential output. Compare the actual and expected node counts, then verify that the graph remains bounded by the number of tasks and that the existing linked fix covers the DAG case.