JavaScriptCore:
authormjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 31 Jan 2007 13:43:13 +0000 (13:43 +0000)
committermjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 31 Jan 2007 13:43:13 +0000 (13:43 +0000)
        Reviewed by Mark with help from Lars.

        - added new ListHashSet class, which combines a hashtable and a linked list to provide a set
        that keeps elements in inserted order

        This is to assist in fixing the following:
        <rdar://problem/4751164> REGRESSION: Safari places text on incorrect button when returning to a page via back [10541]
        http://bugs.webkit.org/show_bug.cgi?id=10541

        * JavaScriptCore.vcproj/WTF/WTF.vcproj:
        * JavaScriptCore.xcodeproj/project.pbxproj:
        * wtf/HashTable.h:
        (WTF::HashTable::find):
        (WTF::HashTable::contains):
        (WTF::::find):
        (WTF::::contains):
        * wtf/ListHashSet.h: Added.
        (WTF::ListHashSetNode::ListHashSetNode):
        (WTF::ListHashSetNodeHashFunctions::hash):
        (WTF::ListHashSetNodeHashFunctions::equal):
        (WTF::ListHashSetIterator::ListHashSetIterator):
        (WTF::ListHashSetIterator::get):
        (WTF::ListHashSetIterator::operator*):
        (WTF::ListHashSetIterator::operator->):
        (WTF::ListHashSetIterator::operator++):
        (WTF::ListHashSetIterator::operator--):
        (WTF::ListHashSetIterator::operator==):
        (WTF::ListHashSetIterator::operator!=):
        (WTF::ListHashSetIterator::operator const_iterator):
        (WTF::ListHashSetIterator::node):
        (WTF::ListHashSetConstIterator::ListHashSetConstIterator):
        (WTF::ListHashSetConstIterator::get):
        (WTF::ListHashSetConstIterator::operator*):
        (WTF::ListHashSetConstIterator::operator->):
        (WTF::ListHashSetConstIterator::operator++):
        (WTF::ListHashSetConstIterator::operator--):
        (WTF::ListHashSetConstIterator::operator==):
        (WTF::ListHashSetConstIterator::operator!=):
        (WTF::ListHashSetConstIterator::node):
        (WTF::ListHashSetTranslator::hash):
        (WTF::ListHashSetTranslator::equal):
        (WTF::ListHashSetTranslator::translate):
        (WTF::::ListHashSet):
        (WTF::::operator):
        (WTF::::~ListHashSet):
        (WTF::::size):
        (WTF::::capacity):
        (WTF::::isEmpty):
        (WTF::::begin):
        (WTF::::end):
        (WTF::::find):
        (WTF::::contains):
        (WTF::::add):
        (WTF::::remove):
        (WTF::::clear):
        (WTF::::unlinkAndDelete):
        (WTF::::appendNode):
        (WTF::::deleteAllNodes):
        (WTF::::makeIterator):
        (WTF::::makeConstIterator):
        (WTF::deleteAllValues):

WebCore:

        Reviewed by Mark.

        - fixed <rdar://problem/4751164> REGRESSION: Safari places text on incorrect button when returning to a page via back [10541]
        http://bugs.webkit.org/show_bug.cgi?id=10541

        * dom/Document.cpp:
        (WebCore::Document::formElementsState):
        * dom/Document.h:

        I couldn't figure out the back/forward support in the tests enough
        to make an automated test, but this maual test reproduces the
        problem 100% without this patch:

        * manual-tests/back.html: Added.
        * manual-tests/form-control-madness.html: Added.

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

JavaScriptCore/ChangeLog
JavaScriptCore/JavaScriptCore.vcproj/WTF/WTF.vcproj
JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
JavaScriptCore/wtf/HashTable.h
JavaScriptCore/wtf/ListHashSet.h [new file with mode: 0644]
WebCore/ChangeLog
WebCore/dom/Document.cpp
WebCore/dom/Document.h
WebCore/manual-tests/back.html [new file with mode: 0644]
WebCore/manual-tests/form-control-madness.html [new file with mode: 0644]

