""" Compositional Performance Analysis Algorithms for Path Latencies

| Copyright (C) 2007-2017 Jonas Diemer, Philip Axer, Johannes Schlatow
| TU Braunschweig, Germany
| All rights reserved.
| See LICENSE file for copyright and license details.

:Authors:
         - Jonas Diemer
         - Philip Axer
         - Johannes Schlatow

Description
-----------

This module contains methods for the ananlysis of path latencies.
It should be imported in scripts that do the analysis.
"""

from __future__ import absolute_import
from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division

from . import options
from . import model
from . import util

import math


def end_to_end_latency(path, task_results, n=1 , task_overhead=0,
                       path_overhead=0, **kwargs):
    """ Computes the worst-/best-case e2e latency for n tokens to pass the path.
    The constant path.overhead is added to the best- and worst-case latencies.

    :param path: the path
    :type path: model.Path
    :param n:  amount of events
    :type n: integer
    :param task_overhead: A constant task_overhead is added once per task to both min and max latency
    :type task_overhead: integer
    :param path_overhead:  A constant path_overhead is added once per path to both min and max latency
    :type path_overhead: integer
    :rtype: tuple (best-case latency, worst-case latency)
    """

    if options.get_opt('e2e_improved') == True:
        (lmin, lmax) = end_to_end_latency_improved(path, task_results,
                                                   n, **kwargs)
    else:
        (lmin, lmax) = end_to_end_latency_classic(path, task_results,
                                                  n, **kwargs)

    for t in path.tasks:
        # implcitly check if t is a junction
        if t in task_results:
            # add per-task overheads
            lmin += task_overhead
            lmax += task_overhead

    # add per-path overhead
    lmin += path_overhead + path.overhead
    lmax += path_overhead + path.overhead

    return (lmin, lmax)

def end_to_end_latency_classic(path, task_results, n=1, injection_rate='max', **kwargs):
    """ Computes the worst-/best-case end-to-end latency
    Assumes that all tasks in the system have successfully been analyzed.
    Assumes that events enter the path at maximum/minumum rate.
    The end-to-end latency is the sum of the individual task's
    worst-case response times.

    This corresponds to Definition 7.3 in [Richter2005]_.

    :param path: the path
    :type path: model.Path
    :param n:  amount of events
    :type n: integer
    :param injection_rate: assumed injection rate is maximum or minimum
    :type injection_rate: string 'max' or 'min'
    :rtype: tuple (best case latency, worst case latency)
    """

    lmax = 0
    lmin = 0

    # check if path is a list of Tasks or a Path object
    tasks = path
    if isinstance(path, model.Path):
        tasks = path.tasks

    for t in tasks:
        # implcitly check if t is a junction
        if t in task_results:
            # sum up best- and worst-case response times
            lmax += task_results[t].wcrt
            lmin += task_results[t].bcrt
        elif isinstance(t, model.Junction):
            # add sampling delay induced by the junction (if available)
            prev_task = tasks[tasks.index(t)-1]
            if prev_task in t.analysis_results:
                lmin += t.analysis_results[prev_task].bcrt
                lmax += t.analysis_results[prev_task].wcrt
        else:
            print("Warning: no task_results for task %s" % t.name)

    if injection_rate == 'max':
        # add the eastliest possible release of event n
        lmax += tasks[0].in_event_model.delta_min(n)

    elif injection_rate == 'min':
        # add the latest possible release of event n
        lmax += tasks[0].in_event_model.delta_plus(n)

    # add the earliest possible release of event n
    lmin += tasks[0].in_event_model.delta_min(n)

    return lmin, lmax


def _event_arrival_path(path, n, e_0=0):
    """ Returns the latest arrival time of the n-th event
    with respect to an event 0 of task 0 (first task in path)

    This is :math:`e_0(n)` from Lemma 1 in [Schliecker2009recursive]_.
    """
    # if e_0 is None:
        # the entry time of the first event

    if n > 0:
        e = e_0 + path.tasks[0].in_event_model.delta_plus(n + 1)
    elif n < 0:
        e = e_0 - path.tasks[0].in_event_model.delta_min(-n + 1)
    else:
        e = 0  # same event, so the difference is 0

    return e


def _event_exit_path(path, task_results, i, n, e_0=0):
    """ Returns the latest exit time of the n-th event
    relative to the arrival of an event 0
    (cf. Lemma 2 in [Schliecker2009recursive]_)
    In contrast to Lemma 2, k_max is set so that all busy times
    are taken into account.
    """

    # logger.debug("calculating exit for task %d, n=%d" % (i, n))

    if i == -1:
        # The exit of task -1 is the arrival of task 0.
        e = _event_arrival_path(path, n, e_0)
    elif path.tasks[i] not in task_results:
        # skip task if there are no results for this
        # (this may happen if, e.g., a chain analysis has been performed)
        return _event_exit_path(path, task_results, i-1, n, e_0)
    else:
        e = float('-inf')
        k_max = len(task_results[path.tasks[i]].busy_times)
        # print("k_max:",k_max)
        for k in range(1, k_max):
            e_k = _event_exit_path(path, task_results, i - 1, n - k + 1, e_0) + \
                    task_results[path.tasks[i]].busy_times[k]

            # print("e_k:",e_k)
            if e_k > e:
                # print("task %d, n=%d k=%d, new e=%d" % (i, n, k, e_k))
                e = e_k

    # print("exit for task %d, n=%d is %d" % (i, n, e))
    return e


def end_to_end_latency_improved(path, task_results, n=1, e_0=0, **kwargs):
    """ Performs the path analysis presented in [Schliecker2009recursive]_,
    which improves results compared to end_to_end_latency() for
    n>1 and bursty event models.
    lat(n)
    """
    lmax = 0
    lmin = 0
    lmax = _event_exit_path(path, task_results, len(path.tasks) - 1, n - 1, e_0) - e_0

    for t in path.tasks:
        if isinstance(t, model.Task) and t in task_results:
            # sum up best-case response times
            lmin += task_results[t].bcrt
        elif isinstance(t, model.Junction):
            print("Error: path contains junctions")
        else:
            print("Warning: no task_results for task %s" % t.name)

    # add the earliest possible release of event n
    # TODO: Can lmin be improved?
    lmin += path.tasks[0].in_event_model.delta_min(n)

    return lmin, lmax

