libs/hwui/OpReorderer.cpp

/*
 * Copyright (C) 2015 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "OpReorderer.h"

#include "LayerUpdateQueue.h"
#include "RenderNode.h"
#include "utils/FatVector.h"
#include "utils/PaintUtils.h"

#include <SkCanvas.h>
#include <utils/Trace.h>
#include <utils/TypeHelpers.h>

namespace android {
namespace uirenderer {

class BatchBase {

public:
    BatchBase(batchid_t batchId, BakedOpState* op, bool merging)
        : mBatchId(batchId)
        , mMerging(merging) {
        mBounds = op->computedState.clippedBounds;
        mOps.push_back(op);
    }

    bool intersects(const Rect& rect) const {
        if (!rect.intersects(mBounds)) return false;

        for (const BakedOpState* op : mOps) {
            if (rect.intersects(op->computedState.clippedBounds)) {
                return true;
            }
        }
        return false;
    }

    batchid_t getBatchId() const { return mBatchId; }
    bool isMerging() const { return mMerging; }

    const std::vector<BakedOpState*>& getOps() const { return mOps; }

    void dump() const {
        ALOGD("    Batch %p, id %d, merging %d, count %d, bounds " RECT_STRING,
                this, mBatchId, mMerging, mOps.size(), RECT_ARGS(mBounds));
    }
protected:
    batchid_t mBatchId;
    Rect mBounds;
    std::vector<BakedOpState*> mOps;
    bool mMerging;
};

class OpBatch : public BatchBase {
public:
    static void* operator new(size_t size, LinearAllocator& allocator) {
        return allocator.alloc(size);
    }

    OpBatch(batchid_t batchId, BakedOpState* op)
            : BatchBase(batchId, op, false) {
    }

    void batchOp(BakedOpState* op) {
        mBounds.unionWith(op->computedState.clippedBounds);
        mOps.push_back(op);
    }
};

class MergingOpBatch : public BatchBase {
public:
    static void* operator new(size_t size, LinearAllocator& allocator) {
        return allocator.alloc(size);
    }

    MergingOpBatch(batchid_t batchId, BakedOpState* op)
            : BatchBase(batchId, op, true) {
    }

    /*
     * Helper for determining if a new op can merge with a MergingDrawBatch based on their bounds
     * and clip side flags. Positive bounds delta means new bounds fit in old.
     */
    static inline bool checkSide(const int currentFlags, const int newFlags, const int side,
            float boundsDelta) {
        bool currentClipExists = currentFlags & side;
        bool newClipExists = newFlags & side;

        // if current is clipped, we must be able to fit new bounds in current
        if (boundsDelta > 0 && currentClipExists) return false;

        // if new is clipped, we must be able to fit current bounds in new
        if (boundsDelta < 0 && newClipExists) return false;

        return true;
    }

    static bool paintIsDefault(const SkPaint& paint) {
        return paint.getAlpha() == 255
                && paint.getColorFilter() == nullptr
                && paint.getShader() == nullptr;
    }

    static bool paintsAreEquivalent(const SkPaint& a, const SkPaint& b) {
        return a.getAlpha() == b.getAlpha()
                && a.getColorFilter() == b.getColorFilter()
                && a.getShader() == b.getShader();
    }

    /*
     * Checks if a (mergeable) op can be merged into this batch
     *
     * If true, the op's multiDraw must be guaranteed to handle both ops simultaneously, so it is
     * important to consider all paint attributes used in the draw calls in deciding both a) if an
     * op tries to merge at all, and b) if the op can merge with another set of ops
     *
     * False positives can lead to information from the paints of subsequent merged operations being
     * dropped, so we make simplifying qualifications on the ops that can merge, per op type.
     */
    bool canMergeWith(BakedOpState* op) const {
        bool isTextBatch = getBatchId() == OpBatchType::Text
                || getBatchId() == OpBatchType::ColorText;

        // Overlapping other operations is only allowed for text without shadow. For other ops,
        // multiDraw isn't guaranteed to overdraw correctly
        if (!isTextBatch || PaintUtils::hasTextShadow(op->op->paint)) {
            if (intersects(op->computedState.clippedBounds)) return false;
        }

        const BakedOpState* lhs = op;
        const BakedOpState* rhs = mOps[0];

        if (!MathUtils::areEqual(lhs->alpha, rhs->alpha)) return false;

        // Identical round rect clip state means both ops will clip in the same way, or not at all.
        // As the state objects are const, we can compare their pointers to determine mergeability
        if (lhs->roundRectClipState != rhs->roundRectClipState) return false;
        if (lhs->projectionPathMask != rhs->projectionPathMask) return false;

        /* Clipping compatibility check
         *
         * Exploits the fact that if a op or batch is clipped on a side, its bounds will equal its
         * clip for that side.
         */
        const int currentFlags = mClipSideFlags;
        const int newFlags = op->computedState.clipSideFlags;
        if (currentFlags != OpClipSideFlags::None || newFlags != OpClipSideFlags::None) {
            const Rect& opBounds = op->computedState.clippedBounds;
            float boundsDelta = mBounds.left - opBounds.left;
            if (!checkSide(currentFlags, newFlags, OpClipSideFlags::Left, boundsDelta)) return false;
            boundsDelta = mBounds.top - opBounds.top;
            if (!checkSide(currentFlags, newFlags, OpClipSideFlags::Top, boundsDelta)) return false;

            // right and bottom delta calculation reversed to account for direction
            boundsDelta = opBounds.right - mBounds.right;
            if (!checkSide(currentFlags, newFlags, OpClipSideFlags::Right, boundsDelta)) return false;
            boundsDelta = opBounds.bottom - mBounds.bottom;
            if (!checkSide(currentFlags, newFlags, OpClipSideFlags::Bottom, boundsDelta)) return false;
        }

        const SkPaint* newPaint = op->op->paint;
        const SkPaint* oldPaint = mOps[0]->op->paint;

        if (newPaint == oldPaint) {
            // if paints are equal, then modifiers + paint attribs don't need to be compared
            return true;
        } else if (newPaint && !oldPaint) {
            return paintIsDefault(*newPaint);
        } else if (!newPaint && oldPaint) {
            return paintIsDefault(*oldPaint);
        }
        return paintsAreEquivalent(*newPaint, *oldPaint);
    }

    void mergeOp(BakedOpState* op) {
        mBounds.unionWith(op->computedState.clippedBounds);
        mOps.push_back(op);

        const int newClipSideFlags = op->computedState.clipSideFlags;
        mClipSideFlags |= newClipSideFlags;

        const Rect& opClip = op->computedState.clipRect;
        if (newClipSideFlags & OpClipSideFlags::Left) mClipRect.left = opClip.left;
        if (newClipSideFlags & OpClipSideFlags::Top) mClipRect.top = opClip.top;
        if (newClipSideFlags & OpClipSideFlags::Right) mClipRect.right = opClip.right;
        if (newClipSideFlags & OpClipSideFlags::Bottom) mClipRect.bottom = opClip.bottom;
    }

