Reviewed by Darin and then Sam.
authorweinig <weinig@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 20 Feb 2007 16:00:18 +0000 (16:00 +0000)
committerweinig <weinig@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 20 Feb 2007 16:00:18 +0000 (16:00 +0000)
        - fix http://bugs.webkit.org/show_bug.cgi?id=10735
          Clicking in SVG results causes WebKit to consume 100% CPU for several minutes

        No test since there is no change in functionality.

        * CMakeLists.txt:
        * WebCore.pro:
        * WebCore.xcodeproj/project.pbxproj: Added PositionIterator.{cpp,h}.
        * WebCoreSources.bkl:
        * dom/Position.cpp:
        (WebCore::Position::Position): Added converting constructor from
        PositionIterator.
        (WebCore::Position::previous): Changed assert() to ASSERT().
        (WebCore::Position::next): Ditto.
        (WebCore::isStreamer): Changed the argument to a PositionIterator.
        (WebCore::Position::upstream): Changed to use PositionIterator.
        (WebCore::Position::downstream): Ditto.
        (WebCore::Position::inRenderedText): Made public.
        (WebCore::Position::hasRenderedNonAnonymousDescendantsWithHeight): Changed
        into a static member function.
        (WebCore::Position::nodeIsUserSelectNone): Ditto.
        * dom/Position.h:
        * dom/PositionIterator.cpp: Added. A Position iterator with constant-time
        increment, decrement, and several predicates on the Position it is at.
        Conversion to/from Position is O(n) in the offset.
        (WebCore::PositionIterator::increment):
        (WebCore::PositionIterator::decrement):
        (WebCore::PositionIterator::atStart):
        (WebCore::PositionIterator::atEnd):
        (WebCore::PositionIterator::atStartOfNode):
        (WebCore::PositionIterator::atEndOfNode):
        (WebCore::PositionIterator::isCandidate):
        * dom/PositionIterator.h: Added.
        (WebCore::PositionIterator::PositionIterator):
        (WebCore::PositionIterator::node):
        (WebCore::PositionIterator::offsetInLeafNode):
        * editing/htmlediting.cpp:
        (WebCore::nextCandidate): Changed to use PositionIterator.
        (WebCore::previousCandidate): Changed to use PositionIterator.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@19734 268f45cc-cd09-0410-ab3c-d52691b4dbfc

WebCore/CMakeLists.txt
WebCore/ChangeLog
WebCore/WebCore.pro
WebCore/WebCore.xcodeproj/project.pbxproj
WebCore/WebCoreSources.bkl
WebCore/dom/Position.cpp
WebCore/dom/Position.h
WebCore/dom/PositionIterator.cpp [new file with mode: 0644]
WebCore/dom/PositionIterator.h [new file with mode: 0644]
WebCore/editing/htmlediting.cpp