def cause_effect_chain_data_age(chain, task_results, details=None):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    return cause_effect_chain(chain, task_results, details, 'data-age')

def cause_effect_chain_reaction_time(chain, task_results, details=None):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    return cause_effect_chain(chain, task_results, details, 'reaction-time')

def cause_effect_chain(chain, task_results, details=None, semantics='data-age'):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """

    sequence = chain.task_sequence(writers_only=True)

    if details is None:
        details = dict()

    periods = [_period(t) for t in sequence]
    if util.GCD(periods) != min(periods):
        print("Error: cause-effect chain analysis requires harmonic periods")

    l_max = _phi(sequence[0]) + _jitter(sequence[0])
    details[sequence[0].name+'-PHI+J'] = l_max
    for i in range(len(sequence)):
        # add write-to-read delay for all but the last task
        if i < len(sequence)-1:
            if semantics == 'data-age':
                # add write to read delay
                delay = _calculate_backward_distance(sequence[i], sequence[i+1], task_results, 
                        details=details)
            elif semantics == 'reaction-time':
                delay = _calculate_forward_distance(sequence[i], sequence[i+1], task_results, 
                        details=details)
            else:
                raise NotImplementedException()

            l_max += delay

        # add read-to-write delay (response time) for all tasks
        delay = task_results[sequence[i]].wcrt
        details[sequence[i].name+'-WCRT'] = delay
        l_max += delay

    return l_max

def _phi(task):
    if hasattr(task.in_event_model, 'phi'):
        return task.in_event_model.phi
    else:
        return 0

def _period(task):
    return task.in_event_model.P

def _jitter(task):
    if hasattr(task.in_event_model, 'J'):
        return task.in_event_model.J
    else:
        return 0

def _calculate_backward_distance(writer, reader, task_results, details):
    """ computes backward distance (for data age)
    """

    if _period(reader) < _period(writer): # oversampling 

        candidates = set()

        if _period(writer) % _period(reader) != 0:
            candidates.add(_period(writer) + task_results[writer].wcrt - task_results[writer].bcrt)
        else:

            for n in range(int(math.ceil(_period(writer)/_period(reader)))):
                candidates.add(_rplus(reader, task_results, n) - _wmin(writer, task_results, 0))

                # include previous cycle?
                if _wplus(writer, task_results) > _rmin(reader, task_results, n):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(writer, task_results, -1))

        result = max(candidates)

    else: # undersampling or same period

        candidates = set()
        candidates.add(_period(writer) + task_results[writer].wcrt - task_results[writer].bcrt)

        if _period(reader) % _period(writer) == 0:

            # include previous cycle?
            if _wplus(writer, task_results) > _rmin(reader, task_results):
                candidates.add(_rplus(reader, task_results) - _wmin(writer, task_results, -1))

            # include all other possible writers
            for n in range(int(math.ceil(_period(reader)/_period(writer)))):
                if _wplus(writer, task_results, n) <= _rplus(reader, task_results):
                    candidates.add(_rplus(reader, task_results) - _wmin(writer, task_results, n))

        result = min([c for c in candidates if c >= 0])

    details[writer.name+'-'+reader.name+'-delay'] = result
    return result

def _calculate_forward_distance(writer, reader, task_results, details):
    """ computes forward distance (for reaction time)
    """

    if _period(reader) < _period(writer): # oversampling 

        candidates = set()
        candidates.add(_period(reader))

        if _period(writer) % _period(reader) == 0:

            for n in range(int(math.ceil(_period(writer)/_period(reader)))):
                if _rmin(reader, task_results, n) >= _wplus(writer, task_results, 0):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(writer, task_results, 0))

                # include previous cycle?
                if _wplus(writer, task_results) > _rmin(reader, task_results, n):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(writer, task_results, -1))

        result = min([c for c in candidates if c >= 0])

    else: # undersampling or same period

        candidates = set()

        if _period(reader) % _period(writer) != 0:
            candidates.add(_period(reader))
        else:

            # include all possible writers
            for n in range(int(math.ceil(_period(reader)/_period(writer)))):
                candidates.add(_rplus(reader, task_results) - _wmin(writer, task_results, n))

                # if write time can be earlier than read time, add distance to next reader
                if _wplus(writer, task_results, n) > _rmin(reader, task_results):
                    candidates.add(_rplus(reader, task_results, 1) - _wmin(writer, task_results, n))

        result = max(candidates)

    details[writer.name+'-'+reader.name+'-delay'] = result
    return result

def _wplus(writer, task_results, n=0):
    return n*_period(writer) + _phi(writer) + task_results[writer].wcrt + _jitter(writer)

def _wmin(writer, task_results, n=0):
    return n*_period(writer) + _phi(writer) + task_results[writer].bcrt - _jitter(writer)

def _rplus(reader, task_results, n=0):
    return _wplus(reader, task_results, n) - task_results[reader].bcrt

def _rmin(reader, task_results, n=0):
    return n*_period(reader) + _phi(reader) - _jitter(reader)

# vim: tabstop=4 expandtab shiftwidth=4 softtabstop=4

0559d7c0c92e2232dc7edf703df7ede39ad2f1c9
<mask token>


def end_to_end_latency(path, task_results, n=1, task_overhead=0,
    path_overhead=0, **kwargs):
    """ Computes the worst-/best-case e2e latency for n tokens to pass the path.
    The constant path.overhead is added to the best- and worst-case latencies.

    :param path: the path
    :type path: model.Path
    :param n:  amount of events
    :type n: integer
    :param task_overhead: A constant task_overhead is added once per task to both min and max latency
    :type task_overhead: integer
    :param path_overhead:  A constant path_overhead is added once per path to both min and max latency
    :type path_overhead: integer
    :rtype: tuple (best-case latency, worst-case latency)
    """
    if options.get_opt('e2e_improved') == True:
        lmin, lmax = end_to_end_latency_improved(path, task_results, n, **
            kwargs)
    else:
        lmin, lmax = end_to_end_latency_classic(path, task_results, n, **kwargs
            )
    for t in path.tasks:
        if t in task_results:
            lmin += task_overhead
            lmax += task_overhead
    lmin += path_overhead + path.overhead
    lmax += path_overhead + path.overhead
    return lmin, lmax


<mask token>


def _event_arrival_path(path, n, e_0=0):
    """ Returns the latest arrival time of the n-th event
    with respect to an event 0 of task 0 (first task in path)

    This is :math:`e_0(n)` from Lemma 1 in [Schliecker2009recursive]_.
    """
    if n > 0:
        e = e_0 + path.tasks[0].in_event_model.delta_plus(n + 1)
    elif n < 0:
        e = e_0 - path.tasks[0].in_event_model.delta_min(-n + 1)
    else:
        e = 0
    return e


<mask token>


def cause_effect_chain_data_age(chain, task_results, details=None):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    return cause_effect_chain(chain, task_results, details, 'data-age')


<mask token>


def _period(task):
    return task.in_event_model.P


def _jitter(task):
    if hasattr(task.in_event_model, 'J'):
        return task.in_event_model.J
    else:
        return 0


<mask token>


def _calculate_forward_distance(writer, reader, task_results, details):
    """ computes forward distance (for reaction time)
    """
    if _period(reader) < _period(writer):
        candidates = set()
        candidates.add(_period(reader))
        if _period(writer) % _period(reader) == 0:
            for n in range(int(math.ceil(_period(writer) / _period(reader)))):
                if _rmin(reader, task_results, n) >= _wplus(writer,
                    task_results, 0):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(
                        writer, task_results, 0))
                if _wplus(writer, task_results) > _rmin(reader, task_results, n
                    ):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(
                        writer, task_results, -1))
        result = min([c for c in candidates if c >= 0])
    else:
        candidates = set()
        if _period(reader) % _period(writer) != 0:
            candidates.add(_period(reader))
        else:
            for n in range(int(math.ceil(_period(reader) / _period(writer)))):
                candidates.add(_rplus(reader, task_results) - _wmin(writer,
                    task_results, n))
                if _wplus(writer, task_results, n) > _rmin(reader, task_results
                    ):
                    candidates.add(_rplus(reader, task_results, 1) - _wmin(
                        writer, task_results, n))
        result = max(candidates)
    details[writer.name + '-' + reader.name + '-delay'] = result
    return result


def _wplus(writer, task_results, n=0):
    return n * _period(writer) + _phi(writer) + task_results[writer
        ].wcrt + _jitter(writer)


def _wmin(writer, task_results, n=0):
    return n * _period(writer) + _phi(writer) + task_results[writer
        ].bcrt - _jitter(writer)


def _rplus(reader, task_results, n=0):
    return _wplus(reader, task_results, n) - task_results[reader].bcrt


<mask token>

<mask token>


def end_to_end_latency(path, task_results, n=1, task_overhead=0,
    path_overhead=0, **kwargs):
    """ Computes the worst-/best-case e2e latency for n tokens to pass the path.
    The constant path.overhead is added to the best- and worst-case latencies.

    :param path: the path
    :type path: model.Path
    :param n:  amount of events
    :type n: integer
    :param task_overhead: A constant task_overhead is added once per task to both min and max latency
    :type task_overhead: integer
    :param path_overhead:  A constant path_overhead is added once per path to both min and max latency
    :type path_overhead: integer
    :rtype: tuple (best-case latency, worst-case latency)
    """
    if options.get_opt('e2e_improved') == True:
        lmin, lmax = end_to_end_latency_improved(path, task_results, n, **
            kwargs)
    else:
        lmin, lmax = end_to_end_latency_classic(path, task_results, n, **kwargs
            )
    for t in path.tasks:
        if t in task_results:
            lmin += task_overhead
            lmax += task_overhead
    lmin += path_overhead + path.overhead
    lmax += path_overhead + path.overhead
    return lmin, lmax


<mask token>


def _event_arrival_path(path, n, e_0=0):
    """ Returns the latest arrival time of the n-th event
    with respect to an event 0 of task 0 (first task in path)

    This is :math:`e_0(n)` from Lemma 1 in [Schliecker2009recursive]_.
    """
    if n > 0:
        e = e_0 + path.tasks[0].in_event_model.delta_plus(n + 1)
    elif n < 0:
        e = e_0 - path.tasks[0].in_event_model.delta_min(-n + 1)
    else:
        e = 0
    return e


def _event_exit_path(path, task_results, i, n, e_0=0):
    """ Returns the latest exit time of the n-th event
    relative to the arrival of an event 0
    (cf. Lemma 2 in [Schliecker2009recursive]_)
    In contrast to Lemma 2, k_max is set so that all busy times
    are taken into account.
    """
    if i == -1:
        e = _event_arrival_path(path, n, e_0)
    elif path.tasks[i] not in task_results:
        return _event_exit_path(path, task_results, i - 1, n, e_0)
    else:
        e = float('-inf')
        k_max = len(task_results[path.tasks[i]].busy_times)
        for k in range(1, k_max):
            e_k = _event_exit_path(path, task_results, i - 1, n - k + 1, e_0
                ) + task_results[path.tasks[i]].busy_times[k]
            if e_k > e:
                e = e_k
    return e


def end_to_end_latency_improved(path, task_results, n=1, e_0=0, **kwargs):
    """ Performs the path analysis presented in [Schliecker2009recursive]_,
    which improves results compared to end_to_end_latency() for
    n>1 and bursty event models.
    lat(n)
    """
    lmax = 0
    lmin = 0
    lmax = _event_exit_path(path, task_results, len(path.tasks) - 1, n - 1, e_0
        ) - e_0
    for t in path.tasks:
        if isinstance(t, model.Task) and t in task_results:
            lmin += task_results[t].bcrt
        elif isinstance(t, model.Junction):
            print('Error: path contains junctions')
        else:
            print('Warning: no task_results for task %s' % t.name)
    lmin += path.tasks[0].in_event_model.delta_min(n)
    return lmin, lmax


def cause_effect_chain_data_age(chain, task_results, details=None):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    return cause_effect_chain(chain, task_results, details, 'data-age')


def cause_effect_chain_reaction_time(chain, task_results, details=None):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    return cause_effect_chain(chain, task_results, details, 'reaction-time')


<mask token>


def _period(task):
    return task.in_event_model.P


def _jitter(task):
    if hasattr(task.in_event_model, 'J'):
        return task.in_event_model.J
    else:
        return 0


def _calculate_backward_distance(writer, reader, task_results, details):
    """ computes backward distance (for data age)
    """
    if _period(reader) < _period(writer):
        candidates = set()
        if _period(writer) % _period(reader) != 0:
            candidates.add(_period(writer) + task_results[writer].wcrt -
                task_results[writer].bcrt)
        else:
            for n in range(int(math.ceil(_period(writer) / _period(reader)))):
                candidates.add(_rplus(reader, task_results, n) - _wmin(
                    writer, task_results, 0))
                if _wplus(writer, task_results) > _rmin(reader, task_results, n
                    ):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(
                        writer, task_results, -1))
        result = max(candidates)
    else:
        candidates = set()
        candidates.add(_period(writer) + task_results[writer].wcrt -
            task_results[writer].bcrt)
        if _period(reader) % _period(writer) == 0:
            if _wplus(writer, task_results) > _rmin(reader, task_results):
                candidates.add(_rplus(reader, task_results) - _wmin(writer,
                    task_results, -1))
            for n in range(int(math.ceil(_period(reader) / _period(writer)))):
                if _wplus(writer, task_results, n) <= _rplus(reader,
                    task_results):
                    candidates.add(_rplus(reader, task_results) - _wmin(
                        writer, task_results, n))
        result = min([c for c in candidates if c >= 0])
    details[writer.name + '-' + reader.name + '-delay'] = result
    return result


def _calculate_forward_distance(writer, reader, task_results, details):
    """ computes forward distance (for reaction time)
    """
    if _period(reader) < _period(writer):
        candidates = set()
        candidates.add(_period(reader))
        if _period(writer) % _period(reader) == 0:
            for n in range(int(math.ceil(_period(writer) / _period(reader)))):
                if _rmin(reader, task_results, n) >= _wplus(writer,
                    task_results, 0):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(
                        writer, task_results, 0))
                if _wplus(writer, task_results) > _rmin(reader, task_results, n
                    ):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(
                        writer, task_results, -1))
        result = min([c for c in candidates if c >= 0])
    else:
        candidates = set()
        if _period(reader) % _period(writer) != 0:
            candidates.add(_period(reader))
        else:
            for n in range(int(math.ceil(_period(reader) / _period(writer)))):
                candidates.add(_rplus(reader, task_results) - _wmin(writer,
                    task_results, n))
                if _wplus(writer, task_results, n) > _rmin(reader, task_results
                    ):
                    candidates.add(_rplus(reader, task_results, 1) - _wmin(
                        writer, task_results, n))
        result = max(candidates)
    details[writer.name + '-' + reader.name + '-delay'] = result
    return result


def _wplus(writer, task_results, n=0):
    return n * _period(writer) + _phi(writer) + task_results[writer
        ].wcrt + _jitter(writer)


def _wmin(writer, task_results, n=0):
    return n * _period(writer) + _phi(writer) + task_results[writer
        ].bcrt - _jitter(writer)


def _rplus(reader, task_results, n=0):
    return _wplus(reader, task_results, n) - task_results[reader].bcrt


<mask token>

<mask token>


def end_to_end_latency(path, task_results, n=1, task_overhead=0,
    path_overhead=0, **kwargs):
    """ Computes the worst-/best-case e2e latency for n tokens to pass the path.
    The constant path.overhead is added to the best- and worst-case latencies.

    :param path: the path
    :type path: model.Path
    :param n:  amount of events
    :type n: integer
    :param task_overhead: A constant task_overhead is added once per task to both min and max latency
    :type task_overhead: integer
    :param path_overhead:  A constant path_overhead is added once per path to both min and max latency
    :type path_overhead: integer
    :rtype: tuple (best-case latency, worst-case latency)
    """
    if options.get_opt('e2e_improved') == True:
        lmin, lmax = end_to_end_latency_improved(path, task_results, n, **
            kwargs)
    else:
        lmin, lmax = end_to_end_latency_classic(path, task_results, n, **kwargs
            )
    for t in path.tasks:
        if t in task_results:
            lmin += task_overhead
            lmax += task_overhead
    lmin += path_overhead + path.overhead
    lmax += path_overhead + path.overhead
    return lmin, lmax


<mask token>


def _event_arrival_path(path, n, e_0=0):
    """ Returns the latest arrival time of the n-th event
    with respect to an event 0 of task 0 (first task in path)

    This is :math:`e_0(n)` from Lemma 1 in [Schliecker2009recursive]_.
    """
    if n > 0:
        e = e_0 + path.tasks[0].in_event_model.delta_plus(n + 1)
    elif n < 0:
        e = e_0 - path.tasks[0].in_event_model.delta_min(-n + 1)
    else:
        e = 0
    return e


def _event_exit_path(path, task_results, i, n, e_0=0):
    """ Returns the latest exit time of the n-th event
    relative to the arrival of an event 0
    (cf. Lemma 2 in [Schliecker2009recursive]_)
    In contrast to Lemma 2, k_max is set so that all busy times
    are taken into account.
    """
    if i == -1:
        e = _event_arrival_path(path, n, e_0)
    elif path.tasks[i] not in task_results:
        return _event_exit_path(path, task_results, i - 1, n, e_0)
    else:
        e = float('-inf')
        k_max = len(task_results[path.tasks[i]].busy_times)
        for k in range(1, k_max):
            e_k = _event_exit_path(path, task_results, i - 1, n - k + 1, e_0
                ) + task_results[path.tasks[i]].busy_times[k]
            if e_k > e:
                e = e_k
    return e


def end_to_end_latency_improved(path, task_results, n=1, e_0=0, **kwargs):
    """ Performs the path analysis presented in [Schliecker2009recursive]_,
    which improves results compared to end_to_end_latency() for
    n>1 and bursty event models.
    lat(n)
    """
    lmax = 0
    lmin = 0
    lmax = _event_exit_path(path, task_results, len(path.tasks) - 1, n - 1, e_0
        ) - e_0
    for t in path.tasks:
        if isinstance(t, model.Task) and t in task_results:
            lmin += task_results[t].bcrt
        elif isinstance(t, model.Junction):
            print('Error: path contains junctions')
        else:
            print('Warning: no task_results for task %s' % t.name)
    lmin += path.tasks[0].in_event_model.delta_min(n)
    return lmin, lmax


def cause_effect_chain_data_age(chain, task_results, details=None):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    return cause_effect_chain(chain, task_results, details, 'data-age')


def cause_effect_chain_reaction_time(chain, task_results, details=None):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    return cause_effect_chain(chain, task_results, details, 'reaction-time')


def cause_effect_chain(chain, task_results, details=None, semantics='data-age'
    ):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    sequence = chain.task_sequence(writers_only=True)
    if details is None:
        details = dict()
    periods = [_period(t) for t in sequence]
    if util.GCD(periods) != min(periods):
        print('Error: cause-effect chain analysis requires harmonic periods')
    l_max = _phi(sequence[0]) + _jitter(sequence[0])
    details[sequence[0].name + '-PHI+J'] = l_max
    for i in range(len(sequence)):
        if i < len(sequence) - 1:
            if semantics == 'data-age':
                delay = _calculate_backward_distance(sequence[i], sequence[
                    i + 1], task_results, details=details)
            elif semantics == 'reaction-time':
                delay = _calculate_forward_distance(sequence[i], sequence[i +
                    1], task_results, details=details)
            else:
                raise NotImplementedException()
            l_max += delay
        delay = task_results[sequence[i]].wcrt
        details[sequence[i].name + '-WCRT'] = delay
        l_max += delay
    return l_max


def _phi(task):
    if hasattr(task.in_event_model, 'phi'):
        return task.in_event_model.phi
    else:
        return 0


def _period(task):
    return task.in_event_model.P


def _jitter(task):
    if hasattr(task.in_event_model, 'J'):
        return task.in_event_model.J
    else:
        return 0


def _calculate_backward_distance(writer, reader, task_results, details):
    """ computes backward distance (for data age)
    """
    if _period(reader) < _period(writer):
        candidates = set()
        if _period(writer) % _period(reader) != 0:
            candidates.add(_period(writer) + task_results[writer].wcrt -
                task_results[writer].bcrt)
        else:
            for n in range(int(math.ceil(_period(writer) / _period(reader)))):
                candidates.add(_rplus(reader, task_results, n) - _wmin(
                    writer, task_results, 0))
                if _wplus(writer, task_results) > _rmin(reader, task_results, n
                    ):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(
                        writer, task_results, -1))
        result = max(candidates)
    else:
        candidates = set()
        candidates.add(_period(writer) + task_results[writer].wcrt -
            task_results[writer].bcrt)
        if _period(reader) % _period(writer) == 0:
            if _wplus(writer, task_results) > _rmin(reader, task_results):
                candidates.add(_rplus(reader, task_results) - _wmin(writer,
                    task_results, -1))
            for n in range(int(math.ceil(_period(reader) / _period(writer)))):
                if _wplus(writer, task_results, n) <= _rplus(reader,
                    task_results):
                    candidates.add(_rplus(reader, task_results) - _wmin(
                        writer, task_results, n))
        result = min([c for c in candidates if c >= 0])
    details[writer.name + '-' + reader.name + '-delay'] = result
    return result


def _calculate_forward_distance(writer, reader, task_results, details):
    """ computes forward distance (for reaction time)
    """
    if _period(reader) < _period(writer):
        candidates = set()
        candidates.add(_period(reader))
        if _period(writer) % _period(reader) == 0:
            for n in range(int(math.ceil(_period(writer) / _period(reader)))):
                if _rmin(reader, task_results, n) >= _wplus(writer,
                    task_results, 0):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(
                        writer, task_results, 0))
                if _wplus(writer, task_results) > _rmin(reader, task_results, n
                    ):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(
                        writer, task_results, -1))
        result = min([c for c in candidates if c >= 0])
    else:
        candidates = set()
        if _period(reader) % _period(writer) != 0:
            candidates.add(_period(reader))
        else:
            for n in range(int(math.ceil(_period(reader) / _period(writer)))):
                candidates.add(_rplus(reader, task_results) - _wmin(writer,
                    task_results, n))
                if _wplus(writer, task_results, n) > _rmin(reader, task_results
                    ):
                    candidates.add(_rplus(reader, task_results, 1) - _wmin(
                        writer, task_results, n))
        result = max(candidates)
    details[writer.name + '-' + reader.name + '-delay'] = result
    return result


def _wplus(writer, task_results, n=0):
    return n * _period(writer) + _phi(writer) + task_results[writer
        ].wcrt + _jitter(writer)


def _wmin(writer, task_results, n=0):
    return n * _period(writer) + _phi(writer) + task_results[writer
        ].bcrt - _jitter(writer)


def _rplus(reader, task_results, n=0):
    return _wplus(reader, task_results, n) - task_results[reader].bcrt


def _rmin(reader, task_results, n=0):
    return n * _period(reader) + _phi(reader) - _jitter(reader)

<mask token>
from __future__ import absolute_import
from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division
from . import options
from . import model
from . import util
import math


def end_to_end_latency(path, task_results, n=1, task_overhead=0,
    path_overhead=0, **kwargs):
    """ Computes the worst-/best-case e2e latency for n tokens to pass the path.
    The constant path.overhead is added to the best- and worst-case latencies.

    :param path: the path
    :type path: model.Path
    :param n:  amount of events
    :type n: integer
    :param task_overhead: A constant task_overhead is added once per task to both min and max latency
    :type task_overhead: integer
    :param path_overhead:  A constant path_overhead is added once per path to both min and max latency
    :type path_overhead: integer
    :rtype: tuple (best-case latency, worst-case latency)
    """
    if options.get_opt('e2e_improved') == True:
        lmin, lmax = end_to_end_latency_improved(path, task_results, n, **
            kwargs)
    else:
        lmin, lmax = end_to_end_latency_classic(path, task_results, n, **kwargs
            )
    for t in path.tasks:
        if t in task_results:
            lmin += task_overhead
            lmax += task_overhead
    lmin += path_overhead + path.overhead
    lmax += path_overhead + path.overhead
    return lmin, lmax


def end_to_end_latency_classic(path, task_results, n=1, injection_rate=
    'max', **kwargs):
    """ Computes the worst-/best-case end-to-end latency
    Assumes that all tasks in the system have successfully been analyzed.
    Assumes that events enter the path at maximum/minumum rate.
    The end-to-end latency is the sum of the individual task's
    worst-case response times.

    This corresponds to Definition 7.3 in [Richter2005]_.

    :param path: the path
    :type path: model.Path
    :param n:  amount of events
    :type n: integer
    :param injection_rate: assumed injection rate is maximum or minimum
    :type injection_rate: string 'max' or 'min'
    :rtype: tuple (best case latency, worst case latency)
    """
    lmax = 0
    lmin = 0
    tasks = path
    if isinstance(path, model.Path):
        tasks = path.tasks
    for t in tasks:
        if t in task_results:
            lmax += task_results[t].wcrt
            lmin += task_results[t].bcrt
        elif isinstance(t, model.Junction):
            prev_task = tasks[tasks.index(t) - 1]
            if prev_task in t.analysis_results:
                lmin += t.analysis_results[prev_task].bcrt
                lmax += t.analysis_results[prev_task].wcrt
        else:
            print('Warning: no task_results for task %s' % t.name)
    if injection_rate == 'max':
        lmax += tasks[0].in_event_model.delta_min(n)
    elif injection_rate == 'min':
        lmax += tasks[0].in_event_model.delta_plus(n)
    lmin += tasks[0].in_event_model.delta_min(n)
    return lmin, lmax


def _event_arrival_path(path, n, e_0=0):
    """ Returns the latest arrival time of the n-th event
    with respect to an event 0 of task 0 (first task in path)

    This is :math:`e_0(n)` from Lemma 1 in [Schliecker2009recursive]_.
    """
    if n > 0:
        e = e_0 + path.tasks[0].in_event_model.delta_plus(n + 1)
    elif n < 0:
        e = e_0 - path.tasks[0].in_event_model.delta_min(-n + 1)
    else:
        e = 0
    return e


def _event_exit_path(path, task_results, i, n, e_0=0):
    """ Returns the latest exit time of the n-th event
    relative to the arrival of an event 0
    (cf. Lemma 2 in [Schliecker2009recursive]_)
    In contrast to Lemma 2, k_max is set so that all busy times
    are taken into account.
    """
    if i == -1:
        e = _event_arrival_path(path, n, e_0)
    elif path.tasks[i] not in task_results:
        return _event_exit_path(path, task_results, i - 1, n, e_0)
    else:
        e = float('-inf')
        k_max = len(task_results[path.tasks[i]].busy_times)
        for k in range(1, k_max):
            e_k = _event_exit_path(path, task_results, i - 1, n - k + 1, e_0
                ) + task_results[path.tasks[i]].busy_times[k]
            if e_k > e:
                e = e_k
    return e


def end_to_end_latency_improved(path, task_results, n=1, e_0=0, **kwargs):
    """ Performs the path analysis presented in [Schliecker2009recursive]_,
    which improves results compared to end_to_end_latency() for
    n>1 and bursty event models.
    lat(n)
    """
    lmax = 0
    lmin = 0
    lmax = _event_exit_path(path, task_results, len(path.tasks) - 1, n - 1, e_0
        ) - e_0
    for t in path.tasks:
        if isinstance(t, model.Task) and t in task_results:
            lmin += task_results[t].bcrt
        elif isinstance(t, model.Junction):
            print('Error: path contains junctions')
        else:
            print('Warning: no task_results for task %s' % t.name)
    lmin += path.tasks[0].in_event_model.delta_min(n)
    return lmin, lmax


def cause_effect_chain_data_age(chain, task_results, details=None):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    return cause_effect_chain(chain, task_results, details, 'data-age')


def cause_effect_chain_reaction_time(chain, task_results, details=None):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    return cause_effect_chain(chain, task_results, details, 'reaction-time')


def cause_effect_chain(chain, task_results, details=None, semantics='data-age'
    ):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    sequence = chain.task_sequence(writers_only=True)
    if details is None:
        details = dict()
    periods = [_period(t) for t in sequence]
    if util.GCD(periods) != min(periods):
        print('Error: cause-effect chain analysis requires harmonic periods')
    l_max = _phi(sequence[0]) + _jitter(sequence[0])
    details[sequence[0].name + '-PHI+J'] = l_max
    for i in range(len(sequence)):
        if i < len(sequence) - 1:
            if semantics == 'data-age':
                delay = _calculate_backward_distance(sequence[i], sequence[
                    i + 1], task_results, details=details)
            elif semantics == 'reaction-time':
                delay = _calculate_forward_distance(sequence[i], sequence[i +
                    1], task_results, details=details)
            else:
                raise NotImplementedException()
            l_max += delay
        delay = task_results[sequence[i]].wcrt
        details[sequence[i].name + '-WCRT'] = delay
        l_max += delay
    return l_max


def _phi(task):
    if hasattr(task.in_event_model, 'phi'):
        return task.in_event_model.phi
    else:
        return 0


def _period(task):
    return task.in_event_model.P


def _jitter(task):
    if hasattr(task.in_event_model, 'J'):
        return task.in_event_model.J
    else:
        return 0


def _calculate_backward_distance(writer, reader, task_results, details):
    """ computes backward distance (for data age)
    """
    if _period(reader) < _period(writer):
        candidates = set()
        if _period(writer) % _period(reader) != 0:
            candidates.add(_period(writer) + task_results[writer].wcrt -
                task_results[writer].bcrt)
        else:
            for n in range(int(math.ceil(_period(writer) / _period(reader)))):
                candidates.add(_rplus(reader, task_results, n) - _wmin(
                    writer, task_results, 0))
                if _wplus(writer, task_results) > _rmin(reader, task_results, n
                    ):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(
                        writer, task_results, -1))
        result = max(candidates)
    else:
        candidates = set()
        candidates.add(_period(writer) + task_results[writer].wcrt -
            task_results[writer].bcrt)
        if _period(reader) % _period(writer) == 0:
            if _wplus(writer, task_results) > _rmin(reader, task_results):
                candidates.add(_rplus(reader, task_results) - _wmin(writer,
                    task_results, -1))
            for n in range(int(math.ceil(_period(reader) / _period(writer)))):
                if _wplus(writer, task_results, n) <= _rplus(reader,
                    task_results):
                    candidates.add(_rplus(reader, task_results) - _wmin(
                        writer, task_results, n))
        result = min([c for c in candidates if c >= 0])
    details[writer.name + '-' + reader.name + '-delay'] = result
    return result


def _calculate_forward_distance(writer, reader, task_results, details):
    """ computes forward distance (for reaction time)
    """
    if _period(reader) < _period(writer):
        candidates = set()
        candidates.add(_period(reader))
        if _period(writer) % _period(reader) == 0:
            for n in range(int(math.ceil(_period(writer) / _period(reader)))):
                if _rmin(reader, task_results, n) >= _wplus(writer,
                    task_results, 0):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(
                        writer, task_results, 0))
                if _wplus(writer, task_results) > _rmin(reader, task_results, n
                    ):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(
                        writer, task_results, -1))
        result = min([c for c in candidates if c >= 0])
    else:
        candidates = set()
        if _period(reader) % _period(writer) != 0:
            candidates.add(_period(reader))
        else:
            for n in range(int(math.ceil(_period(reader) / _period(writer)))):
                candidates.add(_rplus(reader, task_results) - _wmin(writer,
                    task_results, n))
                if _wplus(writer, task_results, n) > _rmin(reader, task_results
                    ):
                    candidates.add(_rplus(reader, task_results, 1) - _wmin(
                        writer, task_results, n))
        result = max(candidates)
    details[writer.name + '-' + reader.name + '-delay'] = result
    return result


def _wplus(writer, task_results, n=0):
    return n * _period(writer) + _phi(writer) + task_results[writer
        ].wcrt + _jitter(writer)


def _wmin(writer, task_results, n=0):
    return n * _period(writer) + _phi(writer) + task_results[writer
        ].bcrt - _jitter(writer)


def _rplus(reader, task_results, n=0):
    return _wplus(reader, task_results, n) - task_results[reader].bcrt


def _rmin(reader, task_results, n=0):
    return n * _period(reader) + _phi(reader) - _jitter(reader)

""" Compositional Performance Analysis Algorithms for Path Latencies

