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