Reviewed by Dave.
authormjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 23 Nov 2004 01:44:59 +0000 (01:44 +0000)
committermjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 23 Nov 2004 01:44:59 +0000 (01:44 +0000)
<rdar://problem/3890961> selecting an item on the Apache bugzilla query page can be sped up 10% (HTMLFormCollection)
<rdar://problem/3890958> JavaScript that toggles checkboxes can be improved 73% (HTMLCollection,HTMLFormCollection)

This avoids the O(N^2) penalty for named item traversal for form collections.

It also combines the item traversal logic for all non-form
collection operations into a single traverseNextItem
function. This avoids having 5 copies of the big switch statement
for this.

Also fixed a bug that prevented the last form element from being removed properly.

        * khtml/html/html_formimpl.cpp:
        (DOM::removeFromVector):
* khtml/dom/html_misc.cpp:
        (HTMLCollection::namedItems):
        * khtml/dom/html_misc.h:
        * khtml/ecma/kjs_html.cpp:
        (KJS::HTMLCollection::getNamedItems):
        * khtml/html/html_miscimpl.cpp:
        (HTMLCollectionImpl::traverseNextItem):
        (HTMLCollectionImpl::calcLength):
        (HTMLCollectionImpl::length):
        (HTMLCollectionImpl::item):
        (HTMLCollectionImpl::nextItem):
        (HTMLCollectionImpl::checkForNameMatch):
        (HTMLCollectionImpl::namedItem):
        (HTMLCollectionImpl::namedItems):
        (HTMLCollectionImpl::nextNamedItem):
        (HTMLFormCollectionImpl::calcLength):
        (HTMLFormCollectionImpl::namedItem):
        (HTMLFormCollectionImpl::nextNamedItem):
        (HTMLFormCollectionImpl::namedItems):
        * khtml/html/html_miscimpl.h:

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

WebCore/ChangeLog-2005-08-23
WebCore/khtml/dom/html_misc.cpp
WebCore/khtml/dom/html_misc.h
WebCore/khtml/ecma/kjs_html.cpp
WebCore/khtml/html/html_formimpl.cpp
WebCore/khtml/html/html_miscimpl.cpp
WebCore/khtml/html/html_miscimpl.h

index 1125486..39d04e3 100644 (file)
@@ -1,3 +1,42 @@
+2004-11-22  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Dave.
+
+       <rdar://problem/3890961> selecting an item on the Apache bugzilla query page can be sped up 10% (HTMLFormCollection)
+       <rdar://problem/3890958> JavaScript that toggles checkboxes can be improved 73% (HTMLCollection,HTMLFormCollection)
+
+       This avoids the O(N^2) penalty for named item traversal for form collections.
+
+       It also combines the item traversal logic for all non-form
+       collection operations into a single traverseNextItem
+       function. This avoids having 5 copies of the big switch statement
+       for this.
+
+       Also fixed a bug that prevented the last form element from being removed properly.
+        
+        * khtml/html/html_formimpl.cpp:
+        (DOM::removeFromVector):
+       * khtml/dom/html_misc.cpp:
+        (HTMLCollection::namedItems):
+        * khtml/dom/html_misc.h:
+        * khtml/ecma/kjs_html.cpp:
+        (KJS::HTMLCollection::getNamedItems):
+        * khtml/html/html_miscimpl.cpp:
+        (HTMLCollectionImpl::traverseNextItem):
+        (HTMLCollectionImpl::calcLength):
+        (HTMLCollectionImpl::length):
+        (HTMLCollectionImpl::item):
+        (HTMLCollectionImpl::nextItem):
+        (HTMLCollectionImpl::checkForNameMatch):
+        (HTMLCollectionImpl::namedItem):
+        (HTMLCollectionImpl::namedItems):
+        (HTMLCollectionImpl::nextNamedItem):
+        (HTMLFormCollectionImpl::calcLength):
+        (HTMLFormCollectionImpl::namedItem):
+        (HTMLFormCollectionImpl::nextNamedItem):
+        (HTMLFormCollectionImpl::namedItems):
+        * khtml/html/html_miscimpl.h:
+
 2004-11-22  Ken Kocienda  <kocienda@apple.com>
 
         Reviewed by Harrison
 2004-11-22  Ken Kocienda  <kocienda@apple.com>
 
         Reviewed by Harrison
index d2651cb..2577f62 100644 (file)
@@ -169,6 +169,15 @@ Node HTMLCollection::nextNamedItem( const DOMString &name ) const
     return static_cast<HTMLCollectionImpl*>( impl )->nextNamedItem( name );
 }
 
     return static_cast<HTMLCollectionImpl*>( impl )->nextNamedItem( name );
 }
 
