--- a/browser/components/places/content/browserPlacesViews.js
+++ b/browser/components/places/content/browserPlacesViews.js
@@ -63,17 +63,17 @@ PlacesViewBase.prototype = {
 
     if (this._rootElt.localName == "menupopup")
       this._rootElt._built = false;
 
     this._result = val;
     if (val) {
       this._resultNode = val.root;
       this._rootElt._placesNode = this._resultNode;
-      this._domNodes = new WeakMap();
+      this._domNodes = new Map();
       this._domNodes.set(this._resultNode, this._rootElt);
 
       // This calls _rebuild through invalidateContainer.
       this._resultNode.containerOpen = true;
     }
     else {
       this._resultNode = null;
       delete this._domNodes;

--- a/browser/components/places/content/controller.js
+++ b/browser/components/places/content/controller.js
@@ -75,17 +75,17 @@ function PlacesController(aView) {
   this._view = aView;
   XPCOMUtils.defineLazyServiceGetter(this, "clipboard",
                                      "@mozilla.org/widget/clipboard;1",
                                      "nsIClipboard");
   XPCOMUtils.defineLazyGetter(this, "profileName", function () {
     return Services.dirsvc.get("ProfD", Ci.nsIFile).leafName;
   });
 
-  this._cachedLivemarkInfoObjects = new WeakMap();
+  this._cachedLivemarkInfoObjects = new Map();
 }
 
 PlacesController.prototype = {
   /**
    * The places view.
    */
   _view: null,
 

--- a/browser/components/places/content/treeView.js
+++ b/browser/components/places/content/treeView.js
@@ -46,17 +46,17 @@ PlacesTreeView.prototype = {
     return this.__dateService;
   },
 
   QueryInterface: XPCOMUtils.generateQI(PTV_interfaces),
 
   // Bug 761494:
   // ----------
   // Some addons use methods from nsINavHistoryResultObserver and
-  // nsINavHistoryResultTreeViewer, without QIing to these intefaces first.
+  // nsINavHistoryResultTreeViewer, without QIing to these interfaces first.
   // That's not a problem when the view is retrieved through the
   // <tree>.view getter (which returns the wrappedJSObject of this object),
   // it raises an issue when the view retrieved through the treeBoxObject.view
   // getter.  Thus, to avoid breaking addons, the interfaces are prefetched.
   classInfo: XPCOMUtils.generateCI({ interfaces: PTV_interfaces }),
 
   /**
    * This is called once both the result and the tree are set.
@@ -148,22 +148,31 @@ PlacesTreeView.prototype = {
    * container, this method will just return a calculated row value, without
    * making assumptions on existence of the node at that position.
    * @return aNode's row if it's in the rows list or if aForceBuild is set, -1
    *         otherwise.
    */
   _getRowForNode:
   function PTV__getRowForNode(aNode, aForceBuild, aParentRow, aNodeIndex) {
     if (aNode == this._rootNode)
-      throw "The root node is never visible";
+      throw new Error("The root node is never visible");
 
-    let ancestors = PlacesUtils.nodeAncestors(aNode);
-    for (let ancestor in ancestors) {
+    // A node is removed form the view either if it has no parent or if its
+    // root-ancestor is not the root node (in which case that's the node
+    // for which nodeRemoved was called).
+    let ancestors = [x for each (x in PlacesUtils.nodeAncestors(aNode))];
+    if (ancestors.length == 0 ||
+        ancestors[ancestors.length - 1] != this._rootNode) {
+      throw new Error("Removed node passed to _getRowForNode");
+    }
+
+    // Ensure that the entire chain is open, otherwise that node is invisible.
+    for (let ancestor of ancestors) {
       if (!ancestor.containerOpen)
-        throw "Invisible node passed to _getRowForNode";
+        throw new Error("Invisible node passed to _getRowForNode");
     }
 
     // Non-plain containers are initially built with their contents.
     let parent = aNode.parent;
     let parentIsPlain = this._isPlainContainer(parent);
     if (!parentIsPlain) {
       if (parent == this._rootNode)
         return this._rows.indexOf(aNode);
@@ -1092,17 +1101,17 @@ PlacesTreeView.prototype = {
     if (this._result) {
       this._result.removeObserver(this);
       this._rootNode.containerOpen = false;
     }
 
     if (val) {
       this._result = val;
       this._rootNode = this._result.root;
-      this._cellProperties = new WeakMap();
+      this._cellProperties = new Map();
       this._cuttingNodes = new Set();
     }
     else if (this._result) {
       delete this._result;
       delete this._rootNode;
       delete this._cellProperties;
       delete this._cuttingNodes;
     }

--- a/toolkit/components/places/nsLivemarkService.js
+++ b/toolkit/components/places/nsLivemarkService.js
@@ -658,28 +658,28 @@ function Livemark(aLivemarkInfo)
 {
   this.title = aLivemarkInfo.title;
   this.parentId = aLivemarkInfo.parentId;
   this.index = aLivemarkInfo.index;
 
   this._status = Ci.mozILivemark.STATUS_READY;
 
   // Hash of resultObservers, hashed by container.
-  this._resultObservers = new WeakMap();
-  // This keeps a list of the containers used as keys in the weakmap, since
+  this._resultObservers = new Map();
+  // This keeps a list of the containers used as keys in the map, since
   // it's not iterable.  In future may use an iterable Map.
   this._resultObserversList = [];
 
   // Sorted array of objects representing livemark children in the form
   // { uri, title, visited }.
   this._children = [];
 
   // Keeps a separate array of nodes for each requesting container, hashed by
   // the container itself.
-  this._nodes = new WeakMap();
+  this._nodes = new Map();
 
   this._guid = "";
   this._lastModified = 0;
 
   this.loadGroup = null;
   this.feedURI = null;
   this.siteURI = null;
   this.expireTime = 0;