page-dependency-graph.js

/**
 * @license Copyright 2017 Google Inc. All Rights Reserved.
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0
 * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
 */
'use strict';

const ComputedArtifact = require('./computed-artifact');
const NetworkNode = require('./dependency-graph/network-node');
const CPUNode = require('./dependency-graph/cpu-node');
const GraphEstimator = require('./dependency-graph/estimator/estimator');
const TracingProcessor = require('../../lib/traces/tracing-processor');

// tasks shorter than 10 ms are unlikely have a significant impact
const MINIMUM_TASK_DURATION = 10000;
// video files tend to be enormous and throw off all graph traversals
const IGNORED_MIME_TYPES_REGEX = /^video/;

class PageDependencyGraphArtifact extends ComputedArtifact {
  get name() {
    return 'PageDependencyGraph';
  }

  get requiredNumberOfArtifacts() {
    return 2;
  }

  /**
   * @param {!WebInspector.NetworkRequest} record
   * @return {!Array<string>}
   */
  static getNetworkInitiators(record) {
    if (!record._initiator) return [];
    if (record._initiator.url) return [record._initiator.url];
    if (record._initiator.type === 'script') {
      const frames = record._initiator.stack.callFrames;
      return Array.from(new Set(frames.map(frame => frame.url))).filter(Boolean);
    }

    return [];
  }

  /**
   * @param {!Array<!WebInspector.NetworkRequest>} networkRecords
   * @return {!NetworkNodeOutput}
   */
  static getNetworkNodes(networkRecords) {
    const nodes = [];
    const idToNodeMap = new Map();
    const urlToNodeMap = new Map();

    networkRecords.forEach(record => {
      if (IGNORED_MIME_TYPES_REGEX.test(record.mimeType)) return;
      const node = new NetworkNode(record);
      nodes.push(node);
      idToNodeMap.set(record.requestId, node);

      if (urlToNodeMap.has(record.url)) {
        const list = urlToNodeMap.get(record.url);
        list.push(node);
      } else {
        urlToNodeMap.set(record.url, [node]);
      }
    });

    return {nodes, idToNodeMap, urlToNodeMap};
  }

  /**
   * @param {!TraceOfTabArtifact} traceOfTab
   * @return {!Array<!CPUNode>}
   */
  static getCPUNodes(traceOfTab) {
    const nodes = [];
    let i = 0;
    while (i < traceOfTab.mainThreadEvents.length) {
      const evt = traceOfTab.mainThreadEvents[i];

      // Skip all trace events that aren't schedulable tasks with sizable duration
      if (
        evt.name !== TracingProcessor.SCHEDULABLE_TASK_TITLE ||
        !evt.dur ||
        evt.dur < MINIMUM_TASK_DURATION
      ) {
        i++;
        continue;
      }

      // Capture all events that occurred within the task
      const children = [];
      i++; // Start examining events after this one
      for (
        const endTime = evt.ts + evt.dur;
        i < traceOfTab.mainThreadEvents.length && traceOfTab.mainThreadEvents[i].ts < endTime;
        i++
      ) {
        children.push(traceOfTab.mainThreadEvents[i]);
      }

      nodes.push(new CPUNode(evt, children));
    }

    return nodes;
  }

  /**
   * @param {!Node} rootNode
   * @param {!NetworkNodeOutput} networkNodeOutput
   */
  static linkNetworkNodes(rootNode, networkNodeOutput) {
    networkNodeOutput.nodes.forEach(node => {
      const initiators = PageDependencyGraphArtifact.getNetworkInitiators(node.record);
      if (initiators.length) {
        initiators.forEach(initiator => {
          const parentCandidates = networkNodeOutput.urlToNodeMap.get(initiator) || [rootNode];
          // Only add the initiator relationship if the initiator is unambiguous
          const parent = parentCandidates.length === 1 ? parentCandidates[0] : rootNode;
          parent.addDependent(node);
        });
      } else if (node !== rootNode) {
        rootNode.addDependent(node);
      }
    });
  }

