extract selected text from the picture

The deleted code extracted the selected text from the WebKit DOM
by looking for text in the render tree that matched the selection
region. This has never worked well.

The replacement approach matches the glyphs in the picture instead.

- WebViewCore.*
Remove getSelection() and supporting routines. Part of the deleted
code looked for punctuation between segments to add space characters
that might not be present in the markup. There's no equivalent in
the replacement code; it uses spacial gaps to detect the need to
add extra spaces.

- SelectText.*
Match the text to the selected region and convert the glyph to
unicode. The tricky part is that spaces need to be inserted into
the string when there are gaps in the text.

- WebView.cpp
Return the selection as a string to the java caller instead
of a region.

To convert the glyphs into text, a companion change was made to
external/skia. To update the UI thread/webkit thread messaging, a
companion change was also made to frameworks/base.

Fixes http://b/2166748

5 files changed, 101 insertions, 230 deletions

diff --git a/WebKit/android/jni/WebViewCore.cpp b/WebKit/android/jni/WebViewCore.cpp
index 7d58b5f..7e35229 100644
--- a/WebKit/android/jni/WebViewCore.cpp
+++ b/WebKit/android/jni/WebViewCore.cpp
@@ -1516,209 +1516,6 @@ void WebViewCore::moveMouse(WebCore::Frame* frame, int x, int y)
     updateCacheOnNodeChange();
 }
 
