Repository navigation
graphlib.TopologicalSorter.prepare() should be idempotent #130914
Description
Feature or enhancement
Proposal:
Proposed Behaviour
TopologicalSorter.prepare() should be idempotent such that calling it repeatedly without draining anything is not an error:
>>> 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:
>>> import graphlib
>>> ts = graphlib.TopologicalSorter()
>>> ts.prepare()
>>> ts.get_ready()
()
>>> ts.prepare()
Traceback (most recent call last):
...
ValueError: cannot prepare() after mutating prepared sorterRationale
TopologicalSorter.prepare() raises an exception if you call it twice:
>>> 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 onceThis is rather unfortunate because if you return a TopologicalSorter that is prepared:
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 tsbecause then you cannot run .static_order() on it:
>>> get_sorter().static_order()
Traceback (most recent call last):
...
ValueError: cannot prepare() more than oncewhile 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.
Activity
vstinner commentedon Mar 13, 2025
cc @pablogsal
pablogsal commentedon Mar 13, 2025
@tim-one what do you think Tim?
tim-one commentedon Mar 13, 2025
I like the simple rule
.prepare()can be called at most once. I'd change the OP'sget_sorter()to take an optionalprepare=Trueargument, and leave it on the user to call that withFalseif 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(), whenself._ready_nodesis notNone, could just return ifself._npassedout == 0.Altermative: leave
.prepare()alone and changestatic_order()instead, to start with:tim-one commentedon Mar 14, 2025
On second thought,
.prepare()is being more dogmatic than necessary. Calling it again is harmless so long as._npassedoutis 0 (and in that case -._ready_nodes is not Nonebut.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_nodeswould become empty again, despite that the user never saw what was in it.lordmauve commentedon Mar 16, 2025
One consequence of reusing
_npassedoutis that empty TopologicalSorters would let you call prepare after static_order():While a non-empty one doesn't allow that:
Make graphlib.TopologicalSorter.prepare() idempotent
pythongh-130914: Make graphlib.TopologicalSorter.prepare() idempotent (…
Revert "pythongh-130914: Make graphlib.TopologicalSorter.prepare() id…
pythongh-130914: Make graphlib.TopologicalSorter.prepare() idempotent (…