Mailman 3 May 2020 - Python-checkins

bpo-17005: Move topological sort functionality to its own module (GH-20558)
by Pablo Galindo 31 May '20

31 May '20

https://github.com/python/cpython/commit/2f172d8f1525defe9bba4d49e967fdfc69… commit: 2f172d8f1525defe9bba4d49e967fdfc69151731 branch: master author: Pablo Galindo <Pablogsal(a)gmail.com> committer: GitHub <noreply(a)github.com> date: 2020-06-01T00:41:14+01:00 summary: bpo-17005: Move topological sort functionality to its own module (GH-20558) The topological sort functionality that was introduced initially in the functools module has been moved to a new graphlib module to better accommodate the new tools and keep the original scope of the functools module. files: A Doc/library/graphlib.rst A Lib/graphlib.py A Lib/test/test_graphlib.py A Misc/NEWS.d/next/Library/2020-05-31-23-32-36.bpo-17005.JlRUGB.rst M Doc/library/datatypes.rst M Doc/library/functools.rst M Doc/whatsnew/3.9.rst M Lib/functools.py M Lib/test/test_functools.py M PCbuild/lib.pyproj diff --git a/Doc/library/datatypes.rst b/Doc/library/datatypes.rst index 675bbb6fafdca..ff51b2779e5fa 100644 --- a/Doc/library/datatypes.rst +++ b/Doc/library/datatypes.rst @@ -33,3 +33,4 @@ The following modules are documented in this chapter: pprint.rst reprlib.rst enum.rst + graphlib.rst diff --git a/Doc/library/functools.rst b/Doc/library/functools.rst index a44eb85b27dba..14aa184e2cd14 100644 --- a/Doc/library/functools.rst +++ b/Doc/library/functools.rst @@ -543,184 +543,6 @@ The :mod:`functools` module defines the following functions: .. versionadded:: 3.8 -.. class:: TopologicalSorter(graph=None) - - Provides functionality to topologically sort a graph of hashable nodes. - - A topological order is a linear ordering of the vertices in a graph such that - for every directed edge u -> v from vertex u to vertex v, vertex u comes - before vertex v in the ordering. For instance, the vertices of the graph may - represent tasks to be performed, and the edges may represent constraints that - one task must be performed before another; in this example, a topological - ordering is just a valid sequence for the tasks. A complete topological - ordering is possible if and only if the graph has no directed cycles, that - is, if it is a directed acyclic graph. - - If the optional *graph* argument is provided it must be a dictionary - representing a directed acyclic graph where the keys are nodes and the values - are iterables of all predecessors of that node in the graph (the nodes that - have edges that point to the value in the key). Additional nodes can be added - to the graph using the :meth:`~TopologicalSorter.add` method. - - In the general case, the steps required to perform the sorting of a given - graph are as follows: - - * Create an instance of the :class:`TopologicalSorter` with an optional - initial graph. - * Add additional nodes to the graph. - * Call :meth:`~TopologicalSorter.prepare` on the graph. - * While :meth:`~TopologicalSorter.is_active` is ``True``, iterate over - the nodes returned by :meth:`~TopologicalSorter.get_ready` and - process them. Call :meth:`~TopologicalSorter.done` on each node as it - finishes processing. - - In case just an immediate sorting of the nodes in the graph is required and - no parallelism is involved, the convenience method - :meth:`TopologicalSorter.static_order` can be used directly: - - .. doctest:: - - >>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}} - >>> ts = TopologicalSorter(graph) - >>> tuple(ts.static_order()) - ('A', 'C', 'B', 'D') - - The class is designed to easily support parallel processing of the nodes as - they become ready. For instance:: - - topological_sorter = TopologicalSorter() - - # Add nodes to 'topological_sorter'... - - topological_sorter.prepare() - while topological_sorter.is_active(): - for node in topological_sorter.get_ready(): - # Worker threads or processes take nodes to work on off the - # 'task_queue' queue. - task_queue.put(node) - - # When the work for a node is done, workers put the node in - # 'finalized_tasks_queue' so we can get more nodes to work on. - # The definition of 'is_active()' guarantees that, at this point, at - # least one node has been placed on 'task_queue' that hasn't yet - # been passed to 'done()', so this blocking 'get()' must (eventually) - # succeed. After calling 'done()', we loop back to call 'get_ready()' - # again, so put newly freed nodes on 'task_queue' as soon as - # logically possible. - node = finalized_tasks_queue.get() - topological_sorter.done(node) - - .. method:: add(node, *predecessors) - - Add a new node and its predecessors to the graph. Both the *node* and all - elements in *predecessors* must be hashable. - - If called multiple times with the same node argument, the set of - dependencies will be the union of all dependencies passed in. - - It is possible to add a node with no dependencies (*predecessors* is not - provided) or to provide a dependency twice. If a node that has not been - provided before is included among *predecessors* it will be automatically - added to the graph with no predecessors of its own. - - Raises :exc:`ValueError` if called after :meth:`~TopologicalSorter.prepare`. - - .. method:: prepare() - - Mark the graph as finished and check for cycles in the graph. If any cycle - is detected, :exc:`CycleError` will be raised, but - :meth:`~TopologicalSorter.get_ready` can 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 :meth:`~TopologicalSorter.add`. - - .. method:: is_active() - - Returns ``True`` if more progress can be made and ``False`` otherwise. - Progress can be made if cycles do not block the resolution and either - there are still nodes ready that haven't yet been returned by - :meth:`TopologicalSorter.get_ready` or the number of nodes marked - :meth:`TopologicalSorter.done` is less than the number that have been - returned by :meth:`TopologicalSorter.get_ready`. - - The :meth:`~TopologicalSorter.__bool__` method of this class defers to - this function, so instead of:: - - if ts.is_active(): - ... - - if possible to simply do:: - - if ts: - ... - - Raises :exc:`ValueError` if called without calling - :meth:`~TopologicalSorter.prepare` previously. - - .. method:: done(*nodes) - - Marks a set of nodes returned by :meth:`TopologicalSorter.get_ready` as - processed, unblocking any successor of each node in *nodes* for being - returned in the future by a call to :meth:`TopologicalSorter.get_ready`. - - Raises :exc:`ValueError` if any node in *nodes* has already been marked as - processed by a previous call to this method or if a node was not added to - the graph by using :meth:`TopologicalSorter.add`, if called without - calling :meth:`~TopologicalSorter.prepare` or if node has not yet been - returned by :meth:`~TopologicalSorter.get_ready`. - - .. method:: get_ready() - - Returns a ``tuple`` with all the nodes that are ready. Initially it - returns all nodes with no predecessors, and once those are marked as - processed by calling :meth:`TopologicalSorter.done`, further calls will - return all new nodes that have all their predecessors already processed. - Once no more progress can be made, empty tuples are returned. - - Raises :exc:`ValueError` if called without calling - :meth:`~TopologicalSorter.prepare` previously. - - .. method:: static_order() - - Returns an iterable of nodes in a topological order. Using this method - does not require to call :meth:`TopologicalSorter.prepare` or - :meth:`TopologicalSorter.done`. This method is equivalent to:: - - def static_order(self): - self.prepare() - while self.is_active(): - node_group = self.get_ready() - yield from node_group - self.done(*node_group) - - The particular order that is returned may depend on the specific order in - which the items were inserted in the graph. For example: - - .. doctest:: - - >>> ts = TopologicalSorter() - >>> ts.add(3, 2, 1) - >>> ts.add(1, 0) - >>> print([*ts.static_order()]) - [2, 0, 1, 3] - - >>> ts2 = TopologicalSorter() - >>> ts2.add(1, 0) - >>> ts2.add(3, 2, 1) - >>> print([*ts2.static_order()]) - [0, 2, 1, 3] - - This is due to the fact that "0" and "2" are in the same level in the - graph (they would have been returned in the same call to - :meth:`~TopologicalSorter.get_ready`) and the order between them is - determined by the order of insertion. - - - If any cycle is detected, :exc:`CycleError` will be raised. - - .. versionadded:: 3.9 - - .. function:: update_wrapper(wrapper, wrapped, assigned=WRAPPER_ASSIGNMENTS, updated=WRAPPER_UPDATES) Update a *wrapper* function to look like the *wrapped* function. The optional @@ -829,20 +651,4 @@ callable, weak referencable, and can have attributes. There are some important differences. For instance, the :attr:`~definition.__name__` and :attr:`__doc__` attributes are not created automatically. Also, :class:`partial` objects defined in classes behave like static methods and do not transform into bound methods -during instance attribute look-up. - - -Exceptions ----------- -The :mod:`functools` module defines the following exception classes: - -.. exception:: CycleError - - Subclass of :exc:`ValueError` raised by :meth:`TopologicalSorter.prepare` if cycles exist - in the working graph. If multiple cycles exist, only one undefined choice among them will - be reported and included in the exception. - - The detected cycle can be accessed via the second element in the :attr:`~CycleError.args` - attribute of the exception instance and consists in a list of nodes, such that each node is, - in the graph, an immediate predecessor of the next node in the list. In the reported list, - the first and the last node will be the same, to make it clear that it is cyclic. +during instance attribute look-up. \ No newline at end of file diff --git a/Doc/library/graphlib.rst b/Doc/library/graphlib.rst new file mode 100644 index 0000000000000..820615e723015 --- /dev/null +++ b/Doc/library/graphlib.rst @@ -0,0 +1,209 @@ +:mod:`graphlib` --- Functionality to operate with graph-like structures +========================================================================= + +.. module:: graphlib + :synopsis: Functionality to operate with graph-like structures + + +**Source code:** :source:`Lib/graphlib.py` + +.. testsetup:: default + + import graphlib + from graphlib import * + +-------------- + + +.. class:: TopologicalSorter(graph=None) + + Provides functionality to topologically sort a graph of hashable nodes. + + A topological order is a linear ordering of the vertices in a graph such that + for every directed edge u -> v from vertex u to vertex v, vertex u comes + before vertex v in the ordering. For instance, the vertices of the graph may + represent tasks to be performed, and the edges may represent constraints that + one task must be performed before another; in this example, a topological + ordering is just a valid sequence for the tasks. A complete topological + ordering is possible if and only if the graph has no directed cycles, that + is, if it is a directed acyclic graph. + + If the optional *graph* argument is provided it must be a dictionary + representing a directed acyclic graph where the keys are nodes and the values + are iterables of all predecessors of that node in the graph (the nodes that + have edges that point to the value in the key). Additional nodes can be added + to the graph using the :meth:`~TopologicalSorter.add` method. + + In the general case, the steps required to perform the sorting of a given + graph are as follows: + + * Create an instance of the :class:`TopologicalSorter` with an optional + initial graph. + * Add additional nodes to the graph. + * Call :meth:`~TopologicalSorter.prepare` on the graph. + * While :meth:`~TopologicalSorter.is_active` is ``True``, iterate over + the nodes returned by :meth:`~TopologicalSorter.get_ready` and + process them. Call :meth:`~TopologicalSorter.done` on each node as it + finishes processing. + + In case just an immediate sorting of the nodes in the graph is required and + no parallelism is involved, the convenience method + :meth:`TopologicalSorter.static_order` can be used directly: + + .. doctest:: + + >>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}} + >>> ts = TopologicalSorter(graph) + >>> tuple(ts.static_order()) + ('A', 'C', 'B', 'D') + + The class is designed to easily support parallel processing of the nodes as + they become ready. For instance:: + + topological_sorter = TopologicalSorter() + + # Add nodes to 'topological_sorter'... + + topological_sorter.prepare() + while topological_sorter.is_active(): + for node in topological_sorter.get_ready(): + # Worker threads or processes take nodes to work on off the + # 'task_queue' queue. + task_queue.put(node) + + # When the work for a node is done, workers put the node in + # 'finalized_tasks_queue' so we can get more nodes to work on. + # The definition of 'is_active()' guarantees that, at this point, at + # least one node has been placed on 'task_queue' that hasn't yet + # been passed to 'done()', so this blocking 'get()' must (eventually) + # succeed. After calling 'done()', we loop back to call 'get_ready()' + # again, so put newly freed nodes on 'task_queue' as soon as + # logically possible. + node = finalized_tasks_queue.get() + topological_sorter.done(node) + + .. method:: add(node, *predecessors) + + Add a new node and its predecessors to the graph. Both the *node* and all + elements in *predecessors* must be hashable. + + If called multiple times with the same node argument, the set of + dependencies will be the union of all dependencies passed in. + + It is possible to add a node with no dependencies (*predecessors* is not + provided) or to provide a dependency twice. If a node that has not been + provided before is included among *predecessors* it will be automatically + added to the graph with no predecessors of its own. + + Raises :exc:`ValueError` if called after :meth:`~TopologicalSorter.prepare`. + + .. method:: prepare() + + Mark the graph as finished and check for cycles in the graph. If any cycle + is detected, :exc:`CycleError` will be raised, but + :meth:`~TopologicalSorter.get_ready` can 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 :meth:`~TopologicalSorter.add`. + + .. method:: is_active() + + Returns ``True`` if more progress can be made and ``False`` otherwise. + Progress can be made if cycles do not block the resolution and either + there are still nodes ready that haven't yet been returned by + :meth:`TopologicalSorter.get_ready` or the number of nodes marked + :meth:`TopologicalSorter.done` is less than the number that have been + returned by :meth:`TopologicalSorter.get_ready`. + + The :meth:`~TopologicalSorter.__bool__` method of this class defers to + this function, so instead of:: + + if ts.is_active(): + ... + + if possible to simply do:: + + if ts: + ... + + Raises :exc:`ValueError` if called without calling + :meth:`~TopologicalSorter.prepare` previously. + + .. method:: done(*nodes) + + Marks a set of nodes returned by :meth:`TopologicalSorter.get_ready` as + processed, unblocking any successor of each node in *nodes* for being + returned in the future by a call to :meth:`TopologicalSorter.get_ready`. + + Raises :exc:`ValueError` if any node in *nodes* has already been marked as + processed by a previous call to this method or if a node was not added to + the graph by using :meth:`TopologicalSorter.add`, if called without + calling :meth:`~TopologicalSorter.prepare` or if node has not yet been + returned by :meth:`~TopologicalSorter.get_ready`. + + .. method:: get_ready() + + Returns a ``tuple`` with all the nodes that are ready. Initially it + returns all nodes with no predecessors, and once those are marked as + processed by calling :meth:`TopologicalSorter.done`, further calls will + return all new nodes that have all their predecessors already processed. + Once no more progress can be made, empty tuples are returned. + + Raises :exc:`ValueError` if called without calling + :meth:`~TopologicalSorter.prepare` previously. + + .. method:: static_order() + + Returns an iterable of nodes in a topological order. Using this method + does not require to call :meth:`TopologicalSorter.prepare` or + :meth:`TopologicalSorter.done`. This method is equivalent to:: + + def static_order(self): + self.prepare() + while self.is_active(): + node_group = self.get_ready() + yield from node_group + self.done(*node_group) + + The particular order that is returned may depend on the specific order in + which the items were inserted in the graph. For example: + + .. doctest:: + + >>> ts = TopologicalSorter() + >>> ts.add(3, 2, 1) + >>> ts.add(1, 0) + >>> print([*ts.static_order()]) + [2, 0, 1, 3] + + >>> ts2 = TopologicalSorter() + >>> ts2.add(1, 0) + >>> ts2.add(3, 2, 1) + >>> print([*ts2.static_order()]) + [0, 2, 1, 3] + + This is due to the fact that "0" and "2" are in the same level in the + graph (they would have been returned in the same call to + :meth:`~TopologicalSorter.get_ready`) and the order between them is + determined by the order of insertion. + + + If any cycle is detected, :exc:`CycleError` will be raised. + + .. versionadded:: 3.9 + + +Exceptions +---------- +The :mod:`graphlib` module defines the following exception classes: + +.. exception:: CycleError + + Subclass of :exc:`ValueError` raised by :meth:`TopologicalSorter.prepare` if cycles exist + in the working graph. If multiple cycles exist, only one undefined choice among them will + be reported and included in the exception. + + The detected cycle can be accessed via the second element in the :attr:`~CycleError.args` + attribute of the exception instance and consists in a list of nodes, such that each node is, + in the graph, an immediate predecessor of the next node in the list. In the reported list, + the first and the last node will be the same, to make it clear that it is cyclic. \ No newline at end of file diff --git a/Doc/whatsnew/3.9.rst b/Doc/whatsnew/3.9.rst index 3d5cec6026add..a468130af1083 100644 --- a/Doc/whatsnew/3.9.rst +++ b/Doc/whatsnew/3.9.rst @@ -245,6 +245,14 @@ PyPI and maintained by the CPython core team. PEP written and implemented by Paul Ganssle +graphlib +--------- + +Add the :mod:`graphlib` that contains the :class:`graphlib.TopologicalSorter` class +to offer functionality to perform topological sorting of graphs. (Contributed by Pablo +Galindo, Tim Peters and Larry Hastings in :issue:`17005`.) + + Improved Modules ================ @@ -352,13 +360,6 @@ ftplib if the given timeout for their constructor is zero to prevent the creation of a non-blocking socket. (Contributed by Dong-hee Na in :issue:`39259`.) -functools ---------- - -Add the :class:`functools.TopologicalSorter` class to offer functionality to perform -topological sorting of graphs. (Contributed by Pablo Galindo, Tim Peters and Larry -Hastings in :issue:`17005`.) - gc -- diff --git a/Lib/functools.py b/Lib/functools.py index 87c7d87438998..5cab497d26403 100644 --- a/Lib/functools.py +++ b/Lib/functools.py @@ -11,7 +11,6 @@ __all__ = ['update_wrapper', 'wraps', 'WRAPPER_ASSIGNMENTS', 'WRAPPER_UPDATES', 'total_ordering', 'cache', 'cmp_to_key', 'lru_cache', 'reduce', - 'TopologicalSorter', 'CycleError', 'partial', 'partialmethod', 'singledispatch', 'singledispatchmethod', 'cached_property'] @@ -199,250 +198,6 @@ def total_ordering(cls): setattr(cls, opname, opfunc) return cls -################################################################################ -### topological sort -################################################################################ - -_NODE_OUT = -1 -_NODE_DONE = -2 - - -class _NodeInfo: - __slots__ = 'node', 'npredecessors', 'successors' - - def __init__(self, node): - # The node this class is augmenting. - self.node = node - - # Number of predecessors, generally >= 0. When this value falls to 0, - # and is returned by get_ready(), this is set to _NODE_OUT and when the - # node is marked done by a call to done(), set to _NODE_DONE. - self.npredecessors = 0 - - # List of successor nodes. The list can contain duplicated elements as - # long as they're all reflected in the successor's npredecessors attribute). - self.successors = [] - - -class CycleError(ValueError): - """Subclass of ValueError raised by TopologicalSorterif cycles exist in the graph - - If multiple cycles exist, only one undefined choice among them will be reported - and included in the exception. The detected cycle can be accessed via the second - element in the *args* attribute of the exception instance and consists in a list - of nodes, such that each node is, in the graph, an immediate predecessor of the - next node in the list. In the reported list, the first and the last node will be - the same, to make it clear that it is cyclic. - """ - pass - - -class TopologicalSorter: - """Provides functionality to topologically sort a graph of hashable nodes""" - - def __init__(self, graph=None): - self._node2info = {} - self._ready_nodes = None - self._npassedout = 0 - self._nfinished = 0 - - if graph is not None: - for node, predecessors in graph.items(): - self.add(node, *predecessors) - - def _get_nodeinfo(self, node): - if (result := self._node2info.get(node)) is None: - self._node2info[node] = result = _NodeInfo(node) - return result - - def add(self, node, *predecessors): - """Add a new node and its predecessors to the graph. - - Both the *node* and all elements in *predecessors* must be hashable. - - If called multiple times with the same node argument, the set of dependencies - will be the union of all dependencies passed in. - - It is possible to add a node with no dependencies (*predecessors* is not provided) - as well as provide a dependency twice. If a node that has not been provided before - is included among *predecessors* it will be automatically added to the graph with - no predecessors of its own. - - Raises ValueError if called after "prepare". - """ - if self._ready_nodes is not None: - raise ValueError("Nodes cannot be added after a call to prepare()") - - # Create the node -> predecessor edges - nodeinfo = self._get_nodeinfo(node) - nodeinfo.npredecessors += len(predecessors) - - # Create the predecessor -> node edges - for pred in predecessors: - pred_info = self._get_nodeinfo(pred) - pred_info.successors.append(node) - - def prepare(self): - """Mark the graph as finished and check for cycles in the graph. - - If any cycle is detected, "CycleError" will be raised, but "get_ready" can - 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". - """ - if self._ready_nodes is not None: - raise ValueError("cannot prepare() more than once") - - 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 - # nodes as possible before cycles block more progress - cycle = self._find_cycle() - if cycle: - raise CycleError(f"nodes are in a cycle", cycle) - - def get_ready(self): - """Return a tuple of all the nodes that are ready. - - Initially it returns all nodes with no predecessors; once those are marked - as processed by calling "done", further calls will return all new nodes that - have all their predecessors already processed. Once no more progress can be made, - empty tuples are returned. - - Raises ValueError if called without calling "prepare" previously. - """ - if self._ready_nodes is None: - raise ValueError("prepare() must be called first") - - # Get the nodes that are ready and mark them - result = tuple(self._ready_nodes) - n2i = self._node2info - for node in result: - n2i[node].npredecessors = _NODE_OUT - - # Clean the list of nodes that are ready and update - # the counter of nodes that we have returned. - self._ready_nodes.clear() - self._npassedout += len(result) - - return result - - def is_active(self): - """Return True if more progress can be made and ``False`` otherwise. - - Progress can be made if cycles do not block the resolution and either there - are still nodes ready that haven't yet been returned by "get_ready" or the - number of nodes marked "done" is less than the number that have been returned - by "get_ready". - - Raises ValueError if called without calling "prepare" previously. - """ - if self._ready_nodes is None: - raise ValueError("prepare() must be called first") - return self._nfinished < self._npassedout or bool(self._ready_nodes) - - def __bool__(self): - return self.is_active() - - def done(self, *nodes): - """Marks a set of nodes returned by "get_ready" as processed. - - This method unblocks any successor of each node in *nodes* for being returned - in the future by a a call to "get_ready" - - Raises :exec:`ValueError` if any node in *nodes* has already been marked as - processed by a previous call to this method, if a node was not added to the - graph by using "add" or if called without calling "prepare" previously or if - node has not yet been returned by "get_ready". - """ - - if self._ready_nodes is None: - raise ValueError("prepare() must be called first") - - n2i = self._node2info - - for node in nodes: - - # Check if we know about this node (it was added previously using add() - if (nodeinfo := n2i.get(node)) is None: - raise ValueError(f"node {node!r} was not added using add()") - - # If the node has not being returned (marked as ready) previously, inform the user. - stat = nodeinfo.npredecessors - if stat != _NODE_OUT: - if stat >= 0: - raise ValueError(f"node {node!r} was not passed out (still not ready)") - elif stat == _NODE_DONE: - raise ValueError(f"node {node!r} was already marked done") - else: - assert False, f"node {node!r}: unknown status {stat}" - - # Mark the node as processed - nodeinfo.npredecessors = _NODE_DONE - - # Go to all the successors and reduce the number of predecessors, collecting all the ones - # that are ready to be returned in the next get_ready() call. - for successor in nodeinfo.successors: - successor_info = n2i[successor] - successor_info.npredecessors -= 1 - if successor_info.npredecessors == 0: - self._ready_nodes.append(successor) - self._nfinished += 1 - - def _find_cycle(self): - n2i = self._node2info - stack = [] - itstack = [] - seen = set() - node2stacki = {} - - for node in n2i: - if node in seen: - continue - - while True: - if node in seen: - # If we have seen already the node and is in the - # current stack we have found a cycle. - if node in node2stacki: - return stack[node2stacki[node]:] + [node] - # else go on to get next successor - else: - seen.add(node) - itstack.append(iter(n2i[node].successors).__next__) - node2stacki[node] = len(stack) - stack.append(node) - - # Backtrack to the topmost stack entry with - # at least another successor. - while stack: - try: - node = itstack[-1]() - break - except StopIteration: - del node2stacki[stack.pop()] - itstack.pop() - else: - break - return None - - def static_order(self): - """Returns an iterable of nodes in a topological order. - - The particular order that is returned may depend on the specific - order in which the items were inserted in the graph. - - Using this method does not require to call "prepare" or "done". If any - cycle is detected, :exc:`CycleError` will be raised. - """ - self.prepare() - while self.is_active(): - node_group = self.get_ready() - yield from node_group - self.done(*node_group) - ################################################################################ ### cmp_to_key() function converter diff --git a/Lib/graphlib.py b/Lib/graphlib.py new file mode 100644 index 0000000000000..948f62f1dc303 --- /dev/null +++ b/Lib/graphlib.py @@ -0,0 +1,245 @@ +__all__ = ["TopologicalSorter", "CycleError"] + +_NODE_OUT = -1 +_NODE_DONE = -2 + + +class _NodeInfo: + __slots__ = "node", "npredecessors", "successors" + + def __init__(self, node): + # The node this class is augmenting. + self.node = node + + # Number of predecessors, generally >= 0. When this value falls to 0, + # and is returned by get_ready(), this is set to _NODE_OUT and when the + # node is marked done by a call to done(), set to _NODE_DONE. + self.npredecessors = 0 + + # List of successor nodes. The list can contain duplicated elements as + # long as they're all reflected in the successor's npredecessors attribute). + self.successors = [] + + +class CycleError(ValueError): + """Subclass of ValueError raised by TopologicalSorterif cycles exist in the graph + + If multiple cycles exist, only one undefined choice among them will be reported + and included in the exception. The detected cycle can be accessed via the second + element in the *args* attribute of the exception instance and consists in a list + of nodes, such that each node is, in the graph, an immediate predecessor of the + next node in the list. In the reported list, the first and the last node will be + the same, to make it clear that it is cyclic. + """ + + pass + + +class TopologicalSorter: + """Provides functionality to topologically sort a graph of hashable nodes""" + + def __init__(self, graph=None): + self._node2info = {} + self._ready_nodes = None + self._npassedout = 0 + self._nfinished = 0 + + if graph is not None: + for node, predecessors in graph.items(): + self.add(node, *predecessors) + + def _get_nodeinfo(self, node): + if (result := self._node2info.get(node)) is None: + self._node2info[node] = result = _NodeInfo(node) + return result + + def add(self, node, *predecessors): + """Add a new node and its predecessors to the graph. + + Both the *node* and all elements in *predecessors* must be hashable. + + If called multiple times with the same node argument, the set of dependencies + will be the union of all dependencies passed in. + + It is possible to add a node with no dependencies (*predecessors* is not provided) + as well as provide a dependency twice. If a node that has not been provided before + is included among *predecessors* it will be automatically added to the graph with + no predecessors of its own. + + Raises ValueError if called after "prepare". + """ + if self._ready_nodes is not None: + raise ValueError("Nodes cannot be added after a call to prepare()") + + # Create the node -> predecessor edges + nodeinfo = self._get_nodeinfo(node) + nodeinfo.npredecessors += len(predecessors) + + # Create the predecessor -> node edges + for pred in predecessors: + pred_info = self._get_nodeinfo(pred) + pred_info.successors.append(node) + + def prepare(self): + """Mark the graph as finished and check for cycles in the graph. + + If any cycle is detected, "CycleError" will be raised, but "get_ready" can + 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". + """ + if self._ready_nodes is not None: + raise ValueError("cannot prepare() more than once") + + 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 + # nodes as possible before cycles block more progress + cycle = self._find_cycle() + if cycle: + raise CycleError(f"nodes are in a cycle", cycle) + + def get_ready(self): + """Return a tuple of all the nodes that are ready. + + Initially it returns all nodes with no predecessors; once those are marked + as processed by calling "done", further calls will return all new nodes that + have all their predecessors already processed. Once no more progress can be made, + empty tuples are returned. + + Raises ValueError if called without calling "prepare" previously. + """ + if self._ready_nodes is None: + raise ValueError("prepare() must be called first") + + # Get the nodes that are ready and mark them + result = tuple(self._ready_nodes) + n2i = self._node2info + for node in result: + n2i[node].npredecessors = _NODE_OUT + + # Clean the list of nodes that are ready and update + # the counter of nodes that we have returned. + self._ready_nodes.clear() + self._npassedout += len(result) + + return result + + def is_active(self): + """Return True if more progress can be made and ``False`` otherwise. + + Progress can be made if cycles do not block the resolution and either there + are still nodes ready that haven't yet been returned by "get_ready" or the + number of nodes marked "done" is less than the number that have been returned + by "get_ready". + + Raises ValueError if called without calling "prepare" previously. + """ + if self._ready_nodes is None: + raise ValueError("prepare() must be called first") + return self._nfinished < self._npassedout or bool(self._ready_nodes) + + def __bool__(self): + return self.is_active() + + def done(self, *nodes): + """Marks a set of nodes returned by "get_ready" as processed. + + This method unblocks any successor of each node in *nodes* for being returned + in the future by a a call to "get_ready" + + Raises :exec:`ValueError` if any node in *nodes* has already been marked as + processed by a previous call to this method, if a node was not added to the + graph by using "add" or if called without calling "prepare" previously or if + node has not yet been returned by "get_ready". + """ + + if self._ready_nodes is None: + raise ValueError("prepare() must be called first") + + n2i = self._node2info + + for node in nodes: + + # Check if we know about this node (it was added previously using add() + if (nodeinfo := n2i.get(node)) is None: + raise ValueError(f"node {node!r} was not added using add()") + + # If the node has not being returned (marked as ready) previously, inform the user. + stat = nodeinfo.npredecessors + if stat != _NODE_OUT: + if stat >= 0: + raise ValueError( + f"node {node!r} was not passed out (still not ready)" + ) + elif stat == _NODE_DONE: + raise ValueError(f"node {node!r} was already marked done") + else: + assert False, f"node {node!r}: unknown status {stat}" + + # Mark the node as processed + nodeinfo.npredecessors = _NODE_DONE + + # Go to all the successors and reduce the number of predecessors, collecting all the ones + # that are ready to be returned in the next get_ready() call. + for successor in nodeinfo.successors: + successor_info = n2i[successor] + successor_info.npredecessors -= 1 + if successor_info.npredecessors == 0: + self._ready_nodes.append(successor) + self._nfinished += 1 + + def _find_cycle(self): + n2i = self._node2info + stack = [] + itstack = [] + seen = set() + node2stacki = {} + + for node in n2i: + if node in seen: + continue + + while True: + if node in seen: + # If we have seen already the node and is in the + # current stack we have found a cycle. + if node in node2stacki: + return stack[node2stacki[node] :] + [node] + # else go on to get next successor + else: + seen.add(node) + itstack.append(iter(n2i[node].successors).__next__) + node2stacki[node] = len(stack) + stack.append(node) + + # Backtrack to the topmost stack entry with + # at least another successor. + while stack: + try: + node = itstack[-1]() + break + except StopIteration: + del node2stacki[stack.pop()] + itstack.pop() + else: + break + return None + + def static_order(self): + """Returns an iterable of nodes in a topological order. + + The particular order that is returned may depend on the specific + order in which the items were inserted in the graph. + + Using this method does not require to call "prepare" or "done". If any + cycle is detected, :exc:`CycleError` will be raised. + """ + self.prepare() + while self.is_active(): + node_group = self.get_ready() + yield from node_group + self.done(*node_group) diff --git a/Lib/test/test_functools.py b/Lib/test/test_functools.py index 72b7765853bc0..e726188982bc4 100644 --- a/Lib/test/test_functools.py +++ b/Lib/test/test_functools.py @@ -3,7 +3,7 @@ import collections import collections.abc import copy -from itertools import permutations, chain +from itertools import permutations import pickle from random import choice import sys @@ -1164,275 +1164,6 @@ def __eq__(self, other): return self.value == other.value -class TestTopologicalSort(unittest.TestCase): - - def _test_graph(self, graph, expected): - - def static_order_with_groups(ts): - ts.prepare() - while ts.is_active(): - nodes = ts.get_ready() - for node in nodes: - ts.done(node) - yield nodes - - ts = functools.TopologicalSorter(graph) - self.assertEqual(list(static_order_with_groups(ts)), list(expected)) - - ts = functools.TopologicalSorter(graph) - self.assertEqual(list(ts.static_order()), list(chain(*expected))) - - def _assert_cycle(self, graph, cycle): - ts = functools.TopologicalSorter() - for node, dependson in graph.items(): - ts.add(node, *dependson) - try: - ts.prepare() - except functools.CycleError as e: - msg, seq = e.args - self.assertIn(' '.join(map(str, cycle)), - ' '.join(map(str, seq * 2))) - else: - raise - - def test_simple_cases(self): - self._test_graph( - {2: {11}, - 9: {11, 8}, - 10: {11, 3}, - 11: {7, 5}, - 8: {7, 3}}, - [(3, 5, 7), (11, 8), (2, 10, 9)] - ) - - self._test_graph({1: {}}, [(1,)]) - - self._test_graph({x: {x+1} for x in range(10)}, - [(x,) for x in range(10, -1, -1)]) - - self._test_graph({2: {3}, 3: {4}, 4: {5}, 5: {1}, - 11: {12}, 12: {13}, 13: {14}, 14: {15}}, - [(1, 15), (5, 14), (4, 13), (3, 12), (2, 11)]) - - self._test_graph({ - 0: [1, 2], - 1: [3], - 2: [5, 6], - 3: [4], - 4: [9], - 5: [3], - 6: [7], - 7: [8], - 8: [4], - 9: [] - }, - [(9,), (4,), (3, 8), (1, 5, 7), (6,), (2,), (0,)] - ) - - self._test_graph({ - 0: [1, 2], - 1: [], - 2: [3], - 3: [] - }, - [(1, 3), (2,), (0,)] - ) - - self._test_graph({ - 0: [1, 2], - 1: [], - 2: [3], - 3: [], - 4: [5], - 5: [6], - 6: [] - }, - [(1, 3, 6), (2, 5), (0, 4)] - ) - - def test_no_dependencies(self): - self._test_graph( - {1: {2}, - 3: {4}, - 5: {6}}, - [(2, 4, 6), (1, 3, 5)] - ) - - self._test_graph( - {1: set(), - 3: set(), - 5: set()}, - [(1, 3, 5)] - ) - - def test_the_node_multiple_times(self): - # Test same node multiple times in dependencies - self._test_graph({1: {2}, 3: {4}, 0: [2, 4, 4, 4, 4, 4]}, - [(2, 4), (1, 3, 0)]) - - # Test adding the same dependency multiple times - ts = functools.TopologicalSorter() - ts.add(1, 2) - ts.add(1, 2) - ts.add(1, 2) - self.assertEqual([*ts.static_order()], [2, 1]) - - def test_graph_with_iterables(self): - dependson = (2*x + 1 for x in range(5)) - ts = functools.TopologicalSorter({0: dependson}) - self.assertEqual(list(ts.static_order()), [1, 3, 5, 7, 9, 0]) - - def test_add_dependencies_for_same_node_incrementally(self): - # Test same node multiple times - ts = functools.TopologicalSorter() - ts.add(1, 2) - ts.add(1, 3) - ts.add(1, 4) - ts.add(1, 5) - - ts2 = functools.TopologicalSorter({1: {2, 3, 4, 5}}) - self.assertEqual([*ts.static_order()], [*ts2.static_order()]) - - def test_empty(self): - self._test_graph({}, []) - - def test_cycle(self): - # Self cycle - self._assert_cycle({1: {1}}, [1, 1]) - # Simple cycle - self._assert_cycle({1: {2}, 2: {1}}, [1, 2, 1]) - # Indirect cycle - self._assert_cycle({1: {2}, 2: {3}, 3: {1}}, [1, 3, 2, 1]) - # not all elements involved in a cycle - self._assert_cycle({1: {2}, 2: {3}, 3: {1}, 5: {4}, 4: {6}}, [1, 3, 2, 1]) - # Multiple cycles - self._assert_cycle({1: {2}, 2: {1}, 3: {4}, 4: {5}, 6: {7}, 7: {6}}, - [1, 2, 1]) - # Cycle in the middle of the graph - self._assert_cycle({1: {2}, 2: {3}, 3: {2, 4}, 4: {5}}, [3, 2]) - - def test_calls_before_prepare(self): - ts = functools.TopologicalSorter() - - with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"): - ts.get_ready() - with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"): - ts.done(3) - with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"): - ts.is_active() - - def test_prepare_multiple_times(self): - ts = functools.TopologicalSorter() - ts.prepare() - with self.assertRaisesRegex(ValueError, r"cannot prepare\(\) more than once"): - ts.prepare() - - def test_invalid_nodes_in_done(self): - ts = functools.TopologicalSorter() - ts.add(1, 2, 3, 4) - ts.add(2, 3, 4) - ts.prepare() - ts.get_ready() - - with self.assertRaisesRegex(ValueError, "node 2 was not passed out"): - ts.done(2) - with self.assertRaisesRegex(ValueError, r"node 24 was not added using add\(\)"): - ts.done(24) - - def test_done(self): - ts = functools.TopologicalSorter() - ts.add(1, 2, 3, 4) - ts.add(2, 3) - ts.prepare() - - self.assertEqual(ts.get_ready(), (3, 4)) - # If we don't mark anything as done, get_ready() returns nothing - self.assertEqual(ts.get_ready(), ()) - ts.done(3) - # Now 2 becomes available as 3 is done - self.assertEqual(ts.get_ready(), (2,)) - self.assertEqual(ts.get_ready(), ()) - ts.done(4) - ts.done(2) - # Only 1 is missing - self.assertEqual(ts.get_ready(), (1,)) - self.assertEqual(ts.get_ready(), ()) - ts.done(1) - self.assertEqual(ts.get_ready(), ()) - self.assertFalse(ts.is_active()) - - def test_is_active(self): - ts = functools.TopologicalSorter() - ts.add(1, 2) - ts.prepare() - - self.assertTrue(ts.is_active()) - self.assertEqual(ts.get_ready(), (2,)) - self.assertTrue(ts.is_active()) - ts.done(2) - self.assertTrue(ts.is_active()) - self.assertEqual(ts.get_ready(), (1,)) - self.assertTrue(ts.is_active()) - ts.done(1) - self.assertFalse(ts.is_active()) - - def test_not_hashable_nodes(self): - ts = functools.TopologicalSorter() - self.assertRaises(TypeError, ts.add, dict(), 1) - self.assertRaises(TypeError, ts.add, 1, dict()) - self.assertRaises(TypeError, ts.add, dict(), dict()) - - def test_order_of_insertion_does_not_matter_between_groups(self): - def get_groups(ts): - ts.prepare() - while ts.is_active(): - nodes = ts.get_ready() - ts.done(*nodes) - yield set(nodes) - - ts = functools.TopologicalSorter() - ts.add(3, 2, 1) - ts.add(1, 0) - ts.add(4, 5) - ts.add(6, 7) - ts.add(4, 7) - - ts2 = functools.TopologicalSorter() - ts2.add(1, 0) - ts2.add(3, 2, 1) - ts2.add(4, 7) - ts2.add(6, 7) - ts2.add(4, 5) - - self.assertEqual(list(get_groups(ts)), list(get_groups(ts2))) - - def test_static_order_does_not_change_with_the_hash_seed(self): - def check_order_with_hash_seed(seed): - code = """if 1: - import functools - ts = functools.TopologicalSorter() - ts.add('blech', 'bluch', 'hola') - ts.add('abcd', 'blech', 'bluch', 'a', 'b') - ts.add('a', 'a string', 'something', 'b') - ts.add('bluch', 'hola', 'abcde', 'a', 'b') - print(list(ts.static_order())) - """ - env = os.environ.copy() - # signal to assert_python not to do a copy - # of os.environ on its own - env['__cleanenv'] = True - env['PYTHONHASHSEED'] = str(seed) - out = assert_python_ok('-c', code, **env) - return out - - run1 = check_order_with_hash_seed(1234) - run2 = check_order_with_hash_seed(31415) - - self.assertNotEqual(run1, "") - self.assertNotEqual(run2, "") - self.assertEqual(run1, run2) - - class TestCache: # This tests that the pass-through is working as designed. # The underlying functionality is tested in TestLRU. diff --git a/Lib/test/test_graphlib.py b/Lib/test/test_graphlib.py new file mode 100644 index 0000000000000..00432537f22d0 --- /dev/null +++ b/Lib/test/test_graphlib.py @@ -0,0 +1,244 @@ +from itertools import chain +import graphlib +import os +import unittest + +from test.support.script_helper import assert_python_ok + +class TestTopologicalSort(unittest.TestCase): + def _test_graph(self, graph, expected): + def static_order_with_groups(ts): + ts.prepare() + while ts.is_active(): + nodes = ts.get_ready() + for node in nodes: + ts.done(node) + yield nodes + + ts = graphlib.TopologicalSorter(graph) + self.assertEqual(list(static_order_with_groups(ts)), list(expected)) + + ts = graphlib.TopologicalSorter(graph) + self.assertEqual(list(ts.static_order()), list(chain(*expected))) + + def _assert_cycle(self, graph, cycle): + ts = graphlib.TopologicalSorter() + for node, dependson in graph.items(): + ts.add(node, *dependson) + try: + ts.prepare() + except graphlib.CycleError as e: + msg, seq = e.args + self.assertIn(" ".join(map(str, cycle)), " ".join(map(str, seq * 2))) + else: + raise + + def test_simple_cases(self): + self._test_graph( + {2: {11}, 9: {11, 8}, 10: {11, 3}, 11: {7, 5}, 8: {7, 3}}, + [(3, 5, 7), (11, 8), (2, 10, 9)], + ) + + self._test_graph({1: {}}, [(1,)]) + + self._test_graph( + {x: {x + 1} for x in range(10)}, [(x,) for x in range(10, -1, -1)] + ) + + self._test_graph( + {2: {3}, 3: {4}, 4: {5}, 5: {1}, 11: {12}, 12: {13}, 13: {14}, 14: {15}}, + [(1, 15), (5, 14), (4, 13), (3, 12), (2, 11)], + ) + + self._test_graph( + { + 0: [1, 2], + 1: [3], + 2: [5, 6], + 3: [4], + 4: [9], + 5: [3], + 6: [7], + 7: [8], + 8: [4], + 9: [], + }, + [(9,), (4,), (3, 8), (1, 5, 7), (6,), (2,), (0,)], + ) + + self._test_graph({0: [1, 2], 1: [], 2: [3], 3: []}, [(1, 3), (2,), (0,)]) + + self._test_graph( + {0: [1, 2], 1: [], 2: [3], 3: [], 4: [5], 5: [6], 6: []}, + [(1, 3, 6), (2, 5), (0, 4)], + ) + + def test_no_dependencies(self): + self._test_graph({1: {2}, 3: {4}, 5: {6}}, [(2, 4, 6), (1, 3, 5)]) + + self._test_graph({1: set(), 3: set(), 5: set()}, [(1, 3, 5)]) + + def test_the_node_multiple_times(self): + # Test same node multiple times in dependencies + self._test_graph({1: {2}, 3: {4}, 0: [2, 4, 4, 4, 4, 4]}, [(2, 4), (1, 3, 0)]) + + # Test adding the same dependency multiple times + ts = graphlib.TopologicalSorter() + ts.add(1, 2) + ts.add(1, 2) + ts.add(1, 2) + self.assertEqual([*ts.static_order()], [2, 1]) + + def test_graph_with_iterables(self): + dependson = (2 * x + 1 for x in range(5)) + ts = graphlib.TopologicalSorter({0: dependson}) + self.assertEqual(list(ts.static_order()), [1, 3, 5, 7, 9, 0]) + + def test_add_dependencies_for_same_node_incrementally(self): + # Test same node multiple times + ts = graphlib.TopologicalSorter() + ts.add(1, 2) + ts.add(1, 3) + ts.add(1, 4) + ts.add(1, 5) + + ts2 = graphlib.TopologicalSorter({1: {2, 3, 4, 5}}) + self.assertEqual([*ts.static_order()], [*ts2.static_order()]) + + def test_empty(self): + self._test_graph({}, []) + + def test_cycle(self): + # Self cycle + self._assert_cycle({1: {1}}, [1, 1]) + # Simple cycle + self._assert_cycle({1: {2}, 2: {1}}, [1, 2, 1]) + # Indirect cycle + self._assert_cycle({1: {2}, 2: {3}, 3: {1}}, [1, 3, 2, 1]) + # not all elements involved in a cycle + self._assert_cycle({1: {2}, 2: {3}, 3: {1}, 5: {4}, 4: {6}}, [1, 3, 2, 1]) + # Multiple cycles + self._assert_cycle({1: {2}, 2: {1}, 3: {4}, 4: {5}, 6: {7}, 7: {6}}, [1, 2, 1]) + # Cycle in the middle of the graph + self._assert_cycle({1: {2}, 2: {3}, 3: {2, 4}, 4: {5}}, [3, 2]) + + def test_calls_before_prepare(self): + ts = graphlib.TopologicalSorter() + + with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"): + ts.get_ready() + with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"): + ts.done(3) + with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"): + ts.is_active() + + 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_invalid_nodes_in_done(self): + ts = graphlib.TopologicalSorter() + ts.add(1, 2, 3, 4) + ts.add(2, 3, 4) + ts.prepare() + ts.get_ready() + + with self.assertRaisesRegex(ValueError, "node 2 was not passed out"): + ts.done(2) + with self.assertRaisesRegex(ValueError, r"node 24 was not added using add\(\)"): + ts.done(24) + + def test_done(self): + ts = graphlib.TopologicalSorter() + ts.add(1, 2, 3, 4) + ts.add(2, 3) + ts.prepare() + + self.assertEqual(ts.get_ready(), (3, 4)) + # If we don't mark anything as done, get_ready() returns nothing + self.assertEqual(ts.get_ready(), ()) + ts.done(3) + # Now 2 becomes available as 3 is done + self.assertEqual(ts.get_ready(), (2,)) + self.assertEqual(ts.get_ready(), ()) + ts.done(4) + ts.done(2) + # Only 1 is missing + self.assertEqual(ts.get_ready(), (1,)) + self.assertEqual(ts.get_ready(), ()) + ts.done(1) + self.assertEqual(ts.get_ready(), ()) + self.assertFalse(ts.is_active()) + + def test_is_active(self): + ts = graphlib.TopologicalSorter() + ts.add(1, 2) + ts.prepare() + + self.assertTrue(ts.is_active()) + self.assertEqual(ts.get_ready(), (2,)) + self.assertTrue(ts.is_active()) + ts.done(2) + self.assertTrue(ts.is_active()) + self.assertEqual(ts.get_ready(), (1,)) + self.assertTrue(ts.is_active()) + ts.done(1) + self.assertFalse(ts.is_active()) + + def test_not_hashable_nodes(self): + ts = graphlib.TopologicalSorter() + self.assertRaises(TypeError, ts.add, dict(), 1) + self.assertRaises(TypeError, ts.add, 1, dict()) + self.assertRaises(TypeError, ts.add, dict(), dict()) + + def test_order_of_insertion_does_not_matter_between_groups(self): + def get_groups(ts): + ts.prepare() + while ts.is_active(): + nodes = ts.get_ready() + ts.done(*nodes) + yield set(nodes) + + ts = graphlib.TopologicalSorter() + ts.add(3, 2, 1) + ts.add(1, 0) + ts.add(4, 5) + ts.add(6, 7) + ts.add(4, 7) + + ts2 = graphlib.TopologicalSorter() + ts2.add(1, 0) + ts2.add(3, 2, 1) + ts2.add(4, 7) + ts2.add(6, 7) + ts2.add(4, 5) + + self.assertEqual(list(get_groups(ts)), list(get_groups(ts2))) + + def test_static_order_does_not_change_with_the_hash_seed(self): + def check_order_with_hash_seed(seed): + code = """if 1: + import graphlib + ts = graphlib.TopologicalSorter() + ts.add('blech', 'bluch', 'hola') + ts.add('abcd', 'blech', 'bluch', 'a', 'b') + ts.add('a', 'a string', 'something', 'b') + ts.add('bluch', 'hola', 'abcde', 'a', 'b') + print(list(ts.static_order())) + """ + env = os.environ.copy() + # signal to assert_python not to do a copy + # of os.environ on its own + env["__cleanenv"] = True + env["PYTHONHASHSEED"] = str(seed) + out = assert_python_ok("-c", code, **env) + return out + + run1 = check_order_with_hash_seed(1234) + run2 = check_order_with_hash_seed(31415) + + self.assertNotEqual(run1, "") + self.assertNotEqual(run2, "") + self.assertEqual(run1, run2) diff --git a/Misc/NEWS.d/next/Library/2020-05-31-23-32-36.bpo-17005.JlRUGB.rst b/Misc/NEWS.d/next/Library/2020-05-31-23-32-36.bpo-17005.JlRUGB.rst new file mode 100644 index 0000000000000..0fd01fb623093 --- /dev/null +++ b/Misc/NEWS.d/next/Library/2020-05-31-23-32-36.bpo-17005.JlRUGB.rst @@ -0,0 +1,4 @@ +The topological sort functionality that was introduced initially in the +:mod:`functools` module has been moved to a new :mod:`graphlib` module to +better accommodate the new tools and keep the original scope of the +:mod:`functools` module. Patch by Pablo Galindo diff --git a/PCbuild/lib.pyproj b/PCbuild/lib.pyproj index 7ce88e5690b45..f0c51edb9d1ca 100644 --- a/PCbuild/lib.pyproj +++ b/PCbuild/lib.pyproj @@ -419,6 +419,7 @@ <Compile Include="getpass.py" /> <Compile Include="gettext.py" /> <Compile Include="glob.py" /> + <Compile Include="graphlib.py" /> <Compile Include="gzip.py" /> <Compile Include="hashlib.py" /> <Compile Include="heapq.py" />

