Attributes: ref: A reference to an object that this DependencyGraphNode represents. dependencies: List of DependencyGraphNodes on which this one depends. dependents: List of DependencyGraphNodes that depend on this one.
| 1638 | |
| 1639 | |
| 1640 | class DependencyGraphNode: |
| 1641 | """ |
| 1642 | |
| 1643 | Attributes: |
| 1644 | ref: A reference to an object that this DependencyGraphNode represents. |
| 1645 | dependencies: List of DependencyGraphNodes on which this one depends. |
| 1646 | dependents: List of DependencyGraphNodes that depend on this one. |
| 1647 | """ |
| 1648 | |
| 1649 | class CircularException(GypError): |
| 1650 | pass |
| 1651 | |
| 1652 | def __init__(self, ref): |
| 1653 | self.ref = ref |
| 1654 | self.dependencies = [] |
| 1655 | self.dependents = [] |
| 1656 | |
| 1657 | def __repr__(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 |
no outgoing calls
no test coverage detected