index 6c35a0b..77524bb 100644 (file)
@@ -791,6 +791,7 @@ set(WebCore_SRCS
     dom/Notation.cpp
     dom/OverflowEvent.cpp
     dom/Position.cpp
+    dom/PositionIterator.cpp
     dom/ProcessingInstruction.cpp
     dom/QualifiedName.cpp
     dom/Range.cpp
index eb5f405..c7fe535 100644 (file)
@@ -1,3 +1,47 @@
+2007-02-20  Mitz Pettel  <mitz@webkit.org>
+
+        Reviewed by Darin and then Sam.
+
+        - fix http://bugs.webkit.org/show_bug.cgi?id=10735
+          Clicking in SVG results causes WebKit to consume 100% CPU for several minutes
+
+        No test since there is no change in functionality.
+
+        * CMakeLists.txt:
+        * WebCore.pro:
+        * WebCore.xcodeproj/project.pbxproj: Added PositionIterator.{cpp,h}.
+        * WebCoreSources.bkl:
+        * dom/Position.cpp:
+        (WebCore::Position::Position): Added converting constructor from
+        PositionIterator.
+        (WebCore::Position::previous): Changed assert() to ASSERT().
+        (WebCore::Position::next): Ditto.
+        (WebCore::isStreamer): Changed the argument to a PositionIterator.
+        (WebCore::Position::upstream): Changed to use PositionIterator.
+        (WebCore::Position::downstream): Ditto.
+        (WebCore::Position::inRenderedText): Made public.
+        (WebCore::Position::hasRenderedNonAnonymousDescendantsWithHeight): Changed
+        into a static member function.
+        (WebCore::Position::nodeIsUserSelectNone): Ditto.
+        * dom/Position.h:
+        * dom/PositionIterator.cpp: Added. A Position iterator with constant-time
+        increment, decrement, and several predicates on the Position it is at.
+        Conversion to/from Position is O(n) in the offset.
+        (WebCore::PositionIterator::increment):
+        (WebCore::PositionIterator::decrement):
+        (WebCore::PositionIterator::atStart):
+        (WebCore::PositionIterator::atEnd):
+        (WebCore::PositionIterator::atStartOfNode):
+        (WebCore::PositionIterator::atEndOfNode):
+        (WebCore::PositionIterator::isCandidate):
+        * dom/PositionIterator.h: Added.
+        (WebCore::PositionIterator::PositionIterator):
+        (WebCore::PositionIterator::node):
+        (WebCore::PositionIterator::offsetInLeafNode):
+        * editing/htmlediting.cpp:
+        (WebCore::nextCandidate): Changed to use PositionIterator.
+        (WebCore::previousCandidate): Changed to use PositionIterator.
+
 2007-02-20  Rob Buis  <buis@kde.org>
 
         Reviewed by Darin.
index 049ae83..48c9a06 100644 (file)
@@ -319,6 +319,7 @@ SOURCES += \
     dom/Notation.cpp \
     dom/OverflowEvent.cpp \
     dom/Position.cpp \
+    dom/PositionIterator.cpp \
     dom/ProcessingInstruction.cpp \
     dom/QualifiedName.cpp \
     dom/Range.cpp \
index f35a439..d6cae25 100644 (file)
                1CFCEED50AACC66900348750 /* DOMHTMLOptionsCollectionPrivate.h in Copy Generated Headers */ = {isa = PBXBuildFile; fileRef = 1CFCEED40AACC65D00348750 /* DOMHTMLOptionsCollectionPrivate.h */; };
                1CFCEEDF0AACC6A300348750 /* DOMHTMLPreElementPrivate.h in Copy Generated Headers */ = {isa = PBXBuildFile; fileRef = 1CFCEEDA0AACC68300348750 /* DOMHTMLPreElementPrivate.h */; };
                1CFCEEFA0AACC7A700348750 /* DOMHTMLInputElementPrivate.h in Copy Generated Headers */ = {isa = PBXBuildFile; fileRef = 1CFCEEF90AACC79000348750 /* DOMHTMLInputElementPrivate.h */; };
+               37919C230B7D188600A56998 /* PositionIterator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 37919C210B7D188600A56998 /* PositionIterator.cpp */; };
+               37919C240B7D188600A56998 /* PositionIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = 37919C220B7D188600A56998 /* PositionIterator.h */; settings = {ATTRIBUTES = (); }; };
                448A29BF0A46D9CB0030759F /* JSHTMLOptionsCollection.h in Headers */ = {isa = PBXBuildFile; fileRef = 448A29BD0A46D9CB0030759F /* JSHTMLOptionsCollection.h */; };
                448A29C00A46D9CB0030759F /* JSHTMLOptionsCollection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 448A29BE0A46D9CB0030759F /* JSHTMLOptionsCollection.cpp */; };
                448AD27C0A48137A0023D179 /* JSHTMLOptionsCollectionCustom.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 448AD27A0A4813790023D179 /* JSHTMLOptionsCollectionCustom.cpp */; };
                1CFCEEF90AACC79000348750 /* DOMHTMLInputElementPrivate.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DOMHTMLInputElementPrivate.h; sourceTree = "<group>"; };
                2D90660B0665D937006B6F1A /* ClipboardMac.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = ClipboardMac.h; sourceTree = "<group>"; tabWidth = 8; usesTabs = 0; };
                2D90660C0665D937006B6F1A /* ClipboardMac.mm */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = ClipboardMac.mm; sourceTree = "<group>"; tabWidth = 8; usesTabs = 0; };
