/*
 * Copyright 2019 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

// TODO(b/129481165): remove the #pragma below and fix conversion issues
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wextra"

#define ATRACE_TAG ATRACE_TAG_GRAPHICS

#include <algorithm>
#include <chrono>
#include <numeric>
#include <sstream>

#include <android-base/logging.h>
#include <android-base/stringprintf.h>
#include <common/FlagManager.h>
#include <common/trace.h>
#include <cutils/compiler.h>
#include <cutils/properties.h>
#include <ftl/concat.h>
#include <utils/Log.h>

#include "RefreshRateSelector.h"
#include "VSyncPredictor.h"

namespace android::scheduler {

using base::StringAppendF;

static auto constexpr kMaxPercent = 100u;

namespace {
int numVsyncsPerFrame(const ftl::NonNull<DisplayModePtr>& displayModePtr) {
    const auto idealPeakRefreshPeriod = displayModePtr->getPeakFps().getPeriodNsecs();
    const auto idealRefreshPeriod = displayModePtr->getVsyncRate().getPeriodNsecs();
    return static_cast<int>(std::round(static_cast<float>(idealPeakRefreshPeriod) /
                                       static_cast<float>(idealRefreshPeriod)));
}
} // namespace

VSyncPredictor::~VSyncPredictor() = default;

VSyncPredictor::VSyncPredictor(std::unique_ptr<Clock> clock, ftl::NonNull<DisplayModePtr> modePtr,
                               size_t historySize, size_t minimumSamplesForPrediction,
                               uint32_t outlierTolerancePercent)
      : mClock(std::move(clock)),
        mId(modePtr->getPhysicalDisplayId()),
        mTraceOn(property_get_bool("debug.sf.vsp_trace", false)),
        kHistorySize(historySize),
        kMinimumSamplesForPrediction(minimumSamplesForPrediction),
        kOutlierTolerancePercent(std::min(outlierTolerancePercent, kMaxPercent)),
        mDisplayModePtr(modePtr),
        mNumVsyncsForFrame(numVsyncsPerFrame(mDisplayModePtr)) {
    resetModel();
}

inline void VSyncPredictor::traceInt64If(const char* name, int64_t value) const {
    if (CC_UNLIKELY(mTraceOn)) {
        traceInt64(name, value);
    }
}

inline void VSyncPredictor::traceInt64(const char* name, int64_t value) const {
    SFTRACE_INT64(ftl::Concat(ftl::truncated<14>(name), " ", mId.value).c_str(), value);
}

inline size_t VSyncPredictor::next(size_t i) const {
    return (i + 1) % mTimestamps.size();
}

nsecs_t VSyncPredictor::idealPeriod() const {
    return mDisplayModePtr->getVsyncRate().getPeriodNsecs();
}

bool VSyncPredictor::validate(nsecs_t timestamp) const {
    SFTRACE_CALL();
    if (mLastTimestampIndex < 0 || mTimestamps.empty() ||
        getSampleSizeAndOldestVsync(timestamp).first == 0) {
        SFTRACE_INSTANT("timestamp valid (first)");
        return true;
    }

    const auto aValidTimestamp = mTimestamps[mLastTimestampIndex];
    const auto percent =
            (timestamp - aValidTimestamp) % idealPeriod() * kMaxPercent / idealPeriod();
    if (percent >= kOutlierTolerancePercent &&
        percent <= (kMaxPercent - kOutlierTolerancePercent)) {
        SFTRACE_FORMAT_INSTANT("timestamp not aligned with model. aValidTimestamp %.2fms ago"
                               ", timestamp %.2fms ago, idealPeriod=%.2 percent=%d",
                               (mClock->now() - aValidTimestamp) / 1e6f,
                               (mClock->now() - timestamp) / 1e6f,
                               idealPeriod() / 1e6f, percent);
        return false;
    }

    const auto isThresholdEnabled =
            FlagManager::getInstance().vsync_predictor_predicts_within_threshold() &&
            (mDisplayModePtr->getVrrConfig() || FlagManager::getInstance().resync_on_tx());
    const auto iter =
            std::min_element(mTimestamps.begin(), mTimestamps.end(), [=](nsecs_t a, nsecs_t b) {
                nsecs_t diffA = std::abs(timestamp - a);
                nsecs_t diffB = std::abs(timestamp - b);
                if (isThresholdEnabled) {
                    bool withinThresholdA = diffA <= kPredictorThreshold.ns();
                    bool withinThresholdB = diffB <= kPredictorThreshold.ns();
                    if (withinThresholdA != withinThresholdB) {
                        return withinThresholdA;
                    }
                }
                return diffA < diffB;
            });
    const auto distancePercent = std::abs(*iter - timestamp) * kMaxPercent / idealPeriod();
    if (distancePercent < kOutlierTolerancePercent) {
        // duplicate timestamp
        SFTRACE_FORMAT_INSTANT("duplicate timestamp");
        return false;
    }
    return true;
}

nsecs_t VSyncPredictor::currentPeriod() const {
    std::lock_guard lock(mMutex);
    return mRateMap.find(idealPeriod())->second.slope;
}

Period VSyncPredictor::minFramePeriod() const {
    std::lock_guard lock(mMutex);
    return minFramePeriodLocked();
}

Period VSyncPredictor::minFramePeriodLocked() const {
    const auto slope = mRateMap.find(idealPeriod())->second.slope;
    return Period::fromNs(slope * mNumVsyncsForFrame);
}

bool VSyncPredictor::addVsyncTimestamp(nsecs_t timestamp) {
    SFTRACE_CALL();

    std::lock_guard lock(mMutex);

    if (!validate(timestamp)) {
        // VSR could elect to ignore the incongruent timestamp or resetModel(). If ts is ignored,
        // don't insert this ts into mTimestamps ringbuffer. If we are still
        // in the learning phase we should just clear all timestamps and start
        // over.
        if (mTimestamps.size() < kMinimumSamplesForPrediction) {
            // Add the timestamp to mTimestamps before clearing it so we could
            // update mKnownTimestamp based on the new timestamp.
            mTimestamps.push_back(timestamp);

            // Do not clear timelines as we don't want to break the phase while
            // we are still learning.
            clearTimestamps(/* clearTimelines */ false);
        } else if (!mTimestamps.empty()) {
            mKnownTimestamp =
                    std::max(timestamp, *std::max_element(mTimestamps.begin(), mTimestamps.end()));
        } else {
            mKnownTimestamp = timestamp;
        }
        SFTRACE_FORMAT_INSTANT("timestamp rejected. mKnownTimestamp was %.2fms ago",
                               (mClock->now() - *mKnownTimestamp) / 1e6f);
        return false;
    }

    if (mTimestamps.size() != kHistorySize) {
        mTimestamps.push_back(timestamp);
        mLastTimestampIndex = next(mLastTimestampIndex);
    } else {
        mLastTimestampIndex = next(mLastTimestampIndex);
        mTimestamps[mLastTimestampIndex] = timestamp;
    }

    traceInt64If("VSP-ts", timestamp);

    const auto [numSamples, oldestTs] = getSampleSizeAndOldestVsync(timestamp);
    traceInt64("VSP-numSamples", static_cast<int64_t>(numSamples));
    mOldestVsync = oldestTs;
    const auto minNumSamples = getMinSamplesRequiredForPrediction();
    if (numSamples < minNumSamples) {
        mRateMap[idealPeriod()] = {idealPeriod(), 0};
        return true;
    }

    // This is a 'simple linear regression' calculation of Y over X, with Y being the
    // vsync timestamps, and X being the ordinal of vsync count.
    // The calculated slope is the vsync period.
    // Formula for reference:
    // Sigma_i: means sum over all timestamps.
    // mean(variable): statistical mean of variable.
    // X: snapped ordinal of the timestamp
    // Y: vsync timestamp
    //
    //         Sigma_i( (X_i - mean(X)) * (Y_i - mean(Y) )
    // slope = -------------------------------------------
    //         Sigma_i ( X_i - mean(X) ) ^ 2
    //
    // intercept = mean(Y) - slope * mean(X)
    //
    std::vector<nsecs_t> vsyncTS(numSamples);
    std::vector<nsecs_t> ordinals(numSamples);

    // Normalizing to the oldest timestamp cuts down on error in calculating the intercept.
    auto it = mRateMap.find(idealPeriod());
    // Calculated slope over the period of time can become outdated as the new timestamps are
    // stored. Using idealPeriod instead provides a rate which is valid at all the times.
    const bool useIdealPeriod =
            FlagManager::getInstance().vsync_predictor_predicts_within_threshold() &&
            (mDisplayModePtr->getVrrConfig() || FlagManager::getInstance().resync_on_tx());
    auto const currentPeriod = useIdealPeriod ? idealPeriod() : it->second.slope;

    // The mean of the ordinals must be precise for the intercept calculation, so scale them up for
    // fixed-point arithmetic.
    constexpr int64_t kScalingFactor = 1000;

    nsecs_t meanTS = 0;
    nsecs_t meanOrdinal = 0;
    size_t vsyncIndex = 0;
    for (size_t i = 0; i < mTimestamps.size(); i++) {
        // Timestamp outside the threshold are not used for the calculation as the older
        // timestamps accumulate drifts and causes the anticipatedPeriod and intercept to
        // reflect that drift which no longer aligns with the current system state.
        if (!isVsyncWithinThreshold(timestamp, mTimestamps[i])) continue;
        const auto ts = mTimestamps[i] - oldestTs;
        vsyncTS[vsyncIndex] = ts;
        meanTS += ts;

        const auto ordinal = currentPeriod == 0
                ? 0
                : (vsyncTS[vsyncIndex] + currentPeriod / 2) / currentPeriod * kScalingFactor;
        ordinals[vsyncIndex] = ordinal;
        meanOrdinal += ordinal;
        ++vsyncIndex;
    }
    LOG_FATAL_IF(vsyncIndex != numSamples,
                 "samples size does not match with the number of vsyncs in window for prediction");

    meanTS /= numSamples;
    meanOrdinal /= numSamples;

    for (size_t i = 0; i < numSamples; i++) {
        vsyncTS[i] -= meanTS;
        ordinals[i] -= meanOrdinal;
    }

    nsecs_t top = 0;
    nsecs_t bottom = 0;
    for (size_t i = 0; i < numSamples; i++) {
        top += vsyncTS[i] * ordinals[i];
        bottom += ordinals[i] * ordinals[i];
    }

    if (CC_UNLIKELY(bottom == 0)) {
        it->second = {idealPeriod(), 0};
        clearTimestamps(/* clearTimelines */ true);
        return false;
    }

    nsecs_t const anticipatedPeriod = top * kScalingFactor / bottom;
    nsecs_t const intercept = meanTS - (anticipatedPeriod * meanOrdinal / kScalingFactor);

    auto const percent = std::abs(anticipatedPeriod - idealPeriod()) * kMaxPercent / idealPeriod();
    if (percent >= kOutlierTolerancePercent) {
        it->second = {idealPeriod(), 0};
        clearTimestamps(/* clearTimelines */ true);
        return false;
    }

    traceInt64("VSP-period", anticipatedPeriod);
    traceInt64("VSP-intercept", intercept);

    it->second = {anticipatedPeriod, intercept};

    ALOGV("model update ts %" PRIu64 ": %" PRId64 " slope: %" PRId64 " intercept: %" PRId64,
          mId.value, timestamp, anticipatedPeriod, intercept);
    return true;
}