index ba4768c5a5a99f827ff6407003cc548fc47e0eb9..f1cd075837e6dcc507d130799a7110d6c6369e04 100644 (file)
@@ -1,3 +1,67 @@
+2007-01-31  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Mark with help from Lars.
+        
+        - added new ListHashSet class, which combines a hashtable and a linked list to provide a set
+        that keeps elements in inserted order
+        
+        This is to assist in fixing the following:
+        <rdar://problem/4751164> REGRESSION: Safari places text on incorrect button when returning to a page via back [10541]
+        http://bugs.webkit.org/show_bug.cgi?id=10541
+
+        * JavaScriptCore.vcproj/WTF/WTF.vcproj:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * wtf/HashTable.h:
+        (WTF::HashTable::find):
+        (WTF::HashTable::contains):
+        (WTF::::find):
+        (WTF::::contains):
+        * wtf/ListHashSet.h: Added.
+        (WTF::ListHashSetNode::ListHashSetNode):
+        (WTF::ListHashSetNodeHashFunctions::hash):
+        (WTF::ListHashSetNodeHashFunctions::equal):
+        (WTF::ListHashSetIterator::ListHashSetIterator):
+        (WTF::ListHashSetIterator::get):
+        (WTF::ListHashSetIterator::operator*):
+        (WTF::ListHashSetIterator::operator->):
+        (WTF::ListHashSetIterator::operator++):
+        (WTF::ListHashSetIterator::operator--):
+        (WTF::ListHashSetIterator::operator==):
+        (WTF::ListHashSetIterator::operator!=):
+        (WTF::ListHashSetIterator::operator const_iterator):
+        (WTF::ListHashSetIterator::node):
+        (WTF::ListHashSetConstIterator::ListHashSetConstIterator):
+        (WTF::ListHashSetConstIterator::get):
+        (WTF::ListHashSetConstIterator::operator*):
+        (WTF::ListHashSetConstIterator::operator->):
+        (WTF::ListHashSetConstIterator::operator++):
+        (WTF::ListHashSetConstIterator::operator--):
+        (WTF::ListHashSetConstIterator::operator==):
+        (WTF::ListHashSetConstIterator::operator!=):
+        (WTF::ListHashSetConstIterator::node):
+        (WTF::ListHashSetTranslator::hash):
+        (WTF::ListHashSetTranslator::equal):
+        (WTF::ListHashSetTranslator::translate):
+        (WTF::::ListHashSet):
+        (WTF::::operator):
+        (WTF::::~ListHashSet):
+        (WTF::::size):
+        (WTF::::capacity):
+        (WTF::::isEmpty):
+        (WTF::::begin):
+        (WTF::::end):
+        (WTF::::find):
+        (WTF::::contains):
+        (WTF::::add):
+        (WTF::::remove):
+        (WTF::::clear):
+        (WTF::::unlinkAndDelete):
+        (WTF::::appendNode):
+        (WTF::::deleteAllNodes):
+        (WTF::::makeIterator):
+        (WTF::::makeConstIterator):
+        (WTF::deleteAllValues):
+
 2007-01-30  Darin Adler  <darin@apple.com>
 
         * kjs/DateMath.cpp: Fix license header to reflect LGPL as the first license
index 2d6a8506601280bd3d4b730c6d251c174b4b088b..a4767c6ac4c0d84227c519168b984e6a419f20a1 100644 (file)
                        RelativePath="..\..\wtf\HashTraits.h"\r
                        >\r
                </File>\r
+               <File\r
+                       RelativePath="..\..\wtf\ListHashSet.h"\r
+                       >\r
+               </File>\r
                <File\r
                        RelativePath="..\..\wtf\ListRefPtr.h"\r
                        >\r
