Extending the NthIndexCache to support caching for the type of index.

Extending the NthIndexCache to support caching for the type
of index.

we have a cache for :nth-child/:nth-last-child indices
called NthIndexCache but for :nth-of-type/:nth-last-of-type
we always count siblings. So implementing cache for latter.

BUG=475720
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=195034

[a.berwal, 2015-04-20 12:06:30]

a.berwal@samsung.com changed reviewers:
+ esprehn@chromium.org;

[a.berwal, 2015-04-20 12:09:04]

a.berwal@samsung.com changed reviewers:
+ esprehn@chromium.org, rune@opera.com
- esprehn@chromium.org;

[rune, 2015-04-20 12:30:55]

You are using the same cache entries for :nth-child and :nth-of-type. That's not
going to work when you're trying to match :nth-child and :nth-of-type for
children of the same parent.

[a.berwal, 2015-04-21 10:35:07]

On 2015/04/20 12:30:55, rune wrote:

Have mode some changes. PTAL.

[rune, 2015-04-21 11:23:57]

On 2015/04/21 10:35:07, a.berwal wrote:
> On 2015/04/20 12:30:55, rune wrote:
> 
> Have mode some changes. PTAL.

This only works for trying to match a single type.

You need to sit down and make a design for how this is going to work, and come
up with something that doesn't explode in your face memory-wise either.

[a.berwal, 2015-04-28 03:11:14]

@rune, PTAL.

[rune, 2015-04-28 09:02:05]

You need to add some tests. In particular combinations of :nth-of-type and
:nth-child for the same set of siblings. With a mix of sibling types.

I'm wondering if we could use a single hash-map instead, where you store a pair
of indices, one for nth-child and one for nth-of-type. Then keep a hashmap of
<type, count> to check if you need to populate the cache for a given type. If
you have added an entry for nth-child, for instance, you just need to set the
type index instead of creating a new entry when populating for nth-of-type.

[a.berwal, 2015-04-29 03:55:31]

I have uploaded a new image on BUG=475720.Are you saying the same?

[esprehn, 2015-04-30 04:55:05]

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
File Source/core/dom/NthIndexCache.cpp (right):

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
Source/core/dom/NthIndexCache.cpp:38:
NthIndexCache::ElementTagNameAndNthIndexMap&
NthIndexCache::ensureElementTagNameAndNthIndexMapForType(Node& parent)
ensureTypeIndexMap(parent).

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
Source/core/dom/NthIndexCache.cpp:72: unsigned
NthIndexCache::NthIndexData::cacheNthIndicesOfType(Element& element, const
QualifiedName& type)
We should make NthIndexData not a nested class.

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
Source/core/dom/NthIndexCache.cpp:74: unsigned index = 0;
This and the other method should both ASSERT(m_elementIndexMap.isEmpty())

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
Source/core/dom/NthIndexCache.cpp:96: auto it =
m_elementTagNameAndNthIndexMap.find(element.tagName());
You should not call find() and then add(), always call add() and then check
isNewEntry. You're doing the hash lookup twice here and also have duplicate
code.

