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