| Copyright (C) 2007-2017 Jonas Diemer, Philip Axer, Johannes Schlatow
| TU Braunschweig, Germany
| All rights reserved.
| See LICENSE file for copyright and license details.

:Authors:
         - Jonas Diemer
         - Philip Axer
         - Johannes Schlatow

Description
-----------

This module contains methods for the ananlysis of path latencies.
It should be imported in scripts that do the analysis.
"""

from __future__ import absolute_import
from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division

from . import options
from . import model
from . import util

import math


def end_to_end_latency(path, task_results, n=1 , task_overhead=0,
                       path_overhead=0, **kwargs):
    """ Computes the worst-/best-case e2e latency for n tokens to pass the path.
    The constant path.overhead is added to the best- and worst-case latencies.

    :param path: the path
    :type path: model.Path
    :param n:  amount of events
    :type n: integer
    :param task_overhead: A constant task_overhead is added once per task to both min and max latency
    :type task_overhead: integer
    :param path_overhead:  A constant path_overhead is added once per path to both min and max latency
    :type path_overhead: integer
    :rtype: tuple (best-case latency, worst-case latency)
    """

    if options.get_opt('e2e_improved') == True:
        (lmin, lmax) = end_to_end_latency_improved(path, task_results,
                                                   n, **kwargs)
    else:
        (lmin, lmax) = end_to_end_latency_classic(path, task_results,
                                                  n, **kwargs)

    for t in path.tasks:
        # implcitly check if t is a junction
        if t in task_results:
            # add per-task overheads
            lmin += task_overhead
            lmax += task_overhead

    # add per-path overhead
    lmin += path_overhead + path.overhead
    lmax += path_overhead + path.overhead

    return (lmin, lmax)

def end_to_end_latency_classic(path, task_results, n=1, injection_rate='max', **kwargs):
    """ Computes the worst-/best-case end-to-end latency
    Assumes that all tasks in the system have successfully been analyzed.
    Assumes that events enter the path at maximum/minumum rate.
    The end-to-end latency is the sum of the individual task's
    worst-case response times.

    This corresponds to Definition 7.3 in [Richter2005]_.

    :param path: the path
    :type path: model.Path
    :param n:  amount of events
    :type n: integer
    :param injection_rate: assumed injection rate is maximum or minimum
    :type injection_rate: string 'max' or 'min'
    :rtype: tuple (best case latency, worst case latency)
    """

    lmax = 0
    lmin = 0

    # check if path is a list of Tasks or a Path object
    tasks = path
    if isinstance(path, model.Path):
        tasks = path.tasks

    for t in tasks:
        # implcitly check if t is a junction
        if t in task_results:
            # sum up best- and worst-case response times
            lmax += task_results[t].wcrt
            lmin += task_results[t].bcrt
        elif isinstance(t, model.Junction):
            # add sampling delay induced by the junction (if available)
            prev_task = tasks[tasks.index(t)-1]
            if prev_task in t.analysis_results:
                lmin += t.analysis_results[prev_task].bcrt
                lmax += t.analysis_results[prev_task].wcrt
        else:
            print("Warning: no task_results for task %s" % t.name)

    if injection_rate == 'max':
        # add the eastliest possible release of event n
        lmax += tasks[0].in_event_model.delta_min(n)

    elif injection_rate == 'min':
        # add the latest possible release of event n
        lmax += tasks[0].in_event_model.delta_plus(n)

    # add the earliest possible release of event n
    lmin += tasks[0].in_event_model.delta_min(n)

    return lmin, lmax


def _event_arrival_path(path, n, e_0=0):
    """ Returns the latest arrival time of the n-th event
    with respect to an event 0 of task 0 (first task in path)

    This is :math:`e_0(n)` from Lemma 1 in [Schliecker2009recursive]_.
    """
    # if e_0 is None:
        # the entry time of the first event

    if n > 0:
        e = e_0 + path.tasks[0].in_event_model.delta_plus(n + 1)
    elif n < 0:
        e = e_0 - path.tasks[0].in_event_model.delta_min(-n + 1)
    else:
        e = 0  # same event, so the difference is 0

    return e


def _event_exit_path(path, task_results, i, n, e_0=0):
    """ Returns the latest exit time of the n-th event
    relative to the arrival of an event 0
    (cf. Lemma 2 in [Schliecker2009recursive]_)
    In contrast to Lemma 2, k_max is set so that all busy times
    are taken into account.
    """

    # logger.debug("calculating exit for task %d, n=%d" % (i, n))

    if i == -1:
        # The exit of task -1 is the arrival of task 0.
        e = _event_arrival_path(path, n, e_0)
    elif path.tasks[i] not in task_results:
        # skip task if there are no results for this
        # (this may happen if, e.g., a chain analysis has been performed)
        return _event_exit_path(path, task_results, i-1, n, e_0)
    else:
        e = float('-inf')
        k_max = len(task_results[path.tasks[i]].busy_times)
        # print("k_max:",k_max)
        for k in range(1, k_max):
            e_k = _event_exit_path(path, task_results, i - 1, n - k + 1, e_0) + \
                    task_results[path.tasks[i]].busy_times[k]

            # print("e_k:",e_k)
            if e_k > e:
                # print("task %d, n=%d k=%d, new e=%d" % (i, n, k, e_k))
                e = e_k

    # print("exit for task %d, n=%d is %d" % (i, n, e))
    return e


def end_to_end_latency_improved(path, task_results, n=1, e_0=0, **kwargs):
    """ Performs the path analysis presented in [Schliecker2009recursive]_,
    which improves results compared to end_to_end_latency() for
    n>1 and bursty event models.
    lat(n)
    """
    lmax = 0
    lmin = 0
    lmax = _event_exit_path(path, task_results, len(path.tasks) - 1, n - 1, e_0) - e_0

    for t in path.tasks:
        if isinstance(t, model.Task) and t in task_results:
            # sum up best-case response times
            lmin += task_results[t].bcrt
        elif isinstance(t, model.Junction):
            print("Error: path contains junctions")
        else:
            print("Warning: no task_results for task %s" % t.name)

    # add the earliest possible release of event n
    # TODO: Can lmin be improved?
    lmin += path.tasks[0].in_event_model.delta_min(n)

    return lmin, lmax

def cause_effect_chain_data_age(chain, task_results, details=None):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    return cause_effect_chain(chain, task_results, details, 'data-age')

def cause_effect_chain_reaction_time(chain, task_results, details=None):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """
    return cause_effect_chain(chain, task_results, details, 'reaction-time')