This should call the ensureTypeMap internally.

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
Source/core/dom/NthIndexCache.cpp:98: return *(it->value);
Delete this.

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
Source/core/dom/NthIndexCache.cpp:99: ElementTagNameAndNthIndexMap::AddResult
addResult = m_elementTagNameAndNthIndexMap.add(element.tagName(), nullptr);
m_indexByType, you don't need these verbose names.

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
File Source/core/dom/NthIndexCache.h (right):

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
Source/core/dom/NthIndexCache.h:52: class HasTagName {
This already exists elsewhere in the code. Just use that? Also I don't think all
this needs to be inline. We should move all the methods to be out of line in a
separate patch.

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
Source/core/dom/NthIndexCache.h:96: if (!m_count)
This will need the same pseudo element fix from rune@ other patch.

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
Source/core/dom/NthIndexCache.h:128: return
nthIndexDataWithTagName(ensureElementTagNameAndNthIndexMapForType(*element.parentNode()),
element).nthIndexOfType(element, type);
nthIndexDataWithTagName should call ensureElementTagNameAndNthIndexMapForType
internally.

https://codereview.chromium.org/1096813005/diff/40001/Source/core/dom/NthInde...
Source/core/dom/NthIndexCache.h:140: return
nthIndexDataWithTagName(ensureElementTagNameAndNthIndexMapForType(*element.parentNode()),
element).nthLastIndexOfType(element, type);
ditto

[a.berwal, 2015-04-30 09:36:22]

@esprehn Incorporated the changes.PTAL

[rune, 2015-04-30 10:04:29]

My idea was to store a pair of indices <nth-index, nth-of-type-index> in the
hash map instead, and have a hash map for <type, count> to avoid creating n
hash-maps if you try to match nth-of-type for n different types of elements in
the same set of siblings, to save memory. I guess we can refine that later.

As mentioned earlier, you still need to write some tests.

[a.berwal, 2015-05-04 07:12:46]

Added Layout Test. PTAL

[rune, 2015-05-04 08:32:49]

https://chromiumcodereview.appspot.com/1096813005/diff/100001/LayoutTests/fas...
File LayoutTests/fast/css/nth-child-and-nth-type-child-expected.html (right):

https://chromiumcodereview.appspot.com/1096813005/diff/100001/LayoutTests/fas...
LayoutTests/fast/css/nth-child-and-nth-type-child-expected.html:3: <body>
Drop html and body.

https://chromiumcodereview.appspot.com/1096813005/diff/100001/LayoutTests/fas...
File LayoutTests/fast/css/nth-child-and-nth-type-child.html (right):

https://chromiumcodereview.appspot.com/1096813005/diff/100001/LayoutTests/fas...
LayoutTests/fast/css/nth-child-and-nth-type-child.html:3: <head>
Drop html, head, and body tags.

https://chromiumcodereview.appspot.com/1096813005/diff/100001/Source/core/dom...
File Source/core/dom/NthIndexCache.cpp (right):

https://chromiumcodereview.appspot.com/1096813005/diff/100001/Source/core/dom...
Source/core/dom/NthIndexCache.cpp:83: // elements will be traversed.
This isn't entirely correct as you're storing every third element of a given
type. You should modify the description to make that clearer.

Note that that number of elements you need to traverse for a lookup is less
predictable than for nth-index since the distribution of elements of a given
type can be sparse, but we can use the spread like this for now.

[a.berwal, 2015-05-04 09:21:43]

Incorporated the Review Comments.
PTAL

[rune, 2015-05-04 09:25:48]

lgtm, but I think there are outstanding issues from esprehn, like making
NthIndexData not a nested class.

[a.berwal, 2015-05-04 09:28:15]

On 2015/05/04 09:25:48, rune wrote:
> lgtm, but I think there are outstanding issues from esprehn, like making
> NthIndexData not a nested class.

For that I will upload a separate patch as esprehn also mentioned to put that in
separate patch.

[rune, 2015-05-04 09:29:37]

On 2015/05/04 09:28:15, a.berwal wrote:
> On 2015/05/04 09:25:48, rune wrote:
> > lgtm, but I think there are outstanding issues from esprehn, like making
> > NthIndexData not a nested class.
> 
> For that I will upload a separate patch as esprehn also mentioned to put that
in
> separate patch.

ok

[a.berwal, 2015-05-04 09:54:58]

esprehn@ PTAL.

[a.berwal, 2015-05-07 03:14:30]

The CQ bit was checked by a.berwal@samsung.com

[commit-bot: I haz the power, 2015-05-07 03:15:42]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1096813005/120001

[esprehn, 2015-05-07 04:16:11]

lgtm, please fix the variable name before committing.

I think we might want to reconsider this to fill the cache for all types in a
single pass eventually so instead of this we'd walk the list and count all
QualifiedNames at the same time (and respecting the spread). We can start here
though.

https://codereview.chromium.org/1096813005/diff/120001/Source/core/dom/NthInd...
File Source/core/dom/NthIndexCache.h (right):

https://codereview.chromium.org/1096813005/diff/120001/Source/core/dom/NthInd...
Source/core/dom/NthIndexCache.h:64: OwnPtrWillBeMember<IndexByType>
m_IndexByType;
m_indexByType, lower case

[esprehn, 2015-05-07 04:16:15]

The CQ bit was unchecked by esprehn@chromium.org

[a.berwal, 2015-05-07 04:19:34]

The CQ bit was unchecked by a.berwal@samsung.com

[a.berwal, 2015-05-07 05:20:48]

The CQ bit was checked by a.berwal@samsung.com

[a.berwal, 2015-05-07 05:20:49]

The patchset sent to the CQ was uploaded after l-g-t-m from
esprehn@chromium.org, rune@opera.com
Link to the patchset:
https://chromiumcodereview.appspot.com/1096813005/#ps140001 (title: "Fixing
nit")

[commit-bot: I haz the power, 2015-05-07 05:21:03]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1096813005/140001

[commit-bot: I haz the power, 2015-05-07 06:53:24]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-05-07 06:53:26]

