WebKit/android/nav/CachedRoot.cpp

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