1 0

Fix typo in "What's new in Python 3.9" (GH-20559)
by Lysandros Nikolaou 31 May '20

31 May '20

https://github.com/python/cpython/commit/491a3d3a75b656c8317d8ce343aea76797… commit: 491a3d3a75b656c8317d8ce343aea767978b946c branch: master author: Lysandros Nikolaou <lisandrosnik(a)gmail.com> committer: GitHub <noreply(a)github.com> date: 2020-05-31T16:28:46-07:00 summary: Fix typo in "What's new in Python 3.9" (GH-20559) Automerge-Triggered-By: @pablogsal files: M Doc/whatsnew/3.9.rst diff --git a/Doc/whatsnew/3.9.rst b/Doc/whatsnew/3.9.rst index 6ace7a4253f18..3d5cec6026add 100644 --- a/Doc/whatsnew/3.9.rst +++ b/Doc/whatsnew/3.9.rst @@ -156,7 +156,7 @@ back to the LL(1) parser using a command line switch (``-X oldparser``) or an environment variable (``PYTHONOLDPARSER=1``). See :pep:`617` for more details. (Contributed by Guido van Rossum, -Pablo Galindo and Lysandros Nikolau in :issue:`40334`.) +Pablo Galindo and Lysandros Nikolaou in :issue:`40334`.) Other Language Changes

