Add pattern matchers for SkRecord

src/record/SkRecordOpts.cpp

Index: src/record/SkRecordOpts.cpp
diff --git a/src/record/SkRecordOpts.cpp b/src/record/SkRecordOpts.cpp
index 5b537de040120a7238ec2dbc95256eeabd51a027..aaa611cf392cf6126b5548f9c5f4e1bcb6a46e59 100644
--- a/src/record/SkRecordOpts.cpp
+++ b/src/record/SkRecordOpts.cpp
@@ -7,10 +7,12 @@
 
 #include "SkRecordOpts.h"
 
-#include "SkRecordTraits.h"
+#include "SkRecordPattern.h"
 #include "SkRecords.h"
 #include "SkTDArray.h"
 
+using namespace SkRecords;
+
 void SkRecordOptimize(SkRecord* record) {
     // TODO(mtklein): fuse independent optimizations to reduce number of passes?
     SkRecordNoopSaveRestores(record);
@@ -19,205 +21,180 @@ void SkRecordOptimize(SkRecord* record) {
     SkRecordBoundDrawPosTextH(record);
 }
 
-namespace {
-
-// Convenience base class to share some common implementation code.
-class Common : SkNoncopyable {
-public:
-    explicit Common(SkRecord* record) : fRecord(record), fIndex(0) {}
-
-    unsigned index() const { return fIndex; }
-    void next() { ++fIndex; }
-
-protected:
-    SkRecord* fRecord;
-    unsigned fIndex;
-};
-
-// Turns logical no-op Save-[non-drawing command]*-Restore patterns into actual no-ops.
-// TODO(mtklein): state machine diagram
-class SaveRestoreNooper : public Common {
-public:
-    explicit SaveRestoreNooper(SkRecord* record)
-        : Common(record), fSave(kInactive), fChanged(false) {}
-
-    // Drawing commands reset state to inactive without nooping.
-    template <typename T>
-    SK_WHEN(SkRecords::IsDraw<T>, void) operator()(T*) { fSave = kInactive; }
+// Most of the optimizations in this file are pattern-based.  These are all defined as structs with:
+//   - a Pattern typedef
+//   - a bool onMatch(SkRceord*, Pattern*, unsigned begin, unsigned end) method,
+//     which returns true if it made changes and false if not.
 
-    // Most non-drawing commands can be ignored.
-    template <typename T>
-    SK_WHEN(!SkRecords::IsDraw<T>, void) operator()(T*) {}
+// Run a pattern-based optimization once across the SkRecord, returning true if it made any changes.
+// It looks for spans which match Pass::Pattern, and when found calls onMatch() with the pattern,
+// record, and [begin,end) span of the commands that matched.
+template <typename Pass>
+static bool apply(Pass* pass, SkRecord* record) {
+    typename Pass::Pattern pattern;
+    bool changed = false;
+    unsigned begin, end = 0;
 
-    void operator()(SkRecords::Save* r) {
-        fSave = SkCanvas::kMatrixClip_SaveFlag == r->flags ? this->index() : kInactive;
+    while (pattern.search(record, &begin, &end)) {
+        changed |= pass->onMatch(record, &pattern, begin, end);
     }
+    return changed;
+}
 
-    void operator()(SkRecords::Restore* r) {
-        if (fSave != kInactive) {
-            // Remove everything between the save and restore, inclusive on both sides.
-            fChanged = true;
-            for (unsigned i = fSave; i <= this->index(); i++) {
-                fRecord->replace<SkRecords::NoOp>(i);
-            }
-            fSave = kInactive;
+// Turns logical no-op Save-[non-drawing command]*-Restore patterns into actual no-ops.
+struct SaveRestoreNooper {
+    // Star matches greedily, so we also have to exclude Save and Restore.
+    typedef Pattern3<Is<Save>,
+                     Star<Not<Or3<Is<Save>,
+                                  Is<Restore>,
+                                  IsDraw> > >,
+                     Is<Restore> >
+        Pattern;
+
+    bool onMatch(SkRecord* record, Pattern* pattern, unsigned begin, unsigned end) {
+        // If restore doesn't revert both matrix and clip, this isn't safe to noop away.
+        if (pattern->first<Save>()->flags != SkCanvas::kMatrixClip_SaveFlag) {
+            return false;
         }
-    }
-
-    bool changed() const { return fChanged; }
-
-private:
-    static const unsigned kInactive = ~0;
-    unsigned fSave;
-    bool fChanged;
-};
-
-// Tries to replace PushCull with PairedPushCull, which lets us skip to the paired PopCull
-// when the canvas can quickReject the cull rect.
-class CullAnnotator : public Common {
-public:
-    explicit CullAnnotator(SkRecord* record) : Common(record) {}
-
-    // Do nothing to most ops.
-    template <typename T> void operator()(T*) {}
-
-    void operator()(SkRecords::PushCull* push) {
-        Pair pair = { this->index(), push };
-        fPushStack.push(pair);
-    }
-
-    void operator()(SkRecords::PopCull* pop) {
-        Pair push = fPushStack.top();
-        fPushStack.pop();
-
-        SkASSERT(this->index() > push.index);
-        unsigned skip = this->index() - push.index;
 
-        SkRecords::Adopted<SkRecords::PushCull> adopted(push.command);
-        SkNEW_PLACEMENT_ARGS(fRecord->replace<SkRecords::PairedPushCull>(push.index, adopted),
-                             SkRecords::PairedPushCull, (&adopted, skip));
+        // The entire span between Save and Restore (inclusively) does nothing.
+        for (unsigned i = begin; i < end; i++) {
+            record->replace<NoOp>(i);
+        }
+        return true;
     }
-
-private:
-    struct Pair {
-        unsigned index;
-        SkRecords::PushCull* command;
-    };
-
-    SkTDArray<Pair> fPushStack;
 };
+void SkRecordNoopSaveRestores(SkRecord* record) {
+    SaveRestoreNooper pass;
+    while (apply(&pass, record));  // Run until it stops changing things.
+}
 
 // Replaces DrawPosText with DrawPosTextH when all Y coordinates are equal.
-class StrengthReducer : public Common {
-public:
-    explicit StrengthReducer(SkRecord* record) : Common(record) {}
+struct StrengthReducer {
+    typedef Pattern1<Is<DrawPosText> > Pattern;
 
-    // Do nothing to most ops.
-    template <typename T> void operator()(T*) {}
+    bool onMatch(SkRecord* record, Pattern* pattern, unsigned begin, unsigned end) {
+        SkASSERT(end == begin + 1);
+        DrawPosText* draw = pattern->first<DrawPosText>();
 
-    void operator()(SkRecords::DrawPosText* r) {
-        const unsigned points = r->paint.countText(r->text, r->byteLength);
+        const unsigned points = draw->paint.countText(draw->text, draw->byteLength);
         if (points == 0) {
-            // No point (ha!).
-            return;
+            return false;  // No point (ha!).
         }
 
-        const SkScalar firstY = r->pos[0].fY;
+        const SkScalar firstY = draw->pos[0].fY;
         for (unsigned i = 1; i < points; i++) {
-            if (r->pos[i].fY != firstY) {
-                // Needs the full strength of DrawPosText.
-                return;
+            if (draw->pos[i].fY != firstY) {
+                return false;  // Needs full power of DrawPosText.
             }
         }
         // All ys are the same.  We can replace DrawPosText with DrawPosTextH.
 
-        // r->pos is points SkPoints, [(x,y),(x,y),(x,y),(x,y), ... ].
+        // draw->pos is points SkPoints, [(x,y),(x,y),(x,y),(x,y), ... ].
         // We're going to squint and look at that as 2*points SkScalars, [x,y,x,y,x,y,x,y, ...].
         // Then we'll rearrange things so all the xs are in order up front, clobbering the ys.
         SK_COMPILE_ASSERT(sizeof(SkPoint) == 2 * sizeof(SkScalar), SquintingIsNotSafe);
-        SkScalar* scalars = &r->pos[0].fX;
+        SkScalar* scalars = &draw->pos[0].fX;
         for (unsigned i = 0; i < 2*points; i += 2) {
             scalars[i/2] = scalars[i];
         }
 
-        // Extend lifetime of r to the end of the method so we can copy its parts.
-        SkRecords::Adopted<SkRecords::DrawPosText> adopted(r);
-        SkNEW_PLACEMENT_ARGS(fRecord->replace<SkRecords::DrawPosTextH>(this->index(), adopted),
-                             SkRecords::DrawPosTextH,
-                             (r->text, r->byteLength, scalars, firstY, r->paint));
+        // Extend lifetime of draw to the end of the loop so we can copy its paint.
+        Adopted<DrawPosText> adopted(draw);
+        SkNEW_PLACEMENT_ARGS(record->replace<DrawPosTextH>(begin, adopted),
+                             DrawPosTextH,
+                             (draw->text, draw->byteLength, scalars, firstY, draw->paint));
+        return true;
     }
 };
+void SkRecordReduceDrawPosTextStrength(SkRecord* record) {
+    StrengthReducer pass;
+    apply(&pass, record);
+}
 
 // Tries to replace DrawPosTextH with BoundedDrawPosTextH, which knows conservative upper and lower
 // bounds to use with SkCanvas::quickRejectY.
-class TextBounder : public Common {
-public:
-    explicit TextBounder(SkRecord* record) : Common(record) {}
+struct TextBounder {
+    typedef Pattern1<Is<DrawPosTextH> > Pattern;
 
-    // Do nothing to most ops.
-    template <typename T> void operator()(T*) {}
+    bool onMatch(SkRecord* record, Pattern* pattern, unsigned begin, unsigned end) {
+        SkASSERT(end == begin + 1);
+        DrawPosTextH* draw = pattern->first<DrawPosTextH>();
 
-    void operator()(SkRecords::DrawPosTextH* r) {
         // If we're drawing vertical text, none of the checks we're about to do make any sense.
         // We'll need to call SkPaint::computeFastBounds() later, so bail if that's not possible.
-        if (r->paint.isVerticalText() || !r->paint.canComputeFastBounds()) {
-            return;
+        if (draw->paint.isVerticalText() || !draw->paint.canComputeFastBounds()) {
+            return false;
         }
 
         // Rather than checking the top and bottom font metrics, we guess.  Actually looking up the
         // top and bottom metrics is slow, and this overapproximation should be good enough.
-        const SkScalar buffer = r->paint.getTextSize() * 1.5f;
+        const SkScalar buffer = draw->paint.getTextSize() * 1.5f;
         SkDEBUGCODE(SkPaint::FontMetrics metrics;)
-        SkDEBUGCODE(r->paint.getFontMetrics(&metrics);)
+        SkDEBUGCODE(draw->paint.getFontMetrics(&metrics);)
         SkASSERT(-buffer <= metrics.fTop);
         SkASSERT(+buffer >= metrics.fBottom);
 
         // Let the paint adjust the text bounds.  We don't care about left and right here, so we use
         // 0 and 1 respectively just so the bounds rectangle isn't empty.
         SkRect bounds;
-        bounds.set(0, r->y - buffer, SK_Scalar1, r->y + buffer);
-        SkRect adjusted = r->paint.computeFastBounds(bounds, &bounds);
-
-        SkRecords::Adopted<SkRecords::DrawPosTextH> adopted(r);
-        SkNEW_PLACEMENT_ARGS(
-                fRecord->replace<SkRecords::BoundedDrawPosTextH>(this->index(), adopted),
-                SkRecords::BoundedDrawPosTextH,
-                (&adopted, adjusted.fTop, adjusted.fBottom));
+        bounds.set(0, draw->y - buffer, SK_Scalar1, draw->y + buffer);
+        SkRect adjusted = draw->paint.computeFastBounds(bounds, &bounds);
+
+        Adopted<DrawPosTextH> adopted(draw);
+        SkNEW_PLACEMENT_ARGS(record->replace<BoundedDrawPosTextH>(begin, adopted),
+                             BoundedDrawPosTextH,
+                             (&adopted, adjusted.fTop, adjusted.fBottom));
+        return true;
     }
 };
+void SkRecordBoundDrawPosTextH(SkRecord* record) {
+    TextBounder pass;
+    apply(&pass, record);
+}
 
+// Replaces PushCull with PairedPushCull, which lets us skip to the paired PopCull when the canvas
+// can quickReject the cull rect.
+// There's no efficient way (yet?) to express this one as a pattern, so we write a custom pass.

[f(malita), 2014/05/05 20:52:59]

Doesn't 

Pattern3<
  Is<PushCull>,
  Star<Not<Or2<Is<PushCull>,Is<PopCull>>>>,
  Is<PopCull>>

capture this? I guess we'd have to apply repeatedly - hence the "efficient"
qualifier?

[mtklein, 2014/05/05 21:43:31]

(I know we talked about this, but I wanted to write it down too for posterity
and to make sure my thinking is clear.)

Yep, that pattern would work if applied repeatedly.  Efficiency is what I'm
worried about.  My main worry is having to apply it repeatedly.  We'd slice off
one layer of PushCull / PopCull at a time, working from bottom of the tree up,
just like we do with SaveRestoreNooper.

The difference here is that we have a direct way of doing everything we want to
do for CullAnnotator in one pass, where SaveRestoreNooper feeds on its own work.
 I'm not sure I could write the SaveRestoreNooper that works in one pass
correctly without lots of test cases.  We also know ahead of time that
CullAnnotator will apply to every PushCull/PopCull pair, where SaveRestoreNooper
ought to be a rarer thing to find, and should usually finish in two or three
passes.

I may play around a bit with extending the DSL to support pushdown automata like
CullAnnotator, but I'd probably want to get one or two other examples of them
working explicitly before I'd feel comfortable building up an abstraction like
that.

+class CullAnnotator {
+public:
+    // Do nothing to most ops.
+    template <typename T> void operator()(T*) {}
 
-template <typename Pass>
-static void run_pass(Pass& pass, SkRecord* record) {
-    for (; pass.index() < record->count(); pass.next()) {
-        record->mutate(pass.index(), pass);
+    void operator()(PushCull* push) {
+        Pair pair = { fIndex, push };
+        fPushStack.push(pair);
     }
-}
 
-}  // namespace
+    void operator()(PopCull* pop) {
+        Pair push = fPushStack.top();
+        fPushStack.pop();
 
+        SkASSERT(fIndex > push.index);
+        unsigned skip = fIndex - push.index;
 
-void SkRecordNoopSaveRestores(SkRecord* record) {
-    // Run SaveRestoreNooper until it doesn't make any more changes.
-    bool changed;
-    do {
-        SaveRestoreNooper nooper(record);
-        run_pass(nooper, record);
-        changed = nooper.changed();
-    } while (changed);
-}
+        Adopted<PushCull> adopted(push.command);
+        SkNEW_PLACEMENT_ARGS(fRecord->replace<PairedPushCull>(push.index, adopted),
+                             PairedPushCull, (&adopted, skip));
+    }
 
-void SkRecordAnnotateCullingPairs(SkRecord* record) {
-    CullAnnotator annotator(record);
-    run_pass(annotator, record);
-}
+    void apply(SkRecord* record) {
+        for (fRecord = record, fIndex = 0; fIndex < record->count(); fIndex++) {
+            fRecord->mutate(fIndex, *this);
+        }
+    }
 
-void SkRecordReduceDrawPosTextStrength(SkRecord* record) {
-    StrengthReducer reducer(record);
-    run_pass(reducer, record);
-}
+private:
+    struct Pair {
+        unsigned index;
+        PushCull* command;
+    };
 
-void SkRecordBoundDrawPosTextH(SkRecord* record) {
-    TextBounder bounder(record);
-    run_pass(bounder, record);
+    SkTDArray<Pair> fPushStack;
+    SkRecord* fRecord;
+    unsigned fIndex;
+};
+void SkRecordAnnotateCullingPairs(SkRecord* record) {
+    CullAnnotator pass;
+    pass.apply(record);
 }