Repository: python/cpython

Issue:
graphlib.TopologicalSorter.prepare() should be idempotent
# Feature or enhancement

### Proposal:

## Proposed Behaviour

[`TopologicalSorter.prepare()`](https://docs.python.org/3/library/graphlib.html#graphlib.TopologicalSorter.prepare) should be idempotent such that calling it repeatedly without draining anything is not an error:

```python
>>> import graphlib
>>> ts = graphlib.TopologicalSorter()
>>> ts.prepare()
>>> ts.prepare()
```

If you have called `.get_ready()`/`.done()` then calling `prepare()` is probably a programming error and this would raise:

```python
>>> import graphlib
>>> ts = graphlib.TopologicalSorter()
>>> ts.prepare()
>>> ts.get_ready()
()
>>> ts.prepare()
Traceback (most recent call last):
  ...
ValueError: cannot prepare() after mutating prepared sorter
```

## Rationale

`TopologicalSorter.prepare()` raises an exception if you call it twice:

```python
>>> import graphlib
>>> ts = graphlib.TopologicalSorter()
>>> ts.prepare()
>>> ts.prepare()
Traceback (most recent call last):
  File "<python-input-3>", line 1, in <module>
    ts.prepare()
    ~~~~~~~~~~^^
  File "/home/mauve/.local/share/ext-python/python-3.13.0.82/lib/python3.13/graphlib.py", line 95, in prepare
    raise ValueError("cannot prepare() more than once")
ValueError: cannot prepare() more than once
```

This is rather unfortunate because if you return a `TopologicalSorter` that is prepared:

```python
def get_sorter(targets) -> TopologicalSorter[str]:
    """Get a TopologicalSorter that pursues the given targets."""
    deps = filter_deps(load_deps(), targets)
    ts = TopologicalSorter(deps)
    ts.prepare()
    return ts
```

because then you cannot run `.static_order()` on it:

```python
>>> get_sorter().static_order()
Traceback (most recent call last):
  ...
ValueError: cannot prepare() more than once
```

while if you don't `prepare()`, you then require the caller to do it, meaning the function that populates and returns a `TopologicalSorter` didn't leave it in a prepared state. It seems appropriate for such a function to call `prepare()` in order to leave the TopologicalSorter ready to iterate and also closed for the addition of new nodes/predecessors.

Therefore I think `prepare()` should be idempotent.

### Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

### Links to previous discussion of this feature:

This is related to #91301 which discusses removing `TopologicalSorter.prepare()` entirely. Doing so would bypass this issue.

<!-- gh-linked-prs -->
### Linked PRs
* gh-131317
<!-- /gh-linked-prs -->

Discussion:
@vstinner: cc @pablogsal @pablogsal: @tim-one what do you think Tim?@tim-one: I like the simple rule `.prepare()` can be called at most once. I'd change the OP's `get_sorter()` to take an optional `prepare=True` argument, and leave it on the user to call that with `False` if they intend to call `.static_order()` (or in any other way want to alter the graph initially constructed).

That said, I think it would be easy to implement (if not to document) what the OP appears to want: `.prepare()`, when `self._ready_nodes` is not `None`, could just return if `self._npassedout == 0`.

Altermative: leave `.prepare()` alone and change `static_order()` instead, to start with:

```python
if self._ready_nodes is None:
    self.prepare()
elif self._npassedout:
    raise ValueError("static_order() cannot be called after work has started")  
```
@tim-one: On second thought, `.prepare()` is being more dogmatic than necessary. Calling it again is harmless so long as `._npassedout` is 0 (and in that case - `._ready_nodes is not None` but `.npassedout == 0` - it should just return at once).  BTW, we cannot execute the _body_ of `.prepare()` again in that case - we must just return. Else `._ready_nodes` would become empty again, despite that the user never saw what was in it.@lordmauve: One consequence of reusing `_npassedout` is that empty TopologicalSorters would let you call prepare after static_order():

```python
>>> from graphlib import TopologicalSorter
>>> t = TopologicalSorter()
>>> list(t.static_order())
[]
>>> t.prepare()
>>> t.prepare()
```

While a non-empty one doesn't allow that:

```python
>>> from graphlib import TopologicalSorter
>>> t = TopologicalSorter({'a': 'bc'})
>>> t.add(*'abc')
>>> list(t.static_order())
['b', 'c', 'a']
>>> t.prepare()
Traceback (most recent call last):
  ...
ValueError: cannot prepare() after starting sort
```

Solution patch:
diff --git a/Doc/library/graphlib.rst b/Doc/library/graphlib.rst
index a0b16576fad..49424700303 100644
--- a/Doc/library/graphlib.rst
+++ b/Doc/library/graphlib.rst
@@ -106,6 +106,14 @@
       function, the graph cannot be modified, and therefore no more nodes can be
       added using :meth:`~TopologicalSorter.add`.
 
+      A :exc:`ValueError` will be raised if the sort has been started by
+      :meth:`~.static_order` or :meth:`~.get_ready`.
+
+      .. versionchanged:: next
+
+         ``prepare()`` can now be called more than once as long as the sort has
+         not started. Previously this raised :exc:`ValueError`.
+
    .. method:: is_active()
 
       Returns ``True`` if more progress can be made and ``False`` otherwise.
diff --git a/Doc/whatsnew/3.14.rst b/Doc/whatsnew/3.14.rst
index 9a25f27ca57..79b219dd726 100644
--- a/Doc/whatsnew/3.14.rst
+++ b/Doc/whatsnew/3.14.rst
@@ -607,6 +607,15 @@ getopt
 * Add support for returning intermixed options and non-option arguments in order.
   (Contributed by Serhiy Storchaka in :gh:`126390`.)
 
+
+graphlib
+--------
+
+* Allow :meth:`graphlib.TopologicalSorter.prepare` to be called more than once
+  as long as sorting has not started.
+  (Contributed by Daniel Pope in :gh:`130914`)
+
+
 http
 ----
 
diff --git a/Lib/graphlib.py b/Lib/graphlib.py
index 82f33fb5cf3..7961c9c5cac 100644
--- a/Lib/graphlib.py
+++ b/Lib/graphlib.py
@@ -90,13 +90,17 @@ def prepare(self):
         still be used to obtain as many nodes as possible until cycles block more
         progress. After a call to this function, the graph cannot be modified and
         therefore no more nodes can be added using "add".
+
+        Raise ValueError if nodes have already been passed out of the sorter.
+
         """
-        if self._ready_nodes is not None:
-            raise ValueError("cannot prepare() more than once")
+        if self._npassedout > 0:
+            raise ValueError("cannot prepare() after starting sort")
 
-        self._ready_nodes = [
-            i.node for i in self._node2info.values() if i.npredecessors == 0
-        ]
+        if self._ready_nodes is None:
+            self._ready_nodes = [
+                i.node for i in self._node2info.values() if i.npredecessors == 0
+            ]
         # ready_nodes is set before we look for cycles on purpose:
         # if the user wants to catch the CycleError, that's fine,
         # they can continue using the instance to grab as many
diff --git a/Misc/NEWS.d/next/Library/2025-03-16-08-00-29.gh-issue-130914.6z883_.rst b/Misc/NEWS.d/next/Library/2025-03-16-08-00-29.gh-issue-130914.6z883_.rst
new file mode 100644
index 00000000000..956cf83758f
--- /dev/null
+++ b/Misc/NEWS.d/next/Library/2025-03-16-08-00-29.gh-issue-130914.6z883_.rst
@@ -0,0 +1,3 @@
+Allow :meth:`graphlib.TopologicalSorter.prepare` to be called more than once
+as long as sorting has not started.
+Patch by Daniel Pope.


Test patch:
diff --git a/Lib/test/test_graphlib.py b/Lib/test/test_graphlib.py
index 5f38af4024c..66722e0b049 100644
--- a/Lib/test/test_graphlib.py
+++ b/Lib/test/test_graphlib.py
@@ -140,9 +140,21 @@ def test_calls_before_prepare(self):
     def test_prepare_multiple_times(self):
         ts = graphlib.TopologicalSorter()
         ts.prepare()
-        with self.assertRaisesRegex(ValueError, r"cannot prepare\(\) more than once"):
+        ts.prepare()
+
+    def test_prepare_after_pass_out(self):
+        ts = graphlib.TopologicalSorter({'a': 'bc'})
+        ts.prepare()
+        self.assertEqual(set(ts.get_ready()), {'b', 'c'})
+        with self.assertRaisesRegex(ValueError, r"cannot prepare\(\) after starting sort"):
             ts.prepare()
 
+    def test_prepare_cycleerror_each_time(self):
+        ts = graphlib.TopologicalSorter({'a': 'b', 'b': 'a'})
+        for attempt in range(1, 4):
+            with self.assertRaises(graphlib.CycleError, msg=f"{attempt=}"):
+                ts.prepare()
+
     def test_invalid_nodes_in_done(self):
         ts = graphlib.TopologicalSorter()
         ts.add(1, 2, 3, 4)