/*
 * Copyright 2026 Google LLC
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "tests/graphite/sparse_strips/OracleValidator.h"

#include "include/core/SkPath.h"
#include "include/core/SkPoint.h"
#include "include/core/SkRect.h"
#include "include/core/SkString.h"
#include "include/private/SkTDArray.h"
#include "src/core/SkVx.h"
#include "src/gpu/graphite/sparse_strips/Flatten.h"
#include "src/gpu/graphite/sparse_strips/MSAA_LUT.h"
#include "src/gpu/graphite/sparse_strips/Polyline.h"
#include "src/gpu/graphite/sparse_strips/Tiler.h"
#include "tests/Test.h"
#include "tests/graphite/sparse_strips/CoverageTestUtils.h"
#include "tests/graphite/sparse_strips/Oracle.h"

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <vector>

namespace skgpu::graphite {

template <uint16_t kTileWidth, uint16_t kTileHeight>
OracleValidator<kTileWidth, kTileHeight>::OracleValidator(
        const SkPath& path, const WideTiles& wides, const EndCaps& ends,
        const SkTDArray<skvx::int8>& exactWindings, const Polyline* polyline,
        const Tiles<kTileWidth, kTileHeight>* tiler, const char* testName, Strictness strictness)
        : fPath(path)
        , fWides(wides)
        , fEnds(ends)
        , fExactWindings(exactWindings)
        , fPolyline(polyline)
        , fTiler(tiler)
        , fTestName(testName)
        , fStrictness(strictness)
        , fToleranceSq(static_cast<float>(Flatten::kQuadTolerance2))
        , fOracle(path) {
    this->buildTileLineMap();
}

template <uint16_t kTileWidth, uint16_t kTileHeight>
skvx::int8 OracleValidator<kTileWidth, kTileHeight>::GetOracleWinding(
        int px, const std::vector<ScanlineOracle8x::RowWindingInterval>& intervals) {
    return ScanlineOracle8x::GetOracleWinding(px, intervals);
}

template <uint16_t kTileWidth, uint16_t kTileHeight>
bool OracleValidator<kTileWidth, kTileHeight>::validate(skiatest::Reporter* reporter,
                                                        uint16_t viewportWidth,
                                                        uint16_t viewportHeight,
                                                        uint32_t* maxSampleDiffOut) const {
    if (!this->validateStreamInvariants(reporter, viewportWidth, viewportHeight)) {
        return false;
    }

    bool allPass = true;
    const auto& caps = fEnds.caps();
    const auto& wides = fWides.tiles();

    int capIdx = 0;
    int wideIdx = 0;

    // Walk row by row through all tile rows present in caps or wides
    while (capIdx < caps.size() || wideIdx < wides.size()) {
        uint16_t rowY = UINT16_MAX;
        if (capIdx < caps.size()) {
            rowY = std::min(rowY, caps[capIdx].fY);
        }
        if (wideIdx < wides.size()) {
            rowY = std::min(rowY, wides[wideIdx].fY);
        }

        int rowCapStart = capIdx;
        while (capIdx < caps.size() && caps[capIdx].fY == rowY) {
            capIdx++;
        }
        int rowCapEnd = capIdx;

        int rowWideStart = wideIdx;
        while (wideIdx < wides.size() && wides[wideIdx].fY == rowY) {
            wideIdx++;
        }
        int rowWideEnd = wideIdx;

        auto isGapFilled = [&](uint16_t startX, uint16_t endX) -> bool {
            for (int w = rowWideStart; w < rowWideEnd; ++w) {
                if (wides[w].fX == startX && wides[w].fX + wides[w].fWidth == endX) {
                    return true;
                }
            }
            return false;
        };

        // Process each pixel row within this tile row [rowY, rowY + kTileHeight)
        for (uint16_t py = rowY; py < rowY + kTileHeight && py < viewportHeight; ++py) {
            std::vector<ScanlineOracle8x::RowWindingInterval> oracleIntervals =
                    fOracle.buildRowIntervals(py);

            int prevEndTileX = 0;

            for (int c = rowCapStart; c < rowCapEnd; ++c) {
                const auto& cap = caps[c];
                uint16_t alphaStartTileX = cap.fX;
                uint16_t alphaEndTileX = cap.fX + cap.fWidth;
                uint16_t spannedTiles = cap.fWidth / kTileWidth;

                // A. Validate gap preceding this cap [prevEndTileX, alphaStartTileX)
                if (alphaStartTileX > prevEndTileX) {
                    bool filled = isGapFilled(prevEndTileX, alphaStartTileX);
                    allPass &= this->validateGapSpan(reporter,
                                                     prevEndTileX,
                                                     alphaStartTileX,
                                                     py,
                                                     oracleIntervals,
                                                     filled);
                }

                // B. Validate boundary column left of the first tile in this cap run
                if (alphaStartTileX > 0) {
                    uint16_t leftColX = alphaStartTileX - 1;
                    bool leftFill = false;
                    for (int w = rowWideStart; w < rowWideEnd; ++w) {
                        if (wides[w].fX + wides[w].fWidth == alphaStartTileX) {
                            leftFill = true;
                            break;
                        }
                    }
                    allPass &= this->validateBoundaryColumn(
                            reporter, leftColX, py, oracleIntervals, leftFill);
                }

                // C. Validate inside the alpha tiles span
                allPass &= this->validateAlphaTileSpan(reporter,
                                                       cap.fX,
                                                       cap.fY,
                                                       cap.fAlphaIndex,
                                                       spannedTiles,
                                                       py,
                                                       oracleIntervals,
                                                       maxSampleDiffOut);

                // D. Validate boundary column right of the last tile in this cap run
                if (alphaEndTileX < viewportWidth) {
                    uint16_t rightColX = alphaEndTileX;
                    bool rightFill = false;
                    for (int w = rowWideStart; w < rowWideEnd; ++w) {
                        if (wides[w].fX == alphaEndTileX) {
                            rightFill = true;
                            break;
                        }
                    }
                    allPass &= this->validateBoundaryColumn(
                            reporter, rightColX, py, oracleIntervals, rightFill);
                }

                prevEndTileX = alphaEndTileX;
            }

            // E. Validate trailing gap to viewport edge [prevEndTileX, viewportWidth)
            if (prevEndTileX < viewportWidth) {
                bool filled = isGapFilled(prevEndTileX, viewportWidth);
                allPass &= this->validateGapSpan(reporter,
                                                 prevEndTileX,
                                                 viewportWidth,
                                                 py,
                                                 oracleIntervals,
                                                 filled);
            }
        }
    }

    return allPass;
}

template <uint16_t kTileWidth, uint16_t kTileHeight>
bool OracleValidator<kTileWidth, kTileHeight>::validateStreamInvariants(
        skiatest::Reporter* reporter, uint16_t viewportWidth, uint16_t viewportHeight) const {
    const auto& caps = fEnds.caps();
    const auto& wides = fWides.tiles();

    if (caps.empty() && wides.empty()) {
        return true;
    }

    // Validate EndCaps invariants
    uint16_t lastCapY = 0;
    uint16_t lastCapEndX = 0;
    bool hasLastCap = false;
    for (int i = 0; i < caps.size(); ++i) {
        const auto& cap = caps[i];
        if (cap.fX % kTileWidth != 0) {
            ERRORF(reporter, "[%s] Cap[%d] fX (%u) not aligned to kTileWidth (%u)",
                   fTestName, i, cap.fX, kTileWidth);
            return false;
        }
        if (cap.fY % kTileHeight != 0) {
            ERRORF(reporter, "[%s] Cap[%d] fY (%u) not aligned to kTileHeight (%u)",
                   fTestName, i, cap.fY, kTileHeight);
            return false;
        }
        if (cap.fWidth % kTileWidth != 0 || cap.fWidth == 0) {
            ERRORF(reporter, "[%s] Cap[%d] fWidth (%u) not valid multiple of kTileWidth (%u)",
                   fTestName, i, cap.fWidth, kTileWidth);
            return false;
        }
        if (cap.fAlphaIndex % (kTileWidth * kTileHeight) != 0) {
            ERRORF(reporter, "[%s] Cap[%d] fAlphaIndex (%d) not multiple of tile size (%d)",
                   fTestName, i, cap.fAlphaIndex, static_cast<int>(kTileWidth * kTileHeight));
            return false;
        }
        if (hasLastCap) {
            if (cap.fY < lastCapY) {
                ERRORF(reporter, "[%s] Cap[%d] fY (%u) < previous row fY (%u)",
                       fTestName, i, cap.fY, lastCapY);
                return false;
            }
            if (cap.fY == lastCapY && cap.fX < lastCapEndX) {
                ERRORF(reporter, "[%s] Cap[%d] fX (%u) overlaps with previous cap endX (%u)",
                       fTestName, i, cap.fX, lastCapEndX);
                return false;
            }
        }
        lastCapY = cap.fY;
        lastCapEndX = cap.fX + cap.fWidth;
        hasLastCap = true;
    }

    // Validate WideTiles invariants
    uint16_t lastWideY = 0;
    uint16_t lastWideEndX = 0;
    bool hasLastWide = false;
    for (int i = 0; i < wides.size(); ++i) {
        const auto& wide = wides[i];
        if (wide.fX % kTileWidth != 0) {
            ERRORF(reporter, "[%s] Wide[%d] fX (%u) not aligned to kTileWidth (%u)",
                   fTestName, i, wide.fX, kTileWidth);
            return false;
        }
        if (wide.fY % kTileHeight != 0) {
            ERRORF(reporter, "[%s] Wide[%d] fY (%u) not aligned to kTileHeight (%u)",
                   fTestName, i, wide.fY, kTileHeight);
            return false;
        }
        if (wide.fWidth % kTileWidth != 0 || wide.fWidth == 0) {
            ERRORF(reporter, "[%s] Wide[%d] fWidth (%u) not valid multiple of kTileWidth (%u)",
                   fTestName, i, wide.fWidth, kTileWidth);
            return false;
        }
        if (hasLastWide) {
            if (wide.fY < lastWideY) {
                ERRORF(reporter, "[%s] Wide[%d] fY (%u) < previous row fY (%u)",
                       fTestName, i, wide.fY, lastWideY);
                return false;
            }
            if (wide.fY == lastWideY && wide.fX < lastWideEndX) {
                ERRORF(reporter, "[%s] Wide[%d] fX (%u) overlaps with previous wide endX (%u)",
                       fTestName, i, wide.fX, lastWideEndX);
                return false;
            }
        }
        lastWideY = wide.fY;
        lastWideEndX = wide.fX + wide.fWidth;
        hasLastWide = true;
    }

    return true;
}

template <uint16_t kTileWidth, uint16_t kTileHeight>
bool OracleValidator<kTileWidth, kTileHeight>::validateBoundaryColumn(
        skiatest::Reporter* reporter,
        uint16_t px,
        uint16_t py,
        const std::vector<ScanlineOracle8x::RowWindingInterval>& oracleIntervals,
        bool expectedFill) const {
    skvx::int8 w = GetOracleWinding(px, oracleIntervals);
    int activeCount = 0;
    uint16_t tileX = px / kTileWidth;
    uint16_t tileY = py / kTileHeight;

    for (int k = 0; k < 8; ++k) {
        bool covered = (w[k] != 0);
        if (fStrictness == Strictness::kNonStrict && covered != expectedFill) {
            float subX = (static_cast<float>(kMsaaPattern<uint8_t>[k]) + 0.5f) / 8.0f;
            float subY = (static_cast<float>(k) + 0.5f) / 8.0f;
            SkPoint subPt = SkPoint::Make(px + subX, py + subY);
            if (this->isWithinTolerance(subPt, tileX, tileY)) {
                covered = expectedFill;
            }
        }
        if (covered) activeCount++;
    }

    // Allow 1-sample tolerance on boundary columns for curved paths due to flattening chord error
    bool matches = expectedFill ? (activeCount >= 7) : (activeCount <= 1);
    if (!matches) {
        ERRORF(reporter,
               "[%s] Boundary Column Winding Mismatch at (px=%u, py=%u): Expected %s, "
               "but Oracle has winding [%d,%d,%d,%d,%d,%d,%d,%d] (%d non-zero)",
               fTestName,
               px,
               py,
               expectedFill ? "Solid Fill" : "Empty Space",
               w[0], w[1], w[2], w[3], w[4], w[5], w[6], w[7],
               activeCount);
        return false;
    }
    return true;
}

template <uint16_t kTileWidth, uint16_t kTileHeight>
bool OracleValidator<kTileWidth, kTileHeight>::validateGapSpan(
        skiatest::Reporter* reporter,
        int startPx,
        int endPx,
        uint16_t py,
        const std::vector<ScanlineOracle8x::RowWindingInterval>& oracleIntervals,
        bool expectedFill) const {
    bool allPass = true;
    uint16_t tileY = py / kTileHeight;
    for (int px = startPx; px < endPx; ++px) {
        skvx::int8 w = GetOracleWinding(px, oracleIntervals);
        int activeCount = 0;
        uint16_t tileX = px / kTileWidth;
        for (int k = 0; k < 8; ++k) {
            bool covered = (w[k] != 0);
            if (fStrictness == Strictness::kNonStrict && covered != expectedFill) {
                float subX = (static_cast<float>(kMsaaPattern<uint8_t>[k]) + 0.5f) / 8.0f;
                float subY = (static_cast<float>(k) + 0.5f) / 8.0f;
                SkPoint subPt = SkPoint::Make(px + subX, py + subY);
                if (this->isWithinTolerance(subPt, tileX, tileY)) {
                    covered = expectedFill;
                }
            }
            if (covered) activeCount++;
        }

        // Allow 1-sample tolerance on gap edges for curved paths due to flattening chord error
        bool matches = expectedFill ? (activeCount >= 7) : (activeCount <= 1);
        if (!matches) {
            ERRORF(reporter,
                   "[%s] Gap Span Winding Mismatch at (px=%d, py=%u): Expected %s, "
                   "but Oracle has winding [%d,%d,%d,%d,%d,%d,%d,%d] (%d non-zero)",
                   fTestName,
                   px,
                   py,
                   expectedFill ? "Solid Fill" : "Empty Space",
                   w[0], w[1], w[2], w[3], w[4], w[5], w[6], w[7],
                   activeCount);
            allPass = false;
            break;
        }
    }
    return allPass;
}

template <uint16_t kTileWidth, uint16_t kTileHeight>
bool OracleValidator<kTileWidth, kTileHeight>::validateAlphaTileSpan(
        skiatest::Reporter* reporter,
        uint16_t startTileX,
        uint16_t rowY,
        uint32_t startAlphaIdx,
        uint16_t spannedTiles,
        uint16_t py,
        const std::vector<ScanlineOracle8x::RowWindingInterval>& oracleIntervals,
        uint32_t* maxSampleDiffOut) const {
    uint16_t localY = py - rowY;
    uint16_t tileY = rowY / kTileHeight;
    bool allPass = true;

    for (uint16_t t = 0; t < spannedTiles; ++t) {
        uint16_t tileStartX = startTileX + t * kTileWidth;
        uint16_t tileX = tileStartX / kTileWidth;
        uint32_t tileStartAlphaIdx = startAlphaIdx + t * (kTileWidth * kTileHeight);

        for (uint16_t localX = 0; localX < kTileWidth; ++localX) {
            uint16_t px = tileStartX + localX;
            uint32_t alphaIdx = tileStartAlphaIdx + localY * kTileWidth + localX;

            if (alphaIdx >= static_cast<uint32_t>(fExactWindings.size())) {
                ERRORF(reporter,
                       "[%s] Alpha index %u out of bounds (exactWindings size %d) at tile(%d,%d) "
                       "pixel(%d,%d)",
                       fTestName,
                       alphaIdx,
                       fExactWindings.size(),
                       static_cast<int>(tileX),
                       static_cast<int>(tileY),
                       static_cast<int>(localX),
                       static_cast<int>(localY));
                return false;
            }

            skvx::int8 actualWinding = fExactWindings[alphaIdx];
            skvx::int8 oracleWinding = GetOracleWinding(px, oracleIntervals);

            int sampleDiff = 0;
            for (int k = 0; k < 8; ++k) {
                if (actualWinding[k] != oracleWinding[k]) {
                    bool isError = true;
                    if (fStrictness == Strictness::kNonStrict) {
                        float subX = (static_cast<float>(kMsaaPattern<uint8_t>[k]) + 0.5f) / 8.0f;
                        float subY = (static_cast<float>(k) + 0.5f) / 8.0f;
                        SkPoint subPt = SkPoint::Make(px + subX, py + subY);
                        if (this->isWithinTolerance(subPt, tileX, tileY)) {
                            isError = false;
                        }
                    }
                    if (isError) {
                        sampleDiff++;
                    }
                }
            }

            if (maxSampleDiffOut) {
                *maxSampleDiffOut = std::max(*maxSampleDiffOut, static_cast<uint32_t>(sampleDiff));
            }

            if (sampleDiff > 4) {
                CoverageTestUtils::PrintWindingDiagnostics<kTileWidth, kTileHeight>(
                        reporter,
                        fTestName,
                        tileStartX,
                        rowY,
                        px,
                        py,
                        actualWinding,
                        oracleWinding,
                        fPolyline,
                        fTiler,
                        fExactWindings,
                        tileStartAlphaIdx,
                        &fOracle);
                ERRORF(reporter,
                       "[%s] Direct Winding Mismatch at tile(%d,%d) pixel(%d,%d) (px=%u, py=%u): "
                       "Diff %d samples. Actual Winding [%d,%d,%d,%d,%d,%d,%d,%d], Oracle Winding "
                       "[%d,%d,%d,%d,%d,%d,%d,%d]",
                       fTestName,
                       static_cast<int>(tileX),
                       static_cast<int>(tileY),
                       static_cast<int>(localX),
                       static_cast<int>(localY),
                       px,
                       py,
                       sampleDiff,
                       actualWinding[0], actualWinding[1], actualWinding[2], actualWinding[3],
                       actualWinding[4], actualWinding[5], actualWinding[6], actualWinding[7],
                       oracleWinding[0], oracleWinding[1], oracleWinding[2], oracleWinding[3],
                       oracleWinding[4], oracleWinding[5], oracleWinding[6], oracleWinding[7]);
                allPass = false;
            }
        }
    }
    return allPass;
}

template <uint16_t kTileWidth, uint16_t kTileHeight>
float OracleValidator<kTileWidth, kTileHeight>::DistanceSqToSegment(SkPoint p,
                                                                    SkPoint a,
                                                                    SkPoint b) {
    float dx = b.fX - a.fX;
    float dy = b.fY - a.fY;
    float lenSq = dx * dx + dy * dy;
    if (lenSq == 0.0f) {
        float px = p.fX - a.fX;
        float py = p.fY - a.fY;
        return px * px + py * py;
    }
    float t = ((p.fX - a.fX) * dx + (p.fY - a.fY) * dy) / lenSq;
    t = std::max(0.0f, std::min(1.0f, t));
    float projX = a.fX + t * dx;
    float projY = a.fY + t * dy;
    float distSqX = p.fX - projX;
    float distSqY = p.fY - projY;
    return distSqX * distSqX + distSqY * distSqY;
}

template <uint16_t kTileWidth, uint16_t kTileHeight>
void OracleValidator<kTileWidth, kTileHeight>::buildTileLineMap() {
    if (!fTiler || !fPolyline) {
        return;
    }
    for (const auto& tile : fTiler->getTiles()) {
        uint32_t lineIdx = tile.fPackedLineIdxIntersectionMask >> IntersectionBits::INT_MASK_SHIFT;
        if (lineIdx + 1 < static_cast<uint32_t>(fPolyline->points().size())) {
            Line line = fPolyline->getLine(lineIdx);
            uint32_t tileKey = (static_cast<uint32_t>(tile.y) << 16) | tile.x;
            auto& lines = fTileLineMap[tileKey];
            bool exists = false;
            for (const auto& existing : lines) {
                if (existing.p0 == line.p0 && existing.p1 == line.p1) {
                    exists = true;
                    break;
                }
            }
            if (!exists) {
                lines.push_back(line);
            }
        }
    }
}

template <uint16_t kTileWidth, uint16_t kTileHeight>
bool OracleValidator<kTileWidth, kTileHeight>::isWithinTolerance(SkPoint subPt,
                                                                 uint16_t tileX,
                                                                 uint16_t tileY) const {
    for (int dy = -1; dy <= 1; ++dy) {
        int ny = static_cast<int>(tileY) + dy;
        if (ny < 0) {
            continue;
        }
        for (int dx = -1; dx <= 1; ++dx) {
            int nx = static_cast<int>(tileX) + dx;
            if (nx < 0) {
                continue;
            }
            uint32_t key = (static_cast<uint32_t>(ny) << 16) | static_cast<uint32_t>(nx);
            auto it = fTileLineMap.find(key);
            if (it != fTileLineMap.end()) {
                for (const auto& line : it->second) {
                    if (DistanceSqToSegment(subPt, line.p0, line.p1) <= fToleranceSq) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

// Explicit template instantiations for supported tile sizes
template class OracleValidator<4, 4>;
template class OracleValidator<8, 8>;

}  // namespace skgpu::graphite