nsecs_t VSyncPredictor::snapToVsync(nsecs_t timePoint) const {
    auto const [slope, intercept] = getVSyncPredictionModelLocked();

    if (mTimestamps.empty()) {
        traceInt64("VSP-mode", 1);
        auto const knownTimestamp = mKnownTimestamp ? *mKnownTimestamp : timePoint;
        auto const numPeriodsOut = ((timePoint - knownTimestamp) / idealPeriod()) + 1;
        return knownTimestamp + numPeriodsOut * idealPeriod();
    }

    // See b/145667109, the ordinal calculation must take into account the intercept.
    const auto oldest =
            (mDisplayModePtr->getVrrConfig() || FlagManager::getInstance().resync_on_tx()) &&
                    FlagManager::getInstance().vsync_predictor_predicts_within_threshold()
            ? mOldestVsync
            : *std::min_element(mTimestamps.begin(), mTimestamps.end());
    auto const zeroPoint = oldest + intercept;
    auto const ordinalRequest = (timePoint - zeroPoint + slope) / slope;
    auto const prediction = (ordinalRequest * slope) + intercept + oldest;

    traceInt64("VSP-mode", 0);
    traceInt64If("VSP-timePoint", timePoint);
    traceInt64If("VSP-prediction", prediction);

    auto const printer = [&, slope = slope, intercept = intercept] {
        std::stringstream str;
        str << "prediction made from: " << timePoint << "prediction: " << prediction << " (+"
            << prediction - timePoint << ") slope: " << slope << " intercept: " << intercept
            << "oldestTS: " << oldest << " ordinal: " << ordinalRequest;
        return str.str();
    };

    ALOGV("%s", printer().c_str());
    LOG_ALWAYS_FATAL_IF(prediction < timePoint, "VSyncPredictor: model miscalculation: %s",
                        printer().c_str());

    return prediction;
}