+QValueList<Node> HTMLCollection::namedItems( const DOMString & name ) const
+{
+    if ( !impl )
+        return QValueList<Node>();
+
+    return static_cast<HTMLCollectionImpl*>( impl )->namedItems( name );
+}
+
+
 HTMLCollectionImpl *HTMLCollection::handle() const
 {
     return impl;
 HTMLCollectionImpl *HTMLCollection::handle() const
 {
     return impl;
index f3e6bf0..c96040c 100644 (file)
@@ -30,6 +30,7 @@
 #define HTML_MISC_H
 
 #include <dom/html_element.h>
 #define HTML_MISC_H
 
 #include <dom/html_element.h>
+#include <qvaluelist.h>
 
 namespace DOM {
 
 
 namespace DOM {
 
@@ -185,6 +186,8 @@ public:
     // In case of multiple items named the same way
     Node nextNamedItem( const DOMString &name ) const;
 
     // In case of multiple items named the same way
     Node nextNamedItem( const DOMString &name ) const;
 
+    QValueList<Node> namedItems( const DOMString &name ) const;
+
 protected:
     HTMLCollectionImpl *impl;
 };
 protected:
     HTMLCollectionImpl *impl;
 };
index 62fb269..503ba54 100644 (file)
@@ -3100,40 +3100,28 @@ Value KJS::HTMLCollection::getNamedItems(ExecState *exec, const Identifier &prop
   kdDebug(6070) << "KJS::HTMLCollection::getNamedItems " << propertyName.ascii() << endl;
 #endif
   DOM::DOMString pstr = propertyName.string();
   kdDebug(6070) << "KJS::HTMLCollection::getNamedItems " << propertyName.ascii() << endl;
 #endif
   DOM::DOMString pstr = propertyName.string();
-  DOM::Node node = collection.namedItem(pstr);
-  if(!node.isNull())
-  {
-    DOM::Node next = collection.nextNamedItem(pstr);
-    if (next.isNull()) // single item
-    {
+
+  QValueList<DOM::Node> namedItems = collection.namedItems(pstr);
+
+  if (namedItems.isEmpty()) {
 #ifdef KJS_VERBOSE
 #ifdef KJS_VERBOSE
-      kdDebug(6070) << "returning single node" << endl;
+    kdDebug(6070) << "not found" << endl;
 #endif
 #endif
+    return Undefined();
+  }
+
+  if (namedItems.count() == 1) {
+    DOM::Node node = namedItems[0];
 #if APPLE_CHANGES
 #if APPLE_CHANGES
-         if (!node.isNull() && (node.handle()->id() == ID_APPLET || node.handle()->id() == ID_EMBED)) {
-           return getRuntimeObject(exec,node);
-         }
-#endif
-      return getDOMNode(exec,node);
+    if (!node.isNull() && (node.handle()->id() == ID_APPLET || node.handle()->id() == ID_EMBED)) {
+      return getRuntimeObject(exec, node);
     }
     }
-    else // multiple items, return a collection
-    {
-      QValueList<DOM::Node> nodes;
-      nodes.append(node);
-      do {
-        nodes.append(next);
-        next = collection.nextNamedItem(pstr);
-      } while (!next.isNull());
-#ifdef KJS_VERBOSE
-      kdDebug(6070) << "returning list of " << nodes.count() << " nodes" << endl;
 #endif
 #endif
-      return Value(new DOMNamedNodesCollection(exec,nodes));
-    }
+
+    return getDOMNode(exec,node);
   }
   }
-#ifdef KJS_VERBOSE
-  kdDebug(6070) << "not found" << endl;
-#endif
-  return Undefined();
+  
+  return Value(new DOMNamedNodesCollection(exec,namedItems));
 }
 
 Value KJS::HTMLCollectionProtoFunc::tryCall(ExecState *exec, Object &thisObj, const List &args)
 }
 
 Value KJS::HTMLCollectionProtoFunc::tryCall(ExecState *exec, Object &thisObj, const List &args)
index bf9fbdf..2c12dc3 100644 (file)
@@ -708,10 +708,13 @@ template<class T> static void removeFromVector(QPtrVector<T> &vec, T *item)
 {
     int pos = vec.findRef(item);
     int count = vec.count();
 {
     int pos = vec.findRef(item);
     int count = vec.count();
+
+    printf("item: 0x%x; pos: %d; vec[0]: 0x%x\n", (unsigned)item, pos, count ? (unsigned)vec[0] : 0);
+
     if (pos < 0)
         return;
 
     if (pos < 0)
         return;
 
-    for (int i = pos; i < count - 2; i++) {
+    for (int i = pos; i < count - 1; i++) {
         vec.insert(i, vec[i+1]);
     }
     vec.remove(count - 1);
         vec.insert(i, vec[i+1]);
     }
     vec.remove(count - 1);
index 335233a..a628d38 100644 (file)
@@ -78,187 +78,117 @@ void HTMLCollectionImpl::resetCollectionInfo() const
     }
 }
 
     }
 }
 