private:
    int mClipSideFlags = 0;
    Rect mClipRect;
};

OpReorderer::LayerReorderer::LayerReorderer(uint32_t width, uint32_t height,
        const BeginLayerOp* beginLayerOp, RenderNode* renderNode)
        : width(width)
        , height(height)
        , offscreenBuffer(renderNode ? renderNode->getLayer() : nullptr)
        , beginLayerOp(beginLayerOp)
        , renderNode(renderNode) {}

// iterate back toward target to see if anything drawn since should overlap the new op
// if no target, merging ops still iterate to find similar batch to insert after
void OpReorderer::LayerReorderer::locateInsertIndex(int batchId, const Rect& clippedBounds,
        BatchBase** targetBatch, size_t* insertBatchIndex) const {
    for (int i = mBatches.size() - 1; i >= 0; i--) {
        BatchBase* overBatch = mBatches[i];

        if (overBatch == *targetBatch) break;

        // TODO: also consider shader shared between batch types
        if (batchId == overBatch->getBatchId()) {
            *insertBatchIndex = i + 1;
            if (!*targetBatch) break; // found insert position, quit
        }

        if (overBatch->intersects(clippedBounds)) {
            // NOTE: it may be possible to optimize for special cases where two operations
            // of the same batch/paint could swap order, such as with a non-mergeable
            // (clipped) and a mergeable text operation
            *targetBatch = nullptr;
            break;
        }
    }
}

