/*

 * Copyright 2022 Google LLC

 *

 * Use of this source code is governed by a BSD-style license that can be

 * found in the LICENSE file.

 */

#ifndef skgpu_graphite_ClipStack_DEFINED

#define skgpu_graphite_ClipStack_DEFINED

#include "include/core/SkClipOp.h"

#include "include/private/base/SkTArray.h"

#include "src/base/SkTBlockList.h"

#include "src/gpu/graphite/DrawOrder.h"

#include "src/gpu/graphite/DrawParams.h"

#include "src/gpu/graphite/geom/Shape.h"

#include "src/gpu/graphite/geom/Transform_graphite.h"

class SkShader;

class SkStrokeRec;

namespace skgpu::graphite {

class BoundsManager;

class Device;

class Geometry;

// TODO: Port over many of the unit tests for skgpu/v1/ClipStack defined in GrClipStackTest since

// those tests do a thorough job of enumerating the different element combinations.

class ClipStack {

public:

    // TODO: Some of these states reflect what SkDevice requires. Others are based on what Ganesh

    // could handle analytically. They will likely change as graphite's clips are sorted out

    enum class ClipState : uint8_t {

        kEmpty, kWideOpen, kDeviceRect, kDeviceRRect, kComplex

    };

    // All data describing a geometric modification to the clip

    struct Element {

        Shape     fShape;

        Transform fLocalToDevice; // TODO: reference a cached Transform like DrawList?

        SkClipOp  fOp;

    };

    // 'owningDevice' must outlive the clip stack.

    ClipStack(Device* owningDevice);

    ~ClipStack();

    ClipStack(const ClipStack&) = delete;

    ClipStack& operator=(const ClipStack&) = delete;

    ClipState clipState() const { return this->currentSaveRecord().state(); }

    int maxDeferredClipDraws() const { return fElements.count(); }

    Rect conservativeBounds() const;

    class ElementIter;

    // Provides for-range over active, valid clip elements from most recent to oldest.

    // The iterator provides items as "const Element&".

    inline ElementIter begin() const;

    inline ElementIter end() const;

    // Clip stack manipulation

    void save();

    void restore();

    void clipShape(const Transform& localToDevice, const Shape& shape, SkClipOp op);

    void clipShader(sk_sp<SkShader> shader);

    // Compute the bounds and the effective elements of the clip stack when applied to the draw

    // described by the provided transform, shape, and stroke.

    //

    // Applying clips to a draw is a mostly lazy operation except for what is returned:

    //  - The Clip's scissor is set to 'conservativeBounds()'.

    //  - The Clip stores the draw's clipped bounds, taking into account its transform, styling, and

    //    the above scissor.

    //  - The Clip also stores the draw's fill-style invariant clipped bounds which is used in atlas

    //    draws and may differ from the draw bounds.

    //

    // All clip elements that affect the draw will be returned in `outEffectiveElements` alongside

    // the bounds. This method does not have any side-effects and the per-clip element state has to

    // be explicitly updated by calling `updateClipStateForDraw()` which prepares the clip stack for

    // later rendering.

    //

    // The returned clip element list will be empty if the shape is clipped out or if the draw is

    // unaffected by any of the clip elements.

    using ElementList = skia_private::STArray<4, const Element*>;

    Clip visitClipStackForDraw(const Transform&,

                               const Geometry&,

                               const SkStrokeRec&,

                               bool outsetBoundsForAA,

                               ElementList* outEffectiveElements) const;

    // Update the per-clip element state for later rendering using pre-computed clip state data for

    // a particular draw. The provided 'z' value is the depth value that the draw will use if it's

    // not clipped out entirely.

    //

    // The returned CompressedPaintersOrder is the largest order that will be used by any of the

    // clip elements that affect the draw.

    //

    // If the provided `clipState` indicates that the draw will be clipped out, then this method has

    // no effect and returns DrawOrder::kNoIntersection.

    CompressedPaintersOrder updateClipStateForDraw(const Clip& clip,

                                                   const ElementList& effectiveElements,

                                                   const BoundsManager*,

                                                   PaintersDepth z);