-unsigned long HTMLCollectionImpl::calcLength(NodeImpl *current) const
+
+NodeImpl *HTMLCollectionImpl::traverseNextItem(NodeImpl *current) const
 {
 {
-    unsigned long len = 0;
-    while(current)
-    {
-        if(current->nodeType() == Node::ELEMENT_NODE)
-        {
+    current = current->traverseNextNode();
+
+    while (current) {
+        if(current->nodeType() == Node::ELEMENT_NODE) {
+            bool found = false;
             bool deep = true;
             HTMLElementImpl *e = static_cast<HTMLElementImpl *>(current);
             bool deep = true;
             HTMLElementImpl *e = static_cast<HTMLElementImpl *>(current);
-            switch(type)
-            {
+            switch(type) {
             case DOC_IMAGES:
                 if(e->id() == ID_IMG)
             case DOC_IMAGES:
                 if(e->id() == ID_IMG)
-                    len++;
+                    found = true;
                 break;
             case DOC_FORMS:
                 if(e->id() == ID_FORM)
                 break;
             case DOC_FORMS:
                 if(e->id() == ID_FORM)
-                    len++;
+                    found = true;
                 break;
             case TABLE_TBODIES:
                 if(e->id() == ID_TBODY)
                 break;
             case TABLE_TBODIES:
                 if(e->id() == ID_TBODY)
-                    len++;
+                    found = true;
                 else if(e->id() == ID_TABLE)
                     deep = false;
                 break;
             case TR_CELLS:
                 if(e->id() == ID_TD || e->id() == ID_TH)
                 else if(e->id() == ID_TABLE)
                     deep = false;
                 break;
             case TR_CELLS:
                 if(e->id() == ID_TD || e->id() == ID_TH)
-                    len++;
+                    found = true;
                 else if(e->id() == ID_TABLE)
                     deep = false;
                 break;
             case TABLE_ROWS:
             case TSECTION_ROWS:
                 if(e->id() == ID_TR)
                 else if(e->id() == ID_TABLE)
                     deep = false;
                 break;
             case TABLE_ROWS:
             case TSECTION_ROWS:
                 if(e->id() == ID_TR)
-                    len++;
+                    found = true;
                 else if(e->id() == ID_TABLE)
                     deep = false;
                 break;
             case SELECT_OPTIONS:
                 if(e->id() == ID_OPTION)
                 else if(e->id() == ID_TABLE)
                     deep = false;
                 break;
             case SELECT_OPTIONS:
                 if(e->id() == ID_OPTION)
-                    len++;
+                    found = true;
                 break;
             case MAP_AREAS:
                 if(e->id() == ID_AREA)
                 break;
             case MAP_AREAS:
                 if(e->id() == ID_AREA)
-                    len++;
+                    found = true;
                 break;
             case DOC_APPLETS:   // all OBJECT and APPLET elements
                 if(e->id() == ID_OBJECT || e->id() == ID_APPLET)
                 break;
             case DOC_APPLETS:   // all OBJECT and APPLET elements
                 if(e->id() == ID_OBJECT || e->id() == ID_APPLET)
-                    len++;
+                    found = true;
                 break;
             case DOC_EMBEDS:   // all EMBED elements
                 if(e->id() == ID_EMBED)
                 break;
             case DOC_EMBEDS:   // all EMBED elements
                 if(e->id() == ID_EMBED)
-                    len++;
+                    found = true;
                 break;
             case DOC_LINKS:     // all A _and_ AREA elements with a value for href
                 if(e->id() == ID_A || e->id() == ID_AREA)
                     if(!e->getAttribute(ATTR_HREF).isNull())
                 break;
             case DOC_LINKS:     // all A _and_ AREA elements with a value for href
                 if(e->id() == ID_A || e->id() == ID_AREA)
                     if(!e->getAttribute(ATTR_HREF).isNull())
-                        len++;
+                        found = true;
                 break;
                 break;
-            case DOC_ANCHORS:      // all A elements with a value for name and all elements with an id attribute
-                if(e->id() == ID_A) {
+            case DOC_ANCHORS:      // all A elements with a value for name or an id attribute
+                if(e->id() == ID_A)
                     if(!e->getAttribute(ATTR_NAME).isNull())
                     if(!e->getAttribute(ATTR_NAME).isNull())
-                        len++;
-                }
+                        found = true;
                 break;
                 break;
-            case DOC_ALL:      // "all" elements
-                len++;
+            case DOC_ALL:
+                found = true;
                 break;
                 break;
-            case NODE_CHILDREN: // first-level children
-                len++;
+            case NODE_CHILDREN:
+                found = true;
                 deep = false;
                 break;
             default:
                 kdDebug( 6030 ) << "Error in HTMLCollection, wrong tagId!" << endl;
             }
                 deep = false;
                 break;
             default:
                 kdDebug( 6030 ) << "Error in HTMLCollection, wrong tagId!" << endl;
             }
-            if(deep) {
+            if (found) {
+                return current;
+            }
+            if (deep) {
                 current = current->traverseNextNode(base);
                 continue;
                 current = current->traverseNextNode(base);
                 continue;
-            }
+            } 
         }
         current = current->traverseNextSibling(base);
     }
         }
         current = current->traverseNextSibling(base);
     }
+    return 0;
+}
+
+
+unsigned long HTMLCollectionImpl::calcLength() const
+{
+    unsigned long len = 0;
+
+    for (NodeImpl *current = traverseNextItem(base); current; current = traverseNextItem(current)) {
+        len++;
+    }
+
     return len;
 }
 
 // since the collections are to be "live", we have to do the
     return len;
 }
 
 // since the collections are to be "live", we have to do the
