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