dom, match: optimize :nth-child, :nth-last-child

I want to use it in the UA sheet, so the loop won't cut it.

(Also fix a parsing bug that prevented "of" from working.)

3 files changed, 75 insertions, 41 deletions

diff --git a/src/css/match.nim b/src/css/match.nim
index 9cdf23c4..382d6312 100644
--- a/src/css/match.nim
+++ b/src/css/match.nim
@@ -89,45 +89,54 @@ func pseudoSelectorMatches(element: Element; sel: Selector;
     return element.hover
   of pcRoot: return element == element.document.documentElement
   of pcNthChild:
-    if sel.pseudo.ofsels.len != 0 and
-        not element.selectorsMatch(sel.pseudo.ofsels, depends):
-      return false
     let A = sel.pseudo.anb.A # step
     let B = sel.pseudo.anb.B # start
-    var i = 1
-    let parent = element.parentNode
-    if parent == nil: return false
-    for child in parent.elementList:
-      if child == element:
-        if A == 0:
-          return i == B
-        if A < 0:
-          return (i - B) <= 0 and (i - B) mod A == 0
-        return (i - B) >= 0 and (i - B) mod A == 0
-      if sel.pseudo.ofsels.len == 0 or
-          child.selectorsMatch(sel.pseudo.ofsels, depends):
-        inc i
+    if sel.pseudo.ofsels.len == 0:
+      let i = element.elIndex + 1
+      if A == 0:
+        return i == B
+      let j = (i - B)
+      if A < 0:
+        return j <= 0 and j mod A == 0
+      return j >= 0 and j mod A == 0
+    if element.selectorsMatch(sel.pseudo.ofsels, depends):
+      var i = 1
+      for child in element.parentNode.elementList:
+        if child == element:
+          if A == 0:
+            return i == B
+          let j = (i - B)
+          if A < 0:
+            return j <= 0 and j mod A == 0
+          return j >= 0 and j mod A == 0
+        if child.selectorsMatch(sel.pseudo.ofsels, depends):
+          inc i
     return false
   of pcNthLastChild:
-    if sel.pseudo.ofsels.len == 0 and
-        not element.selectorsMatch(sel.pseudo.ofsels, depends):
-      return false
     let A = sel.pseudo.anb.A # step
     let B = sel.pseudo.anb.B # start
-    var i = 1
-    let parent = element.parentNode
-    if parent == nil:
-      return false
-    for child in parent.elementList_rev:
-      if child == element:
-        if A == 0:
-          return i == B
-        if A < 0:
-          return (i - B) <= 0 and (i - B) mod A == 0
-        return (i - B) >= 0 and (i - B) mod A == 0
-      if sel.pseudo.ofsels.len != 0 or
-          child.selectorsMatch(sel.pseudo.ofsels, depends):
-        inc i
+    if sel.pseudo.ofsels.len == 0:
+      let last = element.parentNode.lastElementChild
+      let i = last.elIndex + 1 - element.elIndex
+      if A == 0:
+        return i == B
+      let j = (i - B)
+      if A < 0:
+        return j <= 0 and j mod A == 0
+      return j >= 0 and j mod A == 0
+    if element.selectorsMatch(sel.pseudo.ofsels, depends):
+      var i = 1
+      for child in element.parentNode.elementList_rev:
+        if child == element:
+          if A == 0:
+            return i == B
+          let j = (i - B)
+          if A < 0:
+            return j <= 0 and j mod A == 0
+          return j >= 0 and j mod A == 0
+        if sel.pseudo.ofsels.len == 0 or
+            child.selectorsMatch(sel.pseudo.ofsels, depends):
+          inc i
     return false
   of pcChecked:
     depends.add(element, dtChecked)
diff --git a/src/css/selectorparser.nim b/src/css/selectorparser.nim
index 33302068..4330bd18 100644
--- a/src/css/selectorparser.nim
+++ b/src/css/selectorparser.nim
@@ -304,6 +304,9 @@ proc parseNthChild(state: var SelectorParser; cssfunction: CSSFunction;
   let lasttok = get_tok cssfunction.value[i]
   if lasttok.t != cttIdent or not lasttok.value.equalsIgnoreCase("of"):
     fail
+  inc i
+  while i < cssfunction.value.len and cssfunction.value[i] == cttWhitespace:
+    inc i
   if i == cssfunction.value.len: fail
   nthchild.pseudo.ofsels = cssfunction.value[i..^1]
     .parseSelectorList(state.factory, nested = true, forgiving = false)
diff --git a/src/html/dom.nim b/src/html/dom.nim
index b8ab0787..3af310ee 100644
--- a/src/html/dom.nim
+++ b/src/html/dom.nim
@@ -250,6 +250,7 @@ type
     localName* {.jsget.}: CAtom
     id* {.jsget.}: CAtom
     name {.jsget.}: CAtom
+    elIndex*: int # like index, but for elements only.
     classList* {.jsget.}: DOMTokenList
     attrs*: seq[AttrData] # sorted by int(qualifiedName)
     cachedAttributes: NamedNodeMap
@@ -3103,6 +3104,7 @@ proc newHTMLElement*(document: Document; localName: CAtom;
   let localName = document.toAtom(satClassList)
   result.classList = DOMTokenList(element: result, localName: localName)
   result.index = -1
+  result.elIndex = -1
   result.dataset = DOMStringMap(target: result)
 
 proc newHTMLElement*(document: Document; tagType: TagType): HTMLElement =
@@ -3825,9 +3827,13 @@ proc remove*(node: Node; suppressObservers: bool) =
   assert node.index != -1
   #TODO live ranges
   #TODO NodeIterator
+  let element = if node of Element: Element(node) else: nil
   for i in node.index ..< parent.childList.len - 1:
-    parent.childList[i] = parent.childList[i + 1]
-    parent.childList[i].index = i
+    let it = parent.childList[i + 1]
+    it.index = i
+    if element != nil and it of Element:
+      dec Element(it).elIndex
+    parent.childList[i] = it
   parent.childList.setLen(parent.childList.len - 1)
   parent.invalidateCollections()
   node.invalidateCollections()
@@ -3835,10 +3841,11 @@ proc remove*(node: Node; suppressObservers: bool) =
     Element(parent).setInvalid()
   node.parentNode = nil
   node.index = -1
-  if node.document != nil and (node of HTMLStyleElement or
-      node of HTMLLinkElement):
-    node.document.cachedSheetsInvalid = true
-
+  if element != nil:
+    element.elIndex = -1
+    if element.document != nil and
+        (element of HTMLStyleElement or element of HTMLLinkElement):
+      element.document.cachedSheetsInvalid = true
   #TODO assigned, shadow root, shadow root again, custom nodes, registered
   # observers
   #TODO not suppress observers => queue tree mutation record
@@ -4022,13 +4029,28 @@ func preInsertionValidity*(parent, node, before: Node): Err[DOMException] =
 proc insertNode(parent, node, before: Node) =
   parent.document.adopt(node)
   parent.childList.setLen(parent.childList.len + 1)
+  let element = if node of Element: Element(node) else: nil
   if before == nil:
     node.index = parent.childList.high
   else:
     node.index = before.index
+    if element != nil and before of Element:
+      element.elIndex = Element(before).elIndex
     for i in countdown(parent.childList.high - 1, node.index):
-      parent.childList[i + 1] = parent.childList[i]
-      parent.childList[i + 1].index = i + 1
+      let it = parent.childList[i]
+      let j = i + 1
+      it.index = j
+      if element != nil and it of Element:
+        let it = Element(it)
+        if element.elIndex == -1:
+          element.elIndex = it.elIndex
+        inc it.elIndex
+      parent.childList[j] = it
+  if element != nil and element.elIndex == -1:
+    element.elIndex = 0
+    let last = parent.lastElementChild
+    if last != nil:
+      element.elIndex = last.elIndex + 1
   parent.childList[node.index] = node
   node.parentNode = parent
   node.invalidateCollections()