1/*
2 * Copyright (C) 2010, 2011 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#ifndef Region_h
27#define Region_h
28
29#include "IntRect.h"
30#include <wtf/Optional.h>
31#include <wtf/PointerComparison.h>
32#include <wtf/Vector.h>
33
34namespace WebCore {
35
36class Region {
37 WTF_MAKE_FAST_ALLOCATED;
38
39public:
40 WEBCORE_EXPORT Region();
41 WEBCORE_EXPORT Region(const IntRect&);
42
43 WEBCORE_EXPORT Region(const Region&);
44 WEBCORE_EXPORT Region(Region&&);
45
46 WEBCORE_EXPORT ~Region();
47
48 WEBCORE_EXPORT Region& operator=(const Region&);
49 WEBCORE_EXPORT Region& operator=(Region&&);
50
51 IntRect bounds() const { return m_bounds; }
52 bool isEmpty() const { return m_bounds.isEmpty(); }
53 bool isRect() const { return !m_shape; }
54
55 WEBCORE_EXPORT Vector<IntRect, 1> rects() const;
56
57 WEBCORE_EXPORT void unite(const Region&);
58 WEBCORE_EXPORT void intersect(const Region&);
59 WEBCORE_EXPORT void subtract(const Region&);
60
61 WEBCORE_EXPORT void translate(const IntSize&);
62
63 // Returns true if the query region is a subset of this region.
64 WEBCORE_EXPORT bool contains(const Region&) const;
65
66 WEBCORE_EXPORT bool contains(const IntPoint&) const;
67
68 // Returns true if the query region intersects any part of this region.
69 WEBCORE_EXPORT bool intersects(const Region&) const;
70
71 WEBCORE_EXPORT uint64_t totalArea() const;
72
73 unsigned gridSize() const { return m_shape ? m_shape->gridSize() : 0; }
74
75#ifndef NDEBUG
76 void dump() const;
77#endif
78
79 template<class Encoder> void encode(Encoder&) const;
80 template<class Decoder> static Optional<Region> decode(Decoder&);
81 // FIXME: Remove legacy decode.
82 template<class Decoder> static bool decode(Decoder&, Region&);
83
84private:
85 struct Span {
86 int y { 0 };
87 size_t segmentIndex { 0 };
88
89 template<class Encoder> void encode(Encoder&) const;
90 template<class Decoder> static Optional<Span> decode(Decoder&);
91 };
92
93 class Shape {
94 public:
95 Shape() = default;
96 Shape(const IntRect&);
97
98 IntRect bounds() const;
99 bool isEmpty() const { return m_spans.isEmpty(); }
100 bool isRect() const { return m_spans.size() <= 2 && m_segments.size() <= 2; }
101 unsigned gridSize() const { return m_spans.size() * m_segments.size(); }
102
103 typedef const Span* SpanIterator;
104 SpanIterator spans_begin() const;
105 SpanIterator spans_end() const;
106
107 typedef const int* SegmentIterator;
108 SegmentIterator segments_begin(SpanIterator) const;
109 SegmentIterator segments_end(SpanIterator) const;
110
111 static Shape unionShapes(const Shape& shape1, const Shape& shape2);
112 static Shape intersectShapes(const Shape& shape1, const Shape& shape2);
113 static Shape subtractShapes(const Shape& shape1, const Shape& shape2);
114
115 WEBCORE_EXPORT void translate(const IntSize&);
116
117 struct CompareContainsOperation;
118 struct CompareIntersectsOperation;
119
120 template<typename CompareOperation>
121 static bool compareShapes(const Shape& shape1, const Shape& shape2);
122
123 template<class Encoder> void encode(Encoder&) const;
124 template<class Decoder> static Optional<Shape> decode(Decoder&);
125
126#ifndef NDEBUG
127 void dump() const;
128#endif
129
130 private:
131 struct UnionOperation;
132 struct IntersectOperation;
133 struct SubtractOperation;
134
135 template<typename Operation>
136 static Shape shapeOperation(const Shape& shape1, const Shape& shape2);
137
138 void appendSegment(int x);
139 void appendSpan(int y);
140 void appendSpan(int y, SegmentIterator begin, SegmentIterator end);
141 void appendSpans(const Shape&, SpanIterator begin, SpanIterator end);
142
143 bool canCoalesce(SegmentIterator begin, SegmentIterator end);
144
145 Vector<int, 32> m_segments;
146 Vector<Span, 16> m_spans;
147
148 friend bool operator==(const Shape&, const Shape&);
149 };
150
151 std::unique_ptr<Shape> copyShape() const { return m_shape ? std::make_unique<Shape>(*m_shape) : nullptr; }
152 void setShape(Shape&&);
153
154 IntRect m_bounds;
155 std::unique_ptr<Shape> m_shape;
156
157 friend bool operator==(const Region&, const Region&);
158 friend bool operator==(const Shape&, const Shape&);
159 friend bool operator==(const Span&, const Span&);
160 friend bool operator!=(const Span&, const Span&);
161};
162
163static inline Region intersect(const Region& a, const Region& b)
164{
165 Region result(a);
166 result.intersect(b);
167
168 return result;
169}
170
171static inline Region subtract(const Region& a, const Region& b)
172{
173 Region result(a);
174 result.subtract(b);
175
176 return result;
177}
178
179static inline Region translate(const Region& region, const IntSize& offset)
180{
181 Region result(region);
182 result.translate(offset);
183
184 return result;
185}
186
187inline bool operator==(const Region& a, const Region& b)
188{
189 return a.m_bounds == b.m_bounds && arePointingToEqualData(a.m_shape, b.m_shape);
190}
191inline bool operator!=(const Region& a, const Region& b)
192{
193 return !(a == b);
194}
195
196inline bool operator==(const Region::Shape& a, const Region::Shape& b)
197{
198 return a.m_spans == b.m_spans && a.m_segments == b.m_segments;
199}
200
201inline bool operator==(const Region::Span& a, const Region::Span& b)
202{
203 return a.y == b.y && a.segmentIndex == b.segmentIndex;
204}
205
206inline bool operator!=(const Region::Span& a, const Region::Span& b)
207{
208 return !(a == b);
209}
210
211WEBCORE_EXPORT WTF::TextStream& operator<<(WTF::TextStream&, const Region&);
212
213template<class Encoder>
214void Region::Span::encode(Encoder& encoder) const
215{
216 encoder << y << static_cast<uint64_t>(segmentIndex);
217}
218
219template<class Decoder>
220Optional<Region::Span> Region::Span::decode(Decoder& decoder)
221{
222 Optional<int> y;
223 decoder >> y;
224 if (!y)
225 return { };
226
227 Optional<uint64_t> segmentIndex;
228 decoder >> segmentIndex;
229 if (!segmentIndex)
230 return { };
231
232 return { { *y, static_cast<size_t>(*segmentIndex) } };
233}
234
235template<class Encoder>
236void Region::Shape::encode(Encoder& encoder) const
237{
238 encoder << m_segments;
239 encoder << m_spans;
240}
241
242template<class Decoder>
243Optional<Region::Shape> Region::Shape::decode(Decoder& decoder)
244{
245 Optional<Vector<int>> segments;
246 decoder >> segments;
247 if (!segments)
248 return WTF::nullopt;
249
250 Optional<Vector<Region::Span>> spans;
251 decoder >> spans;
252 if (!spans)
253 return WTF::nullopt;
254
255 Shape shape;
256 shape.m_segments = WTFMove(*segments);
257 shape.m_spans = WTFMove(*spans);
258
259 return { shape };
260}
261
262template<class Encoder>
263void Region::encode(Encoder& encoder) const
264{
265 encoder << m_bounds;
266 bool hasShape = !!m_shape;
267 encoder << hasShape;
268 if (hasShape)
269 encoder << *m_shape;
270}
271
272template<class Decoder>
273Optional<Region> Region::decode(Decoder& decoder)
274{
275 Optional<IntRect> bounds;
276 decoder >> bounds;
277 if (!bounds)
278 return WTF::nullopt;
279
280 Optional<bool> hasShape;
281 decoder >> hasShape;
282 if (!hasShape)
283 return WTF::nullopt;
284
285 Region region = { *bounds };
286
287 if (*hasShape) {
288 Optional<Shape> shape;
289 decoder >> shape;
290 if (!shape)
291 return WTF::nullopt;
292 region.m_shape = std::make_unique<Shape>(WTFMove(*shape));
293 }
294
295 return { region };
296}
297
298template<class Decoder>
299bool Region::decode(Decoder& decoder, Region& region)
300{
301 Optional<Region> decodedRegion;
302 decoder >> decodedRegion;
303 if (!decodedRegion)
304 return false;
305 region = WTFMove(*decodedRegion);
306 return true;
307}
308
309} // namespace WebCore
310
311#endif // Region_h
312