-// calculation every time...
+// calculation every time if anything has changed
 unsigned long HTMLCollectionImpl::length() const
 {
     resetCollectionInfo();
     if (!info->haslength) {
 unsigned long HTMLCollectionImpl::length() const
 {
     resetCollectionInfo();
     if (!info->haslength) {
-        info->length = calcLength(base->firstChild());
+        info->length = calcLength();
         info->haslength = true;
     }
     return info->length;
 }
 
         info->haslength = true;
     }
     return info->length;
 }
 
-NodeImpl *HTMLCollectionImpl::getItem(NodeImpl *current, int index, int &len) const
-{
-    while(current)
-    {
-        if(current->nodeType() == Node::ELEMENT_NODE)
-        {
-            bool deep = true;
-            HTMLElementImpl *e = static_cast<HTMLElementImpl *>(current);
-            switch(type)
-            {
-            case DOC_IMAGES:
-                if(e->id() == ID_IMG)
-                    len++;
-                break;
-            case DOC_FORMS:
-                if(e->id() == ID_FORM)
-                    len++;
-                break;
-            case TABLE_TBODIES:
-                if(e->id() == ID_TBODY)
-                    len++;
-                else if(e->id() == ID_TABLE)
-                    deep = false;
-                break;
-            case TR_CELLS:
-                if(e->id() == ID_TD || e->id() == ID_TH)
-                    len++;
-                else if(e->id() == ID_TABLE)
-                    deep = false;
-                break;
-            case TABLE_ROWS:
-            case TSECTION_ROWS:
-                if(e->id() == ID_TR)
-                    len++;
-                else if(e->id() == ID_TABLE)
-                    deep = false;
-                break;
-            case SELECT_OPTIONS:
-                if(e->id() == ID_OPTION)
-                    len++;
-                break;
-            case MAP_AREAS:
-                if(e->id() == ID_AREA)
-                    len++;
-                break;
-            case DOC_APPLETS:   // all OBJECT and APPLET elements
-                if(e->id() == ID_OBJECT || e->id() == ID_APPLET)
-                    len++;
-                break;
-            case DOC_EMBEDS:   // all EMBED elements
-                if(e->id() == ID_EMBED)
-                    len++;
-                break;
-            case DOC_LINKS:     // all A _and_ AREA elements with a value for href
-                if(e->id() == ID_A || e->id() == ID_AREA)
-                    if(!e->getAttribute(ATTR_HREF).isNull())
-                        len++;
-                break;
-            case DOC_ANCHORS:      // all A elements with a value for name or an id attribute
-                if(e->id() == ID_A)
-                    if(!e->getAttribute(ATTR_NAME).isNull())
-                        len++;
-                break;
-            case DOC_ALL:
-                len++;
-                break;
-            case NODE_CHILDREN:
-                len++;
-                deep = false;
-                break;
-            default:
-                kdDebug( 6030 ) << "Error in HTMLCollection, wrong tagId!" << endl;
-            }
-            if(len == (index + 1)) return current;
-            if (deep) {
-                current = current->traverseNextNode(base);
-                continue;
-            } 
-        }
-        current = current->traverseNextSibling(base);
-    }
-    return 0;
-}
-
 NodeImpl *HTMLCollectionImpl::item( unsigned long index ) const
 {
      resetCollectionInfo();
 NodeImpl *HTMLCollectionImpl::item( unsigned long index ) const
 {
      resetCollectionInfo();
@@ -269,13 +199,15 @@ NodeImpl *HTMLCollectionImpl::item( unsigned long index ) const
          return 0;
      }
      if (!info->current || info->position > index) {
          return 0;
      }
      if (!info->current || info->position > index) {
-         info->current = base->firstChild();
+         info->current = traverseNextItem(base);
          info->position = 0;
          if (!info->current)
              return 0;
      }
          info->position = 0;
          if (!info->current)
              return 0;
      }
