###############################################################################
# (c) Copyright 2019-2021 CERN for the benefit of the LHCb Collaboration #
# #
# This software is distributed under the terms of the GNU General Public #
# Licence version 3 (GPL Version 3), copied verbatim in the file "COPYING". #
# #
# In applying this licence, CERN does not waive the privileges and immunities #
# granted to it by virtue of its status as an Intergovernmental Organization #
# or submit itself to any jurisdiction. #
###############################################################################
"""
The control flow of an application configured with PyConf, such as Moore,
defines the order in which algorithms should run.
Each step in the control flow evaluates a *decision*, which indicates whether
the step was successful or not. The overall decision of the application depends
on what the total control flow evaluates to.
Concretely, the control flow in the example of Moore looks something like this::
MooreNode (LAZY_AND)
*-- HLTLinesNode (NONLAZY_OR)
| +-- Hlt2CharmPhysicsLineNode (LAZY_AND)
| | *-- PVFilter
| | *-- D2HHHCombiner
| +-- Hlt2DiMuonPhysicsLineNode (LAZY_AND)
| | *-- PVFilter
| | *-- MuMuCombiner
| +-- Hlt2LumiLineNode (LAZY_AND)
| | *-- ODINBeamFilter
| | *-- LumiCounter
| +-- Hlt2InclusiveBPhysicsLineNode (LAZY_AND)
| *-- PVFilter
| *-- TwoBodyBCombiner
*-- PersistencyNode (LAZY_AND)
*-- DecReports
*-- TurboWriter
If we think about how the trigger needs to come to its decision, we can
understand what the specific pieces mean and why the control flow looks like
it does:
1. For a start, every trigger line should run, and should do so independently of the decisions of other lines.
2. Each line runs a sequence of steps to evaluate its own decision, e.g. it first requires some non-zero number of primary vertices, and then further requires some combiner to produce candidates.
3. If at least one line produces a positive decision ('yes'/'no', 'fired'/'did not fire'), the event should be written out.
So, the control flow looks the way it does in order to evaluate the total trigger decision in the way we want.
Nodes and algorithms
--------------------
A control flow *node* has some number of *children*, and makes its decision
based on the combination of the decisions of its children.
There are two ways we can combine decisions in one of these so-called *composite* nodes:
1. Boolean ``AND``, where all of the children must produce a positive decision.
2. Boolean ``OR``, where at least one of the children must produce a positive decision.
When evaluating a boolean expression, we can choose to 'short circuit' in
certain cases. With an ``AND`` decision, we could choose to not run the next
child if the current child gives a negative decision, because we know the
total expression can now never be positive. With an ``OR`` decision, we could
similarly stop as soon as one child has a positive decision. The ``LAZY`` and
``NONLAZY`` attributes on each node specify this behaviour.
The ``Moore`` node is ``LAZY_AND``. This is because we don't want to write
anything out if the decision of the trigger lines was negative, so we short
circuit in that case.
The ``HLTLines`` node is a ``NONLAZY_OR``. If one line has a positive
decision we already know the event will be saved, but we must evaluate all
lines as they are independent. We always want to know what every line did in
every event.
We have one other type of component in the control flow, which has no children.
These are *algorithms*, and it is these that ultimately make decisions. They
typically take some input, and then return a 'yes' or 'no' based on the
properties of that input.
A primary vertex filter algorithm will return a positive decision if there's
at least one PV in the event.
A prescaler algorithm takes no input, instead evaluating its decision based
on the value of a random number.
All together combining control flow nodes and algorithms allows us to
express complex decision paths in a modular way.
Data flow
---------
Implicit in the control flow is the *data flow*. Notice above that we don't
specify that the reconstruction should run, even though we need the
reconstruction to run the PV filters!
In brief, satisfying data dependencies is the job of the scheduler,
``HLTControlFlowMgr``. When the scheduler needs to run an algorithm, it takes
care of running the algorithms in the data dependency tree. (It's clever
enough to not run the same algorithm multiple times, in case it appears in
multiple data dependency trees.)
We only need to explicitly take care of the control flow, which the scheduler
is also responsible for executing.
API
---
The objects below are what are used to construct the control flow in the
configuration. A `CompositeNode <PyConf.control_flow.CompositeNode>` instance
represents a composite node. The `NodeLogic <PyConf.control_flow.NodeLogic>`
enum is used to specify how child decisions should be combined, ``AND`` or
``OR``, and the whether to short circuit or not, ``LAZY`` or ``NONLAZY``.
.. autoclass:: PyConf.control_flow.NodeLogic
:members:
.. autoclass:: PyConf.control_flow.CompositeNode
:members:
"""
from __future__ import absolute_import, division, print_function
try:
from html import escape as html_escape
except ImportError:
from cgi import escape as html_escape
from enum import Enum
import pydot
from collections.abc import Generator
from typing import Any
from .components import is_algorithm
from .dataflow import DataHandle
__all__ = [
'NodeLogic',
'CompositeNode',
]
# FIXME not sure if i want to have this or rather just strings
[docs]class NodeLogic(Enum):
"""Node control flow behaviour.
Each node contains an ordered set of subnodes/child nodes. These are
processed in order one by one until the node can return True or False.
Whether a node can return depends on its control flow behaviour.
"""
#: Return False and stop processing as soon as a subnode returns False
LAZY_AND = 'LAZY_AND'
#: Return False if any subnode returns False, but do process all subnodes
NONLAZY_AND = 'NONLAZY_AND'
#: Return True and stop processing as soon as a subnode returns True
LAZY_OR = 'LAZY_OR'
#: Return True if any subnode returns True, but do process all subnodes
NONLAZY_OR = 'NONLAZY_OR'
#: Return the negation of the subnode
NOT = 'NOT'
[docs]class CompositeNode(object):
"""A container for a set of subnodes/child nodes."""
def __init__(self,
name,
children,
combine_logic=NodeLogic.LAZY_AND,
force_order=True):
if not isinstance(combine_logic, NodeLogic):
raise TypeError('combine_logic must take an instance of NodeLogic')
if not children:
raise ValueError('children must be a non-empty iterable')
self.name = name
self.children = tuple(
c.producer if isinstance(c, DataHandle) else c for c in children)
if not all(
isinstance(c, CompositeNode) or is_algorithm(c)
for c in self.children):
for c in self.children:
if not (isinstance(c, CompositeNode) or is_algorithm(c)):
print(c)
print(type(c))
if not isinstance(c, CompositeNode):
print("Not a composite node")
if not is_algorithm(c):
print("Not an algorithm")
raise TypeError(
"The list of children may only contain instances of types Algorithm or CompositeNode"
)
self.combine_logic = combine_logic
self.force_order = force_order
def __eq__(self, other):
return self.name == other.name and \
self.children == other.children and \
self.combine_logic == other.combine_logic and \
self.force_order == other.force_order
def __hash__(self):
return hash((
self.name,
self.children,
self.combine_logic,
self.force_order,
))
@property # for API compatibility with Algorithm
def fullname(self):
return self.name
def represent(self):
return (self.name, self.combine_logic.value,
[c.fullname for c in self.children], self.force_order)
@property
def uses_and(self):
return self.combine_logic in (NodeLogic.LAZY_AND,
NodeLogic.NONLAZY_AND)
@property
def uses_or(self):
return self.combine_logic in (NodeLogic.LAZY_OR, NodeLogic.NONLAZY_OR)
@property
def uses_not(self):
return self.combine_logic == NodeLogic.NOT
@property
def is_lazy(self):
return self.combine_logic in (NodeLogic.LAZY_AND, NodeLogic.LAZY_OR)
def _graph(self, graph):
own_name = html_escape(self.name)
sg = pydot.Subgraph(graph_name='cluster_' + own_name)
label = ('<<B>{}</B><BR/>{}, {}>'.format(
own_name,
str(self.combine_logic).replace('NodeLogic.', ''),
'ordered' if self.force_order else 'unordered'))
sg.set_label(label)
sg.set_edge_defaults(dir='forward' if self.force_order else 'none')
node = prev_node = None
for child in self.children:
if is_algorithm(child):
# Must name nodes uniquely within a node, otherwise they will
# only be drawn one (which makes sense for the *data* flow!)
node = pydot.Node(
html_escape('{}_{}'.format(self.name, child.fullname)),
label=child.fullname)
sg.add_node(node)
else:
node = child._graph(sg)
if prev_node is not None:
# When drawing edges to/from subgraphs, the target node must be
# a node inside the subgraph, which we take as the first.
# However we want the arrow to start/from from the edge of the
# subgraph, so must set the ltail/lhead attribute appropriately
if isinstance(prev_node, pydot.Subgraph):
tail_node = _find_first_node(prev_node)
ltail = prev_node.get_name()
else:
tail_node = prev_node
ltail = None
if isinstance(node, pydot.Subgraph):
head_node = _find_first_node(node)
lhead = node.get_name()
else:
head_node = node
lhead = None
edge = pydot.Edge(tail_node, head_node)
if ltail is not None:
edge.set_ltail(ltail)
if lhead is not None:
edge.set_lhead(lhead)
sg.add_edge(edge)
prev_node = node
if node is None:
node = pydot.Node('{}_empty'.format(own_name), label='Empty node')
sg.add_node(node)
graph.add_subgraph(sg)
return sg
def _find_first_node(node):
"""Return the first pydot.Node object found within the node tree."""
# The 'edge' node defines edge defaults; we can't create edges to/from it
if isinstance(node, pydot.Node) and node.get_name() != 'edge':
return node
elif isinstance(node, pydot.Subgraph):
# Recurse down in to the subgraph's nodes and subgraphs
subnodes = node.get_nodes() + node.get_subgraphs()
for subnode in [_f for _f in map(_find_first_node, subnodes) if _f]:
# Return the first node we find
return subnode
return None
def traverse_node_and_children(node: CompositeNode) -> Generator[Any]:
"""Traverse node and its children recursively and yield them.
Args:
node (CompositeNode): The node to traverse.
Yields:
Generator[Any]: Node, Child/Subnode or Any leaf.
"""
yield node
for child in getattr(node, "children", []): # skip childless nodes
for childs_child in traverse_node_and_children(child):
yield childs_child