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.maxY() : prior.maxY(); 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.maxX(); 83 int testRight = bestRect.maxX(); 84 if (right < testRight) 85 right = testRight; 86 width = right - left; 87 } else { 88 left = direction == LEFT ? bestRect.maxX() : prior.maxX(); 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.maxY(); 98 int testBottom = bestRect.maxY(); 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.maxX(), rect.maxY(), 526 testRect.x(), testRect.y(), testRect.maxX(), testRect.maxY()); 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.maxX(), 531 cursorRect.maxY()); 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: 594 distance = testBounds.x() - clip->x(); 595 break; 596 case RIGHT: 597 distance = clip->right() - testBounds.right(); 598 break; 599 case UP: 600 distance = testBounds.y() - clip->y(); 601 break; 602 case DOWN: 603 distance = clip->bottom() - testBounds.bottom(); 604 break; 605 #else 606 case LEFT: 607 distance = clip->maxX() - testBounds.x(); 608 break; 609 case RIGHT: 610 distance = testBounds.maxX() - clip->x(); 611 break; 612 case UP: 613 distance = clip->maxY() - testBounds.y(); 614 break; 615 case DOWN: 616 distance = testBounds.maxY() - clip->y(); 617 break; 618 #endif 619 default: 620 distance = 0; 621 ASSERT(false); 622 } 623 if (distance < bestData->mDistance) { 624 bestData->mNode = test; 625 bestData->mFrame = this; 626 bestData->mDistance = distance; 627 WebCore::IntRect rect = test->ring(this, part); 628 bestData->setMouseBounds(rect); 629 bestData->setNodeBounds(rect); 630 CachedHistory* cachedHistory = history(); 631 switch (direction) { 632 case LEFT: 633 bestData->setLeftDirection(cachedHistory); 634 break; 635 case RIGHT: 636 bestData->setRightDirection(cachedHistory); 637 break; 638 case UP: 639 bestData->setUpDirection(cachedHistory); 640 break; 641 case DOWN: 642 bestData->setDownDirection(cachedHistory); 643 break; 644 default: 645 ASSERT(0); 646 } 647 } 648 } 649 } 650 } 651 652 void CachedFrame::finishInit() 653 { 654 CachedNode* lastCached = lastNode(); 655 lastCached->setLast(); 656 CachedFrame* child = mCachedFrames.begin(); 657 while (child != mCachedFrames.end()) { 658 child->mParent = this; 659 child->finishInit(); 660 child++; 661 } 662 CachedFrame* frameParent; 663 if (mFocusIndex >= 0 && (frameParent = parent())) 664 frameParent->setFocusIndex(indexInParent()); 665 } 666 667 const CachedNode* CachedFrame::frameDown(const CachedNode* test, 668 const CachedNode* limit, BestData* bestData) const 669 { 670 BestData originalData = *bestData; 671 do { 672 if (moveInFrame(&CachedFrame::frameDown, test, bestData)) 673 continue; 674 BestData testData; 675 if (frameNodeCommon(testData, test, bestData, &originalData) == REJECT_TEST) 676 continue; 677 if (checkVisited(test, DOWN) == false) 678 continue; 679 size_t parts = test->navableRects(); 680 for (size_t part = 0; part < parts; part++) { 681 testData.setNodeBounds(test->ring(this, part)); 682 if (testData.setDownDirection(history())) 683 continue; 684 int result = framePartCommon(testData, test, bestData); 685 if (result == REJECT_TEST) 686 continue; 687 if (result == 0 && limit == NULL) { // retry all data up to this point, since smaller may have replaced node preferable to larger 688 BestData innerData = testData; 689 frameDown(document(), test, &innerData); 690 if (checkVisited(innerData.mNode, DOWN)) { 691 *bestData = innerData; 692 continue; 693 } 694 } 695 if (checkVisited(test, DOWN)) 696 *bestData = testData; 697 } 698 } while ((test = test->traverseNextNode()) != limit); 699 ASSERT(mRoot->mCursor == NULL || bestData->mNode != mRoot->mCursor); 700 // does the best contain something (or, is it contained by an area which is not the cursor?) 701 // if so, is the conainer/containee should have been chosen, but wasn't -- so there's a better choice 702 // in the doc list prior to this choice 703 // 704 return bestData->mNode; 705 } 706 707 const CachedNode* CachedFrame::frameLeft(const CachedNode* test, 708 const CachedNode* limit, BestData* bestData) const 709 { 710 BestData originalData = *bestData; 711 do { 712 if (moveInFrame(&CachedFrame::frameLeft, test, bestData)) 713 continue; 714 BestData testData; 715 if (frameNodeCommon(testData, test, bestData, &originalData) == REJECT_TEST) 716 continue; 717 if (checkVisited(test, LEFT) == false) 718 continue; 719 size_t parts = test->navableRects(); 720 for (size_t part = 0; part < parts; part++) { 721 testData.setNodeBounds(test->ring(this, part)); 722 if (testData.setLeftDirection(history())) 723 continue; 724 int result = framePartCommon(testData, test, bestData); 725 if (result == REJECT_TEST) 726 continue; 727 if (result == 0 && limit == NULL) { // retry all data up to this point, since smaller may have replaced node preferable to larger 728 BestData innerData = testData; 729 frameLeft(document(), test, &innerData); 730 if (checkVisited(innerData.mNode, LEFT)) { 731 *bestData = innerData; 732 continue; 733 } 734 } 735 if (checkVisited(test, LEFT)) 736 *bestData = testData; 737 } 738 } while ((test = test->traverseNextNode()) != limit); // FIXME ??? left and up should use traversePreviousNode to choose reverse document order 739 ASSERT(mRoot->mCursor == NULL || bestData->mNode != mRoot->mCursor); 740 return bestData->mNode; 741 } 742 743 int CachedFrame::frameNodeCommon(BestData& testData, const CachedNode* test, 744 BestData* bestData, BestData* originalData) const 745 { 746 testData.mFrame = this; 747 testData.mNode = test; 748 test->clearCondition(); 749 if (test->disabled()) { 750 testData.mNode->setCondition(CachedNode::DISABLED); 751 return REJECT_TEST; 752 } 753 WebCore::IntRect bounds = test->bounds(this); 754 if (bounds.isEmpty()) { 755 testData.mNode->setCondition(CachedNode::NAVABLE); 756 return REJECT_TEST; 757 } 758 if (mRoot->scrolledBounds().intersects(bounds) == false) { 759 testData.mNode->setCondition(CachedNode::NAVABLE); 760 return REJECT_TEST; 761 } 762 if (mRoot->rootLayer() && !test->isInLayer() 763 && !mRoot->baseUncovered().intersects(bounds)) { 764 testData.mNode->setCondition(CachedNode::UNDER_LAYER); 765 return REJECT_TEST; 766 } 767 // if (isNavable(test, &testData.mNodeBounds, walk) == false) { 768 // testData.mNode->setCondition(CachedNode::NAVABLE); 769 // return REJECT_TEST; 770 // } 771 // 772 if (test == mRoot->mCursor) { 773 testData.mNode->setCondition(CachedNode::NOT_CURSOR_NODE); 774 return REJECT_TEST; 775 } 776 // if (test->bounds().contains(mRoot->mCursorBounds)) { 777 // testData.mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR); 778 // return REJECT_TEST; 779 // } 780 void* par = mRoot->mCursor ? mRoot->mCursor->parentGroup() : NULL; 781 testData.mCursorChild = par ? test->parentGroup() == par : false; 782 if (bestData->mNode == NULL) 783 return TEST_IS_BEST; 784 if (mRoot->mCursor && testData.mNode->parentIndex() != bestData->mNode->parentIndex()) { 785 int cursorParentIndex = mRoot->mCursor->parentIndex(); 786 if (cursorParentIndex >= 0) { 787 if (bestData->mNode->parentIndex() == cursorParentIndex) 788 return REJECT_TEST; 789 if (testData.mNode->parentIndex() == cursorParentIndex) 790 return TEST_IS_BEST; 791 } 792 } 793 if (testData.mNode->parent() == bestData->mNode) { 794 testData.mNode->setCondition(CachedNode::CHILD); 795 return REJECT_TEST; 796 } 797 if (testData.mNode == bestData->mNode->parent()) 798 return TEST_IS_BEST; 799 int testInBest = testData.isContainer(bestData); /* -1 pick best over test, 0 no containership, 1 pick test over best */ 800 if (testInBest == 1) { 801 if (test->isArea() || bestData->mNode->isArea()) 802 return UNDECIDED; 803 bestData->mNode = NULL; // force part tests to be ignored, yet still set up remaining test data for later comparisons 804 return TEST_IS_BEST; 805 } 806 if (testInBest == -1) { 807 testData.mNode->setCondition(CachedNode::OUTSIDE_OF_BEST); 808 return REJECT_TEST; 809 } 810 if (originalData->mNode != NULL) { // test is best case 811 testInBest = testData.isContainer(originalData); 812 if (testInBest == -1) { /* test is inside best */ 813 testData.mNode->setCondition(CachedNode::OUTSIDE_OF_ORIGINAL); 814 return REJECT_TEST; 815 } 816 } 817 return UNDECIDED; 818 } 819 820 int CachedFrame::framePartCommon(BestData& testData, 821 const CachedNode* test, BestData* bestData) const 822 { 823 if (mRoot->mCursor 824 && testData.bounds().contains(mRoot->mCursorBounds) 825 && !test->wantsKeyEvents()) { 826 testData.mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR); 827 return REJECT_TEST; 828 } 829 testData.setDistances(); 830 if (bestData->mNode != NULL) { 831 int compared = compare(testData, *bestData); 832 if (compared == 0 && test->isArea() == false && bestData->mNode->isArea() == false) 833 goto pickTest; 834 if (compared >= 0) 835 return compared; 836 } 837 pickTest: 838 return -1; // pick test 839 } 840 841 const CachedNode* CachedFrame::frameRight(const CachedNode* test, 842 const CachedNode* limit, BestData* bestData) const 843 { 844 BestData originalData = *bestData; 845 do { 846 if (moveInFrame(&CachedFrame::frameRight, test, bestData)) 847 continue; 848 BestData testData; 849 if (frameNodeCommon(testData, test, bestData, &originalData) == REJECT_TEST) 850 continue; 851 if (checkVisited(test, RIGHT) == false) 852 continue; 853 size_t parts = test->navableRects(); 854 for (size_t part = 0; part < parts; part++) { 855 testData.setNodeBounds(test->ring(this, part)); 856 if (testData.setRightDirection(history())) 857 continue; 858 int result = framePartCommon(testData, test, bestData); 859 if (result == REJECT_TEST) 860 continue; 861 if (result == 0 && limit == NULL) { // retry all data up to this point, since smaller may have replaced node preferable to larger 862 BestData innerData = testData; 863 frameRight(document(), test, &innerData); 864 if (checkVisited(innerData.mNode, RIGHT)) { 865 *bestData = innerData; 866 continue; 867 } 868 } 869 if (checkVisited(test, RIGHT)) 870 *bestData = testData; 871 } 872 } while ((test = test->traverseNextNode()) != limit); 873 ASSERT(mRoot->mCursor == NULL || bestData->mNode != mRoot->mCursor); 874 return bestData->mNode; 875 } 876 877 const CachedNode* CachedFrame::frameUp(const CachedNode* test, 878 const CachedNode* limit, BestData* bestData) const 879 { 880 BestData originalData = *bestData; 881 do { 882 if (moveInFrame(&CachedFrame::frameUp, test, bestData)) 883 continue; 884 BestData testData; 885 if (frameNodeCommon(testData, test, bestData, &originalData) == REJECT_TEST) 886 continue; 887 if (checkVisited(test, UP) == false) 888 continue; 889 size_t parts = test->navableRects(); 890 for (size_t part = 0; part < parts; part++) { 891 testData.setNodeBounds(test->ring(this, part)); 892 if (testData.setUpDirection(history())) 893 continue; 894 int result = framePartCommon(testData, test, bestData); 895 if (result == REJECT_TEST) 896 continue; 897 if (result == 0 && limit == NULL) { // retry all data up to this point, since smaller may have replaced node preferable to larger 898 BestData innerData = testData; 899 frameUp(document(), test, &innerData); 900 if (checkVisited(innerData.mNode, UP)) { 901 *bestData = innerData; 902 continue; 903 } 904 } 905 if (checkVisited(test, UP)) 906 *bestData = testData; 907 } 908 } while ((test = test->traverseNextNode()) != limit); // FIXME ??? left and up should use traversePreviousNode to choose reverse document order 909 ASSERT(mRoot->mCursor == NULL || bestData->mNode != mRoot->mCursor); 910 return bestData->mNode; 911 } 912 913 CachedFrame* CachedFrame::hasFrame(const CachedNode* node) 914 { 915 return node->isFrame() ? &mCachedFrames[node->childFrameIndex()] : NULL; 916 } 917 918 void CachedFrame::hideCursor() 919 { 920 DBG_NAV_LOGD("mCursorIndex=%d", mCursorIndex); 921 if (mCursorIndex < CURSOR_SET) 922 return; 923 CachedNode& cursor = mCachedNodes[mCursorIndex]; 924 cursor.hideCursor(this); 925 } 926 927 CachedHistory* CachedFrame::history() const 928 { 929 return mRoot->rootHistory(); 930 } 931 932 void CachedFrame::init(const CachedRoot* root, int childFrameIndex, 933 WebCore::Frame* frame) 934 { 935 mContents = WebCore::IntRect(0, 0, 0, 0); // fixed up for real in setData() 936 mLocalViewBounds = WebCore::IntRect(0, 0, 0, 0); 937 mViewBounds = WebCore::IntRect(0, 0, 0, 0); 938 mRoot = root; 939 mCursorIndex = CURSOR_UNINITIALIZED; // not explicitly cleared 940 mFocusIndex = -1; 941 mFrame = frame; 942 mParent = NULL; // set up parents after stretchy arrays are set up 943 mIndexInParent = childFrameIndex; 944 } 945 946 #if USE(ACCELERATED_COMPOSITING) 947 const CachedLayer* CachedFrame::layer(const CachedNode* node) const 948 { 949 if (!node->isInLayer()) 950 return 0; 951 CachedLayer test; 952 test.setCachedNodeIndex(node->index()); 953 return std::lower_bound(mCachedLayers.begin(), mCachedLayers.end(), test); 954 } 955 #endif 956 957 WebCore::IntRect CachedFrame::localBounds(const CachedNode* node, 958 const WebCore::IntRect& rect) const 959 { 960 DBG_NAV_LOGD("node=%p [%d] rect=(%d,%d,w=%d,h=%d)", 961 node, node->index(), rect.x(), rect.y(), rect.width(), rect.height()); 962 #if USE(ACCELERATED_COMPOSITING) 963 return layer(node)->localBounds(mRoot->rootLayer(), rect); 964 #else 965 return rect; 966 #endif 967 } 968 969 int CachedFrame::minWorkingHorizontal() const 970 { 971 return history()->minWorkingHorizontal(); 972 } 973 974 int CachedFrame::minWorkingVertical() const 975 { 976 return history()->minWorkingVertical(); 977 } 978 979 int CachedFrame::maxWorkingHorizontal() const 980 { 981 return history()->maxWorkingHorizontal(); 982 } 983 984 int CachedFrame::maxWorkingVertical() const 985 { 986 return history()->maxWorkingVertical(); 987 } 988 989 const CachedNode* CachedFrame::nextTextField(const CachedNode* start, 990 const CachedFrame** framePtr, bool* startFound) const 991 { 992 const CachedNode* test = mCachedNodes.begin(); 993 while ((test = test->traverseNextNode())) { 994 const CachedFrame* frame = hasFrame(test); 995 if (frame) { 996 if (!frame->validDocument()) 997 continue; 998 const CachedNode* node 999 = frame->nextTextField(start, framePtr, startFound); 1000 if (node) 1001 return node; 1002 } else if (test->isTextInput()) { 1003 if (test == start) 1004 *startFound = true; 1005 else if (*startFound) { 1006 if (framePtr) 1007 *framePtr = this; 1008 return test; 1009 } 1010 } 1011 } 1012 return 0; 1013 } 1014 1015 bool CachedFrame::moveInFrame(MoveInDirection moveInDirection, 1016 const CachedNode* test, BestData* bestData) const 1017 { 1018 const CachedFrame* frame = hasFrame(test); 1019 if (frame == NULL) 1020 return false; // if it's not a frame, let the caller have another swing at it 1021 const CachedNode* childDoc = frame->validDocument(); 1022 if (childDoc == NULL) 1023 return true; 1024 (frame->*moveInDirection)(childDoc, NULL, bestData); 1025 return true; 1026 } 1027 1028 const WebCore::IntRect& CachedFrame::_navBounds() const 1029 { 1030 return history()->navBounds(); 1031 } 1032 1033 SkPicture* CachedFrame::picture(const CachedNode* node) const 1034 { 1035 #if USE(ACCELERATED_COMPOSITING) 1036 if (node->isInLayer()) 1037 return layer(node)->picture(mRoot->rootLayer()); 1038 #endif 1039 return mRoot->mPicture; 1040 } 1041 1042 SkPicture* CachedFrame::picture(const CachedNode* node, int* xPtr, int* yPtr) const 1043 { 1044 #if USE(ACCELERATED_COMPOSITING) 1045 if (node->isInLayer()) { 1046 const CachedLayer* cachedLayer = layer(node); 1047 const LayerAndroid* rootLayer = mRoot->rootLayer(); 1048 cachedLayer->toLocal(rootLayer, xPtr, yPtr); 1049 return cachedLayer->picture(rootLayer); 1050 } 1051 #endif 1052 return mRoot->mPicture; 1053 } 1054 1055 void CachedFrame::resetClippedOut() 1056 { 1057 for (CachedNode* test = mCachedNodes.begin(); test != mCachedNodes.end(); test++) 1058 { 1059 if (test->clippedOut()) { 1060 test->setDisabled(false); 1061 test->setClippedOut(false); 1062 } 1063 } 1064 for (CachedFrame* frame = mCachedFrames.begin(); frame != mCachedFrames.end(); 1065 frame++) { 1066 frame->resetClippedOut(); 1067 } 1068 } 1069 1070 void CachedFrame::resetLayers() 1071 { 1072 #if USE(ACCELERATED_COMPOSITING) 1073 for (CachedFrame* frame = mCachedFrames.begin(); frame != mCachedFrames.end(); 1074 frame++) { 1075 frame->resetLayers(); 1076 } 1077 #endif 1078 } 1079 1080 bool CachedFrame::sameFrame(const CachedFrame* test) const 1081 { 1082 ASSERT(test); 1083 if (mIndexInParent != test->mIndexInParent) 1084 return false; 1085 if (mIndexInParent == -1) // index within parent's array of children, or -1 if root 1086 return true; 1087 return mParent->sameFrame(test->mParent); 1088 } 1089 1090 void CachedFrame::setData() 1091 { 1092 if (this != mRoot) { 1093 mViewBounds = mLocalViewBounds; 1094 mViewBounds.intersect(mRoot->mViewBounds); 1095 } 1096 int x, y; 1097 if (parent() == NULL) 1098 x = y = 0; 1099 else { 1100 x = mLocalViewBounds.x(); 1101 y = mLocalViewBounds.y(); 1102 } 1103 mContents.setX(x); 1104 mContents.setY(y); 1105 CachedFrame* child = mCachedFrames.begin(); 1106 while (child != mCachedFrames.end()) { 1107 child->setData(); 1108 child++; 1109 } 1110 } 1111 1112 bool CachedFrame::setCursor(WebCore::Frame* frame, WebCore::Node* node, 1113 int x, int y) 1114 { 1115 if (NULL == node) { 1116 const_cast<CachedRoot*>(mRoot)->setCursor(NULL, NULL); 1117 return true; 1118 } 1119 if (mFrame != frame) { 1120 for (CachedFrame* testF = mCachedFrames.begin(); testF != mCachedFrames.end(); 1121 testF++) { 1122 if (testF->setCursor(frame, node, x, y)) 1123 return true; 1124 } 1125 DBG_NAV_LOGD("no frame frame=%p node=%p", frame, node); 1126 return false; 1127 } 1128 bool first = true; 1129 CachedNode const * const end = mCachedNodes.end(); 1130 do { 1131 for (CachedNode* test = mCachedNodes.begin(); test != end; test++) { 1132 if (test->nodePointer() != node && first) 1133 continue; 1134 size_t partMax = test->navableRects(); 1135 for (size_t part = 0; part < partMax; part++) { 1136 WebCore::IntRect testBounds = test->ring(this, part); 1137 if (testBounds.contains(x, y) == false) 1138 continue; 1139 if (test->isCursor()) { 1140 DBG_NAV_LOGD("already set? test=%d frame=%p node=%p x=%d y=%d", 1141 test->index(), frame, node, x, y); 1142 return false; 1143 } 1144 const_cast<CachedRoot*>(mRoot)->setCursor(this, test); 1145 return true; 1146 } 1147 } 1148 DBG_NAV_LOGD("moved? frame=%p node=%p x=%d y=%d", frame, node, x, y); 1149 } while ((first ^= true) == false); 1150 failed: 1151 DBG_NAV_LOGD("no match frame=%p node=%p", frame, node); 1152 return false; 1153 } 1154 1155 const CachedNode* CachedFrame::validDocument() const 1156 { 1157 const CachedNode* doc = document(); 1158 return doc != NULL && mViewBounds.isEmpty() == false ? doc : NULL; 1159 } 1160 1161 bool CachedFrame::BestData::canBeReachedByAnotherDirection() 1162 { 1163 if (mMajorButt > -MIN_OVERLAP) 1164 return false; 1165 mMajorButt = -mMajorButt; 1166 return mNavOutside; 1167 } 1168 1169 int CachedFrame::BestData::isContainer(CachedFrame::BestData* other) 1170 { 1171 int _x = x(); 1172 int otherRight = other->right(); 1173 if (_x >= otherRight) 1174 return 0; // does not intersect 1175 int _y = y(); 1176 int otherBottom = other->bottom(); 1177 if (_y >= otherBottom) 1178 return 0; // does not intersect 1179 int _right = right(); 1180 int otherX = other->x(); 1181 if (otherX >= _right) 1182 return 0; // does not intersect 1183 int _bottom = bottom(); 1184 int otherY = other->y(); 1185 if (otherY >= _bottom) 1186 return 0; // does not intersect 1187 int intoX = otherX - _x; 1188 int intoY = otherY - _y; 1189 int intoRight = otherRight - _right; 1190 int intoBottom = otherBottom - _bottom; 1191 bool contains = intoX >= 0 && intoY >= 0 && intoRight <= 0 && intoBottom <= 0; 1192 if (contains && mNode->partRectsContains(other->mNode)) { 1193 // if (mIsArea == false && hasMouseOver()) 1194 // other->mMouseOver = mNode; 1195 return mNode->isArea() ? 1 : -1; 1196 } 1197 bool containedBy = intoX <= 0 && intoY <= 0 && intoRight >= 0 && intoBottom >= 0; 1198 if (containedBy && other->mNode->partRectsContains(mNode)) { 1199 // if (other->mIsArea == false && other->hasMouseOver()) 1200 // mMouseOver = other->mNode; 1201 return other->mNode->isArea() ? -1 : 1; 1202 } 1203 return 0; 1204 } 1205 1206 // distance scale factor factor as a 16.16 scalar 1207 SkFixed CachedFrame::BestData::Overlap(int span, int left, int right) 1208 { 1209 unsigned result; 1210 if (left > 0 && left < span && right > span) 1211 result = (unsigned) left; 1212 else if (right > 0 && right < span && left > span) 1213 result = (unsigned) right; 1214 else if (left > 0 && right > 0) 1215 return SK_Fixed1; 1216 else 1217 return 0; 1218 result = (result << 16) / (unsigned) span; // linear proportion, always less than fixed 1 1219 return (SkFixed) result; 1220 // !!! experiment with weight -- enable if overlaps are preferred too much 1221 // or reverse weighting if overlaps are preferred to little 1222 // return (SkFixed) (result * result >> 16); // but fall off with square 1223 } 1224 1225 void CachedFrame::BestData::setDistances() 1226 { 1227 mDistance = abs(mMajorDelta); 1228 int sideDistance = mWorkingDelta; 1229 if (mWorkingOverlap < SK_Fixed1) { 1230 if (mPreferred > 0) 1231 sideDistance = mWorkingDelta2; 1232 } else if (sideDistance >= 0 && mWorkingDelta2 >=- 0) 1233 sideDistance = 0; 1234 else { 1235 ASSERT(sideDistance <= 0 && mWorkingDelta2 <= 0); 1236 if (sideDistance < mWorkingDelta2) 1237 sideDistance = mWorkingDelta2; 1238 } 1239 // if overlap, smaller abs mWorkingDelta is better, smaller abs majorDelta is better 1240 // if not overlap, positive mWorkingDelta is better 1241 mSideDistance = sideDistance; 1242 } 1243 1244 bool CachedFrame::BestData::setDownDirection(const CachedHistory* history) 1245 { 1246 const WebCore::IntRect& navBounds = history->navBounds(); 1247 mMajorButt = mNodeBounds.y() - navBounds.maxY(); 1248 int testX = mNodeBounds.x(); 1249 int testRight = mNodeBounds.maxX(); 1250 setNavOverlap(navBounds.width(), navBounds.maxX() - testX, 1251 testRight - navBounds.x()); 1252 if (canBeReachedByAnotherDirection()) { 1253 mNode->setCondition(CachedNode::BEST_DIRECTION); 1254 return REJECT_TEST; 1255 } 1256 int inNavTop = mNodeBounds.y() - navBounds.y(); 1257 mMajorDelta2 = inNavTop; 1258 mMajorDelta = mMajorDelta2 + ((mNodeBounds.height() - 1259 navBounds.height()) >> 1); 1260 if (mMajorDelta2 <= 1 && mMajorDelta <= 1) { 1261 mNode->setCondition(CachedNode::CENTER_FURTHER); // never move up or sideways 1262 return REJECT_TEST; 1263 } 1264 int inNavBottom = navBounds.maxY() - mNodeBounds.maxY(); 1265 setNavInclusion(testRight - navBounds.maxX(), navBounds.x() - testX); 1266 bool subsumes = navBounds.height() > 0 && inOrSubsumesNav(); 1267 if (inNavTop <= 0 && inNavBottom <= 0 && subsumes && !mNode->wantsKeyEvents()) { 1268 mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR); 1269 return REJECT_TEST; 1270 } 1271 int maxV = history->maxWorkingVertical(); 1272 int minV = history->minWorkingVertical(); 1273 setWorkingOverlap(testRight - testX, maxV - testX, testRight - minV); 1274 setWorkingInclusion(testRight - maxV, minV - testX); 1275 if (mWorkingOverlap == 0 && mNavOverlap == 0 && inNavBottom >= 0) { 1276 mNode->setCondition(CachedNode::OVERLAP_OR_EDGE_FURTHER); 1277 return REJECT_TEST; 1278 } 1279 mInNav = history->directionChange() && inNavTop >= 0 && 1280 inNavBottom > 0 && subsumes; 1281 return false; 1282 } 1283 1284 bool CachedFrame::BestData::setLeftDirection(const CachedHistory* history) 1285 { 1286 const WebCore::IntRect& navBounds = history->navBounds(); 1287 mMajorButt = navBounds.x() - mNodeBounds.maxX(); 1288 int testY = mNodeBounds.y(); 1289 int testBottom = mNodeBounds.maxY(); 1290 setNavOverlap(navBounds.height(), navBounds.maxY() - testY, 1291 testBottom - navBounds.y()); 1292 if (canBeReachedByAnotherDirection()) { 1293 mNode->setCondition(CachedNode::BEST_DIRECTION); 1294 return REJECT_TEST; 1295 } 1296 int inNavRight = navBounds.maxX() - mNodeBounds.maxX(); 1297 mMajorDelta2 = inNavRight; 1298 mMajorDelta = mMajorDelta2 - ((navBounds.width() - 1299 mNodeBounds.width()) >> 1); 1300 if (mMajorDelta2 <= 1 && mMajorDelta <= 1) { 1301 mNode->setCondition(CachedNode::CENTER_FURTHER); // never move right or sideways 1302 return REJECT_TEST; 1303 } 1304 int inNavLeft = mNodeBounds.x() - navBounds.x(); 1305 setNavInclusion(navBounds.y() - testY, testBottom - navBounds.maxY()); 1306 bool subsumes = navBounds.width() > 0 && inOrSubsumesNav(); 1307 if (inNavLeft <= 0 && inNavRight <= 0 && subsumes && !mNode->wantsKeyEvents()) { 1308 mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR); 1309 return REJECT_TEST; 1310 } 1311 int maxH = history->maxWorkingHorizontal(); 1312 int minH = history->minWorkingHorizontal(); 1313 setWorkingOverlap(testBottom - testY, maxH - testY, testBottom - minH); 1314 setWorkingInclusion(minH - testY, testBottom - maxH); 1315 if (mWorkingOverlap == 0 && mNavOverlap == 0 && inNavLeft >= 0) { 1316 mNode->setCondition(CachedNode::OVERLAP_OR_EDGE_FURTHER); 1317 return REJECT_TEST; 1318 } 1319 mInNav = history->directionChange() && inNavLeft >= 0 && 1320 inNavRight > 0 && subsumes; /* both L/R in or out */ 1321 return false; 1322 } 1323 1324 bool CachedFrame::BestData::setRightDirection(const CachedHistory* history) 1325 { 1326 const WebCore::IntRect& navBounds = history->navBounds(); 1327 mMajorButt = mNodeBounds.x() - navBounds.maxX(); 1328 int testY = mNodeBounds.y(); 1329 int testBottom = mNodeBounds.maxY(); 1330 setNavOverlap(navBounds.height(), navBounds.maxY() - testY, 1331 testBottom - navBounds.y()); 1332 if (canBeReachedByAnotherDirection()) { 1333 mNode->setCondition(CachedNode::BEST_DIRECTION); 1334 return REJECT_TEST; 1335 } 1336 int inNavLeft = mNodeBounds.x() - navBounds.x(); 1337 mMajorDelta2 = inNavLeft; 1338 mMajorDelta = mMajorDelta2 + ((mNodeBounds.width() - 1339 navBounds.width()) >> 1); 1340 if (mMajorDelta2 <= 1 && mMajorDelta <= 1) { 1341 mNode->setCondition(CachedNode::CENTER_FURTHER); // never move left or sideways 1342 return REJECT_TEST; 1343 } 1344 int inNavRight = navBounds.maxX() - mNodeBounds.maxX(); 1345 setNavInclusion(testBottom - navBounds.maxY(), navBounds.y() - testY); 1346 bool subsumes = navBounds.width() > 0 && inOrSubsumesNav(); 1347 if (inNavLeft <= 0 && inNavRight <= 0 && subsumes && !mNode->wantsKeyEvents()) { 1348 mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR); 1349 return REJECT_TEST; 1350 } 1351 int maxH = history->maxWorkingHorizontal(); 1352 int minH = history->minWorkingHorizontal(); 1353 setWorkingOverlap(testBottom - testY, testBottom - minH, maxH - testY); 1354 setWorkingInclusion(testBottom - maxH, minH - testY); 1355 if (mWorkingOverlap == 0 && mNavOverlap == 0 && inNavRight >= 0) { 1356 mNode->setCondition(CachedNode::OVERLAP_OR_EDGE_FURTHER); 1357 return REJECT_TEST; 1358 } 1359 mInNav = history->directionChange() && inNavLeft >= 0 && 1360 inNavRight > 0 && subsumes; /* both L/R in or out */ 1361 return false; 1362 } 1363 1364 bool CachedFrame::BestData::setUpDirection(const CachedHistory* history) 1365 { 1366 const WebCore::IntRect& navBounds = history->navBounds(); 1367 mMajorButt = navBounds.y() - mNodeBounds.maxY(); 1368 int testX = mNodeBounds.x(); 1369 int testRight = mNodeBounds.maxX(); 1370 setNavOverlap(navBounds.width(), navBounds.maxX() - testX, 1371 testRight - navBounds.x()); 1372 if (canBeReachedByAnotherDirection()) { 1373 mNode->setCondition(CachedNode::BEST_DIRECTION); 1374 return REJECT_TEST; 1375 } 1376 int inNavBottom = navBounds.maxY() - mNodeBounds.maxY(); 1377 mMajorDelta2 = inNavBottom; 1378 mMajorDelta = mMajorDelta2 - ((navBounds.height() - 1379 mNodeBounds.height()) >> 1); 1380 if (mMajorDelta2 <= 1 && mMajorDelta <= 1) { 1381 mNode->setCondition(CachedNode::CENTER_FURTHER); // never move down or sideways 1382 return REJECT_TEST; 1383 } 1384 int inNavTop = mNodeBounds.y() - navBounds.y(); 1385 setNavInclusion(navBounds.x() - testX, testRight - navBounds.maxX()); 1386 bool subsumes = navBounds.height() > 0 && inOrSubsumesNav(); 1387 if (inNavTop <= 0 && inNavBottom <= 0 && subsumes && !mNode->wantsKeyEvents()) { 1388 mNode->setCondition(CachedNode::NOT_ENCLOSING_CURSOR); 1389 return REJECT_TEST; 1390 } 1391 int maxV = history->maxWorkingVertical(); 1392 int minV = history->minWorkingVertical(); 1393 setWorkingOverlap(testRight - testX, testRight - minV, maxV - testX); 1394 setWorkingInclusion(minV - testX, testRight - maxV); 1395 if (mWorkingOverlap == 0 && mNavOverlap == 0 && inNavTop >= 0) { 1396 mNode->setCondition(CachedNode::OVERLAP_OR_EDGE_FURTHER); 1397 return REJECT_TEST; 1398 } 1399 mInNav = history->directionChange() && inNavTop >= 0 && 1400 inNavBottom > 0 && subsumes; /* both L/R in or out */ 1401 return false; 1402 } 1403 1404 void CachedFrame::BestData::setNavInclusion(int left, int right) 1405 { 1406 // if left and right <= 0, test node is completely in umbra of cursor 1407 // prefer leftmost center 1408 // if left and right > 0, test node subsumes cursor 1409 mNavDelta = left; 1410 mNavDelta2 = right; 1411 } 1412 1413 void CachedFrame::BestData::setNavOverlap(int span, int left, int right) 1414 { 1415 // if left or right < 0, test node is not in umbra of cursor 1416 mNavOutside = left < MIN_OVERLAP || right < MIN_OVERLAP; 1417 mNavOverlap = Overlap(span, left, right); // prefer smallest negative left 1418 } 1419 1420 void CachedFrame::BestData::setWorkingInclusion(int left, int right) 1421 { 1422 mWorkingDelta = left; 1423 mWorkingDelta2 = right; 1424 } 1425 1426 // distance scale factor factor as a 16.16 scalar 1427 void CachedFrame::BestData::setWorkingOverlap(int span, int left, int right) 1428 { 1429 // if left or right < 0, test node is not in umbra of cursor 1430 mWorkingOutside = left < MIN_OVERLAP || right < MIN_OVERLAP; 1431 mWorkingOverlap = Overlap(span, left, right); 1432 mPreferred = left <= 0 ? 0 : left; 1433 } 1434 1435 #if DUMP_NAV_CACHE 1436 1437 #define DEBUG_PRINT_RECT(prefix, debugName, field) \ 1438 { const WebCore::IntRect& r = b->field; \ 1439 DUMP_NAV_LOGD("%s DebugTestRect TEST%s_" #debugName "={%d, %d, %d, %d}; //" #field "\n", \ 1440 prefix, mFrameName, r.x(), r.y(), r.width(), r.height()); } 1441 1442 CachedFrame* CachedFrame::Debug::base() const { 1443 CachedFrame* nav = (CachedFrame*) ((char*) this - OFFSETOF(CachedFrame, mDebug)); 1444 return nav; 1445 } 1446 1447 void CachedFrame::Debug::print() const 1448 { 1449 CachedFrame* b = base(); 1450 DEBUG_PRINT_RECT("//", CONTENTS, mContents); 1451 DEBUG_PRINT_RECT("", BOUNDS, mLocalViewBounds); 1452 DEBUG_PRINT_RECT("//", VIEW, mViewBounds); 1453 1454 DUMP_NAV_LOGD("// CachedNode mCachedNodes={ // count=%d\n", b->mCachedNodes.size()); 1455 for (CachedNode* node = b->mCachedNodes.begin(); 1456 node != b->mCachedNodes.end(); node++) { 1457 node->mDebug.print(); 1458 const CachedInput* input = b->textInput(node); 1459 if (input) 1460 input->mDebug.print(); 1461 DUMP_NAV_LOGD("\n"); 1462 } 1463 DUMP_NAV_LOGD("// }; // end of nodes\n"); 1464 #if USE(ACCELERATED_COMPOSITING) 1465 DUMP_NAV_LOGD("// CachedLayer mCachedLayers={ // count=%d\n", b->mCachedLayers.size()); 1466 for (CachedLayer* layer = b->mCachedLayers.begin(); 1467 layer != b->mCachedLayers.end(); layer++) { 1468 layer->mDebug.print(); 1469 } 1470 DUMP_NAV_LOGD("// }; // end of layers\n"); 1471 #endif // USE(ACCELERATED_COMPOSITING) 1472 DUMP_NAV_LOGD("// CachedColor mCachedColors={ // count=%d\n", b->mCachedColors.size()); 1473 for (CachedColor* color = b->mCachedColors.begin(); 1474 color != b->mCachedColors.end(); color++) { 1475 color->mDebug.print(); 1476 } 1477 DUMP_NAV_LOGD("// }; // end of colors\n"); 1478 DUMP_NAV_LOGD("// CachedFrame mCachedFrames={ // count=%d\n", b->mCachedFrames.size()); 1479 for (CachedFrame* child = b->mCachedFrames.begin(); 1480 child != b->mCachedFrames.end(); child++) 1481 { 1482 child->mDebug.print(); 1483 } 1484 DUMP_NAV_LOGD("// }; // end of child frames\n"); 1485 DUMP_NAV_LOGD("// void* mFrame=(void*) %p;\n", b->mFrame); 1486 DUMP_NAV_LOGD("// CachedFrame* mParent=%p;\n", b->mParent); 1487 DUMP_NAV_LOGD("// int mIndexInParent=%d;\n", b->mIndexInParent); 1488 DUMP_NAV_LOGD("// const CachedRoot* mRoot=%p;\n", b->mRoot); 1489 DUMP_NAV_LOGD("// int mCursorIndex=%d;\n", b->mCursorIndex); 1490 DUMP_NAV_LOGD("// int mFocusIndex=%d;\n", b->mFocusIndex); 1491 } 1492 1493 bool CachedFrame::Debug::validate(const CachedNode* node) const 1494 { 1495 const CachedFrame* b = base(); 1496 if (b->mCachedNodes.size() == 0) 1497 return false; 1498 if (node >= b->mCachedNodes.begin() && node < b->mCachedNodes.end()) 1499 return true; 1500 for (const CachedFrame* child = b->mCachedFrames.begin(); 1501 child != b->mCachedFrames.end(); child++) 1502 if (child->mDebug.validate(node)) 1503 return true; 1504 return false; 1505 } 1506 1507 #undef DEBUG_PRINT_RECT 1508 1509 #endif 1510 1511 } 1512
