diff options
Diffstat (limited to 'WebKit/android/nav/FindCanvas.cpp')
| -rw-r--r-- | WebKit/android/nav/FindCanvas.cpp | 458 |
1 files changed, 0 insertions, 458 deletions
diff --git a/WebKit/android/nav/FindCanvas.cpp b/WebKit/android/nav/FindCanvas.cpp deleted file mode 100644 index 61bb07e..0000000 --- a/WebKit/android/nav/FindCanvas.cpp +++ /dev/null @@ -1,458 +0,0 @@ -/* - * Copyright 2008, The Android Open Source Project - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY - * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR - * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, - * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, - * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR - * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY - * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#include "config.h" -#include "FindCanvas.h" - -#include "SkRect.h" - -// MatchInfo methods -//////////////////////////////////////////////////////////////////////////////// - -MatchInfo::MatchInfo() { - m_picture = 0; -} - -MatchInfo::~MatchInfo() { - m_picture->safeUnref(); -} - -MatchInfo::MatchInfo(const MatchInfo& src) { - m_location = src.m_location; - m_picture = src.m_picture; - m_picture->safeRef(); -} - -void MatchInfo::set(const SkRegion& region, SkPicture* pic) { - m_picture->safeUnref(); - m_location = region; - m_picture = pic; - SkASSERT(pic); - pic->ref(); -} - -// GlyphSet methods -//////////////////////////////////////////////////////////////////////////////// - -GlyphSet::GlyphSet(const SkPaint& paint, const UChar* lower, const UChar* upper, - size_t byteLength) { - SkPaint clonePaint(paint); - clonePaint.setTextEncoding(SkPaint::kUTF16_TextEncoding); - mTypeface = paint.getTypeface(); - mCount = clonePaint.textToGlyphs(lower, byteLength, NULL); - if (mCount > MAX_STORAGE_COUNT) { - mLowerGlyphs = new uint16_t[2*mCount]; - } else { - mLowerGlyphs = &mStorage[0]; - } - // Use one array, and have mUpperGlyphs point to a portion of it, - // so that we can reduce the number of new/deletes - mUpperGlyphs = mLowerGlyphs + mCount; - int count2 = clonePaint.textToGlyphs(lower, byteLength, mLowerGlyphs); - SkASSERT(mCount == count2); - count2 = clonePaint.textToGlyphs(upper, byteLength, mUpperGlyphs); - SkASSERT(mCount == count2); -} - -GlyphSet::~GlyphSet() { - // Do not need to delete mTypeface, which is not owned by us. - if (mCount > MAX_STORAGE_COUNT) { - delete[] mLowerGlyphs; - } // Otherwise, we just used local storage space, so no need to delete - // Also do not need to delete mUpperGlyphs, which simply points to a - // part of mLowerGlyphs -} - -GlyphSet::GlyphSet& GlyphSet::operator=(GlyphSet& src) { - mTypeface = src.mTypeface; - mCount = src.mCount; - if (mCount > MAX_STORAGE_COUNT) { - mLowerGlyphs = new uint16_t[2*mCount]; - } else { - mLowerGlyphs = &mStorage[0]; - } - memcpy(mLowerGlyphs, src.mLowerGlyphs, 2*mCount*sizeof(uint16_t)); - mUpperGlyphs = mLowerGlyphs + mCount; - return *this; -} - -bool GlyphSet::characterMatches(uint16_t c, int index) { - SkASSERT(index < mCount && index >= 0); - return c == mLowerGlyphs[index] || c == mUpperGlyphs[index]; -} - -// FindCanvas methods -//////////////////////////////////////////////////////////////////////////////// - -FindCanvas::FindCanvas(int width, int height, const UChar* lower, - const UChar* upper, size_t byteLength) - : mLowerText(lower) - , mUpperText(upper) - , mLength(byteLength) - , mNumFound(0) { - - setBounder(&mBounder); - mOutset = -SkIntToScalar(2); - mMatches = new WTF::Vector<MatchInfo>(); - mWorkingIndex = 0; - mWorkingCanvas = 0; - mWorkingPicture = 0; -} - -FindCanvas::~FindCanvas() { - setBounder(NULL); - /* Just in case getAndClear was not called. */ - delete mMatches; - mWorkingPicture->safeUnref(); -} - -// Each version of addMatch returns a rectangle for a match. -// Not all of the parameters are used by each version. -SkRect FindCanvas::addMatchNormal(int index, - const SkPaint& paint, int count, const uint16_t* glyphs, - const SkScalar pos[], SkScalar y) { - const uint16_t* lineStart = glyphs - index; - /* Use the original paint, since "text" is in glyphs */ - SkScalar before = paint.measureText(lineStart, index * sizeof(uint16_t), 0); - SkRect rect; - rect.fLeft = pos[0] + before; - int countInBytes = count * sizeof(uint16_t); - rect.fRight = paint.measureText(glyphs, countInBytes, 0) + rect.fLeft; - SkPaint::FontMetrics fontMetrics; - paint.getFontMetrics(&fontMetrics); - SkScalar baseline = y; - rect.fTop = baseline + fontMetrics.fAscent; - rect.fBottom = baseline + fontMetrics.fDescent; - const SkMatrix& matrix = getTotalMatrix(); - matrix.mapRect(&rect); - // Add the text to our picture. - SkCanvas* canvas = getWorkingCanvas(); - int saveCount = canvas->save(); - canvas->concat(matrix); - canvas->drawText(glyphs, countInBytes, pos[0] + before, y, paint); - canvas->restoreToCount(saveCount); - return rect; -} - -SkRect FindCanvas::addMatchPos(int index, - const SkPaint& paint, int count, const uint16_t* glyphs, - const SkScalar xPos[], SkScalar /* y */) { - SkRect r; - r.setEmpty(); - const SkPoint* temp = reinterpret_cast<const SkPoint*> (xPos); - const SkPoint* points = &temp[index]; - int countInBytes = count * sizeof(uint16_t); - SkPaint::FontMetrics fontMetrics; - paint.getFontMetrics(&fontMetrics); - // Need to check each character individually, since the heights may be - // different. - for (int j = 0; j < count; j++) { - SkRect bounds; - bounds.fLeft = points[j].fX; - bounds.fRight = bounds.fLeft + - paint.measureText(&glyphs[j], sizeof(uint16_t), 0); - SkScalar baseline = points[j].fY; - bounds.fTop = baseline + fontMetrics.fAscent; - bounds.fBottom = baseline + fontMetrics.fDescent; - /* Accumulate and then add the resulting rect to mMatches */ - r.join(bounds); - } - SkMatrix matrix = getTotalMatrix(); - matrix.mapRect(&r); - SkCanvas* canvas = getWorkingCanvas(); - int saveCount = canvas->save(); - canvas->concat(matrix); - canvas->drawPosText(glyphs, countInBytes, points, paint); - canvas->restoreToCount(saveCount); - return r; -} - -SkRect FindCanvas::addMatchPosH(int index, - const SkPaint& paint, int count, const uint16_t* glyphs, - const SkScalar position[], SkScalar constY) { - SkRect r; - // We only care about the positions starting at the index of our match - const SkScalar* xPos = &position[index]; - // This assumes that the position array is monotonic increasing - // The left bounds will be the position of the left most character - r.fLeft = xPos[0]; - // The right bounds will be the position of the last character plus its - // width - int lastIndex = count - 1; - r.fRight = paint.measureText(&glyphs[lastIndex], sizeof(uint16_t), 0) - + xPos[lastIndex]; - // Grab font metrics to determine the top and bottom of the bounds - SkPaint::FontMetrics fontMetrics; - paint.getFontMetrics(&fontMetrics); - r.fTop = constY + fontMetrics.fAscent; - r.fBottom = constY + fontMetrics.fDescent; - const SkMatrix& matrix = getTotalMatrix(); - matrix.mapRect(&r); - SkCanvas* canvas = getWorkingCanvas(); - int saveCount = canvas->save(); - canvas->concat(matrix); - canvas->drawPosTextH(glyphs, count * sizeof(uint16_t), xPos, constY, paint); - canvas->restoreToCount(saveCount); - return r; -} - -void FindCanvas::drawText(const void* text, size_t byteLength, SkScalar x, - SkScalar y, const SkPaint& paint) { - findHelper(text, byteLength, paint, &x, y, &FindCanvas::addMatchNormal); -} - -void FindCanvas::drawPosText(const void* text, size_t byteLength, - const SkPoint pos[], const SkPaint& paint) { - // Pass in the first y coordinate for y so that we can check to see whether - // it is lower than the last draw call (to check if we are continuing to - // another line). - findHelper(text, byteLength, paint, (const SkScalar*) pos, pos[0].fY, - &FindCanvas::addMatchPos); -} - -void FindCanvas::drawPosTextH(const void* text, size_t byteLength, - const SkScalar xpos[], SkScalar constY, - const SkPaint& paint) { - findHelper(text, byteLength, paint, xpos, constY, - &FindCanvas::addMatchPosH); -} - -/* The current behavior is to skip substring matches. This means that in the - * string - * batbatbat - * a search for - * batbat - * will return 1 match. If the desired behavior is to return 2 matches, define - * INCLUDE_SUBSTRING_MATCHES to be 1. - */ -#define INCLUDE_SUBSTRING_MATCHES 0 - -// Need a quick way to know a maximum distance between drawText calls to know if -// they are part of the same logical phrase when searching. By crude -// inspection, half the point size seems a good guess at the width of a space -// character. -static inline SkScalar approximateSpaceWidth(const SkPaint& paint) { - return SkScalarHalf(paint.getTextSize()); -} - -void FindCanvas::findHelper(const void* text, size_t byteLength, - const SkPaint& paint, const SkScalar positions[], - SkScalar y, - SkRect (FindCanvas::*addMatch)(int index, - const SkPaint& paint, int count, - const uint16_t* glyphs, - const SkScalar positions[], SkScalar y)) { - SkASSERT(paint.getTextEncoding() == SkPaint::kGlyphID_TextEncoding); - SkASSERT(mMatches); - GlyphSet* glyphSet = getGlyphs(paint); - const int count = glyphSet->getCount(); - int numCharacters = byteLength >> 1; - const uint16_t* chars = (const uint16_t*) text; - // This block will check to see if we are continuing from another line. If - // so, the user needs to have added a space, which we do not draw. - if (mWorkingIndex) { - SkPoint newY; - getTotalMatrix().mapXY(0, y, &newY); - SkIRect bounds = mWorkingRegion.getBounds(); - if (bounds.fBottom < SkScalarRound(newY.fY)) { - // Now we know that this line is lower than our partial match. - SkPaint clonePaint(paint); - clonePaint.setTextEncoding(SkPaint::kUTF8_TextEncoding); - uint16_t space; - clonePaint.textToGlyphs(" ", 1, &space); - if (glyphSet->characterMatches(space, mWorkingIndex)) { - mWorkingIndex++; - if (mWorkingIndex == count) { - // We already know that it is not clipped out because we - // checked for that before saving the working region. - insertMatchInfo(mWorkingRegion); - - resetWorkingCanvas(); - mWorkingIndex = 0; - mWorkingRegion.setEmpty(); - // We have found a match, so continue on this line from - // scratch. - } - } else { - resetWorkingCanvas(); - mWorkingIndex = 0; - mWorkingRegion.setEmpty(); - } - } - } - // j is the position in the search text - // Start off with mWorkingIndex in case we are continuing from a prior call - int j = mWorkingIndex; - // index is the position in the drawn text - int index = 0; - for ( ; index != numCharacters; index++) { - if (glyphSet->characterMatches(chars[index], j)) { - // The jth character in the search text matches the indexth position - // in the drawn text, so increase j. - j++; - if (j != count) { - continue; - } - // The last count characters match, so we found the entire - // search string. - int remaining = count - mWorkingIndex; - int matchIndex = index - remaining + 1; - // Set up a pointer to the matching text in 'chars'. - const uint16_t* glyphs = chars + matchIndex; - SkRect rect = (this->*addMatch)(matchIndex, paint, - remaining, glyphs, positions, y); - rect.inset(mOutset, mOutset); - // We need an SkIRect for SkRegion operations. - SkIRect iRect; - rect.roundOut(&iRect); - // If the rectangle is partially clipped, assume that the text is - // not visible, so skip this match. - if (getTotalClip().contains(iRect)) { - SkRegion regionToAdd(iRect); - if (!mWorkingRegion.isEmpty()) { - // If this is on the same line as our working region, make - // sure that they are close enough together that they are - // supposed to be part of the same text string. - // The width of two spaces has arbitrarily been chosen. - const SkIRect& workingBounds = mWorkingRegion.getBounds(); - if (workingBounds.fTop <= iRect.fBottom && - workingBounds.fBottom >= iRect.fTop && - SkIntToScalar(iRect.fLeft - workingBounds.fRight) > - approximateSpaceWidth(paint)) { - index = -1; // Will increase to 0 on next run - // In this case, we need to start from the beginning of - // the text being searched and our search term. - j = 0; - mWorkingIndex = 0; - mWorkingRegion.setEmpty(); - continue; - } - // Add the mWorkingRegion, which contains rectangles from - // the previous line(s). - regionToAdd.op(mWorkingRegion, SkRegion::kUnion_Op); - } - insertMatchInfo(regionToAdd); -#if INCLUDE_SUBSTRING_MATCHES - // Reset index to the location of the match and reset j to the - // beginning, so that on the next iteration of the loop, index - // will advance by 1 and we will compare the next character in - // chars to the first character in the GlyphSet. - index = matchIndex; -#endif - } else { - // This match was clipped out, so begin looking at the next - // character from our hidden match - index = matchIndex; - } - // Whether the clip contained it or not, we need to start over - // with our recording canvas - resetWorkingCanvas(); - } else { - // Index needs to be set to index - j + 1. - // This is a ridiculous case, but imagine the situation where the - // user is looking for the string "jjog" in the drawText call for - // "jjjog". The first two letters match. However, when the index - // is 2, and we discover that 'o' and 'j' do not match, we should go - // back to 1, where we do, in fact, have a match - // FIXME: This does not work if (as in our example) "jj" is in one - // draw call and "jog" is in the next. Doing so would require a - // stack, keeping track of multiple possible working indeces and - // regions. This is likely an uncommon case. - index = index - j; // index will be increased by one on the next - // iteration - } - // We reach here in one of two cases: - // 1) We just completed a match, so any working rectangle/index is no - // longer needed, and we will start over from the beginning - // 2) The glyphs do not match, so we start over at the beginning of - // the search string. - j = 0; - mWorkingIndex = 0; - mWorkingRegion.setEmpty(); - } - // At this point, we have searched all of the text in the current drawText - // call. - // Keep track of a partial match that may start on this line. - if (j > 0) { // if j is greater than 0, we have a partial match - int partialIndex = index - j + mWorkingIndex; - const uint16_t* partialGlyphs = chars + partialIndex; - SkRect partial = (this->*addMatch)(partialIndex, paint, j, - partialGlyphs, positions, y); - partial.inset(mOutset, mOutset); - getTotalMatrix().mapRect(&partial); - SkIRect dest; - partial.roundOut(&dest); - // Only save a partial if it is in the current clip. - if (getTotalClip().contains(dest)) { - mWorkingRegion.op(dest, SkRegion::kUnion_Op); - mWorkingIndex = j; - // From one perspective, it seems like we would want to draw here, - // since we have all the information (paint, matrix, etc) - // However, we only want to draw if we find the rest - return; - } - } - // This string doesn't go into the next drawText, so reset our working - // variables - mWorkingRegion.setEmpty(); - mWorkingIndex = 0; -} - -SkCanvas* FindCanvas::getWorkingCanvas() { - if (!mWorkingPicture) { - mWorkingPicture = new SkPicture; - mWorkingCanvas = mWorkingPicture->beginRecording(0,0); - } - return mWorkingCanvas; -} - -GlyphSet* FindCanvas::getGlyphs(const SkPaint& paint) { - SkTypeface* typeface = paint.getTypeface(); - GlyphSet* end = mGlyphSets.end(); - for (GlyphSet* ptr = mGlyphSets.begin();ptr != end; ptr++) { - if (ptr->getTypeface() == typeface) { - return ptr; - } - } - - GlyphSet set(paint, mLowerText, mUpperText, mLength); - *mGlyphSets.append() = set; - return &(mGlyphSets.top()); -} - -void FindCanvas::insertMatchInfo(const SkRegion& region) { - mNumFound++; - mWorkingPicture->endRecording(); - MatchInfo matchInfo; - mMatches->append(matchInfo); - mMatches->last().set(region, mWorkingPicture); -} - -void FindCanvas::resetWorkingCanvas() { - mWorkingPicture->unref(); - mWorkingPicture = 0; - // Do not need to reset mWorkingCanvas itself because we only access it via - // getWorkingCanvas. -} |