Issue 235 - Speed up ElemHide.getSelectorsForDomain

lib/elemHide.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-2016 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 22 matching lines @@
  */
 var filterByKey = Object.create(null);
 
 /**
  * Lookup table, keys of the filters by filter text
  * @type Object
  */
 var keyByFilter = Object.create(null);
 
 /**
+ * Nested lookup table, filter (or false if inactive) by filter text by domain
+ * @type Object
+ */
+var filtersByDomain = Object.create(null);
+
+/**
+ * Indicates whether we are using (and maintaining) the filtersByDomain lookup.
+ * (Will be false for Firefox)
+ * @type Boolean
+ */
+var usingFiltersByDomain = !("nsIStyleSheetService" in Ci);
+
+/**
  * Lookup table, keys are known element hiding exceptions
  * @type Object
  */
 var knownExceptions = Object.create(null);
 
 /**
  * Lookup table, lists of element hiding exceptions by selector
  * @type Object
  */
 var exceptions = Object.create(null);
@@ skipping 10 matching lines @@
  */
 var ElemHide = exports.ElemHide =
 {
   /**
    * Indicates whether filters have been added or removed since the last apply() call.
    * @type Boolean
    */
   isDirty: false,
 
   /**
-   * Inidicates whether the element hiding stylesheet is currently applied.
+   * Indicates whether the element hiding stylesheet is currently applied.
    * @type Boolean
    */
   applied: false,
 
   /**
    * Called on module startup.
    */
   init: function()
   {
     Prefs.addListener(function(name)
     {
       if (name == "enabled")
         ElemHide.apply();
     });
     onShutdown.add(() => ElemHide.unapply());
 
     let styleFile = IO.resolveFilePath(Prefs.data_directory);
     styleFile.append("elemhide.css");
     styleURL = Services.io.newFileURI(styleFile).QueryInterface(Ci.nsIFileURL);
   },
 
   /**
    * Removes all known filters
    */
   clear: function()
   {
     filterByKey = Object.create(null);
     keyByFilter = Object.create(null);
+    filtersByDomain = Object.create(null);
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
@@ skipping 15 matching lines @@
       if (filter.text in keyByFilter)
         return;
 
       let key;
       do {
         key = Math.random().toFixed(15).substr(5);
       } while (key in filterByKey);
 
       filterByKey[key] = filter;
       keyByFilter[filter.text] = key;
+
+      if (usingFiltersByDomain)
+      {
+        let domainMatches = filter.domains || {"": true};
+        for (let domain in domainMatches)
+        {
+          domain = domain.toUpperCase();
+          if (!(domain in filtersByDomain))

[Sebastian Noack, 2016/05/17 09:47:49]

I think we should cache the lookup here:

  let filters = filtersByDomain[domain];
  if (!filters)
    filters = filtersByDomain[domain] = Object.create(null);
  filters[filter.text] = ...;

[kzar, 2016/05/17 10:05:45]

Done.

+            filtersByDomain[domain] = Object.create(null);
+          filtersByDomain[domain][filter.text] = domainMatches[domain] && filter;
+        }
+      }
+
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
    */
   remove: function(filter)
   {
@@ skipping 214 matching lines @@
 
   /**
    * Retrieves an element hiding filter by the corresponding protocol key
    */
   getFilterByKey: function(/**String*/ key) /**Filter*/
   {
     return (key in filterByKey ? filterByKey[key] : null);
   },
 
   /**
-   * 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, must not be
+   * used in Firefox (when usingFiltersByDomain is false).
    */
   getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
   {
-    let result = [];
-    let keys = Object.getOwnPropertyNames(filterByKey);
-    for (let key of keys)
+    if (!usingFiltersByDomain)
+      throw new Error("getSelectorsForDomain can not be used in Firefox!");
+
+    let selectors = [];
+
+    let seenFilters = Object.create(null);
+    let currentDomain = domain ? domain.toUpperCase() : "";
+    while (true)
     {
-      let filter = filterByKey[key];
-      if (specificOnly && (!filter.domains || filter.domains[""]))
-        continue;
+      if (specificOnly && currentDomain == "")
+        break;
 
-      if (filter.isActiveOnDomain(domain) && !this.getException(filter, domain))
-        result.push(filter.selector);
+      let filters = filtersByDomain[currentDomain];
+      if (filters)
+      {
+        for (let filterText in filters)
+        {
+          if (filterText in seenFilters)

[Sebastian Noack, 2016/05/17 09:47:49]

Is this some kind of micro optimization or an attempt to exclude duplicate
selectors? If it's supposed to be the latter, I think it makes more sense to
simply use an object for the resulting selectors and simply returning
Object.keys(selectors) below, as this will also remove duplicate selectors from
different filters. 

[kzar, 2016/05/17 10:05:45]

There's a comment in the old codereview about how this logic should work
https://codereview.adblockplus.org/4529242486341632/diff/29321269/lib/elemHid...

"~foo.example.com,example.com##foo really shouldn't apply on foo.example.com
even if that filter is allowed on example.com."

So let's say the domain given to getSelectorsForDomain is foo.example.com. The
matched filter is false for foo.example.com, meaning that the filter should not
be active. Now without the seenFilters logic we would continue to match the
filter example.com but this time it would be active. So the end result would be
that the filter would be applied to foo.example.com, which would be incorrect.

+            continue;
+          seenFilters[filterText] = true;
+
+          let filter = filters[filterText];
+          if (filter && !this.getException(filter, domain))

[Sebastian Noack, 2016/05/17 09:47:49]

I still have a hard time to understand how/whether filters like
~example.com##div are working. As far as I understand the logic here, you simply
ignore such filters, as the variable "filter" will be false for them here.

[kzar, 2016/05/17 10:05:45]

For ~example.com##div there should be two entries added to filtersByDomain.
filtersByDomain["example.com"]["~example.com##div"][false] and
filtersByDomain[""]["~example.com##div"]. The first has the value of false and
the second has of the filter itself. (Originally it was going to simply be true
but this way we avoid a second lookup to get the filter object.)

+            selectors.push(filter.selector);
+        }
+      }
+
+      if (currentDomain == "")
+        break;
+
+      let nextDot = currentDomain.indexOf(".");
+      currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
-    return result;
+
+    return selectors;
   }
 };