Cache element indices for :nth-child and :nth-last-child selectors.

Source/core/dom/NthIndexCache.h

Index: Source/core/dom/NthIndexCache.h
diff --git a/Source/core/dom/NthIndexCache.h b/Source/core/dom/NthIndexCache.h
new file mode 100644
index 0000000000000000000000000000000000000000..0ceee3ded03ea545fd44b0a295d3dfc9bf06f1b4
--- /dev/null
+++ b/Source/core/dom/NthIndexCache.h
@@ -0,0 +1,95 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef NthIndexCache_h
+#define NthIndexCache_h
+
+#include "core/dom/Element.h"
+#include "core/dom/ElementTraversal.h"
+#include "platform/heap/Handle.h"
+#include "wtf/HashMap.h"
+#include "wtf/OwnPtr.h"
+#include "wtf/RefPtr.h"
+
+namespace blink {
+
+class Document;
+
+class NthIndexCache final {
+    STACK_ALLOCATED();
+    WTF_MAKE_NONCOPYABLE(NthIndexCache);
+public:
+    NthIndexCache(Document&);

[esprehn, 2015/03/31 17:35:15]

explicit

[rune, 2015/03/31 20:57:37]

Done.

+    ~NthIndexCache();
+
+    static NthIndexCache* getInstance() { return s_instance; }

[sof, 2015/03/31 16:59:21]

nit: instance() (or current())

[esprehn, 2015/03/31 17:35:15]

instance()

[rune, 2015/03/31 20:57:37]

Done.

+
+    inline unsigned nthChildIndex(Element&);
+    inline unsigned nthLastChildIndex(Element&);
+
+private:
+    class NthIndexData final : public NoBaseWillBeGarbageCollected<NthIndexData> {
+        WTF_MAKE_NONCOPYABLE(NthIndexData);
+        DECLARE_EMPTY_DESTRUCTOR_WILL_BE_REMOVED(NthIndexData);
+    public:
+        NthIndexData() : m_count(0) { }

[esprehn, 2015/03/31 17:35:15]

I think you can actually do m_count = 0; below now and omit this constructor.

[rune, 2015/03/31 20:57:37]

Done. I had to keep the constructor since there's a copy one declared by
WTF_MAKE_NONCOPYABLE, so I don't know if it was worth it.

+
+        inline unsigned nthIndex(Element&);
+        inline unsigned nthLastIndex(Element&);
+
+        unsigned cacheNthIndices(Element&);
+
+        WillBeHeapHashMap<RawPtrWillBeMember<Element>, unsigned> m_elementIndexMap;
+        unsigned m_count;
+
+        DECLARE_TRACE();
+    };
+
+    NthIndexData& ensureNthIndexDataFor(Node&);
+    inline unsigned nthIndex(Element&);
+
+    using ParentMap = WillBeHeapHashMap<RefPtrWillBeMember<Node>, OwnPtrWillBeMember<NthIndexData>>;
+
+    OwnPtrWillBeMember<ParentMap> m_parentMap;
+    RawPtrWillBeMember<Document> m_document;
+    uint64_t m_domTreeVersion;
+
+    static NthIndexCache* s_instance;
+};
+
+inline unsigned NthIndexCache::NthIndexData::nthIndex(Element& element)
+{
+    if (!m_count)
+        return cacheNthIndices(element);
+
+    unsigned index = 0;
+    for (Element* sibling = &element; sibling; sibling = ElementTraversal::previousSibling(*sibling), index++) {
+        auto it = m_elementIndexMap.find(sibling);
+        if (it != m_elementIndexMap.end())
+            return it->value + index;
+    }
+    return index;
+}
+
+inline unsigned NthIndexCache::NthIndexData::nthLastIndex(Element& element)
+{
+    unsigned index = nthIndex(element);
+    return m_count - index + 1;
+}
+
+inline unsigned NthIndexCache::nthChildIndex(Element& element)
+{
+    ASSERT(element.parentNode());
+    return ensureNthIndexDataFor(*element.parentNode()).nthIndex(element);
+}
+
+inline unsigned NthIndexCache::nthLastChildIndex(Element& element)
+{
+    ASSERT(element.parentNode());
+    return ensureNthIndexDataFor(*element.parentNode()).nthLastIndex(element);
+}
+
+} // namespace blink
+
+#endif // NthIndexCache_h