#include "config.h"
#include "TextIterator.h"
#include "CharacterNames.h"
#include "Document.h"
#include "HTMLElement.h"
#include "HTMLNames.h"
#include "htmlediting.h"
#include "InlineTextBox.h"
#include "Range.h"
#include "RenderTableCell.h"
#include "RenderTableRow.h"
#include "RenderTextControl.h"
#include "VisiblePosition.h"
#include "visible_units.h"
#if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION
#include "TextBreakIteratorInternalICU.h"
#include <unicode/usearch.h>
#endif
using namespace WTF::Unicode;
using namespace std;
namespace WebCore {
using namespace HTMLNames;
class SearchBuffer : public Noncopyable {
public:
SearchBuffer(const String& target, bool isCaseSensitive);
~SearchBuffer();
size_t append(const UChar*, size_t length);
void reachedBreak();
size_t search(size_t& startOffset);
bool atBreak() const;
#if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION
private:
bool isBadMatch(const UChar*, size_t length) const;
String m_target;
Vector<UChar> m_buffer;
size_t m_overlap;
bool m_atBreak;
bool m_targetRequiresKanaWorkaround;
Vector<UChar> m_normalizedTarget;
mutable Vector<UChar> m_normalizedMatch;
#else
private:
void append(UChar, bool isCharacterStart);
size_t length() const;
String m_target;
bool m_isCaseSensitive;
Vector<UChar> m_buffer;
Vector<bool> m_isCharacterStartBuffer;
bool m_isBufferFull;
size_t m_cursor;
#endif
};
static const unsigned bitsInWord = sizeof(unsigned) * 8;
static const unsigned bitInWordMask = bitsInWord - 1;
BitStack::BitStack()
: m_size(0)
{
}
void BitStack::push(bool bit)
{
unsigned index = m_size / bitsInWord;
unsigned shift = m_size & bitInWordMask;
if (!shift && index == m_words.size()) {
m_words.grow(index + 1);
m_words[index] = 0;
}
unsigned& word = m_words[index];
unsigned mask = 1U << shift;
if (bit)
word |= mask;
else
word &= ~mask;
++m_size;
}
void BitStack::pop()
{
if (m_size)
--m_size;
}
bool BitStack::top() const
{
if (!m_size)
return false;
unsigned shift = (m_size - 1) & bitInWordMask;
return m_words.last() & (1U << shift);
}
unsigned BitStack::size() const
{
return m_size;
}
static inline Node* parentCrossingShadowBoundaries(Node* node)
{
if (Node* parent = node->parentNode())
return parent;
return node->shadowParentNode();
}
#if !ASSERT_DISABLED
static unsigned depthCrossingShadowBoundaries(Node* node)
{
unsigned depth = 0;
for (Node* parent = parentCrossingShadowBoundaries(node); parent; parent = parentCrossingShadowBoundaries(parent))
++depth;
return depth;
}
#endif
static Node* nextInPreOrderCrossingShadowBoundaries(Node* rangeEndContainer, int rangeEndOffset)
{
if (!rangeEndContainer)
return 0;
if (rangeEndOffset >= 0 && !rangeEndContainer->offsetInCharacters()) {
if (Node* next = rangeEndContainer->childNode(rangeEndOffset))
return next;
}
for (Node* node = rangeEndContainer; node; node = parentCrossingShadowBoundaries(node)) {
if (Node* next = node->nextSibling())
return next;
}
return 0;
}
static Node* previousInPostOrderCrossingShadowBoundaries(Node* rangeStartContainer, int rangeStartOffset)
{
if (!rangeStartContainer)
return 0;
if (rangeStartOffset > 0 && !rangeStartContainer->offsetInCharacters()) {
if (Node* previous = rangeStartContainer->childNode(rangeStartOffset - 1))
return previous;
}
for (Node* node = rangeStartContainer; node; node = parentCrossingShadowBoundaries(node)) {
if (Node* previous = node->previousSibling())
return previous;
}
return 0;
}
static inline bool fullyClipsContents(Node* node)
{
RenderObject* renderer = node->renderer();
if (!renderer || !renderer->isBox() || !renderer->hasOverflowClip())
return false;
return toRenderBox(renderer)->size().isEmpty();
}
static inline bool ignoresContainerClip(Node* node)
{
RenderObject* renderer = node->renderer();
if (!renderer || renderer->isText())
return false;
EPosition position = renderer->style()->position();
return position == AbsolutePosition || position == FixedPosition;
}
static void pushFullyClippedState(BitStack& stack, Node* node)
{
ASSERT(stack.size() == depthCrossingShadowBoundaries(node));
stack.push(fullyClipsContents(node) || (stack.top() && !ignoresContainerClip(node)));
}
static void setUpFullyClippedStack(BitStack& stack, Node* node)
{
Vector<Node*, 100> ancestry;
for (Node* parent = parentCrossingShadowBoundaries(node); parent; parent = parentCrossingShadowBoundaries(parent))
ancestry.append(parent);
size_t size = ancestry.size();
for (size_t i = 0; i < size; ++i)
pushFullyClippedState(stack, ancestry[size - i - 1]);
pushFullyClippedState(stack, node);
ASSERT(stack.size() == 1 + depthCrossingShadowBoundaries(node));
}
TextIterator::TextIterator()
: m_startContainer(0)
, m_startOffset(0)
, m_endContainer(0)
, m_endOffset(0)
, m_positionNode(0)
, m_textCharacters(0)
, m_textLength(0)
, m_lastCharacter(0)
, m_emitCharactersBetweenAllVisiblePositions(false)
, m_enterTextControls(false)
{
}
TextIterator::TextIterator(const Range* r, bool emitCharactersBetweenAllVisiblePositions, bool enterTextControls)
: m_startContainer(0)
, m_startOffset(0)
, m_endContainer(0)
, m_endOffset(0)
, m_positionNode(0)
, m_textCharacters(0)
, m_textLength(0)
, m_emitCharactersBetweenAllVisiblePositions(emitCharactersBetweenAllVisiblePositions)
, m_enterTextControls(enterTextControls)
{
if (!r)
return;
Node* startContainer = r->startContainer();
if (!startContainer)
return;
int startOffset = r->startOffset();
Node* endContainer = r->endContainer();
int endOffset = r->endOffset();
ASSERT(r->boundaryPointsValid());
m_startContainer = startContainer;
m_startOffset = startOffset;
m_endContainer = endContainer;
m_endOffset = endOffset;
m_node = r->firstNode();
if (!m_node)
return;
setUpFullyClippedStack(m_fullyClippedStack, m_node);
m_offset = m_node == m_startContainer ? m_startOffset : 0;
m_handledNode = false;
m_handledChildren = false;
m_pastEndNode = nextInPreOrderCrossingShadowBoundaries(endContainer, endOffset);
m_needAnotherNewline = false;
m_textBox = 0;
m_haveEmitted = false;
m_lastTextNode = 0;
m_lastTextNodeEndedWithCollapsedSpace = false;
m_lastCharacter = 0;
#ifndef NDEBUG
m_positionNode = m_node;
#endif
advance();
}
void TextIterator::advance()
{
m_positionNode = 0;
m_textLength = 0;
if (m_needAnotherNewline) {
Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;
emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
m_needAnotherNewline = false;
return;
}
if (m_textBox) {
handleTextBox();
if (m_positionNode)
return;
}
while (m_node && m_node != m_pastEndNode) {
if (m_node == m_endContainer && m_endOffset == 0) {
representNodeOffsetZero();
m_node = 0;
return;
}
RenderObject* renderer = m_node->renderer();
if (!renderer) {
m_handledNode = true;
m_handledChildren = true;
} else {
if (!m_handledNode) {
if (renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) m_handledNode = handleTextNode();
else if (renderer && (renderer->isImage() || renderer->isWidget() ||
(renderer->node() && renderer->node()->isElementNode() &&
static_cast<Element*>(renderer->node())->isFormControlElement())))
m_handledNode = handleReplacedElement();
else
m_handledNode = handleNonTextNode();
if (m_positionNode)
return;
}
}
Node* next = m_handledChildren ? 0 : m_node->firstChild();
m_offset = 0;
if (!next) {
next = m_node->nextSibling();
if (!next) {
bool pastEnd = m_node->traverseNextNode() == m_pastEndNode;
Node* parentNode = parentCrossingShadowBoundaries(m_node);
while (!next && parentNode) {
if ((pastEnd && parentNode == m_endContainer) || m_endContainer->isDescendantOf(parentNode))
return;
bool haveRenderer = m_node->renderer();
m_node = parentNode;
m_fullyClippedStack.pop();
parentNode = parentCrossingShadowBoundaries(m_node);
if (haveRenderer)
exitNode();
if (m_positionNode) {
m_handledNode = true;
m_handledChildren = true;
return;
}
next = m_node->nextSibling();
}
}
m_fullyClippedStack.pop();
}
m_node = next;
if (m_node)
pushFullyClippedState(m_fullyClippedStack, m_node);
m_handledNode = false;
m_handledChildren = false;
if (m_positionNode)
return;
}
}
static inline bool compareBoxStart(const InlineTextBox* first, const InlineTextBox* second)
{
return first->start() < second->start();
}
bool TextIterator::handleTextNode()
{
if (m_fullyClippedStack.top())
return false;
RenderText* renderer = toRenderText(m_node->renderer());
if (renderer->style()->visibility() != VISIBLE)
return false;
m_lastTextNode = m_node;
String str = renderer->text();
if (!renderer->style()->collapseWhiteSpace()) {
int runStart = m_offset;
if (m_lastTextNodeEndedWithCollapsedSpace) {
emitCharacter(' ', m_node, 0, runStart, runStart);
return false;
}
int strLength = str.length();
int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;
int runEnd = min(strLength, end);
if (runStart >= runEnd)
return true;
emitText(m_node, runStart, runEnd);
return true;
}
if (!renderer->firstTextBox() && str.length() > 0) {
m_lastTextNodeEndedWithCollapsedSpace = true; return true;
}
if (renderer->containsReversedText()) {
m_sortedTextBoxes.clear();
for (InlineTextBox* textBox = renderer->firstTextBox(); textBox; textBox = textBox->nextTextBox()) {
m_sortedTextBoxes.append(textBox);
}
std::sort(m_sortedTextBoxes.begin(), m_sortedTextBoxes.end(), compareBoxStart);
m_sortedTextBoxesPosition = 0;
}
m_textBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();
handleTextBox();
return true;
}
void TextIterator::handleTextBox()
{
RenderText* renderer = toRenderText(m_node->renderer());
String str = renderer->text();
int start = m_offset;
int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;
while (m_textBox) {
int textBoxStart = m_textBox->start();
int runStart = max(textBoxStart, start);
InlineTextBox* firstTextBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();
bool needSpace = m_lastTextNodeEndedWithCollapsedSpace
|| (m_textBox == firstTextBox && textBoxStart == runStart && runStart > 0);
if (needSpace && !isCollapsibleWhitespace(m_lastCharacter) && m_lastCharacter) {
if (m_lastTextNode == m_node && runStart > 0 && str[runStart - 1] == ' ') {
unsigned spaceRunStart = runStart - 1;
while (spaceRunStart > 0 && str[spaceRunStart - 1] == ' ')
--spaceRunStart;
emitText(m_node, spaceRunStart, spaceRunStart + 1);
} else
emitCharacter(' ', m_node, 0, runStart, runStart);
return;
}
int textBoxEnd = textBoxStart + m_textBox->len();
int runEnd = min(textBoxEnd, end);
InlineTextBox* nextTextBox = 0;
if (renderer->containsReversedText()) {
if (m_sortedTextBoxesPosition + 1 < m_sortedTextBoxes.size())
nextTextBox = m_sortedTextBoxes[m_sortedTextBoxesPosition + 1];
} else
nextTextBox = m_textBox->nextTextBox();
if (runStart < runEnd) {
if (str[runStart] == '\n') {
emitCharacter(' ', m_node, 0, runStart, runStart + 1);
m_offset = runStart + 1;
} else {
int subrunEnd = str.find('\n', runStart);
if (subrunEnd == -1 || subrunEnd > runEnd)
subrunEnd = runEnd;
m_offset = subrunEnd;
emitText(m_node, runStart, subrunEnd);
}
if (m_positionEndOffset < textBoxEnd)
return;
int nextRunStart = nextTextBox ? nextTextBox->start() : str.length();
if (nextRunStart > runEnd)
m_lastTextNodeEndedWithCollapsedSpace = true; m_textBox = nextTextBox;
if (renderer->containsReversedText())
++m_sortedTextBoxesPosition;
return;
}
m_textBox = nextTextBox;
if (renderer->containsReversedText())
++m_sortedTextBoxesPosition;
}
}
bool TextIterator::handleReplacedElement()
{
if (m_fullyClippedStack.top())
return false;
RenderObject* renderer = m_node->renderer();
if (renderer->style()->visibility() != VISIBLE)
return false;
if (m_lastTextNodeEndedWithCollapsedSpace) {
emitCharacter(' ', m_lastTextNode->parentNode(), m_lastTextNode, 1, 1);
return false;
}
if (m_enterTextControls && renderer->isTextControl()) {
if (HTMLElement* innerTextElement = toRenderTextControl(renderer)->innerTextElement()) {
m_node = innerTextElement->shadowTreeRootNode();
pushFullyClippedState(m_fullyClippedStack, m_node);
m_offset = 0;
return false;
}
}
m_haveEmitted = true;
if (m_emitCharactersBetweenAllVisiblePositions) {
emitCharacter(',', m_node->parentNode(), m_node, 0, 1);
return true;
}
m_positionNode = m_node->parentNode();
m_positionOffsetBaseNode = m_node;
m_positionStartOffset = 0;
m_positionEndOffset = 1;
m_textCharacters = 0;
m_textLength = 0;
m_lastCharacter = 0;
return true;
}
static bool shouldEmitTabBeforeNode(Node* node)
{
RenderObject* r = node->renderer();
if (!r || !isTableCell(node))
return false;
RenderTableCell* rc = toRenderTableCell(r);
RenderTable* t = rc->table();
return t && (t->cellBefore(rc) || t->cellAbove(rc));
}
static bool shouldEmitNewlineForNode(Node* node)
{
RenderObject* r = node->renderer();
if (!r)
return node->hasTagName(brTag);
return r->isBR();
}
static bool shouldEmitNewlinesBeforeAndAfterNode(Node* node)
{
RenderObject* r = node->renderer();
if (!r) {
return (node->hasTagName(blockquoteTag)
|| node->hasTagName(ddTag)
|| node->hasTagName(divTag)
|| node->hasTagName(dlTag)
|| node->hasTagName(dtTag)
|| node->hasTagName(h1Tag)
|| node->hasTagName(h2Tag)
|| node->hasTagName(h3Tag)
|| node->hasTagName(h4Tag)
|| node->hasTagName(h5Tag)
|| node->hasTagName(h6Tag)
|| node->hasTagName(hrTag)
|| node->hasTagName(liTag)
|| node->hasTagName(listingTag)
|| node->hasTagName(olTag)
|| node->hasTagName(pTag)
|| node->hasTagName(preTag)
|| node->hasTagName(trTag)
|| node->hasTagName(ulTag));
}
if (isTableCell(node))
return false;
if (r->isTableRow()) {
RenderTable* t = toRenderTableRow(r)->table();
if (t && !t->isInline())
return true;
}
return !r->isInline() && r->isRenderBlock() && !r->isFloatingOrPositioned() && !r->isBody();
}
static bool shouldEmitNewlineAfterNode(Node* node)
{
if (!shouldEmitNewlinesBeforeAndAfterNode(node))
return false;
while ((node = node->traverseNextSibling()))
if (node->renderer())
return true;
return false;
}
static bool shouldEmitNewlineBeforeNode(Node* node)
{
return shouldEmitNewlinesBeforeAndAfterNode(node);
}
static bool shouldEmitExtraNewlineForNode(Node* node)
{
RenderObject* r = node->renderer();
if (!r || !r->isBox())
return false;
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;
}
bool TextIterator::shouldRepresentNodeOffsetZero()
{
if (m_emitCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isTable())
return true;
if (m_lastCharacter == '\n')
return false;
if (m_haveEmitted)
return true;
if (m_node == m_startContainer)
return false;
if (!m_node->isDescendantOf(m_startContainer))
return true;
if (m_startOffset == 0)
return false;
if (!m_node->renderer() || m_node->renderer()->style()->visibility() != VISIBLE)
return false;
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()
{
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()
{
if (!m_haveEmitted)
return;
Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;
if (m_lastTextNode && shouldEmitNewlineAfterNode(m_node)) {
bool addNewline = shouldEmitExtraNewlineForNode(m_node);
if (m_lastCharacter != '\n') {
emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
ASSERT(!m_needAnotherNewline);
m_needAnotherNewline = addNewline;
} else if (addNewline)
emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
}
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;
m_positionNode = textNode;
m_positionOffsetBaseNode = offsetBaseNode;
m_positionStartOffset = textStartOffset;
m_positionEndOffset = textEndOffset;
m_singleCharacterBuffer = c;
m_textCharacters = &m_singleCharacterBuffer;
m_textLength = 1;
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<Range> TextIterator::range() const
{
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);
}
if (m_endContainer)
return Range::create(m_endContainer->document(), m_endContainer, m_endOffset, m_endContainer, m_endOffset);
return 0;
}
Node* TextIterator::node() const
{
RefPtr<Range> 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<int>(startNode->childNodeCount())) {
startNode = startNode->childNode(startOffset);
startOffset = 0;
}
}
if (!endNode->offsetInCharacters()) {
if (endOffset > 0 && endOffset <= static_cast<int>(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
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) {
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) {
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) {
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;
}
}
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);
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();
emitCharacter(',', m_node->parentNode(), index, index + 1);
return true;
}
bool SimplifiedBackwardsTextIterator::handleNonTextNode()
{
if (shouldEmitNewlineForNode(m_node) || shouldEmitNewlineAfterNode(m_node) || shouldEmitTabBeforeNode(m_node)) {
unsigned index = m_node->nodeIndex();
emitCharacter('\n', m_node->parentNode(), index + 1, index + 1);
}
return true;
}
void SimplifiedBackwardsTextIterator::exitNode()
{
if (shouldEmitNewlineForNode(m_node) || shouldEmitNewlineBeforeNode(m_node) || shouldEmitTabBeforeNode(m_node)) {
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<Range> 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<Range> CharacterIterator::range() const
{
RefPtr<Range> 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;
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;
}
String CharacterIterator::string(int numChars)
{
Vector<UChar> 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<Range> characterSubrange(CharacterIterator& it, int offset, int length)
{
it.advance(offset);
RefPtr<Range> start = it.range();
if (length > 1)
it.advance(length - 1);
RefPtr<Range> 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<Range> BackwardsCharacterIterator::range() const
{
RefPtr<Range> 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) , m_textIterator(r)
{
advance(); }
void WordAwareIterator::advance()
{
m_previousText = 0;
m_buffer.clear();
if (!m_didLookAhead) {
ASSERT(!m_textIterator.atEnd());
m_textIterator.advance();
}
m_didLookAhead = false;
while (!m_textIterator.atEnd() && m_textIterator.length() == 0)
m_textIterator.advance();
m_range = m_textIterator.range();
if (m_textIterator.atEnd())
return;
while (1) {
if (isSpaceOrNewline(m_textIterator.characters()[m_textIterator.length() - 1]))
return;
if (m_buffer.isEmpty()) {
m_previousText = m_textIterator.characters();
m_previousLength = m_textIterator.length();
}
m_textIterator.advance();
if (m_textIterator.atEnd() || m_textIterator.length() == 0 || isSpaceOrNewline(m_textIterator.characters()[0])) {
m_didLookAhead = true;
return;
}
if (m_buffer.isEmpty()) {
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()
{
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
}
static inline bool isKanaLetter(UChar character)
{
if (character >= 0x3041 && character <= 0x3096)
return true;
if (character >= 0x30A1 && character <= 0x30FA)
return true;
if (character >= 0x31F0 && character <= 0x31FF)
return true;
if (character >= 0xFF66 && character <= 0xFF9D && character != 0xFF70)
return true;
return false;
}
static inline bool isSmallKanaLetter(UChar character)
{
ASSERT(isKanaLetter(character));
switch (character) {
case 0x3041: case 0x3043: case 0x3045: case 0x3047: case 0x3049: case 0x3063: case 0x3083: case 0x3085: case 0x3087: case 0x308E: case 0x3095: case 0x3096: case 0x30A1: case 0x30A3: case 0x30A5: case 0x30A7: case 0x30A9: case 0x30C3: case 0x30E3: case 0x30E5: case 0x30E7: case 0x30EE: case 0x30F5: case 0x30F6: case 0x31F0: case 0x31F1: case 0x31F2: case 0x31F3: case 0x31F4: case 0x31F5: case 0x31F6: case 0x31F7: case 0x31F8: case 0x31F9: case 0x31FA: case 0x31FB: case 0x31FC: case 0x31FD: case 0x31FE: case 0x31FF: case 0xFF67: case 0xFF68: case 0xFF69: case 0xFF6A: case 0xFF6B: case 0xFF6C: case 0xFF6D: case 0xFF6E: case 0xFF6F: return true;
}
return false;
}
enum VoicedSoundMarkType { NoVoicedSoundMark, VoicedSoundMark, SemiVoicedSoundMark };
static inline VoicedSoundMarkType composedVoicedSoundMark(UChar character)
{
ASSERT(isKanaLetter(character));
switch (character) {
case 0x304C: case 0x304E: case 0x3050: case 0x3052: case 0x3054: case 0x3056: case 0x3058: case 0x305A: case 0x305C: case 0x305E: case 0x3060: case 0x3062: case 0x3065: case 0x3067: case 0x3069: case 0x3070: case 0x3073: case 0x3076: case 0x3079: case 0x307C: case 0x3094: case 0x30AC: case 0x30AE: case 0x30B0: case 0x30B2: case 0x30B4: case 0x30B6: case 0x30B8: case 0x30BA: case 0x30BC: case 0x30BE: case 0x30C0: case 0x30C2: case 0x30C5: case 0x30C7: case 0x30C9: case 0x30D0: case 0x30D3: case 0x30D6: case 0x30D9: case 0x30DC: case 0x30F4: case 0x30F7: case 0x30F8: case 0x30F9: case 0x30FA: return VoicedSoundMark;
case 0x3071: case 0x3074: case 0x3077: case 0x307A: case 0x307D: case 0x30D1: case 0x30D4: case 0x30D7: case 0x30DA: case 0x30DD: return SemiVoicedSoundMark;
}
return NoVoicedSoundMark;
}
static inline bool isCombiningVoicedSoundMark(UChar character)
{
switch (character) {
case 0x3099: case 0x309A: 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<UChar>& 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());
foldQuoteMarks(m_target);
size_t targetLength = m_target.length();
m_buffer.reserveInitialCapacity(max(targetLength * 8, minimumSearchBufferSize));
m_overlap = m_buffer.capacity() / 4;
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);
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
{
if (!m_targetRequiresKanaWorkaround)
return false;
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) {
while (a != aEnd && !isKanaLetter(*a))
++a;
while (b != bEnd && !isKanaLetter(*b))
++b;
if (a == aEnd || b == bEnd) {
ASSERT(a == aEnd);
ASSERT(b == bEnd);
return false;
}
if (isSmallKanaLetter(*a) != isSmallKanaLetter(*b))
return true;
if (composedVoicedSoundMark(*a) != composedVoicedSoundMark(*b))
return true;
++a;
++b;
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<size_t>(matchStart) < size)) {
ASSERT(matchStart == USEARCH_DONE);
return 0;
}
if (!m_atBreak && static_cast<size_t>(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 (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; 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();
m_isCharacterStartBuffer[m_cursor] = false;
return start;
}
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<Range> TextIterator::subrange(Range* entireRange, int characterOffset, int characterCount)
{
CharacterIterator entireRangeIterator(entireRange);
return characterSubrange(entireRangeIterator, characterOffset, characterCount);
}
PassRefPtr<Range> TextIterator::rangeFromLocationAndLength(Element* scope, int rangeLocation, int rangeLength, bool forSelectionPreservation)
{
RefPtr<Range> resultRange = scope->document()->createRange();
int docTextPosition = 0;
int rangeEnd = rangeLocation + rangeLength;
bool startRangeFound = false;
RefPtr<Range> textRunRange;
TextIterator it(rangeOfContents(scope).get(), forSelectionPreservation);
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;
if (foundStart || foundEnd) {
if (len == 1 && it.characters()[0] == '\n') {
Position runStart = textRunRange->startPosition();
Position runEnd = rangeCompliantEquivalent(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) { 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;
static const unsigned cMaxSegmentSize = 1 << 16;
bufferLength = 0;
typedef pair<UChar*, unsigned> TextSegment;
Vector<TextSegment>* textSegments = 0;
Vector<UChar> textBuffer;
textBuffer.reserveInitialCapacity(cMaxSegmentSize);
for (TextIterator it(r); !it.atEnd(); it.advance()) {
if (textBuffer.size() && textBuffer.size() + it.length() > cMaxSegmentSize) {
UChar* newSegmentBuffer = static_cast<UChar*>(malloc(textBuffer.size() * sizeof(UChar)));
if (!newSegmentBuffer)
goto exit;
memcpy(newSegmentBuffer, textBuffer.data(), textBuffer.size() * sizeof(UChar));
if (!textSegments)
textSegments = new Vector<TextSegment>;
textSegments->append(make_pair(newSegmentBuffer, (unsigned)textBuffer.size()));
textBuffer.clear();
}
textBuffer.append(it.characters(), it.length());
bufferLength += it.length();
}
if (!bufferLength)
return 0;
result = static_cast<UChar*>(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<Range> collapsedToBoundary(const Range* range, bool forward)
{
ExceptionCode ec = 0;
RefPtr<Range> 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)) {
size_t lastCharacterInBufferOffset = it.characterOffset();
ASSERT(lastCharacterInBufferOffset >= matchStartOffset);
matchStart = lastCharacterInBufferOffset - matchStartOffset;
matchLength = newMatchLength;
if (forward)
break;
goto tryAgain;
}
if (it.atBreak() && !buffer.atBreak()) {
buffer.reachedBreak();
goto tryAgain;
}
}
return matchLength;
}
PassRefPtr<Range> findPlainText(const Range* range, const String& target, bool forward, bool caseSensitive)
{
size_t matchStart;
size_t matchLength;
{
CharacterIterator findIterator(range, false, true);
matchLength = findPlainText(findIterator, target, forward, caseSensitive, matchStart);
if (!matchLength)
return collapsedToBoundary(range, forward);
}
CharacterIterator computeRangeIterator(range, false, true);
return characterSubrange(computeRangeIterator, matchStart, matchLength);
}
}