2 * Copyright 2006, The Android Open Source Project
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
26 #include "CachedPrefix.h"
27 #include "CachedNode.h"
28 #include "CachedRoot.h"
29 #include "ColumnInfo.h"
31 #include "EventListener.h"
32 #include "EventNames.h"
34 #include "FrameLoader.h"
35 #include "FrameLoaderClientAndroid.h"
36 #include "FrameTree.h"
37 #include "FrameView.h"
38 //#include "GraphicsContext.h"
39 #include "HTMLAreaElement.h"
40 #include "HTMLImageElement.h"
41 #include "HTMLInputElement.h"
42 #include "HTMLMapElement.h"
43 #include "HTMLNames.h"
44 #include "HTMLOptionElement.h"
45 #include "HTMLSelectElement.h"
46 #include "HTMLTextAreaElement.h"
47 #include "InlineTextBox.h"
49 #include "LayerAndroid.h"
50 #include "PluginView.h"
51 #include "RegisteredEventListener.h"
52 #include "RenderImage.h"
53 #include "RenderInline.h"
54 #include "RenderLayerBacking.h"
55 #include "RenderListBox.h"
56 #include "RenderSkinCombo.h"
57 #include "RenderTextControl.h"
58 #include "RenderView.h"
59 #include "RenderWidget.h"
63 #include "WebCoreFrameBridge.h"
64 #include "WebCoreViewBridge.h"
66 #include <wtf/unicode/Unicode.h>
68 #ifdef DUMP_NAV_CACHE_USING_PRINTF
69 FILE* gNavCacheLogFile = NULL;
70 android::Mutex gWriteLogMutex;
73 #include "CacheBuilder.h"
75 #define MINIMUM_FOCUSABLE_WIDTH 3
76 #define MINIMUM_FOCUSABLE_HEIGHT 3
77 #define MAXIMUM_FOCUS_RING_COUNT 32
81 CacheBuilder* CacheBuilder::Builder(Frame* frame) {
82 return &((FrameLoaderClientAndroid*) frame->loader()->client())->getCacheBuilder();
85 Frame* CacheBuilder::FrameAnd(CacheBuilder* cacheBuilder) {
86 FrameLoaderClientAndroid* loader = (FrameLoaderClientAndroid*)
87 ((char*) cacheBuilder - OFFSETOF(FrameLoaderClientAndroid, m_cacheBuilder));
88 return loader->getFrame();
91 Frame* CacheBuilder::FrameAnd(const CacheBuilder* cacheBuilder) {
92 FrameLoaderClientAndroid* loader = (FrameLoaderClientAndroid*)
93 ((char*) cacheBuilder - OFFSETOF(FrameLoaderClientAndroid, m_cacheBuilder));
94 return loader->getFrame();
97 CacheBuilder::LayerTracker::~LayerTracker() {
98 // Check for a stacking context to prevent a crash in layers without a
100 if (mRenderLayer && mRenderLayer->stackingContext())
101 // Restore the scroll position of the layer. Does not affect layers
102 // without overflow scroll as the layer will not be scrolled.
103 mRenderLayer->scrollToOffset(mScroll.x(), mScroll.y());
108 static bool hasEventListener(Node* node, const AtomicString& eventType) {
109 if (!node->isElementNode())
111 Element* element = static_cast<Element*>(node);
112 EventListener* listener = element->getAttributeEventListener(eventType);
113 return 0 != listener;
116 #define DEBUG_BUFFER_SIZE 256
117 #define DEBUG_WRAP_SIZE 150
118 #define DEBUG_WRAP_MAX 170
120 Frame* CacheBuilder::Debug::frameAnd() const {
121 CacheBuilder* nav = (CacheBuilder*) ((char*) this - OFFSETOF(CacheBuilder, mDebug));
122 return CacheBuilder::FrameAnd(nav);
125 void CacheBuilder::Debug::attr(const AtomicString& name, const AtomicString& value) {
126 if (name.isNull() || name.isEmpty() || value.isNull() || value.isEmpty())
128 uChar(name.characters(), name.length(), false);
130 wideString(value.characters(), value.length(), false);
134 void CacheBuilder::Debug::comma(const char* str) {
139 void CacheBuilder::Debug::flush() {
143 if (limit < DEBUG_WRAP_SIZE)
145 if (limit < DEBUG_WRAP_MAX)
148 limit = DEBUG_WRAP_MAX;
149 len = DEBUG_WRAP_SIZE;
150 while (len < limit) {
151 char test = mBuffer[len];
152 if (test < '/' || (test > '9' && test < 'A') || (test > 'Z' && test < 'a') || test > 'z')
156 while (len > 0 && mBuffer[len - 1] == '\\')
158 while (mBuffer[len] == '"')
161 const char* prefix = mPrefix;
162 if (prefix[0] == '\"') {
163 // see if we're inside a quote
165 for (int index = 0; index < len; index++) {
166 if (mBuffer[index] == '\\') {
170 if (mBuffer[index] == '\n') {
174 if (mBuffer[index] == '"')
177 if ((quoteCount & 1) == 0)
180 DUMP_NAV_LOGD("%.*s", len, mBuffer);
181 int copy = mIndex - len;
182 strcpy(mBuffer, prefix);
183 memcpy(&mBuffer[strlen(prefix)], &mBuffer[len], copy);
184 mIndex = strlen(prefix) + copy;
188 void CacheBuilder::Debug::frameName(char*& namePtr, const char* max) const {
191 Frame* frame = frameAnd();
192 Frame* parent = frame->tree()->parent();
194 Builder(parent)->mDebug.frameName(namePtr, max);
195 const AtomicString& name = frame->tree()->name();
196 if (name.length() == 0)
199 if (name.startsWith(AtomicString("opener")))
201 for (; index < name.length(); index++) {
202 char ch = name[index];
205 if (WTF::isASCIIAlphanumeric(ch) || ch == '_')
210 void CacheBuilder::Debug::frames() {
211 Frame* frame = frameAnd();
212 Document* doc = frame->document();
215 bool top = frame->tree()->parent() == NULL;
217 #ifdef DUMP_NAV_CACHE_USING_PRINTF
218 gWriteLogMutex.lock();
219 ASSERT(gNavCacheLogFile == NULL);
220 gNavCacheLogFile = fopen(NAV_CACHE_LOG_FILE, "a");
224 Frame* child = frame->tree()->firstChild();
225 bool hasChild = child != NULL;
227 DUMP_NAV_LOGD("\nnamespace TEST_SPACE {\n\n");
229 Builder(child)->mDebug.frames();
230 child = child->tree()->nextSibling();
233 child = frame->tree()->firstChild();
236 char* childNamePtr = childName;
237 Builder(child)->mDebug.frameName(childNamePtr, childNamePtr + sizeof(childName) - 1);
238 *childNamePtr = '\0';
239 if (child == frame->tree()->firstChild())
240 DUMP_NAV_LOGD("DebugTestFrameGroup TEST%s_GROUP[] = {\n", childName);
241 Frame* next = child->tree()->nextSibling();
242 Document* doc = child->document();
244 RenderObject* renderer = doc->renderer();
245 if (renderer != NULL) {
246 RenderLayer* layer = renderer->enclosingLayer();
249 DUMP_NAV_LOGD("TEST%s_RECTS, ", childName);
250 DUMP_NAV_LOGD("TEST%s_RECT_COUNT, ", childName);
251 DUMP_NAV_LOGD("TEST%s_RECTPARTS, ", childName);
252 DUMP_NAV_LOGD("TEST%s_BOUNDS,\n", childName);
253 DUMP_NAV_LOGD("TEST%s_WIDTH, ", childName);
254 DUMP_NAV_LOGD("TEST%s_HEIGHT,\n", childName);
255 DUMP_NAV_LOGD("0, 0, 0, 0,\n");
256 DUMP_NAV_LOGD("TEST%s_FOCUS, ", childName);
257 Frame* grandChild = child->tree()->firstChild();
259 char grandChildName[256];
260 char* grandChildNamePtr = grandChildName;
261 Builder(grandChild)->mDebug.frameName(grandChildNamePtr,
262 grandChildNamePtr + sizeof(grandChildName) - 1);
263 *grandChildNamePtr = '\0';
264 DUMP_NAV_LOGD("TEST%s_GROUP, ", grandChildName);
265 DUMP_NAV_LOGD("sizeof(TEST%s_GROUP) / sizeof(DebugTestFrameGroup), ", grandChildName);
267 DUMP_NAV_LOGD("NULL, 0, ");
268 DUMP_NAV_LOGD("\"%s\"\n", childName);
269 DUMP_NAV_LOGD("}%c\n", next ? ',' : ' ');
275 DUMP_NAV_LOGD("};\n");
279 DUMP_NAV_LOGD("\n} // end of namespace\n\n");
281 char* frameNamePtr = name;
282 frameName(frameNamePtr, frameNamePtr + sizeof(name) - 1);
283 *frameNamePtr = '\0';
284 DUMP_NAV_LOGD("DebugTestFrameGroup TEST%s_GROUP = {\n", name);
285 DUMP_NAV_LOGD("TEST%s_RECTS, ", name);
286 DUMP_NAV_LOGD("TEST%s_RECT_COUNT, ", name);
287 DUMP_NAV_LOGD("TEST%s_RECTPARTS, ", name);
288 DUMP_NAV_LOGD("TEST%s_BOUNDS,\n", name);
289 DUMP_NAV_LOGD("TEST%s_WIDTH, ", name);
290 DUMP_NAV_LOGD("TEST%s_HEIGHT,\n", name);
291 DUMP_NAV_LOGD("TEST%s_MAX_H, ", name);
292 DUMP_NAV_LOGD("TEST%s_MIN_H, ", name);
293 DUMP_NAV_LOGD("TEST%s_MAX_V, ", name);
294 DUMP_NAV_LOGD("TEST%s_MIN_V,\n", name);
295 DUMP_NAV_LOGD("TEST%s_FOCUS, ", name);
297 child = frame->tree()->firstChild();
299 char* childNamePtr = childName;
300 Builder(child)->mDebug.frameName(childNamePtr, childNamePtr + sizeof(childName) - 1);
301 *childNamePtr = '\0';
302 DUMP_NAV_LOGD("TEST_SPACE::TEST%s_GROUP, ", childName);
303 DUMP_NAV_LOGD("sizeof(TEST_SPACE::TEST%s_GROUP) / sizeof(DebugTestFrameGroup), \n" ,childName);
305 DUMP_NAV_LOGD("NULL, 0, ");
306 DUMP_NAV_LOGD("\"%s\"\n", name);
307 DUMP_NAV_LOGD("};\n");
308 #ifdef DUMP_NAV_CACHE_USING_PRINTF
309 if (gNavCacheLogFile)
310 fclose(gNavCacheLogFile);
311 gNavCacheLogFile = NULL;
312 gWriteLogMutex.unlock();
317 void CacheBuilder::Debug::init(char* buffer, size_t size) {
324 void CacheBuilder::Debug::groups() {
325 Frame* frame = frameAnd();
326 Frame* child = frame->tree()->firstChild();
327 bool hasChild = child != NULL;
328 if (frame->tree()->parent() == NULL && hasChild)
329 DUMP_NAV_LOGD("namespace TEST_SPACE {\n\n");
331 Builder(child)->mDebug.groups();
332 child = child->tree()->nextSibling();
334 if (frame->tree()->parent() == NULL && hasChild)
335 DUMP_NAV_LOGD("\n} // end of namespace\n\n");
336 Document* doc = frame->document();
338 char* frameNamePtr = name;
339 frameName(frameNamePtr, frameNamePtr + sizeof(name) - 1);
340 *frameNamePtr = '\0';
342 DUMP_NAV_LOGD("// %s has no document\n", name);
345 RenderObject* renderer = doc->renderer();
346 if (renderer == NULL) {
347 DUMP_NAV_LOGD("// %s has no renderer\n", name);
350 RenderLayer* layer = renderer->enclosingLayer();
352 DUMP_NAV_LOGD("// %s has no enclosingLayer\n", name);
356 Node* focus = doc->focusedNode();
357 bool atLeastOne = false;
359 if ((atLeastOne |= isFocusable(node)) != false)
361 } while ((node = node->traverseNextNode()) != NULL);
363 if (atLeastOne == false) {
364 DUMP_NAV_LOGD("static DebugTestNode TEST%s_RECTS[] = {\n"
365 "{{0, 0, 0, 0}, \"\", 0, -1, \"\", {0, 0, 0, 0}, false, 0}\n"
367 DUMP_NAV_LOGD("static int TEST%s_RECT_COUNT = 1;"
368 " // no focusable nodes\n", name);
369 DUMP_NAV_LOGD("#define TEST%s_RECTPARTS NULL\n", name);
373 DUMP_NAV_LOGD("static DebugTestNode TEST%s_RECTS[] = {\n", name);
376 if (hasEventListener(node, eventNames().clickEvent))
377 properties.append("ONCLICK | ");
378 if (hasEventListener(node, eventNames().mousedownEvent))
379 properties.append("MOUSEDOWN | ");
380 if (hasEventListener(node, eventNames().mouseupEvent))
381 properties.append("MOUSEUP | ");
382 if (hasEventListener(node, eventNames().mouseoverEvent))
383 properties.append("MOUSEOVER | ");
384 if (hasEventListener(node, eventNames().mouseoutEvent))
385 properties.append("MOUSEOUT | ");
386 if (hasEventListener(node, eventNames().keydownEvent))
387 properties.append("KEYDOWN | ");
388 if (hasEventListener(node, eventNames().keyupEvent))
389 properties.append("KEYUP | ");
390 if (CacheBuilder::HasFrame(node))
391 properties.append("FRAME | ");
393 properties.append("FOCUS | ");
396 if (node->isKeyboardFocusable(NULL))
397 properties.append("KEYBOARD_FOCUSABLE | ");
398 if (node->isMouseFocusable())
399 properties.append("MOUSE_FOCUSABLE | ");
400 if (node->isFocusable())
401 properties.append("SIMPLE_FOCUSABLE | ");
402 if (properties.isEmpty())
403 properties.append("0");
405 properties.truncate(properties.length() - 3);
406 IntRect rect = node->getRect();
407 if (node->hasTagName(HTMLNames::areaTag))
408 rect = getAreaRect(static_cast<HTMLAreaElement*>(node));
409 char buffer[DEBUG_BUFFER_SIZE];
410 memset(buffer, 0, sizeof(buffer));
412 mBufferSize = sizeof(buffer);
414 mIndex = snprintf(buffer, sizeof(buffer), "{{%d, %d, %d, %d}, ", rect.x(), rect.y(),
415 rect.width(), rect.height());
417 uChar(properties.characters(), properties.length(), false);
419 int parentIndex = ParentIndex(node, count, node->parentNode());
421 snprintf(scratch, sizeof(scratch), "%d", parentIndex);
423 Element* element = static_cast<Element*>(node);
424 if (node->isElementNode() && element->hasID())
425 wideString(element->getIdAttribute());
426 else if (node->isTextNode()) {
427 #if 01 // set to one to abbreviate text that can be omitted from the address detection code
428 if (rect.isEmpty() && node->textContent().length() > 100) {
429 wideString(node->textContent().characters(), 100, false);
430 snprintf(scratch, sizeof(scratch), "/* + %d bytes */",
431 node->textContent().length() - 100);
435 wideString(node->textContent().characters(), node->textContent().length(), true);
436 } else if (node->hasTagName(HTMLNames::aTag) ||
437 node->hasTagName(HTMLNames::areaTag))
439 HTMLAnchorElement* anchor = static_cast<HTMLAnchorElement*>(node);
440 wideString(anchor->href());
441 } else if (node->hasTagName(HTMLNames::imgTag)) {
442 HTMLImageElement* image = static_cast<HTMLImageElement*>(node);
443 wideString(image->src());
446 RenderObject* renderer = node->renderer();
447 int tabindex = node->isElementNode() ? node->tabIndex() : 0;
448 RenderLayer* layer = 0;
450 const IntRect& absB = renderer->absoluteBoundingBoxRect();
451 bool hasLayer = renderer->hasLayer();
452 layer = hasLayer ? toRenderBoxModelObject(renderer)->layer() : 0;
453 snprintf(scratch, sizeof(scratch), ", {%d, %d, %d, %d}, %s"
455 absB.x(), absB.y(), absB.width(), absB.height(),
456 renderer->hasOverflowClip() ? "true" : "false", tabindex,
457 hasLayer ? "true" : "false",
458 hasLayer && layer->isComposited() ? "true" : "false");
459 // TODO: add renderer->style()->visibility()
462 print(", {0, 0, 0, 0}, false, 0},");
465 snprintf(scratch, sizeof(scratch), "// %d: ", count);
468 //print(renderer ? renderer->information().ascii() : "NO_RENDER_INFO");
469 if (node->isElementNode()) {
470 Element* element = static_cast<Element*>(node);
471 NamedNodeMap* attrs = element->attributes();
472 unsigned length = attrs->length();
476 for (unsigned i = 0; i < length; i++) {
477 Attribute* a = attrs->attributeItem(i);
478 attr(a->localName(), a->value());
483 RenderStyle* style = renderer->style();
484 snprintf(scratch, sizeof(scratch), "// renderStyle:"
485 " visibility=%s hasBackGround=%d"
486 " tapHighlightColor().alpha()=0x%02x"
487 " isTransparent()=%s",
488 style->visibility() == HIDDEN ? "HIDDEN" : "VISIBLE",
489 renderer->hasBackground(), style->tapHighlightColor().alpha(),
490 renderer->isTransparent() ? "true" : "false");
493 RenderBlock* renderBlock = static_cast<RenderBlock*>(renderer);
494 if (renderer->isRenderBlock() && renderBlock->hasColumns()) {
495 const RenderBox* box = static_cast<RenderBox*>(renderer);
496 const IntRect& oRect = box->visibleOverflowRect();
497 snprintf(scratch, sizeof(scratch), "// renderBlock:"
498 " columnCount=%d columnGap=%d direction=%d"
499 " hasOverflowClip=%d overflow=(%d,%d,w=%d,h=%d)",
500 renderBlock->columnInfo()->columnCount(), renderBlock->columnGap(),
501 renderBlock->style()->direction(), renderer->hasOverflowClip(),
502 oRect.x(), oRect.y(), oRect.width(), oRect.height());
507 #if USE(ACCELERATED_COMPOSITING)
508 if (renderer && renderer->hasLayer()) {
509 RenderLayer* layer = toRenderBoxModelObject(renderer)->layer();
510 RenderLayerBacking* back = layer->backing();
511 GraphicsLayer* grLayer = back ? back->graphicsLayer() : 0;
512 LayerAndroid* aLayer = grLayer ? grLayer->platformLayer() : 0;
513 const SkPicture* pict = aLayer ? aLayer->picture() : 0;
514 const IntRect& r = renderer->absoluteBoundingBoxRect();
515 snprintf(scratch, sizeof(scratch), "// layer:%p back:%p"
516 " gLayer:%p aLayer:%p pict:%p r:(%d,%d,w=%d,h=%d)",
517 layer, back, grLayer, aLayer, pict, r.x(), r.y(),
518 r.width(), r.height());
525 } while ((node = node->traverseNextNode()) != NULL);
526 DUMP_NAV_LOGD("}; // focusables = %d\n", count - 1);
528 DUMP_NAV_LOGD("static int TEST%s_RECT_COUNT = %d;\n\n", name, count - 1);
529 // look for rects with multiple parts
532 bool hasRectParts = false;
533 int globalOffsetX, globalOffsetY;
534 GetGlobalOffset(frame, &globalOffsetX, &globalOffsetY);
537 bool _isFocusable = isFocusable(node) || (node->isTextNode()
538 && node->getRect().isEmpty() == false
540 int nodeIndex = count++;
541 if (_isFocusable == false)
543 RenderObject* renderer = node->renderer();
544 if (renderer == NULL)
546 WTF::Vector<IntRect> rects;
547 IntRect clipBounds = IntRect(0, 0, INT_MAX, INT_MAX);
548 IntRect focusBounds = IntRect(0, 0, INT_MAX, INT_MAX);
549 IntRect* rectPtr = &focusBounds;
551 if (node->isTextNode()) {
552 Text* textNode = (Text*) node;
553 if (CacheBuilder::ConstructTextRects(textNode, 0, textNode,
554 INT_MAX, globalOffsetX, globalOffsetY, rectPtr,
555 clipBounds, &rects) == false)
558 IntRect nodeBounds = node->getRect();
559 if (CacheBuilder::ConstructPartRects(node, nodeBounds, rectPtr,
560 globalOffsetX, globalOffsetY, &rects, &imageCount) == false)
563 unsigned arraySize = rects.size();
564 if (arraySize > 1 || (arraySize == 1 && (rectPtr->width() != rect.width())) ||
565 rectPtr->height() != rect.height()) {
566 if (hasRectParts == false) {
567 DUMP_NAV_LOGD("static DebugTestRectPart TEST%s_RECTPARTS[] = {\n", name);
570 if (node->isTextNode() == false) {
571 unsigned rectIndex = 0;
572 for (; rectIndex < arraySize; rectIndex++) {
573 rectPtr = &rects.at(rectIndex);
574 DUMP_NAV_LOGD("{ %d, %d, %d, %d, %d }, // %d\n", nodeIndex,
575 rectPtr->x(), rectPtr->y(), rectPtr->width(),
576 rectPtr->height(), rectIndex + 1);
579 RenderText* renderText = (RenderText*) node->renderer();
580 InlineTextBox* textBox = renderText->firstTextBox();
581 unsigned rectIndex = 0;
583 FloatPoint pt = renderText->localToAbsolute();
584 IntRect rect = textBox->selectionRect((int) pt.x(), (int) pt.y(), 0, INT_MAX);
586 mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, "{ %d, %d, %d, %d, %d",
587 nodeIndex, rect.x(), rect.y(), rect.width(), rect.height());
588 mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d, %d, %d",
589 textBox->len(), 0 /*textBox->selectionHeight()*/,
590 0 /*textBox->selectionTop()*/);
591 mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d, %d, %d",
592 0 /*textBox->spaceAdd()*/, textBox->start(), 0 /*textBox->textPos()*/);
593 mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d, %d, %d, %d",
594 textBox->x(), textBox->y(), textBox->logicalWidth(), textBox->logicalHeight());
595 int baseline = textBox->renderer()->style(textBox->isFirstLineStyle())->font().ascent();
596 mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d, %d }, // %d ",
597 baseline, imageCount, ++rectIndex);
598 wideString(node->textContent().characters() + textBox->start(), textBox->len(), true);
599 DUMP_NAV_LOGD("%.*s\n", mIndex, mBuffer);
600 textBox = textBox->nextTextBox();
604 } while ((node = node->traverseNextNode()) != NULL);
606 DUMP_NAV_LOGD("{0}\n};\n\n");
608 DUMP_NAV_LOGD("static DebugTestRectPart* TEST%s_RECTPARTS = NULL;\n", name);
610 int contentsWidth = layer->width();
611 int contentsHeight = layer->height();
612 DUMP_NAV_LOGD("static int TEST%s_FOCUS = %d;\n", name, focusIndex);
613 DUMP_NAV_LOGD("static int TEST%s_WIDTH = %d;\n", name, contentsWidth);
614 DUMP_NAV_LOGD("static int TEST%s_HEIGHT = %d;\n\n", name, contentsHeight);
617 bool CacheBuilder::Debug::isFocusable(Node* node) {
618 if (node->hasTagName(HTMLNames::areaTag))
620 if (node->renderer() == false)
622 if (node->isKeyboardFocusable(NULL))
624 if (node->isMouseFocusable())
626 if (node->isFocusable())
628 if (CacheBuilder::AnyIsClick(node))
630 if (CacheBuilder::HasTriggerEvent(node))
635 void CacheBuilder::Debug::localName(Node* node) {
636 const AtomicString& local = node->localName();
637 if (node->isTextNode())
640 wideString(local.characters(), local.length(), false);
644 void CacheBuilder::Debug::newLine(int indent) {
645 if (mPrefix[0] != '\n')
646 print(&mPrefix[0], 1);
648 int lastnewline = mIndex - 1;
649 while (lastnewline >= 0 && mBuffer[lastnewline] != '\n')
652 char* buffer = mBuffer;
653 if (lastnewline > 0) {
654 DUMP_NAV_LOGD("%.*s", lastnewline, buffer);
655 mIndex -= lastnewline;
656 buffer += lastnewline;
658 size_t prefixLen = strlen(mPrefix);
659 int minPrefix = prefixLen - 1;
660 while (minPrefix >= 0 && mPrefix[minPrefix] != '\n')
662 minPrefix = prefixLen - minPrefix - 1;
663 if (mIndex > minPrefix)
664 DUMP_NAV_LOGD("%.*s\n", mIndex, buffer);
669 int CacheBuilder::Debug::ParentIndex(Node* node, int count, Node* parent)
673 ASSERT(node != parent);
675 Node* previous = node;
678 previous = previous->traversePreviousNode();
679 } while (previous && previous != parent);
680 if (previous != NULL)
685 } while ((node = node->traverseNextNode()) != NULL && node != parent);
692 void CacheBuilder::Debug::print(const char* name) {
693 print(name, strlen(name));
696 void CacheBuilder::Debug::print(const char* name, unsigned len) {
698 if (mIndex + len >= DEBUG_BUFFER_SIZE)
700 int copyLen = mIndex + len < DEBUG_BUFFER_SIZE ?
701 len : DEBUG_BUFFER_SIZE - mIndex;
702 memcpy(&mBuffer[mIndex], name, copyLen);
707 mBuffer[mIndex] = '\0';
710 void CacheBuilder::Debug::setIndent(int indent)
713 snprintf(scratch, sizeof(scratch), "%.*s", indent,
718 void CacheBuilder::Debug::uChar(const UChar* name, unsigned len, bool hex) {
719 const UChar* end = name + len;
720 bool wroteHex = false;
722 unsigned ch = *name++;
723 if (ch == '\t' || ch == '\n' || ch == '\r' || ch == 0xa0)
725 if (ch < ' ' || ch == 0x7f) {
727 mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, "\\x%02x", ch);
730 mBuffer[mIndex++] = '?';
731 } else if (ch >= 0x80) {
734 mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex,
735 "\\x%02x\\x%02x", ch >> 6 | 0xc0, (ch & 0x3f) | 0x80);
737 mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex,
738 "\\x%02x\\x%02x\\x%02x", ch >> 12 | 0xe0,
739 (ch >> 6 & 0x3f) | 0x80, (ch & 0x3f) | 0x80);
742 mBuffer[mIndex++] = '?';
744 if (wroteHex && WTF::isASCIIHexDigit((UChar) ch))
745 mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex,
747 else if (ch == '"' || ch == '\\')
748 mBuffer[mIndex++] = '\\';
749 mBuffer[mIndex++] = ch;
752 if (mIndex + 1 >= DEBUG_BUFFER_SIZE)
758 void CacheBuilder::Debug::validateFrame() {
759 Frame* frame = frameAnd();
760 Page* page = frame->page();
762 ASSERT((int) page > 0x10000);
763 Frame* child = frame->tree()->firstChild();
765 Builder(child)->mDebug.validateFrame();
766 child = child->tree()->nextSibling();
770 void CacheBuilder::Debug::wideString(const UChar* chars, int length, bool hex) {
775 uChar(chars, length, hex);
780 void CacheBuilder::Debug::wideString(const String& str) {
781 wideString(str.characters(), str.length(), false);
784 #endif // DUMP_NAV_CACHE
786 CacheBuilder::CacheBuilder()
788 mAllowableTypes = ALL_CACHEDNODE_BITS;
789 #ifdef DUMP_NAV_CACHE_USING_PRINTF
790 gNavCacheLogFile = NULL;
794 void CacheBuilder::adjustForColumns(const ClipColumnTracker& track,
795 CachedNode* node, IntRect* bounds, RenderBlock* renderer)
797 if (!renderer->hasColumns())
801 int tx = track.mBounds.x();
802 int ty = track.mBounds.y();
803 int columnGap = track.mColumnGap;
804 size_t limit = track.mColumnInfo->columnCount();
805 for (size_t index = 0; index < limit; index++) {
806 IntRect column = renderer->columnRectAt(track.mColumnInfo, index);
808 IntRect test = *bounds;
810 if (column.contains(test)) {
817 int xOffset = column.width() + columnGap;
818 x += track.mDirection == LTR ? xOffset : -xOffset;
819 y -= column.height();
823 // Checks if a node has one of event listener types.
824 bool CacheBuilder::NodeHasEventListeners(Node* node, AtomicString* eventTypes, int length) {
825 for (int i = 0; i < length; ++i) {
826 if (!node->getEventListeners(eventTypes[i]).isEmpty())
832 bool CacheBuilder::AnyChildIsClick(Node* node)
834 AtomicString eventTypes[5] = {
835 eventNames().clickEvent,
836 eventNames().mousedownEvent,
837 eventNames().mouseupEvent,
838 eventNames().keydownEvent,
839 eventNames().keyupEvent
842 Node* child = node->firstChild();
843 while (child != NULL) {
844 if (child->isFocusable() ||
845 NodeHasEventListeners(child, eventTypes, 5))
847 if (AnyChildIsClick(child))
849 child = child->nextSibling();
854 bool CacheBuilder::AnyIsClick(Node* node)
856 if (node->hasTagName(HTMLNames::bodyTag))
857 return AnyChildIsClick(node);
859 AtomicString eventTypeSetOne[4] = {
860 eventNames().mouseoverEvent,
861 eventNames().mouseoutEvent,
862 eventNames().keydownEvent,
863 eventNames().keyupEvent
866 if (!NodeHasEventListeners(node, eventTypeSetOne, 4))
869 AtomicString eventTypeSetTwo[3] = {
870 eventNames().clickEvent,
871 eventNames().mousedownEvent,
872 eventNames().mouseupEvent
875 if (NodeHasEventListeners(node, eventTypeSetTwo, 3))
878 return AnyChildIsClick(node);
881 void CacheBuilder::buildCache(CachedRoot* root)
883 Frame* frame = FrameAnd(this);
884 mPictureSetDisabled = false;
885 BuildFrame(frame, frame, root, (CachedFrame*) root);
886 root->finishInit(); // set up frame parent pointers, child pointers
887 setData((CachedFrame*) root);
890 static Node* ParentWithChildren(Node* node)
893 while ((parent = parent->parentNode())) {
894 if (parent->childNodeCount() > 1)
901 // Probably this should check for null instead of the caller. If the
902 // Tracker object is the last thing in the dom, checking for null in the
903 // caller in some cases fails to set up Tracker state which may be useful
904 // to the nodes parsed immediately after the tracked noe.
905 static Node* OneAfter(Node* node)
908 Node* sibling = NULL;
909 while ((parent = parent->parentNode()) != NULL) {
910 sibling = parent->nextSibling();
917 // return true if this renderer is really a pluinview, and it wants
918 // key-events (i.e. focus)
919 static bool checkForPluginViewThatWantsFocus(RenderObject* renderer) {
920 if (renderer->isWidget()) {
921 Widget* widget = static_cast<RenderWidget*>(renderer)->widget();
922 if (widget && (widget->isPluginView() || widget->isPluginViewBase())) {
923 // check if this plugin really wants key events (TODO)
930 #if USE(ACCELERATED_COMPOSITING)
931 static void AddLayer(CachedFrame* frame, size_t index, const IntPoint& location, int id)
933 DBG_NAV_LOGD("frame=%p index=%d loc=(%d,%d) id=%d", frame, index,
934 location.x(), location.y(), id);
935 CachedLayer cachedLayer;
936 cachedLayer.setCachedNodeIndex(index);
937 cachedLayer.setOffset(location);
938 cachedLayer.setUniqueId(id);
939 frame->add(cachedLayer);
943 static int FindColorIndex(WTF::Vector<CachedColor>& colorTracker,
944 const CachedColor& cachedColor)
946 CachedColor* work = colorTracker.begin() - 1;
947 CachedColor* end = colorTracker.end();
948 while (++work < end) {
949 if (*work == cachedColor)
950 return work - colorTracker.begin();
952 int result = colorTracker.size();
953 colorTracker.grow(result + 1);
954 CachedColor& newColor = colorTracker.last();
955 newColor = cachedColor;
959 static void InitColor(CachedColor* color)
961 color->setFillColor(RenderStyle::initialRingFillColor());
962 color->setInnerWidth(RenderStyle::initialRingInnerWidth());
963 color->setOuterWidth(RenderStyle::initialRingOuterWidth());
964 color->setOutset(RenderStyle::initialRingOutset());
965 color->setPressedInnerColor(RenderStyle::initialRingPressedInnerColor());
966 color->setPressedOuterColor(RenderStyle::initialRingPressedOuterColor());
967 color->setRadius(RenderStyle::initialRingRadius());
968 color->setSelectedInnerColor(RenderStyle::initialRingSelectedInnerColor());
969 color->setSelectedOuterColor(RenderStyle::initialRingSelectedOuterColor());
972 // when new focus is found, push it's parent on a stack
973 // as long as more focii are found with the same (grand) parent, note it
974 // (which only requires retrieving the last parent on the stack)
975 // when the parent's last child is found, pop the stack
976 // different from Tracker in that Tracker only pushes focii with children
978 // making this work with focus - child focus - grandchild focus is tricky
979 // if I keep the generation number, I may be able to more quickly determine that
980 // a node is a grandchild of the focus's parent
981 // this additionally requires being able to find the grandchild's parent
983 // keep nodes that are focusable
984 void CacheBuilder::BuildFrame(Frame* root, Frame* frame,
985 CachedRoot* cachedRoot, CachedFrame* cachedFrame)
987 WTF::Vector<FocusTracker> tracker(1); // sentinel
989 FocusTracker* baseTracker = tracker.data();
990 bzero(baseTracker, sizeof(FocusTracker));
991 baseTracker->mCachedNodeIndex = -1;
993 WTF::Vector<LayerTracker> layerTracker(1); // sentinel
994 bzero(layerTracker.data(), sizeof(LayerTracker));
995 WTF::Vector<ClipColumnTracker> clipTracker(1); // sentinel
996 bzero(clipTracker.data(), sizeof(ClipColumnTracker));
997 WTF::Vector<TabIndexTracker> tabIndexTracker(1); // sentinel
998 bzero(tabIndexTracker.data(), sizeof(TabIndexTracker));
999 WTF::Vector<CachedColor> colorTracker(1);
1000 InitColor(colorTracker.data());
1002 char* frameNamePtr = cachedFrame->mDebug.mFrameName;
1003 Builder(frame)->mDebug.frameName(frameNamePtr, frameNamePtr +
1004 sizeof(cachedFrame->mDebug.mFrameName) - 1);
1005 *frameNamePtr = '\0';
1009 Document* doc = frame->document();
1011 CachedNode cachedParentNode;
1012 cachedParentNode.init(parent);
1014 cachedParentNode.mDebug.mNodeIndex = nodeIndex;
1016 cachedFrame->add(colorTracker[0]);
1017 cachedFrame->add(cachedParentNode);
1018 Node* node = parent;
1020 int colorIndex = 0; // assume no special css ring colors
1021 const void* lastStyleDataPtr = 0;
1022 int textInputIndex = 0;
1023 Node* focused = doc->focusedNode();
1025 cachedRoot->setFocusBounds(focused->getRect());
1026 int globalOffsetX, globalOffsetY;
1027 GetGlobalOffset(frame, &globalOffsetX, &globalOffsetY);
1028 #if USE(ACCELERATED_COMPOSITING)
1029 // The frame itself might be composited so we need to track the layer. Do
1030 // not track the base frame's layer as the main content is draw as part of
1031 // BaseLayerAndroid's picture.
1032 if (frame != root && frame->contentRenderer()
1033 && frame->contentRenderer()->usesCompositing() && node->lastChild())
1034 TrackLayer(layerTracker, frame->contentRenderer(), node->lastChild(),
1035 globalOffsetX, globalOffsetY);
1037 while (walk.mMore || (node = node->traverseNextNode()) != NULL) {
1041 FocusTracker* last = &tracker.last();
1042 int lastChildIndex = cachedFrame->size() - 1;
1043 while (node == last->mLastChild) {
1044 if (CleanUpContainedNodes(cachedRoot, cachedFrame, last, lastChildIndex))
1046 tracker.removeLast();
1047 lastChildIndex = last->mCachedNodeIndex;
1048 last = &tracker.last();
1051 const ClipColumnTracker* lastClip = &clipTracker.last();
1052 if (node != lastClip->mLastChild)
1054 clipTracker.removeLast();
1057 const LayerTracker* lastLayer = &layerTracker.last();
1058 if (node != lastLayer->mLastChild)
1060 layerTracker.removeLast();
1063 const TabIndexTracker* lastTabIndex = &tabIndexTracker.last();
1064 if (node != lastTabIndex->mLastChild)
1066 tabIndexTracker.removeLast();
1068 Frame* child = HasFrame(node);
1069 CachedNode cachedNode;
1070 if (child != NULL) {
1071 if (child->document() == NULL)
1073 RenderObject* nodeRenderer = node->renderer();
1074 if (nodeRenderer != NULL && nodeRenderer->style()->visibility() == HIDDEN)
1076 CachedFrame cachedChild;
1077 cachedChild.init(cachedRoot, cacheIndex, child);
1078 int childFrameIndex = cachedFrame->childCount();
1079 cachedFrame->addFrame(cachedChild);
1080 cachedNode.init(node);
1081 cachedNode.setIndex(cacheIndex++);
1082 cachedNode.setDataIndex(childFrameIndex);
1083 cachedNode.setType(FRAME_CACHEDNODETYPE);
1085 cachedNode.mDebug.mNodeIndex = nodeIndex;
1086 cachedNode.mDebug.mParentGroupIndex = Debug::ParentIndex(
1087 node, nodeIndex, NULL);
1089 cachedFrame->add(cachedNode);
1090 CachedFrame* childPtr = cachedFrame->lastChild();
1091 BuildFrame(root, child, cachedRoot, childPtr);
1094 int tabIndex = node->tabIndex();
1095 Node* lastChild = node->lastChild();
1097 tabIndex = tabIndexTracker.last().mTabIndex;
1098 else if (tabIndex > 0 && lastChild) {
1099 DBG_NAV_LOGD("tabIndex=%d node=%p", tabIndex, node);
1100 tabIndexTracker.grow(tabIndexTracker.size() + 1);
1101 TabIndexTracker& indexTracker = tabIndexTracker.last();
1102 indexTracker.mTabIndex = tabIndex;
1103 indexTracker.mLastChild = OneAfter(lastChild);
1105 RenderObject* nodeRenderer = node->renderer();
1106 bool isTransparent = false;
1107 bool hasCursorRing = true;
1108 if (nodeRenderer != NULL) {
1109 RenderStyle* style = nodeRenderer->style();
1110 if (style->visibility() == HIDDEN)
1112 isTransparent = nodeRenderer->hasBackground() == false;
1113 #ifdef ANDROID_CSS_TAP_HIGHLIGHT_COLOR
1114 hasCursorRing = style->tapHighlightColor().alpha() > 0;
1116 #if USE(ACCELERATED_COMPOSITING)
1117 // If this renderer has its own layer and the layer is composited,
1118 // start tracking it.
1119 if (lastChild && nodeRenderer->hasLayer() && toRenderBoxModelObject(nodeRenderer)->layer()->backing())
1120 TrackLayer(layerTracker, nodeRenderer, lastChild, globalOffsetX, globalOffsetY);
1123 bool more = walk.mMore;
1125 // GetGlobalBounds(node, &bounds, false);
1126 bool computeCursorRings = false;
1127 bool hasClip = false;
1128 bool hasMouseOver = false;
1129 bool isUnclipped = false;
1130 bool isFocus = node == focused;
1131 bool takesFocus = false;
1134 TextDirection direction = LTR;
1136 CachedNodeType type = NORMAL_CACHEDNODETYPE;
1137 CachedColor cachedColor;
1138 CachedInput cachedInput;
1141 IntRect originalAbsBounds;
1142 ColumnInfo* columnInfo = NULL;
1143 if (node->hasTagName(HTMLNames::areaTag)) {
1144 type = AREA_CACHEDNODETYPE;
1145 HTMLAreaElement* area = static_cast<HTMLAreaElement*>(node);
1146 bounds = getAreaRect(area);
1147 originalAbsBounds = bounds;
1148 bounds.move(globalOffsetX, globalOffsetY);
1150 isUnclipped = true; // FIXME: areamaps require more effort to detect
1151 // assume areamaps are always visible for now
1155 if (nodeRenderer == NULL)
1158 // some common setup
1159 absBounds = nodeRenderer->absoluteBoundingBoxRect();
1160 originalAbsBounds = absBounds;
1161 absBounds.move(globalOffsetX, globalOffsetY);
1162 hasClip = nodeRenderer->hasOverflowClip();
1164 if (node->hasTagName(HTMLNames::canvasTag))
1165 mPictureSetDisabled = true;
1166 if (checkForPluginViewThatWantsFocus(nodeRenderer)) {
1170 type = PLUGIN_CACHEDNODETYPE;
1173 // Only use the root contentEditable element
1174 if (node->isContentEditable() && !node->parentOrHostNode()->isContentEditable()) {
1177 type = CONTENT_EDITABLE_CACHEDNODETYPE;
1180 if (nodeRenderer->isRenderBlock()) {
1181 RenderBlock* renderBlock = (RenderBlock*) nodeRenderer;
1182 if (renderBlock->hasColumns()) {
1183 columnInfo = renderBlock->columnInfo();
1184 columnGap = renderBlock->columnGap();
1185 direction = renderBlock->style()->direction();
1188 if ((hasClip != false || columnInfo != NULL) && lastChild) {
1189 clipTracker.grow(clipTracker.size() + 1);
1190 ClipColumnTracker& clip = clipTracker.last();
1191 clip.mBounds = absBounds;
1192 clip.mLastChild = OneAfter(lastChild);
1194 clip.mColumnInfo = columnInfo;
1195 clip.mColumnGap = columnGap;
1196 clip.mHasClip = hasClip;
1197 clip.mDirection = direction;
1198 if (columnInfo != NULL) {
1199 const IntRect& oRect = ((RenderBox*)nodeRenderer)->visualOverflowRect();
1200 clip.mBounds.move(oRect.x(), oRect.y());
1203 if (node->isTextNode() && mAllowableTypes != NORMAL_CACHEDNODE_BITS) {
1204 if (last->mSomeParentTakesFocus) // don't look at text inside focusable node
1206 CachedNodeType checkType;
1207 if (isFocusableText(&walk, more, node, &checkType,
1208 &exported) == false)
1212 char buffer[DEBUG_BUFFER_SIZE];
1213 mDebug.init(buffer, sizeof(buffer));
1214 mDebug.print("text link found: ");
1215 mDebug.wideString(exported);
1216 DUMP_NAV_LOGD("%s\n", buffer);
1220 // !!! test ! is the following line correctly needed for frames to work?
1221 cachedNode.init(node);
1222 const ClipColumnTracker& clipTrack = clipTracker.last();
1223 const IntRect& clip = clipTrack.mHasClip ? clipTrack.mBounds :
1224 IntRect(0, 0, INT_MAX, INT_MAX);
1225 if (ConstructTextRects((WebCore::Text*) node, walk.mStart,
1226 (WebCore::Text*) walk.mFinalNode, walk.mEnd, globalOffsetX,
1227 globalOffsetY, &bounds, clip, &cachedNode.mCursorRing) == false)
1230 cachedNode.setBounds(bounds);
1231 if (bounds.width() < MINIMUM_FOCUSABLE_WIDTH)
1233 if (bounds.height() < MINIMUM_FOCUSABLE_HEIGHT)
1235 computeCursorRings = true;
1236 isUnclipped = true; // FIXME: to hide or partially occlude synthesized links, each
1237 // focus ring will also need the offset and length of characters
1238 // used to produce it
1241 if (node->hasTagName(WebCore::HTMLNames::inputTag)) {
1242 HTMLInputElement* input = static_cast<HTMLInputElement*>(node);
1243 if (input->isTextField()) {
1244 if (input->readOnly())
1246 type = TEXT_INPUT_CACHEDNODETYPE;
1248 cachedInput.setAutoComplete(input->autoComplete());
1249 cachedInput.setFormPointer(input->form());
1250 cachedInput.setIsTextField(true);
1251 exported = input->value().threadsafeCopy();
1252 cachedInput.setMaxLength(input->maxLength());
1253 cachedInput.setTypeFromElement(input);
1254 // If this does not need to be threadsafe, we can use crossThreadString().
1255 // See http://trac.webkit.org/changeset/49160.
1256 cachedInput.setName(input->name().string().threadsafeCopy());
1257 // can't detect if this is drawn on top (example: deviant.com login parts)
1258 isUnclipped = isTransparent;
1259 } else if (input->isInputTypeHidden())
1261 else if (input->isRadioButton() || input->isCheckbox())
1262 isTransparent = false;
1263 } else if (node->hasTagName(HTMLNames::textareaTag)) {
1264 HTMLTextAreaElement* area = static_cast<HTMLTextAreaElement*>(node);
1265 if (area->readOnly())
1268 type = TEXT_INPUT_CACHEDNODETYPE;
1269 cachedInput.setFormPointer(area->form());
1270 cachedInput.setIsTextArea(true);
1271 exported = area->value().threadsafeCopy();
1272 } else if (node->hasTagName(HTMLNames::aTag)) {
1273 const HTMLAnchorElement* anchorNode =
1274 (const HTMLAnchorElement*) node;
1275 if (!anchorNode->isFocusable() && !HasTriggerEvent(node))
1277 if (node->disabled())
1279 hasMouseOver = NodeHasEventListeners(node, &eventNames().mouseoverEvent, 1);
1280 type = ANCHOR_CACHEDNODETYPE;
1281 KURL href = anchorNode->href();
1282 if (!href.isEmpty() && !WebCore::protocolIsJavaScript(href.string()))
1283 // Set the exported string for all non-javascript anchors.
1284 exported = href.string().threadsafeCopy();
1285 } else if (node->hasTagName(HTMLNames::selectTag)) {
1286 type = SELECT_CACHEDNODETYPE;
1288 if (type == TEXT_INPUT_CACHEDNODETYPE) {
1289 RenderTextControl* renderText =
1290 static_cast<RenderTextControl*>(nodeRenderer);
1292 cachedRoot->setSelection(renderText->selectionStart(), renderText->selectionEnd());
1293 // FIXME: Are we sure there will always be a style and font, and it's correct?
1294 RenderStyle* style = nodeRenderer->style();
1296 isUnclipped |= !style->hasAppearance();
1297 int lineHeight = -1;
1298 Length lineHeightLength = style->lineHeight();
1299 // If the lineHeight is negative, WebTextView will calculate it
1300 // based on the text size, using the Paint.
1301 // See RenderStyle.computedLineHeight.
1302 if (lineHeightLength.isPositive())
1303 lineHeight = style->computedLineHeight();
1304 cachedInput.setLineHeight(lineHeight);
1305 cachedInput.setTextSize(style->font().size());
1306 cachedInput.setIsRtlText(style->direction() == RTL
1307 || style->textAlign() == WebCore::RIGHT
1308 || style->textAlign() == WebCore::WEBKIT_RIGHT);
1310 cachedInput.setPaddingLeft(renderText->paddingLeft() + renderText->borderLeft());
1311 cachedInput.setPaddingTop(renderText->paddingTop() + renderText->borderTop());
1312 cachedInput.setPaddingRight(renderText->paddingRight() + renderText->borderRight());
1313 cachedInput.setPaddingBottom(renderText->paddingBottom() + renderText->borderBottom());
1317 if (type != ANCHOR_CACHEDNODETYPE) {
1318 bool isFocusable = node->isKeyboardFocusable(NULL) ||
1319 node->isMouseFocusable() || node->isFocusable();
1320 if (isFocusable == false) {
1321 if (node->disabled())
1323 bool overOrOut = HasOverOrOut(node);
1324 bool hasTrigger = HasTriggerEvent(node);
1325 if (overOrOut == false && hasTrigger == false)
1327 takesFocus = hasTrigger;
1330 computeCursorRings = true;
1332 cachedNode.init(node);
1333 if (computeCursorRings == false) {
1334 cachedNode.setBounds(bounds);
1335 cachedNode.mCursorRing.append(bounds);
1336 } else if (ConstructPartRects(node, bounds, &cachedNode.mBounds,
1337 globalOffsetX, globalOffsetY, &cachedNode.mCursorRing,
1338 &imageCount) == false)
1341 if (nodeRenderer) { // area tags' node->renderer() == 0
1342 RenderStyle* style = nodeRenderer->style();
1343 const void* styleDataPtr = style->ringData();
1344 // to save time, see if we're pointing to the same style data as before
1345 if (lastStyleDataPtr != styleDataPtr) {
1346 lastStyleDataPtr = styleDataPtr;
1347 cachedColor.setFillColor(style->ringFillColor());
1348 cachedColor.setInnerWidth(style->ringInnerWidth());
1349 cachedColor.setOuterWidth(style->ringOuterWidth());
1350 cachedColor.setOutset(style->ringOutset());
1351 cachedColor.setPressedInnerColor(style->ringPressedInnerColor());
1352 cachedColor.setPressedOuterColor(style->ringPressedOuterColor());
1353 cachedColor.setRadius(style->ringRadius());
1354 cachedColor.setSelectedInnerColor(style->ringSelectedInnerColor());
1355 cachedColor.setSelectedOuterColor(style->ringSelectedOuterColor());
1356 int oldSize = colorTracker.size();
1357 colorIndex = FindColorIndex(colorTracker, cachedColor);
1358 if (colorIndex == oldSize)
1359 cachedFrame->add(cachedColor);
1363 IntRect clip = hasClip ? bounds : absBounds;
1364 size_t clipIndex = clipTracker.size();
1365 if (clipTracker.last().mNode == node)
1367 while (--clipIndex > 0) {
1368 const ClipColumnTracker& clipTrack = clipTracker.at(clipIndex);
1369 if (clipTrack.mHasClip == false) {
1370 adjustForColumns(clipTrack, &cachedNode, &absBounds, static_cast<RenderBlock*>(nodeRenderer));
1373 const IntRect& parentClip = clipTrack.mBounds;
1374 if (hasClip == false && type == ANCHOR_CACHEDNODETYPE)
1377 clip.intersect(parentClip);
1380 bool isInLayer = false;
1381 #if USE(ACCELERATED_COMPOSITING)
1382 // If this renderer has a composited parent layer (including itself),
1383 // add the node to the cached layer.
1384 // FIXME: does not work for area rects
1385 RenderLayer* enclosingLayer = nodeRenderer->enclosingLayer();
1386 if (enclosingLayer && enclosingLayer->enclosingCompositingLayer()) {
1387 LayerAndroid* layer = layerTracker.last().mLayer;
1389 const IntRect& layerClip = layerTracker.last().mBounds;
1390 if (!layerClip.isEmpty() && !cachedNode.clip(layerClip)) {
1391 DBG_NAV_LOGD("skipped on layer clip %d", cacheIndex);
1392 continue; // skip this node if outside of the clip
1395 isUnclipped = true; // assume that layers do not have occluded nodes
1397 AddLayer(cachedFrame, cachedFrame->size(), layerClip.location(),
1404 continue; // skip this node if clip prevents all drawing
1405 else if (cachedNode.clip(clip) == false)
1406 continue; // skip this node if outside of the clip
1408 cachedNode.setNavableRects();
1409 cachedNode.setColorIndex(colorIndex);
1410 cachedNode.setExport(exported);
1411 cachedNode.setHasCursorRing(hasCursorRing);
1412 cachedNode.setHasMouseOver(hasMouseOver);
1413 cachedNode.setHitBounds(absBounds);
1414 cachedNode.setIndex(cacheIndex);
1415 cachedNode.setIsFocus(isFocus);
1416 cachedNode.setIsInLayer(isInLayer);
1417 cachedNode.setIsTransparent(isTransparent);
1418 cachedNode.setIsUnclipped(isUnclipped);
1419 cachedNode.setOriginalAbsoluteBounds(originalAbsBounds);
1420 cachedNode.setParentIndex(last->mCachedNodeIndex);
1421 cachedNode.setParentGroup(ParentWithChildren(node));
1422 cachedNode.setSingleImage(imageCount == 1);
1423 cachedNode.setTabIndex(tabIndex);
1424 cachedNode.setType(type);
1425 if (type == TEXT_INPUT_CACHEDNODETYPE) {
1426 cachedFrame->add(cachedInput);
1427 cachedNode.setDataIndex(textInputIndex);
1430 cachedNode.setDataIndex(-1);
1432 cachedNode.mDebug.mNodeIndex = nodeIndex;
1433 cachedNode.mDebug.mParentGroupIndex = Debug::ParentIndex(
1434 node, nodeIndex, (Node*) cachedNode.parentGroup());
1436 cachedFrame->add(cachedNode);
1438 int lastIndex = cachedFrame->size() - 1;
1439 if (node == focused) {
1440 CachedNode* cachedNodePtr = cachedFrame->getIndex(lastIndex);
1441 cachedRoot->setCachedFocus(cachedFrame, cachedNodePtr);
1443 if (lastChild != NULL) {
1444 tracker.grow(tracker.size() + 1);
1445 FocusTracker& working = tracker.last();
1446 working.mCachedNodeIndex = lastIndex;
1447 working.mLastChild = OneAfter(lastChild);
1448 last = &tracker.at(tracker.size() - 2);
1449 working.mSomeParentTakesFocus = last->mSomeParentTakesFocus | takesFocus;
1454 while (tracker.size() > 1) {
1455 FocusTracker* last = &tracker.last();
1456 int lastChildIndex = cachedFrame->size() - 1;
1457 if (CleanUpContainedNodes(cachedRoot, cachedFrame, last, lastChildIndex))
1459 tracker.removeLast();
1463 bool CacheBuilder::CleanUpContainedNodes(CachedRoot* cachedRoot,
1464 CachedFrame* cachedFrame, const FocusTracker* last, int lastChildIndex)
1466 // if outer is body, disable outer
1467 // or if there's more than one inner, disable outer
1468 // or if inner is keyboard focusable, disable outer
1469 // else disable inner by removing it
1470 int childCount = lastChildIndex - last->mCachedNodeIndex;
1471 if (childCount == 0)
1473 CachedNode* lastCached = cachedFrame->getIndex(last->mCachedNodeIndex);
1474 Node* lastNode = (Node*) lastCached->nodePointer();
1475 if ((childCount > 1 && lastNode->hasTagName(HTMLNames::selectTag) == false) ||
1476 lastNode->hasTagName(HTMLNames::bodyTag) ||
1477 lastNode->hasTagName(HTMLNames::formTag)) {
1478 lastCached->setBounds(IntRect(0, 0, 0, 0));
1479 lastCached->mCursorRing.clear();
1480 lastCached->setNavableRects();
1483 CachedNode* onlyChildCached = cachedFrame->lastNode();
1484 Node* onlyChild = (Node*) onlyChildCached->nodePointer();
1485 bool outerIsMouseMoveOnly =
1486 lastNode->isKeyboardFocusable(NULL) == false &&
1487 lastNode->isMouseFocusable() == false &&
1488 lastNode->isFocusable() == false &&
1489 HasOverOrOut(lastNode) == true &&
1490 HasTriggerEvent(lastNode) == false;
1491 if (onlyChildCached->parent() == lastCached)
1492 onlyChildCached->setParentIndex(lastCached->parentIndex());
1493 bool hasFocus = lastCached->isFocus() || onlyChildCached->isFocus();
1494 if (outerIsMouseMoveOnly || onlyChild->isKeyboardFocusable(NULL)
1495 || onlyChildCached->isPlugin()) {
1496 int index = lastCached->index();
1497 *lastCached = *onlyChildCached;
1498 lastCached->setIndex(index);
1499 CachedFrame* frame = cachedFrame->hasFrame(lastCached);
1501 frame->setIndexInParent(index);
1503 cachedFrame->removeLast();
1505 cachedRoot->setCachedFocus(cachedFrame, cachedFrame->lastNode());
1509 Node* CacheBuilder::currentFocus() const
1511 Frame* frame = FrameAnd(this);
1512 Document* doc = frame->document();
1514 Node* focus = doc->focusedNode();
1518 Frame* child = frame->tree()->firstChild();
1520 CacheBuilder* cacheBuilder = Builder(child);
1521 Node* focus = cacheBuilder->currentFocus();
1524 child = child->tree()->nextSibling();
1529 static bool strCharCmp(const char* matches, const UChar* test, int wordLength,
1532 for (int index = 0; index < wordCount; index++) {
1533 for (int inner = 0; inner < wordLength; inner++) {
1534 if (matches[inner] != test[inner]) {
1535 matches += wordLength;
1546 static const int stateTwoLetter[] = {
1547 0x02060c00, // A followed by: [KLRSZ]
1549 0x00084001, // C followed by: [AOT]
1550 0x00000014, // D followed by: [CE]
1552 0x00001800, // F followed by: [LM]
1553 0x00100001, // G followed by: [AU]
1554 0x00000100, // H followed by: [I]
1555 0x00002809, // I followed by: [ADLN]
1557 0x01040000, // K followed by: [SY]
1558 0x00000001, // L followed by: [A]
1559 0x000ce199, // M followed by: [ADEHINOPST]
1560 0x0120129c, // N followed by: [CDEHJMVY]
1561 0x00020480, // O followed by: [HKR]
1562 0x00420001, // P followed by: [ARW]
1564 0x00000100, // R followed by: [I]
1565 0x0000000c, // S followed by: [CD]
1566 0x00802000, // T followed by: [NX]
1567 0x00080000, // U followed by: [T]
1568 0x00080101, // V followed by: [AIT]
1569 0x01200101 // W followed by: [AIVY]
1572 static const char firstIndex[] = {
1573 0, 5, 5, 8, 10, 10, 12, 14,
1574 15, 19, 19, 21, 22, 32, 40, 43,
1575 46, 46, 47, 49, 51, 52, 55, 59
1578 // from http://infolab.stanford.edu/~manku/bitcount/bitcount.html
1579 #define TWO(c) (0x1u << (c))
1580 #define MASK(c) (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
1581 #define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
1583 int bitcount (unsigned int n)
1596 static bool isUnicodeSpace(UChar ch)
1598 return ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r' || ch == 0xa0;
1601 static bool validZip(int stateIndex, const UChar* zipPtr)
1603 static const struct {
1609 { 99, 99, -1, -1 }, // AK Alaska
1610 { 35, 36, -1, -1 }, // AL Alabama
1611 { 71, 72, -1, -1 }, // AR Arkansas
1612 { 96, 96, -1, -1 }, // AS American Samoa
1613 { 85, 86, -1, -1 }, // AZ Arizona
1614 { 90, 96, -1, -1 }, // CA California
1615 { 80, 81, -1, -1 }, // CO Colorado
1616 { 6, 6, -1, -1 }, // CT Connecticut
1617 { 20, 20, -1, -1 }, // DC District of Columbia
1618 { 19, 19, -1, -1 }, // DE Delaware
1619 { 32, 34, -1, -1 }, // FL Florida
1620 { 96, 96, -1, -1 }, // FM Federated States of Micronesia
1621 { 30, 31, -1, -1 }, // GA Georgia
1622 { 96, 96, -1, -1 }, // GU Guam
1623 { 96, 96, -1, -1 }, // HI Hawaii
1624 { 50, 52, -1, -1 }, // IA Iowa
1625 { 83, 83, -1, -1 }, // ID Idaho
1626 { 60, 62, -1, -1 }, // IL Illinois
1627 { 46, 47, -1, -1 }, // IN Indiana
1628 { 66, 67, 73, -1 }, // KS Kansas
1629 { 40, 42, -1, -1 }, // KY Kentucky
1630 { 70, 71, -1, -1 }, // LA Louisiana
1631 { 1, 2, -1, -1 }, // MA Massachusetts
1632 { 20, 21, -1, -1 }, // MD Maryland
1633 { 3, 4, -1, -1 }, // ME Maine
1634 { 96, 96, -1, -1 }, // MH Marshall Islands
1635 { 48, 49, -1, -1 }, // MI Michigan
1636 { 55, 56, -1, -1 }, // MN Minnesota
1637 { 63, 65, -1, -1 }, // MO Missouri
1638 { 96, 96, -1, -1 }, // MP Northern Mariana Islands
1639 { 38, 39, -1, -1 }, // MS Mississippi
1640 { 55, 56, -1, -1 }, // MT Montana
1641 { 27, 28, -1, -1 }, // NC North Carolina
1642 { 58, 58, -1, -1 }, // ND North Dakota
1643 { 68, 69, -1, -1 }, // NE Nebraska
1644 { 3, 4, -1, -1 }, // NH New Hampshire
1645 { 7, 8, -1, -1 }, // NJ New Jersey
1646 { 87, 88, 86, -1 }, // NM New Mexico
1647 { 88, 89, 96, -1 }, // NV Nevada
1648 { 10, 14, 0, 6 }, // NY New York
1649 { 43, 45, -1, -1 }, // OH Ohio
1650 { 73, 74, -1, -1 }, // OK Oklahoma
1651 { 97, 97, -1, -1 }, // OR Oregon
1652 { 15, 19, -1, -1 }, // PA Pennsylvania
1653 { 6, 6, 0, 9 }, // PR Puerto Rico
1654 { 96, 96, -1, -1 }, // PW Palau
1655 { 2, 2, -1, -1 }, // RI Rhode Island
1656 { 29, 29, -1, -1 }, // SC South Carolina
1657 { 57, 57, -1, -1 }, // SD South Dakota
1658 { 37, 38, -1, -1 }, // TN Tennessee
1659 { 75, 79, 87, 88 }, // TX Texas
1660 { 84, 84, -1, -1 }, // UT Utah
1661 { 22, 24, 20, -1 }, // VA Virginia
1662 { 6, 9, -1, -1 }, // VI Virgin Islands
1663 { 5, 5, -1, -1 }, // VT Vermont
1664 { 98, 99, -1, -1 }, // WA Washington
1665 { 53, 54, -1, -1 }, // WI Wisconsin
1666 { 24, 26, -1, -1 }, // WV West Virginia
1667 { 82, 83, -1, -1 } // WY Wyoming
1670 int zip = zipPtr[0] - '0';
1672 zip += zipPtr[1] - '0';
1673 int low = zipRange[stateIndex].mLow;
1674 int high = zipRange[stateIndex].mHigh;
1675 if (zip >= low && zip <= high)
1677 if (zip == zipRange[stateIndex].mException1)
1679 if (zip == zipRange[stateIndex].mException2)
1684 #define MAX_PLACE_NAME_LENGTH 25 // the longest allowable one word place name
1686 CacheBuilder::FoundState CacheBuilder::FindAddress(const UChar* chars,
1687 unsigned length, int* start, int* end, bool caseInsensitive)
1689 FindState addressState;
1690 FindReset(&addressState);
1691 addressState.mWords[0] = addressState.mStarts[0] = chars;
1692 addressState.mCaseInsensitive = caseInsensitive;
1693 FoundState state = FindPartialAddress(chars, chars, length, &addressState);
1694 if (state == FOUND_PARTIAL && addressState.mProgress == ZIP_CODE &&
1695 addressState.mNumberCount == 0) {
1696 addressState.mProgress = FIND_STREET;
1697 state = FindPartialAddress(NULL, NULL, 0, &addressState);
1699 *start = addressState.mStartResult;
1700 *end = addressState.mEndResult;
1704 CacheBuilder::FoundState CacheBuilder::FindPartialAddress(const UChar* baseChars,
1705 const UChar* chars, unsigned length, FindState* s)
1707 // lower case letters are optional; trailing asterisk is optional 's'
1708 static char const* const longStreetNames[] = {
1709 "\x04" "LleY" "\x04" "NneX" "\x05" "RCade" "\x05" "VEnue" "\x06" "LAMEDA", // A
1710 "\x04" "aYoU" "\x04" "eaCH" "\x03" "eND" "\x05" "LuFf*" "\x05" "oTtoM"
1711 "\x08" "ouLeVarD" "\x05" "Ranch" "\x05" "RidGe" "\x05" "RooK*"
1712 "\x04" "urG*" "\x05" "YPass" "\x07" "roadWAY", // B
1714 "\x03" "amP" "\x05" "anYoN" "\x03" "aPE" "\x07" "auSeWaY" "\x06" "enTeR*"
1715 "\x06" "IRcle*" "\x05" "LiFf*" "\x03" "LuB" "\x05" "oMmoN" "\x06" "ORner*"
1716 "\x05" "ouRSE" "\x05" "ourT*" "\x04" "oVe*" "\x04" "ReeK" "\x07" "REScent"
1717 "\x04" "ReST" "\x07" "ROSSING" "\x08" "ROSSROAD" "\x04" "URVe"
1718 "\x05" "AMINO" "\x06" "IRCULO" "\x07" "REScent", // C
1719 "\x03" "aLe" "\x02" "aM" "\x05" "iVide" "\x05" "Rive*", // D
1720 "\x06" "STate*" "\x09" "XPresswaY" "\x09" "XTension*", // E
1721 "\x04" "ALL*" "\x04" "eRrY" "\x05" "ieLD*" "\x04" "LaT*" "\x04" "oRD*"
1722 "\x05" "oReST" "\x05" "oRGe*" "\x04" "oRK*" "\x03" "orT" "\x06" "reeWaY", // F
1723 "\x06" "arDeN*" "\x06" "aTeWaY" "\x04" "LeN*" "\x05" "ReeN*" "\x05" "RoVe*", // G
1724 "\x06" "arBoR*" "\x04" "aVeN" "\x06" "eighTS" "\x06" "ighWaY" "\x04" "iLl*"
1725 "\x05" "OLloW", // H
1726 "\x04" "NLeT" "\x06" "Sland*" "\x03" "SLE", // I
1727 "\x08" "unCTion*", // J
1728 "\x03" "eY*" "\x05" "NoLl*", // K
1729 "\x04" "aKe*" "\x03" "AND" "\x06" "aNDinG" "\x03" "aNe" "\x05" "iGhT*"
1730 "\x03" "oaF" "\x04" "oCK*" "\x04" "oDGe" "\x03" "OOP", // L
1731 "\x03" "ALL" "\x05" "aNoR*" "\x06" "eaDoW*" "\x03" "EWS" "\x04" "iLl*"
1732 "\x06" "iSsioN" "\x07" "oTorWaY" "\x04" "ounT" "\x08" "ounTaiN*", // M
1734 "\x06" "RCHard" "\x03" "VAL" "\x07" "verPASs", // O
1735 "\x04" "ARK*" "\x07" "arKWaY*" "\x03" "ASS" "\x06" "aSsaGE" "\x03" "ATH"
1736 "\x03" "IKE" "\x04" "iNE*" "\x04" "Lace" "\x05" "LaiN*" "\x04" "LaZa"
1737 "\x05" "oinT*" "\x04" "oRT*" "\x06" "Rairie" "\x06" "RIVADA", // P
1739 "\x05" "ADiaL" "\x03" "AMP" "\x04" "aNCH" "\x05" "aPiD*"
1741 "\x05" "iDGe*" "\x04" "IVer" "\x04" "oaD*" "\x04" "ouTE" "\x02" "OW"
1742 "\x02" "UE" "\x02" "UN", // R
1743 "\x05" "HoaL*" "\x05" "HoRe*" "\x05" "KyWaY" "\x06" "PrinG*" "\x04" "PUR*"
1744 "\x06" "Quare*" "\x06" "TAtion" "\x08" "TRAvenue" "\x05" "TReaM"
1745 "\x06" "Treet*" "\x05" "uMmiT" "\x07" "PeeDWaY", // S
1746 "\x06" "ERrace" "\x09" "hRoughWaY" "\x04" "RaCE" "\x04" "RAcK" "\x09" "RaFficwaY"
1747 "\x04" "RaiL" "\x05" "UNneL" "\x07" "urnPiKE", // T
1748 "\x08" "nderPASs" "\x05" "Nion*", // U
1749 "\x06" "aLleY*" "\x06" "IAduct" "\x04" "ieW*" "\x07" "iLlaGe*" "\x04" "iLle"
1751 "\x04" "ALK*" "\x03" "ALL" "\x03" "AY*" "\x04" "eLl*", // W
1752 "\x03" "ING" "\x02" "RD", // X
1755 static char const* const longStateNames[] = {
1756 "\x8e" "la" "\x85" "bama" "\x02" "\x84" "ska" "\x01" "\x8f" "merican Samoa" "\x04"
1757 "\x91" "r" "\x86" "izona" "\x05" "\x87" "kansas" "\x03",
1759 "\x8b" "alifornia" "\x06" "\x95" "o" "\x87" "lorado" "\x07" "\x8a" "nnecticut" "\x08",
1760 "\x89" "elaware" "\x0a" "\x95" "istrict of Columbia" "\x09",
1762 "\x9f" "ederated States of Micronesia" "\x0c" "\x88" "lorida" "\x0b",
1763 "\x85" "uam" "\x0e" "\x88" "eorgia" "\x0d",
1764 "\x87" "awaii" "\x0f",
1765 "\x86" "daho" "\x11" "\x89" "llinois" "\x12" "\x88" "ndiana" "\x13" "\x85"
1768 "\x87" "ansas" "\x14" "\x89" "entucky" "\x15",
1769 "\x8a" "ouisiana" "\x16",
1770 "\x86" "aine" "\x19" "\x99" "ar" "\x8e" "shall Islands" "\x1a" "\x86" "yland" "\x18"
1771 "\x8e" "assachusetts" "\x17" "\x93" "i" "\x87" "chigan" "\x1b"
1772 "\x88" "nnesota" "\x1c" "\x93" "iss" "\x88" "issippi" "\x1f" "\x85"
1773 "ouri" "\x1d" "\x88" "ontana" "\x20",
1774 "\x90" "e" "\x87" "braska" "\x23" "\x85" "vada" "\x27" "\xa5" "ew " "\x8a"
1775 "Hampshire" "\x24" "\x87" "Jersey" "\x25" "\x87" "Mexico" "\x26"
1776 "\x85" "York" "\x28" "\x98" "orth " "\x89" "Carolina" "\x21" "\x87"
1777 "Dakota" "\x22" "\x99" "orthern Mariana Islands" "\x1e",
1778 "\x85" "hio" "\x29" "\x89" "klahoma" "\x2a" "\x87" "regon" "\x2b",
1779 "\x86" "alau" "\x2e" "\x8d" "ennsylvania" "\x2c" "\x8c" "uerto Rico" "\x2d",
1781 "\x8d" "hode Island" "\x2f",
1782 "\x98" "outh " "\x89" "Carolina" "\x30" "\x87" "Dakota" "\x31",
1783 "\x90" "e" "\x88" "nnessee" "\x32" "\x84" "xas" "\x33",
1784 "\x85" "tah" "\x34",
1785 "\x88" "ermont" "\x37" "\x94" "irgin" "\x89" " Islands" "\x36" "\x83" "ia" "\x35",
1786 "\x8b" "ashington" "\x38" "\x8e" "est Virginia" "\x3a" "\x8a" "isconsin" "\x39"
1787 "\x88" "yoming" "\x3b"
1790 #if 0 // DEBUG_NAV_UI
1791 static char const* const progressNames[] = {
1795 "NUMBER_TRAILING_SPACE",
1804 // strategy: US only support at first
1805 // look for a 1 - 5 digit number for a street number (no support for 'One Microsoft Way')
1806 // ignore if preceded by '#', Suite, Ste, Rm
1807 // look for two or more words (up to 5? North Frank Lloyd Wright Blvd)
1808 // note: "The Circle at North Hills St." has six words, and a lower 'at' -- allow at, by, of, in, the, and, ... ?
1809 // if a word starts with a lowercase letter, no match
1810 // allow: , . - # / (for 1/2) ' "
1811 // don't look for street name type yet
1812 // look for one or two delimiters to represent possible 2nd addr line and city name
1813 // look for either full state name, or state two letters, and/or zip code (5 or 9 digits)
1814 // now look for street suffix, either in full or abbreviated form, with optional 's' if there's an asterisk
1816 s->mCurrentStart = chars;
1817 s->mEnd = chars + length;
1820 bool mustBeAllUpper = false;
1821 bool secondHalf = false;
1823 UChar ch = s->mCurrent;
1824 while (++chars <= s->mEnd) {
1826 ch = chars < s->mEnd ? *chars : ' ';
1827 switch (s->mProgress) {
1829 if (WTF::isASCIIDigit(ch) == false) {
1830 if (ch != 'O') // letter 'O', not zero
1832 if (s->mEnd - chars < 3)
1836 if ((prior != 'n' || ch != 'e') && (prior != 'N' || ch != 'E'))
1838 if (isUnicodeSpace(*++chars) == false)
1840 s->mProgress = ADDRESS_LINE;
1841 s->mStartResult = chars - 3 - s->mCurrentStart;
1844 if (isUnicodeSpace(prior) == false) {
1845 s->mProgress = SKIP_TO_SPACE;
1848 s->mNumberCount = 1;
1849 s->mProgress = HOUSE_NUMBER;
1850 s->mStartResult = chars - s->mCurrentStart;
1853 if (isUnicodeSpace(ch) == false)
1857 if (WTF::isASCIIDigit(ch)) {
1858 if (++s->mNumberCount >= 6)
1859 s->mProgress = SKIP_TO_SPACE;
1862 if (WTF::isASCIIUpper(ch)) { // allow one letter after house number, e.g. 12A SKOLFIELD PL, HARPSWELL, ME 04079
1863 if (WTF::isASCIIDigit(prior) == false)
1864 s->mProgress = SKIP_TO_SPACE;
1868 if (s->mNumberCount > 0) { // permit 21-23 ELM ST
1873 s->mNumberCount = 0;
1874 s->mProgress = NUMBER_TRAILING_SPACE;
1875 case NUMBER_TRAILING_SPACE:
1876 if (isUnicodeSpace(ch))
1878 if (0 && WTF::isASCIIDigit(ch)) {
1879 s->mNumberCount = 1;
1880 s->mProgress = HOUSE_NUMBER;
1881 s->mStartResult = chars - s->mCurrentStart;
1884 if (WTF::isASCIIDigit(ch) == false && WTF::isASCIIUpper(ch) == false)
1886 s->mProgress = ADDRESS_LINE;
1888 if (WTF::isASCIIAlpha(ch) || ch == '\'' || ch == '-' || ch == '&' || ch == '(' || ch == ')') {
1889 if (++s->mLetterCount > 1) {
1890 s->mNumberWords &= ~(1 << s->mWordCount);
1893 if (s->mNumberCount >= 5)
1895 // FIXME: the test below was added to give up on a non-address, but it
1896 // incorrectly discards addresses where the house number is in one node
1897 // and the street name is in the next; I don't recall what the failing case
1898 // is that suggested this fix.
1899 // if (s->mWordCount == 0 && s->mContinuationNode)
1900 // return FOUND_NONE;
1901 s->newWord(baseChars, chars);
1902 if (WTF::isASCIILower(ch) && s->mNumberCount == 0)
1903 s->mFirstLower = chars;
1904 s->mNumberCount = 0;
1905 if (WTF::isASCIILower(ch) || (WTF::isASCIIAlpha(ch) == false && ch != '-'))
1906 s->mNumberWords &= ~(1 << s->mWordCount);
1907 s->mUnparsed = true;
1909 } else if (s->mLetterCount >= MAX_PLACE_NAME_LENGTH) {
1911 } else if (s->mFirstLower != NULL) {
1912 if (s->mCaseInsensitive)
1914 size_t length = chars - s->mFirstLower;
1917 if (length == 3 && strCharCmp("and" "the", s->mFirstLower, 3, 2) == false)
1919 if (length == 2 && strCharCmp("at" "by" "el" "in" "of", s->mFirstLower, 2, 5) == false)
1923 if (ch == ',' || ch == '*') { // delimits lines
1924 // asterisk as delimiter: http://www.sa.sc.edu/wellness/members.html
1925 if (++s->mLineCount > 5)
1929 if (isUnicodeSpace(ch) || prior == '-') {
1931 if (s->mUnparsed == false)
1933 const UChar* candidate = s->mWords[s->mWordCount];
1934 UChar firstLetter = candidate[0];
1935 if (WTF::isASCIIUpper(firstLetter) == false && WTF::isASCIIDigit(firstLetter) == false)
1938 if ((s->mWordCount == 2 && s->mNumberWords == 3 && WTF::isASCIIDigit(s->mWords[1][1])) || // choose second of 8888 333 Main
1939 (s->mWordCount >= sizeof(s->mWords) / sizeof(s->mWords[0]) - 1)) { // subtract 1 since state names may have two parts
1940 // search for simple number already stored since first potential house # didn't pan out
1941 if (s->mNumberWords == 0)
1944 while ((s->mNumberWords & (1 << shift)) == 0)
1946 s->mNumberWords >>= ++shift;
1947 if (s->mBases[0] != s->mBases[shift]) // if we're past the original node, bail
1949 s->shiftWords(shift);
1950 s->mStartResult = s->mWords[0] - s->mStarts[0];
1951 s->mWordCount -= shift;
1952 // FIXME: need to adjust lineCount to account for discarded delimiters
1954 if (s->mWordCount < 4)
1957 if (firstLetter > 'W' - 'A')
1959 UChar secondLetter = candidate[1];
1961 s->mLetterCount--; // trim trailing dashes, to accept CA-94043
1962 if (s->mLetterCount == 2) {
1963 secondLetter -= 'A';
1964 if (secondLetter > 'Z' - 'A')
1966 if ((stateTwoLetter[firstLetter] & 1 << secondLetter) != 0) {
1967 // special case to ignore 'et al'
1968 if (strCharCmp("ET", s->mWords[s->mWordCount - 2], 2, 1) == false) {
1969 s->mStateWord = s->mWordCount - 1;
1970 s->mZipHint = firstIndex[firstLetter] +
1971 bitcount(stateTwoLetter[firstLetter] & ((1 << secondLetter) - 1));
1972 goto foundStateName;
1977 s->mStates = longStateNames[firstLetter];
1978 if (s->mStates == NULL)
1980 mustBeAllUpper = false;
1981 s->mProgress = STATE_NAME;
1982 unsigned char section = s->mStates[0];
1983 ASSERT(section > 0x80);
1984 s->mSectionLength = section & 0x7f;
1987 s->mStateWord = s->mWordCount - 1;
1990 if (WTF::isASCIIDigit(ch)) {
1991 if (s->mLetterCount == 0) {
1992 if (++s->mNumberCount > 1)
1994 if (s->mWordCount == 0 && s->mContinuationNode)
1996 s->newWord(baseChars, chars);
1997 s->mNumberWords |= 1 << s->mWordCount;
1998 s->mUnparsed = true;
2002 if (ch == '.') { // optionally can follow letters
2003 if (s->mLetterCount == 0)
2005 if (s->mNumberCount > 0)
2009 if (ch == '/') // between numbers (1/2) between words (12 Main / Ste 4d)
2011 if (ch == '#') // can precede numbers, allow it to appear randomly
2013 if (ch == '"') // sometimes parts of addresses are quoted (FIXME: cite an example here)
2017 if (WTF::isASCIIAlpha(ch)) {
2018 if (s->mLetterCount == 0) {
2019 s->newWord(baseChars, chars);
2025 if (WTF::isASCIIDigit(ch) == false) {
2026 if (s->mLetterCount > 0) {
2027 s->mProgress = STATE_NAME;
2034 s->mProgress = ADDRESS_LINE;
2038 // pick up length of first section
2043 bool subStr = false;
2045 unsigned char match = s->mStates[stateIndex];
2046 if (match >= 0x80) {
2047 if (stateIndex == s->mSectionLength)
2051 // goto foundStateName;
2053 skip = match & 0x7f;
2054 match = s->mStates[++stateIndex];
2056 UChar candChar = s->mWords[s->mWordCount - 1][candIndex];
2057 if (mustBeAllUpper && WTF::isASCIILower(candChar))
2059 if (match != candChar) {
2060 if (match != WTF::toASCIILower(candChar)) {
2062 if (subStr == false)
2064 if (stateIndex == s->mSectionLength) {
2066 s->mProgress = ADDRESS_LINE;
2074 continue; // try next substring
2076 mustBeAllUpper = true;
2078 int nextindex = stateIndex + 1;
2079 if (++candIndex >= s->mLetterCount && s->mStates[nextindex] == ' ') {
2080 s->mProgress = SECOND_HALF;
2081 s->mStates += nextindex;
2082 s->mSectionLength -= nextindex;
2085 if (nextindex + 1 == s->mSectionLength || skip == 2) {
2086 s->mZipHint = s->mStates[nextindex] - 1;
2087 goto foundStateName;
2092 s->mStates += s->mSectionLength;
2093 ASSERT(s->mStates[0] == 0 || (unsigned) s->mStates[0] > 0x80);
2094 s->mSectionLength = s->mStates[0] & 0x7f;
2097 } while (s->mSectionLength != 0);
2098 s->mProgress = ADDRESS_LINE;
2101 s->mEndResult = chars - s->mCurrentStart;
2102 s->mEndWord = s->mWordCount - 1;
2103 s->mProgress = ZIP_CODE;
2104 // a couple of delimiters is an indication that the state name is good
2105 // or, a non-space / non-alpha-digit is also good
2106 s->mZipDelimiter = s->mLineCount > 2
2107 || isUnicodeSpace(ch) == false
2108 || chars == s->mEnd;
2109 if (WTF::isASCIIDigit(ch))
2110 s->mZipStart = chars;
2113 if (WTF::isASCIIDigit(ch)) {
2114 int count = ++s->mNumberCount;
2116 if (WTF::isASCIIDigit(prior))
2119 s->mZipStart = chars;
2123 } else if (isUnicodeSpace(ch)) {
2124 if (s->mNumberCount == 0) {
2125 s->mZipDelimiter = true; // two spaces delimit state name
2128 } else if (ch == '-') {
2129 if (s->mNumberCount == 5 && validZip(s->mZipHint, s->mZipStart)) {
2130 s->mNumberCount = 0;
2131 s->mProgress = PLUS_4;
2134 if (s->mNumberCount == 0)
2135 s->mZipDelimiter = true;
2136 } else if (WTF::isASCIIAlpha(ch) == false)
2137 s->mZipDelimiter = true;
2139 if (s->mLetterCount == 0) {
2140 s->newWord(baseChars, chars);
2141 s->mUnparsed = true;
2145 if (s->mNumberCount == 5 || s->mNumberCount == 9) {
2146 if (validZip(s->mZipHint, s->mZipStart) == false)
2148 s->mEndResult = chars - s->mCurrentStart;
2149 s->mEndWord = s->mWordCount - 1;
2150 } else if (s->mZipDelimiter == false) {
2153 s->mProgress = ADDRESS_LINE;
2156 s->mProgress = FIND_STREET;
2159 if (WTF::isASCIIDigit(ch)) {
2160 if (++s->mNumberCount <= 4)
2163 if (isUnicodeSpace(ch)) {
2164 if (s->mNumberCount == 0)
2167 if (s->mNumberCount == 4) {
2168 if (WTF::isASCIIAlpha(ch) == false) {
2169 s->mEndResult = chars - s->mCurrentStart;
2170 s->mEndWord = s->mWordCount - 1;
2172 } else if (s->mNumberCount != 0)
2174 s->mProgress = FIND_STREET;
2178 for (int wordsIndex = s->mStateWord - 1; wordsIndex >= 0; --wordsIndex) {
2179 const UChar* test = s->mWords[wordsIndex];
2180 UChar letter = test[0];
2182 if (letter > 'X' - 'A')
2184 const char* names = longStreetNames[letter];
2188 while ((offset = *names++) != 0) {
2191 for (int idx = 0; idx < offset; idx++) {
2192 char nameLetter = names[idx];
2193 char testUpper = WTF::toASCIIUpper(test[testIndex]);
2194 if (nameLetter == '*') {
2195 if (testUpper == 'S')
2199 bool fullOnly = WTF::isASCIILower(nameLetter);
2200 nameLetter = WTF::toASCIIUpper(nameLetter);
2201 if (testUpper == nameLetter) {
2202 if (abbr && fullOnly)
2207 if (fullOnly == false)
2211 letter = &test[testIndex] < s->mEnds[wordsIndex] ?
2212 test[testIndex] : ' ';
2213 if (WTF::isASCIIAlpha(letter) == false && WTF::isASCIIDigit(letter) == false) {
2214 if (s->mNumberWords != 0) {
2216 int wordReduction = -1;
2218 while ((s->mNumberWords & (1 << shift)) == 0)
2220 if (shift > wordsIndex)
2222 wordReduction = shift;
2223 } while (s->mNumberWords >> ++shift != 0);
2224 if (wordReduction >= 0) {
2225 if (s->mContinuationNode) {
2230 s->mStartResult = s->mWords[wordReduction] - s->mStarts[wordReduction];
2233 if (wordsIndex != s->mStateWord - 1)
2234 return FOUND_COMPLETE;
2242 s->mProgress = ADDRESS_LINE;
2246 if (s->mNumberWords != 0) {
2248 while ((s->mNumberWords & (1 << shift)) == 0)
2250 s->mNumberWords >>= ++shift;
2251 if (s->mBases[0] != s->mBases[shift])
2253 s->shiftWords(shift);
2254 s->mStartResult = s->mWords[0] - s->mStarts[0];
2255 s->mWordCount -= shift;
2256 s->mProgress = ADDRESS_LINE;
2262 if (s->mContinuationNode)
2264 s->mProgress = NO_ADDRESS;
2265 s->mWordCount = s->mLineCount = 0;
2266 s->mNumberWords = 0;
2270 s->mNumberCount = s->mLetterCount = 0;
2271 s->mFirstLower = NULL;
2272 s->mUnparsed = false;
2275 return s->mProgress == NO_ADDRESS ? FOUND_NONE : FOUND_PARTIAL;
2278 // Recogize common email patterns only. Currently has lots of state, walks text forwards and backwards -- will be
2279 // a real challenge to adapt to walk text across multiple nodes, I imagine
2280 // FIXME: it's too hard for the caller to call these incrementally -- it's probably best for this to
2281 // either walk the node tree directly or make a callout to get the next or previous node, if there is one
2282 // walking directly will avoid adding logic in caller to track the multiple partial or full nodes that compose this
2284 CacheBuilder::FoundState CacheBuilder::FindPartialEMail(const UChar* chars, unsigned length,
2287 // the following tables were generated by tests/browser/focusNavigation/BrowserDebug.cpp
2288 // hand-edit at your own risk
2289 static const int domainTwoLetter[] = {
2290 0x02df797c, // a followed by: [cdefgilmnoqrstuwxz]
2291 0x036e73fb, // b followed by: [abdefghijmnorstvwyz]
2292 0x03b67ded, // c followed by: [acdfghiklmnorsuvxyz]
2293 0x02005610, // d followed by: [ejkmoz]
2294 0x001e00d4, // e followed by: [ceghrstu]
2295 0x00025700, // f followed by: [ijkmor]
2296 0x015fb9fb, // g followed by: [abdefghilmnpqrstuwy]
2297 0x001a3400, // h followed by: [kmnrtu]
2298 0x000f7818, // i followed by: [delmnoqrst]
2299 0x0000d010, // j followed by: [emop]
2300 0x0342b1d0, // k followed by: [eghimnprwyz]
2301 0x013e0507, // l followed by: [abcikrstuvy]
2302 0x03fffccd, // m followed by: [acdghklmnopqrstuvwxyz]
2303 0x0212c975, // n followed by: [acefgilopruz]
2304 0x00001000, // o followed by: [m]
2305 0x014e3cf1, // p followed by: [aefghklmnrstwy]
2306 0x00000001, // q followed by: [a]
2307 0x00504010, // r followed by: [eouw]
2308 0x032a7fdf, // s followed by: [abcdeghijklmnortvyz]
2309 0x026afeec, // t followed by: [cdfghjklmnoprtvwz]
2310 0x03041441, // u followed by: [agkmsyz]
2311 0x00102155, // v followed by: [aceginu]
2312 0x00040020, // w followed by: [fs]
2314 0x00180010, // y followed by: [etu]
2315 0x00401001, // z followed by: [amw]
2318 static char const* const longDomainNames[] = {
2319 "\x03" "ero" "\x03" "rpa", // aero, arpa
2321 "\x02" "at" "\x02" "om" "\x03" "oop", // cat, com, coop
2327 "\x03" "nfo" "\x02" "nt", // info, int
2328 "\x03" "obs", // jobs
2331 "\x02" "il" "\x03" "obi" "\x05" "useum", // mil, mobi, museum
2332 "\x03" "ame" "\x02" "et", // name, net
2333 "\x02" "rg", // , org
2338 "\x05" "ravel", // travel
2347 const UChar* start = chars;
2348 const UChar* end = chars + length;
2349 while (chars < end) {
2350 UChar ch = *chars++;
2353 const UChar* atLocation = chars - 1;
2354 // search for domain
2355 ch = *chars++ | 0x20; // convert uppercase to lower
2356 if (ch < 'a' || ch > 'z')
2358 while (chars < end) {
2360 if (IsDomainChar(ch) == false)
2364 UChar firstLetter = *chars++ | 0x20; // first letter of the domain
2366 return FOUND_NONE; // only one letter; must be at least two
2368 if (firstLetter > 'z' - 'a')
2369 continue; // non-letter followed '.'
2370 int secondLetterMask = domainTwoLetter[firstLetter];
2371 ch = *chars | 0x20; // second letter of the domain
2373 if (ch >= 'z' - 'a')
2375 bool secondMatch = (secondLetterMask & 1 << ch) != 0;
2376 const char* wordMatch = longDomainNames[firstLetter];
2378 while (wordMatch != NULL) {
2379 int len = *wordMatch++;
2382 match = wordMatch[wordIndex];
2384 goto foundDomainStart;
2385 if (chars[wordIndex] != match)
2390 if (*wordMatch == '\0')
2401 if (IsDomainChar(ch))
2403 } else if (chars + 1 < end && IsDomainChar(chars[1]))
2406 // found domain. Search backwards from '@' for beginning of email address
2407 s->mEndResult = chars - start;
2413 goto nextAt; // mailbox can't end in period
2415 if (IsMailboxChar(ch) == false) {
2423 UChar firstChar = *chars;
2424 if (firstChar == '.' || firstChar == '@') // mailbox can't start with period or be empty
2426 s->mStartResult = chars - start;
2427 return FOUND_COMPLETE;
2433 chars = atLocation + 1;
2438 #define PHONE_PATTERN "(200) /-.\\ 100 -. 0000" // poor man's regex: parens optional, any one of punct, digit smallest allowed
2440 CacheBuilder::FoundState CacheBuilder::FindPartialNumber(const UChar* chars, unsigned length,
2443 char* pattern = s->mPattern;
2444 UChar* store = s->mStorePtr;
2445 const UChar* start = chars;
2446 const UChar* end = chars + length;
2447 const UChar* lastDigit = NULL;
2449 bool initialized = s->mInitialized;
2450 while (chars < end) {
2451 if (initialized == false) {
2452 s->mBackTwo = s->mBackOne;
2453 s->mBackOne = s->mCurrent;
2455 UChar ch = s->mCurrent = *chars;
2457 char patternChar = *pattern;
2458 switch (patternChar) {
2460 if (initialized == false) {
2461 s->mStartResult = chars - start;
2466 if (ch < patternChar || ch > '9')
2473 if (WTF::isASCIIDigit(ch) == false) {
2479 if (ch == patternChar)
2483 if (ch == patternChar) {
2484 s->mStartResult = chars - start;
2486 s->mOpenParen = true;
2488 goto commonPunctuation;
2490 if ((ch == patternChar) ^ s->mOpenParen)
2494 if (ch == patternChar) {
2499 } while (++pattern); // never false
2505 if (s->mContinuationNode)
2508 pattern = s->mPattern;
2509 store = s->mStorePtr;
2510 } while (++chars < end);
2512 if (WTF::isASCIIDigit(s->mBackOne != '1' ? s->mBackOne : s->mBackTwo))
2515 s->mStorePtr = store;
2516 s->mPattern = pattern;
2517 s->mEndResult = lastDigit - start + 1;
2518 char pState = pattern[0];
2519 return pState == '\0' ? FOUND_COMPLETE : pState == '(' || (WTF::isASCIIDigit(pState) && WTF::isASCIIDigit(pattern[-1])) ?
2520 FOUND_NONE : FOUND_PARTIAL;
2523 CacheBuilder::FoundState CacheBuilder::FindPhoneNumber(const UChar* chars, unsigned length,
2524 int* start, int* end)
2528 FoundState result = FindPartialNumber(chars, length, &state);
2529 *start = state.mStartResult;
2530 *end = state.mEndResult;
2534 void CacheBuilder::FindReset(FindState* state)
2536 memset(state, 0, sizeof(FindState));
2537 state->mCurrent = ' ';
2538 FindResetNumber(state);
2541 void CacheBuilder::FindResetNumber(FindState* state)
2543 state->mOpenParen = false;
2544 state->mPattern = (char*) PHONE_PATTERN;
2545 state->mStorePtr = state->mStore;
2548 IntRect CacheBuilder::getAreaRect(const HTMLAreaElement* area)
2550 Node* node = area->document();
2551 while ((node = node->traverseNextNode()) != NULL) {
2552 RenderObject* renderer = node->renderer();
2553 if (renderer && renderer->isRenderImage()) {
2554 RenderImage* image = static_cast<RenderImage*>(renderer);
2555 HTMLMapElement* map = image->imageMap();
2558 for (n = map->firstChild(); n;
2559 n = n->traverseNextNode(map)) {
2561 if (area->isDefault())
2562 return image->absoluteBoundingBoxRect();
2563 return area->computeRect(image);
2572 void CacheBuilder::GetGlobalOffset(Node* node, int* x, int * y)
2574 GetGlobalOffset(node->document()->frame(), x, y);
2577 void CacheBuilder::GetGlobalOffset(Frame* frame, int* x, int* y)
2579 // TIMER_PROBE(__FUNCTION__);
2587 while ((parent = frame->tree()->parent()) != NULL) {
2588 const WebCore::IntRect& rect = frame->view()->platformWidget()->getBounds();
2593 // TIMER_PROBE_END();
2596 Frame* CacheBuilder::HasFrame(Node* node)
2598 RenderObject* renderer = node->renderer();
2599 if (renderer == NULL)
2601 if (renderer->isWidget() == false)
2603 Widget* widget = static_cast<RenderWidget*>(renderer)->widget();
2606 if (widget->isFrameView() == false)
2608 return static_cast<FrameView*>(widget)->frame();
2611 bool CacheBuilder::HasOverOrOut(Node* node)
2613 // eventNames are thread-local data, I avoid using 'static' variable here.
2614 AtomicString eventTypes[2] = {
2615 eventNames().mouseoverEvent,
2616 eventNames().mouseoutEvent
2619 return NodeHasEventListeners(node, eventTypes, 2);
2622 bool CacheBuilder::HasTriggerEvent(Node* node)
2624 AtomicString eventTypes[5] = {
2625 eventNames().clickEvent,
2626 eventNames().mousedownEvent,
2627 eventNames().mouseupEvent,
2628 eventNames().keydownEvent,
2629 eventNames().keyupEvent
2632 return NodeHasEventListeners(node, eventTypes, 5);
2635 // #define EMAIL_PATTERN "x@y.d" // where 'x' is letters, numbers, and '-', '.', '_' ; 'y' is 'x' without the underscore, and 'd' is a valid domain
2636 // - 0x2D . 0x2E 0-9 0x30-39 A-Z 0x41-5A _ 0x5F a-z 0x61-7A
2638 bool CacheBuilder::IsDomainChar(UChar ch)
2640 static const unsigned body[] = {0x03ff6000, 0x07fffffe, 0x07fffffe}; // 0-9 . - A-Z a-z
2642 if (ch > 'z' - 0x20)
2644 return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0;
2647 bool CacheBuilder::isFocusableText(NodeWalk* walk, bool more, Node* node,
2648 CachedNodeType* type, String* exported) const
2650 Text* textNode = static_cast<Text*>(node);
2651 StringImpl* string = textNode->dataImpl();
2652 const UChar* baseChars = string->characters();
2653 // const UChar* originalBase = baseChars;
2654 int length = string->length();
2656 while (index < length && isUnicodeSpace(baseChars[index]))
2658 if (index >= length)
2660 if (more == false) {
2663 walk->mFinalNode = node;
2664 walk->mLastInline = NULL;
2666 // starting with this node, search forward for email, phone number, and address
2667 // if any of the three is found, track it so that the remaining can be looked for later
2668 FoundState state = FOUND_NONE;
2669 RenderText* renderer = (RenderText*) node->renderer();
2670 bool foundBetter = false;
2671 InlineTextBox* baseInline = walk->mLastInline != NULL ? walk->mLastInline :
2672 renderer->firstTextBox();
2673 if (baseInline == NULL)
2675 int start = walk->mEnd;
2676 InlineTextBox* saveInline;
2677 int baseStart, firstStart = start;
2678 saveInline = baseInline;
2680 for (CachedNodeType checkType = ADDRESS_CACHEDNODETYPE;
2681 checkType <= PHONE_CACHEDNODETYPE;
2682 checkType = static_cast<CachedNodeType>(checkType + 1))
2684 if ((1 << (checkType - 1) & mAllowableTypes) == 0)
2686 InlineTextBox* inlineTextBox = baseInline;
2687 FindState findState;
2688 FindReset(&findState);
2690 if (checkType == ADDRESS_CACHEDNODETYPE) {
2691 findState.mBases[0] = baseChars;
2692 findState.mWords[0] = baseChars + start;
2693 findState.mStarts[0] = baseChars + start;
2695 Node* lastPartialNode = NULL;
2696 int lastPartialEnd = -1;
2697 bool lastPartialMore = false;
2698 bool firstPartial = true;
2699 InlineTextBox* lastPartialInline = NULL;
2702 const UChar* chars = baseChars + start;
2703 length = inlineTextBox == NULL ? 0 :
2704 inlineTextBox->end() - start + 1;
2705 bool wasInitialized = findState.mInitialized;
2706 switch (checkType) {
2707 case ADDRESS_CACHEDNODETYPE:
2708 state = FindPartialAddress(baseChars, chars, length, &findState);
2710 case EMAIL_CACHEDNODETYPE:
2711 state = FindPartialEMail(chars, length, &findState);
2713 case PHONE_CACHEDNODETYPE:
2714 state = FindPartialNumber(chars, length, &findState);
2719 findState.mInitialized = state != FOUND_NONE;
2720 if (wasInitialized != findState.mInitialized)
2722 if (state == FOUND_PARTIAL) {
2723 lastPartialNode = node;
2724 lastPartialEnd = findState.mEndResult + start;
2725 lastPartialMore = firstPartial &&
2726 lastPartialEnd < (int) string->length();
2727 firstPartial = false;
2728 lastPartialInline = inlineTextBox;
2729 findState.mContinuationNode = true;
2730 } else if (state == FOUND_COMPLETE) {
2731 if (foundBetter == false || walk->mStart > findState.mStartResult) {
2732 walk->mStart = findState.mStartResult + firstStart;
2733 if (findState.mEndResult > 0) {
2734 walk->mFinalNode = node;
2735 walk->mEnd = findState.mEndResult + start;
2736 walk->mMore = node == textNode &&
2737 walk->mEnd < (int) string->length();
2738 walk->mLastInline = inlineTextBox;
2740 walk->mFinalNode = lastPartialNode;
2741 walk->mEnd = lastPartialEnd;
2742 walk->mMore = lastPartialMore;
2743 walk->mLastInline = lastPartialInline;
2746 if (checkType == PHONE_CACHEDNODETYPE) {
2747 const UChar* store = findState.mStore;
2748 *exported = String(store);
2750 Node* temp = textNode;
2752 start = walk->mStart;
2753 exported->truncate(0);
2755 Text* tempText = static_cast<Text*>(temp);
2756 StringImpl* string = tempText->dataImpl();
2757 int end = tempText == walk->mFinalNode ?
2758 walk->mEnd : string->length();
2759 exported->append(String(string->substring(
2760 start, end - start)));
2761 ASSERT(end > start);
2762 length += end - start + 1;
2763 if (temp == walk->mFinalNode)
2767 temp = temp->traverseNextNode();
2769 } while (temp->isTextNode() == false);
2770 // add a space in between text nodes to avoid
2771 // words collapsing together
2772 exported->append(" ");
2777 goto tryNextCheckType;
2778 } else if (findState.mContinuationNode)
2780 if (inlineTextBox == NULL)
2782 inlineTextBox = inlineTextBox->nextTextBox();
2783 if (inlineTextBox == NULL)
2785 start = inlineTextBox->start();
2786 if (state == FOUND_PARTIAL && node == textNode)
2787 findState.mContinuationNode = false;
2789 if (state == FOUND_NONE)
2791 // search for next text node, if any
2797 node = node->traverseNextNode();
2798 if (node == NULL || node->hasTagName(HTMLNames::aTag)
2799 || node->hasTagName(HTMLNames::inputTag)
2800 || node->hasTagName(HTMLNames::textareaTag)) {
2801 if (state == FOUND_PARTIAL &&
2802 checkType == ADDRESS_CACHEDNODETYPE &&
2803 findState.mProgress == ZIP_CODE &&
2804 findState.mNumberCount == 0) {
2806 inlineTextBox = NULL;
2808 findState.mProgress = FIND_STREET;
2811 goto tryNextCheckType;
2813 } while (node->isTextNode() == false);
2814 nextNode = static_cast<Text*>(node);
2815 renderer = (RenderText*) nextNode->renderer();
2816 } while (renderer == NULL);
2817 baseInline = renderer->firstTextBox();
2818 } while (baseInline == NULL);
2819 string = nextNode->dataImpl();
2820 baseChars = string->characters();
2821 inlineTextBox = baseInline;
2822 start = inlineTextBox->start();
2824 findState.mEndResult = 0;
2828 baseInline = saveInline;
2829 string = textNode->dataImpl();
2830 baseChars = string->characters();
2833 CachedNodeType temp = *type;
2835 case ADDRESS_CACHEDNODETYPE: {
2836 static const char geoString[] = "geo:0,0?q=";
2837 exported->insert(String(geoString), 0);
2838 int index = sizeof(geoString) - 1;
2839 String escapedComma("%2C");
2840 while ((index = exported->find(',', index)) >= 0)
2841 exported->replace(index, 1, escapedComma);
2843 case EMAIL_CACHEDNODETYPE: {
2844 String encoded = WebCore::encodeWithURLEscapeSequences(*exported);
2845 exported->swap(encoded);
2846 exported->insert(WTF::String("mailto:"), 0);
2848 case PHONE_CACHEDNODETYPE:
2849 exported->insert(WTF::String("tel:"), 0);
2861 bool CacheBuilder::IsMailboxChar(UChar ch)
2863 // According to http://en.wikipedia.org/wiki/Email_address
2864 // ! # $ % & ' * + - . / 0-9 = ?
2867 static const unsigned body[] = {0xa3ffecfa, 0xc7fffffe, 0x7fffffff};
2869 if (ch > '~' - 0x20)
2871 return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0;
2874 bool CacheBuilder::setData(CachedFrame* cachedFrame)
2876 Frame* frame = FrameAnd(this);
2877 Document* doc = frame->document();
2880 RenderObject* renderer = doc->renderer();
2881 if (renderer == NULL)
2883 RenderLayer* layer = renderer->enclosingLayer();
2886 if (layer->width() == 0 || layer->height() == 0)
2891 GetGlobalOffset(frame, &x, &y);
2892 WebCore::IntRect viewBounds = frame->view()->platformWidget()->getBounds();
2894 viewBounds.setLocation(WebCore::IntPoint(x, y));
2895 cachedFrame->setLocalViewBounds(viewBounds);
2896 cachedFrame->setContentsSize(layer->width(), layer->height());
2897 if (cachedFrame->childCount() == 0)
2899 CachedFrame* lastCachedFrame = cachedFrame->lastChild();
2900 cachedFrame = cachedFrame->firstChild();
2902 CacheBuilder* cacheBuilder = Builder((Frame* )cachedFrame->framePointer());
2903 cacheBuilder->setData(cachedFrame);
2904 } while (cachedFrame++ != lastCachedFrame);
2908 #if USE(ACCELERATED_COMPOSITING)
2909 void CacheBuilder::TrackLayer(WTF::Vector<LayerTracker>& layerTracker,
2910 RenderObject* nodeRenderer, Node* lastChild, int offsetX, int offsetY)
2912 RenderLayer* layer = nodeRenderer->enclosingLayer();
2913 RenderLayerBacking* back = layer->backing();
2916 GraphicsLayer* grLayer = back->graphicsLayer();
2917 if (back->hasContentsLayer())
2918 grLayer = back->foregroundLayer();
2921 LayerAndroid* aLayer = grLayer->platformLayer();
2924 IntPoint scroll(layer->scrollXOffset(), layer->scrollYOffset());
2925 #if ENABLE(ANDROID_OVERFLOW_SCROLL)
2926 // If this is an overflow element, track the content layer.
2927 if (layer->hasOverflowScroll() && aLayer->getChild(0))
2928 aLayer = aLayer->getChild(0)->getChild(0);
2931 // Prevent a crash when scrolling a layer that does not have a parent.
2932 if (layer->stackingContext())
2933 layer->scrollToOffset(0, 0);
2935 layerTracker.grow(layerTracker.size() + 1);
2936 LayerTracker& indexTracker = layerTracker.last();
2937 indexTracker.mLayer = aLayer;
2938 indexTracker.mRenderLayer = layer;
2939 indexTracker.mBounds = enclosingIntRect(aLayer->bounds());
2940 // Use the absolute location of the layer as the bounds location. This
2941 // provides the original offset of nodes in the layer so that we can
2942 // translate nodes between their original location and the layer's new
2944 indexTracker.mBounds.setLocation(layer->absoluteBoundingBox().location());
2945 indexTracker.mBounds.move(offsetX, offsetY);
2946 indexTracker.mScroll = scroll;
2947 indexTracker.mLastChild = OneAfter(lastChild);
2948 DBG_NAV_LOGD("layer=%p [%d] bounds=(%d,%d,w=%d,h=%d)", aLayer,
2949 aLayer->uniqueId(), indexTracker.mBounds.x(), indexTracker.mBounds.y(),
2950 indexTracker.mBounds.width(), indexTracker.mBounds.height());
2954 bool CacheBuilder::validNode(Frame* startFrame, void* matchFrame,
2957 if (matchFrame == startFrame) {
2958 if (matchNode == NULL)
2960 Node* node = startFrame->document();
2961 while (node != NULL) {
2962 if (node == matchNode) {
2963 const IntRect& rect = node->hasTagName(HTMLNames::areaTag) ?
2964 getAreaRect(static_cast<HTMLAreaElement*>(node)) : node->getRect();
2965 // Consider nodes with empty rects that are not at the origin
2966 // to be valid, since news.google.com has valid nodes like this
2967 if (rect.x() == 0 && rect.y() == 0 && rect.isEmpty())
2971 node = node->traverseNextNode();
2973 DBG_NAV_LOGD("frame=%p valid node=%p invalid\n", matchFrame, matchNode);
2976 Frame* child = startFrame->tree()->firstChild();
2978 bool result = validNode(child, matchFrame, matchNode);
2981 child = child->tree()->nextSibling();
2984 if (startFrame->tree()->parent() == NULL)
2985 DBG_NAV_LOGD("frame=%p node=%p false\n", matchFrame, matchNode);
2990 static int Area(const IntRect& rect)
2992 return rect.width() * rect.height();
2995 bool CacheBuilder::AddPartRect(IntRect& bounds, int x, int y,
2996 WTF::Vector<IntRect>* result, IntRect* focusBounds)
2998 if (bounds.isEmpty())
3001 if (bounds.maxX() <= 0 || bounds.maxY() <= 0)
3003 IntRect* work = result->begin() - 1;
3004 IntRect* end = result->end();
3005 while (++work < end) {
3006 if (work->contains(bounds))
3008 if (bounds.contains(*work)) {
3010 focusBounds->unite(bounds);
3013 if ((bounds.x() != work->x() || bounds.width() != work->width()) &&
3014 (bounds.y() != work->y() || bounds.height() != work->height()))
3016 IntRect test = *work;
3018 if (Area(test) > Area(*work) + Area(bounds))
3021 focusBounds->unite(bounds);
3024 if (result->size() >= MAXIMUM_FOCUS_RING_COUNT)
3026 result->append(bounds);
3027 if (focusBounds->isEmpty())
3028 *focusBounds = bounds;
3030 focusBounds->unite(bounds);
3034 bool CacheBuilder::ConstructPartRects(Node* node, const IntRect& bounds,
3035 IntRect* focusBounds, int x, int y, WTF::Vector<IntRect>* result,
3038 WTF::Vector<ClipColumnTracker> clipTracker(1);
3039 ClipColumnTracker* baseTracker = clipTracker.data(); // sentinel
3040 bzero(baseTracker, sizeof(ClipColumnTracker));
3041 if (node->hasChildNodes() && node->hasTagName(HTMLNames::buttonTag) == false
3042 && node->hasTagName(HTMLNames::selectTag) == false) {
3043 // collect all text rects from first to last child
3044 Node* test = node->firstChild();
3047 while ((prior = prior->lastChild()) != NULL)
3049 ASSERT(last != NULL);
3050 bool nodeIsAnchor = node->hasTagName(HTMLNames::aTag);
3053 const ClipColumnTracker* lastClip = &clipTracker.last();
3054 if (test != lastClip->mLastChild)
3056 clipTracker.removeLast();
3058 RenderObject* renderer = test->renderer();
3059 if (renderer == NULL)
3061 EVisibility vis = renderer->style()->visibility();
3064 bool hasClip = renderer->hasOverflowClip();
3065 size_t clipIndex = clipTracker.size();
3066 IntRect clipBounds = IntRect(0, 0, INT_MAX, INT_MAX);
3067 if (hasClip || --clipIndex > 0) {
3068 clipBounds = hasClip ? renderer->absoluteBoundingBoxRect() :
3069 clipTracker.at(clipIndex).mBounds; // x, y fixup done by ConstructTextRect
3071 if (test->isTextNode()) {
3072 RenderText* renderText = (RenderText*) renderer;
3073 InlineTextBox *textBox = renderText->firstTextBox();
3074 if (textBox == NULL)
3076 if (ConstructTextRect((Text*) test, textBox, 0, INT_MAX,
3077 x, y, focusBounds, clipBounds, result) == false) {
3082 if (test->hasTagName(HTMLNames::imgTag)) {
3083 IntRect bounds = test->getRect();
3084 bounds.intersect(clipBounds);
3085 if (AddPartRect(bounds, x, y, result, focusBounds) == false)
3087 *imageCountPtr += 1;
3090 if (hasClip == false) {
3091 if (nodeIsAnchor && test->hasTagName(HTMLNames::divTag)) {
3092 IntRect bounds = renderer->absoluteBoundingBoxRect(); // x, y fixup done by AddPartRect
3093 RenderBox* renderBox = static_cast<RenderBox*>(renderer);
3094 int left = bounds.x() + renderBox->paddingLeft() + renderBox->borderLeft();
3095 int top = bounds.y() + renderBox->paddingTop() + renderBox->borderTop();
3096 int right = bounds.maxX() - renderBox->paddingRight() - renderBox->borderRight();
3097 int bottom = bounds.maxY() - renderBox->paddingBottom() - renderBox->borderBottom();
3098 if (left >= right || top >= bottom)
3100 bounds = IntRect(left, top, right - left, bottom - top);
3101 if (AddPartRect(bounds, x, y, result, focusBounds) == false)
3106 Node* lastChild = test->lastChild();
3107 if (lastChild == NULL)
3109 clipTracker.grow(clipTracker.size() + 1);
3110 ClipColumnTracker& clip = clipTracker.last();
3111 clip.mBounds = renderer->absoluteBoundingBoxRect(); // x, y fixup done by ConstructTextRect
3112 clip.mLastChild = OneAfter(lastChild);
3114 } while (test != last && (test = test->traverseNextNode()) != NULL);
3116 if (result->size() == 0 || focusBounds->width() < MINIMUM_FOCUSABLE_WIDTH
3117 || focusBounds->height() < MINIMUM_FOCUSABLE_HEIGHT) {
3118 if (bounds.width() < MINIMUM_FOCUSABLE_WIDTH)
3120 if (bounds.height() < MINIMUM_FOCUSABLE_HEIGHT)
3122 result->append(bounds);
3123 *focusBounds = bounds;
3128 static inline bool isNotSpace(UChar c)
3130 return c <= 0xA0 ? isUnicodeSpace(c) == false :
3131 WTF::Unicode::direction(c) != WTF::Unicode::WhiteSpaceNeutral;
3134 bool CacheBuilder::ConstructTextRect(Text* textNode,
3135 InlineTextBox* textBox, int start, int relEnd, int x, int y,
3136 IntRect* focusBounds, const IntRect& clipBounds, WTF::Vector<IntRect>* result)
3138 RenderText* renderText = (RenderText*) textNode->renderer();
3139 EVisibility vis = renderText->style()->visibility();
3140 StringImpl* string = textNode->dataImpl();
3141 const UChar* chars = string->characters();
3142 FloatPoint pt = renderText->localToAbsolute();
3144 int textBoxStart = textBox->start();
3145 int textBoxEnd = textBoxStart + textBox->len();
3146 if (textBoxEnd <= start)
3148 if (textBoxEnd > relEnd)
3149 textBoxEnd = relEnd;
3150 IntRect bounds = textBox->selectionRect((int) pt.x(), (int) pt.y(),
3152 bounds.intersect(clipBounds);
3153 if (bounds.isEmpty())
3155 bool drawable = false;
3156 for (int index = start; index < textBoxEnd; index++)
3157 if ((drawable |= isNotSpace(chars[index])) != false)
3159 if (drawable && vis != HIDDEN) {
3160 if (AddPartRect(bounds, x, y, result, focusBounds) == false)
3163 if (textBoxEnd == relEnd)
3165 } while ((textBox = textBox->nextTextBox()) != NULL);
3169 bool CacheBuilder::ConstructTextRects(Text* node, int start,
3170 Text* last, int end, int x, int y, IntRect* focusBounds,
3171 const IntRect& clipBounds, WTF::Vector<IntRect>* result)
3174 *focusBounds = IntRect(0, 0, 0, 0);
3176 RenderText* renderText = (RenderText*) node->renderer();
3177 int relEnd = node == last ? end : renderText->textLength();
3178 InlineTextBox *textBox = renderText->firstTextBox();
3179 if (textBox != NULL) {
3181 if ((int) textBox->end() >= start)
3183 } while ((textBox = textBox->nextTextBox()) != NULL);
3184 if (textBox && ConstructTextRect(node, textBox, start, relEnd,
3185 x, y, focusBounds, clipBounds, result) == false)
3192 node = (Text*) node->traverseNextNode();
3193 ASSERT(node != NULL);
3194 } while (node->isTextNode() == false || node->renderer() == NULL);