/*
 * 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/Strip.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 SkTDArray<Strip>& stripBuf, const SkTDArray<uint8_t>& alphaBuf,
        const SkTDArray<skvx::int8>& exactWindings, const Polyline* polyline,
        const Tiles<kTileWidth, kTileHeight>* tiler, const char* testName, Strictness strictness)
        : fPath(path)
        , fStrips(stripBuf)
        , fAlphaBuf(alphaBuf)
        , 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;
    }

    constexpr size_t kBytesPerTile = kTileWidth * kTileHeight;
    bool allPass = true;
    int stripIdx = 0;
    const int numStrips = fStrips.size();

    // Zero-copy streaming walk row-by-row directly from fStrips array
    while (stripIdx < numStrips) {
        if (fStrips[stripIdx].fX == Strip::kCapCoord) {
            stripIdx++;
            continue;
        }

        uint16_t rowY = fStrips[stripIdx].fY;
        int rowStartIdx = stripIdx;

        // Find range [rowStartIdx, rowEndIdx) for the current tile row
        int rowEndIdx = rowStartIdx;
        while (rowEndIdx < numStrips && fStrips[rowEndIdx].fY == rowY) {
            if (fStrips[rowEndIdx].fX == Strip::kCapCoord) {
                rowEndIdx++;
                break;
            }
            rowEndIdx++;
        }

        // Advance main stream index to next row
        stripIdx = rowEndIdx;

        // Process each pixel row within this tile row [rowY, rowY + kTileHeight)
        for (uint16_t py = rowY; py < rowY + kTileHeight && py < viewportHeight; ++py) {
            // 1. Invoke reference oracle to compute ground-truth winding intervals
            std::vector<ScanlineOracle8x::RowWindingInterval> oracleIntervals =
                    fOracle.buildRowIntervals(py);

            int prevEndTileX = 0;
            uint16_t alphaEndTileX = 0;

            // 2. Stream-walk strips in current tile row
            for (int i = rowStartIdx; i < rowEndIdx; ++i) {
                const Strip& curr = fStrips[i];
                if (curr.fX == Strip::kCapCoord) {
                    // Cap strip ends the row: validate trailing gap to viewport edge
                    if (alphaEndTileX < viewportWidth) {
                        allPass &= this->validateGapSpan(reporter,
                                                         alphaEndTileX,
                                                         viewportWidth,
                                                         py,
                                                         oracleIntervals,
                                                         curr.shouldFill());
                    }
                    break;
                }

                uint32_t startIdx = curr.alphaIndex();
                uint32_t endIdx = (i + 1 < numStrips) ? fStrips[i + 1].alphaIndex() : startIdx;
                uint16_t spannedTiles = (endIdx - startIdx) / kBytesPerTile;
                uint16_t alphaStartTileX = curr.fX;
                alphaEndTileX = curr.fX + spannedTiles * kTileWidth;

                // A. Validate gap preceding this strip [prevEndTileX, alphaStartTileX)
                if (alphaStartTileX > prevEndTileX) {
                    allPass &= this->validateGapSpan(reporter,
                                                     prevEndTileX,
                                                     alphaStartTileX,
                                                     py,
                                                     oracleIntervals,
                                                     curr.shouldFill());
                }

                // B. Validate boundary column left of the first tile in a run
                if (alphaStartTileX > 0) {
                    uint16_t leftColX = alphaStartTileX - 1;
                    allPass &= this->validateBoundaryColumn(
                            reporter, leftColX, py, oracleIntervals, curr.shouldFill());
                }

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

                // D. Validate boundary column right of the last tile in a run
                uint16_t rightColX = alphaEndTileX;
                if (rightColX < viewportWidth && i + 1 < numStrips) {
                    bool nextFill = fStrips[i + 1].shouldFill();
                    allPass &= this->validateBoundaryColumn(
                            reporter, rightColX, py, oracleIntervals, nextFill);
                }

                prevEndTileX = alphaEndTileX;
            }
        }
    }

    return allPass;
}

template <uint16_t kTileWidth, uint16_t kTileHeight>
bool OracleValidator<kTileWidth, kTileHeight>::validateStreamInvariants(
        skiatest::Reporter* reporter, uint16_t viewportWidth, uint16_t viewportHeight) const {
    if (fStrips.empty()) {
        if (!fAlphaBuf.empty()) {
            ERRORF(reporter,
                   "[%s] Empty strip buffer but non-empty alpha buffer (%d bytes)",
                   fTestName,
                   fAlphaBuf.size());
            return false;
        }
        return true;
    }

    uint16_t lastY = 0;
    bool hasLastY = false;

    for (int i = 0; i < fStrips.size(); ++i) {
        const Strip& s = fStrips[i];
        if (s.fX != Strip::kCapCoord) {
            if (s.fX % kTileWidth != 0) {
                ERRORF(reporter,
                       "[%s] Strip[%d] fX (%u) is not aligned to kTileWidth (%u)",
                       fTestName,
                       i,
                       s.fX,
                       kTileWidth);
                return false;
            }
            if (s.fY % kTileHeight != 0) {
                ERRORF(reporter,
                       "[%s] Strip[%d] fY (%u) is not aligned to kTileHeight (%u)",
                       fTestName,
                       i,
                       s.fY,
                       kTileHeight);
                return false;
            }
            if (hasLastY && s.fY < lastY) {
                ERRORF(reporter,
                       "[%s] Strip[%d] fY (%u) < previous row fY (%u)",
                       fTestName,
                       i,
                       s.fY,
                       lastY);
                return false;
            }
            lastY = s.fY;
            hasLastY = true;
        }

        if (s.alphaIndex() % (kTileWidth * kTileHeight) != 0) {
            ERRORF(reporter,
                   "[%s] Strip[%d] alphaIndex (%u) is not a multiple of tile size (%d)",
                   fTestName,
                   i,
                   s.alphaIndex(),
                   static_cast<int>(kTileWidth * kTileHeight));
            return false;
        }
    }
    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,
        const Strip& strip,
        uint32_t startAlphaIdx,
        uint16_t spannedTiles,
        uint16_t py,
        const std::vector<ScanlineOracle8x::RowWindingInterval>& oracleIntervals,
        uint32_t* maxSampleDiffOut) const {
    uint16_t rowY = strip.fY;
    uint16_t localY = py - rowY;
    uint16_t tileY = rowY / kTileHeight;
    bool allPass = true;

    for (uint16_t t = 0; t < spannedTiles; ++t) {
        uint16_t tileStartX = strip.fX + 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