def cause_effect_chain(chain, task_results, details=None, semantics='data-age'):
    """ computes the data age of the given cause effect chain
    :param chain: model.EffectChain
    :param task_results: dict of analysis.TaskResult
    """

    sequence = chain.task_sequence(writers_only=True)

    if details is None:
        details = dict()

    periods = [_period(t) for t in sequence]
    if util.GCD(periods) != min(periods):
        print("Error: cause-effect chain analysis requires harmonic periods")

    l_max = _phi(sequence[0]) + _jitter(sequence[0])
    details[sequence[0].name+'-PHI+J'] = l_max
    for i in range(len(sequence)):
        # add write-to-read delay for all but the last task
        if i < len(sequence)-1:
            if semantics == 'data-age':
                # add write to read delay
                delay = _calculate_backward_distance(sequence[i], sequence[i+1], task_results, 
                        details=details)
            elif semantics == 'reaction-time':
                delay = _calculate_forward_distance(sequence[i], sequence[i+1], task_results, 
                        details=details)
            else:
                raise NotImplementedException()

            l_max += delay

        # add read-to-write delay (response time) for all tasks
        delay = task_results[sequence[i]].wcrt
        details[sequence[i].name+'-WCRT'] = delay
        l_max += delay

    return l_max

def _phi(task):
    if hasattr(task.in_event_model, 'phi'):
        return task.in_event_model.phi
    else:
        return 0

