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

#include "GrPictureUtils.h"

#include "SkBBoxHierarchy.h"
#include "SkPaintPriv.h"
#include "SkPatchUtils.h"
#include "SkRecord.h"
#include "SkRecords.h"

SkPicture::AccelData::Key GrAccelData::ComputeAccelDataKey() {
    static const SkPicture::AccelData::Key gGPUID = SkPicture::AccelData::GenerateDomain();

    return gGPUID;
}

// This looks silly, I know.  Why not just use SkRect::MakeLargest()?
// In practice, this is well large enough, and it has a few extra advantages:
// it fits in an SkIRect, and we can munge it a little in both SkRect and
// SKIRect space without worrying about overflow.
static const SkRect kUnbounded = { -2e9f, -2e9f, 2e9f, 2e9f };

namespace SkRecords {

// SkRecord visitor to gather saveLayer/restore information.
class CollectLayers : SkNoncopyable {
public:
    CollectLayers(const SkRect& cullRect, const SkRecord& record,
                  SkBBoxHierarchy* bbh, GrAccelData* accelData)
        : fSaveLayersInStack(0)
        , fAccelData(accelData) {

        // Calculate bounds for all ops.  This won't go quite in order, so we'll need
        // to store the bounds separately then feed them in to the BBH later in order.
        fCTM = &SkMatrix::I();
        fCurrentClipBounds = kUnbounded;

        fBounds.reset(record.count());

        for (fCurrentOp = 0; fCurrentOp < record.count(); ++fCurrentOp) {
            record.visit<void>(fCurrentOp, *this);
        }

        // If we have any lingering unpaired Saves, simulate restores to make
        // sure all ops in those Save blocks have their bounds calculated.
        while (!fSaveStack.isEmpty()) {
            this->popSaveBlock();
        }

        // Any control ops not part of any Save/Restore block draw everywhere.
        while (!fControlIndices.isEmpty()) {
            this->popControl(kUnbounded);
        }

        //--------- LAYER HOISTING
        while (!fSaveLayerStack.isEmpty()) {
            this->popSaveLayerInfo();
        }
        //--------- LAYER HOISTING

        // Finally feed all stored bounds into the BBH.  They'll be returned in this order.
        SkASSERT(bbh);
        bbh->insert(&fBounds, record.count());
    }

    template <typename T> void operator()(const T& op) {
        this->updateCTM(op);
        this->updateClipBounds(op);
        this->trackBounds(op);
        //--------- LAYER HOISTING
        this->trackSaveLayers(op);
        //--------- LAYER HOISTING
    }

private:
    // In this file, SkRect are in local coordinates, Bounds are translated back to identity space.
    typedef SkRect Bounds;

    struct SaveBounds {
        int controlOps;        // Number of control ops in this Save block, including the Save.
        Bounds bounds;         // Bounds of everything in the block.
        const SkPaint* paint;  // Unowned.  If set, adjusts the bounds of all ops in this block.
    };

    //--------- LAYER HOISTING
    class SaveLayerInfo {
    public:
        SaveLayerInfo() { }
        SaveLayerInfo(int opIndex, bool isSaveLayer, const SkPaint* paint, const Bounds& clipBound)
            : fStartIndex(opIndex)
            , fIsSaveLayer(isSaveLayer)
            , fHasNestedSaveLayer(false)
            , fPaint(paint)
            , fClipBound(clipBound) {
        }

        int            fStartIndex;
        bool           fIsSaveLayer;
        bool           fHasNestedSaveLayer;
        const SkPaint* fPaint;
        Bounds         fClipBound;
    };
    //--------- LAYER HOISTING

    // Only Restore and SetMatrix change the CTM.
    template <typename T> void updateCTM(const T&) {}
    void updateCTM(const Restore& op)   { fCTM = &op.matrix; }
    void updateCTM(const SetMatrix& op) { fCTM = &op.matrix; }

    // Most ops don't change the clip.
    template <typename T> void updateClipBounds(const T&) {}

