Add pattern matchers for SkRecord

This is a mid-level library for finding patterns of commands in an SkRecord.  At the API level, it's a bit regex inspired.  Some examples:
 - Pattern1<Is<DrawRect>> matches a single DrawRect

 - Pattern1<Star<Is<DrawRect>>> matches 0 or more DrawRects

 - Pattern2<Is<ClipRect>, Is<DrawRect>> matches a single clip rect followed by a single draw rect

  - Pattern3<Is<Save>, Star<IsDraw>, Is<Restore>> matches a single Save, followed by any number of Draws, followed by Restore

 - Pattern1<Or<Is<DrawRect>, Is<ClipRect>>> matches a DrawRect or a ClipRect

 - Pattern1<Not<Is<ClipRect>>> matches a command that's notClipRect.

Once you have a pattern, you can call .search() on it to step through ranges of matching commands.  This means patterns can replace most of the custom iteration logic for optimization passes: the generic pattern searching steps through all the optimization candidates, which optimization-specific code further inspects and mutates.

SkRecordTraits is now unused.  Bye bye!

Generated code and performance of SkRecordOpts is very similar to what it was before.  (I had to use SK_ALWAYS_INLINE in a few places to make this so.)

BUG=skia:2378
R=fmalita@chromium.org, bungeman@google.com, mtklein@google.com

Author: mtklein@chromium.org

Review URL: https://codereview.chromium.org/263063002

git-svn-id: http://skia.googlecode.com/svn/trunk@14582 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 192 insertions, 0 deletions