1 0

bpo-40759: Deprecate the symbol module (GH-20364)
by Batuhan Taskaya 31 May '20

31 May '20

https://github.com/python/cpython/commit/cf88871d6a9c12e7b7e5f4d65abc2ec6e2… commit: cf88871d6a9c12e7b7e5f4d65abc2ec6e2fe952e branch: master author: Batuhan Taskaya <batuhanosmantaskaya(a)gmail.com> committer: GitHub <noreply(a)github.com> date: 2020-05-31T15:01:50-07:00 summary: bpo-40759: Deprecate the symbol module (GH-20364) Automerge-Triggered-By: @pablogsal files: A Misc/NEWS.d/next/Library/2020-05-24-23-52-35.bpo-40759.DdZdaw.rst M Doc/library/symbol.rst M Doc/whatsnew/3.9.rst M Lib/symbol.py diff --git a/Doc/library/symbol.rst b/Doc/library/symbol.rst index 44996936e2d28..d56600af29d6e 100644 --- a/Doc/library/symbol.rst +++ b/Doc/library/symbol.rst @@ -17,6 +17,11 @@ the definitions of the names in the context of the language grammar. The specific numeric values which the names map to may change between Python versions. +.. warning:: + + The symbol module is deprecated and will be removed in future versions of + Python. + This module also provides one additional data object: diff --git a/Doc/whatsnew/3.9.rst b/Doc/whatsnew/3.9.rst index 7f81074b2b55f..6ace7a4253f18 100644 --- a/Doc/whatsnew/3.9.rst +++ b/Doc/whatsnew/3.9.rst @@ -692,9 +692,10 @@ Deprecated Python versions it will raise a :exc:`TypeError` for all floats. (Contributed by Serhiy Storchaka in :issue:`37315`.) -* The :mod:`parser` module is deprecated and will be removed in future versions - of Python. For the majority of use cases, users can leverage the Abstract Syntax - Tree (AST) generation and compilation stage, using the :mod:`ast` module. +* The :mod:`parser` and :mod:`symbol` modules are deprecated and will be + removed in future versions of Python. For the majority of use cases, + users can leverage the Abstract Syntax Tree (AST) generation and compilation + stage, using the :mod:`ast` module. * Using :data:`NotImplemented` in a boolean context has been deprecated, as it is almost exclusively the result of incorrect rich comparator diff --git a/Lib/symbol.py b/Lib/symbol.py index 36e0eec7ac1f5..aaac8c914431b 100644 --- a/Lib/symbol.py +++ b/Lib/symbol.py @@ -11,6 +11,15 @@ # # make regen-symbol +import warnings + +warnings.warn( + "The symbol module is deprecated and will be removed " + "in future versions of Python", + DeprecationWarning, + stacklevel=2, +) + #--start constants-- single_input = 256 file_input = 257 diff --git a/Misc/NEWS.d/next/Library/2020-05-24-23-52-35.bpo-40759.DdZdaw.rst b/Misc/NEWS.d/next/Library/2020-05-24-23-52-35.bpo-40759.DdZdaw.rst new file mode 100644 index 0000000000000..e77da3ac3dfa9 --- /dev/null +++ b/Misc/NEWS.d/next/Library/2020-05-24-23-52-35.bpo-40759.DdZdaw.rst @@ -0,0 +1 @@ +Deprecate the :mod:`symbol` module.