    // Clip{Path,RRect,Rect,Region} obviously change the clip.  They all know their bounds already.
    void updateClipBounds(const ClipPath& op)   { this->updateClipBoundsForClipOp(op.devBounds); }
    void updateClipBounds(const ClipRRect& op)  { this->updateClipBoundsForClipOp(op.devBounds); }
    void updateClipBounds(const ClipRect& op)   { this->updateClipBoundsForClipOp(op.devBounds); }
    void updateClipBounds(const ClipRegion& op) { this->updateClipBoundsForClipOp(op.devBounds); }

    // The bounds of clip ops need to be adjusted for the paints of saveLayers they're inside.
    void updateClipBoundsForClipOp(const SkIRect& devBounds) {
        Bounds clip = SkRect::Make(devBounds);
        // We don't call adjustAndMap() because as its last step it would intersect the adjusted
        // clip bounds with the previous clip, exactly what we can't do when the clip grows.
        fCurrentClipBounds = this->adjustForSaveLayerPaints(&clip) ? clip : kUnbounded;
    }

    // Restore holds the devBounds for the clip after the {save,saveLayer}/restore block completes.
    void updateClipBounds(const Restore& op) {
        // This is just like the clip ops above, but we need to skip the effects (if any) of our
        // paired saveLayer (if it is one); it has not yet been popped off the save stack.  Our
        // devBounds reflect the state of the world after the saveLayer/restore block is done,
        // so they are not affected by the saveLayer's paint.
        const int kSavesToIgnore = 1;
        Bounds clip = SkRect::Make(op.devBounds);
        fCurrentClipBounds =
            this->adjustForSaveLayerPaints(&clip, kSavesToIgnore) ? clip : kUnbounded;
    }

    // We also take advantage of SaveLayer bounds when present to further cut the clip down.
    void updateClipBounds(const SaveLayer& op)  {
        if (op.bounds) {
            // adjustAndMap() intersects these layer bounds with the previous clip for us.
            fCurrentClipBounds = this->adjustAndMap(*op.bounds, op.paint);
        }
    }

    // The bounds of these ops must be calculated when we hit the Restore
    // from the bounds of the ops in the same Save block.
    void trackBounds(const Save&)          { this->pushSaveBlock(NULL); }
    void trackBounds(const SaveLayer& op)  { this->pushSaveBlock(op.paint); }
    void trackBounds(const Restore&) { fBounds[fCurrentOp] = this->popSaveBlock(); }

    void trackBounds(const SetMatrix&)         { this->pushControl(); }
    void trackBounds(const ClipRect&)          { this->pushControl(); }
    void trackBounds(const ClipRRect&)         { this->pushControl(); }
    void trackBounds(const ClipPath&)          { this->pushControl(); }
    void trackBounds(const ClipRegion&)        { this->pushControl(); }
    void trackBounds(const PushCull&)          { this->pushControl(); }
    void trackBounds(const PopCull&)           { this->pushControl(); }
    void trackBounds(const BeginCommentGroup&) { this->pushControl(); }
    void trackBounds(const AddComment&)        { this->pushControl(); }
    void trackBounds(const EndCommentGroup&)   { this->pushControl(); }
    void trackBounds(const DrawData&)          { this->pushControl(); }

    // For all other ops, we can calculate and store the bounds directly now.
    template <typename T> void trackBounds(const T& op) {
        fBounds[fCurrentOp] = this->bounds(op);
        this->updateSaveBounds(fBounds[fCurrentOp]);
    }

    void pushSaveBlock(const SkPaint* paint) {
        // Starting a new Save block.  Push a new entry to represent that.
        SaveBounds sb = { 0, Bounds::MakeEmpty(), paint };
        fSaveStack.push(sb);
        this->pushControl();
    }