+               37919C210B7D188600A56998 /* PositionIterator.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = PositionIterator.cpp; sourceTree = "<group>"; };
+               37919C220B7D188600A56998 /* PositionIterator.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = PositionIterator.h; sourceTree = "<group>"; };
                448A29BD0A46D9CB0030759F /* JSHTMLOptionsCollection.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = JSHTMLOptionsCollection.h; sourceTree = "<group>"; };
                448A29BE0A46D9CB0030759F /* JSHTMLOptionsCollection.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = JSHTMLOptionsCollection.cpp; sourceTree = "<group>"; };
                448AD27A0A4813790023D179 /* JSHTMLOptionsCollectionCustom.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSHTMLOptionsCollectionCustom.cpp; sourceTree = "<group>"; };
                                1A0D57380A5C7812007EDD4C /* OverflowEvent.idl */,
                                BE91FC8C06133666005E3790 /* Position.cpp */,
                                BE91FC8B06133666005E3790 /* Position.h */,
+                               37919C210B7D188600A56998 /* PositionIterator.cpp */,
+                               37919C220B7D188600A56998 /* PositionIterator.h */,
                                A8EA7EB50A1945D000A8EF5F /* ProcessingInstruction.cpp */,
                                A8EA7EB40A1945D000A8EF5F /* ProcessingInstruction.h */,
                                93EEC1F509C2877700C515D1 /* ProcessingInstruction.idl */,
                                933A14300B7D188600A53FFD /* TextEvent.h in Headers */,
                                933A14B90B7D1D5200A53FFD /* JSTextEvent.h in Headers */,
                                DDE63ED50B7D45A800226998 /* DOMTextEvent.h in Headers */,
+                               37919C240B7D188600A56998 /* PositionIterator.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
                                933A14B80B7D1D5200A53FFD /* JSTextEvent.cpp in Sources */,
                                A7CFB3D10B7ED10A0070C32D /* DragImage.cpp in Sources */,
                                A7CFB3D50B7ED1180070C32D /* DragImageMac.mm in Sources */,
+                               37919C230B7D188600A56998 /* PositionIterator.cpp in Sources */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
index 1c0c13e..4070de3 100644 (file)
         dom/Notation.cpp
         dom/OverflowEvent.cpp
         dom/Position.cpp
+        dom/PositionIterator.cpp
         dom/ProcessingInstruction.cpp
         dom/QualifiedName.cpp
         dom/Range.cpp
index fc5c445..e8cbd44 100644 (file)
@@ -34,6 +34,7 @@
 #include "CSSComputedStyleDeclaration.h"
 #include "htmlediting.h"
 #include "HTMLNames.h"
+#include "PositionIterator.h"
 #include "Text.h"
 #include "TextIterator.h"
 #include "visible_units.h"
@@ -70,8 +71,15 @@ static Node *previousRenderedEditable(Node *node)
     return 0;
 }
 
-Position::Position(Node *node, int offset) 
-    : m_node(node), m_offset(offset) 
+Position::Position(Node* node, int offset) 
+    : m_node(node)
+    , m_offset(offset) 
+{
+}
+
+Position::Position(const PositionIterator& it)
+    : m_node(it.m_parent)
+    , m_offset(it.m_child ? it.m_child->nodeIndex() : (it.m_parent->hasChildNodes() ? maxDeepOffset(it.m_parent) : it.m_offset))
 {
 }
 
@@ -113,7 +121,7 @@ Position Position::previous(EUsingComposedCharacters usingComposedCharacters) co
     
     int o = offset();
     // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.
