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#include "SkPath.h"
9#include "SkRandom.h"
10#include "SkRegion.h"
11#include "Test.h"
12
13static void Union(SkRegion* rgn, const SkIRect& rect) {
14    rgn->op(rect, SkRegion::kUnion_Op);
15}
16
17#define TEST_NO_INTERSECT(rgn, rect)    REPORTER_ASSERT(reporter, !rgn.intersects(rect))
18#define TEST_INTERSECT(rgn, rect)       REPORTER_ASSERT(reporter, rgn.intersects(rect))
19#define TEST_NO_CONTAINS(rgn, rect)     REPORTER_ASSERT(reporter, !rgn.contains(rect))
20
21// inspired by http://code.google.com/p/skia/issues/detail?id=958
22//
23static void test_fromchrome(skiatest::Reporter* reporter) {
24    SkRegion r;
25    Union(&r, SkIRect::MakeXYWH(0, 0, 1, 1));
26    TEST_NO_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 0, 0));
27    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 2, 2));
28    TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, 0, 2, 2));
29    TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 2, 2));
30    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, -1, 2, 2));
31    TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 3, 3));
32
33    Union(&r, SkIRect::MakeXYWH(0, 0, 3, 3));
34    Union(&r, SkIRect::MakeXYWH(10, 0, 3, 3));
35    Union(&r, SkIRect::MakeXYWH(0, 10, 13, 3));
36    TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 2, 2));
37    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 2, 2));
38    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 2, 2, 2));
39    TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, 2, 2, 2));
40
41    TEST_INTERSECT(r, SkIRect::MakeXYWH(9, -1, 2, 2));
42    TEST_INTERSECT(r, SkIRect::MakeXYWH(12, -1, 2, 2));
43    TEST_INTERSECT(r, SkIRect::MakeXYWH(12, 2, 2, 2));
44    TEST_INTERSECT(r, SkIRect::MakeXYWH(9, 2, 2, 2));
45
46    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, -1, 13, 5));
47    TEST_INTERSECT(r, SkIRect::MakeXYWH(1, -1, 11, 5));
48    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 9, 5));
49    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 8, 5));
50    TEST_INTERSECT(r, SkIRect::MakeXYWH(3, -1, 8, 5));
51
52    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 1, 13, 1));
53    TEST_INTERSECT(r, SkIRect::MakeXYWH(1, 1, 11, 1));
54    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 1, 9, 1));
55    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 1, 8, 1));
56    TEST_INTERSECT(r, SkIRect::MakeXYWH(3, 1, 8, 1));
57
58    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 13, 13));
59    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 1, 13, 11));
60    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 2, 13, 9));
61    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 2, 13, 8));
62
63
64    // These test SkRegion::contains(Rect) and SkRegion::contains(Region)
65
66    SkRegion container;
67    Union(&container, SkIRect::MakeXYWH(0, 0, 40, 20));
68    Union(&container, SkIRect::MakeXYWH(30, 20, 10, 20));
69    TEST_NO_CONTAINS(container, SkIRect::MakeXYWH(0, 0, 10, 39));
70    TEST_NO_CONTAINS(container, SkIRect::MakeXYWH(29, 0, 10, 39));
71
72    {
73        SkRegion rgn;
74        Union(&rgn, SkIRect::MakeXYWH(0, 0, 10, 10));
75        Union(&rgn, SkIRect::MakeLTRB(5, 10, 20, 20));
76        TEST_INTERSECT(rgn, SkIRect::MakeXYWH(15, 0, 5, 11));
77    }
78}
79
80static void test_empties(skiatest::Reporter* reporter) {
81    SkRegion valid(SkIRect::MakeWH(10, 10));
82    SkRegion empty, empty2;
83
84    REPORTER_ASSERT(reporter, empty.isEmpty());
85    REPORTER_ASSERT(reporter, !valid.isEmpty());
86
87    // test intersects
88    REPORTER_ASSERT(reporter, !empty.intersects(empty2));
89    REPORTER_ASSERT(reporter, !valid.intersects(empty));
90
91    // test contains
92    REPORTER_ASSERT(reporter, !empty.contains(empty2));
93    REPORTER_ASSERT(reporter, !valid.contains(empty));
94    REPORTER_ASSERT(reporter, !empty.contains(valid));
95
96    SkPath emptyPath;
97    emptyPath.moveTo(1, 5);
98    emptyPath.close();
99    SkRegion openClip;
100    openClip.setRect(-16000, -16000, 16000, 16000);
101    empty.setPath(emptyPath, openClip);  // should not assert
102}
103
104enum {
105    W = 256,
106    H = 256
107};
108
109static SkIRect randRect(SkRandom& rand) {
110    int x = rand.nextU() % W;
111    int y = rand.nextU() % H;
112    int w = rand.nextU() % W;
113    int h = rand.nextU() % H;
114    return SkIRect::MakeXYWH(x, y, w >> 1, h >> 1);
115}
116
117static void randRgn(SkRandom& rand, SkRegion* rgn, int n) {
118    rgn->setEmpty();
119    for (int i = 0; i < n; ++i) {
120        rgn->op(randRect(rand), SkRegion::kUnion_Op);
121    }
122}
123
124static bool slow_contains(const SkRegion& outer, const SkRegion& inner) {
125    SkRegion tmp;
126    tmp.op(outer, inner, SkRegion::kUnion_Op);
127    return outer == tmp;
128}
129
130static bool slow_contains(const SkRegion& outer, const SkIRect& r) {
131    SkRegion tmp;
132    tmp.op(outer, SkRegion(r), SkRegion::kUnion_Op);
133    return outer == tmp;
134}
135
136static bool slow_intersects(const SkRegion& outer, const SkRegion& inner) {
137    SkRegion tmp;
138    return tmp.op(outer, inner, SkRegion::kIntersect_Op);
139}
140
141static void test_contains_iter(skiatest::Reporter* reporter, const SkRegion& rgn) {
142    SkRegion::Iterator iter(rgn);
143    while (!iter.done()) {
144        SkIRect r = iter.rect();
145        REPORTER_ASSERT(reporter, rgn.contains(r));
146        r.inset(-1, -1);
147        REPORTER_ASSERT(reporter, !rgn.contains(r));
148        iter.next();
149    }
150}
151
152static void contains_proc(skiatest::Reporter* reporter,
153                          const SkRegion& a, const SkRegion& b) {
154    // test rgn
155    bool c0 = a.contains(b);
156    bool c1 = slow_contains(a, b);
157    REPORTER_ASSERT(reporter, c0 == c1);
158
159    // test rect
160    SkIRect r = a.getBounds();
161    r.inset(r.width()/4, r.height()/4);
162    c0 = a.contains(r);
163    c1 = slow_contains(a, r);
164    REPORTER_ASSERT(reporter, c0 == c1);
165
166    test_contains_iter(reporter, a);
167    test_contains_iter(reporter, b);
168}
169
170static void test_intersects_iter(skiatest::Reporter* reporter, const SkRegion& rgn) {
171    SkRegion::Iterator iter(rgn);
172    while (!iter.done()) {
173        SkIRect r = iter.rect();
174        REPORTER_ASSERT(reporter, rgn.intersects(r));
175        r.inset(-1, -1);
176        REPORTER_ASSERT(reporter, rgn.intersects(r));
177        iter.next();
178    }
179}
180
181static void intersects_proc(skiatest::Reporter* reporter,
182                          const SkRegion& a, const SkRegion& b) {
183    bool c0 = a.intersects(b);
184    bool c1 = slow_intersects(a, b);
185    REPORTER_ASSERT(reporter, c0 == c1);
186
187    test_intersects_iter(reporter, a);
188    test_intersects_iter(reporter, b);
189}
190
191static void test_proc(skiatest::Reporter* reporter,
192                      void (*proc)(skiatest::Reporter*,
193                                   const SkRegion& a, const SkRegion&)) {
194    SkRandom rand;
195    for (int i = 0; i < 10000; ++i) {
196        SkRegion outer;
197        randRgn(rand, &outer, 8);
198        SkRegion inner;
199        randRgn(rand, &inner, 2);
200        proc(reporter, outer, inner);
201    }
202}
203
204static void rand_rect(SkIRect* rect, SkRandom& rand) {
205    int bits = 6;
206    int shift = 32 - bits;
207    rect->set(rand.nextU() >> shift, rand.nextU() >> shift,
208              rand.nextU() >> shift, rand.nextU() >> shift);
209    rect->sort();
210}
211
212static bool test_rects(const SkIRect rect[], int count) {
213    SkRegion rgn0, rgn1;
214
215    for (int i = 0; i < count; i++) {
216        rgn0.op(rect[i], SkRegion::kUnion_Op);
217    }
218    rgn1.setRects(rect, count);
219
220    if (rgn0 != rgn1) {
221        SkDebugf("\n");
222        for (int i = 0; i < count; i++) {
223            SkDebugf(" { %d, %d, %d, %d },\n",
224                     rect[i].fLeft, rect[i].fTop,
225                     rect[i].fRight, rect[i].fBottom);
226        }
227        SkDebugf("\n");
228        return false;
229    }
230    return true;
231}
232
233DEF_TEST(Region, reporter) {
234    const SkIRect r2[] = {
235        { 0, 0, 1, 1 },
236        { 2, 2, 3, 3 },
237    };
238    REPORTER_ASSERT(reporter, test_rects(r2, SK_ARRAY_COUNT(r2)));
239
240    const SkIRect rects[] = {
241        { 0, 0, 1, 2 },
242        { 2, 1, 3, 3 },
243        { 4, 0, 5, 1 },
244        { 6, 0, 7, 4 },
245    };
246    REPORTER_ASSERT(reporter, test_rects(rects, SK_ARRAY_COUNT(rects)));
247
248    SkRandom rand;
249    for (int i = 0; i < 1000; i++) {
250        SkRegion rgn0, rgn1;
251
252        const int N = 8;
253        SkIRect rect[N];
254        for (int j = 0; j < N; j++) {
255            rand_rect(&rect[j], rand);
256        }
257        REPORTER_ASSERT(reporter, test_rects(rect, N));
258    }
259
260    test_proc(reporter, contains_proc);
261    test_proc(reporter, intersects_proc);
262    test_empties(reporter);
263    test_fromchrome(reporter);
264}
265
266// Test that writeToMemory reports the same number of bytes whether there was a
267// buffer to write to or not.
268static void test_write(const SkRegion& region, skiatest::Reporter* r) {
269    const size_t bytesNeeded = region.writeToMemory(nullptr);
270    SkAutoMalloc storage(bytesNeeded);
271    const size_t bytesWritten = region.writeToMemory(storage.get());
272    REPORTER_ASSERT(r, bytesWritten == bytesNeeded);
273}
274
275DEF_TEST(Region_writeToMemory, r) {
276    // Test an empty region.
277    SkRegion region;
278    REPORTER_ASSERT(r, region.isEmpty());
279    test_write(region, r);
280
281    // Test a rectangular region
282    bool nonEmpty = region.setRect(0, 0, 50, 50);
283    REPORTER_ASSERT(r, nonEmpty);
284    REPORTER_ASSERT(r, region.isRect());
285    test_write(region, r);
286
287    // Test a complex region
288    nonEmpty = region.op(50, 50, 100, 100, SkRegion::kUnion_Op);
289    REPORTER_ASSERT(r, nonEmpty);
290    REPORTER_ASSERT(r, region.isComplex());
291    test_write(region, r);
292}
293