-     int pos = (int) info->position;
-     NodeImpl *node = getItem(info->current, index, pos);
+     NodeImpl *node = info->current;
+     for (unsigned pos = info->position; pos < index; pos++) {
+         node = traverseNextItem(node);
+     }     
      info->current = node;
      info->position = index;
      return info->current;
      info->current = node;
      info->position = index;
      return info->current;
@@ -289,115 +221,34 @@ NodeImpl *HTMLCollectionImpl::firstItem() const
 NodeImpl *HTMLCollectionImpl::nextItem() const
 {
      resetCollectionInfo();
 NodeImpl *HTMLCollectionImpl::nextItem() const
 {
      resetCollectionInfo();
-     int pos = 0;
  
      // Look for the 'second' item. The first one is currentItem, already given back.
  
      // Look for the 'second' item. The first one is currentItem, already given back.
-     NodeImpl *retval = getItem(info->current, 1, pos);
-
+     NodeImpl *retval = traverseNextItem(info->current);
      info->current = retval;
      info->current = retval;
+     info->position++;
      return retval;
 }
 
      return retval;
 }
 
-NodeImpl *HTMLCollectionImpl::getNamedItem( NodeImpl *current, int attr_id,
-                                            const DOMString &name, bool caseSensitive ) const
+bool HTMLCollectionImpl::checkForNameMatch(NodeImpl *node, bool checkName, const DOMString &name, bool caseSensitive) const
 {
 {
-    if(name.isEmpty())
-        return 0;
-
-    while(current)
-    {
-        if(current->nodeType() == Node::ELEMENT_NODE)
-        {
-            bool deep = true;
-            bool check = false;
-            HTMLElementImpl *e = static_cast<HTMLElementImpl *>(current);
-            switch(type)
-            {
-            case DOC_IMAGES:
-                if(e->id() == ID_IMG)
-                    check = true;
-                break;
-            case DOC_FORMS:
-                if(e->id() == ID_FORM)
-                    check = true;
-                break;
-            case TABLE_TBODIES:
-                if(e->id() == ID_TBODY)
-                    check = true;
-                else if(e->id() == ID_TABLE)
-                    deep = false;
-                break;
-            case TR_CELLS:
-                if(e->id() == ID_TD || e->id() == ID_TH)
-                    check = true;
-                else if(e->id() == ID_TABLE)
-                    deep = false;
-                break;
-            case TABLE_ROWS:
-            case TSECTION_ROWS:
-                if(e->id() == ID_TR)
-                    check = true;
-                else if(e->id() == ID_TABLE)
-                    deep = false;
-                break;
-            case SELECT_OPTIONS:
-                if(e->id() == ID_OPTION)
-                    check = true;
-                break;
-            case MAP_AREAS:
-                if(e->id() == ID_AREA)
-                    check = true;
-                break;
-            case DOC_APPLETS:   // all OBJECT and APPLET elements
-                if(e->id() == ID_OBJECT || e->id() == ID_APPLET)
-                    check = true;
-                break;
-            case DOC_EMBEDS:   // all EMBED elements
-                if(e->id() == ID_EMBED)
-                    check = true;
-                break;
-            case DOC_LINKS:     // all A _and_ AREA elements with a value for href
-                if(e->id() == ID_A || e->id() == ID_AREA)
-                    if(!e->getAttribute(ATTR_HREF).isNull())
-                        check = true;
-                break;
-            case DOC_ANCHORS:      // all A elements with a value for name
-                if(e->id() == ID_A)
-                    if(!e->getAttribute(ATTR_NAME).isNull())
-                        check = true;
-                break;
-            case DOC_ALL:
-                check = true;
-                break;
-            case NODE_CHILDREN:
-                check = true;
-                deep = false;
-                break;
-            default:
-                kdDebug( 6030 ) << "Error in HTMLCollection, wrong tagId!" << endl;
-                break;
-            }
-            if (check) {
-                bool found;
-                if (caseSensitive)
-                    found = e->getAttribute(attr_id) == name;
-                else
-                    found = e->getAttribute(attr_id).domString().lower() == name.lower();
-                if (found) {
-                    //kdDebug( 6030 ) << "found node: " << e << " " << current << " " << e->id() << " " << e->tagName().string() << endl;
-                    return current;
-                }
-            }
-            if (deep) {
-                current = current->traverseNextNode(base);
-                continue;
-            } 
+    ElementImpl *e = static_cast<ElementImpl *>(node);
+    if (caseSensitive) {
+        if (checkName) {
+            return e->getAttribute(ATTR_NAME) == name && e->getAttribute(ATTR_ID) != name;
+        } else {
+            return e->getAttribute(ATTR_ID) == name;
+        }
+    } else {
+        if (checkName) {
+            return e->getAttribute(ATTR_NAME).domString().lower() == name.lower() &&
+                e->getAttribute(ATTR_ID).domString().lower() != name.lower();
+        } else {
+            return e->getAttribute(ATTR_ID).domString().lower() == name.lower();
         }
         }
-        current = current->traverseNextSibling(base);
     }
     }
-    return 0;
 }
 
 }
 