-static int findTextBoxIndex(WebCore::Node* node, const WebCore::IntPoint& pt)
-{
-    if (!node->isTextNode()) {
-        DBG_NAV_LOGD("node=%p pt=(%d,%d) isText=false", node, pt.x(), pt.y());
-        return -2; // error
-    }
-    WebCore::RenderText* renderText = (WebCore::RenderText*) node->renderer();
-    if (!renderText) {
-        DBG_NAV_LOGD("node=%p pt=(%d,%d) renderText=0", node, pt.x(), pt.y());
-        return -3; // error
-    }
-    FloatPoint absPt = renderText->localToAbsolute();
-    WebCore::InlineTextBox *textBox = renderText->firstTextBox();
-    int globalX, globalY;
-    CacheBuilder::GetGlobalOffset(node, &globalX, &globalY);
-    int x = pt.x() - globalX;
-    int y = pt.y() - globalY;
-    do {
-        int textBoxStart = textBox->start();
-        int textBoxEnd = textBoxStart + textBox->len();
-        if (textBoxEnd <= textBoxStart) {
-            DBG_NAV_LOGD("textBoxStart=%d <= textBoxEnd=%d", textBoxStart,
-                textBoxEnd);
-            continue;
-        }
-        WebCore::IntRect bounds = textBox->selectionRect(absPt.x(), absPt.y(),
-            textBoxStart, textBoxEnd);
-        if (!bounds.contains(x, y)) {
-            DBG_NAV_LOGD("[absPt=(%g,%g) textBoxStart=%d textBoxEnd=%d]"
-                " !contains (x=%d, y=%d)",
-                absPt.x(), absPt.y(), textBoxStart, textBoxEnd, x, y);
-            continue;
-        }
-        int offset = textBox->offsetForPosition(x - absPt.x());
-#if DEBUG_NAV_UI
-        int prior = offset > 0 ? textBox->positionForOffset(offset - 1) : -1;
-        int current = textBox->positionForOffset(offset);
-        int next = textBox->positionForOffset(offset + 1);
-        DBG_NAV_LOGD("offset=%d pt.x=%d globalX=%d renderX=%g x=%d "
-            "textBox->x()=%d textBox->start()=%d prior=%d current=%d next=%d",
-            offset, pt.x(), globalX, absPt.x(), x,
-            textBox->x(), textBox->start(), prior, current, next
-            );
-#endif
-        return textBox->start() + offset;
-    } while ((textBox = textBox->nextTextBox()));
-    return -1; // couldn't find point, may have walked off end
-}
-
-static inline bool isPunctuation(UChar c)
-{
-    return WTF::Unicode::category(c) & (0
-        | WTF::Unicode::Punctuation_Dash
-        | WTF::Unicode::Punctuation_Open
-        | WTF::Unicode::Punctuation_Close
-        | WTF::Unicode::Punctuation_Connector
-        | WTF::Unicode::Punctuation_Other
-        | WTF::Unicode::Punctuation_InitialQuote
-        | WTF::Unicode::Punctuation_FinalQuote
-    );
-}
-
-static int centerX(const SkIRect& rect)
-{
-    return (rect.fLeft + rect.fRight) >> 1;
-}
-
-static int centerY(const SkIRect& rect)
-{
-    return (rect.fTop + rect.fBottom) >> 1;
-}
-
-static void ShowNode(Node* node)
-{
-#if DEBUG_NAV_UI
-    WebCore::Node* match = node->document();
-    int index = 1;
-    while (match != node && (match = match->traverseNextNode()))
-        index++;
-    if (match != node)
-        index = -1;
-    const char* name = "text";
-    WebCore::CString cstr;
-    if (!node->isTextNode()) {
-        cstr = node->localName().string().utf8();
-        name = cstr.data();
-    }
-    node->getRect();
-    const WebCore::IntRect& b = node->getRect();
-    DBG_NAV_LOGD("%s %p (%d) (%d,%d,w=%d,h=%d)", name, node, index,
-        b.x(), b.y(), b.width(), b.height());
-#endif
-}
-
-static WebCore::Node* ChildIsTextNode(WebCore::Node* node)
-{
-    WebCore::Node* child = node;
-    while (child && !child->isTextNode()) {
-        ShowNode(child);
-        child = child->traverseNextNode(node);
-    }
-    return child;
-}
-
-WebCore::String WebViewCore::getSelection(SkRegion* selRgn)
-{
-    SkRegion::Iterator iter(*selRgn);
-    // FIXME: switch this to use StringBuilder instead
-    WebCore::String result;
-    WebCore::Node* lastStartNode = 0;
-    int lastStartEnd = -1;
-    UChar lastChar = 0xffff;
-    for (; !iter.done(); iter.next()) {
-        const SkIRect& rect = iter.rect();
-        DBG_NAV_LOGD("rect=(%d, %d, %d, %d)", rect.fLeft, rect.fTop,
-            rect.fRight, rect.fBottom);
-        int cy = centerY(rect);
-        WebCore::IntPoint startPt, endPt;
-        WebCore::Node* node = NULL, * endNode = NULL;
-        for (int top = rect.fTop + 2; top != cy; top = cy) {
-            startPt = WebCore::IntPoint(rect.fLeft + 1, top);
-            WebCore::HitTestResult hitTestResult = m_mainFrame->eventHandler()->
-                hitTestResultAtPoint(startPt, false);
-            node = ChildIsTextNode(hitTestResult.innerNode());
-            if (node)
-                break;
-            DBG_NAV_LOGD("node=%p (%s)", node, top != cy ? "top+1" : "cy");
-        }
-        if (!node) {
-            DBG_NAV_LOG("!node");
-            return result;
-        }
-        for (int bottom = rect.fBottom - 1; bottom != cy; bottom = cy) {
-            for (int right = rect.fRight - 1; right != rect.fRight-2; --right) {
-                endPt = WebCore::IntPoint(right, bottom);
-                WebCore::HitTestResult hitTestResult = m_mainFrame->
-                    eventHandler()->hitTestResultAtPoint(endPt, false);
-                endNode = ChildIsTextNode(hitTestResult.innerNode());
-                if (endNode)
-                    break;
-                DBG_NAV_LOGD("!endNode=%p (%s) (right-%d)", node,
-                    bottom != cy ? "bottom-1" : "cy", rect.fRight - right);
-            }
-        }
-        if (!endNode) {
-            DBG_NAV_LOG("!endNode");
-            return result;
-        }
-        int start = findTextBoxIndex(node, startPt);
-        if (start < 0)
-            continue;
-        int end = findTextBoxIndex(endNode, endPt);
-        if (end < -1) // use node if endNode is not valid
-            endNode = node;
-        if (end <= 0)
-            end = static_cast<WebCore::Text*>(endNode)->dataImpl()->length();
-        DBG_NAV_LOGD("node=%p start=%d endNode=%p end=%d", node, start, endNode, end);
-        WebCore::Node* startNode = node;
-        do {
-            if (!node->isTextNode())
-                continue;
-            if (node->getRect().isEmpty())
-                continue;
-            WebCore::Text* textNode = static_cast<WebCore::Text*>(node);
-            WebCore::StringImpl* string = textNode->dataImpl();
-            if (!string->length())
-                continue;
-            const UChar* chars = string->characters();
-            int newLength = node == endNode ? end : string->length();
-            if (node == startNode) {
- #if DEBUG_NAV_UI
-                if (node == lastStartNode)
-                    DBG_NAV_LOGD("start=%d last=%d", start, lastStartEnd);
- #endif
-                if (node == lastStartNode && start < lastStartEnd)
-                    break; // skip rect if text overlaps already written text
-                lastStartNode = node;
-                lastStartEnd = newLength - start;
-            }
-            if (newLength < start) {
-                DBG_NAV_LOGD("newLen=%d < start=%d", newLength, start);
-                break;
-            }
-            if (!isPunctuation(chars[start]))
-                result.append(' ');
-            result.append(chars + start, newLength - start);
-            start = 0;
-        } while (node != endNode && (node = node->traverseNextNode()));
-    }
-    result = result.simplifyWhiteSpace().stripWhiteSpace();
-#if DUMP_NAV_CACHE
-    {
-        char buffer[256];
-        CacheBuilder::Debug debug;
-        debug.init(buffer, sizeof(buffer));
-        debug.print("copy: ");
-        debug.wideString(result);
-        DUMP_NAV_LOGD("%s", buffer);
-    }
-#endif
-    return result;
-}
-
 void WebViewCore::setSelection(int start, int end)
 {
     WebCore::Node* focus = currentFocus();
@@ -2938,20 +2735,6 @@ static void SetBackgroundColor(JNIEnv *env, jobject obj, jint color)
     viewImpl->setBackgroundColor((SkColor) color);
 }
 
