1/*
2 * Copyright 2006, 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 "CachedNode.h"
28#include "CachedRoot.h"
29#include "Document.h"
30#include "EventListener.h"
31#include "EventNames.h"
32#include "Frame.h"
33#include "FrameLoader.h"
34#include "FrameLoaderClientAndroid.h"
35#include "FrameTree.h"
36#include "FrameView.h"
37//#include "GraphicsContext.h"
38#include "GraphicsLayerAndroid.h"
39#include "HTMLAreaElement.h"
40#include "HTMLImageElement.h"
41#include "HTMLInputElement.h"
42#include "HTMLMapElement.h"
43#include "HTMLNames.h"
44#include "HTMLOptionElement.h"
45#include "HTMLSelectElement.h"
46#include "HTMLTextAreaElement.h"
47#include "InlineTextBox.h"
48#include "KURL.h"
49#include "PluginView.h"
50#include "RegisteredEventListener.h"
51#include "RenderImage.h"
52#include "RenderInline.h"
53#include "RenderLayerBacking.h"
54#include "RenderListBox.h"
55#include "RenderSkinCombo.h"
56#include "RenderTextControl.h"
57#include "RenderWidget.h"
58#include "SkCanvas.h"
59#include "SkPoint.h"
60#include "Text.h"
61#include "WebCoreFrameBridge.h"
62#include "WebCoreViewBridge.h"
63#include "Widget.h"
64#include <wtf/unicode/Unicode.h>
65
66#ifdef DUMP_NAV_CACHE_USING_PRINTF
67    FILE* gNavCacheLogFile = NULL;
68    android::Mutex gWriteLogMutex;
69#endif
70
71#include "CacheBuilder.h"
72
73#define MINIMUM_FOCUSABLE_WIDTH 3
74#define MINIMUM_FOCUSABLE_HEIGHT 3
75#define MAXIMUM_FOCUS_RING_COUNT 32
76
77namespace android {
78
79CacheBuilder* CacheBuilder::Builder(Frame* frame) {
80    return &((FrameLoaderClientAndroid*) frame->loader()->client())->getCacheBuilder();
81}
82
83Frame* CacheBuilder::FrameAnd(CacheBuilder* cacheBuilder) {
84    FrameLoaderClientAndroid* loader = (FrameLoaderClientAndroid*)
85        ((char*) cacheBuilder - OFFSETOF(FrameLoaderClientAndroid, m_cacheBuilder));
86    return loader->getFrame();
87}
88
89Frame* CacheBuilder::FrameAnd(const CacheBuilder* cacheBuilder) {
90    FrameLoaderClientAndroid* loader = (FrameLoaderClientAndroid*)
91        ((char*) cacheBuilder - OFFSETOF(FrameLoaderClientAndroid, m_cacheBuilder));
92    return loader->getFrame();
93}
94
95
96#if DUMP_NAV_CACHE
97
98static bool hasEventListener(Node* node, const AtomicString& eventType) {
99    if (!node->isElementNode())
100        return false;
101    Element* element = static_cast<Element*>(node);
102    EventListener* listener = element->getAttributeEventListener(eventType);
103    return 0 != listener;
104}
105
106#define DEBUG_BUFFER_SIZE 256
107#define DEBUG_WRAP_SIZE 150
108#define DEBUG_WRAP_MAX 170
109
110Frame* CacheBuilder::Debug::frameAnd() const {
111    CacheBuilder* nav = (CacheBuilder*) ((char*) this - OFFSETOF(CacheBuilder, mDebug));
112    return CacheBuilder::FrameAnd(nav);
113}
114
115void CacheBuilder::Debug::attr(const AtomicString& name, const AtomicString& value) {
116    if (name.isNull() || name.isEmpty() || value.isNull() || value.isEmpty())
117        return;
118    uChar(name.characters(), name.length(), false);
119    print("=");
120    wideString(value.characters(), value.length(), false);
121    print(" ");
122}
123
124void CacheBuilder::Debug::comma(const char* str) {
125    print(str);
126    print(", ");
127}
128
129void CacheBuilder::Debug::flush() {
130    int len;
131    do {
132        int limit = mIndex;
133        if (limit < DEBUG_WRAP_SIZE)
134            return;
135        if (limit < DEBUG_WRAP_MAX)
136            len = limit;
137        else {
138            limit = DEBUG_WRAP_MAX;
139            len = DEBUG_WRAP_SIZE;
140            while (len < limit) {
141                char test = mBuffer[len];
142                if (test < '/' || (test > '9' && test < 'A') || (test > 'Z' && test  < 'a') || test > 'z')
143                    break;
144                len++;
145            }
146            while (len > 0 && mBuffer[len - 1] == '\\')
147                len--;
148            while (mBuffer[len] == '"')
149                len++;
150        }
151        const char* prefix = mPrefix;
152        if (prefix[0] == '\"') {
153            // see if we're inside a quote
154            int quoteCount = 0;
155            for (int index = 0; index < len; index++) {
156                if (mBuffer[index] == '\\') {
157                    index++;
158                    continue;
159                }
160                if (mBuffer[index] == '\n') {
161                    quoteCount = 0;
162                    continue;
163                }
164                if (mBuffer[index] == '"')
165                    quoteCount++;
166            }
167            if ((quoteCount & 1) == 0)
168                prefix = "\n";
169        }
170        DUMP_NAV_LOGD("%.*s", len, mBuffer);
171        int copy = mIndex - len;
172        strcpy(mBuffer, prefix);
173        memcpy(&mBuffer[strlen(prefix)], &mBuffer[len], copy);
174        mIndex = strlen(prefix) + copy;
175    } while (true);
176}
177
178void CacheBuilder::Debug::frameName(char*& namePtr, const char* max) const {
179   if (namePtr >= max)
180        return;
181   Frame* frame = frameAnd();
182   Frame* parent = frame->tree()->parent();
183   if (parent)
184        Builder(parent)->mDebug.frameName(namePtr, max);
185    const AtomicString& name = frame->tree()->name();
186    if (name.length() == 0)
187        return;
188    unsigned index = 0;
189    if (name.startsWith(AtomicString("opener")))
190        index = 6;
191    for (; index < name.length(); index++) {
192        char ch = name[index];
193        if (ch <= ' ')
194            ch = '_';
195        if (WTF::isASCIIAlphanumeric(ch) || ch == '_')
196            *namePtr++  = ch;
197    }
198}
199
200void CacheBuilder::Debug::frames() {
201    Frame* frame = frameAnd();
202    Document* doc = frame->document();
203    if (doc == NULL)
204        return;
205    bool top = frame->tree()->parent() == NULL;
206    if (top) {
207#ifdef DUMP_NAV_CACHE_USING_PRINTF
208        gWriteLogMutex.lock();
209        ASSERT(gNavCacheLogFile == NULL);
210        gNavCacheLogFile = fopen(NAV_CACHE_LOG_FILE, "a");
211#endif
212        groups();
213    }
214    Frame* child = frame->tree()->firstChild();
215    bool hasChild = child != NULL;
216    if (top && hasChild)
217        DUMP_NAV_LOGD("\nnamespace TEST_SPACE {\n\n");
218    while (child) {
219        Builder(child)->mDebug.frames();
220        child = child->tree()->nextSibling();
221    }
222    if (hasChild) {
223        child = frame->tree()->firstChild();
224        while (child) {
225            char childName[256];
226            char* childNamePtr = childName;
227            Builder(child)->mDebug.frameName(childNamePtr, childNamePtr + sizeof(childName) - 1);
228            *childNamePtr = '\0';
229            if (child == frame->tree()->firstChild())
230                DUMP_NAV_LOGD("DebugTestFrameGroup TEST%s_GROUP[] = {\n", childName);
231            Frame* next = child->tree()->nextSibling();
232            Document* doc = child->document();
233            if (doc != NULL) {
234                RenderObject* renderer = doc->renderer();
235                if (renderer != NULL) {
236                    RenderLayer* layer = renderer->enclosingLayer();
237                    if (layer != NULL) {
238                        DUMP_NAV_LOGD("{ ");
239                        DUMP_NAV_LOGD("TEST%s_RECTS, ", childName);
240                        DUMP_NAV_LOGD("TEST%s_RECT_COUNT, ", childName);
241                        DUMP_NAV_LOGD("TEST%s_RECTPARTS, ", childName);
242                        DUMP_NAV_LOGD("TEST%s_BOUNDS,\n", childName);
243                        DUMP_NAV_LOGD("TEST%s_WIDTH, ", childName);
244                        DUMP_NAV_LOGD("TEST%s_HEIGHT,\n", childName);
245                        DUMP_NAV_LOGD("0, 0, 0, 0,\n");
246                        DUMP_NAV_LOGD("TEST%s_FOCUS, ", childName);
247                        Frame* grandChild = child->tree()->firstChild();
248                         if (grandChild) {
249                            char grandChildName[256];
250                            char* grandChildNamePtr = grandChildName;
251                            Builder(grandChild)->mDebug.frameName(grandChildNamePtr,
252                                grandChildNamePtr + sizeof(grandChildName) - 1);
253                            *grandChildNamePtr = '\0';
254                            DUMP_NAV_LOGD("TEST%s_GROUP, ", grandChildName);
255                            DUMP_NAV_LOGD("sizeof(TEST%s_GROUP) / sizeof(DebugTestFrameGroup), ", grandChildName);
256                        } else
257                            DUMP_NAV_LOGD("NULL, 0, ");
258                        DUMP_NAV_LOGD("\"%s\"\n", childName);
259                        DUMP_NAV_LOGD("}%c\n", next ? ',' : ' ');
260                    }
261                }
262            }
263            child = next;
264        }
265        DUMP_NAV_LOGD("};\n");
266    }
267    if (top) {
268        if (hasChild)
269            DUMP_NAV_LOGD("\n}  // end of namespace\n\n");
270        char name[256];
271        char* frameNamePtr = name;
272        frameName(frameNamePtr, frameNamePtr + sizeof(name) - 1);
273        *frameNamePtr = '\0';
274        DUMP_NAV_LOGD("DebugTestFrameGroup TEST%s_GROUP = {\n", name);
275        DUMP_NAV_LOGD("TEST%s_RECTS, ", name);
276        DUMP_NAV_LOGD("TEST%s_RECT_COUNT, ", name);
277        DUMP_NAV_LOGD("TEST%s_RECTPARTS, ", name);
278        DUMP_NAV_LOGD("TEST%s_BOUNDS,\n", name);
279        DUMP_NAV_LOGD("TEST%s_WIDTH, ", name);
280        DUMP_NAV_LOGD("TEST%s_HEIGHT,\n", name);
281        DUMP_NAV_LOGD("TEST%s_MAX_H, ", name);
282        DUMP_NAV_LOGD("TEST%s_MIN_H, ", name);
283        DUMP_NAV_LOGD("TEST%s_MAX_V, ", name);
284        DUMP_NAV_LOGD("TEST%s_MIN_V,\n", name);
285        DUMP_NAV_LOGD("TEST%s_FOCUS, ", name);
286        if (hasChild) {
287            child = frame->tree()->firstChild();
288            char childName[256];
289            char* childNamePtr = childName;
290            Builder(child)->mDebug.frameName(childNamePtr, childNamePtr + sizeof(childName) - 1);
291            *childNamePtr = '\0';
292            DUMP_NAV_LOGD("TEST_SPACE::TEST%s_GROUP, ", childName);
293            DUMP_NAV_LOGD("sizeof(TEST_SPACE::TEST%s_GROUP) / sizeof(DebugTestFrameGroup), \n" ,childName);
294        } else
295            DUMP_NAV_LOGD("NULL, 0, ");
296        DUMP_NAV_LOGD("\"%s\"\n", name);
297        DUMP_NAV_LOGD("};\n");
298#ifdef DUMP_NAV_CACHE_USING_PRINTF
299        if (gNavCacheLogFile)
300            fclose(gNavCacheLogFile);
301        gNavCacheLogFile = NULL;
302        gWriteLogMutex.unlock();
303#endif
304    }
305}
306
307void CacheBuilder::Debug::init(char* buffer, size_t size) {
308    mBuffer = buffer;
309    mBufferSize = size;
310    mIndex = 0;
311    mPrefix = "";
312}
313
314void CacheBuilder::Debug::groups() {
315    Frame* frame = frameAnd();
316    Frame* child = frame->tree()->firstChild();
317    bool hasChild = child != NULL;
318    if (frame->tree()->parent() == NULL && hasChild)
319        DUMP_NAV_LOGD("namespace TEST_SPACE {\n\n");
320    while (child) {
321        Builder(child)->mDebug.groups();
322        child = child->tree()->nextSibling();
323    }
324    if (frame->tree()->parent() == NULL && hasChild)
325        DUMP_NAV_LOGD("\n} // end of namespace\n\n");
326    Document* doc = frame->document();
327    char name[256];
328    char* frameNamePtr = name;
329    frameName(frameNamePtr, frameNamePtr + sizeof(name) - 1);
330    *frameNamePtr = '\0';
331    if (doc == NULL) {
332        DUMP_NAV_LOGD("// %s has no document\n", name);
333        return;
334    }
335    RenderObject* renderer = doc->renderer();
336    if (renderer == NULL) {
337        DUMP_NAV_LOGD("// %s has no renderer\n", name);
338        return;
339    }
340    RenderLayer* layer = renderer->enclosingLayer();
341    if (layer == NULL) {
342        DUMP_NAV_LOGD("// %s has no enclosingLayer\n", name);
343        return;
344    }
345    Node* node = doc;
346    Node* focus = doc->focusedNode();
347    bool atLeastOne = false;
348    do {
349        if ((atLeastOne |= isFocusable(node)) != false)
350            break;
351    } while ((node = node->traverseNextNode()) != NULL);
352    int focusIndex = -1;
353    if (atLeastOne == false) {
354        DUMP_NAV_LOGD("static DebugTestNode TEST%s_RECTS[] = {\n"
355            "{{0, 0, 0, 0}, \"\", 0, -1, \"\", {0, 0, 0, 0}, false, 0}\n"
356            "};\n\n", name);
357        DUMP_NAV_LOGD("static int TEST%s_RECT_COUNT = 1;"
358            " // no focusable nodes\n", name);
359        DUMP_NAV_LOGD("#define TEST%s_RECTPARTS NULL\n", name);
360    } else {
361        node = doc;
362        int count = 1;
363        DUMP_NAV_LOGD("static DebugTestNode TEST%s_RECTS[] = {\n", name);
364        do {
365            String properties;
366            if (hasEventListener(node, eventNames().clickEvent))
367                properties.append("ONCLICK | ");
368            if (hasEventListener(node, eventNames().mousedownEvent))
369                properties.append("MOUSEDOWN | ");
370            if (hasEventListener(node, eventNames().mouseupEvent))
371                properties.append("MOUSEUP | ");
372            if (hasEventListener(node, eventNames().mouseoverEvent))
373                properties.append("MOUSEOVER | ");
374            if (hasEventListener(node, eventNames().mouseoutEvent))
375                properties.append("MOUSEOUT | ");
376            if (hasEventListener(node, eventNames().keydownEvent))
377                properties.append("KEYDOWN | ");
378            if (hasEventListener(node, eventNames().keyupEvent))
379                properties.append("KEYUP | ");
380            if (CacheBuilder::HasFrame(node))
381                properties.append("FRAME | ");
382            if (focus == node) {
383                properties.append("FOCUS | ");
384                focusIndex = count;
385            }
386            if (node->isKeyboardFocusable(NULL))
387                properties.append("KEYBOARD_FOCUSABLE | ");
388            if (node->isMouseFocusable())
389                properties.append("MOUSE_FOCUSABLE | ");
390            if (node->isFocusable())
391                properties.append("SIMPLE_FOCUSABLE | ");
392            if (properties.isEmpty())
393                properties.append("0");
394            else
395                properties.truncate(properties.length() - 3);
396            IntRect rect = node->getRect();
397            if (node->hasTagName(HTMLNames::areaTag))
398                rect = getAreaRect(static_cast<HTMLAreaElement*>(node));
399            char buffer[DEBUG_BUFFER_SIZE];
400            memset(buffer, 0, sizeof(buffer));
401            mBuffer = buffer;
402            mBufferSize = sizeof(buffer);
403            mPrefix = "\"\n\"";
404            mIndex = snprintf(buffer, sizeof(buffer), "{{%d, %d, %d, %d}, ", rect.x(), rect.y(),
405                rect.width(), rect.height());
406            localName(node);
407            uChar(properties.characters(), properties.length(), false);
408            print(", ");
409            int parentIndex = ParentIndex(node, count, node->parentNode());
410            char scratch[256];
411            snprintf(scratch, sizeof(scratch), "%d", parentIndex);
412            comma(scratch);
413            Element* element = static_cast<Element*>(node);
414            if (node->isElementNode() && element->hasID())
415                wideString(element->getIDAttribute());
416            else if (node->isTextNode()) {
417 #if 01 // set to one to abbreviate text that can be omitted from the address detection code
418               if (rect.isEmpty() && node->textContent().length() > 100) {
419                    wideString(node->textContent().characters(), 100, false);
420                    snprintf(scratch, sizeof(scratch), "/* + %d bytes */",
421                        node->textContent().length() - 100);
422                    print(scratch);
423                } else
424 #endif
425                   wideString(node->textContent().characters(), node->textContent().length(), true);
426            } else if (node->hasTagName(HTMLNames::aTag) ||
427                node->hasTagName(HTMLNames::areaTag))
428            {
429                HTMLAnchorElement* anchor = static_cast<HTMLAnchorElement*>(node);
430                wideString(anchor->href());
431            } else if (node->hasTagName(HTMLNames::imgTag)) {
432                HTMLImageElement* image = static_cast<HTMLImageElement*>(node);
433                wideString(image->src());
434            } else
435                print("\"\"");
436            RenderObject* renderer = node->renderer();
437            int tabindex = node->isElementNode() ? node->tabIndex() : 0;
438            RenderLayer* layer = 0;
439            if (renderer) {
440                const IntRect& absB = renderer->absoluteBoundingBoxRect();
441                bool hasLayer = renderer->hasLayer();
442                layer = hasLayer ? toRenderBoxModelObject(renderer)->layer() : 0;
443                snprintf(scratch, sizeof(scratch), ", {%d, %d, %d, %d}, %s"
444                    ", %d, %s, %s},",
445                    absB.x(), absB.y(), absB.width(), absB.height(),
446                    renderer->hasOverflowClip() ? "true" : "false", tabindex,
447                    hasLayer ? "true" : "false",
448                    hasLayer && layer->isComposited() ? "true" : "false");
449                // TODO: add renderer->style()->visibility()
450                print(scratch);
451            } else
452                print(", {0, 0, 0, 0}, false, 0},");
453
454            flush();
455            snprintf(scratch, sizeof(scratch), "// %d: ", count);
456            mPrefix = "\n// ";
457            print(scratch);
458            //print(renderer ? renderer->information().ascii() : "NO_RENDER_INFO");
459            if (node->isElementNode()) {
460                Element* element = static_cast<Element*>(node);
461                NamedNodeMap* attrs = element->attributes();
462                unsigned length = attrs->length();
463                if (length > 0) {
464                    newLine();
465                    print("// attr: ");
466                    for (unsigned i = 0; i < length; i++) {
467                        Attribute* a = attrs->attributeItem(i);
468                        attr(a->localName(), a->value());
469                    }
470                }
471            }
472            count++;
473            newLine();
474#if USE(ACCELERATED_COMPOSITING)
475            if (renderer && layer) {
476                RenderLayerBacking* back = layer->backing();
477                GraphicsLayerAndroid* grLayer = static_cast
478                    <GraphicsLayerAndroid*>(back ? back->graphicsLayer() : 0);
479                LayerAndroid* aLayer = grLayer ? grLayer->contentLayer() : 0;
480                const SkPicture* pict = aLayer ? aLayer->picture() : 0;
481                snprintf(scratch, sizeof(scratch), "// layer:%p back:%p"
482                    " gLayer:%p aLayer:%p pict:%p", layer, back, grLayer,
483                    aLayer, pict);
484                print(scratch);
485                newLine();
486           }
487#endif
488        } while ((node = node->traverseNextNode()) != NULL);
489        DUMP_NAV_LOGD("}; // focusables = %d\n", count - 1);
490        DUMP_NAV_LOGD("\n");
491        DUMP_NAV_LOGD("static int TEST%s_RECT_COUNT = %d;\n\n", name, count - 1);
492        // look for rects with multiple parts
493        node = doc;
494        count = 1;
495        bool hasRectParts = false;
496        int globalOffsetX, globalOffsetY;
497        GetGlobalOffset(frame, &globalOffsetX, &globalOffsetY);
498        do {
499            IntRect rect;
500            bool _isFocusable = isFocusable(node) || (node->isTextNode()
501              && node->getRect().isEmpty() == false
502                );
503            int nodeIndex = count++;
504            if (_isFocusable == false)
505                continue;
506            RenderObject* renderer = node->renderer();
507            if (renderer == NULL)
508                continue;
509            WTF::Vector<IntRect> rects;
510            IntRect clipBounds = IntRect(0, 0, INT_MAX, INT_MAX);
511            IntRect focusBounds = IntRect(0, 0, INT_MAX, INT_MAX);
512            IntRect* rectPtr = &focusBounds;
513            if (node->isTextNode()) {
514                Text* textNode = (Text*) node;
515                if (CacheBuilder::ConstructTextRects(textNode, 0, textNode,
516                        INT_MAX, globalOffsetX, globalOffsetY, rectPtr,
517                        clipBounds, &rects) == false)
518                    continue;
519            } else {
520                IntRect nodeBounds = node->getRect();
521                if (CacheBuilder::ConstructPartRects(node, nodeBounds, rectPtr,
522                        globalOffsetX, globalOffsetY, &rects) == false)
523                    continue;
524            }
525            unsigned arraySize = rects.size();
526            if (arraySize > 1 || (arraySize == 1 && (rectPtr->width() != rect.width())) ||
527                    rectPtr->height() != rect.height()) {
528                if (hasRectParts == false) {
529                    DUMP_NAV_LOGD("static DebugTestRectPart TEST%s_RECTPARTS[] = {\n", name);
530                    hasRectParts = true;
531                }
532                if (node->isTextNode() == false) {
533                    unsigned rectIndex = 0;
534                    for (; rectIndex < arraySize; rectIndex++) {
535                        rectPtr = &rects.at(rectIndex);
536                        DUMP_NAV_LOGD("{ %d, %d, %d, %d, %d }, // %d\n", nodeIndex,
537                            rectPtr->x(), rectPtr->y(), rectPtr->width(),
538                            rectPtr->height(), rectIndex + 1);
539                    }
540                } else {
541                    RenderText* renderText = (RenderText*) node->renderer();
542                    InlineTextBox* textBox = renderText->firstTextBox();
543                    unsigned rectIndex = 0;
544                    while (textBox) {
545                        FloatPoint pt = renderText->localToAbsolute();
546                        IntRect rect = textBox->selectionRect((int) pt.x(), (int) pt.y(), 0, INT_MAX);
547                        mIndex = 0;
548                        mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, "{ %d, %d, %d, %d, %d",
549                            nodeIndex, rect.x(), rect.y(), rect.width(), rect.height());
550                        mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d, %d, %d",
551                            textBox->len(), 0 /*textBox->selectionHeight()*/,
552                            0 /*textBox->selectionTop()*/);
553                        mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d, %d, %d",
554                            0 /*textBox->spaceAdd()*/, textBox->start(), 0 /*textBox->textPos()*/);
555                        mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d, %d, %d, %d",
556                            textBox->x(), textBox->y(), textBox->width(), textBox->height());
557                        int baseline = textBox->renderer()->style(textBox->isFirstLineStyle())->font().ascent();
558                        mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d }, // %d ",
559                            baseline, ++rectIndex);
560                        wideString(node->textContent().characters() + textBox->start(), textBox->len(), true);
561                        DUMP_NAV_LOGD("%.*s\n", mIndex, mBuffer);
562                        textBox = textBox->nextTextBox();
563                    }
564                }
565            }
566        } while ((node = node->traverseNextNode()) != NULL);
567        if (hasRectParts)
568            DUMP_NAV_LOGD("{0}\n};\n\n");
569        else
570            DUMP_NAV_LOGD("static DebugTestRectPart* TEST%s_RECTPARTS = NULL;\n", name);
571    }
572    int contentsWidth = layer->width();
573    int contentsHeight = layer->height();
574    DUMP_NAV_LOGD("static int TEST%s_FOCUS = %d;\n", name, focusIndex);
575    DUMP_NAV_LOGD("static int TEST%s_WIDTH = %d;\n", name, contentsWidth);
576    DUMP_NAV_LOGD("static int TEST%s_HEIGHT = %d;\n\n", name, contentsHeight);
577}
578
579bool CacheBuilder::Debug::isFocusable(Node* node) {
580    if (node->hasTagName(HTMLNames::areaTag))
581        return true;
582    if (node->renderer() == false)
583        return false;
584    if (node->isKeyboardFocusable(NULL))
585        return true;
586    if (node->isMouseFocusable())
587        return true;
588    if (node->isFocusable())
589        return true;
590    if (CacheBuilder::AnyIsClick(node))
591        return false;
592    if (CacheBuilder::HasTriggerEvent(node))
593        return true;
594    return false;
595}
596
597void CacheBuilder::Debug::localName(Node* node) {
598    const AtomicString& local = node->localName();
599    if (node->isTextNode())
600        print("\"#text\"");
601    else
602        wideString(local.characters(), local.length(), false);
603    print(", ");
604}
605
606void CacheBuilder::Debug::newLine(int indent) {
607    if (mPrefix[0] != '\n')
608        print(&mPrefix[0], 1);
609    flush();
610    int lastnewline = mIndex - 1;
611    while (lastnewline >= 0 && mBuffer[lastnewline] != '\n')
612        lastnewline--;
613    lastnewline++;
614    char* buffer = mBuffer;
615    if (lastnewline > 0) {
616        DUMP_NAV_LOGD("%.*s", lastnewline, buffer);
617        mIndex -= lastnewline;
618        buffer += lastnewline;
619    }
620    size_t prefixLen = strlen(mPrefix);
621    int minPrefix = prefixLen - 1;
622    while (minPrefix >= 0 && mPrefix[minPrefix] != '\n')
623        minPrefix--;
624    minPrefix = prefixLen - minPrefix - 1;
625    if (mIndex > minPrefix)
626        DUMP_NAV_LOGD("%.*s\n", mIndex, buffer);
627    mIndex = 0;
628    setIndent(indent);
629}
630
631int CacheBuilder::Debug::ParentIndex(Node* node, int count, Node* parent)
632{
633    if (parent == NULL)
634        return -1;
635    ASSERT(node != parent);
636    int result = count;
637    Node* previous = node;
638    do {
639        result--;
640        previous = previous->traversePreviousNode();
641    } while (previous && previous != parent);
642    if (previous != NULL)
643        return result;
644    result = count;
645    do {
646        result++;
647    } while ((node = node->traverseNextNode()) != NULL && node != parent);
648    if (node != NULL)
649        return result;
650    ASSERT(0);
651    return -1;
652}
653
654void CacheBuilder::Debug::print(const char* name) {
655    print(name, strlen(name));
656}
657
658void CacheBuilder::Debug::print(const char* name, unsigned len) {
659    do {
660        if (mIndex + len >= DEBUG_BUFFER_SIZE)
661            flush();
662        int copyLen = mIndex + len < DEBUG_BUFFER_SIZE ?
663             len : DEBUG_BUFFER_SIZE - mIndex;
664        memcpy(&mBuffer[mIndex], name, copyLen);
665        mIndex += copyLen;
666        name += copyLen;
667        len -= copyLen;
668    } while (len > 0);
669    mBuffer[mIndex] = '\0';
670}
671
672void CacheBuilder::Debug::setIndent(int indent)
673{
674    char scratch[64];
675    snprintf(scratch, sizeof(scratch), "%.*s", indent,
676        "                                                                    ");
677    print(scratch);
678}
679
680void CacheBuilder::Debug::uChar(const UChar* name, unsigned len, bool hex) {
681    const UChar* end = name + len;
682    bool wroteHex = false;
683    while (name < end) {
684        unsigned ch = *name++;
685        if (ch == '\t' || ch == '\n' || ch == '\r' || ch == 0xa0)
686            ch = ' ';
687        if (ch < ' ' || ch == 0x7f) {
688            if (hex) {
689                mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, "\\x%02x", ch);
690                wroteHex = true;
691            } else
692                mBuffer[mIndex++] = '?';
693        } else if (ch >= 0x80) {
694            if (hex) {
695                if (ch < 0x800)
696                    mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex,
697                        "\\x%02x\\x%02x", ch >> 6 | 0xc0, (ch & 0x3f) | 0x80);
698                else
699                    mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex,
700                        "\\x%02x\\x%02x\\x%02x", ch >> 12 | 0xe0,
701                        (ch >> 6 & 0x3f) | 0x80, (ch & 0x3f) | 0x80);
702                wroteHex = true;
703            } else
704                mBuffer[mIndex++] = '?';
705        } else {
706            if (wroteHex && WTF::isASCIIHexDigit((UChar) ch))
707                mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex,
708                    "\" \"");
709            else if (ch == '"' || ch == '\\')
710                mBuffer[mIndex++] = '\\';
711            mBuffer[mIndex++] = ch;
712            wroteHex = false;
713        }
714        if (mIndex + 1 >= DEBUG_BUFFER_SIZE)
715            flush();
716    }
717    flush();
718}
719
720void CacheBuilder::Debug::validateFrame() {
721    Frame* frame = frameAnd();
722    Page* page = frame->page();
723    ASSERT(page);
724    ASSERT((int) page > 0x10000);
725    Frame* child = frame->tree()->firstChild();
726    while (child) {
727        Builder(child)->mDebug.validateFrame();
728        child = child->tree()->nextSibling();
729    }
730}
731
732void CacheBuilder::Debug::wideString(const UChar* chars, int length, bool hex) {
733    if (length == 0)
734        print("\"\"");
735    else {
736        print("\"");
737        uChar(chars, length, hex);
738        print("\"");
739    }
740}
741
742void CacheBuilder::Debug::wideString(const String& str) {
743    wideString(str.characters(), str.length(), false);
744}
745
746#endif // DUMP_NAV_CACHE
747
748CacheBuilder::CacheBuilder()
749{
750    mAllowableTypes = ALL_CACHEDNODE_BITS;
751#ifdef DUMP_NAV_CACHE_USING_PRINTF
752    gNavCacheLogFile = NULL;
753#endif
754}
755
756void CacheBuilder::adjustForColumns(const ClipColumnTracker& track,
757    CachedNode* node, IntRect* bounds)
758{
759    int x = 0;
760    int y = 0;
761    int tx = track.mBounds.x();
762    int ty = track.mBounds.y();
763    int columnGap = track.mColumnGap;
764    size_t limit = track.mColumns->size();
765    for (size_t index = 0; index < limit; index++) {
766        IntRect column = track.mColumns->at(index);
767        column.move(tx, ty);
768        IntRect test = *bounds;
769        test.move(x, y);
770        if (column.contains(test)) {
771            if ((x | y) == 0)
772                return;
773            *bounds = test;
774            node->move(x, y);
775            return;
776        }
777        int xOffset = column.width() + columnGap;
778        x += track.mDirection == LTR ? xOffset : -xOffset;
779        y -= column.height();
780    }
781}
782
783// Checks if a node has one of event listener types.
784bool CacheBuilder::NodeHasEventListeners(Node* node, AtomicString* eventTypes, int length) {
785    for (int i = 0; i < length; ++i) {
786        if (!node->getEventListeners(eventTypes[i]).isEmpty())
787            return true;
788    }
789    return false;
790}
791
792bool CacheBuilder::AnyChildIsClick(Node* node)
793{
794    AtomicString eventTypes[5] = {
795        eventNames().clickEvent,
796        eventNames().mousedownEvent,
797        eventNames().mouseupEvent,
798        eventNames().keydownEvent,
799        eventNames().keyupEvent
800    };
801
802    Node* child = node->firstChild();
803    while (child != NULL) {
804        if (child->isFocusable() ||
805            NodeHasEventListeners(child, eventTypes, 5))
806                return true;
807        if (AnyChildIsClick(child))
808            return true;
809        child = child->nextSibling();
810    }
811    return false;
812}
813
814bool CacheBuilder::AnyIsClick(Node* node)
815{
816    if (node->hasTagName(HTMLNames::bodyTag))
817        return AnyChildIsClick(node);
818
819    AtomicString eventTypeSetOne[4] = {
820        eventNames().mouseoverEvent,
821        eventNames().mouseoutEvent,
822        eventNames().keydownEvent,
823        eventNames().keyupEvent
824    };
825
826    if (!NodeHasEventListeners(node, eventTypeSetOne, 4))
827        return false;
828
829    AtomicString eventTypeSetTwo[3] = {
830        eventNames().clickEvent,
831        eventNames().mousedownEvent,
832        eventNames().mouseupEvent
833    };
834
835    if (NodeHasEventListeners(node, eventTypeSetTwo, 3))
836        return false;
837
838    return AnyChildIsClick(node);
839}
840
841void CacheBuilder::buildCache(CachedRoot* root)
842{
843    Frame* frame = FrameAnd(this);
844    BuildFrame(frame, frame, root, (CachedFrame*) root);
845    root->finishInit(); // set up frame parent pointers, child pointers
846    setData((CachedFrame*) root);
847}
848
849static Node* ParentWithChildren(Node* node)
850{
851    Node* parent = node;
852    while ((parent = parent->parentNode())) {
853        if (parent->childNodeCount() > 1)
854            return parent;
855    }
856    return 0;
857}
858
859// FIXME
860// Probably this should check for null instead of the caller. If the
861// Tracker object is the last thing in the dom, checking for null in the
862// caller in some cases fails to set up Tracker state which may be useful
863// to the nodes parsed immediately after the tracked noe.
864static Node* OneAfter(Node* node)
865{
866    Node* parent = node;
867    Node* sibling = NULL;
868    while ((parent = parent->parentNode()) != NULL) {
869        sibling = parent->nextSibling();
870        if (sibling != NULL)
871            break;
872    }
873    return sibling;
874}
875
876// return true if this renderer is really a pluinview, and it wants
877// key-events (i.e. focus)
878static bool checkForPluginViewThatWantsFocus(RenderObject* renderer) {
879    if (renderer->isWidget()) {
880        Widget* widget = static_cast<RenderWidget*>(renderer)->widget();
881        if (widget && (widget->isPluginView() || widget->isPluginWidget())) {
882            // check if this plugin really wants key events (TODO)
883            return true;
884        }
885    }
886    return false;
887}
888
889#if USE(ACCELERATED_COMPOSITING)
890static void AddLayer(CachedFrame* frame, size_t index, const IntPoint& location,
891    int id)
892{
893    DBG_NAV_LOGD("frame=%p index=%d loc=(%d,%d) id=%d", frame, index,
894        location.x(), location.y(), id);
895    CachedLayer cachedLayer;
896    cachedLayer.reset();
897    cachedLayer.setCachedNodeIndex(index);
898    cachedLayer.setOffset(location);
899    cachedLayer.setUniqueId(id);
900    frame->add(cachedLayer);
901}
902#endif
903
904// when new focus is found, push it's parent on a stack
905    // as long as more focii are found with the same (grand) parent, note it
906    // (which only requires retrieving the last parent on the stack)
907// when the parent's last child is found, pop the stack
908// different from Tracker in that Tracker only pushes focii with children
909
910// making this work with focus - child focus - grandchild focus is tricky
911// if I keep the generation number, I may be able to more quickly determine that
912// a node is a grandchild of the focus's parent
913// this additionally requires being able to find the grandchild's parent
914
915// keep nodes that are focusable
916void CacheBuilder::BuildFrame(Frame* root, Frame* frame,
917    CachedRoot* cachedRoot, CachedFrame* cachedFrame)
918{
919    WTF::Vector<FocusTracker> tracker(1); // sentinel
920    {
921        FocusTracker* baseTracker = tracker.data();
922        bzero(baseTracker, sizeof(FocusTracker));
923        baseTracker->mCachedNodeIndex = -1;
924    }
925    WTF::Vector<LayerTracker> layerTracker(1); // sentinel
926    bzero(layerTracker.data(), sizeof(LayerTracker));
927    WTF::Vector<ClipColumnTracker> clipTracker(1); // sentinel
928    bzero(clipTracker.data(), sizeof(ClipColumnTracker));
929    WTF::Vector<TabIndexTracker> tabIndexTracker(1); // sentinel
930    bzero(tabIndexTracker.data(), sizeof(TabIndexTracker));
931#if DUMP_NAV_CACHE
932    char* frameNamePtr = cachedFrame->mDebug.mFrameName;
933    Builder(frame)->mDebug.frameName(frameNamePtr, frameNamePtr +
934        sizeof(cachedFrame->mDebug.mFrameName) - 1);
935    *frameNamePtr = '\0';
936    int nodeIndex = 1;
937#endif
938    NodeWalk walk;
939    Document* doc = frame->document();
940    Node* parent = doc;
941    CachedNode cachedParentNode;
942    cachedParentNode.init(parent);
943#if DUMP_NAV_CACHE
944    cachedParentNode.mDebug.mNodeIndex = nodeIndex;
945#endif
946    cachedFrame->add(cachedParentNode);
947    Node* node = parent;
948    int cacheIndex = 1;
949    int textInputIndex = 0;
950    Node* focused = doc->focusedNode();
951    if (focused)
952        cachedRoot->setFocusBounds(focused->getRect());
953    int globalOffsetX, globalOffsetY;
954    GetGlobalOffset(frame, &globalOffsetX, &globalOffsetY);
955    IntPoint bodyPos = IntPoint(0, 0);
956    while (walk.mMore || (node = node->traverseNextNode()) != NULL) {
957#if DUMP_NAV_CACHE
958        nodeIndex++;
959#endif
960        FocusTracker* last = &tracker.last();
961        int lastChildIndex = cachedFrame->size() - 1;
962        while (node == last->mLastChild) {
963            if (CleanUpContainedNodes(cachedRoot, cachedFrame, last, lastChildIndex))
964                cacheIndex--;
965            tracker.removeLast();
966            lastChildIndex = last->mCachedNodeIndex;
967            last = &tracker.last();
968        }
969        do {
970            const ClipColumnTracker* lastClip = &clipTracker.last();
971            if (node != lastClip->mLastChild)
972                break;
973            clipTracker.removeLast();
974        } while (true);
975        do {
976            const LayerTracker* lastLayer = &layerTracker.last();
977            if (node != lastLayer->mLastChild)
978                break;
979            layerTracker.removeLast();
980        } while (true);
981        do {
982            const TabIndexTracker* lastTabIndex = &tabIndexTracker.last();
983            if (node != lastTabIndex->mLastChild)
984                break;
985            tabIndexTracker.removeLast();
986        } while (true);
987        Frame* child = HasFrame(node);
988        CachedNode cachedNode;
989        if (child != NULL) {
990            if (child->document() == NULL)
991                continue;
992            RenderObject* nodeRenderer = node->renderer();
993            if (nodeRenderer != NULL && nodeRenderer->style()->visibility() == HIDDEN)
994                continue;
995            CachedFrame cachedChild;
996            cachedChild.init(cachedRoot, cacheIndex, child);
997            int childFrameIndex = cachedFrame->childCount();
998            cachedFrame->addFrame(cachedChild);
999            cachedNode.init(node);
1000            cachedNode.setIndex(cacheIndex++);
1001            cachedNode.setDataIndex(childFrameIndex);
1002            cachedNode.setType(FRAME_CACHEDNODETYPE);
1003#if DUMP_NAV_CACHE
1004            cachedNode.mDebug.mNodeIndex = nodeIndex;
1005            cachedNode.mDebug.mParentGroupIndex = Debug::ParentIndex(
1006                node, nodeIndex, NULL);
1007#endif
1008            cachedFrame->add(cachedNode);
1009            CachedFrame* childPtr = cachedFrame->lastChild();
1010            BuildFrame(root, child, cachedRoot, childPtr);
1011            continue;
1012        }
1013        int tabIndex = node->tabIndex();
1014        Node* lastChild = node->lastChild();
1015        if (tabIndex <= 0)
1016            tabIndex = tabIndexTracker.last().mTabIndex;
1017        else if (tabIndex > 0 && lastChild) {
1018            DBG_NAV_LOGD("tabIndex=%d node=%p", tabIndex, node);
1019            tabIndexTracker.grow(tabIndexTracker.size() + 1);
1020            TabIndexTracker& indexTracker = tabIndexTracker.last();
1021            indexTracker.mTabIndex = tabIndex;
1022            indexTracker.mLastChild = OneAfter(lastChild);
1023        }
1024        RenderObject* nodeRenderer = node->renderer();
1025        bool isTransparent = false;
1026        bool hasCursorRing = true;
1027        if (nodeRenderer != NULL) {
1028            RenderStyle* style = nodeRenderer->style();
1029            if (style->visibility() == HIDDEN)
1030                continue;
1031            isTransparent = style->hasBackground() == false;
1032#ifdef ANDROID_CSS_TAP_HIGHLIGHT_COLOR
1033            hasCursorRing = style->tapHighlightColor().alpha() > 0;
1034#endif
1035#if USE(ACCELERATED_COMPOSITING)
1036            if (nodeRenderer->hasLayer()) {
1037                TrackLayer(layerTracker, nodeRenderer, lastChild,
1038                    globalOffsetX - bodyPos.x(), globalOffsetY - bodyPos.y());
1039                size_t size = tracker.size();
1040                const LayerAndroid* layer = layerTracker.last().mLayer;
1041                if (layer) {
1042                    int id = layer->uniqueId();
1043                    IntPoint loc = nodeRenderer->
1044                        absoluteBoundingBoxRect().location();
1045                    loc.move(globalOffsetX, globalOffsetY);
1046                    // if this is a child of a CachedNode, add a layer
1047                    size_t limit = cachedFrame->layerCount() == 0 ? 0 :
1048                        cachedFrame->lastLayer()->cachedNodeIndex();
1049                    for (size_t index = 1; index < tracker.size(); index++) {
1050                        const FocusTracker& cursorNode = tracker.at(index);
1051                        size_t index = cursorNode.mCachedNodeIndex;
1052                        if (index <= limit) { // already added?
1053                            DBG_NAV_LOGD("index=%d limit=%d id=%d", index,
1054                                limit, id);
1055                            continue;
1056                        }
1057                        DBG_NAV_LOGD("call add layer %d", id);
1058                        CachedNode* trackedNode = cachedFrame->getIndex(index);
1059                        trackedNode->setIsInLayer(true);
1060                        trackedNode->setIsUnclipped(true);
1061                        AddLayer(cachedFrame, index, loc, id);
1062                    }
1063                }
1064            }
1065#endif
1066        }
1067        bool more = walk.mMore;
1068        walk.reset();
1069     //   GetGlobalBounds(node, &bounds, false);
1070        bool computeCursorRings = false;
1071        bool hasClip = false;
1072        bool hasMouseOver = false;
1073        bool isUnclipped = false;
1074        bool isFocus = node == focused;
1075        bool takesFocus = false;
1076        int columnGap = 0;
1077        TextDirection direction = LTR;
1078        String exported;
1079        CachedNodeType type = NORMAL_CACHEDNODETYPE;
1080        CachedInput cachedInput;
1081        IntRect bounds;
1082        IntRect absBounds;
1083        IntRect originalAbsBounds;
1084        WTF::Vector<IntRect>* columns = NULL;
1085        if (node->hasTagName(HTMLNames::areaTag)) {
1086            type = AREA_CACHEDNODETYPE;
1087            HTMLAreaElement* area = static_cast<HTMLAreaElement*>(node);
1088            bounds = getAreaRect(area);
1089            originalAbsBounds = bounds;
1090            bounds.move(globalOffsetX, globalOffsetY);
1091            absBounds = bounds;
1092            isUnclipped = true;  // FIXME: areamaps require more effort to detect
1093             // assume areamaps are always visible for now
1094            takesFocus = true;
1095            goto keepNode;
1096        }
1097        if (nodeRenderer == NULL)
1098            continue;
1099
1100        // some common setup
1101        absBounds = nodeRenderer->absoluteBoundingBoxRect();
1102        originalAbsBounds = absBounds;
1103        absBounds.move(globalOffsetX, globalOffsetY);
1104        hasClip = nodeRenderer->hasOverflowClip();
1105
1106        if (node->hasTagName(HTMLNames::bodyTag))
1107            bodyPos = originalAbsBounds.location();
1108        if (checkForPluginViewThatWantsFocus(nodeRenderer)) {
1109            bounds = absBounds;
1110            isUnclipped = true;
1111            takesFocus = true;
1112            type = PLUGIN_CACHEDNODETYPE;
1113            goto keepNode;
1114        }
1115        if (nodeRenderer->isRenderBlock()) {
1116            RenderBlock* renderBlock = (RenderBlock*) nodeRenderer;
1117            if (renderBlock->hasColumns()) {
1118                columns = renderBlock->columnRects();
1119#ifdef ANDROID_EXPOSE_COLUMN_GAP
1120                columnGap = renderBlock->columnGap();
1121#endif
1122                direction = renderBlock->style()->direction();
1123            }
1124        }
1125        if ((hasClip != false || columns != NULL) && lastChild) {
1126            clipTracker.grow(clipTracker.size() + 1);
1127            ClipColumnTracker& clip = clipTracker.last();
1128            clip.mBounds = absBounds;
1129            clip.mLastChild = OneAfter(lastChild);
1130            clip.mNode = node;
1131            clip.mColumns = columns;
1132            clip.mColumnGap = columnGap;
1133            clip.mHasClip = hasClip;
1134            clip.mDirection = direction;
1135            if (columns != NULL) {
1136                const IntRect& oRect = ((RenderBox*)nodeRenderer)->visibleOverflowRect();
1137                clip.mBounds.move(oRect.x(), oRect.y());
1138            }
1139        }
1140        if (node->isTextNode() && mAllowableTypes != NORMAL_CACHEDNODE_BITS) {
1141            if (last->mSomeParentTakesFocus) // don't look at text inside focusable node
1142                continue;
1143            CachedNodeType checkType;
1144            if (isFocusableText(&walk, more, node, &checkType,
1145                    &exported) == false)
1146                continue;
1147        #if DUMP_NAV_CACHE
1148            {
1149                char buffer[DEBUG_BUFFER_SIZE];
1150                mDebug.init(buffer, sizeof(buffer));
1151                mDebug.print("text link found: ");
1152                mDebug.wideString(exported);
1153                DUMP_NAV_LOGD("%s\n", buffer);
1154            }
1155        #endif
1156            type = checkType;
1157            // !!! test ! is the following line correctly needed for frames to work?
1158            cachedNode.init(node);
1159            const ClipColumnTracker& clipTrack = clipTracker.last();
1160            const IntRect& clip = clipTrack.mHasClip ? clipTrack.mBounds :
1161                IntRect(0, 0, INT_MAX, INT_MAX);
1162            if (ConstructTextRects((WebCore::Text*) node, walk.mStart,
1163                    (WebCore::Text*) walk.mFinalNode, walk.mEnd, globalOffsetX,
1164                    globalOffsetY, &bounds, clip, &cachedNode.mCursorRing) == false)
1165                continue;
1166            absBounds = bounds;
1167            cachedNode.setBounds(bounds);
1168            if (bounds.width() < MINIMUM_FOCUSABLE_WIDTH)
1169                continue;
1170            if (bounds.height() < MINIMUM_FOCUSABLE_HEIGHT)
1171                continue;
1172            computeCursorRings = true;
1173            isUnclipped = true;  // FIXME: to hide or partially occlude synthesized links, each
1174                                 // focus ring will also need the offset and length of characters
1175                                 // used to produce it
1176            goto keepTextNode;
1177        }
1178        if (node->hasTagName(WebCore::HTMLNames::inputTag)) {
1179            HTMLInputElement* input = static_cast<HTMLInputElement*>(node);
1180            HTMLInputElement::InputType inputType = input->inputType();
1181            if (input->isTextField()) {
1182                type = TEXT_INPUT_CACHEDNODETYPE;
1183                cachedInput.init();
1184                cachedInput.setFormPointer(input->form());
1185                cachedInput.setIsTextField(true);
1186                exported = input->value().threadsafeCopy();
1187                cachedInput.setMaxLength(input->maxLength());
1188                cachedInput.setInputType(inputType);
1189    // If this does not need to be threadsafe, we can use crossThreadString().
1190    // See http://trac.webkit.org/changeset/49160.
1191                cachedInput.setName(input->name().string().threadsafeCopy());
1192    // can't detect if this is drawn on top (example: deviant.com login parts)
1193                isUnclipped = isTransparent;
1194            } else if (inputType == HTMLInputElement::HIDDEN)
1195                continue;
1196        } else if (node->hasTagName(HTMLNames::textareaTag)) {
1197            cachedInput.init();
1198            type = TEXT_INPUT_CACHEDNODETYPE;
1199            HTMLTextAreaElement* area = static_cast<HTMLTextAreaElement*>(node);
1200            cachedInput.setFormPointer(area->form());
1201            // Although technically it is not an HTMLInputElement, and therefore
1202            // has no InputType, this one is the most appropriate.
1203            cachedInput.setInputType(HTMLInputElement::TEXT);
1204            cachedInput.setIsTextField(false);
1205            exported = area->value().threadsafeCopy();
1206        } else if (node->hasTagName(HTMLNames::aTag)) {
1207            const HTMLAnchorElement* anchorNode =
1208                (const HTMLAnchorElement*) node;
1209            if (!anchorNode->isFocusable() && !HasTriggerEvent(node))
1210                continue;
1211            if (node->disabled())
1212                continue;
1213            hasMouseOver = NodeHasEventListeners(node, &eventNames().mouseoverEvent, 1);
1214            type = ANCHOR_CACHEDNODETYPE;
1215            KURL href = anchorNode->href();
1216            if (!href.isEmpty() && !WebCore::protocolIsJavaScript(href.string()))
1217                // Set the exported string for all non-javascript anchors.
1218                exported = href.string().threadsafeCopy();
1219        }
1220        if (type == TEXT_INPUT_CACHEDNODETYPE) {
1221            RenderTextControl* renderText =
1222                static_cast<RenderTextControl*>(nodeRenderer);
1223            if (isFocus)
1224                cachedRoot->setSelection(renderText->selectionStart(), renderText->selectionEnd());
1225            // FIXME: Would it be better to use (float) size()?
1226            // FIXME: Are we sure there will always be a style and font, and it's correct?
1227            RenderStyle* style = nodeRenderer->style();
1228            if (style) {
1229                isUnclipped |= !style->hasAppearance();
1230                cachedInput.setTextSize(style->fontSize());
1231                cachedInput.setIsRtlText(style->direction() == RTL
1232                        || style->textAlign() == WebCore::RIGHT
1233                        || style->textAlign() == WebCore::WEBKIT_RIGHT);
1234            }
1235            cachedInput.setPaddingLeft(renderText->paddingLeft() + renderText->borderLeft());
1236            cachedInput.setPaddingTop(renderText->paddingTop() + renderText->borderTop());
1237            cachedInput.setPaddingRight(renderText->paddingRight() + renderText->borderRight());
1238            cachedInput.setPaddingBottom(renderText->paddingBottom() + renderText->borderBottom());
1239        }
1240        takesFocus = true;
1241        bounds = absBounds;
1242        if (type != ANCHOR_CACHEDNODETYPE) {
1243            bool isFocusable = node->isKeyboardFocusable(NULL) ||
1244                node->isMouseFocusable() || node->isFocusable();
1245            if (isFocusable == false) {
1246                if (node->disabled())
1247                    continue;
1248                bool overOrOut = HasOverOrOut(node);
1249                bool hasTrigger = HasTriggerEvent(node);
1250                if (overOrOut == false && hasTrigger == false)
1251                    continue;
1252                takesFocus = hasTrigger;
1253            }
1254        }
1255        computeCursorRings = true;
1256    keepNode:
1257        cachedNode.init(node);
1258        if (computeCursorRings == false) {
1259            cachedNode.setBounds(bounds);
1260            cachedNode.mCursorRing.append(bounds);
1261        } else if (ConstructPartRects(node, bounds, &cachedNode.mBounds,
1262                globalOffsetX, globalOffsetY, &cachedNode.mCursorRing) == false)
1263            continue;
1264    keepTextNode:
1265        IntRect clip = hasClip ? bounds : absBounds;
1266        size_t clipIndex = clipTracker.size();
1267        if (clipTracker.last().mNode == node)
1268            clipIndex -= 1;
1269        while (--clipIndex > 0) {
1270            const ClipColumnTracker& clipTrack = clipTracker.at(clipIndex);
1271            if (clipTrack.mHasClip == false) {
1272                adjustForColumns(clipTrack, &cachedNode, &absBounds);
1273                continue;
1274            }
1275            const IntRect& parentClip = clipTrack.mBounds;
1276            if (hasClip == false && type == ANCHOR_CACHEDNODETYPE)
1277                clip = parentClip;
1278            else
1279                clip.intersect(parentClip);
1280            hasClip = true;
1281        }
1282        if (hasClip) {
1283            if (clip.isEmpty())
1284                continue; // skip this node if clip prevents all drawing
1285            else if (cachedNode.clip(clip) == false)
1286                continue; // skip this node if outside of the clip
1287        }
1288        bool isInLayer = false;
1289#if USE(ACCELERATED_COMPOSITING)
1290        // FIXME: does not work for area rects
1291        LayerAndroid* layer = layerTracker.last().mLayer;
1292        if (layer) {
1293            const IntRect& layerClip = layerTracker.last().mBounds;
1294            if (!layerClip.isEmpty() && !cachedNode.clip(layerClip)) {
1295                DBG_NAV_LOGD("skipped on layer clip %d", cacheIndex);
1296                continue; // skip this node if outside of the clip
1297            }
1298            isInLayer = true;
1299            isUnclipped = true; // assume that layers do not have occluded nodes
1300            AddLayer(cachedFrame, cachedFrame->size(), layerClip.location(),
1301                layer->uniqueId());
1302        }
1303#endif
1304        cachedNode.setNavableRects();
1305        cachedNode.setExport(exported);
1306        cachedNode.setHasCursorRing(hasCursorRing);
1307        cachedNode.setHasMouseOver(hasMouseOver);
1308        cachedNode.setHitBounds(absBounds);
1309        cachedNode.setIndex(cacheIndex);
1310        cachedNode.setIsFocus(isFocus);
1311        cachedNode.setIsInLayer(isInLayer);
1312        cachedNode.setIsTransparent(isTransparent);
1313        cachedNode.setIsUnclipped(isUnclipped);
1314        cachedNode.setOriginalAbsoluteBounds(originalAbsBounds);
1315        cachedNode.setParentIndex(last->mCachedNodeIndex);
1316        cachedNode.setParentGroup(ParentWithChildren(node));
1317        cachedNode.setTabIndex(tabIndex);
1318        cachedNode.setType(type);
1319        if (type == TEXT_INPUT_CACHEDNODETYPE) {
1320            cachedFrame->add(cachedInput);
1321            cachedNode.setDataIndex(textInputIndex);
1322            textInputIndex++;
1323        } else
1324            cachedNode.setDataIndex(-1);
1325#if DUMP_NAV_CACHE
1326        cachedNode.mDebug.mNodeIndex = nodeIndex;
1327        cachedNode.mDebug.mParentGroupIndex = Debug::ParentIndex(
1328            node, nodeIndex, (Node*) cachedNode.parentGroup());
1329#endif
1330        cachedFrame->add(cachedNode);
1331        {
1332            int lastIndex = cachedFrame->size() - 1;
1333            if (node == focused) {
1334                CachedNode* cachedNodePtr = cachedFrame->getIndex(lastIndex);
1335                cachedRoot->setCachedFocus(cachedFrame, cachedNodePtr);
1336            }
1337            if (lastChild != NULL) {
1338                tracker.grow(tracker.size() + 1);
1339                FocusTracker& working = tracker.last();
1340                working.mCachedNodeIndex = lastIndex;
1341                working.mLastChild = OneAfter(lastChild);
1342                last = &tracker.at(tracker.size() - 2);
1343                working.mSomeParentTakesFocus = last->mSomeParentTakesFocus | takesFocus;
1344            }
1345        }
1346        cacheIndex++;
1347    }
1348    while (tracker.size() > 1) {
1349        FocusTracker* last = &tracker.last();
1350        int lastChildIndex = cachedFrame->size() - 1;
1351        if (CleanUpContainedNodes(cachedRoot, cachedFrame, last, lastChildIndex))
1352            cacheIndex--;
1353        tracker.removeLast();
1354    }
1355}
1356
1357bool CacheBuilder::CleanUpContainedNodes(CachedRoot* cachedRoot,
1358    CachedFrame* cachedFrame, const FocusTracker* last, int lastChildIndex)
1359{
1360    // if outer is body, disable outer
1361    // or if there's more than one inner, disable outer
1362    // or if inner is keyboard focusable, disable outer
1363    // else disable inner by removing it
1364    int childCount = lastChildIndex - last->mCachedNodeIndex;
1365    if (childCount == 0)
1366        return false;
1367    CachedNode* lastCached = cachedFrame->getIndex(last->mCachedNodeIndex);
1368    Node* lastNode = (Node*) lastCached->nodePointer();
1369    if ((childCount > 1 && lastNode->hasTagName(HTMLNames::selectTag) == false) ||
1370            lastNode->hasTagName(HTMLNames::bodyTag) ||
1371            lastNode->hasTagName(HTMLNames::formTag)) {
1372        lastCached->setBounds(IntRect(0, 0, 0, 0));
1373        lastCached->mCursorRing.clear();
1374        lastCached->setNavableRects();
1375        return false;
1376    }
1377    CachedNode* onlyChildCached = cachedFrame->lastNode();
1378    Node* onlyChild = (Node*) onlyChildCached->nodePointer();
1379    bool outerIsMouseMoveOnly =
1380        lastNode->isKeyboardFocusable(NULL) == false &&
1381        lastNode->isMouseFocusable() == false &&
1382        lastNode->isFocusable() == false &&
1383        HasOverOrOut(lastNode) == true &&
1384        HasTriggerEvent(lastNode) == false;
1385    if (onlyChildCached->parent() == lastCached)
1386        onlyChildCached->setParentIndex(lastCached->parentIndex());
1387    bool hasFocus = lastCached->isFocus() || onlyChildCached->isFocus();
1388    if (outerIsMouseMoveOnly || onlyChild->isKeyboardFocusable(NULL))
1389        *lastCached = *onlyChildCached;
1390    cachedFrame->removeLast();
1391    if (hasFocus)
1392        cachedRoot->setCachedFocus(cachedFrame, cachedFrame->lastNode());
1393    return true;
1394}
1395
1396Node* CacheBuilder::currentFocus() const
1397{
1398    Frame* frame = FrameAnd(this);
1399    Document* doc = frame->document();
1400    if (doc != NULL) {
1401        Node* focus = doc->focusedNode();
1402        if (focus != NULL)
1403            return focus;
1404    }
1405    Frame* child = frame->tree()->firstChild();
1406    while (child) {
1407        CacheBuilder* cacheBuilder = Builder(child);
1408        Node* focus = cacheBuilder->currentFocus();
1409        if (focus)
1410            return focus;
1411        child = child->tree()->nextSibling();
1412    }
1413    return NULL;
1414}
1415
1416static bool strCharCmp(const char* matches, const UChar* test, int wordLength,
1417    int wordCount)
1418{
1419    for (int index = 0; index < wordCount; index++) {
1420        for (int inner = 0; inner < wordLength; inner++) {
1421            if (matches[inner] != test[inner]) {
1422                matches += wordLength;
1423                goto next;
1424            }
1425        }
1426        return true;
1427next:
1428        ;
1429    }
1430    return false;
1431}
1432
1433static const int stateTwoLetter[] = {
1434    0x02060c00,  // A followed by: [KLRSZ]
1435    0x00000000,  // B
1436    0x00084001,  // C followed by: [AOT]
1437    0x00000014,  // D followed by: [CE]
1438    0x00000000,  // E
1439    0x00001800,  // F followed by: [LM]
1440    0x00100001,  // G followed by: [AU]
1441    0x00000100,  // H followed by: [I]
1442    0x00002809,  // I followed by: [ADLN]
1443    0x00000000,  // J
1444    0x01040000,  // K followed by: [SY]
1445    0x00000001,  // L followed by: [A]
1446    0x000ce199,  // M followed by: [ADEHINOPST]
1447    0x0120129c,  // N followed by: [CDEHJMVY]
1448    0x00020480,  // O followed by: [HKR]
1449    0x00420001,  // P followed by: [ARW]
1450    0x00000000,  // Q
1451    0x00000100,  // R followed by: [I]
1452    0x0000000c,  // S followed by: [CD]
1453    0x00802000,  // T followed by: [NX]
1454    0x00080000,  // U followed by: [T]
1455    0x00080101,  // V followed by: [AIT]
1456    0x01200101   // W followed by: [AIVY]
1457};
1458
1459static const char firstIndex[] = {
1460     0,  5,  5,  8, 10, 10, 12, 14,
1461    15, 19, 19, 21, 22, 32, 40, 43,
1462    46, 46, 47, 49, 51, 52, 55, 59
1463};
1464
1465// from http://infolab.stanford.edu/~manku/bitcount/bitcount.html
1466#define TWO(c)     (0x1u << (c))
1467#define MASK(c)    (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
1468#define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
1469
1470int bitcount (unsigned int n)
1471{
1472    n = COUNT(n, 0);
1473    n = COUNT(n, 1);
1474    n = COUNT(n, 2);
1475    n = COUNT(n, 3);
1476    return COUNT(n, 4);
1477}
1478
1479#undef TWO
1480#undef MASK
1481#undef COUNT
1482
1483static bool isUnicodeSpace(UChar ch)
1484{
1485    return ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r' || ch == 0xa0;
1486}
1487
1488static bool validZip(int stateIndex, const UChar* zipPtr)
1489{
1490    static const struct {
1491        char mLow;
1492        char mHigh;
1493        char mException1;
1494        char mException2;
1495    } zipRange[] = {
1496        { 99, 99, -1, -1 }, // AK Alaska
1497        { 35, 36, -1, -1 }, // AL Alabama
1498        { 71, 72, -1, -1 }, // AR Arkansas
1499        { 96, 96, -1, -1 }, // AS American Samoa
1500        { 85, 86, -1, -1 }, // AZ Arizona
1501        { 90, 96, -1, -1 }, // CA California
1502        { 80, 81, -1, -1 }, // CO Colorado
1503        {  6,  6, -1, -1 }, // CT Connecticut
1504        { 20, 20, -1, -1 }, // DC District of Columbia
1505        { 19, 19, -1, -1 }, // DE Delaware
1506        { 32, 34, -1, -1 }, // FL Florida
1507        { 96, 96, -1, -1 }, // FM Federated States of Micronesia
1508        { 30, 31, -1, -1 }, // GA Georgia
1509        { 96, 96, -1, -1 }, // GU Guam
1510        { 96, 96, -1, -1 }, // HI Hawaii
1511        { 50, 52, -1, -1 }, // IA Iowa
1512        { 83, 83, -1, -1 }, // ID Idaho
1513        { 60, 62, -1, -1 }, // IL Illinois
1514        { 46, 47, -1, -1 }, // IN Indiana
1515        { 66, 67, 73, -1 }, // KS Kansas
1516        { 40, 42, -1, -1 }, // KY Kentucky
1517        { 70, 71, -1, -1 }, // LA Louisiana
1518        {  1,  2, -1, -1 }, // MA Massachusetts
1519        { 20, 21, -1, -1 }, // MD Maryland
1520        {  3,  4, -1, -1 }, // ME Maine
1521        { 96, 96, -1, -1 }, // MH Marshall Islands
1522        { 48, 49, -1, -1 }, // MI Michigan
1523        { 55, 56, -1, -1 }, // MN Minnesota
1524        { 63, 65, -1, -1 }, // MO Missouri
1525        { 96, 96, -1, -1 }, // MP Northern Mariana Islands
1526        { 38, 39, -1, -1 }, // MS Mississippi
1527        { 55, 56, -1, -1 }, // MT Montana
1528        { 27, 28, -1, -1 }, // NC North Carolina
1529        { 58, 58, -1, -1 }, // ND North Dakota
1530        { 68, 69, -1, -1 }, // NE Nebraska
1531        {  3,  4, -1, -1 }, // NH New Hampshire
1532        {  7,  8, -1, -1 }, // NJ New Jersey
1533        { 87, 88, 86, -1 }, // NM New Mexico
1534        { 88, 89, 96, -1 }, // NV Nevada
1535        { 10, 14,  0,  6 }, // NY New York
1536        { 43, 45, -1, -1 }, // OH Ohio
1537        { 73, 74, -1, -1 }, // OK Oklahoma
1538        { 97, 97, -1, -1 }, // OR Oregon
1539        { 15, 19, -1, -1 }, // PA Pennsylvania
1540        {  6,  6,  0,  9 }, // PR Puerto Rico
1541        { 96, 96, -1, -1 }, // PW Palau
1542        {  2,  2, -1, -1 }, // RI Rhode Island
1543        { 29, 29, -1, -1 }, // SC South Carolina
1544        { 57, 57, -1, -1 }, // SD South Dakota
1545        { 37, 38, -1, -1 }, // TN Tennessee
1546        { 75, 79, 87, 88 }, // TX Texas
1547        { 84, 84, -1, -1 }, // UT Utah
1548        { 22, 24, 20, -1 }, // VA Virginia
1549        {  6,  9, -1, -1 }, // VI Virgin Islands
1550        {  5,  5, -1, -1 }, // VT Vermont
1551        { 98, 99, -1, -1 }, // WA Washington
1552        { 53, 54, -1, -1 }, // WI Wisconsin
1553        { 24, 26, -1, -1 }, // WV West Virginia
1554        { 82, 83, -1, -1 }  // WY Wyoming
1555    };
1556
1557    int zip = zipPtr[0] - '0';
1558    zip *= 10;
1559    zip += zipPtr[1] - '0';
1560    int low = zipRange[stateIndex].mLow;
1561    int high = zipRange[stateIndex].mHigh;
1562    if (zip >= low && zip <= high)
1563        return true;
1564    if (zip == zipRange[stateIndex].mException1)
1565        return true;
1566    if (zip == zipRange[stateIndex].mException2)
1567        return true;
1568    return false;
1569}
1570
1571#define MAX_PLACE_NAME_LENGTH 25 // the longest allowable one word place name
1572
1573CacheBuilder::FoundState CacheBuilder::FindAddress(const UChar* chars,
1574    unsigned length, int* start, int* end, bool caseInsensitive)
1575{
1576    FindState addressState;
1577    FindReset(&addressState);
1578    addressState.mWords[0] = addressState.mStarts[0] = chars;
1579    addressState.mCaseInsensitive = caseInsensitive;
1580    FoundState state = FindPartialAddress(chars, chars, length, &addressState);
1581    if (state == FOUND_PARTIAL && addressState.mProgress == ZIP_CODE &&
1582            addressState.mNumberCount == 0) {
1583        addressState.mProgress = FIND_STREET;
1584        state = FindPartialAddress(NULL, NULL, 0, &addressState);
1585    }
1586    *start = addressState.mStartResult;
1587    *end = addressState.mEndResult;
1588    return state;
1589}
1590
1591CacheBuilder::FoundState CacheBuilder::FindPartialAddress(const UChar* baseChars,
1592    const UChar* chars, unsigned length, FindState* s)
1593{
1594    // lower case letters are optional; trailing asterisk is optional 's'
1595    static char const* const longStreetNames[] = {
1596        "\x04" "LleY" "\x04" "NneX" "\x05" "RCade" "\x05" "VEnue" "\x06" "LAMEDA", // A
1597        "\x04" "aYoU" "\x04" "eaCH" "\x03" "eND" "\x05" "LuFf*" "\x05" "oTtoM"
1598            "\x08" "ouLeVarD" "\x05" "Ranch" "\x05" "RidGe" "\x05" "RooK*"
1599            "\x04" "urG*" "\x05" "YPass" "\x07" "roadWAY", // B
1600        "\x05" "AMINO"
1601        "\x03" "amP" "\x05" "anYoN" "\x03" "aPE" "\x07" "auSeWaY" "\x06" "enTeR*"
1602            "\x06" "IRcle*" "\x05" "LiFf*" "\x03" "LuB" "\x05" "oMmoN" "\x06" "ORner*"
1603            "\x05" "ouRSE" "\x05" "ourT*" "\x04" "oVe*" "\x04" "ReeK" "\x07" "REScent"
1604            "\x04" "ReST" "\x07" "ROSSING" "\x08" "ROSSROAD" "\x04" "URVe"
1605            "\x05" "AMINO" "\x06" "IRCULO" "\x07" "REScent", // C
1606        "\x03" "aLe" "\x02" "aM" "\x05" "iVide" "\x05" "Rive*", // D
1607        "\x06" "STate*" "\x09" "XPresswaY" "\x09" "XTension*", // E
1608        "\x04" "ALL*" "\x04" "eRrY" "\x05" "ieLD*" "\x04" "LaT*" "\x04" "oRD*"
1609            "\x05" "oReST" "\x05" "oRGe*" "\x04" "oRK*" "\x03" "orT" "\x06" "reeWaY", // F
1610        "\x06" "arDeN*" "\x06" "aTeWaY" "\x04" "LeN*" "\x05" "ReeN*" "\x05" "RoVe*", // G
1611        "\x06" "arBoR*" "\x04" "aVeN" "\x06" "eighTS" "\x06" "ighWaY" "\x04" "iLl*"
1612            "\x05" "OLloW", // H
1613        "\x04" "NLeT" "\x06" "Sland*" "\x03" "SLE", // I
1614        "\x08" "unCTion*", // J
1615        "\x03" "eY*" "\x05" "NoLl*", // K
1616        "\x04" "aKe*" "\x03" "AND" "\x06" "aNDinG" "\x03" "aNe" "\x05" "iGhT*"
1617            "\x03" "oaF" "\x04" "oCK*" "\x04" "oDGe" "\x03" "OOP", // L
1618        "\x03" "ALL" "\x05" "aNoR*" "\x06" "eaDoW*" "\x03" "EWS" "\x04" "iLl*"
1619            "\x06" "iSsioN" "\x07" "oTorWaY" "\x04" "ounT" "\x08" "ounTaiN*", // M
1620        "\x03" "eCK", // N
1621        "\x06" "RCHard" "\x03" "VAL" "\x07" "verPASs", // O
1622        "\x04" "ARK*" "\x07" "arKWaY*" "\x03" "ASS" "\x06" "aSsaGE" "\x03" "ATH"
1623            "\x03" "IKE" "\x04" "iNE*" "\x04" "Lace" "\x05" "LaiN*" "\x04" "LaZa"
1624            "\x05" "oinT*" "\x04" "oRT*" "\x06" "Rairie" "\x06" "RIVADA", // P
1625        NULL,
1626        "\x05" "ADiaL" "\x03" "AMP" "\x04" "aNCH" "\x05" "aPiD*"
1627            "\x03" "eST"
1628            "\x05" "iDGe*" "\x04" "IVer" "\x04" "oaD*" "\x04" "ouTE" "\x02" "OW"
1629            "\x02" "UE" "\x02" "UN", // R
1630        "\x05" "HoaL*" "\x05" "HoRe*" "\x05" "KyWaY" "\x06" "PrinG*" "\x04" "PUR*"
1631            "\x06" "Quare*" "\x06" "TAtion" "\x08" "TRAvenue" "\x05" "TReaM"
1632            "\x06" "Treet*" "\x05" "uMmiT" "\x07" "PeeDWaY", // S
1633        "\x06" "ERrace" "\x09" "hRoughWaY" "\x04" "RaCE" "\x04" "RAcK" "\x09" "RaFficwaY"
1634            "\x04" "RaiL" "\x05" "UNneL" "\x07" "urnPiKE", // T
1635        "\x08" "nderPASs" "\x05" "Nion*", // U
1636        "\x06" "aLleY*" "\x06" "IAduct" "\x04" "ieW*" "\x07" "iLlaGe*" "\x04" "iLle"
1637            "\x04" "ISta", // V
1638        "\x04" "ALK*" "\x03" "ALL" "\x03" "AY*" "\x04" "eLl*", // W
1639        "\x03" "ING" "\x02" "RD", // X
1640    };
1641
1642    static char const* const longStateNames[] = {
1643        "\x8e" "la" "\x85" "bama" "\x02" "\x84" "ska" "\x01" "\x8f" "merican Samoa" "\x04"
1644             "\x91" "r" "\x86" "izona" "\x05" "\x87" "kansas" "\x03",
1645        NULL,
1646        "\x8b" "alifornia" "\x06" "\x95" "o" "\x87" "lorado" "\x07" "\x8a" "nnecticut" "\x08",
1647        "\x89" "elaware" "\x0a" "\x95" "istrict of Columbia" "\x09",
1648        NULL,
1649        "\x9f" "ederated States of Micronesia" "\x0c" "\x88" "lorida" "\x0b",
1650        "\x85" "uam" "\x0e" "\x88" "eorgia" "\x0d",
1651        "\x87" "awaii" "\x0f",
1652        "\x86" "daho" "\x11" "\x89" "llinois" "\x12" "\x88" "ndiana" "\x13" "\x85"
1653             "owa" "\x10",
1654        NULL,
1655        "\x87" "ansas" "\x14" "\x89" "entucky" "\x15",
1656        "\x8a" "ouisiana" "\x16",
1657        "\x86" "aine" "\x19" "\x99" "ar" "\x8e" "shall Islands" "\x1a" "\x86" "yland" "\x18"
1658             "\x8e" "assachusetts" "\x17" "\x93" "i" "\x87" "chigan" "\x1b"
1659             "\x88" "nnesota" "\x1c" "\x93" "iss" "\x88" "issippi" "\x1f" "\x85"
1660             "ouri" "\x1d" "\x88" "ontana" "\x20",
1661        "\x90" "e" "\x87" "braska" "\x23" "\x85" "vada" "\x27" "\xa5" "ew " "\x8a"
1662             "Hampshire" "\x24" "\x87" "Jersey" "\x25" "\x87" "Mexico" "\x26"
1663             "\x85" "York" "\x28" "\x98" "orth " "\x89" "Carolina" "\x21" "\x87"
1664             "Dakota" "\x22" "\x99" "orthern Mariana Islands" "\x1e",
1665        "\x85" "hio" "\x29" "\x89" "klahoma" "\x2a" "\x87" "regon" "\x2b",
1666        "\x86" "alau" "\x2e" "\x8d" "ennsylvania" "\x2c" "\x8c" "uerto Rico" "\x2d",
1667        NULL,
1668        "\x8d" "hode Island" "\x2f",
1669        "\x98" "outh " "\x89" "Carolina" "\x30" "\x87" "Dakota" "\x31",
1670        "\x90" "e" "\x88" "nnessee" "\x32" "\x84" "xas" "\x33",
1671        "\x85" "tah" "\x34",
1672        "\x88" "ermont" "\x37" "\x94" "irgin" "\x89" " Islands" "\x36" "\x83" "ia" "\x35",
1673        "\x8b" "ashington" "\x38" "\x8e" "est Virginia" "\x3a" "\x8a" "isconsin" "\x39"
1674             "\x88" "yoming" "\x3b"
1675    };
1676
1677#if 0 // DEBUG_NAV_UI
1678    static char const* const progressNames[] = {
1679        "NO_ADDRESS",
1680        "SKIP_TO_SPACE",
1681        "HOUSE_NUMBER",
1682        "NUMBER_TRAILING_SPACE",
1683        "ADDRESS_LINE",
1684        "STATE_NAME",
1685        "SECOND_HALF",
1686        "ZIP_CODE",
1687        "PLUS_4",
1688        "FIND_STREET"
1689    };
1690#endif
1691    // strategy: US only support at first
1692    // look for a 1 - 5 digit number for a street number (no support for 'One Microsoft Way')
1693        // ignore if preceded by '#', Suite, Ste, Rm
1694    // look for two or more words (up to 5? North Frank Lloyd Wright Blvd)
1695            // note: "The Circle at North Hills St." has six words, and a lower 'at' -- allow at, by, of, in, the, and, ... ?
1696        // if a word starts with a lowercase letter, no match
1697        // allow: , . - # / (for 1/2) ' "
1698        // don't look for street name type yet
1699    // look for one or two delimiters to represent possible 2nd addr line and city name
1700    // look for either full state name, or state two letters, and/or zip code (5 or 9 digits)
1701    // now look for street suffix, either in full or abbreviated form, with optional 's' if there's an asterisk
1702
1703    s->mCurrentStart = chars;
1704    s->mEnd = chars + length;
1705    int candIndex = 0;
1706    bool retryState;
1707    bool mustBeAllUpper = false;
1708    bool secondHalf = false;
1709    chars -= 1;
1710    UChar ch = s->mCurrent;
1711    while (++chars <= s->mEnd) {
1712        UChar prior = ch;
1713        ch = chars < s->mEnd ? *chars : ' ';
1714        switch (s->mProgress) {
1715            case NO_ADDRESS:
1716                if (WTF::isASCIIDigit(ch) == false) {
1717                    if (ch != 'O') // letter 'O', not zero
1718                        continue;
1719                    if (s->mEnd - chars < 3)
1720                        continue;
1721                    prior = *++chars;
1722                    ch = *++chars;
1723                    if ((prior != 'n' || ch != 'e') && (prior != 'N' || ch != 'E'))
1724                        continue;
1725                    if (isUnicodeSpace(*++chars) == false)
1726                        continue;
1727                    s->mProgress = ADDRESS_LINE;
1728                    s->mStartResult = chars - 3 - s->mCurrentStart;
1729                    continue;
1730                }
1731                if (isUnicodeSpace(prior) == false) {
1732                    s->mProgress = SKIP_TO_SPACE;
1733                    continue;
1734                }
1735                s->mNumberCount = 1;
1736                s->mProgress = HOUSE_NUMBER;
1737                s->mStartResult = chars - s->mCurrentStart;
1738                continue;
1739            case SKIP_TO_SPACE:
1740                if (isUnicodeSpace(ch) == false)
1741                    continue;
1742                break;
1743            case HOUSE_NUMBER:
1744                if (WTF::isASCIIDigit(ch)) {
1745                    if (++s->mNumberCount >= 6)
1746                        s->mProgress = SKIP_TO_SPACE;
1747                    continue;
1748                }
1749                if (WTF::isASCIIUpper(ch)) { // allow one letter after house number, e.g. 12A SKOLFIELD PL, HARPSWELL, ME 04079
1750                    if (WTF::isASCIIDigit(prior) == false)
1751                        s->mProgress = SKIP_TO_SPACE;
1752                    continue;
1753                }
1754                if (ch == '-') {
1755                    if (s->mNumberCount > 0) { // permit 21-23 ELM ST
1756                        ++s->mNumberCount;
1757                        continue;
1758                    }
1759                }
1760                s->mNumberCount = 0;
1761                s->mProgress = NUMBER_TRAILING_SPACE;
1762            case NUMBER_TRAILING_SPACE:
1763                if (isUnicodeSpace(ch))
1764                    continue;
1765                if (0 && WTF::isASCIIDigit(ch)) {
1766                    s->mNumberCount = 1;
1767                    s->mProgress = HOUSE_NUMBER;
1768                    s->mStartResult = chars - s->mCurrentStart;
1769                    continue;
1770                }
1771                if (WTF::isASCIIDigit(ch) == false && WTF::isASCIIUpper(ch) == false)
1772                    break;
1773                s->mProgress = ADDRESS_LINE;
1774            case ADDRESS_LINE:
1775                if (WTF::isASCIIAlpha(ch) || ch == '\'' || ch == '-' || ch == '&' || ch == '(' || ch == ')') {
1776                    if (++s->mLetterCount > 1) {
1777                        s->mNumberWords &= ~(1 << s->mWordCount);
1778                        continue;
1779                    }
1780                    if (s->mNumberCount >= 5)
1781                        break;
1782// FIXME: the test below was added to give up on a non-address, but it
1783// incorrectly discards addresses where the house number is in one node
1784// and the street name is in the next; I don't recall what the failing case
1785// is that suggested this fix.
1786//                    if (s->mWordCount == 0 && s->mContinuationNode)
1787//                        return FOUND_NONE;
1788                    s->newWord(baseChars, chars);
1789                    if (WTF::isASCIILower(ch) && s->mNumberCount == 0)
1790                        s->mFirstLower = chars;
1791                    s->mNumberCount = 0;
1792                    if (WTF::isASCIILower(ch) || (WTF::isASCIIAlpha(ch) == false && ch != '-'))
1793                        s->mNumberWords &= ~(1 << s->mWordCount);
1794                    s->mUnparsed = true;
1795                    continue;
1796                } else if (s->mLetterCount >= MAX_PLACE_NAME_LENGTH) {
1797                    break;
1798                } else if (s->mFirstLower != NULL) {
1799                    if (s->mCaseInsensitive)
1800                        goto resetWord;
1801                    size_t length = chars - s->mFirstLower;
1802                    if (length > 3)
1803                        break;
1804                    if (length == 3 && strCharCmp("and" "the", s->mFirstLower, 3, 2) == false)
1805                        break;
1806                    if (length == 2 && strCharCmp("at" "by" "el" "in" "of", s->mFirstLower, 2, 5) == false)
1807                        break;
1808                    goto resetWord;
1809                }
1810                if (ch == ',' || ch == '*') { // delimits lines
1811                    // asterisk as delimiter: http://www.sa.sc.edu/wellness/members.html
1812                    if (++s->mLineCount > 5)
1813                        break;
1814                    goto lookForState;
1815                }
1816                if (isUnicodeSpace(ch) || prior == '-') {
1817            lookForState:
1818                    if (s->mUnparsed == false)
1819                        continue;
1820                    const UChar* candidate = s->mWords[s->mWordCount];
1821                    UChar firstLetter = candidate[0];
1822                    if (WTF::isASCIIUpper(firstLetter) == false && WTF::isASCIIDigit(firstLetter) == false)
1823                        goto resetWord;
1824                    s->mWordCount++;
1825                    if ((s->mWordCount == 2 && s->mNumberWords == 3 && WTF::isASCIIDigit(s->mWords[1][1])) || // choose second of 8888 333 Main
1826                        (s->mWordCount >= sizeof(s->mWords) / sizeof(s->mWords[0]) - 1)) { // subtract 1 since state names may have two parts
1827                        // search for simple number already stored since first potential house # didn't pan out
1828                        if (s->mNumberWords == 0)
1829                            break;
1830                        int shift = 0;
1831                        while ((s->mNumberWords & (1 << shift)) == 0)
1832                            shift++;
1833                        s->mNumberWords >>= ++shift;
1834                        if (s->mBases[0] != s->mBases[shift]) // if we're past the original node, bail
1835                            break;
1836                        s->shiftWords(shift);
1837                        s->mStartResult = s->mWords[0] - s->mStarts[0];
1838                        s->mWordCount -= shift;
1839                        // FIXME: need to adjust lineCount to account for discarded delimiters
1840                    }
1841                    if (s->mWordCount < 4)
1842                        goto resetWord;
1843                    firstLetter -= 'A';
1844                    if (firstLetter > 'W' - 'A')
1845                        goto resetWord;
1846                    UChar secondLetter = candidate[1];
1847                    if (prior == '-')
1848                        s->mLetterCount--; // trim trailing dashes, to accept CA-94043
1849                    if (s->mLetterCount == 2) {
1850                        secondLetter -= 'A';
1851                        if (secondLetter > 'Z' - 'A')
1852                            goto resetWord;
1853                        if ((stateTwoLetter[firstLetter] & 1 << secondLetter) != 0) {
1854                            // special case to ignore 'et al'
1855                            if (strCharCmp("ET", s->mWords[s->mWordCount - 2], 2, 1) == false) {
1856                                s->mStateWord = s->mWordCount - 1;
1857                                s->mZipHint = firstIndex[firstLetter] +
1858                                    bitcount(stateTwoLetter[firstLetter] & ((1 << secondLetter) - 1));
1859                                goto foundStateName;
1860                            }
1861                        }
1862                        goto resetWord;
1863                    }
1864                    s->mStates = longStateNames[firstLetter];
1865                    if (s->mStates == NULL)
1866                        goto resetWord;
1867                    mustBeAllUpper = false;
1868                    s->mProgress = STATE_NAME;
1869                    unsigned char section = s->mStates[0];
1870                    ASSERT(section > 0x80);
1871                    s->mSectionLength = section & 0x7f;
1872                    candIndex = 1;
1873                    secondHalf = false;
1874                    s->mStateWord = s->mWordCount - 1;
1875                    goto stateName;
1876                }
1877                if (WTF::isASCIIDigit(ch)) {
1878                    if (s->mLetterCount == 0) {
1879                        if (++s->mNumberCount > 1)
1880                            continue;
1881                        if (s->mWordCount == 0 && s->mContinuationNode)
1882                            return FOUND_NONE;
1883                        s->newWord(baseChars, chars);
1884                        s->mNumberWords |= 1 << s->mWordCount;
1885                        s->mUnparsed = true;
1886                    }
1887                    continue;
1888                }
1889                if (ch == '.') { // optionally can follow letters
1890                    if (s->mLetterCount == 0)
1891                        break;
1892                    if (s->mNumberCount > 0)
1893                        break;
1894                    continue;
1895                }
1896                if (ch == '/') // between numbers (1/2) between words (12 Main / Ste 4d)
1897                    goto resetWord;
1898                if (ch == '#') // can precede numbers, allow it to appear randomly
1899                    goto resetWord;
1900                if (ch == '"') // sometimes parts of addresses are quoted (FIXME: cite an example here)
1901                    continue;
1902                break;
1903            case SECOND_HALF:
1904                if (WTF::isASCIIAlpha(ch)) {
1905                    if (s->mLetterCount == 0) {
1906                        s->newWord(baseChars, chars);
1907                        s->mWordCount++;
1908                    }
1909                    s->mLetterCount++;
1910                    continue;
1911                }
1912                if (WTF::isASCIIDigit(ch) == false) {
1913                    if (s->mLetterCount > 0) {
1914                        s->mProgress = STATE_NAME;
1915                        candIndex = 0;
1916                        secondHalf = true;
1917                        goto stateName;
1918                    }
1919                    continue;
1920                }
1921                s->mProgress = ADDRESS_LINE;
1922                goto resetState;
1923            case STATE_NAME:
1924            stateName:
1925                // pick up length of first section
1926                do {
1927                    int stateIndex = 1;
1928                    int skip = 0;
1929                    int prefix = 0;
1930                    bool subStr = false;
1931                    do {
1932                        unsigned char match = s->mStates[stateIndex];
1933                        if (match >= 0x80) {
1934                            if (stateIndex == s->mSectionLength)
1935                                break;
1936                            subStr = true;
1937                  //          if (skip > 0)
1938                  //              goto foundStateName;
1939                            prefix = candIndex;
1940                            skip = match & 0x7f;
1941                            match = s->mStates[++stateIndex];
1942                        }
1943                        UChar candChar = s->mWords[s->mWordCount - 1][candIndex];
1944                        if (mustBeAllUpper && WTF::isASCIILower(candChar))
1945                            goto skipToNext;
1946                        if (match != candChar) {
1947                            if (match != WTF::toASCIILower(candChar)) {
1948                       skipToNext:
1949                                if (subStr == false)
1950                                    break;
1951                                if (stateIndex == s->mSectionLength) {
1952                                    if (secondHalf) {
1953                                        s->mProgress = ADDRESS_LINE;
1954                                        goto resetState;
1955                                    }
1956                                    break;
1957                                }
1958                                stateIndex += skip;
1959                                skip = 0;
1960                                candIndex = prefix;
1961                                continue; // try next substring
1962                            }
1963                            mustBeAllUpper = true;
1964                        }
1965                        int nextindex = stateIndex + 1;
1966                        if (++candIndex >= s->mLetterCount && s->mStates[nextindex] == ' ') {
1967                            s->mProgress = SECOND_HALF;
1968                            s->mStates += nextindex;
1969                            s->mSectionLength -= nextindex;
1970                            goto resetWord;
1971                        }
1972                        if (nextindex + 1 == s->mSectionLength || skip == 2) {
1973                            s->mZipHint = s->mStates[nextindex] - 1;
1974                            goto foundStateName;
1975                        }
1976                        stateIndex += 1;
1977                        skip -= 1;
1978                    } while (true);
1979                    s->mStates += s->mSectionLength;
1980                    ASSERT(s->mStates[0] == 0 || (unsigned) s->mStates[0] > 0x80);
1981                    s->mSectionLength = s->mStates[0] & 0x7f;
1982                    candIndex = 1;
1983                    subStr = false;
1984                } while (s->mSectionLength != 0);
1985                s->mProgress = ADDRESS_LINE;
1986                goto resetState;
1987            foundStateName:
1988                s->mEndResult = chars - s->mCurrentStart;
1989                s->mEndWord = s->mWordCount - 1;
1990                s->mProgress = ZIP_CODE;
1991                // a couple of delimiters is an indication that the state name is good
1992                // or, a non-space / non-alpha-digit is also good
1993                s->mZipDelimiter = s->mLineCount > 2
1994                    || isUnicodeSpace(ch) == false
1995                    || chars == s->mEnd;
1996                if (WTF::isASCIIDigit(ch))
1997                    s->mZipStart = chars;
1998                goto resetState;
1999            case ZIP_CODE:
2000                if (WTF::isASCIIDigit(ch)) {
2001                    int count = ++s->mNumberCount;
2002                    if (count == 1) {
2003                        if (WTF::isASCIIDigit(prior))
2004                            ++s->mNumberCount;
2005                        else
2006                            s->mZipStart = chars;
2007                    }
2008                    if (count <= 9)
2009                        continue;
2010                } else if (isUnicodeSpace(ch)) {
2011                    if (s->mNumberCount == 0) {
2012                        s->mZipDelimiter = true; // two spaces delimit state name
2013                        continue;
2014                    }
2015                } else if (ch == '-') {
2016                    if (s->mNumberCount == 5 && validZip(s->mZipHint, s->mZipStart)) {
2017                        s->mNumberCount = 0;
2018                        s->mProgress = PLUS_4;
2019                        continue;
2020                    }
2021                    if (s->mNumberCount == 0)
2022                        s->mZipDelimiter = true;
2023                } else if (WTF::isASCIIAlpha(ch) == false)
2024                    s->mZipDelimiter = true;
2025                else {
2026                    if (s->mLetterCount == 0) {
2027                        s->newWord(baseChars, chars);
2028                        s->mUnparsed = true;
2029                    }
2030                    ++s->mLetterCount;
2031                }
2032                if (s->mNumberCount == 5 || s->mNumberCount == 9) {
2033                    if (validZip(s->mZipHint, s->mZipStart) == false)
2034                        goto noZipMatch;
2035                    s->mEndResult = chars - s->mCurrentStart;
2036                    s->mEndWord = s->mWordCount - 1;
2037                } else if (s->mZipDelimiter == false) {
2038            noZipMatch:
2039                    --chars;
2040                    s->mProgress = ADDRESS_LINE;
2041                    continue;
2042                }
2043                s->mProgress = FIND_STREET;
2044                goto findStreet;
2045            case PLUS_4:
2046                if (WTF::isASCIIDigit(ch)) {
2047                    if (++s->mNumberCount <= 4)
2048                        continue;
2049                }
2050                if (isUnicodeSpace(ch)) {
2051                    if (s->mNumberCount == 0)
2052                        continue;
2053                }
2054                if (s->mNumberCount == 4) {
2055                    if (WTF::isASCIIAlpha(ch) == false) {
2056                        s->mEndResult = chars - s->mCurrentStart;
2057                        s->mEndWord = s->mWordCount - 1;
2058                    }
2059                } else if (s->mNumberCount != 0)
2060                    break;
2061                s->mProgress = FIND_STREET;
2062            case FIND_STREET:
2063            findStreet:
2064                retryState = false;
2065                for (int wordsIndex = s->mStateWord - 1; wordsIndex >= 0; --wordsIndex) {
2066                    const UChar* test = s->mWords[wordsIndex];
2067                    UChar letter = test[0];
2068                    letter -= 'A';
2069                    if (letter > 'X' - 'A')
2070                        continue;
2071                    const char* names = longStreetNames[letter];
2072                    if (names == NULL)
2073                        continue;
2074                    int offset;
2075                    while ((offset = *names++) != 0) {
2076                        int testIndex = 1;
2077                        bool abbr = false;
2078                        for (int idx = 0; idx < offset; idx++) {
2079                            char nameLetter = names[idx];
2080                            char testUpper = WTF::toASCIIUpper(test[testIndex]);
2081                            if (nameLetter == '*') {
2082                                if (testUpper == 'S')
2083                                    testIndex++;
2084                                break;
2085                            }
2086                            bool fullOnly = WTF::isASCIILower(nameLetter);
2087                            nameLetter = WTF::toASCIIUpper(nameLetter);
2088                            if (testUpper == nameLetter) {
2089                                if (abbr && fullOnly)
2090                                    goto nextTest;
2091                                testIndex++;
2092                                continue;
2093                            }
2094                            if (fullOnly == false)
2095                                goto nextTest;
2096                            abbr = true;
2097                        }
2098                        letter = &test[testIndex] < s->mEnds[wordsIndex] ?
2099                            test[testIndex] : ' ';
2100                        if (WTF::isASCIIAlpha(letter) == false && WTF::isASCIIDigit(letter) == false) {
2101                            if (s->mNumberWords != 0) {
2102                                int shift = 0;
2103                                int wordReduction = -1;
2104                                do {
2105                                    while ((s->mNumberWords & (1 << shift)) == 0)
2106                                        shift++;
2107                                    if (shift > wordsIndex)
2108                                        break;
2109                                    wordReduction = shift;
2110                                } while (s->mNumberWords >> ++shift != 0);
2111                                if (wordReduction >= 0) {
2112                                    if (s->mContinuationNode) {
2113                                        if (retryState)
2114                                            break;
2115                                        return FOUND_NONE;
2116                                    }
2117                                    s->mStartResult = s->mWords[wordReduction] - s->mStarts[wordReduction];
2118                                }
2119                            }
2120                            if (wordsIndex != s->mStateWord - 1)
2121                                return FOUND_COMPLETE;
2122                            retryState = true;
2123                        }
2124                    nextTest:
2125                        names += offset;
2126                    }
2127                }
2128                if (retryState) {
2129                    s->mProgress = ADDRESS_LINE;
2130                    s->mStates = NULL;
2131                    continue;
2132                }
2133                if (s->mNumberWords != 0) {
2134                    unsigned shift = 0;
2135                    while ((s->mNumberWords & (1 << shift)) == 0)
2136                        shift++;
2137                    s->mNumberWords >>= ++shift;
2138                    if (s->mBases[0] != s->mBases[shift])
2139                        return FOUND_NONE;
2140                    s->shiftWords(shift);
2141                    s->mStartResult = s->mWords[0] - s->mStarts[0];
2142                    s->mWordCount -= shift;
2143                    s->mProgress = ADDRESS_LINE;
2144                    --chars;
2145                    continue;
2146                }
2147                break;
2148        }
2149        if (s->mContinuationNode)
2150            return FOUND_NONE;
2151        s->mProgress = NO_ADDRESS;
2152        s->mWordCount = s->mLineCount = 0;
2153        s->mNumberWords = 0;
2154    resetState:
2155        s->mStates = NULL;
2156    resetWord:
2157        s->mNumberCount = s->mLetterCount = 0;
2158        s->mFirstLower = NULL;
2159        s->mUnparsed = false;
2160    }
2161    s->mCurrent = ch;
2162    return s->mProgress == NO_ADDRESS ? FOUND_NONE : FOUND_PARTIAL;
2163}
2164
2165// Recogize common email patterns only. Currently has lots of state, walks text forwards and backwards -- will be
2166// a real challenge to adapt to walk text across multiple nodes, I imagine
2167// FIXME: it's too hard for the caller to call these incrementally -- it's probably best for this to
2168// either walk the node tree directly or make a callout to get the next or previous node, if there is one
2169// walking directly will avoid adding logic in caller to track the multiple partial or full nodes that compose this
2170// text pattern.
2171CacheBuilder::FoundState CacheBuilder::FindPartialEMail(const UChar* chars, unsigned length,
2172    FindState* s)
2173{
2174    // the following tables were generated by tests/browser/focusNavigation/BrowserDebug.cpp
2175    // hand-edit at your own risk
2176    static const int domainTwoLetter[] = {
2177        0x02df797c,  // a followed by: [cdefgilmnoqrstuwxz]
2178        0x036e73fb,  // b followed by: [abdefghijmnorstvwyz]
2179        0x03b67ded,  // c followed by: [acdfghiklmnorsuvxyz]
2180        0x02005610,  // d followed by: [ejkmoz]
2181        0x001e00d4,  // e followed by: [ceghrstu]
2182        0x00025700,  // f followed by: [ijkmor]
2183        0x015fb9fb,  // g followed by: [abdefghilmnpqrstuwy]
2184        0x001a3400,  // h followed by: [kmnrtu]
2185        0x000f7818,  // i followed by: [delmnoqrst]
2186        0x0000d010,  // j followed by: [emop]
2187        0x0342b1d0,  // k followed by: [eghimnprwyz]
2188        0x013e0507,  // l followed by: [abcikrstuvy]
2189        0x03fffccd,  // m followed by: [acdghklmnopqrstuvwxyz]
2190        0x0212c975,  // n followed by: [acefgilopruz]
2191        0x00001000,  // o followed by: [m]
2192        0x014e3cf1,  // p followed by: [aefghklmnrstwy]
2193        0x00000001,  // q followed by: [a]
2194        0x00504010,  // r followed by: [eouw]
2195        0x032a7fdf,  // s followed by: [abcdeghijklmnortvyz]
2196        0x026afeec,  // t followed by: [cdfghjklmnoprtvwz]
2197        0x03041441,  // u followed by: [agkmsyz]
2198        0x00102155,  // v followed by: [aceginu]
2199        0x00040020,  // w followed by: [fs]
2200        0x00000000,  // x
2201        0x00180010,  // y followed by: [etu]
2202        0x00401001,  // z followed by: [amw]
2203    };
2204
2205    static char const* const longDomainNames[] = {
2206        "\x03" "ero" "\x03" "rpa",  // aero, arpa
2207        "\x02" "iz",  // biz
2208        "\x02" "at" "\x02" "om" "\x03" "oop",  // cat, com, coop
2209        NULL,  // d
2210        "\x02" "du",  // edu
2211        NULL,  // f
2212        "\x02" "ov",  // gov
2213        NULL,  // h
2214        "\x03" "nfo" "\x02" "nt",  // info, int
2215        "\x03" "obs",  // jobs
2216        NULL,  // k
2217        NULL,  // l
2218        "\x02" "il" "\x03" "obi" "\x05" "useum",  // mil, mobi, museum
2219        "\x03" "ame" "\x02" "et",  // name, net
2220        "\x02" "rg",  // , org
2221        "\x02" "ro",  // pro
2222        NULL,  // q
2223        NULL,  // r
2224        NULL,  // s
2225        "\x05" "ravel",  // travel
2226        NULL,  // u
2227        NULL,  // v
2228        NULL,  // w
2229        NULL,  // x
2230        NULL,  // y
2231        NULL,  // z
2232    };
2233
2234    const UChar* start = chars;
2235    const UChar* end = chars + length;
2236    while (chars < end) {
2237        UChar ch = *chars++;
2238        if (ch != '@')
2239            continue;
2240        const UChar* atLocation = chars - 1;
2241        // search for domain
2242        ch = *chars++ | 0x20; // convert uppercase to lower
2243        if (ch < 'a' || ch > 'z')
2244            continue;
2245        while (chars < end) {
2246            ch = *chars++;
2247            if (IsDomainChar(ch) == false)
2248                goto nextAt;
2249            if (ch != '.')
2250                continue;
2251            UChar firstLetter = *chars++ | 0x20; // first letter of the domain
2252            if (chars >= end)
2253                return FOUND_NONE; // only one letter; must be at least two
2254            firstLetter -= 'a';
2255            if (firstLetter > 'z' - 'a')
2256                continue; // non-letter followed '.'
2257            int secondLetterMask = domainTwoLetter[firstLetter];
2258            ch = *chars | 0x20; // second letter of the domain
2259            ch -= 'a';
2260            if (ch >= 'z' - 'a')
2261                continue;
2262            bool secondMatch = (secondLetterMask & 1 << ch) != 0;
2263            const char* wordMatch = longDomainNames[firstLetter];
2264            int wordIndex = 0;
2265            while (wordMatch != NULL) {
2266                int len = *wordMatch++;
2267                char match;
2268                do {
2269                    match = wordMatch[wordIndex];
2270                    if (match < 0x20)
2271                        goto foundDomainStart;
2272                    if (chars[wordIndex] != match)
2273                        break;
2274                    wordIndex++;
2275                } while (true);
2276                wordMatch += len;
2277                if (*wordMatch == '\0')
2278                    break;
2279                wordIndex = 0;
2280            }
2281            if (secondMatch) {
2282                wordIndex = 1;
2283        foundDomainStart:
2284                chars += wordIndex;
2285                if (chars < end) {
2286                    ch = *chars;
2287                    if (ch != '.') {
2288                        if (IsDomainChar(ch))
2289                            goto nextDot;
2290                    } else if (chars + 1 < end && IsDomainChar(chars[1]))
2291                        goto nextDot;
2292                }
2293                // found domain. Search backwards from '@' for beginning of email address
2294                s->mEndResult = chars - start;
2295                chars = atLocation;
2296                if (chars <= start)
2297                    goto nextAt;
2298                ch = *--chars;
2299                if (ch == '.')
2300                    goto nextAt; // mailbox can't end in period
2301                do {
2302                    if (IsMailboxChar(ch) == false) {
2303                        chars++;
2304                        break;
2305                    }
2306                    if (chars == start)
2307                        break;
2308                    ch = *--chars;
2309                } while (true);
2310                UChar firstChar = *chars;
2311                if (firstChar == '.' || firstChar == '@') // mailbox can't start with period or be empty
2312                    goto nextAt;
2313                s->mStartResult = chars - start;
2314                return FOUND_COMPLETE;
2315            }
2316    nextDot:
2317            ;
2318        }
2319nextAt:
2320        chars = atLocation + 1;
2321    }
2322    return FOUND_NONE;
2323}
2324
2325#define PHONE_PATTERN "(200) /-.\\ 100 -. 0000" // poor man's regex: parens optional, any one of punct, digit smallest allowed
2326
2327CacheBuilder::FoundState CacheBuilder::FindPartialNumber(const UChar* chars, unsigned length,
2328    FindState* s)
2329{
2330    char* pattern = s->mPattern;
2331    UChar* store = s->mStorePtr;
2332    const UChar* start = chars;
2333    const UChar* end = chars + length;
2334    const UChar* lastDigit = NULL;
2335    do {
2336        bool initialized = s->mInitialized;
2337        while (chars < end) {
2338            if (initialized == false) {
2339                s->mBackTwo = s->mBackOne;
2340                s->mBackOne = s->mCurrent;
2341            }
2342            UChar ch = s->mCurrent = *chars;
2343            do {
2344                char patternChar = *pattern;
2345                switch (patternChar) {
2346                    case '2':
2347                            if (initialized == false) {
2348                                s->mStartResult = chars - start;
2349                                initialized = true;
2350                            }
2351                    case '0':
2352                    case '1':
2353                        if (ch < patternChar || ch > '9')
2354                            goto resetPattern;
2355                        *store++ = ch;
2356                        pattern++;
2357                        lastDigit = chars;
2358                        goto nextChar;
2359                    case '\0':
2360                        if (WTF::isASCIIDigit(ch) == false) {
2361                            *store = '\0';
2362                            goto checkMatch;
2363                        }
2364                        goto resetPattern;
2365                    case ' ':
2366                        if (ch == patternChar)
2367                            goto nextChar;
2368                        break;
2369                    case '(':
2370                        if (ch == patternChar) {
2371                            s->mStartResult = chars - start;
2372                            initialized = true;
2373                            s->mOpenParen = true;
2374                        }
2375                        goto commonPunctuation;
2376                    case ')':
2377                        if ((ch == patternChar) ^ s->mOpenParen)
2378                            goto resetPattern;
2379                    default:
2380                    commonPunctuation:
2381                        if (ch == patternChar) {
2382                            pattern++;
2383                            goto nextChar;
2384                        }
2385                }
2386            } while (++pattern); // never false
2387    nextChar:
2388            chars++;
2389        }
2390        break;
2391resetPattern:
2392        if (s->mContinuationNode)
2393            return FOUND_NONE;
2394        FindResetNumber(s);
2395        pattern = s->mPattern;
2396        store = s->mStorePtr;
2397    } while (++chars < end);
2398checkMatch:
2399    if (WTF::isASCIIDigit(s->mBackOne != '1' ? s->mBackOne : s->mBackTwo))
2400        return FOUND_NONE;
2401    *store = '\0';
2402    s->mStorePtr = store;
2403    s->mPattern = pattern;
2404    s->mEndResult = lastDigit - start + 1;
2405    char pState = pattern[0];
2406    return pState == '\0' ? FOUND_COMPLETE : pState == '(' || (WTF::isASCIIDigit(pState) && WTF::isASCIIDigit(pattern[-1])) ?
2407        FOUND_NONE : FOUND_PARTIAL;
2408}
2409
2410CacheBuilder::FoundState CacheBuilder::FindPhoneNumber(const UChar* chars, unsigned length,
2411    int* start, int* end)
2412{
2413    FindState state;
2414    FindReset(&state);
2415    FoundState result = FindPartialNumber(chars, length, &state);
2416    *start = state.mStartResult;
2417    *end = state.mEndResult;
2418    return result;
2419}
2420
2421void CacheBuilder::FindReset(FindState* state)
2422{
2423    memset(state, 0, sizeof(FindState));
2424    state->mCurrent = ' ';
2425    FindResetNumber(state);
2426}
2427
2428void CacheBuilder::FindResetNumber(FindState* state)
2429{
2430    state->mOpenParen = false;
2431    state->mPattern = (char*) PHONE_PATTERN;
2432    state->mStorePtr = state->mStore;
2433}
2434
2435IntRect CacheBuilder::getAreaRect(const HTMLAreaElement* area)
2436{
2437    Node* node = area->document();
2438    while ((node = node->traverseNextNode()) != NULL) {
2439        RenderObject* renderer = node->renderer();
2440        if (renderer && renderer->isRenderImage()) {
2441            RenderImage* image = static_cast<RenderImage*>(renderer);
2442            HTMLMapElement* map = image->imageMap();
2443            if (map) {
2444                Node* n;
2445                for (n = map->firstChild(); n;
2446                        n = n->traverseNextNode(map)) {
2447                    if (n == area) {
2448                        if (area->isDefault())
2449                            return image->absoluteBoundingBoxRect();
2450                        return area->getRect(image);
2451                    }
2452                }
2453            }
2454        }
2455    }
2456    return IntRect();
2457}
2458
2459void CacheBuilder::GetGlobalOffset(Node* node, int* x, int * y)
2460{
2461    GetGlobalOffset(node->document()->frame(), x, y);
2462}
2463
2464void CacheBuilder::GetGlobalOffset(Frame* frame, int* x, int* y)
2465{
2466//    TIMER_PROBE(__FUNCTION__);
2467    ASSERT(x);
2468    ASSERT(y);
2469    *x = 0;
2470    *y = 0;
2471    if (!frame->view())
2472        return;
2473    Frame* parent;
2474    while ((parent = frame->tree()->parent()) != NULL) {
2475        const WebCore::IntRect& rect = frame->view()->platformWidget()->getBounds();
2476        *x += rect.x();
2477        *y += rect.y();
2478        frame = parent;
2479    }
2480 //   TIMER_PROBE_END();
2481}
2482
2483Frame* CacheBuilder::HasFrame(Node* node)
2484{
2485    RenderObject* renderer = node->renderer();
2486    if (renderer == NULL)
2487        return NULL;
2488    if (renderer->isWidget() == false)
2489        return NULL;
2490    Widget* widget = static_cast<RenderWidget*>(renderer)->widget();
2491    if (widget == NULL)
2492        return NULL;
2493    if (widget->isFrameView() == false)
2494        return NULL;
2495    return static_cast<FrameView*>(widget)->frame();
2496}
2497
2498bool CacheBuilder::HasOverOrOut(Node* node)
2499{
2500    // eventNames are thread-local data, I avoid using 'static' variable here.
2501    AtomicString eventTypes[2] = {
2502        eventNames().mouseoverEvent,
2503        eventNames().mouseoutEvent
2504    };
2505
2506    return NodeHasEventListeners(node, eventTypes, 2);
2507}
2508
2509bool CacheBuilder::HasTriggerEvent(Node* node)
2510{
2511    AtomicString eventTypes[5] = {
2512        eventNames().clickEvent,
2513        eventNames().mousedownEvent,
2514        eventNames().mouseupEvent,
2515        eventNames().keydownEvent,
2516        eventNames().keyupEvent
2517    };
2518
2519    return NodeHasEventListeners(node, eventTypes, 5);
2520}
2521
2522// #define EMAIL_PATTERN "x@y.d" // where 'x' is letters, numbers, and '-', '.', '_' ; 'y' is 'x' without the underscore, and 'd' is a valid domain
2523//  - 0x2D . 0x2E 0-9 0x30-39 A-Z 0x41-5A  _ 0x5F a-z 0x61-7A
2524
2525bool CacheBuilder::IsDomainChar(UChar ch)
2526{
2527    static const unsigned body[] = {0x03ff6000, 0x07fffffe, 0x07fffffe}; // 0-9 . - A-Z a-z
2528    ch -= 0x20;
2529    if (ch > 'z' - 0x20)
2530        return false;
2531    return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0;
2532}
2533
2534bool CacheBuilder::isFocusableText(NodeWalk* walk, bool more, Node* node,
2535    CachedNodeType* type, String* exported) const
2536{
2537    Text* textNode = static_cast<Text*>(node);
2538    StringImpl* string = textNode->dataImpl();
2539    const UChar* baseChars = string->characters();
2540//    const UChar* originalBase = baseChars;
2541    int length = string->length();
2542    int index = 0;
2543    while (index < length && isUnicodeSpace(baseChars[index]))
2544        index++;
2545    if (index >= length)
2546        return false;
2547    if (more == false) {
2548        walk->mStart = 0;
2549        walk->mEnd = 0;
2550        walk->mFinalNode = node;
2551        walk->mLastInline = NULL;
2552    }
2553    // starting with this node, search forward for email, phone number, and address
2554    // if any of the three is found, track it so that the remaining can be looked for later
2555    FoundState state = FOUND_NONE;
2556    RenderText* renderer = (RenderText*) node->renderer();
2557    bool foundBetter = false;
2558    InlineTextBox* baseInline = walk->mLastInline != NULL ? walk->mLastInline :
2559        renderer->firstTextBox();
2560    if (baseInline == NULL)
2561        return false;
2562    int start = walk->mEnd;
2563    InlineTextBox* saveInline;
2564    int baseStart, firstStart = start;
2565    saveInline = baseInline;
2566    baseStart = start;
2567    for (CachedNodeType checkType = ADDRESS_CACHEDNODETYPE;
2568        checkType <= PHONE_CACHEDNODETYPE;
2569        checkType = static_cast<CachedNodeType>(checkType + 1))
2570    {
2571        if ((1 << (checkType - 1) & mAllowableTypes) == 0)
2572            continue;
2573        InlineTextBox* inlineTextBox = baseInline;
2574        FindState findState;
2575        FindReset(&findState);
2576        start = baseStart;
2577        if (checkType == ADDRESS_CACHEDNODETYPE) {
2578            findState.mBases[0] = baseChars;
2579            findState.mWords[0] = baseChars + start;
2580            findState.mStarts[0] = baseChars + start;
2581        }
2582        Node* lastPartialNode = NULL;
2583        int lastPartialEnd = -1;
2584        bool lastPartialMore = false;
2585        bool firstPartial = true;
2586        InlineTextBox* lastPartialInline = NULL;
2587        do {
2588            do {
2589                const UChar* chars = baseChars + start;
2590                length = inlineTextBox == NULL ? 0 :
2591                    inlineTextBox->end() - start + 1;
2592                bool wasInitialized = findState.mInitialized;
2593                switch (checkType) {
2594                    case ADDRESS_CACHEDNODETYPE:
2595                        state = FindPartialAddress(baseChars, chars, length, &findState);
2596                    break;
2597                    case EMAIL_CACHEDNODETYPE:
2598                        state = FindPartialEMail(chars, length, &findState);
2599                    break;
2600                    case PHONE_CACHEDNODETYPE:
2601                        state = FindPartialNumber(chars, length, &findState);
2602                    break;
2603                    default:
2604                        ASSERT(0);
2605                }
2606                findState.mInitialized = state != FOUND_NONE;
2607                if (wasInitialized != findState.mInitialized)
2608                    firstStart = start;
2609                if (state == FOUND_PARTIAL) {
2610                    lastPartialNode = node;
2611                    lastPartialEnd = findState.mEndResult + start;
2612                    lastPartialMore = firstPartial &&
2613                        lastPartialEnd < (int) string->length();
2614                    firstPartial = false;
2615                    lastPartialInline = inlineTextBox;
2616                    findState.mContinuationNode = true;
2617                } else if (state == FOUND_COMPLETE) {
2618                    if (foundBetter == false || walk->mStart > findState.mStartResult) {
2619                        walk->mStart = findState.mStartResult + firstStart;
2620                        if (findState.mEndResult > 0) {
2621                            walk->mFinalNode = node;
2622                            walk->mEnd = findState.mEndResult + start;
2623                            walk->mMore = node == textNode &&
2624                                walk->mEnd < (int) string->length();
2625                            walk->mLastInline = inlineTextBox;
2626                        } else {
2627                            walk->mFinalNode = lastPartialNode;
2628                            walk->mEnd = lastPartialEnd;
2629                            walk->mMore = lastPartialMore;
2630                            walk->mLastInline = lastPartialInline;
2631                        }
2632                        *type = checkType;
2633                        if (checkType == PHONE_CACHEDNODETYPE) {
2634                            const UChar* store = findState.mStore;
2635                            *exported = String(store);
2636                        } else {
2637                            Node* temp = textNode;
2638                            length = 1;
2639                            start = walk->mStart;
2640                            exported->truncate(0);
2641                            do {
2642                                Text* tempText = static_cast<Text*>(temp);
2643                                StringImpl* string = tempText->dataImpl();
2644                                int end = tempText == walk->mFinalNode ?
2645                                    walk->mEnd : string->length();
2646                                exported->append(String(string->substring(
2647                                    start, end - start)));
2648                                ASSERT(end > start);
2649                                length += end - start + 1;
2650                                if (temp == walk->mFinalNode)
2651                                    break;
2652                                start = 0;
2653                                do {
2654                                    temp = temp->traverseNextNode();
2655                                    ASSERT(temp);
2656                                } while (temp->isTextNode() == false);
2657                                // add a space in between text nodes to avoid
2658                                // words collapsing together
2659                                exported->append(" ");
2660                            } while (true);
2661                        }
2662                        foundBetter = true;
2663                    }
2664                    goto tryNextCheckType;
2665                } else if (findState.mContinuationNode)
2666                    break;
2667                if (inlineTextBox == NULL)
2668                    break;
2669                inlineTextBox = inlineTextBox->nextTextBox();
2670                if (inlineTextBox == NULL)
2671                    break;
2672                start = inlineTextBox->start();
2673                if (state == FOUND_PARTIAL && node == textNode)
2674                    findState.mContinuationNode = false;
2675            } while (true);
2676            if (state == FOUND_NONE)
2677                break;
2678            // search for next text node, if any
2679            Text* nextNode;
2680            do {
2681                do {
2682                    do {
2683                        node = node->traverseNextNode();
2684                        if (node == NULL || node->hasTagName(HTMLNames::aTag)
2685                                || node->hasTagName(HTMLNames::inputTag)
2686                                || node->hasTagName(HTMLNames::textareaTag)) {
2687                            if (state == FOUND_PARTIAL &&
2688                                    checkType == ADDRESS_CACHEDNODETYPE &&
2689                                    findState.mProgress == ZIP_CODE &&
2690                                    findState.mNumberCount == 0) {
2691                                baseChars = NULL;
2692                                inlineTextBox = NULL;
2693                                start = 0;
2694                                findState.mProgress = FIND_STREET;
2695                                goto finalNode;
2696                            }
2697                            goto tryNextCheckType;
2698                        }
2699                    } while (node->isTextNode() == false);
2700                    nextNode = static_cast<Text*>(node);
2701                    renderer = (RenderText*) nextNode->renderer();
2702                } while (renderer == NULL);
2703                baseInline = renderer->firstTextBox();
2704            } while (baseInline == NULL);
2705            string = nextNode->dataImpl();
2706            baseChars = string->characters();
2707            inlineTextBox = baseInline;
2708            start = inlineTextBox->start();
2709        finalNode:
2710            findState.mEndResult = 0;
2711        } while (true);
2712tryNextCheckType:
2713        node = textNode;
2714        baseInline = saveInline;
2715        string = textNode->dataImpl();
2716        baseChars = string->characters();
2717    }
2718    if (foundBetter) {
2719        CachedNodeType temp = *type;
2720        switch (temp) {
2721            case ADDRESS_CACHEDNODETYPE: {
2722                static const char geoString[] = "geo:0,0?q=";
2723                exported->insert(String(geoString), 0);
2724                int index = sizeof(geoString) - 1;
2725                String escapedComma("%2C");
2726                while ((index = exported->find(',', index)) >= 0)
2727                    exported->replace(index, 1, escapedComma);
2728                } break;
2729            case EMAIL_CACHEDNODETYPE:
2730                exported->insert(WebCore::String("mailto:"), 0);
2731                break;
2732            case PHONE_CACHEDNODETYPE:
2733                exported->insert(WebCore::String("tel:"), 0);
2734                break;
2735            default:
2736                break;
2737        }
2738        return true;
2739    }
2740noTextMatch:
2741    walk->reset();
2742    return false;
2743}
2744
2745bool CacheBuilder::IsMailboxChar(UChar ch)
2746{
2747    static const unsigned body[] = {0x03ff6000, 0x87fffffe, 0x07fffffe}; // 0-9 . - A-Z _ a-z
2748    ch -= 0x20;
2749    if (ch > 'z' - 0x20)
2750        return false;
2751    return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0;
2752}
2753
2754bool CacheBuilder::setData(CachedFrame* cachedFrame)
2755{
2756    Frame* frame = FrameAnd(this);
2757    Document* doc = frame->document();
2758    if (doc == NULL)
2759        return false;
2760    RenderObject* renderer = doc->renderer();
2761    if (renderer == NULL)
2762        return false;
2763    RenderLayer* layer = renderer->enclosingLayer();
2764    if (layer == NULL)
2765        return false;
2766    if (layer->width() == 0 || layer->height() == 0)
2767        return false;
2768    if (!frame->view())
2769        return false;
2770    int x, y;
2771    GetGlobalOffset(frame, &x, &y);
2772    WebCore::IntRect viewBounds = frame->view()->platformWidget()->getBounds();
2773    if ((x | y) != 0)
2774        viewBounds.setLocation(WebCore::IntPoint(x, y));
2775    cachedFrame->setLocalViewBounds(viewBounds);
2776    cachedFrame->setContentsSize(layer->width(), layer->height());
2777    if (cachedFrame->childCount() == 0)
2778        return true;
2779    CachedFrame* lastCachedFrame = cachedFrame->lastChild();
2780    cachedFrame = cachedFrame->firstChild();
2781    do {
2782        CacheBuilder* cacheBuilder = Builder((Frame* )cachedFrame->framePointer());
2783        cacheBuilder->setData(cachedFrame);
2784    } while (cachedFrame++ != lastCachedFrame);
2785    return true;
2786}
2787
2788#if USE(ACCELERATED_COMPOSITING)
2789void CacheBuilder::TrackLayer(WTF::Vector<LayerTracker>& layerTracker,
2790    RenderObject* nodeRenderer, Node* lastChild, int offsetX, int offsetY)
2791{
2792    RenderLayer* layer = toRenderBoxModelObject(nodeRenderer)->layer();
2793    RenderLayerBacking* back = layer->backing();
2794    if (!back)
2795        return;
2796    GraphicsLayerAndroid* grLayer = static_cast
2797        <GraphicsLayerAndroid*>(back->graphicsLayer());
2798    if (!grLayer)
2799        return;
2800    LayerAndroid* aLayer = grLayer->contentLayer();
2801    if (!aLayer)
2802        return;
2803    layerTracker.grow(layerTracker.size() + 1);
2804    LayerTracker& indexTracker = layerTracker.last();
2805    indexTracker.mLayer = aLayer;
2806    indexTracker.mBounds = nodeRenderer->absoluteBoundingBoxRect();
2807    indexTracker.mBounds.move(offsetX, offsetY);
2808    indexTracker.mLastChild = lastChild ? OneAfter(lastChild) : 0;
2809    DBG_NAV_LOGD("layer=%p [%d] bounds=(%d,%d,w=%d,h=%d)", aLayer,
2810        aLayer->uniqueId(), indexTracker.mBounds.x(), indexTracker.mBounds.y(),
2811        indexTracker.mBounds.width(), indexTracker.mBounds.height());
2812}
2813#endif
2814
2815bool CacheBuilder::validNode(Frame* startFrame, void* matchFrame,
2816        void* matchNode)
2817{
2818    if (matchFrame == startFrame) {
2819        if (matchNode == NULL)
2820            return true;
2821        Node* node = startFrame->document();
2822        while (node != NULL) {
2823            if (node == matchNode) {
2824                const IntRect& rect = node->hasTagName(HTMLNames::areaTag) ?
2825                    getAreaRect(static_cast<HTMLAreaElement*>(node)) : node->getRect();
2826                // Consider nodes with empty rects that are not at the origin
2827                // to be valid, since news.google.com has valid nodes like this
2828                if (rect.x() == 0 && rect.y() == 0 && rect.isEmpty())
2829                    return false;
2830                return true;
2831            }
2832            node = node->traverseNextNode();
2833        }
2834        DBG_NAV_LOGD("frame=%p valid node=%p invalid\n", matchFrame, matchNode);
2835        return false;
2836    }
2837    Frame* child = startFrame->tree()->firstChild();
2838    while (child) {
2839        bool result = validNode(child, matchFrame, matchNode);
2840        if (result)
2841            return result;
2842        child = child->tree()->nextSibling();
2843    }
2844#if DEBUG_NAV_UI
2845    if (startFrame->tree()->parent() == NULL)
2846        DBG_NAV_LOGD("frame=%p node=%p false\n", matchFrame, matchNode);
2847#endif
2848    return false;
2849}
2850
2851static int Area(const IntRect& rect)
2852{
2853    return rect.width() * rect.height();
2854}
2855
2856bool CacheBuilder::AddPartRect(IntRect& bounds, int x, int y,
2857    WTF::Vector<IntRect>* result, IntRect* focusBounds)
2858{
2859    if (bounds.isEmpty())
2860        return true;
2861    bounds.move(x, y);
2862    if (bounds.right() <= 0 || bounds.bottom() <= 0)
2863        return true;
2864    IntRect* work = result->begin() - 1;
2865    IntRect* end = result->end();
2866    while (++work < end) {
2867        if (work->contains(bounds))
2868            return true;
2869        if (bounds.contains(*work)) {
2870            *work = bounds;
2871            focusBounds->unite(bounds);
2872            return true;
2873        }
2874        if ((bounds.x() != work->x() || bounds.width() != work->width()) &&
2875               (bounds.y() != work->y() || bounds.height() != work->height()))
2876            continue;
2877        IntRect test = *work;
2878        test.unite(bounds);
2879        if (Area(test) > Area(*work) + Area(bounds))
2880            continue;
2881        *work = test;
2882        focusBounds->unite(bounds);
2883        return true;
2884    }
2885    if (result->size() >= MAXIMUM_FOCUS_RING_COUNT)
2886        return false;
2887    result->append(bounds);
2888    if (focusBounds->isEmpty())
2889        *focusBounds = bounds;
2890    else
2891        focusBounds->unite(bounds);
2892    return true;
2893}
2894
2895bool CacheBuilder::ConstructPartRects(Node* node, const IntRect& bounds,
2896    IntRect* focusBounds, int x, int y, WTF::Vector<IntRect>* result)
2897{
2898    WTF::Vector<ClipColumnTracker> clipTracker(1);
2899    ClipColumnTracker* baseTracker = clipTracker.data(); // sentinel
2900    bzero(baseTracker, sizeof(ClipColumnTracker));
2901    if (node->hasChildNodes() && node->hasTagName(HTMLNames::buttonTag) == false
2902            && node->hasTagName(HTMLNames::selectTag) == false) {
2903        // collect all text rects from first to last child
2904        Node* test = node->firstChild();
2905        Node* last = NULL;
2906        Node* prior = node;
2907        while ((prior = prior->lastChild()) != NULL)
2908            last = prior;
2909        ASSERT(last != NULL);
2910        bool nodeIsAnchor = node->hasTagName(HTMLNames::aTag);
2911        do {
2912            do {
2913                const ClipColumnTracker* lastClip = &clipTracker.last();
2914                if (test != lastClip->mLastChild)
2915                    break;
2916                clipTracker.removeLast();
2917            } while (true);
2918            RenderObject* renderer = test->renderer();
2919            if (renderer == NULL)
2920                continue;
2921            EVisibility vis = renderer->style()->visibility();
2922            if (vis == HIDDEN)
2923                continue;
2924            if (test->isTextNode()) {
2925                RenderText* renderText = (RenderText*) renderer;
2926                InlineTextBox *textBox = renderText->firstTextBox();
2927                if (textBox == NULL)
2928                    continue;
2929                bool hasClip = renderer->hasOverflowClip();
2930                size_t clipIndex = clipTracker.size();
2931                IntRect clipBounds = IntRect(0, 0, INT_MAX, INT_MAX);
2932                if (hasClip || --clipIndex > 0) {
2933                    clipBounds = hasClip ? renderer->absoluteBoundingBoxRect() :
2934                        clipTracker.at(clipIndex).mBounds; // x, y fixup done by ConstructTextRect
2935                }
2936                if (ConstructTextRect((Text*) test, textBox, 0, INT_MAX,
2937                        x, y, focusBounds, clipBounds, result) == false) {
2938                    return false;
2939                }
2940                continue;
2941            }
2942            if (test->hasTagName(HTMLNames::imgTag)) {
2943                IntRect bounds = test->getRect();
2944                if (AddPartRect(bounds, x, y, result, focusBounds) == false)
2945                    return false;
2946                continue;
2947            }
2948            if (renderer->hasOverflowClip() == false) {
2949                if (nodeIsAnchor && test->hasTagName(HTMLNames::divTag)) {
2950                    IntRect bounds = renderer->absoluteBoundingBoxRect();  // x, y fixup done by AddPartRect
2951                    int left = bounds.x() + ((RenderBox*)renderer)->paddingLeft()
2952                        + ((RenderBox*)renderer)->borderLeft();
2953                    int top = bounds.y() + ((RenderBox*)renderer)->paddingTop()
2954                        + ((RenderBox*)renderer)->borderTop();
2955                    int right = bounds.right() - ((RenderBox*)renderer)->paddingRight()
2956                        - ((RenderBox*)renderer)->borderRight();
2957                    int bottom = bounds.bottom() - ((RenderBox*)renderer)->paddingBottom()
2958                        - ((RenderBox*)renderer)->borderBottom();
2959                    if (left >= right || top >= bottom)
2960                        continue;
2961                    bounds = IntRect(left, top, right - left, bottom - top);
2962                    if (AddPartRect(bounds, x, y, result, focusBounds) == false)
2963                        return false;
2964                }
2965                continue;
2966            }
2967            Node* lastChild = test->lastChild();
2968            if (lastChild == NULL)
2969                continue;
2970            clipTracker.grow(clipTracker.size() + 1);
2971            ClipColumnTracker& clip = clipTracker.last();
2972            clip.mBounds = renderer->absoluteBoundingBoxRect(); // x, y fixup done by ConstructTextRect
2973            clip.mLastChild = OneAfter(lastChild);
2974            clip.mNode = test;
2975        } while (test != last && (test = test->traverseNextNode()) != NULL);
2976    }
2977    if (result->size() == 0 || focusBounds->width() < MINIMUM_FOCUSABLE_WIDTH
2978            || focusBounds->height() < MINIMUM_FOCUSABLE_HEIGHT) {
2979        if (bounds.width() < MINIMUM_FOCUSABLE_WIDTH)
2980            return false;
2981        if (bounds.height() < MINIMUM_FOCUSABLE_HEIGHT)
2982            return false;
2983        result->append(bounds);
2984        *focusBounds = bounds;
2985    }
2986    return true;
2987}
2988
2989static inline bool isNotSpace(UChar c)
2990{
2991    return c <= 0xA0 ? isUnicodeSpace(c) == false :
2992        WTF::Unicode::direction(c) != WTF::Unicode::WhiteSpaceNeutral;
2993}
2994
2995bool CacheBuilder::ConstructTextRect(Text* textNode,
2996    InlineTextBox* textBox, int start, int relEnd, int x, int y,
2997    IntRect* focusBounds, const IntRect& clipBounds, WTF::Vector<IntRect>* result)
2998{
2999    RenderText* renderText = (RenderText*) textNode->renderer();
3000    EVisibility vis = renderText->style()->visibility();
3001    StringImpl* string = textNode->dataImpl();
3002    const UChar* chars = string->characters();
3003    FloatPoint pt = renderText->localToAbsolute();
3004    do {
3005        int textBoxStart = textBox->start();
3006        int textBoxEnd = textBoxStart + textBox->len();
3007        if (textBoxEnd <= start)
3008            continue;
3009        if (textBoxEnd > relEnd)
3010            textBoxEnd = relEnd;
3011        IntRect bounds = textBox->selectionRect((int) pt.x(), (int) pt.y(),
3012            start, textBoxEnd);
3013        bounds.intersect(clipBounds);
3014        if (bounds.isEmpty())
3015            continue;
3016        bool drawable = false;
3017        for (int index = start; index < textBoxEnd; index++)
3018            if ((drawable |= isNotSpace(chars[index])) != false)
3019                break;
3020        if (drawable && vis != HIDDEN) {
3021            if (AddPartRect(bounds, x, y, result, focusBounds) == false)
3022                return false;
3023        }
3024        if (textBoxEnd == relEnd)
3025            break;
3026    } while ((textBox = textBox->nextTextBox()) != NULL);
3027    return true;
3028}
3029
3030bool CacheBuilder::ConstructTextRects(Text* node, int start,
3031    Text* last, int end, int x, int y, IntRect* focusBounds,
3032    const IntRect& clipBounds, WTF::Vector<IntRect>* result)
3033{
3034    result->clear();
3035    *focusBounds = IntRect(0, 0, 0, 0);
3036    do {
3037        RenderText* renderText = (RenderText*) node->renderer();
3038        int relEnd = node == last ? end : renderText->textLength();
3039        InlineTextBox *textBox = renderText->firstTextBox();
3040        if (textBox != NULL) {
3041            do {
3042                if ((int) textBox->end() >= start)
3043                    break;
3044            } while ((textBox = textBox->nextTextBox()) != NULL);
3045            if (textBox && ConstructTextRect(node, textBox, start, relEnd,
3046                    x, y, focusBounds, clipBounds, result) == false)
3047                return false;
3048        }
3049        start = 0;
3050        do {
3051            if (node == last)
3052                return true;
3053            node = (Text*) node->traverseNextNode();
3054            ASSERT(node != NULL);
3055        } while (node->isTextNode() == false || node->renderer() == NULL);
3056    } while (true);
3057}
3058
3059}
3060