Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(381)

Unified Diff: pylib/gyp/common.py

Issue 10378042: Correct the order in which OutputDirectory and IntermediateDirectory are defined. (Closed) Base URL: http://gyp.googlecode.com/svn/trunk/
Patch Set: Created 8 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | pylib/gyp/common_test.py » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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
« no previous file with comments | « no previous file | pylib/gyp/common_test.py » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698