    void recordDeferredClipDraws();

private:

    // SaveRecords and Elements are stored in two parallel stacks. The top-most SaveRecord is the

    // active record, older records represent earlier save points and aren't modified until they

    // become active again. Elements may be owned by the active SaveRecord, in which case they are

    // fully mutable, or they may be owned by a prior SaveRecord. However, Elements from both the

    // active SaveRecord and older records can be valid and affect draw operations. Elements are

    // marked inactive when new elements are determined to supersede their effect completely.

    // Inactive elements of the active SaveRecord can be deleted immediately; inactive elements of

    // older SaveRecords may become active again as the save stack is popped back.

    //

    // See go/grclipstack-2.0 for additional details and visualization of the data structures.

    class SaveRecord;

    // Internally, a lot of clip reasoning is based on an op, outer bounds, and whether a shape

    // contains another (possibly just conservatively based on inner/outer device-space bounds).

    // Element and SaveRecord store this information directly. A draw is equivalent to a clip

    // element with the intersection op. TransformedShape is a lightweight wrapper that can convert

    // these different types into a common type that Simplify() can reason about.

    struct TransformedShape;

    // This captures which of the two elements in (A op B) would be required when they are combined,

    // where op is intersect or difference.

    enum class SimplifyResult {

        kEmpty,

        kAOnly,

        kBOnly,

        kBoth

    };

    static SimplifyResult Simplify(const TransformedShape& a, const TransformedShape& b);

    // Wraps the geometric Element data with logic for containment and bounds testing.

    class RawElement : public Element {

    public:

        using Stack = SkTBlockList<RawElement, 1>;

        RawElement(const Rect& deviceBounds,

                   const Transform& localToDevice,

                   const Shape& shape,

                   SkClipOp op);

        ~RawElement() {

            // A pending draw means the element affects something already recorded, so its own

            // shape needs to be recorded as a draw. Since recording requires the Device (and

            // DrawContext), it must happen before we destroy the element itself.

            SkASSERT(!this->hasPendingDraw());

        }

Unexecuted instantiation: skgpu::graphite::ClipStack::RawElement::~RawElement()

Unexecuted instantiation: skgpu::graphite::ClipStack::RawElement::~RawElement()

        // Silence warnings about implicit copy ctor/assignment because we're declaring a dtor

        RawElement(const RawElement&) = default;

        RawElement& operator=(const RawElement&) = default;

        operator TransformedShape() const;

        bool             hasPendingDraw() const { return fOrder != DrawOrder::kNoIntersection; }

        const Shape&     shape()          const { return fShape;         }

        const Transform& localToDevice()  const { return fLocalToDevice; }

        const Rect&      outerBounds()    const { return fOuterBounds;   }

        const Rect&      innerBounds()    const { return fInnerBounds;   }

        SkClipOp         op()             const { return fOp;            }

        ClipState        clipType()       const;

        // As new elements are pushed on to the stack, they may make older elements redundant.

        // The old elements are marked invalid so they are skipped during clip application, but may

        // become active again when a save record is restored.

        bool isInvalid() const { return fInvalidatedByIndex >= 0; }

        void markInvalid(const SaveRecord& current);

        void restoreValid(const SaveRecord& current);

        // 'added' represents a new op added to the element stack. Its combination with this element

        // can result in a number of possibilities:

        //  1. The entire clip is empty (signaled by both this and 'added' being invalidated).

        //  2. The 'added' op supercedes this element (this element is invalidated).

        //  3. This op supercedes the 'added' element (the added element is marked invalidated).

        //  4. Their combination can be represented by a single new op (in which case this

        //     element should be invalidated, and the combined shape stored in 'added').

        //  5. Or both elements remain needed to describe the clip (both are valid and unchanged).

        //

        // The calling element will only modify its invalidation index since it could belong

        // to part of the inactive stack (that might be restored later). All merged state/geometry

        // is handled by modifying 'added'.

        void updateForElement(RawElement* added, const SaveRecord& current);

        // Returns how this element affects the draw after more detailed analysis.

        enum class DrawInfluence {

            kNone,       // The element does not affect the draw