    static bool PaintMayAffectTransparentBlack(const SkPaint* paint) {
        if (paint) {
            // FIXME: this is very conservative
            if (paint->getImageFilter() || paint->getColorFilter()) {
                return true;
            }

            // Unusual Xfermodes require us to process a saved layer
            // even with operations outisde the clip.
            // For example, DstIn is used by masking layers.
            // https://code.google.com/p/skia/issues/detail?id=1291
            // https://crbug.com/401593
            SkXfermode* xfermode = paint->getXfermode();
            SkXfermode::Mode mode;
            // SrcOver is ok, and is also the common case with a NULL xfermode.
            // So we should make that the fast path and bypass the mode extraction
            // and test.
            if (xfermode && xfermode->asMode(&mode)) {
                switch (mode) {
                    // For each of the following transfer modes, if the source
                    // alpha is zero (our transparent black), the resulting
                    // blended alpha is not necessarily equal to the original
                    // destination alpha.
                    case SkXfermode::kClear_Mode:
                    case SkXfermode::kSrc_Mode:
                    case SkXfermode::kSrcIn_Mode:
                    case SkXfermode::kDstIn_Mode:
                    case SkXfermode::kSrcOut_Mode:
                    case SkXfermode::kDstATop_Mode:
                    case SkXfermode::kModulate_Mode:
                        return true;
                        break;
                    default:
                        break;
                }
            }
        }
        return false;
    }

    Bounds popSaveBlock() {
        // We're done the Save block.  Apply the block's bounds to all control ops inside it.
        SaveBounds sb;
        fSaveStack.pop(&sb);

        // If the paint affects transparent black, we can't trust any of our calculated bounds.
        const Bounds& bounds =
            PaintMayAffectTransparentBlack(sb.paint) ? fCurrentClipBounds : sb.bounds;

        while (sb.controlOps-- > 0) {
            this->popControl(bounds);
        }

        // This whole Save block may be part another Save block.
        this->updateSaveBounds(bounds);

        // If called from a real Restore (not a phony one for balance), it'll need the bounds.
        return bounds;
    }

    void pushControl() {
        fControlIndices.push(fCurrentOp);
        if (!fSaveStack.isEmpty()) {
            fSaveStack.top().controlOps++;
        }
    }

    void popControl(const Bounds& bounds) {
        fBounds[fControlIndices.top()] = bounds;
        fControlIndices.pop();
    }

    void updateSaveBounds(const Bounds& bounds) {
        // If we're in a Save block, expand its bounds to cover these bounds too.
        if (!fSaveStack.isEmpty()) {
            fSaveStack.top().bounds.join(bounds);
        }
    }

    // FIXME: this method could use better bounds
    Bounds bounds(const DrawText&) const { return fCurrentClipBounds; }

    Bounds bounds(const Clear&) const { return kUnbounded; }             // Ignores the clip.
    Bounds bounds(const DrawPaint&) const { return fCurrentClipBounds; }
    Bounds bounds(const NoOp&)  const { return Bounds::MakeEmpty(); }    // NoOps don't draw.

    Bounds bounds(const DrawSprite& op) const {
        const SkBitmap& bm = op.bitmap;

        return Bounds::Make(SkIRect::MakeXYWH(op.left, op.top, bm.width(), bm.height()));  // Ignores the matrix.
    }

    Bounds bounds(const DrawRect& op) const { return this->adjustAndMap(op.rect, &op.paint); }
    Bounds bounds(const DrawOval& op) const { return this->adjustAndMap(op.oval, &op.paint); }
    Bounds bounds(const DrawRRect& op) const {
        return this->adjustAndMap(op.rrect.rect(), &op.paint);
    }
    Bounds bounds(const DrawDRRect& op) const {
        return this->adjustAndMap(op.outer.rect(), &op.paint);
    }
    Bounds bounds(const DrawImage& op) const {
        const SkImage* image = op.image;
        SkRect rect = SkRect::MakeXYWH(op.left, op.top,
                                        SkIntToScalar(image->width()), SkIntToScalar(image->height()));

        return this->adjustAndMap(rect, op.paint);
    }
    Bounds bounds(const DrawImageRect& op) const {
        return this->adjustAndMap(op.dst, op.paint);
    }
    Bounds bounds(const DrawBitmapRectToRect& op) const {
        return this->adjustAndMap(op.dst, op.paint);
    }
    Bounds bounds(const DrawBitmapNine& op) const {
        return this->adjustAndMap(op.dst, op.paint);
    }
    Bounds bounds(const DrawBitmap& op) const {
        const SkBitmap& bm = op.bitmap;
        return this->adjustAndMap(SkRect::MakeXYWH(op.left, op.top, SkIntToScalar(bm.width()), SkIntToScalar(bm.height())),
                                    op.paint);
    }
    Bounds bounds(const DrawBitmapMatrix& op) const {
        const SkBitmap& bm = op.bitmap;
        SkRect dst = SkRect::Make(SkIRect::MakeWH(bm.width(), bm.height()));
        op.matrix.mapRect(&dst);
        return this->adjustAndMap(dst, op.paint);
    }

