(self)
| 1658 | return "<DependencyGraphNode: %r>" % self.ref |
| 1659 | |
| 1660 | def FlattenToList(self): |
| 1661 | # flat_list is the sorted list of dependencies - actually, the list items |
| 1662 | # are the "ref" attributes of DependencyGraphNodes. Every target will |
| 1663 | # appear in flat_list after all of its dependencies, and before all of its |
| 1664 | # dependents. |
| 1665 | flat_list = OrderedSet() |
| 1666 | |
| 1667 | def ExtractNodeRef(node): |
| 1668 | """Extracts the object that the node represents from the given node.""" |
| 1669 | return node.ref |
| 1670 | |
| 1671 | # in_degree_zeros is the list of DependencyGraphNodes that have no |
| 1672 | # dependencies not in flat_list. Initially, it is a copy of the children |
| 1673 | # of this node, because when the graph was built, nodes with no |
| 1674 | # dependencies were made implicit dependents of the root node. |
| 1675 | in_degree_zeros = sorted(self.dependents[:], key=ExtractNodeRef) |
| 1676 | |
| 1677 | while in_degree_zeros: |
| 1678 | # Nodes in in_degree_zeros have no dependencies not in flat_list, so they |
| 1679 | # can be appended to flat_list. Take these nodes out of in_degree_zeros |
| 1680 | # as work progresses, so that the next node to process from the list can |
| 1681 | # always be accessed at a consistent position. |
| 1682 | node = in_degree_zeros.pop() |
| 1683 | flat_list.add(node.ref) |
| 1684 | |
| 1685 | # Look at dependents of the node just added to flat_list. Some of them |
| 1686 | # may now belong in in_degree_zeros. |
| 1687 | for node_dependent in sorted(node.dependents, key=ExtractNodeRef): |
| 1688 | is_in_degree_zero = True |
| 1689 | # TODO: We want to check through the |
| 1690 | # node_dependent.dependencies list but if it's long and we |
| 1691 | # always start at the beginning, then we get O(n^2) behaviour. |
| 1692 | for node_dependent_dependency in sorted( |
| 1693 | node_dependent.dependencies, key=ExtractNodeRef |
| 1694 | ): |
| 1695 | if node_dependent_dependency.ref not in flat_list: |
| 1696 | # The dependent one or more dependencies not in flat_list. |
| 1697 | # There will be more chances to add it to flat_list |
| 1698 | # when examining it again as a dependent of those other |
| 1699 | # dependencies, provided that there are no cycles. |
| 1700 | is_in_degree_zero = False |
| 1701 | break |
| 1702 | |
| 1703 | if is_in_degree_zero: |
| 1704 | # All of the dependent's dependencies are already in flat_list. Add |
| 1705 | # it to in_degree_zeros where it will be processed in a future |
| 1706 | # iteration of the outer loop. |
| 1707 | in_degree_zeros += [node_dependent] |
| 1708 | |
| 1709 | return list(flat_list) |
| 1710 | |
| 1711 | def FindCycles(self): |
| 1712 | """ |
no test coverage detected