Issue 4167 - getSelectorsForDomain criteria + keys

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 19 matching lines @@
 var filterByKey = [];
 
 /**
  * Lookup table, keys of the filters by filter text
  * @type Object
  */
 var keyByFilter = Object.create(null);
 
 /**
  * Indicates whether we are using the getSelectorsForDomain function and
- * therefore mainting the required filtersByDomain, filtersBySelector and
- * unconditionalSelectors lookups. (Will be false for Firefox)
+ * therefore maintaining the required filtersByDomain, filterKeysBySelector,
+ * unconditionalSelectors and unconditionalFilterKeys lookups.
+ * (Will be false for Firefox)
  * @type Boolean
  */
 var usingGetSelectorsForDomain = !("nsIStyleSheetService" in Ci);

[Wladimir Palant, 2016/09/19 08:53:59]

This flag needs to go - we'll be using this functionality in Firefox as well
now.

[kzar, 2016/09/19 16:54:31]

Done.

 
 /**
  * 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
+ * Lookup table, filters keys by selector. (Only contains filters that have a
  * selector that is unconditionally matched for all domains.)
  */
-var filtersBySelector = Object.create(null);
+var filterKeysBySelector = Object.create(null);
 
 /**
- * This array caches the keys of filtersBySelector table (selectors which
+ * This array caches the keys of filterKeysBySelector table (selectors which
  * unconditionally apply on all domains). It will be null if the cache needs to
  * be rebuilt.
  */
 var unconditionalSelectors = null;
 
 /**
+ * This array caches the values of filterKeysBySelector table (filterIds for
+ * selectors which unconditionally apply on all domains). It will be null if the
+ * cache needs to be rebuilt.
+ */
+var unconditionalFilterKeys = 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
  */
 var knownExceptions = Object.create(null);
@@ skipping 11 matching lines @@
 var ElemHide = exports.ElemHide =
 {
   /**
    * Removes all known filters
    */
   clear: function()
   {
     filterByKey = [];
     keyByFilter = Object.create(null);
     filtersByDomain = Object.create(null);
-    filtersBySelector = Object.create(null);
-    unconditionalSelectors = null;
+    filterKeysBySelector = Object.create(null);
+    unconditionalSelectors = unconditionalFilterKeys = null;
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
     FilterNotifier.emit("elemhideupdate");
   },
 
-  _addToFiltersByDomain: function(filter)
+  _addToFiltersByDomain: function(key, 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
@@ skipping 15 matching lines @@
       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)
+        let unconditionalFilterKeys = filterKeysBySelector[selector];
+        if (unconditionalFilterKeys)
         {
-          for (let f of unconditionalFilters)
-            this._addToFiltersByDomain(f);
-          delete filtersBySelector[selector];
-          unconditionalSelectors = null;
+          for (let filterKey of unconditionalFilterKeys)
+            this._addToFiltersByDomain(filterKey, filterByKey[filterKey]);
+          delete filterKeysBySelector[selector];
+          unconditionalSelectors = unconditionalFilterKeys = null;
         }
       }
 
       knownExceptions[filter.text] = true;
     }
     else
     {
       if (filter.text in keyByFilter)
         return;
 
       let key = filterByKey.push(filter) - 1;
       keyByFilter[filter.text] = key;
 
       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)
+          let filterKeys = filterKeysBySelector[filter.selector];
+          if (filterKeys)
           {
-            filters.push(filter);
+            filterKeys.push(filter);

[Wladimir Palant, 2016/09/19 08:53:59]

Shouldn't you push `key` here?

Given that you have unit tests, I guess that you need to make sure all edge
cases are really tested?

[kzar, 2016/09/19 16:54:30]

As discussed in IRC it turns out this branch was rarely used and mostly
irrelevant even when it was. I have simplified this logic and related data
structure.

           }
           else
           {
-            filtersBySelector[filter.selector] = [filter];
-            unconditionalSelectors = null;
+            filterKeysBySelector[filter.selector] = [key];
+            unconditionalSelectors = unconditionalFilterKeys = null;
           }
         }
         else
         {
           // The new filter's selector only applies to some domains
-          this._addToFiltersByDomain(filter);
+          this._addToFiltersByDomain(key, filter);
         }
       }
     }
 
     FilterNotifier.emit("elemhideupdate");
   },
 
   /**
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
@@ skipping 15 matching lines @@
     {
       if (!(filter.text in keyByFilter))
         return;
 
       let key = keyByFilter[filter.text];
       delete filterByKey[key];
       delete keyByFilter[filter.text];
 
       if (usingGetSelectorsForDomain)
       {
-        let filters = filtersBySelector[filter.selector];
-        if (filters)
+        let filterKeys = filterKeysBySelector[filter.selector];
+        if (filterKeys)
         {
-          if (filters.length > 1)
+          if (filterKeys.length > 1)
           {
-            let index = filters.indexOf(filter);
-            filters.splice(index, 1);
+            let index = filterKeys.indexOf(key);
+            filterKeys.splice(index, 1);
           }
           else
           {
-            delete filtersBySelector[filter.selector];
-            unconditionalSelectors = null;
+            delete filterKeysBySelector[filter.selector];
+            unconditionalSelectors = unconditionalFilterKeys = null;
           }
         }
         else
         {
           let domains = filter.domains || defaultDomains;
           for (let domain in domains)
           {
             let filters = filtersByDomain[domain];
             if (filters)
               delete filters[key];
@@ skipping 18 matching lines @@
     for (let i = list.length - 1; i >= 0; i--)
       if (list[i].isActiveOnDomain(docDomain))
         return list[i];
 
     return null;
   },
 
   /**
    * Retrieves an element hiding filter by the corresponding protocol key
    */