    Bounds bounds(const DrawPath& op) const {
        return op.path.isInverseFillType() ? fCurrentClipBounds
            : this->adjustAndMap(op.path.getBounds(), &op.paint);
    }
    Bounds bounds(const DrawPoints& op) const {
        SkRect dst;
        dst.set(op.pts, op.count);

        // Pad the bounding box a little to make sure hairline points' bounds aren't empty.
        SkScalar stroke = SkMaxScalar(op.paint.getStrokeWidth(), 0.01f);
        dst.outset(stroke / 2, stroke / 2);

        return this->adjustAndMap(dst, &op.paint);
    }
    Bounds bounds(const DrawPatch& op) const {
        SkRect dst;
        dst.set(op.cubics, SkPatchUtils::kNumCtrlPts);
        return this->adjustAndMap(dst, &op.paint);
    }
    Bounds bounds(const DrawVertices& op) const {
        SkRect dst;
        dst.set(op.vertices, op.vertexCount);
        return this->adjustAndMap(dst, &op.paint);
    }

    Bounds bounds(const DrawPicture& op) const {
        SkRect dst = op.picture->cullRect();
        if (op.matrix) {
            op.matrix->mapRect(&dst);
        }
        return this->adjustAndMap(dst, op.paint);
    }

    Bounds bounds(const DrawPosText& op) const {
        const int N = op.paint.countText(op.text, op.byteLength);
        if (N == 0) {
            return Bounds::MakeEmpty();
        }

        SkRect dst;
        dst.set(op.pos, N);
        AdjustTextForFontMetrics(&dst, op.paint);
        return this->adjustAndMap(dst, &op.paint);
    }
    Bounds bounds(const DrawPosTextH& op) const {
        const int N = op.paint.countText(op.text, op.byteLength);
        if (N == 0) {
            return Bounds::MakeEmpty();
        }

        SkScalar left = op.xpos[0], right = op.xpos[0];
        for (int i = 1; i < N; i++) {
            left = SkMinScalar(left, op.xpos[i]);
            right = SkMaxScalar(right, op.xpos[i]);
        }
        SkRect dst = { left, op.y, right, op.y };
        AdjustTextForFontMetrics(&dst, op.paint);
        return this->adjustAndMap(dst, &op.paint);
    }
    Bounds bounds(const DrawTextOnPath& op) const {
        SkRect dst = op.path.getBounds();

        // Pad all sides by the maximum padding in any direction we'd normally apply.
        SkRect pad = { 0, 0, 0, 0 };
        AdjustTextForFontMetrics(&pad, op.paint);

        // That maximum padding happens to always be the right pad today.
        SkASSERT(pad.fLeft == -pad.fRight);
        SkASSERT(pad.fTop == -pad.fBottom);
        SkASSERT(pad.fRight > pad.fBottom);
        dst.outset(pad.fRight, pad.fRight);

        return this->adjustAndMap(dst, &op.paint);
    }

    Bounds bounds(const DrawTextBlob& op) const {
        SkRect dst = op.blob->bounds();
        dst.offset(op.x, op.y);
        return this->adjustAndMap(dst, &op.paint);
    }

