migrated (most) docstrings to pep-257 format, docstring generator using straight <pre> + trim() func

for now.  applies most of [ticket:214], compliemnts of Lele Gaifax

1 files changed, 95 insertions, 51 deletions

diff --git a/lib/sqlalchemy/topological.py b/lib/sqlalchemy/topological.py
index a1b03b89a..d9f68ac01 100644
--- a/lib/sqlalchemy/topological.py
+++ b/lib/sqlalchemy/topological.py
@@ -4,57 +4,78 @@
 # This module is part of SQLAlchemy and is released under
 # the MIT License: http://www.opensource.org/licenses/mit-license.php
 
-"""topological sorting algorithms.  the key to the unit of work is to assemble a list
-of dependencies amongst all the different mappers that have been defined for classes.
-Related tables with foreign key constraints have a definite insert order, deletion order, 
-objects need dependent properties from parent objects set up before saved, etc.  
-These are all encoded as dependencies, in the form "mapper X is dependent on mapper Y", 
-meaning mapper Y's objects must be saved before those of mapper X, and mapper X's objects 
-must be deleted before those of mapper Y.
-
-The topological sort is an algorithm that receives this list of dependencies as a "partial
-ordering", that is a list of pairs which might say, "X is dependent on Y", "Q is dependent
-on Z", but does not necessarily tell you anything about Q being dependent on X. Therefore,
-its not a straight sort where every element can be compared to another...only some of the
-elements have any sorting preference, and then only towards just some of the other elements.
-For a particular partial ordering, there can be many possible sorts that satisfy the
+"""Topological sorting algorithms.
+
+The key to the unit of work is to assemble a list of dependencies
+amongst all the different mappers that have been defined for classes.
+
+Related tables with foreign key constraints have a definite insert
+order, deletion order, objects need dependent properties from parent
+objects set up before saved, etc.
+
+These are all encoded as dependencies, in the form *mapper X is
+dependent on mapper Y*, meaning mapper Y's objects must be saved
+before those of mapper X, and mapper X's objects must be deleted
+before those of mapper Y.
+
+The topological sort is an algorithm that receives this list of
+dependencies as a *partial ordering*, that is a list of pairs which
+might say, *X is dependent on Y*, *Q is dependent on Z*, but does not
+necessarily tell you anything about Q being dependent on X. Therefore,
+its not a straight sort where every element can be compared to
+another... only some of the elements have any sorting preference, and
+then only towards just some of the other elements.  For a particular
+partial ordering, there can be many possible sorts that satisfy the
 conditions.
 