bool VSyncPredictor::isVsyncWithinThreshold(nsecs_t currentTimestamp,
                                            nsecs_t previousTimestamp) const {
    if (FlagManager::getInstance().vsync_predictor_predicts_within_threshold() &&
        (mDisplayModePtr->getVrrConfig() || FlagManager::getInstance().resync_on_tx())) {
        return currentTimestamp - previousTimestamp <= kPredictorThreshold.ns();
    }
    return true;
}

std::pair<size_t, nsecs_t> VSyncPredictor::getSampleSizeAndOldestVsync(
        nsecs_t currentTimestamp) const {
    if (FlagManager::getInstance().vsync_predictor_predicts_within_threshold() &&
        (mDisplayModePtr->getVrrConfig() || FlagManager::getInstance().resync_on_tx())) {
        size_t numSamples = 0;
        nsecs_t oldestTimestamp = currentTimestamp;
        for (auto vsync : mTimestamps) {
            if (isVsyncWithinThreshold(currentTimestamp, vsync)) {
                ++numSamples;
                if (vsync < oldestTimestamp) {
                    oldestTimestamp = vsync;
                }
            }
        }
        return {numSamples, oldestTimestamp};
    }
    return {mTimestamps.size(), *std::min_element(mTimestamps.begin(), mTimestamps.end())};
}

size_t VSyncPredictor::getMinSamplesRequiredForPrediction() const {
    if (FlagManager::getInstance().vsync_predictor_predicts_within_threshold() &&
        (mDisplayModePtr->getVrrConfig() || FlagManager::getInstance().resync_on_tx()) &&
        mRenderRateOpt) {
        const size_t minimumSamplesForPrediction =
                std::max(static_cast<size_t>(kAbsoluteMinSamplesForPrediction),
                         static_cast<size_t>(kPredictorThreshold.ns() /
                                             mRenderRateOpt->getPeriodNsecs()));
        return std::min(kMinimumSamplesForPrediction, minimumSamplesForPrediction);
    }
    return kMinimumSamplesForPrediction;
}

