WebKit/android/nav/CachedFrame.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 "CachedHistory.h"
  28 #include "CachedNode.h"
  29 #include "CachedRoot.h"
  30 #include "LayerAndroid.h"
  31
  32 #include "CachedFrame.h"
  33
  34 #define OFFSETOF(type, field) ((char*)&(((type*)1)->field) - (char*)1) // avoids gnu warning
  35
  36 #define MIN_OVERLAP 3 // if rects overlap by 2 pixels or fewer, treat them as non-intersecting
  37
  38 namespace android {
  39
  40 WebCore::IntRect CachedFrame::adjustBounds(const CachedNode* node,
  41     const WebCore::IntRect& rect) const
  42 {
  43     DBG_NAV_LOGV("node=%p [%d] rect=(%d,%d,w=%d,h=%d) view=(%d,%d,w=%d,h=%d)"
  44         " local=(%d,%d,w=%d,h=%d) root=(%d,%d,w=%d,h=%d)",
  45         node, node->index(), rect.x(), rect.y(), rect.width(), rect.height(),
  46         mViewBounds.x(), mViewBounds.y(),
  47         mViewBounds.width(), mViewBounds.height(),
  48         mLocalViewBounds.x(), mLocalViewBounds.y(),
  49         mLocalViewBounds.width(), mLocalViewBounds.height(),
  50         mRoot->mViewBounds.x(), mRoot->mViewBounds.y(),
  51         mRoot->mViewBounds.width(), mRoot->mViewBounds.height());
  52 #if USE(ACCELERATED_COMPOSITING)
  53     if (!mRoot)
  54         return rect;
  55
  56     const CachedLayer* cachedLayer = layer(node);
  57     if (!cachedLayer)
  58         return rect;
  59
  60     const WebCore::LayerAndroid* rootLayer = mRoot->rootLayer();
  61     const LayerAndroid* aLayer = cachedLayer->layer(rootLayer);
  62     if (aLayer)
  63         return cachedLayer->adjustBounds(rootLayer, rect);
  64 #endif
  65     return rect;
  66 }
  67
  68 bool CachedFrame::CheckBetween(Direction direction, const WebCore::IntRect& bestRect,
  69         const WebCore::IntRect& prior, WebCore::IntRect* result)
  70 {
  71     int left, top, width, height;
  72     if (direction & UP_DOWN) {
  73         top = direction == UP ? bestRect.bottom() : prior.bottom();
  74         int bottom = direction == UP ? prior.y() : bestRect.y();
  75         height = bottom - top;
  76         if (height < 0)
  77             return false;
  78         left = prior.x();
  79         int testLeft = bestRect.x();
  80         if (left > testLeft)
  81             left = testLeft;
  82         int right = prior.right();
  83         int testRight = bestRect.right();
  84         if (right < testRight)
  85             right = testRight;
  86         width = right - left;
  87     } else {
  88         left = direction == LEFT ? bestRect.right() : prior.right();
  89         int right = direction == LEFT ? prior.x() : bestRect.x();
  90         width = right - left;
  91         if (width < 0)
  92             return false;
  93         top = prior.y();
  94         int testTop = bestRect.y();
  95         if (top > testTop)
  96             top = testTop;
  97         int bottom = prior.bottom();
  98         int testBottom = bestRect.bottom();
  99         if (bottom < testBottom)
 100             bottom = testBottom;
 101         height = bottom - top;
 102     }
 103     *result = WebCore::IntRect(left, top, width, height);
 104     return true;
 105 }
 106
 107 bool CachedFrame::checkBetween(BestData* best, Direction direction)
 108 {
 109     const WebCore::IntRect& bestRect = best->bounds();
 110     BestData test;
 111     test.mDistance = INT_MAX;
 112     test.mNode = NULL;
 113     int index = direction;
 114     int limit = index + DIRECTION_COUNT;
 115     do {
 116         WebCore::IntRect edges;
 117         Direction check = (Direction) (index & DIRECTION_MASK);
 118         if (CheckBetween(check, bestRect,
 119                 history()->priorBounds(), &edges) == false)
 120             continue;
 121         WebCore::IntRect clip = mRoot->scrolledBounds();
 122         clip.intersect(edges);
 123         if (clip.isEmpty())
 124             continue;
 125         findClosest(&test, direction, check, &clip);
 126         if (test.mNode == NULL)
 127             continue;
 128         if (direction == check)
 129             break;
 130     } while (++index < limit);
 131     if (test.mNode == NULL)
 132         return false;
 133     *best = test;
 134     return true;
 135 }
 136
 137 bool CachedFrame::checkRings(const CachedNode* node,
 138         const WebCore::IntRect& testBounds) const
 139 {
 140     return mRoot->checkRings(picture(node), node, testBounds);
 141 }
 142
 143 bool CachedFrame::checkVisited(const CachedNode* node, Direction direction) const
 144 {
 145     return history()->checkVisited(node, direction);
 146 }
 147
 148 void CachedFrame::clearCursor()
 149 {
 150     DBG_NAV_LOGD("mCursorIndex=%d", mCursorIndex);
 151     if (mCursorIndex < CURSOR_SET)
 152         return;
 153     CachedNode& cursor = mCachedNodes[mCursorIndex];
 154     cursor.clearCursor(this);
 155     mCursorIndex = CURSOR_CLEARED; // initialized and explicitly cleared
 156 }
 157
 158 // returns 0 if test is preferable to best, 1 if not preferable, or -1 if unknown
 159 int CachedFrame::compare(BestData& testData, const BestData& bestData) const
 160 {
 161     if (testData.mNode->tabIndex() != bestData.mNode->tabIndex()) {
 162         if (testData.mNode->tabIndex() < bestData.mNode->tabIndex()
 163                 || (mRoot->mCursor && mRoot->mCursor->tabIndex() < bestData.mNode->tabIndex())) {
 164             testData.mNode->setCondition(CachedNode::HIGHER_TAB_INDEX);
 165             return REJECT_TEST;
 166         }
 167         return TEST_IS_BEST;
 168     }
 169     // if the test minor axis line intersects the line segment between cursor
 170     // center and best center, choose it
 171     // give more weight to exact major axis alignment (rows, columns)
 172     if (testData.mInNav != bestData.mInNav) {
 173         if (bestData.mInNav) {
 174             testData.mNode->setCondition(CachedNode::IN_CURSOR);
 175             return REJECT_TEST;
 176         }
 177         return TEST_IS_BEST;
 178     }
 179     if (testData.mInNav) {
 180         if (bestData.mMajorDelta < testData.mMajorDelta) {
 181             testData.mNode->setCondition(CachedNode::CLOSER_IN_CURSOR);
 182             return REJECT_TEST;
 183         }
 184         if (testData.mMajorDelta < bestData.mMajorDelta)
 185             return TEST_IS_BEST;
 186     }
 187     if (testData.mMajorDelta < 0 && bestData.mMajorDelta >= 0) {
 188         testData.mNode->setCondition(CachedNode::FURTHER);
 189         return REJECT_TEST;
 190     }
 191     if ((testData.mMajorDelta ^ bestData.mMajorDelta) < 0) // one above, one below (or one left, one right)
 192         return TEST_IS_BEST;
 193     bool bestInWorking = bestData.inOrSubsumesWorking();
 194     bool testInWorking = testData.inOrSubsumesWorking();
 195     if (bestInWorking && testData.mWorkingOutside && testData.mNavOutside) {
 196         testData.mNode->setCondition(CachedNode::IN_WORKING);
 197         return REJECT_TEST;
 198     }
 199     if (testInWorking && bestData.mWorkingOutside && bestData.mNavOutside)
 200         return TEST_IS_BEST;
 201     bool bestInNav = directionChange() && bestData.inOrSubsumesNav();
 202     bool testInNav = directionChange() && testData.inOrSubsumesNav();
 203     if (bestInWorking == false && testInWorking == false) {
 204         if (bestInNav && testData.mNavOutside) {
 205             testData.mNode->setCondition(CachedNode::IN_UMBRA);
 206             return REJECT_TEST;
 207         }
 208         if (testInNav && bestData.mNavOutside)
 209             return TEST_IS_BEST;
 210     }
 211 #if 01 // hopefully butt test will remove need for this
 212     if (testData.mCursorChild != bestData.mCursorChild) {
 213         if (bestData.mCursorChild) {
 214             testData.mNode->setCondition(CachedNode::IN_CURSOR_CHILDREN);
 215             return REJECT_TEST;
 216         }
 217         return TEST_IS_BEST;
 218     }
 219 #endif
 220     bool bestTestIn = (bestInWorking || bestInNav) && (testInWorking || testInNav);
 221     bool testOverlap = bestTestIn || (testData.mWorkingOverlap != 0 && bestData.mWorkingOverlap == 0);
 222     bool bestOverlap = bestTestIn || (testData.mWorkingOverlap == 0 && bestData.mWorkingOverlap != 0);
 223 #if 01 // this isn't working?
 224     if (testOverlap == bestOverlap) {
 225         if (bestData.mMajorButt < 10 && testData.mMajorButt >= 40) {
 226             testData.mNode->setCondition(CachedNode::BUTTED_UP);
 227             return REJECT_TEST;
 228         }
 229         if (testData.mMajorButt < 10 && bestData.mMajorButt >= 40)
 230             return TEST_IS_BEST;
 231     }
 232 #endif
 233     if (bestOverlap && bestData.mMajorDelta < testData.mMajorDelta) { // choose closest major axis center
 234         testData.mNode->setCondition(CachedNode::CLOSER);
 235         return REJECT_TEST;
 236     }
 237     if (testOverlap && testData.mMajorDelta < bestData.mMajorDelta)
 238         return TEST_IS_BEST;
 239     if (bestOverlap && bestData.mMajorDelta2 < testData.mMajorDelta2) {
 240         testData.mNode->setCondition(CachedNode::CLOSER_TOP);
 241         return REJECT_TEST;
 242     }
 243     if (testOverlap && testData.mMajorDelta2 < bestData.mMajorDelta2)
 244         return TEST_IS_BEST;
 245 #if 01
 246     if (bestOverlap && ((bestData.mSideDistance <= 0 && testData.mSideDistance > 0) ||
 247             abs(bestData.mSideDistance) < abs(testData.mSideDistance))) {
 248         testData.mNode->setCondition(CachedNode::LEFTMOST);
 249         return REJECT_TEST;
 250     }
 251     if (testOverlap && ((testData.mSideDistance <= 0 && bestData.mSideDistance > 0) ||
 252             abs(testData.mSideDistance) < abs(bestData.mSideDistance)))
 253         return TEST_IS_BEST;
 254 // fix me : the following ASSERT fires -- not sure if this case should be handled or not
 255 //    ASSERT(bestOverlap == false && testOverlap == false);
 256 #endif
 257     SkFixed testMultiplier = testData.mWorkingOverlap > testData.mNavOverlap ?
 258         testData.mWorkingOverlap : testData.mNavOverlap;
 259     SkFixed bestMultiplier = bestData.mWorkingOverlap > bestData.mNavOverlap ?
 260         bestData.mWorkingOverlap : bestData.mNavOverlap;
 261     int testDistance = testData.mDistance;
 262     int bestDistance = bestData.mDistance;
 263 //    start here;
 264     // this fails if they're off by 1
 265     // try once again to implement sliding scale so that off by 1 is nearly like zero,
 266     // and off by a lot causes sideDistance to have little or no effect
 267         // try elliptical distance -- lengthen side contribution
 268         // these ASSERTs should not fire, but do fire on mail.google.com
 269         // can't debug yet, won't reproduce
 270     ASSERT(testDistance >= 0);
 271     ASSERT(bestDistance >= 0);
 272     testDistance += testDistance; // multiply by 2
 273     testDistance *= testDistance;
 274     bestDistance += bestDistance; // multiply by 2
 275     bestDistance *= bestDistance;
 276     int side = testData.mSideDistance;
 277     int negative = side < 0 && bestData.mSideDistance > 0;
 278     side *= side;
 279     if (negative)
 280         side = -side;
 281     testDistance += side;
 282     side = bestData.mSideDistance;
 283     negative = side < 0 && testData.mSideDistance > 0;
 284     side *= side;
 285     if (negative)
 286         side = -side;
 287     bestDistance += side;
 288     if (testMultiplier > (SK_Fixed1 >> 1) || bestMultiplier > (SK_Fixed1 >> 1)) { // considerable working overlap?
 289        testDistance = SkFixedMul(testDistance, bestMultiplier);
 290        bestDistance = SkFixedMul(bestDistance, testMultiplier);
 291     }
 292     if (bestDistance < testDistance) {
 293         testData.mNode->setCondition(CachedNode::CLOSER_OVERLAP);
 294         return REJECT_TEST;
 295     }
 296     if (testDistance < bestDistance)
 297         return TEST_IS_BEST;
 298 #if 0
 299     int distance = testData.mDistance + testData.mSideDistance;
 300     int best = bestData.mDistance + bestData.mSideDistance;
 301     if (distance > best) {
 302         testData.mNode->setCondition(CachedNode::CLOSER_RAW_DISTANCE);
 303         return REJECT_TEST;
 304     }
 305     else if (distance < best)
 306         return TEST_IS_BEST;
 307     best = bestData.mSideDistance;
 308     if (testData.mSideDistance > best) {
 309         testData.mNode->setCondition(CachedNode::SIDE_DISTANCE);
 310         return REJECT_TEST;
 311     }
 312     if (testData.mSideDistance < best)
 313         return TEST_IS_BEST;
 314 #endif
 315     if (testData.mPreferred < bestData.mPreferred) {
 316         testData.mNode->setCondition(CachedNode::PREFERRED);
 317         return REJECT_TEST;
 318     }
 319     if (testData.mPreferred > bestData.mPreferred)
 320         return TEST_IS_BEST;
 321     return UNDECIDED;
 322 }
 323
 324 const CachedNode* CachedFrame::currentCursor(const CachedFrame** framePtr) const
 325 {
 326     if (framePtr)
 327         *framePtr = this;
 328     if (mCursorIndex < CURSOR_SET)
 329         return NULL;
 330     const CachedNode* result = &mCachedNodes[mCursorIndex];
 331     const CachedFrame* frame = hasFrame(result);
 332     if (frame != NULL)
 333         return frame->currentCursor(framePtr);
 334     (const_cast<CachedNode*>(result))->fixUpCursorRects(this);
 335     return result;
 336 }
 337
 338 const CachedNode* CachedFrame::currentFocus(const CachedFrame** framePtr) const
 339 {
 340     if (framePtr)
 341         *framePtr = this;
 342     if (mFocusIndex < 0)
 343         return NULL;
 344     const CachedNode* result = &mCachedNodes[mFocusIndex];
 345     const CachedFrame* frame = hasFrame(result);
 346     if (frame != NULL)
 347         return frame->currentFocus(framePtr);
 348     return result;
 349 }
 350
 351 bool CachedFrame::directionChange() const
 352 {
 353     return history()->directionChange();
 354 }
 355
 356 #ifdef BROWSER_DEBUG
 357 CachedNode* CachedFrame::find(WebCore::Node* node) // !!! probably debugging only
 358 {
 359     for (CachedNode* test = mCachedNodes.begin(); test != mCachedNodes.end(); test++)
 360         if (node == test->webCoreNode())
 361             return test;
 362     for (CachedFrame* frame = mCachedFrames.begin(); frame != mCachedFrames.end();
 363             frame++) {
 364         CachedNode* result = frame->find(node);
 365         if (result != NULL)
 366             return result;
 367     }
 368     return NULL;
 369 }
 370 #endif
 371
 372 const CachedNode* CachedFrame::findBestAt(const WebCore::IntRect& rect,
 373     int* best, bool* inside, const CachedNode** directHit,
 374     const CachedFrame** directHitFramePtr,
 375     const CachedFrame** framePtr, int* x, int* y,
 376     bool checkForHiddenStart) const
 377 {
 378     const CachedNode* result = NULL;
 379     int rectWidth = rect.width();
 380     WebCore::IntPoint center = WebCore::IntPoint(rect.x() + (rectWidth >> 1),
 381         rect.y() + (rect.height() >> 1));
 382     mRoot->setupScrolledBounds();
 383     for (const CachedNode* test = mCachedNodes.begin(); test != mCachedNodes.end(); test++) {
 384         if (test->disabled())
 385             continue;
 386         size_t parts = test->navableRects();
 387         BestData testData;
 388         testData.mNode = test;
 389         testData.mFrame = this;
 390         WebCore::IntRect bounds = test->bounds(this);
 391         testData.setMouseBounds(bounds);
 392         testData.setNodeBounds(bounds);
 393         bool checkForHidden = checkForHiddenStart;
 394         for (size_t part = 0; part < parts; part++) {
 395             WebCore::IntRect testRect = test->ring(this, part);
 396             if (testRect.intersects(rect)) {
 397 #if DEBUG_NAV_UI
 398                 if (test->isInLayer()) {
 399                     DBG_NAV_LOGD("[%d] intersects=%s testRect=(%d,%d,w=%d,h=%d)"
 400                         " rect=(%d,%d,w=%d,h=%d)", test->index(),
 401                         testRect.intersects(rect) ? "true" : "false",
 402                         testRect.x(), testRect.y(),
 403                         testRect.width(), testRect.height(),
 404                         rect.x(), rect.y(), rect.width(), rect.height());
 405                 }
 406 #endif
 407                 if (checkForHidden && mRoot->maskIfHidden(&testData) == true) {
 408                     DBG_NAV_LOGD("hidden [%d]", test->index());
 409                     break;
 410                 }
 411                 checkForHidden = false;
 412                 testRect.intersect(testData.mouseBounds());
 413                 if (testRect.contains(center)) {
 414                     // We have a direct hit.
 415                     if (*directHit == NULL) {
 416                         DBG_NAV_LOGD("direct hit 1 [%d]", test->index());
 417                         *directHit = test;
 418                         *directHitFramePtr = this;
 419                         IntRect r(center, IntSize(0, 0));
 420                         *x = r.x();
 421                         *y = r.y();
 422                     } else {
 423                         DBG_NAV_LOGD("direct hit 2 [%d]", test->index());
 424                         // We have hit another one before
 425                         const CachedNode* d = *directHit;
 426                         if (d->bounds(this).contains(testRect)) {
 427                             // This rectangle is inside the other one, so it is
 428                             // the best one.
 429                             *directHit = test;
 430                             *directHitFramePtr = this;
 431                         }
 432                     }
 433                 }
 434                 if (NULL != *directHit) {
 435                     // If we have a direct hit already, there is no need to
 436                     // calculate the distances, or check the other parts
 437                     break;
 438                 }
 439                 DBG_NAV_LOGD("indirect hit [%d]", test->index());
 440                 WebCore::IntRect both = rect;
 441                 int smaller = testRect.width() < testRect.height() ?
 442                     testRect.width() : testRect.height();
 443                 smaller -= rectWidth;
 444                 int inset = smaller < rectWidth ? smaller : rectWidth;
 445                 inset >>= 1; // inflate doubles the width decrease
 446                 if (inset > 1)
 447                     both.inflate(1 - inset);
 448                 both.intersect(testRect);
 449                 if (both.isEmpty())
 450                     continue;
 451                 bool testInside = testRect.contains(center);
 452                 if (*inside && !testInside)
 453                     continue;
 454                 WebCore::IntPoint testCenter = WebCore::IntPoint(testRect.x() +
 455                     (testRect.width() >> 1), testRect.y() + (testRect.height() >> 1));
 456                 int dx = testCenter.x() - center.x();
 457                 int dy = testCenter.y() - center.y();
 458                 int distance = dx * dx + dy * dy;
 459                 if ((!*inside && testInside) || *best >= distance) {
 460                     *best = distance;
 461                     *inside = testInside;
 462                     result = test;
 463                     *framePtr = this;
 464                     *x = both.x() + (both.width() >> 1);
 465                     *y = both.y() + (both.height() >> 1);
 466                 }
 467             }
 468         }
 469     }
 470     for (const CachedFrame* frame = mCachedFrames.begin();
 471             frame != mCachedFrames.end(); frame++) {
 472         const CachedNode* frameResult = frame->findBestAt(rect, best, inside,
 473             directHit, directHitFramePtr, framePtr, x, y, checkForHiddenStart);
 474         if (NULL != frameResult)
 475             result = frameResult;
 476     }
 477     if (NULL != *directHit) {
 478         result = *directHit;
 479         *framePtr = *directHitFramePtr;
 480     }
 481     return result;
 482 }
 483
 484 const CachedFrame* CachedFrame::findBestFrameAt(int x, int y) const
 485 {
 486     if (mLocalViewBounds.contains(x, y) == false)
 487         return NULL;
 488     const CachedFrame* result = this;
 489     for (const CachedFrame* frame = mCachedFrames.begin();
 490             frame != mCachedFrames.end(); frame++) {
 491         const CachedFrame* frameResult = frame->findBestFrameAt(x, y);
 492         if (NULL != frameResult)
 493             result = frameResult;
 494     }
 495     return result;
 496 }
 497
 498 const CachedNode* CachedFrame::findBestHitAt(const WebCore::IntRect& rect,
 499     const CachedFrame** framePtr, int* x, int* y) const
 500 {
 501     mRoot->setupScrolledBounds();
 502     for (const CachedFrame* frame = mCachedFrames.end() - 1;
 503             frame != mCachedFrames.begin() - 1; frame--) {
 504         const CachedNode* frameResult = frame->findBestHitAt(rect,
 505             framePtr, x, y);
 506         if (NULL != frameResult)
 507             return frameResult;
 508     }
 509     for (const CachedNode* test = mCachedNodes.end() - 1;
 510             test != mCachedNodes.begin() - 1; test--) {
 511         if (test->disabled())
 512             continue;
 513         WebCore::IntRect testRect = test->hitBounds(this);
 514         if (testRect.intersects(rect) == false)
 515             continue;
 516         BestData testData;
 517         testData.mNode = test;
 518         testData.mFrame = this;
 519         testData.setMouseBounds(testRect);
 520         testData.setNodeBounds(testRect);
 521         if (mRoot->maskIfHidden(&testData) == true)
 522             continue;
 523         DBG_NAV_LOGD("candidate %d rect=(%d,%d,r=%d,b=%d)"
 524             " testRect=(%d,%d,r=%d,b=%d)",
 525             test->index(), rect.x(), rect.y(), rect.right(), rect.bottom(),
 526             testRect.x(), testRect.y(), testRect.right(), testRect.bottom());
 527         for (int i = 0; i < test->navableRects(); i++) {
 528             WebCore::IntRect cursorRect = test->ring(this, i);
 529             DBG_NAV_LOGD("candidate %d cursorRect=(%d,%d,r=%d,b=%d)",
 530                 i, cursorRect.x(), cursorRect.y(), cursorRect.right(),
 531                 cursorRect.bottom());
 532             if (cursorRect.intersects(rect)) {
 533                 WebCore::IntRect intersection(cursorRect);
 534                 intersection.intersect(rect);
 535                 *x = intersection.x() + (intersection.width() >> 1);
 536                 *y = intersection.y() + (intersection.height() >> 1);
 537                 *framePtr = this;
 538                 return test;
 539             }
 540         }
 541         testRect.intersect(rect);
 542         *x = testRect.x() + (testRect.width() >> 1);
 543         *y = testRect.y() + (testRect.height() >> 1);
 544         *framePtr = this;
 545         return test;
 546     }
 547     return NULL;
 548 }
 549
 550 void CachedFrame::findClosest(BestData* bestData, Direction originalDirection,
 551     Direction direction, WebCore::IntRect* clip) const
 552 {
 553     const CachedNode* test = mCachedNodes.begin();
 554     while ((test = test->traverseNextNode()) != NULL) {
 555         const CachedFrame* child = hasFrame(test);
 556         if (child != NULL) {
 557             const CachedNode* childDoc = child->validDocument();
 558             if (childDoc == NULL)
 559                 continue;
 560             child->findClosest(bestData, originalDirection, direction, clip);
 561         }
 562         if (test->noSecondChance())
 563             continue;
 564         if (test->isNavable(this, *clip) == false)
 565             continue;
 566         if (checkVisited(test, originalDirection) == false)
 567             continue;
 568         size_t partMax = test->navableRects();
 569         for (size_t part = 0; part < partMax; part++) {
 570             WebCore::IntRect testBounds = test->ring(this, part);
 571             if (clip->intersects(testBounds) == false)
 572                 continue;
 573             if (clip->contains(testBounds) == false) {
 574                 if (direction & UP_DOWN) {
 575 //                    if (testBounds.x() > clip->x() || testBounds.right() < clip->right())
 576 //                        continue;
 577                     testBounds.setX(clip->x());
 578                     testBounds.setWidth(clip->width());
 579                 } else {
 580 //                    if (testBounds.y() > clip->y() || testBounds.bottom() < clip->bottom())
 581 //                        continue;
 582                     testBounds.setY(clip->y());
 583                     testBounds.setHeight(clip->height());
 584                 }
 585                 if (clip->contains(testBounds) == false)
 586                     continue;
 587             }
 588             int distance;
 589             // seems like distance for UP for instance needs to be 'test top closest to
 590             // clip bottom' -- keep the old code but try this instead
 591             switch (direction) {
 592 #if 0
 593                 case LEFT: distance = testBounds.x() - clip->x(); break;
 594                 case RIGHT: distance = clip->right() - testBounds.right(); break;
 595                 case UP: distance = testBounds.y() - clip->y(); break;
 596                 case DOWN: distance = clip->bottom() - testBounds.bottom(); break;
 597 #else
 598                 case LEFT: distance = clip->right() - testBounds.x(); break;
 599                 case RIGHT: distance = testBounds.right()  - clip->x(); break;
 600                 case UP: distance = clip->bottom() - testBounds.y(); break;
 601                 case DOWN: distance = testBounds.bottom() - clip->y(); break;
 602 #endif
 603                 default:
 604                     distance = 0; ASSERT(0);
 605             }
 606             if (distance < bestData->mDistance) {
 607                 bestData->mNode = test;
 608                 bestData->mFrame = this;
 609                 bestData->mDistance = distance;
 610                 WebCore::IntRect rect = test->ring(this, part);
 611                 bestData->setMouseBounds(rect);
 612                 bestData->setNodeBounds(rect);
 613                 CachedHistory* cachedHistory = history();
 614                 switch (direction) {
 615                     case LEFT:
 616                         bestData->setLeftDirection(cachedHistory);
 617                     break;
 618                     case RIGHT:
 619                         bestData->setRightDirection(cachedHistory);
 620                     break;
 621                     case UP:
 622                         bestData->setUpDirection(cachedHistory);
 623                     break;
 624                     case DOWN:
 625                         bestData->setDownDirection(cachedHistory);
 626                     break;
 627                     default:
 628                         ASSERT(0);
 629                 }
 630             }
 631         }
 632     }
 633 }
 634
 635 void CachedFrame::finishInit()
 636 {
 637     CachedNode* lastCached = lastNode();
 638     lastCached->setLast();
 639     CachedFrame* child = mCachedFrames.begin();
 640     while (child != mCachedFrames.end()) {
 641         child->mParent = this;
 642         child->finishInit();
 643         child++;
 644     }
 645     CachedFrame* frameParent;
 646     if (mFocusIndex >= 0 && (frameParent = parent()))
 647         frameParent->setFocusIndex(indexInParent());
 648 }
 649
 650 const CachedNode* CachedFrame::frameDown(const CachedNode* test,
 651     const CachedNode* limit, BestData* bestData) const
 652 {
 653     BestData originalData = *bestData;
 654     do {
 655         if (moveInFrame(&CachedFrame::frameDown, test, bestData))
 656             continue;
 657         BestData testData;
 658         if (frameNodeCommon(testData, test, bestData, &originalData) == REJECT_TEST)
 659             continue;
 660         if (checkVisited(test, DOWN) == false)
 661             continue;
 662         size_t parts = test->navableRects();
 663         for (size_t part = 0; part < parts; part++) {
 664             testData.setNodeBounds(test->ring(this, part));
 665             if (testData.setDownDirection(history()))
 666                 continue;
 667             int result = framePartCommon(testData, test, bestData);
 668             if (result == REJECT_TEST)
 669                 continue;
 670             if (result == 0 && limit == NULL) { // retry all data up to this point, since smaller may have replaced node preferable to larger
 671                 BestData innerData = testData;
 672                 frameDown(document(), test, &innerData);
 673                 if (checkVisited(innerData.mNode, DOWN)) {
 674                     *bestData = innerData;
 675                     continue;
 676                 }
 677             }
 678             if (checkVisited(test, DOWN))
 679                 *bestData = testData;
 680         }
 681     } while ((test = test->traverseNextNode()) != limit);
 682     ASSERT(mRoot->mCursor == NULL || bestData->mNode != mRoot->mCursor);
 683     // does the best contain something (or, is it contained by an area which is not the cursor?)
 684         // if so, is the conainer/containee should have been chosen, but wasn't -- so there's a better choice
 685         // in the doc list prior to this choice
 686     //
 687     return bestData->mNode;
 688 }
 689
 690 const CachedNode* CachedFrame::frameLeft(const CachedNode* test,
 691     const CachedNode* limit, BestData* bestData) const
 692 {
 693     BestData originalData = *bestData;
 694     do {
 695         if (moveInFrame(&CachedFrame::frameLeft, test, bestData))
 696             continue;
 697         BestData testData;
 698         if (frameNodeCommon(testData, test, bestData, &originalData) == REJECT_TEST)
 699             continue;
 700         if (checkVisited(test, LEFT) == false)
 701             continue;
 702         size_t parts = test->navableRects();
 703         for (size_t part = 0; part < parts; part++) {
 704             testData.setNodeBounds(test->ring(this, part));
 705             if (testData.setLeftDirection(history()))
 706                 continue;
 707             int result = framePartCommon(testData, test, bestData);
 708             if (result == REJECT_TEST)
 709                 continue;
 710             if (result == 0 && limit == NULL) { // retry all data up to this point, since smaller may have replaced node preferable to larger
 711                 BestData innerData = testData;
 712                 frameLeft(document(), test, &innerData);
 713                 if (checkVisited(innerData.mNode, LEFT)) {
 714                     *bestData = innerData;
 715                     continue;
 716                 }
 717             }
 718             if (checkVisited(test, LEFT))
 719                 *bestData = testData;
 720         }
 721     } while ((test = test->traverseNextNode()) != limit);  // FIXME ??? left and up should use traversePreviousNode to choose reverse document order
 722     ASSERT(mRoot->mCursor == NULL || bestData->mNode != mRoot->mCursor);
 723     return bestData->mNode;
 724 }
 725
 726 int CachedFrame::frameNodeCommon(BestData& testData, const CachedNode* test,
 727     BestData* bestData, BestData* originalData) const
 728 {
 729     testData.mFrame = this;
 730     testData.mNode = test;
 731     test->clearCondition();
 732     if (test->disabled()) {
 733         testData.mNode->setCondition(CachedNode::DISABLED);
 734         return REJECT_TEST;
 735     }
 736     WebCore::IntRect bounds = test->bounds(this);
 737     if (bounds.isEmpty()) {
 738         testData.mNode->setCondition(CachedNode::NAVABLE);
 739         return REJECT_TEST;
 740     }
 741     if (mRoot->scrolledBounds().intersects(bounds) == false) {
 742         testData.mNode->setCondition(CachedNode::NAVABLE);
 743         return REJECT_TEST;
 744     }
 745     if (mRoot->rootLayer() && !test->isInLayer()
 746             && !mRoot->baseUncovered().intersects(bounds)) {
 747         testData.mNode->setCondition(CachedNode::UNDER_LAYER);
 748         return REJECT_TEST;
 749     }
 750 //    if (isNavable(test, &testData.mNodeBounds, walk) == false) {
 751 //        testData.mNode->setCondition(CachedNode::NAVABLE);
 752 //        return REJECT_TEST;
 753 //    }
 754 //
 755     if (test == mRoot->mCursor) {
 756         testData.mNode->setCondition(CachedNode::NOT_CURSOR_NODE);
 757         return REJECT_TEST;
 758     }
 759 //    if (test->bounds().contains(mRoot->mCursorBounds)) {
 760 //        testData.mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR);
 761 //        return REJECT_TEST;
 762 //    }
 763     void* par = mRoot->mCursor ? mRoot->mCursor->parentGroup() : NULL;
 764     testData.mCursorChild = par ? test->parentGroup() == par : false;
 765     if (bestData->mNode == NULL)
 766         return TEST_IS_BEST;
 767     if (mRoot->mCursor && testData.mNode->parentIndex() != bestData->mNode->parentIndex()) {
 768         int cursorParentIndex = mRoot->mCursor->parentIndex();
 769         if (cursorParentIndex >= 0) {
 770             if (bestData->mNode->parentIndex() == cursorParentIndex)
 771                 return REJECT_TEST;
 772             if (testData.mNode->parentIndex() == cursorParentIndex)
 773                 return TEST_IS_BEST;
 774         }
 775     }
 776     if (testData.mNode->parent() == bestData->mNode) {
 777         testData.mNode->setCondition(CachedNode::CHILD);
 778         return REJECT_TEST;
 779     }
 780     if (testData.mNode == bestData->mNode->parent())
 781         return TEST_IS_BEST;
 782     int testInBest = testData.isContainer(bestData); /* -1 pick best over test, 0 no containership, 1 pick test over best */
 783     if (testInBest == 1) {
 784         if (test->isArea() || bestData->mNode->isArea())
 785             return UNDECIDED;
 786         bestData->mNode = NULL;    // force part tests to be ignored, yet still set up remaining test data for later comparisons
 787         return TEST_IS_BEST;
 788     }
 789     if (testInBest == -1) {
 790         testData.mNode->setCondition(CachedNode::OUTSIDE_OF_BEST);
 791         return REJECT_TEST;
 792     }
 793     if (originalData->mNode != NULL) { // test is best case
 794         testInBest = testData.isContainer(originalData);
 795         if (testInBest == -1) { /* test is inside best */
 796             testData.mNode->setCondition(CachedNode::OUTSIDE_OF_ORIGINAL);
 797             return REJECT_TEST;
 798         }
 799     }
 800     return UNDECIDED;
 801 }
 802
 803 int CachedFrame::framePartCommon(BestData& testData,
 804     const CachedNode* test, BestData* bestData) const
 805 {
 806     if (mRoot->mCursor
 807             && testData.bounds().contains(mRoot->mCursorBounds)
 808             && !test->wantsKeyEvents()) {
 809         testData.mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR);
 810         return REJECT_TEST;
 811     }
 812     testData.setDistances();
 813     if (bestData->mNode != NULL) {
 814         int compared = compare(testData, *bestData);
 815         if (compared == 0 && test->isArea() == false && bestData->mNode->isArea() == false)
 816             goto pickTest;
 817         if (compared >= 0)
 818             return compared;
 819     }
 820 pickTest:
 821     return -1; // pick test
 822 }
 823
 824 const CachedNode* CachedFrame::frameRight(const CachedNode* test,
 825     const CachedNode* limit, BestData* bestData) const
 826 {
 827     BestData originalData = *bestData;
 828     do {
 829         if (moveInFrame(&CachedFrame::frameRight, test, bestData))
 830             continue;
 831         BestData testData;
 832         if (frameNodeCommon(testData, test, bestData, &originalData) == REJECT_TEST)
 833             continue;
 834         if (checkVisited(test, RIGHT) == false)
 835             continue;
 836         size_t parts = test->navableRects();
 837         for (size_t part = 0; part < parts; part++) {
 838             testData.setNodeBounds(test->ring(this, part));
 839             if (testData.setRightDirection(history()))
 840                 continue;
 841             int result = framePartCommon(testData, test, bestData);
 842             if (result == REJECT_TEST)
 843                 continue;
 844             if (result == 0 && limit == NULL) { // retry all data up to this point, since smaller may have replaced node preferable to larger
 845                 BestData innerData = testData;
 846                 frameRight(document(), test, &innerData);
 847                 if (checkVisited(innerData.mNode, RIGHT)) {
 848                     *bestData = innerData;
 849                     continue;
 850                 }
 851             }
 852             if (checkVisited(test, RIGHT))
 853                 *bestData = testData;
 854         }
 855     } while ((test = test->traverseNextNode()) != limit);
 856     ASSERT(mRoot->mCursor == NULL || bestData->mNode != mRoot->mCursor);
 857     return bestData->mNode;
 858 }
 859
 860 const CachedNode* CachedFrame::frameUp(const CachedNode* test,
 861     const CachedNode* limit, BestData* bestData) const
 862 {
 863     BestData originalData = *bestData;
 864     do {
 865         if (moveInFrame(&CachedFrame::frameUp, test, bestData))
 866             continue;
 867         BestData testData;
 868         if (frameNodeCommon(testData, test, bestData, &originalData) == REJECT_TEST)
 869             continue;
 870         if (checkVisited(test, UP) == false)
 871             continue;
 872         size_t parts = test->navableRects();
 873         for (size_t part = 0; part < parts; part++) {
 874             testData.setNodeBounds(test->ring(this, part));
 875             if (testData.setUpDirection(history()))
 876                 continue;
 877             int result = framePartCommon(testData, test, bestData);
 878             if (result == REJECT_TEST)
 879                 continue;
 880             if (result == 0 && limit == NULL) { // retry all data up to this point, since smaller may have replaced node preferable to larger
 881                 BestData innerData = testData;
 882                 frameUp(document(), test, &innerData);
 883                 if (checkVisited(innerData.mNode, UP)) {
 884                     *bestData = innerData;
 885                     continue;
 886                 }
 887             }
 888             if (checkVisited(test, UP))
 889                 *bestData = testData;
 890         }
 891     } while ((test = test->traverseNextNode()) != limit);  // FIXME ??? left and up should use traversePreviousNode to choose reverse document order
 892     ASSERT(mRoot->mCursor == NULL || bestData->mNode != mRoot->mCursor);
 893     return bestData->mNode;
 894 }
 895
 896 CachedFrame* CachedFrame::hasFrame(const CachedNode* node)
 897 {
 898     return node->isFrame() ? &mCachedFrames[node->childFrameIndex()] : NULL;
 899 }
 900
 901 void CachedFrame::hideCursor()
 902 {
 903     DBG_NAV_LOGD("mCursorIndex=%d", mCursorIndex);
 904     if (mCursorIndex < CURSOR_SET)
 905         return;
 906     CachedNode& cursor = mCachedNodes[mCursorIndex];
 907     cursor.hideCursor(this);
 908 }
 909
 910 CachedHistory* CachedFrame::history() const
 911 {
 912     return mRoot->rootHistory();
 913 }
 914
 915 void CachedFrame::init(const CachedRoot* root, int childFrameIndex,
 916     WebCore::Frame* frame)
 917 {
 918     mContents = WebCore::IntRect(0, 0, 0, 0); // fixed up for real in setData()
 919     mLocalViewBounds = WebCore::IntRect(0, 0, 0, 0);
 920     mViewBounds = WebCore::IntRect(0, 0, 0, 0);
 921     mRoot = root;
 922     mCursorIndex = CURSOR_UNINITIALIZED; // not explicitly cleared
 923     mFocusIndex = -1;
 924     mFrame = frame;
 925     mParent = NULL; // set up parents after stretchy arrays are set up
 926     mIndexInParent = childFrameIndex;
 927 }
 928
 929 #if USE(ACCELERATED_COMPOSITING)
 930 const CachedLayer* CachedFrame::layer(const CachedNode* node) const
 931 {
 932     if (!node->isInLayer())
 933         return 0;
 934     CachedLayer test;
 935     test.setCachedNodeIndex(node->index());
 936     return std::lower_bound(mCachedLayers.begin(), mCachedLayers.end(), test);
 937 }
 938 #endif
 939
 940 WebCore::IntRect CachedFrame::localBounds(const CachedNode* node,
 941     const WebCore::IntRect& rect) const
 942 {
 943     DBG_NAV_LOGD("node=%p [%d] rect=(%d,%d,w=%d,h=%d)",
 944         node, node->index(), rect.x(), rect.y(), rect.width(), rect.height());
 945 #if USE(ACCELERATED_COMPOSITING)
 946     return layer(node)->localBounds(mRoot->rootLayer(), rect);
 947 #else
 948     return rect;
 949 #endif
 950 }
 951
 952 int CachedFrame::minWorkingHorizontal() const
 953 {
 954     return history()->minWorkingHorizontal();
 955 }
 956
 957 int CachedFrame::minWorkingVertical() const
 958 {
 959     return history()->minWorkingVertical();
 960 }
 961
 962 int CachedFrame::maxWorkingHorizontal() const
 963 {
 964     return history()->maxWorkingHorizontal();
 965 }
 966
 967 int CachedFrame::maxWorkingVertical() const
 968 {
 969     return history()->maxWorkingVertical();
 970 }
 971
 972 const CachedNode* CachedFrame::nextTextField(const CachedNode* start,
 973         const CachedFrame** framePtr, bool* startFound) const
 974 {
 975     const CachedNode* test = mCachedNodes.begin();
 976     while ((test = test->traverseNextNode())) {
 977         const CachedFrame* frame = hasFrame(test);
 978         if (frame) {
 979             if (!frame->validDocument())
 980                 continue;
 981             const CachedNode* node
 982                     = frame->nextTextField(start, framePtr, startFound);
 983             if (node)
 984                 return node;
 985         } else if (test->isTextInput()) {
 986             if (test == start)
 987                 *startFound = true;
 988             else if (*startFound) {
 989                 if (framePtr)
 990                     *framePtr = this;
 991                 return test;
 992             }
 993         }
 994     }
 995     return 0;
 996 }
 997
 998 bool CachedFrame::moveInFrame(MoveInDirection moveInDirection,
 999     const CachedNode* test, BestData* bestData) const