index bcb0a39b67b7015b3a27ab5169f74eba25308f41..17a94fbc073090ec06488432a1bf16f9eac22917 100644 (file)
@@ -88,6 +88,7 @@
                6541BD7508E80A17002CBEE7 /* TCSystemAlloc.h in Headers */ = {isa = PBXBuildFile; fileRef = 6541BD7108E80A17002CBEE7 /* TCSystemAlloc.h */; };
                65621E6D089E859700760F35 /* property_slot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 65621E6B089E859700760F35 /* property_slot.cpp */; };
                65621E6E089E859700760F35 /* property_slot.h in Headers */ = {isa = PBXBuildFile; fileRef = 65621E6C089E859700760F35 /* property_slot.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               657EB7460B708F540063461B /* ListHashSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 657EB7450B708F540063461B /* ListHashSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
                657EEBC0094E445E008C9C7B /* HashCountedSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 657EEBBF094E445E008C9C7B /* HashCountedSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
                6580F796094070560082C219 /* PassRefPtr.h in Headers */ = {isa = PBXBuildFile; fileRef = 6580F795094070560082C219 /* PassRefPtr.h */; settings = {ATTRIBUTES = (Private, ); }; };
                6592C318098B7DE10003D4F6 /* Vector.h in Headers */ = {isa = PBXBuildFile; fileRef = 6592C316098B7DE10003D4F6 /* Vector.h */; settings = {ATTRIBUTES = (Private, ); }; };
                6560A63D04B3B69F008AE952 /* CoreServices.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = CoreServices.framework; path = /System/Library/Frameworks/CoreServices.framework; sourceTree = "<absolute>"; };
                65621E6B089E859700760F35 /* property_slot.cpp */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.cpp.cpp; path = property_slot.cpp; sourceTree = "<group>"; tabWidth = 8; };
                65621E6C089E859700760F35 /* property_slot.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = property_slot.h; sourceTree = "<group>"; tabWidth = 8; };
+               657EB7450B708F540063461B /* ListHashSet.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = ListHashSet.h; sourceTree = "<group>"; };
                657EEBBF094E445E008C9C7B /* HashCountedSet.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = HashCountedSet.h; sourceTree = "<group>"; tabWidth = 8; };
                6580F795094070560082C219 /* PassRefPtr.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = PassRefPtr.h; sourceTree = "<group>"; tabWidth = 8; };
                6592C316098B7DE10003D4F6 /* Vector.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = Vector.h; sourceTree = "<group>"; };
                65162EF108E6A21C007556CD /* wtf */ = {
                        isa = PBXGroup;
                        children = (
+                               657EB7450B708F540063461B /* ListHashSet.h */,
                                E195678D09E7CF1200B89D13 /* unicode */,
                                93AA4F770957251F0084B3A7 /* AlwaysInline.h */,
                                65E217B808E7EECC0023E5F6 /* Assertions.cpp */,
                                D212022B0AD4310D00ED79B6 /* DateMath.h in Headers */,
                                E11D51760B2E798D0056C188 /* StringExtras.h in Headers */,
                                146AAB2B0B66A84900E55F16 /* JSStringRefCF.h in Headers */,
+                               657EB7460B708F540063461B /* ListHashSet.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
index 0e6a6a2ac2cbf23e3fccce750ec480ce1d0befe4..e41e816357efc19cd5bc483fd39404498c8ca433 100644 (file)
@@ -291,9 +291,13 @@ namespace WTF {
         // in the table.
         template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&);
 
-        iterator find(const KeyType&);
-        const_iterator find(const KeyType&) const;
-        bool contains(const KeyType&) const;
+        iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); }
+        const_iterator find(const KeyType& key) const { return find<KeyType, IdentityTranslatorType>(key); }
+        bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); }
+
+        template <typename T, typename HashTranslator> iterator find(const T&);
+        template <typename T, typename HashTranslator> const_iterator find(const T&) const;
+        template <typename T, typename HashTranslator> bool contains(const T&) const;
 
         void remove(const KeyType&);
         void remove(iterator);
@@ -467,36 +471,39 @@ namespace WTF {
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key)
+    template <typename T, typename HashTranslator> 
+    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key)
     {
         if (!m_table)
             return end();
 
-        LookupType result = lookup(key);
+        LookupType result = lookup<T, HashTranslator>(key).first;
         if (!result.second)
             return end();
         return makeIterator(result.first);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key) const
+    template <typename T, typename HashTranslator> 
+    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const
     {
         if (!m_table)
             return end();
 
-        LookupType result = const_cast<HashTable *>(this)->lookup(key);
+        LookupType result = const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key).first;
         if (!result.second)
             return end();
         return makeConstIterator(result.first);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const
+    template <typename T, typename HashTranslator> 
+    bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const
     {
         if (!m_table)
             return false;
 
-        return const_cast<HashTable *>(this)->lookup(key).second;
+        return const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key).first.second;
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
diff --git a/JavaScriptCore/wtf/ListHashSet.h b/JavaScriptCore/wtf/ListHashSet.h
new file mode 100644 (file)
index 0000000..d8ecaa5
--- /dev/null
@@ -0,0 +1,470 @@
+// -*- mode: c++; c-basic-offset: 4 -*-
+/*
+ * Copyright (C) 2005, 2006, 2007 Apple Inc.
+ *
+ * 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.
+ *
+ */
+
+#ifndef WTF_ListHashSet_h
+#define WTF_ListHashSet_h
+
+#include "HashTable.h"
+#include "HashSet.h"
+
+namespace WTF {
+
+    // ListHashSet: just like HashSet, this class provides a Set
+    // interface - a collection of unique objects with O(1) insertion,
+    // removal and test for containership. However, it also has an
+    // order - iterating it will always give back values in the order
+    // in which they are added.
+
+    // In theory it would be possible to add prepend, insertAfter, insertBefore,
+    // and an append that moves the element to the end even if already present,
+    // but unclear yet if these are needed.
+
+    template<typename Value, typename HashFunctions> class ListHashSet;
+
+    template<typename T> struct IdentityExtractor;
+
+    template<typename Value, typename HashFunctions>
+    void deleteAllValues(const ListHashSet<Value, HashFunctions>&);
+
+    template<typename ValueArg, typename HashArg> class ListHashSetIterator;
+    template<typename ValueArg, typename HashArg> class ListHashSetConstIterator;
+
+    template<typename ValueArg> struct ListHashSetNode;
+    template<typename ValueArg, typename HashArg> struct ListHashSetNodeHashFunctions;
+
+    template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
+    private:
+        typedef ListHashSetNode<ValueArg> Node;
+
+        typedef HashTraits<Node*> NodeTraits;
+        typedef ListHashSetNodeHashFunctions<ValueArg, HashArg> NodeHash;
+
+        typedef HashTable<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplType;
+
+        typedef HashArg HashFunctions;
+
+    public:
+        typedef ValueArg ValueType;
+        typedef ListHashSetIterator<ValueType, HashArg> iterator;
+        typedef ListHashSetConstIterator<ValueType, HashArg> const_iterator;
+
+        friend class ListHashSetConstIterator<ValueType, HashArg>;
+
+        ListHashSet();
+        ListHashSet(const ListHashSet&);
+        ListHashSet& operator=(const ListHashSet&);
+        ~ListHashSet();
+
+        int size() const;
+        int capacity() const;
+        bool isEmpty() const;
+
+        iterator begin();
+        iterator end();
+        const_iterator begin() const;
+        const_iterator end() const;
+
+        iterator find(const ValueType&);
+        const_iterator find(const ValueType&) const;
+        bool contains(const ValueType&) const;
+
+        // the return value is a pair of an interator to the new value's location, 
+        // and a bool that is true if an new entry was added
+        pair<iterator, bool> add(const ValueType&);
+
+        void remove(const ValueType&);
+        void remove(iterator);
+        void clear();
+
+    private:
+        void unlinkAndDelete(Node*);
+        void appendNode(Node*);
+        void deleteAllNodes();
+        iterator makeIterator(Node*);
+        const_iterator makeConstIterator(Node*) const;
+
+        friend void deleteAllValues<>(const ListHashSet&);
+
+        ImplType m_impl;
+        Node* m_head;
+        Node* m_tail;
+    };
+
+    template<typename ValueArg> struct ListHashSetNode {
+        // FIXME: arguably this should use a recycling custom allocator
+        ListHashSetNode(ValueArg value) : m_value(value), m_prev(0), m_next(0) {}
+        ValueArg m_value;
+        ListHashSetNode* m_prev;
+        ListHashSetNode* m_next;
+    };
+
+    template<typename ValueArg, typename HashArg> struct ListHashSetNodeHashFunctions {
+        typedef ListHashSetNode<ValueArg> Node;
+        
+        static unsigned hash(Node* const& key) { return HashArg::hash(key->m_value); }
+        static bool equal(Node* const& a, Node* const& b) { return HashArg::equal(a->m_value, b->m_value); }
+    };
+
+    template<typename ValueArg, typename HashArg> class ListHashSetIterator
+    {
+    private:
+        typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
+        typedef ListHashSetIterator<ValueArg, HashArg> iterator;
+        typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
+        typedef ListHashSetNode<ValueArg> Node;
+        typedef ValueArg ValueType;
+        typedef ValueType& ReferenceType;
+        typedef ValueType* PointerType;
+
+        friend class ListHashSet<ValueArg, HashArg>;
+
+        ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
+
+    public:
+        ListHashSetIterator() { }
+
+        // default copy, assignment and destructor are OK
+
+        PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
+        ReferenceType operator*() const { return *get(); }
+        PointerType operator->() const { return get(); }
+
+        iterator& operator++() { ++m_iterator; return *this; }
+
+        // postfix ++ intentionally omitted
+
+        iterator& operator--() { --m_iterator; return *this; }
+
+        // postfix -- intentionally omitted
+
+        // Comparison.
+        bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
+        bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
+
+        operator const_iterator() const { return m_iterator; }
+
+    private:
+        Node* node() { return m_iterator.node(); }
+
+        const_iterator m_iterator;
+    };
+
+    template<typename ValueArg, typename HashArg> class ListHashSetConstIterator
+    {
+    private:
+        typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
+        typedef ListHashSetIterator<ValueArg, HashArg> iterator;
+        typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
+        typedef ListHashSetNode<ValueArg> Node;
+        typedef ValueArg ValueType;
+        typedef const ValueType& ReferenceType;
+        typedef const ValueType* PointerType;
+
+        friend class ListHashSet<ValueArg, HashArg>;
+        friend class ListHashSetIterator<ValueArg, HashArg>;
+
+        ListHashSetConstIterator(const ListHashSetType* set, Node* position)
+            : m_set(set)
+            , m_position(position)
+        {
+        }
+
+    public:
+        ListHashSetConstIterator()
+        {
+        }
+
+        // default copy, assignment and destructor are OK if CHECK_HASHTABLE_ITERATORS is 0
+
+        PointerType get() const
+        {
+            return &m_position->m_value;
+        }
+        ReferenceType operator*() const { return *get(); }
+        PointerType operator->() const { return get(); }
+
+        const_iterator& operator++()
+        {
+            ASSERT(m_position != 0);
+            m_position = m_position->m_next;
+            return *this;
+        }
+
+        // postfix ++ intentionally omitted
+
+        const_iterator& operator--()
+        {
+            ASSERT(m_position != m_set->m_head);
+            m_position = m_position->m_prev;
+            return *this;
+        }
+
+        // postfix -- intentionally omitted
+
+        // Comparison.
+        bool operator==(const const_iterator& other) const
+        {
+            return m_position == other.m_position;
+        }
+        bool operator!=(const const_iterator& other) const
+        {
+            return m_position != other.m_position;
+        }
+
+    private:
+        Node* node() { return m_position; }
+
+        const ListHashSetType* m_set;
+        Node* m_position;
+    };
+
+
+    template<typename ValueType, typename HashFunctions>
+    struct ListHashSetTranslator {
+    private:
+        typedef ListHashSetNode<ValueType> Node;
+    public:
+        static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
+        static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); }
+        static void translate(Node*& location, const ValueType& key, const ValueType&, unsigned)
+        {
+            location = new Node(key);
+        }
+    };
+
+    template<typename T, typename U>
+    inline ListHashSet<T, U>::ListHashSet()
+        : m_head(0)
+        , m_tail(0)
+    {
+    }
+
+    template<typename T, typename U>
+    inline ListHashSet<T, U>::ListHashSet(const ListHashSet& other)
+        : m_head(0)
+        , m_tail(0)
+    {
+        const_iterator end = other.end();
+        for (const_iterator it = other.begin(); it != end; ++it)
+            add(*it);
+    }
+
+    template<typename T, typename U>
+    inline ListHashSet<T, U>& ListHashSet<T, U>::operator=(const ListHashSet& other)
+    {
+        ListHashSet tmp(other);
+        m_impl.swap(tmp.m_impl); 
+        return *this;
+    }
+
+    template<typename T, typename U>
+    inline ListHashSet<T, U>::~ListHashSet()
+    {
+        deleteAllNodes();
+    }
+
+    template<typename T, typename U>
+    inline int ListHashSet<T, U>::size() const
+    {
+        return m_impl.size(); 
+    }
+
+    template<typename T, typename U>
+    inline int ListHashSet<T, U>::capacity() const
+    {
+        return m_impl.capacity(); 
+    }
+
+    template<typename T, typename U>
+    inline bool ListHashSet<T, U>::isEmpty() const
+    {
+        return m_impl.isEmpty(); 
+    }
+
+    template<typename T, typename U>
+    inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::begin()
+    {
+        return makeIterator(m_head); 
+    }
+
+    template<typename T, typename U>
+    inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::end()
+    {
+        return makeIterator(0);
+    }
+
+    template<typename T, typename U>
+    inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::begin() const
+    {
+        return makeConstIterator(m_head); 
+    }
+
+    template<typename T, typename U>
+    inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::end() const
+    {
+        return makeConstIterator(0); 
+    }
+
+    template<typename T, typename U>
+    inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::find(const ValueType& value)
+    {
+        typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
+        typename ImplType::iterator it = m_impl.template find<ValueType, Translator>(value);
+        if (it == m_impl.end())
+            return end();
+
+        return makeIterator(*it); 
+    }
+
+    template<typename T, typename U>
+    inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::find(const ValueType& value) const
+    {
+        typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
+        typename ImplType::const_iterator it = m_impl.template find<ValueType, Translator>(value);
+        if (it == m_impl.end())
+            return end();
+        return makeConstIterator(*(m_impl.template find<ValueType, Translator>(value))); 
+    }
+
+    template<typename T, typename U>
+    inline bool ListHashSet<T, U>::contains(const ValueType& value) const
+    {
+        typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
+        return m_impl.template contains<ValueType, Translator>(value);
+    }
+
+    template<typename T, typename U>
+    pair<typename ListHashSet<T, U>::iterator, bool> ListHashSet<T, U>::add(const ValueType &value)
+    {
+        typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
+        pair<typename ImplType::iterator, bool> result =  m_impl.template add<ValueType, ValueType, Translator>(value, value);
+        if (result.second)
+            appendNode(*(result.first));
+
+        return std::make_pair(makeIterator(*(result.first)), result.second);
+    }
+
+    template<typename T, typename U>
+    inline void ListHashSet<T, U>::remove(iterator it)
+    {
+        if (it == end())
+            return;
+
+        unlinkAndDelete(it.node());
+        m_impl.remove(it.node());
+    }
+
+    template<typename T, typename U>
+    inline void ListHashSet<T, U>::remove(const ValueType& value)
+    {
+        remove(find(value));
+    }
+
+    template<typename T, typename U>
+    inline void ListHashSet<T, U>::clear()
+    {
+        deleteAllNodes();
+        m_impl.clear(); 
+        m_head = 0;
+        m_tail = 0;
+    }
+
+    template<typename T, typename U>
+    void ListHashSet<T, U>::unlinkAndDelete(Node* node)
+    {
+        if (!node->m_prev) {
+            ASSERT(node == m_head);
+            m_head = node->m_next;
+        } else {
+            ASSERT(node != m_head);
+            node->m_prev->m_next = node->m_next;
+        }
+
+        if (!node->m_next) {
+            ASSERT(node == m_tail);
+            m_tail = node->m_prev;
+        } else {
+            ASSERT(node != m_tail);
+            node->m_next->m_prev = node->m_prev;
+        }
+
+        delete node;
+    }
+
+    template<typename T, typename U>
+    void ListHashSet<T, U>::appendNode(Node* node)
+    {
+        node->m_prev = m_tail;
+        node->m_next = 0;
+
+        if (m_tail) {
+            ASSERT(m_head);
+            m_tail->m_next = node;
+        } else {
+            ASSERT(!m_head);
+            m_head = node;
+        }
+
+        m_tail = node;
+    }
+
+    template<typename T, typename U>
+    void ListHashSet<T, U>::deleteAllNodes()
+    {
+        if (!m_head)
+            return;
+
+        for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)
+            delete node;
+    }
+
+    template<typename T, typename U>
+    inline ListHashSetIterator<T, U> ListHashSet<T, U>::makeIterator(Node* position) 
+    {
+        return ListHashSetIterator<T, U>(this, position); 
+    }
+
+    template<typename T, typename U>
+    inline ListHashSetConstIterator<T, U> ListHashSet<T, U>::makeConstIterator(Node* position) const
+    { 
+        return ListHashSetConstIterator<T, U>(this, position); 
+    }
+
+    template<bool, typename ValueType, typename HashTableType>
+    void deleteAllValues(HashTableType& collection)
+    {
+        typedef typename HashTableType::const_iterator iterator;
+        iterator end = collection.end();
+        for (iterator it = collection.begin(); it != end; ++it)
+            delete (*it)->m_value;
+    }
+
+    template<typename T, typename U>
+    inline void deleteAllValues(const ListHashSet<T, U>& collection)
+    {
+        deleteAllValues<true, typename ListHashSet<T, U>::ValueType>(collection.m_impl);
+    }
+
+} // namespace WTF
+
+using WTF::ListHashSet;
+
+#endif /* WTF_ListHashSet_h */
index 29423055af521ecfd2567ed4bc2f162b2df491b0..fe4d0e3dba04a2e19328ebef6e0cb4b8264bb681 100644 (file)
@@ -1,3 +1,21 @@
+2007-01-31  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Mark.
+
+        - fixed <rdar://problem/4751164> REGRESSION: Safari places text on incorrect button when returning to a page via back [10541]
+        http://bugs.webkit.org/show_bug.cgi?id=10541
+
+        * dom/Document.cpp:
+        (WebCore::Document::formElementsState):
+        * dom/Document.h:
+        
+        I couldn't figure out the back/forward support in the tests enough
+        to make an automated test, but this maual test reproduces the
+        problem 100% without this patch:
+        
+        * manual-tests/back.html: Added.
+        * manual-tests/form-control-madness.html: Added.
+
 2007-01-31  David Kilzer  <ddkilzer@kilzer.net>
 
         Reviewed by Mitz.
