Issue 235 - Improved performance of ElemHide.getSelectorsForDomain()

lib/elemHide.js

Index: lib/elemHide.js
===================================================================
--- a/lib/elemHide.js
+++ b/lib/elemHide.js
@@ -59,6 +59,18 @@
 let styleURL = null;
 
 /**
+ * Lookup table, filter selectors by domain which they are applied to
+ * @type Object
+ */
+let selectorsByDomain = Object.create(null);
+
+/**
+ * Indicates whether stylesheets can be used for element hiding
+ * @type Boolean
+ */
+let canUseStylesheets = ("nsIStyleSheetService" in Ci);
+
+/**
  * Element hiding component
  * @class
  */
@@ -105,6 +117,7 @@
     keyByFilter = Object.create(null);
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
+    selectorsByDomain = Object.create(null);
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
@@ -131,6 +144,38 @@
       if (filter.text in keyByFilter)
         return;
 
+      if (!canUseStylesheets)
+      {
+        let domains = filter.domains;
+        if (domains === null)
+        {
+          domains = Object.create(null);
+          domains[""] = true;
+        }
+
+        for (let domain in domains)
+        {
+          if (!(domain in selectorsByDomain))
+          {
+            selectorsByDomain[domain] = Object.create(null);
+            selectorsByDomain[domain].$length = 0;
+          }
+
+          let selectors = selectorsByDomain[domain];
+          if (!(filter.selector in selectors))
+          {
+            selectors[filter.selector] = {
+              isActive: false,
+              count: 0
+            };
+          }
+          selectors[filter.selector].isActive |= domains[domain];
+          selectors[filter.selector].count++;
+
+          selectors.$length++;
+        }
+      }
+
       let key;
       do {
         key = Math.random().toFixed(15).substr(5);
@@ -164,6 +209,28 @@
       if (!(filter.text in keyByFilter))
         return;
 
+      if (!canUseStylesheets)
+      {
+        let domains = filter.domains;
+        if (!domains)
+        {
+          domains = Object.create(null);
+          domains[""] = true;
+        }
+
+        for (let domain in domains)
+        {
+          if (domain in selectorsByDomain
+            && filter.selector in selectorsByDomain[domain]
+            && !--selectorsByDomain[domain][filter.selector].$length)
+          {
+            delete selectorsByDomain[domain][filter.selector];
+            if (!--selectorsByDomain[domain].$length)
+              delete selectorsByDomain[domain];
+          }
+        }
+      }
+
       let key = keyByFilter[filter.text];
       delete filterByKey[key];
       delete keyByFilter[filter.text];
@@ -175,12 +242,12 @@
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
    */
-  getException: function(/**Filter*/ filter, /**String*/ docDomain) /**ElemHideException*/
+  getException: function(/**String*/ selector, /**String*/ docDomain) /**ElemHideException*/
   {
-    if (!(filter.selector in exceptions))
+    if (!(selector in exceptions))
       return null;
 
-    let list = exceptions[filter.selector];
+    let list = exceptions[selector];
     for (let i = list.length - 1; i >= 0; i--)
       if (list[i].isActiveOnDomain(docDomain))
         return list[i];
@@ -372,22 +439,41 @@
   },
 
   /**
-   * Returns a list of all selectors active on a particular domain (currently
-   * used only in Chrome, Opera and Safari).
+   * Returns a list of all selectors active on a particular domain (it cannot
+   * be used in Firefox).
    */
-  getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
+  getSelectorsForDomain: function(/**String*/ docDomain, /**Boolean*/ specificOnly)
   {
-    let result = [];
-    let keys = Object.getOwnPropertyNames(filterByKey);
-    for (let key of keys)
+    if (canUseStylesheets)
+      throw new Error("Use of getSelectorsForDomain is limited to platforms which cannot inject stylesheets");
+
+    let selectors = Object.create(null);
+    let domain = docDomain.toUpperCase();
+    while (true)
     {
-      let filter = filterByKey[key];
-      if (specificOnly && (!filter.domains || filter.domains[""]))
-        continue;
+      if (domain in selectorsByDomain && (domain != "" || !specificOnly))
+      {
+        let domainSelectors = selectorsByDomain[domain];
+        let filterSelectors = Object.getOwnPropertyNames(domainSelectors);
+        for (let filterSelector of filterSelectors)
+        {
+          if (filterSelector == "$length"
+            || filterSelector in selectors
+            || !domainSelectors[filterSelector].isActive
+            || this.getException(filterSelector, docDomain))
+            continue;

[Wladimir Palant, 2015/07/30 11:26:53]

Even with the inconsistent logic changes you are implementing, this is still
wrong. !domainSelectors[filterSelector].isActive shouldn't mean "oh well, maybe
some other domain is allowed" - it's really "oops, should not apply, stop now."
Meaning that ~foo.example.com,example.com##foo really shouldn't apply on
foo.example.com even if that filter is allowed on example.com. Same goes for
exceptions, if we have foo.example.com#@#foo then example.com##foo should *not*
apply on foo.example.com.

I recommend adding unit tests for all the scenarios I mention in the review
comments. I feel like you are consistently forgetting to test the edge cases.

 
-      if (filter.isActiveOnDomain(domain) && !this.getException(filter, domain))
-        result.push(filter.selector);
+          selectors[filterSelector] = null;
+        }
+      }
+
+      if (domain == "")
+        break;
+
+      let nextDot = domain.indexOf(".");
+      domain = (nextDot < 0) ? "" : domain.substr(nextDot + 1);
     }
-    return result;
+
+    return Object.getOwnPropertyNames(selectors);
   }
 };