// Copyright (C) 2021 The Qt Company Ltd.
// Copyright (C) 2016 Intel Corporation.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only

#include <qelapsedtimer.h>
#include <qcoreapplication.h>

#include "private/qcore_unix_p.h"
#include "private/qtimerinfo_unix_p.h"
#include "private/qobject_p.h"
#include "private/qabstracteventdispatcher_p.h"

#include <sys/times.h>

using namespace std::chrono;
// Implied by "using namespace std::chrono", but be explicit about it, for grep-ability
using namespace std::chrono_literals;

QT_BEGIN_NAMESPACE

Q_CORE_EXPORT bool qt_disable_lowpriority_timers=false;

/*
 * Internal functions for manipulating timer data structures.  The
 * timerBitVec array is used for keeping track of timer identifiers.
 */

QTimerInfoList::QTimerInfoList() = default;

steady_clock::time_point QTimerInfoList::updateCurrentTime() const
{
    currentTime = steady_clock::now();
    return currentTime;
}

/*! \internal
    Updates the currentTime member to the current time, and returns \c true if
    the first timer's timeout is in the future (after currentTime).

    The list is sorted by timeout, thus it's enough to check the first timer only.
*/
bool QTimerInfoList::hasPendingTimers()
{
    if (timers.isEmpty())
        return false;
    return updateCurrentTime() < timers.at(0)->timeout;
}

static bool byTimeout(const QTimerInfo *a, const QTimerInfo *b)
{ return a->timeout < b->timeout; };

/*
  insert timer info into list
*/
void QTimerInfoList::timerInsert(QTimerInfo *ti)
{
    timers.insert(std::upper_bound(timers.cbegin(), timers.cend(), ti, byTimeout),
                  ti);
}

static constexpr milliseconds roundToMillisecond(nanoseconds val)
{
    // always round up
    // worst case scenario is that the first trigger of a 1-ms timer is 0.999 ms late
    return ceil<milliseconds>(val);
}

