Debian Codegraph @

taskflow/engines/action_engine/traversal.py

raw
1 # Copyright (C) 2015 Yahoo! Inc. All Rights Reserved.
2 #
3 # Licensed under the Apache License, Version 2.0 (the "License"); you may
4 # not use this file except in compliance with the License. You may obtain
5 # a copy of the License at
6 #
7 # http://www.apache.org/licenses/LICENSE-2.0
8 #
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 # WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 # License for the specific language governing permissions and limitations
13 # under the License.
14
15 import collections
16 import enum
17
18 from taskflow.engines.action_engine import compiler as co
19
20
21 class Direction(enum.Enum):
22 """Traversal direction enum."""
23
24 #: Go through successors.
25 FORWARD = 1
26
27 #: Go through predecessors.
28 BACKWARD = 2
29
30
31 def _extract_connectors(execution_graph, starting_node, direction,
32 through_flows=True, through_retries=True,
33 through_tasks=True):
34 if direction == Direction.FORWARD:
35 connected_iter = execution_graph.successors
36 else:
37 connected_iter = execution_graph.predecessors
38 connected_to_functors = {}
39 if through_flows:
40 connected_to_functors[co.FLOW] = connected_iter
41 connected_to_functors[co.FLOW_END] = connected_iter
42 if through_retries:
43 connected_to_functors[co.RETRY] = connected_iter
44 if through_tasks:
45 connected_to_functors[co.TASK] = connected_iter
46 return connected_iter(starting_node), connected_to_functors
47
48
49 def breadth_first_iterate(execution_graph, starting_node, direction,
50 through_flows=True, through_retries=True,
51 through_tasks=True):
52 """Iterates connected nodes in execution graph (from starting node).
53
54 Does so in a breadth first manner.
55
56 Jumps over nodes with ``noop`` attribute (does not yield them back).
57 """
58 initial_nodes_iter, connected_to_functors = _extract_connectors(
59 execution_graph, starting_node, direction,
60 through_flows=through_flows, through_retries=through_retries,
61 through_tasks=through_tasks)
62 q = collections.deque(initial_nodes_iter)
63 visited_nodes = set()
64 while q:
65 node = q.popleft()
66 if node in visited_nodes:
67 continue
68 visited_nodes.add(node)
69
70 node_attrs = execution_graph.nodes[node]
71 if not node_attrs.get('noop'):
72 yield node
73 try:
74 node_kind = node_attrs['kind']
75 connected_to_functor = connected_to_functors[node_kind]
76 except KeyError:
77 pass
78 else:
79 q.extend(connected_to_functor(node))
80
81
82 def depth_first_iterate(execution_graph, starting_node, direction,
83 through_flows=True, through_retries=True,
84 through_tasks=True):
85 """Iterates connected nodes in execution graph (from starting node).
86
87 Does so in a depth first manner.
88
89 Jumps over nodes with ``noop`` attribute (does not yield them back).
90 """
91 initial_nodes_iter, connected_to_functors = _extract_connectors(
92 execution_graph, starting_node, direction,
93 through_flows=through_flows, through_retries=through_retries,
94 through_tasks=through_tasks)
95 stack = list(initial_nodes_iter)
96 visited_nodes = set()
97 while stack:
98 node = stack.pop()
99 if node in visited_nodes:
100 continue
101 visited_nodes.add(node)
102
103 node_attrs = execution_graph.nodes[node]
104 if not node_attrs.get('noop'):
105 yield node
106 try:
107 node_kind = node_attrs['kind']
108 connected_to_functor = connected_to_functors[node_kind]
109 except KeyError:
110 pass
111 else:
112 stack.extend(connected_to_functor(node))
113
114
115 def depth_first_reverse_iterate(node, start_from_idx=-1):
116 """Iterates connected (in reverse) **tree** nodes (from starting node).
117
118 Jumps through nodes with ``noop`` attribute (does not yield them back).
119 """
120 # Always go left to right, since right to left is the pattern order
121 # and we want to go backwards and not forwards through that ordering...
122 if start_from_idx == -1:
123 # All of them...
124 children_iter = node.reverse_iter()
125 else:
126 children_iter = reversed(node[0:start_from_idx])
127 for child in children_iter:
128 if child.metadata.get('noop'):
129 # Jump through these...
130 for grand_child in child.dfs_iter(right_to_left=False):
131 if grand_child.metadata['kind'] in co.ATOMS:
132 yield grand_child.item
133 else:
134 yield child.item