    static void AdjustTextForFontMetrics(SkRect* rect, const SkPaint& paint) {
#ifdef SK_DEBUG
        SkRect correct = *rect;
#endif
        // crbug.com/373785 ~~> xPad = 4x yPad
        // crbug.com/424824 ~~> bump yPad from 2x text size to 2.5x
        const SkScalar yPad = 2.5f * paint.getTextSize(),
            xPad = 4.0f * yPad;
        rect->outset(xPad, yPad);
#ifdef SK_DEBUG
        SkPaint::FontMetrics metrics;
        paint.getFontMetrics(&metrics);
        correct.fLeft += metrics.fXMin;
        correct.fTop += metrics.fTop;
        correct.fRight += metrics.fXMax;
        correct.fBottom += metrics.fBottom;
        // See skia:2862 for why we ignore small text sizes.
        SkASSERTF(paint.getTextSize() < 0.001f || rect->contains(correct),
                    "%f %f %f %f vs. %f %f %f %f\n",
                    -xPad, -yPad, +xPad, +yPad,
                    metrics.fXMin, metrics.fTop, metrics.fXMax, metrics.fBottom);
#endif
    }

    //--------- LAYER HOISTING
    template <typename T> void trackSaveLayers(const T& op) {
        /* most ops aren't involved in saveLayers */
    }
    void trackSaveLayers(const Save& s) { this->pushSaveLayerInfo(false, NULL); }
    void trackSaveLayers(const SaveLayer& sl) {
        this->pushSaveLayerInfo(true, sl.paint);
    }
    void trackSaveLayers(const Restore& r) { this->popSaveLayerInfo(); }
    void trackSaveLayers(const DrawPicture& dp) {
        // For sub-pictures, we wrap their layer information within the parent
        // picture's rendering hierarchy
        SkPicture::AccelData::Key key = GrAccelData::ComputeAccelDataKey();

        const GrAccelData* childData = 
            static_cast<const GrAccelData*>(dp.picture->EXPERIMENTAL_getAccelData(key));
        if (!childData) {
            // If the child layer hasn't been generated with saveLayer data we
            // assume the worst (i.e., that it does contain layers which nest
            // inside existing layers). Layers within sub-pictures that don't
            // have saveLayer data cannot be hoisted.
            // TODO: could the analysis data be use to fine tune this?
            this->updateStackForSaveLayer();
            return;
        }

        for (int i = 0; i < childData->numSaveLayers(); ++i) {
            const GrAccelData::SaveLayerInfo& src = childData->saveLayerInfo(i);

            Bounds newClip(fCurrentClipBounds);

            if (!newClip.intersect(this->adjustAndMap(src.fBounds, dp.paint))) {
                continue;
            }

            this->updateStackForSaveLayer();

            GrAccelData::SaveLayerInfo& dst = fAccelData->addSaveLayerInfo();

            // If src.fPicture is NULL the layer is in dp.picture; otherwise
            // it belongs to a sub-picture.
            dst.fPicture = src.fPicture ? src.fPicture : static_cast<const SkPicture*>(dp.picture);
            dst.fPicture->ref();
            dst.fBounds = newClip;
            dst.fLocalMat = src.fLocalMat;
            dst.fPreMat = src.fPreMat;
            dst.fPreMat.postConcat(*fCTM);
            if (src.fPaint) {
                dst.fPaint = SkNEW_ARGS(SkPaint, (*src.fPaint));
            }
            dst.fSaveLayerOpID = src.fSaveLayerOpID;
            dst.fRestoreOpID = src.fRestoreOpID;
            dst.fHasNestedLayers = src.fHasNestedLayers;
            dst.fIsNested = fSaveLayersInStack > 0 || src.fIsNested;
        }
    }

    // Inform all the saveLayers already on the stack that they now have a
    // nested saveLayer inside them
    void updateStackForSaveLayer() {
        for (int index = fSaveLayerStack.count() - 1; index >= 0; --index) {
            if (fSaveLayerStack[index].fHasNestedSaveLayer) {
                break;
            }
            fSaveLayerStack[index].fHasNestedSaveLayer = true;
            if (fSaveLayerStack[index].fIsSaveLayer) {
                break;
            }
        }
    }

    void pushSaveLayerInfo(bool isSaveLayer, const SkPaint* paint) {
        if (isSaveLayer) {
            this->updateStackForSaveLayer();
            ++fSaveLayersInStack;
        }

        fSaveLayerStack.push(SaveLayerInfo(fCurrentOp, isSaveLayer, paint, fCurrentClipBounds));
    }

