1/*
2 * Copyright (C) 2009, 2010, 2011, 2012 Research In Motion Limited. All rights reserved.
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
17 */
18
19#include "config.h"
20#include "RenderQueue.h"
21
22#include "BackingStore_p.h"
23#include "SurfacePool.h"
24#include "WebPageClient.h"
25#include "WebPage_p.h"
26
27#include <wtf/NonCopyingSort.h>
28
29#define DEBUG_RENDER_QUEUE 0
30#define DEBUG_RENDER_QUEUE_SORT 0
31
32#if DEBUG_RENDER_QUEUE
33#include <BlackBerryPlatformLog.h>
34#include <wtf/CurrentTime.h>
35#endif
36
37namespace BlackBerry {
38namespace WebKit {
39
40template<SortDirection sortDirection>
41static inline int compareRectOneDirection(const TileIndex& t1, const TileIndex& t2)
42{
43    switch (sortDirection) {
44    case LeftToRight:
45        return t1.i() - t2.i();
46    case RightToLeft:
47        return t2.i() - t1.i();
48    case TopToBottom:
49        return t1.j() - t2.j();
50    case BottomToTop:
51        return t2.j() - t1.j();
52    default:
53        break;
54    }
55    ASSERT_NOT_REACHED();
56    return 0;
57}
58
59template<SortDirection primarySortDirection, SortDirection secondarySortDirection>
60static bool tileIndexIsLessThan(const TileIndex& t1, const TileIndex& t2)
61{
62    int primaryResult = compareRectOneDirection<primarySortDirection>(t1, t2);
63    if (primaryResult || secondarySortDirection == primarySortDirection)
64        return primaryResult < 0;
65    return compareRectOneDirection<secondarySortDirection>(t1, t2) < 0;
66}
67
68typedef bool (*FuncTileIndexLessThan)(const TileIndex& t1, const TileIndex& t2);
69static FuncTileIndexLessThan tileIndexLessThanFunction(SortDirection primary, SortDirection secondary)
70{
71    static FuncTileIndexLessThan s_tileIndexLessThanFunctions[NumSortDirections][NumSortDirections] = { { 0 } };
72    static bool s_initialized = false;
73    if (!s_initialized) {
74#define ADD_COMPARE_FUNCTION(_primary, _secondary) \
75        s_tileIndexLessThanFunctions[_primary][_secondary] = tileIndexIsLessThan<_primary, _secondary>
76
77        ADD_COMPARE_FUNCTION(LeftToRight, LeftToRight);
78        ADD_COMPARE_FUNCTION(LeftToRight, RightToLeft);
79        ADD_COMPARE_FUNCTION(LeftToRight, TopToBottom);
80        ADD_COMPARE_FUNCTION(LeftToRight, BottomToTop);
81
82        ADD_COMPARE_FUNCTION(RightToLeft, LeftToRight);
83        ADD_COMPARE_FUNCTION(RightToLeft, RightToLeft);
84        ADD_COMPARE_FUNCTION(RightToLeft, TopToBottom);
85        ADD_COMPARE_FUNCTION(RightToLeft, BottomToTop);
86
87        ADD_COMPARE_FUNCTION(TopToBottom, LeftToRight);
88        ADD_COMPARE_FUNCTION(TopToBottom, RightToLeft);
89        ADD_COMPARE_FUNCTION(TopToBottom, TopToBottom);
90        ADD_COMPARE_FUNCTION(TopToBottom, BottomToTop);
91
92        ADD_COMPARE_FUNCTION(BottomToTop, LeftToRight);
93        ADD_COMPARE_FUNCTION(BottomToTop, RightToLeft);
94        ADD_COMPARE_FUNCTION(BottomToTop, TopToBottom);
95        ADD_COMPARE_FUNCTION(BottomToTop, BottomToTop);
96#undef ADD_COMPARE_FUNCTION
97
98        s_initialized = true;
99    }
100
101    return s_tileIndexLessThanFunctions[primary][secondary];
102}
103
104class TileIndexLessThan {
105public:
106    TileIndexLessThan(SortDirection primarySortDirection, SortDirection secondarySortDirection)
107        : m_tileIndexIsLessThan(tileIndexLessThanFunction(primarySortDirection, secondarySortDirection))
108    {
109    }
110
111    bool operator()(const TileIndex& t1, const TileIndex& t2)
112    {
113        return m_tileIndexIsLessThan(t1, t2);
114    }
115
116private:
117    FuncTileIndexLessThan m_tileIndexIsLessThan;
118};
119
120RenderQueue::RenderQueue(BackingStorePrivate* parent)
121    : m_parent(parent)
122    , m_rectsAddedToRegularRenderJobsInCurrentCycle(false)
123    , m_currentRegularRenderJobsBatchUnderPressure(false)
124    , m_primarySortDirection(TopToBottom)
125    , m_secondarySortDirection(LeftToRight)
126{
127}
128
129void RenderQueue::reset()
130{
131    m_rectsAddedToRegularRenderJobsInCurrentCycle = false;
132    m_currentRegularRenderJobsBatchUnderPressure = false;
133    m_primarySortDirection = TopToBottom;
134    m_secondarySortDirection = LeftToRight;
135    m_visibleZoomJobs.clear();
136    m_visibleZoomJobsCompleted.clear();
137    m_visibleScrollJobs.clear();
138    m_visibleScrollJobsCompleted.clear();
139    m_nonVisibleScrollJobs.clear();
140    m_nonVisibleScrollJobsCompleted.clear();
141    m_regularRenderJobsRegion = Platform::IntRectRegion();
142    m_currentRegularRenderJobsBatch.clear();
143    m_currentRegularRenderJobsBatchRegion = Platform::IntRectRegion();
144    m_regularRenderJobsNotRenderedRegion = Platform::IntRectRegion();
145    ASSERT(isEmpty());
146}
147
148bool RenderQueue::isEmpty(bool shouldPerformRegularRenderJobs) const
149{
150    return m_visibleZoomJobs.isEmpty() && m_visibleScrollJobs.isEmpty()
151        && (!shouldPerformRegularRenderJobs || m_currentRegularRenderJobsBatch.isEmpty())
152        && (!shouldPerformRegularRenderJobs || m_regularRenderJobsRegion.isEmpty())
153        && m_nonVisibleScrollJobs.isEmpty();
154}
155
156bool RenderQueue::hasCurrentRegularRenderJob() const
157{
158    return !m_currentRegularRenderJobsBatch.isEmpty() || !m_regularRenderJobsRegion.isEmpty();
159}
160
161bool RenderQueue::hasCurrentVisibleZoomJob() const
162{
163    return !m_visibleZoomJobs.isEmpty();
164}
165
166bool RenderQueue::hasCurrentVisibleScrollJob() const
167{
168    return !m_visibleScrollJobs.isEmpty();
169}
170
171bool RenderQueue::isCurrentVisibleZoomJob(const TileIndex& index) const
172{
173    return m_visibleZoomJobs.contains(index);
174}
175
176bool RenderQueue::isCurrentVisibleZoomJobCompleted(const TileIndex& index) const
177{
178    return m_visibleZoomJobsCompleted.contains(index);
179}
180
181bool RenderQueue::isCurrentVisibleScrollJob(const TileIndex& index) const
182{
183    return m_visibleScrollJobs.contains(index);
184}
185
186bool RenderQueue::isCurrentVisibleScrollJobCompleted(const TileIndex& index) const
187{
188    return m_visibleScrollJobsCompleted.contains(index);
189}
190
191bool RenderQueue::isCurrentRegularRenderJob(const TileIndex& index, BackingStoreGeometry* geometry) const
192{
193    Platform::IntRect tileRect(geometry->originOfTile(index), m_parent->tileSize());
194    Platform::IntRectRegion::IntersectionState regularJobsState = m_regularRenderJobsRegion.isRectInRegion(tileRect);
195    Platform::IntRectRegion::IntersectionState currentRegularJobsState = m_currentRegularRenderJobsBatchRegion.isRectInRegion(tileRect);
196
197    return regularJobsState == Platform::IntRectRegion::ContainedInRegion
198        || regularJobsState == Platform::IntRectRegion::PartiallyContainedInRegion
199        || currentRegularJobsState == Platform::IntRectRegion::ContainedInRegion
200        || currentRegularJobsState == Platform::IntRectRegion::PartiallyContainedInRegion;
201}
202
203bool RenderQueue::currentRegularRenderJobBatchUnderPressure() const
204{
205    return m_currentRegularRenderJobsBatchUnderPressure;
206}
207
208void RenderQueue::setCurrentRegularRenderJobBatchUnderPressure(bool currentRegularRenderJobsBatchUnderPressure)
209{
210    m_currentRegularRenderJobsBatchUnderPressure = currentRegularRenderJobsBatchUnderPressure;
211}
212
213void RenderQueue::eventQueueCycled()
214{
215    // Called by the backing store when the event queue has cycled to allow the
216    // render queue to determine if the regular render jobs are under pressure.
217    if (m_rectsAddedToRegularRenderJobsInCurrentCycle && m_currentRegularRenderJobsBatchRegion.isEmpty())
218        m_currentRegularRenderJobsBatchUnderPressure = true;
219    m_rectsAddedToRegularRenderJobsInCurrentCycle = false;
220}
221
222TileIndexList RenderQueue::tileIndexesIntersectingRegion(const Platform::IntRectRegion& region, BackingStoreGeometry* geometry) const
223{
224    TileIndexList indexes;
225    TileIndexList allIndexes = m_parent->indexesForBackingStoreRect(geometry->backingStoreRect());
226
227    for (size_t i = 0; i < allIndexes.size(); ++i) {
228        Platform::IntRect tileRect(geometry->originOfTile(allIndexes[i]), m_parent->tileSize());
229        Platform::IntRectRegion::IntersectionState state = region.isRectInRegion(tileRect);
230        if (state == Platform::IntRectRegion::ContainedInRegion || state == Platform::IntRectRegion::PartiallyContainedInRegion)
231            indexes.append(allIndexes[i]);
232    }
233    return indexes;
234}
235
236TileIndexList RenderQueue::tileIndexesFullyContainedInRegion(const Platform::IntRectRegion& region, BackingStoreGeometry* geometry) const
237{
238    TileIndexList indexes;
239    TileIndexList allIndexes = m_parent->indexesForBackingStoreRect(geometry->backingStoreRect());
240
241    for (size_t i = 0; i < allIndexes.size(); ++i) {
242        Platform::IntRect tileRect(geometry->originOfTile(allIndexes[i]), m_parent->tileSize());
243        Platform::IntRectRegion::IntersectionState state = region.isRectInRegion(tileRect);
244        if (state == Platform::IntRectRegion::ContainedInRegion)
245            indexes.append(allIndexes[i]);
246    }
247    return indexes;
248}
249
250Platform::IntRectRegion RenderQueue::tileRegion(const TileIndexList& indexes, BackingStoreGeometry* geometry) const
251{
252    Platform::IntRectRegion region;
253
254    // Chances are the tiles comprise a perfect rectangle. If we add rectangles
255    // row by row or column by column, IntRectRegion should have an easier time
256    // merging them as the individual rows or columns will merge into another
257    // plain rectangle.
258    Platform::IntRectRegion currentRowOrColumnRegion;
259    size_t lastI = 0;
260    size_t lastJ = 0;
261
262    for (size_t i = 0; i < indexes.size(); ++i) {
263        Platform::IntRect tileRect(geometry->originOfTile(indexes[i]), m_parent->tileSize());
264        bool extendsCurrentRowOrColumn = i && (lastI == indexes[i].i() || lastJ == indexes[i].j());
265
266        if (extendsCurrentRowOrColumn)
267            currentRowOrColumnRegion = Platform::IntRectRegion::unionRegions(currentRowOrColumnRegion, tileRect);
268        else {
269            region = Platform::IntRectRegion::unionRegions(region, currentRowOrColumnRegion);
270            currentRowOrColumnRegion = tileRect;
271        }
272        lastI = indexes[i].i();
273        lastJ = indexes[i].j();
274    }
275
276    return Platform::IntRectRegion::unionRegions(region, currentRowOrColumnRegion);
277}
278
279void RenderQueue::addToQueue(JobType type, const Platform::IntRectRegion& region)
280{
281    if (type == RegularRender) {
282        // Flag that we added rects in the current event queue cycle.
283        m_rectsAddedToRegularRenderJobsInCurrentCycle = true;
284
285        // We try and detect if this newly added region intersects or is contained in the currently running
286        // batch of render jobs. If so, then we have to start the batch over since we decompose individual
287        // rects into subrects and might have already rendered one of them. If the web page's content has
288        // changed state then this can lead to artifacts. We mark this by noting the batch is now under pressure
289        // and the backingstore will attempt to clear it at the next available opportunity.
290        std::vector<Platform::IntRect> rectsInRegion = region.rects();
291        for (size_t i = 0; i < rectsInRegion.size(); ++i) {
292            Platform::IntRectRegion::IntersectionState state = m_currentRegularRenderJobsBatchRegion.isRectInRegion(rectsInRegion[i]);
293            if (state == Platform::IntRectRegion::ContainedInRegion || state == Platform::IntRectRegion::PartiallyContainedInRegion) {
294                m_regularRenderJobsRegion = Platform::IntRectRegion::unionRegions(m_regularRenderJobsRegion, m_currentRegularRenderJobsBatchRegion);
295                m_currentRegularRenderJobsBatch.clear();
296                m_currentRegularRenderJobsBatchRegion = Platform::IntRectRegion();
297                m_currentRegularRenderJobsBatchUnderPressure = true;
298            }
299        }
300        addToRegularQueue(region);
301        return;
302    }
303
304    TileIndexList indexes = tileIndexesIntersectingRegion(region, m_parent->frontState());
305
306    switch (type) {
307    case VisibleZoom:
308        addToScrollZoomQueue(indexes, &m_visibleZoomJobs);
309        return;
310    case VisibleScroll:
311        addToScrollZoomQueue(indexes, &m_visibleScrollJobs);
312        return;
313    case NonVisibleScroll:
314        addToScrollZoomQueue(indexes, &m_nonVisibleScrollJobs);
315        return;
316    default:
317        ASSERT_NOT_REACHED();
318    }
319}
320
321void RenderQueue::addToRegularQueue(const Platform::IntRectRegion& region)
322{
323#if DEBUG_RENDER_QUEUE
324    std::vector<Platform::IntRect> rectsInRegion = region.rects();
325    for (size_t i = 0; i < rectsInRegion.size(); ++i) {
326        if (m_regularRenderJobsRegion.isRectInRegion(rectsInRegion[i]) != Platform::IntRectRegion::ContainedInRegion) {
327            Platform::logAlways(Platform::LogLevelCritical,
328                "RenderQueue::addToRegularQueue region within %s",
329                region.extents().toString().c_str());
330            break;
331        }
332    }
333#endif
334
335    m_regularRenderJobsRegion = Platform::IntRectRegion::unionRegions(m_regularRenderJobsRegion, region);
336
337    // Do not let the regular render queue grow past a maximum of 3 disjoint rects.
338    if (m_regularRenderJobsRegion.numRects() > 2)
339        m_regularRenderJobsRegion = m_regularRenderJobsRegion.extents();
340
341    if (!isEmpty())
342        m_parent->dispatchRenderJob();
343}
344
345void RenderQueue::addToScrollZoomQueue(const TileIndexList& addedTiles, TileIndexList* alreadyQueuedTiles)
346{
347    Platform::IntRect contentsRect = m_parent->expandedContentsRect();
348    for (size_t i = 0; i < addedTiles.size(); ++i) {
349        if (alreadyQueuedTiles->contains(addedTiles[i]))
350            continue;
351
352        Platform::IntRect tileRect(m_parent->frontState()->originOfTile(addedTiles[i]), m_parent->tileSize());
353        if (!contentsRect.intersects(tileRect)) {
354#if DEBUG_RENDER_QUEUE
355                Platform::logAlways(Platform::LogLevelCritical,
356                    "RenderQueue::addToScrollZoomQueue tile at %s outside of expanded contents rect %s, ignoring.",
357                    tileRect.toString().c_str(),
358                    contentsRect.toString().c_str());
359#endif
360            continue;
361        }
362
363#if DEBUG_RENDER_QUEUE
364        Platform::logAlways(Platform::LogLevelCritical,
365            "RenderQueue::addToScrollZoomQueue tile at %s",
366            m_parent->frontState()->originOfTile(addedTiles[i]).toString().c_str());
367#endif
368        alreadyQueuedTiles->append(addedTiles[i]);
369    }
370
371    if (!isEmpty())
372        m_parent->dispatchRenderJob();
373}
374
375void RenderQueue::quickSort(TileIndexList* queue)
376{
377    size_t length = queue->size();
378    if (!length)
379        return;
380
381    WTF::nonCopyingSort(queue->begin(), queue->end(), TileIndexLessThan(m_primarySortDirection, m_secondarySortDirection));
382}
383
384void RenderQueue::updateSortDirection(int lastDeltaX, int lastDeltaY)
385{
386    bool primaryIsHorizontal = abs(lastDeltaX) >= abs(lastDeltaY);
387    if (primaryIsHorizontal) {
388        m_primarySortDirection = lastDeltaX <= 0 ? LeftToRight : RightToLeft;
389        m_secondarySortDirection = lastDeltaY <= 0 ? TopToBottom : BottomToTop;
390    } else {
391        m_primarySortDirection = lastDeltaY <= 0 ? TopToBottom : BottomToTop;
392        m_secondarySortDirection = lastDeltaX <= 0 ? LeftToRight : RightToLeft;
393    }
394}
395
396void RenderQueue::visibleContentChanged(const Platform::IntRect& visibleContent)
397{
398    if (m_visibleScrollJobs.isEmpty() && m_nonVisibleScrollJobs.isEmpty()) {
399        ASSERT(m_visibleScrollJobsCompleted.isEmpty() && m_nonVisibleScrollJobsCompleted.isEmpty());
400        return;
401    }
402
403    TileIndexList visibleTiles = tileIndexesIntersectingRegion(visibleContent, m_parent->frontState());
404
405    // Move visibleScrollJobs to nonVisibleScrollJobs if they do not intersect
406    // the visible content rect.
407    for (size_t i = 0; i < m_visibleScrollJobs.size(); ++i) {
408        if (!visibleTiles.contains(m_visibleScrollJobs[i])) {
409            ASSERT(!m_nonVisibleScrollJobs.contains(m_visibleScrollJobs[i]));
410            m_nonVisibleScrollJobs.append(m_visibleScrollJobs[i]);
411            m_visibleScrollJobs.remove(i);
412            --i;
413        }
414    }
415
416    // Do the same for the completed list.
417    for (size_t i = 0; i < m_visibleScrollJobsCompleted.size(); ++i) {
418        if (!visibleTiles.contains(m_visibleScrollJobsCompleted[i])) {
419            ASSERT(!m_nonVisibleScrollJobsCompleted.contains(m_visibleScrollJobsCompleted[i]));
420            m_nonVisibleScrollJobsCompleted.append(m_visibleScrollJobsCompleted[i]);
421            m_visibleScrollJobsCompleted.remove(i);
422            --i;
423        }
424    }
425
426    // Move nonVisibleScrollJobs to visibleScrollJobs if they do intersect
427    // the visible content rect.
428    for (size_t i = 0; i < m_nonVisibleScrollJobs.size(); ++i) {
429        if (visibleTiles.contains(m_nonVisibleScrollJobs[i])) {
430            ASSERT(!m_visibleScrollJobs.contains(m_nonVisibleScrollJobs[i]));
431            m_visibleScrollJobs.append(m_nonVisibleScrollJobs[i]);
432            m_nonVisibleScrollJobs.remove(i);
433            --i;
434        }
435    }
436
437    // Do the same for the completed list.
438    for (size_t i = 0; i < m_nonVisibleScrollJobsCompleted.size(); ++i) {
439        if (visibleTiles.contains(m_nonVisibleScrollJobsCompleted[i])) {
440            ASSERT(!m_visibleScrollJobsCompleted.contains(m_nonVisibleScrollJobsCompleted[i]));
441            m_visibleScrollJobsCompleted.append(m_nonVisibleScrollJobsCompleted[i]);
442            m_nonVisibleScrollJobsCompleted.remove(i);
443            --i;
444        }
445    }
446
447    if (m_visibleScrollJobs.isEmpty() && !m_visibleScrollJobsCompleted.isEmpty())
448        scrollZoomJobsCompleted(m_visibleScrollJobs, &m_visibleScrollJobsCompleted, false /*shouldBlit*/);
449
450    if (m_nonVisibleScrollJobs.isEmpty() && !m_nonVisibleScrollJobsCompleted.isEmpty())
451        scrollZoomJobsCompleted(m_nonVisibleScrollJobs, &m_nonVisibleScrollJobsCompleted, false /*shouldBlit*/);
452
453    // We shouldn't be empty because the early return above and the fact that this
454    // method just shuffles rects from queue to queue hence the total number of
455    // rects in the various queues should be conserved.
456    ASSERT(!isEmpty());
457}
458
459void RenderQueue::backingStoreRectChanging(const Platform::IntRect&, const Platform::IntRect&)
460{
461    // We could empty them here instead of in BackingStorePrivate::setBackingStoreRect(),
462    // but it seems cleaner to do it there and still avoid code to manually move them.
463    ASSERT(m_visibleZoomJobs.isEmpty());
464    ASSERT(m_visibleZoomJobsCompleted.isEmpty());
465    ASSERT(m_visibleScrollJobs.isEmpty());
466    ASSERT(m_visibleScrollJobsCompleted.isEmpty());
467    ASSERT(m_nonVisibleScrollJobs.isEmpty());
468    ASSERT(m_nonVisibleScrollJobsCompleted.isEmpty());
469
470    // Empty the tile-based current batch and merge its remaining region with
471    // the one from other upcoming regular render jobs. We'll pick all of them
472    // up next time renderRegularRenderJobs() is called.
473    m_regularRenderJobsRegion = Platform::IntRectRegion::unionRegions(m_regularRenderJobsRegion, m_currentRegularRenderJobsBatchRegion);
474    m_currentRegularRenderJobsBatchRegion = Platform::IntRectRegion();
475    m_currentRegularRenderJobsBatch.clear();
476}
477
478void RenderQueue::clear(const Platform::IntRectRegion& region, ClearJobsFlags clearJobsFlags)
479{
480    clearRegions(region, clearJobsFlags);
481    clearTileIndexes(tileIndexesFullyContainedInRegion(region, m_parent->frontState()), clearJobsFlags);
482}
483
484void RenderQueue::clear(const TileIndexList& indexes, BackingStoreGeometry* geometry, ClearJobsFlags clearJobsFlags)
485{
486    clearRegions(tileRegion(indexes, geometry), clearJobsFlags);
487    clearTileIndexes(indexes, clearJobsFlags);
488}
489
490void RenderQueue::clearRegions(const Platform::IntRectRegion& region, ClearJobsFlags clearJobsFlags)
491{
492    if (clearJobsFlags & ClearRegularRenderJobs) {
493        m_regularRenderJobsRegion = Platform::IntRectRegion::subtractRegions(m_regularRenderJobsRegion, region);
494        m_currentRegularRenderJobsBatchRegion = Platform::IntRectRegion::subtractRegions(m_currentRegularRenderJobsBatchRegion, region);
495        m_regularRenderJobsNotRenderedRegion = Platform::IntRectRegion::subtractRegions(m_regularRenderJobsNotRenderedRegion, region);
496    }
497}
498
499void RenderQueue::clearTileIndexes(const TileIndexList& indexes, ClearJobsFlags clearJobsFlags)
500{
501    if (m_visibleScrollJobs.isEmpty() && m_nonVisibleScrollJobs.isEmpty())
502        ASSERT(m_visibleScrollJobsCompleted.isEmpty() && m_nonVisibleScrollJobsCompleted.isEmpty());
503
504    // Remove all indexes from all queues that are being marked as cleared.
505    if (clearJobsFlags & ClearIncompleteZoomJobs) {
506        for (size_t i = 0; i < m_visibleZoomJobs.size(); ++i) {
507            if (indexes.contains(m_visibleZoomJobs.at(i))) {
508                m_visibleZoomJobs.remove(i);
509                --i;
510            }
511        }
512    }
513
514    if (clearJobsFlags & ClearIncompleteScrollJobs) {
515        for (size_t i = 0; i < m_visibleScrollJobs.size(); ++i) {
516            if (indexes.contains(m_visibleScrollJobs.at(i))) {
517                m_visibleScrollJobs.remove(i);
518                --i;
519            }
520        }
521
522        for (size_t i = 0; i < m_nonVisibleScrollJobs.size(); ++i) {
523            if (indexes.contains(m_nonVisibleScrollJobs.at(i))) {
524                m_nonVisibleScrollJobs.remove(i);
525                --i;
526            }
527        }
528    }
529
530    if (clearJobsFlags & ClearCompletedJobs) {
531        for (size_t i = 0; i < m_visibleZoomJobsCompleted.size(); ++i) {
532            if (indexes.contains(m_visibleZoomJobsCompleted.at(i))) {
533                m_visibleZoomJobsCompleted.remove(i);
534                --i;
535            }
536        }
537
538        for (size_t i = 0; i < m_visibleScrollJobsCompleted.size(); ++i) {
539            if (indexes.contains(m_visibleScrollJobsCompleted.at(i))) {
540                m_visibleScrollJobsCompleted.remove(i);
541                --i;
542            }
543        }
544
545        for (size_t i = 0; i < m_nonVisibleScrollJobsCompleted.size(); ++i) {
546            if (indexes.contains(m_nonVisibleScrollJobsCompleted.at(i))) {
547                m_nonVisibleScrollJobsCompleted.remove(i);
548                --i;
549            }
550        }
551    }
552
553    if (clearJobsFlags & ClearRegularRenderJobs) {
554        for (size_t i = 0; i < m_currentRegularRenderJobsBatch.size(); ++i) {
555            if (indexes.contains(m_currentRegularRenderJobsBatch.at(i))) {
556                m_currentRegularRenderJobsBatch.remove(i);
557                --i;
558            }
559        }
560    }
561
562    if (m_visibleZoomJobs.isEmpty() && !m_visibleZoomJobsCompleted.isEmpty())
563        scrollZoomJobsCompleted(m_visibleZoomJobs, &m_visibleZoomJobsCompleted, false /*shouldBlit*/);
564
565    if (m_visibleScrollJobs.isEmpty() && !m_visibleScrollJobsCompleted.isEmpty())
566        scrollZoomJobsCompleted(m_visibleScrollJobs, &m_visibleScrollJobsCompleted, false /*shouldBlit*/);
567
568    if (m_nonVisibleScrollJobs.isEmpty() && !m_nonVisibleScrollJobsCompleted.isEmpty())
569        scrollZoomJobsCompleted(m_nonVisibleScrollJobs, &m_nonVisibleScrollJobsCompleted, false /*shouldBlit*/);
570}
571
572bool RenderQueue::regularRenderJobsPreviouslyAttemptedButNotRendered(const Platform::IntRect& rect)
573{
574    return m_regularRenderJobsNotRenderedRegion.isRectInRegion(rect) != Platform::IntRectRegion::NotInRegion;
575}
576
577void RenderQueue::render(bool shouldPerformRegularRenderJobs)
578{
579    // We request a layout here to ensure that we're executing jobs in the correct
580    // order. If we didn't request a layout here then the jobs below could result
581    // in a layout and that layout can alter this queue. So request layout if needed
582    // to ensure that the queues below are in constant state before performing the
583    // next rendering job.
584
585#if DEBUG_RENDER_QUEUE
586    // Start the time measurement.
587    double time = WTF::currentTime();
588#endif
589
590    m_parent->requestLayoutIfNeeded();
591    m_parent->updateTileMatrixIfNeeded();
592
593#if DEBUG_RENDER_QUEUE
594    double elapsed = WTF::currentTime() - time;
595    if (elapsed)
596        Platform::logAlways(Platform::LogLevelCritical, "RenderQueue::render layout elapsed=%f", elapsed);
597#endif
598
599    // Empty the queues in a precise order of priority.
600    if (!m_visibleZoomJobs.isEmpty())
601        renderScrollZoomJobs(&m_visibleZoomJobs, &m_visibleZoomJobsCompleted, true /*allAtOnceIfPossible*/, true /*shouldBlitWhenCompleted*/);
602    else if (!m_visibleScrollJobs.isEmpty())
603        renderScrollZoomJobs(&m_visibleScrollJobs, &m_visibleScrollJobsCompleted, false /*allAtOnceIfPossible*/, true /*shouldBlitWhenCompleted*/);
604    else if (shouldPerformRegularRenderJobs && (!m_currentRegularRenderJobsBatch.isEmpty() || !m_regularRenderJobsRegion.isEmpty())) {
605        bool allAtOnceIfPossible = currentRegularRenderJobBatchUnderPressure();
606        renderRegularRenderJobs(allAtOnceIfPossible);
607    } else if (!m_nonVisibleScrollJobs.isEmpty())
608        renderScrollZoomJobs(&m_nonVisibleScrollJobs, &m_nonVisibleScrollJobsCompleted, false /*allAtOnceIfPossible*/, false /*shouldBlitWhenCompleted*/);
609}
610
611void RenderQueue::renderRegularRenderJobs(bool allAtOnceIfPossible)
612{
613#if DEBUG_RENDER_QUEUE
614    // Start the time measurement.
615    double time = WTF::currentTime();
616#endif
617
618    ASSERT(!m_currentRegularRenderJobsBatch.isEmpty() || !m_regularRenderJobsRegion.isEmpty());
619
620    if (allAtOnceIfPossible && !m_currentRegularRenderJobsBatchRegion.isEmpty()) {
621        // If there is a current batch of jobs already, merge it back into the
622        // whole area so that we will pick up all of it for the next run.
623        m_regularRenderJobsRegion = Platform::IntRectRegion::unionRegions(m_regularRenderJobsRegion, m_currentRegularRenderJobsBatchRegion);
624
625        // Clear this since we're about to render everything.
626        m_currentRegularRenderJobsBatchRegion = Platform::IntRectRegion();
627        m_currentRegularRenderJobsBatch.clear();
628    }
629
630    Platform::IntRect contentsRect = m_parent->expandedContentsRect();
631
632    // Start new batch if needed.
633    if (m_currentRegularRenderJobsBatchRegion.isEmpty()) {
634        // Don't try to render anything outside the whole contents rectangle.
635        m_regularRenderJobsRegion = Platform::IntRectRegion::intersectRegions(m_regularRenderJobsRegion, contentsRect);
636
637        // Split the current regular render job region into tiles.
638        // Discard regions outside of the region covered by these tiles.
639        // They'll be rendered when the geometry changes.
640        m_regularRenderJobsRegion = Platform::IntRectRegion::intersectRegions(m_regularRenderJobsRegion, m_parent->frontState()->backingStoreRect());
641        m_currentRegularRenderJobsBatch = tileIndexesIntersectingRegion(m_regularRenderJobsRegion, m_parent->frontState());
642
643        // Create a region object that will be checked when adding new rects before
644        // this batch has been completed.
645        m_currentRegularRenderJobsBatchRegion = m_regularRenderJobsRegion;
646
647        // Clear the former region since it is now part of this batch.
648        m_regularRenderJobsRegion = Platform::IntRectRegion();
649
650#if DEBUG_RENDER_QUEUE
651        Platform::logAlways(Platform::LogLevelCritical,
652            "RenderQueue::renderRegularRenderJobs batch size is %d!",
653            m_currentRegularRenderJobsBatch.size());
654#endif
655    }
656
657    Platform::IntRectRegion changingRegion = m_currentRegularRenderJobsBatchRegion;
658    Platform::IntRectRegion changingRegionScheduledForLater = m_regularRenderJobsRegion;
659    Platform::IntRectRegion regionNotRenderedThisTime;
660
661    TileIndexList* outstandingJobs = &m_currentRegularRenderJobsBatch;
662    TileIndexList completedJobs;
663    TileIndexList tilesToRender;
664
665    unsigned numberOfAvailableBackBuffers = SurfacePool::globalSurfacePool()->numberOfAvailableBackBuffers();
666
667    while (!outstandingJobs->isEmpty() && numberOfAvailableBackBuffers) {
668        // Render as many tiles at once as we can handle.
669        for (size_t i = 0; i < outstandingJobs->size() && numberOfAvailableBackBuffers; ++i) {
670            TileIndex index = (*outstandingJobs)[i];
671
672            BackingStoreGeometry* geometry = m_parent->frontState();
673            Platform::IntRect tileRect(geometry->originOfTile(index), m_parent->tileSize());
674
675            if (!contentsRect.intersects(tileRect)) {
676                // This is a safety fallback, at this point we should only
677                // encounter tiles outside of the contents rect if we're in
678                // a second run of the same batch and the contents size has
679                // changed since the last run. Otherwise, see the cropping above.
680#if DEBUG_RENDER_QUEUE
681                Platform::logAlways(Platform::LogLevelCritical,
682                    "RenderQueue::renderRegularRenderJobs tile at %s outside of expanded contents rect %s, ignoring.",
683                    tileRect.toString().c_str(),
684                    contentsRect.toString().c_str());
685#endif
686                outstandingJobs->remove(i);
687                --i;
688                m_currentRegularRenderJobsBatchRegion = Platform::IntRectRegion::intersectRegions(m_currentRegularRenderJobsBatchRegion, contentsRect);
689                continue;
690            }
691
692            if (m_parent->shouldSuppressNonVisibleRegularRenderJobs()) {
693                // If a tile is not visible, remember it as not rendered to be
694                // picked up later by updateTilesForScrollOrNotRenderedRegion()
695                // or updateTilesAfterBackingStoreRectChange().
696                Platform::IntRectRegion tileRegionNotRendered;
697
698                if (!m_parent->isTileVisible(index, geometry)) {
699                    tileRegionNotRendered = Platform::IntRectRegion::intersectRegions(tileRect, m_currentRegularRenderJobsBatchRegion);
700                    regionNotRenderedThisTime = Platform::IntRectRegion::unionRegions(regionNotRenderedThisTime, tileRegionNotRendered);
701                }
702
703                if (!tileRegionNotRendered.isEmpty()) {
704#if DEBUG_RENDER_QUEUE
705                    Platform::logAlways(Platform::LogLevelCritical,
706                        "RenderQueue::renderRegularRenderJobs region within %s not completely rendered!",
707                        tileRegionNotRendered.extents().toString().c_str());
708#endif
709                    outstandingJobs->remove(i);
710                    --i;
711                    continue;
712                }
713            }
714
715            tilesToRender.append(index);
716            --numberOfAvailableBackBuffers;
717        }
718
719        if (tilesToRender.isEmpty())
720            break;
721
722        // This will also clear the rendered tiles in outstandingJobs.
723        TileIndexList renderedTiles = m_parent->render(tilesToRender);
724
725        // Update number of available back buffers now that we've used them.
726        numberOfAvailableBackBuffers = SurfacePool::globalSurfacePool()->numberOfAvailableBackBuffers();
727
728        ASSERT(!renderedTiles.isEmpty());
729        if (renderedTiles.isEmpty()) {
730#if DEBUG_RENDER_QUEUE
731            Platform::logAlways(Platform::LogLevelCritical,
732                "RenderQueue::renderRegularRenderJobs no tiles rendered (%d attempted), available back buffers: %d",
733                tilesToRender.size(),
734                numberOfAvailableBackBuffers);
735#endif
736            break; // Something bad happened, make sure not to try again for now.
737        }
738
739        for (size_t i = 0; i < renderedTiles.size(); ++i) {
740            if (!completedJobs.contains(renderedTiles[i]))
741                completedJobs.append(renderedTiles[i]);
742        }
743
744        if (!allAtOnceIfPossible)
745            break; // We can do the rest next time.
746    }
747
748    const Platform::IntRectRegion renderedRegion = tileRegion(completedJobs, m_parent->frontState());
749
750    m_regularRenderJobsNotRenderedRegion = Platform::IntRectRegion::unionRegions(m_regularRenderJobsNotRenderedRegion, regionNotRenderedThisTime);
751    m_currentRegularRenderJobsBatchRegion = Platform::IntRectRegion::subtractRegions(m_currentRegularRenderJobsBatchRegion, regionNotRenderedThisTime);
752
753#if DEBUG_RENDER_QUEUE
754    // Stop the time measurement.
755    double elapsed = WTF::currentTime() - time;
756    Platform::logAlways(Platform::LogLevelCritical,
757        "RenderQueue::renderRegularRenderJobs within %s: completed = %d, outstanding = %d, elapsed=%f",
758        changingRegion.extents().toString().c_str(),
759        completedJobs.size(),
760        outstandingJobs->size(),
761        elapsed);
762#endif
763
764    // Make sure we didn't alter state of the queues that should have been empty
765    // before this method was called.
766    ASSERT(m_visibleZoomJobs.isEmpty());
767    ASSERT(m_visibleScrollJobs.isEmpty());
768
769    if (m_currentRegularRenderJobsBatchRegion.isEmpty()) {
770        // If the whole scheduled area has been rendered, all outstanding jobs
771        // should have been cleared as well.
772        ASSERT(outstandingJobs->isEmpty());
773        m_currentRegularRenderJobsBatchUnderPressure = false;
774
775        // Notify about the newly rendered content.
776        // In case we picked up an unfinished batch from before, because we
777        // paint a larger area it's possible that we also rendered other
778        // regions that were originally scheduled for later.
779        Platform::IntRectRegion wholeScheduledRegion = Platform::IntRectRegion::unionRegions(changingRegion, changingRegionScheduledForLater);
780        Platform::IntRectRegion renderedChangedRegion = Platform::IntRectRegion::intersectRegions(wholeScheduledRegion, renderedRegion);
781
782        // Blit since this batch is now complete.
783        m_parent->didRenderContent(renderedChangedRegion);
784    }
785
786    if (m_parent->shouldSuppressNonVisibleRegularRenderJobs() && !regionNotRenderedThisTime.isEmpty())
787        m_parent->updateTilesForScrollOrNotRenderedRegion(false /*checkLoading*/);
788}
789
790void RenderQueue::renderScrollZoomJobs(TileIndexList* outstandingJobs, TileIndexList* completedJobs, bool allAtOnceIfPossible, bool shouldBlitWhenCompleted)
791{
792    ASSERT(!outstandingJobs->isEmpty());
793
794#if DEBUG_RENDER_QUEUE || DEBUG_RENDER_QUEUE_SORT
795    // Start the time measurement.
796    double time = WTF::currentTime();
797    double elapsed;
798#endif
799
800    Platform::IntRect contentsRect = m_parent->expandedContentsRect();
801
802    unsigned numberOfAvailableBackBuffers = SurfacePool::globalSurfacePool()->numberOfAvailableBackBuffers();
803
804    // If we take multiple turns to render, we sort to make them appear in the right order.
805    if (!allAtOnceIfPossible && outstandingJobs->size() > numberOfAvailableBackBuffers)
806        quickSort(outstandingJobs);
807
808#if DEBUG_RENDER_QUEUE_SORT
809    // Stop the time measurement
810    elapsed = WTF::currentTime() - time;
811    Platform::logAlways(Platform::LogLevelCritical, "RenderQueue::renderScrollZoomJobs sort elapsed=%f", elapsed);
812#endif
813
814    TileIndexList tilesToRender;
815
816    while (!outstandingJobs->isEmpty() && numberOfAvailableBackBuffers) {
817        // Render as many tiles at once as we can handle.
818        for (size_t i = 0; i < outstandingJobs->size() && numberOfAvailableBackBuffers; ++i) {
819            TileIndex index = (*outstandingJobs)[i];
820            Platform::IntRect tileRect(m_parent->frontState()->originOfTile(index), m_parent->tileSize());
821
822            // Make sure we only try to render tiles containing contents.
823            if (!contentsRect.intersects(tileRect)) {
824#if DEBUG_RENDER_QUEUE
825                Platform::logAlways(Platform::LogLevelCritical,
826                    "RenderQueue::renderScrollZoomJobs tile at %s outside of expanded contents rect %s, ignoring.",
827                    tileRect.toString().c_str(),
828                    contentsRect.toString().c_str());
829#endif
830                outstandingJobs->remove(i);
831                --i;
832                continue;
833            }
834
835            tilesToRender.append((*outstandingJobs)[i]);
836            --numberOfAvailableBackBuffers;
837        }
838
839        if (tilesToRender.isEmpty())
840            break;
841
842        // This will clear the rendered tiles in outstandingJobs.
843        TileIndexList renderedTiles = m_parent->render(tilesToRender);
844
845        // Update number of available back buffers now that we've used them.
846        numberOfAvailableBackBuffers = SurfacePool::globalSurfacePool()->numberOfAvailableBackBuffers();
847
848        ASSERT(!renderedTiles.isEmpty());
849        if (renderedTiles.isEmpty()) {
850#if DEBUG_RENDER_QUEUE
851            Platform::logAlways(Platform::LogLevelCritical,
852                "RenderQueue::renderScrollZoomJobs no tiles rendered (%d attempted, available back buffers: %d)",
853                tilesToRender.size(),
854                numberOfAvailableBackBuffers);
855#endif
856            break; // Something bad happened, make sure not to try again for now.
857        }
858
859        for (size_t i = 0; i < renderedTiles.size(); ++i) {
860            if (!completedJobs->contains(renderedTiles[i]))
861                completedJobs->append(renderedTiles[i]);
862        }
863
864        if (!allAtOnceIfPossible)
865            break; // We can do the rest next time.
866    }
867
868#if DEBUG_RENDER_QUEUE
869    // Stop the time measurement.
870    elapsed = WTF::currentTime() - time;
871    Platform::logAlways(Platform::LogLevelCritical,
872        "RenderQueue::renderScrollZoomJobs completed=%d, outstanding=%d, elapsed=%f",
873        completedJobs->size(),
874        outstandingJobs->size(),
875        elapsed);
876#endif
877
878    if (outstandingJobs->isEmpty())
879        scrollZoomJobsCompleted(*outstandingJobs, completedJobs, shouldBlitWhenCompleted);
880}
881
882void RenderQueue::scrollZoomJobsCompleted(const TileIndexList& outstandingJobs, TileIndexList* completedJobs, bool shouldBlit)
883{
884    // Get rid of the completed list!
885    ASSERT(outstandingJobs.isEmpty());
886    completedJobs->clear();
887
888    // Now blit to the screen if we are done!
889    if (shouldBlit)
890        m_parent->didRenderContent(m_parent->visibleContentsRect());
891}
892
893} // namespace WebKit
894} // namespace BlackBerry
895