We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
can't build docs due to multiple targets for cross-reference
I can't successfully build the docs using `python setup.py docs` with Sphinx 1.5.5 due to the following error

```
Warning, treated as error:
/home/thomas/gitrepos/coala/coalib/core/DependencyTracker.py:docstring of coalib.core.DependencyTracker.DependencyTracker.check_circular_dependencies:None: WARNING: more than one target found for cross-reference 'CircularDependencyError': coalib.collecting.Dependencies.CircularDependencyError, coalib.core.CircularDependencyError.CircularDependencyError
```

I had a look at the implementation of the two CircularDependenyError classes and they are quite similar, can't they be merged?

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `coalib/core/Graphs.py`
Content:
```
1 from coalib.core.CircularDependencyError import CircularDependencyError
2 
3 
4 def traverse_graph(start_nodes, get_successive_nodes,
5                    run_on_edge=lambda prev, nxt: None):
6     """
7     Traverses all edges of a directed, possibly disconnected graph once.
8     Detects cyclic graphs by raising a ``CircularDependencyError``.
9 
10     >>> graph = {1: [2], 2: [3, 4], 5: [3], 3: [6]}
11     >>> def get_successive_nodes(node):
12     ...     return graph.get(node, [])
13     >>> edges = set()
14     >>> def append_to_edges(prev, nxt):
15     ...     edges.add((prev, nxt))
16     >>> traverse_graph([1, 5], get_successive_nodes, append_to_edges)
17     >>> sorted(edges)
18     [(1, 2), (2, 3), (2, 4), (3, 6), (5, 3)]
19 
20     You can also use this function to detect cyclic graphs:
21 
22     >>> graph = {1: [2], 2: [3], 3: [1]}
23     >>> traverse_graph([1], get_successive_nodes)
24     Traceback (most recent call last):
25      ...
26     coalib.core.CircularDependencyError.CircularDependencyError: ...
27 
28     :param start_nodes:
29         The nodes where to start traversing the graph.
30     :param get_successive_nodes:
31         A callable that takes in a node and returns an iterable of nodes to
32         traverse next.
33     :param run_on_edge:
34         A callable that is run on each edge during traversing. Takes in two
35         parameters, the previous- and next-node which form an edge. The default
36         is an empty function.
37     :raises CircularDependencyError:
38         Raised when the graph is cyclic.
39     """
40     path = set()
41     visited_nodes = set()
42 
43     def visit(node):
44         if node not in visited_nodes:
45             visited_nodes.add(node)
46             path.add(node)
47 
48             for subnode in get_successive_nodes(node):
49                 run_on_edge(node, subnode)
50 
51                 if subnode in path:
52                     raise CircularDependencyError(subnode)
53 
54                 visit(subnode)
55 
56             path.remove(node)
57 
58     for node in start_nodes:
59         visit(node)
60
```

