1/*
2 * Copyright 2007, The Android Open Source Project
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 *  * Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 *  * 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 THE COPYRIGHT HOLDERS ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "CachedPrefix.h"
27#include "android_graphics.h"
28#include "CachedHistory.h"
29#include "CachedInput.h"
30#include "CachedNode.h"
31#include "FindCanvas.h"
32#include "FloatRect.h"
33#include "LayerAndroid.h"
34#include "SkBitmap.h"
35#include "SkBounder.h"
36#include "SkPixelRef.h"
37#include "SkRegion.h"
38
39#include "CachedRoot.h"
40
41using std::min;
42using std::max;
43
44#ifdef DUMP_NAV_CACHE_USING_PRINTF
45    extern android::Mutex gWriteLogMutex;
46#endif
47
48namespace android {
49
50class CommonCheck : public SkBounder {
51public:
52    enum Type {
53        kNo_Type,
54        kDrawBitmap_Type,
55        kDrawGlyph_Type,
56        kDrawPaint_Type,
57        kDrawPath_Type,
58        kDrawPicture_Type,
59        kDrawPoints_Type,
60        kDrawPosText_Type,
61        kDrawPosTextH_Type,
62        kDrawRect_Type,
63        kDrawSprite_Type,
64        kDrawText_Type,
65        kDrawTextOnPath_Type
66    };
67
68    static bool isTextType(Type t) {
69        return t == kDrawPosTextH_Type || t == kDrawText_Type;
70    }
71
72    CommonCheck() : mType(kNo_Type), mAllOpaque(true), mIsOpaque(true) {
73        setEmpty();
74    }
75
76    bool doRect(Type type) {
77        mType = type;
78        return doIRect(mUnion);
79    }
80
81    bool joinGlyphs(const SkIRect& rect) {
82        bool isGlyph = mType == kDrawGlyph_Type;
83        if (isGlyph)
84            mUnion.join(rect);
85        return isGlyph;
86    }
87
88    void setAllOpaque(bool opaque) { mAllOpaque = opaque; }
89    void setEmpty() { mUnion.setEmpty(); }
90    void setIsOpaque(bool opaque) { mIsOpaque = opaque; }
91    void setType(Type type) { mType = type; }
92
93    Type mType;
94    SkIRect mUnion;
95    bool mAllOpaque;
96    bool mIsOpaque;
97};
98
99#if DEBUG_NAV_UI
100    static const char* TypeNames[] = {
101        "kNo_Type",
102        "kDrawBitmap_Type",
103        "kDrawGlyph_Type",
104        "kDrawPaint_Type",
105        "kDrawPath_Type",
106        "kDrawPicture_Type",
107        "kDrawPoints_Type",
108        "kDrawPosText_Type",
109        "kDrawPosTextH_Type",
110        "kDrawRect_Type",
111        "kDrawSprite_Type",
112        "kDrawText_Type",
113        "kDrawTextOnPath_Type"
114    };
115#endif
116
117#define kMargin 16
118#define kSlop 2
119
120class BoundsCheck : public CommonCheck {
121public:
122    BoundsCheck() {
123        mAllDrawnIn.setEmpty();
124        mLastAll.setEmpty();
125        mLastOver.setEmpty();
126    }
127
128    static int Area(SkIRect test) {
129        return test.width() * test.height();
130    }
131
132   void checkLast() {
133        if (mAllDrawnIn.isEmpty())
134            return;
135        if (mLastAll.isEmpty() || Area(mLastAll) < Area(mAllDrawnIn)) {
136            mLastAll = mAllDrawnIn;
137            mDrawnOver.setEmpty();
138        }
139        mAllDrawnIn.setEmpty();
140    }
141
142    bool hidden() {
143        return (mLastAll.isEmpty() && mLastOver.isEmpty()) ||
144            mDrawnOver.contains(mBounds);
145    }
146
147    virtual bool onIRect(const SkIRect& rect) {
148        if (joinGlyphs(rect))
149            return false;
150        bool interestingType = mType == kDrawBitmap_Type ||
151            mType == kDrawRect_Type || isTextType(mType);
152        if (SkIRect::Intersects(mBounds, rect) == false) {
153            DBG_NAV_LOGD("BoundsCheck (no intersect) rect={%d,%d,%d,%d}"
154                " mType=%s", rect.fLeft, rect.fTop, rect.fRight, rect.fBottom,
155                TypeNames[mType]);
156            if (interestingType)
157                checkLast();
158            return false;
159        }
160        if (interestingType == false)
161            return false;
162        if (!mDrawnOver.contains(rect) && (mBoundsSlop.contains(rect) ||
163                (mBounds.fLeft == rect.fLeft && mBounds.fRight == rect.fRight &&
164                mBounds.fTop >= rect.fTop && mBounds.fBottom <= rect.fBottom) ||
165                (mBounds.fTop == rect.fTop && mBounds.fBottom == rect.fBottom &&
166                mBounds.fLeft >= rect.fLeft && mBounds.fRight <= rect.fRight))) {
167            mDrawnOver.setEmpty();
168            mAllDrawnIn.join(rect);
169            DBG_NAV_LOGD("BoundsCheck (contains) rect={%d,%d,%d,%d}"
170                " mAllDrawnIn={%d,%d,%d,%d} mType=%s",
171                rect.fLeft, rect.fTop, rect.fRight, rect.fBottom,
172                mAllDrawnIn.fLeft, mAllDrawnIn.fTop, mAllDrawnIn.fRight,
173                mAllDrawnIn.fBottom, TypeNames[mType]);
174       } else {
175            checkLast();
176            if (!isTextType(mType)) {
177                if (
178#if 0
179// should the opaqueness of the bitmap disallow its ability to draw over?
180// not sure that this test is needed
181                (mType != kDrawBitmap_Type ||
182                        (mIsOpaque && mAllOpaque)) &&
183#endif
184                        mLastAll.isEmpty() == false)
185                    mDrawnOver.op(rect, SkRegion::kUnion_Op);
186            } else {
187// FIXME
188// sometimes the text is not drawn entirely inside the cursor area, even though
189// it is the correct text. Until I figure out why, I allow text drawn at the
190// end that is not covered up by something else to represent the link
191// example that triggers this that should be figured out:
192// http://cdn.labpixies.com/campaigns/blackjack/blackjack.html?lang=en&country=US&libs=assets/feature/core
193// ( http://tinyurl.com/ywsyzb )
194                mLastOver = rect;
195            }
196#if DEBUG_NAV_UI
197        const SkIRect& drawnOver = mDrawnOver.getBounds();
198        DBG_NAV_LOGD("(overlaps) rect={%d,%d,%d,%d}"
199            " mDrawnOver={%d,%d,%d,%d} mType=%s mIsOpaque=%s mAllOpaque=%s",
200            rect.fLeft, rect.fTop, rect.fRight, rect.fBottom,
201            drawnOver.fLeft, drawnOver.fTop, drawnOver.fRight, drawnOver.fBottom,
202            TypeNames[mType], mIsOpaque ? "true" : "false",
203            mAllOpaque ? "true" : "false");
204#endif
205        }
206        return false;
207    }
208
209    SkIRect mBounds;
210    SkIRect mBoundsSlop;
211    SkRegion mDrawnOver;
212    SkIRect mLastOver;
213    SkIRect mAllDrawnIn;
214    SkIRect mLastAll;
215};
216
217class BoundsCanvas : public SkCanvas {
218public:
219
220    BoundsCanvas(CommonCheck* bounder) : mBounder(*bounder) {
221        mTransparentLayer = 0;
222        setBounder(bounder);
223    }
224
225    virtual ~BoundsCanvas() {
226        setBounder(NULL);
227    }
228
229    virtual void drawPaint(const SkPaint& paint) {
230        mBounder.setType(CommonCheck::kDrawPaint_Type);
231        SkCanvas::drawPaint(paint);
232    }
233
234    virtual void drawPoints(PointMode mode, size_t count, const SkPoint pts[],
235                            const SkPaint& paint) {
236        mBounder.setType(CommonCheck::kDrawPoints_Type);
237        SkCanvas::drawPoints(mode, count, pts, paint);
238    }
239
240    virtual void drawRect(const SkRect& rect, const SkPaint& paint) {
241        mBounder.setType(CommonCheck::kDrawRect_Type);
242        SkCanvas::drawRect(rect, paint);
243    }
244
245    virtual void drawPath(const SkPath& path, const SkPaint& paint) {
246        mBounder.setType(CommonCheck::kDrawPath_Type);
247        SkCanvas::drawPath(path, paint);
248    }
249
250    virtual void commonDrawBitmap(const SkBitmap& bitmap,
251                              const SkMatrix& matrix, const SkPaint& paint) {
252        mBounder.setType(CommonCheck::kDrawBitmap_Type);
253        mBounder.setIsOpaque(bitmap.isOpaque());
254        SkCanvas::commonDrawBitmap(bitmap, matrix, paint);
255    }
256
257    virtual void drawSprite(const SkBitmap& bitmap, int left, int top,
258                            const SkPaint* paint = NULL) {
259        mBounder.setType(CommonCheck::kDrawSprite_Type);
260        mBounder.setIsOpaque(bitmap.isOpaque());
261        SkCanvas::drawSprite(bitmap, left, top, paint);
262    }
263
264    virtual void drawText(const void* text, size_t byteLength, SkScalar x,
265                          SkScalar y, const SkPaint& paint) {
266        mBounder.setEmpty();
267        mBounder.setType(CommonCheck::kDrawGlyph_Type);
268        SkCanvas::drawText(text, byteLength, x, y, paint);
269        mBounder.doRect(CommonCheck::kDrawText_Type);
270    }
271
272    virtual void drawPosText(const void* text, size_t byteLength,
273                             const SkPoint pos[], const SkPaint& paint) {
274        mBounder.setEmpty();
275        mBounder.setType(CommonCheck::kDrawGlyph_Type);
276        SkCanvas::drawPosText(text, byteLength, pos, paint);
277        mBounder.doRect(CommonCheck::kDrawPosText_Type);
278    }
279
280    virtual void drawPosTextH(const void* text, size_t byteLength,
281                              const SkScalar xpos[], SkScalar constY,
282                              const SkPaint& paint) {
283        mBounder.setEmpty();
284        mBounder.setType(CommonCheck::kDrawGlyph_Type);
285        SkCanvas::drawPosTextH(text, byteLength, xpos, constY, paint);
286        if (mBounder.mUnion.isEmpty())
287            return;
288        SkPaint::FontMetrics metrics;
289        paint.getFontMetrics(&metrics);
290        SkPoint upDown[2] = { {xpos[0], constY + metrics.fAscent},
291            {xpos[0], constY + metrics.fDescent} };
292        const SkMatrix& matrix = getTotalMatrix();
293        matrix.mapPoints(upDown, 2);
294        if (upDown[0].fX == upDown[1].fX) {
295            mBounder.mUnion.fTop = SkScalarFloor(upDown[0].fY);
296            mBounder.mUnion.fBottom = SkScalarFloor(upDown[1].fY);
297        }
298        mBounder.doRect(CommonCheck::kDrawPosTextH_Type);
299    }
300
301    virtual void drawTextOnPath(const void* text, size_t byteLength,
302                                const SkPath& path, const SkMatrix* matrix,
303                                const SkPaint& paint) {
304        mBounder.setEmpty();
305        mBounder.setType(CommonCheck::kDrawGlyph_Type);
306        SkCanvas::drawTextOnPath(text, byteLength, path, matrix, paint);
307        mBounder.doRect(CommonCheck::kDrawTextOnPath_Type);
308    }
309
310    virtual void drawPicture(SkPicture& picture) {
311        mBounder.setType(CommonCheck::kDrawPicture_Type);
312        SkCanvas::drawPicture(picture);
313    }
314
315    virtual int saveLayer(const SkRect* bounds, const SkPaint* paint,
316                          SaveFlags flags) {
317        int depth = SkCanvas::saveLayer(bounds, paint, flags);
318        if (mTransparentLayer == 0 && paint && paint->getAlpha() < 255) {
319            mTransparentLayer = depth;
320            mBounder.setAllOpaque(false);
321        }
322        return depth;
323    }
324
325    virtual void restore() {
326        int depth = getSaveCount();
327        if (depth == mTransparentLayer) {
328            mTransparentLayer = 0;
329            mBounder.setAllOpaque(true);
330        }
331        SkCanvas::restore();
332    }
333
334    int mTransparentLayer;
335    CommonCheck& mBounder;
336};
337
338/*
339LeftCheck examines the text in a picture, within a viewable rectangle,
340and returns via left() the position of the left edge of the paragraph.
341It first looks at the left edge of the test point, then looks above and below
342it for more lines of text to determine the div's left edge.
343*/
344class LeftCheck : public CommonCheck {
345public:
346    LeftCheck(int x, int y) : mX(x), mY(y), mHitLeft(INT_MAX),
347            mMostLeft(INT_MAX) {
348        mHit.set(x - (HIT_SLOP << 1), y - HIT_SLOP, x, y + HIT_SLOP);
349        mPartial.setEmpty();
350        mBounds.setEmpty();
351        mPartialType = kNo_Type;
352    }
353
354    int left() {
355        if (isTextType(mType))
356            doRect(); // process the final line of text
357        return mMostLeft != INT_MAX ? mMostLeft : mX >> 1;
358    }
359
360    // FIXME: this is identical to CenterCheck::onIRect()
361    // refactor so that LeftCheck and CenterCheck inherit common functions
362    virtual bool onIRect(const SkIRect& rect) {
363        bool opaqueBitmap = mType == kDrawBitmap_Type && mIsOpaque;
364        if (opaqueBitmap && rect.contains(mX, mY)) {
365            mMostLeft = rect.fLeft;
366            return false;
367        }
368        if (joinGlyphs(rect)) // assembles glyphs into a text string
369            return false;
370        if (!isTextType(mType) && !opaqueBitmap)
371            return false;
372        /* Text on one line may be broken into several parts. Reassemble
373           the text into a rectangle before considering it. */
374        if (rect.fTop < mPartial.fBottom
375                && rect.fBottom > mPartial.fTop
376                && mPartial.fRight + SLOP >= rect.fLeft
377                && (mPartialType != kDrawBitmap_Type
378                || mPartial.height() <= rect.height() + HIT_SLOP)) {
379            DBG_NAV_LOGD("LeftCheck join mPartial=(%d, %d, %d, %d)"
380                " rect=(%d, %d, %d, %d)",
381                mPartial.fLeft, mPartial.fTop, mPartial.fRight, mPartial.fBottom,
382                rect.fLeft, rect.fTop, rect.fRight, rect.fBottom);
383            mPartial.join(rect);
384            return false;
385        }
386        if (mPartial.isEmpty() == false) {
387            doRect(); // process the previous line of text
388#if DEBUG_NAV_UI
389            if (mHitLeft == INT_MAX)
390                DBG_NAV_LOGD("LeftCheck disabled rect=(%d, %d, %d, %d)",
391                    rect.fLeft, rect.fTop, rect.fRight, rect.fBottom);
392#endif
393        }
394        mPartial = rect;
395        mPartialType = mType;
396        return false;
397    }
398
399    void doRect()
400    {
401        /* Record the outer bounds of the lines of text that intersect the
402           touch coordinates, given some slop */
403        if (SkIRect::Intersects(mPartial, mHit)) {
404            if (mHitLeft > mPartial.fLeft)
405                mHitLeft = mPartial.fLeft;
406            DBG_NAV_LOGD("LeftCheck mHitLeft=%d", mHitLeft);
407        } else if (mHitLeft == INT_MAX)
408            return; // wait for intersect success
409        /* If text is too far away vertically, don't consider it */
410        if (!mBounds.isEmpty() && (mPartial.fTop > mBounds.fBottom + SLOP
411                || mPartial.fBottom < mBounds.fTop - SLOP)) {
412            DBG_NAV_LOGD("LeftCheck stop mPartial=(%d, %d, %d, %d)"
413                " mBounds=(%d, %d, %d, %d)",
414                mPartial.fLeft, mPartial.fTop, mPartial.fRight, mPartial.fBottom,
415                mBounds.fLeft, mBounds.fTop, mBounds.fRight, mBounds.fBottom);
416            mHitLeft = INT_MAX; // and disable future comparisons
417            return;
418        }
419        /* If the considered text is completely to the left or right of the
420           touch coordinates, skip it, turn off further detection */
421        if (mPartial.fLeft > mX || mPartial.fRight < mX) {
422            DBG_NAV_LOGD("LeftCheck stop mX=%d mPartial=(%d, %d, %d, %d)", mX,
423                mPartial.fLeft, mPartial.fTop, mPartial.fRight, mPartial.fBottom);
424            mHitLeft = INT_MAX;
425            return;
426        }
427        /* record the smallest margins on the left and right */
428        if (mMostLeft > mPartial.fLeft) {
429            DBG_NAV_LOGD("LeftCheck new mMostLeft=%d (old=%d)", mPartial.fLeft,
430                mMostLeft);
431            mMostLeft = mPartial.fLeft;
432        }
433        if (mBounds.isEmpty())
434            mBounds = mPartial;
435        else if (mPartial.fBottom > mBounds.fBottom) {
436            DBG_NAV_LOGD("LeftCheck new bottom=%d (old=%d)", mPartial.fBottom,
437                mBounds.fBottom);
438            mBounds.fBottom = mPartial.fBottom;
439        }
440    }
441
442    static const int HIT_SLOP = 5; // space between text parts and lines
443    static const int SLOP = 30; // space between text parts and lines
444    /* const */ SkIRect mHit; // sloppy hit rectangle
445    SkIRect mBounds; // reference bounds
446    SkIRect mPartial; // accumulated text bounds, per line
447    const int mX; // touch location
448    const int mY;
449    int mHitLeft; // touched text extremes
450    int mMostLeft; // paragraph extremes
451    Type mPartialType;
452};
453
454/*
455CenterCheck examines the text in a picture, within a viewable rectangle,
456and returns via center() the optimal amount to scroll in x to display the
457paragraph of text.
458
459The caller of CenterCheck has configured (but not allocated) a bitmap
460the height and three times the width of the view. The picture is drawn centered
461in the bitmap, so text that would be revealed, if the view was scrolled up to
462a view-width to the left or right, is considered.
463*/
464class CenterCheck : public CommonCheck {
465public:
466    CenterCheck(int x, int y, int width) : mX(x), mY(y),
467            mHitLeft(x), mHitRight(x), mMostLeft(INT_MAX), mMostRight(-INT_MAX),
468            mViewLeft(width), mViewRight(width << 1) {
469        mHit.set(x - CENTER_SLOP, y - CENTER_SLOP,
470            x + CENTER_SLOP, y + CENTER_SLOP);
471        mPartial.setEmpty();
472    }
473
474    int center() {
475        doRect(); // process the final line of text
476        /* If the touch coordinates aren't near any text, return 0 */
477        if (mHitLeft == mHitRight) {
478            DBG_NAV_LOGD("abort: mHitLeft=%d ==mHitRight", mHitLeft);
479            return 0;
480        }
481        int leftOver = mHitLeft - mViewLeft;
482        int rightOver = mHitRight - mViewRight;
483        int center;
484        /* If the touched text is too large to entirely fit on the screen,
485           center it. */
486        if (leftOver < 0 && rightOver > 0) {
487            center = (leftOver + rightOver) >> 1;
488            DBG_NAV_LOGD("overlap: leftOver=%d rightOver=%d center=%d",
489                leftOver, rightOver, center);
490            return center;
491        }
492        center = (mMostLeft + mMostRight) >> 1; // the paragraph center
493        if (leftOver > 0 && rightOver >= 0) { // off to the right
494            if (center > mMostLeft) // move to center loses left-most text?
495                center = mMostLeft;
496        } else if (rightOver < 0 && leftOver <= 0) { // off to the left
497            if (center < mMostRight) // move to center loses right-most text?
498                center = mMostRight;
499        } else {
500#ifdef DONT_CENTER_IF_ALREADY_VISIBLE
501            center = 0; // paragraph is already fully visible
502#endif
503        }
504        DBG_NAV_LOGD("scroll: leftOver=%d rightOver=%d center=%d",
505            leftOver, rightOver, center);
506        return center;
507    }
508
509protected:
510    virtual bool onIRect(const SkIRect& rect) {
511        if (joinGlyphs(rect)) // assembles glyphs into a text string
512            return false;
513        if (!isTextType(mType))
514            return false;
515        /* Text on one line may be broken into several parts. Reassemble
516           the text into a rectangle before considering it. */
517        if (rect.fTop < mPartial.fBottom && rect.fBottom >
518                mPartial.fTop && mPartial.fRight + CENTER_SLOP >= rect.fLeft) {
519            DBG_NAV_LOGD("join mPartial=(%d, %d, %d, %d) rect=(%d, %d, %d, %d)",
520                mPartial.fLeft, mPartial.fTop, mPartial.fRight, mPartial.fBottom,
521                rect.fLeft, rect.fTop, rect.fRight, rect.fBottom);
522            mPartial.join(rect);
523            return false;
524        }
525        if (mPartial.isEmpty() == false)
526            doRect(); // process the previous line of text
527        mPartial = rect;
528        return false;
529    }
530
531    void doRect()
532    {
533        /* Record the outer bounds of the lines of text that was 'hit' by the
534           touch coordinates, given some slop */
535        if (SkIRect::Intersects(mPartial, mHit)) {
536            if (mHitLeft > mPartial.fLeft)
537                mHitLeft = mPartial.fLeft;
538            if (mHitRight < mPartial.fRight)
539                mHitRight = mPartial.fRight;
540            DBG_NAV_LOGD("mHitLeft=%d mHitRight=%d", mHitLeft, mHitRight);
541        }
542        /* If the considered text is completely to the left or right of the
543           touch coordinates, skip it */
544        if (mPartial.fLeft > mX || mPartial.fRight < mX)
545            return;
546        int leftOver = mPartial.fLeft - mViewLeft;
547        int rightOver = mPartial.fRight - mViewRight;
548        /* If leftOver <= 0, the text starts off the screen.
549           If rightOver >= 0, the text ends off the screen.
550        */
551        if (leftOver <= 0 && rightOver >= 0) // discard wider than screen
552            return;
553#ifdef DONT_CENTER_IF_ALREADY_VISIBLE
554        if (leftOver > 0 && rightOver < 0)   // discard already visible
555            return;
556#endif
557        /* record the smallest margins on the left and right */
558        if (mMostLeft > leftOver)
559            mMostLeft = leftOver;
560        if (mMostRight < rightOver)
561            mMostRight = rightOver;
562        DBG_NAV_LOGD("leftOver=%d rightOver=%d mMostLeft=%d mMostRight=%d",
563            leftOver, rightOver, mMostLeft, mMostRight);
564    }
565
566    static const int CENTER_SLOP = 10; // space between text parts and lines
567    /* const */ SkIRect mHit; // sloppy hit rectangle
568    SkIRect mPartial; // accumulated text bounds, per line
569    const int mX; // touch location
570    const int mY;
571    int mHitLeft; // touched text extremes
572    int mHitRight;
573    int mMostLeft; // paragraph extremes
574    int mMostRight;
575    const int mViewLeft; // middle third of 3x-wide view
576    const int mViewRight;
577};
578
579class ImageCanvas : public SkCanvas {
580public:
581    ImageCanvas(SkBounder* bounder) : mURI(NULL) {
582        setBounder(bounder);
583    }
584
585// Currently webkit's bitmap draws always seem to be cull'd before this entry
586// point is called, so we assume that any bitmap that gets here is inside our
587// tiny clip (may not be true in the future)
588    virtual void commonDrawBitmap(const SkBitmap& bitmap,
589                              const SkMatrix& , const SkPaint& ) {
590        SkPixelRef* pixelRef = bitmap.pixelRef();
591        if (pixelRef != NULL) {
592            mURI = pixelRef->getURI();
593        }
594    }
595
596    const char* mURI;
597};
598
599class ImageCheck : public SkBounder {
600public:
601    virtual bool onIRect(const SkIRect& rect) {
602        return false;
603    }
604};
605
606class JiggleCheck : public CommonCheck {
607public:
608    JiggleCheck(int delta, int width) : mDelta(delta), mMaxX(width) {
609        mMaxJiggle = 0;
610        mMinX = mMinJiggle = abs(delta);
611        mMaxWidth = width + mMinX;
612    }
613
614    int jiggle() {
615        if (mMinJiggle > mMaxJiggle)
616            return mDelta;
617        int avg = (mMinJiggle + mMaxJiggle + 1) >> 1;
618        return mDelta < 0 ? -avg : avg;
619    }
620
621    virtual bool onIRect(const SkIRect& rect) {
622        if (joinGlyphs(rect))
623            return false;
624        if (mType != kDrawBitmap_Type && !isTextType(mType))
625            return false;
626        int min, max;
627        if (mDelta < 0) {
628            min = mMinX - rect.fLeft;
629            max = mMaxWidth - rect.fRight;
630        } else {
631            min = rect.fRight - mMaxX;
632            max = rect.fLeft;
633        }
634        if (min <= 0)
635            return false;
636        if (max >= mMinX)
637            return false;
638        if (mMinJiggle > min)
639            mMinJiggle = min;
640        if (mMaxJiggle < max)
641            mMaxJiggle = max;
642        return false;
643    }
644
645    int mDelta;
646    int mMaxJiggle;
647    int mMaxX;
648    int mMinJiggle;
649    int mMinX;
650    int mMaxWidth;
651};
652
653class RingCheck : public CommonCheck {
654public:
655    RingCheck(const WTF::Vector<WebCore::IntRect>& rings,
656            const WebCore::IntPoint& location) : mSuccess(true) {
657        const WebCore::IntRect* r;
658        for (r = rings.begin(); r != rings.end(); r++) {
659            SkIRect fatter = {r->x(), r->y(), r->right(), r->bottom()};
660            fatter.inset(-CURSOR_RING_HIT_TEST_RADIUS, -CURSOR_RING_HIT_TEST_RADIUS);
661            DBG_NAV_LOGD("fat=(%d,%d,r=%d,b=%d)", fatter.fLeft, fatter.fTop,
662                fatter.fRight, fatter.fBottom);
663            mRings.op(fatter, SkRegion::kUnion_Op);
664        }
665        DBG_NAV_LOGD("translate=(%d,%d)", -location.x(), -location.y());
666        mRings.translate(-location.x(), -location.y());
667    }
668
669    virtual bool onIRect(const SkIRect& rect) {
670        if (mSuccess && mType == kDrawGlyph_Type) {
671            DBG_NAV_LOGD("contains (%d,%d,r=%d,b=%d) == %s",
672                rect.fLeft, rect.fTop, rect.fRight, rect.fBottom,
673                mRings.contains(rect) ? "true" : "false");
674            mSuccess &= mRings.contains(rect);
675        }
676        return false;
677    }
678
679    bool success() { return mSuccess; }
680    SkRegion mRings;
681    bool mSuccess;
682};
683
684bool CachedRoot::adjustForScroll(BestData* best, CachedFrame::Direction direction,
685    WebCore::IntPoint* scrollPtr, bool findClosest)
686{
687    WebCore::IntRect newOutset;
688    const CachedNode* newNode = best->mNode;
689    // see if there's a middle node
690        // if the middle node is in the visited list,
691        // or if none was computed and the newNode is in the visited list,
692        // treat result as NULL
693    if (newNode != NULL && findClosest) {
694        if (best->bounds().intersects(mHistory->mPriorBounds) == false &&
695                checkBetween(best, direction))
696            newNode = best->mNode;
697        if (findClosest && maskIfHidden(best)) {
698            innerMove(document(), best, direction, scrollPtr, false);
699            return true;
700        }
701        newOutset = newNode->cursorRingBounds(best->mFrame);
702    }
703    int delta;
704    bool newNodeInView = scrollDelta(newOutset, direction, &delta);
705    if (delta && scrollPtr && (newNode == NULL || newNodeInView == false ||
706            (best->mNavOutside && best->mWorkingOutside)))
707        *scrollPtr = WebCore::IntPoint(direction & UP_DOWN ? 0 : delta,
708            direction & UP_DOWN ? delta : 0);
709    return false;
710}
711
712
713int CachedRoot::checkForCenter(int x, int y) const
714{
715    int width = mViewBounds.width();
716    CenterCheck centerCheck(x + width - mViewBounds.x(), y - mViewBounds.y(),
717        width);
718    BoundsCanvas checker(&centerCheck);
719    SkBitmap bitmap;
720    bitmap.setConfig(SkBitmap::kARGB_8888_Config, width * 3,
721        mViewBounds.height());
722    checker.setBitmapDevice(bitmap);
723    checker.translate(SkIntToScalar(width - mViewBounds.x()),
724        SkIntToScalar(-mViewBounds.y()));
725    checker.drawPicture(*pictureAt(x, y));
726    return centerCheck.center();
727}
728
729void CachedRoot::checkForJiggle(int* xDeltaPtr) const
730{
731    int xDelta = *xDeltaPtr;
732    JiggleCheck jiggleCheck(xDelta, mViewBounds.width());
733    BoundsCanvas checker(&jiggleCheck);
734    SkBitmap bitmap;
735    int absDelta = abs(xDelta);
736    bitmap.setConfig(SkBitmap::kARGB_8888_Config, mViewBounds.width() +
737        absDelta, mViewBounds.height());
738    checker.setBitmapDevice(bitmap);
739    int x = -mViewBounds.x() - (xDelta < 0 ? xDelta : 0);
740    int y = -mViewBounds.y();
741    checker.translate(SkIntToScalar(x), SkIntToScalar(y));
742    checker.drawPicture(*pictureAt(x, y));
743    *xDeltaPtr = jiggleCheck.jiggle();
744}
745
746bool CachedRoot::checkRings(SkPicture* picture,
747        const WTF::Vector<WebCore::IntRect>& rings,
748        const WebCore::IntRect& bounds) const
749{
750    if (!picture)
751        return false;
752    RingCheck ringCheck(rings, bounds.location());
753    BoundsCanvas checker(&ringCheck);
754    SkBitmap bitmap;
755    bitmap.setConfig(SkBitmap::kARGB_8888_Config, bounds.width(),
756        bounds.height());
757    checker.setBitmapDevice(bitmap);
758    checker.translate(SkIntToScalar(-bounds.x()), SkIntToScalar(-bounds.y()));
759    checker.drawPicture(*picture);
760    DBG_NAV_LOGD("bounds=(%d,%d,r=%d,b=%d) success=%s",
761        bounds.x(), bounds.y(), bounds.right(), bounds.bottom(),
762        ringCheck.success() ? "true" : "false");
763    return ringCheck.success();
764}
765
766void CachedRoot::draw(FindCanvas& canvas) const
767{
768    canvas.setLayerId(-1); // overlays change the ID as their pictures draw
769    canvas.drawPicture(*mPicture);
770#if USE(ACCELERATED_COMPOSITING)
771    if (!mRootLayer)
772        return;
773    canvas.drawLayers(mRootLayer);
774#endif
775}
776
777const CachedNode* CachedRoot::findAt(const WebCore::IntRect& rect,
778    const CachedFrame** framePtr, int* x, int* y, bool checkForHidden) const
779{
780    int best = INT_MAX;
781    bool inside = false;
782    (const_cast<CachedRoot*>(this))->resetClippedOut();
783    const CachedFrame* directHitFramePtr;
784    const CachedNode* directHit = NULL;
785    const CachedNode* node = findBestAt(rect, &best, &inside, &directHit,
786        &directHitFramePtr, framePtr, x, y, checkForHidden);
787    DBG_NAV_LOGD("node=%d (%p)", node == NULL ? 0 : node->index(),
788        node == NULL ? NULL : node->nodePointer());
789    if (node == NULL) {
790        node = findBestHitAt(rect, framePtr, x, y);
791        DBG_NAV_LOGD("node=%d (%p)", node == NULL ? 0 : node->index(),
792            node == NULL ? NULL : node->nodePointer());
793    }
794    if (node == NULL) {
795        *framePtr = findBestFrameAt(rect.x() + (rect.width() >> 1),
796            rect.y() + (rect.height() >> 1));
797    }
798    return node;
799}
800
801WebCore::IntPoint CachedRoot::cursorLocation() const
802{
803    const WebCore::IntRect& bounds = mHistory->mNavBounds;
804    return WebCore::IntPoint(bounds.x() + (bounds.width() >> 1),
805        bounds.y() + (bounds.height() >> 1));
806}
807
808WebCore::IntPoint CachedRoot::focusLocation() const
809{
810    return WebCore::IntPoint(mFocusBounds.x() + (mFocusBounds.width() >> 1),
811        mFocusBounds.y() + (mFocusBounds.height() >> 1));
812}
813
814// These reset the values because we only want to get the selection the first time.
815// After that, the selection is no longer accurate.
816int CachedRoot::getAndResetSelectionEnd()
817{
818    int end = mSelectionEnd;
819    mSelectionEnd = -1;
820    return end;
821}
822
823int CachedRoot::getAndResetSelectionStart()
824{
825    int start = mSelectionStart;
826    mSelectionStart = -1;
827    return start;
828}
829
830int CachedRoot::getBlockLeftEdge(int x, int y, float scale) const
831{
832    DBG_NAV_LOGD("x=%d y=%d scale=%g mViewBounds=(%d,%d,%d,%d)", x, y, scale,
833        mViewBounds.x(), mViewBounds.y(), mViewBounds.width(),
834        mViewBounds.height());
835    // if (x, y) is in a textArea or textField, return that
836    const int slop = 1;
837    WebCore::IntRect rect = WebCore::IntRect(x - slop, y - slop,
838        slop * 2, slop * 2);
839    const CachedFrame* frame;
840    int fx, fy;
841    const CachedNode* node = findAt(rect, &frame, &fx, &fy, true);
842    if (node && node->wantsKeyEvents()) {
843        DBG_NAV_LOGD("x=%d (%s)", node->bounds(frame).x(),
844            node->isTextInput() ? "text" : "plugin");
845        return node->bounds(frame).x();
846    }
847    SkPicture* picture = node ? frame->picture(node) : pictureAt(x, y);
848    if (!picture)
849        return x;
850    int halfW = (int) (mViewBounds.width() * scale * 0.5f);
851    int fullW = halfW << 1;
852    int halfH = (int) (mViewBounds.height() * scale * 0.5f);
853    int fullH = halfH << 1;
854    LeftCheck leftCheck(fullW, halfH);
855    BoundsCanvas checker(&leftCheck);
856    SkBitmap bitmap;
857    bitmap.setConfig(SkBitmap::kARGB_8888_Config, fullW, fullH);
858    checker.setBitmapDevice(bitmap);
859    checker.translate(SkIntToScalar(fullW - x), SkIntToScalar(halfH - y));
860    checker.drawPicture(*picture);
861    int result = x + leftCheck.left() - fullW;
862    DBG_NAV_LOGD("halfW=%d halfH=%d mMostLeft=%d x=%d",
863        halfW, halfH, leftCheck.mMostLeft, result);
864    return result;
865}
866
867void CachedRoot::getSimulatedMousePosition(WebCore::IntPoint* point) const
868{
869#ifndef NDEBUG
870    ASSERT(CachedFrame::mDebug.mInUse);
871#endif
872    const WebCore::IntRect& mouseBounds = mHistory->mMouseBounds;
873    int x = mouseBounds.x();
874    int y = mouseBounds.y();
875    int width = mouseBounds.width();
876    int height = mouseBounds.height();
877    point->setX(x + (width >> 1)); // default to box center
878    point->setY(y + (height >> 1));
879#if DEBUG_NAV_UI
880    const WebCore::IntRect& navBounds = mHistory->mNavBounds;
881    DBG_NAV_LOGD("mHistory->mNavBounds={%d,%d,%d,%d} "
882        "mHistory->mMouseBounds={%d,%d,%d,%d} point={%d,%d}",
883        navBounds.x(), navBounds.y(), navBounds.width(), navBounds.height(),
884        mouseBounds.x(), mouseBounds.y(), mouseBounds.width(),
885        mouseBounds.height(), point->x(), point->y());
886#endif
887}
888
889void CachedRoot::init(WebCore::Frame* frame, CachedHistory* history)
890{
891    CachedFrame::init(this, -1, frame);
892    reset();
893    mHistory = history;
894    mPicture = NULL;
895}
896
897bool CachedRoot::innerDown(const CachedNode* test, BestData* bestData) const
898{
899    ASSERT(minWorkingVertical() >= mViewBounds.x());
900    ASSERT(maxWorkingVertical() <= mViewBounds.right());
901    setupScrolledBounds();
902    // (line up)
903    mScrolledBounds.setHeight(mScrolledBounds.height() + mMaxYScroll);
904    int testTop = mScrolledBounds.y();
905    int viewBottom = mViewBounds.bottom();
906    const WebCore::IntRect& navBounds = mHistory->mNavBounds;
907    if (navBounds.isEmpty() == false &&
908            navBounds.bottom() > viewBottom && viewBottom < mContents.height())
909        return false;
910    if (navBounds.isEmpty() == false) {
911        int navTop = navBounds.y();
912        int scrollBottom;
913        if (testTop < navTop && navTop < (scrollBottom = mScrolledBounds.bottom())) {
914            mScrolledBounds.setHeight(scrollBottom - navTop);
915            mScrolledBounds.setY(navTop);
916        }
917    }
918    setCursorCache(0, mMaxYScroll);
919    frameDown(test, NULL, bestData);
920    return true;
921}
922
923bool CachedRoot::innerLeft(const CachedNode* test, BestData* bestData) const
924{
925    ASSERT(minWorkingHorizontal() >= mViewBounds.y());
926    ASSERT(maxWorkingHorizontal() <= mViewBounds.bottom());
927    setupScrolledBounds();
928    mScrolledBounds.setX(mScrolledBounds.x() - mMaxXScroll);
929    mScrolledBounds.setWidth(mScrolledBounds.width() + mMaxXScroll);
930    int testRight = mScrolledBounds.right();
931    int viewLeft = mViewBounds.x();
932    const WebCore::IntRect& navBounds = mHistory->mNavBounds;
933    if (navBounds.isEmpty() == false &&
934            navBounds.x() < viewLeft && viewLeft > mContents.x())
935        return false;
936    if (navBounds.isEmpty() == false) {
937        int navRight = navBounds.right();
938        int scrollLeft;
939        if (testRight > navRight && navRight > (scrollLeft = mScrolledBounds.x()))
940            mScrolledBounds.setWidth(navRight - scrollLeft);
941    }
942    setCursorCache(-mMaxXScroll, 0);
943    frameLeft(test, NULL, bestData);
944    return true;
945}
946
947
948void CachedRoot::innerMove(const CachedNode* node, BestData* bestData,
949    Direction direction, WebCore::IntPoint* scroll, bool firstCall)
950{
951    bestData->reset();
952    bool outOfCursor = mCursorIndex == CURSOR_CLEARED;
953    DBG_NAV_LOGD("mHistory->didFirstLayout()=%s && mCursorIndex=%d",
954        mHistory->didFirstLayout() ? "true" : "false", mCursorIndex);
955    if (mHistory->didFirstLayout() && mCursorIndex < CURSOR_SET) {
956        mHistory->reset();
957        outOfCursor = true;
958    }
959    const CachedFrame* cursorFrame;
960    const CachedNode* cursor = currentCursor(&cursorFrame);
961    mHistory->setWorking(direction, cursorFrame, cursor, mViewBounds);
962    bool findClosest = false;
963    if (mScrollOnly == false) {
964        switch (direction) {
965            case LEFT:
966                if (outOfCursor)
967                    mHistory->mNavBounds = WebCore::IntRect(mViewBounds.right(),
968                        mViewBounds.y(), 1, mViewBounds.height());
969                findClosest = innerLeft(node, bestData);
970                break;
971            case RIGHT:
972                if (outOfCursor)
973                    mHistory->mNavBounds = WebCore::IntRect(mViewBounds.x() - 1,
974                        mViewBounds.y(), 1, mViewBounds.height());
975                findClosest = innerRight(node, bestData);
976                break;
977            case UP:
978                if (outOfCursor)
979                    mHistory->mNavBounds = WebCore::IntRect(mViewBounds.x(),
980                        mViewBounds.bottom(), mViewBounds.width(), 1);
981                findClosest = innerUp(node, bestData);
982                break;
983            case DOWN:
984                if (outOfCursor)
985                    mHistory->mNavBounds = WebCore::IntRect(mViewBounds.x(),
986                        mViewBounds.y() - 1, mViewBounds.width(), 1);
987                findClosest = innerDown(node, bestData);
988                break;
989            case UNINITIALIZED:
990            default:
991                ASSERT(0);
992        }
993    }
994    if (firstCall)
995        mHistory->mPriorBounds = mHistory->mNavBounds; // bounds always advances, even if new node is ultimately NULL
996    bestData->setMouseBounds(bestData->bounds());
997    if (adjustForScroll(bestData, direction, scroll, findClosest))
998        return;
999    if (bestData->mNode != NULL) {
1000        mHistory->addToVisited(bestData->mNode, direction);
1001        mHistory->mNavBounds = bestData->bounds();
1002        mHistory->mMouseBounds = bestData->mouseBounds();
1003    } else if (scroll->x() != 0 || scroll->y() != 0) {
1004        WebCore::IntRect newBounds = mHistory->mNavBounds;
1005        int offsetX = scroll->x();
1006        int offsetY = scroll->y();
1007        newBounds.move(offsetX, offsetY);
1008        if (mViewBounds.x() > newBounds.x())
1009            offsetX = mViewBounds.x() - mHistory->mNavBounds.x();
1010        else if (mViewBounds.right() < newBounds.right())
1011            offsetX = mViewBounds.right() - mHistory->mNavBounds.right();
1012        if (mViewBounds.y() > newBounds.y())
1013            offsetY = mViewBounds.y() - mHistory->mNavBounds.y();
1014        else if (mViewBounds.bottom() < newBounds.bottom())
1015            offsetY = mViewBounds.bottom() - mHistory->mNavBounds.bottom();
1016        mHistory->mNavBounds.move(offsetX, offsetY);
1017    }
1018    mHistory->setDidFirstLayout(false);
1019}
1020
1021bool CachedRoot::innerRight(const CachedNode* test, BestData* bestData) const
1022{
1023    ASSERT(minWorkingHorizontal() >= mViewBounds.y());
1024    ASSERT(maxWorkingHorizontal() <= mViewBounds.bottom());
1025    setupScrolledBounds();
1026    // (align)
1027    mScrolledBounds.setWidth(mScrolledBounds.width() + mMaxXScroll);
1028    int testLeft = mScrolledBounds.x();
1029    int viewRight = mViewBounds.right();
1030    const WebCore::IntRect& navBounds = mHistory->mNavBounds;
1031    if (navBounds.isEmpty() == false &&
1032            navBounds.right() > viewRight && viewRight < mContents.width())
1033        return false;
1034    if (navBounds.isEmpty() == false) {
1035        int navLeft = navBounds.x();
1036        int scrollRight;
1037        if (testLeft < navLeft && navLeft < (scrollRight = mScrolledBounds.right())) {
1038            mScrolledBounds.setWidth(scrollRight - navLeft);
1039            mScrolledBounds.setX(navLeft);
1040        }
1041    }
1042    setCursorCache(mMaxXScroll, 0);
1043    frameRight(test, NULL, bestData);
1044    return true;
1045}
1046
1047bool CachedRoot::innerUp(const CachedNode* test, BestData* bestData) const
1048{
1049    ASSERT(minWorkingVertical() >= mViewBounds.x());
1050    ASSERT(maxWorkingVertical() <= mViewBounds.right());
1051    setupScrolledBounds();
1052    mScrolledBounds.setY(mScrolledBounds.y() - mMaxYScroll);
1053    mScrolledBounds.setHeight(mScrolledBounds.height() + mMaxYScroll);
1054    int testBottom = mScrolledBounds.bottom();
1055    int viewTop = mViewBounds.y();
1056    const WebCore::IntRect& navBounds = mHistory->mNavBounds;
1057    if (navBounds.isEmpty() == false &&
1058            navBounds.y() < viewTop && viewTop > mContents.y())
1059        return false;
1060    if (navBounds.isEmpty() == false) {
1061        int navBottom = navBounds.bottom();
1062        int scrollTop;
1063        if (testBottom > navBottom && navBottom > (scrollTop = mScrolledBounds.y()))
1064            mScrolledBounds.setHeight(navBottom - scrollTop);
1065    }
1066    setCursorCache(0, -mMaxYScroll);
1067    frameUp(test, NULL, bestData);
1068    return true;
1069}
1070
1071WebCore::String CachedRoot::imageURI(int x, int y) const
1072{
1073    ImageCheck imageCheck;
1074    ImageCanvas checker(&imageCheck);
1075    SkBitmap bitmap;
1076    bitmap.setConfig(SkBitmap::kARGB_8888_Config, 1, 1);
1077    checker.setBitmapDevice(bitmap);
1078    checker.translate(SkIntToScalar(-x), SkIntToScalar(-y));
1079    checker.drawPicture(*pictureAt(x, y));
1080    return WebCore::String(checker.mURI);
1081}
1082
1083bool CachedRoot::maskIfHidden(BestData* best) const
1084{
1085    const CachedNode* bestNode = best->mNode;
1086    if (bestNode->isUnclipped() || bestNode->isTransparent())
1087        return false;
1088    const CachedFrame* frame = best->mFrame;
1089    SkPicture* picture = frame->picture(bestNode);
1090    if (picture == NULL) {
1091        DBG_NAV_LOG("missing picture");
1092        return false;
1093    }
1094    // given the picture matching this nav cache
1095        // create an SkBitmap with dimensions of the cursor intersected w/ extended view
1096    const WebCore::IntRect& nodeBounds = bestNode->bounds(frame);
1097    WebCore::IntRect bounds = nodeBounds;
1098    bounds.intersect(mScrolledBounds);
1099    int leftMargin = bounds.x() == nodeBounds.x() ? kMargin : 0;
1100    int topMargin = bounds.y() == nodeBounds.y() ? kMargin : 0;
1101    int rightMargin = bounds.right() == nodeBounds.right() ? kMargin : 0;
1102    int bottomMargin = bounds.bottom() == nodeBounds.bottom() ? kMargin : 0;
1103    bool unclipped = (leftMargin & topMargin & rightMargin & bottomMargin) != 0;
1104    WebCore::IntRect marginBounds = nodeBounds;
1105    marginBounds.inflate(kMargin);
1106    marginBounds.intersect(mScrolledBounds);
1107    SkScalar offsetX = SkIntToScalar(leftMargin - bounds.x());
1108    SkScalar offsetY = SkIntToScalar(topMargin - bounds.y());
1109#if USE(ACCELERATED_COMPOSITING)
1110    // When cached nodes are constructed in CacheBuilder.cpp, their
1111    // unclipped attribute is set so this condition won't be reached.
1112    // In the future, layers may contain nodes that can be clipped.
1113    // So to be safe, adjust the layer picture by its offset.
1114    if (bestNode->isInLayer()) {
1115        const CachedLayer* cachedLayer = frame->layer(bestNode);
1116        const LayerAndroid* layer = cachedLayer->layer(mRootLayer);
1117        SkMatrix pictMatrix;
1118        layer->localToGlobal(&pictMatrix);
1119        // FIXME: ignore scale, rotation for now
1120        offsetX += pictMatrix.getTranslateX();
1121        offsetY += pictMatrix.getTranslateY();
1122        DBG_NAV_LOGD("layer picture=%p (%g,%g)", picture,
1123            pictMatrix.getTranslateX(), pictMatrix.getTranslateY());
1124    }
1125#endif
1126    BoundsCheck boundsCheck;
1127    BoundsCanvas checker(&boundsCheck);
1128    boundsCheck.mBounds.set(leftMargin, topMargin,
1129        leftMargin + bounds.width(), topMargin + bounds.height());
1130    boundsCheck.mBoundsSlop = boundsCheck.mBounds;
1131    boundsCheck.mBoundsSlop.inset(-kSlop, -kSlop);
1132    SkBitmap bitmap;
1133    bitmap.setConfig(SkBitmap::kARGB_8888_Config, marginBounds.width(),
1134        marginBounds.height());
1135    checker.setBitmapDevice(bitmap);
1136    // insert probes to be called when the data corresponding to this ring is drawn
1137        // need to know if ring was generated by text, image, or parent (like div)
1138        // ? need to know (like imdb menu bar) to give up sometimes (when?)
1139    checker.translate(offsetX, offsetY);
1140    checker.drawPicture(*picture);
1141    boundsCheck.checkLast();
1142    // was it not drawn or clipped out?
1143    CachedNode* node = const_cast<CachedNode*>(best->mNode);
1144    if (boundsCheck.hidden()) { // if hidden, return false so that nav can try again
1145#if DEBUG_NAV_UI
1146        const SkIRect& m = boundsCheck.mBounds;
1147        const SkIRect& s = boundsCheck.mBoundsSlop;
1148        DBG_NAV_LOGD("hidden node:%p (%d) mBounds={%d,%d,%d,%d} mBoundsSlop="
1149            "{%d,%d,%d,%d}", node, node->index(),
1150            m.fLeft, m.fTop, m.fRight, m.fBottom,
1151            s.fLeft, s.fTop, s.fRight, s.fBottom);
1152        const SkIRect& o = boundsCheck.mDrawnOver.getBounds();
1153        const SkIRect& l = boundsCheck.mLastAll;
1154        const SkIRect& u = boundsCheck.mUnion;
1155        DBG_NAV_LOGD("hidden mDrawnOver={%d,%d,%d,%d} mLastAll={%d,%d,%d,%d}"
1156            " mUnion={%d,%d,%d,%d}",
1157            o.fLeft, o.fTop, o.fRight, o.fBottom,
1158            l.fLeft, l.fTop, l.fRight, l.fBottom,
1159            u.fLeft, u.fTop, u.fRight, u.fBottom);
1160        const SkIRect& a = boundsCheck.mAllDrawnIn;
1161        const WebCore::IntRect& c = mScrolledBounds;
1162        const WebCore::IntRect& b = nodeBounds;
1163        DBG_NAV_LOGD("hidden mAllDrawnIn={%d,%d,%d,%d}"
1164            " mScrolledBounds={%d,%d,%d,%d} nodeBounds={%d,%d,%d,%d}",
1165            a.fLeft, a.fTop, a.fRight, a.fBottom,
1166            c.x(), c.y(), c.right(), c.bottom(),
1167            b.x(), b.y(), b.right(), b.bottom());
1168        DBG_NAV_LOGD("bits.mWidth=%d bits.mHeight=%d transX=%d transY=%d",
1169            marginBounds.width(),marginBounds.height(),
1170            kMargin - bounds.x(), kMargin - bounds.y());
1171#endif
1172        node->setDisabled(true);
1173        node->setClippedOut(unclipped == false);
1174        return true;
1175    }
1176    // was it partially occluded by later drawing?
1177    // if partially occluded, modify the bounds so that the mouse click has a better x,y
1178       const SkIRect& over = boundsCheck.mDrawnOver.getBounds();
1179    if (over.isEmpty() == false) {
1180#if DEBUG_NAV_UI
1181        SkIRect orig = boundsCheck.mBounds;
1182#endif
1183        SkIRect& base = boundsCheck.mBounds;
1184        if (base.fLeft < over.fRight && base.fRight > over.fRight)
1185            base.fLeft = over.fRight;
1186        else if (base.fRight > over.fLeft && base.fLeft < over.fLeft)
1187            base.fRight = over.fLeft;
1188        if (base.fTop < over.fBottom && base.fBottom > over.fBottom)
1189            base.fTop = over.fBottom;
1190        else if (base.fBottom > over.fTop && base.fTop < over.fTop)
1191            base.fBottom = over.fTop;
1192#if DEBUG_NAV_UI
1193        const SkIRect& modded = boundsCheck.mBounds;
1194        DBG_NAV_LOGD("partially occluded node:%p (%d) old:{%d,%d,%d,%d}"
1195            " new:{%d,%d,%d,%d}", node, node->index(),
1196            orig.fLeft, orig.fTop, orig.fRight, orig.fBottom,
1197            base.fLeft, base.fTop, base.fRight, base.fBottom);
1198#endif
1199        best->setMouseBounds(WebCore::IntRect(bounds.x() + base.fLeft - kMargin,
1200            bounds.y() + base.fTop - kMargin, base.width(), base.height()));
1201        node->clip(best->mouseBounds());
1202    }
1203    return false;
1204}
1205
1206const CachedNode* CachedRoot::moveCursor(Direction direction, const CachedFrame** framePtr,
1207    WebCore::IntPoint* scroll)
1208{
1209#ifndef NDEBUG
1210    ASSERT(CachedFrame::mDebug.mInUse);
1211#endif
1212    CachedRoot* frame = this;
1213    const CachedNode* node = frame->document();
1214    if (node == NULL)
1215        return NULL;
1216    if (mViewBounds.isEmpty())
1217        return NULL;
1218    resetClippedOut();
1219    setData();
1220    BestData bestData;
1221    innerMove(node, &bestData, direction, scroll, true);
1222    // if node is partially or fully concealed by layer, scroll it into view
1223    if (mRootLayer && bestData.mNode && !bestData.mNode->isInLayer()) {
1224#if USE(ACCELERATED_COMPOSITING)
1225#if DUMP_NAV_CACHE
1226        CachedLayer::Debug::printRootLayerAndroid(mRootLayer);
1227#endif
1228        SkIRect original = bestData.mNode->cursorRingBounds(bestData.mFrame);
1229        DBG_NAV_LOGD("original=(%d,%d,w=%d,h=%d) scroll=(%d,%d)",
1230            original.fLeft, original.fTop, original.width(), original.height(),
1231            scroll->x(), scroll->y());
1232        original.offset(-scroll->x(), -scroll->y());
1233        SkRegion rings(original);
1234        SkTDArray<SkRect> region;
1235        mRootLayer->clipArea(&region);
1236        SkRegion layers;
1237        for (int index = 0; index < region.count(); index++) {
1238            SkIRect enclosing;
1239            region[index].round(&enclosing);
1240            rings.op(enclosing, SkRegion::kDifference_Op);
1241            layers.op(enclosing, SkRegion::kUnion_Op);
1242        }
1243        SkIRect layerBounds(layers.getBounds());
1244        SkIRect ringBounds(rings.getBounds());
1245        int scrollX = scroll->x();
1246        int scrollY = scroll->y();
1247        if (rings.getBounds() != original) {
1248            int topOverlap = layerBounds.fBottom - original.fTop;
1249            int bottomOverlap = original.fBottom - layerBounds.fTop;
1250            int leftOverlap = layerBounds.fRight - original.fLeft;
1251            int rightOverlap = original.fRight - layerBounds.fLeft;
1252            if (direction & UP_DOWN) {
1253                if (layerBounds.fLeft < original.fLeft && leftOverlap < 0)
1254                    scroll->setX(leftOverlap);
1255                if (original.fRight < layerBounds.fRight && rightOverlap > 0
1256                        && -leftOverlap > rightOverlap)
1257                    scroll->setX(rightOverlap);
1258                bool topSet = scrollY > topOverlap && (direction == UP
1259                    || !scrollY);
1260                if (topSet)
1261                    scroll->setY(topOverlap);
1262                if (scrollY < bottomOverlap && (direction == DOWN || (!scrollY
1263                        && (!topSet || -topOverlap > bottomOverlap))))
1264                    scroll->setY(bottomOverlap);
1265            } else {
1266                if (layerBounds.fTop < original.fTop && topOverlap < 0)
1267                    scroll->setY(topOverlap);
1268                if (original.fBottom < layerBounds.fBottom && bottomOverlap > 0
1269                        && -topOverlap > bottomOverlap)
1270                    scroll->setY(bottomOverlap);
1271                bool leftSet = scrollX > leftOverlap && (direction == LEFT
1272                    || !scrollX);
1273                if (leftSet)
1274                    scroll->setX(leftOverlap);
1275                if (scrollX < rightOverlap && (direction == RIGHT || (!scrollX
1276                        && (!leftSet || -leftOverlap > rightOverlap))))
1277                    scroll->setX(rightOverlap);
1278           }
1279            DBG_NAV_LOGD("rings=(%d,%d,w=%d,h=%d) layers=(%d,%d,w=%d,h=%d)"
1280                " scroll=(%d,%d)",
1281                ringBounds.fLeft, ringBounds.fTop, ringBounds.width(), ringBounds.height(),
1282                layerBounds.fLeft, layerBounds.fTop, layerBounds.width(), layerBounds.height(),
1283                scroll->x(), scroll->y());
1284        }
1285#endif
1286    }
1287    *framePtr = bestData.mFrame;
1288    return const_cast<CachedNode*>(bestData.mNode);
1289}
1290
1291const CachedNode* CachedRoot::nextTextField(const CachedNode* start,
1292        const CachedFrame** framePtr) const
1293{
1294    bool startFound = false;
1295    return CachedFrame::nextTextField(start, framePtr, &startFound);
1296}
1297
1298SkPicture* CachedRoot::pictureAt(int x, int y) const
1299{
1300#if USE(ACCELERATED_COMPOSITING)
1301    if (mRootLayer) {
1302        const LayerAndroid* layer = mRootLayer->find(x, y);
1303        if (layer) {
1304            SkPicture* picture = layer->picture();
1305            if (picture)
1306                return picture;
1307        }
1308    }
1309#endif
1310    return mPicture;
1311}
1312
1313void CachedRoot::reset()
1314{
1315#ifndef NDEBUG
1316    ASSERT(CachedFrame::mDebug.mInUse);
1317#endif
1318    mContents = mViewBounds = WebCore::IntRect(0, 0, 0, 0);
1319    mMaxXScroll = mMaxYScroll = 0;
1320    mRootLayer = 0;
1321    mSelectionStart = mSelectionEnd = -1;
1322    mScrollOnly = false;
1323}
1324
1325bool CachedRoot::scrollDelta(WebCore::IntRect& newOutset, Direction direction, int* delta)
1326{
1327    switch (direction) {
1328        case LEFT:
1329            *delta = -mMaxXScroll;
1330            return newOutset.x() >= mViewBounds.x();
1331        case RIGHT:
1332            *delta = mMaxXScroll;
1333            return newOutset.right() <= mViewBounds.right();
1334        case UP:
1335            *delta = -mMaxYScroll;
1336            return newOutset.y() >= mViewBounds.y();
1337        case DOWN:
1338            *delta = mMaxYScroll;
1339            return newOutset.bottom() <= mViewBounds.bottom();
1340        default:
1341            *delta = 0;
1342            ASSERT(0);
1343    }
1344    return false;
1345}
1346
1347void CachedRoot::setCachedFocus(CachedFrame* frame, CachedNode* node)
1348{
1349    mFocusBounds = WebCore::IntRect(0, 0, 0, 0);
1350    if (node == NULL)
1351        return;
1352    node->setIsFocus(true);
1353    mFocusBounds = node->bounds(frame);
1354    frame->setFocusIndex(node - frame->document());
1355    CachedFrame* parent;
1356    while ((parent = frame->parent()) != NULL) {
1357        parent->setFocusIndex(frame->indexInParent());
1358        frame = parent;
1359    }
1360#if DEBUG_NAV_UI
1361    const CachedFrame* focusFrame;
1362    const CachedNode* focus = currentFocus(&focusFrame);
1363    WebCore::IntRect bounds = WebCore::IntRect(0, 0, 0, 0);
1364    if (focus)
1365        bounds = focus->bounds(focusFrame);
1366    DBG_NAV_LOGD("new focus %d (nodePointer=%p) bounds={%d,%d,%d,%d}",
1367        focus ? focus->index() : 0,
1368        focus ? focus->nodePointer() : NULL, bounds.x(), bounds.y(),
1369        bounds.width(), bounds.height());
1370#endif
1371}
1372
1373void CachedRoot::setCursor(CachedFrame* frame, CachedNode* node)
1374{
1375#if DEBUG_NAV_UI
1376    const CachedFrame* cursorFrame;
1377    const CachedNode* cursor = currentCursor(&cursorFrame);
1378    WebCore::IntRect bounds;
1379    if (cursor)
1380        bounds = cursor->bounds(cursorFrame);
1381    DBG_NAV_LOGD("old cursor %d (nodePointer=%p) bounds={%d,%d,%d,%d}",
1382        cursor ? cursor->index() : 0,
1383        cursor ? cursor->nodePointer() : NULL, bounds.x(), bounds.y(),
1384        bounds.width(), bounds.height());
1385#endif
1386    clearCursor();
1387    if (node == NULL)
1388        return;
1389    node->setIsCursor(true);
1390    node->show();
1391    frame->setCursorIndex(node - frame->document());
1392    CachedFrame* parent;
1393    while ((parent = frame->parent()) != NULL) {
1394        parent->setCursorIndex(frame->indexInParent());
1395        frame = parent;
1396    }
1397#if DEBUG_NAV_UI
1398    cursor = currentCursor(&cursorFrame);
1399    bounds = WebCore::IntRect(0, 0, 0, 0);
1400    if (cursor)
1401        bounds = cursor->bounds(cursorFrame);
1402    DBG_NAV_LOGD("new cursor %d (nodePointer=%p) bounds={%d,%d,%d,%d}",
1403        cursor ? cursor->index() : 0,
1404        cursor ? cursor->nodePointer() : NULL, bounds.x(), bounds.y(),
1405        bounds.width(), bounds.height());
1406#endif
1407}
1408
1409void CachedRoot::setCursorCache(int scrollX, int scrollY) const
1410{
1411    mCursor = currentCursor();
1412    if (mCursor)
1413        mCursorBounds = mCursor->bounds(this);
1414    if (!mRootLayer)
1415        return;
1416    SkRegion baseScrolled(mScrolledBounds);
1417    mBaseUncovered = SkRegion(mScrolledBounds);
1418#if USE(ACCELERATED_COMPOSITING)
1419#if DUMP_NAV_CACHE
1420    CachedLayer::Debug::printRootLayerAndroid(mRootLayer);
1421#endif
1422    SkTDArray<SkRect> region;
1423    mRootLayer->clipArea(&region);
1424    WebCore::IntSize offset(
1425        copysign(min(max(0, mContents.width() - mScrolledBounds.width()),
1426        abs(scrollX)), scrollX),
1427        copysign(min(max(0, mContents.height() - mScrolledBounds.height()),
1428        abs(scrollY)), scrollY));
1429    bool hasOffset = offset.width() || offset.height();
1430    // restrict scrollBounds to that which is not under layer
1431    for (int index = 0; index < region.count(); index++) {
1432        SkIRect less;
1433        region[index].round(&less);
1434        DBG_NAV_LOGD("less=(%d,%d,w=%d,h=%d)", less.fLeft, less.fTop,
1435            less.width(), less.height());
1436        mBaseUncovered.op(less, SkRegion::kDifference_Op);
1437        if (!hasOffset)
1438            continue;
1439        less.offset(offset.width(), offset.height());
1440        baseScrolled.op(less, SkRegion::kDifference_Op);
1441    }
1442    if (hasOffset)
1443        mBaseUncovered.op(baseScrolled, SkRegion::kUnion_Op);
1444#endif
1445}
1446
1447#if DUMP_NAV_CACHE
1448
1449#define DEBUG_PRINT_BOOL(field) \
1450    DUMP_NAV_LOGD("// bool " #field "=%s;\n", b->field ? "true" : "false")
1451
1452#define DEBUG_PRINT_RECT(field) \
1453    { const WebCore::IntRect& r = b->field; \
1454    DUMP_NAV_LOGD("// IntRect " #field "={%d, %d, %d, %d};\n", \
1455        r.x(), r.y(), r.width(), r.height()); }
1456
1457CachedRoot* CachedRoot::Debug::base() const {
1458    CachedRoot* nav = (CachedRoot*) ((char*) this - OFFSETOF(CachedRoot, mDebug));
1459    return nav;
1460}
1461
1462void CachedRoot::Debug::print() const
1463{
1464#ifdef DUMP_NAV_CACHE_USING_PRINTF
1465    gWriteLogMutex.lock();
1466    ASSERT(gNavCacheLogFile == NULL);
1467    gNavCacheLogFile = fopen(NAV_CACHE_LOG_FILE, "a");
1468#endif
1469    CachedRoot* b = base();
1470    b->CachedFrame::mDebug.print();
1471    b->mHistory->mDebug.print(b);
1472    DUMP_NAV_LOGD("// int mMaxXScroll=%d, mMaxYScroll=%d;\n",
1473        b->mMaxXScroll, b->mMaxYScroll);
1474#ifdef DUMP_NAV_CACHE_USING_PRINTF
1475    if (gNavCacheLogFile)
1476        fclose(gNavCacheLogFile);
1477    gNavCacheLogFile = NULL;
1478    gWriteLogMutex.unlock();
1479#endif
1480}
1481
1482#endif
1483
1484}
1485