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