Source/WebKit/android/nav/CacheBuilder.cpp

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