dom/chrome-webidl/DominatorTree.webidl

   1 /* -*- Mode: IDL; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* This Source Code Form is subject to the terms of the Mozilla Public
   3  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
   4  * You can obtain one at http://mozilla.org/MPL/2.0/.
   5  */
   6
   7 typedef unsigned long long NodeId;
   8 typedef unsigned long long NodeSize;
   9
  10 /**
  11  * In a directed graph with a root node `R`, a node `A` is said to "dominate" a
  12  * node `B` iff every path from `R` to `B` contains `A`. A node `A` is said to
  13  * be the "immediate dominator" of a node `B` iff it dominates `B`, is not `B`
  14  * itself, and does not dominate any other nodes which also dominate `B` in
  15  * turn.
  16  *
  17  * If we take every node from a graph `G` and create a new graph `T` with edges
  18  * to each node from its immediate dominator, then `T` is a tree (each node has
  19  * only one immediate dominator, or none if it is the root). This tree is called
  20  * a "dominator tree".
  21  *
  22  * This interface represents a dominator tree constructed from a HeapSnapshot's
  23  * heap graph. The domination relationship and dominator trees are useful tools
  24  * for analyzing heap graphs because they tell you:
  25  *
  26  *   - Exactly what could be reclaimed by the GC if some node `A` became
  27  *     unreachable: those nodes which are dominated by `A`,
  28  *
  29  *   - The "retained size" of a node in the heap graph, in contrast to its
  30  *     "shallow size". The "shallow size" is the space taken by a node itself,
  31  *     not counting anything it references. The "retained size" of a node is its
  32  *     shallow size plus the size of all the things that would be collected if
  33  *     the original node wasn't (directly or indirectly) referencing them. In
  34  *     other words, the retained size is the shallow size of a node plus the
  35  *     shallow sizes of every other node it dominates. For example, the root
  36  *     node in a binary tree might have a small shallow size that does not take
  37  *     up much space itself, but it dominates the rest of the binary tree and
  38  *     its retained size is therefore significant (assuming no external
  39  *     references into the tree).
  40  */
  41 [ChromeOnly, Exposed=(Window,Worker)]
  42 interface DominatorTree {
  43   /**
  44    * The `NodeId` for the root of the dominator tree. This is a "meta-root" in
  45    * that it has an edge to each GC root in the heap snapshot this dominator
  46    * tree was created from.
  47    */
  48   readonly attribute NodeId root;
  49
  50   /**
  51    * Get the retained size of the node with the given id. If given an invalid
  52    * id, null is returned. Throws an error on OOM.
  53    */
  54   [Throws]
  55   NodeSize? getRetainedSize(NodeId node);
  56
  57   /**
  58    * Get the set of ids of nodes immediately dominated by the node with the
  59    * given id. The resulting array is sorted by greatest to least retained
  60    * size. If given an invalid id, null is returned. Throws an error on OOM.
  61    */
  62   [Throws]
  63   sequence<NodeId>? getImmediatelyDominated(NodeId node);
  64
  65   /**
  66    * Get the immediate dominator of the node with the given id. Returns null if
  67    * given an invalid id, or the id of the root node.
  68    */
  69   NodeId? getImmediateDominator(NodeId node);
  70 };