void OpReorderer::LayerReorderer::deferUnmergeableOp(LinearAllocator& allocator,
        BakedOpState* op, batchid_t batchId) {
    OpBatch* targetBatch = mBatchLookup[batchId];

    size_t insertBatchIndex = mBatches.size();
    if (targetBatch) {
        locateInsertIndex(batchId, op->computedState.clippedBounds,
                (BatchBase**)(&targetBatch), &insertBatchIndex);
    }

    if (targetBatch) {
        targetBatch->batchOp(op);
    } else  {
        // new non-merging batch
        targetBatch = new (allocator) OpBatch(batchId, op);
        mBatchLookup[batchId] = targetBatch;
        mBatches.insert(mBatches.begin() + insertBatchIndex, targetBatch);
    }
}

// insertion point of a new batch, will hopefully be immediately after similar batch
// (generally, should be similar shader)
void OpReorderer::LayerReorderer::deferMergeableOp(LinearAllocator& allocator,
        BakedOpState* op, batchid_t batchId, mergeid_t mergeId) {
    MergingOpBatch* targetBatch = nullptr;

    // Try to merge with any existing batch with same mergeId
    auto getResult = mMergingBatchLookup[batchId].find(mergeId);
    if (getResult != mMergingBatchLookup[batchId].end()) {
        targetBatch = getResult->second;
        if (!targetBatch->canMergeWith(op)) {
            targetBatch = nullptr;
        }
    }

    size_t insertBatchIndex = mBatches.size();
    locateInsertIndex(batchId, op->computedState.clippedBounds,
            (BatchBase**)(&targetBatch), &insertBatchIndex);

    if (targetBatch) {
        targetBatch->mergeOp(op);
    } else  {
        // new merging batch
        targetBatch = new (allocator) MergingOpBatch(batchId, op);
        mMergingBatchLookup[batchId].insert(std::make_pair(mergeId, targetBatch));

        mBatches.insert(mBatches.begin() + insertBatchIndex, targetBatch);
    }
}

void OpReorderer::LayerReorderer::replayBakedOpsImpl(void* arg, BakedOpDispatcher* receivers) const {
    ATRACE_NAME("flush drawing commands");
    for (const BatchBase* batch : mBatches) {
        // TODO: different behavior based on batch->isMerging()
        for (const BakedOpState* op : batch->getOps()) {
            receivers[op->op->opId](arg, *op->op, *op);
        }
    }
}

void OpReorderer::LayerReorderer::dump() const {
    ALOGD("LayerReorderer %p, %ux%u buffer %p, blo %p, rn %p",
            this, width, height, offscreenBuffer, beginLayerOp, renderNode);
    for (const BatchBase* batch : mBatches) {
        batch->dump();
    }
}

OpReorderer::OpReorderer(const LayerUpdateQueue& layers, const SkRect& clip,
        uint32_t viewportWidth, uint32_t viewportHeight,
        const std::vector< sp<RenderNode> >& nodes)
        : mCanvasState(*this) {
    ATRACE_NAME("prepare drawing commands");
    mLayerReorderers.emplace_back(viewportWidth, viewportHeight);
        mLayerStack.push_back(0);

    mCanvasState.initializeSaveStack(viewportWidth, viewportHeight,
            clip.fLeft, clip.fTop, clip.fRight, clip.fBottom,
            Vector3());

    // Render all layers to be updated, in order. Defer in reverse order, so that they'll be
    // updated in the order they're passed in (mLayerReorderers are issued to Renderer in reverse)
    for (int i = layers.entries().size() - 1; i >= 0; i--) {
        RenderNode* layerNode = layers.entries()[i].renderNode;
        const Rect& layerDamage = layers.entries()[i].damage;

        saveForLayer(layerNode->getWidth(), layerNode->getHeight(), nullptr, layerNode);
        mCanvasState.writableSnapshot()->setClip(
                layerDamage.left, layerDamage.top, layerDamage.right, layerDamage.bottom);

        if (layerNode->getDisplayList()) {
            deferImpl(*(layerNode->getDisplayList()));
        }
        restoreForLayer();
    }

    // Defer Fbo0
    for (const sp<RenderNode>& node : nodes) {
        if (node->nothingToDraw()) continue;

        int count = mCanvasState.save(SkCanvas::kClip_SaveFlag | SkCanvas::kMatrix_SaveFlag);
        deferNodePropsAndOps(*node);
        mCanvasState.restoreToCount(count);
    }
}

