| Index: pylib/gyp/common.py
 | 
| ===================================================================
 | 
| --- pylib/gyp/common.py	(revision 1374)
 | 
| +++ pylib/gyp/common.py	(working copy)
 | 
| @@ -401,3 +401,52 @@
 | 
|          seen[marker] = 1
 | 
|          result.append(item)
 | 
|      return result
 | 
| +
 | 
| +
 | 
| +class CycleError(Exception):
 | 
| +  """An exception raised when an unexpected cycle is detected."""
 | 
| +  def __init__(self, nodes):
 | 
| +    self.nodes = nodes
 | 
| +  def __str__(self):
 | 
| +    return 'CycleError: cycle involving: ' + str(self.nodes)
 | 
| +
 | 
| +
 | 
| +def TopologicallySorted(graph, get_edges):
 | 
| +  """Topologically sort based on a user provided edge definition.
 | 
| +
 | 
| +  Args:
 | 
| +    graph: A list of node names.
 | 
| +    get_edges: A function mapping from node name to a hashable collection
 | 
| +               of node names which this node has outgoing edges to.
 | 
| +  Returns:
 | 
| +    A list containing all of the node in graph in topological order.
 | 
| +    It is assumed that calling get_edges once for each node and caching is
 | 
| +    cheaper than repeatedly calling get_edges.
 | 
| +  Raises:
 | 
| +    CycleError in the event of a cycle.
 | 
| +  Example:
 | 
| +    graph = {'a': '$(b) $(c)', 'b': 'hi', 'c': '$(b)'}
 | 
| +    def GetEdges(node):
 | 
| +      return re.findall(r'\$\(([^))]\)', graph[node])
 | 
| +    print TopologicallySorted(graph.keys(), GetEdges)
 | 
| +    ==>
 | 
| +    ['a', 'c', b']
 | 
| +  """
 | 
| +  get_edges = memoize(get_edges)
 | 
| +  visited = set()
 | 
| +  visiting = set()
 | 
| +  ordered_nodes = []
 | 
| +  def Visit(node):
 | 
| +    if node in visiting:
 | 
| +      raise CycleError(visiting)
 | 
| +    if node in visited:
 | 
| +      return
 | 
| +    visited.add(node)
 | 
| +    visiting.add(node)
 | 
| +    for neighbor in get_edges(node):
 | 
| +      Visit(neighbor)
 | 
| +    visiting.remove(node)
 | 
| +    ordered_nodes.insert(0, node)
 | 
| +  for node in sorted(graph):
 | 
| +    Visit(node)
 | 
| +  return ordered_nodes
 | 
| 
 |