Failed to apply patch for Source/core/css/SiblingTraversalStrategies.h:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  patching file Source/core/css/SiblingTraversalStrategies.h
  Hunk #1 FAILED at 48.
  Hunk #2 succeeded at 93 with fuzz 2.
  Hunk #3 succeeded at 114 with fuzz 2.
  1 out of 3 hunks FAILED -- saving rejects to file
Source/core/css/SiblingTraversalStrategies.h.rej

Patch:       Source/core/css/SiblingTraversalStrategies.h
Index: Source/core/css/SiblingTraversalStrategies.h
diff --git a/Source/core/css/SiblingTraversalStrategies.h
b/Source/core/css/SiblingTraversalStrategies.h
index
1e008dba5fda36e1c053fe4b5b43ba61e10e51af..5f1e0176bce981354f8fd4fefe37fd469553b1ba
100644
--- a/Source/core/css/SiblingTraversalStrategies.h
+++ b/Source/core/css/SiblingTraversalStrategies.h
@@ -48,15 +48,6 @@ public:
     int countElementsAfter(Element&) const;
     int countElementsOfTypeBefore(Element&, const QualifiedName&) const;
     int countElementsOfTypeAfter(Element&, const QualifiedName&) const;
-
-private:
-    class HasTagName {
-    public:
-        explicit HasTagName(const QualifiedName& tagName) : m_tagName(tagName)
{ }
-        bool operator() (const Element& element) const { return
element.hasTagName(m_tagName); }
-    private:
-        const QualifiedName& m_tagName;
-    };
 };
 
 inline bool DOMSiblingTraversalStrategy::isFirstChild(Element& element) const
@@ -93,6 +84,8 @@ inline int
DOMSiblingTraversalStrategy::countElementsBefore(Element& element) co
 
 inline int DOMSiblingTraversalStrategy::countElementsOfTypeBefore(Element&
element, const QualifiedName& type) const
 {
+    if (NthIndexCache* nthIndexCache = element.document().nthIndexCache())
+        return nthIndexCache->nthChildIndexOfType(element, type) - 1;
     int count = 0;
     for (const Element* sibling = ElementTraversal::previousSibling(element,
HasTagName(type)); sibling; sibling =
ElementTraversal::previousSibling(*sibling, HasTagName(type)))
         ++count;
@@ -112,6 +105,9 @@ inline int
DOMSiblingTraversalStrategy::countElementsAfter(Element& element) con
 
 inline int DOMSiblingTraversalStrategy::countElementsOfTypeAfter(Element&
element, const QualifiedName& type) const
 {
+    if (NthIndexCache* nthIndexCache = element.document().nthIndexCache())
+        return nthIndexCache->nthLastChildIndexOfType(element, type) - 1;
+
     int count = 0;
     for (const Element* sibling = ElementTraversal::nextSibling(element,
HasTagName(type)); sibling; sibling = ElementTraversal::nextSibling(*sibling,
HasTagName(type)))
         ++count;

[commit-bot: I haz the power, 2015-05-07 06:53:31]

The CQ bit was unchecked by commit-bot@chromium.org

[a.berwal, 2015-05-07 07:14:14]

The CQ bit was unchecked by a.berwal@samsung.com

[a.berwal, 2015-05-07 07:14:26]

The CQ bit was checked by a.berwal@samsung.com

[a.berwal, 2015-05-07 07:14:27]

The patchset sent to the CQ was uploaded after l-g-t-m from
esprehn@chromium.org, rune@opera.com
Link to the patchset:
https://chromiumcodereview.appspot.com/1096813005/#ps160001 (title: "Rebasing")

[commit-bot: I haz the power, 2015-05-07 07:14:33]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1096813005/160001

[commit-bot: I haz the power, 2015-05-07 08:38:37]

Committed patchset #9 (id:160001) as
https://src.chromium.org/viewvc/blink?view=rev&revision=195034