static_assert(roundToMillisecond(0ns) == 0ms);
static_assert(roundToMillisecond(1ns) == 1ms);
static_assert(roundToMillisecond(999'999ns) == 1ms);
static_assert(roundToMillisecond(1'000'000ns) == 1ms);
static_assert(roundToMillisecond(999'000'000ns) == 999ms);
static_assert(roundToMillisecond(999'000'001ns) == 1000ms);
static_assert(roundToMillisecond(999'999'999ns) == 1000ms);
static_assert(roundToMillisecond(1s) == 1s);

static constexpr seconds roundToSecs(nanoseconds interval)
{
    // The very coarse timer is based on full second precision, so we want to
    // round the interval to the closest second, rounding 500ms up to 1s.
    //
    // std::chrono::round() wouldn't work with all multiples of 500 because for the
    // middle point it would round to even:
    // value  round()  wanted
    // 500      0        1
    // 1500     2        2
    // 2500     2        3

    auto secs = duration_cast<seconds>(interval);
    const nanoseconds frac = interval - secs;
    if (frac >= 500ms)
        ++secs;
    return secs;
}

static void calculateCoarseTimerTimeout(QTimerInfo *t, steady_clock::time_point now)
{
    // The coarse timer works like this:
    //  - interval under 40 ms: round to even
    //  - between 40 and 99 ms: round to multiple of 4
    //  - otherwise: try to wake up at a multiple of 25 ms, with a maximum error of 5%
    //
    // We try to wake up at the following second-fraction, in order of preference:
    //    0 ms
    //  500 ms
    //  250 ms or 750 ms
    //  200, 400, 600, 800 ms
    //  other multiples of 100
    //  other multiples of 50
    //  other multiples of 25
    //
    // The objective is to make most timers wake up at the same time, thereby reducing CPU wakeups.

    Q_ASSERT(t->interval >= 20ms);

    const auto timeoutInSecs = time_point_cast<seconds>(t->timeout);

    auto recalculate = [&](const milliseconds frac) {
        t->timeout = timeoutInSecs + frac;
        if (t->timeout < now)
            t->timeout += t->interval;
    };

    // Calculate how much we can round and still keep within 5% error
    milliseconds interval = roundToMillisecond(t->interval);
    const milliseconds absMaxRounding = interval / 20;

    auto fracMsec = duration_cast<milliseconds>(t->timeout - timeoutInSecs);

    if (interval < 100ms && interval != 25ms && interval != 50ms && interval != 75ms) {
        auto fracCount = fracMsec.count();
        // special mode for timers of less than 100 ms
        if (interval < 50ms) {
            // round to even
            // round towards multiples of 50 ms
            bool roundUp = (fracCount % 50) >= 25;
            fracCount >>= 1;
            fracCount |= roundUp;
            fracCount <<= 1;
        } else {
            // round to multiple of 4
            // round towards multiples of 100 ms
            bool roundUp = (fracCount % 100) >= 50;
            fracCount >>= 2;
            fracCount |= roundUp;
            fracCount <<= 2;
        }
        fracMsec = milliseconds{fracCount};
        recalculate(fracMsec);
        return;
    }

    milliseconds min = std::max(0ms, fracMsec - absMaxRounding);
    milliseconds max = std::min(1000ms, fracMsec + absMaxRounding);

    // find the boundary that we want, according to the rules above
    // extra rules:
    // 1) whatever the interval, we'll take any round-to-the-second timeout
    if (min == 0ms) {
        fracMsec = 0ms;
        recalculate(fracMsec);
        return;
    } else if (max == 1000ms) {
        fracMsec = 1000ms;
        recalculate(fracMsec);
        return;
    }

    milliseconds wantedBoundaryMultiple{25};

    // 2) if the interval is a multiple of 500 ms and > 5000 ms, we'll always round
    //    towards a round-to-the-second
    // 3) if the interval is a multiple of 500 ms, we'll round towards the nearest
    //    multiple of 500 ms
    if ((interval % 500) == 0ms) {
        if (interval >= 5s) {
            fracMsec = fracMsec >= 500ms ? max : min;
            recalculate(fracMsec);
            return;
        } else {
            wantedBoundaryMultiple = 500ms;
        }
    } else if ((interval % 50) == 0ms) {
        // 4) same for multiples of 250, 200, 100, 50
        milliseconds mult50 = interval / 50;
        if ((mult50 % 4) == 0ms) {
            // multiple of 200
            wantedBoundaryMultiple = 200ms;
        } else if ((mult50 % 2) == 0ms) {
            // multiple of 100
            wantedBoundaryMultiple = 100ms;
        } else if ((mult50 % 5) == 0ms) {
            // multiple of 250
            wantedBoundaryMultiple = 250ms;
        } else {
            // multiple of 50
            wantedBoundaryMultiple = 50ms;
        }
    }

    milliseconds base = (fracMsec / wantedBoundaryMultiple) * wantedBoundaryMultiple;
    milliseconds middlepoint = base + wantedBoundaryMultiple / 2;
    if (fracMsec < middlepoint)
        fracMsec = qMax(base, min);
    else
        fracMsec = qMin(base + wantedBoundaryMultiple, max);

    recalculate(fracMsec);
}

static void calculateNextTimeout(QTimerInfo *t, steady_clock::time_point now)
{
    switch (t->timerType) {
    case Qt::PreciseTimer:
    case Qt::CoarseTimer:
        t->timeout += t->interval;
        if (t->timeout < now) {
            t->timeout = now;
            t->timeout += t->interval;
        }
        if (t->timerType == Qt::CoarseTimer)
            calculateCoarseTimerTimeout(t, now);
        return;

    case Qt::VeryCoarseTimer:
        // t->interval already rounded to full seconds in registerTimer()
        t->timeout += t->interval;
        if (t->timeout <= now)
            t->timeout = time_point_cast<seconds>(now + t->interval);
        break;
    }
}

/*
    Returns the time to wait for the first timer that has not been activated yet,
    otherwise returns std::nullopt.
 */
std::optional<QTimerInfoList::Duration> QTimerInfoList::timerWait()
{
    steady_clock::time_point now = updateCurrentTime();

    auto isWaiting = [](QTimerInfo *tinfo) { return !tinfo->activateRef; };
    // Find first waiting timer not already active
    auto it = std::find_if(timers.cbegin(), timers.cend(), isWaiting);
    if (it == timers.cend())
        return std::nullopt;

    Duration timeToWait = (*it)->timeout - now;
    if (timeToWait > 0ns)
        return roundToMillisecond(timeToWait);
    return 0ms;
}

/*
  Returns the timer's remaining time in milliseconds with the given timerId.
  If the timer id is not found in the list, the returned value will be \c{Duration::min()}.
  If the timer is overdue, the returned value will be 0.
*/
QTimerInfoList::Duration QTimerInfoList::remainingDuration(Qt::TimerId timerId) const
{
    const steady_clock::time_point now = updateCurrentTime();

    auto it = findTimerById(timerId);
    if (it == timers.cend()) {
#ifndef QT_NO_DEBUG
        qWarning("QTimerInfoList::timerRemainingTime: timer id %i not found", int(timerId));
#endif
        return Duration::min();
    }

    const QTimerInfo *t = *it;
    if (now < t->timeout) // time to wait
        return t->timeout - now;
    return 0ms;
}

void QTimerInfoList::registerTimer(Qt::TimerId timerId, QTimerInfoList::Duration interval,
                                   Qt::TimerType timerType, QObject *object)
{
    // correct the timer type first
    if (timerType == Qt::CoarseTimer) {
        // this timer has up to 5% coarseness
        // so our boundaries are 20 ms and 20 s
        // below 20 ms, 5% inaccuracy is below 1 ms, so we convert to high precision
        // above 20 s, 5% inaccuracy is above 1 s, so we convert to VeryCoarseTimer
        if (interval >= 20s)
            timerType = Qt::VeryCoarseTimer;
        else if (interval <= 20ms)
            timerType = Qt::PreciseTimer;
    }

    QTimerInfo *t = new QTimerInfo(timerId, interval, timerType, object);
    QTimerInfo::TimePoint expected = updateCurrentTime() + interval;

    switch (timerType) {
    case Qt::PreciseTimer:
        // high precision timer is based on millisecond precision
        // so no adjustment is necessary
        t->timeout = expected;
        break;

    case Qt::CoarseTimer:
        t->timeout = expected;
        t->interval = roundToMillisecond(interval);
        calculateCoarseTimerTimeout(t, currentTime);
        break;

    case Qt::VeryCoarseTimer:
        t->interval = roundToSecs(t->interval);
        const auto currentTimeInSecs = floor<seconds>(currentTime);
        t->timeout = currentTimeInSecs + t->interval;
        // If we're past the half-second mark, increase the timeout again
        if (currentTime - currentTimeInSecs > 500ms)
            t->timeout += 1s;
    }

    timerInsert(t);
}

bool QTimerInfoList::unregisterTimer(Qt::TimerId timerId)
{
    auto it = findTimerById(timerId);
    if (it == timers.cend())
        return false; // id not found

    // set timer inactive
    QTimerInfo *t = *it;
    if (t == firstTimerInfo)
        firstTimerInfo = nullptr;
    if (t->activateRef)
        *(t->activateRef) = nullptr;
    delete t;
    timers.erase(it);
    return true;
}

bool QTimerInfoList::unregisterTimers(QObject *object)
{
    if (timers.isEmpty())
        return false;

    auto associatedWith = [this](QObject *o) {
        return [this, o](auto &t) {
            if (t->obj == o) {
                if (t == firstTimerInfo)
                    firstTimerInfo = nullptr;
                if (t->activateRef)
                    *(t->activateRef) = nullptr;
                delete t;
                return true;
            }
            return false;
        };
    };

    qsizetype count = timers.removeIf(associatedWith(object));
    return count > 0;
}

auto QTimerInfoList::registeredTimers(QObject *object) const -> QList<TimerInfo>
{
    QList<TimerInfo> list;
    for (const auto &t : timers) {
        if (t->obj == object)
            list.emplaceBack(TimerInfo{t->interval, t->id, t->timerType});
    }
    return list;
}

/*
    Activate pending timers, returning how many where activated.
*/
int QTimerInfoList::activateTimers()
{
    if (qt_disable_lowpriority_timers || timers.isEmpty())
        return 0; // nothing to do

    firstTimerInfo = nullptr;

    const steady_clock::time_point now = updateCurrentTime();
    // qDebug() << "Thread" << QThread::currentThreadId() << "woken up at" << now;
    // Find out how many timer have expired
    auto stillActive = [&now](const QTimerInfo *t) { return now < t->timeout; };
    // Find first one still active (list is sorted by timeout)
    auto it = std::find_if(timers.cbegin(), timers.cend(), stillActive);
    auto maxCount = it - timers.cbegin();

    int n_act = 0;
    //fire the timers.
    while (maxCount--) {
        if (timers.isEmpty())
            break;

        QTimerInfo *currentTimerInfo = timers.constFirst();
        if (now < currentTimerInfo->timeout)
            break; // no timer has expired

        if (!firstTimerInfo) {
            firstTimerInfo = currentTimerInfo;
        } else if (firstTimerInfo == currentTimerInfo) {
            // avoid sending the same timer multiple times
            break;
        } else if (currentTimerInfo->interval <  firstTimerInfo->interval
                   || currentTimerInfo->interval == firstTimerInfo->interval) {
            firstTimerInfo = currentTimerInfo;
        }

        // determine next timeout time
        calculateNextTimeout(currentTimerInfo, now);
        if (timers.size() > 1) {
            // Find where "currentTimerInfo" should be in the list so as
            // to keep the list ordered by timeout
            auto afterCurrentIt = timers.begin() + 1;
            auto iter = std::upper_bound(afterCurrentIt, timers.end(), currentTimerInfo, byTimeout);
            currentTimerInfo = *std::rotate(timers.begin(), afterCurrentIt, iter);
        }

        if (currentTimerInfo->interval > 0ms)
            n_act++;

        // Send event, but don't allow it to recurse:
        if (!currentTimerInfo->activateRef) {
            currentTimerInfo->activateRef = &currentTimerInfo;

            QTimerEvent e(qToUnderlying(currentTimerInfo->id));
            QCoreApplication::sendEvent(currentTimerInfo->obj, &e);

            // Storing currentTimerInfo's address in its activateRef allows the
            // handling of that event to clear this local variable on deletion
            // of the object it points to - if it didn't, clear activateRef:
            if (currentTimerInfo)
                currentTimerInfo->activateRef = nullptr;
        }
    }

    firstTimerInfo = nullptr;
    // qDebug() << "Thread" << QThread::currentThreadId() << "activated" << n_act << "timers";
    return n_act;
}

QT_END_NAMESPACE