            kClipOut,    // The element causes the draw shape to be entirely clipped out

            kIntersect,  // The element intersects the draw shape in a complex way

        };

        DrawInfluence testForDraw(const TransformedShape& draw) const;

        // Updates usage tracking to incorporate the bounds and Z value for the new draw call.

        // If this element hasn't affected any prior draws, it will use the bounds manager to

        // assign itself a compressed painters order for later rendering.

        //

        // This method assumes that this element affects the draw in a complex way, such that

        // calling `testForDraw()` on the same draw would return `DrawInfluence::kIntersect`. It is

        // assumed that `testForDraw()` was called beforehand to ensure that this is the case.

        //

        // Assuming that this element does not clip out the draw, returns the painters order the

        // draw must sort after.

        CompressedPaintersOrder updateForDraw(const BoundsManager* boundsManager,

                                              const Rect& drawBounds,

                                              PaintersDepth drawZ);

        // Record a depth-only draw to the given device, restricted to the portion of the clip that

        // is actually required based on prior recorded draws. Resets usage tracking for subsequent

        // passes.

        void drawClip(Device*);

        void validate() const;

    private:

        // TODO: Should only combine elements within the same save record, that don't have pending

        // draws already. Otherwise, we're changing the geometry that will be rasterized and it

        // could lead to gaps even if in a perfect the world the analytically intersected shape was

        // equivalent. Can't combine with other save records, since they *might* become pending

        // later on.

        bool combine(const RawElement& other, const SaveRecord& current);

        // Device space bounds. These bounds are not snapped to pixels with the assumption that if

        // a relation (intersects, contains, etc.) is true for the bounds it will be true for the

        // rasterization of the coordinates that produced those bounds.

        Rect fInnerBounds;

        Rect fOuterBounds;

        // TODO: Convert fOuterBounds to a ComplementRect to make intersection tests faster?

        // Would need to store both original and complement, since the intersection test is

        // Rect + ComplementRect and Element/SaveRecord could be on either side of operation.

        // State tracking how this clip element needs to be recorded into the draw context. As the

        // clip stack is applied to additional draws, the clip's Z and usage bounds grow to account

        // for it; its compressed painter's order is selected the first time a draw is affected.

        Rect fUsageBounds;

        CompressedPaintersOrder fOrder;

        PaintersDepth fMaxZ;

        // Elements are invalidated by SaveRecords as the record is updated with new elements that

        // override old geometry. An invalidated element stores the index of the first element of

        // the save record that invalidated it. This makes it easy to undo when the save record is

        // popped from the stack, and is stable as the current save record is modified.

        int fInvalidatedByIndex;

    };

    // Represents a saved point in the clip stack, and manages the life time of elements added to

    // stack within the record's life time. Also provides the logic for determining active elements

    // given a draw query.

    class SaveRecord {

    public:

        using Stack = SkTBlockList<SaveRecord, 2>;

        explicit SaveRecord(const Rect& deviceBounds);

        SaveRecord(const SaveRecord& prior, int startingElementIndex);

        const SkShader* shader()      const { return fShader.get(); }

        const Rect&     outerBounds() const { return fOuterBounds;  }

        const Rect&     innerBounds() const { return fInnerBounds;  }

        SkClipOp        op()          const { return fStackOp;      }

        ClipState       state()       const;

        int  firstActiveElementIndex() const { return fStartingElementIndex;     }

        int  oldestElementIndex()      const { return fOldestValidIndex;         }

        bool canBeUpdated()            const { return (fDeferredSaveCount == 0); }

        Rect scissor(const Rect& deviceBounds, const Rect& drawBounds) const;

        // Deferred save manipulation

        void pushSave() {

            SkASSERT(fDeferredSaveCount >= 0);

            fDeferredSaveCount++;

        }

Unexecuted instantiation: skgpu::graphite::ClipStack::SaveRecord::pushSave()

Unexecuted instantiation: skgpu::graphite::ClipStack::SaveRecord::pushSave()

        // Returns true if the record should stay alive. False means the ClipStack must delete it