def _period(task):
    return task.in_event_model.P

def _jitter(task):
    if hasattr(task.in_event_model, 'J'):
        return task.in_event_model.J
    else:
        return 0

def _calculate_backward_distance(writer, reader, task_results, details):
    """ computes backward distance (for data age)
    """

    if _period(reader) < _period(writer): # oversampling 

        candidates = set()

        if _period(writer) % _period(reader) != 0:
            candidates.add(_period(writer) + task_results[writer].wcrt - task_results[writer].bcrt)
        else:

            for n in range(int(math.ceil(_period(writer)/_period(reader)))):
                candidates.add(_rplus(reader, task_results, n) - _wmin(writer, task_results, 0))

                # include previous cycle?
                if _wplus(writer, task_results) > _rmin(reader, task_results, n):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(writer, task_results, -1))

        result = max(candidates)

    else: # undersampling or same period

        candidates = set()
        candidates.add(_period(writer) + task_results[writer].wcrt - task_results[writer].bcrt)

        if _period(reader) % _period(writer) == 0:

            # include previous cycle?
            if _wplus(writer, task_results) > _rmin(reader, task_results):
                candidates.add(_rplus(reader, task_results) - _wmin(writer, task_results, -1))

            # include all other possible writers
            for n in range(int(math.ceil(_period(reader)/_period(writer)))):
                if _wplus(writer, task_results, n) <= _rplus(reader, task_results):
                    candidates.add(_rplus(reader, task_results) - _wmin(writer, task_results, n))

        result = min([c for c in candidates if c >= 0])

    details[writer.name+'-'+reader.name+'-delay'] = result
    return result