1 0

bpo-40755: Add rich comparisons to Counter (GH-20548)
by Raymond Hettinger 31 May '20

31 May '20

https://github.com/python/cpython/commit/b7d79b4f36787874128c439d38397fe95c… commit: b7d79b4f36787874128c439d38397fe95c48429b branch: master author: Raymond Hettinger <rhettinger(a)users.noreply.github.com> committer: GitHub <noreply(a)github.com> date: 2020-05-31T14:57:42-07:00 summary: bpo-40755: Add rich comparisons to Counter (GH-20548) files: A Misc/NEWS.d/next/Library/2020-05-30-18-48-58.bpo-40755.IyOe2J.rst D Misc/NEWS.d/next/Library/2020-05-23-18-24-13.bpo-22533.k64XGo.rst M Doc/library/collections.rst M Lib/collections/__init__.py M Lib/test/test_collections.py diff --git a/Doc/library/collections.rst b/Doc/library/collections.rst index ea2b420292eb0..f538da5e1c9fa 100644 --- a/Doc/library/collections.rst +++ b/Doc/library/collections.rst @@ -290,47 +290,6 @@ For example:: >>> sorted(c.elements()) ['a', 'a', 'a', 'a', 'b', 'b'] - .. method:: isdisjoint(other) - - True if none of the elements in *self* overlap with those in *other*. - Negative or missing counts are ignored. - Logically equivalent to: ``not (+self) & (+other)`` - - .. versionadded:: 3.10 - - .. method:: isequal(other) - - Test whether counts agree exactly. - Negative or missing counts are treated as zero. - - This method works differently than the inherited :meth:`__eq__` method - which treats negative or missing counts as distinct from zero:: - - >>> Counter(a=1, b=0).isequal(Counter(a=1)) - True - >>> Counter(a=1, b=0) == Counter(a=1) - False - - Logically equivalent to: ``+self == +other`` - - .. versionadded:: 3.10 - - .. method:: issubset(other) - - True if the counts in *self* are less than or equal to those in *other*. - Negative or missing counts are treated as zero. - Logically equivalent to: ``not self - (+other)`` - - .. versionadded:: 3.10 - - .. method:: issuperset(other) - - True if the counts in *self* are greater than or equal to those in *other*. - Negative or missing counts are treated as zero. - Logically equivalent to: ``not other - (+self)`` - - .. versionadded:: 3.10 - .. method:: most_common([n]) Return a list of the *n* most common elements and their counts from the @@ -369,6 +328,19 @@ For example:: instead of replacing them. Also, the *iterable* is expected to be a sequence of elements, not a sequence of ``(key, value)`` pairs. +Counters support rich comparison operators for equality, subset, and +superset relationships: ``==``, ``!=``, ``<``, ``<=``, ``>``, ``>=``. +All of those tests treat missing elements as having zero counts so that +``Counter(a=1) == Counter(a=1, b=0)`` returns true. + +.. versionadded:: 3.10 + Rich comparison operations we were added + +.. versionchanged:: 3.10 + In equality tests, missing elements are treated as having zero counts. + Formerly, ``Counter(a=3)`` and ``Counter(a=3, b=0)`` were considered + distinct. + Common patterns for working with :class:`Counter` objects:: sum(c.values()) # total of all counts diff --git a/Lib/collections/__init__.py b/Lib/collections/__init__.py index 55fb46c9bc157..2acf67289f225 100644 --- a/Lib/collections/__init__.py +++ b/Lib/collections/__init__.py @@ -691,6 +691,42 @@ def __delitem__(self, elem): if elem in self: super().__delitem__(elem) + def __eq__(self, other): + 'True if all counts agree. Missing counts are treated as zero.' + if not isinstance(other, Counter): + return NotImplemented + return all(self[e] == other[e] for c in (self, other) for e in c) + + def __ne__(self, other): + 'True if any counts disagree. Missing counts are treated as zero.' + if not isinstance(other, Counter): + return NotImplemented + return not self == other + + def __le__(self, other): + 'True if all counts in self are a subset of those in other.' + if not isinstance(other, Counter): + return NotImplemented + return all(self[e] <= other[e] for c in (self, other) for e in c) + + def __lt__(self, other): + 'True if all counts in self are a proper subset of those in other.' + if not isinstance(other, Counter): + return NotImplemented + return self <= other and self != other + + def __ge__(self, other): + 'True if all counts in self are a superset of those in other.' + if not isinstance(other, Counter): + return NotImplemented + return all(self[e] >= other[e] for c in (self, other) for e in c) + + def __gt__(self, other): + 'True if all counts in self are a proper superset of those in other.' + if not isinstance(other, Counter): + return NotImplemented + return self >= other and self != other + def __repr__(self): if not self: return '%s()' % self.__class__.__name__ @@ -886,92 +922,6 @@ def __iand__(self, other): self[elem] = other_count return self._keep_positive() - def isequal(self, other): - ''' Test whether counts agree exactly. - - Negative or missing counts are treated as zero. - - This is different than the inherited __eq__() method which - treats negative or missing counts as distinct from zero: - - >>> Counter(a=1, b=0).isequal(Counter(a=1)) - True - >>> Counter(a=1, b=0) == Counter(a=1) - False - - Logically equivalent to: +self == +other - ''' - if not isinstance(other, Counter): - other = Counter(other) - for elem in set(self) | set(other): - left = self[elem] - right = other[elem] - if left == right: - continue - if left < 0: - left = 0 - if right < 0: - right = 0 - if left != right: - return False - return True - - def issubset(self, other): - '''True if the counts in self are less than or equal to those in other. - - Negative or missing counts are treated as zero. - - Logically equivalent to: not self - (+other) - ''' - if not isinstance(other, Counter): - other = Counter(other) - for elem, count in self.items(): - other_count = other[elem] - if other_count < 0: - other_count = 0 - if count > other_count: - return False - return True - - def issuperset(self, other): - '''True if the counts in self are greater than or equal to those in other. - - Negative or missing counts are treated as zero. - - Logically equivalent to: not other - (+self) - ''' - if not isinstance(other, Counter): - other = Counter(other) - return other.issubset(self) - - def isdisjoint(self, other): - '''True if none of the elements in self overlap with those in other. - - Negative or missing counts are ignored. - - Logically equivalent to: not (+self) & (+other) - ''' - if not isinstance(other, Counter): - other = Counter(other) - for elem, count in self.items(): - if count > 0 and other[elem] > 0: - return False - return True - - # Rich comparison operators for multiset subset and superset tests - # have been deliberately omitted due to semantic conflicts with the - # existing inherited dict equality method. Subset and superset - # semantics ignore zero counts and require that p⊆q ∧ p⊇q ⇔ p=q; - # however, that would not be the case for p=Counter(a=1, b=0) - # and q=Counter(a=1) where the dictionaries are not equal. - - def _omitted(self, other): - raise TypeError( - 'Rich comparison operators have been deliberately omitted. ' - 'Use the isequal(), issubset(), and issuperset() methods instead.') - - __lt__ = __le__ = __gt__ = __ge__ = __lt__ = _omitted - ######################################################################## ### ChainMap diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py index 8d80e88673b89..7c7f8655b0fbd 100644 --- a/Lib/test/test_collections.py +++ b/Lib/test/test_collections.py @@ -2123,29 +2123,6 @@ def test_multiset_operations(self): set_result = setop(set(p.elements()), set(q.elements())) self.assertEqual(counter_result, dict.fromkeys(set_result, 1)) - def test_subset_superset_not_implemented(self): - # Verify that multiset comparison operations are not implemented. - - # These operations were intentionally omitted because multiset - # comparison semantics conflict with existing dict equality semantics. - - # For multisets, we would expect that if p<=q and p>=q are both true, - # then p==q. However, dict equality semantics require that p!=q when - # one of sets contains an element with a zero count and the other - # doesn't. - - p = Counter(a=1, b=0) - q = Counter(a=1, c=0) - self.assertNotEqual(p, q) - with self.assertRaises(TypeError): - p < q - with self.assertRaises(TypeError): - p <= q - with self.assertRaises(TypeError): - p > q - with self.assertRaises(TypeError): - p >= q - def test_inplace_operations(self): elements = 'abcd' for i in range(1000): @@ -2234,49 +2211,32 @@ def test_multiset_operations_equivalent_to_set_operations(self): self.assertEqual(set(cp - cq), sp - sq) self.assertEqual(set(cp | cq), sp | sq) self.assertEqual(set(cp & cq), sp & sq) - self.assertEqual(cp.isequal(cq), sp == sq) - self.assertEqual(cp.issubset(cq), sp.issubset(sq)) - self.assertEqual(cp.issuperset(cq), sp.issuperset(sq)) - self.assertEqual(cp.isdisjoint(cq), sp.isdisjoint(sq)) - - def test_multiset_equal(self): - self.assertTrue(Counter(a=3, b=2, c=0).isequal('ababa')) - self.assertFalse(Counter(a=3, b=2).isequal('babab')) - - def test_multiset_subset(self): - self.assertTrue(Counter(a=3, b=2, c=0).issubset('ababa')) - self.assertFalse(Counter(a=3, b=2).issubset('babab')) - - def test_multiset_superset(self): - self.assertTrue(Counter(a=3, b=2, c=0).issuperset('aab')) - self.assertFalse(Counter(a=3, b=2, c=0).issuperset('aabd')) - - def test_multiset_disjoint(self): - self.assertTrue(Counter(a=3, b=2, c=0).isdisjoint('cde')) - self.assertFalse(Counter(a=3, b=2, c=0).isdisjoint('bcd')) - - def test_multiset_predicates_with_negative_counts(self): - # Multiset predicates run on the output of the elements() method, - # meaning that zero counts and negative counts are ignored. - # The tests below confirm that we get that same results as the - # tests above, even after a negative count has been included - # in either *self* or *other*. - self.assertTrue(Counter(a=3, b=2, c=0, d=-1).isequal('ababa')) - self.assertFalse(Counter(a=3, b=2, d=-1).isequal('babab')) - self.assertTrue(Counter(a=3, b=2, c=0, d=-1).issubset('ababa')) - self.assertFalse(Counter(a=3, b=2, d=-1).issubset('babab')) - self.assertTrue(Counter(a=3, b=2, c=0, d=-1).issuperset('aab')) - self.assertFalse(Counter(a=3, b=2, c=0, d=-1).issuperset('aabd')) - self.assertTrue(Counter(a=3, b=2, c=0, d=-1).isdisjoint('cde')) - self.assertFalse(Counter(a=3, b=2, c=0, d=-1).isdisjoint('bcd')) - self.assertTrue(Counter(a=3, b=2, c=0, d=-1).isequal(Counter(a=3, b=2, c=-1))) - self.assertFalse(Counter(a=3, b=2, d=-1).isequal(Counter(a=2, b=3, c=-1))) - self.assertTrue(Counter(a=3, b=2, c=0, d=-1).issubset(Counter(a=3, b=2, c=-1))) - self.assertFalse(Counter(a=3, b=2, d=-1).issubset(Counter(a=2, b=3, c=-1))) - self.assertTrue(Counter(a=3, b=2, c=0, d=-1).issuperset(Counter(a=2, b=1, c=-1))) - self.assertFalse(Counter(a=3, b=2, c=0, d=-1).issuperset(Counter(a=2, b=1, c=-1, d=1))) - self.assertTrue(Counter(a=3, b=2, c=0, d=-1).isdisjoint(Counter(c=1, d=2, e=3, f=-1))) - self.assertFalse(Counter(a=3, b=2, c=0, d=-1).isdisjoint(Counter(b=1, c=1, d=1, e=-1))) + self.assertEqual(cp == cq, sp == sq) + self.assertEqual(cp != cq, sp != sq) + self.assertEqual(cp <= cq, sp <= sq) + self.assertEqual(cp >= cq, sp >= sq) + self.assertEqual(cp < cq, sp < sq) + self.assertEqual(cp > cq, sp > sq) + + def test_eq(self): + self.assertEqual(Counter(a=3, b=2, c=0), Counter('ababa')) + self.assertNotEqual(Counter(a=3, b=2), Counter('babab')) + + def test_le(self): + self.assertTrue(Counter(a=3, b=2, c=0) <= Counter('ababa')) + self.assertFalse(Counter(a=3, b=2) <= Counter('babab')) + + def test_lt(self): + self.assertTrue(Counter(a=3, b=1, c=0) < Counter('ababa')) + self.assertFalse(Counter(a=3, b=2, c=0) < Counter('ababa')) + + def test_ge(self): + self.assertTrue(Counter(a=2, b=1, c=0) >= Counter('aab')) + self.assertFalse(Counter(a=3, b=2, c=0) >= Counter('aabd')) + + def test_gt(self): + self.assertTrue(Counter(a=3, b=2, c=0) > Counter('aab')) + self.assertFalse(Counter(a=2, b=1, c=0) > Counter('aab')) ################################################################################ diff --git a/Misc/NEWS.d/next/Library/2020-05-23-18-24-13.bpo-22533.k64XGo.rst b/Misc/NEWS.d/next/Library/2020-05-23-18-24-13.bpo-22533.k64XGo.rst deleted file mode 100644 index 737162f7e12b2..0000000000000 --- a/Misc/NEWS.d/next/Library/2020-05-23-18-24-13.bpo-22533.k64XGo.rst +++ /dev/null @@ -1,2 +0,0 @@ -Add multiset comparison methods to collections.Counter(): isequal(), -issubset(), issuperset(), and isdisjoint(). diff --git a/Misc/NEWS.d/next/Library/2020-05-30-18-48-58.bpo-40755.IyOe2J.rst b/Misc/NEWS.d/next/Library/2020-05-30-18-48-58.bpo-40755.IyOe2J.rst new file mode 100644 index 0000000000000..be5653ea58f27 --- /dev/null +++ b/Misc/NEWS.d/next/Library/2020-05-30-18-48-58.bpo-40755.IyOe2J.rst @@ -0,0 +1 @@ +Add rich comparisons to collections.Counter().

