`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

Commencez par l’implémentation du graphe d’appels de asyncio, en particulier capture_call_graph(), et exécutez le reproducteur de l’issue pour observer la sortie exponentielle. Comparez le nombre réel de nœuds au nombre attendu, puis vérifiez que le graphe reste borné par le nombre de tâches et que le correctif déjà lié couvre le cas DAG.