and the

have bottom margins. RenderObject* r = node->renderer(); if (!r || !r->isBox()) return false; // NOTE: We only do this for a select set of nodes, and fwiw WinIE appears // not to do this at all if (node->hasTagName(h1Tag) || node->hasTagName(h2Tag) || node->hasTagName(h3Tag) || node->hasTagName(h4Tag) || node->hasTagName(h5Tag) || node->hasTagName(h6Tag) || node->hasTagName(pTag)) { RenderStyle* style = r->style(); if (style) { int bottomMargin = toRenderBox(r)->collapsedMarginBottom(); int fontSize = style->fontDescription().computedPixelSize(); if (bottomMargin * 2 >= fontSize) return true; } } return false; } static int collapsedSpaceLength(RenderText* renderer, int textEnd) { const UChar* characters = renderer->text()->characters(); int length = renderer->text()->length(); for (int i = textEnd; i < length; ++i) { if (!renderer->style()->isCollapsibleWhiteSpace(characters[i])) return i - textEnd; } return length - textEnd; } static int maxOffsetIncludingCollapsedSpaces(Node* node) { int offset = caretMaxOffset(node); if (node->renderer() && node->renderer()->isText()) offset += collapsedSpaceLength(toRenderText(node->renderer()), offset); return offset; } // Whether or not we should emit a character as we enter m_node (if it's a container) or as we hit it (if it's atomic). bool TextIterator::shouldRepresentNodeOffsetZero() { if (m_emitCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isTable()) return true; // Leave element positioned flush with start of a paragraph // (e.g. do not insert tab before a table cell at the start of a paragraph) if (m_lastCharacter == '\n') return false; // Otherwise, show the position if we have emitted any characters if (m_haveEmitted) return true; // We've not emitted anything yet. Generally, there is no need for any positioning then. // The only exception is when the element is visually not in the same line as // the start of the range (e.g. the range starts at the end of the previous paragraph). // NOTE: Creating VisiblePositions and comparing them is relatively expensive, so we // make quicker checks to possibly avoid that. Another check that we could make is // is whether the inline vs block flow changed since the previous visible element. // I think we're already in a special enough case that that won't be needed, tho. // No character needed if this is the first node in the range. if (m_node == m_startContainer) return false; // If we are outside the start container's subtree, assume we need to emit. // FIXME: m_startContainer could be an inline block if (!m_node->isDescendantOf(m_startContainer)) return true; // If we started as m_startContainer offset 0 and the current node is a descendant of // the start container, we already had enough context to correctly decide whether to // emit after a preceding block. We chose not to emit (m_haveEmitted is false), // so don't second guess that now. // NOTE: Is this really correct when m_node is not a leftmost descendant? Probably // immaterial since we likely would have already emitted something by now. if (m_startOffset == 0) return false; // If this node is unrendered or invisible the VisiblePosition checks below won't have much meaning. // Additionally, if the range we are iterating over contains huge sections of unrendered content, // we would create VisiblePositions on every call to this function without this check. if (!m_node->renderer() || m_node->renderer()->style()->visibility() != VISIBLE) return false; // The startPos.isNotNull() check is needed because the start could be before the body, // and in that case we'll get null. We don't want to put in newlines at the start in that case. // The currPos.isNotNull() check is needed because positions in non-HTML content // (like SVG) do not have visible positions, and we don't want to emit for them either. VisiblePosition startPos = VisiblePosition(m_startContainer, m_startOffset, DOWNSTREAM); VisiblePosition currPos = VisiblePosition(m_node, 0, DOWNSTREAM); return startPos.isNotNull() && currPos.isNotNull() && !inSameLine(startPos, currPos); } bool TextIterator::shouldEmitSpaceBeforeAndAfterNode(Node* node) { return node->renderer() && node->renderer()->isTable() && (node->renderer()->isInline() || m_emitCharactersBetweenAllVisiblePositions); } void TextIterator::representNodeOffsetZero() { // Emit a character to show the positioning of m_node. // When we haven't been emitting any characters, shouldRepresentNodeOffsetZero() can // create VisiblePositions, which is expensive. So, we perform the inexpensive checks // on m_node to see if it necessitates emitting a character first and will early return // before encountering shouldRepresentNodeOffsetZero()s worse case behavior. if (shouldEmitTabBeforeNode(m_node)) { if (shouldRepresentNodeOffsetZero()) emitCharacter('\t', m_node->parentNode(), m_node, 0, 0); } else if (shouldEmitNewlineBeforeNode(m_node)) { if (shouldRepresentNodeOffsetZero()) emitCharacter('\n', m_node->parentNode(), m_node, 0, 0); } else if (shouldEmitSpaceBeforeAndAfterNode(m_node)) { if (shouldRepresentNodeOffsetZero()) emitCharacter(' ', m_node->parentNode(), m_node, 0, 0); } } bool TextIterator::handleNonTextNode() { if (shouldEmitNewlineForNode(m_node)) emitCharacter('\n', m_node->parentNode(), m_node, 0, 1); else if (m_emitCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isHR()) emitCharacter(' ', m_node->parentNode(), m_node, 0, 1); else representNodeOffsetZero(); return true; } void TextIterator::exitNode() { // prevent emitting a newline when exiting a collapsed block at beginning of the range // FIXME: !m_haveEmitted does not necessarily mean there was a collapsed block... it could // have been an hr (e.g.). Also, a collapsed block could have height (e.g. a table) and // therefore look like a blank line. if (!m_haveEmitted) return; // Emit with a position *inside* m_node, after m_node's contents, in // case it is a block, because the run should start where the // emitted character is positioned visually. Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node; // FIXME: This shouldn't require the m_lastTextNode to be true, but we can't change that without making // the logic in _web_attributedStringFromRange match. We'll get that for free when we switch to use // TextIterator in _web_attributedStringFromRange. // See for an example of how this mismatch will cause problems. if (m_lastTextNode && shouldEmitNewlineAfterNode(m_node)) { // use extra newline to represent margin bottom, as needed bool addNewline = shouldEmitExtraNewlineForNode(m_node); // FIXME: We need to emit a '\n' as we leave an empty block(s) that // contain a VisiblePosition when doing selection preservation. if (m_lastCharacter != '\n') { // insert a newline with a position following this block's contents. emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1); // remember whether to later add a newline for the current node ASSERT(!m_needAnotherNewline); m_needAnotherNewline = addNewline; } else if (addNewline) // insert a newline with a position following this block's contents. emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1); } // If nothing was emitted, see if we need to emit a space. if (!m_positionNode && shouldEmitSpaceBeforeAndAfterNode(m_node)) emitCharacter(' ', baseNode->parentNode(), baseNode, 1, 1); } void TextIterator::emitCharacter(UChar c, Node* textNode, Node* offsetBaseNode, int textStartOffset, int textEndOffset) { m_haveEmitted = true; // remember information with which to construct the TextIterator::range() // NOTE: textNode is often not a text node, so the range will specify child nodes of positionNode m_positionNode = textNode; m_positionOffsetBaseNode = offsetBaseNode; m_positionStartOffset = textStartOffset; m_positionEndOffset = textEndOffset; // remember information with which to construct the TextIterator::characters() and length() m_singleCharacterBuffer = c; m_textCharacters = &m_singleCharacterBuffer; m_textLength = 1; // remember some iteration state m_lastTextNodeEndedWithCollapsedSpace = false; m_lastCharacter = c; } void TextIterator::emitText(Node* textNode, int textStartOffset, int textEndOffset) { RenderText* renderer = toRenderText(m_node->renderer()); String str = renderer->text(); ASSERT(str.characters()); m_positionNode = textNode; m_positionOffsetBaseNode = 0; m_positionStartOffset = textStartOffset; m_positionEndOffset = textEndOffset; m_textCharacters = str.characters() + textStartOffset; m_textLength = textEndOffset - textStartOffset; m_lastCharacter = str[textEndOffset - 1]; m_lastTextNodeEndedWithCollapsedSpace = false; m_haveEmitted = true; } PassRefPtr TextIterator::range() const { // use the current run information, if we have it if (m_positionNode) { if (m_positionOffsetBaseNode) { int index = m_positionOffsetBaseNode->nodeIndex(); m_positionStartOffset += index; m_positionEndOffset += index; m_positionOffsetBaseNode = 0; } return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset); } // otherwise, return the end of the overall range we were given if (m_endContainer) return Range::create(m_endContainer->document(), m_endContainer, m_endOffset, m_endContainer, m_endOffset); return 0; } Node* TextIterator::node() const { RefPtr textRange = range(); if (!textRange) return 0; Node* node = textRange->startContainer(); if (!node) return 0; if (node->offsetInCharacters()) return node; return node->childNode(textRange->startOffset()); } // -------- SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator() : m_positionNode(0) { } SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range* r) : m_positionNode(0) { if (!r) return; Node* startNode = r->startContainer(); if (!startNode) return; Node* endNode = r->endContainer(); int startOffset = r->startOffset(); int endOffset = r->endOffset(); if (!startNode->offsetInCharacters()) { if (startOffset >= 0 && startOffset < static_cast(startNode->childNodeCount())) { startNode = startNode->childNode(startOffset); startOffset = 0; } } if (!endNode->offsetInCharacters()) { if (endOffset > 0 && endOffset <= static_cast(endNode->childNodeCount())) { endNode = endNode->childNode(endOffset - 1); endOffset = lastOffsetInNode(endNode); } } m_node = endNode; setUpFullyClippedStack(m_fullyClippedStack, m_node); m_offset = endOffset; m_handledNode = false; m_handledChildren = endOffset == 0; m_startNode = startNode; m_startOffset = startOffset; m_endNode = endNode; m_endOffset = endOffset; #ifndef NDEBUG // Need this just because of the assert. m_positionNode = endNode; #endif m_lastTextNode = 0; m_lastCharacter = '\n'; m_pastStartNode = previousInPostOrderCrossingShadowBoundaries(startNode, startOffset); advance(); } void SimplifiedBackwardsTextIterator::advance() { ASSERT(m_positionNode); m_positionNode = 0; m_textLength = 0; while (m_node && m_node != m_pastStartNode) { // Don't handle node if we start iterating at [node, 0]. if (!m_handledNode && !(m_node == m_endNode && m_endOffset == 0)) { RenderObject* renderer = m_node->renderer(); if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) { // FIXME: What about CDATA_SECTION_NODE? if (renderer->style()->visibility() == VISIBLE && m_offset > 0) m_handledNode = handleTextNode(); } else if (renderer && (renderer->isImage() || renderer->isWidget())) { if (renderer->style()->visibility() == VISIBLE && m_offset > 0) m_handledNode = handleReplacedElement(); } else m_handledNode = handleNonTextNode(); if (m_positionNode) return; } Node* next = m_handledChildren ? 0 : m_node->lastChild(); if (!next) { // Exit empty containers as we pass over them or containers // where [container, 0] is where we started iterating. if (!m_handledNode && canHaveChildrenForEditing(m_node) && m_node->parentNode() && (!m_node->lastChild() || (m_node == m_endNode && m_endOffset == 0))) { exitNode(); if (m_positionNode) { m_handledNode = true; m_handledChildren = true; return; } } // Exit all other containers. next = m_node->previousSibling(); while (!next) { Node* parentNode = parentCrossingShadowBoundaries(m_node); if (!parentNode) break; m_node = parentNode; m_fullyClippedStack.pop(); exitNode(); if (m_positionNode) { m_handledNode = true; m_handledChildren = true; return; } next = m_node->previousSibling(); } m_fullyClippedStack.pop(); } m_node = next; if (m_node) pushFullyClippedState(m_fullyClippedStack, m_node); // For the purpose of word boundary detection, // we should iterate all visible text and trailing (collapsed) whitespaces. m_offset = m_node ? maxOffsetIncludingCollapsedSpaces(m_node) : 0; m_handledNode = false; m_handledChildren = false; if (m_positionNode) return; } } bool SimplifiedBackwardsTextIterator::handleTextNode() { m_lastTextNode = m_node; RenderText* renderer = toRenderText(m_node->renderer()); String str = renderer->text(); if (!renderer->firstTextBox() && str.length() > 0) return true; m_positionEndOffset = m_offset; m_offset = (m_node == m_startNode) ? m_startOffset : 0; m_positionNode = m_node; m_positionStartOffset = m_offset; m_textLength = m_positionEndOffset - m_positionStartOffset; m_textCharacters = str.characters() + m_positionStartOffset; m_lastCharacter = str[m_positionEndOffset - 1]; return true; } bool SimplifiedBackwardsTextIterator::handleReplacedElement() { unsigned index = m_node->nodeIndex(); // We want replaced elements to behave like punctuation for boundary // finding, and to simply take up space for the selection preservation // code in moveParagraphs, so we use a comma. Unconditionally emit // here because this iterator is only used for boundary finding. emitCharacter(',', m_node->parentNode(), index, index + 1); return true; } bool SimplifiedBackwardsTextIterator::handleNonTextNode() { // We can use a linefeed in place of a tab because this simple iterator is only used to // find boundaries, not actual content. A linefeed breaks words, sentences, and paragraphs. if (shouldEmitNewlineForNode(m_node) || shouldEmitNewlineAfterNode(m_node) || shouldEmitTabBeforeNode(m_node)) { unsigned index = m_node->nodeIndex(); // The start of this emitted range is wrong. Ensuring correctness would require // VisiblePositions and so would be slow. previousBoundary expects this. emitCharacter('\n', m_node->parentNode(), index + 1, index + 1); } return true; } void SimplifiedBackwardsTextIterator::exitNode() { if (shouldEmitNewlineForNode(m_node) || shouldEmitNewlineBeforeNode(m_node) || shouldEmitTabBeforeNode(m_node)) { // The start of this emitted range is wrong. Ensuring correctness would require // VisiblePositions and so would be slow. previousBoundary expects this. emitCharacter('\n', m_node, 0, 0); } } void SimplifiedBackwardsTextIterator::emitCharacter(UChar c, Node* node, int startOffset, int endOffset) { m_singleCharacterBuffer = c; m_positionNode = node; m_positionStartOffset = startOffset; m_positionEndOffset = endOffset; m_textCharacters = &m_singleCharacterBuffer; m_textLength = 1; m_lastCharacter = c; } PassRefPtr SimplifiedBackwardsTextIterator::range() const { if (m_positionNode) return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset); return Range::create(m_startNode->document(), m_startNode, m_startOffset, m_startNode, m_startOffset); } // -------- CharacterIterator::CharacterIterator() : m_offset(0) , m_runOffset(0) , m_atBreak(true) { } CharacterIterator::CharacterIterator(const Range* r, bool emitCharactersBetweenAllVisiblePositions, bool enterTextControls) : m_offset(0) , m_runOffset(0) , m_atBreak(true) , m_textIterator(r, emitCharactersBetweenAllVisiblePositions, enterTextControls) { while (!atEnd() && m_textIterator.length() == 0) m_textIterator.advance(); } PassRefPtr CharacterIterator::range() const { RefPtr r = m_textIterator.range(); if (!m_textIterator.atEnd()) { if (m_textIterator.length() <= 1) { ASSERT(m_runOffset == 0); } else { Node* n = r->startContainer(); ASSERT(n == r->endContainer()); int offset = r->startOffset() + m_runOffset; ExceptionCode ec = 0; r->setStart(n, offset, ec); r->setEnd(n, offset + 1, ec); ASSERT(!ec); } } return r.release(); } void CharacterIterator::advance(int count) { if (count <= 0) { ASSERT(count == 0); return; } m_atBreak = false; // easy if there is enough left in the current m_textIterator run int remaining = m_textIterator.length() - m_runOffset; if (count < remaining) { m_runOffset += count; m_offset += count; return; } // exhaust the current m_textIterator run count -= remaining; m_offset += remaining; // move to a subsequent m_textIterator run for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) { int runLength = m_textIterator.length(); if (runLength == 0) m_atBreak = true; else { // see whether this is m_textIterator to use if (count < runLength) { m_runOffset = count; m_offset += count; return; } // exhaust this m_textIterator run count -= runLength; m_offset += runLength; } } // ran to the end of the m_textIterator... no more runs left m_atBreak = true; m_runOffset = 0; } String CharacterIterator::string(int numChars) { Vector result; result.reserveInitialCapacity(numChars); while (numChars > 0 && !atEnd()) { int runSize = min(numChars, length()); result.append(characters(), runSize); numChars -= runSize; advance(runSize); } return String::adopt(result); } static PassRefPtr characterSubrange(CharacterIterator& it, int offset, int length) { it.advance(offset); RefPtr start = it.range(); if (length > 1) it.advance(length - 1); RefPtr end = it.range(); return Range::create(start->startContainer()->document(), start->startContainer(), start->startOffset(), end->endContainer(), end->endOffset()); } BackwardsCharacterIterator::BackwardsCharacterIterator() : m_offset(0) , m_runOffset(0) , m_atBreak(true) { } BackwardsCharacterIterator::BackwardsCharacterIterator(const Range* range) : m_offset(0) , m_runOffset(0) , m_atBreak(true) , m_textIterator(range) { while (!atEnd() && !m_textIterator.length()) m_textIterator.advance(); } PassRefPtr BackwardsCharacterIterator::range() const { RefPtr r = m_textIterator.range(); if (!m_textIterator.atEnd()) { if (m_textIterator.length() <= 1) ASSERT(m_runOffset == 0); else { Node* n = r->startContainer(); ASSERT(n == r->endContainer()); int offset = r->endOffset() - m_runOffset; ExceptionCode ec = 0; r->setStart(n, offset - 1, ec); r->setEnd(n, offset, ec); ASSERT(!ec); } } return r.release(); } void BackwardsCharacterIterator::advance(int count) { if (count <= 0) { ASSERT(!count); return; } m_atBreak = false; int remaining = m_textIterator.length() - m_runOffset; if (count < remaining) { m_runOffset += count; m_offset += count; return; } count -= remaining; m_offset += remaining; for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) { int runLength = m_textIterator.length(); if (runLength == 0) m_atBreak = true; else { if (count < runLength) { m_runOffset = count; m_offset += count; return; } count -= runLength; m_offset += runLength; } } m_atBreak = true; m_runOffset = 0; } // -------- WordAwareIterator::WordAwareIterator() : m_previousText(0) , m_didLookAhead(false) { } WordAwareIterator::WordAwareIterator(const Range* r) : m_previousText(0) , m_didLookAhead(true) // so we consider the first chunk from the text iterator , m_textIterator(r) { advance(); // get in position over the first chunk of text } // We're always in one of these modes: // - The current chunk in the text iterator is our current chunk // (typically its a piece of whitespace, or text that ended with whitespace) // - The previous chunk in the text iterator is our current chunk // (we looked ahead to the next chunk and found a word boundary) // - We built up our own chunk of text from many chunks from the text iterator // FIXME: Performance could be bad for huge spans next to each other that don't fall on word boundaries. void WordAwareIterator::advance() { m_previousText = 0; m_buffer.clear(); // toss any old buffer we built up // If last time we did a look-ahead, start with that looked-ahead chunk now if (!m_didLookAhead) { ASSERT(!m_textIterator.atEnd()); m_textIterator.advance(); } m_didLookAhead = false; // Go to next non-empty chunk while (!m_textIterator.atEnd() && m_textIterator.length() == 0) m_textIterator.advance(); m_range = m_textIterator.range(); if (m_textIterator.atEnd()) return; while (1) { // If this chunk ends in whitespace we can just use it as our chunk. if (isSpaceOrNewline(m_textIterator.characters()[m_textIterator.length() - 1])) return; // If this is the first chunk that failed, save it in previousText before look ahead if (m_buffer.isEmpty()) { m_previousText = m_textIterator.characters(); m_previousLength = m_textIterator.length(); } // Look ahead to next chunk. If it is whitespace or a break, we can use the previous stuff m_textIterator.advance(); if (m_textIterator.atEnd() || m_textIterator.length() == 0 || isSpaceOrNewline(m_textIterator.characters()[0])) { m_didLookAhead = true; return; } if (m_buffer.isEmpty()) { // Start gobbling chunks until we get to a suitable stopping point m_buffer.append(m_previousText, m_previousLength); m_previousText = 0; } m_buffer.append(m_textIterator.characters(), m_textIterator.length()); int exception = 0; m_range->setEnd(m_textIterator.range()->endContainer(), m_textIterator.range()->endOffset(), exception); } } int WordAwareIterator::length() const { if (!m_buffer.isEmpty()) return m_buffer.size(); if (m_previousText) return m_previousLength; return m_textIterator.length(); } const UChar* WordAwareIterator::characters() const { if (!m_buffer.isEmpty()) return m_buffer.data(); if (m_previousText) return m_previousText; return m_textIterator.characters(); } // -------- static inline UChar foldQuoteMark(UChar c) { switch (c) { case hebrewPunctuationGershayim: case leftDoubleQuotationMark: case rightDoubleQuotationMark: return '"'; case hebrewPunctuationGeresh: case leftSingleQuotationMark: case rightSingleQuotationMark: return '\''; default: return c; } } static inline void foldQuoteMarks(String& s) { s.replace(hebrewPunctuationGeresh, '\''); s.replace(hebrewPunctuationGershayim, '"'); s.replace(leftDoubleQuotationMark, '"'); s.replace(leftSingleQuotationMark, '\''); s.replace(rightDoubleQuotationMark, '"'); s.replace(rightSingleQuotationMark, '\''); } #if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION static inline void foldQuoteMarks(UChar* data, size_t length) { for (size_t i = 0; i < length; ++i) data[i] = foldQuoteMark(data[i]); } static const size_t minimumSearchBufferSize = 8192; #ifndef NDEBUG static bool searcherInUse; #endif static UStringSearch* createSearcher() { // Provide a non-empty pattern and non-empty text so usearch_open will not fail, // but it doesn't matter exactly what it is, since we don't perform any searches // without setting both the pattern and the text. UErrorCode status = U_ZERO_ERROR; UStringSearch* searcher = usearch_open(&newlineCharacter, 1, &newlineCharacter, 1, currentSearchLocaleID(), 0, &status); ASSERT(status == U_ZERO_ERROR || status == U_USING_FALLBACK_WARNING || status == U_USING_DEFAULT_WARNING); return searcher; } static UStringSearch* searcher() { static UStringSearch* searcher = createSearcher(); return searcher; } static inline void lockSearcher() { #ifndef NDEBUG ASSERT(!searcherInUse); searcherInUse = true; #endif } static inline void unlockSearcher() { #ifndef NDEBUG ASSERT(searcherInUse); searcherInUse = false; #endif } // ICU's search ignores the distinction between small kana letters and ones // that are not small, and also characters that differ only in the voicing // marks when considering only primary collation strength diffrences. // This is not helpful for end users, since these differences make words // distinct, so for our purposes we need these to be considered. // The Unicode folks do not think the collation algorithm should be // changed. To work around this, we would like to tailor the ICU searcher, // but we can't get that to work yet. So instead, we check for cases where // these differences occur, and skip those matches. // We refer to the above technique as the "kana workaround". The next few // functions are helper functinos for the kana workaround. static inline bool isKanaLetter(UChar character) { // Hiragana letters. if (character >= 0x3041 && character <= 0x3096) return true; // Katakana letters. if (character >= 0x30A1 && character <= 0x30FA) return true; if (character >= 0x31F0 && character <= 0x31FF) return true; // Halfwidth katakana letters. if (character >= 0xFF66 && character <= 0xFF9D && character != 0xFF70) return true; return false; } static inline bool isSmallKanaLetter(UChar character) { ASSERT(isKanaLetter(character)); switch (character) { case 0x3041: // HIRAGANA LETTER SMALL A case 0x3043: // HIRAGANA LETTER SMALL I case 0x3045: // HIRAGANA LETTER SMALL U case 0x3047: // HIRAGANA LETTER SMALL E case 0x3049: // HIRAGANA LETTER SMALL O case 0x3063: // HIRAGANA LETTER SMALL TU case 0x3083: // HIRAGANA LETTER SMALL YA case 0x3085: // HIRAGANA LETTER SMALL YU case 0x3087: // HIRAGANA LETTER SMALL YO case 0x308E: // HIRAGANA LETTER SMALL WA case 0x3095: // HIRAGANA LETTER SMALL KA case 0x3096: // HIRAGANA LETTER SMALL KE case 0x30A1: // KATAKANA LETTER SMALL A case 0x30A3: // KATAKANA LETTER SMALL I case 0x30A5: // KATAKANA LETTER SMALL U case 0x30A7: // KATAKANA LETTER SMALL E case 0x30A9: // KATAKANA LETTER SMALL O case 0x30C3: // KATAKANA LETTER SMALL TU case 0x30E3: // KATAKANA LETTER SMALL YA case 0x30E5: // KATAKANA LETTER SMALL YU case 0x30E7: // KATAKANA LETTER SMALL YO case 0x30EE: // KATAKANA LETTER SMALL WA case 0x30F5: // KATAKANA LETTER SMALL KA case 0x30F6: // KATAKANA LETTER SMALL KE case 0x31F0: // KATAKANA LETTER SMALL KU case 0x31F1: // KATAKANA LETTER SMALL SI case 0x31F2: // KATAKANA LETTER SMALL SU case 0x31F3: // KATAKANA LETTER SMALL TO case 0x31F4: // KATAKANA LETTER SMALL NU case 0x31F5: // KATAKANA LETTER SMALL HA case 0x31F6: // KATAKANA LETTER SMALL HI case 0x31F7: // KATAKANA LETTER SMALL HU case 0x31F8: // KATAKANA LETTER SMALL HE case 0x31F9: // KATAKANA LETTER SMALL HO case 0x31FA: // KATAKANA LETTER SMALL MU case 0x31FB: // KATAKANA LETTER SMALL RA case 0x31FC: // KATAKANA LETTER SMALL RI case 0x31FD: // KATAKANA LETTER SMALL RU case 0x31FE: // KATAKANA LETTER SMALL RE case 0x31FF: // KATAKANA LETTER SMALL RO case 0xFF67: // HALFWIDTH KATAKANA LETTER SMALL A case 0xFF68: // HALFWIDTH KATAKANA LETTER SMALL I case 0xFF69: // HALFWIDTH KATAKANA LETTER SMALL U case 0xFF6A: // HALFWIDTH KATAKANA LETTER SMALL E case 0xFF6B: // HALFWIDTH KATAKANA LETTER SMALL O case 0xFF6C: // HALFWIDTH KATAKANA LETTER SMALL YA case 0xFF6D: // HALFWIDTH KATAKANA LETTER SMALL YU case 0xFF6E: // HALFWIDTH KATAKANA LETTER SMALL YO case 0xFF6F: // HALFWIDTH KATAKANA LETTER SMALL TU return true; } return false; } enum VoicedSoundMarkType { NoVoicedSoundMark, VoicedSoundMark, SemiVoicedSoundMark }; static inline VoicedSoundMarkType composedVoicedSoundMark(UChar character) { ASSERT(isKanaLetter(character)); switch (character) { case 0x304C: // HIRAGANA LETTER GA case 0x304E: // HIRAGANA LETTER GI case 0x3050: // HIRAGANA LETTER GU case 0x3052: // HIRAGANA LETTER GE case 0x3054: // HIRAGANA LETTER GO case 0x3056: // HIRAGANA LETTER ZA case 0x3058: // HIRAGANA LETTER ZI case 0x305A: // HIRAGANA LETTER ZU case 0x305C: // HIRAGANA LETTER ZE case 0x305E: // HIRAGANA LETTER ZO case 0x3060: // HIRAGANA LETTER DA case 0x3062: // HIRAGANA LETTER DI case 0x3065: // HIRAGANA LETTER DU case 0x3067: // HIRAGANA LETTER DE case 0x3069: // HIRAGANA LETTER DO case 0x3070: // HIRAGANA LETTER BA case 0x3073: // HIRAGANA LETTER BI case 0x3076: // HIRAGANA LETTER BU case 0x3079: // HIRAGANA LETTER BE case 0x307C: // HIRAGANA LETTER BO case 0x3094: // HIRAGANA LETTER VU case 0x30AC: // KATAKANA LETTER GA case 0x30AE: // KATAKANA LETTER GI case 0x30B0: // KATAKANA LETTER GU case 0x30B2: // KATAKANA LETTER GE case 0x30B4: // KATAKANA LETTER GO case 0x30B6: // KATAKANA LETTER ZA case 0x30B8: // KATAKANA LETTER ZI case 0x30BA: // KATAKANA LETTER ZU case 0x30BC: // KATAKANA LETTER ZE case 0x30BE: // KATAKANA LETTER ZO case 0x30C0: // KATAKANA LETTER DA case 0x30C2: // KATAKANA LETTER DI case 0x30C5: // KATAKANA LETTER DU case 0x30C7: // KATAKANA LETTER DE case 0x30C9: // KATAKANA LETTER DO case 0x30D0: // KATAKANA LETTER BA case 0x30D3: // KATAKANA LETTER BI case 0x30D6: // KATAKANA LETTER BU case 0x30D9: // KATAKANA LETTER BE case 0x30DC: // KATAKANA LETTER BO case 0x30F4: // KATAKANA LETTER VU case 0x30F7: // KATAKANA LETTER VA case 0x30F8: // KATAKANA LETTER VI case 0x30F9: // KATAKANA LETTER VE case 0x30FA: // KATAKANA LETTER VO return VoicedSoundMark; case 0x3071: // HIRAGANA LETTER PA case 0x3074: // HIRAGANA LETTER PI case 0x3077: // HIRAGANA LETTER PU case 0x307A: // HIRAGANA LETTER PE case 0x307D: // HIRAGANA LETTER PO case 0x30D1: // KATAKANA LETTER PA case 0x30D4: // KATAKANA LETTER PI case 0x30D7: // KATAKANA LETTER PU case 0x30DA: // KATAKANA LETTER PE case 0x30DD: // KATAKANA LETTER PO return SemiVoicedSoundMark; } return NoVoicedSoundMark; } static inline bool isCombiningVoicedSoundMark(UChar character) { switch (character) { case 0x3099: // COMBINING KATAKANA-HIRAGANA VOICED SOUND MARK case 0x309A: // COMBINING KATAKANA-HIRAGANA SEMI-VOICED SOUND MARK return true; } return false; } static inline bool containsKanaLetters(const String& pattern) { const UChar* characters = pattern.characters(); unsigned length = pattern.length(); for (unsigned i = 0; i < length; ++i) { if (isKanaLetter(characters[i])) return true; } return false; } static void normalizeCharacters(const UChar* characters, unsigned length, Vector& buffer) { ASSERT(length); buffer.resize(length); UErrorCode status = U_ZERO_ERROR; size_t bufferSize = unorm_normalize(characters, length, UNORM_NFC, 0, buffer.data(), length, &status); ASSERT(status == U_ZERO_ERROR || status == U_STRING_NOT_TERMINATED_WARNING || status == U_BUFFER_OVERFLOW_ERROR); ASSERT(bufferSize); buffer.resize(bufferSize); if (status == U_ZERO_ERROR || status == U_STRING_NOT_TERMINATED_WARNING) return; status = U_ZERO_ERROR; unorm_normalize(characters, length, UNORM_NFC, 0, buffer.data(), bufferSize, &status); ASSERT(status == U_STRING_NOT_TERMINATED_WARNING); } inline SearchBuffer::SearchBuffer(const String& target, bool isCaseSensitive) : m_target(target) , m_atBreak(true) , m_targetRequiresKanaWorkaround(containsKanaLetters(m_target)) { ASSERT(!m_target.isEmpty()); // FIXME: We'd like to tailor the searcher to fold quote marks for us instead // of doing it in a separate replacement pass here, but ICU doesn't offer a way // to add tailoring on top of the locale-specific tailoring as of this writing. foldQuoteMarks(m_target); size_t targetLength = m_target.length(); m_buffer.reserveInitialCapacity(max(targetLength * 8, minimumSearchBufferSize)); m_overlap = m_buffer.capacity() / 4; // Grab the single global searcher. // If we ever have a reason to do more than once search buffer at once, we'll have // to move to multiple searchers. lockSearcher(); UStringSearch* searcher = WebCore::searcher(); UCollator* collator = usearch_getCollator(searcher); UCollationStrength strength = isCaseSensitive ? UCOL_TERTIARY : UCOL_PRIMARY; if (ucol_getStrength(collator) != strength) { ucol_setStrength(collator, strength); usearch_reset(searcher); } UErrorCode status = U_ZERO_ERROR; usearch_setPattern(searcher, m_target.characters(), targetLength, &status); ASSERT(status == U_ZERO_ERROR); // The kana workaround requires a normalized copy of the target string. if (m_targetRequiresKanaWorkaround) normalizeCharacters(m_target.characters(), m_target.length(), m_normalizedTarget); } inline SearchBuffer::~SearchBuffer() { unlockSearcher(); } inline size_t SearchBuffer::append(const UChar* characters, size_t length) { ASSERT(length); if (m_atBreak) { m_buffer.shrink(0); m_atBreak = false; } else if (m_buffer.size() == m_buffer.capacity()) { memcpy(m_buffer.data(), m_buffer.data() + m_buffer.size() - m_overlap, m_overlap * sizeof(UChar)); m_buffer.shrink(m_overlap); } size_t oldLength = m_buffer.size(); size_t usableLength = min(m_buffer.capacity() - oldLength, length); ASSERT(usableLength); m_buffer.append(characters, usableLength); foldQuoteMarks(m_buffer.data() + oldLength, usableLength); return usableLength; } inline bool SearchBuffer::atBreak() const { return m_atBreak; } inline void SearchBuffer::reachedBreak() { m_atBreak = true; } inline bool SearchBuffer::isBadMatch(const UChar* match, size_t matchLength) const { // This function implements the kana workaround. If usearch treats // it as a match, but we do not want to, then it's a "bad match". if (!m_targetRequiresKanaWorkaround) return false; // Normalize into a match buffer. We reuse a single buffer rather than // creating a new one each time. normalizeCharacters(match, matchLength, m_normalizedMatch); const UChar* a = m_normalizedTarget.begin(); const UChar* aEnd = m_normalizedTarget.end(); const UChar* b = m_normalizedMatch.begin(); const UChar* bEnd = m_normalizedMatch.end(); while (true) { // Skip runs of non-kana-letter characters. This is necessary so we can // correctly handle strings where the target and match have different-length // runs of characters that match, while still double checking the correctness // of matches of kana letters with other kana letters. while (a != aEnd && !isKanaLetter(*a)) ++a; while (b != bEnd && !isKanaLetter(*b)) ++b; // If we reached the end of either the target or the match, we should have // reached the end of both; both should have the same number of kana letters. if (a == aEnd || b == bEnd) { ASSERT(a == aEnd); ASSERT(b == bEnd); return false; } // Check for differences in the kana letter character itself. if (isSmallKanaLetter(*a) != isSmallKanaLetter(*b)) return true; if (composedVoicedSoundMark(*a) != composedVoicedSoundMark(*b)) return true; ++a; ++b; // Check for differences in combining voiced sound marks found after the letter. while (1) { if (!(a != aEnd && isCombiningVoicedSoundMark(*a))) { if (b != bEnd && isCombiningVoicedSoundMark(*b)) return true; break; } if (!(b != bEnd && isCombiningVoicedSoundMark(*b))) return true; if (*a != *b) return true; ++a; ++b; } } } inline size_t SearchBuffer::search(size_t& start) { size_t size = m_buffer.size(); if (m_atBreak) { if (!size) return 0; } else { if (size != m_buffer.capacity()) return 0; } UStringSearch* searcher = WebCore::searcher(); UErrorCode status = U_ZERO_ERROR; usearch_setText(searcher, m_buffer.data(), size, &status); ASSERT(status == U_ZERO_ERROR); int matchStart = usearch_first(searcher, &status); ASSERT(status == U_ZERO_ERROR); nextMatch: if (!(matchStart >= 0 && static_cast(matchStart) < size)) { ASSERT(matchStart == USEARCH_DONE); return 0; } // Matches that start in the overlap area are only tentative. // The same match may appear later, matching more characters, // possibly including a combining character that's not yet in the buffer. if (!m_atBreak && static_cast(matchStart) >= size - m_overlap) { memcpy(m_buffer.data(), m_buffer.data() + size - m_overlap, m_overlap * sizeof(UChar)); m_buffer.shrink(m_overlap); return 0; } size_t matchedLength = usearch_getMatchedLength(searcher); ASSERT(matchStart + matchedLength <= size); // If this match is "bad", move on to the next match. if (isBadMatch(m_buffer.data() + matchStart, matchedLength)) { matchStart = usearch_next(searcher, &status); ASSERT(status == U_ZERO_ERROR); goto nextMatch; } size_t newSize = size - (matchStart + 1); memmove(m_buffer.data(), m_buffer.data() + matchStart + 1, newSize * sizeof(UChar)); m_buffer.shrink(newSize); start = size - matchStart; return matchedLength; } #else // !ICU_UNICODE inline SearchBuffer::SearchBuffer(const String& target, bool isCaseSensitive) : m_target(isCaseSensitive ? target : target.foldCase()) , m_isCaseSensitive(isCaseSensitive) , m_buffer(m_target.length()) , m_isCharacterStartBuffer(m_target.length()) , m_isBufferFull(false) , m_cursor(0) { ASSERT(!m_target.isEmpty()); m_target.replace(noBreakSpace, ' '); foldQuoteMarks(m_target); } inline SearchBuffer::~SearchBuffer() { } inline void SearchBuffer::reachedBreak() { m_cursor = 0; m_isBufferFull = false; } inline bool SearchBuffer::atBreak() const { return !m_cursor && !m_isBufferFull; } inline void SearchBuffer::append(UChar c, bool isStart) { m_buffer[m_cursor] = c == noBreakSpace ? ' ' : foldQuoteMark(c); m_isCharacterStartBuffer[m_cursor] = isStart; if (++m_cursor == m_target.length()) { m_cursor = 0; m_isBufferFull = true; } } inline size_t SearchBuffer::append(const UChar* characters, size_t length) { ASSERT(length); if (m_isCaseSensitive) { append(characters[0], true); return 1; } const int maxFoldedCharacters = 16; // sensible maximum is 3, this should be more than enough UChar foldedCharacters[maxFoldedCharacters]; bool error; int numFoldedCharacters = foldCase(foldedCharacters, maxFoldedCharacters, characters, 1, &error); ASSERT(!error); ASSERT(numFoldedCharacters); ASSERT(numFoldedCharacters <= maxFoldedCharacters); if (!error && numFoldedCharacters) { numFoldedCharacters = min(numFoldedCharacters, maxFoldedCharacters); append(foldedCharacters[0], true); for (int i = 1; i < numFoldedCharacters; ++i) append(foldedCharacters[i], false); } return 1; } inline size_t SearchBuffer::search(size_t& start) { if (!m_isBufferFull) return 0; if (!m_isCharacterStartBuffer[m_cursor]) return 0; size_t tailSpace = m_target.length() - m_cursor; if (memcmp(&m_buffer[m_cursor], m_target.characters(), tailSpace * sizeof(UChar)) != 0) return 0; if (memcmp(&m_buffer[0], m_target.characters() + tailSpace, m_cursor * sizeof(UChar)) != 0) return 0; start = length(); // Now that we've found a match once, we don't want to find it again, because those // are the SearchBuffer semantics, allowing for a buffer where you append more than one // character at a time. To do this we take advantage of m_isCharacterStartBuffer, but if // we want to get rid of that in the future we could track this with a separate boolean // or even move the characters to the start of the buffer and set m_isBufferFull to false. m_isCharacterStartBuffer[m_cursor] = false; return start; } // Returns the number of characters that were appended to the buffer (what we are searching in). // That's not necessarily the same length as the passed-in target string, because case folding // can make two strings match even though they're not the same length. size_t SearchBuffer::length() const { size_t bufferSize = m_target.length(); size_t length = 0; for (size_t i = 0; i < bufferSize; ++i) length += m_isCharacterStartBuffer[i]; return length; } #endif // !ICU_UNICODE // -------- int TextIterator::rangeLength(const Range* r, bool forSelectionPreservation) { int length = 0; for (TextIterator it(r, forSelectionPreservation); !it.atEnd(); it.advance()) length += it.length(); return length; } PassRefPtr TextIterator::subrange(Range* entireRange, int characterOffset, int characterCount) { CharacterIterator entireRangeIterator(entireRange); return characterSubrange(entireRangeIterator, characterOffset, characterCount); } PassRefPtr TextIterator::rangeFromLocationAndLength(Element* scope, int rangeLocation, int rangeLength, bool forSelectionPreservation) { RefPtr resultRange = scope->document()->createRange(); int docTextPosition = 0; int rangeEnd = rangeLocation + rangeLength; bool startRangeFound = false; RefPtr textRunRange; TextIterator it(rangeOfContents(scope).get(), forSelectionPreservation); // FIXME: the atEnd() check shouldn't be necessary, workaround for . if (rangeLocation == 0 && rangeLength == 0 && it.atEnd()) { textRunRange = it.range(); ExceptionCode ec = 0; resultRange->setStart(textRunRange->startContainer(), 0, ec); ASSERT(!ec); resultRange->setEnd(textRunRange->startContainer(), 0, ec); ASSERT(!ec); return resultRange.release(); } for (; !it.atEnd(); it.advance()) { int len = it.length(); textRunRange = it.range(); bool foundStart = rangeLocation >= docTextPosition && rangeLocation <= docTextPosition + len; bool foundEnd = rangeEnd >= docTextPosition && rangeEnd <= docTextPosition + len; // Fix textRunRange->endPosition(), but only if foundStart || foundEnd, because it is only // in those cases that textRunRange is used. if (foundStart || foundEnd) { // FIXME: This is a workaround for the fact that the end of a run is often at the wrong // position for emitted '\n's. if (len == 1 && it.characters()[0] == '\n') { Position runStart = textRunRange->startPosition(); Position runEnd = VisiblePosition(runStart).next().deepEquivalent(); if (runEnd.isNotNull()) { ExceptionCode ec = 0; textRunRange->setEnd(runEnd.node(), runEnd.deprecatedEditingOffset(), ec); ASSERT(!ec); } } } if (foundStart) { startRangeFound = true; int exception = 0; if (textRunRange->startContainer()->isTextNode()) { int offset = rangeLocation - docTextPosition; resultRange->setStart(textRunRange->startContainer(), offset + textRunRange->startOffset(), exception); } else { if (rangeLocation == docTextPosition) resultRange->setStart(textRunRange->startContainer(), textRunRange->startOffset(), exception); else resultRange->setStart(textRunRange->endContainer(), textRunRange->endOffset(), exception); } } if (foundEnd) { int exception = 0; if (textRunRange->startContainer()->isTextNode()) { int offset = rangeEnd - docTextPosition; resultRange->setEnd(textRunRange->startContainer(), offset + textRunRange->startOffset(), exception); } else { if (rangeEnd == docTextPosition) resultRange->setEnd(textRunRange->startContainer(), textRunRange->startOffset(), exception); else resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset(), exception); } docTextPosition += len; break; } docTextPosition += len; } if (!startRangeFound) return 0; if (rangeLength != 0 && rangeEnd > docTextPosition) { // rangeEnd is out of bounds int exception = 0; resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset(), exception); } return resultRange.release(); } // -------- UChar* plainTextToMallocAllocatedBuffer(const Range* r, unsigned& bufferLength, bool isDisplayString) { UChar* result = 0; // Do this in pieces to avoid massive reallocations if there is a large amount of text. // Use system malloc for buffers since they can consume lots of memory and current TCMalloc is unable return it back to OS. static const unsigned cMaxSegmentSize = 1 << 16; bufferLength = 0; typedef pair TextSegment; Vector* textSegments = 0; Vector textBuffer; textBuffer.reserveInitialCapacity(cMaxSegmentSize); for (TextIterator it(r); !it.atEnd(); it.advance()) { if (textBuffer.size() && textBuffer.size() + it.length() > cMaxSegmentSize) { UChar* newSegmentBuffer = static_cast(malloc(textBuffer.size() * sizeof(UChar))); if (!newSegmentBuffer) goto exit; memcpy(newSegmentBuffer, textBuffer.data(), textBuffer.size() * sizeof(UChar)); if (!textSegments) textSegments = new Vector; textSegments->append(make_pair(newSegmentBuffer, (unsigned)textBuffer.size())); textBuffer.clear(); } textBuffer.append(it.characters(), it.length()); bufferLength += it.length(); } if (!bufferLength) return 0; // Since we know the size now, we can make a single buffer out of the pieces with one big alloc result = static_cast(malloc(bufferLength * sizeof(UChar))); if (!result) goto exit; { UChar* resultPos = result; if (textSegments) { unsigned size = textSegments->size(); for (unsigned i = 0; i < size; ++i) { const TextSegment& segment = textSegments->at(i); memcpy(resultPos, segment.first, segment.second * sizeof(UChar)); resultPos += segment.second; } } memcpy(resultPos, textBuffer.data(), textBuffer.size() * sizeof(UChar)); } exit: if (textSegments) { unsigned size = textSegments->size(); for (unsigned i = 0; i < size; ++i) free(textSegments->at(i).first); delete textSegments; } if (isDisplayString && r->ownerDocument()) r->ownerDocument()->displayBufferModifiedByEncoding(result, bufferLength); return result; } String plainText(const Range* r) { unsigned length; UChar* buf = plainTextToMallocAllocatedBuffer(r, length, false); if (!buf) return ""; String result(buf, length); free(buf); return result; } static inline bool isAllCollapsibleWhitespace(const String& string) { const UChar* characters = string.characters(); unsigned length = string.length(); for (unsigned i = 0; i < length; ++i) { if (!isCollapsibleWhitespace(characters[i])) return false; } return true; } static PassRefPtr collapsedToBoundary(const Range* range, bool forward) { ExceptionCode ec = 0; RefPtr result = range->cloneRange(ec); ASSERT(!ec); result->collapse(!forward, ec); ASSERT(!ec); return result.release(); } static size_t findPlainText(CharacterIterator& it, const String& target, bool forward, bool caseSensitive, size_t& matchStart) { matchStart = 0; size_t matchLength = 0; SearchBuffer buffer(target, caseSensitive); while (!it.atEnd()) { it.advance(buffer.append(it.characters(), it.length())); tryAgain: size_t matchStartOffset; if (size_t newMatchLength = buffer.search(matchStartOffset)) { // Note that we found a match, and where we found it. size_t lastCharacterInBufferOffset = it.characterOffset(); ASSERT(lastCharacterInBufferOffset >= matchStartOffset); matchStart = lastCharacterInBufferOffset - matchStartOffset; matchLength = newMatchLength; // If searching forward, stop on the first match. // If searching backward, don't stop, so we end up with the last match. if (forward) break; goto tryAgain; } if (it.atBreak() && !buffer.atBreak()) { buffer.reachedBreak(); goto tryAgain; } } return matchLength; } PassRefPtr findPlainText(const Range* range, const String& target, bool forward, bool caseSensitive) { // First, find the text. size_t matchStart; size_t matchLength; { CharacterIterator findIterator(range, false, true); matchLength = findPlainText(findIterator, target, forward, caseSensitive, matchStart); if (!matchLength) return collapsedToBoundary(range, forward); } // Then, find the document position of the start and the end of the text. CharacterIterator computeRangeIterator(range, false, true); return characterSubrange(computeRangeIterator, matchStart, matchLength); } }