| 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 |