1 0

Fix asyncio.to_thread() documented return type (GH-20547)
by Kyle Stanley 31 May '20

31 May '20

https://github.com/python/cpython/commit/2b201369b435a4266bda5b895e3b615dbe… commit: 2b201369b435a4266bda5b895e3b615dbe28ea6e branch: master author: Kyle Stanley <aeros167(a)gmail.com> committer: GitHub <noreply(a)github.com> date: 2020-05-31T00:07:04-07:00 summary: Fix asyncio.to_thread() documented return type (GH-20547) When I wrote the documentation for `asyncio.to_thread()`, I mistakenly assumed that `return await loop.run_in_executor(...)` within an async def function would return a Future. In reality, it returns a coroutine. This likely won't affect typical usage of `asyncio.to_thread()`, but it's important for the documentation to be correct here. In general, we also tend to avoid returning futures from high-level APIs in asyncio. files: M Doc/library/asyncio-task.rst M Lib/asyncio/threads.py diff --git a/Doc/library/asyncio-task.rst b/Doc/library/asyncio-task.rst index 847363b134a7a..21824ca537f77 100644 --- a/Doc/library/asyncio-task.rst +++ b/Doc/library/asyncio-task.rst @@ -614,8 +614,7 @@ Running in Threads allowing context variables from the event loop thread to be accessed in the separate thread. - Return an :class:`asyncio.Future` which represents the eventual result of - *func*. + Return a coroutine that can be awaited to get the eventual result of *func*. This coroutine function is primarily intended to be used for executing IO-bound functions/methods that would otherwise block the event loop if diff --git a/Lib/asyncio/threads.py b/Lib/asyncio/threads.py index 51e0ba95d822e..34b7513a42090 100644 --- a/Lib/asyncio/threads.py +++ b/Lib/asyncio/threads.py @@ -17,7 +17,7 @@ async def to_thread(func, /, *args, **kwargs): allowing context variables from the main thread to be accessed in the separate thread. - Return an asyncio.Future which represents the eventual result of *func*. + Return a coroutine that can be awaited to get the eventual result of *func*. """ loop = events.get_running_loop() ctx = contextvars.copy_context()