def _calculate_forward_distance(writer, reader, task_results, details):
    """ computes forward distance (for reaction time)
    """

    if _period(reader) < _period(writer): # oversampling 

        candidates = set()
        candidates.add(_period(reader))

        if _period(writer) % _period(reader) == 0:

            for n in range(int(math.ceil(_period(writer)/_period(reader)))):
                if _rmin(reader, task_results, n) >= _wplus(writer, task_results, 0):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(writer, task_results, 0))

                # include previous cycle?
                if _wplus(writer, task_results) > _rmin(reader, task_results, n):
                    candidates.add(_rplus(reader, task_results, n) - _wmin(writer, task_results, -1))

        result = min([c for c in candidates if c >= 0])

    else: # undersampling or same period

        candidates = set()

        if _period(reader) % _period(writer) != 0:
            candidates.add(_period(reader))
        else:

            # include all possible writers
            for n in range(int(math.ceil(_period(reader)/_period(writer)))):
                candidates.add(_rplus(reader, task_results) - _wmin(writer, task_results, n))

                # if write time can be earlier than read time, add distance to next reader
                if _wplus(writer, task_results, n) > _rmin(reader, task_results):
                    candidates.add(_rplus(reader, task_results, 1) - _wmin(writer, task_results, n))

        result = max(candidates)

    details[writer.name+'-'+reader.name+'-delay'] = result
    return result

def _wplus(writer, task_results, n=0):
    return n*_period(writer) + _phi(writer) + task_results[writer].wcrt + _jitter(writer)

def _wmin(writer, task_results, n=0):
    return n*_period(writer) + _phi(writer) + task_results[writer].bcrt - _jitter(writer)

def _rplus(reader, task_results, n=0):
    return _wplus(reader, task_results, n) - task_results[reader].bcrt

def _rmin(reader, task_results, n=0):
    return n*_period(reader) + _phi(reader) - _jitter(reader)

# vim: tabstop=4 expandtab shiftwidth=4 softtabstop=4
