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