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