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
38namespace android {
39
40WebCore::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
68bool 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
107bool 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
137bool CachedFrame::checkRings(const CachedNode* node,
138        const WebCore::IntRect& testBounds) const
139{
140    return mRoot->checkRings(picture(node), node, testBounds);
141}
142
143bool CachedFrame::checkVisited(const CachedNode* node, Direction direction) const
144{
145    return history()->checkVisited(node, direction);
146}
147
148void 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
159int 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
324const 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
338const 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
351bool CachedFrame::directionChange() const
352{
353    return history()->directionChange();
354}
355
356#ifdef BROWSER_DEBUG
357CachedNode* 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
372const 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
484const 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
498const 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
550void 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
652void 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
667const 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
707const 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
743int 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
820int 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    }
837pickTest:
838    return -1; // pick test
839}
840
841const 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
877const 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
913CachedFrame* CachedFrame::hasFrame(const CachedNode* node)
914{
915    return node->isFrame() ? &mCachedFrames[node->childFrameIndex()] : NULL;
916}
917
918void 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
927CachedHistory* CachedFrame::history() const
928{
929    return mRoot->rootHistory();
930}
931
932void 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)
947const 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
957WebCore::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
969int CachedFrame::minWorkingHorizontal() const
970{
971    return history()->minWorkingHorizontal();
972}
973
974int CachedFrame::minWorkingVertical() const
975{
976    return history()->minWorkingVertical();
977}
978
979int CachedFrame::maxWorkingHorizontal() const
980{
981    return history()->maxWorkingHorizontal();
982}
983
984int CachedFrame::maxWorkingVertical() const
985{
986    return history()->maxWorkingVertical();
987}
988
989const 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
1015bool 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
1028const WebCore::IntRect& CachedFrame::_navBounds() const
1029{
1030    return history()->navBounds();
1031}
1032
1033SkPicture* 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
1042SkPicture* 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
1055void 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
1070void 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
1080bool 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
1090void 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
1112bool 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);
1150failed:
1151    DBG_NAV_LOGD("no match frame=%p node=%p", frame, node);
1152    return false;
1153}
1154
1155const CachedNode* CachedFrame::validDocument() const
1156{
1157    const CachedNode* doc = document();
1158    return doc != NULL && mViewBounds.isEmpty() == false ? doc : NULL;
1159}
1160
1161bool CachedFrame::BestData::canBeReachedByAnotherDirection()
1162{
1163    if (mMajorButt > -MIN_OVERLAP)
1164        return false;
1165    mMajorButt = -mMajorButt;
1166    return mNavOutside;
1167}
1168
1169int 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
1207SkFixed 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
1225void 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
1244bool 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
1284bool 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
1324bool 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
1364bool 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
1404void 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
1413void 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
1420void 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
1427void 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
1442CachedFrame* CachedFrame::Debug::base() const {
1443    CachedFrame* nav = (CachedFrame*) ((char*) this - OFFSETOF(CachedFrame, mDebug));
1444    return nav;
1445}
1446
1447void 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
1493bool 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