blob: 70f2ecccb739a50c03db627c499e2b58f6d25372 [file] [log] [blame]
# swift_build_support/ ----------------------------*- python -*-
# This source file is part of the open source project
# Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
# Licensed under Apache License v2.0 with Runtime Library Exception
# See for license information
# See for the list of Swift project authors
# ----------------------------------------------------------------------------
# This is a simple implementation of an acyclic build graph. We require no
# cycles, so we just perform a reverse post order traversal to get a topological
# ordering. We check during the reverse post order traversal that we do not
# visit any node multiple times.
# Nodes are assumed to be a product's class.
# ----------------------------------------------------------------------------
def _get_po_ordered_nodes(root, invertedDepMap):
# Then setup our worklist/visited node set.
worklist = [root]
visitedNodes = set([])
# TODO: Can we unify po_ordered_nodes and visitedNodes in some way?
po_ordered_nodes = []
# Until we no longer have nodes to visit...
while not len(worklist) == 0:
# First grab the last element of the worklist. If we have already
# visited this node, just pop it and skip it.
# DISCUSSION: Consider the following build graph:
# A -> [C, B]
# B -> [C]
# In this case, we will most likely get the following worklist
# before actually processing anything:
# A, C, B, C
# In this case, we want to ignore the initial C pushed onto the
# worklist by visiting A since we will have visited C already due to
# the edge from B -> C.
node = worklist[-1]
if node in visitedNodes:
# Then grab the dependents of our node.
deps = invertedDepMap.get(node, set([]))
assert(isinstance(deps, set))
# Then visit those and see if we have not visited any of them. Push
# any such nodes onto the worklist and continue. If we have already
# visited all of our dependents, then we can actually process this
# node.
foundDep = False
for d in deps:
if d not in visitedNodes:
foundDep = True
if foundDep:
# Now process the node by popping it off the worklist, adding it to
# the visited nodes set, and append it to the po_ordered_nodes in
# its final position.
return po_ordered_nodes
class BuildDAG(object):
def __init__(self):
self.root = None
# A map from a node to a list of nodes that depend on the given node.
# NOTE: This is an inverted dependency map implying that the root will
# be a "final element" of the graph.
self.invertedDepMap = {}
def add_edge(self, pred, succ):
self.invertedDepMap.setdefault(pred, set([succ])) \
def set_root(self, root):
# Assert that we always only have one root.
assert(self.root is None)
self.root = root
def produce_schedule(self):
# Grab the root and make sure it is not None
root = self.root
assert(root is not None)
# Then perform a post order traversal from root using our inverted
# dependency map to compute a list of our nodes in post order.
# NOTE: The index of each node in this list is the post order number of
# the node.
po_ordered_nodes = _get_po_ordered_nodes(root, self.invertedDepMap)
# Ok, we have our post order list. We want to provide our user a reverse
# post order, so we take our array and construct a dictionary of an
# enumeration of the list. This will give us a dictionary mapping our
# product names to their reverse post order number.
rpo_ordered_nodes = list(reversed(po_ordered_nodes))
node_to_rpot_map = dict((y, x) for x, y in enumerate(rpo_ordered_nodes))
# Now before we return our rpo_ordered_nodes and our node_to_rpot_map, lets
# verify that we didn't find any cycles. We can do this by traversing
# our dependency graph in reverse post order and making sure all
# dependencies of each node we visit has a later reverse post order
# number than the node we are checking.
for n, node in enumerate(rpo_ordered_nodes):
for dep in self.invertedDepMap.get(node, []):
if node_to_rpot_map[dep] < n:
print('n: {}. node: {}.'.format(n, node))
print('dep: {}.'.format(dep))
print('inverted dependency map: {}'.format(self.invertedDepMap))
print('rpo ordered nodes: {}'.format(rpo_ordered_nodes))
print('rpo node to rpo number map: {}'.format(node_to_rpot_map))
raise RuntimeError('Found cycle in build graph!')
return (rpo_ordered_nodes, node_to_rpot_map)
def produce_scheduled_build(input_product_classes):
"""For a given a subset input_input_product_classes of
all_input_product_classes, compute a topological ordering of the
input_input_product_classes + topological closures that respects the
dependency graph.
dag = BuildDAG()
worklist = list(input_product_classes)
visited = set(input_product_classes)
# Construct the DAG.
while len(worklist) > 0:
entry = worklist.pop()
deps = entry.get_dependencies()
if len(deps) == 0:
for d in deps:
dag.add_edge(d, entry)
if d not in visited:
visited = visited.union(deps)
# Then produce the schedule.
schedule = dag.produce_schedule()
# Finally check that all of our input_product_classes are in the schedule.
if len(set(input_product_classes) - set(schedule[0])) != 0:
raise RuntimeError('Found disconnected graph?!')
return schedule