1000 {
1001     const CachedFrame* frame = hasFrame(test);
1002     if (frame == NULL)
1003         return false; // if it's not a frame, let the caller have another swing at it
1004     const CachedNode* childDoc = frame->validDocument();
1005     if (childDoc == NULL)
1006         return true;
1007     (frame->*moveInDirection)(childDoc, NULL, bestData);
1008     return true;
1009 }
1010
1011 const WebCore::IntRect& CachedFrame::_navBounds() const
1012 {
1013     return history()->navBounds();
1014 }
1015
1016 SkPicture* CachedFrame::picture(const CachedNode* node) const
1017 {
1018 #if USE(ACCELERATED_COMPOSITING)
1019     if (node->isInLayer())
1020         return layer(node)->picture(mRoot->rootLayer());
1021 #endif
1022     return mRoot->mPicture;
1023 }
1024
1025 SkPicture* CachedFrame::picture(const CachedNode* node, int* xPtr, int* yPtr) const
1026 {
1027 #if USE(ACCELERATED_COMPOSITING)
1028     if (node->isInLayer()) {
1029         const CachedLayer* cachedLayer = layer(node);
1030         const LayerAndroid* rootLayer = mRoot->rootLayer();
1031         cachedLayer->toLocal(rootLayer, xPtr, yPtr);
1032         return cachedLayer->picture(rootLayer);
1033     }
1034 #endif
1035     return mRoot->mPicture;
1036 }
1037
1038 void CachedFrame::resetClippedOut()
1039 {
1040     for (CachedNode* test = mCachedNodes.begin(); test != mCachedNodes.end(); test++)
1041     {
1042         if (test->clippedOut()) {
1043             test->setDisabled(false);
1044             test->setClippedOut(false);
1045         }
1046     }
1047     for (CachedFrame* frame = mCachedFrames.begin(); frame != mCachedFrames.end();
1048             frame++) {
1049         frame->resetClippedOut();
1050     }
1051 }
1052
1053 void CachedFrame::resetLayers()
1054 {
1055 #if USE(ACCELERATED_COMPOSITING)
1056     for (CachedFrame* frame = mCachedFrames.begin(); frame != mCachedFrames.end();
1057             frame++) {
1058         frame->resetLayers();
1059     }
1060 #endif
1061 }
1062
1063 bool CachedFrame::sameFrame(const CachedFrame* test) const
1064 {
1065     ASSERT(test);
1066     if (mIndexInParent != test->mIndexInParent)
1067         return false;
1068     if (mIndexInParent == -1) // index within parent's array of children, or -1 if root
1069         return true;
1070     return mParent->sameFrame(test->mParent);
1071 }
1072
1073 void CachedFrame::setData()
1074 {
1075     if (this != mRoot) {
1076         mViewBounds = mLocalViewBounds;
1077         mViewBounds.intersect(mRoot->mViewBounds);
1078     }
1079     int x, y;
1080     if (parent() == NULL)
1081         x = y = 0;
1082     else {
1083         x = mLocalViewBounds.x();
1084         y = mLocalViewBounds.y();
1085     }
1086     mContents.setX(x);
1087     mContents.setY(y);
1088     CachedFrame* child = mCachedFrames.begin();
1089     while (child != mCachedFrames.end()) {
1090         child->setData();
1091         child++;
1092     }
1093 }
1094
1095 bool CachedFrame::setCursor(WebCore::Frame* frame, WebCore::Node* node,
1096     int x, int y)
1097 {
1098     if (NULL == node) {
1099         const_cast<CachedRoot*>(mRoot)->setCursor(NULL, NULL);
1100         return true;
1101     }
1102     if (mFrame != frame) {
1103         for (CachedFrame* testF = mCachedFrames.begin(); testF != mCachedFrames.end();
1104                 testF++) {
1105             if (testF->setCursor(frame, node, x, y))
1106                 return true;
1107         }
1108         DBG_NAV_LOGD("no frame frame=%p node=%p", frame, node);
1109         return false;
1110     }
1111     bool first = true;
1112     CachedNode const * const end = mCachedNodes.end();
1113     do {
1114         for (CachedNode* test = mCachedNodes.begin(); test != end; test++) {
1115             if (test->nodePointer() != node && first)
1116                 continue;
1117             size_t partMax = test->navableRects();
1118             for (size_t part = 0; part < partMax; part++) {
1119                 WebCore::IntRect testBounds = test->ring(this, part);
1120                 if (testBounds.contains(x, y) == false)
1121                     continue;
1122                 if (test->isCursor()) {
1123                     DBG_NAV_LOGD("already set? test=%d frame=%p node=%p x=%d y=%d",
1124                         test->index(), frame, node, x, y);
1125                     return false;
1126                 }
1127                 const_cast<CachedRoot*>(mRoot)->setCursor(this, test);
1128                 return true;
1129             }
1130         }
1131         DBG_NAV_LOGD("moved? frame=%p node=%p x=%d y=%d", frame, node, x, y);
1132     } while ((first ^= true) == false);
1133 failed:
1134     DBG_NAV_LOGD("no match frame=%p node=%p", frame, node);
1135     return false;
1136 }
1137
1138 const CachedNode* CachedFrame::validDocument() const
1139 {
1140     const CachedNode* doc = document();
1141     return doc != NULL && mViewBounds.isEmpty() == false ? doc : NULL;
1142 }
1143
1144 bool CachedFrame::BestData::canBeReachedByAnotherDirection()
1145 {
1146     if (mMajorButt > -MIN_OVERLAP)
1147         return false;
1148     mMajorButt = -mMajorButt;
1149     return mNavOutside;
1150 }
1151
1152 int CachedFrame::BestData::isContainer(CachedFrame::BestData* other)
1153 {
1154     int _x = x();
1155     int otherRight = other->right();
1156     if (_x >= otherRight)
1157         return 0; // does not intersect
1158     int _y = y();
1159     int otherBottom = other->bottom();
1160     if (_y >= otherBottom)
1161         return 0; // does not intersect
1162     int _right = right();
1163     int otherX = other->x();
1164     if (otherX >= _right)
1165         return 0; // does not intersect
1166     int _bottom = bottom();
1167     int otherY = other->y();
1168     if (otherY >= _bottom)
1169         return 0; // does not intersect
1170     int intoX = otherX - _x;
1171     int intoY = otherY - _y;
1172     int intoRight = otherRight - _right;
1173     int intoBottom = otherBottom - _bottom;
1174     bool contains = intoX >= 0 && intoY >= 0 && intoRight <= 0 && intoBottom <= 0;
1175     if (contains && mNode->partRectsContains(other->mNode)) {
1176 //        if (mIsArea == false && hasMouseOver())
1177 //            other->mMouseOver = mNode;
1178         return mNode->isArea() ? 1  : -1;
1179     }
1180     bool containedBy = intoX <= 0 && intoY <= 0 && intoRight >= 0 && intoBottom >= 0;
1181     if (containedBy && other->mNode->partRectsContains(mNode)) {
1182 //        if (other->mIsArea == false && other->hasMouseOver())
1183 //            mMouseOver = other->mNode;
1184         return other->mNode->isArea() ? -1  : 1;
1185     }
1186     return 0;
1187 }
1188
1189 // distance scale factor factor as a 16.16 scalar
1190 SkFixed CachedFrame::BestData::Overlap(int span, int left, int right)
1191 {
1192     unsigned result;
1193     if (left > 0 && left < span && right > span)
1194         result = (unsigned) left;
1195     else if (right > 0 && right < span && left > span)
1196         result = (unsigned) right;
1197     else if (left > 0 && right > 0)
1198         return SK_Fixed1;
1199     else
1200         return 0;
1201     result = (result << 16) / (unsigned) span; // linear proportion, always less than fixed 1
1202     return (SkFixed) result;
1203 // !!! experiment with weight -- enable if overlaps are preferred too much
1204 // or reverse weighting if overlaps are preferred to little
1205 //    return (SkFixed) (result * result >> 16); // but fall off with square
1206 }
1207
1208 void CachedFrame::BestData::setDistances()
1209 {
1210     mDistance = abs(mMajorDelta);
1211     int sideDistance = mWorkingDelta;
1212     if (mWorkingOverlap < SK_Fixed1) {
1213         if (mPreferred > 0)
1214             sideDistance = mWorkingDelta2;
1215     } else if (sideDistance >= 0 && mWorkingDelta2 >=- 0)
1216         sideDistance = 0;
1217     else {
1218         ASSERT(sideDistance <= 0 && mWorkingDelta2 <= 0);
1219         if (sideDistance < mWorkingDelta2)
1220             sideDistance = mWorkingDelta2;
1221     }
1222     // if overlap, smaller abs mWorkingDelta is better, smaller abs majorDelta is better
1223     // if not overlap, positive mWorkingDelta is better
1224     mSideDistance = sideDistance;
1225 }
1226
1227 bool CachedFrame::BestData::setDownDirection(const CachedHistory* history)
1228 {
1229     const WebCore::IntRect& navBounds = history->navBounds();
1230     mMajorButt = mNodeBounds.y() - navBounds.bottom();
1231     int testX = mNodeBounds.x();
1232     int testRight = mNodeBounds.right();
1233     setNavOverlap(navBounds.width(), navBounds.right() - testX,
1234         testRight - navBounds.x());
1235     if (canBeReachedByAnotherDirection()) {
1236         mNode->setCondition(CachedNode::BEST_DIRECTION);
1237         return REJECT_TEST;
1238     }
1239     int inNavTop = mNodeBounds.y() - navBounds.y();
1240     mMajorDelta2 = inNavTop;
1241     mMajorDelta = mMajorDelta2 + ((mNodeBounds.height() -
1242         navBounds.height()) >> 1);
1243     if (mMajorDelta2 <= 1 && mMajorDelta <= 1) {
1244         mNode->setCondition(CachedNode::CENTER_FURTHER); // never move up or sideways
1245         return REJECT_TEST;
1246     }
1247     int inNavBottom = navBounds.bottom() - mNodeBounds.bottom();
1248     setNavInclusion(testRight - navBounds.right(), navBounds.x() - testX);
1249     bool subsumes = navBounds.height() > 0 && inOrSubsumesNav();
1250     if (inNavTop <= 0 && inNavBottom <= 0 && subsumes && !mNode->wantsKeyEvents()) {
1251         mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR);
1252         return REJECT_TEST;
1253     }
1254     int maxV = history->maxWorkingVertical();
1255     int minV = history->minWorkingVertical();
1256     setWorkingOverlap(testRight - testX, maxV - testX, testRight - minV);
1257     setWorkingInclusion(testRight - maxV, minV - testX);
1258     if (mWorkingOverlap == 0 && mNavOverlap == 0 && inNavBottom >= 0) {
1259         mNode->setCondition(CachedNode::OVERLAP_OR_EDGE_FURTHER);
1260         return REJECT_TEST;
1261     }
1262     mInNav = history->directionChange() && inNavTop >= 0 &&
1263         inNavBottom > 0 && subsumes;
1264     return false;
1265 }
1266
1267 bool CachedFrame::BestData::setLeftDirection(const CachedHistory* history)
1268 {
1269     const WebCore::IntRect& navBounds = history->navBounds();
1270     mMajorButt = navBounds.x() - mNodeBounds.right();
1271     int testY = mNodeBounds.y();
1272     int testBottom = mNodeBounds.bottom();
1273     setNavOverlap(navBounds.height(), navBounds.bottom() - testY,
1274         testBottom - navBounds.y());
1275     if (canBeReachedByAnotherDirection()) {
1276         mNode->setCondition(CachedNode::BEST_DIRECTION);
1277         return REJECT_TEST;
1278     }
1279     int inNavRight = navBounds.right() - mNodeBounds.right();
1280     mMajorDelta2 = inNavRight;
1281     mMajorDelta = mMajorDelta2 - ((navBounds.width() -
1282         mNodeBounds.width()) >> 1);
1283     if (mMajorDelta2 <= 1 && mMajorDelta <= 1) {
1284         mNode->setCondition(CachedNode::CENTER_FURTHER); // never move right or sideways
1285         return REJECT_TEST;
1286     }
1287     int inNavLeft = mNodeBounds.x() - navBounds.x();
1288     setNavInclusion(navBounds.y() - testY, testBottom - navBounds.bottom());
1289     bool subsumes = navBounds.width() > 0 && inOrSubsumesNav();
1290     if (inNavLeft <= 0 && inNavRight <= 0 && subsumes && !mNode->wantsKeyEvents()) {
1291         mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR);
1292         return REJECT_TEST;
1293     }
1294     int maxH = history->maxWorkingHorizontal();
1295     int minH = history->minWorkingHorizontal();
1296     setWorkingOverlap(testBottom - testY, maxH - testY, testBottom - minH);
1297     setWorkingInclusion(minH - testY, testBottom - maxH);
1298     if (mWorkingOverlap == 0 && mNavOverlap == 0 && inNavLeft >= 0) {
1299         mNode->setCondition(CachedNode::OVERLAP_OR_EDGE_FURTHER);
1300         return REJECT_TEST;
1301     }
1302     mInNav = history->directionChange() && inNavLeft >= 0 &&
1303         inNavRight > 0 && subsumes; /* both L/R in or out */
1304     return false;
1305 }
1306
1307 bool CachedFrame::BestData::setRightDirection(const CachedHistory* history)
1308 {
1309     const WebCore::IntRect& navBounds = history->navBounds();
1310     mMajorButt = mNodeBounds.x() - navBounds.right();
1311     int testY = mNodeBounds.y();
1312     int testBottom = mNodeBounds.bottom();
1313     setNavOverlap(navBounds.height(), navBounds.bottom() - testY,
1314         testBottom - navBounds.y());
1315     if (canBeReachedByAnotherDirection()) {
1316         mNode->setCondition(CachedNode::BEST_DIRECTION);
1317         return REJECT_TEST;
1318     }
1319     int inNavLeft = mNodeBounds.x() - navBounds.x();
1320     mMajorDelta2 = inNavLeft;
1321     mMajorDelta = mMajorDelta2 + ((mNodeBounds.width() -
1322         navBounds.width()) >> 1);
1323     if (mMajorDelta2 <= 1 && mMajorDelta <= 1) {
1324         mNode->setCondition(CachedNode::CENTER_FURTHER); // never move left or sideways
1325         return REJECT_TEST;
1326     }
1327     int inNavRight = navBounds.right() - mNodeBounds.right();
1328     setNavInclusion(testBottom - navBounds.bottom(), navBounds.y() - testY);
1329     bool subsumes = navBounds.width() > 0 && inOrSubsumesNav();
1330     if (inNavLeft <= 0 && inNavRight <= 0 && subsumes && !mNode->wantsKeyEvents()) {
1331         mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR);
1332         return REJECT_TEST;
1333     }
1334     int maxH = history->maxWorkingHorizontal();
1335     int minH = history->minWorkingHorizontal();
1336     setWorkingOverlap(testBottom - testY, testBottom - minH, maxH - testY);
1337     setWorkingInclusion(testBottom - maxH, minH - testY);
1338     if (mWorkingOverlap == 0 && mNavOverlap == 0 && inNavRight >= 0) {
1339         mNode->setCondition(CachedNode::OVERLAP_OR_EDGE_FURTHER);
1340         return REJECT_TEST;
1341     }
1342     mInNav = history->directionChange() && inNavLeft >= 0 &&
1343         inNavRight > 0 && subsumes; /* both L/R in or out */
1344     return false;
1345 }
1346
1347 bool CachedFrame::BestData::setUpDirection(const CachedHistory* history)
1348 {
1349     const WebCore::IntRect& navBounds = history->navBounds();
1350     mMajorButt = navBounds.y() - mNodeBounds.bottom();
1351     int testX = mNodeBounds.x();
1352     int testRight = mNodeBounds.right();
1353     setNavOverlap(navBounds.width(), navBounds.right() - testX,
1354         testRight - navBounds.x());
1355     if (canBeReachedByAnotherDirection()) {
1356         mNode->setCondition(CachedNode::BEST_DIRECTION);
1357         return REJECT_TEST;
1358     }
1359     int inNavBottom = navBounds.bottom() - mNodeBounds.bottom();
1360     mMajorDelta2 = inNavBottom;
1361     mMajorDelta = mMajorDelta2 - ((navBounds.height() -
1362         mNodeBounds.height()) >> 1);
1363     if (mMajorDelta2 <= 1 && mMajorDelta <= 1) {
1364         mNode->setCondition(CachedNode::CENTER_FURTHER); // never move down or sideways
1365         return REJECT_TEST;
1366     }
1367     int inNavTop = mNodeBounds.y() - navBounds.y();
1368     setNavInclusion(navBounds.x() - testX, testRight - navBounds.right());
1369     bool subsumes = navBounds.height() > 0 && inOrSubsumesNav();
1370     if (inNavTop <= 0 && inNavBottom <= 0 && subsumes && !mNode->wantsKeyEvents()) {
1371         mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR);
1372         return REJECT_TEST;
1373     }
1374     int maxV = history->maxWorkingVertical();
1375     int minV = history->minWorkingVertical();
1376     setWorkingOverlap(testRight - testX, testRight - minV, maxV - testX);
1377     setWorkingInclusion(minV - testX, testRight - maxV);
1378     if (mWorkingOverlap == 0 && mNavOverlap == 0 && inNavTop >= 0) {
1379         mNode->setCondition(CachedNode::OVERLAP_OR_EDGE_FURTHER);
1380         return REJECT_TEST;
1381     }
1382     mInNav = history->directionChange() && inNavTop >= 0 &&
1383         inNavBottom > 0 && subsumes; /* both L/R in or out */
1384     return false;
1385 }
1386
1387 void CachedFrame::BestData::setNavInclusion(int left, int right)
1388 {
1389     // if left and right <= 0, test node is completely in umbra of cursor
1390         // prefer leftmost center
1391     // if left and right > 0, test node subsumes cursor
1392     mNavDelta = left;
1393     mNavDelta2 = right;
1394 }
1395
1396 void CachedFrame::BestData::setNavOverlap(int span, int left, int right)
1397 {
1398     // if left or right < 0, test node is not in umbra of cursor
1399     mNavOutside = left < MIN_OVERLAP || right < MIN_OVERLAP;
1400     mNavOverlap = Overlap(span, left, right); // prefer smallest negative left
1401 }
1402
1403 void CachedFrame::BestData::setWorkingInclusion(int left, int right)
1404 {
1405     mWorkingDelta = left;
1406     mWorkingDelta2 = right;
1407 }
1408
1409 // distance scale factor factor as a 16.16 scalar
1410 void CachedFrame::BestData::setWorkingOverlap(int span, int left, int right)
1411 {
1412     // if left or right < 0, test node is not in umbra of cursor
1413     mWorkingOutside = left < MIN_OVERLAP || right < MIN_OVERLAP;
1414     mWorkingOverlap = Overlap(span, left, right);
1415     mPreferred = left <= 0 ? 0 : left;
1416 }
1417
1418 #if DUMP_NAV_CACHE
1419
1420 #define DEBUG_PRINT_RECT(prefix, debugName, field) \
1421     { const WebCore::IntRect& r = b->field; \
1422     DUMP_NAV_LOGD("%s DebugTestRect TEST%s_" #debugName "={%d, %d, %d, %d}; //" #field "\n", \
1423         prefix, mFrameName, r.x(), r.y(), r.width(), r.height()); }
1424
1425 CachedFrame* CachedFrame::Debug::base() const {
1426     CachedFrame* nav = (CachedFrame*) ((char*) this - OFFSETOF(CachedFrame, mDebug));
1427     return nav;
1428 }
1429
1430 void CachedFrame::Debug::print() const
1431 {
1432     CachedFrame* b = base();
1433     DEBUG_PRINT_RECT("//", CONTENTS, mContents);
1434     DEBUG_PRINT_RECT("", BOUNDS, mLocalViewBounds);
1435     DEBUG_PRINT_RECT("//", VIEW, mViewBounds);
1436
1437     DUMP_NAV_LOGD("// CachedNode mCachedNodes={ // count=%d\n", b->mCachedNodes.size());
1438     for (CachedNode* node = b->mCachedNodes.begin();
1439             node != b->mCachedNodes.end(); node++) {
1440         node->mDebug.print();
1441         const CachedInput* input = b->textInput(node);
1442         if (input)
1443             input->mDebug.print();
1444         DUMP_NAV_LOGD("\n");
1445     }
1446     DUMP_NAV_LOGD("// }; // end of nodes\n");
1447 #if USE(ACCELERATED_COMPOSITING)
1448     DUMP_NAV_LOGD("// CachedLayer mCachedLayers={ // count=%d\n", b->mCachedLayers.size());
1449     for (CachedLayer* layer = b->mCachedLayers.begin();
1450             layer != b->mCachedLayers.end(); layer++) {
1451         layer->mDebug.print();
1452     }
1453     DUMP_NAV_LOGD("// }; // end of layers\n");
1454 #endif // USE(ACCELERATED_COMPOSITING)
1455     DUMP_NAV_LOGD("// CachedColor mCachedColors={ // count=%d\n", b->mCachedColors.size());
1456     for (CachedColor* color = b->mCachedColors.begin();
1457             color != b->mCachedColors.end(); color++) {
1458         color->mDebug.print();
1459     }
1460     DUMP_NAV_LOGD("// }; // end of colors\n");
1461     DUMP_NAV_LOGD("// CachedFrame mCachedFrames={ // count=%d\n", b->mCachedFrames.size());
1462     for (CachedFrame* child = b->mCachedFrames.begin();
1463             child != b->mCachedFrames.end(); child++)
1464     {
1465         child->mDebug.print();
1466     }
1467     DUMP_NAV_LOGD("// }; // end of child frames\n");
1468     DUMP_NAV_LOGD("// void* mFrame=(void*) %p;\n", b->mFrame);
1469     DUMP_NAV_LOGD("// CachedFrame* mParent=%p;\n", b->mParent);
1470     DUMP_NAV_LOGD("// int mIndexInParent=%d;\n", b->mIndexInParent);
1471     DUMP_NAV_LOGD("// const CachedRoot* mRoot=%p;\n", b->mRoot);
1472     DUMP_NAV_LOGD("// int mCursorIndex=%d;\n", b->mCursorIndex);
1473     DUMP_NAV_LOGD("// int mFocusIndex=%d;\n", b->mFocusIndex);
1474 }
1475
1476 bool CachedFrame::Debug::validate(const CachedNode* node) const
1477 {
1478     const CachedFrame* b = base();
1479     if (b->mCachedNodes.size() == 0)
1480         return false;
1481     if (node >= b->mCachedNodes.begin() && node < b->mCachedNodes.end())
1482         return true;
1483     for (const CachedFrame* child = b->mCachedFrames.begin();
1484             child != b->mCachedFrames.end(); child++)
1485         if (child->mDebug.validate(node))
1486             return true;
1487     return false;
1488 }
1489
1490 #undef DEBUG_PRINT_RECT
1491
1492 #endif
1493
1494 }