Google Git
Sign in
android / platform / external / webkit / f10585d69aaccf4c1b021df143ee0f08e338cf31 / . / WebKit / android / nav / CacheBuilder.cpp
blob: 037a6e52aaac328da6f4a26b35e5b3dc38cd7dbc [file] [log] [blame]
/*
* Copyright 2006, The Android Open Source Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "CachedPrefix.h"
#include "CachedNode.h"
#include "CachedRoot.h"
#include "Document.h"
#include "EventListener.h"
#include "EventNames.h"
#include "Frame.h"
#include "FrameLoader.h"
#include "FrameLoaderClientAndroid.h"
#include "FrameTree.h"
#include "FrameView.h"
//#include "GraphicsContext.h"
#include "HTMLAreaElement.h"
#include "HTMLImageElement.h"
#include "HTMLInputElement.h"
#include "HTMLMapElement.h"
#include "HTMLNames.h"
#include "HTMLOptionElement.h"
#include "HTMLSelectElement.h"
#include "InlineTextBox.h"
#include "KURL.h"
#include "PluginView.h"
#include "RegisteredEventListener.h"
#include "RenderImage.h"
#include "RenderInline.h"
#include "RenderListBox.h"
#include "RenderSkinCombo.h"
#include "RenderTextControl.h"
#include "RenderWidget.h"
#include "SkCanvas.h"
#include "SkPoint.h"
#include "Text.h"
#include "WebCoreFrameBridge.h"
#include "WebCoreViewBridge.h"
#include "Widget.h"
#include <wtf/unicode/Unicode.h>
#ifdef DUMP_NAV_CACHE_USING_PRINTF
FILE* gNavCacheLogFile = NULL;
android::Mutex gWriteLogMutex;
#endif
#include "CacheBuilder.h"
#define MINIMUM_FOCUSABLE_WIDTH 3
#define MINIMUM_FOCUSABLE_HEIGHT 3
#define MAXIMUM_FOCUS_RING_COUNT 32
namespace android {
CacheBuilder* CacheBuilder::Builder(Frame* frame) {
return &((FrameLoaderClientAndroid*) frame->loader()->client())->getCacheBuilder();
}
Frame* CacheBuilder::FrameAnd(CacheBuilder* cacheBuilder) {
FrameLoaderClientAndroid* loader = (FrameLoaderClientAndroid*)
((char*) cacheBuilder - OFFSETOF(FrameLoaderClientAndroid, m_cacheBuilder));
return loader->getFrame();
}
Frame* CacheBuilder::FrameAnd(const CacheBuilder* cacheBuilder) {
FrameLoaderClientAndroid* loader = (FrameLoaderClientAndroid*)
((char*) cacheBuilder - OFFSETOF(FrameLoaderClientAndroid, m_cacheBuilder));
return loader->getFrame();
}
#if DUMP_NAV_CACHE
static bool hasEventListener(Node* node, const AtomicString& eventType) {
const RegisteredEventListenerVector& listeners = node->eventListeners();
size_t size = listeners.size();
for (size_t i = 0; i < size; ++i) {
const RegisteredEventListener& r = *listeners[i];
if (r.eventType() == eventType)
return true;
}
return false;
}
#define DEBUG_BUFFER_SIZE 256
#define DEBUG_WRAP_SIZE 150
#define DEBUG_WRAP_MAX 170
Frame* CacheBuilder::Debug::frameAnd() const {
CacheBuilder* nav = (CacheBuilder*) ((char*) this - OFFSETOF(CacheBuilder, mDebug));
return CacheBuilder::FrameAnd(nav);
}
void CacheBuilder::Debug::attr(const AtomicString& name, const AtomicString& value) {
if (name.isNull() || name.isEmpty() || value.isNull() || value.isEmpty())
return;
uChar(name.characters(), name.length(), false);
print("=");
wideString(value.characters(), value.length(), false);
print(" ");
}
void CacheBuilder::Debug::comma(const char* str) {
print(str);
print(", ");
}
void CacheBuilder::Debug::flush() {
int len;
do {
int limit = mIndex;
if (limit < DEBUG_WRAP_SIZE)
return;
if (limit < DEBUG_WRAP_MAX)
len = limit;
else {
limit = DEBUG_WRAP_MAX;
len = DEBUG_WRAP_SIZE;
while (len < limit) {
char test = mBuffer[len];
if (test < '/' || (test > '9' && test < 'A') || (test > 'Z' && test < 'a') || test > 'z')
break;
len++;
}
while (mBuffer[len] == '\\' || mBuffer[len] == '"')
len++;
}
const char* prefix = mPrefix;
if (prefix[0] == '\"') {
// see if we're inside a quote
int quoteCount = 0;
for (int index = 0; index < len; index++) {
if (mBuffer[index] == '\\') {
index++;
continue;
}
if (mBuffer[index] == '\n') {
quoteCount = 0;
continue;
}
if (mBuffer[index] == '"')
quoteCount++;
}
if ((quoteCount & 1) == 0)
prefix = "\n";
}
DUMP_NAV_LOGD("%.*s", len, mBuffer);
int copy = mIndex - len;
strcpy(mBuffer, prefix);
memcpy(&mBuffer[strlen(prefix)], &mBuffer[len], copy);
mIndex = strlen(prefix) + copy;
} while (true);
}
void CacheBuilder::Debug::frameName(char*& namePtr, const char* max) const {
if (namePtr >= max)
return;
Frame* frame = frameAnd();
Frame* parent = frame->tree()->parent();
if (parent)
Builder(parent)->mDebug.frameName(namePtr, max);
const AtomicString& name = frame->tree()->name();
if (name.length() == 0)
return;
unsigned index = 0;
if (name.startsWith(AtomicString("opener")))
index = 6;
for (; index < name.length(); index++) {
char ch = name[index];
if (ch <= ' ')
ch = '_';
if (WTF::isASCIIAlphanumeric(ch) || ch == '_')
*namePtr++ = ch;
}
}
void CacheBuilder::Debug::frames() {
Frame* frame = frameAnd();
Document* doc = frame->document();
if (doc == NULL)
return;
bool top = frame->tree()->parent() == NULL;
if (top) {
#ifdef DUMP_NAV_CACHE_USING_PRINTF
gWriteLogMutex.lock();
ASSERT(gNavCacheLogFile == NULL);
gNavCacheLogFile = fopen(NAV_CACHE_LOG_FILE, "a");
#endif
groups();
}
Frame* child = frame->tree()->firstChild();
bool hasChild = child != NULL;
if (top && hasChild)
DUMP_NAV_LOGD("\nnamespace TEST_SPACE {\n\n");
while (child) {
Builder(child)->mDebug.frames();
child = child->tree()->nextSibling();
}
if (hasChild) {
child = frame->tree()->firstChild();
while (child) {
char childName[256];
char* childNamePtr = childName;
Builder(child)->mDebug.frameName(childNamePtr, childNamePtr + sizeof(childName) - 1);
*childNamePtr = '\0';
if (child == frame->tree()->firstChild())
DUMP_NAV_LOGD("DebugTestFrameGroup TEST%s_GROUP[] = {\n", childName);
Frame* next = child->tree()->nextSibling();
Document* doc = child->document();
if (doc != NULL) {
RenderObject* renderer = doc->renderer();
if (renderer != NULL) {
RenderLayer* layer = renderer->enclosingLayer();
if (layer != NULL) {
DUMP_NAV_LOGD("{ ");
DUMP_NAV_LOGD("TEST%s_RECTS, ", childName);
DUMP_NAV_LOGD("TEST%s_RECT_COUNT, ", childName);
DUMP_NAV_LOGD("TEST%s_RECTPARTS, ", childName);
DUMP_NAV_LOGD("TEST%s_BOUNDS,\n", childName);
DUMP_NAV_LOGD("TEST%s_WIDTH, ", childName);
DUMP_NAV_LOGD("TEST%s_HEIGHT,\n", childName);
DUMP_NAV_LOGD("0, 0, 0, 0,\n");
DUMP_NAV_LOGD("TEST%s_FOCUS, ", childName);
Frame* grandChild = child->tree()->firstChild();
if (grandChild) {
char grandChildName[256];
char* grandChildNamePtr = grandChildName;
Builder(grandChild)->mDebug.frameName(grandChildNamePtr,
grandChildNamePtr + sizeof(grandChildName) - 1);
*grandChildNamePtr = '\0';
DUMP_NAV_LOGD("TEST%s_GROUP, ", grandChildName);
DUMP_NAV_LOGD("sizeof(TEST%s_GROUP) / sizeof(DebugTestFrameGroup), ", grandChildName);
} else
DUMP_NAV_LOGD("NULL, 0, ");
DUMP_NAV_LOGD("\"%s\"\n", childName);
DUMP_NAV_LOGD("}%c\n", next ? ',' : ' ');
}
}
}
child = next;
}
DUMP_NAV_LOGD("};\n");
}
if (top) {
if (hasChild)
DUMP_NAV_LOGD("\n} // end of namespace\n\n");
char name[256];
char* frameNamePtr = name;
frameName(frameNamePtr, frameNamePtr + sizeof(name) - 1);
*frameNamePtr = '\0';
DUMP_NAV_LOGD("DebugTestFrameGroup TEST%s_GROUP = {\n", name);
DUMP_NAV_LOGD("TEST%s_RECTS, ", name);
DUMP_NAV_LOGD("TEST%s_RECT_COUNT, ", name);
DUMP_NAV_LOGD("TEST%s_RECTPARTS, ", name);
DUMP_NAV_LOGD("TEST%s_BOUNDS,\n", name);
DUMP_NAV_LOGD("TEST%s_WIDTH, ", name);
DUMP_NAV_LOGD("TEST%s_HEIGHT,\n", name);
DUMP_NAV_LOGD("TEST%s_MAX_H, ", name);
DUMP_NAV_LOGD("TEST%s_MIN_H, ", name);
DUMP_NAV_LOGD("TEST%s_MAX_V, ", name);
DUMP_NAV_LOGD("TEST%s_MIN_V,\n", name);
DUMP_NAV_LOGD("TEST%s_FOCUS, ", name);
if (hasChild) {
child = frame->tree()->firstChild();
char childName[256];
char* childNamePtr = childName;
Builder(child)->mDebug.frameName(childNamePtr, childNamePtr + sizeof(childName) - 1);
*childNamePtr = '\0';
DUMP_NAV_LOGD("TEST_SPACE::TEST%s_GROUP, ", childName);
DUMP_NAV_LOGD("sizeof(TEST_SPACE::TEST%s_GROUP) / sizeof(DebugTestFrameGroup), \n" ,childName);
} else
DUMP_NAV_LOGD("NULL, 0, ");
DUMP_NAV_LOGD("\"%s\"\n", name);
DUMP_NAV_LOGD("};\n");
#ifdef DUMP_NAV_CACHE_USING_PRINTF
if (gNavCacheLogFile)
fclose(gNavCacheLogFile);
gNavCacheLogFile = NULL;
gWriteLogMutex.unlock();
#endif
}
}
void CacheBuilder::Debug::init(char* buffer, size_t size) {
mBuffer = buffer;
mBufferSize = size;
mIndex = 0;
mPrefix = "";
}
void CacheBuilder::Debug::groups() {
Frame* frame = frameAnd();
Frame* child = frame->tree()->firstChild();
bool hasChild = child != NULL;
if (frame->tree()->parent() == NULL && hasChild)
DUMP_NAV_LOGD("namespace TEST_SPACE {\n\n");
while (child) {
Builder(child)->mDebug.groups();
child = child->tree()->nextSibling();
}
if (frame->tree()->parent() == NULL && hasChild)
DUMP_NAV_LOGD("\n} // end of namespace\n\n");
Document* doc = frame->document();
char name[256];
char* frameNamePtr = name;
frameName(frameNamePtr, frameNamePtr + sizeof(name) - 1);
*frameNamePtr = '\0';
if (doc == NULL) {
DUMP_NAV_LOGD("// %s has no document\n", name);
return;
}
RenderObject* renderer = doc->renderer();
if (renderer == NULL) {
DUMP_NAV_LOGD("// %s has no renderer\n", name);
return;
}
RenderLayer* layer = renderer->enclosingLayer();
if (layer == NULL) {
DUMP_NAV_LOGD("// %s has no enclosingLayer\n", name);
return;
}
Node* node = doc;
Node* focus = doc->focusedNode();
bool atLeastOne = false;
do {
if ((atLeastOne |= isFocusable(node)) != false)
break;
} while ((node = node->traverseNextNode()) != NULL);
int focusIndex = -1;
if (atLeastOne == false) {
DUMP_NAV_LOGD("#define TEST%s_RECTS NULL\n", name);
DUMP_NAV_LOGD("static int TEST%s_RECT_COUNT = 0; // no focusable nodes\n", name);
DUMP_NAV_LOGD("#define TEST%s_RECTPARTS NULL\n", name);
} else {
node = doc;
int count = 1;
DUMP_NAV_LOGD("static DebugTestNode TEST%s_RECTS[] = {\n", name);
do {
String properties;
if (hasEventListener(node, eventNames().clickEvent))
properties.append("ONCLICK | ");
if (hasEventListener(node, eventNames().mousedownEvent))
properties.append("MOUSEDOWN | ");
if (hasEventListener(node, eventNames().mouseupEvent))
properties.append("MOUSEUP | ");
if (hasEventListener(node, eventNames().mouseoverEvent))
properties.append("MOUSEOVER | ");
if (hasEventListener(node, eventNames().mouseoutEvent))
properties.append("MOUSEOUT | ");
if (hasEventListener(node, eventNames().keydownEvent))
properties.append("KEYDOWN | ");
if (hasEventListener(node, eventNames().keyupEvent))
properties.append("KEYUP | ");
if (CacheBuilder::HasFrame(node))
properties.append("FRAME | ");
if (focus == node) {
properties.append("FOCUS | ");
focusIndex = count;
}
if (node->isKeyboardFocusable(NULL))
properties.append("KEYBOARD_FOCUSABLE | ");
if (node->isMouseFocusable())
properties.append("MOUSE_FOCUSABLE | ");
if (node->isFocusable())
properties.append("SIMPLE_FOCUSABLE | ");
if (properties.isEmpty())
properties.append("0");
else
properties.truncate(properties.length() - 3);
IntRect rect = node->getRect();
if (node->hasTagName(HTMLNames::areaTag))
rect = getAreaRect(static_cast<HTMLAreaElement*>(node));
char buffer[DEBUG_BUFFER_SIZE];
memset(buffer, 0, sizeof(buffer));
mBuffer = buffer;
mBufferSize = sizeof(buffer);
mPrefix = "\"\n\"";
mIndex = snprintf(buffer, sizeof(buffer), "{{%d, %d, %d, %d}, ", rect.x(), rect.y(),
rect.width(), rect.height());
localName(node);
uChar(properties.characters(), properties.length(), false);
print(", ");
int parentIndex = ParentIndex(node, count, node->parentNode());
char scratch[256];
snprintf(scratch, sizeof(scratch), "%d", parentIndex);
comma(scratch);
Element* element = static_cast<Element*>(node);
if (node->isElementNode() && element->hasID())
wideString(element->getIDAttribute());
else if (node->isTextNode()) {
#if 01 // set to one to abbreviate text that can be omitted from the address detection code
if (rect.isEmpty() && node->textContent().length() > 100) {
wideString(node->textContent().characters(), 100, false);
snprintf(scratch, sizeof(scratch), "/* + %d bytes */",
node->textContent().length() - 100);
print(scratch);
} else
#endif
wideString(node->textContent().characters(), node->textContent().length(), true);
} else if (node->hasTagName(HTMLNames::aTag) ||
node->hasTagName(HTMLNames::areaTag))
{
HTMLAnchorElement* anchor = static_cast<HTMLAnchorElement*>(node);
wideString(anchor->href());
} else if (node->hasTagName(HTMLNames::imgTag)) {
HTMLImageElement* image = static_cast<HTMLImageElement*>(node);
wideString(image->src());
} else
print("\"\"");
RenderObject* renderer = node->renderer();
int tabindex = node->isElementNode() ? node->tabIndex() : 0;
if (renderer) {
const IntRect& absB = renderer->absoluteBoundingBoxRect();
snprintf(scratch, sizeof(scratch), ", {%d, %d, %d, %d}, %s"
", %d},",absB.x(), absB.y(), absB.width(), absB.height(),
renderer->hasOverflowClip() ? "true" : "false", tabindex);
print(scratch);
} else
print(", {0, 0, 0, 0}, false, 0},");
flush();
snprintf(scratch, sizeof(scratch), "// %d: ", count);
mPrefix = "\n// ";
print(scratch);
//print(renderer ? renderer->information().ascii() : "NO_RENDER_INFO");
if (node->isElementNode()) {
Element* element = static_cast<Element*>(node);
NamedNodeMap* attrs = element->attributes();
unsigned length = attrs->length();
if (length > 0) {
newLine();
print("// attr: ");
for (unsigned i = 0; i < length; i++) {
Attribute* a = attrs->attributeItem(i);
attr(a->localName(), a->value());
}
}
}
count++;
newLine();
} while ((node = node->traverseNextNode()) != NULL);
DUMP_NAV_LOGD("}; // focusables = %d\n", count - 1);
DUMP_NAV_LOGD("\n");
DUMP_NAV_LOGD("static int TEST%s_RECT_COUNT = %d;\n\n", name, count - 1);
// look for rects with multiple parts
node = doc;
count = 1;
bool hasRectParts = false;
int globalOffsetX, globalOffsetY;
GetGlobalOffset(frame, &globalOffsetX, &globalOffsetY);
do {
IntRect rect;
bool _isFocusable = isFocusable(node) || (node->isTextNode()
&& node->getRect().isEmpty() == false
);
int nodeIndex = count++;
if (_isFocusable == false)
continue;
RenderObject* renderer = node->renderer();
if (renderer == NULL)
continue;
WTF::Vector<IntRect> rects;
IntRect clipBounds = IntRect(0, 0, INT_MAX, INT_MAX);
IntRect focusBounds = IntRect(0, 0, INT_MAX, INT_MAX);
IntRect* rectPtr = &focusBounds;
if (node->isTextNode()) {
Text* textNode = (Text*) node;
if (CacheBuilder::ConstructTextRects(textNode, 0, textNode,
INT_MAX, globalOffsetX, globalOffsetY, rectPtr,
clipBounds, &rects) == false)
continue;
} else {
IntRect nodeBounds = node->getRect();
if (CacheBuilder::ConstructPartRects(node, nodeBounds, rectPtr,
globalOffsetX, globalOffsetY, &rects) == false)
continue;
}
unsigned arraySize = rects.size();
if (arraySize > 1 || (arraySize == 1 && (rectPtr->width() != rect.width())) ||
rectPtr->height() != rect.height()) {
if (hasRectParts == false) {
DUMP_NAV_LOGD("static DebugTestRectPart TEST%s_RECTPARTS[] = {\n", name);
hasRectParts = true;
}
if (node->isTextNode() == false) {
unsigned rectIndex = 0;
for (; rectIndex < arraySize; rectIndex++) {
rectPtr = &rects.at(rectIndex);
DUMP_NAV_LOGD("{ %d, %d, %d, %d, %d }, // %d\n", nodeIndex,
rectPtr->x(), rectPtr->y(), rectPtr->width(),
rectPtr->height(), rectIndex + 1);
}
} else {
RenderText* renderText = (RenderText*) node->renderer();
InlineTextBox* textBox = renderText->firstTextBox();
unsigned rectIndex = 0;
while (textBox) {
FloatPoint pt = renderText->localToAbsolute();
IntRect rect = textBox->selectionRect((int) pt.x(), (int) pt.y(), 0, INT_MAX);
mIndex = 0;
mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, "{ %d, %d, %d, %d, %d",
nodeIndex, rect.x(), rect.y(), rect.width(), rect.height());
mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d, %d, %d",
textBox->len(), 0 /*textBox->selectionHeight()*/,
0 /*textBox->selectionTop()*/);
mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d, %d, %d",
0 /*textBox->spaceAdd()*/, textBox->start(), 0 /*textBox->textPos()*/);
mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d, %d, %d, %d",
textBox->x(), textBox->y(), textBox->width(), textBox->height());
int baseline = textBox->renderer()->style(textBox->isFirstLineStyle())->font().ascent();
mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, ", %d }, // %d ",
baseline, ++rectIndex);
wideString(node->textContent().characters() + textBox->start(), textBox->len(), true);
DUMP_NAV_LOGD("%.*s\n", mIndex, mBuffer);
textBox = textBox->nextTextBox();
}
}
}
} while ((node = node->traverseNextNode()) != NULL);
if (hasRectParts)
DUMP_NAV_LOGD("{0}\n};\n\n");
else
DUMP_NAV_LOGD("static DebugTestRectPart* TEST%s_RECTPARTS = NULL;\n", name);
}
int contentsWidth = layer->width();
int contentsHeight = layer->height();
DUMP_NAV_LOGD("static int TEST%s_FOCUS = %d;\n", name, focusIndex);
DUMP_NAV_LOGD("static int TEST%s_WIDTH = %d;\n", name, contentsWidth);
DUMP_NAV_LOGD("static int TEST%s_HEIGHT = %d;\n", name, contentsHeight);
}
bool CacheBuilder::Debug::isFocusable(Node* node) {
if (node->hasTagName(HTMLNames::areaTag))
return true;
if (node->renderer() == false)
return false;
if (node->isKeyboardFocusable(NULL))
return true;
if (node->isMouseFocusable())
return true;
if (node->isFocusable())
return true;
if (CacheBuilder::AnyIsClick(node))
return false;
if (CacheBuilder::HasTriggerEvent(node))
return true;
return false;
}
void CacheBuilder::Debug::localName(Node* node) {
const AtomicString& local = node->localName();
if (node->isTextNode())
print("\"#text\"");
else
wideString(local.characters(), local.length(), false);
print(", ");
}
void CacheBuilder::Debug::newLine(int indent) {
if (mPrefix[0] != '\n')
print(&mPrefix[0], 1);
flush();
int lastnewline = mIndex - 1;
while (lastnewline >= 0 && mBuffer[lastnewline] != '\n')
lastnewline--;
lastnewline++;
char* buffer = mBuffer;
if (lastnewline > 0) {
DUMP_NAV_LOGD("%.*s", lastnewline, buffer);
mIndex -= lastnewline;
buffer += lastnewline;
}
size_t prefixLen = strlen(mPrefix);
int minPrefix = prefixLen - 1;
while (minPrefix >= 0 && mPrefix[minPrefix] != '\n')
minPrefix--;
minPrefix = prefixLen - minPrefix - 1;
if (mIndex > minPrefix)
DUMP_NAV_LOGD("%.*s\n", mIndex, buffer);
mIndex = 0;
setIndent(indent);
}
int CacheBuilder::Debug::ParentIndex(Node* node, int count, Node* parent)
{
if (parent == NULL)
return -1;
ASSERT(node != parent);
int result = count;
Node* previous = node;
do {
result--;
previous = previous->traversePreviousNode();
} while (previous && previous != parent);
if (previous != NULL)
return result;
result = count;
do {
result++;
} while ((node = node->traverseNextNode()) != NULL && node != parent);
if (node != NULL)
return result;
ASSERT(0);
return -1;
}
void CacheBuilder::Debug::print(const char* name) {
print(name, strlen(name));
}
void CacheBuilder::Debug::print(const char* name, unsigned len) {
do {
if (mIndex + len >= DEBUG_BUFFER_SIZE)
flush();
int copyLen = mIndex + len < DEBUG_BUFFER_SIZE ?
len : DEBUG_BUFFER_SIZE - mIndex;
memcpy(&mBuffer[mIndex], name, copyLen);
mIndex += copyLen;
name += copyLen;
len -= copyLen;
} while (len > 0);
mBuffer[mIndex] = '\0';
}
void CacheBuilder::Debug::setIndent(int indent)
{
char scratch[64];
snprintf(scratch, sizeof(scratch), "%.*s", indent,
" ");
print(scratch);
}
void CacheBuilder::Debug::uChar(const UChar* name, unsigned len, bool hex) {
const UChar* end = name + len;
bool wroteHex = false;
while (name < end) {
unsigned ch = *name++;
if (ch == '\t' || ch == '\n' || ch == '\r' || ch == 0xa0)
ch = ' ';
if (ch < ' ' || ch == 0x7f) {
if (hex) {
mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex, "\\x%02x", ch);
wroteHex = true;
} else
mBuffer[mIndex++] = '?';
} else if (ch >= 0x80) {
if (hex) {
if (ch < 0x800)
mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex,
"\\x%02x\\x%02x", ch >> 6 | 0xc0, (ch & 0x3f) | 0x80);
else
mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex,
"\\x%02x\\x%02x\\x%02x", ch >> 12 | 0xe0,
(ch >> 6 & 0x3f) | 0x80, (ch & 0x3f) | 0x80);
wroteHex = true;
} else
mBuffer[mIndex++] = '?';
} else {
if (wroteHex && WTF::isASCIIHexDigit((UChar) ch))
mIndex += snprintf(&mBuffer[mIndex], mBufferSize - mIndex,
"\" \"");
else if (ch == '"' || ch == '\\')
mBuffer[mIndex++] = '\\';
mBuffer[mIndex++] = ch;
wroteHex = false;
}
if (mIndex + 1 >= DEBUG_BUFFER_SIZE)
flush();
}
flush();
}
void CacheBuilder::Debug::validateFrame() {
Frame* frame = frameAnd();
Page* page = frame->page();
ASSERT(page);
ASSERT((int) page > 0x10000);
Frame* child = frame->tree()->firstChild();
while (child) {
Builder(child)->mDebug.validateFrame();
child = child->tree()->nextSibling();
}
}
void CacheBuilder::Debug::wideString(const UChar* chars, int length, bool hex) {
if (length == 0)
print("\"\"");
else {
print("\"");
uChar(chars, length, hex);
print("\"");
}
}
void CacheBuilder::Debug::wideString(const String& str) {
wideString(str.characters(), str.length(), false);
}
#endif // DUMP_NAV_CACHE
CacheBuilder::CacheBuilder()
{
mAllowableTypes = ALL_CACHEDNODETYPES;
#ifdef DUMP_NAV_CACHE_USING_PRINTF
gNavCacheLogFile = NULL;
#endif
}
void CacheBuilder::adjustForColumns(const ClipColumnTracker& track,
CachedNode* node, IntRect* bounds)
{
int x = 0;
int y = 0;
int tx = track.mBounds.x();
int ty = track.mBounds.y();
int columnGap = track.mColumnGap;
size_t limit = track.mColumns->size();
for (size_t index = 0; index < limit; index++) {
IntRect column = track.mColumns->at(index);
column.move(tx, ty);
IntRect test = *bounds;
test.move(x, y);
if (column.contains(test)) {
if ((x | y) == 0)
return;
*bounds = test;
node->move(x, y);
return;
}
int xOffset = column.width() + columnGap;
x += track.mDirection == LTR ? xOffset : -xOffset;
y -= column.height();
}
}
// Checks if a node has one of event listener types.
bool CacheBuilder::NodeHasEventListeners(Node* node, AtomicString* eventTypes, int length) {
const RegisteredEventListenerVector& listeners = node->eventListeners();
size_t size = listeners.size();
for (size_t i = 0; i < size; ++i) {
const RegisteredEventListener& r = *listeners[i];
for (int j = 0; j < length; ++j) {
if (r.eventType() == eventTypes[j])
return true;
}
}
return false;
}
bool CacheBuilder::AnyChildIsClick(Node* node)
{
AtomicString eventTypes[5] = {
eventNames().clickEvent,
eventNames().mousedownEvent,
eventNames().mouseupEvent,
eventNames().keydownEvent,
eventNames().keyupEvent
};
Node* child = node->firstChild();
while (child != NULL) {
if (child->isFocusable() ||
NodeHasEventListeners(child, eventTypes, 5))
return true;
if (AnyChildIsClick(child))
return true;
child = child->nextSibling();
}
return false;
}
bool CacheBuilder::AnyIsClick(Node* node)
{
if (node->hasTagName(HTMLNames::bodyTag))
return AnyChildIsClick(node);
AtomicString eventTypeSetOne[4] = {
eventNames().mouseoverEvent,
eventNames().mouseoutEvent,
eventNames().keydownEvent,
eventNames().keyupEvent
};
if (!NodeHasEventListeners(node, eventTypeSetOne, 4))
return false;
AtomicString eventTypeSetTwo[3] = {
eventNames().clickEvent,
eventNames().mousedownEvent,
eventNames().mouseupEvent
};
if (NodeHasEventListeners(node, eventTypeSetTwo, 3))
return false;
return AnyChildIsClick(node);
}
void CacheBuilder::buildCache(CachedRoot* root)
{
Frame* frame = FrameAnd(this);
BuildFrame(frame, frame, root, (CachedFrame*) root);
root->finishInit(); // set up frame parent pointers, child pointers
setData((CachedFrame*) root);
}
static Node* OneAfter(Node* node)
{
Node* parent = node;
Node* sibling = NULL;
while ((parent = parent->parentNode()) != NULL) {
sibling = parent->nextSibling();
if (sibling != NULL)
break;
}
return sibling;
}
// return true if this renderer is really a pluinview, and it wants
// key-events (i.e. focus)
static bool checkForPluginViewThatWantsFocus(RenderObject* renderer) {
if (renderer->isWidget()) {
Widget* widget = static_cast<RenderWidget*>(renderer)->widget();
if (widget && widget->isPluginView()) {
PluginView* pv = static_cast<PluginView*>(widget);
// check if this plugin really wants key events (TODO)
return true;
}
}
return false;
}
// when new focus is found, push it's parent on a stack
// as long as more focii are found with the same (grand) parent, note it
// (which only requires retrieving the last parent on the stack)
// when the parent's last child is found, pop the stack
// different from Tracker in that Tracker only pushes focii with children
// making this work with focus - child focus - grandchild focus is tricky
// if I keep the generation number, I may be able to more quickly determine that
// a node is a grandchild of the focus's parent
// this additionally requires being able to find the grandchild's parent
// keep nodes that are focusable
void CacheBuilder::BuildFrame(Frame* root, Frame* frame,
CachedRoot* cachedRoot, CachedFrame* cachedFrame)
{
WTF::Vector<Tracker> tracker(1);
{
Tracker* baseTracker = tracker.data(); // sentinel
bzero(baseTracker, sizeof(Tracker));
baseTracker->mCachedNodeIndex = -1;
}
WTF::Vector<ClipColumnTracker> clipTracker(1);
{
ClipColumnTracker* baseTracker = clipTracker.data(); // sentinel
bzero(baseTracker, sizeof(ClipColumnTracker));
}
WTF::Vector<TabIndexTracker> tabIndexTracker(1);
{
TabIndexTracker* baseTracker = tabIndexTracker.data(); // sentinel
bzero(baseTracker, sizeof(TabIndexTracker));
}
#if DUMP_NAV_CACHE
char* frameNamePtr = cachedFrame->mDebug.mFrameName;
Builder(frame)->mDebug.frameName(frameNamePtr, frameNamePtr +
sizeof(cachedFrame->mDebug.mFrameName) - 1);
*frameNamePtr = '\0';
int nodeIndex = 1;
#endif
NodeWalk walk;
Document* doc = frame->document();
Node* parent = doc;
CachedNode cachedParentNode;
cachedParentNode.init(parent);
#if DUMP_NAV_CACHE
cachedParentNode.mDebug.mNodeIndex = nodeIndex;
#endif
cachedFrame->add(cachedParentNode);
Node* node = parent;
int cacheIndex = 1;
Node* focused = doc->focusedNode();
if (focused)
cachedRoot->setFocusBounds(focused->getRect());
int globalOffsetX, globalOffsetY;
GetGlobalOffset(frame, &globalOffsetX, &globalOffsetY);
while (walk.mMore || (node = node->traverseNextNode()) != NULL) {
#if DUMP_NAV_CACHE
nodeIndex++;
#endif
Tracker* last = &tracker.last();
int lastChildIndex = cachedFrame->size() - 1;
while (node == last->mLastChild) {
if (CleanUpContainedNodes(cachedFrame, last, lastChildIndex))
cacheIndex--;
tracker.removeLast();
lastChildIndex = last->mCachedNodeIndex;
last = &tracker.last();
}
if (node == last->mParentLastChild)
last->mParentLastChild = NULL;
do {
const ClipColumnTracker* lastClip = &clipTracker.last();
if (node != lastClip->mLastChild)
break;
clipTracker.removeLast();
} while (true);
do {
const TabIndexTracker* lastTabIndex = &tabIndexTracker.last();
if (node != lastTabIndex->mLastChild)
break;
tabIndexTracker.removeLast();
} while (true);
Frame* child = HasFrame(node);
CachedNode cachedNode;
if (child != NULL) {
if (child->document() == NULL)
continue;
RenderObject* nodeRenderer = node->renderer();
if (nodeRenderer != NULL && nodeRenderer->style()->visibility() == HIDDEN)
continue;
CachedFrame cachedChild;
cachedChild.init(cachedRoot, cacheIndex, child);
int childFrameIndex = cachedFrame->childCount();
cachedFrame->addFrame(cachedChild);
cachedNode.init(node);
cachedNode.setIndex(cacheIndex++);
cachedNode.setChildFrameIndex(childFrameIndex);
#if DUMP_NAV_CACHE
cachedNode.mDebug.mNodeIndex = nodeIndex;
cachedNode.mDebug.mParentGroupIndex = Debug::ParentIndex(
node, nodeIndex, NULL);
#endif
cachedFrame->add(cachedNode);
CachedFrame* childPtr = cachedFrame->lastChild();
BuildFrame(root, child, cachedRoot, childPtr);
continue;
}
int tabIndex = node->tabIndex();
Node* lastChild = node->lastChild();
if (tabIndex <= 0)
tabIndex = tabIndexTracker.last().mTabIndex;
else if (tabIndex > 0 && lastChild) {
DBG_NAV_LOGD("tabIndex=%d node=%p", tabIndex, node);
tabIndexTracker.grow(tabIndexTracker.size() + 1);
TabIndexTracker& indexTracker = tabIndexTracker.last();
indexTracker.mTabIndex = tabIndex;
indexTracker.mLastChild = OneAfter(lastChild);
}
RenderObject* nodeRenderer = node->renderer();
bool isTransparent = false;
bool hasCursorRing = true;
if (nodeRenderer != NULL) {
RenderStyle* style = nodeRenderer->style();
if (style->visibility() == HIDDEN)
continue;
isTransparent = style->hasBackground() == false;
#ifdef ANDROID_CSS_TAP_HIGHLIGHT_COLOR
hasCursorRing = style->tapHighlightColor().alpha() > 0;
#endif
}
bool more = walk.mMore;
walk.reset();
// GetGlobalBounds(node, &bounds, false);
bool computeCursorRings = false;
bool hasClip = false;
bool hasMouseOver = false;
bool isAnchor = false;
bool isArea = node->hasTagName(HTMLNames::areaTag);
bool isPassword = false;
bool isTextArea = false;
bool isTextField = false;
bool isRtlText = false;
bool isUnclipped = false;
bool isFocus = node == focused;
bool takesFocus = false;
bool wantsKeyEvents = false;
int maxLength = -1;
int textSize = 12;
int columnGap = 0;
TextDirection direction = LTR;
String name;
String exported;
CachedNodeType type = NORMAL_CACHEDNODETYPE;
IntRect bounds;
IntRect absBounds;
WTF::Vector<IntRect>* columns = NULL;
if (isArea) {
HTMLAreaElement* area = static_cast<HTMLAreaElement*>(node);
bounds = getAreaRect(area);
bounds.move(globalOffsetX, globalOffsetY);
absBounds = bounds;
isUnclipped = true; // FIXME: areamaps require more effort to detect
// assume areamaps are always visible for now
takesFocus = true;
goto keepNode;
}
if (nodeRenderer == NULL)
continue;
// some common setup
absBounds = nodeRenderer->absoluteBoundingBoxRect();
absBounds.move(globalOffsetX, globalOffsetY);
hasClip = nodeRenderer->hasOverflowClip();
if (checkForPluginViewThatWantsFocus(nodeRenderer)) {
bounds = absBounds;
isUnclipped = true;
takesFocus = true;
wantsKeyEvents = true;
goto keepNode;
}
if (nodeRenderer->isRenderBlock()) {
RenderBlock* renderBlock = (RenderBlock*) nodeRenderer;
if (renderBlock->hasColumns()) {
columns = renderBlock->columnRects();
#ifdef ANDROID_EXPOSE_COLUMN_GAP
columnGap = renderBlock->columnGap();
#endif
direction = renderBlock->style()->direction();
}
}
if ((hasClip != false || columns != NULL) && lastChild) {
clipTracker.grow(clipTracker.size() + 1);
ClipColumnTracker& clip = clipTracker.last();
clip.mBounds = absBounds;
clip.mLastChild = OneAfter(lastChild);
clip.mNode = node;
clip.mColumns = columns;
clip.mColumnGap = columnGap;
clip.mHasClip = hasClip;
clip.mDirection = direction;
if (columns != NULL) {
const IntRect& oRect = ((RenderBox*)nodeRenderer)->overflowRect(true);
clip.mBounds.move(oRect.x(), oRect.y());
}
}
if (node->isTextNode() && mAllowableTypes != NORMAL_CACHEDNODETYPE) {
if (last->mSomeParentTakesFocus) // don't look at text inside focusable node
continue;
CachedNodeType checkType;
if (isFocusableText(&walk, more, node, &checkType,
&exported) == false)
continue;
#if DUMP_NAV_CACHE
{
char buffer[DEBUG_BUFFER_SIZE];
mDebug.init(buffer, sizeof(buffer));
mDebug.print("text link found: ");
mDebug.wideString(exported);
DUMP_NAV_LOGD("%s\n", buffer);
}
#endif
type = (CachedNodeType) checkType;
// !!! test ! is the following line correctly needed for frames to work?
cachedNode.init(node);
const ClipColumnTracker& clipTrack = clipTracker.last();
const IntRect& clip = clipTrack.mHasClip ? clipTrack.mBounds :
IntRect(0, 0, INT_MAX, INT_MAX);
if (ConstructTextRects((WebCore::Text*) node, walk.mStart,
(WebCore::Text*) walk.mFinalNode, walk.mEnd, globalOffsetX,
globalOffsetY, &bounds, clip, &cachedNode.cursorRings()) == false)
continue;
absBounds = bounds;
cachedNode.setBounds(bounds);
if (bounds.width() < MINIMUM_FOCUSABLE_WIDTH)
continue;
if (bounds.height() < MINIMUM_FOCUSABLE_HEIGHT)
continue;
computeCursorRings = true;
isUnclipped = true; // FIXME: to hide or partially occlude synthesized links, each
// focus ring will also need the offset and length of characters
// used to produce it
goto keepTextNode;
}
if (node->hasTagName(WebCore::HTMLNames::inputTag)) {
HTMLInputElement* input = (HTMLInputElement*) node;
if (input->inputType() == HTMLInputElement::FILE)
continue;
isTextField = input->isTextField();
if (isTextField)
wantsKeyEvents = true;
isPassword = input->inputType() == HTMLInputElement::PASSWORD;
maxLength = input->maxLength();
name = input->name().string().copy();
isUnclipped = isTransparent; // can't detect if this is drawn on top (example: deviant.com login parts)
} else if (node->hasTagName(HTMLNames::textareaTag))
isTextArea = wantsKeyEvents = true;
else if (node->hasTagName(HTMLNames::aTag)) {
const HTMLAnchorElement* anchorNode =
(const HTMLAnchorElement*) node;
if (!anchorNode->isFocusable() && !HasTriggerEvent(node))
continue;
if (node->disabled())
continue;
hasMouseOver = NodeHasEventListeners(node, &eventNames().mouseoverEvent, 1);
isAnchor = true;
KURL href = anchorNode->href();
if (!href.isEmpty() && !href.protocolIs("javascript"))
// Set the exported string for all non-javascript anchors.
exported = href.string().copy();
}
if (isTextField || isTextArea) {
RenderTextControl* renderText =
static_cast<RenderTextControl*>(nodeRenderer);
if (isFocus)
cachedRoot->setSelection(renderText->selectionStart(), renderText->selectionEnd());
exported = renderText->text().copy();
// FIXME: Would it be better to use (float) size()?
// FIXME: Are we sure there will always be a style and font, and it's correct?
RenderStyle* style = nodeRenderer->style();
if (style) {
isUnclipped |= !style->hasAppearance();
textSize = style->fontSize();
isRtlText = style->direction() == RTL ||
style->textAlign() == WebCore::RIGHT ||
style->textAlign() == WebCore::WEBKIT_RIGHT;
}
}
takesFocus = true;
bounds = absBounds;
if (!isAnchor) {
bool isFocusable = node->isKeyboardFocusable(NULL) ||
node->isMouseFocusable() || node->isFocusable();
if (isFocusable == false) {
if (node->disabled())
continue;
bool overOrOut = HasOverOrOut(node);
bool hasTrigger = HasTriggerEvent(node);
if (overOrOut == false && hasTrigger == false)
continue;
takesFocus = hasTrigger;
}
}
computeCursorRings = true;
keepNode:
cachedNode.init(node);
if (computeCursorRings == false) {
cachedNode.setBounds(bounds);
cachedNode.cursorRings().append(bounds);
} else if (ConstructPartRects(node, bounds, cachedNode.boundsPtr(),
globalOffsetX, globalOffsetY, &cachedNode.cursorRings()) == false)
continue;
keepTextNode:
IntRect clip = hasClip ? bounds : absBounds;
size_t clipIndex = clipTracker.size();
if (clipTracker.last().mNode == node)
clipIndex -= 1;
while (--clipIndex > 0) {
const ClipColumnTracker& clipTrack = clipTracker.at(clipIndex);
if (clipTrack.mHasClip == false) {
adjustForColumns(clipTrack, &cachedNode, &absBounds);
continue;
}
const IntRect& parentClip = clipTrack.mBounds;
if (hasClip == false && isAnchor)
clip = parentClip;
else
clip.intersect(parentClip);
hasClip = true;
}
if (hasClip && !clip.isEmpty() && cachedNode.clip(clip) == false) {
cachedNode.setBounds(clip);
cachedNode.cursorRings().append(clip);
isUnclipped = true;
}
cachedNode.setNavableRects();
cachedNode.setChildFrameIndex(-1);
cachedNode.setExport(exported);
cachedNode.setHasCursorRing(hasCursorRing);
cachedNode.setHasMouseOver(hasMouseOver);
cachedNode.setHitBounds(absBounds);
cachedNode.setIndex(cacheIndex);
cachedNode.setIsAnchor(isAnchor);
cachedNode.setIsArea(isArea);
cachedNode.setIsFocus(isFocus);
cachedNode.setIsPassword(isPassword);
cachedNode.setIsRtlText(isRtlText);
cachedNode.setIsTextArea(isTextArea);
cachedNode.setIsTextField(isTextField);
cachedNode.setIsTransparent(isTransparent);
cachedNode.setIsUnclipped(isUnclipped);
cachedNode.setMaxLength(maxLength);
cachedNode.setName(name);
cachedNode.setParentIndex(last->mCachedNodeIndex);
if (last->mParentLastChild == NULL)
last->mParentLastChild = OneAfter(node->parentNode()->lastChild());
cachedNode.setParentGroup(last->mParentLastChild);
cachedNode.setTabIndex(tabIndex);
cachedNode.setTextSize(textSize);
cachedNode.setType(type);
cachedNode.setWantsKeyEvents(wantsKeyEvents);
#if DUMP_NAV_CACHE
cachedNode.mDebug.mNodeIndex = nodeIndex;
cachedNode.mDebug.mParentGroupIndex = Debug::ParentIndex(
node, nodeIndex, (Node*) cachedNode.parentGroup());
#endif
cachedFrame->add(cachedNode);
{
int lastIndex = cachedFrame->size() - 1;
if (node == focused) {
CachedNode* cachedNodePtr = cachedFrame->getIndex(lastIndex);
cachedRoot->setCachedFocus(cachedFrame, cachedNodePtr);
}
if (lastChild != NULL) {
tracker.grow(tracker.size() + 1);
Tracker& working = tracker.last();
working.mCachedNodeIndex = lastIndex;
working.mLastChild = OneAfter(lastChild);
working.mParentLastChild = OneAfter(node->parentNode()->lastChild());
last = &tracker.at(tracker.size() - 2);
working.mSomeParentTakesFocus = last->mSomeParentTakesFocus | takesFocus;
}
}
cacheIndex++;
}
while (tracker.size() > 1) {
Tracker* last = &tracker.last();
int lastChildIndex = cachedFrame->size() - 1;
if (CleanUpContainedNodes(cachedFrame, last, lastChildIndex))
cacheIndex--;
tracker.removeLast();
}
}
bool CacheBuilder::CleanUpContainedNodes(CachedFrame* cachedFrame,
const Tracker* last, int lastChildIndex)
{
// if outer is body, disable outer
// or if there's more than one inner, disable outer
// or if inner is keyboard focusable, disable outer
// else disable inner by removing it
int childCount = lastChildIndex - last->mCachedNodeIndex;
if (childCount == 0)
return false;
CachedNode* lastCached = cachedFrame->getIndex(last->mCachedNodeIndex);
Node* lastNode = (Node*) lastCached->nodePointer();
if ((childCount > 1 && lastNode->hasTagName(HTMLNames::selectTag) == false) ||
lastNode->hasTagName(HTMLNames::bodyTag) ||
lastNode->hasTagName(HTMLNames::formTag)) {
lastCached->setBounds(IntRect(0, 0, 0, 0));
lastCached->cursorRings().clear();
lastCached->setNavableRects();
return false;
}
CachedNode* onlyChildCached = cachedFrame->lastNode();
Node* onlyChild = (Node*) onlyChildCached->nodePointer();
bool outerIsMouseMoveOnly =
lastNode->isKeyboardFocusable(NULL) == false &&
lastNode->isMouseFocusable() == false &&
lastNode->isFocusable() == false &&
HasOverOrOut(lastNode) == true &&
HasTriggerEvent(lastNode) == false;
if (onlyChildCached->parent() == lastCached)
onlyChildCached->setParentIndex(lastCached->parentIndex());
if (outerIsMouseMoveOnly || onlyChild->isKeyboardFocusable(NULL))
*lastCached = *onlyChildCached;
cachedFrame->removeLast();
return true;
}
Node* CacheBuilder::currentFocus() const
{
Frame* frame = FrameAnd(this);
Document* doc = frame->document();
if (doc != NULL) {
Node* focus = doc->focusedNode();
if (focus != NULL)
return focus;
}
Frame* child = frame->tree()->firstChild();
while (child) {
CacheBuilder* cacheBuilder = Builder(child);
Node* focus = cacheBuilder->currentFocus();
if (focus)
return focus;
child = child->tree()->nextSibling();
}
return NULL;
}
static bool strCharCmp(const char* matches, const UChar* test, int wordLength,
int wordCount)
{
for (int index = 0; index < wordCount; index++) {
for (int inner = 0; inner < wordLength; inner++) {
if (matches[inner] != test[inner]) {
matches += wordLength;
goto next;
}
}
return true;
next:
;
}
return false;
}
static const int stateTwoLetter[] = {
0x02060c00, // A followed by: [KLRSZ]
0x00000000, // B
0x00084001, // C followed by: [AOT]
0x00000014, // D followed by: [CE]
0x00000000, // E
0x00001800, // F followed by: [LM]
0x00100001, // G followed by: [AU]
0x00000100, // H followed by: [I]
0x00002809, // I followed by: [ADLN]
0x00000000, // J
0x01040000, // K followed by: [SY]
0x00000001, // L followed by: [A]
0x000ce199, // M followed by: [ADEHINOPST]
0x0120129c, // N followed by: [CDEHJMVY]
0x00020480, // O followed by: [HKR]
0x00420001, // P followed by: [ARW]
0x00000000, // Q
0x00000100, // R followed by: [I]
0x0000000c, // S followed by: [CD]
0x00802000, // T followed by: [NX]
0x00080000, // U followed by: [T]
0x00080101, // V followed by: [AIT]
0x01200101 // W followed by: [AIVY]
};
static const char firstIndex[] = {
0, 5, 5, 8, 10, 10, 12, 14,
15, 19, 19, 21, 22, 32, 40, 43,
46, 46, 47, 49, 51, 52, 55, 59
};
// from http://infolab.stanford.edu/~manku/bitcount/bitcount.html
#define TWO(c) (0x1u << (c))
#define MASK(c) (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
#define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
int bitcount (unsigned int n)
{
n = COUNT(n, 0);
n = COUNT(n, 1);
n = COUNT(n, 2);
n = COUNT(n, 3);
return COUNT(n, 4);
}
#undef TWO
#undef MASK
#undef COUNT
static bool isUnicodeSpace(UChar ch)
{
return ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r' || ch == 0xa0;
}
static bool validZip(int stateIndex, const UChar* zipPtr)
{
static const struct {
char mLow;
char mHigh;
char mException1;
char mException2;
} zipRange[] = {
{ 99, 99, -1, -1 }, // AK Alaska
{ 35, 36, -1, -1 }, // AL Alabama
{ 71, 72, -1, -1 }, // AR Arkansas
{ 96, 96, -1, -1 }, // AS American Samoa
{ 85, 86, -1, -1 }, // AZ Arizona
{ 90, 96, -1, -1 }, // CA California
{ 80, 81, -1, -1 }, // CO Colorado
{ 6, 6, -1, -1 }, // CT Connecticut
{ 20, 20, -1, -1 }, // DC District of Columbia
{ 19, 19, -1, -1 }, // DE Delaware
{ 32, 34, -1, -1 }, // FL Florida
{ 96, 96, -1, -1 }, // FM Federated States of Micronesia
{ 30, 31, -1, -1 }, // GA Georgia
{ 96, 96, -1, -1 }, // GU Guam
{ 96, 96, -1, -1 }, // HI Hawaii
{ 50, 52, -1, -1 }, // IA Iowa
{ 83, 83, -1, -1 }, // ID Idaho
{ 60, 62, -1, -1 }, // IL Illinois
{ 46, 47, -1, -1 }, // IN Indiana
{ 66, 67, 73, -1 }, // KS Kansas
{ 40, 42, -1, -1 }, // KY Kentucky
{ 70, 71, -1, -1 }, // LA Louisiana
{ 1, 2, -1, -1 }, // MA Massachusetts
{ 20, 21, -1, -1 }, // MD Maryland
{ 3, 4, -1, -1 }, // ME Maine
{ 96, 96, -1, -1 }, // MH Marshall Islands
{ 48, 49, -1, -1 }, // MI Michigan
{ 55, 56, -1, -1 }, // MN Minnesota
{ 63, 65, -1, -1 }, // MO Missouri
{ 96, 96, -1, -1 }, // MP Northern Mariana Islands
{ 38, 39, -1, -1 }, // MS Mississippi
{ 55, 56, -1, -1 }, // MT Montana
{ 27, 28, -1, -1 }, // NC North Carolina
{ 58, 58, -1, -1 }, // ND North Dakota
{ 68, 69, -1, -1 }, // NE Nebraska
{ 3, 4, -1, -1 }, // NH New Hampshire
{ 7, 8, -1, -1 }, // NJ New Jersey
{ 87, 88, 86, -1 }, // NM New Mexico
{ 88, 89, 96, -1 }, // NV Nevada
{ 10, 14, 0, 6 }, // NY New York
{ 43, 45, -1, -1 }, // OH Ohio
{ 73, 74, -1, -1 }, // OK Oklahoma
{ 97, 97, -1, -1 }, // OR Oregon
{ 15, 19, -1, -1 }, // PA Pennsylvania
{ 6, 6, 0, 9 }, // PR Puerto Rico
{ 96, 96, -1, -1 }, // PW Palau
{ 2, 2, -1, -1 }, // RI Rhode Island
{ 29, 29, -1, -1 }, // SC South Carolina
{ 57, 57, -1, -1 }, // SD South Dakota
{ 37, 38, -1, -1 }, // TN Tennessee
{ 75, 79, 87, 88 }, // TX Texas
{ 84, 84, -1, -1 }, // UT Utah
{ 22, 24, 20, -1 }, // VA Virginia
{ 6, 9, -1, -1 }, // VI Virgin Islands
{ 5, 5, -1, -1 }, // VT Vermont
{ 98, 99, -1, -1 }, // WA Washington
{ 53, 54, -1, -1 }, // WI Wisconsin
{ 24, 26, -1, -1 }, // WV West Virginia
{ 82, 83, -1, -1 } // WY Wyoming
};
int zip = zipPtr[0] - '0';
zip *= 10;
zip += zipPtr[1] - '0';
int low = zipRange[stateIndex].mLow;
int high = zipRange[stateIndex].mHigh;
if (zip >= low && zip <= high)
return true;
if (zip == zipRange[stateIndex].mException1)
return true;
if (zip == zipRange[stateIndex].mException2)
return true;
return false;
}
#define MAX_PLACE_NAME_LENGTH 25 // the longest allowable one word place name
CacheBuilder::FoundState CacheBuilder::FindAddress(const UChar* chars,
unsigned length, int* start, int* end, bool caseInsensitive)
{
FindState addressState;
FindReset(&addressState);
addressState.mWords[0] = addressState.mStarts[0] = chars;
addressState.mCaseInsensitive = caseInsensitive;
FoundState state = FindPartialAddress(chars, chars, length, &addressState);
if (state == FOUND_PARTIAL && addressState.mProgress == ZIP_CODE &&
addressState.mNumberCount == 0) {
addressState.mProgress = FIND_STREET;
state = FindPartialAddress(NULL, NULL, 0, &addressState);
}
*start = addressState.mStartResult;
*end = addressState.mEndResult;
return state;
}
CacheBuilder::FoundState CacheBuilder::FindPartialAddress(const UChar* baseChars,
const UChar* chars, unsigned length, FindState* s)
{
// lower case letters are optional; trailing asterisk is optional 's'
static char const* const longStreetNames[] = {
"\x04" "LleY" "\x04" "NneX" "\x05" "RCade" "\x05" "VEnue" "\x06" "LAMEDA", // A
"\x04" "aYoU" "\x04" "eaCH" "\x03" "eND" "\x05" "LuFf*" "\x05" "oTtoM"
"\x08" "ouLeVarD" "\x05" "Ranch" "\x05" "RidGe" "\x05" "RooK*"
"\x04" "urG*" "\x05" "YPass" "\x07" "roadWAY", // B
"\x05" "AMINO"
"\x03" "amP" "\x05" "anYoN" "\x03" "aPE" "\x07" "auSeWaY" "\x06" "enTeR*"
"\x06" "IRcle*" "\x05" "LiFf*" "\x03" "LuB" "\x05" "oMmoN" "\x06" "ORner*"
"\x05" "ouRSE" "\x05" "ourT*" "\x04" "oVe*" "\x04" "ReeK" "\x07" "REScent"
"\x04" "ReST" "\x07" "ROSSING" "\x08" "ROSSROAD" "\x04" "URVe"
"\x05" "AMINO" "\x06" "IRCULO" "\x07" "REScent", // C
"\x03" "aLe" "\x02" "aM" "\x05" "iVide" "\x05" "Rive*", // D
"\x06" "STate*" "\x09" "XPresswaY" "\x09" "XTension*", // E
"\x04" "ALL*" "\x04" "eRrY" "\x05" "ieLD*" "\x04" "LaT*" "\x04" "oRD*"
"\x05" "oReST" "\x05" "oRGe*" "\x04" "oRK*" "\x03" "orT" "\x06" "reeWaY", // F
"\x06" "arDeN*" "\x06" "aTeWaY" "\x04" "LeN*" "\x05" "ReeN*" "\x05" "RoVe*", // G
"\x06" "arBoR*" "\x04" "aVeN" "\x06" "eighTS" "\x06" "ighWaY" "\x04" "iLl*"
"\x05" "OLloW", // H
"\x04" "NLeT" "\x06" "Sland*" "\x03" "SLE", // I
"\x08" "unCTion*", // J
"\x03" "eY*" "\x05" "NoLl*", // K
"\x04" "aKe*" "\x03" "AND" "\x06" "aNDinG" "\x03" "aNe" "\x05" "iGhT*"
"\x03" "oaF" "\x04" "oCK*" "\x04" "oDGe" "\x03" "OOP", // L
"\x03" "ALL" "\x05" "aNoR*" "\x06" "eaDoW*" "\x03" "EWS" "\x04" "iLl*"
"\x06" "iSsioN" "\x07" "oTorWaY" "\x04" "ounT" "\x08" "ounTaiN*", // M
"\x03" "eCK", // N
"\x06" "RCHard" "\x03" "VAL" "\x07" "verPASs", // O
"\x04" "ARK*" "\x07" "arKWaY*" "\x03" "ASS" "\x06" "aSsaGE" "\x03" "ATH"
"\x03" "IKE" "\x04" "iNE*" "\x04" "Lace" "\x05" "LaiN*" "\x04" "LaZa"
"\x05" "oinT*" "\x04" "oRT*" "\x06" "Rairie" "\x06" "RIVADA", // P
NULL,
"\x05" "ADiaL" "\x03" "AMP" "\x04" "aNCH" "\x05" "aPiD*"
"\x03" "eST"
"\x05" "iDGe*" "\x04" "IVer" "\x04" "oaD*" "\x04" "ouTE" "\x02" "OW"
"\x02" "UE" "\x02" "UN", // R
"\x05" "HoaL*" "\x05" "HoRe*" "\x05" "KyWaY" "\x06" "PrinG*" "\x04" "PUR*"
"\x06" "Quare*" "\x06" "TAtion" "\x08" "TRAvenue" "\x05" "TReaM"
"\x06" "Treet*" "\x05" "uMmiT" "\x07" "PeeDWaY", // S
"\x06" "ERrace" "\x09" "hRoughWaY" "\x04" "RaCE" "\x04" "RAcK" "\x09" "RaFficwaY"
"\x04" "RaiL" "\x05" "UNneL" "\x07" "urnPiKE", // T
"\x08" "nderPASs" "\x05" "Nion*", // U
"\x06" "aLleY*" "\x06" "IAduct" "\x04" "ieW*" "\x07" "iLlaGe*" "\x04" "iLle"
"\x04" "ISta", // V
"\x04" "ALK*" "\x03" "ALL" "\x03" "AY*" "\x04" "eLl*", // W
"\x03" "ING" "\x02" "RD", // X
};
static char const* const longStateNames[] = {
"\x8e" "la" "\x85" "bama" "\x02" "\x84" "ska" "\x01" "\x8f" "merican Samoa" "\x04"
"\x91" "r" "\x86" "izona" "\x05" "\x87" "kansas" "\x03",
NULL,
"\x8b" "alifornia" "\x06" "\x95" "o" "\x87" "lorado" "\x07" "\x8a" "nnecticut" "\x08",
"\x89" "elaware" "\x0a" "\x95" "istrict of Columbia" "\x09",
NULL,
"\x9f" "ederated States of Micronesia" "\x0c" "\x88" "lorida" "\x0b",
"\x85" "uam" "\x0e" "\x88" "eorgia" "\x0d",
"\x87" "awaii" "\x0f",
"\x86" "daho" "\x11" "\x89" "llinois" "\x12" "\x88" "ndiana" "\x13" "\x85"
"owa" "\x10",
NULL,
"\x87" "ansas" "\x14" "\x89" "entucky" "\x15",
"\x8a" "ouisiana" "\x16",
"\x86" "aine" "\x19" "\x99" "ar" "\x8e" "shall Islands" "\x1a" "\x86" "yland" "\x18"
"\x8e" "assachusetts" "\x17" "\x93" "i" "\x87" "chigan" "\x1b"
"\x88" "nnesota" "\x1c" "\x93" "iss" "\x88" "issippi" "\x1f" "\x85"
"ouri" "\x1d" "\x88" "ontana" "\x20",
"\x90" "e" "\x87" "braska" "\x23" "\x85" "vada" "\x27" "\xa5" "ew " "\x8a"
"Hampshire" "\x24" "\x87" "Jersey" "\x25" "\x87" "Mexico" "\x26"
"\x85" "York" "\x28" "\x98" "orth " "\x89" "Carolina" "\x21" "\x87"
"Dakota" "\x22" "\x99" "orthern Mariana Islands" "\x1e",
"\x85" "hio" "\x29" "\x89" "klahoma" "\x2a" "\x87" "regon" "\x2b",
"\x86" "alau" "\x2e" "\x8d" "ennsylvania" "\x2c" "\x8c" "uerto Rico" "\x2d",
NULL,
"\x8d" "hode Island" "\x2f",
"\x98" "outh " "\x89" "Carolina" "\x30" "\x87" "Dakota" "\x31",
"\x90" "e" "\x88" "nnessee" "\x32" "\x84" "xas" "\x33",
"\x85" "tah" "\x34",
"\x88" "ermont" "\x37" "\x94" "irgin" "\x89" " Islands" "\x36" "\x83" "ia" "\x35",
"\x8b" "ashington" "\x38" "\x8e" "est Virginia" "\x3a" "\x8a" "isconsin" "\x39"
"\x88" "yoming" "\x3b"
};
#if 0 // DEBUG_NAV_UI
static char const* const progressNames[] = {
"NO_ADDRESS",
"SKIP_TO_SPACE",
"HOUSE_NUMBER",
"NUMBER_TRAILING_SPACE",
"ADDRESS_LINE",
"STATE_NAME",
"SECOND_HALF",
"ZIP_CODE",
"PLUS_4",
"FIND_STREET"
};
#endif
// strategy: US only support at first
// look for a 1 - 5 digit number for a street number (no support for 'One Microsoft Way')
// ignore if preceded by '#', Suite, Ste, Rm
// look for two or more words (up to 5? North Frank Lloyd Wright Blvd)
// note: "The Circle at North Hills St." has six words, and a lower 'at' -- allow at, by, of, in, the, and, ... ?
// if a word starts with a lowercase letter, no match
// allow: , . - # / (for 1/2) ' "
// don't look for street name type yet
// look for one or two delimiters to represent possible 2nd addr line and city name
// look for either full state name, or state two letters, and/or zip code (5 or 9 digits)
// now look for street suffix, either in full or abbreviated form, with optional 's' if there's an asterisk
s->mCurrentStart = chars;
s->mEnd = chars + length;
int candIndex = 0;
bool retryState;
bool mustBeAllUpper = false;
bool secondHalf = false;
chars -= 1;
UChar ch = s->mCurrent;
while (++chars <= s->mEnd) {
UChar prior = ch;
ch = chars < s->mEnd ? *chars : ' ';
switch (s->mProgress) {
case NO_ADDRESS:
if (WTF::isASCIIDigit(ch) == false) {
if (ch != 'O') // letter 'O', not zero
continue;
if (s->mEnd - chars < 3)
continue;
prior = *++chars;
ch = *++chars;
if ((prior != 'n' || ch != 'e') && (prior != 'N' || ch != 'E'))
continue;
if (isUnicodeSpace(*++chars) == false)
continue;
s->mProgress = ADDRESS_LINE;
s->mStartResult = chars - 3 - s->mCurrentStart;
continue;
}
if (isUnicodeSpace(prior) == false) {
s->mProgress = SKIP_TO_SPACE;
continue;
}
s->mNumberCount = 1;
s->mProgress = HOUSE_NUMBER;
s->mStartResult = chars - s->mCurrentStart;
continue;
case SKIP_TO_SPACE:
if (isUnicodeSpace(ch) == false)
continue;
break;
case HOUSE_NUMBER:
if (WTF::isASCIIDigit(ch)) {
if (++s->mNumberCount >= 6)
s->mProgress = SKIP_TO_SPACE;
continue;
}
if (WTF::isASCIIUpper(ch)) { // allow one letter after house number, e.g. 12A SKOLFIELD PL, HARPSWELL, ME 04079
if (WTF::isASCIIDigit(prior) == false)
s->mProgress = SKIP_TO_SPACE;
continue;
}
if (ch == '-') {
if (s->mNumberCount > 0) { // permit 21-23 ELM ST
++s->mNumberCount;
continue;
}
}
s->mNumberCount = 0;
s->mProgress = NUMBER_TRAILING_SPACE;
case NUMBER_TRAILING_SPACE:
if (isUnicodeSpace(ch))
continue;
if (0 && WTF::isASCIIDigit(ch)) {
s->mNumberCount = 1;
s->mProgress = HOUSE_NUMBER;
s->mStartResult = chars - s->mCurrentStart;
continue;
}
if (WTF::isASCIIDigit(ch) == false && WTF::isASCIIUpper(ch) == false)
break;
s->mProgress = ADDRESS_LINE;
case ADDRESS_LINE:
if (WTF::isASCIIAlpha(ch) || ch == '\'' || ch == '-' || ch == '&' || ch == '(' || ch == ')') {
if (++s->mLetterCount > 1) {
s->mNumberWords &= ~(1 << s->mWordCount);
continue;
}
if (s->mNumberCount >= 5)
break;
// FIXME: the test below was added to give up on a non-address, but it
// incorrectly discards addresses where the house number is in one node
// and the street name is in the next; I don't recall what the failing case
// is that suggested this fix.
// if (s->mWordCount == 0 && s->mContinuationNode)
// return FOUND_NONE;
s->mBases[s->mWordCount] = baseChars;
s->mWords[s->mWordCount] = chars - s->mNumberCount;
s->mStarts[s->mWordCount] = s->mCurrentStart;
if (WTF::isASCIILower(ch) && s->mNumberCount == 0)
s->mFirstLower = chars;
s->mNumberCount = 0;
if (WTF::isASCIILower(ch) || (WTF::isASCIIAlpha(ch) == false && ch != '-'))
s->mNumberWords &= ~(1 << s->mWordCount);
s->mUnparsed = true;
continue;
} else if (s->mLetterCount >= MAX_PLACE_NAME_LENGTH) {
break;
} else if (s->mFirstLower != NULL) {
if (s->mCaseInsensitive)
goto resetWord;
size_t length = chars - s->mFirstLower;
if (length > 3)
break;
if (length == 3 && strCharCmp("and" "the", s->mFirstLower, 3, 2) == false)
break;
if (length == 2 && strCharCmp("at" "by" "el" "in" "of", s->mFirstLower, 2, 5) == false)
break;
goto resetWord;
}
if (ch == ',' || ch == '*') { // delimits lines
// asterisk as delimiter: http://www.sa.sc.edu/wellness/members.html
if (++s->mLineCount > 5)
break;
goto lookForState;
}
if (isUnicodeSpace(ch) || prior == '-') {
lookForState:
if (s->mUnparsed == false)
continue;
const UChar* candidate = s->mWords[s->mWordCount];
UChar firstLetter = candidate[0];
if (WTF::isASCIIUpper(firstLetter) == false && WTF::isASCIIDigit(firstLetter) == false)
goto resetWord;
s->mWordCount++;
if ((s->mWordCount == 2 && s->mNumberWords == 3 && WTF::isASCIIDigit(s->mWords[1][1])) || // choose second of 8888 333 Main
(s->mWordCount >= sizeof(s->mWords) / sizeof(s->mWords[0]) - 1)) { // subtract 1 since state names may have two parts
// search for simple number already stored since first potential house # didn't pan out
if (s->mNumberWords == 0)
break;
int shift = 0;
while ((s->mNumberWords & (1 << shift)) == 0)
shift++;
s->mNumberWords >>= ++shift;
if (s->mBases[0] != s->mBases[shift]) // if we're past the original node, bail
break;
memmove(s->mBases, &s->mBases[shift], (sizeof(s->mBases) / sizeof(s->mBases[0]) - shift) * sizeof(s->mBases[0]));
memmove(s->mWords, &s->mWords[shift], (sizeof(s->mWords) / sizeof(s->mWords[0]) - shift) * sizeof(s->mWords[0]));
memmove(s->mStarts, &s->mStarts[shift], (sizeof(s->mStarts) / sizeof(s->mStarts[0]) - shift) * sizeof(s->mStarts[0]));
s->mStartResult = s->mWords[0] - s->mStarts[0];
s->mWordCount -= shift;
// FIXME: need to adjust lineCount to account for discarded delimiters
}
if (s->mWordCount < 4)
goto resetWord;
firstLetter -= 'A';
if (firstLetter > 'W' - 'A')
goto resetWord;
UChar secondLetter = candidate[1];
if (prior == '-')
s->mLetterCount--; // trim trailing dashes, to accept CA-94043
if (s->mLetterCount == 2) {
secondLetter -= 'A';
if (secondLetter > 'Z' - 'A')
goto resetWord;
if ((stateTwoLetter[firstLetter] & 1 << secondLetter) != 0) {
// special case to ignore 'et al'
if (strCharCmp("ET", s->mWords[s->mWordCount - 2], 2, 1) == false) {
s->mStateWord = s->mWordCount - 1;
s->mZipHint = firstIndex[firstLetter] +
bitcount(stateTwoLetter[firstLetter] & ((1 << secondLetter) - 1));
goto foundStateName;
}
}
goto resetWord;
}
s->mStates = longStateNames[firstLetter];
if (s->mStates == NULL)
goto resetWord;
mustBeAllUpper = false;
s->mProgress = STATE_NAME;
unsigned char section = s->mStates[0];
ASSERT(section > 0x80);
s->mSectionLength = section & 0x7f;
candIndex = 1;
secondHalf = false;
s->mStateWord = s->mWordCount - 1;
goto stateName;
}
if (WTF::isASCIIDigit(ch)) {
if (s->mLetterCount == 0) {
if (++s->mNumberCount > 1)
continue;
if (s->mWordCount == 0 && s->mContinuationNode)
return FOUND_NONE;
s->mBases[s->mWordCount] = baseChars;
s->mWords[s->mWordCount] = chars;
s->mStarts[s->mWordCount] = s->mCurrentStart;
s->mNumberWords |= 1 << s->mWordCount;
s->mUnparsed = true;
}
continue;
}
if (ch == '.') { // optionally can follow letters
if (s->mLetterCount == 0)
break;
if (s->mNumberCount > 0)
break;
continue;
}
if (ch == '/') // between numbers (1/2) between words (12 Main / Ste 4d)
goto resetWord;
if (ch == '#') // can precede numbers, allow it to appear randomly
goto resetWord;
if (ch == '"') // sometimes parts of addresses are quoted (FIXME: cite an example here)
continue;
break;
case SECOND_HALF:
if (WTF::isASCIIAlpha(ch)) {
if (s->mLetterCount == 0) {
s->mBases[s->mWordCount] = baseChars;
s->mWords[s->mWordCount] = chars;
s->mStarts[s->mWordCount] = s->mCurrentStart;
s->mWordCount++;
}
s->mLetterCount++;
continue;
}
if (WTF::isASCIIDigit(ch) == false) {
if (s->mLetterCount > 0) {
s->mProgress = STATE_NAME;
candIndex = 0;
secondHalf = true;
goto stateName;
}
continue;
}
s->mProgress = ADDRESS_LINE;
goto resetState;
case STATE_NAME:
stateName:
// pick up length of first section
do {
int stateIndex = 1;
int skip = 0;
int prefix = 0;
bool subStr = false;
do {
unsigned char match = s->mStates[stateIndex];
if (match >= 0x80) {
if (stateIndex == s->mSectionLength)
break;
subStr = true;
// if (skip > 0)
// goto foundStateName;
prefix = candIndex;
skip = match & 0x7f;
match = s->mStates[++stateIndex];
}
UChar candChar = s->mWords[s->mWordCount - 1][candIndex];
if (mustBeAllUpper && WTF::isASCIILower(candChar))
goto skipToNext;
if (match != candChar) {
if (match != WTF::toASCIILower(candChar)) {
skipToNext:
if (subStr == false)
break;
if (stateIndex == s->mSectionLength) {
if (secondHalf) {
s->mProgress = ADDRESS_LINE;
goto resetState;
}
break;
}
stateIndex += skip;
skip = 0;
candIndex = prefix;
continue; // try next substring
}
mustBeAllUpper = true;
}
int nextindex = stateIndex + 1;
if (++candIndex >= s->mLetterCount && s->mStates[nextindex] == ' ') {
s->mProgress = SECOND_HALF;
s->mStates += nextindex;
s->mSectionLength -= nextindex;
goto resetWord;
}
if (nextindex + 1 == s->mSectionLength || skip == 2) {
s->mZipHint = s->mStates[nextindex] - 1;
goto foundStateName;
}
stateIndex += 1;
skip -= 1;
} while (true);
s->mStates += s->mSectionLength;
ASSERT(s->mStates[0] == 0 || (unsigned) s->mStates[0] > 0x80);
s->mSectionLength = s->mStates[0] & 0x7f;
candIndex = 1;
subStr = false;
} while (s->mSectionLength != 0);
s->mProgress = ADDRESS_LINE;
goto resetState;
foundStateName:
s->mEndResult = chars - s->mCurrentStart;
s->mEndWord = s->mWordCount - 1;
s->mProgress = ZIP_CODE;
// a couple of delimiters is an indication that the state name is good
// or, a non-space / non-alpha-digit is also good
s->mZipDelimiter = s->mLineCount > 2 || isUnicodeSpace(ch) == false;
if (WTF::isASCIIDigit(ch))
s->mZipStart = chars;
goto resetState;
case ZIP_CODE:
if (WTF::isASCIIDigit(ch)) {
int count = ++s->mNumberCount;
if (count == 1) {
if (WTF::isASCIIDigit(prior))
++s->mNumberCount;
else
s->mZipStart = chars;
}
if (count <= 9)
continue;
} else if (isUnicodeSpace(ch)) {
if (s->mNumberCount == 0) {
s->mZipDelimiter = true; // two spaces delimit state name
continue;
}
} else if (ch == '-') {
if (s->mNumberCount == 5 && validZip(s->mZipHint, s->mZipStart)) {
s->mNumberCount = 0;
s->mProgress = PLUS_4;
continue;
}
if (s->mNumberCount == 0)
s->mZipDelimiter = true;
} else if (WTF::isASCIIAlpha(ch) == false)
s->mZipDelimiter = true;
else {
if (s->mLetterCount == 0) {
s->mBases[s->mWordCount] = baseChars;
s->mWords[s->mWordCount] = chars;
s->mStarts[s->mWordCount] = s->mCurrentStart;
s->mUnparsed = true;
}
++s->mLetterCount;
}
if (s->mNumberCount == 5 || s->mNumberCount == 9) {
if (validZip(s->mZipHint, s->mZipStart) == false)
goto noZipMatch;
s->mEndResult = chars - s->mCurrentStart;
s->mEndWord = s->mWordCount - 1;
} else if (s->mZipDelimiter == false) {
noZipMatch:
--chars;
s->mProgress = ADDRESS_LINE;
continue;
}
s->mProgress = FIND_STREET;
goto findStreet;
case PLUS_4:
if (WTF::isASCIIDigit(ch)) {
if (++s->mNumberCount <= 4)
continue;
}
if (isUnicodeSpace(ch)) {
if (s->mNumberCount == 0)
continue;
}
if (s->mNumberCount == 4) {
if (WTF::isASCIIAlpha(ch) == false) {
s->mEndResult = chars - s->mCurrentStart;
s->mEndWord = s->mWordCount - 1;
}
} else if (s->mNumberCount != 0)
break;
s->mProgress = FIND_STREET;
case FIND_STREET:
findStreet:
retryState = false;
for (int wordsIndex = s->mStateWord - 1; wordsIndex >= 0; --wordsIndex) {
const UChar* test = s->mWords[wordsIndex];
UChar letter = test[0];
letter -= 'A';
if (letter > 'X' - 'A')
continue;
const char* names = longStreetNames[letter];
if (names == NULL)
continue;
int offset;
while ((offset = *names++) != 0) {
int testIndex = 1;
bool abbr = false;
for (int idx = 0; idx < offset; idx++) {
char nameLetter = names[idx];
char testUpper = WTF::toASCIIUpper(test[testIndex]);
if (nameLetter == '*') {
if (testUpper == 'S')
testIndex++;
break;
}
bool fullOnly = WTF::isASCIILower(nameLetter);
nameLetter = WTF::toASCIIUpper(nameLetter);
if (testUpper == nameLetter) {
if (abbr && fullOnly)
goto nextTest;
testIndex++;
continue;
}
if (fullOnly == false)
goto nextTest;
abbr = true;
}
letter = test[testIndex];
if (WTF::isASCIIAlpha(letter) == false && WTF::isASCIIDigit(letter) == false) {
if (s->mNumberWords != 0) {
int shift = 0;
int wordReduction = -1;
do {
while ((s->mNumberWords & (1 << shift)) == 0)
shift++;
if (shift > wordsIndex)
break;
wordReduction = shift;
} while (s->mNumberWords >> ++shift != 0);
if (wordReduction >= 0) {
if (s->mContinuationNode) {
if (retryState)
break;
return FOUND_NONE;
}
s->mStartResult = s->mWords[wordReduction] - s->mStarts[wordReduction];
}
}
if (wordsIndex != s->mStateWord - 1)
return FOUND_COMPLETE;
retryState = true;
}
nextTest:
names += offset;
}
}
if (retryState) {
s->mProgress = ADDRESS_LINE;
s->mStates = NULL;
continue;
}
if (s->mNumberWords != 0) {
unsigned shift = 0;
while ((s->mNumberWords & (1 << shift)) == 0)
shift++;
s->mNumberWords >>= ++shift;
if (s->mBases[0] != s->mBases[shift])
return FOUND_NONE;
memmove(s->mBases, &s->mBases[shift], (sizeof(s->mBases) / sizeof(s->mBases[0]) - shift) * sizeof(s->mBases[0]));
memmove(s->mWords, &s->mWords[shift], (sizeof(s->mWords) / sizeof(s->mWords[0]) - shift) * sizeof(s->mWords[0]));
memmove(s->mStarts, &s->mStarts[shift], (sizeof(s->mStarts) / sizeof(s->mStarts[0]) - shift) * sizeof(s->mStarts[0]));
s->mStartResult = s->mWords[0] - s->mStarts[0];
s->mWordCount -= shift;
s->mProgress = ADDRESS_LINE;
--chars;
continue;
}
break;
}
if (s->mContinuationNode)
return FOUND_NONE;
s->mProgress = NO_ADDRESS;
s->mWordCount = s->mLineCount = 0;
s->mNumberWords = 0;
resetState:
s->mStates = NULL;
resetWord:
s->mNumberCount = s->mLetterCount = 0;
s->mFirstLower = NULL;
s->mUnparsed = false;
}
s->mCurrent = ch;
return s->mProgress == NO_ADDRESS ? FOUND_NONE : FOUND_PARTIAL;
}
// Recogize common email patterns only. Currently has lots of state, walks text forwards and backwards -- will be
// a real challenge to adapt to walk text across multiple nodes, I imagine
// FIXME: it's too hard for the caller to call these incrementally -- it's probably best for this to
// either walk the node tree directly or make a callout to get the next or previous node, if there is one
// walking directly will avoid adding logic in caller to track the multiple partial or full nodes that compose this
// text pattern.
CacheBuilder::FoundState CacheBuilder::FindPartialEMail(const UChar* chars, unsigned length,
FindState* s)
{
// the following tables were generated by tests/browser/focusNavigation/BrowserDebug.cpp
// hand-edit at your own risk
static const int domainTwoLetter[] = {
0x02df797c, // a followed by: [cdefgilmnoqrstuwxz]
0x036e73fb, // b followed by: [abdefghijmnorstvwyz]
0x03b67ded, // c followed by: [acdfghiklmnorsuvxyz]
0x02005610, // d followed by: [ejkmoz]
0x001e00d4, // e followed by: [ceghrstu]
0x00025700, // f followed by: [ijkmor]
0x015fb9fb, // g followed by: [abdefghilmnpqrstuwy]
0x001a3400, // h followed by: [kmnrtu]
0x000f7818, // i followed by: [delmnoqrst]
0x0000d010, // j followed by: [emop]
0x0342b1d0, // k followed by: [eghimnprwyz]
0x013e0507, // l followed by: [abcikrstuvy]
0x03fffccd, // m followed by: [acdghklmnopqrstuvwxyz]
0x0212c975, // n followed by: [acefgilopruz]
0x00001000, // o followed by: [m]
0x014e3cf1, // p followed by: [aefghklmnrstwy]
0x00000001, // q followed by: [a]
0x00504010, // r followed by: [eouw]
0x032a7fdf, // s followed by: [abcdeghijklmnortvyz]
0x026afeec, // t followed by: [cdfghjklmnoprtvwz]
0x03041441, // u followed by: [agkmsyz]
0x00102155, // v followed by: [aceginu]
0x00040020, // w followed by: [fs]
0x00000000, // x
0x00180010, // y followed by: [etu]
0x00401001, // z followed by: [amw]
};
static char const* const longDomainNames[] = {
"\x03" "ero" "\x03" "rpa", // aero, arpa
"\x02" "iz", // biz
"\x02" "at" "\x02" "om" "\x03" "oop", // cat, com, coop
NULL, // d
"\x02" "du", // edu
NULL, // f
"\x02" "ov", // gov
NULL, // h
"\x03" "nfo" "\x02" "nt", // info, int
"\x03" "obs", // jobs
NULL, // k
NULL, // l
"\x02" "il" "\x03" "obi" "\x05" "useum", // mil, mobi, museum
"\x03" "ame" "\x02" "et", // name, net
"\x02" "rg", // , org
"\x02" "ro", // pro
NULL, // q
NULL, // r
NULL, // s
"\x05" "ravel", // travel
NULL, // u
NULL, // v
NULL, // w
NULL, // x
NULL, // y
NULL, // z
};
const UChar* start = chars;
const UChar* end = chars + length;
while (chars < end) {
UChar ch = *chars++;
if (ch != '@')
continue;
const UChar* atLocation = chars - 1;
// search for domain
ch = *chars++ | 0x20; // convert uppercase to lower
if (ch < 'a' || ch > 'z')
continue;
while (chars < end) {
ch = *chars++;
if (IsDomainChar(ch) == false)
goto nextAt;
if (ch != '.')
continue;
UChar firstLetter = *chars++ | 0x20; // first letter of the domain
if (chars >= end)
return FOUND_NONE; // only one letter; must be at least two
firstLetter -= 'a';
if (firstLetter > 'z' - 'a')
continue; // non-letter followed '.'
int secondLetterMask = domainTwoLetter[firstLetter];
ch = *chars | 0x20; // second letter of the domain
ch -= 'a';
if (ch >= 'z' - 'a')
continue;
bool secondMatch = (secondLetterMask & 1 << ch) != 0;
const char* wordMatch = longDomainNames[firstLetter];
int wordIndex = 0;
while (wordMatch != NULL) {
int len = *wordMatch++;
char match;
do {
match = wordMatch[wordIndex];
if (match < 0x20)
goto foundDomainStart;
if (chars[wordIndex] != match)
break;
wordIndex++;
} while (true);
wordMatch += len;
if (*wordMatch == '\0')
break;
wordIndex = 0;
}
if (secondMatch) {
wordIndex = 1;
foundDomainStart:
chars += wordIndex;
if (chars < end) {
ch = *chars;
if (ch != '.') {
if (IsDomainChar(ch))
goto nextDot;
} else if (chars + 1 < end && IsDomainChar(chars[1]))
goto nextDot;
}
// found domain. Search backwards from '@' for beginning of email address
s->mEndResult = chars - start;
chars = atLocation;
if (chars <= start)
goto nextAt;
ch = *--chars;
if (ch == '.')
goto nextAt; // mailbox can't end in period
do {
if (IsMailboxChar(ch) == false) {
chars++;
break;
}
if (chars == start)
break;
ch = *--chars;
} while (true);
UChar firstChar = *chars;
if (firstChar == '.' || firstChar == '@') // mailbox can't start with period or be empty
goto nextAt;
s->mStartResult = chars - start;
return FOUND_COMPLETE;
}
nextDot:
;
}
nextAt:
chars = atLocation + 1;
}
return FOUND_NONE;
}
#define PHONE_PATTERN "(200) /-.\\ 100 -. 0000" // poor man's regex: parens optional, any one of punct, digit smallest allowed
CacheBuilder::FoundState CacheBuilder::FindPartialNumber(const UChar* chars, unsigned length,
FindState* s)
{
char* pattern = s->mPattern;
UChar* store = s->mStorePtr;
const UChar* start = chars;
const UChar* end = chars + length;
const UChar* lastDigit = NULL;
do {
bool initialized = s->mInitialized;
while (chars < end) {
if (initialized == false) {
s->mBackTwo = s->mBackOne;
s->mBackOne = s->mCurrent;
}
UChar ch = s->mCurrent = *chars;
do {
char patternChar = *pattern;
switch (patternChar) {
case '2':
if (initialized == false) {
s->mStartResult = chars - start;
initialized = true;
}
case '0':
case '1':
if (ch < patternChar || ch > '9')
goto resetPattern;
*store++ = ch;
pattern++;
lastDigit = chars;
goto nextChar;
case '\0':
if (WTF::isASCIIDigit(ch) == false) {
*store = '\0';
goto checkMatch;
}
goto resetPattern;
case ' ':
if (ch == patternChar)
goto nextChar;
break;
case '(':
if (ch == patternChar) {
s->mStartResult = chars - start;
initialized = true;
s->mOpenParen = true;
}
goto commonPunctuation;
case ')':
if ((ch == patternChar) ^ s->mOpenParen)
goto resetPattern;
default:
commonPunctuation:
if (ch == patternChar) {
pattern++;
goto nextChar;
}
}
} while (++pattern); // never false
nextChar:
chars++;
}
break;
resetPattern:
if (s->mContinuationNode)
return FOUND_NONE;
FindResetNumber(s);
pattern = s->mPattern;
store = s->mStorePtr;
} while (++chars < end);
checkMatch:
if (WTF::isASCIIDigit(s->mBackOne != '1' ? s->mBackOne : s->mBackTwo))
return FOUND_NONE;
*store = '\0';
s->mStorePtr = store;
s->mPattern = pattern;
s->mEndResult = lastDigit - start + 1;
char pState = pattern[0];
return pState == '\0' ? FOUND_COMPLETE : pState == '(' || (WTF::isASCIIDigit(pState) && WTF::isASCIIDigit(pattern[-1])) ?
FOUND_NONE : FOUND_PARTIAL;
}
CacheBuilder::FoundState CacheBuilder::FindPhoneNumber(const UChar* chars, unsigned length,
int* start, int* end)
{
FindState state;
FindReset(&state);
FoundState result = FindPartialNumber(chars, length, &state);
*start = state.mStartResult;
*end = state.mEndResult;
return result;
}
void CacheBuilder::FindReset(FindState* state)
{
memset(state, 0, sizeof(FindState));
state->mCurrent = ' ';
FindResetNumber(state);
}
void CacheBuilder::FindResetNumber(FindState* state)
{
state->mOpenParen = false;
state->mPattern = (char*) PHONE_PATTERN;
state->mStorePtr = state->mStore;
}
IntRect CacheBuilder::getAreaRect(const HTMLAreaElement* area)
{
Node* node = area->document();
while ((node = node->traverseNextNode()) != NULL) {
RenderObject* renderer = node->renderer();
if (renderer && renderer->isRenderImage()) {
RenderImage* image = static_cast<RenderImage*>(renderer);
HTMLMapElement* map = image->imageMap();
if (map) {
Node* n;
for (n = map->firstChild(); n;
n = n->traverseNextNode(map)) {
if (n == area) {
if (area->isDefault())
return image->absoluteBoundingBoxRect();
return area->getRect(image);
}
}
}
}
}
return IntRect();
}
void CacheBuilder::GetGlobalOffset(Node* node, int* x, int * y)
{
GetGlobalOffset(node->document()->frame(), x, y);
}
void CacheBuilder::GetGlobalOffset(Frame* frame, int* x, int* y)
{
// TIMER_PROBE(__FUNCTION__);
ASSERT(x);
ASSERT(y);
*x = 0;
*y = 0;
if (!frame->view())
return;
Frame* parent;
while ((parent = frame->tree()->parent()) != NULL) {
const WebCore::IntRect& rect = frame->view()->platformWidget()->getBounds();
*x += rect.x();
*y += rect.y();
frame = parent;
}
// TIMER_PROBE_END();
}
Frame* CacheBuilder::HasFrame(Node* node)
{
RenderObject* renderer = node->renderer();
if (renderer == NULL)
return NULL;
if (renderer->isWidget() == false)
return NULL;
Widget* widget = static_cast<RenderWidget*>(renderer)->widget();
if (widget == NULL)
return NULL;
if (widget->isFrameView() == false)
return NULL;
return static_cast<FrameView*>(widget)->frame();
}
bool CacheBuilder::HasOverOrOut(Node* node)
{
// eventNames are thread-local data, I avoid using 'static' variable here.
AtomicString eventTypes[2] = {
eventNames().mouseoverEvent,
eventNames().mouseoutEvent
};
return NodeHasEventListeners(node, eventTypes, 2);
}
bool CacheBuilder::HasTriggerEvent(Node* node)
{
AtomicString eventTypes[5] = {
eventNames().clickEvent,
eventNames().mousedownEvent,
eventNames().mouseupEvent,
eventNames().keydownEvent,
eventNames().keyupEvent
};
return NodeHasEventListeners(node, eventTypes, 5);
}
// #define EMAIL_PATTERN "x@y.d" // where 'x' is letters, numbers, and '-', '.', '_' ; 'y' is 'x' without the underscore, and 'd' is a valid domain
// - 0x2D . 0x2E 0-9 0x30-39 A-Z 0x41-5A _ 0x5F a-z 0x61-7A
bool CacheBuilder::IsDomainChar(UChar ch)
{
static const unsigned body[] = {0x03ff6000, 0x07fffffe, 0x07fffffe}; // 0-9 . - A-Z a-z
ch -= 0x20;
if (ch > 'z' - 0x20)
return false;
return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0;
}
bool CacheBuilder::isFocusableText(NodeWalk* walk, bool more, Node* node,
CachedNodeType* type, String* exported) const
{
Text* textNode = static_cast<Text*>(node);
StringImpl* string = textNode->string();
const UChar* baseChars = string->characters();
// const UChar* originalBase = baseChars;
int length = string->length();
int index = 0;
while (index < length && isUnicodeSpace(baseChars[index]))
index++;
if (index >= length)
return false;
if (more == false) {
walk->mStart = 0;
walk->mEnd = 0;
walk->mFinalNode = node;
walk->mLastInline = NULL;
}
// starting with this node, search forward for email, phone number, and address
// if any of the three is found, track it so that the remaining can be looked for later
FoundState state = FOUND_NONE;
RenderText* renderer = (RenderText*) node->renderer();
bool foundBetter = false;
InlineTextBox* baseInline = walk->mLastInline != NULL ? walk->mLastInline :
renderer->firstTextBox();
if (baseInline == NULL)
return false;
int start = walk->mEnd;
InlineTextBox* saveInline;
int baseStart, firstStart = start;
saveInline = baseInline;
baseStart = start;
for (CachedNodeType checkType = ADDRESS_CACHEDNODETYPE;
checkType <= PHONE_CACHEDNODETYPE;
checkType = (CachedNodeType) (checkType << 1))
{
if ((checkType & mAllowableTypes) == 0)
continue;
InlineTextBox* inlineTextBox = baseInline;
FindState findState;
FindReset(&findState);
start = baseStart;
if (checkType == ADDRESS_CACHEDNODETYPE) {
findState.mBases[0] = baseChars;
findState.mWords[0] = baseChars + start;
findState.mStarts[0] = baseChars + start;
}
Node* lastPartialNode = NULL;
int lastPartialEnd = -1;
bool lastPartialMore = false;
bool firstPartial = true;
InlineTextBox* lastPartialInline = NULL;
do {
do {
const UChar* chars = baseChars + start;
length = inlineTextBox == NULL ? 0 :
inlineTextBox->end() - start + 1;
bool wasInitialized = findState.mInitialized;
switch (checkType) {
case ADDRESS_CACHEDNODETYPE:
state = FindPartialAddress(baseChars, chars, length, &findState);
break;
case EMAIL_CACHEDNODETYPE:
state = FindPartialEMail(chars, length, &findState);
break;
case PHONE_CACHEDNODETYPE:
state = FindPartialNumber(chars, length, &findState);
break;
default:
ASSERT(0);
}
findState.mInitialized = state != FOUND_NONE;
if (wasInitialized != findState.mInitialized)
firstStart = start;
if (state == FOUND_PARTIAL) {
lastPartialNode = node;
lastPartialEnd = findState.mEndResult + start;
lastPartialMore = firstPartial &&
lastPartialEnd < (int) string->length();
firstPartial = false;
lastPartialInline = inlineTextBox;
findState.mContinuationNode = true;
} else if (state == FOUND_COMPLETE) {
if (foundBetter == false || walk->mStart > findState.mStartResult) {
walk->mStart = findState.mStartResult + firstStart;
if (findState.mEndResult > 0) {
walk->mFinalNode = node;
walk->mEnd = findState.mEndResult + start;
walk->mMore = node == textNode &&
walk->mEnd < (int) string->length();
walk->mLastInline = inlineTextBox;
} else {
walk->mFinalNode = lastPartialNode;
walk->mEnd = lastPartialEnd;
walk->mMore = lastPartialMore;
walk->mLastInline = lastPartialInline;
}
*type = checkType;
if (checkType == PHONE_CACHEDNODETYPE) {
const UChar* store = findState.mStore;
*exported = String(store);
} else {
Node* temp = textNode;
length = 1;
start = walk->mStart;
exported->truncate(0);
do {
Text* tempText = static_cast<Text*>(temp);
StringImpl* string = tempText->string();
int end = tempText == walk->mFinalNode ?
walk->mEnd : string->length();
exported->append(String(string->substring(
start, end - start)));
ASSERT(end > start);
length += end - start + 1;
if (temp == walk->mFinalNode)
break;
start = 0;
do {
temp = temp->traverseNextNode();
ASSERT(temp);
} while (temp->isTextNode() == false);
// add a space in between text nodes to avoid
// words collapsing together
exported->append(" ");
} while (true);
}
foundBetter = true;
}
goto tryNextCheckType;
} else if (findState.mContinuationNode)
break;
if (inlineTextBox == NULL)
break;
inlineTextBox = inlineTextBox->nextTextBox();
if (inlineTextBox == NULL)
break;
start = inlineTextBox->start();
if (state == FOUND_PARTIAL && node == textNode)
findState.mContinuationNode = false;
} while (true);
if (state == FOUND_NONE)
break;
// search for next text node, if any
Text* nextNode;
do {
do {
do {
node = node->traverseNextNode();
if (node == NULL || node->hasTagName(HTMLNames::aTag)) {
if (state == FOUND_PARTIAL &&
checkType == ADDRESS_CACHEDNODETYPE &&
findState.mProgress == ZIP_CODE &&
findState.mNumberCount == 0) {
baseChars = NULL;
inlineTextBox = NULL;
start = 0;
findState.mProgress = FIND_STREET;
goto finalNode;
}
goto tryNextCheckType;
}
} while (node->isTextNode() == false);
nextNode = static_cast<Text*>(node);
renderer = (RenderText*) nextNode->renderer();
} while (renderer == NULL);
baseInline = renderer->firstTextBox();
} while (baseInline == NULL);
string = nextNode->string();
baseChars = string->characters();
inlineTextBox = baseInline;
start = inlineTextBox->start();
finalNode:
findState.mEndResult = 0;
} while (true);
tryNextCheckType:
node = textNode;
baseInline = saveInline;
string = textNode->string();
baseChars = string->characters();
}
if (foundBetter) {
CachedNodeType temp = *type;
switch (temp) {
case ADDRESS_CACHEDNODETYPE: {
static const char geoString[] = "geo:0,0?q=";
exported->insert(String(geoString), 0);
int index = sizeof(geoString) - 1;
String escapedComma("%2C");
while ((index = exported->find(',', index)) >= 0)
exported->replace(index, 1, escapedComma);
} break;
case EMAIL_CACHEDNODETYPE:
exported->insert(WebCore::String("mailto:"), 0);
break;
case PHONE_CACHEDNODETYPE:
exported->insert(WebCore::String("tel:"), 0);
break;
default:
break;
}
return true;
}
noTextMatch:
walk->reset();
return false;
}
bool CacheBuilder::IsMailboxChar(UChar ch)
{
static const unsigned body[] = {0x03ff6000, 0x87fffffe, 0x07fffffe}; // 0-9 . - A-Z _ a-z
ch -= 0x20;
if (ch > 'z' - 0x20)
return false;
return (body[ch >> 5] & 1 << (ch & 0x1f)) != 0;
}
bool CacheBuilder::setData(CachedFrame* cachedFrame)
{
Frame* frame = FrameAnd(this);
Document* doc = frame->document();
if (doc == NULL)
return false;
RenderObject* renderer = doc->renderer();
if (renderer == NULL)
return false;
RenderLayer* layer = renderer->enclosingLayer();
if (layer == NULL)
return false;
if (layer->width() == 0 || layer->height() == 0)
return false;
if (!frame->view())
return false;
int x, y;
GetGlobalOffset(frame, &x, &y);
WebCore::IntRect viewBounds = frame->view()->platformWidget()->getBounds();
if ((x | y) != 0)
viewBounds.setLocation(WebCore::IntPoint(x, y));
cachedFrame->setLocalViewBounds(viewBounds);
cachedFrame->setContentsSize(layer->width(), layer->height());
if (cachedFrame->childCount() == 0)
return true;
CachedFrame* lastCachedFrame = cachedFrame->lastChild();
cachedFrame = cachedFrame->firstChild();
do {
CacheBuilder* cacheBuilder = Builder((Frame* )cachedFrame->framePointer());
cacheBuilder->setData(cachedFrame);
} while (cachedFrame++ != lastCachedFrame);
return true;
}
bool CacheBuilder::validNode(Frame* startFrame, void* matchFrame,
void* matchNode)
{
if (matchFrame == startFrame) {
if (matchNode == NULL)
return true;
Node* node = startFrame->document();
while (node != NULL) {
if (node == matchNode) {
const IntRect& rect = node->hasTagName(HTMLNames::areaTag) ?
getAreaRect(static_cast<HTMLAreaElement*>(node)) : node->getRect();
// Consider nodes with empty rects that are not at the origin
// to be valid, since news.google.com has valid nodes like this
if (rect.x() == 0 && rect.y() == 0 && rect.isEmpty())
return false;
return true;
}
node = node->traverseNextNode();
}
DBG_NAV_LOGD("frame=%p valid node=%p invalid\n", matchFrame, matchNode);
return false;
}
Frame* child = startFrame->tree()->firstChild();
while (child) {
bool result = validNode(child, matchFrame, matchNode);
if (result)
return result;
child = child->tree()->nextSibling();
}
#if DEBUG_NAV_UI
if (startFrame->tree()->parent() == NULL)
DBG_NAV_LOGD("frame=%p node=%p false\n", matchFrame, matchNode);
#endif
return false;
}
static int Area(const IntRect& rect)
{
return rect.width() * rect.height();
}
bool CacheBuilder::AddPartRect(IntRect& bounds, int x, int y,
WTF::Vector<IntRect>* result, IntRect* focusBounds)
{
if (bounds.isEmpty())
return true;
bounds.move(x, y);
if (bounds.right() <= 0 || bounds.bottom() <= 0)
return true;
IntRect* work = result->begin() - 1;
IntRect* end = result->end();
while (++work < end) {
if (work->contains(bounds))
return true;
if (bounds.contains(*work)) {
*work = bounds;
focusBounds->unite(bounds);
return true;
}
if ((bounds.x() != work->x() || bounds.width() != work->width()) &&
(bounds.y() != work->y() || bounds.height() != work->height()))
continue;
IntRect test = *work;
test.unite(bounds);
if (Area(test) > Area(*work) + Area(bounds))
continue;
*work = test;
focusBounds->unite(bounds);
return true;
}
if (result->size() >= MAXIMUM_FOCUS_RING_COUNT)
return false;
result->append(bounds);
if (focusBounds->isEmpty())
*focusBounds = bounds;
else
focusBounds->unite(bounds);
return true;
}
bool CacheBuilder::ConstructPartRects(Node* node, const IntRect& bounds,
IntRect* focusBounds, int x, int y, WTF::Vector<IntRect>* result)
{
WTF::Vector<ClipColumnTracker> clipTracker(1);
ClipColumnTracker* baseTracker = clipTracker.data(); // sentinel
bzero(baseTracker, sizeof(ClipColumnTracker));
if (node->hasChildNodes() && node->hasTagName(HTMLNames::buttonTag) == false
&& node->hasTagName(HTMLNames::selectTag) == false) {
// collect all text rects from first to last child
Node* test = node->firstChild();
Node* last = NULL;
Node* prior = node;
while ((prior = prior->lastChild()) != NULL)
last = prior;
ASSERT(last != NULL);
bool nodeIsAnchor = node->hasTagName(HTMLNames::aTag);
do {
do {
const ClipColumnTracker* lastClip = &clipTracker.last();
if (test != lastClip->mLastChild)
break;
clipTracker.removeLast();
} while (true);
RenderObject* renderer = test->renderer();
if (renderer == NULL)
continue;
EVisibility vis = renderer->style()->visibility();
if (vis == HIDDEN)
continue;
if (test->isTextNode()) {
RenderText* renderText = (RenderText*) renderer;
InlineTextBox *textBox = renderText->firstTextBox();
if (textBox == NULL)
continue;
bool hasClip = renderer->hasOverflowClip();
size_t clipIndex = clipTracker.size();
IntRect clipBounds = IntRect(0, 0, INT_MAX, INT_MAX);
if (hasClip || --clipIndex > 0) {
clipBounds = hasClip ? renderer->absoluteBoundingBoxRect() :
clipTracker.at(clipIndex).mBounds; // x, y fixup done by ConstructTextRect
}
if (ConstructTextRect((Text*) test, textBox, 0, INT_MAX,
x, y, focusBounds, clipBounds, result) == false) {
return false;
}
continue;
}
if (test->hasTagName(HTMLNames::imgTag)) {
IntRect bounds = test->getRect();
if (AddPartRect(bounds, x, y, result, focusBounds) == false)
return false;
continue;
}
if (renderer->hasOverflowClip() == false) {
if (nodeIsAnchor && test->hasTagName(HTMLNames::divTag)) {
IntRect bounds = renderer->absoluteBoundingBoxRect(); // x, y fixup done by AddPartRect
int left = bounds.x() + ((RenderBox*)renderer)->paddingLeft()
+ ((RenderBox*)renderer)->borderLeft();
int top = bounds.y() + ((RenderBox*)renderer)->paddingTop()
+ ((RenderBox*)renderer)->borderTop();
int right = bounds.right() - ((RenderBox*)renderer)->paddingRight()
- ((RenderBox*)renderer)->borderRight();
int bottom = bounds.bottom() - ((RenderBox*)renderer)->paddingBottom()
- ((RenderBox*)renderer)->borderBottom();
if (left >= right || top >= bottom)
continue;
bounds = IntRect(left, top, right - left, bottom - top);
if (AddPartRect(bounds, x, y, result, focusBounds) == false)
return false;
}
continue;
}
Node* lastChild = test->lastChild();
if (lastChild == NULL)
continue;
clipTracker.grow(clipTracker.size() + 1);
ClipColumnTracker& clip = clipTracker.last();
clip.mBounds = renderer->absoluteBoundingBoxRect(); // x, y fixup done by ConstructTextRect
clip.mLastChild = OneAfter(lastChild);
clip.mNode = test;
} while (test != last && (test = test->traverseNextNode()) != NULL);
}
if (result->size() == 0 || focusBounds->width() < MINIMUM_FOCUSABLE_WIDTH
|| focusBounds->height() < MINIMUM_FOCUSABLE_HEIGHT) {
if (bounds.width() < MINIMUM_FOCUSABLE_WIDTH)
return false;
if (bounds.height() < MINIMUM_FOCUSABLE_HEIGHT)
return false;
result->append(bounds);
*focusBounds = bounds;
}
return true;
}
static inline bool isNotSpace(UChar c)
{
return c <= 0xA0 ? isUnicodeSpace(c) == false :
WTF::Unicode::direction(c) != WTF::Unicode::WhiteSpaceNeutral;
}
bool CacheBuilder::ConstructTextRect(Text* textNode,
InlineTextBox* textBox, int start, int relEnd, int x, int y,
IntRect* focusBounds, const IntRect& clipBounds, WTF::Vector<IntRect>* result)
{
RenderText* renderText = (RenderText*) textNode->renderer();
EVisibility vis = renderText->style()->visibility();
StringImpl* string = textNode->string();
const UChar* chars = string->characters();
FloatPoint pt = renderText->localToAbsolute();
do {
int textBoxStart = textBox->start();
int textBoxEnd = textBoxStart + textBox->len();
if (textBoxEnd <= start)
continue;
if (textBoxEnd > relEnd)
textBoxEnd = relEnd;
IntRect bounds = textBox->selectionRect((int) pt.x(), (int) pt.y(),
start, textBoxEnd);
bounds.intersect(clipBounds);
if (bounds.isEmpty())
continue;
bool drawable = false;
for (int index = start; index < textBoxEnd; index++)
if ((drawable |= isNotSpace(chars[index])) != false)
break;
if (drawable && vis != HIDDEN) {
if (AddPartRect(bounds, x, y, result, focusBounds) == false)
return false;
}
if (textBoxEnd == relEnd)
break;
} while ((textBox = textBox->nextTextBox()) != NULL);
return true;
}
bool CacheBuilder::ConstructTextRects(Text* node, int start,
Text* last, int end, int x, int y, IntRect* focusBounds,
const IntRect& clipBounds, WTF::Vector<IntRect>* result)
{
result->clear();
*focusBounds = IntRect(0, 0, 0, 0);
do {
RenderText* renderText = (RenderText*) node->renderer();
int relEnd = node == last ? end : renderText->textLength();
InlineTextBox *textBox = renderText->firstTextBox();
if (textBox != NULL) {
do {
if ((int) textBox->end() >= start)
break;
} while ((textBox = textBox->nextTextBox()) != NULL);
if (textBox && ConstructTextRect(node, textBox, start, relEnd,
x, y, focusBounds, clipBounds, result) == false)
return false;
}
start = 0;
do {
if (node == last)
return true;
node = (Text*) node->traverseNextNode();
ASSERT(node != NULL);
} while (node->isTextNode() == false || node->renderer() == NULL);
} while (true);
}
}