nsecs_t VSyncPredictor::nextAnticipatedVSyncTimeFrom(nsecs_t timePoint,
                                                     std::optional<nsecs_t> lastVsyncOpt) {
    SFTRACE_CALL();
    std::lock_guard lock(mMutex);

    const auto now = TimePoint::fromNs(mClock->now());
    purgeTimelines(now);

    if (lastVsyncOpt && *lastVsyncOpt > timePoint) {
        timePoint = *lastVsyncOpt;
    }

    const auto model = getVSyncPredictionModelLocked();
    const auto threshold = model.slope / 2;
    std::optional<Period> minFramePeriodOpt;

    if (mNumVsyncsForFrame > 1) {
        minFramePeriodOpt = minFramePeriodLocked();
    }

    std::optional<TimePoint> vsyncOpt;
    for (auto& timeline : mTimelines) {
        vsyncOpt = timeline.nextAnticipatedVSyncTimeFrom(model, minFramePeriodOpt,
                                                         snapToVsync(timePoint), mMissedVsync,
                                                         lastVsyncOpt ? snapToVsync(*lastVsyncOpt -
                                                                                    threshold)
                                                                      : lastVsyncOpt);
        if (vsyncOpt) {
            break;
        }
    }
    LOG_ALWAYS_FATAL_IF(!vsyncOpt);

    if (*vsyncOpt > mLastCommittedVsync) {
        mLastCommittedVsync = *vsyncOpt;
        SFTRACE_FORMAT_INSTANT("mLastCommittedVsync in %.2fms",
                               float(mLastCommittedVsync.ns() - mClock->now()) / 1e6f);
    }

    return vsyncOpt->ns();
}

/*
 * Returns whether a given vsync timestamp is in phase with a frame rate.
 * If the frame rate is not a divisor of the refresh rate, it is always considered in phase.
 * For example, if the vsync timestamps are (16.6,33.3,50.0,66.6):
 * isVSyncInPhase(16.6, 30) = true
 * isVSyncInPhase(33.3, 30) = false
 * isVSyncInPhase(50.0, 30) = true
 */
bool VSyncPredictor::isVSyncInPhase(nsecs_t timePoint, Fps frameRate) {
    if (timePoint == 0) {
        return true;
    }

    std::lock_guard lock(mMutex);
    const auto model = getVSyncPredictionModelLocked();
    const nsecs_t period = model.slope;
    const nsecs_t justBeforeTimePoint = timePoint - period / 2;
    const auto now = TimePoint::fromNs(mClock->now());
    const auto vsync = snapToVsync(justBeforeTimePoint);

    purgeTimelines(now);

    for (auto& timeline : mTimelines) {
        if (timeline.isWithin(TimePoint::fromNs(vsync)) == VsyncTimeline::VsyncOnTimeline::Unique) {
            return timeline.isVSyncInPhase(model, vsync, frameRate);
        }
    }

    // The last timeline should always be valid
    return mTimelines.back().isVSyncInPhase(model, vsync, frameRate);
}

void VSyncPredictor::setRenderRate(Fps renderRate, bool applyImmediately,
                                   std::vector<FrameRateOverride> frameRateOverrides) {
    SFTRACE_FORMAT("%s %s", __func__, to_string(renderRate).c_str());
    ALOGV("%s %s: RenderRate %s ", __func__, to_string(mId).c_str(), to_string(renderRate).c_str());
    std::lock_guard lock(mMutex);
    const auto prevRenderRate = mRenderRateOpt;
    mRenderRateOpt = renderRate;
    const auto renderPeriodDelta =
            prevRenderRate ? prevRenderRate->getPeriodNsecs() - renderRate.getPeriodNsecs() : 0;
    if (applyImmediately) {
        SFTRACE_FORMAT_INSTANT("applyImmediately");
        while (mTimelines.size() > 1) {
            mTimelines.pop_front();
        }

        mTimelines.front().setRenderRate(renderRate);
        return;
    }

    const bool newRenderRateIsHigher = renderPeriodDelta > renderRate.getPeriodNsecs() &&
            mLastCommittedVsync.ns() - mClock->now() > 2 * renderRate.getPeriodNsecs();
    if (newRenderRateIsHigher) {
        SFTRACE_FORMAT_INSTANT("newRenderRateIsHigher");
        mTimelines.clear();
        mLastCommittedVsync = TimePoint::fromNs(0);
        mTimelines.emplace_back(mLastCommittedVsync, mIdealPeriod, renderRate);
    } else {
        mTimelines.back().freeze(getVSyncPredictionModelLocked(), mLastCommittedVsync,
                                 frameRateOverrides);
        mTimelines.emplace_back(*(mTimelines.back().validUntil()), mIdealPeriod, renderRate);
    }
    purgeTimelines(TimePoint::fromNs(mClock->now()));
}