1 0

bpo-40829: Add a what's new entry about deprecation of shuffle's random parameter (GH-20541)
by Batuhan Taskaya 30 May '20

30 May '20

https://github.com/python/cpython/commit/007bb06a2de9e64fa978f5dd9131d01002… commit: 007bb06a2de9e64fa978f5dd9131d0100227b4cf branch: master author: Batuhan Taskaya <batuhanosmantaskaya(a)gmail.com> committer: GitHub <noreply(a)github.com> date: 2020-05-30T15:15:06-07:00 summary: bpo-40829: Add a what's new entry about deprecation of shuffle's random parameter (GH-20541) files: M Doc/whatsnew/3.9.rst diff --git a/Doc/whatsnew/3.9.rst b/Doc/whatsnew/3.9.rst index 6c3cbbe641b57..7f81074b2b55f 100644 --- a/Doc/whatsnew/3.9.rst +++ b/Doc/whatsnew/3.9.rst @@ -761,6 +761,9 @@ Deprecated `parso`_. (Contributed by Carl Meyer in :issue:`40360`.) +* The *random* parameter of :func:`random.shuffle` has been deprecated. + (Contributed by Raymond Hettinger in :issue:`40465`) + .. _LibCST: https://libcst.readthedocs.io/ .. _parso: https://parso.readthedocs.io/

