Issue 4057 - Further speedup 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 13 matching lines @@
 var {Utils} = require("utils");
 var {IO} = require("io");
 var {Prefs} = require("prefs");
 var {ElemHideException} = require("filterClasses");
 var {FilterNotifier} = require("filterNotifier");
 
 /**
  * Lookup table, filters by their associated key
  * @type Object
  */
-var filterByKey = Object.create(null);
+var filterByKey = [];
 
 /**
  * Lookup table, keys of the filters by filter text
  * @type Object
  */
 var keyByFilter = Object.create(null);
 
 /**
- * Indicates whether we are using getSelectorsByDomain and maintaining the
- * required lookup tables. (Will be false for Firefox)
+ * Indicates whether we are using the getSelectorsForDomain function and
+ * therefore mainting the required filtersByDomain, filtersBySelector and
+ * unconditionalSelectors lookups. (Will be false for Firefox)
  * @type Boolean
  */
-var usingGetSelectorsByDomain = !("nsIStyleSheetService" in Ci);
-
-/**
- * Lookup table, filter selector by filter ID.
- */
-var selectorByFilterId = [];
-
-/**
- * Lookup table, active filter IDs by domain.
- */
-var activeFilterIdsByDomain = Object.create(null);
-
-/**
- * Lookup table, inactive filter IDs by domain.
- */
-var inactiveFilterIdsByDomain = Object.create(null);
-
-/**
- * Lookup table, filter ID by filter text.
- */
-var filterIdByFilterText = Object.create(null);
+var usingGetSelectorsForDomain = !("nsIStyleSheetService" in Ci);
+
+/**
+ * Nested lookup table, filter (or false if inactive) by filter key by domain.
+ * (Only contains filters that aren't unconditionally matched for all domains.)
+ * @type Object
+ */
+var filtersByDomain = Object.create(null);
+
+/**
+ * Lookup table, filters by selector. (Only contains filters that have a
+ * selector that is unconditionally matched for all domains.)
+ */
+var filtersBySelector = Object.create(null);
+
+/**
+ * This array caches the keys of filtersBySelector table (selectors which
+ * unconditionally apply on all domains). It will be null if the cache needs to
+ * be rebuilt.
+ */
+var unconditionalSelectors = null;
 
 /**
  * Object to be used instead when a filter has a blank domains property.
  */
 var defaultDomains = Object.create(null);
 defaultDomains[""] = true;
 
 /**
  * Lookup table, keys are known element hiding exceptions
  * @type Object
@@ skipping 45 matching lines @@
     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);
+    filterByKey = [];
     keyByFilter = Object.create(null);
-    selectorByFilterId = [];
-    activeFilterIdsByDomain = Object.create(null);
-    inactiveFilterIdsByDomain = Object.create(null);
-    filterIdByFilterText = Object.create(null);
+    filtersByDomain = Object.create(null);
+    filtersBySelector = Object.create(null);
+    unconditionalSelectors = null;
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
 
+  _addToFiltersByDomain: function(filter)
+  {
+    let key = keyByFilter[filter.text];
+    let domains = filter.domains || defaultDomains;
+    for (let domain in domains)
+    {
+      let filters = filtersByDomain[domain];
+      if (!filters)
+        filters = filtersByDomain[domain] = Object.create(null);
+
+      if (domains[domain])
+        filters[key] = filter;
+      else
+        filters[key] = false;
+    }
+  },
+
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
   add: function(filter)
   {
     if (filter instanceof ElemHideException)
     {
       if (filter.text in knownExceptions)
         return;
 
       let selector = filter.selector;
       if (!(selector in exceptions))
         exceptions[selector] = [];
       exceptions[selector].push(filter);
+
+      if (usingGetSelectorsForDomain)
+      {
+        // If this is the first exception for a previously unconditionally
+        // applied element hiding selector we need to take care to update the
+        // lookups.
+        let unconditionalFilters = filtersBySelector[selector];
+        if (unconditionalFilters)
+        {
+          for (let f of unconditionalFilters)
+            this._addToFiltersByDomain(f);
+          delete filtersBySelector[selector];
+          unconditionalSelectors = null;
+        }
+      }
+
       knownExceptions[filter.text] = true;
     }
     else
     {
       if (filter.text in keyByFilter)
         return;
 
-      let key;
-      do {
-        key = Math.random().toFixed(15).substr(5);
-      } while (key in filterByKey);
-
-      filterByKey[key] = filter;
+      let key = filterByKey.push(filter) - 1;
       keyByFilter[filter.text] = key;
 
-      if (usingGetSelectorsByDomain)
-      {
-        let filterId = filterIdByFilterText[filter.text];
-        if (filterId == undefined)

[Wladimir Palant, 2016/05/20 12:33:27]

That's one of the few cases where you need ===, because null == undefined
evaluates to true.

[Sebastian Noack, 2016/05/20 13:03:04]

We always use typeof when checking for undefined.

[kzar, 2016/05/21 04:43:09]

Acknowledged.

-        {
-          filterId = selectorByFilterId.push(filter.selector) - 1;
-          filterIdByFilterText[filter.text] = filterId;
-        }
-
-        let domainMatches = filter.domains || defaultDomains;
-

[Sebastian Noack, 2016/05/20 13:03:03]

Nit: It seems the code reads better without the blakn line here.

[kzar, 2016/05/21 04:43:09]

Done.

-        for (let domain in domainMatches)
-        {
-          let lookup;
-          if (domainMatches[domain])
-            lookup = activeFilterIdsByDomain;
+      if (usingGetSelectorsForDomain)
+      {
+        if (!(filter.domains || filter.selector in exceptions))
+        {
+          // The new filter's selector is unconditionally applied to all domains
+          let filters = filtersBySelector[filter.selector];
+          if (filters)
+          {
+            filters.push(filter);
+          }
           else
-            lookup = inactiveFilterIdsByDomain;
-
-          let filterIds = lookup[domain];
-          if (filterIds == undefined)
-            filterIds = lookup[domain] = [];
-
-          filterIds.push(filterId);
+          {
+            filtersBySelector[filter.selector] = [filter];
+            unconditionalSelectors = null;
+          }
+        }
+        else
+        {
+          // The new filter's selector only applies to some domains
+          this._addToFiltersByDomain(filter);
         }
       }
 
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
@@ skipping 14 matching lines @@
     else
     {
       if (!(filter.text in keyByFilter))
         return;
 
       let key = keyByFilter[filter.text];
       delete filterByKey[key];
       delete keyByFilter[filter.text];
       ElemHide.isDirty = true;
 
-      if (usingGetSelectorsByDomain)

[kzar, 2016/05/20 10:55:17]

I'm not too happy with this change it's kind of slow. When disabling large
subscriptions like EasyList that might be a problem.

(Come to think of it we also forgot to remove things from the lookup with the
earlier changes for this issue...)

-      {
-        let filterId = filterIdByFilterText[filter.text];
-        if (filterId)
-        {
-          delete filterIdByFilterText[filter.text];
-          delete selectorByFilterId[filterId];
-
-          let domains = Object.keys(filter.domains || defaultDomains);

[Wladimir Palant, 2016/05/20 12:33:27]

Why use Object.keys() here all the sudden rather than for..in loop?

[kzar, 2016/05/21 04:43:09]

Done.

-          let filterIdsByDomainLookups = [activeFilterIdsByDomain,
-                                          inactiveFilterIdsByDomain];
-          for (let domain of domains)
-          {
-            for (let filterIdsByDomain of filterIdsByDomainLookups)
-            {
-              let lookup = filterIdsByDomain[domain];
-              if (lookup)
-              {
-                let index = lookup.indexOf(filterId);
-                if (index != -1)
-                  lookup.splice(index, 1);
-              }
-            }
+      if (usingGetSelectorsForDomain)
+      {
+        let filters = filtersBySelector[filter.selector];
+        if (filters)
+        {
+          if (filters.length > 1)
+          {
+            let index = filters.indexOf(filter);
+            filters.splice(index, 1);
+          }
+          else
+          {
+            delete filtersBySelector[filter.selector];
+            unconditionalSelectors = null;
+          }
+        }
+        else
+        {
+          let domains = filter.domains || defaultDomains;
+          for (let domain in domains)
+          {
+            let filters = filtersByDomain[domain];
+            if (filters)
+              delete filters[key];
           }
         }
       }
     }
   },
 
   /**
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
    */