-    assert(o >= 0);
+    ASSERT(o >= 0);
 
     if (o > 0) {
         Node *child = n->childNode(o - 1);
@@ -143,7 +151,7 @@ Position Position::next(EUsingComposedCharacters usingComposedCharacters) const
     
     int o = offset();
     // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.
-    assert(o >= 0);
+    ASSERT(o >= 0);
 
     Node* child = n->childNode(o);
     if (child || !n->hasChildNodes() && o < maxDeepOffset(n)) {
@@ -265,34 +273,31 @@ Position Position::nextCharacterPosition(EAffinity affinity) const
 
 // upstream() and downstream() want to return positions that are either in a
 // text node or at just before a non-text node.  This method checks for that.
-static bool isStreamer(const Position &pos)
+static bool isStreamer(const PositionIterator& pos)
 {
-    if (pos.isNull())
+    if (!pos.node())
         return true;
         
     if (isAtomicNode(pos.node()))
         return true;
         
-    return pos.offset() == 0;
+    return pos.atStartOfNode();
 }
 
 // p.upstream() returns the start of the range of positions that map to the same VisiblePosition as P.
 Position Position::upstream() const
 {
-    // start at equivalent deep position
-    Position start = *this;
-    Node *startNode = start.node();
+    Node* startNode = node();
     if (!startNode)
         return Position();
     
     // iterate backward from there, looking for a qualified position
-    Node *block = enclosingBlock(startNode);
-    Position lastVisible = *this;
-    Position currentPos = start;
+    Nodeblock = enclosingBlock(startNode);
+    PositionIterator lastVisible = *this;
+    PositionIterator currentPos = lastVisible;
     Node* originalRoot = node()->rootEditableElement();
-    for (; !currentPos.atStart(); currentPos = currentPos.previous(UsingComposedCharacters)) {
-        Node *currentNode = currentPos.node();
-        int currentOffset = currentPos.offset();
+    for (; !currentPos.atStart(); currentPos.decrement()) {
+        Node* currentNode = currentPos.node();
         
         if (currentNode->rootEditableElement() != originalRoot)
             break;
@@ -303,7 +308,7 @@ Position Position::upstream() const
             return lastVisible;
 
         // skip position in unrendered or invisible node
-        RenderObject *renderer = currentNode->renderer();
+        RenderObjectrenderer = currentNode->renderer();
         if (!renderer || renderer->style()->visibility() != VISIBLE)
             continue;
                  
@@ -312,22 +317,19 @@ Position Position::upstream() const
             lastVisible = currentPos;
         
         // Don't leave a block flow or table element.  We could rely on code above to terminate and 
-        // return lastVisible on the next iteration, but we terminate early to avoid calling previous()
-        // beceause previous() for an offset 0 position calls nodeIndex(), which is O(n).
-        // FIXME: Avoid calling previous on other offset 0 positions.
-        if (currentNode == enclosingBlock(currentNode) && currentOffset == 0)
+        // return lastVisible on the next iteration, but we terminate early.
+        if (currentNode == enclosingBlock(currentNode) && currentPos.atStartOfNode())
             return lastVisible;
             
         // Return position after brs, tables, and nodes which have content that can be ignored.
         if (editingIgnoresContent(currentNode) || renderer->isBR() || isTableElement(currentNode)) {
-            int maxOffset = maxDeepOffset(currentNode);
-            if (currentOffset >= maxOffset)
-                return Position(currentNode, maxOffset);
+            if (currentPos.atEndOfNode())
+                return Position(currentNode, maxDeepOffset(currentNode));
             continue;
         }
 
         // return current position if it is in rendered text
-        if (renderer->isText() && static_cast<RenderText *>(renderer)->firstTextBox()) {
+        if (renderer->isText() && static_cast<RenderText*>(renderer)->firstTextBox()) {
             if (currentNode != startNode) {
                 // This assertion fires in layout tests in the case-transform.html test because
                 // of a mix-up between offsets in the text in the DOM tree with text in the
@@ -337,12 +339,9 @@ Position Position::upstream() const
                 return Position(currentNode, renderer->caretMaxOffset());
             }
 
-            if (currentOffset < 0)
-                continue;
-
-            unsigned textOffset = currentOffset;
-            RenderText *textRenderer = static_cast<RenderText *>(renderer);
-            for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
+            unsigned textOffset = currentPos.offsetInLeafNode();
+            RenderText* textRenderer = static_cast<RenderText*>(renderer);
+            for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
                 if (textOffset > box->start() && textOffset <= box->start() + box->len())
                     return currentPos;
                     
@@ -360,26 +359,24 @@ Position Position::upstream() const
 // P.downstream() returns the end of the range of positions that map to the same VisiblePosition as P.
 Position Position::downstream() const
 {
-    Position start = *this;
-    Node *startNode = start.node();
+    Node* startNode = node();
     if (!startNode)
         return Position();
 
     // iterate forward from there, looking for a qualified position
-    Node *block = enclosingBlock(startNode);
-    Position lastVisible = *this;
-    Position currentPos = start;
+    Nodeblock = enclosingBlock(startNode);
+    PositionIterator lastVisible = *this;
+    PositionIterator currentPos = lastVisible;
     Node* originalRoot = node()->rootEditableElement();
-    for (; !currentPos.atEnd(); currentPos = currentPos.next(UsingComposedCharacters)) {   
-        Node *currentNode = currentPos.node();
-        int currentOffset = currentPos.offset();
+    for (; !currentPos.atEnd(); currentPos.increment()) {   
+        Node* currentNode = currentPos.node();
         
         if (currentNode->rootEditableElement() != originalRoot)
             break;
 
         // stop before going above the body, up into the head
         // return the last visible streamer position
-        if (currentNode->hasTagName(bodyTag) && currentOffset >= (int) currentNode->childNodeCount())
+        if (currentNode->hasTagName(bodyTag) && currentPos.atEndOfNode())
             break;
             
         // Do not enter a new enclosing block flow or table element, and don't leave the original one.
@@ -387,7 +384,7 @@ Position Position::downstream() const
             return lastVisible;
 
         // skip position in unrendered or invisible node
-        RenderObject *renderer = currentNode->renderer();
+        RenderObjectrenderer = currentNode->renderer();
         if (!renderer || renderer->style()->visibility() != VISIBLE)
             continue;
             
@@ -397,25 +394,22 @@ Position Position::downstream() const
 
         // Return position before brs, tables, and nodes which have content that can be ignored.
         if (editingIgnoresContent(currentNode) || renderer->isBR() || isTableElement(currentNode)) {
-            if (currentOffset <= renderer->caretMinOffset())
+            if (currentPos.offsetInLeafNode() <= renderer->caretMinOffset())
                 return Position(currentNode, renderer->caretMinOffset());
             continue;
         }
 
         // return current position if it is in rendered text
-        if (renderer->isText() && static_cast<RenderText *>(renderer)->firstTextBox()) {
+        if (renderer->isText() && static_cast<RenderText*>(renderer)->firstTextBox()) {
             if (currentNode != startNode) {
-                assert(currentOffset == 0);
+                ASSERT(currentPos.atStartOfNode());
                 return Position(currentNode, renderer->caretMinOffset());
             }
 
-            if (currentOffset < 0)
-                continue;
-
-            unsigned textOffset = currentOffset;
+            unsigned textOffset = currentPos.offsetInLeafNode();
 
-            RenderText *textRenderer = static_cast<RenderText *>(renderer);
-            for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
+            RenderText* textRenderer = static_cast<RenderText*>(renderer);
+            for (InlineTextBoxbox = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
                 if (textOffset >= box->start() && textOffset <= box->end())
                     return currentPos;
                 
@@ -431,7 +425,7 @@ Position Position::downstream() const
     return lastVisible;
 }
 
-static bool hasRenderedNonAnonymousDescendantsWithHeight(RenderObject *renderer)
+bool Position::hasRenderedNonAnonymousDescendantsWithHeight(RenderObject* renderer)
 {
     RenderObject* stop = renderer->nextInPreOrderAfterChildren();
     for (RenderObject *o = renderer->firstChild(); o && o != stop; o = o->nextInPreOrder())
@@ -441,7 +435,7 @@ static bool hasRenderedNonAnonymousDescendantsWithHeight(RenderObject *renderer)
     return false;
 }
 
-static bool nodeIsUserSelectNone(Node* node)
+bool Position::nodeIsUserSelectNone(Node* node)
 {
     return node && node->renderer() && node->renderer()->style()->userSelect() == SELECT_NONE;
 }
index 5ef6690..acb7cbf 100644 (file)
@@ -33,6 +33,7 @@ namespace WebCore {
 
 class CSSComputedStyleDeclaration;
 class Element;
+class PositionIterator;
 class Range;
 
 enum EUsingComposedCharacters { NotUsingComposedCharacters = false, UsingComposedCharacters = true };
@@ -42,6 +43,7 @@ class Position
 public:
     Position() : m_node(0), m_offset(0) { }
     Position(Node*, int offset);
+    Position(const PositionIterator&);
 
     void clear();
 
@@ -71,9 +73,13 @@ public:
     Position downstream() const;
     
     bool isCandidate() const;
+    bool inRenderedText() const;
     bool isRenderedCharacter() const;
     bool rendersInDifferentPosition(const Position &pos) const;
     
+    static bool hasRenderedNonAnonymousDescendantsWithHeight(RenderObject*);
+    static bool nodeIsUserSelectNone(Node*);
+    
     void debugPosition(const char* msg = "") const;
 
 #ifndef NDEBUG
@@ -84,11 +90,8 @@ public:
 private:
     int renderedOffset() const;
 
-    bool inRenderedText() const;
-
     Position previousCharacterPosition(EAffinity) const;
     Position nextCharacterPosition(EAffinity) const;
-    
     RefPtr<Node> m_node;
     int m_offset;
 };
diff --git a/WebCore/dom/PositionIterator.cpp b/WebCore/dom/PositionIterator.cpp
new file mode 100644 (file)
index 0000000..be1e59f
--- /dev/null
@@ -0,0 +1,155 @@
+/*
+ * Copyright (C) 2007 Apple Inc.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "PositionIterator.h"
+
+#include "Node.h"
+#include "RenderObject.h"
+#include "htmlediting.h"
+
+namespace WebCore {
+
+using namespace HTMLNames;
+
+void PositionIterator::increment()
+{
+    if (!m_parent)
+        return;
+
+    if (m_child) {
+        m_parent = m_child;
+        m_child = m_parent->firstChild();
+        m_offset = 0;
+        return;
+    }
+
+    if (!m_parent->hasChildNodes() && m_offset < maxDeepOffset(m_parent))
+        m_offset = m_parent->nextOffset(m_offset);
+    else {
+        m_child = m_parent;
+        m_parent = m_child->parentNode();
+        m_child = m_child->nextSibling();
+        m_offset = 0;
+    }
+}
+
+void PositionIterator::decrement()
+{
+    if (!m_parent)
+        return;
+
+    if (m_child) {
+        m_parent = m_child->previousSibling();
+        if (m_parent) {
+            m_child = 0;
+            m_offset = m_parent->hasChildNodes() ? 0 : maxDeepOffset(m_parent);
+        } else {
+            m_child = m_child->parentNode();
+            m_parent = m_child->parentNode();
+            m_offset = 0;
+        }
+        return;
+    }
+
+    if (m_offset) {
+        m_offset = m_parent->previousOffset(m_offset);
+    } else {
+        if (m_parent->hasChildNodes()) {
+            m_parent = m_parent->lastChild();
+            if (!m_parent->hasChildNodes())
+                m_offset = maxDeepOffset(m_parent);
+        } else {
+            m_child = m_parent;
+            m_parent = m_parent->parentNode();
+        }
+    }
+}
+
+bool PositionIterator::atStart() const
+{
+    if (!m_parent)
+        return true;
+    if (m_parent->parentNode())
+        return false;
+    return !m_parent->hasChildNodes() && !m_offset || m_child && !m_child->previousSibling();
+}
+
+bool PositionIterator::atEnd() const
+{
+    if (!m_parent)
+        return true;
+    if (m_child)
+        return false;
+    return !m_parent->parentNode() && (m_parent->hasChildNodes() || m_offset >= maxDeepOffset(m_parent));
+}
+
+bool PositionIterator::atStartOfNode() const
+{
+    if (!m_parent)
+        return true;
+    if (!m_child)
+        return !m_parent->hasChildNodes() && !m_offset;
+    return !m_child->previousSibling();
+}
+
+bool PositionIterator::atEndOfNode() const
+{
+    if (!m_parent)
+        return true;
+    if (m_child)
+        return false;
+    return m_parent->hasChildNodes() || m_offset >= maxDeepOffset(m_parent);
+}
+
+bool PositionIterator::isCandidate() const
+{
+    if (!m_parent)
+        return false;
+
+    RenderObject* renderer = m_parent->renderer();
+    if (!renderer)
+        return false;
+    
+    if (renderer->style()->visibility() != VISIBLE)
+        return false;
+
+    if (renderer->isBR())
+        return !m_offset && !Position::nodeIsUserSelectNone(m_parent->parent());
+
+    if (renderer->isText())
+        return Position(*this).inRenderedText() && !Position::nodeIsUserSelectNone(m_parent);
+
+    if (isTableElement(m_parent) || editingIgnoresContent(m_parent))
+        return (atStartOfNode() || atEndOfNode()) && !Position::nodeIsUserSelectNone(m_parent->parent());
+
+    if (!m_parent->hasTagName(htmlTag) && renderer->isBlockFlow() && !Position::hasRenderedNonAnonymousDescendantsWithHeight(renderer) &&
+       (renderer->height() || m_parent->hasTagName(bodyTag)))
+        return atStartOfNode() && !Position::nodeIsUserSelectNone(m_parent);
+    
+    return false;
+}
+
+} // namespace WebCore
diff --git a/WebCore/dom/PositionIterator.h b/WebCore/dom/PositionIterator.h
new file mode 100644 (file)
index 0000000..f9e8460
--- /dev/null
@@ -0,0 +1,70 @@
+/*
+ * Copyright (C) 2007 Apple Inc.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef PositionIterator_h
+#define PositionIterator_h
+
+#include "Position.h"
+
+namespace WebCore {
+
+class PositionIterator {
+public:
+    PositionIterator()
+        : m_parent(0)
+        , m_child(0)
+        , m_offset(0)
+    {
+    }
+
+    PositionIterator(const Position& pos)
+        : m_parent(pos.node())
+        , m_child(m_parent->childNode(pos.offset()))
+        , m_offset(m_child ? 0 : pos.offset())
+    {
+    }
+
+    void increment();
+    void decrement();
+
+    Node* node() const { return m_parent; }
+    int offsetInLeafNode() const { return m_offset; }
+
+    bool atStart() const;
+    bool atEnd() const;
+    bool atStartOfNode() const;
+    bool atEndOfNode() const;
+    bool isCandidate() const;
+
+private:
+    friend class Position;
+    Node* m_parent;
+    Node* m_child;
+    int m_offset;
+};
+
+} // namespace WebCore
+
+#endif // PositionIterator_h
index e4033db..57f5288 100644 (file)
@@ -32,6 +32,7 @@
 #include "HTMLElement.h"
 #include "HTMLInterchange.h"
 #include "HTMLNames.h"
+#include "PositionIterator.h"
 #include "RenderObject.h"
 #include "RegularExpression.h"
 #include "Range.h"
@@ -195,9 +196,9 @@ bool isContentEditable(Node* node)
 
 Position nextCandidate(const Position& position)
 {
-    Position p = position;
+    PositionIterator p = position;
     while (!p.atEnd()) {
-        p = p.next(UsingComposedCharacters);
+        p.increment();
         if (p.isCandidate())
             return p;
     }
@@ -218,9 +219,9 @@ Position nextVisuallyDistinctCandidate(const Position& position)
 
 Position previousCandidate(const Position& position)
 {
-    Position p = position;
+    PositionIterator p = position;
     while (!p.atStart()) {
-        p = p.previous(UsingComposedCharacters);
+        p.decrement();
         if (p.isCandidate())
             return p;
     }