OpReorderer::OpReorderer(int viewportWidth, int viewportHeight, const DisplayList& displayList)
        : mCanvasState(*this) {
    ATRACE_NAME("prepare drawing commands");

    mLayerReorderers.emplace_back(viewportWidth, viewportHeight);
    mLayerStack.push_back(0);

    mCanvasState.initializeSaveStack(viewportWidth, viewportHeight,
            0, 0, viewportWidth, viewportHeight, Vector3());
    deferImpl(displayList);
}

void OpReorderer::onViewportInitialized() {}

void OpReorderer::onSnapshotRestored(const Snapshot& removed, const Snapshot& restored) {}

void OpReorderer::deferNodePropsAndOps(RenderNode& node) {
    if (node.applyViewProperties(mCanvasState, mAllocator)) {
        // not rejected so render
        if (node.getLayer()) {
            // HW layer
            LayerOp* drawLayerOp = new (mAllocator) LayerOp(node);
            BakedOpState* bakedOpState = tryBakeOpState(*drawLayerOp);
            if (bakedOpState) {
                // Layer will be drawn into parent layer (which is now current, since we popped mLayerStack)
                currentLayer().deferUnmergeableOp(mAllocator, bakedOpState, OpBatchType::Bitmap);
            }
        } else {
            deferImpl(*(node.getDisplayList()));
        }
    }
}

typedef key_value_pair_t<float, const RenderNodeOp*> ZRenderNodeOpPair;

template <typename V>
static void buildZSortedChildList(V* zTranslatedNodes,
        const DisplayList& displayList, const DisplayList::Chunk& chunk) {
    if (chunk.beginChildIndex == chunk.endChildIndex) return;

    for (size_t i = chunk.beginChildIndex; i < chunk.endChildIndex; i++) {
        RenderNodeOp* childOp = displayList.getChildren()[i];
        RenderNode* child = childOp->renderNode;
        float childZ = child->properties().getZ();

        if (!MathUtils::isZero(childZ) && chunk.reorderChildren) {
            zTranslatedNodes->push_back(ZRenderNodeOpPair(childZ, childOp));
            childOp->skipInOrderDraw = true;
        } else if (!child->properties().getProjectBackwards()) {
            // regular, in order drawing DisplayList
            childOp->skipInOrderDraw = false;
        }
    }

    // Z sort any 3d children (stable-ness makes z compare fall back to standard drawing order)
    std::stable_sort(zTranslatedNodes->begin(), zTranslatedNodes->end());
}

template <typename V>
static size_t findNonNegativeIndex(const V& zTranslatedNodes) {
    for (size_t i = 0; i < zTranslatedNodes.size(); i++) {
        if (zTranslatedNodes[i].key >= 0.0f) return i;
    }
    return zTranslatedNodes.size();
}

