Debian Codegraph @

taskflow/engines/action_engine/compiler.py

raw
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