1/*
2 * Copyright 2014 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#ifndef SkRecord_DEFINED
9#define SkRecord_DEFINED
10
11#include "SkChunkAlloc.h"
12#include "SkRecords.h"
13#include "SkTLogic.h"
14#include "SkTemplates.h"
15
16// SkRecord (REC-ord) represents a sequence of SkCanvas calls, saved for future use.
17// These future uses may include: replay, optimization, serialization, or combinations of those.
18//
19// Though an enterprising user may find calling alloc(), append(), visit(), and mutate() enough to
20// work with SkRecord, you probably want to look at SkRecorder which presents an SkCanvas interface
21// for creating an SkRecord, and SkRecordDraw which plays an SkRecord back into another SkCanvas.
22//
23// SkRecord often looks like it's compatible with any type T, but really it's compatible with any
24// type T which has a static const SkRecords::Type kType.  That is to say, SkRecord is compatible
25// only with SkRecords::* structs defined in SkRecords.h.  Your compiler will helpfully yell if you
26// get this wrong.
27
28class SkRecord : SkNoncopyable {
29    enum {
30        kChunkBytes = 4096,
31        kFirstReserveCount = 64 / sizeof(void*),
32    };
33public:
34    SkRecord() : fAlloc(kChunkBytes), fCount(0), fReserved(0) {}
35
36    ~SkRecord() {
37        Destroyer destroyer;
38        for (unsigned i = 0; i < this->count(); i++) {
39            this->mutate<void>(i, destroyer);
40        }
41    }
42
43    // Returns the number of canvas commands in this SkRecord.
44    unsigned count() const { return fCount; }
45
46    // Visit the i-th canvas command with a functor matching this interface:
47    //   template <typename T>
48    //   R operator()(const T& record) { ... }
49    // This operator() must be defined for at least all SkRecords::*.
50    template <typename R, typename F>
51    R visit(unsigned i, F& f) const {
52        SkASSERT(i < this->count());
53        return fRecords[i].visit<R>(fTypes[i], f);
54    }
55
56    // Mutate the i-th canvas command with a functor matching this interface:
57    //   template <typename T>
58    //   R operator()(T* record) { ... }
59    // This operator() must be defined for at least all SkRecords::*.
60    template <typename R, typename F>
61    R mutate(unsigned i, F& f) {
62        SkASSERT(i < this->count());
63        return fRecords[i].mutate<R>(fTypes[i], f);
64    }
65    // TODO: It'd be nice to infer R from F for visit and mutate if we ever get std::result_of.
66
67    // Allocate contiguous space for count Ts, to be freed when the SkRecord is destroyed.
68    // Here T can be any class, not just those from SkRecords.  Throws on failure.
69    template <typename T>
70    T* alloc(size_t count = 1) {
71        // Bump up to the next pointer width if needed, so all allocations start pointer-aligned.
72        return (T*)fAlloc.allocThrow(SkAlignPtr(sizeof(T) * count));
73    }
74
75    // Add a new command of type T to the end of this SkRecord.
76    // You are expected to placement new an object of type T onto this pointer.
77    template <typename T>
78    T* append() {
79        if (fCount == fReserved) {
80            fReserved = SkTMax<unsigned>(kFirstReserveCount, fReserved*2);
81            fRecords.realloc(fReserved);
82            fTypes.realloc(fReserved);
83        }
84
85        fTypes[fCount] = T::kType;
86        return fRecords[fCount++].set(this->allocCommand<T>());
87    }
88
89    // Replace the i-th command with a new command of type T.
90    // You are expected to placement new an object of type T onto this pointer.
91    // References to the original command are invalidated.
92    template <typename T>
93    T* replace(unsigned i) {
94        SkASSERT(i < this->count());
95
96        Destroyer destroyer;
97        this->mutate<void>(i, destroyer);
98
99        fTypes[i] = T::kType;
100        return fRecords[i].set(this->allocCommand<T>());
101    }
102
103    // Replace the i-th command with a new command of type T.
104    // You are expected to placement new an object of type T onto this pointer.
105    // You must show proof that you've already adopted the existing command.
106    template <typename T, typename Existing>
107    T* replace(unsigned i, const SkRecords::Adopted<Existing>& proofOfAdoption) {
108        SkASSERT(i < this->count());
109
110        SkASSERT(Existing::kType == fTypes[i]);
111        SkASSERT(proofOfAdoption == fRecords[i].ptr<Existing>());
112
113        fTypes[i] = T::kType;
114        return fRecords[i].set(this->allocCommand<T>());
115    }
116
117private:
118    // Implementation notes!
119    //
120    // Logically an SkRecord is structured as an array of pointers into a big chunk of memory where
121    // records representing each canvas draw call are stored:
122    //
123    // fRecords:  [*][*][*]...
124    //             |  |  |
125    //             |  |  |
126    //             |  |  +---------------------------------------+
127    //             |  +-----------------+                        |
128    //             |                    |                        |
129    //             v                    v                        v
130    //   fAlloc:  [SkRecords::DrawRect][SkRecords::DrawPosTextH][SkRecords::DrawRect]...
131    //
132    // In the scheme above, the pointers in fRecords are void*: they have no type.  The type is not
133    // stored in fAlloc either; we just write raw data there.  But we need that type information.
134    // Here are some options:
135    //   1) use inheritance, virtuals, and vtables to make the fRecords pointers smarter
136    //   2) store the type data manually in fAlloc at the start of each record
137    //   3) store the type data manually somewhere with fRecords
138    //
139    // This code uses approach 3).  The implementation feels very similar to 1), but it's
140    // devirtualized instead of using the language's polymorphism mechanisms.  This lets us work
141    // with the types themselves (as SkRecords::Type), a sort of limited free RTTI; it lets us pay
142    // only 1 byte to store the type instead of a full pointer (4-8 bytes); and it leads to better
143    // decoupling between the SkRecords::* record types and the operations performed on them in
144    // visit() or mutate().  The recorded canvas calls don't have to have any idea about the
145    // operations performed on them.
146    //
147    // We store the types in a parallel fTypes array, mainly so that they can be tightly packed as
148    // single bytes.  This has the side effect of allowing very fast analysis passes over an
149    // SkRecord looking for just patterns of draw commands (or using this as a quick reject
150    // mechanism) though there's admittedly not a very good API exposed publically for this.
151    //
152    // The cost to append a T into this structure is 1 + sizeof(void*) + sizeof(T).
153
154    // A mutator that can be used with replace to destroy canvas commands.
155    struct Destroyer {
156        template <typename T>
157        void operator()(T* record) { record->~T(); }
158    };
159
160    // Logically the same as SkRecords::Type, but packed into 8 bits.
161    struct Type8 {
162    public:
163        // This intentionally converts implicitly back and forth.
164        Type8(SkRecords::Type type) : fType(type) { SkASSERT(*this == type); }
165        operator SkRecords::Type () { return (SkRecords::Type)fType; }
166
167    private:
168        uint8_t fType;
169    };
170
171    // No point in allocating any more than one of an empty struct.
172    // We could just return NULL but it's sort of confusing to return NULL on success.
173    template <typename T>
174    SK_WHEN(SkTIsEmpty<T>, T*) allocCommand() {
175        static T singleton = {};
176        return &singleton;
177    }
178
179    template <typename T>
180    SK_WHEN(!SkTIsEmpty<T>, T*) allocCommand() { return this->alloc<T>(); }
181
182    // An untyped pointer to some bytes in fAlloc.  This is the interface for polymorphic dispatch:
183    // visit() and mutate() work with the parallel fTypes array to do the work of a vtable.
184    struct Record {
185    public:
186        // Point this record to its data in fAlloc.  Returns ptr for convenience.
187        template <typename T>
188        T* set(T* ptr) {
189            fPtr = ptr;
190            return ptr;
191        }
192
193        // Get the data in fAlloc, assuming it's of type T.
194        template <typename T>
195        T* ptr() const { return (T*)fPtr; }
196
197        // Visit this record with functor F (see public API above) assuming the record we're
198        // pointing to has this type.
199        template <typename R, typename F>
200        R visit(Type8 type, F& f) const {
201        #define CASE(T) case SkRecords::T##_Type: return f(*this->ptr<SkRecords::T>());
202            switch(type) { SK_RECORD_TYPES(CASE) }
203        #undef CASE
204            SkDEBUGFAIL("Unreachable");
205            return R();
206        }
207
208        // Mutate this record with functor F (see public API above) assuming the record we're
209        // pointing to has this type.
210        template <typename R, typename F>
211        R mutate(Type8 type, F& f) {
212        #define CASE(T) case SkRecords::T##_Type: return f(this->ptr<SkRecords::T>());
213            switch(type) { SK_RECORD_TYPES(CASE) }
214        #undef CASE
215            SkDEBUGFAIL("Unreachable");
216            return R();
217        }
218
219    private:
220        void* fPtr;
221    };
222
223    // fAlloc needs to be a data structure which can append variable length data in contiguous
224    // chunks, returning a stable handle to that data for later retrieval.
225    //
226    // fRecords and fTypes need to be data structures that can append fixed length data, and need to
227    // support efficient random access and forward iteration.  (They don't need to be contiguous.)
228
229    SkChunkAlloc fAlloc;
230    SkAutoTMalloc<Record> fRecords;
231    SkAutoTMalloc<Type8> fTypes;
232    // fCount and fReserved measure both fRecords and fTypes, which always grow in lock step.
233    unsigned fCount;
234    unsigned fReserved;
235};
236
237#endif//SkRecord_DEFINED
238