Add m-esr52 at 52.6.0

1 files changed, 556 insertions, 0 deletions

diff --git a/devtools/client/performance/modules/logic/tree-model.js b/devtools/client/performance/modules/logic/tree-model.js
new file mode 100644
index 000000000..b6376ee8a
--- /dev/null
+++ b/devtools/client/performance/modules/logic/tree-model.js
@@ -0,0 +1,556 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+"use strict";
+
+const { JITOptimizations } = require("devtools/client/performance/modules/logic/jit");
+const FrameUtils = require("devtools/client/performance/modules/logic/frame-utils");
+
+/**
+ * A call tree for a thread. This is essentially a linkage between all frames
+ * of all samples into a single tree structure, with additional information
+ * on each node, like the time spent (in milliseconds) and samples count.
+ *
+ * @param object thread
+ *        The raw thread object received from the backend. Contains samples,
+ *        stackTable, frameTable, and stringTable.
+ * @param object options
+ *        Additional supported options
+ *          - number startTime
+ *          - number endTime
+ *          - boolean contentOnly [optional]
+ *          - boolean invertTree [optional]
+ *          - boolean flattenRecursion [optional]
+ */
+function ThreadNode(thread, options = {}) {
+  if (options.endTime == void 0 || options.startTime == void 0) {
+    throw new Error("ThreadNode requires both `startTime` and `endTime`.");
+  }
+  this.samples = 0;
+  this.sampleTimes = [];
+  this.youngestFrameSamples = 0;
+  this.calls = [];
+  this.duration = options.endTime - options.startTime;
+  this.nodeType = "Thread";
+  this.inverted = options.invertTree;
+
+  // Total bytesize of all allocations if enabled
+  this.byteSize = 0;
+  this.youngestFrameByteSize = 0;
+
+  let { samples, stackTable, frameTable, stringTable } = thread;
+
+  // Nothing to do if there are no samples.
+  if (samples.data.length === 0) {
+    return;
+  }
+
+  this._buildInverted(samples, stackTable, frameTable, stringTable, options);
+  if (!options.invertTree) {
+    this._uninvert();
+  }
+}
+
+ThreadNode.prototype = {
+  /**
+   * Build an inverted call tree from profile samples. The format of the
+   * samples is described in tools/profiler/ProfileEntry.h, under the heading
+   * "ThreadProfile JSON Format".
+   *
+   * The profile data is naturally presented inverted. Inverting the call tree
+   * is also the default in the Performance tool.
+   *
+   * @param object samples
+   *        The raw samples array received from the backend.
+   * @param object stackTable
+   *        The table of deduplicated stacks from the backend.
+   * @param object frameTable
+   *        The table of deduplicated frames from the backend.
+   * @param object stringTable
+   *        The table of deduplicated strings from the backend.
+   * @param object options
+   *        Additional supported options
+   *          - number startTime
+   *          - number endTime
+   *          - boolean contentOnly [optional]
+   *          - boolean invertTree [optional]
+   */
+  _buildInverted: function buildInverted(samples, stackTable, frameTable, stringTable,
+                                         options) {
+    function getOrAddFrameNode(calls, isLeaf, frameKey, inflatedFrame, isMetaCategory,
+                               leafTable) {
+      // Insert the inflated frame into the call tree at the current level.
+      let frameNode;
+
+      // Leaf nodes have fan out much greater than non-leaf nodes, thus the
+      // use of a hash table. Otherwise, do linear search.
+      //
+      // Note that this method is very hot, thus the manual looping over
+      // Array.prototype.find.
+      if (isLeaf) {
+        frameNode = leafTable[frameKey];
+      } else {
+        for (let i = 0; i < calls.length; i++) {
+          if (calls[i].key === frameKey) {
+            frameNode = calls[i];
+            break;
+          }
+        }
+      }
+
+      if (!frameNode) {
+        frameNode = new FrameNode(frameKey, inflatedFrame, isMetaCategory);
+        if (isLeaf) {
+          leafTable[frameKey] = frameNode;
+        }
+        calls.push(frameNode);
+      }
+
+      return frameNode;
+    }
+
+    const SAMPLE_STACK_SLOT = samples.schema.stack;
+    const SAMPLE_TIME_SLOT = samples.schema.time;
+    const SAMPLE_BYTESIZE_SLOT = samples.schema.size;
+
+    const STACK_PREFIX_SLOT = stackTable.schema.prefix;
+    const STACK_FRAME_SLOT = stackTable.schema.frame;
+
+    const getOrAddInflatedFrame = FrameUtils.getOrAddInflatedFrame;
+
+    let samplesData = samples.data;
+    let stacksData = stackTable.data;
+
+    // Caches.
+    let inflatedFrameCache = FrameUtils.getInflatedFrameCache(frameTable);
+    let leafTable = Object.create(null);
+
+    let startTime = options.startTime;
+    let endTime = options.endTime;
+    let flattenRecursion = options.flattenRecursion;
+
+    // Reused options object passed to InflatedFrame.prototype.getFrameKey.
+    let mutableFrameKeyOptions = {
+      contentOnly: options.contentOnly,
+      isRoot: false,
+      isLeaf: false,
+      isMetaCategoryOut: false
+    };
+
+    let byteSize = 0;
+    for (let i = 0; i < samplesData.length; i++) {
+      let sample = samplesData[i];
+      let sampleTime = sample[SAMPLE_TIME_SLOT];
+
+      if (SAMPLE_BYTESIZE_SLOT !== void 0) {
+        byteSize = sample[SAMPLE_BYTESIZE_SLOT];
+      }
+
+      // A sample's end time is considered to be its time of sampling. Its
+      // start time is the sampling time of the previous sample.
+      //
+      // Thus, we compare sampleTime <= start instead of < to filter out
+      // samples that end exactly at the start time.
+      if (!sampleTime || sampleTime <= startTime || sampleTime > endTime) {
+        continue;
+      }
+
+      let stackIndex = sample[SAMPLE_STACK_SLOT];
+      let calls = this.calls;
+      let prevCalls = this.calls;
+      let prevFrameKey;
+      let isLeaf = mutableFrameKeyOptions.isLeaf = true;
+      let skipRoot = options.invertTree;
+
+      // Inflate the stack and build the FrameNode call tree directly.
+      //
+      // In the profiler data, each frame's stack is referenced by an index
+      // into stackTable.
+      //
+      // Each entry in stackTable is a pair [ prefixIndex, frameIndex ]. The
+      // prefixIndex is itself an index into stackTable, referencing the
+      // prefix of the current stack (that is, the younger frames). In other
+      // words, the stackTable is encoded as a trie of the inverted
+      // callstack. The frameIndex is an index into frameTable, describing the
+      // frame at the current depth.
+      //
+      // This algorithm inflates each frame in the frame table while walking
+      // the stack trie as described above.
+      //
+      // The frame key is then computed from the inflated frame /and/ the
+      // current depth in the FrameNode call tree.  That is, the frame key is
+      // not wholly determinable from just the inflated frame.
+      //
+      // For content frames, the frame key is just its location. For chrome
+      // frames, the key may be a metacategory or its location, depending on
+      // rendering options and its position in the FrameNode call tree.
+      //
+      // The frame key is then used to build up the inverted FrameNode call
+      // tree.
+      //
+      // Note that various filtering functions, such as filtering for content
+      // frames or flattening recursion, are inlined into the stack inflation
+      // loop. This is important for performance as it avoids intermediate
+      // structures and multiple passes.
+      while (stackIndex !== null) {
+        let stackEntry = stacksData[stackIndex];
+        let frameIndex = stackEntry[STACK_FRAME_SLOT];
+
+        // Fetch the stack prefix (i.e. older frames) index.
+        stackIndex = stackEntry[STACK_PREFIX_SLOT];
+
+        // Do not include the (root) node in this sample, as the costs of each frame
+        // will make it clear to differentiate (root)->B vs (root)->A->B
+        // when a tree is inverted, a revert of bug 1147604
+        if (stackIndex === null && skipRoot) {
+          break;
+        }
+
+        // Inflate the frame.
+        let inflatedFrame = getOrAddInflatedFrame(inflatedFrameCache, frameIndex,
+                                                  frameTable, stringTable);
+
+        // Compute the frame key.
+        mutableFrameKeyOptions.isRoot = stackIndex === null;
+        let frameKey = inflatedFrame.getFrameKey(mutableFrameKeyOptions);
+
+        // An empty frame key means this frame should be skipped.
+        if (frameKey === "") {
+          continue;
+        }
+
+        // If we shouldn't flatten the current frame into the previous one, advance a
+        // level in the call tree.
+        let shouldFlatten = flattenRecursion && frameKey === prevFrameKey;
+        if (!shouldFlatten) {
+          calls = prevCalls;
+        }
+
+        let frameNode = getOrAddFrameNode(calls, isLeaf, frameKey, inflatedFrame,
+                                          mutableFrameKeyOptions.isMetaCategoryOut,
+                                          leafTable);
+        if (isLeaf) {
+          frameNode.youngestFrameSamples++;
+          frameNode._addOptimizations(inflatedFrame.optimizations,
+                                      inflatedFrame.implementation, sampleTime,
+                                      stringTable);
+
+          if (byteSize) {
+            frameNode.youngestFrameByteSize += byteSize;
+          }
+        }
+
+        // Don't overcount flattened recursive frames.
+        if (!shouldFlatten) {
+          frameNode.samples++;
+          if (byteSize) {
+            frameNode.byteSize += byteSize;
+          }
+        }
+
+        prevFrameKey = frameKey;
+        prevCalls = frameNode.calls;
+        isLeaf = mutableFrameKeyOptions.isLeaf = false;
+      }
+
+      this.samples++;
+      this.sampleTimes.push(sampleTime);
+      if (byteSize) {
+        this.byteSize += byteSize;
+      }
+    }
+  },
+
+  /**
+   * Uninverts the call tree after its having been built.
+   */
+  _uninvert: function uninvert() {
+    function mergeOrAddFrameNode(calls, node, samples, size) {
+      // Unlike the inverted call tree, we don't use a root table for the top
+      // level, as in general, there are many fewer entry points than
+      // leaves. Instead, linear search is used regardless of level.
+      for (let i = 0; i < calls.length; i++) {
+        if (calls[i].key === node.key) {
+          let foundNode = calls[i];
+          foundNode._merge(node, samples, size);
+          return foundNode.calls;
+        }
+      }
+      let copy = node._clone(samples, size);
+      calls.push(copy);
+      return copy.calls;
+    }
+
+    let workstack = [{ node: this, level: 0 }];
+    let spine = [];
+    let entry;
+
+    // The new root.
+    let rootCalls = [];
+
+    // Walk depth-first and keep the current spine (e.g., callstack).
+    do {
+      entry = workstack.pop();
+      if (entry) {
+        spine[entry.level] = entry;
+
+        let node = entry.node;
+        let calls = node.calls;
+        let callSamples = 0;
+        let callByteSize = 0;
+
+        // Continue the depth-first walk.
+        for (let i = 0; i < calls.length; i++) {
+          workstack.push({ node: calls[i], level: entry.level + 1 });
+          callSamples += calls[i].samples;
+          callByteSize += calls[i].byteSize;
+        }
+
+        // The sample delta is used to distinguish stacks.
+        //
+        // Suppose we have the following stack samples:
+        //
+        //   A -> B
+        //   A -> C
+        //   A
+        //
+        // The inverted tree is:
+        //
+        //     A
+        //    / \
+        //   B   C
+        //
+        // with A.samples = 3, B.samples = 1, C.samples = 1.
+        //
+        // A is distinguished as being its own stack because
+        // A.samples - (B.samples + C.samples) > 0.
+        //
+        // Note that bottoming out is a degenerate where callSamples = 0.
+
+        let samplesDelta = node.samples - callSamples;
+        let byteSizeDelta = node.byteSize - callByteSize;
+        if (samplesDelta > 0) {
+          // Reverse the spine and add them to the uninverted call tree.
+          let uninvertedCalls = rootCalls;
+          for (let level = entry.level; level > 0; level--) {
+            let callee = spine[level];
+            uninvertedCalls = mergeOrAddFrameNode(uninvertedCalls, callee.node,
+                                                  samplesDelta, byteSizeDelta);
+          }
+        }
+      }
+    } while (entry);
+
+    // Replace the toplevel calls with rootCalls, which now contains the
+    // uninverted roots.
+    this.calls = rootCalls;
+  },
+
+  /**
+   * Gets additional details about this node.
+   * @see FrameNode.prototype.getInfo for more information.
+   *
+   * @return object
+   */
+  getInfo: function (options) {
+    return FrameUtils.getFrameInfo(this, options);
+  },
+
+  /**
+   * Mimicks the interface of FrameNode, and a ThreadNode can never have
+   * optimization data (at the moment, anyway), so provide a function
+   * to return null so we don't need to check if a frame node is a thread
+   * or not everytime we fetch optimization data.
+   *
+   * @return {null}
+   */
+
+  hasOptimizations: function () {
+    return null;
+  }
+};
+
+/**
+ * A function call node in a tree. Represents a function call with a unique context,
+ * resulting in each FrameNode having its own row in the corresponding tree view.
+ * Take samples:
+ *  A()->B()->C()
+ *  A()->B()
+ *  Q()->B()
+ *
+ * In inverted tree, A()->B()->C() would have one frame node, and A()->B() and
+ * Q()->B() would share a frame node.
+ * In an uninverted tree, A()->B()->C() and A()->B() would share a frame node,
+ * with Q()->B() having its own.
+ *
+ * In all cases, all the frame nodes originated from the same InflatedFrame.
+ *
+ * @param string frameKey
+ *        The key associated with this frame. The key determines identity of
+ *        the node.
+ * @param string location
+ *        The location of this function call. Note that this isn't sanitized,
+ *        so it may very well (not?) include the function name, url, etc.
+ * @param number line
+ *        The line number inside the source containing this function call.
+ * @param number category
+ *        The category type of this function call ("js", "graphics" etc.).
+ * @param number allocations
+ *        The number of memory allocations performed in this frame.
+ * @param number isContent
+ *        Whether this frame is content.
+ * @param boolean isMetaCategory
+ *        Whether or not this is a platform node that should appear as a
+ *        generalized meta category or not.
+ */
+function FrameNode(frameKey, { location, line, category, isContent }, isMetaCategory) {
+  this.key = frameKey;
+  this.location = location;
+  this.line = line;
+  this.youngestFrameSamples = 0;
+  this.samples = 0;
+  this.calls = [];
+  this.isContent = !!isContent;
+  this._optimizations = null;
+  this._tierData = [];
+  this._stringTable = null;
+  this.isMetaCategory = !!isMetaCategory;
+  this.category = category;
+  this.nodeType = "Frame";
+  this.byteSize = 0;
+  this.youngestFrameByteSize = 0;
+}
+
+FrameNode.prototype = {
+  /**
+   * Take optimization data observed for this frame.
+   *
+   * @param object optimizationSite
+   *               Any JIT optimization information attached to the current
+   *               sample. Lazily inflated via stringTable.
+   * @param number implementation
+   *               JIT implementation used for this observed frame (baseline, ion);
+   *               can be null indicating "interpreter"
+   * @param number time
+   *               The time this optimization occurred.
+   * @param object stringTable
+   *               The string table used to inflate the optimizationSite.
+   */
+  _addOptimizations: function (site, implementation, time, stringTable) {
+    // Simply accumulate optimization sites for now. Processing is done lazily
+    // by JITOptimizations, if optimization information is actually displayed.
+    if (site) {
+      let opts = this._optimizations;
+      if (opts === null) {
+        opts = this._optimizations = [];
+      }
+      opts.push(site);
+    }
+
+    if (!this._stringTable) {
+      this._stringTable = stringTable;
+    }
+
+    // Record type of implementation used and the sample time
+    this._tierData.push({ implementation, time });
+  },
+
+  _clone: function (samples, size) {
+    let newNode = new FrameNode(this.key, this, this.isMetaCategory);
+    newNode._merge(this, samples, size);
+    return newNode;
+  },
+
+  _merge: function (otherNode, samples, size) {
+    if (this === otherNode) {
+      return;
+    }
+
+    this.samples += samples;
+    this.byteSize += size;
+    if (otherNode.youngestFrameSamples > 0) {
+      this.youngestFrameSamples += samples;
+    }
+
+    if (otherNode.youngestFrameByteSize > 0) {
+      this.youngestFrameByteSize += otherNode.youngestFrameByteSize;
+    }
+
+    if (this._stringTable === null) {
+      this._stringTable = otherNode._stringTable;
+    }
+
+    if (otherNode._optimizations) {
+      if (!this._optimizations) {
+        this._optimizations = [];
+      }
+      let opts = this._optimizations;
+      let otherOpts = otherNode._optimizations;
+      for (let i = 0; i < otherOpts.length; i++) {
+        opts.push(otherOpts[i]);
+      }
+    }
+
+    if (otherNode._tierData.length) {
+      let tierData = this._tierData;
+      let otherTierData = otherNode._tierData;
+      for (let i = 0; i < otherTierData.length; i++) {
+        tierData.push(otherTierData[i]);
+      }
+      tierData.sort((a, b) => a.time - b.time);
+    }
+  },
+
+  /**
+   * Returns the parsed location and additional data describing
+   * this frame. Uses cached data if possible. Takes the following
+   * options:
+   *
+   * @param {ThreadNode} options.root
+   *                     The root thread node to calculate relative costs.
+   *                     Generates [self|total] [duration|percentage] values.
+   * @param {boolean} options.allocations
+   *                  Generates `totalAllocations` and `selfAllocations`.
+   *
+   * @return object
+   *         The computed { name, file, url, line } properties for this
+   *         function call, as well as additional params if options specified.
+   */
+  getInfo: function (options) {
+    return FrameUtils.getFrameInfo(this, options);
+  },
+
+  /**
+   * Returns whether or not the frame node has an JITOptimizations model.
+   *
+   * @return {Boolean}
+   */
+  hasOptimizations: function () {
+    return !this.isMetaCategory && !!this._optimizations;
+  },
+
+  /**
+   * Returns the underlying JITOptimizations model representing
+   * the optimization attempts occuring in this frame.
+   *
+   * @return {JITOptimizations|null}
+   */
+  getOptimizations: function () {
+    if (!this._optimizations) {
+      return null;
+    }
+    return new JITOptimizations(this._optimizations, this._stringTable);
+  },
+
+  /**
+   * Returns the tiers used overtime.
+   *
+   * @return {Array<object>}
+   */
+  getTierData: function () {
+    return this._tierData;
+  }
+};
+
+exports.ThreadNode = ThreadNode;
+exports.FrameNode = FrameNode;