-  getException: function(/**String*/ selector, /**String*/ docDomain) /**ElemHideException*/
-  {
-    if (!(selector in exceptions))
+  getException: function(/**Filter*/ filter, /**String*/ docDomain) /**ElemHideException*/
+  {
+    if (!(filter.selector in exceptions))
       return null;
 
-    let list = exceptions[selector];
+    let list = exceptions[filter.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 89 matching lines @@
   },
 
   _generateCSSContent: function*()
   {
     // Grouping selectors by domains
     let domains = Object.create(null);
     let hasFilters = false;
     for (let key in filterByKey)
     {
       let filter = filterByKey[key];
+      let selector = filter.selector;
+      if (!selector)
+        continue;
+
       let domain = filter.selectorDomain || "";
 
       let list;
       if (domain in domains)
         list = domains[domain];
       else
       {
         list = Object.create(null);
         domains[domain] = list;
       }
-      list[filter.selector] = key;
+      list[selector] = key;
       hasFilters = true;
     }
 
     if (!hasFilters)
       throw Cr.NS_ERROR_NOT_AVAILABLE;
 
     function escapeChar(match)
     {
       return "\\" + match.charCodeAt(0).toString(16) + " ";
     }
@@ skipping 52 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, must not be
-   * used in Firefox (when usingFiltersByDomain is false).
+   * used in Firefox (when usingGetSelectorsForDomain is false).
    */
   getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
   {
-    if (!usingGetSelectorsByDomain)
+    if (!usingGetSelectorsForDomain)
       throw new Error("getSelectorsForDomain can not be used in Firefox!");
 
-    let selectors = [];
-
-    let seenFilterIds = Object.create(null);
+    if (!unconditionalSelectors)
+      unconditionalSelectors = Object.keys(filtersBySelector);
+    let selectors = specificOnly ? [] : unconditionalSelectors.slice();
+
+    let seenFilters = Object.create(null);
     let currentDomain = domain ? domain.toUpperCase() : "";
     while (true)
     {
       if (specificOnly && currentDomain == "")
         break;
 
-      let inactiveFilterIds = inactiveFilterIdsByDomain[currentDomain];
-      if (inactiveFilterIds)
-        for (let filterId of inactiveFilterIds)
-          seenFilterIds[filterId] = true;
-
-      let activeFilterIds = activeFilterIdsByDomain[currentDomain];
-      if (activeFilterIds)
-      {
-        for (let filterId of activeFilterIds)
-        {
-          if (filterId in seenFilterIds)
+      let filters = filtersByDomain[currentDomain];
+      if (filters)
+      {
+        for (let filterKey in filters)
+        {
+          if (filterKey in seenFilters)
             continue;
-          seenFilterIds[filterId] = true;
-
-          let selector = selectorByFilterId[filterId];
-          if (!this.getException(selector, domain))
-            selectors.push(selector);
+          seenFilters[filterKey] = true;
+
+          let filter = filters[filterKey];
+          if (filter && !this.getException(filter, domain))
+            selectors.push(filter.selector);
         }
       }
 
       if (currentDomain == "")
         break;
 
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
     return selectors;
   }
 };