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
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 "use strict";
 
 (function()
 {
-  let nonEmptyPageMaps = Object.create(null);
-  let pageMapCounter = 0;
+  let nonEmptyPageMaps = new Set();
 
   let PageMap = ext.PageMap = function()
   {
-    this._map = Object.create(null);
-    this._id = ++pageMapCounter;
+    this._map = new Map();
   };
   PageMap.prototype = {
     _delete(id)
     {
-      delete this._map[id];
+      let map = this._map;
 
-      if (Object.keys(this._map).length == 0)
-        delete nonEmptyPageMaps[this._id];
+      let deleted = map.delete(id);
+
+      if (deleted && map.size == 0)
+        nonEmptyPageMaps.delete(this);
     },
     keys()
     {
-      return Object.keys(this._map).map(ext.getPage);
+      return [...ext.mapIterable(this._map.keys(), ext.getPage)];
     },
     get(page)
     {
-      return this._map[page.id];
+      return this._map.get(page.id);
     },
     set(page, value)
     {
-      this._map[page.id] = value;
-      nonEmptyPageMaps[this._id] = this;
+      let map = this._map;
+      let prevSize = map.size;
+
+      map.set(page.id, value);
+
+      if (prevSize == 0)
+        nonEmptyPageMaps.add(this);
     },
     has(page)
     {
-      return page.id in this._map;
+      return this._map.has(page.id);
     },
     clear()
     {
-      for (let id in this._map)
-        this._delete(id);
+      let map = this._map;

[Sebastian Noack, 2017/04/29 22:46:32]

Why do you import this property into a local variable?

[Manish Jethani, 2017/05/04 14:47:33]

I wrongly assumed that this would make it faster. Now I know that's not the
case, at least in v8. I've changed it.

+
+      if (map.size == 0)
+        return;
+
+      map.clear();
+      nonEmptyPageMaps.delete(this);
     },
     delete(page)
     {
       this._delete(page.id);
     }
   };
 
   ext._removeFromAllPageMaps = pageId =>
   {
-    for (let pageMapId in nonEmptyPageMaps)
-      nonEmptyPageMaps[pageMapId]._delete(pageId);
+    for (let pageMap of nonEmptyPageMaps)
+      pageMap._delete(pageId);
   };
 
   /* Pages */
 
   let Page = ext.Page = function(tab)
   {
     this.id = tab.id;
     this._url = tab.url && new URL(tab.url);
 
     this.browserAction = new BrowserAction(tab.id);
     this.contextMenus = new ContextMenus(this);
   };
   Page.prototype = {
     get url()
     {
       // usually our Page objects are created from Chrome's Tab objects, which
       // provide the url. So we can return the url given in the constructor.
       if (this._url)
         return this._url;
 
       // but sometimes we only have the tab id when we create a Page object.
       // In that case we get the url from top frame of the tab, recorded by
       // the onBeforeRequest handler.
-      let frames = framesOfTabs[this.id];
+      let frames = framesOfTabs.get(this.id);
       if (frames)
       {
-        let frame = frames[0];
+        let frame = frames.get(0);
         if (frame)
           return frame.url;
       }
     },
     sendMessage(message, responseCallback)
     {
       chrome.tabs.sendMessage(this.id, message, responseCallback);
     }
   };
 
@@ skipping 44 matching lines @@
   };
 
   chrome.tabs.onUpdated.addListener((tabId, changeInfo, tab) =>
   {
     if (changeInfo.status == "loading")
       ext.pages.onLoading._dispatch(new Page(tab));
   });
 
   function createFrame(tabId, frameId)
   {
-    let frames = framesOfTabs[tabId];
+    let frames = framesOfTabs.get(tabId);
     if (!frames)
-      frames = framesOfTabs[tabId] = Object.create(null);
+    {
+      frames = new Map();
+      framesOfTabs.set(tabId, frames);
+    }
 
-    let frame = frames[frameId];
+    let frame = frames.get(frameId);
     if (!frame)
-      frame = frames[frameId] = {};
+    {
+      frame = Object.create(null);

[Sebastian Noack, 2017/04/29 22:46:32]

Why do we use an object with no prototype here again? If it is not used as a map
we should just use an object literal.

[Manish Jethani, 2017/05/04 14:47:33]

Again I assumed that an object with no prototype would have faster property
lookups (both hits and misses). This is in fact the case in Firefox after a
recent update, but in Chrome it actually slows things down. I've changed it
back.

+      frames.set(frameId, frame);
+    }
 
     return frame;
   }
 
   function updatePageFrameStructure(frameId, tabId, url, parentFrameId)
   {
     if (frameId == 0)
     {
       let page = new Page({id: tabId, url});
 
       ext._removeFromAllPageMaps(tabId);
 
       chrome.tabs.get(tabId, () =>
       {
         // If the tab is prerendered, chrome.tabs.get() sets
         // chrome.runtime.lastError and we have to dispatch the onLoading event,
         // since the onUpdated event isn't dispatched for prerendered tabs.
         // However, we have to keep relying on the unUpdated event for tabs that
         // are already visible. Otherwise browser action changes get overridden
         // when Chrome automatically resets them on navigation.
         if (chrome.runtime.lastError)
           ext.pages.onLoading._dispatch(page);
       });
     }
 
-    // Update frame parent and URL in frame structure
+    // Update frame URL and parent in frame structure
     let frame = createFrame(tabId, frameId);
     frame.url = new URL(url);
-    frame.parent = framesOfTabs[tabId][parentFrameId] || null;
+
+    let parentFrame = framesOfTabs.get(tabId).get(parentFrameId);
+    if (parentFrame)
+      frame.parent = parentFrame;
   }
 
   chrome.webRequest.onHeadersReceived.addListener(details =>
   {
     // We have to update the frame structure when switching to a new
     // document, so that we process any further requests made by that
     // document in the right context. Unfortunately, we cannot rely
     // on webNavigation.onCommitted since it isn't guaranteed to fire
     // before any subresources start downloading[1]. As an
     // alternative we use webRequest.onHeadersReceived for HTTP(S)
@@ skipping 78 matching lines @@
       updatePageFrameStructure(details.frameId, details.tabId, details.url,
                                details.parentFrameId);
     }
   });
 
   function forgetTab(tabId)
   {
     ext.pages.onRemoved._dispatch(tabId);
 
     ext._removeFromAllPageMaps(tabId);
-    delete framesOfTabs[tabId];
+    framesOfTabs.delete(tabId);
   }
 
   chrome.tabs.onReplaced.addListener((addedTabId, removedTabId) =>
   {
     forgetTab(removedTabId);
   });
 
   chrome.tabs.onRemoved.addListener(forgetTab);
 
   chrome.tabs.onActivated.addListener(details =>
@@ skipping 177 matching lines @@
 
   chrome.windows.onFocusChanged.addListener(windowId =>
   {
     if (windowId != chrome.windows.WINDOW_ID_NONE)
       updateContextMenu();
   });
 
 
   /* Web requests */
 
-  let framesOfTabs = Object.create(null);
+  let framesOfTabs = new Map();
 
   ext.getFrame = (tabId, frameId) =>
   {
-    return (framesOfTabs[tabId] || {})[frameId];
+    let frames = framesOfTabs.get(tabId);
+    if (frames)
+      return frames.get(frameId);

[Sebastian Noack, 2017/04/29 22:46:32]

How about:

  return frames && frames.get(frameId);

[Manish Jethani, 2017/05/04 14:47:33]

Done.

   };
 
   let handlerBehaviorChangedQuota =
     chrome.webRequest.MAX_HANDLER_BEHAVIOR_CHANGED_CALLS_PER_10_MINUTES;
 
   function propagateHandlerBehaviorChange()
   {
     // Make sure to not call handlerBehaviorChanged() more often than allowed
     // by chrome.webRequest.MAX_HANDLER_BEHAVIOR_CHANGED_CALLS_PER_10_MINUTES.
     // Otherwise Chrome notifies the user that this extension is causing issues.
@@ skipping 24 matching lines @@
   };
 
   chrome.tabs.query({}, tabs =>
   {
     tabs.forEach(tab =>
     {
       chrome.webNavigation.getAllFrames({tabId: tab.id}, details =>
       {
         if (details && details.length > 0)
         {
-          let frames = framesOfTabs[tab.id] = Object.create(null);
+          let frames = new Map();
+          framesOfTabs.set(tab.id, frames);
 
-          for (let i = 0; i < details.length; i++)
+          for (let detail of details)
           {
-            frames[details[i].frameId] = {
-              url: new URL(details[i].url),
-              parent: null
-            };
+            let frame = Object.create(null);
+            frame.url = new URL(detail.url);
+
+            frames.set(detail.frameId, frame);
           }
 
-          for (let i = 0; i < details.length; i++)
+          for (let detail of details)
           {
-            let {parentFrameId} = details[i];
+            let {parentFrameId} = detail;
 
             if (parentFrameId != -1)
-              frames[details[i].frameId].parent = frames[parentFrameId];
+              frames.get(detail.frameId).parent = frames.get(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,
@@ skipping 36 matching lines @@
 
     // Add "page" and "frame" if the message was sent by a content script.
     // If sent by popup or the background page itself, there is no "tab".
     if ("tab" in rawSender)
     {
       sender.page = new Page(rawSender.tab);
       sender.frame = {
         url: new URL(rawSender.url),
         get parent()
         {
-          let frames = framesOfTabs[rawSender.tab.id];
+          let frames = framesOfTabs.get(rawSender.tab.id);
 
           if (!frames)
             return null;
 
-          let frame = frames[rawSender.frameId];
+          let frame = frames.get(rawSender.frameId);
           if (frame)
-            return frame.parent;
+            return frame.parent || null;

[Sebastian Noack, 2017/04/29 22:46:32]

This seems unrelated.

[Manish Jethani, 2017/05/04 14:47:33]

frame.parent is either an object or undefined. I thought we'd consistently
return null here (see further above in this code). We could also try to make
sure it's always either an object or null to begin with, which we were trying
earlier, but that's too much work to maintain. It's better IMO not to set the
parent property on the frame object if there's no parent object available.

We could also just return undefined if we don't care about that.

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