| 1 |
# Copyright (C) 2014 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 threading |
| 16 |
|
| 17 |
import fasteners |
| 18 |
from oslo_utils import excutils |
| 19 |
|
| 20 |
from taskflow import flow |
| 21 |
from taskflow import logging |
| 22 |
from taskflow import task |
| 23 |
from taskflow.types import graph as gr |
| 24 |
from taskflow.types import tree as tr |
| 25 |
from taskflow.utils import iter_utils |
| 26 |
from taskflow.utils import misc |
| 27 |
|
| 28 |
from taskflow.flow import (LINK_INVARIANT, LINK_RETRY) # noqa |
| 29 |
|
| 30 |
LOG = logging.getLogger(__name__) |
| 31 |
|
| 32 |
# Constants attached to node attributes in the execution graph (and tree |
| 33 |
# node metadata), provided as constants here and constants in the compilation |
| 34 |
# class (so that users will not have to import this file to access them); but |
| 35 |
# provide them as module constants so that internal code can more |
| 36 |
# easily access them... |
| 37 |
TASK = 'task' |
| 38 |
RETRY = 'retry' |
| 39 |
FLOW = 'flow' |
| 40 |
FLOW_END = 'flow_end' |
| 41 |
|
| 42 |
# Quite often used together, so make a tuple everyone can share... |
| 43 |
ATOMS = (TASK, RETRY) |
| 44 |
FLOWS = (FLOW, FLOW_END) |
| 45 |
|
| 46 |
|
| 47 |
class Terminator: |
| 48 |
"""Flow terminator class.""" |
| 49 |
|
| 50 |
def __init__(self, flow): |
| 51 |
self._flow = flow |
| 52 |
self._name = f"{self._flow.name}[$]" |
| 53 |
|
| 54 |
@property |
| 55 |
def flow(self): |
| 56 |
"""The flow which this terminator signifies/marks the end of.""" |
| 57 |
return self._flow |
| 58 |
|
| 59 |
@property |
| 60 |
def name(self): |
| 61 |
"""Useful name this end terminator has (derived from flow name).""" |
| 62 |
return self._name |
| 63 |
|
| 64 |
def __str__(self): |
| 65 |
flow_name = ("%s" % self._flow).strip('"') |
| 66 |
return '"%s[$]"' % flow_name |
| 67 |
|
| 68 |
|
| 69 |
class Compilation: |
| 70 |
"""The result of a compilers ``compile()`` is this *immutable* object.""" |
| 71 |
|
| 72 |
#: Task nodes will have a ``kind`` metadata key with this value. |
| 73 |
TASK = TASK |
| 74 |
|
| 75 |
#: Retry nodes will have a ``kind`` metadata key with this value. |
| 76 |
RETRY = RETRY |
| 77 |
|
| 78 |
FLOW = FLOW |
| 79 |
""" |
| 80 |
Flow **entry** nodes will have a ``kind`` metadata key with |
| 81 |
this value. |
| 82 |
""" |
| 83 |
|
| 84 |
FLOW_END = FLOW_END |
| 85 |
""" |
| 86 |
Flow **exit** nodes will have a ``kind`` metadata key with |
| 87 |
this value (only applicable for compilation execution graph, not currently |
| 88 |
used in tree hierarchy). |
| 89 |
""" |
| 90 |
|
| 91 |
def __init__(self, execution_graph, hierarchy): |
| 92 |
self._execution_graph = execution_graph |
| 93 |
self._hierarchy = hierarchy |
| 94 |
|
| 95 |
@property |
| 96 |
def execution_graph(self): |
| 97 |
"""The execution ordering of atoms (as a graph structure).""" |
| 98 |
return self._execution_graph |
| 99 |
|
| 100 |
@property |
| 101 |
def hierarchy(self): |
| 102 |
"""The hierarchy of patterns (as a tree structure).""" |
| 103 |
return self._hierarchy |
| 104 |
|
| 105 |
|
| 106 |
def _overlap_occurrence_detector(to_graph, from_graph): |
| 107 |
"""Returns how many nodes in 'from' graph are in 'to' graph (if any).""" |
| 108 |
return iter_utils.count(node for node in from_graph.nodes |
| 109 |
if node in to_graph) |
| 110 |
|
| 111 |
|
| 112 |
def _add_update_edges(graph, nodes_from, nodes_to, attr_dict=None): |
| 113 |
"""Adds/updates edges from nodes to other nodes in the specified graph. |
| 114 |
|
| 115 |
It will connect the 'nodes_from' to the 'nodes_to' if an edge currently |
| 116 |
does *not* exist (if it does already exist then the edges attributes |
| 117 |
are just updated instead). When an edge is created the provided edge |
| 118 |
attributes dictionary will be applied to the new edge between these two |
| 119 |
nodes. |
| 120 |
""" |
| 121 |
# NOTE(harlowja): give each edge its own attr copy so that if it's |
| 122 |
# later modified that the same copy isn't modified... |
| 123 |
for u in nodes_from: |
| 124 |
for v in nodes_to: |
| 125 |
if not graph.has_edge(u, v): |
| 126 |
if attr_dict: |
| 127 |
graph.add_edge(u, v, attr_dict=attr_dict.copy()) |
| 128 |
else: |
| 129 |
graph.add_edge(u, v) |
| 130 |
else: |
| 131 |
# Just update the attr_dict (if any). |
| 132 |
if attr_dict: |
| 133 |
graph.add_edge(u, v, attr_dict=attr_dict.copy()) |
| 134 |
|
| 135 |
|
| 136 |
class TaskCompiler: |
| 137 |
"""Non-recursive compiler of tasks.""" |
| 138 |
|
| 139 |
def compile(self, task, parent=None): |
| 140 |
graph = gr.DiGraph(name=task.name) |
| 141 |
graph.add_node(task, kind=TASK) |
| 142 |
node = tr.Node(task, kind=TASK) |
| 143 |
if parent is not None: |
| 144 |
parent.add(node) |
| 145 |
return graph, node |
| 146 |
|
| 147 |
|
| 148 |
class FlowCompiler: |
| 149 |
"""Recursive compiler of flows.""" |
| 150 |
|
| 151 |
def __init__(self, deep_compiler_func): |
| 152 |
self._deep_compiler_func = deep_compiler_func |
| 153 |
|
| 154 |
def compile(self, flow, parent=None): |
| 155 |
"""Decomposes a flow into a graph and scope tree hierarchy.""" |
| 156 |
graph = gr.DiGraph(name=flow.name) |
| 157 |
graph.add_node(flow, kind=FLOW, noop=True) |
| 158 |
tree_node = tr.Node(flow, kind=FLOW, noop=True) |
| 159 |
if parent is not None: |
| 160 |
parent.add(tree_node) |
| 161 |
if flow.retry is not None: |
| 162 |
tree_node.add(tr.Node(flow.retry, kind=RETRY)) |
| 163 |
decomposed = { |
| 164 |
child: self._deep_compiler_func(child, parent=tree_node)[0] |
| 165 |
for child in flow} |
| 166 |
decomposed_graphs = list(decomposed.values()) |
| 167 |
graph = gr.merge_graphs(graph, *decomposed_graphs, |
| 168 |
overlap_detector=_overlap_occurrence_detector) |
| 169 |
for u, v, attr_dict in flow.iter_links(): |
| 170 |
u_graph = decomposed[u] |
| 171 |
v_graph = decomposed[v] |
| 172 |
_add_update_edges(graph, u_graph.no_successors_iter(), |
| 173 |
list(v_graph.no_predecessors_iter()), |
| 174 |
attr_dict=attr_dict) |
| 175 |
# Insert the flow(s) retry if needed, and always make sure it |
| 176 |
# is the **immediate** successor of the flow node itself. |
| 177 |
if flow.retry is not None: |
| 178 |
graph.add_node(flow.retry, kind=RETRY) |
| 179 |
_add_update_edges(graph, [flow], [flow.retry], |
| 180 |
attr_dict={LINK_INVARIANT: True}) |
| 181 |
for node in graph.nodes: |
| 182 |
if node is not flow.retry and node is not flow: |
| 183 |
graph.nodes[node].setdefault(RETRY, flow.retry) |
| 184 |
from_nodes = [flow.retry] |
| 185 |
attr_dict = {LINK_INVARIANT: True, LINK_RETRY: True} |
| 186 |
else: |
| 187 |
from_nodes = [flow] |
| 188 |
attr_dict = {LINK_INVARIANT: True} |
| 189 |
# Ensure all nodes with no predecessors are connected to this flow |
| 190 |
# or its retry node (so that the invariant that the flow node is |
| 191 |
# traversed through before its contents is maintained); this allows |
| 192 |
# us to easily know when we have entered a flow (when running) and |
| 193 |
# do special and/or smart things such as only traverse up to the |
| 194 |
# start of a flow when looking for node deciders. |
| 195 |
_add_update_edges(graph, from_nodes, [ |
| 196 |
node for node in graph.no_predecessors_iter() |
| 197 |
if node is not flow |
| 198 |
], attr_dict=attr_dict) |
| 199 |
# Connect all nodes with no successors into a special terminator |
| 200 |
# that is used to identify the end of the flow and ensure that all |
| 201 |
# execution traversals will traverse over this node before executing |
| 202 |
# further work (this is especially useful for nesting and knowing |
| 203 |
# when we have exited a nesting level); it allows us to do special |
| 204 |
# and/or smart things such as applying deciders up to (but not |
| 205 |
# beyond) a flow termination point. |
| 206 |
# |
| 207 |
# Do note that in a empty flow this will just connect itself to |
| 208 |
# the flow node itself... and also note we can not use the flow |
| 209 |
# object itself (primarily because the underlying graph library |
| 210 |
# uses hashing to identify node uniqueness and we can easily create |
| 211 |
# a loop if we don't do this correctly, so avoid that by just |
| 212 |
# creating this special node and tagging it with a special kind); we |
| 213 |
# may be able to make this better in the future with a multidigraph |
| 214 |
# that networkx provides?? |
| 215 |
flow_term = Terminator(flow) |
| 216 |
graph.add_node(flow_term, kind=FLOW_END, noop=True) |
| 217 |
_add_update_edges(graph, [ |
| 218 |
node for node in graph.no_successors_iter() |
| 219 |
if node is not flow_term |
| 220 |
], [flow_term], attr_dict={LINK_INVARIANT: True}) |
| 221 |
return graph, tree_node |
| 222 |
|
| 223 |
|
| 224 |
class PatternCompiler: |
| 225 |
"""Compiles a flow pattern (or task) into a compilation unit. |
| 226 |
|
| 227 |
Let's dive into the basic idea for how this works: |
| 228 |
|
| 229 |
The compiler here is provided a 'root' object via its __init__ method, |
| 230 |
this object could be a task, or a flow (one of the supported patterns), |
| 231 |
the end-goal is to produce a :py:class:`.Compilation` object as the result |
| 232 |
with the needed components. If this is not possible a |
| 233 |
:py:class:`~.taskflow.exceptions.CompilationFailure` will be raised. |
| 234 |
In the case where a **unknown** type is being requested to compile |
| 235 |
a ``TypeError`` will be raised and when a duplicate object (one that |
| 236 |
has **already** been compiled) is encountered a ``ValueError`` is raised. |
| 237 |
|
| 238 |
The complexity of this comes into play when the 'root' is a flow that |
| 239 |
contains itself other nested flows (and so-on); to compile this object and |
| 240 |
its contained objects into a graph that *preserves* the constraints the |
| 241 |
pattern mandates we have to go through a recursive algorithm that creates |
| 242 |
subgraphs for each nesting level, and then on the way back up through |
| 243 |
the recursion (now with a decomposed mapping from contained patterns or |
| 244 |
atoms to there corresponding subgraph) we have to then connect the |
| 245 |
subgraphs (and the atom(s) there-in) that were decomposed for a pattern |
| 246 |
correctly into a new graph and then ensure the pattern mandated |
| 247 |
constraints are retained. Finally we then return to the |
| 248 |
caller (and they will do the same thing up until the root node, which by |
| 249 |
that point one graph is created with all contained atoms in the |
| 250 |
pattern/nested patterns mandated ordering). |
| 251 |
|
| 252 |
Also maintained in the :py:class:`.Compilation` object is a hierarchy of |
| 253 |
the nesting of items (which is also built up during the above mentioned |
| 254 |
recusion, via a much simpler algorithm); this is typically used later to |
| 255 |
determine the prior atoms of a given atom when looking up values that can |
| 256 |
be provided to that atom for execution (see the scopes.py file for how this |
| 257 |
works). Note that although you *could* think that the graph itself could be |
| 258 |
used for this, which in some ways it can (for limited usage) the hierarchy |
| 259 |
retains the nested structure (which is useful for scoping analysis/lookup) |
| 260 |
to be able to provide back a iterator that gives back the scopes visible |
| 261 |
at each level (the graph does not have this information once flattened). |
| 262 |
|
| 263 |
Let's take an example: |
| 264 |
|
| 265 |
Given the pattern ``f(a(b, c), d)`` where ``f`` is a |
| 266 |
:py:class:`~taskflow.patterns.linear_flow.Flow` with items ``a(b, c)`` |
| 267 |
where ``a`` is a :py:class:`~taskflow.patterns.linear_flow.Flow` composed |
| 268 |
of tasks ``(b, c)`` and task ``d``. |
| 269 |
|
| 270 |
The algorithm that will be performed (mirroring the above described logic) |
| 271 |
will go through the following steps (the tree hierarchy building is left |
| 272 |
out as that is more obvious):: |
| 273 |
|
| 274 |
Compiling f |
| 275 |
- Decomposing flow f with no parent (must be the root) |
| 276 |
- Compiling a |
| 277 |
- Decomposing flow a with parent f |
| 278 |
- Compiling b |
| 279 |
- Decomposing task b with parent a |
| 280 |
- Decomposed b into: |
| 281 |
Name: b |
| 282 |
Nodes: 1 |
| 283 |
- b |
| 284 |
Edges: 0 |
| 285 |
- Compiling c |
| 286 |
- Decomposing task c with parent a |
| 287 |
- Decomposed c into: |
| 288 |
Name: c |
| 289 |
Nodes: 1 |
| 290 |
- c |
| 291 |
Edges: 0 |
| 292 |
- Relinking decomposed b -> decomposed c |
| 293 |
- Decomposed a into: |
| 294 |
Name: a |
| 295 |
Nodes: 2 |
| 296 |
- b |
| 297 |
- c |
| 298 |
Edges: 1 |
| 299 |
b -> c ({'invariant': True}) |
| 300 |
- Compiling d |
| 301 |
- Decomposing task d with parent f |
| 302 |
- Decomposed d into: |
| 303 |
Name: d |
| 304 |
Nodes: 1 |
| 305 |
- d |
| 306 |
Edges: 0 |
| 307 |
- Relinking decomposed a -> decomposed d |
| 308 |
- Decomposed f into: |
| 309 |
Name: f |
| 310 |
Nodes: 3 |
| 311 |
- c |
| 312 |
- b |
| 313 |
- d |
| 314 |
Edges: 2 |
| 315 |
c -> d ({'invariant': True}) |
| 316 |
b -> c ({'invariant': True}) |
| 317 |
""" |
| 318 |
|
| 319 |
def __init__(self, root, freeze=True): |
| 320 |
self._root = root |
| 321 |
self._history = set() |
| 322 |
self._freeze = freeze |
| 323 |
self._lock = threading.Lock() |
| 324 |
self._compilation = None |
| 325 |
self._matchers = [ |
| 326 |
(flow.Flow, FlowCompiler(self._compile)), |
| 327 |
(task.Task, TaskCompiler()), |
| 328 |
] |
| 329 |
self._level = 0 |
| 330 |
|
| 331 |
def _compile(self, item, parent=None): |
| 332 |
"""Compiles a item (pattern, task) into a graph + tree node.""" |
| 333 |
item_compiler = misc.match_type(item, self._matchers) |
| 334 |
if item_compiler is not None: |
| 335 |
self._pre_item_compile(item) |
| 336 |
graph, node = item_compiler.compile(item, parent=parent) |
| 337 |
self._post_item_compile(item, graph, node) |
| 338 |
return graph, node |
| 339 |
else: |
| 340 |
raise TypeError("Unknown object '%s' (%s) requested to compile" |
| 341 |
% (item, type(item))) |
| 342 |
|
| 343 |
def _pre_item_compile(self, item): |
| 344 |
"""Called before a item is compiled; any pre-compilation actions.""" |
| 345 |
if item in self._history: |
| 346 |
raise ValueError("Already compiled item '%s' (%s), duplicate" |
| 347 |
" and/or recursive compiling is not" |
| 348 |
" supported" % (item, type(item))) |
| 349 |
self._history.add(item) |
| 350 |
if LOG.isEnabledFor(logging.TRACE): |
| 351 |
LOG.trace("%sCompiling '%s'", " " * self._level, item) |
| 352 |
self._level += 1 |
| 353 |
|
| 354 |
def _post_item_compile(self, item, graph, node): |
| 355 |
"""Called after a item is compiled; doing post-compilation actions.""" |
| 356 |
self._level -= 1 |
| 357 |
if LOG.isEnabledFor(logging.TRACE): |
| 358 |
prefix = ' ' * self._level |
| 359 |
LOG.trace("%sDecomposed '%s' into:", prefix, item) |
| 360 |
prefix = ' ' * (self._level + 1) |
| 361 |
LOG.trace("%sGraph:", prefix) |
| 362 |
for line in graph.pformat().splitlines(): |
| 363 |
LOG.trace("%s %s", prefix, line) |
| 364 |
LOG.trace("%sHierarchy:", prefix) |
| 365 |
for line in node.pformat().splitlines(): |
| 366 |
LOG.trace("%s %s", prefix, line) |
| 367 |
|
| 368 |
def _pre_compile(self): |
| 369 |
"""Called before the compilation of the root starts.""" |
| 370 |
self._history.clear() |
| 371 |
self._level = 0 |
| 372 |
|
| 373 |
def _post_compile(self, graph, node): |
| 374 |
"""Called after the compilation of the root finishes successfully.""" |
| 375 |
self._history.clear() |
| 376 |
self._level = 0 |
| 377 |
|
| 378 |
@fasteners.locked |
| 379 |
def compile(self): |
| 380 |
"""Compiles the contained item into a compiled equivalent.""" |
| 381 |
if self._compilation is None: |
| 382 |
self._pre_compile() |
| 383 |
try: |
| 384 |
graph, node = self._compile(self._root, parent=None) |
| 385 |
except Exception: |
| 386 |
with excutils.save_and_reraise_exception(): |
| 387 |
# Always clear the history, to avoid retaining junk |
| 388 |
# in memory that isn't needed to be in memory if |
| 389 |
# compilation fails... |
| 390 |
self._history.clear() |
| 391 |
else: |
| 392 |
self._post_compile(graph, node) |
| 393 |
if self._freeze: |
| 394 |
graph.freeze() |
| 395 |
node.freeze() |
| 396 |
self._compilation = Compilation(graph, node) |
| 397 |
return self._compilation |