https://github.com/python/cpython/commit/c1b42db9e47b76fca3c2993cb172cc4991b04839
commit: c1b42db9e47b76fca3c2993cb172cc4991b04839
branch: main
author: Daniel Pope <[email protected]>
committer: tim-one <[email protected]>
date: 2025-03-18T16:28:00-05:00
summary:
gh-130914: Make graphlib.TopologicalSorter.prepare() idempotent (#131317)
Closes #130914: Make graphlib.TopologicalSorter.prepare() idempotent
Relax the rules so that `.prepare()` can be called multiple times, provided
that no work has been passed out by `.get_ready()` yet.
files:
A Misc/NEWS.d/next/Library/2025-03-16-08-00-29.gh-issue-130914.6z883_.rst
M Doc/library/graphlib.rst
M Doc/whatsnew/3.14.rst
M Lib/graphlib.py
M Lib/test/test_graphlib.py
M Misc/ACKS
diff --git a/Doc/library/graphlib.rst b/Doc/library/graphlib.rst
index a0b16576fad219..49424700303fdd 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 9a25f27ca57257..79b219dd72651c 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 82f33fb5cf312c..7961c9c5cac2d6 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/Lib/test/test_graphlib.py b/Lib/test/test_graphlib.py
index 5f38af4024c5b0..66722e0b0498a6 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)
diff --git a/Misc/ACKS b/Misc/ACKS
index c623d69e086b63..b0b4ea0db44b64 100644
--- a/Misc/ACKS
+++ b/Misc/ACKS
@@ -1483,6 +1483,7 @@ Michael Pomraning
Martin Pool
Iustin Pop
Claudiu Popa
+Daniel Pope
Nick Pope
John Popplewell
Matheus Vieira Portela
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 00000000000000..956cf83758f9a2
--- /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.
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3/lists/python-checkins.python.org/
Member address: [email protected]
