Issue 5161 - Use maps and sets where appropriate

ext/background.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-2017 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 10 matching lines @@
 {
   let nonEmptyPageMaps = new Set();
 
   let PageMap = ext.PageMap = function()
   {
     this._map = new Map();
   };
   PageMap.prototype = {
     _delete(id)
     {
-      if (this._map.delete(id) && this._map.size == 0)
+      this._map.delete(id);
+
+      if (this._map.size == 0)
         nonEmptyPageMaps.delete(this);
     },
     keys()
     {
       return this._map.keys();
     },
     get(page)
     {
       return this._map.get(page.id);
     },
     set(page, value)
     {
-      let prevSize = this._map.size;
-
       this._map.set(page.id, value);
-
-      if (prevSize == 0)

[Sebastian Noack, 2017/05/17 06:46:48]

Why not just calling nonEmptyPageMaps.add() no matter what? The behavior will be
the same.

[Manish Jethani, 2017/05/17 21:53:24]

Well, add could be an expensive operation, depending on the way the Set object
has been implemented.

I actually looked this up. Both Chrome and Firefox use the Close table
implementation:

https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables

https://github.com/jorendorff/dht/blob/2d8cf136bad0fa92aeb2b7898cc59b46b471ab...

https://cs.chromium.org/chromium/src/v8/src/js/collection.js?q=generichash+pa...

https://hg.mozilla.org/mozilla-central/file/261a33fad371/js/src/ds/OrderedHas...

The add operation is "O(1)", but basically it involves a hash operation and a
lookup. The speed of the lookup depends on how many items are in the bucket,
that's a linear search at some point, but given the parameters used it's going
to be ~2.67 iterations on average and N iterations in the unlikely worst case (N
being the number of entries in the set).

I don't know how they hash an object reference, but Firefox for example will try
to "scramble" the output of the hash function if it's based on a pointer in
memory, for security reasons:

https://dxr.mozilla.org/mozilla-beta/rev/8bf3d5c1b4b0de2673a74d56c7399a80c543...

Anyway, so it's probably not too bad in the grand scheme of things. On the other
hand, these things can easily add up to a bad user experience.

Does it hurt to avoid calling that method?

nonEmptyPageMaps is a bit of a micro-optimization to begin with. I don't know if
it adds much value. It's only used in ext._removeFromAllPageMaps, which is only
called for top-level frames.

[Sebastian Noack, 2017/05/18 12:23:00]

It seems there will be up to 7 PageMap objects at any given time. So I suppose
even a linear search over all entries would still be ridicolous fast.
It's additional logic, which makes the code harder to maintain.

Also notice that checking the size of the map isn't for free either. So perhaps
you want to benchmark this code with and without checking for the map being
empty, with a realistic number of entries in nonEmptyPageMaps (i.e. 7).
nonEmptyPageMaps is not a micro-optimization, but was an attempt to mitigate
memory leaks. But it seems we could just use a WeakSet() that holds all active
instances now.

[Manish Jethani, 2017/05/18 21:16:37]

Fair enough.
The size of the map is a value in memory, it's practically free.

Also equally relevant to the number of PageMap objects is the number of times
the set method is called.
What I really meant here was that nonEmptyPageMaps could just have been
allPageMaps, then it would only have to be updated in the constructor (a total
of about 7 times?). The only reason the program keeps track of the empty status
is to avoid calling delete on empty maps, which is exactly the kind of
optimization I'm trying to do here, only far less useful. Why not just make it
allPageMaps? Then we don't have to keep track of the empty status, hence code
that's easier to maintain.

Since there are only about 7 PageMap objects, we could just keep all of them in
memory, whether they're empty or not. We could also just make allPageMaps a
WeakSet object.

Now that I look at the code again, we could simply replace ext.PageMap with
ext.createPageMap, a function that would look like this:

  let allPageMaps = new Set(); // or WeakSet
  function createPageMap()
  {
    let pageMap = new Map();
    allPageMaps.add(pageMap);
    return pageMap;
  }

Instead of "new ext.PageMap()" you would do "ext.createPageMap()" and that would
be it.

[Sebastian Noack, 2017/05/18 21:42:12]

That is basically what I meant to suggest. However, I don't quite get why you
want to introduce a factory function, rather than having the constructor
register the instance? Also please use a WeakSet, as it doesn't add any
complexity, but is memory-safe in case we create temporary instances.

For reference, the reason I didn't do so when I initially wrote this code, and
the reason for keeping track of the non-empty PageMaps (with an array), was that
back then WeakSet wasn't there yet, and this way at least empty instances
wouldn't be leaked. Not calling delete() for these was a mere side-effect.

[Manish Jethani, 2017/05/18 22:39:09]

I was hoping to get rid of all the methods entirely since they seemed to be mere
passthroughs to the underlying Map object, but it turns out it's not that simple
because ext.PageMap deals with page objects where the underlying Map object
deals with their IDs.
We forgot that WeakSet doesn't allow iteration. We can't use it here.

JavaScript still doesn't have weak references, that's sad. We had this in AS3. I
think I had a blog post about it back in the day. Anyway, looks like weak
references are coming in ES2017 or something.

[Sebastian Noack, 2017/05/19 12:01:14]

Hmm, perhaps we should have stayed with the nonEmptyPageMap approach then. This
way we at least make sure that temporary instances get eventually cleaned up
when all pages they held are gone.

I just carefully checked all places that use a PageMap and it seems all
instances are created once and never go out of scope. So while this shouldn't
cause a memory leaks with the current code base, I'm mildly concerned we might
have a use case for temporary instances in the future, and whoever might
introduce these might not be aware that PageMaps are leaked.

Eventually, I want to get rid of the abstraction layer, i.e. ext.*, including
PageMaps, all together, and have all code use the chrome.* (or browser.*) API
and tabIds directly. The only reason we have this abstraction layer was so that
we could support Safari, however, we no longer support anything else than
Chrome, Firefox and Edge which all have roughly the same API, with this code.

[Manish Jethani, 2017/05/19 16:20:34]

Yeah, I wasn't too excited about this change either after I learnt that we
couldn't use a WeakSet. I've reverted it now and removed the unnecessary logic
as well.
I see, thanks.

When I feel like I know enough about the code, I'll see if I can come up with
something for this.

[Sebastian Noack, 2017/05/19 17:33:14]

That'd be awesome. :)

-        nonEmptyPageMaps.add(this);
+      nonEmptyPageMaps.add(this);
     },
     has(page)
     {
       return this._map.has(page.id);
     },
     clear()
     {
-      if (this._map.size == 0)
-        return;
-
       this._map.clear();
       nonEmptyPageMaps.delete(this);
     },
     delete(page)
     {
       this._delete(page.id);
     }
   };
 
   ext._removeFromAllPageMaps = pageId =>
@@ skipping 479 matching lines @@
     tabs.forEach(tab =>
     {
       chrome.webNavigation.getAllFrames({tabId: tab.id}, details =>
       {
         if (details && details.length > 0)
         {
           let frames = new Map();
           framesOfTabs.set(tab.id, frames);
 
           for (let detail of details)
-            frames.set(detail.frameId, {url: new URL(detail.url)});
-
-          for (let detail of details)
           {
-            let {parentFrameId} = detail;
-
-            if (parentFrameId != -1)
-              frames.get(detail.frameId).parent = frames.get(parentFrameId);
+            let frame = {url: new URL(detail.url)};
+            frames.set(detail.frameId, frame);
+
+            if (detail.parentFrameId != -1)
+              frame.parent = frames.get(detail.parentFrameId);
           }
         }
       });
     });
   });
 
   chrome.webRequest.onBeforeRequest.addListener(details =>
   {
     // The high-level code isn't interested in requests that aren't
     // related to a tab or requests loading a top-level document,
     // those should never be blocked.
     if (details.tabId == -1 || details.type == "main_frame")
+      return;
+
+    // Filter out requests from non web protocols. Ideally, we'd explicitly
+    // specify the protocols we are interested in (i.e. http://, https://,
+    // ws:// and wss://) with the url patterns, given below, when adding this
+    // listener. But unfortunately, Chrome <=57 doesn't support the WebSocket
+    // protocol and is causing an error if it is given.
+    let url = new URL(details.url);
+    if (url.protocol != "http:" && url.protocol != "https:" &&
+        url.protocol != "ws:" && url.protocol != "wss:")
       return;
 
     // We are looking for the frame that contains the element which
     // has triggered this request. For most requests (e.g. images) we
     // can just use the request's frame ID, but for subdocument requests
     // (e.g. iframes) we must instead use the request's parent frame ID.
     let {frameId, type} = details;
     if (type == "sub_frame")
-    {
       frameId = details.parentFrameId;
-      type = "SUBDOCUMENT";
-    }
 
     let frame = ext.getFrame(details.tabId, frameId);
     if (frame)
     {
       let results = ext.webRequest.onBeforeRequest._dispatch(
-        new URL(details.url),
-        type.toUpperCase(),
-        new Page({id: details.tabId}),
-        frame
+        url, type, new Page({id: details.tabId}), frame
       );
 
       if (results.indexOf(false) != -1)
         return {cancel: true};
     }
   }, {urls: ["<all_urls>"]}, ["blocking"]);
 
 
   /* Message passing */
 
@@ skipping 10 matching lines @@
         url: new URL(rawSender.url),
         get parent()
         {
           let frames = framesOfTabs.get(rawSender.tab.id);
 
           if (!frames)
             return null;
 
           let frame = frames.get(rawSender.frameId);
           if (frame)
             return frame.parent || null;

[Sebastian Noack, 2017/05/17 06:46:48]

Any particular reason you force the return value to be null rather than
undefined?

[Manish Jethani, 2017/05/17 21:53:24]

Just for consistency, nothing else.

 
           return frames.get(0) || null;
         }
       };
     }
 
     return ext.onMessage._dispatch(
       message, sender, sendResponse
     ).indexOf(true) != -1;
   });
@@ skipping 92 matching lines @@
   ext.windows = {
     create(createData, callback)
     {
       chrome.windows.create(createData, createdWindow =>
       {
         afterTabLoaded(callback)(createdWindow.tabs[0]);
       });
     }
   };
 }());