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