  /**
   * @param {!Node} rootNode
   * @param {!NetworkNodeOutput} networkNodeOutput
   * @param {!Array<!CPUNode>} cpuNodes
   * @param {!TraceOfTabArtifact} traceOfTab
   */
  static linkCPUNodes(rootNode, networkNodeOutput, cpuNodes) {
    function addDependentNetworkRequest(cpuNode, reqId) {
      const networkNode = networkNodeOutput.idToNodeMap.get(reqId);
      if (!networkNode || networkNode.resourceType !== 'xhr') return;
      networkNode.addDependency(cpuNode);
    }

    function addDependencyOnUrl(cpuNode, url) {
      const candidates = networkNodeOutput.urlToNodeMap.get(url) || [];

      let minCandidate = null;
      let minDistance = Infinity;
      // Find the closest request that finished before this CPU task started
      candidates.forEach(candidate => {
        const distance = cpuNode.startTime - candidate.endTime;
        if (distance > 0 && distance < minDistance) {
          minCandidate = candidate;
          minDistance = distance;
        }
      });

      if (!minCandidate) return;
      cpuNode.addDependency(minCandidate);
    }

    const timers = new Map();
    for (const node of cpuNodes) {
      for (const evt of node.children) {
        if (!evt.args.data) continue;

        const url = evt.args.data.url;
        const stackTraceUrls = (evt.args.data.stackTrace || []).map(l => l.url).filter(Boolean);

        switch (evt.name) {
          case 'TimerInstall':
            timers.set(evt.args.data.timerId, node);
            stackTraceUrls.forEach(url => addDependencyOnUrl(node, url));
            break;
          case 'TimerFire': {
            const installer = timers.get(evt.args.data.timerId);
            if (!installer) break;
            installer.addDependent(node);
            break;
          }

          case 'InvalidateLayout':
          case 'ScheduleStyleRecalculation':
            stackTraceUrls.forEach(url => addDependencyOnUrl(node, url));
            break;

          case 'EvaluateScript':
            addDependencyOnUrl(node, url);
            stackTraceUrls.forEach(url => addDependencyOnUrl(node, url));
            break;

          case 'XHRReadyStateChange':
            // Only create the dependency if the request was completed
            if (evt.args.data.readyState !== 4) break;

            addDependencyOnUrl(node, url);
            stackTraceUrls.forEach(url => addDependencyOnUrl(node, url));
            break;

          case 'FunctionCall':
          case 'v8.compile':
            addDependencyOnUrl(node, url);
            break;

          case 'ParseAuthorStyleSheet':
            addDependencyOnUrl(node, evt.args.data.styleSheetUrl);
            break;

          case 'ResourceSendRequest':
            addDependentNetworkRequest(node, evt.args.data.requestId, evt);
            stackTraceUrls.forEach(url => addDependencyOnUrl(node, url));
            break;
        }
      }

      if (node.getNumberOfDependencies() === 0) {
        node.addDependency(rootNode);
      }
    }
  }

  /**
   * @param {!TraceOfTabArtifact} traceOfTab
   * @param {!Array<!WebInspector.NetworkRequest>} networkRecords
   * @return {!Node}
   */
  static createGraph(traceOfTab, networkRecords) {
    const networkNodeOutput = this.getNetworkNodes(networkRecords);
    const cpuNodes = this.getCPUNodes(traceOfTab);

    const rootRequest = networkRecords.reduce((min, r) => (min.startTime < r.startTime ? min : r));
    const rootNode = networkNodeOutput.idToNodeMap.get(rootRequest.requestId);

    this.linkNetworkNodes(rootNode, networkNodeOutput, networkRecords);
    this.linkCPUNodes(rootNode, networkNodeOutput, cpuNodes, traceOfTab);

    return rootNode;
  }

  /**
   * @param {!Node} rootNode
   * @return {}
   */
  static estimateGraph(rootNode) {
    return new GraphEstimator(rootNode).estimateWithDetails();
  }

  /**
   *
   * @param {!Node} rootNode
   */
  static printGraph(rootNode, widthInCharacters = 100) {
    function padRight(str, target, padChar = ' ') {
      while (str.length < target) {
        str += padChar;
      }
      return str;
    }

    const nodes = [];
    rootNode.traverse(node => nodes.push(node));
    nodes.sort((a, b) => a.startTime - b.startTime);

    const min = nodes[0].startTime;
    const max = nodes.reduce((max, node) => Math.max(max, node.endTime), 0);

    const totalTime = max - min;
    const timePerCharacter = totalTime / widthInCharacters;
    nodes.forEach(node => {
      const offset = Math.round((node.startTime - min) / timePerCharacter);
      const length = Math.ceil((node.endTime - node.startTime) / timePerCharacter);
      const bar = padRight('', offset) + padRight('', length, '=');

      const displayName = node.record ? node.record._url : node.type;
      // eslint-disable-next-line
      console.log(padRight(bar, widthInCharacters), `| ${displayName.slice(0, 30)}`);
    });
  }

  /**
   * @param {!Trace} trace
   * @param {!DevtoolsLog} devtoolsLog
   * @param {!ComputedArtifacts} artifacts
   * @return {!Promise<!Node>}
   */
  compute_(trace, devtoolsLog, artifacts) {
    const promises = [
      artifacts.requestTraceOfTab(trace),
      artifacts.requestNetworkRecords(devtoolsLog),
    ];

    return Promise.all(promises).then(([traceOfTab, networkRecords]) => {
      return PageDependencyGraphArtifact.createGraph(traceOfTab, networkRecords);
    });
  }
}

module.exports = PageDependencyGraphArtifact;

/**
 * @typedef {{
 *    nodes: !Array<!NetworkNode>,
 *    idToNodeMap: !Map<string, !NetworkNode>,
 *    urlToNodeMap: !Map<string, !Array<!NetworkNode>
 * }}
 */
PageDependencyGraphArtifact.NetworkNodeOutput; // eslint-disable-line no-unused-expressions