Combine event and touch action regions into a single class
[WebKit-https.git] / Source / WebCore / platform / graphics / Region.cpp
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 #include "config.h"
27 #include "Region.h"
28
29 #include <stdio.h>
30 #include <wtf/text/TextStream.h>
31
32 // A region class based on the paper "Scanline Coherent Shape Algebra"
33 // by Jonathan E. Steinhart from the book "Graphics Gems II".
34 //
35 // This implementation uses two vectors instead of linked list, and
36 // also compresses regions when possible.
37
38 namespace WebCore {
39
40 Region::Region()
41 {
42 }
43
44 Region::Region(const IntRect& rect)
45     : m_bounds(rect)
46 {
47 }
48
49 Region::Region(const Region& other)
50     : m_bounds(other.m_bounds)
51     , m_shape(other.copyShape())
52 {
53 }
54
55 Region::Region(Region&& other)
56     : m_bounds(WTFMove(other.m_bounds))
57     , m_shape(WTFMove(other.m_shape))
58 {
59 }
60
61 Region::~Region()
62 {
63 }
64
65 Region& Region::operator=(const Region& other)
66 {
67     m_bounds = other.m_bounds;
68     m_shape = other.copyShape();
69     return *this;
70 }
71
72 Region& Region::operator=(Region&& other)
73 {
74     m_bounds = WTFMove(other.m_bounds);
75     m_shape = WTFMove(other.m_shape);
76     return *this;
77 }
78
79 Vector<IntRect, 1> Region::rects() const
80 {
81     Vector<IntRect, 1> rects;
82
83     if (!m_shape) {
84         if (!m_bounds.isEmpty())
85             rects.uncheckedAppend(m_bounds);
86         return rects;
87     }
88
89     for (Shape::SpanIterator span = m_shape->spans_begin(), end = m_shape->spans_end(); span != end && span + 1 != end; ++span) {
90         int y = span->y;
91         int height = (span + 1)->y - y;
92
93         for (Shape::SegmentIterator segment = m_shape->segments_begin(span), end = m_shape->segments_end(span); segment != end && segment + 1 != end; segment += 2) {
94             int x = *segment;
95             int width = *(segment + 1) - x;
96
97             rects.append(IntRect(x, y, width, height));
98         }
99     }
100
101     return rects;
102 }
103
104 bool Region::contains(const Region& region) const
105 {
106     if (!m_bounds.contains(region.m_bounds))
107         return false;
108
109     if (!m_shape)
110         return true;
111
112     return Shape::compareShapes<Shape::CompareContainsOperation>(*m_shape, region.m_shape ? *region.m_shape : Shape(region.m_bounds));
113 }
114
115 bool Region::contains(const IntPoint& point) const
116 {
117     if (!m_bounds.contains(point))
118         return false;
119
120     if (!m_shape)
121         return true;
122
123     for (Shape::SpanIterator span = m_shape->spans_begin(), end = m_shape->spans_end(); span != end && span + 1 != end; ++span) {
124         int y = span->y;
125         int maxY = (span + 1)->y;
126
127         if (y > point.y())
128             break;
129         if (maxY <= point.y())
130             continue;
131
132         for (Shape::SegmentIterator segment = m_shape->segments_begin(span), end = m_shape->segments_end(span); segment != end && segment + 1 != end; segment += 2) {
133             int x = *segment;
134             int maxX = *(segment + 1);
135
136             if (x > point.x())
137                 break;
138             if (maxX > point.x())
139                 return true;
140         }
141     }
142
143     return false;
144 }
145
146 bool Region::intersects(const Region& region) const
147 {
148     if (!m_bounds.intersects(region.m_bounds))
149         return false;
150
151     if (!m_shape && !region.m_shape)
152         return true;
153
154     return Shape::compareShapes<Shape::CompareIntersectsOperation>(m_shape ? *m_shape : m_bounds, region.m_shape ? *region.m_shape : region.m_bounds);
155 }
156
157 uint64_t Region::totalArea() const
158 {
159     uint64_t totalArea = 0;
160
161     for (auto& rect : rects())
162         totalArea += (rect.width() * rect.height());
163
164     return totalArea;
165 }
166
167 template<typename CompareOperation>
168 bool Region::Shape::compareShapes(const Shape& aShape, const Shape& bShape)
169 {
170     bool result = CompareOperation::defaultResult;
171
172     Shape::SpanIterator aSpan = aShape.spans_begin();
173     Shape::SpanIterator aSpanEnd = aShape.spans_end();
174     Shape::SpanIterator bSpan = bShape.spans_begin();
175     Shape::SpanIterator bSpanEnd = bShape.spans_end();
176
177     bool aHadSegmentInPreviousSpan = false;
178     bool bHadSegmentInPreviousSpan = false;
179     while (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && bSpan != bSpanEnd && bSpan + 1 != bSpanEnd) {
180         int aY = aSpan->y;
181         int aMaxY = (aSpan + 1)->y;
182         int bY = bSpan->y;
183         int bMaxY = (bSpan + 1)->y;
184
185         Shape::SegmentIterator aSegment = aShape.segments_begin(aSpan);
186         Shape::SegmentIterator aSegmentEnd = aShape.segments_end(aSpan);
187         Shape::SegmentIterator bSegment = bShape.segments_begin(bSpan);
188         Shape::SegmentIterator bSegmentEnd = bShape.segments_end(bSpan);
189
190         // Look for a non-overlapping part of the spans. If B had a segment in its previous span, then we already tested A against B within that span.
191         bool aHasSegmentInSpan = aSegment != aSegmentEnd;
192         bool bHasSegmentInSpan = bSegment != bSegmentEnd;
193         if (aY < bY && !bHadSegmentInPreviousSpan && aHasSegmentInSpan && CompareOperation::aOutsideB(result))
194             return result;
195         if (bY < aY && !aHadSegmentInPreviousSpan && bHasSegmentInSpan && CompareOperation::bOutsideA(result))
196             return result;
197
198         aHadSegmentInPreviousSpan = aHasSegmentInSpan;
199         bHadSegmentInPreviousSpan = bHasSegmentInSpan;
200
201         bool spansOverlap = bMaxY > aY && bY < aMaxY;
202         if (spansOverlap) {
203             while (aSegment != aSegmentEnd && bSegment != bSegmentEnd) {
204                 int aX = *aSegment;
205                 int aMaxX = *(aSegment + 1);
206                 int bX = *bSegment;
207                 int bMaxX = *(bSegment + 1);
208
209                 bool segmentsOverlap = bMaxX > aX && bX < aMaxX;
210                 if (segmentsOverlap && CompareOperation::aOverlapsB(result))
211                     return result;
212                 if (aX < bX && CompareOperation::aOutsideB(result))
213                     return result;
214                 if (bX < aX && CompareOperation::bOutsideA(result))
215                     return result;
216
217                 if (aMaxX < bMaxX)
218                     aSegment += 2;
219                 else if (bMaxX < aMaxX)
220                     bSegment += 2;
221                 else {
222                     aSegment += 2;
223                     bSegment += 2;
224                 }
225             }
226
227             if (aSegment != aSegmentEnd && CompareOperation::aOutsideB(result))
228                 return result;
229             if (bSegment != bSegmentEnd && CompareOperation::bOutsideA(result))
230                 return result;
231         }
232
233         if (aMaxY < bMaxY)
234             aSpan += 1;
235         else if (bMaxY < aMaxY)
236             bSpan += 1;
237         else {
238             aSpan += 1;
239             bSpan += 1;
240         }
241     }
242
243     if (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && CompareOperation::aOutsideB(result))
244         return result;
245     if (bSpan != bSpanEnd && bSpan + 1 != bSpanEnd && CompareOperation::bOutsideA(result))
246         return result;
247
248     return result;
249 }
250
251 struct Region::Shape::CompareContainsOperation {
252     const static bool defaultResult = true;
253     inline static bool aOutsideB(bool& /* result */) { return false; }
254     inline static bool bOutsideA(bool& result) { result = false; return true; }
255     inline static bool aOverlapsB(bool& /* result */) { return false; }
256 };
257
258 struct Region::Shape::CompareIntersectsOperation {
259     const static bool defaultResult = false;
260     inline static bool aOutsideB(bool& /* result */) { return false; }
261     inline static bool bOutsideA(bool& /* result */) { return false; }
262     inline static bool aOverlapsB(bool& result) { result = true; return true; }
263 };
264
265 Region::Shape::Shape(const IntRect& rect)
266     : m_segments({ rect.x(), rect.maxX() })
267     , m_spans({ { rect.y(), 0 }, { rect.maxY(), 2 } })
268 {
269 }
270
271 void Region::Shape::appendSpan(int y)
272 {
273     m_spans.append({ y, m_segments.size() });
274 }
275
276 bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end)
277 {
278     if (m_spans.isEmpty())
279         return false;
280
281     SegmentIterator lastSpanBegin = m_segments.data() + m_spans.last().segmentIndex;
282     SegmentIterator lastSpanEnd = m_segments.data() + m_segments.size();
283
284     // Check if both spans have an equal number of segments.
285     if (lastSpanEnd - lastSpanBegin != end - begin)
286         return false;
287
288     // Check if both spans are equal.
289     if (!std::equal(begin, end, lastSpanBegin))
290         return false;
291
292     // Since the segments are equal the second segment can just be ignored.
293     return true;
294 }
295
296 void Region::Shape::appendSpan(int y, SegmentIterator begin, SegmentIterator end)
297 {
298     if (canCoalesce(begin, end))
299         return;
300   
301     appendSpan(y);
302     m_segments.appendRange(begin, end);
303 }
304
305 void Region::Shape::appendSpans(const Shape& shape, SpanIterator begin, SpanIterator end)
306 {
307     for (SpanIterator it = begin; it != end; ++it)
308         appendSpan(it->y, shape.segments_begin(it), shape.segments_end(it));
309 }
310
311 void Region::Shape::appendSegment(int x)
312 {
313     m_segments.append(x);
314 }
315
316 Region::Shape::SpanIterator Region::Shape::spans_begin() const
317 {
318     return m_spans.data();
319 }
320
321 Region::Shape::SpanIterator Region::Shape::spans_end() const
322 {
323     return m_spans.data() + m_spans.size();
324 }
325
326 Region::Shape::SegmentIterator Region::Shape::segments_begin(SpanIterator it) const
327 {
328     ASSERT(it >= m_spans.data());
329     ASSERT(it < m_spans.data() + m_spans.size());
330
331     // Check if this span has any segments.
332     if (it->segmentIndex == m_segments.size())
333         return 0;
334
335     return &m_segments[it->segmentIndex];
336 }
337
338 Region::Shape::SegmentIterator Region::Shape::segments_end(SpanIterator it) const
339 {
340     ASSERT(it >= m_spans.data());
341     ASSERT(it < m_spans.data() + m_spans.size());
342
343     // Check if this span has any segments.
344     if (it->segmentIndex == m_segments.size())
345         return 0;
346
347     ASSERT(it + 1 < m_spans.data() + m_spans.size());
348     size_t segmentIndex = (it + 1)->segmentIndex;
349
350     ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size());
351     return m_segments.data() + segmentIndex;
352 }
353
354 #ifndef NDEBUG
355 void Region::Shape::dump() const
356 {
357     for (auto span = spans_begin(), end = spans_end(); span != end; ++span) {
358         printf("%6d: (", span->y);
359
360         for (auto segment = segments_begin(span), end = segments_end(span); segment != end; ++segment)
361             printf("%d ", *segment);
362         printf(")\n");
363     }
364
365     printf("\n");
366 }
367 #endif
368
369 IntRect Region::Shape::bounds() const
370 {
371     if (isEmpty())
372         return IntRect();
373
374     SpanIterator span = spans_begin();
375     int minY = span->y;
376
377     SpanIterator lastSpan = spans_end() - 1;
378     int maxY = lastSpan->y;
379
380     int minX = std::numeric_limits<int>::max();
381     int maxX = std::numeric_limits<int>::min();
382
383     while (span != lastSpan) {
384         SegmentIterator firstSegment = segments_begin(span);
385         SegmentIterator lastSegment = segments_end(span) - 1;
386
387         if (firstSegment && lastSegment) {
388             ASSERT(firstSegment != lastSegment);
389
390             if (*firstSegment < minX)
391                 minX = *firstSegment;
392
393             if (*lastSegment > maxX)
394                 maxX = *lastSegment;
395         }
396
397         ++span;
398     }
399
400     ASSERT(minX <= maxX);
401     ASSERT(minY <= maxY);
402
403     return IntRect(minX, minY, maxX - minX, maxY - minY);
404 }
405
406 void Region::Shape::translate(const IntSize& offset)
407 {
408     for (size_t i = 0; i < m_segments.size(); ++i)
409         m_segments[i] += offset.width();
410     for (size_t i = 0; i < m_spans.size(); ++i)
411         m_spans[i].y += offset.height();
412 }
413
414 enum {
415     Shape1,
416     Shape2,
417 };
418
419 template<typename Operation>
420 Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2)
421 {
422     COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination);
423     COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination);
424
425     Shape result;
426     if (Operation::trySimpleOperation(shape1, shape2, result))
427         return result;
428
429     SpanIterator spans1 = shape1.spans_begin();
430     SpanIterator spans1End = shape1.spans_end();
431
432     SpanIterator spans2 = shape2.spans_begin();
433     SpanIterator spans2End = shape2.spans_end();
434
435     SegmentIterator segments1 = 0;
436     SegmentIterator segments1End = 0;
437
438     SegmentIterator segments2 = 0;
439     SegmentIterator segments2End = 0;
440
441     // Iterate over all spans.
442     while (spans1 != spans1End && spans2 != spans2End) {
443         int y = 0;
444         int test = spans1->y - spans2->y;
445
446         if (test <= 0) {
447             y = spans1->y;
448
449             segments1 = shape1.segments_begin(spans1);
450             segments1End = shape1.segments_end(spans1);
451             ++spans1;
452         }
453         if (test >= 0) {
454             y = spans2->y;
455
456             segments2 = shape2.segments_begin(spans2);
457             segments2End = shape2.segments_end(spans2);
458             ++spans2;
459         }
460
461         int flag = 0;
462         int oldFlag = 0;
463
464         SegmentIterator s1 = segments1;
465         SegmentIterator s2 = segments2;
466
467         Vector<int, 32> segments;
468
469         // Now iterate over the segments in each span and construct a new vector of segments.
470         while (s1 != segments1End && s2 != segments2End) {
471             int test = *s1 - *s2;
472             int x;
473
474             if (test <= 0) {
475                 x = *s1;
476                 flag = flag ^ 1;
477                 ++s1;
478             }
479             if (test >= 0) {
480                 x = *s2;
481                 flag = flag ^ 2;
482                 ++s2;
483             }
484
485             if (flag == Operation::opCode || oldFlag == Operation::opCode)
486                 segments.append(x);
487             
488             oldFlag = flag;
489         }
490
491         // Add any remaining segments.
492         if (Operation::shouldAddRemainingSegmentsFromSpan1 && s1 != segments1End)
493             segments.appendRange(s1, segments1End);
494         else if (Operation::shouldAddRemainingSegmentsFromSpan2 && s2 != segments2End)
495             segments.appendRange(s2, segments2End);
496
497         // Add the span.
498         if (!segments.isEmpty() || !result.isEmpty())
499             result.appendSpan(y, segments.data(), segments.data() + segments.size());
500     }
501
502     // Add any remaining spans.
503     if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End)
504         result.appendSpans(shape1, spans1, spans1End);
505     else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End)
506         result.appendSpans(shape2, spans2, spans2End);
507
508     return result;
509 }
510
511 struct Region::Shape::UnionOperation {
512     static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result)
513     {
514         if (shape1.isEmpty()) {
515             result = shape2;
516             return true;
517         }
518         
519         return false;
520     }
521
522     static const int opCode = 0;
523
524     static const bool shouldAddRemainingSegmentsFromSpan1 = true;
525     static const bool shouldAddRemainingSegmentsFromSpan2 = true;
526     static const bool shouldAddRemainingSpansFromShape1 = true;
527     static const bool shouldAddRemainingSpansFromShape2 = true;
528 };
529
530 Region::Shape Region::Shape::unionShapes(const Shape& shape1, const Shape& shape2)
531 {
532     return shapeOperation<UnionOperation>(shape1, shape2);
533 }
534
535 struct Region::Shape::IntersectOperation {
536     static bool trySimpleOperation(const Shape&, const Shape&, Shape&)
537     {
538         return false;
539     }
540     
541     static const int opCode = 3;
542     
543     static const bool shouldAddRemainingSegmentsFromSpan1 = false;
544     static const bool shouldAddRemainingSegmentsFromSpan2 = false;
545     static const bool shouldAddRemainingSpansFromShape1 = false;
546     static const bool shouldAddRemainingSpansFromShape2 = false;
547 };
548
549 Region::Shape Region::Shape::intersectShapes(const Shape& shape1, const Shape& shape2)
550 {
551     return shapeOperation<IntersectOperation>(shape1, shape2);
552 }
553
554 struct Region::Shape::SubtractOperation {
555     static bool trySimpleOperation(const Shape&, const Shape&, Region::Shape&)
556     {
557         return false;
558     }
559     
560     static const int opCode = 1;
561     
562     static const bool shouldAddRemainingSegmentsFromSpan1 = true;
563     static const bool shouldAddRemainingSegmentsFromSpan2 = false;
564     static const bool shouldAddRemainingSpansFromShape1 = true;
565     static const bool shouldAddRemainingSpansFromShape2 = false;
566 };
567
568 Region::Shape Region::Shape::subtractShapes(const Shape& shape1, const Shape& shape2)
569 {
570     return shapeOperation<SubtractOperation>(shape1, shape2);
571 }
572
573 #ifndef NDEBUG
574 void Region::dump() const
575 {
576     printf("Bounds: (%d, %d, %d, %d)\n",
577            m_bounds.x(), m_bounds.y(), m_bounds.width(), m_bounds.height());
578     if (m_shape)
579         m_shape->dump();
580 }
581 #endif
582
583 void Region::intersect(const Region& region)
584 {
585     if (m_bounds.isEmpty())
586         return;
587     if (!m_bounds.intersects(region.m_bounds)) {
588         m_shape = nullptr;
589         m_bounds = IntRect();
590         return;
591     }
592     if (!m_shape && !region.m_shape) {
593         m_bounds = intersection(m_bounds, region.m_bounds);
594         return;
595     }
596
597     setShape(Shape::intersectShapes(m_shape ? *m_shape : m_bounds, region.m_shape ? *region.m_shape : region.m_bounds));
598 }
599
600 void Region::unite(const Region& region)
601 {
602     if (region.isEmpty())
603         return;
604     if (isEmpty()) {
605         m_bounds = region.m_bounds;
606         m_shape = region.copyShape();
607         return;
608     }
609     if (region.isRect() && region.m_bounds.contains(m_bounds)) {
610         m_bounds = region.m_bounds;
611         m_shape = nullptr;
612         return;
613     }
614     if (contains(region))
615         return;
616
617     setShape(Shape::unionShapes(m_shape ? *m_shape : m_bounds, region.m_shape ? *region.m_shape : region.m_bounds));
618 }
619
620 void Region::subtract(const Region& region)
621 {
622     if (isEmpty())
623         return;
624     if (region.isEmpty())
625         return;
626     if (!m_bounds.intersects(region.m_bounds))
627         return;
628
629     setShape(Shape::subtractShapes(m_shape ? *m_shape : m_bounds, region.m_shape ? *region.m_shape : region.m_bounds));
630 }
631
632 void Region::translate(const IntSize& offset)
633 {
634     m_bounds.move(offset);
635     if (m_shape)
636         m_shape->translate(offset);
637 }
638
639 void Region::setShape(Shape&& shape)
640 {
641     m_bounds = shape.bounds();
642
643     if (shape.isRect()) {
644         m_shape = nullptr;
645         return;
646     }
647
648     if (!m_shape)
649         m_shape = std::make_unique<Shape>(WTFMove(shape));
650     else
651         *m_shape = WTFMove(shape);
652 }
653
654 TextStream& operator<<(TextStream& ts, const Region& region)
655 {
656     ts << "\n";
657     {
658         TextStream::IndentScope indentScope(ts);
659         for (auto& rect : region.rects())
660             ts << indent << "(rect " << rect << ")\n";
661     }
662
663     return ts;
664 }
665
666 } // namespace WebCore