Debian Codegraph @

taskflow/engines/action_engine/selector.py

raw
1 # Copyright (C) 2013 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 operator
16 import weakref
17
18 from taskflow.engines.action_engine import compiler as co
19 from taskflow.engines.action_engine import deciders
20 from taskflow.engines.action_engine import traversal
21 from taskflow import logging
22 from taskflow import states as st
23 from taskflow.utils import iter_utils
24
25 LOG = logging.getLogger(__name__)
26
27
28 class Selector:
29 """Selector that uses a compilation and aids in execution processes.
30
31 Its primary purpose is to get the next atoms for execution or reversion
32 by utilizing the compilations underlying structures (graphs, nodes and
33 edge relations...) and using this information along with the atom
34 state/states stored in storage to provide other useful functionality to
35 the rest of the runtime system.
36 """
37
38 def __init__(self, runtime):
39 self._runtime = weakref.proxy(runtime)
40 self._storage = runtime.storage
41 self._execution_graph = runtime.compilation.execution_graph
42
43 def iter_next_atoms(self, atom=None):
44 """Iterate next atoms to run (originating from atom or all atoms)."""
45 if atom is None:
46 return iter_utils.unique_seen((self._browse_atoms_for_execute(),
47 self._browse_atoms_for_revert()),
48 seen_selector=operator.itemgetter(0))
49 state = self._storage.get_atom_state(atom.name)
50 intention = self._storage.get_atom_intention(atom.name)
51 if state == st.SUCCESS:
52 if intention == st.REVERT:
53 return iter([
54 (atom, deciders.NoOpDecider()),
55 ])
56 elif intention == st.EXECUTE:
57 return self._browse_atoms_for_execute(atom=atom)
58 else:
59 return iter([])
60 elif state == st.REVERTED:
61 return self._browse_atoms_for_revert(atom=atom)
62 elif state == st.FAILURE:
63 return self._browse_atoms_for_revert()
64 else:
65 return iter([])
66
67 def _browse_atoms_for_execute(self, atom=None):
68 """Browse next atoms to execute.
69
70 This returns a iterator of atoms that *may* be ready to be
71 executed, if given a specific atom, it will only examine the successors
72 of that atom, otherwise it will examine the whole graph.
73 """
74 if atom is None:
75 atom_it = self._runtime.iterate_nodes(co.ATOMS)
76 else:
77 # NOTE(harlowja): the reason this uses breadth first is so that
78 # when deciders are applied that those deciders can be applied
79 # from top levels to lower levels since lower levels *may* be
80 # able to run even if top levels have deciders that decide to
81 # ignore some atoms... (going deeper first would make this
82 # problematic to determine as top levels can have their deciders
83 # applied **after** going deeper).
84 atom_it = traversal.breadth_first_iterate(
85 self._execution_graph, atom, traversal.Direction.FORWARD)
86 for atom in atom_it:
87 is_ready, late_decider = self._get_maybe_ready_for_execute(atom)
88 if is_ready:
89 yield (atom, late_decider)
90
91 def _browse_atoms_for_revert(self, atom=None):
92 """Browse next atoms to revert.
93
94 This returns a iterator of atoms that *may* be ready to be be
95 reverted, if given a specific atom it will only examine the
96 predecessors of that atom, otherwise it will examine the whole
97 graph.
98 """
99 if atom is None:
100 atom_it = self._runtime.iterate_nodes(co.ATOMS)
101 else:
102 atom_it = traversal.breadth_first_iterate(
103 self._execution_graph, atom, traversal.Direction.BACKWARD,
104 # Stop at the retry boundary (as retries 'control' there
105 # surronding atoms, and we don't want to back track over
106 # them so that they can correctly affect there associated
107 # atoms); we do though need to jump through all tasks since
108 # if a predecessor Y was ignored and a predecessor Z before Y
109 # was not it should be eligible to now revert...
110 through_retries=False)
111 for atom in atom_it:
112 is_ready, late_decider = self._get_maybe_ready_for_revert(atom)
113 if is_ready:
114 yield (atom, late_decider)
115
116 def _get_maybe_ready(self, atom, transition_to, allowed_intentions,
117 connected_fetcher, ready_checker,
118 decider_fetcher, for_what="?"):
119 def iter_connected_states():
120 # Lazily iterate over connected states so that ready checkers
121 # can stop early (vs having to consume and check all the
122 # things...)
123 for atom in connected_fetcher():
124 # TODO(harlowja): make this storage api better, its not
125 # especially clear what the following is doing (mainly
126 # to avoid two calls into storage).
127 atom_states = self._storage.get_atoms_states([atom.name])
128 yield (atom, atom_states[atom.name])
129 # NOTE(harlowja): How this works is the following...
130 #
131 # 1. First check if the current atom can even transition to the
132 # desired state, if not this atom is definitely not ready to
133 # execute or revert.
134 # 2. Check if the actual atoms intention is in one of the desired/ok
135 # intentions, if it is not there we are still not ready to execute
136 # or revert.
137 # 3. Iterate over (atom, atom_state, atom_intention) for all the
138 # atoms the 'connected_fetcher' callback yields from underlying
139 # storage and direct that iterator into the 'ready_checker'
140 # callback, that callback should then iterate over these entries
141 # and determine if it is ok to execute or revert.
142 # 4. If (and only if) 'ready_checker' returns true, then
143 # the 'decider_fetcher' callback is called to get a late decider
144 # which can (if it desires) affect this ready result (but does
145 # so right before the atom is about to be scheduled).
146 state = self._storage.get_atom_state(atom.name)
147 ok_to_transition = self._runtime.check_atom_transition(atom, state,
148 transition_to)
149 if not ok_to_transition:
150 LOG.trace("Atom '%s' is not ready to %s since it can not"
151 " transition to %s from its current state %s",
152 atom, for_what, transition_to, state)
153 return (False, None)
154 intention = self._storage.get_atom_intention(atom.name)
155 if intention not in allowed_intentions:
156 LOG.trace("Atom '%s' is not ready to %s since its current"
157 " intention %s is not in allowed intentions %s",
158 atom, for_what, intention, allowed_intentions)
159 return (False, None)
160 ok_to_run = ready_checker(iter_connected_states())
161 if not ok_to_run:
162 return (False, None)
163 else:
164 return (True, decider_fetcher())
165
166 def _get_maybe_ready_for_execute(self, atom):
167 """Returns if an atom is *likely* ready to be executed."""
168 def ready_checker(pred_connected_it):
169 for pred in pred_connected_it:
170 pred_atom, (pred_atom_state, pred_atom_intention) = pred
171 if (pred_atom_state in (st.SUCCESS, st.IGNORE) and
172 pred_atom_intention in (st.EXECUTE, st.IGNORE)):
173 continue
174 LOG.trace("Unable to begin to execute since predecessor"
175 " atom '%s' is in state %s with intention %s",
176 pred_atom, pred_atom_state, pred_atom_intention)
177 return False
178 LOG.trace("Able to let '%s' execute", atom)
179 return True
180 decider_fetcher = lambda: \
181 deciders.IgnoreDecider(
182 atom, self._runtime.fetch_edge_deciders(atom))
183 connected_fetcher = lambda: \
184 traversal.depth_first_iterate(self._execution_graph, atom,
185 # Whether the desired atom
186 # can execute is dependent on its
187 # predecessors outcomes (thus why
188 # we look backwards).
189 traversal.Direction.BACKWARD)
190 # If this atoms current state is able to be transitioned to RUNNING
191 # and its intention is to EXECUTE and all of its predecessors executed
192 # successfully or were ignored then this atom is ready to execute.
193 LOG.trace("Checking if '%s' is ready to execute", atom)
194 return self._get_maybe_ready(atom, st.RUNNING, [st.EXECUTE],
195 connected_fetcher, ready_checker,
196 decider_fetcher, for_what='execute')
197
198 def _get_maybe_ready_for_revert(self, atom):
199 """Returns if an atom is *likely* ready to be reverted."""
200 def ready_checker(succ_connected_it):
201 for succ in succ_connected_it:
202 succ_atom, (succ_atom_state, _succ_atom_intention) = succ
203 if succ_atom_state not in (st.PENDING, st.REVERTED, st.IGNORE):
204 LOG.trace("Unable to begin to revert since successor"
205 " atom '%s' is in state %s", succ_atom,
206 succ_atom_state)
207 return False
208 LOG.trace("Able to let '%s' revert", atom)
209 return True
210 noop_decider = deciders.NoOpDecider()
211 connected_fetcher = lambda: \
212 traversal.depth_first_iterate(self._execution_graph, atom,
213 # Whether the desired atom
214 # can revert is dependent on its
215 # successors states (thus why we
216 # look forwards).
217 traversal.Direction.FORWARD)
218 decider_fetcher = lambda: noop_decider
219 # If this atoms current state is able to be transitioned to REVERTING
220 # and its intention is either REVERT or RETRY and all of its
221 # successors are either PENDING or REVERTED then this atom is ready
222 # to revert.
223 LOG.trace("Checking if '%s' is ready to revert", atom)
224 return self._get_maybe_ready(atom, st.REVERTING, [st.REVERT, st.RETRY],
225 connected_fetcher, ready_checker,
226 decider_fetcher, for_what='revert')