-An intrinsic "gotcha" to this algorithm is that since there are many possible outcomes
-to sorting a partial ordering, the algorithm can return any number of different results for the
-same input; just running it on a different machine architecture, or just random differences
-in the ordering of dictionaries, can change the result that is returned.  While this result
-is guaranteed to be true to the incoming partial ordering, if the partial ordering itself
-does not properly represent the dependencies, code that works fine will suddenly break, then
-work again, then break, etc.   Most of the bugs I've chased down while developing the "unit of work"
-have been of this nature - very tricky to reproduce and track down, particularly before I 
-realized this characteristic of the algorithm.
+An intrinsic *gotcha* to this algorithm is that since there are many
+possible outcomes to sorting a partial ordering, the algorithm can
+return any number of different results for the same input; just
+running it on a different machine architecture, or just random
+differences in the ordering of dictionaries, can change the result
+that is returned.  While this result is guaranteed to be true to the
+incoming partial ordering, if the partial ordering itself does not
+properly represent the dependencies, code that works fine will
+suddenly break, then work again, then break, etc.  Most of the bugs
+I've chased down while developing the *unit of work* have been of this
+nature - very tricky to reproduce and track down, particularly before
+I realized this characteristic of the algorithm.
 """
+
 import string, StringIO
 from sqlalchemy import util
 from sqlalchemy.exceptions import *
 
 class _Node(object):
-    """represents each item in the sort.  While the topological sort
-    produces a straight ordered list of items, _Node ultimately stores a tree-structure
-    of those items which are organized so that non-dependent nodes are siblings."""
+    """Represent each item in the sort.
+
+    While the topological sort produces a straight ordered list of
+    items, ``_Node`` ultimately stores a tree-structure of those items
+    which are organized so that non-dependent nodes are siblings.
+    """
+
     def __init__(self, item):
         self.item = item
         self.dependencies = util.Set()
         self.children = []
         self.cycles = None
+
     def __str__(self):
         return self.safestr()
+
     def safestr(self, indent=0):
         return (' ' * indent * 2) + \
             str(self.item) + \
             (self.cycles is not None and (" (cycles: " + repr([x for x in self.cycles]) + ")") or "") + \
             "\n" + \
             string.join([n.safestr(indent + 1) for n in self.children], '')
+
     def __repr__(self):
         return "%s" % (str(self.item))
+
     def all_deps(self):
-        """Returns a set of dependencies for this node and all its cycles"""
+        """Return a set of dependencies for this node and all its cycles."""
+
         deps = util.Set(self.dependencies)
         if self.cycles is not None:
             for c in self.cycles:
@@ -62,12 +83,15 @@ class _Node(object):
         return deps
 
 class _EdgeCollection(object):
-    """a collection of directed edges."""
+    """A collection of directed edges."""
+
     def __init__(self):
         self.parent_to_children = {}
         self.child_to_parents = {}
+
     def add(self, edge):
-        """add an edge to this collection."""
+        """Add an edge to this collection."""
+
         (parentnode, childnode) = edge
         if not self.parent_to_children.has_key(parentnode):
             self.parent_to_children[parentnode] = util.Set()
@@ -76,8 +100,13 @@ class _EdgeCollection(object):
             self.child_to_parents[childnode] = util.Set()
         self.child_to_parents[childnode].add(parentnode)
         parentnode.dependencies.add(childnode)
+
     def remove(self, edge):
-        """remove an edge from this collection.  return the childnode if it has no other parents"""
+        """Remove an edge from this collection.
+
+        Return the childnode if it has no other parents.
+        """
+
         (parentnode, childnode) = edge
         self.parent_to_children[parentnode].remove(childnode)
         self.child_to_parents[childnode].remove(parentnode)
@@ -85,52 +114,65 @@ class _EdgeCollection(object):
             return childnode
         else:
             return None
+
     def has_parents(self, node):
         return self.child_to_parents.has_key(node) and len(self.child_to_parents[node]) > 0
+
     def edges_by_parent(self, node):
         if self.parent_to_children.has_key(node):
             return [(node, child) for child in self.parent_to_children[node]]
         else:
             return []
+
     def get_parents(self):
         return self.parent_to_children.keys()
+
     def pop_node(self, node):
-        """remove all edges where the given node is a parent.  
-        
-        returns the collection of all nodes which were children of the given node, and have
-        no further parents."""
+        """Remove all edges where the given node is a parent.
+
+        Return the collection of all nodes which were children of the
+        given node, and have no further parents.
+        """
+
         children = self.parent_to_children.pop(node, None)
         if children is not None:
             for child in children:
                 self.child_to_parents[child].remove(node)
                 if not len(self.child_to_parents[child]):
                     yield child
+
     def __len__(self):
         return sum([len(x) for x in self.parent_to_children.values()])
+
     def __iter__(self):
         for parent, children in self.parent_to_children.iteritems():
             for child in children:
                 yield (parent, child)
+
     def __str__(self):
         return repr(list(self))
+
     def __repr__(self):
         return repr(list(self))
-        
+
 class QueueDependencySorter(object):
-    """topological sort adapted from wikipedia's article on the subject.  it creates a straight-line
-    list of elements, then a second pass groups non-dependent actions together to build
-    more of a tree structure with siblings."""
-            
+    """Topological sort adapted from wikipedia's article on the subject.
+
+    It creates a straight-line list of elements, then a second pass
+    groups non-dependent actions together to build more of a tree
+    structure with siblings.
+    """
+
     def __init__(self, tuples, allitems):
         self.tuples = tuples
         self.allitems = allitems
 
     def sort(self, allow_self_cycles=True, allow_all_cycles=False):
         (tuples, allitems) = (self.tuples, self.allitems)
-        #print "\n---------------------------------\n"        
+        #print "\n---------------------------------\n"
         #print repr([t for t in tuples])
         #print repr([a for a in allitems])
-        #print "\n---------------------------------\n"        
+        #print "\n---------------------------------\n"
 
         nodes = {}
         edges = _EdgeCollection()
@@ -138,7 +180,7 @@ class QueueDependencySorter(object):
             if not nodes.has_key(item):
                 node = _Node(item)
                 nodes[item] = node
-        
+
         for t in tuples:
             if t[0] is t[1]:
                 if allow_self_cycles:
@@ -188,16 +230,19 @@ class QueueDependencySorter(object):
             for childnode in edges.pop_node(node):
                 queue.append(childnode)
         return self._create_batched_tree(output)
-        
+
 
     def _create_batched_tree(self, nodes):
-        """given a list of nodes from a topological sort, organizes the nodes into a tree structure,
-        with as many non-dependent nodes set as silbings to each other as possible."""
+        """Given a list of nodes from a topological sort, organize the
+        nodes into a tree structure, with as many non-dependent nodes
+        set as siblings to each other as possible.
+        """
+
         if not len(nodes):
             return None
         # a list of all currently independent subtrees as a tuple of
         # (root_node, set_of_all_tree_nodes, set_of_all_cycle_nodes_in_tree)
-        # order of the list has no semantics for the algorithmic 
+        # order of the list has no semantics for the algorithmic
         independents = []
         # in reverse topological order
         for node in reversed(nodes):
@@ -212,7 +257,7 @@ class QueueDependencySorter(object):
             if nodealldeps:
                 # iterate over independent node indexes in reverse order so we can efficiently remove them
                 for index in xrange(len(independents)-1,-1,-1):
-                    child, childsubtree, childcycles = independents[index] 
+                    child, childsubtree, childcycles = independents[index]
                     # if there is a dependency between this node and an independent node
                     if (childsubtree.intersection(nodealldeps) or childcycles.intersection(node.dependencies)):
                         # prepend child to nodes children
@@ -231,7 +276,7 @@ class QueueDependencySorter(object):
         # used prepend [0:0] instead of extend to maintain exact behaviour of previous implementation
         head.children[0:0] = [i[0] for i in independents]
         return head
-        
+
     def _find_cycles(self, edges):
         involved_in_cycles = util.Set()
         cycles = {}
@@ -241,7 +286,7 @@ class QueueDependencySorter(object):
                 cycle = []
             elif node is goal:
                 return True
-                
+
             for (n, key) in edges.edges_by_parent(node):
                 if key in cycle:
                     continue
@@ -259,7 +304,7 @@ class QueueDependencySorter(object):
                         else:
                             cycles[x] = cycset
                 cycle.pop()
-                    
+
         for parent in edges.get_parents():
             traverse(parent)
 
@@ -269,4 +314,3 @@ class QueueDependencySorter(object):
                 if edge[0] in cycle and edge[1] in cycle:
                     edgecollection.append(edge)
             yield edgecollection
-