+
 NodeImpl *HTMLCollectionImpl::namedItem( const DOMString &name, bool caseSensitive ) const
 {
     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
 NodeImpl *HTMLCollectionImpl::namedItem( const DOMString &name, bool caseSensitive ) const
 {
     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
@@ -407,65 +258,81 @@ NodeImpl *HTMLCollectionImpl::namedItem( const DOMString &name, bool caseSensiti
     // that are allowed a name attribute.
     resetCollectionInfo();
     idsDone = false;
     // that are allowed a name attribute.
     resetCollectionInfo();
     idsDone = false;
-    info->current = getNamedItem(base->firstChild(), ATTR_ID, name);
+
+    NodeImpl *n;
+    for (n = traverseNextItem(base); n; n = traverseNextItem(n)) {
+        if (checkForNameMatch(n, idsDone, name, caseSensitive)) {
+            break;
+        }
+    }
+        
+    info->current = n;
     if(info->current)
         return info->current;
     idsDone = true;
     if(info->current)
         return info->current;
     idsDone = true;
-    info->current = getNamedItem(base->firstChild(), ATTR_NAME, name);
+
+    for (n = traverseNextItem(base); n; n = traverseNextItem(n)) {
+        if (checkForNameMatch(n, idsDone, name, caseSensitive)) {
+            break;
+        }
+    }
+
+    info->current = n;
     return info->current;
 }
 
     return info->current;
 }
 
-NodeImpl *HTMLCollectionImpl::nextNamedItem( const DOMString &name ) const
+QValueList<Node> HTMLCollectionImpl::namedItems(const DOMString &name) const
 {
 {
-    // nextNamedItemInternal can return an item that has both id=<name> and name=<name>
-    // Here, we have to filter out such cases.
-    NodeImpl *impl = nextNamedItemInternal( name );
-    if (!idsDone) // looking for id=<name> -> no filtering
-        return impl;
-    // looking for name=<name> -> filter out if id=<name>
-    bool ok = false;
-    while (impl && !ok)
-    {
-        if(impl->nodeType() == Node::ELEMENT_NODE)
-        {
-            HTMLElementImpl *e = static_cast<HTMLElementImpl *>(impl);
-            ok = (e->getAttribute(ATTR_ID) != name);
-            if (!ok)
-                impl = nextNamedItemInternal( name );
-        } else // can't happen
-            ok = true;
+    resetCollectionInfo();
+    
+    QValueList<Node> idResults;
+    QValueList<Node> nameResults;
+
+    for (NodeImpl *n = traverseNextItem(base); n; n = traverseNextItem(n)) {
+        if (checkForNameMatch(n, false, name, true)) {
+            idResults.append(Node(n));
+        } 
+        if (checkForNameMatch(n, true, name, true)) {
+            nameResults.append(Node(n));
+        }
     }
     }
-    return impl;
+
+    if (idResults.isEmpty())
+        return nameResults;
+
+    for (QValueListIterator<Node> iter = nameResults.begin(); iter != nameResults.end(); ++iter) {
+        idResults.append(*iter);
+    }
+
+    return idResults;
 }
 
 }
 
-NodeImpl *HTMLCollectionImpl::nextNamedItemInternal( const DOMString &name ) const
+
+NodeImpl *HTMLCollectionImpl::nextNamedItem( const DOMString &name ) const
 {
     resetCollectionInfo();
 {
     resetCollectionInfo();
-    //kdDebug() << "\nHTMLCollectionImpl::nextNamedItem starting at " << info->current << endl;
-    // Go to next item first (to avoid returning the same)
-    nextItem(); // sets info->current and invalidates info->postion
-    //kdDebug() << "*HTMLCollectionImpl::nextNamedItem next item is " << info->current << endl;
 
 
-    if ( info->current )
-    {
-        // Then look for next matching named item
-        NodeImpl *retval = getNamedItem(info->current, idsDone ? ATTR_NAME : ATTR_ID, name);
-        if ( retval )
-        {
-            //kdDebug() << "*HTMLCollectionImpl::nextNamedItem found " << retval << endl;
-            info->current = retval;
-            return retval;
+    for (NodeImpl *n = traverseNextItem(info->current ? info->current : base); n; n = traverseNextItem(n)) {
+        if (checkForNameMatch(n, idsDone, name, true)) {
+            info->current = n;
+            return n;
         }
     }
         }
     }
-
-    if ( idsDone )
+    
+    if (idsDone) {
+        info->current = 0; 
         return 0;
         return 0;
-    // After doing all ATTR_ID, do ATTR_NAME
-    //kdDebug() << "*HTMLCollectionImpl::nextNamedItem going to ATTR_NAME now" << endl;
+    }
     idsDone = true;
     idsDone = true;
-    info->current = getNamedItem(base->firstChild(), ATTR_NAME, name);
-    return info->current;
 
 
+    for (NodeImpl *n = traverseNextItem(info->current ? info->current : base); n; n = traverseNextItem(n)) {
+        if (checkForNameMatch(n, idsDone, name, true)) {
+            info->current = n;
+            return n;
+        }
+    }
+
+    return 0;
 }
 
 // -----------------------------------------------------------------------------
 }
 
 // -----------------------------------------------------------------------------
@@ -489,7 +356,7 @@ void HTMLFormCollectionImpl::resetCollectionInfo() const
     HTMLCollectionImpl::resetCollectionInfo();
 }
 
     HTMLCollectionImpl::resetCollectionInfo();
 }
 