void VSyncPredictor::setDisplayModePtr(ftl::NonNull<DisplayModePtr> modePtr) {
    LOG_ALWAYS_FATAL_IF(mId != modePtr->getPhysicalDisplayId(),
                        "mode does not belong to the display");
    SFTRACE_FORMAT("%s %s", __func__, to_string(*modePtr).c_str());
    const auto timeout = modePtr->getVrrConfig()
            ? modePtr->getVrrConfig()->notifyExpectedPresentConfig
            : std::nullopt;
    ALOGV("%s %s: DisplayMode %s notifyExpectedPresentTimeout %s", __func__, to_string(mId).c_str(),
          to_string(*modePtr).c_str(),
          timeout ? std::to_string(timeout->timeoutNs).c_str() : "N/A");
    std::lock_guard lock(mMutex);

    // do not clear the timelines on VRR displays if we didn't change the mode
    const bool isVrr = modePtr->getVrrConfig().has_value();
    const bool clearTimelines = !isVrr || mDisplayModePtr->getId() != modePtr->getId();
    mDisplayModePtr = modePtr;
    mNumVsyncsForFrame = numVsyncsPerFrame(mDisplayModePtr);
    traceInt64("VSP-setPeriod", modePtr->getVsyncRate().getPeriodNsecs());

    static constexpr size_t kSizeLimit = 30;
    if (CC_UNLIKELY(mRateMap.size() == kSizeLimit)) {
        mRateMap.erase(mRateMap.begin());
    }

    if (mRateMap.find(idealPeriod()) == mRateMap.end()) {
        mRateMap[idealPeriod()] = {idealPeriod(), 0};
    }

    if (clearTimelines) {
      mTimelines.clear();
    }
    clearTimestamps(clearTimelines);
}

Duration VSyncPredictor::ensureMinFrameDurationIsKept(TimePoint expectedPresentTime,
                                                      TimePoint lastConfirmedPresentTime) {
    SFTRACE_FORMAT("%s mNumVsyncsForFrame=%d mPastExpectedPresentTimes.size()=%zu", __func__,
                   mNumVsyncsForFrame, mPastExpectedPresentTimes.size());

    if (mNumVsyncsForFrame <= 1) {
        return 0ns;
    }

    const auto currentPeriod = mRateMap.find(idealPeriod())->second.slope;
    const auto threshold = currentPeriod / 2;
    const auto minFramePeriod = minFramePeriodLocked();

    auto prev = lastConfirmedPresentTime.ns();
    for (auto& current : mPastExpectedPresentTimes) {
        SFTRACE_FORMAT_INSTANT("current %.2f past last signaled fence",
                               static_cast<float>(current.ns() - prev) / 1e6f);

        const auto minPeriodViolation = current.ns() - prev + threshold < minFramePeriod.ns();
        if (minPeriodViolation) {
            SFTRACE_NAME("minPeriodViolation");
            current = TimePoint::fromNs(prev + minFramePeriod.ns());
            prev = current.ns();
        } else {
            break;
        }
    }

    if (!mPastExpectedPresentTimes.empty()) {
        const auto phase = Duration(mPastExpectedPresentTimes.back() - expectedPresentTime);
        if (phase > 0ns) {
            for (auto& timeline : mTimelines) {
                timeline.shiftVsyncSequence(phase, minFramePeriod);
            }
            mPastExpectedPresentTimes.clear();
            return phase;
        }
    }

    return 0ns;
}

void VSyncPredictor::onFrameBegin(TimePoint expectedPresentTime, FrameTime lastSignaledFrameTime) {
    SFTRACE_NAME("VSyncPredictor::onFrameBegin");
    std::lock_guard lock(mMutex);

    if (!mDisplayModePtr->getVrrConfig()) return;

    const auto [lastConfirmedPresentTime, lastConfirmedExpectedPresentTime] = lastSignaledFrameTime;
    if (CC_UNLIKELY(mTraceOn)) {
        SFTRACE_FORMAT_INSTANT("vsync is %.2f past last signaled fence",
                               static_cast<float>(expectedPresentTime.ns() -
                                                  lastConfirmedPresentTime.ns()) /
                                       1e6f);
    }
    const auto currentPeriod = mRateMap.find(idealPeriod())->second.slope;
    const auto threshold = currentPeriod / 2;
    mPastExpectedPresentTimes.push_back(expectedPresentTime);

    while (!mPastExpectedPresentTimes.empty()) {
        const auto front = mPastExpectedPresentTimes.front().ns();
        const bool frontIsBeforeConfirmed = front < lastConfirmedPresentTime.ns() + threshold;
        if (frontIsBeforeConfirmed) {
            SFTRACE_FORMAT_INSTANT("Discarding old vsync - %.2f before last signaled fence",
                                   static_cast<float>(lastConfirmedPresentTime.ns() - front) /
                                           1e6f);
            mPastExpectedPresentTimes.pop_front();
        } else {
            break;
        }
    }

    if (lastConfirmedExpectedPresentTime.ns() - lastConfirmedPresentTime.ns() > threshold) {
        SFTRACE_FORMAT_INSTANT("lastFramePresentedEarly");
        return;
    }

    const auto phase = ensureMinFrameDurationIsKept(expectedPresentTime, lastConfirmedPresentTime);
    if (phase > 0ns) {
        mMissedVsync = {expectedPresentTime, minFramePeriodLocked()};
    }
}

void VSyncPredictor::onFrameMissed(TimePoint expectedPresentTime) {
    SFTRACE_NAME("VSyncPredictor::onFrameMissed");

    std::lock_guard lock(mMutex);
    if (!mDisplayModePtr->getVrrConfig()) return;

    // We don't know when the frame is going to be presented, so we assume it missed one vsync
    const auto currentPeriod = mRateMap.find(idealPeriod())->second.slope;
    const auto lastConfirmedPresentTime =
            TimePoint::fromNs(expectedPresentTime.ns() + currentPeriod);

    const auto phase = ensureMinFrameDurationIsKept(expectedPresentTime, lastConfirmedPresentTime);
    if (phase > 0ns) {
        mMissedVsync = {expectedPresentTime, Duration::fromNs(0)};
    }
}

VSyncPredictor::Model VSyncPredictor::getVSyncPredictionModel() const {
    std::lock_guard lock(mMutex);
    return VSyncPredictor::getVSyncPredictionModelLocked();
}

VSyncPredictor::Model VSyncPredictor::getVSyncPredictionModelLocked() const {
    return mRateMap.find(idealPeriod())->second;
}

void VSyncPredictor::clearTimestamps(bool clearTimelines) {
    SFTRACE_FORMAT("%s: clearTimelines=%d", __func__, clearTimelines);

    if (!mTimestamps.empty()) {
        auto const maxRb = *std::max_element(mTimestamps.begin(), mTimestamps.end());
        if (mKnownTimestamp) {
            mKnownTimestamp = std::max(*mKnownTimestamp, maxRb);
            SFTRACE_FORMAT_INSTANT("mKnownTimestamp was %.2fms ago",
                               (mClock->now() - *mKnownTimestamp) / 1e6f);
        } else {
            mKnownTimestamp = maxRb;
            SFTRACE_FORMAT_INSTANT("mKnownTimestamp (maxRb) was %.2fms ago",
                               (mClock->now() - *mKnownTimestamp) / 1e6f);
        }

        mTimestamps.clear();
        mLastTimestampIndex = 0;
    }

    mIdealPeriod = Period::fromNs(idealPeriod());
    if (mTimelines.empty()) {
        mLastCommittedVsync = TimePoint::fromNs(0);
        mTimelines.emplace_back(mLastCommittedVsync, mIdealPeriod, mRenderRateOpt);
    } else if (clearTimelines) {
        while (mTimelines.size() > 1) {
            mTimelines.pop_front();
        }
        mTimelines.front().setRenderRate(mRenderRateOpt);
        // set mLastCommittedVsync to a valid vsync but don't commit too much in the future
        const auto vsyncOpt = mTimelines.front().nextAnticipatedVSyncTimeFrom(
            getVSyncPredictionModelLocked(),
            /* minFramePeriodOpt */ std::nullopt,
            snapToVsync(mClock->now()), MissedVsync{},
            /* lastVsyncOpt */ std::nullopt);
        mLastCommittedVsync = *vsyncOpt;
    }
}

bool VSyncPredictor::needsMoreSamples() const {
    std::lock_guard lock(mMutex);
    return mTimestamps.size() < getMinSamplesRequiredForPrediction();
}

void VSyncPredictor::resetModel() {
    SFTRACE_CALL();
    std::lock_guard lock(mMutex);
    mRateMap[idealPeriod()] = {idealPeriod(), 0};
    clearTimestamps(/* clearTimelines */ true);
}

void VSyncPredictor::dump(std::string& result) const {
    std::lock_guard lock(mMutex);
    StringAppendF(&result, "\tmDisplayModePtr=%s\n", to_string(*mDisplayModePtr).c_str());
    StringAppendF(&result, "\tRefresh Rate Map:\n");
    for (const auto& [period, periodInterceptTuple] : mRateMap) {
        StringAppendF(&result,
                      "\t\tFor ideal period %.2fms: period = %.2fms, intercept = %" PRId64 "\n",
                      period / 1e6f, periodInterceptTuple.slope / 1e6f,
                      periodInterceptTuple.intercept);
    }
    StringAppendF(&result, "\tmTimelines.size()=%zu\n", mTimelines.size());
}

void VSyncPredictor::purgeTimelines(android::TimePoint now) {
    const auto kEnoughFramesToBreakPhase = 5;
    if (mRenderRateOpt &&
        mLastCommittedVsync.ns() + mRenderRateOpt->getPeriodNsecs() * kEnoughFramesToBreakPhase <
                mClock->now()) {
        SFTRACE_FORMAT_INSTANT("kEnoughFramesToBreakPhase");
        mTimelines.clear();
        mLastCommittedVsync = TimePoint::fromNs(0);
        mTimelines.emplace_back(mLastCommittedVsync, mIdealPeriod, mRenderRateOpt);
        return;
    }

    while (mTimelines.size() > 1) {
        if (mTimelines.front().isWithin(now) == VsyncTimeline::VsyncOnTimeline::Outside) {
            mTimelines.pop_front();
        } else {
            break;
        }
    }
    LOG_ALWAYS_FATAL_IF(mTimelines.empty());
    LOG_ALWAYS_FATAL_IF(mTimelines.back().validUntil().has_value());
}

auto VSyncPredictor::VsyncTimeline::makeVsyncSequence(TimePoint knownVsync)
        -> std::optional<VsyncSequence> {
    if (knownVsync.ns() == 0) return std::nullopt;
    return std::make_optional<VsyncSequence>({knownVsync.ns(), 0});
}

VSyncPredictor::VsyncTimeline::VsyncTimeline(TimePoint knownVsync, Period idealPeriod,
                                             std::optional<Fps> renderRateOpt)
      : mIdealPeriod(idealPeriod),
        mRenderRateOpt(renderRateOpt),
        mLastVsyncSequence(makeVsyncSequence(knownVsync)) {}

void VSyncPredictor::VsyncTimeline::freeze(Model model, TimePoint lastVsync,
                                           std::vector<FrameRateOverride> frameRateOverrides) {
    LOG_ALWAYS_FATAL_IF(mValidUntil.has_value());
    if (!frameRateOverrides.empty() && mLastVsyncSequence) {
        const int64_t renderRatePhase =
                getFreezeSequencePhase(model, lastVsync, std::move(frameRateOverrides));
        lastVsync = TimePoint::fromNs(lastVsync.ns() + model.slope * renderRatePhase);
    }

    SFTRACE_FORMAT_INSTANT("renderRate %s valid for %.2f",
                           mRenderRateOpt ? to_string(*mRenderRateOpt).c_str() : "NA",
                           float(lastVsync.ns() - TimePoint::now().ns()) / 1e6f);
    mValidUntil = lastVsync;
}

int64_t VSyncPredictor::VsyncTimeline::getFreezeSequencePhase(
        Model model, TimePoint lastVsync, std::vector<FrameRateOverride> frameRateOverrides) {
    static constexpr uint32_t kCapacity = 10;
    ftl::SmallMap<Fps, ftl::Unit, kCapacity, FpsApproxEqual> overridesSet;
    for (auto [_, frameRateHz] : frameRateOverrides) {
        overridesSet.emplace_or_replace(Fps::fromValue(frameRateHz));
    }

    const auto idealPeriodFps = Fps::fromPeriodNsecs(mIdealPeriod.ns());

    int64_t divisor = 1;
    for (auto [fps, _] : overridesSet) {
        auto frameRateDivisor = RefreshRateSelector::getFrameRateDivisor(idealPeriodFps, fps);
        if (frameRateDivisor <= 0) continue;
        divisor = std::lcm(divisor, frameRateDivisor);
    }

    const auto lastVsyncSequence = getVsyncSequenceLocked(model, lastVsync.ns());
    auto seq = static_cast<int64_t>(std::ceil(static_cast<double>(lastVsyncSequence.seq) /
                                              static_cast<double>(divisor))) *
            divisor;
    return seq - lastVsyncSequence.seq;
}

std::optional<TimePoint> VSyncPredictor::VsyncTimeline::nextAnticipatedVSyncTimeFrom(
        Model model, std::optional<Period> minFramePeriodOpt, nsecs_t vsync,
        MissedVsync missedVsync, std::optional<nsecs_t> lastVsyncOpt) {
    SFTRACE_FORMAT("renderRate %s", mRenderRateOpt ? to_string(*mRenderRateOpt).c_str() : "NA");

    nsecs_t vsyncTime = snapToVsyncAlignedWithRenderRate(model, vsync);
    const auto threshold = model.slope / 2;
    const auto lastFrameMissed =
            lastVsyncOpt && std::abs(*lastVsyncOpt - missedVsync.vsync.ns()) < threshold;
    const auto mightBackpressure = minFramePeriodOpt && mRenderRateOpt &&
            mRenderRateOpt->getPeriod() < 2 * (*minFramePeriodOpt);
    if (lastFrameMissed) {
        // If the last frame missed is the last vsync, we already shifted the timeline. Depends
        // on whether we skipped the frame (onFrameMissed) or not (onFrameBegin) we apply a
        // different fixup if we are violating the minFramePeriod.
        // There is no need to shift the vsync timeline again.
        if (vsyncTime - missedVsync.vsync.ns() < minFramePeriodOpt->ns()) {
            vsyncTime += missedVsync.fixup.ns();
            SFTRACE_FORMAT_INSTANT("lastFrameMissed");
        }
    } else if (mightBackpressure && lastVsyncOpt) {
        const auto vsyncDiff = vsyncTime - *lastVsyncOpt;
        if (vsyncDiff <= minFramePeriodOpt->ns() - threshold) {
            // avoid a duplicate vsync
            SFTRACE_FORMAT_INSTANT("skipping a vsync to avoid duplicate frame. next in %.2f "
                                   "which "
                                   "is %.2f "
                                   "from "
                                   "prev. "
                                   "adjust by %.2f",
                                   static_cast<float>(vsyncTime - TimePoint::now().ns()) / 1e6f,
                                   static_cast<float>(vsyncDiff) / 1e6f,
                                   static_cast<float>(mRenderRateOpt->getPeriodNsecs()) / 1e6f);
            vsyncTime += mRenderRateOpt->getPeriodNsecs();
        }
    }

    SFTRACE_FORMAT_INSTANT("vsync in %.2fms", float(vsyncTime - TimePoint::now().ns()) / 1e6f);
    if (isWithin(TimePoint::fromNs(vsyncTime)) == VsyncOnTimeline::Outside) {
        SFTRACE_FORMAT_INSTANT("no longer valid for vsync in %.2f",
                               static_cast<float>(vsyncTime - TimePoint::now().ns()) / 1e6f);
        return std::nullopt;
    }

    return TimePoint::fromNs(vsyncTime);
}

auto VSyncPredictor::VsyncTimeline::getVsyncSequenceLocked(Model model, nsecs_t vsync)
        -> VsyncSequence {
    if (!mLastVsyncSequence) return {vsync, 0};

    const auto [lastVsyncTime, lastVsyncSequence] = *mLastVsyncSequence;
    const auto vsyncSequence = lastVsyncSequence +
            static_cast<int64_t>(std::round((vsync - lastVsyncTime) /
                                            static_cast<float>(model.slope)));
    return {vsync, vsyncSequence};
}

nsecs_t VSyncPredictor::VsyncTimeline::snapToVsyncAlignedWithRenderRate(Model model,
                                                                        nsecs_t vsync) {
    // update the mLastVsyncSequence for reference point
    mLastVsyncSequence = getVsyncSequenceLocked(model, vsync);

    const auto renderRatePhase = [&]() -> int {
        if (!mRenderRateOpt) return 0;
        const auto divisor =
                RefreshRateSelector::getFrameRateDivisor(Fps::fromPeriodNsecs(mIdealPeriod.ns()),
                                                         *mRenderRateOpt);
        if (divisor <= 1) return 0;

        int mod = mLastVsyncSequence->seq % divisor;
        if (mod == 0) return 0;
        else if (mod < 0)
            mod += divisor;

        return divisor - mod;
    }();

    if (renderRatePhase == 0) {
        return mLastVsyncSequence->vsyncTime;
    }

    return mLastVsyncSequence->vsyncTime + model.slope * renderRatePhase;
}

bool VSyncPredictor::VsyncTimeline::isVSyncInPhase(Model model, nsecs_t vsync, Fps frameRate) {
    const auto getVsyncIn = [](TimePoint now, nsecs_t timePoint) -> float {
        return ticks<std::milli, float>(TimePoint::fromNs(timePoint) - now);
    };

    Fps displayFps = Fps::fromPeriodNsecs(mIdealPeriod.ns());
    const auto divisor = RefreshRateSelector::getFrameRateDivisor(displayFps, frameRate);
    const auto now = TimePoint::now();

    if (divisor <= 1) {
        return true;
    }
    const auto vsyncSequence = getVsyncSequenceLocked(model, vsync);
    SFTRACE_FORMAT_INSTANT("vsync in: %.2f sequence: %" PRId64 " divisor: %zu",
                           getVsyncIn(now, vsyncSequence.vsyncTime), vsyncSequence.seq, divisor);
    return vsyncSequence.seq % divisor == 0;
}

void VSyncPredictor::VsyncTimeline::shiftVsyncSequence(Duration phase, Period minFramePeriod) {
    if (mLastVsyncSequence) {
        const auto renderRate = mRenderRateOpt.value_or(Fps::fromPeriodNsecs(mIdealPeriod.ns()));
        const auto threshold = mIdealPeriod.ns() / 2;
        if (renderRate.getPeriodNsecs() - phase.ns() + threshold >= minFramePeriod.ns()) {
            SFTRACE_FORMAT_INSTANT("Not-Adjusting vsync by %.2f",
                                   static_cast<float>(phase.ns()) / 1e6f);
            return;
        }
        SFTRACE_FORMAT_INSTANT("adjusting vsync by %.2f", static_cast<float>(phase.ns()) / 1e6f);
        mLastVsyncSequence->vsyncTime += phase.ns();
    }
}

VSyncPredictor::VsyncTimeline::VsyncOnTimeline VSyncPredictor::VsyncTimeline::isWithin(
        TimePoint vsync) {
    const auto threshold = mIdealPeriod.ns() / 2;
    if (!mValidUntil || vsync.ns() < mValidUntil->ns() - threshold) {
        // if mValidUntil is absent then timeline is not frozen and
        // vsync should be unique to that timeline.
        return VsyncOnTimeline::Unique;
    }
    if (vsync.ns() > mValidUntil->ns() + threshold) {
        return VsyncOnTimeline::Outside;
    }
    return VsyncOnTimeline::Shared;
}

} // namespace android::scheduler

// TODO(b/129481165): remove the #pragma below and fix conversion issues
#pragma clang diagnostic pop // ignored "-Wextra"