Add pattern matchers for SkRecord

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
Committed: http://code.google.com/p/skia/source/detail?r=14582

[mtklein, 2014-05-05 18:27:14]

Once again, Ben for SkTLogic, Florin for the rest!

[bungeman-skia, 2014-05-05 19:37:50]

I'm going to think about it for a minute, but here's my initial thoughts.

https://codereview.chromium.org/263063002/diff/210001/src/utils/SkTLogic.h
File src/utils/SkTLogic.h (right):

https://codereview.chromium.org/263063002/diff/210001/src/utils/SkTLogic.h#ne...
src/utils/SkTLogic.h:98: 
So it seems the 'normal' way to do this would be to have a member type trait
detector like

#define SK_CREATE_TYPEDEF_DETECTOR(type) \
template <typename T> \
class HasTypedef_##type { \
    template <typename C> static uint8_t func(typename C::foobar*); \
    template <typename> static uint16_t func(...); \
public: \
    static const bool value = sizeof(func<T>(NULL)) == sizeof(uint8_t); \
}

and then

SK_CREATE_TYPEDEF_DETECTOR(type);
SK_WHEN(HasTypedef_type<MyType>, void)

Of course, this is also more complex and less flexible. It is more complex in
that it converts the existence to a bool and then picks T or nothing based on
the bool, as opposed to directly picking T or nothing based on the existence of
the type directly. It also introduces the extra HasTypedef_type name. It does
not handle top level typedefs (though I'm not sure one would want to do that,
maybe that limitation is a feature). On the other hand, it's more uniform to
current usage and removes the SkWhenType and SK_WHEN_TYPE names.

[mtklein, 2014-05-05 20:05:11]

https://codereview.chromium.org/263063002/diff/210001/src/utils/SkTLogic.h
File src/utils/SkTLogic.h (right):

https://codereview.chromium.org/263063002/diff/210001/src/utils/SkTLogic.h#ne...
src/utils/SkTLogic.h:98: 
Strongly agreed and done.

[bungeman-skia, 2014-05-05 20:16:43]

logic / traits lgtm

[f(malita), 2014-05-05 20:52:58]

template voodoo DSL FTW!!!

lgtm

https://codereview.chromium.org/263063002/diff/230001/src/record/SkRecordOpts...
File src/record/SkRecordOpts.cpp (right):

https://codereview.chromium.org/263063002/diff/230001/src/record/SkRecordOpts...
src/record/SkRecordOpts.cpp:158: // There's no efficient way (yet?) to express
this one as a pattern, so we write a custom pass.
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?

https://codereview.chromium.org/263063002/diff/230001/src/record/SkRecordPatt...
File src/record/SkRecordPattern.h (right):

https://codereview.chromium.org/263063002/diff/230001/src/record/SkRecordPatt...
src/record/SkRecordPattern.h:123: // These Cons build lists analagously to
Lisp's "cons".  See Pattern# for the "list" equivalent.
"analogously"

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

https://codereview.chromium.org/263063002/diff/230001/src/record/SkRecordOpts...
File src/record/SkRecordOpts.cpp (right):

https://codereview.chromium.org/263063002/diff/230001/src/record/SkRecordOpts...
src/record/SkRecordOpts.cpp:158: // There's no efficient way (yet?) to express
this one as a pattern, so we write a custom pass.
On 2014/05/05 20:52:59, Florin Malita wrote:
> 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?

(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.

https://codereview.chromium.org/263063002/diff/230001/src/record/SkRecordPatt...
File src/record/SkRecordPattern.h (right):

https://codereview.chromium.org/263063002/diff/230001/src/record/SkRecordPatt...
src/record/SkRecordPattern.h:123: // These Cons build lists analagously to
Lisp's "cons".  See Pattern# for the "list" equivalent.
On 2014/05/05 20:52:59, Florin Malita wrote:
> "analogously"

Done.

[mtklein, 2014-05-05 21:45:34]

The CQ bit was checked by mtklein@google.com

[commit-bot: I haz the power, 2014-05-05 21:45:54]

CQ is trying da patch. Follow status at
 https://skia-tree-status.appspot.com/cq/mtklein@chromium.org/263063002/250001

[commit-bot: I haz the power, 2014-05-05 21:52:45]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-05-05 21:52:45]

Retried try job too often on Build-Ubuntu13.10-GCC4.8-x86_64-Release-Trybot for
step(s) BuildTests
http://skia-tree-status.appspot.com/redirect/compile-buildbots/buildstatus?bu...

[mtklein, 2014-05-05 21:53:32]

The CQ bit was checked by mtklein@google.com

[commit-bot: I haz the power, 2014-05-05 21:54:10]

CQ is trying da patch. Follow status at
 https://skia-tree-status.appspot.com/cq/mtklein@chromium.org/263063002/270001

[commit-bot: I haz the power, 2014-05-05 21:59:59]

Change committed as 14582