-static jstring GetSelection(JNIEnv *env, jobject obj, jobject selRgn)
-{
-#ifdef ANDROID_INSTRUMENT
-    TimeCounterAuto counter(TimeCounter::WebViewCoreTimeCounter);
-#endif
-    WebViewCore* viewImpl = GET_NATIVE_VIEW(env, obj);
-    LOG_ASSERT(viewImpl, "viewImpl not set in %s", __FUNCTION__);
-    SkRegion* selectionRegion = GraphicsJNI::getNativeRegion(env, selRgn);
-    WebCore::String result = viewImpl->getSelection(selectionRegion);
-    if (!result.isEmpty())
-        return WebCoreStringToJString(env, result);
-    return 0;
-}
-
 static void DumpDomTree(JNIEnv *env, jobject obj, jboolean useFile)
 {
     WebViewCore* viewImpl = GET_NATIVE_VIEW(env, obj);
@@ -3217,8 +3000,6 @@ static JNINativeMethod gJavaWebViewCoreMethods[] = {
         (void*) SplitContent },
     { "nativeSetBackgroundColor", "(I)V",
         (void*) SetBackgroundColor },
-    { "nativeGetSelection", "(Landroid/graphics/Region;)Ljava/lang/String;",
-        (void*) GetSelection },
     { "nativeRegisterURLSchemeAsLocal", "(Ljava/lang/String;)V",
         (void*) RegisterURLSchemeAsLocal },
     { "nativeDumpDomTree", "(Z)V",
diff --git a/WebKit/android/jni/WebViewCore.h b/WebKit/android/jni/WebViewCore.h
index 75df0b5..6535d60 100644
--- a/WebKit/android/jni/WebViewCore.h
+++ b/WebKit/android/jni/WebViewCore.h
@@ -247,8 +247,6 @@ namespace android {
         WebCore::String retrieveHref(WebCore::Frame* frame, WebCore::Node* node);
         WebCore::String retrieveAnchorText(WebCore::Frame* frame, WebCore::Node* node);
 
-        WebCore::String getSelection(SkRegion* );
-
         // Create a single picture to represent the drawn DOM (used by navcache)
         void recordPicture(SkPicture* picture);
 
diff --git a/WebKit/android/nav/SelectText.cpp b/WebKit/android/nav/SelectText.cpp
index 9a9f8d2..d8b184a 100644
--- a/WebKit/android/nav/SelectText.cpp
+++ b/WebKit/android/nav/SelectText.cpp
@@ -35,14 +35,17 @@
 #include "SkPoint.h"
 #include "SkRect.h"
 #include "SkRegion.h"
+#include "SkUtils.h"
 
 class CommonCheck : public SkBounder {
 public:
     CommonCheck() : mMatrix(NULL), mPaint(NULL) {}
     
-    virtual void setUp(const SkPaint& paint, const SkMatrix& matrix, SkScalar y) {
+    virtual void setUp(const SkPaint& paint, const SkMatrix& matrix, SkScalar y,
+            const void* text) {
         mMatrix = &matrix;
         mPaint = &paint;
+        mText = static_cast<const uint16_t*>(text);
         mY = y;
         mBase = mBottom = mTop = INT_MAX;
     }
@@ -81,10 +84,11 @@ public:
 protected:   
     const SkMatrix* mMatrix;
     const SkPaint* mPaint;
+    const uint16_t* mText;
+    SkScalar mY;
     int mBase;
     int mBottom;
     int mTop;
-    SkScalar mY;
 };
 
 class FirstCheck : public CommonCheck {
@@ -162,6 +166,8 @@ public:
                     full.fRight = mLast.fLeft;
             }
             mSelectRegion->op(full, SkRegion::kUnion_Op);
+            DBG_NAV_LOGD("MultilineBuilder full=(%d,%d,r=%d,b=%d)",
+                full.fLeft, full.fTop, full.fRight, full.fBottom);
             mLast = full;
             mLastBase = base();
             if (mStart == mEnd)
@@ -178,6 +184,66 @@ protected:
     bool mCapture;
 };
 
+class TextExtractor : public CommonCheck {
+public:
+    TextExtractor(const SkRegion& region) : mSelectRegion(region),
+        mSkipFirstSpace(true) { // don't start with a space
+    }
+
+    virtual void setUp(const SkPaint& paint, const SkMatrix& matrix, SkScalar y,
+            const void* text) {
+        INHERITED::setUp(paint, matrix, y, text);
+        SkPaint charPaint = paint;
+        charPaint.setTextEncoding(SkPaint::kUTF8_TextEncoding);
+        mMinSpaceWidth = charPaint.measureText(" ", 1) * 3 / 4;
+    }
+
+    virtual bool onIRect(const SkIRect& rect, uint16_t glyphID) {
+        SkIRect full;
+        full.set(rect.fLeft, top(), rect.fRight, bottom());
+        if (mSelectRegion.contains(full)) {
+            if (!mSkipFirstSpace
+                    && ((mLast.fTop < top() && mLast.fBottom < top() + 2)
+                    || (mLast.fLeft < rect.fLeft // glyphs are LTR
+                    && mLast.fRight + mMinSpaceWidth < rect.fLeft))) {
+                DBG_NAV_LOGD("TextExtractor [%02x] append space", glyphID);
+                *mSelectText.append() = ' ';
+            } else
+                mSkipFirstSpace = false;
+            DBG_NAV_LOGD("TextExtractor [%02x] append full=(%d,%d,r=%d,b=%d)",
+                glyphID, full.fLeft, full.fTop, full.fRight, full.fBottom);
+            SkUnichar uni;
+            SkPaint utfPaint = *mPaint;
+            utfPaint.setTextEncoding(SkPaint::kUTF16_TextEncoding);
+            utfPaint.glyphsToUnichars(&glyphID, 1, &uni);
+            if (uni) {
+                uint16_t chars[2];
+                size_t count = SkUTF16_FromUnichar(uni, chars);
+                *mSelectText.append() = chars[0];
+                if (count == 2)
+                    *mSelectText.append() = chars[1];
+            }
+            mLast = full;
+        } else
+            DBG_NAV_LOGD("TextExtractor [%02x] skip full=(%d,%d,r=%d,b=%d)",
+                glyphID, full.fLeft, full.fTop, full.fRight, full.fBottom);
+        return false;
+    }
+
+    WebCore::String text() {
+        return WebCore::String(mSelectText.begin(), mSelectText.count());
+    }
+
+protected:
+    const SkRegion& mSelectRegion;
+    SkTDArray<uint16_t> mSelectText;
+    SkIRect mLast;
+    SkScalar mMinSpaceWidth;
+    bool mSkipFirstSpace;
+private:
+    typedef CommonCheck INHERITED;
+};
+
 class TextCanvas : public SkCanvas {
 public:
 
@@ -218,14 +284,14 @@ public:
 
     virtual void drawText(const void* text, size_t byteLength, SkScalar x, 
                           SkScalar y, const SkPaint& paint) {
-        mBounder.setUp(paint, getTotalMatrix(), y);
+        mBounder.setUp(paint, getTotalMatrix(), y, text);
         SkCanvas::drawText(text, byteLength, x, y, paint);
     }
 
     virtual void drawPosTextH(const void* text, size_t byteLength,
                               const SkScalar xpos[], SkScalar constY,
                               const SkPaint& paint) {
-        mBounder.setUp(paint, getTotalMatrix(), constY);
+        mBounder.setUp(paint, getTotalMatrix(), constY, text);
         SkCanvas::drawPosTextH(text, byteLength, xpos, constY, paint);
     }
 
@@ -262,3 +328,17 @@ SkIRect CopyPaste::findClosest(const SkPicture& picture, const SkIRect& area,
     _check.offsetBounds(area.fLeft, area.fTop);
     return _check.bestBounds();
 }
+
+WebCore::String CopyPaste::text(const SkPicture& picture, const SkIRect& area,
+        const SkRegion& region) {
+    SkRegion copy = region;
+    copy.translate(-area.fLeft, -area.fTop);
+    const SkIRect& bounds = copy.getBounds();
+    DBG_NAV_LOGD("area=(%d, %d, %d, %d) region=(%d, %d, %d, %d)",
+        area.fLeft, area.fTop, area.fRight, area.fBottom,
+        bounds.fLeft, bounds.fTop, bounds.fRight, bounds.fBottom);
+    TextExtractor extractor(copy);
+    TextCanvas checker(&extractor, picture, area);
+    checker.drawPicture(const_cast<SkPicture&>(picture));
+    return extractor.text();
+}
diff --git a/WebKit/android/nav/SelectText.h b/WebKit/android/nav/SelectText.h
index 3365816..32d8311 100644
--- a/WebKit/android/nav/SelectText.h
+++ b/WebKit/android/nav/SelectText.h
@@ -26,6 +26,8 @@
 #ifndef SELECT_TEXT_H
 #define SELECT_TEXT_H
 
+#include "PlatformString.h"
+
 class SkPicture;
 struct SkIRect;
 struct SkIPoint;
@@ -37,6 +39,8 @@ public:
         const SkIRect& selStart, const SkIRect& selEnd, SkRegion* region);
     static SkIRect findClosest(const SkPicture& , const SkIRect& area,
         int x, int y);
+    static WebCore::String text(const SkPicture& ,  const SkIRect& area,
+        const SkRegion& );
 };
 
 #endif
diff --git a/WebKit/android/nav/WebView.cpp b/WebKit/android/nav/WebView.cpp
index 361b957..6ba37ba 100644
--- a/WebKit/android/nav/WebView.cpp
+++ b/WebKit/android/nav/WebView.cpp
@@ -34,6 +34,7 @@
 #include "CachedFrame.h"
 #include "CachedNode.h"
 #include "CachedRoot.h"
+#include "CString.h"
 #include "FindCanvas.h"
 #include "Frame.h"
 #include "GraphicsJNI.h"
@@ -1032,9 +1033,15 @@ void moveSelection(int x, int y, bool extendSelection)
         m_selEnd.fLeft, m_selEnd.fTop, m_selEnd.fRight, m_selEnd.fBottom);
 }
 