-  getFilterByKey: function(/**String*/ key) /**Filter*/
+  getFilterByKey: function(/**Number*/ key) /**Filter*/
   {
     return (key in filterByKey ? filterByKey[key] : null);
   },
 
   /**
    * Returns a list of all selectors as a nested map. On first level, the keys
    * are all values of `ElemHideBase.selectorDomain` (domains on which these
    * selectors should apply, ignoring exceptions). The values are maps again,
    * with the keys being selectors and values the corresponding filter keys.
    * @returns {Map.<String,Map<String,String>>}
@@ skipping 12 matching lines @@
 
       if (!domains.has(domain))
         domains.set(domain, new Map());
       domains.get(domain).set(selector, key);
     }
 
     return domains;
   },
 
   /**
-   * Returns a list of all selectors active on a particular domain, must not be
-   * used in Firefox (when usingGetSelectorsForDomain is false).
+   * Returns a list of selectors that apply on each website unconditionally.
+   * @returns {String[]}
    */
-  getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
+  getUnconditionalSelectors: function()
+  {
+    if (!usingGetSelectorsForDomain)
+      throw new Error("getUconditionalSelectors can not be used in Firefox!");
+
+    if (!unconditionalSelectors)
+      unconditionalSelectors = Object.keys(filterKeysBySelector);
+    return unconditionalSelectors.slice();
+  },
+
+  /**
+   * Returns a list of all selectors active on a particular domain.
+   * Returns a list of filterKeys for selectors that apply on each website
+   * unconditionally.
+   * @returns {Number[]}
+   */
+  getUnconditionalFilterKeys: function()
+  {
+    if (!usingGetSelectorsForDomain)
+      throw new Error("getUconditionalFilterKeys can not be used in Firefox!");
+
+    if (!unconditionalFilterKeys)
+    {
+      let selectors = this.getUnconditionalSelectors();
+      unconditionalFilterKeys = [];
+      for (let selector of selectors)
+        for (let key of filterKeysBySelector[selector])
+          unconditionalFilterKeys.push(key);

[Wladimir Palant, 2016/09/19 08:53:59]

On Firefox we actually need a mapping from selectors to filter keys (one key per
selector). So it should be best if we push only the first key for each selector,
then the selector and key at the same position in the array will belong
together.

[kzar, 2016/09/19 16:54:31]

Since we only store one key per unconditional selector now anyway this has been
taken care of :)

+    }
+    return unconditionalFilterKeys.slice();
+  },
+
+  /**
+   * Returns a list of all selectors active on a particular domain. Optionally
+   * a list of corresponding filter keys for the selectors can be returned too.
+   * (Must not be used in Firefox - when usingGetSelectorsForDomain is false).

[Wladimir Palant, 2016/09/19 08:53:59]

Actually, it will be used in Firefox now, that's the only platform using filter
keys ;)

[kzar, 2016/09/19 16:54:31]

Done.

+   */
+  getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly,
+                                  /**Boolean*/ noUnconditional,
+                                  /**Boolean*/ provideFilterKeys)
   {
     if (!usingGetSelectorsForDomain)
       throw new Error("getSelectorsForDomain can not be used in Firefox!");
 
-    if (!unconditionalSelectors)
-      unconditionalSelectors = Object.keys(filtersBySelector);
-    let selectors = specificOnly ? [] : unconditionalSelectors.slice();
+    let filterKeys = [];
+    let selectors = [];
+    if (!(specificOnly || noUnconditional))

[Wladimir Palant, 2016/09/19 08:53:59]

Personally, I find this easier to understand if you get rid of parentheses:

  if (!specificOnly && !noUnconditional)

[kzar, 2016/09/19 16:54:30]

Done.

+    {
+      selectors = this.getUnconditionalSelectors();
+      if (provideFilterKeys)
+        filterKeys = this.getUnconditionalFilterKeys();
+    }
 
     let seenFilters = Object.create(null);
     let currentDomain = domain ? domain.toUpperCase() : "";
     while (true)
     {
       if (specificOnly && currentDomain == "")
         break;
 
       let filters = filtersByDomain[currentDomain];
       if (filters)
       {
         for (let filterKey in filters)
         {
           if (filterKey in seenFilters)
             continue;
           seenFilters[filterKey] = true;
 
           let filter = filters[filterKey];
           if (filter && !this.getException(filter, domain))
+          {
             selectors.push(filter.selector);
+            // It is faster to always push the key, even if not required.
+            filterKeys.push(filterKey);
+          }
         }
       }
 
       if (currentDomain == "")
         break;
 
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
-    return selectors;
+    if (provideFilterKeys)
+      return [selectors, filterKeys];
+    else
+      return selectors;
   }
 };