File indexing completed on 2024-04-28 15:24:52

 /*
  * This file is part of the DOM implementation for KDE.
  *
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  *           (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
  *           (C) 2005, 2009, 2010 Maksim Orlovich (maksim@kde.org)
  *           (C) 2006 Allan Sandfeld Jensen (kde@carewolf.com)
  *           (C) 2007 David Smith (catfish.man@gmail.com)
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Library General Public License for more details.
  *
  * You should have received a copy of the GNU Library General Public License
  * along with this library; see the file COPYING.LIB.  If not, write to
  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  * Boston, MA 02110-1301, USA.
  *
  *
  * The code for ClassNodeListImpl was originally licensed under the following terms
  * (but in this version is available only as above):
  *     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.
  *     3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
  *         its contributors may be used to endorse or promote products derived
  *         from this software without specific prior written permission.
  *
  *     THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "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 OR ITS 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 "dom_nodelistimpl.h"
 #include "dom_nodeimpl.h"
 #include "dom_docimpl.h"
 
 using namespace DOM;
 using namespace khtml;
 
 NodeImpl *DynamicNodeListImpl::item(unsigned long index) const
 {
     unsigned long requestIndex = index;
 
     m_cache->updateNodeListInfo(m_refNode->document());
 
     NodeImpl *n = nullptr;
     bool usedCache = false;
     if (m_cache->current.node) {
         //Compute distance from the requested index to the cache node
         unsigned long cacheDist = qAbs(long(index) - long(m_cache->position));
 
         if (cacheDist < (unsigned long)index) { //Closer to the cached position
             usedCache = true;
             if (index >= m_cache->position) { //Go ahead
                 unsigned long relIndex = index - m_cache->position;
                 n = recursiveItem(m_refNode, m_cache->current.node, relIndex);
             } else { //Go backwards
                 unsigned long relIndex = m_cache->position - index;
                 n = recursiveItemBack(m_refNode, m_cache->current.node, relIndex);
             }
         }
     }
 
     if (!usedCache) {
         n = recursiveItem(m_refNode, m_refNode->firstChild(), index);
     }
 
     //We always update the cache state, to make starting iteration
     //where it was left off easy.
     m_cache->current.node  = n;
     m_cache->position = requestIndex;
     return n;
 }
 
 unsigned long DynamicNodeListImpl::length() const
 {
     m_cache->updateNodeListInfo(m_refNode->document());
     if (!m_cache->hasLength) {
         m_cache->length    = calcLength(m_refNode);
         m_cache->hasLength = true;
     }
     return m_cache->length;
 }
 
 unsigned long DynamicNodeListImpl::calcLength(NodeImpl *start) const
 {
     unsigned long len = 0;
     for (NodeImpl *n = start->firstChild(); n != nullptr; n = n->nextSibling()) {
         bool recurse = true;
         if (nodeMatches(n, recurse)) {
             len++;
         }
         if (recurse) {
             len += DynamicNodeListImpl::calcLength(n);
         }
     }
 
     return len;
 }
 
 DynamicNodeListImpl::DynamicNodeListImpl(NodeImpl *n, int type, CacheFactory *factory)
 {
     m_refNode = n;
     m_refNode->ref();
 
     m_cache = m_refNode->document()->acquireCachedNodeListInfo(
                   factory, n, type);
 }
 
 DynamicNodeListImpl::~DynamicNodeListImpl()
 {
     m_refNode->document()->releaseCachedNodeListInfo(m_cache);
     m_refNode->deref();
 }
 
 /**
  Next item in the pre-order walk of tree from node, but not going outside
  absStart
 */
 static NodeImpl *helperNext(NodeImpl *node, NodeImpl *absStart)
 {
     //Walk up until we wind a sibling to go to.
     while (!node->nextSibling() && node != absStart) {
         node = node->parentNode();
     }
 
     if (node != absStart) {
         return node->nextSibling();
     } else {
         return nullptr;
     }
 }
 
 NodeImpl *DynamicNodeListImpl::recursiveItem(NodeImpl *absStart, NodeImpl *start, unsigned long &offset) const
 {
     for (NodeImpl *n = start; n != nullptr; n = helperNext(n, absStart)) {
         bool recurse = true;
         if (nodeMatches(n, recurse))
             if (!offset--) {
                 return n;
             }
 
         NodeImpl *depthSearch = recurse ? recursiveItem(n, n->firstChild(), offset) : nullptr;
         if (depthSearch) {
             return depthSearch;
         }
     }
 
     return nullptr; // no matching node in this subtree
 }
 
 NodeImpl *DynamicNodeListImpl::recursiveItemBack(NodeImpl *absStart, NodeImpl *start, unsigned long &offset) const
 {
     //### it might be cleaner/faster to split nodeMatches and recursion
     //filtering.
     bool dummy   = true;
     NodeImpl *n  = start;
 
     do {
         bool recurse = true;
 
         //Check whether the current node matches.
         if (nodeMatches(n, dummy))
             if (!offset--) {
                 return n;
             }
 
         if (n->previousSibling()) {
             //Move to the last node of this whole subtree that we should recurse into
             n       = n->previousSibling();
             recurse = true;
 
             while (n->lastChild()) {
                 (void)nodeMatches(n, recurse);
                 if (!recurse) {
                     break;    //Don't go there
                 }
                 n = n->lastChild();
             }
         } else {
             //We're done with this whole subtree, so move up
             n = n->parentNode();
         }
     } while (n && n != absStart);
 
     return nullptr;
 }
 
 // ---------------------------------------------------------------------------
 
 DynamicNodeListImpl::Cache *DynamicNodeListImpl::Cache::makeStructuralOnly()
 {
     return new Cache(DocumentImpl::TV_Structural); // will check the same ver twice
 }
 
 DynamicNodeListImpl::Cache *DynamicNodeListImpl::Cache::makeNameOrID()
 {
     return new Cache(DocumentImpl::TV_IDNameHref);
 }
 
 DynamicNodeListImpl::Cache *DynamicNodeListImpl::Cache::makeClassName()
 {
     return new Cache(DocumentImpl::TV_Class);
 }
 
 DynamicNodeListImpl::Cache::Cache(unsigned short relSecondaryVer): relevantSecondaryVer(relSecondaryVer)
 {}
 
 DynamicNodeListImpl::Cache::~Cache()
 {}
 
 void DynamicNodeListImpl::Cache::clear(DocumentImpl *doc)
 {
     hasLength = false;
     current.node = nullptr;
     version          = doc->domTreeVersion(DocumentImpl::TV_Structural);
     secondaryVersion = doc->domTreeVersion(relevantSecondaryVer);
 }
 
 void DynamicNodeListImpl::Cache::updateNodeListInfo(DocumentImpl *doc)
 {
     //If version doesn't match, clear
     if (doc->domTreeVersion(DocumentImpl::TV_Structural) != version ||
             doc->domTreeVersion(relevantSecondaryVer) != secondaryVersion) {
         clear(doc);
     }
 }
 
 // ---------------------------------------------------------------------------
 ChildNodeListImpl::ChildNodeListImpl(NodeImpl *n): DynamicNodeListImpl(n, CHILD_NODES, DynamicNodeListImpl::Cache::makeStructuralOnly)
 {}
 
 bool ChildNodeListImpl::nodeMatches(NodeImpl * /*testNode*/, bool &doRecurse) const
 {
     doRecurse = false;
     return true;
 }
 
 // ---------------------------------------------------------------------------
 TagNodeListImpl::TagNodeListImpl(NodeImpl *n, NamespaceName namespaceName, LocalName localName, PrefixName prefix)
     : DynamicNodeListImpl(n, UNCACHEABLE, DynamicNodeListImpl::Cache::makeStructuralOnly),
       m_namespaceAware(false)
 {
     m_namespace = namespaceName;
     m_localName = localName;
     m_prefix = prefix;
 }
 
 TagNodeListImpl::TagNodeListImpl(NodeImpl *n, const DOMString &namespaceURI, const DOMString &localName)
     : DynamicNodeListImpl(n, UNCACHEABLE, DynamicNodeListImpl::Cache::makeStructuralOnly),
       m_namespaceAware(true)
 {
     if (namespaceURI == "*") {
         m_namespace = NamespaceName::fromId(anyNamespace);
     } else {
         m_namespace = NamespaceName::fromString(namespaceURI);
     }
     if (localName == "*") {
         m_localName = LocalName::fromId(anyLocalName);
     } else {
         m_localName = LocalName::fromString(localName);
     }
     m_prefix = PrefixName::fromId(emptyPrefix);
 }
 
 bool TagNodeListImpl::nodeMatches(NodeImpl *testNode, bool & /*doRecurse*/) const
 {
     if (testNode->nodeType() != Node::ELEMENT_NODE) {
         return false;
     }
 
     if (m_namespaceAware) {
         return (m_namespace.id() == anyNamespace || m_namespace.id() == namespacePart(testNode->id())) &&
                (m_localName.id() == anyLocalName || m_localName.id() == localNamePart(testNode->id()));
     } else {
         return (m_localName.id() == anyLocalName) || (m_localName.id() == localNamePart(testNode->id()) &&
                 m_prefix == static_cast<ElementImpl *>(testNode)->prefixName());
     }
 }
 
 // ---------------------------------------------------------------------------
 NameNodeListImpl::NameNodeListImpl(NodeImpl *n, const DOMString &t)
     : DynamicNodeListImpl(n, UNCACHEABLE, DynamicNodeListImpl::Cache::makeNameOrID),
       nodeName(t)
 {}
 
 bool NameNodeListImpl::nodeMatches(NodeImpl *testNode, bool & /*doRecurse*/) const
 {
     if (testNode->nodeType() != Node::ELEMENT_NODE) {
         return false;
     }
     return static_cast<ElementImpl *>(testNode)->getAttribute(ATTR_NAME) == nodeName;
 }
 
 // ---------------------------------------------------------------------------
 ClassNodeListImpl::ClassNodeListImpl(NodeImpl *rootNode, const DOMString &classNames)
     : DynamicNodeListImpl(rootNode, UNCACHEABLE, DynamicNodeListImpl::Cache::makeClassName)
 {
     m_classNames.parseClassAttribute(classNames, m_refNode->document()->inCompatMode());
 }
 
 bool ClassNodeListImpl::nodeMatches(NodeImpl *testNode, bool &doRecurse) const
 {
     if (!testNode->isElementNode()) {
         doRecurse = false;
         return false;
     }
 
     if (!testNode->hasClass()) {
         return false;
     }
 
     if (!m_classNames.size()) {
         return false;
     }
 
     const ClassNames  &classes = static_cast<ElementImpl *>(testNode)->classNames();
     for (size_t i = 0; i < m_classNames.size(); ++i) {
         if (!classes.contains(m_classNames[i])) {
             return false;
         }
     }
 
     return true;
 }
 
 // ---------------------------------------------------------------------------
 
 StaticNodeListImpl::StaticNodeListImpl():
     m_knownNormalization(DocumentOrder) // true vacuously
 {}
 
 StaticNodeListImpl::~StaticNodeListImpl() {}
 
 void StaticNodeListImpl::append(NodeImpl *n)
 {
     assert(n);
     m_kids.append(n);
     m_knownNormalization = Unnormalized;
 }
 
 NodeImpl *StaticNodeListImpl::item(unsigned long index) const
 {
     return index < m_kids.size() ? m_kids[index].get() : nullptr;
 }
 
 unsigned long StaticNodeListImpl::length() const
 {
     return m_kids.size();
 }
 
 static bool nodeLess(const SharedPtr<NodeImpl> &n1, const SharedPtr<DOM::NodeImpl> &n2)
 {
     return n1->compareDocumentPosition(n2.get()) & Node::DOCUMENT_POSITION_FOLLOWING;
 }
 
 void StaticNodeListImpl::normalizeUpto(NormalizationKind kind)
 {
     if (m_knownNormalization == kind || m_knownNormalization == DocumentOrder) {
         return;
     }
 
     if (kind == Unnormalized) {
         return;
     }
 
     // First sort.
     std::sort(m_kids.begin(), m_kids.end(), nodeLess);
 
     // Now get rid of dupes.
     DOM::NodeImpl *last = nullptr;
     unsigned out = 0;
     for (unsigned in = 0; in < m_kids.size(); ++in) {
         DOM::NodeImpl *cur = m_kids[in].get();
         if (cur != last) {
             m_kids[out] = cur;
             ++out;
         }
 
         last = cur;
     }
     m_kids.resize(out);
 
     m_knownNormalization = DocumentOrder;
 }
 
 void  StaticNodeListImpl::setKnownNormalization(NormalizationKind kind)
 {
     m_knownNormalization = kind;
 }
 
 StaticNodeListImpl::NormalizationKind StaticNodeListImpl::knownNormalization() const
 {
     return m_knownNormalization;
 }