-const SkRegion& getSelection()
+const String getSelection()
 {
-    return m_selRegion;
+    WebCore::IntRect r;
+    getVisibleRect(&r);
+    SkIRect area;
+    area.set(r.x(), r.y(), r.right(), r.bottom());
+    String result = CopyPaste::text(*m_navPictureUI, area, m_selRegion);
+    DBG_NAV_LOGD("text=%s", result.latin1().data());
+    return result;
 }
 
 void drawSelectionRegion(SkCanvas* canvas)
@@ -1109,7 +1116,7 @@ void getSelectionCaret(SkPath* path)
 
 void sendMoveFocus(WebCore::Frame* framePtr, WebCore::Node* nodePtr)
 {
-    DBG_NAV_LOGD("framePtr=%p nodePtr=%p x=%d y=%d", framePtr, nodePtr, x, y);
+    DBG_NAV_LOGD("framePtr=%p nodePtr=%p", framePtr, nodePtr);
     JNIEnv* env = JSC::Bindings::getJNIEnv();
     env->CallVoidMethod(m_javaGlue.object(env).get(),
         m_javaGlue.m_sendMoveFocus, (jint) framePtr, (jint) nodePtr);
@@ -2071,7 +2078,8 @@ static jobject nativeGetSelection(JNIEnv *env, jobject obj)
 {
     WebView* view = GET_NATIVE_VIEW(env, obj);
     LOG_ASSERT(view, "view not set in %s", __FUNCTION__);
-    return GraphicsJNI::createRegion(env, new SkRegion(view->getSelection()));
+    String selection = view->getSelection();
+    return env->NewString((jchar*)selection.characters(), selection.length());
 }
 
 #ifdef ANDROID_DUMP_DISPLAY_TREE
@@ -2205,7 +2213,7 @@ static JNINativeMethod gJavaWebViewMethods[] = {
         (void*) nativeFocusNodePointer },
     { "nativeGetCursorRingBounds", "()Landroid/graphics/Rect;",
         (void*) nativeGetCursorRingBounds },
-    { "nativeGetSelection", "()Landroid/graphics/Region;",
+    { "nativeGetSelection", "()Ljava/lang/String;",
         (void*) nativeGetSelection },
     { "nativeHasCursorNode", "()Z",
         (void*) nativeHasCursorNode },