diff --git a/tests/RecordPatternTest.cpp b/tests/RecordPatternTest.cpp
new file mode 100644
index 0000000000..e013150072
--- /dev/null
+++ b/tests/RecordPatternTest.cpp
@@ -0,0 +1,192 @@
+#include "Test.h"
+
+#include "SkRecord.h"
+#include "SkRecordPattern.h"
+#include "SkRecorder.h"
+#include "SkRecords.h"
+
+using namespace SkRecords;
+typedef Pattern3<Is<Save>,
+                 Is<ClipRect>,
+                 Is<Restore> >
+    SaveClipRectRestore;
+
+DEF_TEST(RecordPattern_Simple, r) {
+    SaveClipRectRestore pattern;
+
+    SkRecord record;
+    REPORTER_ASSERT(r, !pattern.match(&record, 0));
+
+    SkRecorder recorder(SkRecorder::kWriteOnly_Mode, &record, 1920, 1200);
+
+    // Build up a save-clip-restore block.  The pattern will match only it's complete.
+    recorder.save();
+    REPORTER_ASSERT(r, !pattern.match(&record, 0));
+
+    recorder.clipRect(SkRect::MakeWH(300, 200));
+    REPORTER_ASSERT(r, !pattern.match(&record, 0));
+
+    recorder.restore();
+    REPORTER_ASSERT(r, pattern.match(&record, 0));
+    REPORTER_ASSERT(r, pattern.first<Save>()      != NULL);
+    REPORTER_ASSERT(r, pattern.second<ClipRect>() != NULL);
+    REPORTER_ASSERT(r, pattern.third<Restore>()   != NULL);
+}
+
+DEF_TEST(RecordPattern_StartingIndex, r) {
+    SaveClipRectRestore pattern;
+
+    SkRecord record;
+    SkRecorder recorder(SkRecorder::kWriteOnly_Mode, &record, 1920, 1200);
+
+    // There will be two save-clipRect-restore blocks [0,3) and [3,6).
+    for (int i = 0; i < 2; i++) {
+        recorder.save();
+            recorder.clipRect(SkRect::MakeWH(300, 200));
+        recorder.restore();
+    }
+
+    // We should match only at 0 and 3.  Going over the length should fail gracefully.
+    for (unsigned i = 0; i < 8; i++) {
+        if (i == 0 || i == 3) {
+            REPORTER_ASSERT(r, pattern.match(&record, i) == i + 3);
+        } else {
+            REPORTER_ASSERT(r, !pattern.match(&record, i));
+        }
+    }
+}
+
+DEF_TEST(RecordPattern_DontMatchSubsequences, r) {
+    SaveClipRectRestore pattern;
+
+    SkRecord record;
+    SkRecorder recorder(SkRecorder::kWriteOnly_Mode, &record, 1920, 1200);
+
+    recorder.save();
+        recorder.clipRect(SkRect::MakeWH(300, 200));
+        recorder.drawRect(SkRect::MakeWH(600, 300), SkPaint());
+    recorder.restore();
+
+    REPORTER_ASSERT(r, !pattern.match(&record, 0));
+}
+
+DEF_TEST(RecordPattern_Star, r) {
+    Pattern3<Is<Save>, Star<Is<ClipRect> >, Is<Restore> > pattern;
+
+    SkRecord record;
+    SkRecorder recorder(SkRecorder::kWriteOnly_Mode, &record, 1920, 1200);
+
+    recorder.save();
+    recorder.restore();
+    REPORTER_ASSERT(r, pattern.match(&record, 0));
+    REPORTER_ASSERT(r, pattern.second<SkTDArray<ClipRect*> >()->count() == 0);
+
+    recorder.save();
+        recorder.clipRect(SkRect::MakeWH(300, 200));
+    recorder.restore();
+    REPORTER_ASSERT(r, pattern.match(&record, 2));
+    REPORTER_ASSERT(r, pattern.second<SkTDArray<ClipRect*> >()->count() == 1);
+
+    recorder.save();
+        recorder.clipRect(SkRect::MakeWH(300, 200));
+        recorder.clipRect(SkRect::MakeWH(100, 100));
+    recorder.restore();
+    REPORTER_ASSERT(r, pattern.match(&record, 5));
+    REPORTER_ASSERT(r, pattern.second<SkTDArray<ClipRect*> >()->count() == 2);
+}
+
+DEF_TEST(RecordPattern_IsDraw, r) {
+    Pattern3<Is<Save>, IsDraw, Is<Restore> > pattern;
+
+    SkRecord record;
+    SkRecorder recorder(SkRecorder::kWriteOnly_Mode, &record, 1920, 1200);
+
+    recorder.save();
+        recorder.clipRect(SkRect::MakeWH(300, 200));
+    recorder.restore();
+
+    REPORTER_ASSERT(r, !pattern.match(&record, 0));
+
+    SkPaint paint;
+
+    recorder.save();
+        paint.setColor(0xEEAA8822);
+        recorder.drawRect(SkRect::MakeWH(300, 200), paint);
+    recorder.restore();
+
+    recorder.save();
+        paint.setColor(0xFACEFACE);
+        recorder.drawPaint(paint);
+    recorder.restore();
+
+    REPORTER_ASSERT(r, pattern.match(&record, 3));
+    REPORTER_ASSERT(r, pattern.first<Save>()    != NULL);
+    REPORTER_ASSERT(r, pattern.second<SkPaint>()->getColor() == 0xEEAA8822);
+    REPORTER_ASSERT(r, pattern.third<Restore>() != NULL);
+
+    REPORTER_ASSERT(r, pattern.match(&record, 6));
+    REPORTER_ASSERT(r, pattern.first<Save>()    != NULL);
+    REPORTER_ASSERT(r, pattern.second<SkPaint>()->getColor() == 0xFACEFACE);
+    REPORTER_ASSERT(r, pattern.third<Restore>() != NULL);
+}
+
+DEF_TEST(RecordPattern_Complex, r) {
+    Pattern3<Is<Save>,
+             Star<Not<Or3<Is<Save>,
+                          Is<Restore>,
+                          IsDraw> > >,
+             Is<Restore> > pattern;
+
+    SkRecord record;
+    SkRecorder recorder(SkRecorder::kWriteOnly_Mode, &record, 1920, 1200);
+
+    recorder.save();
+    recorder.restore();
+    REPORTER_ASSERT(r, pattern.match(&record, 0) == 2);
+
+    recorder.save();
+        recorder.save();
+        recorder.restore();
+    recorder.restore();
+    REPORTER_ASSERT(r, !pattern.match(&record, 2));
+    REPORTER_ASSERT(r, pattern.match(&record, 3) == 5);
+
+    recorder.save();
+        recorder.clipRect(SkRect::MakeWH(300, 200));
+    recorder.restore();
+    REPORTER_ASSERT(r, pattern.match(&record, 6) == 9);
+
+    recorder.save();
+        recorder.clipRect(SkRect::MakeWH(300, 200));
+        recorder.drawRect(SkRect::MakeWH(100, 3000), SkPaint());
+    recorder.restore();
+    REPORTER_ASSERT(r, !pattern.match(&record, 9));
+
+    recorder.save();
+        recorder.pushCull(SkRect::MakeWH(300, 200));
+        recorder.clipRect(SkRect::MakeWH(300, 200));
+        recorder.clipRect(SkRect::MakeWH(100, 400));
+        recorder.popCull();
+    recorder.restore();
+    REPORTER_ASSERT(r, pattern.match(&record, 13) == 19);
+
+    // Same as above, but using pattern.search to step through matches.
+    unsigned begin, end = 0;
+    REPORTER_ASSERT(r, pattern.search(&record, &begin, &end));
+    REPORTER_ASSERT(r, begin == 0);
+    REPORTER_ASSERT(r, end == 2);
+
+    REPORTER_ASSERT(r, pattern.search(&record, &begin, &end));
+    REPORTER_ASSERT(r, begin == 3);
+    REPORTER_ASSERT(r, end == 5);
+
+    REPORTER_ASSERT(r, pattern.search(&record, &begin, &end));
+    REPORTER_ASSERT(r, begin == 6);
+    REPORTER_ASSERT(r, end == 9);
+
+    REPORTER_ASSERT(r, pattern.search(&record, &begin, &end));
+    REPORTER_ASSERT(r, begin == 13);
+    REPORTER_ASSERT(r, end == 19);
+
+    REPORTER_ASSERT(r, !pattern.search(&record, &begin, &end));
+}