Description

lordmauve

opened on Mar 6, 2025

Issue body actions

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 sorter

Rationale

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 once

This 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 ts

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

>>> 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.

Linked PRs

• gh-130914: Make graphlib.TopologicalSorter.prepare() idempotent #131317

Activity

1. lordmauve

   added

   type-featureA feature request or enhancementA feature request or enhancement

   on Mar 6, 2025
2. picnixz

   added

   stdlibStandard Library Python modules in the Lib/ directoryStandard Library Python modules in the Lib/ directory

   on Mar 7, 2025
3. vstinner commented on Mar 13, 2025

   

   vstinner

   on Mar 13, 2025

   Member

   More actions

   cc @pablogsal
4. pablogsal commented on Mar 13, 2025

   

   pablogsal

   on Mar 13, 2025

   Member

   More actions

   @tim-one what do you think Tim?
5. tim-one commented on Mar 13, 2025

   

   tim-one

   on Mar 13, 2025

   Member

   More actions

   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:

   if self._ready_nodes is None:
       self.prepare()
   elif self._npassedout:
       raise ValueError("static_order() cannot be called after work has started")  

   Reacted by Daniel Pope
6. tim-one commented on Mar 14, 2025

   

   tim-one

   on Mar 14, 2025

   Member

   More actions

   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.

   Reacted by Daniel Pope
7. lordmauve commented on Mar 16, 2025

   

   lordmauve

   on Mar 16, 2025

   ContributorAuthor

   More actions

   One consequence of reusing _npassedout is that empty TopologicalSorters would let you call prepare after static_order():

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

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

   >>> 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
8. lordmauve

   added a commit that references this issue on Mar 16, 2025

   Make graphlib.TopologicalSorter.prepare() idempotent

   This issue will close once commit 220f1fd is merged into the 'master' branch.

   220f1fd
9. tim-one

   closed this as completedin #131317on Mar 18, 2025
10. tim-one

    closed this as completedin c1b42dbon Mar 18, 2025
11. sebbASF

    added 2 commits that reference this issue on Mar 18, 2025

    pythongh-130914: Make graphlib.TopologicalSorter.prepare() idempotent (…

    c1b42db

    Revert "pythongh-130914: Make graphlib.TopologicalSorter.prepare() id…

    ef14dab
12. colesbury

    added a commit that references this issue on Mar 20, 2025

    pythongh-130914: Make graphlib.TopologicalSorter.prepare() idempotent (…

    d2725d3

Issue actions