index 8c959e5026240d5ea3c8ea73d51b151ebe2e5468..6794df80a9080f93d2be56d063ba863ace4be16f 100644 (file)
@@ -3291,7 +3291,7 @@ Vector<String> Document::formElementsState() const
 {
     Vector<String> stateVector;
     stateVector.reserveCapacity(m_formElementsWithState.size() * 3);
-    typedef HashSet<HTMLGenericFormElement*>::const_iterator Iterator;
+    typedef ListHashSet<HTMLGenericFormElement*>::const_iterator Iterator;
     Iterator end = m_formElementsWithState.end();
     for (Iterator it = m_formElementsWithState.begin(); it != end; ++it) {
         HTMLGenericFormElement* e = *it;
index a2ef21e91aed94bfef66126d0eba0574feb0d693..6ae80bb9ad410c18372df6e5870cf85768da4543 100644 (file)
@@ -36,6 +36,7 @@
 #include "StringHash.h"
 #include "Timer.h"
 #include <wtf/HashCountedSet.h>
+#include <wtf/ListHashSet.h>
 
 namespace WebCore {
 
@@ -673,7 +674,7 @@ protected:
     RegisteredEventListenerList m_windowEventListeners;
 
     typedef HashMap<FormElementKey, Vector<String>, FormElementKeyHash, FormElementKeyHashTraits> FormElementStateMap;
-    HashSet<HTMLGenericFormElement*> m_formElementsWithState;
+    ListHashSet<HTMLGenericFormElement*> m_formElementsWithState;
     FormElementStateMap m_stateForNewFormElements;
 
     Color m_linkColor;
diff --git a/WebCore/manual-tests/back.html b/WebCore/manual-tests/back.html
new file mode 100644 (file)
index 0000000..4eea5df
--- /dev/null
@@ -0,0 +1 @@
+<input type="button" onclick="history.back()" value="Go Back">
\ No newline at end of file
diff --git a/WebCore/manual-tests/form-control-madness.html b/WebCore/manual-tests/form-control-madness.html
new file mode 100644 (file)
index 0000000..30dac2b
--- /dev/null
@@ -0,0 +1,46 @@
+<input name="b" type="button" onclick="location='back.html'" value="Click Here">
+
+<br>
+Only the radio buttons between X's should be checked after clicking the button and going back
+<form>
+<input type="radio" name="old_version" value="12"> 
+<input type="radio" name="version" value="12">
+
+X<input type="radio" name="old_version" value="11"  checked="checked"> X
+<input type="radio" name="version" value="11">
+
+<input type="radio" name="old_version" value="10"> 
+X<input type="radio" name="version" value="10" checked="checked">X
+
+<input type="radio" name="old_version" value="9"> 
+<input type="radio" name="version" value="9">
+
+<input type="radio" name="old_version" value="8"> 
+<input type="radio" name="version" value="8">
+
+<input type="radio" name="old_version" value="7"> 
+<input type="radio" name="version" value="7">
+
+<input type="radio" name="old_version" value="6"> 
+<input type="radio" name="version" value="6">
+
+<input type="radio" name="old_version" value="5"> 
+<input type="radio" name="version" value="5">
+
+<input type="radio" name="old_version" value="4"> 
+<input type="radio" name="version" value="4">
+
+<input type="radio" name="old_version" value="3"> 
+<input type="radio" name="version" value="3">
+
+<input type="radio" name="old_version" value="2"> 
+<input type="radio" name="version" value="2">
+
+<input type="radio" name="old_version" value="1"> 
+<input type="radio" name="version" value="1">
+
+<input type="radio" name="old_version" value="0"> 
+<input type="radio" name="version" value="0">
+</form>
+<br>
+<iframe></iframe>
\ No newline at end of file