← Back to branch summary

~ubuntu-branches/ubuntu/trusty/germinate/trusty-proposed

« back to all changes in this revision

Viewing changes to germinate/tsort.py

  • Committer: Package Import Robot
  • Author(s): Colin Watson
  • Date: 2011-12-04 14:16:54 UTC
  • Revision ID: package-import@ubuntu.com-20111204141654-pumqjv3x5x0a4lgi
Tags: 2.0
* Make sure to always close files after finishing with them.  Mostly this
  is done using the 'with' statement in Python 2.6, but pychecker gets
  unhappy with contextlib.closing so I carried on using traditional
  try/finally blocks in cases that would require that.
* Remove all uses of os.system and os.popen, replacing them with uses of
  the better-designed subprocess module.
* Remove all code supporting the germinate -i/--ipv6 option; this has been
  off by default since November 2004, the service behind this was
  discontinued in March 2007
  (http://lists.debian.org/debian-ipv6/2007/02/msg00015.html), and
  germinate was never a great place to track this kind of thing anyway.
* Convert all option parsing to optparse.  Consolidate defaults into a new
  Germinate.defaults module.
* Update copyright dates.
* Move canonical source location from people.canonical.com to a hosted
  branch on Launchpad.
* Slightly modernise use of dh_python2.
* Forbid seed names containing slashes.
* Eliminate most uses of list.sort() in favour of sorted(iterable).
* When promoting dependencies from lesser seeds, remove them from the
  lesser seed lists at output time rather than immediately.  This is
  mostly to make it easier to process multiple seed structures, but also
  fixes a long-standing bug where promoted dependencies were only removed
  from a single arbitrary lesser seed rather than from all possible ones.
* Memoise the results of Germinator's _inner_seeds, _strictly_outer_seeds,
  and _outer_seeds methods.  This saves nearly a third of germinate's
  runtime in common cases.
* Write all output files atomically.
* Change default distribution to precise.
* Update kubuntu-meta example in germinate-update-metapackage(1).
* Refer to versioned GPL file in debian/copyright.
* Policy version 3.9.2: no changes required.

* Massive API cleanup:
  - Move output-writing functions from the top-level germinate program
    into Germinator.
  - Redesign how Germinator gets Packages/Sources sections from the
    archive.  This now works via an abstract interface, which should make
    it easier to plug in alternative archive sources (e.g. a database).
  - Move all apt_pkg interaction into library code.  Germinator.__init__
    now takes an architecture argument so that it can set
    APT::Architecture.
  - Turn open_seed into a Seed class, allowing it to be a context manager.
  - Move code pertaining to the structure of seeds into a SeedStructure
    class, simplifying the interface.
  - Make all module names lower-case, per PEP-8.  Remove the separate
    Germinate.Archive.tagfile module; this is now in germinate.archive
    directly.  Adjust build system and pychecker handling to support this.
  - Remove unnecessary logging helper functions.
  - Don't modify level names on the root logger simply as a result of
    importing germinate.germinator; move this into a function.
  - Prefix all private methods with an underscore.
  - Remove germinate.tsort from germinate's public API.
  - Convert all method names to the PEP-8 preferred style (method_name
    rather than methodName).
  - Introduce wrapper functions for the various uses of write_list and
    write_source_list, and make the underlying methods private.
  - Make most instance variables private by prefixing an underscore,
    adding a few accessor methods.
  - Convert build system to distutils, make the germinate Python package
    public, and create a new python-germinate binary package.
  - Improve the Seed class so that seeds can be read multiple times
    without having to redownload them, and so that they remember which
    branch they came from.
  - Don't modify inner seeds when processing outer ones; filter
    build-dependencies on output instead.
  - Don't plant or grow seeds that have already had functionally-identical
    versions planted or grown respectively.
  - Automatically convert string dists/components/mirrors/source_mirrors
    arguments to lists in TagFile constructor.
  - Make it possible for a single Germinator to process multiple seed
    structures, reusing the work done on common seeds.
  - Canonicalise mirrors (by appending '/' if necessary) in TagFile rather
    than in the main germinate program.
  - Handle the extra seed entirely within Germinator rather than modifying
    SeedStructure (which doesn't fit well with processing the same seed
    structure on multiple architectures).
  - Use module-level loggers.
  - Get rid of the custom PROGRESS log level.
  - Change germinate.archive to use logging rather than print.
  - Add docstrings for all public classes and methods, and tidy up a few
    existing ones per PEP-257.

Show diffs side-by-side

added added

removed removed

Lines of Context:
germinate/tsort.py
 
1
# Copyright (C) 2005, 2006, 2008, 2009 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
 
17
# This code originated in bzrlib. In order to make it suitable for use in
 
18
# Germinate, Colin Watson removed its bzrlib.errors dependency and stripped
 
19
# out the implementation of specialised merge-graph sorting.
 
20
 
 
21
 
 
22
"""Topological sorting routines."""
 
23
 
 
24
 
 
25
__all__ = ["topo_sort", "TopoSorter"]
 
26
 
 
27
 
 
28
class GraphCycleError(StandardError):
 
29
 
 
30
    _fmt = "Cycle in graph %(graph)r"
 
31
 
 
32
    def __init__(self, graph):
 
33
        StandardError.__init__(self)
 
34
        self.graph = graph
 
35
 
 
36
    def __str__(self):
 
37
        d = dict(self.__dict__)
 
38
        # special case: python2.5 puts the 'message' attribute in a
 
39
        # slot, so it isn't seen in __dict__
 
40
        d['message'] = getattr(self, 'message', 'no message')
 
41
        s = self._fmt % d
 
42
        # __str__() should always return a 'str' object
 
43
        # never a 'unicode' object.
 
44
        if isinstance(s, unicode):
 
45
            return s.encode('utf8')
 
46
        return s
 
47
 
 
48
 
 
49
def topo_sort(graph):
 
50
    """Topological sort a graph.
 
51
 
 
52
    graph -- sequence of pairs of node->parents_list.
 
53
 
 
54
    The result is a list of node names, such that all parents come before
 
55
    their children.
 
56
 
 
57
    node identifiers can be any hashable object, and are typically strings.
 
58
    """
 
59
    return TopoSorter(graph).sorted()
 
60
 
 
61
 
 
62
class TopoSorter(object):
 
63
 
 
64
    def __init__(self, graph):
 
65
        """Topological sorting of a graph.
 
66
 
 
67
        :param graph: sequence of pairs of node_name->parent_names_list.
 
68
                      i.e. [('C', ['B']), ('B', ['A']), ('A', [])]
 
69
                      For this input the output from the sort or
 
70
                      iter_topo_order routines will be:
 
71
                      'A', 'B', 'C'
 
72
 
 
73
        node identifiers can be any hashable object, and are typically strings.
 
74
 
 
75
        If you have a graph like [('a', ['b']), ('a', ['c'])] this will only use
 
76
        one of the two values for 'a'.
 
77
 
 
78
        The graph is sorted lazily: until you iterate or sort the input is
 
79
        not processed other than to create an internal representation.
 
80
 
 
81
        iteration or sorting may raise GraphCycleError if a cycle is present
 
82
        in the graph.
 
83
        """
 
84
        # a dict of the graph.
 
85
        self._graph = dict(graph)
 
86
        self._visitable = set(self._graph)
 
87
        ### if debugging:
 
88
        # self._original_graph = dict(graph)
 
89
 
 
90
        # this is a stack storing the depth first search into the graph.
 
91
        self._node_name_stack = []
 
92
        # at each level of 'recursion' we have to check each parent. This
 
93
        # stack stores the parents we have not yet checked for the node at the
 
94
        # matching depth in _node_name_stack
 
95
        self._pending_parents_stack = []
 
96
        # this is a set of the completed nodes for fast checking whether a
 
97
        # parent in a node we are processing on the stack has already been
 
98
        # emitted and thus can be skipped.
 
99
        self._completed_node_names = set()
 
100
 
 
101
    def sorted(self):
 
102
        """Sort the graph and return as a list.
 
103
 
 
104
        After calling this the sorter is empty and you must create a new one.
 
105
        """
 
106
        return list(self.iter_topo_order())
 
107
 
 
108
###        Useful if fiddling with this code.
 
109
###        # cross check
 
110
###        sorted_names = list(self.iter_topo_order())
 
111
###        for index in range(len(sorted_names)):
 
112
###            rev = sorted_names[index]
 
113
###            for left_index in range(index):
 
114
###                if rev in self.original_graph[sorted_names[left_index]]:
 
115
###                    print "revision in parent list of earlier revision"
 
116
###                    import pdb;pdb.set_trace()
 
117
 
 
118
    def iter_topo_order(self):
 
119
        """Yield the nodes of the graph in a topological order.
 
120
 
 
121
        After finishing iteration the sorter is empty and you cannot continue
 
122
        iteration.
 
123
        """
 
124
        while self._graph:
 
125
            # now pick a random node in the source graph, and transfer it to the
 
126
            # top of the depth first search stack.
 
127
            node_name, parents = self._graph.popitem()
 
128
            self._push_node(node_name, parents)
 
129
            while self._node_name_stack:
 
130
                # loop until this call completes.
 
131
                parents_to_visit = self._pending_parents_stack[-1]
 
132
                # if all parents are done, the revision is done
 
133
                if not parents_to_visit:
 
134
                    # append the revision to the topo sorted list
 
135
                    # all the nodes parents have been added to the output, now
 
136
                    # we can add it to the output.
 
137
                    yield self._pop_node()
 
138
                else:
 
139
                    while self._pending_parents_stack[-1]:
 
140
                        # recurse depth first into a single parent
 
141
                        next_node_name = self._pending_parents_stack[-1].pop()
 
142
                        if next_node_name in self._completed_node_names:
 
143
                            # this parent was completed by a child on the
 
144
                            # call stack. skip it.
 
145
                            continue
 
146
                        if next_node_name not in self._visitable:
 
147
                            continue
 
148
                        # otherwise transfer it from the source graph into the
 
149
                        # top of the current depth first search stack.
 
150
                        try:
 
151
                            parents = self._graph.pop(next_node_name)
 
152
                        except KeyError:
 
153
                            # if the next node is not in the source graph it has
 
154
                            # already been popped from it and placed into the
 
155
                            # current search stack (but not completed or we would
 
156
                            # have hit the continue 4 lines up.
 
157
                            # this indicates a cycle.
 
158
                            raise GraphCycleError(self._node_name_stack)
 
159
                        self._push_node(next_node_name, parents)
 
160
                        # and do not continue processing parents until this 'call'
 
161
                        # has recursed.
 
162
                        break
 
163
 
 
164
    def _push_node(self, node_name, parents):
 
165
        """Add node_name to the pending node stack.
 
166
 
 
167
        Names in this stack will get emitted into the output as they are popped
 
168
        off the stack.
 
169
        """
 
170
        self._node_name_stack.append(node_name)
 
171
        self._pending_parents_stack.append(list(parents))
 
172
 
 
173
    def _pop_node(self):
 
174
        """Pop the top node off the stack
 
175
 
 
176
        The node is appended to the sorted output.
 
177
        """
 
178
        # we are returning from the flattened call frame:
 
179
        # pop off the local variables
 
180
        node_name = self._node_name_stack.pop()
 
181
        self._pending_parents_stack.pop()
 
182
 
 
183
        self._completed_node_names.add(node_name)
 
184
        return node_name