OLD | NEW |
1 # Copyright (c) 2012 Google Inc. All rights reserved. | 1 # Copyright (c) 2012 Google Inc. All rights reserved. |
2 # Use of this source code is governed by a BSD-style license that can be | 2 # Use of this source code is governed by a BSD-style license that can be |
3 # found in the LICENSE file. | 3 # found in the LICENSE file. |
4 | 4 |
5 from compiler.ast import Const | 5 from compiler.ast import Const |
6 from compiler.ast import Dict | 6 from compiler.ast import Dict |
7 from compiler.ast import Discard | 7 from compiler.ast import Discard |
8 from compiler.ast import List | 8 from compiler.ast import List |
9 from compiler.ast import Module | 9 from compiler.ast import Module |
10 from compiler.ast import Node | 10 from compiler.ast import Node |
(...skipping 1521 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1532 def __repr__(self): | 1532 def __repr__(self): |
1533 return '<DependencyGraphNode: %r>' % self.ref | 1533 return '<DependencyGraphNode: %r>' % self.ref |
1534 | 1534 |
1535 def FlattenToList(self): | 1535 def FlattenToList(self): |
1536 # flat_list is the sorted list of dependencies - actually, the list items | 1536 # flat_list is the sorted list of dependencies - actually, the list items |
1537 # are the "ref" attributes of DependencyGraphNodes. Every target will | 1537 # are the "ref" attributes of DependencyGraphNodes. Every target will |
1538 # appear in flat_list after all of its dependencies, and before all of its | 1538 # appear in flat_list after all of its dependencies, and before all of its |
1539 # dependents. | 1539 # dependents. |
1540 flat_list = OrderedSet() | 1540 flat_list = OrderedSet() |
1541 | 1541 |
| 1542 def ExtractNodeRef(node): |
| 1543 """Extracts the object that the node represents from the given node.""" |
| 1544 return node.ref |
| 1545 |
1542 # in_degree_zeros is the list of DependencyGraphNodes that have no | 1546 # in_degree_zeros is the list of DependencyGraphNodes that have no |
1543 # dependencies not in flat_list. Initially, it is a copy of the children | 1547 # dependencies not in flat_list. Initially, it is a copy of the children |
1544 # of this node, because when the graph was built, nodes with no | 1548 # of this node, because when the graph was built, nodes with no |
1545 # dependencies were made implicit dependents of the root node. | 1549 # dependencies were made implicit dependents of the root node. |
1546 in_degree_zeros = set(self.dependents[:]) | 1550 in_degree_zeros = sorted(self.dependents[:], key=ExtractNodeRef) |
1547 | 1551 |
1548 while in_degree_zeros: | 1552 while in_degree_zeros: |
1549 # Nodes in in_degree_zeros have no dependencies not in flat_list, so they | 1553 # Nodes in in_degree_zeros have no dependencies not in flat_list, so they |
1550 # can be appended to flat_list. Take these nodes out of in_degree_zeros | 1554 # can be appended to flat_list. Take these nodes out of in_degree_zeros |
1551 # as work progresses, so that the next node to process from the list can | 1555 # as work progresses, so that the next node to process from the list can |
1552 # always be accessed at a consistent position. | 1556 # always be accessed at a consistent position. |
1553 node = in_degree_zeros.pop() | 1557 node = in_degree_zeros.pop() |
1554 flat_list.add(node.ref) | 1558 flat_list.add(node.ref) |
1555 | 1559 |
1556 # Look at dependents of the node just added to flat_list. Some of them | 1560 # Look at dependents of the node just added to flat_list. Some of them |
1557 # may now belong in in_degree_zeros. | 1561 # may now belong in in_degree_zeros. |
1558 for node_dependent in node.dependents: | 1562 for node_dependent in sorted(node.dependents, key=ExtractNodeRef): |
1559 is_in_degree_zero = True | 1563 is_in_degree_zero = True |
1560 # TODO: We want to check through the | 1564 # TODO: We want to check through the |
1561 # node_dependent.dependencies list but if it's long and we | 1565 # node_dependent.dependencies list but if it's long and we |
1562 # always start at the beginning, then we get O(n^2) behaviour. | 1566 # always start at the beginning, then we get O(n^2) behaviour. |
1563 for node_dependent_dependency in node_dependent.dependencies: | 1567 for node_dependent_dependency in (sorted(node_dependent.dependencies, |
| 1568 key=ExtractNodeRef)): |
1564 if not node_dependent_dependency.ref in flat_list: | 1569 if not node_dependent_dependency.ref in flat_list: |
1565 # The dependent one or more dependencies not in flat_list. There | 1570 # The dependent one or more dependencies not in flat_list. There |
1566 # will be more chances to add it to flat_list when examining | 1571 # will be more chances to add it to flat_list when examining |
1567 # it again as a dependent of those other dependencies, provided | 1572 # it again as a dependent of those other dependencies, provided |
1568 # that there are no cycles. | 1573 # that there are no cycles. |
1569 is_in_degree_zero = False | 1574 is_in_degree_zero = False |
1570 break | 1575 break |
1571 | 1576 |
1572 if is_in_degree_zero: | 1577 if is_in_degree_zero: |
1573 # All of the dependent's dependencies are already in flat_list. Add | 1578 # All of the dependent's dependencies are already in flat_list. Add |
1574 # it to in_degree_zeros where it will be processed in a future | 1579 # it to in_degree_zeros where it will be processed in a future |
1575 # iteration of the outer loop. | 1580 # iteration of the outer loop. |
1576 in_degree_zeros.add(node_dependent) | 1581 in_degree_zeros += [node_dependent] |
1577 | 1582 |
1578 return list(flat_list) | 1583 return list(flat_list) |
1579 | 1584 |
1580 def FindCycles(self): | 1585 def FindCycles(self): |
1581 """ | 1586 """ |
1582 Returns a list of cycles in the graph, where each cycle is its own list. | 1587 Returns a list of cycles in the graph, where each cycle is its own list. |
1583 """ | 1588 """ |
1584 results = [] | 1589 results = [] |
1585 visited = set() | 1590 visited = set() |
1586 | 1591 |
(...skipping 1298 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2885 ValidateRunAsInTarget(target, target_dict, build_file) | 2890 ValidateRunAsInTarget(target, target_dict, build_file) |
2886 ValidateActionsInTarget(target, target_dict, build_file) | 2891 ValidateActionsInTarget(target, target_dict, build_file) |
2887 | 2892 |
2888 # Generators might not expect ints. Turn them into strs. | 2893 # Generators might not expect ints. Turn them into strs. |
2889 TurnIntIntoStrInDict(data) | 2894 TurnIntIntoStrInDict(data) |
2890 | 2895 |
2891 # TODO(mark): Return |data| for now because the generator needs a list of | 2896 # TODO(mark): Return |data| for now because the generator needs a list of |
2892 # build files that came in. In the future, maybe it should just accept | 2897 # build files that came in. In the future, maybe it should just accept |
2893 # a list, and not the whole data dict. | 2898 # a list, and not the whole data dict. |
2894 return [flat_list, targets, data] | 2899 return [flat_list, targets, data] |
OLD | NEW |