1/*
2 * Copyright 2011 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 SkClipStack_DEFINED
9#define SkClipStack_DEFINED
10
11#include "include/core/SkCanvas.h"
12#include "include/core/SkPath.h"
13#include "include/core/SkRRect.h"
14#include "include/core/SkRect.h"
15#include "include/core/SkRegion.h"
16#include "include/private/SkDeque.h"
17#include "src/core/SkClipOpPriv.h"
18#include "src/core/SkMessageBus.h"
19#include "src/core/SkTLazy.h"
20
21#if SK_SUPPORT_GPU
22class GrProxyProvider;
23
24#include "include/private/GrResourceKey.h"
25#endif
26
27// Because a single save/restore state can have multiple clips, this class
28// stores the stack depth (fSaveCount) and clips (fDeque) separately.
29// Each clip in fDeque stores the stack state to which it belongs
30// (i.e., the fSaveCount in force when it was added). Restores are thus
31// implemented by removing clips from fDeque that have an fSaveCount larger
32// then the freshly decremented count.
33class SkClipStack {
34public:
35 enum BoundsType {
36 // The bounding box contains all the pixels that can be written to
37 kNormal_BoundsType,
38 // The bounding box contains all the pixels that cannot be written to.
39 // The real bound extends out to infinity and all the pixels outside
40 // of the bound can be written to. Note that some of the pixels inside
41 // the bound may also be writeable but all pixels that cannot be
42 // written to are guaranteed to be inside.
43 kInsideOut_BoundsType
44 };
45
46 /**
47 * An element of the clip stack. It represents a shape combined with the prevoius clip using a
48 * set operator. Each element can be antialiased or not.
49 */
50 class Element {
51 public:
52 /** This indicates the shape type of the clip element in device space. */
53 enum class DeviceSpaceType {
54 //!< This element makes the clip empty (regardless of previous elements).
55 kEmpty,
56 //!< This element combines a device space rect with the current clip.
57 kRect,
58 //!< This element combines a device space round-rect with the current clip.
59 kRRect,
60 //!< This element combines a device space path with the current clip.
61 kPath,
62
63 kLastType = kPath
64 };
65 static const int kTypeCnt = (int)DeviceSpaceType::kLastType + 1;
66
67 Element() {
68 this->initCommon(0, kReplace_SkClipOp, false);
69 this->setEmpty();
70 }
71
72 Element(const Element&);
73
74 Element(const SkRect& rect, const SkMatrix& m, SkClipOp op, bool doAA) {
75 this->initRect(0, rect, m, op, doAA);
76 }
77
78 Element(const SkRRect& rrect, const SkMatrix& m, SkClipOp op, bool doAA) {
79 this->initRRect(0, rrect, m, op, doAA);
80 }
81
82 Element(const SkPath& path, const SkMatrix& m, SkClipOp op, bool doAA) {
83 this->initPath(0, path, m, op, doAA);
84 }
85
86 ~Element();
87
88 bool operator== (const Element& element) const;
89 bool operator!= (const Element& element) const { return !(*this == element); }
90
91 //!< Call to get the type of the clip element.
92 DeviceSpaceType getDeviceSpaceType() const { return fDeviceSpaceType; }
93
94 //!< Call to get the save count associated with this clip element.
95 int getSaveCount() const { return fSaveCount; }
96
97 //!< Call if getDeviceSpaceType() is kPath to get the path.
98 const SkPath& getDeviceSpacePath() const {
99 SkASSERT(DeviceSpaceType::kPath == fDeviceSpaceType);
100 return *fDeviceSpacePath.get();
101 }
102
103 //!< Call if getDeviceSpaceType() is kRRect to get the round-rect.
104 const SkRRect& getDeviceSpaceRRect() const {
105 SkASSERT(DeviceSpaceType::kRRect == fDeviceSpaceType);
106 return fDeviceSpaceRRect;
107 }
108
109 //!< Call if getDeviceSpaceType() is kRect to get the rect.
110 const SkRect& getDeviceSpaceRect() const {
111 SkASSERT(DeviceSpaceType::kRect == fDeviceSpaceType &&
112 (fDeviceSpaceRRect.isRect() || fDeviceSpaceRRect.isEmpty()));
113 return fDeviceSpaceRRect.getBounds();
114 }
115
116 //!< Call if getDeviceSpaceType() is not kEmpty to get the set operation used to combine
117 //!< this element.
118 SkClipOp getOp() const { return fOp; }
119
120 //!< Call to get the element as a path, regardless of its type.
121 void asDeviceSpacePath(SkPath* path) const;
122
123 //!< Call if getType() is not kPath to get the element as a round rect.
124 const SkRRect& asDeviceSpaceRRect() const {
125 SkASSERT(DeviceSpaceType::kPath != fDeviceSpaceType);
126 return fDeviceSpaceRRect;
127 }
128
129 /** If getType() is not kEmpty this indicates whether the clip shape should be anti-aliased
130 when it is rasterized. */
131 bool isAA() const { return fDoAA; }
132
133 //!< Inverts the fill of the clip shape. Note that a kEmpty element remains kEmpty.
134 void invertShapeFillType();
135
136 //!< Sets the set operation represented by the element.
137 void setOp(SkClipOp op) { fOp = op; }
138
139 /** The GenID can be used by clip stack clients to cache representations of the clip. The
140 ID corresponds to the set of clip elements up to and including this element within the
141 stack not to the element itself. That is the same clip path in different stacks will
142 have a different ID since the elements produce different clip result in the context of
143 their stacks. */
144 uint32_t getGenID() const { SkASSERT(kInvalidGenID != fGenID); return fGenID; }
145
146 /**
147 * Gets the bounds of the clip element, either the rect or path bounds. (Whether the shape
148 * is inverse filled is not considered.)
149 */
150 const SkRect& getBounds() const;
151
152 /**
153 * Conservatively checks whether the clip shape contains the rect/rrect. (Whether the shape
154 * is inverse filled is not considered.)
155 */
156 bool contains(const SkRect& rect) const;
157 bool contains(const SkRRect& rrect) const;
158
159 /**
160 * Is the clip shape inverse filled.
161 */
162 bool isInverseFilled() const {
163 return DeviceSpaceType::kPath == fDeviceSpaceType &&
164 fDeviceSpacePath.get()->isInverseFillType();
165 }
166
167#ifdef SK_DEBUG
168 /**
169 * Dumps the element to SkDebugf. This is intended for Skia development debugging
170 * Don't rely on the existence of this function or the formatting of its output.
171 */
172 void dump() const;
173#endif
174
175#if SK_SUPPORT_GPU
176 /**
177 * This is used to purge any GPU resource cache items that become unreachable when
178 * the element is destroyed because their key is based on this element's gen ID.
179 */
180 void addResourceInvalidationMessage(GrProxyProvider* proxyProvider,
181 const GrUniqueKey& key) const {
182 SkASSERT(proxyProvider);
183
184 if (!fProxyProvider) {
185 fProxyProvider = proxyProvider;
186 }
187 SkASSERT(fProxyProvider == proxyProvider);
188
189 fKeysToInvalidate.push_back(key);
190 }
191#endif
192
193 private:
194 friend class SkClipStack;
195
196 SkTLazy<SkPath> fDeviceSpacePath;
197 SkRRect fDeviceSpaceRRect;
198 int fSaveCount; // save count of stack when this element was added.
199 SkClipOp fOp;
200 DeviceSpaceType fDeviceSpaceType;
201 bool fDoAA;
202
203 /* fFiniteBoundType and fFiniteBound are used to incrementally update the clip stack's
204 bound. When fFiniteBoundType is kNormal_BoundsType, fFiniteBound represents the
205 conservative bounding box of the pixels that aren't clipped (i.e., any pixels that can be
206 drawn to are inside the bound). When fFiniteBoundType is kInsideOut_BoundsType (which
207 occurs when a clip is inverse filled), fFiniteBound represents the conservative bounding
208 box of the pixels that _are_ clipped (i.e., any pixels that cannot be drawn to are inside
209 the bound). When fFiniteBoundType is kInsideOut_BoundsType the actual bound is the
210 infinite plane. This behavior of fFiniteBoundType and fFiniteBound is required so that we
211 can capture the cancelling out of the extensions to infinity when two inverse filled
212 clips are Booleaned together. */
213 SkClipStack::BoundsType fFiniteBoundType;
214 SkRect fFiniteBound;
215
216 // When element is applied to the previous elements in the stack is the result known to be
217 // equivalent to a single rect intersection? IIOW, is the clip effectively a rectangle.
218 bool fIsIntersectionOfRects;
219
220 uint32_t fGenID;
221#if SK_SUPPORT_GPU
222 mutable GrProxyProvider* fProxyProvider = nullptr;
223 mutable SkTArray<GrUniqueKey> fKeysToInvalidate;
224#endif
225 Element(int saveCount) {
226 this->initCommon(saveCount, kReplace_SkClipOp, false);
227 this->setEmpty();
228 }
229
230 Element(int saveCount, const SkRRect& rrect, const SkMatrix& m, SkClipOp op, bool doAA) {
231 this->initRRect(saveCount, rrect, m, op, doAA);
232 }
233
234 Element(int saveCount, const SkRect& rect, const SkMatrix& m, SkClipOp op, bool doAA) {
235 this->initRect(saveCount, rect, m, op, doAA);
236 }
237
238 Element(int saveCount, const SkPath& path, const SkMatrix& m, SkClipOp op, bool doAA) {
239 this->initPath(saveCount, path, m, op, doAA);
240 }
241
242 void initCommon(int saveCount, SkClipOp op, bool doAA);
243 void initRect(int saveCount, const SkRect&, const SkMatrix&, SkClipOp, bool doAA);
244 void initRRect(int saveCount, const SkRRect&, const SkMatrix&, SkClipOp, bool doAA);
245 void initPath(int saveCount, const SkPath&, const SkMatrix&, SkClipOp, bool doAA);
246 void initAsPath(int saveCount, const SkPath&, const SkMatrix&, SkClipOp, bool doAA);
247
248 void setEmpty();
249
250 // All Element methods below are only used within SkClipStack.cpp
251 inline void checkEmpty() const;
252 inline bool canBeIntersectedInPlace(int saveCount, SkClipOp op) const;
253 /* This method checks to see if two rect clips can be safely merged into one. The issue here
254 is that to be strictly correct all the edges of the resulting rect must have the same
255 anti-aliasing. */
256 bool rectRectIntersectAllowed(const SkRect& newR, bool newAA) const;
257 /** Determines possible finite bounds for the Element given the previous element of the
258 stack */
259 void updateBoundAndGenID(const Element* prior);
260 // The different combination of fill & inverse fill when combining bounding boxes
261 enum FillCombo {
262 kPrev_Cur_FillCombo,
263 kPrev_InvCur_FillCombo,
264 kInvPrev_Cur_FillCombo,
265 kInvPrev_InvCur_FillCombo
266 };
267 // per-set operation functions used by updateBoundAndGenID().
268 inline void combineBoundsDiff(FillCombo combination, const SkRect& prevFinite);
269 inline void combineBoundsXOR(int combination, const SkRect& prevFinite);
270 inline void combineBoundsUnion(int combination, const SkRect& prevFinite);
271 inline void combineBoundsIntersection(int combination, const SkRect& prevFinite);
272 inline void combineBoundsRevDiff(int combination, const SkRect& prevFinite);
273 };
274
275 SkClipStack();
276 SkClipStack(void* storage, size_t size);
277 SkClipStack(const SkClipStack& b);
278 ~SkClipStack();
279
280 SkClipStack& operator=(const SkClipStack& b);
281 bool operator==(const SkClipStack& b) const;
282 bool operator!=(const SkClipStack& b) const { return !(*this == b); }
283
284 void reset();
285
286 int getSaveCount() const { return fSaveCount; }
287 void save();
288 void restore();
289
290 class AutoRestore {
291 public:
292 AutoRestore(SkClipStack* cs, bool doSave)
293 : fCS(cs), fSaveCount(cs->getSaveCount())
294 {
295 if (doSave) {
296 fCS->save();
297 }
298 }
299 ~AutoRestore() {
300 SkASSERT(fCS->getSaveCount() >= fSaveCount); // no underflow
301 while (fCS->getSaveCount() > fSaveCount) {
302 fCS->restore();
303 }
304 }
305
306 private:
307 SkClipStack* fCS;
308 const int fSaveCount;
309 };
310
311 /**
312 * getBounds places the current finite bound in its first parameter. In its
313 * second, it indicates which kind of bound is being returned. If
314 * 'canvFiniteBound' is a normal bounding box then it encloses all writeable
315 * pixels. If 'canvFiniteBound' is an inside out bounding box then it
316 * encloses all the un-writeable pixels and the true/normal bound is the
317 * infinite plane. isIntersectionOfRects is an optional parameter
318 * that is true if 'canvFiniteBound' resulted from an intersection of rects.
319 */
320 void getBounds(SkRect* canvFiniteBound,
321 BoundsType* boundType,
322 bool* isIntersectionOfRects = nullptr) const;
323
324 SkRect bounds(const SkIRect& deviceBounds) const;
325 bool isEmpty(const SkIRect& deviceBounds) const;
326
327 /**
328 * Returns true if the input (r)rect in device space is entirely contained
329 * by the clip. A return value of false does not guarantee that the (r)rect
330 * is not contained by the clip.
331 */
332 bool quickContains(const SkRect& devRect) const {
333 return this->isWideOpen() || this->internalQuickContains(devRect);
334 }
335
336 bool quickContains(const SkRRect& devRRect) const {
337 return this->isWideOpen() || this->internalQuickContains(devRRect);
338 }
339
340 void clipDevRect(const SkIRect& ir, SkClipOp op) {
341 SkRect r;
342 r.set(ir);
343 this->clipRect(r, SkMatrix::I(), op, false);
344 }
345 void clipRect(const SkRect&, const SkMatrix& matrix, SkClipOp, bool doAA);
346 void clipRRect(const SkRRect&, const SkMatrix& matrix, SkClipOp, bool doAA);
347 void clipPath(const SkPath&, const SkMatrix& matrix, SkClipOp, bool doAA);
348 // An optimized version of clipDevRect(emptyRect, kIntersect, ...)
349 void clipEmpty();
350 void setDeviceClipRestriction(const SkIRect& rect) {
351 fClipRestrictionRect = SkRect::Make(rect);
352 }
353
354 /**
355 * isWideOpen returns true if the clip state corresponds to the infinite
356 * plane (i.e., draws are not limited at all)
357 */
358 bool isWideOpen() const { return this->getTopmostGenID() == kWideOpenGenID; }
359
360 /**
361 * This method quickly and conservatively determines whether the entire stack is equivalent to
362 * intersection with a rrect given a bounds, where the rrect must not contain the entire bounds.
363 *
364 * @param bounds A bounds on what will be drawn through the clip. The clip only need be
365 * equivalent to a intersection with a rrect for draws within the bounds. The
366 * returned rrect must intersect the bounds but need not be contained by the
367 * bounds.
368 * @param rrect If return is true rrect will contain the rrect equivalent to the stack.
369 * @param aa If return is true aa will indicate whether the equivalent rrect clip is
370 * antialiased.
371 * @return true if the stack is equivalent to a single rrect intersect clip, false otherwise.
372 */
373 bool isRRect(const SkRect& bounds, SkRRect* rrect, bool* aa) const;
374
375 /**
376 * The generation ID has three reserved values to indicate special
377 * (potentially ignorable) cases
378 */
379 static const uint32_t kInvalidGenID = 0; //!< Invalid id that is never returned by
380 //!< SkClipStack. Useful when caching clips
381 //!< based on GenID.
382 static const uint32_t kEmptyGenID = 1; // no pixels writeable
383 static const uint32_t kWideOpenGenID = 2; // all pixels writeable
384
385 uint32_t getTopmostGenID() const;
386
387#ifdef SK_DEBUG
388 /**
389 * Dumps the contents of the clip stack to SkDebugf. This is intended for Skia development
390 * debugging. Don't rely on the existence of this function or the formatting of its output.
391 */
392 void dump() const;
393#endif
394
395public:
396 class Iter {
397 public:
398 enum IterStart {
399 kBottom_IterStart = SkDeque::Iter::kFront_IterStart,
400 kTop_IterStart = SkDeque::Iter::kBack_IterStart
401 };
402
403 /**
404 * Creates an uninitialized iterator. Must be reset()
405 */
406 Iter();
407
408 Iter(const SkClipStack& stack, IterStart startLoc);
409
410 /**
411 * Return the clip element for this iterator. If next()/prev() returns NULL, then the
412 * iterator is done.
413 */
414 const Element* next();
415 const Element* prev();
416
417 /**
418 * Moves the iterator to the topmost element with the specified RegionOp and returns that
419 * element. If no clip element with that op is found, the first element is returned.
420 */
421 const Element* skipToTopmost(SkClipOp op);
422
423 /**
424 * Restarts the iterator on a clip stack.
425 */
426 void reset(const SkClipStack& stack, IterStart startLoc);
427
428 private:
429 const SkClipStack* fStack;
430 SkDeque::Iter fIter;
431 };
432
433 /**
434 * The B2TIter iterates from the bottom of the stack to the top.
435 * It inherits privately from Iter to prevent access to reverse iteration.
436 */
437 class B2TIter : private Iter {
438 public:
439 B2TIter() {}
440
441 /**
442 * Wrap Iter's 2 parameter ctor to force initialization to the
443 * beginning of the deque/bottom of the stack
444 */
445 B2TIter(const SkClipStack& stack)
446 : INHERITED(stack, kBottom_IterStart) {
447 }
448
449 using Iter::next;
450
451 /**
452 * Wrap Iter::reset to force initialization to the
453 * beginning of the deque/bottom of the stack
454 */
455 void reset(const SkClipStack& stack) {
456 this->INHERITED::reset(stack, kBottom_IterStart);
457 }
458
459 private:
460
461 typedef Iter INHERITED;
462 };
463
464 /**
465 * GetConservativeBounds returns a conservative bound of the current clip.
466 * Since this could be the infinite plane (if inverse fills were involved) the
467 * maxWidth and maxHeight parameters can be used to limit the returned bound
468 * to the expected drawing area. Similarly, the offsetX and offsetY parameters
469 * allow the caller to offset the returned bound to account for translated
470 * drawing areas (i.e., those resulting from a saveLayer). For finite bounds,
471 * the translation (+offsetX, +offsetY) is applied before the clamp to the
472 * maximum rectangle: [0,maxWidth) x [0,maxHeight).
473 * isIntersectionOfRects is an optional parameter that is true when
474 * 'devBounds' is the result of an intersection of rects. In this case
475 * 'devBounds' is the exact answer/clip.
476 */
477 void getConservativeBounds(int offsetX,
478 int offsetY,
479 int maxWidth,
480 int maxHeight,
481 SkRect* devBounds,
482 bool* isIntersectionOfRects = nullptr) const;
483
484private:
485 friend class Iter;
486
487 SkDeque fDeque;
488 int fSaveCount;
489
490 SkRect fClipRestrictionRect = SkRect::MakeEmpty();
491
492 bool internalQuickContains(const SkRect& devRect) const;
493 bool internalQuickContains(const SkRRect& devRRect) const;
494
495 /**
496 * Helper for clipDevPath, etc.
497 */
498 void pushElement(const Element& element);
499
500 /**
501 * Restore the stack back to the specified save count.
502 */
503 void restoreTo(int saveCount);
504
505 inline bool hasClipRestriction(SkClipOp op) {
506 return op >= kUnion_SkClipOp && !fClipRestrictionRect.isEmpty();
507 }
508
509 /**
510 * Return the next unique generation ID.
511 */
512 static uint32_t GetNextGenID();
513};
514
515#endif
516
517