| 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 |
from taskflow.engines.action_engine import compiler as co |
| 16 |
from taskflow.engines.action_engine import traversal as tr |
| 17 |
from taskflow import logging |
| 18 |
|
| 19 |
LOG = logging.getLogger(__name__) |
| 20 |
|
| 21 |
|
| 22 |
class ScopeWalker: |
| 23 |
"""Walks through the scopes of a atom using a engines compilation. |
| 24 |
|
| 25 |
NOTE(harlowja): for internal usage only. |
| 26 |
|
| 27 |
This will walk the visible scopes that are accessible for the given |
| 28 |
atom, which can be used by some external entity in some meaningful way, |
| 29 |
for example to find dependent values... |
| 30 |
""" |
| 31 |
|
| 32 |
def __init__(self, compilation, atom, names_only=False): |
| 33 |
self._node = compilation.hierarchy.find(atom) |
| 34 |
if self._node is None: |
| 35 |
raise ValueError("Unable to find atom '%s' in compilation" |
| 36 |
" hierarchy" % atom) |
| 37 |
self._level_cache = {} |
| 38 |
self._atom = atom |
| 39 |
self._execution_graph = compilation.execution_graph |
| 40 |
self._names_only = names_only |
| 41 |
self._predecessors = None |
| 42 |
|
| 43 |
def __iter__(self): |
| 44 |
"""Iterates over the visible scopes. |
| 45 |
|
| 46 |
How this works is the following: |
| 47 |
|
| 48 |
We first grab all the predecessors of the given atom (lets call it |
| 49 |
``Y``) by using the :py:class:`~.compiler.Compilation` execution |
| 50 |
graph (and doing a reverse breadth-first expansion to gather its |
| 51 |
predecessors), this is useful since we know they *always* will |
| 52 |
exist (and execute) before this atom but it does not tell us the |
| 53 |
corresponding scope *level* (flow, nested flow...) that each |
| 54 |
predecessor was created in, so we need to find this information. |
| 55 |
|
| 56 |
For that information we consult the location of the atom ``Y`` in the |
| 57 |
:py:class:`~.compiler.Compilation` hierarchy/tree. We lookup in a |
| 58 |
reverse order the parent ``X`` of ``Y`` and traverse backwards from |
| 59 |
the index in the parent where ``Y`` exists to all siblings (and |
| 60 |
children of those siblings) in ``X`` that we encounter in this |
| 61 |
backwards search (if a sibling is a flow itself, its atom(s) |
| 62 |
will be recursively expanded and included). This collection will |
| 63 |
then be assumed to be at the same scope. This is what is called |
| 64 |
a *potential* single scope, to make an *actual* scope we remove the |
| 65 |
items from the *potential* scope that are **not** predecessors |
| 66 |
of ``Y`` to form the *actual* scope which we then yield back. |
| 67 |
|
| 68 |
Then for additional scopes we continue up the tree, by finding the |
| 69 |
parent of ``X`` (lets call it ``Z``) and perform the same operation, |
| 70 |
going through the children in a reverse manner from the index in |
| 71 |
parent ``Z`` where ``X`` was located. This forms another *potential* |
| 72 |
scope which we provide back as an *actual* scope after reducing the |
| 73 |
potential set to only include predecessors previously gathered. We |
| 74 |
then repeat this process until we no longer have any parent |
| 75 |
nodes (aka we have reached the top of the tree) or we run out of |
| 76 |
predecessors. |
| 77 |
""" |
| 78 |
graph = self._execution_graph |
| 79 |
if self._predecessors is None: |
| 80 |
predecessors = { |
| 81 |
node for node in graph.bfs_predecessors_iter(self._atom) |
| 82 |
if graph.nodes[node]['kind'] in co.ATOMS} |
| 83 |
self._predecessors = predecessors.copy() |
| 84 |
else: |
| 85 |
predecessors = self._predecessors.copy() |
| 86 |
last = self._node |
| 87 |
for lvl, parent in enumerate(self._node.path_iter(include_self=False)): |
| 88 |
if not predecessors: |
| 89 |
break |
| 90 |
last_idx = parent.index(last.item) |
| 91 |
try: |
| 92 |
visible, removals = self._level_cache[lvl] |
| 93 |
predecessors = predecessors - removals |
| 94 |
except KeyError: |
| 95 |
visible = [] |
| 96 |
removals = set() |
| 97 |
atom_it = tr.depth_first_reverse_iterate( |
| 98 |
parent, start_from_idx=last_idx) |
| 99 |
for atom in atom_it: |
| 100 |
if atom in predecessors: |
| 101 |
predecessors.remove(atom) |
| 102 |
removals.add(atom) |
| 103 |
visible.append(atom) |
| 104 |
if not predecessors: |
| 105 |
break |
| 106 |
self._level_cache[lvl] = (visible, removals) |
| 107 |
if LOG.isEnabledFor(logging.TRACE): |
| 108 |
visible_names = [a.name for a in visible] |
| 109 |
LOG.trace("Scope visible to '%s' (limited by parent '%s'" |
| 110 |
" index < %s) is: %s", self._atom, |
| 111 |
parent.item.name, last_idx, visible_names) |
| 112 |
if self._names_only: |
| 113 |
yield [a.name for a in visible] |
| 114 |
else: |
| 115 |
yield visible |
| 116 |
last = parent |