template <typename V>
void OpReorderer::defer3dChildren(ChildrenSelectMode mode, const V& zTranslatedNodes) {
    const int size = zTranslatedNodes.size();
    if (size == 0
            || (mode == ChildrenSelectMode::Negative&& zTranslatedNodes[0].key > 0.0f)
            || (mode == ChildrenSelectMode::Positive && zTranslatedNodes[size - 1].key < 0.0f)) {
        // no 3d children to draw
        return;
    }

    /**
     * Draw shadows and (potential) casters mostly in order, but allow the shadows of casters
     * with very similar Z heights to draw together.
     *
     * This way, if Views A & B have the same Z height and are both casting shadows, the shadows are
     * underneath both, and neither's shadow is drawn on top of the other.
     */
    const size_t nonNegativeIndex = findNonNegativeIndex(zTranslatedNodes);
    size_t drawIndex, shadowIndex, endIndex;
    if (mode == ChildrenSelectMode::Negative) {
        drawIndex = 0;
        endIndex = nonNegativeIndex;
        shadowIndex = endIndex; // draw no shadows
    } else {
        drawIndex = nonNegativeIndex;
        endIndex = size;
        shadowIndex = drawIndex; // potentially draw shadow for each pos Z child
    }

    float lastCasterZ = 0.0f;
    while (shadowIndex < endIndex || drawIndex < endIndex) {
        if (shadowIndex < endIndex) {
            const RenderNodeOp* casterNodeOp = zTranslatedNodes[shadowIndex].value;
            const float casterZ = zTranslatedNodes[shadowIndex].key;
            // attempt to render the shadow if the caster about to be drawn is its caster,
            // OR if its caster's Z value is similar to the previous potential caster
            if (shadowIndex == drawIndex || casterZ - lastCasterZ < 0.1f) {
                deferShadow(*casterNodeOp);

                lastCasterZ = casterZ; // must do this even if current caster not casting a shadow
                shadowIndex++;
                continue;
            }
        }

        const RenderNodeOp* childOp = zTranslatedNodes[drawIndex].value;
        deferRenderNodeOp(*childOp);
        drawIndex++;
    }
}

void OpReorderer::deferShadow(const RenderNodeOp& casterNodeOp) {
    // TODO
}
/**
 * Used to define a list of lambdas referencing private OpReorderer::onXXXXOp() methods.
 *
 * This allows opIds embedded in the RecordedOps to be used for dispatching to these lambdas. E.g. a
 * BitmapOp op then would be dispatched to OpReorderer::onBitmapOp(const BitmapOp&)
 */
