WinCairo build fails to link.
[WebKit-https.git] / Source / WebKit / chromium / tests / RegionTest.cpp
1 /*
2  * Copyright (C) 2012 Google 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'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
15  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
16  * DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
17  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
18  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
19  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
20  * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
21  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
22  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23  */
24
25 #include "config.h"
26
27 #include "Region.h"
28
29 #include <gtest/gtest.h>
30
31 using namespace WebCore;
32
33 namespace {
34
35 #define TEST_INSIDE_RECT(r, x, y, w, h)                      \
36     EXPECT_TRUE(r.contains(IntPoint(x, y)));                 \
37     EXPECT_TRUE(r.contains(IntPoint(x + w - 1, y)));         \
38     EXPECT_TRUE(r.contains(IntPoint(x, y + h - 1)));         \
39     EXPECT_TRUE(r.contains(IntPoint(x + w - 1, y + h - 1))); \
40     EXPECT_TRUE(r.contains(IntPoint(x, y + h / 2)));         \
41     EXPECT_TRUE(r.contains(IntPoint(x + w - 1, y + h / 2))); \
42     EXPECT_TRUE(r.contains(IntPoint(x + w / 2, y)));         \
43     EXPECT_TRUE(r.contains(IntPoint(x + w / 2, y + h - 1))); \
44     EXPECT_TRUE(r.contains(IntPoint(x + w / 2, y + h / 2))); \
45
46 #define TEST_LEFT_OF_RECT(r, x, y, w, h)                     \
47     EXPECT_FALSE(r.contains(IntPoint(x - 1, y)));            \
48     EXPECT_FALSE(r.contains(IntPoint(x - 1, y + h - 1)));    \
49
50 #define TEST_RIGHT_OF_RECT(r, x, y, w, h)                 \
51     EXPECT_FALSE(r.contains(IntPoint(x + w, y)));         \
52     EXPECT_FALSE(r.contains(IntPoint(x + w, y + h - 1))); \
53
54 #define TEST_TOP_OF_RECT(r, x, y, w, h)                   \
55     EXPECT_FALSE(r.contains(IntPoint(x, y - 1)));         \
56     EXPECT_FALSE(r.contains(IntPoint(x + w - 1, y - 1))); \
57
58 #define TEST_BOTTOM_OF_RECT(r, x, y, w, h)                \
59     EXPECT_FALSE(r.contains(IntPoint(x, y + h)));         \
60     EXPECT_FALSE(r.contains(IntPoint(x + w - 1, y + h))); \
61
62 TEST(RegionTest, containsPoint)
63 {
64     Region r;
65
66     EXPECT_FALSE(r.contains(IntPoint(0, 0)));
67
68     r.unite(IntRect(35, 35, 1, 1));
69     TEST_INSIDE_RECT(r, 35, 35, 1, 1);
70     TEST_LEFT_OF_RECT(r, 35, 35, 1, 1);
71     TEST_RIGHT_OF_RECT(r, 35, 35, 1, 1);
72     TEST_TOP_OF_RECT(r, 35, 35, 1, 1);
73     TEST_BOTTOM_OF_RECT(r, 35, 35, 1, 1);
74
75     r.unite(IntRect(30, 30, 10, 10));
76     TEST_INSIDE_RECT(r, 30, 30, 10, 10);
77     TEST_LEFT_OF_RECT(r, 30, 30, 10, 10);
78     TEST_RIGHT_OF_RECT(r, 30, 30, 10, 10);
79     TEST_TOP_OF_RECT(r, 30, 30, 10, 10);
80     TEST_BOTTOM_OF_RECT(r, 30, 30, 10, 10);
81
82     r.unite(IntRect(31, 40, 10, 10));
83     EXPECT_FALSE(r.contains(IntPoint(30, 40)));
84     EXPECT_TRUE(r.contains(IntPoint(31, 40)));
85     EXPECT_FALSE(r.contains(IntPoint(40, 39)));
86     EXPECT_TRUE(r.contains(IntPoint(40, 40)));
87
88     TEST_INSIDE_RECT(r, 30, 30, 10, 10);
89     TEST_LEFT_OF_RECT(r, 30, 30, 10, 10);
90     TEST_RIGHT_OF_RECT(r, 30, 30, 10, 10);
91     TEST_TOP_OF_RECT(r, 30, 30, 10, 10);
92     TEST_INSIDE_RECT(r, 31, 40, 10, 10);
93     TEST_LEFT_OF_RECT(r, 31, 40, 10, 10);
94     TEST_RIGHT_OF_RECT(r, 31, 40, 10, 10);
95     TEST_BOTTOM_OF_RECT(r, 31, 40, 10, 10);
96
97     r.unite(IntRect(42, 40, 10, 10));
98
99     TEST_INSIDE_RECT(r, 42, 40, 10, 10);
100     TEST_LEFT_OF_RECT(r, 42, 40, 10, 10);
101     TEST_RIGHT_OF_RECT(r, 42, 40, 10, 10);
102     TEST_TOP_OF_RECT(r, 42, 40, 10, 10);
103     TEST_BOTTOM_OF_RECT(r, 42, 40, 10, 10);
104
105     TEST_INSIDE_RECT(r, 30, 30, 10, 10);
106     TEST_LEFT_OF_RECT(r, 30, 30, 10, 10);
107     TEST_RIGHT_OF_RECT(r, 30, 30, 10, 10);
108     TEST_TOP_OF_RECT(r, 30, 30, 10, 10);
109     TEST_INSIDE_RECT(r, 31, 40, 10, 10);
110     TEST_LEFT_OF_RECT(r, 31, 40, 10, 10);
111     TEST_RIGHT_OF_RECT(r, 31, 40, 10, 10);
112     TEST_BOTTOM_OF_RECT(r, 31, 40, 10, 10);
113 }
114
115 TEST(RegionTest, emptySpan)
116 {
117     Region r;
118     r.unite(IntRect(5, 0, 10, 10));
119     r.unite(IntRect(0, 5, 10, 10));
120     r.subtract(IntRect(7, 7, 10, 0));
121
122     Vector<IntRect> rects = r.rects();
123     for (size_t i = 0; i < rects.size(); ++i)
124         EXPECT_FALSE(rects[i].isEmpty());
125 }
126
127 #define TEST_NO_INTERSECT(a, b)      \
128 {                                    \
129     Region ar = a;                   \
130     Region br = b;                   \
131     EXPECT_FALSE(ar.intersects(br)); \
132     EXPECT_FALSE(br.intersects(ar)); \
133 }
134
135 #define TEST_INTERSECT(a, b)        \
136 {                                   \
137     Region ar = a;                  \
138     Region br = b;                  \
139     EXPECT_TRUE(ar.intersects(br)); \
140     EXPECT_TRUE(br.intersects(ar)); \
141 }
142
143 TEST(RegionTest, intersectsRegion)
144 {
145     Region r;
146
147     TEST_NO_INTERSECT(IntRect(), IntRect());
148     TEST_NO_INTERSECT(IntRect(), IntRect(0, 0, 1, 1));
149     TEST_NO_INTERSECT(IntRect(), IntRect(1, 1, 1, 1));
150
151     r.unite(IntRect(0, 0, 1, 1));
152     TEST_NO_INTERSECT(r, IntRect());
153     TEST_INTERSECT(r, IntRect(0, 0, 1, 1));
154     TEST_INTERSECT(r, IntRect(0, 0, 2, 2));
155     TEST_INTERSECT(r, IntRect(-1, 0, 2, 2));
156     TEST_INTERSECT(r, IntRect(-1, -1, 2, 2));
157     TEST_INTERSECT(r, IntRect(0, -1, 2, 2));
158     TEST_INTERSECT(r, IntRect(-1, -1, 3, 3));
159
160     r.unite(IntRect(0, 0, 3, 3));
161     r.unite(IntRect(10, 0, 3, 3));
162     r.unite(IntRect(0, 10, 13, 3));
163     TEST_NO_INTERSECT(r, IntRect());
164     TEST_INTERSECT(r, IntRect(1, 1, 1, 1));
165     TEST_INTERSECT(r, IntRect(0, 0, 2, 2));
166     TEST_INTERSECT(r, IntRect(1, 0, 2, 2));
167     TEST_INTERSECT(r, IntRect(1, 1, 2, 2));
168     TEST_INTERSECT(r, IntRect(0, 1, 2, 2));
169     TEST_INTERSECT(r, IntRect(0, 0, 3, 3));
170     TEST_INTERSECT(r, IntRect(-1, -1, 2, 2));
171     TEST_INTERSECT(r, IntRect(2, -1, 2, 2));
172     TEST_INTERSECT(r, IntRect(2, 2, 2, 2));
173     TEST_INTERSECT(r, IntRect(-1, 2, 2, 2));
174
175     TEST_INTERSECT(r, IntRect(11, 1, 1, 1));
176     TEST_INTERSECT(r, IntRect(10, 0, 2, 2));
177     TEST_INTERSECT(r, IntRect(11, 0, 2, 2));
178     TEST_INTERSECT(r, IntRect(11, 1, 2, 2));
179     TEST_INTERSECT(r, IntRect(10, 1, 2, 2));
180     TEST_INTERSECT(r, IntRect(10, 0, 3, 3));
181     TEST_INTERSECT(r, IntRect(9, -1, 2, 2));
182     TEST_INTERSECT(r, IntRect(12, -1, 2, 2));
183     TEST_INTERSECT(r, IntRect(12, 2, 2, 2));
184     TEST_INTERSECT(r, IntRect(9, 2, 2, 2));
185
186     TEST_INTERSECT(r, IntRect(0, -1, 13, 5));
187     TEST_INTERSECT(r, IntRect(1, -1, 11, 5));
188     TEST_INTERSECT(r, IntRect(2, -1, 9, 5));
189     TEST_INTERSECT(r, IntRect(2, -1, 8, 5));
190     TEST_INTERSECT(r, IntRect(3, -1, 8, 5));
191     TEST_NO_INTERSECT(r, IntRect(3, -1, 7, 5));
192
193     TEST_INTERSECT(r, IntRect(0, 1, 13, 1));
194     TEST_INTERSECT(r, IntRect(1, 1, 11, 1));
195     TEST_INTERSECT(r, IntRect(2, 1, 9, 1));
196     TEST_INTERSECT(r, IntRect(2, 1, 8, 1));
197     TEST_INTERSECT(r, IntRect(3, 1, 8, 1));
198     TEST_NO_INTERSECT(r, IntRect(3, 1, 7, 1));
199
200     TEST_INTERSECT(r, IntRect(0, 0, 13, 13));
201     TEST_INTERSECT(r, IntRect(0, 1, 13, 11));
202     TEST_INTERSECT(r, IntRect(0, 2, 13, 9));
203     TEST_INTERSECT(r, IntRect(0, 2, 13, 8));
204     TEST_INTERSECT(r, IntRect(0, 3, 13, 8));
205     TEST_NO_INTERSECT(r, IntRect(0, 3, 13, 7));
206 }
207
208 TEST(RegionTest, ReadPastFullSpanVectorInIntersectsTest)
209 {
210     Region r;
211
212     // This region has enough spans to fill its allocated Vector exactly.
213     r.unite(IntRect(400, 300, 1, 800));
214     r.unite(IntRect(785, 585, 1, 1));
215     r.unite(IntRect(787, 585, 1, 1));
216     r.unite(IntRect(0, 587, 16, 162));
217     r.unite(IntRect(26, 590, 300, 150));
218     r.unite(IntRect(196, 750, 1, 1));
219     r.unite(IntRect(0, 766, 1, 1));
220     r.unite(IntRect(0, 782, 1, 1));
221     r.unite(IntRect(745, 798, 1, 1));
222     r.unite(IntRect(795, 882, 10, 585));
223     r.unite(IntRect(100, 1499, 586, 1));
224     r.unite(IntRect(100, 1500, 585, 784));
225     // This query rect goes past the bottom of the Region, causing the
226     // test to reach the last span and try go past it. It should not read
227     // memory off the end of the span Vector.
228     TEST_NO_INTERSECT(r, IntRect(0, 2184, 1, 150));
229 }
230
231 #define TEST_NO_CONTAINS(a, b)     \
232 {                                  \
233     Region ar = a;                 \
234     Region br = b;                 \
235     EXPECT_FALSE(ar.contains(br)); \
236 }
237
238 #define TEST_CONTAINS(a, b)       \
239 {                                 \
240     Region ar = a;                \
241     Region br = b;                \
242     EXPECT_TRUE(ar.contains(br)); \
243 }
244
245 TEST(RegionTest, containsRegion)
246 {
247     TEST_CONTAINS(IntRect(), IntRect());
248     TEST_NO_CONTAINS(IntRect(), IntRect(0, 0, 1, 1));
249     TEST_NO_CONTAINS(IntRect(), IntRect(1, 1, 1, 1));
250
251     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(11, 10, 1, 1));
252     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 11, 1, 1));
253     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 10, 1, 1));
254     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 9, 1, 1));
255     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 9, 2, 2));
256     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 9, 2, 2));
257     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 10, 2, 2));
258     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 10, 2, 2));
259     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 9, 3, 3));
260
261     Region hLines;
262     for (int i = 10; i < 20; i += 2)
263         hLines.unite(IntRect(i, 10, 1, 10));
264
265     TEST_CONTAINS(IntRect(10, 10, 9, 10), hLines);
266     TEST_NO_CONTAINS(IntRect(10, 10, 9, 9), hLines);
267     TEST_NO_CONTAINS(IntRect(10, 11, 9, 9), hLines);
268     TEST_NO_CONTAINS(IntRect(10, 10, 8, 10), hLines);
269     TEST_NO_CONTAINS(IntRect(11, 10, 8, 10), hLines);
270
271     Region vLines;
272     for (int i = 10; i < 20; i += 2)
273         vLines.unite(IntRect(10, i, 10, 1));
274
275     TEST_CONTAINS(IntRect(10, 10, 10, 9), vLines);
276     TEST_NO_CONTAINS(IntRect(10, 10, 9, 9), vLines);
277     TEST_NO_CONTAINS(IntRect(11, 10, 9, 9), vLines);
278     TEST_NO_CONTAINS(IntRect(10, 10, 10, 8), vLines);
279     TEST_NO_CONTAINS(IntRect(10, 11, 10, 8), vLines);
280
281     Region grid;
282     for (int i = 10; i < 20; i += 2)
283         for (int j = 10; j < 20; j += 2)
284             grid.unite(IntRect(i, j, 1, 1));
285
286     TEST_CONTAINS(IntRect(10, 10, 9, 9), grid);
287     TEST_NO_CONTAINS(IntRect(10, 10, 9, 8), grid);
288     TEST_NO_CONTAINS(IntRect(10, 11, 9, 8), grid);
289     TEST_NO_CONTAINS(IntRect(10, 10, 8, 9), grid);
290     TEST_NO_CONTAINS(IntRect(11, 10, 8, 9), grid);
291
292     TEST_CONTAINS(hLines, hLines);
293     TEST_CONTAINS(vLines, vLines);
294     TEST_NO_CONTAINS(vLines, hLines);
295     TEST_NO_CONTAINS(hLines, vLines);
296     TEST_CONTAINS(grid, grid);
297     TEST_CONTAINS(hLines, grid);
298     TEST_CONTAINS(vLines, grid);
299     TEST_NO_CONTAINS(grid, hLines);
300     TEST_NO_CONTAINS(grid, vLines);
301
302     for (int i = 10; i < 20; i += 2)
303         TEST_CONTAINS(hLines, IntRect(i, 10, 1, 10));
304
305     for (int i = 10; i < 20; i += 2)
306         TEST_CONTAINS(vLines, IntRect(10, i, 10, 1));
307
308     for (int i = 10; i < 20; i += 2)
309         for (int j = 10; j < 20; j += 2)
310             TEST_CONTAINS(grid, IntRect(i, j, 1, 1));
311
312     Region container;
313     container.unite(IntRect(0, 0, 40, 20));
314     container.unite(IntRect(0, 20, 41, 20));
315     TEST_CONTAINS(container, IntRect(5, 5, 30, 30));
316
317     container = Region();
318     container.unite(IntRect(0, 0, 10, 10));
319     container.unite(IntRect(0, 30, 10, 10));
320     container.unite(IntRect(30, 30, 10, 10));
321     container.unite(IntRect(30, 0, 10, 10));
322     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
323
324     container = Region();
325     container.unite(IntRect(0, 0, 10, 10));
326     container.unite(IntRect(0, 30, 10, 10));
327     container.unite(IntRect(30, 0, 10, 40));
328     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
329
330     container = Region();
331     container.unite(IntRect(30, 0, 10, 10));
332     container.unite(IntRect(30, 30, 10, 10));
333     container.unite(IntRect(0, 0, 10, 40));
334     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
335
336     container = Region();
337     container.unite(IntRect(0, 0, 10, 40));
338     container.unite(IntRect(30, 0, 10, 40));
339     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
340
341     container = Region();
342     container.unite(IntRect(0, 0, 40, 40));
343     TEST_NO_CONTAINS(container, IntRect(10, -1, 20, 10));
344
345     container = Region();
346     container.unite(IntRect(0, 0, 40, 40));
347     TEST_NO_CONTAINS(container, IntRect(10, 31, 20, 10));
348
349     container = Region();
350     container.unite(IntRect(0, 0, 40, 20));
351     container.unite(IntRect(0, 20, 41, 20));
352     TEST_NO_CONTAINS(container, IntRect(-1, 10, 10, 20));
353
354     container = Region();
355     container.unite(IntRect(0, 0, 40, 20));
356     container.unite(IntRect(0, 20, 41, 20));
357     TEST_NO_CONTAINS(container, IntRect(31, 10, 10, 20));
358
359     container = Region();
360     container.unite(IntRect(0, 0, 40, 40));
361     container.subtract(IntRect(0, 20, 60, 0));
362     TEST_NO_CONTAINS(container, IntRect(31, 10, 10, 20));
363 }
364
365 TEST(RegionTest, unite)
366 {
367     Region r;
368     Region r2;
369
370     // A rect uniting a contained rect does not change the region.
371     r2 = r = IntRect(0, 0, 50, 50);
372     r2.unite(IntRect(20, 20, 10, 10));
373     EXPECT_EQ(r, r2);
374
375     // A rect uniting a containing rect gives back the containing rect.
376     r = IntRect(0, 0, 50, 50);
377     r.unite(IntRect(0, 0, 100, 100));
378     EXPECT_EQ(Region(IntRect(0, 0, 100, 100)), r);
379
380     // A complex region uniting a contained rect does not change the region.
381     r = IntRect(0, 0, 50, 50);
382     r.unite(IntRect(100, 0, 50, 50));
383     r2 = r;
384     r2.unite(IntRect(20, 20, 10, 10));
385     EXPECT_EQ(r, r2);
386
387     // A complex region uniting a containing rect gives back the containing rect.
388     r = IntRect(0, 0, 50, 50);
389     r.unite(IntRect(100, 0, 50, 50));
390     r. unite(IntRect(0, 0, 500, 500));
391     EXPECT_EQ(Region(IntRect(0, 0, 500, 500)), r);
392 }
393
394 } // namespace