/*
 * Copyright 2019 Google LLC
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#include "src/gpu/ganesh/ops/PathInnerTriangulateOp.h"

#include "include/core/SkPathTypes.h"
#include "include/core/SkString.h"
#include "include/gpu/ganesh/GrRecordingContext.h"
#include "include/private/SkAlignedStorage.h"
#include "include/private/SkOnce.h"
#include "src/core/SkArenaAlloc.h"
#include "src/core/SkSLTypeShared.h"
#include "src/gpu/ResourceKey.h"
#include "src/gpu/ganesh/GrAppliedClip.h"
#include "src/gpu/ganesh/GrEagerVertexAllocator.h"
#include "src/gpu/ganesh/GrGeometryProcessor.h"
#include "src/gpu/ganesh/GrOpFlushState.h"
#include "src/gpu/ganesh/GrPipeline.h"
#include "src/gpu/ganesh/GrProcessorAnalysis.h"
#include "src/gpu/ganesh/GrProgramInfo.h"
#include "src/gpu/ganesh/GrRecordingContextPriv.h"
#include "src/gpu/ganesh/GrRenderTargetProxy.h"
#include "src/gpu/ganesh/GrResourceProvider.h"
#include "src/gpu/ganesh/GrShaderCaps.h"
#include "src/gpu/ganesh/GrShaderVar.h"
#include "src/gpu/ganesh/GrSurfaceProxyView.h"
#include "src/gpu/ganesh/GrUserStencilSettings.h"
#include "src/gpu/ganesh/glsl/GrGLSLVertexGeoBuilder.h"
#include "src/gpu/ganesh/ops/FillPathFlags.h"
#include "src/gpu/ganesh/tessellate/GrPathTessellationShader.h"
#include "src/gpu/ganesh/tessellate/PathTessellator.h"
#include "src/gpu/tessellate/Tessellation.h"

#include <memory>

class GrGLSLVaryingHandler;

namespace skgpu {
class KeyBuilder;
}

using namespace skia_private;

#if !defined(SK_ENABLE_OPTIMIZE_SIZE)

namespace skgpu::ganesh {

namespace {

// Fills an array of convex hulls surrounding 4-point cubic or conic instances. This shader is used
// for the "cover" pass after the curves have been fully stencilled.
class HullShader : public GrPathTessellationShader {
public:
    HullShader(const SkMatrix& viewMatrix, SkPMColor4f color, const GrShaderCaps& shaderCaps)
            : GrPathTessellationShader(kTessellate_HullShader_ClassID,
                                       GrPrimitiveType::kTriangleStrip,
                                       viewMatrix,
                                       color,
                                       PatchAttribs::kNone) {
        fInstanceAttribs.emplace_back("p01", kFloat4_GrVertexAttribType, SkSLType::kFloat4);
        fInstanceAttribs.emplace_back("p23", kFloat4_GrVertexAttribType, SkSLType::kFloat4);
        if (!shaderCaps.fInfinitySupport) {
            // A conic curve is written out with p3=[w,Infinity], but GPUs that don't support
            // infinity can't detect this. On these platforms we also write out an extra float with
            // each patch that explicitly tells the shader what type of curve it is.
            fInstanceAttribs.emplace_back("curveType", kFloat_GrVertexAttribType, SkSLType::kFloat);
        }
        this->setInstanceAttributesWithImplicitOffsets(fInstanceAttribs.data(),
                                                       fInstanceAttribs.size());
        SkASSERT(fInstanceAttribs.size() <= kMaxInstanceAttribCount);

        if (!shaderCaps.fVertexIDSupport) {
            constexpr static Attribute kVertexIdxAttrib("vertexidx", kFloat_GrVertexAttribType,
                                                        SkSLType::kFloat);
            this->setVertexAttributesWithImplicitOffsets(&kVertexIdxAttrib, 1);
        }
    }

private:
    const char* name() const final { return "tessellate_HullShader"; }
    void addToKey(const GrShaderCaps&, KeyBuilder*) const final {}
    std::unique_ptr<ProgramImpl> makeProgramImpl(const GrShaderCaps&) const final;

    constexpr static int kMaxInstanceAttribCount = 3;
    STArray<kMaxInstanceAttribCount, Attribute> fInstanceAttribs;
};

std::unique_ptr<GrGeometryProcessor::ProgramImpl> HullShader::makeProgramImpl(
        const GrShaderCaps&) const {
    class Impl : public GrPathTessellationShader::Impl {
        void emitVertexCode(const GrShaderCaps& shaderCaps,
                            const GrPathTessellationShader&,
                            GrGLSLVertexBuilder* v,
                            GrGLSLVaryingHandler*,
                            GrGPArgs* gpArgs) override {
            if (shaderCaps.fInfinitySupport) {
                v->insertFunction(
                "bool is_conic_curve() { return isinf(p23.w); }"
                "bool is_non_triangular_conic_curve() {"
                    // We consider a conic non-triangular as long as its weight isn't infinity.
                    // NOTE: "isinf == false" works on Mac Radeon GLSL; "!isinf" can get the wrong
                    // answer.
                    "return isinf(p23.z) == false;"
                "}"
                );
            } else {
                v->insertFunction(SkStringPrintf(
                "bool is_conic_curve() { return curveType != %g; }",
                        tess::kCubicCurveType).c_str());
                v->insertFunction(SkStringPrintf(
                "bool is_non_triangular_conic_curve() {"
                    "return curveType == %g;"
                "}", tess::kConicCurveType).c_str());
            }
            v->codeAppend(
            "float2 p0=p01.xy, p1=p01.zw, p2=p23.xy, p3=p23.zw;"
            "if (is_conic_curve()) {"
                // Conics are 3 points, with the weight in p3.
                "float w = p3.x;"
                "p3 = p2;"  // Duplicate the endpoint for shared code that also runs on cubics.
                "if (is_non_triangular_conic_curve()) {"
                    // Convert the points to a trapeziodal hull that circumcscribes the conic.
                    "float2 p1w = p1 * w;"
                    "float T = .51;"  // Bias outward a bit to ensure we cover the outermost samples.
                    "float2 c1 = mix(p0, p1w, T);"
                    "float2 c2 = mix(p2, p1w, T);"
                    "float iw = 1 / mix(1, w, T);"
                    "p2 = c2 * iw;"
                    "p1 = c1 * iw;"
                "}"
            "}"

            // Translate the points to v0..3 where v0=0.
            "float2 v1 = p1 - p0;"
            "float2 v2 = p2 - p0;"
            "float2 v3 = p3 - p0;"

            // Reorder the points so v2 bisects v1 and v3.
            "if (sign(cross_length_2d(v2, v1)) == sign(cross_length_2d(v2, v3))) {"
                "float2 tmp = p2;"
                "if (sign(cross_length_2d(v1, v2)) != sign(cross_length_2d(v1, v3))) {"
                    "p2 = p1;"  // swap(p2, p1)
                    "p1 = tmp;"
                "} else {"
                    "p2 = p3;"  // swap(p2, p3)
                    "p3 = tmp;"
                "}"
            "}"
            );

            if (shaderCaps.fVertexIDSupport) {
                // If we don't have sk_VertexID support then "vertexidx" already came in as a
                // vertex attrib.
                v->codeAppend(
                // sk_VertexID comes in fan order. Convert to strip order.
                "int vertexidx = sk_VertexID;"
                "vertexidx ^= vertexidx >> 1;");
            }

            v->codeAppend(
            // Find the "turn direction" of each corner and net turn direction.
            "float vertexdir = 0;"
            "float netdir = 0;"
            "float2 prev, next;"
            "float dir;"
            "float2 localcoord;"
            "float2 nextcoord;"
            );

            for (int i = 0; i < 4; ++i) {
                v->codeAppendf(
                "prev = p%i - p%i;", i, (i + 3) % 4);
                v->codeAppendf(
                "next = p%i - p%i;", (i + 1) % 4, i);
                v->codeAppendf(
                "dir = sign(cross_length_2d(prev, next));"
                "if (vertexidx == %i) {"
                    "vertexdir = dir;"
                    "localcoord = p%i;"
                    "nextcoord = p%i;"
                "}"
                "netdir += dir;", i, i, (i + 1) % 4);
            }

            v->codeAppend(
            // Remove the non-convex vertex, if any.
            "if (vertexdir != sign(netdir)) {"
                "localcoord = nextcoord;"
            "}"

            "float2 vertexpos = AFFINE_MATRIX * localcoord + TRANSLATE;");
            gpArgs->fLocalCoordVar.set(SkSLType::kFloat2, "localcoord");
            gpArgs->fPositionVar.set(SkSLType::kFloat2, "vertexpos");
        }
    };
    return std::make_unique<Impl>();
}

}  // anonymous namespace

void PathInnerTriangulateOp::visitProxies(const GrVisitProxyFunc& func) const {
    if (fPipelineForFills) {
        fPipelineForFills->visitProxies(func);
    } else {
        fProcessors.visitProxies(func);
    }
}

GrDrawOp::FixedFunctionFlags PathInnerTriangulateOp::fixedFunctionFlags() const {
    auto flags = FixedFunctionFlags::kUsesStencil;
    if (GrAAType::kNone != fAAType) {
        flags |= FixedFunctionFlags::kUsesHWAA;
    }
    return flags;
}

GrProcessorSet::Analysis PathInnerTriangulateOp::finalize(const GrCaps& caps,
                                                          const GrAppliedClip* clip,
                                                          GrClampType clampType) {
    return fProcessors.finalize(fColor, GrProcessorAnalysisCoverage::kNone, clip, nullptr, caps,
                                clampType, &fColor);
}

void PathInnerTriangulateOp::pushFanStencilProgram(const GrTessellationShader::ProgramArgs& args,
                                                   const GrPipeline* pipelineForStencils,
                                                   const GrUserStencilSettings* stencil) {
    SkASSERT(pipelineForStencils);
    auto shader = GrPathTessellationShader::MakeSimpleTriangleShader(args.fArena, fViewMatrix,
                                                                     SK_PMColor4fTRANSPARENT);
    fFanPrograms.push_back(GrTessellationShader::MakeProgram(args, shader, pipelineForStencils,
                                                             stencil)); }

void PathInnerTriangulateOp::pushFanFillProgram(const GrTessellationShader::ProgramArgs& args,
                                                const GrUserStencilSettings* stencil) {
    SkASSERT(fPipelineForFills);
    auto shader = GrPathTessellationShader::MakeSimpleTriangleShader(args.fArena, fViewMatrix,
                                                                     fColor);
    fFanPrograms.push_back(GrTessellationShader::MakeProgram(args, shader, fPipelineForFills,
                                                             stencil));
}

void PathInnerTriangulateOp::prePreparePrograms(const GrTessellationShader::ProgramArgs& args,
                                                GrAppliedClip&& appliedClip) {
    SkASSERT(!fFanTriangulator);
    SkASSERT(!fFanPolys);
    SkASSERT(!fPipelineForFills);
    SkASSERT(!fTessellator);
    SkASSERT(!fStencilCurvesProgram);
    SkASSERT(fFanPrograms.empty());
    SkASSERT(!fCoverHullsProgram);

    if (fPath.countVerbs() <= 0) {
        return;
    }

    // If using wireframe, we have to fall back on a standard Redbook "stencil then cover" algorithm
    // instead of bypassing the stencil buffer to fill the fan directly.
    bool forceRedbookStencilPass =
            (fPathFlags & (FillPathFlags::kStencilOnly | FillPathFlags::kWireframe));
    bool doFill = !(fPathFlags & FillPathFlags::kStencilOnly);

    bool isLinear;
    fFanTriangulator = args.fArena->make<GrInnerFanTriangulator>(fPath, args.fArena);
    fFanPolys = fFanTriangulator->pathToPolys(&fFanBreadcrumbs, &isLinear);

    // Create a pipeline for stencil passes if needed.
    const GrPipeline* pipelineForStencils = nullptr;
    if (forceRedbookStencilPass || !isLinear) {  // Curves always get stencilled.
        auto pipelineFlags = (fPathFlags & FillPathFlags::kWireframe)
                ? GrPipeline::InputFlags::kWireframe
                : GrPipeline::InputFlags::kNone;
        pipelineForStencils = GrPathTessellationShader::MakeStencilOnlyPipeline(
                args, fAAType, appliedClip.hardClip(), pipelineFlags);
    }

    // Create a pipeline for fill passes if needed.
    if (doFill) {
        fPipelineForFills = GrTessellationShader::MakePipeline(args, fAAType,
                                                               std::move(appliedClip),
                                                               std::move(fProcessors));
    }

    // Pass 1: Tessellate the outer curves into the stencil buffer.
    if (!isLinear) {
        fTessellator = PathCurveTessellator::Make(args.fArena,
                                                  args.fCaps->shaderCaps()->fInfinitySupport);
        auto* tessShader = GrPathTessellationShader::Make(*args.fCaps->shaderCaps(),
                                                          args.fArena,
                                                          fViewMatrix,
                                                          SK_PMColor4fTRANSPARENT,
                                                          fTessellator->patchAttribs());
        const GrUserStencilSettings* stencilPathSettings =
                GrPathTessellationShader::StencilPathSettings(GrFillRuleForSkPath(fPath));
        fStencilCurvesProgram = GrTessellationShader::MakeProgram(args,
                                                                  tessShader,
                                                                  pipelineForStencils,
                                                                  stencilPathSettings);
    }

    // Pass 2: Fill the path's inner fan with a stencil test against the curves.
    if (fFanPolys) {
        if (forceRedbookStencilPass) {
            // Use a standard Redbook "stencil then cover" algorithm instead of bypassing the
            // stencil buffer to fill the fan directly.
            const GrUserStencilSettings* stencilPathSettings =
                    GrPathTessellationShader::StencilPathSettings(GrFillRuleForSkPath(fPath));
            this->pushFanStencilProgram(args, pipelineForStencils, stencilPathSettings);
            if (doFill) {
                this->pushFanFillProgram(args,
                                         GrPathTessellationShader::TestAndResetStencilSettings());
            }
        } else if (isLinear) {
            // There are no outer curves! Ignore stencil and fill the path directly.
            SkASSERT(!pipelineForStencils);
            this->pushFanFillProgram(args, &GrUserStencilSettings::kUnused);
        } else if (!fPipelineForFills->hasStencilClip()) {
            // These are a twist on the standard Redbook stencil settings that allow us to fill the
            // inner polygon directly to the final render target. By the time these programs
            // execute, the outer curves will already be stencilled in. So if the stencil value is
            // zero, then it means the sample in question is not affected by any curves and we can
            // fill it in directly. If the stencil value is nonzero, then we don't fill and instead
            // continue the standard Redbook counting process.
            constexpr static GrUserStencilSettings kFillOrIncrDecrStencil(
                GrUserStencilSettings::StaticInitSeparate<
                    0x0000,                       0x0000,
                    GrUserStencilTest::kEqual,    GrUserStencilTest::kEqual,
                    0xffff,                       0xffff,
                    GrUserStencilOp::kKeep,       GrUserStencilOp::kKeep,
                    GrUserStencilOp::kIncWrap,    GrUserStencilOp::kDecWrap,
                    0xffff,                       0xffff>());

            constexpr static GrUserStencilSettings kFillOrInvertStencil(
                GrUserStencilSettings::StaticInit<
                    0x0000,
                    GrUserStencilTest::kEqual,
                    0xffff,
                    GrUserStencilOp::kKeep,
                    // "Zero" instead of "Invert" because the fan only touches any given pixel once.
                    GrUserStencilOp::kZero,
                    0xffff>());

            auto* stencil = (fPath.getFillType() == SkPathFillType::kWinding)
                    ? &kFillOrIncrDecrStencil
                    : &kFillOrInvertStencil;
            this->pushFanFillProgram(args, stencil);
        } else {
            // This is the same idea as above, but we use two passes instead of one because there is
            // a stencil clip. The stencil test isn't expressive enough to do the above tests and
            // also check the clip bit in a single pass.
            constexpr static GrUserStencilSettings kFillIfZeroAndInClip(
                GrUserStencilSettings::StaticInit<
                    0x0000,
                    GrUserStencilTest::kEqualIfInClip,
                    0xffff,
                    GrUserStencilOp::kKeep,
                    GrUserStencilOp::kKeep,
                    0xffff>());

            constexpr static GrUserStencilSettings kIncrDecrStencilIfNonzero(
                GrUserStencilSettings::StaticInitSeparate<
                    0x0000,                         0x0000,
                    // No need to check the clip because the previous stencil pass will have only
                    // written to samples already inside the clip.
                    GrUserStencilTest::kNotEqual,   GrUserStencilTest::kNotEqual,
                    0xffff,                         0xffff,
                    GrUserStencilOp::kIncWrap,      GrUserStencilOp::kDecWrap,
                    GrUserStencilOp::kKeep,         GrUserStencilOp::kKeep,
                    0xffff,                         0xffff>());

            constexpr static GrUserStencilSettings kInvertStencilIfNonZero(
                GrUserStencilSettings::StaticInit<
                    0x0000,
                    // No need to check the clip because the previous stencil pass will have only
                    // written to samples already inside the clip.
                    GrUserStencilTest::kNotEqual,
                    0xffff,
                    // "Zero" instead of "Invert" because the fan only touches any given pixel once.
                    GrUserStencilOp::kZero,
                    GrUserStencilOp::kKeep,
                    0xffff>());

            // Pass 2a: Directly fill fan samples whose stencil values (from curves) are zero.
            this->pushFanFillProgram(args, &kFillIfZeroAndInClip);

            // Pass 2b: Redbook counting on fan samples whose stencil values (from curves) != 0.
            auto* stencil = (fPath.getFillType() == SkPathFillType::kWinding)
                    ? &kIncrDecrStencilIfNonzero
                    : &kInvertStencilIfNonZero;
            this->pushFanStencilProgram(args, pipelineForStencils, stencil);
        }
    }

    // Pass 3: Draw convex hulls around each curve.
    if (doFill && !isLinear) {
        // By the time this program executes, every pixel will be filled in except the ones touched
        // by curves. We issue a final cover pass over the curves by drawing their convex hulls.
        // This will fill in any remaining samples and reset the stencil values back to zero.
        SkASSERT(fTessellator);
        auto* hullShader = args.fArena->make<HullShader>(fViewMatrix, fColor,
                                                         *args.fCaps->shaderCaps());
        fCoverHullsProgram = GrTessellationShader::MakeProgram(
                args, hullShader, fPipelineForFills,
                GrPathTessellationShader::TestAndResetStencilSettings());
    }
}

void PathInnerTriangulateOp::onPrePrepare(GrRecordingContext* context,
                                          const GrSurfaceProxyView& writeView,
                                          GrAppliedClip* clip,
                                          const GrDstProxyView& dstProxyView,
                                          GrXferBarrierFlags renderPassXferBarriers,
                                          GrLoadOp colorLoadOp) {
    // DMSAA is not supported on DDL.
    bool usesMSAASurface = writeView.asRenderTargetProxy()->numSamples() > 1;
    this->prePreparePrograms({context->priv().recordTimeAllocator(), writeView, usesMSAASurface,
                             &dstProxyView, renderPassXferBarriers, colorLoadOp,
                             context->priv().caps()},
                             (clip) ? std::move(*clip) : GrAppliedClip::Disabled());
    if (fStencilCurvesProgram) {
        context->priv().recordProgramInfo(fStencilCurvesProgram);
    }
    for (const GrProgramInfo* fanProgram : fFanPrograms) {
        context->priv().recordProgramInfo(fanProgram);
    }
    if (fCoverHullsProgram) {
        context->priv().recordProgramInfo(fCoverHullsProgram);
    }
}

SKGPU_DECLARE_STATIC_UNIQUE_KEY(gHullVertexBufferKey);

void PathInnerTriangulateOp::onPrepare(GrOpFlushState* flushState) {
    const GrCaps& caps = flushState->caps();

    if (!fFanTriangulator) {
        this->prePreparePrograms({flushState->allocator(), flushState->writeView(),
                                 flushState->usesMSAASurface(), &flushState->dstProxyView(),
                                 flushState->renderPassBarriers(), flushState->colorLoadOp(),
                                 &caps}, flushState->detachAppliedClip());
        if (!fFanTriangulator) {
            return;
        }
    }

    if (fFanPolys) {
        GrEagerDynamicVertexAllocator alloc(flushState, &fFanBuffer, &fBaseFanVertex);
        fFanVertexCount = fFanTriangulator->polysToTriangles(fFanPolys, &alloc, &fFanBreadcrumbs);
    }

    if (fTessellator) {
        auto tessShader = &fStencilCurvesProgram->geomProc().cast<GrPathTessellationShader>();
        fTessellator->prepareWithTriangles(flushState,
                                           tessShader->viewMatrix(),
                                           &fFanBreadcrumbs,
                                           {SkMatrix::I(), fPath, SK_PMColor4fTRANSPARENT},
                                           fPath.countVerbs());
    }

    if (!caps.shaderCaps()->fVertexIDSupport) {
        constexpr static float kStripOrderIDs[4] = {0, 1, 3, 2};

        SKGPU_DEFINE_STATIC_UNIQUE_KEY(gHullVertexBufferKey);

        fHullVertexBufferIfNoIDSupport = flushState->resourceProvider()->findOrMakeStaticBuffer(
                GrGpuBufferType::kVertex, sizeof(kStripOrderIDs), kStripOrderIDs,
                gHullVertexBufferKey);
    }
}

void PathInnerTriangulateOp::onExecute(GrOpFlushState* flushState, const SkRect& chainBounds) {
    if (fCoverHullsProgram &&
        fCoverHullsProgram->geomProc().hasVertexAttributes() &&
        !fHullVertexBufferIfNoIDSupport) {
        return;
    }

    if (fStencilCurvesProgram) {
        SkASSERT(fTessellator);
        flushState->bindPipelineAndScissorClip(*fStencilCurvesProgram, this->bounds());
        fTessellator->draw(flushState);
    }

    // Allocation of the fan vertex buffer may have failed but we already pushed back fan programs.
    if (fFanBuffer) {
        for (const GrProgramInfo* fanProgram : fFanPrograms) {
            flushState->bindPipelineAndScissorClip(*fanProgram, this->bounds());
            flushState->bindTextures(fanProgram->geomProc(), nullptr, fanProgram->pipeline());
            flushState->bindBuffers(nullptr, nullptr, fFanBuffer);
            flushState->draw(fFanVertexCount, fBaseFanVertex);
        }
    }

    if (fCoverHullsProgram) {
        SkASSERT(fTessellator);
        flushState->bindPipelineAndScissorClip(*fCoverHullsProgram, this->bounds());
        flushState->bindTextures(fCoverHullsProgram->geomProc(), nullptr, *fPipelineForFills);
        fTessellator->drawHullInstances(flushState, fHullVertexBufferIfNoIDSupport);
    }
}

}  // namespace skgpu::ganesh

#endif // SK_ENABLE_OPTIMIZE_SIZE