#define OP_RECEIVER(Type) \
        [](OpReorderer& reorderer, const RecordedOp& op) { reorderer.on##Type(static_cast<const Type&>(op)); },
void OpReorderer::deferImpl(const DisplayList& displayList) {
    static std::function<void(OpReorderer& reorderer, const RecordedOp&)> receivers[] = {
        MAP_OPS(OP_RECEIVER)
    };
    for (const DisplayList::Chunk& chunk : displayList.getChunks()) {
        FatVector<ZRenderNodeOpPair, 16> zTranslatedNodes;
        buildZSortedChildList(&zTranslatedNodes, displayList, chunk);

        defer3dChildren(ChildrenSelectMode::Negative, zTranslatedNodes);
        for (size_t opIndex = chunk.beginOpIndex; opIndex < chunk.endOpIndex; opIndex++) {
            const RecordedOp* op = displayList.getOps()[opIndex];
            receivers[op->opId](*this, *op);
        }
        defer3dChildren(ChildrenSelectMode::Positive, zTranslatedNodes);
    }
}

void OpReorderer::deferRenderNodeOp(const RenderNodeOp& op) {
    if (op.renderNode->nothingToDraw()) return;
    int count = mCanvasState.save(SkCanvas::kClip_SaveFlag | SkCanvas::kMatrix_SaveFlag);

    // apply state from RecordedOp
    mCanvasState.concatMatrix(op.localMatrix);
    mCanvasState.clipRect(op.localClipRect.left, op.localClipRect.top,
            op.localClipRect.right, op.localClipRect.bottom, SkRegion::kIntersect_Op);

    // then apply state from node properties, and defer ops
    deferNodePropsAndOps(*op.renderNode);

    mCanvasState.restoreToCount(count);
}

void OpReorderer::onRenderNodeOp(const RenderNodeOp& op) {
    if (!op.skipInOrderDraw) {
        deferRenderNodeOp(op);
    }
}

static batchid_t tessellatedBatchId(const SkPaint& paint) {
    return paint.getPathEffect()
            ? OpBatchType::AlphaMaskTexture
            : (paint.isAntiAlias() ? OpBatchType::AlphaVertices : OpBatchType::Vertices);
}

void OpReorderer::onBitmapOp(const BitmapOp& op) {
    BakedOpState* bakedStateOp = tryBakeOpState(op);
    if (!bakedStateOp) return; // quick rejected

    mergeid_t mergeId = (mergeid_t) op.bitmap->getGenerationID();
    // TODO: AssetAtlas
    currentLayer().deferMergeableOp(mAllocator, bakedStateOp, OpBatchType::Bitmap, mergeId);
}

void OpReorderer::onRectOp(const RectOp& op) {
    BakedOpState* bakedStateOp = tryBakeOpState(op);
    if (!bakedStateOp) return; // quick rejected
    currentLayer().deferUnmergeableOp(mAllocator, bakedStateOp, tessellatedBatchId(*op.paint));
}

void OpReorderer::onSimpleRectsOp(const SimpleRectsOp& op) {
    BakedOpState* bakedStateOp = tryBakeOpState(op);
    if (!bakedStateOp) return; // quick rejected
    currentLayer().deferUnmergeableOp(mAllocator, bakedStateOp, OpBatchType::Vertices);
}

void OpReorderer::saveForLayer(uint32_t layerWidth, uint32_t layerHeight,
        const BeginLayerOp* beginLayerOp, RenderNode* renderNode) {

    mCanvasState.save(SkCanvas::kClip_SaveFlag | SkCanvas::kMatrix_SaveFlag);
    mCanvasState.writableSnapshot()->transform->loadIdentity();
    mCanvasState.writableSnapshot()->initializeViewport(layerWidth, layerHeight);
    mCanvasState.writableSnapshot()->roundRectClipState = nullptr;

    // create a new layer, and push its index on the stack
    mLayerStack.push_back(mLayerReorderers.size());
    mLayerReorderers.emplace_back(layerWidth, layerHeight, beginLayerOp, renderNode);
}

void OpReorderer::restoreForLayer() {
    // restore canvas, and pop finished layer off of the stack
    mCanvasState.restore();
    mLayerStack.pop_back();
}

// TODO: test rejection at defer time, where the bounds become empty
void OpReorderer::onBeginLayerOp(const BeginLayerOp& op) {
    const uint32_t layerWidth = (uint32_t) op.unmappedBounds.getWidth();
    const uint32_t layerHeight = (uint32_t) op.unmappedBounds.getHeight();
    saveForLayer(layerWidth, layerHeight, &op, nullptr);
}

void OpReorderer::onEndLayerOp(const EndLayerOp& /* ignored */) {
    const BeginLayerOp& beginLayerOp = *currentLayer().beginLayerOp;
    int finishedLayerIndex = mLayerStack.back();

    restoreForLayer();

    // record the draw operation into the previous layer's list of draw commands
    // uses state from the associated beginLayerOp, since it has all the state needed for drawing
    LayerOp* drawLayerOp = new (mAllocator) LayerOp(
            beginLayerOp.unmappedBounds,
            beginLayerOp.localMatrix,
            beginLayerOp.localClipRect,
            beginLayerOp.paint,
            &mLayerReorderers[finishedLayerIndex].offscreenBuffer);
    BakedOpState* bakedOpState = tryBakeOpState(*drawLayerOp);

    if (bakedOpState) {
        // Layer will be drawn into parent layer (which is now current, since we popped mLayerStack)
        currentLayer().deferUnmergeableOp(mAllocator, bakedOpState, OpBatchType::Bitmap);
    } else {
        // Layer won't be drawn - delete its drawing batches to prevent it from doing any work
        mLayerReorderers[finishedLayerIndex].clear();
        return;
    }
}

void OpReorderer::onLayerOp(const LayerOp& op) {
    LOG_ALWAYS_FATAL("unsupported");
}

} // namespace uirenderer
} // namespace android