1 0

bpo-40061: Fix a possible refleak in _asynciomodule.c (GH-19748)
by Zackery Spytz 30 May '20

30 May '20

https://github.com/python/cpython/commit/7b78e7f9fd77bb3280ee39fb74b86772a7… commit: 7b78e7f9fd77bb3280ee39fb74b86772a7d46a70 branch: master author: Zackery Spytz <zspytz(a)gmail.com> committer: GitHub <noreply(a)github.com> date: 2020-05-30T01:22:02-07:00 summary: bpo-40061: Fix a possible refleak in _asynciomodule.c (GH-19748) tup should be decrefed in the unlikely event of a PyList_New() failure. files: M Modules/_asynciomodule.c diff --git a/Modules/_asynciomodule.c b/Modules/_asynciomodule.c index 0608c40f6c339..0454f9c6824bf 100644 --- a/Modules/_asynciomodule.c +++ b/Modules/_asynciomodule.c @@ -710,6 +710,7 @@ future_add_done_callback(FutureObj *fut, PyObject *arg, PyObject *ctx) else { fut->fut_callbacks = PyList_New(1); if (fut->fut_callbacks == NULL) { + Py_DECREF(tup); return NULL; }

1 0

bpo-40798: Generate a different message for already removed elements (GH-20483)
by Miss Islington (bot) 30 May '20