    void popSaveLayerInfo() {
        if (fSaveLayerStack.count() <= 0) {
            SkASSERT(false);
            return;
        }

        SaveLayerInfo sli;
        fSaveLayerStack.pop(&sli);

        if (!sli.fIsSaveLayer) {
            return;
        }

        --fSaveLayersInStack;

        GrAccelData::SaveLayerInfo& slInfo = fAccelData->addSaveLayerInfo();

        SkASSERT(NULL == slInfo.fPicture);  // This layer is in the top-most picture

        slInfo.fBounds = fBounds[sli.fStartIndex];
        slInfo.fBounds.intersect(sli.fClipBound);
        slInfo.fLocalMat = *fCTM;
        slInfo.fPreMat = SkMatrix::I();
        if (sli.fPaint) {
            slInfo.fPaint = SkNEW_ARGS(SkPaint, (*sli.fPaint));
        }
        slInfo.fSaveLayerOpID = sli.fStartIndex;
        slInfo.fRestoreOpID = fCurrentOp;
        slInfo.fHasNestedLayers = sli.fHasNestedSaveLayer;
        slInfo.fIsNested = fSaveLayersInStack > 0;
    }
    //--------- LAYER HOISTING

    // Returns true if rect was meaningfully adjusted for the effects of paint,
    // false if the paint could affect the rect in unknown ways.
    static bool AdjustForPaint(const SkPaint* paint, SkRect* rect) {
        if (paint) {
            if (paint->canComputeFastBounds()) {
                *rect = paint->computeFastBounds(*rect, rect);
                return true;
            }
            return false;
        }
        return true;
    }

    bool adjustForSaveLayerPaints(SkRect* rect, int savesToIgnore = 0) const {
        for (int i = fSaveStack.count() - 1 - savesToIgnore; i >= 0; i--) {
            if (!AdjustForPaint(fSaveStack[i].paint, rect)) {
                return false;
            }
        }
        return true;
    }

    // Adjust rect for all paints that may affect its geometry, then map it to identity space.
    Bounds adjustAndMap(SkRect rect, const SkPaint* paint) const {
        // Inverted rectangles really confuse our BBHs.
        rect.sort();

        // Adjust the rect for its own paint.
        if (!AdjustForPaint(paint, &rect)) {
            // The paint could do anything to our bounds.  The only safe answer is the current clip.
            return fCurrentClipBounds;
        }

        // Adjust rect for all the paints from the SaveLayers we're inside.
        if (!this->adjustForSaveLayerPaints(&rect)) {
            // Same deal as above.
            return fCurrentClipBounds;
        }

        // Map the rect back to identity space.
        fCTM->mapRect(&rect);

        // Nothing can draw outside the current clip.
        // (Only bounded ops call into this method, so oddballs like Clear don't matter here.)
        rect.intersect(fCurrentClipBounds);
        return rect;
    }

    // Conservative identity-space bounds for each op in the SkRecord.
    SkAutoTMalloc<Bounds> fBounds;

    // We walk fCurrentOp through the SkRecord, as we go using updateCTM()
    // and updateClipBounds() to maintain the exact CTM (fCTM) and conservative
    // identity-space bounds of the current clip (fCurrentClipBounds).
    unsigned fCurrentOp;
    const SkMatrix* fCTM;
    Bounds fCurrentClipBounds;

    // Used to track the bounds of Save/Restore blocks and the control ops inside them.
    SkTDArray<SaveBounds> fSaveStack;
    SkTDArray<unsigned>   fControlIndices;

    //--------- LAYER HOISTING
    // Used to collect saveLayer information for layer hoisting
    int                   fSaveLayersInStack;
    SkTDArray<SaveLayerInfo> fSaveLayerStack;
    GrAccelData*          fAccelData;
    //--------- LAYER HOISTING
};

} // namespace SkRecords

void SkRecordComputeLayers(const SkRect& cullRect, const SkRecord& record,
                           SkBBoxHierarchy* bbh, GrAccelData* data) {
    SkRecords::CollectLayers collector(cullRect, record, bbh, data);
}