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.setSpellcheck(input->spellcheck());
1250                 cachedInput.setFormPointer(input->form());
1251                 cachedInput.setIsTextField(true);
1252                 exported = input->value().threadsafeCopy();
1253                 cachedInput.setMaxLength(input->maxLength());
1254                 cachedInput.setTypeFromElement(input);
1255     // If this does not need to be threadsafe, we can use crossThreadString().
1256     // See http://trac.webkit.org/changeset/49160.
1257                 cachedInput.setName(input->name().string().threadsafeCopy());
1258     // can't detect if this is drawn on top (example: deviant.com login parts)
1259                 isUnclipped = isTransparent;
1260             } else if (input->isInputTypeHidden())
1261                 continue;
1262             else if (input->isRadioButton() || input->isCheckbox())
1263                 isTransparent = false;
1264         } else if (node->hasTagName(HTMLNames::textareaTag)) {
1265             HTMLTextAreaElement* area = static_cast<HTMLTextAreaElement*>(node);
1266             if (area->readOnly())
1267                 continue;
1268             cachedInput.init();
1269             type = TEXT_INPUT_CACHEDNODETYPE;
1270             cachedInput.setFormPointer(area->form());
1271             cachedInput.setIsTextArea(true);
1272             exported = area->value().threadsafeCopy();
1273         } else if (node->hasTagName(HTMLNames::aTag)) {
1274             const HTMLAnchorElement* anchorNode =
1275                 (const HTMLAnchorElement*) node;
1276             if (!anchorNode->isFocusable() && !HasTriggerEvent(node))
1277                 continue;
1278             if (node->disabled())
1279                 continue;
1280             hasMouseOver = NodeHasEventListeners(node, &eventNames().mouseoverEvent, 1);
1281             type = ANCHOR_CACHEDNODETYPE;
1282             KURL href = anchorNode->href();
1283             if (!href.isEmpty() && !WebCore::protocolIsJavaScript(href.string()))
1284                 // Set the exported string for all non-javascript anchors.
1285                 exported = href.string().threadsafeCopy();
1286         } else if (node->hasTagName(HTMLNames::selectTag)) {
1287             type = SELECT_CACHEDNODETYPE;
1288         }
1289         if (type == TEXT_INPUT_CACHEDNODETYPE) {
1290             RenderTextControl* renderText =
1291                 static_cast<RenderTextControl*>(nodeRenderer);
1292             if (isFocus)
1293                 cachedRoot->setSelection(renderText->selectionStart(), renderText->selectionEnd());
1294             // FIXME: Are we sure there will always be a style and font, and it's correct?
1295             RenderStyle* style = nodeRenderer->style();
1296             if (style) {
1297                 isUnclipped |= !style->hasAppearance();
1298                 int lineHeight = -1;
1299                 Length lineHeightLength = style->lineHeight();
1300                 // If the lineHeight is negative, WebTextView will calculate it
1301                 // based on the text size, using the Paint.
1302                 // See RenderStyle.computedLineHeight.
1303                 if (lineHeightLength.isPositive())
1304                     lineHeight = style->computedLineHeight();
1305                 cachedInput.setLineHeight(lineHeight);
1306                 cachedInput.setTextSize(style->font().size());
1307                 cachedInput.setIsRtlText(style->direction() == RTL
1308                         || style->textAlign() == WebCore::RIGHT
1309                         || style->textAlign() == WebCore::WEBKIT_RIGHT);
1310             }
1311             cachedInput.setPaddingLeft(renderText->paddingLeft() + renderText->borderLeft());
1312             cachedInput.setPaddingTop(renderText->paddingTop() + renderText->borderTop());
1313             cachedInput.setPaddingRight(renderText->paddingRight() + renderText->borderRight());
1314             cachedInput.setPaddingBottom(renderText->paddingBottom() + renderText->borderBottom());
1315         }
1316         takesFocus = true;
1317         bounds = absBounds;
1318         if (type != ANCHOR_CACHEDNODETYPE) {
1319             bool isFocusable = node->isKeyboardFocusable(NULL) ||
1320                 node->isMouseFocusable() || node->isFocusable();
1321             if (isFocusable == false) {
1322                 if (node->disabled())
1323                     continue;
1324                 bool overOrOut = HasOverOrOut(node);
1325                 bool hasTrigger = HasTriggerEvent(node);
1326                 if (overOrOut == false && hasTrigger == false)
1327                     continue;
1328                 takesFocus = hasTrigger;
1329             }
1330         }
1331         computeCursorRings = true;
1332     keepNode:
1333         cachedNode.init(node);
1334         if (computeCursorRings == false) {
1335             cachedNode.setBounds(bounds);
1336             cachedNode.mCursorRing.append(bounds);
1337         } else if (ConstructPartRects(node, bounds, &cachedNode.mBounds,
1338                 globalOffsetX, globalOffsetY, &cachedNode.mCursorRing,
1339                 &imageCount) == false)
1340             continue;
1341     keepTextNode:
1342         if (nodeRenderer) { // area tags' node->renderer() == 0
1343             RenderStyle* style = nodeRenderer->style();
1344             const void* styleDataPtr = style->ringData();
1345             // to save time, see if we're pointing to the same style data as before
1346             if (lastStyleDataPtr != styleDataPtr) {
1347                 lastStyleDataPtr = styleDataPtr;
1348                 cachedColor.setFillColor(style->ringFillColor());
1349                 cachedColor.setInnerWidth(style->ringInnerWidth());
1350                 cachedColor.setOuterWidth(style->ringOuterWidth());
1351                 cachedColor.setOutset(style->ringOutset());
1352                 cachedColor.setPressedInnerColor(style->ringPressedInnerColor());
1353                 cachedColor.setPressedOuterColor(style->ringPressedOuterColor());
1354                 cachedColor.setRadius(style->ringRadius());
1355                 cachedColor.setSelectedInnerColor(style->ringSelectedInnerColor());
1356                 cachedColor.setSelectedOuterColor(style->ringSelectedOuterColor());
1357                 int oldSize = colorTracker.size();
1358                 colorIndex = FindColorIndex(colorTracker, cachedColor);
1359                 if (colorIndex == oldSize)
1360                     cachedFrame->add(cachedColor);
1361             }
1362         } else
1363             colorIndex = 0;
1364         IntRect clip = hasClip ? bounds : absBounds;
1365         size_t clipIndex = clipTracker.size();
1366         if (clipTracker.last().mNode == node)
1367             clipIndex -= 1;
1368         while (--clipIndex > 0) {
1369             const ClipColumnTracker& clipTrack = clipTracker.at(clipIndex);
1370             if (clipTrack.mHasClip == false) {
1371                 adjustForColumns(clipTrack, &cachedNode, &absBounds, static_cast<RenderBlock*>(nodeRenderer));
1372                 continue;
1373             }
1374             const IntRect& parentClip = clipTrack.mBounds;
1375             if (hasClip == false && type == ANCHOR_CACHEDNODETYPE)
1376                 clip = parentClip;
1377             else
1378                 clip.intersect(parentClip);
1379             hasClip = true;
1380         }
1381         bool isInLayer = false;
1382 #if USE(ACCELERATED_COMPOSITING)
1383         // If this renderer has a composited parent layer (including itself),
1384         // add the node to the cached layer.
1385         // FIXME: does not work for area rects
1386         RenderLayer* enclosingLayer = nodeRenderer->enclosingLayer();
1387         if (enclosingLayer && enclosingLayer->enclosingCompositingLayer()) {
1388             LayerAndroid* layer = layerTracker.last().mLayer;
1389             if (layer) {
1390                 const IntRect& layerClip = layerTracker.last().mBounds;
1391                 if (!layerClip.isEmpty() && !cachedNode.clip(layerClip)) {
1392                     DBG_NAV_LOGD("skipped on layer clip %d", cacheIndex);
1393                     continue; // skip this node if outside of the clip
1394                 }
1395                 isInLayer = true;
1396                 isUnclipped = true; // assume that layers do not have occluded nodes
1397                 hasClip = false;
1398                 AddLayer(cachedFrame, cachedFrame->size(), layerClip.location(),
1399                          layer->uniqueId());
1400             }
1401         }
1402 #endif
1403         if (hasClip) {
1404             if (clip.isEmpty())
1405                 continue; // skip this node if clip prevents all drawing
1406             else if (cachedNode.clip(clip) == false)
1407                 continue; // skip this node if outside of the clip
1408         }
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         return false;
1481     }
1482     CachedNode* onlyChildCached = cachedFrame->lastNode();
1483     Node* onlyChild = (Node*) onlyChildCached->nodePointer();
1484     bool outerIsMouseMoveOnly =
1485         lastNode->isKeyboardFocusable(NULL) == false &&
1486         lastNode->isMouseFocusable() == false &&
1487         lastNode->isFocusable() == false &&
1488         HasOverOrOut(lastNode) == true &&
1489         HasTriggerEvent(lastNode) == false;
1490     if (onlyChildCached->parent() == lastCached)
1491         onlyChildCached->setParentIndex(lastCached->parentIndex());
1492     bool hasFocus = lastCached->isFocus() || onlyChildCached->isFocus();
1493     if (outerIsMouseMoveOnly || onlyChild->isKeyboardFocusable(NULL)
1494             || onlyChildCached->isPlugin()) {
1495         int index = lastCached->index();
1496         *lastCached = *onlyChildCached;
1497         lastCached->setIndex(index);
1498         CachedFrame* frame = cachedFrame->hasFrame(lastCached);
1499         if (frame)
1500             frame->setIndexInParent(index);
1501     }
1502     cachedFrame->removeLast();
1503     if (hasFocus)
1504         cachedRoot->setCachedFocus(cachedFrame, cachedFrame->lastNode());
1505     return true;
1506 }
1507
1508 Node* CacheBuilder::currentFocus() const
1509 {
1510     Frame* frame = FrameAnd(this);
1511     Document* doc = frame->document();
1512     if (doc != NULL) {
1513         Node* focus = doc->focusedNode();
1514         if (focus != NULL)
1515             return focus;
1516     }
1517     Frame* child = frame->tree()->firstChild();
1518     while (child) {
1519         CacheBuilder* cacheBuilder = Builder(child);
1520         Node* focus = cacheBuilder->currentFocus();
1521         if (focus)
1522             return focus;
1523         child = child->tree()->nextSibling();
1524     }
1525     return NULL;
1526 }
1527
1528 static bool strCharCmp(const char* matches, const UChar* test, int wordLength,
1529     int wordCount)
1530 {
1531     for (int index = 0; index < wordCount; index++) {
1532         for (int inner = 0; inner < wordLength; inner++) {
1533             if (matches[inner] != test[inner]) {
1534                 matches += wordLength;
1535                 goto next;
1536             }
1537         }
1538         return true;
1539 next:
1540         ;
1541     }
1542     return false;
1543 }
1544
1545 static const int stateTwoLetter[] = {
1546     0x02060c00,  // A followed by: [KLRSZ]
1547     0x00000000,  // B
1548     0x00084001,  // C followed by: [AOT]
1549     0x00000014,  // D followed by: [CE]
1550     0x00000000,  // E
1551     0x00001800,  // F followed by: [LM]
1552     0x00100001,  // G followed by: [AU]
1553     0x00000100,  // H followed by: [I]
1554     0x00002809,  // I followed by: [ADLN]
1555     0x00000000,  // J
1556     0x01040000,  // K followed by: [SY]
1557     0x00000001,  // L followed by: [A]
1558     0x000ce199,  // M followed by: [ADEHINOPST]
1559     0x0120129c,  // N followed by: [CDEHJMVY]
1560     0x00020480,  // O followed by: [HKR]
1561     0x00420001,  // P followed by: [ARW]
1562     0x00000000,  // Q
1563     0x00000100,  // R followed by: [I]
1564     0x0000000c,  // S followed by: [CD]
1565     0x00802000,  // T followed by: [NX]
1566     0x00080000,  // U followed by: [T]
1567     0x00080101,  // V followed by: [AIT]
1568     0x01200101   // W followed by: [AIVY]
1569 };
1570
1571 static const char firstIndex[] = {
1572      0,  5,  5,  8, 10, 10, 12, 14,
1573     15, 19, 19, 21, 22, 32, 40, 43,
1574     46, 46, 47, 49, 51, 52, 55, 59
1575 };
1576
1577 // from http://infolab.stanford.edu/~manku/bitcount/bitcount.html
1578 #define TWO(c)     (0x1u << (c))
1579 #define MASK(c)    (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
1580 #define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
1581
1582 int bitcount (unsigned int n)
1583 {
1584     n = COUNT(n, 0);
1585     n = COUNT(n, 1);
1586     n = COUNT(n, 2);
1587     n = COUNT(n, 3);
1588     return COUNT(n, 4);
1589 }
1590
1591 #undef TWO
1592 #undef MASK
1593 #undef COUNT
1594
1595 static bool isUnicodeSpace(UChar ch)
1596 {
1597     return ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r' || ch == 0xa0;
1598 }
1599
1600 static bool validZip(int stateIndex, const UChar* zipPtr)
1601 {
1602     static const struct {
1603         char mLow;
1604         char mHigh;
1605         char mException1;
1606         char mException2;
1607     } zipRange[] = {
1608         { 99, 99, -1, -1 }, // AK Alaska
1609         { 35, 36, -1, -1 }, // AL Alabama
1610         { 71, 72, -1, -1 }, // AR Arkansas
1611         { 96, 96, -1, -1 }, // AS American Samoa
1612         { 85, 86, -1, -1 }, // AZ Arizona
1613         { 90, 96, -1, -1 }, // CA California
1614         { 80, 81, -1, -1 }, // CO Colorado
1615         {  6,  6, -1, -1 }, // CT Connecticut
1616         { 20, 20, -1, -1 }, // DC District of Columbia
1617         { 19, 19, -1, -1 }, // DE Delaware
1618         { 32, 34, -1, -1 }, // FL Florida
1619         { 96, 96, -1, -1 }, // FM Federated States of Micronesia
1620         { 30, 31, -1, -1 }, // GA Georgia
1621         { 96, 96, -1, -1 }, // GU Guam
1622         { 96, 96, -1, -1 }, // HI Hawaii
1623         { 50, 52, -1, -1 }, // IA Iowa
1624         { 83, 83, -1, -1 }, // ID Idaho
1625         { 60, 62, -1, -1 }, // IL Illinois
1626         { 46, 47, -1, -1 }, // IN Indiana
1627         { 66, 67, 73, -1 }, // KS Kansas
1628         { 40, 42, -1, -1 }, // KY Kentucky
1629         { 70, 71, -1, -1 }, // LA Louisiana
1630         {  1,  2, -1, -1 }, // MA Massachusetts
1631         { 20, 21, -1, -1 }, // MD Maryland
1632         {  3,  4, -1, -1 }, // ME Maine
1633         { 96, 96, -1, -1 }, // MH Marshall Islands
1634         { 48, 49, -1, -1 }, // MI Michigan
1635         { 55, 56, -1, -1 }, // MN Minnesota
1636         { 63, 65, -1, -1 }, // MO Missouri
1637         { 96, 96, -1, -1 }, // MP Northern Mariana Islands
1638         { 38, 39, -1, -1 }, // MS Mississippi
1639         { 55, 56, -1, -1 }, // MT Montana
1640         { 27, 28, -1, -1 }, // NC North Carolina
1641         { 58, 58, -1, -1 }, // ND North Dakota
1642         { 68, 69, -1, -1 }, // NE Nebraska
1643         {  3,  4, -1, -1 }, // NH New Hampshire
1644         {  7,  8, -1, -1 }, // NJ New Jersey
1645         { 87, 88, 86, -1 }, // NM New Mexico
1646         { 88, 89, 96, -1 }, // NV Nevada
1647         { 10, 14,  0,  6 }, // NY New York
1648         { 43, 45, -1, -1 }, // OH Ohio
1649         { 73, 74, -1, -1 }, // OK Oklahoma
1650         { 97, 97, -1, -1 }, // OR Oregon
1651         { 15, 19, -1, -1 }, // PA Pennsylvania
1652         {  6,  6,  0,  9 }, // PR Puerto Rico
1653         { 96, 96, -1, -1 }, // PW Palau
1654         {  2,  2, -1, -1 }, // RI Rhode Island
1655         { 29, 29, -1, -1 }, // SC South Carolina
1656         { 57, 57, -1, -1 }, // SD South Dakota
1657         { 37, 38, -1, -1 }, // TN Tennessee
1658         { 75, 79, 87, 88 }, // TX Texas
1659         { 84, 84, -1, -1 }, // UT Utah
1660         { 22, 24, 20, -1 }, // VA Virginia
1661         {  6,  9, -1, -1 }, // VI Virgin Islands
1662         {  5,  5, -1, -1 }, // VT Vermont
1663         { 98, 99, -1, -1 }, // WA Washington
1664         { 53, 54, -1, -1 }, // WI Wisconsin
1665         { 24, 26, -1, -1 }, // WV West Virginia
1666         { 82, 83, -1, -1 }  // WY Wyoming
1667     };
1668
1669     int zip = zipPtr[0] - '0';
1670     zip *= 10;
1671     zip += zipPtr[1] - '0';
1672     int low = zipRange[stateIndex].mLow;
1673     int high = zipRange[stateIndex].mHigh;
1674     if (zip >= low && zip <= high)
1675         return true;
1676     if (zip == zipRange[stateIndex].mException1)
1677         return true;
1678     if (zip == zipRange[stateIndex].mException2)
1679         return true;
1680     return false;
1681 }
1682
1683 #define MAX_PLACE_NAME_LENGTH 25 // the longest allowable one word place name
1684
1685 CacheBuilder::FoundState CacheBuilder::FindAddress(const UChar* chars,
1686     unsigned length, int* start, int* end, bool caseInsensitive)
1687 {
1688     FindState addressState;
1689     FindReset(&addressState);
1690     addressState.mWords[0] = addressState.mStarts[0] = chars;
1691     addressState.mCaseInsensitive = caseInsensitive;
1692     FoundState state = FindPartialAddress(chars, chars, length, &addressState);
1693     if (state == FOUND_PARTIAL && addressState.mProgress == ZIP_CODE &&
1694             addressState.mNumberCount == 0) {
1695         addressState.mProgress = FIND_STREET;
1696         state = FindPartialAddress(NULL, NULL, 0, &addressState);
1697     }
1698     *start = addressState.mStartResult;
1699     *end = addressState.mEndResult;
1700     return state;
1701 }
1702
1703 CacheBuilder::FoundState CacheBuilder::FindPartialAddress(const UChar* baseChars,
1704     const UChar* chars, unsigned length, FindState* s)
1705 {
1706     // lower case letters are optional; trailing asterisk is optional 's'
1707     static char const* const longStreetNames[] = {
1708         "\x04" "LleY" "\x04" "NneX" "\x05" "RCade" "\x05" "VEnue" "\x06" "LAMEDA", // A
1709         "\x04" "aYoU" "\x04" "eaCH" "\x03" "eND" "\x05" "LuFf*" "\x05" "oTtoM"
1710             "\x08" "ouLeVarD" "\x05" "Ranch" "\x05" "RidGe" "\x05" "RooK*"
1711             "\x04" "urG*" "\x05" "YPass" "\x07" "roadWAY", // B
1712         "\x05" "AMINO"
1713         "\x03" "amP" "\x05" "anYoN" "\x03" "aPE" "\x07" "auSeWaY" "\x06" "enTeR*"
1714             "\x06" "IRcle*" "\x05" "LiFf*" "\x03" "LuB" "\x05" "oMmoN" "\x06" "ORner*"
1715             "\x05" "ouRSE" "\x05" "ourT*" "\x04" "oVe*" "\x04" "ReeK" "\x07" "REScent"
1716             "\x04" "ReST" "\x07" "ROSSING" "\x08" "ROSSROAD" "\x04" "URVe"
1717             "\x05" "AMINO" "\x06" "IRCULO" "\x07" "REScent", // C
1718         "\x03" "aLe" "\x02" "aM" "\x05" "iVide" "\x05" "Rive*", // D
1719         "\x06" "STate*" "\x09" "XPresswaY" "\x09" "XTension*", // E
1720         "\x04" "ALL*" "\x04" "eRrY" "\x05" "ieLD*" "\x04" "LaT*" "\x04" "oRD*"
1721             "\x05" "oReST" "\x05" "oRGe*" "\x04" "oRK*" "\x03" "orT" "\x06" "reeWaY", // F
1722         "\x06" "arDeN*" "\x06" "aTeWaY" "\x04" "LeN*" "\x05" "ReeN*" "\x05" "RoVe*", // G
1723         "\x06" "arBoR*" "\x04" "aVeN" "\x06" "eighTS" "\x06" "ighWaY" "\x04" "iLl*"
1724             "\x05" "OLloW", // H
1725         "\x04" "NLeT" "\x06" "Sland*" "\x03" "SLE", // I
1726         "\x08" "unCTion*", // J
1727         "\x03" "eY*" "\x05" "NoLl*", // K
1728         "\x04" "aKe*" "\x03" "AND" "\x06" "aNDinG" "\x03" "aNe" "\x05" "iGhT*"
1729             "\x03" "oaF" "\x04" "oCK*" "\x04" "oDGe" "\x03" "OOP", // L
1730         "\x03" "ALL" "\x05" "aNoR*" "\x06" "eaDoW*" "\x03" "EWS" "\x04" "iLl*"
1731             "\x06" "iSsioN" "\x07" "oTorWaY" "\x04" "ounT" "\x08" "ounTaiN*", // M
1732         "\x03" "eCK", // N
1733         "\x06" "RCHard" "\x03" "VAL" "\x07" "verPASs", // O
1734         "\x04" "ARK*" "\x07" "arKWaY*" "\x03" "ASS" "\x06" "aSsaGE" "\x03" "ATH"
1735             "\x03" "IKE" "\x04" "iNE*" "\x04" "Lace" "\x05" "LaiN*" "\x04" "LaZa"
1736             "\x05" "oinT*" "\x04" "oRT*" "\x06" "Rairie" "\x06" "RIVADA", // P
1737         NULL,
1738         "\x05" "ADiaL" "\x03" "AMP" "\x04" "aNCH" "\x05" "aPiD*"
1739             "\x03" "eST"
1740             "\x05" "iDGe*" "\x04" "IVer" "\x04" "oaD*" "\x04" "ouTE" "\x02" "OW"
1741             "\x02" "UE" "\x02" "UN", // R
1742         "\x05" "HoaL*" "\x05" "HoRe*" "\x05" "KyWaY" "\x06" "PrinG*" "\x04" "PUR*"
1743             "\x06" "Quare*" "\x06" "TAtion" "\x08" "TRAvenue" "\x05" "TReaM"
1744             "\x06" "Treet*" "\x05" "uMmiT" "\x07" "PeeDWaY", // S
1745         "\x06" "ERrace" "\x09" "hRoughWaY" "\x04" "RaCE" "\x04" "RAcK" "\x09" "RaFficwaY"
1746             "\x04" "RaiL" "\x05" "UNneL" "\x07" "urnPiKE", // T
1747         "\x08" "nderPASs" "\x05" "Nion*", // U
1748         "\x06" "aLleY*" "\x06" "IAduct" "\x04" "ieW*" "\x07" "iLlaGe*" "\x04" "iLle"
1749             "\x04" "ISta", // V
1750         "\x04" "ALK*" "\x03" "ALL" "\x03" "AY*" "\x04" "eLl*", // W
1751         "\x03" "ING" "\x02" "RD", // X
1752     };
1753
1754     static char const* const longStateNames[] = {
1755         "\x8e" "la" "\x85" "bama" "\x02" "\x84" "ska" "\x01" "\x8f" "merican Samoa" "\x04"
1756              "\x91" "r" "\x86" "izona" "\x05" "\x87" "kansas" "\x03",
1757         NULL,
1758         "\x8b" "alifornia" "\x06" "\x95" "o" "\x87" "lorado" "\x07" "\x8a" "nnecticut" "\x08",
1759         "\x89" "elaware" "\x0a" "\x95" "istrict of Columbia" "\x09",
1760         NULL,
1761         "\x9f" "ederated States of Micronesia" "\x0c" "\x88" "lorida" "\x0b",
1762         "\x85" "uam" "\x0e" "\x88" "eorgia" "\x0d",
1763         "\x87" "awaii" "\x0f",
1764         "\x86" "daho" "\x11" "\x89" "llinois" "\x12" "\x88" "ndiana" "\x13" "\x85"
1765              "owa" "\x10",
1766         NULL,
1767         "\x87" "ansas" "\x14" "\x89" "entucky" "\x15",
1768         "\x8a" "ouisiana" "\x16",
1769         "\x86" "aine" "\x19" "\x99" "ar" "\x8e" "shall Islands" "\x1a" "\x86" "yland" "\x18"
1770              "\x8e" "assachusetts" "\x17" "\x93" "i" "\x87" "chigan" "\x1b"
1771              "\x88" "nnesota" "\x1c" "\x93" "iss" "\x88" "issippi" "\x1f" "\x85"
1772              "ouri" "\x1d" "\x88" "ontana" "\x20",
1773         "\x90" "e" "\x87" "braska" "\x23" "\x85" "vada" "\x27" "\xa5" "ew " "\x8a"
1774              "Hampshire" "\x24" "\x87" "Jersey" "\x25" "\x87" "Mexico" "\x26"
1775              "\x85" "York" "\x28" "\x98" "orth " "\x89" "Carolina" "\x21" "\x87"
1776              "Dakota" "\x22" "\x99" "orthern Mariana Islands" "\x1e",
1777         "\x85" "hio" "\x29" "\x89" "klahoma" "\x2a" "\x87" "regon" "\x2b",
1778         "\x86" "alau" "\x2e" "\x8d" "ennsylvania" "\x2c" "\x8c" "uerto Rico" "\x2d",
1779         NULL,
1780         "\x8d" "hode Island" "\x2f",
1781         "\x98" "outh " "\x89" "Carolina" "\x30" "\x87" "Dakota" "\x31",
1782         "\x90" "e" "\x88" "nnessee" "\x32" "\x84" "xas" "\x33",
1783         "\x85" "tah" "\x34",
1784         "\x88" "ermont" "\x37" "\x94" "irgin" "\x89" " Islands" "\x36" "\x83" "ia" "\x35",
1785         "\x8b" "ashington" "\x38" "\x8e" "est Virginia" "\x3a" "\x8a" "isconsin" "\x39"
1786              "\x88" "yoming" "\x3b"
1787     };
1788
1789 #if 0 // DEBUG_NAV_UI
1790     static char const* const progressNames[] = {
1791         "NO_ADDRESS",
1792         "SKIP_TO_SPACE",
1793         "HOUSE_NUMBER",
1794         "NUMBER_TRAILING_SPACE",
1795         "ADDRESS_LINE",
1796         "STATE_NAME",
1797         "SECOND_HALF",
1798         "ZIP_CODE",
1799         "PLUS_4",
1800         "FIND_STREET"
1801     };
1802 #endif
1803     // strategy: US only support at first
1804     // look for a 1 - 5 digit number for a street number (no support for 'One Microsoft Way')
1805         // ignore if preceded by '#', Suite, Ste, Rm
1806     // look for two or more words (up to 5? North Frank Lloyd Wright Blvd)
1807             // note: "The Circle at North Hills St." has six words, and a lower 'at' -- allow at, by, of, in, the, and, ... ?
1808         // if a word starts with a lowercase letter, no match
1809         // allow: , . - # / (for 1/2) ' "
1810         // don't look for street name type yet
1811     // look for one or two delimiters to represent possible 2nd addr line and city name
1812     // look for either full state name, or state two letters, and/or zip code (5 or 9 digits)
1813     // now look for street suffix, either in full or abbreviated form, with optional 's' if there's an asterisk
1814
1815     s->mCurrentStart = chars;
1816     s->mEnd = chars + length;
1817     int candIndex = 0;
1818     bool retryState;
1819     bool mustBeAllUpper = false;
1820     bool secondHalf = false;
1821     chars -= 1;
1822     UChar ch = s->mCurrent;
1823     while (++chars <= s->mEnd) {
1824         UChar prior = ch;
1825         ch = chars < s->mEnd ? *chars : ' ';
1826         switch (s->mProgress) {
1827             case NO_ADDRESS:
1828                 if (WTF::isASCIIDigit(ch) == false) {
1829                     if (ch != 'O') // letter 'O', not zero
1830                         continue;
1831                     if (s->mEnd - chars < 3)
1832                         continue;
1833                     prior = *++chars;
1834                     ch = *++chars;
1835                     if ((prior != 'n' || ch != 'e') && (prior != 'N' || ch != 'E'))
1836                         continue;
1837                     if (isUnicodeSpace(*++chars) == false)
1838                         continue;
1839                     s->mProgress = ADDRESS_LINE;
1840                     s->mStartResult = chars - 3 - s->mCurrentStart;
1841                     continue;
1842                 }
1843                 if (isUnicodeSpace(prior) == false) {
1844                     s->mProgress = SKIP_TO_SPACE;
1845                     continue;
1846                 }
1847                 s->mNumberCount = 1;
1848                 s->mProgress = HOUSE_NUMBER;
1849                 s->mStartResult = chars - s->mCurrentStart;
1850                 continue;
1851             case SKIP_TO_SPACE:
1852                 if (isUnicodeSpace(ch) == false)
1853                     continue;
1854                 break;
1855             case HOUSE_NUMBER:
1856                 if (WTF::isASCIIDigit(ch)) {
1857                     if (++s->mNumberCount >= 6)
1858                         s->mProgress = SKIP_TO_SPACE;
1859                     continue;
1860                 }
1861                 if (WTF::isASCIIUpper(ch)) { // allow one letter after house number, e.g. 12A SKOLFIELD PL, HARPSWELL, ME 04079
1862                     if (WTF::isASCIIDigit(prior) == false)
1863                         s->mProgress = SKIP_TO_SPACE;
1864                     continue;
1865                 }
1866                 if (ch == '-') {
1867                     if (s->mNumberCount > 0) { // permit 21-23 ELM ST
1868                         ++s->mNumberCount;
1869                         continue;
1870                     }
1871                 }
1872                 s->mNumberCount = 0;
1873                 s->mProgress = NUMBER_TRAILING_SPACE;
1874             case NUMBER_TRAILING_SPACE:
1875                 if (isUnicodeSpace(ch))
1876                     continue;
1877                 if (0 && WTF::isASCIIDigit(ch)) {
1878                     s->mNumberCount = 1;
1879                     s->mProgress = HOUSE_NUMBER;
1880                     s->mStartResult = chars - s->mCurrentStart;
1881                     continue;
1882                 }
1883                 if (WTF::isASCIIDigit(ch) == false && WTF::isASCIIUpper(ch) == false)
1884                     break;
1885                 s->mProgress = ADDRESS_LINE;
1886             case ADDRESS_LINE:
1887                 if (WTF::isASCIIAlpha(ch) || ch == '\'' || ch == '-' || ch == '&' || ch == '(' || ch == ')') {
1888                     if (++s->mLetterCount > 1) {
1889                         s->mNumberWords &= ~(1 << s->mWordCount);
1890                         continue;
1891                     }
1892                     if (s->mNumberCount >= 5)
1893                         break;
1894 // FIXME: the test below was added to give up on a non-address, but it
1895 // incorrectly discards addresses where the house number is in one node
1896 // and the street name is in the next; I don't recall what the failing case
1897 // is that suggested this fix.
1898 //                    if (s->mWordCount == 0 && s->mContinuationNode)
1899 //                        return FOUND_NONE;
1900                     s->newWord(baseChars, chars);
1901                     if (WTF::isASCIILower(ch) && s->mNumberCount == 0)
1902                         s->mFirstLower = chars;
1903                     s->mNumberCount = 0;
1904                     if (WTF::isASCIILower(ch) || (WTF::isASCIIAlpha(ch) == false && ch != '-'))
1905                         s->mNumberWords &= ~(1 << s->mWordCount);
1906                     s->mUnparsed = true;
1907                     continue;
1908                 } else if (s->mLetterCount >= MAX_PLACE_NAME_LENGTH) {
1909                     break;
1910                 } else if (s->mFirstLower != NULL) {
1911                     if (s->mCaseInsensitive)
1912                         goto resetWord;
1913                     size_t length = chars - s->mFirstLower;
1914                     if (length > 3)
1915                         break;
1916                     if (length == 3 && strCharCmp("and" "the", s->mFirstLower, 3, 2) == false)
1917                         break;
1918                     if (length == 2 && strCharCmp("at" "by" "el" "in" "of", s->mFirstLower, 2, 5) == false)
1919                         break;
1920                     goto resetWord;
1921                 }
1922                 if (ch == ',' || ch == '*') { // delimits lines
1923                     // asterisk as delimiter: http://www.sa.sc.edu/wellness/members.html
1924                     if (++s->mLineCount > 5)
1925                         break;
1926                     goto lookForState;
1927                 }
1928                 if (isUnicodeSpace(ch) || prior == '-') {
1929             lookForState:
1930                     if (s->mUnparsed == false)
1931                         continue;
1932                     const UChar* candidate = s->mWords[s->mWordCount];
1933                     UChar firstLetter = candidate[0];
1934                     if (WTF::isASCIIUpper(firstLetter) == false && WTF::isASCIIDigit(firstLetter) == false)
1935                         goto resetWord;
1936                     s->mWordCount++;
1937                     if ((s->mWordCount == 2 && s->mNumberWords == 3 && WTF::isASCIIDigit(s->mWords[1][1])) || // choose second of 8888 333 Main
1938                         (s->mWordCount >= sizeof(s->mWords) / sizeof(s->mWords[0]) - 1)) { // subtract 1 since state names may have two parts
1939                         // search for simple number already stored since first potential house # didn't pan out
1940                         if (s->mNumberWords == 0)
1941                             break;
1942                         int shift = 0;
1943                         while ((s->mNumberWords & (1 << shift)) == 0)
1944                             shift++;
1945                         s->mNumberWords >>= ++shift;
1946                         if (s->mBases[0] != s->mBases[shift]) // if we're past the original node, bail
1947                             break;
1948                         s->shiftWords(shift);
1949                         s->mStartResult = s->mWords[0] - s->mStarts[0];
1950                         s->mWordCount -= shift;
1951                         // FIXME: need to adjust lineCount to account for discarded delimiters
1952                     }
1953                     if (s->mWordCount < 4)
1954                         goto resetWord;
1955                     firstLetter -= 'A';
1956                     if (firstLetter > 'W' - 'A')
1957                         goto resetWord;
1958                     UChar secondLetter = candidate[1];
1959                     if (prior == '-')
1960                         s->mLetterCount--; // trim trailing dashes, to accept CA-94043
1961                     if (s->mLetterCount == 2) {
1962                         secondLetter -= 'A';
1963                         if (secondLetter > 'Z' - 'A')
1964                             goto resetWord;
1965                         if ((stateTwoLetter[firstLetter] & 1 << secondLetter) != 0) {
1966                             // special case to ignore 'et al'
1967                             if (strCharCmp("ET", s->mWords[s->mWordCount - 2], 2, 1) == false) {
1968                                 s->mStateWord = s->mWordCount - 1;
1969                                 s->mZipHint = firstIndex[firstLetter] +
1970                                     bitcount(stateTwoLetter[firstLetter] & ((1 << secondLetter) - 1));
1971                                 goto foundStateName;
1972                             }
1973                         }
1974                         goto resetWord;
1975                     }
1976                     s->mStates = longStateNames[firstLetter];
1977                     if (s->mStates == NULL)
1978                         goto resetWord;
1979                     mustBeAllUpper = false;
1980                     s->mProgress = STATE_NAME;
1981                     unsigned char section = s->mStates[0];
1982                     ASSERT(section > 0x80);
1983                     s->mSectionLength = section & 0x7f;
1984                     candIndex = 1;
1985                     secondHalf = false;
1986                     s->mStateWord = s->mWordCount - 1;
1987                     goto stateName;
1988                 }
1989                 if (WTF::isASCIIDigit(ch)) {
1990                     if (s->mLetterCount == 0) {
1991                         if (++s->mNumberCount > 1)
1992                             continue;
1993                         if (s->mWordCount == 0 && s->mContinuationNode)
1994                             return FOUND_NONE;
1995                         s->newWord(baseChars, chars);
1996                         s->mNumberWords |= 1 << s->mWordCount;
1997                         s->mUnparsed = true;
1998                     }
1999                     continue;
2000                 }
2001                 if (ch == '.') { // optionally can follow letters
2002                     if (s->mLetterCount == 0)
2003                         break;
2004                     if (s->mNumberCount > 0)
2005                         break;
2006                     continue;
2007                 }
2008                 if (ch == '/') // between numbers (1/2) between words (12 Main / Ste 4d)
2009                     goto resetWord;
2010                 if (ch == '#') // can precede numbers, allow it to appear randomly
2011                     goto resetWord;
2012                 if (ch == '"') // sometimes parts of addresses are quoted (FIXME: cite an example here)
2013                     continue;
2014                 break;
2015             case SECOND_HALF:
2016                 if (WTF::isASCIIAlpha(ch)) {
2017                     if (s->mLetterCount == 0) {
2018                         s->newWord(baseChars, chars);
2019                         s->mWordCount++;
2020                     }
2021                     s->mLetterCount++;
2022                     continue;
2023                 }
2024                 if (WTF::isASCIIDigit(ch) == false) {
2025                     if (s->mLetterCount > 0) {
2026                         s->mProgress = STATE_NAME;
2027                         candIndex = 0;
2028                         secondHalf = true;
2029                         goto stateName;
2030                     }
2031                     continue;
2032                 }
2033                 s->mProgress = ADDRESS_LINE;
2034                 goto resetState;
2035             case STATE_NAME:
2036             stateName:
2037                 // pick up length of first section
2038                 do {
2039                     int stateIndex = 1;
2040                     int skip = 0;
2041                     int prefix = 0;
2042                     bool subStr = false;
2043                     do {
2044                         unsigned char match = s->mStates[stateIndex];
2045                         if (match >= 0x80) {
2046                             if (stateIndex == s->mSectionLength)
2047                                 break;
2048                             subStr = true;
2049                   //          if (skip > 0)
2050                   //              goto foundStateName;
2051                             prefix = candIndex;
2052                             skip = match & 0x7f;
2053                             match = s->mStates[++stateIndex];
2054                         }
2055                         UChar candChar = s->mWords[s->mWordCount - 1][candIndex];
2056                         if (mustBeAllUpper && WTF::isASCIILower(candChar))
2057                             goto skipToNext;
2058                         if (match != candChar) {
2059                             if (match != WTF::toASCIILower(candChar)) {
2060                        skipToNext:
2061                                 if (subStr == false)
2062                                     break;
2063                                 if (stateIndex == s->mSectionLength) {
2064                                     if (secondHalf) {
2065                                         s->mProgress = ADDRESS_LINE;
2066                                         goto resetState;
2067                                     }
2068                                     break;
2069                                 }
2070                                 stateIndex += skip;
2071                                 skip = 0;
2072                                 candIndex = prefix;
2073                                 continue; // try next substring
2074                             }
2075                             mustBeAllUpper = true;
2076                         }
2077                         int nextindex = stateIndex + 1;
2078                         if (++candIndex >= s->mLetterCount && s->mStates[nextindex] == ' ') {
2079                             s->mProgress = SECOND_HALF;
2080                             s->mStates += nextindex;
2081                             s->mSectionLength -= nextindex;
2082                             goto resetWord;
2083                         }
2084                         if (nextindex + 1 == s->mSectionLength || skip == 2) {
2085                             s->mZipHint = s->mStates[nextindex] - 1;
2086                             goto foundStateName;
2087                         }
2088                         stateIndex += 1;
2089                         skip -= 1;
2090                     } while (true);
2091                     s->mStates += s->mSectionLength;
2092                     ASSERT(s->mStates[0] == 0 || (unsigned) s->mStates[0] > 0x80);
2093                     s->mSectionLength = s->mStates[0] & 0x7f;
2094                     candIndex = 1;
2095                     subStr = false;
2096                 } while (s->mSectionLength != 0);
2097                 s->mProgress = ADDRESS_LINE;
2098                 goto resetState;
2099             foundStateName:
2100                 s->mEndResult = chars - s->mCurrentStart;
2101                 s->mEndWord = s->mWordCount - 1;
2102                 s->mProgress = ZIP_CODE;
2103                 // a couple of delimiters is an indication that the state name is good
2104                 // or, a non-space / non-alpha-digit is also good
2105                 s->mZipDelimiter = s->mLineCount > 2
2106                     || isUnicodeSpace(ch) == false
2107                     || chars == s->mEnd;
2108                 if (WTF::isASCIIDigit(ch))
2109                     s->mZipStart = chars;
2110                 goto resetState;
2111             case ZIP_CODE:
2112                 if (WTF::isASCIIDigit(ch)) {
2113                     int count = ++s->mNumberCount;
2114                     if (count == 1) {
2115                         if (WTF::isASCIIDigit(prior))
2116                             ++s->mNumberCount;
2117                         else
2118                             s->mZipStart = chars;
2119                     }
2120                     if (count <= 9)
2121                         continue;
2122                 } else if (isUnicodeSpace(ch)) {
2123                     if (s->mNumberCount == 0) {
2124                         s->mZipDelimiter = true; // two spaces delimit state name
2125                         continue;
2126                     }
2127                 } else if (ch == '-') {
2128                     if (s->mNumberCount == 5 && validZip(s->mZipHint, s->mZipStart)) {
2129                         s->mNumberCount = 0;
2130                         s->mProgress = PLUS_4;
2131                         continue;
2132                     }
2133                     if (s->mNumberCount == 0)
2134                         s->mZipDelimiter = true;
2135                 } else if (WTF::isASCIIAlpha(ch) == false)
2136                     s->mZipDelimiter = true;
2137                 else {
2138                     if (s->mLetterCount == 0) {
2139                         s->newWord(baseChars, chars);
2140                         s->mUnparsed = true;
2141                     }
2142                     ++s->mLetterCount;
2143                 }
2144                 if (s->mNumberCount == 5 || s->mNumberCount == 9) {
2145                     if (validZip(s->mZipHint, s->mZipStart) == false)
2146                         goto noZipMatch;
2147                     s->mEndResult = chars - s->mCurrentStart;
2148                     s->mEndWord = s->mWordCount - 1;
2149                 } else if (s->mZipDelimiter == false) {
2150             noZipMatch:
2151                     --chars;
2152                     s->mProgress = ADDRESS_LINE;
2153                     continue;
2154                 }
2155                 s->mProgress = FIND_STREET;
2156                 goto findStreet;
2157             case PLUS_4:
2158                 if (WTF::isASCIIDigit(ch)) {
2159                     if (++s->mNumberCount <= 4)
2160                         continue;
2161                 }
2162                 if (isUnicodeSpace(ch)) {
2163                     if (s->mNumberCount == 0)
2164                         continue;
2165                 }
2166                 if (s->mNumberCount == 4) {
2167                     if (WTF::isASCIIAlpha(ch) == false) {
2168                         s->mEndResult = chars - s->mCurrentStart;
2169                         s->mEndWord = s->mWordCount - 1;
2170                     }
2171                 } else if (s->mNumberCount != 0)
2172                     break;
2173                 s->mProgress = FIND_STREET;
2174             case FIND_STREET:
2175             findStreet:
2176                 retryState = false;
2177                 for (int wordsIndex = s->mStateWord - 1; wordsIndex >= 0; --wordsIndex) {
2178                     const UChar* test = s->mWords[wordsIndex];
2179                     UChar letter = test[0];
2180                     letter -= 'A';
2181                     if (letter > 'X' - 'A')
2182                         continue;
2183                     const char* names = longStreetNames[letter];
2184                     if (names == NULL)
2185                         continue;
2186                     int offset;
2187                     while ((offset = *names++) != 0) {
2188                         int testIndex = 1;
2189                         bool abbr = false;
2190                         for (int idx = 0; idx < offset; idx++) {
2191                             char nameLetter = names[idx];
2192                             char testUpper = WTF::toASCIIUpper(test[testIndex]);
2193                             if (nameLetter == '*') {
2194                                 if (testUpper == 'S')
2195                                     testIndex++;
2196                                 break;
2197                             }
2198                             bool fullOnly = WTF::isASCIILower(nameLetter);
2199                             nameLetter = WTF::toASCIIUpper(nameLetter);
2200                             if (testUpper == nameLetter) {
2201                                 if (abbr && fullOnly)
2202                                     goto nextTest;
2203                                 testIndex++;
2204                                 continue;
2205                             }
2206                             if (fullOnly == false)
2207                                 goto nextTest;
2208                             abbr = true;
2209                         }
2210                         letter = &test[testIndex] < s->mEnds[wordsIndex] ?
2211                             test[testIndex] : ' ';
2212                         if (WTF::isASCIIAlpha(letter) == false && WTF::isASCIIDigit(letter) == false) {
2213                             if (s->mNumberWords != 0) {
2214                                 int shift = 0;
2215                                 int wordReduction = -1;
2216                                 do {
2217                                     while ((s->mNumberWords & (1 << shift)) == 0)
2218                                         shift++;
2219                                     if (shift > wordsIndex)
2220                                         break;
2221                                     wordReduction = shift;
2222                                 } while (s->mNumberWords >> ++shift != 0);
2223                                 if (wordReduction >= 0) {
2224                                     if (s->mContinuationNode) {
2225                                         if (retryState)
2226                                             break;
2227                                         return FOUND_NONE;
2228                                     }
2229                                     s->mStartResult = s->mWords[wordReduction] - s->mStarts[wordReduction];
2230                                 }
2231                             }
2232                             if (wordsIndex != s->mStateWord - 1)
2233                                 return FOUND_COMPLETE;
2234                             retryState = true;
2235                         }
2236                     nextTest:
2237                         names += offset;
2238                     }
2239                 }
2240                 if (retryState) {
2241                     s->mProgress = ADDRESS_LINE;
2242                     s->mStates = NULL;
2243                     continue;
2244                 }
2245                 if (s->mNumberWords != 0) {
2246                     unsigned shift = 0;
2247                     while ((s->mNumberWords & (1 << shift)) == 0)
2248                         shift++;
2249                     s->mNumberWords >>= ++shift;
2250                     if (s->mBases[0] != s->mBases[shift])
2251                         return FOUND_NONE;
2252                     s->shiftWords(shift);
2253                     s->mStartResult = s->mWords[0] - s->mStarts[0];
2254                     s->mWordCount -= shift;
2255                     s->mProgress = ADDRESS_LINE;
2256                     --chars;
2257                     continue;
2258                 }
2259                 break;
2260         }
2261         if (s->mContinuationNode)
2262             return FOUND_NONE;
2263         s->mProgress = NO_ADDRESS;
2264         s->mWordCount = s->mLineCount = 0;
2265         s->mNumberWords = 0;
2266     resetState:
2267         s->mStates = NULL;
2268     resetWord:
2269         s->mNumberCount = s->mLetterCount = 0;
2270         s->mFirstLower = NULL;
2271         s->mUnparsed = false;
2272     }
2273     s->mCurrent = ch;
2274     return s->mProgress == NO_ADDRESS ? FOUND_NONE : FOUND_PARTIAL;
2275 }
2276
2277 // Recogize common email patterns only. Currently has lots of state, walks text forwards and backwards -- will be
2278 // a real challenge to adapt to walk text across multiple nodes, I imagine
2279 // FIXME: it's too hard for the caller to call these incrementally -- it's probably best for this to
2280 // either walk the node tree directly or make a callout to get the next or previous node, if there is one
2281 // walking directly will avoid adding logic in caller to track the multiple partial or full nodes that compose this
2282 // text pattern.
2283 CacheBuilder::FoundState CacheBuilder::FindPartialEMail(const UChar* chars, unsigned length,
2284     FindState* s)
2285 {
2286     // the following tables were generated by tests/browser/focusNavigation/BrowserDebug.cpp
2287     // hand-edit at your own risk
2288     static const int domainTwoLetter[] = {
2289         0x02df797c,  // a followed by: [cdefgilmnoqrstuwxz]
2290         0x036e73fb,  // b followed by: [abdefghijmnorstvwyz]
2291         0x03b67ded,  // c followed by: [acdfghiklmnorsuvxyz]
2292         0x02005610,  // d followed by: [ejkmoz]
2293         0x001e00d4,  // e followed by: [ceghrstu]
2294         0x00025700,  // f followed by: [ijkmor]
2295         0x015fb9fb,  // g followed by: [abdefghilmnpqrstuwy]
2296         0x001a3400,  // h followed by: [kmnrtu]
2297         0x000f7818,  // i followed by: [delmnoqrst]
2298         0x0000d010,  // j followed by: [emop]
2299         0x0342b1d0,  // k followed by: [eghimnprwyz]
2300         0x013e0507,  // l followed by: [abcikrstuvy]
2301         0x03fffccd,  // m followed by: [acdghklmnopqrstuvwxyz]
2302         0x0212c975,  // n followed by: [acefgilopruz]
2303         0x00001000,  // o followed by: [m]
2304         0x014e3cf1,  // p followed by: [aefghklmnrstwy]
2305         0x00000001,  // q followed by: [a]
2306         0x00504010,  // r followed by: [eouw]
2307         0x032a7fdf,  // s followed by: [abcdeghijklmnortvyz]
2308         0x026afeec,  // t followed by: [cdfghjklmnoprtvwz]
2309         0x03041441,  // u followed by: [agkmsyz]
2310         0x00102155,  // v followed by: [aceginu]
2311         0x00040020,  // w followed by: [fs]
2312         0x00000000,  // x
2313         0x00180010,  // y followed by: [etu]
2314         0x00401001,  // z followed by: [amw]
2315     };
2316
2317     static char const* const longDomainNames[] = {
2318         "\x03" "ero" "\x03" "rpa",  // aero, arpa
2319         "\x02" "iz",  // biz
2320         "\x02" "at" "\x02" "om" "\x03" "oop",  // cat, com, coop
2321         NULL,  // d
2322         "\x02" "du",  // edu
2323         NULL,  // f
2324         "\x02" "ov",  // gov
2325         NULL,  // h
2326         "\x03" "nfo" "\x02" "nt",  // info, int
2327         "\x03" "obs",  // jobs
2328         NULL,  // k
2329         NULL,  // l
2330         "\x02" "il" "\x03" "obi" "\x05" "useum",  // mil, mobi, museum
2331         "\x03" "ame" "\x02" "et",  // name, net
2332         "\x02" "rg",  // , org
2333         "\x02" "ro",  // pro
2334         NULL,  // q
2335         NULL,  // r
2336         NULL,  // s
2337         "\x05" "ravel",  // travel
2338         NULL,  // u
2339         NULL,  // v
2340         NULL,  // w
2341         NULL,  // x
2342         NULL,  // y
2343         NULL,  // z
2344     };
2345
2346     const UChar* start = chars;
2347     const UChar* end = chars + length;
2348     while (chars < end) {
2349         UChar ch = *chars++;
2350         if (ch != '@')
2351             continue;
2352         const UChar* atLocation = chars - 1;
2353         // search for domain
2354         ch = *chars++ | 0x20; // convert uppercase to lower
2355         if (ch < 'a' || ch > 'z')
2356             continue;
2357         while (chars < end) {
2358             ch = *chars++;
2359             if (IsDomainChar(ch) == false)
2360                 goto nextAt;
2361             if (ch != '.')
2362                 continue;
2363             UChar firstLetter = *chars++ | 0x20; // first letter of the domain
2364             if (chars >= end)
2365                 return FOUND_NONE; // only one letter; must be at least two
2366             firstLetter -= 'a';
2367             if (firstLetter > 'z' - 'a')
2368                 continue; // non-letter followed '.'
2369             int secondLetterMask = domainTwoLetter[firstLetter];
2370             ch = *chars | 0x20; // second letter of the domain
2371             ch -= 'a';
2372             if (ch >= 'z' - 'a')
2373                 continue;
2374             bool secondMatch = (secondLetterMask & 1 << ch) != 0;
2375             const char* wordMatch = longDomainNames[firstLetter];
2376             int wordIndex = 0;
2377             while (wordMatch != NULL) {
2378                 int len = *wordMatch++;
2379                 char match;
2380                 do {
2381                     match = wordMatch[wordIndex];
2382                     if (match < 0x20)
2383                         goto foundDomainStart;
2384                     if (chars[wordIndex] != match)
2385                         break;
2386                     wordIndex++;
2387                 } while (true);
2388                 wordMatch += len;
2389                 if (*wordMatch == '\0')
2390                     break;
2391                 wordIndex = 0;
2392             }
2393             if (secondMatch) {
2394                 wordIndex = 1;
2395         foundDomainStart:
2396                 chars += wordIndex;
2397                 if (chars < end) {
2398                     ch = *chars;
2399                     if (ch != '.') {
2400                         if (IsDomainChar(ch))
2401                             goto nextDot;
2402                     } else if (chars + 1 < end && IsDomainChar(chars[1]))
2403                         goto nextDot;
2404                 }
2405                 // found domain. Search backwards from '@' for beginning of email address
2406                 s->mEndResult = chars - start;
2407                 chars = atLocation;
2408                 if (chars <= start)
2409                     goto nextAt;
2410                 ch = *--chars;
2411                 if (ch == '.')
2412                     goto nextAt; // mailbox can't end in period
2413                 do {
2414                     if (IsMailboxChar(ch) == false) {
2415                         chars++;
2416                         break;
2417                     }
2418                     if (chars == start)
2419                         break;
2420                     ch = *--chars;
2421                 } while (true);
2422                 UChar firstChar = *chars;
2423                 if (firstChar == '.' || firstChar == '@') // mailbox can't start with period or be empty
2424                     goto nextAt;
2425                 s->mStartResult = chars - start;
2426                 return FOUND_COMPLETE;
2427             }
2428     nextDot:
2429             ;
2430         }
2431 nextAt:
2432         chars = atLocation + 1;
2433     }
2434     return FOUND_NONE;
2435 }
2436
2437 #define PHONE_PATTERN "(200) /-.\\ 100 -. 0000" // poor man's regex: parens optional, any one of punct, digit smallest allowed
2438
2439 CacheBuilder::FoundState CacheBuilder::FindPartialNumber(const UChar* chars, unsigned length,
2440     FindState* s)
2441 {
2442     char* pattern = s->mPattern;
2443     UChar* store = s->mStorePtr;
2444     const UChar* start = chars;
2445     const UChar* end = chars + length;
2446     const UChar* lastDigit = NULL;
2447     do {
2448         bool initialized = s->mInitialized;
2449         while (chars < end) {
2450             if (initialized == false) {
2451                 s->mBackTwo = s->mBackOne;
2452                 s->mBackOne = s->mCurrent;
2453             }
2454             UChar ch = s->mCurrent = *chars;
2455             do {
2456                 char patternChar = *pattern;
2457                 switch (patternChar) {
2458                     case '2':
2459                             if (initialized == false) {
2460                                 s->mStartResult = chars - start;
2461                                 initialized = true;
2462                             }
2463                     case '0':
2464                     case '1':
2465                         if (ch < patternChar || ch > '9')
2466                             goto resetPattern;
2467                         *store++ = ch;
2468                         pattern++;
2469                         lastDigit = chars;
2470                         goto nextChar;
2471                     case '\0':
2472                         if (WTF::isASCIIDigit(ch) == false) {
2473                             *store = '\0';
2474                             goto checkMatch;
2475                         }
2476                         goto resetPattern;
2477                     case ' ':
2478                         if (ch == patternChar)
2479                             goto nextChar;
2480                         break;
2481                     case '(':
2482                         if (ch == patternChar) {
2483                             s->mStartResult = chars - start;
2484                             initialized = true;
2485                             s->mOpenParen = true;
2486                         }
2487                         goto commonPunctuation;
2488                     case ')':
2489                         if ((ch == patternChar) ^ s->mOpenParen)
2490                             goto resetPattern;
2491                     default:
2492                     commonPunctuation:
2493                         if (ch == patternChar) {
2494                             pattern++;
2495                             goto nextChar;
2496                         }
2497                 }
2498             } while (++pattern); // never false
2499     nextChar:
2500             chars++;
2501         }
2502         break;
2503 resetPattern:
2504         if (s->mContinuationNode)
2505             return FOUND_NONE;
2506         FindResetNumber(s);
2507         pattern = s->mPattern;
2508         store = s->mStorePtr;
2509     } while (++chars < end);
2510 checkMatch:
2511     if (WTF::isASCIIDigit(s->mBackOne != '1' ? s->mBackOne : s->mBackTwo))
2512         return FOUND_NONE;
2513     *store = '\0';
2514     s->mStorePtr = store;
2515     s->mPattern = pattern;
2516     s->mEndResult = lastDigit - start + 1;
2517     char pState = pattern[0];
2518     return pState == '\0' ? FOUND_COMPLETE : pState == '(' || (WTF::isASCIIDigit(pState) && WTF::isASCIIDigit(pattern[-1])) ?
2519         FOUND_NONE : FOUND_PARTIAL;
2520 }
2521
2522 CacheBuilder::FoundState CacheBuilder::FindPhoneNumber(const UChar* chars, unsigned length,
2523     int* start, int* end)
2524 {
2525     FindState state;
2526     FindReset(&state);
2527     FoundState result = FindPartialNumber(chars, length, &state);
2528     *start = state.mStartResult;
2529     *end = state.mEndResult;
2530     return result;
2531 }
2532
2533 void CacheBuilder::FindReset(FindState* state)
2534 {
2535     memset(state, 0, sizeof(FindState));
2536     state->mCurrent = ' ';
2537     FindResetNumber(state);
2538 }
2539
2540 void CacheBuilder::FindResetNumber(FindState* state)
2541 {
2542     state->mOpenParen = false;
2543     state->mPattern = (char*) PHONE_PATTERN;
2544     state->mStorePtr = state->mStore;
2545 }
2546
2547 IntRect CacheBuilder::getAreaRect(const HTMLAreaElement* area)
2548 {
2549     Node* node = area->document();
2550     while ((node = node->traverseNextNode()) != NULL) {
2551         RenderObject* renderer = node->renderer();
2552         if (renderer && renderer->isRenderImage()) {
2553             RenderImage* image = static_cast<RenderImage*>(renderer);
2554             HTMLMapElement* map = image->imageMap();
2555             if (map) {
2556                 Node* n;
2557                 for (n = map->firstChild(); n;
2558                         n = n->traverseNextNode(map)) {
2559                     if (n == area) {
2560                         if (area->isDefault())
2561                             return image->absoluteBoundingBoxRect();
2562                         return area->computeRect(image);
2563                     }
2564                 }
2565             }
2566         }
2567     }
2568     return IntRect();
2569 }
2570
2571 void CacheBuilder::GetGlobalOffset(Node* node, int* x, int * y)
2572 {
2573     GetGlobalOffset(node->document()->frame(), x, y);
2574 }
2575
2576 void CacheBuilder::GetGlobalOffset(Frame* frame, int* x, int* y)
2577 {
2578 //    TIMER_PROBE(__FUNCTION__);
2579     ASSERT(x);
2580     ASSERT(y);
2581     *x = 0;
2582     *y = 0;
2583     if (!frame->view())
2584         return;
2585     Frame* parent;
2586     while ((parent = frame->tree()->parent()) != NULL) {
2587         const WebCore::IntRect& rect = frame->view()->platformWidget()->getBounds();
2588         *x += rect.x();
2589         *y += rect.y();
2590         frame = parent;
2591     }
2592  //   TIMER_PROBE_END();
2593 }
2594
2595 Frame* CacheBuilder::HasFrame(Node* node)
2596 {
2597     RenderObject* renderer = node->renderer();
2598     if (renderer == NULL)
2599         return NULL;
2600     if (renderer->isWidget() == false)
2601         return NULL;
2602     Widget* widget = static_cast<RenderWidget*>(renderer)->widget();
2603     if (widget == NULL)
2604         return NULL;
2605     if (widget->isFrameView() == false)
2606         return NULL;
2607     return static_cast<FrameView*>(widget)->frame();
2608 }
2609
2610 bool CacheBuilder::HasOverOrOut(Node* node)
2611 {
2612     // eventNames are thread-local data, I avoid using 'static' variable here.
2613     AtomicString eventTypes[2] = {
2614         eventNames().mouseoverEvent,
2615         eventNames().mouseoutEvent
2616     };
2617
2618     return NodeHasEventListeners(node, eventTypes, 2);
2619 }
2620
2621 bool CacheBuilder::HasTriggerEvent(Node* node)
2622 {
2623     AtomicString eventTypes[5] = {
2624         eventNames().clickEvent,
2625         eventNames().mousedownEvent,
2626         eventNames().mouseupEvent,
2627         eventNames().keydownEvent,
2628         eventNames().keyupEvent
2629     };
2630
2631     return NodeHasEventListeners(node, eventTypes, 5);
2632 }
2633
2634 // #define EMAIL_PATTERN "x@y.d" // where 'x' is letters, numbers, and '-', '.', '_' ; 'y' is 'x' without the underscore, and 'd' is a valid domain
2635 //  - 0x2D . 0x2E 0-9 0x30-39 A-Z 0x41-5A  _ 0x5F a-z 0x61-7A
2636
2637 bool CacheBuilder::IsDomainChar(UChar ch)
2638 {
2639     static const unsigned body[] = {0x03ff6000, 0x07fffffe, 0x07fffffe}; // 0-9 . - A-Z a-z
2640     ch -= 0x20;
2641     if (ch > 'z' - 0x20)
2642         return false;
2643     return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0;
2644 }
2645
2646 bool CacheBuilder::isFocusableText(NodeWalk* walk, bool more, Node* node,
2647     CachedNodeType* type, String* exported) const
2648 {
2649     Text* textNode = static_cast<Text*>(node);
2650     StringImpl* string = textNode->dataImpl();
2651     const UChar* baseChars = string->characters();
2652 //    const UChar* originalBase = baseChars;
2653     int length = string->length();
2654     int index = 0;
2655     while (index < length && isUnicodeSpace(baseChars[index]))
2656         index++;
2657     if (index >= length)
2658         return false;
2659     if (more == false) {
2660         walk->mStart = 0;
2661         walk->mEnd = 0;
2662         walk->mFinalNode = node;
2663         walk->mLastInline = NULL;
2664     }
2665     // starting with this node, search forward for email, phone number, and address
2666     // if any of the three is found, track it so that the remaining can be looked for later
2667     FoundState state = FOUND_NONE;
2668     RenderText* renderer = (RenderText*) node->renderer();
2669     bool foundBetter = false;
2670     InlineTextBox* baseInline = walk->mLastInline != NULL ? walk->mLastInline :
2671         renderer->firstTextBox();
2672     if (baseInline == NULL)
2673         return false;
2674     int start = walk->mEnd;
2675     InlineTextBox* saveInline;
2676     int baseStart, firstStart = start;
2677     saveInline = baseInline;
2678     baseStart = start;
2679     for (CachedNodeType checkType = ADDRESS_CACHEDNODETYPE;
2680         checkType <= PHONE_CACHEDNODETYPE;
2681         checkType = static_cast<CachedNodeType>(checkType + 1))
2682     {
2683         if ((1 << (checkType - 1) & mAllowableTypes) == 0)
2684             continue;
2685         InlineTextBox* inlineTextBox = baseInline;
2686         FindState findState;
2687         FindReset(&findState);
2688         start = baseStart;
2689         if (checkType == ADDRESS_CACHEDNODETYPE) {
2690             findState.mBases[0] = baseChars;
2691             findState.mWords[0] = baseChars + start;
2692             findState.mStarts[0] = baseChars + start;
2693         }
2694         Node* lastPartialNode = NULL;
2695         int lastPartialEnd = -1;
2696         bool lastPartialMore = false;
2697         bool firstPartial = true;
2698         InlineTextBox* lastPartialInline = NULL;
2699         do {
2700             do {
2701                 const UChar* chars = baseChars + start;
2702                 length = inlineTextBox == NULL ? 0 :
2703                     inlineTextBox->end() - start + 1;
2704                 bool wasInitialized = findState.mInitialized;
2705                 switch (checkType) {
2706                     case ADDRESS_CACHEDNODETYPE:
2707                         state = FindPartialAddress(baseChars, chars, length, &findState);
2708                     break;
2709                     case EMAIL_CACHEDNODETYPE:
2710                         state = FindPartialEMail(chars, length, &findState);
2711                     break;
2712                     case PHONE_CACHEDNODETYPE:
2713                         state = FindPartialNumber(chars, length, &findState);
2714                     break;
2715                     default:
2716                         ASSERT(0);
2717                 }
2718                 findState.mInitialized = state != FOUND_NONE;
2719                 if (wasInitialized != findState.mInitialized)
2720                     firstStart = start;
2721                 if (state == FOUND_PARTIAL) {
2722                     lastPartialNode = node;
2723                     lastPartialEnd = findState.mEndResult + start;
2724                     lastPartialMore = firstPartial &&
2725                         lastPartialEnd < (int) string->length();
2726                     firstPartial = false;
2727                     lastPartialInline = inlineTextBox;
2728                     findState.mContinuationNode = true;
2729                 } else if (state == FOUND_COMPLETE) {
2730                     if (foundBetter == false || walk->mStart > findState.mStartResult) {
2731                         walk->mStart = findState.mStartResult + firstStart;
2732                         if (findState.mEndResult > 0) {
2733                             walk->mFinalNode = node;
2734                             walk->mEnd = findState.mEndResult + start;
2735                             walk->mMore = node == textNode &&
2736                                 walk->mEnd < (int) string->length();
2737                             walk->mLastInline = inlineTextBox;
2738                         } else {
2739                             walk->mFinalNode = lastPartialNode;
2740                             walk->mEnd = lastPartialEnd;
2741                             walk->mMore = lastPartialMore;
2742                             walk->mLastInline = lastPartialInline;
2743                         }
2744                         *type = checkType;
2745                         if (checkType == PHONE_CACHEDNODETYPE) {
2746                             const UChar* store = findState.mStore;
2747                             *exported = String(store);
2748                         } else {
2749                             Node* temp = textNode;
2750                             length = 1;
2751                             start = walk->mStart;
2752                             exported->truncate(0);
2753                             do {
2754                                 Text* tempText = static_cast<Text*>(temp);
2755                                 StringImpl* string = tempText->dataImpl();
2756                                 int end = tempText == walk->mFinalNode ?
2757                                     walk->mEnd : string->length();
2758                                 exported->append(String(string->substring(
2759                                     start, end - start)));
2760                                 ASSERT(end > start);
2761                                 length += end - start + 1;
2762                                 if (temp == walk->mFinalNode)
2763                                     break;
2764                                 start = 0;
2765                                 do {
2766                                     temp = temp->traverseNextNode();
2767                                     ASSERT(temp);
2768                                 } while (temp->isTextNode() == false);
2769                                 // add a space in between text nodes to avoid
2770                                 // words collapsing together
2771                                 exported->append(" ");
2772                             } while (true);
2773                         }
2774                         foundBetter = true;
2775                     }
2776                     goto tryNextCheckType;
2777                 } else if (findState.mContinuationNode)
2778                     break;
2779                 if (inlineTextBox == NULL)
2780                     break;
2781                 inlineTextBox = inlineTextBox->nextTextBox();
2782                 if (inlineTextBox == NULL)
2783                     break;
2784                 start = inlineTextBox->start();
2785                 if (state == FOUND_PARTIAL && node == textNode)
2786                     findState.mContinuationNode = false;
2787             } while (true);
2788             if (state == FOUND_NONE)
2789                 break;
2790             // search for next text node, if any
2791             Text* nextNode;
2792             do {
2793                 do {
2794                     do {
2795                         if (node)
2796                             node = node->traverseNextNode();
2797                         if (node == NULL || node->hasTagName(HTMLNames::aTag)
2798                                 || node->hasTagName(HTMLNames::inputTag)
2799                                 || node->hasTagName(HTMLNames::textareaTag)) {
2800                             if (state == FOUND_PARTIAL &&
2801                                     checkType == ADDRESS_CACHEDNODETYPE &&
2802                                     findState.mProgress == ZIP_CODE &&
2803                                     findState.mNumberCount == 0) {
2804                                 baseChars = NULL;
2805                                 inlineTextBox = NULL;
2806                                 start = 0;
2807                                 findState.mProgress = FIND_STREET;
2808                                 goto finalNode;
2809                             }
2810                             goto tryNextCheckType;
2811                         }
2812                     } while (node->isTextNode() == false);
2813                     nextNode = static_cast<Text*>(node);
2814                     renderer = (RenderText*) nextNode->renderer();
2815                 } while (renderer == NULL);
2816                 baseInline = renderer->firstTextBox();
2817             } while (baseInline == NULL);
2818             string = nextNode->dataImpl();
2819             baseChars = string->characters();
2820             inlineTextBox = baseInline;
2821             start = inlineTextBox->start();
2822         finalNode:
2823             findState.mEndResult = 0;
2824         } while (true);
2825 tryNextCheckType:
2826         node = textNode;
2827         baseInline = saveInline;
2828         string = textNode->dataImpl();
2829         baseChars = string->characters();
2830     }
2831     if (foundBetter) {
2832         CachedNodeType temp = *type;
2833         switch (temp) {
2834             case ADDRESS_CACHEDNODETYPE: {
2835                 static const char geoString[] = "geo:0,0?q=";
2836                 exported->insert(String(geoString), 0);
2837                 int index = sizeof(geoString) - 1;
2838                 String escapedComma("%2C");
2839                 while ((index = exported->find(',', index)) >= 0)
2840                     exported->replace(index, 1, escapedComma);
2841                 } break;
2842             case EMAIL_CACHEDNODETYPE: {
2843                 String encoded = WebCore::encodeWithURLEscapeSequences(*exported);
2844                 exported->swap(encoded);
2845                 exported->insert(WTF::String("mailto:"), 0);
2846                 } break;
2847             case PHONE_CACHEDNODETYPE:
2848                 exported->insert(WTF::String("tel:"), 0);
2849                 break;
2850             default:
2851                 break;
2852         }
2853         return true;
2854     }
2855 noTextMatch:
2856     walk->reset();
2857     return false;
2858 }
2859
2860 bool CacheBuilder::IsMailboxChar(UChar ch)
2861 {
2862     // According to http://en.wikipedia.org/wiki/Email_address
2863     // ! # $ % & ' * + - . / 0-9 = ?
2864     // A-Z ^ _
2865     // ` a-z { | } ~
2866     static const unsigned body[] = {0xa3ffecfa, 0xc7fffffe, 0x7fffffff};
2867     ch -= 0x20;
2868     if (ch > '~' - 0x20)
2869         return false;
2870     return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0;
2871 }
2872
2873 bool CacheBuilder::setData(CachedFrame* cachedFrame)
2874 {
2875     Frame* frame = FrameAnd(this);
2876     Document* doc = frame->document();
2877     if (doc == NULL)
2878         return false;
2879     RenderObject* renderer = doc->renderer();
2880     if (renderer == NULL)
2881         return false;
2882     RenderLayer* layer = renderer->enclosingLayer();
2883     if (layer == NULL)
2884         return false;
2885     if (layer->width() == 0 || layer->height() == 0)
2886         return false;
2887     if (!frame->view())
2888         return false;
2889     int x, y;
2890     GetGlobalOffset(frame, &x, &y);
2891     WebCore::IntRect viewBounds = frame->view()->platformWidget()->getBounds();
2892     if ((x | y) != 0)
2893         viewBounds.setLocation(WebCore::IntPoint(x, y));
2894     cachedFrame->setLocalViewBounds(viewBounds);
2895     cachedFrame->setContentsSize(layer->scrollWidth(), layer->scrollHeight());
2896     if (cachedFrame->childCount() == 0)
2897         return true;
2898     CachedFrame* lastCachedFrame = cachedFrame->lastChild();
2899     cachedFrame = cachedFrame->firstChild();
2900     do {
2901         CacheBuilder* cacheBuilder = Builder((Frame* )cachedFrame->framePointer());
2902         cacheBuilder->setData(cachedFrame);
2903     } while (cachedFrame++ != lastCachedFrame);
2904     return true;
2905 }
2906
2907 #if USE(ACCELERATED_COMPOSITING)
2908 void CacheBuilder::TrackLayer(WTF::Vector<LayerTracker>& layerTracker,
2909     RenderObject* nodeRenderer, Node* lastChild, int offsetX, int offsetY)
2910 {
2911     RenderLayer* layer = nodeRenderer->enclosingLayer();
2912     RenderLayerBacking* back = layer->backing();
2913     if (!back)
2914         return;
2915     GraphicsLayer* grLayer = back->graphicsLayer();
2916     if (back->hasContentsLayer())
2917         grLayer = back->foregroundLayer();
2918     if (!grLayer)
2919         return;
2920     LayerAndroid* aLayer = grLayer->platformLayer();
2921     if (!aLayer)
2922         return;
2923     IntPoint scroll(layer->scrollXOffset(), layer->scrollYOffset());
2924 #if ENABLE(ANDROID_OVERFLOW_SCROLL)
2925     // If this is an overflow element, track the content layer.
2926     if (layer->hasOverflowScroll() && aLayer->getChild(0))
2927         aLayer = aLayer->getChild(0)->getChild(0);
2928     if (!aLayer)
2929         return;
2930     // Prevent a crash when scrolling a layer that does not have a parent.
2931     if (layer->stackingContext())
2932         layer->scrollToOffset(0, 0);
2933 #endif
2934     layerTracker.grow(layerTracker.size() + 1);
2935     LayerTracker& indexTracker = layerTracker.last();
2936     indexTracker.mLayer = aLayer;
2937     indexTracker.mRenderLayer = layer;
2938     indexTracker.mBounds = enclosingIntRect(aLayer->bounds());
2939     // Use the absolute location of the layer as the bounds location.  This
2940     // provides the original offset of nodes in the layer so that we can
2941     // translate nodes between their original location and the layer's new
2942     // location.
2943     indexTracker.mBounds.setLocation(layer->absoluteBoundingBox().location());
2944     indexTracker.mBounds.move(offsetX, offsetY);
2945     indexTracker.mScroll = scroll;
2946     indexTracker.mLastChild = OneAfter(lastChild);
2947     DBG_NAV_LOGD("layer=%p [%d] bounds=(%d,%d,w=%d,h=%d)", aLayer,
2948         aLayer->uniqueId(), indexTracker.mBounds.x(), indexTracker.mBounds.y(),
2949         indexTracker.mBounds.width(), indexTracker.mBounds.height());
2950 }
2951 #endif
2952
2953 bool CacheBuilder::validNode(Frame* startFrame, void* matchFrame,
2954         void* matchNode)
2955 {
2956     if (matchFrame == startFrame) {
2957         if (matchNode == NULL)
2958             return true;
2959         Node* node = startFrame->document();
2960         while (node != NULL) {
2961             if (node == matchNode) {
2962                 const IntRect& rect = node->hasTagName(HTMLNames::areaTag) ?
2963                     getAreaRect(static_cast<HTMLAreaElement*>(node)) : node->getRect();
2964                 // Consider nodes with empty rects that are not at the origin
2965                 // to be valid, since news.google.com has valid nodes like this
2966                 if (rect.x() == 0 && rect.y() == 0 && rect.isEmpty())
2967                     return false;
2968                 return true;
2969             }
2970             node = node->traverseNextNode();
2971         }
2972         DBG_NAV_LOGD("frame=%p valid node=%p invalid\n", matchFrame, matchNode);
2973         return false;
2974     }
2975     Frame* child = startFrame->tree()->firstChild();
2976     while (child) {
2977         bool result = validNode(child, matchFrame, matchNode);
2978         if (result)
2979             return result;
2980         child = child->tree()->nextSibling();
2981     }
2982 #if DEBUG_NAV_UI
2983     if (startFrame->tree()->parent() == NULL)
2984         DBG_NAV_LOGD("frame=%p node=%p false\n", matchFrame, matchNode);
2985 #endif
2986     return false;
2987 }
2988
2989 static int Area(const IntRect& rect)
2990 {
2991     return rect.width() * rect.height();
2992 }
2993
2994 bool CacheBuilder::AddPartRect(IntRect& bounds, int x, int y,
2995     WTF::Vector<IntRect>* result, IntRect* focusBounds)
2996 {
2997     if (bounds.isEmpty())
2998         return true;
2999     bounds.move(x, y);
3000     if (bounds.maxX() <= 0 || bounds.maxY() <= 0)
3001         return true;
3002     IntRect* work = result->begin() - 1;
3003     IntRect* end = result->end();
3004     while (++work < end) {
3005         if (work->contains(bounds))
3006             return true;
3007         if (bounds.contains(*work)) {
3008             *work = bounds;
3009             focusBounds->unite(bounds);
3010             return true;
3011         }
3012         if ((bounds.x() != work->x() || bounds.width() != work->width()) &&
3013                (bounds.y() != work->y() || bounds.height() != work->height()))
3014             continue;
3015         IntRect test = *work;
3016         test.unite(bounds);
3017         if (Area(test) > Area(*work) + Area(bounds))
3018             continue;
3019         *work = test;
3020         focusBounds->unite(bounds);
3021         return true;
3022     }
3023     if (result->size() >= MAXIMUM_FOCUS_RING_COUNT)
3024         return false;
3025     result->append(bounds);
3026     if (focusBounds->isEmpty())
3027         *focusBounds = bounds;
3028     else
3029         focusBounds->unite(bounds);
3030     return true;
3031 }
3032
3033 bool CacheBuilder::ConstructPartRects(Node* node, const IntRect& bounds,
3034     IntRect* focusBounds, int x, int y, WTF::Vector<IntRect>* result,
3035     int* imageCountPtr)
3036 {
3037     WTF::Vector<ClipColumnTracker> clipTracker(1);
3038     ClipColumnTracker* baseTracker = clipTracker.data(); // sentinel
3039     bzero(baseTracker, sizeof(ClipColumnTracker));
3040     if (node->hasChildNodes() && node->hasTagName(HTMLNames::buttonTag) == false
3041             && node->hasTagName(HTMLNames::selectTag) == false) {
3042         // collect all text rects from first to last child
3043         Node* test = node->firstChild();
3044         Node* last = NULL;
3045         Node* prior = node;
3046         while ((prior = prior->lastChild()) != NULL)
3047             last = prior;
3048         ASSERT(last != NULL);
3049         bool nodeIsAnchor = node->hasTagName(HTMLNames::aTag);
3050         do {
3051             do {
3052                 const ClipColumnTracker* lastClip = &clipTracker.last();
3053                 if (test != lastClip->mLastChild)
3054                     break;
3055                 clipTracker.removeLast();
3056             } while (true);
3057             RenderObject* renderer = test->renderer();
3058             if (renderer == NULL)
3059                 continue;
3060             EVisibility vis = renderer->style()->visibility();
3061             if (vis == HIDDEN)
3062                 continue;
3063             bool hasClip = renderer->hasOverflowClip();
3064             size_t clipIndex = clipTracker.size();
3065             IntRect clipBounds = IntRect(0, 0, INT_MAX, INT_MAX);
3066             if (hasClip || --clipIndex > 0) {
3067                 clipBounds = hasClip ? renderer->absoluteBoundingBoxRect() :
3068                     clipTracker.at(clipIndex).mBounds; // x, y fixup done by ConstructTextRect
3069             }
3070             if (test->isTextNode()) {
3071                 RenderText* renderText = (RenderText*) renderer;
3072                 InlineTextBox *textBox = renderText->firstTextBox();
3073                 if (textBox == NULL)
3074                     continue;
3075                 if (ConstructTextRect((Text*) test, textBox, 0, INT_MAX,
3076                         x, y, focusBounds, clipBounds, result) == false) {
3077                     return false;
3078                 }
3079                 continue;
3080             }
3081             if (test->hasTagName(HTMLNames::imgTag)) {
3082                 IntRect bounds = test->getRect();
3083                 bounds.intersect(clipBounds);
3084                 if (AddPartRect(bounds, x, y, result, focusBounds) == false)
3085                     return false;
3086                 *imageCountPtr += 1;
3087                 continue;
3088             }
3089             if (hasClip == false) {
3090                 if (nodeIsAnchor && test->hasTagName(HTMLNames::divTag)) {
3091                     IntRect bounds = renderer->absoluteBoundingBoxRect();  // x, y fixup done by AddPartRect
3092                     RenderBox* renderBox = static_cast<RenderBox*>(renderer);
3093                     int left = bounds.x() + renderBox->paddingLeft() + renderBox->borderLeft();
3094                     int top = bounds.y() + renderBox->paddingTop() + renderBox->borderTop();
3095                     int right = bounds.maxX() - renderBox->paddingRight() - renderBox->borderRight();
3096                     int bottom = bounds.maxY() - renderBox->paddingBottom() - renderBox->borderBottom();
3097                     if (left >= right || top >= bottom)
3098                         continue;
3099                     bounds = IntRect(left, top, right - left, bottom - top);
3100                     if (AddPartRect(bounds, x, y, result, focusBounds) == false)
3101                         return false;
3102                 }
3103                 continue;
3104             }
3105             Node* lastChild = test->lastChild();
3106             if (lastChild == NULL)
3107                 continue;
3108             clipTracker.grow(clipTracker.size() + 1);
3109             ClipColumnTracker& clip = clipTracker.last();
3110             clip.mBounds = renderer->absoluteBoundingBoxRect(); // x, y fixup done by ConstructTextRect
3111             clip.mLastChild = OneAfter(lastChild);
3112             clip.mNode = test;
3113         } while (test != last && (test = test->traverseNextNode()) != NULL);
3114     }
3115     if (result->size() == 0 || focusBounds->width() < MINIMUM_FOCUSABLE_WIDTH
3116             || focusBounds->height() < MINIMUM_FOCUSABLE_HEIGHT) {
3117         if (bounds.width() < MINIMUM_FOCUSABLE_WIDTH)
3118             return false;
3119         if (bounds.height() < MINIMUM_FOCUSABLE_HEIGHT)
3120             return false;
3121         result->append(bounds);
3122         *focusBounds = bounds;
3123     }
3124     return true;
3125 }
3126
3127 static inline bool isNotSpace(UChar c)
3128 {
3129     return c <= 0xA0 ? isUnicodeSpace(c) == false :
3130         WTF::Unicode::direction(c) != WTF::Unicode::WhiteSpaceNeutral;
3131 }
3132
3133 bool CacheBuilder::ConstructTextRect(Text* textNode,
3134     InlineTextBox* textBox, int start, int relEnd, int x, int y,
3135     IntRect* focusBounds, const IntRect& clipBounds, WTF::Vector<IntRect>* result)
3136 {
3137     RenderText* renderText = (RenderText*) textNode->renderer();
3138     EVisibility vis = renderText->style()->visibility();
3139     StringImpl* string = textNode->dataImpl();
3140     const UChar* chars = string->characters();
3141     FloatPoint pt = renderText->localToAbsolute();
3142     do {
3143         int textBoxStart = textBox->start();
3144         int textBoxEnd = textBoxStart + textBox->len();
3145         if (textBoxEnd <= start)
3146             continue;
3147         if (textBoxEnd > relEnd)
3148             textBoxEnd = relEnd;
3149         IntRect bounds = textBox->selectionRect((int) pt.x(), (int) pt.y(),
3150             start, textBoxEnd);
3151         bounds.intersect(clipBounds);
3152         if (bounds.isEmpty())
3153             continue;
3154         bool drawable = false;
3155         for (int index = start; index < textBoxEnd; index++)
3156             if ((drawable |= isNotSpace(chars[index])) != false)
3157                 break;
3158         if (drawable && vis != HIDDEN) {
3159             if (AddPartRect(bounds, x, y, result, focusBounds) == false)
3160                 return false;
3161         }
3162         if (textBoxEnd == relEnd)
3163             break;
3164     } while ((textBox = textBox->nextTextBox()) != NULL);
3165     return true;
3166 }
3167
3168 bool CacheBuilder::ConstructTextRects(Text* node, int start,
3169     Text* last, int end, int x, int y, IntRect* focusBounds,
3170     const IntRect& clipBounds, WTF::Vector<IntRect>* result)
3171 {
3172     result->clear();
3173     *focusBounds = IntRect(0, 0, 0, 0);
3174     do {
3175         RenderText* renderText = (RenderText*) node->renderer();
3176         int relEnd = node == last ? end : renderText->textLength();
3177         InlineTextBox *textBox = renderText->firstTextBox();
3178         if (textBox != NULL) {
3179             do {
3180                 if ((int) textBox->end() >= start)
3181                     break;
3182             } while ((textBox = textBox->nextTextBox()) != NULL);
3183             if (textBox && ConstructTextRect(node, textBox, start, relEnd,
3184                     x, y, focusBounds, clipBounds, result) == false)
3185                 return false;
3186         }
3187         start = 0;
3188         do {
3189             if (node == last)
3190                 return true;
3191             node = (Text*) node->traverseNextNode();
3192             ASSERT(node != NULL);
3193         } while (node->isTextNode() == false || node->renderer() == NULL);
3194     } while (true);
3195 }
3196
3197 }