30 May '20

https://github.com/python/cpython/commit/ba1c2c85b39fbcb31584c20f8a63fb87f9… commit: ba1c2c85b39fbcb31584c20f8a63fb87f9cb9c02 branch: 3.8 author: Miss Islington (bot) <31488909+miss-islington(a)users.noreply.github.com> committer: GitHub <noreply(a)github.com> date: 2020-05-30T00:54:58-07:00 summary: bpo-40798: Generate a different message for already removed elements (GH-20483) (cherry picked from commit 735d902b363b759df9ff00e58bbf4f7e2bde78cd) Co-authored-by: Florian Dahlitz <f2dahlitz(a)freenet.de> files: M Doc/tools/extensions/pyspecific.py M Doc/tools/templates/dummy.html diff --git a/Doc/tools/extensions/pyspecific.py b/Doc/tools/extensions/pyspecific.py index 2d95612415942..a128c705847e9 100644 --- a/Doc/tools/extensions/pyspecific.py +++ b/Doc/tools/extensions/pyspecific.py @@ -311,7 +311,8 @@ class DeprecatedRemoved(Directive): final_argument_whitespace = True option_spec = {} - _label = 'Deprecated since version {deprecated}, will be removed in version {removed}' + _deprecated_label = 'Deprecated since version {deprecated}, will be removed in version {removed}' + _removed_label = 'Deprecated since version {deprecated}, removed in version {removed}' def run(self): node = addnodes.versionmodified() @@ -319,7 +320,15 @@ def run(self): node['type'] = 'deprecated-removed' version = (self.arguments[0], self.arguments[1]) node['version'] = version - label = translators['sphinx'].gettext(self._label) + env = self.state.document.settings.env + current_version = tuple(int(e) for e in env.config.version.split('.')) + removed_version = tuple(int(e) for e in self.arguments[1].split('.')) + if current_version < removed_version: + label = self._deprecated_label + else: + label = self._removed_label + + label = translators['sphinx'].gettext(label) text = label.format(deprecated=self.arguments[0], removed=self.arguments[1]) if len(self.arguments) == 3: inodes, messages = self.state.inline_text(self.arguments[2], diff --git a/Doc/tools/templates/dummy.html b/Doc/tools/templates/dummy.html index 8d94137b01b51..68ae3ad148ec2 100644 --- a/Doc/tools/templates/dummy.html +++ b/Doc/tools/templates/dummy.html @@ -5,3 +5,4 @@ {% trans %}CPython implementation detail:{% endtrans %} {% trans %}Deprecated since version {deprecated}, will be removed in version {removed}{% endtrans %} +{% trans %}Deprecated since version {deprecated}, removed in version {removed}{% endtrans %}

1 0

bpo-40798: Generate a different message for already removed elements (GH-20483)
by Miss Islington (bot) 30 May '20

30 May '20

https://github.com/python/cpython/commit/a9dbae434f26b2c419a1cd0a8233143f40… commit: a9dbae434f26b2c419a1cd0a8233143f40fd00db branch: 3.7 author: Miss Islington (bot) <31488909+miss-islington(a)users.noreply.github.com> committer: GitHub <noreply(a)github.com> date: 2020-05-30T00:52:27-07:00 summary: bpo-40798: Generate a different message for already removed elements (GH-20483) (cherry picked from commit 735d902b363b759df9ff00e58bbf4f7e2bde78cd) Co-authored-by: Florian Dahlitz <f2dahlitz(a)freenet.de> files: M Doc/tools/extensions/pyspecific.py M Doc/tools/templates/dummy.html diff --git a/Doc/tools/extensions/pyspecific.py b/Doc/tools/extensions/pyspecific.py index 466e84c26147c..3b6fa90059160 100644 --- a/Doc/tools/extensions/pyspecific.py +++ b/Doc/tools/extensions/pyspecific.py @@ -236,7 +236,8 @@ class DeprecatedRemoved(Directive): final_argument_whitespace = True option_spec = {} - _label = 'Deprecated since version {deprecated}, will be removed in version {removed}' + _deprecated_label = 'Deprecated since version {deprecated}, will be removed in version {removed}' + _removed_label = 'Deprecated since version {deprecated}, removed in version {removed}' def run(self): node = addnodes.versionmodified() @@ -244,7 +245,15 @@ def run(self): node['type'] = 'deprecated-removed' version = (self.arguments[0], self.arguments[1]) node['version'] = version - label = translators['sphinx'].gettext(self._label) + env = self.state.document.settings.env + current_version = tuple(int(e) for e in env.config.version.split('.')) + removed_version = tuple(int(e) for e in self.arguments[1].split('.')) + if current_version < removed_version: + label = self._deprecated_label + else: + label = self._removed_label + + label = translators['sphinx'].gettext(label) text = label.format(deprecated=self.arguments[0], removed=self.arguments[1]) if len(self.arguments) == 3: inodes, messages = self.state.inline_text(self.arguments[2], diff --git a/Doc/tools/templates/dummy.html b/Doc/tools/templates/dummy.html index 8d94137b01b51..68ae3ad148ec2 100644 --- a/Doc/tools/templates/dummy.html +++ b/Doc/tools/templates/dummy.html @@ -5,3 +5,4 @@ {% trans %}CPython implementation detail:{% endtrans %} {% trans %}Deprecated since version {deprecated}, will be removed in version {removed}{% endtrans %} +{% trans %}Deprecated since version {deprecated}, removed in version {removed}{% endtrans %}

1 0

bpo-40798: Generate a different message for already removed elements (GH-20483)
by Florian Dahlitz 30 May '20

30 May '20

https://github.com/python/cpython/commit/735d902b363b759df9ff00e58bbf4f7e2b… commit: 735d902b363b759df9ff00e58bbf4f7e2bde78cd branch: master author: Florian Dahlitz <f2dahlitz(a)freenet.de> committer: GitHub <noreply(a)github.com> date: 2020-05-30T09:47:32+02:00 summary: bpo-40798: Generate a different message for already removed elements (GH-20483) files: M Doc/tools/extensions/pyspecific.py M Doc/tools/templates/dummy.html diff --git a/Doc/tools/extensions/pyspecific.py b/Doc/tools/extensions/pyspecific.py index bc51555fa0512..46064fa3b6b00 100644 --- a/Doc/tools/extensions/pyspecific.py +++ b/Doc/tools/extensions/pyspecific.py @@ -311,7 +311,8 @@ class DeprecatedRemoved(Directive): final_argument_whitespace = True option_spec = {} - _label = 'Deprecated since version {deprecated}, will be removed in version {removed}' + _deprecated_label = 'Deprecated since version {deprecated}, will be removed in version {removed}' + _removed_label = 'Deprecated since version {deprecated}, removed in version {removed}' def run(self): node = addnodes.versionmodified() @@ -319,7 +320,15 @@ def run(self): node['type'] = 'deprecated-removed' version = (self.arguments[0], self.arguments[1]) node['version'] = version - label = translators['sphinx'].gettext(self._label) + env = self.state.document.settings.env + current_version = tuple(int(e) for e in env.config.version.split('.')) + removed_version = tuple(int(e) for e in self.arguments[1].split('.')) + if current_version < removed_version: + label = self._deprecated_label + else: + label = self._removed_label + + label = translators['sphinx'].gettext(label) text = label.format(deprecated=self.arguments[0], removed=self.arguments[1]) if len(self.arguments) == 3: inodes, messages = self.state.inline_text(self.arguments[2], diff --git a/Doc/tools/templates/dummy.html b/Doc/tools/templates/dummy.html index 8d94137b01b51..68ae3ad148ec2 100644 --- a/Doc/tools/templates/dummy.html +++ b/Doc/tools/templates/dummy.html @@ -5,3 +5,4 @@ {% trans %}CPython implementation detail:{% endtrans %} {% trans %}Deprecated since version {deprecated}, will be removed in version {removed}{% endtrans %} +{% trans %}Deprecated since version {deprecated}, removed in version {removed}{% endtrans %}

1 0