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->rendererIsEditable() && !node->parentOrHostNode()->rendererIsEditable()) {
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.setSpellcheck(input->spellcheck());
1250 cachedInput.setFormPointer(input->form());
1251 cachedInput.setIsTextField(true);
1252 exported = input->value().threadsafeCopy();
1253 cachedInput.setMaxLength(input->maxLength());
1254 cachedInput.setTypeFromElement(input);
1255 // If this does not need to be threadsafe, we can use crossThreadString().
1256 // See http://trac.webkit.org/changeset/49160.
1257 cachedInput.setName(input->name().string().threadsafeCopy());
1258 // can't detect if this is drawn on top (example: deviant.com login parts)
1259 isUnclipped = isTransparent;
1260 } else if (input->isInputTypeHidden())
1262 else if (input->isRadioButton() || input->isCheckbox())
1263 isTransparent = false;
1264 } else if (node->hasTagName(HTMLNames::textareaTag)) {
1265 HTMLTextAreaElement* area = static_cast<HTMLTextAreaElement*>(node);
1266 if (area->readOnly())
1269 type = TEXT_INPUT_CACHEDNODETYPE;
1270 cachedInput.setFormPointer(area->form());
1271 cachedInput.setIsTextArea(true);
1272 exported = area->value().threadsafeCopy();
1273 } else if (node->hasTagName(HTMLNames::aTag)) {
1274 const HTMLAnchorElement* anchorNode =
1275 (const HTMLAnchorElement*) node;
1276 if (!anchorNode->isFocusable() && !HasTriggerEvent(node))
1278 if (node->disabled())
1280 hasMouseOver = NodeHasEventListeners(node, &eventNames().mouseoverEvent, 1);
1281 type = ANCHOR_CACHEDNODETYPE;
1282 KURL href = anchorNode->href();
1283 if (!href.isEmpty() && !WebCore::protocolIsJavaScript(href.string()))
1284 // Set the exported string for all non-javascript anchors.
1285 exported = href.string().threadsafeCopy();
1286 } else if (node->hasTagName(HTMLNames::selectTag)) {
1287 type = SELECT_CACHEDNODETYPE;
1289 if (type == TEXT_INPUT_CACHEDNODETYPE) {
1290 RenderTextControl* renderText =
1291 static_cast<RenderTextControl*>(nodeRenderer);
1293 cachedRoot->setSelection(renderText->selectionStart(), renderText->selectionEnd());
1294 // FIXME: Are we sure there will always be a style and font, and it's correct?
1295 RenderStyle* style = nodeRenderer->style();
1297 isUnclipped |= !style->hasAppearance();
1298 int lineHeight = -1;
1299 Length lineHeightLength = style->lineHeight();
1300 // If the lineHeight is negative, WebTextView will calculate it
1301 // based on the text size, using the Paint.
1302 // See RenderStyle.computedLineHeight.
1303 if (lineHeightLength.isPositive())
1304 lineHeight = style->computedLineHeight();
1305 cachedInput.setLineHeight(lineHeight);
1306 cachedInput.setTextSize(style->font().size());
1307 cachedInput.setIsRtlText(style->direction() == RTL
1308 || style->textAlign() == WebCore::RIGHT
1309 || style->textAlign() == WebCore::WEBKIT_RIGHT);
1311 cachedInput.setPaddingLeft(renderText->paddingLeft() + renderText->borderLeft());
1312 cachedInput.setPaddingTop(renderText->paddingTop() + renderText->borderTop());
1313 cachedInput.setPaddingRight(renderText->paddingRight() + renderText->borderRight());
1314 cachedInput.setPaddingBottom(renderText->paddingBottom() + renderText->borderBottom());
1318 if (type != ANCHOR_CACHEDNODETYPE) {
1319 bool isFocusable = node->isKeyboardFocusable(NULL) ||
1320 node->isMouseFocusable() || node->isFocusable();
1321 if (isFocusable == false) {
1322 if (node->disabled())
1324 bool overOrOut = HasOverOrOut(node);
1325 bool hasTrigger = HasTriggerEvent(node);
1326 if (overOrOut == false && hasTrigger == false)
1328 takesFocus = hasTrigger;
1331 computeCursorRings = true;
1333 cachedNode.init(node);
1334 if (computeCursorRings == false) {
1335 cachedNode.setBounds(bounds);
1336 cachedNode.mCursorRing.append(bounds);
1337 } else if (ConstructPartRects(node, bounds, &cachedNode.mBounds,
1338 globalOffsetX, globalOffsetY, &cachedNode.mCursorRing,
1339 &imageCount) == false)
1342 if (nodeRenderer) { // area tags' node->renderer() == 0
1343 RenderStyle* style = nodeRenderer->style();
1344 const void* styleDataPtr = style->ringData();
1345 // to save time, see if we're pointing to the same style data as before
1346 if (lastStyleDataPtr != styleDataPtr) {
1347 lastStyleDataPtr = styleDataPtr;
1348 cachedColor.setFillColor(style->ringFillColor());
1349 cachedColor.setInnerWidth(style->ringInnerWidth());
1350 cachedColor.setOuterWidth(style->ringOuterWidth());
1351 cachedColor.setOutset(style->ringOutset());
1352 cachedColor.setPressedInnerColor(style->ringPressedInnerColor());
1353 cachedColor.setPressedOuterColor(style->ringPressedOuterColor());
1354 cachedColor.setRadius(style->ringRadius());
1355 cachedColor.setSelectedInnerColor(style->ringSelectedInnerColor());
1356 cachedColor.setSelectedOuterColor(style->ringSelectedOuterColor());
1357 int oldSize = colorTracker.size();
1358 colorIndex = FindColorIndex(colorTracker, cachedColor);
1359 if (colorIndex == oldSize)
1360 cachedFrame->add(cachedColor);
1364 IntRect clip = hasClip ? bounds : absBounds;
1365 size_t clipIndex = clipTracker.size();
1366 if (clipTracker.last().mNode == node)
1368 while (--clipIndex > 0) {
1369 const ClipColumnTracker& clipTrack = clipTracker.at(clipIndex);
1370 if (clipTrack.mHasClip == false) {
1371 adjustForColumns(clipTrack, &cachedNode, &absBounds, static_cast<RenderBlock*>(nodeRenderer));
1374 const IntRect& parentClip = clipTrack.mBounds;
1375 if (hasClip == false && type == ANCHOR_CACHEDNODETYPE)
1378 clip.intersect(parentClip);
1381 bool isInLayer = false;
1382 #if USE(ACCELERATED_COMPOSITING)
1383 // If this renderer has a composited parent layer (including itself),
1384 // add the node to the cached layer.
1385 // FIXME: does not work for area rects
1386 RenderLayer* enclosingLayer = nodeRenderer->enclosingLayer();
1387 if (enclosingLayer && enclosingLayer->enclosingCompositingLayer()) {
1388 LayerAndroid* layer = layerTracker.last().mLayer;
1390 const IntRect& layerClip = layerTracker.last().mBounds;
1391 if (!layerClip.isEmpty() && !cachedNode.clip(layerClip)) {
1392 DBG_NAV_LOGD("skipped on layer clip %d", cacheIndex);
1393 continue; // skip this node if outside of the clip
1396 isUnclipped = true; // assume that layers do not have occluded nodes
1398 AddLayer(cachedFrame, cachedFrame->size(), layerClip.location(),
1405 continue; // skip this node if clip prevents all drawing
1406 else if (cachedNode.clip(clip) == false)
1407 continue; // skip this node if outside of the clip
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();
1482 CachedNode* onlyChildCached = cachedFrame->lastNode();
1483 Node* onlyChild = (Node*) onlyChildCached->nodePointer();
1484 bool outerIsMouseMoveOnly =
1485 lastNode->isKeyboardFocusable(NULL) == false &&
1486 lastNode->isMouseFocusable() == false &&
1487 lastNode->isFocusable() == false &&
1488 HasOverOrOut(lastNode) == true &&
1489 HasTriggerEvent(lastNode) == false;
1490 if (onlyChildCached->parent() == lastCached)
1491 onlyChildCached->setParentIndex(lastCached->parentIndex());
1492 bool hasFocus = lastCached->isFocus() || onlyChildCached->isFocus();
1493 if (outerIsMouseMoveOnly || onlyChild->isKeyboardFocusable(NULL)
1494 || onlyChildCached->isPlugin()) {
1495 int index = lastCached->index();
1496 *lastCached = *onlyChildCached;
1497 lastCached->setIndex(index);
1498 CachedFrame* frame = cachedFrame->hasFrame(lastCached);
1500 frame->setIndexInParent(index);
1502 cachedFrame->removeLast();
1504 cachedRoot->setCachedFocus(cachedFrame, cachedFrame->lastNode());
1508 Node* CacheBuilder::currentFocus() const
1510 Frame* frame = FrameAnd(this);
1511 Document* doc = frame->document();
1513 Node* focus = doc->focusedNode();
1517 Frame* child = frame->tree()->firstChild();
1519 CacheBuilder* cacheBuilder = Builder(child);
1520 Node* focus = cacheBuilder->currentFocus();
1523 child = child->tree()->nextSibling();
1528 static bool strCharCmp(const char* matches, const UChar* test, int wordLength,
1531 for (int index = 0; index < wordCount; index++) {
1532 for (int inner = 0; inner < wordLength; inner++) {
1533 if (matches[inner] != test[inner]) {
1534 matches += wordLength;
1545 static const int stateTwoLetter[] = {
1546 0x02060c00, // A followed by: [KLRSZ]
1548 0x00084001, // C followed by: [AOT]
1549 0x00000014, // D followed by: [CE]
1551 0x00001800, // F followed by: [LM]
1552 0x00100001, // G followed by: [AU]
1553 0x00000100, // H followed by: [I]
1554 0x00002809, // I followed by: [ADLN]
1556 0x01040000, // K followed by: [SY]
1557 0x00000001, // L followed by: [A]
1558 0x000ce199, // M followed by: [ADEHINOPST]
1559 0x0120129c, // N followed by: [CDEHJMVY]
1560 0x00020480, // O followed by: [HKR]
1561 0x00420001, // P followed by: [ARW]
1563 0x00000100, // R followed by: [I]
1564 0x0000000c, // S followed by: [CD]
1565 0x00802000, // T followed by: [NX]
1566 0x00080000, // U followed by: [T]
1567 0x00080101, // V followed by: [AIT]
1568 0x01200101 // W followed by: [AIVY]
1571 static const char firstIndex[] = {
1572 0, 5, 5, 8, 10, 10, 12, 14,
1573 15, 19, 19, 21, 22, 32, 40, 43,
1574 46, 46, 47, 49, 51, 52, 55, 59
1577 // from http://infolab.stanford.edu/~manku/bitcount/bitcount.html
1578 #define TWO(c) (0x1u << (c))
1579 #define MASK(c) (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
1580 #define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
1582 int bitcount (unsigned int n)
1595 static bool isUnicodeSpace(UChar ch)
1597 return ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r' || ch == 0xa0;
1600 static bool validZip(int stateIndex, const UChar* zipPtr)
1602 static const struct {
1608 { 99, 99, -1, -1 }, // AK Alaska
1609 { 35, 36, -1, -1 }, // AL Alabama
1610 { 71, 72, -1, -1 }, // AR Arkansas
1611 { 96, 96, -1, -1 }, // AS American Samoa
1612 { 85, 86, -1, -1 }, // AZ Arizona
1613 { 90, 96, -1, -1 }, // CA California
1614 { 80, 81, -1, -1 }, // CO Colorado
1615 { 6, 6, -1, -1 }, // CT Connecticut
1616 { 20, 20, -1, -1 }, // DC District of Columbia
1617 { 19, 19, -1, -1 }, // DE Delaware
1618 { 32, 34, -1, -1 }, // FL Florida
1619 { 96, 96, -1, -1 }, // FM Federated States of Micronesia
1620 { 30, 31, -1, -1 }, // GA Georgia
1621 { 96, 96, -1, -1 }, // GU Guam
1622 { 96, 96, -1, -1 }, // HI Hawaii
1623 { 50, 52, -1, -1 }, // IA Iowa
1624 { 83, 83, -1, -1 }, // ID Idaho
1625 { 60, 62, -1, -1 }, // IL Illinois
1626 { 46, 47, -1, -1 }, // IN Indiana
1627 { 66, 67, 73, -1 }, // KS Kansas
1628 { 40, 42, -1, -1 }, // KY Kentucky
1629 { 70, 71, -1, -1 }, // LA Louisiana
1630 { 1, 2, -1, -1 }, // MA Massachusetts
1631 { 20, 21, -1, -1 }, // MD Maryland
1632 { 3, 4, -1, -1 }, // ME Maine
1633 { 96, 96, -1, -1 }, // MH Marshall Islands
1634 { 48, 49, -1, -1 }, // MI Michigan
1635 { 55, 56, -1, -1 }, // MN Minnesota
1636 { 63, 65, -1, -1 }, // MO Missouri
1637 { 96, 96, -1, -1 }, // MP Northern Mariana Islands
1638 { 38, 39, -1, -1 }, // MS Mississippi
1639 { 55, 56, -1, -1 }, // MT Montana
1640 { 27, 28, -1, -1 }, // NC North Carolina
1641 { 58, 58, -1, -1 }, // ND North Dakota
1642 { 68, 69, -1, -1 }, // NE Nebraska
1643 { 3, 4, -1, -1 }, // NH New Hampshire
1644 { 7, 8, -1, -1 }, // NJ New Jersey
1645 { 87, 88, 86, -1 }, // NM New Mexico
1646 { 88, 89, 96, -1 }, // NV Nevada
1647 { 10, 14, 0, 6 }, // NY New York
1648 { 43, 45, -1, -1 }, // OH Ohio
1649 { 73, 74, -1, -1 }, // OK Oklahoma
1650 { 97, 97, -1, -1 }, // OR Oregon
1651 { 15, 19, -1, -1 }, // PA Pennsylvania
1652 { 6, 6, 0, 9 }, // PR Puerto Rico
1653 { 96, 96, -1, -1 }, // PW Palau
1654 { 2, 2, -1, -1 }, // RI Rhode Island
1655 { 29, 29, -1, -1 }, // SC South Carolina
1656 { 57, 57, -1, -1 }, // SD South Dakota
1657 { 37, 38, -1, -1 }, // TN Tennessee
1658 { 75, 79, 87, 88 }, // TX Texas
1659 { 84, 84, -1, -1 }, // UT Utah
1660 { 22, 24, 20, -1 }, // VA Virginia
1661 { 6, 9, -1, -1 }, // VI Virgin Islands
1662 { 5, 5, -1, -1 }, // VT Vermont
1663 { 98, 99, -1, -1 }, // WA Washington
1664 { 53, 54, -1, -1 }, // WI Wisconsin
1665 { 24, 26, -1, -1 }, // WV West Virginia
1666 { 82, 83, -1, -1 } // WY Wyoming
1669 int zip = zipPtr[0] - '0';
1671 zip += zipPtr[1] - '0';
1672 int low = zipRange[stateIndex].mLow;
1673 int high = zipRange[stateIndex].mHigh;
1674 if (zip >= low && zip <= high)
1676 if (zip == zipRange[stateIndex].mException1)
1678 if (zip == zipRange[stateIndex].mException2)
1683 #define MAX_PLACE_NAME_LENGTH 25 // the longest allowable one word place name
1685 CacheBuilder::FoundState CacheBuilder::FindAddress(const UChar* chars,
1686 unsigned length, int* start, int* end, bool caseInsensitive)
1688 FindState addressState;
1689 FindReset(&addressState);
1690 addressState.mWords[0] = addressState.mStarts[0] = chars;
1691 addressState.mCaseInsensitive = caseInsensitive;
1692 FoundState state = FindPartialAddress(chars, chars, length, &addressState);
1693 if (state == FOUND_PARTIAL && addressState.mProgress == ZIP_CODE &&
1694 addressState.mNumberCount == 0) {
1695 addressState.mProgress = FIND_STREET;
1696 state = FindPartialAddress(NULL, NULL, 0, &addressState);
1698 *start = addressState.mStartResult;
1699 *end = addressState.mEndResult;
1703 CacheBuilder::FoundState CacheBuilder::FindPartialAddress(const UChar* baseChars,
1704 const UChar* chars, unsigned length, FindState* s)
1706 // lower case letters are optional; trailing asterisk is optional 's'
1707 static char const* const longStreetNames[] = {
1708 "\x04" "LleY" "\x04" "NneX" "\x05" "RCade" "\x05" "VEnue" "\x06" "LAMEDA", // A
1709 "\x04" "aYoU" "\x04" "eaCH" "\x03" "eND" "\x05" "LuFf*" "\x05" "oTtoM"
1710 "\x08" "ouLeVarD" "\x05" "Ranch" "\x05" "RidGe" "\x05" "RooK*"
1711 "\x04" "urG*" "\x05" "YPass" "\x07" "roadWAY", // B
1713 "\x03" "amP" "\x05" "anYoN" "\x03" "aPE" "\x07" "auSeWaY" "\x06" "enTeR*"
1714 "\x06" "IRcle*" "\x05" "LiFf*" "\x03" "LuB" "\x05" "oMmoN" "\x06" "ORner*"
1715 "\x05" "ouRSE" "\x05" "ourT*" "\x04" "oVe*" "\x04" "ReeK" "\x07" "REScent"
1716 "\x04" "ReST" "\x07" "ROSSING" "\x08" "ROSSROAD" "\x04" "URVe"
1717 "\x05" "AMINO" "\x06" "IRCULO" "\x07" "REScent", // C
1718 "\x03" "aLe" "\x02" "aM" "\x05" "iVide" "\x05" "Rive*", // D
1719 "\x06" "STate*" "\x09" "XPresswaY" "\x09" "XTension*", // E
1720 "\x04" "ALL*" "\x04" "eRrY" "\x05" "ieLD*" "\x04" "LaT*" "\x04" "oRD*"
1721 "\x05" "oReST" "\x05" "oRGe*" "\x04" "oRK*" "\x03" "orT" "\x06" "reeWaY", // F
1722 "\x06" "arDeN*" "\x06" "aTeWaY" "\x04" "LeN*" "\x05" "ReeN*" "\x05" "RoVe*", // G
1723 "\x06" "arBoR*" "\x04" "aVeN" "\x06" "eighTS" "\x06" "ighWaY" "\x04" "iLl*"
1724 "\x05" "OLloW", // H
1725 "\x04" "NLeT" "\x06" "Sland*" "\x03" "SLE", // I
1726 "\x08" "unCTion*", // J
1727 "\x03" "eY*" "\x05" "NoLl*", // K
1728 "\x04" "aKe*" "\x03" "AND" "\x06" "aNDinG" "\x03" "aNe" "\x05" "iGhT*"
1729 "\x03" "oaF" "\x04" "oCK*" "\x04" "oDGe" "\x03" "OOP", // L
1730 "\x03" "ALL" "\x05" "aNoR*" "\x06" "eaDoW*" "\x03" "EWS" "\x04" "iLl*"
1731 "\x06" "iSsioN" "\x07" "oTorWaY" "\x04" "ounT" "\x08" "ounTaiN*", // M
1733 "\x06" "RCHard" "\x03" "VAL" "\x07" "verPASs", // O
1734 "\x04" "ARK*" "\x07" "arKWaY*" "\x03" "ASS" "\x06" "aSsaGE" "\x03" "ATH"
1735 "\x03" "IKE" "\x04" "iNE*" "\x04" "Lace" "\x05" "LaiN*" "\x04" "LaZa"
1736 "\x05" "oinT*" "\x04" "oRT*" "\x06" "Rairie" "\x06" "RIVADA", // P
1738 "\x05" "ADiaL" "\x03" "AMP" "\x04" "aNCH" "\x05" "aPiD*"
1740 "\x05" "iDGe*" "\x04" "IVer" "\x04" "oaD*" "\x04" "ouTE" "\x02" "OW"
1741 "\x02" "UE" "\x02" "UN", // R
1742 "\x05" "HoaL*" "\x05" "HoRe*" "\x05" "KyWaY" "\x06" "PrinG*" "\x04" "PUR*"
1743 "\x06" "Quare*" "\x06" "TAtion" "\x08" "TRAvenue" "\x05" "TReaM"
1744 "\x06" "Treet*" "\x05" "uMmiT" "\x07" "PeeDWaY", // S
1745 "\x06" "ERrace" "\x09" "hRoughWaY" "\x04" "RaCE" "\x04" "RAcK" "\x09" "RaFficwaY"
1746 "\x04" "RaiL" "\x05" "UNneL" "\x07" "urnPiKE", // T
1747 "\x08" "nderPASs" "\x05" "Nion*", // U
1748 "\x06" "aLleY*" "\x06" "IAduct" "\x04" "ieW*" "\x07" "iLlaGe*" "\x04" "iLle"
1750 "\x04" "ALK*" "\x03" "ALL" "\x03" "AY*" "\x04" "eLl*", // W
1751 "\x03" "ING" "\x02" "RD", // X
1754 static char const* const longStateNames[] = {
1755 "\x8e" "la" "\x85" "bama" "\x02" "\x84" "ska" "\x01" "\x8f" "merican Samoa" "\x04"
1756 "\x91" "r" "\x86" "izona" "\x05" "\x87" "kansas" "\x03",
1758 "\x8b" "alifornia" "\x06" "\x95" "o" "\x87" "lorado" "\x07" "\x8a" "nnecticut" "\x08",
1759 "\x89" "elaware" "\x0a" "\x95" "istrict of Columbia" "\x09",
1761 "\x9f" "ederated States of Micronesia" "\x0c" "\x88" "lorida" "\x0b",
1762 "\x85" "uam" "\x0e" "\x88" "eorgia" "\x0d",
1763 "\x87" "awaii" "\x0f",
1764 "\x86" "daho" "\x11" "\x89" "llinois" "\x12" "\x88" "ndiana" "\x13" "\x85"
1767 "\x87" "ansas" "\x14" "\x89" "entucky" "\x15",
1768 "\x8a" "ouisiana" "\x16",
1769 "\x86" "aine" "\x19" "\x99" "ar" "\x8e" "shall Islands" "\x1a" "\x86" "yland" "\x18"
1770 "\x8e" "assachusetts" "\x17" "\x93" "i" "\x87" "chigan" "\x1b"
1771 "\x88" "nnesota" "\x1c" "\x93" "iss" "\x88" "issippi" "\x1f" "\x85"
1772 "ouri" "\x1d" "\x88" "ontana" "\x20",
1773 "\x90" "e" "\x87" "braska" "\x23" "\x85" "vada" "\x27" "\xa5" "ew " "\x8a"
1774 "Hampshire" "\x24" "\x87" "Jersey" "\x25" "\x87" "Mexico" "\x26"
1775 "\x85" "York" "\x28" "\x98" "orth " "\x89" "Carolina" "\x21" "\x87"
1776 "Dakota" "\x22" "\x99" "orthern Mariana Islands" "\x1e",
1777 "\x85" "hio" "\x29" "\x89" "klahoma" "\x2a" "\x87" "regon" "\x2b",
1778 "\x86" "alau" "\x2e" "\x8d" "ennsylvania" "\x2c" "\x8c" "uerto Rico" "\x2d",
1780 "\x8d" "hode Island" "\x2f",
1781 "\x98" "outh " "\x89" "Carolina" "\x30" "\x87" "Dakota" "\x31",
1782 "\x90" "e" "\x88" "nnessee" "\x32" "\x84" "xas" "\x33",
1783 "\x85" "tah" "\x34",
1784 "\x88" "ermont" "\x37" "\x94" "irgin" "\x89" " Islands" "\x36" "\x83" "ia" "\x35",
1785 "\x8b" "ashington" "\x38" "\x8e" "est Virginia" "\x3a" "\x8a" "isconsin" "\x39"
1786 "\x88" "yoming" "\x3b"
1789 #if 0 // DEBUG_NAV_UI
1790 static char const* const progressNames[] = {
1794 "NUMBER_TRAILING_SPACE",
1803 // strategy: US only support at first
1804 // look for a 1 - 5 digit number for a street number (no support for 'One Microsoft Way')
1805 // ignore if preceded by '#', Suite, Ste, Rm
1806 // look for two or more words (up to 5? North Frank Lloyd Wright Blvd)
1807 // note: "The Circle at North Hills St." has six words, and a lower 'at' -- allow at, by, of, in, the, and, ... ?
1808 // if a word starts with a lowercase letter, no match
1809 // allow: , . - # / (for 1/2) ' "
1810 // don't look for street name type yet
1811 // look for one or two delimiters to represent possible 2nd addr line and city name
1812 // look for either full state name, or state two letters, and/or zip code (5 or 9 digits)
1813 // now look for street suffix, either in full or abbreviated form, with optional 's' if there's an asterisk
1815 s->mCurrentStart = chars;
1816 s->mEnd = chars + length;
1819 bool mustBeAllUpper = false;
1820 bool secondHalf = false;
1822 UChar ch = s->mCurrent;
1823 while (++chars <= s->mEnd) {
1825 ch = chars < s->mEnd ? *chars : ' ';
1826 switch (s->mProgress) {
1828 if (WTF::isASCIIDigit(ch) == false) {
1829 if (ch != 'O') // letter 'O', not zero
1831 if (s->mEnd - chars < 3)
1835 if ((prior != 'n' || ch != 'e') && (prior != 'N' || ch != 'E'))
1837 if (isUnicodeSpace(*++chars) == false)
1839 s->mProgress = ADDRESS_LINE;
1840 s->mStartResult = chars - 3 - s->mCurrentStart;
1843 if (isUnicodeSpace(prior) == false) {
1844 s->mProgress = SKIP_TO_SPACE;
1847 s->mNumberCount = 1;
1848 s->mProgress = HOUSE_NUMBER;
1849 s->mStartResult = chars - s->mCurrentStart;
1852 if (isUnicodeSpace(ch) == false)
1856 if (WTF::isASCIIDigit(ch)) {
1857 if (++s->mNumberCount >= 6)
1858 s->mProgress = SKIP_TO_SPACE;
1861 if (WTF::isASCIIUpper(ch)) { // allow one letter after house number, e.g. 12A SKOLFIELD PL, HARPSWELL, ME 04079
1862 if (WTF::isASCIIDigit(prior) == false)
1863 s->mProgress = SKIP_TO_SPACE;
1867 if (s->mNumberCount > 0) { // permit 21-23 ELM ST
1872 s->mNumberCount = 0;
1873 s->mProgress = NUMBER_TRAILING_SPACE;
1874 case NUMBER_TRAILING_SPACE:
1875 if (isUnicodeSpace(ch))
1877 if (0 && WTF::isASCIIDigit(ch)) {
1878 s->mNumberCount = 1;
1879 s->mProgress = HOUSE_NUMBER;
1880 s->mStartResult = chars - s->mCurrentStart;
1883 if (WTF::isASCIIDigit(ch) == false && WTF::isASCIIUpper(ch) == false)
1885 s->mProgress = ADDRESS_LINE;
1887 if (WTF::isASCIIAlpha(ch) || ch == '\'' || ch == '-' || ch == '&' || ch == '(' || ch == ')') {
1888 if (++s->mLetterCount > 1) {
1889 s->mNumberWords &= ~(1 << s->mWordCount);
1892 if (s->mNumberCount >= 5)
1894 // FIXME: the test below was added to give up on a non-address, but it
1895 // incorrectly discards addresses where the house number is in one node
1896 // and the street name is in the next; I don't recall what the failing case
1897 // is that suggested this fix.
1898 // if (s->mWordCount == 0 && s->mContinuationNode)
1899 // return FOUND_NONE;
1900 s->newWord(baseChars, chars);
1901 if (WTF::isASCIILower(ch) && s->mNumberCount == 0)
1902 s->mFirstLower = chars;
1903 s->mNumberCount = 0;
1904 if (WTF::isASCIILower(ch) || (WTF::isASCIIAlpha(ch) == false && ch != '-'))
1905 s->mNumberWords &= ~(1 << s->mWordCount);
1906 s->mUnparsed = true;
1908 } else if (s->mLetterCount >= MAX_PLACE_NAME_LENGTH) {
1910 } else if (s->mFirstLower != NULL) {
1911 if (s->mCaseInsensitive)
1913 size_t length = chars - s->mFirstLower;
1916 if (length == 3 && strCharCmp("and" "the", s->mFirstLower, 3, 2) == false)
1918 if (length == 2 && strCharCmp("at" "by" "el" "in" "of", s->mFirstLower, 2, 5) == false)
1922 if (ch == ',' || ch == '*') { // delimits lines
1923 // asterisk as delimiter: http://www.sa.sc.edu/wellness/members.html
1924 if (++s->mLineCount > 5)
1928 if (isUnicodeSpace(ch) || prior == '-') {
1930 if (s->mUnparsed == false)
1932 const UChar* candidate = s->mWords[s->mWordCount];
1933 UChar firstLetter = candidate[0];
1934 if (WTF::isASCIIUpper(firstLetter) == false && WTF::isASCIIDigit(firstLetter) == false)
1937 if ((s->mWordCount == 2 && s->mNumberWords == 3 && WTF::isASCIIDigit(s->mWords[1][1])) || // choose second of 8888 333 Main
1938 (s->mWordCount >= sizeof(s->mWords) / sizeof(s->mWords[0]) - 1)) { // subtract 1 since state names may have two parts
1939 // search for simple number already stored since first potential house # didn't pan out
1940 if (s->mNumberWords == 0)
1943 while ((s->mNumberWords & (1 << shift)) == 0)
1945 s->mNumberWords >>= ++shift;
1946 if (s->mBases[0] != s->mBases[shift]) // if we're past the original node, bail
1948 s->shiftWords(shift);
1949 s->mStartResult = s->mWords[0] - s->mStarts[0];
1950 s->mWordCount -= shift;
1951 // FIXME: need to adjust lineCount to account for discarded delimiters
1953 if (s->mWordCount < 4)
1956 if (firstLetter > 'W' - 'A')
1958 UChar secondLetter = candidate[1];
1960 s->mLetterCount--; // trim trailing dashes, to accept CA-94043
1961 if (s->mLetterCount == 2) {
1962 secondLetter -= 'A';
1963 if (secondLetter > 'Z' - 'A')
1965 if ((stateTwoLetter[firstLetter] & 1 << secondLetter) != 0) {
1966 // special case to ignore 'et al'
1967 if (strCharCmp("ET", s->mWords[s->mWordCount - 2], 2, 1) == false) {
1968 s->mStateWord = s->mWordCount - 1;
1969 s->mZipHint = firstIndex[firstLetter] +
1970 bitcount(stateTwoLetter[firstLetter] & ((1 << secondLetter) - 1));
1971 goto foundStateName;
1976 s->mStates = longStateNames[firstLetter];
1977 if (s->mStates == NULL)
1979 mustBeAllUpper = false;
1980 s->mProgress = STATE_NAME;
1981 unsigned char section = s->mStates[0];
1982 ASSERT(section > 0x80);
1983 s->mSectionLength = section & 0x7f;
1986 s->mStateWord = s->mWordCount - 1;
1989 if (WTF::isASCIIDigit(ch)) {
1990 if (s->mLetterCount == 0) {
1991 if (++s->mNumberCount > 1)
1993 if (s->mWordCount == 0 && s->mContinuationNode)
1995 s->newWord(baseChars, chars);
1996 s->mNumberWords |= 1 << s->mWordCount;
1997 s->mUnparsed = true;
2001 if (ch == '.') { // optionally can follow letters
2002 if (s->mLetterCount == 0)
2004 if (s->mNumberCount > 0)
2008 if (ch == '/') // between numbers (1/2) between words (12 Main / Ste 4d)
2010 if (ch == '#') // can precede numbers, allow it to appear randomly
2012 if (ch == '"') // sometimes parts of addresses are quoted (FIXME: cite an example here)
2016 if (WTF::isASCIIAlpha(ch)) {
2017 if (s->mLetterCount == 0) {
2018 s->newWord(baseChars, chars);
2024 if (WTF::isASCIIDigit(ch) == false) {
2025 if (s->mLetterCount > 0) {
2026 s->mProgress = STATE_NAME;
2033 s->mProgress = ADDRESS_LINE;
2037 // pick up length of first section
2042 bool subStr = false;
2044 unsigned char match = s->mStates[stateIndex];
2045 if (match >= 0x80) {
2046 if (stateIndex == s->mSectionLength)
2050 // goto foundStateName;
2052 skip = match & 0x7f;
2053 match = s->mStates[++stateIndex];
2055 UChar candChar = s->mWords[s->mWordCount - 1][candIndex];
2056 if (mustBeAllUpper && WTF::isASCIILower(candChar))
2058 if (match != candChar) {
2059 if (match != WTF::toASCIILower(candChar)) {
2061 if (subStr == false)
2063 if (stateIndex == s->mSectionLength) {
2065 s->mProgress = ADDRESS_LINE;
2073 continue; // try next substring
2075 mustBeAllUpper = true;
2077 int nextindex = stateIndex + 1;
2078 if (++candIndex >= s->mLetterCount && s->mStates[nextindex] == ' ') {
2079 s->mProgress = SECOND_HALF;
2080 s->mStates += nextindex;
2081 s->mSectionLength -= nextindex;
2084 if (nextindex + 1 == s->mSectionLength || skip == 2) {
2085 s->mZipHint = s->mStates[nextindex] - 1;
2086 goto foundStateName;
2091 s->mStates += s->mSectionLength;
2092 ASSERT(s->mStates[0] == 0 || (unsigned) s->mStates[0] > 0x80);
2093 s->mSectionLength = s->mStates[0] & 0x7f;
2096 } while (s->mSectionLength != 0);
2097 s->mProgress = ADDRESS_LINE;
2100 s->mEndResult = chars - s->mCurrentStart;
2101 s->mEndWord = s->mWordCount - 1;
2102 s->mProgress = ZIP_CODE;
2103 // a couple of delimiters is an indication that the state name is good
2104 // or, a non-space / non-alpha-digit is also good
2105 s->mZipDelimiter = s->mLineCount > 2
2106 || isUnicodeSpace(ch) == false
2107 || chars == s->mEnd;
2108 if (WTF::isASCIIDigit(ch))
2109 s->mZipStart = chars;
2112 if (WTF::isASCIIDigit(ch)) {
2113 int count = ++s->mNumberCount;
2115 if (WTF::isASCIIDigit(prior))
2118 s->mZipStart = chars;
2122 } else if (isUnicodeSpace(ch)) {
2123 if (s->mNumberCount == 0) {
2124 s->mZipDelimiter = true; // two spaces delimit state name
2127 } else if (ch == '-') {
2128 if (s->mNumberCount == 5 && validZip(s->mZipHint, s->mZipStart)) {
2129 s->mNumberCount = 0;
2130 s->mProgress = PLUS_4;
2133 if (s->mNumberCount == 0)
2134 s->mZipDelimiter = true;
2135 } else if (WTF::isASCIIAlpha(ch) == false)
2136 s->mZipDelimiter = true;
2138 if (s->mLetterCount == 0) {
2139 s->newWord(baseChars, chars);
2140 s->mUnparsed = true;
2144 if (s->mNumberCount == 5 || s->mNumberCount == 9) {
2145 if (validZip(s->mZipHint, s->mZipStart) == false)
2147 s->mEndResult = chars - s->mCurrentStart;
2148 s->mEndWord = s->mWordCount - 1;
2149 } else if (s->mZipDelimiter == false) {
2152 s->mProgress = ADDRESS_LINE;
2155 s->mProgress = FIND_STREET;
2158 if (WTF::isASCIIDigit(ch)) {
2159 if (++s->mNumberCount <= 4)
2162 if (isUnicodeSpace(ch)) {
2163 if (s->mNumberCount == 0)
2166 if (s->mNumberCount == 4) {
2167 if (WTF::isASCIIAlpha(ch) == false) {
2168 s->mEndResult = chars - s->mCurrentStart;
2169 s->mEndWord = s->mWordCount - 1;
2171 } else if (s->mNumberCount != 0)
2173 s->mProgress = FIND_STREET;
2177 for (int wordsIndex = s->mStateWord - 1; wordsIndex >= 0; --wordsIndex) {
2178 const UChar* test = s->mWords[wordsIndex];
2179 UChar letter = test[0];
2181 if (letter > 'X' - 'A')
2183 const char* names = longStreetNames[letter];
2187 while ((offset = *names++) != 0) {
2190 for (int idx = 0; idx < offset; idx++) {
2191 char nameLetter = names[idx];
2192 char testUpper = WTF::toASCIIUpper(test[testIndex]);
2193 if (nameLetter == '*') {
2194 if (testUpper == 'S')
2198 bool fullOnly = WTF::isASCIILower(nameLetter);
2199 nameLetter = WTF::toASCIIUpper(nameLetter);
2200 if (testUpper == nameLetter) {
2201 if (abbr && fullOnly)
2206 if (fullOnly == false)
2210 letter = &test[testIndex] < s->mEnds[wordsIndex] ?
2211 test[testIndex] : ' ';
2212 if (WTF::isASCIIAlpha(letter) == false && WTF::isASCIIDigit(letter) == false) {
2213 if (s->mNumberWords != 0) {
2215 int wordReduction = -1;
2217 while ((s->mNumberWords & (1 << shift)) == 0)
2219 if (shift > wordsIndex)
2221 wordReduction = shift;
2222 } while (s->mNumberWords >> ++shift != 0);
2223 if (wordReduction >= 0) {
2224 if (s->mContinuationNode) {
2229 s->mStartResult = s->mWords[wordReduction] - s->mStarts[wordReduction];
2232 if (wordsIndex != s->mStateWord - 1)
2233 return FOUND_COMPLETE;
2241 s->mProgress = ADDRESS_LINE;
2245 if (s->mNumberWords != 0) {
2247 while ((s->mNumberWords & (1 << shift)) == 0)
2249 s->mNumberWords >>= ++shift;
2250 if (s->mBases[0] != s->mBases[shift])
2252 s->shiftWords(shift);
2253 s->mStartResult = s->mWords[0] - s->mStarts[0];
2254 s->mWordCount -= shift;
2255 s->mProgress = ADDRESS_LINE;
2261 if (s->mContinuationNode)
2263 s->mProgress = NO_ADDRESS;
2264 s->mWordCount = s->mLineCount = 0;
2265 s->mNumberWords = 0;
2269 s->mNumberCount = s->mLetterCount = 0;
2270 s->mFirstLower = NULL;
2271 s->mUnparsed = false;
2274 return s->mProgress == NO_ADDRESS ? FOUND_NONE : FOUND_PARTIAL;
2277 // Recogize common email patterns only. Currently has lots of state, walks text forwards and backwards -- will be
2278 // a real challenge to adapt to walk text across multiple nodes, I imagine
2279 // FIXME: it's too hard for the caller to call these incrementally -- it's probably best for this to
2280 // either walk the node tree directly or make a callout to get the next or previous node, if there is one
2281 // walking directly will avoid adding logic in caller to track the multiple partial or full nodes that compose this
2283 CacheBuilder::FoundState CacheBuilder::FindPartialEMail(const UChar* chars, unsigned length,
2286 // the following tables were generated by tests/browser/focusNavigation/BrowserDebug.cpp
2287 // hand-edit at your own risk
2288 static const int domainTwoLetter[] = {
2289 0x02df797c, // a followed by: [cdefgilmnoqrstuwxz]
2290 0x036e73fb, // b followed by: [abdefghijmnorstvwyz]
2291 0x03b67ded, // c followed by: [acdfghiklmnorsuvxyz]
2292 0x02005610, // d followed by: [ejkmoz]
2293 0x001e00d4, // e followed by: [ceghrstu]
2294 0x00025700, // f followed by: [ijkmor]
2295 0x015fb9fb, // g followed by: [abdefghilmnpqrstuwy]
2296 0x001a3400, // h followed by: [kmnrtu]
2297 0x000f7818, // i followed by: [delmnoqrst]
2298 0x0000d010, // j followed by: [emop]
2299 0x0342b1d0, // k followed by: [eghimnprwyz]
2300 0x013e0507, // l followed by: [abcikrstuvy]
2301 0x03fffccd, // m followed by: [acdghklmnopqrstuvwxyz]
2302 0x0212c975, // n followed by: [acefgilopruz]
2303 0x00001000, // o followed by: [m]
2304 0x014e3cf1, // p followed by: [aefghklmnrstwy]
2305 0x00000001, // q followed by: [a]
2306 0x00504010, // r followed by: [eouw]
2307 0x032a7fdf, // s followed by: [abcdeghijklmnortvyz]
2308 0x026afeec, // t followed by: [cdfghjklmnoprtvwz]
2309 0x03041441, // u followed by: [agkmsyz]
2310 0x00102155, // v followed by: [aceginu]
2311 0x00040020, // w followed by: [fs]
2313 0x00180010, // y followed by: [etu]
2314 0x00401001, // z followed by: [amw]
2317 static char const* const longDomainNames[] = {
2318 "\x03" "ero" "\x03" "rpa", // aero, arpa
2320 "\x02" "at" "\x02" "om" "\x03" "oop", // cat, com, coop
2326 "\x03" "nfo" "\x02" "nt", // info, int
2327 "\x03" "obs", // jobs
2330 "\x02" "il" "\x03" "obi" "\x05" "useum", // mil, mobi, museum
2331 "\x03" "ame" "\x02" "et", // name, net
2332 "\x02" "rg", // , org
2337 "\x05" "ravel", // travel
2346 const UChar* start = chars;
2347 const UChar* end = chars + length;
2348 while (chars < end) {
2349 UChar ch = *chars++;
2352 const UChar* atLocation = chars - 1;
2353 // search for domain
2354 ch = *chars++ | 0x20; // convert uppercase to lower
2355 if (ch < 'a' || ch > 'z')
2357 while (chars < end) {
2359 if (IsDomainChar(ch) == false)
2363 UChar firstLetter = *chars++ | 0x20; // first letter of the domain
2365 return FOUND_NONE; // only one letter; must be at least two
2367 if (firstLetter > 'z' - 'a')
2368 continue; // non-letter followed '.'
2369 int secondLetterMask = domainTwoLetter[firstLetter];
2370 ch = *chars | 0x20; // second letter of the domain
2372 if (ch >= 'z' - 'a')
2374 bool secondMatch = (secondLetterMask & 1 << ch) != 0;
2375 const char* wordMatch = longDomainNames[firstLetter];
2377 while (wordMatch != NULL) {
2378 int len = *wordMatch++;
2381 match = wordMatch[wordIndex];
2383 goto foundDomainStart;
2384 if (chars[wordIndex] != match)
2389 if (*wordMatch == '\0')
2400 if (IsDomainChar(ch))
2402 } else if (chars + 1 < end && IsDomainChar(chars[1]))
2405 // found domain. Search backwards from '@' for beginning of email address
2406 s->mEndResult = chars - start;
2412 goto nextAt; // mailbox can't end in period
2414 if (IsMailboxChar(ch) == false) {
2422 UChar firstChar = *chars;
2423 if (firstChar == '.' || firstChar == '@') // mailbox can't start with period or be empty
2425 s->mStartResult = chars - start;
2426 return FOUND_COMPLETE;
2432 chars = atLocation + 1;
2437 #define PHONE_PATTERN "(200) /-.\\ 100 -. 0000" // poor man's regex: parens optional, any one of punct, digit smallest allowed
2439 CacheBuilder::FoundState CacheBuilder::FindPartialNumber(const UChar* chars, unsigned length,
2442 char* pattern = s->mPattern;
2443 UChar* store = s->mStorePtr;
2444 const UChar* start = chars;
2445 const UChar* end = chars + length;
2446 const UChar* lastDigit = NULL;
2448 bool initialized = s->mInitialized;
2449 while (chars < end) {
2450 if (initialized == false) {
2451 s->mBackTwo = s->mBackOne;
2452 s->mBackOne = s->mCurrent;
2454 UChar ch = s->mCurrent = *chars;
2456 char patternChar = *pattern;
2457 switch (patternChar) {
2459 if (initialized == false) {
2460 s->mStartResult = chars - start;
2465 if (ch < patternChar || ch > '9')
2472 if (WTF::isASCIIDigit(ch) == false) {
2478 if (ch == patternChar)
2482 if (ch == patternChar) {
2483 s->mStartResult = chars - start;
2485 s->mOpenParen = true;
2487 goto commonPunctuation;
2489 if ((ch == patternChar) ^ s->mOpenParen)
2493 if (ch == patternChar) {
2498 } while (++pattern); // never false
2504 if (s->mContinuationNode)
2507 pattern = s->mPattern;
2508 store = s->mStorePtr;
2509 } while (++chars < end);
2511 if (WTF::isASCIIDigit(s->mBackOne != '1' ? s->mBackOne : s->mBackTwo))
2514 s->mStorePtr = store;
2515 s->mPattern = pattern;
2516 s->mEndResult = lastDigit - start + 1;
2517 char pState = pattern[0];
2518 return pState == '\0' ? FOUND_COMPLETE : pState == '(' || (WTF::isASCIIDigit(pState) && WTF::isASCIIDigit(pattern[-1])) ?
2519 FOUND_NONE : FOUND_PARTIAL;
2522 CacheBuilder::FoundState CacheBuilder::FindPhoneNumber(const UChar* chars, unsigned length,
2523 int* start, int* end)
2527 FoundState result = FindPartialNumber(chars, length, &state);
2528 *start = state.mStartResult;
2529 *end = state.mEndResult;
2533 void CacheBuilder::FindReset(FindState* state)
2535 memset(state, 0, sizeof(FindState));
2536 state->mCurrent = ' ';
2537 FindResetNumber(state);
2540 void CacheBuilder::FindResetNumber(FindState* state)
2542 state->mOpenParen = false;
2543 state->mPattern = (char*) PHONE_PATTERN;
2544 state->mStorePtr = state->mStore;
2547 IntRect CacheBuilder::getAreaRect(const HTMLAreaElement* area)
2549 Node* node = area->document();
2550 while ((node = node->traverseNextNode()) != NULL) {
2551 RenderObject* renderer = node->renderer();
2552 if (renderer && renderer->isRenderImage()) {
2553 RenderImage* image = static_cast<RenderImage*>(renderer);
2554 HTMLMapElement* map = image->imageMap();
2557 for (n = map->firstChild(); n;
2558 n = n->traverseNextNode(map)) {
2560 if (area->isDefault())
2561 return image->absoluteBoundingBoxRect();
2562 return area->computeRect(image);
2571 void CacheBuilder::GetGlobalOffset(Node* node, int* x, int * y)
2573 GetGlobalOffset(node->document()->frame(), x, y);
2576 void CacheBuilder::GetGlobalOffset(Frame* frame, int* x, int* y)
2578 // TIMER_PROBE(__FUNCTION__);
2586 while ((parent = frame->tree()->parent()) != NULL) {
2587 const WebCore::IntRect& rect = frame->view()->platformWidget()->getBounds();
2592 // TIMER_PROBE_END();
2595 Frame* CacheBuilder::HasFrame(Node* node)
2597 RenderObject* renderer = node->renderer();
2598 if (renderer == NULL)
2600 if (renderer->isWidget() == false)
2602 Widget* widget = static_cast<RenderWidget*>(renderer)->widget();
2605 if (widget->isFrameView() == false)
2607 return static_cast<FrameView*>(widget)->frame();
2610 bool CacheBuilder::HasOverOrOut(Node* node)
2612 // eventNames are thread-local data, I avoid using 'static' variable here.
2613 AtomicString eventTypes[2] = {
2614 eventNames().mouseoverEvent,
2615 eventNames().mouseoutEvent
2618 return NodeHasEventListeners(node, eventTypes, 2);
2621 bool CacheBuilder::HasTriggerEvent(Node* node)
2623 AtomicString eventTypes[5] = {
2624 eventNames().clickEvent,
2625 eventNames().mousedownEvent,
2626 eventNames().mouseupEvent,
2627 eventNames().keydownEvent,
2628 eventNames().keyupEvent
2631 return NodeHasEventListeners(node, eventTypes, 5);
2634 // #define EMAIL_PATTERN "x@y.d" // where 'x' is letters, numbers, and '-', '.', '_' ; 'y' is 'x' without the underscore, and 'd' is a valid domain
2635 // - 0x2D . 0x2E 0-9 0x30-39 A-Z 0x41-5A _ 0x5F a-z 0x61-7A
2637 bool CacheBuilder::IsDomainChar(UChar ch)
2639 static const unsigned body[] = {0x03ff6000, 0x07fffffe, 0x07fffffe}; // 0-9 . - A-Z a-z
2641 if (ch > 'z' - 0x20)
2643 return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0;
2646 bool CacheBuilder::isFocusableText(NodeWalk* walk, bool more, Node* node,
2647 CachedNodeType* type, String* exported) const
2649 Text* textNode = static_cast<Text*>(node);
2650 StringImpl* string = textNode->dataImpl();
2651 const UChar* baseChars = string->characters();
2652 // const UChar* originalBase = baseChars;
2653 int length = string->length();
2655 while (index < length && isUnicodeSpace(baseChars[index]))
2657 if (index >= length)
2659 if (more == false) {
2662 walk->mFinalNode = node;
2663 walk->mLastInline = NULL;
2665 // starting with this node, search forward for email, phone number, and address
2666 // if any of the three is found, track it so that the remaining can be looked for later
2667 FoundState state = FOUND_NONE;
2668 RenderText* renderer = (RenderText*) node->renderer();
2669 bool foundBetter = false;
2670 InlineTextBox* baseInline = walk->mLastInline != NULL ? walk->mLastInline :
2671 renderer->firstTextBox();
2672 if (baseInline == NULL)
2674 int start = walk->mEnd;
2675 InlineTextBox* saveInline;
2676 int baseStart, firstStart = start;
2677 saveInline = baseInline;
2679 for (CachedNodeType checkType = ADDRESS_CACHEDNODETYPE;
2680 checkType <= PHONE_CACHEDNODETYPE;
2681 checkType = static_cast<CachedNodeType>(checkType + 1))
2683 if ((1 << (checkType - 1) & mAllowableTypes) == 0)
2685 InlineTextBox* inlineTextBox = baseInline;
2686 FindState findState;
2687 FindReset(&findState);
2689 if (checkType == ADDRESS_CACHEDNODETYPE) {
2690 findState.mBases[0] = baseChars;
2691 findState.mWords[0] = baseChars + start;
2692 findState.mStarts[0] = baseChars + start;
2694 Node* lastPartialNode = NULL;
2695 int lastPartialEnd = -1;
2696 bool lastPartialMore = false;
2697 bool firstPartial = true;
2698 InlineTextBox* lastPartialInline = NULL;
2701 const UChar* chars = baseChars + start;
2702 length = inlineTextBox == NULL ? 0 :
2703 inlineTextBox->end() - start + 1;
2704 bool wasInitialized = findState.mInitialized;
2705 switch (checkType) {
2706 case ADDRESS_CACHEDNODETYPE:
2707 state = FindPartialAddress(baseChars, chars, length, &findState);
2709 case EMAIL_CACHEDNODETYPE:
2710 state = FindPartialEMail(chars, length, &findState);
2712 case PHONE_CACHEDNODETYPE:
2713 state = FindPartialNumber(chars, length, &findState);
2718 findState.mInitialized = state != FOUND_NONE;
2719 if (wasInitialized != findState.mInitialized)
2721 if (state == FOUND_PARTIAL) {
2722 lastPartialNode = node;
2723 lastPartialEnd = findState.mEndResult + start;
2724 lastPartialMore = firstPartial &&
2725 lastPartialEnd < (int) string->length();
2726 firstPartial = false;
2727 lastPartialInline = inlineTextBox;
2728 findState.mContinuationNode = true;
2729 } else if (state == FOUND_COMPLETE) {
2730 if (foundBetter == false || walk->mStart > findState.mStartResult) {
2731 walk->mStart = findState.mStartResult + firstStart;
2732 if (findState.mEndResult > 0) {
2733 walk->mFinalNode = node;
2734 walk->mEnd = findState.mEndResult + start;
2735 walk->mMore = node == textNode &&
2736 walk->mEnd < (int) string->length();
2737 walk->mLastInline = inlineTextBox;
2739 walk->mFinalNode = lastPartialNode;
2740 walk->mEnd = lastPartialEnd;
2741 walk->mMore = lastPartialMore;
2742 walk->mLastInline = lastPartialInline;
2745 if (checkType == PHONE_CACHEDNODETYPE) {
2746 const UChar* store = findState.mStore;
2747 *exported = String(store);
2749 Node* temp = textNode;
2751 start = walk->mStart;
2752 exported->truncate(0);
2754 Text* tempText = static_cast<Text*>(temp);
2755 StringImpl* string = tempText->dataImpl();
2756 int end = tempText == walk->mFinalNode ?
2757 walk->mEnd : string->length();
2758 exported->append(String(string->substring(
2759 start, end - start)));
2760 ASSERT(end > start);
2761 length += end - start + 1;
2762 if (temp == walk->mFinalNode)
2766 temp = temp->traverseNextNode();
2768 } while (temp->isTextNode() == false);
2769 // add a space in between text nodes to avoid
2770 // words collapsing together
2771 exported->append(" ");
2776 goto tryNextCheckType;
2777 } else if (findState.mContinuationNode)
2779 if (inlineTextBox == NULL)
2781 inlineTextBox = inlineTextBox->nextTextBox();
2782 if (inlineTextBox == NULL)
2784 start = inlineTextBox->start();
2785 if (state == FOUND_PARTIAL && node == textNode)
2786 findState.mContinuationNode = false;
2788 if (state == FOUND_NONE)
2790 // search for next text node, if any
2796 node = node->traverseNextNode();
2797 if (node == NULL || node->hasTagName(HTMLNames::aTag)
2798 || node->hasTagName(HTMLNames::inputTag)
2799 || node->hasTagName(HTMLNames::textareaTag)) {
2800 if (state == FOUND_PARTIAL &&
2801 checkType == ADDRESS_CACHEDNODETYPE &&
2802 findState.mProgress == ZIP_CODE &&
2803 findState.mNumberCount == 0) {
2805 inlineTextBox = NULL;
2807 findState.mProgress = FIND_STREET;
2810 goto tryNextCheckType;
2812 } while (node->isTextNode() == false);
2813 nextNode = static_cast<Text*>(node);
2814 renderer = (RenderText*) nextNode->renderer();
2815 } while (renderer == NULL);
2816 baseInline = renderer->firstTextBox();
2817 } while (baseInline == NULL);
2818 string = nextNode->dataImpl();
2819 baseChars = string->characters();
2820 inlineTextBox = baseInline;
2821 start = inlineTextBox->start();
2823 findState.mEndResult = 0;
2827 baseInline = saveInline;
2828 string = textNode->dataImpl();
2829 baseChars = string->characters();
2832 CachedNodeType temp = *type;
2834 case ADDRESS_CACHEDNODETYPE: {
2835 static const char geoString[] = "geo:0,0?q=";
2836 exported->insert(String(geoString), 0);
2837 int index = sizeof(geoString) - 1;
2838 String escapedComma("%2C");
2839 while ((index = exported->find(',', index)) >= 0)
2840 exported->replace(index, 1, escapedComma);
2842 case EMAIL_CACHEDNODETYPE: {
2843 String encoded = WebCore::encodeWithURLEscapeSequences(*exported);
2844 exported->swap(encoded);
2845 exported->insert(WTF::String("mailto:"), 0);
2847 case PHONE_CACHEDNODETYPE:
2848 exported->insert(WTF::String("tel:"), 0);
2860 bool CacheBuilder::IsMailboxChar(UChar ch)
2862 // According to http://en.wikipedia.org/wiki/Email_address
2863 // ! # $ % & ' * + - . / 0-9 = ?
2866 static const unsigned body[] = {0xa3ffecfa, 0xc7fffffe, 0x7fffffff};
2868 if (ch > '~' - 0x20)
2870 return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0;
2873 bool CacheBuilder::setData(CachedFrame* cachedFrame)
2875 Frame* frame = FrameAnd(this);
2876 Document* doc = frame->document();
2879 RenderObject* renderer = doc->renderer();
2880 if (renderer == NULL)
2882 RenderLayer* layer = renderer->enclosingLayer();
2885 if (layer->width() == 0 || layer->height() == 0)
2890 GetGlobalOffset(frame, &x, &y);
2891 WebCore::IntRect viewBounds = frame->view()->platformWidget()->getBounds();
2893 viewBounds.setLocation(WebCore::IntPoint(x, y));
2894 cachedFrame->setLocalViewBounds(viewBounds);
2895 cachedFrame->setContentsSize(layer->scrollWidth(), layer->scrollHeight());
2896 if (cachedFrame->childCount() == 0)
2898 CachedFrame* lastCachedFrame = cachedFrame->lastChild();
2899 cachedFrame = cachedFrame->firstChild();
2901 CacheBuilder* cacheBuilder = Builder((Frame* )cachedFrame->framePointer());
2902 cacheBuilder->setData(cachedFrame);
2903 } while (cachedFrame++ != lastCachedFrame);
2907 #if USE(ACCELERATED_COMPOSITING)
2908 void CacheBuilder::TrackLayer(WTF::Vector<LayerTracker>& layerTracker,
2909 RenderObject* nodeRenderer, Node* lastChild, int offsetX, int offsetY)
2911 RenderLayer* layer = nodeRenderer->enclosingLayer();
2912 RenderLayerBacking* back = layer->backing();
2915 GraphicsLayer* grLayer = back->graphicsLayer();
2916 if (back->hasContentsLayer())
2917 grLayer = back->foregroundLayer();
2920 LayerAndroid* aLayer = grLayer->platformLayer();
2923 IntPoint scroll(layer->scrollXOffset(), layer->scrollYOffset());
2924 #if ENABLE(ANDROID_OVERFLOW_SCROLL)
2925 // If this is an overflow element, track the content layer.
2926 if (layer->hasOverflowScroll() && aLayer->getChild(0))
2927 aLayer = aLayer->getChild(0)->getChild(0);
2930 // Prevent a crash when scrolling a layer that does not have a parent.
2931 if (layer->stackingContext())
2932 layer->scrollToOffset(0, 0);
2934 layerTracker.grow(layerTracker.size() + 1);
2935 LayerTracker& indexTracker = layerTracker.last();
2936 indexTracker.mLayer = aLayer;
2937 indexTracker.mRenderLayer = layer;
2938 indexTracker.mBounds = enclosingIntRect(aLayer->bounds());
2939 // Use the absolute location of the layer as the bounds location. This
2940 // provides the original offset of nodes in the layer so that we can
2941 // translate nodes between their original location and the layer's new
2943 indexTracker.mBounds.setLocation(layer->absoluteBoundingBox().location());
2944 indexTracker.mBounds.move(offsetX, offsetY);
2945 indexTracker.mScroll = scroll;
2946 indexTracker.mLastChild = OneAfter(lastChild);
2947 DBG_NAV_LOGD("layer=%p [%d] bounds=(%d,%d,w=%d,h=%d)", aLayer,
2948 aLayer->uniqueId(), indexTracker.mBounds.x(), indexTracker.mBounds.y(),
2949 indexTracker.mBounds.width(), indexTracker.mBounds.height());
2953 bool CacheBuilder::validNode(Frame* startFrame, void* matchFrame,
2956 if (matchFrame == startFrame) {
2957 if (matchNode == NULL)
2959 Node* node = startFrame->document();
2960 while (node != NULL) {
2961 if (node == matchNode) {
2962 const IntRect& rect = node->hasTagName(HTMLNames::areaTag) ?
2963 getAreaRect(static_cast<HTMLAreaElement*>(node)) : node->getRect();
2964 // Consider nodes with empty rects that are not at the origin
2965 // to be valid, since news.google.com has valid nodes like this
2966 if (rect.x() == 0 && rect.y() == 0 && rect.isEmpty())
2970 node = node->traverseNextNode();
2972 DBG_NAV_LOGD("frame=%p valid node=%p invalid\n", matchFrame, matchNode);
2975 Frame* child = startFrame->tree()->firstChild();
2977 bool result = validNode(child, matchFrame, matchNode);
2980 child = child->tree()->nextSibling();
2983 if (startFrame->tree()->parent() == NULL)
2984 DBG_NAV_LOGD("frame=%p node=%p false\n", matchFrame, matchNode);
2989 static int Area(const IntRect& rect)
2991 return rect.width() * rect.height();
2994 bool CacheBuilder::AddPartRect(IntRect& bounds, int x, int y,
2995 WTF::Vector<IntRect>* result, IntRect* focusBounds)
2997 if (bounds.isEmpty())
3000 if (bounds.maxX() <= 0 || bounds.maxY() <= 0)
3002 IntRect* work = result->begin() - 1;
3003 IntRect* end = result->end();
3004 while (++work < end) {
3005 if (work->contains(bounds))
3007 if (bounds.contains(*work)) {
3009 focusBounds->unite(bounds);
3012 if ((bounds.x() != work->x() || bounds.width() != work->width()) &&
3013 (bounds.y() != work->y() || bounds.height() != work->height()))
3015 IntRect test = *work;
3017 if (Area(test) > Area(*work) + Area(bounds))
3020 focusBounds->unite(bounds);
3023 if (result->size() >= MAXIMUM_FOCUS_RING_COUNT)
3025 result->append(bounds);
3026 if (focusBounds->isEmpty())
3027 *focusBounds = bounds;
3029 focusBounds->unite(bounds);
3033 bool CacheBuilder::ConstructPartRects(Node* node, const IntRect& bounds,
3034 IntRect* focusBounds, int x, int y, WTF::Vector<IntRect>* result,
3037 WTF::Vector<ClipColumnTracker> clipTracker(1);
3038 ClipColumnTracker* baseTracker = clipTracker.data(); // sentinel
3039 bzero(baseTracker, sizeof(ClipColumnTracker));
3040 if (node->hasChildNodes() && node->hasTagName(HTMLNames::buttonTag) == false
3041 && node->hasTagName(HTMLNames::selectTag) == false) {
3042 // collect all text rects from first to last child
3043 Node* test = node->firstChild();
3046 while ((prior = prior->lastChild()) != NULL)
3048 ASSERT(last != NULL);
3049 bool nodeIsAnchor = node->hasTagName(HTMLNames::aTag);
3052 const ClipColumnTracker* lastClip = &clipTracker.last();
3053 if (test != lastClip->mLastChild)
3055 clipTracker.removeLast();
3057 RenderObject* renderer = test->renderer();
3058 if (renderer == NULL)
3060 EVisibility vis = renderer->style()->visibility();
3063 bool hasClip = renderer->hasOverflowClip();
3064 size_t clipIndex = clipTracker.size();
3065 IntRect clipBounds = IntRect(0, 0, INT_MAX, INT_MAX);
3066 if (hasClip || --clipIndex > 0) {
3067 clipBounds = hasClip ? renderer->absoluteBoundingBoxRect() :
3068 clipTracker.at(clipIndex).mBounds; // x, y fixup done by ConstructTextRect
3070 if (test->isTextNode()) {
3071 RenderText* renderText = (RenderText*) renderer;
3072 InlineTextBox *textBox = renderText->firstTextBox();
3073 if (textBox == NULL)
3075 if (ConstructTextRect((Text*) test, textBox, 0, INT_MAX,
3076 x, y, focusBounds, clipBounds, result) == false) {
3081 if (test->hasTagName(HTMLNames::imgTag)) {
3082 IntRect bounds = test->getRect();
3083 bounds.intersect(clipBounds);
3084 if (AddPartRect(bounds, x, y, result, focusBounds) == false)
3086 *imageCountPtr += 1;
3089 if (hasClip == false) {
3090 if (nodeIsAnchor && test->hasTagName(HTMLNames::divTag)) {
3091 IntRect bounds = renderer->absoluteBoundingBoxRect(); // x, y fixup done by AddPartRect
3092 RenderBox* renderBox = static_cast<RenderBox*>(renderer);
3093 int left = bounds.x() + renderBox->paddingLeft() + renderBox->borderLeft();
3094 int top = bounds.y() + renderBox->paddingTop() + renderBox->borderTop();
3095 int right = bounds.maxX() - renderBox->paddingRight() - renderBox->borderRight();
3096 int bottom = bounds.maxY() - renderBox->paddingBottom() - renderBox->borderBottom();
3097 if (left >= right || top >= bottom)
3099 bounds = IntRect(left, top, right - left, bottom - top);
3100 if (AddPartRect(bounds, x, y, result, focusBounds) == false)
3105 Node* lastChild = test->lastChild();
3106 if (lastChild == NULL)
3108 clipTracker.grow(clipTracker.size() + 1);
3109 ClipColumnTracker& clip = clipTracker.last();
3110 clip.mBounds = renderer->absoluteBoundingBoxRect(); // x, y fixup done by ConstructTextRect
3111 clip.mLastChild = OneAfter(lastChild);
3113 } while (test != last && (test = test->traverseNextNode()) != NULL);
3115 if (result->size() == 0 || focusBounds->width() < MINIMUM_FOCUSABLE_WIDTH
3116 || focusBounds->height() < MINIMUM_FOCUSABLE_HEIGHT) {
3117 if (bounds.width() < MINIMUM_FOCUSABLE_WIDTH)
3119 if (bounds.height() < MINIMUM_FOCUSABLE_HEIGHT)
3121 result->append(bounds);
3122 *focusBounds = bounds;
3127 static inline bool isNotSpace(UChar c)
3129 return c <= 0xA0 ? isUnicodeSpace(c) == false :
3130 WTF::Unicode::direction(c) != WTF::Unicode::WhiteSpaceNeutral;
3133 bool CacheBuilder::ConstructTextRect(Text* textNode,
3134 InlineTextBox* textBox, int start, int relEnd, int x, int y,
3135 IntRect* focusBounds, const IntRect& clipBounds, WTF::Vector<IntRect>* result)
3137 RenderText* renderText = (RenderText*) textNode->renderer();
3138 EVisibility vis = renderText->style()->visibility();
3139 StringImpl* string = textNode->dataImpl();
3140 const UChar* chars = string->characters();
3141 FloatPoint pt = renderText->localToAbsolute();
3143 int textBoxStart = textBox->start();
3144 int textBoxEnd = textBoxStart + textBox->len();
3145 if (textBoxEnd <= start)
3147 if (textBoxEnd > relEnd)
3148 textBoxEnd = relEnd;
3149 IntRect bounds = textBox->selectionRect((int) pt.x(), (int) pt.y(),
3151 bounds.intersect(clipBounds);
3152 if (bounds.isEmpty())
3154 bool drawable = false;
3155 for (int index = start; index < textBoxEnd; index++)
3156 if ((drawable |= isNotSpace(chars[index])) != false)
3158 if (drawable && vis != HIDDEN) {
3159 if (AddPartRect(bounds, x, y, result, focusBounds) == false)
3162 if (textBoxEnd == relEnd)
3164 } while ((textBox = textBox->nextTextBox()) != NULL);
3168 bool CacheBuilder::ConstructTextRects(Text* node, int start,
3169 Text* last, int end, int x, int y, IntRect* focusBounds,
3170 const IntRect& clipBounds, WTF::Vector<IntRect>* result)
3173 *focusBounds = IntRect(0, 0, 0, 0);
3175 RenderText* renderText = (RenderText*) node->renderer();
3176 int relEnd = node == last ? end : renderText->textLength();
3177 InlineTextBox *textBox = renderText->firstTextBox();
3178 if (textBox != NULL) {
3180 if ((int) textBox->end() >= start)
3182 } while ((textBox = textBox->nextTextBox()) != NULL);
3183 if (textBox && ConstructTextRect(node, textBox, start, relEnd,
3184 x, y, focusBounds, clipBounds, result) == false)
3191 node = (Text*) node->traverseNextNode();
3192 ASSERT(node != NULL);
3193 } while (node->isTextNode() == false || node->renderer() == NULL);