        bool popSave() {

            fDeferredSaveCount--;

            SkASSERT(fDeferredSaveCount >= -1);

            return fDeferredSaveCount >= 0;

        }

Unexecuted instantiation: skgpu::graphite::ClipStack::SaveRecord::popSave()

Unexecuted instantiation: skgpu::graphite::ClipStack::SaveRecord::popSave()

        // Return true if the element was added to 'elements', or otherwise affected the save record

        // (e.g. turned it empty).

        bool addElement(RawElement&& toAdd, RawElement::Stack* elements, Device*);

        void addShader(sk_sp<SkShader> shader);

        // Remove the elements owned by this save record, which must happen before the save record

        // itself is removed from the clip stack. Records draws for any removed elements that have

        // draw usages.

        void removeElements(RawElement::Stack* elements, Device*);

        // Restore element validity now that this record is the new top of the stack.

        void restoreElements(RawElement::Stack* elements);

    private:

        // These functions modify 'elements' and element-dependent state of the record

        // (such as valid index and fState). Records draws for any clips that have deferred usages

        // that are inactivated and cannot be restored (i.e. part of the active save record).

        bool appendElement(RawElement&& toAdd, RawElement::Stack* elements, Device*);

        void replaceWithElement(RawElement&& toAdd, RawElement::Stack* elements, Device*);

        // Inner bounds is always contained in outer bounds, or it is empty. All bounds will be

        // contained in the device bounds.

        Rect fInnerBounds; // Inside is full coverage (stack op == intersect) or 0 cov (diff)

        Rect fOuterBounds; // Outside is 0 coverage (op == intersect) or full cov (diff)

        // A save record can have up to one shader, multiple shaders are automatically blended

        sk_sp<SkShader> fShader;

        const int fStartingElementIndex; // First element owned by this save record

        int       fOldestValidIndex;     // Index of oldest element that's valid for this record

        int       fDeferredSaveCount;    // Number of save() calls without modifications (yet)

        // Will be kIntersect unless every valid element is kDifference, which is significant

        // because if kDifference then there is an implicit extra outer bounds at the device edges.

        SkClipOp  fStackOp;

        ClipState fState;

    };

    Rect deviceBounds() const;

    const SaveRecord& currentSaveRecord() const {

        SkASSERT(!fSaves.empty());

        return fSaves.back();

    }

Unexecuted instantiation: skgpu::graphite::ClipStack::currentSaveRecord() const

Unexecuted instantiation: skgpu::graphite::ClipStack::currentSaveRecord() const

    // Will return the current save record, properly updating deferred saves

    // and initializing a first record if it were empty.

    SaveRecord& writableSaveRecord(bool* wasDeferred);

    RawElement::Stack fElements;

    SaveRecord::Stack fSaves; // always has one wide open record at the top

    Device* fDevice; // the device this clip stack is coupled with

};

// Clip element iteration

class ClipStack::ElementIter {

public:

    bool operator!=(const ElementIter& o) const {

        return o.fItem != fItem && o.fRemaining != fRemaining;

    }

    const Element& operator*() const { return *fItem; }

    ElementIter& operator++() {

        // Skip over invalidated elements

        do {

            fRemaining--;

            ++fItem;

        } while(fRemaining > 0 && (*fItem).isInvalid());

        return *this;

    }

    ElementIter(RawElement::Stack::CRIter::Item item, int r) : fItem(item), fRemaining(r) {}

    RawElement::Stack::CRIter::Item fItem;

    int fRemaining;

    friend class ClipStack;

};

ClipStack::ElementIter ClipStack::begin() const {

    if (this->currentSaveRecord().state() == ClipState::kEmpty ||

        this->currentSaveRecord().state() == ClipState::kWideOpen) {

        // No visible clip elements when empty or wide open

        return this->end();

    }

    int count = fElements.count() - this->currentSaveRecord().oldestElementIndex();

    return ElementIter(fElements.ritems().begin(), count);

}

ClipStack::ElementIter ClipStack::end() const {

    return ElementIter(fElements.ritems().end(), 0);

}

} // namespace skgpu::graphite

#endif // skgpu_graphite_ClipStack_DEFINED