-unsigned long HTMLFormCollectionImpl::calcLength(NodeImpl*) const
+unsigned long HTMLFormCollectionImpl::calcLength() const
 {
     QPtrVector<HTMLGenericFormElementImpl> &l = static_cast<HTMLFormElementImpl*>( base )->formElements;
 
 {
     QPtrVector<HTMLGenericFormElementImpl> &l = static_cast<HTMLFormElementImpl*>( base )->formElements;
 
@@ -613,3 +480,102 @@ NodeImpl * HTMLFormCollectionImpl::nextNamedItemInternal( const DOMString &name
     idsDone = true;
     return getNamedItem(base->firstChild(), ATTR_NAME, name, true);
 }
     idsDone = true;
     return getNamedItem(base->firstChild(), ATTR_NAME, name, true);
 }
+
+NodeImpl *HTMLFormCollectionImpl::namedItem( const DOMString &name, bool caseSensitive ) const
+{
+    // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
+    // This method first searches for an object with a matching id
+    // attribute. If a match is not found, the method then searches for an
+    // object with a matching name attribute, but only on those elements
+    // that are allowed a name attribute.
+    resetCollectionInfo();
+    idsDone = false;
+    info->current = getNamedItem(base->firstChild(), ATTR_ID, name, true);
+    if(info->current)
+        return info->current;
+    idsDone = true;
+    info->current = getNamedItem(base->firstChild(), ATTR_NAME, name, true);
+    return info->current;
+}
+
+
+NodeImpl *HTMLFormCollectionImpl::nextNamedItem( const DOMString &name ) const
+{
+    // nextNamedItemInternal can return an item that has both id=<name> and name=<name>
+    // Here, we have to filter out such cases.
+    NodeImpl *impl = nextNamedItemInternal( name );
+    if (!idsDone) // looking for id=<name> -> no filtering
+        return impl;
+    // looking for name=<name> -> filter out if id=<name>
+    bool ok = false;
+    while (impl && !ok)
+    {
+        if(impl->nodeType() == Node::ELEMENT_NODE)
+        {
+            HTMLElementImpl *e = static_cast<HTMLElementImpl *>(impl);
+            ok = (e->getAttribute(ATTR_ID) != name);
+            if (!ok)
+                impl = nextNamedItemInternal( name );
+        } else // can't happen
+            ok = true;
+    }
+    return impl;
+}
+
+QValueList<Node> HTMLFormCollectionImpl::namedItems(const DOMString &name) const
+{
+    if (name.length()) {
+        return QValueList<Node>();
+    }
+
+    resetCollectionInfo();
+
+    QValueList<Node> idResults;
+    QValueList<Node> nameResults;
+
+    if (base->nodeType() != Node::ELEMENT_NODE ||static_cast<HTMLElementImpl*>(base)->id() != ID_FORM)
+        return idResults;
+
+    HTMLElementImpl* baseElement = static_cast<HTMLElementImpl*>(base);
+
+    bool foundInputElements = false;
+    HTMLFormElementImpl* f = static_cast<HTMLFormElementImpl*>(baseElement);
+    for (unsigned i = 0; i < f->formElements.count(); ++i) {
+        HTMLGenericFormElementImpl* e = f->formElements[i];
+        if (e->isEnumeratable()) {
+            if (checkForNameMatch(e, false, name, true)) {
+                idResults.append(Node(e));
+                foundInputElements = true;
+            } 
+            if (checkForNameMatch(e, true, name, true)) {
+                nameResults.append(Node(e));
+                foundInputElements = true;
+            }
+        }
+    }
+
+    if (!foundInputElements) {
+        HTMLFormElementImpl* f = static_cast<HTMLFormElementImpl*>(baseElement);
+
+        for (unsigned i = 0; i < f->imgElements.count(); ++i) {
+            HTMLImageElementImpl* e = f->imgElements[i];
+
+            if (checkForNameMatch(e, false, name, true)) {
+                idResults.append(Node(e));
+            } 
+            if (checkForNameMatch(e, true, name, true)) {
+                nameResults.append(Node(e));
+            }
+        }
+    }
+
+    if (idResults.isEmpty())
+        return nameResults;
+
+    for (QValueListIterator<Node> iter = nameResults.begin(); iter != nameResults.end(); ++iter) {
+        idResults.append(*iter);
+    }
+
+    return idResults;
+}
+
index 72656f5..5cec109 100644 (file)
@@ -83,6 +83,8 @@ public:
     // In case of multiple items named the same way
     NodeImpl *nextNamedItem( const DOMString &name ) const;
 
     // In case of multiple items named the same way
     NodeImpl *nextNamedItem( const DOMString &name ) const;
 
+    virtual QValueList<Node> namedItems( const DOMString &name ) const;
+
     struct CollectionInfo {
         CollectionInfo() : version(0), current(0), position(0), length(0), haslength(false) {}
         unsigned int version;
     struct CollectionInfo {
         CollectionInfo() : version(0), current(0), position(0), length(0), haslength(false) {}
         unsigned int version;
@@ -93,10 +95,9 @@ public:
      };
 
 protected:
      };
 
 protected:
-    virtual unsigned long calcLength(NodeImpl *current) const;
-    virtual NodeImpl *getItem(NodeImpl *current, int index, int &pos) const;
-    virtual NodeImpl *getNamedItem(NodeImpl *current, int attr_id, const DOMString &name, bool caseSensitive = true) const;
-    virtual NodeImpl *nextNamedItemInternal( const DOMString &name ) const;
+    virtual NodeImpl *traverseNextItem(NodeImpl *start) const;
+    bool checkForNameMatch(NodeImpl *node, bool checkName, const DOMString &name, bool caseSensitive) const;
+    virtual unsigned long calcLength() const;
     virtual void resetCollectionInfo() const;
     // the base node, the collection refers to
     NodeImpl *base;
     virtual void resetCollectionInfo() const;
     // the base node, the collection refers to
     NodeImpl *base;
@@ -129,8 +130,13 @@ public:
     virtual NodeImpl *item ( unsigned long index ) const;
     virtual NodeImpl *firstItem() const;
     virtual NodeImpl *nextItem() const;
     virtual NodeImpl *item ( unsigned long index ) const;
     virtual NodeImpl *firstItem() const;
     virtual NodeImpl *nextItem() const;
+
+    NodeImpl *namedItem ( const DOMString &name, bool caseSensitive = true ) const;
+    NodeImpl *nextNamedItem( const DOMString &name ) const;
+
+    virtual QValueList<Node> namedItems( const DOMString &name ) const;
 protected:
 protected:
-    virtual unsigned long calcLength(NodeImpl* current) const;
+    virtual unsigned long calcLength() const;
     virtual NodeImpl *getNamedItem(NodeImpl* current, int attr_id, const DOMString& name, bool caseSensitive) const;
     virtual NodeImpl *nextNamedItemInternal( const DOMString &name ) const;
 private:
     virtual NodeImpl *getNamedItem(NodeImpl* current, int attr_id, const DOMString& name, bool caseSensitive) const;
     virtual NodeImpl *nextNamedItemInternal( const DOMString &name ) const;
 private: