Schedule Parallel-Safe Tool Calls into Waves

Problem Statement

When a model emits several tool calls in one turn, firing them all concurrently is the whole point - but only some of them are actually safe to run together. Two calls that read the same file are fine. A read racing a write on that file is not, and neither is a call that needs the output of another.

Write the scheduler that packs a batch of tool calls into the fewest safe waves.

Background

Each call declares the resource it touches (a file path, a table, an API namespace) and its mode, either "read" or "write". Two calls in the same wave conflict when they name the same resource and at least one of them is a write. Read/read never conflicts - that is the parallelism you are trying to harvest.

Calls may also declare depends_on, a list of call ids whose results they consume. A dependency must complete in a strictly earlier wave.

The scheduler is greedy and order-sensitive, which keeps it deterministic:

1. Walk the still-unscheduled calls in their original order.
2. Skip any call whose dependencies are not all already completed in an earlier wave - it waits.
3. Otherwise, add it to the current wave if it conflicts with nothing already placed in this wave; if it does conflict, it waits.
4. Close the wave, mark its calls complete, repeat with the calls that waited.

If a pass places no calls at all, the batch is unschedulable - a dependency cycle, or a dependency on an id that is not in the batch.

Your Task

Implement:

def plan_parallel_waves(calls):

• calls: list of dicts {"id": str, "tool": str, "resource": str, "mode": "read"|"write", "depends_on": list[str]}. depends_on may be absent, meaning no dependencies.

Return list[list[str]] - one inner list per wave, holding that wave's call ids sorted ascending. Return [] if the batch is unschedulable.

Input/Output Format

Returns a list of lists of strings. Note the greedy packing uses the original order, but each wave is reported sorted.

Sample

calls = [
    {"id": "c1", "tool": "read_file",  "resource": "cfg", "mode": "read"},
    {"id": "c2", "tool": "read_file",  "resource": "cfg", "mode": "read"},
    {"id": "c3", "tool": "write_file", "resource": "cfg", "mode": "write"},
]
print(plan_parallel_waves(calls))
# [['c1', 'c2'], ['c3']]

c1 and c2 both only read cfg, so they share a wave; c3 writes it and is pushed to the next.