Path: `coalib/core/DependencyTracker.py`
Content:
```
1 from itertools import chain
2 
3 from coalib.core.Graphs import traverse_graph
4 
5 
6 class DependencyTracker:
7     """
8     A ``DependencyTracker`` allows to register and manage dependencies between
9     objects.
10 
11     This class uses a directed graph to track relations.
12 
13     Add a dependency relation between two objects:
14 
15     >>> object1 = object()
16     >>> object2 = object()
17     >>> tracker = DependencyTracker()
18     >>> tracker.add(object2, object1)
19 
20     This would define that ``object1`` is dependent on ``object2``.
21 
22     If you define that ``object2`` has its dependency duty fulfilled, you can
23     resolve it:
24 
25     >>> resolved = tracker.resolve(object2)
26     >>> resolved
27     {<object object at ...>}
28     >>> resolved_object = resolved.pop()
29     >>> resolved_object is object1
30     True
31 
32     This returns all objects that are now freed, meaning they have no
33     dependencies any more.
34 
35     >>> object3 = object()
36     >>> tracker.add(object2, object1)
37     >>> tracker.add(object3, object1)
38     >>> tracker.resolve(object2)
39     set()
40     >>> tracker.resolve(object3)
41     {<object object at ...>}
42 
43     The ones who instantiate a ``DependencyTracker`` are responsible for
44     resolving dependencies in the right order. Dependencies which are itself
45     dependent will be forcefully resolved and removed from their according
46     dependencies too.
47     """
48 
49     def __init__(self):
50         self._dependency_dict = {}
51 
52     def get_dependants(self, dependency):
53         """
54         Returns all immediate dependants for the given dependency.
55 
56         >>> tracker = DependencyTracker()
57         >>> tracker.add(0, 1)
58         >>> tracker.add(0, 2)
59         >>> tracker.add(1, 3)
60         >>> tracker.get_dependants(0)
61         {1, 2}
62         >>> tracker.get_dependants(1)
63         {3}
64         >>> tracker.get_dependants(2)
65         set()
66 
67         :param dependency:
68             The dependency to retrieve all dependants from.
69         :return:
70             A set of dependants.
71         """
72         try:
73             return set(self._dependency_dict[dependency])
74         except KeyError:
75             return set()
76 
77     def get_dependencies(self, dependant):
78         """
79         Returns all immediate dependencies of a given dependant.
80 
81         >>> tracker = DependencyTracker()
82         >>> tracker.add(0, 1)
83         >>> tracker.add(0, 2)
84         >>> tracker.add(1, 2)
85         >>> tracker.get_dependencies(0)
86         set()
87         >>> tracker.get_dependencies(1)
88         {0}
89         >>> tracker.get_dependencies(2)
90         {0, 1}
91 
92         :param dependant:
93             The dependant to retrieve all dependencies from.
94         :return:
95             A set of dependencies.
96         """
97         return set(
98             dependency
99             for dependency, dependants in self._dependency_dict.items()
100             if dependant in dependants)
101 
102     def get_all_dependants(self, dependency):
103         """
104         Returns a set of all dependants of the given dependency, even
105         indirectly related ones.
106 
107         >>> tracker = DependencyTracker()
108         >>> tracker.add(0, 1)
109         >>> tracker.add(1, 2)
110         >>> tracker.get_all_dependants(0)
111         {1, 2}
112 
113         :param dependency:
114             The dependency to get all dependants for.
115         :return:
116             A set of dependants.
117         """
118         dependants = set()
119 
120         def append_to_dependants(prev, nxt):
121             dependants.add(nxt)
122 
123         traverse_graph(
124             [dependency],
125             lambda node: self._dependency_dict.get(node, frozenset()),
126             append_to_dependants)
127 
128         return dependants
129 
130     def get_all_dependencies(self, dependant):
131         """
132         Returns a set of all dependencies of the given dependants, even
133         indirectly related ones.
134 
135         >>> tracker = DependencyTracker()
136         >>> tracker.add(0, 1)
137         >>> tracker.add(1, 2)
138         >>> tracker.get_all_dependencies(2)
139         {0, 1}
140 
141         :param dependant:
142             The dependant to get all dependencies for.
143         :return:
144             A set of dependencies.
145         """
146         dependencies = set()
147 
148         def append_to_dependencies(prev, nxt):
149             dependencies.add(nxt)
150 
151         traverse_graph(
152             [dependant],
153             lambda node:
154                 {dependency
155                  for dependency, dependants in self._dependency_dict.items()
156                  if node in dependants},
157             append_to_dependencies)
158 
159         return dependencies
160 
161     @property
162     def dependants(self):
163         """
164         Returns a set of all registered dependants.
165 
166         >>> tracker = DependencyTracker()
167         >>> tracker.add(0, 1)
168         >>> tracker.add(0, 2)
169         >>> tracker.add(1, 3)
170         >>> tracker.dependants
171         {1, 2, 3}
172         """
173         return set(chain.from_iterable(self._dependency_dict.values()))
174 
175     @property
176     def dependencies(self):
177         """
178         Returns a set of all registered dependencies.
179 
180         >>> tracker = DependencyTracker()
181         >>> tracker.add(0, 1)
182         >>> tracker.add(0, 2)
183         >>> tracker.add(1, 3)
184         >>> tracker.dependencies
185         {0, 1}
186         """
187         return set(self._dependency_dict.keys())
188 
189     def __iter__(self):
190         """
191         Returns an iterator that iterates over all dependency relations.
192 
193         >>> tracker = DependencyTracker()
194         >>> tracker.add(0, 1)
195         >>> tracker.add(0, 2)
196         >>> tracker.add(1, 2)
197         >>> for dependency, dependant in sorted(tracker):
198         ...     print(dependency, '->', dependant)
199         0 -> 1
200         0 -> 2
201         1 -> 2
202         """
203         return ((dependency, dependant)
204                 for dependency, dependants in self._dependency_dict.items()
205                 for dependant in dependants)
206 
207     def add(self, dependency, dependant):
208         """
209         Add a dependency relation.
210 
211         This function does not check for circular dependencies.
212 
213         >>> tracker = DependencyTracker()
214         >>> tracker.add(0, 1)
215         >>> tracker.add(0, 2)
216         >>> tracker.resolve(0)
217         {1, 2}
218 
219         :param dependency:
220             The object that is the dependency.
221         :param dependant:
222             The object that is the dependant.
223         """
224         if dependency not in self._dependency_dict:
225             self._dependency_dict[dependency] = set()
226 
227         self._dependency_dict[dependency].add(dependant)
228 
229     def resolve(self, dependency):
230         """
231         Resolves all dependency-relations from the given dependency, and frees
232         and returns dependants with no more dependencies. If the given
233         dependency is itself a dependant, all those relations are also removed.
234 
235         >>> tracker = DependencyTracker()
236         >>> tracker.add(0, 1)
237         >>> tracker.add(0, 2)
238         >>> tracker.add(2, 3)
239         >>> tracker.resolve(0)
240         {1, 2}
241         >>> tracker.resolve(2)
242         {3}
243         >>> tracker.resolve(2)
244         set()
245 
246         :param dependency:
247             The dependency.
248         :return:
249             Returns a set of dependants whose dependencies were all resolved.
250         """
251         # Check if dependency has itself dependencies which aren't resolved,
252         # these need to be removed too. This operation does not free any
253         # dependencies.
254         dependencies_to_remove = []
255         for tracked_dependency, dependants in self._dependency_dict.items():
256             if dependency in dependants:
257                 dependants.remove(dependency)
258 
259                 # If dependants set is now empty, schedule dependency for
260                 # removal from dependency_dict.
261                 if not dependants:
262                     dependencies_to_remove.append(tracked_dependency)
263 
264         for tracked_dependency in dependencies_to_remove:
265             del self._dependency_dict[tracked_dependency]
266 
267         # Now free dependants which do depend on the given dependency.
268         possible_freed_dependants = self._dependency_dict.pop(
269             dependency, set())
270         non_free_dependants = set()
271 
272         for possible_freed_dependant in possible_freed_dependants:
273             # Check if all dependencies of dependants from above are satisfied.
274             # If so, there are no more dependencies for dependant. Thus it's
275             # resolved.
276             for dependants in self._dependency_dict.values():
277                 if possible_freed_dependant in dependants:
278                     non_free_dependants.add(possible_freed_dependant)
279                     break
280 
281         # Remaining dependents are officially resolved.
282         return possible_freed_dependants - non_free_dependants
283 
284     def check_circular_dependencies(self):
285         """
286         Checks whether there are circular dependency conflicts.
287 
288         >>> tracker = DependencyTracker()
289         >>> tracker.add(0, 1)
290         >>> tracker.add(1, 0)
291         >>> tracker.check_circular_dependencies()
292         Traceback (most recent call last):
293          ...
294         coalib.core.CircularDependencyError.CircularDependencyError: ...
295 
296         :raises CircularDependencyError:
297             Raised on circular dependency conflicts.
298         """
299         traverse_graph(
300             self._dependency_dict.keys(),
301             lambda node: self._dependency_dict.get(node, frozenset()))
302 
303     @property
304     def are_dependencies_resolved(self):
305         """
306         Checks whether all dependencies in this ``DependencyTracker`` instance
307         are resolved.
308 
309         >>> tracker = DependencyTracker()
310         >>> tracker.are_dependencies_resolved
311         True
312         >>> tracker.add(0, 1)
313         >>> tracker.are_dependencies_resolved
314         False
315         >>> tracker.resolve(0)
316         {1}
317         >>> tracker.are_dependencies_resolved
318         True
319 
320         :return:
321             ``True`` when all dependencies resolved, ``False`` if not.
322         """
323         return not self._dependency_dict
324
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/coalib/core/DependencyTracker.py b/coalib/core/DependencyTracker.py
--- a/coalib/core/DependencyTracker.py
+++ b/coalib/core/DependencyTracker.py
@@ -293,7 +293,7 @@
          ...
         coalib.core.CircularDependencyError.CircularDependencyError: ...
 
-        :raises CircularDependencyError:
+        :raises coalib.core.CircularDependencyError.CircularDependencyError:
             Raised on circular dependency conflicts.
         """
         traverse_graph(
diff --git a/coalib/core/Graphs.py b/coalib/core/Graphs.py
--- a/coalib/core/Graphs.py
+++ b/coalib/core/Graphs.py
@@ -34,7 +34,7 @@
         A callable that is run on each edge during traversing. Takes in two
         parameters, the previous- and next-node which form an edge. The default
         is an empty function.
-    :raises CircularDependencyError:
+    :raises coalib.core.CircularDependencyError.CircularDependencyError:
         Raised when the graph is cyclic.
     """
     path = set()

{"golden_diff": "diff --git a/coalib/core/DependencyTracker.py b/coalib/core/DependencyTracker.py\n--- a/coalib/core/DependencyTracker.py\n+++ b/coalib/core/DependencyTracker.py\n@@ -293,7 +293,7 @@\n          ...\n         coalib.core.CircularDependencyError.CircularDependencyError: ...\n \n-        :raises CircularDependencyError:\n+        :raises coalib.core.CircularDependencyError.CircularDependencyError:\n             Raised on circular dependency conflicts.\n         \"\"\"\n         traverse_graph(\ndiff --git a/coalib/core/Graphs.py b/coalib/core/Graphs.py\n--- a/coalib/core/Graphs.py\n+++ b/coalib/core/Graphs.py\n@@ -34,7 +34,7 @@\n         A callable that is run on each edge during traversing. Takes in two\n         parameters, the previous- and next-node which form an edge. The default\n         is an empty function.\n-    :raises CircularDependencyError:\n+    :raises coalib.core.CircularDependencyError.CircularDependencyError:\n         Raised when the graph is cyclic.\n     \"\"\"\n     path = set()\n", "issue": "can't build docs due to multiple targets for cross-reference\nI can't successfully build the docs using `python setup.py docs` with Sphinx 1.5.5 due to the following error\r\n\r\n```\r\nWarning, treated as error:\r\n/home/thomas/gitrepos/coala/coalib/core/DependencyTracker.py:docstring of coalib.core.DependencyTracker.DependencyTracker.check_circular_dependencies:None: WARNING: more than one target found for cross-reference 'CircularDependencyError': coalib.collecting.Dependencies.CircularDependencyError, coalib.core.CircularDependencyError.CircularDependencyError\r\n```\r\n\r\nI had a look at the implementation of the two CircularDependenyError classes and they are quite similar, can't they be merged?\n", "before_files": [{"content": "from coalib.core.CircularDependencyError import CircularDependencyError\n\n\ndef traverse_graph(start_nodes, get_successive_nodes,\n                   run_on_edge=lambda prev, nxt: None):\n    \"\"\"\n    Traverses all edges of a directed, possibly disconnected graph once.\n    Detects cyclic graphs by raising a ``CircularDependencyError``.\n\n    >>> graph = {1: [2], 2: [3, 4], 5: [3], 3: [6]}\n    >>> def get_successive_nodes(node):\n    ...     return graph.get(node, [])\n    >>> edges = set()\n    >>> def append_to_edges(prev, nxt):\n    ...     edges.add((prev, nxt))\n    >>> traverse_graph([1, 5], get_successive_nodes, append_to_edges)\n    >>> sorted(edges)\n    [(1, 2), (2, 3), (2, 4), (3, 6), (5, 3)]\n\n    You can also use this function to detect cyclic graphs:\n\n    >>> graph = {1: [2], 2: [3], 3: [1]}\n    >>> traverse_graph([1], get_successive_nodes)\n    Traceback (most recent call last):\n     ...\n    coalib.core.CircularDependencyError.CircularDependencyError: ...\n\n    :param start_nodes:\n        The nodes where to start traversing the graph.\n    :param get_successive_nodes:\n        A callable that takes in a node and returns an iterable of nodes to\n        traverse next.\n    :param run_on_edge:\n        A callable that is run on each edge during traversing. Takes in two\n        parameters, the previous- and next-node which form an edge. The default\n        is an empty function.\n    :raises CircularDependencyError:\n        Raised when the graph is cyclic.\n    \"\"\"\n    path = set()\n    visited_nodes = set()\n\n    def visit(node):\n        if node not in visited_nodes:\n            visited_nodes.add(node)\n            path.add(node)\n\n            for subnode in get_successive_nodes(node):\n                run_on_edge(node, subnode)\n\n                if subnode in path:\n                    raise CircularDependencyError(subnode)\n\n                visit(subnode)\n\n            path.remove(node)\n\n    for node in start_nodes:\n        visit(node)\n", "path": "coalib/core/Graphs.py"}, {"content": "from itertools import chain\n\nfrom coalib.core.Graphs import traverse_graph\n\n\nclass DependencyTracker:\n    \"\"\"\n    A ``DependencyTracker`` allows to register and manage dependencies between\n    objects.\n\n    This class uses a directed graph to track relations.\n\n    Add a dependency relation between two objects:\n\n    >>> object1 = object()\n    >>> object2 = object()\n    >>> tracker = DependencyTracker()\n    >>> tracker.add(object2, object1)\n\n    This would define that ``object1`` is dependent on ``object2``.\n\n    If you define that ``object2`` has its dependency duty fulfilled, you can\n    resolve it:\n\n    >>> resolved = tracker.resolve(object2)\n    >>> resolved\n    {<object object at ...>}\n    >>> resolved_object = resolved.pop()\n    >>> resolved_object is object1\n    True\n\n    This returns all objects that are now freed, meaning they have no\n    dependencies any more.\n\n    >>> object3 = object()\n    >>> tracker.add(object2, object1)\n    >>> tracker.add(object3, object1)\n    >>> tracker.resolve(object2)\n    set()\n    >>> tracker.resolve(object3)\n    {<object object at ...>}\n\n    The ones who instantiate a ``DependencyTracker`` are responsible for\n    resolving dependencies in the right order. Dependencies which are itself\n    dependent will be forcefully resolved and removed from their according\n    dependencies too.\n    \"\"\"\n\n    def __init__(self):\n        self._dependency_dict = {}\n\n    def get_dependants(self, dependency):\n        \"\"\"\n        Returns all immediate dependants for the given dependency.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(1, 3)\n        >>> tracker.get_dependants(0)\n        {1, 2}\n        >>> tracker.get_dependants(1)\n        {3}\n        >>> tracker.get_dependants(2)\n        set()\n\n        :param dependency:\n            The dependency to retrieve all dependants from.\n        :return:\n            A set of dependants.\n        \"\"\"\n        try:\n            return set(self._dependency_dict[dependency])\n        except KeyError:\n            return set()\n\n    def get_dependencies(self, dependant):\n        \"\"\"\n        Returns all immediate dependencies of a given dependant.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(1, 2)\n        >>> tracker.get_dependencies(0)\n        set()\n        >>> tracker.get_dependencies(1)\n        {0}\n        >>> tracker.get_dependencies(2)\n        {0, 1}\n\n        :param dependant:\n            The dependant to retrieve all dependencies from.\n        :return:\n            A set of dependencies.\n        \"\"\"\n        return set(\n            dependency\n            for dependency, dependants in self._dependency_dict.items()\n            if dependant in dependants)\n\n    def get_all_dependants(self, dependency):\n        \"\"\"\n        Returns a set of all dependants of the given dependency, even\n        indirectly related ones.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(1, 2)\n        >>> tracker.get_all_dependants(0)\n        {1, 2}\n\n        :param dependency:\n            The dependency to get all dependants for.\n        :return:\n            A set of dependants.\n        \"\"\"\n        dependants = set()\n\n        def append_to_dependants(prev, nxt):\n            dependants.add(nxt)\n\n        traverse_graph(\n            [dependency],\n            lambda node: self._dependency_dict.get(node, frozenset()),\n            append_to_dependants)\n\n        return dependants\n\n    def get_all_dependencies(self, dependant):\n        \"\"\"\n        Returns a set of all dependencies of the given dependants, even\n        indirectly related ones.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(1, 2)\n        >>> tracker.get_all_dependencies(2)\n        {0, 1}\n\n        :param dependant:\n            The dependant to get all dependencies for.\n        :return:\n            A set of dependencies.\n        \"\"\"\n        dependencies = set()\n\n        def append_to_dependencies(prev, nxt):\n            dependencies.add(nxt)\n\n        traverse_graph(\n            [dependant],\n            lambda node:\n                {dependency\n                 for dependency, dependants in self._dependency_dict.items()\n                 if node in dependants},\n            append_to_dependencies)\n\n        return dependencies\n\n    @property\n    def dependants(self):\n        \"\"\"\n        Returns a set of all registered dependants.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(1, 3)\n        >>> tracker.dependants\n        {1, 2, 3}\n        \"\"\"\n        return set(chain.from_iterable(self._dependency_dict.values()))\n\n    @property\n    def dependencies(self):\n        \"\"\"\n        Returns a set of all registered dependencies.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(1, 3)\n        >>> tracker.dependencies\n        {0, 1}\n        \"\"\"\n        return set(self._dependency_dict.keys())\n\n    def __iter__(self):\n        \"\"\"\n        Returns an iterator that iterates over all dependency relations.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(1, 2)\n        >>> for dependency, dependant in sorted(tracker):\n        ...     print(dependency, '->', dependant)\n        0 -> 1\n        0 -> 2\n        1 -> 2\n        \"\"\"\n        return ((dependency, dependant)\n                for dependency, dependants in self._dependency_dict.items()\n                for dependant in dependants)\n\n    def add(self, dependency, dependant):\n        \"\"\"\n        Add a dependency relation.\n\n        This function does not check for circular dependencies.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.resolve(0)\n        {1, 2}\n\n        :param dependency:\n            The object that is the dependency.\n        :param dependant:\n            The object that is the dependant.\n        \"\"\"\n        if dependency not in self._dependency_dict:\n            self._dependency_dict[dependency] = set()\n\n        self._dependency_dict[dependency].add(dependant)\n\n    def resolve(self, dependency):\n        \"\"\"\n        Resolves all dependency-relations from the given dependency, and frees\n        and returns dependants with no more dependencies. If the given\n        dependency is itself a dependant, all those relations are also removed.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(2, 3)\n        >>> tracker.resolve(0)\n        {1, 2}\n        >>> tracker.resolve(2)\n        {3}\n        >>> tracker.resolve(2)\n        set()\n\n        :param dependency:\n            The dependency.\n        :return:\n            Returns a set of dependants whose dependencies were all resolved.\n        \"\"\"\n        # Check if dependency has itself dependencies which aren't resolved,\n        # these need to be removed too. This operation does not free any\n        # dependencies.\n        dependencies_to_remove = []\n        for tracked_dependency, dependants in self._dependency_dict.items():\n            if dependency in dependants:\n                dependants.remove(dependency)\n\n                # If dependants set is now empty, schedule dependency for\n                # removal from dependency_dict.\n                if not dependants:\n                    dependencies_to_remove.append(tracked_dependency)\n\n        for tracked_dependency in dependencies_to_remove:\n            del self._dependency_dict[tracked_dependency]\n\n        # Now free dependants which do depend on the given dependency.\n        possible_freed_dependants = self._dependency_dict.pop(\n            dependency, set())\n        non_free_dependants = set()\n\n        for possible_freed_dependant in possible_freed_dependants:\n            # Check if all dependencies of dependants from above are satisfied.\n            # If so, there are no more dependencies for dependant. Thus it's\n            # resolved.\n            for dependants in self._dependency_dict.values():\n                if possible_freed_dependant in dependants:\n                    non_free_dependants.add(possible_freed_dependant)\n                    break\n\n        # Remaining dependents are officially resolved.\n        return possible_freed_dependants - non_free_dependants\n\n    def check_circular_dependencies(self):\n        \"\"\"\n        Checks whether there are circular dependency conflicts.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(1, 0)\n        >>> tracker.check_circular_dependencies()\n        Traceback (most recent call last):\n         ...\n        coalib.core.CircularDependencyError.CircularDependencyError: ...\n\n        :raises CircularDependencyError:\n            Raised on circular dependency conflicts.\n        \"\"\"\n        traverse_graph(\n            self._dependency_dict.keys(),\n            lambda node: self._dependency_dict.get(node, frozenset()))\n\n    @property\n    def are_dependencies_resolved(self):\n        \"\"\"\n        Checks whether all dependencies in this ``DependencyTracker`` instance\n        are resolved.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.are_dependencies_resolved\n        True\n        >>> tracker.add(0, 1)\n        >>> tracker.are_dependencies_resolved\n        False\n        >>> tracker.resolve(0)\n        {1}\n        >>> tracker.are_dependencies_resolved\n        True\n\n        :return:\n            ``True`` when all dependencies resolved, ``False`` if not.\n        \"\"\"\n        return not self._dependency_dict\n", "path": "coalib/core/DependencyTracker.py"}], "after_files": [{"content": "from coalib.core.CircularDependencyError import CircularDependencyError\n\n\ndef traverse_graph(start_nodes, get_successive_nodes,\n                   run_on_edge=lambda prev, nxt: None):\n    \"\"\"\n    Traverses all edges of a directed, possibly disconnected graph once.\n    Detects cyclic graphs by raising a ``CircularDependencyError``.\n\n    >>> graph = {1: [2], 2: [3, 4], 5: [3], 3: [6]}\n    >>> def get_successive_nodes(node):\n    ...     return graph.get(node, [])\n    >>> edges = set()\n    >>> def append_to_edges(prev, nxt):\n    ...     edges.add((prev, nxt))\n    >>> traverse_graph([1, 5], get_successive_nodes, append_to_edges)\n    >>> sorted(edges)\n    [(1, 2), (2, 3), (2, 4), (3, 6), (5, 3)]\n\n    You can also use this function to detect cyclic graphs:\n\n    >>> graph = {1: [2], 2: [3], 3: [1]}\n    >>> traverse_graph([1], get_successive_nodes)\n    Traceback (most recent call last):\n     ...\n    coalib.core.CircularDependencyError.CircularDependencyError: ...\n\n    :param start_nodes:\n        The nodes where to start traversing the graph.\n    :param get_successive_nodes:\n        A callable that takes in a node and returns an iterable of nodes to\n        traverse next.\n    :param run_on_edge:\n        A callable that is run on each edge during traversing. Takes in two\n        parameters, the previous- and next-node which form an edge. The default\n        is an empty function.\n    :raises coalib.core.CircularDependencyError.CircularDependencyError:\n        Raised when the graph is cyclic.\n    \"\"\"\n    path = set()\n    visited_nodes = set()\n\n    def visit(node):\n        if node not in visited_nodes:\n            visited_nodes.add(node)\n            path.add(node)\n\n            for subnode in get_successive_nodes(node):\n                run_on_edge(node, subnode)\n\n                if subnode in path:\n                    raise CircularDependencyError(subnode)\n\n                visit(subnode)\n\n            path.remove(node)\n\n    for node in start_nodes:\n        visit(node)\n", "path": "coalib/core/Graphs.py"}, {"content": "from itertools import chain\n\nfrom coalib.core.Graphs import traverse_graph\n\n\nclass DependencyTracker:\n    \"\"\"\n    A ``DependencyTracker`` allows to register and manage dependencies between\n    objects.\n\n    This class uses a directed graph to track relations.\n\n    Add a dependency relation between two objects:\n\n    >>> object1 = object()\n    >>> object2 = object()\n    >>> tracker = DependencyTracker()\n    >>> tracker.add(object2, object1)\n\n    This would define that ``object1`` is dependent on ``object2``.\n\n    If you define that ``object2`` has its dependency duty fulfilled, you can\n    resolve it:\n\n    >>> resolved = tracker.resolve(object2)\n    >>> resolved\n    {<object object at ...>}\n    >>> resolved_object = resolved.pop()\n    >>> resolved_object is object1\n    True\n\n    This returns all objects that are now freed, meaning they have no\n    dependencies any more.\n\n    >>> object3 = object()\n    >>> tracker.add(object2, object1)\n    >>> tracker.add(object3, object1)\n    >>> tracker.resolve(object2)\n    set()\n    >>> tracker.resolve(object3)\n    {<object object at ...>}\n\n    The ones who instantiate a ``DependencyTracker`` are responsible for\n    resolving dependencies in the right order. Dependencies which are itself\n    dependent will be forcefully resolved and removed from their according\n    dependencies too.\n    \"\"\"\n\n    def __init__(self):\n        self._dependency_dict = {}\n\n    def get_dependants(self, dependency):\n        \"\"\"\n        Returns all immediate dependants for the given dependency.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(1, 3)\n        >>> tracker.get_dependants(0)\n        {1, 2}\n        >>> tracker.get_dependants(1)\n        {3}\n        >>> tracker.get_dependants(2)\n        set()\n\n        :param dependency:\n            The dependency to retrieve all dependants from.\n        :return:\n            A set of dependants.\n        \"\"\"\n        try:\n            return set(self._dependency_dict[dependency])\n        except KeyError:\n            return set()\n\n    def get_dependencies(self, dependant):\n        \"\"\"\n        Returns all immediate dependencies of a given dependant.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(1, 2)\n        >>> tracker.get_dependencies(0)\n        set()\n        >>> tracker.get_dependencies(1)\n        {0}\n        >>> tracker.get_dependencies(2)\n        {0, 1}\n\n        :param dependant:\n            The dependant to retrieve all dependencies from.\n        :return:\n            A set of dependencies.\n        \"\"\"\n        return set(\n            dependency\n            for dependency, dependants in self._dependency_dict.items()\n            if dependant in dependants)\n\n    def get_all_dependants(self, dependency):\n        \"\"\"\n        Returns a set of all dependants of the given dependency, even\n        indirectly related ones.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(1, 2)\n        >>> tracker.get_all_dependants(0)\n        {1, 2}\n\n        :param dependency:\n            The dependency to get all dependants for.\n        :return:\n            A set of dependants.\n        \"\"\"\n        dependants = set()\n\n        def append_to_dependants(prev, nxt):\n            dependants.add(nxt)\n\n        traverse_graph(\n            [dependency],\n            lambda node: self._dependency_dict.get(node, frozenset()),\n            append_to_dependants)\n\n        return dependants\n\n    def get_all_dependencies(self, dependant):\n        \"\"\"\n        Returns a set of all dependencies of the given dependants, even\n        indirectly related ones.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(1, 2)\n        >>> tracker.get_all_dependencies(2)\n        {0, 1}\n\n        :param dependant:\n            The dependant to get all dependencies for.\n        :return:\n            A set of dependencies.\n        \"\"\"\n        dependencies = set()\n\n        def append_to_dependencies(prev, nxt):\n            dependencies.add(nxt)\n\n        traverse_graph(\n            [dependant],\n            lambda node:\n                {dependency\n                 for dependency, dependants in self._dependency_dict.items()\n                 if node in dependants},\n            append_to_dependencies)\n\n        return dependencies\n\n    @property\n    def dependants(self):\n        \"\"\"\n        Returns a set of all registered dependants.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(1, 3)\n        >>> tracker.dependants\n        {1, 2, 3}\n        \"\"\"\n        return set(chain.from_iterable(self._dependency_dict.values()))\n\n    @property\n    def dependencies(self):\n        \"\"\"\n        Returns a set of all registered dependencies.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(1, 3)\n        >>> tracker.dependencies\n        {0, 1}\n        \"\"\"\n        return set(self._dependency_dict.keys())\n\n    def __iter__(self):\n        \"\"\"\n        Returns an iterator that iterates over all dependency relations.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(1, 2)\n        >>> for dependency, dependant in sorted(tracker):\n        ...     print(dependency, '->', dependant)\n        0 -> 1\n        0 -> 2\n        1 -> 2\n        \"\"\"\n        return ((dependency, dependant)\n                for dependency, dependants in self._dependency_dict.items()\n                for dependant in dependants)\n\n    def add(self, dependency, dependant):\n        \"\"\"\n        Add a dependency relation.\n\n        This function does not check for circular dependencies.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.resolve(0)\n        {1, 2}\n\n        :param dependency:\n            The object that is the dependency.\n        :param dependant:\n            The object that is the dependant.\n        \"\"\"\n        if dependency not in self._dependency_dict:\n            self._dependency_dict[dependency] = set()\n\n        self._dependency_dict[dependency].add(dependant)\n\n    def resolve(self, dependency):\n        \"\"\"\n        Resolves all dependency-relations from the given dependency, and frees\n        and returns dependants with no more dependencies. If the given\n        dependency is itself a dependant, all those relations are also removed.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(0, 2)\n        >>> tracker.add(2, 3)\n        >>> tracker.resolve(0)\n        {1, 2}\n        >>> tracker.resolve(2)\n        {3}\n        >>> tracker.resolve(2)\n        set()\n\n        :param dependency:\n            The dependency.\n        :return:\n            Returns a set of dependants whose dependencies were all resolved.\n        \"\"\"\n        # Check if dependency has itself dependencies which aren't resolved,\n        # these need to be removed too. This operation does not free any\n        # dependencies.\n        dependencies_to_remove = []\n        for tracked_dependency, dependants in self._dependency_dict.items():\n            if dependency in dependants:\n                dependants.remove(dependency)\n\n                # If dependants set is now empty, schedule dependency for\n                # removal from dependency_dict.\n                if not dependants:\n                    dependencies_to_remove.append(tracked_dependency)\n\n        for tracked_dependency in dependencies_to_remove:\n            del self._dependency_dict[tracked_dependency]\n\n        # Now free dependants which do depend on the given dependency.\n        possible_freed_dependants = self._dependency_dict.pop(\n            dependency, set())\n        non_free_dependants = set()\n\n        for possible_freed_dependant in possible_freed_dependants:\n            # Check if all dependencies of dependants from above are satisfied.\n            # If so, there are no more dependencies for dependant. Thus it's\n            # resolved.\n            for dependants in self._dependency_dict.values():\n                if possible_freed_dependant in dependants:\n                    non_free_dependants.add(possible_freed_dependant)\n                    break\n\n        # Remaining dependents are officially resolved.\n        return possible_freed_dependants - non_free_dependants\n\n    def check_circular_dependencies(self):\n        \"\"\"\n        Checks whether there are circular dependency conflicts.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.add(0, 1)\n        >>> tracker.add(1, 0)\n        >>> tracker.check_circular_dependencies()\n        Traceback (most recent call last):\n         ...\n        coalib.core.CircularDependencyError.CircularDependencyError: ...\n\n        :raises coalib.core.CircularDependencyError.CircularDependencyError:\n            Raised on circular dependency conflicts.\n        \"\"\"\n        traverse_graph(\n            self._dependency_dict.keys(),\n            lambda node: self._dependency_dict.get(node, frozenset()))\n\n    @property\n    def are_dependencies_resolved(self):\n        \"\"\"\n        Checks whether all dependencies in this ``DependencyTracker`` instance\n        are resolved.\n\n        >>> tracker = DependencyTracker()\n        >>> tracker.are_dependencies_resolved\n        True\n        >>> tracker.add(0, 1)\n        >>> tracker.are_dependencies_resolved\n        False\n        >>> tracker.resolve(0)\n        {1}\n        >>> tracker.are_dependencies_resolved\n        True\n\n        :return:\n            ``True`` when all dependencies resolved, ``False`` if not.\n        \"\"\"\n        return not self._dependency_dict\n", "path": "coalib/core/DependencyTracker.py"}]}