Issue 235 - Improved performance of ElemHide.getSelectorsForDomain()

lib/elemHide.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-2015 Eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ skipping 41 matching lines @@
  */
 let exceptions = Object.create(null);
 
 /**
  * Currently applied stylesheet URL
  * @type nsIURI
  */
 let styleURL = null;
 
 /**
- * Lookup table, blocking filters by domain which they are applied to
+ * Lookup table, filter selectors by domain which they are applied to
  * @type Object
  */
-let filtersByDomain = Object.create(null);
+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
@@ skipping 34 matching lines @@
 
   /**
    * Removes all known filters
    */
   clear: function()
   {
     filterByKey = Object.create(null);
     keyByFilter = Object.create(null);
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
-    filtersByDomain = Object.create(null);
+    selectorsByDomain = Object.create(null);
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
   add: function(filter)
   {
@@ skipping 17 matching lines @@
       {
         let domains = filter.domains;
         if (domains === null)
         {
           domains = Object.create(null);
           domains[""] = true;
         }
 
         for (let domain in domains)
         {
-          if (!(domain in filtersByDomain))
+          if (!(domain in selectorsByDomain))
           {
-            filtersByDomain[domain] = Object.create(null);
-            filtersByDomain[domain].$length = 0;
+            selectorsByDomain[domain] = Object.create(null);
+            selectorsByDomain[domain].$length = 0;
           }
 
-          filtersByDomain[domain][filter.text] = domains[domain];
-          filtersByDomain[domain].$length++;
+          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);
       } while (key in filterByKey);
 
       filterByKey[key] = filter;
       keyByFilter[filter.text] = key;
@@ skipping 27 matching lines @@
       {
         let domains = filter.domains;
         if (!domains)
         {
           domains = Object.create(null);
           domains[""] = true;
         }
 
         for (let domain in domains)
         {
-          if (domain in filtersByDomain && filter.text in filtersByDomain[domain])
+          if (domain in selectorsByDomain
+            && filter.selector in selectorsByDomain[domain]
+            && !--selectorsByDomain[domain][filter.selector].$length)
           {
-            delete filtersByDomain[domain][filter.text];
-            if (!--filtersByDomain[domain].$length)
-              delete filtersByDomain[domain];
+            delete selectorsByDomain[domain][filter.selector];
+            if (!--selectorsByDomain[domain].$length)
+              delete selectorsByDomain[domain];
           }
         }
       }
 
       let key = keyByFilter[filter.text];
       delete filterByKey[key];
       delete keyByFilter[filter.text];
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
    */
-  getException: function(/**Filter*/ filter, /**String*/ docDomain) /**ElemHideException*/
-  {
-    if (!(filter.selector in exceptions))
+  getException: function(/**String*/ selector, /**String*/ docDomain) /**ElemHideException*/
+  {
+    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];
 
     return null;
   },
 
   /**
    * Will be set to true if apply() is running (reentrance protection).
    * @type Boolean
@@ skipping 81 matching lines @@
           }
         }
 
         FilterNotifier.triggerListeners("elemhideupdate");
       }
     }.bind(this));
 
     this._applying = true;
   },
 
-  _generateCSSContent: function()
+  _generateCSSContent: function*()
   {
     // Grouping selectors by domains
     let domains = Object.create(null);
     let hasFilters = false;
     for (let key in filterByKey)
     {
       let filter = filterByKey[key];
       let domain = filter.selectorDomain || "";
 
       let list;
@@ skipping 72 matching lines @@
    */
   getFilterByKey: function(/**String*/ key) /**Filter*/
   {
     return (key in filterByKey ? filterByKey[key] : null);
   },
 
   /**
    * 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)
   {
     if (canUseStylesheets)
       throw new Error("Use of getSelectorsForDomain is limited to platforms which cannot inject stylesheets");
 
-    let selectors = [];
-    domain = domain.toUpperCase();
-
-    if (!specificOnly)
-    {
-      let filterTexts = filtersByDomain[""];
-      if (filterTexts)
-      {
-        for (let filterText in filterTexts)
-        {
-          if (filterTexts[filterText] && filterText != "$length")
-          {
-            let filter = Filter.fromText(filterText);
-            if (!this.getException(filter, domain))
-              selectors[selectors.length] = filter.selector;
-          }
-        }
-      }
-    }

[Wladimir Palant, 2015/06/05 21:58:54]

This block duplicates the logic below unnecessarily. It also happens to produce
wrong results. For example, ~example.com##foo should be active on every domain
but example.com. However, with domain being foo.example.com your code will
currently add it to the selectors in the block above and ignore the exception
completely.

"" should really be handled in the loop below along with other "domains":

while (true)
{
  if (domain in filtersByDomain && (domain != "" || !specificOnly))
  ...

  if (domain == "")
    break;

  let nextDot = domain.indexOf(".");
  domain = domain.substr(nextDot + 1);
}

[Thomas Greiner, 2015/06/23 13:28:40]

Done.

-
-    let ignorableFilters = [];

[Wladimir Palant, 2015/06/05 21:58:54]

Use an object here rather than an array, given that you need to do frequent
lookups?

Also, it's ignoredFilters I think.

[Thomas Greiner, 2015/06/23 13:28:40]

Done.

+    let selectors = Object.create(null);
+    let domain = docDomain.toUpperCase();
     while (true)
     {
-      if (domain && domain in filtersByDomain)
-      {
-        let filterTexts = filtersByDomain[domain];
-        for (let filterText in filterTexts)
-        {
-          if (ignorableFilters.indexOf(filterText) > -1)

[Wladimir Palant, 2015/06/05 21:58:54]

How about checking for $length immediately?

if (filterText == "$length" || filterText in ignoredFilters)
  continue;

[Thomas Greiner, 2015/06/23 13:28:40]

Done.

+      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 (filterTexts[filterText])
-          {
-            if (filterText == "$length")
-              continue;
-
-            let filter = Filter.fromText(filterText);
-            if (!this.getException(filter, domain))

[Wladimir Palant, 2015/06/05 21:58:54]

Calling Filter.fromText() here looks like unnecessary overhead - you don't
really need the full filter. How about storing the selectors in the data rather
than the complete filter text? ElemHide.getException() can be changed to accept
selectors rather than filters, that's what it needs anyway. The only other
caller of ElemHide.getException() is contentPolicy.js and easily changed.

The only problem: multiple filters could use the same selector for the same
domain (consider foo.example.com##foo and bar.example.org,foo.example.com##foo),
meaning that your current approach to remove filters from the data will no
longer work. We need to store the count for each selector rather than for
domains.

[Thomas Greiner, 2015/06/23 13:28:40]

Done. That's an awesome tip, thanks!

Note that the `#foo` selector is currently being returned twice when using the
two filters you mentioned. This no longer occurs with these changes.

-              selectors[selectors.length] = filter.selector;

[Wladimir Palant, 2015/06/05 21:58:54]

selectors.push() please.

Either way, I think this might add the same selector multiple times. Consider
foo.example.com,example.com##foo on foo.example.com.

[Thomas Greiner, 2015/06/23 13:28:40]

Done.
Done. Unfortunately, `Array.indexOf()` is terribly slow to check this so I chose
to use the `ignoredSelectors` object for this.

-          }
-          else
-            ignorableFilters[ignorableFilters.length] = filterText;
-        }
-      }
+
+          selectors[filterSelector] = null;
+        }
+      }
+
+      if (domain == "")
+        break;
 
       let nextDot = domain.indexOf(".");
-      if (nextDot < 0)
-        break;
-      domain = domain.substr(nextDot + 1);
-    }
-
-    return selectors;
+      domain = (nextDot < 0) ? "" : domain.substr(nextDot + 1);
+    }
+
+    return Object.getOwnPropertyNames(selectors);
   }
 };